News

使用惯用 Kotlin 解决 Advent of Code 谜题

Read this post in other languages:
English, 한국어

除了编写代码之外,学习一门语言最好的方式是什么? 解决像 Advent of Code 中的那些有趣而简短的任务可能是练习语言技能的绝佳机会,如果将自己的解决方案与其他人解决相同问题的方式进行比较,您可以学到很多东西。

来自世界各地的许多开发者,包括来自 Kotlin 团队的一些开发者,都会参加 Eric Wastl 创建的 Advent of Code 挑战。 Advent of Code 是每年 12 月发布的一系列任务,您可以解决这些任务并与他人竞争。 许多人都认同这是庆祝圣诞节和新年的最好的倒计时日历!

为了帮助社区学习惯用 Kotlin,并激励更多开发者将来用 Kotlin 解决 Advent of Code 任务,我们决定为 Advent of Code 2020 的任务准备解决方案。 不管您已经在 12 月解决了这些任务,准备现在解决,还是只想查看解决方案,我们都希望您能在这些材料中有所收获。 当然,如果您先尝试自己解决任务,效果会更好!

 

以下是第一个任务的解决方案和视频。 如果您觉得这种形式很有用,并希望我们用类似的方式涵盖更多任务,请在评论中分享您的想法!

第 1 天. Report Repair

我们要修正一份费用报告! 请在 https://adventofcode.com/2020/day/1 查看完整的任务描述*。

您需要从数字列表中找到和为 2020 的两个(在第二部分中是三个)条目,然后将这两个(或三个)数字相乘。

如何解决任务

https://adventofcode.com/ 注册,打开 https://adventofcode.com/2020/day/1 下的任务,使用 Kotlin 编写您的解决方案,然后在网站上检查结果。 您可以在线编写 Kotlin 代码,也可以使用 IDE:

最后,将您的解决方案与下面的解决方案进行比较。

我们将 src 文件夹标记为源集,将代码直接放在那里。 为方便起见,我们将输入文件(如 src/day1/input.txt)复制到源文件夹。 您可以在此项目中找到解决方案。

解决方案

以下是示例输入:

1721
979
366
299
675
1456

 

首先,我们需要读取和解析输入。 我们可以使用 Kotlin readLines() 函数从给定文件中读取行列表:

 

File("src/day1/input.txt").readLines()

 

readLines() 返回一个字符串列表,我们将其转换为一个数字列表:

 

import java.io.File
fun main() {
   val numbers = File("src/day1/input.txt")
       .readLines()
       .map(String::toInt)


}

 

将此代码放入 main 函数中,该函数是程序的入口点。 当您开始输入时,IntelliJ IDEA 会自动导入 java.io.File

现在,我们只需迭代列表,然后对每个数字重复该迭代并检查和:

 

for (first in numbers) {
   for (second in numbers) {
       if (first + second == 2020) {
           println(first * second)
           return
       }
   }
}

 

将此代码放在 main 中,这样一来,找到所需数字时, return 会从 main 返回。

以类似的方式检查三个数字的和:

 

for (first in numbers) {
   for (second in numbers) {
       for (third in numbers) {
           if (first + second + third == 2020) {
               println(first * second * third)
               return
           }
       }
   }
}

 

您可以运行上述代码并获得给定输入的结果。 就是这样! 第一个任务其实很简单。

但是,对于每个元素,我们在相同的列表上进行了反复迭代。 如果使用两个嵌套循环来查找两个数字,则需要 N2 次运算,其中 N 是元素的数量。 当我们需要查找三个数字时,就是三个嵌套循环,以及 N3 次运算。 如果数字列表很大,这不是解决此类问题的最高效方式。 当然还有更好的办法,对吧?

当然有,Kotlin 标准库可以帮助我们简洁地进行表达。 像往常一样,我们可以用某种用于查找结果的智能存储来代替冗长的计算。

解决两个数字的任务

首先,我们构建一个数字补数(即与给定数字的和为 2020 的数字)的映射:

 

val complements = numbers.associateBy { 2020 - it }

 

我们使用 Kotlin associateBy 函数来构建映射。 它的 lambda 实参返回此映射中的一个键,通过该键存储列表元素。 对于示例输入,它将是以下映射:

 

numbers: [1721, 979, 366, 299, 675, 1456]
complements map: {299=1721, 1041=979, 1654=366, 1721=299, 1345=675, 564=1456}

 

经过这个程序,您可以清楚地看到答案! 列表中的第一个数字 1721 作为键出现在 complements 映射中:1721=299,这意味着它是数字 299 的补数,二者的和为 2020

将此信息存储在映射中后,我们可以检查列表中的任何数字在此映射中是否有补数。 以下代码会查找第一个具有现成补数的数字:

 

val pair = numbers.mapNotNull { number ->
   val complement = complements[number]
   if (complement != null) Pair(number, complement) else null
}.firstOrNull()

 

我们将每个数字转换成一个由数字及其补数组成的对(如果补数存在),然后找到第一个非 null 结果。

我们使用 mapNotNull,它会转换列表中的每个元素并筛选出所有 null 结果。 它是先调用 map,再对结果调用 filterNotNull 的简写形式。

firstOrNull 会返回列表中的第一个元素,如果列表为空,则返回 null。 Kotlin 标准库通常使用 OrNull 后缀来标记失败时返回 null 的函数,而不是抛出异常(如 elementAtOrNullsingleOrNullmaxOrNull)。

从 Kotlin 1.5.0 开始,您还可以将后续的两个运算 mapNotNullfirst(OrNull) 替换为一个函数调用:firstNotNullOf(OrNull)

在构建辅助结构后,我们设法通过 N 次运算(而不是像之前一样通过 N2 次运算)找到了满足条件的两个数字!

我们需要将这些数字相乘,因此下面是最后一步:

 

println(pair?.let { (a, b) -> a * b })

 

pair 变量包含由两个数字组成的可以为 null 的 Pair,如果初始列表不包含和为 2020 的数字,则为 null。 我们使用安全访问 ?.let 函数并在 lambda 语法中进行析构,在 pair 不为 null 的情况下显示结果。

解决三个数字的任务

下一步是解决三个数字的问题。 我们来重用目前为止所做的工作,并将查找和为给定数字的一对数字的逻辑提取到一个单独的函数中:

 

fun List<Int>.findPairOfSum(sum: Int): Pair<Int, Int>? {
   // Map: sum - x -> x
   val complements = associateBy { sum - it }
   return firstNotNullOfOrNull { number ->
       val complement = complements[number]
       if (complement != null) Pair(number, complement) else null
   }
}

 

我们还使用了 firstNotNullOfOrNull 函数。

接下来,我们使用 findPairOfSum 构建一个辅助映射,用来存储每个数字的补值对,这些值与此数字的和为 2020:

 

// Map: x -> (y, z) where y + z = 2020 - x
val complementPairs: Map<Int, Pair<Int, Int>?> =
   numbers.associateWith { numbers.findPairOfSum(2020 - it) }

 

对于相同的初始输入,下面是补数对映射:

 

numbers: [1721, 979, 366, 299, 675, 1456]
complement pairs: {1721=null, 979=(366, 675), 366=(979, 675), 299=null, 675=(979, 366), 1456=null}

 

和之前一样,您已经可以看到答案了! 它是与映射中非 null 对相对应的数字。

然而,我们并不真的需要构建整个映射。我们只需要找到对应于非 null 对的第一个数字! 我们使用已经熟悉的 firstNotNullOfOrNull 函数进行查找:

 

fun List<Int>.findTripleOfSum(): Triple<Int, Int, Int>? =
   firstNotNullOfOrNull { x ->
       findPairOfSum(2020 - x)?.let { pair ->
           Triple(x, pair.first, pair.second)
       }
   }

 

请注意 Kotlin 的简明语法,该函数可以直接返回一个表达式。

如果得到的三元组不为 null,则最后一步是计算乘积,这与我们之前的方式类似:

 

println(triple?.let { (x, y, z) -> x * y * z} )

 

这部分到此结束!

在下一部分中,我们将讨论如何解决第二个任务。 如果您觉得此内容有用,并希望我们为更多任务提供解决方案,请告诉我们!

*经 Advent of Code (Eric Wastl) 许可使用。

本博文英文原作者:

Sue

Svetlana Isakova

Discover more