a problem to solve

[mensanator at aol.com]

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.

Then you'll want to represent the lights as a 20-bit binary number.

Each bit position corresponds to 4 lamps, so there are 16 possible
ways those 4 lamps could be lit. Construct a truth table and see which
of the outcomes have exactly 3 lit.

A	B	C	D	Y
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	0

The boolean equation (where  ~ means NOT,  + means OR,  x means XOR)
for Y is thus

Y = ~ABCD + A~BCD + AB~CD + ABC~D

which can be reduced to

Y = CD(AxB) + AB(CxD)

You'll need to do that for each bit position.

Now for each combination of four switches, look for one that
gives you 11111111111111111111 when you calculate the
20 Y values.

For eaxample, the first switch in each panel (using hex)
would be:

>>> A1 = 0xf5fdc
>>> B1 = 0xddb7d
>>> C1 = 0xf33bd
>>> D1 = 0x77edb

>>> Y = ((C1 & D1) & (A1 ^ B1)) | ((A1 & B1) & (C1 ^ D1))
>>> Y
674245

But which positions have 3 lights lit?

Printing Y in base 2 will tell us:

>>> import gmpy
>>> print gmpy.digits(Y,2)
10100100100111000101

Now you'll want A,B,C,D to be lists and adjust the formula for Y
accordingly. Then simply try every combination of ABCD.


>
> Anyway, any advice for how to proceed would be great! I hope I described
> it well enough.