Child Toy Analysis

ToysAlgo.py

from collections import Counter
from itertools import permutations
from matplotlib import pyplot as plt


COLS = 5
ROWS = 6

x1 = 10
x2 = 10

assert x1 + x2 * 2 == COLS * ROWS

level = [[0] * COLS for _ in range(ROWS)]

total = 0

counter = Counter()


def display_level(level):
    for row in level:
        print(' '.join(str(v) for v in row))
    print('=' * 20)


def calc_map(level):
    '''
    1 1 1 2 3
    1 2 3 2 3
    1 2 3 2 3
    1 2 3 2 3
    1 2 3 2 3
    1 2 3 2 3
    '''
    init = list(range(COLS))
    for row in level:
        next = [0] * COLS
        for i, v in enumerate(row):
            if v == 1:
                next[i] = init[i]
            elif v == 2:
                next[i + 1] = init[i]
            elif v == 3:
                next[i - 1] = init[i]
        init = next
    return tuple(init)


def distribute(level, x1, x2, i=0, j=0):
    if x1 == x2 == 0:
        # display_level(level)
        res = calc_map(level)
        global total
        total += 1
        counter[res] += 1
        return
    # new line
    if j >= COLS:
        j = 0
        i += 1
    # try put a 1x1 block
    if x1 > 0:
        level[i][j] = 1
        distribute(level, x1 - 1, x2, i, j + 1)
        level[i][j] = 0
    # try put a 1x2 block
    if x2 > 0 and j + 1 < COLS:
        level[i][j] = 2
        level[i][j + 1] = 3
        distribute(level, x1, x2 - 1, i, j + 2)
        level[i][j] = 0
        level[i][j + 1] = 0


distribute(level, x1, x2)

print(f'{total=}')

# filter out the symmetric cases
filtered = Counter()
for case, count in sorted(counter.items(), key=lambda x: x[0]):
    if case[::-1] in filtered:
        filtered[case[::-1]] += count
    else:
        filtered[case] += count


# for case in filtered.most_common():
#     print(case)

# print(len(filtered))

most_common = filtered.most_common()
x = [str(case) for case, _ in most_common]
y = [count for _, count in most_common]

# plot the distribution
# plt.bar(x, y)
# plt.xticks(rotation=90)
# plt.show()

# print(sum(filtered.values()))

perms = set(permutations(range(COLS)))
unreached = perms.difference(set(counter.keys()))

for case in sorted(unreached):
    print(case)

print(f'{len(unreached)=}')