<- cd ../ (back to ~/writeups on the homepage)

[ writeup · case #028 ]

Cat Jail v3: Paws Off

A "beat me 10 times in a row" Nim-like fish game with take and split moves under a per-move timeout. Model it as an impartial combinatorial game and compute Sprague-Grundy values to force a win every round, driven by an automated client.

date
2026-10-11
read
2 min
tags
#ctf #misc #game-theory #sprague-grundy
event
Securinets ENIT — Cat the Flag v3
category
misc
placement
1st place

Category: Misc / Game Theory Service: nc misc.securinets-enit.club 1332 Flag: SecurinetsENIT{spr4gu3_grundy_t4m35_th3_k1tt3n5}

Challenge

Mimi comes back with new rules and dares you to beat her 10 times in a row. Each round you're given several piles of fish. On your turn you pick one pile and either:

  • take 1, 3, or 4 fish from it → take <pile> <amount>
  • split it into two piles of different non-empty sizes → split <pile> <size of one part>

Whoever makes the last move wins (normal play). There's a per-move timeout ("Too slow"), so you can't play by hand — needs an automated client.

Protocol details that matter:

  • <pile> is a 1-based index into the displayed list.
  • It asks "Do you want to go first? (y/n)" at the start of each of the 10 games.
  • After your move the server reprints Piles: (post-your-move), announces Mimi's move, then reprints Piles: again. The last Piles: line before Your move: is the authoritative state.
  • Going first with y just prints Your move: with no new Piles: line, so you must keep the piles from the "go first" prompt.

Idea

This is an impartial combinatorial game, so it's solved with Sprague–Grundy.

Compute the Grundy value g(n) of a single pile of size n. The reachable positions from a pile of size n are:

  • takes: n-1, n-3, n-4 (when ≥ 0) → Grundy g(n-t)
  • splits: every a + b = n with a ≠ b, both ≥ 1 → Grundy g(a) XOR g(b)

g(n) = mex of all those reachable Grundy values.

The Grundy value of the whole position is the XOR of g(pile) over all piles.

  • If the XOR ≠ 0 the position is winning for the mover → go first and move to a XOR-0 position.
  • If the XOR == 0 → go second (any move the opponent makes breaks it; you restore 0).

Each of your turns: enumerate every legal move, pick one whose resulting position has total XOR == 0. Repeat until you take the last fish.

Solver

python
import socket, time, re, sys

HOST="misc.securinets-enit.club"; PORT=1332

# Sprague-Grundy: take 1/3/4, or split into two unequal non-empty piles
N=250
g=[0]*(N+1)
for n in range(1,N+1):
    reach=set()
    for t in (1,3,4):
        if n-t>=0: reach.add(g[n-t])
    for a in range(1,n):
        b=n-a
        if a!=b: reach.add(g[a]^g[b])
    m=0
    while m in reach: m+=1
    g[n]=m

def xor_state(piles):
    x=0
    for p in piles: x^=g[p]
    return x

def find_move(piles):
    fallback=None
    for i,v in enumerate(piles):
        rest=piles[:i]+piles[i+1:]
        base=xor_state(rest)
        for t in (1,3,4):
            if t<=v:
                nv=v-t
                cmd=f"take {i+1} {t}"
                if fallback is None: fallback=cmd
                if base^(g[nv] if nv>0 else 0)==0: return cmd
        for a in range(1,v):
            b=v-a
            if a!=b:
                cmd=f"split {i+1} {a}"
                if fallback is None: fallback=cmd
                if base^g[a]^g[b]==0: return cmd
    return fallback

s=socket.socket(); s.connect((HOST,PORT))
buf=""; cur_piles=None

def pump(timeout=5.0):
    global buf,cur_piles
    s.settimeout(0.4)
    end=time.time()+timeout
    while time.time()<end:
        try:
            c=s.recv(4096)
            if not c: return False
            txt=c.decode(errors="replace"); buf+=txt
            sys.stdout.write(txt); sys.stdout.flush()
            ms=re.findall(r"Piles:\s*([0-9 ]+)", buf)
            if ms: cur_piles=[int(x) for x in ms[-1].split()]
            if buf.rstrip().endswith(">"): return True
        except socket.timeout:
            if buf.rstrip().endswith(">"): return True
    return True

def send(x):
    global buf
    s.sendall((x+"\n").encode()); buf=""

while True:
    alive=pump()
    if "go first" in buf:
        x=xor_state(cur_piles)
        send("y" if x!=0 else "n"); continue
    if "Your move" in buf:
        send(find_move(cur_piles)); continue
    if not alive: break
    time.sleep(0.15)

Result

The client wins all 10 games (going first when the starting XOR ≠ 0, second when it's 0, then always moving to XOR 0). Final round ends with:

text
You made the last move! Mimi's ears flatten.

Mimi bows. For the first time, she has been outplayed:
SecurinetsENIT{spr4gu3_grundy_t4m35_th3_k1tt3n5}

Takeaway

Any "last move wins, pick a pile and do X" game is impartial → reach for Sprague–Grundy. The only per-challenge work is encoding the move set (here: subtract 1/3/4, and split into unequal parts) into the reachable-states function; the XOR-to-zero strategy is mechanical after that.