[Language: Haskell]

Part 1- 8.82 ms

Part 2 -1.16 s

Came up with a pretty nice solution for Part 1. Built a GF(2) matrix (bit masks represented using integers) where each row corresponds to a light, and the columns are buttons that will toggle that particular light. (A 1 indicates that that particular button will toggle that light.) Set up a linear system and solve via Gaussian elimination to determine pivot and free variables (button presses). Back substitute with all free variables set to 0 to get a single solution. Then set different combinations of free variables to 1 with that solution to find the optimal (minimal) solution. GF(2) is quite elegant here, as multiplying two rows of the matrix is a simple fast XOR operation.

Part 2 was nasty, nasty, nasty. I knew I needed to abandon GF(2) and use a full linear integer system to solve this. But all my attempts to prune the search space were fruitless. I ultimately did what a lot of other people here did - pipe the constraints into Z3, call Z3 from Haskell, and then get the answer back and display it. Not my finest moment, but oh well.