Inspired by a game which I saw mentioned in David Mond's Maths of Climate Change talk (actually, I read it rather than watched it), I've started a new competition. The aim is to save the planet!

Outline

There is a bot in #SaveThePlanet, on IRC server irc.uwcs.co.uk which listens for commands (rough protocol docs are available). It maintains a world state in which you have to, well, save the planet.

It's not always possible; you may be doomed. In fact, if you're playing against a number of evil entities intent on destroying the world, the world will be destroyed.

Climate badness is modeled by "chance of a disaster per tick", and is initially random. You can donate money per tick and hold industries. The more you donate, the better it is for the climate, and the more industry, the worse. The actual factors involved are picked at random per game, as is your initial industry count (more industry means more influence, but more likely to get disastered).

Should you save the world (read: restore climate to 0), the player who gained the most industry wins. Should you melt down the world, the player who donate the most wins. (See protocol document for specifics.)

Competition

The game will be running until the end of term. Each game will score points for the players who came out on top, and those points will be summed up over the day to produce a total. This orders the players for the day and gives points (6 for first place, 3 for second, 2 for third and 1 for fourth). Points are again aggregated over a week, and the weekly winners get prizes. Next week is a warmup (I'll use it to tweak the scoring and the game in general).

Each game, the bot picks between 2 and number of players asking to participate, and kills off the rest (players who've been in more games recently will be killed off more often) with no penalty, in order to give variation in the type of game you face.

The first competitive week runs from 00:00 Sat to 00:00 Sat over Week 9. The final week runs only until 00:00 Fri Week 10, to give me time to work out who won and present prizes at the CompSoc LAN. The final week will have £30 to the winner, £20 to runner up and £10 to third place. Prizes for the first week are undecided.

Sample code

Current version of the game bot is at: http://www.bucko.me.uk/competitions/SaveThePlanet/game.pl.txt

A sample bot (actually, 3), written in Perl, is at: http://www.bucko.me.uk/competitions/SaveThePlanet/sample.pl.txt (passwords are read from a separate file).

A Java sample using pIRCbot, is at: http://www.bucko.me.uk/competitions/SaveThePlanet/jarvur.

Win Data

You can get XML data about recent games:

• Last few games
• Last 10 games
• Today's games

Other stuff

I'll update this post as I tweak the algorithm until the start of the first week. The above code will be updated, too.

Prize is open to anyone I know and any member of CompSoc, plus anyone I feel like allowing to get the prize. If you wish to not be included in the prize giving, you can still compete, but let me know.

Good luck!

Delightful. I've been encoding some DVDs recently, and twice I've left it going on one job and returned to find my system was off, after logging the following:

May 21 06:14:35 tank kernel: [24200.843888] ACPI: Critical trip point
May 21 06:14:35 tank kernel: [24200.843888] ACPI: Unable to turn cooling device [ffff8101af06f8b0] 'on'
May 21 06:14:35 tank shutdown[27159]: shutting down for system halt
May 21 07:51:14 tank syslogd 1.5.0#5: restart.

The second time, the encode jobs appeared to have finished (I had a valid and complete AVI file), yet the system still cut out. They were simultaneous and of different lengths, so they would have finished at different times.

Further, I've been checking on sensors - the ACPI thermal_zone temperature at /proc/acpi/thermal_zone/THRM/temperature reports the same value as the w83627ehf device - specifically, 22C at idle, maybe 55C max at load. This seems pretty normal to me. The core temperatures are more worrying, at 45C idle, 82C load.

I've got a stock HSF on an E6600 at default clock. When at load, I've also got a noisy 120mm fan pointing directly at the HSF with the case open.

Are these numbers normal? If so, what's going on? Internet won't even tell me normal coretemp numbers...

Some people probably know I'm going through a password reset period right now. Included in this is my banking passwords for NatWest, Alliance and Leicester and Egg.

I have made some worrying observations to this end. Firstly, NatWest and Egg (at the least) ask for individual characters on login. This practice reduces the user's ability to add security by pre/app-ending a long known phrase to their password as an unguessable salt, but on the plus side makes it harder to keylog a password. More worrying, however, is the following bizarre password policies employed by the banks:

As you can see, there's some fairly arbitrary restrictions here. Why aren't I allowed to use symbols? Why does 2 digits and one letter make a password secure (considering, say, may12, meets this criteria)?

Do any banks let you use hardcore passwords? It'd be great if people could play around and let me know various banks' policies on passwords.

I frequently have to send messages to large numbers of people, namely the leaders of clans on the KGS Clans System. This is tedious work as the client has an awful non-keyboard navigable UI. In fact, the minimal path to send a message turns out to be:

1. Start CGoban
2. Send space to press the default activated logiin button (return doesn't work).
3. Press return twice to log in with saved user/pass.
4. Wait for the rooms box to pop up.
5. Click the menu bar (can't use a keyboard shortcut...).
6. Navigate to the User menu. Press up to get to "leave message".
7. Press tab, as it defaults to having no widget in focus.
8. Type the target user.
9. Press tab or return.
10. Type the message.
11. As you are now unable to keyboard-navigate from the input box, click "OK".

I dread to think how the author would respond were some poor disabled person to explain how painful it is to operate that monster.

Today I coded a hack/fix for this problem. I have a shell script which automates this process using xvfb, xwininfo and xte. It is now fully integrated into my admin system so that I can message various groups of clan leaders.

Java is slow, meaning there are frequent "sleep" calls to ensure things happen. Also, xte does not seem to enjoy the company of xvfb. Specifically, "key colon" produces a semicolon unless surrounded by "keydown Shift_L" and "keyup Shift_L". This happens with capital letters and many other symbols. Additionally, "key :" works on my X server but apparently not on xvfb, and "str :" works locally but gives an X error on the remote. I am unsure as to how to fix the xte problem, and have left a kludge in the script to use Perl to manipulate a string into something it'll like. It only accepts a small number of symbols.

A humongous 2 entries to this one. There was a clear winner:

Zed0

Perl, filename must be '278951438'.

sub p{print 1+int$_/3,-1-$_%3;die}@_=map{(/O/?99:/X/?1:-1)*chop$0}split/\n?/,<>.<>.<>;map{$a=@_[$_];map{$b=@_[$_];$a*$b<0|$a+$b-@_[$_]-15||p for@z}0..$_-1}@z=0..8;@_[$_]<0&&p for@z

I can't pretend to understand what it does, but it does pass all of my tests. Total length is 181. I'm informed that the filename is a magic square which is solved to find possible lines.

Rupert Swarbrick

Once again attempting to golf in a non-golfable language. This one (factor) has compulsory whitespace, compulsory non-evaluation brackets, but at least no nasty angle brackets for me to quote in my HTML.

USING: arrays kernel math combinators io sequences namespaces assocs prettyprint ; IN: A SYMBOL: z : s swap ; : a 32 s index ; : b [ 1 + ] bi@ z get { { 1 [ s ] } { 2 [ dup rot 1 = [ ] [ 4 s - s ] if ] } [ drop ] } case "," s pprint write . ; input-stream get lines dup dup [ flip ] [ dup reverse [ [ s ?nth ] map-index ] bi@ 2array ] bi 3array >alist [ first2 s z set [ [ [ 88 = ] count 2 = ] [ a ] bi and ] find a dup [ b t ] [ drop ] if ] find [ 2drop ] [ drop 0 z set [ a ] find [ a b ] [ 2drop ] if* ] if

Total length: 517 bytes. It's over half a kibibyte! Rupert has outdone himself on this one.

More amusingly, his co-ordinates are backwards, meaning it fails half of the tests if I don't reverse them. :)

I think Rupert's aiming for the "points for participation" award, perhaps...

Problem

For those enjoying the challenge of the previous post, but wanting a little more, I'm setting the challenge of writing an AI for n by n by n naughts and crosses (n less than or equal to 30, say). You are aiming to get n in a row (that is, a line of maximal length on the grid).

Your code should accept input of Y-Z grids from X=1 to n, with "," separating lines, ";" separating grids, "X" representing an X, "O" representing an O and " " (space) representing a blank space. You are to infer the size from this input.

For example:

    ,  X ,    ,    ;    ,    ,    ,    ;    , O  ,    ,    ;    ,    ,    ,    

This grid has an X on (1, 2, 3) and an O on (3, 2, 2).

You are to assume that you are playing naughts. Your code should output 3 numbers in bracket notation, with a newline, representing the (x, y, z) co-ordinates it wishes to play, for example "(1, 4, 2)\n" to play at x=1, y=4, z=2. It may take as long as it likes to do this (within reason; code which takes a very long time per move may be killed), but see below.

Your code may then exit (in which case it will be rerun with the grid which contains its own move and the response), or it may await a response move in the same "(X, Y, Z)\n" format before moving again.

The first item on the command line will always be the name of its opponent. For the same opponent, this is guaranteed to be the same, so that a learning AI may choose to scrap its cache between opponents.

Submission

Your submission should be either a source file or an archive of files. Provide some adequate instructions on how to execute it - and ensure these are easy to follow on either a 32-bit or 64-bit Debian system (64-bit preferred). Your entry will be run in its own directory, with which it is free to do as it pleases (but do not create files larger than around 100MB in total - if you are creating many large files, please note in your submission which of these may be deleted and when).

Your entry will be scored on code quality, speed and skill. All three are worth the same. Code quality will be judged by hand. Speed will be determined by the time taken to run a number of vs. matches against other AI, as will skill. These matches will probably take place on 4x4x4 or 5x5x5 boards, but your entry will be tested to ensure it at least understands how to win and block wins on larger boards. It should therefore ensure it does not spend a long time thinking about these.

Mail submissions to isreal-progcomp20090125@bucko.me.uk by the end (BST) of 25th Jan 2009.

Prizes

Prizes for winners are quite possible if the submissions are of a reasonable quality. These may be in the form of T-shirts, book tokens or similar.

Sample Code

I have written some sample code and put it online at http://www.bucko.me.uk/progcomp20090125.tar.bz2. There are two samples: uk.me.bucko.progcomp20090125.FirstEmpty and uk.me.bucko.progcomp20090125.Random. Compile them with javac uk/me/bucko/progcomp20090125/*.java; run a test with java uk.me.bucko.progcomp20090125.Test uk.me.bucko.progcomp20090125.Random uk.me.bucko.progcomp20090125.FirstEmpty 5 (for 5x5x5). Don't complain about my poor code! It's up to you to make it better if it sucks - but it does work.

Problem

Your task, should you choose to accept it, is to write an "AI" for the Naughts and Crosses. The only requirement is that your AI must, if it is possible, prevent its opponent from winning on their next move: it must block a three in a row if one is threatened. If many are threatened it must block at least one. It may not win unless this also directly blocks a win by its opponent (or there are no blocks that can be made). Otherwise it may play anywhere legal.

Input will be three lines containing X, O or space characters. You must output, on STDOUT, two integers with some amount of non-numeric separating them containing the co-ordinates to place an 'O' (the output must match the Perl regex m/(\d+)\D+(\d+)/s). The top left is (1,1); the first digit is the X co-ordinate, so the top right is (1,3). For example:

echo "X O"; echo "XOO"; echo "   "

A trivial solution to this example is the script: perl -e 'print"3,1"'

Submissions

You must submit either a command line or a source file. If you submit a command line, the full character length of the line will be used as your score. If you submit a source file, it should be executable via your chosen language's interpreter or compilable via the compiler, and the byte length of the file will be your score. If you require command line options to run, interpret or compile your code, they will be added to your source length (this includes any whitespace, so "perl -n filename" costs 3 extra characters). If your code is to be compiled, you may choose the compiled length over the source length if it is shorter.

You may use any language that I can either apt-get install onto my 32-bit or 64-bit Debian chroots, or that you provide simple instructions for me to get running on said chroot. If I can't even get the language to run, you score 9001.

Submissions to isreal-progcomp20090104@bucko.me.uk by the end of 4th January (BST).

The lowest score wins. Lowest alphanumerics breaks the tie, and further silly tiebreakers will break any further ties.

Extra

If enough people also submit an AI that can win if it is possible (this includes punishing mistakes, so "O \n X \n O" requires a move in a corner), this will also be judged in a separate category.

So, today I nipped into town and got myself some mobile broadband. I went with O₂, as their PaYG package is basically the same as most contracts (with shorter period options - £2 for a day or £7.50 for a week) -- with no minimal period, and you only pay for it it you want to use it! Of course, you have to spend £30 on the modem, but that's not such a hard hit to take.

Let's get the plus out of the way: When it's connected properly, it works. It's fast, it doesn't seem to drop out (yet); it just works.

Now, the software it comes with is atrocious. It hangs for a minute every time you connect or disconnect. It minimises to tray, and can't be told not to. It's a skinned region window. It often gives little feedback about what it's up to. And finally, they committed the ultimate crime: They didn't use a standard interface to do a standard thing. It's hardly common to O₂; my dad's got a dongle, too, and it uses some godawful software with similar problems. Seriously, XP/Vista provide a dialup service; why can't you use it?

Coverage seems somewhat iffy. I played with it a few times on the train to Edinburgh, and found it often would get a signal, but refuse to connect to it (including when stationary in a station). It worked fine both at home and in my guest house room.

I also seem to be connected through some transparent proxy on crack. It's chopping off some of the end of HTML documents, resulting in XHTML parse errors from Opera. Refreshing the pages in question always makes it work fine - it seems like it only does it on the first page view of a page, and in the case of my image repository, always immediately after the "http:" of an URL (original: '<a href="http://blah">http://blah</a>(moreHTML)'; O₂: '<a href="http://blah">http:</body>(newline)</html>(endofdoc)'). The worrying thing is that it's not a 100% chop; it's still giving a </body> and a </html> - it's not closing anything else, though.

Summary, so far: It's pretty OK, but I think I'm glad I'm on PaYG.

David Bewick

Entry in Perl, command line perl -Mbigint dbewick-entry:

$n=<>,$d=<>;map{$d/=$_ while$d%$_<1}2,5,$n>1?$n:2;7while$n%$d>0&10**++$_%$d>1;print

Score is 7 + 84 = 91. I have to say, I'm impressed by the optimisation here (ie. I don't understand it!). The code appears to first eliminate the terminating expansions and then compute expansion length. At first I thought I could shave some score with few quick modifications (use perl -p change $n=<>,$d=<> to $n=$_,$d=<>;$_=0), but alas it's score-neutral. Of the submitted solutions, this is the shortest, so is the winner.

whythehell

Entry in False (interpreter at http://wouter.fov120.com/files/lang/false/False12b.zip or http://kahneman.dyndns.org/ -- commandline false_int filename.f $a $b):

b;c;[$@$@/@*-]m:$[$1=~][[2O1Om;!2O2Om;!+0=][@1O/@2O/@]#1-]#@@[\[$2Om;!0=][1O/]#\%]$@5@!2@!1$[10*2Om;!$1>][\1+\]#%.

Score is 115, and I won't pretend to know how it works. Interestingly (and quite annoyingly for wth), False does not have a remainder operator, which is what he implemented in the first square-bracketted section. I presume the code first eliminates the terminating expansion case, then computes the length by long division.

The code has the drawback that the interpreter spams its interpreter message on every run - and since the stack is nonempty on exit, spams an error also. Both of these are on STDOUT and thus break the spec. Appending 3 % signs removes the error at the cost of 3 extra points (118 total). The former is an interpreter issue, so is forgiven.

Michael Tandy

Entry in Perl (commandline only; parameters at end of commandline):

perl -e 'sub L{($a,$b)=@_;$g=$a;for($i=1;$i<10000;$i++$g=($g*10)%$b;if($g==0)return 1;}if($g==$a%$b){return $i;}}return L($g,$b);}print L($ARGV[0],$ARGV[1]);'

1 command line bit, 149 chars in the quotes makes a score of 150. The code doesn't work, but a slight modification does:

sub L{($a,$b)=@_;$g=$a;for($i=1;$i<10000;$i++){$g=($g*10)%$b;return 1 if($g==0);if($g==$a%$b){return $i;}}return L($g,$b);}print L($ARGV[0],$ARGV[1]);

(A score of 152 including the -e). The code executes corrently on my test data set of (1, 2), (2, 7) and (7, 7). Further analysis of Michael's code reveals it will fail to terminate when fed (1, 10007), due to the odd looking recursion. Removing the central test in the for() and the recursive execution fixes this bug - and shortens the code! Using this and some other simple changes the code can be reduced to correctly executing code with a score of 107.

Rupert Swarbrick

Entry in postscript (command line echo "$a $b" | gs -dBATCH -q entry.ps):

(%stdin) run /a{{dup 3 2 roll dup 4 3 roll mod 0 eq{exch dup 3 1 roll idiv exch}exit}ifelse}loop exch pop}def /d{dup 3 2 roll dup 4 1 roll}def d d ge{exch}if pop 2 1 3 2 roll{{3 1 roll d 5 4 roll dup dup 7 1 roll 4 1 roll mod 3 1 roll exch mod add 0 eq{3 2 roll dup dup 5 4 roll exch idiv 4 2 roll idiv 3 2 roll}{3 2 roll pop exit}ifelse}loop}for exch pop 2 a 5 a dup 1 le{pop 1}{dup 1 10 4 3 roll mod{dup 1 eq{pop exch pop exit}{10 mul exch 1 add exch 3 2 roll dup 4 1 roll mod}ifelse}loop}ifelse stack

504 bytes of source, plus 7 characters in the commandline, so a score of 511. At least it was under half a kibipoint! As this submission was not near winning, I will forgive the transgression of requiring the input to have no newlines. The code appears to work on a random variety of examples. It was apparently written non-golfed and then had some disgusting emacs function reduce it to a shorter example. I'd give negative marks for not using vim, but I only have his word for it. The code removes all 2 and 5 divisors, and then finds the multiplicative order of a, mod b.

David Buckley

Entry in dc, the GNU reverse polish calculator (input on stdin; commandline dc entry.dc):

??dsb[r10*lb%r1-d0<g]dsgx+dsa[d10*lb%dla=dd0=flex]dse[zd1-nQ]sd[1nzQ]sfx

73 bytes source, commandline comes free, so score of 73. Yeah, I know, entering my own competition, I couldn't resist giving the entries a good thrashing! In pseudocode, sets $c to $a, then repeatedly does $c = ($c * 10) mod $b, firstly $b times, putting the result in $a, then until the result is either 0 or $a. In the former case, outputs 1, in the latter case outputs the number of iterations, which it tracks using the stack size (it leaks into the stack deliberately). It's probably improvable, but it's still a good quick effort.

Edit: Seems I made a bad assumption - my original code will only reliably compute 1 / b. Thanks, DBewick. Code updated to take this into account.

Watch this space for a new competition soon.

The Problem

A little simpler than the last one. Given two positive integers a and b, it is well known that there exists a decimal expansion for a÷b. For example, 17÷3 = 5.6666666666666666…. Any terminating expansion is assumed to have an infinite number of trailing zeros. Your task is to compute for any two inputs a and b the length of the repeating part of the decimal expansion. We will call this l(a, b).

To illustrate further, l(17, 3) = 1, l(3, 1) = 1 and l(1, 99) = 2.

Implementation

Your code will be run with decimal encodings of a and b seperated by newlines on standard input, or a then b as the first two command line parameters, or both (please specify or I'll assume the latter. That is:

$ (echo $a; echo $b)|$yourcommandline

$ $yourcommandline $a $b

$ (echo $a; echo $b)|$yourcommandline $a $b

Your code should output l(a, b), as a decimal number, on standard output. It may also output a single newline ("\n", "\r" or "\r\n" but no others) after this. No other output is allowed.

As input lengths are often a problem, a will be between 1 and 93744, and b will be between 1 and 75283. Your code need not behave correctly with inputs outside of these ranges, but must behave correctly inside them.

Submission

Your submission should contain: Firstly a source file (optional if you are using perl -e or similar), and secondly a command line with which to run the source file. This will replace $yourcommandline in the example above. It may also contain any number of extra files which your code needs to run.

Completed entries should be sent to: progcomp20081021@bucko.me.uk by the end of Sun 2 Nov 2008 (BST). Multiple submissions are allowed (and encouraged if they're in different languages/different algorithms).

Scoring

I apologise for this section being long, but some people always try to abuse missing clarifications.

Your score will be the total length of your code. This is the character length of your command line, plus the character length of all of your filenames, plus the byte length of all of your files. Certain things are available for free:

The command line may consist of the name of an executable on my Debian GNU/Linux system and your source file name (which I may alter, so don't try to cheat by encoding your solution into the file name) for free. It may also contain any number of switches to the executable, of which the switch symbol ("-", "--" or "/") is always free, but switches must always contain at least one character other than the switch symbol. There may only be one command on your commandline. If you want pipes etc., you must use a soure file. Your source file name is also free.

You may submit compiled code with source, provided it will compile on my Debian GNU/Linux system. In this case, your source length is deemed to be the smaller of my compiled executable and your source file, and the compiled executable's filename is free. The length of your compiler command line is added to the length of your execution command line (though the latter will probably be zero), and is scored in the same way.

For example, suppose that Jack Jones submits the command line perl -wp progcomp.pl The answer is and source file progcomp.pl with content use warnings; print "@ARGV[0..2] 4";. Besides the fact that his submission does not count, since he failed to solve the problem, his command line is free except for "wp", "The", "answer" and "is" (total length 13), his source file name is free, and his code length is 36. His score is thus 49. The parts which cost are underlined to better illustrate.

If multiple entries of a similar nature (same algorithm or same language, etc.) are recieved, they will be grouped as such when scored, so that there may be multiple 'category' winners. There will also be a winner for shortest overall code.

In the event of a tie, the lowest number of alphanumeric characters will break the tie. If this ties also, similar tiebreaks will be invented until one of them breaks the tie.

Hints

Hints at http://www.bucko.me.uk/progcomp_hints.html, for if you get stuck on how to implement the problem. But please have a go at figuring it out before you read them.

Edit: Clarified the means your application will recieve input.

Michael Tandy

$ perl -lpe'$s--;$_.=$_>4?">N":$_<4?"<N":die$s'

$ echo '$s--;$_.=$_>4?">N":$_<4?"<N":die$s' > 'Guess N, 0<N<99 short'
$ perl -lp 'Guess N, 0<N<<9 short'

perl -lpe'BEGIN{$s=6}1/$s--;$_.=$_>34?">N":$_<34?"<N":die"score $s"'

perl -lpe'BEGIN{print"Guess N,0<N<99"}$s--;$_.=$_>34?">N":$_<34?"<N":die"score $s"'

Faux

whythehell

sed 's,.*,look &|grep ^&$,e;:;s,.,,p;t'|wc -c&sleep<&-10

mulletron

import System.Posix.User

main=getLoginName>>= \x->putStrLn$x++", You just lost the game!"

$ runhaskell Progcomp.hs 
Progcomp.hs: getLoginName: invalid argument (Bad file descriptor)