Tuesdays and KenKen

 Dev  1 Response »
Jan 132015
 

http://f.cl.ly/items/25322w1e2O163G1S1l39/kenken.jpg

So my wife and I were riding the train this morning, and having finished the crossword puzzle, we gave the KenKen a shot. It definitely provided some fun, but more so it got me thinking about combinations and permutations…

Eventually I started wondering how many total permutations there are of the 6 by 6 grid of numbers, and how many of those constitute valid KenKen boards (each row and each column must have all of the numbers between 1-6).

I ended up writing this script to brute force it:

https://gist.github.com/loisaidasam/507e82157d670023500b

But it seems like there are more combinations than I’d guessed! …

$ ./kenken.py 1
Number of unique combinations for cardinality 1: 1
Good: 1
Bad: 0

$ ./kenken.py 2
Number of unique combinations for cardinality 2: 6
Good: 2
Bad: 4
$ ./kenken.py 3
Number of unique combinations for cardinality 3: 1680
Good: 12
Bad: 1668

I’m running it with cardinality of 4 now (4×4 grid of numbers between 1-4) and it’s checking board 3 billion something…

Next steps would be trying to think of a clever way to find out the number of valid combinations for a 6×6 grid. Either we can continue with a programatic approach, either by using multiprocessing or just throwing random combinations at it, or both…

OR we could probably divert to math. A quick Google search gave me this link that seems to explain it pretty well:

http://www.math.cornell.edu/~mec/KenKen/Lecture_4.html

I guess the answer is 6! * 5! * 4! * 3! * 2! * 1!, or 24883200 (right? someone wanna double check me here?).

Long story short, it looks like there’s no shortage of viable KenKen boards!

Thanks Cornell Department of Mathematics…

Socks – Pair Matching

 Dev, Mondays and Tips, My Latest And Greatest Invention  No Responses »
Nov 032014
 

http://media.kohls.com.edgesuite.net/is/image/kohls/982103_Black?wid=500&hei=500&op_sharpen=1

Recently I bought a three-pack of these cool Nike Dri-FIT Crew Socks and I guess they mold them specifically for your left and right foot?

In getting ready for work this morning, I grabbed a pair of these bad boys, and I noticed that more often than not, the laundry place where I get my laundry done seems to pair them correctly (meaning that each “L” sock is paired with a corresponding “R” sock). I was wondering if they’re just hyper-considerate laundry folders over there, or if maybe it was just a coincidence.

Not recalling my statistics, I wrote a brute-force script to figure out what percentage of the time they would be bundled “correctly” when bundled at random:

https://gist.github.com/loisaidasam/1307fa9988404cbe1bed

And I found the answer to be an astonishing 40%!

$ python socks.py 3 -n 100000
3 pairs of socks
100000 iterations
{False: 60011, True: 39989}
Good 39.99% of the time

I don’t know about you, but I find that percentage to be super high! We’re saying that when choosing socks in random order, that almost half of the time they’ll end up being bundled “correctly” with three bundles of properly matched “R” and “L” socks!

Update: I finished getting ready and hopped on my bike, and as I was commuting into work I started thinking about my results, specifically wondering if I could come up with a statistical explanation, and I think I figured it out.

Steps and corresponding probabilities:

  1. Choose one sock at random (cool 100% of the time, hard to mess this one up)
  2. Choose a sock that matches (cool 60% of the time – of the 5 remaining socks, 3 should be the correct match, and 2 the wrong one)
  3. Choose another remaining sock at random (cool 100% of the time)
  4. Choose a sock that matches this sock (cool 66.666…% of the time – of the remaining 3 socks, 2 are the correct match and 1 is wrong)
  5. The last two socks will always match each other (100%)

Now using statistics, you multiply the probabilities of these events happening (right?):

1.00 * 0.60 * 1.00 * 66.666 * 1.00

or in fractions

3/5 * 2/3

or

2/5

or

40%

Yay, math!