title: Where should I put my restaurant?

text:
# Question
Title: Where should I put my restaurant?
You are the owner of a restaurant. You are opening in a new area in Cartesia where there is only one main road, known as the y-axis. You want to place your restaurant such that you minimize the total distance from your restaurant and each of the houses in that area.

**Input**:

The input will be

```
n, the number of houses
house1
house2
house3
...
houseN

```

where each house is a coordinate in the form `x y`. Each unit represents one kilometer.

You can take input as a string or provide a function that takes the input, in whatever format you choose, as its arguments.

**Output**: The y-coordinate of your restaurant (remember, it will be located on the y-axis). Actually, it will be located on the side of the road, but the difference is negligible.

Essentially, if nth house is `h_n` and `D` is the distance function, then you want to find `k` such that `D(h_0, (0, k)) + D(h_1, (0, k)) + D(h_2, (0, k)) + ... + D(h_n, (0, k))` is minimized.

Note that distance is calculated as though the customer travels in an exactly straight line from their house to the restaurant. That is the distance from `(x, y)` to your restaurant is `sqrt(x^2 + (y - k)^2)`.

The output should be accurate to at least 2 decimal places.

Output can be printed as a string or can be returned from the function.

Example input/output:

```
Input:
2
5.7 3.2
8.9 8.1
Output:
5.113013698630137

```

The total distance in this example is about `15.4003` kilometers.

This is code golf -- shortest code wins.

P.S. I'm also interested in a mathematical solution that isn't just brute force. It won't win the code golf but it'll get some upvotes. Here is how I did the example problem:

Let point A be located at A(5.7, 3.2) and B at B(8.9, 8.1). Let the solution point at (0, k) be C. Reflect A over the y-axis to make A' at (-5.7, 3.2). The distance from A' to C is equal to the distance from A to C. Therefore, the problem can be reduced to the point C such that A'C + CB is minimized. Obviously, this would be the point C that lies on the line A'B.

I don't know if this would generalize well to 3 or more points.

# Answer
> 27 votes
# C, ~~315~~ 302 bytes

```
t,i;double o,w,h,x,y,k,a,b,c;double g(N,S)double N,S[][2];{for(t=0;t<N;t++)k+=S[t][1];k/=N;for(i=0;i<9;i++){o=w=h=0;for(t=0;t<N;t++)x=S[t][0],y=S[t][1],a=y-k,c=k*k-2*k*y+x*x+y*y,o+=-a/sqrt(x*x+a*a),w+=x*x/pow(c,1.5),h+=3*x*x*a/pow(c,2.5);a=h/2;b=w-h*k;c=o-w*k+a*k*k;k=(-b+sqrt(b*b-4*a*c))/h;}return k;}

```

This is far from pretty, and it's not short either. I figured since I'm not going to win the length contest, I can try to win the (theoretical) accuracy contest! The code is probably an order of magnitude or two faster than the bruteforce solution, and relies on a bit of mathematical tomfoolery.

We define a function `g(N,S)` which takes as input the number of houses, `N`, and an array of houses `S[][2]`.

Here it is unraveled, with a test case:

```
t,i;
double o,w,h,x,y,k,a,b,c;
double g(N,S)double N,S[][2];{
    /* Initially, let k hold the geometric mean of given y-values */
    for(t=0;t<N;t++)
        k+=S[t][1];
    k/=N;

    /* We approximate 9 times to ensure accuracy */
    for(i=0;i<9;i++){
        o=w=h=0;
        for(t=0;t<N;t++)
            /* Here, we are making running totals of partial derivatives */
            /* o is the first, w the second, and h the third*/
            x=S[t][0],
            y=S[t][1],
            a=y-k,
            c=k*k-2*k*y+x*x+y*y,
            o+=-a/sqrt(x*x+a*a),
            w+=x*x/pow(c,1.5),
            h+=3*x*x*a/pow(c,2.5);
        /* We now use these derivatives to find a (hopefully) closer k */
        a=h/2;
        b=w-h*k;
        c=o-w*k+a*k*k;
        k=(-b+sqrt(b*b-4*a*c))/h;
    }
    return k;
}
/* Our testing code */
int main(int argc, char** argv) {
    double test[2][2] = {
        {5.7, 3.2},
        {8.9, 8.1}
    };
    printf("%.20lf\n", g(2, test));
    return 0;
}

```

Which outputs:

```
5.11301369863013732697

```

**Warning: Knowledge of some calculus may be required for a complete understanding!**

So, let's talk about the math.

We know the distance from our desired point `(0, k)` and a house `i`:

And thus the total distance `D` from `n` houses can be defined as follows:

What we would like to do is minimize this function by taking a derivative with respect to `k` and setting it equal to `0`. Let's try it. We know that the derivatives of `D` can be described as follows:

But the first partial derivative of each `Di` is pretty bad...

Unfortunately, even with `n == 2`, setting these derivatives to `0` and solving for `k` becomes disastrous very quickly. We need a more robust method, even if it requires some approximation.

*Enter Taylor Polynomials.*

If we know the value of `D(k0)` as well as all of `D`'s derivatives at `k0`, we can rewrite `D` as a Taylor Series:

Now, this formula's got a bunch of stuff in it, and its derivatives can get pretty unwieldy, *but we now have a polynomial approximation of* `D`!

Doing a little bit of calculus, we find the next two derivatives of `D` by evaluating the derivatives of `Di`, just as before:

By truncation and evaluating the derivatives, we may now approximate `D` as a 3rd degree polynomial of the form:

Where `A, B, C, D` are simply real numbers.

Now *this* we can minimize. When we take a derivative and set it equal to 0, we will end up with an equation of the form:

Doing the calculus and substitutions, we come up with these formulas for `a, b, and c`:

Now our problem gives us 2 solutions given by the quadratic formula:

The entire formula for `k` would be a massive burden to write out, so we do it in pieces here and in the code.

Since we know that the higher `k` will always result in the minimum distance of our approximate `D` (I have a truly marvelous proof of this, which the margin of this paper is insufficient to contain...) we do not even have to consider the smaller of the solutions.

One final problem remains. For accuracy purposes, it is necessary that we begin with a `k0` that is at least in the ballpark of where we expect the answer to be. For this purpose, my code chooses the geometric mean of the y-values of every house.

As a fail-safe, we repeat the entire problem again 9 times, replacing `k0` with `k` at every iteration, to ensure accuracy.

I haven't done the math about how many iterations and how many derivatives are truly necessary, but I've opted to err on the side of caution until I can confirm accuracy.

If you made it through that with me, thank you so much! I hope you understood, and if you spot any mistakes (of which there are likely many, I'm very tired), please let me know!

# Answer
> 13 votes
# TI-BASIC, 20

```
fMin(sum(abs(iX-Ans)),X,~E99,E99

```

Takes input on the homescreen of your TI-83 or 84 series calculator in this form (You can type a `2:` first, which would be ignored):

```
{5.7+3.2i,8.9+8.1i}:[program name]

```

If the houses are always less than a billion km away from the origin, E99 can be replaced with E9 for a size of 18 bytes.

Were there a golfing language based on Mathematica, it could win this challenge in 10-14 bytes.

# Answer
> 10 votes
# Mathematica, 42 bytes

```
k/.Last@Minimize[Tr[Norm[#-{0,k}]&/@#],k]&

```

This is an anonymous function taking a list of pairs as the house coordinates and returning the desired y coordinate.

It's a fairly straightforward implementation. We map `Norm[#-{0,k}]&` onto each house coordinate (which computes the distance to an undetermined point `{0,k}` on the y axis) and sum them all up with `Tr[...]` (for trace, which is equivalent to `Total` for 1-d lists). Then we use the convenient `Minimize` to find the minimum of this sum in `k`. This gives a result of the form `{distance, {k -> position}`, so we need `k/.Last@` to extract the `position` we're looking for.

# Answer
> 6 votes
# Pyth, 33 bytes

```
hosm.a,d,0NQcR^T3rhKSms*^T3ekQheK

```

This is the brute force solution: It orders all possible locations of the restaurant, with a resolution of .001 km, by their total distance from the houses, then selects the one with the least total distance. It takes the house locations as a list of 2 entry lists of floats on STDIN.

Demonstration.

The resolution could be set anywhere from 1e-2 km to 1e-10 km at the same code length, but with exponential slowdowns in runtime.

I feel like this could be golfed some more, I'll look at it again later.

# Answer
> 3 votes
# Python 2, 312

```
from math import*;A,L,p=[map(float,raw_input().split()) for i in range(input())],lambda a:a[1],0.001
def R(m,M,s):
 while m<=M:yield m;m+=s
m=min(A,key=L)[1];M=max(A,key=L)[1];r=(m+M)/2;s=r-m
while s>p:D={y:sum([sqrt(X*X+(Y-y)**2)for X,Y in A])for y in R(r-s,r+s,s*p)};r=min(D,key=D.get);s*=p;m=r-s;M=r+s
print r

```

# Answer
> 3 votes
# R, ~~145~~ ~~143~~ 126

Lots of golfing room left on this I suspect. Pretty much a brute force method. I would like to find a nicer way to do this. I though Geometric Means might help, but alas no.

```
r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]

```

**Test run**

```
> r=sapply(seq(min((p=matrix(scan(),nr=2))),max(p),.001),function(X,p)c(X,sum((p[1,]^2+(p[2,]-X)^2)^.5)),p);r[1,order(r[2,])[1]]
1: 5.7 3.2
3: 8.9 8.1
5:
Read 4 items
[1] 5.113
>

```

As a matter of interest, if there is just two houses to consider the following will return an acceptable result. However it falls over on three. I can't take it any further at the moment, but I thought some of the brains here might be able to do something with it.

```
p=matrix(scan(),nr=2);weighted.mean(p[2,],sum(p[1,])-p[1,])

```

# Answer
> 2 votes
# MATLAB, 42

If it is OK to take input as

```
I=[5.7 3.2
    8.9 8.1]

```

then this statement

```
fminunc(@(y)sum(hypot(I(:,1),I(:,2)-y)),0)

```

returns `5.113014445748538`.

Shamelessly stealing Thomas Kwa's method, you could get it down to 30 at least:

```
I=[5.7+3.2i 8.9+8.1i];
fminunc(@(y)sum(abs(I-i*y)),0)

```

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


title: Calculating Collatz Cousins

text:
# Question
Title: Calculating Collatz Cousins
Define the function *f(n)* for a positive integer *n* as follows:

* *n / 2*, if *n* is even
* *3 * n + 1*, if *n* is odd

If you repeatedly apply this function to any *n* greater than 0, the result always seems to converge to 1 (though nobody's been able to prove that yet). This property is known as the Collatz Conjecture.

Define an integer's *stopping time* as the number of times you have to pass it through the Collatz function *f* before it reaches 1. Here are the stopping times of the first 15 integers:

```
1  0
2  1
3  7
4  2
5  5
6  8
7  16
8  3
9  19
10 6
11 14
12 9
13 9
14 17
15 17

```

Let's call any set of numbers with the same stopping time *Collatz cousins*. For example, 5 and 32 are Collatz cousins, with a stopping time of 5.

Your task: write a program or function that takes a nonnegative integer and generates the set of Collatz cousins whose stopping time is equal to that integer.

## Input

A nonnegative integer S, given via STDIN, ARGV, or function argument.

## Output

A list of all numbers whose stopping time is S, **sorted** in **ascending** order. The list may be output by your program, or returned or output by your function. Output format is flexible: space-separated, newline-separated, or any standard list format of your language is fine, as long as the numbers are easily distinguishable from one another.

## Requirements

Your submission must give correct results for any S ≤ 30. It should finish in seconds or minutes, not hours or days.

## Examples

```
0  -> 1
1  -> 2
5  -> 5, 32
9  -> 12, 13, 80, 84, 85, 512
15 -> 22, 23, 136, 138, 140, 141, 150, 151, 768, 832, 848, 852, 853, 904, 906, 908, 909, 5120, 5376, 5440, 5456, 5460, 5461, 32768

```

Here is a Gist of the output for S = 30.

This is : shortest program in bytes wins. Good luck!

# Answer
# Pyth, ~~26~~ ~~24~~ 21 bytes

```
Su+yMG-/R3fq4%T6G1Q]1

```

This code runs instantly for `S=30`. Try it out yourself: Demonstration

Thanks to @isaacg for saving 5 bytes.

### Explanation

My code starts with `1` and undos the Collatz function. It maps all numbers `d` of the `S-1` step to `2*d` and `(d-1)/3`. The last one in not always valid though.

```
                        implicit: Q = input number
                   ]1   start with G = [1]
 u                Q     apply the following function Q-times to G:
                          update G by
   yMG                      each number in G doubled
  +                       +
          fq4%T6G           filter G for numbers T, which satisfy 4==T%6
       /R3                  and divide them by 3
      -          1          and remove 1, if it is in the list
                            (to avoid jumping from 4 to 1)
S                       sort the result and print

```
> 7 votes

# Answer
# Mathematica, ~~98~~ ~~92~~ 89 bytes

This solution solves `S = 30` immediately:

```
(p={0};l={1};Do[l=Complement[##&@@{2#,Mod[a=#-1,2]#~Mod~3~Mod~2a/3}&/@l,p=p⋃l],{#}];l)&

```

This is an unnamed function taking `S` as its only parameter and returning a list of the Collatz cousins.

The algorithm is a simple breadth-first search. The Collatz cousins for a given `S` are all the integers that can be reached from the Collatz cousins for `S-1` via `2*n` or odd numbers that can be reached via `(n-1)/3`. We also need to ensure that we only produce those integers which were reached for the *first time* after `S` steps, so we keep track of all previous cousins in `p` and remove those from the result. Since we're doing that anyway, we can save a few bytes by computing the steps from *all* previous cousins (not just those from `S-1`) to save a few bytes (that makes it slightly slower, but not noticeably for the required `S`).

Here is a slightly more readable version:

```
(
  p = {0};
  l = {1};
  Do[
    l = Complement[
      ## & @@ {2 #, Mod[a = # - 1, 2] #~Mod~3~Mod~2 a/3} & /@ l,
      p = p ⋃ l
    ]~Cases~_Integer,
    {#}
  ];
  l
) &

```
> 8 votes

# Answer
# CJam, ~~29~~ 26 bytes

```
Xari{{2*_Cmd8=*2*)}%1-}*$p

```

*Credit goes to @isaacg for his idea to remove 1's after each iteration, which saved me two bytes directly and another one indirectly.*

Try it online in the CJam interpreter (should finish in less than a second).

### How it works

```
Xa       e# Push A := [1].
ri{      e# Read an integer from STDIN and do the following that many times:
  {      e# For each N in A:
    2*   e#     Push I := (N * 2) twice.
    _Cmd e#     Push (I / 12) and (I % 12).
     8=  e#     Push K := (I % 12 == 8).

         e#     (K == 1) if and only if the division ((N - 1) / 3) is exact and
         e#     yields an odd integer. In this case we can compute the quotient
         e#     as (I / 12) * 2 + 1.

    *2*) e#     Push J := (I / 12) * K * 2 + 1.

         e#     This yields ((N - 1) / 3) when appropriate and 1 otherwise.
  }%     e# Replace N with I and J.
  1-     e# Remove all 1's from A.

         e# This serves three purposes:

         e# 1. Ones have been added as dummy values for inappropriate quotients.

         e# 2. Not allowing 1's in A avoids integers that have already stopped
         e#    from beginning a new cycle. Since looping around has been prevented,
         e#    A now contains all integers of a fixed stopping time.

         e# 3. If A does not contain duplicates, since the maps N -> I and N -> J
         e#      are inyective (exluding image 1) and yield integers of different
         e#      parities, the updated A won't contain duplicates either.

}*       e#
$p       e# print(sort(C))

```
> 5 votes

# Answer
# Python 2, ~~86~~ ~~83~~ ~~75~~ ~~73~~ 71 bytes

```
f=lambda n,k=1:sorted([k][n:]or(k>4==k%6and f(n-1,k/3)or[])+f(n-1,k*2))

```

Call like `f(30)`. `n = 30` is pretty much instant.

*(Thanks to @DLosc for the idea of recursing by `k` being a number rather than a list of cousins, and a few bytes. Thank to @isaacg for dropping `~-`.)*

This variant is much shorter, but unfortunately takes too long due to exponential branching:

```
f=lambda n,k=1:sorted([k][n:]or(k>4==k%6)*f(n-1,k/3)+f(n-1,k*2))

```
> 5 votes

# Answer
# CJam, 35 bytes

```
1]ri{_"(Z/Y*"3/m*:s:~\L+:L-_&0-}*$p

```

Explanation coming soon. This is a much faster version than the "pretty straight forward" approach (see it in edit history).

Try it online here for `N = 30` which runs in seconds on the online version and instantly in the Java Compiler
> 4 votes

# Answer
# Java 8, 123

```
x->java.util.stream.LongStream.range(1,(1<<x)+1).filter(i->{int n=0;for(;i>1;n++)i=i%2<1?i/2:3*i+1;return n==x;}).toArray()

```

When `x` is 30, the program takes 15 minutes and 29 seconds.

## Expanded

```
class Collatz {
    static IntFunction<long[]> f =
            x -> java.util.stream.LongStream.range(1, (1 << x) + 1).filter(i -> {
                int n = 0;
                for (; i > 1; n++)
                    i = i % 2 < 1 ? i / 2 : 3 * i + 1;
                return n == x;
            }).toArray();

    public static void main(String[] args) {
        System.out.println(Arrays.toString(f.apply(15)));
    }
}

```
> 3 votes

# Answer
# Python 2, 118 bytes

Well, I figured that I wouldn't reach the best Python score after seeing @Sp3000's solution. But it looked like a fun little problem, so I wanted to try an independent solution anyway:

```
s={1}
for k in range(input()):
 p,s=s,set()
 for t in p:s.add(2*t);t>4and(t-1)%6==3and s.add((t-1)/3)
print sorted(s)

```

Same thing before stripping whitespace:

```
s={1}
for k in range(input()):
    p,s=s,set()
    for t in p:
        s.add(2 * t)
        t > 4 and (t - 1) % 6 == 3 and s.add((t - 1) / 3)
print sorted(s)

```

This is a very direct implementation of a breadth first search. In each step, we have the set with stopping time `k`, and derive the set with stopping time `k + 1` by adding the possible predecessors of each value `t` in the set from step `k`:

* `2 * t` is always a possible predecessor.
* If `t` can be written as `3 * u + 1`, where `u` is an odd number that is not `1`, then `u` is a predecessor as well.

Takes about 0.02 seconds to run for `N = 30` on my MacBook Pro.
> 1 votes

# Answer
# PHP 5.4+, 178 bytes

The function

```
function c($s,$v=1,$p=[],&$r=[]){$p[]=$v;if(!$s--){return$r[$v][]=$p;}c($s,$v*2,$p,$r);is_int($b=($v-1)/3)&!in_array($b,$p)&$b%2?c($s,$b,$p,$r):0;ksort($r);return array_keys($r);}

```

Test & Output

```
echo "0 - ".implode(',',c(0)).PHP_EOL;
// 0 - 1
echo "1 - ".implode(',',c(1)).PHP_EOL;
// 1 - 2
echo "5 - ".implode(',',c(5)).PHP_EOL;
// 5 - 5,32
echo "9 - ".implode(',',c(9)).PHP_EOL;
// 9 - 12,13,80,84,85,512
echo "15 - ".implode(',',c(15)).PHP_EOL;
// 15 - 22,23,136,138,140,141,150,151,768,832,848,852,853,904,906,908,909,5120,5376,5440,5456,5460,5461,32768

```

S(30) runs in **0.24 seconds\***, returns 732 elements. A couple are

```
86,87,89,520,522,524,525,528, [ ... ] ,178956928,178956960,178956968,178956970,1073741824

```

\*To save on bytes, I had to add `ksort` and `array_keys` at every step. The only other choice I had was to make a small wrapper function that calls `c()` and then calls `array_keys` and `ksort` on the result once. But due to the time still being decently snappy, I decided to take the performance hit for low byte count. Without the proper sorting & processing, the time is **0.07 seconds** on average for S(30).

If anyone has any clever ways of getting the proper processing only once without too many additional bytes, please let me know! (I store my numbers as array keys, hence the use of `array_keys` and `ksort`)
> 1 votes

# Answer
# C Language

```
#include <stdio.h>
#include <limits.h>
const int s = 30;

bool f(long i)
{
    int r = 0;
    for(;;)
        if (i < 0 || r > s) return false;
        else if (i == 1) break;
        else{r ++;i = i % 2 ? 3*i + 1 : i/2;}
    return (r==s);
}

void main(){
    for(long i = 1; i < LONG_MAX; i++) if (f(i)) printf("%ld ", i);
}

```
> 0 votes

---
Tags: code-golf, math, number, sequence, restricted-time
---


# Question
Title: xkcd challenge: "Percentage of the screen that is [x] color"
So I think we've all probably seen this xkcd comic:

:

This might either be too general or too difficult, I'm not sure. But the challenge is to create a program in any language that creates a window that has at least 2 colors and displays in English words what percentage of the screen is each color.

ex. The simplest solution would be a white background with black letters that read "Percentage of this image that is black: \[x\]%. Percentage of this image that is white: \[y\]%"

You can go as crazy or as simple as you want; plain text is a valid solution but if you make interesting images like in the xkcd comic that's even better! The winner will be the most fun and creative solution that gets the most votes. So go forth and make something fun and worthy of xkcd! :)

So, what do you think? Sound like a fun challenge? :)

**Please include a screenshot of your program running in your answer :)**

# Answer
## Elm

Haven't seen anyone use this loophole yet: demo

```
import Color exposing (hsl)
import Graphics.Element exposing (..)
import Mouse
import Text
import Window

msg a = centered <| Text.color a (Text.fromString "half the screen is this color")

type Pos = Upper | Lower

screen (w,h) (x,y) =
  let (dx,dy) = (toFloat x - toFloat w / 2, toFloat h / 2 - toFloat y)
      ang = hsl (atan2 dy dx) 0.7 0.5
      ang' = hsl (atan2 dx dy) 0.7 0.5
      box c = case c of
        Upper -> container w (h // 2) middle (msg ang) |> color ang'
        Lower -> container w (h // 2) middle (msg ang') |> color ang
  in  flow down [box Upper, box Lower]

main = Signal.map2 screen Window.dimensions Mouse.position

```
> 37 votes

# Answer
# JavaScript with HTML

I tried to reproduce the original comic more precisely. A screenshot is taken using the html2canvas library. The numbers are calculated repeatedly, so you can resize the window or even add something to page in real time.

Try it online: http://copy.sh/xkcd-688.html

Here's a screenshot:

```
<html contenteditable>
<script src=http://html2canvas.hertzen.com/build/html2canvas.js></script>
<script>
onload = function() {
    setInterval(k, 750);
    k();
}
function k() {
    html2canvas(document.body, { onrendered: t });
}
function t(c) {
    z.getContext("2d").drawImage(c, 0, 0, 300, 150);
    c = c.getContext("2d").getImageData(0, 0, c.width, c.height).data;

    for(i = y = 0; i < c.length;)
        y += c[i++];

    y /= c.length * 255;

    x.textContent = (y * 100).toFixed(6) + "% of this website is white";

    q = g.getContext("2d");

    q.fillStyle = "#eee";
    q.beginPath();
    q.moveTo(75, 75);
    q.arc(75,75,75,0,7,false);
    q.lineTo(75,75);
    q.fill();

    q.fillStyle = "#000";
    q.beginPath();
    q.moveTo(75, 75);
    q.arc(75,75,75,0,6.28319*(1-y),false);
    q.lineTo(75,75);
    q.fill();
}
</script>
<center>
<h2 id=x></h2>
<hr>
<table><tr>
<td>Fraction of<br>this website<br>which is white _/
<td><canvas width=150 id=g></canvas>
<td>  Fraction of<br>- this website<br>  which is black
</table>
<hr>
0
<canvas style="border-width: 0 0 1px 1px; border-style: solid" id=z></canvas>
<h4>Location of coloured pixels in this website</h4>

```
> 39 votes

# Answer
# Processing, 222 characters

I've always wanted to make my own version of that comic strip! The simplest (only?) way I could think of doing this was trial and error - draw something, count, draw again...

This program settles for an accurate percentage after a few seconds. It's not very pretty, but **it's interactive**; you can resize the window and it will start to recalculate.

Added some newlines for readability:

```
float s,S,n;
int i;
void draw(){
frame.setResizable(true);
background(255);
fill(s=i=0);
text(String.format("%.2f%% of this is white",S/++n*100),10,10);
loadPixels();
while(i<width*height)if(pixels[i++]==-1)s++;
S+=s/height/width;
}

```

It only shows percentage of white pixels; Because of antialiasing of the text, non-white pixels are not necessarily black. The longer it is running the more time it will need to update itself on a resize.

#### Edit:

So, it's a code-challenge; I sort of golfed it anyways. Maybe I could add some sort of graphs later, but the general principle would remain the same. The interactiveness is the neat part I think.
> 26 votes

# Answer
Great challenge. Here's my solution. I tried to get as close as possible to the original comic, I even used the xkcd font.

It's a WPF application, but I used `System.Drawing` to do the drawing parts because I'm lazy.

Basic concept: In WPF, windows are `Visuals`, which means they can be rendered. I render the entire Window instance onto a bitmap, count up the black and total black or white (ignoring the grays in the font smoothing and stuff) and also count these up for each 3rd of the image (for each panel). Then I do it again on a timer. It reaches equilibrium within a second or two.

Download:

MEGA Always check files you download for viruses, etc, etc.

You'll need to install the font above to your system if you want to see it, otherwise it's the WPF default one.

XAML:

```
<Window
 x:Class="WpfApplication1.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="xkcd: 688" Height="300" Width="1000" WindowStyle="ToolWindow">
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="0.3*"/>
            <ColumnDefinition Width="0.3*"/>
            <ColumnDefinition Width="0.3*"/>
        </Grid.ColumnDefinitions>

        <Border BorderBrush="Black" x:Name="bFirstPanel" BorderThickness="3" Padding="10px" Margin="0 0 10px 0">
            <Grid>
                <Label FontSize="18" FontFamily="xkcd" VerticalAlignment="Top">Fraction of this window that is white</Label>
                <Label FontSize="18" FontFamily="xkcd" VerticalAlignment="Bottom">Fraction of this window that is black</Label>
                <Image x:Name="imgFirstPanel"></Image>
            </Grid>
        </Border>
        <Border Grid.Column="1" x:Name="bSecondPanel" BorderBrush="Black" BorderThickness="3" Padding="10px" Margin="10px 0">
            <Grid>
                <TextBlock FontSize="18" FontFamily="xkcd" VerticalAlignment="Top" HorizontalAlignment="Left">Amount of <LineBreak></LineBreak>black ink <LineBreak></LineBreak>by panel:</TextBlock>
                <Image x:Name="imgSecondPanel"></Image>
            </Grid>
        </Border>
        <Border Grid.Column="2" x:Name="bThirdPanel" BorderBrush="Black" BorderThickness="3" Padding="10px" Margin="10px 0 0 0">
            <Grid>
                <TextBlock FontSize="18" FontFamily="xkcd" VerticalAlignment="Top" HorizontalAlignment="Left">Location of <LineBreak></LineBreak>black ink <LineBreak></LineBreak>in this window:</TextBlock>
                <Image x:Name="imgThirdPanel"></Image>
            </Grid>
        </Border>

    </Grid>
</Window>

```

Code:

```
using System;
using System.Drawing;
using System.Timers;
using System.Windows;
using System.Windows.Media;
using System.Windows.Media.Imaging;
using Brushes = System.Drawing.Brushes;

namespace WpfApplication1
{
    public partial class MainWindow : Window
    {
        private Timer mainTimer = new Timer();
        public MainWindow()
        {
            InitializeComponent();

            Loaded += (o1,e1) =>
                          {
                              mainTimer = new Timer(1000/10);
                              mainTimer.Elapsed += (o, e) => {
                                  try
                                  {
                                      Dispatcher.Invoke(Refresh);
                                  } catch(Exception ex)
                                  {
                                      // Nope
                                  }
                              };
                              mainTimer.Start();
                          };
        }

        private void Refresh()
        {
            var actualh = this.RenderSize.Height;
            var actualw = this.RenderSize.Width;

            var renderTarget = new RenderTargetBitmap((int) actualw, (int) actualh, 96, 96, PixelFormats.Pbgra32);
            var sourceBrush = new VisualBrush(this);

            var visual = new DrawingVisual();
            var context = visual.RenderOpen();

            // Render the window onto the target bitmap
            using (context)
            {
                context.DrawRectangle(sourceBrush, null, new Rect(0,0, actualw, actualh));
            }
            renderTarget.Render(visual);

            // Create an array with all of the pixel data
            var stride = (int) actualw*4;
            var data = new byte[stride * (int)actualh];
            renderTarget.CopyPixels(data, stride, 0);

            var blackness = 0f;
            var total = 0f;

            var blacknessFirstPanel = 0f;
            var blacknessSecondPanel = 0f;
            var blacknessThirdPanel = 0f;
            var totalFirstPanel = 0f;
            var totalSecondPanel = 0f;
            var totalThirdPanel = 0f;

            // Count all of the things
            for (var i = 0; i < data.Length; i += 4)
            {
                var b = data[i];
                var g = data[i + 1];
                var r = data[i + 2];

                if (r == 0 && r == g && g == b)
                {
                    blackness += 1;
                    total += 1;

                    var x = i%(actualw*4) / 4;

                    if(x < actualw / 3f)
                    {
                        blacknessFirstPanel += 1;
                        totalFirstPanel += 1;
                    } else if (x < actualw * (2f / 3f))
                    {
                        blacknessSecondPanel += 1;
                        totalSecondPanel += 1;
                    }
                    else if (x < actualw)
                    {
                        blacknessThirdPanel += 1;
                        totalThirdPanel += 1;
                    }
                } else if (r == 255 && r == g && g == b)
                {
                    total += 1;

                    var x = i % (actualw * 4) / 4;

                    if (x < actualw / 3f)
                    {
                        totalFirstPanel += 1;
                    }
                    else if (x < actualw * (2f / 3f))
                    {
                        totalSecondPanel += 1;
                    }
                    else if (x < actualw)
                    {
                        totalThirdPanel += 1;
                    }
                }
            }

            var black = blackness/total;

            Redraw(black, blacknessFirstPanel, blacknessSecondPanel, blacknessThirdPanel, blackness, renderTarget);
        }

        private void Redraw(double black, double firstpanel, double secondpanel, double thirdpanel, double totalpanels, ImageSource window)
        {
            DrawPieChart(black);
            DrawBarChart(firstpanel, secondpanel, thirdpanel, totalpanels);
            DrawImage(window);
        }

        void DrawPieChart(double black)
        {
            var w = (float)bFirstPanel.ActualWidth;
            var h = (float)bFirstPanel.ActualHeight;
            var padding = 0.1f;

            var b = new Bitmap((int)w, (int)h);
            var g = Graphics.FromImage(b);

            var px = padding*w;
            var py = padding*h;

            var pw = w - (2*px);
            var ph = h - (2*py);

            g.DrawEllipse(Pens.Black, px,py,pw,ph);

            g.FillPie(Brushes.Black, px, py, pw, ph, 120, (float)black * 360);

            g.DrawLine(Pens.Black, 30f, h * 0.1f, w / 2 + w * 0.1f, h / 2 - h * 0.1f);
            g.DrawLine(Pens.Black, 30f, h - h * 0.1f, w / 2 - w * 0.2f, h / 2 + h * 0.2f);

            imgFirstPanel.Source = System.Windows.Interop.Imaging.CreateBitmapSourceFromHBitmap(b.GetHbitmap(), IntPtr.Zero, Int32Rect.Empty, BitmapSizeOptions.FromWidthAndHeight(b.Width, b.Height));
        }

        void DrawBarChart(double b1, double b2, double b3, double btotal)
        {
            var w = (float)bFirstPanel.ActualWidth;
            var h = (float)bFirstPanel.ActualHeight;
            var padding = 0.1f;

            var b = new Bitmap((int)w, (int)h);
            var g = Graphics.FromImage(b);

            var px = padding * w;
            var py = padding * h;

            var pw = w - (2 * px);
            var ph = h - (2 * py);

            g.DrawLine(Pens.Black, px, py, px, ph+py);
            g.DrawLine(Pens.Black, px, py + ph, px+pw, py+ph);

            var fdrawbar = new Action<int, double>((number, value) =>
                {
                    var height = ph*(float) value/(float) btotal;
                    var width = pw/3f - 4f;

                    var x = px + (pw/3f)*(number-1);
                    var y = py + (ph - height);

                    g.FillRectangle(Brushes.Black, x, y, width, height);
                });

            fdrawbar(1, b1);
            fdrawbar(2, b2);
            fdrawbar(3, b3);

            imgSecondPanel.Source = System.Windows.Interop.Imaging.CreateBitmapSourceFromHBitmap(b.GetHbitmap(), IntPtr.Zero, Int32Rect.Empty, BitmapSizeOptions.FromWidthAndHeight(b.Width, b.Height));
        }

        void DrawImage(ImageSource window)
        {
            imgThirdPanel.Source = window;
        }
    }
}

```

The code isn't cleaned up, but it should be somewhat readable, sorry.
> 21 votes

# Answer
## C (with SDL and SDL\_ttf): Grayscale solution

Here's a solution that takes advantage of the pie chart form to capture the complete spectrum of grayscale pixel colors, clocking in at just under 100 lines.

```
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "SDL.h"
#include "SDL_ttf.h"

int main(void)
{
    SDL_Surface *screen, *buffer, *caption;
    SDL_Color pal[256];
    SDL_Rect rect;
    SDL_Event event;
    TTF_Font *font;
    int levels[256], plev[256];
    Uint8 *p;
    float g;
    int cr, redraw, hoffset, h, n, v, w, x, y;

    SDL_Init(SDL_INIT_VIDEO);
    TTF_Init();
    screen = SDL_SetVideoMode(640, 480, 0, SDL_ANYFORMAT | SDL_RESIZABLE);
    font = TTF_OpenFont(FONTPATH, 24);
    buffer = 0;
    for (;;) {
        if (!buffer) {
            buffer = SDL_CreateRGBSurface(SDL_SWSURFACE, screen->w, screen->h,
                                          8, 0, 0, 0, 0);
            for (n = 0 ; n < 256 ; ++n)
                pal[n].r = pal[n].g = pal[n].b = n;
            SDL_SetColors(buffer, pal, 0, 256);
        }
        memcpy(plev, levels, sizeof levels);
        memset(levels, 0, sizeof levels);
        SDL_LockSurface(buffer);
        p = buffer->pixels;
        for (h = 0 ; h < buffer->h ; ++h) {
            for (w = 0 ; w < buffer->w ; ++w)
                ++levels[p[w]];
            p += buffer->pitch;
        }
        for (n = 1 ; n < 256 ; ++n)
            levels[n] += levels[n - 1];
        redraw = memcmp(levels, plev, sizeof levels);
        if (redraw) {
            SDL_UnlockSurface(buffer);
            SDL_FillRect(buffer, NULL, 255);
            caption = TTF_RenderText_Shaded(font,
                        "Distribution of pixel color in this image",
                        pal[0], pal[255]);
            rect.x = (buffer->w - caption->w) / 2;
            rect.y = 4;
            hoffset = caption->h + 4;
            SDL_BlitSurface(caption, NULL, buffer, &rect);
            SDL_FreeSurface(caption);
            SDL_LockSurface(buffer);
            cr = buffer->h - hoffset;
            cr = (cr < buffer->w ? cr : buffer->w) / 2 - 4;
            p = buffer->pixels;
            for (h = 0 ; h < buffer->h ; ++h) {
                y = h - (screen->h + hoffset) / 2;
                for (w = 0 ; w < buffer->w ; ++w) {
                    x = w - buffer->w / 2;
                    g = sqrtf(x * x + y * y);
                    if (g < cr - 1) {
                        g = atanf((float)y / (x + g));
                        v = levels[255] * (g / M_PI + 0.5);
                        for (n = 0 ; n < 255 && levels[n] < v ; ++n) ;
                        p[w] = n;
                    } else if (g < cr + 1) {
                        p[w] = (int)(128.0 * fabs(g - cr));
                    }
                }
                p += buffer->pitch;
            }
        }
        SDL_UnlockSurface(buffer);
        SDL_BlitSurface(buffer, NULL, screen, NULL);
        SDL_UpdateRect(screen, 0, 0, 0, 0);
        if (redraw ? SDL_PollEvent(&event) : SDL_WaitEvent(&event)) {
            if (event.type == SDL_QUIT)
                break;
            if (event.type == SDL_VIDEORESIZE) {
                SDL_SetVideoMode(event.resize.w, event.resize.h, 0,
                                 SDL_ANYFORMAT | SDL_RESIZABLE);
                SDL_FreeSurface(buffer);
                buffer = 0;
            }
        }
    }
    SDL_Quit();
    TTF_Quit();
    return 0;
}

```

As with my previous solution, the path to the font file needs to be either hardcoded in the source or added to the build command, e.g.:

```
gcc -Wall -o xkcdgolf `sdl-config --cflags`
    -DFONTPATH=`fc-match --format='"%{file}"' :bold`
    xkcdgolf.c -lSDL_ttf `sdl-config --libs` -lm

```

The output of the program looks like this:

This one is fun to watch, because all the math slows down the redraws to where you can see the program zero in on the stable solution. The first estimate is wildly off (since the surface starts out all-black), and then shrinks down to the final size after about a dozen or so iterations.

The code works by taking a population count of each pixel color in the current image. If this population count doesn't match the last one, then it redraws the image. The code iterates over every pixel, but it transforms the x,y coordinates into polar coordinates, computing first the radius (using the center of the image as the origin). If the radius is within the pie chart area, it then computes the theta. The theta is easily scaled to the population counts, which determines the pixel color. On the other hand, if the radius is right on the border of the pie chart, then an anti-aliased value is computed to draw the circle around the outside of the chart. Polar coordinates make everything easy!
> 14 votes

# Answer
## C (with SDL and SDL\_ttf)

Here's a very simple implementation, in about 60 lines of C code:

```
#include <stdio.h>
#include "SDL.h"
#include "SDL_ttf.h"

int main(void)
{
    char buf[64];
    SDL_Surface *screen, *text;
    SDL_Rect rect;
    SDL_Color black;
    SDL_Event event;
    TTF_Font *font;
    Uint32 blackval, *p;
    int size, b, prevb, h, i;

    SDL_Init(SDL_INIT_VIDEO);
    TTF_Init();
    screen = SDL_SetVideoMode(640, 480, 32, SDL_ANYFORMAT | SDL_RESIZABLE);
    font = TTF_OpenFont(FONTPATH, 32);
    black.r = black.g = black.b = 0;
    blackval = SDL_MapRGB(screen->format, 0, 0, 0);

    b = -1;
    for (;;) {
        prevb = b;
        b = 0;
        SDL_LockSurface(screen);
        p = screen->pixels;
        for (h = screen->h ; h ; --h) {
            for (i = 0 ; i < screen->w ; ++i)
                b += p[i] == blackval;
            p = (Uint32*)((Uint8*)p + screen->pitch);
        }
        SDL_UnlockSurface(screen);
        size = screen->w * screen->h;
        SDL_FillRect(screen, NULL, SDL_MapRGB(screen->format, 255, 255, 255));
        sprintf(buf, "This image is %.2f%% black pixels", (100.0 * b) / size);
        text = TTF_RenderText_Solid(font, buf, black);
        rect.x = (screen->w - text->w) / 2;
        rect.y = screen->h / 2 - text->h;
        SDL_BlitSurface(text, NULL, screen, &rect);
        SDL_FreeSurface(text);
        sprintf(buf, "and %.2f%% white pixels.", (100.0 * (size - b)) / size);
        text = TTF_RenderText_Solid(font, buf, black);
        rect.x = (screen->w - text->w) / 2;
        rect.y = screen->h / 2;
        SDL_BlitSurface(text, NULL, screen, &rect);
        SDL_FreeSurface(text);
        SDL_UpdateRect(screen, 0, 0, 0, 0);
        if (b == prevb ? SDL_WaitEvent(&event) : SDL_PollEvent(&event)) {
            if (event.type == SDL_QUIT)
                break;
            if (event.type == SDL_VIDEORESIZE)
                SDL_SetVideoMode(event.resize.w, event.resize.h, 32,
                                 SDL_ANYFORMAT | SDL_RESIZABLE);
        }
    }

    TTF_Quit();
    SDL_Quit();
    return 0;
}

```

To compile this, you need to define `FONTPATH` to point to a .ttf file of the font to use:

```
gcc -Wall -o xkcdgolf `sdl-config --cflags`
    -DFONTPATH='"/usr/share/fonts/truetype/freefont/FreeSansBold.ttf"'
    xkcdgolf.c -lSDL_ttf `sdl-config --libs`

```

On most modern Linux machines you can use the `fc-match` utility to look up font locations, so the compile command becomes:

```
gcc -Wall -o xkcdgolf `sdl-config --cflags`
    -DFONTPATH=`fc-match --format='"%{file}"' :bold`
    xkcdgolf.c -lSDL_ttf `sdl-config --libs`

```

(Of course you can replace the requested font with your personal favorite.)

The code specifically requests no anti-aliasing, so that the window contains only black and white pixels.

Finally, I was inspired by @daniero's elegant solution to permit window resizing. You'll see that sometimes the program oscillates between counts, stuck in an orbit around an attractor it can never reach. When that happens, just resize the window a bit until it stops.

And, per request, here's what it looks like when I run it on my system:

Finally, I feel that I should point out, in case anyone here hasn't already seen it, that the MAA published an interview with Randall Munroe in which he discusses the making of cartoon #688 in some detail.
> 10 votes

# Answer
The image is 100x100 and the numbers are exact, and I do mean exact - I chose a 10000 pixel image so that the percentages could be expressed with two decimal places. The method was a bit of math, a bit of guessing, and some number crunching in Python.

Seeing as I knew in advance that the percentages could be expressed in 4 digits, I counted how many black pixels were in each of the digits 0 through 9, in 8 pixel high Arial, which is what the text is written in. I wrote a quick function `weight` which tells you how many pixels are needed to write a given number, left padded with zeros to have 4 digits:

```
def weight(x):
    total = 4 * px[0]
    while x > 0:
       total = total - px[0] + px[x % 10]
       x = x / 10
    return total

```

`px` is an array mapping digits to number of required pixels. If B is the number of black pixels, and W is the number of white pixels, we have `B + W = 10000`, and we need:

```
B = 423 + weight(B) + weight(W)
W = 9577 - weight(B) - weight(W)

```

Where did the constants come from? 423 is the "initial" number of black pixels, the number of black pixels in the text without the numbers. 9577 is the number of initial white pixels. I had to adjust the amount of initial black pixels several times before I managed to get constants such that the above system even has a solution. This was done by guessing and crossing my fingers.

The above system is horribly non-linear, so obviously you can forget about solving it symbolically, but what you can do is just loop through every value of B, set W = 10000 - B, and check the equations explicitly.

```
>>> for b in range(10000 + 1):
...     if b == weight(b) + weight(10000 - b)+423: print b;
...
562
564

```
> 9 votes

# Answer
# QBasic

Because nostalgia.

<sup>And because I don't really know any image libraries in modern languages.</sup>

```
SCREEN 9

CONST screenWidth = 640
CONST screenHeight = 350
CONST totalPixels# = screenWidth * screenHeight

accuracy = 6

newWhite# = 0
newGreen# = 0
newBlack# = totalPixels#

DO
    CLS
    white# = newWhite#
    green# = newGreen#
    black# = newBlack#

    ' Change the precision of the percentages every once in a while
    ' This helps in finding values that converge
    IF RND < .1 THEN accuracy = INT(RND * 4) + 2
    format$ = "###." + LEFT$("######", accuracy) + "%"

    ' Display text
    LOCATE 1
    PRINT "Percentage of the screen which is white:";
    PRINT USING format$; pct(white#)
    LOCATE 4
    PRINT white#; "/"; totalPixels#; "pixels"
    LOCATE 7
    PRINT "Percentage of the screen which is black:";
    PRINT USING format$; pct(black#)
    LOCATE 10
    PRINT black#; "/"; totalPixels#; "pixels"
    LOCATE 13
    PRINT "Percentage of the screen which is green:";
    PRINT USING format$; pct(green#)
    LOCATE 16
    PRINT green#; "/"; totalPixels#; "pixels"

    ' Display bar graphs
    LINE (0, 16)-(pct(white#) / 100 * screenWidth, 36), 2, BF
    LINE (0, 100)-(pct(black#) / 100 * screenWidth, 120), 2, BF
    LINE (0, 184)-(pct(green#) / 100 * screenWidth, 204), 2, BF

    newBlack# = pixels#(0)
    newGreen# = pixels#(2)
    newWhite# = pixels#(15)
LOOP UNTIL black# = newBlack# AND white# = newWhite# AND green# = newGreen#

' Wait for user keypress before ending program: otherwise the "Press any
' key to continue" message would instantly make the results incorrect!
x$ = INPUT$(1)

FUNCTION pixels# (colr)
' Counts how many pixels of the given color are on the screen

pixels# = 0

FOR i = 0 TO screenWidth - 1
    FOR j = 0 TO screenHeight - 1
        IF POINT(i, j) = colr THEN pixels# = pixels# + 1
    NEXT j
NEXT i

END FUNCTION

FUNCTION pct (numPixels#)
' Returns percentage, given a number of pixels

pct = numPixels# / totalPixels# * 100

END FUNCTION

```

Pretty straightforward output-count-repeat method. The main "interesting" thing is that the program randomly tries different precisions for the percentages--I found that it didn't always converge otherwise.

And the output (tested on QB64):
> 9 votes

# Answer
# AWK

## ... with netpbm and other helpers

The 'x' file:

```
BEGIN {
        FS=""
        n++
        while(n!=m) {
                c="printf '%s\n' '"m"% black pixels'"
                c=c" '"100-m"% white pixels'"
                c=c" | pbmtext -space 1 -lspace 1 | pnmtoplainpnm | tee x.pbm"
                n=m
                delete P
                nr=0
                while(c|getline==1) if(++nr>2) for(i=1;i<=NF;i++) P[$i]++
                close(c)
                m=100*P[1]/(P[0]+P[1])
                print m"%"
        }
}

```

The run:

```
$ awk -f x
4.44242%
5.2424%
5.04953%
5.42649%
5.27746%
5.1635%
5.15473%
5.20733%
5.20733%

```

The picture is written as 'x.pbm', I converted it to png for uploading:
> 3 votes

---
Tags: popularity-contest, graphical-output
---


# Question
Title: Write A Program That Outputs Its Mirror Level
There are 95 printable ASCII characters:

```
 !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

In the Consolas font (the Stack Exchange code block default), some of the characters have mirrors around a vertical axis of symmetry:

* These pairs of characters are mirrors of each other: `()` `[]` `{}` `<>` `/\`
* These characters are mirrors of themselves: `! "'*+-.8:=AHIMOTUVWXY^_ovwx|` (Note that space is one.)
* These do not have mirrors: `#$%&,012345679;?@BCDEFGJKLNPQRSZ`abcdefghijklmnpqrstuyz~`

(`i`, `l`, `0`, `#`, and probably other characters are their own mirrors in some fonts but we'll stick to the Consolas shapes.)

A string is said to be a mirror of itself if it is made with **only the 39 mirror characters**, arranged such that the string has a central vertical line of symmetry. So `](A--A)[` is a mirror of itself but `](A--A(]` is not.

Write a one-line even-length program that is a mirror of itself. When N copies of its left half have been prepended to it and N copies of its right half have been appended to it, it should output N+1. N is a non-negative integer.

For example, if the program was `](A--A)[` (left half: `](A-`, right half: `-A)[`), then:

* Running `](A--A)[` should output `1`. (N = 0)
* Running `](A-](A--A)[-A)[` should output `2`. (N = 1)
* Running `](A-](A-](A--A)[-A)[-A)[` should output `3`. (N = 2)
* Running `](A-](A-](A-](A--A)[-A)[-A)[-A)[` should output `4`. (N = 3)
* . . .
* Running `](A-](A-](A-](A-](A-](A-](A-](A-](A-](A--A)[-A)[-A)[-A)[-A)[-A)[-A)[-A)[-A)[-A)[` should output `10`. (N = 9)
* etc.

### Rules

* Output to stdout or your language's closest alternative. There may be an optional trailing newline. No input should be taken.
* The process should theoretically work for N up to 215-1 or beyond, given enough memory and computing power.
* A full program is required, not just a REPL command.

**The shortest initial program (N = 0 case) in bytes wins.**

# Answer
> 20 votes
# Pip, ~~12~~ ~~8~~ 4 bytes

*Now with 66% fewer bytes!*

```
x++x

```
* `x` is a variable, preinitialized to `""`. In numeric context, this becomes `0`.
* The first half, sans the final `+`, makes an expression of the form `x+x+...+x`. This is a valid statement that does nothing.
* The second half, including the final `+` from the first half, makes an expression of the form `++x+x+...+x`. `++x` increments `x` to `1`, and the rest adds it to itself N times. Because expressions are evaluated left-to-right in Pip, the increment is guaranteed to happen first, and the result is equal to the number of mirror levels.
* At the end, the value of this expression is auto-printed.

Unfortunately, Pip doesn't do well processing huge expressions: this solution causes a `maximum recursion depth exceeded` error for N above 500 or so. Here's a previous solution that doesn't, for **8 bytes**:

```
x++oo++x

```

More on Pip

# Answer
> 34 votes
# GolfScript, 10 bytes

```
!:{)::(}:!

```

Try it online with Web Golfscript: N = 0, N = 1, N = 2, N = 3, N = 41

Web GolfScript has a 1024 character limit, but the Ruby interpreter handles **N = 32767** perfectly:

```
$ curl -Ss http://www.golfscript.com/golfscript/golfscript.rb > golfscript.rb
$ echo '"!:{):"32768*":(}:!"32768*' | ruby golfscript.rb > mirror-level-32767.gs
$ ruby golfscript.rb mirror-level-32767.gs
32768

```

### How it works

Without any input, GolfScript initially has an empty string on the stack.

In the first left half, the following happens:

* `!` applies logical NOT to the empty string. This pushes `1`.
* `:{` saves the integer on the stack in the variable `{`.

Yes, that is a valid identifier, although there's no way to retrieve the stored value.
* `)` increments the integer on the stack.
* `:` is an incomplete instruction.

The the subsequent left halves, the following happens:

* `:!` (where `:` is a leftover from before) saves the integer on the stack in the variable `!`.

Yes, that is also a valid identifier. This breaks the `!` command, but we don't use it anymore.
* `:{`, `)` and `:` work as before.

In the first right half, the following happens:

* `::` (where `:` is a leftover from before) saves the integer on the stack in the variable `:`.

Yes, *even that* is valid identifier. As with `{`, there's no way to retrieve the stored value.
* `(` decrements the integer on the stack, yielding the number of left halves.
* `}`, since it is unmatched and terminates execution immediately.

This is an undocumented feature. I call them *supercomments*.

The remaining code is simply ignored.

# Answer
> 27 votes
# Z80 Machine Code, ~~8~~ 6 bytes\*

`<8ww8>` * Assumes certain conditions by entering from Amstrad BASIC

```
<   INC A         // A=A+1
8w  JR C, #77     ## C is unset unless A has overflowed, does nothing

w   LD (HL), A    // Saves A to memory location in HL (randomly initialised)
8>  JR C, #3E     ## C is still unset, does nothing

```

`A` is initially 0 when entered from BASIC. It increments `A` *n* times, then writes it *n* times to the same memory location (which is set to a slightly random location by BASIC)! The `JR` Jump Relative operation never does anything since the `C` flag is always unset, so is used to "comment out" the following byte! This version is slightly cheating by assuming certain entry conditions, namely entering from BASIC guarantees that `A` is always 0. The location of `(HL)` is not guaranteed to be safe, and in fact, is probably a dangerous location. The below code is much more robust which is why it's so much longer.

# Z80 Machine Code, 30 bytes

As ASCII: `o!.ww.!>A=o>{))((}<o=A<!.ww.!o`

Basically, the first half guarantees creation of a zero value and the second half increments it and writes it to memory. In the expanded version below `##` denotes code that serves no purpose in its half of the mirror.

```
o   LD L, A       ##
!.w LD HL, #772E  // Load specific address to not corrupt random memory!
w   LD (HL), A    ## Save random contents of A to memory
.!  LD L, #21     ##
>A  LD A, #41     // A=#41
=   DEC A         // A=#40
o   LD L, A       // L=#40
>{  LD A, #7B     ##
)   ADD HL, HL    // HL=#EE80
)   ADD HL, HL    // HL=#DD00. L=#00 at this point

((  JR Z, #28     ##
}   LD A, L       // A=L
<   INC A         // A=L+1
o   LD L, A       // L=L+1
=   DEC A         // A=L
A   LD B, C       ##
<   INC A         // A=L+1
!.w LD HL, #772E  // Load address back into HL
w   LD (HL), A    // Save contents of A to memory
.!  LD L, #21     ##
o   LD L, A       // L=A

```

Breakdown of allowed instructions:

```
n   op    description
--  ----  -----------
28  LD    LoaD 8-bit or 16-bit register
3   DEC   DECrement 8-bit or 16-bit register
1   INC   INCrement 8-bit or 16-bit register
1   ADD   ADD 8-bit or 16-bit register

Available but useless instructions:
3   JR    Jump Relative to signed 8-bit offset
1   DAA   Decimal Adjust Accumulator (treats the A register as two decimal digits
          instead of two hexadecimal digits and adjusts it if necessary)
1   CPL   1s ComPLement A
1   HALT  HALT the CPU until an interrupt is received

```

Out of the 39 instructions allowed, 28 are load operations (the block from 0x40 to 0x7F are all single byte `LD` instructions), most of which are of no help here! The only load to memory instruction still allowed is `LD (HL), A` which means I have to store the value in `A`. Since `A` is the only register left with an allowed `INC` instruction this is actually quite handy!

I can't load `A` with 0x00 to start with because ASCII 0x00 is not an allowed character! All the available values are far from 0 and all mathematical and logical instructions have been disallowed! Except... I can still do `ADD HL, HL`, add 16-bit `HL` to itself! Apart from directly loading values (no use here!), INCrementing `A` and DECrementing `A`, `L` or `HL` this is the only way I have of changing the value of a register! There is actually one specialised instruction that could be helpful in the first half but a pain to work around in the second half, and a ones-complement instruction that is almost useless here and would just take up space.

So, I found the closest value to 0 I could: 0x41. How is that close to 0? In binary it is 0x01000001. So I decrement it, load it into `L` and do `ADD HL, HL` twice! `L` is now zero, which I load back into `A`! Unfortunately, the ASCII code for `ADD HL, HL` is `)` so I now need to use `(` twice. Fortunately, `(` is `JR Z, e`, where `e` is the next byte. So it gobbles up the second byte and I just need to make sure it doesn't do anything by being careful with the `Z` flag! The last instruction to affect the `Z` flag was `DEC A` (counter-intuitively, `ADD HL, HL` doesn't change it) and since I know that `A` was 0x40 at that point it's guaranteed that `Z` is not set.

The first instruction in the second half `JR Z, #28` will do nothing the first 255 times because the Z flag can only be set if A has overflowed from 255 to 0. After that the output will be wrong, however since it's only saving 8-bits values anyway that shouldn't matter. The code shouldn't be expanded more than 255 times.

The code has to be executed as a snippet since all available ways of returning cleanly have been disallowed. All the RETurn instructions are above 0x80 and the few Jump operations allowed can only jump to a positive offset, because all 8-bit negative values have been disallowed too!

# Answer
> 20 votes
# J, ~~16~~ 14 bytes

```
(_=_)]++[(_=_)

```

Usages:

```
   (_=_)]++[(_=_)
1
   (_=_)]+(_=_)]++[(_=_)+[(_=_)
2
   (_=_)]+(_=_)]+(_=_)]++[(_=_)+[(_=_)+[(_=_)
3

```

Explanation:

* J evaluates from right to left.
* `(_=_)` is `inf equals inf` which is true, has a value of `1`, so the expression becomes `1+]...[+1`. (`(8=8)` would also work but this looks cooler. :))
* `[` and `]` return their the left and right arguments respectively if they have 2 arguments. If they get only 1 they return that.
* `+` adds the 2 arguments. If it gets only 1 it returns that.

Now let's evaluate a level 3 expression (going from right to left):

```
(_=_)]+(_=_)]++[(_=_)+[(_=_)  NB. (_=_) is 1

1]+1]+1]++[1+[1+[1  NB. unary [, binary +

1]+1]+1]++[1+[2  NB. unary [, binary +

1]+1]+1]++[3  NB. unary [, unary +

1]+1]+1]+3  NB. unary +, binary ]

1]+1]+3  NB. unary +, binary ]

1]+3  NB. unary +, binary ]

3

```

As we see the right half of the `1`'s gets added and the left side of the `1`'s gets omitted resulting in the desired integer `N`, the mirror level.

Try it online here.

# Answer
> 11 votes
# CJam, 14 bytes

```
]X+:+OooO+:+X[

```

Try it online in the CJam interpreter: N = 0, N = 1, N = 2, N = 3, N = 41

Note that this code finishes with an error message. Using the Java interpreter, that error message can be suppressed by closing or redirecting STDERR.1

### How it works

In the left halves, the following happens:

* `]` wraps the entire stack in an array.
* `X` appends `1` to that array.
* `:+` computes the sum of all array elements.
* `Oo` prints the contents of empty array (i.e., nothing).

In the first right half, the following happens:

* `o` prints the integer on the stack, which is the desired output.
* `O+` attempts to append an empty array to the topmost item of the stack.

However, the stack was empty before pushing `O`. This fails and terminates the execution of the program.

The remaining code is simply ignored.

1According to the meta poll Should submissions be allowed to exit with an error?, this is allowed.

# Answer
> 11 votes
# Haskell, 42 bytes

```
(8-8)-(-(8-8)^(8-8))--((8-8)^(8-8)-)-(8-8)

```

Luckily a line comment in Haskell (-\> `--`) is mirrorable and half of it (-\> `-`) is a valid function. The rest is some math to get the numbers `0` and `1`. Basically we have `(0)-(-1)` with a comment for `N=0` and prepend `(0)-(-1)-` in each step.

If floating point numbers are allowed for output, we can build `1` from `8/8` and get by with 26 bytes:

# Haskell, 26 bytes

```
(8-8)-(-8/8)--(8\8-)-(8-8)

```

Outputs `1.0`, `2.0`, etc.

---
Tags: code-golf, restricted-source, source-layout, printable-ascii
---


# Question
Title: Computing truncated digits sums of powers of pi
Given a positive integer *n* output the sum of the first *n* decimal digits of the fractional part of *πn*.

Example input and outputs:

> 1 → 1
> 2 → 14
> 3 → 6
> 4 → 13
> 5 → 24
> 50 → 211
> 500 → 2305
> 5000 → 22852

Built-in functions computing digits of *π* or evaluating either power series or continued fractions are not allowed. Standard loopholes apply. Input/output can be in a convenient format (stdin, stdout, function in/output, etc).

Shortest code in bytes wins.

# Answer
> 1 votes
# Pyth, 33

```
s<>j^u+/*GHhyHy^TyQr*TQ0ZQT_y*QQQ

```

Based on this answer by isaacg. Could probably be golfed more. Slow.

```
s<>j            Digit sum of...
  ^
    u               Evaluate pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + ...))))
      +
        /
          *GH
          hyH
        y^TyQ       Except we generate a large integer containing 2n digits,
                    rather than a fraction.
      r*TQ0         Experimentally verified that 10*n iterations will give enough
                    precision for 2n digits (# digits correct grows faster than 2n).
      Z
    Q               To the nth power.
  T_y*QQQ         Get the last 2n^2 digits (all the fractional digits) and get the
                  first n fractional digits.

```

# Answer
> 4 votes
## Python - 191 Bytes

```
t=i=1L;k=n=input();f=2000*20**n;A=range(n+1)
for k in range(2,n):A=[(A[j-1]+A[j+1])*j>>1for j in range(n-k+1)];f*=k
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

```

**~4x faster version - 206 bytes**

```
t=i=1L;k=n=input();f=2000*20**n;A=[0,1]+[0]*n
for k in range(1,n):
 f*=k
 for j in range(-~n/2-k+1):A[j]=j*A[j-1]+A[j+1]*(j+2-n%2)
while k:k=(1-~i*n%4)*f/A[1]/i**n;t+=k;i+=2
print sum(map(int,`t`[-n-4:-4]))

```

Input is taken from stdin. Output for *n = 5000* takes approximately 14s with the second script (or 60s with the first).

---

Sample usage:

```
$ echo 1 | python pi-trunc.py
1

$ echo 2 | python pi-trunc.py
14

$ echo 3 | python pi-trunc.py
6

$ echo 4 | python pi-trunc.py
13

$ echo 5 | python pi-trunc.py
24

$ echo 50 | python pi-trunc.py
211

$ echo 500 | python pi-trunc.py
2305

$ echo 5000 | python pi-trunc.py
22852

```

---

The formula used is the following:

where *An* is the *nth* Alternating Number, which can be formally defined as the number of alternating permutations on a set of size *n* (see also: A000111). Alternatively, the sequence can be defined as the composition of the Tangent Numbers and Secant Numbers (*A2n = Sn*, *A2n+1 = Tn*), more on that later.

The small correction factor *cn* rapidly converges to *1* as *n* becomes large, and is given by:

For *n = 1*, this amounts to evaluating the Leibniz Series. Approximating *π* as *10½*, the number of terms required can be calculated as:

which converges (rounded up) to *17*, although smaller values of *n* require considerably more.

For the calculation of *An* there are several algorithms, and even an explicit formula, but all of them are quadratic by *n*. I originally coded an implementation of Seidel's Algorithm, but it turns to be too slow to be practical. Each iteration requires an additional term to be stored, and the terms increase in magnitude very rapidly (the "wrong" kind of *O(n2)*).

The first script uses an implementation of an algorithm originally given by Knuth and Buckholtz:

> *Let T1,k = 1 for all k = 1..n*
>
> *Subsequent values of T are given by the recurrence relation:*
>
> *Tn+1,k = 1/2* \[ *(k - 1) Tn,k-1 \+ (k + 1) Tn,k+1* \]
>
> *An is then given by Tn,1*
>
> (see also: A185414)

Although not explicitly stated, this algorithm calculates both the Tangent Numbers and the Secant Numbers simultaneously. The second script uses a variation of this algorithm by Brent and Zimmermann, which calculates either *T* or *S*, depending on the parity of *n*. The improvement is quadratic by *n/2*, hence the ~4x speed improvement.

# Answer
> 3 votes
# Python 2, 246 bytes

I have taken a similar approach to my answer at Calculate π with quadratic convergence . The last line takes the Nth power of pi and sums the digits. The N=5000 test takes a minute or so.

```
from decimal import*
d=Decimal
N=input()
getcontext().prec=2*N
j=d(1)
h=d(2)
f=h*h
g=j/h
a=j
b=j/h.sqrt()
t=j/f
p=j
for i in bin(N)[2:]:e=a;a,b=(a+b)/h,(a*b).sqrt();c=e-a;t-=c*c*p;p+=p
k=a+b
l=k*k/f/t
print sum(map(int,`l**N`.split('.')[1][:N]))

```

Some tests:

```
$ echo 1 | python soln.py
1
$ echo 3 | python soln.py
6
$ echo 5 | python soln.py
24
$ echo 500 | python soln.py
2305
$ echo 5000 | python soln.py
22852

```

The ungolfed code:

```
from decimal import *
d = Decimal

N = input()
getcontext().prec = 2 * N

# constants:
one = d(1)
two = d(2)
four = two*two
half = one/two

# initialise:
a = one
b = one / two.sqrt()
t = one / four
p = one

for i in bin(N)[2:] :
    temp = a;
    a, b = (a+b)/two, (a*b).sqrt();
    pterm = temp-a;
    t -= pterm*pterm * p;
    p += p

ab = a+b
pi = ab*ab / four / t
print sum(map(int, `pi ** N`.split('.')[1][:N]))

```

---
Tags: code-golf, math, arithmetic, pi
---


# Question
Title: Implement lazy lists, preferably in a language you don't know well
This is a nice exercise for becoming more fluent in that programming language you've been meaning to learn, but have only tinkered with lightly. This involves working with objects, using or simulating closures, and stretching the type system.

Your task is to write code to manage lazy lists, then use it to implement this algorithm for generating Fibonacci numbers:

*Code samples are in Haskell*

```
let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
 in take 40 fibs

```

Result:

```
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]

```

Your lazy list implementation should meet these guidelines:

* A List node is one of three things:
    + Nil - Empty list.
    `[]`
    + Cons - A single item, paired with a List of the remaining items:
    `1 : [2,3,4,5]`
    (`:` is the cons operator in Haskell)
    + Thunk - A deferred computation that produces a List node when needed.
* It supports the following operations:
    + nil - Construct an empty list.
    + cons - Construct a cons cell.
    + thunk - Construct a Thunk, given a function that takes no arguments and returns a Nil or Cons.
    + force - Given a List node:
        - If it's a Nil or Cons, simply return it.
        - If it's a Thunk, call its function to get a Nil or Cons. Replace the thunk with that Nil or Cons, and return it.
        **Note:** Replacing the thunk with its forced value is an important part of the definition of "lazy". If this step is skipped, the Fibonacci algorithm above will be too slow.
    + empty - See if a List node is Nil (after forcing it).
    + head (a.k.a. "car") - Get the first item of a list (or throw a fit if it's Nil).
    + tail (a.k.a. "cdr") - Get the elements after the head of a list (or throw a fit if it's Nil).
    + zipWith - Given a binary function (e.g. `(+)`) and two (possibly infinite) lists, apply the function to corresponding items of the lists. Example:
    `zipWith (+) [1,2,3] [1,1,10] == [2,3,13]`
    + take - Given a number N and a (possibly infinite) list, grab the first N items of the list.
    + print - Print all the items in a list. This should work incrementally when given a long or infinite list.
* `fibs` uses itself in its own definition. Setting up lazy recursion is a tad tricky; you'll need to do something like this:

+ Allocate a thunk for `fibs`. Leave it in a dummy state for now.
    + Define the thunk function, which depends on a reference to `fibs`.
    + Update the thunk with its function.

You may want to hide this plumbing by defining a function `fix` which calls a List-returning function with its own return value. Consider taking a short nap so this idea can set in.
* Polymorphism (the ability to work with lists of any type of item) is not required, but see if you can find a way to do it that's idiomatic in your language.
* Don't worry about memory management. Even languages with garbage collection have a tendency to carry around objects you'll never use again (e.g. on the call stack), so don't be surprised if your program leaks memory while traversing an infinite list.

Feel free to deviate slightly from these guidelines to accommodate the particulars of your language, or to explore alternative approaches to lazy lists.

Rules:

* Pick a language you don't know well. I can't "require" this, hence the "honor-system" tag. However, voters can check your history to see what languages you've been posting in.
* Don't use your language's built-in lazy list support to do everything. Post something substantial or at least interesting.

+ Haskell is pretty much out. That is, unless you do something like this:

    ```
    data List a = IORef (ListNode a)
    data ListNode a = Nil | Cons !a !(List a) | Thunk !(IO (ListNode a))

    ```

    Note: Haskell's non-strict evaluation isn't off-limits, but your lazy list implementation shouldn't derive its capability directly from there. In fact, it'd be interesting to see an efficient, purely functional solution that doesn't require laziness.
    + Python:

    - Don't use itertools.
        - Generators are fine, but you use them, you'll have to find some way to memoize forced values.

# Answer
> 6 votes
## C

I am a total beginner in C, this code is actually the first real thing I coded in C. It compiles without any warnings and runs fine on my system.

### How to build

First, get the tarball from my server. It includes a makefile, so just run `make` to build it and then `make run` to run it. The program then prints a list of the first 93 fibonacci numbers. (After number 94, an unsigned 64 bit integer overflows)

### Explanation

The programs core is the file `lazy-list.c`. In the corresponding header file, I define a struct `list`, that is our lazy list. It looks like this:

```
enum cell_kind {
  NIL,
  CONS,
  THUNK
};

typedef enum cell_kind cell_kind;

typedef long int content_t;

struct list {
  cell_kind kind;
  union {
    struct {
      content_t* head;
      struct list* tail;
    } cons;
    struct {
      struct list* (*thunk)(void*);
      /* If you want to give arguments to the thunk, put them in here */
      void* args;
    } thunk;
  } content;
};

```

The member `kind` is kind of a tag. It marks, whether we reched the lists end (`NIL`), a cell that is already evaluated (`CONS`) or a thunk (`THUNK`). Then, there follows a union. It is

* either an already evaluated cell with a value and a tail
* or a thunk, featuring a function-pointer and a struct, that may contain some arguments to the function, if needed.

The content of the union is asserted by the tag. If the tag is `NIL`, the content of the union is undefined.

By defining the helper functions mentioned in the specification above, one can usually abstract the lists definition from it's usage, eg. you can simply call `nil()` to get an empty list instead of creating one by yourself.

The three most interesting functions are `zipWith`, `take` and `fibonaccis`. But I don't want to explain `take`, since it is very similar to `zipWith`. All functions, that operate lazily, have three components:

* A wrapper, that creates a thunk
* A worker, that performs the calculations for one cell
* A struct, that keeps the arguments

In case of `zipWith`, these are `zipWith`, `__zipWith` and `__zipArgs`. I just show them here without any further explanation, there function should be quite clear:

```
struct __zipArgs {
  content_t* (*f)(content_t*,content_t*);
  list* listA;
  list* listB;
};

static list* __zipWith(void* args_) {
  struct __zipArgs* args = args_;
  list* listA = args->listA;
  list* listB = args->listB;
  list* listC;

  content_t* (*f)(content_t*,content_t*) = args->f;
  content_t* headA = head(listA);
  content_t* headB = head(listB);
  content_t* headC;

  if (NULL == headA || NULL == headB) {
    free(args);
    return nil();
  } else {
    headC = f(headA, headB);
    args->listA = tail(listA);
    args->listB = tail(listB);
    listC = thunk(__zipWith,args);
    return cons(headC,listC);
  }
}

list* zipWith(content_t* (*f)(content_t*,content_t*),list* listA, list* listB) {
  struct __zipArgs* args = malloc(sizeof(struct __zipArgs));
  args->f = f;
  args->listA = listA;
  args->listB = listB;
  return thunk(__zipWith,args);
}

```

The other interesting function is `fibonaccis()`. The problem is, that we need to pass a pointer of the first and second cell to the thunk of the third, but in order to create those cells we also need a pointer to the thunk. To solve that problem, I filled the pointer to the thunk with a `NULL` first and changed it into the thunk, after it was created. Here is the listening:

```
static content_t* __add(content_t* a,content_t* b) {
  content_t* result = malloc(sizeof(content_t));
  *result = *a + *b;
  return result;
}

list* fibonaccis() {
  static content_t one_ = 1;
  static content_t zero_ = 0;
  list* one  = cons(&one_,NULL);
  list* two  = cons(&zero_,one);
  list* core = zipWith(__add,one,two);
  one->content.cons.tail = core;
  return two;

```

### Possible improvements

* My solution does not use polymorphism. Although possibly possible, my C skills are not sufficient to know how to use it. Instead, I used a type `content_t`, that one can change to whatever fits.
* One could extract the thunk out of the list's defintion and using it only abstractly, but doing so would make the code more complicated.
* One could improve the parts of my code that aren't good C.

# Answer
> 6 votes
## PostScript

I've played with PostScript before, but I wouldn't say I know it particularly well (in fact, my guess is that you can count the number of people in the world that really know PostScript using one hand).

I deviated from your spec in that the function that's used to create a thunk is allowed to return another thunk; `force` will keep evaluating until the result is a `nil` or a `cons`.

The lists are implemented as dictionaries:

```
<< /type /nil >>

<< /type /cons
   /head someValue
   /tail someList >>

<< /type /thunk
   /func evaluationFunction >>

<< /type /dataThunk
   /func evaluationFunction
   /data someValueToBePassedToTheFunction >>

```

The code follows. Note that we're overwriting some builtin operators (in particular `print`; I haven't checked if there are more); in real world use, this would have to be watched out for. Of course there will be no real world use, so that's fine.

The comments before the procedures are to be read as

```
% before2 before1 before0  <| procedure |>  after1 after0

```

i.e. showing the expected stack contents before the call and the resulting stack contents after the call. The comments within the procedures show the content of the stack after the particular line has been executed.

```
% Helper procedure that creates a dictionary with the top two elements as keys
% and the next two elements as values.
%
% value1 value2 key1 key2  <| _twodict |>  << /key1 /value1 /key2 /value2 >>
/_twodict {
    << 5 1 roll    % << value1 value2 key1 key2
    4 2 roll       % << key1 key2 value1 value2
    3 2 roll       % << key1 value1 value2 key2
    exch >>
} def

/nil {
    << /type /nil >>
} def

% item list  <| cons |>  consCell
/cons {
    /head /tail _twodict
    dup /type /cons put
} def

% constructs a thunk from the function, which will be called with no
% arguments to produce the actual list node. It is legal for the function
% to return another thunk.
%
% func  <| thunk |>  lazyList
/thunk {
    /thunk /func /type _twodict
} def

% A dataThunk is like a regular thunk, except that there's an additional
% data object that will be passed to the evaluation function
%
% dataObject func  <| dataThunk |>  lazyList
/dataThunk {
    /data /func _twodict
    dup /type /dataThunk put
} def

% lazyList  <| force |>  consOrNil
/force {
    dup /type get dup
    /thunk eq
    {
        pop
        dup /func get exec exch copy
        force
        dup /func undef
    }
    {
        /dataThunk eq
        {
            dup dup /data get exch
            /func get exec exch copy
            force
            dup dup /func undef /data undef
        } if
    } ifelse
} def

/empty {
    force
    /type get
    /nil eq
} def

/head {
    force /head get
} def

/tail {
    force /tail get
} def

/print {
    dup empty not
    {
        dup
        head ==
        tail
        print
    }
    {
        pop
    } ifelse
} def

% sourceList n  <| take |>  resultingList
/take {
    /source /n _twodict
    {
        dup /source get exch    % source data
        /n get 1 sub dup        % source n-1 n-1
        -1 eq
        {
            pop pop nil
        }
        {                       % source n-1
            exch                % n-1 source
            dup head            % n-1 source head
            3 1 roll            % head n-1 source
            tail
            exch take           % head rest
            cons
        } ifelse
    }
    dataThunk
} def

% sourceList1 sourceList2 func  <| zipWith |>  resultList
/zipWith {
    3 1 roll
    2 array astore                  % func [L1 L2]
    /func /sources _twodict
    {
        dup /sources get aload pop  % data L1 L2
        2 copy empty exch empty or
        {
            pop pop pop nil
        }
        {
            dup head exch tail      % data L1 H2 T2
            3 2 roll
            dup head exch tail      % data H2 T2 H1 T1
            exch                    % data H2 T2 T1 H1
            4 3 roll                % data T2 T1 H1 H2
            5 4 roll /func get      % T2 T1 H1 H2 func
            dup 4 1 roll            % T2 T1 func H1 H2 func
            exec                    % T2 T1 func NEWHEAD
            4 2 roll                % func NEWHEAD T2 T1
            exch 4 3 roll           % NEWHEAD T1 T2 func
            zipWith cons
        } ifelse
    }
    dataThunk
} def

```

Load this into Ghostscript, ignoring the displayed page -- we're only working with the interpreter. Here's the Fibonacci algorithm:

```
[balpha@localhost lazylist]$ gs lazylist.ps
GPL Ghostscript 8.71 (2010-02-10)
Copyright (C) 2010 Artifex Software, Inc.  All rights reserved.
This software comes with NO WARRANTY: see the file PUBLIC for details.
GS> **/fibs 0 1 { fibs fibs tail { add } zipWith } thunk cons cons def**
GS> **fibs 40 take print**
0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
GS>

```

Two additional interesting functions:

```
% creates an infinite list that starts with the given value, incrementing
% by one for each additional element
%
% startValue  <| count |>  lazyList
/count {
    {
        dup
        1 add count
        cons
    }
    dataThunk
} def

% apply the given function to each element of the source list, creating
% a (lazy) list that contains the corresponding results
%
% sourceList function  <| map |> resultList
/map {
    /source /func _twodict
    {
        dup /func get exch
        /source get                 % func source
        dup empty not
        {
            dup head                % func source head
            2 index                 % func source head func
            exec 3 1 roll           % newHead func source
            tail exch map cons
        }
        {
            pop pop nil
        } ifelse
    }
    dataThunk
} def

```

Start counting at 5, multiply each element of the resulting list with 3, and display the first ten values:

```
GS> 5 count { 3 mul } map 10 take print
15
18
21
24
27
30
33
36
39
42

```

Regarding polymorphism: Even though PostScript is strongly typed, it allows arbitrary types as dictionary values, so you can throw in anything you like:

```
GS> 1337 [ 42 3.14 ] << /key /value >> (Hello world) 3 count
GS<5> cons cons cons cons 10 take print
1337
[42 3.14]
-dict-
(Hello world)
3
4
5
6
7
8
GS>

```

Note that type errors, e.g. from trying to add strings to numbers, will only happen at evaluation time:

```
GS> (some string) (another string) nil cons cons
GS<1> 13 27 nil cons cons
GS<2> { add } zipWith      % no error yet
GS<1> print
Error: /typecheck in --add--

```

# Answer
> 5 votes
## C++

This is the largest thing I've ever written in C++. I normally use Objective-C.

It's polymorphic but it doesn't free anything ever.

My `main` function (and the `add` function to `ZipWith`)ended up looking like this:

```
int add(int a, int b) {return a + b;}

int main(int argc, char **argv) {
    int numFib = 15; // amount of fibonacci numbers we'll print
    if (argc == 2) {
        numFib = atoi(argv[1]);
    }

    // list that starts off 1, 1...
    LazyList<int> fibo = LazyList<int>(new Cons<int>(1,
                     new LazyList<int>(new Cons<int>(1))));
    // zip the list with its own tail
    LazyList<int> *fiboZip = LazyList<int>::ZipWith(add, &fibo, fibo.Tail());
    // connect the begin list to the zipped list
    fibo.Tail() -> ConnectToList(fiboZip);

    // print fibonacci numbers
    int *fibonums = fibo.Take(numFib);
    for (int i=0; i<numFib; i++) cout << fibonums[i] << " ";

    cout<<endl;

    return 0;
}

```

This gives

```
 ./lazylist-fibo 20
 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

```

The classes work like this:

```
make a thunk:    LazyList<T>(new Thunk<T>( function, *args ))
make empty list: LazyList<T>(new Nil<T>())
make cons:       LazyList<T>(new Cons<T>( car, *cdr ))

list empty:      list.Empty()
list's head:     list.Head()
list's tail:     list.Tail()
zipWith:         LazyList<T>::ZipWith(function, a, b)
take:            list.Take(n)
print:           list.Print()

```

Full source: here. It's a mess, mainly because it's in one big file.

Edit: changed the link (the old one was dead).

# Answer
> 4 votes
## Python

Doesn't use generators to implement the list, just to implement the `__iter__` method for use with `for`.

```
class Node(object):
    def __init__(self, head, tail):
        self.__head__ = head
        self.__tail__ = tail

    def force(self):
        return self

    def empty(self):
        return False

    def head(self):
        return self.__head__

    def tail(self):
        return self.__tail__

    def zip_with(self, func, other):
        def gen_func():
            if other.empty():
                return other
            return Node(func(self.head(), other.head()), self.tail().zip_with(func, other.tail()))
        return Thunk(gen_func)

    def __iter__(self):
        while not self.empty():
            yield self.head()
            self = self.tail()

    def append(self, other):
        while not self.tail().empty():
            self = self.tail()
        self.__tail__ = other

    def take(self, n):
        if n == 0:
            return NullNode()
        else:
            return Node(self.__head__, self.__tail__.take(n - 1))

    def _print(self):
        for item in self:
            print item

class NullNode(Node):
    def __init__(self):
        pass

    def empty(self):
        return True

    def head(self):
        raise TypeError("cannot get head of nil")

    def tail(self):
        raise TypeError("cannot get tail of nil")

    def zip_with(self, func, other):
        return self

    def append(self, other):
        raise TypeError("cannot append to nil")

    def take(self, n):
        return self

class Thunk(Node):
    def __init__(self, func):
        self.func = func

    def force(self):
        node = self.func()
        self.__class__ = node.__class__
        if not node.empty():
            self.__head__ = node.head()
            self.__tail__ = node.tail()
        return self

    def empty(self):
        return self.force().empty()

    def head(self):
        return self.force().head()

    def tail(self):
        return self.force().tail()

    def take(self, n):
        return self.force().take(n)

```

The Fibonacci list is created like this:

```
>>> from lazylist import *
>>> fib = Node(0, Node(1, NullNode()))
>>> fib.append(fib.zip_with(lambda a, b: a + b, fib.tail()))
>>>

```

# Answer
> 4 votes
## Ruby

My first Ruby program. We represent all nodes as arrays, where the array length determines the type:

```
0: empty list
1: thunk (call the single element to get the cons cell)
2: cons cell (1st is head, 2nd is tail)

```

The code is then pretty straightforward, with a hack to reset the thunk function to set up the recursive fib.

```
def nil_()
  return Array[]
end

def cons(a, b)
  return Array[a, b]
end

def thunk(f)
  return Array[f]
end

def force(x)
  if x.size == 1
    r = x[0].call
    if r.size == 2
      x[0] = r[0]
      x.push(r[1])
    else
      x.pop()
    end
  end
end

def empty(x)
  force(x)
  return x.size == 0
end

def head(x)
  force(x)
  return x[0]
end

def tail(x)
  force(x)
  return x[1]
end

def zipWith(f, a, b)
  return thunk(lambda {
    if empty(a) or empty(b)
      return nil_()
    else
      return cons(f.call(head(a), head(b)), zipWith(f, tail(a), tail(b)))
    end
  })
end

def take(n, x)
  if n == 0
    return nil_()
  else
    return cons(head(x), take(n - 1, tail(x)))
  end
end

def print(x)
  while not empty(x)
    puts x[0]
    x = x[1]
  end
end

def add(x, y)
  return x + y
end

T=thunk(nil)  # dummy thunk function
fibs=cons(0, cons(1, T))
T[0]=zipWith(method(:add), fibs, tail(fibs))[0]  # overwrite thunk function

print(take(40, fibs))

```

# Answer
> 3 votes
## Google Go

A relatively new language, and I learned it by `CTRL+F`ing the Spec.

```
package main
import "fmt"

type List struct {
  isNil, isCons, isThunk bool
  head *interface { }
  tail *List
  thunk (func() List)
}

func Nil() List {
  return List { true, false, false, nil, nil, Nil }
}

func Cons(a interface { }, b List) List {
  return List { false, true, false, &a, &b, Nil }
}

func Thunk(f(func() List)) List {
  return List { false, false, true, nil, nil, f }
}

func Force(x List) List {
  if x.isNil { return Nil()
  } else if x.isCons { return Cons(*x.head, *x.tail) }
  return Force(x.thunk())
}

func Empty(x List) bool {
  return Force(x).isNil;
}

func Head(x List) interface { } {
  y := Force(x)
  if y.isNil { panic("No head for empty lists.") }
  return *y.head
}

func Tail(x List) List {
  y := Force(x)
  if y.isNil { panic("No tail for empty lists.") }
  return *y.tail
}

func Take(n int, x List) List {
  if (n == 0) { return Nil() }
  return Thunk(func() List {
    y := Force(x)
    return Cons(*y.head, Take(n - 1, *y.tail))
  })
}

func Wrap(x List) List {
  return Thunk(func() List {
    return x
  })
}

func ZipWith(f(func(interface { }, interface { }) interface { }), a List, b List) List {
  return Thunk(func() List {
    x, y := Force(a), Force(b)
    if x.isNil || y.isNil {
      return Nil()
    }
    return Cons(f(*x.head, *y.head), ZipWith(f, *x.tail, *y.tail))
  });
}

func FromArray(a []interface { }) List {
  l := Nil()
  for i := len(a) - 1; i > -1; i -- {
    l = Cons(a[i], l)
  }
  return l
}

func Print(x List) {
  fmt.Print("[")
  Print1(x)
  fmt.Print("]")
}

func Print1(x List) {
  y := Force(x)
  if y.isCons {
    fmt.Print(Head(y))
    z := Force(Tail(y))
    if z.isCons { fmt.Print(", ") }
    Print1(z)
  }
}

func Plus(a interface { }, b interface { }) interface { } {
  return a.(int) + b.(int)
}

func Fibs() List {

  return Thunk(func() List {
    return Cons(0, Cons(1, Thunk(func() List {
      return ZipWith(Plus, Thunk(Fibs), Tail(Thunk(Fibs)))
    })))
  })
}

func Fibs0() List {
  // alternative method, working
  return Cons(0, Cons(1, Fibs1(0, 1)))
}

func Fibs1(a int, b int) List {
  c := a + b
  return Cons(c, Thunk(func() List { return Fibs1(b, c) }))
}

func CountUp(x int, k int) List {
  return Cons(x, Thunk(func() List {
    return CountUp(x + k, k)
  }))
}

func main() {
  //a := []interface{} { 0, 1, 2, 3 }
  //l, s := FromArray(a), FromArray(a)
  Print(Take(40, Fibs()))
}

```

The problem was fixed, by dealing with thunk-within-a-thunks. However, it seems the online compiler cannot take 40 elements, maybe because of memory. I will test it on my Linux later.

```
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368runtime: address space conflict: map() =
throw: runtime: address space conflict

panic during panic

```

I tested the code with the online compiler, because I can't install Go on Windows easily.

# Answer
> 3 votes
# Crystal

Despite following the GitHub repository, I've never actually *used* Crystal until now. Crystal is a statically-typed Ruby variant with full type inference. Even though there's already a Ruby answer, Crystal's static typing led me to using polymorphism, rather than an array, to represent the nodes. Because Crystal does not allow modification of `self`, I created a wrapper class, named `Node`, that would wrap everything else and manage the thunks.

Along with the classes, I created the constructor functions `lnil`, `cons`, and `thunk`. I've never quite used Ruby for more than a 20-line script before, either, so the block stuff threw me off quite a bit.

I based the `fib` function off the Go answer.

```
class InvalidNodeException < Exception
end

abstract class LazyValue
end

class LNil < LazyValue
    def empty?
        true
    end

    def force!
        self
    end

    def head
        raise InvalidNodeException.new "cannot get head of LNil"
    end

    def tail
        raise InvalidNodeException.new "cannot get tail of Nil"
    end

    def take(n)
        Node.new self
    end
end

class Cons < LazyValue
    def initialize(@car, @cdr)
    end

    def empty?
        false
    end

    def force!
        @cdr.force!
        self
    end

    def head
        @car
    end

    def tail
        @cdr
    end

    def take(n)
        Node.new n > 0 ? Cons.new @car, @cdr.take n-1 : LNil.new
    end
end

class Thunk < LazyValue
    def initialize(&@func : (-> Node))
    end

    def empty?
        raise Exception.new "should not be here!"
    end

    def force!
        @func.call()
    end

    def head
        self.force!.head
    end

    def tail
        self.force!.tail
    end

    def take(n)
        self.force!.take n
    end
end

class Node
    def initialize(@value = LNil.new)
    end

    def empty?
        self.force!
        @value.empty?
    end

    def force!
        @value = @value.force!
        self
    end

    def head
        self.force!
        @value.head
    end

    def tail
        self.force!
        @value.tail
    end

    def take(n)
        self.force!
        return @value.take n
    end

    def print
        cur = self
        while !cur.empty?
            puts cur.head
            cur = cur.tail
        end
    end
end

def lnil
    Node.new LNil.new
end

def cons(x, r)
    Node.new Cons.new x, r
end

def thunk(&f : (-> Node))
    Node.new Thunk.new &f
end

def inf(st=0)
    # a helper to make an infinite list
    f = ->() { lnil }
    f = ->() { st += 1; cons st, thunk &f }
    thunk { cons st, thunk &f }
end

def zipwith(a, b, &f : Int32, Int32 -> Int32)
    thunk { a.empty? || b.empty? ? lnil :
            cons f.call(a.head, b.head), zipwith a.tail, b.tail, &f }
end

def fibs
    # based on the Go answer
    fibs2 = ->(a : Int32, b : Int32) { lnil }
    fibs2 = ->(a : Int32, b : Int32) { cons a+b, thunk { fibs2.call b, a+b } }
    cons 0, cons 1, thunk { fibs2.call 0, 1 }
end

fibs.take(40).print
zipwith(inf, (cons 1, cons 2, cons 3, lnil), &->(a : Int32, b : Int32){ a+b }).print

```

# Answer
> 2 votes
I bent the rules a little because there isn’t yet a .NET solution here – or more generally an OOP solution except for the one in Python which uses inheritance, but it’s different enough from my solution to make both interesting (in particular since Python allows to modify the `self` instance, making the thunk implementation straightforward).

So this is **C#**. Full disclosure: I’m nowhere near a beginner in C# but I haven’t touched the language in a while since I currently have no use for it at the job.

The salient points:

* All classes (`Nil`, `Cons`, `Thunk`) derive from a common abstract base class, `List`.
* The `Thunk` class uses the Envelope-Letter pattern. This essentially emulates the `self.__class__ = node.__class__` assignment in the Python source, since the `this` reference cannot be modified in C#.
* `IsEmpty`, `Head` and `Tail` are properties.
* *All* appropriate functions are implemented recursively and lazily (except for `Print`, which can’t be lazy) by returning thunks. For example, this is `Nil<T>.ZipWith`:

```
public override List<T> ZipWith(Func<T, T, T> func, List<T> other) {
    return Nil();
}

```

… and this is `Cons<T>.ZipWith`:

```
public override List<T> ZipWith(Func<T, T, T> func, List<T> other) {
    return Thunk(() => {
        if (other.IsEmpty)
            return Nil();

        return Cons(func(Head, other.Head), Tail.ZipWith(func, other.Tail));
    });
}

```

Unfortunately, C# has no multiple dispatch, otherwise I could also get rid of the `if` statement. Alas, no dice.

Now, I’m not really happy with my implementation. I’m happy so far because all of the above is totally straightforward. *But*. I feel that the definition of `Fib` is needlessly complicated since I need to wrap the arguments into thunks to make it work:

```
List<int> fib = null;
fib = List.Cons(0, List.Cons(1,
    List.ZipWith(
        (a, b) => a + b,
        List.Thunk(() => fib),
        List.Thunk(() => fib.Tail))));

```

(Here, `List.Cons`, `List.Thunk` and `List.ZipWith` are convenience wrappers.)

I would like to understand why the following much easier definition isn’t working:

```
List<int> fib = List.Cons(0, List.Cons(1, List.Nil<int>()));
fib = fib.Concat(fib.ZipWith((a, b) => a + b, fib.Tail));

```

given an appropriate definition of `Concat`, of course. This is essentially what the Python code does – but it’s not working (= throwing a fit).

/EDIT: Joey has pointed out the obvious flaw in this solution. However, replacing the second line with a thunk also yields an error (Mono segfaults; I’m suspecting a stack overflow which Mono doesn’t handle well):

```
fib = List.Thunk(() => fib.Concat(fib.ZipWith((a, b) => a + b, fib.Tail)));

```

The full source code can be found as a gist on GitHub.

# Answer
> 2 votes
## Pico

for the record, this solution uses a translation of scheme's delay force as defined in srfi-45. and builds lazy lists on top of that.

```
{
` scheme's srfi-45 begins here `

  _lazy_::"lazy";
  _eager_::"eager";

  lazy(exp())::[[_lazy_, exp]];
  eager(exp)::[[_eager_, exp]];
  delay(exp())::lazy(eager(exp()));

  force(promise)::
    { content:promise[1];
      if(content[1]~_eager_,
        content[2],
        if(content[1]~_lazy_,
          { promise_:content[2]();
            content:promise[1];
            if(content[1]~_lazy_,
             { content_:promise_[1];
               content[1]:=content_[1];
               content[2]:=content_[2];
               promise_[1]:=content });
            force(promise) })) };

` scheme's srfi-45 ends here `

nil:delay([]);
is_nil(s):size(force(s))=0;
cons(a(),b()):delay([a(),b()]);
head(s):force(s)[1];
tail(s):force(s)[2];

zipWith(f,a,b):
  lazy(if(is_nil(a)|is_nil(b),
         nil,
         cons(f(head(a),head(b)), zipWith(f,tail(a),tail(b)))));

fibs:void;
fibs:=cons(0, cons(1, zipWith(+,fibs,tail(fibs))));

take(c,s):
  lazy(if((c=0)|(is_nil(s)),
         nil,
         cons(head(s),take(c-1,tail(s)))));

print(s):
  { comma(s):
      if(is_nil(s),
        void,
        { display(head(s));
          if(!(is_nil(tail(s))), display(","));
          comma(tail(s)) });
    display("[");
    comma(s);
    display("]");
    void };

print(take(40,fibs))

}

```

the output looks like this: (but depending on how `tpico` is patched it might have more double quotes in it. `display` normally prints strings with quotes. i.e. all appearances of `[`,`,`,`]` would have quotes around them like `"["`.)

```
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5702887,9227465,14930352,24157817,39088169,63245986]<void>

```

due to the limits of the integer datatype in tpico this fails at computing the 45th (or 46th offset) Fibonacci number.

note that tpico 2.0pl11 is broken in that `begin(a,b)` (which is commonly written as `{a;b}`) and the `if` function are not tail recursive. not to mention that it took me 5 years to figure out why `begin` wasn't tail recursive. also at that time i wrote the translation of srfi-45 in Pico. it turned out to be that `begin` was waiting for the value of `b` before returning when it didn't need to wait. and once i got that i was also able to fix `if` as it had the same problem. and there was this other error that made the meta level constructor `make` inoperative.

Pico lets a function control if its arguments are evaluated before the function is called or just packaged as thunks. for this code, i can ellipsis over the oddities of *call by function*.

Pico has no type inference. i thought about this for a while but i ran to a problem due to the oddities of *call by function*. i came up with the statement that *types must encode the existence of bound variable names*. but i was mainly thinking of how to adapt Hindley-Milner type inference to a subset of Pico without mutation. the main idea was that *the type checker returns multiple possible schemes if there are more than one possible binding* and *the type check succeeds if there is at least one possible type scheme*. a possible scheme is one that no type assignment conflicts.

---
Tags: code-challenge, data-structures
---


# Question
Title: Improving a Rubik's Cube scrambler's byte count
Okay, I recently wrote a Javascript Rubik's Cube scrambler that outputs a 25-move scramble. It's 135 bytes. The Gist is here, but for reference, I have the formatted code:

```
function(){
  for(a=s=y=r=[],m='RLUDFB',x=Math.random;++a<26;y=r,s.push(r+["'",2,''][0|x()*2]))
  for(;r==y;r=m[0|x()*5]);
  return s.join(' ')
}

```

Any tips?

EDIT: Code is updated, with @Optimizer's edits.

# Answer
> 0 votes
# ~~140 135~~ 127 bytes

Still a big one, but here's for starters:

```
function(){for(a=s=y=r=[],x=Math.random;a<25;s[a++]=r+["'",2,''][0|x(y=r)*3])for(;r==y;r='RLUDFB'[0|x()*6]);return s.join(' ')}

```

Some of the few tips used:

* Loose the `var`. There is no point in using `var` when your aim is to golf!
* When `a = []`, `a++` gives `0`. We use this fact to remove a `0` and `,`
* Combine the `a<25` and `a++`
* You don't need to split a string. You can access its characters anyways via `[i]`
* Get rid of `{}` in `for` loops

More to come.

---
Tags: code-golf, tips, javascript
---