Coding misadventure with Rust as a JS Dev: Project Euler #81
It's been quite some time that I've been wanting to play with Rust. Primarily because I've been on the dynamic and duck typed world for so long. JavaScript and Python are absolutely great languages, but I wanted to do something different, something a bit more bare metal.
With that out of the way, here's a brief introduction about me, I've been into programming since 2010. Started off with Python 2.5, then gradually moved to JavaScript (with sprinkles of TypeScript) and then a bit of PHP. But most of my work has been around PHP, Python and JavaScript.
Apart from that I am also very interested in Mathematics, and I love solving Project Euler problems. Over the years, I have solved a few challenges and I found myself bored/distracted alternatively.
And I thought, what would be a better way to learn Rust than by solving a problem on Project Euler. Oh boy, was I wrong.
The Project Euler Problem #81
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by only moving to the right and down, is indicated in bold red and is equal to 2427.
Find the minimal path sum from the top left to the bottom right by only moving right and down in matrix.txt (right click and "Save Link/Target As..."), a 31K text file containing an 80 by 80 matrix.
I picked this problem, because it looked simple enough. Also, if a problem needs combinatorics, I am going to uses Python, no two ways about it.
At first, I thought of solving this using Djikstra but I thought of challenging myself a bit more. It would've been solved but would be quite slow to be honest. (there's a forum against each answer, and I have seen quite a few answers that used Dijkstra)
Using a diamond shaped Binary tree to represent the data
This is what I sketched using an awesome app called Xournal++. I turned the matrix into a binary tree and then, I came up with this algorithm.
function findMax(node):
if node is leaf:
return node.value
else if node.left exists and node.right exists:
node.value += min(findMax(node.left), findMax(node.right))
else if node.left exists:
node.value+= findMax(node.left)
else if node.right exists:
node.value+= findMax(node.right)
result = findMax(rootNode)In English, it would be something like
- Start at bottom
- Move up, and add the smaller node's value to current node
- The final answer on the top would be the answer
Mistake #1: Not Reading the Rust book (doc) and trying to write code in it
I was decently successful in Golang with this approach, after all, I am that kind of person who could pick up programming languages and frameworks in hours, and not days.
But rust is a different beast. For example, take the below code
fn main(){
// perfectly legal code
let f;
f = 33;
println!("Value of f {}", f);
// Compiler cries in angst
let v = 32;
v = 33;
println!("Value of v {}", v);
}This is due to the fact that, in Rust, everything is immutable unless explicitly allowed. In the first case, we are merely declaring the variable f, and the variable doesn't yet exist. Only when we first assign it, does it come into existence. To make the compiler stop crying in the second case, you need to make it let mut v = 32 and then you can mutate v.
I did the best thing I could, I took advice from the internet and read the Rust by Example document. It took a day for me to go through, but I couldn't be happier.
Mistake #2: Trying to implement a Binary Tree in Rust
I tried the following after reading a lot on the topic (DS in Rust) and I believed I had a decent binary tree module in hand. Forgive the misnomer (it shouldn't be Graph)
use std::rc::Rc;
use std::cell::RefCell;
use std::fmt;
type GraphNodeRef = Rc<RefCell<GraphNode>>;
#[derive(Clone)]
pub struct GraphNode {
pub value: i32,
pub left: Option<GraphNodeRef>,
pub right: Option<GraphNodeRef>
}
impl fmt::Display for GraphNode {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "NodeVal: {}", self.value)
}
}
impl GraphNode {
pub fn new (val: i32) -> GraphNode {
GraphNode {
value: val,
left: None,
right: None
}
}
pub fn insert_left(&mut self, val: Option<GraphNodeRef>){
self.left = val;
}
pub fn insert_right(&mut self, val: Option<GraphNodeRef>){
self.right = val;
}
pub fn is_leaf(&self) -> bool {
let result: bool;
match (&self.left, &self.right) {
(None, None) => result = true,
_ => result = false
}
return result;
}
}use crate::GraphNode;
use std::fmt;
pub struct Graph<'a> {
root: &'a GraphNode
}
impl fmt::Display for Graph<'_> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "NodeVal: {}", self.root.value)
}
}
impl<'a> Graph<'_> {
pub fn new(val: &GraphNode) -> Graph {
Graph {
root: val
}
}
}pub mod graph_node;
pub mod graph;
Those who already know Rust, they must be cursing me by now. But I did not know then. After all, I am a Rust expert by now, I can handle Option<Rc<RefCell<GraphNode>>>. As you can see, my ego shattered when I tried to construct a proper Graph and traverse it.
At this point, I tried to Google "Doubly Linked List implementation in Rust" (of course, I did not want to Google a Binary Tree implementation, that would be cheating).
Guess what? While a DLL is an entry level intro to DS in C++ or Java, not here. Writing a LinkedList is surprisingly hard in Rust. And yes, I get it, a proper DLL that performs very well is hard everywhere, but I wanted "just" a DLL, not a highly efficient, ultra durable, crash free, memory safe DLL.
The Rust compiler is basically like, choose one
- write an awesome implementation
- admit that you're wrong (by writing
unsafecode) - Get a standard implementation
- GTFO (find an alternate solution)
The Solution
Well, the solution that I found was that, I could just do basic address manipulation, and not go into the Binary Tree route at all.
If I tilted the matrix (visually) in a 45 degree angle, it would look like a diamond shape. This meant, I could traverse it in 5 (2*N-1) layers.
Soon after that, I figured out the addressing of the matrix. One important part is that N-1 is the "Pivot Point". As the number of nodes per layer decreases after that. I came up with the following algorithm to calculate the index from a layer index.
At this point I took the idea to the editor, and wrote up the following function.
type Point = (usize, usize);
// ^- basically a tuple containing two numbers
fn evaluate(data: &mut Vec<Vec<i32>>) -> i32 {
let pivot_point = data.len() - 1;
// LOOP over 0 through 2N-1,
// p is hence the layer index
for p in 0..(2 * data.len() - 1) {
// for a given layer p, figure out the indexes that will be present
let mut points: Vec<Point> = Vec::new();
// if p is less than the pivot point, it's just (k, p-k)
if p <= pivot_point {
for k in 0..=p {
points.push((k, (p - k)));
}
// otherwise, it's as following
} else {
let dx = 2 * pivot_point - p;
let offset = p - pivot_point;
for k in 0..=dx {
points.push((k + offset, (dx - k) + offset));
}
}
for (x, y) in points {
match (x, y) {
// for bottom layer, do nothing
(0,0) => {},
// for edge nodes, just add the only child
(0, y) => data[x][y] += data[0][y - 1],
(x, 0) => data[x][y] += data[x - 1][0],
// otherwise just the minimum of the two nodes (left or right)
(x, y) => data[x][y] += min(data[x][y - 1], data[x - 1][y])
}
}
}
return data[pivot_point][pivot_point];
}
I then paired this with the main function, and text parsing logic (which was surprisingly simple), and this was the final "code" i came up with.
use std::cmp::min;
use std::fs;
use std::string::*;
fn parse_content(content: &String) -> Vec<Vec<i32>> {
let mut output: Vec<Vec<i32>> = Vec::new();
for line in content.lines() {
let mut console: Vec<i32> = Vec::new();
for i in line.split(',') {
console.push(i.trim().parse::<i32>().unwrap_or(0))
}
output.push(console);
}
return output;
}
type Point = (usize, usize);
fn evaluate(data: &mut Vec<Vec<i32>>) -> i32 {
let pivot_point = data.len() - 1;
for p in 0..(2 * data.len() - 1) {
let mut points: Vec<Point> = Vec::new();
if p <= pivot_point {
for k in 0..=p {
points.push((k, (p - k)));
}
} else {
let dx = 2 * pivot_point - p;
let offset = p - pivot_point;
for k in 0..=dx {
points.push((k + offset, (dx - k) + offset));
}
}
for (x, y) in points {
match (x, y) {
(0,0) => {},
(0, y) => {
data[x][y] += data[0][y - 1];
}
(x, 0) => data[x][y] += data[x - 1][0],
(x, y) => {
data[x][y] += min(data[x][y - 1], data[x - 1][y]);
}
}
}
}
return data[pivot_point][pivot_point];
}
fn main() {
let content = fs::read_to_string("inputs/matrix.txt").expect("Something went wrong");
let mut data: Vec<Vec<i32>> = parse_content(&content);
let result = evaluate(&mut data);
println!("Result: {}", result)
}I then ran it against the sample that was given, and it then produced the correct output. Soon I ran it on the complete file, and my answer was indeed accepted by Project Euler. The entire 80x80 matrix ran in just 0.008 seconds on my laptop with i5-9300H processor.
My Takeaway from learning Rust as a JS Developer
TL;DR It's hard. and it's amazing.
One reason Rust is so hard is that it makes you think about writing correct code. We intuitively think in abstractions, but we seldom forget that the CPU does not abstract the execution. It's amazing how JavaScript and Python still works very fast.
And thanks to the abstracted thought process, I wouldn't have come up with a clever and fast solution if I could implement a binary tree easily. In a way, Rust forced me to be clever and attempt alternative solutions.
I visited each node only once. In retrospect, Just to convert to a Binary tree would have taken a significantly long time to allocate and connect that many nodes, i would still be visiting each node of the matrix, then a memory allocation and linking, followed by a recursive traversal of the binary tree itself.
But I don't see Rust as a web service (which pays my bills at the moment) in 99% cases. Most services require modularity, fast E2E turnaround time and are almost always IO bound. NodeJS, Python, Golang and Java takes that spot for me in that order.
That being said, I will be solving more Project Euler problems and other problems in general and keep posting.
Thanks a lot for reading, Please share your feedback with me wherever you can.