Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #63095

Re: [newbie] Recursive algorithm - review

Show key headers only | View raw

On 1/3/2014 7:16 PM, Wiktor wrote:
> 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 (filled out) 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

[0]*size] is fine for one row

towers = [[0]*size] for i in range(size)]

should do what you want for a 2-d array instead of the above.

I cannot look at the rest right now.

-- 
Terry Jan Reedy

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 01:16 +0100
  Re: [newbie] Recursive algorithm - review Terry Reedy <tjreedy@udel.edu> - 2014-01-03 20:47 -0500
    Re: [newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 12:23 +0100
  Re: [newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 20:07 +0100
    Re: [newbie] Recursive algorithm - review Wiktor <look@signature.invalid> - 2014-01-04 20:36 +0100
    Re: [newbie] Recursive algorithm - review Chris Angelico <rosuav@gmail.com> - 2014-01-05 10:11 +1100

csiph-web