title: Best Scoring Boggle Board

text:
# Question
Title: Best Scoring Boggle Board
I was interested in seeing the answers to this (now defunct) question, but it has never been corrected/improved.

Given a set of 6-sided Boggle dice (configuration stolen from this question), determine in two minutes of processing time which board configuration will allow for the highest possible score. (i.e. which dice in which location with which side up allows for the largest scoring word pool?)

---

**OBJECTIVE**

* Your code should run for no more than 2 minutes (120 seconds). At that time, it should automatically stop running and print the results.
* Final challenge score will be the average Boggle score of 5 runs of the program.

+ In the event of a tie, the winner will be whichever algorithm found *more* words.
    + In the event there is still a tie, the winner will be whichever algorithm found *more* **long (8+)** words.

---

**RULES/CONSTRAINTS**

* This is a code challenge; code length is irrelevant.
* Please refer to this link for a word list (use `ISPELL "english.0"` list - the SCOWL list is missing some pretty common words).

+ This listing may be referred to/imported/read in your code any way you wish.
    + Only words matched by the regex `^([a-pr-z]|qu){3,16}$` will be counted. (Only lowercase letters, 3-16 characters, qu must be used as a unit.)
* Words are formed by linking adjacent letters (horizontal, vertical, and diagonal) to spell words out in the correct order, without using a single die more than once in a single words.

+ Words must be 3 letters or longer; shorter words will earn no points.
    + Duplicated letters are acceptable, just not dice.
    + Words that span the edges/cross over from one side of the board to the other are not allowed.
* The final Boggle (*not challenge*) score is the total of the point values for all the words that are found.

+ The point value assigned for each word is based on the length of the word. (see below)
    + Normal Boggle rules would deduct/discount words found by another player. Assume here no other players are involved and all found words count towards the total score.
    + However, words found more than once in the same grid should only be counted once.
* Your function/program must *FIND* the optimal arrangement; simply hard-coding a predetermined list won't do.
* Your output should be a 4x4 grid of your ideal game board, a list of all the found words for that board, and the Boggle score to match those words.

---

**DIE CONFIGURATION**

```
A  A  E  E  G  N
E  L  R  T  T  Y
A  O  O  T  T  W
A  B  B  J  O  O
E  H  R  T  V  W
C  I  M  O  T  U
D  I  S  T  T  Y
E  I  O  S  S  T
D  E  L  R  V  Y
A  C  H  O  P  S
H  I  M  N  Qu U
E  E  I  N  S  U
E  E  G  H  N  W
A  F  F  K  P  S
H  L  N  N  R  Z
D  E  I  L  R  X

```

---

**STANDARD BOGGLE SCORING TABLE**

```
Word length => Points
<= 2 - 0 pts
   3 - 1
   4 - 1
   5 - 2
   6 - 3
   7 - 5
>= 8 - 11 pts
*Words using the "Qu" die will count the full 2 letters for their word, not just the 1 die.

```

---

**EXAMPLE OUTPUT**

```
A  L  O  J
V  U  T  S
L  C  H  E
G  K  R  X

CUT
THE
LUCK
HEX
....

140 points

```

If any further clarification is needed, please ask!

# Answer
> 9 votes
# C, averaging 500+ 1500 1750 points

This is a relatively minor improvement over version 2 (see below for notes on previous versions). There are two parts. First: Instead of selecting boards randomly from the pool, the program now iterates over every board in the pool, using each one in turn before returning to the top of the pool and repeating. (Since the pool is being modified while this iteration occurs, there will still be boards that get chosen twice in a row, or worse, but this is not a serious concern.) The second change is that the program now tracks when the pool changes, and if the program goes for too long without improving the pool's contents, it determines that the search has "stalled", empties the pool, and starts over with a new search. It continues to do this until the two minutes are up.

I had initially thought that I would be employing some kind of heuristic search to get beyond the 1500-point range. @mellamokb's comment about a 4527-point board led me to assume that there was plenty of room for improvement. However, we are using a relatively small wordlist. The 4527-point board was scoring using YAWL, which is the most inclusive wordlist out there -- it's even bigger than the official US Scrabble wordlist. With this in mind, I re-examined the boards my program had found and noticed that there appeared to be a limited set of boards above 1700 or so. So for example, I had multiple runs that had discovered a board scoring 1726, but it was always the exact same board that was found (ignoring rotations and reflections).

As another test, I ran my program using YAWL as the dictionary, and it found the 4527-point board after about a dozen runs. Given this, I am hypothesizing that my program is already at the upper limit of the search space, and therefore the rewrite I was planning would introduce extra complexity for very little gain.

Here is my list of the five highest-scoring boards my program has found using the `english.0` wordlist:

```
1735 :  D C L P  E I A E  R N T R  S E G S
1738 :  B E L S  R A D G  T I N E  S E R S
1747 :  D C L P  E I A E  N T R D  G S E R
1766 :  M P L S  S A I E  N T R N  D E S G
1772:   G R E P  T N A L  E S I T  D R E S

```

My belief is that the 1772 "grep board" (as I've taken to calling it), with 531 words, is the highest-scoring board possible with this wordlist. Over 50% of my program's two-minute runs end with this board. I've also left my program running overnight without it finding anything better. So if there is a higher-scoring board, it would likely have to have some aspect that defeats the program's search technique. A board in which every possible small change to the layout causes a huge drop in the total score, for example, might never be discovered by my program. My hunch is that such a board is very unlikely to exist.

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

#define WORDLISTFILE "./english.0"

#define XSIZE 4
#define YSIZE 4
#define BOARDSIZE (XSIZE * YSIZE)
#define DIEFACES 6
#define WORDBUFSIZE 256
#define MAXPOOLSIZE 32
#define STALLPOINT 64
#define RUNTIME 120

/* Generate a random int from 0 to N-1.
 */
#define random(N)  ((int)(((double)(N) * rand()) / (RAND_MAX + 1.0)))

static char const dice[BOARDSIZE][DIEFACES] = {
    "aaeegn", "elrtty", "aoottw", "abbjoo",
    "ehrtvw", "cimotu", "distty", "eiosst",
    "delrvy", "achops", "himnqu", "eeinsu",
    "eeghnw", "affkps", "hlnnrz", "deilrx"
};

/* The dictionary is represented in memory as a tree. The tree is
 * represented by its arcs; the nodes are implicit. All of the arcs
 * emanating from a single node are stored as a linked list in
 * alphabetical order.
 */
typedef struct {
    int letter:8;   /* the letter this arc is labelled with */
    int arc:24;     /* the node this arc points to (i.e. its first arc) */
    int next:24;    /* the next sibling arc emanating from this node */
    int final:1;    /* true if this arc is the end of a valid word */
} treearc;

/* Each of the slots that make up the playing board is represented
 * by the die it contains.
 */
typedef struct {
    unsigned char die;      /* which die is in this slot */
    unsigned char face;     /* which face of the die is showing */
} slot;

/* The following information defines a game.
 */
typedef struct {
    slot board[BOARDSIZE];  /* the contents of the board */
    int score;              /* how many points the board is worth */
} game;

/* The wordlist is stored as a binary search tree.
 */
typedef struct {
    int item: 24;   /* the identifier of a word in the list */
    int left: 16;   /* the branch with smaller identifiers */
    int right: 16;  /* the branch with larger identifiers */
} listnode;

/* The dictionary.
 */
static treearc *dictionary;
static int heapalloc;
static int heapsize;

/* Every slot's immediate neighbors.
 */
static int neighbors[BOARDSIZE][9];

/* The wordlist, used while scoring a board.
 */
static listnode *wordlist;
static int listalloc;
static int listsize;
static int xcursor;

/* The game that is currently being examined.
 */
static game G;

/* The highest-scoring game seen so far.
 */
static game bestgame;

/* Variables to time the program and display stats.
 */
static time_t start;
static int boardcount;
static int allscores;

/* The pool contains the N highest-scoring games seen so far.
 */
static game pool[MAXPOOLSIZE];
static int poolsize;
static int cutoffscore;
static int stallcounter;

/* Some buffers shared by recursive functions.
 */
static char wordbuf[WORDBUFSIZE];
static char gridbuf[BOARDSIZE];

/*
 * The dictionary is stored as a tree. It is created during
 * initialization and remains unmodified afterwards. When moving
 * through the tree, the program tracks the arc that points to the
 * current node. (The first arc in the heap is a dummy that points to
 * the root node, which otherwise would have no arc.)
 */

static void initdictionary(void)
{
    heapalloc = 256;
    dictionary = malloc(256 * sizeof *dictionary);
    heapsize = 1;
    dictionary->arc = 0;
    dictionary->letter = 0;
    dictionary->next = 0;
    dictionary->final = 0;
}

static int addarc(int arc, char ch)
{
    int prev, a;

    prev = arc;
    a = dictionary[arc].arc;
    for (;;) {
        if (dictionary[a].letter == ch)
            return a;
        if (!dictionary[a].letter || dictionary[a].letter > ch)
            break;
        prev = a;
        a = dictionary[a].next;
    }
    if (heapsize >= heapalloc) {
        heapalloc *= 2;
        dictionary = realloc(dictionary, heapalloc * sizeof *dictionary);
    }
    a = heapsize++;
    dictionary[a].letter = ch;
    dictionary[a].final = 0;
    dictionary[a].arc = 0;
    if (prev == arc) {
        dictionary[a].next = dictionary[prev].arc;
        dictionary[prev].arc = a;
    } else {
        dictionary[a].next = dictionary[prev].next;
        dictionary[prev].next = a;
    }
    return a;
}

static int validateword(char *word)
{
    int i;

    for (i = 0 ; word[i] != '\0' && word[i] != '\n' ; ++i)
        if (word[i] < 'a' || word[i] > 'z')
            return 0;
    if (word[i] == '\n')
        word[i] = '\0';
    if (i < 3)
        return 0;
    for ( ; *word ; ++word, --i) {
        if (*word == 'q') {
            if (word[1] != 'u')
                return 0;
            memmove(word + 1, word + 2, --i);
        }
    }
    return 1;
}

static void createdictionary(char const *filename)
{
    FILE *fp;
    int arc, i;

    initdictionary();
    fp = fopen(filename, "r");
    while (fgets(wordbuf, sizeof wordbuf, fp)) {
        if (!validateword(wordbuf))
            continue;
        arc = 0;
        for (i = 0 ; wordbuf[i] ; ++i)
            arc = addarc(arc, wordbuf[i]);
        dictionary[arc].final = 1;
    }
    fclose(fp);
}

/*
 * The wordlist is stored as a binary search tree. It is only added
 * to, searched, and erased. Instead of storing the actual word, it
 * only retains the word's final arc in the dictionary. Thus, the
 * dictionary needs to be walked in order to print out the wordlist.
 */

static void initwordlist(void)
{
    listalloc = 16;
    wordlist = malloc(listalloc * sizeof *wordlist);
    listsize = 0;
}

static int iswordinlist(int word)
{
    int node, n;

    n = 0;
    for (;;) {
        node = n;
        if (wordlist[node].item == word)
            return 1;
        if (wordlist[node].item > word)
            n = wordlist[node].left;
        else
            n = wordlist[node].right;
        if (!n)
            return 0;
    }
}

static int insertword(int word)
{
    int node, n;

    if (!listsize) {
        wordlist->item = word;
        wordlist->left = 0;
        wordlist->right = 0;
        ++listsize;
        return 1;
    }

    n = 0;
    for (;;) {
        node = n;
        if (wordlist[node].item == word)
            return 0;
        if (wordlist[node].item > word)
            n = wordlist[node].left;
        else
            n = wordlist[node].right;
        if (!n)
            break;
    }

    if (listsize >= listalloc) {
        listalloc *= 2;
        wordlist = realloc(wordlist, listalloc * sizeof *wordlist);
    }
    n = listsize++;
    wordlist[n].item = word;
    wordlist[n].left = 0;
    wordlist[n].right = 0;
    if (wordlist[node].item > word)
        wordlist[node].left = n;
    else
        wordlist[node].right = n;
    return 1;
}

static void clearwordlist(void)
{
    listsize = 0;
    G.score = 0;
}

static void scoreword(char const *word)
{
    int const scoring[] = { 0, 0, 0, 1, 1, 2, 3, 5 };
    int n, u;

    for (n = u = 0 ; word[n] ; ++n)
        if (word[n] == 'q')
            ++u;
    n += u;
    G.score += n > 7 ? 11 : scoring[n];
}

static void addwordtolist(char const *word, int id)
{
    if (insertword(id))
        scoreword(word);
}

static void _printwords(int arc, int len)
{
    int a;

    while (arc) {
        a = len + 1;
        wordbuf[len] = dictionary[arc].letter;
        if (wordbuf[len] == 'q')
            wordbuf[a++] = 'u';
        if (dictionary[arc].final) {
            if (iswordinlist(arc)) {
                wordbuf[a] = '\0';
                if (xcursor == 4) {
                    printf("%s\n", wordbuf);
                    xcursor = 0;
                } else {
                    printf("%-16s", wordbuf);
                    ++xcursor;
                }
            }
        }
        _printwords(dictionary[arc].arc, a);
        arc = dictionary[arc].next;
    }
}

static void printwordlist(void)
{
    xcursor = 0;
    _printwords(1, 0);
    if (xcursor)
        putchar('\n');
}

/*
 * The board is stored as an array of oriented dice. To score a game,
 * the program looks at each slot on the board in turn, and tries to
 * find a path along the dictionary tree that matches the letters on
 * adjacent dice.
 */

static void initneighbors(void)
{
    int i, j, n;

    for (i = 0 ; i < BOARDSIZE ; ++i) {
        n = 0;
        for (j = 0 ; j < BOARDSIZE ; ++j)
            if (i != j && abs(i / XSIZE - j / XSIZE) <= 1
                       && abs(i % XSIZE - j % XSIZE) <= 1)
                neighbors[i][n++] = j;
        neighbors[i][n] = -1;
    }
}

static void printboard(void)
{
    int i;

    for (i = 0 ; i < BOARDSIZE ; ++i) {
        printf(" %c", toupper(dice[G.board[i].die][G.board[i].face]));
        if (i % XSIZE == XSIZE - 1)
            putchar('\n');
    }
}

static void _findwords(int pos, int arc, int len)
{
    int ch, i, p;

    for (;;) {
        ch = dictionary[arc].letter;
        if (ch == gridbuf[pos])
            break;
        if (ch > gridbuf[pos] || !dictionary[arc].next)
            return;
        arc = dictionary[arc].next;
    }
    wordbuf[len++] = ch;
    if (dictionary[arc].final) {
        wordbuf[len] = '\0';
        addwordtolist(wordbuf, arc);
    }
    gridbuf[pos] = '.';
    for (i = 0 ; (p = neighbors[pos][i]) >= 0 ; ++i)
        if (gridbuf[p] != '.')
            _findwords(p, dictionary[arc].arc, len);
    gridbuf[pos] = ch;
}

static void findwordsingrid(void)
{
    int i;

    clearwordlist();
    for (i = 0 ; i < BOARDSIZE ; ++i)
        gridbuf[i] = dice[G.board[i].die][G.board[i].face];
    for (i = 0 ; i < BOARDSIZE ; ++i)
        _findwords(i, 1, 0);
}

static void shuffleboard(void)
{
    int die[BOARDSIZE];
    int i, n;

    for (i = 0 ; i < BOARDSIZE ; ++i)
        die[i] = i;
    for (i = BOARDSIZE ; i-- ; ) {
        n = random(i);
        G.board[i].die = die[n];
        G.board[i].face = random(DIEFACES);
        die[n] = die[i];
    }
}

/*
 * The pool contains the N highest-scoring games found so far. (This
 * would typically be done using a priority queue, but it represents
 * far too little of the runtime. Brute force is just as good and
 * simpler.) Note that the pool will only ever contain one board with
 * a particular score: This is a cheap way to discourage the pool from
 * filling up with almost-identical high-scoring boards.
 */

static void addgametopool(void)
{
    int i;

    if (G.score < cutoffscore)
        return;
    for (i = 0 ; i < poolsize ; ++i) {
        if (G.score == pool[i].score) {
            pool[i] = G;
            return;
        }
        if (G.score > pool[i].score)
            break;
    }
    if (poolsize < MAXPOOLSIZE)
        ++poolsize;
    if (i < poolsize) {
        memmove(pool + i + 1, pool + i, (poolsize - i - 1) * sizeof *pool);
        pool[i] = G;
    }
    cutoffscore = pool[poolsize - 1].score;
    stallcounter = 0;
}

static void selectpoolmember(int n)
{
    G = pool[n];
}

static void emptypool(void)
{
    poolsize = 0;
    cutoffscore = 0;
    stallcounter = 0;
}

/*
 * The program examines as many boards as it can in the given time,
 * and retains the one with the highest score. If the program is out
 * of time, then it reports the best-seen game and immediately exits.
 */

static void report(void)
{
    findwordsingrid();
    printboard();
    printwordlist();
    printf("score = %d\n", G.score);
    fprintf(stderr, "// score: %d points (%d words)\n", G.score, listsize);
    fprintf(stderr, "// %d boards examined\n", boardcount);
    fprintf(stderr, "// avg score: %.1f\n", (double)allscores / boardcount);
    fprintf(stderr, "// runtime: %ld s\n", time(0) - start);
}

static void scoreboard(void)
{
    findwordsingrid();
    ++boardcount;
    allscores += G.score;
    addgametopool();
    if (bestgame.score < G.score) {
        bestgame = G;
        fprintf(stderr, "// %ld s: board %d scoring %d\n",
                time(0) - start, boardcount, G.score);
    }

    if (time(0) - start >= RUNTIME) {
        G = bestgame;
        report();
        exit(0);
    }
}

static void restartpool(void)
{
    emptypool();
    while (poolsize < MAXPOOLSIZE) {
        shuffleboard();
        scoreboard();
    }
}

/*
 * Making small modifications to a board.
 */

static void turndie(void)
{
    int i, j;

    i = random(BOARDSIZE);
    j = random(DIEFACES - 1) + 1;
    G.board[i].face = (G.board[i].face + j) % DIEFACES;
}

static void swapdice(void)
{
    slot t;
    int p, q;

    p = random(BOARDSIZE);
    q = random(BOARDSIZE - 1);
    if (q >= p)
        ++q;
    t = G.board[p];
    G.board[p] = G.board[q];
    G.board[q] = t;
}

/*
 *
 */

int main(void)
{
    int i;

    start = time(0);
    srand((unsigned int)start);

    createdictionary(WORDLISTFILE);
    initwordlist();
    initneighbors();

    restartpool();
    for (;;) {
        for (i = 0 ; i < poolsize ; ++i) {
            selectpoolmember(i);
            turndie();
            scoreboard();
            selectpoolmember(i);
            swapdice();
            scoreboard();
        }
        ++stallcounter;
        if (stallcounter >= STALLPOINT) {
            fprintf(stderr, "// stalled; restarting search\n");
            restartpool();
        }
    }

    return 0;
}

```

**Notes for version 2 (June 9)**

Here's one way to use the initial version of my code as a jumping-off point. The changes to this version consist of less than 100 lines, but tripled the average game score.

In this version, the program maintains a "pool" of candidates, consisting of the N highest-scoring boards that the program has generated so far. Every time a new board is generated, it is added to the pool and the lowest-scoring board in the pool is removed (which may very well be the board that was just added, if its score is lower than what's already there). The pool is initially filled with randomly generated boards, after which it keeps a constant size throughout the program's run.

The program's main loop consists of of selecting a random board from the pool and altering it, determining this new board's score and then putting it into the pool (if it scores well enough). In this fashion the program is continually refining high-scoring boards. The main activity is to make stepwise, incremental improvements, but the size of the pool also allows the program to find multi-step improvements that temporarily make a board's score worse before it can make it better.

Typically this program finds a good local maximum rather quickly, after which presumably any better maximum is too distant to be found. And so once again there's little point to running the program longer than 10 seconds. This might be improved by e.g. having the program detect this situation and start a fresh search with a new pool of candidates. However, this would net only a marginal increase. A proper heuristic search technique would likely be a better avenue of exploration.

(Side note: I saw that this version was generating about 5k boards/sec. Since the first version typically did 20k boards/sec, I was initially concerned. Upon profiling, however, I discovered that the extra time was spent managing the wordlist. In other words, it was entirely due to the program finding so many more words per board. In light of this, I considered changing the code to manage the wordlist, but given that this program is only using 10 of its allotted 120 seconds, such an optimization would be very premature.)

**Notes for version 1 (June 2)**

This is a very, very simple solution. All it does it generate random boards, and then after 10 seconds it outputs the one with the highest score. (I defaulted to 10 seconds because the extra 110 seconds permitted by the problem specification typically doesn't improve the final solution found enough to be worth waiting for.) So it's extremely dumb. However, it has all the infrastructure to make a good starting point for a more intelligent search, and if anyone wishes to make use of it before the deadline, I encourage them to do so.

The program starts by reading the dictionary into a tree structure. (The form isn't quite as optimized as it could be, but it's more than good enough for these purposes.) After some other basic initialization, it then begins generating boards and scoring them. The program examines about 20k boards per second on my machine, and after about 200k boards the random approach starts to run dry.

Since only one board is actually being evaluated at any given time, the scoring data is stored in global variables. This allows me to minimize the amount of constant data that has to be passed as arguments to the recursive functions. (I'm sure this will give some people hives, and to them I apologize.) The wordlist is stored as a binary search tree. Every word found has to be looked up in the wordlist, so that duplicate words aren't counted twice. The wordlist is only needed during the evaulation process, however, so it's discarded after the score is found. Thus, at the end of the program, the chosen board has to be scored all over again, so that the wordlist can be printed out.

Fun fact: The average score for a randomly-generated Boggle board, as scored by `english.0`, is 61.7 points.

# Answer
> 3 votes
## VBA (average currently ranging 80-110 points, unfinished)

Here's my working process, but it's far from the best possible; my absolute best score found on any board after many test runs is around 120. There still needs to be some better general cleanup and I'm sure there are more efficiencies to be gained in a number of places.

* **2012.05.09:**
    + Original posting
* **2012.05.10 - 2012.05.18:**
    + Improved the scoring algorithm
    + Improved the pathfinding logic
* **2012.06.07 - 2012.06.12**:
    + Reduced word limit to 6 from 8. Allows for more boards with smaller words. Appears to have made a slight improvement in average score. (10-15 or so boards checked per run vs. 1 to 2)
    + Following breadbox's suggestion, I've created a tree structure to house the word-list. This does speed up back-end checking of the words on a board significantly.
    + I played with changing the maximum word size (speed vs. score) and I haven't yet decided if 5 or 6 is a better option for me. 6 results in 100-120 total boards checked, while 5 results in 500-1000 (both of which are still far below the other examples provided so far).
    + **Problem**: After many successive runs, the process begins to slow, so there is still some memory to be managed.

This probably looks horrid to some of you, but as I said, WIP. **I am very open to *constructive* criticism!** Sorry for the very lengthy body...

---

*Dice Class Module*:

```
Option Explicit

Private Sides() As String

Sub NewDie(NewLetters As String)
    Sides = Split(NewLetters, ",")
End Sub

Property Get Side(i As Integer)
    Side = Sides(i)
End Property

```

---

*Tree Class Module*:

```
Option Explicit

Private zzroot As TreeNode

Sub AddtoTree(ByVal TreeWord As Variant)
Dim i As Integer
Dim TempNode As TreeNode

    Set TempNode = TraverseTree(TreeWord, zzroot)
    SetNode TreeWord, TempNode

End Sub

Private Function SetNode(ByVal Value As Variant, parent As TreeNode) As TreeNode
Dim ValChar As String
    If Len(Value) > 0 Then
        ValChar = Left(Value, 1)
        Select Case Asc(ValChar) - 96
            Case 1:
                Set parent.Node01 = AddNode(ValChar, parent.Node01)
                Set SetNode = parent.Node01
            Case 2:
                Set parent.Node02 = AddNode(ValChar, parent.Node02)
                Set SetNode = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set parent.Node26 = AddNode(ValChar, parent.Node26)
                Set SetNode = parent.Node26
            Case Else:
                Set SetNode = Nothing
        End Select

        Set SetNode = SetNode(Right(Value, Len(Value) - 1), SetNode)
    Else
        Set parent.Node27 = AddNode(True, parent.Node27)
        Set SetNode = parent.Node27
    End If
End Function

Function AddNode(ByVal Value As Variant, NewNode As TreeNode) As TreeNode
    If NewNode Is Nothing Then
        Set AddNode = New TreeNode
        AddNode.Value = Value
    Else
        Set AddNode = NewNode
    End If
End Function
Function TraverseTree(TreeWord As Variant, parent As TreeNode) As TreeNode
Dim Node As TreeNode
Dim ValChar As String
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            Set TraverseTree = TraverseTree(Right(TreeWord, Len(TreeWord) - 1), Node)
            If Not TraverseTree Is Nothing Then
                Set TraverseTree = parent
            End If
        Else
            Set TraverseTree = parent
        End If
    Else
        If parent.Node27.Value Then
            Set TraverseTree = parent
        Else
            Set TraverseTree = Nothing
        End If
    End If
End Function

Function WordScore(TreeWord As Variant, Step As Integer, Optional parent As TreeNode = Nothing) As Integer
Dim Node As TreeNode
Dim ValChar As String
    If parent Is Nothing Then Set parent = zzroot
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            WordScore = WordScore(Right(TreeWord, Len(TreeWord) - 1), Step + 1, Node)
        End If
    Else
        If parent.Node27 Is Nothing Then
            WordScore = 0
        Else
            WordScore = Step
        End If
    End If
End Function

Function ValidWord(TreeWord As Variant, Optional parent As TreeNode = Nothing) As Integer
Dim Node As TreeNode
Dim ValChar As String
    If parent Is Nothing Then Set parent = zzroot
    If Len(TreeWord) > 0 Then
        ValChar = Left(TreeWord, 1)

        Select Case Asc(ValChar) - 96
            Case 1:
                Set Node = parent.Node01
            Case 2:
                Set Node = parent.Node02
            ' ... - Reduced to limit size of answer.
            Case 26:
                Set Node = parent.Node26
            Case Else:
                Set Node = Nothing
        End Select

        If Not Node Is Nothing Then
            ValidWord = ValidWord(Right(TreeWord, Len(TreeWord) - 1), Node)
        Else
            ValidWord = False
        End If
    Else
        If parent.Node27 Is Nothing Then
            ValidWord = False
        Else
            ValidWord = True
        End If
    End If
End Function

Private Sub Class_Initialize()
    Set zzroot = New TreeNode
End Sub

Private Sub Class_Terminate()
    Set zzroot = Nothing
End Sub

```

---

*TreeNode Class Module*:

```
Option Explicit

Public Value As Variant
Public Node01 As TreeNode
Public Node02 As TreeNode
' ... - Reduced to limit size of answer.
Public Node26 As TreeNode
Public Node27 As TreeNode

```

---

*Main Module*:

```
Option Explicit

Const conAllSides As String = ";a,a,e,e,g,n;e,l,r,t,t,y;a,o,o,t,t,w;a,b,b,j,o,o;e,h,r,t,v,w;c,i,m,o,t,u;d,i,s,t,t,y;e,i,o,s,s,t;d,e,l,r,v,y;a,c,h,o,p,s;h,i,m,n,qu,u;e,e,i,n,s,u;e,e,g,h,n,w;a,f,f,k,p,s;h,l,n,n,r,z;d,e,i,l,r,x;"
Dim strBoard As String, strBoardTemp As String, strWords As String, strWordsTemp As String
Dim CheckWordSub As String
Dim iScore As Integer, iScoreTemp As Integer
Dim Board(1 To 4, 1 To 4) As Integer
Dim AllDice(1 To 16) As Dice
Dim AllWordsTree As Tree
Dim AllWords As Scripting.Dictionary
Dim CurWords As Scripting.Dictionary
Dim FullWords As Scripting.Dictionary
Dim JunkWords As Scripting.Dictionary
Dim WordPrefixes As Scripting.Dictionary
Dim StartTime As Date, StopTime As Date
Const MAX_LENGTH As Integer = 5
Dim Points(3 To 8) As Integer

Sub Boggle()
Dim DiceSetup() As String
Dim i As Integer, j As Integer, k As Integer

    StartTime = Now()

    strBoard = vbNullString
    strWords = vbNullString
    iScore = 0

    ReadWordsFileTree

    DiceSetup = Split(conAllSides, ";")

    For i = 1 To 16
        Set AllDice(i) = New Dice
        AllDice(i).NewDie "," & DiceSetup(i)
    Next i

    Do While WithinTimeLimit

        Shuffle

        strBoardTemp = vbNullString
        strWordsTemp = vbNullString
        iScoreTemp = 0

        FindWords

        If iScoreTemp > iScore Or iScore = 0 Then
            iScore = iScoreTemp
            k = 1
            For i = 1 To 4
                For j = 1 To 4
                    strBoardTemp = strBoardTemp & AllDice(k).Side(Board(j, i)) & "  "
                    k = k + 1
                Next j
                strBoardTemp = strBoardTemp & vbNewLine
            Next i
            strBoard = strBoardTemp
            strWords = strWordsTemp

        End If

    Loop

    Debug.Print strBoard
    Debug.Print strWords
    Debug.Print iScore & " points"

    Set AllWordsTree = Nothing
    Set AllWords = Nothing
    Set CurWords = Nothing
    Set FullWords = Nothing
    Set JunkWords = Nothing
    Set WordPrefixes = Nothing

End Sub

Sub ShuffleBoard()
Dim i As Integer

    For i = 1 To 16
        If Not WithinTimeLimit Then Exit Sub
        Board(Int((i - 1) / 4) + 1, 4 - (i Mod 4)) = Int(6 * Rnd() + 1)
    Next i

End Sub

Sub Shuffle()
Dim n As Long
Dim Temp As Variant
Dim j As Long

    Randomize
    ShuffleBoard
    For n = 1 To 16
        If Not WithinTimeLimit Then Exit Sub
        j = CLng(((16 - n) * Rnd) + n)
        If n <> j Then
            Set Temp = AllDice(n)
            Set AllDice(n) = AllDice(j)
            Set AllDice(j) = Temp
        End If
    Next n

    Set FullWords = New Scripting.Dictionary
    Set CurWords = New Scripting.Dictionary
    Set JunkWords = New Scripting.Dictionary

End Sub

Sub ReadWordsFileTree()
Dim FSO As New FileSystemObject
Dim FS
Dim strTemp As Variant
Dim iLength As Integer
Dim StartTime As Date

    StartTime = Now()
    Set AllWordsTree = New Tree
    Set FS = FSO.OpenTextFile("P:\Personal\english.txt")

    Points(3) = 1
    Points(4) = 1
    Points(5) = 2
    Points(6) = 3
    Points(7) = 5
    Points(8) = 11

    Do Until FS.AtEndOfStream
        strTemp = FS.ReadLine
        If strTemp = LCase(strTemp) Then
            iLength = Len(strTemp)
            iLength = IIf(iLength > 8, 8, iLength)
            If InStr(strTemp, "'") < 1 And iLength > 2 Then
                AllWordsTree.AddtoTree strTemp
            End If
        End If
    Loop
    FS.Close

End Sub

Function GetScoreTree() As Integer
Dim TempScore As Integer

    If Not WithinTimeLimit Then Exit Function

    GetScoreTree = 0

    TempScore = AllWordsTree.WordScore(CheckWordSub, 0)
    Select Case TempScore
        Case Is < 3:
            GetScoreTree = 0
        Case Is > 8:
            GetScoreTree = 11
        Case Else:
            GetScoreTree = Points(TempScore)
    End Select

End Function

Sub SubWords(CheckWord As String)
Dim CheckWordScore As Integer
Dim k As Integer, l As Integer

    For l = 0 To Len(CheckWord) - 3
        For k = 1 To Len(CheckWord) - l
            If Not WithinTimeLimit Then Exit Sub

            CheckWordSub = Mid(CheckWord, k, Len(CheckWord) - ((k + l) - 1))

            If Len(CheckWordSub) >= 3 And Not CurWords.Exists(CheckWordSub) Then
                CheckWordScore = GetScoreTree

                If CheckWordScore > 0 Then
                    CurWords.Add CheckWordSub, CheckWordSub
                    iScoreTemp = iScoreTemp + CheckWordScore
                    strWordsTemp = strWordsTemp & CheckWordSub & vbNewLine
                End If

                If Left(CheckWordSub, 1) = "q" Then
                    k = k + 1
                End If
            End If

        Next k
    Next l

End Sub

Sub FindWords()
Dim CheckWord As String
Dim strBoardLine(1 To 16) As String
Dim Used(1 To 16) As Boolean
Dim i As Integer, j As Integer, k As Integer, l As Integer, m As Integer, n As Integer
Dim StartSquare As Integer
Dim FullCheck As Variant

    n = 1
    For l = 1 To 4
        For m = 1 To 4
            If Not WithinTimeLimit Then Exit Sub
            strBoardLine(n) = AllDice(n).Side(Board(m, l))
            n = n + 1
        Next m
    Next l

    For i = 1 To 16
        For k = 1 To 16

            If Not WithinTimeLimit Then Exit Sub
            If k Mod 2 = 0 Then
                For j = 1 To 16
                    Used(j) = False
                Next j

                Used(i) = True
                MakeWords strBoardLine, Used, i, k / 2, strBoardLine(i)
            End If

        Next k
    Next i

    For Each FullCheck In FullWords.Items
        SubWords CStr(FullCheck)
    Next FullCheck

End Sub

Function MakeWords(BoardLine() As String, Used() As Boolean, _
    Start As Integer, _
    Direction As Integer, CurString As String) As String
Dim i As Integer, j As Integer, k As Integer, l As Integer

    j = 0

    Select Case Direction
        Case 1:
            k = Start - 5
        Case 2:
            k = Start - 4
        Case 3:
            k = Start - 3
        Case 4:
            k = Start - 1
        Case 5:
            k = Start + 1
        Case 6:
            k = Start + 3
        Case 7:
            k = Start + 4
        Case 8:
            k = Start + 5
    End Select

    If k >= 1 And k <= 16 Then
        If Not WithinTimeLimit Then Exit Function

        If Not Used(k) Then
            If ValidSquare(Start, k) Then
                If Not (JunkWords.Exists(CurString & BoardLine(k))) And Not FullWords.Exists(CurString & BoardLine(k)) Then
                    Used(k) = True
                    For l = 1 To MAX_LENGTH
                        If Not WithinTimeLimit Then Exit Function
                        MakeWords = CurString & BoardLine(k)
                        If Not (JunkWords.Exists(MakeWords)) Then
                            JunkWords.Add MakeWords, MakeWords
                        End If
                        If Len(MakeWords) = MAX_LENGTH And Not FullWords.Exists(MakeWords) Then
                            FullWords.Add MakeWords, MakeWords
                        ElseIf Len(MakeWords) < MAX_LENGTH Then
                            MakeWords BoardLine, Used, k, l, MakeWords
                        End If
                    Next l
                    Used(k) = False
                End If
            End If
        End If
    End If

    If Len(MakeWords) = MAX_LENGTH And Not FullWords.Exists(MakeWords) Then
        FullWords.Add MakeWords, MakeWords
        Debug.Print "FULL - " & MakeWords
    End If

End Function

Function ValidSquare(StartSquare As Integer, EndSquare As Integer) As Boolean
Dim sx As Integer, sy As Integer, ex As Integer, ey As Integer

    If Not WithinTimeLimit Then Exit Function

    sx = (StartSquare - 1) Mod 4 + 1
    ex = (EndSquare - 1) Mod 4 + 1

    sy = Int((StartSquare - 1) / 4 + 1)
    ey = Int((EndSquare - 1) / 4 + 1)

    ValidSquare = (sx - 1 <= ex And sx + 1 >= ex) And (sy - 1 <= ey And sy + 1 >= ey) And StartSquare <> EndSquare

End Function

Function WithinTimeLimit() As Boolean
    StopTime = Now()
    WithinTimeLimit = (Round(CDbl(((StopTime - StartTime) - Int(StopTime - StartTime)) * 86400), 0) < 120)
End Function

```

# Answer
> 2 votes
Quick look at size of the search space.

```
   16! => 20922789888000 Dice Permutations
(6^16) =>  2821109907456 Face Permutations
 59025489844657012604928000 Boggle Grids

```

Reducing to exclude the repetition on each die.

```
              16! => 20922789888000 Dice Permutations
(4^4)*(5^6)*(6^5) => 31104000000 Unique Face Permutations
   650782456676352000000000 Boggle Grids

```

@breadbox store the dictionary as an Hash Table O(1) checking.

**EDIT**

Best Board (I've witnessed so far)

```
L  E  A  N
S  E  T  M
T  S  B  D
I  E  G  O

Score: 830
Words: 229
SLEETIEST  MANTELETS
MANTEELS  MANTELET  MATELESS
MANTEEL  MANTELS  TESTEES  BETISES  OBTESTS  OBESEST
SLEETS  SLEEST  TESTIS  TESTES  TSETSE  MANTES  MANTEL  TESTAE  TESTEE
STEELS  STELES  BETELS  BESETS  BESITS  BETISE  BODGES  BESEES  EISELS
GESTES  GEISTS  OBTEST
LEANT  LEATS  LEETS  LEESE  LESES  LESTS  LESBO  ANTES  NATES  SLEET  SETAE
SEATS  STIES  STEEL  STETS  STEAN  STEAM  STELE  SELES  TAELS  TEELS  TESTS
TESTE  TELES  TETES  MATES  TESTA  TEATS  SEELS  SITES  BEETS  BETEL  BETES
BESET  BESTS  BESIT  BEATS  BODGE  BESEE  DOGES  EISEL  GESTS  GESTE  GESSE
GEITS  GEIST  OBESE
LEAN  LEAT  LEAM  LEET  LEES  LETS  LEST  LESS  EATS  EELS  ELSE  ETNA  ESES
ESTS  ESSE  ANTE  ANTS  ATES  AMBO  NATS  SLEE  SEEL  SETA  SETS  SESE  SEAN
SEAT  SEAM  SELE  STIE  STET  SEES  TAEL  TAES  TEEL  TEES  TEST  TEAM  TELE
TELS  TETS  TETE  MATE  MATS  MAES  TIES  TEAT  TEGS  SELS  SEGO  SITS  SITE
BEET  BEES  BETA  BETE  BETS  BEST  BEAN  BEAT  BEAM  BELS  BOGS  BEGO  BEGS
DOGE  DOGS  DOBS  GOBS  GEST  GEIT  GETS  OBES
LEA  LEE  LET  LES  EAN  EAT  EEL  ELS  ETA  EST  ESS  ANT  ATE  NAT  NAE  NAM
SEE  SET  SEA  SEL  TAN  TAE  TAM  TEE  TES  TEA  TEL  TET  MNA  MAN  MAT  MAE
TIE  TIS  TEG  SEG  SEI  SIT  BEE  BET  BEL  BOD  BOG  BEG  DOG  DOB  ITS  EGO
GOD  GOB  GET  OBS  OBE
EA  EE  EL  ET  ES  AN  AT  AE  AM  NA  ST  TA  TE  MA
TI  SI  BE  BO  DO  IT  IS  GO  OD  OB

```

# Answer
> 1 votes
My entry is over here on Dream.In.Code ~30ms per a board search (on a 2 core machine, should be quicker with more cores)

---
Tags: code-challenge, game, boggle
---


# Question
Title: Print largest integer you can with the fewest characters
Find a way to output a large integer with few characters. Solutions will be scored based on the magnitude of the number and shortness of code.

EDIT: Let's impose a time limit of a minute on sensible hardware, where sensible is a PC you can buy off the shelves.

# Answer
> 31 votes
# JavaScript (10)

```
alert(1/0)

```

Prints "Infinity", did I win? :)

# Answer
> 21 votes
## bc (1 character)

```
9

```

Without a scoring method, this has a fair magnitude/length ratio indeed.

# Answer
> 17 votes
### bash (41)

approx. 10,000,000 digits:

```
ulimit -t 60;while true;do echo -n 5;done

```

# Answer
> 16 votes
## Python 18 characters

```
print hex(8**9**9)

```

It's about 290 million digits.

Turns out python `print` of decimal numbers is really slow, but `hex` is fast:

```
> time python -c "print hex(8**9**9)" | wc
   1       1 290565371
real    0m40.514s

```

# Answer
> 12 votes
## Ruby - 8 chars

```
p $$**$$

```

260120641601536 digits, today on my system. ($$ is the process ID).

# Answer
> 11 votes
```
while(1){print 1}

```

Time to write is `O(n)` compared to length of output number.

# Answer
> 10 votes
## C 86 (including NL)

```
main(i){
char b[8<<14];
memset(b,'9',8<<14);
for(i=0;i<8<<15;i++)
write(1,b,8<<14);
}

```

Prints 34\_359\_973\_368 digits on my i7 620M. Challenge this score!

```
$ gcc -O3 a.c; time ./a.out | wc -c
34359738368

real    0m31.974s
user    0m0.500s
sys     0m41.031s

```

# Answer
> 7 votes
### bash, 35 chars, unimaginably big number

The question doesn't specify the output representation, so I'm going to go charging far past any of the numbers output by previous answers (and way way way past even Graham's number):

```
for((i=999;i--;))do printf 9→9;done
```

An even shorter answer, although with a smaller number (still larger than Graham's number) is:

(12 chars)

```
echo 3→3→3→3
```

# Answer
> 7 votes
## Mathematica, 5

```
10! !

```

10 factorial, factorial. Prints 22,228,104 digits in about 30 seconds on my machine.

# Answer
> 5 votes
**PHP**

1,500,050,000,000 digits in 53.383 seconds (1.5 trillion digits) in 61 characters:

```
$a=bcpow('1000','10000');for($i=0;$i<50000000;$i++)echo $a;

```

# Answer
> 2 votes
### LISP (18)

10,000,000 digits in few seconds (SBCL).

```
(expt 10 10000000)

```

# Answer
> 2 votes
## Clojure - 28 chars (for unreasonably large numbers)

Strategy is to repeatedly apply the function f(x)=x^x. Works fine because Clojure automatically uses BigInteger arthmetic when this starts to overflow the normal integer range.

```
(nth(iterate #(expt % %)X)Y)

```

Choose X and Y depending on how unreasonably large you want the answer to be and how long you want it to run....:

For X=2:

```
Y=0 -> 2
Y=1 -> 4
Y=2 -> 256
Y=3 -> about 3.2*10^619 (in less than 1ms)
Y=4 -> unreasonably large

```

For X=9:

```
Y=0 -> 9
Y=1 -> 387420489
Y=2 -> about 10^320000000
Y=3 -> ermmm..... even bigger than unreasonably large?

```

A couple of things to note:

* `(iterate #(expt % %)X)` creates an infinite lazy sequence of ridiculously large exponentials. Y just determines which term of the sequence you want to look at (as you can see above, even the very early terms get very large very fast...)
* if not already imported you need to (use 'clojure.contrib.math) for the expt function

# Answer
> 2 votes
## Bash, 10 characters

```
seq -s9 $$

```

2011.8 digits per code character today on my machine.

# Answer
> 1 votes
Python: 83 characters, 32,089,643 digit number on my PC in a minute

```
import sys
sys.setrecursionlimit(1e9)
def p(n):sys.stdout.write(str(n));p(n*9)
p(9)

```

Note that it will either run out of time (in which case kill it) or eventually throw stack overflow errors, so you need to pipe stderr to `/dev/null`.

# Answer
> 1 votes
### Windows PowerShell(7)

I guess this is cheating, but techncially the value printed *is* an integer:

```
'9'*9e6

```

Exactly 9000000 digits.

Can be made larger with (19):

```
'9'*[int]::MaxValue

```

but raises an OutOfMemoryException on my poor 32-bit machine. This, however, will work fine as long as it's left running:

```
for(){write-host -n 9}

```

# Answer
> 1 votes
## PHP, 115 characters:

```
<? $f=fopen("/tmp/int.txt","w");for($i=$t=0;$i<2.4e7;$i++,$t++){if($t>1e4){fputs($f,$a);$t=0;}$a.=$i;}fputs($f,$a);

```

Outputs at least 1,024,000,00 characters to /tmp/int.txt.

File size (after running): http://codepad.viper-7.com/rgDglK

**Output to Screen, 76 characters**

```
<? for($i=$t=0;$i<2.4e7;$i++,$t++){if($t>1e4){echo $a;$t=0;}$a.=$i;}echo $a;

```

Has the ability to output 208, 896, 814, 305 characters, tested but unconfirmed through the output. You can confirm it by only calculating the length of the output through the second link. Each page may require a few refreshes due to errors.

Output: http://codepad.viper-7.com/rJJerv (Will crash the page eventually)
Length: http://codepad.viper-7.com/zWxX0C

Both the file size verification and the length verification take less than a minute on my old laptop, the output verification crashes the brower ~20 seconds into loading. The question did not state that the script had to work via command line, so I would not expect it to give perfect results when run that way.

# Answer
> 1 votes
`alert(Number.MAX_VALUE); : 1.7976931348623157e+308`
`<script>function f(m){n=1;for(i=1;i<=m;i++){n*=i;}return n;}alert(f(f(9)));</script> : Infinity`

# Answer
> 1 votes
```
time echo "7^7^7" | bc

...
29571409790619889611503701095991663965767866370599610471047901915338\
37220795832889549191447357443319063581523185421788310894001395744859\
694202869611751580402966282378932933502849310357073612870132343

real    0m58.837s
user    0m56.220s
sys 0m0.028s

```

on a 1.6 Mhz Pentium M.

# Answer
> 1 votes
```
cat /dev/sda

```

It's a 256-base Integer with 640,135,028,736 digits on my 640GB hd. Too bad some are non-printable.

# Answer
> 1 votes
Hmm, lets see, the largest "decimal number" I could generate on Linux, 2.4GHz Intel/Core2 w/2GB RAM, needing:

```
real    0m51.341s
user    0m1.820s
sys     0m5.644s

```

keeping user time far below 60s.

## Perl, 15 characters

```
print 1,"0"x2e9

```

gives a number staring with **100000...** and with about 2,000,000,000 (2 billion) zeros in total.

Regards

rbo

---

<sub>Tested with
```
 time perl -e 'print 1,"0"x2e9'>out

```

on a good hard drive.

</sub>

# Answer
> 1 votes
# Ruby - 12 chars

**7.5e+306 / character of code**

**25.7 digits / character of code**

```
p 9e307.to_i

```

# Answer
> 1 votes
Based on @M28 's answer

**PHP 10 chars**

```
echo 9e999

```

# Answer
> 1 votes
## C

```
printf("-infinity");

```

What's your definition of "large"?

# Answer
> 1 votes
## PHP, 18

```
<?for(;1;print9){}

```

=D

# Answer
> 1 votes
## Ruby, 11

`p 9 while 1`

Or you can omit the `9` and pretend that it's outputting in the ascii representation of the number "0x0A0A0A0A..."

# Answer
> 1 votes
# Factor, 137 characters

```
USING: calendar kernel io math.order sequences ;
58 seconds hence
99999 "9" <repetition> concat
[ dup write over now after? ] loop 2drop

```

With comments,

```
! calendar => seconds hence now
! kernel => dup over loop 2drop
! io => write
! math.order => after?
! sequences => <repetition> concat
USING: calendar kernel io math.order sequences ;

! Push the stop time (58 seconds after now). This leaves 2 extra seconds
! for starting and stopping the script.
58 seconds hence

! Push a long string of "9"s. The best length is near 99999.
99999 "9" <repetition> concat
[
    ! Write the very long string of "9"s.
    dup write
    ! If the stop time is after now, then loop.
    over now after?
] loop

! Empty the data stack.
2drop

```

This script tries to print as many "9" digits as possible, without exceeding the time limit of one minute. The number of digits changes from run to run.

Output is **10 ^ 4\_765\_052\_349 - 1**, if I must display the number in an *xterm*.

```
$ time ~/park/factor/factor scratch.factor | tee out
99999999999999999999999999999999999999999999999999999999999999999999999999999999
99999999999999999999999999999999999999999999999999999999999999999999999999999999
...
999999999999999999    0m58.56s real     0m15.63s user     0m26.21s system
$ wc -c out
 4765052349 out

```

Output is **10 ^ 22\_843\_571\_562 - 1**, if I never display the number.

```
$ time ~/park/factor/factor scratch.factor | wc -c
 22843571562
    0m58.32s real     0m50.27s user     0m19.50s system

```

Additional notes:

* Each `write` converts the string (Unicode codepoints) to a byte array (UTF-8). This conversion might waste time inside the loop. A faster program might make a byte array before the loop, and write the byte array inside the loop; but I cannot write a byte array to the default output stream, which is a character stream. I would have to use many characters to open a binary stream.
* A faster program might call *setitimer(2)* and handle *SIGALRM* after 58 seconds. I did not find a short way to call *setitimer(2)* from Factor.

# Answer
> 1 votes
# Haskell (code: 22 chars, output: 309 digits)

```
main=print$floor 1e309

```

This outputs: 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

Any higher exponent yields the same result, as 1e309 gets interpreted as Infinity, and this is apperantly the maximum result of `floor`.

# Answer
> 1 votes
# Haskell (20 characters)

```
main=print.floor$1/0

```

# Answer
> 1 votes
## Brainfuck, 4

Of course the answer is in base 256

```
-[.]

```

C-C after a minute. Will print a number about 255^1e10.

# Answer
> 1 votes
# Perl 6, 14 bytes

```
.print for^Inf

```

There is a pattern in this integer. I would name it a waterfall because it looks like one.

# Answer
> 0 votes
**Python, 21 characters**

```
print "10"+"^10"*1337

```

> "output a large integer"

It has 10 to the power of 10 repeated 1336 times (Tetration) number of zeros with a leading 1.

# Answer
> 0 votes
**Windows x86 .com**

8 bytes

```
B4 02 B2 39 CD 21 EB F8

```

# Answer
> 0 votes
Interpreted Haskell using tryhaskell.org, 10 characters, 5120 digits

```
0xF^0xFFFF

```

---
Tags: code-golf, code-challenge, number
---


# Question
Title: Generate a valid equation using user-specified numbers
This is based on a game one of my math teachers used to play in middle school. He would write 5 random one-digit numbers on the board, and then a random two-digit number. We would try to create an equation that used all 5 of the one-digit numbers to yield the two-digit number. Here are some examples with solutions to explain this better:

```
Input:           Solution:
7 5 4 8 4 34     5*8-7+4/4 = 34
3 1 5 7 6 54     (7+3)*6-5-1 = 54
3 9 2 1 6 87     9*(2+1)*3+6 = 87
2 1 6 9 7 16     (9-7+6*1)*2 = 16
2 4 5 8 6 96     8*(5+6)+2*4 = 96
3 8 4 5 4 49     8*(4+4)-3*5 = 49

```

This challenge is to write a program that can generate such equations for a given input. The input can be provided either via the command line or via a prompt. The 5 one-digit numbers will always be entered first (in no particular order), followed by the two-digit number. The program will then print out a solution equation it finds; you do not have to handle situations where there is no solution. The function must be capable of using the following operations in the equation: addition, subtraction, multiplication, and division. If you would like to allow additional basic operations, that's fine as long as they remain in the spirit of the challenge (negation, exponentiation, and modulus would be nice additions). Order of operations follows the standard math rules, so parenthesis will be needed for grouping. The program must take less than a minute to run on a modern computer.

Programs will be scored based on code length (including required whitespace). Note: division must be exact, not rounded or truncated to nearest integer.

# Answer
> 7 votes
## Python 2.7 (284), Python 3.x (253)

```
from __future__ import division #(Remove for Python 3.x)
from itertools import *
a=raw_input().split()
for i in permutations(a[:-1],5):
 for j in product('+-*/',repeat=5):
  for k,l in combinations(range(1,12,2),2):
   d=''.join(sum(zip(i,j),()))[:-1];d='('+d[:l]+')'+d[l:]
   if eval(d)==int(a[-1]):print d;b

```

It gives an error (calling unknown function `b`) on solution.

Basically, it's a gigantic brute force. It takes in the input, splits it by its spaces (`1 2 -> [1,2]`), and then permutes through that list. With every permutation, it will iterate through all possible strings of length 5 using the characters `+-*/`. With each of those iterations, it will generate the combinations of length 2 of the list `[1,3,5,7,9,11]`, interweave the permutation and the string together (`12345 *-/+- -> 1*2-3/4+5-`), and put in the parentheses. Finally, it will evaluate it, and if the answer and equation are true, then it prints the equation and stops.

This is horribly inefficient, about `O(n!/(n-5)!)=O(n^5)`, but it runs in a reasonable time for the test inputs.

# Answer
> 3 votes
### Scala 368:

The 2nd g=-Line is more easy to test, the first is flexible to take command arguments, and both are of equal length, so I only count from the second one - remove it to do args passing:

```
val g=(args.map(_.toDouble))
val g=Array(3,9,2, 1, 6, 87)
val k="+*/-DQ"
val i=(0 to 5)
val f:Seq[(Double,Double)=>Double]=Seq(_+_,_*_,_/_,_-_,(a,b)=>b-a,(a,b)=>b/a)
val h=g.init.permutations;
for(j<-h;o<-i;p<-i;q<-i;r<-i;z=try{f(r)(f(q)(f(p)(f(o)(j(0),j(1)),j(2)),j(3)),j(4))}catch{case _ => 0}
if(z==g(5)))printf("(((%d%c%d)%c%d)%c%d)%c%d=%d\n",j(0),k(o),j(1),k(p),j(2),k(q),j(3),k(r),j(4),g(5))

```

Sample output (you might have a question right now - just a moment):

```
(((5+7)/1)+6)*3=54
(((5-7)D1)*6)*3=54
(((5D7)+1)*6)*3=54
(((5+7)+6)Q1)Q3=54

```

What about this 5D7 thing? D1? Is it hex? There is Q1, Q3 - what's that.

Sir\_Lagsalot allowed new basic operations in the spirit of the challenge, and yes, these are basic operations, Delta and Quotient.

They are different from a/b and a-b in that aQb means b/a and aDb means b-a. Let's call it the Ukrainian notation.

So

```
(((5-7)D1)*6)*3=54

```

means

```
((1-(5-7))*6)*3=54
 (1-(-2))*6*3
   3*6*3 = 18*3=54

```

To the more interesting question of the how and why: In the beginning I got mad about the possibilities to place the parentheses, and whether (a+b)-c = a+b-c = (a+b-c) = ((a+b)-c) = (b+a)-c and so on. You can get mad over this question, but if you write down the possible parenthesis combinations, you sometimes throw away the scratch sheet and face the fact: You always perform 4 operations between 5 values, and you always start with one of them. If the pattern is always `(((_x_)x_)x_)x_ ?= _` (x being one of the 4 operators) and allow the opposite direction ( x b) and (b x a), you addressed every possibility.

Now for a+b and a\*b we don't need no opposite direction, they are commutative. So I invented the D and Q operator, which just switch the direction. I now have 2 operators more, but don't need to switch direction. Well - it is done in the function Sequence:

```
 (a,b)=>b-a,(a,b)=>b/a

```

My for-comprehension takes the values from the Array g, and distributes them on a to e, then I pick 4 indexes to pick the function and later the (only by index) associated operator symbol. I have to catch div/0 errors, since subtraction can lead to zeros, while the sample input data doesn't contain a 0.

---
Tags: code-golf, puzzle-solver, expression-building
---


# Question
Title: generate a valid equation using specified operators
A twist on a recently asked question, you are given a list of operators and a result and you need to find integers which, when operated on by those operators, generate the result.

**Example 1**

input

```
+ + * / 13

```

possible output

```
4 8 2 2 4

```

which means that `4 + 8 + 2 * 2 / 4 = 13`.

More specifically, you are given a sequence of *N* operators (between 1 and 5 inclusive) and an integer result, space separated. You must print *N+1* integers, space separated, in the range 1 through 9, inclusive, that when alternated with the operators produce the result.

The operators are `+,-,*,/`. They have the natural precedence order (`*` and `/` before `+` and `-`, left associative). Divides must be integral divides, a divide with a fractional result is not allowed. Operators must appear in the order given.

Most problems will have more than one solution. Printing any of them, or any subset of them, is fine. If there is no solution, print `NO SOLUTION`.

**Example 2**

input

```
/ + - - 16

```

output

```
9 1 9 1 1

```

**Example 3**

input

```
+ 5

```

output

```
1 4
2 3
3 2
4 1

```

(or any nonempty subset of those lines)

**Example 4**

input

```
+ + 30

```

output

```
NO SOLUTION

```

**Example 5**

input

```
/ + / 3

```

output

```
6 3 5 5

```

note that `3 2 3 2` is not a solution, as `3/2+3/2=3` is true but the individual divides have fractional values.

Standard code golf, shortest answer wins.

# Answer
> 3 votes
## Perl, 129 160 151 chars

```
sub a{my($s,$t,$o)=splice@_,0,3;@_?map{a("$s $_","$t$o$_",@_)}1..9:
$o-eval$t||$o-eval"use integer;$t"||exit say$s}a"","","",split$",<>;say"NO SOLUTION"

```

Fun with recursion. The program exits upon finding the first valid tuple.

The `eval` has to be done twice, in and out of integer-only mode, in order to avoid invalid solutions like that given in example 5 in the description.

# Answer
> 1 votes
## Python (~~197 212~~ 277)

Related question, related answer. Gives the answer and an error if there is one, else prints "NO SOLUTION".

```
import re,itertools as I
e=eval;a=raw_input().split();c=1;b=len(a)
for i in I.product('123456789',repeat=b):
 d=''.join(sum(zip([j+'.'for j in i],a),()))[:3*b-1]
 if e(d)==int(a[-1])and all([e(n)%1==0 for n in re.findall('\d./\d.',d)]):print' '.join(i);c=0
print"NO SOLUTION"*c

```

# Answer
> 1 votes
### Scala 333

```
val o=args.init
val e=args.last
val n=(1 to 9)
val i=new bsh.Interpreter
def b(o:Array[String],s:String=""):Boolean={
if(s.isEmpty)n.exists(y=>b(o,s+y))else
if(o.isEmpty){
val r=i.eval(s)
if(r.toString==e){
println(s.replaceAll("[-*+/]"," "))
true}else false}else
n.exists(x=>b(o.tail,s+o(0)+x))
}
b(o)||{println("NO SOLUTION");true}

```

# Answer
> 0 votes
# Python 2.7, 192 190 184 181 chars

Getting rid of `itertools.product` saved 3 characters.

```
s=raw_input().split()
j=' '.join
s[-1]='=='+s[-1]
n=len(s)
x=[j(i)for i in map(str,range(10**(n-1),10**n))if'0'not in i and eval(j(map(j,zip(i,s))))]
print x and x[0]or"NO SOLUTION"

```

---
Tags: code-golf, expression-building
---


# Question
Title: Implement a model of computation using a type system
Implement any model of computation as powerful as a Turing machine using any existing language's type system.

Your solution should handle the computation using the language's type system, not the language's regular Turing complete features, nor a macro system. It is however acceptable to use the language's regular features for IO, typical boilerplate, etc. so long as your program's Turing completeness hangs on the type system.

You are certainly welcome to use optional type system features that require compiler options to activate.

Please specify how to program and run your machine, ala "edit these numbers/constructs in the source, compile it and run it."

As an example, there is an implementation of brainfuck in C++ template meta-programming. In fact, brainfuck is more complex than necessary because it offers user IO separate from its tape. A few simpler models of computation include Brainfuck's ancestor P", λ-calculus, the (2,3) Turing Machine, and Conway's Game of Life.

We'll declare the winner to be whoever minimizes : their code's length plus 10 times the number of commenters who assert they already knew the language had a turing complete type system.

# Answer
> 4 votes
My limited Haskell-fu has come up with this implementation of SK-calculus in Haskell's type system:

```
data S = S
data K = K
data A l r = A l r

class C i o | i -> o
instance C (A (A K a) b) a
instance C (A (A (A S a) b) c) (A (A a c) (A b c))

```

---
Tags: code-challenge
---


title: Create a User-Profile Mini-Game

text:
# Question
Title: Create a User-Profile Mini-Game
Yesterday, I stumbled on a very clever thing.

Yes, that's a working implementation of Tic-Tac-Toe on a user profile page, from `@minitech`. Of course, the moment I saw it, I had to reverse engineer his idea and one-up him :P

Here's my own example embedded directly in the post. It's a tad buggy due to a couple of implementation details I haven't worked out a good solution for. Sometimes after you click a peg, it doesn't update properly until another page refresh:

## Towers of Hanoi

Reset

## Can you do better?

* Create a working game in your posted answer (or your user profile page). This is done via appropriately configuring a webserver you own (or writing a program that acts as a webserver), and embedding content from it in a post, using the referer to determine what commands the user is giving to the game.
* Coolest idea (most votes) wins the competition, by Canada Day (Sunday, July 1, 2012 @ 11:59 PM EST)
* In the event of a tie, the older answer wins.

# Answer
## Conway's Game of Life

+1 generation \- +5 generations \- zoom in \- zoom out

Load pattern: random \- glider \- gunstar \- snail \- lwss \- lightspeedoscillator1 \- tumbler

Used Python and SVG output. I have tried using single pixels at first (so you could toggle single cells), but it did not work out, because the browser does not load images in order. Also, much bigger patterns are possible like this without crashing my webserver.

**Update:**

I had some fun with python and added several features and improvements:

* Added HUD with population count, zoom and name
* Patterns in the rle format can now be loaded (long list, via) using the `pattern` parameter (e.g. `?pattern=glider`). The filesize is limited to 1.5kB
* Can forward n generations, limited to 5 at a time, using the `next` parameter
* Slightly improved algorithm. It's not really fast though, I want this to stay simple
* It also works standalone now (uses either referer or its own query string): https://copy.sh/fcgi-bin/life2.py?pattern=gosperglidergun

```
sessions = {}

WIDTH = 130
HEIGHT = 130
RULE = (3,), (2, 3)

def read_pattern(filename, offset_x, offset_y):

    filename = PATH + filename + '.rle.gz'

    try:
        if os.stat(filename).st_size > 1500:
            return ['pattern too big', set()]
    except OSError as e:
        return ['could not find pattern', set()]

    file = gzip.open(filename)

    x, y = offset_x, offset_y
    name = ''
    pattern_string = ''
    field = []

    for line in file:
        if line[0:2] == '#N':
            name = line[2:-1]
        elif line[0] != '#' and line[0] != 'x':
            pattern_string += line[:-1]

    for count, chr in re.findall('(\d*)(b|o|\$|!)', pattern_string):
        count = int(count) if count else 1

        if chr == 'o':
            for i in range(x, x + count):
                field.append( (i, y) )
            x += count
        elif chr == 'b':
            x += count
        elif chr == '$':
            y += count
            x = offset_x
        elif chr == '!':
            break

    file.close()

    return [name, set(field)]

def next_generation(field, n):

    for _ in range(n):

        map = {}

        for (x, y) in field:
            for (i, j) in ( (x-1, y-1), (x, y-1), (x+1, y-1), (x-1, y), (x+1, y), (x-1, y+1), (x, y+1), (x+1, y+1) ):
                map[i, j] = map[i, j] + 1 if (i, j) in map else 1

        field = [
            (x, y)
            for x in range(0, WIDTH)
            for y in range(0, HEIGHT)
            if (x, y) in map
            if ( (map[x, y] in RULE[1]) if (x, y) in field else (map[x, y] in RULE[0]) )
        ]

    return field

def life(env, start):

    if 'REMOTE_ADDR' in env:
        client_ip = env['REMOTE_ADDR']
    else:
        client_ip = '0'

    if not client_ip in sessions:
        sessions[client_ip] = read_pattern('trueperiod22gun', 10, 10) + [2]

    session = sessions[client_ip]

    if 'HTTP_REFERER' in env:
        query = urlparse.parse_qs(urlparse.urlparse(env['HTTP_REFERER']).query, True)
    elif 'QUERY_STRING' in env:
        query = urlparse.parse_qs(env['QUERY_STRING'], True)
    else:
        query = None

    timing = time.time()

    if query:
        if 'next' in query:
            try:
                count = min(5, int(query['next'][0]))
            except ValueError as e:
                count = 1
            session[1] = set( next_generation(session[1], count) )
        elif 'random' in query:
            session[0:2] = 'random', set([ (random.randint(0, WIDTH), random.randint(0, HEIGHT)) for _ in range(800) ])
        elif 'pattern' in query:
            filename = query['pattern'][0]
            if filename.isalnum():
                session[0:2] = read_pattern(filename, 10, 10)
        elif 'zoomin' in query:
            session[2] += 1
        elif 'zoomout' in query and session[2] > 1:
            session[2] -= 1

    timing = time.time() - timing

    start('200 Here you go', [
        ('Content-Type', 'image/svg+xml'),
        ('Cache-Control', 'no-store, no-cache, must-revalidate, post-check=0, pre-check=0'),
        ('Expires', 'Tue, 01 Jan 2000 12:12:12 GMT')
    ])

    pattern_name, field, zoom = session

    yield '<?xml version="1.0" encoding="UTF-8"?>'
    yield '<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">'
    yield '<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" version="1.1" baseProfile="full" width="400px" height="200px">'
    yield '<!-- finished in %f -->' % timing
    yield '<text x="0" y="10" style="font-size:10px">Population: %d</text>' % len(field)
    yield '<text x="100" y="10" style="font-size:10px">Zoom: %d</text>' % zoom
    yield '<text x="180" y="10" style="font-size:10px; font-weight:700">%s</text>' % pattern_name
    yield '<line x1="0" y1="15" x2="666" y2="15" style="stroke:#000; stroke-width:1px" />'

    for (x, y) in field:
        yield '<rect x="%d" y="%d" width="%d" height="%d"/>' % (zoom * x, zoom * y + 20, zoom, zoom)

    yield '</svg>'

from flup.server.fcgi import WSGIServer
import random
import re
import gzip
import os
import urlparse
import time

WSGIServer(life).run()

```

You can take my code as a template for further python fastcgi submissions.
> 28 votes

# Answer
# C# - Stack Exchange Hangman

Guess names of Stack Exchange websites in this Hangman game:

(source: apphb.com)

\`A\` \`B\` \`C\` \`D\` \`E\` \`F\` \`G\` \`H\` \`I\` \`J\` \`K\` \`L\` \`M\` \`N\` \`O\` \`P\` \`Q\` \`R\` \`S\` \`T\` \`U\` \`V\` \`W\` \`X\` \`Y\` \`Z\`
\`New game\`

---

This was done using ASP.NET MVC 3.0. Here's the code of the `Controller` that does the trick:

```
public class HangmanController : Controller
{
    public ActionResult Index()
    {
        var game = Session["hangman"] as HangmanGame ?? HangmanGame.New();

        game = ExecuteGameCommand(game);

        Session["hangman"] = game;

        var imageRenderer = new HangmanImageRenderer(game);
        return new ImageResult(imageRenderer.Render());
    }

    private HangmanGame ExecuteGameCommand(HangmanGame game)
    {
        var referrerQuery = Request.UrlReferrer != null ? Request.UrlReferrer.Query : string.Empty;

        if (referrerQuery.Contains("_new_hangman_"))
            return HangmanGame.New();

        if(game.IsOver())
            return game;

        var chosenLetter = HangmanGame.ValidLetters
            .FirstOrDefault(letter => referrerQuery.Contains(String.Format("_hangman_{0}_", letter)));

        if (chosenLetter != default(char))
            game.RegisterGuess(chosenLetter);

        return game;
    }
}

```

Other than this code, there are three more classes that I haven't included since they are pretty long and straightforward:

* `HangmanGame` \- here's where the game business rules are implemented
* `HangmanImageRenderer` \- the class that encapsulates all the GDI ugliness
* `ImageResult` \- a custom `ActionResult` that is used to return a dynamically generated image

The entire code listing is available at http://pastebin.com/ccwZLknX
> 36 votes

# Answer
# Clojoban! \[WIP\]

I wanted to make a bigger game out of this to learn Clojure, so this took a while to pull off (and got pretty big.) I've had a lot of fun doing it, btw!

`Restart level``New game`

. .

\- `No-op*`

. .

**(click here if game becomes unresponsive)*

## Instructions

You are Robby , a hard-working robot. You work at a `FlipCo Industries` as a heavy load carrier. Your job is to move each `box` to a `goal` spending as few steps as possible. `FlipCo`'s facilities are **DANGEROUS**. There are lots of challenges and special places to discover.

If you get stuck, click `Restart level` (but your step count won't be reset!)

---

You can also play at Clojoban's front page (although it kind of ruins the purpose of the challenge.) It fixes the infamous anchor problem, doesn't require cross-site cookies and you can play with your keyboard arrow keys! You can also play at my user profile page without the annoying anchor problem.

In Firefox the image doesn't flicker while it's loading so it's a bit more comfortable to play.

This game is FAR from completion, **Clojoban is still a work in progress**. You can see the complete sourcecode at Clojoban's GitHub project page. There's some info in the README about contributing. I need levels too! See the level format at the example levels. You can peek at Clojoban's issue tracker and see what's coming next!
> 21 votes

# Answer
## Maze

(source: t15.org)

 `New`     \- `Noop button`

I started from the PHP maze generator I found here: http://dev.horemag.net/2008/03/01/php-maze-generation-class/.

**EDIT**: changed the output to PNG instead of SVG (for better cross browser compatibility).

**EDIT 2:** added a header for fixing IE cookie compatibility. Should now work correctly in all major browsers.

The image does not refresh if you take the same direction twice (due to the anchor links). Press F5 the second time, or play the maze on my stackoverflow profile.

**EDIT 3:** Added a no-op button for easily being able to take the same direction twice (see comments below).

```
<?php
// based upon the maze generator by Evgeni Vasilev (PHP Adaptation)
// see http://dev.horemag.net/2008/03/01/php-maze-generation-class/
class Maze
{
  var $maze = array();
  var $mx = 0;
  var $my = 0;
  var $xplayer = 1;
  var $yplayer = 1;

  function Maze($mx, $my)
  {
    $mx +=2;
    $my +=2;
    $this->mx = $mx;
    $this->my = $my;
    $dx = array( 0, 0, -1, 1 );
    $dy = array( -1, 1, 0, 0 );
    $todo = array();
    $todonum = 0;

    for ($x = 0; $x < $mx; ++$x){
      for ($y = 0; $y < $my; ++$y){
        if ($x == 0 || $x == $mx-1 || $y == 0 || $y == $my-1) {
          $this->maze[$x][$y] = 32;
        } else {
          $this->maze[$x][$y] = 63;
        }
      }
    }
    $x = rand(1, $mx-2); $y = rand(1, $my-2);
    $x = 1; $y = 1;
    $this->maze[$x][$y] &= ~48;
    for ($d = 0; $d < 4; ++$d){
      if (($this->maze[$x + $dx[$d]][$y + $dy[$d]] & 16) != 0) {
        $todo[$todonum++] = (($x + $dx[$d]) << 16) | ($y + $dy[$d]);
        $this->maze[$x + $dx[$d]][$y + $dy[$d]] &= ~16;
      }
    }

    while ($todonum > 0) {
      $n = rand(0, $todonum-1);
      $x = $todo[$n] >> 16;
      $y = $todo[$n] & 65535;
      $todo[$n] = $todo[--$todonum];
      do {
        $d = rand(0, 3);
      } while (($this->maze[$x + $dx[$d]][$y + $dy[$d]] & 32) != 0);
      $this->maze[$x][$y] &= ~((1 << $d) | 32);
      $this->maze[$x + $dx[$d]][$y + $dy[$d]] &= ~(1 << ($d ^ 1));
      for ($d = 0; $d < 4; ++$d){
        if (($this->maze[$x + $dx[$d]][$y + $dy[$d]] & 16) != 0) {
          $todo[$todonum++] = (($x + $dx[$d]) << 16) | ($y + $dy[$d]);
          $this->maze[$x + $dx[$d]][$y + $dy[$d]] &= ~16;
        }
      }
    }
    $this->maze[1][1] &= ~1;
    $this->maze[$mx-2][$my-2] &= ~2;
  }

  function _drawLine($img,$color, $x1, $y1, $x2, $y2)
  {
    imageline($img, $x1, $y1, $x2, $y2, $color);
  }

  function _drawPlayer($img, $x, $y, $r, $colorborder, $colorfill)
  {
    imagefilledellipse($img, $x, $y, $r, $r, $colorfill);
    imageellipse($img, $x, $y, $r, $r, $colorborder);
  }

  function _drawWin($img, $color)
  {
    imagestring($img, 5, 170, 90, "YOU WIN!", $color);
  }

  function movePlayerDown()
  {
    if ($this->yplayer+1 < $this->my-1 && ($this->maze[$this->xplayer][$this->yplayer] & 2) == 0)
    $this->yplayer++;
  }

  function movePlayerUp()
  {
    if ($this->yplayer-1 > 0 && ($this->maze[$this->xplayer][$this->yplayer] & 1) == 0)
      $this->yplayer--;
  }

  function movePlayerRight()
  {
    if ($this->xplayer+1 < $this->mx-1 && ($this->maze[$this->xplayer][$this->yplayer] & 8) == 0)
      $this->xplayer++;
  }

  function movePlayerLeft()
  {
    if ($this->xplayer-1 > 0 && ($this->maze[$this->xplayer][$this->yplayer] & 4) == 0)
      $this->xplayer--;
  }

  function renderImage($xs, $ys)
  {
    $off = 0;
    $w = ($this->mx*$xs)+($off*2); $h = ($this->my*$ys)+($off*2);
    $img = imagecreatetruecolor($w, $h);
    imagesetthickness($img, 2);
    $fg = imagecolorallocate($img, 0, 0, 0);
    $bg = imagecolorallocate($img, 248, 248, 248);
    $red = imagecolorallocate($img, 255, 0, 0);
    imagefill($img, 0, 0, $bg);
    if (($this->xplayer == $this->mx-2) && ($this->yplayer == $this->my-2)) {
      $this->_drawWin($img, $red);
      return $img;
    }

    for ($y = 1; $y < $this->my-1; ++$y) {
      for ($x = 1; $x < $this->mx-1; ++$x){
        if (($this->maze[$x][$y] & 1) != 0)
          $this->_drawLine ($img, $fg, $x * $xs + $off, $y * $ys + $off, $x * $xs + $xs + $off, $y * $ys + $off);
        if (($this->maze[$x][$y] & 2) != 0)
          $this->_drawLine ($img, $fg, $x * $xs + $off, $y * $ys + $ys + $off, $x * $xs + $xs + $off, $y * $ys + $ys + $off);
        if (($this->maze[$x][$y] & 4) != 0)
          $this->_drawLine ($img, $fg, $x * $xs + $off, $y * $ys + $off, $x * $xs + $off, $y * $ys + $ys + $off);
        if (($this->maze[$x][$y] & 8) != 0)
          $this->_drawLine ($img, $fg, $x * $xs + $xs + $off, $y * $ys + $off, $x * $xs + $xs + $off, $y * $ys + $ys + $off);
        if ($x == $this->xplayer && $y == $this->yplayer) {
          $this->_drawPlayer ($img, $x * $xs + ($xs/2), $y * $ys + ($ys/2), 14, $fg, $red);
        }
      }
    }
    return $img;
  }
}
header('P3P: CP="CURa ADMa DEVa PSAo PSDo OUR BUS UNI PUR INT DEM STA PRE COM NAV OTC NOI DSP COR"');
session_start();
$orig_url = $_SERVER['HTTP_REFERER'];
if (!isset($_SESSION['maze']) || strpos($orig_url, 'resetmaze')){
    $_SESSION['maze'] = new Maze(25,10);
}
$maze = $_SESSION['maze'];
if (strpos($orig_url, 'playerdown')) { $maze->movePlayerDown(); }
if (strpos($orig_url, 'playerup')) { $maze->movePlayerUp(); }
if (strpos($orig_url, 'playerright')) { $maze->movePlayerRight(); }
if (strpos($orig_url, 'playerleft')) { $maze->movePlayerLeft(); }
$img = $maze->renderImage(16,16);
header("Content-Type: image/png");
imagepng($img);
imagedestroy($img);
?>

```
> 17 votes

# Answer
## "Simon says" game

Unfortunately, I could not get this submission in on time by the (somewhat arbitrary) deadline, but I really wanted to demonstrate animation in such a user profile game, and none of the previous submissions are animated. This game is a clone of the classic Milton Bradley game Simon, in which the player tries to repeat an increasingly long sequence of signals.

Information about this game, including its source code, is available at its GitHub page. There may be occasional graphical glitches (especially on Windows computers) arising from the hackish "palette animation" that avoids the need for a graphics drawing library. The existence of these glitches can serve as a useful excuse for quickly losing this game because of terrible memory.

Additionally, the effects of high latency and limited bandwidth can make this game much more challenging than the original as well. I think that in order to get much more than five points (when the game first speeds up), you will need to determine which light flashes one more time than in the previous round rather than depending on the correct sequence (which is very hard to do).

If this game fails to work for you (it restarts every time you click a button), your browser might be blocking its cookie. I have not yet added a workaround, so for the time being, please either use Chrome, Opera, or Firefox or temporarily change your Internet Explorer or Safari cookie settings.

**Edit 2018-05-24:** At this time, I have deleted the publicly accessible Heroku instance of this app. I may or may not put the app back online at a later date. The app's code is still available on GitHub, so you can either run it locally or create your own Heroku app instance if you wish to play the game.
> 11 votes

---
Tags: popularity-contest, game
---


title: Mouse in a room

text:
# Question
Title: Mouse in a room
There is a mouse in a room, in the top-left corner. It can move up, down, left, or right, and the mouse cannot go through any cell in the room twice. Given this, return all the possible paths in which the mouse will visit every square.

**Input:** Two integers `m` and `n`, which represent the `m x n` room. m\<9, n\<9.

**Output:** The `m x n` room, with `^<>v` noting the direction the path goes. Each line of the room will be seperated by a newline, and each room will be seperated by one newline. The last room the mouse enters will be noted by a dot.

```
v > v .
v ^ v ^
> ^ > ^

next room goes here...

```

**Test Cases:**

Input: `2 3`, output:

```
v > v
> ^ .

> > v
. < <

v . <
> > ^

```

Shortest code wins.

# Answer
> 5 votes
### GolfScript, 146 137 characters

```
~:h\:w*:s(4\?,{[[0.]{\.4/\4%@[0$"<^v>"3$=]@2*)@[~2$3/+(\@3%+(\]@\}s(*[\;46]].{.0=.~0(>\0(>@~h<\w<&&&\0=~w*+*}%$s,={${1=}%h/n*n+n+}{;}if}%

```

The code shows a very direct implementation in GolfScript. Therefore, I suspect that there is plenty room for improvement. Be aware that the algorithm is really slow if you try it on anything larger than 3x3 or 2x4. I decided to put a `.` for the last position since any direction would be allowed there (the mouse already entered each cell and the last step is irrelevant).

Example:

```
> 2 4
>>>v
.<<<

v.<<
>>>^

v>>v
>^.<

v>v.
>^>^

```

*Edit:* Minor changes.

# Answer
> 4 votes
## Python, 296 269

With so many suggestions from others, I decided to make this a community solution. Tabs have been replaced with 4 spaces.

```
a=[-1,0,1,0];d='<^>v.'
def r(x,y):
 if G.values().count(4)<2:
    for i in n:print''.join(d[G[j,i]]for j in m)
    print
 for i in range(4):
    X=x+a[i];Y=y+a[i-1]
    if 4==G.get((X,Y)):G[x,y]=i;r(X,Y);G[X,Y]=4
m,n=map(range,input())
G=dict(((i,j),4)for i in m for j in n)
r(0,0)

```

**Example**

```
$ python paths.py
5,2
>>>>v
.<<<<

v>>>v
>^.<<

v>v>v
>^>^.

v>v.<
>^>>^

v.<<<
>>>>^

```

# Answer
> 1 votes
# Mathematica 347 315 chars

Very slow for all but the smallest arrays. This is because the solution is overly general, treating the paths as Hamiltonian Graphs rather than something more specific like a grid. Anyway, here's the code:

```
Needs["Combinatorica`"]
p=ReplacePart;
q[l_,{},s_]:=p[s,l->"."]//Grid
q[l_, d_,s_]:=q[l+d[[1,1]], Rest@d,p[s,l:>d[[1,2]]]]
f[r_,c_]:=Column[q[{1,1},Differences[#]/.{-1-> {{0,-1},"<"},1-> {{0,1},">"},c-> {{1,0},"v"},-c-> {{-1,0},"^"}},ConstantArray[0,{r,c}]]&/@Cases[HamiltonianPath[GridGraph[c,r],All],{1,__}],Spacings->{0,3}]

```

Example (I reformatted the output into a table):

```
"4 4"
f@@ImportString[%,"Table"][[1]]

```

---
Tags: code-golf, path-finding
---


title: Conway's Hello World

text:
# Question
Title: Conway's Hello World
It is often said, that all programmers should be able to write a "hello world" program in any programming language after a few glances on that language (And quicksort after a few more glances).

As the Conway's Game of Life is Turing complete (so it qualifies as a general-purpose programming language), the problem is self-explanatory:

Create a "Hello World!" application using only Conway's Game of Life! The only valid entry is an **initial state** for the Conway's Game of Life, which:

* **does not contain** any recognizable shape resembling the text "Hello World!"
* **will contain** a recognizable shape resembling the text "Hello World!" within a reasonable number of cycles (it should not run for more than a couple of minutes on a good PC - this enables billions of cycles and should be enough)
* the area where the "Hello World!" text will appear **should be empty** in the initial state! (Otherwise the problem would be way too easy) If no one manages to do it, we might reduce this requirement to "mostly empty"

**Scoring:**

**The winner will be based on the number of upvotes in approximately one week after the first valid submission.**

Guidelines for voting:

* more elaborate and beautiful output should be worth more
* output which is stable over many cycles should be worth more than one which fades away to be unrecognizable in the next cycle.
* a solution locked into a perpetual cycle, or starting from an interesting pattern is worth the most, because it proves intelligent design of the state, and not just random trial and error with a reverse simulation.

**The entry should be in a format readable by at least one of the notable simulators or an online simulator which the answerer links to. Links (to an animation or a simulator set to the initial state) are also accepted, even encouraged. If the output is not visible within a few cycles, the entry should specify after which cycle will the result be visible.**

---

***Edit:***

There can be some slight tolerance in the phrase to be generated. It can be "`Hello, World!`", "`hello, world`" "`HELLO WORLD!`" etc.

# Answer
> 58 votes
My first attempt to this, a relatively simple solution. It fires a couple of glider barrels. Each pair of gliders turns into a block, which then form the text. This process takes about 16000 generations (you can set a frame skip or use the superstep button in my simulator).

Direct Link. Move around with right mouse, zoom with mouse wheel.

Link to .rle file (also works with Golly)

Image of the pattern 32:1:

---
Tags: code-challenge, game-of-life
---


title: Christmas Lists

text:
# Question
Title: Christmas Lists
The challenge is to create one program that will accept as arguments (arrays of arrays) or on standard input (line-by-line, separated by commas) a collection of families and names, like so:

```
John,Anna
Mark,James
Elizabeth,Daniel,Isabelle
Ryan,Ruth

```

As well as two other arguments (two more arrays of pairs, as arrays) or on standard input (a blank line after the preceding input, followed by two comma-separated lists on two lines with an `=` separating pairings; see example) that represent the two previous years' Christmas lists:

```
John=Mark,James=Anna,Elizabeth=Ryan,...
John=Isabelle,Ryan=Elizabeth,Daniel=Mark,...

```

The function/program must return/output (in any format) a way that each person is assigned somebody to give a present to, following these rules:

1. A person cannot give a present to him or herself.
2. A person cannot give a present to anybody in his or her own family.
3. A person cannot be assigned the same person he or she was assigned in any of the two previous years.

If such a matching is impossible for every person, output/return `null` or nothing or something appropriate.

This is a code golf, so shortest code wins, but I'll also give a bounty to the code that runs fastest (on my computer, at least, though results shouldn't vary much).

# Answer
> 2 votes
### GolfScript, 90 characters

```
+:q;:f[]*:^[]:r\{.,{(^3${1=}%-f{2$\?)},~-q{(3$={-.}*;}/{.[[2$\]]4$|3$c;}%;;;}{;:r}if;}:c~r

```

The program does a simple recursive search on the names. It actually calculates all possible lists but saves them to a variable for output, so only the last one is returned.

The input/output is on the interpreter stack (first families then two previous years\` assignments), e.g.

```
#PREPARE INPUT
;
[["John" "Anna"]["Mark" "James"]["Elizabeth" "Daniel" "Isabelle"]["Ryan" "Ruth"]]
[["Ruth" "John"] ["Ryan" "Daniel"] ["Isabelle" "Mark"] ["Daniel" "Anna"] ["Elizabeth" "James"] ["James" "Elizabeth"] ["Mark" "Ryan"] ["Anna" "Isabelle"] ["John" "Ruth"]]
[["Ruth" "Anna"] ["Ryan" "Elizabeth"] ["Isabelle" "John"] ["Daniel" "James"] ["Elizabeth" "Mark"] ["James" "Daniel"] ["Mark" "Isabelle"] ["Anna" "Ruth"] ["John" "Ryan"]]

#PROGRAM
+:q;:f[]*:^[]:r\{.,{(^3${1=}%-f {2$\?)},~-q{(3$={-.}*;}/{.[[2$\]]4$|3$c;}%;;;}{;:r}if;}:c~r

#SHOW OUTPUT
p

```

prints the output

```
[["Ruth" "Elizabeth"] ["Ryan" "John"] ["Isabelle" "James"] ["Daniel" "Mark"] ["Elizabeth" "Anna"] ["James" "Ruth"] ["Mark" "Daniel"] ["Anna" "Ryan"] ["John" "Isabelle"]]

```

---
Tags: code-golf
---


# Question
Title: Implement Two-Layer Perceptron Algorithm
Train a two-layer perceptron. You will find the Wikipedia article and these lecture slides useful.

Use a sigmoid activation function for both the hidden and output layers, $$\sigma(x) = \frac{1}{1 + e^{-x}}$$

Your function should take in a list or array of input/output pairs and an integer specifying how many training passes through the input set to make. Both the input and output will be vectors of any convenient representation in your language. You should output or otherwise initialize a classifier function or object.

Initialize the weights randomly and to prevent overflow/underflow, normalize the weight vectors after each update.

You should handle input data vectors up to 1000 dimensions and at least 10 output dimensions. The classifier function should return a vector of the activation levels of each of the outputs.

You may assume access to implementations of all of the BLAS routines.

The MNIST database has a very large training and test set you might find useful for testing purposes.

**EDIT:** Example dataset.

Input and output vectors (input).

```
Input  Output
[0,0]   [0]
[0,1]   [1]
[1,0]   [1]
[1,1]   [0]

```

Your program should produce a classifier that takes in a vector of two elements and returns a vector of one element that has similar behavior as the input.

# Answer
I'm going to cheat here, hence community wiki: instead of logistic sigmoid, I'll use the hyperbolic tangent and instead of backprop, I'll use ELM to train the perceptron. Here's the version for XOR, in Python, using BLAS via SciPy.

```
import numpy as np
from scipy.linalg import pinv2

n_hidden = 10  # hyperparameter

# Training set
X_train = np.array([[0,0], [0,1], [1,0], [1,1]])
y_train = [0, 1, 1, 0]

# set hidden layer parameters randomly
w = np.random.randn(X_train.shape[1], n_hidden)
b = np.random.randn(n_hidden)

# compute hidden layer activation
H = np.tanh(np.dot(X_train, w) + b)

# fit output layer parameters
beta = np.dot(pinv2(H), np.atleast_2d(y_train).T)

# prediction and evaluation
pred_train = (np.dot(H, beta) > .5).ravel()
print "Training set accuracy:", np.mean(pred_train == y_train)

```

I previously published a digits classification script using this algorithm. After removing comments, this is 11 lines of code @ 425 characters.
> 2 votes

---
Tags: code-golf
---


title: Box Blur Challenge

text:
# Question
Title: Box Blur Challenge
The challenge is to implement a box blur in any language. The input will be as a 32-bit uncompressed bitmap, BGRA, preceded by one byte defining the radius of the blur and one byte defining the width of the image. The output should be in the same format as the input (minus the blur radius, of course).

Fastest code wins, and a 50-point bounty to the shortest entry, and another to the "most obfuscated" in my opinion.

# Answer
> 5 votes
eTeX, too many chars

```
\immediate\openout5\jobname.out\let\x\newlinechar\x0\catcode0=12\let\y
\linepenalty\def\ndef#1{\expandafter\edef\csname\the#1\endcsname}\loop
\lccode0\x\lowercase{\ndef\x{^^@}}\ifnum\x<255\advance\x1\repeat\def\R
#1 #2 #3 {\Sr#1 \def\Y{#2}\x=0 \Rl#3????}\def\Rle#1\fi#2\Rc{\fi\Rl#1}
\def\Ry#1#2{\ndef{\y;\the\x.#1}{\number`#2 }}\def\Rc#1#2#3#4{\ifnum\Y=
\y\Rle#1#2#3#4\fi\advance\y1 \Ry1#1\Ry2#2\Ry3#3\Ry4#4\Rc}\def\Re{\fi\x
-1\immediate\write5{\Bl1;1.!}\end}\def\Rl#1{\edef\X{\the\x}\advance\x1
\y0 \ifx?#1\Re\fi\Rc#1}\def\Bl#1;{\ifnum\X<#1 \Ble\fi\Bc#1;}\def\Ble
#1!{\fi}\def\Bc#1;#2.{\ifnum\Y<#2 \Bce\fi\By#1;#2.1\By#1;#2.2\By
#1;#2.3\By#1;#2.4\expandafter\Bc\number#1\expandafter;\the\numexpr
#2+1.}\def\Bce#1#2#3;{#1\expandafter\Bl\the\numexpr#3+1;1.}\def\Sr#1
{\x-#1\def~{}\Sl#1 \edef~{\def\noexpand\By####1;####2.####3{\noexpand
\csname\noexpand\the\numexpr(\unexpanded\expandafter{~}+0)/(\unexpanded
{\Bt\X}#1 ####1 *\unexpanded{\Bt\Y}#1 ####2 )\endcsname}}~}\def\Sl#1
{\ifnum#1<\x\else\y-#1 \Sc#1 \advance\x1 \Sl#1 \fi}\def\Sc#1 {\ifnum
#1<\y\else\edef~{\unexpanded\expandafter{~}\unexpanded{\expandafter\t
\csname\the}\numexpr####2+\the\x;\noexpand\the\numexpr####1+\the\y
.####3\endcsname}\advance\y1 \Sc#1 \fi}\def\t#1{\ifx\relax#1\else+#1\fi
}\def\Bt#1#2 #3 {\expandafter\use\the\numexpr(\ifnum#2<#3 1+#2\else
#3\fi+\ifnum\numexpr#2+#3>#1 #1-#3\else#2\fi);}\def\use#1;{#1}
\expandafter\R\noexpand

```

Run as for instance

```
etex filename 10 3 55555555qqqq55555555qqqq5555qqqqqqqq5555qqqqqqqq

```

---
Tags: fastest-code
---


# Question
Title: Doors doors doors, c'mon down to the door store!
## The challenge is twofold:

Make a program that builds a door. *ASCII, HTML or otherwise*

Make the door functional. *Opens and closes*

*Either open-able through input or interaction!*

* Non-functional door +5 points.
* Just a open-able door +10 points.
* Interactive door +15 points.
* Fancy door +20 points. *This means revolving,bifold etc*
* Animated +20 points.
* \<100 characters +50 points.
* -100 points for using a program specifically designed for drawing or animation.

If you have criteria suggestions leave them in the comments.

### Non-functional open door example:

```
<?php
$idiots_in_room=true;

if($idiots_in_room)
{

$count=20;
$count2=7;
for($i=0;$i<$count;$i++)
{

if($i==0)
{
echo str_repeat("-",10);
if($i==0){echo ".";}
echo "\n";
}
elseif($i==9)
{
echo str_repeat("-",10);
echo str_repeat("Â ",7)."o"."|";
echo "\n";
}
elseif($i<=9)
{

echo str_repeat("-",1).str_repeat("Â ",8).str_repeat("-",1);

echo ($i<5) ? str_repeat("Â ",$i*2)."\\" : str_repeat("Â ",8)."|";
echo "\n";
}
elseif($i<=14)
{
if($i>9){echo str_repeat("Â ",$i)."\\";}
echo str_repeat("Â ",$count2--)."|";
echo "\n";
}

}
}

```

### Example Output:

```
----------.
-        -  \
-        -    \
-        -      \
-        -        \
-        -        |
-        -        |
-        -        |
-        -        |
----------       o|
          \       |
           \      |
            \     |
             \    |
              \   |

```

# Answer
> 21 votes
### JavaScript, 4380 characters, 65(?) points

ASCII? Check. HTML? Check. Is a door? Check. Openable door? Check. Interactive? Check. Fancy? Double doors with properly positioned hinges, I hope that counts. Animated? Check. Under 100 characters? Ha. Not using facilities intended for drawing? Check.

Live demo. (Note: In my testing with Firefox, clicking the doors more than once doesn't work — for some reason the event handler doesn't fire again and I'm baffled as to why; pointing out what I did wrong would be welcome. Though, you might want to run this in Chrome anyway for decent JS performance.)

```
<title>Door</title>
<pre onmouseup="turn();" style="display: table; margin: auto; font-family: 'Monaco', monospace; font-size: 0.6em; line-height: 0.7em;">
</pre>
<p>Click doors to open or close.</p>
<script>

  // Appearance of hit surface - global used to avoid allocating a record to return
  var mat;

  // Scene construction tools
  function box(size,ms) {
    return function (x, y, z) {
      var vdist0 = Math.abs(x) - size[0];
      var vdist1 = Math.abs(y) - size[1];
      var vdist2 = Math.abs(z) - size[2];
      mat = vdist0 > vdist1 && vdist0 > vdist2 ? ms[0] :
            vdist1 > vdist0 && vdist1 > vdist2 ? ms[1] :
            ms[2];
      return Math.max(vdist0, vdist1, vdist2);
    };
  }
  function translate(vec, obj) {
    var dx = vec[0];
    var dy = vec[1];
    var dz = vec[2];
    return function (x, y, z) { return obj(x - dx, y - dy, z - dz); };
  }
  function mirror(obj) {
    return function (x, y, z) { return obj(-x, y, z); };
  }
  function spin(obj) {
    return function (x, y, z) {
      var a = Date.now() / 1000;
      var s = Math.sin(a);
      var c = Math.cos(a);
      return obj(
        x * c + z * s,
        y,
        x * -s + z * c
      );
    };
  }
  function doorturn(obj) {
    return function (x, y, z) {
      var a = pos;
      var s = Math.sin(a);
      var c = Math.cos(a);
      return obj(
        x * c + z * s,
        y,
        x * -s + z * c
      );
    };
  }
  function rotx(a, obj) {
    return function (x, y, z) {
      var s = Math.sin(a);
      var c = Math.cos(a);
      return obj(
        x,
        y * c + z * s,
        y * -s + z * c
      );
    };
  }
  function roty(a, obj) {
    return function (x, y, z) {
      var s = Math.sin(a);
      var c = Math.cos(a);
      return obj(
        x * c + z * s,
        y,
        x * -s + z * c
      );
    };
  }
  function union(as, bs) {
    return function (x, y, z) {
      var a = as(x, y, z); var am = mat;
      var b = bs(x, y, z);
      if (a < b) {
        mat = am;
        return a;
      } else {
        return b;
      }
    };
  }

  // Display parameters
  var vw = 80, vh = 80;
  var timestep = 1/30;

  // Scene
  var wallhwidth = 30;
  var wallhheight = 35;
  var wallmat = [";", "\u2014", ":"];
  var dhwidth = 10;
  var dhheight = 20;
  var hthick = 2;
  var door = translate([-dhwidth*2, 0, 0], doorturn(translate([hthick, 0, dhwidth], box([hthick, dhheight, dhwidth], [".", "\u2014", "|"]))));
  var doors = union(door, mirror(door));
  var wall = union(
    union(
      translate([dhwidth*2+wallhwidth, 0, -hthick], box([wallhwidth, wallhheight, hthick], wallmat)),
      translate([-dhwidth*2-wallhwidth, 0, -hthick], box([wallhwidth, wallhheight, hthick], wallmat))),
    translate([0, wallhheight-(wallhheight-dhheight)/2, -hthick], box([dhwidth*2, (wallhheight-dhheight)/2, hthick], wallmat)));
  var floor = translate([0, -dhheight - 1.1, 0], box([100, 1, 100], ["/","/","/"]));
  var sill = translate([0, -dhheight - 1, -hthick], box([dhwidth*2, 1, hthick], ["\\","%","\\"]));
  var sbox = translate([0, 0, -12], spin(box([8, 8, 8], ["x", "y", "z"])))
  var scene = union(sbox, union(union(wall, doors), union(floor, sill)));
  var view = translate([vw/2, vh/2, -100], rotx(0.2, roty(-0.6, scene)));

  // Animation state
  var pos = -Math.PI/2;
  var dpos = 0;
  var interval;

  // Main loop function
  function r() {
    // Update state
    pos += dpos * timestep;
    if (Math.abs(pos) >= Math.PI/2) {
      dpos = 0;
      pos = Math.PI/2 * pos / Math.abs(pos);
      if (pos < 0) { // no animation needed
        clearInterval(interval); interval = undefined;
      }
    }

    // Render scene
    var t = [];
    for (var y = vh - 1; y >= 0; y--) {
      for (var x = 0; x < vw; x++) {
        var z = 0, distance;
        while ((distance = view(x,y,z)) > 0.12) {
          z -= distance;
          if (!isFinite(z) || z < -1000) {
            mat = " ";
            break;
          }
        }
        t.push(mat);
      }
      t.push("\n");
    }
    document.getElementsByTagName("pre")[0].textContent = t.join("");
  }

  // Click handler
  function turn() {
    if (dpos !== 0) {
      dpos *= -1;
    } else {
      dpos = (pos < 0 ? 1 : -1) * 2.3;
    }
    if (!interval) {
      interval = setInterval(r, timestep*1000);
    }
  }

  // Render initial state
  r();
</script>

```

When closed, the doors look like this:

# Answer
> 9 votes
# HTML & CSS3, 55 points

Fancy, interactive, animated door is 55 points, I think.

Yes, this opens like any other door, but if a sliding door counts as fancy, why doesn't a rotating one? If a rotating one isn't fancy, well, a sliding door is no problem `:)`

A demo is available at http://result.dabblet.com/gist/3132160/ac475112dbba493d2dd7d98493d4f4ceaa209a7c. Click the doorknob to open and close. No JavaScript involved; it's just the magic of CSS3.

```
#wall {
    background-color: #eee;
    bottom: 0;
    left: 0;
    position: absolute;
    right: 0;
    top: 0;
    transform: rotateX(-10deg);
    transform-origin: 0 100%;
    transform-style: preserve-3d;
}

#door-container {
    background-color: black;
    height: 100%;
    margin: 0 auto;
    width: 300px;
}

#door {
    background-color: brown;
    height: 100%;
    margin: auto;
    position: relative;
    transform-origin: 0 0;
    transition: transform 0.5s ease;
    width: 300px;
}

#door .knob {
    background-color: gold;
    border-radius: 10px;
    height: 20px;
    margin-top: -10px;
    position: absolute;
    right: 10px;
    top: 50%;
    width: 20px;
}

#open:target + #wall #door {
    transform: rotateY(-145deg);
}

#open:target + #wall #open-link {
    display: none;
}

#close-link {
    display: none;
}

#open:target + #wall #close-link {
    display: inline;
}

```

```
<span id="open"></span>
<div id="wall">
    <div id="door-container">
        <div id="door">
            <a href="#open" id="open-link" class="knob"></a>
            <a href="#closed" id="close-link" class="knob"></a>
        </div>
    </div>
</div>

```

# Answer
> 6 votes
# Mathematica 271 chars

```
Manipulate[a = {0, 0, 0}; b = {0, 0, h}; p = Polygon; c = Cuboid; t = Rotate;Graphics3D[{c@{{-w - 1, 0, 0}, {-w, 1, h}}, c@{{w + 1, 0, 0}, {w, 1, h}},t[p@{a, b, {-w, 0, h}, {-w, 0, 0}}, r, {0, 0, 1}, {- 2 w/3, -w/3, 0}], t[p@{a, b, {w, 0, h}, {w, 0, 0}}, -r, {0, 0, 1}, { 2 w/3, -w/3, 0}]}],{{r, 0}, 0, 3/2}, {{w, 2}, 1, 3}, {{h, 4}, 3, 5}]

```

The double doors

* open by rotation from zero to 90 degrees (using the slider `r`)
* can be have their height and width set by sliders (`h` and `w`).
* are in a 3D lighting environment
* can be interactively rotated to be viewed from different angles.

---

The code is based on a program by Sándor Kabal.

# Answer
> 4 votes
# Python - 65 points, 86 chars

Interactive and less than 100 chars.

Waits for input and *shows you the door*. Valid input is "open" and "close" and "bye".

```
g,s=1,'open close'
while g:
 i=raw_input()
 print '_'+'/_ '[s.find(i)/5]+'_'
 g=i in s

```

# Answer
> 4 votes
# Mathematica 127 chars

This is a more streamlined implementation than the one I submitted earlier. It has a single door. The single door

* opens by rotation from zero to 90 degrees (using the slider `o`)
* is in a 3D lighting environment
* can be interactively rotated to be viewed from different angles.

However, it uses a fixed door height and width.

```
Manipulate[a = {0, 0, 0}; Graphics3D[{Tube[{a, {1, 0, 0}, {1, 0, 2}, {0, 0, 2}, a}, .03],Rotate[Cuboid@{a, {1, -.1, 2}}, o, {0, 0, 1}, a]}], {o, 0, -Pi/2}]

```

---
Tags: code-challenge
---