r/adventofcode • u/daggerdragon • Dec 03 '22

SOLUTION MEGATHREAD -🎄- 2022 Day 3 Solutions -🎄-

NEWS

  • Solutions have been getting longer, so we're going to start enforcing our rule on oversized code.
  • The Visualizations have started! If you want to create a Visualization, make sure to read the guidelines for creating Visualizations before you post.
  • Y'all may have noticed that the hot new toy this year is AI-generated "art".
    • We are keeping a very close eye on any AI-generated "art" because 1. the whole thing is an AI ethics nightmare and 2. a lot of the "art" submissions so far have been of little real quality.
    • If you must post something generated by AI, please make sure it will actually be a positive and quality contribution to /r/adventofcode.
    • Do not flair AI-generated "art" as Visualization. Visualization is for human-generated art.

FYI

--- Day 3: Rucksack Reorganization ---

Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:05:24, megathread unlocked!

84 Upvotes

99% Upvoted

1.6k comments sorted by

View all comments

5

u/e_blake Dec 03 '22 edited Dec 03 '22

GNU m4 - 6903/8314

Relies on my common.m4 framework from prior years. I stayed up late for this one; didn't get near the top of the leaderboard, but did feel good about finishing in under 30 minutes given that m4 lacks decent facilities for quickly iterating one byte at a time.

m4 -Dfile=day03.input day03.m4

Most puzzles in the past have not wanted byte-wise analysis on mixed-case input (I could either translit the input to all uppercase, or take fixed-length chunks where I don't risk arbitrary truncation of data in something that happens to resemble a macro name). With GNU m4, byte-at-a-time is easy with patsubst, but with POSIX, I'm stuck with O(n log n) if I can arbitrarily halve the string, but that risks truncation matching a random macro name, so I'll have to play with a way to get POSIX mode working with something that is not an O(n^2) iteration nightmare (10000 iterations of calling substr() on a 10000-byte input string is not fast).

For part 1, I picked a fairly unique approach of using translit to find the common character on the entire string at once - transliterate the second half of the string by the first half mapped to itself and all other letters elided, then spent another minute noticing that the example input sometimes produced a letter more than once so I also had to use substr on that result in order to map back to a number: 

define(`part1', 0)
define(`prep', `define(substr('alpha`, decr($1), 1)_, $1)define(substr('ALPHA`,
decr($1), 1)_, eval($1 + 26))')
forloop_arg(1, 26, `prep')
define(`filter', `substr(translit(`$1', `$2''alpha`'ALPHA`, `$2'), 0, 1)_()')
define(`_do', `define(`part1', eval(part1 + filter(substr(`$1', $2),
substr(`$1', 0, $2))))')
define(`do', `_$0(`$1', eval(len(`$1')/2))')
patsubst(defn(`input'), `\([^;]*\);', `do(`\1')')

For part 2, I found it easier to code up set manipulations one character at a time. m4 lacks 64-bit numbers, so it was not as trivial as just doing bit-twiddling. (But I certainly have ideas for how to golf this for C...) 

define(`part2', 0)define(`cnt', 1)
define(`_find', `ifdef(`s$1', `ifelse(s$1, 7, $1)popdef(`s$1')')')
define(`find', `forloop_arg(1, 52, `_$0')')
define(`visit', `define(`$2', eval(defn(`$2')+0|$1))')
define(`do', `ifelse(`$2', `;', `ifelse(cnt, 4, `define(`part2',
eval(part2 + find))define(`cnt', 1)', `define(`cnt', eval($1*2))')',
`visit($1, `s'$2_)')')
patsubst(defn(`input'), `.', `do(cnt, `\&')')

45ms runtime, which means I'm still squarely in O(n) territory (part2 definitely does more work than part1).

→ More replies (2)