CodeShell.kr - No Show

Posted on In Views: Disqus:

Challenge

一个 sqlite 数据库与一份重放规则，题面说房间是空的。难点在于要先排除「藏数据」路线，才能确认答案就是重放结果本身。

An empty room

一间空房。

1
https://codeshell.kr/challenges/misc-no-show/

Solution

附件含 room.sqlite 与规则：房间初始为空，booking_events 表乱序存储，按 seq 升序重放 BOOK / RELEASE / MOVE。

Step 1：先排除"藏数据"路线：integrity_check 通过、freelist_count = 0、文件正好 6 页（无 WAL/journal、无尾部附加数据），grep -a CodeShell 无命中。

Step 2：重放 611 条事件，得到 7×35 的占用位图，并断言所有格子取值都在 {0,1}（事件流自洽，无需猜测冲突处理）。

Step 3：7 行正好是 5×7 点阵字体的高度，35 列按 5 列宽切分读出字形：

1
2
3
4
5
6
7
8
#...# .###. .#### #...# .###. #...#
##..# #...# #.... #...# #...# #...#
#.#.# #...# #.... #...# #...# #.#.#
#..## #...# .###. ##### #...# #.#.#
#...# #...# ....# #...# #...# #.#.#
#...# #...# ....# #...# #...# ##.##
#...# .###. ####. #...# .###. #...#
  N     O          S     H     O     W

即 NO SHOW。

Script

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
#!/usr/bin/env python3
"""CodeShell.kr - No Show (Misc, 100p) solver.

The room starts empty and booking_events is stored out of order; replaying
BOOK / RELEASE / MOVE by ascending seq gives the final occupancy bitmap.  The
assertion that every cell ends up in {0,1} is what shows the event stream is
self-consistent and no conflict policy has to be guessed.
"""
import sqlite3

DB = "extracted/misc-no-show/room.sqlite"


def main():
    c = sqlite3.connect(DB)
    rows, seats = c.execute("SELECT rows, seats_per_row FROM room").fetchone()
    ev = list(c.execute(
        "SELECT seq, action, src_row, src_seat, dst_row, dst_seat "
        "FROM booking_events ORDER BY seq"))

    occ = [[0] * seats for _ in range(rows)]
    for _, act, sr, ss, dr, ds in ev:
        if act == "BOOK":
            occ[dr][ds] += 1
        elif act == "RELEASE":
            occ[sr][ss] -= 1
        else:
            occ[sr][ss] -= 1
            occ[dr][ds] += 1

    assert {v for r in occ for v in r} <= {0, 1}
    for r in occ:
        print("".join("#" if v else "." for v in r))


if __name__ == "__main__":
    main()
CodeShell{NOSHOW}