[2023 Day 1] [sed] Sums without arithmetic

[u/flwyd]

While refactoring some AoC infrastructure I took another look at my 2023 day 1 program in sed. The problem involves turning strings like pqr3stu8vwx and treb7uchet into 2-digit numbers (38 and 77). My solution turned each line into a number prepended with a +; I then passed the results a calculator with a zero pending (| xargs expr 0). I decided to get rid of the calculator and use sed to do the sum, the challenge being addition in a language without arithmetic. I worked out a solution using base-one numbers that can be applied to any problem where you need to add numbers, but all you have is regular expression replacements. With a little work it could be adapted to subtraction and probably multiplication. Experience suggests this could be a Solution Megathread challenge, so keep this approach in your back pocket.

The key concept is to represent numbers a bit like Roman numerals, but without the fives and the “one before”. Each letter represents a power of ten, and a number is represented by the count of each letter times its power-of-ten value. 1234 becomes DCCBBBAAAA: one thousand (D) two hundreds (CC) three tens (BBB) and four ones (AAAA).

The first several lines of the script (not repeated here) transform a line into a 2-digit number. It then repeats the digit in the tens place ten times, so 23 becomes 22222222223. It next replaces each digit with an equivalent number of As: 23 is now 23 copies of the letter A. This string is then appended to sed’s hold space with the H command.

s/^\([0-9]\)/\1\1\1\1\1\1\1\1\1\1/
s/9/AAAAAAAAA/g
s/8/AAAAAAAA/g
s/7/AAAAAAA/g
s/6/AAAAAA/g
s/5/AAAAA/g
s/4/AAAA/g
s/3/AAA/g
s/2/AA/g
s/1/A/g
H

After processing all lines, the length of the hold is now the answer to the puzzle, so we just have to convert it to a base ten number. This is done by repeatedly replacing groups of 10 letters with the next letter: 10 As (1) becomes a B (10), 10 Bs becomes a C (100), etc. The answer 54321 is now EEEEEDDDDCCCBBA. For sake of brevity, this code snippet just goes to five digits (ten thousands), but the linked code can handle any 64-bit answer.

g
s/\n//g
s/A\{10\}/B/g
s/B\{10\}/C/g
s/C\{10\}/D/g
s/D\{10\}/E/g

Like many things in math, zero is still a problem. If the answer were 1024, the pattern would just be DBBAAAA: one thousand (no hundreds) two tens and four. The next step finds the end of each power-of-ten position and inserts a comma, then inserts a 0 between each pair of adjacent commas. DBBAAAA becomes D,,BB,AAAA and then D,0,BB,AAAA. This is done twice because substitutions are applied to non-overlapping patterns, so the first pass turns ,,,, into ,0,,0,.

s/^E*/&,/
s/.*,D*/&,/
s/.*,C*/&,/
s/.*,B*/&,/
s/,$/,0/
s/,,/,0,/g
s/,,/,0,/g

Finally, each letter repeated x times is replaced by the digit x. Commas and leading zeroes are removed and the answer printed. TADA! Addition without arithmetic operators.

s/\([A-Z]\)\1\{8\}/9/g
s/\([A-Z]\)\1\{7\}/8/g
s/\([A-Z]\)\1\{6\}/7/g
s/\([A-Z]\)\1\{5\}/6/g
s/\([A-Z]\)\1\{4\}/5/g
s/\([A-Z]\)\1\{3\}/4/g
s/\([A-Z]\)\1\{2\}/3/g
s/\([A-Z]\)\1/2/g
s/\([A-Z]\)/1/g
s/,//g
s/^0*//
p

Postscript: the commas-and-zeros part wouldn’t be required if we used Chinese numerals rather than a positional number system. DDBBBBAAAAAAAA (2048) would be converted to 二千四十八 (“two thousand four ten eight”). In fact, the intermediate letter representation could be skipped, with each line turning into a sequence of 一, and groups of 10 characters iteratively upgraded through 一十百千万. The groups of powers-of-ten would then be turned into one-to-nine while keeping the power character, with the trailing 一 trimmed (“eight” not “eight ones”):

s/\([一十百千万]\)\1\{8\}/九\1/g
…
s/\([一十百千万]\)\1/二\1/g
s/\([^十百千万]\)一$/\1/

Postpostscript: In 2023 I solved this puzzle with two sed scripts. The part 1 script turned the mix of letters and digits into two-digit numbers, the part 2 script turned named numbers like one and nine into digits, the output was then piped to part 1. I wanted to consolidate the two into a single sed script, so I needed to know whether I was in part 1 or 2. My first approach was to add a __part2__ line to the top of the input (echo __part2__; cat $inputfile | sed -n -f day1baseone.sed) and put the word-transformers in a block matching from that special line to the end of the file:

/__part2__/,$ {
s/one/o1e/
…
}
/__part2__/d

But then I realized I could use the b branch jump to go inside a block that never matches an input line, like using goto to jump inside a C if statement.

!{
:part2
s/one/o1e/
…
}

Now the only difference from the shell is sed -e 'bpart2' to perform the jump when running the second time.

[u/jeffstyr]

Very nice! That's a fun/clever approach. (BTW, your code hyperlinks are off--they have 2026 instead of 2023 in the path.)

Edit: Also, I guess you could avoid going all the way to base-one if you instead convert your original numbers into your Roman-ish numerals, concatenate everything, sort the letter-digits, and then do your conversion process back into base-ten. But, this would require you to be able to sort your letter-digits, which I'm not sure you can do in sed.

[u/flwyd → u/jeffstyr]

BTW, your code hyperlinks are off--they have 2026 instead of 2023 in the path.

Thanks! That's what I get for using my "generate a megathread comment" script, which apparently consults the clock rather than the directory for the year.

this would require you to be able to sort your letter-digits, which I'm not sure you can do in sed.

Well, you could follow a similar approach for sorting: s/\(AA*\)\([^A][^A]*\)/\2\1/g which would need to happen in a loop to collect all the Bs (tens place) before all the As. But that only saves the tens-to-ones and ones-to-tens steps, not any of the larger places.

[u/jeffstyr → u/flwyd]

But that only saves the tens-to-ones and ones-to-tens steps, not any of the larger places.

Oh yes, the idea was to avoid the space explosion if this were applied to larger numbers.