Coding misadventure with Rust as a JS Dev: Project Euler #81

Algorithms Nov 27, 2020

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.

Sohan's Progress in Project Euler
I should Learn Rust Meme (https://github.com/rochacbruno/rust_memes)

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.

Python vs Rust Meme (https://github.com/rochacbruno/rust_memes)

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.

$$ \begin{pmatrix} \color{red}{131} & 673 & 234 & 103 & 18\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & \color{red}{746} & \color{red}{422} & 111\\ 537 & 699 & 497 & \color{red}{121} & 956\\ 805 & 732 & 524 & \color{red}{37} & \color{red}{331} \end{pmatrix} $$

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

Converting this to a binary tree

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;
    }

    
}
src/mygraph/graph_node.rs
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
        }
    }
}
src/mygraph/graph.rs
pub mod graph_node;
pub mod graph;
src/mygraph/mod.rs

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 unsafe code)
  • 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.

Diagonally tilted matrix
Diagonally tilted matrix

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.

Roughly this is the way I figured out the indexing
Roughly this is the way I figured out the indexing

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)
}
src/main.rs

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.

Sohan Basak

Hi, I am Sohan. A software engineer by profession, I am really passionate about algorithms, AI/ML, Maths and Physics. Play the guitar as a hobby, the maths behind music is fascinating.