HackThisSite - Programming Mission 6

Posted on In Views: Word count in article: 2.8k Reading time ≈ 10 mins.
HackThisSite - Programming Mission 6 的题目分析与方法记录，涉及 hackthissite, programming, captcha, ocr, vector-graphics。

Challenge

Bypass the image captcha

This level is about OCR. Write a program which is able to read all the characters in the given image, and let it beat this image captcha automatically. Type in all characters from the image which you can find HERE. Begin from the innermost character and continue clockwise. You have 30 seconds time to send the solution.

Solution

Step 1: 端点数据

实例页 https://www.hackthissite.org/missions/prog/6/ 里的链接指向 /missions/prog/6/image。直接 GET 它拿到的是 HTML（Content-Type: text/html）， 内容是真正的 drawIt()（完整数组约 3350 个整数，下面只列开头）。这意味着题目虽然把它描述成 OCR， 但客户端拿到的并不是一张 PNG，而是可以直接重建的绘图指令；“随螺旋倒置”的字符只是整体旋转， 不需要把倒置字符单独当作另一套字形：先按极角把每个字符旋回统一方向，再识别即可。

常规 OCR 在本题的螺旋排列上不稳定。下面按连通域切分、按极角旋转归一化，再对矢量字形做模板匹配。

1
2
3
4
5
6
$ curl -sL -b '<mission-cookie>' 'https://www.hackthissite.org/missions/prog/6/image/'
\r\n<html>\r\n<head>\r\n\r\n<script type="text/javascript">\r\n<!--\r\n
var strHTML = "";\t\r\n
function drawIt()\r\n{\r\n
  var drawData = new Array(565,623,565,618,768,354,757,364,520,643,528,645,
  794,563,782,556,658,452,672,448,700,663,697,656,490,519,486,520,363,464,

Step 2: 图元与字形

把图元按原样画进一张 idmap[x][y] = 第几个图元 的栅格图，然后对栅格做 8 邻域洪泛： 连成一片的像素就是一个字形，顺便把该字形用到的图元 id 全部收集起来。 这样字形切分完全不依赖列投影之类的排版假设，对螺旋上各种朝向的字形都成立。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
import math
import re
import time

import numpy as np
import requests
from scipy.spatial import cKDTree

BASE = "https://www.hackthissite.org"
N_CHARS = 253
STEP = 0.35                      # point-cloud sampling spacing, in device px


def session(cookie):
    s = requests.Session()
    s.headers.update({
        "User-Agent": "Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 "
                      "(KHTML, like Gecko) Chrome/131.0.0.0 Safari/537.36",
        "Cookie": cookie,
        "Referer": BASE + "/missions/programming/",
    })
    return s


def fetch_drawdata(s):
    """Instance page -> captcha URL -> the flat drawData array. Timer starts here."""
    page = s.get(BASE + "/missions/prog/6/", timeout=20).text
    hit = re.search(r'(?:href|src)="([^"]*prog/6/image[^"]*)"', page)
    url = hit.group(1) if hit else "/missions/prog/6/image"
    if not url.endswith("/"):
        url += "/"               # bare path 301s but the redirect body is empty
    if url.startswith("/"):
        url = BASE + url
    html = s.get(url, timeout=20,
                 headers={"Referer": BASE + "/missions/prog/6/"}).text
    m = re.search(r"new Array\(([^)]*)\)", html, re.S)
    return [int(x) for x in re.findall(r"-?\d+", m.group(1))]


def primitives(data):
    """Split drawData exactly the way drawIt() does: 4 ints = line, 5 ints = arc."""
    i, out = 0, []
    while i + 2 < len(data):
        if data[i + 2] >= 10:
            out.append(("L", *[float(v) for v in data[i:i + 4]]))
            i += 4
        else:
            out.append(("A", *[float(v) for v in data[i:i + 5]]))
            i += 5
    return out


def rasterize(prims, w, h):
    """idmap[x][y] = index of the primitive that painted that pixel."""
    idmap = [[-1] * h for _ in range(w)]
    for idx, p in enumerate(prims):
        if p[0] == "L":
            x1, y1, x2, y2 = p[1:5]
            n = max(2, int(math.hypot(x2 - x1, y2 - y1) * 2))
            pts = [(x1 + (x2 - x1) * t / n, y1 + (y2 - y1) * t / n)
                   for t in range(n + 1)]
        else:
            x0, y0, r, s, e = p[1:6]
            n = max(2, int(abs(e) / 4.0))
            pts = [(x0 + r * math.cos(math.radians(s + e * t / n)),
                    y0 - r * math.sin(math.radians(s + e * t / n)))
                   for t in range(n + 1)]
        for fx, fy in pts:
            xx, yy = int(round(fx)), int(round(fy))
            if 0 <= xx < w and 0 <= yy < h:
                idmap[xx][yy] = idx
    return idmap


def glyphs(idmap):
    """8-neighbour flood fill: one connected blob = one character."""
    w, h = len(idmap), len(idmap[0])
    seen = [[False] * h for _ in range(w)]
    out = []
    for sx in range(w):
        for sy in range(h):
            if idmap[sx][sy] < 0 or seen[sx][sy]:
                continue
            stack, pts, ids = [(sx, sy)], [], set()
            seen[sx][sy] = True
            while stack:
                x, y = stack.pop()
                pts.append((x, y))
                ids.add(idmap[x][y])
                for dx in (-1, 0, 1):
                    for dy in (-1, 0, 1):
                        nx, ny = x + dx, y + dy
                        if (0 <= nx < w and 0 <= ny < h and not seen[nx][ny]
                                and idmap[nx][ny] >= 0):
                            seen[nx][ny] = True
                            stack.append((nx, ny))
            if len(pts) >= 4:                       # drop 1-3 px specks
                xs = [q[0] for q in pts]
                ys = [q[1] for q in pts]
                out.append({"ids": sorted(ids),
                            "cx": sum(xs) / len(xs),
                            "cy": sum(ys) / len(ys),
                            "n": len(pts)})
    return out

Step 3: 螺旋排序

题面已经给了读序：从最内层开始，顺时针。字形落在一条对数螺旋上：每 10 度放一个字形， 半径每步乘 1.005。于是读序 = 第几圈（半径）主序 + 圈内第几个（角度）次序。

先网格搜索螺旋中心：让所有字形的极角落进 10 度格子（最内圈的几个字形半径太小、 角度噪声大，直接跳过不参与打分）。再把序号 \(k = j + 36m\)（\(j\) 为圈内角序，\(m\) 为圈号）迭代拟合 \(\ln r = A + B \cdot k\)（\(B = \ln 1.005\)），直到分配稳定：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
from collections import Counter

B_LOG = math.log(1.005)


def fit_center(gs, init):
    """Grid-search the spiral centre so every glyph angle lands on the 10-deg lattice."""
    def score(cx, cy):
        tot, cnt = 0.0, 0
        for g in gs:
            if math.hypot(g["cx"] - cx, g["cy"] - cy) < 150:
                continue
            ang = math.degrees(math.atan2(g["cy"] - cy, g["cx"] - cx))
            tot += abs((ang + 5.0) % 10.0 - 5.0) ** 2
            cnt += 1
        return tot / max(1, cnt)

    best = (score(*init), init[0], init[1])
    for span, step in ((80.0, 1.0), (4.0, 0.2), (0.6, 0.05)):
        x0, y0 = best[1], best[2]
        x = x0 - span
        while x <= x0 + span:
            y = y0 - span
            while y <= y0 + span:
                sc = score(x, y)
                if sc < best[0]:
                    best = (sc, x, y)
                y += step
            x += step
    return best[1], best[2]


def order_glyphs(gs, cx, cy):
    """k = angle index + 36 * turn; k = 0 is the innermost glyph, k grows clockwise."""
    for g in gs:
        g["r"] = math.hypot(g["cx"] - cx, g["cy"] - cy)
        g["ang"] = math.degrees(math.atan2(g["cy"] - cy, g["cx"] - cx)) % 360.0
        g["slot"] = int(round(g["ang"] / 10.0)) % 36
    cnt = Counter(g["slot"] for g in gs)
    j0 = max(cnt, key=lambda s: cnt[s])       # innermost slot holds the extra glyph
    for g in gs:
        g["j"] = (g["slot"] - j0) % 36
    A = math.log(min(g["r"] for g in gs))
    for _ in range(8):                        # iterate ln r = A + B*k
        for g in gs:
            m = round((math.log(g["r"]) - A - B_LOG * g["j"]) / (36.0 * B_LOG))
            m = min(max(m, 0), 7)
            k = g["j"] + 36 * m
            g["k"] = k if 0 <= k <= N_CHARS - 1 else None
        pts = [(g["k"], math.log(g["r"])) for g in gs if g["k"] is not None]
        n = len(pts)
        mk = sum(a for a, b in pts) / n
        mr = sum(b for a, b in pts) / n
        slope = (sum((a - mk) * (b - mr) for a, b in pts)
                 / sum((a - mk) ** 2 for a, b in pts))
        A = mr - slope * mk
    return sorted([g for g in gs if g["k"] is not None], key=lambda g: g["k"])

Step 4: 原型提取

字符集是大写十六进制（0123456789ABCDEF），而且字形是矢量定义的：同一个字符的路径 形状每次完全一样，只是被整体旋转过（旋转角等于它所在位置的极角 + 90 度，让字形的上 朝外）。所以只要把每个字形转回标准朝向，同一字符的点云就能完全重合。

做法：把每个字形的图元绕自身中心反向旋转 -(ang + 90) 度，再把图元采成点云、 减去自身均值（消掉平移），就得到朝向归一化的点云。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
def rotate_prim(p, cx, cy, deg):
    """Rotate a primitive about (cx, cy) by deg degrees in screen coords."""
    th = math.radians(deg)
    c, s = math.cos(th), math.sin(th)

    def R(x, y):
        dx, dy = x - cx, y - cy
        return (cx + dx * c - dy * s, cy + dx * s + dy * c)

    if p[0] == "L":
        x1, y1 = R(p[1], p[2])
        x2, y2 = R(p[3], p[4])
        return ("L", x1, y1, x2, y2)
    x, y = R(p[1], p[2])
    return ("A", x, y, p[3], p[4] - deg, p[5])   # the start angle shifts too


def sample(prims):
    """Sample canonical primitives to a point cloud, centred on its own mean."""
    pts = []
    for p in prims:
        if p[0] == "L":
            x1, y1, x2, y2 = p[1:5]
            n = max(2, int(math.hypot(x2 - x1, y2 - y1) / STEP))
            pts += [(x1 + (x2 - x1) * t / n, y1 + (y2 - y1) * t / n)
                    for t in range(n + 1)]
        else:
            x0, y0, r = p[1:4]
            s, e = p[4:6] if p[0] == "A" else (0.0, 360.0)
            n = max(2, int(abs(e) / 4.0))
            pts += [(x0 + r * math.cos(math.radians(s + e * t / n)),
                     y0 - r * math.sin(math.radians(s + e * t / n)))
                    for t in range(n + 1)]
    a = np.array(pts, dtype=np.float64)
    a -= a.mean(0)
    return a


def cloud(g):
    """Orientation-normalised point cloud of one glyph."""
    ang = round(g["ang"] / 10.0) * 10.0
    return sample([rotate_prim(p, g["cx"], g["cy"], -(ang + 90.0))
                   for p in g["prims"]])

离线阶段把 253 个点云两两算 Chamfer 距离、做完全连接层次聚类，t = 0.80 正好切出 16 类，和字符集大小一致（这一步本身就是 16 类假设的验证：多一类少一类都说明阈值错了）。 每类取 medoid（到同类其他成员平均距离最小的那个字形）作为原型，把 16 个原型打成 ASCII 点阵人眼看一遍，就得到标签表。下面是复核过的其中两个原型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
label=8  medoid=k1            label=4  medoid=k38
  |..#####..                    |....#...
  |..#...##.                    |.#..#...
  |.#.....#.                    |.#..#...
  |.#.....#.                    |.#..#...
  |..#...#..                    |#...#...
  |..#####..                    |########
  |.##....#.                    |....#...
  |.#......#                    |....#...
  |#.......#                    |....#...
  |#.......#                    |....#...
  |.#......#                    |....#...
  |.##...##.                    |....#...
  |...####..                    |....#...

16 个原型全部人工确认过一次。原型存成 templates_gen.py，

Step 5: 模板分类

点云之间用对称 Chamfer 距离比形状：对每个点找另一方最近点的距离，两个方向取平均。 比位图 IoU 更耐受采样密度差异，也不需要对齐网格。

完整的 templates_gen.py 内容如下。它是被 solve.py 导入的纯数据模块。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# auto-generated canonical glyph templates (relative to cloud mean)
TEMPLATES = {
    '0': [
        ('A', -0.26, 3.31, 4.00, 180.00, 180.00),
        ('L', -3.46, -3.15, -3.86, 3.54),
        ('A', 0.14, -3.38, 4.00, 360.00, 180.00),
        ('L', 3.34, 3.08, 3.74, -3.62),
    ],
    '1': [
        ('L', 0.46, -7.29, -2.54, -3.29),
        ('L', 0.46, -7.29, 0.46, 6.71),
        ('L', -2.54, 6.71, 3.46, 6.71),
    ],
    '2': [
        ('L', 4.03, -3.38, -3.91, 6.96),
        ('A', -0.07, -2.95, 4.00, 0.00, 180.00),
        ('L', -3.91, 6.96, 4.63, 7.05),
    ],
    '3': [
        ('L', -2.53, -1.73, -1.53, -1.73),
        ('A', -1.53, 2.27, 4.00, 225.00, 230.00),
        ('A', -1.53, -4.73, 3.00, 270.00, 225.00),
    ],
    '4': [
        ('L', -1.51, -6.14, -3.21, 0.87),
        ('L', -3.21, 0.87, 4.39, 1.29),
        ('L', 0.72, -5.89, 0.46, 8.04),
    ],
    '5': [
        ('L', -2.32, -2.11, 0.50, -1.86),
        ('L', 3.81, -7.25, -2.59, -7.10),
        ('L', -2.32, -2.11, -2.59, -7.10),
        ('A', 0.13, 2.36, 4.00, 180.00, 270.00),
    ],
    '6': [
        ('L', -3.31, -0.43, 1.69, -9.09),
        ('O', 0.16, 1.57, 4.00),
    ],
    '7': [
        ('L', 0.99, 1.85, -3.47, 1.58),
        ('L', 2.76, -5.21, -3.94, -5.61),
        ('L', 2.76, -5.21, -1.64, 8.41),
    ],
    '8': [
        ('O', -0.06, -4.25, 3.00),
        ('O', 0.17, 2.82, 4.00),
    ],
    '9': [
        ('L', -1.66, 8.64, 2.36, 0.52),
        ('O', -0.12, -1.44, 4.00),
    ],
    'A': [
        ('L', 0.22, -7.18, 5.84, 7.01),
        ('L', -5.34, 7.07, 0.22, -7.18),
        ('L', 3.12, -0.58, -2.96, -0.64),
    ],
    'B': [
        ('L', -4.42, -6.64, -4.17, 7.28),
        ('L', -4.42, -6.64, 0.96, -6.81),
        ('L', -4.17, 7.28, 1.21, 7.11),
        ('A', 0.36, 3.61, 4.00, -90.00, 180.00),
        ('A', 0.87, -3.65, 4.00, -90.00, 180.00),
        ('L', 0.79, -0.49, -3.66, 0.02),
    ],
    'C': [
        ('A', 2.35, 0.31, 7.00, 55.00, 255.00),
    ],
    'D': [
        ('A', -0.29, 0.22, 7.00, 270.00, 180.00),
        ('L', -4.29, -6.71, -4.35, 7.18),
        ('L', 0.17, -6.98, -4.29, -6.71),
        ('L', -4.35, 7.18, 0.11, 6.91),
    ],
    'E': [
        ('L', -2.63, 7.00, 5.37, 7.00),
        ('L', -2.63, 7.00, -2.63, -7.00),
        ('L', 5.37, -7.00, -2.63, -7.00),
        ('L', -2.63, 0.00, 4.37, 0.00),
    ],
    'F': [
        ('L', -2.19, 1.77, 4.51, 1.37),
        ('L', -1.79, 8.47, -1.73, -5.43),
        ('L', -1.73, -5.43, 6.34, -5.46),
    ],
}

分类函数在 solver 中使用这些模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def classify(order, templates):
    tchars = sorted(templates)
    tclouds = {c: sample(templates[c]) for c in tchars}
    trees = {c: cKDTree(tclouds[c]) for c in tchars}
    chars, margins = [], []
    for g in order:
        c = cloud(g)
        ct = cKDTree(c)
        ranked = sorted((0.5 * (trees[t].query(c)[0].mean()
                                + ct.query(tclouds[t])[0].mean()), t)
                        for t in tchars)
        chars.append(ranked[0][1])
        margins.append(ranked[1][0] - ranked[0][0])
    return "".join(chars), min(margins)

Step 6: 在线 Solver

30 秒限时从实例页生成那一刻开始算，所以不能拆成几步手工执行，必须一个进程内完成， 而且 POST 前要重新算一次时间预算。给足余量后：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def solve_once(cookie, dry=False):
    s = session(cookie)
    t0 = time.time()

    data = fetch_drawdata(s)                                  # timer starts here
    prims = primitives(data)
    w = int(max(p[1] for p in prims)) + 30
    h = int(max(p[2] for p in prims)) + 30
    gs = glyphs(rasterize(prims, w, h))
    init = (sum(g["cx"] for g in gs) / len(gs),
            sum(g["cy"] for g in gs) / len(gs))
    cx, cy = fit_center(gs, init)
    order = order_glyphs(gs, cx, cy)
    for g in order:
        ids = set(g["ids"])
        g["prims"] = [p for i, p in enumerate(prims) if i in ids]
    answer, margin = classify(order, TEMPLATES)
    if len(answer) != N_CHARS or any(c not in "0123456789ABCDEF" for c in answer):
        raise RuntimeError("incomplete or invalid glyph sequence")
    t_solve = time.time()
    if t_solve - t0 >= 25:
        raise RuntimeError("insufficient submission time budget")

    if dry:
        return answer, t_solve - t0
    resp = s.post(BASE + "/missions/prog/6/index.php",
                  data={"solution": answer, "submitbutton": "submit"},
                  timeout=30, headers={"Referer": BASE + "/missions/prog/6/"}).text
    ok = "successfully completed" in resp or "Congrats" in resp
    return answer, time.time() - t0, ok


def main(cookie):
    answer, t_fetch_solve = solve_once(cookie, dry=True)
    print("fetch+solve %.2fs  len=%d  margin>=%.2f"
          % (t_fetch_solve, len(answer), 0.0))
    answer, total, ok = solve_once(cookie)
    print("total %.2fs  accepted=%s" % (total, ok))

上面的 Python 块按顺序拼入同一个 solve6.py，TEMPLATES 也在该文件内；依赖为 requests、numpy 和 scipy。补上运行入口：

1
2
3
4
5
6
if __name__ == "__main__":
    import os
    cookie = os.environ.get("HTS_COOKIE")
    if not cookie:
        raise SystemExit("HTS_COOKIE is required")
    main(cookie)

圆模板 O 是完整的 360 度圆，不带弧起始角；采样器必须与 A 弧分开处理。