Start by parsing the input:

import           Data.List.Split (splitOn)

parse :: String -> [(Int, [[Int]], [Int])]
parse = map (line . words) . lines
  where
    line (t : ws) = 
      (target t, map list (init ws), list (last ws))
    target s = fromBits . init $ tail s
    list = map read . splitOn "," . init . tail

Of interest is the lighting sequence, which is represented as dots (.) and hashes (#). You can think of this as a number expressed as zeroes and ones:

fromBits :: [Char] -> Int
fromBits = foldl f 0 . reverse
  where
    f acc '.' = acc * 2
    f acc '#' = acc * 2 + 1

And so we move onto the first part.

The first part requires us to find the combinations of buttons that can result in the lighting sequence, with repetitions allowed. Pressing once switches on the lights, and pressing a second time switches it off. This behavior is identical to XOR! Therefore, the first part is a combination-sum problem, but using XOR, so a combination-xor problem if you will.

First, we’d need to convert a button into its bitwise form:

import           Data.Bits       (bit, xor, (.|.))
import           Control.Monad       (filterM)

toBits :: [Int] -> Int
toBits = foldl1 (.|.) . map bit

Next, we require the powerset of all possible buttons:

powerset [] = [[]]
powerset (x : xs) = map (x :) subset ++ subset
  where
    subset = powerset xs

Thus, our combination-xor is defined like so:

comboXor target = 
  filter ((== target) . foldl xor 0) . powerset

And the solution to the first part, is simply the application of comboXor to each line of the input, and finding the smallest possible sequence in each solution:

p1 = sum . map solveLine
  where
    solveLine (target, btns, _) =
      minimum . map length $ comboXor target (map toBits btns)

This part requires us to minimize a collection of equations to identify N coefficients. The solution for this part is given quite easily by LP/SAT solvers, but not so easily by hand. Some resources:

• Simplex Algorithm
• Gaussian Eliminiation

Finally, a main function to wrap it all up:

main = do
  n <- parse <$> getContents
  print $ p1 n