## Project Euler 174

We shall define a square lamina to be a square outline with a square “hole” so that the shape possesses vertical and horizontal symmetry.

Given eight tiles it is possible to form a lamina in only one way: 3 × 3 square with a 1 × 1 hole in the middle. However, using thirty-two tiles it is possible to form two distinct laminae. If t represents the number of tiles used, we shall say that t = 8 is type L(1) and t = 32 is type L(2).

Let N(n) be the number of t <= 1000000 such that t is type L(n); for example, N(15) = 832.

What is sum of N(n) for n=1 to 10?

This question turned out to be fairly straight forward, and is solvable using a brute force method.

Basically, we want to arrange tiles in laminae that are symmetrical, and don’t use more than 1,000,000 tiles. The largest lamina we can arrange would then be 250,000 tiles per side, with a wall thickness of 1.

The way I set this up was to iterate through all lamina side lengths (L) from 3 to our limit, 250,000. Then, for each, iterate for different hole sizes (H) in the middle from L–2 down to 1. (The evenness of L and H have to match.)

Calculating the number of tiles is an easy prospect; t = L² – H². A dictionary then keeps track of how many tiles are used for each combination. Once we’ve brute forced all the combinations, look through the dictionary to count up all the tile values that have 10 solutions or less!

``````let history = {};
let limit = 1000000;

for (let L=3; L<250000; L++){
let L2 = L * L;
// Hole (H) size must be at least 1, smaller than or equal to l-2
for (let H=0; H<=L-2; H++){
// Calculate number of tiles (t) in lamina
let t = L2 - (H * H);

// L and H evenness must match
if (L%2 != H%2) continue;

if (t > limit) continue;

// Store result in history
if (history[t] == undefined)
history[t] = [];

history[t].push(L);
}
}

let count = 0
for (let i in history)
if (history[i].length <= 10)
count++;

console.log(count);
``````

The first time I ran this, it was much slower than anticipated. I let it run overnight, and was happy to see the correct result when I checked on it the next day. I wondered what I needed to optimize to make it run better. It turns out that I had typed the upper limit, L, as 2,500,000! By decreasing that to the proper value, that reduced the compute time to 17 seconds.

I was able to find one more low-hanging optimization opportunity. By iterating through the H values from largest to smallest, the number of tiles, t, would increase. Once that value got over the 1,000,000 limit, I can break out of the loop, and go to the next value of L. This saves a lot of time computing out of bounds answers!

``````for (let L=3; L<250000; L++){
let L2 = L * L;
// Hole (H) size must be at least 1, smaller than or equal to l-2
for (let H=L-2; H>1; H-=2){
// Calculate number of tiles (t) in lamina
let t = L2 - (H * H);

// Break once we get over limit
if (t > limit) break;

// Store result in history
if (history[t] == undefined)
history[t] = [];

history[t].push(L);
}
}
``````

This optimization pushed the compute time down to .278s! That’s a very reasonable time for Project Euler.

## 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.