Tag: programming

Smallest number -pseudo-AI-challenge

Posted by – May 23, 2011

In the proud tradition of this blog I’m holding a new smallest number tournament. The rules of this wonderful game are as follows:

  1. Each player chooses an integer greater than zero.
  2. If more than one player chooses the same number, that number is disqualified.
  3. The player who played the smallest number that didn’t get disqualified wins.

For example, if Bernie plays 1, Joan plays 2 and Dave plays 5, Bernie wins, because he played the smallest number. But if there had been an extra participant, Frank, who had also played 1, Joan would have won, because 1 would have been disqualified and 2 was the next smallest number played.

But this time I don’t want you to play the game – I want you to write a small program that plays the game. There are two ways to participate in this contest

Firstly, you can write a Python class that has at least the following methods (all of these except play() can just pass):

  • announce_num_players(integer): take an integer giving the number of participants in the tournament, don’t return anything
  • announce_game_length(integer): take an integer giving the number of rounds that will be played, don’t return anything
  • get_ready(): do any final initialization
  • announce_result(result): take a list with all the other players’ plays from the most recent round (the same player will always occupy the same place in this list)
  • play(): return your number for the round

An example minimal contestant could look like this:

class Player:
    def __init__(self, number = 4):
        self.always_play_this_number = number
    def get_ready(self):
        pass
    def announce_num_players(self, num):
        pass
    def announce_game_length(self, num):
        pass
    def announce_result(self, result):
        pass
    def play(self):
        return self.always_play_this_number

(Always play 4 unless initialized to always play something else, and don’t do anything with the extra information.)

Secondly, you can come up with a distribution. It can be a constant distribution, with constant probabilities for each number, like this:

[0.3, 0.3, 0.3, 0.1]

(play numbers 1-3 with a probability of 30% each and number 4 with a probability of 10%)

or a list comprehension that uses information about the number of players and rounds, like this:

[1.0/num_players for x in range(num_players)]

(play numbers up to the number of players with equal probability)

or any other convenient-to-me way of describing a distribution in list form.

Submissions are open until I’m satisfied that most people I know who might be interested have had time to come up with a submission. I will be happy to help with the programming if you’d like. I will be participating myself, but I promise I will not use information from other submissions.

Send submissions to my email address which should be visible in the side panel, preferably with a subject like “Smallest number challenge”.

The prize is the joy of participation, and it will be given to all participants!

Details about the tournament arrangements

I will score each tournament in at least two ways: the official way and Vadim’s zero-sum way.

  • In the official scoring, a player who plays a winning move receives one point. A player who doesn’t play a winning move receives zero points.
  • In Vadim’s zero-sum scoring for n-player tournaments, the winner gets n-1 points, losers get -1 point, and if there’s no winner, everyone gets 0 points.

I will run several tournaments with varying numbers of rounds, all with the full complement of participating players.

The tournament-running program will always call announce_game_length() and announce_num_players() for each player before a tournament starts, and announce_result() every time a round has been completed. Players that support the special value None as an argument from these functions will participate in a special tournament where the players don’t get this information.

Surprising trickiness of partitions

Posted by – March 19, 2010

I had to bang my head against the keyboard for a long time to get through problem #76 at Project Euler. It’s a deceptively “easy” problem: In how many ways can you write 100 as the sum of at least two positive integers, disregarding different ways to order the summands? (Writing integers as a sum of positive integers is known as partitioning.)

For example, 7 =
6 + 1 =
5 + 2 =
4 + 3 =
5 + 1 + 1 =
4 + 2 + 1 =
3 + 3 + 1 =
4 + 2 + 2 =
4 + 1 + 1 + 1 =
3 + 2 + 1 + 1 =
2 + 2 + 2 + 1 =
3 + 1 + 1 + 1 + 1 =
2 + 2 + 1 + 1 + 1 =
2 + 1 + 1 + 1 + 1 + 1 =
1 + 1 + 1 + 1 + 1 + 1 + 1
so there are 14 ways, not counting writing it as 7.

100 is such a small number that I figured even a stupid solution would work, but my first naive method of overgenerating sums and throwing them all into a set was too slow (it was ok up to partitioning about 15, but 20 took over a minute already). I was sure early on that some sort of recursive solution would work, but I must have had a stupid day because it took me ages to hit on a suitable idea (recurse by partioning the greatest summand into two partitions every way possible until you get to a sum of ones). The forum for discussing the solution was quite interesting; many people had thought of cleverer dynamic algorithms, finding the solution in a couple of hundredths of a second. But it turns out that there’s a lot of real number theory behind this as well. There’s a good article on MathWorld. I think the “simplest” formula people used to get solutions in something like a millisecond was this recurrence relation:

which apparently comes from a generating function using a q-series, discovered by Euler. I don’t really know what that means.

Daylight diagram

Posted by – February 4, 2010

I tried to find a diagram with the distribution of daylight over the course of a year in Helsinki but couldn’t, so I made my own. Shockingly, my little Python script worked the first time I ran it:

More…

Hell, world!

Posted by – September 3, 2009

I am supposed to learn enough libtool and autotools to package our current library and utilities in a “do it right” way. Some of my favourite things about this task so far:

  • From the libtool manual:

    But of course, that would be too simple, so many systems require that you run the ranlib command on the resulting library (to give it better karma, or something)

  • There’s a libtool demo of a trivial Hello World program & library packaged with autotools. configure.ac and Makefile.am are about 250 lines put together.
  • The program part of the demo is called “hello”, but the library is called “hell”

find-file-other-frames

Posted by – August 6, 2009

This post is for emacs users.

Every day I start work by opening a bunch of files in emacs frames. Sometimes they’re all .java, sometimes .cc and .h. Sometimes they’re all the files in some directory. C-x 5 f this.cc, C-x 5 f that.cc, C-x 5 f the-other.cc etc. I could use wildcards, but then all the files would be loaded into the same frame. There must be a better way! The following remaps the bindings for find-file-other frame to a function called find-file-other-frames, which loads one file into the current frame and the rest (found by using wildcards) into new frames of their own. If you only want to find one file, it’s opened into a new frame as usual.

;; a find-file-other-frame that for multiple files opens a new frame for each
;; one except the first
(defun find-file-other-frames (filename &optional wildcards)
  "Edit file FILENAME, in another frame.
  Like `find-file-other-frame', but in the case of multiple files loads the
  first one into the current frame and creates new frames to each of
  the remaining ones."
  (interactive (find-file-read-args "Find file(s) in other frame(s): " nil))
  (let ((value (find-file-noselect filename nil nil wildcards)))
    (if (listp value)
      (progn
        (setq value (nreverse value))
        (cons (switch-to-buffer (car value))
          (mapcar 'switch-to-buffer-other-frame (cdr value))))
      (switch-to-buffer-other-frame value))))
 
(define-key ;; replace the keybindings
  (current-global-map) [remap find-file-other-frame] 'find-file-other-frames)

edit: a perhaps better way to do the last two lines:

(substitute-key-definition
  'find-file-other-frame 'find-file-other-frames (current-global-map))

Flag diacritics

Posted by – May 11, 2009

As some readers will be aware, I’ve been “implementing flag diacritics” at my new job. This post is all about what that means.

We have a reader program which reads in morphological transducers and uses them to analyse words. A morphological transducer is a (representation of a) collection of rules about a language’s inflection. For example, if you give the French morphology transducer we have the word déclare it will output:

déclarer+verb+singular+imperative+present+secondPerson
déclarer+verb+singular+indicative+present+firstPerson
déclarer+verb+singular+indicative+present+thirdPerson
déclarer+verb+singular+subjunctive+present+firstPerson
déclarer+verb+singular+subjunctive+present+thirdPerson

From morphology alone we don’t know which of those is right (that’s a matter for another blog post), but those are the only possibilities. For example “déclarer+verb+singular+indicative+present+secondPerson” doesn’t appear because that would be (tu) declares.

Flag diacritics are a way to express long-distance morphological rules. For example, let’s say you have a language with productive compounding (one in which lots of words can form compounds with each other, like Finnish) and in which grammatical suffixes vary according to whether another word is going to be compounded onto them. A simple way to express this is to add a marker to one class of suffixes saying “another noun must be compounded onto this” and not to have it in the other class. In the Sámi morphology there’s something like this going on (but with noun-verb-compounding) and it’s controlled with the following flag diacritics:

@P.NeedNoun.ON@
@D.NeedNoun.ON@
@C.NeedNoun@

As you might have guessed, flag diacritics are always delimited by @-signs. @P.NeedNoun.ON@ means “set the NeedNoun feature to have the value ON”, @D.NeedNoun.ON@ means “if the NeedNoun feature has the value ON, this combination is disallowed” and @C.NeedNoun@ means “clear the value of the NeedNoun feature”. Before support for this was added, the Sámi transducer gave ten analyses for the word láhkaásahus, two of which were:

láhkka+N+SgGenCmp#@P.NeedNoun.ON@ásahit+V+TV+Imprt+Prs+Sg3@D.NeedNoun.ON@#
láhkka+N+SgGenCmp#ásahus@C.NeedNoun@+N+Sg+Nom@D.NeedNoun.ON@#
(# means “word boundary”)

The first one shouldn’t appear at all because first we set NeedNoun to ON (because we’re trying to interpret the ásahus part as a compounding verb which should be followed by a noun) and then disallow it (because we’ve reached the end of the word so we’re not going be compounding any more nouns). The second, however, is ok: first we clear NeedNoun (which changes nothing since it hadn’t been set in the first place), then @D.NeedNoun.ON@ says “NeedNoun must not be set to ON”, which it isn’t. Also we of course shouldn’t be outputting the flag diacritics themselves. The desired output out of those two is therefore

láhkka+N+SgGenCmp#ásahus+N+Sg+Nom#

Out of the ten possible analyses of láhkaásahus six are disallowed by the flag diacritics, so in this case it’s a pretty important rule. For any Sámi enthusiasts out there, the four currently produced analyses are

láhkka+N+SgGenCmp#ásahus+N+Sg+Nom#
láhka#ásahus+N+Sg+Nom#
láhka+N+SgCmp#ásahus+N+Sg+Nom#
láhka+N+SgNomCmp#ásahus+N+Sg+Nom#

No more tricks

Posted by – February 11, 2009

Programming used to have a lot to do with little puzzles and tricks; pointer arithmetic, bitmasks and logical operators, writing to video memory etc. Someone once asked me how do you swap the contents of two (numerical) variables without using a third one in between (of course you’d never want to do this anyway, but it’s a “fun” question). The answer is something like this:

a = a+b
b = b-a
a = a+b
b = -1*b

This is how you do it in Python:

a, b = b, a

New-fangled programming languages, eh? (Ok, Python was first released in 1991 which was a long time before I programmed anything, but anyway.)

Apropos of that last notation, this is how you write Euclid’s algorithm in Python (% is the modulo operator):

def euclid(a,b):
        while b:
                a, b = b, a%b
        return a

It’s sickeningly succinct, really. I kind of quite like it, but it kind of feels not very hardcore (comparing to, say, The Story of Mel which I’ve linked to before). Although really it’s just normality by now. Meh, meh.

What makes a man turn neutral? Lust for gold? Power? Or were you just born with a heart full of neutrality?

Computer philosophy

Posted by – February 10, 2009

>>> True or False
True
>>> True and False
False
>>> True = False
>>> not True or False
True
>>> not not not not not not False
False
>>> True/False
Traceback (most recent call last):
File “<stdin>”, line 1, in
ZeroDivisionError: integer division or modulo by zero

Tomorrow come trouble

Posted by – January 31, 2009

Evolutionary explanations for human biodiversity are creeping into the mainstream: Why are taller people more intelligent than shorter people?

In our paper, Reyniers and I propose a second possible explanation […]
1. Assortative mating of tall men and beautiful women. […]
2. Assortative mating of intelligent men and beautiful women. […]
3. Extrinsic correlation between height and physical attractiveness (produced by Mechanism 1 above) and extrinsic correlation between intelligence and physical attractiveness (produced by Mechanism 2 above) will create a second-order extrinsic correlation between height and intelligence.

We believe that this may be why taller people are more intelligent than shorter people. Another factor contributing to the seeming male advantage in intelligence is that taller parents are more likely to have sons than shorter parents. So, over many generations, more sons will inherit their parents’ genes inclining them to be taller and more intelligent, and more daughters will inherit their parents’ genes inclining them to be shorter and less intelligent. But, once again, the crucial factor is height, not sex.

In our paper, we present evidence for all of the crucial mechanisms: Taller people are on average physically more attractive than shorter people; physically more attractive people are on average more intelligent than physically less attractive people; taller people are on average more intelligent than shorter people; and taller parents are more likely to have sons than shorter parents.

I have no idea whether this particular hypothesis will turn out to be correct, but in general I suppose there must be numerous human selection mechanisms of this kind waiting to be discovered. I expect they will explain some surprising things, confirm some unpopular but well-known truths and raise much ire. As danimal, that steely fist of Internet logic, put it:

Theodosius Dobzhansky famously wrote: “Nothing in Biology Makes Sense Except in the Light of Evolution.” This includes relationships between men and women.

It surprises me that the obvious extensions of this haven’t been researched much, at least as far as I know.

If you’re into science, you’ve probably heard people complaining about scientific information and contemporary results being too proprietary and hard to discover, especially considering they’re mostly funded by the public. The Science Commons is looking to change that; let’s hope it takes off.

For math geeks: a series of Project Euler puzzles revealed something shocking to me:
– once you’ve solved problem 64 and have a good way of handling continued fractions (it’s not feasible to do this with floating point approximations)
– gone on to 65 and learned about convergents
– you run into 66 which seems to be completely unrelated and again too slow for naive bruteforce methods, so after banging your head for a while you google quadratic diophantine equations and find out that the way to solve these equations is to find the right convergents for the square roots – and this is guaranteed to find the minimal solution for every equation of this type! Check it out.

There’s a program called Microsoft Songsmith that’s supposed to allow users to sing over a backing track that follows their singing. It doesn’t really work. Except for hilarity:

Gaze long into the abyss, and the abyss gazes into you

Posted by – November 28, 2008

A conversation I had yesterday evening revealed something about computability and mathematics that hadn’t occurred to me. First, some preliminaries.

Consider a computer running a program written in a language with a finite number of symbols. The computer proceeds step by step through a string of instructions, some of which may tell it to execute commands from another location in the string of instructions. Some programs like this will run forever (for instance a program that simply enters an infinite loop) and others will do some finite number of things and then stop executing. Call these two groups of programs “non-halting” and “halting”, respectively. Defining these things suitably it is possible to prove that if a program is halting, its length determines an upper bound on the number of steps it takes. If the length of the program is n, call the maximum number of steps f(n).

Now consider a mathematical statement about the natural numbers, the unproved Goldbach’s conjecture for instance. The conjecture says that every even integer greater than 2 can be written as the sum of two primes. 4 = 2+2, 6 = 3+3, 8 = 3+5, 10 = 5+5, 60 = 7+53 etc. This is a claim about every even number there is, so presumably there isn’t any way to just do calculations to prove the conjecture: we have to prove it for all of the infinitely many even numbers at once.

Now consider a computer program that goes through even numbers, checking whether each can be written as the sum of two primes. This program is either halting or non-halting. If it is halting, Goldbach’s conjecture is false (because the program would only halt if it finds a counterexample). If Goldbach’s conjecture is true, the program is non-halting – but we can’t exactly wait forever to see that it never halts. But because we know that a program of length n will either halt by step f(n) or never, we only need to wait until the machine has taken f(n) steps. This means that it is sufficient to do finitely many calculations to find out whether Goldbach’s conjecture is true.

Unless I or the guy who explained this to me missed something; I haven’t actually read about this in a book or anything.

And of course this doesn’t make for a very feasible way to solve the problem because f(n) grows very quickly indeed.