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:

  1. parses and numerically sorts line numbers.
  2. generates printable one-transform candidates for each chunk, including the identity transform.
  3. retains the highest-scoring few candidates per line.
  4. searches combinations in descending total english score.
  5. 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 (&#97;), 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 &amp;#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:

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:

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:

  1. the beam over single readings;
  2. a beam four times wider;
  3. the beam with the searches (caesar shifts, keyed xor);
  4. 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:

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:

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:

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:

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

{generated by a clanker}