mfocko/blog
1
0
Fork 0
mirror of https://github.com/mfocko/blog.git synced 2024-11-24 22:11:54 +01:00
Code Issues Projects Releases Packages Wiki Activity Actions
blog/assets/js/3da4b779.3fd3a899.js
github-actions[bot] c66e8be46b deploy: dc2f8c7761
2024-07-11 21:59:04 +00:00

1 line
No EOL
33 KiB
JavaScript
Raw Permalink Blame History

"use strict";(self.webpackChunkfi=self.webpackChunkfi||[]).push([[2177],{28737:(e,n,t)=>{t.r(n),t.d(n,{assets:()=>l,contentTitle:()=>a,default:()=>c,frontMatter:()=>o,metadata:()=>r,toc:()=>d});var i=t(85893),s=t(11151);const o={title:"4th week of Advent of Code '22 in Rust",description:"Surviving fourth week in Rust.",date:"2023-07-07T15:14",slug:"aoc-2022/4th-week",authors:"mf",tags:["advent-of-code","advent-of-code-2022","rust"],hide_table_of_contents:!1},a=void 0,r={permalink:"/blog/aoc-2022/4th-week",editUrl:"https://github.com/mfocko/blog/tree/main/blog/aoc-2022/04-week-4.md",source:"@site/blog/aoc-2022/04-week-4.md",title:"4th week of Advent of Code '22 in Rust",description:"Surviving fourth week in Rust.",date:"2023-07-07T15:14:00.000Z",formattedDate:"July 7, 2023",tags:[{label:"advent-of-code",permalink:"/blog/tags/advent-of-code"},{label:"advent-of-code-2022",permalink:"/blog/tags/advent-of-code-2022"},{label:"rust",permalink:"/blog/tags/rust"}],readingTime:15.315,hasTruncateMarker:!0,authors:[{name:"Matej Focko",email:"me+blog@mfocko.xyz",title:"a.k.a. @mf",url:"https://gitlab.com/mfocko",imageURL:"https://github.com/mfocko.png",key:"mf"}],frontMatter:{title:"4th week of Advent of Code '22 in Rust",description:"Surviving fourth week in Rust.",date:"2023-07-07T15:14",slug:"aoc-2022/4th-week",authors:"mf",tags:["advent-of-code","advent-of-code-2022","rust"],hide_table_of_contents:!1},unlisted:!1,prevItem:{title:"How can Copr help with broken dependencies",permalink:"/blog/2023/08/02/copr"},nextItem:{title:"3rd week of Advent of Code '22 in Rust",permalink:"/blog/aoc-2022/3rd-week"}},l={authorsImageUrls:[void 0]},d=[{value:"Day 22: Monkey Map",id:"day-22-monkey-map",level:2},{value:"Solution",id:"solution",level:3},{value:"Column iterator",id:"column-iterator",level:4},{value:"Walking around the map",id:"walking-around-the-map",level:4},{value:"Problems",id:"problems",level:4},{value:"Clippy",id:"clippy",level:4},{value:"Day 23: Unstable Diffusion",id:"day-23-unstable-diffusion",level:2},{value:"Solution",id:"solution-1",level:3},{value:"Day 24: Blizzard Basin",id:"day-24-blizzard-basin",level:2},{value:"Solution",id:"solution-2",level:3},{value:"Breakdown",id:"breakdown",level:4},{value:"Evaluating the blizzards",id:"evaluating-the-blizzards",level:4},{value:"Shortest-path algorithm",id:"shortest-path-algorithm",level:4},{value:"Min-heap",id:"min-heap",level:4},{value:"Day 25: Full of Hot Air",id:"day-25-full-of-hot-air",level:2},{value:"Solution",id:"solution-3",level:3},{value:"Converting from <code>&amp;str</code>",id:"converting-from-str",level:4},{value:"Converting to <code>String</code>",id:"converting-to-string",level:4},{value:"Adjusting the code",id:"adjusting-the-code",level:4},{value:"Summary",id:"summary",level:2},{value:"Advent of Code",id:"advent-of-code",level:3},{value:"with Rust",id:"with-rust",level:3}];function h(e){const n={a:"a",admonition:"admonition",annotation:"annotation",blockquote:"blockquote",code:"code",em:"em",h2:"h2",h3:"h3",h4:"h4",hr:"hr",img:"img",li:"li",math:"math",mi:"mi",mrow:"mrow",p:"p",pre:"pre",semantics:"semantics",span:"span",strong:"strong",ul:"ul",...(0,s.a)(),...e.components};return(0,i.jsxs)(i.Fragment,{children:[(0,i.jsxs)(n.p,{children:["Let's go through the fourth week of ",(0,i.jsx)(n.a,{href:"https://adventofcode.com",children:(0,i.jsx)(n.em,{children:"Advent of Code"})})," in Rust."]}),"\n",(0,i.jsx)(n.h2,{id:"day-22-monkey-map",children:(0,i.jsx)(n.a,{href:"https://adventofcode.com/2022/day/22",children:"Day 22: Monkey Map"})}),"\n",(0,i.jsx)(n.admonition,{title:"tl;dr",type:"info",children:(0,i.jsx)(n.p,{children:"Simulating a movement on a 2D map with given instructions. Map becomes a cube in\nthe 2nd part\u2026"})}),"\n",(0,i.jsx)(n.admonition,{title:"Rant",type:"danger",children:(0,i.jsx)(n.p,{children:"This was the most obnoxious problem of this year\u2026 and a lot of Rust issues have\nbeen hit."})}),"\n",(0,i.jsx)(n.h3,{id:"solution",children:"Solution"}),"\n",(0,i.jsx)(n.p,{children:"It seems like a very simple problem to solve, but with very obnoxious changes in\nthe 2nd part and also it's relatively hard to decompose \xbbproperly\xab."}),"\n",(0,i.jsx)(n.h4,{id:"column-iterator",children:"Column iterator"}),"\n",(0,i.jsxs)(n.p,{children:["In the first part of the problem it was needed to know the boundaries of each\nrow and column, since I stored them in ",(0,i.jsx)(n.code,{children:"Vec<Vec<char>>"})," and padded with spaces\nto ensure I have a rectangular 2D \u201carray\u201d. However when you wanted to go through\neach row and column to determine the boundaries, it was very easy to do for the\nrows (cause each row is a ",(0,i.jsx)(n.code,{children:"Vec"})," element), but not for the columns, since they\nspan multiple rows."]}),"\n",(0,i.jsxs)(n.p,{children:["For this use case I have implemented my own ",(0,i.jsx)(n.em,{children:"column iterator"}),":"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"pub struct ColumnIterator<'a, T> {\n map: &'a [Vec<T>],\n column: usize,\n\n i: usize,\n}\n\nimpl<'a, T> ColumnIterator<'a, T> {\n pub fn new(map: &'a [Vec<T>], column: usize) -> ColumnIterator<'a, T> {\n Self { map, column, i: 0 }\n }\n}\n\nimpl<'a, T> Iterator for ColumnIterator<'a, T> {\n type Item = &'a T;\n\n fn next(&mut self) -> Option<Self::Item> {\n if self.i >= self.map.len() {\n return None;\n }\n\n self.i += 1;\n Some(&self.map[self.i - 1][self.column])\n }\n}\n"})}),"\n",(0,i.jsx)(n.p,{children:"Given this piece of an iterator, it is very easy to factor out the common\nfunctionality between the rows and columns into:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"let mut find_boundaries = |constructor: fn(usize) -> Orientation,\n iterator: &mut dyn Iterator<Item = &char>,\n upper_bound,\n i| {\n let mut first_non_empty = iterator.enumerate().skip_while(|&(_, &c)| c == ' ');\n let start = first_non_empty.next().unwrap().0 as isize;\n\n let mut last_non_empty = first_non_empty.skip_while(|&(_, &c)| c != ' ');\n let end = last_non_empty.next().unwrap_or((upper_bound, &'_')).0 as isize;\n\n boundaries.insert(constructor(i), start..end);\n};\n"})}),"\n",(0,i.jsx)(n.p,{children:"And then use it as such:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"// construct all horizontal boundaries\n(0..map.len()).for_each(|row| {\n find_boundaries(\n Orientation::horizontal,\n &mut map[row].iter(),\n map[row].len(),\n row,\n );\n});\n\n// construct all vertical boundaries\n(0..map[0].len()).for_each(|col| {\n find_boundaries(\n Orientation::vertical,\n &mut ColumnIterator::new(&map, col),\n map.len(),\n col,\n );\n});\n"})}),"\n",(0,i.jsx)(n.h4,{id:"walking-around-the-map",children:"Walking around the map"}),"\n",(0,i.jsxs)(n.p,{children:["Once the 2nd part got introduced, you start to think about a way how not to\ncopy-paste a lot of stuff (I haven't avoided it anyways\u2026). In this problem, I've\nchosen to introduce a trait (i.e. ",(0,i.jsx)(n.em,{children:"interface"}),") for 2D and 3D walker."]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"trait Wrap: Clone {\n type State;\n\n // simulation\n fn is_blocked(&self) -> bool;\n fn step(&mut self, steps: isize);\n fn turn_left(&mut self);\n fn turn_right(&mut self);\n\n // movement\n fn next(&self) -> (Self::State, Direction);\n\n // final answer\n fn answer(&self) -> Output;\n}\n"})}),"\n",(0,i.jsx)(n.p,{children:"Each walker maintains its own state and also provides the functions that are\nused during the simulation. The \u201cpromised\u201d methods are separated into:"}),"\n",(0,i.jsxs)(n.ul,{children:["\n",(0,i.jsxs)(n.li,{children:[(0,i.jsx)(n.em,{children:"simulation"}),"-related: that are used during the simulation from the ",(0,i.jsx)(n.code,{children:".fold()"})]}),"\n",(0,i.jsxs)(n.li,{children:[(0,i.jsx)(n.em,{children:"movement"}),"-related: just a one method that holds most of the logic differences\nbetween 2D and 3D"]}),"\n",(0,i.jsxs)(n.li,{children:[(0,i.jsx)(n.em,{children:"final answer"}),": which extracts the ",(0,i.jsx)(n.em,{children:"proof of solution"})," from the\nimplementation-specific walker"]}),"\n"]}),"\n",(0,i.jsx)(n.p,{children:"Both 2D and 3D versions borrow the original input and therefore you must\nannotate the lifetime of it:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"struct Wrap2D<'a> {\n input: &'a Input,\n position: Position,\n direction: Direction,\n}\nimpl<'a> Wrap2D<'a> {\n fn new(input: &'a Input) -> Wrap2D<'a> {\n// \u2026\n"})}),"\n",(0,i.jsx)(n.h4,{id:"problems",children:"Problems"}),"\n",(0,i.jsx)(n.p,{children:"I have used a lot of closures for this problem and once I introduced a parameter\nthat was of unknown type (apart from the fact it implements a specific trait), I\ngot suggested a \u201cfix\u201d for the compilation error that resulted in something that\nwas not possible to parse, cause it, more than likely, violated the grammar."}),"\n",(0,i.jsxs)(n.p,{children:["In a similar fashion, I have been suggested changes that led to a code that\ndidn't make sense by just looking at it (there was no need to try the changes),\nfor example one suggested change in the closure parameter caused disapperance of\nthe parameter name. ","\ud83d\ude04"]}),"\n",(0,i.jsx)(n.h4,{id:"clippy",children:"Clippy"}),"\n",(0,i.jsx)(n.p,{children:"I have to admit that Clippy was rather helpful here, I'll include two examples\nof rather smart suggestions."}),"\n",(0,i.jsxs)(n.p,{children:["When writing the parsing for this problem, the first thing I have spotted on the\n",(0,i.jsx)(n.code,{children:"char"})," was the ",(0,i.jsx)(n.code,{children:".is_digit()"})," function that takes a radix as a parameter. Clippy\nnoticed that I use ",(0,i.jsx)(n.code,{children:"radix = 10"})," and suggested switching to ",(0,i.jsx)(n.code,{children:".is_ascii_digit()"}),"\nthat does exactly the same thing:"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-diff",children:"- .take_while(|c| c.is_digit(10))\n+ .take_while(|c| c.is_ascii_digit())\n"})}),"\n",(0,i.jsxs)(n.p,{children:["Another useful suggestion appeared when working with the iterators and I wanted\nto get the ",(0,i.jsxs)(n.span,{className:"katex",children:[(0,i.jsx)(n.span,{className:"katex-mathml",children:(0,i.jsx)(n.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(n.semantics,{children:[(0,i.jsx)(n.mrow,{children:(0,i.jsx)(n.mi,{children:"n"})}),(0,i.jsx)(n.annotation,{encoding:"application/x-tex",children:"n"})]})})}),(0,i.jsx)(n.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(n.span,{className:"base",children:[(0,i.jsx)(n.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(n.span,{className:"mord mathnormal",children:"n"})]})})]}),"-th element from it. You know the ",(0,i.jsx)(n.code,{children:".skip()"}),", you know the\n",(0,i.jsx)(n.code,{children:".next()"}),", just \u201cslap\u201d them together and we're done for ","\ud83d\ude01"," Well, I got\nsuggested to use ",(0,i.jsx)(n.code,{children:".nth()"})," that does exactly the combination of the two mentioned\nmethods on iterators:"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-diff",children:"- match it.clone().skip(skip).next().unwrap() {\n+ match it.clone().nth(skip).unwrap() {\n"})}),"\n",(0,i.jsx)(n.h2,{id:"day-23-unstable-diffusion",children:(0,i.jsx)(n.a,{href:"https://adventofcode.com/2022/day/23",children:"Day 23: Unstable Diffusion"})}),"\n",(0,i.jsx)(n.admonition,{title:"tl;dr",type:"info",children:(0,i.jsx)(n.p,{children:"Simulating movement of elves around with a set of specific rules."})}),"\n",(0,i.jsx)(n.h3,{id:"solution-1",children:"Solution"}),"\n",(0,i.jsxs)(n.p,{children:["There's not much to mention since it's just a cellular automaton simulation\n(even though the AoC rules for cellular automatons usually get out of hand\n","\ud83d\ude09",")."]}),"\n",(0,i.jsx)(n.p,{children:"Although I had a need to determine boundaries of the elves' positions and ended\nup with a nasty DRY violation. Knowing that you you're looking for maximum and\nminimum that are, of course, exactly the same except for initial values and\ncomparators, it looks like a rather simple fix, but typing in Rust is something\nelse, right? In the end I settled for a function that computes both boundaries\nwithout any duplication while using a closure:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"fn get_bounds(positions: &Input) -> (Vector2D<isize>, Vector2D<isize>) {\n let f = |init, cmp: &dyn Fn(isize, isize) -> isize| {\n positions\n .iter()\n .fold(Vector2D::new(init, init), |acc, elf| {\n Vector2D::new(cmp(acc.x(), elf.x()), cmp(acc.y(), elf.y()))\n })\n };\n\n (f(isize::MAX, &min::<isize>), f(isize::MIN, &max::<isize>))\n}\n"})}),"\n",(0,i.jsx)(n.p,{children:"This function returns a pair of 2D vectors that represent opposite points of the\nbounding rectangle of all elves."}),"\n",(0,i.jsxs)(n.p,{children:["You might ask why would we need a closure and the answer is that ",(0,i.jsx)(n.code,{children:"positions"}),"\ncannot be captured from within the nested function, only via closure. One more\nfun fact on top of that is the type of the comparator"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"&dyn Fn(isize, isize) -> isize\n"})}),"\n",(0,i.jsxs)(n.p,{children:["Once we remove the ",(0,i.jsx)(n.code,{children:"dyn"})," keyword, compiler yells at us and also includes a way\nhow to get a more thorough explanation of the error by running"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-shell",children:"$ rustc --explain E0782\n"})}),"\n",(0,i.jsx)(n.p,{children:"which shows us"}),"\n",(0,i.jsxs)(n.blockquote,{children:["\n",(0,i.jsxs)(n.p,{children:["Trait objects must include the ",(0,i.jsx)(n.code,{children:"dyn"})," keyword."]}),"\n",(0,i.jsx)(n.p,{children:"Erroneous code example:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{children:"trait Foo {}\nfn test(arg: Box<Foo>) {} // error!\n"})}),"\n",(0,i.jsx)(n.p,{children:"Trait objects are a way to call methods on types that are not known until\nruntime but conform to some trait."}),"\n",(0,i.jsxs)(n.p,{children:["Trait objects should be formed with ",(0,i.jsx)(n.code,{children:"Box<dyn Foo>"}),", but in the code above\n",(0,i.jsx)(n.code,{children:"dyn"})," is left off."]}),"\n",(0,i.jsxs)(n.p,{children:["This makes it harder to see that ",(0,i.jsx)(n.code,{children:"arg"})," is a trait object and not a\nsimply a heap allocated type called ",(0,i.jsx)(n.code,{children:"Foo"}),"."]}),"\n",(0,i.jsxs)(n.p,{children:["To fix this issue, add ",(0,i.jsx)(n.code,{children:"dyn"})," before the trait name."]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{children:"trait Foo {}\nfn test(arg: Box<dyn Foo>) {} // ok!\n"})}),"\n",(0,i.jsx)(n.p,{children:"This used to be allowed before edition 2021, but is now an error."}),"\n"]}),"\n",(0,i.jsxs)(n.admonition,{title:"Rant",type:"danger",children:[(0,i.jsxs)(n.p,{children:["Not all of the explanations are helpful though, in some cases they might be even\nmore confusing than helpful, since they address ",(0,i.jsx)(n.em,{children:"very simple"})," use cases."]}),(0,i.jsx)(n.p,{children:"As you can see, even in this case there are two sides to the explanations:"}),(0,i.jsxs)(n.ul,{children:["\n",(0,i.jsxs)(n.li,{children:["it explains why you need to use ",(0,i.jsx)(n.code,{children:"dyn"}),", but"]}),"\n",(0,i.jsxs)(n.li,{children:["it still mentions that trait objects need to be heap-allocated via ",(0,i.jsx)(n.code,{children:"Box<T>"}),"\nthat, as you can see in my snippet, ",(0,i.jsx)(n.strong,{children:"does not"})," apply here ","\ud83d\ude04"," IMO it's\ncaused by the fact that we are borrowing it and therefore we don't need to\ncare about the size or whereabouts of it."]}),"\n"]})]}),"\n",(0,i.jsxs)(n.admonition,{title:"C++ parallel",type:"info",children:[(0,i.jsxs)(n.p,{children:["If you dive into the explanation above, you can notice that the ",(0,i.jsx)(n.code,{children:"Box<dyn Trait>"}),"\npattern is very helpful for using types that are not known during compile-time.\nYou would use a very similar approach in C++ when parsing some data structure\nfrom input (let's say JSON for example)."]}),(0,i.jsxs)(n.p,{children:["On the other hand, in this case, it doesn't really make much sense, cause you\ncan clearly see that the types ",(0,i.jsx)(n.strong,{children:"are known"})," during the compile-time, which in\nC++ could be easily resolved by templating the helper function."]})]}),"\n",(0,i.jsx)(n.h2,{id:"day-24-blizzard-basin",children:(0,i.jsx)(n.a,{href:"https://adventofcode.com/2022/day/24",children:"Day 24: Blizzard Basin"})}),"\n",(0,i.jsx)(n.admonition,{title:"tl;dr",type:"info",children:(0,i.jsx)(n.p,{children:"Navigating your way through a basin with series of blizzards that move around\nyou as you move."})}),"\n",(0,i.jsx)(n.admonition,{title:"caution",type:"warning",children:(0,i.jsxs)(n.p,{children:["It's second to last day and I went \u201c",(0,i.jsx)(n.em,{children:"bonkers"}),"\u201d on the Rust ","\ud83d\ude04"," Proceed to\nread ",(0,i.jsx)(n.em,{children:"Solution"})," part on your own risk."]})}),"\n",(0,i.jsx)(n.h3,{id:"solution-2",children:"Solution"}),"\n",(0,i.jsx)(n.p,{children:"You are given a map with blizzards all over the place and you're supposed to\nfind the minimum time it requires you to walk through the basin without getting\nin any of the blizzards."}),"\n",(0,i.jsx)(n.h4,{id:"breakdown",children:"Breakdown"}),"\n",(0,i.jsxs)(n.p,{children:["Relatively simple, yet a bit annoying, approach can be taken. It's technically\na shortest-path algorithm implementation with some relaxation restrictions and\nbeing able to stay on one position for some time, so each ",(0,i.jsx)(n.em,{children:"vertex"})," of the graph\nis determined by the position on the map and the ",(0,i.jsx)(n.em,{children:"timestamp"}),". I have chosen to\nuse ",(0,i.jsx)(n.code,{children:"Vector3D<usize>"}),", since ",(0,i.jsx)(n.code,{children:"x"})," and ",(0,i.jsx)(n.code,{children:"y"})," attributes can be used for the position\nand, well, let's use ",(0,i.jsx)(n.code,{children:"z"})," for a timestamp, cause why not, right? ","\ud83d\ude09"]}),"\n",(0,i.jsx)(n.h4,{id:"evaluating-the-blizzards",children:"Evaluating the blizzards"}),"\n",(0,i.jsx)(n.admonition,{title:"caution",type:"warning",children:(0,i.jsx)(n.p,{children:"I think that this is the most perverted abuse of the traits in the whole 4 weeks\nof AoC in Rust\u2026"})}),"\n",(0,i.jsxs)(n.p,{children:["The blizzards move along their respective directions in time and loop around in\ntheir respective row/column. Each vertex holds position ",(0,i.jsx)(n.strong,{children:"and"})," time, so we can\n",(0,i.jsx)(n.em,{children:"just"})," index the basin with the vertex itself, right? Yes, we can ","\ud83d\ude08"]}),"\n",(0,i.jsx)(n.admonition,{title:"Fun fact",type:"tip",children:(0,i.jsx)(n.p,{children:"While writing this part, I've recognized unnecessary verbosity in the code and\ncleaned it up a bit. The changed version is shown here and the original was just\nmore verbose."})}),"\n",(0,i.jsxs)(n.p,{children:["I'll skip the boring parts of checking bounds and entry/exit of the basin ","\ud83d\ude09","\nWe can easily calculate positions of the blizzards using a modular arithmetics:"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"impl Index<Position> for Basin {\n type Output = char;\n\n fn index(&self, index: Position) -> &Self::Output {\n // \u2039skipped boring parts\u203a\n\n // We need to account for the loops of the blizzards\n let width = self.cols - 2;\n let height = self.rows - 2;\n\n let blizzard_origin = |size, d, t, i| ((i - 1 + size + d * (t % size)) % size + 1) as usize;\n [\n (\n index.y() as usize,\n blizzard_origin(width, -1, index.z(), index.x()),\n '>',\n ),\n (\n index.y() as usize,\n blizzard_origin(width, 1, index.z(), index.x()),\n '<',\n ),\n (\n blizzard_origin(height, -1, index.z(), index.y()),\n index.x() as usize,\n 'v',\n ),\n (\n blizzard_origin(height, 1, index.z(), index.y()),\n index.x() as usize,\n '^',\n ),\n ]\n .iter()\n .find_map(|&(y, x, direction)| {\n if self.map[y][x] == direction {\n Some(&self.map[y][x])\n } else {\n None\n }\n })\n .unwrap_or(&'.')\n }\n}\n"})}),"\n",(0,i.jsxs)(n.p,{children:["As you can see, there is an expression for calculating the original position and\nit's used multiple times, so why not take it out to a lambda, right? ","\ud83d\ude09"]}),"\n",(0,i.jsxs)(n.p,{children:["I couldn't get the ",(0,i.jsx)(n.code,{children:"rustfmt"})," to format the ",(0,i.jsx)(n.code,{children:"for"}),"-loop nicely, so I've just\ndecided to go with iterating over an elements of a slice. I have used, once\nagain, a combination of two functions (",(0,i.jsx)(n.code,{children:"find_map"})," in this case) to do 2 things\nat once and at the end, if we haven't found any blizzard, we just return the\nempty space."]}),"\n",(0,i.jsxs)(n.p,{children:["I think it's a very ",(0,i.jsx)(n.em,{children:"nice"})," (and naughty) way how to use the ",(0,i.jsx)(n.code,{children:"Index"})," trait, don't\nyou think?"]}),"\n",(0,i.jsx)(n.h4,{id:"shortest-path-algorithm",children:"Shortest-path algorithm"}),"\n",(0,i.jsxs)(n.p,{children:["For the shortest path you can choose and adjust any of the common shortest-path\nalgorithms, in my case, I have decided to use ",(0,i.jsx)(n.a,{href:"https://en.wikipedia.org/wiki/A*_search_algorithm",children:(0,i.jsx)(n.em,{children:"A*"})})," instead of Dijkstra's\nalgorithm, since it better reflects the ",(0,i.jsx)(n.em,{children:"cost"})," function."]}),"\n",(0,i.jsxs)(n.admonition,{title:"Comparison of costs",type:"info",children:[(0,i.jsxs)(n.p,{children:["With the Dijkstra's algorithm I would proceed with the ",(0,i.jsx)(n.code,{children:"time"})," attribute used as\na priority for the queue."]}),(0,i.jsxs)(n.p,{children:["Whereas with the ",(0,i.jsx)(n.em,{children:"A*"}),", I have chosen to use both time and Manhattan distance\nthat promotes vertices closer to the exit ",(0,i.jsx)(n.strong,{children:"and"})," with a minimum time taken."]})]}),"\n",(0,i.jsxs)(n.p,{children:["Cost function is, of course, a closure ","\ud83d\ude09"]}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"let cost = |p: Position| p.z() as usize + exit.y().abs_diff(p.y()) + exit.x().abs_diff(p.x());\n"})}),"\n",(0,i.jsx)(n.p,{children:"And also for checking the possible moves from the current vertex, I have\nimplemented, yet another, closure that yields an iterator with the next moves:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"let next_positions = |p| {\n [(0, 0, 1), (0, -1, 1), (0, 1, 1), (-1, 0, 1), (1, 0, 1)]\n .iter()\n .filter_map(move |&(x, y, t)| {\n let next_p = p + Vector3D::new(x, y, t);\n\n if basin[next_p] == '.' {\n Some(next_p)\n } else {\n None\n }\n })\n};\n"})}),"\n",(0,i.jsx)(n.h4,{id:"min-heap",children:"Min-heap"}),"\n",(0,i.jsxs)(n.p,{children:["In this case I had a need to use the priority queue taking the elements with the\nlowest cost as the prioritized ones. Rust only offers you the ",(0,i.jsx)(n.a,{href:"https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html",children:(0,i.jsx)(n.code,{children:"BinaryHeap"})})," and\nthat is a max-heap. One of the ways how to achieve a min-heap is to put the\nelements in wrapped in a ",(0,i.jsx)(n.a,{href:"https://doc.rust-lang.org/std/cmp/struct.Reverse.html",children:(0,i.jsx)(n.code,{children:"Reverse"})})," (as is even showed in the linked ",(0,i.jsxs)(n.a,{href:"https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html#min-heap",children:["docs of\nthe ",(0,i.jsx)(n.code,{children:"BinaryHeap"})]}),"). However the wrapping affects the type of the heap and also\npopping the most prioritized elements yields values wrapped in the ",(0,i.jsx)(n.code,{children:"Reverse"}),"."]}),"\n",(0,i.jsx)(n.p,{children:"For this purpose I have just taken the max-heap and wrapped it as a whole in a\nseparate structure providing just the desired methods:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"use std::cmp::{Ord, Reverse};\nuse std::collections::BinaryHeap;\n\npub struct MinHeap<T> {\n heap: BinaryHeap<Reverse<T>>,\n}\n\nimpl<T: Ord> MinHeap<T> {\n pub fn new() -> MinHeap<T> {\n MinHeap {\n heap: BinaryHeap::new(),\n }\n }\n\n pub fn push(&mut self, item: T) {\n self.heap.push(Reverse(item))\n }\n\n pub fn pop(&mut self) -> Option<T> {\n self.heap.pop().map(|Reverse(x)| x)\n }\n}\n\nimpl<T: Ord> Default for MinHeap<T> {\n fn default() -> Self {\n Self::new()\n }\n}\n"})}),"\n",(0,i.jsx)(n.p,{children:"Rest is just the algorithm implementation which is not that interesting."}),"\n",(0,i.jsx)(n.h2,{id:"day-25-full-of-hot-air",children:(0,i.jsx)(n.a,{href:"https://adventofcode.com/2022/day/25",children:"Day 25: Full of Hot Air"})}),"\n",(0,i.jsx)(n.admonition,{title:"tl;dr",type:"info",children:(0,i.jsxs)(n.p,{children:["Playing around with a numbers in a ",(0,i.jsx)(n.em,{children:"special"})," base."]})}),"\n",(0,i.jsxs)(n.p,{children:["Getting flashbacks to the ",(0,i.jsx)(n.em,{children:"IB111 Foundations of Programming"}),"\u2026 Very nice \u201cproblem\u201d\nwith a rather easy solution, as the last day always seems to be."]}),"\n",(0,i.jsx)(n.h3,{id:"solution-3",children:"Solution"}),"\n",(0,i.jsxs)(n.p,{children:["Implementing 2 functions, converting from the ",(0,i.jsx)(n.em,{children:"SNAFU base"})," and back to the ",(0,i.jsx)(n.em,{children:"SNAFU"}),"\n",(0,i.jsx)(n.em,{children:"base"})," representation. Let's do a bit more though! I have implemented two functions:"]}),"\n",(0,i.jsxs)(n.ul,{children:["\n",(0,i.jsx)(n.li,{children:(0,i.jsx)(n.code,{children:"from_snafu"})}),"\n",(0,i.jsx)(n.li,{children:(0,i.jsx)(n.code,{children:"to_snafu"})}),"\n"]}),"\n",(0,i.jsx)(n.p,{children:"Now it is apparent that all I do is number to string and string to number. Hmm\u2026\nthat sounds familiar, doesn't it? Let's introduce a structure for the SNAFU numbers\nand implement the traits that we need."}),"\n",(0,i.jsx)(n.p,{children:"Let's start with a structure:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-rust",children:"#[derive(Debug, PartialEq, Eq, PartialOrd, Ord)]\nstruct SNAFU {\n value: i64,\n}\n"})}),"\n",(0,i.jsxs)(n.h4,{id:"converting-from-str",children:["Converting from ",(0,i.jsx)(n.code,{children:"&str"})]}),"\n",(0,i.jsxs)(n.p,{children:["We will start by implementing the ",(0,i.jsx)(n.code,{children:"FromStr"})," trait that will help us parse our input.\nThis is rather simple, I can just take the ",(0,i.jsx)(n.code,{children:"from_snafu"})," function, copy-paste it\ninto the ",(0,i.jsx)(n.code,{children:"from_str"})," method and the number I get will be wrapped in ",(0,i.jsx)(n.code,{children:"Result"})," and\n",(0,i.jsx)(n.code,{children:"SNAFU"})," structure."]}),"\n",(0,i.jsxs)(n.h4,{id:"converting-to-string",children:["Converting to ",(0,i.jsx)(n.code,{children:"String"})]}),"\n",(0,i.jsxs)(n.p,{children:["This is more fun. In some cases you need to implement only one trait and others\nare automatically implemented using that one trait. In our case, if you look in\nthe documentation, you can see that ",(0,i.jsx)(n.code,{children:"ToString"})," trait is automatically implemented\nfor any type that implements ",(0,i.jsx)(n.code,{children:"Display"})," trait."]}),"\n",(0,i.jsxs)(n.p,{children:["Let's implement the ",(0,i.jsx)(n.code,{children:"Display"})," trait then. We should be able to use the ",(0,i.jsx)(n.code,{children:"to_snafu"}),"\nfunction and just take the ",(0,i.jsx)(n.code,{children:"self.value"})," from the ",(0,i.jsx)(n.code,{children:"SNAFU"})," structure."]}),"\n",(0,i.jsxs)(n.p,{children:["And for the convenience of tests, we can also implement a rather simple ",(0,i.jsx)(n.code,{children:"From<i64>"}),"\ntrait for the ",(0,i.jsx)(n.code,{children:"SNAFU"}),"."]}),"\n",(0,i.jsx)(n.h4,{id:"adjusting-the-code",children:"Adjusting the code"}),"\n",(0,i.jsx)(n.p,{children:"After those changes we need to adjust the code and tests."}),"\n",(0,i.jsx)(n.p,{children:"Parsing of the input is very easy, before we have used the lines, now we parse\neverything:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-diff",children:" fn parse_input<P: AsRef<Path>>(pathname: P) -> Input {\n- file_to_lines(pathname)\n+ file_to_structs(pathname)\n }\n"})}),"\n",(0,i.jsx)(n.p,{children:"Part 1 needs to be adjusted a bit too:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-diff",children:" fn part_1(input: &Input) -> Output {\n- to_snafu(input.iter().map(|s| from_snafu(s)).sum())\n+ SNAFU::from(input.iter().map(|s| s.value).sum::<i64>()).to_string()\n }\n"})}),"\n",(0,i.jsx)(n.p,{children:"You can also see that it simplifies the meaning a bit and it is more explicit than\nthe previous versions."}),"\n",(0,i.jsx)(n.p,{children:"And for the tests:"}),"\n",(0,i.jsx)(n.pre,{children:(0,i.jsx)(n.code,{className:"language-diff",children:" #[test]\n fn test_from() {\n- for (n, s) in EXAMPLES.iter() {\n- assert_eq!(from_snafu(s), *n);\n+ for (&n, s) in EXAMPLES.iter() {\n+ assert_eq!(s.parse::<SNAFU>().unwrap().value, n);\n }\n }\n\n #[test]\n fn test_to() {\n- for (n, s) in EXAMPLES.iter() {\n- assert_eq!(to_snafu(*n), s.to_string());\n+ for (&n, s) in EXAMPLES.iter() {\n+ assert_eq!(SNAFU::from(n).to_string(), s.to_string());\n }\n"})}),"\n",(0,i.jsx)(n.h2,{id:"summary",children:"Summary"}),"\n",(0,i.jsx)(n.p,{children:"Let's wrap the whole thing up! Keeping in mind both AoC and the Rust\u2026"}),"\n",(0,i.jsx)(n.p,{children:(0,i.jsx)(n.img,{alt:"Finished advent calendar :smile:",src:t(63321).Z+"",width:"2417",height:"1984"})}),"\n",(0,i.jsx)(n.h3,{id:"advent-of-code",children:"Advent of Code"}),"\n",(0,i.jsxs)(n.p,{children:["This year was quite fun, even though most of the solutions and posts came in\nlater on (",(0,i.jsx)(n.em,{children:"cough"})," in '23 ",(0,i.jsx)(n.em,{children:"cough"}),"). Day 22 was the most obnoxious one\u2026 And also\nit feels like I used priority queues and tree data structures ",(0,i.jsx)(n.strong,{children:"a lot"})," ","\ud83d\udc40"]}),"\n",(0,i.jsx)(n.h3,{id:"with-rust",children:"with Rust"}),"\n",(0,i.jsx)(n.p,{children:"I must admit that a lot of compiler warnings and errors were very useful. Even\nthough I still found some instances where they didn't help at all or cause even\nworse issues than I had. Compilation times have been addressed with the caching."}),"\n",(0,i.jsx)(n.p,{children:"Building my first tree data structure in Rust has been a very \u201cinteresting\u201d\njourney. Being able to write a more generic BFS algorithm that allows you to not\nduplicate code while still mantaining the desired functionality contributes to\na very readable code."}),"\n",(0,i.jsx)(n.p,{children:"I am definitely much more aware of the basic things that bloated Python is\nmissing, yet Rust has them\u2026"}),"\n",(0,i.jsxs)(n.p,{children:["Using explicit types and writing down placeholder functions with ",(0,i.jsx)(n.code,{children:"todo!()"}),"\nmacros is very pleasant, since it allows you to easily navigate the type system\nduring the development when you don't even need to be sure how are you going to\nput the smaller pieces together."]}),"\n",(0,i.jsx)(n.p,{children:"I have used a plethora of traits and also implemented some of them to either be\nidiomatic, or exploit the syntactic sugar they offer. Deriving the default trait\nimplementation is also very helpful in a lot of cases, e.g. debugging output,\ncopying, equality comparison, etc."}),"\n",(0,i.jsx)(n.p,{children:"I confess to touching more \u201ccursed\u201d parts of the Rust, such as macros to\ndeclutter the copy-paste for tests or writing my own structures that need to\ncarry a lifetime for their own fields."}),"\n",(0,i.jsxs)(n.p,{children:["tl;dr Relatively pleasant language until you hit brick wall ","\ud83d\ude09"]}),"\n",(0,i.jsx)(n.hr,{}),"\n",(0,i.jsxs)(n.p,{children:["See you next year! Maybe in Rust, maybe not ","\ud83d\ude43"]})]})}function c(e={}){const{wrapper:n}={...(0,s.a)(),...e.components};return n?(0,i.jsx)(n,{...e,children:(0,i.jsx)(h,{...e})}):h(e)}},63321:(e,n,t)=>{t.d(n,{Z:()=>i});const i=t.p+"assets/images/calendar-f891b624f3e0efb34bba582100a7d8df.png"},11151:(e,n,t)=>{t.d(n,{Z:()=>r,a:()=>a});var i=t(67294);const s={},o=i.createContext(s);function a(e){const n=i.useContext(o);return i.useMemo((function(){return"function"==typeof e?e(n):{...n,...e}}),[n,e])}function r(e){let n;return n=e.disableParentContext?"function"==typeof e.components?e.components(s):e.components||s:a(e.components),i.createElement(o.Provider,{value:n},e.children)}}}]);
Reference in a new issue View git blame Copy permalink