title: The Easter Egg Hunt on the Hill

text:
# Question
Title: The Easter Egg Hunt on the Hill
# Easter Egg Hunt

Bot find egg before bunny find egg. Bot happy.

## Overview

This is a challenge in honor of Easter and the Easter egg hunting tradition!

Your bot has a vision of two spaces in every direction, including diagonals, creating a 5x5 square around you that you can see. It is looking for eggs, and whoever finds the most eggs wins!

## The Board

The board will consist of `o`s, which are Easter eggs, `#`s, which are walls, `*`s, which are other players, and s, which are empty spaces.

* It will be a square with edge length `(number of entries) * 3`.
* It will be surrounded by walls.
* Inside of the walls will be an assortment of randomly placed, straight line walls of `#`, which will have a random length between 2 and 10 inclusive. There will be `(number of entries) * 3` of them.
* The eggs will then be placed randomly. There will be `(number of entries) * 4` of them, and they will only be generated on blank () squares.
* There must be at least 7 entires for the board generating process to work properly.

Here is a JSFiddle that will generate a random board for you to test with. Here's an example, with `(number of entries) = 7`:

```
#####################
#        o         ##
#    #    o        ##
#    #o    ######  ##
######     #       ##
## o #     #       ##
##  o#   #o#    o o##
##   #o  # # o  #   #
##   # o # #    #   #
##  ##   # #  o #   #
##  #    #  o   # # #
##  # o  #   ## # # #
##  #           # # #
# o #          ## # #
# o oo         ##o  #
#o  ####### oo ##   #
#        #      #   #
#   o o o#          #
#   o ####   o     o#
#                   #
#####################

```

After the board is generated, each player is placed on a random  square (empty space).

## Input

You will take six lines of input. The first five lines are your field of vision (spaces out of bounds of the board will be represented by `X`, and the middle space will always be `*`, you), and the sixth line will be empty (at first).

## Output

You will output three lines. First, the direction that you want to move in:

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

```

(9 is a no-op if you don't want to move), second, one of `A`ttack, `C`ounter, or `N`othing (this will be explained in depth soon), and the thrid line will be any string of length up to 1024. This will be your bot's memory. You may use it for whatever you would like, or you may leave it blank. This memory will then be the sixth line of input to your program on the next run.

All further lines of output are ignored, and if there is only one line, the second is assumed to be blank.

## Moving

The following process is used to determine where you moved:

* If, when you move, you end up in an empty space (), your player is placed into that space.
* If you end up in a wall (`#`), your move is ignored and you lose your turn.
* If you end up in an egg (`o`) or on a player (`*`), this information is stored and will be used after everybody has moved.

After everybody has moved, ambiguities are resolved.

If there are two players that have landed on the same space, a fight occurs! This is where the `A`/`C`/`N` comes in to play. `A`ttack beats `N`othing (normal attack), `N`othing beats `C`ounter (you can't counter nothing), and `C`ounter beats `A`ttack (counterattack). The player who wins this fight stays on their square, and the player who loses goes back to the original square that they started on. In the event of a tie, both players go back to where they were.

If a losing or tied player goes back to where they were and there is another player there, there is no fight and the other player will also revert to its original space. If *this* space has another player, *that* player goes back, and this continues until all players are in different spaces.

If there are three or more players on one space, they all revert back to their original positions.

If any player is still standing on an egg...

* If the player chose `A`, the egg is destroyed.
* If the player chose `C`, nothing happens and the player reverts to its original space.
* If the player chose `N`, the player picks up the egg! The player's score is incremented by one and the egg is removed.

## Languages

You may use any language that is freely available on Windows, OSX, and Linux, to ensure fairness among each contestant. If the code is not freely runnable but can be compiled or packaged into a format that is, please include this format in your answer as well. Ideally, if you can compile your code into a more common language (i.e. CoffeeScript -\> JavaScript), please do so.

## Scoring

Your score will be the average number of eggs you collect out of ten runs. A run ends when all eggs are collected or when `(number of entries * 25)` turns have passed. I will manually make sure that it is possible to reach all eggs for each map (by continually generating maps until all eggs are reachable).

## Scoreboard

A scoreboard will be added when all of the following conditions are met:

* At least seven valid entries with a positive or zero score (not downvoted) have been submitted
* At least 48 hours has passed since the creation of this challenge (UTC 14:23)

The rules will not change during this pre-contest period, except to add clarification where a rule was unclear. ~~Once the scoreboard is put up, the testing program will also be posted here so that you can test your entries.~~ The testing code for this is still work-in-progress, but it's playable and it works. Here's the GitHub repo.

# Answer
> 3 votes
## Cart'o'Gophers

Here is another submission - and this one is actually meant to be competitive. Again, it's in Ruby. So run it with `ruby cartogophers.rb`. This took a lot longer than expected...

```
require 'zlib'
require 'base64'

def encode map, coords
    zipped = Zlib::Deflate.deflate map.join
    encoded = Base64.encode64(zipped).gsub("\n",'')
    "#{coords[:x]}|#{coords[:y]}|#{map.length}|#{encoded}"
end

def decode memory
    memory =~ /^(\d+)[|](\d+)[|](\d+)[|](.*)$/
    coords = {x: $1.to_i, y: $2.to_i}
    n_rows = $3.to_i
    encoded = $4
    decoded = Base64.decode64 encoded
    unzipped = Zlib::Inflate.inflate decoded
    n_cols = unzipped.length / n_rows;
    return unzipped.scan(/.{#{n_cols}}/), coords
end

def update map, fov, coords
    if coords[:x] < 2
        map.map! { |row| '?' << row }
        coords[:x] += 1
    elsif coords[:x] >= map[0].length - 2
        map.map! { |row| row << '?' }
    end

    if coords[:y] < 2
        map.unshift '?' * map[0].length
        coords[:y] += 1
    elsif coords[:y] >= map.length - 2
        map.push '?' * map[0].length
    end

    fov.each_index do |i|
        map[coords[:y]-2+i][coords[:x]-2, 5] = fov[i]
    end

    return map, coords
end

def clean_up map
    map.each do |row|
        row.gsub!('*', ' ')
    end
end

DIRECTIONS = [
    [],
    [-1,-1],
    [ 0,-1],
    [ 1,-1],
    [ 1, 0],
    [ 1, 1],
    [ 0, 1],
    [-1, 1],
    [-1, 0],
    [ 0, 0]
]

def move_to dir, coords
    {
        x: coords[:x] + DIRECTIONS[dir][0],
        y: coords[:y] + DIRECTIONS[dir][1]
    }
end

def get map, coords
    if coords[:x] < 0 || coords[:x] >= map[0].length ||
       coords[:y] < 0 || coords[:y] >= map.length
        return '?'
    end
    map[coords[:y]][coords[:x]]
end

def set map, coords, value
    unless coords[:x] < 0 || coords[:x] >= map[0].length ||
       coords[:y] < 0 || coords[:y] >= map.length
        map[coords[:y]][coords[:x]] = value
    end
    map[coords[:y]][coords[:x]]
end

def scan_surroundings map, coords
    not_checked = [coords]
    checked = []
    cost = { coords => 0 }
    direction = { coords => 9 }
    edges = {}

    while not_checked.length > 0
        current = not_checked.pop

        checked.push current
        (-1..1).each do |i|
            (-1..1).each do |j|
                c = { x: current[:x]+i, y: current[:y]+j }
                unless not_checked.include?(c) || checked.include?(c)
                    if get(map, c) == '#'
                        checked.push c
                    elsif get(map, c) == '?'
                        checked.push c
                        edges[current] = { cost: cost[current], move: direction[current] }
                    else
                        not_checked.unshift c

                        cost[c] = cost[current] + 1
                        if direction[current] == 9 # assign initial direction
                            direction[c] = DIRECTIONS.find_index([i,j])
                        else
                            direction[c] = direction[current]
                        end

                        if get(map, c) == 'o'
                            return direction[c], if cost[c] == 1 then 'N' else 'A' end
                        end

                        edges[c] = { cost: cost[c], move: direction[c] } if c[:x] == 0 || c[:x] == map[0].length - 1 ||
                                                                            c[:y] == 0 || c[:y] == map.length - 1
                    end
                end
            end
        end
    end

    # If no egg has been found return the move to the closest edge
    nearest_edge = edges.keys.sort_by { |c| edges[c][:cost] }.first
    if edges.length > 0
        return edges[nearest_edge][:move], 'A'
    else
        # The entire map has been scanned and no more eggs are left.
        # Wait for the game to end.
        return 9, 'N'
    end
end

input = $<.read.split "\n"
fov = input[0..4]
memory = input[5]

if memory
    map, coords = decode memory
    map, coords = update(map, fov, coords)
else
    map = fov
    coords = {x: 2, y: 2}
end
clean_up map

move, attack = scan_surroundings(map, coords)

memory = encode map, move_to(move, coords)

puts "#{move}
#{attack}
#{memory}"

```

This bot remembers what it has seen before and tries to construct a larger map at each turn. It then uses a breadth-first search for the nearest egg and heads that way. If there is no egg that can be reached on the current map, the bot heads for the nearest open edge of its map (so as to expand the map quickly in a direction it can still move).

This bot has no concept of other bots yet and no fighting strategy either. Since I haven't found a reliable way to determine if my move has been successful, this can cause some problems. I simply always assume that the move has been successful - so if it wasn't new patches will be loaded into the map in the wrong places, which may or may not be harmful to pathfinding.

The bot uses the memory to store the map and its new position on the map (assuming the move will be successful). The map is stored without line breaks, zipped and base64 encoded (along with the number of rows of the map, so that the line breaks can be reinserted). This compression brings the size down to about a third of the uncompressed map, so having a shade over 1000 bytes, I could store a map of about 3000 cells, which roughly corresponds to fully exploring a map with 18 bots. As long as there are nowhere near that many submissions, I don't think I can be bothered to figure out a fix for that case.

~~After a few test runs against 5 `dumbbot`s and 1 `naivebot` (my other submission), it either performed really badly (like 1 or 2 eggs) or outperformed the others by a considerable margin (7 to 9 eggs). I may think about a better fighting strategy and how I can determine if I actually moved or not. Both might be able to improve the score somewhat.~~

Oh and if you're wondering about the name of the bot, you should read The Order of The Stick (last panel on this comic).

**EDIT:** There were a few bugs with detecting the edges of the discovered map. Now that I've fixed them this bot always gets scores of about `20` against 5 `dumbbot`s and 1 `naivebot`. That's more like it! If you add `$stderr.puts map` to my bot now, you can really see how he systematically uncovers the map and collects all eggs in the meantime. I've also decided to choose `A` instead of `N` whenever not stepping onto an egg, to reduce the probability of moving back to the bot's original cell (which partly screws up the map).

(It doesn't perform quite as well against 6 `naivebot`s, especially since it's very possible to end up in a "deadlock" with another bot when they both repeatedly want to grab an egg and choose `N`. I need to think about that...)

# Answer
> 3 votes
**Java Bunny**

This bunny hasn't finished growing up yet (I still plan to make changes), but it's a starting point for right now. He looks for the closest egg and goes towards it. There isn't wall detection or out-of-bounds detection (yet). He'll go to pick up the egg he lands on, but otherwise he'll try to push he way around and attack anything else. If there are no nearby eggs, he'll start following the nearest bunny. They might know something that he doesn't. Otherwise, he'll just pick a random direction to walk. And he's pretty forgetful (no use of the memory variable).

Plans moving forward:

* Make decisions based on walls/out-of-bounds
* Pick paths with a purpose, rather than randomly
* Use the memory to determine the direction I was going before

**Update 1** My bunny will follow other bunnies if he doesn't see an egg. Also refactored the "find nearest egg" code into it's own method.

```
import java.util.*;

public class EasterEggHunt {

    // board chars
    public static final char EGG = 'o';
    public static final char WALL = '#';
    public static final char BUNNY = '*';
    public static final char SPACE = ' ';
    public static final char OUT_OF_BOUNDS = 'X';

    // player moves
    public static final char ATTACK = 'A';
    public static final char COUNTER = 'C';
    public static final char NOTHING = 'N';

    // directions
    public static final int UPPER_LEFT = 1;
    public static final int UP = 2;
    public static final int UPPER_RIGHT = 3;
    public static final int RIGHT = 4;
    public static final int LOWER_RIGHT = 5;
    public static final int DOWN = 6;
    public static final int LOWER_LEFT = 7;
    public static final int LEFT = 8;
    public static final int STAY = 9;

    // the size of the immediate area
    // (I'll be at the center)
    public static final int VISION_RANGE = 5;

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);

        char[][] immediateArea = new char[VISION_RANGE][VISION_RANGE];

        for (int i = 0; i < VISION_RANGE; ++i) {
            String line = input.nextLine();
            for (int j = 0; j < VISION_RANGE; ++j) {
                immediateArea[i][j] = line.charAt(j);
            }
        }

        String memory = input.nextLine();

        int moveDirection = decideMoveDirection(immediateArea, memory);
        System.out.println(moveDirection);

        char action = decideAction(immediateArea, memory, moveDirection);
        System.out.println(action);

        // change the memory?
        System.out.println(memory);

    }

    private static int decideMoveDirection(char[][] immediateArea, String memory) {

        // if there's a nearby egg, go towards it
        int direction = nearestBoardObject(immediateArea, EGG);

        // if we didn't find an egg, look for a bunny
        // (maybe he knows where to find eggs)
        if (direction == STAY)
            direction = nearestBoardObject(immediateArea, BUNNY);

        // otherwise, pick a random direction and go
        // we want to also have the chance to stop and catch our breath
        if (direction == STAY)
            direction = new Random().nextInt(STAY + 1);

        return direction;
    }

    private static int nearestBoardObject(char[][] immediateArea, char boardObject) {

        // start at the center and go outward (pick a closer target over a farther one)
        int spacesAway = 1;
        int meX = immediateArea.length / 2;
        int meY = immediateArea[meX].length / 2;

        while (spacesAway <= immediateArea.length / 2) {

            // I like to look right, and go clockwise
            if (immediateArea[meX][meY + spacesAway] == boardObject)
                return RIGHT;
            if (immediateArea[meX + spacesAway][meY + spacesAway] == boardObject)
                return LOWER_RIGHT;
            if (immediateArea[meX + spacesAway][meY] == boardObject)
                return DOWN;
            if (immediateArea[meX + spacesAway][meY - spacesAway] == boardObject)
                return LOWER_LEFT;
            if (immediateArea[meX][meY - spacesAway] == boardObject)
                return LEFT;
            if (immediateArea[meX - spacesAway][meY - spacesAway] == boardObject)
                return UPPER_LEFT;
            if (immediateArea[meX - spacesAway][meY] == boardObject)
                return UP;
            if (immediateArea[meX - spacesAway][meY + spacesAway] == boardObject)
                return UPPER_RIGHT;

            ++spacesAway;
        }

        // if the target object isn't in the immediate area, stay put
        return STAY;

    }

    private static char decideAction(char[][] immediateArea, String memory, int moveDirection) {

        char destinationObject = getDestinationObject(immediateArea, moveDirection);

        switch (destinationObject) {

            case EGG:
                // don't break the egg
                return NOTHING;
            default:
                // get really aggressive on everything else
                // other players, walls, doesn't matter
                return ATTACK;

        }

    }

    private static char getDestinationObject(char[][] immediateArea, int moveDirection) {

        // start at my spot (middle of the board) and figure out which direction I'm going
        int targetX = immediateArea.length / 2;
        int targetY = immediateArea[targetX].length / 2;

        switch (moveDirection) {

            case RIGHT:
                ++targetY;
                break;
            case LOWER_RIGHT:
                ++targetX;
                ++targetY;
                break;
            case DOWN:
                ++targetX;
                break;
            case LOWER_LEFT:
                ++targetX;
                --targetY;
                break;
            case LEFT:
                --targetY;
                break;
            case UPPER_LEFT:
                --targetX;
                --targetY;
                break;
            case UP:
                --targetX;
                break;
            case UPPER_RIGHT:
                --targetX;
                ++targetY;
                break;
            // otherwise we aren't moving

        }

        return immediateArea[targetX][targetY];

    }

}

```

# Answer
> 0 votes
# `N`aiveBot (in Ruby)

Here is a very simplistic bot to get the egg rolling (we want to hit those 7 submissions quick, right?). My Ruby isn't very idiomatic so this code may make proper rubyists cringe in pain. Read at your own risk.

```
input = $<.read
$data = input.split("\n")

def is_egg x, y
    $data[y+2][x+2] == 'o'
end

def is_wall x, y
    $data[y+2][x+2] == '#'
end

def is_empty x, y
    $data[y+2][x+2] == ' '
end

def is_player x, y
    $data[y+2][x+2] == '*'
end

if (is_egg(-2,-2) || is_egg(-2,-1) || is_egg(-1,-2)) && !is_wall(-1,-1) || is_egg(-1,-1)
    dir = 1
elsif is_egg(0,-2) && !is_wall(0,-1) || is_egg(0,-1)
    dir = 2
elsif (is_egg(2,-2) || is_egg(2,-1) || is_egg(1,-2)) && !is_wall(1,-1) || is_egg(1,-1)
    dir = 3
elsif is_egg(2,0) && !is_wall(1,0) || is_egg(1,0)
    dir = 4
elsif (is_egg(2,2) || is_egg(2,1) || is_egg(1,2)) && !is_wall(1,1) || is_egg(1,1)
    dir = 5
elsif is_egg(0,2) && !is_wall(0,1) || is_egg(0,1)
    dir = 6
elsif (is_egg(-2,2) || is_egg(-2,1) || is_egg(-1,2)) && !is_wall(-1,1) || is_egg(-1,1)
    dir = 7
elsif is_egg(-2,0) && !is_wall(-1,0) || is_egg(-1,0)
    dir = 8
else
    dir = rand(8) + 1
end

attack = 'N'
puts "#{dir}
#{attack}
"

```

Run with `ruby naivebot.rb`.

I'm simply hardcoding a few cases, where an egg is visible and not obstructed by a wall. It doesn't even go for the closest egg, but picks the first move that makes sense. If no such egg is found, the bot makes a random move. It disregards all other players and never attacks or counters.

# Answer
> 0 votes
# WallFolower

(deliberate pun) in **Python 3**:

```
import sys
import random

#functions I will use
dist       = lambda p1,p2: max(abs(p2[1] - p1[1]), abs(p2[0] - p1[0]))
distTo     = lambda p    : dist((2,2), p)
cmp        = lambda x,y  : (x > y) - (x < y)
sgn        = lambda x    : (-1,0,1)[(x>0)+(x>=0)]
move       = lambda p    : (sgn(p[0] - 2), sgn(p[1] - 2))
unmove     = lambda p    : (p[0] * 2 + 2, p[1] * 2 + 2)
outputmove = lambda p    : (1,2,3,8,9,4,7,6,5)[(sgn(p[0] - 2) + 1) + 3*(sgn(p[1]-2) + 1)]
def noeggfinish(move):
    print(outputmove(unmove(move)))
    print('ACN'[random.randint(0, 2)])
    print("1"+move)
    sys.exit(0)

#beginning of main body
view    = [list(l) for l in map(input, ('',)*5)] #5 line input, all at once.
memory  = input() #currently used only as last direction moved in a tuple
eggs    = []
enemies = []
for y in range(5):
    for x in range(5):
        if   view[y][x] == 'o': eggs    += [(x,y)]
        elif view[y][x] == '*': enemies += [(x,y)]

eggs.sort(key = lambda p:distTo(p)) #sort by how close to me they are.

tiedeggs = []
end = 0
for egg in eggs[:]:
    if end:break
    for enemy in enemies:
        exec({
            -1: 'eggs.remove(egg)',
             0: 'tiedeggs += egg',
             1: 'end=1'
        }[cmp(dist(enemy, egg), distTo(egg))])
        if end:break
if eggs:
    print(outputmove(eggs[0]))
    print('N')              #no attack here
    print("0"+move(eggs[0]))
    sys.exit(0)
elif tiedeggs:
    print(outputmove(tiedeggs[0]))
    print('N')              #no attack here
    print("0"+move(tiedeggs[0]))
    sys.exit(0)
#now there are no eggs worth going for
#do a LH wall follow

lastmove = eval(memory[1:]) #used to resolve ambiguity
if lastmove[0] and lastmove[1]:
    lastmove[random.randint(0,1)] = 0 #disregard diagonal moves
if eval(memory[0]):
    exec("check=view[%n][%n]"%{(0,-1):(0,0),(1,0):(4,0),(0,1):(4,4),(-1,0):(0,4)}[lastmove])
    if check == '#':
        noeggfinish(lastmove)
    else:pass
#currently unimplemented
#move randomly
noeggfinish(tuple([(x,y) for x in [-1,0,1] for y in [-1,0,1] if (x,y) != (0,0)))

```

Moves to an egg if there is an egg in sight, but only if it is closer to that egg than another robot. If there is a tie in distance, it goes for it anyways. Otherwise, does a LH wall follow (not currently well implemented).

Still needs work on the wall follow, but I'll post this here anyways.

---
Tags: king-of-the-hill
---


title: Increment Bitwise

text:
# Question
Title: Increment Bitwise
Make a function that increments a number using only bitwise, loops, and conditions.

**Rules:**

1. All entries must be as per the language spec defined below.
2. Scoring is not of code length, but of the points for each operation given below.
3. The entry point is `inc(a)`, for "increment and return a".
4. Lowest score wins.

See the example to help with scoring.

**Language Spec (strict JS subset):**

All input is assumed to be signed 32-bit integers, with input being in the range \[-231+1, 231-2\] (interval notation), with the upper bound to give room for the increment. All output is assumed to be within the range \[-231+2, 231-1\].

Whitespace is never syntactically significant beyond separating literals, keywords, and newline-ended comments. Booleans for conditions can and may be implicitly converted to integers, with `1 == true` and `0 == false`. All variables are passed by value (as they are all primitives).

Cost is given for each element, with "per use" implied.

Comments: (0 pts)

```
/* like this */
// or this

```

Numeric or variable literal: (0 pts)

```
i, someVariable, 2, etc.

```

Boolean literal: (0 pts)

```
true  // == 1, implicit conversion
false // == 0, implicit conversion

```
* Note: Integer to boolean conversion is as follows (in pseudocode):

```
if 0: true
else: false

```

Grouping: (0 pts)

```
(foo && bar);

```

Function declaration: (0 pts)

```
function foo() { ... } // braces required
function bar(a) { ... }

```

Declare variable: (0 pts)

```
var a;

```

Assignment: (1 pt)

```
var a = 1; // semicolon required to terminate statement
a = 2; // only needs declared once
var b = a;
// b = a = 3; // cannot assign in right side of statement
var c = a << 5;
var d = a ^ (c << 5);

```

Equality/Inequality: (1 pt)

```
x == 1; // equality
x != 1; // inequality
x > y; // greater than
x >= y; // greater than or equal to
x < y; // less than
x <= y; // less than or equal to

```

Logical operators: (1 pt)

* `!a` (not)
* `a && b` (and, returns 1 if both are true, 0 otherwise)
* `a || b` (or, returns 1 if either are true, 0 otherwise)

Bitwise operators: (1 pt)

* `~a` (not)
* `a & b` (and)
* `a | b` (or)
* `a ^ b` (exclusive or)
* `a << b` (arithmetic left shift)
* `a >> b` (arithmetic right shift)
* `a >>> b` (logical right shift)

Augmented assignment: (2 pts)

```
a &= b; // example

```

If statement: (condition value + 1 pt)

```
if (condition) { ... }
if (x == 2) { ... } // worth 2 pts
if (x) { ... } // x is nonzero, worth 1 pt

```

If-Else statement: (condition value + 2 pts)

```
if (condition) { ... } else { ... }

```

While statement: (condition value + 2 pts)

```
while (condition) { ... }
while (x == 2) { ... } // worth 3 pts
while (x) { ... } // evaluation same as in if, worth 2 pts

```

Do-While statement: (condition value + 2 pts)

```
do { ... } while (condition); // semicolon required

```

Return statement: (number of points for statement on right + 1 pt)

```
return foo; // semicolon required, worth 1 pt
return a & b; // worth 2 pts

```

Function call: (number of parameters + 2 pts)

```
foo(); // worth 2 pts
bar(1, 2) // worth 2 + 2 = 4 pts

```

Operator precedence (first to last performed):

1. `( ... )`
2. `~`/`!` (right-to-left)
3. `<<`/`>>`/`>>>` (left-to-right)
4. `>`/`<`/`>=`/`<=` (left-to-right)
5. `==`/`!=` (left-to-right)
    * Note: `1 == 1 == 1` works out to `0 == 1` which is `0`.
6. `&` (left-to-right)
7. `^` (left-to-right)
8. `|` (left-to-right)
9. `&&` (left-to-right)
10. `||` (left-to-right)

**Example scoring:**

This (ficticious) example would score 14 points. See comments for details.

```
function inc(a) {
  var b = a; // adds 1 pt for assignment
  if (!a) return 0; // adds 3 pts: 2 for if and 1 for return
  while (a & b) { // adds 3 pts: 2 for while and 1 for `&`
    b >>= a ^ b; // adds 3 pts: 2 for augmented assignment, 1 for `^`
    a = b << 1; // adds 2 pts: 1 for assignment, 1 for `<<`
  }
  return a ^ b; // adds 2 pts: 1 for return, 1 for `^`
}

```

# Answer
# 10

Works for negative numbers.

```
function inc(x)
{
    if(x & 1)                       // 1 + 1
        return inc(x >>> 1) << 1;   // 1 + 3 + 1 + 1

    return x | 1;                   // 1 + 1
};

```
> 5 votes

# Answer
# 11 points (also works for negative numbers)

```
function inc(a) {
  var t = 1;             // 1 pt
  while (a & t) {        // 3 pts
    a &= (~t);           // 3 pts
    t <<= 1;             // 2 pts
  }
  return a|t;            // 2 pts
}

```

I thought this was supposed to actually increment the number it was called on, but I am not familiar with a way to pass integers by reference in JS.
> 2 votes

# Answer
## 10 (works for negative numbers)

```
function inc(a)
{
    var c = 1;                   // 1
    while (c)                    // 2
    {
        var s = a ^ c;           // 2
        c = (a & c) << 1;        // 3
        a = s;                   // 1
    }
    return a;                    // 1
}

```
> 2 votes

# Answer
# 11 (Works for negatives)

```
function inc(a) {
    for(var b=1;a&b;b<<=1) {
        a=a^b;
    }
    return a^b
}

```
> 2 votes

# Answer
# 10 (13 if it must work for negative numbers)

```
function inc(a){
  var m=1;             // 1pts
  while((a & m)==m){   // 4pts
    m=(m<<1)|1;        // 3pts
  }
  return a^m;          // 2pts
}

```
> 0 votes

---
Tags: restricted-source, javascript, atomic-code-golf
---


title: Low Entropy Literature

text:
# Question
Title: Low Entropy Literature
This is one of my favourite poems I wanted to share. Especially because it looks good for compressing. Who cares about literature in the 21st century anyway.

# Goal

Your goal is to write the **shortest program** possible that prints out the following poem:
http://pastebin.com/aXV0C515

# Rules

* The HQ9Monkey++ language is **prohibited**

# Answer
# Python 2.x (Baseline answer, ~~651~~ 650, +/- 40% gain)

```
print'eJxNU0G2pDAI3OcUXA2VmLxJwE+S73NOP2DHHncIBRSVsiFvonCSKDWown/oKpYLQRJEq0RUifFd0XzQ/F6UcANhWFAWXFqwOvREcGYLWtdRG8joE94HUwtRpc6Ew+R8hqG2ED5xIhXjo7kR+MyY99RD5gmNmcp2Fz7f7WegUnglkLGLZtsfEv4+fA/smbg3WPXKvDtVa5s796zlIYrD91VsnfSRBcuRcKEe6Dc/QDhk8NYg5WbDFE8OkajDl+lhJ5g+l7XNNTWXAgZnQi0XVNwoWM6ulUfmipcwox0fTCE2pgYc7DEu5Zt80K61pRocevfMRX8cIl8iYo0JFXkf1O5HWlXO7T/VLl76PoCpxrBKdbBAs+BbsgPcGj2JPY/dL+xLccWfQbCb7KUgrCnXA/kvUTBriBGRe3lHBsI1wUImb3AHffT7TGc6W0uuIfbgLMmuM2Xuln7m4k4ApcObTYmenicfx0EKlaoRMJt576diBkxJhnE1Py6udHJfzLYTt83w5lbU7qdW1DWZy31PH8pQKM6o2Ziy2RbU2l4Pmq33gnj32EWx0NrplvamPU2LK70J74Ph5ejWX5QbnKJl/kt3dBL4gH/NMmPU'.decode('base64').decode('zip')

```
> 6 votes

# Answer
# Bash, 499 bytes

Why wasn't this a standard loophole?

```
0000000: 7461 696c 202d 6334 3733 2022 2430 227c  tail -c473 "$0"|
0000010: 7a63 6174 3b65 7869 740a 1f8b 0800 5d28  zcat;exit.....](
0000020: a753 0003 4d53 5176 8430 08fc cf29 b81a  .S..MSQv.0...)..
0000030: 2a9a bc26 6049 529f 3d7d 27ae 6ef7 2fc2  *..&`IR.=}'.n./.
0000040: 00c3 3056 d6c5 9c0e 3197 4ac5 f44b ce8c  ..0V....1.J..K..
0000050: 5808 1669 4566 65b7 75fd cc78 dae5 fe9e  X..iEfe.u..x....
0000060: 5c78 2153 9ad8 269e 6a40 9e5a 143a 121e  \x!S..&.j@.Z.:..
0000070: b579 2f95 acb7 1bde ba4a 0dab 5bb9 0303  .y/......J..[...
0000080: 66c7 d38c bd06 0aaf 8f28 6e20 e4a9 0a8d  f........(n ....
0000090: a66b da62 0b49 6fec 9a24 2f57 e2f5 5dbf  .k.b.Io..$/W..].
00000a0: 3bbb 848f 002b 37f3 0402 21f2 cf43 78e7  ;....+7...!..Cx.
00000b0: 9644 5ba5 d9cf a4db e08a b267 e896 3c3f  .D[........g..<?
00000c0: 54b9 8f81 856b 137f 84e1 bc47 9ea4 05f9  T....k.....G....
00000d0: 490f 9076 ebba 548a a9a2 9bf3 a161 1569  I..v..T......a.i
00000e0: f4a6 ba63 0728 74a2 ec99 5352 ce04 bc0a  ...c.(t...SR....
00000f0: 7b3e a9f0 2201 31ec 6b8f d285 4f53 65ac  {>..".1.k...OSe.
0000100: 1f20 9282 2b80 5dc7 9ba7 fc0e 3ee8 2137  . ..+.].....>.!7
0000110: 4295 76bf 6a9e 495f 0363 6f2a 86ca c8ce  B.v.j.I_.co*....
0000120: ba75 a9d7 a166 b763 f927 db6c a4de 3780  .u...f.c.'.l..7.
0000130: 704a b395 0136 aa78 bc53 d860 d8a3 45c3  pJ...6.x.S.`..E.
0000140: 85a0 80a9 04c8 35f3 7717 daa0 7cce 4c73  ......5.w...|.Ls
0000150: 4c65 67fd 1509 b087 8188 5dc3 1b2b 09cf  Leg.......]..+..
0000160: 9126 81c0 61b8 e8a5 e0ab bbca 516b 1c2a  .&..a.......Qk.*
0000170: 720b 83a5 603d 4873 95b4 23e5 6106 72d9  r...`=Hs..#.a.r.
0000180: 4731 a468 f1b9 7adf 7771 2a52 4000 561b  G1.h..z.wq*R@.V.
0000190: b5af 0c4c 18a3 7570 8527 a721 751c d6b8  ...L..up.'.!u...
00001a0: cb0e 5e16 e0e1 58f6 3656 2dec 7384 d3c7  ..^...X.6V-.s...
00001b0: 9cd6 5d29 cb7a bf2a dae4 0553 d8d1 e0ff  ..]).z.*...S....
00001c0: a209 b527 ad57 0d36 5ab3 cc4d 2e69 2fda  ...'.W.6Z..M.i/.
00001d0: b76f 7996 4fc2 5b57 fa30 756d 1f94 2b1d  .oy.O.[W.0um..+.
00001e0: e6f9 fe9f aed7 2174 35f8 03f5 2b98 87b5  ......!t5...+...
00001f0: 0300 00                                  ...

```

base64:

```
dGFpbCAtYzQ3MyAiJDAifHpjYXQ7ZXhpdAofiwgAXSinUwADTVNRdoQwCPzPKbgaKpq8JmBJUp89
fSeubvcvwgDDMFbWxZwOMZdKxfRLzoxYCBZpRWZlt3X9zHja5f6eXHghU5rYJp5qQJ5aFDoSHrV5
L5WstxveukoNq1u5AwNmx9OMvQYKr48obiDkqQqNpmvaYgtJb+yaJC9X4vVdvzu7hI8AKzfzBAIh
8s9DeOeWRFul2c+k2+CKsmfoljw/VLmPgYVrE3+E4bxHnqQF+UkPkHbrulSKqaKb86FhFWn0prpj
Byh0ouyZU1LOBLwKez6p8CIBMexrj9KFT1NlrB8gkoIrgF3Hm6f8Dj7oITdClXa/ap5JXwNjbyqG
ysjOunWp16Fmt2P5J9tspN43gHBKs5UBNqp4vFPYYNijRcOFoICpBMg183cX2qB8zkxzTGVn/RUJ
sIeBiF3DGysJz5EmgcBhuOil4Ku7ylFrHCpyC4OlYD1Ic5W0I+VhBnLZRzGkaPG5et93cSpSQABW
G7WvDEwYo3VwhSenIXUc1rjLDl4W4OFY9jZWLexzhNPHnNZdKct6vyra5AVT2NHg/6IJtSetVw02
WrPMTS5pL9q3b3mWT8JbV/owdW0flCsd5vn+n67XIXQ1+AP1K5iHtQMAAA==

```
> 3 votes

---
Tags: code-golf, kolmogorov-complexity
---


# Question
Title: Find the fastest swim relay (shortest path of unique nodes and types)
**fastest relay time** = lowest possible total integer value of (a freestyle swimmers time) + (1 breastroke swimmers time) + (another backstroke swimmers time) + (another butterfly swimmers time)

* Each swimmer must be unique to the relay (no duplicates)
* Each stroke must be used once

Input Data: array of dictionaries, where each single dictionary represents a swimmer's swim times for each stroke. Each dictionary has the named properties of 'fly','back','breast','free':

Example Input:

```
[
{'Fly': 10, 'Breast': 48.26, 'Free': 28.43, 'Back': 34},
{'Fly': 47.51, 'Breast': 24, 'Free': 28.47, 'Back': 10},
{'Fly': 26, 'Breast': 46.44, 'Free': 10, 'Back': 30},
{'Fly': 37.81, 'Breast': 10, 'Free': 24, 'Back': 49},
{'Fly': 38.31, 'Breast': 29, 'Free': 20, 'Back': 10}
]

```

Example Output:

```
40

```

(this is an easy case where the best relay is simply the fastest person in each stroke; other times you might need to have the 3rd fastest breastroker swim breastroke in order to get the lowest overall time!)

Example Measurement of a relay using the first 4 swimmers in the data set above:

```
swimmer 1 swims fly and his time is 10
total += 10
swimmer 2 swims back and his time is 10
total += 10
swimmer 3 swims fly and his time is 10
total += 10
swimmer 4 swims breast and his time is 10
best relay total for these 4 people = 40

```

Output Data: should be a single float or integer value representing the total time of the best relay. (a legal relay includes a fly swimmer, a back swimmer, a breast swimmer, and a free swimmer, each leg of the relay swam by a unique swimmer)

EDIT: brute force vs dynamic parameter removed.

# Answer
> 1 votes
Meh, I'm no Python programmer by any stretch of the imagination. Hell, some would even hesitate to call me a programmer. But as nobody else has answerred this, why not post my solution? If anything else, it was fun just to brush up on the very Python basics:

```
swimmers = [{'Fly': 10, 'Breast': 48.26, 'Free': 28.43, 'Back': 34},
{'Fly': 47.51, 'Breast': 24, 'Free': 28.47, 'Back': 10},
{'Fly': 26, 'Breast': 46.44, 'Free': 10, 'Back': 30},
{'Fly': 37.81, 'Breast': 10, 'Free': 24, 'Back': 49},
{'Fly': 38.31, 'Breast': 29, 'Free': 20, 'Back': 10}]

bestTime = float('inf')

for fly in range(len(swimmers)):
    for breast in range(len(swimmers)):
        for free in range(len(swimmers)):
            for back in range(len(swimmers)):
                if len(set([fly,breast,free,back])) > 3:
                    current = swimmers[fly]['Fly'] + swimmers[breast]['Breast'] + swimmers[free]['Free'] + swimmers[back]['Back']
                    if current < bestTime:
                        bestTime = current

print bestTime

```

---
Tags: fastest-code, path-finding
---


title: Restricted minumum

text:
# Question
Title: Restricted minumum
You need to find the sum of minimum values of two list (same size) of small numbers. In a C like language, that could be expressed as:

`v = min(a[0],b[0]) + min(a[1],b[1])+ min(a[2],b[2]) ...`

The range of values is 0..7 and the 2 list can have up to 7 values. If you like, all the values in each list can be stored as a single 32 bit number.

My goal is avoiding branches in code, so the rules are

* Single line expression,
* No function calls or method calls (except for basic operations like sum, if your language mandate this),
* No if statements, including things that compile to if statements such as ternary operators or "greater than" operators

**Edit 1** To clarify, what I want is 'no branches in code'. So, no if, no calls (function of methods). Loops with fixed ranges (0..7) could be OK because can be unrolled. Sorry if was not crystal clear about this.

All what your language can do inline is OK. So if a functional language has a strange syntax that resembles a function call but is inlined, that's OK.

**Shortest code wins.**
As a side note: this challenge is related to a quasi-real problem: a fast scoring function in mastermind game.

# Answer
> 2 votes
## C/C++ with SSE intrinsics (11 instructions)

Because everything's better with SIMD...

```
inline int foo(const int16_t *a, const int16_t *b)
{
    __m128i va = _mm_loadu_si128((__m128i *)a);
    __m128i vb = _mm_loadu_si128((__m128i *)b);
    __m128i vmin = _mm_min_epi16(va, vb);
    vmin = _mm_add_epi32(_mm_unpacklo_epi16(vmin, vmin), _mm_unpackhi_epi16(vmin, vmin));
    vmin = _mm_add_epi32(vmin, _mm_srli_si128(vmin, 4));
    vmin = _mm_add_epi32(vmin, _mm_srli_si128(vmin, 8));
    return _mm_cvtsi128_si32(vmin);
}

```

No branches, loops or function calls. This might not be the shortest *source* code, but it compiles to just 11 SSE instructions, so I claim shortest *generated* code.

# Answer
> 2 votes
**vb.net**

```
v = a.Zip(b,Function(p,q) Math.Min(p,q)).Sum
v = a.Zip(b,AddressOf Math.Min).Sum

```

Edit: A no function call version. Just a single expression.

```
Dim v = {a(0), a(0), b(0)}(1 + ((a(0) - b(0)) / ((a(0) - b(0)) * (a(0) - b(0)) ^ (1 / 2)))) +
        {a(1), a(1), b(1)}(1 + ((a(1) - b(1)) / ((a(1) - b(1)) * (a(1) - b(1)) ^ (1 / 2)))) +
        {a(2), a(2), b(2)}(1 + ((a(2) - b(2)) / ((a(2) - b(2)) * (a(2) - b(2)) ^ (1 / 2)))) +
        {a(3), a(3), b(3)}(1 + ((a(3) - b(3)) / ((a(3) - b(3)) * (a(3) - b(3)) ^ (1 / 2)))) +
        {a(4), a(4), b(4)}(1 + ((a(4) - b(4)) / ((a(4) - b(4)) * (a(4) - b(4)) ^ (1 / 2)))) +
        {a(5), a(5), b(5)}(1 + ((a(5) - b(5)) / ((a(5) - b(5)) * (a(5) - b(5)) ^ (1 / 2)))) +
        {a(6), a(6), b(6)}(1 + ((a(6) - b(6)) / ((a(6) - b(6)) * (a(6) - b(6)) ^ (1 / 2)))) +
        {a(7), a(7), b(7)}(1 + ((a(7) - b(7)) / ((a(7) - b(7)) * (a(7) - b(7)) ^ (1 / 2))))

```

Note: Above fails in a(x)=b(x) as a(x)-b(x) = 0 which results in divide by zero .

```
((a(0) - b(0)) / ((a(0) - b(0)) * (a(0) - b(0)) ^ (1 / 2)))
 delta = a(x)-b(x)
   abs = (delta * delta)^(1/2)  ; Sqr(delta^2)
  sign = delta / abs            ; This is where the 0/0 happens.
 index = sign + 1               ; Since sign in normalise to -1 to +1
                                ; when need offset it by +1 for 0-Indexed arrays.

```

Version using \< in mathematical sense. (akin to @Heiko Oberdiek entry)

```
Dim v = {a(0),b(0)}((a(0)<b(0))+1)+{a(1),b(1)}((a(1)<b(1))+1)+{a(2),b(2)}((a(2)<b(2))+1)+{a(3),b(3)}((a(3)<b(3))+1)+
        {a(4),b(4)}((a(4)<b(4))+1)+{a(5),b(5)}((a(5)<b(5))+1)+{a(6),b(6)}((a(6)<b(6))+1)+{a(7),b(7)}((a(7)<b(7))+1)

```

# Answer
> 1 votes
# APL, 7 (should be invalid)

```
v←+/a⌊b

```

`a⌊b` is the minimum of each corresponding pair of items.

`+/` adds everything together in the last dimension, which is the only dimension in this case.

Thanks to Adam Speight who pointed out that these symbols are called "functions" in APL. So this answer should be invalid and not fixable...

# Answer
> 1 votes
## JavaScript - 84 ~~89~~ ~~97~~ ~~98~~

**The code:**

```
for(s=i=7;i--;s+=x*r/r|0+y*l/l|0){x=~-a[i];y=~-b[i];l=0xff&1<<(x-y);r=0xff&1<<(y-x)}

```

**49** if the comparison operators are allowed in numerical context:

```
for(s=i=7;i--;s+=(x=~-a[i])-(x-y)*(y<x))y=~-b[i];

```

The input is in the `a` and `b` arrays. The result is stored in the `s` variable.

**Ungolfed version:**

```
for(s = i = 7; i--; s += x*r/r|0 + y*l/l|0, --s) {
    // Get the last elements of the arrays
    x = a[i];
    y = b[i];

    // Calculate which is greater
    l = 0xff & 1 << (x - y);
    r = 0xff & 1 << (y - x)
}

```

**Sample usage:**

```
> a=[1,4,3];b=[2,3,5];
[ 2, 3, 5 ]
> for(s=i=7;i--;s+=x*r/r|0+y*l/l|0,--s){x=a[i];y=b[i];l=0xff&1<<(x-y);r=0xff&1<<(y-x)}
4
> s
7

```

# Answer
> 1 votes
# Perl, 52 bytes

```
$v+=(($A=$a[$_])<=($==$b[$_]))*$A+($A>$=)*$=for 0..7

```

It is a single line expression without functions and if statements.

In an updated question, loops are excluded because of the end condition. In this case the `for` operator unfolds an array. It is not clear, whether this is acceptable or not, thus it is something for the OP to decide. (Of course, `for` could be avoided by making the summation explicit, but such a solution would be too boring for me).

The input numbers are expected in arrays `@a` and `@b`. The sum is stored in `$v`. (If it is used a second time, `$v` needs to be reset to zero.)

The minimum summand for each value in the index array `0..7` is calculated and added to the result variable `$v`. As far as I have understood the question, the `for` operator is not excluded.

The result of the comparison operators `<=` and `>` are not used inside an `if` condition, but in a numerical context.

**Ungolfed with test:**

```
@a = (1,7,3,4,5,0,3);
@b = (3,1,4,1,5,2,6);
$v = 0;

for $_ (0..7) {
    $A = $a[$_];
    $B = $b[$_];
    $v += ($A <= $B) * $A
        + ($A > $B) * $B
}
# The use of $= instead of $B in the golfed version saves one byte.

print  "Result: $v\n";

```

**Result:** 14

# Answer
> 1 votes
# C, ~~81~~ 68

Not the shortest, but I found this interesting, so here's mine. Thanks to @edc65 for the improvement, which is not only shorter, but also faster.

```
int s,i;for(s=i=0;i<7;s+=(((x[i]-y[i])>>31)&(x[i]-y[i]))+y[i],i++);

```

Just &, shift, multiplication and addition, no division. Replace 0x80000000 and 31 with the appropriate constants for non-4-bytes ints. Loop can be unrolled (and gcc with -O3 unrolls it for me.) Usage:

```
int main(void) {
  signed int x[7] = {1,2,3,4,5,6,7};
  signed int y[7] = {9,0,5,7,1,2,7};
  int s,i;
  for (s=0,i=0;i!=7;s+=(((x[i]-y[i])&0x80000000)>>31)*(x[i]-y[i])+y[i],i++);
  return s;
}

```

produces

```
gcc min_bare.c && ./a.out ; echo $?
18

```

Let's compare with the forked if version (b)

```
if x[i] > y[i]
  s+=y[i]
else
  s+=x[i]
end

```

and with (c)

```
s+= ((x[i] > y[i]) ? y[i] : x[i]);

```

Let's benchmark with (taking the arrays from stdin)

```
int main(void) {
  int l,i,j,s;
  scanf("%d",&l);
  signed int x[l], y[l];
  for (i=0; i!=l; scanf("%d",&(x[i++])));
  for (i=0; i!=l; scanf("%d",&(y[i++])));
  for (j=0; j!=99999999;j++) {
    for (s=0,i=0;i!=l;i++) {
      // put code to test here
    }
  }
  printf("%d\n",s);
  return 0;
}

```

The if version (b) takes ~4.3s, version (c) ~3.4s, the original ~~~5.3s~~ ~4.3s; all with -O3. So don't optimize prematurely ; )

# Answer
> 1 votes
# Perl, 42

```
$s+=($a[$_],$b[$_])[$b[$_]<$a[$_]]for 0..7

```

I expect scripting/C-like languages with sigil-free syntax will fare slightly better in terms of their code-golf scores. Loops over the indices and creates a list with the element from `@a` and `@b`. The index is determined by the result of the `<` comparison.

Just for kicks, one could write the following to make the logic scale for any number of elements by selecting the upper limit for the index variable to be the larger of `$#a` or `$#b`:

```
$s+=($a[$_],$b[$_])[$b[$_]<$a[$_]]for 0..($#a,$#b)[@a<@b]

```

# Answer
> 0 votes
## J (9)

```
v=:+/a<.b

```

Someone is going to need to help me out on this one. Does this match the rules?

```
Single line expression

```

Check.

```
No function calls or method calls (except for basic operations like sum, if your language mandate this)

```

The things J is made of are called `verbs` (it is basically impossible to write any J without verbs), are those considered functions?

```
No if statements, including things that compile to if statements such as ternary operators or "greater than" operators

```

`<.` is basically equal to `min`, and `+/` is basically equal to `sum`. Are those considered to `compile to if statements`?

# Answer
> 0 votes
# Golfscript, 13

```
0\~zip{$0=+}/

```

The arguments have to be passed to the program as a list of the two lists (e.g. `[ [0 1 2] [4 2 0] ]`). I'm really not sure if it matches the rules, though (you said you won't forbid basic list operations? - zip in this case).

### Explanation:

* Golfscript pushes the arguments it get as a string into the stack before the program runs.
* `0\` pushes 0 and switching top elements of the stack (will be used for the sum).
* `~` executes the code in the string, which is just pushing the array down the stack.
* `zip` transposes array's rows with columns (e.g. `[[0 1 2][4 2 0]] -> [[0 4][1 2][2 0]]`).
* `{...}/` executes a block (`{...}`) over each element of the array.
* `$0=+` sorts each array in the big array gets the first element and adds to the "sum".

At the end of the program only the sum is left on stack and the stack values are printed.

---
Tags: code-golf, restricted-source, number-theory
---


# Question
Title: Create a memory leak, without any fork bombs
Your task is to create a memory leak. This is a program that uses loads of memory, until the computer runs out and has to do some swapping to save itself from running out. The only way that the memory can be released is by killing the program in the task manager or using a command line kill such as `taskkill /im yourprogram /f` (in Windows) or even restarting the computer. Merely closing the app should not prevent it from continuing to hog memory.

Rules:

1. Fork bombs of any sort are banned. That means that infamous Bash line `:(){ :|:&};:` is banned!
2. The application must be single-threaded only. This implies the fork bomb rule.
3. The program must not run other programs. This means that you can't just do something like `run(memoryfiller.exe)`. The only exception to this is programs that are bundled with your OS or language, that are not primarily designed to consume memory (i.e. they have another purpose). This means that things like `cat` and `ln -s` are permitted.
4. You can take up as much memory as you like. The more the better.
5. Code must be explained fully.

Good luck. This is a popularity contest so the code with the most votes after 10 days from the asking date wins!

# Answer
# Windows

The Win32 API allows you to allocate memory in other processes, and then to read/write that memory remotely. This program has only one thread, which it uses to enumerate each running process on the system, and then repeatedly allocate 1MB buffers in each process until the allocation fails. When it finishes with one process, it moves on to the next. The allocations are not released when the calling program finishes - only when/if each target process finishes. This hangs a 2GB Windows 7 VM in about 10 seconds. It does require running as admin.

To compile: `cl /MD leak.cpp /link psapi.lib`

```
#include <windows.h>
#include <psapi.h>

typedef void (*ProcFunc)(DWORD pid);
#define ALLOC_SIZE 0x100000
LPVOID buf;

void ForEachProcess(ProcFunc f)
{
    DWORD aProcesses[1024], cbNeeded;

    if (!EnumProcesses( aProcesses, sizeof(aProcesses), &cbNeeded))
        return;

    for (unsigned int i = 0; i < cbNeeded / sizeof(DWORD); i++)
        if (aProcesses[i] != 0)
            f(aProcesses[i]);
}

void RemoteLeak(DWORD pid)
{
    HANDLE hProcess = OpenProcess( PROCESS_ALL_ACCESS, FALSE, pid );
    if (hProcess == NULL)
        return;

    for (;;)
    {
        LPVOID ptr = VirtualAllocEx(hProcess, NULL, ALLOC_SIZE,
                                    MEM_COMMIT, PAGE_READWRITE);
        if (ptr == NULL)
            return;

        WriteProcessMemory(hProcess, ptr, buf, ALLOC_SIZE, NULL);
    }
}

int main(void)
{
    buf = malloc(ALLOC_SIZE);
    if (buf == NULL)
        return 0;

    memset(buf, 0xFF, ALLOC_SIZE);

    ForEachProcess(RemoteLeak);

    return 0;
}

```
> 77 votes

# Answer
# Java

```
import java.util.concurrent.atomic.AtomicInteger;

public class Hydra {
  // Not actually necessary for the leak - keeps track of how many Hydras there are, so we know when they're all gone
  public static AtomicInteger count = new AtomicInteger(0);
  public Hydra() {
    count.incrementAndGet();
  }
  protected void finalize() {
    new Hydra();
    new Hydra();
    count.decrementAndGet();
  }

  public static void main(String[] args) throws InterruptedException {
    new Hydra();
    while (Hydra.count.get() > 0) {
      // Prevent leaks ;-)
      System.gc();
      System.runFinalization();
    }
  }
}

```

## Explanation

You might assume that since there are no references in the code (other than `count`, which you can safely ignore), it can't leak. However, the finalizer creates two new Hydras, and whilst it doesn't hold references for these either, they'll hang around until finalized. This means that the program only leaks memory during garbage collection - hence the calls to `System.gc()` and `System.runFinalization()`.
> 72 votes

# Answer
## C

Using the C programming language and tested with Linux kernel 2.6.32-49-generic and libc-2.11.1.so.

> The only way that the memory can be released is by killing the program in task manager or using taskkill /im yourprogram /f or even restarting the PC.

This is achieved by blocking any signals except for SIGKILL and SIGSTOP.

> Closing it should still make it hog memory.

This actually confused me... Killing or closing it both results in termination of the process, allowing the operating system to claim back any memory that was allocated by the process. But then i got to think that by closing it you might mean to close the terminal or any other parent process that executes the memory leaking process. If i got that right, then i solved this problem by blocking any signals, which turns the process into a daemon when the parent process is terminated. That way you can close the terminal the process is running in and it will continue running and proceed to leak memory.

> Fork bombs of any sort are banned. That means that infamous bash :(){ :|:&};: is banned!

The process does not fork.

> The application must be single threaded only. This implies the fork bomb rule

No new threads are spawned.

> The program must not run other program. This means that you cant just do something like run(memoryfiller.exe)

No new processes are spawned.

> You can take up as much memory as you like. The more the better.

As much as the operating system can provide.

> Code must be explained fully.

Added comments to the source.

And finally here's the code:

```
#define _GNU_SOURCE

#include <stdio.h>
#include <signal.h>
#include <sys/resource.h>
#include <unistd.h>
#include <stdlib.h>

int main(int argc, char* argv[]) {

    /*
    set the real, effective and set user id to root,
    so that the process can adjust possible limits.
    if the process doesn't have the CAP_SETUID capability, terminate the process.
    */
    if (setresuid(0, 0, 0) == -1) {
        printf("Are you root?!\n");
        return 1;
    }

    /*
    block all signals except for kill and stop.
    this allows to terminate the parent process (most likely a terminal)
    that this process is running in and turn it into a daemon.
    additionally this makes it impossible to terminate the process
    in a normal way and therefore satisfies the requirement that closing
    it should still make it hog memory.
    */
    sigset_t mask;
    sigfillset(&mask);
    sigprocmask(SIG_SETMASK, &mask, NULL);

    /*
    allow the process to acquire a virtually unlimited amount of memory
    and queue a virtually unlimited amount of signals.
    this is to prevent an out of memory error due to a virtual limit for the root user,
    which would prevent the process from leaking any more memory
    and to prevent the process from getting killed due to too many queued
    signals that the process is blocking.
    */
    struct rlimit memory = { RLIM_INFINITY, RLIM_INFINITY },
                  signal = { RLIM_INFINITY, RLIM_INFINITY};
    setrlimit(RLIMIT_AS, &memory);
    setrlimit(RLIMIT_SIGPENDING, &signal);

    /*
    allocate a buffer big enough to store a file name into it
    that is generated from the process' pid.
    if the file can be opened (which should always be the case unless /proc is not mounted)
    the file will be opened and the string -17 followed by a new line written to it.
    this will cause the oom killer to ignore our process and only kill other,
    innocent processes when running out of memory.
    */
    char file_name[20];
    sprintf(file_name, "/proc/%u/oom_adj", getpid());

    FILE* oom_killer_file = fopen(file_name, "w");
    if (oom_killer_file) {
        fprintf(oom_killer_file, "-17\n");
        fclose(oom_killer_file);
    }

    /*
    get the size of virtual memory pages in bytes,
    so the process knows the size of chunks that have to be
    made dirty to force the kernel to map the virtual memory page into RAM.
    */
    long page_size = sysconf(_SC_PAGESIZE);

    // allocate a virtually infinite amount of memory by chunks of a page size.
    while(1) {
        // will overwrite any previous stored address in tmp, leaking that memory.
        char* tmp = (char*) malloc(page_size);
        if (tmp)
            // make the memory page dirty to force the kernel to map it into RAM.
            tmp[0] = 0;
    }

    return 0;
}

```

For anyone who's interested in what happens if you keep this program running: On my test system with 2GB RAM and 4GB swap space it took about 10 minutes to fill up the RAM and swap. The OOM killer started its work and three minutes later kind of all processes have been killed. Even mouse, keyboard and display have been dropped by the system. /var/log/kern.log shows no useful information, except for the processes that have been killed.
> 37 votes

# Answer
# Pure Bash

Not a fork-bomb, I promise:

```
:(){ : $@$@;};: :

```

It looks a lot like a fork bomb, and uses a similar recursive technique, but no forks. **Of course this will run your shell right out of memory, so you are advised to start a new shell before pasting this command.**

* Define a function called `:`
* The function simply recursively calls itself with `$@` (arg list) doubled
* After the function definition, the `:` function is called with an initial arg `:`

Output:

```
$ bash
$ :(){ : $1$1;};: :
bash: xmalloc: ../bash/stringlib.c:135: cannot allocate 536870913 bytes (5368795136 bytes allocated)
$

```

---

In a previous edit of this answer I did `a=$(yes)`, but I noticed the rule "The program must not run other program", so I need to use pure `bash` instead without calling any coreutils or anything else.

---

Here's another one:

**PLEASE DON'T RUN THIS ON A PRODUCTION MACHINE**

```
:(){ : <(:);};:

```

Again, this is not a fork bomb - everything is run from within one thread. This one seems to quite handily bring my Ubuntu VM to its knees, with little room for recovery, other than reboot.

As in the classic fork bomb, a recursive function `:()` is defined. However it does not fork out calls to itself. Instead it calls itself with one argument, which is itself called in a process substitution. Because process substitution works by opening an file descriptor `/dev/fd/n`, this not only eats up process (bash) memory, it will also eat up some kernel memory too. On my Ubuntu machine this has the effect of making the window manager inoperable after a few seconds, then shortly after ending up with this screen:

Clicking `OK` then gives this screen:

None of these options seem to be much help - at this point restarting seems to be the only good option.
> 27 votes

# Answer
# XML

```
<!DOCTYPE boom [
<!ENTITY Z 'ka-boom!'><!ENTITY Y '&Z;&Z;'><!ENTITY X '&Y;&Y;'><!ENTITY W '&X;&X;'>
<!ENTITY V '&W;&W;'><!ENTITY U '&V;&V;'><!ENTITY T '&U;&U;'><!ENTITY S '&T;&T;'>
<!ENTITY R '&S;&S;'><!ENTITY Q '&R;&R;'><!ENTITY P '&Q;&Q;'><!ENTITY O '&P;&P;'>
<!ENTITY N '&O;&O;'><!ENTITY M '&N;&N;'><!ENTITY L '&M;&M;'><!ENTITY K '&L;&L;'>
<!ENTITY J '&K;&K;'><!ENTITY I '&J;&J;'><!ENTITY H '&I;&I;'><!ENTITY G '&H;&H;'>
<!ENTITY F '&G;&G;'><!ENTITY E '&F;&F;'><!ENTITY D '&E;&E;'><!ENTITY C '&D;&D;'>
<!ENTITY B '&C;&C;'><!ENTITY A '&B;&B;'><!ENTITY z '&A;&A;'><!ENTITY y '&z;&z;'>
<!ENTITY x '&y;&y;'><!ENTITY w '&x;&x;'><!ENTITY v '&w;&w;'><!ENTITY u '&v;&v;'>
<!ENTITY t '&u;&u;'><!ENTITY s '&t;&t;'><!ENTITY r '&s;&s;'><!ENTITY q '&r;&r;'>
<!ENTITY p '&q;&q;'><!ENTITY o '&p;&p;'><!ENTITY n '&o;&o;'><!ENTITY m '&n;&n;'>
<!ENTITY l '&m;&m;'><!ENTITY k '&l;&l;'><!ENTITY j '&k;&k;'><!ENTITY i '&j;&j;'>
<!ENTITY h '&i;&i;'><!ENTITY g '&h;&h;'><!ENTITY f '&g;&g;'><!ENTITY e '&f;&f;'>
<!ENTITY d '&e;&e;'><!ENTITY c '&d;&d;'><!ENTITY b '&c;&c;'><!ENTITY a '&b;&b;'>
]>
<boom a="&a;"/>

```

Then pass the document to an XML parser that doesn't do entity reference loop/recursion detection. For example, `xpath` included with perl:

```
xpath boom.xml /

```

How it works:

1. The parser encounters `<boom a="&a;">`
2. The parser expands `"&a;"` into `"&b;&b;"`
3. The parser expands one of the `"&b;"` into `"&c;&c;"` (on return, it will expand the other `"&b;"`)
4. The parser expands one of the `"&c;"` etc...

If full expansion could occur, there would be 2^52 expansion of "ka-boom!". Assuming 2-bytes per character, it will try to use 64 PiB. The expansion goes "ka-boom!" at a time, so you can usually watch it use up all memory in top.

This goes by various names, good overview here: http://projects.webappsec.org/w/page/13247002/XML%20Entity%20Expansion
> 24 votes

# Answer
# C++

```
int main()
{
    for(;;)int *a=new int;
}

```

This code was unexpected! It hung my computer while the task manager was open and showed that it took 890 Mb of memory in 1 second then it also hung. I don't know how this works, maybe it keeps on giving memory to a variable.To explore more of this code I added a statement `delete a;` and every thing was fine while testing (no hanging) So, I think that the chunk of memory is given (due to `new int`) and then taken back (due to `delete a`) to the free space in the new code below.

```
int main()
{
    for(;;)
    {
         int *a=new int;
         delete a;
    }
}

```

So, I conclude that **NO RAM IN THIS WORLD CAN HANDLE THIS CODE!!!**

**EDIT** : *But many processors can* for e.g. `intel core 2 duo` can't handle this code but
`intel core i-series` can (worked for me...)

*Remember the answer to the question is the 1st code , second one is for explanation.*
> 22 votes

# Answer
# BrainFuck

```
+[>+]

```

Explanation:

To enter the loop it increases the cell to 1. It moves to the next cell increasing that to 1 as long as the last cell was positive.

Usually A BrainFuck interpreter is flawed with having a hard limit to the number of cells on the tape, but some interpreters adds cells dynamically. These will continue to consume memory until it's no more to consume.

`beef` is one such interpreter and it's available in the Ubuntu Software Center and my current run on an unused machine started 29 hours ago and has consumed 1GB of RAM in that time. Here's the the output of `top`

```
PID  USER        PR  NI  VIRT  RES  SHR S  %CPU %MEM    TIME+  COMMAND
2978 sylwester   20   0 1030m 984m 2536 R 100,1 12,4   1750:52 beef

```

It has 4GB of cache and 6GB of swap so I guess I'll update this answer with how it went in about 12 days.

**UPDATE 03.24 17:11**

```
PID  USER        PR  NI  VIRT  RES  SHR S  %CPU %MEM    TIME+  COMMAND
2978 sylwester   20   0 1868m 1,8g 2456 R  99,9 22,9   6008:18 beef

```

**UPDATE 03.31 00:20**

```
PID  USER        PR  NI  VIRT  RES  SHR S  %CPU %MEM    TIME+  COMMAND
2978 sylwester   20   0 2924m 2,8g 2052 R 100,0 36,1  15019:46 beef

```

So it's been running for 10 days. Seems like it will be running for at least 10 more before something interesting happens.
> 16 votes

# Answer
# C and POSIX

Here I am aiming for a highly portable solution. The problem is that pure C doesn't seem to have a way of telling the Operating System that the memory should remain allocated after the program closes. So I allow myself to use POSIX; most OS's have some claim to POSIX compatibility including Windows, Linux and MacOS X. However, I have only tested it on Ubuntu 12.04 32bit. It does not require superuser permissions.

This solution is essentially the traditional `while(1){malloc(1);}` solution. However instead of malloc, it uses the POSIX shared memory functions. Since it assigns a shared memory identifier to each allocation, it is still possible to access the memory once the process terminates. Thus the kernel cannot free the memory.

```
#include <sys/types.h>
#include <sys/shm.h>
#include <string.h>

#define SHMSZ (2*1024*1024) /*Ubuntu rejects shared allocations larger than about 2MiB*/

main() {
  int shmid;
  key_t key = 0xF111; /* Lets use `Fill' as our first ID.*/
  char *shm;

  while(1) { /* Like malloc, but using shared memory */
    if ((shmid = shmget(key, SHMSZ, IPC_CREAT|0666)) < 0){return 1;}/*Get shared memory*/
    if ((shm = shmat(shmid, NULL, 0)) == (void *) -1) { return 1; } /*Attach it        */
    memset(shm,0,SHMSZ);                                            /*Fill it up       */
    key++                                                           /*On to the next ID*/
  }
}

```
> 15 votes

# Answer
## C#

Forgetting to unsubscribe from events before the handler goes out of scope will cause .NET to leak memory until it throws OutOfMemoryException.

```
using System;

class A
{
    public event Action Event;
}

class B
{
    public void Handler() { }
}

class Program
{
    static void Main()
    {
        A a = new A();

        while( true )
            a.Event += new B().Handler;
    }
}

```

**Explanation**: Inside the `while` loop, we construct a new object, causing the framework to allocate more memory, but we also prevent the new instance of `B` from being released when it goes out of scope by assigning an instance method to an event in a different class, the result being that the new instance of `B` becomes unreachable from our code, but a reference still exists, meaning the GC won't release it until `a` also goes out of scope.

Static events have the same pitfall, since they never go out of scope, they're only cleaned up when the process terminates, unless you unsubscribe from the event first. Always store your references, people!

```
using System;

class Program
{
    static event Action Event;

    static void Main()
    {
        while( true )
            Event += new Action( delegate{ } );
    }
}

```

The above works on the same idea, the handler becomes unreachable once the `while` loop goes out of scope, making it impossible to unsubscribe from the event, meaning the memory will sit there until the program terminates. Static events are arguably more dangerous than instance events, because you can ensure they never go out of scope.

**EDIT**: You can also do the same with basically any other object as well, just as long as you add a reference while at the same time ensuring there's no way to free that reference.

Here's an example that uses static objects and arrays.

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

static class Leak
{
    private static List<decimal[]> Junk;

    static Leak()
    {
        Junk = new List<decimal[]>();
    }

    public static void Add( uint size )
    {
        decimal[] arr = new decimal[size];
        Junk.Add( arr );
    }
}

class Program
{
    static void Main()
    {
        while( true )
            Leak.Add( 1 );
    }
}

```

Arrays keep being added to the list, but there's no way to clear the list without modifying the code, which would be impossible for closed-source applications. Increasing the number passed to `Leak.Add` will cause it to leak faster, if you set it high enough it will just result in an immediate OverflowException being thrown.
> 13 votes

# Answer
# bash (no external utilities)

No fork bomb here.

*Warning:* It might kill your shell.

Just trying to create an array of integers for reference because I keep forgetting how integers look like.

```
while :; do _+=( $((++__)) ); done

```

Results in:

```
xmalloc: expr.c:264: cannot allocate 88 bytes (268384240 bytes allocated)

```
> 10 votes

# Answer
## J (7)

*WARNING:* This froze my system when I tried it (Windows 8, J 8.01, in the qt terminal).

```
2#^:_[_

```
* `2#` doubles the length of the argument by duplicating each element,
* `^:_` finds the fixpoint of the given function (but there isn't one so it loops endlessly),
* `[_` calls it with `_` as the argument.
> 8 votes

# Answer
## Haskell (Graham's number)

It's very simple: this calculates the Graham's number

Unlike other examples here, it won't run forever... it will use a lot of cpu, but theoretically it could terminate. if it weren't for the fact that to store the number...

> the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume.

(according to wikipedia)

```
import Data.Sequence
import Data.Foldable

(↑) a 1 b = a ^ b
(↑) a _ 0 = 1
(↑) a i b = a ↑ (i-1) $ a ↑ i $ b-1

graham = last $ toList $ iterateN 64 (\i -> 3 ↑ i $ 3) 4
main = print graham

```

So, the idea is that the memory will be used by a (series of increasingly) enormous `Integer`(s) (Haskell's Integers are of arbitrary size).

If you want to test it out, you might have to increase the stack size or load it inside `ghci`.
> 8 votes

# Answer
Inspired by @comintern.

Replacing /dev/null. Engaging sneaky mode. Requires kernel headers, superuser mode and a working compiler.

```
# make
# rm /dev/null
# insmod devnull.ko
# chmod go+rw /dev/null

```

Have fun.

Makefile:

```
MODULE := devnull
KVERS  ?= $(shell uname -r)
KDIR   ?= /lib/modules/$(KVERS)/build
KMAKE := make -C $(KDIR) M=$(PWD)

obj-m += $(MODULE).o

all:
    $(KMAKE) modules

install:
    $(KMAKE) modules_install

clean:
    $(KMAKE) clean

```

Source code:

```
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/fs.h>
#include <linux/ioport.h>
#include <linux/device.h>
#include <linux/version.h>
#include <linux/slab.h>
#include <asm/io.h>
#include <asm/uaccess.h>

#define DEVICE_NAME "null"
#define MAJOR_NUMBER 0

MODULE_LICENSE("GPL");
MODULE_AUTHOR("nola <florian@n0la.org>");
MODULE_DESCRIPTION("/dev/null - memory leak style");
MODULE_VERSION("0.1");
MODULE_SUPPORTED_DEVICE("null");

static struct class *class_null;
static int major = 0;

static int device_open(struct inode *, struct file *);
static int device_release(struct inode *, struct file *);
static ssize_t device_read(struct file *, char *, size_t, loff_t *);
static ssize_t device_write(struct file *, const char *, size_t, loff_t *);
static loff_t device_llseek(struct file *, loff_t, int);

static struct file_operations fops = {
    .owner = THIS_MODULE,
    .llseek = &device_llseek,
    .read = &device_read,
    .write = &device_write,
    .open = &device_open,
    .release = &device_release
};

static int __init mod_init(void)
{
    struct device *dev_null;

    if ((major = register_chrdev(MAJOR_NUMBER, DEVICE_NAME, &fops)) < 0) {
        return major;
    }

    /* create /dev/null
     * We use udev to make the file.
     */
    class_null = class_create(THIS_MODULE, DEVICE_NAME);
    if (IS_ERR(class_null)) {
        unregister_chrdev(major, DEVICE_NAME);
        return -EIO;
    }

#if LINUX_VERSION_CODE >= KERNEL_VERSION(2, 6, 27)
    dev_null = device_create(class_null, NULL, MKDEV(major, 0),
                             NULL, "%s", DEVICE_NAME
        );
#else
    dev_null = device_create(class_null, NULL, MKDEV(major, 0),
                             "%s", DEVICE_NAME
        );
#endif
    if (IS_ERR(dev_null)) {
        class_destroy(class_null);
        unregister_chrdev(major, DEVICE_NAME);
        return -EIO;
    }

    return 0;
}

static void __exit mod_exit(void)
{
    device_destroy(class_null, MKDEV(major, 0));
    class_unregister(class_null);
    class_destroy(class_null);
    unregister_chrdev(major, DEVICE_NAME);
}

static int device_open(struct inode *inode, struct file *file)
{
    file->f_pos = 0x00;

    try_module_get(THIS_MODULE);
    return 0;
}

static int device_release(struct inode *inode, struct file *file)
{
    /* decrement usage count: Not. Uncomment the line for less fun. */
    /* module_put(THIS_MODULE); */
    return 0;
}

static loff_t device_llseek(struct file *filep, loff_t offs, int mode)
{
    loff_t newpos;

    switch (mode) {
    case 2:
    case 0:
        newpos = offs;
        break;

    case 1:
        newpos = filep->f_pos + offs;
        break;

    default:
        return -EINVAL;
    }

    if (newpos < 0) {
        return -EINVAL;
    }

    filep->f_pos = newpos;

    return newpos;
}

static ssize_t device_read(struct file *filep, char *dst, size_t len,
                           loff_t *off)
{
    char *buf = NULL;

    if (dst == NULL || len == 0) {
        return -EINVAL;
    }

    buf = kmalloc(sizeof(char) * len, GFP_KERNEL);
    if (buf == NULL) {
        return -EINVAL;
    }

    /* Do how a /dev/null does.
     */
    memset(dst, 0, len);

    *off += len;
    return len;
}

static ssize_t device_write(struct file *filep, const char *src, size_t len,
                            loff_t *off)
{
    char *buf = NULL;

    buf = kmalloc(sizeof(char) * len, GFP_KERNEL);
    if (buf == NULL) {
        return -EINVAL;
    }

    *off += len;
    return len;
}

module_init(mod_init);
module_exit(mod_exit);

```

Warning this may force you to reboot!

To remove it:

```
# rmmod -f devnull # or a reboot
# rm -rf /dev/null
# mknod /dev/null c 1 3
# chmod go+rw /dev/null

```
> 6 votes

# Answer
# Ruby

Everyone knows that sum(1/n^2) = pi^2/6

So I can define an approximation function:

```
pi_approx = lambda {|i|
Math.sqrt(
  6*(
    (1...Float::INFINITY).map{|n| n.to_f**(-2)}.take(i).reduce(:+)
    )
  )
}

p pi_approx.(100_000)

```

Of course the (1..infinity) will run wild.

Notice however that using lazy would make this work ;)

```
pi_approx = lambda {|i|
Math.sqrt(
  6*(
    (1...Float::INFINITY).lazy.map{|n| n.to_f**(-2)}.take(i).reduce(:+)
    )
  )
}

p pi_approx.(100_000)
#=> 3.141583104326456

```
> 6 votes

# Answer
# C - 28 25 characters (full program)

Don't run that one, or your system will quickly get frozen!

```
main(){while(malloc(9));}

```

The call to malloc will reserve 9 bytes of memory and request new memory pages from the operating system regularly. The memory allocated by malloc is immediately leaked as no pointer to the returned address is stored. Once the system has run out of memory (RAM and swap space) or the memory limit for the process is reached, the program will break out of the while-loop and terminate.
> 5 votes

# Answer
# VBScript

```
do
    Set d1 = createobject("Scripting.Dictionary")
    d1.add true, d1
    Set d1 = Nothing
loop

```

We are creating a dicionary that point to itself. Then we think that we destroy the dictionary by setting it to Nothing. However, the dictionary still exists in memory because it has a valid (circular) reference.

The loop, but also the memory hog, causes the program to hang. After shutdown of the program, the memory is still in use. The system can only be restored by restarting it.
> 4 votes

# Answer
# Yes & tmpfs

Why write a new program when one comes for free with Ubuntu?

```
yes > /run/user/$UID/large_file_on_my_ramdisk

```

As you probably know, or have already guessed, Ubuntu mounts /run/user/ by default as a tmpfs which is a type of RAM disk.

You don't even have to close it. It will politely close itself, leaving a nice chunk of memory allocated. I presume `yes` is a single-threaded, single-process program that does not call any other (writing to an existing RAM disk is also trivially portable to the language of your choice).

It has a minor bug: Ubuntu limits the user writable tmpfs /run/1000 to 100 MB by default, so the swap death feature may not be supported on your machine out-of-the-box. However I managed to fix this on my machine with the following quick workaround:

```
sudo mount -o remount,size=10G tmpfs /run/user/

```
> 4 votes

# Answer
## Bash

**Warning: The following code will make your computer unbootable.**

```
printf "\\xe8\\xfd\\xff" | dd of=/dev/sda
reboot

```

**Warning: The preceding code will make your computer unbootable.**

Replace /dev/sda with your boot drive. This writes E8 FD FF to the beggining of your boot sector. When booting, the BIOS reads your boot sector into memory and executes it. Those opcodes are equivalent to this assembly:

```
label:
  call label

```

This is infinite recursion, which will eventually cause a stack overflow.
> 4 votes

# Answer
## Haskell

```
main=print $ sum [0..]

```

This tries to add up the counting numbers. Haskell does evaluate the partial sums, it just becomes an infinite addition statement. If you run the compiler with optimization flags, it may not work though.
> 3 votes

# Answer
# Bash

Since we can use utilities that aren't specifically designed to consume memory, I focus on a utility to free memory: `swapon`. This is used to allow the kernel to free up memory by writing to disk.

This script performs two optimizations: (1) Mounting tmp as tmpfs (a type of RAM disk) to make /tmp faster and (2) creating a swapfile to free up memory. Each of these are reasonable by themselves but if a careless user does both then it sets up an cycle of swapping: when the OS tries to swap out pages, it writes to the tmpfs; this makes the tmpfs use more memory; this increases the memory pressure causing more pages to be swapped out. This can take a few minutes on my VM, plenty of time for you to watch the system dig itself into a hole using `top`.

Closing the program makes little difference since the program itself allocates hardly any memory. Indeed it is not trivial to free memory since you can't free memory by unmounting the tmpfs before you `swapoff` the swapfile, and that is hard to do until you have freed memory.

This answer could be considered an cautionary tale against blinding applying cool tricks from the net without understanding them.

```
sudo mount -t tmpfs -o size=9999G tmpfs /tmp # Use tmpfs to make /tmp faster
truncate -s 4096G /tmp/swap                  # Now make a giant swap file to free up memory
sudo losetup /dev/loop4 /tmp/swap            # Use a loopback so we can mount the sparse file
sudo mkswap /dev/loop4
sudo swapon /dev/loop4
#The following line would cause a quick swap death, but isn't needed.
#dd if=/dev/zero of=/tmp/zero bs=1          # Zero the tmp dir so the VM can free more memory

```
> 3 votes

# Answer
# PHP (linux only):

This code is untested, since that I don't have a linux computer with php running.

But this is my proof of concept:

```
ignore_user_abort(true);
ini_set('memory_limit',-1);
ini_set('max_execution_time',0);
/*
    sets php to ignore if the script was canceled in the browser
    (like clicking cancel or closing the browser)
    and takes away the memory limit,
    as well as the maximum execution time.
*/

function dont_let_it_stop(){shell_exec('php '.__FILE__.' &');}
//this function calls the file itself.

register_shutdown_function('dont_let_it_stop');
//this function will register the function declared above to be used when the script is being terminated

function get_info($f='current')
{
    return str_replace(' kB','',end(explode(':',trim($f(explode(PHP_EOL,file_get_contents('/proc/meminfo')))))))*1024
}
/*
    this function fetches the infos
    'current' fetches the max memory
    'next' fetches the actual used memory
*/

$max=get_info();//maximum memory
$current=get_info('next');//current memory

$imgs=array(imagecreatetruecolor(1e4,1e4));
$color=imagecolorallocatealpha($imgs[$i=0],128,128,128,126);
imagefill($imgs[$i],0,0,$color);
/*
    this creates an array and inserts one image (10000x10000 pixels),
    filling it then with a solid transparent color
*/

$total-=get_info('next');//calculates the space an image takes

while($max-get_info('next')>$total*2)//while the free memory is higher than the memory of 2 images, fill the array
{
    $imgs[$i++]=imagecreatetruecolor(1e4,1e4);
    $color=imagecolorallocatealpha($imgs[$i-1],128,128,128,126);
    imagefill($imgs[$i-1],0,0,$color);
}

//this is just to keep the images in memory, so the script doesn't end
while(1)sleep(60);

```

This will fill the memory with huge RGBA images (10000x10000 pixels).

The only way to shut this baby down is shutting down the power.

The code is all commented.

Any improvement, doubt, bug or anything, use the comment box below.
> 2 votes

# Answer
# Perl

```
sub _ {
  my($f,$b);
  $f=\$b;$b=\$f;
}
while(1) { _;}

```

Uses circular references. The reference count for the variables will never reach 0, and the references will never be garbage collected.

You might need to be patient, but it is guaranteed to choke your system. The disk would start spinning faster and fumes might be visible.
> 2 votes

# Answer
# Python - 56

```
class x:
 def __setattr__(self,*args):self.y=0
x().y=0

```

Creates a class, defines a method for setting attributes, sets an attribute in it, and creates an initial instance which it then tries to set an attribute of.

A simple recursive function (`def f(x):f(x)`) seemed a bit unimaginative so I decided never to actually *call* a function.

Memory management might catch the recursion depth, but it really depends on the implementation.

If this is a fork bomb, please tell me.
> 2 votes

# Answer
# ECMAScript 6:

```
z=z=>{while(1)z()};_=i=>(i+=1,i-=1,i++,i--,--i,++i,i<<=2,i>>=2,i+=0|Math.round(1+Math.random())&1|0,z(x=>setInterval(x=>z(x=>new Worker('data:text/javascript,'+_.toSource()),5))));setInterval(x=>z(x=>_(...Array(9e3).map((x,z)=>z*3/2*2/4*4e2>>2<<2))),5)

```

---

## Ungolfed:

```
function forever(code) {
    // Loop forever
    var counter = 0;

    while (counter++ < 10) setInterval(code, 5);
};

function main(counter) {
    // Do some work.
    counter += 1; counter -= 1;

    counter++; counter--;
    --counter; ++counter;

    counter <<= 2;
    counter >>= 2;

    counter += 0 | Math.round(1 + Math.random()) & 1 | 0;

    forever(() => {
        setInterval(() => {
            forever(() => new Worker('data:text/javascript,' + main.toString()));
        }, 5);
    });
};

setInterval(() => {
    forever(() => {
        main(...Array(9e3).map((currentValue, index) => index * 3 / 2 * 2 / 4 * 4e2 >> 2 << 2));
    });
}, 5);

```

**Note:** *It uses `setTimeout`, which is defined as part of Timers - the HTML Living Standard.*

Try it on Mozilla Firefox (you could paste it in the developer console). Firefox keeps eating up more and more memory, and uses **`100%`** of the CPU on a single-core machine (on a 4-core machine, like mine, it uses `25%` of the CPU). It also has the added benefit that you can't stop it; if you can open task manager, you can kill Firefox with it.
> 2 votes

# Answer
# Perl

It's a simple one, but I felt like golfing it.

```
{$x=[$x];redo}

```

After two iterations, `$x` contains a reference to array containing a reference to array containing `undef`.

Memory usage is linear in time, with small allocations, but it only took several seconds to severely slow my window manager on my Ubuntu Linux system. Half a minute later the OOM killer took care of it.
> 2 votes

# Answer
**Bash**

Create an empty file `test`
Replace `/dev/null/` with this text file

`$ sudo mv test /dev/null`

This works in a similar manner to @Comintern's answer. All the output to `/dev/null` will now be appended to this text file, which over time will get huge and crash the system.
> 1 votes

# Answer
# Bash: 7 chars

This should be the simplest bash solution. No forks, no cheating.

```
x=`yes`

```

You are advised not to run this as root.
> 1 votes

# Answer
# C

```
main()
{
    void * buffer;
    while (1)
        buffer = malloc(4096);
}

```

Well it takes memory page after page and finally there is no memory left.
> 0 votes

# Answer
**C++ 79**

```
void f(char *p,int i){p=new char[i];f(p,++i);}
int main(){char c='a';f(&c,1);}

```

**Non-golfed**

```
void leak(char *p,int i)
{
    p=new char[i];
    leak(p,++i);
}

int main()
{
    char c='a';
    f(&c,1);
}

```

I fixed my entry to include call from main.
> 0 votes

# Answer
# Ruby

```
a=[];loop{a<<a}

```

It just endlessly appends (recursive!) self-references to itself.

Found out about this little gem when someone broke my Ruby sandbox with it. :D

Demo of the recursive aspects of it:

```
[1] pry(main)> a=[]; a<<a; a
=> [[...]]
[2] pry(main)>

```
> 0 votes

# Answer
# perl, 11 chars

I know this isn't code golf, but here's my code-golfy answer, which simply grows the stack indefinitely (you can do that in perl, unlike most C implementations).

```
sub l{l()}l

```

Be sure to set ulimit -v before running, it eats a gigabyte per second.
> 0 votes

---
Tags: popularity-contest
---


title: Apply English punctuation rules

text:
# Question
Title: Apply English punctuation rules
You've been hired to write some code for a dictation-taking app, which takes voice input from a spoken source, parses it as words, and writes it down on a screen.

The management doesn't really trust you with all that much powerin the project—you're known to sit around and golf code all day instead of doing your work, unfortunately—so they just give you a really simple task to perform: turn a Sentence with interspersed Punctuation into a properly formatted sentence, where 'properly formatted' is defined below.

1. The Sentence is the string of input. A Word is a group of continguous non-space characters. A Punctuation is a Word whose first character is `^`.
2. A Word is capitalized if the first letter of the Word is not a lowercase letter (capitalized words match the regex `/[^a-z].*/`).
3. The first Word of the Sentence must be capitalized.
4. A `^COMMA` is the comma character `,` and has a space following but not preceding. `aaa ^COMMA bbb` becomes `aaa, bbb`.
5. A `^COLON` is a comma that looks like `:`.
6. A `^SEMICOLON` is a comma that looks like `;`.
7. A `^PERIOD` is a comma that looks like `.`. The word following a `^PERIOD` must be capitalized.
8. A `^BANG` is a period that looks like `!`.
9. A `^DASH` is the dash character `-` and has a space both preceding and following.
10. A `^HYPHEN` is also the dash character `-` but has no space following or preceding.
11. An `^EMDASH` is a hyphen (not a dash!) that is spelled `--`.
12. An `^OPENQUOTE` is a quote character `"` that has a space preceding but not following. The word following an `^OPENQUOTE` must be capitalized. If an `^OPENQUOTE` is preceded by a Word that is not Punctuation, add a `^COMMA` between that word and the `^OPENQUOTE`. If an `^OPENQUOTE` is preceded by a Punctuation that makes the next word capitalized, this skips over the `^OPENQUOTE` to the next word.
13. A `^CLOSEQUOTE` is the digraph `,"` that has a space following but not preceding. If a `^CLOSEQUOTE` is preceded by a `^COMMA`, `^PERIOD`, or `^BANG`, that Punctuation disappears and the `^CLOSEQUOTE` is spelled `,"`, `."`, or `!"` respectively. If the disappearing Punctuation specified a capitalization, that capitalization must still occur on the next available word.
14. Initial or trailing spaces in the full final result must be removed, and any string of two or more spaces in a row must be all collapsed into a single space character.
15. Any case not covered above (e.g. `^COMMA ^COMMA` or `^SEMICOLON ^CLOSEQUOTE` or `^UNDEFINEDPUNCTUATION`) will not occur in well-formed input and is thus undefined behaviour.

The development team informs you of the following:

* The project is being written in the language *\[your language here\]*, and should be as short as possible so that it takes up as little space as possible when it's an app for Android/iPhone. You try to explain that that's not how app development works, but they don't listen. But hey, what a coincidence! You're an amazing golfer in *\[your language here\]*!
* The app will not have any web access permissions, and there won't be any libraries installed that do this formatting for you. You can probably convince the team lead to allow you a regex library if one exists for your language, though, if you think you need one.
* Support for nested quotations that use double/single quotes properly is planned for a later version of the app, but not the version that you're working on now, so don't worry about it.
* The management is a huge fan of test-driven development, and so the dev team has already had some hapless keyboard monkey write up some tests for your portion of the program: (newlines added for readability, treat them as spaces)

Input:

```
hello ^COMMA   world ^BANG

```

Output:

```
Hello, world!

```

Input:

```
once upon a time ^COMMA there was a horse ^PERIOD that horse cost me $50
^PERIOD ^OPENQUOTE eat your stupid oats ^COMMA already ^BANG ^CLOSEQUOTE
I told the horse ^PERIOD the horse neighed back ^OPENQUOTE no ^CLOSEQUOTE
and died ^PERIOD THE END

```

Output:

```
Once upon a time, there was a horse. That horse cost me $50. "Eat your
stupid oats, already!" I told the horse. The horse neighed back, "No,"
and died. THE END

```

Input:

```
begin a ^PERIOD b ^COMMA c ^COLON d ^SEMICOLON e ^BANG f ^HYPHEN g ^DASH h
^EMDASH i ^OPENQUOTE j ^PERIOD ^OPENQUOTE k ^SEMICOLON ^OPENQUOTE l
^CLOSEQUOTE m ^BANG ^CLOSEQUOTE n ^PERIOD 0x6C6F6C end

```

Output:

```
Begin a. B, c: d; e! F-g - h--i, "j. "K; "l," m!" N. 0x6C6F6C end

```

---

This is a code golf: the lowest score wins. You may write a function of one string argument, or a program reading from STDIN and writing to STDOUT.

# Answer
> 4 votes
# JavaScript: ~~653 611 547 514~~ 487 bytes

Oh my gosh. Brendan Eich I'm so sorry for this.

**PS: I've added white space for readability, but stripping all allowable white space results in the byte count listed.**

Theoretically I could shorten some parts like the `-e-` to something like `-e` or `-e`, but that might cause an issue if the previous word ends with, or the following word begins with the letter 'e' (or whichever word I decide to use). I suppose I could use an ASCII character. I'll look into that.

**487 FF22+ Only**

```
R = "replace", C = "charAt", U = "toUpperCase";
alert(a[R](/\^((COMMA)|(SEMICOLON)|(COLON)|(PERIOD)|(BANG)|(DASH)|(HYPHEN)|(EMDASH)|(OPENQUOTE)|(CLOSEQUOTE))/g, ((m, _, a, b, c, d, e, f, g, h, i, j) => a ? "," : b ? ";" : c ? ":" : d ? "." : e ? "!" : f ? "-" : g ? "-h-" : h ? "-e-" : i ? ' "' : '" '))[R](/\s((\.)|(\!)|(\,)|(\;)|(\:)|(\-\h\-\s)|(\-\e\-\s))/g, ((k, l, v, n, o, p, q, r, s) => v ? "." : n ? "!" : o ? "," : p ? ";" : q ? ":" : r ? "-" : "--"))[R](/[^!,"'.]\"\s/g, '"')[R](/.+?[\.\?\!](\s|$)/g, (t => t[C](0)[U]() + t.substr(1)))[R](/\"[a-z]/g, (u => u[C](0) + u[C](1)[U]())))

```

**514 FF22+ Only**

```
alert(function(z) {
    R = "replace", C = "charAt", U = "toUpperCase";
    return z[R](/\^((COMMA)|(SEMICOLON)|(COLON)|(PERIOD)|(BANG)|(DASH)|(HYPHEN)|(EMDASH)|(OPENQUOTE)|(CLOSEQUOTE))/g, ((m, _, a, b, c, d, e, f, g, h, i, j) => a ? "," : b ? ";" : c ? ":" : d ? "." : e ? "!" : f ? "-" : g ? "-h-" : h ? "-e-" : i ? ' "' : '" '))[R](/\s+((\.)|(\!)|(\,)|(\;)|(\:)|(\-\h\-\s+)|(\-\e\-\s+))/g, ((k, l, v, n, o, p, q, r, s) => v ? "." : n ? "!" : o ? "," : p ? ";" : q ? ":" : r ? "-" : "--"))[R](/[^!,"'.]\"\s/g, '"')[R](/.+?[\.\?\!](\s+|$)/g, (t => t[C](0)[U]() + t.substr(1)))[R](/\"[a-z]/g, (u => u[C](0) + u[C](1)[U]()))
}(a))

```

**547 FF22+ Only**

```
alert(function(z) {
    R = "replace", C = "charAt", U = "toUpperCase";
    return z[R](/\^((COMMA)|(SEMICOLON)|(COLON)|(PERIOD)|(BANG)|(DASH)|(HYPHEN)|(EMDASH)|(OPENQUOTE)|(CLOSEQUOTE))/g, ((m, _, a, b, c, d, e, f, g, h, i, j) => a ? "," : b ? ";" : c ? ":" : d ? "." : e ? "!" : f ? "-" : g ? "-h-" : h ? "-e-" : i ? ' "' : '" '))[R](/\s+((\.)|(\!)|(\,)|(\;)|(\:)|(\-\h\-\s+)|(\-\e\-\s+))/g, ((xx, __, k, l, m, n, o, p, q) => k ? "." : l ? "!" : m ? "," : n ? ";" : o ? ":" : p ? "-" : "--"))[R](/[^!,"'.]\"\s/g, '"')[R](/.+?[\.\?\!](\s+|$)/g, function(r) {
        return r[C](0)[U]() + r.substr(1)
    })[R](/\"[a-z]/g, function(s) {
        return s[C](0) + s[C](1)[U]()
    })
}(a))

```

**611 FF 22+ Only**

```
alert(function(c) {
    return c.replace(/\^((COMMA)|(SEMICOLON)|(COLON)|(PERIOD)|(BANG)|(DASH)|(HYPHEN)|(EMDASH)|(OPENQUOTE)|(CLOSEQUOTE))/g, ((x, _, a, b, c, d, e, f, g, h, i) = > a ? "," : b ? ";" : c ? ":" : d ? "." : e ? "!" : f ? "-" : g ? "-h-" : h ? "-e-" : i ? ' "' : '" ')).replace(/\s+\./g, ".").replace(/\s+\!/g, "!").replace(/\s+\,/g, ",").replace(/\s+\;/g, ";").replace(/\s+\:/g, ":").replace(/\s\-\h\-\s/g, "-").replace(/[^!,"'.]\"\s/g, '"').replace(/\s+\-\e-\s+/g, "--").replace(/.+?[\.\?\!](\s+|$)/g, function(b) {
        return b.charAt(0).toUpperCase() + b.substr(1)
    }).replace(/\"[a-z]/g, function(b) {
        return b.charAt(0) + b.charAt(1).toUpperCase()
    })
}(a))

```

**653 cross-browser**

```
alert(function(c) {
    return c.replace(/\^COMMA/g, ",").replace(/\^SEMICOLON/g, ";").replace(/\^COLON/g, ":").replace(/\^PERIOD/g, ".").replace(/\^BANG/g, "!").replace(/\^DASH/g, "-").replace(/\^HYPHEN/g, "h-h").replace(/\^EMDASH/g, "-e-").replace(/\^OPENQUOTE/g, ' "').replace(/\^CLOSEQUOTE/g, '" ').replace(/\s+\./g, ".").replace(/\s+\!/g, "!").replace(/\s+\,/g, ",").replace(/\s+\;/g, ";").replace(/\s+\:/g, ":").replace(/\s\h\-\h\s/g, "-").replace(/[^!,"'.]\"\s/g, '"').replace(/\s+\-\e-\s+/g, "--").replace(/.+?[\.\?\!](\s|$)/g, function(b) {
        return b.charAt(0).toUpperCase() + b.substr(1)
    }).replace(/\"[a-z]/g, function(b) {
        return b.charAt(0) + b.charAt(1).toUpperCase()
    })
}(a))

```

**How it works:**

> https://gist.github.com/ericlagergren/1a61b5d772ae49ab3aea

JSFiddle (for the 653 byte cross-browser solution)

JSFiddle (for the 595 FF 22+ **only** solution)

JSFiddle (for the 547 FF 22+ **only** solution)

JSFiddle (for the 514 FF 22+ **only** solution)

JSFiddle (for the 487 FF 22+ **only** solution)

This is the first time I've had to write JS that uses more than one regex, and usually my regex is predefined.

I'll continue to shave off bytes as much as I can.

# Answer
> 1 votes
# PHP, 412 bytes

(Ungolfed here for clarity; see ideone for golfed version.)

PHP's preg\_replace() function will accept array arguments, which is pretty useful here. I *think* the following code does everything that's required. It passes all the test cases at least.

```
function x($s) {
    $r='preg_replace';
    $s=$r('/ +/',' ',$s);
    $s=$r(array('/ \^COMMA/','/ \^COLON/','/ \^SEMICOLON/','/ \^PERIOD/','/ \^BANG/',
                '/\^DASH/','/ \^HYPHEN /','/ \^EMDASH /','/\^OPENQUOTE /','/ \^CLOSEQUOTE/'),
          array(',',':',';','.','!','-','-','--','"',',"'),
          $s);
    $s=$r('/(^\W*\w|([\.!]| ")\W+\w)/e','strtoupper("$0")',$s);
    $s=$r('/([,\.!]),/','\1',$s);
    $s=$r('/(\w)( "\w)/e','"$1,".strtoupper("$2")',$s);
    echo $s;
}

```

---
Tags: code-golf, string, parsing, natural-language
---


title: Calculate number of characters in code

text:
# Question
Title: Calculate number of characters in code
The task is to find the number of characters in your source code up to the previous line.

You may do some addition of two integers, or whatever that comes to mind. But at the end of your logic, you need to calculate the number of characters written in your code up to the last line.

EDIT: The goal is to find the number of characters required to perform a task. For example, you are adding two numbers. The task is to find the number of characters used in doing that task.

New line characters do not count. Lets start.

# Answer
## JavaScript

I think that's what you want:

```
function foo() {
   return arguments.callee.toString()
}
foo().length

```
> 4 votes

---
Tags: popularity-contest
---


title: Find a binary tree's deepest node

text:
# Question
Title: Find a binary tree's deepest node
Write a program that takes a binary tree as input, and outputs the deepest node and its depth. If there is a tie, print all involved nodes as well as their depths. Each node is represented as:

`T(x,x)`

`T(x)`

`T`

where `T` is the identifier of one or more alphanumeric characters and each `x` is another node.

Here's a simple definition of a binary tree:

* At the head of a binary tree is a node.
* A node in a binary tree has at most two children.

For example, the input `A(B(C,D(E)))` (below) would output `3:E`.

While the following tree is a three-way tie between 5, 11, and 4, and their depth is also 3 (starting from 0):

The input `2(7(2,6(5,11)),5(9(4)))` (below) would output `3:5,11,4`.

This is code golf, so the shortest code measured in bytes wins.

# Answer
# CJam, 49 47

```
0q')/{'(/):U;,+:TW>{T:W];}*TW={U]',*}*T(}/;W':@

```

```
0                 " Push 0 ";
q                 " Read the whole input ";
')/               " Split the input by ')' ";
{                 " For each item ";
  '(/             " Split by '(' ";
  )               " Extract the last item of the array ";
  :U;             " Assign the result to U, and discard it ";
  ,               " Get the array length ";
  +               " Add the top two items of the stack, which are the array length and the number initialized to 0 ";
  :T              " Assign the result to T ";
  W>{             " If T>W, while W is always initialized to -1 ";
    T:W];         " Set T to W, and empty the stack ";
  }*
  TW={            " If T==W ";
    U]',*         " Push U and add a ',' between everything in the stack, if there were more than one ";
  }*
  T(              " Push T and decrease by one ";
}/
;                 " Discard the top item, which should be now -1 ";
W                 " Push W ";
':                " Push ':' ";
@                 " Rotate the 3rd item to the top ";

```
> 6 votes

# Answer
## Haskell, 186 bytes

```
p@(n,s)%(c:z)=maybe((n,s++[c])%z)(\i->p:(n+i,"")%z)$lookup c$zip"),("[-1..1];p%_=[p]
(n,w)&(i,s)|i>n=(i,show i++':':s)|i==n=(n,w++',':s);p&_=p
main=interact$snd.foldl(&)(0,"").((0,"")%)

```

Full program, takes tree on `stdin`, produces spec'd output format on `stdout`:

```
& echo '2(7(2,6(5,11)),5(9(4)))' | runhaskell 32557-Deepest.hs
3:5,11,4

& echo 'A(B(C,D(E)))' | runhaskell 32557-Deepest.hs
3:E

```

Guide to the golf'd code *(added better names, type signatures, comments, and some subexpressions pulled out and named -- but otherwise the same code; an ungolf'd version wouldn't conflate breaking into nodes with numbering, nor finding deepest with output formatting.)*:

```
type Label = String         -- the label on a node
type Node = (Int, Label)    -- the depth of a node, and its label

-- | Break a string into nodes, counting the depth as we go
number :: Node -> String -> [Node]
number node@(n, label) (c:cs) =
    maybe addCharToNode startNewNode $ lookup c adjustTable
  where
    addCharToNode = number (n, label ++ [c]) cs
        -- ^ append current character onto label, and keep numbering rest

    startNewNode adjust = node : number (n + adjust, "") cs
        -- ^ return current node, and the number the rest, adjusting the depth

    adjustTable = zip "),(" [-1..1]
        -- ^ map characters that end node labels onto depth adjustments
        -- Equivalent to [ (')',-1), (',',0), ('(',1) ]

number node _ = [node]      -- default case when there is no more input

-- | Accumulate into the set of deepest nodes, building the formatted output
deepest :: (Int, String) -> Node -> (Int, String)
deepest (m, output) (n, label)
    | n > m     = (n, show n ++ ':' : label)    -- n is deeper tham what we have
    | n == m    = (m, output ++ ',' : label)    -- n is as deep, so add on label
deepest best _ = best                           -- otherwise, not as deep

main' :: IO ()
main' = interact $ getOutput . findDeepest . numberNodes
  where
    numberNodes :: String -> [Node]
    numberNodes = number (0, "")

    findDeepest :: [Node] -> (Int, String)
    findDeepest = foldl deepest (0, "")

    getOutput :: (Int, String) -> String
    getOutput = snd

```
> 5 votes

# Answer
## GolfScript (75 chars)

Not especially competitive, but sufficiently twisted that it has some interest:

```
{.48<{"'^"\39}*}%','-)](+0.{;.@.@>-\}:^;@:Z~{2$2$={@@.}*;}:^;Z~\-])':'@','*

```

The code has three phases. Firstly we preprocess the input string:

```
# In regex terms, this is s/([ -\/])/'^\1'/g
{.48<{"'^"\39}*}%
# Remove all commas
','-
# Rotate the ' which was added after the closing ) to the start
)](+

```

We've transformed e.g. `A(B(C,D(E)))` to `'A'^('B'^('C'^'D'^('E'^)''^)''^)` . If we assign a suitable block to `^` we can do useful processing by using `~` to eval the string.

Secondly, we find the maximum depth:

```
0.
# The block we assign to ^ assumes that the stack is
#   max-depth current-depth string
# It discards the string and updates max-depth
{;.@.@>-\}:^;
@:Z~

```

Finally we select the deepest nodes and build the output:

```
# The block we assign to ^ assumes that the stack is
#   max-depth current-depth string
# If max-depth == current-depth it pushes the string under them on the stack
# Otherwise it discards the string
{2$2$={@@.}*;}:^;
# Eval
Z~
# The stack now contains
#   value1 ... valuen max-depth 0
# Get a positive value for the depth, collect everything into an array, and pop the depth
\-])
# Final rearranging for the desired output
':'@','*

```
> 4 votes

# Answer
## Perl 5 - 85

Please feel free to edit this post to correct the character count. I use `say` feature, but I don't know about the flags to make it run correctly without declaring `use 5.010;`.

```
$_=$t=<>,$i=0;$t=$_,$i++while s/\w+(\((?R)(,(?R))?\))?/$1/g,/\w/;@x=$t=~/\w+/gs;say"$i:@x"

```

**Demo on ideone**

The output is space-separated instead of comma-separated.

The code simply uses recursive regex to remove the root of the trees in the forest, until it is not possible to do so. Then the string before the last will contain all the leaf nodes at the deepest level.

### Sample runs

```
2
0:2

2(3(4(5)),6(7))
3:5

2(7(2,6(5,11)),5(9(4)))
3:5 11 4

1(2(3(4,5),6(7,8)),9(10(11,12),13(14,15)))
3:4 5 7 8 11 12 14 15

```
> 1 votes

# Answer
**VB.net**

```
Function FindDeepest(t$) As String
  Dim f As New List(Of String)
  Dim m = 0
  Dim d = 0
  Dim x = ""
  For Each c In t
    Select Case c
      Case ","
        If d = m Then f.Add(x)
        x = ""
      Case "("
        d += 1
        If d > m Then f.Clear() :
        m = d
        x = ""
      Case ")"
        If d = m Then f.Add(x) : x = ""
        d -= 1
      Case Else
        x += c
    End Select
  Next
  Return m & ":" & String.Join(",", f)
End Function

```

Assumption: Node Values can not contain `,`,`(`,`)`
> 1 votes

# Answer
# Javascript (E6) 120

Iterative version

```
m=d=0,n=[''];
prompt().split(/,|(\(|\))/).map(e=>e&&(e=='('?m<++d&&(n[m=d]=''):e==')'?d--:n[d]+=' '+e));
alert(m+':'+n[m])

```

**Ungolfed** and testable

```
F= a=> (
    m=d=0,n=[''],
    a.split(/,|(\(|\))/)
    .map(e=>e && (e=='(' ? m < ++d && (n[m=d]='') : e==')' ? d-- : n[d]+=' '+e)),
    m+':'+n[m]
)

```

**Test** In Firefox console:

```
['A', '2(7(2,6(5,11)),5(9(4)))', 'A(B(C,D(E)))']
.map(x => x + ' --> ' + F(x)).join('\n')

```

Output

> "A --\> 0: A
>
> 2(7(2,6(5,11)),5(9(4))) --\> 3: 5 11 4
>
> A(B(C,D(E))) --\> 3: E"
> 1 votes

---
Tags: code-golf, binary-tree
---