a problem to solve

[John Salerno]

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.

[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

[mensanator]

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.

[John Salerno]

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?

[John Salerno]

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?

[Michael Tobis]

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

[mensanator]

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.

[mensanator]

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[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.

[mensanator]

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

[mensanator]

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[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.

[Michael Tobis]

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

[mensanator]

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

[John Salerno]

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.

[John Salerno]

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. :)

[John Salerno]

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?

[mensanator]

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**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[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.

[mensanator]

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.

[mensanator]

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.

[John Salerno]

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. :)

[John Salerno]

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?

[mensanator]

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))

[John Salerno]

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! :)

[John Salerno]

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()

[mensanator]

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[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
# 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

[John Salerno]

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. :)

[Clemens Hepper]

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

[mensanator]

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

[Scott David Daniels]

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