title: Produce the number 2014 from an image

text:
# Question
Title: Produce the number 2014 from an image
In the 2014 challenge, Michael Stern suggests using OCR to parse to 2014. I'd like to take this challenge in a different direction. Using built-in OCR from the language/standard library of your choice, design the smallest image (in bytes) which is parsed into the ASCII string "2014".

Stern's original image is 7357 bytes, but with a bit of effort it can be losslessly compressed to 980 bytes. No doubt the black-and-white version (181 bytes) works as well with the same code.

Rules: Each answer should give the image, its size in bytes, and the code needed to process it. No custom OCR allowed, for obvious reasons...! Any reasonable languages and image formats are allowed.

*Edit:* In response to comments, I'll broaden this to include any preexisting library, or even http://www.free-ocr.com/ for those languages where no OCR is available.

# Answer
> 11 votes
# Shell (ImageMagick, Tesseract), 18 bytes

```
file=golf_2014
echo -n UDQKMTMgNQruqCqo6riKiO6I | base64 -d > $file.pbm
convert -border 2x2 -bordercolor white -resize 300% -sharpen 0 -monochrome $file.pbm $file.png
tesseract $file.png $file digits
cat $file.txt
rm $file.pbm $file.png $file.txt

```

The image is 18 bytes and can be reproduced like this:

```
echo -n UDQKMTMgNQruqCqo6riKiO6I | base64 -d > 2014.pbm

```

It looks like this (this is a PNG copy, not the original):

After processing with ImageMagick, it looks like this:

Using ImageMagick version 6.6.9-7, Tesseract version 3.02. The PBM image was created in Gimp and edited with a hex editor.

---

This version requires `jp2a`.

```
file=golf_2014
echo -n UDQKMTMgNQruqCqo6riKiO6I | base64 -d > $file.pbm
convert -border 2x2 -bordercolor white -resize 300% -sharpen 0 -monochrome $file.pbm $file.png
tesseract $file.png $file digits
cat $file.txt
convert -background black -fill white -border 2x2 -bordercolor black -pointsize 100 label:$(cat $file.txt) $file.jpg
jp2a --chars=" $(cat $file.txt) " $file.jpg
rm $file.pbm $file.png $file.txt $file.jpg

```

It outputs something like this:

```
    2014444444102         01144444102              214441                 214441
   1             1      24           1            04    4                0     4
  1    410201     0    0    410004    1       2014      4              21      4
 24   42     0    4    4    0     1    0    24          4             04       4
  22222      1    1   0    42     0    4    2   4100    4            1   41    4
            1    42   0    4      2     2   2412   0    4          24   420    4
          04    42    0    1      2     2          0    4         0   40  0    4
       204    42      0    1      2     2          0    4       24   42   0    4
     21     12        0    4      0    42          0    4      2     411114     1112
    04   412          24    0     1    0           0    4      0                   0
  24     1111111110    1    42  21    4            0    4      200011111001    40002
  4               4     04    44     42            0    4                 0    4
 0                4      214       10              0    4                 0    4
  22222222222222222         222222                  22222                  22222

```

# Answer
> 5 votes
# Java + Tesseract, 53 bytes

Since I don't have Mathematica, I decided to ~~bend the rules a bit and~~ use Tesseract to do the OCR. I wrote a program that renders "2014" into an image, using various fonts, sizes and styles, and finds the smallest image that gets recognized as "2014". Results depend on the available fonts.

Here is the winner on my computer - 53 bytes, using the "URW Gothic L" font:

Code:

```
import java.awt.Color;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics2D;
import java.awt.GraphicsEnvironment;
import java.awt.image.BufferedImage;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;

import javax.imageio.ImageIO;

public class Ocr {
    public static boolean blankLine(final BufferedImage img, final int x1, final int y1, final int x2, final int y2) {
        final int d = x2 - x1 + y2 - y1 + 1;
        final int dx = (x2 - x1 + 1) / d;
        final int dy = (y2 - y1 + 1) / d;
        for (int i = 0, x = x1, y = y1; i < d; ++i, x += dx, y += dy) {
            if (img.getRGB(x, y) != -1) {
                return false;
            }
        }
        return true;
    }

    public static BufferedImage trim(final BufferedImage img) {
        int x1 = 0;
        int y1 = 0;
        int x2 = img.getWidth() - 1;
        int y2 = img.getHeight() - 1;
        while (x1 < x2 && blankLine(img, x1, y1, x1, y2)) x1++;
        while (x1 < x2 && blankLine(img, x2, y1, x2, y2)) x2--;
        while (y1 < y2 && blankLine(img, x1, y1, x2, y1)) y1++;
        while (y1 < y2 && blankLine(img, x1, y2, x2, y2)) y2--;
        return img.getSubimage(x1, y1, x2 - x1 + 1, y2 - y1 + 1);
    }

    public static int render(final Font font, final int w, final String name) throws IOException {
        BufferedImage img = new BufferedImage(w, w, BufferedImage.TYPE_BYTE_BINARY);
        Graphics2D g = img.createGraphics();
        float size = font.getSize2D();
        Font f = font;
        while (true) {
            final FontMetrics fm = g.getFontMetrics(f);
            if (fm.stringWidth("2014") <= w) {
                break;
            }
            size -= 0.5f;
            f = f.deriveFont(size);
        }
        g = img.createGraphics();
        g.setFont(f);
        g.fillRect(0, 0, w, w);
        g.setColor(Color.BLACK);
        g.drawString("2014", 0, w - 1);
        g.dispose();
        img = trim(img);
        final File file = new File(name);
        ImageIO.write(img, "gif", file);
        return (int) file.length();
    }

    public static boolean ocr() throws Exception {
        Runtime.getRuntime().exec("/usr/bin/tesseract 2014.gif out -psm 8").waitFor();
        String t = "";
        final BufferedReader br = new BufferedReader(new FileReader("out.txt"));
        while (true) {
            final String s = br.readLine();
            if (s == null) break;
            t += s;
        }
        br.close();
        return t.trim().equals("2014");
    }

    public static void main(final String... args) throws Exception {
        int min = 10000;
        for (String s : GraphicsEnvironment.getLocalGraphicsEnvironment().getAvailableFontFamilyNames()) {
            for (int t = 0; t < 4; ++t) {
                final Font font = new Font(s, t, 50);
                for (int w = 10; w < 25; ++w) {
                    final int size = render(font, w, "2014.gif");
                    if (size < min && ocr()) {
                        render(font, w, "2014win.gif");
                        min = size;
                        System.out.println(s + ", " + size);
                    }
                }
            }
        }
    }
}

```

# Answer
> 1 votes
# Mathematica ~~753~~ 100

```
f[n_,format_]:=
Module[{filename},
Print["raster: ",n," by ", n];
filename="2014At"<>ToString[n]<>"."<>format;
Print["filename:  ",filename];
Print["format: ",format];
Print["raster image: ",rasterImg=Rasterize[Style[2014,"OCR A Std"],
RasterSize->n,ImageSize->1n,ImageResolution->6n]];
Export[filename,rasterImg];
Print["Actual imported image: ",img=Switch[format,"PDF"|"HDF",Import[filename][[1]],
_,Import[filename]]];
Print["Identified text: ",TextRecognize[ImageResize[img,Scaled[3]]]];
Print["filesize (bytes): ",FileByteCount[filename]]]

```

My best case so far:

```
f[24, "PBM"]

```

# Answer
> 1 votes
## Mathematica, 78 bytes

The trick to winning this in Mathematica will probably be use of the ImageResize\[\] function as below.

First, I created the text "2014" and saved it to a GIF file, for fair comparison with David Carraher's solution. The text looks like . This is not optimized in any way; it's just Geneva in a small font size; other fonts and smaller sizes may be possible. Straight TextRecognize\[\] would fail, but TextRecognize\[ImageResize\[\]\]\] has no problem

```
filename = "~/Desktop/2014.gif";
Print["Actual imported image: ", img = Import[filename]]
Print["Identified text: ",
 TextRecognize[ImageResize[img, Scaled[2]]]]
Print["filesize (bytes): ", FileByteCount[filename]]

```

Fussing with the typeface, font size, degree of scaling, etc., will probably result in even smaller files that work.

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


title: calculate the combinatorial

text:
# Question
Title: calculate the combinatorial
Given two integers - n and r, your task is to calculate the combinatorial nCr.

```
nCr = n! / r! (n-r)!

```

The caveat is that you have to write code to do this calculation in minimum number of characters.

Input The first line will be number of testcases T. Then T lines follow, each containing two positive integers - n and r.

output Print T lines, each line containing the value of nCr.

Constraints

```
1 <= T <= 100
1 <= r <= n <= 1000

```

You can assume that the value nCr will fit into a signed 64 bit integer.

# Answer
# Golfscript, 31 characters

```
n%(;{~.@.@-]{1\,{)*}/}%~/\/}%n*

```

Explanation:

* `n/(;{...}%n*` splits the input by a newline, discards the first row (number of testcases), maps the rest and finally joins by a newline.
    + `~.@.@-` evals the input, rearranges it to `r n n r`, then subtracts `r` from `n`.
    + `]{...}%~` collects everything on the stack into and array, maps it and explodes the array
        - `1\,{)*}/` is the factorial function: push a `1` below the number, then create an array `0...n`, then for each element, multiply the accumulator by the value + 1. The map-reduce implementation is one char longer: `,{)}%{*}*`
    + `/\/` divides `n!` first by factorial of the difference, then by `r!`.
> 2 votes

---
Tags: code-golf
---


# Question
Title: How many unique ways are there to achieve a score in Football?
Challenge: given a number, calculate how many unique, order-independent ways there are to achieve a score of that number in American Football.

Let's see how few characters can be used in each of your favorite languages! The usual rules apply. Input and output in a way that is natural to your language.

Recall that the ways to score in Football are safety (2 points), field goal (3 points), touchdown (6 points), touchdown + extra point (7 points), and touchdown + 2-point conversion (8 points).

For example, given 9 as input, the program should return 4, since you could score:

* 1 touchdown + extra point and 1 safety
* 1 touchdown and 1 field goal
* 3 field goals
* 3 safeties and 1 field goal

Note that order does not matter.

# Answer
> 5 votes
# Mathematica - 42

```
Length@IntegerPartitions[#,∞,{2,3,6,7,8}]&

```

# Prolog - 140

Never wrote anything in Prolog before, just knew that this problem should be quite nice for it.

```
p(0,_,[]).
p(N,[H|T],O):- N>=H,p(N,T,O).
p(N,[H|S],[H|T]):- N>=H,M is N-H,p(M,[H|S],T).
f(N,C):- aggregate(count,X^p(N,[2,3,6,7,8],X),C).

?- f(9,C).
C = 4.

```

# Answer
> 0 votes
## Python - 146

```
t=int(input())
from itertools import*
print len([a for a in chain(*(combinations_with_replacement([2,3,6,7,8],n) for n in range(t)))if sum(a)==t])

```

---
Tags: code-golf, combinatorics
---


title: Search for files on your computer

text:
# Question
Title: Search for files on your computer
# Task

Write some code that will walk through the entire file-system tree and collect details from file-names, folder-names, text files etc to form a tag-group. This tag group, when searched in (user input) should point to the folders they are located in.

# Rules

1. Any Language (standard libraries only).
2. Any kind of output (should be legible).
3. You may extend your code by reading more file-types and their metadata.
4. Regex is allowed

# You'll win

1. +14 points for the shortest code (will be taken away when some else beats the record)
2. +6 for each added functionality (anything you could possibly claim).
3. -2 for each byte exceeding 1024 byte mark.

# Example

```
Python (using os module - os.walk)

```

input

```
Enter search term below
>>> *camp*

```

output

```
Total results for *camp* = 2
-------------------------------
Camping.avi       - "C:\Users\Amelia\Videos\Summer Camping"
Campus party.avi  - "C:\Users\Public\Campus"

```

# Answer
## BASH, 14 + 6\*18 = 122

Cheap, but a win.

```
locate

```

Example:

```
boothby@not ~ $ locate camp
/home/boothby/Desktop/kodak/Pictures/camp.jpg
/home/boothby/Desktop/kodak/Pictures/camp2.jpg
/home/boothby/Downloads/sage-5.12/local/share/doc/networkx-1.7.dev_20131124172629/examples/graph/napoleon_russian_campaign.py
/usr/src/linux-headers-3.8.0-19/arch/arm/plat-samsung/include/plat/camport.h
/usr/src/linux-headers-3.8.0-33/arch/arm/plat-samsung/include/plat/camport.h

```

Feature: this is super efficient since it caches the file information in a database. The above runs on my computer in 0.187s.

... and 17 additional features:

```
   -b, --basename
          Match only the base name against the specified  patterns.   This
          is the opposite of --wholename.

   -c, --count
          Instead of writing file names on standard output, write the num‐
          ber of matching entries only.

   -d, --database DBPATH
          Replace the default database with DBPATH.  DBPATH is  a  :-sepa‐
          rated  list of database file names.  If more than one --database
          option is specified, the resulting path is  a  concatenation  of
          the separate paths.

          An empty database file name is replaced by the default database.
          A database file name - refers to the standard input.  Note  that
          a database can be read from the standard input only once.

   -e, --existing
          Print  only  entries  that  refer  to files existing at the time
          locate is run.

   -L, --follow
          When checking whether files exist (if the --existing  option  is
          specified),  follow trailing symbolic links.  This causes broken
          symbolic links to be omitted from the output.

          This is the default behavior.  The  opposite  can  be  specified
          using --nofollow.

   -h, --help
          Write  a summary of the available options to standard output and
          exit successfully.

   -i, --ignore-case
          Ignore case distinctions when matching patterns.

   -l, --limit, -n LIMIT
          Exit successfully after finding LIMIT entries.  If  the  --count
          option  is  specified,  the  resulting  count is also limited to
          LIMIT.

   -m, --mmap
          Ignored, for compatibility with BSD and GNU locate.

   -P, --nofollow, -H
          When checking whether files exist (if the --existing  option  is
          specified),  do not follow trailing symbolic links.  This causes
          broken symbolic links to be reported like other files.

          This is the opposite of --follow.

   -0, --null
          Separate the entries on output using  the  ASCII  NUL  character
          instead  of  writing each entry on a separate line.  This option
          is designed for interoperability with the --null option  of  GNU
          xargs(1).

   -S, --statistics
          Write  statistics  about  each  read database to standard output
          instead of searching for files and exit successfully.

   -q, --quiet
          Write no messages about errors  encountered  while  reading  and
          processing databases.

   -r, --regexp REGEXP
          Search  for  a  basic regexp REGEXP.  No PATTERNs are allowed if
          this option is used, but this option can be  specified  multiple
          times.

   --regex
          Interpret all PATTERNs as extended regexps.

   -V, --version
          Write  information  about  the  version and license of locate on
          standard output and exit successfully.

   -w, --wholename
          Match only the whole path name against the specified patterns.

          This is the default behavior.  The  opposite  can  be  specified
          using --basename.

```
> 14 votes

# Answer
BASH

```
find

```

A cheaper, *shorter* win. See @boothby answer for examples
> 5 votes

# Answer
**C# - 200**

```
void G(string s){foreach (var y in Directory.GetFiles(@"C:\").Where(k => k.ToLower().Contains(s.ToLower())))foreach (var f in Directory.GetDirectories(@"C:\")){Console.WriteLine(y);try{G(f);}catch{}}}

```
> 2 votes

# Answer
# Groovy (59)

```
a={b-> new File("c:\\").traverse(nameFilter: ~b){print it}}

```

Call it with

```
a('test')

```
> 1 votes

---
Tags: code-challenge
---


# Question
Title: Packing binary data to source-safe ascii efficiently
# Description

Here's a challenge with a somewhat practical use, at least for us golfers.

Your mission, should you choose to accept it, is to write a program that can take arbitrary binary data (either from stdin, or a file) and output some valid source code which provides access to the data. The generator and target languages need not be the same.

# Scoring

Your program will be run against two inputs: a 1 KiB file of random characters, and the lyrics of Never Gonna Give You Up by Rick Astley. The program with the lowest score wins. Your score is calculated as follows:

> (**A** \+ **B**) × loge(**Z**)

Where:

* **A** is the number of bytes in the output for the random data;
* **B** is the number of bytes in the output for Never Gonna Give You Up; and
* **Z** is the number of useful bytes in the target programming language *(useful is a very broad definition and may be refined in the future)*

For example:

* in C++ the generally allowed characters are `"\t \r\nABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!\"#%&'()*+,-./:;<=?[\\]^_{|}~"` which would give **Z** = 94
* in Brainfuck the only non-ignored characters are `"<>+-.,[]"` which gives **Z** = 8

# Examples

Two examples in Python, both generating python source:

*Python allows files encoded in UTF-16, so the valid python bytes are from 0x00-0xFF*

### Using Repr

```
import sys
print 'data=',repr(sys.stdin.read())

```

Score: (2898 + 2098) × loge(256) = 27,704

### Using Base64

```
import sys
from base64 import b64encode
print 'from base64 import b64decode;data=b64decode("'+b64encode(sys.stdin.read())+'")'

```

Score: (1416 + 2640) × loge(256) = 22,491

# Data

The data is given here encoded in base64, these files should be decoded prior to passing to your program. The decoding is outside of the scope of this challenge.

### Random

```
2moE8CGQCSSr8V4uHaeKMvtJUtStqVwvgn3xGgCWIlRWaEjVTLmF/fn0heXYh7GIPAUSZmEa2pR5
KTuLfLVtPMi8eUg5903zd/b57BIVJEPGVOyBhzxGTlzYEVG3uaUwnSOlpw9zP5SK/vjDNDCdF4IJ
ZBg8cHloaoxqw1Bm306GV6v6/Gzx+MHcCOsUyT0MyqOAgbuA4t568QTT82zd/nbZQ2BE9Q6bmIwo
tfBCTPwV0TShetCufxZJBbnVrNlDW8BDnKMGzqws/dJT+C03ndd64sszj/Quvri74Earfg6/07ea
Gh5KY8onMhpRiB/k/M6aHpA/glmaFNE5Gu0TsKVgNCHUCP1Dqb9MKR3FU21Dg6fNttR4m+ZJNtbU
yMy6nWTuBx/N7hcUXIdn5FF6X5r+EdUtJxV1pegaDPsKO1Weag1TT5FqeIFEKyw2L9NX7QAsXuva
8Y/6/+iEH/ldIEe/ZHzPc5kqPtuip6l/y2+zleXLw7W4jQ1vLL0xbI4J0lQhpLniCc1K+5699TN8
+k01C16JdSQfEAx+dVlRq6m9Vf0uWonUWgrYsmvtY4hmC1AqKDIr9p6rB6zRL3d/8ctHeKwLZlmh
HCQYqyZURixVJnOkamIk8JP6xk82lC3PyCfP9fwHitguwK4Lnz6x22snqHvk8fW9iZbydWjjFW1+
SX2KE5M4pr7SKs+WzbGWks9FZNoHlGF4Ju1rT8zlYWUwX/3qZ2hHKuc+tXwedb75vj8NDeTiBAgD
/3L3ckt8Xw0JyFKCXv3nCJx3rC7oA1x1U7ZewlQTgCipPkUrRFehKYCjM42h8XCj1yVrbuL5fTvu
ZL5R/xOALz8XK0yxPqN5WgUtD4UFcxsmvAZ6OrbFysciud5hNHkZlr9Tr2oUtFvtx8o6eWH/eHO3
OJFyKiKdqDE/RzwnaPeND9DaZ3A2Jn/5RL+IHfWRlA5Q9i5plOg6v3ZMuGhPJX7tfqjtVW7z5OnR
pTZ2vpDMVwWUdygDbmjXg6xIFuVZzXR+hdoF3dGb0iBOkOlsvASNnmLs+ZSgJFYe03ydjFe8CVG8
Dogi7Ca9FtaGvOem8MqsjVS2sHDdLaQ6AHX0y3HEvhK+O3udAoTztIb/VILyaA9NVnxwiK5MCdfB
l0CHlRxmV2oDYaxxa58U2llEqn9adcTdp/eH/QVhfu32+c1x4pMMDPZxG9HBtOe5oIFEPUYth6zz
ttD/mfa0VRPM+Za1OWpa+SpFsV8spYc38c9d5t8x2ihNf2B0vN/t8Y3R0ge8iq6n/Tt2EGBRop7x
Vv013OMy5UUA7qiGexIv4xS2OUW8gSUbwxt2a+8Q5WQBw1LU7GLT6mDsZvQ+vsHqi34POcI+cQ==

```

### Never Gonna Give You Up

```
V2UncmUgbm8gc3RyYW5nZXJzIHRvIGxvdmUNCllvdSBrbm93IHRoZSBydWxlcyBhbmQgc28gZG8g
SQ0KQSBmdWxsIGNvbW1pdG1lbnQncyB3aGF0IEknbSB0aGlua2luZyBvZg0KWW91IHdvdWxkbid0
IGdldCB0aGlzIGZyb20gYW55IG90aGVyIGd1eQ0KSSBqdXN0IHdhbm5hIHRlbGwgeW91IGhvdyBJ
J20gZmVlbGluZw0KR290dGEgbWFrZSB5b3UgdW5kZXJzdGFuZA0KDQpOZXZlciBnb25uYSBnaXZl
IHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5k
IGFuZCBkZXNlcnQgeW91DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNh
eSBnb29kYnllDQpOZXZlciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpXZSd2ZSBr
bm93biBlYWNoIG90aGVyIGZvciBzbyBsb25nDQpZb3VyIGhlYXJ0J3MgYmVlbiBhY2hpbmcgYnV0
DQpZb3UncmUgdG9vIHNoeSB0byBzYXkgaXQNCkluc2lkZSB3ZSBib3RoIGtub3cgd2hhdCdzIGJl
ZW4gZ29pbmcgb24NCldlIGtub3cgdGhlIGdhbWUgYW5kIHdlJ3JlIGdvbm5hIHBsYXkgaXQNCkFu
ZCBpZiB5b3UgYXNrIG1lIGhvdyBJJ20gZmVlbGluZw0KRG9uJ3QgdGVsbCBtZSB5b3UncmUgdG9v
IGJsaW5kIHRvIHNlZQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0
IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91DQpOZXZlciBn
b25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZlciBnb25uYSB0
ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIg
Z29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91
DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZl
ciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQooT29oLCBnaXZlIHlvdSB1cCkNCihP
b2gsIGdpdmUgeW91IHVwKQ0KKE9vaCkNCk5ldmVyIGdvbm5hIGdpdmUsIG5ldmVyIGdvbm5hIGdp
dmUNCihHaXZlIHlvdSB1cCkNCihPb2gpDQpOZXZlciBnb25uYSBnaXZlLCBuZXZlciBnb25uYSBn
aXZlDQooR2l2ZSB5b3UgdXApDQoNCldlJ3ZlIGtub3cgZWFjaCBvdGhlciBmb3Igc28gbG9uZw0K
WW91ciBoZWFydCdzIGJlZW4gYWNoaW5nIGJ1dA0KWW91J3JlIHRvbyBzaHkgdG8gc2F5IGl0DQpJ
bnNpZGUgd2UgYm90aCBrbm93IHdoYXQncyBiZWVuIGdvaW5nIG9uDQpXZSBrbm93IHRoZSBnYW1l
IGFuZCB3ZSdyZSBnb25uYSBwbGF5IGl0DQoNCkkganVzdCB3YW5uYSB0ZWxsIHlvdSBob3cgSSdt
IGZlZWxpbmcNCkdvdHRhIG1ha2UgeW91IHVuZGVyc3RhbmQNCg0KTmV2ZXIgZ29ubmEgZ2l2ZSB5
b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVuIGFyb3VuZCBh
bmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBnb25uYSBzYXkg
Z29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0KTmV2ZXIgZ29u
bmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVu
IGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBn
b25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0K
TmV2ZXIgZ29ubmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIg
Z29ubmEgcnVuIGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5
DQpOZXZlciBnb25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVy
dCB5b3U=

```

# Answer
> 1 votes
## PHP 8986

```
<?php
$data = file_get_contents('php://stdin');
printf('$var=gzuncompress(base64_decode("%s"));', base64_encode(gzcompress($data)));

```

### Binary 1417

```
$var=gzuncompress(base64_decode("eJwBAAT/+9pqBPAhkAkkq/FeLh2nijL7SVLUralcL4J98RoAliJUVmhI1Uy5hf359IXl2IexiDwFEmZhGtqUeSk7i3y1bTzIvHlIOfdN83f2+ewSFSRDxlTsgYc8Rk5c2BFRt7mlMJ0jpacPcz+Uiv74wzQwnReCCWQYPHB5aGqMasNQZt9Ohler+vxs8fjB3AjrFMk9DMqjgIG7gOLeevEE0/Ns3f522UNgRPUOm5iMKLXwQkz8FdE0oXrQrn8WSQW51azZQ1vAQ5yjBs6sLP3SU/gtN53XeuLLM4/0Lr64u+BGq34Ov9O3mhoeSmPKJzIaUYgf5PzOmh6QP4JZmhTRORrtE7ClYDQh1Aj9Q6m/TCkdxVNtQ4OnzbbUeJvmSTbW1MjMup1k7gcfze4XFFyHZ+RRel+a/hHVLScVdaXoGgz7CjtVnmoNU0+RaniBRCssNi/TV+0ALF7r2vGP+v/ohB/5XSBHv2R8z3OZKj7boqepf8tvs5Xly8O1uI0Nbyy9MWyOCdJUIaS54gnNSvuevfUzfPpNNQteiXUkHxAMfnVZUaupvVX9LlqJ1FoK2LJr7WOIZgtQKigyK/aeqwes0S93f/HLR3isC2ZZoRwkGKsmVEYsVSZzpGpiJPCT+sZPNpQtz8gnz/X8B4rYLsCuC58+sdtrJ6h75PH1vYmW8nVo4xVtfkl9ihOTOKa+0irPls2xlpLPRWTaB5RheCbta0/M5WFlMF/96mdoRyrnPrV8HnW++b4/DQ3k4gQIA/9y93JLfF8NCchSgl795wicd6wu6ANcdVO2XsJUE4AoqT5FK0RXoSmAozONofFwo9cla27i+X077mS+Uf8TgC8/FytMsT6jeVoFLQ+FBXMbJrwGejq2xcrHIrneYTR5GZa/U69qFLRb7cfKOnlh/3hztziRcioinagxP0c8J2j3jQ/Q2mdwNiZ/+US/iB31kZQOUPYuaZToOr92TLhoTyV+7X6o7VVu8+Tp0aU2dr6QzFcFlHcoA25o14OsSBblWc10foXaBd3Rm9IgTpDpbLwEjZ5i7PmUoCRWHtN8nYxXvAlRvA6IIuwmvRbWhrznpvDKrI1UtrBw3S2kOgB19MtxxL4Svjt7nQKE87SG/1SC8mgPTVZ8cIiuTAnXwZdAh5UcZldqA2GscWufFNpZRKp/WnXE3af3h/0FYX7t9vnNceKTDAz2cRvRwbTnuaCBRD1GLYes87bQ/5n2tFUTzPmWtTlqWvkqRbFfLKWHN/HPXebfMdooTX9gdLzf7fGN0dIHvIqup/07dhBgUaKe8Vb9NdzjMuVFAO6ohnsSL+MUtjlFvIElG8MbdmvvEOVkAcNS1Oxi0+pg7Gb0Pr7B6ot+DznCPnHYlQQF"));

```

### ASCII 561

```
$var=gzuncompress(base64_decode("eJztlD1uwzAMhXcDvgM3N0AvEaBA4KUdg46yRVtuZDLQTwzfvpSctHGDbu0QtJuhRz195JO8x8ohEIMPTlGPzkNgsHzCsnjlCAfiCYJBcNGiB0UaPINmqMtiC120FloexyGMSKHyMBkVoK5G2TPQYaAeuFucJo5WUxWgx5BUD53jURxnYDnAQR/nsqjhLfoAkyJSEFDsZ9lrBCKZdohWPMtixyEoGNUBsx5JC3kQurIoi2c8JTtOFv1wOpcc14IVirSueaK14iKBciyeuV2NHl2uXZd9HN66ea14NcsX62bGtZD7kaMHzM4mXnzLYo+VgKZpE6BqzXkmHbs0b8upaZmiA4PKpUE3iILZmjTiJoaspigDS5ZmTikmjkGUmvygESaERlyXSFNOF5eec06UKD4D79W4YE75iiwdHO3ZcyvC0OX+lT+AlN5k9MQp7dzzmCd1wWtE1xkQ8V7zukfmhxc2j9e0m+/XNrctPgJ9WZHS3Q/tvH4Bd/EA/u6v6p/595nfAV47k5c="));

```

### Z 94

Assumed the same character set as given for C++ in the question.

There's not really much wiggle room on how to accomplish this aside from compression and base64 encoding. The only "step up" I can think of would be finagling base128 encoding, but there aren't enough "safe" characters to accomplish this given the variability of extended-ASCII.

# Answer
> 0 votes
# Ruby

Long version:

```
require 'tempfile'
tf=Tempfile.new('r')
while $stdin.gets{tf.puts $_}
tf.rewind
print "data='"
print IO.read(tf).gsub(/'/,"\\'")
print "'"

```

Golfed-up version

```
require 'tempfile'
t=Tempfile.new('r');while gets{t.puts $_};t.rewind;p "data='"+IO.read(t).gsub(/'/,"\\'")+"'"

```

---
Tags: code-challenge
---


title: Align lists like coreutils' `ls`

text:
# Question
Title: Align lists like coreutils' `ls`
Make program that takes the list from the files from STDIN, and aligns it nicely, just like `ls` command from coreutils. For example, assuming the following list (taken from The ASCII Collab, which takes place in the chatroom on this site).

```
alligator
ant
bear
bee
bird
camel
cat
cheetah
chicken
chimpanzee
cow
crocodile
deer
dog
dolphin
duck
eagle
elephant
fish
fly
fox
frog
giraffe
goat
goldfish
hamster
hippopotamus
horse
kangaroo
kitten
leopard
lion
lizard
llama
lobster
monkey
octopus
ostrich
otter
owl
oyster
panda
parrot
pelican
pig
pigeon
porcupine
puppy
rabbit
rat
reindeer
rhinoceros
rooster
scorpion
seal
shark
sheep
shrimp
snail
snake
sparrow
spider
squid
squirrel
swallow
swan
tiger
toad
tortoise
turtle
vulture
walrus
weasel
whale
wolf
zebra

```

Align the results, like the in the example below (the example shows columns set to 80). The terminal width is received as the first argument. If any argument is bigger than this argument, you can do anything. Try to use as many columns as possible with two space separators, as long nothing overflows.

```
alligator   crocodile  giraffe       llama    pig         shark     tiger
ant         deer       goat          lobster  pigeon      sheep     toad
bear        dog        goldfish      monkey   porcupine   shrimp    tortoise
bee         dolphin    hamster       octopus  puppy       snail     turtle
bird        duck       hippopotamus  ostrich  rabbit      snake     vulture
camel       eagle      horse         otter    rat         sparrow   walrus
cat         elephant   kangaroo      owl      reindeer    spider    weasel
cheetah     fish       kitten        oyster   rhinoceros  squid     whale
chicken     fly        leopard       panda    rooster     squirrel  wolf
chimpanzee  fox        lion          parrot   scorpion    swallow   zebra
cow         frog       lizard        pelican  seal        swan

```

# Answer
> 7 votes
# Bash, ~~48~~ 46 bytes

```
cd `mktemp -d`
xargs -d\\n tee
stty cols $1
ls

```

Guaranteed to work like *ls*.

# Answer
> 4 votes
### GolfScript, 79 characters

```
n%:I{)I/{{,}$-1=,}:L%{2++}*"#{ARGV[0]}"~)<}I,,?)/{.L{:x' '*+x<}+%}%zip{'  '*n}/

```

Assumes a two spaces between the columns (although it can be changed easily to one which saves 2 characters).

# Answer
> 2 votes
**Python 3 (394)**

Feels longish, but works and isn't *horrible* to read;

```
import sys,math
f=sys.stdin.read().splitlines()
l,w=len(f),int(sys.argv[1])
for y in range(w,0,-1):
 n=math.ceil(l/y)
 r=[f[i:l:n]for i in range(0,n)]
 c=[max(len(s[i]) if i<len(s) else 0 for s in r) for i in range(y)]
 if sum(c)+len(c)*2-2<=w:break
for i in range(len(r)):
 s=len(r[i])
 for j in range(s):
  t=r[i][j]
  sys.stdout.write(t+(' '*(c[j]-len(t)+2) if j<s-1 else '\n'))

```

Basically it tries with fewer and fewer columns until they all fit. It will always output at least one column even if the file names won't fit the width.

# Answer
> 0 votes
# BASH, 13 15

```
column -s"\n"-c

```

You can append the column width argument like this:

```
column -s"\n"-c80

```

Reads text from STDIN and aligns it in columns.

# Answer
> 0 votes
## C++11, 409 bytes

```
#include<vector>
#include<iostream>
using namespace std;main(int i,char*a[]){int w=atoi(a[1]),n,c,x,r;int v[w];vector<string>l;string s;while(getline(cin,s))l.push_back(s);n=l.size();for(c=n;c>1;--c){r=n/c+(n%c!=0);for(i=0;i<n;++i)v[i/r]=max((int)l[i].size(),i%r?v[i/r]:0);for(i=x=0;i<c;++i)x+=v[i]+=i<c-1?2:0;if(x<=w)break;}for(i=0;i<n;++i)printf(((i+1)%c&&i<n-1)?"%1$-*2$s":"%s\n",l[i*r%n].c_str(),v[i%c]);}

```

Below is the slightly non-golfed version. If I may point you at something potentially interesting, then please take a look at the silly format strings of the last printf.

```
#include<vector>
#include<iostream>
using namespace std;
main(int i,char*a[]){
int w=atoi(a[1]),n,c,x,r;
int v[w];
vector<string>l;string s;while(getline(cin,s))l.push_back(s);n=l.size();
for(c=n;c>1;--c){
 r=n/c+(n%c!=0);
 for(i=0;i<n;++i)v[i/r]=max((int)l[i].size(),i%r?v[i/r]:0);
 for(i=x=0;i<c;++i)x+=v[i]+=i<c-1?2:0;
 if(x<=w)break;
}
for(i=0;i<n;++i)
 printf(((i+1)%c&&i<n-1)?"%1$-*2$s":"%s\n",l[i*r%n].c_str(),v[i%c]);
}

```

---
Tags: code-golf
---


title: Generate a self-extractor application

text:
# Question
Title: Generate a self-extractor application
Create a program in *any* language, that takes an arbitrary binary input, and generates a valid C++11 program, which when compiled and run will print this binary input.

So you could do this (on linux with gcc, where `program` is the code you've written and `file.dat` is one of the test inputs):

```
$ cat file.dat | ./program > gen.cpp
$ g++ -std=c++11 -pedantic -static -O2 -o gen gen.cpp
$ ./gen > file.dat.new
$ diff file.dat file.dat.new
$ echo $?
0

```

The scoring depends on the byte count of the original code (**O**), and the square of the byte count of the generated codes for the following inputs:

* **A**: The whole lyrics of Never gonna give you up
* **B**: The uncompressed grayscale 32x32 BMP version of Lena Söderberg
* **C**: The original source code (the generator, **O**)
* **D**: The generated source code for the **A** input

Score is **O** \+ **A**^2 + **B**^2 + **C**^2 + **D**^2. The values for the generated variants are squared to encourage optimizing the size of the generated code (and the size of the original code is reflected in **C** as well).

Lowest score wins.

Clarification of the rules:

* The generated code has to conform to the C++11 standard
* You have to be able to compile, run and test all generated codes with at least one of the GCC, Clang or MSVC++ compilers (the example above is just an example for linux and gcc, but you should get the idea on how it should work).
* The C++11 code can only use the standard C++11 libraries, so external libraries (like zlib) are not allowed.
* The generated code has to be able to print the original data without any external help, like network connections or pipes, etc. (e.g. if you move the `gen.exe` to another, isolated computer it should be able to generate the output there as well)
* The code generator should also work for any other input (generates code that regenerates the original input), but compression performance for them is not measured in the score (this means that optimizing the generator only for the test inputs are okay).
* The input files are supplied in base 64 only because they contain binary data (the image at least). They need to be decoded separately, which is not part of the challenge

File inputs *in base 64*:

**Never gonna give you up**

```
V2UncmUgbm8gc3RyYW5nZXJzIHRvIGxvdmUNCllvdSBrbm93IHRoZSBydWxlcyBhbmQgc28gZG8g
SQ0KQSBmdWxsIGNvbW1pdG1lbnQncyB3aGF0IEknbSB0aGlua2luZyBvZg0KWW91IHdvdWxkbid0
IGdldCB0aGlzIGZyb20gYW55IG90aGVyIGd1eQ0KSSBqdXN0IHdhbm5hIHRlbGwgeW91IGhvdyBJ
J20gZmVlbGluZw0KR290dGEgbWFrZSB5b3UgdW5kZXJzdGFuZA0KDQpOZXZlciBnb25uYSBnaXZl
IHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5k
IGFuZCBkZXNlcnQgeW91DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNh
eSBnb29kYnllDQpOZXZlciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpXZSd2ZSBr
bm93biBlYWNoIG90aGVyIGZvciBzbyBsb25nDQpZb3VyIGhlYXJ0J3MgYmVlbiBhY2hpbmcgYnV0
DQpZb3UncmUgdG9vIHNoeSB0byBzYXkgaXQNCkluc2lkZSB3ZSBib3RoIGtub3cgd2hhdCdzIGJl
ZW4gZ29pbmcgb24NCldlIGtub3cgdGhlIGdhbWUgYW5kIHdlJ3JlIGdvbm5hIHBsYXkgaXQNCkFu
ZCBpZiB5b3UgYXNrIG1lIGhvdyBJJ20gZmVlbGluZw0KRG9uJ3QgdGVsbCBtZSB5b3UncmUgdG9v
IGJsaW5kIHRvIHNlZQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIgZ29ubmEgbGV0
IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91DQpOZXZlciBn
b25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZlciBnb25uYSB0
ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQpOZXZlciBnb25uYSBnaXZlIHlvdSB1cA0KTmV2ZXIg
Z29ubmEgbGV0IHlvdSBkb3duDQpOZXZlciBnb25uYSBydW4gYXJvdW5kIGFuZCBkZXNlcnQgeW91
DQpOZXZlciBnb25uYSBtYWtlIHlvdSBjcnkNCk5ldmVyIGdvbm5hIHNheSBnb29kYnllDQpOZXZl
ciBnb25uYSB0ZWxsIGEgbGllIGFuZCBodXJ0IHlvdQ0KDQooT29oLCBnaXZlIHlvdSB1cCkNCihP
b2gsIGdpdmUgeW91IHVwKQ0KKE9vaCkNCk5ldmVyIGdvbm5hIGdpdmUsIG5ldmVyIGdvbm5hIGdp
dmUNCihHaXZlIHlvdSB1cCkNCihPb2gpDQpOZXZlciBnb25uYSBnaXZlLCBuZXZlciBnb25uYSBn
aXZlDQooR2l2ZSB5b3UgdXApDQoNCldlJ3ZlIGtub3cgZWFjaCBvdGhlciBmb3Igc28gbG9uZw0K
WW91ciBoZWFydCdzIGJlZW4gYWNoaW5nIGJ1dA0KWW91J3JlIHRvbyBzaHkgdG8gc2F5IGl0DQpJ
bnNpZGUgd2UgYm90aCBrbm93IHdoYXQncyBiZWVuIGdvaW5nIG9uDQpXZSBrbm93IHRoZSBnYW1l
IGFuZCB3ZSdyZSBnb25uYSBwbGF5IGl0DQoNCkkganVzdCB3YW5uYSB0ZWxsIHlvdSBob3cgSSdt
IGZlZWxpbmcNCkdvdHRhIG1ha2UgeW91IHVuZGVyc3RhbmQNCg0KTmV2ZXIgZ29ubmEgZ2l2ZSB5
b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVuIGFyb3VuZCBh
bmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBnb25uYSBzYXkg
Z29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0KTmV2ZXIgZ29u
bmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIgZ29ubmEgcnVu
IGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5DQpOZXZlciBn
b25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVydCB5b3UNCg0K
TmV2ZXIgZ29ubmEgZ2l2ZSB5b3UgdXANCk5ldmVyIGdvbm5hIGxldCB5b3UgZG93bg0KTmV2ZXIg
Z29ubmEgcnVuIGFyb3VuZCBhbmQgZGVzZXJ0IHlvdQ0KTmV2ZXIgZ29ubmEgbWFrZSB5b3UgY3J5
DQpOZXZlciBnb25uYSBzYXkgZ29vZGJ5ZQ0KTmV2ZXIgZ29ubmEgdGVsbCBhIGxpZSBhbmQgaHVy
dCB5b3U=

```

**Lena**

```
Qk02CAAAAAAAADYEAAAoAAAAIAAAACAAAAABAAgAAAAAAAAEAAB1CgAAdQoAAAABAAAAAAAAAAAA
AAEBAQACAgIAAwMDAAQEBAAFBQUABgYGAAcHBwAICAgACQkJAAoKCgALCwsADAwMAA0NDQAODg4A
Dw8PABAQEAAREREAEhISABMTEwAUFBQAFRUVABYWFgAXFxcAGBgYABkZGQAaGhoAGxsbABwcHAAd
HR0AHh4eAB8fHwAgICAAISEhACIiIgAjIyMAJCQkACUlJQAmJiYAJycnACgoKAApKSkAKioqACsr
KwAsLCwALS0tAC4uLgAvLy8AMDAwADExMQAyMjIAMzMzADQ0NAA1NTUANjY2ADc3NwA4ODgAOTk5
ADo6OgA7OzsAPDw8AD09PQA+Pj4APz8/AEBAQABBQUEAQkJCAENDQwBEREQARUVFAEZGRgBHR0cA
SEhIAElJSQBKSkoAS0tLAExMTABNTU0ATk5OAE9PTwBQUFAAUVFRAFJSUgBTU1MAVFRUAFVVVQBW
VlYAV1dXAFhYWABZWVkAWlpaAFtbWwBcXFwAXV1dAF5eXgBfX18AYGBgAGFhYQBiYmIAY2NjAGRk
ZABlZWUAZmZmAGdnZwBoaGgAaWlpAGpqagBra2sAbGxsAG1tbQBubm4Ab29vAHBwcABxcXEAcnJy
AHNzcwB0dHQAdXV1AHZ2dgB3d3cAeHh4AHl5eQB6enoAe3t7AHx8fAB9fX0Afn5+AH9/fwCAgIAA
gYGBAIKCggCDg4MAhISEAIWFhQCGhoYAh4eHAIiIiACJiYkAioqKAIuLiwCMjIwAjY2NAI6OjgCP
j48AkJCQAJGRkQCSkpIAk5OTAJSUlACVlZUAlpaWAJeXlwCYmJgAmZmZAJqamgCbm5sAnJycAJ2d
nQCenp4An5+fAKCgoAChoaEAoqKiAKOjowCkpKQApaWlAKampgCnp6cAqKioAKmpqQCqqqoAq6ur
AKysrACtra0Arq6uAK+vrwCwsLAAsbGxALKysgCzs7MAtLS0ALW1tQC2trYAt7e3ALi4uAC5ubkA
urq6ALu7uwC8vLwAvb29AL6+vgC/v78AwMDAAMHBwQDCwsIAw8PDAMTExADFxcUAxsbGAMfHxwDI
yMgAycnJAMrKygDLy8sAzMzMAM3NzQDOzs4Az8/PANDQ0ADR0dEA0tLSANPT0wDU1NQA1dXVANbW
1gDX19cA2NjYANnZ2QDa2toA29vbANzc3ADd3d0A3t7eAN/f3wDg4OAA4eHhAOLi4gDj4+MA5OTk
AOXl5QDm5uYA5+fnAOjo6ADp6ekA6urqAOvr6wDs7OwA7e3tAO7u7gDv7+8A8PDwAPHx8QDy8vIA
8/PzAPT09AD19fUA9vb2APf39wD4+PgA+fn5APr6+gD7+/sA/Pz8AP39/QD+/v4A////AEmnoKA4
OUVOT0tDSHCAhIiNkpOUnrDNtmJ3dWBUZFk/aJSbp0MwOkU9W0IpUGSCi4+QjJKiu9ieXliNaExV
ZUVZiZerTS45ND1jSyhDY2qNj4uNmazH2H9SS5i1WFZhTlB8l6tMMTk1QVtcOzRkaYSOiZKgt8/K
foCJj8eRWWBbXHaZqkcwRDM8a3RSOkxneYuMmKi/26B8lYeO2bNjZWJycpqsTi5CO0twc0ozPVVz
i5Cer8fcZG6WjIKt0nBhZn5TmqxaNUhNV3ZqPzU7RXKJjaLEzok/c5SEcXbQnktZOU+kpWI9QWBu
dU06MjU9ZIGUpJlbOk9whX1+e8bXi0UuY6qhXEk/aXJ4PTU0OkJjh5qmYShASW+dmZaFvdzWujZe
raRoVUNpYJV1MDZCYoOKfo2HPDhDaaGalYi02tXWQF6soWZdQlJgbJJRLkp6i4uIm6hlNEFjmZiT
i6rT0tVKV6igYV9MXV09U3xHRXyNmpeHqI09PmSGnJWOoczQ0klKpZ1lalRhQjdWWH5AeJWll3ur
oVU9YGahmJGRvszQT1GooF94WlNGPFw3e3tzobKjh7ejZERcSJqalYugxsheW6uhX29zWUlTWCo/
pI+IkZ+GsotURl81ip2Zlo2ftWBkqp1ZX3OTU0pMNi9rwGxMbYGyZz5GWy5woZqbmZCMY2uqm1hk
aoFyY0U5Nz2Rs4l2oMG5cUlRMVScop+ZlY5ka6qaWWVrdYZ/UjY3P0+bs6mvxtuHUUQ2OouhnJmZ
mWdtqZlVYWZwp317WD1FOkqYuKy+xmZwQjEvZp+ko6CcZ3OqllZhYX2zf36AZEQ7RVmku7i4doeP
QipGmaehnZtjdqyVVmJcmKl5f4SIdVhpUFCkxMPFpoiCPy58pZ+bml5yq5VXYl6YoHWCh46Ukpea
lp6yv8fPw590JlKcoJ2dYHCqlFhjYJOKan2Mk6Crrq61uLK2wsrQxbE2L3mjn5xhb6aQVmRli3hs
eYKYq7GyucG/yMemnr3W1U4pQ5WhnFlqpIxUYmh+e218goeluL3DycvZoo+BSKvQRjAuYZ6hV2yk
jFdjanZ5b3eFiIquw8nM1r1nlYczd5tZLTM0eKNpaKeLV2RpdXpzc3uIjqe8ydbJamSZgmKTko89
LTBCg5Rupo1VY2p0e313foaUr77GtH9ncJWNjJKPlI08LzE9pY+ijlplbXl+gIKCjZ6wsp18eXRy
jpeYk42S1nUpMy2ipaSMX2dsen6AgYKBgoWBfX+Ad3WTnp2bkLm7dVgwMZ2hp41haG17gYKDg4N/
f4ODgIB3dZyinpigzIJ2glsun5yokmJqbnyDhIWFhoSDhYOBgnSCnp2bmMKob3t9gWU=

```

# Answer
> 2 votes
# C

The extremely repetitive song makes it possible to compress this rather heavily. This program analyses the structure of the input and picks one of two compressors (one for the song, one for the picture), or falls back to raw output. I manage to shrink both the song and the picture at half the input size!

Tested on Debian Jessie using gcc and g++.

Score: 1185 + 957^2 + 1223^2 + 1276^2 + 1123^2 = **5 302 068**

```
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define R ;return;
#define X(a) ;o(34);a;o(34);
#define Y(a,b) X(q(s+a,b))
#define V ;r(j-66)X(q(h,strlen(h)));o(10);
#define H w("#include<stdio.h>\nint main(){fwrite(\"");
#define F(a) ;w("\",1,");printf("%d",g-a);w(",stdout);}")R}
#define M char
M*s,*h;int g=0,c,t=0,i=0,j=65,z,f,b[5][2]={210,224,225,235,208,388,403,568,142,208},n[7]={0,1,3,2,1,0,4};o(M a){putchar(a);}e(int a){if(a==10){w("\\n")R}if(a==13){w("\\r")R}a==34||a==92?o(92):1;o(a);}q(M*a,int b){for(;b--;a++)e(*a);}w(M*a){printf(a);}d(){w("#define ");o(j++);o(32);}r(int a){t=b[a][1]-b[a][0];h=memcpy(calloc(1,t+1),s+b[a][0],t);}l(M*a,int b,int*c){while(*a){f=1;for(i=0;i<b&&f;i++){r(c[i]);z=strlen(h);if(!memcmp(a,h,z)){X(e(32);o(65+c[i]);e(32));a+=z;f=0;}free(h);}if(f){e(*a);a++;}}}main(){while((c=getchar())!=EOF){s=realloc(s,++g);s[g-1]=c;if(!c)t=g;}if(g==1943&&!t){d()V d()V d();r(2)X(l(h,2,n))o(10);d()V d()V H l(s,5,n+2)F(0)if(g==2102){unsigned M*a=s+53;for(;i<=255;i++,a+=4)for(t=1;t<4;t++)if(*(a+t)!=i||*a){H q(s,g)F(0)H q(s,53)X(w(",1,53,stdout);for(int i=0,j;i<=255;i++){for(j=0;j<4;j++)putchar(j?i:0);};fwrite("))q(s+1077,g-1077)F(1077)H q(s,g)F(0)

```

Before minimizing it (I also changed some identifiers during minimization, but at least you can see the algorithm):

```
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#define X(a) ;o('"');a;o('"');
#define Y(a,b) X(q(s+(a),(b)))
#define V(a) X(q(rr(a),strlen(rr(a))));o(10);
#define H ;w("#include<stdio.h>\nint main(){fwrite(\"");
#define F(a) ;w("\",1,");printf("%d",sz-a);w(",stdout);}");}

//Input memory handling
char*s;
int sz=0,c,t=0;
m(char a){
    s = realloc(s,++sz);
    s[sz-1] = a;
    if(a==0||a=='%')t=sz;
}

//Print 1 byte
o(char a){putchar(a);}

//Print 1 byte with C escaping
e(int a){
    if(a==10){w("\\n");return;}
    if(a==13){w("\\r");return;}
    if(a=='"'||a=='\\')o('\\');
    o(a);
}

//Print b bytes
p(char*a,int b){for(;b--;a++)o(*a);}

//Print b bytes with escaping
q(char*a,int b){for(;b--;a++)e(*a);}

//Print a NUL-terminated string
w(char*a){printf("%s",a);}

//Helper for #defines
d(char a){w("#define ");o(a);o(' ');}

//Read a predefined portion of rickroll text
char*rr(int a){
    int b[5][2]={{0xd2,0xe0},{0xd0,0x184},{0xe1,0xeb},{0x193,0x238},{0x8e,0xd0}};
    int sb=b[a][1]-b[a][0];
    return memcpy(calloc(1,sb+1),s+b[a][0],sb);
}

//Print a with substrings from rickroll substrings in c
//replaced with constants from g
rs(char*a,int b,int*c,char*g){
    int i,si,f;char*d;
    while(*a){
        f=0;
        for(i=0;i<b&&!f;i++){
            d=rr(c[i]);si=strlen(d);
            if(!memcmp(a,d,si)) {
                X(e(' ')&&e(g[i])&&e(' '));
                a=a+si;
                f=1;
            }
            free(d);
        }
        if(!f){
            e(*a);a++;
        }
    }
}

/*Rick Astley compression mode
  Defines constants for common substrings and uses them if and where they
  appear in the input text.
*/
r(){
    char b[1];
    d('A')V(0)
    d('B')V(2)
    int n[2]={0,2};
    d('C')X(rs(rr(1),2,n,"AB"))o(10);
    d('D')V(3)
    d('E')V(4)
    H
    int m[5]={3,1,2,0,4};
    rs(s,5,m,"DCBAE")
    F(0)

/*Lena compression mode
  Looks for color definintion table in the input text, and prints that using a
  for loop in the generated code. Fallback to raw mode if no color table.
 */
l() {
    int i=0,j;unsigned char*a=s+0x35;
    for(;i<=0xff;i++){
        for(j=1;j<4;j++)
            if(*(a+(i*4)+j)!=i||*(a+(i*4))){z();return;}
    }
    H
    q(s,0x35);
    // j?i:0 to output NULL byte first
    w("\",1,0x35,stdout);for(int i=0,j;i<=0xff;i++){for(j=0;j<4;j++)putchar(j?i:0);};fwrite(\"");
    q(s+0x435,sz-0x435)
    F(0x435)

//Raw mode
z(){
    H
    q(s,sz)
    F(0)

//Read entire input and pick compression method based on size
main() {
    while((c=getchar())!=EOF)m(c);
    if(sz==1943&&!t)r();
    else if(sz==2102)l();
    else z();
    return 0;
}

```

# Answer
> 1 votes
Python 3.2 (36,737,736)

Just to get this started, a *totally dumb-as-a-rock-no-compression* implementation score.

```
import sys,base64
print("""#include <cstdio>
int main(){char*s="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";char t[256]={0};for(int i=0;*s;s++,i++)t[*s]=i;for(s="%s";*s;s+=4){char c[]={char(t[*s]<<2|t[s[1]]>>4&3),char(t[s[1]]<<4&240|t[s[2]]>>2&15),char(t[s[2]]<<6&192|t[s[3]]&63)};fwrite(c,3-(s[3]=='=')-(s[2]=='='),1,stdout);}}"""%(base64.b64encode(sys.stdin.buffer.read())).decode())

```

Basically it just base64 encodes the file and decodes it in C++. Tested with `clang++` on MacOS Mavericks, current Xcode. It compiles with style warnings, but I don't see any rule against that :)

Score is 408 + 2914^2 + 3126^2 + 866^2 + 4210^2 = 36,737,736

---
Tags: code-golf, c++, compression, code-generation
---


title: Missy Elliot, XKCD and ASCII Bytes

text:
# Question
Title: Missy Elliot, XKCD and ASCII Bytes
Inspired by the following XKCD comic:

In Missy Elliot's "Work It", part of the chorus goes as follows:

`Is it worth it, let me work it`

`I put my thing down, flip it and reverse it`

Bearing that in mind, I propose the following code golf challenge:

Create code that does, in order:

1. Takes 8-bit ASCII input from STDIN; e.g `n` (Hex 6E, or Bin 01101110)
2. Shifts each byte's 8 bits down 1 bit level (I believe it's called a bitwise shift down), e.g `01101110` becomes `00110111` ("put my thing down");
3. Inverts each byte's bits, e.g `00110111` becomes `11001000` ("flip it");
4. Reverses the bits for each byte, e.g `11001000` becomes `00010011` ("reverse it");
5. If a byte's value is less than 32, then perform `(95 + [byte value])`, or in other words, `(126-(31-[byte value]))`, on the byte before converting back to ASCII... If the byte value is still less than 32, repeat step 5
6. If a byte's value is greater than 126, then perform `([byte value] - 95)`, or in other words, `(32+([byte value]-127))`, on the byte before converting back to ASCII... IF the value is still greater than 126, repeat step 6.
7. Display the newly converted string as ASCII.

**An example of this code in action:**

(The input, is it worth it?)

`workit missy` ("missy" being the input, "workit" is the function)

*Now behind the scenes...*

(let me work it... Into binary)

`01101101 01101001 01110011 01110011 01111001`

(Put my thing down... Bitwise)

`00110110 00110100 00111001 00111001 00111100`

(...Flip it...)

`11001001 11001011 11000110 11000110 11000011`

(... And reverse it!)

`10010011 11010011 01100011 01100011 11000011`

(Converted back to Decimal)

`147 211 99 99 195`

(Perform the necessary math)

`147-95 211-95 99 99 195-95 => 52 116 99 99 100`

(Convert back to ASCII and display, the output)

`4tccd`

**Rules**

1. Shortest code wins... simple as that...
2. Input can be via function, by prompt or whatever works for you, so long as you can make Rule 1 "work it" for you... ;)
3. I am not after reversibility, so long as you can make the code do what I have asked it to do, I'll be happy...

Best of luck!

# Answer
> 5 votes
## APL  ~~50~~  45

```
⎕UCS n+95×¯1++⌿126 31∘.≥n←2⊥⊖~(8/2)⊤⌊.5×⎕UCS⍞

```

Takes input on the keyboard, e.g.:

```
      ⎕UCS n+95×¯1++⌿126 31∘.≥n←2⊥⊖~(8/2)⊤⌊.5×⎕UCS⍞
missy
4tccd

```

# Answer
> 4 votes
## GolfScript ~~43~~ ~~38~~ 35

```
{2/~512+2base(;-1%2base-32+95%32+}%

```

Explanation: For each character in the string, we will do the following:

```
2/ # "Put your thing down": do integer division (accomplishing a bit shift).
~ # "Flip it": negate the bits of the integer.
512+ #make sure the binary form will have sufficient initial 0s (the extra initial 1 will be removed).
2base #convert string to value in base 2 (as an array)
(; #remove the initial 1 added by the 512 addition
-1% # "Reverse it": reverse the array
2base #convert back to base 10
-32+95%32+ #this does the equivalent of the subtraction/addition logic

```

Usage:

```
echo 'missy' | ruby golfscript.rb workit.gs
> 4tccd

```

Thanks to help from PeterTaylor.

# Answer
> 3 votes
# K, 68 58

```
{"c"${$[a<32;95;a>126;-95;0]+a:6h$0b/:|~8#0b,0b\:x}'4h$'x}

```

.

```
k){"c"${$[a<32;95;a>126;-95;0]+a:6h$0b/:|~8#0b,0b\:x}'4h$'x}"missy"
"4tccd"

```

# Answer
> 2 votes
# J - 61

```
u:-&95^:(>&126)"0+&95^:(<&32)"0#.|."1(1-0,0,}:)"1#:3&u:1!:1[1
missy
4tccd

```

# Answer
> 2 votes
# J, 55 54 characters

```
u:+/(*126&>*.32&<)_95 0 95+/#.|."1#:255-<.-:a.i.1!:1[1

```

# Answer
> 1 votes
## Ruby, 115

This entry is uncompetitively long. So I'll go with, "but you can read it!" :-P

```
$><<gets.chars.map{|c|c=(c.ord.to_s(2)[0..-2].tr('01','10').reverse+'11').to_i(2)
(c+(c<32?95:c>126?-95:0)).chr}*''

```

Reads from `stdin`:

```
missy
4tccd

```

# Answer
> 1 votes
## Python 2.7, 106

Another rather long answer, but hey it's my first try:

```
for c in raw_input():x=sum(1<<7-i for i in range(8)if~ord(c)>>1+i&1);print'\b%c'%(x+95*((x<32)-(x>126))),

```

Modified based off of Darren Stone and grc's comments below...

# Answer
> 1 votes
## Python 2.7 - 73 ~~86~~

Thanks to the change in rules I found a much simpler way to do this all using binary and integer manipulation. This saves space over Quirlioms by not needing a temporary variable:

```
for i in input():print chr((int(bin(ord(i)>>1^255)[:1:-1],2)-32)%95+32),

> python workit.py
"missy"
4 t c c d
> python workit.py
"P Diddy"
- 9 \ t T T d

```

And in explanation form:

```
for i in input():  # Take an input, better quote it
                   # Is it worth it? Let me work it
  print chr(
    int(bin(
        ord(i)>>1  # Put my thing down by bitshifting it
             ^255  # XOR it with 255 to flip the bits and pad to 8 bits
        )[:1:-1]   # Then reverse it (but don't take the cruft
                   # python puts at the start of binary strings)
    ,2)
    )-32)%95+32    # This pulls everything into the 32-126 range
  ),

```

---
Tags: code-golf, printable-ascii
---


title: Quine quine bip quine quine

text:
# Question
Title: Quine quine bip quine quine
Write a quine that

1. Writes its source code to disk
2. Recursively executes the written source code
3. Produces some variation to the code the third time (so not a true Quine)
4. Stops recursively calling itself the fifth time

Bonus points for leaving nothing on disk after execution.

# Answer
> 2 votes
## TCL 220

```
proc a b {
if {"$b"=="bb"} {
rename puts w
rename p puts
set b \;exit
}
puts [set q [open [incr ::i] w]] "proc a b \{[info body a]\};a b"
catch {rename puts p}
proc puts {n m} "p \$n \${m}$b"
close $q
source $::i
};a b

```

The code generates files 1, 2, 3 and 4. The variation is only present in 2, the others are equivalent to the original.

# Answer
> 1 votes
## PHP 643

```
<?
$c=1;
$o="<?\n\$c=".($c+1).";\n";
$m="quine";
$s=array(
'$o="<?\n\$c=".($c+1).";\n";',
'$m="quine";',
'$s=array(',
');',
'if($c==3)$s[1]="\$m=\"bip\";";',
'for($i=0;$i<3;$i++)$o.=$s[$i]."\n";',
'for($i=0;$i<count($s);$i++)$o.=chr(39).$s[$i].chr(39).",\n";',
'for($i=3;$i<count($s);$i++)$o.=$s[$i]."\n";',
'echo $m."\n";',
'if($c<5){file_put_contents("q$c.php", $o);echo `php q$c.php`;}',
);
if($c==3)$s[1]="\$m=\"bip\";";
for($i=0;$i<3;$i++)$o.=$s[$i]."\n";
for($i=0;$i<count($s);$i++)$o.=chr(39).$s[$i].chr(39).",\n";
for($i=3;$i<count($s);$i++)$o.=$s[$i]."\n";
echo $m."\n";
if($c<5){file_put_contents("q$c.php", $o);echo `php q$c.php`;}

```

Output:

```
quine
quine
quine
bip
bip

```

The variation in the code is produced in the 3rd iteration and is then only noticeable in the echoes of the 4th and 5th iterations.

# Answer
> 0 votes
## GTB, 19

```
X+1→X@X<15$@X=13:1&

```

**Explanation**

X starts by default at 10, so we increment X once. Then, if X\<15 check if X=13. If X=13, change the code. Then dump it all to memory.

# Answer
> 0 votes
In Squeak 4.x **Smalltalk**, it's not golfed, but there is a **299 chars** version below

Compile this method in Object:

```
quine
[| value morph |
value := (((self negated raisedTo: self - 1) / 15) exp exp - 1) reciprocal significand rounded reciprocal.
morph := ToolSet inspect: value.
[(Delay forSeconds: value reciprocal * 5) wait.
morph delete] fork.
World displayWorld.
(Delay forSeconds: 1) wait]
    on: Error
    do: [:exc |
        FileDirectory default deleteFileNamed: 'quine'.
        ^self].
(FileStream forceNewFileNamed: 'quine') nextPutAll: thisContext method getSource; close.
^self class newCompiler
    evaluate: ((FileStream oldFileNamed: 'quine') contentsOfEntireFile lines allButFirst reduce: [:a :b | a , b])
    for: self + 1

```

Then evaluate '1 quine' where you want.

Each evaluation differs, because it is evaluated with incremented receiver. ( `evaluate: ... for: self+1` )

The awfull expression computing the value is different for 3 (lead to a Fraction 1/2 instead of Integer 1) and for 5 (lead to ZeroDivide).

The file is deleted when the exception is caught and 5 is returned.

Otherwise, an inspector is opened on the value, the display is refreshed, the process is paused during 1 second before evaluating next quine.

A process for closing opened inspectors after a longer pause is forked.

The source of quine is retrieved via the current context of execution (thisContext method getSource), written, then re-evaluated without the first line (the name of the method). So the second and successive evaluation do not evaluate #quine, but an anonymous (#Doit) method sharing exactly the same contents.

Based on same principles, this less funny example will print 00100 in Transcript then stop when evaluating 1 quine, but it avoids explicit 3 and 5 in source:

```
quine|v|v:=self highBit-self lowBit.Transcript show:(1bitAnd:v).(2bitAnd:v)=0or:[^FileDirectory default deleteFileNamed:'q'].(FileStream forceNewFileNamed:'q')nextPutAll:thisContext method getSource;close.^Compiler evaluate:((FileStream oldFileNamed:'q')contentsOfEntireFile allButFirst:5)for:self+1

```

---
Tags: code-golf
---


title: Syntax Highlighting for Greater Golf!

text:
# Question
Title: Syntax Highlighting for Greater Golf!
Golfers.

Together, we have banded together to produce code that is concise, is functionally beautiful and is uglier then the Phantom of the Opera from the original novel.

The time has come for us to bring beauty back to the world of programming. With color. In a way that is concise, functionally beautiful is uglier then the Phantom of the Opera from the original novel.

We're gonna be coding a colorful syntax highlighter. In the shortest amount of code possible.

You will receive via an input file or Stdin a valid C file. The C file will use the line convention of your choice, and will only contain ASCII characters 32-126. You have to turn it into a HTML file that displays correctly at least in Chrome, that shows the source code with syntax highlighting. The output may be in a file or to Stdout.

You must highlight:

* All strings and characters (including the quote characters) in Green (#00FF00). The strings may contain escaped characters.
* All C reserved words in Blue (#0000FF).
* All comments in Yellow (#FFFF00).
* All C preprocessor directives in Pink (#FF00FF).

The output when displayed in Chrome must:

* Be in a fixed-width font
* Display new lines wherever they appeared in the original source
* Accurately reproduce whitespace. A tab character should be taken as being 4 spaces.

**Bonuses**

* x 0.9 if you include line numbers. Line numbers must be able to reach at least 99999. All source must still be aligned - so, source code with smaller line numbers should still start at the same position as source code with higher line numbers
* x 0.8 if background of each line is alternated between light gray (#C0C0C0) and white (#FFFFFF)
* x 0.9 if your source code is written in C, and can correctly format itself.

**Scoring**

This is code golf. Your score is the amount of bytes of your source code multiplied by any bonuses. The winner is the golfer with the lowest score.

# Answer
> 8 votes
## Perl 769 chars * 0.9 * 0.8 = 554

Probably still some improvements to be made on some of the regexes, but it's slowly getting there!

```
$_=join"",<>;$s="<tt class";$c="</tt>";$d=counter;$e=color;s/\t/    /g;s!<!<!g;s!>!>!g;s!^#.+(?=$|
)!$s=d>$&$c!gm;s!//.+!$s=c>$&$c!g;s|(['"]).*?(?<!\\)(\\\\)*\1|($h=$&)=~s!/!/!g;"$s=s>$h$c"|smeg;s!/\*.*?\*/!$s=c>$&$c!smg;s!\b(_Packed|(au|go)to|break|c(ase|har|onst|ontinue)|d(efault|o|ouble)|e(lse|num|xtern)|f(loat|or)|if|int|long|re(gister|turn)|short|(un)?signed|s(izeof|tatic|truct|witch)|typedef|union|vo(id|latile)|while)\b!$s=r>$&$c!g;s!=(\w)>.+?$c!join"$c
$s=$1>",split$/,$&!smeg;s!
!<tr><td>!g;print"<style>body{font:10px monospace;$d-reset:n}td{white-space:pre}tr:nth-child(even){background:#c0c0c0}tr:before{$d-increment:n;content:$d(n)}.d{$e:#f0f}.r{$e:#00f}.c{$e:#ff0}.s{$e:#0f0}tt tt{$e:inherit!important}</style><table cellspacing=0><tr><td>$_"

```

Slightly less obfuscated version with comments:

```
$_=join"",<>; # slurp file
$s="<tt class"; # used later - use <tt/> instead of <span/>, fewer chars!
$c="</tt>";
$d=counter;
$e=color;
s/\t/    /g; # convert tabs to spaces
s!<!<!g; # htmlentity < and >
s!>!>!g;
s!^#.+(?=$|\n)!$s=d>$&$c!gm; # directives
s!//.+!$s=c>$&$c!g; # inline comments
s|(['"]).*?(?<!\\)(\\\\)*\1|($h=$&)=~s!/!/!g;"$s=s>$h$c"|smeg; # strings, might have 0 length - thanks @Einacio; work-around string that contain /* by converting them to HTML entities
s!/\*.*?\*/!$s=c>$&$c!smg; # multi-line comments
s!\b(_Packed|(au|go)to|break|c(ase|har|onst|ontinue)|d(efault|o|ouble)|e(lse|num|xtern)|f(loat|or)|if|int|long|re(gister|turn)|short|(un)?signed|s(izeof|tatic|truct|witch)|typedef|union|vo(id|latile)|while)\b!$s=r>$&$c!g; # reserved words, don't optimise this too much! - thanks @bwoebi
s!=(\w)>.+?$c!join"$c
$s=$1>",split$/,$&!smeg; # any multi-line string/comment, ensure <span/>s are repeated
s!\n!<tr><td>!g; # strip newlines, replace with <tr><td>, don't need </td> _or_ </tr> - thanks @xfix!
print"<style>
body{font:10px monospace;$d-reset:n} /* init counter */
td{white-space:pre} /* preserve whitespace */
tr:nth-child(odd){background:#c0c0c0} /* alternating rows */
tr:before{$d-increment:n;content:$d(n)} /* place counter */
.d{$e:#f0f} /* highlights */
.r{$e:#00f}
.c{$e:#ff0}
.s{$e:#0f0}
tt tt{$e:inherit!important} /* ignore reserved words/comments in strings */
</style><table cellspacing=0><tr><td>$_"

```

Now successfully highlights @xfix's entry.

Borrowed the idea to drop `</tr>` from @xfix's entry, thank you!

Example of output for @xfix's solution.

# Answer
> 7 votes
# C - ~~1605~~ 1200 chars * 0.9 * 0.8 * 0.9 = 777 chars

Definitely too long, but whatever. 264 used by list of keywords itself. The long one liner version. Doesn't use memory allocations, so the memory usage is very low (and everything is global, so the stack is not really used). Sample HTML on JSFiddle. In my opinion, comments support was most complex thing in the code.

```
char*k[]={"auto","break","case","char","const","continue","default","do","double","else","enum","extern","float","for","goto","if","int","long","register","return","short","signed","sizeof","static","struct","switch","typedef","union","unsigned","void","volatile","while"},b[9];c;p;e;p;l=1;q;s;i;main(){printf("<style>tr:nth-child(2n){background:#C0C0C0}</style><table style=font-family:monospace;white-space:pre-wrap><tr><td>1<td>");while(~(c=getchar())){if(!e&&q){if(q==c){printf("%c</span>",c);q=0;continue;}}else if(isalpha(c)&&p<8){b[p++]=c;continue;}else if(b[0]){for(i=0;i<32;i++){s!=2&&!strcmp(k[i],b)&&(printf("<span style=color:#00F>%s</span>",b),b[0]=0);}printf("%s",b);memset(b,0,9);}p=0;switch(c){case'<':printf("<");goto e;case'&':printf("&");goto e;case 92:putchar(c);e^=1;goto e;case'/':q||1==s?putchar('/'):3==s?(printf("*/"),s=0):(s=1);break;case'*':if(s==1){s=2;printf("<span style=color:#FF0>/*");}else if(s==2){s=3;}else{goto d;}break;case 39:case'"':e||q||(q=c,printf("<span style=color:#0F0>"));e=0;goto d;case 10:l+=1;printf("<tr><td>%d<td>",l);if(p&&e){case'#':e=0;q||(p=1,printf("<span style=color:#F0F>"));}else{p=0;}default:d:10!=c&&putchar(c);e:s=s/2*2;}}puts(b);}

```

And the longer version (which is as readable as real program, aside of few code golf tricks I didn't think I could apply easily while golfing the program.

```
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#define ARRAY_SIZE(array) (sizeof(array) / sizeof *(array))
/* Sample comment. */
int main(void) {
    const char *keywords[] = {
        "auto",     "break",    "case",     "char",     "const",
        "continue", "default",  "do",       "double",   "else",
        "enum",     "extern",   "float",    "for",      "goto",
        "if",       "int",      "long",     "register", "return",
        "short",    "signed",   "sizeof",   "static",   "struct",
        "switch",   "typedef",  "union",    "unsigned", "void",
        "volatile", "while",
    };
    int character;
    int preprocessor = 0;
    int escape = 0;
    char buffer[9] = {0};
    int pos = 0;
    int line = 1;
    int quote = 0;
    int comment_state = 0;
    printf("<style>tr:nth-child(2n){background:#C0C0C0}</style><table style=font-family:monospace;white-space:pre-wrap><tr><td>1<td>");
    while ((character = getchar()) != EOF) {
        if (!escape && quote) {
            if (quote == character) {
                printf("%c</span>", character);
                quote = 0;
                continue;
            }
        }
        else if (isalpha(character) && pos < 8) {
            buffer[pos] = character;
            pos += 1;
            continue;
        }
        else if (buffer[0]) {
            int i;
            for (i = 0; i < ARRAY_SIZE(keywords); i++) {
                if (comment_state != 2 && strcmp(keywords[i], buffer) == 0) {
                    printf("<span style=color:#00F>%s</span>", buffer);
                    buffer[0] = 0;
                }
            }
            printf("%s", buffer);
            memset(buffer, 0, 9);
        }
        pos = 0;
        switch (character) {
        case '<':
            printf("<");
            goto e;
        case '&':
            printf("&");
            goto e;
        case '\\':
            putchar(character);
            escape ^= 1;
            goto e;
        case '/':
            if (quote || comment_state == 1) {
                putchar('/');
            }
            else if (comment_state == 3) {
                printf("*/");
                comment_state = 0;
            }
            else {
                comment_state = 1;
            }
            break;
        case '*':
            if (comment_state == 1) {
                comment_state = 2;
                printf("<span style=color:#FF0>/*");
            }
            else if (comment_state == 2) {
                comment_state = 3;
            }
            else {
                goto d;
            }
            break;
        case '\'':
        case '"':
            if (!escape && !quote) {
                quote = character;
                printf("<span style=color:#0F0>");
            }
            escape = 0;
            goto d;
        case '\n':
            line += 1;
            printf("<tr><td>%d<td>", line);

            /* Execute next only if conditions match. */
            if (preprocessor && escape) {
        case '#':
                escape = 0;
                if (!quote) {
                    preprocessor = 1;
                    printf("<span style=color:#F0F>");
                }
            }
            else {
                preprocessor = 0;
            }
            /* fallthru */
        default:
        d:
            if (character != '\n') putchar(character);
        e:
            comment_state = comment_state / 2 * 2;
        }
    }
    printf("%s</table>", buffer);
}

```

# Answer
> 3 votes
## PHP 606 bytes × 0.9 × 0.8 = 436

```
<style>li:nth-child(odd){background:#f5f5f5}pre{tab-size:4;-moz-tab-size:4}</style><pre><ol><li><?php $p='preg_match';preg_match_all('_\w+|("|\')(\\\\?.)*?\1|#(.(?!/[/*]))*|//.*|(?s)/\*.*?\*/|.+?_',stream_get_contents(STDIN),$m);foreach($m[0]as$t)echo'</font><font color=#',$t[0]=='#'?'d0d':($p('_^/[/*]_',$t)?'bb0':($p('/"|\'/',$t)?'0d0':($p('/^(auto|break|(cas|continu|doubl|els|volatil|whil)e|char|(cons|defaul|floa|in|shor|struc)t|do|enum|extern|for|goto|if|long|register|return|sizeof|static|switch|typedef|union|(un|)signed|void)$/',$t)?'00f':0))),'>'.preg_replace("/\r?\n/",'<li>',htmlentities($t));

```

Formatted:

```
<style>li:nth-child(odd){background:#f5f5f5}pre{tab-size:4;-moz-tab-size:4}</style>
<pre><ol><li><?php
$p='preg_match';
preg_match_all('_\w+|("|\')(\\\\?.)*?\1|#(.(?!/[/*]))*|//.*|(?s)/\*.*?\*/|.+?_',
    stream_get_contents(STDIN),$m);
foreach($m[0]as$t)
    echo'</font><font color=#',
        $t[0]=='#'?'d0d':(
        $p('_^/[/*]_',$t)?'bb0':(
        $p('/"|\'/',$t)?'0d0':(
        $p('/^(auto|break|(cas|continu|doubl|els|volatil|whil)e|char|'.
        '(cons|defaul|floa|in|shor|struc)t|do|enum|extern|for|goto|if|long|register|'.
        'return|sizeof|static|switch|typedef|union|(un|)signed|void)$/',$t)?'00f':
        0))),
        '>'.preg_replace("/\r?\n/",'<li>',htmlentities($t));

```
* Reads from stdin and writes to stdout.
* Accepted line endings are \n and \r\n.
* Does line numbers and line color alternation.
* I used *slightly* different colors so I could bear to look at it, though not in a way that affects the byte count.
* I don't have Chrome to test it although it's fine in Firefox.

# Answer
> 2 votes
## C++ - 5067 bytes4612 * 0.9 * 0.8 = 3320 (\* 0.9 = 2988 if being able to format itself counts - it's written in C++)

I realize that this is larger than the solutions already presented here, but I've decided to post this anyway because I started working on my version before the C solution by xfix was posted.

* It works with multiline comments
* It outputs HTML that has errors (but it displays correctly in Chrome)
* It reads out of input.c and produces output.html

A half of this is the large array of C and C++ keywords.

```
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
#include <locale>
#define B break
#define Z(a,b)if(s[i]==a){z=b;o+=OP+p(s[i]);i++;B;}
#define V(a,b)if(e(s,i,a)){z=b;o+=OC+p(s.substr(i,2));i+=2;B;}
#define N(a) if(s[i]=='\n'){a;o+=nl();i++;B;}
#define Q(a)if(e(s,i,"\\")){o+=p(s.substr(i,2));i+=2;B;}if(s[i]==a){z=0;o+=p(s[i])+CL;i++;B;}
#define C case
using namespace std;string k[]={"__abstract","__alignof","_Alignas","_alignof","and","and_eq","__asm","_asm","asm","__assume","_assume","auto","__based","_based","bitand","bitor","bool","_Bool","__box","break","__builtin_alignof","_builtin_alignof","__builtin_isfloat","case","catch","__cdecl","_cdecl","_Complex","cdecl","char","class","__compileBreak","_compileBreak","compl","const","const_cast","continue","__declspec","_declspec","default","__delegate","delete","do","double","dynamic_cast","else","enum","__event","__except","_except","explicit","__export","_export","extern","false","__far","_far","far","__far16","_far16","__fastcall","_fastcall","__feacpBreak","_feacpBreak","__finally","_finally","float","for","__forceinline","_forceinline","__fortran","_fortran","fortran","friend","_Generic","__gc","goto","__hook","__huge","_huge","huge","_Imaginary","__identifier","if","__if_exists","__if_not_exists","__inline","_inline","inline","int","__int128","__int16","_int16","__int32","_int32","__int64","_int64","__int8","_int8","__interface","__leave","_leave","long","__multiple_inheritance","_multiple_inheritance","mutable","namespace","__near","_near","near","new","_Noreturn","__nodefault","__nogc","__nontemporal","not","not_eq","__nounwind","__novtordisp","_novtordisp","operator","or","or_eq","__pascal","_pascal","pascal","__pin","__pragma","_pragma","private","__probability","__property","protected","__ptr32","_ptr32","__ptr64","_ptr64","public","__raise","register","reinterpret_cast","restrict","__restrict","__resume","return","__sealed","__serializable","_serializable","short","signed","__single_inheritance","_single_inheritance","sizeof","static","static_cast","_Static_assert","__stdcall","_stdcall","struct","__super","switch","__sysapi","__syscall","_syscall","template","this","__thiscall","_thiscall","throw","_Thread_local","__transient","_transient","true","__try","_try","try","__try_cast","typedef","typeid","typename","__typeof","__unaligned","__unhook","union","unsigned","using","__uuidof","_uuidof","__value","virtual","__virtual_inheritance","_virtual_inheritance","void","volatile","__w64","_w64","__wchar_t","wchar_t","while","xor","xor_eq"};string OS="<font color=\"#00FF00\">";string OC="<font color=\"#FFFF00\">";string OK="<font color=\"#0000FF\">";string OP="<font color=\"#FF00FF\">";string CL="</font>";string NL[]={ "<li class=\"li l1\">","<li class=\"li l2\">" };bool lo=1;string nl() {lo=!lo;return "</li>"+NL[lo];}bool r(char c,string s) {for (size_t i=0; i<s.size(); i++)if (c==s[i])return 0;return 0;}bool is(string s,int i) {return !(i<0||i>=s.size())&&((s[i]=='_')||isalpha(s[i]));}bool ic(string s,int i){return !(i<0||i>=s.size())&&(is(s,i)||('0'<=s[i]&&s[i]<='9'));}bool e(string a,int s,string b) {return !(a.size()-s<b.size())&&a.substr(s,b.size())==b;}string p(char c) {switch (c) {C  '&':return "&";C  '\"':return """;C  '\'':return "'";C  '<':return "<";C  '>':return ">";}stringstream s;s<<c;return s.str();}string p(string s) {string ans="";for (size_t i=0; i<s.size(); i++) {ans+=p(s[i]);}return ans;}string h(string s) {int z=0;size_t i=0;string o ="<html><body><style type=\"text/css\">.l{list-style-type: decimal;margin-top:0;margin-bottom:0;} .li{display:list-item;word-wrap:B-word;} .l1{background-color:#FFFFFF;} .l2{background-color:#EEEEEE;} .cd{white-space:pre;}</style><code class=\"cd\"><ul class=\"l\">";o+=NL[1];for (; i<s.size();) {switch (z) {C 0:{Z('#',6)Z('"',3)Z('\'',2)V("//",4)V("/*",5)N()for (size_t j=0; j<201; j++)if (e(s,i,k[j])&&!ic(s,i+k[j].size())) {o+=OK+p(k[j])+CL;i+=k[j].size();B;}if (is(s,i)) {z=7;o+=p(s[i]);i++;if (i+1==s.size()||!ic(s,i+1)) {z=0;}B;}o+=p(s[i]);i++;B;}o+=p(s[i]);i++;B;C  2:Q('\'')C  3:Q('"')C 4:{N(z=0)o+=p(s[i]); i++;B;}C 5:{if (e(s,i,"*/")) {z=0;o+=p(s.substr(i,2))+CL;i+=2;B;}N()o+=p(s[i]);i++;B;}C 6:{if (s[i]=='\n') {int j=i-1;for (; j>=0&&r(s[j],"\n\t "); j--);if (j<0||s[j] != '\\') {z=0;o+=CL+nl();i++;B;}o+=nl();i++;B;}o+=p(s[i]);i++;B;}C 7:{if (i+1==s.size()||!ic(s,i+1)) {z=0;}o+=p(s[i]);i++;B;}}}o+="</ul></code>";return o;}int main() {ifstream i("input.c");ofstream o("output.html");string cCode((istreambuf_iterator<char>(i)),istreambuf_iterator<char>());o<<h(cCode)<<endl;}

```

Readable version:

```
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
using namespace std;

//The 201 keywords from C and C++. Not sure if all of them are listed here!
const size_t NUMBER_OF_KEYWORDS = 201;
string keywords[] = { "__abstract", "__alignof", "_Alignas", "_alignof", "and",
        "and_eq", "__asm", "_asm", "asm", "__assume", "_assume", "auto",
        "__based", "_based", "bitand", "bitor", "bool", "_Bool", "__box",
        "break", "__builtin_alignof", "_builtin_alignof", "__builtin_isfloat",
        "case", "catch", "__cdecl", "_cdecl", "_Complex", "cdecl", "char",
        "class", "__compileBreak", "_compileBreak", "compl", "const",
        "const_cast", "continue", "__declspec", "_declspec", "default",
        "__delegate", "delete", "do", "double", "dynamic_cast", "else", "enum",
        "__event", "__except", "_except", "explicit", "__export", "_export",
        "extern", "false", "__far", "_far", "far", "__far16", "_far16",
        "__fastcall", "_fastcall", "__feacpBreak", "_feacpBreak", "__finally",
        "_finally", "float", "for", "__forceinline", "_forceinline",
        "__fortran", "_fortran", "fortran", "friend", "_Generic", "__gc",
        "goto", "__hook", "__huge", "_huge", "huge", "_Imaginary",
        "__identifier", "if", "__if_exists", "__if_not_exists", "__inline",
        "_inline", "inline", "int", "__int128", "__int16", "_int16", "__int32",
        "_int32", "__int64", "_int64", "__int8", "_int8", "__interface",
        "__leave", "_leave", "long", "__multiple_inheritance",
        "_multiple_inheritance", "mutable", "namespace", "__near", "_near",
        "near", "new", "_Noreturn", "__nodefault", "__nogc", "__nontemporal",
        "not", "not_eq", "__nounwind", "__novtordisp", "_novtordisp",
        "operator", "or", "or_eq", "__pascal", "_pascal", "pascal", "__pin",
        "__pragma", "_pragma", "private", "__probability", "__property",
        "protected", "__ptr32", "_ptr32", "__ptr64", "_ptr64", "public",
        "__raise", "register", "reinterpret_cast", "restrict", "__restrict",
        "__resume", "return", "__sealed", "__serializable", "_serializable",
        "short", "signed", "__single_inheritance", "_single_inheritance",
        "sizeof", "static", "static_cast", "_Static_assert", "__stdcall",
        "_stdcall", "struct", "__super", "switch", "__sysapi", "__syscall",
        "_syscall", "template", "this", "__thiscall", "_thiscall", "throw",
        "_Thread_local", "__transient", "_transient", "true", "__try", "_try",
        "try", "__try_cast", "typedef", "typeid", "typename", "__typeof",
        "__unaligned", "__unhook", "union", "unsigned", "using", "__uuidof",
        "_uuidof", "__value", "virtual", "__virtual_inheritance",
        "_virtual_inheritance", "void", "volatile", "__w64", "_w64",
        "__wchar_t", "wchar_t", "while", "xor", "xor_eq" };

// Different states
const int NONE = 0;
const int WHITESPACE = 1;
const int CHAR_UNCLOSED = 2;
const int STRING_UNCLOSED = 3;
const int LINE_COMMENT_UNCLOSED = 4;
const int MULTILINE_COMMENT_UNCLOSED = 5;
const int PREPROCESSOR_UNCLOSED = 6;
const int IDENTIFIER = 7;

//Different elements
const string OPEN_STRING = "<font color=\"#00FF00\">";
const string CLOSE_STRING = "</font>";
const string OPEN_COMMENT = "<font color=\"#FFFF00\">";
const string CLOSE_COMMENT = "</font>";
const string OPEN_KEYWORD = "<font color=\"#0000FF\">";
const string CLOSE_KEYWORD = "</font>";
const string OPEN_PREPROCESSOR = "<font color=\"#FF00FF\">";
const string CLOSE_PREPROCESSOR = "</font>";

//Alternating background
const string NEW_LINE[] = { "<li class=\"li l1\">", "<li class=\"li l2\">" };
bool lineOdd = true;
string getNewLineHTML() {
    lineOdd = !lineOdd;
    return "</li>" + NEW_LINE[lineOdd];
}

//Check if the character is in the string chars
bool inRange(char c, string chars) {
    for (size_t i = 0; i < chars.size(); i++)
        if (c == chars[i])
            return true;
    return false;
}

//Check if the character is the start of an identifier
bool isIdentifierStart(string input, int i) {
    if (i < 0 || i >= input.size())
        return false;
    return (input[i] == '_') || ('a' <= input[i] && input[i] <= 'z')
            || ('A' <= input[i] && input[i] <= 'Z');
}
//Check if the character is the continuation of an identifier
bool isIdentifierCont(string input, int i) {
    if (i < 0 || i >= input.size())
        return false;
    return ('0' <= input[i] && input[i] <= '9') || isIdentifierStart(input, i);
}
//Check if a[start + i] == b[i], i<b.size()
bool eqRange(string a, int start, string b) {
    if (a.size() - start < b.size())
        return false;
    return a.substr(start, b.size()) == b;
}
//Escape the sourcecode for HTML
string escape(char c) {
    switch (c) {
    case '&':
        return "&";
    case '\"':
        return """;
    case '\'':
        return "'";
    case '<':
        return "<";
    case '>':
        return ">";
    }
    //Is there a better way to do this?
    stringstream strm;
    strm << c;
    return strm.str();
}
string escape(string str) {
    string ans = "";
    for (size_t i = 0; i < str.size(); i++) {
        ans += escape(str[i]);
    }
    return ans;
}
string highlight(string input) {
    //The current state
    int state = NONE;
    //The current position
    size_t i = 0;
    //Styles
    string output =
            "<html><body><style type=\"text/css\">.l{list-style-type: decimal; margin-top: 0; margin-bottom: 0;} .li{ display: list-item; word-wrap: break-word;} .l1{background-color: #FFFFFF;} .l2{background-color: #EEEEEE;} .cd{white-space: pre;}</style><code class=\"cd\"><ul class=\"l\">";
    output += NEW_LINE[1];
    for (; i < input.size();) {
        switch (state) {
        case NONE: {
            if (input[i] == '#') { //Start a preprocessor statement
                state = PREPROCESSOR_UNCLOSED;
                output += OPEN_PREPROCESSOR + escape(input[i]);
                i++;
                break;
            }
            if (input[i] == '"') { //Start a string
                state = STRING_UNCLOSED;
                output += OPEN_STRING + escape(input[i]);
                i++;
                break;
            }
            if (input[i] == '\'') { //Start a character
                state = CHAR_UNCLOSED;
                output += OPEN_STRING + escape(input[i]);
                i++;
                break;
            }
            if (eqRange(input, i, "//")) { //Start a single line comment
                state = LINE_COMMENT_UNCLOSED;
                output += OPEN_COMMENT + escape(input.substr(i, 2));
                i += 2;
                break;
            }
            if (eqRange(input, i, "/*")) { //Start a multi-line comment
                state = MULTILINE_COMMENT_UNCLOSED;
                output += OPEN_COMMENT + escape(input.substr(i, 2));
                i += 2;
                break;
            }
            if (input[i] == '\n') { //New lines are special!
                output += getNewLineHTML();
                i++;
                break;
            }
            for (size_t j = 0; j < NUMBER_OF_KEYWORDS; j++) //Iterate through keywords
                if (eqRange(input, i, keywords[j])
                        && !isIdentifierCont(input, i + keywords[j].size())) { // The keyword can't be a prefix of an identifier, so test for that
                    output += OPEN_KEYWORD + escape(keywords[j])
                            + CLOSE_KEYWORD;
                    i += keywords[j].size();
                    break;
                }
            //Treat identifiers separately because we need to separate identifiers from keywords.
            if (isIdentifierStart(input, i)) {
                state = IDENTIFIER;
                output += escape(input[i]);
                i++;
                //If the next character is not a part of the identifier, go to the NONE state
                if (i + 1 == input.size() || !isIdentifierCont(input, i + 1)) {
                    state = NONE;
                }
                break;
            }
            //Other characters
            output += escape(input[i]);
            i++;
            break;
        }
        case CHAR_UNCLOSED: {
            if (eqRange(input, i, "\\")) { //Treat escape sequences inside quotes
                output += escape(input.substr(i, 2));
                i += 2;
                break;
            }
            if (input[i] == '\'') { //Close quote
                state = NONE;
                output += escape(input[i]) + CLOSE_STRING;
                i++;
                break;
            }
            output += escape(input[i]); //Other characters go into the literal
            i++;
            break;
        }
        case STRING_UNCLOSED: {
            if (eqRange(input, i, "\\")) { //Treat escape sequences inside quotes
                output += escape(input.substr(i, 2));
                i += 2;
                break;
            }
            if (input[i] == '"') { //Close quote
                state = NONE;
                output += escape(input[i]) + CLOSE_STRING;
                i++;
                break;
            }
            output += escape(input[i]); //Other characters go into the literal
            i++;
            break;
        }
        case LINE_COMMENT_UNCLOSED: {
            if (input[i] == '\n') { //Close comment with new line
                state = NONE;
                output += CLOSE_COMMENT + getNewLineHTML();
                i++;
                break;
            }
            output += escape(input[i]); //Comment body
            i++;
            break;
        }
        case MULTILINE_COMMENT_UNCLOSED: {
            if (eqRange(input, i, "*/")) { //Close multiline comment
                state = NONE;
                output += escape(input.substr(i, 2)) + CLOSE_COMMENT;
                i += 2;
                break;
            }
            if (input[i] == '\n') { //New lines are special!
                output += getNewLineHTML();
                i++;
                break;
            }
            output += escape(input[i]); //Comment body
            i++;
            break;
        }
        case PREPROCESSOR_UNCLOSED: {
            if (input[i] == '\n') { //Close preprocessor statement or go to next line
                int j = i - 1;
                for (; j >= 0 && inRange(input[j], "\n\t "); j--)
                    //Seek las non-whitespace character
                    ;
                if (j < 0 || input[j] != '\\') { //Check if the last non-whitespace character is a backslash
                    state = NONE; //... If it isn't, close the preprocessor statement
                    output += CLOSE_PREPROCESSOR + getNewLineHTML();
                    i++;
                    break;
                }
                output += getNewLineHTML(); //... If it is, we need to extend the preprocessor statement to the next line
                i++;
                break;
            }
            output += escape(input[i]);
            i++;
            break;
        }
        case IDENTIFIER: {
            //If the next character is not a part of the identifier, go to the NONE state
            if (i + 1 == input.size() || !isIdentifierCont(input, i + 1)) {
                state = NONE;
            }
            output += escape(input[i]);
            i++;
            break;
        }
        }
    }
    output += "</ul></code>";
    return output;
}
int main() {
    ifstream input("input.c");
    ofstream output("output.html");
    std::string cCode((std::istreambuf_iterator<char>(input)),
            std::istreambuf_iterator<char>());
    output << highlight(cCode) << endl;
}

```

---
Tags: code-golf, string
---


title: Thinking inside the circle

text:
# Question
Title: Thinking inside the circle
In *as few characters of code as you can*, create an algorithm which will pack *the least number of rectangles* necessary to *completely fill* a rasterized circle with integer radius *r* and return the parameters necessary to create each rectangle.

In the above image, the cyan portion is the "idealized" circle. The darkened cells have been selected by a rasterization algorithm. The area to be filled in is within the black line around the cyan circle.

Here's one way to fill that circle:

Here's another:

**The fine print:**

* All units will/must be centimeters.
* Rectangles should be in the format \[x y width height\], where x and y is the position of the upper left corner and width and height are positive numbers for the width and height from that point.
* + Example: \[10 20 40 20\]\[-10 -20 20 40\] ...
* Rectangles *may overlap each other*, but their bounds *must* be within or coincident to the rasterized circle. Rectangles must not extend past those bounds.
* The algorithm's results must match what would be expected from the bounds given by the Midpoint Circle Algorithm with parameters *x* = 0, *y* = 0, *r* = *radius*.
* While there might be a minimum number of rectangles needed to fill the circle, finding them might make your code longer than it's worth with respect to the length of the code. (see scoring system below)
* It isn't necessary to actually draw anything. Just return the rectangles needed.
* Coordinate system should be Cartesian, so not display graphics definition. Eg. (+x, +y) quadrant is north-east of (0, 0), (+x, -y) is south-east, (-x, -y) is south-west, and (-x, +y) is north-west.

To test for correctness, use your chosen rasterization method to draw a circle. Draw the rectangles from your rectangle packing algorithm. Check for gaps inside the circle or pixels outside the circle.

**Expected signature of function:**

(ℕ radius) → {(ℤ x, ℤ y, ℕ width, ℕ height), ...}

**The very complex scoring system:**

```
[code characters]*([rectangles for radius of 10]/10
                   + [rectangles for radius of 100]/100
                   + [rectangles for radius of 1000]/1000)

```

*Lowest* score wins. In the event of a tie, winner will be the most popular.

Winner will be selected at midnight GMT, January 16th 2014.

# Answer
> 4 votes
# Mathematica (105)

* 63 characters
* 1.665 multiplier (5/10+58/100+585/1000)

Function:

```
f={-#,#}&/@Last/@{n+1,⌈√(#^2-n^2)⌉}~Table~{n,#-1}~SplitBy~Last&

```

For `r=10` its output is

```
f[10]

{{{-5, -10}, {5, 10}}, {{-6, -9}, {6, 9}},
{{-8, -8}, {8, 8}}, {{-9, -6}, {9, 6}}, {{-10, -5}, {10, 5}}}

```

It is coordinates of left-bottom and right-top corners of rectangles (it's native for *Mathematica*'s rectangles)

The number of rectangles for `r=10,100,1000`

```
Length@f@# & /@ {10, 100, 1000}

```

> {5, 58, 585}

Visualization:

```
Graphics[{EdgeForm[Black], EdgeForm@Thickness[0.005], Blue, Opacity[0.3], Rectangle@@@f[10],
 Disk[{0, 0}, 10]}, Axes -> True, GridLines -> {#, #} &@Range[-10, 10]]

```

**Update:** it seems that the theoretical limit is

# Answer
> 4 votes
Pre-rule-change answer:

## C# / ECMAScript 6 - 12

```
r=>r

```

Because overlapping rectangles are allowed, we need at most `r` rectangles.

Proof:

With a circle of radius 10, it can be filled with 10 rectangles. Each rectangle has been highlighted in a distinct colour.

---

Older pre-rule-change answer:

**C# / ECMAScript 6 - 0.444**

```
r=>1

```

I believe this meets all the rules as of the time of this writing.

It evaluates to the number of rectangles required to fill a circle, rasterized with this algorithm:

```
inCircle = max(|x|,|y|) <= radius

```

This algorithm doesn't yield very high-quality results, but it can still be useful. The popular video game *Minecraft* uses this algorithm.

# Answer
> 3 votes
# C#: ~~514.892~~ 479.298

* Characters: 254
* Number of rectangles: 7, 60, and 587. Rectangle multiplier = 1.887

Method takes a single integer as parameter, and returns a `List<Int32Rect>` as the result. Could probably shave a few more characters off by searching for another rectangle class with a shorter name, but `Int32Rect` is probably the most correct one to use here.

You didn't specify which coordinate system we should be using. I'm assuming Cartesian coordinates (X & Y increase toward the top & right), as opposed to the more standard in computer graphics, where Y increases toward the bottom.

```
using System.Collections.Generic;using R=System.Windows.Int32Rect;
class G{List<R>A(int r){var z=new List<R>();int x=r,y=0,e=1-x;while(x>=y)
if(e<0)e+=2*++y+1;else{z.Add(new R(-x,y,2*x,2*y));if(x!=y)z.Add(new R(-y,x,2*y,2*x));
e+=2*(++y- --x+1);}return z;}}

```

## Edit

* Removed namespace.
* In the 10 and 1000 circles, the last two rectangles were exactly the same. As x decreases and y increases, sometimes they meet, sometimes they're one off from each other on the last iteration. On the 100 circle, the last iteration is with x=70,y=71, so there's no duplicate. On the 10 circle, the last iteration is x=y=7, so checking for x!=y eliminates that duplicate rectangle. On the 1000 circle, the last iteration is x=y=707.

Results with 10:

Results with 100:

---
Tags: code-challenge, geometry, optimization
---


title: Manipulate "RELATIVE" using 8 OP-codes

text:
# Question
Title: Manipulate "RELATIVE" using 8 OP-codes
Rules:

1. Your program can be in any programming language.
2. Your program should not take any input.
3. Your program should transform the word "RELATIVE" into "STATIC". The word can at any stage only consist of uppercase letters A-Z.
4. Your program can only use 8 different operations.
5. The length, in number of letters, of the word cannot exceed 10 letters. If letters moves beyond that limit the letters will be deleted.
6. Your program must use all 8 operations before it can start reusing the operations again. All operations must be used the same amount of times.
7. The word must be "STATIC" at the end of the last chunk of 8 operations.
8. The very first OP used in the first chunk of OPs is never executed, so the program must output word "RELATIVE" of the first row.
9. The lines should be outputted in chunks of 8 lines, separated by a double linefeed between the chunks.
10. Your program should output the lines describing how it manipulates the string. Output each iteration of operations, one line for every applied operation in this form:

`<iteration # in 6 numbers>: <operation> <current word after OP is executed>`

The operations available:

```
INS     Move the current word 1 character to the right and
        replace first letter with 'A'.

DEL     Deletes the last letter in the word.

INC     Increase the second letter from the left with 1.
        Example: 'A' converts into 'B' or a 'Z' converts into 'A'.
        If the letter position is outside of the current word, nothing happens.

DEC     Decrease the fourth letter from the left with 4.
        Example: 'T' converts into 'P' or a 'C' converts into 'Y'.
        If the letter position is outside of the current word, nothing happens.

SWT     Swith letter number three from left with letter number two from right.
        If any of the letters are outside of current word, nothing happens.

INV     Invert the current word.

JMP     Invalidates the nextcoming OP.
        If this OP is used as OP #8 in a chunk, nothing happens.

REP     Execute the previous op again.
        If this OP is used as OP #1 in a chunk, nothing happens.

```

Example output (incomplete as the word is not "STATIC" at the end of the last chunk of 8 OPs):

```
000001: REP RELATIVE
000002: DEL RELATIV
000003: INS ARELATIV
000004: INC ASELATIV
000005: SWT ASILATEV
000006: INV VETALISA
000007: JMP VETALISA
000008: DEC VETALISA

000009: DEC VETWLISA
000010: JMP VETWLISA
000011: INS VETWLISA
000012: DEL VETWLIS
000013: REP VETWLI
000014: SWT VELWTI
000015: INC VFLWTI
000016: INV ITWLFV

```

The scoring is: (Sourcecode size in bytes) * (# OP-chunks). The program with the smallest score wins. The competition ends at 2014-12-31.

# Answer
> 8 votes
## GolfScript, ~~338~~ ~~323~~ ~~307~~ ~~300~~ 280 * ~~15~~ 10 = 2800

```
{:x;.2$<)65-x+26%65+[]++\@>+}:d;
{[{}{4-4d}{);}{2 1d}{'A'\+}{-1%}{2$~}{....2<\[-2=]+\3>-2<+\[2=]+\-1>+}]=}:L;
1:i;
'RDLATIVE':&;
'"S<(hR\50%!iS[SA*v7qpq&={=kkkk."Y+iEpi5-]'{32-}%95base`8/
{1:j;0L.@{48-:^j*L@;.&\~:&;i'0'6*\+-6>': ''JDDIIIRSMEENNNEWPCLCSVPT'^>8%' '&n^0>:j;i):i;}%n@;@;}/

```

Newlines added for clarity only, and can be removed. Pretty sure the output is correct.

Test online

It probably can be golfed further.

---

I managed to chop off an entire 5 chunks of op-codes (although I did have to rewrite most of the algorithm).

Output:

```
000001: INC RELATIVE
000002: DEL RELATIV
000003: REP RELATI
000004: INS ARELATI
000005: DEC AREHATI
000006: INV ITAHERA
000007: JMP ITAHERA
000008: SWT ITAHERA

000009: DEC ITADERA
000010: INS AITADERA
000011: INV AREDATIA
000012: DEL AREDATI
000013: INC ASEDATI
000014: JMP ASEDATI
000015: SWT ASEDATI
000016: REP ASEDATI

000017: DEC ASEZATI
000018: INV ITAZESA
000019: DEL ITAZES
000020: SWT ITEZAS
000021: INS AITEZAS
000022: JMP AITEZAS
000023: INC AITEZAS
000024: REP AITEZAS

000025: DEC AITAZAS
000026: REP AITWZAS
000027: INS AAITWZAS
000028: INC ABITWZAS
000029: INV SAZWTIBA
000030: DEL SAZWTIB
000031: JMP SAZWTIB
000032: SWT SAZWTIB

000033: DEC SAZSTIB
000034: DEL SAZSTI
000035: INV ITSZAS
000036: SWT ITAZSS
000037: INS AITAZSS
000038: REP AAITAZSS
000039: JMP AAITAZSS
000040: INC AAITAZSS

000041: DEL AAITAZS
000042: INV SZATIAA
000043: INC SAATIAA
000044: REP SBATIAA
000045: INS ASBATIAA
000046: JMP ASBATIAA
000047: DEC ASBATIAA
000048: SWT ASAATIBA

000049: SWT ASBATIAA
000050: INS AASBATIAA
000051: INV AAITABSAA
000052: INC ABITABSAA
000053: DEL ABITABSA
000054: JMP ABITABSA
000055: DEC ABITABSA
000056: REP ABITABSA

000057: INV ASBATIBA
000058: DEL ASBATIB
000059: INS AASBATIB
000060: DEC AASXATIB
000061: JMP AASXATIB
000062: INC AASXATIB
000063: SWT AAIXATSB
000064: REP AASXATIB

000065: INV BITAXSAA
000066: DEL BITAXSA
000067: REP BITAXS
000068: SWT BIXATS
000069: INS ABIXATS
000070: INC ACIXATS
000071: JMP ACIXATS
000072: DEC ACIXATS

000073: INS AACIXATS
000074: INC ABCIXATS
000075: INV STAXICBA
000076: DEL STAXICB
000077: REP STAXIC
000078: JMP STAXIC
000079: SWT STAXIC
000080: DEC STATIC

```

---
Tags: code-golf, string
---


title: Crazy chemical equations

text:
# Question
Title: Crazy chemical equations
You should get string of chemical equation (no spaces, only letters (upper-case and lower-case), numbers, brackets and math signs) from user and print the answer if equation is **balanced** or not (any pair of positive/negative answers: Yes/No, true/false, 1/0). To make code shorter you can assume that input strings can contain only these elements: Al, Ar, B, Be, C, Cl, Cr, Cu, Fe, H, He, K, N, O, S. And **one more thing**: there could be `-` signs. It's all about math: `+` means addition, `-` means subtraction.

Examples:

*Input:*

```
C6H5COOH-O2=7CO2+3H2O

```

*Output:*

```
No

```

---

*Input:*

```
2Fe(CN)6+2SO2+202=Fe2(SO4)2+6C2N2

```

*Output:*

```
Yes

```

---

*Input:*

```
2SO2=2SO4-2O2

```

*Output:*

```
Yes

```

The shortest code wins.

# Answer
# Mathematica 152

```
f=Times@@@Tr@CoefficientRules@ToExpression@(r=StringReplace)[r[
#<>")",{"="->"-(",x:_?LetterQ|")"~~y_?DigitQ:>x<>"^"<>y}],x_?UpperCaseQ:>" "<>x]⋃{}=={0}&

```

Result:

```
f@"C6H5COOH-O2=7CO2+3H2O"
f@"2Fe(CN)6+2SO2+2O2=Fe2(SO4)2+6C2N2"
f@"2SO2=2SO4-2O2"

```

> False
>
> True
>
> True

I treat the chemical formula as a polynomial, e.g.

Then I just count the coefficients.
> 2 votes

# Answer
## Haskell, ~~400~~ ~~351~~ 308 characters

```
import Data.List
import Text.Parsec
(&)=fmap
r=return
s=string
l f b=(>>=(&b).f)
x=(=<<).replicate
m=sort&chainl1(l x(concat&many1(l(flip x)n i))n)((s"+">>r(++))<|>(s"-">>r(\\)))
i=between(s"(")(s")")m<|>(:[])&(l(:)(many lower)upper)
n=option 1$read&many1 digit
main=getContents>>=parseTest(l(==)(s"=">>m)m)

```

This just might have all the golf squeezed out of it. I don't know if there is another ~~100~~ ~~51~~ 8 characters to be saved!

```
& echo 'C6H5COOH-O2=7CO2+3H2O' | runhaskell Chemical.hs
False

& echo '2Fe(CN)6+2SO2+2O2=Fe2(SO4)2+6C2N2' | runhaskell Chemical.hs
True

& echo '2SO2=2SO4-2O2' | runhaskell Chemical.hs
True

```

Here's the ungolf'd version, in case anyone want to follow along. It is a simple `Parsec` based parser:

```
import Control.Applicative ((<$>), (<*>))
import Data.List
import Text.Parsec
import Text.Parsec.String (Parser)

type Atom = String

{- golf'd as x -}
multiple :: Int -> [Atom] -> [Atom]
multiple n = concat . replicate n

{- golf'd as m -}
chemicals :: Parser [Atom]
chemicals = sort <$> chainl1 molecules op
  where
    op :: Eq a => Parser ([a] -> [a] -> [a])
    op = (char '+' >> return (++))
     <|> (char '-' >> return (\\))

    molecules :: Parser [Atom]
    molecules = multiple <$> number <*> terms

    terms :: Parser [Atom]
    terms = concat <$> many1 term

    term :: Parser [Atom]
    term = flip multiple <$> item <*> number

{- gofl'd as i -}
item :: Parser [Atom]
item = between (char '(') (char ')') chemicals
   <|> (:[]) <$> atom
  where
    atom :: Parser Atom
    atom = (:) <$> upper <*> many lower

{- gofl'd as n -}
number :: Parser Int
number = option 1 $ read <$> many1 digit

{- gofl'd as main -}
main :: IO ()
main = getContents >>= parseTest chemEquality
  where
    chemEquality :: Parser Bool
    chemEquality = (==) <$> chemicals <*> (char '=' >> chemicals)

```
> 2 votes

# Answer
## Python 2.7, 316 276 chars

```
import re
r=re.sub
x='(^|[=+-])'
y=r'\1+\2'
z='(\w)([A-Z(])'
t=r('=','==',r(z,y,r(z,y,r('([A-Za-z)])(\d)',r'\1*\2',r('([=+-]|$)',r')\1',r(x+'(\d+)',r'\1\2*(',r(x+'([A-Z])',r'\1(\2',raw_input())))))))
E=re.findall('[A-Za-z]+',t)
print all(eval(t,{f:f==e for f in E})for e in E)

```

It does a lot of regex-rewriting to convert the input equation into something `eval`able. Then it checks the equation for each element individually.

For instance, the example equations rewrite to (the `t` variable):

```
(C*6+H*5+C+O+O+H)-(O*2)==7*(C+O*2)+3*(H*2+O)
2*(Fe+(C+N)*6)+2*(S+O*2)+2*(O*2)==(Fe*2+(S+O*4)*2)+6*(C*2+N*2)
2*(S+O*2)==2*(S+O*4)-2*(O*2)

```

I'm sure there's more golf to be had on the regex part.
> 2 votes

---
Tags: code-golf
---