a problem to solve

[Claudio Grondi]

John Salerno wrote:
> Ok, here's a problem I've sort of assigned to myself for fun, but it's 
> turning out to be quite a pain to wrap my mind around. It's from a 
> puzzle game. It will help if you look at this image:
> 
> http://www.johnjsal.devisland.net/switches.jpg
> 
> Here's the situation: Each of the four rows in the diagram is considered 
> a single 'panel'. Each panel has eight 'switches', which are composed of 
> two columns each, and these columns have a total of 20 lights (10 in one 
> column, 10 in the other). The picture hopefully makes this description 
> clear.
> 
> The shaded boxes denote which lights turn on when you select that 
> particular switch. So, the very first switch in the first row, if turned 
> on, would turn on the first four lights, not the fifth, turn on the 
> sixth, not the seventh, and turn on 8-14, etc. up to the 20th light.
> 
> You can only turn on one switch per panel, so eventually you will have 
> four switches lit.
> 
> What you are shooting for is to find a combination of four switches so 
> that exactly three lights in the same location are lit, no more or less. 
> So turning on the first switch in each row would not work, because that 
> would mean that the second light in each switch would be lit, and you 
> can't have all four lit, just three.
> 
> So anyway, the reason I describe all this isn't so you can solve it for 
> me, because I really want to figure it out. I just was hoping you can 
> give me some tips as to how to implement the algorithm. Maybe Python has 
> some functions that I can use to make it easier than it seems.
> 
> My plan right now is to do a comparison of panel 1, switch 1, light 1 
> with panel 2, switch 1, light 1, then panel 3, switch 1, light 1, etc., 
> which sounds scary. I didn't know if Python had a way to compare the 
> whole switch in one step, perhaps.
> 
> Also, I was wondering how I might implement the switches as data 
> structures. Right now I have them as a list of 32 strings, but I thought 
> maybe some type of bitwise comparisons could help.
> 
> Anyway, any advice for how to proceed would be great! I hope I described 
> it well enough.

1. implement the switches as a list of integers composed out of bits for 
each light (1 for light turned on, 0 for off).
2. you can find if four lights are turned on by doing bit comparison of 
four integers (the & operator). If you get as result a non-zero value 
you know, that there are four lights in same location switched on
3. run a loop over the first eight switches and in this loop a loop over 
the second row, etc., so that you get all possible arrangement tested 
(four nested loops)
4. if you find a case the four switches gives a zero value, test if you 
have exactly three ligths on

You need to know:
   what is a list of integers
   how to do bitwise and with integers (the & operator)
   how to loop over list elements using their index
     ( e.g with "for listIndex in range(0,8):")
   how to set single bits of an integer
     ( e.g. intVal | 0x01, intVal | 0x02, intVal | 0x04, etc. )

Hope this helps

Claudio