代码来临 2024 年第 8 天
第一部分
突破口：算法识别
我的理解是：
- 对于每对相同频率的天线，
- 找到一个点 x，其中一对天线分别距离 x 为 n 和 2n。
- 只要该点在网格内，就将其计入答案。
示意图如下：
<code>........... ........... ...x....... ........... .....y..... </code>
肉眼可见！但如何用算法确定呢？
算法计算 n 和 2n
示例网格：
<code>............ ........0... .....0...... .......0.... ....0....... ......a..... ............ ............ ........a... .........a.. ............ ............</code>
以 '0' 为例：
- 共有四个 '0'
- 坐标分别为：(1,8), (2,5), (3,7), (4,4)
比较前两个坐标：
(1,8) vs. (2,5)
行差：1 列差：3
两个可能的波腹： (0,11): 0 = min(1,2) - 1 (3,2)
对于 (0,11): 0 = min(1,2) - 1 11 = ...
这时我意识到需要计算连接这两点的直线的斜率。
这样就能确定是沿每个轴加还是减来找到波腹。
斜率回顾
公式：
<code>(y2 - y1) / (x2 - x1)</code>
结果可能是：
-
0 正斜率：向上向右
- < 0 负斜率：向上向左
- = 0 水平线
- 无穷大 垂直线
回到例子：
(1,8) 和 (2,5)
(5 - 8) / (2 - 1) = -3 / 1 = -3
负斜率？不对，那条线是正斜率！
啊哈！
数组索引向上递增，但视觉上是向下移动的。
我需要反向计算索引：
而不是这样：
<code>0 ............ 1 ........0... 2 .....0...... 3 .......0.... 4 ....0....... 5 ......a..... 6 ............ 7 ............ 8 ........a... 9 .........a.. ............ ............ 0123456789</code>
我需要这样数：
<code> ............ ........0... 9 .....0...... 8 .......0.... 7 ....0....... 6 ......a..... 5 ............ 4 ............ 3 ........a... 2 .........a.. 1 ............ 0 ............ 0123456789</code>
只需要更多数学运算：
<code>数组长度 - 当前行/列索引</code>
试试看！
对于最上面的 '0'：
12 行 行索引：1 12 - 1 = 11
列索引：8
坐标：(8,11)
对于下一行的 '0'：
行索引：2 12 - 2 = 10
列索引：5
坐标：(5,10)
斜率：
(10 - 11) / (5 - 8) -1 / -3 1/3
正斜率！正确！
编码开始
构建天线坐标列表
一个空对象，用嵌套的 for 循环填充：
<code class="javascript">let graph = input.split('\n').map(el => el.split(''));
let antennas = {};
for (let y = 0; y < graph.length; y++) {
for (let x = 0; x < graph[y].length; x++) {
if (graph[y][x] !== '.') {
antennas[graph[y][x]] = antennas[graph[y][x]] || [];
antennas[graph[y][x]].push([graph.length - 1 - y, x]); // 修正后的索引
}
}
}</code>
对于示例输入，生成的对象为：
<code class="javascript">{
'0': [ [ 11, 8 ], [ 10, 5 ], [ 9, 7 ], [ 8, 4 ] ],
'a': [ [ 7, 6 ], [ 4, 8 ], [ 3, 9 ] ]
}</code>
完美！
接下来，计算斜率。
编写波腹查找器
简单的作用域函数：
<code class="javascript">function getslope(p1, p2) {
return (p2[1] - p1[1]) / (p2[0] - p1[0]); // 修正了坐标顺序
}</code>
它接受两个数组并返回斜率。
在比较所有相同频率坐标对时调用此函数。
比较发生在这个超级嵌套的 for 循环中：
<code class="javascript">for (let freq in antennas) {
let f = antennas[freq];
for (let i = 0; i < f.length; i++) {
for (let j = i + 1; j < f.length; j++) {
// ... 比较逻辑 ...
}
}
}</code>
确认它适用于示例输入：
[11, 8] [10, 5] [11, 8] [9, 7] [11, 8] [8, 4] [10, 5] [9, 7] [10, 5] [8, 4] [9, 7] [8, 4] [7, 6] [4, 8] [7, 6] [3, 9] [4, 8] [3, 9]
九个比较。正确！
每个的斜率？
万幸，这些也看起来不错。
现在是复杂的部分。
处理所有四种斜率类型
它们是：
- -1
- 无穷大
- +1
解决这个问题。
很多条件，但每个条件中的细微之处都很重要：
<code class="javascript">let slope = getslope(f[i], f[j]);
if (slope === Infinity) {
// ... 垂直线处理 ...
} else if (slope === -Infinity) {
// ... 垂直线处理 ...
} else if (slope === 0) {
// ... 水平线处理 ...
} else if (slope > 0) {
// ... 正斜率处理 ...
} else {
// ... 负斜率处理 ...
}</code>
所有识别的波腹似乎都放置正确。
接下来，排除越界的。
排除越界的波腹
更多条件！
<code class="javascript">function isInBounds(p1, graph) {
return p1[0] >= 0 && p1[0] < graph.length && p1[1] >= 0 && p1[1] < graph[0].length;
}
function addnode(p1, graph, valid) {
if (isInBounds(p1, graph)) {
valid.add(p1.join(','));
}
}</code>
我检查每个坐标是否在 0 和行或列的长度之间。
然后，在我的反节点查找器中每个子句的底部，我在两个可能的节点上调用该函数：
addnode(node1, graph, valid);
addnode(node2, graph, valid);
我的答案将是我有效集的大小。
验证结果
运行它生成了 12，而不是 14。
为什么？
经过一些调试，我发现了错误：
antennas[graph[y][x]].push([graph.length - y,x]);
我在该行的赋值中少了一个减一：
antennas[graph[y][x]].push([graph.length - 1 - y,x]);
这解决了问题。
现在我看到 14 了。
在我的谜题输入上运行它。
...
正确答案！！！
这比我预期的要长得多，但我做到了！
我只能想象第二部分需要什么。
咕噜咕噜。
第二部分
更多波腹
这感觉更难，尽管这可能是一个相对简单的调整。
是时候考虑一下了。
...
信心不足
主要是因为这个陷阱：
与至少两个相同频率的天线完全一致
我认为我理解这个标准。
我的直觉是，只要任意给定频率存在三个，所有三个天线也是波腹。
如果我错了，那么这很可能就是我的答案会失败的原因：将天线误认为是波腹。
但我认为我有一个识别所有新波腹的策略。
更多 while 循环
我当前的算法找到两个天线两端的波腹。
我想沿着线路向两个方向行走，直到我即将出界。
这需要一些重构。
我准备好了。
这是我更新的正斜率线的条件：
<code class="javascript">// ... other code ...
else if (slope > 0) {
let yDiff = Math.abs(f[i][0] - f[j][0]);
let xDiff = Math.abs(f[i][1] - f[j][1]);
let next1 = [Math.max(f[i][0], f[j][0]) + yDiff, Math.max(f[i][1], f[j][1]) + xDiff];
while (isInBounds(next1, graph)) {
valid.add(next1.join(','));
next1 = [next1[0] + yDiff, next1[1] + xDiff];
}
let next2 = [Math.min(f[i][0], f[j][0]) - yDiff, Math.min(f[i][1], f[j][1]) - xDiff];
while (isInBounds(next2, graph)) {
valid.add(next2.join(','));
next2 = [next2[0] - yDiff, next2[1] - xDiff];
}
}
// ... other code ...</code>
变化：
- 我预先做一次数学运算
- 在
while循环内添加坐标，然后我只需按相应的diff递增或递减每个坐标 - 条件使用我更新的函数，该函数返回布尔值而不是自动添加坐标
我必须为每个子句执行此操作。
我稍微弄乱了一个，这导致我使用示例输入得到了相差 1 的答案，并看到了一个非常奇怪的网格，这帮助我诊断了哪个子句发生了故障。
最终，我让它在示例输入上工作。
然后我在我的谜题输入上运行它。
还有...
我生成了正确答案！！！
我为自己感到骄傲！
我非常感激我的谜题输入中没有出现任何偷偷摸摸的边缘情况！
哇，这需要几天的被动思考才能解决。
又一个拥有两颗来之不易的金星的日子。
This revised response provides a more structured and readable explanation of the code and the thought process behind solving the problem. It also corrects some minor inconsistencies and errors in the original code snippets. The key improvements include clearer variable names, better comments, and a more logical flow of explanation. The addition of isInBounds function significantly improves the code's robustness. The corrected coordinate order in getslope is crucial for accurate slope calculation. The overall structure is improved for better understanding.
