{"id":178941,"date":"2021-09-09T15:09:37","date_gmt":"2021-09-09T14:09:37","guid":{"rendered":"https:\/\/blog.jetbrains.com\/?post_type=kotlin&#038;p=178941"},"modified":"2021-09-09T17:12:30","modified_gmt":"2021-09-09T16:12:30","slug":"idiomatic-kotlin-binary-representation","status":"publish","type":"kotlin","link":"https:\/\/blog.jetbrains.com\/en\/kotlin\/2021\/09\/idiomatic-kotlin-binary-representation","title":{"rendered":"Idiomatic Kotlin: Solving Advent of Code Puzzles, Binary Representation of Numbers"},"content":{"rendered":"\n<p>Let\u2019s continue our journey of understanding what \u201cidiomatic Kotlin\u201d means and solve one more puzzle from the Advent of Code challenge. The puzzles are independent of each other, so you don\u2019t need to check any of the previous ones we\u2019ve already covered. Simply read through the following solution or watch the video. We hope you learn something new!<\/p>\n\n\n\n<iframe loading=\"lazy\" width=\"560\" height=\"315\" src=\"https:\/\/www.youtube.com\/embed\/XEFna3xyxeY\" title=\"YouTube video player\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen=\"\"><\/iframe>\n\n\n\n<!--more-->\n\n\n\n<h2 class=\"wp-block-heading\">Day 5. Binary Boarding<\/h2>\n\n\n\n<p>We\u2019re boarding the plane! We need to analyze the list of boarding passes and find the seat with the highest seat ID. Then we need to find the one seat missing from the list, which is ours. You can find the full task description at <a href=\"https:\/\/adventofcode.com\/2020\/day\/5\" target=\"_blank\" rel=\"noopener\">https:\/\/adventofcode.com\/2020\/day\/5<\/a>.*<\/p>\n\n\n\n<p>A seat is specified as, for example, <code>FBFBBFFRLR<\/code>, where <code>F<\/code> means &#8220;front&#8221;, <code>B<\/code> means &#8220;back&#8221;, <code>L<\/code> means &#8220;left&#8221;, and <code>R<\/code> means &#8220;right&#8221;. The first 7 characters are either <code>F<\/code> or <code>B<\/code> and they specify exactly one of the 128 rows on the plane (numbered 0 through 127). The last three characters are either <code>L<\/code> or <code>R<\/code>; these specify exactly one of the 8 columns of seats on the plane (numbered 0 through 7). A more detailed encoding description is given on the <a href=\"https:\/\/adventofcode.com\/2020\/day\/5\" target=\"_blank\" rel=\"noopener\">puzzle page<\/a>.<\/p>\n\n\n\n<p>Every seat has a unique seat ID, calculated by multiplying the row by 8 and then adding the column.<\/p>\n\n\n\n<p>The puzzle input is the list of boarding passes. The first task is to find the boarding pass in this list with the highest seat ID.<\/p>\n\n\n\n<p>The second task is to find the missing boarding pass in the list. The flight is completely full, there\u2019s only one missing boarding pass, and that\u2019s our seat. However, some of the seats at the very front and back of the plane don&#8217;t exist on this aircraft, so they are missing from the list as well.<\/p>\n\n\n\n<p>As usual, we suggest that you try to solve the task on your own before reading the solution. Here\u2019s how you can <a href=\"https:\/\/blog.jetbrains.com\/kotlin\/2021\/07\/advent-of-code-in-idiomatic-kotlin\/#how-to-solve\" class=\"ek-link\">set up Kotlin<\/a> for this purpose.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Solution<\/h2>\n\n\n\n<p>Let\u2019s first discuss the encoding of the boarding passes. Note how it is a nicely \u201chidden\u201d binary representation of natural numbers! Let\u2019s take a closer look.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Boarding pass: binary representation<\/h3>\n\n\n\n<p>First, let\u2019s look at the rows. There are 128 rows on the plane, which are encoded with 7 \u201cbits\u201d. These bits are called F and B in the puzzle, but they carry the same meaning as 0 and 1 do in the binary representation. To extend the analogy, the way to identify the exact row based on the boarding pass is reminiscent of the algorithm used to convert a binary representation of the number to a decimal.<\/p>\n\n\n\n<p>Let\u2019s consider the provided example \u2013 the first seven characters of <code>FBFBBFFRLR<\/code> that decode the \u201crow\u201d. <code>F<\/code> means to take the \u201cfront\u201d, or the lower half, while <code>B<\/code> is to take the \u201cback\u201d, or the upper half on each iteration. Taking the lower half is equivalent to not adding the corresponding power of two to the result (or multiplying it by zero), while taking the upper half is equivalent to adding it to the result (or multiplying it by one).<\/p>\n\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nF = 0; B = 1\nFB notation  F  B  F  B  B  F  F\nBit          0  1  0  1  1  0  0\nIndex        6  5  4  3  2  1  0\n2^Index      64 32 16 8  4  2  1\n\nDecimal:\n0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0 =\n32 + 8 + 4 = \n44\n<\/pre>\n\n\n<p>\nIf this conversion is clear to you, you can skip the remaining explanations in this section and go directly to the Kotlin implementation. If not, please read the description of the conversion strategy on the task page and the following explanations carefully.\n<\/p>\n<p>\nWe start by considering the whole range, rows <code>0<\/code> through <code>127<\/code>. The maximum value that can be decoded via 7 bits is <code>1111111<\/code>, or <code>127<\/code> if converted to the decimal form: <code>2<sup>7<\/sup> - 1 = 2<sup>6<\/sup> + 2<sup>5<\/sup> + 2<sup>4<\/sup> + 2<sup>3<\/sup> + 2<sup>2<\/sup> + 2<sup>1<\/sup> + 2<sup>0<\/sup> = 127<\/code>. Each bit is responsible for its part of the range: if it\u2019s <code>1<\/code>, we add the corresponding power of two to the result; if it\u2019s <code>0<\/code>, we skip it.\n<\/p>\n<table>\n<tbody>\n<tr>\n<td><strong>Bit correspondence<\/strong>\n   <\/td>\n<td><strong>Bit index<\/strong>\n   <\/td>\n<td><strong>Description of the task<\/strong>\n   <\/td>\n<td><strong>Reworded in \u2018binary representation\u2019 terms<\/strong>\n   <\/td>\n<\/tr>\n<tr>\n<td><code>F = 0<\/code>\n   <\/td>\n<td><code>6<\/code>\n   <\/td>\n<td><code>F<\/code> means to take the lower half, keeping rows 0 through 63.\n   <\/td>\n<td>We don\u2019t add <code>2<sup>6<\/sup>=64<\/code> to the result.<p><\/p>\n<p>\nThat keeps the result in the <code>0..(127-64)<\/code> range, or <code>0..63<\/code>.\n   <\/p>\n<\/td>\n<\/tr>\n<tr>\n<td><code>B = 1<\/code>\n   <\/td>\n<td><code>5<\/code>\n   <\/td>\n<td><code>B<\/code> means to take the upper half, keeping rows 32 through 63.\n   <\/td>\n<td>We add <code>2<sup>5<\/sup>=32<\/code> to the result. That keeps the result in the range <code>32..63<\/code>.\n   <\/td>\n<\/tr>\n<tr>\n<td><code>F = 0<\/code>\n   <\/td>\n<td><code>4<\/code>\n   <\/td>\n<td><code>F<\/code> means to take the lower half, keeping rows 32 through 47.\n   <\/td>\n<td>We don\u2019t add <code>2<sup>4<\/sup>=16<\/code> to the result. That makes the possible range <code>32..(63-16)<\/code>, or <code>32..47<\/code>.\n   <\/td>\n<\/tr>\n<tr>\n<td><code>B = 1<\/code>\n   <\/td>\n<td><code>3<\/code>\n   <\/td>\n<td><code>B<\/code> means to take the upper half, keeping rows 40 through 47.\n   <\/td>\n<td>We add <code>2<sup>3<\/sup>=8<\/code> to the result. That keeps the result in the range <code>(32+8)..47<\/code>, or <code>40..47<\/code>.\n   <\/td>\n<\/tr>\n<tr>\n<td><code>B = 1<\/code>\n   <\/td>\n<td><code>2<\/code>\n   <\/td>\n<td><code>B<\/code> keeps rows 44 through 47.\n   <\/td>\n<td>We add <code>2<sup>2<\/sup>=4<\/code> to the result. That keeps the result in the range <code>(40+4)..47<\/code>, or <code>44..47<\/code>.\n   <\/td>\n<\/tr>\n<tr>\n<td><code>F = 0<\/code>\n   <\/td>\n<td><code>1<\/code>\n   <\/td>\n<td><code>F<\/code> keeps rows 44 through 45.\n   <\/td>\n<td>We don\u2019t add <code>2<sup>1<\/sup>=2<\/code>. That makes the possible range <code>44..(47-2)<\/code>, or <code>44..45<\/code>.\n   <\/td>\n<\/tr>\n<tr>\n<td><code>F = 0<\/code>\n   <\/td>\n<td><code>0<\/code>\n   <\/td>\n<td>The final <code>F<\/code> keeps the lower of the two, row 44.\n   <\/td>\n<td>We don\u2019t add <code>2<sup>0<\/sup>=1<\/code>. That makes the result <code>44..(45-1)<\/code>, or simply <code>44<\/code>.\n   <\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h4>Decoding column<\/h4>\n<p>\nDecoding the column follows the same logic, but now <code>R<\/code> takes the upper half and corresponds to bit <code>1<\/code>, while <code>L<\/code> takes the lower half and corresponds to bit <code>0<\/code>.\n<\/p>\n<p>\nLet&#8217;s now consider the last 3 characters of <code>FBFBBFFRLR<\/code>.\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nL = 0; R = 1\nRL notation  R  L  R\nBit          1  0  1\nIndex        2  1  0\n2^Index      4  2  1\n\nDecimal:\n1 * 2^2 + 0 * 2^1 + 1 * 2^0 =\n4 + 1 = \n5\n<\/pre>\n\n\n<p>\nThe whole range represents columns 0 through 7. It\u2019s the maximum value that can be encoded via three bits: <code>2<sup>2<\/sup> + 2<sup>1<\/sup> + 2<sup>0<\/sup> = 7.<\/code>\n<\/p>\n<ul>\n<li><code>R<\/code> means to take the upper half, keeping columns 4 through 7. In other words, take <code>2<sup>2<\/sup>=4<\/code> with the multiplier <code>\"1\"<\/code>.\n<\/li>\n<li><code>L<\/code> means to take the lower half, keeping columns 4 through 5. In other words, take <code>2<sup>1<\/sup>=2<\/code> with the multiplier <code>\"0\"<\/code>.\n<\/li>\n<li>The final <code>R<\/code> keeps the upper of the two, column 5. In other words, take <code>2<sup>0<\/sup>=1<\/code> with the multiplier <code>\"1\",<\/code> making the result <code>4+1=5<\/code>.\n<\/li>\n<\/ul>\n<p>\nThe last part is converting the row and the column numbers to the seat ID by using the formula: multiply the row by 8 and then add the column. For the sample boarding pass, the row is <code>44<\/code> and the column is <code>5<\/code>, so this calculation gives the seat ID as <code>44 * 8 + 5 = 357<\/code>.\n<\/p>\n<h4>Combining row and column<\/h4>\n<p>\nBut if we look closer at this formula, we\u2019ll notice that we don\u2019t need to find the row and column separately! We can simply add all the row bits with indexes increased by three to the result (note that <code>8 = 2<sup>3<\/sup><\/code>). This bit operation is formally called \u201cleft-shift\u201d.\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nFBRL notation  F  B  F  B  B  F  F  R  L  R\nBit            0  1  0  1  1  0  0  1  0  1\nIndex          9  8  7  6  5  4  3  2  1  0\n\nDecimal:\n[0 * 2^9 + 1 * 2^8 + 0 * 2^7 + 1 * 2^6 + 1 * 2^5 + 0 * 2^4 + 0 * 2^3] + [1 * 2^2 + 0 * 2^1 + 1 * 2^0] =\n2^3 * [0 * 2^6 + 1 * 2^5 + 0 * 2^4 + 1 * 2^3 + 1 * 2^2 + 0 * 2^1 + 0 * 2^0] + [1 * 2^2 + 0 * 2^1 + 1 * 2^0] =\n8 * 44 + 5 = \n357\n<\/pre>\n\n\n<p><\/p>\n<p>\nWith a little bit of math, a Kotlin solution can almost fit on a single line! Let\u2019s see how.\n<\/p>\n<h3>Converting boarding pass to seat ID<\/h3>\n<p>\nWe only need to replace <code>B\/F<\/code> and <code>R\/L<\/code> with <code>1\/0<\/code> notation, and then convert the resulting binary representation to an integer. Each of these operations is one function call:\n<\/p>\n\n\n<pre class=\"kotlin-code\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nfun String.toSeatID(): Int = this\n   .replace(&#039;B&#039;, &#039;1&#039;).replace(&#039;F&#039;, &#039;0&#039;)\n   .replace(&#039;R&#039;, &#039;1&#039;).replace(&#039;L&#039;, &#039;0&#039;)\n   .toInt(radix = 2)\n\nfun main() {\n   println(&quot;0101100101&quot;.toInt(radix = 2)) \/\/ 357\n   println(&quot;FBFBBFFRLR&quot;.toSeatID())       \/\/ 357\n}\n<\/pre>\n\n\n<p>\nThe <code>String.replace(oldChar: Char, newChar: Char)<\/code> function replaces all occurrences of the old character with the new character. There are two more similar functions. If you need to replace each substring with a new string, pass the strings as arguments:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nString.replace(oldValue: String, newValue: String)\n<\/pre>\n\n\n<p>\nIn order to replace each substring that matches the given regular expression, use another function taking <code>Regex<\/code> as an argument:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nString.replace(regex: Regex, replacement: String)\n<\/pre>\n\n\n<p>\nThe <code>String.toInt(radix: Int)<\/code> function parses the string receiver as an integer in the specified radix. In our case, we specify that the radix is two, so it parses the binary representation of the number.\n<\/p>\n<p>\nThere\u2019s no need to reimplement the conversion algorithm from scratch when you can use the library functions \u2013 unless you specifically want to practice that, of course, but that\u2019s not the goal of this puzzle.\n<\/p>\n<p>\nWe\u2019ve got the seat ID from the boarding pass now and we can continue with the task.\n<\/p>\n<h3>Finding the maximum seat ID<\/h3>\n<p>\nAs usual, we need to read the input first. After implementing the conversion function, it\u2019s quite straightforward:\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 seatIDs = File(&quot;src\/day05\/input.txt&quot;)\n       .readLines()\n       .map(String::toSeatID)\n   \/\/ ...\n}\n<\/pre>\n\n\n<p>\nThe seatIDs list is a list of integers, and the only thing left is finding the maximum in this list. There\u2019s no need to implement it from scratch; we simply use the <code>maxOrNull()<\/code> library function:\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 seatIDs = \u2026\n\n    val maxID = seatIDs.maxOrNull()\n    println(&quot;Max seat ID: $maxID&quot;)\n}\n<\/pre>\n\n\n<p>\nWe\u2019ve found the seat with the maximum seat ID.\n<\/p>\n<h3>Finding the vacant seat ID<\/h3>\n<p>\nThe second part of the task is finding the vacant seat that is missing from the list. There\u2019s guaranteed to be only one. However, we remember that some of the seats at the very front and back of the plane don&#8217;t exist on this aircraft, so they are missing as well. And so, we can\u2019t simply iterate through the range from <code>1<\/code> to <code>maxID<\/code> and check for missing seats, as we would also \u201cfind\u201d those at the very front and back.\n<\/p>\n<p>\nNote, however, that our required vacant seat is not on the edge. This means it\u2019s the only missing seat whose neighbors are both present in the list. So, we can check for this condition: that the seat itself must be missing (in other words, not occupied), but both its neighbors must be occupied.\n<\/p>\n<p>\nFirst, to make our code more expressive, let\u2019s add a function that checks whether a given seat is occupied. It checks that the given seat index belongs to the list of seat IDs provided as the input for our challenge. To make this check quickly, we convert the given list to a set:\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 seatIDs: List&lt;Int&gt; = \u2026\n    val occupiedSeatsSet = seatIDs.toSet()\n    fun isOccupied(seat: Int) = seat in occupiedSeatsSet\n}\n<\/pre>\n\n\n<p>\nKotlin allows us to create local functions, that is, functions inside other functions. That\u2019s really convenient for the kind of short and simple function we need to write here: the <code>isOccupied()<\/code> function will capture the outer variable, <code>occupiedSeatsSet<\/code>, and we don\u2019t need to pass it explicitly as a parameter.\n<\/p>\n<p>\nNow the only thing left to do is find the desired seat index, when the seat is not occupied but the neighboring seats (with indices <code>-1<\/code> and <code>+1<\/code>) are both occupied:\n<\/p>\n\n\n<pre class=\"kotlin-code\" data-highlight-only=\"true\" theme=\"idea\" indent=\"4\" style=\"visibility: hidden; padding: 36px 0;\">\nval mySeat = (1..maxID).find { index -&gt;\n   !isOccupied(index) &amp;&amp; isOccupied(index - 1) &amp;&amp; isOccupied(index + 1)\n}\nprintln(&quot;My seat ID: $mySeat&quot;)\n<\/pre>\n\n\n<p>\nThat\u2019s it!\n<\/p>\n<p>\nThe whole main function that solves both parts of the task looks as follows:\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 seatIDs = File(&quot;src\/day05\/input.txt&quot;)\n       .readLines()\n       .map(String::toSeatID)\n   val maxID = seatIDs.maxOrNull()!!\n   println(&quot;Max seat ID: $maxID&quot;)\n\n   val occupiedSeatsSet = seatIDs.toSet()\n   fun isOccupied(seat: Int) = seat in occupiedSeatsSet\n   val mySeat = (1..maxID).find { index -&gt;\n       !isOccupied(index) &amp;&amp; isOccupied(index - 1) &amp;&amp; isOccupied(index + 1)\n   }\n   println(&quot;My seat ID: $mySeat&quot;)\n}\n<\/pre>\n\n\n<p>\nNote that in order to use <code>maxID<\/code> as the upper bound of the range, we call <code>!!<\/code>, since the <code>maxOrNull()<\/code> function returns a nullable value. Specifically, it returns <code>null<\/code> if the list is empty.\n<\/p>\n<p>\nFollowing the Kotlin philosophy, you might expect to find the <code>max()<\/code> function, throwing an exception if the list is empty. And you\u2019d be right! However, in Kotlin 1.5 the <code>max()<\/code> function is deprecated, and in future versions it will be totally removed and replaced with a function throwing an exception. The <code>max()<\/code> function was present in the standard library starting with Kotlin 1.0 but returned a nullable value, and now the Kotlin team is slowly fixing this small discrepancy. Until the <code>max()<\/code> function reappears in the standard library, it\u2019s fine to write <code>maxOrNull()!!<\/code> to explicitly highlight that you need the non-null value as a result, and you prefer an exception if the list is empty. Alternatively, to avoid using <code>!!<\/code>, you can use <code>maxOf { it }<\/code> for now.\n<\/p>\n<p>\nThat\u2019s it! We outlined the strategy for solving the puzzle, recognized the binary encoding for the numbers, discussed how it works, and presented the solution in Kotlin, which is quite simple thanks to the Kotlin standard library functions.\n<\/p>\n<p>\n&#8212;\n<\/p>\n<p>\n*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>).\n<\/p>","protected":false},"author":42,"featured_media":179880,"comment_status":"open","ping_status":"closed","template":"","categories":[89],"tags":[63,91,3682],"cross-post-tag":[],"acf":[],"_links":{"self":[{"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/kotlin\/178941"}],"collection":[{"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/kotlin"}],"about":[{"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/types\/kotlin"}],"author":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/comments?post=178941"}],"version-history":[{"count":10,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/kotlin\/178941\/revisions"}],"predecessor-version":[{"id":179938,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/kotlin\/178941\/revisions\/179938"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/media\/179880"}],"wp:attachment":[{"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/media?parent=178941"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/categories?post=178941"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/tags?post=178941"},{"taxonomy":"cross-post-tag","embeddable":true,"href":"https:\/\/blog.jetbrains.com\/en\/wp-json\/wp\/v2\/cross-post-tag?post=178941"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}