[pypy-issue] [issue843] PyPy slower than CPython with puzzle problem

[Alex Krusz]

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."