Created
June 24, 2019 03:11
-
-
Save jmhummel/cb279bf40779eef259ebf7e5201581d9 to your computer and use it in GitHub Desktop.
2019-06-21 Riddler Classic
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment