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.

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.

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.

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.

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.

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

National Squishyball League Championship

Another week, another Riddler. The question:

Congratulations! The Acme Axegrinders, which you own, are the regular season champions of the National Squishyball League (NSL). Your team will now play a championship series against the Boondocks Barbarians, which had the second-best regular season record. You feel good about Acme’s chances in the series because Acme won exactly 60 percent of the hundreds of games it played against Boondocks this season. (The NSL has an incredibly long regular season.) The NSL has two special rules for the playoffs:

1. The owner of the top-seeded team (i.e., you) gets to select the length of the championship series in advance of the first game, so you could decide to play a single game, a best two out of three series, a three out of five series, etc., all the way up to a 50 out of 99 series.
2. The owner of the winning team gets $1 million minus$10,000 for each of the victories required to win the series, regardless of how many games the series lasts in total. Thus, if the top-seeded team’s owner selects a single-game championship, the winning owner will collect $990,000. If he or she selects a 4 out of 7 series, the winning team’s owner will collect$960,000. The owner of the losing team gets nothing.

Since Acme has a 60 percent chance of winning any individual game against Boondocks, Rule 1 encourages you to opt for a very long series to improve Acme’s chances of winning the series. But Rule 2 means that a long series will mean less winnings for you if Acme does take the series.

How long a series should you select in order to maximize your expected winnings? And how much money do you expect to win?

To find this you have to find the expected value for each number of games. This ended up being:

$\sum_{n=0}^{f_{t}-1}\left(p^{f_{t}+n}\right)\left(\left(1-p\right)^{f_{t}-1-n}\right)\left(\frac{\left( 2f_{t}-1\right)!}{\left(f_{t}+n\right)!\left(f_{t}-1-n\right)!}\right)$

Where

$n =$ number of games won

$f_{t} =$ series is first to _

$p =$ probability Axegrinders win

What the heck is this? Oh man good question. Okay so first we assume that in each case we are playing the full number of games. So if it is a first to 3 (commonly referred to as a best of 5) then we are going to play five games, even if we win the first 3. This can lead to “extra” wins, but helps keep the math concise. So again in the first to 3 case:

 Axegrinders Wins Barbarians wins Ways this can occur First to 3 3 2 10 4 1 5 5 0 1

So the equation would take n=0 (no extra wins) to make the top row. The probability this happens is

$\left ( 0.6 \right )^{3}\left ( 0.4 \right )^{2}\cdot 1$

summed with the next two rows:

$\left ( 0.6 \right )^{4}\left ( 0.4 \right )\cdot 5$

$\left ( 0.6 \right )^{5}\cdot 10$

this sum, equal to 0.68, is the chance that the Axegrinders win the series. This is multiplied by the payout to get the expected value (662,000).

This gives us this wonky looking graph:

The result of this is the optimal payout is when the Axegrinders choose to play a first to 13, or best of 25. Doing so will give them an expected return of $736,222. The code: import math import matplotlib.pyplot as plt #Chances of winning def c_o_w(prob,first_to): chance_of_winning = 0 for i in range(0,first_to): games = 2*first_to-1 a_wins = first_to+i b_wins = games-a_wins individ_prob = prob**(a_wins)*(1-prob)**(b_wins)*math.factorial(games)/(math.factorial(a_wins)*math.factorial(b_wins)) chance_of_winning += individ_prob return(chance_of_winning) #Calculated chances of winning, payout and ev for each series length chances = [] payout = [] ev = [] x = [] for series_length in range(1,86): chances.append(c_o_w(0.6,series_length)) payout.append(100-series_length) ev.append(chances[series_length-1]*payout[series_length-1]) x.append(series_length) #Oh man I gotta graph this fig, ax = plt.subplots(sharey=False) pev, = ax.plot(x,ev, color = 'b', label = 'Expected Value') ax.set_ylabel("Dollars, in Thousands", color = 'b') ppay, = ax.plot(x,payout,color = 'g', label = 'Payout') ax.tick_params('y',colors = 'b') ax.set_xlabel("Best of _ Series") ax2 = ax.twinx() pchance, = ax2.plot(x,chances, color = 'm', label = 'Probability to win series') ax2.set_ylabel("Chances Axegrinders Win Series", color = 'm') ax2.tick_params('y',colors = 'm') fig.tight_layout() plt.title('Axegrinders Series Length Selection') fig.legend([pev,ppay,pchance],['Expected Value', 'Payout', 'Chances Axegrinders Win Series'],loc='lower right', borderaxespad=8.) plt.show()  The Purge Riddler Another week, another Riddler. This weeks: A town of 1,000 households has a strange law intended to prevent wealth-hoarding. On January 1 of every year, each household robs one other household, selected at random, moving all of that house’s money into their own house. The order in which the robberies take place is also random and is determined by a lottery. (Note that if House A robs House B first, and then C robs A, the houses of A and B would each be empty and C would have acquired the resources of both A and B.) Two questions about this fateful day: 1. What is the probability that a house is not robbed over the course of the day 2. Suppose that every house has the same amount of cash to begin with — say$100. Which position in the lottery has the most expected cash at the end of the day, and what is that amount?

This one revolves around lots of conditional probability which I really enjoy.

Question One:

This one is the basis for main problem. Each player has a $\frac{1}{999}$ chance in robbing an individual. Therefore the chance to NOT get robbed is the probability that each player fails to rob you, or $\left ( \frac{998}{999} \right )^{999}$. This is approximately 0.3677.

Question Two:

This is the real problem here. For each player you need to know the chance that they get robbed before its their turn, then the amount that you are likely to steal from others and finally all multiplied by the chances your stuff gets stolen. This looks like this:

$ev(n) = \left (100\cdot \left ( \frac{998}{999} \right )^{n}+100+100 \cdot \left ( 1-\left ( \frac{998}{999} \right )^{n} \right ) \right )^{999-n}$

Expected Cash Returns in Relation to Position, n with 1000 players and 100\$ starting sum

This, plotted, leaves you with the following graph:

To check the answer I plotted this against a simulated version of the game which was run a million times:


import random
import matplotlib.pyplot as plt

#Run a house robbing simulation
def house_rob(players):
holdings = players*[1]
for i in range(0,players):
unselected = True
to_take_from = 0
while to_take_from == i or unselected:
to_take_from = random.randint(0,players-1)
unselected = False
holdings[i] += holdings[to_take_from]
holdings[to_take_from] = 0
#print(holdings)
unrobbed_people = holdings.count(1)
return holdings,unrobbed_people

#Iteratively run trials
players = 1000
avg_holdings = players*[0]
num_trials = 300000
for trials in range(0,num_trials):
results = house_rob(players)
for i in range(len(results[0])):
avg_holdings[i] += results[0][i]

player_titles = []
real = []
plottable_holdings = []
delta = []
for n in range(1,players):
real.append((1*(998/999)**n+1+1*((1-(998/999)**n)*(1/999)))*(998/999)**(999-n))
player_titles.append(n)
plottable_holdings.append(avg_holdings[n]/num_trials)
delta.append(plottable_holdings[n-1]-real[n-1])

#And make those graphs
plt.scatter(player_titles,plottable_holdings)
plt.scatter(player_titles,real, color = "g")
plt.title("Expected Cash Returns in Relation to Position")
plt.xlabel("Player Position")
plt.ylabel("Expected Cash Returns, in hundreds")
plt.show()



Weighing Accurately

The Problem:

What is the smallest set of weights needed in order to weigh every integral number of pounds up to 255 pounds by putting the weights on one side of a balance scale and the object to be weighed on the other side?

If you are allowed to put weights on both sides of the scale, what is the smallest set of weights needed for the above problem?

Solution:

To represent the one side case you use the powers of two as weights. This would require the weights 1,2,4,8,16,32,64 and 128. Which weights you use would look a lot like the binary representation for the number.
The second case you get three bits of info per number so you can use powers of threes as weights. This means the weights 1,3,9,27,81 and 243g. For example to weigh something that is 22g you would put the 27, 1 and 3g on the unweighted side and the 9g on the side with the unknown object to identify it. Fun!