ARTICLE DETAIL

资讯详情

深耕郑州网站建设与运营推广的一线实战洞察。

用 TypeScript 类型系统验证数独是否已解:type-challenges 31797 Sudoku 全面解析

用 TypeScript 类型系统验证数独是否已解:type-challenges 31797 Sudoku 全面解析 示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载type-challenges 仓库中的 Sudoku31797hard 难度 要求你编写一个类型SudokuSolvedT在编译期判定一个给定的 9×9 数独盘面是否已经被完整且正确地解开。本文将带你从题目输入结构出发逐步推导出行、列、宫三条校验线在类型层面的提取与判重方法最终给出一个可通过仓库全部 8 组测试用例的完整实现并深入讲解递归条件类型、变长元组、矩阵转置等核心技巧。一、题目概览挑战背景与输入表示题目由 Bruno Ladeia 提出见 info.yml 的元数据标注难度为hard标签为union / array / tuple / game。README 中明确说明该题改编自 Advent of TypeScript 2023 的第 22 天挑战由 TypeHero 设计原题灵感来自经典的数独游戏规则。题目要求一句话概括就是编写一个类型验证一个数独游戏已被解出。在动手前先看题目的起点模板 template.tstype Digits 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 type SudokuSolved any模板只提供了两个东西Digits19 的字面量联合类型提示盘面单元格的合法取值SudokuSolved等待你实现的空壳当前为any。输入结构由 test-cases.ts 中的测试数据决定一个数独盘面被编码为9 行 × 3 个宫 × 3 个格子的三层嵌套元组。以第一个测试用例为例type test_sudoku_1_actual SudokuSolved[ [[1, 2, 3], [5, 6, 7], [4, 8, 9]], // 第 1 行3 个 3×3 宫 [[4, 8, 9], [1, 2, 3], [5, 6, 7]], [[5, 6, 7], [4, 8, 9], [1, 2, 3]], ... ]也就是说泛型参数T的类型形状是number[][][]T[行索引][宫索引][格索引]。9 行 × 3 宫 × 3 格恰好组成一个 9×9 的完整盘面且盘面中没有空格——已解出意味着每一个格子都已填入数字 19且满足数独规则。二、判定规则行、列、宫三条线都必须无重复数独的规则可以抽象为9 条横线行、9 条竖线列、9 个 3×3 方块宫中的每一条都必须恰好包含数字 19 各一次。由于题目保证盘面完整无空位恰好包含 19 各一次等价于更易实现的条件——一条线上 9 个数字两两不重复若一条线上存在重复数字则必然缺少某个 19 中的数字 → 非法若一条线上 9 个数字互不重复且每个格子取值来自 19则恰好覆盖 19 → 合法。因此整个解题的核心可以拆成三个子问题如何把一条线表示成一个 9 元组如何从嵌套结构T中抽出行、列、宫三类线如何判定一个元组内没有重复元素。三、测试用例分析8 组用例在考什么test-cases.ts 末尾第 99108 行定义了最终的断言type cases [ ExpectEqualtest_sudoku_1_actual, true, ExpectEqualtest_sudoku_2_actual, true, ExpectEqualtest_sudoku_3_actual, true, ExpectEqualtest_sudoku_4_actual, false, ExpectEqualtest_sudoku_5_actual, false, ExpectEqualtest_sudoku_6_actual, false, ExpectEqualtest_sudoku_7_actual, false, ExpectEqualtest_sudoku_8_actual, false, ]其中Expect与Equal来自仓库的测试工具包 utils/index.d.tsExpectT extends true只有在传入true时才通过编译。前 3 组是合法已解盘面应返回true后 5 组各有破绽应返回false。逐一核对可以看清每个破绽命中的校验维度用例期望破绽所在test_1true完整合法盘面test_2true完整合法盘面test_3true完整合法盘面test_4false第 7 行展平后为[2,3,1,6,4,5,8,9,4]数字 4 重复行违规test_5false第 7 行展平后为[5,9,1,6,2,3,2,4,8]数字 2 重复行违规test_6false第 1 行展平后为[8,9,7,3,6,1,1,4,5]数字 1 重复行违规test_7false左上角 3×3 宫为[1,2,3,2,3,5,3,5,6]2/3/5 重复宫违规test_8false9 行完全相同任一列都出现 9 次同一数字列违规值得注意的是第 46 组都在行维度上埋雷第 7 组在宫维度第 8 组在列维度——它们共同提醒我们三类线一条都不能漏检。四、从零搭建解决方案下面按先搭通用零件、再组装主类型的顺序逐步构造一个可运行、可通过全部用例的实现。第 1 步通用零件——元组判重判定一条线无重复用递归条件类型遍历元组把见过的元素累积进Seen一旦当前元素已在Seen中出现即返回truetype HasDuplicateT extends unknown[], Seen extends unknown[] [] T extends [infer F, ...infer R] ? F extends Seen[number] ? true : HasDuplicateR, [...Seen, F] : false type IsValidLineL extends unknown[] HasDuplicateL extends true ? false : true这里用到了两条关键机制递归条件类型 变长元组[infer F, ...infer R]每次拆出首元素F与剩余元组R[...Seen, F]累积已见元素Seen[number]索引访问将元组的所有元素合并成联合类型F extends Seen[number]即F 是否在已见集合中。需要留意一个细节该判重逻辑成立的前提是每个格子都是字面量数字类型。若盘面中出现宽泛的numbernumber extends 1 | 2 | …会判定为 false判重会失效——这也是题目刻意用字面量元组作为测试输入的原因。第 2 步提取行——展平 3 宫一行由 3 个宫组成展平后即 9 个数字type FlattenRowRow extends unknown[][], Acc extends unknown[] [] Row extends [infer F extends unknown[], ...infer R extends unknown[][]] ? FlattenRowR, [...Acc, ...F] : Acc再把 9 行整体映射一遍得到展平后的 9×9 矩阵type MapRowsT extends unknown[][][], Acc extends unknown[][] [] T extends [infer F extends unknown[][], ...infer R extends unknown[][][]] ? MapRowsR, [...Acc, FlattenRowF] : Acc第 3 步提取列——矩阵转置列比行麻烦需要从每一行中取相同下标的元素组成新元组。一个优雅的做法是矩阵转置把 9×9 矩阵转置后列就变成了行可以直接复用第 2 步的行校验。转置的递归思路是反复剥离每一行的首元素把它们收集成新的行type TransposeM extends unknown[][], Acc extends unknown[][] [] M extends [infer F extends unknown[], ...infer R extends unknown[][]] ? F extends [infer H, ...infer T] ? Transpose[...R, T], [...Acc, [H]] : never : Acc追踪一次小例子[[1,2,3],[4,5,6],[7,8,9]]经过三轮迭代后Acc依次收集[1]、[4]、[7]……最终得到[[1],[4],[7],[2],[5],[8],[3],[6],[9]]正是转置矩阵。它的本质是首列逐行出队 → 其余行队尾入队循环往复直到所有元素被重新排列。第 4 步提取宫——每三行取三个竖直宫宫是 3×3 方块以三行如第 02 行为一组把它们在同一列位置上的 3 个宫首尾拼接即可得到该组的 3 条宫线type GetBoxesT extends unknown[][][], Acc extends unknown[][] [] T extends [ infer A extends unknown[][], infer B extends unknown[][], infer C extends unknown[][], ...infer R extends unknown[][][], ] ? GetBoxes R, [ ...Acc, [...A[0], ...B[0], ...C[0]], [...A[1], ...B[1], ...C[1]], [...A[2], ...B[2], ...C[2]], ] : Acc每轮吞掉 3 行产出 3 条 9 元素宫线分别是该三行中第 0、1、2 列位置的竖直宫。3 轮迭代后正好得到全部 9 个宫。第 5 步组装主类型最后写一个逐条线校验的驱动器并串联行、列、宫三类校验type AllValidLines extends unknown[][], Acc extends boolean true Lines extends [infer F extends unknown[], ...infer R extends unknown[][]] ? AllValidR, Acc extends true ? IsValidLineF : false : Acc type SudokuSolvedT extends unknown[][][] AllValidMapRowsT extends true ? AllValidTransposeMapRowsT extends true ? AllValidGetBoxesT extends true ? true : false : false : falseAllValid用一个累积的boolean实现短路一旦某条线非法后续迭代直接返回false避免无谓的深度递归。整个SudokuSolved按行 → 列 → 宫三级嵌套展开任一环节非法即整体为false。五、完整实现与验证将上述零件合并就是一份可直接放进 template.ts 的完整答案type Digits 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 type HasDuplicateT extends unknown[], Seen extends unknown[] [] T extends [infer F, ...infer R] ? F extends Seen[number] ? true : HasDuplicateR, [...Seen, F] : false type IsValidLineL extends unknown[] HasDuplicateL extends true ? false : true type FlattenRowRow extends unknown[][], Acc extends unknown[] [] Row extends [infer F extends unknown[], ...infer R extends unknown[][]] ? FlattenRowR, [...Acc, ...F] : Acc type MapRowsT extends unknown[][][], Acc extends unknown[][] [] T extends [infer F extends unknown[][], ...infer R extends unknown[][][]] ? MapRowsR, [...Acc, FlattenRowF] : Acc type TransposeM extends unknown[][], Acc extends unknown[][] [] M extends [infer F extends unknown[], ...infer R extends unknown[][]] ? F extends [infer H, ...infer T] ? Transpose[...R, T], [...Acc, [H]] : never : Acc type GetBoxesT extends unknown[][][], Acc extends unknown[][] [] T extends [ infer A extends unknown[][], infer B extends unknown[][], infer C extends unknown[][], ...infer R extends unknown[][][], ] ? GetBoxes R, [ ...Acc, [...A[0], ...B[0], ...C[0]], [...A[1], ...B[1], ...C[1]], [...A[2], ...B[2], ...C[2]], ] : Acc type AllValidLines extends unknown[][], Acc extends boolean true Lines extends [infer F extends unknown[], ...infer R extends unknown[][]] ? AllValidR, Acc extends true ? IsValidLineF : false : Acc type SudokuSolvedT extends unknown[][][] AllValidMapRowsT extends true ? AllValidTransposeMapRowsT extends true ? AllValidGetBoxesT extends true ? true : false : false : false对照 test-cases.ts 中的 8 组用例逐一推演test_13行、列、宫 27 条线均无重复 →truetest_46各自某行存在重复数字4、2、1AllValidMapRowsT短路为false→falsetest_7左上宫[1,2,3,2,3,5,3,5,6]重复宫校验拦截 →falsetest_8行全相同转置后每列 9 个相同数字列校验拦截 →false。六、如何在本地运行与验证本仓库的每个挑战都由四个文件构成Sudoku 也不例外README.md题目描述template.ts需要填写的类型骨架test-cases.ts判定用的测试用例info.yml难度、标签、作者等元数据。按仓库根目录 README.md 的说明你可以在本地复现整个做题流程克隆仓库后执行pnpm install安装依赖再执行pnpm generate或带--keep-changes/-K参数保留你的修改并同步更新生成可在本地 IDE 中打开的 playground。将上面的完整实现写入template.ts用 TypeScript 编译器以严格模式检查test-cases.ts只要cases数组中的 8 组ExpectEqual...全部通过编译即证明实现正确。七、技术要点回顾与延伸这道 hard 题综合了类型层面多个高频技巧值得逐条沉淀递归条件类型是类型级编程的循环几乎所有结构化遍历判重、展平、映射、转置都依赖[infer F, ...infer R]的拆解-递归模式变长元组variadic tuple用于携带状态[...Seen, F]、[...Acc, ...F]让每次递归都能携带已计算的结果实现累加器式的函数式写法索引访问Seen[number]将元组折叠为联合类型配合extends即可实现成员判定这是判重类题目的标准套路矩阵转置的思路可以复用把取列转化为取行大幅降低实现复杂度该技巧同样出现在本仓库的 25270-medium-transpose 等题目中短路累积布尔值控制递归深度一旦发现非法线立刻收敛为false是控制类型实例化开销的实用手法。如果你还想在数独主题上继续精进仓库中还有一道同属#game标签的姊妹题 35314-hard-valid-sudoku校验一个含空格盘面是否有效而非已解出两者的校验维度行/列/宫一致但输入允许0占位边界处理值得对比体会。总而言之SudokuSolved是一次把领域规则翻译成类型约束的绝佳练习它证明 TypeScript 类型系统不仅能描述数据形状还能在编译期执行真实的业务校验逻辑——这也正是 type-challenges 项目希望通过一个个挑战帮你建立的类型直觉。赞分享示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载相关推荐三个问题定下 YOLO 多目标跟踪部署BoxMOT 完整跟踪部署实践三个问题定下 YOLO 多目标跟踪部署BoxMOT 完整跟踪部署实践 BoxMOT 是一个可插拔的多目标跟踪框架可与 YOLO 系列检测器直接搭配。它内置人工智能计算机视觉深度学习Type Challenges 3060用 TypeScript 类型系统实现 Array.unshiftType Challenges 3060用 TypeScript 类型系统实现 Array.unshift type challenges 仓库的第 3060示例工程用 TypeScript 类型系统实现数组反转type-challenges 3192 Reverse 深入解析用 TypeScript 类型系统实现数组反转type challenges 3192 Reverse 深入解析 Reverse 是 type challen示例工程上一篇Gutenberg 核心评论回复链接块core/comment-reply-link深度解析动态渲染、上下文继承与主题支持配置下一篇Karpenter NodePool 完全指南从节点模板、调度约束到中断与资源限额创作声明:本文部分内容由AI辅助生成(AIGC),仅供参考
返回列表