[pypy-issue] [issue843] PyPy slower than CPython with puzzle problem
Alex Krusz
tracker at bugs.pypy.org
Wed Aug 24 08:30:47 CEST 2011
New submission from Alex Krusz <harfatum at gmail.com>:
Input/Output:
D:\Python>python athena_16.py 48 10
[2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] set([3318]) [[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2]
]
806844323190414
Total time was 6.473 seconds.
D:\Python>pypy athena_16.py 48 10
[2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] set([3318]) [[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2]
]
806844323190414
Total time was 10.525 seconds.
============================
This code was written to satisfy the following problem:
Your niece was given a set of blocks for her birthday, and she has decided to
build a panel using
3âÃ1â and 4.5âÃ1" blocks. For structural integrity, the spaces between the
blocks must not line up
in adjacent rows. For example, the 13.5âÃ3â panel below is unacceptable, because
some of the
spaces between the blocks in the first two rows line up (as indicated by the
dotted line).
There are 2 ways in which to build a 7.5âÃ1â panel, 2 ways to build a 7.5âÃ2â
panel, 4 ways to
build a 12âÃ3â panel, and 7958 ways to build a 27âÃ5â panel. How many different
ways are there
for your niece to build a 48âÃ10â panel? The answer will fit in a 64-bit
integer. Write a program to
calculate the answer.
The program should be non-interactive and run as a single-line command which
takes two
command-line arguments, width and height, in that order. Given any width between
3 and 48 that
is a multiple of 0.5, inclusive, and any height that is an integer between 1 and
10, inclusive, your
program should calculate the number of valid ways there are to build a wall of
those dimensions.
Your programâs output should simply be the solution as a number, with no
line-breaks or white
spaces.
----------
files: athena_16.py
messages: 3005
nosy: Harfatum, pypy-issue
priority: bug
status: unread
title: PyPy slower than CPython with puzzle problem
________________________________________
PyPy bug tracker <tracker at bugs.pypy.org>
<https://bugs.pypy.org/issue843>
________________________________________
-------------- next part --------------
#Assuming you cannot lay the blocks upright! That would be another can of worms, but it'd be doable.
import time
from sys import argv
from itertools import combinations
t1 = time.clock()
def all_single_rows(width):
#returns a list of all the possible block patterns for n total blocks with k of length 3
result = []
n = width / 2
#cutting off decimal if present
width_parity = width % 2
for i in range(n/3 + 1):
for bits in combinations(range(n-i), 2*i + width_parity):
s = [2] * (n-i)
for bit in bits:
s[bit] = 3
result.append(s)
return result
def running_total(list):
total = 0
total_list = set([])
for item_num in range(len(list)-1): #-1 because the last items in the running totals will always be identical
total += list[item_num]
total_list.add(total)
return total_list
def find_compatibility(single_rows):
length = len(single_rows)
compatibility = [set([]) for x in range(length)]
running_totals = [set([]) for x in range(length)]
for i in range(length):
running_totals[i] = running_total(single_rows[i])
for i in range(length):
for j in range(i+1, length): #listing all compatibility sets
#compare the ith row with the remaining rows to check if creases don't line up (i.e. compatible rows)
if not running_totals[i] & running_totals[j]:
compatibility[i].add(j)
compatibility[j].add(i)
return compatibility
def find_total_walls(compatibility, rows_left):
length = len(compatibility)
previous_row = [1 for x in range(length)]
for row in range(rows_left - 1):
next_row_possibilities = [0 for x in range(length)]
for compat_index in range(length):
for x in compatibility[compat_index]:
next_row_possibilities[x] += previous_row[compat_index]
previous_row = next_row_possibilities
return sum(next_row_possibilities)
raw_width, height = float(argv[1]), int(argv[2])
width = int(raw_width*2)/3
#convert to ints, which should be faster. blocks of width 3 and 4.5 are at a 2:3 ratio
single_rows = all_single_rows(width)
compatibility = find_compatibility(single_rows)
total_walls = find_total_walls(compatibility, height)
print single_rows[-1], compatibility[-1], [single_rows[x] for x in compatibility[-1]]
print total_walls
t2 = time.clock()
print "Total time was", round(t2-t1, 3), "seconds."
More information about the pypy-issue
mailing list