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

[Alex Krusz]

Alex Krusz <harfatum at gmail.com> added the comment:

Not sure if this merits a separate submission, but I tried re-doing the
generate_compatibility function without using a set & or disjoint operation at
all, but rather building up each row from scratch. This too results in slower
performance with PyPy (Windows 1.6 beta) than with CPython 2.7.

________________________________________
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, product, chain

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 xrange(n/3 + 1):
        for bits in combinations(xrange(n-i), 2*i + width_parity):
            s = [2] * (n-i)
            for bit in bits:
                s[bit] = 3
            result.append(s)
    return result

def flatten(listOfLists):
    #"Flatten one level of nesting" thanks to http://docs.python.org/library/itertools.html
    return chain.from_iterable(listOfLists)
    
def running_total(list):
    total = 0
    total_list = []
    for item_num in xrange(len(list)): #could do -1 because the last items in the running totals will always be identical
        total += list[item_num]
        total_list.append(total)
    total_list.append(0) #hacky; to make the "j+2" position checking work when generating the fixed_sum_begins
    return total_list
   
def permutations(length):
    # we know the blocks of length length have only one two... so we can shortcut this.
    # we can also pseudo-overload this function to return blocks of 2s by using negatives
    if length > 0:
        return [[[3]*i + [2] + [3]*(length-i-1) for i in xrange(length)]]
    elif length < 0:
        return [[[2]]]*-length
    else:
        return [[[3]]]
   
def generate_compatibility(single_rows, width):
    length = len(single_rows)
    compatibility = [set([]) for x in xrange(length)]
    running_totals = [[] for x in xrange(length)]
    
    running_totals = [running_total(single_rows[i]) for i in xrange(length)]
    #tally the running totals for each row
    
    fixed_sum_begin = [[ 5 - single_rows[i][0] ] for i in xrange(length)]
    fixed_part_begin = [[ 5 - single_rows[i][0] ] for i in xrange(length)]
    
    fixed_sum_end = [[5 - single_rows[i][-1]] for i in xrange(length)]
    fixed_part_end = [[5 - single_rows[i][-1]] for i in xrange(length)]
    
    variable_part = dict()
    compat_blocks = [[] for i in xrange(length)]
    
    for i in xrange(length): # for the running total list for each row
        if single_rows[i][0] == 2: #since all compatibility pairs are symmetric,
            continue                    #we can skip the ones that start with 2
        
        j = 0
        
        while ( ( single_rows[i][j+1] != 3 ) or ( not fixed_sum_begin[i][j] - running_totals[i][j] in (-1, -4)))\
            and fixed_sum_begin[i][j] < (width - 2)\
            and not (single_rows[i][j+1] == 2 and fixed_sum_begin[i][j] - running_totals[i][j+2] == -4):
            #while there is no choice, we can fill up the first part of the row
            if ( (running_totals[i][j+2] - fixed_sum_begin[i][j] != 3) and (running_totals[i][j+1] - fixed_sum_begin[i][j] != 3)\
                and (width - fixed_sum_begin[i][j] != 4)) or (width - fixed_sum_begin[i][j] == 3):
                fixed_sum_begin[i].append(fixed_sum_begin[i][j] + 3)
            #might not need this! it (should be) guaranteed
            elif ( (running_totals[i][j+1] - fixed_sum_begin[i][j] != 2) and (running_totals[i][j] - fixed_sum_begin[i][j] != 2))\
            or (width - running_totals[i][j] == 2):
                #is the == 2 necessary?
                fixed_sum_begin[i].append(fixed_sum_begin[i][j] + 2)
            else:
                print "Bug!"
            j += 1
            #Need to account for false choices near end of row, see 32232 in 18,3;
            #this is a hacky way to do it. Implementing the above steps in reverse
            #may be more elegant, but slower.
            
        if fixed_sum_begin[i][-1] == width - 4:
            fixed_sum_begin[i].extend([width-2,width])
        elif width - fixed_sum_begin[i][-1] == 2 or width - fixed_sum_begin[i][-1] == 3:
            fixed_sum_begin[i].append(width)
        elif fixed_sum_begin[i][-1] == width - 6 and running_totals[i][-3] == width - 2:
            fixed_sum_begin[i].extend([width-3,width])
        
        fixed_part_begin[i].extend([fixed_sum_begin[i][y]-fixed_sum_begin[i][y-1] for y in xrange(1,len(fixed_sum_begin[i]))])
        #this goes back from the summed fixed rows, to the originals (made of 2s and 3s)
        ###print "fixed",i, fixed_rows[i]
        ##print "fixed:",fixed_part_begin[i]
        
        count = 0
        j = 0
        chunks = []
        reverse_count = width
        
        if fixed_sum_begin[i][-1] != width:
            #first, generate the fixed ending for each row
            single_rows[i].reverse()
            running_totals[i] = running_total(single_rows[i])
            
            while ( ( single_rows[i][j+1] != 3 ) or ( not fixed_sum_end[i][j] - running_totals[i][j] in (-1, -4)))\
            and fixed_sum_end[i][j] < (width - fixed_sum_begin[i][-1])\
            and not (single_rows[i][j+1] == 2 and fixed_sum_end[i][j] - running_totals[i][j+2] == -4):
                #while there is no choice, we can fill up the first part of the row
                if ( (running_totals[i][j+2] - fixed_sum_end[i][j] != 3) and (running_totals[i][j+1] - fixed_sum_end[i][j] != 3)\
                    and (width - fixed_sum_end[i][j] != 4)) or (width - fixed_sum_end[i][j] == 3):
                    fixed_sum_end[i].append(fixed_sum_end[i][j] + 3)
                #might not need this! it (should be) guaranteed
                elif ( (running_totals[i][j+1] - fixed_sum_end[i][j] != 2) and (running_totals[i][j] - fixed_sum_end[i][j] != 2))\
                or (width - running_totals[i][j] == 2):
                    #is the == 2 necessary?
                    fixed_sum_end[i].append(fixed_sum_end[i][j] + 2)
                else:
                    print "Bug!"
                j += 1
            
            single_rows[i].reverse()
                
            fixed_part_end[i].extend([fixed_sum_end[i][y]-fixed_sum_end[i][y-1] for y in xrange(1,len(fixed_sum_end[i]))])
            
            fixed_part_end[i].reverse()
            
            if sum(fixed_part_begin[i]) + sum(fixed_part_end[i]) != width:
                count = 0
                for j in xrange(len(fixed_sum_begin[i]),len(single_rows[i])-len(fixed_sum_end[i])): #is this right
                    if single_rows[i][j] == 2:
                        
                        if single_rows[i][j-1] == 3:# and had_two: #think about if this works
                            if count:
                                chunks += [count+1]
                            count = 0
                        else:
                            count -= 1
                    else: # == 3
                        if single_rows[i][j-1] == 2 and j != len(fixed_sum_begin[i]):
                            if count:
                                chunks += [count]
                            count = 1
                        else:
                            count += 1
                
                if count: chunks += [count]
                    
                if fixed_sum_begin[i][-1] + fixed_sum_end[i][-1] +\
                sum([3*x-1 for x in chunks if x > 0]) +\
                sum([-2*x for x in chunks if x < 0]) < width:
                    chunks[-1] += 1
                    
        
        if fixed_sum_begin[i][-1] != width:
            variable_part[i] = map(flatten,product(*flatten(map(permutations,chunks))))
        
        
    for i in xrange(length):
        
        if single_rows[i][0] == 2:
            continue
        
        if not variable_part.get(i,[]):
            #if there's no variable part; i.e. the whole row is fixed
            ##print "total is", fixed_part_begin[i]
            compat_blocks[i] = [fixed_part_begin[i]]
        else:
            for j in [list(x) for x in variable_part[i]]:
                compat_blocks[i].append(fixed_part_begin[i]+j+fixed_part_end[i])
            

    for i in xrange(length):
        for j in xrange(len(compat_blocks[i])):
            try:
                compatibility[i].add(single_rows.index(compat_blocks[i][j]))
                compatibility[single_rows.index(compat_blocks[i][j])].add(i)
            except ValueError:
                print "bug! i,j:",i,j
            
    #print "final compat:"
    #for q in xrange(length):
    #    print q, compatibility[q]
    return compatibility

def find_total_walls(compatibility, rows_left):
    length = len(compatibility)
    previous_row = [1 for x in xrange(length)]
    
    for row in xrange(rows_left - 1):
        next_row_possibilities = [0 for x in xrange(length)]
        for compat_index in xrange(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 are nicer. blocks of width 3 and 4.5 are at a 2:3 ratio

single_rows = all_single_rows(width)
compatibility = generate_compatibility(single_rows, width)
total_walls = find_total_walls(compatibility, height)

print total_walls

t2 = time.clock()
print "Total time was", round(t2-t1, 3), "seconds."