Hey, I'm Richard

I study Computer Science at the University of Ottawa. I write about topics that interest me on my blog. I make digital art, run marathons, and have a ton of side projects. I participate in game jams, online programming contests, and build web apps, services, and tools.

# Projects # Recent Solutions

## Trapping Rain Water

array two pointers stack
28 Jul 2019

By moving `once from left to right` across the array of heights, it’s possible to calculate the total trapped rain water using a `stack`.

## Daily Capacity

binary search optimization
1 Jun 2019

To determine the minimum capacity required to ship all packages within D days, it was optimal to use a `binary search`. Assuming that the minimum weight was `K`, we know that all capacities less than `K` will fail and all capacities larger will succeed. Thus, we perform a `binary search` over the space of all possible capacities until we find then minimum capacity `K` such that k-1 is false.

## Alien Rhyme

Suffix Tree Post Order strings
13 Apr 2019

This problem is from Round 1A Google Code Jam 2019, I solved it by constructing a `suffix tree`, which I then traversed using a `post order traversal` in order to match strings into groups of two from longest to shortest suffix. # Puzzles

## Shortest Path Sum

Floyd-Warshall graph algorithm

Given the hex string in the `white box` below. Construct a graph according to the following rules:

• Each unique letter is a node.
• Two nodes have an edge between them if they are adjacent in the string.
• The weight of the edge between two nodes is the hex value of the two connected nodes.
• If the same edge appears twice, ignore its second appearance.
• The weight of an edge from a node to itself is zero.

Find the sum of `every unique shortest path`. Two shortest paths are `unique` if one of the paths contains at least one node that the other does not. The shortest path between two nodes is a series of edges along which one could travel to get from one node to the other.

Example The hex string `5d0d` has 3 unique nodes `5, d, and 0`. As we traverse the string from left to right, we find the following edges:

• Edge `5d` with value `5 + d = 5 + 13 = 18`
• Edge `d0` with value `d + 0 = 13 + 0 = 13`
• Edge `0d` which is the same as `d0`, so we ignore it

We have 3 shortest paths to consider as follows:

• Path `0` to `d` with a cost of `13`
• Path `0` to `5` with a cost of `31`
• Path `d` to `5` with a cost of `18`
• Note, the remaining paths would just be one of the above in reverse.

So, the answer to this example case is 13 + 31 + 18 = `62`

SUBMIT
CORRECT

## Binary Search

binary search algorithm

Given the function below, find the largest integer `n` such that `query(n)` returns `false` and `query(n+1)` returns `true`. The answer is an integer between `1` and `80000000000` (80 billion!)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 `````` ``````function query(n) { let d1 = dist(n); let d2 = dist(n + 1); return d2 > d1; } function dist(v) { let c = (v + 28000000000)/10000000000; let t = c * Math.log(c)/2; let a = Math.pow(t - c, 2); let b1 = t + c; let b2 = c * Math.log(c); let b = Math.pow(b1 - b2, 2); return Math.sqrt(a + b); } ``````

SUBMIT
CORRECT

## Odd and Even Numbers 😏

tricky logic

Find the missing value (hint: read the title):

• 80618 = 4
• 10792 = 2
• 21643 = 3
• 75335 = 0
• 44713 = ?

SUBMIT
CORRECT # Games

## Maze

JOIN

Use `arrow keys` to move. Collect the `gold` before the other players. This is multiplayer game with anyone else on this site. Written with `NodeJS` and `Socket.io`. Player list and scores are shown below:

`Spread` is a game about strategically selecting a starting point for a `virus`. `Left click` on the canvas to start the spread. 