2019-06-21 Riddler Classic

2019-06-21-classic-matrix.py

from heapq import heappush, heappop

import numpy as np
from collections import deque

STATES = [(0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 1), (0, 1, 0, 1), (0, 1, 1, 1), (1, 1, 1, 1)]
ACTIONS = STATES[1:]
STATE_MAP = {state: i for i, state in enumerate(STATES)}
ACTION_MAP = {action: i for i, action in enumerate(ACTIONS)}


def rotations(state):
    return (state[i:] + state[:i] for i in range(len(state)))


def normalize(state):
    return min(rotations(state))


def transform(state, action):
    return tuple(state[i] ^ action[i] for i in range(len(state)))


def get_action_matrix():
    output = np.zeros((5, 6, 6))
    for k, action in enumerate(ACTIONS):
        for j, state in enumerate(STATES):
            if state == (1, 1, 1, 1):
                output[k, j, j] = 1
            else:
                for rot in rotations(state):
                    state_out = normalize(transform(rot, action))
                    output[k, STATE_MAP[state_out], j] += 0.25
    return output


def a_star_search(action_matrix, start_v, goal_v):
    seen = set([])
    parent = {}
    heap = []
    seen.add(start_v)
    heappush(heap, (1, 0, 0, start_v))
    while heap:
        f_score, g_score, n, v = heappop(heap)
        # print(f_score, g_score, n, v)
        if v[:-1] == goal_v[:-1]:
            return parent, v
        n += 1
        for k, action in enumerate(ACTIONS):
            w = tuple(np.matmul(action_matrix[k], v))
            if w not in seen:
                seen.add(w)
                parent[w] = (v, action)
                g = n * (w[-1] - v[-1]) + g_score
                h = (n+1) * (1 - w[-1])
                f = h + g
                heappush(heap, (f, g, n, w))


def main():
    action_matrix = get_action_matrix()
    start_v = (1, 4, 4, 2, 4, 0)

    # best move set
    moves = [[1, 1, 1, 1],
             [0, 1, 0, 1],
             [1, 1, 1, 1],
             [0, 0, 1, 1],
             [1, 1, 1, 1],
             [0, 1, 0, 1],
             [1, 1, 1, 1],
             [0, 0, 0, 1],
             [1, 1, 1, 1],
             [0, 1, 0, 1],
             [1, 1, 1, 1],
             [0, 0, 1, 1],
             [1, 1, 1, 1],
             [0, 1, 0, 1],
             [1, 1, 1, 1]]

    v = start_v
    print('v', v)
    for action in moves:
        action = tuple(action)
        v = np.matmul(action_matrix[ACTION_MAP[action]], v)
        print('v', v)

    # return

    goal_v = (0, 0, 0, 0, 0, 1)
    print(action_matrix[0])
    parent, v = a_star_search(action_matrix, start_v, goal_v)

    moves = []
    while tuple(v) in parent:
        v, edge = parent[tuple(v)]
        moves.insert(0, (v, edge))

    for v, edge in moves:
        print(v)
        print(edge)
        print()

    for _, edge in moves:
        # print(v)
        print(edge)




if __name__ == '__main__':
    main()

2019-06-21-classic.py

from collections import deque


class State:
    @staticmethod
    def rotations(coins):
        return coins, coins[1:] + coins[:1], coins[2:] + coins[:2], coins[3:] + coins[:3]

    @staticmethod
    def normalize(coins):
        return min(coins, coins[1:] + coins[:1], coins[2:] + coins[:2], coins[3:] + coins[:3])

    @staticmethod
    def action_results(coins, action):
        s = set([])
        for rot in State.rotations(coins):
            res = tuple(rot[i] ^ action[i] for i in range(4))
            s.add(State.normalize(res))
        return s


ACTIONS = [[0, 0, 0, 1], [0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 1], [1, 1, 1, 1]]


class Vertex:
    @staticmethod
    def adjacent_edges(vertex):
        edges = []
        for action in ACTIONS:
            s = set([])
            for state in vertex:
                s.update(State.action_results(state, action))
            s.discard((1, 1, 1, 1))
            edges.append((action, s))
        return edges


class Node:
    def adjacent_edges(self):
        edges = []
        for action in ACTIONS:
            s = set([])
            for state in vertex:
                s.update(State.action_results(state, action))
            s.discard((1, 1, 1, 1))
            edges.append((action, s))
        return edges


def BFS(start_v, goal_v):
    seen = set([])
    parent = {}
    Q = deque([])
    seen.add(tuple(start_v))
    Q.appendleft(start_v)
    while len(Q) > 0:
        v = Q.pop()
        if v == goal_v:
            return parent
        for edge, w in Vertex.adjacent_edges(v):
            if tuple(w) not in seen:
                seen.add(tuple(w))
                parent[tuple(w)] = (v, edge)
                Q.appendleft(w)


def main():
    # coins = [0, 0, 1,

    start_v = {(0,0,0,0), (0,0,0,1), (0,0,1,1), (0,1,0,1), (0,1,1,1)}
    goal_v = set([])
    parent = BFS(start_v, goal_v)

    v = goal_v
    moves = []
    while tuple(v) in parent:
        v, edge = parent[tuple(v)]
        moves.insert(0, (v, edge))

    for v, edge in moves:
        print(v)
        print(edge)
        print()

    for _, edge in moves:
        # print(v)
        print(edge)


if __name__ == '__main__':
    main()