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
Rust
Blunt force grid navigation https://gitlab.com/landreville/advent-of-code-2024/-/blob/main/src/bin/04.rs
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
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
Julia
Had some time to clean up the code today since the solution was quite straight forward after making a plan on how to approach it.
spoiler
function readWordSearch(inputFile::String)::Matrix{Char} f = open(inputFile,"r") lines::Vector{String} = readlines(f) close(f) wordSearch = Matrix{Char}(undef,length(lines),length(lines)) for (i,line) in enumerate(lines) wordSearch[i,:] = collect(line) end return wordSearch end function countXMASAppearances(wS::Matrix{Char})::Int appearanceCount::Int = 0 for i=1 : size(wS)[1] #lines for j=1 : size(wS)[2] #columns wS[i,j]!='X' ? continue : nothing #continue if char is not X #if char is X, check surrounding area # check horizontals #left j>=4 ? (wS[i,j-1]*wS[i,j-2]*wS[i,j-3]=="MAS" ? appearanceCount+=1 : nothing) : nothing #right j<=size(wS)[2]-3 ? (wS[i,j+1]*wS[i,j+2]*wS[i,j+3]=="MAS" ? appearanceCount+=1 : nothing) : nothing # check verticals #up i>=4 ? (wS[i-1,j]*wS[i-2,j]*wS[i-3,j]=="MAS" ? appearanceCount+=1 : nothing) : nothing #down i<=size(wS)[1]-3 ? (wS[i+1,j]*wS[i+2,j]*wS[i+3,j]=="MAS" ? appearanceCount+=1 : nothing) : nothing # check diagonals #left up i>=4 && j>=4 ? (wS[i-1,j-1]*wS[i-2,j-2]*wS[i-3,j-3]=="MAS" ? appearanceCount+=1 : nothing) : nothing #right up i>=4 && j<=size(wS)[2]-3 ? (wS[i-1,j+1]*wS[i-2,j+2]*wS[i-3,j+3]=="MAS" ? appearanceCount+=1 : nothing) : nothing #left down i<=size(wS)[1]-3 && j>=4 ? (wS[i+1,j-1]*wS[i+2,j-2]*wS[i+3,j-3]=="MAS" ? appearanceCount+=1 : nothing) : nothing #right down i<=size(wS)[1]-3 && j<=size(wS)[2]-3 ? (wS[i+1,j+1]*wS[i+2,j+2]*wS[i+3,j+3]=="MAS" ? appearanceCount+=1 : nothing) : nothing end end return appearanceCount end function countX_MASAppearances(wordSearch::Matrix{Char})::Int appearances::Int = 0 for l=2 : size(wordSearch)[1]-1 for c=2 : size(wordSearch)[2]-1 wordSearch[l,c]!='A' ? continue : nothing checkArr = [wordSearch[l-1,c-1],wordSearch[l-1,c+1],wordSearch[l+1,c-1],wordSearch[l+1,c+1]] if checkArr in [['M','M','S','S'],['M','S','M','S'],['S','S','M','M'],['S','M','S','M']] appearances += 1 end end end return appearances end wordSearch::Matrix{Char} = readWordSearch(inputFile prinltn("part 1 appearances: $(countXMASAppearances(wordSearch))") prinltn("part 2 appearances: $(countX_MASAppearances(wordSearch))")
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 ( dimension -- coords ) [ first [0..b) [ 0 2array ] map ] [ first2 [ 1 - ] [ 1 (a..b] ] bi* [ 2array ] with map ] bi append ; : backslash-origins ( dimension -- coords ) 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 dimension slash-origins [ slash ] with map ; : backslashes ( rows -- lines ) dup dimension 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 dimension slash-origins [ slash ] origin-adistances [ [ 0 swap - ] keep ] a-coords ; : backslash-a-coords ( rows -- coords ) dup dimension 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.
Python
<spoiler title>
def read_input(path): with open(path) as f: lines = f.readlines() for i, line in enumerate(lines): ln = line.replace("\n","") lines[i] = ln return lines def find_X(lines): Xes = [] for j, line in enumerate(lines): ind = [i for i, ltr in enumerate(line) if ltr == "X"] for i in ind: Xes.append((j,i)) return Xes def find_M(lines, x, dim): # Check for Ms M_dirs = [] for i in [-1, 0, 1]: x_ind = x[0] + i if x_ind>=0 and x_ind<dim: for j in [-1, 0, 1]: y_ind = x[1]+j if y_ind>=0 and y_ind<dim: if lines[x_ind][y_ind] == "M": M = [(x_ind, y_ind), (i,j)] M_dirs.append(M) return M_dirs def check_surroundings(loc, lines, check_char, direction): max = len(lines)-1 check_lock = [loc[i]+direction[i] for i in range(len(loc))] if all(i>=0 and i<=max for i in check_lock) and check_char in str(lines[check_lock[0]][check_lock[1]]): return True else: return False def part_one(lines): ans = 0 X = find_X(lines) dim = len(lines[0]) for x in X: M = find_M(lines, x, dim) for m in M: loc = m[0] dir = m[1] if not check_surroundings(loc, lines, 'A', dir): continue loc = [loc[0]+dir[0], loc[1]+dir[1]] if not all(i>=0 and i<=dim-1 for i in loc): continue if not check_surroundings(loc, lines, 'S', dir): continue ans+=1 return ans def extract_square(lines, loc): str = "" for i in range(-1,2,1): for j in range(-1,2,1): x_ind = loc[0]+i y_ind = loc[1]+j if not all(p>=0 and p<=len(lines[0])-1 for p in [x_ind, y_ind]): raise ValueError("The given lock is at the edge of the grid and therefore will not produce a square") str += lines[x_ind][y_ind] return str def check_square(square): if not square[4]=="A": return False elif not ((square[0]=="M" and square[8]=="S") or (square[0]=="S" and square[8]=="M")): return False elif not ((square[2]=="M" and square[6]=="S") or (square[2]=="S" and square[6]=="M")): return False else: return True def part_two(lines): ans = 0 dim = len(lines[0]) for i in range(1,dim-1): for j in range(1,dim-1): square = extract_square(lines, (i,j)) if check_square(square): ans += 1 return ans path = r'Day_4\input.txt' lines = read_input(path) print("Answer part 1: ", part_one(lines)) print("Answer part 2: ", part_two(lines))
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
This one was a little bit of a pain. I loved it.
TypeScript
Solution
import { AdventOfCodeSolutionFunction } from "./solutions"; enum Direction { UP, UP_RIGHT, RIGHT, BOTTOM_RIGHT, BOTTOM, BOTTOM_LEFT, LEFT, UP_LEFT, }; const ALL_DIRECTIONS = [ Direction.RIGHT, Direction.BOTTOM_RIGHT, Direction.BOTTOM, Direction.BOTTOM_LEFT, Direction.LEFT, Direction.UP_LEFT, Direction.UP, Direction.UP_RIGHT, ]; const check_coords = (grid: Array<Array<string>>, x: number, y: number) => { return y >= grid.length || y < 0 || x >= grid[y].length || x < 0 } const search_direction = (grid: Array<Array<string>>, x: number, y: number, direction: Direction, find: Array<string>) => { // exit conditions // no more to find if (find.length == 0) return 1; // found the end // invalid coords if (check_coords(grid, x, y)) return 0; // make new mutable list const newFind = [...find]; const searchChar = newFind.shift(); // wrong character if (grid[y][x] !== searchChar) return 0; switch (direction) { case Direction.UP: return search_direction(grid, x, y + 1, direction, newFind); case Direction.UP_RIGHT: return search_direction(grid, x + 1, y + 1, direction, newFind); case Direction.RIGHT: return search_direction(grid, x + 1, y, direction, newFind); case Direction.BOTTOM_RIGHT: return search_direction(grid, x + 1, y - 1, direction, newFind); case Direction.BOTTOM: return search_direction(grid, x, y - 1, direction, newFind); case Direction.BOTTOM_LEFT: return search_direction(grid, x - 1, y - 1, direction, newFind); case Direction.LEFT: return search_direction(grid, x - 1, y, direction, newFind); case Direction.UP_LEFT: return search_direction(grid, x - 1, y + 1, direction, newFind); default: return 0; } } const part_1_search = (grid: Array<Array<string>>, x: number, y: number, find: Array<string>) => { return ALL_DIRECTIONS.reduce<number>( (instances, direction) => instances + search_direction(grid, x, y, direction, find), 0 ); } const part_2_search = (grid: Array<Array<string>>, x: number, y: number, find: Array<string>) => { return ( search_direction(grid, x - 1, y + 1, Direction.BOTTOM_RIGHT, find) + search_direction(grid, x + 1, y + 1, Direction.BOTTOM_LEFT, find) + search_direction(grid, x - 1, y - 1, Direction.UP_RIGHT, find) + search_direction(grid, x + 1, y - 1, Direction.UP_LEFT, find) ) == 2 ? 1 : 0; } export const solution_4: AdventOfCodeSolutionFunction = (input) => { const grid = input.split("\n").map(st => st.trim()).map(v => v.split("")); let part_1 = 0; let part_2 = 0; const find_1 = "XMAS".split(""); const find_2 = "MAS".split(""); for (let y = 0; y < grid.length; y++) { for (let x = 0; x < grid[y].length; x++) { part_1 += part_1_search(grid, x, y, find_1); part_2 += part_2_search(grid, x, y, find_2); } } return { part_1, part_2, }; }
Felt like this code quality is better than what I usually output :)
Go
Just a bunch of ifs and bounds checking. Part 2 was actually simpler.
Code
func part1(W [][]rune) { m := len(W) n := len(W[0]) xmasCount := 0 for i := 0; i < m; i++ { for j := 0; j < n; j++ { if W[i][j] != 'X' { continue } if j < n-3 && W[i][j+1] == 'M' && W[i][j+2] == 'A' && W[i][j+3] == 'S' { // Horizontal left to right xmasCount++ } if j >= 3 && W[i][j-1] == 'M' && W[i][j-2] == 'A' && W[i][j-3] == 'S' { // Horizontal right to left xmasCount++ } if i < m-3 && W[i+1][j] == 'M' && W[i+2][j] == 'A' && W[i+3][j] == 'S' { // Vertical up to down xmasCount++ } if i >= 3 && W[i-1][j] == 'M' && W[i-2][j] == 'A' && W[i-3][j] == 'S' { // Vertical down to up xmasCount++ } if j < n-3 && i < m-3 && W[i+1][j+1] == 'M' && W[i+2][j+2] == 'A' && W[i+3][j+3] == 'S' { // Diagonal left to right and up to down xmasCount++ } if j >= 3 && i < m-3 && W[i+1][j-1] == 'M' && W[i+2][j-2] == 'A' && W[i+3][j-3] == 'S' { // Diagonal right to left and up to down xmasCount++ } if j < n-3 && i >= 3 && W[i-1][j+1] == 'M' && W[i-2][j+2] == 'A' && W[i-3][j+3] == 'S' { // Diagonal left to right and down to up xmasCount++ } if j >= 3 && i >= 3 && W[i-1][j-1] == 'M' && W[i-2][j-2] == 'A' && W[i-3][j-3] == 'S' { // Diagonal right to left and down to up xmasCount++ } } } fmt.Println(xmasCount) } func part2(W [][]rune) { m := len(W) n := len(W[0]) xmasCount := 0 for i := 0; i <= m-3; i++ { for j := 0; j <= n-3; j++ { if W[i+1][j+1] != 'A' { continue } if W[i][j] == 'M' && W[i][j+2] == 'M' && W[i+2][j] == 'S' && W[i+2][j+2] == 'S' { xmasCount++ } else if W[i][j] == 'M' && W[i][j+2] == 'S' && W[i+2][j] == 'M' && W[i+2][j+2] == 'S' { xmasCount++ } else if W[i][j] == 'S' && W[i][j+2] == 'S' && W[i+2][j] == 'M' && W[i+2][j+2] == 'M' { xmasCount++ } else if W[i][j] == 'S' && W[i][j+2] == 'M' && W[i+2][j] == 'S' && W[i+2][j+2] == 'M' { xmasCount++ } } } fmt.Println(xmasCount) } func main() { file, _ := os.Open("input.txt") defer file.Close() scanner := bufio.NewScanner(file) var W [][]rune for scanner.Scan() { line := scanner.Text() W = append(W, []rune(line)) } part1(W) part2(W) }
Raku
Oof, my struggle to make custom index walking paths for part 1 did not pay off for part 2.
Solution
sub MAIN($input) { my $file = (open $input).slurp; my @grid is List = $file.lines».comb».list; my @transposedGrid is List = [Z] @grid; my @reversedGrid is List = @grid».reverse; my @transposedReversedGrid is List = @transposedGrid».reverse; my @horizontalScanRows is List = generateScanHorizontal(@grid); my @transposedHorizontalScanRows is List = generateScanHorizontal(@transposedGrid); my @part-one-counts = []; @part-one-counts.push(count-xmas(@grid, @horizontalScanRows)); # Right @part-one-counts.push(count-xmas(@transposedGrid, @transposedHorizontalScanRows)); # Down @part-one-counts.push(count-xmas(@reversedGrid, @horizontalScanRows)); # Left @part-one-counts.push(count-xmas(@transposedReversedGrid, @transposedHorizontalScanRows)); # Up my @diagonalScanRows is List = generateScanDiagonal(@grid); my @transposedDiagonalScanRows is List = generateScanDiagonal(@transposedGrid); @part-one-counts.push(count-xmas(@grid, @diagonalScanRows)); # Down Right @part-one-counts.push(count-xmas(@grid, @diagonalScanRows».reverse)); # Up Left @part-one-counts.push(count-xmas(@reversedGrid, @diagonalScanRows)); # Down Left @part-one-counts.push(count-xmas(@reversedGrid, @diagonalScanRows».reverse)); # Up Right my $part-one-solution = @part-one-counts.sum; say "part 1: $part-one-solution"; my @part-two-counts = []; @part-two-counts.push(countGridMatches(@grid, (<M . S>,<. A .>,<M . S>))); @part-two-counts.push(countGridMatches(@grid, (<S . S>,<. A .>,<M . M>))); @part-two-counts.push(countGridMatches(@grid, (<S . M>,<. A .>,<S . M>))); @part-two-counts.push(countGridMatches(@grid, (<M . M>,<. A .>,<S . S>))); my $part-two-solution = @part-two-counts.sum; say "part 2: $part-two-solution"; } sub count-xmas(@grid, @scanRows) { my $xmas-count = 0; for @scanRows -> @scanRow { my $xmas-pos = 0; for @scanRow -> @pos { my $char = @grid[@pos[0]][@pos[1]]; if "X" eq $char { $xmas-pos = 1; }elsif <X M A S>[$xmas-pos] eq $char { if $xmas-pos == 3 { $xmas-pos = 0; $xmas-count += 1; } else { $xmas-pos += 1; } } else { $xmas-pos = 0; } } } return $xmas-count; } sub generateScanHorizontal(@grid) { # Horizontal my $rows = @grid.elems; my $cols = @grid[0].elems; my @scanRows = (); for 0..^$rows -> $row { my @scanRow = (); for 0..^$cols -> $col { @scanRow.push(($row, $col)); } @scanRows.push(@scanRow); } return @scanRows.List».List; } sub generateScanDiagonal(@grid) { # Down-right diagonal my $rows = @grid.elems; my $cols = @grid[0].elems; my @scanRows = (); for 0..^($rows + $cols - 1) -> $diag { my @scanRow = (); my $starting-row = max(-$cols + $diag + 1, 0); my $starting-col = max($rows - $diag - 1, 0); my $diag-len = min($rows - $starting-row, $cols - $starting-col); for 0..^$diag-len -> $diag-pos { @scanRow.push(($starting-row + $diag-pos, $starting-col + $diag-pos)); } @scanRows.push(@scanRow); } return @scanRows.List».List; } sub countGridMatches(@grid, @needle) { my $count = 0; for 0..(@grid.elems - @needle.elems) -> $top { TOP-LEFT: for 0..(@grid[$top].elems - @needle[0].elems) -> $left { for 0..^@needle.elems -> $row-offset { for 0..^@needle[$row-offset].elems -> $col-offset { my $needle-char = @needle[$row-offset][$col-offset]; next if $needle-char eq "."; next TOP-LEFT if $needle-char ne @grid[$top+$row-offset][$left+$col-offset]; } } $count += 1; } } return $count; }
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); }
Kotlin
fun part1(input: String): Int { return countWordOccurrences(input.lines()) } fun part2(input: String): Int { val grid = input.lines().map(String::toList) var count = 0 for (row in 1..grid.size - 2) { for (col in 1..grid[row].size - 2) { if (grid[row][col] == 'A') { count += countCrossMatch(grid, row, col) } } } return count } private fun countCrossMatch(grid: List<List<Char>>, row: Int, col: Int): Int { val surroundingCorners = listOf( grid[row - 1][col - 1], // upper left grid[row - 1][col + 1], // upper right grid[row + 1][col - 1], // lower left grid[row + 1][col + 1], // lower right ) // no matches: // M S S M // A A // S M M S return if (surroundingCorners.count { it == 'M' } == 2 && surroundingCorners.count { it == 'S' } == 2 && surroundingCorners[0] != surroundingCorners[3] ) 1 else 0 } private fun countWordOccurrences(matrix: List<String>): Int { val rows = matrix.size val cols = if (rows > 0) matrix[0].length else 0 val directions = listOf( Pair(0, 1), // Horizontal right Pair(1, 0), // Vertical down Pair(1, 1), // Diagonal down-right Pair(1, -1), // Diagonal down-left Pair(0, -1), // Horizontal left Pair(-1, 0), // Vertical up Pair(-1, -1), // Diagonal up-left Pair(-1, 1) // Diagonal up-right ) fun isWordAt(row: Int, col: Int, word: String, direction: Pair<Int, Int>): Boolean { val (dx, dy) = direction for (i in word.indices) { val x = row + i * dx val y = col + i * dy if (x !in 0 until rows || y !in 0 until cols || matrix[x][y] != word[i]) { return false } } return true } var count = 0 for (row in 0 until rows) { for (col in 0 until cols) { for (direction in directions) { if (isWordAt(row, col, "XMAS", direction)) { count++ } } } } return count }
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
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
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); }