Project Euler 243 - And Python!

Introduction

Project Euler is one of my favorite ways to occasionally exercise both my puzzle-solving, math, and programming interests.  The problems tend to not be sophisticated from a software engineering angle, but the more advanced problems require both mathematical and computer science knowledge.  It seems like the more difficult problems tend to be more mathematical.

I chose problem 243 because it was in the 200s and many people had solved it.  243 is one of the few problems necessary to get the "Trinary Triumph" badge, along with 1, 3, 9, 27, and 81 (powers of 3).

I'll say this about 243 - I did a lot of work before finiding the quick mathematical solution.  I could give a quick write up on the actual solution, but I put in so much work on the solutions that didn't quite work that it would seem like a waste to me to not show the process.  The other nice thing?  Giving out the actual answer rubs me the wrong way, allowing people who haven't done the work to take credit for doing so.  There are other places where you can find the answers, but not here.  If you want to cheat, you can easily find the answer elsewhere, and more easily than you'll find here.

The other part of this is my journey into Python. I've only been coding in Python for a few months.  I took up Python basically because I hadn't done it before, and I wanted to work in a language that isn't associated with the Microsoft sphere of influence.  I worked for Microsoft, so I don't necessarily need more of that.

Part 1 - Brute Force

https://projecteuler.net/problem=243

The first step, usually, is to look at the problem from a brute force angle.  For Project Euler, I prefer problems that cannot be solved by the brute force approach within anywhere near a reasonable amount of time.  Since the problems are supposed to be solvable within a minute, I consider the problem too easy if brute force can solve it even within an hour.  Fortunately, Project Euler rarely makes the problems that easy.

Anyway, brute force is pretty much always worth trying.  It gives a way to check the more sophisticated algorithm, and often lets me wrap my head around the problem, so my brain can think of other ways to solve it.

We are looking for irreduceable fractions.  On an individual fraction basis, that seems pretty easy to do manually:  Just find out if the numerator and denominator have any common factors.  If they do, the fraction can be reduced.

Python has a greast common denominator function, gcd, which makes a brute force solution easy.

The basic brute force solution is:
Starting from d=2.
Find the resilience of d.
If it is less than 15499/94744, we have the solution.

What is the resilience R(d) of a number?

Take all the numbers from 1 to d-1.
Determine which of those numbers has a gcd with d == 1, the count of those over d-1 is the resilience.

def R(d):
    resilient_numerator = 0
    for i in range(1,d):
        if gcd(i,d) == 1:
            resilient_numerator += 1
    return Fraction(resilient_numerator,d-1)

That bit of code correctly returns the value expected for d=12 given in the example, 4/11.  So we'll consider that good for now.

Running R(d) through a range of denominators, I didn't get one less than 15499/94744 within a minute.  Or two.  Or three.

That was the first attempt, and it was no surprise it failed.  I didn't even know how close it was.

Part 2 - How close

Next I wanted to see how close I was actually getting.

def brute_lowest_resilience(maxint):
    best = Fraction(1,1)
    
    for i in range(2,maxint):
        current = R(i)
        if current < best:
            print "New lowest!", i, current, float(current)
            best = current
    return best

The goal is 15499/94744, which is around 0.163588.

So I ran my brute_lowest_resilience to 100000.

Even after a few minutes, the best result was far above the goal, creeping more slowly towards it as time went on.

Here's the output after a few minutes:

New lowest! 4 2/3 0.666666666667
New lowest! 6 2/5 0.4
New lowest! 12 4/11 0.363636363636
New lowest! 18 6/17 0.352941176471
New lowest! 24 8/23 0.347826086957
New lowest! 30 8/29 0.275862068966
New lowest! 60 16/59 0.271186440678
New lowest! 90 24/89 0.269662921348
New lowest! 120 32/119 0.268907563025
New lowest! 150 40/149 0.268456375839
New lowest! 180 48/179 0.268156424581
New lowest! 210 48/209 0.22966507177
New lowest! 420 96/419 0.229116945107
New lowest! 630 144/629 0.22893481717
New lowest! 840 192/839 0.22884386174
New lowest! 1050 240/1049 0.228789323165
New lowest! 1260 288/1259 0.228752978554
New lowest! 1470 336/1469 0.228727025187
New lowest! 1680 384/1679 0.228707564026
New lowest! 1890 432/1889 0.228692429857
New lowest! 2100 480/2099 0.228680323964
New lowest! 2310 480/2309 0.207882200087
New lowest! 4620 960/4619 0.207837194198
New lowest! 6930 1440/6929 0.207822196565
New lowest! 9240 1920/9239 0.20781469856
New lowest! 11550 2400/11549 0.207810200017
New lowest! 13860 2880/13859 0.207807201097
New lowest! 16170 3360/16169 0.207805059064
New lowest! 18480 3840/18479 0.207803452568
New lowest! 20790 4320/20789 0.207802203088
New lowest! 23100 4800/23099 0.207801203515
New lowest! 25410 5280/25409 0.20780038569
New lowest! 27720 5760/27719 0.207799704174
New lowest! 30030 5760/30029 0.19181457924

One of the first things I noticed was a sort of pattern.  6, 12, 18, 24, 30 - multiples of 6.  Then multiples of 30 - 30, 60, 90, 120, 150, 180, 210.  Then multiples of 210.  And so on.

If you take a look at where the pattern made its biggest changes: 6, 30, 210, 2310...
You can see:
6 * 5 = 30
30 * 7 = 210
210 * 11 = 2310

The pattern changes when it is a multiple of the next prime.

So, with the information I have now, I can try to find a solution.  At least, I can try narrowing down where I'll find the answer.

2*3*5*7*11*13*17*19 = 9699690

R(9699690) = 1658880/9699689
And that's around 17.1024
And that took around 16 seconds.

So, as it stands, this path will not get me to an answer in under a minute.  It does get me closer to the answer, and it does give me a better idea of just how large the answer is.

9699690 * 23 = 223092870

R(223092870) = ?
I get a MemoryError when I try to run that.

So I have two problems here.
First, the algorithm is too slow.
Second, it can't handle large enough numbers.

Next time:  MemoryErrors, for loops, the Sieve of Eratosthenes!

Archive: Google AI Challenge! (C#)

Note:  This used to be on my old blog.  That went down, but I still had the file, so here it is!

The (February 2010) Google AI Challenge was a programming contest held from 2/4/2010 - 2/26/2010.
I finished 28th out of 708 entrants. I wrote it in C#, because my most likely next job will have me working at Microsoft. Plus I wanted to try to win, so I didn't want to experiment with a language I've never studied (Python) or a language I've never been particularly good with (Lisp). I toyed with doing it in C++, but I'm more comfortable with C# right now.

My code is available (zipped up) here:

The Game

The challenge was to create an AI that would play the Tron Lightcycles game, also known as Snakes or Worms or Snafu.
In it, the two players begin in a rectangular board (sometimes with obstacles within the board). Simultaneously, each player moves one square in an available direction (N,E,S, or W), and the position the player vacates is replaced with a wall. The first player to hit a wall loses, but if both players hit a wall (or each other) at the same time, the game is a tie.

The Algorithm

My algorithm seemed to me to be pretty much straightforward and basic, right out of my college AI class. In fact, I had some known issues with my algorithm. And there were places where I figured it could be rewritten to be more efficient, whether it was just a code cleanup or a wasteful algorithm. Still, 680 participants ended up finishing behind me, so I guess I did enough.

Evaluation

My algorithm began with the evaluation code. Basically, this took the "current" state of the board, and gave an integer score based on how well my AI was doing.
In what I later learned was called using a Voronoi heuristic, I went through each square of the board, giving my AI 100 points if it was closer the square than the opponent, and subtracting 100 points if the opponent was closer. Positions that were walls went unscored.
This was not the best evaluation function. I knew early on there was an issue on certain boards where a bottleneck could easily separate some available positions with others.

#########
#   #   #
# 1##   #
#       #
#   #   #
#   #   #
#   #   #
#   #   #
#   #   #
#   #2  #
#   #   #
#   #   #
#########

In this example, player 2 isn't really in a particularly bad position. But my AI evaluates this board as being a great position for player 1. Player 1 is closer to all of the spots on the left side of the board, and some of the spots on the right side of the board (the upper ones), so player 1 is judged to have an advantage. Unfortunately for my AI, player 1's position isn't that strong - it's much closer to a tie. Not knowing that this board is evenly scored for players 1 and 2 was my AI's biggest issue.

Here's an example of a game that was lost because of this issue: http://csclub.uwaterloo.ca/contest/visualizer.php?game_id=4073327

I never got around to solving this problem before the contest ended, but apparently the #1 finisher, Andy Sloane, came up with an idea at 3am on the final day of the contest.

Lookahead

For my lookahead, I used a recursive algorithm, a variant of Negamax with alpha-beta pruning.

Basically this meant that for each possible move my AI could make, it would call my NegamaxAB function (sending the function a board that included the move made) , and whichever move returned the best score would be the move to make.
The NegamaxAB function would first check to see if the board it was given was a cutoff node (time ran out, or someone crashed, or the maximum depth to search had been reached). If so, it would evaluate that board and return it.
If it wasn't a cutoff node, the Negamax would generate all possible moves for the player to move, and then send those to the NegamaxAB function, looking for the best move (highest score). Because I was also performing alpha-beta pruning on the algorithm, I kept track of values for alpha (the minimum score for the maximizing player) and beta (the maximum score for the minimizing player). In each call to NegaMax, the positions of alpha and beta are switched, and the evaluation score is negated, allowing for the single Negamax function to put itself in the shoes of each player when it is being run for that player.

Because Negamax was designed for turn-based two player games, I made the design decision to evaluate board like a turn-based two player game. My player would go first, and the opponent would go second. So my algorithm's calculated my opponent's turn using my move as data. Basically I assumed my opponent knew exactly what I would do. This made it a little easier to port the Negamax algorithm to my code, and also made my AI's decision a bit more difficult than it actually was.

The Time Limit

Under the contest rules, each move had a one second time limit. I handled this using an iterative deepening search.

I started by performing a search 2 moves ahead (one for me, one for my opponent). That search ended with a "best move".
If there was still time, I performed a brand new search 4 moves ahead. If I didn't run out of time in the middle of this new search, the move returned would become the new "best move"
I continued doing this, adding 2 levels of lookahead at each iteration, until I ran out of time. I added two levels of lookahead to simulate both players making a move.
The best move returned from the most recent completed search was the move I made.

Filling a Separated Board

Often, my AI would find itself in a situation where it was separated from the opponent, where the two bots were in separated zones.

#########
#   #   #
#   #   #
#  1#   #
#   #   #
#   #   #
#   #2  #
#   #   #
#   #   #
#########

In this case, my AI would switch to fill mode.
My intent was to make this a breadth first search, where each node was evaluated by the number of positions accessible to it.
I ended up wastefully reusing my iterative deepening code instead, and didn't get to fixing it before I ran out of time.
I did make one improvement. Sometimes my AI would find itself staying away from small sections it couldn't fill. If there were more than one of these sections it would put all of them of until it only had the option of even partially filling one of them.

Illustrated in this game: http://csclub.uwaterloo.ca/contest/visualizer.php?game_id=4041576
In this game, my AI finds itself staying away from the two dead ends, until it finds itself forced to go to one of them. By this time, though, trying to stay away from the one-square dead ends made my AI create two multiple-square dead ends. It chose one, leaving many squares open on the board. If the fill had been better, my AI would have won that game.

So to try to fix it, I modified the evaluation to not include dead ends beyond the first. That way, my AI would allow itself to block off a dead end rather than postpone that section of the board until later, which could be deadly if there were multiple dead ends on the board. It was a definite improvement.

The Competition

I don't know how talented the field was. I assume it was pretty good. Granted, not all of the 708 entrants were particularly good or tried very hard, but I'm still assuming they were pretty good. First off, 302 of the participants submitted their code more than twenty times. That means that 302 participants actually uploaded code to the server more than twenty times. Usually, a code upload only comes after making modifications to the AI, so 302 participants seemed really motiviated to participate. Secondly, and I'm just guessing on this, but it takes a certain type of motivated individual to participate in a contest like this. I would guess that the majority of participants were above average, especially the 302. Why join otherwise.
I'm sure there were plenty of participants who didn't have the time to invest in trying to win, but the 302 made a good effort. I estimate I submitted about 30 times. I had 14 different distinct versions of my AI, and 24 unique submissions. Sometimes I resubmitted old code to get a better view of how my AI was doing.

Summary

This was one fun challenge. I enjoyed the time I put into coding up my AI, and it was icing on the cake that I managed to perform pretty well (28th out of 708, in case you don't remember). It was exciting to see how my AI fared on the leaderboard, and how my improvements were reflected on the preliminary rankings. I coded late into the night sometimes, and I sometimes woke up early to get in some coding before work. I did it because I loved it. Next time, maybe I'll win.