# Question
Title: Reduce the amount of loops when finding if an element is stored only once in the array?
I was amazed to find that there is a way to reduce the times you loop on an array to find if a element is contained once.

One would think that the only way would be to loop through the whole array, and increasing a variable every time you find a match, and then check if it is equal to 1. However, lets look at this JavaScript code:

```
function isOnce(itm,arr){
    var first_match=-1;
    for(var i=0,len=arr.length;i<len;i++){
        if(arr[i]===itm){
            first_match=i;
            break;
        }
    }
    if(first_match!=-1){
        var last_match=-1;
        for(i=arr.length-1;i>first_match;i--){
            if(arr[i]===itm){
                last_match=i;
                break;
            }
        }
        if(last_match==-1){
            return true;
        }
    }
    return false;
}

```

It can reduce the times you loop when these two points met:

* There are 2 or more matches
* The first and last match are at least 1 space apart

so, `arr=["a", ...(thousands of items here)... ,"a"]; //we only looped 2 times`

I was wondering if there are other ways to reduce the looping in \*certain cases.

\*There are obviously some cases that one will need to loop through every item on these worst-case scenarios. So it might not work all the time.

# Answer
D

```
bool containsOnce(E,R)(R haystack,E needle){
     bool foundOnce=false;
     foreach(e;haystack){
          if(e==needle){
              if(foundOnce)return false;
              foundOnce=true;
          }
     }
     return foundOnce;
}

```

this is pretty much the best case on unsorted data, you loop until you find a match and then set a flag to true and continue looping, when you find the second match return false immediately, when you looped over the entire thing return state of the flag

this has better timebounds when the double match is found near the beginning of the array (and in general when the items are close together) (but is better in a code-golf contest ;) )

in interest of time bound you'll remain at O(n) regardless on any algorithm (sometimes there simply are no improvements possible except with micro-optimizations). as finding a single match (a subproblem of the current problem) in an unsorted array is O(n)
> 3 votes

---
Tags: optimization, array
---


# Question
Title: Convert __DATE__-style string to sortable string
Goal is to write the shortest possible C89 and C99-compliant single-module C program which will compute and print out a single-line string whose sort order will correspond with the date given by the predefined `__DATE__` macro (in other words, later dates will yield later-sorting strings). The programmer is free to arbitrarily select the mapping between dates and strings, but every entry should specify the mapping and it should be obvious that it will sort correctly (e.g. a programmer could decide to compute (day + month\*73 + year\*4129) and output that as a number, though it's likely that particular encoding would probably require a longer program than some others).

The program should yield identical results on any standards-compliant compiler on which 'int' is 32 bits or larger and both source and target character sets are 7-bit ASCII, and should not rely upon any implementation-defined or undefined behavior nor print any characters outside the 32-126 range except for a single newline at the end. The program should contain the following aspects indicated below (replacing *«CODE»* with anything desired):

```
♯include <stdio.h>
*«CODE»*int main(void){*«CODE»*}

```

All output shall be produced by the `printf` at the end (i.e. the correct value will be in an `int` called `z`). The required elements will be included in the character total for each entry.

Code should operate correctly for all future dates through `Dec 31 9999`. Libraries which are standard in both C89 and C99 may be used, provided that appropriate headers are included. Note that standard date libraries may not be assumed to operate beyond the Unix limits.

Note: Code is permitted to perform Undefined Behavior if and only if the `__DATE__` macro expands to a macro other than a date between `Feb 11 2012` and `Dec 31 9999` (expressed in that format, using C-standard abbreviated English month names Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec)

Note 2: For compliance with C99 standards, 'main' should return an arbitrary, but defined value, and the newline is required. The first requirement, btw, adds 7 characters to my best effort; the single new-line adds 5.

# Answer
## C, 137 184 184 140 120 106 103 characters

Replaced the month name lookup with a magic formula.
The formula `(m[1]*4388^m[2]*7)%252` is ascending for month names.
Changed it to nicely return 0, at no cost.
It no longer prints a number. Instead it prints a string, which should sort right.
Implemented supercat's `%*s` idea, which inserts more spaces for earlier months, along with a function that's descending for month names - `(m[1]*29^m[2]+405)%49`.

```
#include<stdio.h>
int main(void){
    char*m=__DATE__"%*.6s\n"+1;
    return!printf(m+6,(*m*29^m[1]+405)%49,m);
}

```

I thought single digit days are represented as `Jan_1_2012` (`_` being a space), when in fact it's `Jan__1_2012` (extra space). This complicated things, so my previous versions were more complicated:

```
#include<stdio.h>
int main(void){
    char*m=__DATE__+1,*t=m+m[4]/16;
    return!printf("%s%3d%s\n",t+3,(*m*4388^m[1]*7)%252,t);
}

```
> 3 votes

# Answer
## C, 194 characters

```
#include <stdio.h>
#include <string.h>
d,y,n[3];
int main(void)
{
sscanf(__DATE__,"%s %d %d",n,&d,&y);
return printf("%d%02d%02d",y,13-strlen(strstr("JanFebMarAprMayJunJulAugSepOctNovDec",n))/3,d);
}

```

I think most of the newlines are unnecessary, but I've left them in for readability.

Not sure what your feelings are about compiler warnings - this throws a few but runs fine. Also not sure whether the declarations with no type are valid C89 or not.
> 1 votes

# Answer
Here are the solutions that I had come up with (for brevity, I'm just writing the `#include` line once--copy and paste as needed to assemble a testable program).

```
(my entries)
#include <stdio.h>
int main(void){char*d=__DATE__"%s%sDFCwu-vBxE-t%c"+1;return printf(d+6,d+(*d+d[1])%17+9,d,10);}
int main(void){char*d="h-elbj-ikcfdga-"__DATE__+16;return printf("%s%s\n",d+6,d-(*d+d[1])%17);}
int main(void){char*d=__DATE__+1;return printf("%s%x%s\n",d+6,3**d+"![ WT -#[ 8"[d[1]%12],d);}
int main(void){char*d=__DATE__"%x%.5s\n"+1;return printf(d+6,3**d+"![ WT -#[ 8"[d[1]%12],d);}
int main(void){char*d=__DATE__"%x%.5s\n";return printf(d+7,d[1]+"1C0EB042E0:"[d[2]%12],d);}
(ugoren's entry, golfed, for comparison, and adding .5 to the %s format specifier)
int main(void){char*m=__DATE__"%3d%.5s\n"+1;return!printf(m+6,(*m*803^m[1]*95)%94,m);}

```

My initial approaches made use of a month-to-number approach which can turn each month into an arbitrary character. If in a production embedded-systems environment one had to turn an alphabetic month into a number 1-12, the approach might actually be an efficient algorithm to do so (perhaps using repeated subtract-17 instead of mod, if no other divisions are required).

Allowing the computation to return values which were sortable but not consecutive made it possible to use a smaller table indexed using the third character of the month, and add to that character the second. A further savings was achieved by realizing that the multiplication by three I'd used to facilitate "tiebreaking" was in fact not needed, since the months which would otherwise yield matching hash values were correctly sortable by their first character.

I tried quite a few variations, but nothing came close to the operator combination that ugoren found, which don't require any table. I was also impressed by his entry which would have accommodated single-digit dates without padding, which would have been a challenge in its own right, and one which I doubt that I could have handled as nicely.
> 1 votes

# Answer
## C, 163 characters

A different approach from my other solution.
I can save 13 characters by making `t` an int array, and relying on the internal layout of `struct tm`. But I guess it violates the rules.

```
#define _XOPEN_SOURCE
#include<time.h>
#include<stdio.h>
int main(void){
    struct tm t;
    strptime(__DATE__,"%b%d%Y",&t);
    return printf("%d\n",t.tm_year*366+t.tm_yday);
}

```
> 0 votes

---
Tags: code-golf, date, c
---


title: Busy Brain Beaver

text:
# Question
Title: Busy Brain Beaver
Write a brainfuck program of no more than 256 characters that takes as many steps as possible, but does not loop infinitely. The program may not take any input.

More specifically:

* Assume an infinite number of cells to the right.
* A `<` when at the leftmost cell does nothing.
* A `-` when cell value is zero sets cell to `255`.
* The instructions `+-<>.` all count as one step when executed.
* When a `[` or `]` is encountered, it counts as one step. However, if the condition is true and control flow jumps, the corresponding `]` or `[` does **not** again count as a step.
* The solution that takes the most steps wins.
* If there is some kind of pattern in your solution, giving a function for how many steps a similar program of length `n` would take is appreciated but not mandatory.
* To count instructions, you can use this modified interpreter:

Example:

```
++[-]

```

The encountered instructions are `++[-]-]`, and the program ran for 7 steps.

# Answer
Here's a 41-character program that eventually halts, leaving more than 10↑(10↑28) contiguous cells set equal to 1 (so the number of instructions executed is very much greater than that):

```
>+>+>+>+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]

```

If I'm not mistaken, that's a correct translation of the following program in the BF-variant language that uses a single bit for each memory cell (i.e., cell content 0..1 instead of 0..255, so '+' acts to simply flip the bit-value):

```
>+>+>+>+[+>[>]+[+>[>]+[+>[>]+[<]+<]+<]+<]

```

The exact value (the number of adjacent 1-bits) produced by the latter program is

```
3 * (2 ↑ 118842243771396506390315925503 - 1) + 1.

```

---

The above program initializes & computes a function that grows like 2↑↑x (in Knuth up-arrow notation). Similar conversion of a variant-BF program that initializes & computes a function that grows like 2↑23x provides the following 256-character program:
```
>+>+>+>+>+>+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[->[>]+[<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+<]+

```

which eventually halts, leaving more than 2↑236 adjacent cells set equal to 1 (so the number of steps is enormously more than that).

**NB-1**: 2↑236 is an "inconceivably large" number; e.g., even 2↑46 = 2↑↑↑↑6 already surpasses the first term (3↑↑↑↑3) in the sequence used to compute Graham's number.

**NB-2**: I think it's likely that 256 characters is enough for a BF program to initialize & compute a function with output *much larger than Graham's number* — if I find time, maybe I'll try to write one.

**NB-3**: In case anyone is interested in the origin of the above programs, here are some programming resources for "Brainf\*ck F", with various programs written in Python. ("Brainf\*ck F", or just "F", is what I called a Turing-complete variant of the Smallf\*ck esolanguage.) I just now uploaded these files, which have been offline for several years, and for now the linked webpage is just a "file cabinet" -- see the file Busy\_Beavers.txt for a detailed discussion relevant to the above programs.
> 17 votes

# Answer
Here is a nice 39 character one:

```
-[>-[>-[-[>+<-]<[>+<-]<[>+<-]>>>]<-]<-]

```

It basically makes a 3 space wide 'sled' that it moves right and decrements by one. Completed in 31,919,535,558 instructions, with the innermost loop executing 256^3 times. I still have plenty of room to extend this pretty far at a rate of 14 characters to another order of magnitude to the run time.

Works on any interpreter with unbounded memory, or with wrapping memory.

I leave it a an exercise to the reader to determine when the improved by 2 loops version will finish:

```
-[>-[>-[>-[>-[-[>+<-]<[>+<-]<[>+<-]<[>+<-]<[>+<-]>>>>>]<-]<-]<-]<-]

```

It has now run overnight, and it is over 3,000,000,000 steps. Still has not gotten through a single iteration of the outer loop. Has barely made it through 15% of the second loop.
> 10 votes

# Answer
This programs works in infinte number of cells. Two values are initialized in the begining with ascii values 255. The first value at the first rotation of main loop is splited to 255 cell and they are initialized with 255 each, at the second rotation of main loop the each value in 255 cells again splits up to 255\*255 cells, in the same way for 255 rotation of main loop the total cells initialized will be 255^255 . The second value determines how much times the main loop is to be repeated.

```
>->>-[<<[<]>[[[>]>>>[>]-[<]<<<[<]>-]>]>[>>[>]>+<<[<]<-]>>[>]>-]

```
> 2 votes

# Answer
This program is almost same as my previous program , difference is that the value determining the outer loop remains fixed in a particular cell so both number of cells initialized and total steps at the end of the program can be increased

```
->>-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]

```

cells initialized at the end of program 255^255

```
-[>-[>->>[-]-<<[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<-]<-]

```

cells initialized at the end of program 255^255^3

I further modified it to run for even more number of steps.

```
->>>->>-<<<<<[>>>[>]<[[>>[>]<[[>>[>]-[<]<-]>>[[<+>-]>]<<[<]<]>>[[<+>-]>]<<[<]<-]<[>>>[[<+>-]>]<<[<]]<]>>>>[[<<+>>-]>]<-<<[<]<<-]

```

it initializes 255^255 cells during first rotation of main 255^(255^255\*255) cells during second rotation of main loop 255^{255^(255^255\*255)\*255} cells during third rotation of main loop in this way loop repeats 255 times
> 2 votes

---
Tags: code-challenge, brainfuck, busy-beaver
---


title: Lowest unique bid auction

text:
# Question
Title: Lowest unique bid auction
> **Thanks for all the entries, the deadline has now passed and the final scores are at the end of the question.**
> **Congratulations to PhiNotPi on a fairly comprehensive victory.**

This is a challenge, the aim of which is to create a program which wins more often than any of its opponents in a lowest unique bid auction.

## Input

As input the program will receive all the previous rounds' bidding, one round per line, all bids separated by spaces as follows:

```
10 4 12 11 12 4 7 3 3
1 2 9 15 1 15 15 9 3
3 21 6 4 3 8 6 13 1

```

Each column of the input represents the bidding of one bot. The first column is the receiving program's bids, while the rest are in a randomly generated order. Thanks to hammar and Peter Taylor for their input.

Input is provided as the one and only command-line (multi-line) argument to your program:

```
./test1 '1 2
3 4
5 6
1 2'

```

This means that your program will need to be runnable from the command-line. Please give an example of invocation as part of your answer.

**In the first round only** as a means of letting you know how many bots you're up against, the input will be a line of `0`s - one for each bot.

## Output

Your program should output its bid as an integer in the range 1 to 100 (inclusive).

## Scorer Program

This is my scoring program - any suggestions for additions, improvements or bug fixes would be welcomed.

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

#define NUMROUNDS 10
#define NUMBOTS 4
#define MAXINPUTSIZE 10000
#define MAXFILENAMESIZE 100

int main()
{
    int i,j,a,b,winner;
    FILE *fp;
    char bots[NUMBOTS][MAXFILENAMESIZE]={"onesconfident","random100","random20","random5"};
    char openstring[MAXFILENAMESIZE+MAXINPUTSIZE+3];
    char input[MAXINPUTSIZE];
    char buff[5];
    int shuffle[NUMBOTS],auction[100],lowestbid[NUMBOTS]={[0 ... NUMBOTS-1]=101};
    static int guesses[NUMBOTS][NUMROUNDS];
    static int scores[NUMBOTS],totalwinbids[NUMBOTS];

    srand(time(NULL));

    for(i=0;i<NUMROUNDS;i++)
    {
        /*blank the auction bids for the next round */
        for(a=0;a<100;a++)
        {
            auction[a]=9999;
        }

        /*loop through the bots sending the input and storing their output */
        for(j=0;j<NUMBOTS;j++)
        {
            /*Fisher-Yates shuffle */
            for(b=0;b<NUMBOTS;b++)
            {
                shuffle[b]=(b+j)%NUMBOTS;/*put current bot at index 0 */
            }
            for(b=NUMBOTS-1;b>1;b--)
            {
                int z=rand()%(b-1)+1;/*make sure shuffle leaves index 0 alone */
                int t=shuffle[b];
                shuffle[b]=shuffle[z];
                shuffle[z]=t;
            }

            /*generate the input for the bots */
            strcpy(input,"'");
            if(i==0)
            {
                for(b=0;b<NUMBOTS;b++)
                {
                    if(b!=0)
                        sprintf(input,"%s 0",input);
                    else
                        sprintf(input,"%s0",input);
                }
            }
            else
            {
                for(a=0;a<i;a++)
                {
                    for(b=0;b<NUMBOTS;b++)
                    {
                        if(b!=0)
                            sprintf(input,"%s %d",input,guesses[shuffle[b]][a]);
                        else
                            sprintf(input,"%s%d",input,guesses[shuffle[b]][a]);
                    }
                    if(a!=i-1)
                        strcat(input,"\n");
                }
            }
            strcat(input,"'");

            sprintf(openstring,"%s %s",bots[j],input);
            fp=popen(openstring,"r");

            fgets(buff,3,fp);
            fflush(NULL);
            pclose(fp);
            guesses[j][i]=atoi(buff);

            /*add the bid to the auction, eliminating any duplicates */
            if(auction[atoi(buff)-1]!=9999)
                auction[atoi(buff)-1]=9998;
            else
                auction[atoi(buff)-1]=j;
        }

        winner=9999;
        /*add one to the score of the winning bot */
        for(a=0;a<100;a++)
        {
            if(auction[a]!=9998 && auction[a]!=9999)
            {
                winner=auction[a];
                scores[winner]+=1;
                totalwinbids[winner]+=guesses[winner][i];
                if(guesses[winner][i]<lowestbid[winner])
                    lowestbid[winner]=guesses[winner][i];
                break;
            }
        }

        /*output this round's bids and the winning bot's name */
        strcpy(input,"");
        for(b=0;b<NUMBOTS;b++)
        {
            if(strcmp(input,"")!=0)
                sprintf(input,"%s %d",input,guesses[b][i]);
            else
                sprintf(input,"%d",guesses[b][i]);
        }
        if(winner!=9999)
            printf("%s %s\n",input,bots[winner]);
        else
            printf("%s No winner\n",input);
    }

    /*output final scores */
    printf("\nResults:\n");
    printf("Bot\tScore\tTotal\tLowest\n");
    for(a=0;a<NUMBOTS;a++)
    {
        printf("%s\t%d\t%d\t%d\n",bots[a],scores[a],totalwinbids[a],lowestbid[a]);
    }

    return 0;
}

```

## Test players

**One's confident** Always bids 1.

```
#include <stdio.h>

int main()
{
    printf("1");
    return 0;
}

```

**Random100** Bids at random over the entire range

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

int main()
{
    srand(getpid());
    printf("%d",rand()%100+1);
    return 0;
}

```

**Random20** Bids at random between 1 and 20

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

int main()
{
    srand(getpid());
    printf("%d",rand()%20+1);
    return 0;
}

```

**Random5** Bids at random between 1 and 5

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

int main()
{
    srand(getpid());
    printf("%d",rand()%5+1);
    return 0;
}

```

Example run-through:

```
1 38 5 2 onesconfident
1 66 13 5 onesconfident
1 94 1 3 random5
1 22 9 1 random20
1 50 17 4 onesconfident
1 78 5 2 onesconfident
1 6 13 5 onesconfident
1 34 1 3 random5
1 62 9 1 random20
1 90 17 4 onesconfident

Results:
Bot Score   Total   Lowest
onesconfident   6   6   1
random100   0   0   101
random20    2   18  9
random5 2   6   3

```

These players are for testing purposes only. They will NOT be included in the competition. You can enter as many bots as you wish, so if anyone does enter a bot that only guesses `1`, you can enter another that does the same to render it useless.

## Winner

The winning bot in each round is the one which gives the lowest *unique* bid. So given a round in which the following bids are made: `1 1 3 5 2 3 6 3 2 8 7` the winner would be the bot that bid `5` because the `1`s, `2`s and `3`s are not unique.

The winner of the competition will be the program which wins the most times after 100 rounds. In case of a tie the total of the winning bids will be used as a tie-breaker, and in the event of that also being a tie, the lowest winning bid will be used as a further tie-breaker. These scoring factors are all output by the scoring program.

I will run the scoring program on all working programs that have been entered 2 weeks from today (18th February **now extended to 11pm(GMT) on the 20th of February**). I'll upvote all working entries and accept the winner of my scoring run.

**Final scoring run**

```
1 9 3 2 1 6 4 3 6 8 7 10 26 6 10 5 26 2 5 8 8 5 7 6 42 1 ./phinotpi2
1 11 4 2 1 4 9 20 6 8 7 6 26 4 8 4 26 2 5 8 8 5 7 7 42 1 ./phinotpi2
1 7 9 2 1 4 3 20 6 8 7 6 7 4 8 9 26 2 5 8 8 5 4 9 42 3 node minitech1.js
1 13 20 2 1 3 3 20 6 8 7 7 9 6 8 20 26 2 5 8 8 5 9 9 42 3 ./dirichlet
1 12 13 2 1 1 3 20 6 8 7 7 9 6 9 13 26 2 5 8 8 5 20 9 42 3 ./dirichlet
1 2 4 2 1 1 3 20 6 8 7 7 9 6 9 12 26 2 5 8 8 5 13 9 42 3 python blazer1.py
1 11 4 2 1 4 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 12 9 42 3 ./celtschk
1 3 4 2 1 1 3 20 6 8 7 6 7 4 8 9 26 2 5 8 8 5 4 9 42 3 node minitech1.js
1 7 4 2 1 1 3 20 6 8 7 9 26 6 7 20 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 9 9 2 1 3 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 20 9 42 10 ./phinotpi2
1 13 4 2 1 3 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 12 20 2 1 1 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./phinotpi2
1 10 3 2 1 2 4 20 6 8 7 6 9 3 9 3 26 2 5 8 8 5 7 9 42 10 ./phinotpi2
1 6 9 2 1 4 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 8 4 2 1 3 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./celtschk
1 2 13 2 1 3 3 20 6 8 7 9 20 6 8 9 26 2 5 8 8 5 7 9 42 10 ruby1.9 strategist.rb
1 2 4 2 1 3 3 20 6 8 7 7 10 6 9 10 26 2 5 8 8 5 9 9 42 10 python blazer1.py
1 3 13 2 1 4 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 10 9 42 10 ./celtschk
1 4 4 2 1 3 3 20 6 8 7 6 7 4 8 9 26 2 5 8 8 5 4 9 42 10 ruby1.9 strategist.rb
1 4 9 2 1 4 3 20 6 8 7 7 9 6 8 10 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 11 7 2 1 1 4 20 6 8 7 6 7 3 8 3 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 6 4 2 1 3 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 13 7 2 1 1 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./phinotpi2
1 7 4 2 1 4 4 20 6 8 7 6 20 3 8 3 26 2 5 8 8 5 7 9 42 10 ./celtschk
1 13 3 2 1 1 4 20 6 8 7 6 7 3 8 9 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 3 4 2 1 3 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 9 9 42 10 ruby1.9 strategist.rb
1 5 4 2 1 2 3 20 6 8 7 6 7 4 8 10 26 2 5 8 8 5 4 9 42 10 ./phinotpi2
1 6 3 2 1 3 4 20 6 8 7 6 7 3 8 3 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 10 20 2 1 1 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 10 3 2 1 4 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./celtschk
1 12 4 2 1 1 3 20 6 8 7 9 20 6 8 9 26 2 5 8 8 5 7 9 42 10 ./phinotpi2
1 5 3 2 1 1 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 13 3 2 1 4 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 6 9 2 1 4 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./phinotpi2
1 5 4 2 1 2 4 20 6 8 7 6 20 3 8 3 26 2 5 8 8 5 7 9 42 10 ./celtschk
1 12 3 2 1 3 4 20 6 8 7 6 7 3 8 9 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 10 7 2 1 2 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 9 10 2 1 4 9 20 6 8 7 4 6 3 8 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 9 20 2 1 4 4 20 6 8 7 6 20 3 8 7 26 2 5 8 8 5 3 9 42 10 ruby1.9 strategist.rb
1 6 3 2 1 3 3 20 6 8 7 9 10 6 9 10 26 2 5 8 8 5 7 9 42 10 node minitech1.js
1 13 3 2 1 3 3 20 6 8 7 7 10 6 8 20 26 2 5 8 8 5 10 9 42 11 ./celtschk
1 3 3 2 1 1 3 20 6 8 7 7 26 6 9 9 26 2 5 8 8 5 20 9 42 11 ruby1.9 strategist.rb
1 5 20 2 1 2 3 20 6 8 7 7 11 6 9 11 26 2 5 8 8 5 9 9 42 11 ./phinotpi2
1 7 3 2 1 4 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 11 9 42 11 node minitech1.js
1 7 3 2 1 1 4 20 6 8 7 6 7 3 8 20 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 8 4 2 1 4 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 20 9 42 10 ./phinotpi2
1 2 3 2 1 3 9 20 6 8 7 4 6 3 8 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 4 13 2 1 3 4 20 6 8 7 6 20 3 7 7 26 2 5 8 8 5 3 9 42 10 ./celtschk
1 8 3 2 1 3 3 20 6 8 7 9 20 6 8 9 26 2 5 8 8 5 7 9 42 10 ruby1.9 strategist.rb
1 9 10 2 1 2 3 20 6 8 7 7 10 6 9 10 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 10 20 2 1 1 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 9 4 2 1 1 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 11 20 2 1 4 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./phinotpi2
1 4 9 2 1 3 4 20 6 8 7 6 9 3 9 3 26 2 5 8 8 5 7 9 42 10 ruby1.9 strategist.rb
1 5 3 2 1 4 4 20 6 8 7 6 7 3 8 10 26 2 5 8 8 5 3 9 42 10 ./celtschk
1 7 4 2 1 3 3 20 6 8 7 7 9 6 8 9 26 2 5 8 8 5 10 9 42 10 python blazer1.py
1 4 9 2 1 1 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 8 4 2 1 3 9 20 6 8 7 4 6 3 8 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 10 9 2 1 3 4 20 6 8 7 6 20 3 8 7 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 4 20 2 1 1 3 20 6 8 7 6 20 4 8 4 26 2 5 8 8 5 7 9 42 10 ./phinotpi2
1 5 3 2 1 2 9 20 6 8 7 4 6 3 9 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 2 4 2 1 1 4 20 6 8 7 6 20 3 8 7 26 2 5 8 8 5 3 9 42 10 ./celtschk
1 10 12 2 1 1 3 20 6 8 7 9 20 6 8 9 26 2 5 8 8 5 7 9 42 10 ./phinotpi2
1 9 4 2 1 4 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 9 9 42 10 ruby1.9 strategist.rb
1 11 3 2 1 3 4 20 6 8 7 6 7 3 8 10 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 8 4 2 1 1 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 13 9 2 1 4 9 20 6 8 7 4 6 3 8 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 2 9 2 1 3 4 20 6 8 7 6 20 3 8 7 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 8 3 2 1 2 3 20 6 8 7 6 20 4 8 4 26 2 5 8 8 5 7 9 42 10 ./celtschk
1 3 3 2 1 4 3 20 6 8 7 6 7 4 8 9 26 2 5 8 8 5 4 9 42 10 ruby1.9 strategist.rb
1 10 4 2 1 1 3 20 6 8 7 7 9 6 8 10 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 3 9 2 1 4 4 20 6 8 7 6 7 3 8 3 26 2 5 8 8 5 10 9 42 10 node minitech1.js
1 7 11 2 1 4 4 20 6 8 7 6 7 3 8 20 26 2 5 8 8 5 3 9 42 10 ./celtschk
1 8 3 2 1 2 3 20 6 8 7 7 9 6 8 9 26 2 5 8 8 5 20 9 42 10 ruby1.9 strategist.rb
1 3 10 2 1 3 3 20 6 8 7 7 10 6 9 10 26 2 5 8 8 5 9 9 42 10 node minitech1.js
1 8 4 2 1 1 3 20 6 8 7 7 10 6 8 20 26 2 5 8 8 5 10 9 42 11 ./phinotpi2
1 2 4 2 1 2 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 20 9 42 11 ruby1.9 strategist.rb
1 4 9 2 1 4 4 20 6 8 7 6 7 3 8 11 26 2 5 8 8 5 3 9 42 11 node minitech1.js
1 4 9 2 1 1 3 20 6 8 7 7 11 6 8 20 26 2 5 8 8 5 11 9 42 10 ./phinotpi2
1 2 7 2 1 1 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 20 9 42 10 ./phinotpi2
1 9 3 2 1 1 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 3 9 2 1 2 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ruby1.9 strategist.rb
1 5 7 2 1 3 3 20 6 8 7 10 20 6 8 10 26 2 5 8 8 5 7 9 42 10 ./celtschk
1 8 10 2 1 4 3 20 6 8 7 7 10 6 9 9 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 5 4 2 1 4 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 9 9 42 10 ruby1.9 strategist.rb
1 5 20 2 1 3 4 20 6 8 7 6 7 3 8 10 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 11 20 2 1 2 3 20 6 8 7 6 7 4 8 4 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 12 10 2 1 1 9 20 6 8 7 4 6 3 9 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 10 3 2 1 1 4 20 6 8 7 6 20 3 8 7 26 2 5 8 8 5 3 9 42 10 ./phinotpi2
1 9 4 2 1 4 3 20 6 8 7 6 20 4 8 4 26 2 5 8 8 5 7 9 42 10 ./phinotpi2
1 5 3 2 1 1 9 20 6 8 7 4 6 3 8 3 26 2 5 8 8 5 4 9 42 10 scala Schwarzenbeck
1 7 4 2 1 1 4 20 6 8 7 6 20 3 7 7 26 2 5 8 8 5 3 9 42 10 ./celtschk
1 11 7 2 1 3 3 20 6 8 7 9 20 6 8 9 26 2 5 8 8 5 7 9 42 10 ruby1.9 strategist.rb
1 13 10 2 1 1 3 20 6 8 7 7 10 6 9 10 26 2 5 8 8 5 9 9 42 10 ./phinotpi2
1 9 9 2 1 1 4 20 6 8 7 6 7 3 9 3 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 7 9 2 1 3 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 ruby1.9 strategist.rb
1 13 7 2 1 4 3 20 6 8 7 6 7 4 8 10 26 2 5 8 8 5 4 9 42 10 ./phinotpi2
1 8 7 2 1 1 4 20 6 8 7 6 7 3 8 3 26 2 5 8 8 5 10 9 42 10 ./phinotpi2
1 12 3 2 1 1 9 20 6 8 7 4 6 3 8 4 26 2 5 8 8 5 3 9 42 10 scala Schwarzenbeck
1 13 7 2 1 2 3 20 6 8 7 6 20 4 8 7 26 2 5 8 8 5 4 9 42 10 ./phinotpi2

Results:
Bot                 Score   Total   Lowest
perl phinotpi1.pl           0   0   101
./dirichlet                 2   25  12
python blazer1.py           3   12  4
perl chef.pl ilmari2.chef   0   0   101
./brainfuck ilmari1.bf      0   0   101
./christophe1               0   0   101
./phinotpi2                 44  156 3
node minitech1.js           7   140 20
scala Mueller               0   0   101
scala Beckenbauer           0   0   101
scala Schwarzenbeck         15  105 7
./alice                     0   0   101
./bob                       0   0   101
./eve                       0   0   101
python joe.py               0   0   101
python copycat.py           0   0   101
python totalbots.py         0   0   101
perl healthinspector.pl     0   0   101
./mellamokb1                0   0   101
./mellamokb2                0   0   101
php eightscancel.php        0   0   101
php fivescancel.php         0   0   101
python copycat2.py          0   0   101
./celtschk                  14  126 9
./deepthought               0   0   101
ruby1.9 strategist.rb       15  152 10

```

# Answer
> 9 votes
## Perl

I tried a little harder this time. It's a really simple complex strategy, but I've set up the framework for expansion.

Edit: Complete redo. This thing is in it for the win.

```
    sub prob{
$_[0]+$_[1]-$_[0]*$_[1]
}

$_=<>;
INPUT:{

tr/ /,/;
@in = eval;
for(1..$#in){
 $bids[$rnum][$in[$_]]++
}
for(0..$#in){
 $tbids[$rnum][$in[$_]]++
}
$rnum++;
$_=<>;
if($_ ne"\n"){redo INPUT}
}

for(0..100){$pre[$_]=0}

dirichlet: for(2..$#in/2+2){    #rough approximation,
$pre[$_]=prob($pre[$_], 1/int($#in/2+1))
}

CDP:{
    @cdps1=(1,1,1,2,2,3,3,4);
    @cdps2=(-2,-1,0,1,1,2,2,3,3);
    for($a=0;$a<8;$a++){
    for($b=0;$b<9;$b++){
     $sum=$cdps1[$a]+$cdps2[$b];
     if($sum<1){$sum=1};
     $pre[$sum] = prob($pre[$sum], 1/72);
    }
    }
}

blazer: {
for($r=1;$r<$rnum;$r++){
winner: for($pnt=1;$pnt<101;$pnt++){
        if($tbids[$r][$pnt] == 1){
            if($pnt > 2){
                $winnum[$pnt]++;
            $wins++;
            }
        last winner
        }
}
    }
    if($wins==0){
    $pre[3]=prob($pre[3], 1);last blazer
    }
    for(1..100){
    $pre[$_]=prob($pre[$_], $winnum[$_]/$wins);
    }
}

CC1: for($pnt=1;$pnt<101;$pnt++){
    if($tbids[$rnum-1][$pnt] == 1){
        $pre[$pnt] = prob($pre[$pnt], 1);last CC1
    }
    if($pnt==100){
        for($pnt2=1;$pnt2<100;$pnt2++){
        $pre[$pnt2] = prob($pre[$pnt2], $tbids[$rnum-1][$pnt2]/($#in+1));
    }
    }
}

CC2: for($pnt=1;$pnt<101;$pnt++){
    if($rnum-2<0){$pre[7] = prob($pre[7], 1);last CC2}
    if($tbids[$rnum-2][$pnt] == 1){
        $pre[$pnt] = prob($pre[$pnt], 1);last CC2
    }
    if($pnt==100){
        $pre[7] = prob($pre[7], 1);last CC2
    }
}

one: {
$pre[1] = prob($pre[1], 1);
}

two: {
$pre[2] = prob($pre[2], 1);
}

five: {
$pre[5] = prob($pre[5], 1);
}

eight: {
$pre[8] = prob($pre[8], 1);
}

fortytwo: {
$pre[42] = prob($pre[42], 1);
}

mueller: {
    $a=($#in+2)/4;
    $pre[int$a]=prob($pre[int$a], 1)
}

schwarzenbeck: {
    $a=($#in+2)/4+1;
    $pre[int$a]=prob($pre[int$a], 1)
}

beckenbauer: {
    $a=($#in+2)/4+2;
    $pre[int$a]=prob($pre[int$a], 1)
}

totalbots: {
    $pre[$#in+1]=prob($pre[$#in+1], 1)
}

joe: {
$sum=0;
    for(1..100){
    $sum+=$tbids[$rnum-1][$_];
}
    $average=$sum/($#in+1);
    if($average==0){$average=10};
    $pre[$average]=prob($pre[$average], 1);
}

node: {
$max=0;$maxloc=0;
for(1..100){
    if($tbids[$rnum-1][$_]>$max){$max=$tbids[$rnum-1][$_];$maxloc=$_}
}
$maxloc--;
#if($maxloc==0){
$maxloc=20;
#}
if($rnum==1){$maxloc=3}
    $pre[$maxloc]=prob($pre[$maxloc], 1);
}
#print"\n@pre\n\n";

decide: for(1..100){if($pre[$_]<0.5){print; last decide}}

```

This program takes input one line at a time, followed by two newlines:

```
perl PhiNotPi2.plx
1 2 3 3 2
2 1 3 1 3
2 1 1 1 3
[empty line]

```

# Answer
> 8 votes
## Chef

Since always betting 1 is now a losing strategy, the obvious thing to do is to always bet *2* instead. So let me do that. To make this otherwise boring entry a little more interesting, I decided to write it in Chef:

```
Shirred Eggs.

This recipe prints the number 2 and, in doing so, yields two delicious
shirred eggs.

Ingredients.
2 eggs

Cooking time: 12 minutes.

Pre-heat oven to 175 degrees Celsius.

Method.
Put eggs into mixing bowl. Pour contents of the mixing bowl into the
baking dish. Shirr the eggs. Bake the eggs until shirred.

Serves 1.

```

As a bonus, the program actually more or less works as a real — if trivial — recipe, even if it does kind of read as if the writer was a bit, um, baked. The Chef grammar seems to make it pretty hard to write anything that involves something more complicated than mixing stuff in a bowl and baking it and still have it work both as a program and as a recipe, especially if any of the verbs one wants to use are even slightly irregular (like "fry" → "fried").

**Edit:** Changed the recipe from fried to shirred eggs — thanks to Blazer for the suggestion! The cooking time and temperature should be considered advisory only; I haven't actually tried the recipe yet myself, so I can't vouch for their accuracy.

# Answer
> 4 votes
## Python (Blazer)

This bot analyzes the previous rounds and records the numbers that win. Winning numbers that appear more often will therefore have a better chance of getting picked. It will then randomly choose numbers from winning numbers (other than 1 or 2). it will choose ~~2~~ 3 instead if it is the first round.

~~Input is read one line at a time. simply enter an empty line to stop accepting input~~

~~A trick is to just paste (it automatically accepts each line with \n within the paste) and hit enter twice~~

You may now just runt the script with a filename in the command line:

```
python bidding.py bidding.txt

```

file should look like this:

```
10 4 12 11 12 4 7 3 3
1 2 9 15 1 15 15 9 3
3 21 6 4 3 8 6 13 1

```

-

```
import random
import sys

winning = [] # record the winning numbers

content = sys.argv[1].split('\n')
for each in content:
    x = map(int, each.split())
    if len(x)+sum(x) == 0:
        continue

    y = []
    for each in x:
        if x.count(each) == 1:
            y.append(each)
    if len(y) > 0:
        if min(y) not in [1,2]:  #never choose 1 or 2
            winning.append(min(y))

# choose an output
if len(winning) == 0:
    print 3
else:
    print random.choice(winning)

```

~~edit: added `or sum(rounds) == 0` to compensate for the recent first-round-all-zeros change~~

edit: problems in comments fixed, also made it able to receive input from a filename, and never chooses '2' anymore since competition has weeded that out as well. works with either all-0's as the starting input or no data in the file at all

edit2: forgot a min()

edit3: changed input to suit question's input needs

# Answer
> 4 votes
## Python (2.6)

Extremely simple, but still I'm curious how it will perform compared to the other approaches.

```
import sys, random
try:
    s = sys.stdin.readlines()[-2]
    m = min(int(x) for x in s.split())
except IndexError:
    m = random.choice([1,1,1,2,2,3,3,4])
a = random.choice([-2,-1,0,1,1,2,2,3,3])
print max(m + a, 1)

```

Just pipe in the bids via stdin, e.g. `python testbid.py < bids.txt`.

*EDIT*: changed for the 'first round all zeros'

*EDIT*: changed the 'magic numbers' a bit (a second time)

# Answer
> 3 votes
### Schwarzenbeck (Scala)

```
object Schwarzenbeck extends App {
  println ((args(0).split('\n')(0).split(' ').length+1)/4+1)
}

```

Schwarzenbeck isn't supposed to score the goals. He is the cleanup for Beckenbauer, which follows soon. :)

To use it, you need a compiler and compile it

```
scalac Schwarzenbeck.scala

```

Then you can run it:

```
scala Schwarzenbeck 'your ar-
gu-
ment'

```

Edit: Further adjustments.

# Answer
> 3 votes
**Strategist (Ruby )**

Implements hundreds of simple strategies: for each round, picks the one which would have won the most previous rounds:

```
require 'Matrix'
def winner guesses
  g=guesses.sort
  while g[0]&&g[0]==g[1]
    g.shift while g[0]==g[1]
    g.shift
  end
  g[0]
end

def prob g
  prob=[0]*100;best=0;n=g.size*(g[0].size-1)
  g.each{|r|r[1..-1].each{|v|prob[v-1]+=1.0/n}};
  prob.map!{|v|v/n}
end

def regression x, y, degree
  return y if x.size==1
  x_data = x.map {|xi| (0..degree).map{|pow| (xi**pow.to_f) }}
  mx = Matrix[*x_data]
  my = Matrix.column_vector y
  begin
    r = ((mx.t * mx).inv * mx.t * my).transpose.to_a[0]
  rescue Exception => e
    r=[0]*degree;r[-1]=y[-1].to_f/(x[-1]**degree)
  end
  r
end

brains=((1..50).map{|w|[proc{|g|w},
    proc{|g|best=0;(p=prob g).each_with_index{|v,i|
      best=i if(v+i/100.0/w)<p[best]};best+1}]}+
  (1..7).map{|w|[proc{|g|p=1; if (g[1]) then h=g[1..-1];x=(1..h.size).to_a
      p=0;regression(x,h.map{|r|winner r},w).each_with_index{|v,i|
      p+=v*(g.size**i)};end;p.to_i},
    proc{|g|b=g[0].size/4;if g[1] then pred=[];h=g[1..-1]
      x=(1..h.size).to_a;h[0].size.times{|i|p=0
      regression(x,h.map{|r|r[i]},w).each_with_index{|v,i|p+=v*((x[-1]+1)**i)}
      pred<<[[p.to_i,1].max,100].min}
      (1..100).each{|i|if !pred.include?(i) then b=i;break;end};end;b}]}+
  (-1..1).map{|w|[proc{|g|r=g[0].size; if g.size>1 then
      f=g[1..-1].flatten;r=(f.inject{|s,v|s+v}/f.size.to_f+w).to_i;end;r},
    proc{|g|r=g[0].size/2; if g.size>1 then
      r=(g[1..-1].inject(0){|s,v|s+winner(v)}/(g.size.to_f-1)+w).to_i;end;r},
    proc{|g|(winner(g[-1])||9)+w}  ]}+
  [proc{|g|b=0;(p=prob g).each_with_index{|v,i|b=i if v<p[b]};b+1}]).flatten

games = ARGV[0].split("\n").map{|l|l.split.map{|v|v.to_i}}
winpct=[0]*brains.size
(games.size-1).times{|round|
  entries=games[round+1].dup
  brains.each_with_index{|b,i|
    entries[0]=pick=[b[games[0..round]],1].max
    winpct[i]+= 1.0/games.size if winner(entries)==pick
  }
}
best=0;
winpct.each_index{|i|best = i if (winpct[i]>winpct[best])}
puts brains[best][games]

```

I'm not sure I've got the input format right - I'm not sure how to generate multi-line command line arguments for testing it on windows. *(This method seems to work on IDEone.)*

# Answer
> 2 votes
## Perl

I figured that I might as well enter the inevitable. More serious entries coming soon. As a bonus, this entry will never lose in one-on-one competition.

```
print 1

```

# Answer
> 2 votes
## JavaScript (node.js)

Counts what was most popular last round and bids one less than that, wrapping to 20 and bidding 3 on the first round.

```
var lastRound = /[^\n]+$/.exec(process.argv[2]);
var numbers = {};
var re = /\d+/g;
var match;

while(match = re.exec(lastRound)) {
    numbers[match] = numbers[match] >>> 0 + 1;
}

var maxKey = -1;

for(var i in numbers) {
    if(maxKey === -1 || numbers[i] > numbers[maxKey]) {
        maxKey = i;
    }
}

if(maxKey == 0) {
    // First round. Bid 3.
    console.log(3);
} else if(maxKey == 1) {
    // Bid 20.
    console.log(20);
} else {
    // Bid one less.
    console.log(maxKey - 1);
}

```

How to invoke:

```
node script.js 'the argument'

```

# Answer
> 2 votes
## Perl (Bob)

```
$_=<>;
INPUT:{

tr/ /,/;
@in = eval;
for(1..$#in){
 $bids[$rnum][$in[$_]]++
}
for(0..$#in){
 $tbids[$rnum][$in[$_]]++
}
$rnum++;
$_=<>;
if($_ ne"\n"){redo INPUT}
}

for(0..100){$pre[$_]=0}

blazer: {
for($r=1;$r<$rnum;$r++){
winner: for($pnt=1;$pnt<101;$pnt++){
        if($tbids[$r][$pnt] == 1){
            if($pnt > 2){
                $winnum[$pnt]++;
            $wins++;
            }
        last winner
        }
}
    }
    if($wins==0){
    $pre[3]++;last blazer
    }
}

CC1: for($pnt=1;$pnt<101;$pnt++){
    if($tbids[$rnum-1][$pnt] == 1){
        $pre[$pnt]++;last CC1
    }
}

CC2: for($pnt=1;$pnt<101;$pnt++){
    if($rnum-2<0){$pre[7]++;last CC2}
    if($tbids[$rnum-2][$pnt] == 1){
        $pre[$pnt]++;last CC2
    }
    if($pnt==100){
    $pre[7]++;last CC2
    }
}

one: {
$pre[1]+=2;
}

two: {
$pre[2]+=2;
}

five: {
$pre[5]+=2;
}

eight: {
$pre[8]+=2;
}

fortytwo: {
$pre[42]++;
}

mueller: {
    $a=($#in+2)/4;
    $pre[int$a]++;
}

schwarzenbeck: {
    $a=($#in+2)/4+1;
    $pre[int$a]++;
}

beckenbauer: {
    $a=($#in+2)/4+2;
    $pre[int$a]++;
}

totalbots: {
    $pre[$#in+1]++;
}

joe: {
$sum=0;
    for(1..100){
    $sum+=$_*$tbids[$rnum-1][$_];
}
    $average=$sum/($#in+1);
    if($average==0){$average=10};
    $pre[$average]++;
}

node: {
$max=0;$maxloc=0;
for(1..100){
    if($tbids[$rnum-1][$_]>$max){$max=$tbids[$rnum-1][$_];$maxloc=$_}
}
$maxloc--;
#if($maxloc==0){
$maxloc=20;
#}
if($rnum==1){$maxloc=3}
    $pre[$maxloc]++;
}
choice: for(1..100){
    if($pre[$_]==1){
$count++;
    if($count==3){print; last choice}
}
    if($_==100){print"98"}
}

```

See "Bob" for how to invoke.

# Answer
> 2 votes
## Perl (Alice)

```
$_=<>;
INPUT:{

tr/ /,/;
@in = eval;
for(1..$#in){
 $bids[$rnum][$in[$_]]++
}
for(0..$#in){
 $tbids[$rnum][$in[$_]]++
}
$rnum++;
$_=<>;
if($_ ne"\n"){redo INPUT}
}

for(0..100){$pre[$_]=0}

blazer: {
for($r=1;$r<$rnum;$r++){
winner: for($pnt=1;$pnt<101;$pnt++){
        if($tbids[$r][$pnt] == 1){
            if($pnt > 2){
                $winnum[$pnt]++;
            $wins++;
            }
        last winner
        }
}
    }
    if($wins==0){
    $pre[3]++;last blazer
    }
}

CC1: for($pnt=1;$pnt<101;$pnt++){
    if($tbids[$rnum-1][$pnt] == 1){
        $pre[$pnt]++;last CC1
    }
}

CC2: for($pnt=1;$pnt<101;$pnt++){
    if($rnum-2<0){$pre[7]++;last CC2}
    if($tbids[$rnum-2][$pnt] == 1){
        $pre[$pnt]++;last CC2
    }
    if($pnt==100){
    $pre[7]++;last CC2
    }
}

one: {
$pre[1]+=2;
}

two: {
$pre[2]+=2;
}

five: {
$pre[5]+=2;
}

eight: {
$pre[8]+=2;
}

fortytwo: {
$pre[42]++;
}

mueller: {
    $a=($#in+2)/4;
    $pre[int$a]++;
}

schwarzenbeck: {
    $a=($#in+2)/4+1;
    $pre[int$a]++;
}

beckenbauer: {
    $a=($#in+2)/4+2;
    $pre[int$a]++;
}

totalbots: {
    $pre[$#in+1]++;
}

joe: {
$sum=0;
    for(1..100){
    $sum+=$_*$tbids[$rnum-1][$_];
}
    $average=$sum/($#in+1);
    if($average==0){$average=10};
    $pre[$average]++;
}

node: {
$max=0;$maxloc=0;
for(1..100){
    if($tbids[$rnum-1][$_]>$max){$max=$tbids[$rnum-1][$_];$maxloc=$_}
}
$maxloc--;
#if($maxloc==0){
$maxloc=20;
#}
if($rnum==1){$maxloc=3}
    $pre[$maxloc]++;
}
choice: for(1..100){
    if($pre[$_]==1){
$count++;
    if($count==2){print; last choice}
}
    if($_==100){print"99"}
}

```

Takes input similar to my other bots.

```
perl Alice.plx
1 4 3 12
3 2 4 11
[blank line]

```

# Answer
> 2 votes
## Perl (Eve)

I completely redid this entry to help pave the way for my other bots.

```
$_=<>;
INPUT:{

tr/ /,/;
@in = eval;
for(1..$#in){
 $bids[$rnum][$in[$_]]++
}
for(0..$#in){
 $tbids[$rnum][$in[$_]]++
}
$rnum++;
$_=<>;
if($_ ne"\n"){redo INPUT}
}

for(0..100){$pre[$_]=0}

blazer: {
for($r=1;$r<$rnum;$r++){
winner: for($pnt=1;$pnt<101;$pnt++){
        if($tbids[$r][$pnt] == 1){
            if($pnt > 2){
                $winnum[$pnt]++;
            $wins++;
            }
        last winner
        }
}
    }
    if($wins==0){
    $pre[3]++;last blazer
    }
}

CC1: for($pnt=1;$pnt<101;$pnt++){
    if($tbids[$rnum-1][$pnt] == 1){
        $pre[$pnt]++;last CC1
    }
}

CC2: for($pnt=1;$pnt<101;$pnt++){
    if($rnum-2<0){$pre[7]++;last CC2}
    if($tbids[$rnum-2][$pnt] == 1){
        $pre[$pnt]++;last CC2
    }
    if($pnt==100){
    $pre[7]++;last CC2
    }
}

one: {
$pre[1]+=2;
}

two: {
$pre[2]+=2;
}

five: {
$pre[5]+=2;
}

eight: {
$pre[8]+=2;
}

fortytwo: {
$pre[42]++;
}

mueller: {
    $a=($#in+2)/4;
    $pre[int$a]++;
}

schwarzenbeck: {
    $a=($#in+2)/4+1;
    $pre[int$a]++;
}

beckenbauer: {
    $a=($#in+2)/4+2;
    $pre[int$a]++;
}

totalbots: {
    $pre[$#in+1]++;
}

joe: {
$sum=0;
    for(1..100){
    $sum+=$_*$tbids[$rnum-1][$_];
}
    $average=$sum/($#in+1);
    if($average==0){$average=10};
    $pre[$average]++;
}

node: {
$max=0;$maxloc=0;
for(1..100){
    if($tbids[$rnum-1][$_]>$max){$max=$tbids[$rnum-1][$_];$maxloc=$_}
}
$maxloc--;
#if($maxloc==0){
$maxloc=20;
#}
if($rnum==1){$maxloc=3}
    $pre[$maxloc]++;
}
choice: for(1..100){
    if($pre[$_]==1){
$count++;
    if($count==1){print; last choice}
}
    if($_==100){print"100"}
}

```

Takes one input format: the same as "Bob" and "Alice".

# Answer
> 2 votes
## Python (Joe)

This is by no means designed to win, but I'm throwing it out there anyway to add some color to the crowd :) It bids the average of the last round (Average Joe). Invoked the same as my original answer (which I will now name because it seems like that's what all the cool kids are doing, and it helps to distinguish the two). if starting round, it bids `10`.

```
content = sys.argv[1].split('\n')
x = map(int, content[-1].split())
print sum(x)/len(x) if sum(x) != 0 else 10

```

edit: changed method of input to suit question's input method

# Answer
> 2 votes
## Python (CopyCat)

Yet another, this time it copies the exact answer the last winner had, if there was one. It's dsigned to both try to win and block other bidders. bids `5` if first round, bids a random number from the previous round if there was somehow no winner

```
content = sys.argv[1].split('\n')
x = map(int, content[-1].split())
y = []
for each in x:
    if x.count(each) == 1:
        y.append(each)
print min(y) if sum(y) > 0 else random.choice(x) if sum(x) > 0 else 5

```

# Answer
> 2 votes
## Python (TotalBots)

I think this one will be my last, but we'll see. It takes advantange of knowing how many bots there are by simply outputting the number of competing bots, so if there are 17 bots (current number of bots, plus this one), it will output `17`

```
content = sys.argv[1].split('\n')
print len(content[-1].split())

```

# Answer
> 2 votes
## Perl (Health Inspector)

```
print ((((((2)**(2))*((2)**(2)))/((((2)**(2))*(2))*(2)))+((((2)**(2))*(2))/((2)+((2)*(((((2)**(2))+((2)*(2)))+(((2)*(2))/((2)**(2))))**(((2)/(2))/(2)))))))+((((2)-(2))/((((2)**(2))+(2))*((2)+(2))))*(rand(2))))

```

I bet you can guess what it does.

# Answer
> 2 votes
# C++ (Educated Guess)

I already thought I would have missed the deadline, but thanks to the extension I can still add my entry. This program compiles with g++. The program tries to guess the statistics of the other entries, and to choose the smallest one not likely to be chosen by any other one.

```
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <cstdlib>
#include <ctime>
#include <exception>
#include <stdexcept>

typedef std::vector<int> botvec;
typedef std::vector<botvec> scorevec;

// read all the scores from the given string
// note that this only does minimal error checking
// the result is a vector of vector, each entry of which
// represents one round. That is, the vectors in the vector
// correspond to the lines of the command line argument.
scorevec read_past_scores(char const* scoretext)
{
  scorevec past_scores;

  std::istringstream is(scoretext);
  std::string line;

  scorevec::size_type size = 0;

  while (std::getline(is, line))
  {
    past_scores.push_back(botvec());

    std::istringstream ils(line);
    int i;
    while (ils >> i)
      past_scores.back().push_back(i);
    if (size == 0)
      size = past_scores.back().size();
    else if (past_scores.back().size() != size)
      throw std::runtime_error("invalid score format");
  }
  return past_scores;
}

struct counts { int count[100]; };
struct prob { double p[100]; };

int generate_answer(scorevec& past_scores)
{
  int const number_of_players = past_scores.front().size();
  if (past_scores.front().front() == 0) // initial round
    past_scores.pop_back();

  // Pre-fill the counts to get reasonable probabilities also for
  // insufficient statistics (and the statistics *will* be
  // insufficient!). Bias in favour of small numbers.
  counts initial;
  for (int i = 0; i < 100; ++i)
    initial.count[i] =
      i < number_of_players? 100*(number_of_players-i) : 1;

  std::deque<counts> playercounts(number_of_players, initial);

  // add the actual guesses (with a high factor, to give them high
  // weight against the initial counts)
  for (int i = 0; i < past_scores.size(); ++i)
    for (int j = 0; j < number_of_players; ++j)
      playercounts[j].count[past_scores[i][j]-1]+=5000;

  // drop the own guesses
  playercounts.pop_front();

  // calculate the probabilities corresponding to the counts
  std::vector<prob> playerprobabilities(playercounts.size());
  for (int i = 0; i < playercounts.size(); ++i)
  {
    double sum = 0;
    for (int k = 0; k < 100; ++k)
      sum += playercounts[i].count[k];
    for (int k = 0; k < 100; ++k)
      playerprobabilities[i].p[k] = playercounts[i].count[k]/sum;
  }

  // for each selection, estimate the expected number of other players
  // who will bet on it. Return the first one with an expectation
  // below 1.5.
  for (int i = 0; i < 100; ++i)
  {
    double estimate = 0;
    for (int j = 0; j < number_of_players; ++j)
      estimate += playerprobabilities[j].p[i];
    if (estimate < 1.5)
      return i+1;
  }

  // in the unlikely case that such a choice doesn't exist (meaning
  // there are far more than 100 players), just return 100.
  return 100;
}

int main(int argc, char* argv[])
{
  if (argc < 2)
  {
    std::cerr << "Missing score argument!\n";
    return EXIT_FAILURE;
  }

  try
  {
    scorevec past_scores = read_past_scores(argv[1]);

    std::srand(std::time(0));

    std::cout << generate_answer(past_scores) << std::endl;

    return EXIT_SUCCESS;
  }
  catch(std::exception& e)
  {
    std::cerr << e.what() << "\n";
    return EXIT_FAILURE;
  }
  catch(...)
  {
    std::cerr << "Unknown error\n";
    return EXIT_FAILURE;
  }
}

```

# Answer
> 1 votes
## dirichlet.c

```
#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 0;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 32) n++;
            else if (*str == 10) break;
    }

    n /= 2;
    if (n > 99) n = 99;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 2 + val);
}

```

I think this goes through random bits too fast to use `/dev/random`, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.

### Rationale

I didn't want to explain the logic behind this before the tournament was over, but now that the winner has been announced, I think it's time.

By the pigeon-hole principle (aka Dirichlet's principle, hence the name of the bot), if there are *N* competing bots then there is a number *w* in \[1..1+*N*/2\] which either won or would have won if selected. I therefore conclude that the optimal strategy will not select numbers greater than 1+*N*/2. But if *N* is even, selecting 1+*N*/2 creates a smaller winning slot. Therefore the slots which are worth selecting are \[1..(*N*+1)/2\].

That leaves the question of how to select a slot. For small numbers of bots I verified that there's a Nash equilibrium when each bot selects uniformly among the candidates, and I strongly suspect that this will continue to hold true.

The minor deviation in this bot's strategy from the theoretical one is simply metagaming.

# Answer
> 1 votes
## Brainfuck

To quote from the challenge:

> "You can enter as many bots as you wish, so if anyone does enter a bot that only guesses `1`, you can enter another that does the same to render it useless."

Well, since PhiNotPi did enter one, let me enter another. Just to be different, I'll do it in Brainfuck:

```
+++[->++++<]>[-<++++>]<+.

```

Of course, now that betting 1 is no longer a feasible strategy, the obvious thing to do now is to bet 2 instead...

**Edit:** Split answer into two per comments, rewrote both programs in more interesting languages.

# Answer
> 1 votes
### Beckenbauer (Scala)

```
object Beckenbauer extends App {
  println ((args(0).split('\n')(0).split(' ').length+1)/4+2)
}

```

With the help of Schwarzenbeck, Beckenbauer is supposed to score some goals. Without Schwarzenbeck, he's nothing.

Details about running and compilation: See \[Schwarzenbeck\]\[1\]

Edit: Playing deeper in the room now, too.

# Answer
> 1 votes
### Mueller (Scala)

```
object Mueller extends App {
  println ((args(0).split('\n')(0).split(' ').length+1)/4)
}

```

If you know Schwarzenbeck and Beckenbauer, you surely expected Mueller. Here he is. He will benefit much from Beckenbauer and Schwarzenbeck and is supposed to win.

Details about running and compilation: See Schwarzenbeck

Closer to the goal, now.

# Answer
> 1 votes
## Batch Scripting

```
echo 5

```

My submission, gives 5 as its answer every time ;-)

# Answer
> 1 votes
Eight.bat

```
echo 8

```

Another simple answer, gives 8 every time.

# Answer
> 1 votes
## FivesCancel (PHP)

Cancels mellamokb's "always 5" solution.

```
5

```

# Answer
> 1 votes
## EightsCancel (PHP)

Cancels mellamokb's "always 8" solution. Sorry, mellamokb!

```
8

```

# Answer
> 1 votes
## Python 2.7 - Copycat2

Copies the *second* last round's winner. Oh no! otherwise outputs 7.

```
import sys
content = sys.argv[1].split('\n')
x = map(int, content[-2].split()) if len(content) > 1 else [7]
y = []
for each in x:
    if x.count(each) == 1:
        y.append(each)
print min(y) if sum(y) > 0 else random.choice(x) if sum(x) > 0 else 7

```

# Answer
> 1 votes
# Shell script (Deep Thought)

OK, so that I get a slight second chance, here's another entry, this time a shell script (should work with any shell). This always gives the answer to the question of life, the universe and everything.

```
echo 42

```

Actually this algorithm is not entirely correct because I omitted the 7.5 million year delay. :-)

---
Tags: king-of-the-hill
---


title: Can you find Waldo?

text:
# Question
Title: Can you find Waldo?
**Where's Waldo** is a searching game where you are presented an image of some scene, and your goal is to find a man named Waldo in the picture.

Here are a couple pictures showing what Waldo looks like. He always wears a red and white striped sweater and hat, blue pants, brown shoes and hair. He can be with or without accessories such as a camera, glasses, or a cane.

And here are some of the scenes where Waldo is hidden. (You can right click the images and go to the image source for higher resolution.)

# The Challenge

Write a program that processes the images (provided as input however you like) and finds Waldo in as many of the above five images as possible. Your program is scored using the following formula

```
codeLength / numberOfPicturesInWhichWaldoIsFound

```

and, of course, the lower the score, the better.

# Answer
# Shell script, score 30/5 = 6

Since there's no specification on what comprises finding Waldo (i.e. how exact the location must be specified), I figure this program should give a rather good score, finding Waldo in every one of those pictures.

```
echo Waldo is in the picture.

```
> 11 votes

---
Tags: code-challenge
---


# Question
Title: Swaps needed to sort an array in bubble sort method
Write shortest code that detect how many swaps (minimum) are needed to sort (in increasing order) any array of unique positive integers. It should be fast enough to detect number of swaps in array of 1'000'000 integers in decreasing order in 1-2 minutes.

### Refs

### Score

```
[time elapsed]s/60s * [length of code]

```

# Answer
## Python - 262 chars * 45 / 60 = 196.5

Edit: much faster sorting algorithm.

First it will sort all the items in the list by what hundred they are in (0, 100, 200, etc), in a list in `m` (note: I count these as 1 step each, so a list of 1,000,000 items will automatically have 1,000,000 steps initially)

Then it will sort the lists within `m` using the bubble sorting function `c`

This is greatly sped up from using `c` on the original list to be sorted, because the amount of time it takes to sort 1000 items is small (~0.04 seconds), but exponentially increases the larger the list gets (~45 seconds at 10,000 items). But if you sort 100 lists of 100 items, it only takes .4 seconds, to sort, more than 100 times faster than sorting 1 list of 10,000 items. It should therefor take 4 seconds to sort 100,000 items, and 40 seconds to finally sort 1,000,000

In actuality, it took 45 seconds to sort the reversed 1,000,000 item list this way, and results in 50,500,000 steps:

```
python bubblesortcount.py
50500000
44.6600000858

```

This functon works with the given case (reverse ordered list), as well as any random case. No negative integers, though.

```
r=range
def b(l):
 m=[[]for i in r(len(l)//100+1)];t=[];o=0
 for e in l:m[e//100].append(e);o+=1
 for e in m:x=c(e);t+=x[0];o+=x[1]
 return t,o
def c(l):
 s=0
 for p in r(len(l)-1,0,-1):
  for i in r(p):
   if l[i]>l[i+1]:l[i],l[i+1]=l[i+1],l[i];s+=1
 return l,s

```

test:

```
import random,time
a=time.time()
d=b(range(1000000)[::-1]) #reversed list
#d=b(random.sample(range(1000000),1000000)) #scrambled list
z=(time.time()-a)
#print d[0] # comment to not print a gigantic list
print d[1] # number of steps
print z # time it took

```

Edit: by changing the amount the helper function sorts by to 100, I reduced the average time it takes to sort the list to 45 seconds. also reduces character count by 2

edit again: you know what? maybe what I'm doing isn't valid. I can change the amount the helper function sorts by to just 1 and it will sort a million items in 5 seconds.. is this valid?
> 1 votes

---
Tags: code-golf
---


title: Calculate the total number of paths

text:
# Question
Title: Calculate the total number of paths
## Description

There will be a grid of `9x9`, where there will be placed `12` rocks.

You will start at a starting-rock and walking with a starting-direction (north, south, west or east), whenever you see a rock, you have two options:

* Climb over the rock and continue in the same direction
* Change direction to your \*left

\*NOT to the `west`, you change to your left as if you were walking and you take your own left.

So the flow of the paths will always be `counter-clockwise`. Here is an example that illustrates the flow:

Note: In this case, the starting-rock is the yellow `(X)` and the starting-direction is to the `south`

---

## Rules

* The code must be able to solve it for any rock (if it doesn't have complete paths, then is 0)
* You can NOT memorize anything different than the rocks used
* The rocks must be included on the code (so you can't pass them by input)
* We will use the above's rock placement in the competition
* You chose how you will pick the starting-rock (Example: passing an array index or giving a xy location, etc) and how you chose the starting-direction (Example: 1=north, 2=south or etc)
* It must return, print or otherwise make us know the total number of paths somehow for that given rock
* Counted by characters used

Just to immortalize the grid and rock placements in case the image dies for unknown reasons, I will put it in plain text:

```
100100000
100100010
000000000
000000000
000000000
010010000
000000000
010100000
100010010

//rocks = 1, empty = 0

```

---

## Clarifications

* You can't walk on the same part twice on the same path (crossing ways are allowed)
* We need to be able to set on the input: a) the starting-rock and b) the starting-direction
* The complete paths must end on the starting-rock
* Note that it shouldn't be a problem whether we can climb over a starting rock or not, because it is impossible to this to happen with the current map and rules (we do have a four-path rock where this could happen, but after analysing it, this can't happen)
* You are allowed to compress the 9x9 grid. (the most it can be compressed is to a 5x5 I think)

# Answer
> 2 votes
## Python, 274 chars

```
S=7
D=-1j

R=[0,4,7,1+1j,3+1j,1+3j,4+3j,7j,3+7j,7+7j,8j,3+8j]
Z={}
for i in range(4096):
 d=D;p=R[S];L=[]
 while len(L)<12:
  p+=d;P=[(abs(r-p),r)for r in R if r-p==abs(r-p)*d]
  if not P:break
  p=min(P)[1];d*=1j**(i>>R.index(p)&1);L+=[p]
  if p==R[S]:Z[tuple(L)]=1;break
print len(Z)

```

The code I'm counting starts at the `R=[...`, the initial two lines are "input" which I didn't count.

`R` is the set of rock coordinates, listed using complex number coordinates. `S` is the starting rock. `D` is the starting direction, again using complex numbers (1=right,-1=left,1j=up,-1j=down).

The code tries all of the 2^12=4096 possibilities for go straight/turn left for each rock, then walks from the starting rock until it gets back to the starting rock, or there is no more rock on the path, or the path gets too long (it loops). It saves the path in `Z` if it is successful.

# Answer
> 1 votes
**ASM - WinXP Command shell .COM 128 bytes, source = 607 characters**

To run, provide the rock id and the direction, e.g.

```
program c1

```

where the letter is the rock (top left = a, bottom right = l) and the number is the direction: up = 3, left = 2, down = 1, right = 0

```
   mov bp,1000h
   mov di,bp
   mov cx,bp
   xor ax,ax
   rep stosw
   mov bl,b[82h]
   sub bl,'a'-1
   mov bh,ch
   add bx,bx
   mov cl,b[83h]
   sub cl,48
   shl cl,2
   mov di,bx
   call l2
   mov dx,bp
   add b[bp],48
   mov b[bp+1],'$'
   mov ah,9
   int 21h
   ret
l1:inc b[bp]
   cmp di,bx
   je ret
   dec b[bp]
   cmp b[di+bp],0
   jne ret
   call l2
   sub cl,4
l2:mov dx,[di+l3-2]
   ror dx,cl
   and dx,15
   jz ret
   mov b[di+bp],1
   pusha
   mov di,dx
   add di,di
   call l1
   popa
   mov b[di+bp],0
   ret
l3:xor al,b[bx+si]
   inc ax
   add w[si+09510],sp
   and ax,ax
   add al,087
   add b[bx+si+0906],dh
   pusha
   add b[bx+si+0b],cl
   xor b[si],cl
   jpe l4
l4:pop bx

```

# Answer
> 0 votes
## JavaScript, 466 chars

* Starting-direction is equal to: North=1, West=2, South=3, East=4
* The starting-rock is in row/column notation, where the upper-left is `11`. (the grid was compressed to a 5x5)

The first two lines are input and aren't included in the count of characters, also I added some break lines to wrap the code.

```
D=3;//starting direction
C=21;//starting rock

function a(a){return a+="",(a[0]-1)*5+(a[1]-1)}
function b(a){var b=!1,c=C+"";a==4?(h=c[0]+(c[1]-1))[1]>0&&(b=!0):a==3?(h=-(-c[0]-1)+c[1]+"")[0]<6&&(b=!0):a==2?(h=c[0]+ -(-c[1]-1))[1]<6&&(b=!0):(h=c[0]-1+c[1])[0]>0&&(b=!0);if(b)return C=h*1,!0}
function c(){var c=C;while(b(D)&&F[a(C)]==0);if(C!=c&&F[a(C)]==1)return!0}
function d(){if(c()){F[C]++;var a=D,b=C;C!=B?(d(),C=b,D=a,D==1?D=4:D--,d()):(A++,F=E)}}
A=0,B=C,E=F="1010010101010100110010011".split(""),d(),alert(A)

```

Uncompressed and explained code:

```
dir=3;
start=21;

//transforms row-column notation to array index
function toAV(a){
    return a+="",(a[0]-1)*5+(a[1]-1);
}

//advance one square on the current direction
//returns true when it succeed
function walk(num){
    var walkbol=false,str=xy+"";
    if(num==4){
        if((wal_rec=str[0]+(str[1]-1))[1]>0){
            walkbol=true;
        }
    }else if(num==3){
        if((wal_rec=-(-str[0]-1)+str[1]+"")[0]<6){
            walkbol=true;
        }
    }else if(num==2){
        if((wal_rec=str[0]+-(-str[1]-1))[1]<6){
            walkbol=true;
        }
    }else{
        if((wal_rec=(str[0]-1)+str[1])[0]>0){
            walkbol=true;
        }
    }
    if(walkbol){
        xy=wal_rec*1;
        return true;
    }
}

//start walking on the current dir until a)didn't succeed walking or b)step on a rock
//returns true when it moved at least once and it ended above a rock
function nextRock(){
    var str1=xy;
    while(walk(dir)&&map[toAV(xy)]==0){}

    if(xy!=str1&&map[toAV(xy)]==1){
        return true;
    }
}

//if it finds a rock, it calls itself twice
//one with the current direction and one with the direction to its left
function splitways(){
    if(nextRock()){
        map[xy]++;
        var cc=dir,dd=xy;
        if(xy!=start){
            splitways();
            //--
            xy=dd;
            dir=cc;
            dir==1?dir=4:dir--;
            splitways();
        }else{
            count++;
            map=xmap;
        }
    }
}

//globals
count=0,xy=start,xmap=map="1010010101010100110010011".split("");

//start
splitways();
alert(count);

```

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


title: Implementing a firewall

text:
# Question
Title: Implementing a firewall
Your program reads from standard input and prints to standard output.

The first thing you'll be receiving on stdinput will be the ruleset for your firewall (until you encounter a double newline).

We'll start explaining **the ruleset** itself with some sample input:

```
/* header abbreviations added for demonstration purposes only */

 /> Allow (A) or Block (B)
|
|  /> Source (incl. mask)
| |
| |               /> Destination (incl. mask)
| |              |
| |              |          /> Source port(s)
| |              |         |
| |              |         |           /> Destination port(s)
| |              |         |          |

A 192.168.1.0/24 0.0.0.0/0 1024:65536 80
A 0.0.0.0/0 192.168.1.0/24 80 1024:65536
A 192.168.1.1/32 0.0.0.0/0 80 1024:65536
A 0.0.0.0/0 192.168.1.1/32 1024:65536 80
B 0.0.0.0/0 0.0.0.0/0 * *

```
* Rules are processed in cascading order. Once you find a matching rule, determine the outcome and stop processing.
* If a packet does not match any given rule, block it (sane defaults).
* Elements of a rule are single-space delimited.
* Source and destination adresses will provide a netmask. Be sure to filter accordingly.
* The specification of the source and destinations ports must support the following syntax:
    1. Single ports: e.g. "80"
    2. Inclusive port ranges: e.g. "1024:65536"
    3. All ports: e.g. "\*"
* You may assume input to be well-formed.

After the double newline, you'll receive (one or more) newline seperated **input packets** to test according to the ruleset you've now acquired.

Some sample input for the packets to clarify:

```
/* header abbreviations added for demonstration purposes only */

 /> Source
|
|             /> Source port
|            |
|            |     /> Destination
|            |    |
|            |    |              /> Destination port
|            |    |             |

192.168.1.18 1036 157.136.122.5 22
157.136.108.8 2400 192.168.1.1 80

```

You'll examine these input packets and determine the outcome of filtering according to the rules.

The above sample input (ruleset + packets) should thus yield the following output:

```
BLOCK 192.168.1.18 1036 157.136.122.5 22
ALLOW 157.136.108.8 2400 192.168.1.1 80

```

The output is basically no more than 'BLOCK' or 'ALLOW' followed by a space and the verbatim input line.

**Some varia:**

* This is code golf, the shortest (source code, by byte count) solution wins. Have fun!
* You are not allowed to use specific IP address handling features of your language.
* Specialized languages for routing or firewalling will be excluded from contending for first place (if they exist).
* If any part of the question is ambiguous or in need of further clarification, feel free to comment.

# Answer
> 3 votes
## Haskell, 356 characters

```
main=interact$f.break null.lines;f(r,_:p)=unlines$map(foldr(g.w)(j"B"++)r)p
g[r,s,d,a,b]n x|and$zipWith3($)(cycle[k.('/'#),q.(':'#)])[s,a,d,b]$w x=j r++x|t=n x
k[y,z]x=y%z==x%z;y%z=foldl((.r).(+).(*256))0('.'#y)`div`2^(32-r z)
q["*"]x=t;q[y]x=x==y;q[a,b]x=r x>=r a&&r x<=r b
d#x=w$map(d?)x;d?x|d==x=' '|t=x;j"A"="ALLOW ";j"B"="BLOCK ";t=1<3;r=read;w=words

```

# Answer
> 1 votes
# Perl 561

First try. Any tips?

```
[gary@phoenix ~]$ cat test | perl f2.pl
BLOCK 192.168.1.18 1036 157.136.122.5 22
ALLOW 157.136.108.8 2400 192.168.1.1 80

sub r{($i,$j)=split'/',shift;$j eq 0?'*':map$h.=sprintf("%.8b",$_),split/\./,$i;
substr$h,0,$j}sub s{$_[0]=~/(\d+):(\d+)/?$1<$_[1]&& $_[1]<$2:$_[0]==$_[1]}sub
t{chomp;($a,$b,$c,$d,$e)=split/ /}sub o{$_[0]eq'*'or$_[0] eq
substr&r($_[1].'/32'),0,length$_[0]}sub p{$_[0]eq'*'or&s($_[0],$_[1])}
map((/^[AB]/?(t,push@f,join' ',($a,&r($b),&r($c),$d,$e)):push@g,$_),<STDIN>);
push@f,"B * * * *\n";for $q(@g){if($q=~/[0-9]/){($k,$l,$m,$n)=split/ /,$q;
for(@f){&t;$a=$a=~/^A/?'ALLOW':'BLOCK';&o($b,$k)&& &o($c,$m)&& &p($d,$l)&&
&p($e,$n)?print"$a $q":next;last}}}

```

# Answer
> 1 votes
# Ruby (384)

Not sure it's 100% correct, but works at least for the given example inputs. Propably could be made a bit shorter too.

```
$ wc gc4907-firewall.rb
       9      15     384 gc4907-firewall.rb

$ cat fwinput| ruby gc4907-firewall.rb
BLOCK 192.168.1.18 1036 157.136.122.5 22
ALLOW 157.136.108.8 2400 192.168.1.1 80

```

```
q=->x{x.gsub(/(\d+)\.?/){'%02x'%$1}.hex}
w=->x{u=x.scan(/[\d.]+\/\d+/)
p=$'.split.map{|z|z=="*"?->y{1}:(z=eval z.sub(?:,'..');->y{z===y.to_i})}
f=u.map{|z|a,m=z.split ?/;a=q[a]>>(m=32-m.to_i);->y{a==q[y]>>m}}.zip(p).flatten
->y{f.zip(y.split).all?{|z,c|z[c]}&&x[0]}}
s=[]
while gets=~/./;s<<w[$_];end
s<<->x{0}
$<.map{|p|s.map{|f|(f=f[p])&&(puts (f=="A"?"ALLOW ":"BLOCK ")+p;break)}}

```

$' seems to confuse both brace matching in emacs, and syntax highlight here.

---
Tags: code-golf
---


title: C: Output "tomorrow's date"

text:
# Question
Title: C: Output "tomorrow's date"
I'm a code golf novice, but I'm eager to give it a go.

My challenge is: Write the shortest program in C which takes in a date `D` as input and outputs the date `D + 1 day`

**Rules:**

* program must compile only with `gcc progname.c -o progname` So no compiler/makefile tricks (if there are any) - compiler warnings don't matter
* The input and output format must be `day/month/year` zero padding of single digit values does not matter: `1/3/1998` is equal to `01/03/1998`
* It doesn't matter how you give the the program it's input date, it can be a program argument, `scanf` whatever. Output must be to `stdout` however
* February has 29 days when the year is divisible by 4
* No date validation necessary, i.e. assume the input is always a valid date.
* any integer year should be supported, i.e. `INT_MIN -> INT_MAX`

Shortest code length wins, and there are extra points for extra bastardised C.

## My solution uses 126 123\* 121 characters

Good luck

```
*s="%i/%i/%i",m,d;main(y){scanf(s,&d,&m,&y);printf(s,d,m,(d=d%((m>7^m&1)+27+(m-2?3:y%4?1:2))+1)-1?y:(m=m%12+1)-1?y:y+1);}

```

\*because of an idea Gareth's code gave me

# Answer
> 4 votes
Okay, it's been a while since I wrote any C but I'll give it a go:

```
m,y,*q="%d/%d/%d";
main(d){
scanf(q,&d,&m,&y);
++d>30+(m+(m>7))%2-(m^2?0:2-!(y%4))?(m+=d=1)>12?y+=m=1:0:0;
printf(q,d,m,y);}

```

**120 characters**.
With a bit of formatting(not that it makes it any more readable any more...):

```
m,y,*q="%d/%d/%d";
main(d)
{
    scanf(q,&d,&m,&y);
    ++d>30+(m+(m>7))%2-(m^2?0:2-!(y%4))?(m+=d=1)>12?y+=m=1:0:0;
    printf(q,d,m,y);
}

```

The compiler throws out warnings like nobody's business, but it works.

I'm not sure I can get it any smaller than this now without stealing a couple of tricks from Griffin. With those tricks I can get to **116 characters**:

```
m,y,*q="%d/%d/%d";
main(d){
scanf(q,&d,&m,&y);
printf(q,d,m,++d>30+(m>7^m&1)-(m^2?0:2-!(y%4))?(m+=d=1)>12?y+=m=1:y:y);}

```

# Answer
> 2 votes
## C, 112 chars

Many months late, but I just saw it and decided to improve it.
The leading `*` isn't needed for 32bit platforms (and some 64bit platforms), so it can perhaps be removed.

```
*s="%d/%d/%d";
main(y,m,d){
    scanf(s,&d,&m,&y);
    d++>29+(m-2?m+m/8&1:!(y%4)-2)?d=m++<12||(y+=m=1):0;
    printf(s,d,m,y);
}

```

Lots of similarity to Gareth's solution, but honestly - I didn't look.
The only thing I did borrow was saving the format string in a variable (which is kind of obvious, but I missed it).

I do fix a problem with Gareth's solution - it relies on the evaluation order of `printf` parameters.

# Answer
> 1 votes
# C - 293

```
#define w(x) while(*(i++)!='/');x=atoi(i);
main(){char x[99];scanf("%s",x);f(x);}
f(char* i){
int a=atoi(i),b,c,m[]={0,1,0,1,0,1,0,1,1,0,1,0,1};
w(b);w(c);
if(b==2)if((a==28&&c%4)||a==29){a=1;b=3;}else a++;else if(a-m[b]-30==0)if(b==12){a=b=1;c++;}else{a=1;b++;}else a++;
printf("%d/%d/%d",a,b,c);}

```

I've never really tried to golf C (and I am by no means an expert in C), but I feel this is pretty good. Basically it goes like this: get input from scanf, convert days, shift pointer, convert months, shift pointer, convert years (latter two have a #define to help), do logic with calendar logic. year%4 was a cool trick, and I have a month hash table indicating if the month is 30 or 31 days (kinda big to declare, but I think it was worth it). Finally, print. I'm sure there is a neat way to refactor using ternary (?:), but again, I'm no expert.

EDIT: fixed some typos.

# Answer
> 1 votes
## C (in a way), ~~97~~ 71

I will lose fifty rep for this but it was necessary.

The *actual* rule violation is that it doesn't quite do `INT_MIN..INT_MAX`; the range instead seems to be `0..1410065407` (on 64-bit Ubuntu 11... I'm saying nothing about portability :P).

```
main(){system("read a;date -d@$((`date -d$a +%s`+86400)) +%m/%d/%Y");}

```

(old version:)

```
d,e[9];main(){sprintf(e,"date -d@$((`date -d%s +%%s`+86400)) +%%m/%%d/%%Y",gets(&d))&system(e);}

```

# Answer
> 0 votes
# 106 100 characters

Another entry that breaks the year rule by supporting only the years 1 to 9999, and also implements correct leap year handling instead of following requirements. The code simply uses POSIX libraries while abusing the type system:

```
t[9],b[9],*f="%d/%m/%Y";main(){gets(b);strptime(b,f,t);t[3]++;mktime(t);strftime(b,99,f,t);puts(b);}

```

---
Tags: code-golf, c, date
---


title: Implement Oplop

text:
# Question
Title: Implement Oplop
Oplop is an algorithm to generate website specific passwords based on a master password and a keyword.

It is described here: http://code.google.com/p/oplop/wiki/HowItWorks

There's an online implementation here: https://oplop.appspot.com/

My attempt in Q is 204 200 167 165 139 characters ignoring whitespace:

```
{d:.Q.A,.Q.a,(n:"0123456789"),"-_";
b:d 2 sv'6 cut(,/)0b vs'(md5 x,y),2#0x00;
i:b in n;j:i?1b;k:(j _i)?0b;
8#$[0=0+/i;"1";8>j;();b j+(!)k],b}

```

EDIT: I achieved significant character savings by removing some redundant code from my Hex-\>Base64 conversion.

2012.03.07 - Cut out 2 more characters

2012.03.11 - Removed duplication and got accurate char count

2012.03.20 - Down to 141

**Criteria**

Candidate functions/implementations should take two strings as arguments and return an 8 character password as defined in the algorithm.

**Judging**

Code golf so shortest code takes the prize.

# Answer
## Ruby (113 110 chars)

```
require 'digest'
b=Digest::MD5.base64digest(ARGV.join)
puts "#{b} 1".sub(/(^\D{8,}(\d*))/,'\2\1')[0..7].tr'+/','-_'

```

```
require'digest'
b=Digest::MD5.base64digest(ARGV.join)
puts"#{b} 1".sub(/(^\D{8,}(\d*))/,'\2\1')[0,8].tr'+/','-_'

```

I notice that all the non-Python languages have to do a translation of the + and / to be - and \_, respectively. It seems that Python's base64 is different/wrong?
> 3 votes

# Answer
## Python - 198 166 152 150

```
import base64,md5,sys,re
b=base64.urlsafe_b64encode(md5.md5(sys.argv[1]+sys.argv[2]).digest())
r=re.findall('\d+',b)if all(not c.isdigit()for c in b[:8])else['']
print((r[0]if len(r)else'1')+b)[:8]

```

```
import base64,md5,sys,re
b=base64.urlsafe_b64encode(md5.md5("".join(sys.argv[1:])).digest())
print((''if re.search('\d',b[:8])else re.findall('\d+',b+'1')[0])+b)[:8]

```

```
import base64,md5,sys,re
b=base64.urlsafe_b64encode(md5.md5("".join(sys.argv[1:])).digest())
print(re.findall('(?:[^\d]{8,}(\d*)|)',b+' 1')[0]+b)[:8]

```

This was a fun one. Could be a lot shorter if not for the verbosity of the `md5` and `base64` modules. The third and fourth lines are the interesting ones. My favourite trick was using a list containing only an empty string to avoid having to use any real if statements.

EDIT: Had to change from checking `c.isalpha()` to `not c.isdigit()` (added 4 characters)

EDIT: Shaved off 32 characters. Many thanks to Ugoren!

EDIT: Shaved off 14 more chars again many thanks to Ugoren. Used some regex trickiness

```
print(re.findall('(?:[^\d]{8,}(\d*)|)',b+' 1')[0]+b)[:8]

```

instead of

```
print((re.findall('^[^\d]{8,}(\d*)',b+' 1')+[''])[0]+b)[:8]

```

To save three chars.
> 5 votes

# Answer
## Shell - 116

```
echo -n $1$2|md5sum|xxd -r -p|base64|sed -re'y!+/!-_!;/^.{0,7}[0-9]/!{s/^([^0-9]*)([0-9]+)/\2\1/;t;s/^/1/}'|cut -c-8

```

Depends on cut, md5sum and base64 from coreutils, xxd and GNU sed.
> 5 votes

# Answer
## PHP (126)

```
function f($m,$n){return substr(preg_replace('/^\D{8,}(\d+)/','$1$0',strtr(base64_encode(md5($m.$n,1)),'+/','-_').' 1'),0,8);}

```

Beautified:

```
function oplop( $master, $nick ) {
    return substr( preg_replace(
        '/^\D{8,}(\d+)/', '$1$0',
        strtr( base64_encode( md5( $master . $nick, true ) ), '+/', '-_' ) . ' 1'
    ), 0, 8 );
}

```
> 2 votes

---
Tags: code-golf, string, cryptography
---


# Question
Title: all occurences of each line from a file in another file for each line in the first file
This is a code golf problem: Say you have two files, one file s and one file h. The problem is that for each line l of s you should produce a list that contains all lines of h that contain l. By "contain" I mean a substring, so, for example the line "foobar12baz" contains either foo, bar, foobar, 12, 1 or baz, etc...

You may use any programming language or any program to accomplish this in the least number of characters possible. Instead of a list you may print an array, or other sequence type structure.

Here is some Haskell I wrote that does it in 103 characters, and assumes you have the following modules imported

Data.List

Control.Monad

Control.Applicative

```
let f = (<$>) lines . readFile in (\(a,b)-> [[d|d<-b, isInfixOf c d]|c<-a]) <$> liftM2 (,) (f "s") (f "h")

```

Example files:

"h"

```
asdf1
asd2asdf
s3adsf

```

"s"

```
1
2
3

```

Output:

```
[["asdf1"],["asd2asdf"],["s3adsf"]]

```

# Answer
> 9 votes
just grep is enough...

```
grep -Ff s h

```

# Answer
> 1 votes
Better:

```
puts IO.readlines('h').grep /#{IO.readlines's'}/

```

In ruby, 53 characters, outputs an array and not a file:

```
p IO.readlines('h').each{|m|m=~/#{IO.readlines's'}/}

```

This reads file 'h' for every line of 's' to save a variable. Not ideal.

Happy golfing!

# Answer
> -1 votes
```
while read -r;do grep "$REPLY" --h>"$REPLY";done<s

```

YEAAAAAAAH!!1

---
Tags: code-golf, string
---


title: Binary tree encoding

text:
# Question
Title: Binary tree encoding
Let's suppose you have a complete binary tree (i.e. each internal node has exactly two non empty descendants). Each node contains a nonzero integer. You are given the task of encoding and decoding the tree into/from a list of integers.

The tree is stored internally something like:

```
struct node {
  int data;
  struct node *left, *right;
};

```

And you have to implement two functions:

```
int *encode(struct node *root);
struct node *decode(int *array);

```

It is up to you how you encode and decode.

Points for:

* minimum encoding length
* complexity (ideally linear in number of nodes)
* originality

No points for source code length and you are not restricted to C.

Tree example:

```
     5
    / \
   3   2
      / \
     2   1
    / \
   9   9

```

# Answer
> 2 votes
**~ 1.03 N**

It seems all the answers so far take least 2\*N * 32-bits to store. (Except the solutions in languages which allows integer values longer than 32 bits, like the Haskell and Ruby solutions - but those are still going to take extra bytes to encode whenever the data is greater than 16K.)

Here is a solution which only takes N+ceiling(N/32)+1 ints of storage. This approaches 1.03125 N for large N, and is under 1.1 N for all N greater than 20.

The idea is to store an extra bit for each node where 1 is "hasChildren". These bits are packed into N/32 words up front.

```
int* encodeHelper(Node* n, int* code, int* pos, int* flag)
{
   int hasKids = (n->left!=0);
   code[*flag/32]|=hasKids<<(*flag&31);
   *flag+=1;
   if (hasKids) bencodeHelper(n->left, code, pos, flag);
   code[*pos]=n->data;
   *pos+=1;
   if (hasKids) bencodeHelper(n->right, code, pos, flag);
   return code;
}

int* encode(Node* h, int* sizeOut)
{
   int nnodes=countNodes(h);
   int nflags = (int)ceil(nnodes/32.0);
   int pos=nflags+1;
   int flag=32;
   int* out;
   *sizeOut = 1+nnodes+nflags;
   out = calloc(*sizeOut, sizeof(int));
   if (!h) return out;
   out[0]=nflags+1; //store start of data
   return encodeHelper(h,out,&pos,&flag);
}

Node* decodeHelper(int* code, int* pos, int* flag)
{
   Node*n = calloc(1, sizeof(Node));
   int hasKids = code[*flag/32]>>(*flag&31)&1;
   *flag+=1;
   if (hasKids) n->left = bdecodeHelper(code, pos, flag);
   n->data = code[*pos];
   *pos+=1;
   if (hasKids) n->right = bdecodeHelper(code, pos, flag);
   return n;
}

Node* decode(int* code)
{
   int flag=32;
   int pos=code[0];
   if (!pos) return NULL;
   return decodeHelper(code, &pos, &flag);
}

```

*(compelete implementation here)*

# Answer
> 6 votes
This Haskell program encodes a tree of n nodes in n Integers. The trick is that it encodes the node's data doubled, and then uses the lower-order bit to indicate if this is a leaf node, or an interior node.

Technically, the `Parser` monad here is over-kill, since there is only one parser created, `decoder` and I could have put the parser chaining logic directly there. But this way the decoder is very clear, and the `Parser` despite it's small size, is a reasonable simple parsing framework.

```
import Control.Monad (ap)

data Tree = Leaf Integer | Node Integer Tree Tree
  deriving (Eq, Show)

encode :: Tree -> [Integer]
encode (Leaf n)     = [n*2]
encode (Node n t u) = (n*2+1) : encode t ++ encode u

decode :: [Integer] -> Maybe Tree
decode = fullyParse decoder
  where
    decoder :: Parser Integer Tree
    decoder = do
      i <- next
      let n = i `div` 2
      if even i
        then return (Leaf n)
        else return (Node n) `ap` decoder `ap` decoder

-- A simple Parsing Monad
data Parser a b = P { runParser :: [a] -> Maybe (b, [a]) }

instance Monad (Parser a) where
  return a = P ( \ts -> Just (a, ts) )
  p >>= q  = P ( \ts -> runParser p ts >>= (\(v,ts') -> runParser (q v) ts') )
  fail _   = P ( const Nothing )

next :: Parser a a
next = P n
 where n (t:ts) = Just (t,ts)
       n _      = Nothing

fullyParse :: Parser a b -> [a] -> Maybe b
fullyParse p ts = runParser p ts >>= consumedResult
  where
    consumedResult (v,[]) = Just v
    consumedResult _      = Nothing

-- Example
main :: IO ()
main = do
    putStrLn $ "example:  " ++ show ex
    putStrLn $ "encoding: " ++ show encEx
    putStrLn $ "decoding: " ++ show decEx
    putStrLn $ "worked?   " ++ show worked
  where
    ex = Node 5
          (Leaf 3)
          (Node 2
            (Node 2
              (Leaf 9)
              (Leaf 9)
            )
            (Leaf 1)
          )
    encEx = encode ex
    decEx = decode encEx
    worked = maybe False (ex ==) decEx

```

Running this gets you:

```
> runhaskell TreeEncoding.hs
example:  Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1))
encoding: [11,6,5,5,18,18,2]
decoding: Just (Node 5 (Leaf 3) (Node 2 (Node 2 (Leaf 9) (Leaf 9)) (Leaf 1)))
worked?   True

```

# Answer
> 5 votes
In C

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

struct Node;
typedef struct Node Node;

struct Node
{
    int   data;
    Node* left;
    Node* right;
};
/* Private Functions */
static int*  encodeNode(Node* tree, int* store);
static Node* decodeNode(int** store);

/* Public Functions */
Node*   newNode(int data,Node* left,Node* right);
void    deleteTree(Node* tree);
int     countNodesTree(Node* tree);
int*    encode(Node *tree);
Node*   decode(int* store);
void    printTree(Node* tree);

Node* newNode(int data,Node* left,Node* right)
{
    Node* result    = (Node*)malloc(sizeof(Node));
    result->data    = data;
    result->left    = left;
    result->right   = right;

    return result;
}

void deleteTree(Node* tree)
{
    if (tree == NULL)
    {   return;
    }

    deleteTree(tree->left);
    deleteTree(tree->right);
    free(tree);
}

int countNodesTree(Node* tree)
{
    if (tree == NULL)
    {   return 0;
    }

    return    countNodesTree(tree->left)
            + countNodesTree(tree->right)
            + 1;
}

void printTree(Node* tree)
{
    if (tree == NULL)
    {
        fprintf(stdout, "- ");
    }
    else
    {
        fprintf(stdout, "%d ", tree->data);
        printTree(tree->left);
        printTree(tree->right);
    }
};

```

The encode:

```
int* encode(Node *tree)
{
    int     nodeCount   = countNodesTree(tree);
    int*    result      = (int*)malloc(sizeof(int) * (nodeCount * 2 + 1));

    // Put the node count in the first element.
    // This makes it easy to also serialize this object for transport
    // i.e. you can put it in a file or a stream (socket) and easily recover it.
    result[0]           = nodeCount;
    encodeNode(tree, result + 1);
    return result;
}

int* encodeNode(Node* tree, int* store)
{
    if (tree != NULL)
    {
        store[0]    = tree->data;
        /*
         * Slight overkill. for this question.
         * But works and makes future enhancement easy
         */
        store[1]    = (tree->left  == NULL ? 0 : 1)
                    + (tree->right == NULL ? 0 : 2);
        store += 2;

        store       = encodeNode(tree->left,  store);
        store       = encodeNode(tree->right, store);
    }
    return store;
}

```

The decode:

```
Node* decode(int* store)
{
    if (store == NULL)
    { fprintf(stderr, "Bad Input terminating: encode() always return non NULL\n");
      exit(1);
    }

    if (store[0] == 0)
    {
        return NULL;
    }

    store++;
    return decodeNode(&store);
}

Node* decodeNode(int** store)
{
    int     value   = (*store)[0];
    int     flag    = (*store)[1];
    (*store) += 2;

    Node*   left    = flag & 1 ? decodeNode(store) : NULL;
    Node*   right   = flag & 2 ? decodeNode(store) : NULL;

    return newNode(value, left, right);
}

```

Main:

```
int main()
{
    Node*   t = newNode(5,
                        newNode(3, NULL, NULL),
                        newNode(2,
                                newNode(2,
                                        newNode(9, NULL, NULL),
                                        newNode(9, NULL, NULL)
                                       ),
                                newNode(1, NULL, NULL)
                               )
                       );

    printTree(t);
    fprintf(stdout,"\n");

    int*    e   = encode(t);
    Node*   d   = decode(e);
    printTree(d);
    fprintf(stdout,"\n");

    free(e);
    deleteTree(d);
    deleteTree(t);
}

```

Note. Each node is encoded as two integers (plus one int for the count of nodes).
So the supplied tree encodes like this:

```
 7, 5, 3, 3, 0, 2, 3, 2, 3, 9, 0, 9, 0 1, 0
 ^  ^
 ^  ^ Node 1
 ^
 Count

```

# Answer
> 3 votes
In Ruby, with the same encoding than @MtnViewMark :

```
class Node
        def initialize(data, left = nil, right = nil)
                @data, @left, @right = data, left, right
        end

        def encode
                "%d %s %s" % [@data<<1|1, @left.encode, @right.encode]
        end

        class << self
                def decode(str)
                        _decode(str.split.map &:to_i)
                end

                private

                def _decode(a)
                        n = a.shift
                        if n & 1 == 1
                                Node.new(n>>1, _decode(a), _decode(a))
                        else
                                Leaf.new(n>>1)
                        end
                end
        end
end

class Leaf < Node
        def encode
                (@data<<1).to_s
        end
end

tree=Node.decode("11 6 5 5 18 18 2")
print tree.encode

```

The cost is one integer per node (`data << 1 | has_childs`) :

```
11 6 5 5 18 18 2

```

# Answer
> 2 votes
Given a binary tree with `n` nodes, this encodes it in a list of `2n + 1` integers. Both the encoding and decoding algorithms have `O(n)` complexity.

I use the 0 integer as a sentinel marker when encoding, indicating when I unfold the recursion. Then when I'm decoding, I put the tree nodes I'm creating on a stack (of sorts) and use the 0s in the list to keep track of where to add the next node. I haven't tried, but I'm pretty sure the decoding would break if the tree was not complete.

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

// Prototypes
struct BTnode;
struct BTnode * bt_add_left(struct BTnode * node, int data);
struct BTnode * bt_add_right(struct BTnode * node, int data);
int             bt_depth(struct BTnode * tree);
int             bt_encode_preorder(int * list, struct BTnode * tree, int index);
struct BTnode * bt_node_create(int data);
int             bt_node_delete(struct BTnode * node);
void            bt_print_preorder(struct BTnode * tree);
int *           encode(struct BTnode * tree);
struct BTnode * decode(int * list);

// Binary tree node
struct BTnode
{
  int data;
  struct BTnode *left, *right;
};

// Add node to this node's left
struct BTnode * bt_add_left(struct BTnode * node, int data)
{
  struct BTnode * newnode = bt_node_create(data);
  node->left = newnode;
  return newnode;
}

// Add node to this node's right
struct BTnode * bt_add_right(struct BTnode * node, int data)
{
  struct BTnode * newnode = bt_node_create(data);
  node->right = newnode;
  return newnode;
}

// Determine depth of the tree
int bt_depth(struct BTnode * tree)
{
  int depth;
  int leftdepth = 0;
  int  rightdepth = 0;
  if( tree == NULL ) return 0;

  if( tree->left != NULL )
    leftdepth = bt_depth(tree->left);
  if( tree->right != NULL )
    rightdepth = bt_depth(tree->right);

  depth = leftdepth;
  if(rightdepth > leftdepth)
    depth = rightdepth;

  return depth + 1;
}

// Recursively add node values to integer list, using 0 as an unfolding sentinel
int bt_encode_preorder(int * list, struct BTnode * tree, int index)
{
  list[ index++ ] = tree->data;

  // This assumes the tree is complete (i.e., if the current node does not have
  // a left child, then it does not have a right child either)
  if( tree->left != NULL )
  {
    index = bt_encode_preorder(list, tree->left, index);
    index = bt_encode_preorder(list, tree->right, index);
  }

  // Add sentinel
  list[ index++ ] = 0;
  return index;
}

// Allocate memory for a node
struct BTnode * bt_node_create(int data)
{
  struct BTnode * newnode = (struct BTnode *) malloc(sizeof(struct BTnode));
  newnode->left = NULL;
  newnode->right = NULL;
  newnode->data = data;
  return newnode;
}

// Free node memory
int bt_node_delete(struct BTnode * node)
{
  int data;
  if(node == NULL)
    return 0;
  data = node->data;

  if(node->left != NULL)
    bt_node_delete(node->left);
  if(node->right != NULL)
    bt_node_delete(node->right);

  free(node);
  return data;
}

// Print all values from the tree in pre-order
void bt_print_preorder(struct BTnode * tree)
{
  printf("%d ", tree->data);
  if(tree->left != NULL)
    bt_print_preorder(tree->left);
  if(tree->right != NULL)
    bt_print_preorder(tree->right);
}

// Decode binary tree structure from a list of integers
struct BTnode * decode(int * list)
{
  struct BTnode * tree;
  struct BTnode * nodestack[ list[0] ];
  int i,j;

  // Handle trivial case
  if( list == NULL ) return NULL;

  tree = bt_node_create( list[1] );
  nodestack[ 1 ] = tree;

  j = 1;
  for(i = 2; i < list[0]; i++)
  {
    if( list[i] == 0 )
    {
      //printf("popping\n");
      j--;
    }
    else
    {
      if( nodestack[j]->left == NULL )
      {
        //printf("Adding %d to left of %d\n", list[i], nodestack[j]->data);
        nodestack[ j+1 ] = bt_add_left(nodestack[j], list[i]);
        j++;
      }
      else
      {
        //printf("Adding %d to right of %d\n", list[i], nodestack[j]->data);
        nodestack[ j+1 ] = bt_add_right(nodestack[j], list[i]);
        j++;
      }
    }
  }

  return tree;
}

// Encode binary tree structure as a list of integers
int * encode(struct BTnode * tree)
{
  int maxnodes, depth, length;
  int * list;
  int j;

  // Handle trivial case
  if(tree == NULL) return NULL;

  // Calculate maximum number of nodes in the tree from the tree depth
  maxnodes = 1;
  depth = bt_depth(tree);
  for(j = 0; j < depth; j++)
  {
    maxnodes += pow(2, j);
  }

  // Allocate memory for the list; we need two ints for each value plus the
  // first value in the list to indicate length
  list = (int *) malloc( ((maxnodes * 2)+1) * sizeof(int));
  length = bt_encode_preorder(list, tree, 1);
  list[ 0 ] = length;
  return list;
}

int main()
{
  struct BTnode * tree;
  struct BTnode * newtree;
  int * list;
  int i;

  /* Provided example

        5
       / \
      3   2
         / \
        2   1
       / \
      9   9
  */
  tree = bt_node_create(5);
  bt_add_left(tree, 3);
  struct BTnode * temp = bt_add_right(tree, 2);
  bt_add_right(temp, 1);
  temp = bt_add_left(temp, 2);
  bt_add_left(temp, 9);
  bt_add_right(temp, 9);
  printf("T (traversed in pre-order):  ");
  bt_print_preorder(tree);
  printf("\n");

  list = encode(tree);
  printf("T (encoded as integer list): ");
  for(i = 1; i < list[0]; i++)
    printf("%d ", list[i]);
  printf("\n");

  newtree = decode(list);
  printf("T' (decoded from int list):  ");
  bt_print_preorder(newtree);
  printf("\n\n");

  // Free memory
  bt_node_delete(tree);
  bt_node_delete(newtree);
  free(list);
  return 0;
}

```

Saved this as `encode.c` then compiled and executed. This program uses the example tree you provided, and I've tested it on a few others successfully.

```
$ gcc -Wall -lm -o encode encode.c
$ ./encode
T (traversed in pre-order):  5 3 2 2 9 9 1
T (encoded as integer list): 5 3 0 2 2 9 0 9 0 0 1 0 0 0
T' (decoded from int list):  5 3 2 2 9 9 1

```

# Answer
> 2 votes
My code encodes the tree in a preorder traversal, each leaf in two ints (its data followed by 0) and each internal node in one int (its data followed by its left child, then its right). For a complete binary tree (as you define it) with n nodes, n must be odd, and there are (n+1)/2 leaves and (n-1)/2 internal nodes, so that's 3n/2+1/2 integers for the encoding.

warning: untested, just typed it in.

```
struct node {
  int data;
  struct node *left, *right;
};

void encodeInternal(struct node *root, vector<int> *buf) {
  buf->push_back(root->data);
  if (root->left) {
    encodeInternal(root->left, buf);
    encodeInternal(root->right, buf);
  } else {
    buf->push_back(0);
  }
}
int *encode(struct node *root) {
  vector<int> buf;
  encodeInternal(root, &buf);
  return &buf[0];
}

struct decodeResult {
  int encoded_size;
  struct node *n;
}
struct decodeResult decodeInternal(int *array) {
  struct node *n = (struct node*)malloc(sizeof(struct node));
  n->data = array[0];
  if (array[1] == 0) {
    n->left = n->right = NULL;
    return (decodeResult){2, n};
  } else {
    decodeResult L = decodeInternal(array + 1);
    decodeResult R = decodeInternal(array + 1 + L.encoded_size);
    n->left = L.n;
    n->right = R.n;
    return (decodeResult){1 + L.encoded_size + R.encoded_size, n};
  }
}
struct node *decode(int *array) {
  return decodeInternal(array).n;
}

```

# Answer
> 2 votes
### Scala:

```
trait Node {
  def encode (): Array[Int]
}

case object Node {
  def decode (a: Array[Int]): InnerNode = {
    if (a.length == 1) InnerNode (a(0)) else {
      val r = InnerNode (a(1))
      val l = decode (a.tail.tail)
      InnerNode (a(0), l, r)
    }
  }
}

case object Leaf extends Node {
  def encode (): Array[Int] = Array.empty
}

case class InnerNode (val data: Int, var l: Node=Leaf, var r: Node=Leaf) extends Node {
  def encode (): Array[Int] = Array (data) ++ r.encode () ++ l.encode ()
}

object BinTreeTest extends App {
  println (Node.decode (Array (1, 2, 3, 4, 5)).encode.mkString (", "))
}

```

This is an approach which uses deprecated syntax, but compiles without error in Scala 2.9.1 . It generates a Tree and decodes every encoded Tree to the same Array as used for encoding. Maybe I get somehow rid of the deprecated warnings today.

Wow - that was a simple one. First idea worked immediately.

# Answer
> 1 votes
Here's my try. It stores the tree in an array of size 2\**depth+1. It uses `a[0]` to hold the size, and `a[size]` to hold the index of the first "empty node" it encounters in a depth-first traversal. (An empty node is the place where a child would be stored if the parent had one). Each empty node holds the index of the next empty node that will be encountered.

This scheme avoids reserving bits to mark the presense children, so each node can use the full integer range. It also allows unbalanced trees - a parent can have only one child.

output:

```
empty tree:  [0]
head node only:  [2,5,0]
example tree: [16,5,3,2,5,14,2,1,0,0, 0,0,9,9,15,0,4];

```

The Encoder:

```
//utility
 int findDepth(Node* n) {
    int l = 0 ,r = 0;
    if (n) {
       l = 1 + findDepth(n->left);
       r = 1 + findDepth(n->right);
    }
    return ( l > r ) ? l : r;
 }

//Encode Function
 int* encodeTree(Node* head) {
    int* out;
    int depth = findDepth(head);
    int size = depth>0;
    while (depth--) size*=2;
    out = calloc(size+1,sizeof(int));
    out[0]=size;
    encodeNode(head, out,1, out+size);
    return out;
 }

 void encodeNode(Node* n, int* a, int idx, int* pEmpty) {
    if (n) {
       a[idx]=n->data;
       encodeNode(n->left,a,idx*2,pEmpty);
       encodeNode(n->right,a,idx*2+1,pEmpty);
    }
    else if (idx<a[0]) {
       *pEmpty = idx;
       pEmpty = a+idx;
    }
 }

```

The Decoder:

```
 //Decode Function
 Node* decodeArray(int* a) {
    return (a[0]) ?  decodeNode(a,1,a+a[0]) : NULL;
 }

 Node* decodeNode(int* a, int idx, int* pEmpty) {
    Node* n = NULL;
    if (idx== *pEmpty)
       *pEmpty=a[idx];
    else {
       n = calloc(1,sizeof(Node));
       n->data = a[idx];
       if (idx*2<a[0]) {
          n->left = decodeNode(a, idx*2, pEmpty);
          n->right = decodeNode(a, idx*2+1, pEmpty);
       }
    }
    return n;
 }

```

---

(thanks @daniel sobral for fixing the formatting)

---
Tags: code-challenge, tree-traversal
---