Matches meme solver

matches_meme_solver.py

#!/usr/bin/env python3
from multiprocessing import Pool, Queue
from itertools import product

PROBLEM = '  6008  '
DEPTH = 2

EMPTY = 0, 0, 0, 0, 0, 0, 0
DIGIT_FONTS = [
    (
        (1, 1, 1, 1, 0, 1, 1),
    ),
    (
        (1, 0, 0, 1, 0, 0, 0), # (0, 0, 1, 0, 0, 1, 0)
    ),
    (
        (0, 1, 1, 1, 1, 0, 1),
    ),
    (
        (0, 1, 1, 0, 1, 1, 1),
    ),
    (
        (1, 0, 1, 0, 1, 1, 0),
    ),
    (
        (1, 1, 0, 0, 1, 1, 1),
    ),
    (
        (1, 1, 0, 1, 1, 1, 1),
    ),
    (
        (0, 1, 1, 0, 0, 1, 0), # (1, 1, 1, 0, 0, 1, 0),
    ),
    (
        (1, 1, 1, 1, 1, 1, 1),
    ),
    (
        (1, 1, 1, 0, 1, 1, 1), # (1, 1, 1, 0, 1, 1, 0),
    ),
]
COUNT_MAP = ['0th', '1st', '2nd', '3rd'] + \
    ['{}th'.format(i) for i in range(4, max(4, len(PROBLEM) + 1))]
POS_MAP = ['Left top', 'Top', 'Right Top',
           'Left bottom', 'Middle', 'Right bottom', 'Bottom']

REVERSE_MAP = {}
for i, fonts in enumerate(DIGIT_FONTS):
    for font in fonts:
        REVERSE_MAP[font] = i
REVERSE_MAP[EMPTY] = ' '


def slice_fonts(fonts):
    sliced_fonts = []
    for i in range(len(fonts) // 7):
        sliced_fonts.append(tuple(fonts[i * 7:(i + 1) * 7]))
    return sliced_fonts


def find_neighbor_actions_job(fonts, possible_move):
    def internal(ab_list):
        mutate_fonts = list(fonts)
        actions_done = []  # 0 = Skip, 1 = Removed, 2 = Inserted, 3 = Moved
        for ab in ab_list:
            a, b = ab
            if a == b:
                if possible_move == 0:
                    if mutate_fonts[a]:
                        mutate_fonts[a] = 0
                        actions_done.append((1, a))
                    else:
                        actions_done.append((0,))
                elif possible_move == 2:
                    if not mutate_fonts[a]:
                        mutate_fonts[a] = 1
                        actions_done.append((2, a))
                    else:
                        actions_done.append((0,))
                else:
                    actions_done.append((0,))
            else:
                if mutate_fonts[a] and not mutate_fonts[b]:
                    mutate_fonts[a] = 0
                    mutate_fonts[b] = 1
                    actions_done.append((3, a, b))
                else:
                    actions_done.append((0,))
        if fonts != tuple(mutate_fonts):
            should_add = True
            for mutate_font in slice_fonts(mutate_fonts):
                if mutate_font not in REVERSE_MAP:
                    should_add = False
                    break
            if should_add:
                return tuple(actions_done)
    return internal


def find_neighbor_actions(fonts, depth):
    # (a1, b1, a2, b2, .., a_depth, b_depth)
    neighbor_actions = set()
    prod = product(
        *([list(product(*[range(len(fonts)), range(len(fonts))]))] * depth))
    for possible_move in range(3):  # When an == bn, Remove | Leave as is | Add
        wrapper = find_neighbor_actions_job(fonts, possible_move)
        for ab_list in prod:
            actions = wrapper(ab_list)
            if actions:
                neighbor_actions.add(actions)
    return neighbor_actions


dup = set()


def move_recursive(moving_fonts, actions_left):
    global l, dup
    if actions_left == 0:
        return moving_fonts
    possible_fonts_list = []
    for possible_fonts in moving_fonts:
        for i in range(len(possible_fonts)):
            for j in range(len(possible_fonts)):
                if i != j and possible_fonts[i] == 1 and possible_fonts[j] == 0:
                    f = list(possible_fonts)
                    f[i], f[j] = 0, 1
                    k = (tuple(f), actions_left,)
                    if k in dup:
                        continue
                    dup.add(k)
                    fl_append = move_recursive([f], actions_left - 1)
                    possible_fonts_list += fl_append
    return possible_fonts_list


def find_neighbor_actions_move_only(fonts, depth):  # Much faster
    # (a1, b1, a2, b2, .., a_depth, b_depth)
    result = move_recursive([fonts], depth)

    neighbor_actions = set()
    for muta in result:
        should_add = True
        for mutate_font in slice_fonts(muta):
            if mutate_font not in REVERSE_MAP:
                should_add = False
                break
        if should_add:
            actions = []
            min_j = 0
            for i in range(len(fonts)):
                if fonts[i] == 1 and muta[i] == 0:
                    for j in range(min_j, len(fonts)):
                        if fonts[j] == 0 and muta[j] == 1:
                            min_j = j + 1
                            actions.append((3, i, j))
                            break
            neighbor_actions.add(tuple(actions))
    return neighbor_actions


def pos_repr(pos):
    pos, nth = pos % 7, pos // 7 + 1
    return '({}, {})'.format(COUNT_MAP[nth], POS_MAP[pos])


def construct_from_neighbor_actions(fonts, actions):
    # 0 = Skip, 1 = Removed, 2 = Inserted, 3 = Moved
    mutate_fonts = list(fonts)
    info = {
        'action_human': [],
        'mutating_fonts_list': [],
        'repr_digit': None
    }
    info['mutating_fonts_list'].append(fonts)
    for action in actions:
        if action[0] == 0:
            info['action_human'].append('Skip')
        elif action[0] == 1:
            mutate_fonts[action[1]] = 0
            info['action_human'].append(
                'Removed from {}'.format(pos_repr(action[1])))
        elif action[0] == 2:
            mutate_fonts[action[1]] = 1
            info['action_human'].append(
                'Inserted to {}'.format(pos_repr(action[1])))
        elif action[0] == 3:
            mutate_fonts[action[1]] = 0
            mutate_fonts[action[2]] = 1
            info['action_human'].append(
                'Moved from {} to {}'.format(pos_repr(action[1]), pos_repr(action[2])))
        info['mutating_fonts_list'].append(tuple(mutate_fonts))
    info['repr_digit'] = int(
        "".join(map(lambda f: str(REVERSE_MAP[f]), slice_fonts(mutate_fonts))).replace(' ', ''))
    return info


def render_font_to_buf(font):
    buf = ''
    for i, d in enumerate(font):
        if i == 1 or i == 4:
            buf += '‾' if d else ' '
        elif i == 6:
            buf += ' ‾ ' if d else '   '
        else:
            buf += '|' if d else ' '
        if i == 2 or i == 5:
            buf += '\n'
    return buf


def render_font(font):
    print(render_font_to_buf(font))


def line_by_line(buf_a, buf_b):
    c = ''
    a = buf_a.split('\n')
    b = buf_b.split('\n')
    for i in range(len(a)):
        c += a[i] + ' ' + b[i] + '\n'
    return c.strip('\n')


def line_by_line_multi(bufs):
    buf = bufs[0]
    for i in range(len(bufs) - 1):
        buf = line_by_line(buf, bufs[i + 1])
    return buf


if __name__ == '__main__':
    problem_fonts = []
    for s in PROBLEM:
        try:
            problem_fonts += list(DIGIT_FONTS[int(s)][0])
        except:
            problem_fonts += list(EMPTY)
    print(problem_fonts)
    all_actions = find_neighbor_actions_move_only(problem_fonts, DEPTH)
    infos = []
    for actions in all_actions:
        infos.append(construct_from_neighbor_actions(problem_fonts, actions))
    infos.sort(key=lambda i: i['repr_digit'])
    for info in infos:
        print(info)
        for progress_fonts in info['mutating_fonts_list']:
            bufs = list(map(lambda f: render_font_to_buf(f),
                            slice_fonts(progress_fonts)))
            lbl_bufs = line_by_line_multi(bufs)
            print(lbl_bufs)
    digits = []
    for info in infos:
        if not digits or digits[len(digits) - 1] != info['repr_digit']:
            digits.append(info['repr_digit'])
    print('Possible solutions', digits, len(digits))

origin.txt

https://www.facebook.com/sarcasmLOL/photos/a.1521463861515726.1073741828.1515871602074952/2800973426898090/?type=3&theater
https://drop.wtako.net/file/02b411604d697ca0e2038202616b885aea187754.jpg

https://www.facebook.com/photo.php?fbid=2072557412957573&set=gm.1436841499991545&type=3&theater