随机地图与开放世界永远令人着迷。从早期的 MineCraft 到现代的 No Man’s Sky ,程序化生成的世界为玩家提供了无尽的探索和发现的机会。 在诸多程序化生成算法中, 波函数坍缩(Wave Function Collapse, WFC)算法 因其独特的生成方式和令人惊叹的结果而脱颖而出。下面就是我们使用波函数坍缩算法生成的图案: 3Bricks Knot MoreFlowers Mountains Village Water Circle Lake 接下来,我们将深入探讨波函数坍缩算法的原理、实现以及应用。 请客吃饭的感悟 假设你是 The Family Guys 中国分 guy。你想要请你一大家子吃饭,大家需要围坐在一张大圆桌旁。但是位置有限,需要合理安排每个人的位置,以确保每个人都能愉快地交流:…
如何在不让对方知道我内裤颜色的情况下,向对方证明我穿了内裤?你也许需要了解零知识证明。 为了理解本文,你可能需要具备密码学的基础知识,了解哈希函数、公钥密码学等概念。你也需要了解 NP 完全性、图论等计算复杂性理论的基础知识。可以参考 之前的文章 。 Intro 假设我们有一个 5x5 的数字网格,里面随机填充了数字 1 到 25。我们想向别人证明 25 这个数字在网格中存在,但不想透露它的位置。 为了实现这一点,我们可以用一块不透明的遮罩覆盖整个网格,只在 25 所在的位置挖一个洞。这样,观察者能看到洞里露出的数字 25,知道它确实存在于网格中,但无法确定它在表格中的相对位置,因为其他数字都被遮住了。 下面是一个可以互动的演示,展示了这个概念: Your browser does not support iframes. Click here to visit the content…
随着 Web AI 技术的快速发展,浏览器厂商开始将 AI 能力直接集成到浏览器内核中。Chrome 从 138 版本开始,正式提供了一套原生的 AI API,包括翻译、语言检测、文本摘要和语言模型等功能。这意味着开发者可以在不依赖外部服务的情况下,直接调用浏览器内置的 AI 能力来构建智能化的 Web 应用。 本文将详细介绍这些 API 的使用方法,并提供完整的示例代码。 这些功能基本都需要 Chrome 浏览器 138 或更高版本,下面的小工具展示了你的浏览器是否支持这些 API: Your browser does not support iframes. Click here to visit the content 翻译 API 样例 如果你使用的是 Chrome 浏览器 138 或更高版本,下面的示例便可以直接运行。 Chrome AI 翻译 API 演示 refresh…
如何让一台服务器接受尽可能多的连接? Wikipedia en.wikipedia.org open_in_new The C10k problem is the problem of optimizing network sockets to handle a large number of clients at the same time. The name C10k is a numeronym for concurrently handling ten thousand connections. Handling many concurrent connections is a different problem from handling many requests per second: the latter requires high throughput…
前段时间读了微信技术团队的一篇文章( 从微信后端仓库发展史谈谈单仓和多仓 ),讲微信是如何在一步步壮大的过程中,逐步从大仓中剥离公众号、小程序等功能到小仓中,从而解决了各种公共库全都塞在同一个文件夹下导致的耦合、权限等问题。 在这个过程中,微信团队总结了一些经验教训,包括提出了合理规划项目文件结构的重要性:如果一股脑地将所有代码按照功能划分到不同的文件夹中,可能会因为未来的需求,导致文件夹之间产生强耦合,从而影响到代码的可维护性和可扩展性。 看完此文,我想就此谈一谈我对大型项目目录组织的看法。正好,最近 Go 写得比较多,就先从 Go 的项目组织谈起。 不过,谈论 Go 的项目组织前,我不得不搬出 Go 语言作者 Russ Cox 的一则 comment: @rsc in golang-standards/project-layout · issue #117 open_in_new…
我之前在写代码时用到了一个正则表达式来匹配 URL,CodeQL 检测出其存在问题: This part of the regular expression may cause exponential backtracking on strings starting with '0' and containing many repetitions of '0'. 这其实是 CWE-1333 ,表明一个正则表达式可能出现极为低效的情况。接下来我们来看看具体是怎么回事。 正则表达式通常会被解析为一个非确定性有限自动机(NFA), 其中每对状态和输入符号可能存在多个可能的后续状态 。算法会逐一尝试所有可能的路径,直到找到匹配项。这一情况通常被称为 backtracking。 例如,对于正则表达式 ^(aa|.)+$ ,如果输入为无法匹配到的 aaX ,算法会尝试以下路径: 按照左侧的 aa…
你是否好奇过 git diff 是如何高效地比较文件并精确显示变化的?这个看似简单的操作背后,隐藏着相当精妙的算法设计。 假设有两个文件 \(A\) 和 \(B\),它们分别有 \(N=7\) 行和 \(M=6\) 行: A B === === A C B B C A A B B A B C A 我们可以将这个比较问题抽象为在一个 \(N \times M\) 网格中寻找路径: 从任意坐标 \((x, y)\) 出发,我们有三种可能的移动方式: 向右移动 到 \((x+1, y)\) — 表示删除第一个文件的第 \(x+1\) 行 向下移动 到 \((x, y+1)\) — 表示添加第二个文件的第 \(y+1\) 行 对角线移动 到 \((x+1, y+1)\) — 表示两个文件的对应行内容相同(无需编辑) 对角线移动在 diff…