a problem to solve

M

mensanator

John said:
John said:
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))
 
J

John Salerno

John said:
John said:
(e-mail address removed) 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! :)
 
J

John Salerno

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,0xbfed3,0xedef5]
panelTwo = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0xb77dd,0x7ef5d]
panelThree =
[0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0xecfbd,0xb75df]
panelFour =
[0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0xfb35f,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()
 
M

mensanator

John said:
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,0xbfed3,0xedef5]
panelTwo = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0xb77dd,0x7ef5d]
panelThree =
[0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0xecfbd,0xb75df]
panelFour =
[0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0xfb35f,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,0xbfed3,0xedef5]
b = [0xddb7d,0xfaddb,0xde75f,0xeef7a,0xdd77b,0xdfbce,0xb77dd,0x7ef5d]
c = [0xf37bd,0xdfaee,0xddd6f,0xddfb6,0xb9efb,0xb7bbe,0xecfbd,0xb75df]
d = [0x77edb,0xbb7ee,0xdf773,0x7bdeb,0x7ddaf,0xdeeeb,0xfb35f,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)) | ((a[h] & b) & (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
 
J

John Salerno

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

Clemens Hepper

Hi,

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
 
M

mensanator

Clemens said:
Hi,



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

Scott David Daniels

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
(e-mail address removed)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,951
Messages
2,570,113
Members
46,698
Latest member
alexxx

Latest Threads

Top