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. -- http://mail.python.org/mailman/listinfo/python-list
