title: Are these dice nontransitive?

text:
# Question
Title: Are these dice nontransitive?
Nontransitive dice are nice little toys that defy our intuition in probability theory. We'll need a few definitions for this challenge:

Consider two dice *A* and *B* which are thrown at the same time. We say that *A* **beats** *B* if the probability of *A* showing a larger number than *B* is strictly greater than the probability of *B* showing a larger number than *A*.

Now consider a set of three dice, with labels *A*, *B*, *C*. Such a set of dice is called **nontransitive** if

* either *A* beats *B*, *B* beats *C* and *C* beats *A*
* or *C* beats *B*, *B* beats *A* and *A* beats *C*.

As one of my favourite examples, consider the Grime dice, which have the following sides:

```
A: 3 3 3 3 3 6
B: 2 2 2 5 5 5
C: 1 4 4 4 4 4

```

Interestingly, the mean of each die is 3.5, just like a regular die.

One can show that:

* *A* beats *B* with a probability of 7/12.
* *B* beats *C* with a probability of 7/12.
* *C* beats *A* with a probability of 25/36.

Now these particular dice are even weirder. If we roll each die twice and add up the results, the order of which beats which gets reversed:

* *B* beats *A* with a probability of 85/144.
* *C* beats *B* with a probability of 85/144.
* *A* beats *C* with a probability of 671/1296.

Let's call a set of dice with this property **Grime-nontransitive**.

On the other hand, if the dice retain their original cycle when using two throws, we call them **strongly nontransitive**. (If there is no cycle at all for two throws, we simply call them *nontransitive*.)

## The Challenge

Given three six-sided dice, determine which of the above properties this set has, and output one of the following strings: `none`, `nontransitive`, `Grime-nontransitive`, `strongly nontransitive`.

You may write a program or function, take input via STDIN, command-line argument, prompt or function argument, and write the result to STDOUT or return it as a string.

You may assume that all sides are non-negative integers. You cannot assume that the sides or the dice are in any particular order. You can take input in any convenient list or string format.

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

```
none
1 2 3 4 5 6, 6 5 4 3 2 1, 1 3 5 2 4 6
1 1 1 6 6 6, 4 4 4 5 5 5, 5 5 5 5 5 5
1 1 2 5 6 6, 2 2 3 4 4 6, 2 3 3 4 4 5
0 1 2 3 4 5, 1 1 2 3 3 5, 1 2 2 2 3 5
3 13 5 7 13 7, 5 7 11 5 7 13, 5 9 13 5 7 9

nontransitive
1 2 2 4 6 6, 1 2 3 5 5 5, 2 3 4 4 4 4
1 4 4 4 4 4, 2 2 2 4 5 6, 2 3 3 3 5 5
1 2 1 6 5 6, 3 1 3 6 2 6, 2 4 2 4 4 5
3 4 6 6 7 7, 4 4 4 7 7 7, 5 5 5 5 6 7
2 5 11 11 14 14, 5 5 5 14 14 14, 8 8 8 8 8 17

Grime-nontransitive
3 3 3 3 3 6, 2 2 2 5 5 5, 1 4 4 4 4 4
1 1 4 5 5 5, 2 2 2 3 6 6, 3 3 3 4 4 4
2 1 4 6 4 4, 2 4 5 2 3 5, 3 3 6 3 3 3
11 11 13 15 15 16, 12 12 12 13 16 16, 13 13 13 14 14 14
4 4 7 16 19 19, 4 7 13 13 13 19, 4 10 10 10 16 19

strongly nontransitive
2 2 2 5 5 5, 2 3 3 3 5 5, 1 1 4 5 5 5
2 2 2 3 6 6, 2 2 2 5 5 5, 2 2 4 4 4 5
1 5 1 3 6 5, 6 6 4 2 2 1, 5 3 4 3 4 2
0 0 2 4 4 5, 0 1 1 3 5 5, 1 1 2 3 4 4
1 1 9 17 17 21, 1 5 5 13 21 21, 5 5 13 13 13 17

```

If you want to test your code even more thoroughly, Peter Taylor was kind enough to write a reference implementation, which classified all ~5000 sets of dice with sides 1 to 6 and a mean of 3.5. **Pastebin link**

# Answer
# Dyalog APL, ~~107~~ 100 bytes

~~`{({+/×+/¨,¨×⍵∘.-¨1⌽⍵}{3≠|a←⍺⍺⍵:1⋄a=b←⍺⍺∘.+⍨¨⍵:2⋄3+a=-b}⍵)⊃(⊂'none'),'strongly '⍬'Grime-',¨⊂'nontransitive'}`~~

`{T←{+/×+/¨∊¨×⍵∘.-¨1⌽⍵}⋄3≠|S←T⍵:'none'⋄N←'nontransitive'⋄S=D←T∘.+⍨¨⍵:'strongly ',N⋄S=-D:'Grime-',N⋄N}`

(Thanks @Tobia for this simpler, shorter, better solution)

Basics:

* assignment
* statement separator
* `{}` lambda form
* `⍺⍵` left and right argument
* `A:B` guard ("if `A` then return `B`")

`T` is a function that returns 3 if A beats B, B beats C, and C beats A; -3 if the exact opposite is the case; and something inbetween otherwise. In detail:

* `1⌽⍵` is the one-rotation of . If  is ABC, the rotation is BCA.
* `∘.-` computes a subtraction table between two vectors (`1 2...10 ∘.× 1 2...10` would be the multiplication table we know from school). We apply this between each (`¨`) item of  and its corresponding item in `1⌽⍵`.
* `×` signum of all numbers in the subtraction tables
* `∊¨` flatten each table
* `+/¨` and sum it. We now have three numbers that represent balances: number of winning minus losing cases for each of A vs B, B vs C, C vs A.
* `×` signum of those
* `+/` sum

Then handle the cases in turn:

* `3≠|S←T⍵:'none'` if `T⍵`'s absolute value isn't 3, return 'none'
* `N←'nontransitive'` we'll need this word a lot
* `S=D←T∘.+⍨¨⍵:'strongly ',N` compute `T` for pairs of dice (`∘.+⍨¨⍵` ←→ `⍵((∘.+)¨)⍵`) and return "strongly..." if the same relationships among ABC still hold
* `S=-D:'Grime-',N` ⍝ "Grime" if the relationships are in the opposite directions
* `N` if all else fails, just "nontransitive"
> 5 votes

# Answer
# Python 2, 269

Here's a nice little expression that evaluates to a function. It accepts three lists of integers. Passes all test cases.

```
lambda A,B,C,w=lambda A,B:cmp(sum(cmp(a,b)for a in A for b in B),0),x=lambda A,B:cmp(sum(cmp(a+c,b+d)for a in A for b in B for c in A for d in B),0): (w(A,B)==w(B,C)==w(C,A)!=0)*((x(A,B)==x(B,C)==x(C,A))*["","strongly ","Grime-"][x(A,B)*w(A,B)]+"nontransitive")or"none"

```
> 13 votes

# Answer
# J - 311 257 bytes

Update (13 Jan 2015):

```
g=:4 :'(+/,x>/y)>+/,y>/x'
h=:4 :'(,+/~x)g,+/~y'
f=: 3 :0
'a b c'=:y
if. (b g a)*(c g b)*a g c do.
a=.2{y
c=.0{y
end.
'none'([`]@.((a g b)*(b g c)*c g a))((''([`]@.((b h a)*(c h b)*a h c))'Grime-')([`]@.((a h b)*(b h c)*c h a))'strongly '),'nontransitive'
)

```

Explanation: Using Gerunds, simplify the `if.`s to `@.`s.

## Older version:

First try at both coding in J as well as golfing.

```
g=:4 :'(+/,x>/y)>+/,y>/x'
h=:4 :'(,+/~x)g,+/~y'
f=: 3 :0
'a b c'=:y
if. (b g a)*(c g b)*a g c do.
a=.2{y
c=.0{y
end.
if. (a g b)*(b g c)*c g a do.
if. (a h b)*(b h c)*c h a do.
'strongly nontransitive'
elseif. (b h a)*(c h b)*a h c do.
'Grime-nontransitive'
elseif. do.
'nontransitive'
end.
else.
'none'
end.
)

```

Run it using a syntax similar to following (extra spaces for clarity):

```
f 3 6 $          1 1 9 17 17 21, 1 5 5 13 21 21, 5 5 13 13 13 17

```

Explanation:

`g` is defined as a diad taking two arrays that tells if first dice beats second dice
`h` is defined as a diad taking two arrays that tells if throwing twice and summing, does first dice beat second
`f` is a monad that takes a table and returns a string with the right answer

Edit: Fix a mistake in Grime-nontransitive condition (replacing `,` with `*`)
> 2 votes

# Answer
# Matlab (427)

It is not that short and I am sure it can be golfed a lot more, I just tried to solve this challenge because I thought it was a very fun task, so thanks **@MartinBüttner** for creating this challenge!

```
a=input();b=input();c=input();
m = 'non';l=@(a)ones(numel(a),1)*a;n=@(a,b)sum(sum(l(a)>l(b)'));g=@(a,b)n(a,b)>n(b,a);s=@(a,b,c)sum([g(a,b),g(b,c),g(c,a)]);
x=s(a,b,c);y=s(a,c,b);if x~=3 && y~=3;m=[m,'e'];else m=[m,'transitive'];o=ones(6,1);a=o*a;a=a+a';a=a(:)';b=o*b;b=b+b';b=b(:)';c=o*c;c=c+c';c=c(:)';u=s(a,b,c);
v=s(a,c,b);if u==3|| v==3;if x==3&&u==3 || y==3&&v==3 m=['strongly ',m];else m=['Grime-',m];end;end;end;disp(m);

```

Here the full length code with some comments if you want to try to understand what's going on. I included some test cases hare and excluced the input commands:

```
%nontransitive
% a = [1 2 2 4 6 6];
% b = [1 2 3 5 5 5];
% c = [2 3 4 4 4 4];

%none
% a = [1 2 3 4 5 6];
% b = [6 5 4 3 2 1];
% c = [1 3 5 2 4 6];

%grime nontransitive
% a = [3 3 3 3 3 6];
% b = [2 2 2 5 5 5];
% c = [1 4 4 4 4 4];

%strongly nontransitive
% a = [2 2 2 5 5 5];
% b = [2 3 3 3 5 5];
% c = [1 1 4 5 5 5];

m = 'non';

l=@(a)ones(numel(a),1)*a;
n=@(a,b)sum(sum(l(a)>l(b)'));
%input as row vector, tests whether the left one beats the right one:
g=@(a,b)n(a,b)>n(b,a);
s=@(a,b,c)sum([g(a,b),g(b,c),g(c,a)]);
%if one of those x,y has the value 3, we'll have intransitivity
x=s(a,b,c);
y=s(a,c,b);
if x~=3 && y~=3 %nontransitive
    m=[m,'e'];
else %transitive
    m=[m,'transitive'];
    o=ones(6,1);
    a=o*a;a=a+a';a=a(:)'; %all possible sums of two elements of a
    b=o*b;b=b+b';b=b(:)';
    c=o*c;c=c+c';c=c(:)';
    u=s(a,b,c);
    v=s(a,c,b);

    %again: is u or v equal to 3 then we have transitivity
    if u==3 || v==3 %grime OR strongly
        % if e.g. x==3 and u==3 then the 'intransitivity' is in the same
        % 'order', that means stronlgy transitive
        if x==3 && u==3 || y==3 && v==3%strongly
            m=['strongly ',m];
        else %grime
            m=['Grime-',m];
        end
    end
end

disp(m);

```
> 1 votes

# Answer
## Pyth 129 ~~133~~

```
Lmsd^b2Msmsm>bkGHDPNK-ghNeNgeNhNR?^tZ<KZKZAGHmsdCm,PkP,yhkyekm,@Qb@QhbUQ?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive

```

Try it here, or at least you could, but the online `eval` doesn't seem to like lists of lists :( If you want to try it there, manually store a list of 3 dice into a variable not used by the program and then replace all instances of `Q` with that variable. A sample initialization:

```
J[[3 3 3 3 3 6)[2 2 2 5 5 5)[1 4 4 4 4 4))

```

This passes all of Martin's test cases, I haven't the heart go through all of Peter's cases :P

Explanation (this is gonna be a doozy)

```
Lmsd^b2

```

Pretty simple, makes a function `y` that returns the sum of each Cartesian pair of values in an iterable. Equivalent to: `def y(b):return map(lambda d:sum(d),product(b,repeats=2))`. This is used to create many-sided dies that simulate throwing the regular dies twice.

```
Msmsm>bkGH

```

Defines a function `g` of 2 arguments that returns how many times a die beats another. Equivalent to `def g(G,H):return sum(map(lambda k:sum(map(lambda b:b>k,G)),H)`.

```
DPNK-ghNeNgeNhNR?^tZ<KZKZ

```

Defines a funtion `P` that takes a list of two dice as its argument. This returns -1 if the first die 'loses', 0 for a tie and 1 if the first die 'wins'. Equivalent to:

```
def P(N):
 K=g(N[0],N[-1]) - g(N[-1],N[0])
 return -1**(K<0) if K else 0

```

The `AGH` assigns acts like a python 2-tuple assignment. Essentially `G,H=(result)`

```
msdCm,PkP,yhkyekm,@Qb@QhbUQ

```

Going to explain backwards through the maps. `m,@Qb@QhbUQ` iterates over b=0..2 and generates 2-tuples of dice with index b and index b+1. This gives us dice (A,B),(B,C),(C,A) (pyth automatically mods indexes by the length of the list).

Next, `m,PkP,yhkyek` iterates over the result of the previous map, with each dice pair being stored in k over each run. Returns `tuple(P(k),P(tuple(y(k[0]),y(k[-1]))))` for each value. That boils down to \`((A beats B?, 2\*A beats 2\*B), (B beats C?, 2\*B beats..)).

Finally, `msdC` sums the values of the previous map after it has been zipped. The zip causes all of the single dice 'beats' values in the first tuple, and the double dice values in the second.

```
?"none"|!G%G3s[*!+GH"Grime-"*qGH"strongly ""nontransitive

```

A gross thing that prints out the results. If G is 0 or not divisible by 3, this catches bot +/- 3, (`|!G%G3`), prints `none`, otherwise prints the sum of the follwing list: `[not(G+H)*"Grime",(G==H)*"strongly ","nontransitive"]`. I think the booleans are fairly self-explanatory with regard to the definitions in the question. Do note that G cannot be zero here, as that is caught by the previous check.
> 1 votes

# Answer
# J (204)

Way too long, could probably be golfed a lot by having a more efficient system for picking the right string.

```
f=:3 :'(<,>)/"1+/"2>"1,"2(<,>)/L:0{(,.(1&|.))y'
n=:'nontransitive'
d=:3 :0
if.+/*/a=.f y do.+/*/b=.f<"1>,"2+/L:0{,.~y if.a-:b do.'strongly ',n elseif.a-:-.b do.'Grime-',n elseif.do.n end.else.'none'end.
)

```
> 1 votes

# Answer
## JavaScript - 276 bytes

```
function(l){r=function(i){return l[i][Math.random()*6|0]};p=q=0;for(i=0;j=(i+1)%3,i<3;++i)for(k=0;k<1e5;++k){p+=(r(i)>r(j))-(r(i)<r(j));q+=(r(i)+r(i)>r(j)+r(j))-(r(i)+r(i)<r(j)+r(j))}alert((a=Math.abs)(p)>5e3?((a(q)>5e3?p*q>0?'strongly ':'Grime-':'')+'nontransitive'):'none')}

```

I'm not really good in probability, so to be sure of my results, I prefer to just throw the dice hundreds of thousands times.

The expression evaluates to a function, that should be called with only one argument: an array of three arrays of integers. Check the Fiddle to be able to run the code by yourself.

Here is the ungolfed version:

```
function (diceList) {
    var getRandomValue = function (idDie) {
        return diceList[idDie][Math.floor(Math.random() * 6)];
    };

    var probabilitySimpleThrow = 0;
    var probabilityDoubleThrow = 0;

    for (var idDieA = 0; idDieA < 3; ++idDieA)
    {
        var idDieB = (idDieA + 1) % 3;
        for (var idThrow = 0; idThrow < 1e5; ++idThrow)
        {
            probabilitySimpleThrow += getRandomValue(idDieA) > getRandomValue(idDieB);
            probabilitySimpleThrow -= getRandomValue(idDieA) < getRandomValue(idDieB);

            probabilityDoubleThrow += getRandomValue(idDieA) + getRandomValue(idDieA) > getRandomValue(idDieB) + getRandomValue(idDieB);
            probabilityDoubleThrow -= getRandomValue(idDieA) + getRandomValue(idDieA) < getRandomValue(idDieB) + getRandomValue(idDieB);
        }
    }

    if (Math.abs(probabilitySimpleThrow) > 5e3) {
        if (Math.abs(probabilityDoubleThrow) > 5e3) {
            if (probabilitySimpleThrow * probabilityDoubleThrow > 0) {
                var result = 'strongly ';
            }
            else {
                var result = 'Grime-';
            }
        }
        else {
            var result = '';
        }

        result += 'nontransitive';
    }
    else {
        var result = 'none';
    }

    alert(result);
}

```
> 0 votes

---
Tags: code-golf, probability-theory
---


# Question
Title: Print the fingering for the note on a saxophone
Your challenge is, given a series of notes, print the fingerings that minimize the amount of movements you need to make (explained below).

My not standard way of transforming fingerings to text: The `|` line separates the left and right hand. Use `1` for the index finger, `2` for the middle finger and `3` for the ring finger. Use `a-d` for the right hand to represent the side keys played by the pinkies (and just `a` and `b` for the left hand).

An example for low A#/Bb:

which would be written as `123d|123b`.

The side keys, which are hit with the part of your hand between the thumb and index finger, are labeled as `e`, `f`, and `g`.

In addition, there is a little key between the right hand's `1` and `2` used for playing `Bb`. This is called the `i` key.

The octave key is labeled `o`

These are the fingerings (note that `b` means flat, not the note `B` which is uppercase):

```
A#3 or Bb3: 123d|123b
B3 or Cb4: 123c|123b
B#3 or C4: 123|123b
C#4 or Db4: 123b|123b
D4: 123|123
D#4 or Eb4: 123|123a
E4 or Fb4: 123|12
E#4 or F4: 123|1
F#4 or Gb4: 123|2
G4: 123|                // Note that the | is still necessary
G#4 or Ab4: 123a|
A4: 12|
A#4 or Bb4: 12|g OR 1i| OR 1|1 OR 1|2
B4 or Cb5: 1|
B#4 or C5: 2| OR 1|f
C#5 or Db5: |  OR o3|  // No fingers down for first fingering
D5: o123|123
/* All fingerings from D5 - B#5/C6 are the same as the lower octave
   but with the octave key (prefixed with o) */
C#6 or Db6: o|
D6: of|
D#6 or Eb6: oef|
E6 or Fb6: oef|e
E#6 or F6: oefg|

```

**Input**: A series of notes separated by semicolons.

**Output**: A series of fingerings separated by semicolons. If there is more than one way to finger a certain note, the program must chose the fingering that minimizes *distance* from its neighbors. If it is the only note or there is a tie, you may output any fingering.

A fingering's *distance* from another is how many fingers you would have to lift/press to change the note.

Example: `12| --> 1|` has a distance of 1 because you have to lift finger 2. Example: `12|g --> 12|` has a distance of 1 because you only have to lift one side key.

Test cases:

```
C#5;D5;C#5 --> o3|;o123|123;o3|

```

**Bonus**: -100 if your program takes an audio file (probably midi) as input and outputs the fingering corresponding to the notes played.

# Answer
> 2 votes
## Python 3, ~~528~~ 525 bytes (ouch!)

Not the prettiest code in the world, but I think it works. Calculates the shortest overall distance by trying all possible fingering combinations, so also not the most efficient.

```
from itertools import*
def f(x,y):a,b=x.split('|');c,d=y.split('|');return len(set(a)^set(c))+len(set(b)^set(d))
print(";".join(min(product(*["zd|zb zc|zb z|zb zb|zb z|z z|za z|12 z|1 z|2 z| za| 12| 12|g&1i|&1|1&1|2 1| 2|&1|f |&o3| oz|z oz|za oz|12 oz|1 oz|2 oz| oza| o12| o12|g&o1i|&o1|1&o1|2 o1| o2|&o1|f o| of| oef| oef|e oefg|".replace('z','123').split()["C D EF G A B".find(n[0])+" #".find(n[1:-1])+12*int(n[-1])-46].split('&') for n in input().split(';')]),key=lambda x:sum(f(x[i],x[i+1]) for i in range(len(x)-1)))))

```

Not many tricks. Saved a bit by a string-replace on "123". Simplified distance calculation by doing each half separately. Note name to pitch calculation is fairly tight but should be able to golf the rest down.

---
Tags: code-golf, music
---


title: Build a MU puzzle solver

text:
# Question
Title: Build a MU puzzle solver
The MU puzzle is a puzzle in which you find out whether you can turn `MI` into `MU` given the following operations:

1. If your string ends in `I`, you may add a `U` to the end. (e.g. `MI -> MIU`)
2. If your string begins with `M`, you may append a copy of the part after `M` to the string.
(e.g. `MII -> MIIII`)
3. If your string contains three consecutive `I`'s, you may change them into a `U`.
(e.g. `MIII -> MU`)
4. If your string contains two consecutive `U`'s, you may delete them. (e.g. `MUUU -> MU`).

Your task is to build a program that determines whether this is doable for any start and finish strings.

Your program will take two strings as input. Each string will consist of the following:

* one `M`.
* a string of up to twenty-nine `I`'s and `U`'s.

Your program will then return `true` (or your programming language's representation thereof/YPLRT) if the second string is reachable from the first string, and `false` (or YPLRT) if it is not.

Example inputs and outputs:

```
MI  MII
true

MI  MU
false

MIIIIU  MI
true

```

The shortest code in any language to do this wins.

# Answer
> 8 votes
# SWI Prolog, 183 characters

```
m(A,A).
m([i],[i,u]).
m([i,i,i|T],B):-m([u|T],B).
m([u,u|T],B):-m(T,B).
n([m|A],[m|B]):-(m(A,B);append(A,A,X),m(X,B)).
n(A,B):-m(A,B).
s(A,B):-atom_chars(A,X),atom_chars(B,Y),n(X,Y).

```

How about some Prolog, (since nobody has answered in 6 months). To run, just use "s(mi,mu)." The code breaks up atoms into chars, then searches for the solution.

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


title: Implement slow sorting algorithm

text:
# Question
Title: Implement slow sorting algorithm
All good coders know some good sorting algorithms like quicksort or merge sort. There is also slow sorting algorithms, e.g. bubble sort and insertion sort.

But those are such easy to implement and so, so efficient. Too efficient. Your task is to create very slow sorting algorithm.

Please attach the Big O notation of your algorithm to your post to help us rate them. Also, please describe how your sorting algorithm works.

Input given trough STDIN. The first line contains number of arguments, and arguments are given after that. The arguments are integers in range from 0 to 105 and there are maximum 103 of them.

Output is list sorted and printed line by line into STDOUT sorted beginning from decending order.

You may not use any random numbers or any other random sources.

This is .

# Answer
> 6 votes
# Mathematica, Time complexity O(n * n!), Space complexity O(n!)

```
list = RandomInteger[10, 7]
(*{5, 5, 4, 10, 5, 10, 5}*)
permutations = Permutations@list;
Cases[permutations, l_ /; And @@ Thread[Most[RotateLeft@l - l] >= 0]][[1]]
(*{4, 5, 5, 5, 5, 10, 10}*)

```

This generates all permutations, discards all that aren't sorted, and then picks the first one.

Therefore, it will use O(n!) memory and O(n!) time to generate all the permutations. Then it will use O(n!) time again, to iterate through the permutations, while needing O(n) for *each* of them to check that they are sorted.

Note that this is both the worst case *and* best case complexity.

# Answer
> 0 votes
# CJam, Time complexity O(n(2n+1)\*log(n)), Space complexity O(n)

```
q~:Q,_#2#{Q$;}*Q$p

```

This sorts the array **n2n \+ 1** times using Merge Sort which has time complexity of **n log(n)**

But really, this can be extended to any time complexity with a final output in range of Big Integer.

(Don't) try it online here

Input is like:

```
[1 4 2 3 1 5 6 1 2344 343 1 2 3 23 1 2 32 1 2 3 4]

```

and output is the sorted array

A graph comparing **n * n!** with **n2n + 1 * log(n)**

---
Tags: popularity-contest, sorting
---


title: Computer Generated Textured Wall Paint

text:
# Question
Title: Computer Generated Textured Wall Paint
The paint on the walls in my room has a random, almost fractal-like, 3-dimensional texture:

In this challenge you will write a program that generates random images that look like they could be part of my walls.

Below I've collected 10 images of different spots on my walls. All have roughly the same lighting and all were taken with the camera one foot away from the wall. The borders were evenly cropped to make them 2048 by 2048 pixels, then they were scaled to 512 by 512. The image above is image A.

**These are only thumbnails, click images to view at full size!**

**A:**  **B:**  **C:**  **D:**  **E:**

**F:**  **G:**  **H:**  **I:**  **J:**

Your task is to write a program that takes in a positive integer from 1 to 216 as a random seed, and for each value generates a distinct image that looks like it could have been the "eleventh image" of my wall. If someone looking at my 10 images and a few of yours can't tell which were computer generated then you've done very well!

Please show off a few of your generated images so viewers can see them without having to run the code.

I realize that the lighting in my images is not perfectly uniform in intensity or color. I'm sorry for this but it's the best I could do without better lighting equipment. Your images do not need to have variable lighting (though they could). The texture is the more important thing to focus on.

# Details

* You may use image processing tools and libraries.
* Take the input in any common way you desire (command line, stdin, obvious variable, etc).
* The output image can be in any common lossless image file format, or it can just be displayed in a window/bowser.
* You may programmatically analyze my 10 images but **don't assume that everyone running your code has access to them.**
* You must generate the images programmatically. You may not hard-code a slight variant of one of my images or some other stock image. (People would vote you down for this anyway.)
* You may use built-in pseudorandom number generators and assume the period is 216 or more.

# Scoring

This is a popularity contest so the highest-voted answer wins.

# Answer
# GLSL (+ JavaScript + WebGL)

**Live demo** **|** **GitHub repository**

## How to use

Reload the page for a new random image. If you want to feed in a particular seed, open your browser's console and call `drawScreen(seed)`. The console should display the seed used on load.

I haven't really tested this on a lot of platforms, so let me know if it doesn't work for you. Of course, your browser needs to support WebGL. Errors are displayed either in the column on the left, or in the browser's console (depending on the type of error).

**New:** You can now bring the walls to life a bit, by ticking the "movable light source" checkbox.

## What is this sorcery?

I've got this WebGL boilerplate code floating around my GitHub account, which I use every now and then to quickly prototype some 2D graphics things in WebGL. With some shader magic, we can also make it look slightly 3D, so I thought that was the quickest way to get some nice effects going. Most of the setup is from that boilerplate code, and I'm considering that a library for this submission and won't include it in this post. If you're interested, have a look at the main.js on GitHub (and the other files in that folder).

All the JavaScript does is to set up a WebGL context, store the seed in a uniform for the shader, and then render a single quad over the entire context. The vertex shader is a simple passthrough shader, so all the magic happens in the fragment shader. That's why I called this a GLSL submission.

The largest part of the code is actually to generate the Simplex noise, which I found on GitHub. So I'm omitting that as well in the code listing below. The important part is, it defines a function `snoise(vec2 coords)` which returns simplex noise without using a texture or array lookup. It's not seeded at all, so the trick to getting different noise is to use the seed in determining where to do the lookup.

So here goes:

```
#ifdef GL_ES
precision mediump float;
#endif
#extension GL_OES_standard_derivatives : enable

uniform float uSeed;
uniform vec2 uLightPos;

varying vec4 vColor;
varying vec4 vPos;

/* ... functions to define snoise(vec2 v) ... */

float tanh(float x)
{
    return (exp(x)-exp(-x))/(exp(x)+exp(-x));
}

void main() {
    float seed = uSeed * 1.61803398875;
    // Light position based on seed passed in from JavaScript.
    vec3 light = vec3(uLightPos, 2.5);
    float x = vPos.x;
    float y = vPos.y;

    // Add a handful of octaves of simplex noise
    float noise = 0.0;
    for ( int i=4; i>0; i-- )
    {
        float oct = pow(2.0,float(i));
        noise += snoise(vec2(mod(seed,13.0)+x*oct,mod(seed*seed,11.0)+y*oct))/oct*4.0;
    }
    // Level off the noise with tanh
    noise = tanh(noise*noise)*2.0;
    // Add two smaller octaves to the top for extra graininess
    noise += sqrt(abs(noise))*snoise(vec2(mod(seed,13.0)+x*32.0,mod(seed*seed,11.0)+y*32.0))/32.0*3.0;
    noise += sqrt(abs(noise))*snoise(vec2(mod(seed,13.0)+x*64.0,mod(seed*seed,11.0)+y*64.0))/64.0*3.0;

    // And now, the lighting
    float dhdx = dFdx(noise);
    float dhdy = dFdy(noise);
    vec3 N = normalize(vec3(-dhdx, -dhdy, 1.0)); // surface normal
    vec3 L = normalize(light - vec3(vPos.x, vPos.y, 0.0)); // direction towards light source
    vec3 V = vec3(0.0, 0.0, 1.0); // direction towards viewpoint (straight up)
    float Rs = dot(2.0*N*dot(N,L) - L, V); // reflection coefficient of specular light, this is actually the dot product of V and and the direction of reflected light
    float k = 1.0; // specular exponent

    vec4 specularColor = vec4(0.4*pow(Rs,k));
    vec4 diffuseColor = vec4(0.508/4.0, 0.457/4.0, 0.417/4.0, 1.0)*dot(N,L);
    vec4 ambientColor = vec4(0.414/3.0, 0.379/3.0, 0.344/3.0, 1.0);

    gl_FragColor = specularColor + diffuseColor + ambientColor;
    gl_FragColor.a = 1.0;
}

```

That's it. I might add some more explanation tomorrow, but the basic idea is:

* Choose a random light position.
* Add up a few octaves of noise, to generate the fractal pattern.
* Square the noise to keep the bottom rough.
* Feed the noise through `tanh` to level off the top.
* Add two more octaves for a little bit more texture on the top layer.
* Compute the normals of the resulting surface.
* Run a simple Phong shading over that surface, with specular and diffuse lights. The colours are chosen based on some random colours I picked from the first example image.
> 65 votes

# Answer
# Mathematica Spackling

The app below applies speckling to a random image. Clicking on "new patch" generates a new random image to work with, and then applies the effects according to current settings. The effects are oil painting, Gaussian filter, posterization, and embossing. Each effect can be independently tweaked. The seed for the random number generator can be any integer from 1 to 2^16.

**Update**: The Gaussian filter, which softens the edges, is now the last image effect applied. With this modification, the posterization effect was no longer needed and thus removed.

```
Manipulate[
 GaussianFilter[ImageEffect[ImageEffect[r, {"OilPainting", o}], {"Embossing", e, 1.8}], g],
 Button["new patch", (SeedRandom[seed] r = RandomImage[1, {400, 400}])],
 {{o, 15, "oil painting"}, 1, 20, 1, ContinuousAction -> False, Appearance -> "Labeled"},
 {{e, 1.64, "embossing"}, 0, 5, ContinuousAction -> False, Appearance -> "Labeled"},
 {{g, 5, "Gaussian filter"}, 1, 12, 1, ContinuousAction -> False, Appearance -> "Labeled"},
 {{seed, 1}, 1, 2^16, 1, ContinuousAction -> False, Appearance -> "Labeled"},
 Initialization :> (SeedRandom[seed]; r = RandomImage[1, {400, 400}])]

```

---

## Explanation

The explanation is based on a slightly different version, in which posterization was employed and `GaussianFilter` was applied early on. But it still serves to clarify how each image effect alters an image. The end result is a paint texture with sharper edges. When the Gaussian filter is only applied at the end, the result will be smoother, as the above picture shows.

Let's look at some image effects, one at a time.

Generate a starting image.

```
 r = RandomImage[1, {200, 200}]

```

---

Lena will show us how each image effect transforms a life-like picture.

```
Lena = ExampleData[{"TestImage", "Lena"}]

```

---

An oil painting effect applied to Lena.

```
ImageEffect[Lena, {"OilPainting", 8}]

```

##

An oil painting effect applied to our random image. The effect was intensified (16 instead of 8).

```
 r1 = ImageEffect[r, {"OilPainting", 16}]

```

---

A Gaussian filter effect applied to Lena (not to the oil painting effect version of Lena). The radius is 10 pixels. (In the final version, at the top of this entry, GaussianFilter is applied as the final effect.)

```
 GaussianFilter[Lena, 10]

```

---

A somewhat milder Gaussian filter effect applied to r1. The radius is 5 pixels.

```
 r2 = GaussianFilter[r1, 5]

```

---

An intense posterization effect applied to Lena. (In the final version of the app, I removed posterization. But we'll leave it in the analysis, since the examples in the analysis were based on an earlier version with posterization.)

```
 ImageEffect[Lena, {"Posterization", 2}]

```

---

A posterization effect applied to r2.

```
r3 = ImageEffect[r2, {"Posterization", 4}]

```

---

Embossing Lena

```
 ImageEffect[Lena, {"Embossing", 1.2, 1.8}]

```

---

Embossing r3 completes the image processing. This is intended to look something like the OP's ceiling.

```
 ceilingSample = ImageEffect[r3, {"Embossing", 1.2, 1.8}]

```

---

For the curious, here is Lena with the same image effects applied.
> 33 votes

# Answer
# POV-Ray

A lot of golfing potential, run with `povray /RENDER wall.pov -h512 -w512 -K234543`

First it creates a random texture, but instead of stopping there it transforms the texture into a 3D-heightfield to make the radial shadows from the camera flash more realistic. And for good measure it adds another texture of little bumps on top.
The only way apart from hardcoding the random seed is to use the `clock` variable meant for animations, this is passed with the `-K{number}` flag

```
#default{ finish{ ambient 0.1 diffuse 0.9 }}

camera {location y look_at 0 right x}
light_source {5*y color 1}

#declare R1 = seed (clock); // <= change this

#declare HF_Function  =
 function{
   pigment{
     crackle turbulence 0.6
     color_map{
       [0.00, color 0.01]
       [0.10, color 0.05]
       [0.30, color 0.20]
       [0.50, color 0.31]
       [0.70, color 0.28]
       [1.00, color 0.26]
     }// end color_map
    scale <0.25,0.005,0.25>*0.7
    translate <500*rand(R1),0,500*rand(R1)>
   } // end pigment
 } // end function

height_field{
  function  512, 512
  { HF_Function(x,0,y).gray * .04 }
  smooth
  texture { pigment{ color rgb<0.6,0.55,0.5>}
            normal { bumps 0.1 scale 0.005}
            finish { phong .1 phong_size 400}
          } // end of texture
  translate< -0.5,0.0,-0.5>
}

```
> 13 votes

---
Tags: popularity-contest, graphical-output, image-processing, fractal
---


title: Heaps of trouble

text:
# Question
Title: Heaps of trouble
# Challenge

You must, in the least bytes possible, implement the Binary Heap data structure and each of the following methods that operate on it:

* A function which takes no arguments and returns an empty Heap
* A function which takes a list of arguments with an arbitrary length and returns a Heap containing the elements
* A function which takes two Heaps and merges them into a new Heap, returning it
* A function which removes the root element of the Heap and reorders it accordingly, returning the root and new Heap
* A function which takes an integer and a Heap, inserts it into the Heap, and returns the Heap

# Clarifications

* Your heap must be implemented as linking nodes created with structs, classes, custom types or equivalent, not using an array or list
* You may implement either a max-heap or a min-heap, it is your choice.
* You may assume that only integers are being stored in the heap
* Your functions must be bound to a variable or name (and callable, obviously)
* Standard loopholes are disallowed

## Resources

# Answer
> 3 votes
# Haskell - 217

Golfed version

```
data H=H H Int H|E
l E=0
l(H a _ b)=1+l a+l b
i E x=H E x E
i(H a y b)x|l a>l b=H a u$i b v|1>0=H(i a v)u b where(u,v)|x>y=(x,y)|1>0=(y,x)
f=foldl i E
t E=[]
t(H a x b)=x:t a++t b
m a b=f$t a++t b
p(H a x b)=(x,m a b)

```

Same, but with meaningfull names. Straightforward heap implemented as a binary tree, it can be either `Empty` or `Heap leftBranch element rightBranch`.

```
data Heap=Heap Heap Int Heap|Empty
len Empty=0
len(Heap a _ b)=1+len a+len b
insert Empty x=Heap Empty x Empty
insert(Heap a y b)x
    |len a>len b=Heap a u$insert b v
    |1>0=Heap(insert a v)u b
    where
        (u,v)|x>y=(x,y)
             |1>0=(y,x)
fromList=foldl insert Empty
toList Empty=[]
toList(Heap a x b)=x:toList a++toList b
merge a b=fromList$toList a++toList b
pop(Heap a x b)=(x,merge a b)

```

# Answer
> -1 votes
## Lua - 275 (Already lost :D)

```
function f(s)return loadstring(s)end;f(([[a=f"_{}"b=f"t={...}&sort(t)_t"c=f"z={...}_f('x={'..&concat(z[1],',')..','..&concat(z[2],',')..'}&sort(x)_x')()"d=f"z={...}z=z[1]r=z[#z]&remove(z,#z)_z,r"e=f"z={...}&insert(z[1],z[2])_z[1]"]]):gsub("&","table."):gsub("_","return "))()

```

How it works:

```
function newHeap()
    return {}
end
function insertItemsToHeap(...)
    heap = {...}
    table.sort(heap)
    return heap
end
function margeHeaps(heap1, heap2)
    x = loadstring("return {"..table.concat(heap1,",")..","..table.concat(heap2,",").."}")()
    table.sort(x)
    return x
end
function removeRoot(...)
    z = {...}
    z = z[1]
    r = z[#z]
    table.remove(z,#z)
    return z, r
end
function insertInt(heap, int)
    table.insert(heap, int)
    return heap
end

```

Note: I have no previous experience with Binary Heaps once however, hope this is right.

---
Tags: code-golf, data-structures
---


# Question
Title: Winning Strategies for a String Construction Game
# Background

Alice and Bob play a game called *construct a binary word*. To play the game, you fix a length `n >= 0`, a set `G` of length-`n` binary words called the *goal set*, and a length-`n` string `t` containing the letters `A` and `B`, called the *turn order*. The game lasts for `n` turns, and on turn `i`, the player defined by `t[i]` selects a bit `w[i]`. When the game is over, the players look at the binary word `w` they have constructed. If this word is found in the goal set `G`, Alice wins the game; otherwise, Bob wins.

For example, let's fix `n = 4`, `G = [0001,1011,0010]`, and `t = AABA`. Alice gets the first turn, and she chooses `w[0] = 0`. The second turn is also Alice's, and she chooses `w[1] = 0`. Bob has the third turn, and he chooses `w[2] = 0`. On the final turn, Alice chooses `w[3] = 1`. The resulting word, `0001`, is found in `G`, so Alice wins the game.

Now, if Bob had chosen `w[2] = 1`, Alice could have chosen `w[3] = 0` in her final turn, and still win. This means that Alice can win the game no matter how Bob plays. In this situation, Alice has a *winning strategy*. This strategy can be visualized as a labeled binary tree, which branches at the levels corresponding to Bob's turns, and whose every branch contains a word from `G`:

```
A A B A

-0-0-0-1
    \
     1-0

```

Alice plays by simply following the branches on her turn; no matter which branch Bob chooses, Alice eventually wins.

# Input

You are given as input the length `n`, and the set `G` as a (possibly empty) list of strings of length `n`.

# Output

Your output is the list of turn orders for which Alice has a winning strategy, which is equivalent to the existence of a binary tree as described above. The order of the turn orders does not matter, but duplicates are forbidden.

# Detailed Rules

You can write a full program or a function. In the case of a program, you can choose the delimiter for the input and output, but it must be the same for both. The shortest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
3 [] -> []
3 [000,001,010,011,100,101,110,111] -> [AAA,AAB,ABA,ABB,BAA,BAB,BBA,BBB]
4 [0001,1011,0010] -> [AAAA,BAAA,AABA]
4 [0001,1011,0010,0110,1111,0000] -> [AAAA,BAAA,ABAA,BBAA,AABA,AAAB]
5 [00011,00110,00111,11110,00001,11101,10101,01010,00010] -> [AAAAA,BAAAA,ABAAA,BBAAA,AABAA,AAABA,BAABA,AAAAB,AABAB]

```

### Fun Fact

The number of turn orders in the output is *always* equal to the number of words in the goal set.

# Answer
# Dyalog APL, 59 bytes

`{(a≡,⊂⍬)∨0=⍴a←∪⍵:a⋄(∇h/t)(('A',¨∪),'B',¨∩)∇(~h←⊃¨a)/t←1↓¨a}`

Same algorithm as in @xnor's solution.

```
(a≡,⊂⍬)∨0=⍴a←∪⍵:a
           a←∪⍵    ⍝ "a" is the unique items of the argument
        0=⍴a       ⍝ is it empty?
 a≡,⊂⍬             ⍝ is it a vector that contains the empty vector?
       ∨       :a  ⍝ if any of the above, return "a"

(∇h/t)(('A',¨∪),'B',¨∩)∇(~h←⊃¨a)/t←1↓¨a
                                 t←1↓¨a  ⍝ drop an item from each of "a" and call that "t"
                         ~h←⊃¨a          ⍝ first of each of "a", call that "h", then negate it
                                /        ⍝ use "~h" as a boolean mask to select from "t"
                       ∇                 ⍝ apply a recursive call
(∇h/t)                                   ⍝ use "h" as a boolean mask on "t", then a recursive call
      (('A',¨∪),'B',¨∩)                  ⍝ apply a fork on the results from the two recursive calls:
       ('A',¨∪)                          ⍝   prepend 'A' to each of the intersection
               ,                         ⍝   concatenated with
                'B',¨∪                   ⍝   prepend 'B' to each of the union

```
> 1 votes

# Answer
# Python, 132

```
def f(S,n):
 if n<1:return S
 a,b=[f({x[1:]for x in S if x[0]==c},n-1)for c in'01']
 return{'A'+y for y in a|b}|{'B'+y for y in a&b}

```

Example run:

```
f({'000','001','010','011','100','101','110','111'},3) ==
{'ABA', 'ABB', 'AAA', 'AAB', 'BBB', 'BBA', 'BAB', 'BAA'}

```

This is only kind-of golfed, mostly to show the algorithm. The inputs and output are sets of strings. Python doesn't seem to have the right features to express parts of this compactly, so it would be cool if someone wrote this in a better-suited language.

Here's how the recursion can be expressed mathematically. Unfortunately, PPCG still lacks math rendering, so I'll have to use code blocks.

The objects of interest are sets of strings. Let `|` represent set union and `&` represent set intersection.

If `c` is a character, let `c#S` represent prepending the character `c` to all strings in `S`. Conversely, let the contraction `c\S` be the one-character-shorter strings of `S` that follow initial character `c`, e.g., `0\{001,010,110,111} = {01,10}`.

We can uniquely split a set of strings `S` with chars in `01` by their first character.

```
S = 0#(0\S) | 1#(1\S)

```

Then, we can express the desired function `f` as follows, with the bases cases in the first two lines and the recursive can in the last line:

```
f({})   = {}
f({''}) = {''}
f(S)    = A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S))

```

Note that we don't need to use the length `n`.

Why does this work? Let's think about the move-strings that let Alice win for a set of strings `S`.

If the first character is `A`, Alice can pick the first move ('0' or '1'), letting her choose to reduce the problem to `S0` or `S1`. So now the remaining move-string has to be in at least one of `f(S0)` or `f(S1)`, hence we take their union `|`.

Similarly, if the first character is 'B', Bob gets to pick, and he'll pick the worse one for Alice, so the remaining move-string must be in the intersection (`&`).

The base cases simply check if `S` is empty or not at the end. If we're tracking the length of the strings `n`, by subtracting 1 each time we recurse, the bases can instead be written:

```
f(S) = S if n==0

```

The recursive solution also explains the fun fact that `f(S)` has the same size as `S`. It's true for the base cases, and for the inductive case

```
f(S) = A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S))

```

we have

```
size(f(S)) = size(A#(f(0\S)|f(1\S)) | B#(f(0\S)&f(1\S)))
           = size(A#(f(0\S)|f(1\S))) + size(B#(f(0\S)&f(1\S))))
           = size((f(0\S)|f(1\S))) + size((f(0\S)&f(1\S))))
           = size(f(0\S)) + size(f(1\S))  [since size(X|Y) + size(X&Y) = size(X) + size(Y)]
           = size(0\S) + size(1\S)
           = size(S)

```
> 13 votes

---
Tags: code-golf, game
---


title: Code Golf Image Downloader

text:
# Question
Title: Code Golf Image Downloader
In many challenges, the post contains images, which must be saved to a file in order to be able to work on the problem. This is an especially tedious manual task. We programmers should not have to be subjected to such drudgery. Your task is to automatically download all the images contained in a Code Golf.SE question.

## Rules

* Your program may connect to any part of `stackexchange.com`, but may not connect to any other domains, excepting the locations of the images (i.e., don't bother with a URL shortener).
* An integer *N* is given as input, on the command line or stdin.
* The URL `http://codegolf.stackexchange.com/questions/*N*` is guaranteed to be a valid link to a Code Golf question.
* Each image displayed in the body of question *N* must be saved to a file on the local computer. Either of the following locations is acceptable:
    + The current directory
    + A directory input by the user
* Your program must not save files other than the images in the question body (e.g. user avatars, or images contained in answers).
* Images must be saved with the same file extension as the original.

This is a — write the shortest program you can.

**Validity criterion for answers**

There are various possible edge cases with multiple images of the same name, text with the same name as HTML elements, etc. An answer will be invalidated only if it can be shown to fail on some revision of a question posted before January 10, 2015.

# Answer
> 10 votes
# Mathematica, ~~211~~ 210 bytes

```
i=Import;FileNameTake@#~Export~i@#&/@ImportString["body"/.("items"/.i["http://api.stackexchange.com/2.2/questions/"<>InputString[]<>"?site=codegolf&filter=!*Lgp.gEWHA6BNP.l","JSON"])[[1]],{"HTML","ImageLinks"}]

```

Ungolfed:

```
i = Import;
FileNameTake@#~Export~i@# & /@
 ImportString[
  "body" /. (
    "items" /.
      i["http://api.stackexchange.com/2.2/questions/" <>
        InputString[] <> "?site=codegolf&filter=!*Lgp.gEWHA6BNP.l",
       "JSON"]
  )[[1]],
  {"HTML", "ImageLinks"}
 ]

```

It's pretty straightforward. I've set up a filter for the StackExchange API, which returns only the body of a question. The code retrieves the question information with that filter and parses it as JSON. I select the correct element (the body), and use `ImportString` to parse the HTML and filter out all image URLs. `FileNameTake@#~Export~Import@#` then downloads each of the images and stores it in the current working directory with the same file name as that in the URL.

You can find out the current working directory with `Directory[]`.

In principle, there's a much shorter version, because `ImportString` can actually download all the files right away, instead of just giving me the URLs. But then I lose information about the original file type (since they are converted to `Image` objects upon download), so I can only save them all as the same type (PNG, say).

# Answer
> 8 votes
## Javascript - ~~149~~ 161 bytes

```
$.get("http://codegolf.stackexchange.com/q/"+prompt(),function(e){$(".post-text:first img",e).each(function(e,t){$('<a href="'+t.src+'"download>')[0].click()})})

```

with whitespace

```
$.get('http://codegolf.stackexchange.com/q/' + prompt(), function(d) {
  $('.post-text:first img',d).each(function(i,e){
   $('<a href="' + e.src + '"download>')[0].click();
  })
})

```

script has to be run from stackexchange site to work. ~~Will default to the current page if no question number is specified in the prompt~~

# Answer
> 5 votes
## Python 2 - 241 bytes

Pretty straightforward, can probably be golfed further. I search the site for all occurrences of `img src=` between the first occurrence of `post-text` and the `/div` immediately following that. Each image url is then read and saved to the working directory.

```
import string,sys,urllib,re;o=string.find;u=urllib.urlopen
r=u("http://codegolf.stackexchange.com/q/"+sys.argv[1]).read()
i=o(r,"post-text")
for p in re.findall(r'img src="([^"]*)',r[i:o(r,"/div",i)]):f=open(p[-9:],"wb");f.write(u(p).read())

```

# Answer
> 2 votes
# Mathematica, 195

```
x=XMLElement;c=Cases;i=Import;l=Infinity;FileNameTake@#~Export~i@#&/@(((c[#,x["img",{"src"->e_,_},___]:>e,l]&)@*(c[#,x[_,{__,"id"->"question",__},e_]:>e,l]&)@*(i[#,"XMLObject"] &))@InputString[])

```

This exports images in the same way that Martin did in his Mathematica solution, read his answer for more information about that. This approach is very different from his, instead of parsing the result from the API I parse the HTML page directly. Or rather, I parse the symbolic XML that Mathematica can generate from HTML.

# Answer
> 1 votes
# Python 2 - ~~398~~ ~~342~~ 334 bytes

The program download the SE page, extracts the post part (the post-text div element), finds urls that end in an image extension and downloads them. The images are saved as `img<n>.<ext>` in the current directory.

```
import urllib2 as u,re,sys
z=u.urlopen;i=1
p=z('http://codegolf.stackexchange.com/q/'+sys.argv[1]).read()
s=re.search(r'ss="po(.+?)/di',p,16).group(1)
for L in re.findall('"(h.+?://.*?)"',s):
 b=L.rsplit('.',1)
 if len(b)==2 and b[1].lower() in 'jpg jpeg png gif bmp'.split():
  open('img%u.%s'%(i,b[1]),'wb').write(z(L).read());i+=1

```

This program will also download images that are supplied as a link, not only embedded images. By giving each image a unique filename, name clashes are also avoided.

# Answer
> 1 votes
# Bash - 86 bytes

```
wget -r -l1 -np -Ajpg,jpeg,png,bmp,gif http://codegolf.stackexchange.com/questions/$1

```

Nothing wget won't fix. `-np` prevents wget from entering upper directories(User Imgs) `-A` only grabs files with the extension matching the list presented. `-r` is a recursive download. `-l` prevents wget from going too deep. `$1` is the question to grab.

# Answer
> 1 votes
# Node.js, ~~251~~ 247 Bytes

```
r=require,g=r('request'),g('http://codegolf.stackexchange.com/q/'+process.argv[2],function(_,_,b){r('cheerio').load(b)('#question .post-text img').each(function(i,a){s=a.attribs.src,g(s).pipe(r('fs').createWriteStream(i+r('path').basename(s)))})})

```

Uses `request` to make HTTP `GET`s and `cheerio` to parse the HTML. Name collisions are resolved by prepending the index of the current image to the basename of the file's URL. Images are saved to same directory as the current file.

# Answer
> 1 votes
# Lua, 200 bytes

```
r=require'socket.http'.request r('http://codegolf.stackexchange.com/questions/'.. ...):gsub('post.text(.-)div',function(p)p:gsub('src="(.-)"',function(i)io.open(i:sub(-9),'wb'):write((r(i)))end)end)

```

Accepts the number as a command-line argument.

Assumes any `src=` attribute will be for an `img` tag since these are the only tags with `src` attributes that stack exchange allows (right?).

Also note the `.. ...`. I'm particularly proud of that one.

---
Tags: code-golf, internet
---


# Question
Title: Advanced Code Golf - Write a small HTTP server
Your challenge is to write a code-golf HTTP server that accepts GET requests. It obviously doesn't have to be fully featured, but it must serve files from a directory.

Rules:

* The HTTP server must listen on TCP port 36895 (0x901F)
* It must serve files from `/var/www` on \*NIX systems (e.g. Linux), or `C:\hgolf` on Windows.
* You may ignore all incoming HTTP headers except the `GET` itself.
* If the HTTP method is not GET, you must send back a status code of "405 Not Supported" and a body of "405 Not Supported".
* If the file does not exist, you must send back a status code of "404 File Not Found" and a body of "404 File Not Found".
* If the file exists but could not be read for some reason, you must send back a status code of "500 Server Error" and a body of "500 Server Error".
* If the user requests `/` or any other existing directory root (e.g. `/foo/` where a directory `foo` exists in `/var/www/`), respond with a blank page.
* Your response must contain at least the minimum headers to allow the content to be displayed on Firefox 8.0 and Internet Explorer 8.0
* You must respond with the `Content-Type` header set, but you only have to support extensions `html => text/html` and `txt => text/plain`. For any other file extension, Send `application/octet-stream` as the content type.
* Your code must be able to transfer both ASCII and binary data, though you do not explicitly have to distinguish between the two.
* You may not use 3rd party libraries.
* You may not use in-built classes or features designed to process HTTP requests (e.g. `HttpListener` in C#)
* If your code will only work on a specific OS due to the socket APIs you've used, please state this.

Solutions must include an image showing it serving a HTML page to a browser.

If you've got any questions, please feel free to ask! :)

# Answer
### Ruby, 383 characters

```
require 'socket'
v=TCPServer.new 36895
while c=v.accept
h="200 OK";m="";t=""
(c.gets=~/GET (\S*)/)?File.directory?(s='C:/hgolf'+$1)?0:File.exist?(s)?(h+="\r\nContent-Type: "+(s=~/\.txt$/?"text/plain":s=~/\.html$/?"text/html":"application/octet-stream");t="IO.copy_stream(s,c)"):(h=m="404 File Not Found"):(h=m="405 Not Supported")
c.puts "HTTP/1.1 #{h}\r\n\r\n"+m
eval(t)
c.close
end

```

The restructuring of the code to pack the essential logic into one line which makes the code shorter. Nevertheless, I hope this version can be golfed a little bit further.

Note: I didn't yet implement the "500 Server Error" because I couldn't find an appropriate structure (maybe packaging everything into begin/rescue/end but reading the file is done after the header was sent).
> 12 votes

# Answer
# Bash+netcat: 354 characters

* Two script files are used.
* No URL decoding, thus file names with spaces and special characters not supported.
* Single threaded, so concurrent requests may fail.
* Tested on Linux, works nicely with Firefox and Opera.

**webserver.sh** (33 characters):

```
while :;do nc -lp36895 -e./w;done

```

**w** (321 characters):

```
read m p v
p=/var/www$p
t=text/plain
[[ -r $p ]]||s='500 Server Error'
[[ -e $p ]]||s='404 Not Found'
[[ $m != GET ]]&&s='405 Not Supported'
[[ $s||-d $p ]]||case ${p##*.} in
txt);;html)t=text/html;;*)t=application/octet-stream;;esac
echo "$v ${s-200 Ok}
Content-Type:$t
"
[[ $s ]]&&echo $s||{ [[ -d $p ]]&&echo||cat $p;}

```

Sample run:

```
bash-4.2$ ./webserver.sh

```

Sample visit (Firefox 19.0):
> 27 votes

# Answer
# Haskell, 636

```
import Data.List;import Network;import System.Directory;import System.IO
main=listenOn(PortNumber 36895)>>=l;l s=(n s`catch`\_->u())>>l s
n s=do(h,_,_)<-accept s;z h>>=q.words>>=hPutStr h;hClose h
q("GET":p:_)=d$"/var/www"++p;q _=c"405 Not Supported"
d p=doesFileExist p>>=f p;e x|x=u$s""""|1<3=c"404 File Not Found"
f p x|x=t p`catch`\_e->c"500 Server Error"|1<3=doesDirectoryExist p>>=e
t p=fmap(s$"\nContent-Type: "++g p)$z=<<openBinaryFile p ReadMode
r s h b=["HTTP/1.0 ",s,h,"\n\n",b]>>=id
g p|b".html"p="text/html"|b".txt"p="text/plain"|1<3="application/octet-stream"
s=r"200 OK";c s=u$r s[]s;u=return;b=isSuffixOf;z=hGetContents

```

Files are streamed lazily, so serving large files does not use much memory, but this also means that only errors at the start of transmission (e.g. permission errors) result in a `500 Server Error`.

Tested on Ubuntu 10.10. Can be ported to Windows by changing the `/var/www` to `C:/hgolf` and changing `main=` to `main=withSocketsDo$`, since the sockets library on Windows requires explicit initialization.

**Ungolfed version:**

```
import Data.List
import Network
import System.Directory
import System.IO

root = "/var/www"

main = do
    s <- listenOn (PortNumber 36895)
    loop s

loop s = (next s `catch` \e -> return ()) >> loop s

next s = do
    (h, _, _) <- accept s
    hGetContents h >>= serve >>= hPutStr h
    hClose h

serve req =
    case words req of
        ("GET" : path : _) -> deliver (root ++ path)
        _ -> complain "405 Not Supported"

deliver path = do
    isFile <- doesFileExist path
    if isFile
        then transfer path `catch` (\e -> complain "500 Server Error")
        else do isDir <- doesDirectoryExist path
                if isDir
                    then return $ response "200 OK" [] ""
                    else complain "404 File Not Found"

transfer path = do
   body <- hGetContents =<< openBinaryFile path ReadMode
   return $ response "200 OK" ["Content-Type: " ++ guessType path] body

response status headers body =
  concat [unlines $ ("HTTP/1.0 " ++ status) : headers, "\n", body]

complain status = return $ response status [] status

guessType path
    | ".html" `isSuffixOf` path = "text/html"
    | ".txt"  `isSuffixOf` path = "text/plain"
    | otherwise                 = "application/octet-stream"

```
> 12 votes

# Answer
## Python 2, 525 510 493 (bending the rules 483) chars

```
from socket import*
from os.path import*
a=socket(2,1)
a.bind(("",80))
a.listen(5)
while 1:
 c,_=a.accept();i=c.recv(512).split("\n")[0].split();z=i[1][1:];m=i[2]+(i[0]!="GET"and"405 Not Supported\n\n"*2or exists(z)-1and"404 File Not Found\n\n"*2or"200 OK\n")
 if(len(m)>16)+isdir(z)<1:
    try:f=open(z,"rb");m+="Content-Type: "+{".txt":"text/plain","html":"text/html"}.get(z[-4:],"application/octet-stream")+"\n\n"+f.read()
    except:m=i[2]+"500 Server Error\n\n"*2
 c.send(m);c.close()

```

I stated that I only need 483 chars if I bend the rules because the last `;c.close()` could be omitted. This is because the moment the next client gets accepted, the socket gets closed anyway. This will of course increase waiting time somewhat (Firefox will only display the page when the next client connects, Chrome will display it before, but will continue to load), but the rules do not require me to respond to the request *immediately*, only to do so *at some point*.

I am not certain whether this will work on Unixes because I used send instead of sendall and send does not guarantee to actually send everything it is fed. It does work on Windows.
> 11 votes

# Answer
# Groovy, ~~507~~ ~~500~~ ~~489~~ 485

```
for(ServerSocket s=new ServerSocket(36895);;){t=s.accept()
o=t.outputStream
o<<"HTTP/1.1 "
e='\r\n'*2
d={o<<"$it$e$it"}
p=t.inputStream.newReader().readLine().split()
if(p[0]!='GET')d'405 Not Supported'else{f=new File('/var/www/',p[1])
if(!f.exists())d'404 File Not Found'else if(f.isFile()){x=f.name=~/\.(.*)/
o<<"200 OK\r\nContent-Type: ${[html:'text/html',txt:'text/plain'][!x?:x[0][1]]?:'application/octet-stream'}$e"
try{o.bytes=f.bytes}catch(t){d"500 Server Error"}}}
o.close()}

```

Added the image download to show binary files are working properly - had a few issues with them to begin with.

Can anyone suggest a shorter way to read the input?
> 6 votes

# Answer
## Erlang (escript) 575

Very dirty Erlang escript. There have to be one blank line at beginning of file to work well:

```
$ cat hgolf.erl

main(_)->{ok,L}=gen_tcp:listen(36895,[]),s(L).
s(L)->{ok,S}=gen_tcp:accept(L),receive{tcp,S,"GET "++R}->[F|_]=string:tokens("/var/www"++R," "),case case file:read_file_info(F)of{ok,{_,_,regular,read,_,_,_,_,_,_,_,_,_,_}}->a;{ok,_}->"500 Server Error";_->"404 File Not Found"end of a->h(S,"200 OK\r\nContent-Type: "++case lists:reverse(F)of"lmth."++_->"text/html";"txt."++_->"text/plain";_->"application/octet-stream"end,[]),file:sendfile(F,S);E->h(S,E,E)end;_->E="405 Not Supported",h(S,E,E)end,gen_tcp:close(S),s(L).
h(S,H,B)->gen_tcp:send(S,["HTTP/1.1 ",H,"\r\n\r\n",B]).

```

How to run

```
$ escript hgolf.erl

```

**Edit:**

I have squeezed out 20 chars. `case` is surprisingly shorter than function with even one argument and three clauses.
> 5 votes

# Answer
# VB.NET, 7203

You can define any port and any base directory using `--port` and `--base`, respectively.

No, this isn't really a golfing solution. But being VB.NET, there's really no point anyway. On the plus side, this one has lots more features.

```
Imports System.IO
Imports System.Net
Imports System.Net.Sockets
Imports System.Text
Imports System.Text.RegularExpressions

Public Module Server
    Private Const READ_BUFFER_SIZE As Integer = 1024

#Region "Content-Type Identification"
    Private ReadOnly ContentTypes As New Dictionary(Of String, String) From {
            {".htm", "text/html"},
            {".html", "text/html"},
            {".js", "text/javascript"},
            {".css", "text/css"},
            {".png", "image/png"},
            {".jpg", "image/jpeg"},
            {".jpeg", "image/jpeg"},
            {".gif", "image/gif"}
        } 'Feel free to add more.

    ''' <summary>
    ''' Retrieves the Content-Type of the specified file.
    ''' </summary>
    ''' <param name="filepath">The file for which to retrieve the Content-Type.</param>
    Private Function GetContentType(ByVal filepath As String) As String
        Dim ext As String = IO.Path.GetExtension(filepath)

        If ContentTypes.ContainsKey(ext) Then _
            Return ContentTypes(ext)

        Return "text/plain"
    End Function
#End Region

#Region "Server Main()"
    Public Sub Main(ByVal args() As String)
        Try
            'Get a dictionary of options passed:
            Dim options As New Dictionary(Of String, String) From {
                {"--port", "8080"},
                {"--address", "127.0.0.1"},
                {"--base", String.Empty}
            }

            For i As Integer = 0 To args.Length - 2
                If args(i).StartsWith("-") AndAlso options.ContainsKey(args(i)) Then _
                    options(args(i)) = args(i + 1)
            Next

            'Get the base directory:
            Dim basedir As String = Path.Combine(My.Computer.FileSystem.CurrentDirectory, options("--base"))

            'Start listening:
            Dim s As New TcpListener(IPAddress.Parse(options("--address")), Integer.Parse(options("--port"))) 'Can be changed.
            Dim client As TcpClient

            s.Start()

            Do
                'Wait for the next TCP client, and accept the connection:
                client = s.AcceptTcpClient()

                'Read the data being sent to the server:
                Dim ns As NetworkStream = client.GetStream()
                Dim sendingData As New Text.StringBuilder()
                Dim rdata(READ_BUFFER_SIZE - 1) As Byte
                Dim read As Integer

                Do
                    read = ns.Read(rdata, 0, READ_BUFFER_SIZE)
                    sendingData.Append(Encoding.UTF8.GetString(rdata, 0, read))
                Loop While read = READ_BUFFER_SIZE

                'Get the method and requested file:
#If Not Debug Then
                Try
#End If
                If sendingData.Length > 0 Then
                    Dim data As String = sendingData.ToString()

                    Dim headers() As String = data.Split({ControlChars.Cr, ControlChars.Lf}, StringSplitOptions.RemoveEmptyEntries)
                    Dim basicRequestInfo() As String = headers(0).Split(" "c)
                    Dim method As String = basicRequestInfo(0)
                    Dim filepath As String = basicRequestInfo(1).Substring(1)
                    Dim actualFilepath As String = Path.Combine(basedir, Uri.UnescapeDataString(Regex.Replace(filepath, "\?.*$", "")).TrimStart("/"c).Replace("/"c, "\"c))
                    Dim httpVersion As String = basicRequestInfo(2)

                    'Set up the response:
                    Dim responseHeaders As New Dictionary(Of String, String)

                    Dim statusCode As String = "200"
                    Dim statusReason As String = "OK"
                    Dim responseContent() As Byte = {}

                    'Check the HTTP version - we only support HTTP/1.0 and HTTP/1.1:
                    If httpVersion <> "HTTP/1.0" AndAlso httpVersion <> "HTTP/1.1" Then
                        statusCode = "505"
                        statusReason = "HTTP Version Not Supported"
                        responseContent = Encoding.UTF8.GetBytes("505 HTTP Version Not Supported")
                    Else

                        'Attempt to check if the requested path is a directory; if so, we'll add index.html to it:
                        Try
                            If filepath = String.Empty OrElse filepath = "/" Then
                                actualFilepath = Path.Combine(basedir, "index.html")
                                filepath = "/"
                            ElseIf Directory.Exists(actualFilepath) Then
                                actualFilepath = Path.Combine(actualFilepath, "index.html")
                            End If
                        Catch
                            'Ignore the error; it will appear once again when we try to read the file.
                        End Try

                        'Check the method - we only support GET and HEAD:
                        If method = "GET" Then
                            'Make sure nobody's trying to hack the system by requesting ../whatever or an absolute path:
                            If filepath.Contains("..") Then
                                statusCode = "403"
                                statusReason = "Forbidden"
                                responseContent = Encoding.UTF8.GetBytes("403 Forbidden")
                                Console.WriteLine("Access to {0} was forbidden.", filepath)
                            ElseIf Not File.Exists(actualFilepath) Then
                                statusCode = "404"
                                statusReason = "Not Found"
                                responseContent = Encoding.UTF8.GetBytes("404 Not Found")
                                Console.WriteLine("A request for file {0} resulted in a 404 Not Found. The actual path was {1}.", filepath, actualFilepath)
                            Else
                                Try
                                    'Read the requested file:
                                    responseContent = File.ReadAllBytes(actualFilepath)

                                    'Get the requested file's length:
                                    responseHeaders.Add("Content-Length", responseContent.Length.ToString())

                                    'And get its content type too:
                                    responseHeaders.Add("Content-Type", GetContentType(actualFilepath))
                                Catch
                                    'Couldn't get the file's information - assume forbidden.
                                    statusCode = "403"
                                    statusReason = "Forbidden"
                                    responseContent = Encoding.UTF8.GetBytes("403 Forbidden")
                                End Try
                            End If
                        ElseIf method = "HEAD" Then
                            'Make sure nobody's trying to hack the system by requesting ../whatever or an absolute path:
                            If filepath.Contains("..") Then
                                statusCode = "403"
                                statusReason = "Forbidden"
                                responseContent = Encoding.UTF8.GetBytes("403 Forbidden")
                                Console.WriteLine("Access to {0} was forbidden.", filepath)
                            ElseIf Not File.Exists(actualFilepath) Then
                                statusCode = "404"
                                statusReason = "Not Found"
                                responseContent = Encoding.UTF8.GetBytes("404 Not Found")
                                Console.WriteLine("A request for file {0} resulted in a 404 Not Found.", filepath)
                            Else
                                Try
                                    'Get the requested file's length:
                                    responseHeaders.Add("Content-Length", New FileInfo(actualFilepath).Length.ToString())

                                    'And get its content type too:
                                    responseHeaders.Add("Content-Type", GetContentType(actualFilepath))
                                Catch
                                    'Couldn't get the file's information - assume forbidden.
                                    statusCode = "403"
                                    statusReason = "Forbidden"
                                    responseContent = Encoding.UTF8.GetBytes("403 Forbidden")
                                End Try
                            End If
                        Else
                            'Unknown method:
                            statusCode = "405"
                            statusReason = "Method Not Allowed"
                        End If

                        'Prepare the response:
                        Dim response As New List(Of Byte)

                        'Prepare the response's HTTP version and status:
                        response.AddRange(Encoding.UTF8.GetBytes("HTTP/1.1 " & statusCode & statusReason & ControlChars.CrLf))

                        'Prepare the response's headers:
                        Dim combinedResponseHeaders As New List(Of String)
                        For Each header As KeyValuePair(Of String, String) In responseHeaders
                            combinedResponseHeaders.Add(header.Key & ": " & header.Value)
                        Next
                        response.AddRange(Encoding.UTF8.GetBytes(String.Join(ControlChars.CrLf, combinedResponseHeaders.ToArray())))

                        'Prepare the response's content:
                        response.Add(13)
                        response.Add(10)
                        response.Add(13)
                        response.Add(10)
                        response.AddRange(responseContent)

                        'Finally, write the response:
                        ns.Write(response.ToArray(), 0, response.Count)
                    End If
                End If
#If Not Debug Then
                Catch ex As Exception
                    Console.WriteLine("Serious error while processing request:")
                    Console.WriteLine(ex.ToString())
                    Dim errorResponse() As Byte = Encoding.UTF8.GetBytes("HTTP/1.1 500 Internal Server Error" & ControlChars.CrLf & ControlChars.CrLf & "500 Internal Server Error")
                    ns.Write(errorResponse, 0, errorResponse.Length)
                End Try
#End If

                'And at last, close the connection:
                client.Close()
            Loop
        Catch ex As SocketException
            Console.WriteLine("SocketException occurred. Is the socket already in use?")
            Console.ReadKey(True)
        End Try
    End Sub
#End Region

End Module

```

I even decided to put it on GitHub :) https://github.com/minitech/DevServ
> 3 votes

# Answer
# C# (869)

```
using E=System.Text.Encoding;using System.IO;class C{static void Main(){var l=new System.Net.Sockets.TcpListener(new System.Net.IPEndPoint(16777343,36895));l.Start();while(0<1){using(var c=l.AcceptTcpClient()){try{string v="200 OK",r="",t="text/plain",p;var s=c.GetStream();var b=new byte[c.ReceiveBufferSize];s.Read(b,0,b.Length);var h=E.UTF8.GetString(b).Split();b=null;try{if(h[0]=="GET"){p="/var/www"+h[1];if(File.Exists(p)){b=File.ReadAllBytes(p);t=p.EndsWith(".txt")?t:p.EndsWith(".html")?"text/html":"application/octet-stream";}else if(!Directory.Exists(p)){v=r="404 Not Found";}}else{v=r="405 Not Supported";}}catch(IOException){v=r="500 Server Error";}b=b??E.UTF8.GetBytes(r);var m=E.UTF8.GetBytes("HTTP/1.1 "+v+"\r\nContent-Type:"+t+";charset=utf-8\r\nContent-Length:"+b.Length+"\r\n\r\n");s.Write(m,0,m.Length);s.Write(b,0,b.Length);}catch(IOException){}}}}}

```

Ungolfed

```
using System.Text;
using System.IO;

class C {
    static void Main() {
        var listener = new System.Net.Sockets.TcpListener(new System.Net.IPEndPoint(16777343,36895));
        listener.Start();

        while (true){
            using (var client = listener.AcceptTcpClient()) {
                try {
                    string responseCode = "200 OK", responseBody = "", contentType = "text/plain", path;
                    var stream = client.GetStream();

                    var bytes = new byte[client.ReceiveBufferSize];
                    stream.Read(bytes,0,bytes.Length);

                    var requestHeaders = Encoding.UTF8.GetString(bytes).Split();
                    bytes = null;

                    try{
                        if(requestHeaders[0] == "GET"){
                            path = "/var/www" + requestHeaders[1];

                            if (File.Exists(path)) {
                                bytes = File.ReadAllBytes(path);
                                contentType = path.EndsWith(".txt") ? contentType : path.EndsWith(".html") ? "text/html" : "application/octet-stream";
                            } else if (!Directory.Exists(path)){
                                responseCode = responseBody = "404 Not Found";
                            }
                        } else {
                            responseCode = responseBody = "405 Not Supported";
                        }
                    } catch(IOException) {
                        responseCode = responseBody = "500 Server Error";
                    }
                    bytes = bytes ?? Encoding.UTF8.GetBytes(responseBody);

                    var responseHeader=Encoding.UTF8.GetBytes("HTTP/1.1 " + responseCode + "\r\nContent-Type:" + contentType + ";charset=utf-8\r\nContent-Length:" + bytes.Length + "\r\n\r\n");
                    stream.Write(responseHeader, 0, responseHeader.Length);
                    stream.Write(bytes, 0, bytes.Length);
                } catch(IOException) {
                    // If a client disconnects in the middle of a request (e.g. by refreshing the browser) an IOException is thrown.
                }
            }
        }
    }
}

```
> 3 votes

# Answer
# Node.js - 636

Only tested on Linux, won't work on Windows.

```
a=require
b=a('fs')
function c(){g+=o+h+i+j+f+f+o+f}
a('net').createServer(function(d){d.on('data',function(e){f='\r\n'
g='HTTP/1.1 '
h=f+'Content-Type: '
i='text/'
j='plain'
if(k=/^GET (\S+)/.exec((e+'').split(f)[0])){k=k[1]
l=k.slice(k.lastIndexOf('.')+1)
m='www'+k
if(b.existsSync(m)){if(b.lstatSync(m).isDirectory()){g+='200 OK'+h+i+j+f}else{try{n=b.readFileSync(m)
g+='200 OK'+h
if(l=='txt')g+=i+j
else if(l=='html')g+=i+l
else g+='application/octet-stream'
g+=f+f+n}catch(_){o='500 Server Error'
c()}}}else{o='404 File Not Found'
c()}}else{o='405 Not Supported'
c()}
d.write(g)
d.end()})
d.on('error',function(){})}).listen(36895)

```
> 3 votes

# Answer
# Python 3 - 655

```
from socket import*
import re
import threading
def x(c):
    u=str(c.recv(1024))
    if not'GET'in u:conn.sendall(t("HTTP/1.1 405 Not Supported"))
    u=re.search('GET [^\s]+ HTTP/1.1',u).group(0).split(" ")[1];u="/index.html" if u == "/" else u;e=u.split(".")[1]
    try:c.sendall(t("HTTP/1.1 200 OK\nContent-Type: "+({'txt':'text/plain','html':'text/html'}[e]if e in'txthtml'else'application/octet-stream')+"\n\n")+open("."+u,'rb').read())
    except:c.sendall(t("HTTP/1.1 404 File Not Found\n\n404 File Not Found"))
t=lambda s: bytes(s,'utf8')
s=socket(AF_INET,SOCK_STREAM)
s.bind(('',36895))
s.listen(10)
while 1:threading.Thread(target=x,args=[s.accept()[0]]).run()

```
> 2 votes

# Answer
## Scala, 653 characters

```
import java.net._
import java.io._
object I extends App{val l=new ServerSocket(36895)
while(true){var (s,e,c,b)=(l.accept,"200 OK","text/html","")
var h=io.Source.fromInputStream(s.getInputStream).getLines.next.split(" ")
if(h(0)!="GET"){e="405 Not Supported"
b=e}else{var f=new File("/var/www"+h(1))
if(!f.isDirectory){if(f.exists){var q=h(1).split("\\.").last
if(q=="txt")c="text/plain"else if(q!="html")c="application/octet-stream"
try b=io.Source.fromFile(f).mkString catch{case _=>e="500 Server Error";b=e}}else{e="404 File Not Found"
b=e}}}
var o=new PrintWriter(s.getOutputStream)
o.print("HTTP/1.1 "+e+"\nContent-Encoding:"+c+"\n\n"+b)
o.close}}

```

A screenshot of it running on my MacBook:

Not great, but I'll have a go at squashing it a bit when I've got some time later.
> 1 votes

# Answer
# VB.Net (3504 characters):

```
Imports System.IO:Imports System.Net:Imports System.Net.Sockets:Imports System.Text:Imports System.Text.RegularExpressions:Module x:Dim s=1024,ct As New Dictionary(Of String,String)From{{".htm","text/html"},{".html","text/html"},{".js","text/javascript"},{".css","text/css"},{".png","image/png"},{".jpg","image/jpeg"},{".jpeg","image/jpeg"},{".gif","image/gif"}}:Function b$(f$):Dim ext$=Path.GetExtension(f$):Return If(ct.ContainsKey(ext$),ct(ext$),"text/plain"):End Function:Sub Main(a$()):Try:Dim z As New Dictionary(Of String,String)From{{"--port","8080"},{"--address","127.0.0.1"},{"--base",""}}:For i As Integer=0 To a.Length-2:If a$(i).StartsWith("-")AndAlso z.ContainsKey(a$(i))Then:z(a$(i))=a$(i+1):Next:Dim b$=Path.Combine(My.Computer.FileSystem.CurrentDirectory,z("--base")),s As New TcpListener(IPAddress.Parse(z("--address")),Integer.Parse(z("--port"))),c As TcpServer:s.Start():Do:c=s.AcceptTcpServer():Dim ns As NetworkStream=c.GetStream():Dim sd As New Text.StringBuilder(),rd(s-1)As Byte,r As Integer:Do:r=ns.Read(rd,0,s):sd.Append(Encoding.UTF8.GetString(rd,0,r)):Loop While r=s:Try:If sd.Length>0 Then:Dim dd$=sd.ToString(),h$()=dd$.Split({ControlChars.Cr,ControlChars.Lf},StringSplitOptions.RemoveEmptyEntries),br$()=h$(0).Split(" "c),mt$=br$(0),f$=br$(1).Substring(1),af$=Path.Combine(b$,Uri.UnescapeDataString(Regex.Replace(f$,"\?.*$","")).TrimStart("/"c).Replace("/"c,"\"c)),hv$=br$(2),rh As New Dictionary(Of String,String),sc$="200",sr$="OK",rc()As Byte={}:If hv$<>"HTTP/1.0"AndAlso hv$<>"HTTP/1.1"Then:sc$="505":sr$="HTTP Version Not Supported":rc=Encoding.UTF8.GetBytes("505"&sr$):Else:Try:If f$=String.Empty OrElse f$="/"Then:af$=Path.Combine(b$,"index.html"):f$="/":ElseIf Directory.Exists(af$)Then:af$=Path.Combine(af$,"index.html"):End If:Catch:End Try:If mt$="GET"Then:If f$.Contains("..")Then:sc$="403":sr$="Forbidden":rc=Encoding.UTF8.GetBytes(sc$&" "&sr$):Console.WriteLine("{0} forbidden.",f$):ElseIf Not File.Exists(af$)Then:sc$="404":sr$="Not Found":rc=Encoding.UTF8.GetBytes(sc$&" "&sr$):Console.WriteLine("{0} resulted in 404 Not Found. Path {1}.",f$,af$):Else:Try:rc=File.ReadAllBytes(af$):rh.Add("Content-Length",rc.Length&""):rh.Add("Content-Type",b$(af$)):Catch:sc$="403":sr$="Forbidden":rc = Encoding.UTF8.GetBytes(sc$&" "&sr$):End Try:End If:ElseIf mt$="HEAD"Then:If f$.Contains("..")Then:sc$="403":sr$="Forbidden":rc=Encoding.UTF8.GetBytes(sc$&" "&sr$):Console.WriteLine("{0} forbidden.",f$):ElseIf Not File.Exists(af$)Then:sc$="404":sr$="Not Found":rc=Encoding.UTF8.GetBytes(sc$&" "&sr$):Console.WriteLine("404 Not Found: {0}",f$):Else:Try:rh.Add("Content-Length",New FileInfo(af$).Length&""):rh.Add("Content-Type",b$(af$)):Catch:sc$="403":sr$="Forbidden":rc = Encoding.UTF8.GetBytes(sc$&" "&sr$):End Try:End If:Else:sc$="405":sr$="Method Not Allowed":End If:Dim rr As New List(Of Byte):rr.AddRange(Encoding.UTF8.GetBytes("HTTP/1.1 "&sc$&sr$&ControlChars.CrLf)):Dim cr As New List(Of String):For Each h As KeyValuePair(Of String,String)In rh:cr.Add(h.Key&": "&h.Value):Next:rr.AddRange(Encoding.UTF8.GetBytes(String.Join(ControlChars.CrLf,cr.ToArray()))):rr.Add(13):rr.Add(10):rr.Add(13):rr.Add(10):rr.AddRange(rc):ns.Write(rr.ToArray(),0,rr.Count):End If:End If:Catch ex As Exception:Console.WriteLine("Error:"):Console.WriteLine(ex.ToString()):Dim e()As Byte=Encoding.UTF8.GetBytes("HTTP/1.1 500 Internal x Error"&ControlChars.CrLf &ControlChars.CrLf &"500 Internal x Error"):ns.Write(e,0,e.Length):End Try:c.Close():Loop:Catch:End Try:End Sub:End Module

```

Golfed from @minitech's answer.
> 1 votes

# Answer
# Lua 5.1 in ~~435~~ 434 bytes

```
s=require'socket'.bind('*',36895)while{}do
c=s:accept()u=c:receive'*l':match'GET (.*) HTTP'f,_,e=io.open('/var/www'..u,'rb')d=z
x=z if f then d,_,x=f:read'*a'end
h=u and(x==21 and''or(e==2 and'404 File Not Found'or d
and('200 OK\r\nContent-Type:'..(({txt='text/plain',html='text/html'})[u:match'%.(.-)$']or'application/octet-stream'))or'500 Server Error'))or'405 Not Supported'c:send('HTTP/1.1 '..h..'\r\n\r\n'..(d
or h))c:close()end

```

...and the proof...
> 1 votes

---
Tags: code-golf
---


# Question
Title: Looking for programs in a huge Boggle board
Each character in this 64 by 64 block of text has been chosen randomly and uniformly from the 95 printable ASCII characters.

```
/rq$:Zy5*g'$DeGXX2o8y "{@Cg:FR9qih}xh >5$DsF1Fs5Ao~smFp;.RJbV )U
c4\(|Sx*V$10G9xO:NjHKasem%,\9[pPm@&kTaN~HC[;9`lgqlAH(7dt0a-5}LJ[
&sifw9V-.PLRoD~F'dJYA^Q)L#h>$9h!B4b&ceKp8~HndzDm#1/ySydrf5T8[Y%4
U9>HLQ74Qf[^V9tpWrKFcFxZJ::4?z/o]3u,V[B&hB9lFYA0:rW#yql5z9.d*D}U
:M2*O9'7_HMGw_=%@hR>O+(@Dr6MIt(=/{-{4lia0Vmws32wr(fnTmT%HSo&7!uz
\KZWG&KnXh+6E+Q>%pV(<Bnm-d+p~y~]Ta"aw9)]0A_AHz\tP3&}1R^/yPPSgN?8
".7|Uj)S7-k[`yeLO~P2a?z3wiS(R-\k'?z(pVm;;D^k/q84?&7:,E*9$UQ"UbBJ
ME]&*R ,*7PDF4Tw*-;De{YeP_al.CJcJX`@V_y+>^<h{L[^Y"!RxjN^lyA_/Y=(
#C>Zo#Sl;UUD5ChIj'L@rkELk%S*]a$87j\\n;}796m/\NPL>8d-T-hR!7ftw ?A
tV5"E309bAv$jhE6\'8f?VGlBb?z#V;F((3'|}$tfpiNB>"*mxc,X1s:/%x*JQAL
rxYXUJsd?X}^yc|'16539vd=psU'>|y/!$-TRamKcJk^2-aD35h7CcaRNue"8#{;
@yUq?*(72I8@I)So+]RwtKy:mLhjG/f#:U<TXml<PtX*+,ngfZt75-q*gSsyI2tS
|*M*;yz6u2(LZ>W`bth-7G~>|dh'pm}]@"#Oq9%o\W)b,gh%b1O]4F:EGb7ERI=@
ehMo69slKw=S@<j*Q4sfd\1')#)V&yaPF%%ZG6VK\_-$Cab,nrlW"O(<tu&xU=I&
|[g4k2L;FD)=yX0SsE-|vI(mDOccuU(+m\wxgrJxi8ZP[uD)L.!K@]%@q`!pk8Yx
?PZaS3;x,7nK~IHlrCGy~xq:@K/CJ1J^oeac&Tv?6[H>>0lu?(/bh@6J^@S?IY-|
@tdN$K=Ci2;_0Du;L2OO'en|]<_`nX5p3Bes9`8{}fRCV$X&aoQGYS'$j%r<2709
UwETsAo^d!aUZ0vN5,Yq\n%JAIm}%O88FAJK^Jt&=jM\Q1^+^|X8\._"l%hlF+yH
+c^FBFxTGz|f|#kElQs)mS64-3Z\An]|[rQo"OQ+ IP"ARdJ}/OYFQF_/{B 73mU
UPvxNByN[2TT,XgRZ_LwolUVWuR)DjYI7j#mmA8m?&Y}}[_h8@Y-R*,#=1\D*&@*
ePW.w{@z3moe3Vztd,>?*~ZQUvn8$+xw$$f92D*kPZ":;lcTr3m&{*?j$FgZK|cU
IAd'0C{<4b}NuhX1B#gmk'oF4+(@fzP^T?hF/#]g^y rb5][)X-d4Q't~1]HE"tZ
p2Z,%H0$EWF/%|UQm?&]E~=v;9YwxrSs%}df`[ `SfXMJWt86UY1duGAAKkFSrH!
oUyB[soS!N%XYwX]%n K^}CcTE?~.,8`C&l)Jjjp5|z))!o/ "G)sj,{OETsi:KE
4E,':a=,T~YlxdF^<\$fE|f:_-RG}7=m%g\-9a*X]`n<P$D+q7O`+$P&!\"NUs7n
hL@0s 7i^Xp\._4$lZIB9Ql AXX_00K=<hp%55KSO6yWH~cGe%|(p_WzlhPUbH{?
o5b4pi(,]&&jB\hGa:\DQbrYc,n|,b)_E{n~i~+JSxn?%/qJVm|B 8"Jf||L.|M-
 KRxH;T^Z7%ZufyO=nI;[v1\8ZTg\_)ect4DvMTvqtoo(;b~J&'~E2TTD!w1BvGv
Q+1sv>q%1$BaCm%(\%uGH*]emoFwejkhb$gKm=DVG#&:p'";s)&MY30q_cG=.CKJ
q,aWTi|^w2wg3<G_y<n+^Xq2ymHFs#7z[x0l'Lz6N>Mpo?=hAd&58HVMhsh(kQH5
&kSivkn`,KON9xb:$M[L15!D6W?\ASWc#}V#2U;qxKhtil73,!iuG~(lr[tPJQ6w
IZ)0Vp{kEUID:vgwmTMQ#Y]NdX6{'/3bI2x9k 4[>j)&Q0U,t,iA#A%4929o6+n_
SQe/!KubbuXthMe&2\%:'Z`,aaA)V&(v+]0^v-_@*Qg!^K!pCo"@e/|3}.3q^R||
6hF>/jd>(=il~2$KY.^x~K_H)J8Fi)'LOcUr4xJir^v0,c fIsoT<|7K}Bls|36z
MQ|-w=bp)_EY>YtGcW)!@/|Lc:I_<]x.~[|QSgJY1ZX9^e`ojAR6U#zt9!,44}>#
EJzH \gwosC>Z*)H!]1BPaIEYGyk{c0zv{d\#px2@#'-T{{.Qxknxv}"x3#K]w>;
<X(\bNnY_6*7Yu7_3a+wInwt vh=1eBgz>7Bnhs!<t.T#&V{+?p+{.RTN:xz>|,E
$upN*[F4A`~ZDMDt{.&2z+LZ7bcfeJfF9Uy3xX]ZzQ1FvB.U4S!hm$LYCp: wF7h
 47-+lY$"}AExXQ@?!/6}biptH=6N-6&8-T\C8{`i56e'%cimv,0QKYTx) "nkFJ
C:Enw=Q%6J;t6wS+2O,b0v'"OK6GMbr);y#-H86>pCE6wjdk*rR*=reWo57^2TFH
::Nq,t9_S">\o^NZzh|U\^qyh-yt0nvMs%'6\;$%(91gTC=&1q]q-*u*so KrXsE
-Sz>q]l86[OO@\5W<'\XDc,%/=0sV0&1'Etty%f ~,c45IIqy=no.DY{8\?fa<9{
6%3TP:i^q.JzU217CADu}iAzWT""E\{IEMbGDKZB6s*LmlM0|<WA8CP7sR}f?WSL
S`T} 7Tn9!h8P\W 8J\#Mg\o;Qwt&4\UYKf{)O3G&B]sK.bw1!?7=:h$IIOIakD<
H/O5v`ld*35MSsydSQoiAnJ*\!^?'_=6E?c> PtM!rw5y{ZT2xSco){3_?j|wtJp
CT1!e~k8aNgw)LE:}oX4R*<u]TB%\IN8YoMK'bV%L2H{L3'c/|xoTY^&&WPKSyo<
cXma$Rfjj^':^a\?$UOo48]791Wywj7aH1\iP|\l=sjjbjqZB2)-apvjV@q47Spw
OP[kT<l@cKB="n;VC#6a*InmS~$TN{= j)r>S] uH9:E-}y>.Ygc'll$5Y$j]AYt
jB="iGo7[qY~A*nv.\51[<]):^[iZs4s-D_bC'OfM%lHlz;MoxY$Ku]NCt72PYMB
_(myN5'%] C!7FPoGX7+*,Yptuaz;Q6W,;R|U1XEhgq21R7<ncnDB<D_);j.:r0r
Q6!k|Dq`!Jz7l="*n?w@f|h=PA_A)n._ii:s~'n~XsD}?JRIkC9AW^piUfBTU,ui
nf+yZ`7P-(@{>s:{Vz'N 7qB&+UZbm4'0]D~HZNJq.w</3 \cL)WRDP(y]w~L4N/
!!lA+NK[+9#-iwx`PE53D.K2]]#M.Rm$^Cc'|!@cX6{yCg8K0|>E_jyup|+'=#c%
Ao5$B);DoQ#jg[7GbdE+o:R,T#@`;UnX}.?2z\RJ98Se*_.*e8mCUF}Vw1u13cy1
2s}1@?{0);Jo6(J@l>[M 0CkeO6{ExN7,%Kv1#[!** czaX)=;Q~D;z',fkq!1W<
% f(i#i`PQY!m7v#D:j5pyU]8:at2,k("BWZRI<WR??GQ$^1d[m,F(<e5CLv-m*B
CD)zVpa95WpJ K@&}yN\Q8I<%z/*_/bPsR5=0\Z=#mWZDAfA5[k|$Yks@Q;@h,s/
Np.$gTvz>T+"0|$Nw::%m$GFYxG{2akv$Eh8\4|eW'oJEffNzJ>UxU4>oITZMe/'
EMg$>kD|\ ^.W)Stzv/7z\^bdi]E@] U&-r8(B^?}$P56[?e~jE#_j)5=#~.yNP$
'mgF3EAhXB 55)\WXp*e+fD#^&SHGx++7VO[R7*b(Q+:jESt'K%m~d$Bv^/{7=zr
5oCZDp& ;*Y*G`L$C]Nm`|^:y2NKaO!)u/{hwm(VjS`<qKgNw7[+~0 <be'sWjTo
.3!sPGuFFZ@9.4u*ml)pLeEVJ~8A$mgz*d>ajbg1FIYrg6J`D0xJMXi`ghA1V$ju
*rJg/ o;6M7`(qTF.nO'4da,{ieM&NC9rg;nX*))*DK"DycYD66&6z/I@}y4@$<f
3S]~9g An{=Rj|y&A2Vh^F\3lb#N~8w0EMx<K$]z(eZS~zbmgeeV\i7,MY~zrc+;

```

Your task in this challenge is not to write your own code, but rather to extract code from this block of text as if it is a huge Boggle grid and you're looking for a runnable program instead of a word.

The submission with the program that produces the longest finite output wins.

# Details

Treat the 64 by 64 grid of text exactly like a 64 by 64 Boggle grid with additional characters. Construct a string that is a runnable program in some language by choosing a starting location in the grid and repeatedly moving one step vertically, horizontally, or diagonally (8 directions total) as many times as you want. **You may NOT use the same grid space more than once!**

For example, these 4 lines were taken from near the middle of the text block:

```
EJzH \gwosC>Z*)H!]1BPaIEYGyk{c0zv{d\#px2@#'-T{{.Qxknxv}"x3#K]w>;
<X(\bNnY_6*7Yu7_3a+wInwt vh=1eBgz>7Bnhs!<t.T#&V{+?p+{.RTN:xz>|,E
$upN*[F4A`~ZDMDt{.&2z+LZ7bcfeJfF9Uy3xX]ZzQ1FvB.U4S!hm$LYCp: wF7h
 47-+lY$"}AExXQ@?!/6}biptH=6N-6&8-T\C8{`i56e'%cimv,0QKYTx) "nkFJ

```

Starting with the `p` near the right end of the third line I can move to the  by going diagonally down and right, then to the `"` by going right, then up 3 times over `zK`, and left 4 times over `#3x"`. This traces out the string `p " zK#3x"` which when run as a Ruby program outputs `" zK#3x"`.

The goal is to find a program that produces the longest **finite** output. **Only printable ASCII characters are considered when counting the length of the output (this means tabs and newlines are not counted), though other characters may be present.** The Ruby example only produces 8 characters.

Also...

* The program may be from 1 to 4096 characters long.
* The program may not contain tabs, newlines, or non-printable ASCII (as they aren't in the grid).
* The program should run and exit without errors.
* There are no time or complexity constraints as long as the program would *eventually* terminate with finite output.
* The grid does not loop around from left to right or top to bottom.

Please mention where your program appears in the grid so we can quickly verify that it really is there.

# Answer
> 15 votes
# CJam, over (81182737^2813292)↑↑(10604499373-1) chars

Okay I think I've finally sorted everything out. This was fun — coming up with the code was like navigating a minefield.

---

Before we dive in, let's start with a simpler example (try it online):

```
1 3{(\1\{(\5*\}h;\}h;

```

`h` is a do-while loop that leaves the condition on the stack, and `{}` are code blocks. The inner block is:

```
(        Decrement
\        Swap top two of stack
5*       Push 5 and multiply
\        Swap back

```

Suppose the top of the stack is `[1 10]` and we perform the do-while `{(\5*\}h;`. This is what happens:

```
[1 10] --decrement--> [1 9]    --swap--> [9 1]    --multiply--> [9 5^1]  --swap--> [5^1 9]
       --decrement--> [5^1 8]  --swap--> [8 5^1]  --multiply--> [8 5^2]  --swap--> [5^2 8]
       --decrement--> [5^2 7]  --swap--> [7 5^2]  --multiply--> [7 5^3]  --swap--> [5^3 7]
       ...

```

This happens until the 10 decrements all the way down to 0 and the loop terminates, at which point we end up with `[5^10 0]` at the top of the stack. We can then use `;` to pop the zero, leaving `[5^10]`.

In other words we have just performed exponentiation, with `[1 x]{(\5*\}h;` resulting in `[5^x]`.

The outer block `{(\1\{(\5*\}h;\}h;` is similar, but instead of the `5*` in the middle we have our "exponentiate base 5" loop. So for our simple example, starting with `[1 3]` we get:

```
[1 3] -dec/swap-> [2 1]   -push 1-> [2 1 1]   -swap-> [2 1 1]   -5^-> [2 5]     -swap-> [5 2]
      -dec/swap-> [1 5]   -push 1-> [1 5 1]   -swap-> [1 1 5]   -5^-> [1 5^5]   -swap-> [5^5 1]
      -dec/swap-> [0 5^5] -push 1-> [0 5^5 1] -swap-> [0 1 5^5] -5^-> [0 5^5^5] -swap-> [5^5^5 0]

```

The top is zero, so we stop the loop and pop, leaving `[5^5^5]`. In other words, we have just created `5^5^5`, or `5↑↑3` in Knuth's up arrow notation. You can switch 5 and 3 for other numbers but hyperexponentiation gets big **fast**, so I wouldn't recommend picking anything too large.

---

Now for the real thing:

```
1B);0D+9#{z(J Y=A*;\VC#UooJ87<W5^o\OO>;J6%_9=+NpXzH|>!p{Kdp(_E=XIK21^%^Z&&p\Y~!E<432|T|Z#00I0*boW)I^8227(*JEo*#09;*7XH+G^o9=pWdK>(2P-*I\6539K~>)#D@</CJ1(+^po\F"U$(jX?a"apV\|;}_V);;D00&phVA^^6pJP\<%o\8H>V1^+aoXY-Y&41-X)8/o!Jb;}"}:rM)<W?o:p'";h

```

*(Path trace)*

Anotated (anything without notes is filler):

```
1                                           Push 1
B);
0D+9#                                       Push 13^9 = 10604499373
{                                           Start outer block
z
(                                           Decrement
J Y=A*;
\                                           Swap
VC#Uoo
J87<                                        Push 1
W5^o
\                                           Swap back
OO>;
J6%_9=+NpXzH|>!p
{                                           Start inner block
Kdp
(                                           Decrement
_E=XIK21^%^Z&&p
\                                           Swap
Y~!E<432|T|Z#00I0*boW)I^8227(*JEo*#         Push 81182737^2813292, <output 3 chars>
09;
*                                           Multiply by previous large number
7XH+G^o9=pWdK>(2P-*I\6539K~>)#D@</CJ1(+^po
\                                           Swap back
F"U$(jX?a"apV\|;
}                                           End inner block
_V);;
D00&p
h                                           Perform inner do-while loop
VA^^6pJP\<%o                                Pop top of stack by outputting
\                                           Swap back
8H>V1^+aoXY-Y&41-X)8/o!Jb;
}                                           End outer block
"}:rM)<W?o:p'";
h                                           Perform outer do-while loop

```

It's basically the same as the simple example, just with a lot of filler while navigating from one instruction to another in the grid.

Instead of 5 and 3 we have `81182737^2813292` and `10604499373`, meaning that `(81182737^2813292)↑↑10604499373` gets outputted at the end (given enough time and memory, of course!). Note that this is merely a lower bound — there's a lot of other printing that takes place, e.g. with 6 and 3 the output is over 2 million chars long even though `6^6^6` has only 36k digits.

If you want to try this full version for yourself, test with:

```
1B);
3
{z(J Y=A*;\VC#UooJ87<W5^o\OO>;J6%_9=+NpXzH|>!p{Kdp(_E=XIK21^%^Z&&p\
5
09;*7XH+G^o9=pWdK>(2P-*I\6539K~>)#D@</CJ1(+^po\F"U$(jX?a"apV\|;}_V);;D00&phVA^^6pJP\<%o\8H>V1^+aoXY-Y&41-X)8/o!Jb;}"}:rM)<W?o:p'";h

```

replacing the 5 and 3 on the second and fourth lines with numbers of your choice. Note that the output will have a few extra digits around the important hyperexponentiated number (namely a preceding `010` and a trailing `0`).

---

## A few notes on CJam

You might we wondering: why not use CJam's inbuilt exponentiation (`#`) instead of the inner do-while loop? Unfortunately, after digging through CJam's source, I learnt that for exponentiation the *base* can be a BigInt (arbitrary precision) but **the exponent gets converted to a normal 32-bit int**. This has some amusing, but annoying side effects:

```
2 2 31# #     -->    java.lang.ArithmeticException: Negative exponent  (should be 2^2^31)
2 2 32# #     -->    1                                                 (should be 2^2^32)

```

This meant that I couldn't use CJam's builtin exponentation when the exponent is too large, for overflow reasons. However, multiplication is different as multiplying two BigInts results in a new BigInt, so I decided to exploit that instead.

# Answer
> 7 votes
# TECO, ~2^31 * 13 ~= 27.9 * 10^9

```
?^e=<\RZK%B"svbk7,.c2z\R!Z~|bS|VM!2=9%MEX'1UC>

```

Edit: Changed a couple of characters because I accidentally reused one, but that part was inside a comment so it doesn't make much difference.

The `?` turns on command echoing, which I use to create most of the output. Then the characters `\RZK%B"s'1UC>` are printed in a loop. `%B"s` adds one to B and then tests if it is less than zero. Thus, this conditional should be entered after 2^31 cycles when it overflows to a negative number. Inside the conditional there is an `EX` command which exits the program.

Currently I am attempting to run it to completion with the output directed to a file.

# Answer
> -3 votes
# HQ9+ (17195 characters)

**Source:**

```
9Q9

```

(starts at 5:4 and then down)

**Output:**

The text to the song "99 bottles of beer" (8596 characters), the string `9Q9` (3 characters) and another copy of "99 bottles of beer" (8596 characters).

This is a very lame answer and you should not upvote it, but someone had to post it.

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