Project Euler 114

It’s been a while since I’ve taken the time to solve some Project Euler problems. I thought today would be a good day to pick it up and try solving one I had not been able to solve the last time I tried.

I’m going to speak generically about the problem because I don’t want to spoil it for anyone who may be trying to solve it. In brief, I had written a brute-force method for solving the problem, but as Project Euler so often does, they made the scale so huge that brute-force methods often fail. I turned to the internet to try to find a clue to point me in the right direction.

Sadly, one of the links I clicked didn’t have a clue, but just said “This is a Fibonacci sequence problem.”

I couldn’t unsee it, and it was clearly the way the problem was intended to be solved at scale. It felt like it was ruined, and I regretted trying to find assistance.

I decided to go do another problem without getting any aids or accidentally cheating. The problem I chose was another problem that scales quickly. The problem is stated as follows:

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one grey square. There are exactly seventeen ways of doing this.

How many ways can a row measuring fifty units in length be filled?

I decided to start this problem with a brute force approach, even though I knew it wouldn’t scale. I wrote a recursive function to create rows filled with tiles. I started with the length of 7 they provided in the example, and I too got the correct 17.

function recurse(array){
    // Find the length of the array
    let s = tile_sum(array); 

    // If the array it too long, abort
    if (s > limit) 
        return;

    // If the array is correct size,
    // check for uniqueness and record, abort
    if (s == limit){ 
        record(array);
        return;
    }

    // Add tiles sized 1-limit and recurse
    for (let t=1; t<=limit; t++){
        if (t == 2) continue; // Tiles length 2 don't exist

        // Add a single tile spacer in if we are adding a red tile
        if (array[array.length-1] != 1 && t > 1)
            array.push(1);

        // Add tile to the array and recurse
        recurse(array.slice().concat([t]));
    }
}

I slowly increased the length by one to make sure nothing would break in my algorithm. I also noted the numbers as it computed them.

f(7) = 17
f(8) = 27
f(9) = 42
f(10) = 72

I thought that having learned my lesson from the previous problem I might have some luck by identifying this series of numbers. I went to the OEIS (Online Encyclopedia of Integer Sequences) and entered in these integers.

Spoilers below…

The OEIS search provided a result! It was A004695, the Fibonacci sequence… (but halved). Sure enough, computing the correct number in the Fibonacci sequence, and halving it yielded the correct answer for this problem.

I can’t believe two problems in a row ended up having the same shortcut. I wonder if the next one will as well…

Phasmophobia and Bézier Curves

I’ve been playing a lot of Phasmophobia recently. It’s a ghost-hunting game where you, and a team of up-to 3 other investigators explore haunted properties looking for evidence in order to determine what type of ghost is present. At the same time you have to try to not get killed at the hands of said ghost.

So what does this game have to do with Bézier curves??

We’ll get there. Trust me.

In the most recent release, the developers added in some riddles and clues to tease something coming in the next major revision. The problem I ran into was that if I had a question about a riddle I couldn’t solve, googling would only bring up spoiler-filled results. I don’t want answers, but little nudges in the correct direction.

I decided to take it upon myself to create a repository of information about the clues so one can decide which information to be exposed to, thereby minimizing risk of unwanted spoilage. I give you, Phasmophobia Rune Hints.

This still has nothing to do with Bézier curves! Get on with it!

Dear reader, I am nearly there. Believe me!

One of the evidences of ghost ghost activity in the game is what they call “Ghost Orbs”. They are floating balls of light that are only visible on video camera. (In reality these are specs of dust reflecting light close to a lens…) In any case, I wanted to spruce up my rune hinting website with some Phasmophobia appropriate ambiance. I wanted to add some ghost orbs.

My first implementation was to take a PNG of a ghost orb and use javascript to move it in a specific direction while fading it in and out at the ends of the animation. This yielded a result and was maybe passable, but it wasn’t great. My brother suggested to use Bézier curves in order to have it follow a more natural curved path.

In this example, the ghost orbs both start and end at the same location, however the one on the left follows a linear path while the one on the right follows a Bézier curve. (The points are chosen at random, so you may have to watch a few cycles to get an interesting comparison). Below is a simplified example of the code to demonstrate the minimal logic required to compute the curved path.

function find_point_on_line(p1, p2, percent){
    let p3 = {
        "x" : ((p2.x - p1.x) * percent) + p1.x,
        "y" : ((p2.y - p1.y) * percent) + p1.y,
    }
    return p3;
}

function follow_bezier_curve(b1, b2, b3, percent){
    if (percent >= 1) return; // We finished
    let p1 = find_point_on_line(b1, b2, percent);
    let p2 = find_point_on_line(b2, b3, percent);
    let p3 = find_point_on_line(p1, p2, percent);
    move_orb(p3);
    timer = setTimeout(() => follow_bezier_curve(percent+.001), 1000/60);
}

Bézier curves are pretty common. I’ve been using them for decades in software like Adobe Illustrator or Affinity Designer. I remember learning about them in college. But I’ve actually never had a need to program my own.

As it turns out, they are really simple. A quadratic Bézier curve uses 3 points; a, b, and c. First you draw a path from a to b, and from b to c. Then you draw paths between points at equivalent subdivisions on these paths. The result is a really nice curve. It’s really hard to explain with words, so try out this interactive animation instead:

This is the type of Bézier curve I used on the Phasmophobia site.

There are also cubic Bézier curves. Cubic curves are basically two quadratic curves combined. Let’s say you have 4 paints; a, b, c, and d. You would create two quadratic curves; abc, bcd, then your final curve will be created by the same process along the resulting curves.

These 4-point quadratic curves are how vector drawing programs like Illustrator build paths. the outer two points act as nodes, and the inner two act as the handles.

Although not very complicated, I thought it was a fun diversion, and wanted to share.

More Thoughts on Lego

Quite a while back, I wrote about how much fun I was having with Lego Digital Designer (LDD). I was really pleased with that program, and have used it a lot (mostly to put together old sets from my childhood that I no longer have). Unfortunately Lego discontinued support in 2016. This wasn’t a huge deal at first; it just meant that new pieces weren’t being added. However, LDD for Mac is 32 bit, and Apple axed 32 bit support with the release of MacOS 10.15 Catalina. I actually abstained from upgrading to Catalina because of a few 32 bit apps, the most prominent of which was LDD. Eventually though, I had to upgrade and say goodbye to LDD.

Luckily, I found a way to fill the Lego shaped void in my heart. I discovered a program called Studio. Studio is developed by the people at Bricklink. It is very similar to LDD, but it is actually much better. It uses the LDRAW library of pieces so it’s parts inventory is much more complete than LDD’s.

It has a built in render function for making photo-realistic images of your creations that looks amazing. It’s really easy to use, and turns out great results.

You can import the pieces from real Lego sets by entering in the set number. All the pieces you need will be placed knolled on the build field. This is great for people who want to build sets virtually, like me, or for people who like to make instruction for My Own Creations (MOCs) where alternative builds are made using the same pieces from a real Lego set.

Overall, I think that Studio is fantastic, and I am so glad to have it available to use.

Other Thoughts on Lego

Lego has gone through many different generations and has evolved a bit with each one. I think any given generation will say the sets they grew up with were “the best,” but I find people are always most sentimental for what they had when growing up. Obviously though, what I grew up with in the 90’s was the best.

Technic

I played with Lego a lot as a kid, and I would build all sorts of things. Though I made a lot of spaceships and cars, I feel like a bulk of my free play was inventing mechanical things with Technic bricks. I remember making arms, gearing system, levers, and all sorts of interesting things.

I now play Lego with my kids, and one thing I find is how much I struggle to make mechanical things using the current Technic bricks. The bricks I am used to were just regular bricks with holes in them. My Technic cars would be two 16 long Technic bricks spaced apart and held together by a couple plates. It was quick and easy to build something like that. The new generation of Technic bricks are completely smooth, and my brain just didn’t get wired for dealing with it. I find it much more limiting somehow and struggle to build some things that I feel should be simple.

Collectible Sets

Another thing that feels like it’s changed since the 90’s is the proliferation of licensed and collectible/limited sets. The first licensed Lego set was Luke’s X-Wing (7140) which was introduced in 1999. Up to this point all Lego sets were all based on internal Lego themes, like Pirates, City, Space, etc. The popularity of licensed sets grew during the 2000’s. There were (and still are) licensed themes like Harry Potter, Star Wars, Minecraft, and Disney. And with the proliferation of these licensed sets came the behavior of collecting. People (nerds) want to display their sets or collect all their favorite things from their beloved franchises.

The old way of Legoing seemed to be buy -> build -> play -> destroy. Now a common progression is to buy -> build -> display. I am definitely guilty of this too. I have the Grogu set and you can bet I’m not letting the pieces get mixed in with everything else because it was a limited set and builds something super specific.

I recently read a comment on Hacker News where someone was lamenting that Lego sets have become 3D puzzles rather than a play system, and that sentiment really resonated with me.

Highly Specialized Pieces

Lego introduces new parts every year. They always have, and they always will. I think it’s good for things to grow and evolve, however it also feels like adding more and more parts dilutes the abstractability of the medium. Making very specific parts to a set that can only be used in a single way feels like it works against the free-play mentality that one associates with Lego.

This though really isn’t as much of a problem as one might think. If you are free-building with Lego and have these pieces, you either find creative ways to use them, or you ignore them. It’s a non-issue, but something I see come up a lot in discussions of modern-day Lego.

In any case, Lego remains one of my favorite things to play with, whether physically or digitally. It can be an open landscape for your imagination, and I’m glad that it’s available for me and my children to enjoy.