Rescuing the Paratroopers

Another week, another Riddler. The question:

During their descent, three paratroopers were blown off course and crash-landed in the desert — an infinite, uniform, two-dimensional plane. They come to at a random time after the crash and must find a way to meet up. The only tool they each have is a device that displays a snapshot of the positions (but not the velocities) of all three of them in the desert. They can each use this tool only once. To make things more annoying, they’ve all been nearly blinded by sandstorms and won’t be able to physically see the others until they’ve all arrived at the same point.

Can you devise a strategy that they can agree upon beforehand and that will guarantee they will meet up? (Note that the snapshot does not indicate the specific identities of the other paratroopers, so a strategy like “let’s agree that A stands still and B and C walk to him” will not work.)

Extra credit: Is there a strategy that would work for any number of paratroopers?

Here is the strategy I devised: Everyone gets to decide their unique walking velocity — the only thing that matters is that everyone’s speed is different than the others. Then we will, when we wake up, draw a circle that is constrained by the three points of our buddies (including ourselves). This represents the path that we will walk at our set velocity in a set direction (say, clockwise). Then as we walk if another person were to wake up they would inevitably draw the same circle and embark along the same path, eventually running into one another. If we meet up we will stay exactly where we met. The third person will either be on the same path or wake up and see that the other two have met and make a bee line for the group of two.

3PersonPath.PNG

Example of path determined by a snapshot

Extrapolating this to more people, we just make a closed shape that has as many variables as there are people. For four we can use an ellipse with horizontally constrained foci, for five we can use an ellipse with unconstrained foci, etc.

4PersonPath.PNG

Example of a path made with four people

In the case with more than three people if two meet they continue to move along their path. Anyone who wakes up after two have met will again just make a bee line for where ever the two person group is at that time, knowing they will be collected at the next revolution. This should work for all cases.

Advertisements

Website Overhaul

At work I’ve been been put in charge of doing some web design. After spending more time in the space I realized just how bad my previous version of my website was — so I went ahead and redid it:

DesktopScreenshot.JPG

Homepage, as viewed from a desktop browser

This also served as a way for me to test CSS Grid. This allowed me to have drastic differences in layout from the mobile page and desktop page with lots of shared code.

PhoneScreenshot.JPG

Homepage, as viewed from a mobile browser

Overall it was a pretty pleasant experience. CSS Grid didn’t get rid of the standard CSS tomfoolery (letter spacing adjustment, weird nesting attributes, the feeling of CSS bloat) but made the general layout step much easier. Check out the website here.

Putting Sharp Objects into Round Ones

Another week, another Riddler. This first question:

Choose three points on a circle at random and connect them to form a triangle. What is the probability that the center of the circle is contained in that triangle?

The method of finding if a point was in the center was as follows: Take Triangle ABC. Find the cross product of the vectors BA and BCenter. If the resulting vector is in the same direction (As measured by the dot product) as the cross product between the vectors BA and BC then the point is on the correct side of the line BA. Put another way, the center and the point C are on the same side of line AB. Repeat this for lines AC and BC. If the center is on the correct side of all the triangle’s lines then it is inside ABC.

This simulation was iterated to yield the answer of 25%.


Next question:

Choose four points at random (independently and uniformly distributed) on the surface of a sphere. What is the probability that the tetrahedron defined by those four points contains the center of the sphere?

This was much more tricky. Firstly we had to find four points randomly distributed on a sphere. For this I used the Marsaglia method detailed here:

If  x_1, x_2 are on independent uniform distributions on from (-1,1) and rejecting points for which x_1^2+x_2^2>=1

Capture.PNG

Next I needed to see if the center was enclosed. To do this I took the determinant 5 matrices of this form:

[[A_x,A_y,A_z,1],
[[B_x,B_y,B_z,1],
[[C_x,C_y,C_z,1],
[D_x,D_y,D_z,1]]
(Tetrahedron made up of points ABCD, center is c):

The other four matrices are of that form, but replacing A’s with c’s, then B’s with c’s, then C’s with c’s and finally D’s with c’s. If all these determinants have the same sign then the point is enclosed.

This simulation was iterated to yield the answer of 12.5%.

These graphs required a bunch of code to make the graphs. This can be found here

Smash Fight Stick — Barron B0XX

The Backstory:


Super Smash Bros Melee is a wild game – its 17 years old at this point but still played both casually and competitively by many and considered one of the  best games of all time. In part because of it’s extended age it has seen many mods (some by me) both in software and in hardware. This serves as an additional controller hardware mod

The Project:


The goal for this controller is to make an ergonomic controller in the spirit of fight sticks. The inspiration comes from the player Hax$ whose hands were hurt to the point of being unable to play the game with a standard controller — in response to this he assisted in designing a controller like this and then became the best player with it.

 

Fast forward a year, he still hasn’t started selling them. So I took it upon myself to make one. For this I used Simple Controller’s guide to get an idea of how to do it. I wanted a different physical design so I went ahead and rendered it in Solidworks. Inspired by the retro electronics I wanted a see through design, which would have lots of wiring implications later:

SolidworksRender

Look at final design in Solidworks

Looked nice! Because it was going to be clear I needed to make the wiring look clean and orderly cool — hence the huge grounding bar. Next I had to just build it. Two hardware trips, two McMaster orders, three Amazon orders, one broken piece of acrylic and one burnt thumb I had it assembled.

The BarronB0XX

Completed controller

— Link to Build Pictures —

Next the code had to be edited. Thankfully Simple Controllers had created a good basis – however his controller was based on the Smashbox style controller — I wanted mine to be based on Hax’s B0XX. This meant changing some logic to reflect the changes Hax implemented, as well as those I wanted. The changes I put on github.

— Link to Github —

Just like that, its done! Now just to get good with it 🙂

 

Piano Logger

The Project

Data can be pretty sweet – I think its real fun to see progression and adds an aspect of gamification to otherwise mundane things. However, something to track piano playing didn’t exist – yet.

PianoHeatmapExample.png

Example of the heatmap generated

Therefore what I created is a piano keylogger, heatmap generator and session tracker. The idea is with this you can accurately see what keys you played and for how long you practiced – reducing my ability to lie about practice length (the initial purpose of this) while getting some cool graphs. I imagine the heatmaps for various composers works or genres of music could be insightful.

CSVExample.PNG

Example of the keylogging aspect of the program

The Program

Heatmap Creation:

To make the piano diagram we use the PIL module and lots of polygons. To get the layering I wanted (black keys over white keys) I had to draw the black keys second. This is fine but introduced a mapping problem.

IndexingExample.png

Green numbers represent the MIDI ID’s. Because I am drawing these in first I have to also fill them with the heatmap coloration first. I drew them in a simple incremental pattern (red #’s) – but now I’d need something to map the red numbers to green numbers (this problem will occur again for drawing black keys). The solution was to create mappings in a CSV file and reference the file for every key drawn in. Its obviously not optimal from a performance point of view but it is configurable and works.

Check the code out on Github

An amphibious enigma

Another week, another Riddler. The question:

A frog needs to jump across 20 lily pads. He starts on the shore (Number 0) and ends precisely on the last lily pad (Number 20). He can jump one or two lily pads at a time. How many different ways can he reach his destination?

What if he can jump one, two or three at a time? Or four? Five? Six? Etc.

The way to beat this game is to look at the ways to reach pad. The first pad (pad_1) can only be reached by jumping from pad_0, so there is only one way to get there. Pad_2 can only be reached from pad_0 and pad_1, so number of ways to get to pad_2 is the sum of the ways to get to pad_0 and pad_1, which is two. Continuing this the number of ways to get to pad_3 is the sum of pad_2 and pad_1, which is 5.

This results in the Fibonacci Sequence, shown here. This means the number of ways to get to pad_20 is 10946.

If the frog can jump 3, 4, 5, etc the sequence becomes the Tribonacci Numbers (121415), Tetranacci numbers (283953), etc

Game Show: Bright Lights, Big City

Another week, another Riddler. The question:

You and three of your friends are on a game show. On stage is a sealed room, and in that room are four sealed, numbered boxes. Each box contains one of your names, and each name is in one box. You and your friends take turns entering the room alone and opening up to two boxes, with the aim of finding the box containing your name. Everyone enters exactly once. Your team can confer on a strategy before stepping on stage, but there is no communication allowed during the show — no player knows the outcome of another player’s trip into the room.

Your team wins if it’s ultimately revealed that everyone found the box containing his or her name and loses if any player failed to do so. Obviously, the odds of winning are no better than 50 percent because any single player has a 50 percent chance of finding his or her own name. If each person opens two boxes at random, the chance of winning is (1/2)^4=1/16=6.25(1/2)^4=1/16=6.25 percent. Or to put it in technical terms: The chance of winning is not so great. Call this the naive strategy.

Your goal: Concoct a strategy that beats the naive strategy — one that gives the team a better chance of winning than 1/16.

Extra credit: Suppose there are 100 contestants and 100 boxes. Each player may open 50 boxes. The chance of winning by using the naive strategy is 1 in 2^100, or about 1 in 1.2×10301.2×1030. How much can you improve the team’s chances?

The way to beat this game is to look at the problem in a different light. My strategy to winning was to instead look at the chance that the first half of the players have their number in the first half of the boxes. If they are the first half of the players will find their numbers, meaning the second half are guaranteed to find theirs in the second half. The equation for this would look something like this:

\prod_{i=0}^{n/2}\left ( \frac{\frac{n}{2}-i}{n-i} \right )

Where

n =  number of players

This provides the answer of 1/6th for four players and 7.91e-15 for 50 players