tooling: bounded decoding search
several warmups and embedded descriptors used familiar transforms in changing orders. we built a small decoding engine instead of writing a new base64 loop for each challenge.
transform registry
the registry maps names to strict text-to-text operations: base64, url-safe base64, base32, base85, ascii85, hexadecimal, url percent decoding, rot1–25, rot47, and reversal. a transform must reject malformed input and output valid, non-empty text. strictness prevents permissive decoders from silently deleting characters and producing misleading candidates.
TRANSFORMS = {
"b64": strict_base64,
"hex": strict_hex,
"rot13": rotate_13,
"reverse": lambda text: text[::-1],
# ...
}
breadth-first peeling
for whole-value encodings, candidates are explored breadth-first. each queue entry contains text and the transform path that produced it. a seen set prevents cycles; consecutive rotations and double reversals are skipped; and a depth limit bounds the search.
queue = deque([(raw, [])])
seen = {raw}
while queue:
text, path = queue.popleft()
if goal(text):
return text, path
if len(path) == MAX_DEPTH:
continue
for name, transform in TRANSFORMS.items():
candidate = transform_if_valid(text)
if candidate not in seen:
seen.add(candidate)
queue.append((candidate, path + [name]))
the goal is semantic. for the warmup lane, it requires a bounded word-word-word-NN slug on the final non-empty line and ordinary english in the surrounding text. this disambiguates rot13 because both encrypted and decrypted slugs satisfy the same structural regex.
english scoring is intentionally modest: it counts a small vocabulary such as “the,” “submit,” “answer,” and “decode.” it ranks candidates; it is not a general language detector.
independently encoded lines
later blobs used records of the form NN<TAB>chunk, with a different codec per line. the engine:
- parses and numerically sorts line numbers.
- generates printable one-transform candidates for each chunk, including the identity transform.
- retains the highest-scoring few candidates per line.
- searches combinations in descending total english score.
- joins a combination and applies the same semantic goal.
keeping line boundaries is essential. concatenating base64, rot13, and hex before decoding makes none of them valid. numeric sorting is also essential: lexicographic order places line 10 before line 2.
failure behavior
the engine raises an error when no candidate meets the goal. it does not return the “least bad” string. in timed automation, a loud local failure is safer than submitting plausible garbage and consuming an attempt.
day 4 additions
more representations
day 4's warmup wrote bytes as space-separated eight-bit binary groups. the transform is strict: every non-space character must be 0 or 1 and the bit count a multiple of eight, so it rejects almost everything else immediately. because binary groups are also valid decimal digit runs, it is tried first.
on day 4 we also added the representations most likely to come next, each with the same rule of rejecting malformed input instead of returning partial text: octal and decimal byte lists, morse, base58, base45, atbash, uuencode, quoted-printable, \x/\u/octal escapes and html entities, and base64 or hex wrapping zlib, gzip, bzip2 or xz data. a mutation test encodes a known message with each one and requires the slug to come back through the normal search.
day 5 additions
probing the engine with stacked encodings on day 5 found one real gap: a single-byte xor under hex or base64. xor'd bytes are not text, so the hex and base64 steps reject them before any later step could undo the xor. two combined steps decode to raw bytes and search the key space directly:
def _xor_text(data: bytes) -> str:
best = None
for key in range(1, 256):
try:
text = bytes(b ^ key for b in data).decode("utf-8")
except UnicodeDecodeError:
continue
if not _printable(text):
continue
score = sum(c in FREQUENT for c in text) # e t a o i n s h r d l u, space
if best is None or score > best[0]:
best = (score, text)
if best is None:
raise ValueError("no single-byte xor key gives text")
return best[1]
the key with the most common english letters wins among printable candidates. the near miss is a key off by the case bit: it flips letter case, which scores the same, but it also turns every space into a nul byte, so the printable check rejects it. fourteen two- and three-layer stacks (for example rot13, then base64, then decimal) peel in under 10 ms.
ranked xor candidates
an outside review of the engine found two plaintexts the scorer above gets wrong. a four-letter word such as test ties with udru (key off by one): every letter of both is in the frequent set, and the lower key wins the tie. an answer-shaped string made mostly of digits and capitals gives the letter count too little evidence, so an unrelated printable decode outscored it.
two changes fix this. first, the score now weighs english words from the scoring vocabulary heavily, adds a point for every answer-shaped character (letters, digits, -, _, braces, space), and subtracts for rare punctuation, which is what a near-miss key tends to leave behind:
def _xor_score(text: str) -> int:
rare = sum(c not in ANSWER_CHARS and c not in ".,:;'\"!?()\n\t/" for c in text)
return (
20 * english(text)
+ 2 * len(SLUG.findall(text))
+ sum(c in FREQUENT for c in text)
+ sum(c in ANSWER_CHARS for c in text)
- 3 * rare
)
second, the xor steps no longer collapse to one guess inside the searches that have a goal. the breadth-first peel and the mixed-line decoder both ask for a step's readings, and for the two xor steps that is the four best keys rather than one, so the goal test (a slug on the last line, english text) picks the right one. a short word stays ambiguous on score alone, since case-flipped variants of it are equally printable, but it is now always among the readings the goal sees. answer-shaped and english plaintexts rank first for every key we tested.
day 7 additions
numbered bases not used yet
the warmups prompt names its base each day (64, 13, 16, 2, 10, 8, then the address bar's percent-encoding). base36, base62 (the text as one big number in that alphabet), base91 and a1z26 joined the registry.
scoring line combinations once
the per-line decoder ranks the cartesian product of each line's best readings. it rescored every reading inside every combination: with 33 blobs of numbered lines that was millions of regex calls and 3.8 seconds of a 9-second clock. each reading is now scored once and a combination's total is a sum of cached scores; the ordering, and therefore every result, is unchanged.
day 8 additions
ties and budgets in the line decoder
day 8's new line kind was html character references (a), which the escape reader already decoded. the per-line ranking still lost them: a short entity chunk has no english words, so its real reading scored zero, and so did three copies of the raw text (plain, plus rot13 and atbash, which barely touch a string of digits and punctuation). the best-four cut kept the copies. now identical readings collapse to one, a reading equal to its input is not a decoding, and equal english scores are ordered by the share of dictionary words among their letter runs, then by how word-like their characters are.
both searches got budgets. the breadth-first peel stops after 20,000 nodes and the combination search after 200,000 tried combinations, each with an error that says so. combinations now come off a heap of per-line index vectors, best first, instead of sorting the whole product; the order is the same and the first pop usually wins.
the whole message, scored by letter pairs
the message is split evenly over its lines, and the line count has grown with the day, so chunks keep getting shorter. a three-character chunk cannot be judged alone. the line decoder now runs a beam over the lines: every reading of the next line is appended to every kept hypothesis, and a hypothesis is scored by letter-pair log-probabilities over the joined text, including the pair that crosses the line boundary.
def _char_cost(prev: str, ch: str) -> float:
table = _bigrams() # committed letter-pair log-probabilities
low = ch.lower()
if low in table:
p = prev.lower() if prev.lower() in table else " "
return table[p][low] + CHAR_REWARD - (2.0 if ch.isupper() else 0.0)
if ch.isdigit() or ch in PUNCT:
return -3.0
return -6.0 if ch.isprintable() and ord(ch) < 128 else -18.0
the beam keeps 64 hypotheses, at most six per final character, because hypotheses that end alike score alike from there on. among finished hypotheses, one whose slug is made of dictionary words wins. the letter-pair table and the word list are committed files, so the ranking is identical on every machine. keyed xor readings stay out of the first pass: 256 keys of letter-like noise per line crowd the beam; they join a second pass with two-transform readings if the first finds nothing.
lines without numbers decode in file order through the same beam, and the slug's shape is read from the question's syntax text (word count, number of digits) instead of a constant pattern.
more representations
unicode escapes (\u{61}, %u0061, U+0061), css escapes (\61 ), nato words, seven-bit binary groups and utf-16 text inside base64. the escape reader now runs to a fixed point, so a double-encoded &#97; decodes in one reading.
day 9 additions
quoted lines
day 9's new line kind was a json string literal of \u escapes. the escape reader decoded the escapes and kept the quotes, and when the slug crossed into that line the opening quote split a slug word, so no reading of the message contained a slug. three readings now cover it:
jsonstr: a line that starts and ends with a double quote and contains a backslash is parsed withjson.loads; anything that does not parse to a string is refused. it is first in the line order.- unwrap: every reading of a line, the raw text included, also counts with wrapper characters stripped from both ends, ranked after the readings themselves. it needs no knowledge of the format that put the wrapper there.
- a line inside a matched pair of quotes or brackets is also read inside the pair by the codecs the pair broke, so a quoted base64 or hex string decodes. codecs that already read the whole line are not rerun on the inside: rot47 of a bracketed chunk minus its bracket produced a near-miss word.
bare = []
for name, text in [("plain", chunk), *out]:
stripped = text.strip(WRAPPERS) # "'`[](){}<>
if stripped and stripped != text:
bare.append((f"{name}+unwrap", stripped))
return out + bare
the literal family
percent escapes, html references and json strings are one family: text written as a source-code or markup literal. the registry gained the rest of it, each codec refusing text it does not read:
literals: prefixed quoted strings (b'\x4e',$'\x4e',X'4E',"\N{...}"), char-code calls (String.fromCharCode(78,105),chr(78),[char]0x4e,CHAR(78),Chr(&H4E),string.char(78)) and the operators that join them (+,&,||,.,..,,,-join,concat()). a lone plain quoted string is left to the unwrap reading.bytelist: array literals of prefixed bytes ({0x4e, 0x69},&H4E &H69,0b1001110 0b1101001).- the escape reader also takes
\x{..},\Uwith eight digits,\o{..}and\N{name}; morse accepts typographic dots and dashes; hex and decimal lists accept array syntax.
more representations
z85, base32hex, punycode (xn-- labels), utf-7, mime encoded words (=?utf-8?B?...?=), data uris, grade-1 six-dot braille and braille cells as bytes, unicode compatibility forms (fullwidth and mathematical letters, through nfkc), and bacon's cipher with the 26- and 24-letter tables. base36, base62, base91 and a1z26 are now line readings as well. a stress test builds blobs in the day-9 layout with a tenth line in each of 37 candidate representations and requires the slug back; another feeds every new codec a plain english sentence and requires a refusal.
caesar shifts and two-step repair
a stress line shifted by three, read as plain text, kept the slug's shape: hyphens and digits pass through a caesar shift, so the message ended in a slug of non-words, a wrong answer instead of an error. caesar shifts now join the xor searches as line readings, but only after the plain codecs find no slug made of dictionary words: in the first pass, 24 shifts of every short chunk crowded out the true readings. the passes run in this order:
- the beam over single readings;
- a beam four times wider;
- the beam with the searches (caesar shifts, keyed xor);
- repair: each line the best slug lies on gets every one- and two-step reading in turn, the other lines kept, and the most fluent message whose slug is dictionary words wins.
a second step of the same family as the first (two shifts, two reversals) is skipped. after the last line the beam keeps at most six hypotheses per reading of that line instead of per final character: every message ends in the slug's digits, so one final character held them all.
keyed lines
a line under a vigenère-family key keeps the slug's shape the same way. when repair finds nothing, each line under the slug is tried with vigenère, beaufort, variant beaufort, autokey, and repeating-key xor of its hex or base64 bytes. keys come from the challenge's own text (name, prompt, question) and the other lines' words, up to 48 per line, plus keys the text proves: the previous lines leave a word unfinished, each dictionary completion of the right length gives the key's first letters, and a key is kept only when it repeats inside that completion, so a short key is shown, never guessed. only a slug of dictionary words is accepted. 48 blobs with an unrecoverable key decode, all as low confidence, in under two seconds.
failure reports and confidence
a numbered blob that fails now raises its own error with each line's reading from the beam, the line that reads worst shown as raw text. it used to fall through to a whole-blob peel that could not succeed on nine encodings, spent its node budget in nearly six seconds, and reported only "no decoding path found". the decoder's answer is now a ranked list of slugs with a confidence flag: confident when the first slug is made of dictionary words, otherwise the per-line report comes with it. dictionary words rank readings but never filter them, so a slug word missing from the word list still decodes, as a low-confidence answer.
day 10 additions
base32 that tolerates its own padding
day 10's encoding was base32, already in the registry, and the transform passed its input straight to base64.b32decode. that call accepts only uppercase text whose length is a multiple of eight, so a bare message decoded only when its byte length happened to be a multiple of five. base32 and base32hex now strip any padding, recompute it and fold the case first:
def _b32_padded(text: str) -> str:
s = _compact(text).rstrip("=")
return s + "=" * (-len(s) % 8)
base32's other alphabets
b32alt reads the text in each other common base32 alphabet by translating it to the rfc 4648 one: crockford (case-insensitive, i and l read as one, o as zero), z-base-32 and geohash. each alphabet that reads the text is one reading, and the whole-message beam picks among them by score like any other reading. text with a character outside an alphabet is refused by that alphabet.
number runs and a faster failure
binary groups are read with any separator, and octal and decimal runs with no separator are read at a fixed width. rot18 (rot13 on letters, rot5 on digits) is a registered transform, outside the line order.
the last-resort combination search, which runs when no reading of some line fits, was capped at 200,000 combinations and spent about 2.6 seconds a set proving that nothing fits. the cap is now 5,000: an unreadable line fails in about a quarter of a second a set, with every line's best reading in the error.
day 11 additions
the rest of the base family
day 10 was base32 and day 11 base64url, so day 11 added the base family's other members as line readings, each refusing text it cannot read:
- base64's other alphabets. whole permutations (
itoa64andbcrypt, which start with./, andz64andradix64, which put the digits first) are translated to the rfc 4648 alphabet, one reading per alphabet that reads the text, asb32altdoes for base32. variants that change only the last two symbols (xml, y64, imap, filename-safe) are not listed one by one: the reader takes the two non-alphanumeric symbols the text actually uses and tries them as positions 62 and 63 in both orders. - base58's flickr alphabet (bitcoin's with the cases swapped) and ripple's reordered one.
- base92 (13 bits per pair of characters, 6 for an odd last one), base100 (one emoji per byte), and hex of ebcdic (ibm037) bytes. the ebcdic reading refuses text that decodes to control characters, which is what plain ascii hex becomes when read as ebcdic.
- xxencode: uuencode's line format over an alphanumeric alphabet, with the
beginandendlines optional:
def xx(text: str) -> str:
lines = [
ln.strip()
for ln in text.splitlines()
if ln.strip() and not ln.startswith(("begin ", "end"))
]
if not lines or any(set(ln) - set(XX_ALPHABET) for ln in lines):
raise ValueError("not xxencoded")
out = b"".join(binascii.a2b_uu(ln.translate(XX_TO_UU)) for ln in lines)
...
translating each line to uuencode's alphabet lets the standard library's a2b_uu do the length character and the 4-for-3 unpacking.
day 12 additions
whole-text transforms
day 12's line was the message reversed, a reading the engine already had. the next one may be another whole-text transform, so two were added:
- inverted case (
nICE wORK): read only when the text's uppercase letters outnumber its lowercase ones, so ordinary text never takes the reading. - a keyless rail fence: one reading per rail count from 2 to 8 that the text is long enough for, each undoing the zigzag. a transposition keeps the letters, so text of 8 or more letters whose letters are mostly outside the common english set (
etaoinshrdlu) is refused before any reading is built.
def _rail_positions(n: int, rails: int) -> list[int]:
rows: list[list[int]] = [[] for _ in range(rails)]
row, step = 0, 1
for i in range(n):
rows[row].append(i)
if row == 0:
step = 1
elif row == rails - 1:
step = -1
row += step
return [i for r in rows for i in r]
the rail fence reads whole messages only. tried on every line of a numbered blob, its readings of each unreadable line cost about 0.45s of a 48-set budget test, so a rail-fenced line is reported unread instead.
a search does not outrank a codec
the two-step repair re-reads the lines under the slug with every one- and two-step reading and keeps the most fluent message whose slug is dictionary words. a caesar shift is a search, not a codec, and on short words it finds other words: rot13 of reversed tiger read back by reverse-then-rot9 is pecan. both are dictionary words, and fluency picked the wrong one in 7 of 40 test blobs, as a confident answer. the repair now ranks a reading made only of named codecs above one that needed a search, and fluency decides within each group. the remaining misses come back low confidence.
day 13 additions
classical substitutions after atbash
day 13's line was atbash, which the engine already read. its general form, the affine cipher (x -> a*x + b mod 26 with a coprime to 26), the keyboard shift (each letter typed one key to the side on a qwerty row) and the progressive trithemius shift (the key grows by one per letter) were added the same day. each of them reads every text under some key, so each gives at most one reading: the key whose text scores best as english, and only when that text clearly reads as english and better than the input:
def _best_english(text: str, outs: list[str], name: str) -> str:
best = max(outs, key=english)
if english(best) < MIN_ENGLISH or english(best) <= english(text):
raise ValueError(f"no {name} reading reads english")
return best
they run on whole messages only: on a nine-character line chunk, 285 affine keys produced confident wrong slugs in testing. the polybius square (row and column digit pairs from 1 to 5, i and j sharing a cell, j restored where only the j spelling is a word) and the tap code (c standing in for k) became line readings, since their digit pairs cannot be mistaken for text.
day 14 additions
line k in day k's codec
the mastery blob gains one numbered line a day, and line k has always been in day k's encoding. the engine now reads the known lines by that schedule before any search, and searches only a line past the table:
def positional(chunks, known, hints=""):
n = len(DAY_CODECS)
if len(chunks) > n + 1:
return None
parts = [(DAY_CODECS[k], TRANSFORMS[DAY_CODECS[k]](c))
for k, c in enumerate(chunks[:n])]
if len(chunks) <= n:
return parts if known(text_of(parts)) else None
return new_line(parts, chunks[n], known, hints)
the reading is accepted only when the joined text ends in a dictionary slug; otherwise the per-line search runs as before. the searched line goes in a fixed order: what the challenge's own words name first (a cipher family's name, a number word: week is 7, dozen 12, fortnight 14), then every single codec, then keyed readings with the prompt's words as keys, then pairs of codecs. on day 14's mastery bytes the per-line search misread five short chunks of 68 blobs; the positional reading decodes all of them.
non-ascii and esoteric encodings
new readings: yenc, rot8000 (a rotation over the bmp's printable characters), dna (two bits a base, four bases a byte, every common base order), ternary (one base-3 group per byte), upside-down text, zero-width and unicode-tag steganography, brainfuck and ook!, rot5 over digits alone, raw ebcdic bytes, binhex 4.0, a base64 whose 64-symbol alphabet travels in the blob itself, and base65536 and base2048 from their reference tables. the encodings whose text is never ascii are skipped on ascii chunks, which kept the search inside its budget.
day 16 additions
two more schedule rows, and rows that chain
day 15's line was rot47. as the one line past the schedule table it was found by the new-line search on every blob, every mode passed, and the row was never added. day 16's sixteen-line blobs then had two lines past a fourteen-row table; the positional reading searches at most one, so it returned nothing and the whole-message beam read the mastery, crashing on 16 of 78 blobs (dot com). the table now holds both days, and a row can name a chain of steps, written a>b, for a codec that is two transforms in a row:
DAY_CODECS = (
"b64", "rot13", "hex", "bin", "dec", "oct", "url", "escapes", "jsonstr",
"b32", "b64url", "reverse", "atbash", "rot19", "rot47", "morse>hex",
)
def day_codec(name, chunk):
for step in name.split(">"):
if step not in TRANSFORMS:
raise ValueError(f"no transform {step!r}")
chunk = TRANSFORMS[step](chunk)
return chunk
whenever a numbered line is read by anything but its row (the new-line search, the per-line search or the beam), the decoder records the row it would have needed, decode.DAY_CODECS[k] = name; a regression replay fails on any such record (the table check), so a forgotten row now fails the day it is forgotten instead of the day after.
dot and dash name morse
the prompt's hint words rank the searched line's readings. the morse family listed dots and dashes, and day 16's "dot dot dot" matched neither; the words are now dot and dash, which also match their plurals.
a short new line, ranked by slug words
a seventeenth line will be about six characters. on chunks that short several codecs produce text that still ends in a dictionary slug: a caesar line read under a neighbouring shift, or an atbash reading found before the keyed one. the slugs of every day so far draw on a small vocabulary (about a hundred and forty words over 667 slugs, none new since day 11), so readings are now ranked by how many of the message's last words are in it, after the prompt's named codecs and before english. the search also no longer stops at the first tier with a dictionary reading: it goes on through the later tiers (keyed readings, pairs of codecs) until a reading's slug is made only of known words, and falls back to the first tier's best when none is.
for tier in (hint_step, one_step, left_out, keyed_step, two_steps):
hits = [parts + [r] for r in tier(chunk) if known(head + r.text)]
if not hits:
continue
vocab = [h for h in hits if slug_words_known(text_of(h))]
if vocab:
return max(vocab, key=rank)
first = first or max(hits, key=rank)
return first
the failure report leads with what the table did not read
when no reading meets the goal, the error lists each line's best reading (day 9). the list was in line order and the report is cut to a fixed length; on day 16 the cut fell after line 10 of 16, so the lines that explained the failure were not in it. lines the table did not read now come first, each with its raw text next to its best reading.
day 17 additions
bacon groups as hex nibbles
day 17's codec was bacon's cipher over hex (bacon bits): five-symbol groups of a and b, read as binary, but never above fifteen, so each group is one hex nibble and two make a byte. the engine's bacon reading maps groups to letters, which gives a string of a-p that nothing further reads. the new transform refuses a group above fifteen and an odd count, so ordinary bacon text never reads as hex:
vals = [int(g, 2) for g in groups] # a = 0, b = 1
if len(vals) % 2 or max(vals) > 15:
raise ValueError("bacon groups are not hex nibbles")
return as_text(bytes(vals[i] << 4 | vals[i + 1] for i in range(0, len(vals), 2)))
it is the seventeenth row of the line schedule, in the line order after the two bacon tables, and "a's and b's" and "sixteen" are its hint words. the single was one whole blob in the codec, not numbered lines; the whole-text search reads it on its first step.
day 18 additions
a fixed rail count for the line schedule
day 18's codec was a three-rail fence (off the rails). the keyless rail reading (day 13 prep) ranks two to eight rails by how english each reading looks, which is right on a whole message and wrong on a seven character line chunk, where several rail counts read plausibly. the eighteenth schedule row is the fixed three-rail transform, and the reading of any rail count reads any length (a five character chunk of a nineteen line mastery too); only the keyless search skips the counts a short text cannot tell apart.
def unrail(text, rails):
plain = [""] * len(text)
for ch, i in zip(text, rail_positions(len(text), rails)):
plain[i] = ch
return "".join(plain)
def railfence3(text):
return unrail(text, 3)
a keyless columnar transposition
a rail fence is one transposition; the unkeyed columnar is the other common one: the text written row by row into n columns and read column by column, the first len % n columns one longer. columnar_readings gives one reading per column count from two to eight that leaves at least two rows, under the rail fence's letter-frequency refusal, and column, columns, grid and rows are its hint words.
def uncolumnar(text, columns):
rows, extra = divmod(len(text), columns)
out, pos = [""] * len(text), 0
for c in range(columns):
for r in range(rows + (1 if c < extra else 0)):
out[r * columns + c] = text[pos]
pos += 1
return "".join(out)
day 19 additions
wide text under every step
day 19's blob was hex of utf-16le text that starts with a byte-order mark (little things). every reading turns its bytes into text through one function, which already took utf-16le by its zero high bytes; the mark's second byte (fe) sits where a zero was expected, so the bytes went to utf-8 and every reading failed. the function now checks a mark of either order first, then zero high bytes in either order, and utf-32 the same way before utf-16 (utf-32le's mark starts with utf-16le's).
if data[:4] in (b"\xff\xfe\x00\x00", b"\x00\x00\xfe\xff"):
data = data.decode("utf-32").encode()
elif data[:2] in (b"\xff\xfe", b"\xfe\xff"):
data = data.decode("utf-16").encode()
the nineteenth schedule row and wide-text hints
utf16lehex (hex, then utf-16 by its mark or its zeros) is the line schedule's nineteenth row, so the mastery's line 19 reads by its day; utf32hex is the same step for four-byte text. "two bytes", "little one", "big one" and "endian" hint the utf-16 family, "four bytes" and "ucs-4" the utf-32 one.
day 20 additions
the big-endian row
day 20's line was hex of utf-16 big-endian text behind its byte-order mark (big entrance). the text reader already honoured a mark of either order, so the plain hex step read the line, and the schedule recorded it as hex. a row named by the first step that happened to read a line loses what the line is, so the twentieth row is utf16behex: hex, then utf-16 big-endian by its fe ff mark or by the zero byte coming first, refusing the little-endian order that the nineteenth row reads.
raw = bytes.fromhex(clean(text))
big = raw[:2] == b"\xfe\xff" or (len(raw) > 3 and not any(raw[0::2]))
if len(raw) % 2 or not big:
raise ValueError("not utf-16be hex")
the hint words split by order: "big one", "big-endian" and "big entrance" name the big-endian row first; "two bytes", "little one", "endian" and "wide" name the little-endian one, whose reader takes either mark.
day 21 additions
a compressed line
day 21's twenty-first line was base64 of a gzip member (under pressure), and the single and time trial were whole blobs of the same kind. the base64-then-decompress step already accepted either framing, gzip (1f 8b) or zlib (78 with the header check bits), through one call, so the search read the line; the schedule now names row 21 b64inflate, and the prompt's words (compressed, inflate, deflate, zlib, pressure) hint it first.
raw = base64.b64decode(compact(text), validate=True)
text = zlib.decompress(raw, 47).decode("utf-8") # 32 + 15: gzip or zlib
day 22 additions
a zlib line, and the rest of the wrapper family
day 22's twenty-second line was base64 of a zlib stream (deflated ego); the base64-then-decompress step already read zlib, so the schedule only names row 22. the same step now also reads the wrappers a "familiar wrapper" could name next: zstd and lz4 frames (each by its magic), raw deflate (no header, so the stream must end exactly at the data's end) and brotli (no magic either, fed in small steps against the size bound and required to finish). a line that is none of them still raises instead of yielding bytes.
for unpack in (inflate, gunzip, bunzip, unxz, unzstd, unlz4, raw_inflate, unbrotli):
try:
return as_text(unpack(raw))
except (OSError, EOFError, ValueError, LZMAError, zlib.error):
continue
raise ValueError("not compressed")
a slug that runs past its shape
the question's syntax gives the slug's shape, and the line search used it to judge readings of the newest line: a reading that ended the message in a slug of that shape was accepted, one that did not was not. one mastery blob's message ran on past the shape, so its verified zlib reading was refused and a reversed-base64 reading that happened to end the shape won. a slug followed by more -token groups now counts as found; the answer is both forms, in an order a later timed attempt settled ([redacted]).
core = shape.pattern.removesuffix(r"(?![A-Za-z0-9-])")
extended = re.compile(core + r"(?:-[a-z0-9]+)+(?![A-Za-z0-9-])")
hint words by stem
the prompt said "inflation"; the hint table said "inflate". a hint word now also matches the prompt by its stem (a final e dropped), so the family is tried first whichever form the prompt uses.
day 23 additions
ascii85 as the twenty-third row
day 23's twenty-third line was ascii85 between adobe's <~ and ~> delimiters (eighty-five alive). the ascii85 reading already switched to adobe mode when the text carries the opening delimiter, and the prompt's words (85, ascii85, adobe) already ranked it first for a new line, so the line was read on the day; the schedule now names row 23.
a short new line read as written
each day adds a line, so the message's characters spread over more lines and the newest chunk gets shorter. at twenty-four lines the last chunk is four characters: one letter and the slug's two digits with their hyphen. four readings broke on chunks that short, found by modelling 24 and 25 line blobs in the readiness tests:
- a transposition no wider than the chunk (four columns, a four-wide spiral) leaves it unchanged, and the search dropped a reading equal to its input, so a digit-shift reading of the same chunk won instead. the line as written is now a reading tier of its own, after the one-step codecs and before the rarer ones; a codec the prompt names still wins.
- when two readings score the same on the prompt, the slug words and english, the ranking now prefers the one that leaves the chunk as written over, say, a 2x2 spiral that swaps the digits.
- a route transposition whose grid is one row reads the text as written; it is offered last, so a real grid's reading still comes first.
- yenc needed 30% of a chunk above ascii before it would read it, which a four-byte chunk with one such byte failed; it now refuses only text with no byte above ascii at all.
tiers = (_hint_step, _one_step, _as_written, _left_out, _keyed_step, _two_steps)
def _as_written(chunk, head, hints):
return [("plain", chunk)]
def _hint_rank(hints, named, chunk, parts):
name, reading = parts[-1]
text = _text(parts)
return (prompt_rank(name), hinted(name), graded_words(text),
english(text), reading == chunk)
day 24 additions
netstrings as the twenty-fourth row
day 24's line was a run of netstrings, <length>:<data>,, one per character of the message (string theory). no reading parsed length-prefixed text, and the prompt's words ("count", "comma") matched no hint family, so the line search ended with no path. the netstring reading reads the decimal length, takes exactly that many characters and requires a comma right after them; a comma or colon inside the data is never a separator, because the reader has stepped past the data by its length before it looks for the next colon.
j = s.find(":", i)
if j <= i or not s[i:j].isdigit():
raise ValueError("not a netstring")
end = j + 1 + int(s[i:j])
if end >= len(s) or s[end] != ",":
raise ValueError("netstring length mismatch")
out.append(s[j + 1 : end])
i = end + 1
it is a line reading and the schedule's row 24, and count, comma, length and colon are its hint words.
five more framings beside it
a prompt about counting and stopping could as well have meant one of netstring's neighbours, so five more readings went in with it, each with a test sample and each raising where it does not apply:
bencode:<length>:<data>strings with no comma, bare or insidel...elists andd...edictionaries; integers (i42e) are structure, and the strings in order are the text.hexdump:xxd,hexdump -Candod -A x -t x1listings, one offset a line. the byte column ends at|(hexdump -C) or at the two spaces before xxd's ascii column; a line whose offset is set off by a single space (od) counts as a listing only when the offsets step by each line's byte count, otherwise it is spaced hex.roman: roman numerals read as a1z26 letters (x-i-x) or as character codes (cvi), validated by the standard numeral grammar, not by a letter table.numberwords: numbers spelled out (twelve,ninety-seven, or digits spelled one by one,one-zero-six), read as a1z26 letters when every value is 1 to 26, else as printable character codes.rle: run-length pairs with the count first (3a2b) or last (a3b2), counts under 100, at least two pairs, one order throughout. the output is capped at 4,096 characters: without the cap a bare hex chunk such as206465636fparsed as a single run and expanded to 206 million characters.
def _codes_text(vals, what):
if all(1 <= v <= 26 for v in vals):
return "".join(chr(96 + v) for v in vals) # a1z26
if all(32 <= v <= 126 for v in vals):
return "".join(chr(v) for v in vals) # character codes
raise ValueError(f"{what} are not letters or character codes")
a shape gate before each new reading
each of the six readings cost about 0.08 seconds of call-and-exception overhead over a 48-set mastery, whose whole budget in our tests is 2 seconds. a chunk that cannot start like the reading's input now skips the call, the way readings for non-ascii encodings already skip ascii chunks:
LOOKS_LIKE = {
"netstring": re.compile(r"\s*\d+:"),
"bencode": re.compile(r"\s*(?:[ldi]|\d+:)"),
"hexdump": re.compile(r"\s*(?:0x)?[0-9a-fA-F]{4,10}[:\s]\s*[0-9a-fA-F]{2}"),
"roman": re.compile(r"[\s,;./|ivxlcdm-]+$", re.I),
"rle": re.compile(r"\s*(?:\d{1,2}\D|\D\d{1,2})"),
}
shape = LOOKS_LIKE.get(name)
if shape is not None and shape.match(chunk) is None:
continue
day 25 additions
code points as the twenty-fifth row
day 25's line spelled every character of the message as a unicode code point, U+ and four hex digits, one token per character with a space between tokens (you have a point). the reading for it, uniesc, has existed since day 8 for browser-side escapes: javascript's \u{...} with one to six hex digits, the %uXXXX form older web servers emit, and the standard's own U+XXXX with four to six. one optional whitespace character after a U+ token belongs to the token, so a line of them joins into text instead of text with a space between every letter.
UNICODE_ESCAPE = re.compile(
r"\\u\{([0-9a-fA-F]{1,6})\}|%u([0-9a-fA-F]{4})|U\+([0-9a-fA-F]{4,6})\s?"
)
line 25 of every mastery blob was past the schedule, so the line search read it and the mastery passed; the regression replay's table check reported the missing row. the schedule now names uniesc as row 25, so line 25 is read by its row before any search runs.
day 26 additions
brainfuck as the twenty-sixth row
day 26's line was a brainfuck program (food for thought): +, - and . only, one cell, no loops, each run of + or - the step from one character's code to the next and each . a printed character. the brainfuck reading has been in the registry since day 14 with ook!, a complete interpreter with a bounded tape and step count. it refuses text with fewer than eight command characters or with command characters under 80 percent of the non-whitespace text, before it runs anything, because ., ,, +, -, < and > are common in other encodings:
code = [c for c in text if c in "+-<>[].,"]
if len(code) < 8 or len(code) < 0.8 * len(text.replace(" ", "").replace("\n", "")):
raise ValueError("not brainfuck")
line 26 of every mastery blob was past the schedule, so the line search read it, and the regression replay's table check reported the missing row. the schedule now names brainfuck as row 26:
DAY_CODECS = (
"b64", "rot13", "hex", "bin", "dec", "oct", "url", "escapes", "jsonstr",
"b32", "b64url", "reverse", "atbash", "rot19", "rot47", "morse>hex",
"baconhex", "railfence3", "utf16lehex", "utf16behex", "b64inflate",
"b64inflate", "a85", "netstring", "uniesc", "brainfuck",
)
day 27 additions
ook! as the twenty-seventh row
day 27's line was an ook! program (monkey business): the brainfuck dialect that spells each command as a pair of Ook., Ook? and Ook! tokens. the reading has been in the registry since day 14 beside brainfuck: it checks that every whitespace-separated token is one of the three words and that there is an even number of them, maps each pair to its brainfuck command and runs the same bounded interpreter:
OOK = {("Ook.", "Ook?"): ">", ("Ook?", "Ook."): "<", ("Ook.", "Ook."): "+",
("Ook!", "Ook!"): "-", ("Ook!", "Ook."): ".", ("Ook.", "Ook!"): ",",
("Ook!", "Ook?"): "[", ("Ook?", "Ook!"): "]"}
code = "".join(OOK[(a, b)] for a, b in zip(toks[::2], toks[1::2]))
line 27 of every mastery blob was past the schedule, so the line search read it (0.4 seconds on the single, about a second and a half over the mastery's blobs), and the regression replay's table check reported the missing row. the schedule now names ook as row 27:
DAY_CODECS = (
"b64", "rot13", "hex", "bin", "dec", "oct", "url", "escapes", "jsonstr",
"b32", "b64url", "reverse", "atbash", "rot19", "rot47", "morse>hex",
"baconhex", "railfence3", "utf16lehex", "utf16behex", "b64inflate",
"b64inflate", "a85", "netstring", "uniesc", "brainfuck", "ook",
)
day 28 additions
reversed hex as the twenty-eighth row
day 28's line was hex whose text was then reversed character by character (back in sixteen). reversing the characters of a hex string reverses the byte order and swaps the two digits inside every byte, so the reading is the chain of the reversal step and the hex step, in that order. both steps were in the registry and the prompt's words named them ("sixteen" is a hex hint word, "backward" a reversal one), so the search found the chain on every mode's first run; on the mastery it did so once per blob, past the schedule. the schedule now names the chain as row 28:
DAY_CODECS = (
"b64", "rot13", "hex", "bin", "dec", "oct", "url", "escapes", "jsonstr",
"b32", "b64url", "reverse", "atbash", "rot19", "rot47", "morse>hex",
"baconhex", "railfence3", "utf16lehex", "utf16behex", "b64inflate",
"b64inflate", "a85", "netstring", "uniesc", "brainfuck", "ook",
"reverse>hex",
)
no beam after a confident slug
once the first reading of a message produced a slug, the whole-message search still ranked readings of every line with a beam, to have backups ready in case the first slug was rejected. on day 28's mastery, a hundred and thirty-eight blobs, that beam was nearly all of the solve. the search now returns as soon as the slug it found is made of dictionary words; a slug with a non-word in it, or no slug, still runs the beam. over every saved mastery set from day 3 on, no first slug changed, and day 28's mastery went from 1.06 seconds to 0.08.
first = find_slug(raw, pattern, hints)
if known_slug(first, slug): # every word in the slug vocabulary
return [first] # the beam below only fed retries
the chain that read a day's first blob confidently is also kept, so the day's later blobs try it before any search.
a budget per blob
the whole-value peel now stops after eight seconds on one blob and returns any slug-shaped reading as low confidence instead of running on, and it checks the slug goal as readings are made rather than after a whole layer. a blob in the moo language that missed took 34.7 seconds before and 0.2 now.
seven more readings
cow (brainfuck spelled in moos), whitespace (a program of spaces, tabs and newlines, read without stripping), jsfuck (evaluated by node under a five-second cap), deadfish, bubblebabble, a nibble swap of hex, and base64 of ebcdic text, each with hint words and a round-trip test.
a distinct-letter guard on substitutions
affine and keyboard-shift readings map letters one to one, so they cannot change how many distinct letters a text has. every message so far has more than twenty; hex, brainfuck and ook! blobs have at most seven. both readings now refuse a text with fewer than eight distinct letters, which took day 27's ook! single from 248 milliseconds to 32.
day 29 additions
rot13 over base64 as the twenty-ninth row
day 29's line was base64 whose letters were then rotated thirteen places (rotten base). the rotation moves letters only, so the digits, the + and / and the = padding stay put and the line keeps its base64 shape without decoding to text. the reading is the chain of the rot13 step and the base64 step, in that order. both steps were in the registry and the prompt's words named them ("sixty-four" is a base64 hint word, "thirteen" a rot13 one), so the search found the chain on every mode's first run; on the mastery it did so once per blob, past the schedule. the schedule now names the chain as row 29:
DAY_CODECS = (
"b64", "rot13", "hex", "bin", "dec", "oct", "url", "escapes", "jsonstr",
"b32", "b64url", "reverse", "atbash", "rot19", "rot47", "morse>hex",
"baconhex", "railfence3", "utf16lehex", "utf16behex", "b64inflate",
"b64inflate", "a85", "netstring", "uniesc", "brainfuck", "ook",
"reverse>hex",
"rot13>b64",
)
day 30 additions
url twice as the thirtieth row
day 30's line was url encoding applied twice (percent percent): "that address bar problem? it happened twice." the url step was in the registry and "percent" is one of its hint words, so the search found the two-step reading on every mode's first run; on the mastery it did so once per blob, past the schedule. the schedule now names the chain as row 30, "address bar" joins the url hint words, and the next-day blob model learned the same row (replay and analysis):
DAY_CODECS = (
"b64", "rot13", "hex", "bin", "dec", "oct", "url", "escapes", "jsonstr",
"b32", "b64url", "reverse", "atbash", "rot19", "rot47", "morse>hex",
"baconhex", "railfence3", "utf16lehex", "utf16behex", "b64inflate",
"b64inflate", "a85", "netstring", "uniesc", "brainfuck", "ook",
"reverse>hex",
"rot13>b64",
"url>url",
)
a chain of the day table's codecs
days 28, 29 and 30 were each a chain of two codecs the table already held (reversed hex, rot13 over base64, url twice), named only by a pun. a breadth-first search over chains now runs after every transform alone and before the peel: its units are the table's steps and its chained rows (morse>hex is one unit), the codecs the prompt names first, up to three units deep, one second a search. the single's chain is kept, so the mastery's new line reads by it in about a millisecond. repeat words name a codec applied twice:
REPEAT_WORDS = ("twice", "double", "two times", "second time", "two layers")
over every two-unit pair of 26 table units (654) and 130 sampled three-unit chains, with and without the prompt, every single reads inside its budget, none confidently wrong (before: 615 of 654 and 60 of 130). escapes now stops at a quoted json string and at adobe-framed ascii85, so escapes>jsonstr and escapes>a85 read as chains, where escapes used to run on into the inner layer. a one-line override stays decode.remember("a>b>c").
a line nothing reads goes out unsure
with the table reading lines 1 to 30, a line 31 no codec reads ran every fallback after the new-line search: over a second a set, three minutes for 150 sets against a 15-second solve cap. the one line past the table now gets 0.03 seconds of the repairs' readings; a codec's reading that ends a slug of dictionary words still wins, anything else leads an unsure list whose report names that line only. 150 such sets take 3.3 seconds.
a short line read by a search is never confident
the new-line search reads the line past the table under every prompt key and keyed cipher, every shift, xor, rails, columns and alphabets. on a few letters one of them ends a slug of dictionary words by chance: at five to nine characters, permuted lines read confidently wrong in up to three sets of four. a reading whose path has a keyed or searched step is now confident only with seven letters in distinct words; under that it leads an unsure list. measured over three hundred sets a cell, lines of 3 to 20 characters under two prompts: no confident wrong reading in any cell, and the right slug still first in every true keyed line.
changelog
- day 1: whole-value base64 peeling with a slug goal.
- day 2: the transform registry, breadth-first search with an english-scored goal (rot13 ambiguity), per-line decoding.
- day 3: hex, numbered
NN<TAB>chunkrecords with independent codecs and a best-first combination search. - day 4: binary groups; then octal, decimal, morse, base58/45, atbash, uu, quoted-printable, escapes and compressed payloads.
- day 5: single-byte xor under hex and base64, checked against stacked encodings; a stronger xor score (english words, answer-shaped characters, rare-punctuation penalty) and the best four keys passed to goal-driven searches instead of one.
- day 7: base36, base62, base91 and a1z26; line-combination scores cached (mastery bundle 3.8s -> 0.27s).
- day 8: html references decoded to a fixed point; identical readings collapsed and score ties ordered by dictionary words; node and combination budgets with a best-first heap; a whole-message beam scored by letter pairs across line boundaries; unnumbered lines; the slug shape read from the question; unicode, css, nato, seven-bit binary and utf-16 readings.
- day 9: json string literals and wrapper-stripped readings of quoted or bracketed lines; the source-literal family (prefixed strings, char-code calls, byte lists) plus z85, base32hex, punycode, utf-7, mime words, data uris, braille, nfkc and bacon; caesar shifts as a search pass and two-step repair of the lines under a non-dictionary slug; keyed vigenère, beaufort, autokey and xor recovery with keys from the blob and the prompt; per-line failure reports and low-confidence answers.
- day 10: padding-tolerant, case-folded base32 and base32hex; the crockford, z-base-32 and geohash alphabets; binary groups with any separator and fixed-width octal and decimal runs; rot18; the combination search capped at 5,000 (an unreadable line fails in about 0.25s a set).
- day 11: base64's other alphabets (itoa64, bcrypt, z64, radix64, and two-symbol variants read from the text's own symbols), base58's flickr and ripple alphabets, base92, base100, xxencode and ebcdic hex as line readings.
- day 12: inverted case as a line reading and a keyless rail fence for whole messages; the two-step repair prefers named codecs over shift searches.
- day 13: affine, keyboard-shift and progressive (trithemius) readings of whole messages, kept only when one key reads clearly english; polybius square and tap code as line readings.
- day 14: numbered line k read by day k's codec before any search, the new line searched in prompt order; yenc, rot8000, dna, ternary, upside-down, zero-width and tag steganography, brainfuck / ook!, rot5 digits, raw ebcdic, binhex, a carried base64 alphabet, base65536 and base2048; non-ascii encodings skipped on ascii chunks.
- day 16: rot47 and morse-then-hex rows in the line schedule, rows as chains of steps, and a record of every line read without its row;
dotanddashas morse hints; a short new line ranked by known slug words, searched past the first tier; failure reports lead with the lines the schedule missed. - day 17: bacon groups read as hex nibbles, the seventeenth schedule row.
- day 18: a fixed three-rail fence, the eighteenth schedule row; a rail reading of any length; a keyless columnar transposition.
- day 19: utf-16 and utf-32 text read by a byte-order mark or zero bytes under every step; hex of utf-16 as the nineteenth schedule row; wide-text hint words.
- day 20: hex of utf-16 big-endian as the twentieth schedule row; hint words split by byte order.
- day 21: base64 of a gzip member as the twenty-first schedule row; compression hint words.
- day 22: base64 of a zlib stream as the twenty-second schedule row; a slug that runs past its shape answered whole, then shaped; hint words by stem; zstd, lz4, raw deflate and brotli under the wrapper step.
- day 23: ascii85 as the twenty-third schedule row; a short new line read as written (its own tier, preferred on a ranking tie), the one-row route grid, yenc on a single byte above ascii.
- day 24: netstrings as the twenty-fourth schedule row with counting hint words; bencode, hexdump listings, roman numerals, spelled-out numbers and bounded run-length pairs beside it; a shape gate that skips each of the six on a chunk that cannot be its input.
- day 25: the code-point reading (
U+XXXX, also\u{...}and%uXXXX) as the twenty-fifth schedule row. - day 26: brainfuck as the twenty-sixth schedule row.
- day 27: ook! as the twenty-seventh schedule row.
- day 28: reversed hex as the twenty-eighth schedule row; no beam search after a slug of dictionary words, and a day's confident chain tried first on its later blobs; an eight-second peel budget per blob; cow, whitespace, jsfuck, deadfish, bubblebabble, nibble-swap and base64-of-ebcdic readings; a distinct-letter guard on affine and keyboard readings.
- day 29: rot13 over base64 as the twenty-ninth schedule row.
- day 30: url twice as the thirtieth schedule row; a breadth-first search over chains of up to three schedule codecs before the peel, the prompt's codecs first; escapes stops at a quoted json string and at framed ascii85; a mastery line nothing reads goes out unsure within 0.03s; a short line read only by a keyed or searched step is never confident.
{generated by a clanker}