top-front-side-puzzle.py

from hashlib import md5
from time import time


def views_match(cube, top, front, side):
    view_from_top = [int(sum(cube[i::16]) > 0) for i in range(16)]
    view_from_front = [int(sum(cube[i+j:i+j+16:4]) > 0) for i in range(0, 64, 16) for j in range(4)]
    view_from_side = [int(sum(cube[i+j:i+j+4]) > 0) for i in range(0, 64, 16) for j in reversed(range(0, 16, 4))]
    return view_from_top == top and view_from_front == front and view_from_side == side


def solve_minimal(top, front, side):
    cube = [1] * 64

    for idx, value in enumerate(top):
        if value == 0:
            cube[idx::16] = [0] * 4
    for idx, value in enumerate(front):
        if value == 0:
            column, height = idx % 4, idx // 4
            cube[height*16+column:height*16+column+16:4] = [0] * 4
    for idx, value in enumerate(side):
        if value == 0:
            row, height = 3 - (idx % 4), idx // 4
            cube[height*16+row*4:height*16+row*4+4] = [0] * 4

    if views_match(cube, top, front, side):
        pruning_table = generate_pruning(cube, front, side)
        time_starting = time()
        result = recursive(cube, 0, 64, 0, top, front, side, pruning_table)
        return result[0], result[1], time() - time_starting


def generate_pruning(cube, front, side):
    pruning_table = []
    for i in range(64):
        height, row, column = i // 16, 3 - ((i // 4) % 4), i % 4

        different_heights = max(sum(front[height*4+4:]), sum(side[height*4+4:]))

        column_sum = 0
        if row == 3:
            column_sum += sum(front[height*4+column+1:height*4+4])

        row_sum = sum(side[height*4:height*4+row])

        pruning_table.append(different_heights + max(column_sum, row_sum))

    return pruning_table


def recursive(cube, idx, best, s, top, front, side, pruning_table):
    if idx == 64:
        return sum(cube), cube[:]

    result0 = 65, None

    if s + pruning_table[idx] >= best:
        return result0

    if cube[idx] == 1:
        cube[idx] = 0
        if views_match(cube, top, front, side):
            result0 = recursive(cube, idx + 1, best, s, top, front, side, pruning_table)
            if result0[0] < best:
                best = result0[0]
        cube[idx] = 1

    result1 = recursive(cube, idx + 1, best, s + cube[idx], top, front, side, pruning_table)

    return min(result0, result1)


def create(n):
    inp = "{:048b}".format(int(md5("{:06}".format(n).encode("utf-8")).hexdigest()[:12], 16))
    cube = list(map(int, inp))
    return cube[:16], cube[16:32], cube[32:]


time_start = time()
count_solvable = 0
solving_times = []
cubes = []
N = 1000000
for n in range(N):
    top, front, side = create(n)

    result = solve_minimal(top, front, side)
    if result:
        count_solvable += 1
        cubes.append(result[0])
        solving_times.append(result[2])
        print("Seed: {:06}, time: {:.2f} sec, cubes: {}, cube: {}".format(n, result[2], result[0], result[1]))

print()
print("{} out of {} puzzles are solvable. ".format(count_solvable, N))
print("The number of cubes for all solvable puzzles is {}.".format(sum(cubes)))
print("Cubes necessary: min {}, avg {:.2f}, max {}.".format(min(cubes), sum(cubes) / len(cubes), max(cubes)))
print("Solving times (seconds): min {:.2f}, avg {:.2f}, max {:.2f}".format(min(solving_times),
                                                                           sum(solving_times) / len(solving_times),
                                                                           max(solving_times)))
print("Total time: {:.2f} seconds".format(time() - time_start))