10 votes

Day 20: Jurassic Jigsaw

Today's problem description: https://adventofcode.com/2020/day/20


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

10 comments

  1. PapaNachos
    (edited )
    Link
    Part A has some interesting tricks to it. Part B is uh... Part B will be interesting. Some of the shortcuts I used for part A definitely won't help with part B. Edit: I made a ton of progress on...

    Part A has some interesting tricks to it. Part B is uh... Part B will be interesting. Some of the shortcuts I used for part A definitely won't help with part B.

    Edit: I made a ton of progress on part B, but I've had a headache all day and this isn't helping. I'll probably come back to this one in the future. We'll see how I'm feeling later tonight

    Day 20 Part A – Python

    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)
    
    Tips and Commentary
    • For part A you only really need to care about the borders

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

    4 votes
  2. pnutzh4x0r
    Link
    Python Repo Link Part 1 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...

    Python

    Repo Link

    Part 1

    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()
    
    3 votes
  3. OrangeBacon
    Link
    I finally finished both parts of today's!!! woo! part 2 took a very long time lol, at least the program runs quickly. This was such a hard problem imo. Repo link:...

    I finally finished both parts of today's!!! woo! part 2 took a very long time lol, at least the program runs quickly.
    This was such a hard problem imo.
    Repo link: https://github.com/OrangeBacon/adventofcode2020/blob/main/src/days/day20.rs

    Notes: For part 1 only the edges of each tile needs to be considered, as each edge is included either once or twice, it is possible to get a single way of organising the tiles. To make the edge comparison nicer, the `#` can be replaced with `1` and `.` with `0` and then each edge can be converted to a binary number. To make the rotations easier, I read those numbers clockwise round the edge of each tile, rather than left to right. For this part, the image doesn't need to be constructed as the corners will be the tiles with two edges that are included twice. For part 2, the orientation of the image doesn't matter, so it can be started from any corner. The input is small enough that all rotations of each tile can be checked to find the correct rotation, rather than trying to find a clever way of working out the tile rotations. For finding the monster, I search through the complete image for one monster, if it is not found, i rotate the whole image, repeat for all 4 orientations, flip and repeat again, to find the one orientation and flip when one monster is found. I then search through the input for all monsters, keeping a set of all coordinates included in monsters and subtract the size of that set from the total number of `#` in the input.
    Rust part 1 + 2 (336 lines)
    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))
    }
    
    3 votes
  4. thorondir
    Link
    Well, damn. This was a tough one. The code isn't exactly clean, but it does work. Fair warning, the formatting is rather horrid, but I'm hoping the comments will make it more readable. Parts 1 and...

    Well, damn.
    This was a tough one.
    The code isn't exactly clean, but it does work.
    Fair warning, the formatting is rather horrid, but I'm hoping the comments will make it more readable.

    Parts 1 and 2
    #!/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()
    
    3 votes
  5. Gyrfalcon
    Link
    Well, I got part 1 much faster than I thought I would. Unfortunately, part 2 negates my shortcut for part 1, so I'll have to come back to this. Part 1 Ignoring the need to actually make the image...

    Well, I got part 1 much faster than I thought I would. Unfortunately, part 2 negates my shortcut for part 1, so I'll have to come back to this.

    Part 1

    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()
    
    2 votes
  6. wycy
    (edited )
    Link
    Rust Absolute mess, but finally got it. I'll clean this up some day, probably after AoC. Rust use std::env; use std::io; use std::collections::{HashMap,VecDeque}; #[macro_use] extern crate...

    Rust

    Absolute mess, but finally got it. I'll clean this up some day, probably after AoC.

    Rust
    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();
    }
    
    2 votes
  7. [3]
    wycy
    Link
    Question I'll only have a bit of time later tonight to work on this, so a question to help me speed things along later: Spoilers?Does anyone know if each tile edge will only match another tile...

    Question

    I'll only have a bit of time later tonight to work on this, so a question to help me speed things along later:

    Spoilers?Does anyone know if each tile edge will only match another tile edge exactly once when its in its correct orientation, or do you have to handle duplicates? In other words, can one tile edge match 1 other tile edge in one orientation, but when rotated/flipped it then correctly matches all 4 tiles around it?
    1 vote
    1. PapaNachos
      Link Parent
      Spoilers I don't know if it holds for part B yet, but at least for my data set that assumption held for what I considered important for part A.
      Spoilers

      I don't know if it holds for part B yet, but at least for my data set that assumption held for what I considered important for part A.

      3 votes
    2. thorondir
      Link Parent
      Edit to make it a spoiler. Spoiler? Yeah, I only ever checked "the new tile" against "the current tile", without also checking that other neighbours matched, and it works. I did some...
      Edit to make it a spoiler. Spoiler? Yeah, I only ever checked "the new tile" against "the current tile", without also checking that other neighbours matched, and it works. I did some sanity-checking to be sure, and it seems there are never more than two tiles that could match each other.
      2 votes
  8. leif
    Link
    This one was brutal—storing the tiles as sets of coordinates helped a lot.

    This one was brutal—storing the tiles as sets of coordinates helped a lot.

    1 vote