Day 4: Ceres Search
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)
- You can send code in code blocks by using three backticks, the code, and then three backticks or use something such as https://topaz.github.io/paste/ if you prefer sending it through a URL
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
Part 1:
with open('input') as data: lines = [l.strip() for l in data.readlines()] # Remove empty line class Result(): def __init__(self): self.count = 0 def analyze_lines(lines: list[str]): ans.count += get_rights(lines) ans.count += get_ups(lines) ans.count += get_downs(lines) ans.count += get_down_rights(lines) ans.count += get_down_lefts(lines) ans.count += get_up_lefts(lines) ans.count += get_up_rights(lines) for line in lines: ans.count += get_lefts(line) def get_ups(lines: list[str]) -> int: up_count = 0 for i_l, line in enumerate(lines): result = "" if i_l < 3: continue for i_c, char in enumerate(line): if char == "X": result = char result += "".join([lines[i_l - n][i_c] for n in range(1, 4)]) if result == "XMAS": up_count += 1 else: result = "" return up_count def get_downs(lines: list[str]) -> int: down_count = 0 for i_l, l in enumerate(lines): result = "" for i_c, c in enumerate(l): if c == "X": result += c try: result += "".join([lines[i_l + n][i_c] for n in range(1, 4)]) except IndexError: result = "" continue finally: if result == "XMAS": down_count += 1 result = "" return down_count def get_lefts(line: str) -> int: left_count = 0 for i, char in enumerate(line): if i < 3: continue elif char == "X" and line[i-1] == "M" and line[i-2] == "A" and line[i-3] == "S": left_count += 1 return left_count def get_rights(lines: list[str]) -> int: right_counts = 0 for l in lines: right_counts += l.count("XMAS") return right_counts def get_down_rights(lines: list[str]) -> int: down_right_count = 0 for i_l, l in enumerate(lines): result = "" for i_c, c in enumerate(l): if c == "X": result += c try: result += "".join( [lines[i_l + n][i_c + n] for n in range(1,4)] ) except IndexError: result = "" continue finally: if result == "XMAS": down_right_count += 1 result = "" return down_right_count def get_down_lefts(lines: list[str]) -> int: down_left_count = 0 for i_l, l in enumerate(lines): result = "" for i_c, c in enumerate(l): if i_c < 3: continue if c == "X": result += c try: result += "".join( [lines[i_l + n][i_c - n] for n in range(1,4)] ) except IndexError: result = "" continue finally: if result == "XMAS": down_left_count += 1 result = "" return down_left_count def get_up_rights(lines: list[str]) -> int: up_right_count = 0 for i_l, l in enumerate(lines): result = "" if i_l < 3: continue for i_c, c in enumerate(l): if c == "X": result += c try: result += "".join( [lines[i_l - n][i_c + n] for n in range(1,4)] ) except IndexError: result = "" continue finally: if result == "XMAS": up_right_count += 1 result = "" return up_right_count def get_up_lefts(lines: list[str]) -> int: up_left_count = 0 for i_l, l in enumerate(lines): result = "" if i_l < 3: continue for i_c, c in enumerate(l): if i_c < 3: continue if c == "X": result = c try: result += "".join( [lines[i_l - n][i_c - n] for n in range(1,4)] ) except IndexError as e: result = "" continue finally: if result == "XMAS": up_left_count += 1 result = "" return up_left_count ans = Result() analyze_lines(lines) print(ans.count)
Part 2:
with open('input') as data: lines = list(filter(lambda x: x != '', [l.strip() for l in data.readlines()])) xmases = 0 for i in range(1, len(lines)): for j in range(1, len(lines[i])): if lines[i][j] == "A": try: up_back = lines[i-1][j-1] down_over = lines[i+1][j+1] up_over = lines[i-1][j+1] down_back = lines[i+1][j-1] except IndexError: continue else: if {up_back, down_over} == set("MS") and {up_over, down_back} == set("MS"): xmases += 1 print(xmases)
I actually found part two A LOT easier than part 1.
Haskell
Popular language this year :)
I got embarrassingly stuck on this one trying to be clever with list operations. Then I realized I should just use an array…
import Data.Array.Unboxed (UArray) import Data.Array.Unboxed qualified as A import Data.Bifunctor readInput :: String -> UArray (Int, Int) Char readInput s = let rows = lines s n = length rows in A.listArray ((1, 1), (n, n)) $ concat rows s1 `eq` s2 = s1 == s2 || s1 == reverse s2 part1 arr = length $ filter isXmas $ concatMap lines $ A.indices arr where isXmas ps = all (A.inRange $ A.bounds arr) ps && map (arr A.!) ps `eq` "XMAS" lines p = [take 4 $ iterate (bimap (+ di) (+ dj)) p | (di, dj) <- [(1, 0), (0, 1), (1, 1), (1, -1)]] part2 arr = length $ filter isXmas innerPoints where innerPoints = let ((i1, j1), (i2, j2)) = A.bounds arr in [(i, j) | i <- [i1 + 1 .. i2 - 1], j <- [j1 + 1 .. j2 - 1]] isXmas p = up p `eq` "MAS" && down p `eq` "MAS" up (i, j) = map (arr A.!) [(i + 1, j - 1), (i, j), (i - 1, j + 1)] down (i, j) = map (arr A.!) [(i - 1, j - 1), (i, j), (i + 1, j + 1)] main = do input <- readInput <$> readFile "input04" print $ part1 input print $ part2 input
Nim
Could be done more elegantly, but I haven’t bothered yet.
proc solve(input: string): AOCSolution[int, int] = var lines = input.splitLines() block p1: # horiz for line in lines: for i in 0..line.high-3: if line[i..i+3] in ["XMAS", "SAMX"]: inc result.part1 for y in 0..lines.high-3: #vert for x in 0..lines[0].high: let word = collect(for y in y..y+3: lines[y][x]) if word in [@"XMAS", @"SAMX"]: inc result.part1 #diag \ for x in 0..lines[0].high-3: let word = collect(for d in 0..3: lines[y+d][x+d]) if word in [@"XMAS", @"SAMX"]: inc result.part1 #diag / for x in 3..lines[0].high: let word = collect(for d in 0..3: lines[y+d][x-d]) if word in [@"XMAS", @"SAMX"]: inc result.part1 block p2: for y in 0..lines.high-2: for x in 0..lines[0].high-2: let diagNW = collect(for d in 0..2: lines[y+d][x+d]) let diagNE = collect(for d in 0..2: lines[y+d][x+2-d]) if diagNW in [@"MAS", @"SAM"] and diagNE in [@"MAS", @"SAM"]: inc result.part2
J
Unsurprisingly this is the kind of problem that J is really good at. The dyadic case (table) of the adverb
/
is doing all the heavy lifting here: it makes a higher rank tensor by traversing items of the specified rank on each side and combining them according to the remaining frame of each side’s shape. The hard part is arranging the arguments so that your resulting matrix has its axes in the correct order.data_file_name =: '4.data' NB. cutopen yields boxed lines, so unbox them and ravel items to make a letter matrix grid =: ,. > cutopen fread data_file_name NB. pad the grid on every side with #'XMAS' - 1 spaces hpadded_grid =: ((' ' & ,) @: (, & ' '))"1 grid padded_grid =: (3 1 $ ' ') , hpadded_grid , (3 1 $ ' ') NB. traversal vectors directions =: 8 2 $ 1 0 1 1 0 1 _1 1 _1 0 _1 _1 0 _1 1 _1 NB. rpos cpos matches rdir cdir if the string starting at rpos cpos in NB. direction rdir cdir is the string we want matches =: 4 : 0 */ ,'XMAS' -: padded_grid {~ <"1 x +"1 y *"1 0 i. 4 )"1 positions =: (3 + i. 0 { $ grid) ,"0/ (3 + i. 1 { $ grid) result1 =: +/, positions matches/ directions NB. pairs of traversal vectors x_directions =: 4 2 2 $ 1 1 _1 1 1 1 1 _1 _1 _1 _1 1 _1 _1 1 _1 NB. rpos cpos x_matches 2 2 $ rdir1 cdir1 rdir2 cdir2 if there is an 'A' at NB. rpos cpos and the string in each of dir1 and dir2 centered at rpos cpos NB. is the string we want x_matches =: 4 : 0 NB. (2 2 $ rdir1 cdir1 rdir2 cdir2) *"1 0/ (_1 + i.3) yields a matrix NB. 2 3 $ (_1 * dir1) , (0 * dir1) , (1 * dir1) followed by the same for dir2 */ ,'MAS' -:"1 padded_grid {~ <"1 x +"1 y *"1 0/ _1 + i. 3 )"1 2 result2 =: +/, positions x_matches/ x_directions
I struggled a lot more when doing list slices that I would’ve liked to
Haskell
import Data.List qualified as List collectDiagonal :: [String] -> Int -> Int -> String collectDiagonal c y x | length c > y && length (c !! y) > x = c !! y !! x : collectDiagonal c (y+1) (x+1) | otherwise = [] part1 c = do let forwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails) $ c let backwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse) $ c let downwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails ) . List.transpose $ c let upwardXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse ) . List.transpose $ c let leftSideDiagonals = map (\ y -> collectDiagonal c y 0) [0..length c] let leftTopDiagonals = map (\ x -> collectDiagonal c 0 x) [1..(length . List.head $ c)] let leftDiagonals = leftSideDiagonals ++ leftTopDiagonals let rightSideDiagonals = map (\ y -> collectDiagonal (map List.reverse c) y 0) [0..length c] let rightTopDiagonals = map (\ x -> collectDiagonal (map List.reverse c) 0 x) [1..(length . List.head $ c)] let rightDiagonals = rightSideDiagonals ++ rightTopDiagonals let diagonals = leftDiagonals ++ rightDiagonals let diagonalXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails) $ diagonals let reverseDiagonalXMAS = map (length . filter (List.isPrefixOf "XMAS") . List.tails . reverse) $ diagonals print . sum $ [sum forwardXMAS, sum backwardXMAS, sum downwardXMAS, sum upwardXMAS, sum diagonalXMAS, sum reverseDiagonalXMAS] return () getBlock h w c y x = map (take w . drop x) . take h . drop y $ c isXBlock b = do let diagonal1 = collectDiagonal b 0 0 let diagonal2 = collectDiagonal (map List.reverse b) 0 0 diagonal1 `elem` ["SAM", "MAS"] && diagonal2 `elem` ["SAM", "MAS"] part2 c = do let lineBlocks = List.map (getBlock 3 3 c) [0..length c - 1] let groupedBlocks = List.map (flip List.map [0..(length . head $ c) - 1]) lineBlocks print . sum . map (length . filter isXBlock) $ groupedBlocks return () main = do c <- lines <$> getContents part1 c part2 c return ()
Uiua
Just part1 for now as I need to walk the dog :-)
[edit] Part 2 now added, and a nicer approach than Part 1 in my opinion, if you’re able to keep that many dimensions straight in your head :-)
[edit 2] Tightened it up a bit more.
Grid ← ⊜∘⊸≠@\n "MMMSXXMASM\nMSAMXMSMSA\nAMXSXMAAMM\nMSAMASMSMX\nXMASAMXAMM\nXXAMMXXAMA\nSMSMSASXSS\nSAXAMASAAA\nMAMMMXMMMM\nMXMXAXMASX" ≡⍉⍉×⇡4¤[1_0 0_1 1_1 1_¯1] # Use core dirs to build sets of 4-offsets. ↯∞_2⇡△ Grid # Get all possible starting points. &p/+♭⊞(+∩(≍"XMAS")⇌.⬚@.⊡:Grid≡+¤) # Part 1. Join the two into a table, use to pick 4-elements, check, count. Diags ← [[¯. 1_1] [¯. 1_¯1]] BothMas ← /×≡(+∩(≍"MS")⇌.)⬚@.⊡≡+Diags¤¤ # True if both diags here are MAS. &p/+≡BothMas⊚="A"⟜¤Grid # Part 2. For all "A"s in grid, check diags, count where good.
I’m not even sure how to write most of these characters
The operators have all got ascii names you can type, and the formatter converts them to the symbols. It’s a bit odd but really worthwhile, as you get access to the powerful array handling functionality that made solving today’s challenges so much more straightforward than in other languages.
It looks quite functional indeed
Factor
spoiler
: get-input ( -- rows ) "vocab:aoc-2024/04/input.txt" utf8 file-lines ; : verticals ( rows -- lines ) [ dimension last [0..b) ] keep cols ; : slash-origins ( rows -- coords ) dimension [ first [0..b) [ 0 2array ] map ] [ first2 [ 1 - ] [ 1 (a..b] ] bi* [ 2array ] with map ] bi append ; : backslash-origins ( rows -- coords ) dimension first2 [ [0..b) [ 0 2array ] map ] [ 1 (a..b] [ 0 swap 2array ] map ] bi* append ; : slash ( rows origin -- line ) first2 [ 0 [a..b] ] [ pick dimension last [a..b) ] bi* zip swap matrix-nths ; : backslash ( rows origin -- line ) [ dup dimension ] dip first2 [ over first [a..b) ] [ pick last [a..b) ] bi* zip nip swap matrix-nths ; : slashes ( rows -- lines ) dup slash-origins [ slash ] with map ; : backslashes ( rows -- lines ) dup backslash-origins [ backslash ] with map ; : word-count ( line word -- n ) dupd [ reverse ] dip '[ _ subseq-indices length ] bi@ + ; : part1 ( -- n ) get-input { [ ] [ verticals ] [ slashes ] [ backslashes ] } cleave-array concat [ "XMAS" word-count ] map-sum ; : origin-adistances ( rows origins line-quot: ( rows origin -- line ) -- origin-adistances-assoc ) with zip-with "MAS" "SAM" [ '[ [ _ subseq-indices ] map-values ] ] bi@ bi append harvest-values [ [ 1 + ] map ] map-values ; inline : a-coords ( origin-adistances coord-quot: ( adistance -- row-delta col-delta ) -- coords ) '[ first2 [ @ 2array v+ ] with map ] map-concat ; inline : slash-a-coords ( rows -- coords ) dup slash-origins [ slash ] origin-adistances [ [ 0 swap - ] keep ] a-coords ; : backslash-a-coords ( rows -- coords ) dup backslash-origins [ backslash ] origin-adistances [ dup ] a-coords ; : part2 ( -- n ) get-input [ slash-a-coords ] [ backslash-a-coords ] bi intersect length ;
Better viewed on GitHub.
Haskell
import Control.Arrow import Data.Array.Unboxed import Data.List type Pos = (Int, Int) type Board = Array Pos Char data Dir = N | NE | E | SE | S | SW | W | NW target = "XMAS" parse s = listArray ((1, 1), (n, m)) [l !! i !! j | i <- [0 .. n - 1], j <- [0 .. m - 1]] where l = lines s (n, m) = (length $ head l, length l) move N = first pred move S = first succ move E = second pred move W = second succ move NW = move N . move W move SW = move S . move W move NE = move N . move E move SE = move S . move E check :: Board -> Pos -> Int -> Dir -> Bool check b p i d = i >= length target || ( inRange (bounds b) p && (b ! p) == (target !! i) && check b (move d p) (succ i) d ) checkAllDirs :: Board -> Pos -> Int checkAllDirs b p = length . filter (check b p 0) $ [N, NE, E, SE, S, SW, W, NW] check2 :: Board -> Pos -> Bool check2 b p = all (inRange (bounds b)) moves && ((b ! p) == 'A') && ("SSMM" `elem` rotations) where rotations = rots $ (b !) <$> moves moves = flip move p <$> [NE, SE, SW, NW] rots xs = init $ zipWith (++) (tails xs) (inits xs) part1 b = sum $ checkAllDirs b <$> indices b part2 b = length . filter (check2 b) $ indices b main = getContents >>= print . (part1 &&& part2) . parse
python
solution
import aoc def setup(): return (aoc.get_lines(4, padded=(True, '.', 3)), 0) def one(): lines, acc = setup() for row, l in enumerate(lines): for col, c in enumerate(l): if c == 'X': w = l[col - 3:col + 1] e = l[col:col + 4] n = c + lines[row - 1][col] + \ lines[row - 2][col] + lines[row - 3][col] s = c + lines[row + 1][col] + \ lines[row + 2][col] + lines[row + 3][col] nw = c + lines[row - 1][col - 1] + \ lines[row - 2][col - 2] + lines[row - 3][col - 3] ne = c + lines[row - 1][col + 1] + \ lines[row - 2][col + 2] + lines[row - 3][col + 3] sw = c + lines[row + 1][col - 1] + \ lines[row + 2][col - 2] + lines[row + 3][col - 3] se = c + lines[row + 1][col + 1] + \ lines[row + 2][col + 2] + lines[row + 3][col + 3] for word in [w, e, n, s, nw, ne, sw, se]: if word in ['XMAS', 'SAMX']: acc += 1 print(acc) def two(): lines, acc = setup() for row, l in enumerate(lines): for col, c in enumerate(l): if c == 'A': l = lines[row - 1][col - 1] + c + lines[row + 1][col + 1] r = lines[row + 1][col - 1] + c + lines[row - 1][col + 1] if l in ['MAS', 'SAM'] and r in ['MAS', 'SAM']: acc += 1 print(acc) one() two()
Rust
I had a hunch about part two that didn’t pay off, so I over-coded this instead of just using an array of arrays.
use std::{fs, str::FromStr}; use color_eyre::eyre::{Report, Result}; #[derive(Debug, Copy, Clone)] enum Direction { N, NE, E, SE, S, SW, W, NW, } impl Direction { fn all() -> &'static [Direction] { &[ Direction::N, Direction::NE, Direction::E, Direction::SE, Direction::S, Direction::SW, Direction::W, Direction::NW, ] } } #[derive(Debug, PartialEq, Eq)] struct WordSearch { grid: Vec<char>, width: usize, height: usize, } impl FromStr for WordSearch { type Err = Report; fn from_str(s: &str) -> Result<Self, Self::Err> { let grid: Vec<_> = s.chars().filter(|&ch| ch != '\n').collect(); let width = s .chars() .position(|ch| ch == '\n') .ok_or_else(|| Report::msg("grid width cannot be zero, or one line"))?; let height = grid.len() / width; Ok(Self { grid, width, height, }) } } impl WordSearch { fn neighbour(&self, i: usize, dir: Direction) -> Option<usize> { let width = self.width; let length = self.grid.len(); use Direction::*; match dir { N if i >= width => Some(i - width), NE if i >= width && i % width != width - 1 => Some(i - width + 1), E if i % width != width - 1 => Some(i + 1), SE if i + width + 1 < length && i % width != width - 1 => Some(i + width + 1), S if i + width < length => Some(i + width), SW if i + width - 1 < length && i % width != 0 => Some(i + width - 1), W if i % width != 0 => Some(i - 1), NW if i >= width && i % width != 0 => Some(i - width - 1), _ => None, } } fn word_count(&self, word: &str) -> Result<usize> { let mut found = 0; for i in 0..self.grid.len() { for dir in Direction::all() { if self.word_present(word, i, *dir) { found += 1; } } } Ok(found) } fn x_count(&self) -> Result<usize> { let mut found = 0; for i in 0..self.grid.len() { if self.x_present(i) { found += 1; } } Ok(found) } fn word_present(&self, word: &str, location: usize, dir: Direction) -> bool { let mut next = Some(location); for ch in word.chars() { let i = if let Some(i) = next { i } else { // Off the edge return false; }; if self.grid[i] != ch { return false; } next = self.neighbour(i, dir); } true } fn x_present(&self, location: usize) -> bool { if self.grid.get(location) != Some(&'A') { return false; } let diags = [ (Direction::NE, Direction::SW), (Direction::NW, Direction::SE), ]; diags.iter().all(|(dir_a, dir_b)| { let Some(a_idx) = self.neighbour(location, *dir_a) else { return false; }; let Some(b_idx) = self.neighbour(location, *dir_b) else { return false; }; let a = self.grid[a_idx]; let b = self.grid[b_idx]; (a == 'M' && b == 'S') || (b == 'M' && a == 'S') }) } } fn part1(filepath: &str) -> Result<usize> { let input = fs::read_to_string(filepath)?; let grid = WordSearch::from_str(&input)?; grid.word_count("XMAS") } fn part2(filepath: &str) -> Result<usize> { let input = fs::read_to_string(filepath)?; let grid = WordSearch::from_str(&input)?; grid.x_count() } fn main() -> Result<()> { color_eyre::install()?; println!("Part 1: {}", part1("d04/input.txt")?); println!("Part 2: {}", part2("d04/input.txt")?); Ok(()) }
Nim
import ../aoc, strutils type Cell* = tuple[x,y:int] #the 8 grid direction const directions : array[8, Cell] = [ (1, 0), (-1, 0), (0, 1), ( 0,-1), (1, 1), (-1,-1), (1,-1), (-1, 1) ] const xmas = "XMAS" #part 1 proc searchXMAS*(grid:seq[string], x,y:int):int = #search in all 8 directions (provided we can find a full match in that direction) let w = grid[0].len let h = grid.len for dir in directions: # check if XMAS can even fit let xEnd = x + dir.x * 3 let yEnd = y + dir.y * 3 if xEnd < 0 or xEnd >= w or yEnd < 0 or yEnd >= h: continue; #step along direction var matches = 0 for s in 0..3: if grid[y + dir.y * s][x + dir.x * s] == xmas[s]: inc matches if matches == xmas.len: inc result #part 2 proc isMAS(grid:seq[string], c, o:Cell):bool= let ca : Cell = (c.x+o.x, c.y+o.y) let cb : Cell = (c.x-o.x, c.y-o.y) let a = grid[ca.y][ca.x] let b = grid[cb.y][cb.x] (a == 'M' and b == 'S') or (a == 'S' and b == 'M') proc searchCrossMAS*(grid:seq[string], x,y:int):bool = grid[y][x] == 'A' and grid.isMAS((x,y), (1,1)) and grid.isMAS((x,y), (1,-1)) proc solve*(input:string): array[2,int] = let grid = input.splitLines let w = grid[0].len let h = grid.len #part 1 for y in 0..<h: for x in 0..<w: result[0] += grid.searchXMAS(x, y) #part 2, skipping borders for y in 1..<h-1: for x in 1..<w-1: result[1] += (int)grid.searchCrossMAS(x, y)
Part 1 was done really quickly. Part 2 as well, but the result was not accepted…
Turns out +MAS isn’t actually a thing :P
C#
public class Day04 : Solver { private int width, height; private char[,] data; public void Presolve(string input) { var lines = input.Trim().Split("\n").ToList(); height = lines.Count; width = lines[0].Length; data = new char[height, width]; for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { data[i, j] = lines[i][j]; } } } private static readonly string word = "XMAS"; public string SolveFirst() { int counter = 0; for (int start_i = 0; start_i < height; start_i++) { for (int start_j = 0; start_j < width; start_j++) { if (data[start_i, start_j] != word[0]) continue; for (int di = -1; di <= 1; di++) { for (int dj = -1; dj <= 1; dj++) { if (di == 0 && dj == 0) continue; int end_i = start_i + di * (word.Length - 1); int end_j = start_j + dj * (word.Length - 1); if (end_i < 0 || end_j < 0 || end_i >= height || end_j >= width) continue; for (int k = 1; k < word.Length; k++) { if (data[start_i + di * k, start_j + dj * k] != word[k]) break; if (k == word.Length - 1) counter++; } } } } } return counter.ToString(); } public string SolveSecond() { int counter = 0; for (int start_i = 1; start_i < height - 1; start_i++) { for (int start_j = 1; start_j < width - 1; start_j++) { if (data[start_i, start_j] != 'A') continue; int even_mas_starts = 0; for (int di = -1; di <= 1; di++) { for (int dj = -1; dj <= 1; dj++) { if (di == 0 && dj == 0) continue; if ((di + dj) % 2 != 0) continue; if (data[start_i + di, start_j + dj] != 'M') continue; if (data[start_i - di, start_j - dj] != 'S') continue; even_mas_starts++; } } if (even_mas_starts == 2) counter++; } } return counter.ToString(); } }
Rust
Ugh. Spent way too long on today’s. Should have just used my own grid structure from last year. I will likely refactor to use that. Even though it’s likely a super slow implementation, the convenience of dealing with it is better than shoehorning in the
grid::Grid<T>
from that crate.solution (no supporting code)
use grid::Grid; use crate::shared::{ grid2d::{iter_diag_nesw, iter_diag_nwse, Point}, util::read_lines, }; fn parse_grid(input: &[String]) -> Grid<u8> { let cols = input.first().unwrap().len(); Grid::from_vec( input .iter() .flat_map(|row| row.chars().map(|c| c as u8).collect::<Vec<u8>>()) .collect(), cols, ) } fn part1(grid: &Grid<u8>) -> usize { let mut xmas_count = 0; let rows = grid .iter_rows() .map(|d| String::from_utf8(d.copied().collect()).unwrap()); let cols = grid .iter_cols() .map(|d| String::from_utf8(d.copied().collect()).unwrap()); for diag in iter_diag_nesw(grid) .chain(iter_diag_nwse(grid)) .filter_map(|d| { if d.len() >= 4 { Some(String::from_utf8(d.clone()).unwrap()) } else { None } }) .chain(rows) .chain(cols) { xmas_count += diag.matches("XMAS").count() + diag.matches("SAMX").count() } xmas_count } fn part2(grid: &Grid<u8>) -> usize { let mut xmas_count = 0; let valid = [ [b'M', b'M', b'S', b'S'], [b'M', b'S', b'S', b'M'], [b'S', b'M', b'M', b'S'], [b'S', b'S', b'M', b'M'], ]; for x in 1..grid.cols() - 1 { for y in 1..grid.rows() - 1 { if grid.get(y, x) == Some(&b'A') && valid.contains( &(Point::new(x as isize, y as isize) .diagonal_neighbors(grid) .map(|i| i.unwrap_or(0))), ) { xmas_count += 1; } } } xmas_count } pub fn solve() { let input = read_lines("inputs/day04.txt"); let grid = parse_grid(&input); println!("Part 1: {}", part1(&grid)); println!("Part 2: {}", part2(&grid)); }
And here’s a link to the Github if you care to see the gross supporting code :D
C
What can I say, bunch of for loops! I add a 3 cell border to avoid having to do bounds checking in the inner loops.
Code
#include "common.h" #define GZ 146 int main(int argc, char **argv) { static char g[GZ][GZ]; static const char w[] = "XMAS"; int p1=0,p2=0, x,y, m,i; if (argc > 1) DISCARD(freopen(argv[1], "r", stdin)); for (y=3; y<GZ && fgets(g[y]+3, GZ-3, stdin); y++) ; for (y=3; y<GZ-3; y++) for (x=3; x<GZ-3; x++) { for (m=1,i=0; i<4; i++) {m &= g[y+i][x]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y-i][x]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y][x+i]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y][x-i]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y+i][x+i]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y-i][x-i]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y+i][x-i]==w[i];} p1+=m; for (m=1,i=0; i<4; i++) {m &= g[y-i][x+i]==w[i];} p1+=m; p2 += g[y+1][x+1]=='A' && ((g[y][x] =='M' && g[y+2][x+2]=='S') || (g[y][x] =='S' && g[y+2][x+2]=='M')) && ((g[y+2][x]=='M' && g[y][x+2] =='S') || (g[y+2][x]=='S' && g[y][x+2] =='M')); } printf("04: %d %d\n", p1, p2); }
Uiua
This one was nice. The second part seemed quite daunting at first but wasn’t actually that hard in the end.
Run with example input here
Row ← ⌕ "XMAS" RevRow ← ⌕"SAMX" Sum ← /+/+ Count ← +∩Sum⊃Row RevRow PartOne ← ( &rs ∞ &fo "input-4.txt" ⊜∘≠@\n. ⊙+⟜∩Count⟜⍉ # horizontal and vertical search ⟜(/+⧈(Count⍉≡⬚@ ↻⇡⧻.)4) /+⧈(Count⍉≡⬚@ ↻¯⇡⧻.)4 ++ ) Mask ← °⊚×2⇡5 # Create variations of X-MAS Vars ← ( ["M S" " A " "M S"] ≡♭[∩⟜⍉]≡⇌. Mask ⊏0⊞▽¤ ) PartTwo ← ( &rs ∞ &fo "input-4.txt" ⊜∘≠@\n. ⧈(/+♭⊞≍⊙¤Vars▽Mask♭)3_3 Sum ) &p "Day 4:" &pf "Part 1: " &p PartOne &pf "Part 2: " &p PartTwo