title: stupid restrictions and desert

text:
# Question
Title: stupid restrictions and desert
So, you were sitting at your desk, golfing a program to calculate the first 20 digits of pi, and along comes your boss and throws your apple IIe out the window. You are now working on a new project and this computer does not yet have any text capability. None. No fonts. Nothing.

Now let's finish that program. **Calculate** and **Display** the first 20 characters of pi without using any fonts that are not part of your program. Your output can be displayed or written to standard out as an image file (jpeg, png, gif, svg(as long as you don't use any characters), bmp, xpm). You can use any language, but you can not use your language's font functions, text display or similar.

small bonus (10 characters) If it will work on a Lisa.

Edit: for those who didn't figure it out my inspiration was the first mac, and the title is a pun. A big kudos to @Sukminder whose animated gif is just cool. The contest is not over if a better answer comes along.

# Answer
> 6 votes
## Python, 222 chars

```
n=[10**20*277991633/1963319607/10**i%10 for i in range(19,1,-1)]
print' *     *'
print' * **    '+' '.join(' ** * ***** *****  *'[2*d:2*d+2]for d in n)
print'**     * '+' '.join('**  *    * ** ***** '[2*d:2*d+2]for d in n)

```

The first line calculates the digits of pi using the approximation `pi-3 ~= 277991633/1963319607`. The next three lines output 20 characters of pi using ASCII art Nemeth Braille.

```
 *     *
 * **    *  ** *  *   * *  ** *  ** *  *   * **  * ** *  ** *
**     *     *     * *  *  *   *     * ** *  ** *     *     **

```

I'm pushing the boundaries in two directions here, both in the "calculating Pi" and "human readable" senses.

# Answer
> 20 votes
## Python, 217 bytes

*Requires the Python Imaging Library*

```
import Image
x=p=141
i=Image.new('1',(x,11))
while~-p:x=p/2*x/p+2*10**19;p-=2
for c in str(x):[i.putpixel((j%7/5*4-~j%7/4*~j/7+p,j%7*3%14%8+j%14/10+2),1&ord('}`7gjO_a\177o'[int(c)])>>j%7)for j in range(17)];p+=7
i.show()

```

The byte count assumes that the escaped character `\177` is replaced with its literal equivalent (char *127*).

Output will appear as the following (it will open in your default \*.bmp viewer):

Note that this could easily be parameterized to print any number of digits you like. The following will accept an integer input from stdin, and display that many digits:

```
import Image
n=input()
x=p=n*7|1
i=Image.new('1',(x,11))
while~-p:x=p/2*x/p+2*10**(n-1);p-=2
for c in str(x):[i.putpixel((j%7/5*4-~j%7/4*~j/7+p,j%7*3%14%8+j%14/10+2),1&ord('}`7gjO_a\177o'[int(c)])>>j%7)for j in range(17)];p+=7
i.show()

```

Output for *n=80*:

---

### Pi Calculation

```
while~-p:x=p/2*x/p+2*10**19;p-=2

```

Yup, that's it. The formula used is the result of applying Euler's Transform to the Leibniz Series, and then factoring out each term from the remainder of the sum. The formula converges linearly; each digit requires *log2(10) ≈ 3.32* iterations. For those interested in the derivation, see Appendix A.

### Display

PIL is used for image generation, because it's the most convenient library that I know of. A blank *141×11* black and white bitmap is created, and then white lines are drawn on it in a seven-segment fashion, one pixel at a time. The positions required to draw each segment are stored in a bitmask string, with bits corresponding to the following positions:

```
 000
3   5
3   5
 111
4   6
4   6
 222

```

The bit of magic `(j%7/5*4-~j%7/4*~j/7+p,j%7*3%14%8+j%14/10+2)` produces the each pixel in the following order (base-18):

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

 07e
3   5
a   c
 18f
4   6
b   d
 29g

```

---

### Appendix A

Euler's Transform is a convergence acceleration technique that works for any series which displays absolute monotonic convergence. The resulting series will converge linearly, typically at the rate of one bit per term (note that if the original series was already super-linear, the resulting series will actually converge slower). The purely mathematical description is a bit hard to follow, so I'll be taking a procedural approach.

We'll start with the Leibniz Series:

Then split each term in half, combining neighboring terms:

Simplified:

Generalized:

Notice that the leading ½ didn't have a partner term, and thus was excluded from the rest of the sum. This is the first term of the transformed series. To find the next term, we repeat the process again:

And again:

And again:

And once more for good measure:

At this point we have the first five terms, and the sixth term is evident. This should be enough to generalize, so we'll stop here. We'll start by factoring the numerators and denominators:

The denominators evidently contain a Double Factorial of *2n+1*, so we'll patch that in:

Everything fits, except for the first two terms which have an unaccounted for *2* in the denominator. We can fix that by multiplying the entire expression by *2*:

*23 = 2·4*, so:

The numerator can now be easily identified as *n!*.

Notice that the factor added to each successive term, *n/(2n+1)*, approaches ½ as *n* becomes large, implying a linear convergence at the rate of one bit per term - this is in fact by design. A nice result, but it'd be even nicer without the factorials in there. What we can do here is to factor out each successive term from the rest of the sum, which will generate a nested expression:

This can be rewritten as a recurrence relation:

Where *n* counts backwards from ⌈*log2(10)·d*⌉ .. *0*, where *d* is the number of digits required.

It might be interesting to note that the stable point of this recurrence is exactly *2* (or *4* if you've doubled it, as I have in the implmentation above), so you can save a number of iterations by initializing properly. Though, initializing to a random value you need elsewhere, and throwing a few extra iterations on the top is generally cheaper byte-wise.

# Answer
> 12 votes
#C – 777 Characters

# C – 731 Characters

Prints GIF to `stdout`.

* Quirk: No comma after first `3`.

Stitching together GIF from pre-configured header + each digit represented by home brewed (embedded) font of 5x5 pixels.

> Result

> It is there ---^

*Note that GIF vanishes, sometimes, in Chrome after one run.*

```
#include <stdio.h>
#define G 68,30
#define F(e,i)for(i=0;i<e;++i)
#define B w[++k]
unsigned char r[][10]={{4,18,150,199,188,159,10,0},{4,18,102,169,188,122,64,1},{G,160,166,104,217,80,1},{G,160,166,184,140,66,1},{68,96,153,193,135,138,66,1},{G,6,107,199,155,80,40},{68,128,150,22,173,218,90,1},{G,160,182,169,254,84,1},{G,6,138,153,140,10,0},{G,6,138,185,250,66,1},{0,0,0,5,0,5,0,0,2,8}},w[440]={71,73,70,56,57,97,100,0,5,0,144,0,0,255,255,255,0,0,0};int main(){int a=10000,b=0,c=70,d,e=0,f[71],g;int i,j,k=18,s=0;char m[5];for(;b<c;)f[b++]=a/5;for(;d=0,g=c*2;c-=14,e=d%a){for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);sprintf(m,"%d",e+d/a);F(4,i){B=44;B=s++*5;F(10,j)B=r[10][j];F(8,j)B=r[m[i]-'0'][j];B=0;}}B=59;fwrite(w,1,k,stdout);}

```

---

# Short introduction:

## Calculation of PI

Pi is calculated using a slightly modified version of Dik Winter and Achim Flammenkamp's implementation of Rabinowitz and Wagon's algorithm for computing digits of π.

```
int a=10000,b,c=2800,d,e,f[2801],g;main(){for(;b-c;)f[b++]=a/5;for(;d=0,g=c*2;c
-=14,printf("%.4d",e+d/a),e=d%a)for(b=c;d+=f[b]*a,f[b]=d%--g,d/=g--,--b;d*=b);}

```

## GIF generation

GIF images has a `canvas` property in header. We can use this in combination with displaying multiple images by setting `left` property for each digit accordingly – where each digit is a (embedded) image in itself.

Documentation.

## Example:

```
Header: Canvas Width  100 pixels
        Canvas Height   5 pixels

3 : left  0 pixels
1 : left  5 pixels
4 : left 10 pixels
… and so on.

```

## Expanded code (with loads of comments)

*Messy, but that is part of the minimization*:

```
#include <stdio.h>
#define G 68,30
#define F(e,i)for(i=0;i<e;++i)
#define B w[++k]

/* Font + Image Descriptor + Start of Image Data.
 *
 * Font glyphs are black and white pixels making a 5x5 picture.
 * Each glyph has its own entry in array.
 * Pixels (White,White,Black,Black ...) are further compressed using LZW
 * compression.
 *
 * Next entry in array is Image Descriptor which is added before each glyph.
 * Last entry is start of Image Data.
 *
 * - "0" and comma are 7 and 5 bytes, but hacked to fill 8 bytes to make it
 * easier to handle in minified code.
 * */
unsigned char r[][10]={
        /* Images representing glyphs. */
        { 4,   18, 150, 199, 188, 159, 10,  0}, /* 0 */
        { 4,   18, 102, 169, 188, 122, 64,  1}, /* 1 */
        { 68,  30, 160, 166, 104, 217, 80,  1}, /* 2 */
        { 68,  30, 160, 166, 184, 140, 66,  1}, /* 3 */
        { 68,  96, 153, 193, 135, 138, 66,  1}, /* 4 */
        { 68,  30,   6, 107, 199, 155, 80, 40}, /* 5 */
        { 68, 128, 150,  22, 173, 218, 90,  1}, /* 6 */
        { 68,  30, 160, 182, 169, 254, 84,  1}, /* 7 */
        { 68,  30,   6, 138, 153, 140, 10,  0}, /* 8 */
        { 68,  30,   6, 138, 185, 250, 66,  1}, /* 9 */
        {132, 143, 121, 177,  92,   0,  0,  0}, /* , (removed as not used) */
        {
        /* Image Descriptor */
        /* 0x2C    Image separator (Embedded in code)   */
           0,   /* Image Left   (LSB embedded in code.  */
        0, 0,   /* Image top    (16-bit Little endian)  */
        5, 0,   /* Image Width  (16-bit Little endian)  */
        5, 0,   /* Image Height (16-bit Little endian)  */
        0,      /* Packed byte  (Local color table (not used, etc.)) */
        /* Start of Image Data */
        2,      /* Starting size of LZW 2 + 1 = 3 */
        8       /* Number of bytes in data */
        }
};
/* GIF Header + Global Color table.
 *
 * GIF's has a standard header.
 * Canvas size is the are on which to paint.
 * Usually this is size of whole image, but in this code I've spanned it out
 * and paint glyphs by rendering pictures on a canvas of size:
 * 20 * width_of_1_image (5 * 20 = 100)
 *
 * Each image can have an optional color table, but if not present the global
 * color table is used. In this code only global color table is used. It
 * consist of only black and white. (Though very easy to change if wanted.)
 * */
unsigned char buf[440] = {
        71, 73, 70,     /* Signature     "GIF" */
        56, 57, 97,     /* Version       "89a" */
        100, 0,         /* Canvas width  (16-bit Little endian) 5 * 20 = 100*/
          5, 0,         /* Canvas height (16-bit Little endian) 5 pixels.   */
        144,            /* Packed byte: 1 001 0 000
                                  1 : Has global color table.
                                001 : Color resolution.
                                  0 : Sorted Color Table (No)
                                000 : Size of Global Color table (2^(value+1))
                                        or 2 << value ...
                        */
        0,              /* Background Color index. */
        0,              /* Pixel aspect ratio. */
        /* Global color table. */
        255, 255, 255,  /* Index 0: White */
          0,   0,   0   /* Index 1: Black */
};

int main(void){
        /* PI generation variables. */
        int a = 10000,
            b = 0,
            c = 70,
            d,
            e = 0,
            f[71],
            g;
        /* General purpose variables */
        int i,
            j,
            k = 18,     /* Current Index in out buffer. */
            s = 0;      /* Image counter:
                           (Tells us what "left/x" value should be). */
        char m[5];      /* Print next 4 digits of PI to this buffer. */
        /* Prepare / pre-fill for PI math. */
        for(;b < c;)
                f[b++] = a/5;
        /* Calculate 4 and 4 digits of PI and push onto out buffer. */
        for(; d = 0, g = c * 2; c -= 14 , e = d % a) {
                for (b = c; d += f[b] * a, f[b] = d % --g, d /= g--, --b; d *= b);
                /* sprintf next 4 digits to temprary buffer.     */
                sprintf(m, "%d", e + d/a);
                /* We are served 4 and 4 digits.
                 * Here we transalte them to glyphs and push onto out buffer*/
                for (i = 0; i < 4; ++i) {
                        buf[++k] = 0x2C;     /* 0x2C : Image separator.        */
                        buf[++k] = s++ * 5;  /* xx   : Image left (x) on canvas.*/
                        for (j = 0; j < 10; ++j) {
                                /* Push "Start of Image Data" onto buffer      */
                                buf[++k] = r[11][j];
                        }
                        for (j = 0; j < 8; ++j) {
                                /* Push data of glyph (LZW-compressed) onto buffer. */
                                buf[++k] = r[m[i]-'0'][j];
                        }
                        /* Start of image data informs how big the image data
                         * is. End with zero to mark that this is EOI. */
                        buf[++k] = 0;
                }
        }
        /* 0x3b is Trailer, marking end of file. */
        buf[k] = 0x3b;
        /* Write buffer to standard output.
         * 'k' holds length of data, though as we know this image is
         * 100x5 etc. we can pre-define it as well.
         * */
        fwrite(buf, 1, k, stdout);
}

```

---

Looking to use a shorter / other algorithm for calculating π.

# Answer
> 7 votes
# JavaScript, 680 chars

```
<html><body></body><script>v=["","41L70L7e","24C223060Ca0b587C592b2eLae","30L90L55L65C95a7a9Cac9e6eC5e3e2c","aaL2aL80L8e","90L40L36C455565C95a7a9Cac9e6eC5e3e2c","70C52272aC2c3e6eC9eacaaCa89666C36282a","20La0C745a5e","60C202435C465666C96a8aaCac9e6eC3e2c2aC283666C768695Ca4a060","a4Ca69868C382624C223060C90a2a4Ca77c5e","6dC7d7e6eC5e5d6d"];v["."]=v[10];a=(""+(4*Math.atan(1))).split("");s="";for(i in a)s+="<path d='M "+v[a[i]].split("").map(function(c){return+-c||c>"Z"?parseInt(c,16):c;}).join(" ")+"'transform='translate("+i*33+".5,10.5)scale(3,3)'fill='none'stroke='#333'stroke-linecap='round'stroke-linejoin='round'/>";document.body.innerHTML="<svg>"+s+"</svg>";</script></html>

```

This can be viewed in a web browser; the numbers are output as SVG paths.

* It doesn't compute pi in an interesting way, and JS lacks a number type with precision to display 20 digits.
* To save characters, I omitted the path data for "0", since it doesn't show up in the sequence.

# Answer
> 5 votes
# Java - ~~866~~ ~~860~~ ~~857~~ 853 chars, plus a cheating version with 574 chars

Using the Simon Plouffe formula from 1996, outputs a `x.png` file with white digital-clock-like numbers in a black background:

This is the compressed code:

```
import java.math.BigDecimal;class E{static java.awt.Graphics g;public static void main(String[]h)throws Exception{java.awt.image.BufferedImage i=new java.awt.image.BufferedImage(213,17,1);g=i.getGraphics();BigDecimal y=v(-3);for(int n=1;n<99;n++)y=y.add(v(n).multiply(v(2).pow(n)).multiply(f(n).pow(2)).divide(f(2*n),42,0));int j=2;for(char c:y.toPlainString().substring(0,21).toCharArray()){if(j!=12){c-=48;boolean b=c!=1&c!=4;t(b,j,2,8,3);t(c<1|c>3&c!=7,j,2,3,8);t(c<5|c>6,j+5,2,3,8);t(c>1&c!=7,j,7,8,3);t(c%2==0&b,j,7,3,8);t(c!=2,j+5,7,3,8);t(b&c!=7,j,12,8,3);}j+=10;}t(true,17,12,3,3);javax.imageio.ImageIO.write(i,"png",new java.io.File("x.png"));}static BigDecimal v(int k){return BigDecimal.valueOf(k);}static BigDecimal f(int k){return k<2?v(1):f(k-1).multiply(v(k));}static void t(boolean x,int a,int b,int c,int d){if(x)g.fillRect(a,b,c,d);}}

```

That, with identing and some whitespaces would be this:

```
import java.math.BigDecimal;

class E {

    static java.awt.Graphics g;

    public static void main(String[] h) throws Exception {
        java.awt.image.BufferedImage i = new java.awt.image.BufferedImage(213, 17, 1);
        g = i.getGraphics();
        BigDecimal y = v(-3);

        // Calculate PI using the Simon Plouffe formula, 1996.
        for (int n = 1; n < 99; n++)
            y = y.add(v(n).multiply(v(2).pow(n)).multiply(f(n).pow(2)).divide(f(2 * n), 42, 0));

        int j = 2;
        for (char c : y.toPlainString().substring(0, 21).toCharArray()) {
            if (j != 12) {
                c -= 48;
                boolean b = c != 1 & c != 4;
                t(b, j, 2, 8, 3);
                t(c < 1 | c > 3 & c != 7, j, 2, 3, 8);
                t(c < 5 | c > 6, j + 5, 2, 3, 8);
                t(c > 1 & c != 7, j, 7, 8, 3);
                t(c % 2 == 0 & b, j, 7, 3, 8);
                t(c != 2, j + 5, 7, 3, 8);
                t(b & c != 7, j, 12, 8, 3);
            }
            j += 10;
        }
        t(true, 17, 12, 3, 3);
        javax.imageio.ImageIO.write(i, "png", new java.io.File("x.png"));
    }

    static BigDecimal v(int k) {
        return BigDecimal.valueOf(k);
    }

    static BigDecimal f(int k) {
        return k < 2 ? v(1) : f(k - 1).multiply(v(k));
    }

    static void t(boolean x, int a, int b, int c, int d) {
        if (x) g.fillRect(a, b, c, d);
    }
}

```

Cheating the rules and considering that the calculation of PI can be done as "the numeric representation of the String 3.1415926535897934384", this can be reduced to 574 chars:

```
class F{static java.awt.Graphics g;public static void main(String[]h)throws Exception{java.awt.image.BufferedImage i=new java.awt.image.BufferedImage(213,17,1);g=i.getGraphics();int j=2;for(char c:"3.1415926535897932384".toCharArray()){if(j!=12){c-=48;boolean b=c!=1&c!=4;t(b,j,2,8,3);t(c<1|c>3&c!=7,j,2,3,8);t(c<5|c>6,j+5,2,3,8);t(c>1&c!=7,j,7,8,3);t(c%2==0&b,j,7,3,8);t(c!=2,j+5,7,3,8);t(b&c!=7,j,12,8,3);}j+=10;}t(true,17,12,3,3);javax.imageio.ImageIO.write(i,"png",new java.io.File("x.png"));}static void t(boolean x,int a,int b,int c,int d){if(x)g.fillRect(a,b,c,d);}}

```

# Answer
> 4 votes
# Java - ~~642~~ 622 characters

Copying from my previous answer, using the Simon Plouffe formula from 1996. But outputs ASCII-art instead:

```
import java.math.BigDecimal;class H{public static void main(String[]h)throws Exception{int[]t={31599,4681,31183,29647,5101,29671,31719,4687,31727,29679,8192};BigDecimal y=v(-3);for(int n=1;n<99;n++)y=y.add(v(n).multiply(v(2).pow(n)).multiply(f(n).pow(2)).divide(f(2*n),42,0));for(int z=0;z<5;z++){for(char c:y.toPlainString().substring(0,21).toCharArray()){if(c<48)c=58;int a=(t[c-48]>>>z*3)&7;e(a/4);e(a/2&1);e(a&1);e(0);e(0);}e(10);}}static void e(int c){System.out.print((char)(c<2?c*3+32:c));}static BigDecimal v(int k){return BigDecimal.valueOf(k);}static BigDecimal f(int k){return k<2?v(1):f(k-1).multiply(v(k));}}

```

All of that, with some identing and spaces, and a bit of help to the reader understand the meaning of the magic numbers:

```
import java.math.BigDecimal;

class H {

    public static void main(String[] h) throws Exception {
        // Each block corresponds to a line. Each char has 5 lines with a 3-char width.
        int[] t = {
            0b111_101_101_101_111,
            0b001_001_001_001_001,
            0b111_100_111_001_111,
            0b111_001_111_001_111,
            0b001_001_111_101_101,
            0b111_001_111_100_111,
            0b111_101_111_100_111,
            0b001_001_001_001_111,
            0b111_101_111_101_111,
            0b111_001_111_101_111,
            0b010_000_000_000_000
        };

        // Calculate PI using the Simon Plouffe formula, 1996.
        BigDecimal y = v(-3);
        for (int n = 1; n < 99; n++)
            y = y.add(v(n).multiply(v(2).pow(n)).multiply(f(n).pow(2)).divide(f(2 * n), 42, 0));

        for (int z = 0; z < 5; z++) {
            for (char c : y.toPlainString().substring(0, 21).toCharArray()) {
                if (c < 48) c = 58;
                int a = (t[c - 48] >>> z * 3) & 7;
                e(a / 4);
                e(a / 2 & 2);
                e(a & 1);
                e(0);
                e(0); // Not needed, but makes a better art with the cost of 5 chars.
            }
            e(10);
        }
    }

    static void e(int c) {
        System.out.print((char) (c < 2 ? c * 3 + 32 : c));
    }

    static BigDecimal v(int k) {
        return BigDecimal.valueOf(k);
    }

    static BigDecimal f(int k) {
        return k < 2 ? v(1) : f(k - 1).multiply(v(k));
    }
}

```

Output:

```
###         #  # #    #  ###  ###  ###  ###  ###  ###  ###  ###  ###  ###  ###  ###  ###  ###  ###  # #
  #         #  # #    #  #    # #    #  #    #      #  #    # #  # #    #  # #    #    #    #  # #  # #
###         #  ###    #  ###  ###  ###  ###  ###  ###  ###  ###  ###    #  ###  ###  ###  ###  ###  ###
  #         #    #    #    #    #  #    # #    #    #    #  # #    #    #    #    #  #      #  # #    #
###   #     #    #    #  ###  ###  ###  ###  ###  ###  ###  ###  ###    #  ###  ###  ###  ###  ###    #

```

# Answer
> 4 votes
## C, ~~253~~ 250 chars

Approximates pi using the algorithm in @Sukminder's code (shamelessly borrowing and refactoring their code a bit). Outputs a binary PBM image, which could then e.g. be converted with ImageMagick.

```
b,c=70,e,f[71],g;v[71],j,k;L[5]={1072684944,792425072,492082832,256581624};
main(d){for(puts("P4\n8 100");b<c;)f[b++]=2;for(;d=0,g=--c*2;e=d%10){
for(b=c;d+=f[b]*10,f[b]=d%--g,d/=g--,--b;d*=b);v[j++]=e+d/10;}
for(;k<100;k++)putchar(L[k%5]>>3*v[k/5]&7);}

```

Here's what the output looks like with my Braille-based PPM renderer:

Has the same quirk as @Sukminder's answer in that it lacks a decimal separator. In addition, the output of mine is vertical, and whether it's human-readable is arguable...

Edit: applied @ugoren's suggestions.

# Answer
> 4 votes
**PHP 380**

requires gd enabled for image output

```
<? header('Content-Type: image/png');$i=imagecreatetruecolor(84,5);$n=['71775777770','51115441550','51777771770','51411151510','71771771712'];$c=imagecolorallocate($i,255,255,255);$m=(6.28318/2).(5307*5).(28060387*32);$k=5;while($k--)for($j=0;$j<21;$j++){$p=str_pad(decbin($n[$k][($m[$j]!='.')?$m[$j]:10]),3,'0',0);$l=3;while($l--)$p[$l]&&imagesetpixel($i,$l+$j*4,$k,$c);}imagepng($i);

```

pi calculation: since base php has a default precision of 14 and i didn't want to recompile the server with the arbitrary precision extensions enabled, i couldn't even aproximate PI with the required decimals, so instead it calculates tau/2 and then the rest of the decimals

since the graphic is made of 0's and 1's, i may try using WBMP as the format later to see if i can remove gd

# Answer
> 4 votes
# C+LaserWriter printer 599 - 10 = 589

Pipe the output to your LaserWriter! :) This should work on a Lisa (with a C compiler).

It calculates `pi` in the printer by calculating the sum of the lengths of the line-segments which approximate a Bezier curve sequence which approximates a half-circle, divided by diameter, times 2.

```
main(){
printf("/dist{dtransform dup mul exch dup mul add sqrt}def");
printf("/len{3 2 roll sub 3 1 roll exch sub dist}def");
printf("/pi{0 0 2 index 0 180 arc closepath flattenpath");
printf("[{2 copy}{2 copy 6 2 roll len 3 1 roll}{}{counttomark -2 roll len\n");
printf("counttomark 2 add 1 roll counttomark 1 sub{add}repeat\n");
printf("exch pop exch pop exch div 2 mul}pathforall}def\n");
printf("matrix setmatrix 100 dup scale 10 setflat 100 pi 10 string cvs\n");
printf("matrix defaultmatrix setmatrix/Palatino-Roman findfont 10 scalefont setfont\n");
printf("100 700 moveto show showpage");
}

```

Ungolfed Level-1 (1985-compatible) PostScript:

```
%!
/dist { % dx dy  .  dz
    dtransform
    dup mul exch dup mul add sqrt
} def

/len { % x1 y1 x2 y2  .  dist(y2-y1,x2-x1)
    3 2 roll % x1 x2 y2 y1
    sub 3 1 roll exch sub % y2-y1 x2-x1
    dist
} def

/pi { % rad
    0 0 2 index 0 180 arc closepath % rad
    flattenpath
    [
    { % rad [ x(0) y(0)     (m)print
        2 copy
    } %moveto proc
    { % rad [ ... x(n-1) y(n-1) x(n) y(n)     (l)print
        2 copy 6 2 roll len % rad [ ... x(n) y(n) dist
        3 1 roll % rad [ ... dist x(n) y(n)
    } %lineto proc
    {} %curveto proc % n.b. flattenpath leaves no curve segments
    { % rad [ x(0) y(0) dist(1) dist(2) ... dist(n-1) x(n) y(n)     (c)print
        counttomark -2 roll len % rad [ dist(1) dist(2) ... dist(n)
        counttomark 2 add 1 roll % dist(n) rad [ dist...
        counttomark 1 sub { add } repeat % dist(n) rad [ sum_dist
        exch pop % dist(n) rad sum_dist
        exch pop % dist(n) sum_dist
        exch % sum_dist dist(n)
        div  % length_of_half_circle/diameter
        2 mul % C/d
    } %closepath proc
    pathforall
} def

matrix setmatrix
100 dup scale
10 setflat
100 pi 10 string cvs
matrix defaultmatrix setmatrix
/Palatino-Roman findfont 10 scalefont setfont
100 700 moveto show

```

Output:

# Answer
> 2 votes
## Java, 1574 2643 1934 characters

Compressed **1934** characters:

```
    public static void main(String[] args){int[][][]num={{{1,1,1},{1,0,1},{1,0,1},{1,0,1},{1,1,1}},{{0,0,1},{0,0,1},{0,0,1},{0,0,1},{0,0,1}},{{1,1,1},{0,0,1},{1,1,1},{1,0,0},{1,1,1}},{{1,1,1},{0,0,1},{1,1,1},{0,0,1},{1,1,1}},{{1,0,1},{1,0,1},{1,1,1},{0,0,1},{0,0,1}},{{1,1,1},{1,0,0},{1,1,1},{0,0,1},{1,1,1}},{{1,1,1},{1,0,0},{1,1,1},{1,0,1},{1,1,1}},{{1,1,1},{0,0,1},{0,0,1},{0,0,1},{0,0,1}},{{1,1,1},{1,0,1},{1,1,1},{1,0,1},{1,1,1}},{{1,1,1},{1,0,1},{1,1,1},{0,0,1},{0,0,1}},{{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,1}}};BufferedImage image=new BufferedImage(103,5,BufferedImage.TYPE_3BYTE_BGR);for(int q=0;q<103;q++){for(int w=0;w<5;w++){image.setRGB(q,w,0xFFFFFF);}}int loc = 0;String g=String.valueOf(pi(20));for(int w=0;w<g.length()-1;w++){Integer n=0;if(g.charAt(w)=='.'){n=10;}else{n=Integer.parseInt(String.valueOf(g.charAt(w)));}for(int t=0;t<5;t++){for(int q=0;q<3;q++){int c=num[n][t][q]==1?0x000000:0xFFFFFF;image.setRGB(loc+q,t,c);}}loc+=5;}try{BufferedImage bi=image;File f=new File("o.png");ImageIO.write(bi,"png",f);}catch(IOException e){}}public static BigDecimal pi(final int SCALE){BigDecimal a=BigDecimal.ONE;BigDecimal b=BigDecimal.ONE.divide(sqrt(new BigDecimal(2),SCALE),SCALE,BigDecimal.ROUND_HALF_UP);BigDecimal t=new BigDecimal(0.25);BigDecimal x=BigDecimal.ONE;BigDecimal y;while(!a.equals(b)){y=a;a=a.add(b).divide(new BigDecimal(2),SCALE,BigDecimal.ROUND_HALF_UP);b=sqrt(b.multiply(y),SCALE);t=t.subtract(x.multiply(y.subtract(a).multiply(y.subtract(a))));x=x.multiply(new BigDecimal(2));}return a.add(b).multiply(a.add(b)).divide(t.multiply(new BigDecimal(4)),SCALE,BigDecimal.ROUND_HALF_UP);}public static BigDecimal sqrt(BigDecimal A,final int SCALE){BigDecimal x0=new BigDecimal("0");BigDecimal x1=new BigDecimal(Math.sqrt(A.doubleValue()));while(!x0.equals(x1)){x0=x1;x1=A.divide(x0,SCALE,BigDecimal.ROUND_HALF_UP);x1=x1.add(x0);x1=x1.divide(new BigDecimal(2),SCALE,BigDecimal.ROUND_HALF_UP);}return x1;}}

```

Expanded **2643** characters:

```
public static void main(String[] args) {
    int[][][] num = { { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 0, 1 }, { 1, 1, 1 } },
            { { 0, 0, 1 }, { 0, 0, 1 }, { 0, 0, 1 }, { 0, 0, 1 }, { 0, 0, 1 } },
            { { 1, 1, 1 }, { 0, 0, 1 }, { 1, 1, 1 }, { 1, 0, 0 }, { 1, 1, 1 } },
            { { 1, 1, 1 }, { 0, 0, 1 }, { 1, 1, 1 }, { 0, 0, 1 }, { 1, 1, 1 } },
            { { 1, 0, 1 }, { 1, 0, 1 }, { 1, 1, 1 }, { 0, 0, 1 }, { 0, 0, 1 } },
            { { 1, 1, 1 }, { 1, 0, 0 }, { 1, 1, 1 }, { 0, 0, 1 }, { 1, 1, 1 } },
            { { 1, 1, 1 }, { 1, 0, 0 }, { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } },
            { { 1, 1, 1 }, { 0, 0, 1 }, { 0, 0, 1 }, { 0, 0, 1 }, { 0, 0, 1 } },
            { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 } },
            { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 }, { 0, 0, 1 }, { 0, 0, 1 } },
            { { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 0 }, { 0, 0, 1 } } };

    BufferedImage image = new BufferedImage(103, 5, BufferedImage.TYPE_3BYTE_BGR);

    for (int q = 0; q < 103; q++) {
        for (int w = 0; w < 5; w++) {
            image.setRGB(q, w, 0xFFFFFF);
        }
    }

    int loc = 0;

    String g = String.valueOf(pi(20));
    for (int w = 0; w < g.length()-1; w++) {
        Integer n = 0;
        if (g.charAt(w) == '.') {
            n = 10;
        } else {
            n = Integer.parseInt(String.valueOf(g.charAt(w)));
        }
        for (int t = 0; t < 5; t++) {
            for (int q = 0; q < 3; q++) {
                int c = num[n][t][q] == 1 ? 0x000000 : 0xFFFFFF;
                image.setRGB(loc + q, t, c);
            }
        }
        loc += 5;
    }
    try {
        BufferedImage bi = image;
        File outputfile = new File("out2.png");
        ImageIO.write(bi, "png", outputfile);
    } catch (IOException e) {

    }
}

public static BigDecimal pi(final int SCALE) {
    BigDecimal a = BigDecimal.ONE;
    BigDecimal b = BigDecimal.ONE.divide(sqrt(new BigDecimal(2), SCALE), SCALE, BigDecimal.ROUND_HALF_UP);
    BigDecimal t = new BigDecimal(0.25);
    BigDecimal x = BigDecimal.ONE;
    BigDecimal y;

    while (!a.equals(b)) {
        y = a;
        a = a.add(b).divide(new BigDecimal(2), SCALE, BigDecimal.ROUND_HALF_UP);
        b = sqrt(b.multiply(y), SCALE);
        t = t.subtract(x.multiply(y.subtract(a).multiply(y.subtract(a))));
        x = x.multiply(new BigDecimal(2));
    }
    return a.add(b).multiply(a.add(b)).divide(t.multiply(new BigDecimal(4)), SCALE, BigDecimal.ROUND_HALF_UP);

}

public static BigDecimal sqrt(BigDecimal A, final int SCALE) {
    BigDecimal x0 = new BigDecimal("0");
    BigDecimal x1 = new BigDecimal(Math.sqrt(A.doubleValue()));
    while (!x0.equals(x1)) {
        x0 = x1;
        x1 = A.divide(x0, SCALE, BigDecimal.ROUND_HALF_UP);
        x1 = x1.add(x0);
        x1 = x1.divide(new BigDecimal(2), SCALE, BigDecimal.ROUND_HALF_UP);
    }
    return x1;
}

```

Pi method gathered from: https://stackoverflow.com/questions/8343977/calculate-pi-on-an-android-phone?rq=1

---
Tags: code-golf, graphical-output, pi
---


# Question
Title: Determining part of speech of most words
Write a program to output the part of speech of any word inputted to it. I doubt that anyone could get a perfect algorithm, so I will give the code a batch of words in order to ascertain what algorithm is the best.

Weighted Scoring:
+10pts for each word identified correctly: http://www.englishclub.com/grammar/parts-of-speech\_1.htm (out of 100 randomly selected words)
-1pt for each byte
+5pts for each upvote on your answer

Rules:
no using external resources (unless they are counted in the size)

UPDATE: Due to the need for a standardized word list for testing purposes, I will be using the list provided in the response to this question. http://www-personal.umich.edu/~jlawler/wordlist It seems to be a fairly complete list, and will make this a challenge more than a guessing game.

# Answer
> 4 votes
# Mathematica

Mathematica has a native database of words (called up by the simple command `WordData` ) that includes, among other properties, the parts of speech. Without this database, it would be impossible for me to answer the question.

The word list from here was downloaded. Once stored, it is called up as follows:

```
words = Import["wordlist.txt", "Table"];
Length[words]

```

> 69905

Forty words are randomly chosen from the list:

```
list = Flatten@RandomSample[words, 40]

```

> {"mealtime", "deride", "cricketground", "torpedinidae", "rosefish", "akron", "sloppy", "deaden", "assaultive", "mick", "unperceptiveness", "skeg", "pad", "mane", "carvel-built", "night-stop", "monarchy", "corking", "backlog", "scaphopoda", "bagman", "phrthe", "wholesome", "proprietress", "hortus", "unreliable", "farthermost", "fearfulness", "malposed", "stoke", "affiche", "lunatic", "holcus", "devoutness", "macaque", "zenithal", "poetry", "precipitate", "agoraphobic", "snapper"}

---

The following asks Mathematica to return the parts of speech for the list of 40 words. The parts of 31 words are identified. 9 words are not recognized.

```
(s = Select[Flatten@{{#}, WordData[#, "PartsOfSpeech"]} & /@
     list, ! MatchQ[#, {_, WordData[_, _]}] &]) // TableForm
Length[s]

```

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


# Question
Title: Coding in song - Representing music lyrics in a programming language of your choosing
Write a program in the language of your choosing which when read are the lyrics to a song. It *must* be a valid program which can be compiled and run without errors. While you could technically print to the screen all the lyrics, you're encouraged to do it with style and avoiding string literals whenever possible.

Given that this is difficult on of itself, you're allowed to write a single section of boilerplate code which doesn't count towards being readable in the lyrics. However, once the block of code begins which must be read as the lyrics to a song, you cannot interrupt it until the song is finished. You can indicate the beginning and end of the song code with comments. Please also specify the lyrics themselves as you would read the code. You can be "liberal" with your interpretation so long as you don't stray too far from what's written, otherwise it will cost you points.

Partial song lyrics are allowed, though you get double points for having the words to an entire song. Judging is divided into 3 categories:

1. 10 points - Originality
2. 10 points - Song difficulty
3. 20 points - Representation of that song in code.

For each submission, I'll give you your score in a comment below. If you edit your answer, just give me a comment indicator and I'll re-evaluate it accordingly. However in order to be fair, each re-evaluation subtracts 2 points from your total score.

An example might be the following:

```
public class Song {
    public String play() {
        // Song begin
        try {
            if(this instanceof TheRealLife || this instanceof JustFantasy) {
                throw new InALandSlide();
            }
        } catch (InALandSlide e) {
        }
        return "No \"FromReality\"";
        // Song end
    }

    public static void main(String [] args) {
        Song song = new Song();
        song.play();
    }
}

```

Which gets read:

```
Is this TheRealLife?
Or is this JustFantasy?
Caught InALandSlide.
No escape \"FromReality\"

```

Instrumentals aren't allowed, wise guys. ;)

# Answer
## Python - 8+4+15 = 27 points

Here's on couple of stanzas from The Hunting of the Snark by Lewis Carroll.
It calculates a number, based on the algorithm suggested in the poem, and uses it to state a proof about the voice of the jubjub.

```
class taking:
    def __init__(self, n): convenient.val = (n)
    def __enter__(self): pass
    def __exit__(self, type, value, traceback): pass
def a(x,y): x.val = y(x.val); return True
class We:
    def __init__(self): self.val=0
    def __add(self, y): return y+sum(self.x)
    def add(self, *x): self.x = x; return self.__add
    def multiply(self,x,by,diminished_by): self.val *= by-diminished_by
    def proceed2divide(self,x,by): self.val /= by
    def subtract(self,x): self.val -= x; return True
perfectly = lambda x: x and not not x
def must_be(x):
    if x:
        print "\n".join(["Tis the %s of the Jubjub!"%["voice","note","song"][x%3] for x in range(out.val)])
        return out.val
out=convenient=as_you_see=we=then=the=We()
_ = exactly = 15
with\
\
    taking(3) as the_subject_to_reason_about:
    a(convenient, #2 state
    we.add(7,_ & 10)) and then.multiply(out,
    by=1000, diminished_by=8)

    the_result = we.proceed2divide(as_you_see,
    by=992)
    then.subtract(17) and the; answer = must_be(
    exactly and perfectly(True))

```

The original text:

> "Taking Three as the subject to reason about—
> A convenient number to state—
> We add Seven, and Ten, and then multiply out
> By One Thousand diminished by Eight.
>
> "The result we proceed to divide, as you see,
> By Nine Hundred and Ninety Two:
> Then subtract Seventeen, and the answer must be
> Exactly and perfectly true.
> 8 votes

# Answer
## Python (8+7+15=30)

Valid Python code synctactically although it does not do anything particulary useful ;-)

```
from sys import exit as stops ; import os
thing = [] ; me = can = remember = False ; this = open(__file__)
def terrible(v): return v

# ==== start song snippet

me = can = remember = not any(thing)
can = not this.tell(), [True, "dream"]
locals()["deep"] = {"down":{"inside":{"feel_to":"scream"}}}
if `this` + (terrible("silence")): stops(me)

# ===== end song snippet

```

How it is supposed to be read:

> I can't remember anything.
> Can't tell if this is true or dream.
> Deep down inside I feel to scream.
> This terrible silence stops me.
> ...
> *(Metallica - One)*
> 6 votes

# Answer
## C

Somewhat sloppy, I wrote this in about 15 minutes for giggles. Compiles and runs fine with latest version of G++/MinGW (doesn't really do much, though). You can figure this out just fine by yourself, I think:

```
class Rick {

public:

    struct us { bool you; bool me; };

    bool giveYouUp()  { return false; }
    bool letYouDown() { return false; }
    bool runAround()  { return false; }
    bool desertYou()  { return false; }
    bool makeYouCry() { return false; }
    bool sayGoodbye() { return false; }
    bool tellALie()   { return false; }
    bool hurtYou()    { return false; }

    bool thinkingOf(bool whatImThinkingOf) { return whatImThinkingOf; }
    bool justWantTo(bool whatIWantToDo) { return whatIWantToDo; }
    bool tellYou(bool whatIWantToTellYou) { return whatIWantToTellYou; }

    void roll() {
        bool gonna = false;
        while (gonna) {
            giveYouUp();
            letYouDown();
            gonna = (runAround() && desertYou());
            makeYouCry();
            sayGoodbye();
            gonna = (tellALie() && hurtYou());
        }

        bool strangersToLove = true;
        us we = {!strangersToLove, !strangersToLove};

        bool knowTheRules = true;
        bool you = knowTheRules, I = knowTheRules;

        bool aFullCommitment = true;
        we.me = thinkingOf(aFullCommitment);

        int me = 0;
        Rick* guys[] = {this, nullptr, nullptr, nullptr, nullptr};

        bool howImFeeling = true;
        we.me = justWantTo(tellYou(howImFeeling));

        bool understand = true;
        while (we.you != understand) {
            we.you = understand;
        }
    }

};

int main() {
    Rick rick;
    rick.roll();

    return 0;
}

```
> 6 votes

# Answer
### Scala(48 = 2\*(7+4+13))

It's Linux! song.

```
object Song extends App {
  // Compose a song
  trait Compose {
    override def toString = {
      val token = """^.*\$(.*)\$.*$""".r
      val token(verse) = super.toString
      verse.replaceAll("([a-z])([A-Z])", "$1 $2").capitalize
    }
    def excl(ex: String) = println(this + ex)
    def !!(c: Compose) = { excl("."); c }
    def ***(c: Compose) = { excl("..."); c }
    def !(c: Compose) = { excl("!"); c }
    def *(c: Compose) = { excl(","); c }
    def ! = excl("!")
  }
  // It's linux  - lyrics
  case object ItBootsUpFine extends Compose
  case object AllOfTheTime extends Compose
  case object TuxThePenguinIsGreat extends Compose
  case object aPieInTheFace extends Compose
  case object ToTheManIHate extends Compose
  case object EveryoneKnowsItsLinux extends Compose
  case object StableForYouAndMe extends Compose
  case object ItsLinux extends Compose
  case object NoMoreBSODs extends Compose
  case object BetterThanNT extends Compose
  case object BestOfAllItsFree extends Compose
  case object FreeSoftwareForYouAndMe extends Compose
  case object LinuxGPLd extends Compose

  // Singer to sing a song
  def sing(song: => Unit) = { song }

  // Song begins
  sing {
      ItBootsUpFine!
      AllOfTheTime!!
      TuxThePenguinIsGreat!
      aPieInTheFace*
      ToTheManIHate***
      EveryoneKnowsItsLinux!
      ItsLinux!
      ItsLinux!
      StableForYouAndMe!
      ItsLinux!
      ItsLinux!
      NoMoreBSODs!
      ItsLinux!
      ItsLinux!
      BetterThanNT!
      ItsLinux!
      ItsLinux!
      BestOfAllItsFree!
      FreeSoftwareForYouAndMe***
      LinuxGPLd!
  }
  // Song ends
}

```

### Output:

```
It Boots Up Fine!
All Of The Time.
A Pie In The Face,
Tux The Penguin Is Great!
To The Man IHate...
Everyone Knows Its Linux!
Its Linux!
Its Linux!
Stable For You And Me!
Its Linux!
Its Linux!
No More BSODs!
Its Linux!
Its Linux!
Better Than NT!
Its Linux!
Its Linux!
Best Of All Its Free!
Free Software For You And Me...
Linux GPLd!

```
> 2 votes

# Answer
# PHP

Tried my favorite song, Stairway to Heaven.

```
$GLOBALS['sign']= 'words';

class lady extends me // there is a lady
{
  function __construct(){   // who is sure
    global $glitters = 'gold'; // all that glitters is gold
    $buy('stairway_to_heaven'); // and shes buying the stairway to heaven
  }
  $know[] = 'stars are close'; // when she get's there she knows, the stars are close
  function word(){  // with a word she can get
    debug_backtrace(); // what she come for
  }

  $this->buy('stairway_to_heaven'); // and she's buying the stairway to heaven

  $sign = 'words'; // there is a sign on the door
  if(!$sign === $GLOBALS['sign']) // but she want to be sure, cause you know sometimes words have 2 meanings
    exit();

  in_array($tree / $brook, $songbird ? 'sings'); // (literal) in a tree by the brook, there is a songbird who sings

  mysql_real_escape_string($_GET['thoughts']); // sometimes all of our thoughts are misgiven
  for ($i=0;$i<2;i++)
    parent::wonder(); // makes me wonder , makes me wonder

}

```

How is it read :

> There's a lady who's sure all that glitters is gold
> And she's buying a stairway to heaven.
> When she gets there she knows, if the stars are all close
> With a word she can get what she came for.
> Ooh, ooh, and she's buying a stairway to heaven.
> There's a sign on the wall but she wants to be sure
> 'Cause you know sometimes words have two meanings.
> In a tree by the brook, there's a songbird who sings,
> Sometimes all of our thoughts are misgiven.
> Ooh, it makes me wonder,
> Ooh, it makes me wonder.
> 1 votes

# Answer
## C

Here's a complete song.
You can listen to it in Mama Lisa's World.
Note that the song is included as-is, including the punctuation.

```
#define breath,
#define smell breath
#define an;}Englishman; main(){printf("%d\n",sizeof
struct x{int
// Song starts here
Fee, fa, fie, fo, fum,
I smell the breath of an Englishman.
// Song ends here
I);}

```

Prints the number 4.
> 1 votes

# Answer
# Ruby

My take at as close representation as possible. It's easy with Ruby's call chaining.

```
$lines = []

def thisline n=2
    caller(n).first.match(/:(\d+):/)[1].to_i
end

class Chain < Array
    def method_missing method, *args
        $lines[thisline] = Chain[first, self[1], [method, thisline, args]]
    end

    def -(arg)
        $lines[thisline] = Chain[' - ', thisline, self, arg]
    end

    def tokens
        if size < 3
            if first == :_
                []
            else
                [first.to_s.tr(?_, ?\s).strip]
            end
        elsif size < 4
            [first.to_s.tr(?_, ?\s)] + at(2).tokens
        else
            lhs = case el = at(2)
            when Chain then el.tokens
            when String
                el.empty? ? [?'] : [?', el, ?']
            end

            rhs = case el = at(3)
            when Chain then el.tokens
            when Range then el.first.tokens + ['... '] + el.last.tokens
            end

            lhs + [first.to_s.tr(?_, ?\s)] + rhs
        end
    end
end

def self.method_missing method, *args
    line = thisline(3)

    if args.length > 1
        newlines = args.first.is_a?(String) ? args.first.count(?\n) : 0
        $lines[line] = false
        $lines[line-newlines] = Chain[method, line, Chain[', ', line, *args]]
    else
        $lines[line] = Chain[method, line, *args]
    end
end

####################

The pest in_the eyes of death follows us
Through the dirty streets of blood
It begins to eat inside us, decaying_our_bones
How will we escape_if the void covers our lungs?
We are buried_in the spewed trash_for ourselves

Blood _, pain - nothing_to_say
Why then_- must_we_die?

Escape to the void
Escape to the void

I look at my face on the other side of the mirror
My face falls down_in pieces full of worms
I burst my rotten heart with my own hands
I'm dying and I can',t_help_myself

Blood _, pain - nothing_to_say
Why then_- must_we_die?

What have I been running from?
I'',m_not_guilty
You've shown me the worst way
Cause you',re_my_victim... the_next_one

The pest in_the eyes of death follows us
Through the dirty streets of blood
It begins to eat inside us, decaying_our_bones
How will we escape if_the void covers our lungs?
We are buried in_the spewed trash_for ourselves

Blood _, pain - nothing_to_say
Why then_ - must_we_die?

Escape to the void
Escape to the void

####################

$lines.drop_while {|line| !line }.each_with_index {|line, i|
    puts if line.nil?
    next if not line

    line = line.tokens
    line.map!.with_index {|el, j|
        punct = [', ', ' - ', '... ', ?']

        if line[j-1] == ?' and el == ', '
            ''
        elsif punct.include?(el) or punct.include?(line[j+1])
            el
        else
            el + ?\s
        end
    }

    puts line.join
}

```

## Output

```
The pest in the eyes of death follows us
Through the dirty streets of blood
It begins to eat inside us, decaying our bones
How will we escape if the void covers our lungs?
We are buried in the spewed trash for ourselves

Blood, pain - nothing to say
Why then - must we die?

Escape to the void
Escape to the void

I look at my face on the other side of the mirror
My face falls down in pieces full of worms
I burst my rotten heart with my own hands
I'm dying and I can't help myself

Blood, pain - nothing to say
Why then - must we die?

What have I been running from?
I'm not guilty
You've shown me the worst way
Cause you're my victim... the next one

The pest in the eyes of death follows us
Through the dirty streets of blood
It begins to eat inside us, decaying our bones
How will we escape if the void covers our lungs?
We are buried in the spewed trash for ourselves

Blood, pain - nothing to say
Why then - must we die?

Escape to the void
Escape to the void

```

## To do

1. Multiline commas (arguments)
2. Multiline dots (method calls)
> 1 votes

# Answer
**T-SQL Bone Thugs-N-Harmony**

```
DECLARE @line1 varchar(25);
DECLARE @line2 varchar(25);
DECLARE @line4 varchar(25);
DECLARE @line5 varchar(25);

SET @line1 = 'Wake up, wake up, wake up,';
SET @line2 = 'its the';
SET @line4 = 'to get up, get up get up';
SET @line5 = 'so cash your checks and get up';

SELECT @line1 as Layzie, @line2 as Bizzy,
CONVERT(date,DATEADD(day, -
(SELECT
DATEPART(day, GETDATE())
- 1), GETDATE())) as FirstOfTheMonth,
@line4 as Layzie, @line5 as Bizzy;

```

Yeah I know I cheated a bit and I might have the members who sang which line wrong also.
> 0 votes

# Answer
**C - Bottles of Beer**

Compile and run this. Lyrics are put into the source code. Compile and execute output to get next line of song. When it says "Time to go...." then compile and execute with the number of bottles specified on the command line, e.g.:

```
cl prog.c
prog 32 > prog1.c
cl prog1.c
prog1 > .... etc

```

The code, tested using VS2005:-

```
// Time to go to the shop and get some beer
//
//
//
//
// #####.#####.#####.#####.#####.#####.#####
// ##.#####.#####.#####.#####.#####.#####.##
// #####.#####.#####.#####.#####.#####.#####
// ##.#####.#####.#####.#####.#####.#####.##

char *z [] = {
"void l(char *s,int b){int i;printf(\"// \");for(i=0;i<b;++i)printf(s);",
"printf(\"\\n\");}\nint main(int argc, char *argv[]){\nint i,j,k,x=%d;",
"char*p;\nif(!x&&argc==2)x=atoi(argv[1]);\nif(!x){printf(\"// Time to ",
"go to the shop and get some beer\\n//\\n//\\n//\\n//\\n\");k=7;\n",
"}else{printf(\"// %%d bottles of beer on the wall, %%d bottles of beer",
".\\n\",x,x);printf(\"// Take one down and pass it round, \");\n",
"if(x>1)printf(\"%%d bottles of beer on the wall.\\n//\\n\",x-1);\n",
"else printf(\"no more bottles of beer on the wall.\\n//\\n\");\n",
"k=x>2?x:2;l(\"  ^   \",x);l(\" / \\\\  \",x);l(\"/   \\\\ \",x);",
"l(\"|   | \",x);l(\"|Duf| \",x);l(\"|   | \",x);l(\"----- \",x);}\n",
"for(i=0;i<4;++i){\nprintf(\"// %%s\", i&1 ? \"##.\" : \"\");\n",
"for(j=i&1;j<k;++j)\nprintf(\"%%s#####\",j!=(i&1)?\".\":\"\");\n",
"printf(\"%%s\\n\",i&1?\".##\":\"\");}\nprintf(\"\\nchar *z [] = {\\n\");\n",
"for(i=0;i<sizeof z/sizeof z[0];++i){\nprintf(\"\\\"\");\n",
"for(p=z[i];*p;++p)\nswitch (*p){\ncase '\\n':printf(\"\\\\n\");break;\n",
"case '\\\\':printf(\"%%c%%c\",92,92);break;\n",
"case '%%':printf(\"%%c\",37);break;\ncase '\"':printf(\"%%c%%c\",92,'\"');break;\n",
"default:printf(\"%%c\", *p);break;}\nprintf(\"\\\",\\n\");}\n",
"printf(\"};\\n\");\nfor(i=0;i<sizeof z/sizeof z[0];++i)\n",
"printf(z[i],x?x-1:0);}\n",
};
void l(char *s,int b){int i;printf("// ");for(i=0;i<b;++i)printf(s);printf("\n");}
int main(int argc, char *argv[]){
int i,j,k,x=0;char*p;
if(!x&&argc==2)x=atoi(argv[1]);
if(!x){printf("// Time to go to the shop and get some beer\n//\n//\n//\n//\n");k=7;
}else{printf("// %d bottles of beer on the wall, %d bottles of beer.\n",x,x);printf("// Take one down and pass it round, ");
if(x>1)printf("%d bottles of beer on the wall.\n//\n",x-1);
else printf("no more bottles of beer on the wall.\n//\n");
k=x>2?x:2;l("  ^   ",x);l(" / \\  ",x);l("/   \\ ",x);l("|   | ",x);l("|Duf| ",x);l("|   | ",x);l("----- ",x);}
for(i=0;i<4;++i){
printf("// %s", i&1 ? "##." : "");
for(j=i&1;j<k;++j)
printf("%s#####",j!=(i&1)?".":"");
printf("%s\n",i&1?".##":"");}
printf("\nchar *z [] = {\n");
for(i=0;i<sizeof z/sizeof z[0];++i){
printf("\"");
for(p=z[i];*p;++p)
switch (*p){
case '\n':printf("\\n");break;
case '\\':printf("%c%c",92,92);break;
case '%':printf("%c",37);break;
case '"':printf("%c%c",92,'"');break;
default:printf("%c", *p);break;}
printf("\",\n");}
printf("};\n");
for(i=0;i<sizeof z/sizeof z[0];++i)
printf(z[i],x?x-1:0);}

```
> 0 votes

# Answer
## Perl performs Barnes & Barnes

Ever since I first learned Perl, I've wanted an excuse to use the `-P` option. Today, that excuse has finally arrived:

```
#define cry $$
#define people $_
#define some kill
#define we people
#define whenyoudie END
sub yeah{}

# "When You Die", Barnes & Barnes

whenyoudie { you stop drinking beer }
whenyoudie { you stop being here }
whenyoudie { some people,cry }
whenyoudie { we=say "goodbye" }

                yeah

```

Run it with `-M5.010` in addition to the `-P` option, like so:

```
$ perl -PM5.010 whenyoudie
goodbye
Hangup
$

```
> 0 votes

---
Tags: code-challenge
---


# Question
Title: Crash (i.e. cause the interpreter to stop working and force close) Python
I would like to see who can make Python have a fatal crash with the most creative code. This means that when the program runs, Windows for example, will take over and pop up with something like “IDLE has stopped working”, or Linux will do whatever Linux does when a program crashes.

Rules:

1. This must be made in Python 2.7 or above (So old bugs aren't exploited that have been fixed in future versions of Python).
2. The definition of "crash" is "make IDLE or Python exit in an unintended way." This does not mean "make IDLE or Python halt and give a traceback". This also means exit, sys.quit, abort etc are not valid answers. For example, this will not be accepted:

```
import sys
try:
     print c # Crashes Here, as c is not defined.
 except NameError, SyntaxError:
     print "Oh No!"
     sys.exit()

```
3. Making Python stop responding is not accepted.
4. The code must be explained on what it does to crash. A link to a bug report is fine.

The most upvoted answer after 10 days wins! Begin!!

**EDIT:** May I make it clear that the objective is **not to make Python just halt executing the program** with a traceback. The objective is to make Python completely crash or stop working. This means that if this task is successfully accomplished, Windows would give this (I'm not crashing Word here, it's just an example of what should happen for a different program):

or this:

# Answer
Should have been a code-golfing contest ;) - I guess the creativity is the statement the code makes: "I just don't know what's happening here..."

**Copy and paste** the following character in IDLE running on Windows:

```

```

The crash has something to do with the character being encoded as UTF-16 by Windows and the unsuccessful conversion to a UTF-8 character by IDLE...

Edit: python bug #13153
> 19 votes

# Answer
`ctypes` abuse:

```
import ctypes;ctypes.string_at(1)

```

This casts 1 to an address and dereferences it. On any sane system (i.e. one on which 0x00000001 is not a mapped address), this will segfault instantly.
> 19 votes

# Answer
## 60

```
import sys
sys.setrecursionlimit(1<<30)
f=lambda f:f(f)
f(f)

```

Not my own idea. Copied from the Python Wiki here.

This causes an infinite recursion, and is not stopped by the interpreter because we changed the recursion limit.
> 12 votes

# Answer
`signal` abuse (non-Windows only):

```
import os;os.kill(0,4)

```

On most systems (on which SIGILL = 4) this will kill Python with an "illegal instruction" error.

Or you can kill the program using the *killer alarm clock*:

```
import signal;signal.alarm(1)

```

After one second, Python dies with the cryptic message "Alarm clock".
> 10 votes

# Answer
In Python 3.3:

```
exec(type((lambda:0).__code__)(0,1,0,0,0,b'',(),(),(),'','',1,b''))

```

In Python 2.7 code objects are slightly different:

```
exec type((lambda:0).func_code)(0,1,0,0,'Q',(),(),(),'','',0,'')

```

Yes, you can pass any old rubbish to the byte code interpreter and it executes it (Python issue #17187).
> 10 votes

# Answer
Recursive iterators use the C stack, not the Python stack (issue #14010 and issue #14507):

```
i=''
for _ in range(9**6):i=filter(int,i)
del i

```
> 6 votes

# Answer
One easy way to crash the interpreter is to trick it into deallocating None:

```
import ctypes, sys
(ctypes.c_char*4).from_address(id(None))[:] = '\0'*4

```

As a bonus, here's a clever way to segfault Python 2:

```
import ctypes, struct, sys
inner = ()
outer = (inner,)
c_outer = (ctypes.c_char * sys.getsizeof(outer)).from_address(id(outer))
inner_index = c_outer[:].find(struct.pack('P', id(inner)))
c_outer[inner_index:inner_index+struct.calcsize('P')] = struct.pack('P', id(outer))
print outer

```

What exactly this does is left as an exercise to the reader.
> 4 votes

# Answer
Someone thought they could prevent new `FlagsType` objects from being created by setting `FlagsType.tp_new = NULL`, but they forgot to remove the method (issue #13204):

```
import sys
t=type(sys.flags)
t.__new__(t)

```

(`sys.version_info` has the same bug.)
> 3 votes

# Answer
Use of `alloca` in `ctypes` module (issue #13096):

```
from ctypes import *
POINTER('a'*9**8)

```
> 3 votes

# Answer
One possible way which crashes my Python with `MemoryError`:

```
x=[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]

```
> 0 votes

---
Tags: popularity-contest, python
---


title: Get as close to pi as you can

text:
# Question
Title: Get as close to pi as you can
Your job is to **write a program to find the closest number to `PI`**.

## Let me clarify.

You will first choose a number type. Let us say you choose `Integer` (in an actual answer, you cannot). Your program would then have to generate an integer that is closed to `PI`. For `Integer`s, this would be `3`. Not `4`; `3`.

For every allowed number type, there will be one and only one closest number, as you will see.

1. Select your number type. It should only be able to represent rational numbers. You can not make up your own number types. `Float` or `Double` is recommended.
2. Your program will generate a number `ctp` for "close to `PI`" (I am just calling it that; you don't have to). `223/71` \< `ctp` \< `22/7` must be true (this is why you can't choose `Integer`s). Also, `ctp` must be the closet number to `PI` in its number type (although see bonus).
3. No importing libraries for mathematical functions, operations, etc... (although types are allowed as long, as it obeys #1).
4. You must somehow output `ctp`.
5. You also may not hard code any number (in any type) that uses at least half the precision of your chosen number type.

Bonus: If you use a data type with a precision that depends on machine resources, and it still generates the most accurate approximation possible for any given machine, you can take the `pi`th root of your score. Note: If you code may actually exhaust machine resources, put a warning in. That way people know to use virtual machines to check it (or just check it with their minds).

This is code golf, so shortest program in bytes wins!

**Note: The point of this challenge is not just to be another pi calculation challenge. You have to work at the limits of your number type, where all calculations can have detrimental rounding errors. You are doing maximum-precision computing. This is not the same as just outputting a large number of digits.**

# Answer
# C++ 158 chars

```
#include<iostream>
#include<iomanip>
int main(){double p=0;for(long long l=1;l>0;l+=2){p+=(double)4/l;l+=2;p-=(double)4/l;}std::cout<<std::setprecision(30)<<p;}

```

Simply calculates pi by brute force until my computer can't store the number to divide 4 by.

I got to 3.1415926535`792384` before I killed it. The highlighted part is what is off; it should have been 3.1415926535`897932`. Eventually, it would have got there.
> 1 votes

# Answer
## Java: 352 chars

```
import java.math.BigDecimal;class B{public static void main(String[]h){BigDecimal y=v(-3);for(int n=1;n<99;n++)y=y.add(v(n).multiply(v(2).pow(n)).multiply(f(n).pow(2)).divide(f(2*n),42,0));System.out.println(y.toPlainString());}static BigDecimal v(int k){return BigDecimal.valueOf(k);}static BigDecimal f(int k){return k<2?v(1):f(k-1).multiply(v(k));}}

```

This is a simplification of my answer to another question. It uses the formula from Simon Plouffe, 1996. It only uses addition, multiplication, division and exponentiation on the JDK's built-in class `java.lang.BigDecimal`.

Idented version:

```
import java.math.BigDecimal;

class B {
    public static void main(String[] h) {
        BigDecimal y = v(-3);
        for (int n = 1; n < 99; n++)
            y = y.add(v(n).multiply(v(2).pow(n)).multiply(f(n).pow(2)).divide(f(2 * n), 42, 0));
        System.out.println(y.toPlainString());
    }

    static BigDecimal v(int k) {
        return BigDecimal.valueOf(k);
    }

    static BigDecimal f(int k) {
        return k < 2 ? v(1) : f(k - 1).multiply(v(k));
    }
}

```

This is the output:

```
3.141592653589793238462643377679212002490611

```

If you change that 99 and that 42, you might adjust the output. The 99 is the number of iterations (more iterations = more precision). The 42 is the number of decimal digits used in the division (so it rounds beyond that in the case of unexact decimal fractions). For example, using 999 and 420 instead, this is the output:

```
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249120347355734950229986020976256234993050320608823801378401335409091901873689012669359599460964434973644188892882434846280102165

```

Since it is possible to adjust the precision, but only by changing 2 numbers in the source code, but OTOH those numbers have the exact purpose to define the precision, then I don't know if the bonus do applies or do not.
> 1 votes

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


# Question
Title: Convert calendar dates to week dates and vice versa
Your mission is to write a program that accepts a date in the formats `2014-02-27` (calendar date) and `2014-W09-4` (week date) from standard input and outputs the date in the format it wasn't entered in (to standard output with a trailing newline). The dates must conform to the standard ISO 8601, i.e. with weeks that starts on Mondays and where the first week in a (week) year is the one that contains the first Thursday in the calendar year. You are not allowed to use any libraries, built-in functions or operators that relates to the handling of dates and time.

For example:

```
>./aprogramnamethatmostprobablyrelatestobutterfliesandbiscuits
2014-02-27
2014-W09-4
>./aprogramnamethatmostprobablyrelatestobutterfliesandbiscuits
2014-W09-4
2014-02-27
>./aprogramnamethatmostprobablyrelatestobutterfliesandbiscuits
2008-12-30
2009-W01-2
>./aprogramnamethatmostprobablyrelatestobutterfliesandbiscuits
2009-W53-7
2010-01-03
>

```

Years prior to 1583 and after 9999 need not yield the correct answer.

The shortest answer (in characters, not bytes) will be declared the winner and therefore accepted in 19½ days.

A nice resource: ISO week date

# Answer
# Javascript: 422 characters

Originally this had 825 characters, and was still a bit comprehensible and legible, beside the fact of being golfed. I was sure that it could be reduced in something between 10% to 20%. This answer passed by tons of edits from me and got suggestions from @Ismael Miguel and specially from @DocMax resulting in an extremely-golf-crushed source down to 422 characters, with the side-effect of making it heavily obfuscated, a reduction of almost 49%. Really thanks for both, I wish that you two could get a badge for this. I did not thought that it could be reduced by so much.

Here is the code, 422 characters:

```
x=prompt(E=eval);W=x[f=5]=='W';A=x.match(/\d+/g);y=+A[a=0];for(t="'012011223445569'[z]-30+30*z";q=a%4<1&(a%100>0|a%400<1),a++<y;f=(f+1+q)%7)v=f;z=w=+A[1]-W;r=+A[2];if(W){w+=f>3;h=7*w+r-f;for(z=1;h-q*(z>2)>=E(t);++z);w=1+(10+z--)%12;d=h-q*(z<3)-E(t);y+=z?z>12:-1}else{g=r+E(t)-(w>1&&!q+w-2?2-q:2);d=(f+g)%7;w=0|g/7+(f<4);w=w>11&r-d>26?(++y,1):w<1?(--y,53^v>3):w}alert(y+(W?'-':'-W')+(w>9?'':0)+w+'-'+(!W|++d>9?'':0)+d+'\n')

```

Pretty complex. Here a (somewhat long) partially-ungolfed (but still badly obfuscated) and commented version:

```
x = prompt(E = eval); // Receives input, but has a side-effect of having a strange message in the prompt box.

// Year 0 of the Gregorian calendar (if such thing existed) would start on a 5=Friday. (0=Monday, 6=Sunday)
W = x[f = 5] == 'W'; // Checks if there is a W in the sixth char.
A = x.match(/\d+/g); // Divide the input in 3 numbers.

y = +A[a = 0]; // Parse the year.

// The t variable is used to create a table with cumulative months length starting from December of the previous year, this table is acessed by using the eval() function.
// Calculate the weekday of 01/01 of the year in the f variable. Do that by counting Gregorian calendar years from 0 until now.
// Count 2 weekdays for leap years and 1 for non-leap years.
// The variable q defines if the year is a leap year.
// The v variable stores the weekday of 01/01 of the prevoius year.
// The % 7 ensures that the weekday are kept in the interval 0-6, where 0 is Monday and 6 is Sunday.
for (t = "'012011223445569'[z] - 30 + 30 * z"; q = a % 4 < 1 & (a % 100 > 0 | a % 400 < 1), a++ < y; f = (f + 1 + q) % 7)
  v = f;

z = w = +A[1] - W; // Parse the second number, might be the week number or the month, accordingly to the W.
r = +A[2]; // Parse the third number, might be the week day or the day in the month, accordingly to the W.

// Converts week date to calendar date.
if (W) {

  // The expression "7 * (f > 3) - f" maps the offset between the calendar date and the week date in the following manner:
  // {0Mon:1, 1Tue:0, 2Wed:-1, 3Thu:-2, 4Fri:4, 5Sat:3, 6Sun:2}
  // Obtain the day within the year and store it in h.
  w += f > 3;
  h = 7 * w + r - f;

  // Finds the day offset in the table to the corresponding month.
  for (z = 1; h - q * (z > 2) >= E(t); ++z);

  // This calculates the day in the month and the month.
  w = 1 + (10 + z--) % 12;
  d = h - q * (z < 3) - E(t);

  // Fix-up the year, if needed.
  y += z ? z > 12 : -1

// Converts calendar date to week date.
} else {

  // Calculate how many days passed since 01/01
  g = r + E(t) - (w > 1 && !q + w - 2 ? 2 - q : 2);

  // Knowing the week day in which the year started and how many days passed since 01/01, calculate the week day of the given date.
  d = (f + g) % 7;

  // Calculates how many weeks passed since 01/01 and add one week if the year started on Monday, Tuesday, Wednesday or Thursday.
  w = 0 | g / 7 + (f < 4);

  // If we are in the last 3 days of the year, and 01/01 will fall on Monday, Tuesday, Wednesday or Thursday,
  // then we advance to the first week of the next year.
  // Do this by checking r + 3 - (d - 2) > 31, where:
  //   r is the date;
  //   (d - 2) is the weekday (d=1 for monday, 7 for sunday);
  //   (3 - (d - 2)) is the number of days until the week's Thursday and;
  //   > 31 means January of the next year.
  // r + 3 - (d - 2) > 31 is simplified to r - d > 26.
  w = w > 11 & r - d > 26 ? (++y, 1)

  // If we are at the 0th week of the year, go back to the last week of the previous year.
  // If the last year started on Friday, Saturday or Sunday this would be the 52nd week. It is the 53rd otherwise.
    : w < 1 ? (--y, 53 ^ v > 3)

  // Neither of the previous two cases.
    : w
}

// Output it.
alert(y + (W ? '-' : '-W') + (w > 9 ? '' : 0) + w + '-' + (!W | ++d > 9 ? '' : 0) + d + '\n')

```

The prompt box comes with the message with the serialization of the `eval` function. Ignore this message, it is just a side-effect of golfing some chars.

It passes for all provided test cases. If given invalid input, the behaviour is undefined.

Here are the test cases, had some bugs in previous versions (specially with the last two lines):

```
2014-02-27  <-->  2014-W09-4
2008-12-30  <-->  2009-W01-2
2010-01-03  <-->  2009-W53-7
2011-04-23  <-->  2011-W16-6
2012-01-01  <-->  2011-W52-7

```

In case you are curious, here it is the original, 825 characters code:

```
p=parseInt;x=prompt();y=p(x.substr(0,4));f=6;j="a%4<1&(a%100>0|a%400<1)";for(a=1583;a<y;a++)f+=eval(j)?2:1;f%=7;q=eval(j);if(x.contains('W')){w=p(x.substr(6,2))-1;r=p(x.substr(9))-1;u=f<1?3:f<5?1-f:f-4;h=w*7+r+u+1;e=q?1:0;d=h<1?(m=12,y--,h+31):h<32?(m=1,h):h<60+e?(m=2,h-31):h<91+e?(m=3,h-59-e):h<121+e?(m=4,h-90-e):h<152+e?(m=5,h-120-e):h<182+e?(m=6,h-151-e):h<213+e?(m=7,h-181-e):h<244+e?(m=8,h-212-e):h<274+e?(m=9,h-243-e):h<305+e?(m=10,h-273-e):h<335+e?(m=11,h-304-e):h<366+e?(m=12,h-334-e):(m=1,y++,h-365-e);alert(y+'-'+(m<10?'0':'')+m+'-'+(d<10?'0':'')+d+'\n')}else{m=p(x.substr(5,2));d=p(x.substr(8));g=d-1;for(b=1;b<m;b++)g+=[31,q?29:28,31,30,31,30,31,31,30,31,30,31][b-1];v=(f+g)%7;w=~~(g/7)+(f>0&f<5?1:0);if(v<1)w--,v=7;if(m>11&d>28&32-d+f>3)w=1,y++;if(w<1)w=53,y--;alert(y+'-W'+(w<10?'0':'')+w+'-'+(v<1?7:v)+'\n')}

```
> 9 votes

# Answer
# C: 286 characters

In a quite unorthodox fashion I will give an entry to my own challenge (but I will not accept this answer even if it is the shortest when the time comes), just to show another (much less elegant than the JS-solution) way to attack the problem.

```
I[9],C[9],W[9],Y,M=5,D,y,w,d;main(){for(gets(I);sprintf(C,"%d-%02d-%02d",Y,M,D),sprintf(W,"%d-W%02d-%d",y,w,d),(strcmp(I,C)||puts(W)<0)&&(strcmp(I,W)||puts(C)<0);++D>28+(M^2?M+(M>7)&1^2:!(Y&3)&&(Y%25||!(Y&15)))&&(D=1,M=M%12+1)<2&&Y++,(d=d%7+1)<2&&(M>11&&D>28||M<2&&D<5?(w=1,y++):w++));}

```

I simply simulate the calendars day by day, increasing the month, week, year and week-year as needed. When either the week date or calendar date is equal to what was inputted I output the date in the format it wasn't inputted in (so if the input is invalid it will simply loop forever).

In a slightly more readable form:

```
I[9],C[9],W[9],Y,M=5,D,y,w,d;
main(){
        for(
                gets(I);

                sprintf(C,"%d-%02d-%02d",Y,M,D),
                sprintf(W,"%d-W%02d-%d",y,w,d),

                (strcmp(I,C)||puts(W)<0)&&
                (strcmp(I,W)||puts(C)<0);

                ++D>28+(M^2?M+(M>7)&1^2:!(Y&3)&&(Y%25||!(Y&15)))&&
                (D=1,M=M%12+1)<2&&Y++,

                (d=d%7+1)<2&&
                (M>11&&D>28||M<2&&D<5?(w=1,y++):w++)
        );
}

```
> 4 votes

---
Tags: code-golf
---


title: Writing firewall rules

text:
# Question
Title: Writing firewall rules
Congratulations, you're now a network administrator! As your first task you will need to configure a firewall to stop any traffic to some blacklisted addresses.

Unfortunately, the only firewall at your disposal only takes in rules in this format:

`x.y.z.t/m ALLOW`

There's no `DENY` keyword. If you want to exclude a specific address, you'll have to write a lot of rules to allow everything **except** that address. If you want to exclude more than one address or a whole range, then you're in luck because these `ALLOW` rules will overlap to some degree.

### The challenge

You are given a list of blacklisted IPs. Write a program that will print out rules for our firewall. Also, be sensible when writing rules: don't just enumerate all 256^4 and don't print out duplicates.

Code golf rules apply: **shortest code wins**

*\*this problem is inspired by a real life assignment; a friend actually needed this done*

### Example

To block address 0.1.2.3 you could write the following `ALLOW` rules (this is not the only solution possible, and it's certainly not the shortest):

```
0.1.2.0 ALLOW
0.1.2.1 ALLOW
0.1.2.2 ALLOW
0.1.2.4 ALLOW
...
0.1.2.255 ALLOW

0.1.0.0/24 ALLOW
0.1.1.0/24 ALLOW
0.1.4.0/24 ALLOW
...
0.1.255.0/24 ALLOW

0.0.0.0/16 ALLOW
0.2.0.0/16 ALLOW
...
0.255.0.0/16 ALLOW

1.0.0.0/8 ALLOW
...
255.0.0.0/8 ALLOW

```

# Answer
# Python3 - 325 chars

```
import sys
r=[(0,32)]
for b in (int('%02x'*4%tuple(int(x) for x in y.split('.')),16) for y in sys.stdin):
 i=0
 while i<len(r):l,q=r[i];o=2**q//2;m=l+o;h=m+o;k=l<=b<h;r[i:i+1]=[(l,q-k),(m,q-k)][0:k+1*(not l==h==b)];i+=1-k
for n,m in r:print('%s/%d ALLOW'%('.'.join(str(int(('%08x'%n)[i:i+2],16)) for i in range(0,8,2)),32-m))

```
> 1 votes

# Answer
# Python 3: 253 characters

Yay, Python!

```
from ipaddress import *
import sys
def e(x,a):
 b=[]
 for i in a:
  try: b+=i.address_exclude(ip_network(x))
  except ValueError: b+=[i]
 return b
a=[ip_network('0.0.0.0/0')]
for h in sys.stdin:
 for i in h.split(): a=e(i,a)
for i in a: print(i,'ALLOW')

```

It accepts a list of addresses on stdin, separated by any (ASCII) whitespace you like (no commas, though).

You can save 12 characters by replacing the stdin loop with `for i in sys.stdin: a=e(i.strip(),a)`. The `strip()` is necessary to get rid of a trailing newline anyway, though, so I figured I'd use `split()` and another `for` loop and allow any whitespace.

You can probably save a few more characters by moving the code out of that pesky function. I didn't because I figured I was already confusing myself enough.

You can also make it work for IPv6 instead by changing only one line.

## Ungolfed version:

```
#!/usr/bin/env python3

import ipaddress
import sys

def exclude(address, networks):
    new_networks = []
    for network in networks:
        try:
            new_networks.extend(network.address_exclude(ipaddress.ip_network(address)))
        except ValueError:
            new_networks.append(network)
        except TypeError:
            pass
    return new_networks

networks = [ipaddress.IPv6Network('::/0'), ipaddress.IPv4Network('0.0.0.0/0')]
for line in sys.stdin:
    for address in line.split():
        networks = exclude(line, networks)

for network in networks:
    print(network)

```

This one has the added benefit of working for IPv4 *and* IPv6, no tweaking necessary. :)
> 1 votes

# Answer
# PHP 5.3, 465 characters

```
$r=array_map(function($v){return explode('.',$v);},$w);$l=256;$n=" ALLOW\r\n";$o='';$a=$b=$c=$d=range(0,$l-1);foreach($r as$i){unset($a[$i[0]],$b[$i[1]],$c[$i[2]],$d[$i[3]]);}for($x=0;$x<$l;$x++){for($y=0;$y<$l;$y++){for($z=0;$z<$l;$z++){for($t=0;$t<$l;$t++){$k="$x.$y.$z.$t";if(isset($a[$x])){$o.="$k/8$n";break 3;}elseif(isset($b[$y])){$o.="$k/16$n";break 2;}elseif(isset($c[$z])){$o.="$k/24$n";break;}else$o.=isset($d[$t])?"$k$n":'';}}}}file_put_contents($p,$o);

```

**Usage:**

```
$w = array('2.5.5.4', '1.2.3.4');
$p = 'data.txt';
$r=array_map(function($v){return explode('.',$v);},$w);$l=256;$n=" ALLOW\r\n";$o='';$a=$b=$c=$d=range(0,$l-1);foreach($r as$i){unset($a[$i[0]],$b[$i[1]],$c[$i[2]],$d[$i[3]]);}for($x=0;$x<$l;$x++){for($y=0;$y<$l;$y++){for($z=0;$z<$l;$z++){for($t=0;$t<$l;$t++){$k="$x.$y.$z.$t";if(isset($a[$x])){$o.="$k/8$n";break 3;}elseif(isset($b[$y])){$o.="$k/16$n";break 2;}elseif(isset($c[$z])){$o.="$k/24$n";break;}else$o.=isset($d[$t])?"$k$n":'';}}}}file_put_contents($p,$o);

```

This will write to data.txt

**Uncompressed:**

```
$deny = array('2.5.5.4', '1.2.3.4');
$file = 'data.txt';

$list = array_map(function($v){return explode('.', $v);}, $deny);
$l = 256;
$n = " ALLOW\r\n";$o = '';

$first = $second = $third = $fourth = range(0,$l-1);
foreach($list as $ip){unset($first[$ip[0]], $second[$ip[1]], $third[$ip[2]], $fourth[$ip[3]]);}

for($x=0;$x<$l;$x++){
    for($y=0;$y<$l;$y++){
        for($z=0;$z<$l;$z++){
            for($t=0;$t<$l;$t++){
                if(isset($first[$x])){
                    $o .= "$x.0.0.0/8$n";break 3;
                }else{
                    if(isset($second[$y])){
                        $o.="$x.$y.0.0/16$n";break 2;
                    }else{
                        if(isset($third[$z])){
                            $o.="$x.$y.$z.0/24$n";break 1;
                        }else{
                            if(isset($fourth[$t])){
                                $o.="$x.$y.$z.$t$n";
                            }
                        }
                    }
                }
            }
        }
    }
}

file_put_contents($file, $o);

```
> 0 votes

---
Tags: code-golf
---


title: Inverse CIDR whitelist

text:
# Question
Title: Inverse CIDR whitelist
# The task

The task is to write a program that turns a list of IPv6 addresses into a shortest possible list of CIDR masks, such that everything but those IPs is matched.

# CIDR masks

A CIDR mask matches IPs by a prefix. `::/19` matches all IPs whose first 19 bits are zero, i.e. `0:0000-1fff:*:*:*:*:*:*`. Similarly, `55aa::/16` matches all IPs that start with `0101010110101010` bit sequence, i.e. `55aa:*:*:*:*:*:*:*`.
A `/128` always matches only one IP. A `/0` matches all IPs.

# Input

Input is a list of IP addresses in full form: eight 4-digit hexadecimal groups separated by `:` in network order (most significant first). For example, `0000:0000:0000:0000:0000:0000:0000:0000`.
You're free to choose any separation character for the input list, might it be newline, space, comma, `\0`, etc. You can also rely on `a-f` being in a particular case.

# Output

Output is the shortest list of CIDR masks that cover all IP addresses except those listed in input.
Again you're free to choose any separation character.
The CIDR should be formatted as any representation of an IP followed by `/` and amount of bits in the prefix (in decimal). For example, `0243:F6A8:885A:308D:3131:98A2:0000:0000/112`.
You are not required to shorten the IP at all, as in above example. However `243:f6a8:885a:308d:3131:98a2::/112` is not invalid.
The order of masks doesn't matter. If there are multiple representations using equal amount of masks - either will suffice.

# Examples

I'm not posting complete outputs, since coming up with an algorithm is a part of the task :)
Instead I'm specifying how much masks does it take, according to my own calculations. If you find a mistake, or a shorter masklist, please report.

```
>>> 0000:0000:0000:0000:0000:0000:0000:0000
 [128 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:0000 0000:0000:0000:0000:0000:0000:0000:0001
 [127 masks]
>>> ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff 0000:0000:0000:0000:0000:0000:0000:0000
 [254 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:ffff 0000:0000:0000:0000:0000:0000:0000:0000
 [142 masks]
>>> 0123:4567:89ab:cdef:fedc:ba98:7654:3210 0246:8ace:1357:9bdf:0246:8ace:1357:9bdf
 [248 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:0000 0000:0000:0001:0000:0000:0000:0000:0000 0000:0000:0002:0000:0000:0000:0000:0000 0000:0000:0003:0000:0000:0000:0000:0000 0000:0000:0004:0000:0000:0000:0000:0000 < snip > 0000:0000:00ff:0000:0000:0000:0000:0000
 (256 IPs)
 [20520 masks]
>>> 0000:0000:0000:0000:0000:0000:0000:0000 0000:0000:0000:0000:0000:0000:0000:0001 0000:0000:0000:0000:0000:0000:0000:0002 0000:0000:0000:0000:0000:0000:0000:0003 0000:0000:0000:0000:0000:0000:0000:0004 < snip > 0000:0000:0000:0000:0000:0000:0000:0fff
 (4096 IPs)
 [116 masks]

```

# Scoring

Amount of characters in the code, UTF-8 characters are counted as one, if you must.

### Bonus points

* **-16** Cover the case of empty input list.
* **-32** Output shortened IPs: strip leading zeros, replace sequential zero groups with `::`, etc. See this Wikipedia article.
    + **-32** Do not use the v4-in-v6 form (`dead::beef:1.2.3.4`).
* **-64** Permit shortened IPs in input.

# Answer
> 3 votes
### GolfScript, 120 (136 characters - 16 bonus)

```
n%{':'-{48^71%}%16base}%-1+2.7??:W+${\)1$1$-{}{129,-1%{2\?.2$)<3$@%!&}?:~2$W+16base(;{.48+\9>39*+}%4/':'*'/'+128@-+puts\2~?+\2~?-}/;;}*;

```

Assumes the addresses as separate lines on STDIN. A considerable amount of the code is actually used to input/output in the correct format. The algorithm itself is quite simple and described here.

# Answer
> 1 votes
# Python 3: 128 points

(240 characters - (16 + 32 + 64) bonus points)

Yay, Python!

(I used the standard library instead of actually writing my own algorithm. Is that cheating?)

```
from ipaddress import *
import sys
def e(x,a):
 b=[]
 for i in a:
  try: b+=i.address_exclude(ip_network(x))
  except ValueError: b+=[i]
 return b
a=[ip_network('::/0')]
for h in sys.stdin:
 for i in h.split(): a=e(i,a)
for i in a: print(i)

```

It accepts a list of addresses on stdin, separated by any (ASCII) whitespace you like (no commas, though).

If stdin is empty (or has only whitespace), it will print `::/0` (-16 points). It also prints (-32) and handles (-64) shortened IPs.

You can save 12 characters by replacing the stdin loop with `for i in sys.stdin: a=e(i.strip(),a)`. The `strip()` is necessary to get rid of a trailing newline anyway, though, so I figured I'd use `split()` and another `for` loop and allow any whitespace.

You can probably save a few more characters by moving the code out of that pesky function. I didn't because I figured I was already confusing myself enough.

You can also make it work for IPv4 instead by changing only one line.

## Ungolfed version:

```
#!/usr/bin/env python3

import ipaddress
import sys

def exclude(address, networks):
    new_networks = []
    for network in networks:
        try:
            new_networks.extend(network.address_exclude(ipaddress.ip_network(address)))
        except ValueError:
            new_networks.append(network)
        except TypeError:
            pass
    return new_networks

networks = [ipaddress.IPv6Network('::/0'), ipaddress.IPv4Network('0.0.0.0/0')]
for line in sys.stdin:
    for address in line.split():
        networks = exclude(line, networks)

for network in networks:
    print(network)

```

This one has the added benefit of working for IPv4 *and* IPv6, no tweaking necessary. :)

---
Tags: code-challenge
---