Mancala is a traditional African two-player board game with many different variations. One variant of mancala, called Kalah, has a long history in AI research – see e.g. Silver 1961 (pdf), Bell 1968, Slagle and Dixon 1969 (pdf), and Irving et al 2000 (pdf).
Prolog is a logic programming language devised by Alain Colmerauer and his colleagues in the early 1970s. The idea behind the language is that you feed the computer a set of facts and rules, then ask the computer to use those constraints to answer questions about things you want to know.
For today’s practice, I tried to implement a program to play mancala in Prolog – specifically the version of mancala I learned as a kid, which has three seeds per hole (game rules are here). To solve the game, we can generate a tree of possible moves for each state and use minimax with alpha-beta pruning to find the optimal one. The code is here.
The way Super Bowl pools work is this: people who buy in are randomly assigned a pair of numbers on a 10-by-10 grid. At the end of each quarter, the person with the box corresponding to the last digits of the two teams’ scores wins part of the pool.
Since some of us will be participating in a pool like this on Sunday, I thought it’d be useful to look at which numbers are most likely to be profitable.
Your goal is to earn points by arranging pillows into piles of the same color. You earn 100 points whenever you make a pile of three same-colored pillows. You can only move the topmost pillow in each stack. To move a pillow, touch the stack it’s in, then touch the stack you’d like to move it to. New pillows are added at an increasing rate as the game level increases, and the game ends when any stack reaches the top of the screen.
Let’s try to implement the FFT in F#. First, here’s the naive DFT algorithm (a direct translation to code of the definition):
This gives an exact answer, but with poor performance – this has O(N2) time complexity. To improve performance, we first reduce problem scope by assuming that the number of input terms is an integral power of 2, letting us use the radix-2 DIT divide-and-conquer algorithm. This splits the DFT into two DFTs – a DFT of the even-numbered and a DFT of the odd-numbered terms:
This is fast – O(n log n) – but only handles signals with lengths of integral powers of 2. To use the radix-2 algorithm for a signal of arbitrary length, we need to increase length to the next smallest power of 2. We can’t zero-pad the signal itself, but if we express the transform as a convolution then pad the convolution we’ll get an exact answer. (My hour’s up, but if you’re interested the convolution algorithm is explained here.)
The Bureau of Labor Statistics makes state-, region-, county-, and city-level unemployment data available in flat files via FTP here. I used mapping data from the R maps library to draw the regions, but the county names there don’t match the BLS county names exactly – I removed references to “County”, “Parish”, and “City” in the county names to solve some of the mismatch problems, but a few counties are still missing. Also, I didn’t bother plotting and insetting Alaska or Hawaii.
The result (this would’ve been more interesting if I’d waited until the 2012 data was released, but still):
In the equation
where x, y, and n are positive integers, what is the least value of n where the number of distinct solutions (i.e. solutions where x, y does not recur as y, x) exceeds 1000?
Since x, y, and n are positive integers, we know that x and y must each be greater than n. Thus, we can rewrite (1) as
where a and b are again positive integers.
Doing some algebra, we get:
This means that each distinct pair of divisors of n2 represents a distinct solution to (1). Thus, if we can find the number of divisors that n2 has, we’ll know that half that number (well, actually divisors(n2) + 1 / 2 because one of the divisor pairs – n * n = n2 – won’t be doubled) is the number of solutions to (1).
Now we just need an algorithm to find the number of divisors of a given integer m. An easy way to do this would be to enumerate each of the numbers up to sqrt(m) and count each number that divides m evenly as a divisor. Since we’re going to use this algorithm many times, though, this brute force approach won’t work.
Instead, we’ll use the divisor function. This tells us that we can obtain the number of divisors of m from its prime factorization. Specifically, the number of divisors of m is the product over all distinct prime factors of the power of the prime factor, plus 1. (That is, if we can write
then we have
.) Think of it this way: each distinct divisor of m is some distinct combination of m’s prime factors, and each prime factor can appear 0, 1, …, or si times, so multiplying through for each of the prime factors we get (7).)
Now we just need an algorithm to factor a number into primes.
We can use a (pseudo-)sieve of Eratosthenes to generate a seed list of potential primes:
We use the list of primes to obtain the prime factorization:
Factoring n2 still takes some time, though, as n2 grows much more quickly than n.
Luckily, we can factor n instead. From (6) we can see that
so with the same combinatorics that gave us (7) we have
Now, finally, we can find the solution using (9):
And obtain the solution using an (empirically-determined-to-be) appropriate max prime seed:
This gives us a final answer of 180,180.
Meant to have a crack at #110 today also, but this problem took an embarassingly long time to solve.