WeChall - Lettergrid

Posted on In Views: Disqus:

Lettergrid (Coding) by gizmore 限时 word search——4.5 秒内找出网格中所有隐藏单词并按起始位置提交

Challenge

页面生成一个字母网格，需要在 4.5 秒内找出所有隐藏的单词（长度 >= 6，8 个直线方向），并按起始字母位置排序后提交。

1
2
3
Base:      https://www.wechall.net/challenge/lettergrid
Grid:      generate.php   → 返回 <pre> 格式的字母网格
Submit:    index.php?solution=<answer>&cmd=Submit+Answer  (GET)

答案格式：单词直接拼接，无分隔符（不是逗号分隔）。按单词起始位置（从上到下、从左到右）排序。

Solution

Trie 前缀树 + 8 方向扫描，单次运行 2-3 秒，远低于 4.5s 限时：

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
import requests, re

BASE = 'https://www.wechall.net/challenge/lettergrid'
sess = requests.Session()
sess.cookies.set('WC', '...', domain='www.wechall.net')

# 1. 构建 Trie（单词 >= 6 字符）
class TrieNode:
    __slots__ = ('children', 'is_word')
    def __init__(self):
        self.children = {}
        self.is_word = False

root = TrieNode()
for word in open('/usr/share/dict/words'):
    w = word.strip().lower()
    if len(w) >= 6:
        node = root
        for ch in w:
            node = node.children.setdefault(ch, TrieNode())
        node.is_word = True

# 2. 获取网格
r = sess.get(f'{BASE}/generate.php')
match = re.search(r'<pre>(.*?)</pre>', r.text, re.DOTALL)
grid = [list(line.strip().lower()) for line in match.group(1).strip().split('\n') if line.strip()]
ROWS, COLS = len(grid), len(grid[0])

# 3. 8 方向搜索（用 Trie 实时剪枝）
DIRS = [(0,1),(0,-1),(1,0),(-1,0),(1,1),(1,-1),(-1,1),(-1,-1)]
found = {}  # word -> (start_r, start_c)

for r in range(ROWS):
    for c in range(COLS):
        for dr, dc in DIRS:
            node, last_word, last_len = root, None, 0
            for step in range(max(ROWS, COLS)):
                nr, nc = r + dr*step, c + dc*step
                if not (0 <= nr < ROWS and 0 <= nc < COLS): break
                ch = grid[nr][nc]
                if ch not in node.children: break
                node = node.children[ch]
                if node.is_word:
                    word = ''.join(grid[r+dr*s][c+dc*s] for s in range(step+1))
                    if word not in found:
                        found[word] = (r, c)

# 4. 按起始位置排序后提交
answer = ''.join(sorted(found.keys(), key=lambda w: found[w]))
print(f'Found {len(found)} words: {sorted(found.keys())}')

r = sess.get(f'{BASE}/index.php', params={'solution': answer, 'cmd': 'Submit Answer'})
if 'solved' in r.text.lower() or 'correct' in r.text.lower():
    print('SOLVED!')

Key Points:

  • 无分隔符：单词按起始位置排序后直接拼接，不加逗号或空格
  • /challenge/lettergrid/：注意 URL 没有 /en/ 前缀
  • 网格来源：generate.php，每次刷新不同，必须同一 session 内抓取
  • 提交方式：GET 到 index.php?solution=...&cmd=Submit+Answer，不需要 CSRF
  • 标准词库：/usr/share/dict/words 或 dwyl/english-words 皆可，344K 单词 >= 6 字符足够覆盖
  • Trie 剪枝是关键：不用 Trie 的话搜索量是 网格数 × 方向 × 最大路径长度，用 Trie 可以实时过滤无效前缀
  • 答案 session-bound：每次网格不同，无固定答案