title: Grid-Routing Battle

text:
# Question
Title: Grid-Routing Battle
**NOTE:** This challenge is currently dead, as I'm unable to install the languages needed to run a match. If someone else has the time and interest to do it, I'm not opposed.

**See the bottom of the post for a leaderboard.**

This is a semi-cooperative king-of-the-hill challenge, where the bots construct paths through a two-dimensional grid graph. The bot who controls the nodes with the most traffic is the winner. However, it takes more than one bot's resources to actually build a connecting path, so the bots will have to work together -- to some extent.

# Gameplay

In the following, let `N > 0` be the number of bots in play.

## The Grid

The game is played on a two-dimensional integer grid of size `⌊4/3N<sup>2</sup>⌋ × ⌊4/3N<sup>2</sup>`, whose bottom left coordinate is at `(0,0)`. Each coordinate `(x,y)` with `0 ≤ y < ⌊4/3N<sup>2</sup>⌋-1` has outgoing edges to the three coordinates `(x-1,y+1)`, `(x,y+1)`, and `(x+1,y+1)` above it, where the `x`-coordinates are taken modulo `⌊4/3N<sup>2</sup>`. This means that the grid wraps around at the east and west edges. Every bottom coordinate `(x,0)` is a *source*, and every top coordinate `(x,⌊4/3N<sup>2</sup>⌋-1)` is a *sink*.

The following picture shows an `8 × 8` grid.

Each vertex of the graph is either *inactive*, *active*, or *broken*. All vertices start inactive, and can be activated by bots, which will then be their owners. Also, bots can break vertices, and they cannot be repaired.

## Turn Order

A turn consists of a *destruction phase* and an *activation phase*. In the destruction phase, each bot may break one inactive vertex. That vertex is broken from then on, and may not be activated by anyone. In the activation phase, each bot may activate one inactive vertex. From then on, they own that vertex, and it cannot be reactivated by anyone else. Several bots may own a single vertex, if they all activate it on the same turn. In each phase, the vertex selections are done simultaneously.

## Scoring

One round lasts for exactly `N<sup>2</sup>` turns. After this, the round is scored as follows. From each active source vertex, we perform `N` times a randomized depth-first search along the active vertices (meaning that the children of each vertex are visited in a random order). If a path is found from the source to some sink, then for all vertices along that path, every owner of the vertex gets one point.

The entire game lasts for 100 rounds, and the bot with the most points overall is the winner. I may increase this number, if the variance of the scores is too high.

# Additional Rules

* No messing with the controller or other submissions.
* At most one submission per contestant.
* No external resources, except one private text file, wiped clean at the beginning of the game.
* Do not design your bot to beat or support specific opponents.
* Provide commands to compile and run your bot. Any compiler/interpreter that's freely available for Debian Linux is acceptable.

# The Controller

The controller is written in Python 3, and can be found in GitHub. See the README file for detailed instructions. Here's an API to get you started:

* Bots are started at the beginning of each round, and persist until the end of the round. The communicate with the controller via STDIN and STDOUT, using newline-terminated messages.
* `BEGIN [num-of-bots] [num-of-turns] [side-length]` is input at the beginning.
* `DESTROY [turn]` is input at the beginning of each destruction phase. Your bot shall respond with either `VERTEX x,y` to choose a vertex, or `NONE`.
* `BROKEN [turn] [your-choice] [other-choices]` is input at the end of each destruction phase. The order of the other bots is randomized at the beginning of each game, but stays fixed during it. The choices are presented as `x,y` or `N`.
* `ACTIVATE [turn]` and `OWNED [turn] [your-choice] [other-choices]` are the equivalents of the above for the activation phase, and have the same semantics.
* `SCORE [your-score] [other-scores]` is input at the end of the game.
* Your bot has **1 second** to analyze the results of a phase and choose the next vertex, and **1 second** to quit after given the score. I will test the submissions on my relatively old laptop, so it's better to leave some margin here.

**Please remember to flush your output buffer.** Not doing so may hang the controller in some environments.

# Leaderboard

*Updated 3/13/2015*

Peacemaker is up and running, and Funnelweb received an update too. The scores jumped up by an order of magnitude. Connector exceeded the time limit in two games.

```
Funnelweb: 30911
Connector: 18431
Watermelon: 3488
Annoyance: 1552
Explorer: 735
Checkpoint: 720
Random Builder: 535
FaucetBot: 236
Peacemaker: 80

```

The full log with ASCII art graphics can be found in the controller's repository, in `graphical_log.txt`.

Some observations:

* Connector can very easily be stopped by breaking a single vertex in front of it. I suspect Annoyance frequently does this. However, it currently makes little sense because only Connector can conceivably construct a path.
* Watermelon can get a decent score by simply happening to be on a connecting path (since the DFS is very likely to use its vertices).
* Explorer likes to grow vines from the watermelons.
* The updated Funnelweb gets really good scores, since Connector usually latches onto it in the lower half of the grid.
* The games are getting quite long, the average round taking about 25 seconds on my machine.

# Answer
# Funnelweb, Python 2

version 1.2 - Better joining code, added new animation

Named after one of Australia's less friendly spiders. This bot first builds a funnel-shaped nest in the top rows, then lures other bots into building paths for traffic to the nest.

Here is a new animation of a 6 bot game on a 4/3N^2 board showing the funnelweb and some simpler bots:

The funnelweb's Python code:

```
from random import *
import sys
ME = 0
def pt(x,y): return '%u,%u' % (x % side_len, y)

while True:
    msg = raw_input().split()

    if msg[0] == 'BEGIN':
        turn = 0
        numbots, turns, side_len = map(int, msg[1:])
        R = range(side_len)
        top = side_len - 1
        grid = dict((pt(x, y), []) for x in R for y in R)
        mynodes = set()
        deadnodes = set()
        freenodes = set(grid.keys())
        mycol = choice(R)
        extra = sample([pt(x,top) for x in R], side_len)
        path = [(mycol, y) for y in range(top, top - side_len/6, -1)]
        moves = []
        fence = []
        for x,y in path:
            moves.append( [pt(x,y), pt(x+1,y), pt(x-1,y)] )
            fence.extend( [pt(x+1,y), pt(x-1,y)] )
        for dx in range(2, side_len):
            fence.extend( [pt(x+dx,y), pt(x-dx,y)] )
        for x,y in [(mycol, y) for y in
                range(top - side_len/6, top - 3*side_len/4, -1)]:
            moves.append( [pt(x,y), pt(x+1,y), pt(x-1,y)] )

    elif msg[0] == 'DESTROY':
        target = 'NONE'
        while fence:
            loc = fence.pop(0)
            if loc in freenodes:
                target = 'VERTEX ' + loc
                break
        print target
        sys.stdout.flush()

    elif msg[0] == 'BROKEN':
        for rid, loc in enumerate(msg[2:]):
            if loc != 'N':
                grid[loc] = None
                deadnodes.add(loc)
                freenodes.discard(loc)
                if loc in extra: extra.remove(loc)

    elif msg[0] == 'ACTIVATE':
        target = 'NONE'
        while moves:
            loclist = moves.pop(0)
            goodlocs = [loc for loc in loclist if loc in freenodes]
            if goodlocs:
                target = 'VERTEX ' + goodlocs[0]
                break
        if target == 'NONE':
            if extra:
                target = 'VERTEX ' + extra.pop(0)
            else:
                target = 'VERTEX ' + pt(choice(R), choice(R))
        print target
        sys.stdout.flush()

    elif msg[0] == 'OWNED':
        for rid, loc in enumerate(msg[2:]):
            if loc != 'N':
                grid[loc].append(rid)
                if rid == ME:
                    mynodes.add(loc)
                freenodes.discard(loc)
                if loc in extra: extra.remove(loc)
        turn += 1

    elif msg[0] == 'SCORE':
        break

```

The spider is run with `python funnelweb.py`.
> 7 votes

# Answer
## Connector (Java)

Tries to create a path at a random position. Because it can't create a path on its own, it searches for active cells and uses them. Credit goes to Geobits, from whom I stole some code. Also, this submission isn't finished yet, as it simply stops doing anything as soon as the path is built.

**Edit:** If a path is built, Connector tries to create multiple paths along the existing one.

```
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class Connector {
    private static final int INACTIVE = 0;
    private static final int ACTIVE   = 1;
    private static final int BROKEN   = 2;
    private static final int MINE     = 3;

    private int size = 0;
    private int[][] grid = new int[size][size];
    private Point previousCell = null;
    private final List<Point> path = new ArrayList<>();

    public static void main(String[] args) {
        new Connector().start();
    }

    private void start() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                String input = reader.readLine();
                act(input);
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(0);
            }
        }
    }

    private void act(String input) throws Exception {
        String[] msg = input.split(" ");
        String output = "";
        int turn;
        switch(msg[0]){
        case "BEGIN":
            size = Integer.parseInt(msg[3]);
            grid = new int[size][size];
            break;
        case "DESTROY":
            output = "NONE";
            break;
        case "BROKEN":
            update(msg, true);
            break;
        case "ACTIVATE":
            turn = Integer.parseInt(msg[1]);
            output = activate(turn);
            break;
        case "OWNED":
            update(msg, false);
            break;
        case "SCORE":
            System.exit(0);
            break;
        }
        if (output.length() > 0) {
            System.out.println(output);
        }
    }

    private String activate(int turn) {
        if (turn == 0) {
            Random r = new Random();
            previousCell = new Point(r.nextInt(size), 0);
            return "VERTEX " + previousCell.x + "," + 0;
        }
        Point lastCell = findLastPathCell(previousCell.x, previousCell.y);
        if (lastCell.y == size-1) {
            //path is done
            Point extendingPathPoint = findExtendingPathPoint();
            if (extendingPathPoint == null) {
                return "NONE";
            }
            return "VERTEX " + extendingPathPoint.x + "," + extendingPathPoint.y;
        } else {
            int x = findBestX(lastCell.x, lastCell.y);
            return "VERTEX " + x + "," + (lastCell.y + 1);
        }
    }

    private int findBestX(int x, int y) {
        int bestScore = Integer.MIN_VALUE;
        int bestX = 0;
        for (int i = -1; i <= 1; i++) {
            int newY = y + 1;
            int newX = (x + i + size) % size;
            int score = calcCellScore(newX, newY, 10);
            if (score > bestScore) {
                bestScore = score;
                bestX = newX;
            } else if (score == bestScore && Math.random() < 0.3) {
                bestX = newX;
            }
        }
        return bestX;
    }

    private int calcCellScore(int x, int y, int depth) {
        int newY = y + 1;
        if (depth < 0) {
            return 1;
        }
        if (newY >= size)
            return 100;
        int cellScore = 0;
        for (int i = -1; i <= 1; i++) {
            int newX = (x + i + size) % size;
            if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
                cellScore += 5;
            } else if (grid[newX][newY] == INACTIVE) {
                cellScore += 1;
            } else {
                cellScore -= 2;
            }
            cellScore += calcCellScore(newX, newY, depth -1);
        }
        return cellScore;
    }

    private Point findLastPathCell(int x, int y) {
        Point thisCell = new Point(x,y);
        int newY = y + 1;
        if (newY >= size) {
            return thisCell;
        }
        List<Point> endCells = new ArrayList<>();
        endCells.add(thisCell);
        path.add(thisCell);
        for (int i = -1; i <= 1; i++) {
            int newX = (x + i + size) % size;
            if (grid[newX][newY] == ACTIVE || grid[newX][newY] == MINE) {
                endCells.add(findLastPathCell(newX, newY));
            }
        }
        int bestY = -1;
        Point bestPoint = null;
        for (Point p : endCells) {
            if (p.y > bestY) {
                bestY = p.y;
                bestPoint = p;
            }
        }
        return bestPoint;
    }

    private Point findExtendingPathPoint() {
        if (path.size() == 0)
            return null;
        Random rand = new Random();
        for (int i = 0; i < size; i++) {
            Point cell = path.get(rand.nextInt(path.size()));
            for (int j = -1; j <= 1; j += 2) {
                Point newCellX = new Point((cell.x + j + size) % size, cell.y);
                if (grid[newCellX.x][newCellX.y] == INACTIVE)
                    return newCellX;

                Point newCellY = new Point(cell.x, cell.y + j);
                if (cell.y < 0 || cell.y >= size)
                    continue;
                if (grid[newCellY.x][newCellY.y] == INACTIVE)
                    return newCellY;
            }
        }
        return null;
    }

    private void update(String[] args, boolean destroyPhase) {
        for(int i = 2; i < args.length; i++) {
            String[] tokens = args[i].split(",");
            if(tokens.length > 1){
                int x = Integer.parseInt(tokens[0]);
                int y = Integer.parseInt(tokens[1]);
                if (grid[x][y] == INACTIVE) {
                    if (destroyPhase) {
                        grid[x][y] = BROKEN;
                    } else if (i == 2) {
                        grid[x][y] = MINE;
                        path.add(new Point(x,y));
                        previousCell = new Point(x,y);
                    } else {
                        grid[x][y] = ACTIVE;
                    }
                }
            }
        }
    }
}

```
> 7 votes

# Answer
# Checkpoint, Java

This bot tries to create checkpoints so that any valid path passes through one of my vertices. Since there are N2 turns and the board is 2N2 across, I can activate/break every node on a single horizontal line (assuming I'm there first). Do this in an alternating pattern (`x` is broken, `o` is mine):

```
xoxoxoxoxoxox...

```

If you want to make a path, you need to go through my checkpoints :)

Now, there are several issues this might face. First, it's not going to do very well at all unless there are many paths. Since he doesn't make *any* productive paths himself, he really is totally reliant on there being some competitors. Even a couple competitors combining to make a single path won't help much, since he only scores one spot for each path found. What he needs to shine is probably quite a few bots making quite a few different paths. Even then, it might not score *very* highly, but it was an idea I had in chat, so...

If one of the spaces on the line is blocked/claimed already, I just search for a nearby spot I can use (preferably on the same `x` line, just shifted vertically).

---

```
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Checkpoint {
    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true)
            try {
                String input = reader.readLine();
                act(input);
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(0);
            }
    }

    static void act(String input) throws Exception{
        String[] msg = input.split(" ");
        String output = "";
        int turn;
        boolean found = false;
        switch(msg[0]){
        case "BEGIN":
            size = Integer.parseInt(msg[3]);
            grid = new int[size][size];
            target = size/2;
            break;
        case "DESTROY":
            turn = Integer.parseInt(msg[1]);
            for(int x=0;x<size;x+=2)
                for(int y=0;y<size&&!found;y++)
                    if(grid[(x+turn*2)%size][(y+target)%size]==INACTIVE){
                        output = "VERTEX " + ((x+turn*2)%size) + "," + ((y+target)%size);
                        found = true;
                    }
            if(output.length() < 1)
                output = "NONE";
            break;
        case "BROKEN":
            for(int i=2;i<msg.length;i++){
                String[] tokens = msg[i].split(",");
                if(tokens.length>1){
                    int x = Integer.parseInt(tokens[0]);
                    int y = Integer.parseInt(tokens[1]);
                    if(grid[x][y]==INACTIVE)
                        grid[x][y] = BROKEN;
                }
            }
            break;
        case "ACTIVATE":
            turn = Integer.parseInt(msg[1]);
            for(int x=1;x<size;x+=2)
                for(int y=0;y<size&&!found;y++)
                    if(grid[(x+turn*2)%size][(y+target)%size]==INACTIVE){
                        output = "VERTEX " + ((x+turn*2)%size) + "," + ((y+target)%size);
                        found = true;
                    }
            if(output.length() < 1)
                output = "NONE";
            break;
        case "OWNED":
            for(int i=2;i<msg.length;i++){
                String[] tokens = msg[i].split(",");
                if(tokens.length>1){
                    int x = Integer.parseInt(tokens[0]);
                    int y = Integer.parseInt(tokens[1]);
                    if(i==2){
                        if(grid[x][y]==INACTIVE)
                            grid[x][y] = MINE;
                    }else{
                        if(grid[x][y]==INACTIVE)
                            grid[x][y]=ACTIVE;
                    }
                }
            }
            break;
        case "SCORE":
            System.exit(0);
            break;
        }
        if(output.length()>0)
            System.out.println(output);
    }

    static int size = 2;
    static int target = size/2;
    static int[][] grid = new int[size][size];

    static final int INACTIVE = 0;
    static final int ACTIVE   = 1;
    static final int BROKEN   = 2;
    static final int MINE     = 3;
}

```

---

To compile, it's `javac Checkpoint.java`. To run, `java Checkpoint`. You'll want to add/change the path to reflect wherever it is.
> 6 votes

# Answer
# FaucetBot (in R)

Creates a bottleneck on the second line, and activate nodes on the path behind it.

```
infile <- file("stdin")
open(infile)
repeat{
    input <- readLines(infile,1)
    args <- strsplit(input," ")[[1]]
    if(args[1]=="BEGIN"){
        L <- as.integer(args[4])
        M <- N <- matrix(0,nrow=L,ncol=L)
        x0 <- sample(2:(L-1),1)
        }
    if(args[1]=="DESTROY"){
        if(args[2]==0){
            X <- x0
            Y <- 2
            }else{
                free <- which(M[,2] == 0)
                mine <- which(N[,2] == 1)
                X <- free[which.min(abs(free-mine))]
                Y <- 2
                }
        if(length(X)){cat(sprintf("VERTEX %s,%s\n",X-1,Y-1))}else{cat("NONE\n")}
        flush(stdout())
        }
    if(args[1]=="BROKEN"){
        b <- strsplit(args[args!="N"][-(1:2)],",")
        o <- strsplit(args[3],",")[[1]]
        b <- lapply(b,as.integer)
        if(o[1]!="N") N[as.integer(o[1])+1,as.integer(o[2])+1] <- -1
        for(i in seq_along(b)){M[b[[i]][1]+1,b[[i]][2]+1] <- -1}
        }
    if(args[1]=="ACTIVATE"){
        if(args[2]==0){
            broken <- which(M[,2] == -1)
            free <- which(M[,2] == 0)
            X <- free[which.min(abs(broken-free))]
            Y <- 2
            }else{
                y <- 3
                X <- NULL
                while(length(X)<1){
                    lastrow <- which(N[,y-1]==1)
                    newrow <- unlist(sapply(lastrow,function(x)which(M[,y]==0 & abs((1:L)-x)<2)))
                    if(length(newrow)){
                        X <- sample(newrow,1)
                        Y <- y
                        }
                    y <- y+1
                    if(y>L){X <- x0; Y <- 1}
                    }
                }
        cat(sprintf("VERTEX %s,%s\n",X-1,Y-1))
        flush(stdout())
        }
    if(args[1]=="OWNED"){
        b <- strsplit(args[args!="N"][-(1:2)],",")
        o <- strsplit(args[3],",")[[1]]
        b <- lapply(b,as.integer)
        if(o[1]!="N") N[as.integer(o[1])+1,as.integer(o[2])+1] <- 1
        for(i in seq_along(b)){M[b[[i]][1]+1,b[[i]][2]+1] <- 1}
        }
    if(args[1]=="SCORE") q(save="no")
    }

```

If I didn't screw up, the final configuration should be something like:

```
........    .a..aa..
..aaa...    ..aaa...
.xxaxx..    xxxaxxx.    etc.
........    ........

```

Command is `Rscript FaucetBot.R`.
> 5 votes

# Answer
# Watermelon, Java

Attempts to draw watermelons on the grid.

```
import java.awt.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Watermelon {

    private static int numberOfBots;
    private static int numberOfTurns;
    private static int sideLength;

    private static int turn = 0;

    private static int[][] theGrid;

    private static final int INACTIVE = -2;
    private static final int BROKEN   = -1;
    private static final int MINE     =  0;
    private static final int ACTIVE   =  1;

    private static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private static PrintStream out = System.out;

    public static void main(String[] args) throws IOException {
        while (true){
            String[] input = in.readLine().trim().split(" ");
            String instruction = input[0];
            switch (instruction){
                case "BEGIN":
                    begin(input);
                    break;
                case "DESTROY":
                    destroy(input);
                    break;
                case "BROKEN":
                    broken(input);
                    break;
                case "ACTIVATE":
                    activate(input);
                    break;
                case "OWNED":
                    owned(input);
                    break;
                default:
                    return;
            }
            out.flush();
        }
    }

    private static void begin(String[] input) {
        numberOfBots = Integer.parseInt(input[1]);
        numberOfTurns = Integer.parseInt(input[2]);
        sideLength = Integer.parseInt(input[3]);
        theGrid = new int[sideLength][sideLength];
        for (int x = 0; x < sideLength; x++){
            for (int y = 0; y < sideLength; y++){
                theGrid[x][y] = INACTIVE;
            }
        }
    }

    private static void owned(String[] input) {
        turn = Integer.parseInt(input[1]);
        for (int i = input.length - 1; i >= 2; i--){
            if (input[i].equals("N")){
                continue;
            }
            String[] coordinates = input[i].split(",");
            int x = Integer.parseInt(coordinates[0]);
            int y = Integer.parseInt(coordinates[1]);
            int player = i - 2;
            if (player == 0){
                theGrid[x][y] = MINE;
            } else {
                theGrid[x][y] = ACTIVE;
            }
        }
    }

    private static void activate(String[] input) {
        turn = Integer.parseInt(input[1]);
        double[][] values = new double[sideLength][sideLength];
        List<Point> pointList = new ArrayList<>();
        for (int x = 0; x < sideLength; x++){
            for (int y = 0; y < sideLength; y++){
                if (theGrid[x][y] == MINE || theGrid[x][y] == ACTIVE){
                    for (int x1 = 0; x1 < sideLength; x1++){
                        for (int y1 = 0; y1 < sideLength; y1++){
                            double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
                            values[x1][y1] += 1 / (distance + 1);
                        }
                    }
                }
                pointList.add(new Point(x, y));
            }
        }
        pointList.sort(Comparator.comparingDouble((Point a) -> values[a.x][a.y]).reversed());
        for (Point point : pointList){
            if (theGrid[point.x][point.y] == INACTIVE){
                out.println("VERTEX " + point.x + "," + point.y);
                return;
            }
        }
        out.println("NONE");
    }

    private static void broken(String[] input) {
        turn = Integer.parseInt(input[1]);
        for (int i = 2; i < input.length; i++){
            if (input[i].equals("N")){
                continue;
            }
            String[] coordinates = input[i].split(",");
            int x = Integer.parseInt(coordinates[0]);
            int y = Integer.parseInt(coordinates[1]);
            theGrid[x][y] = BROKEN;
        }
    }

    private static void destroy(String[] input) {
        turn = Integer.parseInt(input[1]);
        double[][] values = new double[sideLength][sideLength];
        List<Point> pointList = new ArrayList<>();
        for (int x = 0; x < sideLength; x++){
            for (int y = 0; y < sideLength; y++){
                if (theGrid[x][y] == MINE){
                    for (int x1 = 0; x1 < sideLength; x1++){
                        for (int y1 = 0; y1 < sideLength; y1++){
                            double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
                            values[x1][y1] -= 1 / (distance + 1);
                        }
                    }
                }
                if (theGrid[x][y] == ACTIVE){
                    for (int x1 = 0; x1 < sideLength; x1++){
                        for (int y1 = 0; y1 < sideLength; y1++){
                            double distance = Math.pow(x - x1, 2) + Math.pow(y - y1, 2);
                            values[x1][y1] += 1 / (distance + 1) / (numberOfBots - 1);
                        }
                    }
                }
                pointList.add(new Point(x, y));
            }
        }
        pointList.sort(Comparator.comparingDouble((Point a) -> values[a.x][a.y]).reversed());
        for (Point point : pointList){
            if (theGrid[point.x][point.y] == INACTIVE){
                out.println("VERTEX " + point.x + "," + point.y);
                return;
            }
        }
        out.println("NONE");
    }
}

```
> 5 votes

# Answer
# Peacemaker, Java

Based on Manu's code.

Peacemaker search conflict zones (i.e. most BROKEN or ACTIVE vertex concentration) and activates a random vertex nearby.

```
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.IntStream;

public class Peacemaker {
    private static final int INACTIVE = 0;
    private static final int ACTIVE   = 1;
    private static final int BROKEN   = 2;
    private static final int MINE     = 3;

    private int size = 0;
    private int[][] grid = new int[size][size];
    private int startingPoint = 0;

    public static void main(String[] args) {
        new Peacemaker().start();
    }

    private void start() {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            try {
                String input = reader.readLine();
                act(input);
            } catch (Exception e) {
                e.printStackTrace();
                System.exit(0);
            }
        }
    }

    private void act(String input) throws Exception {
        String[] msg = input.split(" ");
        String output = "";
        int turn;
        switch(msg[0]){
        case "BEGIN":
            size = Integer.parseInt(msg[3]);
            grid = new int[size][size];
            break;
        case "DESTROY":
            output = "NONE";
            break;
        case "BROKEN":
            update(msg, true);
            break;
        case "ACTIVATE":
            turn = Integer.parseInt(msg[1]);
            output = activate(turn);
            break;
        case "OWNED":
            update(msg, false);
            break;
        case "SCORE":
            System.exit(0);
            break;
        }
        if (output.length() > 0) {
            System.out.println(output);
        }
    }

    private String activate(int turn) {
        Random r = new Random();
        if (turn == 0) {
            startingPoint = r.nextInt(size);
            return "VERTEX " + startingPoint + "," + 0;
        } else {

            Point point = searchConflicts();

            int posX = point.x;
            int posY = point.y;

            while (grid[posX][posY] != INACTIVE) {
                 int previousX = (posX - 1 < 0 ? size - 1 : posX - 1);
                 int nextX = (posX + 1 > size - 1 ? 0 : posX + 1);
                 int previousY = (posY - 1 < 0 ? size - 1 : posY - 1);
                 int nextY = (posY + 1 > size - 1 ? 0 : posY + 1);

                 int choice = r.nextInt(4);
                 switch (choice) {
                     case 0: posX = previousX; break;
                     case 1: posX = nextX; break;
                     case 2: posY = previousY; break;
                     case 3: posY = nextY; break;
                 }
            }

            return "VERTEX " + posX + "," + posY;
        }
    }

    private Point searchConflicts() {

        int previousCellScore = 0;
        int cellX = 0;
        int cellY = 0;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j ++) {
                if (previousCellScore < adjacentCellsScore(i, j)) {
                    cellX = i; cellY = j;
                    previousCellScore = adjacentCellsScore(i, j);
                }
            }
        }
        return new Point(cellX, cellY);
    }

    /*  Format of adjacent cells :
     *
     *   0 1 2
     *   3 . 4
     *   5 6 7
     */
    private int adjacentCellsScore(int x, int y) {

        int[] scores = new int[8];

        int previousX = (x - 1 < 0 ? size - 1 : x - 1);
        int nextX = (x + 1 > size - 1 ? 0 : x + 1);
        int previousY = (y - 1 < 0 ? size - 1 : y - 1);
        int nextY = (y + 1 > size - 1 ? 0 : y + 1);

        scores[0] = calcScore(previousX, nextY);
        scores[1] = calcScore(x, nextY);
        scores[2] = calcScore(nextX, nextY);
        scores[3] = calcScore(previousX, y);
        scores[4] = calcScore(nextX, y);
        scores[5] = calcScore(previousX, previousY);
        scores[6] = calcScore(x, previousY);
        scores[7] = calcScore(nextX, previousY);

        return IntStream.of(scores).reduce(0, (a, b) -> a + b);
    }

    private int calcScore(int x, int y) {
        int activeScore = 2;
        int mineScore = 1;
        int inactiveScore = 0;
        int brokenScore = 3;

        if (grid[x][y] == ACTIVE)
            return activeScore;
        else if (grid[x][y] == MINE)
            return mineScore;
        else if (grid[x][y] == INACTIVE)
            return inactiveScore;
        else if (grid[x][y] == BROKEN)
            return brokenScore;
        else
            return 0;
    }

    private void update(String[] args, boolean destroyPhase) {
        for(int i = 2; i < args.length; i++) {
            String[] tokens = args[i].split(",");
            if(tokens.length > 1){
                int x = Integer.parseInt(tokens[0]);
                int y = Integer.parseInt(tokens[1]);
                if (grid[x][y] == INACTIVE) {
                    if (destroyPhase) {
                        grid[x][y] = BROKEN;
                    } else if (i == 2) {
                        grid[x][y] = MINE;
                    } else {
                        grid[x][y] = ACTIVE;
                    }
                }
            }
        }
    }
}

```
> 5 votes

# Answer
# Random Builder, Python 3

This is a stupid example bot that never destroys anything, and tries to activate a random vertex every turn. Note that it doesn't need to check whether the vertex is inactive; the controller takes care of that.

```
import random as r

while True:
    msg = input().split()
    if msg[0] == "BEGIN":
        side_len = int(msg[3])
    elif msg[0] == "DESTROY":
        print("NONE")
    elif msg[0] == "ACTIVATE":
        print("VERTEX %d,%d"%(r.randrange(side_len), r.randrange(side_len)), flush=True)
    elif msg[0] == "SCORE":
        break

```

Run with the command

```
python3 random_builder.py

```

You may need to replace `python3` by `python` depending on your Python installation. To do this, just edit the `bots.txt` file. I updated the controller, and there's no need to mess with file paths anymore.
> 2 votes

# Answer
# Explorer, Python 3

Activation strategy:

Creates a heatmap based on the state of every node (active/inactive/broken) and chooses the node which would have the biggest expected heatmap-value per person if it would choose that one.

Destruction strategy:

Never destroys anything as that doesn't help the bot much.

```
import sys

class bd:

    def __init__(s, l):

        s.l=l
        s.b=[]
        s.v=[]
        s.m=[]
        s.bm=[]
        s.utd=False #up_to_date
        s.bmc=1

        for i in range(s.l):
            s.b+=[[]]
            s.v+=[[]]
            s.m+=[[]]
            s.bm+=[[]]
            for k in range(s.l):
                s.b[i]+=[0]
                s.v[i]+=[0]
                s.m[i]+=[0]
                s.bm[i]+=[s.bmc]

    def update(s):
        s.utd=True

        vu=[]
        vd=[]
        for i in range(s.l):
            vu+=[[]]
            vd+=[[]]
            for k in range(s.l):
                vu[i]+=[1]
                vd[i]+=[1]

        #spread up
        for i in range(s.l):
            vu[i][0]*=s.bm[i][0]

        for k in range(1,s.l):
            for i in range(s.l):
                sumv=vu[(i-1)%s.l][k-1]+vu[(i)%s.l][k-1]+vu[(i+1)%s.l][k-1]
                vu[i][k]*=sumv*s.bm[i][k]/3

        #spread down
        t=s.l-1
        for i in range(s.l):
            vd[i][t]*=s.bm[i][t]

        for k in range(s.l-2,-1,-1):
            for i in range(s.l):
                sumv=vd[(i-1)%s.l][k+1]+vd[(i)%s.l][k+1]+vd[(i+1)%s.l][k+1]
                vd[i][k]*=sumv*s.bm[i][k]/3

        #mult
        for i in range(s.l):
            for k in range(s.l):
                if s.b[i][k]==-1 or s.m[i][k]==1:
                    s.v[i][k]=float(-1)
                else:
                    s.v[i][k]=vu[i][k]*vd[i][k]/(s.b[i][k]+1)

    def add_act(s,al):
        s.utd=False

        for ind, ap in enumerate(al):
            i,k=ap
            s.b[i][k]+=1
            s.bm[i][k]=2*s.bmc
            #doesn't work alone WHY???
            if ind==0: s.m[i][k]=1

    def add_ina(s,il):
        s.utd=False

        for ind, ip in enumerate(il):
            i,k=ip
            s.b[i][k]=-1
            s.bm[i][k]=0

    def get_newact(s):
        s.update()
        vm=-28
        pm=None
        for i in range(s.l):
            for k in range(s.l):
                if s.v[i][k]>vm:
                    vm=s.v[i][k]
                    pm=(i,k)
        #doesn't work alone WHY???
        s.m[pm[0]][pm[1]]=1
        return pm

b=None

while True:
    inp=input()
    msg = inp.split()
    if msg[0] == "BEGIN":
        b = bd(int(msg[3]))
    elif msg[0] == "DESTROY":
        print("NONE")
    elif msg[0] == "BROKEN":
        pl=[]
        for m in msg[2:]:
            if m!='N':
                pl+=[tuple(map(int,m.split(',')))]
        b.add_ina(pl)
    elif msg[0] == "ACTIVATE":
        at=b.get_newact()
        print("VERTEX %d,%d"%(at[0], at[1]))
    elif msg[0] == "OWNED":
        pl=[]
        for m in msg[2:]:
            if m!='N':
                pl+=[tuple(map(int,m.split(',')))]
        b.add_act(pl)
    elif msg[0] == "SCORE":
        break

    sys.stdout.flush()

```
> 2 votes

# Answer
# Annoyance, Bash

```
#!/bin/bash

declare -A avail
broken=
owned=

while read c p
    case "$c" in
        ACTIVATE|BROKEN) v=broken;;
        *) v=owned
    esac
    case "$c" in
        BEGIN)
            read b t n <<<"$p"
            list=$(
                eval "echo {0..$((n-1))},{0..$((n-1))}\$'\\n'" |
                shuf
            )
            for i in $list; do
                avail[$i]=1
            done;;
        DESTROY|ACTIVATE)
            for t in $(
                for i in ${!v}; do
                    [ "$i" != N ] &&
                    if [ "$c" = ACTIVATE ]; then
                        echo $(((${i%,*}+2)%n)),${i#*,}
                        echo $(((${i%,*}-2+n)%n)),${i#*,}
                    else
                        echo ${i%,*},$(((${i#*,}+1)%n))
                        echo ${i%,*},$(((${i#*,}-1+n)%n))
                    fi
                done |
                shuf
            ) $list; do
                [ "${avail[$t]}" ] && echo VERTEX $t && break
            done ||
            echo NONE;;
        BROKEN|OWNED)
            read x m $v <<<"$p";
            for i in $m ${!v}; do
                unset avail[$i]
            done;;
        SCORE)! :
    esac
do :;done

```

Tried to make the result looks more interesting.

Run with `bash annoyance.sh`.
> 1 votes

# Answer
# Middle Man

I saw that some bots built from the top, and some from the bottom. This is the first (I think) to start in the middle and work up and down.

(it is not tested with the controller, so if it dose not work, let me know.)

```
class Node

  def self.set_size s
    @@grid = Array.new(s,Array.new(s,0))
  end

  def initialize x,y
    @x=x
    @y=y
  end

  def offset dx,dy
    return Node.new @x+dx,@y+dy
  end

  def state
    return -1 if @x<0 || @y<0 || @x>=@@grid.length || @y>=@@grid.length
    @@grid[@x][@y]
  end

  def state= n
    return -1 if @x<0 || @y<0 || @x>=@@grid.length || @y>=@@grid.length
     @@grid[@x][@y]=n
  end

  def active?
    state > 0
  end

  def open?
    state == 0
  end
  attr_reader :x,:y

  def to_s
    "VERTEX #{@x},#{@y}"
  end

  def scan_down
    ans = nil
    [0,-1,1].each do|offset|
      n = Node.new @x+offset,@y-1
      ans = (ans||n) if n.open?
      ans = (n.scan_down||ans) if n.active?
    end
    return ans
  end

  def scan_up
    ans = nil
    [0,-1,1].each do|offset|
      n = Node.new @x+offset,@y+1
      ans = (ans||n) if n.open?
      ans = (n.scan_up||ans) if n.active?
    end
    return ans
  end

end

input = gets.split
input.shift

BotCount = input.shift.to_i
Turns = input.shift.to_i
GridSize = input.shift.to_i

Node.set_size GridSize

midRow = GridSize/2

toDestroy = (0...GridSize).map{|i|Node.new i,midRow}
toDestroy.reject!{|n| n.x==midRow}

chain = []
Turns.times do
  gets;
  toDestroy.each{|x|
    if x.active?
      toDestroy.push x.offset 0,1
      toDestroy.push x.offset 1,1
      toDestroy.push x.offset -1,1
    end
  }
  toDestroy.reject!{|x|!x.open?}
  puts toDestroy.sample
  input = gets.split
  input.shift;input.shift
  input.each{|str|
    a,b = str.split ','
    (Node.new a.to_i,b.to_i).state=1
  }
  gets;

  if chain.length == 0
    n = Node.new midRow,midRow
    until n.open?
      n = Node.new n.x+1,midRow
    end
    puts chain[0]=n
  elsif rand>0.5
    n=nil
    loop do
      h=chain[0]
      n = h.scan_down
     break if !n
      chain.shift
    end
    h.unshift n
    puts n
  else
    loop do
      h=chain[-1]
      n = h.scan_up
      h.pop if !n
      brake if n
    end
    chain.push n
    puts n
  end

  input = gets.split
  input.shift;input.shift
  input.each{|str|
    a,b = str.split ','
    (Node.new a,b).state=-1
  }

end
gets
exit

```
> 1 votes

---
Tags: king-of-the-hill, path-finding, grid
---


title: Computing the geometric median

text:
# Question
Title: Computing the geometric median
Given a list of integer points in an *n*-dimensional space, output the geometric median. Note that the output is not necessarily integer. Your answer must be precise to at least two digits after the decimal point.

You may assume that *n* \< 16 and that every component of each point fits in a 32-bit signed integer.

You may write a program or a function. You may take input and give output in any reasonable format. You may optionally pass *n* as a separate argument, instead of having to deduce it.

You must implement an algorithm to compute the geometric median, and not brute force over the output domain.

Examples:

```
(5), (14), (10), (7)                         -> any 7 <= x <= 10 is valid
(2, 3), (8, 4), (12, -3), (0, 0), (0, 0)     -> (2.17, 1.29)
(0, 0, 3), (20, 7, 3), (13, 14, 15)          -> (13.18, 7.94, 7.23)
(2, 20, 3, 30), (20, 2, 20, 2), (1, 2, 3, 4) -> (5.46, 5.12, 6.84, 8.06)

```

The answer is only unique if the set of points do not lie on a line. If the answer is not unique, you may return any valid answer.

# Answer
# Matlab, ~~77~~ 75

I just use the definition of the geometric median with a numerical minimization. In this case I make use of the Nelder-Mead simplex algorithm. It sould always converge as we try to find the minimum of a convex function (according to Wikipedia).

```
n=@(m)trace((m'*m).^.5);f=@(m)fminsearch(@(y)n(bsxfun(@minus,m,y)),m(:,1))

```

Old version: n=@(m)sum(diag(m'\*m).^.5);f=@(m)fminsearch(@(y)n(bsxfun(@minus,m,y)),m(:,1))

The input format is a matix with the input vectors as columns, e.g:

```
m = [[2; 20; 3; 30],[20; 2; 20; 2],[1; 2; 3; 4]];

```
> 1 votes

---
Tags: code-golf, geometry
---


title: A backwards relationship

text:
# Question
Title: A backwards relationship
Write a program or function that, given two ASCII strings `A` and `B`, will produce strings `A'` and `B'` where the common substrings are reversed in their place. The process for finding `A'` is as follows:

1. `A'` is initially empty.
2. If the first character of `A` is in `B`, find the longest prefix of `A` which is a substring of `B`. Remove this prefix from `A` and add its reversal to `A'`.
3. Otherwise, remove this first character from `A` and add it to `A'`.
4. Repeat steps 2-3 until `A` is empty.

Finding `B'` is done similarly.

## Example

Let's consider the strings `A = "abc bab"` and `B = "abdabc"`. For `A'`, this is what happens:

* `A = "abc bab"`: The first character `"a"` is in B and the longest prefix of A found in B is `"abc"`. We remove this prefix from A and add its reversal `"cba"` to A'.
* `A = " bab"`: The first character `" "` is not in B, so we remove this character from A and add it to A'.
* `A = "bab"`: The first character `"b"` is in B and the longest prefix of A found in B is `"b"`. We remove this prefix from A and add its reversal (which is still `"b"`) to A'.
* `A = "ab"`: The first character `"a"` is in B and the longest prefix of A found in B is `"ab"`. We remove this prefix from A and add its reversal `"ba"` to A'.
* `A = ""`: A is empty, so we stop.

Thus we get `A' = "cba" + " " + "b" + "ba" = "cba bba"`. For B', the process is similar:

```
B = "abdabc"  ->  "a" in A, remove prefix "ab"
B = "dabc"    ->  "d" not in A, remove "d"
B = "abc"     ->  "a" in A, remove prefix "abc"

```

Thus we get `B' = "ba" + "d" + "cba" = "badcba"`.

Finally, we return the two strings, i.e.

```
(A', B') = ("cba bba", "badcba")

```

## Test cases

```
"abc bab", "abdabc" -> "cba bba", "badcba"
"abcde", "abcd bcde" -> "dcbae", "dcba edcb"
"hello test", "test banana" -> "hello tset", "tset banana"
"birds flying high", "whistling high nerds" -> "bisdr flyhgih gni", "wihstlhgih gni nesdr"

```

---

Shortest code in bytes wins.

# Answer
# Pyth, 29 bytes

```
M&G+_Je|f}TH._GhGg.-GJHgzQgQz

```

Test Harness.

Input format is:

```
abc bab
"abdabc"

```

Output is:

```
cba bba
badcba

```
> 1 votes

# Answer
## Haskell, ~~120~~ 111 bytes

```
import Data.List
a&b=(a#b,b#a)
[]#_=[]
(a:y)#b=[a]%y where p%(i:w)|reverse(i:p)`isInfixOf`b=(i:p)%w;p%x=p++x#b

```

Test runs:

```
λ: "abc bab"&"abdabc"
("cba bba","badcba")

λ: "abcde"&"abcd bcde"
("dcbae","dcba edcb")

λ: "hello test"&"test banana"
("hello tset","tset banana")

λ: "birds flying high"&"whistling high nerds"
("bisdr flyhgih gni","wihstlhgih gni nesdr")

```
> 2 votes

# Answer
# SWI-Prolog, 312 bytes

```
a(A,B,X,Y):-b(A,B,"",X),b(B,A,"",Y).
b(A,B,R,Z):-A="",R=Z;sub_string(A,0,1,_,C),(sub_string(B,_,1,_,C),(string_length(A,J),I is J-1,between(0,I,K),L is J-K,sub_string(A,0,L,_,S),sub_string(B,_,L,_,S),string_codes(S,E),reverse(E,F),string_codes(Y,F));S=C,Y=C),string_concat(S,V,A),string_concat(R,Y,X),b(V,B,X,Z).

```

Example: `a("birds flying high","whistling high nerds",X,Y).` outputs

```
X = "bisdr flyhgih gni",
Y = "wihstlhgih gni nesdr" .

```

A way, *way* too long solution that goes too show how verbose Prolog is when dealing with strings. It might be possible to shorten this thing using codes arrays (``birds flying high``) instead of strings (`"birds flying high"`).
> 1 votes

# Answer
## Python 2.7, ~~169~~ ~~156~~ ~~152~~ 141 Bytes

```
m=lambda A,B:(b(A,B),b(B,A))
def b(A,B,C=''):
 while A:j=next((j for j in range(len(A),0,-1)if A[:j]in B),1);C+=A[:j][::-1];A=A[j:]
 return C

```

The function `m` takes the 2 strings as input.It calls the `b` function twice which does the actual processing according to the specs.
Demo here.
Testing it -

```
l=[("abc bab", "abdabc"),
("abcde", "abcd bcde"),
("hello test", "test banana"),
("birds flying high", "whistling high nerds")]
for e in l:
    print m(*e)

```

OUTPUTS:

```
('cba bba', 'badcba')
('dcbae', 'dcba edcb')
('hello tset', 'tset banana')
('bisdr flyhgih gni', 'wihstlhgih gni nesdr')

```

PS: Thanks to orlp for the solution using `next()`
> 1 votes

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


title: Golfing strings in Fourier

text:
# Question
Title: Golfing strings in Fourier
## Challenge

Given a string as input, golf down the Fourier program which outputs that string.

In Fourier there is no easy way to output a string: you have to go through each character code and output that as a character.

## Fourier

The language is based upon an accumulator, a global variable which is initialised to 0 at the start of the program. This is used by almost every operator in the language. Only some do not change the value of the accumulator.

### Character out

```
a

```

Takes the value of the accumulator as the ASCII code and outputs the character. Does not change the value of the accumulator.

If the accumulator is greater than 255, the program will return an error. Likewise if the accumulator is less than 0.

### Number out

```
o

```

Outputs the value of the accumulator. Does not change the value of the accumulator.

### Increase

```
^

```

Increase the accumulator by one.

### Decrease

```
v

```

Decrease the accumulator by one.

### Add

```
+x

```

Sets the accumulator to the value of the accumulator plus the value of x.

### Subtract

```
-x

```

Sets the accumulator to the value of the accumulator minus the value of x.

### Multiply

```
*x

```

Sets the accumulator to the value of the accumulator multiplied by the value of x.

### Divide

```
/x

```

Sets the accumulator to the value of the accumulator divided by the value of x. (Note that this is integer division, so `1/6` results in `0`)

### Number

```
n

```

Set the accumulator to the integer n.

### Note

Here, `x` and `n` can be any integer from `0` to `2^32-1` inclusive.

## More information

You must only use the operators described above. Therefore your outputted Fourier program is invalid if it uses any of the following (note that the following operators are allowed for the bounty):

* Repeat loops
* If statements
* Variables
* Random
* Modulo
* User Input
* Greater/Less than operators
* Equality operators
* Clear screen
* Time delay
* Date functions

Your program can either be a full program or a function, taking in input via STDIN, a file or function arguments. You may also take input straight from the Internet.

Note that if there is a `vv` in your code, you should replace it with `-2`. The same goes for `^^`, replacing it with `+2`.

## Examples

If the input is `7n`, then the expected program is:

```
55a110a

```

But you can save one byte with

```
55a*2a

```

Another way is

```
7o110a

```

Using number out.

---

Similarly if the input is `Hello`, then the expected program is:

```
72a101a108a108a111a

```

You can golf it down by 3 bytes (because outputting doesn't change the accumulator):

```
72a101a108aa111a

```

But wait, we can use the addition operator, saving 2 bytes:

```
72a101a+7aa+3a

```

## Formatting

Because I'll be using Martin Büttner's Stack Snippet leaderboard, please could you format the title like so:

```
# <Language name>, <length of total output> bytes

```

Then, you can put anything you wish below the title.

## Winning

You should post the length of Fourier programs (produced by your code) to output this text file and this text file. Your score is the combined length of both Fourier programs in bytes (non-ASCII characters aren't used in Fourier so it doesn't really make a difference).

The person with the lowest scores wins. If there is a tie, the shortest program in bytes wins.

## Bounty

This 500 rep bounty is for a *new* answer which golfs the strings using any of Fourier's functions. That includes variables, loops and if statements etc. This new answer will not be accepted.

## Leaderboard

Refer to formatting section above:

```
var QUESTION_ID=55384;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),e.has_more?getAnswers():process()}})}function shouldHaveHeading(e){var a=!1,r=e.body_markdown.split("\n");try{a|=/^#/.test(e.body_markdown),a|=["-","="].indexOf(r[1][0])>-1,a&=LANGUAGE_REG.test(e.body_markdown)}catch(n){}return a}function shouldHaveScore(e){var a=!1;try{a|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(r){}return a}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading),answers.sort(function(e,a){var r=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0],n=+(a.body_markdown.split("\n")[0].match(SIZE_REG)||[1/0])[0];return r-n});var e={},a=1,r=null,n=1;answers.forEach(function(s){var t=s.body_markdown.split("\n")[0],o=jQuery("#answer-template").html(),l=(t.match(NUMBER_REG)[0],(t.match(SIZE_REG)||[0])[0]),c=t.match(LANGUAGE_REG)[1],i=getAuthorName(s);l!=r&&(n=a),r=l,++a,o=o.replace("{{PLACE}}",n+".").replace("{{NAME}}",i).replace("{{LANGUAGE}}",c).replace("{{SIZE}}",l).replace("{{LINK}}",s.share_link),o=jQuery(o),jQuery("#answers").append(o),e[c]=e[c]||{lang:c,user:i,size:l,link:s.share_link}});var s=[];for(var t in e)e.hasOwnProperty(t)&&s.push(e[t]);s.sort(function(e,a){return e.lang>a.lang?1:e.lang<a.lang?-1:0});for(var o=0;o<s.length;++o){var l=jQuery("#language-template").html(),t=s[o];l=l.replace("{{LANGUAGE}}",t.lang).replace("{{NAME}}",t.user).replace("{{SIZE}}",t.size).replace("{{LINK}}",t.link),l=jQuery(l),jQuery("#languages").append(l)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/,NUMBER_REG=/\d+/,LANGUAGE_REG=/^#*\s*([^,]+)/;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script><link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"><div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table></div> <tbody id="languages"> </tbody> </table></div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody></table>
```

# Answer
# Python, 14307118 bytes

### 601216 for Hamlet + 13705902 for Genesis = 14307118

There are definitely some senarios under which this solution is not optimal, such as for `1111`, where it will output `1111o` as opposed to `11oo`. However, I think it is nearly optimal.

Edit: Saved a few bytes by improving `0o0o` to `0oo`.

The name of the file containing the input is received on STDIN, output to STDOUT.

Results verified with the official interpreter.

```
def opt_str(char, acc):
    opts = []
    char_num = ord(char)
    opts.append(str(char_num))
    if 0 < char_num - acc < 10:
        opts.append('+' + str(char_num - acc))
    if 0 < acc - char_num < 10:
        opts.append('-' + str(acc - char_num))
    if char_num - acc == 1:
        opts.append('^')
    if acc - char_num == 1:
        opts.append('v')
    if acc == char_num:
        opts.append('')
    if acc and char_num % acc == 0:
        opts.append('*' + str(char_num//acc))
    try:
        if acc // (acc // char_num) == char_num:
            opts.append('/' + str(acc // char_num))
    except:
        pass
    return [opt for opt in opts if len(opt) == len(min(opts, key=len))]

acc = 0
result = []
pos = 0
with open(input(), "r") as myfile:
        in_str = myfile.read()
while pos < len(in_str):
    i = in_str[pos]
    pos += 1
    if i in '0123456789':
        if i != '0':
            while pos < len(in_str) and in_str[pos] in '0123456789':
                i += in_str[pos]
                pos += 1
        if i == str(acc):
            result.append('o')
        else:
            result.append(i + 'o')
        acc = int(i)
    else:
        opts = opt_str(i, acc)
        result.append(opts[0] + 'a')
        acc = ord(i)
print(''.join(result))

```
> 9 votes

# Answer
# \>\<\>, 14310665 bytes

## 601398 for hamlet + 13709267 for genesis

This is still a work in progress and takes a lot of time to complete.

```
v
0
>i:0(?;:r-:?!v:0a-)?v     v
  >~:v       ~      >:a(?v>
 :1+?v~'v'o  v      o'^'~\:0)?v
     >n      vno'+'      ^?=1:<
^        o'a'<

```
> 13 votes

# Answer
# Java, 14307140 bytes

### Hamlet - 601,218

### Genesis - 13,705,922

The idea here is to do all the work upfront, by making a character-\>character map. Then you can just loop through and grab the shortest strings.

A bit of an exception has to be made for numerals, so I check for them in the main loop. It's still fast, though, and handles the larger test case in a few seconds. I *may* be able to tweak this section for a couple more bytes, but I'm fairly sure it's close to optimum.

Input is a filename as argument. Output is written to a file `inputFilename_out.4`, and the character count is sent to STDOUT.

This is 1737 bytes for the tiebreaker, completely ungolfed. I can golf it a lot if needed, but it's still going to be a bit big.

```
import java.nio.file.Files;
import java.nio.file.OpenOption;
import java.nio.file.Paths;
import java.text.NumberFormat;

public class FourierMapper {
    public static void main(String[] args) throws Exception {
        FourierMapper fm = new FourierMapper();
        fm.createMap();
        String filename = args.length>0? args[0]:"bible.txt";
        String out = fm.fourierize(filename);
        System.out.println(out.length());
        Files.write(Paths.get(filename + "_out.4"), out.getBytes(), new OpenOption[]{});
    }

    String[][] map = new String[9999][256];
    void createMap(){
        for(int from=0;from<9999;from++){
            for(int to=0;to<256;to++){
                if(to<10||from<1){
                    map[from][to] = ""+to;
                } else if(to==from){
                    map[from][to] = "";
                } else if(to-from==1){
                    map[from][to] = "^";
                } else if(to-from==-1){
                    map[from][to] = "v";
                } else if(to>99){
                    if(to%from<1){
                        map[from][to] = "*"+(to/from);
                    } else if(to>from&&to-from<10){
                        map[from][to] = "+"+(to-from);
                    } else if(from>to&&from-to<10){
                        map[from][to] = "-"+(from-to);
                    } else {
                        map[from][to] = ""+to;
                    }
                } else {
                    map[from][to] = ""+to;
                }
            }
        }
    }

    String fourierize(String filename) throws Exception{
        StringBuilder out = new StringBuilder();
        byte[] in = Files.readAllBytes(Paths.get(filename));
        String whole = new String(in);
        out.append(in[0] + "a");
        int number = -1;
        for(int i=1;i<in.length;){
            if(in[i]<58&&in[i]>47){
                number = in[i]==48?0:((Number)NumberFormat.getInstance().parse(whole.substring(i,i+4))).intValue();
                out.append(""+number+"o");
                i += (""+number).length();
            } else {
                if(number<0)
                    out.append(map[in[i-1]][in[i]]+"a");
                else
                    out.append(map[number][in[i]]+"a");
                number = -1;
                i++;
            }
        }
        return out.toString();
    }

}

```
> 8 votes

# Answer
# PHP, 14307118 bytes

## 601,216 (Hamlet) + 13,705,902 (Bible)

```
function f($file) {
    $text = file_get_contents($file);

    $a = 0;

    for ($i = 0; $i < strlen($text); $i++) {
        $chr = $text[$i];

        if (ctype_digit($chr)) {
            while ($chr && isset($text[$i + 1]) && ctype_digit($text[$i + 1])) {
                $chr .= $text[$i + 1];
                $i++;
            }

            if ($a == (int)$chr) {
                print "o";
            }
            else {
                $a = (int)$chr;
                print $chr . "o";
            }

            continue;
        }

        $ord = ord($chr);

        $mapping = array(
            '' => $a,
            '^' => $a + 1,
            'v' => $a - 1
        );

        for ($j = 2; $j <= 9; $j++) {
            $mapping["+$j"] = $a + $j;
            $mapping["-$j"] = $a - $j;
            $mapping["*$j"] = $a * $j;
            $mapping["/$j"] = $a / $j;
        }

        foreach ($mapping as $op => $value) {
            if ($value === $ord) {
                $a = $value;
                print $op . "a";
                continue 2;
            }
            else if ($value . '' === $chr) {
                $a = $value;
                print $op . "o";
                continue 2;
            }
        }

        $a = $ord;
        print $ord . "a";
    }
}

```

Fourier output for Hamlet

It works as follows:

1. Iterates over each character in the input;
2. If there is a sequence of non 0 leading digits it will set the accumulator to that number and output it as number. It also checks for similar digits;
3. Otherwise, checks if there is shorter way of outputting the current character (rather than the ASCII code + "a" symbol = 4 characters) by performing a basic operation (+-\*/) on the accumulator with a number between 2 and 9; obviously, it also tries to compare/increment/decrement;
> 2 votes

---
Tags: code-challenge, metagolf
---


title: Enumerate valid Brainf**k programs

text:
# Question
Title: Enumerate valid Brainf**k programs
Golunar/Unary is a way to encode all valid Brainfuck programs, but it is not an enumeration, since most natural numbers do not correspond to a valid program.

For the purpose of this challenge, assume a doubly infinite tape and no comments, i.e., a Brainfuck program is valid if and only if it consists solely of the characters `<>+-.,[]` and all left and right brackets match.

For example, the empty program, `,[+][-].`, `[>+<[--].]` and `+[+[+][+[+]+]+]+.` are valid Brainfuck programs, while `][`, and `a[]` are not.

### Task

Write a program or function that accepts a valid Brainfuck program as input and returns a natural number (**1**, **2**, **3**, …), with the following constraints:

* The generated output must be different for all valid Brainfuck programs.
* For every natural number **n**, there must be a valid Brainfuck program that, when provided as input, generates the output **n**.

### Additional rules

* Given a Brainfuck program of 100 or less bytes, your program or function must finish within one minute.

This means that you cannot iterate over all valid Brainfuck programs until you match the input.
* Standard rules apply.

# Answer
> 16 votes
# Python 3, ~~443~~ ~~158~~ ~~155~~ ~~154~~ ~~134~~ ~~131~~ ~~128~~ ~~124~~ ~~117~~ ~~116~~ 115 bytes

```
c=d=C=D=0
for e in input():v='[<>,.-+]'.find(e);d=d*8+v;c+=c<0<6<v;c-=d>1>v;C,D=(c,C+1,d,D)[v>6::2]
print(-~D*8**C)

```

Several bytes thanks to Sp3000 and Mitch Schwartz :D

## How this works:

This maps all valid BF programs into all possible, valid or invalid, BF programs, that don't start with a `[`, in a one-to-one ratio. After that, the new program is simply converted into octal.

**Here is the mapping formula:**

1. Separate a BF program into 3 parts. The first part is the largest prefix consisting of only `[` characters. The third part is the largest postfix consisting of only `]` characters. The second part is the middle.
2. Dispose of the first part. These can be recomputed later.
3. Remove all `]` brackets in the third part that match `[` brackets in the second part. These can also be recomputed later.
4. Concatenate the second and third parts together.

If you don't understand this explanation, you can find an extended explanation in chat starting here.

**For reference, here are the first 20 programs:**

```
1 :
2 : <
3 : >
4 : ,
5 : .
6 : -
7 : +
8 : []
9 : <[]
10 : <<
11 : <>
12 : <,
13 : <.
14 : <-
15 : <+
16 : [<]
17 : >[]
18 : ><
19 : >>
20 : >,

```

Here are the first 1000 programs: http://pastebin.com/qykBWhmD
Here is the program I used to generate them: http://ideone.com/e8oTVl

**Here is `Hello, World!`:**

```
>>> ++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.
457711481836430915510337664562435564418569135809989841510260388418118348571803953323858180392373

```

# Answer
> 13 votes
# Python 2, 157 bytes

```
def f(s,o=0,d=0,D={}):T=s,o,d;x=D[T]=D[T]if T in D else~o and 0**o+sum(f(s[1:],cmp(c,"[")%-3-~o,d or cmp(c,s[0]))for c in"+,-.<>[]")if s else~d<0==o;return+x

```

Still looks pretty golfable, but I'm posting this for now. It uses recursion with a bit of caching. Annoyingly, `D.get` doesn't short circuit for the caching, so I can't save 9 bytes that way...

The mapping prioritises length first, then lexicographical order over the ordering `"][><.-,+"` (see output examples below). The main idea is to compare prefixes.

The variable `o` keeps track of the number of `[` brackets still open for the current prefix, while the variable `d` takes one of three values indicating:

* `d = 1`: The current prefix is lexicographically earlier than `s`. Add all programs with this prefix and length `<= s`,
* `d = -1`: The current prefix is lexicographically later than `s`. Add all programs with this prefix and length `< s`.
* `d = 0`: The current prefix is a prefix of `s`, so we might change `d` to 1 or -1 later.

For example, if we have `s = "[-]"` and our current prefix is `p = "+"`, since `p` is later than `s` lexicographically we know only to add the programs starting with `p` which are strictly shorter than `s`.

To give a more detailed example, suppose we have an input program `s = "-[]"`. The first recursive expansion does this:

```
  (o == 0)               # Adds a program shorter than s if it's valid
                         # For the first expansion, this is 1 for the empty program
+ f(s[1:], o=-1, d=1)    # ']', o goes down by one due to closing bracket
+ f(s[1:], o=1, d=1)     # '[', o goes up by one due to opening bracket
+ f(s[1:], o=0, d=1)     # '>'
+ f(s[1:], o=0, d=1)     # '<'
+ f(s[1:], o=0, d=1)     # '.', d is set to 1 for this and the previous branches
                         # since they are lexicographically earlier than s's first char
+ f(s[1:], o=0, d=0)     # '-', d is still 0 since this is equal to s's first char
+ f(s[1:], o=0, d=-1)    # ',', d is set to -1 for this and the later branches
                         # since they are lexicographically later than s's first char
+ f(s[1:], o=0, d=-1)    # '+'

```

Note how we don't actually use the prefixes in the recursion - all we care about them is captured through the variables `d`, `o` and the shrinking input program `s`. You'll notice a lot of repetition above - this is where caching comes in, allowing us to process 100-char programs well within the time limit.

When `s` is empty, we look at `(d>=0 and o==0)`, which decides whether to return 1 (count this program because it's lexicographically early/equal and the program is valid), or 0 (don't count this program).

Any situtation with `o < 0` immediately returns `0`, since any programs with this prefix have more `]`s than `[`, and are thus invalid.

---

The first 20 outputs are:

```
 1
> 2
< 3
. 4
- 5
, 6
+ 7
[] 8
>> 9
>< 10
>. 11
>- 12
>, 13
>+ 14
<> 15
<< 16
<. 17
<- 18
<, 19
<+ 20

```

Using the same Hello World example as @TheNumberOne's answer:

```
>>> f("++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.")
3465145076881283052460228065290888888678172704871007535700516169748342312215139431629577335423L

```

# Answer
> 5 votes
This answer is a formal proof for the answer by TheNumberOne, Enumerate valid Brainf\**k programs, where it can be a bit hard to understand the fine points why the enumeration is correct. It's nontrivial to understand why there isn't some invalid program that maps to a number not covered by a valid program.

Throughout this answer capitals are used to denote programs, and lowercase variables are used for functions and integers. ~ is the concatenation operator.

***Proposition 1:***

*Let the function f be the program described in that answer. Then for every program U there exists a valid program V such that f(U) = f(V)*

**Definition 1:**

Let g(X) be the number of `[` that appear in the program X, and let h(X) be the number of `]` that appear.

**Definition 2:**

Define P(x) to be this function:

```
P(x) = "" (the empty program) when x <= 0
P(x) = "]" when x = 1
P(x) = "]]" when x = 2
etcetera

```

**Definition 3:**

Given a program X, denote X1 to be it's largest prefix of `[` characters, X2 its center, and X3 its largest suffix of `]` characters.

**Proof of proposition 1:**

If g(U) = h(U) then U is a valid program, and we can take V=U. (trivial case).

If g(U) \< h(U) then we can create V by prepending n = h(U) - g(U) `[` symbols. Obviously f(V) = f(U) as all `[` symbols in the prefix are removed.

Now consider g(U) \> h(U). Define T = U2 ~ U3. if g(T) \<= h(T), then we can construct V by removing n = g(U) - h(U) `[` symbols.

So we can assume that h(T) \< g(T). Construct V = T ~ P(g(T) - h(T)).

We need three small facts to proceed:

*Claim 1:* g(U2) = g(T)

U3 does not contain any `[` symbols by its definition. As T = U2 ~ U3, its `[` symbols are all in the first part.

*Claim 2:* h(U3) \< g(T)

This follows from noting that h(T) \< g(T) and h(U3) \< h(U3 ~ U2) = h(T).

*Claim 3:* h(V3) = g(U2) - h(U2)

```
h(V3) = h(U3) + g(T) - h(T)                           using the construction of V
h(V3) = h(U3) + g(U2) + g(U3) - h(U2) - h(U3)         apply the definition of T
h(V3) = g(U2) - h(U2) *one term cancels, g(U3)        is always zero, as U3 contains only `]` symbols*

```

Now we show that f(V) = f(U).

```
f(U) = U2 ~ P(h(U3) - g(U2)) = U2                     claim 2, definition of P

f(V) = U2 ~ P(h(V3) - g(V2))
     = U2 ~ P(h(V3) - g(U2))
     = U2 ~ P(g(U2) - h(U2) - g(U2))                  claim 3
     = U2 ~ P(-h(U2))
     = U2                                             definition P

```

This completes the proof. Q.E.D.

Let's do uniqueness as well.

***Proposition 2:***

*Let U, V be two diffrent, valid programs. Then f(U) != f(V)*

This is fairly straightforward compared to the previous proposition.

Let's assume that U2 = V2. But then the only way U and V can be diffrent is by adding or removing n `[` and `]` symbols to U1 and U3 respectively. Yet this changes the output of f, since f will count the number of unmatched `]` symbols in the suffix.

Thus U2 != V2.

Obviously, this leads to a contradiction. As U2 and V2 are literally contained in the output of f(U) and f(V) respectively, they cannot differ, except at the 'edge', the place where U2 is concatenated with U3. But the first and last symbols of U2 and V2 cannot be `[` or `]` by definition, while those are the only symbols allowed in U1, U3, V1, V3 respectively and respectively again. Thus we get U2 = V2. Q.E.D.

---
Tags: code-golf, balanced-string, brainfuck, restricted-time
---


# Question
Title: Anti-golfscript anti-golf: create a task where GolfScript or J is outgolfed by your (conventional) lang
You need to make three things:

1. Statement of a task, **T**.
2. Solution of the task in language not typically used for golfing, **A**.
3. Solution of the task in language typically used for golfing, **B**. Don't try to just bloat up **B** to pump up the score, instead think as if **B** was written by your competitor.

Use common sense in defining `typically used for golfing`, try to maximize fun for other users.

Other users may propose better `B`s (maybe including in other "golfy" languages).

Scoring is `(length_in_bytes(B)+5)/(length_in_bytes(A)+5)`, more is better. (Maybe the scoring formula should be changed?..)

The main idea is to invent a task where languages that typically perform well in codegolf meet a problem. It can be sudden strength of a usual language in the given task or sudden weakness of some golflang.

Avoid tasks that mention specific programming languages, like `Input a string and execute it as a Scheme code`.

# Answer
My previous question, Print a sinusoidal wave (vertically), qualifies at this moment. I'm posting it here as a solution, also hoping that you guys can come up with some shorter solutions to my original question.

As required by Vi., I will post a summary of the question.

Print a continuous sinusoidal wave scrolling vertically on a terminal. The program should not terminate and should continuously scroll down the wave (except until SIGINT). You may assume overflow is not a problem (i.e. you may use infinite loops with incrementing counters, or infinite recursion).

The wave should satisfy the following properties:

* Amplitude = 20 chars (peak amplitude)
* Period = 60 to 65 lines (inclusive)
* The output should only consist of spaces, newline and `|`
* After each line of output, pause for 50ms

There is a sample output on my original question, but I'm not posting it here, because this will make my answer ridiculously long. My original question can be seen here: Print a sinusoidal wave (vertically)

Shortest `A` currently: a Perl solution with 48 chars: https://codegolf.stackexchange.com/a/18655/12205

```
print$"x(25+20*sin).'|
';$_+=.1;`sleep .05`;do$0

```

Shortest `B` currently: a J solution with 54 chars: https://codegolf.stackexchange.com/a/18649/12205

```
($:+&0.1[6!:3@]&0.05[2:1!:2~' |'#~1,~[:<.20*1+1&o.)0

```

Currently, the score of this answer is 1.113 (an awfully low score)
> 14 votes

# Answer
# Add two numbers

Get two numbers from STDIN, and add them together. You have to support floating point numbers, so 0.5 + 1.5 has to equal 2.

## Perl 5 (with `-E`)

```
say<>+<>

```

## GolfScript

```
n%'+'*'"#{
}"'n/\*~

```
> 8 votes

# Answer
# Print 'Hello, World!' to the stdout.

PHP, 13 bytes

```
Hello, World!

```

Golfscript, 15 bytes

```
'Hello, World!'

```

Pyth, 14 bytes

```
"Hello, World!

```
> 8 votes

# Answer
## Score 48/37 or 1.(297)

T: write a code snippet that ends the program after exactly one hour (as close as possible, like within a second) of running. Don't worry about exceptions, they can be unhandled.

A: Java (32)

```
Thread.sleep(3600000);int a=1/0;

```

B: is for Befunge 98, requires the TIME fingerprint (43)

```
"EMIT"4(HMS00p01p02p#;gS-!01gM-!H-!++3-!j;@

```

This takes the Hour, Minute, and Second at the time of running, and puts the at cells 02, 01, and 00. Then, it skips over the `;` to the second part. The second part works as follows:

```
g          get the value at 00
"EMIT"4(S) get the current time in seconds
-!         subtracts the values and changes a 0 to 1, anything else to 0

```

similarly for the Minute and Hour.

```
++  sums up the values
3-! i the sum is 3, we get a 1, otherwise, we get a 0.
j   jump over the next that many cells
;   skip code execution until the next ;
@   end program

```

Note that Befunge will automatically go back to the beginning of the line when the end of a line is reached.

---

As we can see, Befunge is not good when it comes to waiting for specific times. However, Java is not bad.
> 7 votes

# Answer
# Output a certain text file (498.388888 points)

The goal output is here.

The Python 3.4.3 script to print it is 49 bytes:

```
for b in dir(__builtins__):print(eval(b).__doc__)

```

The naive CJam program equal to the goal output, by wrapping the output string in `"..."` and escaping each `"` that occurs in it, would be 26908 bytes.
> 5 votes

# Answer
# Say "Hello world!" (50 / 26 ≈ 1.92)

Show a message box to say "Hello world!"

## JavaScript

```
alert('Hello world!')

```

In a browser with support for DOM Level 0+.

## Perl

```
use Win32;Win32::MsgBox('Hello world!','',48)

```

Running on ActivePerl with Win32::GUI.
> 4 votes

# Answer
# Output "Hello world!" until user presses "q", ~~1.842~~ 105/44 = 2.386

1. Print "Hello world!" (including newline).
2. The user presses a key, which is not echoed to the screen.
3. Repeat until the key pressed was "q".

## QBasic (~~52~~ 39 characters)

```
1?"Hello world!":IF"q"<>INPUT$(1)THEN 1

```

Since posting my original answer, I discovered that I could turn off autoformatting in QB64. :^D With the line number and `?` shortcut for `PRINT`, this looks rather like a ternary expression in C-like languages.

First version:

```
PRINT "Hello world!"
IF INPUT$(1) <> "q" THEN RUN

```

## Perl 5 (100 characters)

```
while("q"ne$e){print"Hello world!\n";system"stty cbreak -echo";$e=getc;system"stty -cbreak echo";}

```

The above will only work on (certain?) UNIX systems (tested on Ubuntu 12.04). It's possible that one could go cross-platform and get it down to 91 characters using the Term::ReadKey module, but I haven't tested it:

```
use Term::ReadKey;while("q"ne$e){print"Hello world!\n";ReadMode 3;$e=ReadKey 0;ReadMode 0;}

```
> 3 votes

# Answer
# Hello, world (3 1/3 points)

Write program that outputs `Hello World.`.

## HQ9+ (1 character)

This is not language "typically used for golfing", so I believe it fits here. Works in this interpreter, by the way.

```
H

```

## GolfScript (15 characters)

I doubt it can get any shorter, even if it's GolfScript.

```
"Hello World."

```
> 1 votes

# Answer
## Output "Hello world!", 33/97 = 2.94

Write a program that outputs `Hello world!`

## Arduino or GML

```
Serial.print("Hello world!")

```

or

```
show_message("Hello world!")

```

Both are 28 characters.

## GTB

I use GTB for golfing a lot (especially since I created it myself, and it is Turing complete). Unfortunately, there is only limited support for lowercase characters (because TI-84 calculator can't deal with it). This is probably the shortest GTB program that can output Hello world!

```
S;"lower",1,1)→_~"H"+S;"expr(",1,1)+_+_+S;"cos(",2,1)+" W"+S;" or ",2,2)+_+S;" and ",4,1)+"!

```

92 characters.
> 0 votes

---
Tags: popularity-contest, metagolf, golfscript
---


title: Tips For Golfing In Groovy

text:
# Question
Title: Tips For Golfing In Groovy
As I have seen many questions asking tips for golfing in their interested language, I decided to ask for my favorite language: Groovy. People can give some tips and tricks that will be used in golfing with Groovy.

# Answer
> 5 votes
I'm new to this whole golfing thing, this is what I got so far:

Use Closures not functions:

```
def a(b){print b}

```

is longer than

```
a={print it}

```

You can use a negative index in arrays and lists as an alias for size()-

```
c = "abc"
d = ["a", "b", "c"]

assert c[c.size()-1] == c[-1]
assert c[c.size()-2] == c[-2]
assert d[d.size()-1] == d[-1]
assert d.last() == d[-1]

```

The spread operator is a shortcut for collect:

```
assert d*.size() == d.collect{it.size()}
```

For sorting use the spaceship operator:

```
e = [54,5,12]
assert e.sort{a,b->a<=>b}==e.sort{a,b->a<b?-1:+1}
assert e.sort{a,b->a<=>b}==e.sort{a,b->if (a>b) {return(-1)} else {return(+1)}}

```

Edit Conversions:

```
assert "123" as int == "123".toInteger()

```

# Answer
> 3 votes
As Groovy is a somewhat verbose language, you could use Groovys MOP to shorten method calls.

The following snippet for example would pay off after the fourth usage:

```
''.metaClass.r<<{i->(int)Math.random()*i}
''.r(12)

```

Tip golfing edit:

```
0.metaClass.r<<{i->(int)Math.random()*i}
0.r(12)

```

Or, you know:

```
r={(int)Math.random()*it}
r(12)

```

# Answer
> 2 votes
## `grep` is short and works on several problems

get the chars of a string as a list with spaces and without leading elements: `'ABC XYZ'.grep()` returns `[A, B, C, , X, Y, Z]`

grep with regexp is shorther than converting to upper case, if required: `it.grep(~/(?i)$c/)` instead of `it.toUpperCase().grep(c)`

# Answer
> 2 votes
**Getting An Array from a List of Objects**

If you have a list of objects like:

```
def users = [[user:'A',id:1],[user:'B',id:2],[user:'C',id:3]]

```

You can generate an ArrayList with a certain property using:

```
def userIds = users*.id // [1, 2, 3] no explicit loops!

```

**BONUS: Groovy... on Rails!**

Well, in Grails Framework we must get many values from a select with multiple attribute. You can use loops, flatten and other programming more typical structures, but you can save some lines. If you have a select like:

```
<select id="users" multiple="true" name="users">
    <option value="193">User A</option>
    <option value="378">User B</option>
    <option value="377">User C</option>
</select><%-- No Grails tags for now --%>

```

Then, in your controller you can simple write:

```
def aListOfUsers = User.getAll(params.list('userIds'))

```

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