title: 1P5: Iterated Prisoner's Dilemma

text:
# Question
Title: 1P5: Iterated Prisoner's Dilemma
This task is part of the First Periodic Premier Programming Puzzle Push and is intended as demonstration of the new challenge-type proposal.

**The task is the write a program to play the iterated prisoner's dilemma better than other entrants.**

> Look, Vinny. We know your cellmate---what's his name? Yeah McWongski, the Nippo-Irish-Ukranian mobster--is up to something and you know what it is.
>
> We're trying to be nice here, Vinnie. Givin' you a chance.
>
> If you tells us what he's plannin' we'll see you get a good work assignment.
>
> And if you don't...

## The Rules of the Game

* The contest consists of a full round-robin (all possible pairing) of two contestants at a time (including self plays).
* There are 100 rounds played between each pair
* In each round each player is asked to choose between cooperating with the other player or betraying them, without knowing the other players intentions in the matter, *but* with a memory of the outcomes of previous rounds played against this opponent.
* Points are awarded for each round based on the combined choice. If both players cooperate they each get 2 points. Mutual betrayal yields 1 point each. In the mixed case, the betraying player is awarded 4 points and the cooperator is penalized by 1.
* An "official" match will be run not sooner than 10 days after posting with all the submissions I can get to work and be used to select the "accepted" winner. I have a Mac OS 10.5 box, so POSIX solutions should work, but there are linuxisms that don't. Likewise, I have no support for the win32 API. I'm willing to make a basic effort to install things, but there is a limit. The limits of my system in no way represent the limits of acceptable responses, simply those that will be included in the "offical" match.

## The Programmer's interface

* Entries should be in the form of programs that can be run from the command line; the decision must the (sole!) output of the program on the standard output. The history of previous rounds with this opponent will be presented as a command-line argument.
* Output is either "c" (for *clam up*) or "t" (for *tell all*).
* The history is a single string of characters representing previous rounds with the most recent rounds coming earliest in the string. The characters are
    + "K" (for *kept the faith* meaning mutual cooperation)
    + "R" (for *rat b@st@rd sold me out!*)
    + "S" (for *sucker!* meaning you benefited from a betrayal)
    + "E" (for *everyone is looking out for number one* on mutual betrayal)

## The bracket

Four players will be provided by the author

* Angel -- always cooperates
* Devil -- always talks
* TitForTat -- Cooperates on the first round then always does as he was done by in the last round
* Random -- 50/50

to which I will add all the entries that I can get to run.

The total score will be the sum score against all opponents (including self-plays only once and using the average score).

### Entrants

(current as of 2 May 2011 7:00)

The Secret Handshake | Anti-T42T Missile | Mistrust (variant) | Anti-Handshake | The Little Lisper | Convergence | Shark | Probabimatic | Pavlov - Win Stay, Lose Switch | Honor Among Thieves | Help Vampire | Druid | Little Schemer | Bygones | Tit for Two Tats | Simpleton |

## Scorer

```
#! /usr/bin/python
#
# Iterated prisoner's dilemma King of Hill Script Argument is a
# directory. We find all the executables therein, and run all possible
# binary combinations (including self-plays (which only count once!)).
#
# Author: dmckee (https://codegolf.stackexchange.com/users/78/dmckee)
#
import subprocess
import os
import sys
import random
import py_compile

###
# config
PYTHON_PATH = '/usr/bin/python' #path to python executable

RESULTS = {"cc":(2,"K"), "ct":(-1,"R"), "tc":(4,"S"), "tt":(1,"E")}

def runOne(p,h):
    """Run process p with history h and return the standard output"""
    #print "Run '"+p+"' with history '"+h+"'."
    process = subprocess.Popen(p+" "+h,stdout=subprocess.PIPE,shell=True)
    return process.communicate()[0]

def scoreRound(r1,r2):
    return RESULTS.get(r1[0]+r2[0],0)

def runRound(p1,p2,h1,h2):
    """Run both processes, and score the results"""
    r1 = runOne(p1,h1)
    r2 = runOne(p2,h2)
    (s1, L1), (s2, L2) = scoreRound(r1,r2), scoreRound(r2,r1)
    return (s1, L1+h1),  (s2, L2+h2)

def runGame(rounds,p1,p2):
    sa, sd = 0, 0
    ha, hd = '', ''
    for a in range(0,rounds):
        (na, ha), (nd, hd) = runRound(p1,p2,ha,hd)
        sa += na
        sd += nd
    return sa, sd

def processPlayers(players):
    for i,p in enumerate(players):
        base,ext = os.path.splitext(p)
        if ext == '.py':
            py_compile.compile(p)
            players[i] = '%s %sc' %( PYTHON_PATH, p)
    return players

print "Finding warriors in " + sys.argv[1]
players=[sys.argv[1]+exe for exe in os.listdir(sys.argv[1]) if os.access(sys.argv[1]+exe,os.X_OK)]
players=processPlayers(players)
num_iters = 1
if len(sys.argv) == 3:
    num_iters = int(sys.argv[2])
print "Running %s tournament iterations" % (num_iters)
total_scores={}
for p in players:
    total_scores[p] = 0
for i in range(1,num_iters+1):
    print "Tournament %s" % (i)
    scores={}
    for p in players:
        scores[p] = 0
    for i1 in range(0,len(players)):
        p1=players[i1];
        for i2 in range(i1,len(players)):
            p2=players[i2];
#        rounds = random.randint(50,200)
            rounds = 100
            #print "Running %s against %s (%s rounds)." %(p1,p2,rounds)
            s1,s2 = runGame(rounds,p1,p2)
            #print (s1, s2)
            if (p1 == p2):
                scores[p1] += (s1 + s2)/2
            else:
                scores[p1] += s1
                scores[p2] += s2

    players_sorted = sorted(scores,key=scores.get)
    for p in players_sorted:
        print (p, scores[p])
    winner = max(scores, key=scores.get)
    print "\tWinner is %s" %(winner)
    total_scores[p] += 1
print '-'*10
print "Final Results:"
players_sorted = sorted(total_scores,key=total_scores.get)
for p in players_sorted:
    print (p, total_scores[p])
winner = max(total_scores, key=total_scores.get)
print "Final Winner is " + winner

```
* Complaints about my horrible python are welcome, as I am sure this sucks more than one way
* Bug fixes welcome

**Scorer Changelog:**

* Print sorted players and scores, and declare a winner (4/29, Casey)
* Optionally run multiple tournaments (`./score warriors/ num_tournaments)`) default=1 , detect & compile python sources (4/29, Casey)
* Fix particularly dumb bug in which the second player was being passed a incorrect history. (4/30, dmckee; thanks Josh)

## Initial warriors

By way of example, and so that the results can be verified

**Angel**

```
#include <stdio.h>
int main(int argc, char**argv){
  printf("c\n");
  return 0;
}

```

or

```
#!/bin/sh
echo c

```

or

```
#!/usr/bin/python
print 'c'

```

**Devil**

```
#include <stdio.h>
int main(int argc, char**argv){
  printf("t\n");
  return 0;
}

```

**Random**

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
int main(int argc, char**argv){
  srandom(time(0)+getpid());
  printf("%c\n",(random()%2)?'c':'t');
  return 0;
}

```

Note that the scorer may re-invoke the warrior many times in one second, so a serious effort must be made to insure randomness of the results if time is being used to seed the PRNG.

**TitForTat**

```
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char**argv){
  char c='c';
  if (argv[1] && (
          (argv[1][0] == 'R') || (argv[1][0] == 'E')
          ) ) c='t';
  printf("%c\n",c);
  return 0;
}

```

The first one that actually *does something* with the history.

**Running the scorer on only the provided warriors yields**

```
Finding warriors in warriors/
Running warriors/angel against warriors/angel.
Running warriors/angel against warriors/devil.
Running warriors/angel against warriors/random.
Running warriors/angel against warriors/titfortat.
Running warriors/devil against warriors/devil.
Running warriors/devil against warriors/random.
Running warriors/devil against warriors/titfortat.
Running warriors/random against warriors/random.
Running warriors/random against warriors/titfortat.
Running warriors/titfortat against warriors/titfortat.
('warriors/angel', 365)
('warriors/devil', 832)
('warriors/random', 612)
('warriors/titfortat', 652)

```

That devil, he's a craft one, and nice guys apparently come in last.

## Results

of the "official" run

```
('angel', 2068)
('helpvamp', 2295)
('pavlov', 2542)
('random', 2544)
('littleschemer', 2954)
('devil', 3356)
('simpleton', 3468)
('secrethandshake', 3488)
('antit42t', 3557)
('softmajo', 3747)
('titfor2tats', 3756)
('convergence', 3772)
('probabimatic', 3774)
('mistrust', 3788)
('hyperrationalwasp', 3828)
('bygones', 3831)
('honoramongthieves', 3851)
('titfortat', 3881)
('druid', 3921)
('littlelisper', 3984)
('shark', 4021)
('randomSucker', 4156)
('gradual', 4167)
        Winner is ./gradual

```

# Answer
> 12 votes
## Gradual

This strategy is based on a paper by Beaufils, Delahaye and Mathieu. My C really isn't the best, so if anyone has any suggestions to improve/speed up the code, let me know!

\[Edit\] Worth to note is that Gradual was designed to be a strategy that outperforms Tit for Tat. It has similar properties in that it is willing to cooperate and retaliates against a defecting opponent. Unlike Tit for Tat, which only has a memory of the last round played, Gradual will remember the complete interaction and defect the number of times the opponent has defected so far. It will offer mutual cooperation afterwards again, though.

As usual, the performance of the strategy depends a bit on the line-up of other strategies. Also the original paper wasn't really clear on some details.

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
    if(argc == 1){
        printf("c\n");
        return 0;
    }

    size_t l = strlen(argv[1]);
    int i;
    size_t currentSequence = 0;
    size_t totalDefects = 0;
    size_t lastDefects = 0;

    for(i = l-1; i >= 0; i--){
        if(argv[1][i] == 'E' || argv[1][i] == 'R'){
            totalDefects++;
            currentSequence = 0;
        } else if(argv[1][i] == 'S') {
            currentSequence++;
        }
    }

    if(currentSequence < totalDefects)
        // continue defect sequence
        printf("t\n");
    else if(argv[1][0] == 'S' || argv[1][0] == 'E' ||
            argv[1][1] == 'S' || argv[1][1] == 'E')
        // blind cooperation
        printf("c\n");
    else if(argv[1][0] == 'R')
        // start new defect sequence
        printf("t\n");
    else
        printf("c\n");

    return 0;
}

```

# Answer
> 11 votes
## The Secret Handshake

```
#!/usr/bin/python
import sys
import random

def main():
    if len(sys.argv) == 1:
        hist = ""
    else:
        hist = sys.argv[1]
    if len(hist) <= len(TAG) and hist == TAGMATCH[len(TAG) - len(hist):]:
        print TAG[len(TAG) - len(hist) - 1]
        return
    if hist[-len(TAG):] == TAGMATCH:
        print 'c'
        return
    print "t"

def getTag():
    global TAG
    filename = sys.argv[0]
    filename = filename.replace(".pyc", ".py")
    f = open(filename, 'r')
    code = f.read().split('\n')
    f.close()
    if len(code[1]) == 0 or code[1][0] != '#':
        random.seed()
        newtag = 't' * 10
        cs = 0
        while cs < 3:
            pos = random.randint(0, 8)
            if newtag[pos] == 't':
                newtag = newtag[:pos] + 'c' + newtag[pos+1:]
                cs += 1
        code.insert(1, '#%s' % newtag)
        f = open(filename, 'w')
        f.write('\n'.join(code))
        f.close()
        TAG = newtag
    else:
        TAG = code[1][1:]
    global TAGMATCH
    TAGMATCH = TAG.replace('c', 'K').replace('t', 'E')

if __name__ == "__main__":
    getTag()
    main()

```

The strategy here is to sacrifice the first 10 rounds to performing a "secret" handshake. If I'm celled with myself, I then recognize the history of the first 10 moves and put on my Angel cap for the rest of the game. As soon as I recognize that my cellmate isn't myself, I transform into a Devil in an attempt to take advantage of overly cooperative cellmates.

Whether sacrificing the first 10 rounds will allow me to edge out the Devil itself depends strongly on how many entries there are. To minimize the damage, only 3 cooperates show up in the handshake.

Edit: TAGMATCH dynamic now to prevent stupid errors like changing only one of them and so I can make TAG dynamic at some point in the future.

Edit 2: Now randomly generates the tag on the first run and stores it in the file specified by `sys.argv[0]` (`.pyc` replaced by `.py` so it goes to the code, not bytecode, file). I think this is the only information all of my instances have that no one else has, so it seems like the only option for avoiding parasites.

# Answer
> 6 votes
# The Little Lisper

```
(setf *margin* (/ (+ 40 (random 11)) 100))
(setf *r* 0.0)
(setf *s* 0.0)
(setf *k* 0.0)
(setf *e* 0.0)

;; step 1 - cout up all the games results

(loop for i from 1 to (length(car *args*)) do
    (setf foo (char (car *args*) (1- i)))
    (cond
        ((equal foo #\R) (setf *r* (1+ *r*)))
        ((equal foo #\S) (setf *s* (1+ *s*)))
        ((equal foo #\K) (setf *k* (1+ *k*)))
        ((equal foo #\E) (setf *e* (1+ *e*)))
    )
)

(setf *sum* (+ *r* *s* *k* *e*))

;; step 2 - rate trustworthiness
(if (> *sum* 0)
    (progn
        (setf *dbag* (/ (+ *r* *e*) *sum*)) ; percentage chance he rats
        (setf *trust* (/ (+ *s* *k*) *sum*)); percentage chance he clams
    )
    (progn
        (setf *dbag* 0) ; percentage chance he rats
        (setf *trust* 0); percentage chance he clams
    )
)

;; step 3 - make a decision (the hard part....)

(write-char
    (cond
        ((> *sum* 3) (cond
                    ((or (= *dbag* 1) (= *trust* 1)) #\t) ; maximizes both cases
                                                          ; takes advantage of the angel, crockblocks the devil
                    ((> (+ *dbag* *margin*) *trust*) #\t) ; crockblock statistical jerks
                    ((< *dbag* *trust*) #\c)              ; reward the trusting (WARN - BACKSTABBING WOULD IMPROVE SCORE)
                    ((and
                        (= (floor *dbag* *margin*) (floor *trust* *margin*))
                        (not (= 0 *dbag* *trust*)))
                        #\t)                              ; try to backstab a purely random opponent, avoid opening w/ a backstab
                    )
        )
        (t #\c)                                            ; defalt case - altruism
    )
)

```

# The Devil

Consider the following, format (Player1, Player2)

* (C, T) - P2 gains *FOUR POINTS* for his treachery, while P1 *LOOSES ONE*
* (T, T) - *P2 AND P1 GAIN 1*

Assuming that P2 is the devil, there is no way that the devil can ever loose points, in fact the worst that he can do is gain only one point. Up against a purely random opponent therefore, the devil's worst possible score will be exactly (5/2)\*n where n is the number of "games" played. His absolute worst-case is against himself, where his score will be n, and his best-case is against an angel, which will be 4\*n

# Assert : optimal\_strat = devil

this is a tourney. Backstabbing my cell-mate is a much better strategy than cooperation because it helps *MY SCORE* more (+4). BONUS - he gets slammed (-1)! If I stick my neck out for him, I stand to gain (+2) and loose (-1). Therefor statistically backstabbing is rewarded.

# But Is It Optimal?

There is no reason to EVER (under this scoring system) co-operate.

* If you chose the wrong time to clam up, you loose out.
* If you rat, at least you don't loose anything.
* If you rat and he's dumb, you gain 2x more than if you had been a good pall.

In the KOTH system, maximization of returns is essential. Even if you have two bots who get perfectly synced and co-operate, their individuals scores will still only get boosted by 200 points for their sportsmanship. A devil on the other hand will earn at least 100 points, with an average case of 200 and a maximum of 400, and cost his opponents up to 100 points each! So practically, the devil really scores an average game of 300, spiking to 500.

# Bottom line - time will tell

To me, it looks like the scoring should be re-considered lest the devil take the day. Increasing the co-operation score to 3 all might do it. It is possible however to detect devils and prevent them from scoring their full 400, as pavlov and spite show. Can I prove that either one will pick up enough points for their cooperation to justify their faith? no. All of that is dependent on the final field of contenders.

> GL, HF!

And please do your worst to this post. I wanna write my senior paper on this when all's said and done.

# Version history

1. Added a margin variable which changes Lisper's tolerance for duchebaggery randomly.
2. Updated lisper to clam for the first two rounds to get off on the right foot with co-operative opponents
3. Used a genetic algorithm to find the most robust values for the random threshold generator based on their maximum cumulative score against a standard set of opponents. Posted update including them.

**OFFICIAL VERSION OF LISPER**

**DEVEL VERSION OF LISPER**

# Answer
> 5 votes
## Mistrust (variant)

This one came out first in my own tests years ago (back then I was in 11th grade and did a tiny thesis on exactly this, using strategies devised by other students as well). It starts out with the sequence `tcc` ( and plays like Tit for Tat after that.

Apologies for the horrible code; if someone can make that shorter while not exactly golfing it, I'd be grateful :-)

```
#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[]) {
    if (argc == 1)
        printf("t\n");
    else switch (strlen(argv[1])) {
        case 0:
            printf("t\n");
            break;
        case 1:
        case 2:
            printf("c\n");
            break;
        default:
            if (argv[1][0] == 'R' || argv[1][0] == 'E')
                printf("t\n");
            else
                printf("c\n");
            break;
    }

    return 0;
}

```

# Answer
> 5 votes
## Anti-T42T Missile

```
#!/usr/bin/python

"""
Anti-T42T Missile, by Josh Caswell

That Tit-for-two-tats, what a push-over!
  T42T: ccctcctcc...
AT42TM: cttcttctt...
        KSSRSSRSS...
"""
import sys
try:
    history = sys.argv[1]
except IndexError:
    print 'c'
    sys.exit(0)

if history[:2] == 'SS':
    print 'c'
else:
    print 't'

```

Does reasonably well against the base set of warriors: kills Angel, slightly beaten by Devil (but keeps his score low), generally beats RAND handily, and just barely beats Tit for Tat. Does poorly when playing against itself.

# Answer
> 4 votes
## Convergence

Initially nice, then plays randomly with an eye on the opponent's history.

```
/* convergence
 *
 * A iterated prisoners dilemma warrior for
 *
 * Strategy is to randomly chose an action based on the opponent's
 * history, weighting recent rounds most heavily. Important fixed
 * point, we should never be the first to betray.
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#include <string.h>

int main(int argc, char**argv){
  srandom(time(0)+getpid()); /* seed the PRNG */
  unsigned long m=(1LL<<31)-1,q,p=m;
  if (argc>1) {
    size_t i,l=strlen(argv[1]);
    for (i=l; --i<l; ){
      switch (argv[1][i]) {
      case 'R':
      case 'E':
    q = 0;
    break;
      case 'K':
      case 'S':
    q = m/3;
    break;
      }
      p/=3;
      p=2*p+q;
    }
  }
  /* printf("Probability of '%s' is %g.\n",argv[1],(double)p/(double)m); */
  printf("%c\n",(random()>p)?'t':'c');
  return 0;
}

```

I've tried diddling the weighting on the history, but haven't properly optimized it.

# Answer
> 4 votes
## Shark

```
#!/usr/bin/env python

"""
Shark, by Josh Caswell

Carpe stultores.
"""

import sys

HUNGER = 12

try:
    history = sys.argv[1]
except IndexError:
    print 'c'
    sys.exit(0)

if history.count('S') > HUNGER:
    print 't'
else:
    print 'c' if history[0] in "SK" else 't'

```

Does quite well against the base roster.

# Answer
> 3 votes
## Pavlov - Win Stay, Lose Switch

On the first turn it cooperates, and then it cooperates *if and only if* both players opted for the same choice in the previous move.

```
#!/usr/bin/python
import sys

if len(sys.argv) == 1:
    print 'c'
else:
    hist = sys.argv[1]
    if hist[0] == 'K' or hist[0] == 'E':
        print 'c'
    else:
        print 't'

```

# Answer
> 3 votes
## "Probabimatic"

Starts by cooperating, then picks whichever option gives it the highest expected value. Simple.

```
#include <stdio.h>

void counts(char* str, int* k, int* r, int* s, int* e) {
    *k = *r = *s = *e = 0;
    char c;
    for (c = *str; c = *str; str++) {
        switch (c) {
            case 'K': (*k)++; break;
            case 'R': (*r)++; break;
            case 'S': (*s)++; break;
            case 'E': (*e)++; break;
        }
    }
}

// Calculates the expected value of cooperating and defecting in this round. If we haven't cooperated/defected yet, a 50% chance of the opponent defecting is assumed.
void expval(int k, int r, int s, int e, float* coop, float* def) {
    if (!k && !r) {
        *coop = .5;
    } else {
        *coop = 2 * (float)k / (k + r) - (float)r / (k + r);
    }
    if (!s && !e) {
        *def = 2.5;
    } else {
        *def = 4 * (float)s / (s + e) + (float)e / (s + e);
    }
}

int main(int argc, char** argv) {
    if (argc == 1) {
        // Always start out nice.
        putchar('c');
    } else {
        int k, r, s, e;
        counts(argv[1], &k, &r, &s, &e);
        float coop, def;
        expval(k, r, s, e, &coop, &def);
        if (coop > def) {
            putchar('c');
        } else {
            // If the expected values are the same, we can do whatever we want.
            putchar('t');
        }
    }
    return 0;
}

```

Used to start by cooperating, but now it seems that defecting actually works better. EDIT: Oh wait, it actually doesn't.

# Answer
> 3 votes
## Honor Among Thieves

```
#!/usr/bin/env python

"""
Honor Among Thieves, by Josh Caswell

I'd never sell out a fellow thief, but I'll fleece a plump mark,
and I'll cut your throat if you try to cross me.
"""

from __future__ import division
import sys

PLUMPNESS_FACTOR = .33
WARINESS = 10

THIEVES_CANT = "E" + ("K" * WARINESS)

try:
    history = sys.argv[1]
except IndexError:
    history = ""

if history:
    sucker_ratio = (history.count('K') + history.count('S')) / len(history)
    seem_to_have_a_sucker = sucker_ratio > PLUMPNESS_FACTOR

# "Hey, nice t' meetcha."
if len(history) < WARINESS:
    #"Nice day, right?"
    if not set(history).intersection("RE"):
        print 'c'
    # "You sunnuvab..."
    else:
        print 't'

# "Hey, lemme show ya this game. Watch the queen..."
elif len(history) == WARINESS and seem_to_have_a_sucker:
    print 't'

# "Oh, s#!t, McWongski, I swear I din't know dat were you."
elif history[-len(THIEVES_CANT):] == THIEVES_CANT:

    # "Nobody does dat t' me!"
    if set(history[:-len(THIEVES_CANT)]).intersection("RE"):
        print 't'
    # "Hey, McWongski, I got dis job we could do..."
    else:
        print 'c'

# "Do you know who I am?!"
elif set(history).intersection("RE"):
    print 't'

# "Ah, ya almos' had da queen dat time. One more try, free, hey? G'head!"
elif seem_to_have_a_sucker:
    print 't'

# "Boy, you don't say much, do ya?"
else:
    print 'c'

```

Note that the `THIEVES_CANT` is essentially a handshake, though it will only emerge when playing against a cooperator. However, it avoids the parasite problem by checking for later crosses. Does quite well against the base roster.

# Answer
> 3 votes
### Hyperrational Wasp

Implemented in Java because I wasn't sure how complex the data structures were going to end up. If this is a problem for someone then I think I can port it to bash without too many problems because in the end it only really uses simple associative arrays.

**Note**: I've removed this from a package in line with the latest version of my patch to the scorer to handle Java. If you want to post a Java solution which uses inner classes then you'll have to patch the patch.

```
import java.util.*;

public class HyperrationalWasp
{
    // I'm avoiding enums so as not to clutter up the warriors directory with extra class files.
    private static String Clam = "c";
    private static String Rat = "t";
    private static String Ambiguous = "x";

    private static final String PROLOGUE = "ttc";

    private static int n;
    private static String myActions;
    private static String hisActions;

    private static String decideMove() {
        if (n < PROLOGUE.length()) return PROLOGUE.substring(n, n+1);

        // KISS - rather an easy special case here than a complex one later
        if (mirrorMatch()) return Clam;
        if (n == 99) return Rat; // This is rational rather than superrational

        int memory = estimateMemory();
        if (memory == 0) return Rat; // I don't think the opponent will punish me
        if (memory > 0) {
            Map<String, String> memoryModel = buildMemoryModel(memory);
            String myRecentHistory = myActions.substring(0, memory - 1);
            // I don't think the opponent will punish me.
            if (Clam.equals(memoryModel.get(Rat + myRecentHistory))) return Rat;
            // I think the opponent will defect whatever I do.
            if (Rat.equals(memoryModel.get(Clam + myRecentHistory))) return Rat;
            // Opponent will cooperate unless I defect.
            return Clam;
        }

        // Haven't figured out opponent's strategy. Tit for tat is a reasonable fallback.
        return hisAction(0);
    }

    private static int estimateMemory() {
        if (hisActions.substring(0, n-1).equals(hisActions.substring(1, n))) return 0;

        int memory = -1; // Superrational?
        for (int probe = 1; probe < 5; probe++) {
            Map<String, String> memoryModel = buildMemoryModel(probe);
            if (memoryModel.size() <= 1 || memoryModel.values().contains(Ambiguous)) {
                break;
            }
            memory = probe;
        }

        if (memory == -1 && isOpponentRandom()) return 0;

        return memory;
    }

    private static boolean isOpponentRandom() {
        // We only call this if the opponent appears not have have a small fixed memory,
        // so there's no point trying anything complicated. This is supposed to be a Wilson
        // confidence test, although my stats is so rusty there's a 50/50 chance that I've
        // got the two probabilities (null hypothesis of 0.5 and observed) the wrong way round.
        if (n < 10) return false; // Not enough data.
        double p = count(hisActions, Clam) / (double)n;
        double z = 2;
        double d = 1 + z*z/n;
        double e = p + z*z/(2*n);
        double var = z * Math.sqrt(p*(1-p)/n + z*z/(4*n*n));
        return (e - var) <= 0.5 * d && 0.5 * d <= (e + var);
    }

    private static Map<String, String> buildMemoryModel(int memory) {
        // It's reasonable to have a hard-coded prologue to probe opponent's behaviour,
        // and that shouldn't be taken into account.
        int skip = 0;
        if (n > 10) skip = n / 2;
        if (skip > 12) skip = 12;

        Map<String, String> memoryModel = buildMemoryModel(memory, skip);
        // If we're not getting any useful information after skipping prologue, take it into account.
        if (memoryModel.size() <= 1 && !memoryModel.values().contains(Ambiguous)) {
            memoryModel = buildMemoryModel(memory, 0);
        }
        return memoryModel;
    }

    private static Map<String, String> buildMemoryModel(int memory, int skip) {
        Map<String, String> model = new HashMap<String, String>();
        for (int off = 0; off < n - memory - 1 - skip; off++) {
            String result = hisAction(off);
            String hypotheticalCause = myActions.substring(off+1, off+1+memory);
            String prev = model.put(hypotheticalCause, result);
            if (prev != null && !prev.equals(result)) model.put(hypotheticalCause, Ambiguous);
        }
        return model;
    }

    private static boolean mirrorMatch() { return hisActions.matches("c*ctt"); }
    private static String myAction(int idx) { return myActions.substring(idx, idx+1).intern(); }
    private static String hisAction(int idx) { return hisActions.substring(idx, idx+1).intern(); }
    private static int count(String actions, String action) {
        int count = 0;
        for (int idx = 0; idx < actions.length(); ) {
            int off = actions.indexOf(action, idx);
            if (off < 0) break;
            count++;
            idx = off + 1;
        }
        return count;
    }

    public static void main(String[] args) {
        if (args.length == 0) {
            hisActions = myActions = "";
            n = 0;
        }
        else {
            n = args[0].length();
            myActions = args[0].replaceAll("[KR]", Clam).replaceAll("[SE]", Rat);
            hisActions = args[0].replaceAll("[KS]", Clam).replaceAll("[RE]", Rat);
        }

        System.out.println(decideMove());
    }

}

```

The changes I made to the scorer to run this are:

```
17a18
> import re
22a24
> GCC_PATH = 'gcc'                #path to c compiler
24c26
< JAVA_PATH = '/usr/bin/java'   #path to java vm
---
> JAVA_PATH = '/usr/bin/java'     #path to java vm
50,55c52,59
<         elif ext == '.java':
<             if subprocess.call([JAVAC_PATH, self.filename]) == 0:
<                 print 'compiled java: ' + self.filename
<                 classname = re.sub('\.java$', '', self.filename)
<                 classname = re.sub('/', '.', classname);
<                 return JAVA_PATH + " " + classname
---
>         elif ext == '.class':
>             # We assume further down in compilation and here that Java classes are in the default package
>             classname = re.sub('.*[/\\\\]', '', self.filename)
>             dir = self.filename[0:(len(self.filename)-len(classname))]
>             if (len(dir) > 0):
>                 dir = "-cp " + dir + " "
>             classname = re.sub('\\.class$', '', classname);
>             return JAVA_PATH + " " + dir + classname
196c200,201
<         if os.path.isdir(sys.argv[1]):
---
>         warriors_dir = re.sub('/$', '', sys.argv[1])
>         if os.path.isdir(warriors_dir):
198,200c203,211
<             for foo in os.listdir("./src/"): # build all c/c++ champs first.
<                 os.system(str("gcc -o ./warriors/" + os.path.splitext(os.path.split(foo)[1])[0] + " ./src/" + foo ))
<                 #print str("gcc -o ./warriors/" + os.path.splitext(os.path.split(foo)[1])[0] + " ./src/" + foo )
---
>             for foo in os.listdir("./src/"): # build all c/c++/java champs first.
>                 filename = os.path.split(foo)[-1]
>                 base, ext = os.path.splitext(filename)
>                 if (ext == '.c') or (ext == '.cpp'):
>                     subprocess.call(["gcc", "-o", warriors_dir + "/" + base, "./src/" + foo])
>                 elif (ext == '.java'):
>                     subprocess.call([JAVAC_PATH, "-d", warriors_dir, "./src/" + foo])
>                 else:
>                     print "No compiler registered for ", foo
202,203c213,214
<             print "Finding warriors in " + sys.argv[1]
<             players = [sys.argv[1]+exe for exe in os.listdir(sys.argv[1]) if os.access(sys.argv[1]+exe,os.X_OK)]
---
>             print "Finding warriors in " + warriors_dir
>             players = [warriors_dir+"/"+exe for exe in os.listdir(warriors_dir) if (os.access(warriors_dir+"/"+exe,os.X_OK) or os.path.splitext(exe)[-1] == '.class')]

```

Thanks to @rmckenzie for folding in my challenger function.

# Answer
> 3 votes
## Soft\_majo

Ah well, another one of the standard strategies, just to complete the line-up.

This one picks the move the opponent has made most; if equal it cooperates.

```
#include <stdio.h>
#include <string.h>

int main(int argc, char * argv[]) {
    int d = 0, i, l;

    if (argc == 1) {
        printf("c\n");
    } else {
        l = strlen(argv[1]);

        for (i = 0; i < l; i++)
            if (argv[1][i] == 'R' || argv[1][i] == 'E')
                d++;

        printf("%c\n", d > l/2 ? 't' : 'c');
    }
}

```

# Answer
> 3 votes
## Random sucker

This one will defect if the opponent defects too often (threshold), but will randomly try backstabbing every now and then.

Does fairly well against everyone except the Java and Lisp players (which I cannot get to run, due to neither Java nor Lisp on the test machine); most of the time at least.

```
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>

#define THRESHOLD 7
#define RAND 32

int main(int c, char * a []) {
    int r;
    char * x;
    int d = 0;

    srandom(time(0) + getpid());

    if (c == 1) {
        printf("c\n");
        return 0;
    }

    for (x = a[1]; *x; x++)
        if (*x == 'R' || *x == 'E') d++;

    if (d > THRESHOLD || random() % 1024 < RAND || strlen(a[1]) == 99)
        printf("t\n");
    else
        printf("c\n");

    return 0;
}

```

# Answer
> 2 votes
# BYGONES

```
#!/usr/bin/env python

"""
BYGONES, entry to 1P5 Iterated Prisoner's Dilemma, by Josh Caswell

Cooperates at first, plays as Tit for Tat for `bygones * 2` rounds, then checks
history: if there's too much ratting, get mad and defect; too much
suckering, feel bad and cooperate.
"""

bygones = 5

import sys

# React to strangers with trust.
try:
    history = sys.argv[1]
except IndexError:
    print 'c'
    sys.exit(0)

replies = { 'K' : 'c', 'S' : 'c',
            'R' : 't', 'E' : 't' }

# Reply in kind.
if len(history) < bygones * 2:
    print replies[history[0]]
    sys.exit(0)

# Reflect on past interactions.
faithful_count = history.count('K')
sucker_count = history.count('S')
rat_count = history.count('R')

# Reprisal.
if rat_count > faithful_count + bygones:
    # Screw you!
    print 't'
    sys.exit(0)

# Reparation.
if sucker_count > faithful_count + bygones:
    # Geez, I've really been mean.
    print 'c'
    sys.exit(0)

# Resolve to be more forgiving.
two_tats = ("RR", "RE", "ER", "EE")
print 't' if history[:2] in two_tats else 'c'

```

Haven't worked out the best value for `bygones` yet. I don't expect this to be a *winning* strategy, but I'm interested in the performance of a strategy something like what I think is "good" in real life. A future revision may include checking the number of mutual defections, too.

# Answer
> 2 votes
## Help Vampire

```
#!/usr/bin/env python

"""
Help Vampire, entry to 1P5 Iterated Prisoner's Dilemma,
by Josh Caswell.

1. Appear Cooperative 2. Acknowledge Chastisement
3. Act contritely 4. Abuse charity 5. Continual affliction
"""

import sys
from os import urandom

LEN_ABASHMENT = 5

try:
    history = sys.argv[1]
except IndexError:
    print 'c'    # Appear cooperative
    sys.exit(0)

# Acknowledge chastisement
if history[0] in "RE":
    print 'c'
# Act contritely
elif set(history[:LEN_ABASHMENT]).intersection(set("RE")):
    print 'c'
# Abuse charity
elif history[0] == 'S':
    print 't'
# Continual affliction
else:
    print 't' if ord(urandom(1)) % 3 else 'c'

```

Has an amusingly asymmetrical result when pitted against itself. If only this solution could be applied in real life.

# Answer
> 2 votes
## Druid

```
#!/usr/bin/env python

"""
Druid, by Josh Caswell

Druids are slow to anger, but do not forget.
"""

import sys
from itertools import groupby

FORBEARANCE = 7
TOLERANCE = FORBEARANCE + 5

try:
    history = sys.argv[1]
except IndexError:
    history = ""

# If there's been too much defection overall, defect
if (history.count('E') > TOLERANCE) or (history.count('R') > TOLERANCE):
    print 't'
# Too much consecutively, defect
elif max([0] + [len(list(g)) for k,g in     # The 0 prevents dying on []
                groupby(history) if k in 'ER']) > FORBEARANCE:
    print 't'
# Otherwise, be nice
else:
    print 'c'

```

Does reasonably well against the base roster.

# Answer
> 2 votes
## Little Schemer

```
#!/usr/bin/env python

"""
The Little Schemer, by Josh Caswell

No relation to the book. Keeps opponent's trust > suspicion
by at least 10%, trying to ride the line.
"""

from __future__ import division
import sys
from os import urandom

out = sys.stderr.write

def randrange(n):
    if n == 0:
        return 0
    else:
        return ord(urandom(1)) % n

try:
    history = sys.argv[1]
except IndexError:
    print 'c'
    sys.exit(0)

R_count = history.count('R')
S_count = history.count('S')
K_count = history.count('K')
E_count = history.count('E')

# Suspicion is _S_ and E because it's _opponent's_ suspicion
suspicion = (S_count + E_count) / len(history)
# Likewise trust
trust = (K_count + R_count) / len(history)

if suspicion > trust:
    print 'c'
else:
    projected_suspicion = (1 + S_count + E_count) / (len(history) + 1)
    projected_trust = (1 + K_count + R_count) / (len(history) + 1)

    leeway = projected_trust - projected_suspicion
    odds = int(divmod(leeway, 0.1)[0])

    print 't' if randrange(odds) else 'c'

```

Does poorly against the base set, but quite well against its target. Obviously, not written in Scheme.

# Answer
> 2 votes
## Simpleton

```
#!/usr/bin/env python

"""
Simpleton, by Josh Caswell

Quick to anger, quick to forget, unable to take advantage of opportunity.
"""

import sys
from os import urandom

WHIMSY = 17

try:
    history = sys.argv[1]
except IndexError:
    if not ord(urandom(1)) % WHIMSY:
        print 't'
    else:
        print 'c'
    sys.exit(0)

if history[0] in "RE":
    print 't'
elif not ord(urandom(1)) % WHIMSY:
    print 't'
else:
    print 'c'

```

Does okay against the base roster.

# Answer
> 1 votes
# Tit for Two Tats

### another old favorite

```
#!/usr/bin/env python

"""
Tit For Two Tats, entry to 1P5 Iterated Prisoner's Dilemma,
    by Josh Caswell (not an original idea).

Cooperates unless opponent has defected in the last two rounds.
"""

import sys
try:
    history = sys.argv[1]
except IndexError:
    history = ""

two_tats = ("RR", "RE", "ER", "EE")

if len(history) < 2:
    print 'c'
else:
    print 't' if history[:2] in two_tats else 'c'

```

---
Tags: 1p5, king-of-the-hill
---


title: File access redirection

text:
# Question
Title: File access redirection
This one ought to be a little more of a challenge than your normal "compute these numbers" or "print this sequence of text" puzzles:

Write a program that launches another program and when that other program tries to access a certain file the program causes it to open a different file.

Example:

The program launches Notepad.
Notepad attempts to open "orange.txt"
The program detects it and makes notepad open "green.txt" instead.

Rules:
WinAPI is allowed, but your code will stand out better if you can get this some other way.
You can use any language, but it must be able to run on either Windows or Linux

# Answer
> 6 votes
## C - 146

This is based on an answer to the StackOverflow question "how could I intercept linux sys calls?".

```
#define r(s)int s(int p,int f,int m)
#define c(s)r(s){return((r((*)))dlsym(-1,#s))(strcmp(p,getenv("OLD"))?p:getenv("NEW"),f,m);}
c(open)c(open64)

```

This has been tested on Linux/x86, and is unlikely to be portable.

### Usage:

```
$ echo orange > orange.txt
$ echo green > green.txt
$ gcc -fPIC -shared -ldl intercept-open.c -o intercept-open.so
$ cat orange.txt
orange
$ LD_PRELOAD="./intercept-open.so" OLD="orange.txt" NEW="green.txt" cat orange.txt
green

```

This works with some programs (e.g. `cat`, `less`, `wc`, `vim`) but not others (e.g. `nano`, `gedit`).

# Answer
> 7 votes
## gdb, 108 chars

```
star
b open if !(int)strcmp(((char**)$esp)[1],"orange.txt")
comm
set((char**)$esp)[1]="green.txt"
c
end
c
q

```

Save as the file `redirect` and run like this:

```
gdb -x redirect <program you want to redirect>

```

Works on x86 (linux at least, and probably Windows/Mac also). Here's what the lines do:

`star` = `start` gets to the beginning of main (needed so `open` is defined for the next step).

`b open if...` = break if we're calling `open` on `orange.txt`

`comm` = `command` the code up to the next `end` is executed when the breakpoint fires.

`set ((char*))...` = replace the `open` argument with `green.txt`

`c`=`continue`

`q`=`quit`

---
Tags: code-challenge
---


title: Circle Through Three Points

text:
# Question
Title: Circle Through Three Points
Given the Cartesian coordinates of three points on a plane, find the equation of the circle through them all. The three points will not be on a straight line.

Each line of input to your program will contain the `x` and `y` coordinates of three points, in the order `A(x),A(y),B(x),B(y),C(x),C(y)`. These coordinates will be real numbers less than 1,000,000 separated from each other by space.

The solution is to be printed as an equation of the form `(x-h)^2 + (y-k)^2 = r^2`. Values for `h`, `k`, `r` are to be printed with three digits after the decimal point. Plus and minus signs in the equations should be changed as needed to avoid multiple signs before a number.

```
Sample Inputs

7.0 -5.0 -1.0 1.0 0.0 -6.0
1.0 7.0 8.0 6.0 7.0 -2.0

Sample Outputs

(x - 3.000)^2 + (y + 2.000)^2 = 5.000^2
(x - 3.921)^2 + (y - 2.447)^2 = 5.409^2

```

# Answer
## Python, 176 189 chars

```
import sys,re
for s in sys.stdin:x,y,z=eval(re.sub(r'(\S+) (\S+)',r'\1+\2j,',s));w=z-x;w/=y-x;c=(x-y)*(w-abs(w)**2)/2j/w.imag-x;print'(x%+.3f)^2+(y%+.3f)^2=%.3f^2'%(c.real,c.imag,abs(c+x))

```

Does all its work in the complex plane. I go the math from the bottom of this page. `-c` is the center of the circle.
> 6 votes

# Answer
## Ruby, 192 characters

```
$<.map{|l|a,b,c,d,e,f=l.split.map &:to_f
n=(f-d)/(e-c)
puts"(x%+.3f)^2+(y%+.3f)^2=%.3f^2"%[x=-(n*(a+c)+(n*(b-f)-(c+e))*m=(d-b)/(c-a))/2/n-=m,y=-(x+(a+c)/2)/m-(b+d)/2,((a+x)**2+(b+y)**2)**0.5]}

```

Usage examples:

```
$ echo "7.0 -5.0 -1.0 1.0 0.0 -6.0
1.0 7.0 8.0 6.0 7.0 -2.0" | ruby circle.rb
(x-3.000)^2+(y+2.000)^2=5.000^2
(x-3.921)^2+(y-2.447)^2=5.409^2

```
> 2 votes

# Answer
### C# - 490

```
using System;class C{static void Main(){Func<string,double>p=s=>double.Parse(s);Func<double,string>t=s=>(s<0?"+ ":"- ")+Math.Abs(s).ToString("F3");foreach(var l in System.IO.File.ReadAllLines("i")){var v=l.Split();double a=p(v[0]),b=p(v[1]),c=p(v[2]),d=p(v[3]),e=p(v[4]),f=p(v[5]),m=(d-b)/(c-a),n=(f-d)/(e-c),x=(m*n*(b-f)+n*(a+c)-m*(c+e))/(2*(n-m)),y=-(x-(a+c)/2)/m+(b+d)/2,r=Math.Sqrt((x-a)*(x-a)+(y-b)*(y-b));Console.WriteLine("(x "+t(x)+")^2+(y "+t(y)+")^2 = "+r.ToString("F3")+"^2");}}}

```

This finds the 2 lines between AB and BC. Then it finds where the bisects of those 2 lines intersect. (Which I just noticed is what @PeterTaylor mentioned in his comment to @PeterOfTheCorn.)
> 2 votes

# Answer
## Javascript (299)

The only way that I could think of solving this was algebraically solving three equations for three unknowns to find h, k, and r.

```
p=prompt().split(' ');a=p[0],b=p[1],c=p[2],d=p[3],e=p[4],f=p[5];h=((a*a+b*b)*(f-d)+(c*c+d*d)*(b-f)+(e*e+f*f)*(d-b))/(a*(f-d)+c*(b-f)+e*(d-b))/2;k=((a*a+b*b)*(e-c)+(c*c+d*d)*(a-e)+(e*e+f*f)*(c-a))/(b*(e-c)+d*(a-e)+f*(c-a))/2;r=Math.sqrt((a-h)*(a-h)+(b-k)*(b-k));alert("(x-"+h+")²+(y-"+k+")²="+r+"²");

```

Example I/O:

`7.0 -5.0 -1.0 1.0 0.0 -6.0` --\> `(x-3)²+(y--2)²=5²`

`1.0 7.0 8.0 6.0 7.0 -2.0` --\> `(x-3.9210526315789473)²+(y-2.4473684210526314)² =5.409159155551175²`

The only bug that I see is that if h or k is negative, it outputs `--` instead of `+`.
> 0 votes

---
Tags: code-golf, math
---


# Question
Title: Data theft via remote desktop connection
A software vendor friend of mine wants to clamp down the development environment by limiting access to the software's source code to only Remote Desktop access, disallowing any digital communication including clipboard, printer, network shares, and internet access from that environment.

The reasoning is that they are contractually obligated to provide a company-standard-issue development environment to an overseas partner and there is a concern of theft.

I want to convince them that this is a futile effort and vain burden on good developers since the otherwise unsupervised access to the source code will provide ample opportunity to steal the data. No matter how many firewall rules and group policies are in place, one channel remains that cannot be removed - the screen.

Assuming the development environment has Visual Studio 2010, data compression software, and other common development environment tools, what is the slickest way to use the Remote Desktop screen to steal the data? Keep in mind any limitations of the screen refresh rate.

Candidate approach: a monochrome bitmap of the screen can hold over 200KB of an archive of such source code. Without error correction, that's just over 500 screenshots of monochrome data for 100MB of compressed source code. The data must be encoded, decoded, and I'm entirely too lazy to save 500 screenshots into paint. Existing free software can be involved, but not installed on the environment.

Other ideas? Implementations?

# Answer
Use FRAPS to capture video from your local machine. Then you can flash stuff up on the remote desktop at up to the frame rate and it will all get recorded to a local video file.

I don't see a way to sync to exactly to the frame rate, so you'll need some error detection to make sure you're not getting data mid-draw. Here's a simple scheme using text and a python script:

```
framerate = 30  # fps of viewer
numlines = 24   # lines of text you can see at once
import sys,time,md5,base64
lineno = 0
while 1:
  lines = 'chunk starting at line %d\n' % lineno
  for i in xrange(numlines - 2):
    lines += sys.stdin.readline()
    lineno += 1
  print 'md5:', base64.encodestring(md5.new(lines).digest()),
  print lines
  time.sleep(1.0/framerate)

```

Run this script in the RemoteDesktop window and pipe in the text you wish to capture. When it is done, OCR each frame of your FRAPS output (that's the hard part, I'm not sure what you'd use for that). Throw away any duplicate frames and frames where the md5 isn't right.

You probably want to base64 encode your input, as OCR doesn't do well with nonprinting characters like tabs and spaces.
> 5 votes

---
Tags: code-challenge
---


title: The Prime Grid Game

text:
# Question
Title: The Prime Grid Game
I had fun solving this, so I offer this golf challenge.

The objective of this **golf** is to find the largest prime number that can be constructed using the given instructions.

You should accept 3x3 grid of single digits as input. (It's up to you how you want to do that, but specify that in your program.)

You can move along the grid orthogonally (left, right, up or down), and as you move, you keep appending the digits you walk across.

E.g.

```
1 2 3
3 5 6
1 8 9

```

Say we start at `1`, we can form the number 1236589 but **cannot** form 15.

You have to evaluate every starting position.

If a prime cannot be found, print `-1`, else print the prime itself.

Shortest code wins, make sure it runs within 10 secs.

Have Fun!

Edit: Use one position exactly once, in the entire number.

Here's a test case

**Input:**

```
1 2 3
4 5 6
7 8 9

```

**Output:** 69854123

# Answer
## Haskell, 239 characters

```
p=2:q[3..]
q=filter(#p)
n#(x:y)=n==x||n`mod`x/=0&&(n`div`x<x||n#y)
(n§m)q=n:maybe[](\i->[q-4,q-1,q+1,q+4]>>=(n*10+i)§filter(/=(q,i))m)(lookup q m)
i=[0,1,2,4,5,6,8,9,10]
main=getLine>>=print.maximum.(-1:).q.(i>>=).(0§).zip i.map read.words

```

Input is given as a single line of nine numbers:

```
$> echo 1 2 3  3 5 6  1 8 9 | runhaskell 2485-PrimeGrid.hs
81356321
$> echo 1 2 3  4 5 6  7 8 9 | runhaskell 2485-PrimeGrid.hs
69854123
$> echo 1 1 1  1 1 1  1 1 1 | runhaskell 2485-PrimeGrid.hs
11
$> echo 2 2 2  2 2 2  2 2 2 | runhaskell 2485-PrimeGrid.hs
2
$> echo 4 4 4  4 4 4  4 4 4 | runhaskell 2485-PrimeGrid.hs
-1

```
> 4 votes

# Answer
## Python, 286 274 chars

```
I=lambda:raw_input().split()
m=['']
G=m*4+I()+m+I()+m+I()+m*4
def B(s,p):
 d=G[p]
 if''==d:return-1
 G[p]='';s+=d;n=int(s)
 r=max(n if n>1and all(n%i for i in range(2,n**.5+1))else-1,B(s,p-4),B(s,p+4),B(s,p-1),B(s,p+1))
 G[p]=d;return r
print max(B('',i)for i in range(15))

```

This does give a deprecation warning for the float argument to `range`. Ignore it, or spend 5 more chars to wrap `int()` around it.
> 3 votes

---
Tags: code-golf, number, primes, grid
---


title: Respawning Factorial

text:
# Question
Title: Respawning Factorial
Write a program that does one step of the computation of factorial, then, generate (quine) a new program, and performs the rest of the process in the new program The seed and spawned programs will have a variable n for the factorial to be computed and m for the accumulator.

I don't care if you use scripted or compiled language. You can use the cheat of "reading the source file". You MUST create a new file and run the new file to qualify: no self-modifying code or using code loaded in memory, but spawning with `data:` url in JS is allowed.

Here is an example in Java: https://gist.github.com/968033

Shortest code wins.

# Answer
> 4 votes
# Perl, 95

```
$m=1;$n=12||die$m;@ARGV=$0;$_=<>;$m*=$n--;s/\|/;\$m=$m;\$n=$n|/;open _,">$0";print _;exec$^X,$0

```

The program really has to be on a single line, and overwrites itself at each iteration.

# Answer
> 0 votes
# Javascript (163)

```
g=document.location;if(s=g.search.split(",")[1]){
n=s.split(":");i=n[1];n=n[0];i*=--n;
n==1?alert(i):g.search="?a=,"+n+":"+i}
else{n=prompt();g.search="?a=,"+n+":"+n}

```

This uses the querystring to pass values and refreshes the page.

# Answer
> 0 votes
# Python (189)

It's not very short but it does take its argument on the command line.

```
n,m=0,1
from sys import*
a,f=argv,file
_,n=a[0],len(a)>1and n<1and int(a[1])or n
if n>1:x=f(_).readlines();x[0]='n,m=%s\n'%`n-1,m*n`;f(_,'w').write(''.join(x));exec f(_).read()
else:print m

```

---
Tags: code-golf
---


title: 1P5: Word Changer

text:
# Question
Title: 1P5: Word Changer
*This was written as part of the First Periodic Premier Programming Puzzle Push.*

### The Game

A starting and ending word of the same length are provided. The objective of the game is to change one letter in the starting word to form a different valid word, repeating this step until the ending word is reached, using the fewest amount of steps. For example, given the words TREE and FLED, the output would be:

```
TREE
FREE
FLEE
FLED
2

```

### Specifications

* The Wikipedia articles for the OWL or SOWPODS might be a useful starting point as far as word lists go.
* The program should support two ways of selecting the start and end words:
    1. Specified by the user via command-line, stdin, or whatever is suitable for your language of choice (just mention what you're doing).
    2. Selecting 2 words at random from the file.
* The starting and ending words, as well as all interim words should be the same length.
* Each step should be printed out on its line.
* The final line of your output should be the number of interim steps that were required to get between the starting and ending words.
* If a match cannot be found between the starting and ending words, the output should consist of 3 lines: the beginning word, the ending word, and the word OY.
* Include the Big O Notation for your solution in your answer
* Please include 10 unique starting and ending words pairs (with their output, of course) to show the steps your program produces. (To save space, while your program should output these on individual lines, you can consolidate these into a single line for posting, replacing new lines with spaces and a comma between each run.

### Goals / Winning Criteria

* The fastest/best Big O solution producing the shortest interim steps after one week will win.
* If a tie results from the Big O criteria, the shortest code will win.
* If there is still a tie, the first solution to reach its fastest and shortest revision will win.

### Tests / Sample Output

```
DIVE
DIME
DAME
NAME
2

PEACE
PLACE
PLATE
SLATE
2

HOUSE
HORSE
GORSE
GORGE
2

POLE
POSE
POST
PAST
FAST
3

```

### Validation

I am working on a script that can be used to validate the output.

It will:

1. Ensure that each word is valid.
2. Ensure that each word is exactly 1 letter different from the previous word.

It will not:

1. Check that the shortest number of steps were used.

Once I've gotten that written, I will of course update this post. (:

# Answer
> 9 votes
Since length is listed as a criterion, here's the golfed version at 1681 characters (could probably still be improved by 10%):

```
import java.io.*;import java.util.*;public class W{public static void main(String[]
a)throws Exception{int n=a.length<1?5:a[0].length(),p,q;String f,t,l;S w=new S();Scanner
s=new Scanner(new
File("sowpods"));while(s.hasNext()){f=s.next();if(f.length()==n)w.add(f);}if(a.length<1){String[]x=w.toArray(new
String[0]);Random
r=new Random();q=x.length;p=r.nextInt(q);q=r.nextInt(q-1);f=x[p];t=x[p>q?q:q+1];}else{f=a[0];t=a[1];}H<S>
A=new H(),B=new H(),C=new H();for(String W:w){A.put(W,new
S());for(p=0;p<n;p++){char[]c=W.toCharArray();c[p]='.';l=new
String(c);A.get(W).add(l);S z=B.get(l);if(z==null)B.put(l,z=new
S());z.add(W);}}for(String W:A.keySet()){C.put(W,w=new S());for(String
L:A.get(W))for(String b:B.get(L))if(b!=W)w.add(b);}N m,o,ñ;H<N> N=new H();N.put(f,m=new
N(f,t));N.put(t,o=new N(t,t));m.k=0;N[]H=new
N[3];H[0]=m;p=H[0].h;while(0<1){if(H[0]==null){if(H[1]==H[2])break;H[0]=H[1];H[1]=H[2];H[2]=null;p++;continue;}if(p>=o.k-1)break;m=H[0];H[0]=m.x();if(H[0]==m)H[0]=null;for(String
v:C.get(m.s)){ñ=N.get(v);if(ñ==null)N.put(v,ñ=new N(v,t));if(m.k+1<ñ.k){if(ñ.k<ñ.I){q=ñ.k+ñ.h-p;N
Ñ=ñ.x();if(H[q]==ñ)H[q]=Ñ==ñ?null:Ñ;}ñ.b=m;ñ.k=m.k+1;q=ñ.k+ñ.h-p;if(H[q]==null)H[q]=ñ;else{ñ.n=H[q];ñ.p=ñ.n.p;ñ.n.p=ñ.p.n=ñ;}}}}if(o.b==null)System.out.println(f+"\n"+t+"\nOY");else{String[]P=new
String[o.k+2];P[o.k+1]=o.k-1+"";m=o;for(q=m.k;q>=0;q--){P[q]=m.s;m=m.b;}for(String
W:P)System.out.println(W);}}}class N{String s;int k,h,I=(1<<30)-1;N b,p,n;N(String S,String
d){s=S;for(k=0;k<d.length();k++)if(d.charAt(k)!=S.charAt(k))h++;k=I;p=n=this;}N
x(){N r=n;n.p=p;p.n=n;n=p=this;return r;}}class S extends HashSet<String>{}class H<V>extends
HashMap<String,V>{}

```

The ungolfed version, which uses package names and methods and doesn't give warnings or extend classes just to alias them, is:

```
package com.akshor.pjt33;

import java.io.*;
import java.util.*;

// WordLadder partially golfed and with reduced dependencies
//
// Variables used in complexity analysis:
// n is the word length
// V is the number of words (vertex count of the graph)
// E is the number of edges
// hash is the cost of a hash insert / lookup - I will assume it's constant, but without completely brushing it under the carpet
public class WordLadder2
{
    private Map<String, Set<String>> wordsToWords = new HashMap<String, Set<String>>();

    // Initialisation cost: O(V * n * (n + hash) + E * hash)
    private WordLadder2(Set<String> words)
    {
        Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
        Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();

        // Cost: O(Vn * (n + hash))
        for (String word : words)
        {
            // Cost: O(n*(n + hash))
            for (int i = 0; i < word.length(); i++)
            {
                // Cost: O(n + hash)
                char[] ch = word.toCharArray();
                ch[i] = '.';
                String link = new String(ch).intern();
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
            }
        }

        // Cost: O(V * n * hash + E * hash)
        for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
            String src = from.getKey();
            wordsToWords.put(src, new HashSet<String>());
            for (String link : from.getValue()) {
                Set<String> to = linksToWords.get(link);
                for (String snk : to) {
                    // Note: equality test is safe here. Cost is O(hash)
                    if (snk != src) add(wordsToWords, src, snk);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException
    {
        // Cost: O(filelength + num_words * hash)
        Map<Integer, Set<String>> wordsByLength = new HashMap<Integer, Set<String>>();
        BufferedReader br = new BufferedReader(new FileReader("sowpods"), 8192);
        String line;
        while ((line = br.readLine()) != null) add(wordsByLength, line.length(), line);

        if (args.length == 2) {
            String from = args[0].toUpperCase();
            String to = args[1].toUpperCase();
            new WordLadder2(wordsByLength.get(from.length())).findPath(from, to);
        }
        else {
            // 5-letter words are the most interesting.
            String[] _5 = wordsByLength.get(5).toArray(new String[0]);
            Random rnd = new Random();
            int f = rnd.nextInt(_5.length), g = rnd.nextInt(_5.length - 1);
            if (g >= f) g++;
            new WordLadder2(wordsByLength.get(5)).findPath(_5[f], _5[g]);
        }
    }

    // O(E * hash)
    private void findPath(String start, String dest) {
        Node startNode = new Node(start, dest);
        startNode.cost = 0; startNode.backpointer = startNode;

        Node endNode = new Node(dest, dest);

        // Node lookup
        Map<String, Node> nodes = new HashMap<String, Node>();
        nodes.put(start, startNode);
        nodes.put(dest, endNode);

        // Heap
        Node[] heap = new Node[3];
        heap[0] = startNode;
        int base = heap[0].heuristic;

        // O(E * hash)
        while (true) {
            if (heap[0] == null) {
                if (heap[1] == heap[2]) break;
                heap[0] = heap[1]; heap[1] = heap[2]; heap[2] = null; base++;
                continue;
            }

            // If the lowest cost isn't at least 1 less than the current cost for the destination,
            // it can't improve the best path to the destination.
            if (base >= endNode.cost - 1) break;

            // Get the cheapest node from the heap.
            Node v0 = heap[0];
            heap[0] = v0.remove();
            if (heap[0] == v0) heap[0] = null;

            // Relax the edges from v0.
            int g_v0 = v0.cost;
            // O(hash * #neighbours)
            for (String v1Str : wordsToWords.get(v0.key))
            {
                Node v1 = nodes.get(v1Str);
                if (v1 == null) {
                    v1 = new Node(v1Str, dest);
                    nodes.put(v1Str, v1);
                }

                // If it's an improvement, use it.
                if (g_v0 + 1 < v1.cost)
                {
                    // Update the heap.
                    if (v1.cost < Node.INFINITY)
                    {
                        int bucket = v1.cost + v1.heuristic - base;
                        Node t = v1.remove();
                        if (heap[bucket] == v1) heap[bucket] = t == v1 ? null : t;
                    }

                    // Next update the backpointer and the costs map.
                    v1.backpointer = v0;
                    v1.cost = g_v0 + 1;

                    int bucket = v1.cost + v1.heuristic - base;
                    if (heap[bucket] == null) {
                        heap[bucket] = v1;
                    }
                    else {
                        v1.next = heap[bucket];
                        v1.prev = v1.next.prev;
                        v1.next.prev = v1.prev.next = v1;
                    }
                }
            }
        }

        if (endNode.backpointer == null) {
            System.out.println(start);
            System.out.println(dest);
            System.out.println("OY");
        }
        else {
            String[] path = new String[endNode.cost + 1];
            Node t = endNode;
            for (int i = t.cost; i >= 0; i--) {
                path[i] = t.key;
                t = t.backpointer;
            }
            for (String str : path) System.out.println(str);
            System.out.println(path.length - 2);
        }
    }

    private static <K, V> void add(Map<K, Set<V>> map, K key, V value) {
        Set<V> vals = map.get(key);
        if (vals == null) map.put(key, vals = new HashSet<V>());
        vals.add(value);
    }

    private static class Node
    {
        public static int INFINITY = Integer.MAX_VALUE >> 1;

        public String key;
        public int cost;
        public int heuristic;
        public Node backpointer;

        public Node prev = this;
        public Node next = this;

        public Node(String key, String dest) {
            this.key = key;
            cost = INFINITY;
            for (int i = 0; i < dest.length(); i++) if (dest.charAt(i) != key.charAt(i)) heuristic++;
        }

        public Node remove() {
            Node rv = next;
            next.prev = prev;
            prev.next = next;
            next = prev = this;
            return rv;
        }
    }
}

```

As you can see, the running cost analysis is `O(filelength + num_words * hash + V * n * (n + hash) + E * hash)`. If you'll accept my assumption that a hash table insertion/lookup is constant time, that's `O(filelength + V n^2 + E)`. The particular statistics of the graphs in SOWPODS mean that `O(V n^2)` really dominates `O(E)` for most `n`.

Sample outputs:

IDOLA, IDOLS, IDYLS, ODYLS, ODALS, OVALS, OVELS, OVENS, EVENS, ETENS, STENS, SKENS, SKINS, SPINS, SPINE, 13

WICCA, PROSY, OY

BRINY, BRINS, TRINS, TAINS, TARNS, YARNS, YAWNS, YAWPS, YAPPS, 7

GALES, GASES, GASTS, GESTS, GESTE, GESSE, DESSE, 5

SURES, DURES, DUNES, DINES, DINGS, DINGY, 4

LICHT, LIGHT, BIGHT, BIGOT, BIGOS, BIROS, GIROS, GIRNS, GURNS, GUANS, GUANA, RUANA, 10

SARGE, SERGE, SERRE, SERRS, SEERS, DEERS, DYERS, OYERS, OVERS, OVELS, OVALS, ODALS, ODYLS, IDYLS, 12

KEIRS, SEIRS, SEERS, BEERS, BRERS, BRERE, BREME, CREME, CREPE, 7

This is one of the 6 pairs with the longest shortest path:

GAINEST, FAINEST, FAIREST, SAIREST, SAIDEST, SADDEST, MADDEST, MIDDEST, MILDEST, WILDEST, WILIEST, WALIEST, WANIEST, CANIEST, CANTEST, CONTEST, CONFEST, CONFESS, CONFERS, CONKERS, COOKERS, COOPERS, COPPERS, POPPERS, POPPETS, POPPITS, POPPIES, POPSIES, MOPSIES, MOUSIES, MOUSSES, POUSSES, PLUSSES, PLISSES, PRISSES, PRESSES, PREASES, UREASES, UNEASES, UNCASES, UNCASED, UNBASED, UNBATED, UNMATED, UNMETED, UNMEWED, ENMEWED, ENDEWED, INDEWED, INDEXED, INDEXES, INDENES, INDENTS, INCENTS, INCESTS, INFESTS, INFECTS, INJECTS, 56

And one of the worst-case soluble 8-letter pairs:

ENROBING, UNROBING, UNROPING, UNCOPING, UNCAPING, UNCAGING, ENCAGING, ENRAGING, ENRACING, ENLACING, UNLACING, UNLAYING, UPLAYING, SPLAYING, SPRAYING, STRAYING, STROYING, STROKING, STOOKING, STOOPING, STOMPING, STUMPING, SLUMPING, CLUMPING, CRUMPING, CRIMPING, CRISPING, CRISPINS, CRISPENS, CRISPERS, CRIMPERS, CRAMPERS, CLAMPERS, CLASPERS, CLASHERS, SLASHERS, SLATHERS, SLITHERS, SMITHERS, SMOTHERS, SOOTHERS, SOUTHERS, MOUTHERS, MOUCHERS, COUCHERS, COACHERS, POACHERS, POTCHERS, PUTCHERS, PUNCHERS, LUNCHERS, LYNCHERS, LYNCHETS, LINCHETS, 52

Now that I think I've got all the requirements of the question out of the way, my discussion.

For a CompSci the question obviously reduces to shortest path in a graph G whose vertices are words and whose edges connect words differing in one letter. Generating the graph efficiently isn't trivial - I actually have an idea I need to revisit to reduce the complexity to O(V n hash + E). The way I do it involves creating a graph which inserts extra vertices (corresponding to words with one wildcard character) and is homeomorphic to the graph in question. I did consider using that graph rather than reducing to G - and I suppose that from a golfing point of view I should have done - on the basis that a wildcard node with more than 3 edges reduces the number of edges in the graph, and the standard worst case running time of shortest path algorithms is `O(V heap-op + E)`.

However, the first thing I did was to run some analyses of the graphs G for different word lengths, and I discovered that they're extremely sparse for words of 5 or more letters. The 5-letter graph has 12478 vertices and 40759 edges; adding link nodes makes the graph worse. By the time you're up to 8 letters there are fewer edges than nodes, and 3/7 of the words are "aloof". So I rejected that optimisation idea as not really helpful.

The idea which did prove helpful was to examine the heap. I can honestly say that I've implemented some moderately exotic heaps in the past, but none as exotic as this. I use A-star (since C provides no benefit given the heap I'm using) with the obvious heuristic of number of letters different from the target, and a bit of analysis shows that at any time there are no more than 3 different priorities in the heap. When I pop a node whose priority is (cost + heuristic) and look at its neighbours, there are three cases I'm considering: 1) neighbour's cost is cost+1; neighbour's heuristic is heuristic-1 (because the letter it changes becomes "correct"); 2) cost+1 and heuristic+0 (because the letter it changes goes from "wrong" to "still wrong"; 3) cost+1 and heuristic+1 (because the letter it changes goes from "correct" to "wrong"). So if I relax the neighbour I'm going to insert it at the same priority, priority+1, or priority+2. As a result I can use a 3-element array of linked lists for the heap.

I should add a note about my assumption that hash lookups are constant. Very well, you may say, but what about hash computations? The answer is that I'm amortising them away: `java.lang.String` caches its `hashCode()`, so the total time spent computing hashes is `O(V n^2)` (in generating the graph).

There is another change which affects the complexity, but the question of whether it is an optimisation or not depends on your assumptions about statistics. (IMO putting "the best Big O solution" as a criterion is a mistake because there isn't a best complexity, for a simple reason: there isn't a single variable). This change affects the graph generation step. In the code above, it's:

```
        Map<String, Set<String>> wordsToLinks = new HashMap<String, Set<String>>();
        Map<String, Set<String>> linksToWords = new HashMap<String, Set<String>>();

        // Cost: O(Vn * (n + hash))
        for (String word : words)
        {
            // Cost: O(n*(n + hash))
            for (int i = 0; i < word.length(); i++)
            {
                // Cost: O(n + hash)
                char[] ch = word.toCharArray();
                ch[i] = '.';
                String link = new String(ch).intern();
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
            }
        }

        // Cost: O(V * n * hash + E * hash)
        for (Map.Entry<String, Set<String>> from : wordsToLinks.entrySet()) {
            String src = from.getKey();
            wordsToWords.put(src, new HashSet<String>());
            for (String link : from.getValue()) {
                Set<String> to = linksToWords.get(link);
                for (String snk : to) {
                    // Note: equality test is safe here. Cost is O(hash)
                    if (snk != src) add(wordsToWords, src, snk);
                }
            }
        }

```

That's `O(V * n * (n + hash) + E * hash)`. But the `O(V * n^2)` part comes from generating a new n-character string for each link and then computing its hashcode. This can be avoided with a helper class:

```
    private static class Link
    {
        private String str;
        private int hash;
        private int missingIdx;

        public Link(String str, int hash, int missingIdx) {
            this.str = str;
            this.hash = hash;
            this.missingIdx = missingIdx;
        }

        @Override
        public int hashCode() { return hash; }

        @Override
        public boolean equals(Object obj) {
            Link l = (Link)obj; // Unsafe, but I know the contexts where I'm using this class...
            if (this == l) return true; // Essential
            if (hash != l.hash || missingIdx != l.missingIdx) return false;
            for (int i = 0; i < str.length(); i++) {
                if (i != missingIdx && str.charAt(i) != l.str.charAt(i)) return false;
            }
            return true;
        }
    }

```

Then the first half of the graph generation becomes

```
        Map<String, Set<Link>> wordsToLinks = new HashMap<String, Set<Link>>();
        Map<Link, Set<String>> linksToWords = new HashMap<Link, Set<String>>();

        // Cost: O(V * n * hash)
        for (String word : words)
        {
            // apidoc: The hash code for a String object is computed as
            // s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
            // Cost: O(n * hash)
            int hashCode = word.hashCode();
            int pow = 1;
            for (int j = word.length() - 1; j >= 0; j--) {
                Link link = new Link(word, hashCode - word.charAt(j) * pow, j);
                add(wordsToLinks, word, link);
                add(linksToWords, link, word);
                pow *= 31;
            }
        }

```

By using the structure of the hashcode we can generate the links in `O(V * n)`. However, this has a knock-on effect. Inherent in my assumption that hash lookups are constant time is an assumption that comparing objects for equality is cheap. However, the equality test of Link is `O(n)` in the worst case. The worst case is when we have a hash collision between two equal links generated from different words - i.e. it occurs `O(E)` times in the second half of the graph generation. Other than that, except in the unlikely event of a hash collision between non-equal links, we're good. So we've traded in `O(V * n^2)` for `O(E * n * hash)`. See my previous point about statistics.

# Answer
> 5 votes
# Java

**Complexity** : ?? (I don't have a CompSci Degree, so i'd appreciate help in this matter.)

**Input** : Provide Pair of words (more than 1 pair if you wish) in the command line. If no Command line is specified 2 distinct random words are chosen.

```
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.Set;

public class M {

    // for memoization
    private static Map<String, List<String>> memoEdits = new HashMap<String, List<String>>();
    private static Set<String> dict;

    private static List<String> edits(String word, Set<String> dict) {
        if(memoEdits.containsKey(word))
            return memoEdits.get(word);

        List<String> editsList = new LinkedList<String>();
        char[] letters = word.toCharArray();
        for(int i = 0; i < letters.length; i++) {
            char hold = letters[i];
            for(char ch = 'A'; ch <= 'Z'; ch++) {
                if(ch != hold) {
                    letters[i] = ch;
                    String nWord = new String(letters);
                    if(dict.contains(nWord)) {
                        editsList.add(nWord);
                    }
                }
            }
            letters[i] = hold;
        }
        memoEdits.put(word, editsList);
        return editsList;
    }

    private static Map<String, String> bfs(String wordFrom, String wordTo,
                                           Set<String> dict) {
        Set<String> visited = new HashSet<String>();
        List<String> queue = new LinkedList<String>();
        Map<String, String> pred = new HashMap<String, String>();
        queue.add(wordFrom);
        while(!queue.isEmpty()) {
            String word = queue.remove(0);
            if(word.equals(wordTo))
                break;

            for(String nWord: edits(word, dict)) {
                if(!visited.contains(nWord)) {
                    queue.add(nWord);
                    visited.add(nWord);
                    pred.put(nWord, word);
                }
            }
        }
        return pred;
    }

    public static void printPath(String wordTo, String wordFrom) {
        int c = 0;
        Map<String, String> pred = bfs(wordFrom, wordTo, dict);
        do {
            System.out.println(wordTo);
            c++;
            wordTo = pred.get(wordTo);
        }
        while(wordTo != null && !wordFrom.equals(wordTo));
        System.out.println(wordFrom);
        if(wordTo != null)
            System.out.println(c - 1);
        else
            System.out.println("OY");
        System.out.println();
    }

    public static void main(String[] args) throws Exception {
        BufferedReader scan = new BufferedReader(new FileReader(new File("c:\\332609\\dict.txt")),
                                                 40 * 1024);
        String line;
        dict = new HashSet<String>(); //the dictionary (1 word per line)
        while((line = scan.readLine()) != null) {
            dict.add(line);
        }
        scan.close();
        if(args.length == 0) { // No Command line Arguments? Pick 2 random
                               // words.
            Random r = new Random(System.currentTimeMillis());
            String[] words = dict.toArray(new String[dict.size()]);
            int x = r.nextInt(words.length), y = r.nextInt(words.length);
            while(x == y) //same word? that's not fun...
                y = r.nextInt(words.length);
            printPath(words[x], words[y]);
        }
        else { // Arguments provided, search for path pairwise
            for(int i = 0; i < args.length; i += 2) {
                if(i + 1 < args.length)
                    printPath(args[i], args[i + 1]);
            }
        }
    }
}

```

# Answer
> 3 votes
## c on unix

Using dijkstra algorithm.

A large fraction of the code is a costume n-ary tree implementation, which serves to hold

* The wordlist (thus minimizing the number of times the input file is read (twice for no arguments, once for other cases) on the assumption that file IO is slow
* The partial trees as we build them.
* The final path.

Anyone interested in seeing *how* it works should probably read `findPath`, `process`, and `processOne` (and their associated comments). And maybe `buildPath` and `buildPartialPath`. The rest is bookkeeping and scaffolding. Several routines used during testing and development but not in the "production" version have been left in place.

I'm using `/usr/share/dict/words` on my Mac OS 10.5 box, which has so many long, esoteric entries that letting it run completely at random generates a *lot* of `OY`s.

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <getline.h>
#include <time.h>
#include <unistd.h>
#include <ctype.h>

const char*wordfile="/usr/share/dict/words";
/* const char*wordfile="./testwords.txt"; */
const long double RANDOM_MAX = (2LL<<31)-1;

typedef struct node_t {
  char*word;
  struct node_t*kids;
  struct node_t*next;
} node;

/* Return a pointer to a newly allocated node. If word is non-NULL,
 * call setWordNode;
 */
node*newNode(char*word){
  node*n=malloc(sizeof(node));
  n->word=NULL;
  n->kids=NULL;
  n->next=NULL;
  if (word) n->word = strdup(word);
  return n;
}
/* We can use the "next" links to treat these as a simple linked list,
 * and further can make it a stack or queue by
 *
 * * pop()/deQueu() from the head
 * * push() onto the head
 * * enQueue at the back
 */
void push(node*n, node**list){
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  n->next = (*list);
  (*list) = n;
}
void enQueue(node*n, node**list){
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  if ( *list==NULL ) {
    *list=n;
  } else {
    enQueue(n,&((*list)->next));
  }
}
node*pop(node**list){
  node*temp=NULL;
  if (list==NULL){
    fprintf(stderr,"Active operation on a NULL list! Exiting\n");
    exit(5);
  }
  temp = *list;
  if (temp != NULL) {
    (*list) = temp->next;
    temp->next=NULL;
  }
  return temp;
}
node*deQueue(node**list){ /* Alias for pop */
  return pop(list);
}

/* return a pointer to a node in tree matching word or NULL if none */
node* isInTree(char*word, node*tree){
  node*isInNext=NULL;
  node*isInKids=NULL;
  if (tree==NULL || word==NULL) return NULL;
  if (tree->word && (0 == strcasecmp(word,tree->word))) return tree;
  /* prefer to find the target at shallow levels so check the siblings
     before the kids */
  if (tree->next && (isInNext=isInTree(word,tree->next))) return isInNext;
  if (tree->kids && (isInKids=isInTree(word,tree->kids))) return isInKids;
  return NULL;
}

node* freeTree(node*t){
  if (t==NULL) return NULL;
  if (t->word) {free(t->word); t->word=NULL;}
  if (t->next) t->next=freeTree(t->next);
  if (t->kids) t->kids=freeTree(t->kids);
  free(t);
  return NULL;
}

void printTree(node*t, int indent){
  int i;
  if (t==NULL) return;
  for (i=0; i<indent; i++) printf("\t"); printf("%s\n",t->word);
  printTree(t->kids,indent+1);
  printTree(t->next,indent);
}

/* count the letters of difference between two strings */
int countDiff(const char*w1, const char*w2){
  int count=0;
  if (w1==NULL || w2==NULL) return -1;
  while ( (*w1)!='\0' && (*w2)!='\0' ) {
    if ( (*w1)!=(*w2) ) count++;
    w1++;
    w2++;
  }
  return count;
}

node*buildPartialPath(char*stop, node*tree){
  node*list=NULL;
  while ( (tree != NULL) &&
      (tree->word != NULL) &&
      (0 != strcasecmp(tree->word,stop)) ) {
    node*kid=tree->kids;
    node*newN = newNode(tree->word);
    push(newN,&list);
    newN=NULL;
    /* walk over all all kids not leading to stop */
    while ( kid &&
        (strcasecmp(kid->word,stop)!=0) &&
        !isInTree(stop,kid->kids) ) {
      kid=kid->next;
    }
    if (kid==NULL) {
      /* Assuming a preconditions where isInTree(stop,tree), we should
       * not be able to get here...
       */
      fprintf(stderr,"Unpossible!\n");
      exit(7);
    }
    /* Here we've found a node that either *is* the target or leads to it */
    if (strcasecmp(stop,kid->word) == 0) {
      break;
    }
    tree = kid;
  }
  return list;
}
/* build a node list path
 *
 * We can walk down each tree, identfying nodes as we go
 */
node*buildPath(char*pivot,node*frontTree,node*backTree){
  node*front=buildPartialPath(pivot,frontTree);
  node*back=buildPartialPath(pivot,backTree);
  /* weld them together with pivot in between
  *
  * The front list is in reverse order, the back list in order
  */
  node*thePath=NULL;
  while (front != NULL) {
    node*n=pop(&front);
    push(n,&thePath);
  }
  if (pivot != NULL) {
    node*n=newNode(pivot);
    enQueue(n,&thePath);
  }
  while (back != NULL) {
    node*n=pop(&back);
    enQueue(n,&thePath);
  }
  return thePath;
}

/* Add new child nodes to the single node in ts named by word. Also
 * queue these new word in q
 *
 * Find node N matching word in ts
 * For tword in wordList
 *    if (tword is one change from word) AND (tword not in ts)
 *        add tword to N.kids
 *        add tword to q
 *        if tword in to
 *           return tword
 * return NULL
 */
char* processOne(char *word, node**q, node**ts, node**to, node*wordList){
  if ( word==NULL || q==NULL || ts==NULL || to==NULL || wordList==NULL ) {
    fprintf(stderr,"ProcessOne called with NULL argument! Exiting.\n");
    exit(9);
  }
  char*result=NULL;
  /* There should be a node in ts matching the leading node of q, find it */
  node*here = isInTree(word,*ts);
  /* Now test each word in the list as a possible child of HERE */
  while (wordList != NULL) {
    char *tword=wordList->word;
    if ((1==countDiff(word,tword)) && !isInTree(tword,*ts)) {
      /* Queue this up as a child AND for further processing */
      node*newN=newNode(tword);
      enQueue(newN,&(here->kids));
      newN=newNode(tword);
      enQueue(newN,q);
      /* This might be our pivot */
      if ( isInTree(tword,*to) ) {
    /* we have found a node that is in both trees */
    result=strdup(tword);
    return result;
      }
    }
    wordList=wordList->next;
  }
  return result;
}

/* Add new child nodes to ts for all the words in q */
char* process(node**q, node**ts, node**to, node*wordList){
  node*tq=NULL;
  char*pivot=NULL;
  if ( q==NULL || ts==NULL || to==NULL || wordList==NULL ) {
    fprintf(stderr,"Process called with NULL argument! Exiting.\n");
    exit(9);
  }
  while (*q && (pivot=processOne((*q)->word,&tq,ts,to,wordList))==NULL) {
    freeTree(deQueue(q));
  }
  freeTree(*q);
  *q=tq;
  return pivot;
}

/* Find a path between w1 and w2 using wordList by dijkstra's
 * algorithm
 *
 * Use a breadth-first extensions of the trees alternating between
 * trees.
 */
node* findPath(char*w1, char*w2, node*wordList){
  node*thePath=NULL; /* our resulting path */
  char*pivot=NULL; /* The node we find that matches */
  /* trees of existing nodes */
  node*t1=newNode(w1);
  node*t2=newNode(w2);
  /* queues of nodes to work on */
  node*q1=newNode(w1);
  node*q2=newNode(w2);

  /* work each queue all the way through alternating until a word is
     found in both lists */
  while( (q1!=NULL) && ((pivot = process(&q1,&t1,&t2,wordList)) == NULL) &&
     (q2!=NULL) && ((pivot = process(&q2,&t2,&t1,wordList)) == NULL) )
    /* no loop body */ ;

  /* one way or another we are done with the queues here */
  q1=freeTree(q1);
  q2=freeTree(q2);
  /* now construct the path */
  if (pivot!=NULL) thePath=buildPath(pivot,t1,t2);
  /* clean up after ourselves */
  t1=freeTree(t1);
  t2=freeTree(t2);

  return thePath;
}

/* Convert a non-const string to UPPERCASE in place */
void upcase(char *s){
  while (s && *s) {
    *s = toupper(*s);
    s++;
  }
}

/* Walks the input file stuffing lines of the given length into a list */
node*getListWithLength(const char*fname, int len){
  int l=-1;
  size_t n=0;
  node*list=NULL;
  char *line=NULL;
  /* open the word file */
  FILE*f = fopen(fname,"r");
  if (NULL==f){
    fprintf(stderr,"Could not open word file '%s'. Exiting.\n",fname);
    exit(3);
  }
  /* walk the file, trying each word in turn */
  while ( !feof(f) && ((l = getline(&line,&n,f)) != -1) ) {
    /* strip trailing whitespace */
    char*temp=line;
    strsep(&temp," \t\n");
    if (strlen(line) == len) {
      node*newN = newNode(line);
      upcase(newN->word);
      push(newN,&list);
    }
  }
  fclose(f);
  return list;
}

/* Assumes that filename points to a file containing exactly one
 * word per line with no other whitespace.
 * It will return a randomly selected word from filename.
 *
 * If veto is non-NULL, only non-matching words of the same length
 * wll be considered.
 */
char*getRandomWordFile(const char*fname, const char*veto){
  int l=-1, count=1;
  size_t n=0;
  char *word=NULL;
  char *line=NULL;
  /* open the word file */
  FILE*f = fopen(fname,"r");
  if (NULL==f){
    fprintf(stderr,"Could not open word file '%s'. Exiting.\n",fname);
    exit(3);
  }
  /* walk the file, trying each word in turn */
  while ( !feof(f) && ((l = getline(&line,&n,f)) != -1) ) {
    /* strip trailing whitespace */
    char*temp=line;
    strsep(&temp," \t\n");
    if (strlen(line) < 2) continue; /* Single letters are too easy! */
    if ( (veto==NULL) || /* no veto means chose from all */
     (
      ( strlen(line) == strlen(veto) )  && /* veto means match length */
      ( 0 != strcasecmp(veto,line) )       /* but don't match word */
       ) ) {
      /* This word is worthy of consideration. Select it with random
         chance (1/count) then increment count */
      if ( (word==NULL) || (random() < RANDOM_MAX/count) ) {
    if (word) free(word);
    word=strdup(line);
      }
      count++;
    }
  }
  fclose(f);
  upcase(word);
  return word;
}

void usage(int argc, char**argv){
  fprintf(stderr,"%s [ <startWord> [ <endWord> ]]:\n\n",argv[0]);
  fprintf(stderr,
      "\tFind the shortest transformation from one word to another\n");
  fprintf(stderr,
      "\tchanging only one letter at a time and always maintaining a\n");
  fprintf(stderr,
      "\tword that exists in the word file.\n\n");
  fprintf(stderr,
      "\tIf startWord is not passed, chose at random from '%s'\n",
      wordfile);
  fprintf(stderr,
      "\tIf endWord is not passed, chose at random from '%s'\n",
      wordfile);
  fprintf(stderr,
      "\tconsistent with the length of startWord\n");
  exit(2);
}

int main(int argc, char**argv){
  char *startWord=NULL;
  char *endWord=NULL;

  /* intialize OS services */
  srandom(time(0)+getpid());
  /* process command line */
  switch (argc) {
  case 3:
    endWord = strdup(argv[2]);
    upcase(endWord);
  case 2:
    startWord = strdup(argv[1]);
    upcase(startWord);
  case 1:
    if (NULL==startWord) startWord = getRandomWordFile(wordfile,NULL);
    if (NULL==endWord)   endWord   = getRandomWordFile(wordfile,startWord);
    break;
  default:
    usage(argc,argv);
    break;
  }
  /* need to check this in case the user screwed up */
  if ( !startWord || ! endWord || strlen(startWord) != strlen(endWord) ) {
    fprintf(stderr,"Words '%s' and '%s' are not the same length! Exiting\n",
        startWord,endWord);
    exit(1);
  }
  /* Get a list of all the words having the right length */
  node*wordList=getListWithLength(wordfile,strlen(startWord));
  /* Launch into the path finder*/
  node *theList=findPath(startWord,endWord,wordList);
  /* Print the resulting path */
  if (theList) {
    int count=-2;
    while (theList) {
      printf("%s\n",theList->word);
      theList=theList->next;
      count++;
    }
    printf("%d\n",count);
  } else {
    /* No path found case */
    printf("%s %s OY\n",startWord,endWord);
  }
  return 0;
}

```

Some output:

```
$ ./changeword dive name
DIVE
DIME
DAME
NAME
2
$ ./changeword house gorge
HOUSE
HORSE
GORSE
GORGE
2
$ ./changeword stop read
STOP
STEP
SEEP
SEED
REED
READ
4
$ ./changeword peace slate
PEACE
PLACE
PLATE
SLATE
2
$ ./changeword pole fast
POLE
POSE
POST
PAST
FAST
3
$ ./changeword
QUINTIPED LINEARITY OY
$ ./changeword sneaky
SNEAKY WAXILY OY
$ ./changeword TRICKY
TRICKY
PRICKY
PRINKY
PRANKY
TRANKY
TWANKY
SWANKY
SWANNY
SHANNY
SHANTY
SCANTY
SCATTY
SCOTTY
SPOTTY
SPOUTY
STOUTY
STOUTH
STOUSH
SLOUSH
SLOOSH
SWOOSH
19
$ ./changeword router outlet
ROUTER
ROTTER
RUTTER
RUTHER
OUTHER
OUTLER
OUTLET
5
$ ./changeword
IDIOM
IDISM
IDIST
ODIST
OVIST
OVEST
OVERT
AVERT
APERT
APART
SPART
SPARY
SEARY
DEARY
DECRY
DECAY
DECAN
DEDAN
SEDAN
17

```

Complexity analysis is non-trivial. The search is a two-sided, iterative deepening.

* For each node examined I walk the entire word list (though limited to words of the right length). Call the length of the list `W`.
* The minimum number of steps is `S_min = (<number of different letter>-1)` because if we are only one letter apart we score the change at 0 intermediate steps. The maximum is hard to quantify see the TRICKY--SWOOSH run above. Each half of the tree will be `S/2-1` to `S/2`
* I have not done an analysis of the branching behavior of the tree, but call it `B`.

So the minimum number of operations is around `2 * (S/2)^B * W`, not really good.

---
Tags: code-challenge, word-puzzle, 1p5
---


title: 2-dimensional ray tracing

text:
# Question
Title: 2-dimensional ray tracing
The challenge is to implement a 2-dimensional ray tracing program, text-based.

Sources of white light are `@` symbols. `R`, `G` and `B` are light filters. `/` and `\` are mirrors with 80% reflectivity. `?` is a light sensor. `>`, `<`, `^` and `V` combine light in the appropriate direction (e.g. if one red and one green came into a `>` the light would be emitted toward the right and it would be yellow). Other non-whitespace characters absorb all light. Light is emitted from `@` symbols in **four** directions.

When the program is run, it should produce output the same as the input, but with traced rays. Because this is 2 dimensional, and I guarantee in the input no rays will ever cross, there will be no problem with that. Each ray should be represented by a letter; r=red, g=green, b=blue, c=cyan, m=magenta, y=yellow, w=white. There won't be any ternary colors, ever. The casing is important to differentiate it from the input. After that output, the values of light captured by the question marks (in order of their appearance, left to right top to bottom) should be outputted as percentages and colors. For example, this input:

```
 /                  @
                    -
 \R>                 ?

 @B/

```

Should give the output:

```
 /wwwwwwwwwwwwwwwwww@w
 w                  -
w\R>mmmmmmmmmmmmmmmmm?
 w b
 @B/

#1: 72% Magenta

```

Another important point to note - when two colors are combined using a "prism" (the arrows) the strength of the combined light becomes the average strength of the two. Output must be *exactly as specified* (e.g. #x: \[x\]\[x\]x% *Color*).

If your language cannot read from STDIN and write to STDOUT, create a function (anonymous or lambda when available) that accepts the input as an argument and returns the result.

Directives to the compiler, structures required or recommended for all or most programs created in the language, etc. can be omitted. For example, `#include` and `using` directives (but not `#define`) may be removed in C-style languages, `#/usr/bin/perl -options` in Perl, and

```
 Module Module1
      Sub Main()
      End Sub
 End Module

```

in VB.NET, for example. If you import namespaces or add include directives, please note them in your answer.

Is that hard enough, now? :)

# Answer
> 2 votes
## Python, 602 559 614 chars

```
import sys
S=sys.stdin.readlines()
X=max(len(s)for s in S)
I='#'*X+''.join(t[:-1]+' '*(X-len(t))+'\n'for t in S)+'#'*X
L=len(I)
R=range(L)
B=[0]*L
C=[0]*L
for p in R:
 if'@'!=I[p]:continue
 for d in(1,-1,X,-X):
  q=p;c=7;b=100.
  while 1:
   q+=d;a=I[q];B[q]+=b;C[q]|=c
   if a in'\/':d=(ord(a)/30-2)*X/d;b*=.8
   elif a in'RGB':c&=ord(a)/5-12
   elif a in'><^V':d={'>':1,'<':-1,'^':-X,'V':X}[a];b/=2
   elif' '!=a:break
print''.join(I[p]if' '!=I[p]else' bgcrmyw'[C[p]]for p in R[X:-X])
i=0
for p in R:
 if'?'==I[p]:i+=1;print'#%d:'%i,'%.0f%%'%B[p],[0,'Blue','Green','Cyan','Red','Magenta','Yellow','White'][C[p]]

```

Edit: fixed so it doesn't need trailing spaces.

# Answer
> 2 votes
## F#

```
#nowarn "0025"

open System

type MirrorDirection = bool
type LightDirection = bool * bool
type Sq =
  | Air // [ ]
  | Mirror of MirrorDirection // [/] [\]
  | FilterR
  | FilterG
  | FilterB
  | Sensor // [?]
  | Combine of LightDirection // [^] [v] [<] [>]
  | Emitter // [@]
  | Wall of Char // non-whitespace

let [ mL; mR ] : MirrorDirection list = [ true; false ]
(* true T^/
       F</>F
        /vT   false
 *)
let [ dN; dS; dW; dE ] : LightDirection list = [ true, true; false, true; true, false; false, false ]
let bounce (m : MirrorDirection) ((a, b) : LightDirection) =
  m <> a, not b

let dv (a : LightDirection) =
  if a = dN then 0, -1
  elif a = dS then 0, 1
  elif a = dW then -1, 0
  else 1, 0

let fo<'a> : (('a option)[,] -> 'a seq) =
  Seq.cast
  >> Seq.filter Option.isSome
  >> Seq.map Option.get

let input = Console.In.ReadToEnd().Replace("\r\n", "\n")
let sqs =
  input.Split('\n')
  |> Array.map (fun x ->
    x.ToCharArray()
    |> Array.map (
      function
      | ' ' | '\t' | '\v' -> Air
      | '/' -> Mirror mL
      | '\\' -> Mirror mR
      | 'R' -> FilterR
      | 'G' -> FilterG
      | 'B' -> FilterB
      | '?' -> Sensor
      | '^' -> Combine dN
      | 'v' -> Combine dS
      | '<' -> Combine dW
      | '>' -> Combine dE
      | '@' -> Emitter
      | x -> Wall x
    )
  )

let w =
  Array.map Array.length sqs
  |> Set.ofArray
  |> Set.maxElement
let h = sqs.Length

let ib x y = -1 < x && x < w && -1 < y && y < h

let arr = Array2D.init w h (fun x y ->
  if x < sqs.[y].Length then
    sqs.[y].[x]
  else
    Air
)

let board =
  Array2D.map (
    function
    | _ -> 0.0, 0.0, 0.0
  ) arr

let mutable rays =
  Array2D.mapi (fun x y a ->
    match a with
    | Emitter -> Some(x, y)
    | _ -> None
  ) arr
  |> fo
  |> Seq.map (fun (x, y) ->
    [|
      dN, x, y, 1., 1., 1.
      dS, x, y, 1., 1., 1.
      dW, x, y, 1., 1., 1.
      dE, x, y, 1., 1., 1.
    |]
  )
  |> Seq.reduce Array.append

for i = 0 to w * h * 2 do
  rays <-
    rays
    |> Array.map (
      (fun (dir, x, y, r, g, b) ->
        let dx, dy = dv dir
        dir, x + dx, y + dy, r, g, b
      )
      >> (fun (dir, x, y, r, g, b) ->
        if ib x y then
          match arr.[x, y] with
          | Wall _ -> Array.empty
          | Sensor -> [| dir, x, y, r, g, b |]
          | FilterR -> [| dir, x, y, r, 0., 0. |]
          | FilterG -> [| dir, x, y, 0., g, 0. |]
          | FilterB -> [| dir, x, y, 0., 0., b |]
          | Mirror d -> [| bounce d dir, x, y, r * 0.8, g * 0.8, b * 0.8 |]
          | _ -> [| dir, x, y, r, g, b |]
        else
          Array.empty
      ))
    |> Array.concat
  Array2D.mapi (fun x y a ->
    match a with
    | Combine d -> Some(x, y, d)
    | _ -> None
  ) arr
  |> fo
  |> Seq.iter (fun (x, y, d) ->
    for i = 0 to rays.Length - 1 do
      let (d', x', y', r, g, b) = rays.[i]
      if x' = x && y' = y then
        rays.[i] <- (d, x, y, r, g, b)
  )
  for d, x, y, r, g, b in rays do
    if ib x y then
      match board.[x, y] with
      | r', g', b' -> board.[x, y] <- r + r', g + g', b + b'

printfn "%s" (
  let mutable s = ""
  for y = 0 to h - 1 do
    for x = 0 to w - 1 do
      s <- s + (match arr.[x, y] with
                | Air ->
                  match board.[x, y] with
                  | r, g, b ->
                    if r + g + b = 0.0 then ' '
                    else
                      if g = 0.0 && b = 0.0 then 'r'
                      elif r = 0.0 && b = 0.0 then 'g'
                      elif r = 0.0 && g = 0.0 then 'b'
                      elif r = 0.0 then 'c'
                      elif g = 0.0 then 'm'
                      elif b = 0.0 then 'y'
                      else 'w'
                | Wall z -> z
                | Mirror z -> if z = mL then '/' else '\\'
                | FilterR -> 'R'
                | FilterG -> 'G'
                | FilterB -> 'B'
                | Sensor -> '?'
                | Combine z -> if z = dN then '^' elif z = dS then 'v' elif z = dW then '<' else '>'
                | Emitter -> '@'
                |> sprintf "%c")
    s <- s + "\n"
  s
)

Array2D.mapi (fun x y a ->
  match a with
  | Sensor -> Some(x, y)
  | _ -> None
) arr
|> fo
|> Seq.iteri (fun i (x, y) ->
  let (r, g, b) = board.[x, y]
  let desc =
    if r + g + b = 0.0 then "None"
    elif g = 0.0 && b = 0.0 then "Red"
    elif r = 0.0 && b = 0.0 then "Green"
    elif r = 0.0 && g = 0.0 then "Blue"
    elif r = 0.0 then "Cyan"
    elif g = 0.0 then "Magenta"
    elif b = 0.0 then "Yellow"
    else "White"
  let avg = int((r + g + b) * 100.0 / (match desc with
                                       | "White" | "None" -> 3.0
                                       | "Red" | "Green" | "Blue" -> 1.0
                                       | _ -> 2.0))
  printfn "#%d: %d%% %s" (i + 1) avg desc
)

```

---
Tags: code-golf, ascii-art
---