Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #50008
| From | Helmut Jarausch <jarausch@igpm.rwth-aachen.de> |
|---|---|
| Newsgroups | comp.lang.python |
| Subject | Re: How to make this faster |
| Date | 2013-07-05 18:42 +0000 |
| Message-ID | <b3oidfFu5lhU4@mid.dfncis.de> (permalink) |
| References | <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de> |
On Fri, 05 Jul 2013 17:25:54 +0100, MRAB wrote:
> For comparison, here's my solution:
Your solution is very fast, indeed.
It takes 0.04 seconds (mean of 1000 runs) restoring "grid"
in between.
But that's a different algorithm which is IMHO more difficult to understand.
Many thanks,
Helmut
>
> from collections import Counter
>
> problem = '''
> _________
> _____3_85
> __1_2____
> ___5_7___
> __4___1__
> _9_______
> 5______73
> __2_1____
> ____4___9
> '''
>
> # Build the grid.
> digits = "123456789"
>
> grid = []
>
> for row in problem.splitlines():
> if not row:
> continue
>
> new_row = []
>
> for cell in row:
> if cell.isdigit():
> new_row.append({cell})
> else:
> new_row.append(set(digits))
>
> grid.append(new_row)
>
> # Solve the grid.
> changed = True
> while changed:
> changed = False
>
> # Look for cells that contain only one digit.
> for r in range(9):
> for c in range(9):
> if len(grid[r][c]) == 1:
> digit = list(grid[r][c])[0]
>
> # Remove from other cells in same row.
> for c2 in range(9):
> if c2 != c and digit in grid[r][c2]:
> grid[r][c2].remove(digit)
> changed = True
>
> # Remove from other cells in same column.
> for r2 in range(9):
> if r2 != r and digit in grid[r2][c]:
> grid[r2][c].remove(digit)
> changed = True
>
> # Remove from other cells in the same block of 9.
> start_row = r - r % 3
> start_column = c - c % 3
> for r2 in range(start_row, start_row + 3):
> for c2 in range(start_column, start_column + 3):
> if (r2, c2) != (r, c) and digit in grid[r2][c2]:
> grid[r2][c2].remove(digit)
> changed = True
>
> # Look for digits that occur in only one cell in a row.
> for r in range(9):
> counts = Counter()
> for c in range(9):
> counts += Counter(grid[r][c])
>
> unique = {digit for digit, times in counts.items() if times == 1}
>
> for c in range(9):
> if len(grid[r][c]) > 1 and len(grid[r][c] & unique) == 1:
> grid[r][c] &= unique
> changed = True
>
> # Look for digits that occur in only one cell in a column.
> for c in range(9):
> counts = Counter()
> for r in range(9):
> counts += Counter(grid[r][c])
>
> unique = {digit for digit, times in counts.items() if times == 1}
>
> for r in range(9):
> if len(grid[r][c]) > 1 and len(grid[r][c] & unique) == 1:
> grid[r][c] &= unique
> changed = True
>
> # Look for digits that occur in only one cell in a block of 9.
> for start_row in range(0, 9, 3):
> for start_column in range(0, 9, 3):
> counts = Counter()
> for r in range(start_row, start_row + 3):
> for c in range(start_column, start_column + 3):
> counts += Counter(grid[r][c])
>
> unique = {digit for digit, times in counts.items() if times == 1}
>
> for r in range(start_row, start_row + 3):
> for c in range(start_column, start_column + 3):
> if len(grid[r][c]) > 1 and len(grid[r][c] & unique) == 1:
> grid[r][c] &= unique
> changed = True
>
> # Display the solution.
> for row in grid:
> for cell in row:
> print("".join(sorted(cell)), end=" ")
>
> print()
Back to comp.lang.python | Previous | Next — Previous in thread | Find similar | Unroll thread
How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 08:22 +0000
Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 10:38 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:07 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 11:13 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 10:53 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 12:02 +0000
Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 13:44 +0100
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 14:41 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:28 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 15:45 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:48 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:26 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 14:54 +0000
Re: How to make this faster Fábio Santos <fabiosantosart@gmail.com> - 2013-07-05 16:18 +0100
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:24 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:17 +0000
Re: How to make this faster Oscar Benjamin <oscar.j.benjamin@gmail.com> - 2013-07-05 16:38 +0100
Re: How to make this faster MRAB <python@mrabarnett.plus.com> - 2013-07-05 17:25 +0100
Re: How to make this faster Joshua Landau <joshua.landau.ws@gmail.com> - 2013-07-06 02:45 +0100
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 15:47 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:52 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 16:07 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-05 16:50 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:39 +0000
Re: How to make this faster Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-07-06 03:05 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-06 07:25 +0000
Re: How to make this faster Helmut Jarausch <jarausch@igpm.rwth-aachen.de> - 2013-07-05 18:42 +0000
csiph-web