# Question
Title: X greater than 3 with at least 2 difference between X and Y
I am trying to golf down some C++. Is it possible to make this condition shorter?

`X > 3 & X - Y > 1`

(Apart from removing whitespace, of course.)

So, `X` is at least `4` but `X >= Y + 2`.

`X` and `Y` are integers in the \[0,5\] interval.

I have tried to find some bitwise formula but failed.

# Answer
After brute forcing every useful combination of symbols under 9 characters, I've found there to be no smaller solution than `x>3&x-y>1`.

For fun here's some funky 9 character solutions the brute forcer found:

```
-x<~y>4>x
~y+x>2>>y
x*x-y*y>9
~y>x/~3*x
-3>>y>y-x
~y+x<<y>2

```

---

Brute forcing was done in Python, building top-down syntax trees where no child may have an operator with precedence lower than its parent according to C's rules. To cut down on possibilities I only allowed single digit literals, and no binary operator may have two constant children. I could not possibly think of any solution that would have a two digit literal, or one that builds a constant using a binary operator. Then each expression was evaluated for \[0, 5\] and if it matches it gets printed.
> 11 votes

# Answer
In response to the (awesome) golfs by `orlp`:

# Correctness must come first

* Most of these break down for some integer types. This includes the version from the OP
* Interestingly they *do* work for `int16_t` \- so there is the assumption. Probably the bit shifts would need to +16 for 32 bit ints (that's pretty much everywhere these days). This makes them a character bigger...

The only "correct" way to write it, IMO is `(x>3) && (x > y+1)`, which may be golfed down to `x>3&x>y+1` (9 characters).

*(You really need to take the possibility of (larger) unsigned types into consideration, especially since unsigned-ness is "contagious" in C++ expressions. I suppose "fixing" that with the appropriate `static_cast<>`s would kinda defeat the purpose...)*

**UPDATE**

With the following tests I've been able to figure out which expressions *actually* work reliably:

**`Live On Coliru`**

```
#define REPORT(caption, expr) do {\
    do_report(caption, [](T x, T y) -> bool { return (expr); }, #expr); } while (false)

template <typename T> struct driver {
    static void run() {
        std::cout << "\n" << __PRETTY_FUNCTION__ << "\n";

        // the only two correct implementations:
        REPORT("MASTER"  , (x>3) && (x>y+1));
        REPORT("GOLF"    , x>3&x>y+1);
        REPORT("lookup"  , "000000000000000000000000111000111100"[x*6+y]-'0');

        // failing sometimes:
        REPORT("question", (x>3)&(x-y>1));
        REPORT("orlp0"   , x>3&x-y>1);
        REPORT("orlp2"   , ~y+x>2>>y);
        REPORT("orlp3"   , x*x-y*y>9);
        REPORT("orlp4"   , ~y>x/~3*x);
        REPORT("orlp5"   , -3>>y>y-x);
        REPORT("orlp6"   , ~y+x<<y>2);

        // failing always
        REPORT("orlp1"   , -x<~y>4>x);
    }
private:
    static void do_report(std::string const& caption, bool (*f)(T,T), char const* expression) {
        std::string r;
        for (T x = 0; x < 6; ++x) for (T y = 0; y < 6; ++y) r += f(x, y)?'1':'0';
        bool const correct = "000000000000000000000000111000111100" == r;
        std::cout << (correct?"OK\t":"ERR\t") << r << "\t" << caption << "\t" << expression << "\n";
    }
};

int main() {
    driver<int8_t>::run();
    driver<int16_t>::run();
    driver<int32_t>::run();
    driver<int64_t>::run();

    driver<uint8_t>::run();
    driver<uint16_t>::run();
    driver<uint32_t>::run();
    driver<uint64_t>::run();
}

```

Output on coliru, here for reference:

```
static void driver<T>::run() [with T = signed char]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = short int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = long int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = unsigned char]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = short unsigned int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
OK  000000000000000000000000111000111100    question    (x>3)&(x-y>1)
OK  000000000000000000000000111000111100    orlp0   x>3&x-y>1
OK  000000000000000000000000111000111100    orlp2   ~y+x>2>>y
OK  000000000000000000000000111000111100    orlp3   x*x-y*y>9
OK  000000000000000000000000111000111100    orlp4   ~y>x/~3*x
OK  000000000000000000000000111000111100    orlp5   -3>>y>y-x
OK  000000000000000000000000111000111100    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = unsigned int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
ERR 000000000000000000000000111001111100    question    (x>3)&(x-y>1)
ERR 000000000000000000000000111001111100    orlp0   x>3&x-y>1
ERR 111111011111001111000111111011111101    orlp2   ~y+x>2>>y
ERR 011111001111000111000011111001111100    orlp3   x*x-y*y>9
ERR 111111111111111111111111111111111111    orlp4   ~y>x/~3*x
ERR 111111011111001111000111111011111101    orlp5   -3>>y>y-x
ERR 111111011111001111000111111011111101    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

static void driver<T>::run() [with T = long unsigned int]
OK  000000000000000000000000111000111100    MASTER  (x>3) && (x>y+1)
OK  000000000000000000000000111000111100    GOLF    x>3&x>y+1
OK  000000000000000000000000111000111100    lookup  "000000000000000000000000111000111100"[x*6+y]-'0'
ERR 000000000000000000000000111001111100    question    (x>3)&(x-y>1)
ERR 000000000000000000000000111001111100    orlp0   x>3&x-y>1
ERR 111111011111001111000111111011111101    orlp2   ~y+x>2>>y
ERR 011111001111000111000011111001111100    orlp3   x*x-y*y>9
ERR 111111111111111111111111111111111111    orlp4   ~y>x/~3*x
ERR 111111011111001111000111111011111101    orlp5   -3>>y>y-x
ERR 111111011111001111000111111011111101    orlp6   ~y+x<<y>2
ERR 000000000000000000000000000000000000    orlp1   -x<~y>4>x

```

# Summary

Since this about the "cost" of repeating source code elements, you might use a lookup table. You can "hide" the lookup table, so it is either

```
 LUT[x][y]

```

or

```
 LUT[x*6+y]

```

Of course you can be pedantic and obtuse and rename the LUT

```
 L[x][y]

```

So my "version" is ... ***7 characters***. (Or make if a function and `L(x,y)` is even shorter).

Or, more importantly: correct, testable and maintainable.
> 0 votes

---
Tags: code-golf, number, tips, c++
---


title: Downhill Maze Solver

text:
# Question
Title: Downhill Maze Solver
A downhill maze is given as a series of rows of space separated digits from 0 to 9 inclusive, plus one "S" and one "X", where the S denotes the start and the X denotes the finish. In a downhill maze, you may only go to a space that is adjacent to you to the north, south, east, or west (no diagonals), and you may only go to spaces with a value less than or equal to the value you are currently on.

The program should output a path to navigate through the maze in the same format as the input, only all traversed spaces should have a "." in them, and all unvisited spaces should have a "#" in them. The starting and ending cells should also keep their "S" and "X", respectively. You can assume there is always a solution to the maze.

Example input:

```
3 3 3 3 2 1 S 8 9
3 1 1 3 3 0 6 8 7
1 2 2 4 3 2 5 9 7
1 2 1 5 4 3 4 4 6
1 1 X 6 4 4 5 5 5

```

Example output:

```
. . . . # # S . #
. # # . . # # . .
. # # # . # # # .
. # # # . # # # .
. . X # . . . . .

```

# Answer
> 3 votes
# JavaScript (ES6) 219

A function returning true or false. The solution (if found) is output on the console. It does not try to find an optimal solution.

```
f=o=>(r=(m,p,w=0,v=m[p])=>
v>':'
  ?console.log(' '+m.map(v=>v<0?'#':v,m[f]='X').join(' '))
  :v<=w&&[1,-1,y,-y].some(d=>r([...m],d+p,v),m[p]='.')
)(o.match(/[^ ]/g).map((v,p)=>v>'S'?(f=p,0):v>':'?v:v<'0'?(y=y||~p,v):~v,y=0),f)

```

**Ungolfed** to death and explained more than needed

```
f=o=>{
  var r = ( // recursive search function
    m, // maze array (copy of)
    p, // current position
    w  // value at previous position
  )=>
  {
    var v = m[p]; // get value at current position
    if (v == 'S') // if 'S', solution found, output and return true
    {
      m[f] = 'X'; // put again 'X' at finish position
      m = m.map(v => { // scan array to obtain '#'
        if (v < 0) // a numeric value not touched during search
          return '#'
        else
          return v
      }).join(' '); // array to string again, with added blanks (maybe too many)
      console.log(' '+m) // to balance ' '
      return true; // return false will continue the search and find all possible solutions
    }
    if (v <= w) // search go on if current value <= previous (if numeric, they both are negative)
    {
      m[p]='.'; // mark current position
      return [1,-1,y,-y].some(d=>r([...m], d+p, v)) // scan in all directions
    }
    // no more paths, return false and backtrack
    return false
  }

  var f, // finish position (but it is the start of the search)
      y = 0; // offset to next/prev row
  o = o.match(/[^ ]/g) // string to char array, removing ' 's
  .map((v,p) => // array scan to find f and y, and transform numeric chars to numbers
   {
     if (v > 'S') // check if 'X'
     {
       f = p;
       return 0; // 'X' position mapped to min value
     }
     if (v > ':') // check if 'S'
       return v; // no change
     if (v < '0') // check if newline
     {
       if (!y) y = ~p; // position of first newline used to find y offset
       return v; // no change
     }
     return ~v; // map numeric v to -v-1 so have range (-1..-10)
   })

  return r(o, f, 0) // start with a fake prev value
}

```

**Test** in Firefox/FireBug console

```
f('3 3 3 3 2 1 S 8 9\n3 1 1 3 3 0 6 8 7\n1 2 2 4 3 2 5 9 7\n1 2 1 5 4 3 4 4 6\n1 1 X 6 4 4 5 5 5')

```

*Output*

```
. . . . # # S . #
. # # . . # # . .
. # # # . # # # .
. # # # . # # # .
. . X # . . . . .

true

```

# Answer
> 4 votes
# C# - 463

Accepts input via STDIN, and should produce an optimal path, tested for the given test case, but not otherwise. Assumes there is always a solution.

I'm in a bit of a hurry, I have a deadline in 7 hours, but this just looked like too much fun to miss out on. I'm also out of practice. It could be very embarrassing if this goes wrong, but it's reasonably golfed.

```
using C=System.Console;class P{static void Main(){var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+');int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L;var K=new int[L];for(K[s]=s+2;j-->0;)for(i=0;i<L;i+=2){System.Action<int>M=z=>{if((z+=i)>=0&z<L&&S[z]<=S[i]&K[z]<1&K[i]>0&(i%w==z%w|i/w==z/w))K[z]=i+1;};M(2);M(-2);M(w);M(-w);}for(w=e;w!=s+1;w=i){i=K[w]-1;K[w]=-1;}for(;++j<L;)C.Write(j%2<1?K[j]<0?j==s?'S':j==e?'X':'.':'#':S[j]);}}

```

Code with comments:

```
using C=System.Console;

class P
{
    static void Main()
    {
        var S=C.In.ReadToEnd().Replace("\r","").Replace('X','+'); // read in the map, replace X with + because + < 0
        int s=S.IndexOf('S'),e=S.IndexOf('+'),w=S.IndexOf('\n')+1,L=S.Length,i,j=L; // find start, end, width, length

        var K=new int[L]; // this stores how we got to each point as loc+1 (0 means we havn't visited it)

        for(K[s]=s+2; // can't risk this being 0
            j-->0;) // do L passes
            for(i=0;i<L;i+=2) // each pass, look at every location
            {
                // if a whole load of bouds checks, point new location (i+z) at i
                System.Action<int>M=z=>{if((z+=i)>=0&z<L&&S[z]<=S[i]&K[z]<1&K[i]>0&(i%w==z%w|i/w==z/w))K[z]=i+1;};
                // try and move in each direction
                M(2);
                M(-2);
                M(w);
                M(-w);
            }

        for(w=e;w!=s+1;w=i) // find route back
        {
            i=K[w]-1; // previous location
            K[w]=-1; // set this so we know we've visited it
        }

        for(;++j<L;) // print out result
            C.Write(j%2<1?K[j]<0?j==s?'S':j==e?'X':'.':'#':S[j]); // if K < 0, we visit it, otherwise we don't
    }
}

```

---
Tags: code-golf, graph-theory, path-finding, grid
---


title: Fractal Points on a Line

text:
# Question
Title: Fractal Points on a Line
Sometimes, when I'm really bored (*really* bored), I like to draw a line segment and draw points on it.

First, I draw a line segment of a certain size, which is 2^N for some value of N. The line will be represented by a series of `.` characters.

```
................

```

Then, I plot a point at the left end. Points will be represented by `X` characters.

```
X...............

```

Then, I follow a pattern. Starting at the most recently plotted point (which I'll call A), I advance to the next plotted point (B) on the line (wrapping around as necessary). Then, I advance to the *next* plotted point on the line (C). Then, I plot a new point half-way in between this third point (C) and the next already plotted point (D).

Whenever you wrap around the line, the "middle" is determined in wrapping manner. The newly plotted point is always to the right of C.

Let's say that the following line was my current line. Here is how I would plot the next two points. For this example, I'll label each important point with a letter.

```
X...A...X.X...X.
    ^

X...A...B.X...X.
        ^

X...A...B.C...X.
          ^

X...A...B.C...D.
            ^

X...X...X.X.A.X.
            ^

X...X...X.X.A.B.
              ^

C...X...X.X.A.B.
^

C...D...X.X.A.B.
  ^

X.A.X...X.X.X.X.
  ^

```

Returning to the previous example, the next point will be plotted in the middle of the line.

```
X.......X.......

```

This is perhaps a little bit of a special case: advancing to the next point simply leaves you where you started. The only useful halfway point is the "cyclic" halfway point (the halfway point on the line), as opposed plotting a point on top of itself.

Below is the series of points that I would plot on the line from here to the end.

```
X.......X.......
X.......X...X...
X.......X.X.X...
X...X...X.X.X...
X...X...X.XXX...
X.X.X...X.XXX...
X.X.X...XXXXX...

```

There is no longer any room to plot the next point, as it would have to be wedged between two adjacent points, so I have reached the maximum depth for the given value of N = 4. The last line in the above list is "complete."

## The Challenge

The goal is to write the shortest program/named function that will print/return the completed line for a given value of N. The above shows N = 4.

## Input

Input will be a single non-negative integer N. The length of the generated line will then be 2^N.

## Output

Output will be the completed line of length 2^N, formed by `.` and `X` characters. A trailing newline doesn't matter.

## Example I/O

```
0
X

1
XX

2
X.XX

3
X.X.XXX.

4
X.X.X...XXXXX...

5
X.X.X...X...X...X.XXX.XXX.......

```

# Answer
> 4 votes
# Python 2, 137

```
n=input()
l=[0]*2**n;i=0
while~i%2:i=i/2%2**n;l[i]=1;i=sum([k for k,v in enumerate(l*4)if(k>i)*v][1:3])
print''.join(['.X'[x]for x in l])

```

Quite straightforward.

# Pyth, 49

More or less a translation. Main difference is that I don't use a list representing the line, I use a string.

```
J*\.^2QW!%Z2K%/Z2lJ=JXJK\X=Zs<tf&q\X@JT>TKU*4J2)J

```

Try it online.

```
                         Q=input(); Z=0 #implicit
J*\.^2Q                  J = "."*(2^Q)
W!%Z2                    while !(Z%2):
  K%/Z2lJ                  K=(Z/2)%(len(J))
  =JXJK\X                  change J, the point at index K is changed to a "X"
       f          U*4J     filter all elements T in [0, 1, 2, ..., 4*len(J)-1]:
        &q\X@JT>TK           where J[T]=='X' and T>K
     <t               2    only us the second and third element
  =Zs                      and store the sum to Z
)J                       end while and print J

```

# Answer
> 4 votes
# Clip, 95

```
[z?zF#2(z*2*:(#2(z'.'X]'X]]n[Fa[b[q[j[r?=rirFrsrb'X]b]][t[u+*<ut*Blb/+tu2]]g+2jqg+3jq]#qa]%b'X}

```

# Answer
> 3 votes
# CJam, ~~55 53 51~~ 50 bytes

```
2ri#:N'.*0aN{):U+__Nf++$_U#))>2<1bNe|2/N%|}*{'Xt}/

```

Something to start with.

Try it online here

# Answer
> 3 votes
## GolfScript (61 bytes)

```
~2\?,[]0{.@|$4*.@?2+1$>2<.+~<!4$,*++.2/\1&!}do;`{&!'X.'1/=}+%

```

The number of loop iterations required seems to be A061419, but the do-loop is shorter than calculating that. A divmod would save a char inside the do loop. The part which feels most wasteful is the output conversion, but I don't see how to improve it.

# Answer
> 2 votes
# Java, ~~209~~ ~~207~~ ~~195~~ 191 bytes

I'm surprised I was able to get it this short. There is probably still room for improvement. As usual, suggestions will be appreciated :)

This returns a `char[]`. Call using `a(n)`.

```
char[]a;int b,c,d,e=2;char[]a(int f){java.util.Arrays.fill(a=new char[b=1<<f],'.');for(a[0]=88;d+1<e;c=(d+e)/2,a[c%b]=88)e=b(d=b(b(c)));return a;}int b(int f){for(;;)if(a[++f%b]>87)return f;}

```

Indented:

```
char[] a;
int b, c, d, e = 2;

char[] a(int f){
    java.util.Arrays.fill(
            a = new char[
                    b = 1 << f
                    ]
            , '.'
    );
    for(
            a[0] = 88;
            d + 1 < e;
                c = (d + e) / 2,
                a[c % b] = 88
        )
        e = b(
                d = b(
                        b(c)
                )
        );
    return a;
}

int b(int f){
    for (;;)
        if (a[++f % b] > 87)
            return f;
}

```

12 bytes thanks to Peter :)
4 bytes thanks to TNT ;)

# Answer
> 1 votes
# Mathematica, ~~110~~ ~~102~~ ~~112~~ 108

```
a=Array["."&,n=2^Input[]];a[[Mod[Round@{n/2,n}//.{x_,y_,z___}/;y-x>1:>{z,x+n,(x+y)/2+n,y+n},n]+1]]="X";""<>a

```

# Answer
> 1 votes
# Haskell, 182 bytes

```
(a:b)%(c:d)|a<c=a:b%(c:d)|1<2=c:(a:b)%d
f i=putStr$map(!(0:g[0,n..]))[0..n-1]where n=2^i;e!l|e`elem`l='X'|1<2='.';g(_:_:c:d:r)|m==c=[]|1<2=mod m n:g((d:r)%[m,m+n..])where m=div(c+d)2

```

Usage: `f 5`. Output: `X.X.X...X...X...X.XXX.XXX.......`.

Unfortunately Haskell doesn’t have a merge function in the standard libraries, so I have to provide my own (-\> `%`). Fortunately I have to merge only infinite lists, so I don’t have to cover the base cases, i.e. empty lists. It still costs 40 bytes.

How it works: instead of setting the `X`s directly in an array, I keep a list of positions where they are. Furthermore I do not wrap around at `2^N` but keep on increasing the positions towards infinity (e.g. for N=2 with an `X` at the front, the position list looks like `[0,4,8,12,16,20,…]`). I take the 3rd and 4th element (`c` and `d`), calculate the new position `(c+d)/2`, keep it for the output list, merge the old position list from position 4 (the `d`) on with a new one starting with `(c+d)/2` and recur. I stop when `(c+d)/2` equals `c`. Finally I add a `0` to the output list and print `X`s at the given positions and `.` elsewhere.

```
step by step example, N=2

step  position list       (c+d)/2  output     lists to merge (pos. list for next round)
                                   list       old list from d on / new list from (c+d)/2

  #1  [0,4,8,12,16,…]       10     [10]          [12,16,20,24,…] / [10,14,18,22,…]
  #2  [10,12,14,16,18,…]    15     [10,15]       [16,18,20,22,…] / [15,19,23,27,…]
  #3  [15,16,18,19,20,…]    18

stop here, because c equals (c+d)/2

add 0 to the output list: [0,10,15]
take all elements modulo 2^N: [0,2,3]
print X at position 0, 2 and 3

```

---
Tags: code-golf
---


title: Calculate the size of the moon

text:
# Question
Title: Calculate the size of the moon
## The size of the moon mystery

I am sure you have heard that the moon changes its size. When you're in love and you're lucky, the moon is almost twice in size compared to normal situations. Some people say the reason is the atmosphere which acts as a lens. Others think that it is only a matter of comparison to other objects such as trees nearby. Whatever explanation you read, it's quite subjective.

## The size of the moon science

Ok, we're programmers, aren't we? We rely on facts, right? So here's the experiment:

1. Take a nice camera which supports setting time and aperture manually.
2. Set your camera to maximum zoom level.
3. Go out, take some photographs of the moon in order to detect the best settings so that the moon is sharp and lighting is just fine.
4. Remember the settings
5. Take photos of the moon with those settings every time you think the moon is large or small.
6. Calculate the size of the moon in pixels

The camera won't lie, would it? By counting the bright pixels we can effectively measure the size of the moon - at least in pixels.

If the size is the same across all photos, then it's a bug in our brain. If the size differs, then there's room for speculation

* the moon really grows (but what does it eat?)
* there's an atmospherical lens effect
* the moon has an elliptical curve and is sometimes nearer, sometimes further away from earth
* ...

But I'll leave that open until your task is completed. Of course you want to know in advance if your software can calculate the moon size accurately.

## The task

Given a few optimized pictures of the moon, please calculate the size of the moon. The optimization is: the pixels are either black or white. Nothing in between. No antialiasing. That makes it easy, doesn't it?

The caveat: the moon is not always full, you know ... it can be a sickle! But even in shape of a sickle, the size of the moon is larger. So you'll calculate the full size, please.

* Your program takes a PNG as input, e.g. as file name command line argument, piped into `stdin` or as a Bitmap object (of a standard framework library) if you write a function instead of a program.
* Your program works with any reasonable input bitmap size, not necessarily square. Minimum width and height of 150 pixels are guaranteed.
* The full moon covers at least 25% of the picture.
* Your program outputs the calculated size of the moon in pixels as if it were a full moon.
* We assume that the moon is a perfect sphere.
* The exact size is always an integer number, but you can output a decimal number if your calculation returns that.
* The accuracy should be between 98% and 102%. (That's rather a guess than something I could guarantee to be achievable. If you think it's too hard to reach, please leave a comment.)

**Update**:

* The center of the moon isn't necessarily in the middle of the picture.
* The minimum visible area is 5% of the moon or 1.25% of the total number of pixels.
* The picture is taken in a way that the whole moon would fit the image, i.e. the total number of pixels is an upper boundary for the moon size.
* The moon will not be cropped / clipped.

## The samples

You can generate your own samples using the blend file if you like. I have created the following pictures for you. You can count pixels in a PNG file using WhitePixelCounter.exe (needs .NET) to check whether the image contains black and white pixels only and how many of them.

The following 256x256 pixel images differ in the amount of white pixels, but should all result in a calculated moon size of 16416 pixels.

And these 177x177 pixel images should return 10241 pixels. The images are basically the same, but this time a camera with a different focal length was used.

Non-square and non-centered samples with a result of 9988:

Oh, I don't have a reference implementation for now and I even don't know whether I am able to implement something. But in my brain there is a strong belief that tells me it must be mathematically solvable.

## The rules

This is Code Golf. The shortest code on 2015-03-30 gets accepted.

# Answer
> 10 votes
# Mathematica ~~126 119~~ 109 bytes

Mathematica can measure the elongation of a component in an image. A full moon, being perfectly symmetric, has an elongation of 0, on a scale of 0 to 1.

A diminishing moon becomes increasingly elongated, to a maximum of roughly 0.8.

`0.998 -0.788 x-0.578 x^2` was the empirically determined model (based on the large photos) for \`predicting the fullness of the moon (by area), given its elongation.

I adjusted the model to `1- 0.788 x -0.578 x^2` so that with exactly zero elongation (full moon) the model will return 1 for the pixel scale factor. It saves 4 bytes and still stays within the accuracy limits.

This model is used for any size images. The moon image does not need to be centered. It also does not need to cover a fixed proportion of the photo.

Here are the data points (elongation, displayedMoonPixels/fullMoonPixels) for the large images and the parabolic model that was generated to fit the data. Linear models fit ok, but the quadratic model is dead on, within limits (see below).

Here the data are from the large pictures. So is the model

---

Below, the data (the red points) are from the small pictures. The model (the blue curve) is the one generated by the large pictures, the same one as displayed above.

The smallest crescent has 7.5% the area of a full moon. (The smallest crescent among the large photos is 19% of a full moon.) If the quadratic model had been based on the small photos the fit below would be better, only because it accommodated the small crescent. A robust model, that would stand up under a wide range of conditions, including very small crescents, would be better made from a larger variety of pictures.

The closeness of fit shows that the model was not hard-coded for the given pictures. We can be fairly certain that the elongation of a moon is independent of the size of the photo, as one would expect.

`f` takes the image, `i`, as input and outputs the predicted size of the full moon, in pixels. It works for off-center shots.

As the data below show, it all of the test cases except one. The moons were arranged from full to most diminished.

```
i_~c~t_ := Max@ComponentMeasurements[i, t][[All, 2]];
f@i_ := i~c~"Count"/(1 - 0.788 x - 0.578 x^2 /. x -> i~c~"Elongation")

```

More than one image component may turn up in a photo. Even a single pixel separated from the others will be considered a distinct component. For this reason, it is necessary to search "all" components, to find the one that has the greater number of pixels. (One of the small photos has more than one image component.)

**Large pictures**

Predictions of moon size made from the large photos were uniformly accurate.

```
{"predicted size of full moon", f[#] & /@ large}
{"accuracy", %[[2]]/16416}

```

> {"predicted sizes of full moon", {16422., 16270.9, 16420.6, 16585.5, 16126.5, 16151.6}}
>
> {"accuracy", {1.00037, 0.991161, 1.00028, 1.01033, 0.982367, 0.983891}}

---

**Small pictures**

Predictions of moon size made from the small photos were uniformly, with one great exception, the final picture. I suspect the issue stems from the fact that the crescent is very narrow.

```
{"predicted sizes of full moon", f[#] & /@ small}
{"accuracy", %[[2]]/10241}

```

> {"predicted sizes of full moon",{10247.3, 10161., 10265.6, 10391., 10058.9, 7045.91}}
> {"accuracy", {1.00061, 0.992192, 1.0024, 1.01465, 0.982221, 0.68801}}

# Answer
> 5 votes
# J, ~~227~~ 207 bytes (maximal error 1.9%)

My main idea is that if we can find 3 points on the contour of the moon which are on the contour of the full moon too we can compute the circumcircle of these points. That circumcircle will be to full moon.

If we find two white points with maximal distance those will always be such points as they will be either a real diagonal in the full moon or the endpoints of the crescent. ~~We can find the pair of points with the greatest distance in any graph by selecting the point furthest from any given starting point and then selecting the point furthest from the selected one.~~

We find a third point with a maximal value of the products of the distances from the previous points. This will always be on the contour and on the outer side of a crescent or the bigger side of a gibbous.

The diameter of the circumcircle is computed as the length of one side divided by the sinus of the opposite angle.

The time-complexity of this method is linear in the size of the input image.

## Code

```
f=.3 :0
load'graphics/png'
i=.readpng y
p=.(,i=_1)#|:,"%.0 1|:,"0/&>/<@i."*$i
s=.%:+/|:*:(-1|.]) (([,],:m@(*&d))(m@d))(m=.p{~(i.>./)@])(d=.+/@:*:@((|:p)-])) 0{p
o.*:-:({.s)%0 o.((+/-2*{.)*:s)%2**/}.s
)

```

The function expects the input filename as a string.

(For a (little) more readable version check revision history.)

## Code explanation

* p is a list of white pixel coordinates (called points in the future)
* function d computes distances between elements of p and a given point
* the second part of the definition of s creates a 3-point list:

+ A is the furthest point from the first point in the list
    + B is the furthest point from A
    + C is a point with a maximal value of distance form A times distance from B
* s is the side-lengths of triangle ABC
* the last line computes the area of the circumcircle of ABC which is the full moon

## Results

The largest error is 1.9%.

Images are in the same order as in the question.

```
Output  Accuracy
----------------
  16407 0.999453 NB. Large images
16375.3 0.997523
16223.9 0.988301
16241.5 0.989369
16262.6 0.990654
16322.1 0.994279
10235.3 0.999445 NB. Small images
10235.3 0.999444
10221.2 0.998067
10220.3 0.997978
  10212 0.997169
10229.6  0.99889
9960.42 0.997239 NB. Offset images
9872.22 0.988408
10161.8   1.0174
9874.95 0.988681
 9805.9 0.981768

```

# Answer
> 2 votes
# Matlab ~~162~~ 156 (not quite in the current error margin)

First of all: The accuracy is under 2% for all but one image in each of the two series, where it is greater (about 5% and 14%). My approach was finding the two pixels of the moon that are the furthest away from each other, and then using this as an estimate for the diameter.

```
a=imread(input(''));                 %read input image
b=a(:,:,1)>0;                        %binarize red channel
s=size(b);                           %get size of the image
[x,y]=meshgrid(1:s(1),1:s(2));
z=(x+i*y).*b;z=z(z~=0);              %find the coordinates of all white pixels (as a list)
o=ones(size(z(:)))*z(:)';
disp(max(max(abs(o-o.').^2))*pi/4);  %calculate the maximum of the distance between each possible pair and evaluate area formula

```

These are the accuracy results (reltative deviation `1 - (predicted size / real size)`)

```
0.0006 0.0025 0.0169 0.0500 0.0521 0.0113 0.0006 0.0006 0.0026 0.0472 0.1383 0.0131

```

# Answer
> 1 votes
## C# - 617

This solution does not work for all images, because on one of the images, the slope (m) becomes infinity.

The principle was mentioned before:

1. Find two points with maximum distance (red)
2. Imagine a line between them (red)
3. Imagine a line with rectangular angle in the middle (green)
4. Find white points on the green line
5. Use the one with maximum distance from other points (green)
6. Calculate the area of a circle from three points

The problematic case is this one, where the slope is infinity. It is possible to workaround by rotating the image 90° or in code, loop over the `y` axis instead of `x`.

```
double A(Bitmap b){var a=new List<P>();for(var y=0;y<b.Height;y++)for(var x=0;x<b.Width;x++)if(b.GetPixel(x,y).R>0)a.Add(new P{x=x,y=y});double c=0.0,d=0.0,e=0.0,f=0.0,g=0.0,n=double.MaxValue;foreach(var h in a)foreach(var i in a){var t=Math.Sqrt(Math.Pow(h.x-i.x,2)+Math.Pow(h.y-i.y,2));if(t>c){d=h.x;f=i.x;e=h.y;g=i.y;c=t;}}c=(f-d)/(e-g);for(int x=0;x<b.Width;x++){int y=(int)(c*x+((e+g)/2-c*(d+f)/2));if(y>=0&&y<b.Height&&b.GetPixel(x,y).R>0){var s=(g-e)/(f-d);var q=(y-g)/(x-f);var j=(s*q*(e-y)+q*(d+f)-s*(f+x))/(2*(q-s));var k=-(j-(d+f)/2)/s+(e+g)/2;var l=(j-d)*(j-d)+(k-e)*(k-e);if(l<n)n=l;}}return Math.PI*n;}

```

The minimum accuracy is

* +1,89% for the 256 pixel images
* -0.55% for the 177 pixel images
* -1.66% for the non-square images

---
Tags: code-golf, image-processing
---


title: Golfing every ASCII character in 99

text:
# Question
Title: Golfing every ASCII character in 99
*99* is a programming language I invented earlier this week for my challenge Write an interpreter for 99. (Invented but never needed to implement thanks to half a dozen of you. ;) ) The full language spec is in that challenge so I'm not bothering to repost it all here.

In *99* you can print individual ASCII characters to stdout, but due to the constraints of the language, it is not always clear how to print a particular character as concisely as possible.

For each of the 128 ASCII characters, write a *99* program that takes no input and outputs that sole character. You may code any or all of these answers by hand, or you can write another program (in any language you like) to generate them for you.

The sum of the characters in each of your 128 *99* programs is your score. **The lowest score wins.** Newlines count as one character.

Remember, in *99*, only even sized variables like `9999` output ASCII characters (odd sized variables output integers). Their value is divided by 9 and then taken mod 128, so values do not need to be in a certain range to map to ASCII characters. For example, the internal values 297, 1449, and -855 all correspond to the character `!` because when they are divided by 9 and taken mod 128, they all become 33, which is the character code for `!`.

If you need an interpreter for *99*, I'd suggest Mac's Python answer.

I know I said my next challenge would be more interactive but I'm still working on the stuff for that one.

# Answer
> 7 votes
# One assignment, 2075 (optimal)

This should be the optimal value (unless I have a big error in reasoning or my testing sucks).

First of all. There are only 7 different numbers (mod 128) you can express in 99. All values of 7 or more 9 evaluate to the same number 71. (Because 10^8 mod 128 == 0, 10^9 mod 128 == 0, ...)

If one of the 4 values you can express with an even number of nines, than outputting this number is clearly the optimal solution.

Otherwise I try to reach the number with one assignment statement (assign to 99) and print 99. As it turns out the maximal program size with this approach is 22 char. Clearly using Goto takes definitely more than that. The only possibility that a one-assignment solution might be beaten is a solution with two assignments. I tested this (hopefully with no errors, the code for this is quite messy), and found no solution for any ASCII char.

Therefore only checking the 4 direct numbers and the one-assignment approach should be enough to find the optimal solution. The following Python (2 and 3 compatible) program generates all programs and sums up their lengths. It uses a simple IDA\* approach.

```
from itertools import count

def nines_to_dec(nines):
    return ((10**nines - 1) // 9) % 128

def shortest_representation(ascii_value):
    # try simple output,
    # max code length is 8, (8 nines == 10 nines == 12 nines == ...)
    # if this works, than this is the shortest representation

    for nines in range(2, 9, 2):
        if nines_to_dec(nines) == ascii_value:
            return "9" * nines

    # otherwise try one assignment
    for length in count(1):
        result = assignment(ascii_value, length, [])
        if result:
            return "99 " + result + "\n99"

def assignment(value, left, nines_list):
    if left == 0:
        eval_numbers = [nines_to_dec(nines) for nines in nines_list]

        if (sum(eval_numbers[::2]) - sum(eval_numbers[1::2])) % 128 == value:
            return " ".join("9" * nines for nines in nines_list)
        else:
            return False

    for nines in range(1, 8):
        left2 = left - nines - 1 # -1 for space
        if left2 >= 0:
            result = assignment(value, left2, nines_list + [nines])
            if result:
                return result

    return False

lengths = []
for i in range(128):
    program =shortest_representation(i)
    lengths.append(len(program))
    print("ASCII-value: {}, ASCII-char: {}".format(i, chr(i)))
    print(program)

print(sorted(lengths))
print(sum(lengths))

```

The output is of the following form:

```
....
ASCII-value: 65, ASCII-char: A
99 9 999999 9999999
99
ASCII-value: 66, ASCII-char: B
99 9 99 9999 99
99
ASCII-value: 67, ASCII-char: C
99 9 99 9 99 9999
99
....

```

You can find the complete output at: http://pastebin.com/bKXLAArq

The char with the shortest program (2 char) is `vertical tab - 11` with a program length of 2, the chars with the longest programs (22 char) are `bell - 7` and `A - 65`.

The sum for all programs is 2075.

And by the way, I used the k/q interpreter from tmartin. I hat quite some troubles with the other ones (Python, Perl, CJam). Not sure if it was my fault.

# Answer
> 3 votes
# A Variety of Techniques, 42109

For the numbers, instead of calculating the large ASCII character, I just calculated the number's value. You only said to be able to output the character, so this should still work.

EDIT: Switched the numbers to use the ASCII characters, so disregard that. I left the original number code in the Java code but commented out in case anyone wanted to use it.

Some of these I did by hand, most I just wrote a program to type out.

These are made up of 1-4 lines each, so they're fairly friendly to just copy and paste into a program. It should be noted that they don't work in succession due to my generated code not preserving variable states.

The most common technique used here was the same as orlp's approach:

> Keep subtracting 9 from 99, then output.

My version differs by using some custom cases and composing a lot of the math onto just one line. Custom cases are just where the character can be represented with just a bunch of 9's and no math or my generation code could be shortened.

## Programs

I've put the output on Pastebin for those of you who don't feel like running the program:

http://pastebin.com/Cs6WZUfb

## Java Code I used:

```
public class AsciiGen99 {

  public static void main(String[] args) {
    long totalsize = 0;
    for (int i = 0; i < 128; i++) {
      System.out.println("\n The program for ASCII code " + i + " is as follows:\n");
      String yea = find(i);
      if (yea != null) {
        System.out.println(yea);
        totalsize += yea.length();
      } else {
        String v = "99 9 9\n9 99 9";
        if (i != 0) {
          v += "\n99";
          for (int j = 0; j < i; j++) {
            v += " 99 9";
          }
        }

        v += "\n99";

        System.out.println(v);
        totalsize += v.length();
      }
    }
    System.out.println(totalsize);
  }

  public static String find(int i) {
    switch (i) {
      case '\0':
        return "99 9 9\n99";
      case '\1':
        return "99 9\n99";
    }
//    if (48 <= i && i <= 57) {
//      switch (i) {
//        case '0':
//          return "9 9 9\n9";
//        case '1':
//          return "9";
//        case '2':
//          return "999 9 9\n9 999 9\n999 999 9 999 9\n999";
//        case '3':
//          return "999 9 9\n9 999 9\n999 999 9 999 9 999 9\n999";
//        case '4':
//          return "999 9 9\n9 999 9\n999 999 9 999 9 999 9 999 9\n999";
//        case '5':
//          return "999 9 9\n9 999 9\n999 999 9 999 9 999 9 999 9 999 9\n999";
//        case '6':
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//        case '7':
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//        case '8':
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//        case '9'://ironic
//          return "99 9 9\n9 99 9\n999 99 9 99 9 99 9 99 9 99 9 99 9 99 9 99 9 99 9\n999";
//      }
//    }
    int x, a;
    for (x = 0; x < 100000; x++) {
      a = i + 128 * x;
      String s = "" + a*9;
      if (containsOnly9(s) && (s.length() & 1) == 0) {
        return ("" + (a * 9));
      }
    }

    return null;
  }
  public static boolean containsOnly9(String s) {
    for (char c : s.toCharArray()) {
      if (c != '9' && c != ' ' && c != '\n' && c != '\r' && c != '\t') {
        return false;
      }
    }
    return true;
  }
}

```

# Answer
> 1 votes
# Repeated subtraction, 65280

A trivial solution to compare against. Keep subtracting 9 from 99, then output. Example for ASCII character 10:

```
99 99 9
99

```

There are 128 programs. The first program is two characters long (99), each one after that is 8 characters (99 99 9\n) longer than the previous one.

Python program generating programs seperated by empty lines, and computing score:

```
score = 0
for n in range(128):
    program = "99 99 9\n" * n + "99"
    score += len(program)
    print(program + "\n")

print(score)

```

---
Tags: kolmogorov-complexity, metagolf
---


title: Write an interpreter for 99

text:
# Question
Title: Write an interpreter for 99
*99* (pronounced "ninety-nine") is a brand new Esoteric programming language (not to be confused with 99, note the italics). Your task in this challenge is to write an interpreter for *99* that is as short as possible. The submission with the fewest bytes wins. Tiebreaker goes to the submission posted first.

Since this question is a bit more in depth than usual, and I'm eager to see good answers, I'll be awarding a 250 rep bounty to my favorite answer (not necessarily the winner).

# *99* Spec

*99* is an imperative language. Each line in a *99* program is a single statement, and during execution, the instruction pointer starts at the top line and goes through each of the subsequent lines in order, executing them along the way. The program ends when the last line has been executed. Goto statements may reroute the path of the instruction pointer.

Newline, space, and `9` are the only three characters that matter in a *99* program. All other characters are completely ignored. Additionally, trailing spaces on each line are ignored, and multiple spaces in a row are read as one space. ("Newline" refers to any common line break encoding. It doesn't matter which one your interpreter uses.)

So this program:

```
   9      BLAH        99   9a9bb9c9
9 this line and the next have 6 trailing spaces 9

```

Is identical to this program:

```
 9 99 9999
9 9

```

## Variables

Variables in *99* all have names that are one or more `9`'s strung together (`9+` in regex). For example, `9`, `99`, and `9999999999` are all distinct variables. Naturally, there are infinitely many (barring memory limitations).

The value of each variable is a signed, arbitrary precision integer. By default, each variable is assigned to its own numeric representation. So unless it has been reassigned, the value of the variable `9` is the number 9, and the value of the variable `99` is the number 99, and so on. You could think of it as treating the variables as plain numbers until they are explicitly assigned.

**I will use `V` to refer to an arbitrary variable name below.
Each instance of `V` could be replaced with `9`, `99`, `999`, `9999`, etc.**

## Statements

There are five different statement types in *99*. Each line in a *99* program contains exactly one statement.

The syntax described here assumes all extraneous characters have been removed, all trailing spaces have been removed, and all sequences of multiple spaces have been replaced with single spaces.

**1. No Operation**

```

```

An empty line is a no-op. It does nothing (besides incrementing the instruction pointer).

**2. Output**

```
V

```

A single variable `V` on a line prints that variable to stdout.

If `V` has an odd number of `9`'s (`9`, `999`, etc.) then the integer value of `V` divided by 9 will be printed (in decimal).

If `V` has an even number of `9`'s (`99`, `9999`, etc.) then the ASCII character with code `V` divided by 9, mod 128 will be printed. (That's `(V / 9) % 128`, a value from 0 to 127.)

*Example*: The program

```
9
9999

```

would print `1W`. The first line prints `1` because 9/9 is 1. The second line prints `W` because 9999/9 is 1111, and 1111 mod 128 is 87, and 87 is the character code for `W`.

Note that line breaks are not printed between output tokens. `\n` needs to be explicitly printed for a line break.

**3. Input**

```
 V

```

A single variable `V` on a line **with a leading space** takes input from stdin and stores it in that variable.

If `V` has an odd number of `9`'s then the user may type in any signed integer, and `V` will be set to 9 times that value.

If `V` has an even number of `9`'s then the user may type in any ASCII character, and `V` will be set to 9 times its character code.

*Example*: Given `-57` and `A` as input, this program

```
 9
9
 99
99

```

would output `-57A`. Internally, the variable `9` would have the value -513, and `99` would have the value 585.

Your interpreter may assume that the inputs are always syntactically valid.

**4. Assignment**

This statement can be arbitrarily long. It is two or more variables on a line, separated by spaces:

```
V<sub>1</sub> V<sub>2</sub> V<sub>3</sub> V<sub>4</sub> V<sub>5</sub> ...

```

This assigns `V<sub>1</sub>` to the sum of all the `V`'s with even indices, minus the sum of the `V`'s with odd indices (excluding `V<sub>1</sub>`). Assignments are by value, not by reference.

It could be translated in most languages as `V<sub>1</sub> = V<sub>2</sub> - V<sub>3</sub> + V<sub>4</sub> - V<sub>5</sub> + ...`.

So, if there are only two variables, it's normal assignment:

`V1 V2``V1 = V2`

If there are three, then it's subtraction:

`V1 V2 V3``V1 = V2 - V3`

And the `+`/`-` sign keeps switching back and forth with each additional variable:

`V1 V2 V3 V4``V1 = V2 - V3 + V4`

*Example*: This program would output `1110123`:

```
999           Prints triple-nine divided by nine (111).
999 9 9       Assigns triple-nine to zero (nine minus nine).
999           Prints triple-nine divided by nine (0)
9 999 9       Assigns single-nine to negative nine (zero minus nine).
999 999 9     Adds nine to triple-nine (really subtracts negative nine).
999           Prints triple-nine divided by nine (1).
999 999 9     Adds nine to triple-nine (really subtracts negative nine).
999           Prints triple-nine divided by nine (2).
999 999 9     Adds nine to triple-nine (really subtracts negative nine).
999           Prints triple-nine divided by nine (3).

```

**5. Goto (jump if all zero)**

This statement can also be arbitrarily long. It is two or more variables on a line, separated by spaces, **with a leading space**:

```
 V<sub>1</sub> V<sub>2</sub> V<sub>3</sub> V<sub>4</sub> V<sub>5</sub> ...

```

If some of the values besides `V<sub>1</sub>` are non-zero, then this behaves just like a no-op. The instruction pointer is moved to the next line as usual.

If *all* of the values besides `V<sub>1</sub>` *are* zero, then the instruction pointer is moved to line number `V<sub>1</sub>`. The lines are zero-indexed, so if `V<sub>1</sub>` is zero, then the pointer moves to the top line. The program terminates (normally, without error) if `V<sub>1</sub>` is negative or is larger than the highest possible index (number of lines minus one).

**Note that `V<sub>1</sub>` was not divided by 9 here. And since it's impossible to have a variable be a value that's not a multiple of 9, only line numbers that are multiples of 9 can be jumped to.**

*Examples:*

This program will print `1`'s forever:

```
9          Prints single-nine divided by nine (always 1).
99 9 9     Assigns double-nine to zero.
 99 99     Jumps to line zero (top line) if double-nine is zero.

```

This program

```
99999999                                              Print G.
999 99                                                Set triple-nine to ninety-nine.
9999999999 9999999999 9999999999 99 99 9 9 999 999    Set 10-nine to zero.
99999999999 9999999999                                Set 11-nine to zero.

999                                                   Print triple-nine's value divided by nine. (This is the ninth line.)
99999999                                              Print G.
999 999 9                                             Subtract nine from triple-nine.
 99999 999                                            Jump to line 5-nines if triple-nine is zero (ends program).
 9 99999999999 9999999999                             Jump to line nine if 10-nine and 11-nine are zero (always jumps).

```

will output the numbers 11 to 1, in decreasing order, surrounded by `G`'s:

```
G11G10G9G8G7G6G5G4G3G2G1G

```

## Additional Details

The ideal interpreter will run from the command line with the *99* program file name as an argument. The I/O will also be done on the fly in the command line.

You may, however, just write an interpreter function that takes in the program as a string as well as a list of the input tokens (e.g. `["-57", "A"]`). The function should print or return the output string.

Slightly different ways of running the interpreter and handling I/O are fine if these options are impossible in your language.

---

**Bonus:** Write something cool in *99* and I'll gladly put it in this post as an example.

---

Hope you enjoyed my 99th challenge! :D

# Answer
# CJam, 157 bytes

```
{:I;_N" 9"+--N/:P:,$W=){1a*Ab}%:V;{PT):T(=:LS%_{LS#\:,_,({(\{V=}%@{V-1@{2$*+0@-\}*\;t:V;}{:|T@V=9*?:T;}?}{~\{_V=\1&!{128%c}*o}{VIW):W=it:V;}?}?}R?Tg)TP,<*}g}

```

Try it online:

### Explanation

Trying to format this with proper indentation and comments would probably take forever, so I'll just give an algorithmic summary.

The code is a block, CJam's analog to anonymous functions. The block expects the program string and list of inputs on the stack when executed.

Initialization consists of three steps. First, the input list is saved. Then, every character in the program that isn't meaningful is removed and the result is split into a list of lines and saved. Finally, the variable list is initialized. This list maps each variable, indexed by name length, to its value divided by 9 (a variable can never hold a value that's not a multiple of 9, and all operations except goto benefit from this change). The list is initialized up to the length of the longest line, which is an upper bound on the longest varaible name present. There's also a bit of implicit initialization due to initial variable values: the line number is 0 and the input index is -1.

The interpreter is implemented as one would expect: a loop that reads the next line, increments the line number, and executes the line while the line number points to an existing line. Line parsing first checks that the line isn't empty, then branches based on whether the arity is 1 or \>1, then branches based on whether there was a leading space. These four branches emulate the four (excluding no-op) operations in a mostly straightforward manner, albeit agressively golfed like everything else. Perhaps one optimization of note is that, since a valid input sequence should always produce an element of type expected by the program, I omitted making separate cases for input based on the length of the variable name. It is simply assumed that the element read from the input list is of the expected type.
> 16 votes

# Answer
# Python 3, 421 414 410 404 388 395 401 bytes

### Golfed:

```
import sys,re
v,i,c,g,L={},0,[re.sub('( ?)[^9]+','\\1',l).rstrip().split(' ')for l in open(sys.argv[1])],lambda i:v.get(i,int(i)//9),len
while-1<i<L(c):
 d=c[i];l=L(d);e,*f=d;i+=1
 if l>1:
  x,*y=f
  if e:w=list(map(g,f));v[e]=sum(w[::2])-sum(w[1::2])
  elif l==2:j=input();v[x]=int(j)if L(x)%2 else ord(j)
  elif~-any(g(j)for j in y):i=g(x)*9
 elif e:w=g(e);print(w if L(e)%2 else chr(w%128),end='')

```

### Ungolfed:

```
import sys, re

# Intialise variable table.
vars_ = {}
get_var = lambda i: vars_.get(i, int(i)//9)

# Parse commands.
commands=[re.sub('( ?)[^9]+','\\1',l).rstrip().split(' ') for l in open(sys.argv[1])]

# Run until the current instruction index is out of bounds.
index=0
while 0 <= index < len(commands):
    # Get the current command and increment the index.
    command = commands[index]
    l = len(command)
    first = command[0]
    index += 1

    if l > 1:
        # Handle the "assignment" command.
        if first:
            operands = [get_var(i) for i in command[1:]]
            vars_[first] = sum(operands[0::2]) - sum(operands[1::2])
        # Handle the "input" command.
        elif l==2:
            inp = input()
            vars_[command[1]] = int(inp) if len(command[1]) % 2 else ord(inp)
        # Handle the "goto" command.
        elif not any(get_var(i) for i in command[2:]):
            index = get_var(command[1]) * 9
    # Handle the "output" command.
    elif first:
        val = get_var(first)
        print(val if len(first) % 2 else chr(val % 128),end='')

```

Pretty much just a literal implementation of the spec, golfed down as far as I can get it.

Run from the command line by supplying a 99 source-code file as the sole argument (e.g. the last example from the OP):

```
> python3 ninetynine.py countdown.txt
G11G10G9G8G7G6G5G4G3G2G1G
>

```

As an added bonus, here's a (rather poor) implementation of "99 bottles" in *99*: http://pastebin.com/nczmzkFs
> 26 votes

# Answer
# Common Lisp, ~~1180~~ ~~857~~ ~~837~~ 836 bytes

I know this is not going to win, but I had fun golfing this one. I managed to remove 343 bytes, which is more than two *99* interpreters written in CJam.

Also, quite amusingly, the more I try to compress it, the more I am persuaded that for Common Lisp, it is *shorter* to compile the code than to try interpreting it on the fly.

```
(defmacro g(g &aux a(~ -1)> d x q(m 0)r v(n t)c(w 0)? u z)(flet((w(n p)(intern(format()"~a~a"p n))))(#1=tagbody %(case(setf c(ignore-errors(elt g(incf ~))))(#\  #2=(when(> w 0)(pushnew w v)(if u()(setq ?(oddp w)))(#5=push(w w'V)u)(setf w 0))(setf z t))(#\9(incf w)(setf >(or >(and n z))z()n()))((#\Newline())#2#(#5#(when u(setf u(reverse u)a(pop u))(if >(if u`(when(every'zerop(list,@u))(setf @,a)(go ^))`(setf,a,(if ?'(read)'(char-code(read-char)))))(if u`(setf,a,(do(p m)((not u)`(-(+,@p),@m))(#5#(pop u)p)(#5#(if u(pop u)0)m)))`(princ,(if ? a`(code-char(mod,a 128)))))))r)(incf m)(setf ?()u()z()>()n t)))(if c(go %))$(decf m)(setq d(pop r))(if d(#5# d x))(when(=(mod m 9)0)(#5#(w #3=(/ m 9)'L)x)(#5#`(,#3#(go,(w #3#'L)))q))(if(>= m 0)(go $)))`(let(@,@(mapcar(lambda(n)`(,(w n'V),(/(1-(expt 10 n))9)))v))(#1#,@x(go >)^(case @,@q)>))))

```
* lexical analysis and code generation are interleaved: I do not store the internal representation, but process directly each line.
* there is a single `tagbody` to perform 2 loops:

```
 (... (tagbody % ... (go %) $ ... (go $)) result)

```
* local variables are declared in `&aux`
* don't generate a closure, but directly the interpreted code
* etc.

# Ungolfed, commented

```
(defmacro parse-99
    (string &aux
              (~ -1) ; current position in string
              a      ; first variable in a line
              >      ; does current line starts with a leading space?
              d      ; holds a statement during code generation
              x      ; all statements (labels + expressions)
              q      ; all generated case statements
              (m 0)  ; count program lines (first increases, then decreases)
              r      ; list of parsed expressions (without labels)
              v      ; set of variables in program, as integers: 999 is 3
              (n t)  ; are we in a new line without having read a variable?
              c      ; current char in string
              (w 0)  ; currently parsed variable, as integer
              ?      ; is first variable odd?
              u      ; list of variables in current line, as integers
              z)     ; is the last read token a space?
  (flet((w(n p)
          ;; produce symbols for 99 variables
          ;; e.g. (10 'V) => 'V10
          ;;      (4 'L)  => 'L4
          (intern(format()"~a~a"p n))))
    (tagbody
     parse
       (case (setf c
                   ;; read current char in string,
                   ;; which can be NIL if out-of-bounds
                   (ignore-errors(aref string (incf ~))))

         ;; Space character
         (#\Space
          #2=(when(> w 0)
               (pushnew w v)            ; we were parsing a variable, add it to "v"
               (if u()(setq ?(oddp w))) ; if stack is empty, this is the first variable, determine if odd
               (push(w w'V)u)           ; add to stack of statement variable
               (setf w 0))              ; reset w for next variable

          ;; Space can either be significant (beginning of line,
          ;; preceding a variable), or not. We don't know yet.
          (setf z t))

         ;; Nine
         (#\9
          (incf w) ; increment count of nines
          (setf >(or >(and n z)) ; there is an indent if we were
                                 ; starting a newline and reading a
                                 ; space up to this variable (or if we
                                 ; already know that there is an
                                 ; indent in current line).
                ;; reset z and n
                z()n()))

         ;; Newline, or end of string
         ((#\Newline())
          #2#  ;; COPY-PASTE the above (when(> w 0)...) statement,
               ;; which adds previously read variable if necessary.

          ;; We can now convert the currently read line.
          ;; We push either NIL or a statement into variable R.

          (push(when u
                     (setf u (reverse u) ; we pushed, we must reverse
                           a (pop u))    ; a is the first element, u is popped
                     (if >
                         ;; STARTS WITH LEADING SPACE
                         (if u
                             ;; JUMP
                             `(when(every'zerop(list,@u))(setf @,a)(go ^))

                             ;; READ
                             `(setf,a,(if ?'(read)'(char-code(read-char)))))

                         ;; STARTS WITH VARIABLE
                         (if u

                             ;; ARITHMETIC
                             `(setf,a,(do(p m) ; declare p (plus) and m (minus) lists

                                         ;; stopping condition: u is empty
                                         ((not u)
                                          ;; returned value: (- (+ ....) ....)
                                          `(-(+,@p),@m))

                                        ;; alternatively push
                                        ;; variables in p and m, while
                                        ;; popping u

                                        (push(pop u)p)

                                        ;; first pop must succeed, but
                                        ;; not necessarly the second
                                        ;; one.  using a zero when u
                                        ;; is empty covers a lot of
                                        ;; corner cases.

                                        (push(if u (pop u) 0) m)))

                             ;; PRINT
                             `(princ,(if ? a`(code-char(mod,a 128)))))))
               r)
          ;; increase line count
          (incf m)
          ;; reset intermediate variables
          (setf ?()u()z()>()n t)))

       ;; loop until end of string
       (if c (go parse))

     build
       ;;; Now, we can add labels in generated code, for jumps

       ;; decrease line count M, which guards our second loop
       (decf m)

       ;; Take generated statement from R
       (setq d(pop r))

       ;; we pop from R and push in X, which means X will eventually
       ;; be in the correct sequence order. Here, we can safely
       ;; discard NIL statements.

       ;; We first push the expression, and THEN the label, so that
       ;; the label ends up being BEFORE the corresponding statement.
       (if d(push d x))

       ;; We can only jump into lines multiple of 9
       (when (=(mod m 9)0)
         ;; Push label
         (push(w #3=(/ m 9)'L)x)
         ;; Also, build a case statement for the jump table (e.g. 2(go L2))
         (push`(,#3#(go,(w #3#'L)))q))
       ;; loop
       (if(>= m 0)(go build)))

    ;; Finally, return the code
    `(let(@ ; target of a jump instruction

          ;; other variables: V3 represents 999 and has a default value of 111
          ,@(mapcar(lambda(n)`(,(w n'V),(/(1-(expt 10 n))9)))v))

       ;; build a tagbody, inject statements from X and case statements from Q
       ;; label ^ points to jump table : we go to ^ each time there is a JUMP
       ;; label > is the end of program

       ;; note that if the case does not match any authorized target
       ;; address, we simply end the programs.
       (tagbody,@x(go >)^(case @,@q)>))))

```

We use standard input/output during evaluation, meaning we use standard `read` and `princ` functions. Hence, the resulting code can be made executable on the command-line, as show below.

Inputs are not completely well sanitized when running *99* programs: it is assumed that the user knows what kind of values are expected.

The only possible *runtime* overhead can occur when jumping, since we must evaluate the value of a variable and match that value to a label. Except that, the interpreter shall be quite efficient.

Based on the clever obseravtion from Mac that we don't need to divide and multiply by 9 each time, the current version manages to **never** divides nor multiply by 9 during execution.

# Example

If we replace `defmacro` by `defun`, we see the generated code. For example:

```
(g
"99999999                                              Print G.
999 99                                                Set triple-nine to ninety-nine.
9999999999 9999999999 9999999999 99 99 9 9 999 999    Set 10-nine to zero.
99999999999 9999999999                                Set 11-nine to zero.

999                                                   Print triple-nine's value divided by nine. (This is the ninth line.)
99999999                                              Print G.
999 999 9                                             Subtract nine from triple-nine.
 99999 999                                            Jump to line 5-nines if triple-nine is zero (endsprogram).
 9 99999999999 9999999999                             Jump to line nine if 10-nine and 11-nine are zero (alwa

")

```

Here is the resulting code:

```
(LET (@
      (V5 11111)
      (V11 11111111111)
      (V1 1)
      (V10 1111111111)
      (V2 11)
      (V3 111)
      (V8 11111111))
  (TAGBODY
   L0
    (PRINC (CODE-CHAR (MOD V8 128)))
    (SETF V3 (- (+ V2) 0))
    (SETF V10 (- (+ V3 V1 V2 V10) V3 V1 V2 V10))
    (SETF V11 (- (+ V10) 0))
   L1
    (PRINC V3)
    (PRINC (CODE-CHAR (MOD V8 128)))
    (SETF V3 (- (+ V3) V1))
    (WHEN (EVERY 'ZEROP (LIST V3)) (SETF @ V5) (GO ^))
    (WHEN (EVERY 'ZEROP (LIST V11 V10)) (SETF @ V1) (GO ^))
    (GO >)
   ^
    (CASE @ (0 (GO L0)) (1 (GO L1)))
   >))

```

When executed, prints "G11G10G9G8G7G6G5G4G3G2G1G"

# Command-line

We can build an executable by dumping a core and specifying the `toplevel` function. Define a file named `boot.lisp` where you put the `defmacro`, and then write the following:

```
(defun main()(parse-99 <PROGRAM>))
(save-lisp-and-die "test-99" :executable t :toplevel #'main)

```

Running `sbcl --load boot.lisp` gives the following output:

```
$ sbcl --load boot.lisp
This is SBCL 1.2.8.32-18c2392, an implementation of ANSI Common Lisp.
More information about SBCL is available at <http://www.sbcl.org/>.

SBCL is free software, provided as is, with absolutely no warranty.
It is mostly in the public domain; some portions are provided under
BSD-style licenses.  See the CREDITS and COPYING files in the
distribution for more information.
[undoing binding stack and other enclosing state... done]
[saving current Lisp image into test-99:
writing 5824 bytes from the read-only space at 0x20000000
writing 3120 bytes from the static space at 0x20100000
writing 55771136 bytes from the dynamic space at 0x1000000000
done]

```

Then, running the compiled *99* program:

```
$ time ./test-99
G11G10G9G8G7G6G5G4G3G2G1G
real    0m0.009s
user    0m0.008s
sys     0m0.000s

```

# 99 bottles

If you are interested, here is the compiled code for the 99 bottles program written in Mac's answer: http://pastebin.com/ZXe839CZ (this is the old version where we have `jmp` and `end` labels, a surrounding lambda and prettier arithmetic).

Here is an execution with the new version, to prove it still works: http://pastebin.com/raw.php?i=h73q58FN
> 17 votes

# Answer
# TI-84 Basic (Calculator Script), 376 373 377 381 bytes

*If it runs on a TI-84 calculator, you'll be able to use it on a standardized test... so it's useful ;)*

Minimum operating system version - 2.53MP (MathPrint) due to the summation sigma

```
#Get input from STDIN
:Ans+":"->Str0
#Initialize instruction pointer
:1->I
#Initialize variable set
:DelVar L1999->dim(L1
#Strip out those pesky non-newline/space/9 characters
:For(J,1,length(Ans
:sub(Str0,J,1
:If not(inString(": 9",Ans
:sub(Str0,1,J-1)+sub(Str0,J+1,length(Str0)-J->Str0
:End
#Main interpreting loop
:While I<length(Str0
:sub(Str0,I+1,inString(Str0,":",I+1)-I-1->Str1
:DelVar A" "=sub(Ans,1,1->A
:inString(Str0,":",I+1->I
:If A
:sub(Str1,2,length(Str1)-1->Str1
:End
:length(Str1->L
#0 is Output, 1 is Input, 2 is Assignment, 3 is Goto
:2A+inString(Str1," ->B
:If not(Ans
:Disp L1(L
:If Ans=1
:Then
:Input C
:C->L1(L
:End
#Get those delimited variables
:If B>1
:Then
:"{"+Str1->Str2
:While inString(Ans,"
:inString(Ans,"
:sub(Str2,1,Ans-1)+sub(Str2,Ans+1,length(Str2)-Ans->Str2
:End
:log(expr(Ans)+1->L2
:End
:If B=2
#Gotta expand that -+ pattern
:Ans(2->L1(Ans(1
;Love that summation Σ
:If B=3 and Σ(L2(K),K,2,dim(L2
:Then
:DelVar IFor(K,0,9L2(1
:inString(Str0,":",I+1->I
:End
:End

```

P.S. ASCII guidelines could not be followed exactly, but in TI-Basic `:` is a newline. Thus, all the actual newlines in the code mean that the `:` or `#` at the beginning of each line are not required. The beginning tokens `:` and `#` just differentiate between comments and code.

**Original Hex Dump (376 Bytes)**

```
49 3f bb 54 5d 20 39 39 39 04 b5 5d 20 3f 72 04 aa 09 3f d3 4a 2b 31 2b bb 2b 72 3f bb 0c aa 09 2b 4a 2b 31 3f ce b8 bb 0f 2a 3e 29 39 2a 2b 72 3f bb 0c aa 09 2b 31 2b 4a 71 31 11 70 bb 0c aa 09 2b 4a 70 31 2b 72 71 4a 04 aa 09 3f d4 3f d1 49 6b bb 2b aa 09 3f bb 0c aa 09 2b 49 70 31 2b bb 0f aa 09 2b 2a 3e 2a 2b 49 70 31 11 71 49 71 31 04 aa 20 3f bb 54 41 2a 29 2a 6a bb 0c 72 2b 31 2b 31 04 41 3f bb 0f aa 09 2b 2a 3e 2a 2b 49 70 31 04 49 3f ce 41 3f bb 0c aa 20 2b 32 2b bb 2b aa 20 11 71 31 04 aa 20 3f d4 3f bb 2b aa 20 04 4c 3f 32 41 70 bb 0f aa 20 2b 2a 29 04 42 3f ce b8 72 3f de 5d 20 10 4c 11 83 39 3f ce 72 6a 31 3f cf 3f dc 43 3f 39 43 04 5d 20 10 4c 3f d4 3f ce 42 6c 31 3f cf 3f 2a 08 2a 70 aa 20 04 aa 01 3f d1 bb 0f 72 2b 2a 29 3f bb 0f 72 2b 2a 29 3f bb 0c aa 01 2b 31 2b 72 71 31 11 70 bb 0c aa 01 2b 72 70 31 2b bb 2b aa 01 11 71 72 04 aa 01 3f d4 3f c0 bb 2a 72 11 70 31 04 5d 01 3f d4 3f ce 42 6a 32 3f 72 10 32 04 5d 20 10 72 10 31 3f ce 42 6a 33 40 ef 33 5d 01 10 4b 11 2b 4b 2b 32 2b b5 5d 01 3f cf 3f bb 54 49 d3 4b 2b 30 2b 5d 01 10 31 3f bb 0f aa 09 2b 2a 3e 2a 2b 49 70 31 04 49 3f d4 3f d4 2e 76

```

**Edit #1** \- Optimized 3 bytes using Mac's observation **Edits #2 & #3** \- Fixed bugs spotted by Runer112.
> 6 votes

# Answer
# C 426 ~~458 481 497~~

**Edit** Maybe I'm going too far, but this works with Visual C: removed stdio.h, using int instead of FILE\* for fopen and getc

**Edit 2** Reorder execution step, more clutter, 32 chars saved

```
B[99999],*r,*i[9999],V[999],v,w,m,n;unsigned p,s;
main(b,a)char*a[];{r=i[0]=B;m=fopen(a[1],"r");
do if(w=getc(m),n+=w==57,w<33){
if(n){for(v=1,b=n;--b;)v=v*10+1;V[n]=v;*r++=p?-n:n;b=n=0;};
w-32?(*r=p=0,b=i[++s]=++r):(p=b,b=0);}while(w>=0);
while(p<s)if(w=0,r=i[p++],v=*r++)
if(m=v>0,*r){for(;b=*r++;m=-m)w=w+m*V[b]|!m*V[b];m?V[v]=w:(p=w?p:9*V[-v]);
}else~v&1?!m?V[-v]=getchar():putchar(V[v]&127):m?printf("%d",V[v]):scanf("%d",V-v);
}

```

Stand alone console program, program name taken on command line and input/output via console.

Old style K&R, default type int for global vars and parameters. Assuming EOF defined as -1 (as it is in every C implementation I'm aware of)

Compiles with warnings with Visual Studio 2010 (Win32 console C++ project, compile as C) Compiles on Ideone, but can't run as it needs a file.

First step, the source code is read and parsed, each line is stored as a sequence of integers based on the numbers of 9s. If there is a leading blank, the first number is negative. So:  `9 BLAH 99 9a9bb9c9` ( `9 99 9999`) becomes `-1,2,4` There is a shortcut - not so legal : all ascii codes less than ' ' are considered newlines.

In this step all the used variable are preinitialised.

The execution step follows the specifications, no frills, save storing numbers divided by 9.

**More readable** same code (I hope), spaces and newlines added

```
B[99999],*r,*i[9999],V[999],v,w,m,n;
unsigned p,s;
main(b,a)char*a[];
{
  r=i[0]=B;
  m=fopen(a[1],"r");
  do if(w=getc(m),n+=w==57,w<33)
  {
     if(n){for(v=1,b=n;--b;)v=v*10+1;V[n]=v;*r++=p?-n:n;b=n=0;};
     w-32?(*r=p=0,b=i[++s]=++r):(p=b,b=0);
  }
  while (w>=0);
  while (p<s)
    if (w = 0, r = i[p++], v = *r++)
        if (m = v > 0, *r){
            for(; b = *r++; m = -m)
                w = w + m*V[b] | !m*V[b];
            m ? V[v]=w : (p = w ? p : 9*V[-v]);
        } else
            ~v & 1
            ? !m ? V[-v] = getchar() : putchar(V[v] & 127)
            : m ? printf("%d", V[v]) : scanf("%d", V - v);
}

```
> 6 votes

# Answer
# Haskell, 550 bytes

```
import Data.List.Split
import System.Environment
a#b=takeWhile(/=a)b
(!)=map
main=do(f:_)<-getArgs;readFile f>>=e.(p!).lines
p l=(if ' '#l<'9'#l then[0]else[])++length!(wordsBy(/='9')l)
e l=(\x->div(10^x-1)9)%l where
 _%[]=return()
 v%([]:r)=v%r
 v%([n]:r)=putStr(if odd n then show(v n)else[toEnum$v n`mod`128])>>v%r
 v%([0,n]:r)=do i<-getLine;u n(if odd n then read i else fromEnum$head i)v%r
 v%((0:n:m):r)|any(/=0)(v!m)=v%r|v n<0=v%[]|1<2=v%drop(9*v n)l
 v%((n:m):r)=u n(sum$zipWith(*)(v!m)(cycle[1,-1]))v%r
u n i v= \x->if x==n then i else v x

```

Example run with the "countdown" program stored in the file `i.99`

```
$ ./99 i.99
G11G10G9G8G7G6G5G4G3G2G1G

```

Ungolfed version:

```
import Data.List.Split
import System.Environment

-- The main function takes the first command line argument as a file name,
-- reads the content, splits it into lines, parses each line and evaluates
-- the list of parsed lines.
main = do
 (f:_)<-getArgs
 readFile f >>= eval.map parse.lines

-- each line is coverted into a list of integers, which represent the number
-- of 9s (e.g. "999 99 9999" -> [3,2,4]). If there's a space before the first
-- 9, a 0 is put in front of the list (e.g. " 9 9 999" -> [0,1,1,3]).
parse l = (if takeWhile (/=' ') l < takeWhile (/='9') l then [0] else [])
   ++ map length (wordsBy(/='9') l)

-- The work is done by the helper function 'go', which takes two arguments
--   a) a functions which takes an integer i and returns the value of the
--      variable with i 9s (e.g: input: 4, output: value of 9999). To be
--      exact, the value divided by 9 is returned.
--   b) a list of lines to work on
-- 'eval' starts the process with a function that returns i 1s for every i and
-- the list of the parsed input. 'go' checks which statement has to be
-- executed for the next line and calls itself recursively
eval list = go (\x -> div (10^x-1) 9) list
   where
   go _ []                  = return ()
   go v ([]:r)              = go v r
   go v ([n]:r)             = putStr (if odd n then show(v n) else [toEnum (v n`mod`128)]) >> go v r
   go v ([0,n]:r)           = do i<-getLine ; go (update n (if odd n then read i else fromEnum$head i) v) r
   go v ((0:n:m):r)
      | any (/=0) (map v m) = go v r
      | v n < 0             = go v []
      | otherwise           = go v (drop (9*v n) list)
   go v ((n:m):r)           = go (update n (sum $ zipWith (*) (map v m) (cycle[1,-1])) v) r

-- updates a function for retrieving variable values.
-- n = position to update
-- i = new value
-- v = the function to update
update n i v = \x->if x==n then i else v x

```
> 5 votes

# Answer
# q/k, 490 469

```
M:mod;T:trim;R:read0;S:set;s:" "
f:(rtrim')(f:R -1!`$.z.x 0)inter\:"9 \n"
k)m:{@[x;&M[!#x;2];-:]}
b:{}
k)p:{1@$$[1=M[#x;2];(K x)%9;"c"$M[(K x)%9;128]];}
k)i:{S[(`$T x);$[1=M[#T x;2];9*"J"$R 0;*9*"i"$R 0]]}
k)K:{$[#!:a:`$x;.:a;"I"$x]}
k)v:{(S).(`$*:;+/m@K'1_)@\:T's\:x}
k)g:{$[&/0=C:K'c:1_J:s\:T x;n::-1+K@*J;|/~0=C;;(d<0)|(d:*C)<#f;exit 0]}
k)r:{`b`p`i`v`g@*&(&/x=s;q&1=c;(e~s)&1=C;(q:e~"9")&1<c:#s\:x;((e:*x)~s)&1<C:#s\:1_x)}
k)n:0;while[~n>#o:(r')f;(o n)f n;n+:1]
\\

```

.

```
$ q 99.q countdown.txt -q
G11G10G9G8G7G6G5G4G3G2G1G

```

The script is a mixture of q and k, so first up I define a few q keywords that I want to use multiple times in k functions. (basically #define macros)

```
M:mod;T:trim;R:read0;S:set

```

`f` reads the file passed into the program and strips out unnecessary characters

```
q)f
"99999999"
"999 99"
"9999999999 9999999999 9999999999 99 99 9 9 999 999"
"99999999999 9999999999"
""
""
""
""
""
"999"
"99999999"
"999 999 9"
" 99999 999"
" 9 99999999999 9999999999"

```

`m` takes a list/vector and multiples the odd indices by -1

```
q)m 1 2 3 4 5
1 -2 3 -4 5

```

`b` is just an empty function, used for the no-op lines

`p` is the print function.

`K` is a function that examines a variable. If the variable exists, it returns it, otherwise it just returns the literal.

```
//999 not defined, so just return 999
q)K "999"
999
//Set 999 to 9
q)v "999 9"
//K now returns 9
q)K "999"
9

```

`v` is the assignment function.

`g` is the goto function.

`r` takes a string and decides which operation needs to be applied.

And then finally, I just iterate through the `f` list of strings, with `n` as the iterator. The goto function will update `n` as necessary.
> 4 votes

# Answer
# JavaScript (ES6) 340 ~~352~~

A function with 2 parameters

* program code as a multiline string
* input as an array

The third optional parameter (default 10k) is the max number of iterations - I don't like a program that run forever

JSFiddle To test

```
I=(c,i,k=1e5,
  V=v=>v in V?V[v]:v/9 // variable getter with default initial value
)=>(c=>{
 for(p=o='';--k&&p<c[L='length'];)
   (v=(r=c[p++].split(' '))[S='shift']())? // no leading space
      r[r.map(t=>w-=(m=-m)*V(t),w=0,m=1),0]?V[v]=w // Assign
      :o+=v[L]&1?V(v):String.fromCharCode(V(v)&127) // Output
   : // else, leading space
    (v=r[S]())&&
       (r[0]?r.some(t=>V(t))?0:p=9*V(v) // Goto
       :(t=i[S](),V[v]=v[L]&1?t:t.charCodeAt()) // Input
    )
})(c.replace(/ (?=[^9])|[^9\s]/g,'').split('\n'))  // code cleaning
||o

```
> 4 votes

# Answer
# Perl, ~~273 266 255 244~~ 238

Line breaks added for clarity.

```
open A,pop;
for(@c=<A>){
y/ 9//cd;s/ +/ /g;s/ $//;
$p="((99)+|9+)";$a='+';
s/^ $p$/$1='$2'?ord<>:<>/;
s/^$p$/print'$2'?chr$1%128:$1/;
s/^ $p /\$_=$1*011unless/&&y/ /|/;
s/ /=/;s/ /$a=-$a/ge;
s!9+!${x.$&}=$&/9;"\$x$&"!eg}
eval$c[$_++]until/-/|$_>@c

```

Program name taken on command line:

```
$ perl 99.pl 99beers.99

```

Each line of the program is converted into Perl code, for example:

```
print'$x99'?chr$x99999999%128:$x99999999
$x999=$x99
$x9999999999=$x9999999999-$x9999999999+$x99-$x99+$x9-$x9+$x999-$x999
$x99999999999=$x9999999999

print''?chr$x999%128:$x999
print'$x99'?chr$x99999999%128:$x99999999
$x999=$x999-$x9
$_=$x99999*011unless$x999
$_=$x9*011unless$x99999999999|$x9999999999

```

More details

```
open A,pop; # open the source file
for(@c=<A>){ # read all lines into @c and iterate over them
y/ 9//cd; # remove all but spaces and 9's
s/ +/ /g;s/ $//; # remove duplicate and trailing spaces
$p="((99)+|9+)";$a='+';
s/^ $p$/$1='$2'?ord<>:<>/; # convert input
s/^$p$/print'$2'?chr$1%128:$1/; # convert output
s/^ $p /\$_=$1*011unless/&&y/ /|/; # convert goto
s/ /=/;s/ /$a=-$a/ge; # convert assignment
s!9+!${x.$&}=$&/9;"\$x$&"!eg} # initialize and convert variables
eval$c[$_++]until/-/|$_>@c # run (program counter is in $_)

```
> 3 votes

---
Tags: code-golf, interpreter
---


title: Count Maximal Fence Arrangements

text:
# Question
Title: Count Maximal Fence Arrangements
# Background

I want to build a fence. For that, I have collected a bunch of poles, and stuck them to the ground. I have also collected lots of boards that I'll nail to the poles to make the actual fence. I tend to get carried away when building stuff, and most likely I'll just keep nailing the boards to the poles until there's no more place to put them. I want you to enumerate the possible fences that I can end up with.

# Input

Your input is a list of two-dimensional integer coordinates representing the positions of the poles, in any convenient format. You can assume that it contains no duplicates, but you cannot assume anything about its order.

The boards are represented by straight lines between the poles, and for simplicity, we only consider horizontal and vertical boards. Two poles can be joined by a board if there are no other poles or boards between them, meaning that the boards cannot cross each other. An arrangement of poles and boards is *maximal* if no new boards can be added to it (equivalently, there is either a pole or a board between any two horizontally or vertically aligned poles).

# Output

Your output is the number of maximal arrangements that can be constructed using the poles.

# Example

Consider the input list

```
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)]

```

Viewed from the top, the corresponding arrangement of poles looks something like this:

```
  o
 o o
o    o
 o o
  o

```

There are exactly three maximal arrangements that can be constructed using these poles:

```
  o        o        o
 o-o      o|o      o-o
o----o   o||| o   o| | o
 o-o      o|o      o-o
  o        o        o

```

Thus the correct output is `3`.

# Rules

You can write either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

```
[] -> 1
[(0,0),(1,1),(2,2)] -> 1
[(0,0),(1,0),(2,0)] -> 1
[(0,0),(0,1),(1,0),(1,1)] -> 1
[(1,0),(0,1),(-1,0),(0,-1)] -> 2
[(3,0),(1,1),(0,2),(-1,1),(-2,0),(-1,-1),(0,-2),(1,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1)] -> 3
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1)] -> 4
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(0,-1),(2,2)] -> 5
[(0,0),(4,0),(1,1),(1,-2),(3,1),(3,-2),(2,-1),(4,-1),(0,-1),(2,2)] -> 8

```

# Answer
> 5 votes
# Mathematica, 301 bytes

```
(t~SetAttributes~Orderless;u=Subsets;c=Complement;l=Select;f=FreeQ;Count[s=List@@@l[t@@@u[Sort@l[Sort/@#~u~{2},!f[#-#2&@@#,0]&]//.{a___,{x_,y_},{x_,z_},b___,{y_,z_},c___}:>{a,{x,y},b,{y,z},c}],f[#,t[{{a_,b_},{a_,c_}},{{d_,e_},{f_,e_}},___]/;d<a<f&&b<e<c]&],l_/;f[s,k_List/;k~c~l!={}&&l~c~k=={},{1}]])&

```

This is an unnamed function which takes the coordinates as a nested `List` and returns an integer. That is, you can either give it a name and call it, or just append

```
@ {{3, 0}, {1, 1}, {0, 2}, {-1, 1}, {-2, 0}, {-1, -1}, {0, -2}, {1, -1}}

```

With indentation:

```
(
  t~SetAttributes~Orderless;
  u = Subsets;
  c = Complement;
  l = Select;
  f = FreeQ;
  Count[
    s = List @@@ l[
      t @@@ u[
        Sort @ l[
          Sort /@ #~u~{2},
          !f[# - #2 & @@ #, 0] &
        ] //. {a___, {x_, y_}, {x_, z_}, b___, {y_, z_}, c___} :>
              {a, {x, y}, b, {y, z}, c}
      ],
      f[
        #,
        t[{{a_, b_}, {a_, c_}}, {{d_, e_}, {f_, e_}}, ___]
          /; d < a < f && b < e < c
      ] &
    ],
    l_ /; f[
      s,
      k_List /; k~c~l != {} && l~c~k == {},
      {1}
    ]
  ]
) &

```

I can't even begin to express how naive this implementation is... it definitely couldn't be more brute force...

* Get all (unordered) pairs of poles.
* Sort each pair and all pairs into a canonical order.
* Discard pairs which don't share one coordinate (i.e. which aren't connectible by an orthogonal line).
* Discard pairs can be formed from two shorter pairs (so that `o--o--o` yields only two fences instead of three).
* Get all subsets of those pairs - i.e. all possible combinations of fences.
* Filter out combinations which have fences crossing each other.
* Count the number of resulting fence sets for which no strict superset can be found in the list.

Surprisingly it does solve all the test cases virtually immediately.

A really neat trick I discovered for this is the use of `Orderless` to cut down on the number of patterns I have to match. Essentially, when I want to ditch fence sets with crossing fences, I need to find a pair of vertical and horizontal fence and check the condition on them. But I don't know what order they'll appear in. Since list patterns are normally order dependent, this would result in two really long patterns. So instead I replace with surrounding list with a function `t` with `t @@@` \- which isn't defined so it is held as it is. But that function is `Orderless`, so I *can* just check a single order in the pattern, and Mathematica will check it against all permutations. Afterwards, I put the lists back in place with `List @@@`.

I wish there was a built-in that is a) `Orderless`, b) *not* `Listable` and c) not defined for 0 arguments or list arguments. Then I could replace `t` by that. But there doesn't seem to be such an operator.

# Answer
> 1 votes
# Haskell, 318 bytes

```
import Data.List
s=subsequences
k[(_,a,b),(_,c,d)]|a==c=f(\w->(1,a,w))b d|1<2=f(\w->(2,w,b))a c
f t u v=[t x|x<-[min u v+1..max u v-1]]
q l=nub[x|x<-map(k=<<)$s[a|a@[(_,n,m),(_,o,p)]<-s l,n==o||m==p],x++l==nubBy(\(_,a,b)(_,c,d)->a==c&&b==d)(x++l)]
m=q.map(\(a,b)->(0,a,b))
p l=sum[1|x<-m l,all(\y->y==x||x\\y/=[])$m l]

```

Usage: `p [(1,0),(0,1),(-1,0),(0,-1)]`. Output: `2`

How it works:

* create all sublists of the input list and keep those with two elements and with either equal x or equal y coordinates. This is a list of all pairs of poles where a fence can be build in between.
* create all sublists of it
* add boards for every list
* remove lists where a x-y coordinate appears twice (boards and poles)
* remove duplicate lists (boards only) to handle multiple empty lists, because of directly adjacent poles (e.g. (1,0) and (1,1))
* keep those which are not a strict sublist of another list
* count remaining lists

---
Tags: code-golf, combinatorics, graph-theory
---


title: Write a GIF encoder

text:
# Question
Title: Write a GIF encoder
Yes, the good old GIF. Loved for its versatility, hated for its patents and partly obsoleted due to its limitations (and patents), GIF consists, at the core, of a color palette and a palette-indexed image compressed using the LZW algorithm.

Your task is to write a program that reads an image in ASCII PPM format ("P3" magic number) from the standard input, and writes the same image (identical pixel-by-pixel) in GIF format to the standard output. The output can either be in binary form, or ASCII text with each byte represented by a number between 0 and 255 (inclusive), separated by whitespace.

The input image is guaranteed not to have more than 256 different colors.

**Scoring:**

Your program will be tested on 3 sample images, and your score will be calculated as:
*program size + sum(output size - reference size for each sample image)*
Lowest score wins.

**Requirements:**

* Your program must work with any similar kinds of images of various sizes, and not be limited to the sample images. You could, for example, restrict the dimensions to be multiples of 2 or assume that the ppm max color is 255, but it should still work with a wide variety of input images.
* The output must be a valid GIF file that can be loaded with any compliant program (after converting back to binary if using the ASCII output option).
* You can not use any image processing functions (built-in or third-party), your program must contain all the relevant code.
* Your program must be runnable in Linux using freely available software.
* The source code must use only ASCII characters.

**Sample images:**

Here are the 3 sample images that will be used for scoring. You can download a zip archive with the ppm files (use the download button on the top of that page). Or you can convert them from the png images below, using ImageMagick with the following command:

```
convert file.png -compress none file.ppm

```

I am also providing the MD5 checksums of the ppm files for confirmation.

**1. amber**

Reference size: 38055
MD5 checksum of ppm: d1ad863cb556869332074717eb278080

**2. blueeyes**

Reference size: 28638
MD5 checksum of ppm: e9ad410057a5f6c25a22a534259dcf3a

**3. peppers**

Reference size: 53586
MD5 checksum of ppm: 74112dbdbb8b7de5216f9e24c2e1a627

# Answer
# Perl, 515 + -2922 + 0 + -2571 = -4978

Another approach. This time I am trying to save the image in tiles of size 64xH. This is fine according to specs, but some software may show only the first tile or an animation. The tiles compress better because of better spacial locality. I still do normal compression as well for the second image and choose whatever came shorter. Since this compresses the image twice, it is twice as slow compared to my previous solution.

```
#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@l=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
print+GIF89a,pack(vvCxxC768,@k,~8,@t);
sub v{($w,$h)=@_;for$k(0.."@k"/$w-1){
$k*=$w;$r='';@d=();@p=grep+($z++-$k)%"@k"<$w,@l;
$"=' ';$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
$h.=pack"Cv4n(C/a)*",44,$k,0,$w,$k[1],8,/.{0,255}/gs
}$b=$h if!$b||length$b>length$h}
"@k"%64||v 64;v"@k";print"$b;"

```

# Perl, 354 + 12 + 0 + -1 = 365 ~~418 9521 51168 56639~~

Either there is some bug in my code or the second image is optimized for a specific encoder as seemingly insignificant change reduced the size to the reference exactly. Takes about 30s-60s per image.

Golfed version.

```
#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

```

The only decision a GIF compressor can take is when to reset the LZW dictionary. In general because of how the images for this task were chosen the best moment to do so is each 4096 codes which is the moment the dictionary would overflow. With such limit the dictionary never overflows which saves a couple of bytes in the implementation. This is how it works in detail:

```
#!perl -n0
# function to add one codeword to the output stream @r.
# the current codeword length is based on the dictionary size/
sub r{push@r,map"@_">>$_,0..log(@d|256)/log 2}
# get the dimensions into @k
@k=/(\d+) (\d+)/;
# get pixel indexes to @p and palette to @t
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
# convert index table into space separated string
$_="@p ";$"='|';
# LZW encoder; while something to encode
while(/\S/){
# output reset code
r 256;
# reset code dictionary $d is the last code number,
# %d is the map of codes and @d list of codes
$d=257;%d=map{($_,$_-1)}@d=1..256;
# find codes using regexp, stop at dictionary overflow
while($d<4096&&s/^(@d) (\d*)/$2/){
unshift@d,$&;$d{$&}=++$d;r$d{$1}}}
# end LZW encoder; output end code
r 257;
# convert bit string @r to bytes $f
vec($f,$j++,1)=$_ for@r;
# output header up to the color table
print+GIF89a,pack(vvCvC768,@k,~8,0,@t),
# output rest of the header
pack(Cv4CC,44,0,0,@k,0,8),
# output the LZW compressed data $f slicing into sub-blocks
$f=~s/.{0,255}/chr(length$&).$&/egsr,';'

```

# Perl, 394 + -8 + 0 + -12 = 374

Adding a heuristic to guess the reset point improves compression a bit but not enough to justify the extra code:

```
#!perl -n0
sub r{$r.=1&"@_">>$_ for 0..log(@d|256)/log 2}
@k=/(\d+) (\d+)/;
@p=map{$$_||=(push(@t,split$"),++$i)}/\d+ \d+ \d+/g;
$_="@p ";$"='|';while(/./){
r 256;%d=map{($_,$_-1)}@d=1..256;
$d{$&}=@d+2,r$d{$1},unshift@d,$&while
(@d<4001||(/((@d) ){11}/,$&=~y/ //>12))&@d<4095&&s/^(@d) (\d*)/$2/}
r 257;$_=pack"b*",$r;
print+GIF89a,pack(vvCxxC768,@k,~8,@t),
pack("Cx4vvn(C/a)*",44,@k,8,/.{0,255}/gs),';'

```
> 4 votes

# Answer
# CJam, score 155 + 35306 + 44723 + 21518 = 101702

Just a dumb reference implementation. It's slow, doesn't do any actual compression and it's not golfed.

```
"GIF89a":iS*SqN/S*S%1>:i3/:M0=2<256f{md\}S*:ZS247S0S0SM1>_|:PL*_,768\m0a*+S*S44S0S0S0S0SZS0S8SM1>Pf{\a#}254/256a*{512+2b1>W%}%:+8/{W%2b}%255/{_,S@S*S}/0S59

```
> 2 votes

---
Tags: code-golf, image-processing, compression
---