QR is Life

Task description

Можете ли pronaći 12-znamenkasti broj koji se koristi kao remote seed? Taj broj je flag. (Can you find the 12-digit number used as the remote seed? That number is the flag.)

What the page does

A “QR Life Simulator” takes a number, generates a QR code from it, and shows a grid that evolves client-side using Conway’s Game of Life, the classic cellular automaton where each cell turns on or off each step based on how many of its neighbours are currently on. A comment in the /flag page’s HTML reveals exactly how the QR code was built: version 1 (a 21x21 grid), error correction level H, numeric data mode, generated with Python’s qrcode library version 7.4.2.

The server applies exactly one step

Generating a QR code locally for a known number and comparing it against what the server’s /flag response actually shows revealed that the server doesn’t serve the raw QR code; it runs one step of Game of Life on it first, server-side, before the client-side JavaScript takes over and keeps evolving from there. Confirmed directly: evolving a locally generated QR code by one step reproduces the server’s response exactly, cell for cell.

That matters because Game of Life has no general inverse; many different starting grids can evolve into the same next state, or none can. Reversing one step isn’t a formula, it’s a search, constrained by whatever we already know must be true about the starting grid.

Pinning down the QR mask

QR codes apply one of eight fixed “mask patterns” over their data to avoid visually awkward runs, and the library picks whichever mask scores best for the given content, which changes which mask applies depending on the actual encoded number. Checking all eight candidates, computing each mask’s effect on the QR code’s fixed structural cells (the finder patterns, separators, timing strip and format information, none of which depend on the encoded data) and evolving just those cells by one step, only mask 3 reproduced the flag grid’s structural cells exactly, all 176 of them.

Why the search is tractable at all

A 12-digit number in QR numeric mode encodes as four groups of three digits, producing 9 data codewords plus 17 Reed-Solomon error-correction codewords, 208 bits placed across the grid in a fixed zig-zag order. Brute-forcing all 10^12 possible 12-digit numbers directly is out of reach, but most of the evolved grid’s cells don’t depend on anything past the raw data codewords; error-correction codewords only affect cells whose values those checks never need. 65 specific cells in the evolved flag grid turn out to depend only on the 72 raw data bits, bits that are already fully pinned down by the four 3-digit groups alone, with no Reed-Solomon computation required to check them.

That split made a staged search practical: check the cheapest, most restrictive subset of those 65 cells first (ones depending only on the first group of digits), and reject almost every candidate before ever computing anything expensive.

Phase	Cells checked	Digits fixed by this phase	Survivors
1	13	digits 1 to 3	about 55 of 900
2	more	digits 4 to 6	about 2 per phase-1 survivor
3	more	digits 7 to 9	very few
4	all 65	digits 10 to 12	about 1 total
final	all 441 cells, Reed-Solomon verified	full QR, full Game of Life step	1 confirmed match

A small C program implementing this staged rejection ran in about 5 seconds and found exactly one match: 669533758353.

Confirming it

Submitting 669533758353 to the server reproduces the /flag grid exactly, zero cells different, confirming the answer.

Why the structure mattered

A QR code’s rigid layout, fixed finder patterns in known positions, a small set of possible masks, and a strict order for placing data bits, turns an otherwise impossible 10^12 search over one step of an irreversible cellular automaton into a seconds-long, heavily pruned computation.