The SNAFU numbers put me in mind of Roman numerals, which is the most widely known numerical notation that uses subtractive notation.
We can, however, use standard base-N techniques to parse and form SNAFU numbers by just treating = and - as alternative digits for 3 and 4. This works great for turning integers into SNAFU numbers provided we also increment the next unit up (the 5s, 25s, 125s, etc.). So, 3 becomes 1=, 4 becomes 1- purely because the next unit, the 5s, was incremented by one, and this also works for 8 becoming 2=, 13 becoming 1== (via 20 -> 2 _ 5, and the remainder 3 becoming = and incrementing the 5s, but 3 _ 5then again results in a= and incrementing the 25s).
How do you add that extra digit to the next position then? By rounding up when dividing the remainder value by 5; value // 5 would give you the remainder after creating a right-most digit, while (value + 2) // 5 gives you that remainder plus 1 if the last digit was 3 or 4.
I've implemented this as a subclass of the built-in int() type, to make it a little more interesting. Parsing a string is done in Snafu.__new__(), and turning the internal integer value to a string again is done in __repr__().
from __future__ import annotations
from typing import TYPE_CHECKING, Any, Final, Iterable, Self
if TYPE_CHECKING:
from _typeshed import SupportsAdd
SNAFU_DIGITS: Final[str] = "012=-"
SNAFU_VALUES: Final[tuple[int, ...]] = (0, 1, 2, -2, -1)
DIGIT_TO_VALUE: Final[dict[str, int]] = {
c: v for c, v in zip(SNAFU_DIGITS, SNAFU_VALUES)
}
class Snafu(int):
def __new__(cls, value: str | int | Self, _v=DIGIT_TO_VALUE) -> Self:
if isinstance(value, Snafu):
return value
if isinstance(value, str):
value: int = sum((5**i) * _v[c] for i, c in enumerate(reversed(value)))
return super().__new__(cls, value)
def __repr__(self, _d=SNAFU_DIGITS) -> str:
chars, i = [], self
while i:
chars.append(_d[i % 5])
i = (i + 2) // 5
return "".join(chars[::-1])
def __add__(self, rhs: Self) -> Self:
return type(self)(super().__add__(rhs))
tests = (
(1, "1"),
(2, "2"),
(3, "1="),
(4, "1-"),
(5, "10"),
(6, "11"),
(7, "12"),
(8, "2="),
(9, "2-"),
(10, "20"),
(15, "1=0"),
(20, "1-0"),
(2022, "1=11-2"),
(12345, "1-0---0"),
(314159265, "1121-1110-1=0"),
)
for i, s in tests:
assert Snafu(s) == i
assert str(Snafu(i)) == s
def snafu_sum(values: Iterable[str], /, cls: type[SupportsAdd[Any]] = Snafu) -> str:
# start sum() with a Snafu(0) number; alternatively, add Snafu.__radd__ to
# allow for 0 + *first Snafu value* to produce a Snafu number.
return repr(sum(map(cls, values), cls("0")))
example = """\
1=-0-2
12111
2=0=
21
2=01
111
20012
112
1=-1=
1-12
12
1=
122
""".splitlines()
print(snafu_sum(example))
assert snafu_sum(example) == "2=-1=0"
2=-1=0
import aocd
numbers = aocd.get_data(day=25, year=2022).splitlines()
print("Part 1:", snafu_sum(numbers))
Part 1: 2-21=02=1-121-2-11-0
Can we avoid conversion to integers and back when adding two Snafu values? We can if we can add the numbers directly. This works the same as with addition in base 10 or any other base: by carrying the remainder to the next column of digits. We can capture this in a table even; for any of the 25 different combinations of two SNAFU digits, give the resulting summed digit and any carry value.
There are only 6 cases (out of 25) where there will be a carry value that is not 0. Of those 6 there are only 4 unique digit-and-carry pairs; 2 positive and 2 negative carries; The 2 positive variants produce either 3 or 4 and so must add an extra count to the next power of 5 (3 or 1= and 4 or 1-). The two negative versions involve adding a subtractive digit (= or -) to another subtractive digit, and so creating -3 or -4. These lead to a unit being taken away from the next power of 5, so the carry there is -. Put differently, -3 is the same as -5 + 2, and -4 is the same as -5 + 1, and that's exctly what using - as the carry expresses.
However, as the timing runs at the end show, summing the numbers after parsing them into integers is about twice as fast!
from itertools import zip_longest
from typing import Literal, TypeAlias
from IPython.display import Markdown, display
SnafuDigit: TypeAlias = Literal["0", "1", "2", "=", "-"]
Carry: TypeAlias = SnafuDigit
SNAFU_ADD: Final[dict[tuple[SnafuDigit, SnafuDigit], tuple[Carry, SnafuDigit]]] = {
("0", "="): ("0", "="), # 0 + -2 = -2
("0", "-"): ("0", "-"), # 0 + -1 = -1
("0", "0"): ("0", "0"), # 0 + 0 = 0
("0", "1"): ("0", "1"), # 0 + 1 = 1
("0", "2"): ("0", "2"), # 0 + 2 = 2
("1", "="): ("0", "-"), # 1 + -2 = -1
("1", "-"): ("0", "0"), # 1 + -1 = 0
("1", "0"): ("0", "1"), # 1 + 0 = 1
("1", "1"): ("0", "2"), # 1 + 1 = 2
("1", "2"): ("1", "="), # 1 + 2 = 3 (5, -2)
("2", "="): ("0", "0"), # 2 + -2 = 0
("2", "-"): ("0", "1"), # 2 + -1 = 1
("2", "0"): ("0", "2"), # 2 + 0 = 2
("2", "1"): ("1", "="), # 2 + 1 = 3 (5, -2)
("2", "2"): ("1", "-"), # 2 + 2 = 4 (5, -1)
("=", "="): ("-", "1"), # -2 + -2 = -4 (-5, 1)
("=", "-"): ("-", "2"), # -2 + -1 = -3 (-5, 2)
("=", "0"): ("0", "="), # -2 + 0 = -2
("=", "1"): ("0", "-"), # -2 + 1 = -1
("=", "2"): ("0", "0"), # -2 + 2 = 0
("-", "="): ("-", "2"), # -1 + -2 = -3 (-5, 2)
("-", "-"): ("0", "="), # -1 + -1 = -2
("-", "0"): ("0", "-"), # -1 + 0 = -1
("-", "1"): ("0", "0"), # -1 + 1 = 0
("-", "2"): ("0", "1"), # -1 + 2 = 1
}
class PureSnafu:
_s: str
def __init__(self, s: str) -> Self:
self._s = s
def __repr__(self) -> str:
return self._s
def __add__(self, rhs: Self) -> Self:
carry = "0"
digits = []
for a, b in zip_longest(reversed(self._s), reversed(rhs._s), fillvalue="0"):
c, digit = SNAFU_ADD[a, b]
cc, cdigit = SNAFU_ADD[carry, digit]
_, carry = SNAFU_ADD[c, cc]
digits.append(cdigit)
if carry != "0":
digits.append(carry)
return __class__("".join(digits[::-1]))
def __eq__(self, other: Self) -> bool:
if not isinstance(other, __class__):
return NotImplemented
return self._s == other._s
assert snafu_sum(example, cls=PureSnafu) == "2=-1=0"
assert snafu_sum(numbers) == snafu_sum(numbers, cls=PureSnafu)
display(Markdown("## Timings\n\n### Summing as integers:"))
%timeit snafu_sum(numbers)
display(Markdown("### Summing as strings:"))
%timeit snafu_sum(numbers, cls=PureSnafu)