While refactoring some
Advent of Code 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.
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 transform a line into a 2-digit number.
s/[^0-9]//g
s/\([0-9]\).*\([0-9]\)/\1\2/
s/^[0-9]$/&&/
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*//
pPostscript: 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/g
s/一$//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.
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
juushika![[community profile]](https://www.dreamwidth.org/img/silk/identity/community.png){kind=small}
![九州鐡道驛中驛外圖 [Painting in and around a Station on the Kyushu Railway] (painting)](https://classinph.pages.dev/bl-https://mizuma-art.co.jp/wp/wp-content/uploads/2018/03/cfa0cc244e0c7209f24c19ad812bffd2.jpg){kind=link}