449,220 Members | 1,506 Online Need help? Post your question and get tips & solutions from a community of 449,220 IT Pros & Developers. It's quick & easy.

# a problem to solve

 P: n/a 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. Mar 22 '06 #1
27 Replies

 P: n/a 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 Mar 22 '06 #2

 P: n/a 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. Mar 23 '06 #3

 P: n/a me********@aol.com wrote: Then you'll want to represent the lights as a 20-bit binary number. Each bit position corresponds to 4 lamps I'm not sure I understand that. If I use a 20-bit number, wouldn't each bit correspond to a single light on each switch? What do you mean that each bit is 4 lamps? Mar 24 '06 #4

 P: n/a John Salerno wrote: Anyway, any advice for how to proceed would be great! I hope I described it well enough. Ok, after reading the suggestions, I feel better about proceeding. But one question: how exactly do I come up with 32 different 20-bit integers for each switch? Do I need to figure out the bits for each one manually? And how is this written in Python? Using hex? Mar 24 '06 #5

 P: n/a First do a little estimation. We know we have to find four out of 16 switches, so the number of possibilities to search is only C(4,16) = 1820, so an exhaustive search will work. These will turn on 15 lights in each set of 20, of which the number of possibilities is C(15,20)**4 = 57779667567968256L The number of these that are successes is the number of ways to pick 3 out of 4 twenty times: 4**20 = 1099511627776L For each pick, your chance of success is then float(1099511627776L)/57779667567968256L = 1.9029386530869287e-05 You get 1820 distinct tries. Assuming no overlap (which slightly overestimates your chances if it's a false assumption), the odds that there is a solution are 1820 * 1.9029386530869287e-05 = 0.034633483486182101 or about 3.5%. Not great. There seem to be some symmetries I haven't used, which may conceivably help your cause. I just wonder if you have some basis for beleiving that there is a solution. mt Mar 24 '06 #6

 P: n/a John Salerno wrote: me********@aol.com wrote: Then you'll want to represent the lights as a 20-bit binary number. Each bit position corresponds to 4 lamps I'm not sure I understand that. If I use a 20-bit number, wouldn't each bit correspond to a single light on each switch? What do you mean that each bit is 4 lamps? You have 4 panels, each with 20 lamps (label them 19 to 0): panel A 00000000000000000000 panel B 00000000000000000000 panel C 00000000000000000000 panel D 00000000000000000000 ^ ^ | | lamp 19 lamp 0 There are 4 lamps labeled 19, 4 labeled 18, etc. The boolean equation I gave you is the solution to a single lamp position. If a 0 represents OFF and a 1 represents ON, then this is equivalent to 4 20-bit binary numbers and you can use bitwise operators to solve all 20 lamp positions simultaneously. For each bit position, the boolean equation returns a 1 in the repective bit if there are exactly 3 1's in that lamp position of the 4 panels. The first switch in each panel lights the lamps: A 11110101111111011100 B 11011101101101111101 C 11110011011110111101 D 01110111111011011011 You can, by hand, figure out which bit positions have exactly 3 1's vertically. A 11110101111111011100 B 11011101101101111101 C 11110011011110111101 D 01110111111011011011 ---------------------- Y 10100100110111000101 So, as you already know, setting switch 1 on each panel is not a solution, we need a 1 in each bit position. You can determine this from the decimal representation. A 20-bit binary number of all 1's would be 2**20 - 1, so if Y = 1048575, then Y is a solution. In my example, I used hex to enter the sample values just because it was easier: Group the 20 bits into five groups of 4, and convert each group to a hex character A 1111 0101 1111 1101 1100 f 5 f d c Repeating the example (correcting the typo in the first post) A1 = 0xf5fdc B1 = 0xddb7d C1 = 0xf37bd D1 = 0x77edb Y = ((C1 & D1) & (A1 ^ B1)) | ((A1 & B1) & (C1 ^ D1)) Y 675269 We can see this is not a solution. Converting Y to binary allows us to see which lamp positions have three lit and confirm that the boolean equation matches our hand calculation. print gmpy.digits(Y,2) 10100100110111000101 By the way, I have a program that solves the problem. You said you wanted to do it yourself, so if you need more help, I can walk you through how to solve it. Mar 24 '06 #7

 P: n/a John Salerno wrote: John Salerno wrote: Anyway, any advice for how to proceed would be great! I hope I described it well enough. Ok, after reading the suggestions, I feel better about proceeding. But one question: how exactly do I come up with 32 different 20-bit integers for each switch? Eight numbers for each switch, 32 total. Make a list for each panel and in each list, put in eight binary numbers using the position in the list to represent the switch number. So we'll want to label our switches 0-7. Do I need to figure out the bits for each one manually? Yes, you get them from your diagram showing which lamps are lit for each switch. And how is this written in Python? Using hex? That's one way to do it. I did it that way because I have the hex patterns memorized. I have already gone to the trouble of converting all your patterns to hex numbers, if you're interested. If you want to do it yourself, simply ignore this. a = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] b = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] c = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] d = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] Now since the panels are now lists, we use an index representing the switch to retrieve the lamps lit by that switch. Refering to my original boolean equation, replace A1 by a, B1 by b, etc. to evaluate that set of switches. Once you see that a,b,c,d is not a solution, try a different set of switches. Repeat until you find a set that works. There is, in fact a solution, but I won't reveal it unless you ask. If you need help in figuring out how to walk through all 4096 possible switch sets, just ask. Mar 24 '06 #8

 P: n/a Michael Tobis wrote: First do a little estimation. We know we have to find four out of 16 switches, 4 panels, eight switches each, 32 total. so the number of possibilities to search is only C(4,16) = 1820, so an exhaustive search will work. Yes, but for the wrong reason. It's not combinations, the switch selection A = 1 B = 2 C = 3 D = 4 is not the same as A = 4 B = 3 C = 2 D = 1 You want permutations with replacement, so there are 8**4 = 4096 possibilities, which is still tractable. These will turn on 15 lights in each set of 20, of which the number of possibilities is C(15,20)**4 = 57779667567968256L No, there are only 8 possible patterns on each panel. Not every possible 15 lamp pattern is realized. The number of these that are successes is the number of ways to pick 3 out of 4 twenty times: 4**20 = 1099511627776L For each pick, your chance of success is then float(1099511627776L)/57779667567968256L = 1.9029386530869287e-05 Chance doesn't enter into it. Unless you ask what is the chance that a randomly selected switch pattern is a solution? But no one is asking that. You get 1820 distinct tries. Assuming no overlap (which slightly overestimates your chances if it's a false assumption), the odds that there is a solution are 1820 * 1.9029386530869287e-05 = 0.034633483486182101 or about 3.5%. Not great. The odds are 100% if there is at least one solution. There seem to be some symmetries I haven't used, which may conceivably help your cause. I just wonder if you have some basis for beleiving that there is a solution. There is. I solved it using the technique I outlined in my previous posts. mt Mar 24 '06 #9

 P: n/a me********@aol.com wrote: John Salerno wrote: John Salerno wrote: Anyway, any advice for how to proceed would be great! I hope I described it well enough. Ok, after reading the suggestions, I feel better about proceeding. But one question: how exactly do I come up with 32 different 20-bit integers for each switch? Eight numbers for each switch, 32 total. Should be: Eight numbers for each panel, 32 total. Make a list for each panel and in each list, put in eight binary numbers using the position in the list to represent the switch number. So we'll want to label our switches 0-7. Do I need to figure out the bits for each one manually? Yes, you get them from your diagram showing which lamps are lit for each switch. And how is this written in Python? Using hex? That's one way to do it. I did it that way because I have the hex patterns memorized. I have already gone to the trouble of converting all your patterns to hex numbers, if you're interested. If you want to do it yourself, simply ignore this. a = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] b = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] c = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] d = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] Now since the panels are now lists, we use an index representing the switch to retrieve the lamps lit by that switch. Refering to my original boolean equation, replace A1 by a, B1 by b, etc. to evaluate that set of switches. Once you see that a,b,c,d is not a solution, try a different set of switches. Repeat until you find a set that works. There is, in fact a solution, but I won't reveal it unless you ask. If you need help in figuring out how to walk through all 4096 possible switch sets, just ask. Mar 24 '06 #10

 P: n/a Yeah, I misread the question, but the gist of my query remains. The odds are 100% if there is at least one solution. Let's not get too philosophical. My question was whether there was an a priori reason for believing that there is a solution. You want permutations with replacement, so there are 8**4 = 4096 Agreed. My mistake. These will turn on 15 lights in each set of 20, of which the number of possibilities is C(15,20)**4 = 57779667567968256L No, there are only 8 possible patterns on each panel. Not every possible 15 lamp pattern is realized Right, but that is exactly my point. This is the number of possible selections of 15 out of 20 made four times. Any attempt will be a member of that space. Then the probability of hitting a solution at random is the ratio of solutions to that space. So I think my chance of success on a sinlge selection, assuming random design of the switch banks, is correct: 1.9e-05 My error gave me the wrong multiplier. It's 4096 rather than 1820. So now I'm goinq with a 7.79% chance of randomly setting up the problem to yield a solution. Still seems somwhat unlikely that there would be a solution unless the problem were set up in advance. (homework? a puzzle book?), I am just wondering where the puzzle came from. Was there more than one solution? mt Mar 24 '06 #11

 P: n/a Michael Tobis wrote: Yeah, I misread the question, but the gist of my query remains. The odds are 100% if there is at least one solution. Let's not get too philosophical. My question was whether there was an a priori reason for believing that there is a solution. You want permutations with replacement, so there are 8**4 = 4096 Agreed. My mistake. These will turn on 15 lights in each set of 20, of which the number of possibilities is C(15,20)**4 = 57779667567968256L No, there are only 8 possible patterns on each panel. Not every possible 15 lamp pattern is realized Right, but that is exactly my point. This is the number of possible selections of 15 out of 20 made four times. Any attempt will be a member of that space. Then the probability of hitting a solution at random is the ratio of solutions to that space. So I think my chance of success on a sinlge selection, assuming random design of the switch banks, is correct: 1.9e-05 My error gave me the wrong multiplier. It's 4096 rather than 1820. So now I'm goinq with a 7.79% chance of randomly setting up the problem to yield a solution. Ok, random settings didn't make any sense since the problem was already set up. Still seems somwhat unlikely that there would be a solution unless the problem were set up in advance. It would be easy to set up an answer. Then work backwards to create 7 bad settings for each switch, although I'm not sure how you would ensure not accidently creating another solution. Would be simple enough to verify, though. With only 4096 permutations, it only takes seconds to find the solution(s). (homework? a puzzle book?), I am just wondering where the puzzle came from. The OP mentioned it came from a puzzle game That made me think there was likely at least one solution. Was there more than one solution? No, there is exactly one solution where Y has 20 1's. Second best has only 16 1's, of which there are 8 solutions. For example: 16 11011011111111110011 3 4 5 5 where the numbers are popcount, Y (in binary) and the four switch settings. mt Mar 25 '06 #12

 P: n/a me********@aol.com wrote: (homework? a puzzle book?), I am just wondering where the puzzle came from. The OP mentioned it came from a puzzle game That made me think there was likely at least one solution. Right, a computer puzzle game (a Myst-style game called Realms of Illusion), and I know there's at least one answer because it's been months since I finished the game. :) I also think, but can't say for sure, that there is just one solution. Mar 25 '06 #13

 P: n/a me********@aol.com wrote: You have 4 panels, each with 20 lamps (label them 19 to 0): panel A 00000000000000000000 panel B 00000000000000000000 panel C 00000000000000000000 panel D 00000000000000000000 I'm sorry for being so dense, but I don't understand this. There are four panels, yes. Each panel has eight switches, and each switch has 20 lights. What do you mean when you say that each panel has 20 lamps? By the way, I have a program that solves the problem. You said you wanted to do it yourself, so if you need more help, I can walk you through how to solve it. I already know the solution (I had to cheat to get past this part of the game, it was just too frustrating). I was always more interested in the actual process of figuring it out via writing a program. You can tell me your solution if you want and I can check it. This will at least confirm that you understand the problem fully and that I'm just being moronic when it comes to understanding your explanations. :) Mar 25 '06 #14

 P: n/a me********@aol.com wrote: a = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] b = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] c = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] d = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] Once you see that a,b,c,d is not a solution, try a different set of switches. Repeat until you find a set that works. There is, in fact a solution, but I won't reveal it unless you ask. Using your hex list, I combined the four correct switches with the & operator, and the result was 0. Shouldn't it be 1 for the correct answer? Mar 25 '06 #15

 P: n/a John Salerno wrote: me********@aol.com wrote: a = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] b = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] c = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] d = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] Once you see that a,b,c,d is not a solution, try a different set of switches. Repeat until you find a set that works. There is, in fact a solution, but I won't reveal it unless you ask. Using your hex list, I combined the four correct switches with the & operator, and the result was 0. Shouldn't it be 1 for the correct answer? No. First of all, combining them with the & operator would be the asnswer to having all four lamps lit in the same position. But you want exactly 3 (in any combination). The correct way to combine the switches (using my answer of a b c d) is to use the boolean expression I gave you initially: y = ((c & d) & (a ^ b)) | ((a & b) & (c ^ d)) y 1048575 Note the answer is 2**20-1, not 1, the correct answer will have a 1 in EACH of the 20 bit positions (when y is printed in binary). Is 1048575 the right answer? import gmpy print gmpy.digits(y,2) 11111111111111111111 Yes, it is the right answer. If you calculate y for EVERY possible permutation of switches a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d a b c d .. .. .. a b c d a b c d a b c d you'll find that a b c d is the ONLY solution. Mar 25 '06 #16

 P: n/a John Salerno wrote: me********@aol.com wrote: You have 4 panels, each with 20 lamps (label them 19 to 0): panel A 00000000000000000000 panel B 00000000000000000000 panel C 00000000000000000000 panel D 00000000000000000000 I'm sorry for being so dense, but I don't understand this. There are four panels, yes. Each panel has eight switches, and each switch has 20 lights. What do you mean when you say that each panel has 20 lamps? Oh, I see where the confusion is. EACH switch has 20 lamps. But, since ONLY 1 switch can be on, each panel shows exactly one pattern of lamps, correct? So we only consider panel A to have 20 lamps, the 20 that are selected by the switch. For the purposes of solving the puzzle, we simply want to know what the pattern is when switch 0 is selected, what the pattern is when switch 1 is selected, etc. for each of the four panels. By the way, I have a program that solves the problem. You said you wanted to do it yourself, so if you need more help, I can walk you through how to solve it. I already know the solution (I had to cheat to get past this part of the game, it was just too frustrating). I was always more interested in the actual process of figuring it out via writing a program. You can tell me your solution if you want and I can check it. I also posted it in the other reply, but here it is again: a b c d Remember, count from 0, switch 7 is the last switch. We can manually verify print gmpy.digits(a,2) 11101101111011110101 print gmpy.digits(b,2) 11011110011101011111 print gmpy.digits(c,2) 10110111101110111110 print gmpy.digits(d,2) 1111011110111101011 11101101111011110101 11011110011101011111 10110111101110111110 01111011110111101011 Note that in each column, there is exactly one 0, which means there is exaclty 3 1's in that column, therefore, a b c d is a solution. This will at least confirm that you understand the problem fully and that I'm just being moronic when it comes to understanding your explanations. :) You're not moronic. I have 30 years experience with boolean algebra and digital logic. I understand what's trivial to me is not trivial to everyone. But I don't know how much you know and how much you want to work out yourself. You certainly CAN solve the problem by the tedious method you initially described. But since you specifically asked about use bitwise operators, I used that in my solution. I didn't want to spoil it for you, but say the word and I'll post my program code. Mar 25 '06 #17

 P: n/a John Salerno wrote: me********@aol.com wrote: (homework? a puzzle book?), I am just wondering where the puzzle came from. The OP mentioned it came from a puzzle game That made me think there was likely at least one solution. Right, a computer puzzle game (a Myst-style game called Realms of Illusion), and I know there's at least one answer because it's been months since I finished the game. :) I also think, but can't say for sure, that there is just one solution. _I_ can say for sure, there is just one solution. Mar 25 '06 #18

 P: n/a me********@aol.com wrote: No. First of all, combining them with the & operator would be the asnswer to having all four lamps lit in the same position. But you want exactly 3 (in any combination). The correct way to combine the switches (using my answer of a b c d) is to use the boolean expression I gave you initially: Ah, that makes sense. I think I have a handle on it now. Of course, you did the grunt work of making the hex list, which might not have been so fun, but now I can work on using it to get the solution. Once I do, I'd love to compare my answer to yours, because something tells me yours will be much more elegant. :) Mar 25 '06 #19

 P: n/a John Salerno wrote: me********@aol.com wrote: No. First of all, combining them with the & operator would be the asnswer to having all four lamps lit in the same position. But you want exactly 3 (in any combination). The correct way to combine the switches (using my answer of a b c d) is to use the boolean expression I gave you initially: Ah, that makes sense. I think I have a handle on it now. Of course, you did the grunt work of making the hex list, which might not have been so fun, but now I can work on using it to get the solution. Once I do, I'd love to compare my answer to yours, because something tells me yours will be much more elegant. :) p.s. is there an xor operator in python? Mar 25 '06 #20

 P: n/a John Salerno wrote: John Salerno wrote: me********@aol.com wrote: No. First of all, combining them with the & operator would be the asnswer to having all four lamps lit in the same position. But you want exactly 3 (in any combination). The correct way to combine the switches (using my answer of a b c d) is to use the boolean expression I gave you initially: Ah, that makes sense. I think I have a handle on it now. Of course, you did the grunt work of making the hex list, which might not have been so fun, but now I can work on using it to get the solution. Once I do, I'd love to compare my answer to yours, because something tells me yours will be much more elegant. :) p.s. is there an xor operator in python? Yep. The XOR operator is ^. That's why you have to use ** for exponentiation. In addition to &=AND, there is also |=OR. I actually gave two boolean expressions. First, using the standard notation, where concatenation implies AND, + is OR and x is XOR (actually, the standard notation for XOR is a + inside a circle, but my keyboard doesn't have one of those). Y = CD(A x B) + AB(C x D) Second, using the Python operators Y = ((C & D) & (A ^ B)) | ((A & B) & (C ^ D)) Mar 25 '06 #21

 P: n/a me********@aol.com wrote: John Salerno wrote: John Salerno wrote: me********@aol.com wrote: No. First of all, combining them with the & operator would be the asnswer to having all four lamps lit in the same position. But you want exactly 3 (in any combination). The correct way to combine the switches (using my answer of a b c d) is to use the boolean expression I gave you initially: Ah, that makes sense. I think I have a handle on it now. Of course, you did the grunt work of making the hex list, which might not have been so fun, but now I can work on using it to get the solution. Once I do, I'd love to compare my answer to yours, because something tells me yours will be much more elegant. :) p.s. is there an xor operator in python? Yep. The XOR operator is ^. That's why you have to use ** for exponentiation. In addition to &=AND, there is also |=OR. I actually gave two boolean expressions. First, using the standard notation, where concatenation implies AND, + is OR and x is XOR (actually, the standard notation for XOR is a + inside a circle, but my keyboard doesn't have one of those). Y = CD(A x B) + AB(C x D) Second, using the Python operators Y = ((C & D) & (A ^ B)) | ((A & B) & (C ^ D)) Thanks! Back to work for me! :) Mar 25 '06 #22

 P: n/a me********@aol.com wrote: If you need help in figuring out how to walk through all 4096 possible switch sets, just ask. Ok, thanks to your list, I figured out a program that works! It's probably not the best, and it doesn't really display which switches are correct in any apparent way (you have to look for them in the list), but it works! Here's the code. I'd love to see your implementation too. from gmpy import digits panelOne = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] panelTwo = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] panelThree = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] panelFour = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] for a in panelOne: for b in panelTwo: for c in panelThree: for d in panelFour: if (a & b & (c ^ d)) | (c & d & (a ^ b)) == 1048575: print 'Solution is:', digits(a, 16), digits(b, 16), digits(c, 16), digits(d, 16) raw_input() Mar 25 '06 #23

 P: n/a John Salerno wrote: me********@aol.com wrote: If you need help in figuring out how to walk through all 4096 possible switch sets, just ask. Ok, thanks to your list, I figured out a program that works! It's probably not the best, and it doesn't really display which switches are correct in any apparent way (you have to look for them in the list), but it works! Here's the code. I'd love to see your implementation too. from gmpy import digits panelOne = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] panelTwo = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] panelThree = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] panelFour = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] for a in panelOne: for b in panelTwo: for c in panelThree: for d in panelFour: if (a & b & (c ^ d)) | (c & d & (a ^ b)) == 1048575: print 'Solution is:', digits(a, 16), digits(b, 16), digits(c, 16), digits(d, 16) raw_input() Well, I don't get the prize for most elegant. But that's partly because I included the ooloop6 function. That's real handy to have in your puzzle solving toolbox. It can generate all the subsets of the cartesian product of a string of characters: Permutations with Replacement Combinations with Replacement Permutations without Replacement Combinations without Replacement It will dynamically create as many nested for loops as you need (up to the Python limit of 20, but keep in mind that there are 19928148895209409152340197376 possible 20 letter words). Of course, we only need Permutations with Replacement for THIS problem, which can be done more elegantly the way you did it. import gmpy # and gmpy can do much more than base conversion # lots of functions of interest to the bit-banger # example below def ooloop6(a, n, perm=True, repl=True): if (not repl) and (n>len(a)): return r0 = range(n) r1 = r0[1:] if perm and repl: # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) e = ''.join(["p = [''.join((",v,")) ",f,"]"]) exec e return p if (not perm) and repl: # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) i = ' and '.join(['(c%s>=c%s)' % (j,j-1) for j in r1]) e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"]) exec e return p if perm and (not repl): # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) i = ' and '.join([' and '.join(['(c%s!=c%s)' % (j,k) for k in range(j)]) for j in r1]) e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"]) exec e return p if (not perm) and (not repl): # ok v = ','.join(['c%s' % i for i in r0]) f = ' '.join(['for c%s in a' % i for i in r0]) i = ' and '.join(['(c%s>c%s)' % (j,j-1) for j in r1]) e = ''.join(["p = [''.join((",v,")) ",f," if ",i,"]"]) exec e return p a = [0xf5fdc,0xf6edb,0xbddb7,0x6fddd,0xeb7ed,0xb977f,0x bfed3,0xedef5] b = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0x b77dd,0x7ef5d] c = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0x ecfbd,0xb75df] d = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0x fb35f,0xbb7dd] p = ooloop6('01234567',4) # p is a list of all 4096 possible switch patterns # ['0000','0001','0002',...'7775','7776','7777'] for q in p: h = int(q) # have to convert the characters to i = int(q) # ints so that they can be used as j = int(q) # indexes into the panel lists k = int(q) y = ((c[j] & d[k]) & (a[h] ^ b[i])) | ((a[h] & b[i]) & (c[j] ^ d[k])) z = gmpy.digits(y,2) # y converted to base 2 r = gmpy.popcount(y) # a real neat gmpy bit function! # popcount is the number of 1 bits # in the number # in case there is no solution, I want to see how close # I come, so I print all solutions that have over 15 # 1-bits if r>15: print '%2d %s%s' % (r,'0'*(20-len(z)),z),h,i,j,k # it's not wrong to iterate through the list directly, # but by using an index instead of saying "for a in Panel1", # I can then print the index when I find a solution. # so I can simply say the switches are 7 2 5 3 # note the expression '0'*(20-len(z)) # the base 2 conversion stops at the most significant 1-bit # this pads it out to 20 characters if necessary ## program output ## ## 16 00110111111111111110 2 3 1 7 ## 16 11011011111111110011 3 4 5 5 ## 16 11111101110111010111 5 5 6 0 ## 16 11011111101110111011 6 3 0 4 ## 16 01111111111111100011 7 1 5 2 ## 20 11111111111111111111 7 2 5 3 <--- solution ## 16 11111001111110111011 7 2 5 4 ## 16 11111100111111011011 7 4 5 3 ## 16 01011111011111111101 7 7 5 3 Mar 25 '06 #24

 P: n/a me********@aol.com wrote: Well, I don't get the prize for most elegant. But that's partly because I included the ooloop6 function. :: snip a bunch of scary code :: :) Wow, that's impressive. My solution looks a whole lot simpler than yours, but I certainly could not have done it without all your great help (the hex list, the formula, even the basic explanation of what needs to happen, i.e. Y needs to be 11111111111111111111). Thanks for taking the time to work with me on this. I don't know if I would have ever finished it without your help -- and this thing has been haunting me for months. :) Mar 25 '06 #25

 P: n/a Hi, me********@aol.com wrote: That's one way to do it. I did it that way because I have the hex patterns memorized. You should be able to generate your numbers like this: number = int('0010010001000000100', 2) mfg - eth Mar 27 '06 #26

 P: n/a Clemens Hepper wrote: Hi, me********@aol.com wrote: That's one way to do it. I did it that way because I have the hex patterns memorized. You should be able to generate your numbers like this: number = int('0010010001000000100', 2) Well, that would be another way, wouldn't it? Thanks for the tip, but you're a bit late (pun intended), we've both already solved the problem. And since base conversion is a one-way street in Python, the fact that you can do that doesn't eliminate the need for gmpy (or something equivalent) if you want to go the other way, decimal to binary. And furthermore, having Python's bitwise operators is nice, but it's not nice enough. I need the bitwise functionality gmpy provides that's not available in Python: scan for position of least significant 1 or 0, count of 1 bits, Hamming distance, etc. So, rather than point out that one can do number = int('0010010001000000100', 2) I would rather advise that the person obtain gmpy and use its conversion number = gmpy.mpz('0010010001000000100', 2) They'll thank me eventually. mfg - eth Mar 27 '06 #27

 P: n/a me********@aol.com wrote: And furthermore, having Python's bitwise operators is nice, but it's not nice enough. I need the bitwise functionality gmpy provides that's not available in Python: scan for position of least significant 1 or 0, Cute tricks (artifact of two's complement notation): v & -v == isolated least significant bit of v math.log(v & -v, 2) == bit number of least significant bit. --Scott David Daniels sc***********@acm.org Mar 27 '06 #28

### This discussion thread is closed

Replies have been disabled for this discussion. 