12 coins, 11 gold

The Problem:

---

You have 12 gold coins — or so you think! One is fake and is known to have a different weight than the others. It could be heavier or lighter; you only know it’s wrong. Using the same simple balance scale, how do you determine the incorrect coin, and whether it is heavier or lighter, in only three weighings?

Problem from Ollie’s The Riddler

The Logic:

---

The criteria for the unique coin’s identity to be known is

• It must be weighed at least once
• If put on the scale with an equal number of coins on each side it cannot be evenly balanced
• If put on the scale more than once with an even number of coins on each side it must weight consistently more or consistently less than the other side

This is the framework for finding the solution — just find a weighing scheme that lets you remove 11 of the coins from this criteria with one that satisfies it. There is some branching allowed, depending on the result of the previous weighing you can alter which coins you put on each side of the scale. I call these Scale Configs and there are two per branch:

For example, putting coins 0,1,2,3 on one side of the scale and 4,5,6,7 on the other is Scale Config 1

The Solution:

---

My configurations are as follows:

For example, if coin 8 is made of a heavier material than metal our path would go:

1. Weigh [0,1,2,3] against [4,5,6,7]. They are evenly balanced (go to Config 3)
2. Weigh [5,6,7] (known non-unique coins) against [8,9,10]. [8,9,10] is heavier meaning the coin is among those three and heavier
3. Weigh [8] against [9]. 8 is heavier and therefore the unique coin

Code:

---

Making this in Python helped me understand the problem and the decisions I actually got to make. I was fairly confident in my Configurations 1,3,6,7 because I could logic though them — but 2, 4 and 5 were all dependent on one another and therefore annoying. It ended up saving time just writing a way to brute force different configurations for those three — yielding the solution above.

The code can be found here 

 

The code creates configurations for both sides of C2, C4, C5 then tests every coin as being both heavier and lighter. If it can deduce each one then it is a pass. It took about 20,000 iterations to get to the working solution, above.

 

Bedframe

Album of process here

The Riddler: an impromptu gambling problem

Here is a solution to the gambling problem posed in this weeks Riddler by Ollie. The problem can be found here in full:

---

You and I stumble across a 100-sided die in our local game shop. We know we need to have this die — there is no question about it — but we’re not quite sure what to do with it. So we devise a simple game: We keep rolling our new purchase until one roll shows a number smaller than the one before. Suppose I give you a dollar every time you roll. How much money do you expect to win?

Extra credit: What happens to the amount of money as the number of sides increases?

---

The key, for me, to this problem was thinking about all the branches that occur after the first roll.

Rolling a 99 on the first roll would mean there are 98 branches below that require further exploration — only rolling another 99 or 100 would end the game.

The branches that come from rolling the highest number in a four sided die case. Determining the average number of points in this case isn’t immediately obvious

However rolling a 1 on the first roll would mean there are 0 branches that require further exploration — no number on the die is smaller than that. Therefore rolling a 1 means you are expected to get 0 more points.

The branches that come from rolling the lowest number in a four sided die case. Determining that your payout is 2 is evident

Extending this thought rolling a 2 would mean that there is one branch that extends the game — rolling a  one. Therefore we know the expected reward for rolling a two is the chance that the game extends (1/100) times the sum of one (because you get to roll again) and the average of the expected values of all smaller numbers (just the ev(1), which is 0).

Generalizing this we get:

For a one hundred sided die you can see that the point values you can expect to get after the initial roll increase as the number you roll increases

Using this we would get the expected value for all sides on the die and average them — followed by adding two because we get a point for the first roll and the last roll, regardless of their value.

Again this is easy to generalize for variously sized dice, giving us the equation:

Giving us the answers of payout(100) = 2.73and as s approaches infinity the payout approaches e, Euler’s number

Edit 1/20/17: So I guess this answer is wrong. Since this model proved similar to my testing (done by just playing the game using rand()) I suspect something is up with my interpretation of the games rules

 

 

All code written in python 3.5:

import matplotlib.pyplot as plt

#Finding expected payout
results = []
for num_sides in range(10,500): 
  ev = [0]
  for i in range(1,num_sides):
    ev.append((len(ev)/num_sides)*(sum(ev)/len(ev)+1))

  results.append(2+sum(ev)/len(ev))

#Plotting
plt.plot([range(10,500)],[results],'ro')
plt.title('an impromptu gambling problem')
plt.ylabel('Expected Payout')
plt.xlabel('Number of Sides')
plt.show()

 

Lights Please 2 : Automating Phillips Hue Lights

If you look at a previous work I did here I tried to get lights to reference the forecast and wake me up with the lights that reference that. The code was done in a batch script and in general wasn’t very good… so I revisited it to make it better

---

The idea:

Have lights that turn on when my alarm does and correspond to the weather that day

---

Similar to before, I have a script that turns on the lights to that days weather using Task Manager. However this time its written in python 2.7 and distinctly tells you the weather patterns for the day

Now I use the OpenWeatherMap results to determine what the weather is. That comes back as a unique 3 digit code, which I reference against in this excel spreadsheet:

Then I color the lights according to that!

Notes:

• The excel sheet uses a macro to fill the light cells making it easier to set up schemes
• Triple blue means rain
• Red means freak out
• There are like 8 distinctions for thunderstorm which is crazy

---

Link to github

The Riddler — Gerrymandering

This week’s Riddler was finding a geometric split to segment a population:

The Problem:

Below is a rough approximation of Colorado’s voter preferences, based on county-level results from the 2012 presidential election, in a 14-by-10 grid. Colorado has seven districts, so each would have 20 voters in this model. What is the most districts that the Red Party could win if you get to draw the districts with the same rules as above? What about the Blue Party? (Assume ties within a district are considered wins for the party of your choice.)

The Process:

To solve myself and @CheddaBob10 created a random search process. Given a seed of districts the correct size it would:

• Pick a random square
• Pick a random square surrounding it. Swap them
• Check to see if the districts are contiguous
• Check to see how many of your districts have a majority. if more than your current maximum, print the districtization
• Repeat

The Results:

An example of all the districts moving about through approximately 1500 iterations:

A single district can morph like this one after approximately 1000 iterations:

The reality is that it took over 100,000 iterations to find the optimal districts. They are:

For blue to win 5 of the 7 (its upper bound):

For red to win 7 of 7:

The Code:

All written in python 2.7 with Bobby Gebert

The Riddler – Can You Survive This Deadly Board Game?

This week’s Riddler was about probability and maximizing probability of surviving a punishment. The official text is:

The Problem:

While traveling in the Kingdom of Arbitraria, you are accused of a heinous crime. Arbitraria decides who’s guilty or innocent not through a court system, but a board game. It’s played on a simple board: a track with sequential spaces numbered from 0 to 1,000. The zero space is marked “start,” and your token is placed on it. You are handed a fair six-sided die and three coins. You are allowed to place the coins on three different (nonzero) spaces. Once placed, the coins may not be moved.

After placing the three coins, you roll the die and move your token forward the appropriate number of spaces. If, after moving the token, it lands on a space with a coin on it, you are freed. If not, you roll again and continue moving forward. If your token passes all three coins without landing on one, you are executed. On which three spaces should you place the coins to maximize your chances of survival?

The Process:

To solve this you should use a few thoughts:

• The chance to land on a square is the average of the previous six squares
• The chance to land on anything below 0 is 0. The chance to “land” on zero is 1
• You only need to escape once — once you land on a square with a coin on it the game is over

Using these my code framework is pretty simple. In psuedocode:

for square_selection in range(0,3):
 set values representing square(-5) to square(-1) to 0
 set values representing square(0) to 1
 for squares(1) to square(1000):
     chance to land on it = average of previous six squares
 if the square was a "highscore" before:
     set its chance to 0
 highscore = index of max(square(1) to square(1000))

plot it

Here is the actual code

The Results:

Here is the results of probability of landing on each square if no coin has been placed

This makes the first coin placement, on square 6, very easy. Then the values of the following squares actually decrease because the possibility of getting to them from a six are removed. This leads to the following:

 

where the red represents the first placement, the blue the second and the green the second.

As a result the squares you should place coins on are 4, 5, and 6. Doing so will net you a 79% chance of survival — pretty good!

 

Swype Implementation

Swype is a popular way to type on Android phones — it works by taking the unbroken path of the fingers over letters and surmising what word was intended. An example of a finger-path would be:

——-

The Task

——-

Using this I was tasked with creating a program that takes the output from a finger path and reports back possible words that both include all the letters in that order and start and end with the letters.

A formal description of the task can be found here

——-

The Solution

——-

For this I wrote a program in python. The program is twofold:

1. Create a group of smaller dictionaries to significantly reduce my searchspace
2. Determine the dictionary of choice and find all words that fit the letter group

Working under the pretense that the word starts and ends on the first and last letter of the desired word this reduces the searchspace by 26^2, or 676 times. Since our dictionary is static the first task should only need to be run once to give us our subdictionaries. Task two is relatively simple, looking at each word in the dictionary and seeing if our letter string could possibly create it. There is a small setting to allow for double-letters (the challenge only wanted one set of double letters to be possible for some reason). The search times that I was getting are roughly equal to those of other solvers

——-

The Code

the code can be found here