title: Break the broken hash

text:
# Question
Title: Break the broken hash
Some time ago, I found this unused hash function (written in Java) in our codebase:

```
long hashPassword(String password)
{
    password = password.toUpperCase();
    long hash = 0;
    int multiplier = 13;
    for (int i = 0; i < password.length(); i++)
    {
        hash += hash * multiplier + (short)password.charAt(i);
        multiplier++;
    }
    hash = Math.abs(hash);
    hash <<= hash % 11;
    hash = Math.abs(hash);
    return hash;
}

```

I am very happy that it was unused, because it is beyond broken. Not only is this hash function very weak with an ouput of only 8 bytes, but it is also reversible, and it collides very easily: there are many similar inputs that will generate the same hash. A friend and I worked on the problem, and we managed to create a C# program that does just that: take a hash, and show the reasonable inputs that could have generated this hash.

Now is your turn. Write a program, in any language, that accepts a numeric hash as its sole parameter, and yields all possible inputs (made of 5+ characters with only printable ASCII characters) that would produce the given hash if passed to the function above, each on a new line. You don't need to handle any specific kind of error, as long as it works for any given numeric hash.

On your post, please include the hash of a word of your choice, and five possible inputs that have this hash (though your program must not be limited to finding only five).

Most elegant solution wins, and elegance is defined as algorithmic elegance (in other words, brute-force won't win). I'll accept an answer on March 13.

Example input and output (UNIX shell optional):

```
$ ./hashbreaker 224443104
ZNEAK
Y^4Q]
\2'!'
ZMUB9
Y_%AK
[and many, many, many more results...]

```

# Answer
Another partial answer:

```
using System;
using System.Collections.Generic;

namespace Sandbox {
    class Launcher {
        public static int Main(string[] args) {
            long h4;
            if (args.Length != 1 || !long.TryParse(args[0], out h4)) {
                Console.Error.WriteLine("Usage: Sandbox.exe <hash>");
                return -1;
            }

            // TODO Handle 15-char or longer solutions. 15 chars is the point at which simple mod breaks because the multipliers wrap.
            for (int len = 5; len < 15; len++)
                foreach (long h3 in invAbs(h4))
                    foreach (long h2 in h3Toh2(h3))
                        foreach (long h1 in invAbs(h2))
                            foreach (string soln in solveH1Inner(h1, new char[len], len - 1, 1, 13 + len))
                                Console.WriteLine(soln);

            return 0;
        }

        private static IEnumerable<string> solveH1Inner(long rem, char[] chs, int off, long mul, long mod) {
            if (off < 0) {
                if (rem == 0) yield return new string(chs);
                yield break;
            }

            long mask = (mul & -mul) - 1;
            if ((rem & mask) != 0) yield break;

            foreach (char ch in " !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_{|}~") {
                if ((ch * mul) % mod == rem % mod) {
                    chs[off] = ch;
                    foreach (string soln in solveH1Inner(rem - mul * ch, chs, off - 1, mul * mod, mod - 1))
                        yield return soln;
                }
            }

            yield break;
        }

        private static IEnumerable<long> invAbs(long h4) {
            if (h4 < 0 && h4 != long.MinValue) throw new ArgumentException();
            yield return h4;
            if (h4 != long.MinValue) yield return -h4;
        }

        private static IEnumerable<long> h3Toh2(long h3) {
            // h3 = h2 << (h2 % 11)
            // where h2 is either long.MinValue or non-negative.
            // long.MinValue << (long.MinValue % 11) = 0
            if (h3 == 0) yield return long.MinValue;

            for (int shift = 0; shift < 11; shift++) {
                if (shift == 0 && h3 < 0) continue;

                long mask = (1L << shift) - 1;
                if ((h3 & mask) != 0) break;

                long inc = shift == 0 ? 0 : 1L << (64 - shift);
                long maskBottom = inc - 1;
                long bottom = (h3 >> shift) & maskBottom;
                long top = 0;
                do {
                    if ((top + bottom) % 11 == shift) yield return (top + bottom);
                    top += inc;
                } while (top > 0);
            }
        }
    }
}

```

There are some minor optimisations which could be done, but I think it's more legible like this. (Arguably I should eliminate the enumerators and push the WriteLine in too, but hey).

Example of collisions for 199681664

```
PETER
OTTER
R(DER
Q6SVR
R*&$@

```
> 2 votes

# Answer
I got more than enough answers without reversing both `abs` calls, so I skipped that. They'd be trivial to add back if *really* needed. I'm not even taking `long` overflow into account, but that'd let you insert most any word you like in the greater hashes. As if that was needed to get collisions.

```
import Data.Char
import Data.Bits
import Control.Monad

printables = [32..95]

reverseModShift11 x = do
  let zeros = head $ filter (testBit x) [0..]
  b <- [0 .. zeros]
  let h = x `shiftR` b
  guard $ (h `mod` 11) == (fromIntegral b)
  return h

reverseBase p m n | m < 13    = []
                  | n <  0    = []
                  | n == 0 && m == 13 = return p
                  | otherwise = do
  let r = n `mod` m
  c <- filter (\x -> x `mod` m == r) printables
  reverseBase (chr c:p) (m-1) ((n-c) `div` m)

reverseBases = join . ap (map (reverseBase "") [14..29]) . return

breakHash = reverseModShift11 >=> reverseBases

```

Sample use:

```
*Main> breakHash 224443104
["]#'!'","\\2'!'","[A'!'","ZP'!'","Y_'!'",
  (...)
"[?EAK","ZNEAK","Y]EAK",
  (...)
"] TQ]","\\/TQ]","[>TQ]","ZMTQ]","Y\\TQ]"]

```
> 2 votes

# Answer
# JavaScript 224 LOC

This function will calculate all results of a given length, optionally limited to results starting with a given string, that is if it's done within the 1 second that I have allotted. If no results exist it is done virtually instantly. The function rely heavily on a very slow custom built 64 bit integer library, an equivalent C function would probably be 100 to 1000 times faster. I might set up a nice web interface.

```
<html>
<head>
<title>Break Hash</title>
</head>
<body>
<pre id="out"></pre>
<script>
function to64(inp){
    var res=[]
    res[0]=inp%(256*256*256)
    inp=Math.floor(inp/(256*256*256))
    res[1]=inp%(256*256*256)
    inp=Math.floor(inp/(256*256*256))
    res[2]=inp%(256*256)
    return res
}
function add64(inp1,inp2){
    var res=[]
    res[0]=inp1[0]+inp2[0]
    res[1]=inp1[1]+inp2[1]+Math.floor(res[0]/(256*256*256))
    res[2]=(inp1[2]+inp2[2]+Math.floor(res[1]/(256*256*256)))&(256*256-1)
    res[0]&=(256*256*256-1)
    res[1]&=(256*256*256-1)
    return res
}
function neg64(inp){
    var res=[]
    res[0]=inp[0]^(256*256*256-1)
    res[1]=inp[1]^(256*256*256-1)
    res[2]=inp[2]^(256*256-1)
    return add64(res,[1,0,0])
}
function abs64(inp){
    if(inp[2]>=(256*128)){
        return neg64(inp)
    }
    return inp
}
function mul64(inp1,inp2){
    var res=[]
    res[0]=inp1[0]*inp2[0]
    res[1]=inp1[1]*inp2[0]+inp1[0]*inp2[1]+Math.floor(res[0]/(256*256*256))
    res[2]=inp1[2]*inp2[0]+inp1[1]*inp2[1]+inp1[0]*inp2[2]+Math.floor(res[1]/(256*256*256))
    overflow=(res[2]>=(256*256)) //Global shortcut
    res[2]&=(256*256-1)
    res[0]&=(256*256*256-1)
    res[1]&=(256*256*256-1)
    return res
}
function mod64(inp1,inp2){ //64,float -> float
    var res=inp1[2]%inp2
    res=(res*(256*256*256)+inp1[1])%inp2
    return (res*(256*256*256)+inp1[0])%inp2
}
function div64(inp1,inp2){ //64,float -> 64
    var res=[]
    res[2]=Math.floor(inp1[2]/inp2)
    var mem1=inp1[1]+(inp1[2]%inp2)*(256*256*256)
    res[1]=Math.floor(mem1/inp2)
    res[0]=Math.floor((inp1[0]+(mem1%inp2)*(256*256*256))/inp2)
    return add64(res,[0,0,0])
}
function cmp64(inp1,inp2){
    for(var a=2;a>=0;a--){
        if(inp1[a]>inp2[a]){
            return 1
        }
        if(inp1[a]<inp2[a]){
            return -1
        }
    }
    return 0
}
function string64(inp){
    var res=""
    while(cmp64(inp,[0,0,0])){
        res=mod64(inp,10)+res
        inp=div64(inp,10)
    }
    return res||"0"
}

function hashPassword(password){
    var i
    password=stringtoarray(password)
    var hash = to64(0);
    var multiplier = to64(13);
    for (i = 0; i < password.length; i++){
        multiplier = add64(multiplier,[1,0,0])
        hash = add64(mul64(hash,multiplier),to64(password[i]));
    }
    hash = abs64(hash);
    hash = mul64(hash,to64(Math.pow(2,mod64(hash,11))));
    hash = abs64(hash);
    return string64(hash)
}
function stringtoarray(password){
    var i
    if((typeof password)=="string"){
        var password2 = password.toUpperCase();
        password=[]
        for(i=0;i<password2.length;i++){
            password[i]=password2.charCodeAt(i)
        }
    }
    return password
}

function reverse(hash,start,len){
    var maxtime=(+new Date())+1000
    var m1=neg64(to64(1))
    start=stringtoarray(start)
    var multipliers=[]
    var multipliersum=[]
    var max=[]
    var min=[]
    var firstlimit=0
    multipliers[len-1]=[1,0,0]
    multipliersum[len-1]=[1,0,0]
    max[len-1]=[126,0,0]
    min[len-1]=[32,0,0]
    for(var a=len-2;a>=0;a--){
        multipliers[a]=mul64(multipliers[a+1],to64(15+a))
        multipliersum[a]=add64(multipliers[a],multipliersum[a+1])
        min[a]=mul64(multipliersum[a],[32,0,0])
        max[a]=mul64(multipliersum[a],[126,0,0])
        if(overflow && !firstlimit){
            firstlimit=a+1
        }
    }
    var startvalue=[0,0,0]
    for(var a=0;a<start.length;a++){
        startvalue=add64(startvalue,mul64(to64(start[a]),multipliers[a]))
    }
    startvalue=neg64(startvalue)

    allowed=[]
    for(a=0;a<32;a++){
        allowed[a]=false
    }
    for(a=32;a<97;a++){
        allowed[a]=true
    }
    for(a=97;a<123;a++){
        allowed[a]=false
    }
    for(a=123;a<127;a++){
        allowed[a]=true
    }
    for(a=127;a<256;a++){
        allowed[a]=false
    }
    var results=[]
    function arrtostring(arr){
        str=""
        for(var a=0;a<arr.length;a++){
            //str+=String.fromCharCode(arr[a])
            str+="&#"+arr[a]+";"
        }
        return str
    }
    function makepwd(ihash){ //This is where clock cycles go to die
        ihash=add64(ihash,startvalue)
        stringarr=[]
        for(var a=0;a<start.length;a++){
            stringarr[a]=start[a]
        }
        function addrest(ihash,startfrom){
            if(maxtime<(+new Date())){
                return
            }
            var a
            var jhash
            if(startfrom==len){
                if(cmp64(ihash,[0,0,0])==0){
                    results[results.length]=arrtostring(stringarr)
                }
            }
            else if(startfrom<firstlimit || ((cmp64(ihash,min[startfrom])!=-1) && (cmp64(ihash,max[startfrom])!=1))){
                for(a=32;a<127;a++){
                    if(allowed[a]){
                        jhash=add64(ihash,neg64(mul64(to64(a),multipliers[startfrom])))
                        stringarr[startfrom]=a
                        addrest(jhash,startfrom+1)
                    }
                }
            }
        }
        addrest(ihash,start.length)
    }
    function reversemod(ihash){
        if(ihash[2]<(128*256)){
            if(mod64(ihash,11)==0){
                makepwd(ihash)
                makepwd(neg64(ihash))
            }
        }
        var modresult=1
        var a
        var addlim
        var jhash
        while(mod64(ihash,2)==0){
            ihash=div64(ihash,2)
            addlim=Math.pow(2,modresult-1)
            for(a=0;a<addlim;a++){
                jhash=add64(to64(a*Math.pow(2,64-modresult)),ihash)
                if(mod64(jhash,11)==modresult){
                    makepwd(jhash)
                    makepwd(neg64(jhash))
                }
            }
            modresult++
        }
    }
    reversemod(hash)
    reversemod(neg64(hash))
    return results
}

document.getElementById("out").innerHTML=reverse(to64(224443104),"ebusiness",22).join("<br>")
//document.getElementById("out").innerHTML=hashPassword("EBUSINESS\"XUWL]NHHHF{I")
</script>
</body>
</html>

```

Some collisions for 224443104

```
EBUSINESS"XUWL]NHHHF{I
EBUSINESS"XUWL]NHHHF|&
EBUSINESS"XUWL]NHHHGYI
EBUSINESS"XUWL]NHHHGZ&
EBUSINESS"XUWL]NHHHH7I

```
> 2 votes

---
Tags: cryptography, programming-puzzle
---


title: Solve the 8 Puzzle

text:
# Question
Title: Solve the 8 Puzzle
The 8 Puzzle is the smaller variant of the 15Puzzle (or the Sliding puzzle). You have a `3x3` grid which is filled with numbers from 0-8 (0 denotes the blank tile) arranged in a random order. Your task is to input a 3x3 grid and show the shortest solution (minimum moves) to get to the goal state. Display each boardstate including the first state in the output.

There may be multiple optimal solutions, you just need to print one.

Input: (small example)

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

```

Output:

```
2 <- denotes minimum number of moves required
1 2 0
4 5 3
7 8 6

1 2 3
4 5 0
7 8 6

1 2 3
4 5 6
7 8 0 <- goal state

```

If the puzzle can't be solved, print just `-1` (denoting unsolvable)

**Edit**: Time limit : \< 30seconds.

# Answer
## Python, 418 characters

The code exhaustively enumerates all positions and makes maps of their depth (D), and a position one closer to solved (E). Then it looks up the goal state to get the output.

```
D={(1,2,3,4,5,6,7,8,0):0}
E=D.copy()
def Z(a,d):
 b=list(a);b[i],b[i+d]=b[i+d],0;b=tuple(b)
 if b not in E:E[b]=a;D[b]=D[a]+1
for x in' '*32:
 for a in E.copy():
  i=list(a).index(0)
  if i>2:Z(a,-3)
  if i%3:Z(a,-1)
  if i%3<2:Z(a,1)
  if i<6:Z(a,3)
g=[]
for x in' '*3:g+=map(int,raw_input().split())
g=tuple(g)
if g in E:
 print D[g]
 while g:
  for i in(0,3,6):print'%d %d %d'%g[i:i+3]
  g=E[g];print
else:print -1

```
> 6 votes

---
Tags: code-golf, sliding-puzzle
---


title: The fourth power (Juzuk)

text:
# Question
Title: The fourth power (Juzuk)
In 1939 Juzuk described a way to generate the fourth powers of natural numbers. Group the natural numbers like this:

```
1   2 3   4 5 6   7 8 9 10   11 12 13 14 15   ...

```

Scratch each second group:

```
1   4 5 6   11 12 13 14 15 ...

```

The sum of the *n* remaining groups is *n*\**4.

* **Input**: none
* **Task**: print the fourth powers upto 100\**4, using Juzuk's method.
* **Output**:

0 (optional) 1 16 81 ... 100000000

# Answer
## J, ~~40~~ 38 (*not* summing unneeded)

```
+/\+/"1(+:i.100){(#~i.201)[/.>:i.20100

```

## J, 30 (summing unneeded)

```
+/\_2{.\(#~i.201)+//.>:i.20100

```
> 3 votes

# Answer
## J, 33

```
~.+/\(#~i.200)(+/*2|#)/.1+i.2!200

```
> 4 votes

# Answer
**Haskell, 78**

```
print[sum$concat$take x[take x$drop(sum[1..x-1])[1..]|x<-[1,3..]]|x<-[0..100]]
[0,1,16,81,256,625,1296,2401,4096,6561,10000,14641,20736,28561,38416,50625,65536,...

```

Hope the slightly different output formatting is ok. There's probably a much better way to write this in Haskell, but I felt like solving this in a language I don't often use.
> 3 votes

# Answer
## Python 2, 68

Quick and dirty Python solution:

```
s=0
for n in range(100):s+=sum(range(2*n*n+n+1,2*n*n+3*n+2));print s

```
> 3 votes

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


title: Build a simple proxy

text:
# Question
Title: Build a simple proxy
Make the shortest proxy server.

### Input/Output Specifications

Client:

* Input: a port number (32-bit integer) **(,) or (space)** a url (see test cases)
* Output: html source of the url

Server:

* Input: port to listen to (32-bit integer)
* Output: **REC** when input is received from the client, **OK** when finished sending the html source to the client.

### Rules

* You may make either a **complete program** or **functions in an interpreted language**.
* Input is taken through **stdin** or given as a **arguments**.
* Your code has to work for the given **test cases only** (more is optional, less is invalid).
* The client output has to be the same as with what you get when you "view source" from a browser.
* The server **may exit** after each handled request (i.e does not have to be persistent/daemon)
* (**edit**) Any other input/output than what specified, is forbidden.

### Test cases (client inputs)

1. N1 https://stackoverflow.com/
2. N2 http://en.wikipedia.org/wiki/Proxy\_server
3. N3 http://stackexchange.com/search?q=code+golf

where Ni are random integers between 1 and 2048.

# Answer
## ZSH - 57 + 42 characters

Server:

```
s=$(nc -l $1)
echo REC
curl -s $s|nc 127.0.0.1 $1
echo OK

```

Client:

```
echo $2|nc 127.0.0.1 $1
echo "$(nc -l $1)"

```

Usage:

```
sudo zsh server.zsh 123

sudo zsh client.zsh 123 http://stackoverflow.com/
sudo zsh client.zsh 123 http://en.wikipedia.org/wiki/Proxy_server
sudo zsh client.zsh 123 "http://stackexchange.com/search?q=code+golf"

```
> 5 votes

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


# Question
Title: Turn 2D boolean array into (rectilinear) polygons
## Challenge

Write a program which, given a 2-dimensional boolean array (equivalently, a monochromatic bitmap), outputs a series of polygons that describe the outline of the region that is “true” (1).

The input is provided as a sequence of `'#'` (hash), `' '` (space) and `\n` (newline) characters. Lines may differ in length, in which case the missing parts are assumed to be spaces. The output should be a (newline-separated) list of polygons, each polygon represented by a (comma-separated) list of coordinates.

## Examples & Requirements

1. **The co-ordinates must be listed in clockwise order.** Input:

```
#

```

Acceptable outputs include:

```
(0,0), (1,0), (1,1), (0,1)

(1,0), (1,1), (0,1), (0,0)

(1,1), (0,1), (0,0), (1,0)

(0,1), (0,0), (1,0), (1,1)

```
2. **Disjoint regions must return multiple polygons.** Input:

```
# #

```

Example output (actual output must consist of two lines):

```
(0,0), (1,0), (1,1), (0,1)
(2,0), (3,0), (3,1), (2,1)

```
3. **Holes in a polygon must be listed as a separate polygon, but in anti-clockwise order.** Input:

```
###
# #
###

```

Example output:

```
(0,0), (3,0), (3,3), (0,3)
(1,1), (1,2), (2,2), (2,1)

```
4. You are free to choose whether **diagonally adjacent vertices join up or not.** Input:

```
#
 #

```

Example output:

```
(0,0), (1,0), (1,1), (0,1)
(1,1), (2,1), (2,2), (1,2)

```

or

```
(0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)

```
5. The lists of coordinates need not be optimally short. For example:

```
##

```

Acceptable outputs:

```
(0,0), (2,0), (2,1), (0,1)

// Redundant coordinates along a straight line are acceptable
(0,0), (1,0), (2,0), (2,1), (1,1), (0,1)

// Duplicate start- and end-point are acceptable
(0,0), (2,0), (2,1), (0,1), (0,0)

```

As usual, shortest program “wins”.

# Answer
## Perl, ~~345~~ ~~311~~ 265 chars

```
s!.!$i{$x++}=$&eq'#'!ge,$x=$r+=64for<>;sub a{$d+=@_||3;$d%=4;$y=$x%64;$z=$x>>6;$c.=", ($y,$z)";}for$x(keys%i){if($c=!$v{$x}&$i{$x}&!$i{$x-1}){$i{($x+=(1,64)[$d^3])-(64,65,1)[$d]}?$i{$x-(65,1,0,64)[$d]}?a 1:($x-=(64,1)[$d]):a while$d||!$v{$x}++;print substr$c.$/,3}}

```

### Limitations

Assumes that the input is no wider than 64 characters (but its height is in principle unbounded). This can be extended to 512 or 8192 or any other power of two by changing the relevant constants, making the code only slightly longer.

### Slightly more readable version

Some credit goes to mob because the first line is my re-use of his idea in lasers. The rest is entirely my work.

```
# Read “%i”nput (this line is essentially mob’s idea, see above)
s!.! $i{$x++} = $& eq '#' !ge, $x = $r += 64 for <>;

# Subroutine to add a vertex to the current polygon and change the current “$d”irection
sub a
{
    $d += @_ || 3;
    $d %= 4;
    $y = $x % 64;
    $z = $x >> 6;
    $c .= ", ($y,$z)";
}

for $x (keys %i)
{
    # Go to the next “upward-pointing” edge that we haven’t already “%v”isited.
    if ($c = !$v{$x} & $i{$x} & !$i{$x-1})
    {
        # We’re going in the “$d”irection of 0=up, 1=left, 2=down, 3=right
        $i{($x += (1,64)[$d^3]) - (64,65,1)[$d]}
        ?  $i{$x - (65,1,0,64)[$d]}
           ?  a 1               # take a 90° turn to the left
           : ($x -= (64,1)[$d]) # move straight ahead
        : a                     # take a 90° turn to the right

        # Only stop if the current “$d”irection is “up” and we encounter a “%v”isited edge
        # (which necessarily is the one we started from)
        while $d || !$v{$x}++;

        # Remove “1, ” and output this polygon
        print substr $c.$/, 3
    }
}

```

### Edits

* **(345 → 312)** Realised there’s no need to update `$x` when taking a turn because the next iteration will already do it
* **(312 → 311)** Change `1`=down,`2`=left to `1`=left,`2`=down and update `$d` via XOR instead of directly
* **(311 → 265)** Remove repetition of the innermost expression and use arrays to parametrise it
> 3 votes

# Answer
## Python, 607 characters

The code works by keeping a list of the boundaries discovered so far as it processes # symbols in input order. The boundaries are stored in a table E which maps edges (4-tuples of x\_start,y\_start,x\_end,y\_end) to a list of edges which form the boundary of a polygon. As we process each new #, it may be connected to a polygon above (p) or to its left (q). The code finds p and q using E and then merges the boundary of the current # (r) with p and q, if they exist. The case where p==q generates holes.

```
import sys
x=y=N=0
E={}
def P(L):
 if L:print ', '.join(map(lambda z:str(z[:2]),L))
while 1:
 r,a,b,c=[(x,y,x+1,y),(x+1,y,x+1,y+1),(x+1,y+1,x,y+1),(x,y+1,x,y)],(x+1,y,x,y),(x,y,x,y\
+1),sys.stdin.read(1)
 if not c:break
 p,q=E.get(a),E.get(b)
 if'#'==c:
  if p:
   i=p.index(a)
   if q:
    j=q.index(b)
    if p==q:
     if i<j:P(p[i+1:j]);p[i:j+1]=r[1:3]
     else:P(p[i+1:]+p[:j]);p[i:]=r[1:3];p[0:j+1]=[]
    else:p[i:i+1]=r[1:3]+q[j+1:]+q[:j]
   else:p[i:i+1]=r[1:]
  elif q:j=q.index(b);q[j:j+1]=r[:3];p=q
  else:p=r
  for e in p:E[e]=p
 x+=1
 if'\n'==c:y+=1;x=0
for L in E.values():
 if L:P(L);L[:]=[]

```
> 2 votes

---
Tags: code-golf, geometry, optimized-output
---


# Question
Title: Find all number pairs that sum to 121212
This problem is quite easy to do by brute force. In fact, it'll be reasonably fast to brute force as well. But where's the fun in that?

## The Problem

Produce a list of all unique 5 digit number pairs that sum to `121212`. However, each decimal digit must appear exactly once in either number. So a valid pair would be `(98167, 23045)`. But an invalid pair would be `(23456, 97756)` because `7, 5, 6` are repeated more than once, and `1, 8, 0` are not used at all. There are exactly 192 unique pairs.

## Rules

1. *Efficiency:* You can brute force this. But that's trivial to do. So instead, the real challenge here is to find a way to efficiently produce the list of numbers.
2. *Source Code Requirements:* It cannot store the number list (or any part of it). The number sequence **must** be generated on the fly.

Have Fun!

# Answer
# JavaScript

```
function findpairs(arrin1,arrin2){
    functioncount++
    var arr1=[]
    var arr2=[]
    var strike=[]
    var overflow=0
    var b
    var len=arrin1.length
    for(var a=0;a<len;a++){
        arr1[a]=arrin1[a]
        arr2[a]=arrin2[a]
        strike[arr1[a]]=true
        strike[arr2[a]]=true
        overflow=+((arr1[a]+arr2[a])>9)
    }
    var desired=12-(len%2)-overflow
    for(a=9;a>0;a--){
        b=(desired-a)%10
        if(a>b && !strike[a] && !strike[b]){
            if(len==4){
                if((a+b)>9){
                    document.write(""+a+arr1[3]+arr1[2]+arr1[1]+arr1[0]+" "+b+arr2[3]+arr2[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr1[1]+arr2[0]+" "+b+arr2[3]+arr2[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr2[1]+arr1[0]+" "+b+arr2[3]+arr2[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr1[2]+arr2[1]+arr2[0]+" "+b+arr2[3]+arr2[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr1[1]+arr1[0]+" "+b+arr2[3]+arr1[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr1[1]+arr2[0]+" "+b+arr2[3]+arr1[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr2[1]+arr1[0]+" "+b+arr2[3]+arr1[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr1[3]+arr2[2]+arr2[1]+arr2[0]+" "+b+arr2[3]+arr1[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr1[1]+arr1[0]+" "+b+arr1[3]+arr2[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr1[1]+arr2[0]+" "+b+arr1[3]+arr2[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr2[1]+arr1[0]+" "+b+arr1[3]+arr2[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr1[2]+arr2[1]+arr2[0]+" "+b+arr1[3]+arr2[2]+arr1[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr1[1]+arr1[0]+" "+b+arr1[3]+arr1[2]+arr2[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr1[1]+arr2[0]+" "+b+arr1[3]+arr1[2]+arr2[1]+arr1[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr2[1]+arr1[0]+" "+b+arr1[3]+arr1[2]+arr1[1]+arr2[0]+"<br>")
                    document.write(""+a+arr2[3]+arr2[2]+arr2[1]+arr2[0]+" "+b+arr1[3]+arr1[2]+arr1[1]+arr1[0]+"<br>")
                    resultcount+=16
                }
            }
            else{
                arr1[len]=a
                arr2[len]=b
                findpairs(arr1,arr2)
            }
        }
    }
}
resultcount=0
functioncount=0
start=+new Date()
findpairs([],[])
end=+new Date()
document.write("<br>"+resultcount+" results<br>"+(end-start)+" ms<br>"+functioncount+" function calls")

```

Hosted at: http://ebusiness.hopto.org/findpairs.htm

Mathematical realization: If you have one pair 15 others can trivially be generated by swapping digits between the two numbers, therefore I only search for numbers where the digits of the first are all greater than the digits of the second, and then simply output all the permutations.

I start from the least significant digits and generate the sequence as a tree traversal, for each step asserting that the intermediate result is correct and that no digits are spent twice. With these methods the function need only be called 50 times in total. On my machine Chrome yield runtime results of typically 2 ms.
> 6 votes

# Answer
**C++**

```
#include<iostream>
using namespace std;
#include<algorithm>

int main()
{
    long long N,F,S;
    char str[11]="1023456789";
    while (1) {
        sscanf(str,"%lld",&N);
        F=N/100000;S=N%100000;
        if (F>60000)
           break;
        if (F+S==121212)
           printf("%lld %lld\n",F,S);
        next_permutation(str,str+10);
    }
}

```

http://www.ideone.com/Lr84g
> 8 votes

# Answer
Python 2.

It's pretty efficient because it constructs the numbers (the inner-most loop is executed 4570 times total) and pretty short because I golfed a little (201 characters), but I'm not really sure I want to *explain* this :)

```
p=lambda t,a,d:((x,y)for x in range(10)for y in[(t-x-a)%10]if(x not in d)&(y not in d)and x-y)
w=lambda s:[s]if len(s)==10and s[:5]<s[5:]else(m for n in p(2-len(s)/2%2,sum(s[-2:])/10,s)for m in w(s+n))

```

The returned values are pretty peculiar, though: call `w` with an empty tuple, and you get an iterator of 10-tuples. These 10 tuples are the digits of the two numbers, alas *backwards* and *alternating*, i.e. the tuple

```
(2, 0, 8, 3, 7, 4, 9, 1, 6, 5)

```

represents the numbers 51430 and 69782.

Test:

```
result = list(w(()))

assert len(set(result)) == 192               # found all values
assert len(result) == 192                    # and no dupes

for digits in result:
    assert all(0 <= d <= 9 for d in digits)  # real digits -- zero through nine
    assert len(set(digits)) == 10            # all digits distinct

    n1 = int("".join(map(str, digits[9::-2])))
    n2 = int("".join(map(str, digits[8::-2])))

    assert n1 + n2 == 121212                 # sum is correct

```

Here is the ungolfed version:

```
ppcalls = 0       # number of calls to possiblePairs
ppyields = 0      # number of pairs yielded by possiblePairs
ppconstructed = 0 # number of construced pairs; this is the number
                  #     of times we enter the innermost loop

def possiblePairs(theirSumMod10, addition, disallowed):
    global ppcalls, ppyields, ppconstructed
    ppcalls += 1
    for a in range(10):
        b = (theirSumMod10 - a - addition) % 10
        ppconstructed += 1
        if a not in disallowed and b not in disallowed and a != b:
            ppyields += 1
            yield (a, b)

def go(sofar):
    if len(sofar) == 10:
        if sofar[:5] < sofar[5:]: # dedupe
            yield sofar

    digitsum = 2 - (len(sofar) / 2) % 2 # 1 or 2, alternating

    for newpair in possiblePairs(digitsum, sum(sofar[-2:]) / 10, sofar):
        for more in go(sofar + newpair):
            yield more

list(go(()))        # iterate

print ppcalls       # 457
print ppyields      # 840
print ppconstructed # 4570

```
> 4 votes

# Answer
## C

```
#include <stdio.h>

int mask(int n)
{
    int ret = 0;

    for (; n > 0; n /= 10)
        ret |= 1 << n % 10;

    return ret;
}

int main(void)
{
    int a, b;

    for (a = 21213, b = 99999; a < b; a++, b--)
        if ((mask(a) | mask(b)) == 0x3FF)
            printf("%d %d\n", a, b);

    return 0;
}

```

This traverses all pairs of 5-digit numbers that sum to 121212 (meaning 39393 iterations, or ~1/46th of the iterations used by fR0DDY's answer). For each pair, it forms a bit mask of the digits in each number, then sees if they OR to 0b1111111111.
> 3 votes

# Answer
## Javascript (481)

```
function m(d,i){o=d-i;if(0<=o&&o<=9&&o!=i)return o;o+=10;if(0<=o&&o<=9&&o!=i)return o;return}function p(n,a){x=0;r=[];d=n%10;for(i=0;i<10;i++){if((!a||!a.contains(i))&&(o=m(d,i))&&(!a||!a.contains(o))&&i+o<=n)r[x++]=[i,o]}return r}function f(n,a){var x=0;var r=[];var d=p(n,a);for(var i=0;i<d.length;i++){var s=Math.floor((n-d[i][0]-d[i][1])/10);if(s>0){var t=f(s,d[i].concat(a));for(var j=0;j<t.length;j++)r[x++]=[t[j][0]*10+d[i][0],t[j][1]*10+d[i][1]]}else{r[x++]=d[i]}}return r}

```

http://jsfiddle.net/XAYr3/4/

Basic idea: generate combinations of valid digits that can be used in the right-most column. For instance, (0,2), (3,9), (4,8), (5,7). For each combination, recursively find pairs that work for the next-from-right digit, without duplicating digits in the first pair. Recurse until a pair of 5-digit numbers has been generated. Combine all those results into a single array, and the list is 192 elements. This I believe should require about the fewest iterations, but all of the array allocation/deallocation makes it overall somewhat practically inefficient.

My counting tests show that function `f` is called 310 times, the inner loop `i` is executed 501 times total (across all calls to `f`), and the inner-inner loop `j` is executed 768 times total (across everything).
> 2 votes

# Answer
## Python, 171 characters

```
def R(x,y,d,c):
 if not d and x<y:print x,y
 for p in d:
  q=(12-c%2-p-(x+y)/10**c)%10
  if p-q and q in d:R(x+p*10**c,y+q*10**c,d-set([p,q]),c+1)
R(0,0,set(range(10)),0)

```

The code maintains the invariant that `x`,`y` have `c` digits and that all the unused digits are in the set `d`.

The routine `R` is called a total of 841 times, which is pretty efficient.
> 1 votes

# Answer
**C++**

```
#include<iostream>
using namespace std;
#include<algorithm>
#include<cstring>

int main()
{
        int i;
        char str1[11]="0123456789",str2[11];
        for (i=99999;i>60000;i--)
        {
                sprintf(str2,"%d%d",i,121212-i);
                sort(str2,str2+10);
                if(!strcmp(str1,str2))
                        printf("%d %d\n",i,121212-i);
        }
}

```

http://www.ideone.com/Lr84g
> 0 votes

---
Tags: code-challenge, generation
---


title: Simple Geometric problem

text:
# Question
Title: Simple Geometric problem
This problem (see below) has been given as a High School Programming League code golf challenge. The shortest codes submitted during the contest were: 177 bytes in Ruby, 212 bytes in Python 2.5, 265 bytes in C. Can anyone make it shorter? Other programming languages are also allowed.

**Problem formulation**: Given 8 integers: -1000 \< x1, y1, x2, y2, x3, y3, x4, y4 \< 1000. Check what is the shape of the intersection of two axis-aligned rectangles: P1 = (x1, y1), (x1, y2), (x2, y2), (x2, y1) and P2 = (x3, y3), (x3, y4), (x4, y4), (x4, y3).

```
* If the rectangles do not intersect print *nothing*.
* If there is exactly one point in common print *point*.
* If the intersections of P1 and P2 is a line segment print *line*.
* If they have a rectangular area in common print *rectangle*.

```

**Input data specification**: The first line contains the number of test cases *t* (1\<=*t*\<1000). Each of the following t lines contains 8 integers: x1, y1, x2, y2, x3, y3, x4, y4 (The area of both rectangles is greater than 0).

You can test your solution here.

# Answer
> 4 votes
## Python, 200 characters

```
f=lambda a,b,c,d:min(2,sum((x-c)*(x-d)<=0for x in range(min(a,b),max(a,b)+1)))
for i in' '*input():z=map(int,raw_input().split());print('nothing','point','line',0,'rectangle')[f(*z[::2])*f(*z[1::2])]

```

`f` returns:

```
0 if the intervals [a,b] and [c,d] don't overlap
1 if the intervals [a,b] and [c,d] overlap in only one point
2 if the intervals [a,b] and [c,d] overlap in a range of points

```

# Answer
> 3 votes
**OCaml, 265 chars**

```
let a,c,p=abs,compare,print_endline
let q s t u v w x y z=match
c(a(s-u)+a(w-y))(a(s+u-w-y)),
c(a(t-v)+a(x-z))(a(t+v-x-z))with
0,0->p"point"|0,1|1,0->p"line"|1,1->p"rectangle"|_->p"nothing"
let()=for n=1 to read_int()do Scanf.scanf"%d %d %d %d %d %d %d %d\n"q done

```

Uses (abuses) the fact that compare returns 0, 1 or -1. This is not guaranteed according to its documentation but true with OCaml 3.10.1.

---
Tags: code-golf, geometry
---


title: Write a compressing util for gzip files

text:
# Question
Title: Write a compressing util for gzip files
The task of this challenge is as following:

Write a program that reads a file of reasonable size (let's say \<16 MB) from stdin or anywhere else (however you like, but must not be hardcoded), and put's the compressed output onto stdout. The output must be a valid gzip compressed file and if the compressed file runs through gunzip, it should yield exactly the same file as before.

## Rules

* The programming language used must be known *before* this competition started
* The score of your program is the number of characters of the source code or the assembled program (whatever is shorter)
* You're not allowed to use any kind of existing compression libraries.
* Have fun!

# Answer
# C# (534 characters)

```
using System.IO;using B=System.Byte;class X{static void Main(string[]a){var f=File.ReadAllBytes(a[0]);int l=f.Length,i=0,j;var p=new uint[256];for(uint k=0,r=0;k<256;r=++k){for(j=0;j<8;j++)r=r>>1^(r&1)*0xedb88320;p[k]=r;}uint c=~(uint)0,n=c;using(var o=File.Open(a[0]+".gz",FileMode.Create)){o.Write(new B[]{31,139,8,0,0,0,0,0,4,11},0,10);for(;i<l;i++){o.Write(new B[]{(B)(i<l-1?0:1),1,0,254,255,f[i]},0,6);c=p[(c^f[i])&0xFF]^c>>8;}c^=n;o.Write(new[]{(B)c,(B)(c>>8),(B)(c>>16),(B)(c>>24),(B)l,(B)(l>>8),(B)(l>>16),(B)(l>>24)},0,8);}}}

```

### Much more readable:

```
using System.IO;
using B = System.Byte;
class X
{
    static void Main(string[] a)
    {
        // Read file contents
        var f = File.ReadAllBytes(a[0]);
        int l = f.Length, i = 0, j;

        // Initialise table for CRC hashsum
        var p = new uint[256];
        for (uint k = 0, r = 0; k < 256; r = ++k)
        {
            for (j = 0; j < 8; j++)
                r = r >> 1 ^ (r & 1) * 0xedb88320;
            p[k] = r;
        }

        uint c = ~(uint) 0, n = c;

        // Write the output file
        using (var o = File.Open(a[0] + ".gz", FileMode.Create))
        {
            // gzip header
            o.Write(new B[] { 31, 139, 8, 0, 0, 0, 0, 0, 4, 11 }, 0, 10);
            for (; i < l; i++)
            {
                // deflate block header plus one byte of payload
                o.Write(new B[] { (B) (i < l - 1 ? 0 : 1), 1, 0, 254, 255, f[i] }, 0, 6);
                // Compute CRC checksum
                c = p[(c ^ f[i]) & 0xFF] ^ c >> 8;
            }
            c ^= n;
            o.Write(new[] {
                // CRC checksum
                (B) c, (B) (c >> 8), (B) (c >> 16), (B) (c >> 24),
                // original file size
                (B) l, (B) (l >> 8), (B) (l >> 16), (B) (l >> 24)
            }, 0, 8);
        }
    }
}

```

### Comments:

* Expects path to file as first command-line argument.
* Output file is input file + `.gz`.
* I am not using any libraries to do the gzip, deflate or CRC32. It’s all in there.
* This “compressor” increases the filesize by a factor of 6. But it’s in valid gzip format!
* Tested using GNU gunzip and WinRAR.
> 11 votes

---
Tags: code-golf, compression
---


title: ->The Tragedy of Macbeth<-

text:
# Question
Title: ->The Tragedy of Macbeth<-
# The Setup

---

Here you can find the full text of *The Tragedy of Macbeth*. If you view the source, and save it as text, you will notice it comes out to 206,244 total characters (including the whitespace at the end of the html).

# The Challenge

---

Write a program which compresses the text linked above into the smallest possible text file which can then reproduce the original text **exactly** (including the whitespace).

# The Rules

---

Your program cannot have any prior knowledge of the text it is compressing. The goal however is still to compress this specific text, so don't worry if it sucks at other text as long as it does the best job possible on *Macbeth*.

The program must take either "compress" or "decompress" as the first parameter and the text file as the second command line parameter. The compressed output has to be a text file, and it has to be UTF16. The compressed output when decompressed must match exactly the original file in a character for character comparison.

The program needs to finish in a reasonable amount of time. If it takes longer than a few seconds, please list the average running time with your submission.

# The Scoring

---

The only score is the number of characters in the compressed output. The score only counts if the decompress matches the original in a character for character comparison.

# Answer
## Pseudo-code, compresses Macbeth to 0 bytes

Counter-example (yeah, almost joke) submission intended to point out the flaws with the question. (the C# was a bit long both in source size and resulting output)

```
if argument is "compress"
  compare entire input file to the Tragedy of Macbeth
  if equal, then output empty file
  else if input is non-empty,
    then RLE-encode input stream on chr(127) only and output that
  else [if input is empty]
    then RLE-encode a string of zero times chr(127)
else if argument is "decompress"
  if input is empty
  then output the Tragedy of Macbeth
  else RLE-decode input file on chr(127) only and output back

```

With this approach, Macbeth is brought down to as short a file as possible. Other text input is usually passed untouched, at worst gains a byte per chr(127) which tend not to occur in actual text.
> 10 votes

# Answer
**Python, compresses to 40,304 bytes.**

Similar to Mark's answer, but uses bzip2 instead of zlib (usually better for plain text.)

```
import bz2 as z,sys;print getattr(z,sys.argv[2])(open(sys.argv[1]).read())

```

Call like so:

```
python macbeth.py macbeth.txt compress > macbeth-compressed.txt
python macbeth.py macbeth.txt uncompress > macbeth-uncompressed.txt

```

Results:

```
thomas@jupiter:~$ python macbeth.py macbeth.txt compress | wc -c
40304

```
> 2 votes

# Answer
# C#, 1 byte compressed

I've hardly ever used C#'s file manipulation capabilities, so I'll try not to screw this up too badly:

```
class Program
{
    //args[0]: "compress" = compress mode, anything else = extract mode
    //args[1]: filename of source
    //args[2]: filename of target
    static void Main(string[] args)
    {
        byte[] info;

        using (FileStream fs = File.Open(args[1], FileMode.Open))
        {
            //read the source file
            info = new byte[fs.Length];
            fs.Read(info, 0, (int)fs.Length);
        }

        byte[] macbeth;

        using (WebClient client = new WebClient())
        {
            //get the real MacBeth
            macbeth = client.DownloadData(@"http://shakespeare.mit.edu/macbeth/full.html");
        }

        if (args[0] == "compress")
        {
            //is this also MacBeth?
            if (Encoding.Default.GetString(macbeth).Equals(Encoding.Default.GetString(info), StringComparison.Ordinal))
            {
                //yep, write a dot
                using (FileStream fsOut = File.Create(args[2]))
                {
                    byte[] infoOut = new UTF8Encoding(true).GetBytes(".");
                    fsOut.Write(infoOut, 0, infoOut.Length);
                }
            }
            else
            {
                //nope, better just copy it
                File.Copy(args[1], args[2];
            }
        }
        else
        {
            //is it a dot?
            if (info.Length == 1 && info[0] == Convert.ToByte("."))
            {
                //yep, write MacBeth
                using (FileStream fsOut = File.Create(args[2]))
                {
                    fsOut.Write(macbeth, 0, macbeth.Length);
                }
            }
            else
            {
                //nope! just copy the file
                File.Copy(args[1], args[2]);
            }
        }
    }
}

```

Compresses MacBeth *all the way down to a single byte.* While admittedly cheesy, this is **technically** within the rules (I checked). If it's good enough for Jon Skeet, it's good enough for me.

Holy smoke, talk about a tiny file size, huh? And it's lossless! I'm going to make a million dollars.
> 2 votes

---
Tags: code-challenge, kolmogorov-complexity
---


title: Koch Snowflake - codegolf

text:
# Question
Title: Koch Snowflake - codegolf
The Koch snowflake (also known as the Koch star and Koch island) is a mathematical curve and one of the earliest fractal curves to have been described. It is based on the Koch curve, which appeared in a 1904 paper titled "On a continuous curve without tangents, constructible from elementary geometry" (original French title: "Sur une courbe continue sans tangente, obtenue par une construction géométrique élémentaire") by the Swedish mathematician Helge von Koch.

Here are some ascii representations of various iterations:

```
n=1
__
\/

n=2
__/\__
\    /
/_  _\
  \/

n=3
      __/\__
      \    /
__/\__/    \__/\__
\                /
/_              _\
  \            /
__/            \__
\                /
/_  __      __  _\
  \/  \    /  \/
      /_  _\
        \/

```

Since there is obviously a limit to the resolution of the ascii representation, we must enlarge the size of the snowflake by a factor of 3 for each iteration to show the extra detail.

Write the shortest code to output the snowflake in the same style for n=4

Your program should not take any input.
Your program should write the snowflake to the console.

# Answer
> 2 votes
## Python, 338 bytes

```
#coding:u8
print u"碜䄎쀠ࢻ﬊翀蝈⼖㗎芰悼컃뚔㓖ᅢ鄒鱖渟犎윽邃淁挢㇌ꎸ⛏偾࿵헝疇颲㬤箁鴩沬饅앎↳\ufaa4軵몳퍋韎巃๧瓠깡未늳蒤ꕴ⁵ᦸ䥝両䣚蟆鼺伍匧䄂앢哪⡈⁙ತ乸ሣ暥ฦꋟ㞨ޯ⿾庾뻛జ⻏燀䲞鷗﫿".encode("utf-16be").decode("zlib")

```

Just another unicode exploit

run at ideone

# Answer
> 10 votes
## Python, 650 612 594 574 characters

```
n='\n'
S='_a/G\F I\n'
A=dict(zip(S,('III','   ','__/','  G','\  ','F__','   ','III','')))
B=dict(zip(S,('III','   ','\  ',' aF','/a ','  G','   ','III','')))
C=dict(zip(S,('___','aaa','/  ','GII','II\\','  F','   ','III','')))
def T(s):
 a=b=c=d=r=u''
 for k in s:
    a+=A[k];b+=B[k];c+=C[k]
    if k=='I':a=a[:-3]+('II\\'if'a '==d[1:3]else'GII'if' a'==d[:2]else 3*k)
    d=d[3:]
    if k==n:d=c.replace('____','__/F').replace('aaaa','aa  ').replace('/  a','/a  ').replace('a  F','  aF');r+=a+n+b+n+d+n;a=b=c=''
 return r
print T(T(T('__\n\G\n'))).translate({97:95,71:47,73:32,70:92})

```

This works by expanding the triangle by a factor of 3 each time. To do that, we need to keep track of whether each symbol is a left or right boundary (e.g. how `/` is expanded depends on which side of the `/` is the inside). We use different symbols for the two possible cases, as follows:

```
_: _, outside on the top
a: _, outside on the bottom
/: /, outside on the left
G: /, outside on the right
\: \, outside on the left
F: \, outside on the right
<space>: inside
I: outside

```

The `d` variable handles the special case where the expansion of an `a` needs to extend into the 3x3 in the next row.

# Answer
> 6 votes
## MS-DOS 16 bit machine code: 199 bytes

Decode using this site, save as 'koch.com' file and execute from WinXP command prompt.

```
sCAAxo7ajsKLz/OquF9fulwvvUoBM9u+BADoiQDodgDocwDogADobQDoagDodwCK8TLSs0+I98cHDQrGRwIktAnNIf7GOO5+7MNWAVwBYwFsAXoBgwGJB4DDAsOIN/7D6QQA/suIF/7P6R0A/suAPyB1AogH/suIB8OBw/8AiDfpBgD+x4gX/sM4734Ciu84z30Cis/Dg8UIg8UCgf1WAXLzg+0Mw07/dgB0GV/o9v/o5v/o8P/o3f/o2v/o5//o1//o4f9Gww==

```

**Update**

Here's an easy-to-read assembler version:

```
  ; L-System Description
  ;
  ; Alphabet : F
  ; Constants : +, -
  ; Axiom : F++F++F
  ; Production rules: F -> F-F++F-F
  ;
  ; Register usage:
  ;                             _        _
  ; bp = direction: 0 = ->, 1 = /|, 2 = |\, 3 = <-, 4 = |/_, 5 = _\|
  ; cl = min y, ch = max y
  ; bl = x (unsigned)
  ; bh = y (signed)
  ; si = max level

  ; clear data
  mov al,20h
  add dh,al
  mov ds,dx
  mov es,dx
  mov cx,di
  rep stosb
  mov ax,'__'
  mov dx,'/\'

  ; initialise variables
  mov bp,Direction0
  xor bx,bx
  mov si,4

  call MoveForward
  call TurnRight
  call TurnRight
  call MoveForward
  call TurnRight
  call TurnRight
  call MoveForward

  mov dh,cl
  xor dl,dl
  mov bl,79
OutputLoop:
  mov bh,dh
  mov w [bx],0a0dh
  mov b [bx+2],24h
  mov ah,9
  int 21h
  inc dh
  cmp dh,ch
  jle OutputLoop
  ret

Direction0:
  dw MoveRight
  dw MoveUpRight
  dw MoveUpLeft
  dw MoveLeft
  dw MoveDownLeft
  dw MoveDownRight
Direction6:

MoveRight:
  mov w [bx],ax
  add bl,2
  ret

MoveUpRight:
  mov b [bx],dh
  inc bl
  jmp DecBHCheckY

MoveUpLeft:
  dec bl
  mov b [bx],dl
DecBHCheckY:
  dec bh
  jmp CheckY

MoveLeft:
  dec bl
  cmp b [bx],20h
  jne MoveLeftAgain
  mov [bx],al
MoveLeftAgain:
  dec bl
  mov [bx],al
  ret

MoveDownLeft:
  add bx,255
  mov b [bx],dh
  jmp CheckY

MoveDownRight:
  inc bh
  mov b [bx],dl
  inc bl

CheckY:
  cmp bh,ch
  jle NoMaxChange
  mov ch,bh
NoMaxChange:
  cmp bh,cl
  jge NoMinChange
  mov cl,bh
NoMinChange:
  ret

TurnRight:
  add bp,8

TurnLeft:
  add bp,2

  cmp bp,Direction6
  jb ret
  sub bp,12
  ret

MoveForward:
  dec si
  push [bp]
  jz DontRecurse
  pop di
  call MoveForward
  call TurnLeft
  call MoveForward
  call TurnRight
  call TurnRight
  call MoveForward
  call TurnLeft
  call MoveForward
DontRecurse:
  inc si
  ret

```

# Answer
> 4 votes
# Perl, ~~176~~ 175 bytes

Posting this as a separate answer because it uses a binary source file, which is perhaps a bit cheaty. But considering that it’s still Perl *source code,* I think it’s remarkable that it beats the MS-DOS *machine code* solution!

### Source as base64-encoded

```
JF89IsLApwag0dhnMmAmMEcGIAcGQNHYwsDRFLsQ0djCwKcGoNHYwsDRFDdbECYwcRUxe1DCwNEUuxDR2
CI7c14uXiR4PW9yZCQmOyQieCgkeD4+MykucXcoXCAvXyBfXy8gXC8gX18gX1wgLyBfXy9cX18pWyR4Jj
ddXmVnO3NeLnsyN31eJF89cmV2ZXJzZSQmO3l+L1xcflxcL347cHJpbnQkJi4kXy4kL15lZw==

```

### Somewhat more readable

Replace all instances of `/<[0-9a-f]+>/` with the relevant binary data:

```
# Raw data!
$_="<c2c0a706a0d1d86732602630470620070640d1d8c2c0d114bb10d1d8c2>".
   "<c0a706a0d1d8c2c0d114375b1026307115317b50c2c0d114bb10d1d8>";

# Decode left half of the snowflake (without newlines)
s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;

# Reconstruct the right half and the newlines
s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg

```

In this version, the snowflake is encoded in the following way:

* The 8 bits in each byte are divided like this:

```
+---+---+---+---+---+---+---+---+
|      5 bits       |   3 bits  |
+---+---+---+---+---+---+---+---+
          R               C

```
* `R` encodes a run of spaces. The longest run is 27 characters, so all runs fit into 5 bits.
* `C` encodes a sequence of characters which are simply looked up in the literal array. (I used to have slightly crazier encodings here where the array contained only `/ \ _`, but the Perl code necessary to decode it was longer...)
* I am lucky that the binary data does not contain any `"`/`'` or `\` that would need escaping. I didn’t plan for this. But even if it did, I probably could have just changed the order of the items in the array to fix that.
* It is amazing how simple this solution is compared to the tens of other solutions I went through before I came up with this. I experimented with many different bitwise encodings more complex than this one, and it never occurred to me that a simpler one might be worth it simply because the Perl code to decode it would be shorter. I also tried to compress repetitions in the data using variable interpolation (see the other answer), but with the newest version that doesn’t gain any characters anymore.

# Answer
> 3 votes
# Perl, ~~224~~ 223 characters

```
use MIME::Base64;$_=decode_base64 wsCnBqDR2GcyYCYwRwYgBwZA0djCwNEUuxDR2MLApwag0djCwNEUN1sQJjBxFTF7UMLA0RS7ENHY;s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg

```

### Somewhat more readable

```
use MIME::Base64;

# raw binary data in base-64-encoded form as a bareword
$_=decode_base64
    wsCnBqDR2GcyYCYwRwYgBwZA0djCwNEUuxDR2MLApwag0djCwNEUN1sQJjBxFTF7UMLA0RS7ENHY;

# Decode left half of the snowflake (without newlines)
s^.^$x=ord$&;$"x($x>>3).qw(\ /_ __/ \/ __ _\ / __/\__)[$x&7]^eg;

# Reconstruct the right half and the newlines
s^.{27}^$_=reverse$&;y~/\\~\\/~;print$&.$_.$/^eg

```

### How it works

For an explanation of how it works, see the other answer in which I post the same in binary. I am really sorry that I am not actually *generating* the Koch snowflake, just compressing it...

### Previous versions

* **(359)** Encoded the entire snowflake instead of just the left half. Spaces were included in the bit encoding; no run-length yet. Used several interpolated variables plus a `@_` array which was accessed using `s/\d/$_[$&]/eg`. Newlines were encoded as `!`.
* **(289)** First version that encoded only the left half of the snowflake.
* **(267)** First version that used run-length encoding for the spaces.
* **(266)** Change `' '` to `$"`.
* **(224)** Radically different compression, encoded as base-64. (Now equivalent to the binary version.)
* **(223)** Realised that I can put the print inside the last subst and thus save a semicolon.

# Answer
> 3 votes
## Python, 284

```
for s in "eJyVkNENACEIQ/+dgg1YiIT9tzgENRyWXM4/pH1tIMJPlUezIiGwMoNgE5SzQvzRBq52Ebce6cr0aefbt7NjHeNEzC9OAalADh0V3gK35QWPeiXIFHKH8seFfh1zlQB6bjxXIeB9ACWRVwo=".decode('base64').decode('zlib').split('\n'):print s+'  '*(27-len(s))+'\\'.join([c.replace('\\','/')for c in s[::-1].split('/')])

```

With a bit more whitespace:

```
for s in "eJyVkNENACEIQ/+dgg1YiIT9tzgENRyWXM4/pH1tIMJPlUezIiGwMoNgE5SzQvzRBq52Ebce6cr0aefbt7NjHeNEzC9OAalADh0V3gK35QWPeiXIFHKH8seFfh1zlQB6bjxXIeB9ACWRVwo=".decode('base64').decode('zlib').split('\n'):
  print s + '  '*(27-len(s)) + '\\'.join([c.replace('\\','/') for c in s[::-1].split('/')])

```

The left side is compressed; the right side is reproduced from the left side.

---
Tags: code-golf, ascii-art, kolmogorov-complexity, fractal
---


# Question
Title: What is a good way to deal with tasks that require arrays using Haskell?
Often a task requires real arrays. Take for instance the task to implement Befunge or \>\<\>. I tried to use the `Array` module for this, but it's really cumbersome, as it feels like I'm coding much too verbose. Can anybody help me how to solve such code-golf tasks less verbose and more functional?

# Answer
First of all, I recommend looking at Data.Vector, a nicer alternative to Data.Array in some cases.

`Array` and `Vector` are ideal for some memoization cases, as demonstrated in my answer to "Finding maximum paths". However, some problems simply aren't easy to express in a functional style. For example, Problem 28 in Project Euler calls for summing the numbers on the diagonals of a spiral. Sure, it should be pretty easy to find a formula for these numbers, but constructing the spiral is more challenging.

Data.Array.ST provides a mutable array type. However, the type situation is a mess: it uses a class MArray to overload every single one of its methods except for runSTArray. So, unless you plan on returning an immutable array from a mutable array action, you'll have to add one or more type signatures:

```
import Control.Monad.ST
import Data.Array.ST

foo :: Int -> [Int]
foo n = runST $ do
    a <- newArray (1,n) 123 :: ST s (STArray s Int Int) -- this type signature is required
    sequence [readArray a i | i <- [1..n]]

main = print $ foo 5

```

Nevertheless, my solution to Euler 28 turned out pretty nicely, and did not require that type signature because I used `runSTArray`.

## Using Data.Map as a "mutable array"

If you're looking to implement a mutable array algorithm, another option is to use Data.Map . When you use an array, you kind of wish you had a function like this, which changes a single element of an array:

```
writeArray :: Ix i => i -> e -> Array i e -> Array i e

```

Unfortunately, this would require copying the entire array, unless the implementation used a copy-on-write strategy to avoid it when possible.

The good news is, `Data.Map` has a function like this, insert:

```
insert :: Ord k => k -> a -> Map k a -> Map k a

```

Because `Map` is implemented internally as a balanced binary tree, `insert` only takes O(log n) time and space, and preserves the original copy. Hence, `Map` not only provides a somewhat-efficient "mutable array" that is compatible with the functional programming model, but it even lets you "go back in time" if you so please.

Here is a solution to Euler 28 using Data.Map :

```
{-# LANGUAGE BangPatterns #-}

import Data.Map hiding (map)
import Data.List (intercalate, foldl')

data Spiral = Spiral Int (Map (Int,Int) Int)

build :: Int -> [(Int,Int)] -> Map (Int,Int) Int
build size = snd . foldl' move ((start,start,1), empty) where
    start = (size-1) `div` 2
    move ((!x,!y,!n), !m) (dx,dy) = ((x+dx,y+dy,n+1), insert (x,y) n m)

spiral :: Int -> Spiral
spiral size
    | size < 1  = error "spiral: size < 1"
    | otherwise = Spiral size (build size moves) where
        right   = (1,0)
        down    = (0,1)
        left    = (-1,0)
        up      = (0,-1)
        over n  = replicate n up ++ replicate (n+1) right
        under n = replicate n down ++ replicate (n+1) left
        moves   = concat $ take size $ zipWith ($) (cycle [over, under]) [0..]

spiralSize :: Spiral -> Int
spiralSize (Spiral s m) = s

printSpiral :: Spiral -> IO ()
printSpiral (Spiral s m) = do
    let items = [[m ! (i,j) | j <- [0..s-1]] | i <- [0..s-1]]
    mapM_ (putStrLn . intercalate "\t" . map show) items

sumDiagonals :: Spiral -> Int
sumDiagonals (Spiral s m) =
    let total = sum [m ! (i,i) + m ! (s-i-1, i) | i <- [0..s-1]]
     in total-1 -- subtract 1 to undo counting the middle twice

main = print $ sumDiagonals $ spiral 1001

```

The bang patterns prevent a stack overflow caused by the accumulator items (cursor, number, and Map) not being used until the very end. For most code golfs, input cases should not be big enough to need this provision.
> 5 votes

# Answer
The glib answer is: Don't use arrays. The not-so-glib answer is: Try to rethink your problem so that it doesn't need arrays.

Often, a problem with some thought can be done without any array like structure at all. For example, here's my answer to Euler 28:

```
-- | What is the sum of both diagonals in a 1001 by 1001 spiral?
euler28 = spiralDiagonalSum 1001

spiralDiagonalSum n
    | n < 0 || even n = error "spiralDiagonalSum needs a positive, odd number"
    | otherwise = sum $ scanl (+) 1 $ concatMap (replicate 4) [2,4..n]

```

What gets expressed in the code here is the pattern of the sequence of numbers as they grow around the rectangular spiral. There was no need to actually represent the matrix of numbers itself.

The key to thinking beyond arrays is to think about what the problem at hand actually means, not how you might represent it as bytes in RAM. This just comes with practice (perhaps a reason I code-golf so much!)

Another example is how I solved the finding maximal paths code-golf. There, the method of passing the partial solutions as a wave through the matrix, row by row, is expressed directly by the fold operation. Remember: On most CPUs, you can't deal with the array as a whole at once: The program is going to have to operate through it over time. It may not need the whole array at once at any time.

Of course, some problems are stated in such a way that they are inherently array based. Languages like \>\<\>, Befunge, or Brainfuck have arrays at their heart. However, even there, arrays can often be dispensed with. For example, see my solution to interpreting Brainfuck, the real core of its semantics is a zipper. To start thinking this way, focus on the patterns of access, and the structure closer to the meaning of problem. Often this needn't be forced into a mutable array.

When all else fails, and you do need to use an array - @Joey's tips are a good start.
> 9 votes

---
Tags: code-golf, tips, haskell
---


# Question
Title: Program that runs when rows and columns are transposed
I posted this to The Daily WTF coder challenge forum a few years ago but only got one response. I figure CodeGolf stack exchange might generate more interest!

**Description**

Write a program that runs when the rows and columns of the source code are transposed.

In other words, imagine each character on each line is a cell in a matrix (pad out shorter lines as necessary to make the matrix rectangular). Write a functioning program that still functions even if its "matrix" is transposed.

*This is just a creative puzzle, not a golf.*

**Details**

1. The program must execute without error and do something interesting\*
2. The transpose of the program must execute without error and do something interesting, although not necessarily the same thing as the original.
3. Any language.
4. No shebang required.
5. Single row/single column entries disallowed.

\*Interesting is the subjective opinion of the CodeGolf community.

**Deadline** April 15 2011

**Trivial Example**

Here's a really stupid example, but it illustrates the rules pretty well. Of course, any "symmetric" program will meet this challenge, but I encourage you to try non-symmetric programs.

```
# #####################
 print "hello,world\n";
#r
#i
#n
#t
#
#"
#h
#e
#l
#l
#o
#,
#w
#o
#r
#l
#d
#\
#n
#"
#;

```

**Transposer Reference Implementation**

Here's a perl snippet that does the type of transposing that I am talking about. *This is not the objective of the puzzle, it is just a helper tool.*

```
#!/usr/bin/perl
my @matrix;
open('SOURCE', $ARGV[0]);
my $matrixwidth = -1;
my $matrixheight = 0;
foreach (<SOURCE>) {
  chomp;
  if ($matrixwidth < length $_) {$matrixwidth = length $_}
  my @row = split(//, $_);
  push @matrix, \@row;
  $matrixheight++;
}
foreach my $x (0 .. ($matrixwidth-1)) {
  foreach my $y (0 .. ($matrixheight-1)) {
    print(defined $matrix[$y]->[$x] ? $matrix[$y]->[$x] : ' ');
  }
  print "\n";
}

```

# Answer
## c

Not-quite-trivial, not-quite-symmetric solution that prints it's command line arguments, one per line. As shown it prints them in order, as transposed in reverse order.

```
/*******ipcc;m(acaw-{aa)
********nuohiairhrh-prr;
********ttnaningagiaugg}
******** ssrtntcrvlrtvc}
******** (t*   ,*)egs[]
********   s    *{(c(
********   )       )
*******/
int
puts(
const
char*s)
;int
main
(int
argc,
char**
argv){
int i;
for(i=1;
i<argc;
i++)
{puts(
argv[i]
);}}

```
> 11 votes

# Answer
Here's one I came up with when I originally wrote the challenge a few years back. It's a perl script that can transpose other scripts. You can run it on itself, save the output as a new script, then run that new script on itself to get the original.

```
#######       p           $f f   ]'
#      ofm    u        $  ho o   -
#      poy    s        w  +r r  p>'
#      er ####h########=##+ #   r[}
    open   'M' , $ARGV[ 0]  ; # i$p
  for(;   <M>  ; ){         #   nxr
      #((@             $  }( (  t]i
      #';r             #   $ $   ?n
      #M<=    @        r   x y   $t
      #'M     m        +   = =   m
      # >     ,        1   0 0   ["
my @r=   $_ =~ /./g;#  >   ; ;   $\
      #  _ /  \                # yn
push @m,     \@r;              # ]"
      # ;=    r            $ $   -}
      #  ~    ;        $   x y   >
$w=($#r   + 1>        $w)      # [
?$#r+1:     $w ;$h++}# ?   < <   $
for (     $x=0 ;$x<$w;         # x
          $x++ ){              # ]
for (     $y=0 ;$y<$h;
          $y++ ){           #$
  print               #$   $ h  d:
defined                #   w ;  e
      #$)/    #        r   ; $  f
      #A{.             +   $ y  i
      #R#/             1   x +  n
      #G g             :   + +  e
      #V ;                 + )  d
     $m[  $y]->[$x]
      #0 #                 ) {  $
 ?$m[$y]->[$x]:' '}          #  m
      #)               $   {    [
      #;               w        $
  print "\n"} #        ;        y

```
> 16 votes

---
Tags: popularity-contest
---


title: Squares in Movement Range

text:
# Question
Title: Squares in Movement Range
There are two inputs, the first input is a map in 2D array, where 2 represents an obstacle and 0 represents a regular ground, and 1 represents the player's location (implies that the player is standing on ground), the second input is the player's movement range.

A player can move on the map (horizontally, vertically, but not diagonally) within the movement range (0 to movement range inclusive), and the player can travel through an obstacle, but only one at a time. At last, a player cannot stand on an obstacle.

The program outputs an 2D array of booleans, showing all possible squares the player can move to.

Here are some examples:

Input

```
________
_____#__
___+__#_
#__#____
________, range=2
(_ = 0, + = 1, # = 2)

```

Output

```
___+____
__+++___
_+++++__
__+_+___
___+____ (+ = true, _ = false)

```

Input

```
__________
__________
______#___
__#_+##___
__________
____#_____
__________, range=4

```

Output

```
___+++____
__+++++___
_+++++_+__
++_++_____
_+++++++__
__++_++___
___+++____

```

There will be two winners: shortest brute-force and shortest efficient algorithm (the map and the movement range can get arbitrarily large)

# Answer
# Python, 284 characters

```
def M(A,R):
 X,Y=range(len(A[0])),range(len(A))
 G,P,H=[set(x+1j*y for x in X for y in Y if A[y][x]>=z) for z in(0,1,2)]
 P-=H
 for i in' '*R:P|=G&reduce(lambda x,y:x|y,[set(p+d for p in P)-(H&set(p+d for p in H))for d in(1,1j,-1,-1j)])
 return[[x+1j*y in P-H for x in X]for y in Y]

def display(A):print'\n'.join(''.join('_+'[c]for c in r)for r in A)

A=[[0,0,0,0,0,0,0,0],
   [0,0,0,0,0,2,0,0],
   [0,0,0,1,0,0,2,0],
   [2,0,0,2,0,0,0,0],
   [0,0,0,0,0,0,0,0]]
display(M(A,2))

A=[[0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,0,0,2,0,0,0],
   [0,0,2,0,1,2,2,0,0,0],
   [0,0,0,0,0,0,0,0,0,0],
   [0,0,0,0,2,0,0,0,0,0],
   [0,0,0,0,0,0,0,0,0,0]]
display(M(A,4))

```

The main `M` routine takes the 2D array containing the map and the range, and returns the 2D array of booleans.

`G` is the set of all indexes of (in-bounds) squares, encoded as complex numbers. `H` is the same but for the obstacles, and `P` is the same for the player. The main loop updates `P` by moving `P` in each of the 4 cardinal directions, filtered by the obstacles and the bounds of the array.
> 1 votes

---
Tags: code-golf, geometry
---


title: Finding maximum paths

text:
# Question
Title: Finding maximum paths
Given a square of positive, natural numbers write a program find a horizontal and a vertical path with the sum of numbers along them being maximal. A *horizontal* path goes from the first column to the last and has to increase its column position by one in each step. A *vertical* path goes from the first row to the last and has to increase its row position by one in each step. Furthermore the row position in a *horizontal* path may stay the same or change by one in either direction, likewise for vertical paths.

To illustrate, the following could be a valid path:

The following path would be invalid, since it steps backwards (and remains on the same row in some places):

The following path would be equally invalid, since it changes the row position by more than one in a single step:

*Note: The solution should run in an acceptable amount of time.*

**Input**

*n* lines of input with *n* space-separated positive integers each are given on standard input. 2 ≤ *n* ≤ 40. Every line is terminated by a line break. The numbers are small enough that the maximum sum fits in a 32-bit signed integer.

**Output**

The maximum sums of the horizontal and vertical paths (in that order) separated by a single space.

**Sample input 1**

```
1 2
1 2

```

**Sample output 1**

```
3 4

```

**Sample input 2**

```
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 4 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 4 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

```

**Sample output 2**

```
37 35

```

**Sample input 3**

```
683 671 420 311 800 936
815 816 123 142 19 831
715 588 622 491 95 166
885 126 262 900 393 898
701 618 956 865 199 537
226 116 313 822 661 214

```

**Sample output 3**

```
4650 4799

```

---

For your convenience we have prepared a few test cases in bash (thanks to Ventero) and PowerShell which you can run your program through. Invocation is: `<test> <command line>`, so something like `./test python paths.py` or `./test.ps1 paths.exe`. Have fun :-)

# Answer
## GolfScript - 49 Nabb enhanced characters

51 characters
50 strictly and utterly necessary characters + 3 slackers that only did the job of 1
56 mostly redundant characters

```
n%{~]}%.zip{{0@+\{\.1>\3<$-1=@+}%\;}*$-1=\}2*' '@

```

51 solution:

```
n%{~]}%.zip{(\{0@+\{\.1>\3<$-1=@+}%\}%;$-1=\}2*' '@

```

53 solution:

```
n/{~]}%);.zip{(\{0@+\{\.1>\3<$-1=@+}%\}%;$-1=\}2*' '@
             a8_b9___c10___11______12 13      14_

```

The method works on two lines at a time, one containing the maximum sums reached at each point, and one containing the next line.

a/14: Repeat twice, once for each result.
8: Take the first line from the input and switch it behind the input array, this in now the first set of maximum sums.
b/13: Iterate over each remaining line in the array.
9: Put 0 at the beginning of the maximum sums.
c/12: Iterate over each element of the line.
10: Make a copy of the maximum sums with the first element removed.
11: Take the first 3 elements of the maximum sums, sort them and add the largest to the current element of the line.

56 solution:

```
n/{~]}%);.zip{1,99*\{{\.1>\3<$-1=@+}%0\+\}%;$-1=\}2*' '@
1________2___ 3____ 4______________________5_____ 6_7___

```

1: From input to array of arrays in 9 characters, actually it could have been done with just 1, but I broke that key so this will have to do.
2: 4 characters just to make a transposed copy.
3: Array of 99 0s in 5 characters, it could probably be done in a way smarter fashion, but I smoke too much weed to figure how.
4: Overly complicated double loop that iterate over every single element of the input and does some fuzzy logic or something like that to produce the result. Nabb will probably make something equivalent in around 3½ characters.
5: By now the result is there, inside an array that is, this silly piece of code is just there to get it out (and junk a piece of leftovers (and switch the result into place)).
6: This is a command so simple that its character count would probably be negative in an optimal solution. 7: At this point the program is really done, but due to sloppiness in the preceding code the output is in the wrong order and lacks a space, so here goes a few more bits down the drain.
> 6 votes

# Answer
# Haskell: 314 necessary characters

```
import Data.Vector(fromList,generate,(!))
import List
l=fromList
x=maximum
g=generate
p a=show$x[m!i!0|i<-[0..h-1]]where{
w=length$head a;h=length$a;n=l$map l a;
m=g h$ \i->g w$ \j->n!i!j+x[k#(j+1)|k<-[i-1..i+1]];
i#j|i<0||i>=h||j>=w=0|1>0=m!i!j;}
q a=p a++' ':(p.transpose)a
main=interact$q.map(map read.words).lines

```

Note: this requires the module Data.Vector. I'm not sure if it's included in the Haskell platform or not.

Ungolfed version:

```
import Data.Vector(fromList,generate,(!))
import Data.List

-- horizontal; we use transpose for the vertical case
max_path :: [[Integer]] -> Integer
max_path numbers = maximum [m ! i ! 0 | i <- [0..h-1]] where
    w = length (head numbers)
    h = length numbers
    n = fromList $ map fromList numbers
    m = generate h $ \i -> generate w $ \j ->
        n ! i ! j + maximum [f i' (j+1) | i' <- [i-1..i+1]]
    f i j | i < 0 || i >= h || j >= w = 0
    f i j = m ! i ! j

max_paths :: [[Integer]] -> String
max_paths numbers = (show . max_path) numbers ++ " " ++
                    (show . max_path . transpose) numbers

main = interact $ max_paths . map (map read . words) . lines

```

This solution uses laziness, in tandem with Data.Vector, for memoization. For every point, the solution for the maximum path from it to the end is computed, then stored in the cell of Vector `m` and reused when needed.
> 3 votes

# Answer
# J, 91 95

```
a=:".;._2(1!:1)3
c=:4 :'>./x+"1|:y,.(1|.!.0 y),._1|.!.0 y'
p=:[:>./c/
(":(p|:a),p a)1!:2(4)

```

I decline to do IO, lowering my score dramatically. Passes all tests in the test harness (though it *only* works if the input ends with a line ending, as in the test harness).

I removed the handling for Windows line endings, since Chris suggested that it wasn't necessary. The multi-platform version would have `a=:".;._2 toJ(1!:1)3` as the first line.

Explanation:

* `f` gives the solution pair by calling p normally and with input transposed (`|:`).
* `p` takes the maximum (`>./`) of the row-totals from applying `c` between each row (`c/`)
* `c` takes two rows (x and y). It adds x to each of y, y shifted up 1 cell (`1|.!.0 y`), and y shifted down 1 cell (`_1|.!.0 y`). Then it takes the maximums of the three alternatives for each row. (`>./`). The rest is rank \[sic\] - I'm not sure if I'm doing it right.
> 3 votes

# Answer
# Ruby 1.9, 155 characters

```
f=->t{(1...l=t.size).map{|a|l.times{|b|t[a][b]+=t[a-1][(b>0?b-1:0)..b+1].max}};t[-1].max};q=[*$<].map{|a|a.split.map &:to_i};puts [f[q.transpose],f[q]]*" ""

```

Straightforward solution that passes all testcases.
> 2 votes

# Answer
# Haskell, 154 characters

```
import List
z=zipWith
f=show.maximum.foldl1(\a->z(+)$z max(tail a++[0])$z max(0:a)a)
q a=f(transpose a)++' ':f a
main=interact$q.map(map read.words).lines

```

---

* Edit: (155 -\> 154) inlined the function folded over
> 2 votes

# Answer
# Python, 149

```
import sys
def f(g,t=[]):
 for r in g:t=[int(e)+max(t[i-1:i+2]+[0])for i,e in enumerate(r)]
 print max(t),
g=map(str.split,sys.stdin)
f(zip(*g)),f(g)

```

If I were to calculate only a vertical or horizontal shortest path,
it could be done in-place instead, saving about a third of the bytes.
> 2 votes

# Answer
## J, 109+10= 119 chars

```
y=:0".(1!:1)3
N=:%:#y
y=:y$~N,N
r=:(((1&{)(+(3>./\0,0,~]))(0&{)),2&}.)^:(<:N)
(":([:>./"1([:r|:),r)y)(1!:2)4

```

Run with `tr`:

```
cat << EOF | tr \\n ' ' | ./maxpath.ijs

```

As usual in J, most of the code is for input/output. The "actual" code is 65 characters:

```
r=:(((1&{)(+(3>./\0,0,~]))(0&{)),2&}.)^:(<:#y)
([:>./"1([:r|:),r)y

```

*Passes all test cases*
> 1 votes

# Answer
# Python, 204 characters

```
import sys
I=sys.stdin.read()
n=I.count('\n')
A=map(int,I.split())
R=range(n)
X=lambda h,a:[a[i]+max(([0]+h)[i:i+3])for i in R]
h=v=[0]*n
for i in R:h=X(h,A[i*n:i*n+n]);v=X(v,A[i::n])
print max(v),max(h)

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Help Mr Jones to enjoy his bicycle round-trip
Mr Jones wants to do a round-trip on his bicycle. He wants to visit several cities in arbitrary order, but his route must not cross it self, since he hates to be at the same place twice in his holidays. As he really loves cycling, the length of his route is completely irrelevant, but he dislikes to drive around the landscape without a target. The route he likes is from on city in a straight line to another, without any detour.

As Mr Jones is a passionated code golfer, he wants you to find a program, that plans a round trip for him, given a set of cities. The input has the form `A (B|C)`. `A` is a city's name, `B` and `C` are its coordinates. You may assume, that the coordinate are positive and less than 1000. The data sets for the cities are line-separated. Here is an example, of how an example input might look like:

```
SomeTown (1|10)
ACity (3|4)
Wherever (7|7)
Home (5|1)

```

Mr Jones isn't pedantic, he just wants to have a useful program. Thus, you may decide by your self how the output is looking like, as long as it mets these criteria:

* The output is a map of the cities, with the route drawn between them. If anything is correct, the route shouldn't overlap itself and should end where it started
* The coordinates are like in usual programming: (1|1) is in the NW corner. Add kind of a ruler to the maps border, to ease reading it
* The cities names have to be written down on the map, but feel free to use abbreviations which is explained somewhere else on the map
* The map can be both ASCII-art or an image
* Keep the output readable

An output might look like this:

```
  1234567
 1    D
 2   * *
 3  *  *
 4  B   *
 5  *   *
 6  *   *
 7 *    C
 8*   **
 9*  *
10A**

A: SomeTown
B: ACity
C: Wherever
D: Home

```

The program with the smallest char count wins. I don't count parameters to the compiler / interpreter, if they are needed for compiling, but please don't abuse this rule. Usual code golf rules apply.

Here is another testcase. You output doesn't have to match mine, nor do you have to choose the same path as me. The output is drawn by hand and shows a possible output. Input:

```
home (5|7)
supermarket (13|12)
park (15|5)
new plaza (9|16)
friend's house (20|11)
old castle (14|21)
riverside (1|20)
beach (10|1)
cinema (21|18)
forest (23|7)
little island (21|1)
museum of code-golf (6|25)
airport (18|25)
tea-shop (24|14)
restaurant (24|22)
great bridge (3|12)
SO building (25|9)

```

And this is an example output:

```
           1111111111222222
  1234567890123456789012345
 1         H*        *K
 2        *  *      *  *
 3        *   *    *   *
 4       *     * **    *
 5      *       C      *
 6     *               *
 7    A                 J
 8   *                   *
 9   *                    Q
10   *                    *
11   *            ***E    *
12  P         B***   *   *
13  *        *       *   *
14  *       *        *   N
15 *       *          *  *
16 *      D           *  *
17 *       *          *  *
18*         *         I  *
19*          *        *  *
20G           *      *   *
21 *           F     *   *
22  *         **    *    O
23   *      **     *   **
24    *   **       *  *
25     L**         M**

A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building

```

*I am not an English native speaker. Feel free to correct my language and grammar, if necessary.*

# Answer
# J, 357 288

```
m=:>:>./c=:>1{"1 p=:([:<`([:<1-~[:".;._1'|',}:);._1'(',]);._2(1!:1)3
'n c'=:|:o=:p/:12 o.j./"1 c-"1(+/%#)c
C=:<"1 c
L=:u:65+i.#o
g=:<"1;c([:<@|:0.5<.@+[+>@])"1(-~/"2(<@:*]%~i.@>:@])"0([:>./|@-/)"2)>C,"0(1|.C)
echo(u:48+10|i.>:0{m),|:(u:48+10|>:i.1{m),L C}'*'g}m$' '
echo' ',L,.':',.' ',.n

```

This is just a quick squeezing of the original (see below). A lot of golfing is probably still possible to eliminate lots of useless rank manipulation and boxing.

Only caveat: Ruler is just the last digit unlike example output.

**Edit:** Bug fix - Cities had wrong labels (and were not in alpha order on map).

**Edit 2:** Removed all sorts of horseplay and tomfoolery for a savings of 69 characters.

Output (Verbatim, from test script):

```
First example:
01234567
1    B
2   **
3   * *
4  A  *
5  *  *
6 *    *
7 *    C
8 *  **
9* **
0D*

A: ACity
B: Home
C: Wherever
D: SomeTown

Second example:
012345678901234567890123456789012
1         D          F
2        * *       ***
3       *   **    *  *
4       *     * **   *
5      *       E     *
6     *              *
7    C              *          *I
8     **            *      *****
9       *           *   *H*   *
0        **         * **     *
1          **       G*     **
2  A*********B            *
3   **                   *
4     *                 J
5      **              *
6        Q             *
7      **             *
8    **              K
9  **                 *
0P*                    *
1 *           N        *
2  *        ** *        L
3   *     **    *     **
4    *  **       *  **
5     O*          M*

A: great bridge
B: supermarket
C: home
D: beach
E: park
F: little island
G: friend's house
H: SO building
I: forest
J: tea-shop
K: cinema
L: restaurant
M: airport
N: old castle
O: museum of code-golf
P: riverside
Q: new plaza
   End Second

```

Ungolfed original:

```
coords =: > 1 {" 1 parsed =: ([:<`([:<[:".;._1'|',}:);._1'(',]);._2 (1!:1)3

center =: (+/%#) coords
max =: >:>./ coords
angles =:  12 o. j./"1 coords -"1 center
ordered =: parsed /: angles
paths =: >(],"0(1)|.]) 1 {" 1 ordered

path_grid_lengths =: ([:>./|@-/)"2 paths
path_grid_interval =: ([:<]%~i.@>:@|)"0 path_grid_lengths
path_grid_distances =: -~/"2 paths
path_grid_steps =: path_grid_distances ([:<[*>@])"0 path_grid_interval

path_grid_points_sortof =: (> 1{"1 ordered) ([:<0.5<.@+[+>@])"0 path_grid_steps
path_grid_points =: <"1;([:<>@[,.>@])/"1 path_grid_points_sortof

graph_body =: }."1}. (u:65+i.#ordered) (1{"1 ordered) } '*' path_grid_points} max $ ' '

axis_top =: |:(":"0)10|}.i. 1{max
axis_side =: (":"0)10|i. 0{max

echo |:(axis_side) ,"1 axis_top, graph_body
echo ''
echo (u:65+i.#parsed),.':',.' ',.(> 0{"1 ordered)

```
> 9 votes

# Answer
## Haskell, 633 characters

```
import List
c n=n>>=(++" ").show.(*3)
(x&y)l="<text x='"++c[x]++"' y='"++c[y]++"'>"++l++"</text>"
f%p=[a-1,b+2,(a+b)/2]where n=map(f.fst)p;a=minimum n;b=maximum n
s p=concat["<svg xmlns='http://www.w3.org/2000/svg' viewBox='",c[i,m-1,j,n],"'><polygon fill='none' stroke='#c8c' points='",c$snd=<<(sort$map a p),"'/><g font-size='1' fill='#bbb'>",(\x->(x&m$show x)++(i&x$show x))=<<[floor(i`min`m)..ceiling(j`max`n)],"</g><g font-size='2'>",snd=<<p,"</g></svg>"]where a((x,y),_)=(atan2(x-q)(y-r),[x,y]);[i,j,q,m,n,r]=fst%p++snd%p
w(l,s)=((x,y),(x&y)l)where(x,r)=v s;(y,_)=v r
v=head.reads.tail
main=interact$s.map(w.break(=='(')).lines

```

Rather longish for code-golf, but produces a lovely SVG map:

Or, if your browser can't handle SVG, a PNG of that image:

---

* Edit: (648 -\> 633) in-line coordinate drawing, and possibly draw more than needed, letting them be clipped by the `viewBox`; also a few golf-tricks here and there.
> 21 votes

# Answer
## Python, 516 476 bytes

```
#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
for L in sys.stdin.readlines():
 i,j,K=L.find('('),L.find('|'),'%c'%k
 n,h,v=L[:i-1],int(L[i+1:j]),int(L[j+1:-2])
 H=max(H,h);V=max(V,v);T+=[(K,h,v)];k+=1;print K+':',n
V=V+1&~1
for s in zip(*['%3d'%(i+1)for i in range(H)]):print'   '+''.join(s)
C=H*V*[u'─']
C[0::H]=u'│'*V
C[1::H]=V/2*u'└┌'
C[H-1::H]=V/2*u'┐┘'
C[0:2]=u'┌─'
C[-H:-H+2]=u'└─'
for K,h,v in T:C[v*H-H+h-1]=K
for i in range(V):print'%3d'%(i+1)+''.join(C[i*H:i*H+H])

```

(Note: I didn't include the first two lines in the byte count, I consider them "interpreter parameters". But I did charge myself for the utf-8 length of the program in bytes.)

On your second example I produce:

```
A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building

            11111111112222222222333
   12345678901234567890123456789012
  1┌────────H──────────K──────────┐
  2│┌─────────────────────────────┘
  3│└─────────────────────────────┐
  4│┌─────────────────────────────┘
  5│└────────────C────────────────┐
  6│┌─────────────────────────────┘
  7│└──A──────────────────────────J
  8│┌─────────────────────────────┘
  9│└──────────────────────Q──────┐
 10│┌─────────────────────────────┘
 11│└─────────────────E───────────┐
 12│┌P─────────B──────────────────┘
 13│└─────────────────────────────┐
 14│┌─────────────────────N───────┘
 15│└─────────────────────────────┐
 16│┌──────D──────────────────────┘
 17│└─────────────────────────────┐
 18│┌──────────────────I──────────┘
 19│└─────────────────────────────┐
 20G┌─────────────────────────────┘
 21│└───────────F─────────────────┐
 22│┌─────────────────────O───────┘
 23│└─────────────────────────────┐
 24│┌─────────────────────────────┘
 25│└───L───────────M─────────────┐
 26└──────────────────────────────┘

```

Yay, Unicode glyphs!
> 12 votes

# Answer
## Python, 1074 bytes

Ok, spent way too many bytes (and time) getting reasonable paths to work.

```
#!/usr/bin/python
#coding=utf-8
import sys
H=V=0
T=[]
k=65
R=1000
for L in sys.stdin.readlines():
 i,j,K=L.find('('),L.find('|'),'%c'%k
 n,h,v=L[:i-1],int(L[i+1:j]),int(L[j+1:-2])
 H=max(H,h);V=max(V,v);T+=[(v*R-R+h-1,K)];k+=1;print K+':',n
for s in zip(*['%3d'%(i+1)for i in range(H+1)]):print'   '+''.join(s)
T.sort()
U=reduce(lambda a,x:a[:-1]+[(a[-1][0],x)]if x/R==a[-1][0]/R else a+[(x,x)],[[(T[0][0],T[0][0])]]+map(lambda x:x[0],T))
C=R*V*[' ']
r=0
for x,y in U:C[x:y]=(y-x)*u'─'
for (a,b),(c,d)in zip(U,U[1:]):
 if r:
  if d%R>b%R:x=b/R*R+d%R;C[b:x]=(x-b)*u'─';C[x:d:R]=(d-x)/R*u'│';C[x]=u'┐'
  else:x=d/R*R+b%R;C[d:x]=(x-d)*u'─';C[b:x:R]=(x-b)/R*u'│';C[x]=u'┘'
 else:
  if c%R<a%R:x=a/R*R+c%R;C[x:a]=(a-x)*u'─';C[x:c:R]=(c-x)/R*u'│';C[x]=u'┌'
  else:x=c/R*R+a%R;C[a:x:R]=(x-a)/R*u'│';C[x:c]=(c-x)*u'─';C[x]=u'└'
 r^=1
p=U[0][1];C[p:H]=(H-p)*u'─'
if r:p=U[-1][1];C[p:R*V]=(R*V-p)*u'─'
else:V+=1;C+=[' ']*R;p=U[-1][0]+R;C[p:R*V]=(R*V-p)*u'─';C[p]=u'└'
C[H::R]=u'┐'+u'│'*(V-2)+u'┘'
for p,K in T:C[p]=K
for i in range(V):print'%3d'%(i+1)+''.join(C[i*R:i*R+H+1])

```

Makes nice paths, though:

```
A: SomeTown
B: ACity
C: Wherever
D: Home

   12345678
  1  ┌─D──┐
  2  │    │
  3  │    │
  4  B───┐│
  5      ││
  6      ││
  7┌─────C│
  8│      │
  9│      │
 10A──────┘

```

and

```
A: home
B: supermarket
C: park
D: new plaza
E: friend's house
F: old castle
G: riverside
H: beach
I: cinema
J: forest
K: little island
L: museum of code-golf
M: airport
N: tea-shop
O: restaurant
P: great bridge
Q: SO building

            111111111122222222223333
   123456789012345678901234567890123
  1         H──────────K───────────┐
  2         │                      │
  3         │                      │
  4         │                      │
  5         └────C────────────────┐│
  6                               ││
  7    A──────────────────────────J│
  8    │                           │
  9    └───────────────────Q       │
 10                        │       │
 11  ┌────────────────E────┘       │
 12  P─────────B──────────┐        │
 13                       │        │
 14        ┌──────────────N        │
 15        │                       │
 16        D───────────┐           │
 17                    │           │
 18┌───────────────────I           │
 19│                               │
 20G────────────┐                  │
 21             F                  │
 22             └─────────O        │
 23                       │        │
 24                       │        │
 25     L───────────M─────┘        │
 26     └──────────────────────────┘

```
> 6 votes

---
Tags: code-golf, ascii-art, graph-theory, graphical-output
---