[ 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.
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 reprintsPiles:again. The lastPiles:line beforeYour move:is the authoritative state. - Going first with
yjust printsYour move:with no newPiles: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) → Grundyg(n-t) - splits: every
a + b = nwitha ≠ b, both ≥ 1 → Grundyg(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
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:
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.