-
https://www.youtube.com/watch?v=4n3l-ZcDJNY 2018 LLVM Developers’ Meeting: A. Dergachev “Faster, Stronger C++ Analysis with the Clang Static..”
-
https://www.youtube.com/watch?v=UcxF6CVueDM Clang Static Analysis - Gabor Horvath - Meeting C++ 2016
-
https://blog.rust-lang.org/2016/04/19/MIR.html rust blog on its MIR
Fast, greedy algorithm to find minimal paths from square $0$ to any square $n$ in the Infinite Sidewalk
Jane Street posted the Infinite Sidewalk problem:
Imagine standing on the first square of an infinite sidewalk labelled
$1,1,2,2,3,3…$ Whenever you are on a square labelled$k$ , you may jump$k$ squares in either direction to another square.
As shown in Proof: Every square in the Infinite Sidewalk is reachable, if we want to find a path from square
First, let
$A(n) = \frac 2 3 (n-1)$
from collections import deque | |
board = [ | |
[ 57, 33, 132, 268, 492, 732 ], | |
[ 81, 123, 240, 443, 353, 508 ], | |
[ 186, 42, 195, 704, 452, 228 ], | |
[ -7, 2, 357, 452, 317, 395 ], | |
[ 5, 23, -4, 592, 445, 620 ], | |
[ 0, 77, 32, 403, 337, 452 ], | |
] |
This ended up taking a bit longer than I'd hoped. I started out by exploring the data using some JavaScript mapping libraries, but started to realize I was going to need something with a little more heft. I turned to Ruby, and decided the RGeo gem was the right thing for the job. It's been some time since I've used Ruby regularly, so there was some time spent reacquainting myself with some language stuff. And just getting up to speed with a library I had never used before.
At the core of the problem is this: how close is each address point to a street line? I looked up the math involved, and decided calculating things was going to be too much trouble. Then I discovered a very relevant message on the RGeo-users mailing list, and the rest of the solution was structuring the data properly.
I created a helper function point_line_dist(point, line)
that returns the distance
<html> | |
<head> | |
<meta charset="UTF-8"> | |
<meta name="viewport" content="width=device-width, initial-scale=1.0"> | |
<meta http-equiv="X-UA-Compatible" content="ie=edge"> | |
<title>To Do</title> | |
<style> | |
body { | |
font-size: 1rem; | |
font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Roboto, Oxygen, Ubuntu, Cantarell, 'Open Sans', 'Helvetica Neue', sans-serif; |
Table of Contents:
When converting from a smart pointer type to a borrowed reference, you need to 'cross-borrow' data. This requires writing &*expr
or &**expr
, etc. This is usually just annoying - it doesn't help to read or write the code. When writing, you play 'type Tetris', inserting *
s until the compiler is happy. When reading it is just line noise. At best, if you are passing a value to a function, it tells you that you are passing a borrowed reference, not owned data. Alternatively, that you are passing by reference, not value.
So, we would like to spare the programmer this burden. The question is how. There have been a few proposals (rust-lang/rfcs#226, rust-lang/rfcs#241, rust-lang/rfcs#248). A central question when evaluating these proposals is whether the programmer should care first about the borrowed-ness of data or about the amount of indirection to the user. I am starting to lean more towards the position of making ownership/borrowing s