{"id":1122,"date":"2024-12-04T19:59:52","date_gmt":"2024-12-04T17:59:52","guid":{"rendered":"https:\/\/www.juustila.com\/antti\/?p=1122"},"modified":"2024-12-05T07:48:54","modified_gmt":"2024-12-05T05:48:54","slug":"advent-of-code-day-4-ceres-search","status":"publish","type":"post","link":"https:\/\/www.juustila.com\/antti\/2024\/12\/04\/advent-of-code-day-4-ceres-search\/","title":{"rendered":"Advent of Code Day 4 – Ceres Search"},"content":{"rendered":"\n

Today I got to reuse the Matrix<T><\/code> generic data structure I implemented last year. Input being a grid of characters like:<\/p>\n\n\n\n

MMMSXXMASM
MSAMXMSMSA
AMXSXMAAMM
MSAMASMSMX
XMASAMXAMM
XXAMMXXAMA
SMSMSASXSS
SAXAMASAAA
MAMMMXMMMM
MXMXAXMASX<\/pre>\n\n\n\n
The goal in part 1 of the puzzle was to find out how many times the word “XMAS” appears in the grid, whether it is written left-to-right, right-to-left or downwards or upwards. And<\/em> diagonally, from left to right and down, or from right to left and up, as well as from left to right and up, or from right to left and down.<\/p>\n\n\n\n
The Matrix implementation has an algorithm to rotate the matrix in steps of 90 degrees. So instead of traversing the grid in all those directions, I rotated it 90 degrees to find out the left-right-up-down and back occurrences of XMAS. After each rotation, I just searched let to right, covering the other directions using rotation<\/p>\n\n\n\n
The diagonals are handled in the same way, but in each rotation, I only handled the upper right half of the grid, diagonally where the lines were longer than three characters. I first made the mistake of handling the corner-to-corner line in all rotated diagonals, having too large count of occurrences. When I got to see this mistake, I handled that corner-to-corner diagonal only in one of the rotations.<\/p>\n\n\n\n
In all of those cases I ended up with a line, string of characters. What I needed to do then was to find out how many times the line (and the line in reversed order) contains the XMAS.<\/p>\n\n\n\n
Part 2 was much more simpler than part 1, so that was quickly solved. The goal was to count how many crosses like this…:<\/p>\n\n\n\n
M.S
.A.
M.S<\/pre>\n\n\n\n
…the matrix contains.<\/p>\n\n\n\n
This required just two loops within, starting from the first line and column from the edge, finishing on second-to-last row and column, check if the cell contains an A and then check if the opposing corners are different and contain M and S.<\/p>\n\n\n\n
This was quick on my work laptop (MacBook Pro M2, 2022):<\/p>\n\n\n\n
$ swift run -c release AdventOfCode 4 --benchmark
Building for production...
[1\/1] Write swift-version--1AB21518FC5DEDBE.txt
Build of product 'AdventOfCode' complete! (0.16s)
Executing Advent of Code challenge 4...
Part 1: 2549
Part 2: 2003
Part 1 took 0.014584666 seconds, part 2 took 0.002027958 seconds.<\/pre>\n\n\n\n
The matrix rotations take time, obviously, so part 1 was slower. I considered counting the results of rotated matrices in parallel, but decided not to. That may or may not produce any speed advantage, don’t know… Also could’ve tried to do not rotating in part 1, and just go all in to the matrix from all directions and back to find the words. Well’ it works so I’ll let it be.<\/p>\n","protected":false},"excerpt":{"rendered":"
Today I got to reuse the Matrix<T> generic data structure I implemented last year. Input being a grid of characters like: MMMSXXMASMMSAMXMSMSAAMXSXMAAMMMSAMASMSMXXMASAMXAMMXXAMMXXAMASMSMSASXSSSAXAMASAAAMAMMMXMMMMMXMXAXMASX The goal in part 1 of the puzzle was to find out how many times the word “XMAS” appears in the grid, whether it is written left-to-right, right-to-left or downwards or upwards. And … Continue reading “Advent of Code Day 4 – Ceres Search”<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_post_was_ever_published":false},"categories":[2],"tags":[136,48,149,70,46],"class_list":["post-1122","post","type-post","status-publish","format-standard","hentry","category-coding","tag-advent-of-code","tag-algorithms","tag-aoc2024","tag-programming","tag-swift"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1122","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/comments?post=1122"}],"version-history":[{"count":2,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1122\/revisions"}],"predecessor-version":[{"id":1125,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/posts\/1122\/revisions\/1125"}],"wp:attachment":[{"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/media?parent=1122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/categories?post=1122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.juustila.com\/antti\/wp-json\/wp\/v2\/tags?post=1122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}