a problem to solve

mensanator at aol.com mensanator at aol.com
Sat Mar 25 09:21:59 CET 2006


John Salerno wrote:
> mensanator at 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,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[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




More information about the Python-list mailing list