Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: [newbie] Recursive algorithm - review
Date: Fri, 03 Jan 2014 20:47:16 -0500
References: <m2p28zow0k72.17kajsf7eon4w.dlg@40tude.net>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.2.0
In-Reply-To: <m2p28zow0k72.17kajsf7eon4w.dlg@40tude.net>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.4874.1388800051.18130.python-list@python.org>
Lines: 79
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:63095

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