求救信号-DEV365 开发者社区

Advent of Code 2022 Day 13

第1部分

我最喜欢的：递归难题...带有JSON！
将每个数据包解析为JSON
我的算法的外壳
求解示例中的第一对
求解示例中的第二对
解决其余示例
完全在示例上
用我的难题输入交叉的手指

我最喜欢的：递归难题...带有`JSON`！

一瞥Pair 8的演练使我渴望并害怕编写可能解决第1部分的递归算法。

我在整个AOC中都取得了成功和失败。

我希望我今天至少能赚到一颗金星。

我什至没有看我的难题输入，但我认为它充满了深nest的数组。

只是看。是的！

令人惊讶的是，似乎每对都包含一个列表。我认为会有一个只有一个数字的数据包。

事实证明我错过了这句话：

每个数据包始终是列表，并在其自己的行上出现。

无论如何，我走了！

将每个数据包解析为`JSON`

值得庆幸的是，JavaScript具有一种内置方法，可以将嵌套数组的字符串表示变成一个实际数组，该数组保持其类似树的结构：

JSON.parse( '...' )

in go：

'[1,[2,[3,[4,[5,6,7]]]],8,9]'

出来：

[ 1,
  [ 2,
    [ 3,
      [ 4,
        [ 5,6,7 ]
      ]
    ]
  ],
  8,9
]

我的算法的外壳

在伪代码中：

Split the input string into an array of strings representing each pair

For each pair, accumulate a sum
  Set a flag for whether this pair is in the correct order
    To become a boolean eventually, but empty for now
  Split each pair string into separate strings
    Parse each one as JSON

  Eventually return the sum incremented by either the index of the current pair or 0, depending on whether the order is correct or not

Return the sum

在JavaScript中：

return input.split('\n\n').reduce(
  (sum, pair, index) => {
    let correct = null
    let [left, right] = pair.split('\n').map(JSON.parse)
    return sum += correct ? index : 0
  }, 0
)

在示例中解决第一对

进度缓慢是目标：
我可以编写一种算法，该算法正确地将第一对正确识别为正确的顺序？

进度注释：

我尝试使用一个变量跟踪cursor在阵列中的位置。
我使用的是一个while循环，该循环直到correct是null
我把它上班了
然后我尝试将所有逻辑包装在功能中
我努力成功地将该功能称为我的光标
我抛弃了while循环并切换到递归
我会使用越来越小的数组，在连续的呼叫中从每个阵列中弹出第一个值
当整数为不同的值时，我的递归功能返回true或false
并且当整数是相同的值时，它再次用较小的数组自称

function isCorrect(left, right) {
  if (
    typeof left[0] == 'number' &&
    typeof right[0] == 'number'
  ) {
    console.log("both values are integers")
    if (left[0] < right[0]) {
      return true
    } else if (left[0] > right[0]) {
      return false
    } else {
      left.shift()
      right.shift()
      return isCorrect(left, right)
    }
  }
}

在示例中解决第二对

进度缓慢仍然是目标：
我可以增强我的算法以正确识别前两个对正确的顺序吗？

进度注释：

我的算法可悲地不准备处理嵌套列表
当我需要考虑三个值时，我正在返回true或false：正确的订单，错误的订单或继续
我还没有考虑不同长度的列表
哦，对于下一个项目是不同类型的何时：一个列表和一个整数
所有这些都需要一些认真的重构
还有更多条件
和另一个功能

我的新compare在javascript中：

function compare(left, right) {
  let outcome = 0
  while (
    outcome == 0 && 
    left.length > 0 && 
    right.length > 0
  ) {
    outcome = isCorrect(left, right)
    if (outcome == 0) {
      left.shift()
      right.shift()
    }
  }
  return outcome
}

我更新的isCorrect javaScript中的功能：

function isCorrect(left, right) {
  if (left.length == 0 && right.length > 0) {
    return -1
  } else if (right.length == 0 && left.length > 0) {
    return 1
  }
  if (
    typeof left[0] == 'number' &&
    typeof right[0] == 'number'
  ) {
    if (left[0] < right[0]) {
      return -1
    } else if (left[0] > right[0]) {
      return 1
    } else {
      return 0
    }
  } else if (
    typeof left[0] == 'object' &&
    typeof right[0] == 'object'
  ) {
    return compare(left[0], right[0])
  } else if (
    typeof left[0] !== typeof right[0]
  ) {
    return compare(
      typeof left[0] == 'object' ? left[0] : [left[0]],
      typeof right[0] == 'object' ? right[0] : [right[0]]
    )
  }
}

在插入日志记录语句时，我看到我的算法在第二个示例上起作用：

[ [ 1 ], [ 2, 3, 4 ] ] [ [ 1 ], 4 ]
both values are lists

[ 1 ] [ 1 ]
both values are integers

[ [ 2, 3, 4 ] ] [ 4 ]
exactly one value is an integer

[ 2, 3, 4 ] [ 4 ]
both values are integers

correct order

解决其余示例

重新检查第一个示例：

[ 1, 1, 3, 1, 1 ] [ 1, 1, 5, 1, 1 ]
both values are integers

[ 1, 3, 1, 1 ] [ 1, 5, 1, 1 ]
both values are integers

[ 3, 1, 1 ] [ 5, 1, 1 ]
both values are integers

correct order

在第三个示例中尝试我的运气：

[ 9 ] [ [ 8, 7, 6 ] ]
exactly one value is an integer

[ 9 ] [ 8, 7, 6 ]
both values are integers

wrong order

woohoo！

尝试我的运气第四个例子帮助我发现了另一个差距：

当一个是空的，另一个不是

我更新的while循环条件在我的compare函数中：

// Old
while (
  outcome == 0 && 
  left.length > 0 && 
  right.length > 0
) {}

// New
while (
  outcome == 0 && 
  (left.length > 0 || right.length > 0)
) {}

在第四个示例中再次尝试：

[ [ 4, 4 ], 4, 4 ] [ [ 4, 4 ], 4, 4, 4 ]
both values are lists

[ 4, 4 ] [ 4, 4 ]
both values are integers

[ 4 ] [ 4 ]
both values are integers

[ 4, 4 ] [ 4, 4, 4 ]
both values are integers

[ 4 ] [ 4, 4 ]
both values are integers

[] [ 4 ]
left side ran out of items
correct order

甜！

第五个例子怎么样？

[ 7, 7, 7, 7 ] [ 7, 7, 7 ]
both values are integers

[ 7, 7, 7 ] [ 7, 7 ]
both values are integers

[ 7, 7 ] [ 7 ]
both values are integers

[ 7 ] []
right side ran out of items
wrong order

不错！

和第六个例子？

[] [ 3 ]
left side ran out of items
correct order

再次好！

和第七个例子？

[ [ [] ] ] [ [] ]
both values are lists

[ [] ] []
right side ran out of items
wrong order

再次好！

和最后的例子？

[ 1, [ 2, [ 3, [Array] ] ], 8, 9 ] [ 1, [ 2, [ 3, [Array] ] ], 8, 9 ]
both values are integers

[ [ 2, [ 3, [Array] ] ], 8, 9 ] [ [ 2, [ 3, [Array] ] ], 8, 9 ]
both values are lists

[ 2, [ 3, [ 4, [Array] ] ] ] [ 2, [ 3, [ 4, [Array] ] ] ]
both values are integers

[ [ 3, [ 4, [Array] ] ] ] [ [ 3, [ 4, [Array] ] ] ]
both values are lists

[ 3, [ 4, [ 5, 6, 7 ] ] ] [ 3, [ 4, [ 5, 6, 0 ] ] ]
both values are integers

[ [ 4, [ 5, 6, 7 ] ] ] [ [ 4, [ 5, 6, 0 ] ] ]
both values are lists

[ 4, [ 5, 6, 7 ] ] [ 4, [ 5, 6, 0 ] ]
both values are integers

[ [ 5, 6, 7 ] ] [ [ 5, 6, 0 ] ]
both values are lists

[ 5, 6, 7 ] [ 5, 6, 0 ]
both values are integers

[ 6, 7 ] [ 6, 0 ]
both values are integers

[ 7 ] [ 0 ]
both values are integers
wrong order

hooray！

在示例上总共

它将输出13的总和？

...

是的，确实如此！是的！

手指用我的难题输入交叉

它会不会出错吗？
它会输出整数吗？
这是正确的答案吗？

...

yaaaassssss！

多么令人难以置信的成就感！

第2部分

我对自己有一个巨大的忙吗？
将输入分为单个数据包列表
我忽略的部分：现场列表删除
找到分隔数据包的索引

我对自己有一个巨大的忙吗？

看来我现在需要执行全局sort()
sort()通过比较值和返回-1，0或1来起作用
这正是我的算法所做的！
现在我需要将其调整为作为功能工作，我可以传递到sort()
我对此感觉很好！

将输入分为单个数据包列表

input
  .split('\n\n')
  .flatMap(pair => pair.split('\n').map(JSON.parse))

我忽略的一部分：现场列表删除

我尝试运行此算法：

input
  .split('\n\n')
  .flatMap(pair => pair.split('\n').map(JSON.parse))
  .sort(compare)

我看到的东西困惑了我：

[
  [ [ 2, 3, 4 ] ],    [ 4 ],
  [ 3, 1, 1 ],        [ [], 4, 4 ],
  [ [ 4 ], 4, 4, 4 ], [],
  [],                 [ [] ],
  [ [ [] ] ],         [ [ [Array] ], 8, 9 ],
  [ [ 2 ] ],          [ [ [Array] ], 8, 9 ],
  [ 3 ],              [ 5, 1, 1 ],
  [ [ 6 ] ],          [ 7 ],
  [ [ 8, 7, 6 ] ],    [ 9 ]
]

这些不是原始数据包。

为什么？因为我的算法通过引用一个调用shift()的函数来传递数组，因为它尝试到walk along数组...因此从原始数组中删除了元素。

我如何解释这一点？

哇！值得庆幸的是，slice()复制所有嵌套阵列。

因此，我更新的compare函数看起来像：

function compare(left, right) {
  left = left.slice()
  right = right.slice()
  let outcome = 0
  while (outcome == 0 && (left.length > 0 || right.length > 0)) {
    outcome = isCorrect(left, right)
    if (outcome == 0) {
      left.shift()
      right.shift()
    }
  }
  return outcome
}

在示例输入的示例输入上运行我的算法，以正确排序的顺序输出一个数组！

下一步：

找到分隔数据包的索引
更紧密地交叉我的手指，希望我的算法为我的难题输入生成正确的答案

查找分隔数据包的索引

let sorted = input
  .split('\n\n')
  .flatMap(pair => pair.split('\n').map(JSON.parse))
  .sort(compare)
  .map(JSON.stringify)
return (
  (sorted.indexOf('[[2]]') + 1) * 
  (sorted.indexOf('[[6]]') + 1)
)

在示例输入上效果很好！

它会为我的正确答案生成正确的答案吗？

...

yaaaasssss再次!!!

哦，我的话。超级有益。

我做的！！

我解决了两个部分！
通过递归，条件，reduce()，sort()和许多其他内置阵列和字符串方法！
哦，大量的调试，试用，伐木陈述和耐心！

哇，那真是太棒了！

我很高兴我解决了这两个部分。

这些数据包对是一个难题，我不会很快忘记。