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 814, 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.  
Share this Question
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 814, 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 nonzero 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  
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 814, 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 20bit 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.  
P: n/a
 me********@aol.com wrote: Then you'll want to represent the lights as a 20bit binary number.
Each bit position corresponds to 4 lamps
I'm not sure I understand that. If I use a 20bit number, wouldn't each
bit correspond to a single light on each switch? What do you mean that
each bit is 4 lamps?  
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 20bit 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?  
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.9029386530869287e05
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.9029386530869287e05 = 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  
P: n/a

John Salerno wrote: me********@aol.com wrote:
Then you'll want to represent the lights as a 20bit binary number.
Each bit position corresponds to 4 lamps
I'm not sure I understand that. If I use a 20bit 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 20bit 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 20bit 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.  
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 20bit 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 07.
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[0],
B1 by b[0], etc. to evaluate that set of switches.
Once you see that a[0],b[0],c[0],d[0] 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.  
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.9029386530869287e05
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.9029386530869287e05 = 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  
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 20bit 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 07.
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[0], B1 by b[0], etc. to evaluate that set of switches.
Once you see that a[0],b[0],c[0],d[0] 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.  
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.9e05 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  
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.9e05 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  
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 Myststyle 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.  
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. :)  
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[0],b[0],c[0],d[0] 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?  
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[0],b[0],c[0],d[0] 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[7] b[2] c[5] d[3])
is to use the boolean expression I gave you initially: y = ((c[5] & d[3]) & (a[7] ^ b[2]))  ((a[7] & b[2]) & (c[5] ^ d[3]))
y
1048575
Note the answer is 2**201, 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[0] b[0] c[0] d[0]
a[0] b[0] c[0] d[1]
a[0] b[0] c[0] d[2]
a[0] b[0] c[0] d[3]
a[0] b[0] c[0] d[4]
a[0] b[0] c[0] d[5]
a[0] b[0] c[0] d[6]
a[0] b[0] c[0] d[7]
a[0] b[0] c[1] d[0]
..
..
..
a[7] b[7] c[7] d[5]
a[7] b[7] c[7] d[6]
a[7] b[7] c[7] d[7]
you'll find that a[7] b[2] c[5] d[3] is the ONLY solution.  
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[7] b[2] c[5] d[3]
Remember, count from 0, switch 7 is the last switch.
We can manually verify print gmpy.digits(a[7],2)
11101101111011110101 print gmpy.digits(b[2],2)
11011110011101011111 print gmpy.digits(c[5],2)
10110111101110111110 print gmpy.digits(d[3],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[7] b[2] c[5] d[3] 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.  
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 Myststyle 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.  
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[7] b[2] c[5] d[3]) 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: 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[7] b[2] c[5] d[3]) 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?  
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[7] b[2] c[5] d[3]) 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))  
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[7] b[2] c[5] d[3]) 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! :)  
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()  
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 bitbanger
# 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,j1) 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,j1) 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[0]) # have to convert the characters to
i = int(q[1]) # ints so that they can be used as
j = int(q[2]) # indexes into the panel lists
k = int(q[3])
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
# 1bits
if r>15:
print '%2d %s%s' % (r,'0'*(20len(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'*(20len(z))
# the base 2 conversion stops at the most significant 1bit
# 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  
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. :)  
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  
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 oneway 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  
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   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 1931
 replies: 27
 date asked: Mar 22 '06
