Day 13: Point of Incidence
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard
🔓 Unlocked
You must log in or register to comment.
Python
Also on Github
from .solver import Solver def is_mirrored_x(pattern: set[tuple[int, int]], max_x: int, max_y: int, x_mirror: int, desired_errors: int = 0) -> bool: min_x = max(0, 2 * x_mirror - max_x) max_x = min(max_x, 2 * x_mirror) errors = 0 for y in range(max_y): for x in range(min_x, x_mirror): mirrored = 2 * x_mirror - x - 1 if (x, y) in pattern and (mirrored, y) not in pattern: errors += 1 if (x, y) not in pattern and (mirrored, y) in pattern: errors += 1 if errors > desired_errors: return False return errors == desired_errors def is_mirrored_y(pattern: set[tuple[int, int]], max_x: int, max_y: int, y_mirror: int, desired_errors: int = 0) -> bool: min_y = max(0, 2 * y_mirror - max_y) max_y = min(max_y, 2 * y_mirror) errors = 0 for x in range(max_x): for y in range(min_y, y_mirror): mirrored = 2 * y_mirror - y - 1 if (x, y) in pattern and (x, mirrored) not in pattern: errors += 1 if (x, y) not in pattern and (x, mirrored) in pattern: errors += 1 if errors > desired_errors: return False return errors == desired_errors def find_mirror_axis(pattern: set[tuple[int, int]], max_x: int, max_y: int, desired_errors: int = 0) -> tuple[None, int]|tuple[int, None]: for possible_x_mirror in range(1, max_x): if is_mirrored_x(pattern, max_x, max_y, possible_x_mirror, desired_errors): return possible_x_mirror, None for possible_y_mirror in range(1, max_y): if is_mirrored_y(pattern, max_x, max_y, possible_y_mirror, desired_errors): return None, possible_y_mirror raise RuntimeError('No mirror axis found') class Day13(Solver): def __init__(self): super().__init__(13) self.patterns: list[set[tuple[int, int]]] = [] self.dimensions: list[tuple[int, int]] = [] def presolve(self, input: str): patterns = input.rstrip().split('\n\n') for pattern in patterns: lines = pattern.splitlines() points: set[tuple[int, int]] = set() max_x = 0 max_y = 0 for y, line in enumerate(lines): max_y = max(max_y, y) for x, char in enumerate(line): max_x = max(max_x, x) if char == '#': points.add((x, y)) self.patterns.append(points) self.dimensions.append((max_x + 1, max_y + 1)) def solve_first_star(self) -> int: sum = 0 for pattern, (max_x, max_y) in zip(self.patterns, self.dimensions, strict=True): mirror_x, mirror_y = find_mirror_axis(pattern, max_x, max_y) sum += (mirror_x or 0) + (mirror_y or 0) * 100 return sum def solve_second_star(self) -> int: sum = 0 for pattern, (max_x, max_y) in zip(self.patterns, self.dimensions, strict=True): mirror_x, mirror_y = find_mirror_axis(pattern, max_x, max_y, 1) sum += (mirror_x or 0) + (mirror_y or 0) * 100 return sum
Haskell
This was fun and (fairly) easy! Off-by-one errors are a likely source of bugs here.
import Control.Monad import Data.List import Data.List.Split import Data.Maybe score d pat = ((100 *) <$> search pat) `mplus` search (transpose pat) where search pat' = find ((d ==) . rdiff pat') [1 .. length pat' - 1] rdiff pat' i = let (a, b) = splitAt i pat' in length $ filter (uncurry (/=)) $ zip (concat $ reverse a) (concat b) main = do input <- splitOn [""] . lines <$> readFile "input13" let go d = print . sum . map (fromJust . score d) $ input go 0 go 1
Line-seconds score:
0.102
😉I decided to use string comparison for some reason, which meant part two wasn't as quick as it would have been.
use std::{cmp, fs, iter}; fn transpose(rows: &[&str]) -> Vec { (0..rows[0].len()) .map(|i| { let bytes: Vec<_> = (0..rows.len()).map(|j| rows[j].as_bytes()[i]).collect(); String::from_utf8(bytes).unwrap() }) .collect() } fn reflection_value(rows: &[&str]) -> Option { 'row_loop: for i in 0..(rows.len() - 1) { if rows[i] != rows[i + 1] { continue; } // we have an initial match let other_matches = cmp::min(i, rows.len() - 2 - i); for j in 1..=other_matches { if rows[i - j] != rows[i + 1 + j] { continue 'row_loop; } } return Some(i as u32 + 1); } None } fn summary(file_path: &str) -> u32 { fs::read_to_string(file_path) .expect("Can't read input file") .split("\n\n") .map(|s| { let rows: Vec<&str> = s.split('\n').collect(); if let Some(v) = reflection_value(&rows) { v * 100 } else { let cols_owned: Vec = transpose(&rows); let cols: Vec<&str> = cols_owned.iter().map(|s| s.as_str()).collect(); reflection_value(&cols).expect("No reflections found") } }) .sum() } fn str_diff(str1: &str, str2: &str) -> u32 { iter::zip(str1.chars(), str2.chars()) .map(|(s1, s2)| if s1 == s2 { 0 } else { 1 }) .sum() } fn smudged_reflection_value(rows: &[&str]) -> Option { for i in 0..(rows.len() - 1) { let num_cmps = cmp::min(i, rows.len() - 2 - i); let errs: u32 = (0..=num_cmps) .map(|j| str_diff(rows[i - j], rows[i + 1 + j])) .sum(); if errs != 1 { continue; } return Some(i as u32 + 1); } None } fn smudged_summary(file_path: &str) -> u32 { fs::read_to_string(file_path) .expect("Can't read input file") .split("\n\n") .map(|s| { let rows: Vec<&str> = s.split('\n').collect(); if let Some(v) = smudged_reflection_value(&rows) { v * 100 } else { let cols_owned: Vec = transpose(&rows); let cols: Vec<&str> = cols_owned.iter().map(|s| s.as_str()).collect(); smudged_reflection_value(&cols).expect("No reflections found") } }) .sum() } fn main() { println!(" normal: {}", summary("d13/input.txt")); println!("smudged: {}", smudged_summary("d13/input.txt")); }
C
Implementing part 1 with a bunch of for loops made me wonder about elegant NumPy solutions but then part 2 came along and it was a perfect fit! Just change a flag to a counter and remove the if-match-early-exit.
https://github.com/sjmulder/aoc/blob/master/2023/c/day13.c
int main() { static char g[32][32]; int p1=0,p2=0, w,h, x,y,i, nmis; while (!feof(stdin)) { for (h=0; ; h++) { assert(h < (int)LEN(*g)); if (!fgets(g[h], LEN(*g), stdin)) break; if (!g[h][0] || g[h][0]=='\n') break; } assert(h>0); w = strlen(g[0])-1; assert(w>0); for (x=1; x
Scala3
// i is like // # # # # # // 1 2 3 4 def smudgesAround(i: Int, s: List[List[Char]]): Long = val toEdge = math.min(i, s.size - i) (0 until toEdge).map(e => s(i - e - 1).lazyZip(s(i + e)).count(_ != _)).sum def symmetries(g: List[List[Char]], smudges: Int) = val rows = (1 until g.size).filter(smudgesAround(_, g) == smudges) val g2 = g.transpose val cols = (1 until g2.size).filter(smudgesAround(_, g2) == smudges) 100*rows.sum + cols.sum def task1(a: List[String]): Long = a.chunk(_ == "").map(g => symmetries(g.map(_.toList), 0)).sum def task2(a: List[String]): Long = a.chunk(_ == "").map(g => symmetries(g.map(_.toList), 1)).sum