huseyinyilmaz / light-switch-problem-solver

Light switch problem solver

Light switch problem solver

I stumble upon this problem on a youtube video about battle field 4

There are certain number of lights in a room. There are also certain number of switches. Every switch opens some variaty of lights. If a light is already lit, switch closes the light. If it is not lit, it opens the light.

For instance in the diagram we have 2 lights A and B. We also have a switch S. Light A is lit and light B is not lit.

+----------+---------+
|##########|         |      +--+
|### A ####|    B    |      |S |
|##########|         |      +-++
+----+-----+----+----+        |
     |          |             |
     +----------+-------------+

If we press the switch S which is connected to Light A and B, Light A will be turned off and ligt B will be runed on.

+----------+---------+
|          |#########|      +--+
|    A     |### B ###|      |S#|
|          |#########|      +-++
+----+-----+----+----+        |
     |          |             |
     +----------+-------------+

Things get little more complicated if we have multiple switches connected to same light. Here are 3 ligts with 2 switches. Light B is connected to both switches So if we press one button light B will be turned on and if we press it again light will be turned off.

1 - Initial state

       +--------+-----------------+
       |        |                 |

+-------+---+---+----+--+ ++-+ | | | | | A | B | C | +--+ +--+ | | | | +---+---+---+---+-------+ ++-+ | | | +-------+--------------------+

2 - Turn on switch T

+-------+---+---+----+--+ ++-+ | #######| | A ## C ##| +--+ +--+ | #######| +---+---+---+---+-------+ ++-+ | | | +-------+--------------------+

3 - Turn on switch S

+-------+---+---+----+--+ ++-+ B +--+ +--+ +---+---+---+---+-------+ ++-+ | | | +-------+--------------------+

So problem is given the number of switches and lights and specification about how they are connected, find a switch combination that lits all the lights.

Here is the types for the solver.

module Solver where

type LightName = String
type SwitchName = String

data Switch = Switch SwitchName [LightName] deriving (Show, Eq)

solve :: [LightName] -> [Switch] -> Maybe [SwitchName]
solve _lns _ss = Nothing

Run unittest against you solution by

stack test

Lastly here here is a example fucntion call that finds the solution for 1 light and 1 switch

*Main> solve ["A"] [Switch {switchName="S", lights=["A"]}]
Just ["S"]