Day 20: Jurassic Jigsaw

For this one I use the same trick I used on day 5 (replacing the text with binary), Then I also reverse the strings, and I convert them to decimal. That gives me 8 numbers for each tile that I can then compare.

From there, I compare each tile's borders to each other tile. The ones that only match up 4 times (2 borders x2 because flipped) are the corner pieces.

#tiles = test_data.split('\n\n')
tiles = input_data.split('\n\n')

tile_dict = {}

class tile(object):
    def __init__(self, name, val):
        self.name = name
        self.original_data = val
        self.all_configurations = None
        self.all_borders = None
    def you_spin_me_right_round(self):
        #this should handle flipping, but not rotations
        front = []
        back = []
        for row in self.original_data:
            front.append(row[0])
            back.append(row[-1])
        borders = [''.join(front), ''.join(back), ''.join(self.original_data[0]),''.join(self.original_data[-1])]
        flipped_borders = []
        for border in borders:
            flipped_borders.append(border[::-1])
        binary_borders = []
        for border in borders + flipped_borders:
            border = border.replace('.', '0')
            border = border.replace('#', '1')
            binary_borders.append(int(border,2))
        #border configurations can go here if they're necessary
        self.all_borders = binary_borders

for tile_data in tiles:
    name = tile_data.split('\n')[0][5:9]
    new_tile = tile(name, list(map(list,tile_data.split('\n')[1:])))
    new_tile.you_spin_me_right_round()
    tile_dict[name] = new_tile

tile_scores = {}
for tile_key in tile_dict.keys():
    tile_score = 0
    base_tile = tile_dict[tile_key]
    for comparision_tile_key in tile_dict.keys():
        if tile_key is not comparision_tile_key:
            for border in base_tile.all_borders:
                if border in tile_dict[comparision_tile_key].all_borders:
                    tile_score = tile_score + 1
    tile_scores[tile_key] = tile_score
score_product = 1
for key in tile_scores.keys():
    if tile_scores[key] == 4:
        score_product = score_product * int(key)
        print(key)
print(score_product)

• For part A you only really need to care about the borders

• The borders can be converted into numbers a few different ways

I almost didn't do this one because I did not want to implement flipping and rotating (just tedious)... but then I realized that for Part 1, you do not need to actually perform the flips and rotations... you can just hash the edges. Once you hash the edges (ie. top, bottom, left, right, and their reversed versions) and track which tiles correspond to those edges, then you will see that edges will have a mapping to which tiles are neighbors. After you create this mapping, you can then count how many matched edges each tile has. The corners will have exactly 2 neighbors, so you can pick them out easily.

That is how I avoided having to actually flip or rotate the pieces and generate the actual image... Unfortunately, I think Part 2 may require actually forming the image, so I will probably go to sleep... I may or may not attempt Part 2 in the morning.

import collections
import functools
import operator
import re
import sys

# Functions

def read_tile(stream=sys.stdin):
    try:
        number = int(re.findall(r'Tile (\d+):', stream.readline())[0])
    except IndexError:
        return None, None

    tile = []
    while line := stream.readline().strip():
        tile.append(line)

    return number, tile

def read_tiles(stream=sys.stdin):
    tiles = {}
    while (tile := read_tile(stream)) and tile[0]:
        tiles[tile[0]] = tile[1]
    return tiles

def hash_edges(tiles):
    edges = collections.defaultdict(list)

    for number, tile in tiles.items():
        tile_edges = (
            tile[0],                            # Top
            tile[-1],                           # Bottom
            ''.join(r[0]  for r in tile),       # Left
            ''.join(r[-1] for r in tile),       # Right
        )

        for edge in tile_edges:
            edges[edge      ].append(number)
            edges[edge[::-1]].append(number)    # Flipped

    return edges

def count_neighbors(edges):
    counts = collections.defaultdict(set)

    for edge, tiles in edges.items():
        for tile1 in tiles:
            for tile2 in tiles:
                if tile1 != tile2:
                    counts[tile1].add(tile2)

    return counts

# Main Execution

def main():
    tiles   = read_tiles()
    edges   = hash_edges(tiles)
    counts  = count_neighbors(edges)
    corners = [tile for tile, neighbors in counts.items() if len(neighbors) == 2]
    result  = functools.reduce(operator.mul, corners)

    print(result)

if __name__ == '__main__':
    main()

use anyhow::Result;
use libaoc::{aoc, AocResult, Timer};
use regex::Regex;
use std::cell::RefCell;
use std::collections::BTreeMap;
use hashbrown::HashSet;

#[derive(Clone, Debug, Copy)]
struct Adjacency {
    id: usize,
    side: usize,
    flip: bool,
}
/*
top
right
bottom
left
*/
#[derive(Clone, Debug)]
struct Tile {
    data: Vec<Vec<char>>,
    sides: [usize; 4],
    flip_sides: [usize; 4],
    adjacency: [Vec<Adjacency>; 4],
    rotation: usize,
    flip: bool,
}

impl Tile {
    fn get_side(&self, side: usize) -> Option<usize> {
        let mut adj = self.adjacency.to_vec();
        if self.flip {
            adj.swap(0,2);
        }
        adj.rotate_right(self.rotation);
        adj[side].get(0).and_then(|x|Some(x.id))
    }

    /// applies flips and rotation until side side == id
    fn set_transform(&mut self, side: usize, id: usize, side2: usize, id2: usize) {
        let mut adj = self.adjacency.to_vec();
        for i in 0..4 {
            if ((id == 0 && adj[side].len() == 0) || (adj[side].len() > 0 && adj[side][0].id == id))&&((id2 == 0 && adj[side2].len() == 0) || (adj[side2].len() > 0 && adj[side2][0].id == id2)) {
                self.rotation = i;
                return;
            }
            adj.rotate_right(1);
        }
        adj.swap(0,2);
        self.flip = true;
        for i in 0..4 {
            if ((id == 0 && adj[side].len() == 0) || (adj[side].len() > 0 && adj[side][0].id == id))&&((id2 == 0 && adj[side2].len() == 0) || (adj[side2].len() > 0 && adj[side2][0].id == id2)) {
                self.rotation = i;
                return;
            }
            adj.rotate_right(1);
        }
    }
}

#[aoc("27803643063307", "1644")]
pub fn solve(timer: &mut Timer, input: &str) -> Result<AocResult> {
    let line = Regex::new(r"(\r?\n){2}")?;
    let input: BTreeMap<usize, _> = line
        .split(input)
        .map(|x| {
            let parts = x.split_once('\n').unwrap();
            let id = parts.0[5..=8].parse().unwrap();
            let data = parts.1.replace('.', "0").replace('#', "1");
            let data_map: Vec<_> = data.lines().collect();
            let chars = data_map.iter().skip(1).take(8).map(|x|x.chars().skip(1).take(8).collect()).collect();

            let top = usize::from_str_radix(data_map[0], 2).unwrap();
            let right = usize::from_str_radix(
                &data_map
                    .iter()
                    .map(|x| x.chars().rev().next().unwrap())
                    .collect::<String>(),
                2,
            )
            .unwrap();
            let bottom = usize::from_str_radix(
                &data_map[data_map.len() - 1]
                    .chars()
                    .rev()
                    .collect::<String>(),
                2,
            )
            .unwrap();
            let left = usize::from_str_radix(
                &data_map
                    .iter()
                    .rev()
                    .map(|x| x.chars().next().unwrap())
                    .collect::<String>(),
                2,
            )
            .unwrap();

            let top_flip = usize::from_str_radix(&data_map[0].chars().rev().collect::<String>(), 2).unwrap();
            let right_flip = usize::from_str_radix(
                &data_map
                    .iter().rev()
                    .map(|x| x.chars().rev().next().unwrap())
                    .collect::<String>(),
                2,
            )
            .unwrap();
            let bottom_flip = usize::from_str_radix(
                &data_map[data_map.len() - 1]
                    .chars()
                    .collect::<String>(),
                2,
            )
            .unwrap();
            let left_flip = usize::from_str_radix(
                &data_map
                    .iter()
                    .map(|x| x.chars().next().unwrap())
                    .collect::<String>(),
                2,
            )
            .unwrap();

            (
                id,
                RefCell::new(Tile {
                    data: chars,
                    sides: [top, right, bottom, left],
                    flip_sides: [top_flip, right_flip, bottom_flip, left_flip],
                    adjacency: [vec![], vec![], vec![], vec![]],
                    rotation: 0,
                    flip: false,
                }),
            )
        })
        .collect();

    timer.lap("Parse");

    for (&id, image) in &input {
        let mut adjacency = [vec![], vec![], vec![], vec![]];
        for (side_id, &side) in image.borrow().sides.iter().enumerate() {
            for (&test_id, test_image) in &input {
                if test_id == id {continue;}
                for (test_side_id, &test_side) in test_image.borrow().sides.iter().enumerate() {
                    if side == test_side {
                        adjacency[side_id].push(Adjacency {
                            id: test_id,
                            side: test_side_id+2,
                            flip: false,
                        })
                    }
                    if image.borrow().flip_sides[side_id] == test_side {
                        adjacency[side_id].push(Adjacency {
                            id: test_id,
                            side: test_side_id,
                            flip: true,
                        })
                    }
                }
            }
        }
        image.borrow_mut().adjacency = adjacency;
    }

    // it apears that adjacency lists contain either 0 or 1 adjacency, which
    // makes things significantly easier assuming this holds

    let adjacency_sums:Vec<_> = input.iter().map(|(&id, x)| {
        (id, x.borrow().adjacency.iter().map(|x|x.len()).sum::<usize>())
    }).collect();

    let part1 = adjacency_sums.iter().fold(1, |acc, (id, val)| {
        if *val == 2 {
            acc * id
        } else {
            acc
        }
    });

    timer.lap("Part 1");

    let image_size = (input.len() as f32).sqrt() as usize;
    let mut image = vec![vec![0usize; image_size]; image_size];

    // first cell
    image[0][0] = adjacency_sums.iter().filter(|(_,v)|*v==2).next().unwrap().0;
    input[&image[0][0]].borrow_mut().set_transform(0, 0, 3, 0);

    // first row
    for i in 1..image_size {
        let left = image[0][i-1];
        let new_id = input[&left].borrow().get_side(1).unwrap();
        image[0][i] = new_id;
        input[&new_id].borrow_mut().set_transform(0, 0, 3, left);
    }

    // first column
    for i in 1..image_size {
        let above = image[i-1][0];
        let new_id = input[&above].borrow().get_side(2).unwrap();
        image[i][0] = new_id;
        input[&new_id].borrow_mut().set_transform(0, above, 3, 0);
    }

    // other cells
    for col in 1..image_size {
        for row in 1..image_size {
            let above = image[row-1][col];
            let left = image[row][col-1];
            let new_id = input[&above].borrow().get_side(2).unwrap();
            image[row][col] = new_id;
            input[&new_id].borrow_mut().set_transform(0, above, 3, left);
        }
    }

    for tile in input.values() {
        let mut tile = tile.borrow_mut();
        if tile.flip {
            tile.data.reverse();
        }

        for _ in 0..tile.rotation {
            let mut new = vec![vec![]; 8];
            for col in 0..8 {
                for row in (0..8).rev() {
                    new[col].push(tile.data[row][col]);
                }
            }
            tile.data = new;
        }
    }

    let mut i = vec![];
    for row in &image {
        for tile_row in 0..8 {
            let mut row_str: Vec<char> = vec![];
            for tile in row {
                row_str.extend(input[&tile].borrow().data[tile_row].iter());
            }
            i.push(row_str);
        }
    }

    fn check_monster(i: &[Vec<char>], quick_exit: bool, found_set: &mut HashSet<(usize, usize)>) -> i32 {
        let mut count = 0;
        for r in 0..(i.len() - 2) {
            for c in 0..(i.len()-19) {
                //                   #
                // #    ##    ##    ###
                //  #  #  #  #  #  #
                let monster = [
                    (r,c+18),
                    (r+1,c),
                    (r+1,c+5),
                    (r+1,c+6),
                    (r+1,c+11),
                    (r+1,c+12),
                    (r+1,c+17),
                    (r+1,c+18),
                    (r+1,c+19),
                    (r+2,c+1),
                    (r+2,c+4),
                    (r+2,c+7),
                    (r+2,c+10),
                    (r+2,c+13),
                    (r+2,c+16),
                ];
                let is_monster = monster.iter().all(|&(r,c)|i[r][c]=='1');
                if is_monster && quick_exit {
                    return 1;
                }
                if is_monster {
                    count += 1;
                    for coord in &monster {
                        found_set.insert(*coord);
                    }
                }
            }
        }

        count
    }

    'out: loop {
        for _ in 0..4 {
            if check_monster(&i, true, &mut HashSet::new()) > 0 {
                break 'out;
            }

            let mut new = vec![vec![]; i.len()];
            for col in 0..i.len() {
                for row in (0..i.len()).rev() {
                    new[col].push(i[row][col]);
                }
            }
            i = new;
        }
        i.reverse();
        for _ in 0..4 {
            if check_monster(&i, true, &mut HashSet::new()) > 0 {
                break 'out;
            }

            let mut new = vec![vec![]; i.len()];
            for col in 0..i.len() {
                for row in (0..i.len()).rev() {
                    new[col].push(i[row][col]);
                }
            }
            i = new;
        }

        break 'out;
    }

    let ones = i.iter().fold(0, |acc, row| {
        acc + row.iter().fold(0, |acc, tile| {
            if *tile == '1' {
                acc + 1
            } else {
                acc
            }
        })
    });

    let mut found_set = HashSet::new();
    check_monster(&i, false, &mut found_set);
    let part2 = ones - found_set.len();

    timer.lap("Part 2");

    Ok(AocResult::new(part1, part2))
}

#!/usr/bin/env python3

import copy
import math
import sys

class Tile(object):
    def __init__(self, in_data):
#        print(f'Tile init: {in_data}')
        lines = [l.strip() for l in in_data.split('\n') if len(l) > 0]
        self.id = int(lines[0].split(" ")[1].replace(":", ""))
        self.data = lines[1:]
        self.left = None
        self.right = None
        self.top = None
        self.bot = None

    def get_left_edge(self):
        return [x[0] for x in self.data]

    def get_right_edge(self):
        return [x[-1] for x in self.data]

    def get_top_edge(self):
        return self.data[0]

    def get_bottom_edge(self):
        return self.data[-1]

    def get_id(self):
        return self.id

    def flip_vertical(self):
        self.data.reverse()
        tmp = self.top
        self.top = self.bot
        self.bot = tmp

        return self

    def rotate_right(self):
        new_data = [None] * len(self.data)
        for i, l in enumerate(self.data):
            new_data[i] = [None] * len(self.data[i])

        for i in range(len(self.data)):
            for j, c in enumerate(self.data[i]):
                new_data[j][len(self.data[i]) - i - 1] = c

        for i, l in enumerate(new_data):
            new_data[i] = ''.join(new_data[i])

        self.data = new_data

        tmp = self.top
        self.top = self.left
        self.left = self.bot
        self.bot = self.right
        self.right = tmp

        return self

    def __str__(self):
        s = f'Tile: {self.id}\n' + '\n'.join(self.data)

        return s

    def set_left(self, t):
        self.left = t

    def set_right(self, t):
        self.right = t

    def set_top(self, t):
        self.top = t

    def set_bot(self, t):
        self.bot = t

    def count_waves(self):
        waves = 0
        for line in self.data:
            for c in line:
                if c == '#':
                    waves += 1

        return waves

    def search_and_mark_seamonster(self, seamonster):
        seamonster_count = 0
        max_shards = 0
        for x in range(len(self.data) - len(seamonster)):
            for y in range(len(self.data[x]) - len(seamonster[0])):
                seamonster_shard_count = 0
                for a in range(len(seamonster)):
                    for b in range(len(seamonster[a])):
                        if seamonster[a][b] == '#' and self.data[x + a][y + b] == '#':
                            seamonster_shard_count += 1

                if seamonster_shard_count > max_shards:
                    max_shards = seamonster_shard_count
                if seamonster_shard_count == 15:
#                    print(f'found a seamonster! at {x}:{y}')
                    seamonster_count += 1
                    for a in range(len(seamonster)):
                        for b in range(len(seamonster[a])):
                            if seamonster[a][b] == '#' and self.data[x + a][y + b] == '#':
                                line = [x for x in self.data[x + a]]
                                line[y + b] = 'O'
                                self.data[x + a] = ''.join(line)

        return seamonster_count



class Board(object):
    def __init__(self, size):
        self.size = size
        self.space = [None] * size
        for i in range(size):
            self.space[i] = [None] * size

    def __str__(self):
        s = ''
        for i in range(self.size):
            for j in range(self.size):
                if type(self.space[i][j]) == Tile:
                    s += f'<{self.space[i][j].get_id()}>'
                else:
                    s += '<None>'
            if i != self.size - 1:
                s += '\n'
        return s

    def print_image(self):
        tile_size = len(self.space[0][0].data)
        image = []
        for x in range(self.size):
            for l in range(1, tile_size - 1):
                line = ''
                for y in range(self.size):
                    line += f'{self.space[x][y].data[l][1:-1]}'
                image.append(line)
        img_str = 'Img: 9999\n' + '\n'.join(image)
#        print(f'IMAGE:\n{img_str}')
        return img_str

    def place(self, x, y, tile):
        self.space[x][y] = tile
        return self

    def get(self, x, y):
        return self.space[x][y]

    def rotate_right(self):
        new_data = [None] * self.size
        for i in range(self.size):
            new_data[i] = [None] * self.size

        for i in range(self.size):
            for j, t in enumerate(self.space[i]):
#                print(f'rotate: [{i}][{j}] -> [{j}][{self.size - i - 1}] = {t}')
                new_data[j][self.size - i - 1] = t

        self.space = copy.deepcopy(new_data)
        return self


def check_bottom_top(one, two):
    return tiles[one].get_bottom_edge() == tiles[two].get_top_edge()

def check_top_bottom(one, two):
    return tiles[one].get_top_edge() == tiles[two].get_bottom_edge()

def check_right_left(one, two):
    return tiles[one].get_right_edge() == tiles[two].get_left_edge()

def check_left_right(one, two):
    return tiles[one].get_left_edge() == tiles[two].get_right_edge()

def find_top(one, two):
    for flips in range(2):
        for rots in range(4):
            if check_bottom_top(one, two):
#                print(f'tile {one} goes on top of tile {two}')
                tiles[one].set_bot(tiles[two])
                tiles[two].set_top(tiles[one])
                return True
            else:
                tiles[two].rotate_right()
        else:
            tiles[two].flip_vertical()
    return False

def find_bot(one, two):
    for flips in range(2):
        for rots in range(4):
            if check_top_bottom(one, two):
#                print(f'tile {one} goes below tile {two}')
                tiles[one].set_top(tiles[two])
                tiles[two].set_bot(tiles[one])
                return True
            else:
                tiles[two].rotate_right()
        else:
            tiles[two].flip_vertical()
    return False

def find_right(one, two):
    for flips in range(2):
        for rots in range(4):
            if check_right_left(one, two):
#                print(f'tile {one} goes left of {two}')
                tiles[one].set_right(tiles[two])
                tiles[two].set_left(tiles[one])
                return True
            else:
                tiles[two].rotate_right()
        else:
            tiles[two].flip_vertical()
    return False

def find_left(one, two):
    for flips in range(2):
        for rots in range(4):
            if check_left_right(one, two):
#                print(f'tile {one} goes right of {two}')
                tiles[one].set_left(tiles[two])
                tiles[two].set_right(tiles[one])
                return True
            else:
                tiles[two].rotate_right()
        else:
            tiles[two].flip_vertical()
    return False

#input_data = open('tiny_input', 'r').read().split('\n\n')
input_data = open('input', 'r').read().split('\n\n')

seamonster = """                  # 
#    ##    ##    ###
 #  #  #  #  #  #   """.split('\n')

tiles = {}

first_tile = None
for d in input_data:
    if len(d) < 10:
        continue
    t = Tile(d)
    tiles[t.get_id()] = t
    if first_tile is None:
        first_tile = t.get_id()

tile_keys = list(tiles.keys())
tile_set = set(tile_keys)
board_size = int(math.sqrt(len(tile_keys)))

b = Board(board_size)

# at this point we have a list of tiles that need placing, and a board that we could place them on.
# but we don't know where to start, so we do something a bit different:

broad = {(0, 0): first_tile}
coords = {first_tile: (0, 0)}
placed = set()
placed.add(first_tile)
to_check = set()
to_check.add(first_tile)

# we start with the first tile that we read from the input, and try to find tiles that match it
# on any of the sides. If we find a match, we set that match as 'placed', and don't look at it
# again.
# we do this until we have placed every single tile next to at least one other tile.
# this makes it so that if we have 'placed' all the tiles, we should have the relationships
# between them as well. A sanity-check later also proves it.
# I feel like this just works by happenstance, that there could be some inputs that would make
# this not work, but with the given input... it works.

while len(placed) < len(tile_keys):
    unset = tile_set - placed
    if len(to_check) == 0:
        to_check = placed.copy()
    last = to_check.pop()
    cur_t = tiles[last]
    cur_x, cur_y = coords[last]

    for t in unset:
        if find_top(last, t):
            broad[(cur_x + 1, cur_y)] = t
            coords[t] = (cur_x + 1, cur_y)
            placed.add(t)
            to_check.add(t)
            break
        if find_bot(last, t):
            broad[(cur_x - 1, cur_y)] = t
            coords[t] = (cur_x - 1, cur_y)
            placed.add(t)
            to_check.add(t)
            break
        if find_left(last, t):
            broad[(cur_x, cur_y - 1)] = t
            coords[t] = (cur_x, cur_y - 1)
            placed.add(t)
            to_check.add(t)
            break
        if find_right(last, t):
            broad[(cur_x, cur_y + 1)] = t
            coords[t] = (cur_x, cur_y + 1)
            placed.add(t)
            to_check.add(t)
            break

# normalize coordinates to start at zero and place them on the board, do sanity check
# since we just started at (0, 0), but we can go any direction, we need to normalize the indices
# so that they would work on a board. So we find the minimum coordinate for each direction
# and then add the absolute value of that to each index, so we start at zero and then just go up

min_x = 999
min_y = 999

for k in coords.keys():
    if coords[k][0] < min_x:
        min_x = coords[k][0]
    if coords[k][1] < min_y:
        min_y = coords[k][1]

for k in coords.keys():
    coords[k] = (coords[k][0] + abs(min_x), coords[k][1] + abs(min_y))
    b.place(coords[k][0], coords[k][1], tiles[k])
    # sanity-check that the neighbours are allowable
    if tiles[k].bot and not check_bottom_top(k, tiles[k].bot.get_id()):
        print(f'{k} should not have {tiles[k].bot.get_id()} at the bottom!')
    if tiles[k].top and not check_top_bottom(k, tiles[k].top.get_id()):
        print(f'{k} should not have {tiles[k].top.get_id()} at the top!')
    if tiles[k].right and not check_right_left(k, tiles[k].right.get_id()):
        print(f'{k} should not have {tiles[k].right.get_id()} at the right!')
    if tiles[k].left and not check_left_right(k, tiles[k].left.get_id()):
        print(f'{k} should not have {tiles[k].left.get_id()} at the left!')

# at this points we've placed all the tiles on the board, and we can get the result for task one
print(f'result: {b.get(0, 0).get_id() * b.get(board_size - 1, board_size - 1).get_id() * b.get(0, board_size - 1).get_id() * b.get(board_size - 1, 0).get_id()}')

# for task two we need a bit more work.
# add all tiles on the board together to make an image
img = b.print_image()
img_tile = Tile(img)

# then rotate and flip the image until we find the seamonsters
# if we've found seamonsters, we're done!
for flips in range(2):
    for rots in range(4):
        seamonster_count = img_tile.search_and_mark_seamonster(seamonster)
        if seamonster_count:
            print(f'{img_tile}')
            print(f'there are {seamonster_count} seamonsters in that image!')
            print(f'wave-count: {img_tile.count_waves()}')
            sys.exit(0)
        else:
            img_tile.rotate_right()
    else:
        img_tile.flip_vertical()

Ignoring the need to actually make the image seemed like the move here. Part 2 is making me regret this lol.

function main()

    input = []
    open("Day20/input.txt") do fp
        input = split(readchomp(fp), "\n\n")
    end

    tiles = Dict()
    for tile in input
        rows = split(tile, '\n')
        id = parse(Int, rows[1][6:end-1])
        tile = hcat([[val == '#' for val in row] for row in rows[2:end]]...)'
        tiles[id] = tile
        
    end

    all_possible_edges = Dict([key => get_edge_permutations(value) for (key, value) in tiles])
    
    shared_edges = Dict()
    for (id,edges) in all_possible_edges
        for (other_id, other_edges) in all_possible_edges
            if other_id != id
                if length(intersect(edges, other_edges)) == 2
                    if !(id in keys(shared_edges))
                        shared_edges[id] = [other_id]
                    else
                        push!(shared_edges[id], other_id)
                    end
                end
            end
        end
    end

    println(prod(key for (key,value) in shared_edges if length(value) == 2))
end

function get_edges(tile)
    top = Tuple(collect(tile[1,idx] for idx in 1:10))
    bottom = Tuple(collect(tile[10,idx] for idx in 1:10))
    left = Tuple(collect(tile[idx,1] for idx in 1:10))
    right = Tuple(collect(tile[idx,10] for idx in 1:10))
    return [top, bottom, left, right]
end

function get_edge_permutations(tile)
    return [get_edges(tile)..., collect(reverse(edge) for edge in get_edges(tile))...]
end

main()

use std::env;
use std::io;
use std::collections::{HashMap,VecDeque};

#[macro_use]
extern crate text_io;

const DIM1: usize = 10;
const DIM2: usize = 9;

#[derive(Debug,Clone)]
struct Tile {
    id: usize,
    img: HashMap<(usize,usize),bool>,
    edges: Vec<String>,
    neighbors: Vec<usize>,
    drawn: bool,
}
impl From<&str> for Tile {
    fn from(input: &str) -> Self {
        let lines = input.lines().collect::<Vec<_>>();
        let id: usize;
        scan!(lines.get(0).unwrap().bytes() => "Tile {}:", id);
        let mut map: HashMap<(usize,usize),bool> = HashMap::new();
        for (y,line) in lines[1..].iter().enumerate() {
            for (x,ch) in line.chars().enumerate() {
                match ch {
                    '#' => { map.insert((x,y),true); },
                    '.' => { map.insert((x,y),false); },
                    other => panic!("Unknown square: {}", other),
                }
            }
        }
        // Get edges
        let mut self_ = Self { id: id, img: map, edges: Vec::new(), neighbors: Vec::new(), drawn: false };
        self_.make_edges();
        self_
    }
}
impl Tile {
    pub fn make_edges(&mut self) {
        self.edges.clear();
        let mut edges: Vec<String> = vec![self.edge_top(),self.edge_bottom(),self.edge_left(),self.edge_right()];
        edges.push(self.edge_top().reversed());
        edges.push(self.edge_bottom().reversed());
        edges.push(self.edge_left().reversed());
        edges.push(self.edge_right().reversed());
        self.edges = edges;
    }
    pub fn edge_top(&self) -> String {
        (0..DIM1).map(|x| bool_char(self.img.get(&(x,0)).unwrap())).collect::<String>()
    }
    pub fn edge_bottom(&self) -> String {
        (0..DIM1).map(|x| bool_char(self.img.get(&(x,DIM1-1)).unwrap())).collect::<String>()
    }
    pub fn edge_left(&self) -> String {
        (0..DIM1).map(|y| bool_char(self.img.get(&(0,y)).unwrap())).collect::<String>()
    }
    pub fn edge_right(&self) -> String {
        (0..DIM1).map(|y| bool_char(self.img.get(&(DIM1-1,y)).unwrap())).collect::<String>()
    }
    pub fn flip_lr(&mut self) {
        let img_copy = self.img.clone();
        for y in 0..DIM1 {
            for x in 0..DIM1 {
                let copy = img_copy.get(&(x,y)).unwrap();
                self.img.insert((DIM1-1-x,y),*copy);
            }
        }
        self.make_edges();
    }
    pub fn flip_tb(&mut self) {
        let img_copy = self.img.clone();
        for y in 0..DIM1 {
            for x in 0..DIM1 {
                let copy = img_copy.get(&(x,y)).unwrap();
                self.img.insert((x,DIM1-1-y),*copy);
            }
        }
        self.make_edges();
    }
    pub fn rotate_ccw(&mut self) {
        let img_copy = self.img.clone();
        for y in 0..DIM1 {
            for x in 0..DIM1 {
                self.img.insert((y,x),*img_copy.get(&(DIM1-1-x,y)).unwrap());
            }
        }
        self.make_edges();
    }
}
trait Reversed {
    fn reversed(&self) -> Self;
}
impl Reversed for String {
    fn reversed(&self) -> String {
        self.chars().rev().collect::<String>()
    }
}

fn map_extents<T>(map: &HashMap<(i64,i64),T>) -> (i64,i64,i64,i64) {
    let xmin = &map.keys().map(|&(x,_)| x).min().unwrap();
    let ymin = &map.keys().map(|&(_,y)| y).min().unwrap();
    let xmax = &map.keys().map(|&(x,_)| x).max().unwrap();
    let ymax = &map.keys().map(|&(_,y)| y).max().unwrap();
    (*xmin,*ymin,*xmax,*ymax)
}

fn bool_char(b: &bool) -> String {
    match b {
        true =>  "#".to_string(),
        false => ".".to_string(),
    }
}

fn day20(input: &str) -> io::Result<()> {
    let mut tiles = std::fs::read_to_string(input)
        .unwrap()
        .split("\n\n")
        .map(Tile::from)
        .collect::<Vec<_>>();

    let num_tiles = tiles.len();

    // Find neighbors
    for tile in 0..num_tiles {
        for other in 0..num_tiles {
            if tile == other { continue; }
            let mut matches = false;
            'outer: for edge in &tiles[tile].edges {
                for other_edge in &tiles[other].edges {
                    if edge == other_edge {
                        matches = true;
                        break 'outer;
                    }
                }
            }
            if matches {
                tiles[tile].neighbors.push(other);
                tiles[other].neighbors.push(tile);
            }
        }
    }

    // Dedup neighbors
    for tile in 0..num_tiles {
        tiles[tile].neighbors.sort();
        tiles[tile].neighbors.dedup();
    }

    // Part 1
    let part1: usize = tiles
        .iter()
        .filter(|tile| tile.neighbors.len() == 2)
        .map(|tile| tile.id)
        .product();
    println!("Part 1: {}", part1); // 27803643063307
  
    // This rotation was previously mixed in with other code
    // Now stuck with it since the rest of the built-in rotations
    // hinge on this.
    tiles[0].rotate_ccw();

    // Starting with tile 0, find all neighbors
    // place and orient them as appropriate
    let mut grid: HashMap<(i64,i64),Tile> = HashMap::new();
    let mut q: VecDeque<(usize,i64,i64)> = VecDeque::new();
    tiles[0].drawn = true;
    grid.insert((0,0),tiles[0].clone());
    q.push_back((0,0,0)); // (tile_id, x, y)
    while q.len() > 0 {
        let (t_id,x,y) = q.pop_front().unwrap();
        'neighbors: for neighbor_id in &tiles[t_id].neighbors.clone() {
            if tiles[*neighbor_id].drawn { continue 'neighbors; }
            
            // Edges of current tile (only actual edges, not reversed)
            for (eid,edge) in tiles[t_id].clone().edges[0..4].into_iter().enumerate() {
                
                // Match against all edges of neighboring tile, including reversed
                for (eid_other,other_edge) in tiles[*neighbor_id].clone().edges.iter().enumerate() {

                    // Found match
                    if edge == other_edge {
                        let newxy: (i64,i64);
                        match (eid,eid_other) {
                            (0,0) => { // top - matches top
                                newxy = (x,y-1);
                                tiles[*neighbor_id].flip_tb();
                            }, 
                            (0,1) => { // top - matches bottom
                                newxy = (x,y-1);
                            },
                            (0,2) => { // top - matches left
                                newxy = (x,y-1);
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (0,3) => { // top - matches right
                                newxy = (x,y-1);
                                tiles[*neighbor_id].flip_lr();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (0,4) => { // top - matches top reversed
                                newxy = (x,y-1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            }, 
                            (0,5) => { // top - matches bottom reversed
                                newxy = (x,y-1);
                                tiles[*neighbor_id].flip_lr();
                            },
                            (0,6) => { // top - matches left reversed
                                newxy = (x,y-1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].flip_lr();
                            },
                            (0,7) => { // top - matches right reversed
                                newxy = (x,y-1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (1,0) => { // bottom - matches top
                                newxy = (x,y+1);
                            },
                            (1,1) => { // bottom - matches bottom
                                newxy = (x,y+1);
                                tiles[*neighbor_id].flip_tb();
                            },
                            (1,2) => { // bottom - matches left
                                newxy = (x,y+1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].flip_lr();
                            },
                            (1,3) => { // bottom - matches right
                                newxy = (x,y+1);
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (1,4) => { // bottom - matches top reversed
                                newxy = (x,y+1);
                                tiles[*neighbor_id].flip_lr();
                            },
                            (1,5) => { // bottom - matches bottom reversed
                                newxy = (x,y+1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (1,6) => { // bottom - matches left reversed
                                newxy = (x,y+1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (1,7) => { // bottom - matches right reversed
                                newxy = (x,y+1);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].flip_lr();
                            },
                            (2,0) => { // left - matches top
                                newxy = (x-1,y);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (2,1) => { // left - matches bottom
                                newxy = (x-1,y);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].flip_tb();
                            },
                            (2,2) => { // left - matches left
                                newxy = (x-1,y);
                                tiles[*neighbor_id].flip_lr();
                            },
                            (2,3) => { // left - matches right
                                newxy = (x-1,y);
                            },
                            (2,4) => { // left - matches top reversed
                                newxy = (x-1,y);
                                //tiles[*neighbor_id].rotate_ccw();
                                //tiles[*neighbor_id].rotate_ccw();
                                //tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].flip_tb();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (2,5) => { // left - matches bottom reversed
                                newxy = (x-1,y);
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (2,6) => { // left - matches left reversed
                                newxy = (x-1,y);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (2,7) => { // left - matches right reversed
                                newxy = (x-1,y);
                                tiles[*neighbor_id].flip_tb();
                            },
                            (3,0) => { // right - matches top
                                newxy = (x+1,y);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].flip_tb();
                            },
                            (3,1) => { // right - matches bottom
                                newxy = (x+1,y);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (3,2) => { // right - matches left
                                newxy = (x+1,y);
                            },
                            (3,3) => { // right - matches right
                                newxy = (x+1,y);
                                tiles[*neighbor_id].flip_lr();
                            },
                            (3,4) => { // right - matches top reversed
                                newxy = (x+1,y);
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (3,5) => { // right - matches bottom reversed
                                newxy = (x+1,y);                               
                                tiles[*neighbor_id].flip_tb();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (3,6) => { // right - matches left reversed
                                newxy = (x+1,y);
                                tiles[*neighbor_id].flip_tb();
                            },
                            (3,7) => { // right - matches right reversed
                                newxy = (x+1,y);
                                tiles[*neighbor_id].rotate_ccw();
                                tiles[*neighbor_id].rotate_ccw();
                            },
                            (_,_) => panic!("Bad combination!"),
                        }
                        tiles[*neighbor_id].drawn = true;
                        grid.insert(newxy,tiles[*neighbor_id].clone());
                        q.push_back((*neighbor_id,newxy.0,newxy.1));
                    }
                }
            }
        }
    }

    // Print grid of tile IDs
    let (xmin,ymin,xmax,ymax) = map_extents(&grid);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            print!(" {} ", grid.get(&(x,y)).unwrap().id);
        }
        println!();
    }
    println!();

    // Build actual image (and print with tile IDs)
    let mut img: HashMap<(i64,i64),bool> = HashMap::new();
    let mut newx = 0;
    let mut newy = 0;
    for y in ymin..=ymax {
        //for y2 in 0..DIM1 {
        for y2 in 1..DIM2 {
            for x in xmin..=xmax {
                print!("  ");
                let t = grid.get(&(x,y)).unwrap();
                print!("{} ",t.id);
              //for x2 in 0..DIM1 {
                for x2 in 1..DIM2 {
                    print!("{}", bool_char(t.img.get(&(x2,y2)).unwrap()));
                    img.insert((newx,newy),*t.img.get(&(x2,y2)).unwrap());
                    newx += 1;
                }
            }
            newx = 0;
            newy += 1;
            println!();
        }
        println!();
    }

    // Display pre-oriented image
    println!("Final Image:");
    let (xmin,ymin,xmax,ymax) = map_extents(&img);
    println!("x=({},{}), y=({},{})",xmin,xmax,ymin,ymax);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            print!("{}", bool_char(img.get(&(x,y)).unwrap()));
        }
        println!();
    }

    // Display image in new non-final orientation
    println!();
    println!("Final Image rotated:");
    rotate_map_ccw(&mut img);
    flip_map_lr(&mut img);
    let (xmin,ymin,xmax,ymax) = map_extents(&img);
    println!("x=({},{}), y=({},{})",xmin,xmax,ymin,ymax);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            print!("{}", bool_char(img.get(&(x,y)).unwrap()));
        }
        println!();
    }

    // Orient map to find monsters
    rotate_map_ccw(&mut img);
    rotate_map_ccw(&mut img);
    rotate_map_ccw(&mut img);
    flip_map_lr(&mut img);

    // Count monsters
    let mut num_monsters = 0;
    const MONSTER_NUM: usize = 15;
    for y in 3..ymax {
        for x in 0..=xmax-19 {
            let monster_pts = [
                (x,y),(x+1,y+1),(x+4,y+1),(x+5,y),(x+6,y),(x+7,y+1),(x+10,y+1),
                (x+11,y),(x+12,y),(x+13,y+1),(x+16,y+1),(x+17,y),(x+18,y),(x+19,y),
                (x+18,y-1)
            ];
            if monster_pts.iter().map(|pt| img.get(&pt).unwrap()).filter(|t| **t).count() == MONSTER_NUM {
                num_monsters += 1;
            }
        }
    }

    // Count non-monster
    let hashes = img.iter().filter(|(_,v)| **v).count();
    println!("Hashes: {}", hashes);
    println!("Monsters: {}", num_monsters);

    // Part 2
    let part2 = hashes as i64 - (num_monsters*MONSTER_NUM as i64);
    println!("Part 2: {}", part2); // 1644

    Ok(())
}

fn flip_map_lr<T: Clone>(map: &mut HashMap<(i64,i64),T>) {
    let map_copy = map.clone();
    let (xmin,ymin,xmax,ymax) = map_extents(&map);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            map.insert((xmax-x,y),map_copy.get(&(x,y)).unwrap().clone());
        }
    }
}
fn flip_map_tb<T: Clone>(map: &mut HashMap<(i64,i64),T>) {
    let map_copy = map.clone();
    let (xmin,ymin,xmax,ymax) = map_extents(&map);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            map.insert((x,ymax-y),map_copy.get(&(x,y)).unwrap().clone());
        }
    }
}
fn rotate_map_ccw<T: Clone>(map: &mut HashMap<(i64,i64),T>) {
    let map_copy = map.clone();
    let (xmin,ymin,xmax,ymax) = map_extents(&map);
    for y in ymin..=ymax {
        for x in xmin..=xmax {
            map.insert((y,x),map_copy.get(&(xmax-x,y)).unwrap().clone());
        }
    }
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day20(&filename).unwrap();
}