title: Help our robots reach the teleporter

text:
# Question
Title: Help our robots reach the teleporter
**UPDATE: Added a Python framework to get started.**

The space-station has been overtaken by crusher-bots. You must direct as many of our expensive and fragile tech-bots called "rabbits" to an exit teleporter before the station self-destructs, but the crusher-bots are patrolling the corridors.

Your program is given an ASCII map, and each turn is told where the crusher-bots are and your current rabbits are. Your program should then move your rabbits toward the exit teleporter while avoiding the crusher-bots.

## Execution

Run the Python 2 controller with:

```
python controller.py <mapfile> <turns> <seed> <runs> <prog>...
<prog> can be <interpreter> <yourprog> or similar.

```

The seed is a small integer used for the crusher and your program PRNG so that runs are repeatable. Your program should perform consistently regardless of the actual seed used. If seed is zero, the controller will use a random seed for each run.

The controller will run your program with the name of the map text file and seed as arguments. Eg:

```
perl wandomwabbits.pl large.map 322

```

If your program uses a PRNG, you should initialise it with the given seed. The controller then sends your program updates through STDIN and reads your rabbit movements through STDOUT.

Each turn the controller will output 3 lines:

```
turnsleft <INT>
crusher <x,y> <movesto|crushes> <x,y>; ...
rabbits <x,y> <x,y> ...

```

then waits for the program to output one line:

```
move <x,y> to <x,y>; ...

```

**UPDATE: Your program will have 2 seconds to initialise before the first lines are sent by the controller.**

If your program takes longer than 0.5 seconds to respond with moves after the controller rabbit location input, the controller will exit.

If there are no rabbits on the grid, the rabbits line will have no values, and your program should output a bare "move" string line.

Remember to flush your program output stream each turn or the controller may hang.

## Example

prog input:

```
turnsleft 35
crusher 22,3 crushes 21,3; 45,5 movesto 45,4
rabbits 6,4 8,7 7,3 14,1 14,2 14,3

```

prog output:

```
move 14,3 to 14,4; 14,2 to 14,3; 6,4 to 7,4

```

## Controller logic

The logic for each turn:

* if turns left is zero, print score and exit.
* for each empty start cell, add a rabbit if no crusher in sight.
* for each crusher, decide move direction (see below).
* for each crusher, move if possible.
* if crusher is at a rabbit location, remove rabbit.
* output turnsleft, crusher actions, and rabbit locations to program.
* read rabbit move requests from program.
* if a rabbit not exist or move not possible, skip.
* plot each new location of rabbits.
* if rabbit hits a crusher, rabbit is destroyed.
* if rabbit is in exit teleporter, rabbit is removed and score increased.
* if rabbits collide, they are both destroyed.

Each crusher always has a heading direction (one of NSEW). A crusher follows this navigation logic each turn:

* If one or more rabbits are visible in any of 4 orthogonal directions, change direction to one of the closest rabbits. Note that crushers cannot see past another crusher.
* else choose randomly between open forward,left,right options if possible.
* else if obstacles (wall or other crusher) in front, left, *and* right, set direction to behind.

Then for each crusher:

* If there is no obstacle in new crusher direction, move (and possibly crush).

## The map symbols

The map is a rectangular grid of ASCII characters. The map is made up of walls `#`, corridor spaces , rabbit start positions `s`, exit teleporters `e`, and crusher starting locations `c`. The top left corner is location (0,0).

## Small map

```
###################
#        c        #
# # ######## # # ##
# ###s    #  ####e#
#   # # # ## ##   #
### # ###  # ## # #
#         ##      #
###################

```

## Test map

```
#################################################################
#s                       ############################          s#
## ## ### ############ # #######                ##### ####### ###
## ## ### #            # ####### ########## # # ####   ###### ###
## ## ### # ############ ####### ##########     ##### ####### ###
## ## ##  #              ####### ########## # # ##### ####      #
##    ### #### #### ########     ##########     ##### #### ## ###
######### ####      ######## ################ ####### ####    ###
#########  ################# ################   c     ####### ###
######### ##################          ####### ####### ###########
######### ################## ######## #######         ###########
##### ###   c                          ###### ###################
#         #### ### # # # # # # # # # # ###### ##############    #
# ####### ####                         ###    ####     ##### ## #
#         #### ### # # # # # # # # # # ### # ###   #########    #
##### ### #### ###                   #####   ### #  ######## ####
############## ### # # # # # # # # # # #######   ##  ####### ####
#### #### #### ###                     ###   # # ###  ###### ####
##             ### # # # # # # # # # # ### ### #  ###  ##### ####
##### ######## ### # # # ##### # # # # ### ### # #####  #### ####
##### ##### ######         c   #       ### ###   ######  ### ####
##       c   ######################### ### ##### ####### ### ####
##### # ### #######   ########         ### ##### c  ##    ## ####
#####   #   ####### ########## ## ######## #     ######## ## ####
######### # #######            ## #     ## # # # #####     # ####
### ##### #     ### # ############## # ### #      ###  ## #  ####
#      ## # ### ### # ############## # ### ##### #####    ## ####
### ## ## #     ###                  #           ########       #
#s  ##      ###################################################e#
#################################################################

```

## Example large map run

## Score

To evaluate your program, run the controller with the test map, 500 turns, 5 runs, and seed of 0. Your score is the total number of rabbits successfully teleported off the station to safety. In the event of a tie, the answer with the most votes will win.

Your answer should include a title with entry name, language used, and score. In the answer body, please include the controller score output complete with seed numbers so that others can repeat your runs. For example:

```
Running: controller.py small.map 100 0 5 python bunny.py
   Run                 Seed      Score
     1                  965          0
     2                  843          6
     3                  749         11
     4                  509         10
     5                  463          3
Total Score: 30

```

You can use standard and freely available libraries but the standard loopholes are forbidden. You must not optimise your program for a given seed, turn count, map feature set, or other parameters. I reserve the right to change the map, turn count, and seed if I suspect a violation of this rule.

## Controller code

```
#!/usr/bin/env python
# Control Program for the Rabbit Runner on PPCG.
# Usage: controller.py <mapfile> <turns> <seed> <runs> <prog>...
# Tested on Python 2.7 on Ubuntu Linux. May need edits for other platforms.
# v1.0 First release.
# v1.1 Fixed crusher reporting bug.
# v1.2 Control for animation image production.
# v1.3 Added time delay for program to initialise

import sys, subprocess, time, re, os
from random import *

# Suggest installing Pillow if you don't have PIL already
try:
    from PIL import Image, ImageDraw
except:
    Image, ImageDraw = None, None
GRIDLOG = True      # copy grid to run.log each turn (off for speed)
MKIMAGE = False     # animation image creation (much faster when off)
IMGWIDTH = 600      # animation image width estimate
INITTIME = 2        # Allow 2 seconds for the program to initialise

point = complex     # use complex numbers as 2d integer points
ORTH = [1, -1, 1j, -1j]     # all 4 orthogonal directions

def send(proc, msg):
    proc.stdin.write((msg+'\n').encode('utf-8'))
    proc.stdin.flush()

def read(proc):
    return proc.stdout.readline().decode('utf-8')

def cansee(cell):
    # return a dict of visible cells containing robots with distances
    see = {}    # see[cell] = dist
    robots = rabbits | set(crushers)
    if cell in robots:
        see[cell] = 0
    for direc in ORTH:
        for dist in xrange(1,1000):
            test = cell + direc*dist
            if test in walls:
                break
            if test in robots:
                see[test] = dist
                if test in crushers:
                    break       # can't see past them
    return see

def bestdir(cr, direc):
    # Decide in best direction for this crusher-bot
    seen = cansee(cr)
    prey = set(seen) & rabbits
    if prey:
        target = min(prey, key=seen.get)    # Find closest
        vector = target - cr
        return vector / abs(vector)
    obst = set(crushers) | walls
    options = [d for d in ORTH if d != -direc and cr+d not in obst]
    if options:
        return choice(options)
    return -direc

def features(fname):
    # Extract the map features
    walls, crusherstarts, rabbitstarts, exits = set(), set(), set(), set()
    grid = [line.strip() for line in open(fname, 'rt')]
    grid = [line for line in grid if line and line[0] != ';']
    for y,line in enumerate(grid):
        for x,ch in enumerate(line):
            if ch == ' ': continue
            cell = point(x,y)
            if ch == '#': walls.add(cell)
            elif ch == 's': rabbitstarts.add(cell)
            elif ch == 'e': exits.add(cell)
            elif ch == 'c': crusherstarts.add(cell)
    return grid, walls, crusherstarts, rabbitstarts, exits

def drawrect(draw, cell, scale, color, size=1):
    x, y = int(cell.real)*scale, int(cell.imag)*scale
    edge = int((1-size)*scale/2.0 + 0.5)
    draw.rectangle([x+edge, y+edge, x+scale-edge, y+scale-edge], fill=color)

def drawframe(runno, turn):
    if Image == None:
        return
    scale = IMGWIDTH/len(grid[0])
    W, H = scale*len(grid[0]), scale*len(grid)
    img = Image.new('RGB', (W,H), (255,255,255))
    draw = ImageDraw.Draw(img)
    for cell in rabbitstarts:
        drawrect(draw, cell, scale, (190,190,255))
    for cell in exits:
        drawrect(draw, cell, scale, (190,255,190))
    for cell in walls:
        drawrect(draw, cell, scale, (190,190,190))
    for cell in crushers:
        drawrect(draw, cell, scale, (255,0,0), 0.8)
    for cell in rabbits:
        drawrect(draw, cell, scale, (0,0,255), 0.4)
    img.save('anim/run%02uframe%04u.gif' % (runno, turn))

def text2point(textpoint):
    # convert text like "22,6" to point object
    return point( *map(int, textpoint.split(',')) )

def point2text(cell):
    return '%i,%i' % (int(cell.real), int(cell.imag))

def run(number, nseed):
    score = 0
    turnsleft = turns
    turn = 0
    seed(nseed)
    calltext = program + [mapfile, str(nseed)]
    process = subprocess.Popen(calltext,
            stdin=subprocess.PIPE, stdout=subprocess.PIPE, stderr=errorlog)
    time.sleep(INITTIME)
    rabbits.clear()
    crushers.clear()
    crushers.update( dict((cr, choice(ORTH)) for cr in crusherstarts) )

    while turnsleft > 0:
        # for each empty start cell, add a rabbit if no crusher in sight.
        for cell in rabbitstarts:
            if cell in rabbits or set(cansee(cell)) & set(crushers):
                continue
            rabbits.add(cell)
        # write the grid to the runlog and create image frames
        if GRIDLOG:
            for y,line in enumerate(grid):
                for x,ch in enumerate(line):
                    cell = point(x,y)
                    if cell in crushers: ch = 'X'
                    elif cell in rabbits: ch = 'o'
                    runlog.write(ch)
                runlog.write('\n')
            runlog.write('\n\n')
        if MKIMAGE:
            drawframe(number, turn)
        # for each crusher, decide move direction.
        for cr, direc in crushers.items():
            crushers[cr] = bestdir(cr, direc)
        # for each crusher, move if possible.
        actions = []
        for cr, direc in crushers.items():
            newcr = cr + direc
            if newcr in walls or newcr in crushers:
                continue
            crushers[newcr] = crushers.pop(cr)
            action = ' movesto '
            # if crusher is at a rabbit location, remove rabbit.
            if newcr in rabbits:
                rabbits.discard(newcr)
                action = ' crushes '
            actions.append(point2text(cr)+action+point2text(newcr))
        # output turnsleft, crusher actions, and rabbit locations to program.
        send(process, 'turnsleft %u' % turnsleft)
        send(process, 'crusher ' + '; '.join(actions))
        rabbitlocs = [point2text(r) for r in rabbits]
        send(process, ' '.join(['rabbits'] + rabbitlocs))
        # read rabbit move requests from program.
        start = time.time()
        inline = read(process)
        if time.time() - start > 0.5:
            print 'Move timeout'
            break
        # if a rabbit not exist or move not possible, no action.
        # if rabbit hits a crusher, rabbit is destroyed.
        # if rabbit is in exit teleporter, rabbit is removed and score increased.
        # if two rabbits collide, they are both destroyed.
        newrabbits = set()
        for p1,p2 in re.findall(r'(\d+,\d+)\s+to\s+(\d+,\d+)', inline):
            p1, p2 = map(text2point, [p1,p2])
            if p1 in rabbits and p2 not in walls:
                if p2-p1 in ORTH:
                    rabbits.discard(p1)
                    if p2 in crushers:
                        pass        # wabbit squished
                    elif p2 in exits:
                        score += 1  # rabbit saved
                    elif p2 in newrabbits:
                        newrabbits.discard(p2)  # moving rabbit collision
                    else:
                        newrabbits.add(p2)
        # plot each new location of rabbits.
        for rabbit in newrabbits:
            if rabbit in rabbits:
                rabbits.discard(rabbit)     # still rabbit collision
            else:
                rabbits.add(rabbit)
        turnsleft -= 1
        turn += 1
    process.terminate()
    return score

mapfile = sys.argv[1]
turns = int(sys.argv[2])
argseed = int(sys.argv[3])
runs = int(sys.argv[4])
program = sys.argv[5:]
errorlog = open('error.log', 'wt')
runlog = open('run.log', 'wt')
grid, walls, crusherstarts, rabbitstarts, exits = features(mapfile)
rabbits = set()
crushers = dict()

if 'anim' not in os.listdir('.'):
    os.mkdir('anim')
for fname in os.listdir('anim'):
    os.remove(os.path.join('anim', fname))

total = 0
print 'Running:', ' '.join(sys.argv)
print >> runlog, 'Running:', ' '.join(sys.argv)
fmt = '%10s %20s %10s'
print fmt % ('Run', 'Seed', 'Score')
for n in range(runs):
    nseed = argseed if argseed else randint(1,1000)
    score = run(n, nseed)
    total += score
    print fmt % (n+1, nseed, score)
print 'Total Score:', total
print >> runlog, 'Total Score:', total

```

The controller makes a text log of the runs in `run.log` and a series of images in the `anim` directory. If your Python installation can't find the PIL image library (download as Pillow), no images will be generated. I have been animating the image series with ImageMagick. Eg:

```
convert -delay 100 -loop 0 anim/run01* run1anim.gif

```

You are welcome to post interesting animations or images with your answer.

You can turn these features off and speed up the controller by setting `GRIDLOG
= False` and/or `MKIMAGE = False` in the first few lines of the controller program.

## Suggested Python framework

To help get started, here is a framework in Python. The first step is to read in the map file and find paths to the exits. In each turn there should be some code to store where the crushers are, and code that decides where to move our rabbits. The simplest strategy to start with is moving the rabbits towards an exit ignoring the crushers -- some rabbits might get through.

```
import sys, re
from random import *

mapfile = sys.argv[1]
argseed = int(sys.argv[2])
seed(argseed)

grid = [line.strip() for line in open(mapfile, 'rt')]
#
# Process grid to find teleporters and paths to get there
#

while 1:
    msg = sys.stdin.readline()

    if msg.startswith('turnsleft'):
        turnsleft = int(msg.split()[1])

    elif msg.startswith('crusher'):
        actions = re.findall(r'(\d+),(\d+) (movesto|crushes) (\d+),(\d+)', msg)
        #
        # Store crusher locations and movement so we can avoid them
        #

    elif msg.startswith('rabbits'):
        moves = []
        places = re.findall(r'(\d+),(\d+)', msg)
        for rabbit in [map(int, xy) for xy in places]:
            #
            # Compute the best move for this rabbit
            newpos = nextmoveforrabbit(rabbit)
            #
            moves.append('%u,%u to %u,%u' % tuple(rabbit + newpos))
        print 'move ' + '; '.join(moves)
        sys.stdout.flush()

```

# Answer
> 2 votes
# Crazy, Python 45

I did 25 runs with random seed, my computer isn't fast enough to go for 1000 (if someone want to correct the score) First program in python, it was a pain to debug for me. Also I don't know if I used it well.

It uses a breadth-first algorithm from the exit, one taking into account the crushers, the other without. I had a lot of timeout so I didn't go for something more complex (one crusher removal, etc.). The rabbits also go crazy if there is a crusher nearby in the hope to make it go to a wrong path.

```
import sys, re
from random import *

mapfile = sys.argv[1]
argseed = int(sys.argv[2])
seed(argseed)

grid = [line.strip() for line in open(mapfile, 'rt')]
width = len(grid[0])
height = len(grid)

starts = set([])
end = ()
walkables = set([])
crushers = set([])
#
# Process grid to find teleporters and paths to get there
#
for a in range(height):
    for b in range(width):
        if grid[a][b] == 'e':
            end = (b,a)
            walkables.add((b,a))
        elif grid[a][b] == 's':
            starts.add((b,a))
            walkables.add((b,a))
        elif grid[a][b] == 'c':
            crushers.add((b,a))
            walkables.add((b,a))
        elif grid[a][b] == ' ':
            walkables.add((b,a))

toSearch = [ (end, 0) ]
inSearch = [ end ]
visited = set([])
gradient = [[0]*height for x in range(width)]
while len(toSearch) > 0 :
    current = toSearch.pop(0)
    (row, col) = current[0]
    length = current[1]
    visited.add(current[0])
    neighbors = {(row+1,col),(row-1,col),(row,col+1),(row,col-1)}
    neighborSpaces = walkables & neighbors
    unvisited = neighborSpaces - visited
    for node in unvisited:
        if not node in inSearch:
            gradient[node[0]][node[1]]=[current[0][0],current[0][1]]
            inSearch.append(node)
            toSearch.append((node, length+1))
    toSearch.sort(key=lambda node: node[1])

while 1:
    msg = sys.stdin.readline()

    if msg.startswith('turnsleft'):
        turnsleft = int(msg.split()[1])

    elif msg.startswith('crusher'):
        # Update crushers
        actions = re.findall(r'(\d+),(\d+) (movesto|crushes) (\d+),(\d+)', msg)
        for one_action in actions:
            crushers.discard((int(one_action[0]),int(one_action[1])))
            crushers.add((int(one_action[3]),int(one_action[4])))

    elif msg.startswith('rabbits'):
        toSearch = [ (end, 0) ]
        inSearch = [ end ]
        visited = set([])
        gradient2 = [[0]*height for x in range(width)]
        while len(toSearch) > 0 :
            current = toSearch.pop(0)
            (row, col) = current[0]
            length = current[1]
            visited.add(current[0])
            neighbors = {(row+1,col),(row-1,col),(row,col+1),(row,col-1)}
            neighborSpaces = (walkables - crushers) & neighbors
            unvisited = neighborSpaces - visited
            for node in unvisited:
                if not node in inSearch:
                    gradient2[node[0]][node[1]]=[current[0][0],current[0][1]]
                    inSearch.append(node)
                    toSearch.append((node, length+1))
            toSearch.sort(key=lambda node: node[1])
        moves = []
        places = re.findall(r'(\d+),(\d+)', msg)
        for rabbit in [map(int, xy) for xy in places]:
            # If any crushers insight, go crazy to lose him
            directions = [(1,0),(-1,0),(0,1),(0,-1)]
            crazy = False
            newpos = 0
            for direction in directions:
                (row, col) = rabbit
                sight = 0
                while len({(row,col)} & walkables)>0 and sight<5 and crazy == False:
                    sight+=1
                    if (row,col) in crushers:
                        directions.remove(direction)
                        crazy = True
                    (row,col) = (row+direction[0],col+direction[1])
            for direction in directions:
                if not (rabbit[0]+direction[0],rabbit[1]+direction[1]) in walkables:
                    directions.remove(direction)
            if len(directions)==0:
                directions = [(1,0),(-1,0),(0,1),(0,-1)]
            direction = choice(directions)
            newpos = [rabbit[0]+direction[0],rabbit[1]+direction[1]]
            # Else use gradients
            if crazy == False:
                newpos = gradient2[rabbit[0]][rabbit[1]]
                if newpos == 0:
                    newpos = gradient[rabbit[0]][rabbit[1]]
            moves.append('%u,%u to %u,%u' % tuple(rabbit + newpos))
        print 'move ' + '; '.join(moves)
        sys.stdout.flush()

```

# Answer
> 1 votes
# Bunny, Java, 26.385

I averaged the scores of runs 1 to 1000 and multiplied by 5 to get my score. I'm pretty sure this is equivalent to the average score over all possible games with the standard options.

Scores

```
import java.awt.Point;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    private static final char WALL = '#';
    private static final char CRUSHER = 'c';
    private static final char ESCAPE = 'e';
    private static final char HUTCH = 's';

    private int height;
    private int width;

    private char[][] map;
    private List<Point> escapes = new ArrayList<>();
    private List<Point> crushers = new ArrayList<>();
    private List<Point> rabbits = new ArrayList<>();
    private List<Point> hutches = new ArrayList<>();

    private BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    private PrintStream out = System.out;
    private int[][] distances;

    public Main(String[] args) throws Exception {
        loadMap(args[0]);
    }

    private void loadMap(String mapFileName) throws Exception {
        char[][] preMap = new BufferedReader(new FileReader(mapFileName))
                .lines()
                .map(String::toCharArray)
                .toArray(char[][]::new);

        width = preMap[0].length;
        height = preMap.length;

        map = new char[width][height];    //tranpose

        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                map[x][y] = preMap[y][x];
            }
        }

        processMap();

        distances = dijkstra();

    }

    private void processMap() {
        for (int x = 0; x < width; x++){
            for (int y = 0; y < height; y++){
                char c = map[x][y];
                Point p = new Point(x, y);
                if (c == CRUSHER){
                    crushers.add(p);
                }
                if (c == ESCAPE){
                    escapes.add(p);
                }
                if (c == HUTCH){
                    hutches.add(p);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        new Main(args).run();
    }

    private void run() throws Exception{
        while (true) {
            in.readLine();
            readCrushers();
            readRabbits();
            makeDecision();
        }
    }

    private void makeDecision() {
        Map<Point, Point> moves = new HashMap<>();

        for (Point rabbit : rabbits){
            Point bestDirection = null;
            for (Point p : pointsAroundInclusive(rabbit)){
                if (
                        (bestDirection == null ||
                                distances[p.x][p.y] < distances[bestDirection.x][bestDirection.y]
                        ) && !moves.entrySet().contains(p)){
                    bestDirection = p;
                }
            }
            if (bestDirection != null) {
                moves.put(rabbit, bestDirection);
            }
        }

        out.println("move" +
                moves.entrySet().stream().map(a -> {
                    Point l0 = a.getKey();
                    Point l1 = a.getValue();
                    return " " + l0.x + "," + l0.y + " to " + l1.x + "," + l1.y;
                }).collect(Collectors.joining(";")));
    }

    private List<Point> pointsAroundInclusive(Point point) {
        List<Point> result = pointsAroundExclusive(point);
        result.add(point);
        return result;
    }

    private int[][] dijkstra() {
        Queue<Point> queue = new LinkedList<>();
        Set<Point> scanned = new HashSet<>();
        queue.addAll(escapes);
        scanned.addAll(escapes);

        int[][] distances = new int[width][height];

        while (!queue.isEmpty()) {
            Point next = queue.remove();
            int distance = distances[next.x][next.y];

            pointsAroundExclusive(next).stream()
                    .filter(p -> !scanned.contains(p))
                    .forEach(p -> {
                        distances[p.x][p.y] = distance + 1;
                        scanned.add(p);
                        queue.add(p);
                    });
        }

        return distances;
    }

    private List<Point> pointsAroundExclusive(Point p) {
        Point[] around = new Point[]{
                new Point(p.x - 1, p.y),
                new Point(p.x + 1, p.y),
                new Point(p.x, p.y - 1),
                new Point(p.x, p.y + 1)
        };

        List<Point> result = new ArrayList<>(Arrays.asList(around));
        result.removeIf(a -> {
            if (a.x < 0 || a.x >= width){
                return true;
            }
            if (a.y < 0 || a.y >= height){
                return true;
            }
            char c = map[a.x][a.y];
            return c == WALL;
        });

        return result;
    }

    private void readRabbits() throws Exception {
        String[] locations = in.readLine().substring("rabbits".length()).trim().split("\\s");
        rabbits.clear();

        for (String location : locations){

            if (location.equals("")){
                continue;
            }

            String[] decomposed = location.split(",");

            int x = Integer.parseInt(decomposed[0]);
            int y = Integer.parseInt(decomposed[1]);

            rabbits.add(new Point(x, y));
        }

    }

    private void readCrushers() throws Exception {
        String[] locations = in.readLine().substring("crusher".length()).trim().split("(; )?\\d+,\\d+ (movesto|crushes) ");
        crushers.clear();

        for (String location : locations){

            if (location.equals("")){
                continue;
            }

            String[] decomposed = location.split(",");

            int x = Integer.parseInt(decomposed[0]);
            int y = Integer.parseInt(decomposed[1]);

            crushers.add(new Point(x, y));
        }
    }

}

```

The best run tested has seed 1000. Here's a GIF of it:

---
Tags: code-challenge, path-finding, grid
---


# Question
Title: Print the first character of the previous answers
**The accepted winner is isaacg, with his 7-bit ASCII answer.** However, the challenge isn't over yet - this bounty is awarded to the shortest answer. If, *somehow*, you get all the first characters of all the other answers down into 10 bytes, you will win the bounty. This includes all the characters from Round 2's GolfScript answer (plus the one added by that answer itself). This is the ONE time I will let you go out of order - if you have any objections to this, let me know in the comments.

> I'd like to give credit to randomra, who helped me with my old idea and gave me this new one.

### Previous Winners

* Round 1: isaacg, with 7-bit ASCII
`Next bytes: 30 (or 10 if you want that sweet, sweet rep)`
You know, code-golfing is really cool. People take a challenge, and it slowly gets smaller! But let's do this another way. So, here is my challenge:
* The code will print the first character of all the previous answers in the order they were posted (the first answer prints nothing)
* The code starts at 100 bytes and decreases by 5 each time.
* If two posts are going by the same answer (i.e, they both posted within a few seconds of each other), the newer one has to add the old one's character and decrease by 5 bytes (even by a few seconds).
* Any language can be used.
* Your code must not produce any errors.
* Your code must use all the bytes required for the first step.
* Your code must print to STDOUT.
* Non-printable characters are OK, but:
    + They can not be the first character (for the sake of the purpose of this question)
    + You must let everyone know where they are
* You may post multiple answers, but:
    + You must wait 2 answers before posting another (so if you posted the 100 bytes, you have to wait until 85 bytes.)
* You can't:
    + use more than 10 bytes of comments
    + have variables that go unused for the entire program
    + fill the program with whitespace
    + have variable names longer than 10 bytes (but you can have multiple less-than 10-byte variables)
    (EMBLEM's first answer being the exception to these rules, because it was posted before these restrictions.)
* No standard loopholes. Unless you want to take all the fun out of the challenge.
* When no more answers are submitted for 3 weeks, the answer that uses the fewest bytes wins. (In the event of a tie, the one printing the longer string wins.)

Example: The third answer has to be a 90 bytes long code outputting two characters (the first char of the 100-byte code then the first char of the 95-byte code). The first answer outputs nothing (no previous answers to get chars from).

# Answer
> 35 votes
# 7-bit ASCII, 15 bytes

Updated: I did not realize that padding should occur at the end.

Correct version, padded at end:

hexdump (xxd):

```
0000000: e1c3 af0e 1438 a8b6 8f37 7a7b 7250 b6    .....8...7z{rP.

```

Printouts (not sure which is correct):

```
�ï8��z{rP�

áÃ¯8¨¶7z{rP¶

```

Old version, incorrectly padded at the front:

```
pá×
T[G½=¹([

```

The language / format here is 7-bit ascii, where each group of 7 bits corresponds to an ASCII character. It is used in transferring SMS data. A decoder is located here.

No widely accepted ruling exists on whether answers to fixed output questions which are not written in a programming language are allowed. See this meta post for more information. (I apologize, I misread that post earlier.)

# Answer
> 25 votes
# Element, 80 bytes

```
programs do many fun things, like print the letters p`, p`, u`, and p` in a row.

```

This is a language I created over three years ago. You can find an interpreter, written in Perl, here. The ``` operator prints the top thing on the stack (the letters). The other punctuation does do stuff, like concatenation, but the results are never printed.

# Answer
> 10 votes
# Clip, 20 bytes

```
[M"ppuppPq([#fwSmdP"

```

# Answer
> 5 votes
# Common Lisp, 65 bytes

```
(print(map 'string #' code-char #(112 112 117 112 #x70 80 #x71)))

```

# Answer
> 5 votes
## Scratch, 45 bytes

```
when green flag clicked
show
say[ppuppPq([#f]

```

Byte count as per text representation. See meta.

# Answer
> 5 votes
# Round 2: Ruby, 75 bytes

```
"ppuppPq([#fwSmdP[ppnvos".chars.each do|character|;print character;end#4444

```

I thought I'd make it a little more challenging by starting my answer with a quote! \>:D

# Answer
> 4 votes
# Python 3, 95 bytes

```
pre='public class f{public static void main(String[] a){System.out.print("");}}'
print(pre[0])

```

# Answer
> 4 votes
# Haskell, 35 bytes

```
main = putStrLn "\&ppuppPq([#fwS\&"

```

# Answer
> 4 votes
It has been 24 hours since the edit! Let's do this! :D

# Java, Round 2, 100 bytes

```
public class Bytes{public static void main(String[] args){System.out.print("ppuppPq([#fwSmdP[p");}}

```

# Answer
> 3 votes
# Java, 100 bytes

```
public class f{public static void main(String[] a){System.out.print("");}}//createdbyEMBLEMasdfghjkl

```

# Answer
> 3 votes
# Mathematica, 75 bytes

```
Print[StringJoin[First/@Characters/@{"publ","pre=","usin","p1 =","prog"}]];

```

# Answer
> 3 votes
# F#, 60 bytes

```
[<EntryPoint>]let main arg=System.Console.Write "ppuppPq(";0

```

# Answer
> 3 votes
# F# script, 40 bytes

```
System.Console.Write "\u0070puppPq([#fw"

```

It has its own file type (`.fsx`), so I'm pretty sure that it counts as a language.

# Answer
> 3 votes
# Round 2: ///, 65 bytes

```
\p/CodeGolfIsAwesome!/puppPq/CodeGolfIsAwesome!([#fwSmdP[ppnvos"R

```

Thought I would spice it up a bit more with a backslash :)

# Answer
> 2 votes
# C#, 90 bytes

```
using System;namespace IAmAwesome{class Program{static void Main(){Console.Write("pp");}}}

```

# Answer
> 2 votes
# Ruby, 70 bytes

```
q = ["publ", "pre", "usi", "p1 ", "pro", "Pri"]
q.each{|s| print s[0]}

```

# Answer
> 2 votes
# C, 55 Bytes

```
#include<stdio.h>
int main(){return puts("ppuppPq([");}

```

# Answer
> 2 votes
# JavaScript, 50 bytes

```
function foo() {console.log("ppuppPq([#");}
foo();

```

# Answer
> 2 votes
# MATLAB, 30 bytes

```
disp([112 112 'uppPq([#fwSm'])

```

Nicely shows how loose MATLAB goes about with data types.

# Answer
> 2 votes
# Mathematica, 25 bytes

```
Print["ppuppPq([#fwSmd"];

```

# Answer
> 2 votes
# Round 2: Batch, 70 bytes

```
REM BATCHS
GOTO B
:C
ECHO ppuppPq([#fwSmdP[ppnvos"
GOTO A
:B
GOTO C
:A

```

Your quote was futile. D:\>

Edit: it just occurred to me that I was going by file size instead of character count, not sure how bytes are to be counted :P

Edit 2: Added a comment to fill bytes. If you check byte count on a windows machine, just pretend the "REM BATCHS" is just "REM" I guess. :P

# Answer
> 2 votes
# Round 2, \>\<\>, 45 bytes

4 chars of comments.

```
'c(v\R"sovnpp[PdmSwf#[(qPppupp'01.uwyz
ol?!;

```

The string now contains both `"` and `'`, so \>\<\> answers can't just surround it with either anymore (that's how I avoided any escapes).

# Answer
> 2 votes
# Round 2, Mathematica, 40 bytes

```
Print@"ppuppPq([#fwSmdP[ppnvos\"R\\v(c'"

```

Yay second page!

# Answer
> 2 votes
# Round 2, Golfscript, 35 bytes

```
"ppuppPq([#fwSmdP[ppnvos\"R\\v(c'P"

```

No waste bytes. Starts with a quote again!

# Answer
> 1 votes
# Python 3, 85 bytes

```
p1 = 'publ'
p2 = 'pre'
p3 = 'usi'
def cprint():
  print(p1[0], p2[0], p3[0])
cprint()

```

# Answer
> 1 votes
# Round 2, C#, 95 bytes

```
namespace Cool{class Program{static void Main(){System.Console.Write("ppuppPq([#fwSmdP[pp");}}}

```

# Answer
> 1 votes
**Round 2: Javascript, 90 bytes**

```
var p="p";alert(p+p+p+"u"+p+p+p.toUpperCase()+"q([#fwSmd"+p.toUpperCase()+"["+p+p+"n");//p

```

# Answer
> 1 votes
**Round 2, Javascript, 60 bytes**

```
var _p="p";alert(_p.repeat(2)+"uppPq([#fwSmdP[ppnvos\"R\\");
```

# Answer
> 1 votes
# Round 2, F# script, 55 bytes

```
(**)System.Console.Write(@"uppPq([#fwSmdP[ppnvos""R\v")

```

See my previous F# script anwer for why I think it is a valid language.

# Answer
> 1 votes
# Round 2, R, 50 bytes

```
cat('ppuppPq([#fwSmdP[ppnvos\"R\\v(',file=stdout())

```

# Answer
> 0 votes
# Round 2: Python, 85 bytes

```
os=['p']*8
os[4:6]=u'P'+r'q([#fwSmdP'
os[2:2]='u'
os[-2:-2]='['
print''.join(os)+'nv'

```

Starts with the fundamentals - the `'p'`s - and builds it up from there.

# Answer
> 0 votes
## Round 2: VBS, 80 bytes

```
s = "ppuppPq([#fwSmdP[ppnvo" : For i=1 To 22 : WScript.Echo Mid(s ,i , 1) : Next

```

Left field language.

---
Tags: kolmogorov-complexity, answer-chaining
---


title: Write an URL compressor

text:
# Question
Title: Write an URL compressor
Today your goal is to invent URL compression. You must write two programs: a compressor and a decompressor.

* The compressor will be called with **one** URL on stdin and its output will be read on stdout.
* The decompressor will be called with the output of the compressor on stdin, and must produce the **exact** URL passed into the compressor to stdout.
* The sum of the size in bytes of the compressor and decompressor source may be at most 1024 bytes.
* Your answer must come with command line instructions to run your two programs. You're not allowed to pass in information of any kind through command line arguments - they should merely be to run the program.

The standard loopholes are not allowed. Additionally, your program is not allowed to keep and use any state of any kind between executions, not in files, environment variables, etc. Lastly, you may not use any built-in data compression routines if your language has them.

### Scoring

I have taken all URLs found in the StackExchange dump of PPCG and collected them in one file, one URL per line. Your score will be the sum of the size of all compressed URLs in that file. **Lowest score wins.**

---

It is not guaranteed that your program is called with a valid URL. Your program must work for every input found in the test file, but doesn't have to work for any other input.

**Your answer only has to work for the given URLs, and only has to optimize for those.**

# Answer
> 9 votes
# CJam ~~308954~~ 268306 bytes

### Compressor (511 bytes)

```
0000000: 22 2f 25 2d 30 31 32 33 35 61 65 0a 2e 34 37 38  "/%-01235ae..478
0000010: 39 62 63 66 67 69 6c 6d 70 73 74 75 0a 36 41 42  9bcfgilmpstu.6AB
0000020: 43 44 45 46 49 4a 4b 4c 4d 53 58 5f 64 68 6a 6b  CDEFIJKLMSX_dhjk
0000030: 6e 6f 72 76 77 78 79 7a 97 a0 a5 a6 22 0a 4e 2f  norvwxyz....".N/
0000040: 5f 3a 2b 32 35 36 63 2c 5e 61 2b 3a 47 3b 22 63  _:+256c,^a+:G;"c
0000050: 6f 7f 6d 73 74 6e 67 6f 6c 6f 72 64 65 7f 85 83  o.mstngolorde...
0000060: 66 67 87 86 88 81 61 8a 63 8b 6b 61 82 80 2f 2e  fg....a.c.ka../.
0000070: 8e 65 8f 8d 90 68 91 63 92 78 93 65 94 8c 95 65  .e...h.c.x.e...e
0000080: 72 6f 6e 84 67 77 69 9a 6b 9b 69 74 68 96 61 69  ron.gwi.k.ith.ai
0000090: 98 69 6e 65 74 6e a1 65 6e 64 69 25 32 a5 30 a6  .inetn.endi%2.0.
00000a0: a6 77 77 a8 77 6c 65 72 65 2e 99 ac 2f ad 9c 9f  .ww.wlere.../...
00000b0: 73 81 af 89 2e b1 9e b1 96 65 a4 70 b4 9c b5 72  s........e.p...r
00000c0: 69 a5 42 b7 70 b9 74 62 8f b6 61 bc ae 61 72 b2  i.B.p.tb..a..ar.
00000d0: 2f 61 74 6c 6f 61 6d 74 6d 68 c3 c4 6c 65 b0 75  /atloamtmh..le.u
00000e0: c6 71 c7 b3 c8 63 ba 73 ca 88 cb 72 6f 61 6e 69  .q...c.s...roani
00000f0: 9d cf 75 d0 bb 67 d1 65 73 75 73 d4 97 b3 d5 6a  ..u..g.esus....j
0000100: c2 63 d7 c1 77 d9 8f 70 68 db bb 70 dc 73 75 74  .c..w..ph..p.sut
0000110: de a4 df 61 e0 98 90 85 e2 69 e3 d3 83 e5 8d a9  ...a.....i......
0000120: 2e 61 dd 76 97 6f e9 8c ea eb 66 ec da 6a 73 ee  .a.v.o....f..js.
0000130: 66 ef 69 f0 64 f1 64 f2 aa 70 cd a2 2f 2e f5 f3  f.i.d.d..p../...
0000140: f6 e1 f6 e6 73 f9 ae 61 6c 75 6e bf 34 70 79 fe  ....s..alun.4py.
0000150: 9d 63 74 fc 00 b8 b8 75 72 03 8f a5 43 64 6f 06  .ct....ur...Cdo.
0000160: 63 d6 73 ed c8 a7 a7 b8 a6 a6 a5 69 73 72 c2 75  c.s........isr.u
0000170: 74 69 82 bd 2f 2e 11 a3 12 67 49 14 43 15 41 16  ti../....gI.C.A.
0000180: 16 a3 74 07 73 72 fc d2 0d 69 74 2e c5 63 68 61  ..t.sr...it..cha
0000190: 73 e8 3f 20 63 5c 22 3d be 1e 6f 03 69 aa a5 39  s.? c\"=..o.i..9
00001a0: 60 a5 6f 66 22 32 2f 31 32 39 2c 31 32 37 66 2b  `.of"2/129,127f+
00001b0: 33 33 2c 2b 3a 63 22 5c 22 3c 3e 5c 5e 60 7b 7d  33,+:c"\"<>\^`{}
00001c0: 22 2b 6c 5f 34 3d 27 73 3d 3a 4c 37 2b 3e 40 7b  "+l_4='s=:L7+>@{
00001d0: 2f 5c 28 40 5c 2a 7d 2f 30 5c 7b 47 7b 31 24 23  /\(@\*}/0\{G{1$#
00001e0: 29 7d 23 5f 47 3d 3a 54 40 23 40 54 2c 2a 2b 34  )}#_G=:T@#@T,*+4
00001f0: 2a 2b 7d 2f 32 2a 4c 2b 32 35 36 62 3a 63 0a     *+}/2*L+256b:c.

```

### Decompressor (510 bytes)

```
0000000: 22 2f 25 2d 30 31 32 33 35 61 65 0a 2e 34 37 38  "/%-01235ae..478
0000010: 39 62 63 66 67 69 6c 6d 70 73 74 75 0a 36 41 42  9bcfgilmpstu.6AB
0000020: 43 44 45 46 49 4a 4b 4c 4d 53 58 5f 64 68 6a 6b  CDEFIJKLMSX_dhjk
0000030: 6e 6f 72 76 77 78 79 7a 97 a0 a5 a6 22 0a 4e 2f  norvwxyz....".N/
0000040: 5f 3a 2b 32 35 36 63 2c 5e 61 2b 3a 47 3b 22 63  _:+256c,^a+:G;"c
0000050: 6f 7f 6d 73 74 6e 67 6f 6c 6f 72 64 65 7f 85 83  o.mstngolorde...
0000060: 66 67 87 86 88 81 61 8a 63 8b 6b 61 82 80 2f 2e  fg....a.c.ka../.
0000070: 8e 65 8f 8d 90 68 91 63 92 78 93 65 94 8c 95 65  .e...h.c.x.e...e
0000080: 72 6f 6e 84 67 77 69 9a 6b 9b 69 74 68 96 61 69  ron.gwi.k.ith.ai
0000090: 98 69 6e 65 74 6e a1 65 6e 64 69 25 32 a5 30 a6  .inetn.endi%2.0.
00000a0: a6 77 77 a8 77 6c 65 72 65 2e 99 ac 2f ad 9c 9f  .ww.wlere.../...
00000b0: 73 81 af 89 2e b1 9e b1 96 65 a4 70 b4 9c b5 72  s........e.p...r
00000c0: 69 a5 42 b7 70 b9 74 62 8f b6 61 bc ae 61 72 b2  i.B.p.tb..a..ar.
00000d0: 2f 61 74 6c 6f 61 6d 74 6d 68 c3 c4 6c 65 b0 75  /atloamtmh..le.u
00000e0: c6 71 c7 b3 c8 63 ba 73 ca 88 cb 72 6f 61 6e 69  .q...c.s...roani
00000f0: 9d cf 75 d0 bb 67 d1 65 73 75 73 d4 97 b3 d5 6a  ..u..g.esus....j
0000100: c2 63 d7 c1 77 d9 8f 70 68 db bb 70 dc 73 75 74  .c..w..ph..p.sut
0000110: de a4 df 61 e0 98 90 85 e2 69 e3 d3 83 e5 8d a9  ...a.....i......
0000120: 2e 61 dd 76 97 6f e9 8c ea eb 66 ec da 6a 73 ee  .a.v.o....f..js.
0000130: 66 ef 69 f0 64 f1 64 f2 aa 70 cd a2 2f 2e f5 f3  f.i.d.d..p../...
0000140: f6 e1 f6 e6 73 f9 ae 61 6c 75 6e bf 34 70 79 fe  ....s..alun.4py.
0000150: 9d 63 74 fc 00 b8 b8 75 72 03 8f a5 43 64 6f 06  .ct....ur...Cdo.
0000160: 63 d6 73 ed c8 a7 a7 b8 a6 a6 a5 69 73 72 c2 75  c.s........isr.u
0000170: 74 69 82 bd 2f 2e 11 a3 12 67 49 14 43 15 41 16  ti../....gI.C.A.
0000180: 16 a3 74 07 73 72 fc d2 0d 69 74 2e c5 63 68 61  ..t.sr...it..cha
0000190: 73 e8 3f 20 63 5c 22 3d be 1e 6f 03 69 aa a5 39  s.? c\"=..o.i..9
00001a0: 60 a5 6f 66 22 32 2f 5b 71 32 35 36 62 32 6d 64  `.of"2/[q256b2md
00001b0: 22 68 74 74 70 22 6f 27 73 2a 6f 22 3a 2f 2f 22  "http"o's*o"://"
00001c0: 6f 7b 34 6d 64 47 3d 5f 2c 40 5c 6d 64 40 3d 5c  o{4mdG=_,@\md@=\
00001d0: 7d 68 3b 5d 57 25 31 32 39 2c 31 32 37 66 2b 33  }h;]W%129,127f+3
00001e0: 33 2c 2b 3a 63 22 5c 22 3c 3e 5c 5e 60 7b 7d 22  3,+:c"\"<>\^`{}"
00001f0: 2b 57 25 7b 2f 5c 29 40 5c 2a 7d 2f 4e 0a        +W%{/\)@\*}/N.

```

### Algorithm

1. Strip the `<scheme>://` part from the URL.
2. Replace character pairs by unused code points in the 0 - 255 range.

This uses a static dictionary which is included in the source code.
3. Use arithmetic encoding on the modified input string.

To comply with the source code size limit, this is done by splitting the 256 code points into 4 groups and pretending the groups and the code points in a fixed group have equal probabilities.
4. Append a bit indicating the scheme to the resulting integer.
5. Convert the integer into a string.

## Test cases

Create the source code files.

```
$ xxd -p -r > comp.cjam <<< 222f252d303132333561650a2e3437383962636667696c6d707374750a36414243444546494a4b4c4d53585f64686a6b6e6f72767778797a97a0a5a6220a4e2f5f3a2b323536632c5e612b3a473b22636f7f6d73746e676f6c6f7264657f8583666787868881618a638b6b6182802f2e8e658f8d9068916392789365948c9565726f6e846777699a6b9b69746896616998696e65746ea1656e64692532a530a6a67777a8776c6572652e99ac2fad9c9f7381af892eb19eb19665a470b49cb57269a542b770b974628fb661bcae6172b22f61746c6f616d746d68c3c46c65b075c671c7b3c863ba73ca88cb726f616e699dcf75d0bb67d165737573d497b3d56ac263d7c177d98f7068dbbb70dc737574dea4df61e0989085e269e3d383e58da92e61dd76976fe98ceaeb66ecda6a73ee66ef69f064f164f2aa70cda22f2ef5f3f6e1f6e673f9ae616c756ebf347079fe9d6374fc00b8b87572038fa543646f0663d673edc8a7a7b8a6a6a5697372c275746982bd2f2e11a3126749144315411616a374077372fcd20d69742ec563686173e83f20635c223dbe1e6f0369aaa53960a56f6622322f3132392c313237662b33332c2b3a63225c223c3e5c5e607b7d222b6c5f343d27733d3a4c372b3e407b2f5c28405c2a7d2f305c7b477b312423297d235f473d3a54402340542c2a2b342a2b7d2f322a4c2b323536623a630a

$ xxd -p -r > decomp.cjam <<< 222f252d303132333561650a2e3437383962636667696c6d707374750a36414243444546494a4b4c4d53585f64686a6b6e6f72767778797a97a0a5a6220a4e2f5f3a2b323536632c5e612b3a473b22636f7f6d73746e676f6c6f7264657f8583666787868881618a638b6b6182802f2e8e658f8d9068916392789365948c9565726f6e846777699a6b9b69746896616998696e65746ea1656e64692532a530a6a67777a8776c6572652e99ac2fad9c9f7381af892eb19eb19665a470b49cb57269a542b770b974628fb661bcae6172b22f61746c6f616d746d68c3c46c65b075c671c7b3c863ba73ca88cb726f616e699dcf75d0bb67d165737573d497b3d56ac263d7c177d98f7068dbbb70dc737574dea4df61e0989085e269e3d383e58da92e61dd76976fe98ceaeb66ecda6a73ee66ef69f064f164f2aa70cda22f2ef5f3f6e1f6e673f9ae616c756ebf347079fe9d6374fc00b8b87572038fa543646f0663d673edc8a7a7b8a6a6a5697372c275746982bd2f2e11a3126749144315411616a374077372fcd20d69742ec563686173e83f20635c223dbe1e6f0369aaa53960a56f6622322f5b7132353662326d642268747470226f27732a6f223a2f2f226f7b346d64473d5f2c405c6d64403d5c7d683b5d57253132392c313237662b33332c2b3a63225c223c3e5c5e607b7d222b57257b2f5c29405c2a7d2f4e0a

```

Verify their integrity.

```
$ cksum comp.cjam decomp.cjam
2293013588 511 comp.cjam
1577103568 510 decomp.cjam

```

Download the CJam interpreter.

```
$ wget -q wget http://downloads.sourceforge.net/project/cjam/cjam-0.6.4/cjam-0.6.4.jar

```

Create an alias for running the interpreter.

```
$ alias cjam='java -jar cjam-0.6.4.jar'

```

Set encoding to ISO-8859-1 to store each character as a single byte.

```
$ LANG=en_US

```

Prepare the test file.

```
$ wget -q https://gist.githubusercontent.com/orlp/fd3411259469ade4c65d/raw/bb6b088c18c444d28729abc870d6076ca594a6de/urls.txt

$ echo >> urls.txt

```

For each line in the test file, feed the URL to the compressor, append the output to `urls-comp.bin` and feed it back to the decompressor. Save the combined output of all decompressions in `urls-vrfy.txt`. **This will take a few minutes.**

```
$ >urls-comp.bin

$ for URL in $(<urls.txt); do
> echo $URL | cjam comp.cjam | tee -a urls-comp.bin | cjam decomp.cjam
> done > urls-vrfy.txt

```

Verify that all URLs were decoded appropriately.

```
$ cksum urls.txt urls-vrfy.txt
3445245739 588562 urls.txt
3445245739 588562 urls-vrfy.txt

```

Compute the score.

```
$ wc -c urls-comp.bin
268306 urls-comp.bin

```

## How it works

### Common

Push the string containing the first three character groups.

```
"/%-01235ae
.4789bcfgilmpstu
6ABCDEFIJKLMSX_dhjknorvwxyz����"

```

Split at linefeeds, flatten a copy of the resulting array and compute the symmetric difference of the resulting string and the string of all code points.

```
N/_:+256c,^

```

Append the result to the array which now contains all four character groups. Save the result in the variable `G` and discard it from the stack.

```
a+:G;

```

Push the array (let's call it `A`) containing all character pairs to be substituted.

```
"comstngolorde��fg����a�c�ka��/.�e���h�c�x�e���eron�gwi�k�ith�ai�inetn�endi%2�0��ww�wlere.��/���s���.����e�p���ri�B�p�tb��a��ar�/atloamtmh��le�u�qǳ�c�sʈ�roani��uлg�esusԗ��j�c��wُphۻp�sutޤ�a���i�Ӄit.�chas�? c\"=�oi��9`�of"
2/

```

Push the array `[ 0 ... 128 ]`, add 127 to each element, append the array `[ 0 ... 32 ]`, cast to Char and append the string `"\"<>\^`{}"`. The result is the string (let's call it`S\`) of all unused code points from 0 to 255.

```
129,127f+33,+:c"\"<>\^`{}"+

```

### Compressor

```
...        " Generate G. Push A and S.                                        ";
l          " Read one line from STDIN.                                        ";
_4='s=     " Check if its 5th character is an 's'.                            ";
:L7+       " Save the result in L and add it to 7.                            ";
>          " Discard that many characters from the input string.              ";
@{         " For each character pair in A:                                    ";
  /        "   Split the input string at its occurrences.                     ";
  \(@\     "   Unshift one character C from S.                                ";
  *        "   Join the split string, using C as separator.                   ";
}/         "                                                                  ";
0          " Push 0 (accumulator).                                            ";
\{         " For each character C in the input string:                        ";
  G{1$#)}# "   Retrieve the index of the group C belongs to.                  ";
  _G=:T    "   Store the group in T.                                          ";
  @#       "   Push the index of C in T.                                      ";
  @T,*+4*+ "   Multiply the accumulator by the length of T and add the index. ";
}/         "                                                                  ";
2*L+       " Multiply the accumulator by 2 and add L.                         ";
256b:c     " Convert the accumulator (BigInteger) into a byte string.         ";

```

### Decompressor

```
...        " Generate G. Push A.                                              ";
[q         " Start an array and read the whole input.                         ";
256b       " Convert the byte string into an integer.                         ";
2md        " Push quotient and residue of the division by 2.                  ";
"http"o    " Print 'http'.                                                    ";
's*o       " If the residue is 1, print 's'.                                  ";
"://"o     " Print '://'.                                                     ";
{          " While the integer is non-zero:                                   ";
  4md      "   Push quotient and residue of the division by 4.                ";
  G=_,     "   Push the corresponding character group and its length.         ";
  @\md     "   Divide the integer by the length. Push quotient and residue.   ";
  @=\      "   Retrieve the char corresponding to the residue from the group. ";
}h         "                                                                  ";
]W%        " End and reverse array.                                           ";
           " Since the elements are Chars, this yields a string.              ";
...        " Push S.                                                          ";
\W%{       " For each character in S reversed:                                ";
  /        "     Split the string at its occurrences.                         ";
  \)@\     "     Pop one character pair P from A.                             ";
  *        "     Join the split string, using P as separator.                 ";
}/         "                                                                  ";
N          " Push a linefeed.                                                 ";

```

### Remarks

Decompression will work correctly only for the `http` and `https` schemes. The reasons are twofold:

* The `http` part is hardcoded.
* The arithmetic encoding uses the fact that `<http|https>://` cannot be followed by a third slash.

Since the integer 0 encodes any arbitrary run of slashes (character 0 of group 0), we would have to store the URL's length or the number of leading slashes to support, e.g., `file:///` URLs.

# Answer
> 7 votes
# BrainFuck: 550417

**Encoder:**

```
,,,,,[.,]

```

**Decoder:**

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

```

It needs the url without linefeed and it expects 0 as EOF.

Example:

```
> echo -n "http://stackoverflow.com/" | beef encode.bf
://stackoverflow.com/
> echo -n "://stackoverflow.com/" | beef decode.bf
http://stackoverflow.com/

```

# Answer
> 1 votes
# MATLAB, 477161

Edit: something odd is going on here. When I fed the original list through a RAR compressor, it got it down to 122Kb. When I feed my compressed list, though, it can only get it down to 222Kb. So, basically I created a compression algorithm that will make it harder for other compression algorithms to work. How about that, huh... :)

Takes the input string, strips it of the `http` at the start, and then compresses the string into a 7-bit representation. Appends an 'x' or 'y' for the decompressor to now whether it is dealing with a complete block or not; this could have probably been done more efficient (perhaps a parity bit) but this will have to do for now (it will only decrease my score with about 10k). I only realized halfway this was not code-golf, so you'll have to do without descriptive variable names.

```
function t=compress(s);
s=s(5:end);
t='';
replacable='"<>\^`{}';
for(k=replacable)
    s=strrep(s,['%' dec2hex(k)],k);
end
l=numel(s);
for(i=1:8:l-mod(l,8))
    t=[t char(bin2dec(reshape(dec2bin(s(i:i+7),7),7,8)))'];
end
if(mod(l,8))
    t=[t s(l-mod(l,8)+1:l)];
    t(end+1)='x';
else
    t(end+1)='y';
end

```

Decompress:

```
function s=decompress(t);
l=numel(t)-1;
if(t(end)=='x')
    endfor=l-mod(l,7);
    endfor(l==endfor)=l-7;
else
    endfor=l-1;
end
s='http';
for(i=1:7:endfor)
    s=[s char(bin2dec(reshape(dec2bin(t(i:i+6),8),8,7)))'];
end
if(t(end)=='x')
    s=[s t(endfor+1:end-1)];
end

replacable='"<>\^`{}';
for(k=replacable)
    s=strrep(s,k,['%' dec2hex(k)]);
end

```

EDIT: fixed some bugs, added some `%xx` replacements; other than that I'm calling it a day because I'll *never* get to 300k with this approach.

# Answer
> 1 votes
# Python (413649)

Compressor:

```
u=input()[4:]
for i,j in zip('"<>\\^`{}\t\r\v\f','s:// :// codegolf.stackexchange.com en.wikipedia.org/wiki cjam.aditsu.net jsfiddle.net golfscript.apphb.com ideone.com github.com stackoverflow.com esolangs.org i.stack.imgur.com'.split()):
 u=u.replace(j,i)
print(u)

```

Decompressor:

```
u='http'+input()
for i,j in zip('"<>\\^`{}\t\r\v\f','s:// :// codegolf.stackexchange.com en.wikipedia.org/wiki cjam.aditsu.net jsfiddle.net golfscript.apphb.com ideone.com github.com stackoverflow.com esolangs.org i.stack.imgur.com'.split()):
 u=u.replace(i,j)
print(u)

```

The algorithm is very simple. The http at the beginning is stripped because it is the same in all of the test urls. It then takes the most common domain names in the test file and substitutes each for a single ascii character, out of the characters not used in any. It also substitutes `://` (http) and `s://` (https) for individual characters.

---
Tags: code-challenge, kolmogorov-complexity, restricted-source, compression
---


title: Slime Molds Can Count!

text:
# Question
Title: Slime Molds Can Count!
# Background

Slime molds are awesome. If you place them on a surface with food sources, they will spread their tendrils to find the food, after which they form a network of connections between the sources. In this challenge, you shall simulate a slime mold looking for food. Moreover, this particular mold will stop once it's found enough.

# Input

Your inputs shall be a list `L` of 2D integer coordinates in the native format of your language, and a nonnegative integer `N`. The list `L` is guaranteed to be duplicate-free, but it may not be sorted. The input `N` is between 0 and the length of `L`, inclusive.

The list `L` represents a set of coordinates for food sources. For example, the list

```
[(0,0),(2,-1),(3,1),(0,4),(5,5)]

```

could be interpreted visually as

```
     o
o

   o
o
  o

```

# Output

Your output is another duplicate-free list `K` of 2D integer coordinates on the same format as the input. It represents the network formed by the slime mold, and it shall satisfy the following conditions:

* The intersection of `L` and `K` has size exactly `N`.
* The set `K` is connected as a subset of the integer grid (via orthogonal or diagonal adjacencies).
* If any coordinate of `K` is removed, it no longer satisfies the first two conditions.

Note that if `N = 0`, the output must be an empty list.

An example of an acceptable output for the above list `L` and `N = 4` would be

```
[(0,0),(0,1),(0,2),(0,3),(0,4),(1,4),(2,4),(3,3),(3,2),(3,1),(3,5),(4,5),(5,5)]

```

which can be visualized as

```
   xxO
Oxx
x  x
x  x
x  O
O
  o

```

where each `O` represents a coordinate in both `L` and `K`, and each `x` represents a coordinate in `K` but not in `L`. Other outputs are also acceptable, and the "tendrils" don't have to be the shortest possible. For example, this is also an acceptable solution:

```
   xxOxx
Oxx     x
  x    x
 x    x
x  o x
O   x
  Ox

```

# Rules

Both the input and output shall be lists, not sets or other datatypes. The coordinates themselves can be lists or tuples. You can change the order of the two inputs if needed.

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

# Test Cases

Your program should work on these lists for all applicable values of `N`.

```
[]
[(2,3)]
[(0,0),(1,0),(0,1),(1,1)]
[(0,0),(2,-1),(3,1),(0,4),(5,5)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3)]
[(0,0),(1,0),(2,0),(3,0),(0,3),(1,3),(2,3),(3,3),(0,1),(0,2),(3,1),(3,2),(8,1),(8,2),(-5,1),(-5,2)]
[(0,0),(20,0),(15,15),(-10,4),(-10,3),(0,-5),(7,6),(7,7),(8,8),(9,8),(10,-2),(-1,12),(-3,10)]
[(0,0),(1,0),(2,0),(3,0),(5,0),(6,0),(7,0),(0,9),(1,9),(2,9),(3,8),(4,9),(5,10),(6,10),(7,9),(3,3),(4,4),(5,5)]

```

Visualized:

```
===
o
===
oo
oo
===
     o
o

   o
o
  o
===
oooo

oooo
===
     oooo
o    o  o    o
o    o  o    o
     oooo
===
                         o

         o

       o

                  oo
                 o
                 o

o
o

          o                   o

                    o

          o
===
     oo
ooo o  o
   o

     o
    o
   o

oooo ooo

```

# Answer
> 3 votes
# CJam, ~~77~~ 95 bytes

I think this can be golfed a bit more, but here goes:

```
q~$<_{{:X;]{[X\]z::-~mhW*}$~:Y{_)Y1{_@=X@=}:B~-g-{+__X=!\}:C~1B=!&}g{_(Y0B-g-\C0B=!&}g}*]_&}L?p

```

Input goes like `N <Array of coordinate array>`. For example:

```
4 [[0 0] [1 5] [2 1] [0 3] [5 0] [5 5]]

```

Output:

> \[\[0 5\] \[1 5\] \[0 4\] \[0 3\] \[0 0\] \[0 2\] \[0 1\] \[1 1\] \[2 1\]\]

**Algorithm**:

The algorithm is pretty straight forward and goes like:

* Sort the input coordinate array. This makes the coordinates sorted first by row and then by column.
* Now we pick first `N` points
* Now we reduce on these `N` points. The destination is the last point and the source is the closes point to that last point.
* Then we start with the top-left most point, walk right (or left) till its on or directly above the next point.
* Then we walk down to reach the next point.
* It is guaranteed that there will be no uncovered point left to the above point in the same row. This ensures that we do not touch any other point that the chosen `N`. Choosing the closes point also ensures that second rule is held true.

Try it online here

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


title: Nameless to Brainf**k converter

text:
# Question
Title: Nameless to Brainf**k converter
This is inspired by the Brainf\*** to tinyBF converter challenge.

Brainf\**k (which will be henceforth referred to as BF) is a well-known estoric programming language, so I won't go over it too much here.

Nameless language is a binary-looking version of BF. See the linked page for more info.

Your challenge is to implement a **golfed Nameless-to-BF converter**. It should implement *all* of the commands except for 1100 (which isn't really possible to implement in BF) and 1010 (that isn't really possible, either). Any characters other than 1's and 0's should be ignored because they can be used for comments (after all, you wouldn't want an unreadable program, right? ;).

Here's a simple table of a Nameless -\> BF mapping:

```
0000 -> >
0001 -> <
0010 -> +
0011 -> -
0100 -> .
0101 -> ,
0110 -> [
0111 -> ]
1011 -> [-]
1000 -> adds the base 10 value of the next command to the current memory cell (see below)
1001 -> subtracts the base 10 value of the next command from the current memory cell (see below)

```

**NOTE**: I accidentally flipped `<` and `>`. Thanks to @IlmariKaronen for pointing that out.

For 1000 and 1001, you can directly implement it in the translator. For instance, this:

```
1000 0010

```

could be written as:

```
++

```

The translator determined the value of the next command in advance and wrote it out.

Invalid sequences (e.g. 1111) and the presence of 1000/1001 at the end of the program are undefined; you don't have to handle them.

MAY THE GOLFING BEGIN!!!

# Answer
# CJam, 58 bytes

```
q{As#)},:~4/2fb{(:X8<"><+-.,[]"X={XA<{("+-"X=*}"[-]"?}?o}h

```

Try it online.

### Explanation

```
q               "Read the input.";
{As#)},         "Remove any extraneous characters (not '0' or '1').";
:~              "Evaluate each character ('0' -> 0, '1' -> 1).";
4/2fb           "Split into groups of 4 (Nameless commands) and numerically
                 evaluate each group as an array of binary digits.";
{               "While command values remain:";
  (:X             "Grab the next command value.";
  8<              "If the command value is less than 8:";
  "><+-.,[]"X=    "Then: It maps directly to a BF command. Look it up.";
  {               "Else:";
    XA<             "If the command value is less than 10:";
    {("+-"X=*}      "Then: It is 8 or 9. Grab the next command value and
                     produce a string of that many copies of '+' if the former
                     command value is 8, or '-' if it is 9.";
    "[-]"?          "Else: It is 11. Produce its translation, '[-]'.";
  }?
  o               "Output the BF translation.";
}h

```
> 2 votes

# Answer
# Perl - ~~343~~ ~~339~~ 305 bytes

I know CJam's already done it, but I figured I'd try a non-esoteric solution.

```
open(F,$ARGV[0]);%s=qw(0000 > 0001 < 0010 + 0011 - 0100 . 0101 , 0110 [ 0111 ] 1011 [-]);while(<F>){$x=0;$p='';@c=split(' ');foreach$c(@c){if($c=='1000'){for(1..oct("0b".$c[$x+1])){$p.='+'}}elsif($c=='1001'){for(1..oct("0b".$c[$x+1])){$p.='-'}}elsif(exists$s{$c}){$p.=$s{$c}}else{$p.=$c.' '};$x++}print$p}

```

It keeps comments, and prints it without a trailing newline.

If I've missed anything, please let me know.
**Changes**

* Saved 4 bytes by deleting unnecessary characters, and fixed comments.
* Saved 34 bytes by removing checking for `1000`/`1001` at the end of a line. (Credit to mbomb007)
> 1 votes

# Answer
# Python 2, ~~221~~ 216 bytes

Run it here: http://repl.it/hxJ/1

Not sure if it can be golfed more. I had to use a `while` (very annoyingly) instead of a list comprehension for the whole thing, since the iterator must skip an instruction if the instruction is `1000` or `1001`. (By the way, the indentations are tab characters.)

```
import re
b='><+-.,[]'
i=re.sub('[^01]','',input())
n=[int(j,2)for j in re.findall('.'*4,i)]
k=0;o=''
while k<len(n):
    c=n[k]
    if c<8:o+=b[c]
    elif c<10:o+=n[k+1]*('+'if c<9 else'-');k+=1
    else:o+='[-]'
    k+=1
print o

```
> 0 votes

---
Tags: code-golf, brainfuck, binary
---


# Question
Title: Write a program that takes as close to 1 second sharp to execute in your language
Write a program that takes as close to 1 second Wall-time sharp to execute in your language.

Anything goes except to have the processor sleep / pause / wait, by either internal or relying on external processes.

It should be interesting to see that adding one character more somewhere will more easily bring you to the correct time (though obviously at the cost of a character). Think for example to have a for loop run 10000 instead of 1000 times which "costs" 1 character.

**Execution time** will be measured online by ideone.

I guess for an "official time", I'll run a benchmark of say 100 times. Next to a low amount of characters and close to 1.000 seconds, low variance should also earn you street creds.

It might actually be fun to come up with an idea for how much "worth" a character gets in terms of getting closer to 5.00 seconds.

Measures:

1. `abs(5 - execution_time)` (lower better)
2. Number of characters (lower better)
3. Variability (lower better)
4. Cleverness (higher better)
5. Fun (higher better)

# Answer
# Linux shell - 0.999 seconds (19 characters)

```
$ ping -c 2 127.0.0.1
PING 127.0.0.1 (127.0.0.1) 56(84) bytes of data.
64 bytes from 127.0.0.1: icmp_seq=1 ttl=64 time=0.057 ms
64 bytes from 127.0.0.1: icmp_seq=2 ttl=64 time=0.049 ms

--- 127.0.0.1 ping statistics ---
2 packets transmitted, 2 received, 0% packet loss, time 999ms
rtt min/avg/max/mdev = 0.049/0.053/0.057/0.004

```

I got 1000ms on the dot a few times, but 999ms was more common. Perhaps relying on ping's inherent waits between packets to decrease network congestion may cross a line, but in my defense, I didn't write a sleep or busy-wait in my code... I just really wanted a N=2 sample size for my pings. You never know when your sneaky computer might respond to one message and not another!
> 5 votes

# Answer
# Perl: 1.0031 seconds, 16 characters

(An unhandled signal terminates the process, so this code was measured from “outside” with `bash`'s `time`. Result includes the `perl` interpreter's startup time too. :()

```
alarm 1;1while 1

```

# Perl: 1.000059 seconds, 42 characters

(This code was surrounded with `Time::HiRes::gettimeofday()` calls for more accurate measurement.)

```
eval{$SIG{ALRM}=sub{die};alarm 1;1while 1}

```

(No, `alarm` is not a `sleep`. Not works on ideone.)
> 2 votes

# Answer
# Perl - ~~1.0065~~ ~~1.0032~~ 1.0025 seconds

```
for ($i = 0;$i < 11489000;$i++) {
 "Hey, I can see my post from here!";
}

```

Tested using the command `time perl onesecond.pl`, and averaged.
There is also another Perl answer, so it looks like I may have to step up my game...
> 1 votes

# Answer
# **The Hexadecimal Stacking Pseudo-Assembly Language**

Probably the longest program you'll see here at 120. Ranges from (usually; there are some rare cases which are well outside this range for some reason) 0.93 to 1.03 seconds run time (I rigged up a simple timer to my copy of the java interpreter). Pushes 40,960 33s to a stack, prints them all as chars, then halts with status 418.

```
20A000
400000
000000
200021
400100
410000
400200
200001
400000
410200
400000
220000
420000
400000
030000
010001
010000
000001
140100
0401A2

```
> 0 votes

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


# Question
Title: IPV4 subnet list cleaner (in CIDR notation)
We have a lot of IPV4 address, to group into subnets, so we need a tool for doing this:

Our list is very ugly, not ordered and sometime in subnet notation, sometime in simple address.

**Sample:**

```
192.168.5.16/30
192.168.5.18
192.168.2.231/27
192.173.17.0/24
192.168.1.5/32
192.168.5.18/32
192.168.3.0/24
192.168.2.231/27
192.168.2.245/29
192.168.4.0/29
192.173.16.0/24
192.173.18.0/24
192.173.19.0/24
10.100.12.24

```

some explanation about the input (*our old list*):

* each line hold only **1** IPV4 *subnet*
* if a line don't contain any subnet info like on line `2`, it's a single ip, so the 32 bit mask is to be considered.
* subnet info is in the *CIDR* form: `IPV4/integer` where integer is mask length
* IPV4 is not necessarely the *base* (first in range) of subnet
* list is not sorted
* list is not short... could make more the 60k entries...
* there is repetition, overlap of subnets... lot of *useless lines*

( The last is the main reason we need to build this tool! ;-)

From this sample list we want to obtain shortened, sorted and cleaned list like:

```
10.100.12.24/32
192.168.1.5/32
192.168.2.224/27
192.168.3.0/24
192.168.4.0/29
192.168.5.16/30
192.173.16.0/22

```

Where all lines is subnet and all IPV4 part is base IP (begin of range), sorted, and without overlap or repetitions.

And where all IP present somewhere in input is present and no one more!

**CIDR**

For informations about:

**Code golf**

* Input values could be given as you will, (arguments, read from file or STDIN)
* Output to STDOUT, one subnet per line.
* Output has to be sorted by the unsigned integer value of IPV4 (big-endian)
* Output has to contain as few lines as possible
* Of course, sum of output subnet must match sum of input subnet! **no more, nor less!** So `0.0.0.0/0` which override everything is not accepted! (unless it's the only valid answer, see last test)
* Use of libraries forbiden! Standard loophole applies
* Shortest code wins!

**Test cases**

For testing this, (under bash) I use something like:

```
for i in {167772416..167774464};do
     echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&255]
  done

```

as input, this must render:

```
10.0.1.0/24
10.0.2.0/23
10.0.4.0/22
10.0.8.0/24
10.0.9.0/32

```

or

```
for i in {167772416..167774464};do
     [ $i -gt 167773316 ] && [ $i -lt 167773556 ] ||
         echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&255]/30
  done

```

Note, I've added `/30` after each ip. this will do a lot of overlap!

```
10.0.1.0/24
10.0.2.0/23
10.0.4.0/25
10.0.4.128/29
10.0.5.116/30
10.0.5.120/29
10.0.5.128/25
10.0.6.0/23
10.0.8.0/24
10.0.9.0/30

```

Extreme test rule

```
63.168.3.85/2
64.168.3.85/2
192.168.3.85/2
191.168.3.85/2

```

This **special** case must render:

```
0.0.0.0/0

```

**Accepted answers**

As this question seem not so easy, I will add *time from question* to the list

> 1. CJam, 101 \- user23013 - 38 hours
> 2. Perl, 223 \- nutki - 1 week
> 3. Pure bash, 1040 \- F.Hauri - 4 days

# Answer
# CJam, 101 95 94

```
qN/{'//('./1\+256b2b\{i)<}/}%_|{{):T;_aM+:M(a&}gT+}%${_2$#!{;}*}*]{_(!a32*+32<8/2fb'.*'/@,(N}%

```

The `{~}2j` construct didn't make it shorter...

Try it here. (And link for Firefox.)

### Explanation

```
qN/               " Read each line. ";
{                 " For each line: ";
    '//           " Split by / ";
    ('./          " Split first item by . ";
    1\+256b2b     " The address + 2^32 in base 2, which always has length 33 ";
    \{i)<}/       " For each other items N (if any), get the first N+1 bits. ";
}%
_|                " Remove duplicates. ";
{                 " For each item (each array of bits): ";
    {             " Do: ";
        ):T;      " Remove last bit and save it in T. ";
        _aM+:M    " Add the array to M. ";
        (a#)      " Find the array in the original M. ";
    }g            " while it is found. ";
    T+            " Append the last T back. ";
}%
$                 " Sort. ";
{                 " Reduce and wrap in array: ";
    _2$#!         " Test if the previous string is a prefix of the current. ";
     {;}*         " If so, discard it. ";
}*]
{                 " For each item (each array of bits): ";
    _(!a32*+32<   " Remove first bit and pad to 32 bits to the right. ";
    8/2fb'.*      " Convert to IP address. ";
    '/@,(         " Append / and original length - 1. ";
    N             " Append a newline. ";
}%

```
> 3 votes

# Answer
# Perl, 172 ~~223 245~~

Using hashes was not necessary. The removal allowed for a significantly shorter code, though the idea is the same.

```
#!perl -lp0a
$_=join$\,sort map{1x(s/\d*./unpack B8,chr$&/ge>4?$&:32)&$_}@F;1while s/^(.*)
\1.*/$1/m||s/^(.*)0
\1.$/$1/m;s!^.*!(join'.',map{ord}split'',pack B32,$&).'/'.length$&!gme

```

Test me.

Older version with explanation:

```
#!perl -lp0a
s/(^|\.)(\d+)/sprintf"%08b",$2/ge,/\D/&&($_=$`|2x$',y/0-3/##01/)for@F;$_=join$\,sort@F;1while s/^((\d*)#*)
\2.*/$1/mg||s/^(\d*)0(#*)
\1[1]\b#*/$1#$2/mg;s!.+!$&.'/'.$&=~y/01//!ge;y/#/0/;s!\d{8}\B!$&.!g;s!\d{8}!"0b$&"!gee

```

Test me.

First convert input to textual format (`s/(^|\.)(\d+)/sprintf"%08b",$2/ge,/\D/&&($_=$p|2x$',y/0-3/##01/)`):

```
00##############################
01##############################
11##############################
10##############################

```

Sort it (`$_=join$\,sort@F`):

```
00##############################
01##############################
10##############################
11##############################

```

Clean using two regexps: one to remove duplicates and more specific addresses and the second to join two adjacent networks into one with a longer mask (`s/^((\d*)#*)\n\2.*/$1/mg` and `s/^(\d*)0(#*)\n\1[1]\b#*/$1#$2/mg`).

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

```

And convert back to the original form (`s!.+!$&.'/'.$&=~y/01//!ge;y/#/0/;s!\d{8}\B!$&.!g;s!\d{8}!"0b$&"!gee`):

```
0.0.0.0/0

```
> 3 votes

# Answer
## Ruby - 425

(broken - see comment below)

```
a=(0..32).map{[]}
l=->m{2**m-1<<32-m}
$<.map{|i|/\//=~i=i[?/]?i:i.chop+'/32'
s=$'.to_i
n=$`.split(?.).inject(0){|v,d|v*256+d.to_i}
next if s.times.any?{|t|a[t].any?{|e|n&l[t]==e[1]}}
s.upto(32){|t|a[t].reject!{|e|e[1]&l[s]==n}}
a[s]<<[i,n]
(b=k=n&l[s]
break if(y=a[s+1].select{|e|e[1]&l[s]==b}).size<2
a[s+1]-=y
a[s]<<[(0..3).map{k,i=k.divmod(256);i}.reverse*?.+?/+s.to_s,b])until(s-=1)<0}
puts a.flatten(1).sort_by{|v|v.pop}

```
> 1 votes

# Answer
### Pure bash ~~1100~~ ~~1079~~ 1040

**Edited:** A little ~~better~~ more *golfed*!

```
#!/bin/bash -i
alias d=done e=unset f=printf\ -v g=local h=else i=then j=for k=while C=do E=fi
n(){ g s e i;j i in ${!u[@]};C [ $1 -ge $[i+1] ]&&[ $1 -le $[u[i]+1] ]&&s=$i
[ $2 -ge $[i-1] ]&&[ $2 -le $[u[i]-1] ]&&e=$i;d;if [ "$s" ];i if [ "$e" ];i \
[ $s -ne $e ]&&{ u[s]=${u[e]};e u[e];};h [ $1 -lt $s ]&&{ u[$1]=${u[s]};e u[s
];s=$1;};[ $2 -gt ${u[s]} ]&&u[s]=$2;E;h if [ "$e" ];i [ $1 -lt $e ]&&{ u[$1
]=${u[e]};e u[e];e=$1;};[ $2 -gt ${u[e]} ]&&u[e]=$2;h u[$1]=$2;E;E;};q(){
g s=${1#*/} m=${1%/*} z;[ -z "${s//*.*}" ]&&s=32;y $s z;set -- ${m//./ }
m=$[$1<<24|$2<<16|$3<<8|$4];n $[m&z] $[m|((2**32-1)^z)];};y(){ f $2 "%u" $[ (
2**32-1)^(~0^~0<<(32-$1))];};r(){ f $2 "%s" $[$1>>24].$[$1>>16&255].$[$1>>8&
255].$[$1&255];};t(){ g s z;k [ "$1" ];C s=32;k y $[s-1] z&&[ $1 = $[($1>>(33
-s))<<(33-s)] ]&&[ $2 -ge $[$1|((2**32-1)^z)] ];C ((s--));d;r $1 x;echo $x/$s
y $s z;if [ $2 -gt $[$1|((2**32-1)^z)] ];i set -- $[1+($1|((2**32-1)^z))] $2
h shift 2;E;d;};k read w;C q $w;d;p=-1;j o in ${!u[@]};C [ $o -gt $p ]&&p=${u[
o]}&&t $o ${u[o]};d

```

which work quickly, even on wide ranges!

```
./myscript.sh <<<"63.168.3.85/2\n64.168.3.85/2\n192.168.3.85/2\n191.168.3.85/2"
0.0.0.0/0

./myscript.sh < <(for i in {167772416..167774464};do
     [ $i -gt 167773316 ] && [ $i -lt 167773556 ] ||
         echo $[i>>24].$[i>>16&255].$[i>>8&255].$[i&255]/30
   done)
10.0.1.0/24
10.0.2.0/23
10.0.4.0/25
10.0.4.128/29
10.0.5.116/30
10.0.5.120/29
10.0.5.128/25
10.0.6.0/23
10.0.8.0/24
10.0.9.0/30

```
> 0 votes

# Answer
### Javascript ~1335

While total js is 2009, the essential part is contained in two function and main routine. html, css and ~674 chars of javascript in only cosmetic.

```
var g={};function B(){document.getElementById('z').addEventListener('click',go);
window.addEventListener('resize',C);C();}function C(){document.getElementById('y'
).setAttribute('style','height:'+(window.innerHeight-46-document.getElementById(
'y').offsetTop).toFixed(0)+"px");document.getElementById('x').setAttribute(
'style','height:'+(window.innerHeight-46-document.getElementById('x').offsetTop
).toFixed(0)+"px");}function go(){document.getElementById('y').innerHTML='';
document.getElementById('A').innerHTML='...running...';w()
}function u(q,j){var o=Object.keys(g).sort(function(a,b){return a-b}),s,e;for(var
i=0;i<o.length;i++){if((q*1>=o[i]*1+1)&(q<=g[o[i]]*1+1))s=1*o[i];if((j*1>=o[i]-1
)&(j<=g[o[i]]-1))e=1*o[i]};if(typeof(s)!=='undefined'){if(typeof(e)!=='undefined'
){if(1*s<1*e){g[s]=g[e];delete g[e]}}else{if(1*q<1*s){g[q]=g[s];delete g[s];s=q};
if(1*j>1*g[s])g[s]=j}}else{if(typeof(e)!=='undefined'){if(1*q<1*e){g[q]=g[e];
delete g[e];e=q};if(1*j>1*g[e])g[e]=j}else{g[q]=j}}}function v(f,p){var e,ie,c=''
;while(typeof(f)!=='undefined'){e=32;while((ie=(~0<<(33-e))>>>0)&&(f==((f>>(33-e)
)<<(33-e))>>>0)&&(p>=(((~0<<32)^ie)|f)>>>0)&&(e>0))e--;c+=(f>>24&255)+"."+(f>>16&
255)+"."+(f>>8&255)+"."+(f&255);c+='/'+e+'<br/>';ie=e>0?(~0<<(32-e))>>>0:0;if(p>(
(f|(~0<<32)^ie))>>>0){var d=f;f=1*1+((f|((~0<<32)^ie))>>>0)}else{f=undefined}}
return c}function w(){var l=[];g={};document.getElementById('A').innerHTML+=
'<br/>reading...';var n=document.getElementById('x').value.split("\n");for(var
i=0;i<n.length;i++){if(!n[i].match("/"))n[i]+="/32";var s=n[i].match(
/(\d+)\.(\d+)\.(\d+)\.(\d+)\/(\d+)/);if((s)&&(s.length==6)){var k=(s[1]<<24|s[2]
<<16|s[3]<<8|s[4])>>>0;var e=(~0<<(32-s[5]))>>>0;var t=(~0&k&e)>>>0;var r=(((~0
<<32)^e)|t)>>>0;u(t,r);}};var o=Object.keys(g).sort(function(a,b){return a-b});
var h=-1;for(i=0;i<o.length;i++){if(1*o[i]>1*h){h=g[o[i]];document.getElementById
('y').innerHTML+=v(o[i],g[o[i]]);}}document.getElementById('A').innerHTML+=
'<br/>printing...'};window.onload=B;
```

```
body{font-family:Sans;background:#9ac;}#z{position:absolute;top:3em;right:2%;}
span button, span input{font-size:.63em;}#A{width:50%;min-height:3.4em;background:
#679;border:1px solid black;border-color:white black black white;border-radius:
.5em;padding:.2em 1em .2em 1em;margin:1em 0px .1em 0px;margin-left:24%;color:
#cdf;box-shadow: 2px 2px 4px black;}#y{width:72%;overflow:auto;margin-left:24%;
background:#bce;padding:1em;border-radius:.8em;border:1px solid black;box-shadow:
2px 2px 4px;border-color:white black black white;}#x{position:fixed;top:1.5em;
left:1%;padding:1em;width:18%;anchor:left;height:33em;border-radius:.3em;border:
1px solid black;border-color:white black black white;box-shadow:2px 2px 4px;}
```

```
<button id="z"> GO </button><textarea id="x"></textarea><div id="A">---</div><pre id="y"></pre>
```
> 0 votes

---
Tags: code-golf, array, networking
---


title: IMP: Implicit multiplication parser

text:
# Question
Title: IMP: Implicit multiplication parser
Jack likes the C programming language, but hates writing expressions like `V=a*b\*h;` to multiply values.

He would like to just write `V=abh;` instead; why should the compiler moan about `abh` being undefined? Since `int a, b, h;` are defined, can't it just deduce multiplication? Help him implement a parser that deciphers a single multiplication term, provided the set of variables defined in current scope is known.

For simplicity, no numbers will be included (i.e. `2abh`), only single-character variables.

The input is **a multiplication term T**, fulfilling regexp:

```
[a-zA-Z_][a-zA-Z_0-9]*

```

**and a variable set Z**  .

A parsing P of the term T over variable set Z is a string fulfilling the following conditions:

1. P can be turned back into T by removing all `*` characters
2. The string either is a variable name from Z or consists of proper variable names from Z split up by single `*` characters.

The solution should print all possible ways to parse the input.

Examples:

```
Vars           a, c, ab, bc
Term           abc
Solution       ab*c, a*bc

Vars           ab, bc
Term           abc
Solution       -

Vars           -
Term           xyz
Solution       -

Vars           xyz
Term           xyz
Solution       xyz

Vars           width, height
Term           widthheight
Solution       width*height

Vars           width, height
Term           widthheightdepth
Solution       -

Vars           aaa, a
Term           aaaa
Solution       aaa*a, a*aaa, a*a*a*a

```

The input (the list of variables and the term) may be supplied in any way suitable for the language.

The output can be in any sensible form (one result per line or a comma-separated list etc.) - but it should be unambiguous and possible to read.

Empty output is acceptable if there is no possible parsing of a term (in the examples I used '-' for clarity).

This is , so the shortest code wins.

# Answer
# Pyth, 18 chars

```
mj\*dfqzsTsm^Qkhlz

```

This solution is adapted from my Interpreting Fish solution. The problems are actually very similar.

Expects input as such:

```
aaaa
"a", "aaa"

```

Gives output like this:

```
['a*aaa', 'aaa*a', 'a*a*a*a']

```

Try it here.

* `sm^Qkhlz`: Generates all sequences of variables containing up to the length of the input string number of variables.
* `fqzsT`: Filters out the variable sequences that match the input string
* `mj\*d`: Inserts the `*` symbol and prints.
> 4 votes

# Answer
# Python 2 - ~~147~~ 94 bytes

---

```
R=lambda S,V,F=[]:S and[R(S[len(v):],V,F+[v])for v in V if v==S[:len(v)]]or print("*".join(F))

```

This defines a function `R` to be used like:

```
>>> R("abc", ["a", "bc", "ab", "c"])

```

Prints output like:

```
a*bc
ab*c

```
> 3 votes

# Answer
# JavaScript (ES6) 111

Adapted from my "fish" answer, the main difference is finding all solutions, not just the first.

```
F=(v,t)=>(k=(s,r)=>s?v.map(v=>s.slice(0,l=v.length)==v&&k(s.slice(l),[...r,v])):console.log(r.join('*')))(t,[])

```

The output is printed to the console. The function result have no meaning and must be discarded.

**Test** In Firefox/FireBug console

```
F(['a','c','ab','bc'],'abc')
a*bc
ab*c

F(['ab','bc'],'abc')

F(['aaa','a'],'aaaa')
aaa*a
a*aaa
a*a*a*a

F(['xyz'],'xyz')
xyz

```
> 1 votes

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