1
#!/usr/bin/env python3
2
import argparse
3
import subprocess
4
from functools import lru_cache
5

6

7
WIDTH = 0x113  # 275
8
HEIGHT = 5
9
BIT_BUDGET = 0xFE5  # 4069 bits consumed by verifier
10

11
# Derived from reversing nonogram_gate
12
CIPHER_FILE_OFFSET = 0x2020
13
CIPHER_LEN = 0x1FD  # 509
14
XOR_STRIDE = 0x3D
15

16

17
def extract_cipher(path: str) -> bytes:
18
    with open(path, "rb") as f:
19
        blob = f.read()
20
    end = CIPHER_FILE_OFFSET + CIPHER_LEN
21
    if end > len(blob):
22
        raise ValueError("binary too small for expected encrypted clue region")
23
    return blob[CIPHER_FILE_OFFSET:end]
24

25

26
def decode_clue_blob(cipher: bytes) -> bytes:
27
    tmp = bytearray(CIPHER_LEN)
28
    out = bytearray(CIPHER_LEN)
29
    for i, c in enumerate(cipher):
30
        tmp[i] = (c ^ ((i * XOR_STRIDE - 0x0D) & 0xFF)) & 0xFF
31
    for i, v in enumerate(tmp):
32
        out[(i * 7) % CIPHER_LEN] = v
33
    return bytes(out)
34

35

36
class BitReader:
37
    def __init__(self, data: bytes):
38
        self.data = data
39
        self.bitpos = 0
40

41
    def read(self, nbits: int) -> int:
42
        val = 0
43
        for _ in range(nbits):
44
            if self.bitpos >= len(self.data) * 8:
45
                raise ValueError("bitstream underflow")
46
            byte = self.data[self.bitpos // 8]
47
            shift = 7 - (self.bitpos % 8)
48
            bit = (byte >> shift) & 1
49
            val = (val << 1) | bit
50
            self.bitpos += 1
51
        return val
52

53

54
def parse_clues(decoded: bytes):
55
    br = BitReader(decoded)
56
    row_clues = []
57
    for _ in range(HEIGHT):
58
        cnt = br.read(7)
59
        row_clues.append([br.read(3) for _ in range(cnt)])
60

61
    col_clues = []
62
    for _ in range(WIDTH):
63
        cnt = br.read(7)
64
        col_clues.append([br.read(3) for _ in range(cnt)])
65

66
    if br.bitpos != BIT_BUDGET:
67
        raise ValueError(f"unexpected clue bit count: {br.bitpos} != {BIT_BUDGET}")
68
    return row_clues, col_clues
69

70

71
def runs_from_bits(bits):
72
    runs = []
73
    run = 0
74
    for b in bits:
75
        if b:
76
            run += 1
77
        elif run:
78
            runs.append(run)
79
            run = 0
80
    if run:
81
        runs.append(run)
82
    return runs
83

84

85
def column_candidates(col_clues):
86
    cand = []
87
    for clue in col_clues:
88
        valid = []
89
        for mask in range(1 << HEIGHT):
90
            bits = [1 if (mask >> r) & 1 else 0 for r in range(HEIGHT)]
91
            if runs_from_bits(bits) == clue:
92
                valid.append(bits)
93
        if not valid:
94
            raise ValueError(f"no candidate column for clue {clue}")
95
        cand.append(valid)
96
    return cand
97

98

99
def row_transition_table(row_clues):
100
    tables = []
101
    starts = []
102
    accepts = []
103
    for runs in row_clues:
104
        k = len(runs)
105
        state_id = {}
106
        states = []
107
        trans = []
108

109
        def intern(st):
110
            if st in state_id:
111
                return state_id[st]
112
            idx = len(states)
113
            state_id[st] = idx
114
            states.append(st)
115
            trans.append([-1, -1])
116
            return idx
117

118
        start = intern((0, 0, 0))  # (next_run_idx, rem_in_current_run, must_gap_zero)
119
        q = [start]
120
        qi = 0
121
        while qi < len(q):
122
            sid = q[qi]
123
            qi += 1
124
            run_idx, rem, must_gap = states[sid]
125
            for bit in (0, 1):
126
                nxt = None
127
                if rem > 0:
128
                    if bit == 1:
129
                        rem2 = rem - 1
130
                        if rem2 == 0:
131
                            if run_idx == k - 1:
132
                                nxt = (k, 0, 0)
133
                            else:
134
                                nxt = (run_idx + 1, 0, 1)
135
                        else:
136
                            nxt = (run_idx, rem2, 0)
137
                else:
138
                    if run_idx == k:
139
                        if bit == 0:
140
                            nxt = (k, 0, 0)
141
                    else:
142
                        if must_gap:
143
                            if bit == 0:
144
                                nxt = (run_idx, 0, 0)
145
                        else:
146
                            if bit == 0:
147
                                nxt = (run_idx, 0, 0)
148
                            else:
149
                                rem2 = runs[run_idx] - 1
150
                                if rem2 == 0:
151
                                    if run_idx == k - 1:
152
                                        nxt = (k, 0, 0)
153
                                    else:
154
                                        nxt = (run_idx + 1, 0, 1)
155
                                else:
156
                                    nxt = (run_idx, rem2, 0)
157
                if nxt is not None:
158
                    nid = intern(nxt)
159
                    trans[sid][bit] = nid
160
                    if nid >= len(q):
161
                        q.append(nid)
162

163
        accept_set = {sid for sid, (ri, rem, _) in enumerate(states) if ri == k and rem == 0}
164
        tables.append(trans)
165
        starts.append(start)
166
        accepts.append(accept_set)
167
    return tables, starts, accepts
168

169

170
def solve_board(row_clues, col_clues):
171
    col_cands = column_candidates(col_clues)
172
    trans, starts, accepts = row_transition_table(row_clues)
173

174
    @lru_cache(maxsize=None)
175
    def dfs(col, s0, s1, s2, s3, s4):
176
        states = (s0, s1, s2, s3, s4)
177
        if col == WIDTH:
178
            ok = all(states[r] in accepts[r] for r in range(HEIGHT))
179
            return tuple() if ok else None
180

181
        for bits in col_cands[col]:
182
            nxt = []
183
            valid = True
184
            for r in range(HEIGHT):
185
                ns = trans[r][states[r]][bits[r]]
186
                if ns < 0:
187
                    valid = False
188
                    break
189
                nxt.append(ns)
190
            if not valid:
191
                continue
192
            tail = dfs(col + 1, nxt[0], nxt[1], nxt[2], nxt[3], nxt[4])
193
            if tail is not None:
194
                return (tuple(bits),) + tail
195
        return None
196

197
    path = dfs(0, starts[0], starts[1], starts[2], starts[3], starts[4])
198
    if path is None:
199
        raise ValueError("no satisfying board found")
200

201
    board = [[0] * WIDTH for _ in range(HEIGHT)]
202
    for c, col_bits in enumerate(path):
203
        for r in range(HEIGHT):
204
            board[r][c] = col_bits[r]
205
    return board
206

207

208
def board_to_submission_hex(board):
209
    bits = []
210
    for r in range(HEIGHT):
211
        bits.extend(board[r])
212
    bits.append(0)  # parser expects one extra trailing bit from 344th nibble; must be zero
213

214
    if len(bits) != 0x560:  # 1376
215
        raise ValueError("unexpected bit length for hex encoding")
216

217
    out = []
218
    for i in range(0, len(bits), 4):
219
        nib = (bits[i] << 3) | (bits[i + 1] << 2) | (bits[i + 2] << 1) | bits[i + 3]
220
        out.append(format(nib, "x"))
221
    return "".join(out)
222

223

224
def pretty(board):
225
    return "\n".join("".join("#" if board[r][c] else "." for c in range(WIDTH)) for r in range(HEIGHT))
226

227

228
def main():
229
    ap = argparse.ArgumentParser(description="Solve nonogram_gate by decoding and solving its nonogram clues.")
230
    ap.add_argument("binary", nargs="?", default="./nonogram_gate", help="path to challenge binary")
231
    ap.add_argument("--run", action="store_true", help="run the binary with computed hex")
232
    args = ap.parse_args()
233

234
    cipher = extract_cipher(args.binary)
235
    decoded = decode_clue_blob(cipher)
236
    row_clues, col_clues = parse_clues(decoded)
237
    board = solve_board(row_clues, col_clues)
238
    answer_hex = board_to_submission_hex(board)
239

240
    print(answer_hex)
241
    print()
242
    print(pretty(board))
243

244
    if args.run:
245
        p = subprocess.run(
246
            [args.binary],
247
            input=(answer_hex + "\n").encode(),
248
            stdout=subprocess.PIPE,
249
            stderr=subprocess.STDOUT,
250
            check=False,
251
        )
252
        print()
253
        print(p.stdout.decode(errors="replace"))
254

255

256
if __name__ == "__main__":
257
    main()

1
from copy import deepcopy
2

3
puzzle = """
4
########
5
#..#####
6
#.....##
7
#oo.oo##
8
#..#o..#
9
#......#
10
########
11
""".strip().split("\n")
12
puzzle = [list(x) for x in puzzle]
13

14
pos = (1, 1)
15

16
inp = ""
17
history = []
18
while True:
19
    print(inp)
20
    for (i, r) in enumerate(puzzle):
21
        for (j, v) in enumerate(r):
22
            x = v
23
            if (i, j) == pos:
24
                x = "x"
25
            print(x, end="")
26
        print()
27
    for c in input("> "):
28
        if c == "z":
29
            (puzzle, pos, inp) = history.pop()
30
            continue
31
        elif c in ("w", "a", "s", "d"):
32
            (dr, dc) = {"w": (-1, 0), "s": (1, 0), "a": (0, -1), "d": (0, 1)}[c]
33
            (nr, nc) = (pos[0] + dr, pos[1] + dc)
34
            hist = (deepcopy(puzzle), pos, inp)
35
            if puzzle[nr][nc] == "#":
36
                continue
37
            if puzzle[nr][nc] == "o":
38
                (nnr, nnc) = (nr + dr, nc + dc)
39
                if puzzle[nnr][nnc] != ".":
40
                    continue
41
                puzzle[nnr][nnc] = "o"
42
                puzzle[nr][nc] = "."
43
            pos = (nr, nc)
44
            history.append(hist)
45
            inp += c
46
        else:
47
            print("unknown")