Chess Domination

Domination is a state achieved in chess when all unoccupied squares are threatened by a piece. Its a combinatorics problem that match people like to think about — more can be read about it here

I ended up just brute forcing the problem which is like wrong but it ended up being kinda cool to see just how many iterations it takes. I ended up just having it run on a second monitor for a day or so to see how close to the optimal solution it could get.

Continue reading

Advertisements

a puzzle about domestic boundaries

Another week, another riddler. The problem is:

    Consider four square-shaped ranches, arranged in a two-by-two pattern, as if part of a larger checkerboard. One family lives on each ranch, and each family builds a small house independently at a random place within the property. Later, as the families in adjacent quadrants become acquainted, they construct straight-line paths between the houses that go across the boundaries between the ranches, four in total. These paths form a quadrilateral circuit path connecting all four houses. This circuit path is also the boundary of the area where the families’ children are allowed to roam.

    What is the probability that the children are able to travel in a straight line from any allowed place to any other allowed place without leaving the boundaries? (In other words, what is the probability that the quadrilateral is convex?)

 

I wish I could say I did something cool. Instead I just brute forced it. After ten million iterations the resulting probability of a convex ranch is 9.09%
github

Continue reading

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?

400px-The_Coin_full.jpg

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:

Untitled Diagram (1).png

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:

WithConfigsUntitled Diagram (1).png

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.

 

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.

RollMax.png

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.

Simplified.png

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

CodeCogsEqn (5).gif

Generalizing this we get:

CodeCogsEqn (4).gif

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

evPerRoll.png

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.

CodeCogsEqn (8).gif

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

CodeCogsEqn (7).gif

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

WithLabels.png

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:

colorschemes2

Then I color the lights according to that!

example.png

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

colorado.png

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:

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):

BlueColorado.png

For red to win 7 of 7:RedColorado.png

The Code:

All written in python 2.7 with Bobby Gebert