Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #50000
| Date | 2013-07-05 17:25 +0100 |
|---|---|
| From | MRAB <python@mrabarnett.plus.com> |
| Subject | Re: How to make this faster |
| References | <b3ne2rFojnkU1@mid.dfncis.de> <b3nmtfFojnkU3@mid.dfncis.de> <b3o6bkFtc39U4@mid.dfncis.de> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.4303.1373041542.3114.python-list@python.org> (permalink) |
On 05/07/2013 16:17, Helmut Jarausch wrote:
> On Fri, 05 Jul 2013 15:45:25 +0100, Oscar Benjamin wrote:
>
>> Presumably then you're now down to the innermost loop as a bottle-neck:
>>
>> Possibilities= 0
>> for d in range(1,10) :
>> if Row_Digits[r,d] or Col_Digits[c,d] or Sqr_Digits[Sq_No,d] : continue
>> Possibilities+= 1
>>
>> If you make it so that e.g. Row_Digits[r] is a set of indices rather
>> than a list of bools then you can do this with something like
>>
>> Possibilities = len(Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No])
>>
>> or perhaps
>>
>> Possibilities = len(set.union(Row_Digits[r], Col_Digits[c],
>> Sqr_Digits[Sq_No]))
>>
>> which I would expect to be a little faster than looping over range
>> since the loop is then performed under the hood by the builtin
>> set-type.
>>
>> It just takes practice.
>
> indeed
>
>> It's a little less obvious in Python than in
>> low-level languages where the bottlenecks will be and which operations
>> are faster/slower but optimisation always involves a certain amount of
>> trial and error anyway.
>>
>>
>> Oscar
>
> I've tried the following version
>
> def find_good_cell() :
> Best= None
> minPoss= 10
> for r,c in Grid :
> if Grid[(r,c)] > 0 : continue
> Sq_No= (r//3)*3+c//3
> Possibilities= 9-len(Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No])
> if ( Possibilities < minPoss ) :
> minPoss= Possibilities
> Best= (r,c)
>
> if minPoss == 0 : Best=(-1,-1)
> return Best
>
> All_digits= set((1,2,3,4,5,6,7,8,9))
>
> def Solve(R_Cells) :
> if R_Cells == 0 :
> print("\n\n++++++++++ S o l u t i o n ++++++++++\n")
> Print_Grid()
> return True
>
> r,c= find_good_cell()
> if r < 0 : return False
> Sq_No= (r//3)*3+c//3
>
> for d in All_digits - (Row_Digits[r] | Col_Digits[c] | Sqr_Digits[Sq_No]) :
> # put d into Grid
> Grid[(r,c)]= d
> Row_Digits[r].add(d)
> Col_Digits[c].add(d)
> Sqr_Digits[Sq_No].add(d)
>
> Success= Solve(R_Cells-1)
>
> # remove d again
> Grid[(r,c)]= 0
> Row_Digits[r].remove(d)
> Col_Digits[c].remove(d)
> Sqr_Digits[Sq_No].remove(d)
>
> if Success :
> Zuege.append((d,r,c))
> return True
>
> return False
>
> which turns out to be as fast as the previous "dictionary only version".
> Probably, set.remove is a bit slow
>
For comparison, here's my solution:
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 | Next 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