{"id":184516,"date":"2021-10-13T15:05:59","date_gmt":"2021-10-13T14:05:59","guid":{"rendered":"https:\/\/blog.jetbrains.com\/?post_type=kotlin&#038;p=184516"},"modified":"2021-10-13T15:06:01","modified_gmt":"2021-10-13T14:06:01","slug":"idiomatic-kotlin-working-with-lists","status":"publish","type":"kotlin","link":"https:\/\/blog.jetbrains.com\/ja\/kotlin\/2021\/10\/idiomatic-kotlin-working-with-lists","title":{"rendered":"Idiomatic Kotlin: Solving Advent of Code Puzzles, Working With Lists"},"content":{"rendered":"\n<p>This post continues our \u201cIdiomatic Kotlin\u201d series and provides the solution for the <a href=\"https:\/\/adventofcode.com\/2020\/day\/9\" target=\"_blank\" rel=\"noopener\">Advent of Code Day 9<\/a>* challenge. While solving it, we\u2019ll look into different ways to manipulate lists in Kotlin.<\/p>\n\n\n\n<iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/vj3J9MuF1mI\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n\n\n\n<h2 class=\"wp-block-heading\">Day 9. Encoding error, part I<\/h2>\n\n\n\n<p>We need to attack a weakness in data encrypted with the eXchange-Masking Addition System (XMAS)! The data is a list of numbers, and we need to find the first number in the list (starting from the 26th) that is <em>not<\/em> the sum of any 2 of the 25 numbers before it. We\u2019ll call the number <em>valid<\/em> if it can be presented as a sum of two numbers from the previous sublist, and <em>invalid<\/em> otherwise. Two numbers that sum to a valid number must be different from each other.<\/p>\n\n\n\n<p>If the first 25 numbers are 1 through 25 in a random order, the next number must be the sum of two of those numbers to be valid:<\/p>\n\n\n\n<ul><li>26 would be a valid next number, as it could be 1 plus 25 (or many other pairs, like 2 and 24).<\/li><li>49 would be a valid next number, as it is the sum of 24 and 25.<\/li><li>100 would not be valid; no two of the previous 25 numbers sum to 100.<\/li><li>50 would also not be valid; although 25 appears in the previous 25 numbers, the two numbers in the pair must be different.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Solution, part I<\/h2>\n\n\n\n<p>Let\u2019s solve the task in Kotlin! For a start, let\u2019s implement a function that checks whether a given list contains a pair of numbers that sum up to a given number. We\u2019ll later use this function to check whether a given number is valid by passing this number and the list of the previous 25 numbers as arguments.<\/p>\n\n\n\n<p>For convenience, we can define the function as an extension on a <code>List<\/code> of <code>Long<\/code> numbers. We need to iterate over all the elements in the list, looking for the two with the given sum. The first naive attempt will be using <code>forEach<\/code> (we call it on <code>this<\/code> implicit receiver, our list of numbers) to iterate through the elements twice:<\/p>\n\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun List&lt;Long&gt;.hasPairOfSumV1(sum: Long): Boolean {\n   forEach { first -&gt;\n       forEach { second -&gt;\n           if (first + second == sum) return true\n       }\n   }\n   return false\n}\nfun main() {\n   val numbers = listOf(1L, 24, 25, 10, 13)\n   println(numbers.hasPairOfSumV1(26)) \/\/ true; 26 = 1 + 25\n   println(numbers.hasPairOfSumV1(49)) \/\/ true; 49 = 24 + 25\n   println(numbers.hasPairOfSumV1(100)) \/\/ false\n\n   \/\/ This is wrong:\n   println(numbers.hasPairOfSumV1(50)) \/\/ true; 50 = 25 * 2\n}\n<\/pre>\n\n\n<p>\nBut this solution is wrong! Using this approach, <code>first<\/code> and <code>second<\/code> might refer to the same element. But as we remember from the task description, two numbers that sum to a valid number must be different from each other.\n<\/p>\n<p>\nTo fix that, we can iterate over a list of elements with indices and make sure that the indices of two elements are different:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun List&lt;Long&gt;.hasPairOfSumV2(sum: Long): Boolean {\n   forEachIndexed { i, first -&gt;\n       forEachIndexed { j, second -&gt;\n           if (i != j &amp;&amp; first + second == sum) return true\n       }\n   }\n   return false\n}\nfun main() {\n   val numbers = listOf(1L, 24, 25, 10, 13)\n   println(numbers.hasPairOfSumV2(50)) \/\/ false\n}\n<\/pre>\n\n\n<p>\nThis way, if <code>first<\/code> and <code>second<\/code> both refer to <code>25<\/code>, they have the same indices, so they are no longer interpreted as a correct pair.\n<\/p>\n<p>\nWe can rewrite this code and delegate the logic for finding the necessary element to Kotlin library functions. For this case, <code>any<\/code> does the job. It returns <code>true<\/code> if the list contains an element that satisfies the given condition:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\n\/\/sampleStart\nfun List&lt;Long&gt;.hasPairOfSum(sum: Long): Boolean =\n   indices.any { i -&gt;\n       indices.any { j -&gt;\n           i != j &amp;&amp; this[i] + this[j] == sum\n       }\n   }\n\/\/sampleEnd\n\nfun main() {\n   val numbers = listOf(1L, 24, 25, 10, 13)\n   println(numbers.hasPairOfSum(50)) \/\/ false\n}\n<\/pre>\n\n\n<p>\nOur final version of the <code>hasPairOfSum<\/code> function uses any to iterate through indices instead of elements and checks for a pair that meets the condition. <code>indices<\/code> is an extension property on <code>Collection<\/code> that returns an integer range of collection indices, <code>0..size - 1<\/code>; we call it on <code>this<\/code> implicit receiver, our list of numbers.\n<\/p>\n<h3>Finding an invalid number<\/h3>\n<p>\nLet\u2019s implement a function that looks for an invalid number, one that is not the sum of two of the 25 numbers before it.\n<\/p>\n<p>\nBefore we start, let\u2019s store the group size, 25, as a constant. We have a sample input that we can check our solution against which uses the group size 5 instead, so it\u2019s much more convenient to change this constant in one place:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nconst val GROUP_SIZE = 25\n<\/pre>\n\n\n<p>\nWe define the group size as <code>const val<\/code> and make it a compile-time constant, which means it\u2019ll be replaced with the actual value at compile time. Indeed, if you use this constant (e.g. in a range <code><em>GROUP_SIZE<\/em>..<em>lastIndex<\/em><\/code>) and look at the bytecode, you\u2019ll no longer be able to find the <code>GROUP_SIZE<\/code> property. Its usage will have been replaced with the constant <code>25<\/code>.<\/p>\n<p>\nFor convenience, we can again define the <code>findInvalidNumber<\/code> function as an extension function on <code>List<long><\/long><\/code>. Let\u2019s first implement it more directly, and then rewrite it using the power of standard library functions.\n<\/p>\n<p>\nWe use the example provided with the problem, where every number but one is the sum of two of the previous <code>5<\/code> numbers; the only number that does not follow this rule is <code>127<\/code>:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\n\/\/sampleStart\nconst val GROUP_SIZE = 5\n\nfun List&lt;Long&gt;.findInvalidNumberV1(): Long? {\n   for (index in (GROUP_SIZE + 1)..lastIndex) {\n       val prevGroup = subList(index - GROUP_SIZE, index)\n       if (!prevGroup.hasPairOfSum(sum = this[index])) {\n           return this[index]\n       }\n   }\n   return null\n}\n\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576)\n   println(numbers.findInvalidNumberV1()) \/\/ 127\n}\n\/\/sampleEnd\n\nfun List&lt;Long&gt;.hasPairOfSum(sum: Long): Boolean =\n   indices.any { i -&gt;\n       indices.any { j -&gt;\n           i != j &amp;&amp; this[i] + this[j] == sum\n       }\n   }\n<\/pre>\n\n\n<p>\nBecause we need to find the first number in the input list that satisfies our condition starting from the 26th, we iterate over all indices starting from <code>GROUP_SIZE + 1<\/code> up to the last index, and for each corresponding element check whether it\u2019s invalid. <code>prevGroup<\/code> contains exactly <code>GROUP_SIZE<\/code> elements, and we run <code>hasPairOfSum<\/code> on it, providing the current element as the sum to check. If we find an invalid element, we return it.\n<\/p>\n<p>\nYou may think that the <code>sublist()<\/code> function creates the sublists and copies the list content, but it doesn\u2019t! It merely creates a view. By using it, we avoid having to create many intermediate sublists!\n<\/p>\n<p>\nWe can rewrite this code using the <code>firstOrNull<\/code> library function. It finds the first element that satisfies the given condition. This allows us to find the index of the invalid number. Then we use <code>let<\/code> to return the element staying at the found position:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nconst val GROUP_SIZE = 5\n\/\/sampleStart\nfun List&lt;Long&gt;.findInvalidNumberV2(): Long? =\n   ((GROUP_SIZE + 1)..lastIndex)\n       .firstOrNull { index -&gt;\n           val prevGroup = subList(index - GROUP_SIZE, index)\n           !prevGroup.hasPairOfSum(sum = this[index])\n       }\n       ?.let { this[it] }\n\/\/sampleEnd\n\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576)\n   println(numbers.findInvalidNumberV2()) \/\/ 127\n}\n\nfun List&lt;Long&gt;.hasPairOfSum(sum: Long): Boolean =\n   indices.any { i -&gt;\n       indices.any { j -&gt;\n           i != j &amp;&amp; this[i] + this[j] == sum\n       }\n   }\n<\/pre>\n\n\n<p>\nNote how we use safe access together with <code>let<\/code> to transform the index if one was found. Otherwise <code>null<\/code> is returned.\n<\/p>\n<h3>Using \u2018windowed\u2019<\/h3>\n<p>\nTo improve readability, we can follow a slightly different approach. Instead of iterating over indices by hand and constructing the necessary sublists, we use a library function that does the job for us.\n<\/p>\n<p>\nThe Kotlin standard library has the <code>windowed<\/code> function, which returns a list or a sequence of snapshots of a window of a given size. This window \u201cslides\u201d along the given collection or sequence, moving by one element each step:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun main() {\n   val list = listOf(&#039;a&#039;, &#039;b&#039;, &#039;c&#039;, &#039;d&#039;, &#039;e&#039;)\n   println(list.windowed(2)) \/\/ [[a, b], [b, c], [c, d], [d, e]]\n   println(list.windowed(3)) \/\/ [[a, b, c], [b, c, d], [c, d, e]]\n}\n<\/pre>\n\n\n<p>\nHere we build sublists, that is, snapshots, of size 2 and 3. To see more examples of how to use <code>windowed<\/code> and other advanced operations on collections, check out <a href=\"https:\/\/www.youtube.com\/watch?v=N4CpLxGJlq0\" target=\"_blank\" rel=\"noopener\">this video<\/a>.\n<\/p>\n<p>\nThis function is perfectly suited to our challenge, as it can build sublists of the required size automatically for us. Let\u2019s rewrite <code>findInvalidNumber<\/code> once more:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nconst val GROUP_SIZE = 5\n\/\/sampleStart\nfun List&lt;Long&gt;.findInvalidNumberV3(): Long? =\n    windowed(GROUP_SIZE + 1)\n       .firstOrNull { window -&gt;\n           val prevGroup = window.dropLast(1)\n           !prevGroup.hasPairOfSum(sum = window.last())\n       }\n       ?.last()\n\/\/sampleEnd\n\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576)\n   println(numbers.findInvalidNumberV3()) \/\/ 127\n}\n\nfun List&lt;Long&gt;.hasPairOfSum(sum: Long): Boolean =\n   indices.any { i -&gt;\n       indices.any { j -&gt;\n           i != j &amp;&amp; this[i] + this[j] == sum\n       }\n   }\n<\/pre>\n\n\n<p>To have both the previous group and the current number, we use a window with the size <code>GROUP_SIZE + 1<\/code>. The first <code>GROUP_SIZE<\/code> elements form the necessary sublist to check, while the last element is the current number. If we find a sublist that satisfies the given condition, its last element is the result.<\/p>\n<h3 id=\"sublist-windowed-difference\">Note about the difference between <code>sublist<\/code> and <code>windowed<\/code> functions<\/h3>\n<p>Note, however, that unlike <code>sublist()<\/code>, which creates a view of the existing list, the <code>windowed()<\/code> function builds all the intermediate lists. Though using it improves readability, it results in some performance drawbacks. For parts of the code that are not performance-critical, these drawbacks usually are not noticeable. On the JVM, the garbage collector is very effective at collecting such short-lived objects. It\u2019s nevertheless useful to know about these nuanced differences between the two functions!<\/p>\n<p>There\u2019s also an overloaded version of the <code>windowed()<\/code> function that takes lambda as an argument describing how to transform each window. This version doesn\u2019t create new sublists to pass as lambda arguments. Instead, it passes \u201cephemeral\u201d sublists (somewhat similar to <code>sublist()<\/code> views) that are valid only inside the lambda. You should not store such a sublist or allow it to escape unless you\u2019ve made a snapshot of it:<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun main() {\n   val list = listOf(&#039;a&#039;, &#039;b&#039;, &#039;c&#039;, &#039;d&#039;, &#039;e&#039;)\n   \/\/ Intermediate lists are created:\n   println(list.windowed(2).map { it.joinToString(&quot;&quot;) })\n\n   \/\/ Lists passed to lambda are &quot;ephemeral&quot;,\n   \/\/ they are only valid inside this lambda:\n   println(list.windowed(2) { it.joinToString(&quot;&quot;) })\n\n   \/\/ You should make a copy of a window sublist\n   \/\/ to store it or pass further:\n   var firstWindowRef: List&lt;Char&gt;? = null\n   var firstWindowCopy: List&lt;Char&gt;? = null\n   list.windowed(2) {\n       if (it.first() == &#039;a&#039;) {\n           firstWindowRef = it \/\/ Don&#039;t do this!\n           firstWindowCopy = it.toList()\n       }\n       it.joinToString(&quot;&quot;)\n   }\n   println(&quot;Ref: $firstWindowRef&quot;)   \/\/ [d, e]\n   println(&quot;Copy: $firstWindowCopy&quot;) \/\/ [a, b]\n}\n<\/pre>\n\n\n<p>If you try to store the very first window <code>[a, b]<\/code> by copying the reference, you see that by the end of the iterations this reference contains different data, the last window. To get the first window, you need to copy the content.<\/p>\n<p>A function with similar optimization might be added in the future for Sequences, see <a href=\"https:\/\/youtrack.jetbrains.com\/issue\/KT-48800\" target=\"_blank\" rel=\"noopener\">KT-48800<\/a> for details.<\/p>\n<p>We can further improve our <code>findInvalidNumber<\/code> function by using sequences instead of lists. In Kotlin, <code>Sequence<\/code> provides a lazy way of computation. In the current solution, <code>windowed<\/code> eagerly returns the result, the full list of windows. If the required element is found in the very first list, it\u2019s not efficient. The change to <code>Sequence <\/code>causes the result to be evaluated lazily, which means the snapshots are built only when they\u2019re actually needed.<\/p>\n<p>The change to sequences only requires one line. We convert a list to a sequence before performing any further operations:<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nconst val GROUP_SIZE = 5\n\/\/sampleStart\nfun List&lt;Long&gt;.findInvalidNumber(): Long? =\n    asSequence()\n       .windowed(GROUP_SIZE + 1)\n       .firstOrNull { window -&gt;\n           val prevGroup = window.dropLast(1)\n           !prevGroup.hasPairOfSum(sum = window.last())\n       }\n       ?.last()\n\/\/sampleEnd\n\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576)\n   println(numbers.findInvalidNumber()) \/\/ 127\n}\n\nfun List&lt;Long&gt;.hasPairOfSum(sum: Long): Boolean =\n   indices.any { i -&gt;\n       indices.any { j -&gt;\n           i != j &amp;&amp; this[i] + this[j] == sum\n       }\n   }\n<\/pre>\n\n\n<p>\nThat\u2019s it! We\u2019ve improved the solution from the very first version, making it more \u201cidiomatic\u201d along the way.\n<\/p>\n<p>\nThe last thing to do is to get the result for our challenge. We read the input, convert it to a list of numbers, and display the invalid one:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun main() {\n   val numbers = File(&quot;src\/day09\/input.txt&quot;)\n       .readLines()\n       .map { it.toLong() }\n\n   val invalidNumber = numbers.findInvalidNumber()\n   println(invalidNumber)\n}\n<\/pre>\n\n\n<p>\nFor the sample input, the answer is <code>127<\/code>, and for real input, the answer is also correct! Let\u2019s now move on to solve the second part of the task.\n<\/p>\n<h2>Encoding error, part II<\/h2>\n<p>\nThe second part of the task requires us to use the invalid number we just found. We need to find a contiguous set of at least two numbers in the list which sum up to this invalid number. The result we are looking for is the sum of the smallest and largest number in this contiguous range.\n<\/p>\n<p>\nFor the sample list, we need to find a contiguous list which sums to 127:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\n35 20 15 25 47 40 62 55 65 95 102 117 150 182 127 219 299 277 309 576\n<\/pre>\n\n\n<p>\nIn this list, adding up all of the numbers from 15 through 40 produces 127. To find the result, we add together the smallest and largest number in this contiguous range; in this example, these are 15 and 47, producing 62.\n<\/p>\n<h2>Solution, part II<\/h2>\n<p>\nWe need to find a sublist in a list with the given sum of its elements. Let\u2019s first implement this function in a straightforward manner, then rewrite the same logic using library functions. We\u2019ll discuss whether the <code>windowed<\/code> function from the previous part can help us here as well, and finally we\u2019ll identify a more efficient solution.\n<\/p>\n<p>\nTo check the sum of every contiguous sublist of a given list, we try all the options for the list\u2019s start and end indices, build each sublist, and calculate its sum. <code>fromIndex<\/code> belongs to a full range of indices, while <code>toIndex<\/code> should be greater than <code>fromIndex<\/code> and shouldn\u2019t exceed the list <code>size<\/code> (the <code>toIndex<\/code> argument defines an exclusive, not inclusive, upper bound):\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun List&lt;Long&gt;.findSublistOfSumV1(targetSum: Long): List&lt;Long&gt;? {\n   for (fromIndex in indices) {\n       for (toIndex in (fromIndex + 1)..size) {\n           val subList = subList(fromIndex, toIndex)\n           if (subList.sum() == targetSum) {\n               return subList\n           }\n       }\n   }\n   return null\n}\n\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576\n   )\n   println(numbers.findSublistOfSumV1(127)) \/\/ [15, 25, 47, 40]\n}\n<\/pre>\n\n\n<p>\nWe can rewrite this logic using the <code>firstNotNullOfOrNull<\/code> function. Here, we iterate over possible values for <code>fromIndex<\/code> and for <code>toIndex<\/code> and look for the first value that satisfies the given condition:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\n\/\/sampleStart\nfun List&lt;Long&gt;.findSublistOfSumV2(targetSum: Long): List&lt;Long&gt;? =\n   indices.firstNotNullOfOrNull { fromIndex -&gt;\n       ((fromIndex + 1)..size)\n           .firstNotNullOfOrNull { toIndex -&gt;\n               subList(fromIndex, toIndex).takeIf { it.sum() == targetSum }\n           }\n   }\n\n\/\/sampleEnd\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576\n   )\n   println(numbers.findSublistOfSumV2(127)) \/\/ [15, 25, 47, 40]\n}\n<\/pre>\n\n\n<p>\nThe logic hasn\u2019t changed, we\u2019ve simply rewritten it using the <code>firstNotNullOfOrNull<\/code>. If a sublist with the required sum is found, it\u2019s returned from both <code>firstNotNullOfOrNull<\/code> calls as the first found non-<code>null<\/code> value.\n<\/p>\n<p>\nThe <code>takeIf<\/code> function returns its receiver if it satisfies the given condition or <code>null<\/code> if it doesn&#8217;t. In this case, the <code>takeIf<\/code> call returns the found sublist if the sum of its elements is equal to the provided <code>targetSum<\/code>.\n<\/p>\n<p>\nAn alternative way to solve this problem is, for each possible sublist size, to build all the sublists of this size using the <code>windowed<\/code> function, and then check the sum of its elements:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\n\/\/sampleStart\nfun List&lt;Long&gt;.findSublistOfSumV3(targetSum: Long): List&lt;Long&gt;? =\n   (2..size).firstNotNullOfOrNull { sublistSize -&gt;\n       asSequence()\n           .windowed(sublistSize)\n           .firstOrNull { sublist -&gt;\n               sublist.sum() == targetSum\n           }\n   }\n\n\/\/sampleEnd\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576\n   )\n   println(numbers.findSublistOfSumV3(127)) \/\/ [15, 25, 47, 40]\n}\n<\/pre>\n\n\n<p>\nAs before, we convert the input list to a sequence to perform the operation in a lazy manner: each new sublist is created when it needs to be checked for <code>sum<\/code>.\n<\/p>\n<p>\nAll the functions we\u2019ve considered so far work for the challenge input and give the correct answer, but they have one common disadvantage: they manipulate the sublists of all possible sizes, and for each one, calculate the sum. This approach isn\u2019t the most efficient. We can do better, can\u2019t we?\n<\/p>\n<p>\nWe can precalculate all the sums of sublists from the first element in the list to each element, and use these \u201cprefix\u201d sums to easily calculate the sum between any two elements. If we have the sum of elements from <code>0<\/code> to <code>fromIndex<\/code>, and the sum of elements from <code>0<\/code> to <code>toIndex<\/code>, the sum of the elements from <code>fromIndex<\/code> to <code>toIndex<\/code> can be found by subtracting the former from the latter:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nsum(fromIndex, toIndex) = sum(0, toIndex) - sum(0, fromIndex)\n<\/pre>\n\n\n<p>The following illustration shows that:<\/p>\n\n\n<figure class=\"wp-block-image size-large\"><img decoding=\"async\" loading=\"lazy\" width=\"1458\" height=\"641\" src=\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/10\/prefixSumIllustration.png\" alt=\"\" class=\"wp-image-188857\"\/><\/figure>\n\n\n\n<p>We need to precalculate the prefix sum for each element. We can use the standard library\u2019s <code>scan<\/code> function for that! It also has another name, <code>runningFold<\/code>.<\/p>\n\n\n\n<p>The <code>fold<\/code> and <code>scan<\/code> <code>(runningFold)<\/code> functions are related:<\/p>\n\n\n\n<ul><li>They both \u201caccumulate\u201d value starting with the initial value. On each step, they apply the provided operation to the current accumulator value and the next element.<\/li><li><code>fold<\/code> returns only the final result, while <code>scan<\/code> <code>(runningFold)<\/code> returns the results for all the intermediate steps.<\/li><\/ul>\n\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun main() {\n   println((1..4).fold(0) { acc, elem -&gt; acc + elem }) \/\/ 10\n   println((1..4).scan(0) { acc, elem -&gt; acc + elem }) \/\/ [0, 1, 3, 6, 10]\n}\n<\/pre>\n\n\n<p>The following animation illustrates the <code>fold<\/code> and <code>scan<\/code> functions in action:<\/p>\n\n\n<img decoding=\"async\" src=\"https:\/\/blog.jetbrains.com\/wp-content\/uploads\/2021\/10\/scan-animation-preview.jpeg\" alt=\"Scan animation\" data-gif-src=\"https:\/\/resources.jetbrains.com\/storage\/products\/blog\/wp-content\/uploads\/Kotlin\/scan-animation.gif\">\n\n\n\n<p>After precalculating all the prefix sums, we use them to find the sums of all the possible sublists, and look for the required sum:<\/p>\n\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\n\/\/sampleStart\nfun List&lt;Long&gt;.findSublistOfSum(targetSum: Long): List&lt;Long&gt;? {\n   val prefixSums = scan(0L) { acc, element -&gt; acc + element }\n   return indices.firstNotNullOfOrNull { fromIndex -&gt;\n       ((fromIndex + 1)..size).firstNotNullOfOrNull { toIndex -&gt;\n           val subListSum = prefixSums[toIndex] - prefixSums[fromIndex]\n           if (subListSum == targetSum) subList(fromIndex, toIndex) else null\n       }\n   }\n}\n\/\/sampleEnd\nfun main() {\n   val numbers = listOf&lt;Long&gt;(\n       35, 20, 15, 25, 47, 40, 62,\n       55, 65, 95, 102, 117, 150, 182,\n       127, 219, 299, 277, 309, 576\n   )\n   println(numbers.findSublistOfSum(127)) \/\/ [15, 25, 47, 40]\n}\n<\/pre>\n\n\n<p>In this solution, we explicitly build only one sublist of the required sum to return it as the result.<\/p>\n<p>Let\u2019s now call the <code>findSublistOfSum<\/code> function to find the result for our initial challenge. After we found the invalid number in part I, we pass this value as an argument to the <code>findSublistOfSum<\/code> function, and then find the sum of the minimum and maximum values of the resulting list:<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun main() {\n   val numbers = File(&quot;src\/day09\/input.txt&quot;)\n       .readLines()\n       .map { it.toLong() }\n\n   val invalidNumber = numbers.findInvalidNumber()\n       ?: error(&quot;All numbers are valid!&quot;)\n   println(&quot;Invalid number: $invalidNumber&quot;)\n\n   val sublist = numbers.findSublistOfSum(sum = invalidNumber)\n       ?: error(&quot;No sublist is found!&quot;)\n   println(sublist.minOf { it } + sublist.maxOf { it })\n}\n<\/pre>\n\n\n<p>Note how we use the <code>error<\/code> function to report an error and throw an exception in the event that one of our functions returns <code>null<\/code>. In AdventOfCode puzzles, we assume that the input is correct, but it\u2019s still useful to handle errors properly.<\/p>\n<p>That\u2019s all! We\u2019ve discussed the solution for the Day 9 AdventOfCode challenge and worked with the <code>any<\/code>, <code>firstOrNull<\/code>, <code>firstNotNullOfOrNull<\/code>, <code>windowed<\/code>, <code>takeIf<\/code> and <code>scan<\/code> functions, which exemplify a more idiomatic Kotlin style.<\/p>\n<p>&#8212;<\/p>\n<p>*Used with the permission of <a href=\"https:\/\/adventofcode.com\/\" target=\"_blank\" rel=\"noopener\">Advent of Code<\/a> (<a href=\"https:\/\/twitter.com\/ericwastl\" target=\"_blank\" rel=\"noopener\">Eric Wastl<\/a>).<\/p>","protected":false},"author":42,"featured_media":191823,"comment_status":"closed","ping_status":"closed","template":"","categories":[89],"tags":[6259,63,3682],"cross-post-tag":[],"acf":[],"_links":{"self":[{"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/kotlin\/184516"}],"collection":[{"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/kotlin"}],"about":[{"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/types\/kotlin"}],"author":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/comments?post=184516"}],"version-history":[{"count":10,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/kotlin\/184516\/revisions"}],"predecessor-version":[{"id":191842,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/kotlin\/184516\/revisions\/191842"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/media\/191823"}],"wp:attachment":[{"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/media?parent=184516"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/categories?post=184516"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/tags?post=184516"},{"taxonomy":"cross-post-tag","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/ja\/wp-json\/wp\/v2\/cross-post-tag?post=184516"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}