这个谜题的描述令人困惑。就像，真的很混乱。我至少读了五遍才明白这个问题。
第一部分
对于这个谜题，示例输入如下：
seeds: 79 14 55 13
seed-to-soil map:
50 98 2
52 50 48
soil-to-fertilizer map:
0 15 37
37 52 2
39 0 15
fertilizer-to-water map:
49 53 8
0 11 42
42 0 7
57 7 4
water-to-light map:
88 18 7
18 25 70
light-to-temperature map:
45 77 23
81 45 19
68 64 13
temperature-to-humidity map:
0 69 1
1 0 69
humidity-to-location map:
60 56 37
56 93 4
地图的每一行都是目标起点、源起点和范围长度。例如，如果我们取seed-to-soil map的第一行：
$line = '50 98 2' ;
[ $destinationStart , $sourceStart , $rangeLength ] = explode ( ' ' , $line ) ;
$sourceRange = range (
$sourceStart ,
$sourceStart + $rangeLength - 1
) ;
$destinationRange = range (
$destinationStart ,
$destinationStart + $rangeLength - 1
) ;
$mapped = array_combine ( $sourceRange , $destinationRange ) ;
$mapped = [
98 => 50 ,
99 => 51 ,
] ;
需要对输入中的每个地图执行此操作。然后获取第一个地图的种子编号，获取值（如果不在范围内，则获取前一个值），依此类推直到最后一个位置值。因此，在上面的示例中，如果种子数为98 ，则值为50 。然后取50并查看soil-to-fertilizer map中是否存在该值。如果这没有意义，请查看今天难题的代码页的出现。 [1]
以下是我的完整“解决方案”。我循环遍历每个地图的每一行，根据数字生成范围，并将其添加到mapData数组中。请注意，我使用array_combine将源值用作键，将目标值用作新值。 array_replace保留键，与 array_merge 不同， array_merge会重置键，这在本例中很重要。
$rawData = explode ( "\n\n" , $input ) ;
$seeds = explode ( ' ' , str_replace ( 'seeds: ' , '' , $rawData [ 0 ] ) ) ;
unset ( $rawData [ 0 ] ) ;
$mapData = [ ] ;
foreach ( $rawData as $value ) {
$lines = explode ( "\n" , $value ) ;
$mapName = str_replace ( ' map:' , '' , $lines [ 0 ] ) ;
unset ( $lines [ 0 ] ) ;
$mapData [ $mapName ] = [ ] ;
foreach ( [ $lines ] as $line )
{
[ $destinationStart , $sourceStart , $rangeLength ] = explode ( ' ' , $line ) ;
// generate the ranges for the source and destination
$mapData [ $mapName ] = array_replace ( $mapData [ $mapName ] , array_combine (
range ( $sourceStart , $sourceStart + $rangeLength - 1 ) ,
range ( $destinationStart , $destinationStart + $rangeLength - 1 ) ,
) ) ;
}
}
$locations = [ ] ;
foreach ( $seeds as $seed )
{
// keep track of the current value, starting with the seed
$current = $seed ;
foreach ( $mapData as $mapName => $map )
{
// if there isn't a value set, fallback to the current
$current = $map [ $current ] ?? $current ;
}
$locations [ ] = $current ;
}
echo 'Lowest location number is ' . min ( $locations ) . PHP_EOL ;
这适用于示例输入，考虑到我花了很长时间试图理解这个谜题，这很好。然后我在真实输入上运行它并得到内存不足错误：
Fatal error: Allowed memory size of 536870912 bytes exhausted
此时我实际上还没有查看真正的输入。与样本输入相比，真实输入的数字很大，因此范围生成导致 PHP 内存不足。这意味着我必须重新考虑我的解决方案，或者投入大量的记忆并希望得到最好的结果。
所以我用 64GB 内存运行它： php -d memory_limit=64000M 1.php ，它工作了！或者至少，它跑了。它给了我一个错误的答案。我更好地查看了实际输入中的数字，然后就到此为止了。
两个小时后，我恍然大悟，意识到如何在不需要Frontier 超级计算机 1.102 exaFLOPS 的情况下解决这个问题。我还注意到一些测试代码对其中一个数组进行了切片，因此即使我没有内存问题，我也永远不会得到正确的答案。哎呀。
第一部分 回归
我可以通过生成每个范围的开始和结束来计算种子的索引，而不是为每个数字生成范围：
- $mapData[$mapName] = array_replace($mapData[$mapName], array_combine(
- range($sourceStart, $sourceStart + $rangeLength - 1),
- range($destinationStart, $destinationStart + $rangeLength - 1),
- ));
+ $mapData[$mapName][] = [
+ 'sourceStart' => $sourceStart,
+ 'sourceEnd' => $sourceStart + $rangeLength - 1,
+ 'destinationStart' => $destinationStart,
+ 'destinationEnd' => $destinationStart + $rangeLength - 1,
+ ];
然后计算差值来创建我的索引，然后在下一个“地图”上使用该索引来获取正确的值：
$locations = [ ] ;
foreach ( $seeds as $seed ) {
$current = $seed ;
foreach ( $mapData as $mapName => $mapArray ) {
foreach ( $mapArray as $map )
{
if ( $current >= $map [ 'sourceStart' ] && $current <= $map [ 'sourceEnd' ] ) {
$index = $current - ( int ) $map [ 'sourceStart' ] ;
$current = ( int ) $map [ 'destinationStart' ] + $index ;
break ;
}
}
}
$locations [ ] = $current ;
}
echo 'Lowest location number is ' . min ( $locations ) . PHP_EOL ;
第一部分完成了。我什至不需要给它额外的内存来运行。
第二部分
套用近藤玛丽亚的话：
你的感受是决策的标准——具体来说，知道什么能激发快乐。在编写代码时要确定这一点，关键是一次拿起一点点代码，然后静静地问自己：“这会激发快乐吗？”
就像2015年的《神奇四侠》一样，没有第二部。不是今天，撒旦。
我的代码在 GitHub 上。
-
可能和我一样困惑⤾