# [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() [[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() [[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

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
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
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 =  * (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]

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]:

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), int(argv)
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."
```