Hi,
it's my first post on this newsgroup so welcome everyone. :)
I'm still learning Python (v3.3), and today I had idea to design (my first)
recursive function, that generates board to 'Towers' Puzzle:
http://www.chiark.greenend.org.uk/~sgtatham/puzzles/js/towers.html
(so I could in future write algorithm to solve it ;-))
I'm pretty proud of myself - that it works, and that took me only 4 hours
to debug. ;-)
But on Project Euler site sometimes I'm also proud, that I solved some
problem in 30-line script, and then on forum there's one lined solution...
So maybe You might look at this script, and tell me if this can be more
pythonic. It's nothing urgent. I can wait - it works after all. ;-)
Idea is that function "generate()" 'finds' one number at a time (well,
besides first row), then checks if there are no repetitions in column
(because in row there cannot be by design - I pop out numbers from shuffled
list [1, 2, 3, ..., size] for every row.)
If no repetition - calls the same function to find next number, and so on.
If there is repetition at some point - recursion jumps back, and try
different number on previous position.
import random
def check(towers, x=None):
if x:
c = x % len(towers) # check only column with
column = [] # value added on pos. x
for i in range(len(towers)):
column.append(towers[i][c])
column = [x for x in column if x != 0]
# print(column) # debugging leftovers ;-)
return len(column) == len(set(column))
else:
for c in range(len(towers)): # 'x' not provided,
column = [] # so check all columns
for i in range(len(towers)):
column.append(towers[i][c])
column = [x for x in column if x != 0]
# print(column)
if len(column) != len(set(column)):
return False
return True
def generate(size=4, towers=None, row=None, x=0):
if not towers: # executed only once.
row = [a for a in range(1, size+1)] # Then I'll pass towers list
random.shuffle(row) # at every recursion
towers = []
# not so pretty way to generate
for i in range(size): # matrix filled with 0's
towers.append([]) # I tried: towers = [[0]*size]*size
for j in range(size): # but this doesn't work. ;-)
towers[i].append(0) # I don't know how to do this with
# list comprehension (one inside
row_ = row[:] # other?)
towers[0] = row_ # after adding first row, columns will be
row = [] # always unique, so I add entire row at once.
x = size - 1 # Then I will be adding only one num at time.
# 'x' is pretty much position of last added el.
if not row:
row = [a for a in range(1, size+1)]
random.shuffle(row)
if x + 1 < size**2:
repeat = True
attempt = 0
while repeat:
# print(towers, row, x)
x += 1
num = row.pop(0) # take num from right, and
towers[x // size][x % size] = num # if doesn't match - put
repeat = not check(towers, x) # back (append) on left -
# - to rotate
if repeat: # I'll repeat 'matching' next
row.append(num) # number as long as last
x -= 1 # changed column is unique
attempt += 1
# after some attempts I give
if attempt > len(row) - 1: # up and jump back from
return False # current recursion
else:
if not generate(size, towers, row, x):
repeat = True
row.append(num) # after some failed attempts
x -= 1 # on this 'level' I give up
attempt += 1 # again...
if attempt > len(row) - 1:
return False # ...and jump back one
# more time...
return towers
def main():
towers6by6 = generate(6)
# print(check(towers6by6))
print(towers6by6)
if __name__ == "__main__": main()
Footnote: English isn't my native language, so forgive me my bad grammar
and/or vocabulary. :-)
--
Best regrds, Wiktor Matuszewski
'py{}@wu{}em.pl'.format('wkm', 'ka') # spam trap
--
https://mail.python.org/mailman/listinfo/python-list
