COMP3702 Tutorial 3 solutions

matt_q3.py

from matt_q1_q2 import *

class EightPuzzle:
    ACTIONS = ['U', 'D', 'L', 'R']

    def __init__(self, init_state, goal_state):
        self.size = 3
        self.init_state = init_state
        self.goal_state = goal_state

    @staticmethod
    def coord_map(single):
        return single % 3, single // 3

    @staticmethod
    def coord_reverse(x, y):
        return y * 3 + x

    @staticmethod
    def swap(config, coord1, coord2):
        c1 = EightPuzzle.coord_reverse(*coord1)
        c2 = EightPuzzle.coord_reverse(*coord2)
        result = list(config)
        result[c1], result[c2] = result[c2], result[c1]

        return ''.join(result)

    def step(self, state, action):
        x, y = self.coord_map(state.index('_'))
        action_map = {'L': (x - 1, y), 'R': (x + 1, y), 
            'U': (x, y - 1), 'D': (x, y + 1)}

        next_move = action_map.get(action, None)
        if next_move is None:
            assert False, "Invalid Action"

        if (not 0 <= next_move[0] < self.size) \
          or (not 0 <= next_move[1] < self.size):
            return False, state
        
        next_state = self.swap(state, (x, y), next_move)
        return True, next_state

    def is_goal(self, state):
        return state == self.goal_state

    def get_state_cost(self, state):
        return 1

def num_mismatches_heuristic(env, state):
    mismatches = 0
    for tile in '12345678_':
        x, y = EightPuzzle.coord_map(state.index(tile))
        xx, yy = EightPuzzle.coord_map(env.goal_state.index(tile))

        mismatches += (x != xx) + (y != yy)
    return mismatches // 2

def summed_manhattan_heuristic(env, state):
    total_displacement = 0
    for tile in '12345678_':
        x, y = EightPuzzle.coord_map(state.index(tile))
        xx, yy = EightPuzzle.coord_map(env.goal_state.index(tile))
        
        total_displacement += (abs(xx - x) + abs(yy - y))
    return total_displacement // 2


if __name__ == "__main__":
    n_trials = 100
    print('== Exercise 3.3 ==')
    env = EightPuzzle("281463_75", "1238_4765")

    print('BFS:')
    t0 = time.time()
    for i in range(n_trials):
        actions_bfs = bfs(env, verbose=(i == 0))
    t_bfs = (time.time() - t0) / n_trials
    print(f'Num Actions: {len(actions_bfs)},\nActions: {actions_bfs}')
    print(f'Time: {t_bfs}')
    print('\n')

    print('IDDFS:')
    t0 = time.time()
    for i in range(n_trials):
        actions_iddfs = iddfs(env, verbose=(i == 0))
    t_iddfs = (time.time() - t0) / n_trials
    print(f'Num Actions: {len(actions_iddfs)},\nActions: {actions_iddfs}')
    print(f'Time: {t_iddfs}')
    print('\n')

    print('UCS:')
    t0 = time.time()
    for i in range(n_trials):
        actions_ucs = ucs(env, verbose=(i == 0))
    t_ucs = (time.time() - t0) / n_trials
    print(f'Num Actions: {len(actions_ucs)},\nActions: {actions_ucs}')
    print(f'Time: {t_ucs}')
    print('\n')

    print('A* (num mismatches):')
    t0 = time.time()
    for i in range(n_trials):
        actions_a_star = a_star(env, num_mismatches_heuristic, verbose=(i == 0))
    t_a_star = (time.time() - t0) / n_trials
    print(f'Num Actions: {len(actions_a_star)},\nActions: {actions_a_star}')
    print(f'Time: {t_a_star}')
    print('\n')

    print('A* (summed manhattan):')
    t0 = time.time()
    for i in range(n_trials):
        actions_a_star = a_star(env, summed_manhattan_heuristic, verbose=(i == 0))
    t_a_star = (time.time() - t0) / n_trials
    print(f'Num Actions: {len(actions_a_star)},\nActions: {actions_a_star}')
    print(f'Time: {t_a_star}')
    print('\n')