开发工具测试【免费下载链接】fast-checkProperty based testing framework for JavaScript (like QuickCheck) written in TypeScript项目地址https://gitcode.com/gh_mirrors/fa/fast-check点击查看免费下载导读本文基于 fast-check 官方博客《Advent of PBT 2024 · Day 18》挑战完整还原圣诞老人最短旅程规划器这道命题精灵们用贪心最近邻算法实现了一条从原点出发、遍历所有收货点并返回原点的最优路线规划而你需要借助 fast-check 的属性测试能力在茫茫输入空间中找出让该实现翻车的反例。读完本文你将掌握如何把旅行商问题TSP这类组合优化问题转化为可验证的属性property学会用fc.integer、fc.record、fc.array组合生成带约束的测试数据并通过对照参考实现的方式自动发现启发式算法的缺陷。挑战背景圣诞老人的最短旅程问题原文档 index.md 给出了完整的题目设定每年圣诞老人都要从自己的家坐标(0, 0)出发拜访全球各地的小孩再回到家中。每多跑一公里就多一分延误圣诞的风险因此最小化总路程至关重要。精灵们设计的雪橇系统工作流程如下圣诞老人输入需要拜访的所有房子的列表每个房子用一对坐标(x, y)表示其中x、y都是0 到 1000 之间的整数雪橇计算一条从圣诞老人家出发、依次拜访每栋房子、最后返回圣诞老人家的最短路线。两地之间的距离采用圣诞老人专属的度量方式——曼哈顿距离Math.abs(houseA.x - houseB.x) Math.abs(houseA.y - houseB.y)精灵们宣称今年算法万无一失圣诞老人则心存疑虑于是请你用 fast-check 的**属性测试property-based testing**能力找到能令该算法产生错误结果的输入在平安夜前救下圣诞节。问题形式化带曼哈顿距离的旅行商问题将题目抽象后这实际上是一个经典的**旅行商问题TSP**变体节点集合圣诞老人家(0, 0)加上若干房子(x, y)边权曼哈顿距离L1 距离目标找出一条从(0, 0)出发、恰好访问每个房子一次、最终回到(0, 0)的闭环使得环路总长度最小。由于曼哈顿距离不满足直线最短的直觉它本质上是只能沿网格方向行走的距离贪心策略很容易被局部最优误导——这正是本次挑战埋下的伏笔。与欧氏距离 TSP 一样该问题的精确求解复杂度是指数级的需要穷举排列但本题的房子数量由输入控制参考实现便采用了暴力穷举。精灵们的实现贪心最近邻算法仓库中的 buggy.mjs 就是精灵们交付的问题实现。它的策略非常直观每次从当前位置出发挑选距离最近、且尚未拜访的房子直到拜访完所有房子最后返回圣诞老人家。// ts-check /** typedef {{ x: number, y: number }} House */ /** * param {House[]} houses * returns {House[]} */ export default function findOptimalJourney(houses) { const santaHouse { x: 0, y: 0 }; const toVisit [...houses]; const journey [santaHouse]; let lastHouse santaHouse; while (toVisit.length ! 0) { let closestIndex 0; let closestDistance distance(lastHouse, toVisit[0]); for (let i 1; i toVisit.length; i) { const currentDistance distance(lastHouse, toVisit[i]); if (currentDistance closestDistance) { closestIndex i; closestDistance currentDistance; } } lastHouse toVisit[closestIndex]; toVisit.splice(closestIndex, 1); journey.push(lastHouse); } journey.push(santaHouse); return journey; } /** * param {House} houseA * param {House} houseB * returns {number} */ function distance(houseA, houseB) { return Math.abs(houseA.x - houseB.x) Math.abs(houseA.y - houseB.y); }从源码可以清楚看到它的两个特点贪心决策while循环内每次都线性扫描剩余房子选出距离lastHouse最近的节点closestIndex然后splice移除并加入旅程平局策略当多个房子距离相同时currentDistance closestDistance的严格小于比较会保留第一个遇到的房子即平局时倾向于下标更小的那个——这会让结果依赖输入顺序。贪心最近邻是 TSP 最经典的启发式之一但它不保证全局最优当前一步看起来最省的选择可能迫使后续付出更大的绕行代价。一个手工反例考虑如下三个房子坐标均在合法范围[0, 1000]内1,0 0,1 2,1精灵实现的贪心路线为每次选最近的未拜访点(0,0) → (1,0) → (0,1) → (2,1) → (0,0)总距离 1 2 2 3 8。而最优路线其实是(0,0) → (1,0) → (2,1) → (0,1) → (0,0)总距离 1 2 2 1 6。贪心算法多跑了 2 个单位它在(1,0)处选择了距离同样为 2 的(0,1)因为下标更靠前却没想到先拜访(2,1)能省下返回(0,0)的最后一程。类似地(1,0)、(0,1)、(2,2)也能构成反例贪心 10 vs 最优 8。这就是该实现需要被属性测试抓出来的缺陷。参考实现穷举搜索的标准答案同目录下的 AdventOfTheDay.tsx 中嵌入了参考实现它采用递归穷举所有拜访顺序比较每种顺序的总距离含返回(0,0)的一段选出最优解type House { x: number; y: number }; const santaHouse { x: 0, y: 0 }; function findOptimalJourneyInternal(houses: House[], lastHouse: House): { journey: House[]; distance: number } { if (houses.length 0) { return { journey: [lastHouse], distance: distance({ ...santaHouse }, lastHouse) }; } let bestMatchDistance: number Number.POSITIVE_INFINITY; let bestMatchJourney: House[] []; for (let i 0; i ! houses.length; i) { const fromLastHouse distance(lastHouse, houses[i]); const otherHouses houses.slice(); otherHouses.splice(i, 1); const rec findOptimalJourneyInternal(otherHouses, lastHouse); if (bestMatchDistance rec.distance fromLastHouse) { bestMatchDistance rec.distance fromLastHouse; bestMatchJourney rec.journey; } } return { journey: [lastHouse, ...bestMatchJourney], distance: bestMatchDistance, }; } function findOptimalJourney(houses: House[]): House[] { return findOptimalJourneyInternal(houses, { ...santaHouse }).journey; } function distance(houseA: House, houseB: House) { return Math.abs(houseA.x - houseB.x) Math.abs(houseA.y - houseB.y); }这段代码的要点递归枚举findOptimalJourneyInternal每次从剩余房子中取出一个作为下一站递归求解子问题取总距离最小者含返程的代价基线情形没有剩余房子返回distance({ ...santaHouse }, lastHouse)即从最后一站返回圣诞老人家的距离因此其distance度量是完整闭环的代价正确但昂贵复杂度为O(n!)n 稍大即不可行但它提供了判定精灵实现是否正确的黄金标准。参考实现的角色正是属性测试中的测试预言test oracle对一个随机生成的房子列表精灵实现的路线总距离必须等于穷举最优解的总距离否则即发现缺陷。用 fast-check 寻找反例属性测试实战有了参考实现这个预言属性就非常自然无论输入什么样的房子列表贪心实现的闭环总距离都不应大于穷举最优解的闭环总距离若精灵算法真如宣称的最优两者必须相等。第一步构造输入任意值Arbitraries根据题目约束每个坐标是 0 到 1000 之间的整数可以组合三个 fast-check 内置任意值构造器fc.integer({ min: 0, max: 1000 })生成[0, 1000]内的整数坐标fc.record({ x: ..., y: ... })组合出{ x, y }形状的房子fc.array(houseArbitrary, { minLength: ..., maxLength: ... })生成房子列表。import * as fc from fast-check; const houseArbitrary fc.record({ x: fc.integer({ min: 0, max: 1000 }), y: fc.integer({ min: 0, max: 1000 }), }); // 注意maxLength 不宜过大否则参考实现O(n!)会跑不完 const housesArbitrary fc.array(houseArbitrary, { minLength: 2, maxLength: 8 });这些 API 的约束语义可以从仓库源码确认integer.ts 中IntegerConstraints的默认值分别为min -0x80000000、max 0x7fffffff且会在min max或参数非整数时抛出错误本题显式传入{ min: 0, max: 1000 }收紧范围record.ts 支持requiredKeys默认全部键必填与noNullPrototype等选项这里直接用默认行为即可array.ts 中ArrayConstraints的默认minLength为 0未指定maxLength时上界为0x7fffffff同时可用size控制生成规模此处用{ minLength: 2, maxLength: 8 }保证至少有两个房子、且穷举参考实现可承受。第二步定义距离与闭环总路程const santaHouse { x: 0, y: 0 }; function distance(a: { x: number; y: number }, b: { x: number; y: number }): number { return Math.abs(a.x - b.x) Math.abs(a.y - b.y); } // 把旅程首尾闭合成完整环路再求总距离 // 贪心实现返回的 journey 已含返回原点的一步追加原点只会多算一段 0 距离结果不变 function tourDistance(journey: { x: number; y: number }[]): number { let total 0; const closed [...journey, santaHouse]; for (let i 1; i closed.length; i) { total distance(closed[i - 1], closed[i]); } return total; }第三步编写属性并断言import { expect, test } from vitest; import * as fc from fast-check; import findOptimalJourney from ./advent.js; // 精灵实现buggy import { findOptimalJourney as findOptimalJourneyReference } from ./reference; // 穷举参考实现 test(精灵的旅程规划器应始终给出最优路线, () { fc.assert( fc.property(housesArbitrary, (houses) { const greedy tourDistance(findOptimalJourney(houses)); const optimal tourDistance(findOptimalJourneyReference(houses)); expect(greedy).toBe(optimal); }), ); });执行npx vitest后fast-check 会随机采样生成大量随机的房子列表坐标在[0, 1000]、数量在[2, 8]逐一对照两个实现命中反例一旦发现greedy ! optimal立即记录触发失败的输入例如[{x:1,y:0},{x:0,y:1},{x:2,y:1}]自动收缩shrinking在保留失败的前提下把坐标和列表长度往最小化方向收缩最终给你一个尽量精简的失败样例便于人工确认。这正是属性测试相较手写少量用例的核心价值不需要你事先猜出反例长什么样只需把应当永远成立的规律写出来。fast-check 的property与assert两个入口的实现细节可以在 Property.ts 与 Runner.ts 中看到property会把所有任意值包进AlwaysShrinkableArbitrary并用tuple组合成整体assert在失败时会抛错并输出RunDetails而check则返回可编程检查的RunDetailsfast-check.ts 中对两者均有导出。收缩行为的底层依据也可以从源码确认_internals/IntegerArbitrary.ts 中当区间包含 0 时整数会优先向 0 收缩shrink的注释明确写着shrink towards zero并带有偏向生成bias机制保证既覆盖极端值、又能快速逼近最小反例。从源码看挑战机制在线沙盒与答案校验这篇挑战文章并不只是静态文本正文中的AdventPlaygroundOfTheDay /与FormOfTheDay /是实打实的交互组件其机制同样值得拆解在线沙盒AdventPlayground.tsx 通过 StackBlitz SDK 内嵌一个 Node Vitest 项目自动生成advent.js精灵实现源码、advent.d.ts类型声明和advent.test.ts测试模板依赖为fast-check: latest、typescript: latest、vitest: latest启动命令为npx vitest --watch --reporterverbose。测试模板默认只是占位fc.property(fc.constant(noop), ...)等你把它改造成真正的属性测试。页面上还提供源码文件下载入口方便本地复现答案校验AdventOfTheDayBuilder.tsx 的onSubmit会先用解析器把文本框内容转成输入再分别运行精灵实现与参考实现通过postAdvent即上文的总路程计算比较二者输出是否一致一致则提示这个输入看起来没问题Santa 还在找 Bug不一致则判定为成功找到缺陷并把答案存入localStorage输入格式从 AdventOfTheDay.tsx 的parser可以看到输入按行解析每行必须是x,y形式的两个整数且x、y均须在[0, 1000]内否则报错All lines except must be of the form , 。占位示例为1,2 / 10,9 / 200,15。也就是说你的任务本质是找到一个满足格式约束的输入让贪心实现的闭环总路程严格大于穷举最优解。上面手工推导的1,0\n0,1\n2,1就是一个可直接提交的答案。本地复现与延伸思考如果你想脱离在线沙盒在本地完整复现这道题新建目录并初始化 npm 项目安装fast-check、vitest、typescript与沙盒依赖一致将 buggy.mjs 复制为被测模块参照 AdventOfTheDay.tsx 中的findOptimalJourney实现参考版本用上文第三步的属性测试断言两条路线总距离相等npx vitest即可看到 fast-check 找到并收缩出最小反例。值得延伸思考的几点贪心为什么失败最近邻启发式只考虑下一步不考虑这一步对后续的影响曼哈顿距离下先横后纵或先纵后横的顺序差异会被放大属性测试的价值就在于把这种反例的搜索自动化参考实现即 oracle当被测算法没有可对照的标准答案时也可以把属性写成数学不变量如总距离不超过某个上界、路线恰好覆盖所有房子各一次这类思路可进一步参考仓库的属性测试入门文档控制测试成本穷举 oracle 的复杂度是O(n!)所以array的maxLength必须控制在小规模本挑战场景 68 个房子即可稳定触发反例这是将昂贵预言嵌入属性测试时的通用权衡。小结Advent of PBT Day 18 用圣诞老人最短旅程这一经典 TSP 变体生动演示了属性测试在启发式算法缺陷发现上的威力贪心最近邻实现看似合理却经不起与穷举最优解的系统性对照。通过fc.integer、fc.record、fc.array的组合构造合法输入再以闭环总距离相等为属性运行fc.assertfast-check 自动完成了反例搜索与收缩最终给出(1,0)、(0,1)、(2,1)这样简洁的失败样例。掌握这套任意值构造 测试预言对照 自动收缩的方法论你就能把大量看起来对的算法实现变成可被机器证伪的严谨属性。赞分享开发工具测试【免费下载链接】fast-checkProperty based testing framework for JavaScript (like QuickCheck) written in TypeScript项目地址https://gitcode.com/gh_mirrors/fa/fast-check点击查看免费下载相关推荐fast-check 实战用属性测试揪出压缩算法的边界 Bug——Advent of PBT 2024 Day 14 复盘fast check 实战用属性测试揪出压缩算法的边界 Bug——Advent of PBT 2024 Day 14 复盘 本文基于 fast check 官开发工具测试用 fast-check 揪出误杀合法邮箱的正则Advent of PBT 2024 Day 17 实战拆解用 fast check 揪出误杀合法邮箱的正则Advent of PBT 2024 Day 17 实战拆解 导读 本篇基于 fast check 官方 Ad开发工具测试用 fast-check 属性测试揪出「魔法词」回文校验的 Unicode 陷阱Advent of PBT Day 10用 fast check 属性测试揪出「魔法词」回文校验的 Unicode 陷阱Advent of PBT Day 10 Intl.Segmenter 按开发工具测试上一篇【亲测免费】 探索CoreProtect一款强大的服务器保护插件下一篇终极解决方案JKeyboardPanelSwitch让Android键盘面板切换如丝般顺滑创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
