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
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(); } }
I tried to think of some clever LINQ to do this one, but was blanking entirely.
So naïve search it is.
C#
string wordsearch = ""; int width; int height; public void Input(IEnumerable<string> lines) { wordsearch = string.Join("", lines); height = lines.Count(); width = lines.First().Length; } public void Part1() { int words = 0; for (int y = 0; y < height; y++) for (int x = 0; x < width; x++) words += SearchFrom(x, y); Console.WriteLine($"Words: {words}"); } public void Part2() { int words = 0; for (int y = 1; y < height - 1; y++) for (int x = 1; x < width - 1; x++) words += SearchCross(x, y); Console.WriteLine($"Crosses: {words}"); } public int SearchFrom(int x, int y) { char at = wordsearch[y * width + x]; if (at != 'X') return 0; int words = 0; for (int ydir = -1; ydir <= 1; ++ydir) for (int xdir = -1; xdir <= 1; ++xdir) { if (xdir == 0 && ydir == 0) continue; if (SearchWord(x, y, xdir, ydir)) words++; } return words; } private readonly string word = "XMAS"; public bool SearchWord(int x, int y, int xdir, int ydir) { int wordit = 0; while (true) { char at = wordsearch[y * width + x]; if (at != word[wordit]) return false; if (wordit == word.Length - 1) return true; wordit++; x += xdir; y += ydir; if (x < 0 || y < 0 || x >= width || y >= height) return false; } } public int SearchCross(int x, int y) { if (x == 0 || y == 0 || x == width - 1 || y == width - 1) return 0; char at = wordsearch[y * width + x]; if (at != 'A') return 0; int found = 0; for (int ydir = -1; ydir <= 1; ++ydir) for (int xdir = -1; xdir <= 1; ++xdir) { if (xdir == 0 || ydir == 0) continue; if (wordsearch[(y + ydir) * width + (x + xdir)] != 'M') continue; if (wordsearch[(y - ydir) * width + (x - xdir)] != 'S') continue; found++; } if (found == 2) return 1; return 0; }
I haven’t quite started yet, and this one does feel like a busy work kinda problem. I was wondering if I could write something to rotate the board and do the search, but I think that might be not worth the effort
Zig
const std = @import("std"); const List = std.ArrayList; const tokenizeScalar = std.mem.tokenizeScalar; const parseInt = std.fmt.parseInt; const print = std.debug.print; const eql = std.mem.eql; var gpa = std.heap.GeneralPurposeAllocator(.{}){}; const alloc = gpa.allocator(); const Point = struct { x: isize, y: isize, fn add(self: *const Point, point: *const Point) Point { return Point{ .x = self.x + point.x, .y = self.y + point.y }; } }; // note: i have no idea how to use this or if it's even possible // const DirectionType = enum(u8) { Up, Down, Left, Right, UpLeft, UpRight, DownLeft, DownRight }; // const Direction = union(DirectionType) { // up: Point = .{ .x = 0, .y = 0 }, // }; const AllDirections = [_]Point{ .{ .x = 0, .y = -1 }, // up .{ .x = 0, .y = 1 }, // down .{ .x = -1, .y = 0 }, // left .{ .x = 1, .y = 0 }, // right .{ .x = -1, .y = -1 }, // up left .{ .x = 1, .y = -1 }, // up right .{ .x = -1, .y = 1 }, // down left .{ .x = 1, .y = 1 }, // down right }; const Answer = struct { xmas: u32, mas: u32, }; pub fn searchXmas(letters: List([]const u8), search_char: u8, position: Point, direction: Point) u32 { const current_char = getChar(letters, position); if (current_char == search_char) { const next = position.add(&direction); if (current_char == 'M') { return searchXmas(letters, 'A', next, direction); } else if (current_char == 'A') { return searchXmas(letters, 'S', next, direction); } else if (current_char == 'S') { return 1; // found all letters } } return 0; } pub fn countXmas(letters: List([]const u8), starts: List(Point)) u32 { var counter: u32 = 0; for (starts.items) |start| { for (AllDirections) |direction| { const next = start.add(&direction); counter += searchXmas(letters, 'M', next, direction); } } return counter; } pub fn countMas(letters: List([]const u8), starts: List(Point)) u32 { var counter: u32 = 0; for (starts.items) |start| { const a_char = getChar(letters, start) orelse continue; const top_left_char = getChar(letters, start.add(&AllDirections[4])) orelse continue; const down_right_char = getChar(letters, start.add(&AllDirections[7])) orelse continue; const top_right_char = getChar(letters, start.add(&AllDirections[5])) orelse continue; const down_left_char = getChar(letters, start.add(&AllDirections[6])) orelse continue; const tldr = [3]u8{ top_left_char, a_char, down_right_char }; const trdl = [3]u8{ top_right_char, a_char, down_left_char }; if ((eql(u8, &tldr, "MAS") or eql(u8, &tldr, "SAM")) and (eql(u8, &trdl, "MAS") or eql(u8, &trdl, "SAM"))) { counter += 1; } } return counter; } pub fn getChar(letters: List([]const u8), point: Point) ?u8 { if (0 > point.x or point.x >= letters.items.len) { return null; } const row = @as(usize, @intCast(point.x)); if (0 > point.y or point.y >= letters.items[row].len) { return null; } const col = @as(usize, @intCast(point.y)); return letters.items[row][col]; } pub fn solve(input: []const u8) !Answer { var rows = tokenizeScalar(u8, input, '\n'); var letters = List([]const u8).init(alloc); defer letters.deinit(); var x_starts = List(Point).init(alloc); defer x_starts.deinit(); var a_starts = List(Point).init(alloc); defer a_starts.deinit(); var x: usize = 0; while (rows.next()) |row| { try letters.append(row); for (row, 0..) |letter, y| { if (letter == 'X') { try x_starts.append(.{ .x = @intCast(x), .y = @intCast(y) }); } else if (letter == 'A') { try a_starts.append(.{ .x = @intCast(x), .y = @intCast(y) }); } } x += 1; } // PART 1 const xmas = countXmas(letters, x_starts); // PART 2 const mas = countMas(letters, a_starts); return Answer{ .xmas = xmas, .mas = mas }; } pub fn main() !void { const answer = try solve(@embedFile("input.txt")); print("Part 1: {d}\n", .{answer.xmas}); print("Part 2: {d}\n", .{answer.mas}); } test "test input" { const answer = try solve(@embedFile("test.txt")); try std.testing.expectEqual(18, answer.xmas); }
Lisp
Not super happy with the code, but it got the job done.
Part 1 and 2
(defun p1-process-line (line) (to-symbols line)) (defun found-word-h (word data i j) "checks for a word existing from the point horizontally to the right" (loop for j2 from j for w in word when (not (eql w (aref data i j2))) return nil finally (return t))) (defun found-word-v (word data i j) "checks for a word existing from the point vertically down" (loop for i2 from i for w in word when (not (eql w (aref data i2 j))) return nil finally (return t))) (defun found-word-d-l (word data i j) "checks for a word existsing from the point diagonally to the left and down" (destructuring-bind (n m) (array-dimensions data) (declare (ignorable n)) (and (>= (- i (length word)) -1) (>= m (+ j (length word))) (loop for i2 from i downto 0 for j2 from j for w in word when (not (eql w (aref data i2 j2))) return nil finally (return t))))) (defun found-word-d-r (word data i j) "checks for a word existing from the point diagonally to the right and down" (destructuring-bind (n m) (array-dimensions data) (and (>= n (+ i (length word))) (>= m (+ j (length word))) (loop for i2 from i for j2 from j for w in word when (not (eql w (aref data i2 j2))) return nil finally (return t))) )) (defun count-word-h (data word) "Counts horizontal matches of the word" (let ((word-r (reverse word)) (word-l (length word))) (destructuring-bind (n m) (array-dimensions data) (loop for i from 0 below n sum (loop for j from 0 upto (- m word-l) count (found-word-h word data i j) count (found-word-h word-r data i j)))))) (defun count-word-v (data word) "Counts vertical matches of the word" (let ((word-r (reverse word)) (word-l (length word))) (destructuring-bind (n m) (array-dimensions data) (loop for j from 0 below m sum (loop for i from 0 upto (- n word-l) count (found-word-v word data i j) count (found-word-v word-r data i j)))))) (defun count-word-d (data word) "Counts diagonal matches of the word" (let ((word-r (reverse word))) (destructuring-bind (n m) (array-dimensions data) (loop for i from 0 below n sum (loop for j from 0 below m count (found-word-d-l word data i j) count (found-word-d-l word-r data i j) count (found-word-d-r word data i j) count (found-word-d-r word-r data i j) ))))) (defun run-p1 (file) "cares about the word xmas in any direction" (let ((word '(X M A S)) (data (list-to-2d-array (read-file file #'p1-process-line)))) (+ (count-word-v data word) (count-word-h data word) (count-word-d data word)))) (defun run-p2 (file) "cares about an x of mas crossed with mas" (let ((word '(M A S)) (word-r '(S A M)) (data (list-to-2d-array (read-file file #'p1-process-line)))) (destructuring-bind (n m) (array-dimensions data) (loop for i from 0 below (- n 2) sum (loop for j from 0 below (- m 2) count (and (found-word-d-r word data i j) (found-word-d-l word data (+ i 2) j)) count (and (found-word-d-r word-r data i j) (found-word-d-l word data (+ i 2) j)) count (and (found-word-d-r word data i j) (found-word-d-l word-r data (+ i 2) j)) count (and (found-word-d-r word-r data i j) (found-word-d-l word-r data (+ i 2) j)) )))))
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
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 ()
Rust
One of those with running through tricky grid indices. The vector types from the euclid crate helped in dealing with positions.
Code
use euclid::{vec2, default::*}; fn count_xmas(grid: &[&[u8]], pos: (usize, usize)) -> u32 { if grid[pos.1][pos.0] != b'X' { return 0 } let bounds = Rect::new(Point2D::origin(), Size2D::new(grid[0].len() as i32, grid.len() as i32)); const DIRS: [Vector2D<i32>; 8] = [ vec2(1, 0), vec2(-1, 0), vec2(0, 1), vec2(0, -1), vec2(1, 1), vec2(1, -1), vec2(-1, 1), vec2(-1, -1), ]; let mut count = 0; for dir in DIRS { let mut cur = Point2D::from(pos).to_i32(); let mut found = true; for letter in [b'M', b'A', b'S'] { cur += dir; if !bounds.contains(cur) || grid[cur.y as usize][cur.x as usize] != letter { found = false; break } } if found { count += 1; } } count } fn part1(input: String) { let grid = input.lines().map(|l| l.as_bytes()).collect::<Vec<_>>(); let count = (0..grid.len()).map(|y| { (0..grid[y].len()).map(|x| count_xmas(&grid, (x, y))).sum::<u32>() }) .sum::<u32>(); println!("{count}"); } fn is_x_mas(grid: &[&[u8]], pos: (usize, usize)) -> bool { if grid[pos.1][pos.0] != b'A' { return false } const DIRS: [Vector2D<i32>; 4] = [vec2(1, -1), vec2(1, 1), vec2(-1, 1), vec2(-1, -1)]; let pos = Point2D::from(pos).to_i32(); (0..4).any(|d| { let m_pos = [pos + DIRS[d], pos + DIRS[(d + 1) % 4]]; // 2 adjacent positions of M let s_pos = [pos + DIRS[(d + 2) % 4], pos + DIRS[(d + 3) % 4]]; // others S m_pos.iter().all(|p| grid[p.y as usize][p.x as usize] == b'M') && s_pos.iter().all(|p| grid[p.y as usize][p.x as usize] == b'S') }) } fn part2(input: String) { let grid = input.lines().map(|l| l.as_bytes()).collect::<Vec<_>>(); let count = (1..grid.len() - 1).map(|y| { (1..grid[y].len() - 1).filter(|&x| is_x_mas(&grid, (x, y))).count() }) .sum::<usize>(); println!("{count}"); } util::aoc_main!();
(also on github)
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()
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); }
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
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
C#
namespace Day04; static class Program { public record struct Point(int Row, int Col); static void Main(string[] args) { var sample = File.ReadAllLines("sample.txt"); var data = File.ReadAllLines("data.txt"); Console.WriteLine($"Part 1 (sample): {SolvePart1(sample)}"); Console.WriteLine($"Part 1 (data): {SolvePart1(data)}"); Console.WriteLine($"Part 2 (sample): {SolvePart2(sample)}"); Console.WriteLine($"Part 2 (data): {SolvePart2(data)}"); } private static readonly string Search = "XMAS"; private static readonly Func<Point, Point>[] DirectionalMoves = { p => new Point(p.Row + 1, p.Col), p => new Point(p.Row + 1, p.Col + 1), p => new Point(p.Row, p.Col + 1), p => new Point(p.Row - 1, p.Col + 1), p => new Point(p.Row - 1, p.Col), p => new Point(p.Row - 1, p.Col - 1), p => new Point(p.Row, p.Col - 1), p => new Point(p.Row + 1, p.Col - 1), }; private static readonly Func<Point, Point>[] ForwardSlashMoves = { p => new Point(p.Row - 1, p.Col - 1), p => new Point(p.Row + 1, p.Col + 1), }; private static readonly Func<Point, Point>[] BackSlashMoves = { p => new Point(p.Row + 1, p.Col - 1), p => new Point(p.Row - 1, p.Col + 1), }; static long SolvePart1(string[] data) { return Enumerable .Range(0, data.Length) .SelectMany(row => Enumerable.Range(0, data[row].Length) .Select(col => new Point(row, col))) .Where(p => IsMatch(data, p, Search[0])) .Sum(p => DirectionalMoves .Count(move => DeepMatch(data, move(p), move, Search, 1))); } static long SolvePart2(string[] data) { return Enumerable .Range(0, data.Length) .SelectMany(row => Enumerable.Range(0, data[row].Length) .Select(col => new Point(row, col))) .Where(p => IsMatch(data, p, 'A')) .Count(p => CheckDiagonalMoves(data, p, ForwardSlashMoves) && CheckDiagonalMoves(data, p, BackSlashMoves)); } static bool CheckDiagonalMoves(string[] data, Point p, Func<Point, Point>[] moves) => (IsMatch(data, moves[0](p), 'S') && IsMatch(data, moves[1](p), 'M')) || (IsMatch(data, moves[0](p), 'M') && IsMatch(data, moves[1](p), 'S')); static bool DeepMatch(string[] data, Point p, Func<Point, Point> move, string search, int searchIndex) => (searchIndex >= search.Length) ? true : (!IsMatch(data, p, search[searchIndex])) ? false : DeepMatch(data, move(p), move, search, searchIndex + 1); static bool IsMatch(string[] data, Point p, char searchChar) => IsInBounds(data, p) && (data[p.Row][p.Col] == searchChar); static bool IsInBounds(string[] data, Point p) => (p.Row >= 0) && (p.Col >= 0) && (p.Row < data.Length) && (p.Col < data[0].Length); }