WeChall - Letterworm

Posted on In Views: Disqus:

Challenge

WeChall 上的 Letterworm（Coding），Lettergrid 的变体。单词在网格中可以中途改变方向（Boggle-style zigzag），不再是直线扫描。限时 4.5 秒提交，答案按起点 (row, col) 排序，逗号分隔。最小长度 6 字符。

Solution

核心思路：Trie 剪枝的 DFS。流程：

  1. 从 73h_vordz.php 获取候选词表（97 个计算机/编程相关单词）
  2. 从 generate.php 获取网格（iframe 内嵌，<pre> 标签包裹）
  3. 用词表构建 Trie
  4. 从每个格子出发 DFS 8 方向搜索，Trie 提前剪枝
  5. 去除真子串（如 "program" 存在时移除 "programs"... 此题其实不需要）
  6. 按起点 (row, col) 升序排列，逗号拼接提交
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
#!/usr/bin/env python3
"""Letterworm solver — Trie + DFS, sub-4.5s"""
import requests, re, time
from urllib.parse import quote

BASE = "http://www.wechall.net/challenge/letterworm"
COOKIE = {"WC": "your_cookie"}
UA = "Mozilla/5.0 Chrome/131"

class TrieNode:
    __slots__ = ('children', 'is_word')
    def __init__(self):
        self.children = {}
        self.is_word = False

# 1. Fetch wordlist (cached per session)
t0 = time.time()
sess = requests.Session()
sess.headers.update({"User-Agent": UA})
sess.cookies.update(COOKIE)

r = sess.get(f"{BASE}/73h_vordz.php", timeout=5)
words = [w.strip().lower() for w in r.text.strip().split('\n') if w.strip()]
root = TrieNode()
for w in words:
    node = root
    for ch in w:
        node = node.children.setdefault(ch, TrieNode())
    node.is_word = True
print(f"Wordlist: {len(words)} words")

# 2. Fetch grid (starts the 4.5s timer!)
r = sess.get(f"{BASE}/generate.php", timeout=5)
m = re.search(r'<pre>(.*?)</pre>', r.text, re.DOTALL)
grid = [l.strip().lower() for l in m.group(1).split('\n')
        if l.strip() and all(c.isalpha() for c in l.strip())]
ROWS, COLS = len(grid), len(grid[0])
print(f"Grid: {ROWS}x{COLS}")

# 3. DFS search
DIRS = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
found = {}  # word -> (r0, c0)

for r0 in range(ROWS):
    for c0 in range(COLS):
        ch = grid[r0][c0]
        if ch not in root.children:
            continue
        stack = [(r0, c0, root.children[ch], frozenset([(r0, c0)]), ch)]
        while stack:
            cr, cc, node, vis, word = stack.pop()
            if node.is_word and word not in found:
                found[word] = (r0, c0)
            for dr, dc in DIRS:
                nr, nc = cr + dr, cc + dc
                if 0 <= nr < ROWS and 0 <= nc < COLS and (nr, nc) not in vis:
                    nch = grid[nr][nc]
                    if nch in node.children:
                        stack.append((nr, nc, node.children[nch],
                                     vis | frozenset([(nr, nc)]), word + nch))

print(f"Found: {len(found)} words in {time.time()-t0:.3f}s")

# 4. Sort and submit
answer = ','.join(sorted(found, key=lambda w: found[w]))
r = sess.get(f"{BASE}/index.php", params={"solution": answer, "submit": "Submit"})
print("Correct!" if "Correct after" in r.text else f"Failed: {r.text[:200]}")
  • 词表来源：73h_vordz.php（= "the_words" leet），gitignored 但 live server 可访问。共 97 个计算机/编程单词，不是全量英语词典
  • 4.5 秒时限：从 generate.php 调用开始计时。本地 Trie 构建 + DFS 不到 10ms，瓶颈在网络延迟
password,program,partition,evaluate