performance measurements

Each table row shows performance measurements for this Python 3 program with a particular command-line input value N.

 N  CPU secs Elapsed secs Memory KB Code B ≈ CPU Load
2,09810.8210.824,4281442  0% 100% 0% 1%

Read the ↓ make, command line, and program output logs to see how this program was run.

Read meteor-contest benchmark to see what this program should do.

 notes

Python 3.4.0 (default, Mar 17 2014, 08:23:52) [GCC 4.8.1] on linux

 meteor-contest Python 3 program source code

# The Computer Language Benchmarks Game

# http://benchmarksgame.alioth.debian.org/

#

# contributed by: Olof Kraigher

# 2to3


from sys import argv

width = 5
height = 10

directions  = { "E" : 0, "NE" : 1, "NW" : 2, "W" : 3, "SW" : 4, "SE" : 5}
rotate      = { "E" : "NE", "NE" : "NW", "NW" : "W", "W" : "SW", "SW" : "SE", "SE" : "E"}
flip        = { "E" : "W", "NE" : "NW", "NW" : "NE", "W" : "E", "SW" : "SE", "SE" : "SW"}
move        = { "E" : lambda x,y: (x+1,y),
                "W" : lambda x,y: (x-1,y),
                "NE" : lambda x,y: (x+(y%2),y-1),
                "NW" : lambda x,y: (x+(y%2)-1,y-1),
                "SE" : lambda x,y: (x+(y%2),y+1),
                "SW" : lambda x,y: (x+(y%2)-1,y+1)}

pieces =   [    ["E", "E", "E", "SE"],
                ["SE", "SW", "W", "SW"],
                ["W", "W", "SW", "SE"],
                ["E",  "E", "SW", "SE"],
                ["NW", "W", "NW", "SE", "SW"],
                ["E",  "E", "NE", "W"],
                ["NW", "NE", "NE", "W"],
                ["NE", "SE", "E", "NE"],
                ["SE", "SE", "E", "SE"],
                ["E", "NW", "NW", "NW"]]

solutions = []
masks = [0 for i in range(10)]

valid = lambda x,y: (0 <= x) and (x < width) and (0 <= y) and (y < height)
legal = lambda mask,board: (mask & board) == 0
zerocount = lambda mask: sum([((1<<x) & mask) == 0 for x in range(50)])

def findFreeCell(board):
    for y in range(height):
        for x in range(width):
            if board & (1 << (x + width*y)) == 0:
                return x,y


def floodFill(board, xxx_todo_changeme):
    (x, y) = xxx_todo_changeme
    if not valid(x,y):
        return board
    if board & (1 << (x + width*y)) != 0:
        return board

    board = board | (1 << (x + width*y))

    for f in list(move.values()):
        board = board | floodFill(board, f(x,y))

    return board

def noIslands(mask):
    zeroes = zerocount(mask)

    if zeroes < 5:
        return False

    while mask != 0x3FFFFFFFFFFFF:
        mask = floodFill(mask, findFreeCell(mask))
        new_zeroes = zerocount(mask)

        if zeroes - new_zeroes < 5:
            return False

        zeroes = new_zeroes

    return True

def getBitmask(x,y,piece):
    mask = (1 << (x + width*y))

    for cell in piece:
        x,y = move[cell](x,y)
        if valid(x,y):
            mask = mask | (1 << (x + width*y))
        else:
            return False, 0

    return True, mask

def allBitmasks(piece, color):
    bitmasks = []
    for orientations in range(2):
        for rotations in range(6 - 3*(color == 4)):
            for y in range(height):
                for x in range(width):
                    isValid, mask = getBitmask(x,y,piece)
                    if isValid and noIslands(mask):
                        bitmasks.append(mask)

            piece = [rotate[cell] for cell in piece]
        piece = [flip[cell] for cell in piece]


    return bitmasks

def generateBitmasks():

    global masksAtCell

    masksAtCell = [[[] for j in range(10)] for i in range(width*height)]

    color = 0
    for piece in pieces:
        masks = allBitmasks(piece, color)
        masks.sort()
        cellMask = 1 << (width*height-1)
        cellCounter = width*height-1

        j = len(masks)-1

        while (j >= 0):
            if (masks[j] & cellMask) == cellMask:
                masksAtCell[cellCounter][color].append(masks[j])
                j = j-1
            else:
                cellMask = cellMask >> 1
                cellCounter -= 1
        color += 1


def solveCell(cell, board, n):

    global solutions, masks, masksAtCell

    if len(solutions) >= n:
        return

    if board == 0x3FFFFFFFFFFFF:
        # Solved

        s = stringOfMasks(masks)
        solutions.append(s);
        solutions.append(inverse(s));
        return

    if board & (1 << cell) != 0:
        # Cell full

        solveCell(cell-1, board, n)
        return

    if cell < 0:
        # Out of board

        return

    for color in range(10):
        if masks[color] == 0:
            for mask in masksAtCell[cell][color]:
                if legal(mask, board):
                    masks[color] = mask
                    solveCell(cell-1, board | mask, n);
                    masks[color] = 0

def solve(n):
    generateBitmasks()
    solveCell(width*height-1, 0, n)


def stringOfMasks(masks):
    s = ""
    mask = 1;
    for y in range(height):
        for x in range(width):
            for color in range(10):
                if (masks[color] & mask) != 0:
                    s += str(color)
                    break
                elif color == 9:
                    s += "."
            mask = mask << 1
    return s

def inverse(s):
    ns = [x for x in s]

    for x in range(width):
        for y in range(height):
            ns[x + y*width] = s[width-x-1 + (width - y - 1)*width]

    return s

def printSolution(solution):
    for y in range(height):
        for x in range(width):
            print(solution[x + y*width], end=' ')

        if (y%2) == 0:
            print("")
            print("", end=' ')
        else:
            print("")

if __name__ == "__main__":

    if not len(argv) > 1:
        exit()

    solve(int(argv[1]))
    print(len(solutions), "solutions found")
    print()
    printSolution(min(solutions))
    print()
    printSolution(max(solutions))
    print()

 make, command-line, and program output logs

Tue, 18 Mar 2014 19:44:07 GMT

MAKE:
mv meteor.python3 meteor.py
0.01s to complete and log all make actions

COMMAND LINE:
/usr/local/src/Python-3.4.0/bin/python3.4 meteor.py 2098

PROGRAM OUTPUT:
2098 solutions found

0 0 0 0 1 
 2 2 2 0 1 
2 6 6 1 1 
 2 6 1 5 5 
8 6 5 5 5 
 8 6 3 3 3 
4 8 8 9 3 
 4 4 8 9 3 
4 7 4 7 9 
 7 7 7 9 9 

9 9 9 9 8 
 9 6 6 8 5 
6 6 8 8 5 
 6 8 2 5 5 
7 7 7 2 5 
 7 4 7 2 0 
1 4 2 2 0 
 1 4 4 0 3 
1 4 0 0 3 
 1 1 3 3 3 

Revised BSD license

  Home   Conclusions   License   Play