# Question
Title: Build a Nonographic Magnitude Optimizer™
A nonogram is a Japanese puzzle game in which the goal is to draw a black-and-white picture according to a list of contiguous regions, like so:

Define the *nonographic magnitude* of a row or column to be the number of contiguous black regions in that row or column. For example, the top row has a nonographic magnitude of 1, because there is one region of 2 squares in that row. The 8th row has a nonographic magnitude of 3 because it has 2, 2, 1.

An empty row or column has a nonographic magnitude of 0.

---

Your task is to write a program that takes a solution grid for a nonogram, and produces a solution grid with *as few filled-in squares as possible* where every row and column has the same nonographic magnutide as the given solution grid.

For example, a nonogram grid with all the squares filled in has a nonographic magnitude of 1 on every row or column:

The same nonographic magnitude could be achieved just by having a diagonal stripe through the grid, reducing the number of filled-in squares dramatically:

---

Your program will receive an input consisting of 50,000 lines from this file (1.32 MB tar.gz text file; 2.15 MB unzipped), each representing a single 16×16 nonogram solution grid with randomly (80% black) filled-in squares, and output another 50,000 lines, each containing the optimized solution grid for the corresponding input grid.

Each grid is represented as a base64 string with 43 characters (encoding squares from left to right, then top to bottom), and your program will need to return its output in the same format. For example, the first grid in the file is `E/lu/+7/f/3rp//f799xn/9//2mv//nvj/bt/yc9/40=`, and renders as:

The grid starts with `E` which maps to `000100`, so the first six cells in the top row are all white except the fourth one. The next character is `/` which maps to `111111`, so the next 6 cells are all black — and so on.

---

Your program must actually return a solution grid with the correct nonographic magnitudes for each of the 50,000 test cases. It is allowed to return the same grid as the input if nothing better was found.

The program to return the fewest total filled-in squares (in any language) is the winner, with shorter code being the tiebreaker.

---

Current scoreboard:

1. 3,637,260 — Sleafar, Java
2. 7,270,894 — flawr, Matlab
3. 10,239,288 — Joe Z., Bash

# Answer
> 8 votes
## Python 2 & PuLP — 2,644,688 squares (optimally minimized); 10,753,553 squares (optimally maximized)

## Minimally golfed to 1152 bytes

```
from pulp import*
x=0
f=open("c","r")
g=open("s","w")
for k,m in enumerate(f):
 if k%2:
    b=map(int,m.split())
    p=LpProblem("Nn",LpMinimize)
    q=map(str,range(18))
    ir=q[1:18]
    e=LpVariable.dicts("c",(q,q),0,1,LpInteger)
    rs=LpVariable.dicts("rs",(ir,ir),0,1,LpInteger)
    cs=LpVariable.dicts("cs",(ir,ir),0,1,LpInteger)
    p+=sum(e[r][c] for r in q for c in q),""
    for i in q:p+=e["0"][i]==0,"";p+=e[i]["0"]==0,"";p+=e["17"][i]==0,"";p+=e[i]["17"]==0,""
    for o in range(289):i=o/17+1;j=o%17+1;si=str(i);sj=str(j);l=e[si][str(j-1)];ls=rs[si][sj];p+=e[si][sj]<=l+ls,"";p+=e[si][sj]>=l-ls,"";p+=e[si][sj]>=ls-l,"";p+=e[si][sj]<=2-ls-l,"";l=e[str(i-1)][sj];ls=cs[si][sj];p+=e[si][sj]<=l+ls,"";p+=e[si][sj]>=l-ls,"";p+=e[si][sj]>=ls-l,"";p+=e[si][sj]<=2-ls-l,""
    for r,z in enumerate(a):p+=lpSum([rs[str(r+1)][c] for c in ir])==2*z,""
    for c,z in enumerate(b):p+=lpSum([cs[r][str(c+1)] for r in ir])==2*z,""
    p.solve()
    for r in ir:
     for c in ir:g.write(str(int(e[r][c].value()))+" ")
     g.write('\n')
    g.write('%d:%d\n\n'%(-~k/2,value(p.objective)))
    x+=value(p.objective)
 else:a=map(int,m.split())
print x

```

(NB: the heavily indented lines start with tabs, not spaces.)

Example output: https://drive.google.com/file/d/0B-0NVE9E8UJiX3IyQkJZVk82Vkk/view?usp=sharing

It turns out that problems like are readily convertible to Integer Linear Programs, and I needed a basic problem to learn how to use PuLP—a python interface for a variety of LP solvers—for a project of my own. It also turns out that PuLP is extremely easy to use, and the ungolfed LP builder worked perfectly the first time I tried it.

The two nice things about employing a branch-and-bound IP solver to do the hard work of solving this for me (other than not having to implement a branch and bound solver) are that

* Purpose-built solvers are really fast. This program solves all 50000 problems in about 17 hours on my relatively low-end home PC. Each instance took from 1-1.5 seconds to solve.
* They produce guaranteed optimal solutions (or tell you that they failed to do so). Thus, I can be confident that no one will beat my score in squares (although someone might tie it and beat me on the golfing part).

## How to use this program

First, you'll need to install PuLP. `pip install pulp` should do the trick if you have pip installed.

Then, you'll need to put the following in a file called "c": https://drive.google.com/file/d/0B-0NVE9E8UJiNFdmYlk1aV9aYzQ/view?usp=sharing

Then, run this program in any late Python 2 build from the same directory. In less than a day, you'll have a file called "s" which contains 50,000 solved nonogram grids (in readable format), each with the total number of filled squares listed below it.

If you'd like to maximize the number of filled squares instead, change the `LpMinimize` on line 8 to `LpMaximize` instead. You will get output very much like this: https://drive.google.com/file/d/0B-0NVE9E8UJiYjJ2bzlvZ0RXcUU/view?usp=sharing

## Input format

This program uses a modified input format, since Joe Z. said that we would be allowed to re-encode the input format if we like in a comment on the OP. Click the link above to see what it looks like. It consists of 10000 lines, each containing 16 numbers. The even numbered lines are the magnitudes for the rows of a given instance, while the odd numbered lines are the magnitudes for the columns of the same instance as the line above them. This file was generated by the following program:

```
from bitqueue import *

with open("nonograms_b64.txt","r") as f:
    with open("nonogram_clues.txt","w") as g:
        for line in f:
            q = BitQueue(line.decode('base64'))
            nonogram = []
            for i in range(256):
                if not i%16: row = []
                row.append(q.nextBit())
                if not -~i%16: nonogram.append(row)
            s=""
            for row in nonogram:
                blocks=0                         #magnitude counter
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print >>g, s
            nonogram = map(list, zip(*nonogram)) #transpose the array to make columns rows
            s=""
            for row in nonogram:
                blocks=0
                for i in range(16):
                    if row[i]==1 and (i==0 or row[i-1]==0): blocks+=1
                s+=str(blocks)+" "
            print >>g, s

```

(This re-encoding program also gave me an extra opportunity to test my custom BitQueue class I created for the same project mentioned above. It is simply a queue to which data can be pushed as sequences of bits OR bytes, and from which data can be popped either a bit or a byte at a time. In this instance, it worked perfectly.)

I re-encoded the input for the specific reason that to build an ILP, the extra information about the grids that were used to generate the magnitudes is perfectly useless. The magnitudes are the only constraints, and so the magnitudes are all I needed access to.

## Ungolfed ILP builder

```
from pulp import *
total = 0
with open("nonogram_clues.txt","r") as f:
    with open("solutions.txt","w") as g:
        for k,line in enumerate(f):
            if k%2:
                colclues=map(int,line.split())
                prob = LpProblem("Nonogram",LpMinimize)
                seq = map(str,range(18))
                rows = seq
                cols = seq
                irows = seq[1:18]
                icols = seq[1:18]
                cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
                rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
                colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)
                prob += sum(cells[r][c] for r in rows for c in cols),""
                for i in rows:
                    prob += cells["0"][i] == 0,""
                    prob += cells[i]["0"] == 0,""
                    prob += cells["17"][i] == 0,""
                    prob += cells[i]["17"] == 0,""
                for i in range(1,18):
                    for j in range(1,18):
                        si = str(i); sj = str(j)
                        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
                        prob += cells[si][sj] <= l + ls,""
                        prob += cells[si][sj] >= l - ls,""
                        prob += cells[si][sj] >= ls - l,""
                        prob += cells[si][sj] <= 2 - ls - l,""
                        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
                        prob += cells[si][sj] <= l + ls,""
                        prob += cells[si][sj] >= l - ls,""
                        prob += cells[si][sj] >= ls - l,""
                        prob += cells[si][sj] <= 2 - ls - l,""
                for r,clue in enumerate(rowclues):
                    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
                for c,clue in enumerate(colclues):
                    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""
                prob.solve()
                print "Status for problem %d: "%(-~k/2),LpStatus[prob.status]
                for r in rows[1:18]:
                    for c in cols[1:18]:
                        g.write(str(int(cells[r][c].value()))+" ")
                    g.write('\n')
                g.write('Filled squares for %d: %d\n\n'%(-~k/2,value(prob.objective)))
                total += value(prob.objective)
            else:
                rowclues=map(int,line.split())
print "Total number of filled squares: %d"%total

```

This is the program that actually produced the "example output" linked above. Hence the extra long strings at the end of each grid, which I truncated when golfing it. (The golfed version should produce identical output, minus the words `"Filled squares for "`)

## How it Works

```
cells = LpVariable.dicts("cell",(rows,cols),0,1,LpInteger)
rowseps = LpVariable.dicts("rowsep",(irows,icols),0,1,LpInteger)
colseps = LpVariable.dicts("colsep",(irows,icols),0,1,LpInteger)

```

I use an 18x18 grid, with the center 16x16 part being the actual puzzle solution. `cells` is this grid. The first line creates 324 binary variables: "cell\_0\_0", "cell\_0\_1", and so on. I also create grids of the "spaces" between and around the cells in the solution part of the grid. `rowseps` points to the 289 variables which symbolize the spaces that separate cells horizontally, while `colseps` similarly points to variables that mark the spaces that separate cells vertically. Here's a unicode diagram:

```
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|□|0
  - - - - - - - - - - - - - - - -
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

```

The `0`s and s are the binary values tracked by the `cell` variables, the `|`s are the binary values tracked by the `rowsep` variables, and the `-`s are the binary values tracked by the `colsep` variables.

```
prob += sum(cells[r][c] for r in rows for c in cols),""

```

This is the objective function. Just the sum of all the `cell` variables. Since these are binary variables, this is just exactly the number of filled squares in the solution.

```
for i in rows:
    prob += cells["0"][i] == 0,""
    prob += cells[i]["0"] == 0,""
    prob += cells["17"][i] == 0,""
    prob += cells[i]["17"] == 0,""

```

This just sets the cells around the outer edge of the grid to zero (which is why I represented them as zeroes above). This is the most expedient way to track how many "blocks" of cells are filled, since it ensures that every change from unfilled to filled (moving across a column or row) is matched by a corresponding change from filled to unfilled (and vice versa), even if the first or last cell in the row is filled. This is the sole reason for using an 18x18 grid in the first place. It's not the only way to count blocks, but I think it is the simplest.

```
for i in range(1,18):
    for j in range(1,18):
        si = str(i); sj = str(j)
        l = cells[si][str(j-1)]; ls = rowseps[si][sj]
        prob += cells[si][sj] <= l + ls,""
        prob += cells[si][sj] >= l - ls,""
        prob += cells[si][sj] >= ls - l,""
        prob += cells[si][sj] <= 2 - ls - l,""
        l = cells[str(i-1)][sj]; ls = colseps[si][sj]
        prob += cells[si][sj] <= l + ls,""
        prob += cells[si][sj] >= l - ls,""
        prob += cells[si][sj] >= ls - l,""
        prob += cells[si][sj] <= 2 - ls - l,""

```

This is the real meat of the logic of the ILP. Basically it requires that each cell (other than those in the first row and column) be the logical xor of the cell and separator directly to its left in its row and directly above it in its column. I got the constraints that simulate an xor within a {0,1} integer program from this wonderful answer: https://cs.stackexchange.com/a/12118/44289

To explain a bit more: this xor constraint makes it so that the separators can be 1 if and only if they lie between cells which are 0 and 1 (marking a change from unfilled to filled or vice versa). Thus, there will be exactly twice as many 1-valued separators in a row or column as the number of blocks in that row or column. In other words, the sum of the separators on a given row or column is exactly twice the magnitude of that row/column. Hence the following constraints:

```
for r,clue in enumerate(rowclues):
    prob += lpSum([rowseps[str(r+1)][c] for c in icols]) == 2 * clue,""
for c,clue in enumerate(colclues):
    prob += lpSum([colseps[r][str(c+1)] for r in irows]) == 2 * clue,""

```

And that's pretty much it. The rest just asks the default solver to solve the ILP, then formats the resulting solution as it writes it to the file.

# Answer
> 3 votes
# Java, ~~6,093,092~~ ~~4,332,656~~ 3,637,260 squares (minimized), ~~10,567,550~~ ~~10,567,691~~ 10,568,746 squares (maximized)

Both variants of the program repeatedly perform operations on the source grid, without changing the magnitude.

## Minimizer

### shrink()

If a black square has 2 white neighbors and 2 black neighbors in a 90° angle, it can be replaced by a white square.

### moveLine()

In configurations like above the black line can be moved to the right. This is done repeatedly for all 4 line directions clockwise and counterclockwise, to open up new shrink possibilities.

## Maximizer

Uncomment the line in `main()` and comment out the line above it for this version.

### grow()

If a white square has 2 white neighbors and 2 black neighbors in a 90° angle, it can be replaced by a black square.

### moveLine()

Same as in Minimizer.

## Source

```
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.util.Arrays;
import java.util.Base64;
import java.util.function.Function;

public class Main {
    private static final int SIZE = 16;
    private static final int SIZE_4 = SIZE + 4;
    private static final int E = 0;
    private static final int N = 1;
    private static final int W = 2;
    private static final int S = 3;

    private static final Base64.Decoder decoder = Base64.getMimeDecoder();
    private static final Base64.Encoder encoder = Base64.getMimeEncoder();
    private static int sourceBlack = 0;
    private static int targetBlack = 0;

    private static class Nonogram {
        private final boolean[] cells = new boolean[SIZE_4 * SIZE_4];
        private final int[] magnitudes;

        public Nonogram(String encoded) {
            super();
            byte[] decoded = decoder.decode(encoded);
            for (int i = 0; i < decoded.length; ++ i) {
                for (int j = 0; j < 8; ++ j) {
                    if ((decoded[i] & (1 << (7 - j))) != 0) {
                        int k = i * 8 + j;
                        cells[getPos(k / SIZE, k % SIZE)] = true;
                        ++ sourceBlack;
                    }
                }
            }
            magnitudes = calcMagnitudes();
        }

        private int getPos(int row, int col) {
            return (row + 2) * SIZE_4 + col + 2;
        }

        private int move(int pos, int dir, int count) {
            switch (dir) {
                case E: return pos + count;
                case N: return pos - count * SIZE_4;
                case W: return pos - count;
                case S: return pos + count * SIZE_4;
                default: return pos;
            }
        }

        private int move(int pos, int dir) {
            return move(pos, dir, 1);
        }

        private int[] calcMagnitudes() {
            int[] result = new int[SIZE * 2];
            for (int row = 0; row < SIZE; ++ row) {
                for (int col = 0; col < SIZE; ++ col) {
                    int pos = getPos(row, col);
                    if (cells[pos]) {
                        if (!cells[move(pos, W)]) {
                            ++ result[row + SIZE];
                        }
                        if (!cells[move(pos, N)]) {
                            ++ result[col];
                        }
                    }
                }
            }
            return result;
        }

        private boolean isBlack(int pos) {
            return cells[pos];
        }

        private boolean isWhite(int pos) {
            return !cells[pos];
        }

        private boolean allBlack(int pos, int dir, int count) {
            int p = pos;
            for (int i = 0; i < count; ++ i) {
                if (isWhite(p)) {
                    return false;
                }
                p = move(p, dir);
            }
            return true;
        }

        private boolean allWhite(int pos, int dir, int count) {
            int p = pos;
            for (int i = 0; i < count; ++ i) {
                if (isBlack(p)) {
                    return false;
                }
                p = move(p, dir);
            }
            return true;
        }

        private int findWhite(int pos, int dir) {
            int count = 0;
            int p = pos;
            while (cells[p]) {
                ++ count;
                p = move(p, dir);
            }
            return count;
        }

        @SafeVarargs
        private final void forEach(Function<Integer, Boolean>... processors) {
            outer:
            for (;;) {
                for (Function<Integer, Boolean> processor : processors) {
                    for (int row = 0; row < SIZE; ++ row) {
                        for (int col = 0; col < SIZE; ++ col) {
                            if (processor.apply(getPos(row, col))) {
                                continue outer;
                            }
                        }
                    }
                }
                return;
            }
        }

        private boolean shrink(int pos) {
            if (cells[pos] && cells[move(pos, W)] != cells[move(pos, E)] &&
                    cells[move(pos, N)] != cells[move(pos, S)]) {
                cells[pos] = false;
                return true;
            }
            return false;
        }

        private boolean grow(int pos) {
            if (!cells[pos] && cells[move(pos, W)] != cells[move(pos, E)] &&
                    cells[move(pos, N)] != cells[move(pos, S)]) {
                cells[pos] = true;
                return true;
            }
            return false;
        }

        private boolean moveLine(boolean clockwise, int dir, int sourcePos) {
            int from = (dir + (clockwise ? 1 : 3)) % 4;
            int to = (dir + (clockwise ? 3 : 1)) % 4;
            int opp = (dir + 2) % 4;
            if (isBlack(sourcePos) && isWhite(move(sourcePos, from)) && isWhite(move(sourcePos, dir))) {
                int toCount = findWhite(move(move(sourcePos, dir), to), to) + 1;
                if (allWhite(move(sourcePos, to), to, toCount + 1)) {
                    int lineCount = 1;
                    int tmpPos = move(sourcePos, opp);
                    while (isBlack(tmpPos) && isWhite(move(tmpPos, from)) && allWhite(move(tmpPos, to),  to, toCount + 1)) {
                        ++ lineCount;
                        tmpPos = move(tmpPos, opp);
                    }
                    if (allBlack(tmpPos, to, toCount + 1)) {
                        tmpPos = sourcePos;
                        for (int j = 0; j < lineCount; ++ j) {
                            cells[tmpPos] = false;
                            cells[move(tmpPos, to, toCount)] = true;
                            tmpPos = move(tmpPos, opp);
                        }
                        return true;
                    }
                }
            }
            return false;
        }

        public Nonogram minimize() {
            for (int i = 0; i < 5; ++ i) {
                forEach(pos -> shrink(pos), pos -> moveLine(true, E, pos), pos -> moveLine(true, N, pos),
                        pos -> moveLine(true, W, pos), pos -> moveLine(true, S, pos));
                forEach(pos -> shrink(pos), pos -> moveLine(false, E, pos), pos -> moveLine(false, N, pos),
                        pos -> moveLine(false, W, pos), pos -> moveLine(false, S, pos));
            }
            return this;
        }

        public Nonogram maximize() {
            for (int i = 0; i < 5; ++ i) {
                forEach(pos -> grow(pos), pos -> moveLine(true, E, pos), pos -> moveLine(true, N, pos),
                        pos -> moveLine(true, W, pos), pos -> moveLine(true, S, pos));
                forEach(pos -> grow(pos), pos -> moveLine(false, E, pos), pos -> moveLine(false, N, pos),
                        pos -> moveLine(false, W, pos), pos -> moveLine(false, S, pos));
            }
            return this;
        }

        public String toBase64() {
            if (!Arrays.equals(magnitudes, calcMagnitudes())) {
                throw new RuntimeException("Something went wrong!");
            }
            byte[] decoded = new byte[SIZE * SIZE / 8];
            for (int i = 0; i < decoded.length; ++ i) {
                for (int j = 0; j < 8; ++ j) {
                    int k = i * 8 + j;
                    if (cells[getPos(k / SIZE, k % SIZE)]) {
                        decoded[i] |= 1 << (7 - j);
                        ++ targetBlack;
                    }
                }
            }
            return encoder.encodeToString(decoded);
        }

        @Override
        public String toString() {
            StringBuilder b = new StringBuilder();
            for (int row = 0; row < SIZE; ++ row) {
                for (int col = 0; col < SIZE; ++ col) {
                    b.append(cells[getPos(row, col)] ? '#' : ' ');
                }
                b.append('\n');
            }
            return b.toString();
        }
    }

    public static void main(String[] args) throws Exception {
        try (BufferedWriter writer = new BufferedWriter(new FileWriter("solutions_b64.txt"));
                BufferedReader reader = new BufferedReader(new FileReader("nonograms_b64.txt"))) {
            String line;
            while ((line = reader.readLine()) != null) {
                writer.write(new Nonogram(line).minimize().toBase64() + "\n");
                //writer.write(new Nonogram(line).maximize().toBase64() + "\n");
            }
        }
        System.out.printf("%d -> %d", sourceBlack, targetBlack);
    }
}

```

# Answer
> 2 votes
# Bash — 10,239,288 squares

As a last-place reference solution:

```
cp nonograms_b64.txt solutions_b64.txt

```

Since your program is allowed to return the same grid if it can't find a better solution, printing out the whole file verbatim is also valid.

There are a total of 10,239,288 black squares in the test file, which is pretty close to the 10,240,000 you'd expect from 80% of squares filled in out of 50,000 grids with 256 squares each. As usual with my test-battery questions, I've selected the number of test cases with the expectation that the optimal scores will be around the 2-million range, although I suspect the scores will be closer to 4 or 5 million this time around.

---

If anyone can create a solution that *maximizes* the black squares rather than minimizing them and manages to get over 10,240,000, I might consider giving it a bounty.

# Answer
> 1 votes
# Matlab, 7,270,894 squares (~71% of original)

Idea is a simple repeated greedy search: For every black square, try if you can set it to white without changing the nonographic magnitudes. Repeat this twice. (You could achieve way better results with more repetitions, but not for free: It results in an correspondingly longer runtime. Now it was about 80 minutes. I would do that, if we would not have to compute all 50k testcases...)

Here the code (each function in a separate file, as usual.)

```
function D = b64decode(E)
% accepts a string of base 64 encoded data, and returns a array of zeros
% and ones
F = E;
assert( mod(numel(E),4)==0 && 0 <= sum(E=='=') && sum(E=='=') <= 2,'flawed base 64 code')

F('A' <= E & E<= 'Z') = F('A' <= E & E<= 'Z') -'A';       %upper case
F('a' <= E & E<= 'z') = F('a' <= E & E<= 'z') -'a' + 26;  %lower case
F('0'<= E & E <= '9') = F('0'<= E & E <= '9') -'0' + 52;  %digits
F( E == '+') = 62;
F( E == '/') = 63;
F( E == '=') = 0;

D=zeros(1,numel(E)*3*8/4);

for k=1:numel(E);
    D(6*(k-1)+1 + (0:5)) = dec2bin(F(k),6)-'0';
end

if E(end) == '=';
    D(end-7:end) = [];
    if E(end-1) == '=';
        D(end-7:end) = [];
    end
end
end

function E = b64encode(D)
assert(mod(numel(D),8)==0,'flawed byte code');
N=0;
while mod(numel(D),6) ~= 0;
    D = [D,zeros(1,8)];
    N = N+1;
end
dict = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/';

E=zeros(1,numel(D)/6)+'=';
for k=0:numel(E)-N-1;
    E(k+1) = dict(bin2dec( [D(6*k+(1:6))+'0',''] ) + 1);
end

E = [E,''];
end

function [B,T,O] = reduce_greedy(N)
% reduce greedily
NM = nomographic_magnitude(N);
B = N; %current best
M = N;
T = nnz(N); %current number of filled squares
O = T;

for r=1:2;  %how many repetitions
    I = find(B);
    for k=1:numel(I);
        M = B;
        M( I(k) ) = 0;
        %check whether we have a valid solution
        if all(NM == nomographic_magnitude(M))
            if T > nnz(M); %did we actually reduce the number of filled squares?
                B = M;
                T = nnz(M);
            end
        end
    end
end

%% main file
string_in = fileread('nonograms_b64.txt');
string_out = string_in;
tic
total_new = 0;  %total number of black squares
total_old = 0;
M = 50000;
for k=1:M;
    disp(k/M); %display the progress
    line = string_in(45*(k-1)+(1:44));
    decoded = b64decode(line);
    nonogram = reshape(decoded,16,[]) ;%store nonogram as a matrix
    [B,T,O] = reduce_greedy(nonogram);
    disp([nnz(B),nnz(nonogram)])
    total_new = total_new + T;
    total_old = total_old + O;
    string_in(45*(k-1)+(1:44)) = b64encode(B(:).');
end
toc
F = fopen('nonograms_b64_out.txt','w');
fprintf(F,string_out);
%%
disp([total_new,total_old])

```

---
Tags: puzzle-solver, test-battery
---


title: Putting square pegs into square holes

text:
# Question
Title: Putting square pegs into square holes
I was intrigued by the design of this graphic from the New York Times, in which each US state is represented by a square in a grid. I wondered whether they placed the squares by hand or actually found an optimal placement of squares (under some definition) to represent the positions of the contiguous states.

Your code is going to take on a small part of the challenge of optimally placing squares to represent states (or other arbitrary two-dimensional shapes.) Specifically, it's going to assume that we already have all the geographic centers or centroids of the shapes in a convenient format, and that the optimal representation of the data in a diagram like this is the one in which the total distance from the centroids of the shapes to the centers of the squares that represent them is minimal, with at most one square in each possible position.

Your code will take a list of unique pairs of floating-point X and Y coordinates from 0.0 to 100.0 (inclusive) in any convenient format, and will output the non-negative integer coordinates of unit squares in a grid optimally placed to represent the data, preserving order. In cases where multiple arrangements of squares are optimal, you can output any of the optimal arrangements. Between 1 and 100 pairs of coordinates will be given.

This is code golf, shortest code wins.

**Examples:**

Input: `[(0.0, 0.0), (1.0, 1.0), (0.0, 1.0), (1.0, 0.0)]`

This is an easy one. The centers of the squares in our grid are at 0.0, 1.0, 2.0, etc. so these shapes are already perfectly placed at the centers of squares in this pattern:

```
21
03

```

So your output should be exactly these coordinates, but as integers, in a format of your choice:

```
[(0, 0), (1, 1), (0, 1), (1, 0)]

```

Input: `[(2.0, 2.1), (2.0, 2.2), (2.1, 2.0), (2.0, 1.9), (1.9, 2.0)]`

In this case all the shapes are close to the center of the square at (2, 2), but we need to push them away because two squares cannot be in the same position. Minimizing the distance from a shape's centroid to the center of the square that represents it gives us this pattern:

```
 1
402
 3

```

So your output should be `[(2, 2), (2, 3), (3, 2), (2, 1), (1, 2)]`.

**Test cases:**

```
[(0.0, 0.0), (1.0, 1.0), (0.0, 1.0), (1.0, 0.0)] -> [(0, 0), (1, 1), (0, 1), (1, 0)]
[(2.0, 2.1), (2.0, 2.2), (2.1, 2.0), (2.0, 1.9), (1.9, 2.0)] -> [(2, 2), (2, 3), (3, 2), (2, 1), (1, 2)]
[(94.838, 63.634), (97.533, 1.047), (71.954, 18.17), (74.493, 30.886), (19.453, 20.396), (54.752, 56.791), (79.753, 68.383), (15.794, 25.801), (81.689, 95.885), (27.528, 71.253)] -> [(95, 64), (98, 1), (72, 18), (74, 31), (19, 20), (55, 57), (80, 68), (16, 26), (82, 96), (28, 71)]
[(0.0, 0.0), (0.1, 0.0), (0.2, 0.0), (0.0, 0.1), (0.1, 0.1), (0.2, 0.1), (0.0, 0.2), (0.1, 0.2), (0.2, 0.2)] -> [(0, 0), (1, 0), (2, 0), (0, 1), (1, 1), (2, 1), (0, 2), (1, 2), (2, 2)]
[(1.0, 0.0), (1.0, 0.1), (1.0, 0.2), (1.0, 0.3)] -> [(1, 0), (0, 0), (2, 0), (1, 1)] or [(1, 0), (2, 0), (0, 0), (1, 1)]
[(3.75, 3.75), (4.25, 4.25)] -> [(3, 4), (4, 4)] or [(4, 3), (4, 4)] or [(4, 4), (4, 5)] or [(4, 4), (5, 4)]

```

Total distance from the centroids of shapes to the centers of the squares that represent them in each case (please let me know if you spot any errors!):

```
0.0
3.6
4.087011
13.243299
2.724791
1.144123

```

**Just for fun:**

Here's a representation of the geographic centers of the contiguous United States in our input format, at roughly the scale the Times used:

```
[(15.2284, 3.1114), (5.3367, 3.7096), (13.0228, 3.9575), (2.2198, 4.8797), (7.7802, 5.5992), (20.9091, 6.6488), (19.798, 5.5958), (19.1941, 5.564), (17.023, 1.4513), (16.6233, 3.0576), (4.1566, 7.7415), (14.3214, 6.0164), (15.4873, 5.9575), (12.6016, 6.8301), (10.648, 5.398), (15.8792, 5.0144), (13.2019, 2.4276), (22.3025, 8.1481), (19.2836, 5.622), (21.2767, 6.9038), (15.8354, 7.7384), (12.2782, 8.5124), (14.1328, 3.094), (13.0172, 5.3427), (6.142, 8.8211), (10.0813, 6.6157), (3.3493, 5.7322), (21.3673, 7.4722), (20.1307, 6.0763), (7.5549, 3.7626), (19.7895, 7.1817), (18.2458, 4.2232), (9.813, 8.98), (16.8825, 6.1145), (11.0023, 4.2364), (1.7753, 7.5734), (18.8806, 6.3514), (21.3775, 6.6705), (17.6417, 3.5668), (9.9087, 7.7778), (15.4598, 4.3442), (10.2685, 2.5916), (5.3326, 5.7223), (20.9335, 7.6275), (18.4588, 5.0092), (1.8198, 8.9529), (17.7508, 5.4564), (14.0024, 7.8497), (6.9789, 7.1984)]

```

To get these, I took the coordinates from the second list on this page and used `0.4 * (125.0 - longitude)` for our X coordinate and `0.4 * (latitude - 25.0)` for our Y coordinate. Here's what that looks like plotted:

The first person to use the output from their code with the above coordinates as input to create a diagram with actual squares gets a pat on the back!

# Answer
> 3 votes
# Mathematica, 473 bytes

```
f@p_:=(s=Flatten@Round@p;v=Array[{x@#,y@#}&,n=Length@p];
  Do[w=Flatten[{g@#,h@#}&/@(b=Flatten@Position[p,x_/;Norm[x-p[[i]]]<=2,{1}])];f=Total[Norm/@(p-v)]+Total[If[#1==#2,1*^4,0]&@@@v~Subsets~{2}]/.Flatten[{x@#->g@#,y@#->h@#}&@@@w]/.Thread[Flatten@v->s];
    c=w∈Integers&&And@@MapThread[Max[#-2,0]<=#2<=Min[#+2,100]&,{Flatten@p[[b]],w}];s=Flatten@ReplacePart[s~Partition~2,Thread[b->Partition[w/.Last@Quiet@NMinimize[{f,c},w,MaxIterations->300],2]]]
    ,{i,n}]~Do~{2};s~Partition~2)

```

---

Before golfing:

```
f[p_]:=(n=Length@p;s=Flatten@Round@p;v=Array[{x[#],y[#]}&,n];
  Do[
    v2=Flatten[{x2[#],y2[#]}&/@(b=Flatten@Position[p,x_/;Norm[x-p[[i]]]<=2,{1}])];
    f2=Total[Norm/@(p-v)]+Total[If[#1==#2,1*^4,0]&@@@Subsets[v,{2}]]/.Flatten[{x[#]->x2[#],y[#]->y2[#]}&@@@v2]/.Thread[Flatten@v->s];
    c2=v2∈Integers&&And@@MapThread[Max[#-2,0]<=#2<=Min[#+2,100]&,{Flatten@p[[b]],v2}];
    s=Flatten@ReplacePart[s~Partition~2,Thread[b->Partition[v2/.Last@Quiet@NMinimize[{f2,c2},v2,MaxIterations->300],2]]];
    ,{i,n}]~Do~{2};
  s~Partition~2)

```

---

**Explanation**:

This optimization problem is not difficult to describe in Mathematica. Given a list of points `p` of length `n`,

* the variables are `x[i]` and `y[i]`: `v=Array[{x[#],y[#]}&,n]`,
* the function to minimize is the total of displacements: `f=Total[Norm/@(p-v)]`,
* the constraints are: `c=Flatten[v]∈Integers&&And@@(Or@@Thread[#1!=#2]&@@@Subsets[v,{2}])`.

And, `NMinimize[{f,cons},v,MaxIterations->Infinity]` will give the result. But unfortunately, such straight forward scheme seems too complicated to converge.

To work around the problem of complexity, two techniques are adopted:

* a large "interaction", `If[#1==#2,1*^4,0]&`, is used to avoid collision between points.
* instead of optimize all variable at the same time, we optimize on every point with their neighbors in turn.

We start from an initial guess by rounding the points. When the optimizations are done one by one, collisions are expected to be resolved, and an optimized arrangement is established.

The final solution is at least good, if not optimal. (I believe `:P`)

---

**Result**:

The result of **Just for fun** is shown below. Dark green points are the inputs, gray squares are the outputs, and black lines shows the displacements.

The sum of displacements is **19.4595**. And the solution is

```
{{15,3},{5,4},{13,4},{2,5},{8,6},{21,6},{20,5},{19,5},{17,1},{17,3},{4,8},{14,6},{15,6},{13,7},{11,5},{16,5},{13,2},{22,8},{19,6},{21,7},{16,8},{12,9},{14,3},{13,5},{6,9},{10,7},{3,6},{22,7},{20,6},{8,4},{20,7},{18,4},{10,9},{17,6},{11,4},{2,8},{19,7},{22,6},{18,3},{10,8},{15,4},{10,3},{5,6},{21,8},{18,5},{2,9},{18,6},{14,8},{7,7}}

```

# Answer
> 2 votes
## Python 3, 877 bytes

This is **not** a correct implementation. It fails on the second of the "further test cases", producing a solution with a total distance of 13.5325, where the solution provided needs only 13.2433. Further complicating matters is the fact that my golfed implementation doesn't match the ungolfed one I wrote first...

However, nobody else has answered, and this is too interesting a challenge to let slip past. Also, I have a picture generated from the USA data, so there's that.

The algorithm is something like this:

1. Push all points to the nearest integer coordinates (hereafter called a "square").
2. Find the square with the greatest number of points.
3. Find the lowest-cost redistribution of those points to the nine-square neighbourhood of this one, excluding any squares that have already been processed in step 2.
    * The redistribution is limited to one point per square, unless that wouldn't provide enough squares (although even then, only one point will remain on *this* square).
4. Repeat from step 2 until no square has more than one point.
5. Locate each of the original points, in order, and output their squares, in order.

I have absolutely no proof of optimality for any part of this algorithm, just a strong suspicion that it'll provide "pretty good" results. I think that's what we called a "heuristic algorithm" back in my uni days...!

```
l=len
I,G,M=-1,101,150
d=lambda x,y,X,Y:abs(x-X+1j*(y-Y))
N=(0,0),(I,0),(0,I),(1,0),(0,1),(I,I),(1,I),(1,1),(I,I)
n=lambda p,e:[(x,y)for(x,y)in(map(sum,zip(*i))for i in zip([p]*9,N))if(x,y)not in e and I<x<G and I<y<G]
def f(p):
 g={};F=[];O=[I]*l(p)
 for P in p:
  z=*map(round,P),
  if z in g:g[z]+=[P]
  else:g[z]=[P]
 while l(g)<l(p):
  L,*P=0,
  for G in g:
   if l(g[G])>l(P):L,P=G,g[G]
  o=n(L,F);h=l(o)<l(P);c=[[d(*q,*r)for r in o]for q in P];r={}
  while l(r)<l(c):
   A=B=C=M;R=S=0
   while R<l(c):
    if R not in r:
     z=min(c[R])
     if z<A:B,A=R,z;C=c[R].index(A)
    R+=1
   while S<l(c):
    if S==B:
     v=0
     while v<l(c[S]):
      if v!=C:c[S][v]=M
      v+=1
    elif C<1or not h:c[S][C]=M
    S+=1
   r[B]=C
  for q in r:
   x,y=P[q],o[r[q]]
   if y==L or y not in g:g[y]=[x]
   else:g[y]+=[x]
  F+=[L]
 for G in g:
  O[p.index(g[G][0])]=G
 return O

```

And the result of running it on the USA data (thanks to a utility function that turns the results into SVG):

This is slightly worse than the one the ungolfed code produced; the only visible difference is that the top-rightmost square is one further to the left in the better one.

# Answer
> 1 votes
# MATLAB, ~~316 343~~ 326 bytes

This one is a work in progress - it's not fast, but it is short. It seems to pass most of the test cases. Currently the one just for fun input of the map is running, but it is still going after 10 minutes, so...

```
function p=s(a)
c=ceil(a');a=a(:,1)+j*a(:,2);[~,p]=r(a,c,[],Inf);p=[real(p),imag(p)];end
function [o,p]=r(a,c,p,o)
if ~numel(c)
o=sum(abs(p-a));else
x=c(1)+(-1:1);y=c(2)+(-1:1);P=p;
for X=1:3
for Y=1:3
Q=x(X)+j*y(Y);if(x(X)>=0)&(y(Y)>=0)&all(Q~=P)
[O,Q]=r(a,c(:,2:end),[P;Q],o);
if(O<o) o=O;p=Q;disp(o);end
end;end;end;end;end

```

And in a somewhat more readable format:

```
function p=squaremap(a)
%Input format: [2.0, 2.1;2.0, 2.2;2.1, 2.0;2.0, 1.9;1.9, 2.0]

    c=ceil(a'); %Convert each point to the next highest integer centre
    a=a(:,1)+j*a(:,2); %Convert each 2D point into a complex number
    [~,p]=r(a,c,[],Inf); %Recurse!
    p=[real(p),imag(p)];
end

function [o,p]=r(a,c,p,o)
    if ~numel(c) %If we are as deep as we can go
        o=sum(abs(p-a)); %See what our overall distance is
    else
        x=c(1)+(-1:1);y=c(2)+(-1:1); %For each point we try 9 points, essentially a 3x3 square
        P=p;
        for X=1:3;
            for Y=1:3
                %For each point
                Q=x(X)+j*y(Y); %Covert to a complex number
                if(x(X)>=0)&(y(Y)>=0)&all(Q~=P) %If the point is not negative and has not already been used this iteration
                    [O,Q]=r(a,c(:,2:end),[P;Q],o); %Otherwise iterate further
                    if(O<o) o=O;p=Q;end %Keep updating the smallest path and list of points we have found
                end
            end
        end
    end
end

```

The input format is expected to be a MATLAB array, such as:

```
[2.0, 2.1;2.0, 2.2;2.1, 2.0;2.0, 1.9;1.9, 2.0]

```

Which is pretty close to the format in the question, which allows some leeway.

The output is in the same format as the input, an array where any given index corresponds to the same point in both the input and output.

---

Hmm, 8 hours and still running on the map one... this solution is guaranteed to find the most optimal, but it does it via brute force, so takes a very long time.

I've come up with another solution which is much faster, but like the other answer fails to find the most optimal in one of the test cases. Interestingly the map I get for my other solution (not posted) is shown below. It achieves an total distance of 20.72.

---
Tags: code-golf, math, number, geometry
---


title: Interpret Functional-Basic

text:
# Question
Title: Interpret Functional-Basic
# About Functional-Basic

Functional-Basic (FB for short) is a language that only allows numbers and lists. Basic features, such as the `if` statement are missing in an attempt to simplify the language.

Everything in this language is immutable. `input` is always assigned to the script input, which can be either a number or a list.

## Basic operators

Note that you must support the order of operations for these. (https://en.wikipedia.org/wiki/Order\_of\_operations#Definition)

* `+`: Addition - Applies to both numbers and lists.
* `-`: Subtraction - Only applies numbers.
* `*`: Multiplication - Only applies numbers.
* `/`: Division - Only applies numbers.
* `^`: Exponentiation - Only applies numbers.

## Functions you must implement

* `sum: List of numbers -> Number` Sum a list of numbers. Sum of `[]` is `0`.
* `product: List of numbers -> Number` Get the product of a list. Product of `[]` is `1`.
* `print: Anything -> [empty list]` Print the value to standard out. Returns empty list. `print` always ends in a newline.

### Output format of the `print` function

The output should look like how it would be coded literally into the program, with the minor change that one space is required after a comma in lists. The values infinity and negative infinity are `Infinity` and `-Infinity` respectively. `Not a number` is represented by `NaN`.

# Syntax

The syntax for FB is very simplistic. Below is a description of each major section of the syntax.

### Useful terms

```
identifier : a string of only letters

```

### Variable declaration

Though I call them variables, they are really immutable. The only place where a space is required in the syntax is between the `[name]` and `let`. `name`s will never contain numbers, just upper and lower case ASCII letters. For simplicity you can assume that identifiers will never be used twice, even in `for` loops. Also names will not overlap with built-ins (`let`, `sum`, `for`, ...). Syntax:

```
let [identifier] = [some expression][newline]

```

Some examples:

```
let sumOfLst=sum [1,2]
let prod    = product [2,2]

```

### Numbers

Numbers in FB conform to the IEEE 754/854 standard, with implementations providing a minimum of 32-bit precision. `NaN`, `Infinity` and `-Infinity` will not occur in the program source, but may be a result of a calculation.

### Lists

Lists have a very limited set of capabilities. You can add lists together with `+`, and you can map over them with `for`. No indexed array access is supported here. Lists *can* have nested list inside them, but if it does it won't have any numbers as direct sub-children (i.e. lists don't mix types). List have only 2 ways to be created, the literal syntax and by mapping over a list with a `for` loop.

Syntax is just like most list types in other languages.

Examples:

```
let b = []  <-- not sure what you can do with a empty list...
let c = [5, 6]
let d = [5, []]             <-- invalid
let e = [[5, 2, 6], [6]]    <-- valid
let f = [5] + 5             <-- invalid
let g = [5] + [5]           <-- valid
let h = [[6, 2], []] + []   <-- valid
let i = [[6, 2], []] + [5]  <-- invalid

```

### For loops

For loops in FB behave much like `map` in other languages in that it returns a list with the function applied to each element of the list. For simplicity you will never have nested `for` loops. Identifiers from outer scopes may be used in the expression. The expression will always be on the same line.

Syntax:

```
for ([identifier] in [list, may
           be an identifier pointing to a list]) [expression]

```

Examples:

```
for(x in lst) x+1
let nList = for (bestNameEver in [2, 5, 6]) bestNameEver^2
let lstOfLsts = for (i in b) [b, b+1]
for(x in [1, 2, 3])print x

```

### Functions

Really only 3 functions exist in FB, `sum`, `product`, and `print`. Refer to the list above for definition of how they should work. All functions have an arity of 1. Function application consists of the name of the function, a space and an expression as the argument. Functions will take the very next thing after them as their argument, even if it is another function. If the arg is another function it will force the evaluation of that function to receive it's arguments. Example:

```
print sum [5]
prints argument is sum.
print (sum) [5]
sum grabs the list since that is the next thing and evaluates it.
print (5)

```

Syntax:

```
[function name][minimum one space][expression as the argument]

```

Examples:

```
print [5, 1]
sum   [6, 7]
print 1+2    <-- This is invalid, because print grabs the `1`
                      and returns `[]`, and `[]+2` is invalid
print (1+2)  <-- This is valid

```

### Other syntax features

Parenthesis are supported.

Example:

```
print ((1+2)*5)

```

## Handling errors

You can assume that all programs you will receive are syntactically correct and will not violate any rules placed on numbers and lists. The only thing that results in a error case is division by zero (`x/0`). If you encounter a division by zero you simply halt execution of your program and print `Division by zero!` to either stdout or stderr.

## Examples

Code and output. (`>` denotes code):

```
>print sum [1, 2, 3]
6

>print for (x in [1, 2, 3]) x+2
[3, 4, 5]

>let aFloat = 4.2
>let aInt = 5
>let aList = [aFloat, aInt]
>print product aList
21

>let x = for (y in [2.3, 5.6]) y/5*6
>print product x
18.5472

>let superSecretNumber = 0
>print superSecretNumber
0

Input: [2, 3, 4]
>for (i in input) print i*2
4
6
8

>let answerToLife = 6*9
>print answerToLife
54

>print print sum [5, 2]
7
[]

>let a = [1, 2, 3]
>let b = for (x in a) [x, x+1]
>print b
[[1, 2], [2, 3], [3, 4]]

>print print []
[]
[]

>print for (i in [1, 2, 3]) print i
1
2
3
[[], [], []]

```

# Answer
# Python 2.7, 979

I'm sure I could golf it further, but I don't see the point yet as I'm the only answer for the moment - I'm a bit lazy

Here is the code of my interpreter :

```
import sys,re
V={}
S=lambda m:re.sub(' +',';',m).split(';')
def P(t):print t;return []
def E(t):
 if len(t)==1:return t[0]
 y=E(t[1:])
 return{'print':'P('+y+')','sum':'sum('+y+')','product':'reduce(lambda x,y:x*y'+y+',1)'}[t[0]]
def e(t):
 y=t[0]
 if y=='let':v=V[t[1]]=e(t[3:]);return v
 if y=='print':v=e(t[1:]);return P(v)
 if y=='sum':return sum(e(t[1:]))
 if y=='product':return reduce(lambda x,y:x*y,e(t[1:]),1)
 if y=='for':c=S(R(t[1][1:-1].replace('/',' ')));return eval('map(lambda %s:%s,%s)' % (c[0],E(t[2:]),str(e(c[2:]))))
 if y[0]=='[':v=V['input']=eval(re.sub('([a-zA-Z]+)',"V['\\1']",y));return v
 if re.match('[0-9]+',y):v=V['input']=eval(y);return v
 return V[y]
def R(s, u='[',e=']',r=''):
 m,b='',1
 for c in s:
  if b:
   m+=c
   if c==u:b=0
  else:
   m+=r if c==' 'else c
   if c==e:b=1
 return m
def i(s):
 try:e(S(R(R(s.replace('^','**'),'(',')','/'))))
 except ZeroDivisionError:print 'Division by zero!';sys.exit(1)
while 1:print '>',;i(raw_input())

```

You can play with it here
> 5 votes

---
Tags: code-golf, interpreter
---


# Question
Title: Sort scrambled two-dimensional array filled with numbers by swapping adjacent numbers
A two-dimensional array of size n×n is filled with n\*n numbers, starting from number 1. Those numbers are to be sorted per row in ascending order; the first number of a row must be greater than the last number of the previous row (the smallest number of all (1) will be in \[0,0\]). This is similar to the 15 puzzle.

This is, for example, a sorted array of size *n = 3*.

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

```

## Input

The input is a scrambled array. It can be of any size up to n = 10. Example for n = 3:

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

```

## Output

Output a list of *swaps* required to sort the array. A *swap* is defined as following: **Two *adjacent* numbers swap positions, either horizontally or vertically; diagonal swapping is not permitted.**

Example output for the example above:

* Swap 4 and 1
* Swap 8 and 5
* Swap 8 and 6
* Swap 9 and 8

**The less swaps required, the better.** Computation time must be feasible.

---

Here is another example input, with n = 10:

```
41 88 35 34 76 44 66 36 58 28
6 71 24 89 1 49 9 14 74 2
80 31 95 62 81 63 5 40 29 39
17 86 47 59 67 18 42 61 53 100
73 30 43 12 99 51 54 68 98 85
13 46 57 96 70 20 82 97 22 8
10 69 50 65 83 32 93 45 78 92
56 16 27 55 84 15 38 19 75 72
33 11 94 48 4 79 87 90 25 37
77 26 3 52 60 64 91 21 23 7

```

If I'm not mistaken, this would require around 1000-2000 swaps.

# Answer
# Mathematica, not golfed

```
towards[a_,b_]:={a,a+If[#==0,{0,Sign@Last[b-a]},{#,0}]&@Sign@First[b-a]};
f[m_]:=Block[{m2=Map[QuotientRemainder[#-1,10]+1&,m,{2}]},
  Rule@@@Apply[10(#1-1)+#2&,#,{2}]&@
    Reap[Table[
      m2=NestWhile[
        Function[{x},x/.(Sow[#];Thread[#->Reverse@#])&[x[[##]]&@@@towards[First@Position[x,i,{2}],i]]]
        ,m2,#~Extract~i!=i&];
      ,{i,Reverse/@Tuples[Range[10],2]}];][[2,1]]]

```

---

**Explanation**:

The algorithm is similar to "bubble sort". These 100 numbers are put into correct order one by one, `1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100`. They are first move up/down to the correct rows, and then move left to the correct columns.

Function `towards` gives the two position to swap. For example, if `{5,2}` is moving to `{1,1}`, `towards[{5,2},{1,1}]` gives `{{5,2},{5,1}}` (move up); and `towards[{5,1},{1,1}]` gives `{{5,1},{4,1}}` (move left).

---

**Results**:

For the test case, the total number of swaps is 558. The first few swaps are,

```
{1->76,1->34,1->35,1->88,1->41,11->16,11->69,11->46, ...

```

For a random configuration, the total number of swaps is **558.5 ± 28.3** (1σ).
> 3 votes

---
Tags: code-challenge, array, sorting
---


title: Trim and Count the Decimals

text:
# Question
Title: Trim and Count the Decimals
In this challenge, you will write a program to output how many decimal places are in the input *string* and trim the input if needed.

## Examples

```
-12.32
2

32
0

3231.432
3

-34.0
0 -34

023
0 23

00324.230
2 324.23

10
0

00.3
1 0.3

0
0

-04.8330
3 -4.833

```

## Rules

* Input will be a string which can be taken through, STDIN, function arguments or the closest equivalent
* Output can be through function return, STDOUT, or the closest equivalent.
* **There is no limit on the size for the input integer** except for your languages maximum *string* length.
* If the input has any unnecessary (leading or trailing) zeros:
    1. You should take them out
    2. Output the amount of decimal place in the new number
    3. Output the new number separated by a separator (e.g. space, newline, comma)
* Input will always match this RegEx: `-?\d+(\.\d+)?`, or *if you don't speak RegEx*:
    + There *could* be a `-` at the beginning implying a negative number. Then there will be at *least* one digit. Then there *could* be... a `.` and some more digits.
    + To check if an input is valid, check here
* **No Regex**

---

This is so shortest code in bytes wins

# Answer
# PHP 7, 142 bytes

I somehow managed to squeeze everything into a single print statement:

```
<?=strlen((explode('.',$t=trim('-'==($_=$argv[1])[0]?$n=$_=trim($_,'-'):$_,0)))[1]).($t!==$_?($n?' -':' ').('.'==$t[0]?0:'').trim($t,'.'):'');

```

Runs from command line, like:

```
$ php trimandcount.php "-04833.010"

```

**Demo**

See all test cases including a very long one (62 characters) in action:

Try before buy1

1 Hover over the box below "*Output for 7.0.0*" to see all results.
> 0 votes

# Answer
## Python 2, ~~165~~ 180 bytes

At first I was thinking about writing my first Pyth program, got it to count the digits after the potential comma. But then I got quite annoyed, I don't know how you'd enjoy that language, guess it's just for winning purposes. Anyway here's my solution (edited since it didn't work for large numbers):

```
def t(i):
 o,a='',i
 while a[-1]=='0':
  a=a[:-1]
 while a[0]=='0':
  a=a[1:]
 if a[-1]=='.':a=a[:-1]
 if'.'in a:o=str(len(a)-a.index('.')-1)
 else:o='0'
 if a!=i:o+=" "+a
 print o

```

In case anybody wants to build on my work in Pyth: `~b@+cz"."" "1Wq@b_1"0"~b<b_1)plrb6` To see where you're at, you might want to insert a p between `@+`.
> 4 votes

# Answer
# 05AB1E, 23 bytes (non-competitive)

Damn, I was so close. Python parses very large floats using scientific notation, so I fixed this bug in the interpreter. However, this was done *after* the challenge and my submission is therefore non-competitive.

Code:

```
DÞ'.¡0Üg,\DÞ0Ü'.ÜDrQ_i,

```

Explanation:

```
D                       # Duplicate top of the stack, or input when empty
 Þ                      # Convert to float
  '.¡                   # Split on '.' (decimal point)
     0Ü                 # Remove trailing zeroes
       g                # Get the length
        ,               # Output top of the stack (the length)
         \              # Discard the top item
          D             # Duplicate top of the stack
           Þ            # Convert to float
            0Ü          # Remove trailing zeroes
              '.Ü       # Remove trailing dots
                 D      # Duplicate top of the stack
                  r     # Reverse the stack
                   Q_i, # If not equal, print top of the stack

```

Uses the ISO 8859-1 encoding.
> 2 votes

# Answer
# JavaScript (ES6), 156 ~~162~~

**Edit** Fixed bug for '-0' - thx @Fez Vrasta **Edit 2** 6 bytes saved thx @Neil

It's a mess, but it's 100% string based - no limit due to numeric types

```
s=>(l=k=p=t=0,[...s].map(c=>++t&&c=='.'?p=t:+c&&(l=t,k=k||t)),m=p>l?p-1:p?l:t,k=k>p&&p?p-2:k-1,r=(s<'0'?'-':'')+s.slice(k,m),(p&&m>p?m-p:0)+(r!=s?' '+r:''))

```

**Less golfed**

```
f=s=>
(
  // All values are position base 1, so that 0 means 'missing'
  // k position of first nonzero digit
  // l position of last non zero digit
  // p position of decimal point
  // t string length
  l=k=p=t=0,
  // Analyze input string
  [...s].map((c,i)=>c=>++t&&c=='.'?p=t:+c&&(l=t,k=k||t)),
  // m position of last digits in output
  // if the point is after the last nz digit, must keep the digits up to before the point
  // else if point found, keep  up to l, else it's a integer: keep all
  m=p>l?p-1:p?l:t,
  // the start is the first nonzero digit for an integer
  // but if there is a point must be at least 1 char before the point
  k=k>p&&p?p-2:k-1,
  // almost found result : original string from k to m
  r=(s<'0'?'-':'')+s.slice(k,m), // but eventually prepend a minus
  (p&&m>p?m-p:0) // number of decimal digits
  +(r!=s?' '+r:'') // append the result if it's different from input
)

```

**Test**

```
F=s=>(l=k=p=t=0,[...s].map(c=>++t&&c=='.'?p=t:+c&&(l=t,k=k||t)),m=p>l?p-1:p?l:t,k=k>p&&p?p-2:k-1,r=(s<'0'?'-':'')+s.slice(k,m),(p&&m>p?m-p:0)+(r!=s?' '+r:''))

console.log=x=>O.textContent+=x+'\n';
// Test cases
;[['-12.32','2'],['32','0'],['3231.432','3'],['-34.0','0 -34']
 ,['023','0 23'],['00324.230','2 324.23'],['10','0'],['00.3','1 0.3']
 ,['0','0'],['-0','0'],['-04.8330','3 -4.833']]
.forEach(t=>{
  var i=t[0],k=t[1],r=F(i);
  console.log((k==r?'OK ':'KO ')+i+' -> '+r)})

function test(){var i=I.value,r=F(i);R.textContent=r;}
test()
```

```
input { width:90% }
input,span { font-family: sans-serif; font-size:14px }
```

```
Input: <input id=I oninput='test()' value='-000000098765432112345.67898765432100000'>
Output: <span id=R></span><br>
Test cases<br>
<pre id=O></pre>
```
> 2 votes

# Answer
## ES6, ~~102~~ ~~180~~ 177 bytes

~~```
s=>(t=s.replace(/(-?)0*(\d+(.\d*[1-9])?).*/,"$1$2"),d=t.length,d-=1+t.indexOf('.')||d,t!=s?d+' '+t:d)

```~~
```
s=>{t=[...s];for(m=t[0]<'0';t[+m]==0&&t[m+1]>'.';)t[m++]='';r=l=t.length;for(r-=1+t.indexOf('.')||l;t[--l]<1&&r;r--)t[l]='';t[l]<'0'?t[l]='':0;t=t.join``;return t!=s?r+' '+t:r}

```

Edit: Saved 3 bytes thanks to @edc65; saved 1 byte thanks to insertusernamehere.
> 1 votes

# Answer
# C++, 180 bytes

```
int f(char*s,char*&p){int m=*s=='-',n=0;for(p=s+m;*p=='0';++p);for(;*++s-'.'&&*s;);p-=p==s;if(*s){for(;*++s;)++n;for(;*--s=='0';--n)*s=0;*s*=n>0;}if(m&&*p-'0'|n)*--p='-';return n;}

```

This is portable C++, that makes no assumptions of character encoding, and includes no libraries (not even the Standard Library).

Input is passed in `s`. The number of decimal places is returned; the string is modified in-place and the new start is returned in `p`.

By rights, I should return a `size_t`, but instead I'm going to claim that you should compile this for an OS that limits the size of strings to half the range of `int`. I think that's reasonable; it counts more than 2 billion decimal places on 32-bit architectures.

### Explanation

```
int f(char*s, char*&p){
    int m=*s=='-', n=0;
    for(p=s+m;*p=='0';++p);     // trim leading zeros
    for(;*++s-'.'&&*s;);        // advance to decimal point
    p-=p==s;                    // back up if all zeros before point
    if(*s){
        for(;*++s;)++n;          // count decimal places
        for(;*--s=='0';--n)*s=0; // back up and null out trailing zeros
        *s*=n>0;                 // don't end with a decimal point
    }
    if(m&&*p-'0'|n)*--p='-';    // reinstate negative sign
    return n;
}

```

### Test program

```
#include <cstring>
#include <cstdio>
int main(int argc, char **argv)
{
    for (int i = 1;  i < argc;  ++i) {
        char buf[200];
        strcpy(buf, argv[i]);
        char *s;
        int n = f(buf, s);
        printf("%10s ==> %-10s (%d dp)\n", argv[i], s, n);
    }
}

```

### Test output

```
    -12.32 ==> -12.32     (2 dp)
        32 ==> 32         (0 dp)
  3231.432 ==> 3231.432   (3 dp)
     -34.0 ==> -34        (0 dp)
       023 ==> 23         (0 dp)
 00324.230 ==> 324.23     (2 dp)
        10 ==> 10         (0 dp)
      00.3 ==> 0.3        (1 dp)
  -04.8330 ==> -4.833     (3 dp)
    -00.00 ==> 0          (0 dp)
       -00 ==> 0          (0 dp)
       000 ==> 0          (0 dp)
      0.00 ==> 0          (0 dp)
      -0.3 ==> -0.3       (1 dp)
         5 ==> 5          (0 dp)
        -5 ==> -5         (0 dp)

```
> 0 votes

---
Tags: code-golf, number, counting
---


title: Encode bytes to PGP wordlist format

text:
# Question
Title: Encode bytes to PGP wordlist format
The PGP Word List is a set of 512 English words for verbally communicating strings of bytes, such as authentication codes or hashes. It is used in secure VoIP software as well as in some other important applications, such as the DNSSEC Root KSK Ceremonies held four times a year.

It consists of 256 two-syllable words and 256 three-syllable words. Bytes at even offsets become two-syllable words, while bytes at odd offsets become three-syllable words. This protects against transposition of adjacent words, repetition of a word, or omission of a word.

The two subsets are kept as alphabetical lists and numbered accordingly, so a null byte (hex 00) becomes "aardvark" at an even offset and "adroitness" at an odd offset. Likewise, the words for hex FF are "Zulu" and "Yucatan" respectively.

---

Write a complete program to encode a sequence of bytes (represented as pairs of hex digits) as a sequence of words from the PGP Word List.

Because the program is to be run on a secure, air-gapped computer, and USB drives are a security risk, the program should be as short as possible to facilitate manual entry. (The length of each program is measured in bytes, because if I were to use the complicated keystroke formula I came up with, this specification would be twice as long as it is now.)

## Input format

The program must accept a string of hex digits as either a single line of input or a command-line argument. You may assume the following:

* There are no spaces or other separators between hex digits.
* The number of hex digits is between 2 and 128 inclusive.
* The number of hex digits is even.
* Digits A-F are either all lowercase or all uppercase (if the required letter case is documented).

Example input: `9030e74b`

## Output format

The program must print a corresponding line of words from the PGP Word List. Adjacent words must be separated by a single space. However, case of the letters within the words may differ from that shown in the PGP Word List.

Example output: `peachy commando transit disable`

## Restrictions

The program must not rely on any external copy of the PGP Word List, including any data known to be largely derived from the list that may be present in a system file or library.

## Test cases

A TSV file is provided. In each line, column 1 contains the input (as lowercase hex digits), and column 2 contains the corresponding output. More test cases may be added if necessary.

# Answer
> 1 votes
# PHP – 3302 bytes

This solution uses a `gzcompress`ed string of uppercase space-delimited PGP words, e.g. `AARDVARK ABSURD ACCRUE...WOODLARK ZULU`.

```
<?php $f='explode';$g='gzuncompress';$h='base64_decode';$a[]=$f(' ',$g($h('eNollVli5CAMRK/CVWSMbWJAhKU9zv0PMk/0R6jqsGgrySJt/0i7nWx9tt2J920GILPsLR4DmIn1OFL04BWEYzGn0LuTdGpiTfqwauFSzuqk+BgKh2tN/KuN2PnR+7RXxxUKN0cS1r8RvNtkUy2Av48Y0r7Yg2eQ8qNuC5JjOcE9Sa5guOInGPZH/oFHwx7HQzoEU1toPRDUFlOK653YzUDi3R/+YOpv2YORZ2jzF2yGLdpZzdt6RPXuFy+6rXEnds40gk+RMI3dE1da9Pe7TODC4aWzNxt+Y2SOYVbn358d8CFbTvwlsSVLLGyM0MDg7S1/xR4SoLdFC9a6thvpy2TLE715lIz1Hv0Xm2qGBSn2iEX2KMF7xW/WjFkfIKwNq/ps6wkLatenGCv3C+hzqHKiTR/FTsxM/XYj3ZLl54bNXfq1qUW0k41NEcdOAJdQgF3Pbjf2JmcJwzAWOQOEs8dMbmmKqPb2jW7HCPW1o7Pcobh9ViVN+4OTlgb2FuymvnCeS38hntfY0J2j7EqxFz6syaQWmtUhdC8V+OcDLoU3nJYtI4MwL3fICvMw+c7hjiRnVfQKGSsRR3pHk+oOUjVmC0ZyWMk9Gm+SdoSHJ7h9yh8OB3fiGmGdKa7anml6xZdTz5OOAdN+mJTOFjLxuXPGXaw+l9BSw128tyTiLgoZXhcJjAgNZyKTsXxM3YaaaILYk2X+R57N+o8r3+LcCFOPA3yiu5P8Q4poQ/DRJIJUcmhxODqrkLmM9prLeslzuzwbicnTJFaoLX0TIHXMYoilVlxZNbCOUbmXD7qNiWdYTUqRtA7u01ziqry7vK4G8RdADbtQ5Hq9Pf4yb2qS91K7XNMc6moLPk0kBznwC+iXCQQWy1j/0ScZzhqTrZV333ER5e9kctnzv5Mp0QAd4lDkiMyfJoOGG65Zt6MCDGjLwIlUAfIcuER57CCI76xD5/r1CYUitLDGU7uwyN24eRM5rp2rH5pusxtQQZ6aJAQFdomJ2gzIs9s++kTjeNx9KKSqeyVuexg2Vkp7kJViBkNA/50Jsrq5X2J6B7JZgehzMldcv2dK6B7y7jYku3UR21xm1q2G70XqmmJGvltIYF0CuUDiuyZlmeNakXZ96VKuVimMaDBIW60IS2mL5it1bRqNxNMerfwXufX6fjuvD7K05oSxIiMYie0hw5CyL0sD58haH8GmXazG2hoFfRBqNi+G1meVB9Yyt+cpXJkt66TwfeJVQU39YXxsyyLzxHQzaOXoO8jnirVaP2c3Qq6BkozVvXyvOqpkelMVbGW1LRuYtom2ely/ZxaALGQ+NDD9wTlgboQ9ZlZOz1LI13i9feJm8UwaukhMerM8lreJlknXrD2s1QrykcrlD8+asD6RCew+k8IW99inOADJ5sVKAyHsMJqJyj1xfY4fVb6WjKq/meZ/RSEoQA==')));$a[]=$f(' ',$g($h('eNo1lmuChDgIhK+Sq9AxKtsxuHnoOPc/yH7E2T9DjXlAoChalmraS2otyHJpSzXI2lM9pO9Btq2mTXoKkr+SFXPotvcnyDFy6m5aOlIBlZ5KkSDnmTWKfzktZwtSD21dI3dUTMY27jddgvTMRo2Aw9q5p8ri6Ha2J3zk82Qr2Pi9iaCC6ifFkcInZbu3aqMs4aOrRcktfGx5tiGVT2bflnL2I1aXVLMWDlnvdmR/56fK8hn1cXDJYm5/NavgrSb5yi2sDT+3dQ9hNPUEHb5hdGJZpYcoB3G4LYsuniNQsfKRnIFn1Wi1gNzJtKnLl6BiygmPfoAoR7bmiNysT4i7HB9PPtmJ5MO+icWdhG4WyF3dHo8imueqkNNoB+F1Nf94sMZzAKeUZ1orXpxoJY5a/+Cqy9/ZstqsjsP/Kw1sqbTRJhq5kwVgPe2N2Wq19vobJWqe8fCp2eWPqyPqqj8hDn9Is4MjBIitYZGvdQlLivJGAEq+zYEekrFNt+Iel9RT7FYnqJuHPtHhxVw0dpmLWqzJcFDZ7mEt2uSTfU+DKJpWR3WcXa/5kWPvPiNEv9Yj+P3lBCHtzke8p1Ih77sMsSvVpErp3yHzLEDPd7VRal4D+OphIZGEZ4E/6UdmqOkHl/Ox6ccWsrpKi1o8latmmZesWjR+n0A1/Lzbrn1w61pxxeknbLJsqVcH+UrNecn/k6obFGriS2490RsMH+4CcCntug3tUr3STrBBPqsjzX7P7gy+rX5Bv3SQEeWeZJlt5xCKvM25U57u9+5QaPreLc/eCDv88r5n7VmqDEQgKDzkJdQVlDrXKok4ZwoVn3Caw74Du4o/E5tq8e9OTZcRLc1P4R00XiYoNdkmHR2VvwsvRxSZZ0r5jBz+ERopSvhnnOoKktMJUR+sN7E/MWSFfiToIDtdISu6F/djNuohFIPChCNROMHQIHg61Pke7UwvvNkHWto4PPlkNROQwEhwFZc8MlhmCxyWpbXUHCBmvmSFcMXty0ekEHp1C0Uqb/QXlcRzBHO3N/ZQrN5pc8kyusRbyHa1YCWjfv7fyd1cZjVPTbDRV00ZNQyneIdGbFko7QtobuyZuNUFHlyRnPLaKuc+0UHL+xovKE6hM1HEikSdpMYl40wFknphuGqW+prwLSZNcO7MA6HQ5440ufYDuv25IG3Jr7X4TX2lgowQKjcJdqI673XmvR8oZeQ7IgC6oIjzDPiDkLj/8RYWm7XtfuvDA9BVmhiesERpcOMOa0IqvGigqNQVM+WsptMnCY8G+VxzW+nj6HvaVBMH6Gzz2Kq//tUhh5ougnLEeEOfgvd3Gb7v0nfpsuyOGjWQfJstQFoQQQD0UV1LGhOEdAMiVJuZd4l+tagZL3fBazZYVNZwRTK82x3CHPKBCPX9j7WtDwo1+7yN83S1IfY2J4QzhEqeGnWuP/Rw35/Q0Q0b1SWtM8Bm+UInr3K6IzgoMRqWITUrjeT7qLgBFZ6whCjpDBnkEsallfHFW/2CyjQh0CX050x3nQ3r02dWk1EvUI/V4RGuxuAd5Z2wWCYnf8lj861+ew7jZP65ll8Sp7SQQ8HZEi6XHLTn0rqhvAKAWhTy8p8SHsxljyc83N6BhUCnFNJa4d71aPAgh1uZy0yzmxH490Phfl6PT/JfOE+SGp7Bo6T8BwHcnAI=')));$f=1;foreach(str_split($argv[1],2)as$b)echo$a[$f^=1][hexdec($b)].' ';echo"\n";

```

Save as `decode.php` and run with argument in the command line, e.g.

```
$ php decode.php 9030e74b
PEACHY COMMANDO TRANSIT DISABLE

```

Because the specification mentioned ease of text entry, I guessed full 8-bit was a no-no and restricted to regular ASCII and base 64 for the encoding.

The PGP word lists on their own, no spaces, with one word running into the next, is 3919 characters long, so this solution represents a savings of 15.74%.

Another solution formatting the strings with mixed case `AardvarkAbsurdAccrue...WoodlarkZulu` and splitting based on the case, while retaining the delimiter, turns out to be longer at 3433 bytes, even though I'm removing 510 spaces from the PGP word list source!

```
<?php $f='preg_split';$g='/([A-Z])/';$h='gzuncompress';$i='base64_decode';foreach([$f($g,$h($i('eNodVdF246oO/TY7STNzejvNmLRd67zJWDGMAXFA1ON+/d30IUixQWhvbckDleWTyjbMtZVlsLY0HmzkYSn+ocPSgg6PR/BWB8e0DD4GrnUIq4QhBNmHIImHGGVI1nPSIefAQ1Ffdai1IZA6TnXQQHX4UrYjzSJpJLs9PIelOztyGCn9kZEp+rSOvASKeWR2/pNh6k5/R34UXLCMHB5UdeRSuWyjD8H3474iaECwP/iNQexGC8PuKsW6MTSePbZJnPthka06BBoLdvvqxgJswSfuztbyWLzdjh4Xdz4sVR5bmSltY1PFRe3rCy9PHIH45MiXALLgqHI5ObYIcXK+cjg52YAIJuf+qoCXSPUEfD2BAKdWb79NEYmnwJRwuAPYpWwnmQudJOIiyyfBUvQk+9yP9twX2ROctB2nIvtDRE+lWU942yIqscBWMHFqs7dnqm4WJH4G2lmCnpGpo7ScZa3Yey60JlYYn2jlcyfl0cK5K4HLuXxjOCPwzIRdLW2czi1L0vOOhIDzQtrXBXK5rGsXzMWvTmcK4ZIWQcm62S8pgIdLAa+Xainz5a9lXi4Hr50IWAUS90QdyRMOS9OnQGuWwLDacT6FQwvlJ7CgrTBs5M7YU0EkiU+lX8zpSl9Ija/sVy7X4HuFrqFZqXyVdYWYrxKWBzRwLRyB4dr8QuD5B0Hp+gNRbC/wDxSEj5/IHihgWlj5Z/rsKoSR8Mk/awCV/9A+oyOe+fhm+hk6ksfj2e/+OdBfSf8TS4GxQiIvXLy++JRkf4FYyos42reXVii8NKjiF8oDSfMvztoSDEKX9OubUYj5lbZ+4+usrfIrmlRoec3q7WuxdKNjoePGZN1xQyEqJb25o/r/Gt8CHU5w6Baayq2wDW1h2AcXrNX10t6KT9r/yx5gWvYBSz5uhzpJvxstkJ3+bujQ8ruJ0kSr+sgTqXWsU+83dRM/pMSJV0hqYp8W5jJx7HsmznRMqHTr/ienlSfuo2ByuCJOfrYQ4QQ9dalOMreKFVUoUwNYXgz5AJLV0L7gnQGxwUsylpO3xgpwIRoc7TQZpk6a4cBWDfq2d5RxBDlijQWRjZN9RS+brYUAWZrtWADPdGVXJ2owTnrDmUS5D4tuv5+jgH07TA1+YSNBDCTrOhojB9olmUwJ885kptL7Ak4IMwgx2XERD+tXhMp4FNjk47sTjIKC3qHdSaQM68tOB2xaenRFKlyMch8oPsMpPV2jwBNxrUreO9twSjxMW6mYVqK0pKbVjNHMZkc7z/0SdDHO39FR3tY7YbTf0ZzoqnjnmLnqvXfR3WOw813A8l1yFDzuowgvoIjq+78W6d6nR8R4vhf5QwlrmwPfW5RybylxuB8WH4K3ZJu+JbCi7i3tQP+WMQj1LVfuC+h9pyzlHZHAxbvHPHtvqE76oK6CDxSd9aNDRJ7LB0HiC3/4/m36EMGHpGz/ttD+D3OmxWA=')),-1,3),$f($g,$h($i('eNotVdF24joM/LZAaWHP0rJA27OPwhGJDo6VlW2o+/V3lN4XJOzYGkkzctebSkmcc9ffJbN118I2URm7YTAeqHAXbxSli5MMY2ndVCMX/GaeOJUuFU6JunmOEgj/Z41RO5skFwncGX4jdxmXqvRdifhGQlcmzfPIxl0tOue2okuLmlYUbg+EtBXZhUPlFUd9DKY19Su5aqCYV9q3oZL1K9Vb5hjxtVrPFiXxSkvRKSKdlVF/qdZg79QrzLdEobQyphs9qK2qnxgKotYsXoEJu7Ug+pXKmiaEhkm99EAEJ2m6UIxrmk2CWlqTX+2GC93Y1hz5Yv4tQNWoGQ7Sv7b1SNPFiyr9GjnrjXk9olqDrgF+aIi7Vi9GCrzW6VJROsXShI1eYWdKzY0mVHytKVSzH+8q/c+pdNWl5vD+bxu8zCnX7E6NBbmu1WZdEKqZ5iVITUGiI8BC1jvSsBrkKl/r6qCzTrwGIBh7opsWeuJAS1A47J/AykTxibMMCVGeuHAoam5tAM7FmVDiJwmFfEeSZqqwhi8B40kyXSL284Wj8BWO1bnI3ZdwYPlGQ3XGbRDz+zvyJoXRyZSGTTKQbtkDGw3tybz5V8lPwcq8bOVAM4Bv8k0m3SDR1lPbfJED23whjOe0+dK+5mfKQRLq9CyR/PCzJAm39qzGOPjsgErt+dn4X8Wx9kL9wMVg450BOL2AEuDYC1iQCetuUMEXkBK4GPYupb1UKQS0ZQuCVNTK4EjE+a3z7qF229I3qK41b5n6RRrw0OhFPFuUHAXlLVjg4bYaFyJvwQ9XI29bb1ShzB04BNAU4XCpeYdcZ6/PDnEG3SVnKu3SlZANDFvConMKJd4l6CMgHpy6dHSHOg9OJHfSzz13d+68y4XSpcZfBL4H+lVnAejfPINf7Te7vEak8lvAnNL2SL/IxHsqYZxcRXtChVHsPaMRtHcqa9pLwPGgMy/eA9/spc91Qk33EiMAELi0FyNMm73k5Hzda6ScOcNilmBdE7ARzEKkvWaQo+grGVIB9FcGbnrlR44Lzle1Bw+YGW+gM+C+jaJvKWLswJ9xYSpvFl2jb7VchSOG0IFcPOGAVbRpsVDcgWbGXT5AD5gag6bFGM2jOxNUiA1gTeDAgdESYz4gd8j3wAnUQq0PbEvT7u79tCbwYSQ4oR1GDAdMVtiiPxejKIzbNNy4XGs8gBxoFuhxgPSXa9TVeDANWFSDc0efQRJ4X5A0QtalSzBRMhh3aAAr/Z/qwivtSH43ghwZuvUuHDELZsavT5Ijzz6eU4Hjr8PRSdDXgP28yBoWMy0DytFTXEaBe8J3iu7gkcCAOEJ0qeKbuyzrd4XK7ITSUnyo9idXCAR6olINoj5hLKOO7RTAE6/oCXNwmQYnRXoYNCet2BE74XrkCzDuofmFT4XL+MO1U6kzJxffqc6zi/7Op2X0otGnmmcJ4psN4ipjO0PEWg0KPOMlmL0hZ9SMZlx/1guFoGcw0bxtZ518BD/OmMjc6xlzQRwgHB8g7Wx4B5ATThomNHD15zbzw1xM7xjm3p13FADE4f7dAV1Vy3taXiaYa8MPqpTxld8Z3+egGHXDBwXX+AcNhAD9hwt/0A+xATOOPgTUUPvwlxbBP7R5JT9dIam0T58/4P/nKFNGQ+OnhBET6BMvyM9T+tmWIH/ZH/zGZH8rwFP6Dz6ZaRE=')),-1,3)]as$p){$t=[];for($i=0;$i<count($p);$i+=2)$t[]=$p[$i].$p[$i+1];$a[]=$t;}$f=1;foreach(str_split($argv[1],2)as$b)echo$a[$f^=1][hexdec($b)].' ';echo"\n";

```

Save as `decode.php` and run the same way:

```
$ php decode.php 9030e74b
Peachy Commando Transit Disable

```

As well, using `aARDVARKaBSURDaCCRUE...wOODLARKzULU` as the source text, the solution still comes out at 3433 bytes:

```
<?php $f='preg_split';$g='/([a-z])/';$h='gzuncompress';$i='base64_decode';foreach([$f($g,$h($i('eNodVdt227oO/DaIhEVWIMHNS1TlTbIdtycnjSs5yVr76/cwDyZgiQQxgwG0UrZPlKd1KC3b1ZjceDWBV5v9qa62SV1PJ/Gmro7Jrj4Il7LKqLKK6LyKRl5D0DUaz7GuKQmvufpS11IaAlXHsaxVqKzPlc1Gg2rcyEwnz2K7MyOHjeIP3ZiCj+PGViikjdn5J4YpM/3c+JRxgd1YTlTqxrlwnjYv4vtxXxBUEOwHfpuomcgy7Fw1G7dJ48Fjm4ahH1adikOgLWO3L27LwCY+cnemlrbszbT0uLjzZKjw1vJAcdparbioPT/j5ZkDEJ8d+SwgC06tnM+ODUKcnS8sZ6cTEMGk1F9l8BKonIGvJyBwSvHm22TVcBamiMMdwKx5OuuQ6awBFxk+K5ZczzoP/WjP3eoc4cRpOWedT6r1nJvxhLctoBIWtoCJcxu8uVBxgyLxC9AOKvWCTB1Fe9GxYO8l0xi5wvhII186Kacml64Ezpf8jeGCwAMTdrU4cby0pLFeZiQEnFeqfbWQy3Ucu2CufnR1IJFrtIqSdTNfo4CHawav12Io8fWnYbbXhcdOBGwFEvdCHckLDmurL0JjUmHY2nG+yFIzpRewUFtm2MCdsZeMSBpecr+Y442ekRrf2I+cb+J7hW7SjBa+6ThCzDcVe4IGbpkDMNyatwSefxGUXn8hiukF/oWC8PIb2QMFTJORf8enrkIYlSf+XQRU/o/mAR3xyss306/QkZ5Or372r0I/Nf5fDQljhUTeOPv65mPU+Q1iyW/qaJ7eWiZ5a1DFH5QHkuY/nGqLMAid459vRiHmd5r6je9DbYXf0aRK9j1Vb96zoTstlpY7k3HLHYUoFOvdLcX/0/gutDjFobu0qvfMRppl2BNnrMX10t6zj7X/11lgWvKCJS33pTqNfxtZyK7+bejQ/LdppZ3G6gPvVI3juvd+q27nk+aw8whJ7eyjZc47h75n50TLjkq37j9xHHnnPgp2hyvC7gcDEe7QU5fqrkMrWFGFvDeAZXuQF5BcD5ot3h0gVrzGw3D05jAKXIgGp3aaDqZO2sHCph7o295RhyPIEWvIiHw4nUf08jE1EcjymBYLeEdXdnFaD4yT3nBHpNSHRbffz1HAvh2miLd8qOgBybqO5tAF7RKPRBHz7khMufcFHJEBhBzJcVYP60eESngkfKTluxOOCgp6h3YnUmVYn2daYKPt0StS4XxU7gPFJzi5p3tU4Am4tmqaO9twcliONlI+Wg7aYj1aSRjNfMxo56Ffgi7G+Qc6ypvyIIz2B5oTXRUeHBKX+uhd9PAY7PxQsPzQFBSP+yjCCyii+P6vBXr06REwnh9Zf1DE2gbhRwuaHy1Glsdi8CH4iKbVjwhWqvuIM9B/JAzC+pEK9wX0flLS/IlI4OLTY559NlQnflFXwReKzvWrQ0Se9osgcctfvn+bvlTxIcnTv03af4OkKGA=')),-1,3),$f($g,$h($i('eNotVdF24joM/DbhiEQHx8rKNtR9C5QW9iwtC7Q9+/d3lN4XJOzYGkkz8tyZSkmc89xtJbPN68I2UhnmvjfuqfAcNxRljqP0Q2nzWCMX/GYeOZU5FU6J5mmKEgj/J41RZxslFwk8G34jzxmXqnRzifhGwlxGzdPAxnMtOuW2p1WLmvYUNjuEtD3ZikPlPUfd9aY1dXtZa6CY99q1vpJ1e9VN5hjxtVrHFiXxXkvRMSKdvVG3qtZgt9QpzLNEobQ3pg3tqO2rn+gLotYsXoERu7Ug+prKgUaEhkmddEAEJ2laUYwHmkyCWjqQX+2GC23YDhx5Zf4tQNWoGQ7SX7fDQOPKiyrdATnrhvkwoFq9HgC+b4h7UC9GCnzQcVVROsXSiI1OYSdKzY0mVPygKVSzH28t3c+ptNal5vD+bxu8zCnX7E6NBbke1CZdEKqZ5iVITUGiI8BC1i3SsBpkLU+H6qCzjnwAIBh7oY0WeuFAS1A47J/AykjxhbP0CVFeuHAoam6tB87FGVHiFwmFfEeSZqqwhi8B40UyrSL284qj8BqO1anI1pdwYPlGQ3XGHRHz+TnyMYXByZT6YzKQbtkDGw3tyXz8VclPwcq0bOVAE4Af80ZGPSLR1lE7PpEDOz4hjOd0fNKu5lfKQRLq9CqR/PCrJAmb9qrGOPjqgErt+NX4V8Wx9kZdz8Vg45YBOL2BEuDYG1iQCetuUME3kBK4GHYrpb1VKQS05QSCVNTK4EjE+ZPzbqe2OdEzqK41n5i6RRrw0OhFPCeUHAXlE1jg4U4aFyKfwA9XI59aZ1ShzDM4BNAU4XCp+YxcJ6/PGXF6PSdnKp3TmpANDFvConMKJT4n6CMgHpy6dPSMOvdOJHfSzz1bd7Z8zoXSqsbfBL4H+l0nAeg/PIFf7Q+7vAak8kfAnNIuSL/IyBcqYRhdRRdChVHsC6MRdHEqa7pIwPGgEy/eDt9cpMt1RE0vEiMAELh0ESNMm4vk5Hy9aKScOcNilmBdE7ARzEKki2aQo+g7GVIB9HcGbnrnXY4Lzne1HfeYGR+gM+B+DKIfKWLswJ9wYSofFl2jH7WshSOG0JVcPOGKVbRpsVDclSbGXT5Ar5gavabFGE2DOyNUiA1gTeDAldESY74id8j3ygnUQq2vbEvTtu79tCbwdSA4oV0HDAdMVtiiPxejKIzbNGy4rGu8ghxoFuhxhfSXa9TVeDUNWFSDs0WfQRJ4T5A0QtalSzBRMhh3bQAr3d/qwivtRn43gtwYuvUu3DALJsavT5IbTz6eU4Hjr8PNSdDVgP28yBoWMy0Dys1TXEaBe8Jbiu7gkcCAuEF0qeKbrSzrW4XK7I7SUtypdndXCAR6p1INor5jLKOO7R7AE6/oHXNwmQZ3RXoYNHet2BG743rkCzDuofmF74XL8MO1e6kTJxffvU6Ti37L92X0otH3micJ4psN4ipDe0DEWg0KfOAlmLwhD9SMJlz/0BWFoA8w0bxtDx19BO8emMjc6QNzQRwgHB8g7WF4B5ATThomNHB1jzbxzlxMnxjm3p1PFADE4e7TAa1Vy2daXiaYdcMPqpTxld8ZP6egGHX9FwXX+Bf1hADdlwu/1y+xHjOOvgTUUPvylxbBv7R5Jb9dIam0b58/4P/3IGNGQ+O3hAET6BsvyM9T+t2WIP/YH/zGZP8qwFP6Dz1XnCI=')),-1,3)]as$p){$t=[];for($i=0;$i<count($p);$i+=2)$t[]=$p[$i].$p[$i+1];$a[]=$t;}$f=1;foreach(str_split($argv[1],2)as$b)echo$a[$f^=1][hexdec($b)].' ';echo"\n";

```

Sample:

```
$ php decode.php 9030e74b
pEACHY cOMMANDO tRANSIT dISABLE

```

What's likely going on here are inefficiencies in the compression algorithm arising from using mixed case. Good to know - you learn something every day...

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


title: Hypercube sides

text:
# Question
Title: Hypercube sides
Your goal is to output all the "sides" (corners, edges, faces, etc.) of an N-dimensional unit hypercube, where N is non-negative. A "side" is defined as any (N-M)-dimension surface embedded in N-dimensional space, where `1 <= M <= N`.

The hypercube spans the space \[0, 1\] in each dimension. For example, for N=2 the square is bounded by the corner points (0, 0) and (1, 1).

# Input

Your function/program should take a single non-negative integer N. You may assume N \<= 10.

# Outputs

The output may be to any convenient format desired: return a list, print to stdio/file, output parameters, etc.

The output must contain the min/max bounds of all unique sides. Order does not matter.

**Example sides formats**

A 0D side (a.k.a. a point) in 3D space could be bounded by:

```
# in [(min0, max0),...] format, this is the point 0,1,0
[(0, 0), (1, 1), (0, 0)]

```

A 1D side (a.k.a. an edge) in 2D space could be bounded by:

```
# in [(min0, min1,...), (max0, max1,...)] format, this is the line from point (0,0) to (1,0)
[(0, 0), (1, 0)]

```

Note that it is ok to flatten the output any way you want (\[min0, max0, min1, max1, ...\] or \[min0, min1, min2, ..., max0, max1, max2, ...\], etc.)

Wikipedia has a list of the number of sides to expect for various hypercubes. In total, there should be `3<sup>N</sup>-1` results.

**Full sample outputs**

This uses the convention `[min0, max0, min1, max1, ...]`

N = 0

```
empty list (or no output)

```

N = 1

```
[0, 0]
[1, 1]

```

N = 2

```
[0, 1, 0, 0]
[0, 0, 0, 1]
[0, 1, 1, 1]
[1, 1, 0, 1]
[0, 0, 0, 0]
[0, 0, 1, 1]
[1, 1, 0, 0]
[1, 1, 1, 1]

```

N = 3

```
[0, 1, 0, 1, 0, 0]
[0, 1, 0, 0, 0, 1]
[0, 0, 0, 1, 0, 1]
[0, 1, 0, 1, 1, 1]
[0, 1, 1, 1, 0, 1]
[1, 1, 0, 1, 0, 1]
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 0, 1]
[0, 1, 0, 0, 1, 1]
[0, 1, 1, 1, 0, 0]
[0, 0, 0, 1, 1, 1]
[0, 0, 1, 1, 0, 1]
[1, 1, 0, 1, 0, 0]
[1, 1, 0, 0, 0, 1]
[0, 1, 1, 1, 1, 1]
[1, 1, 0, 1, 1, 1]
[1, 1, 1, 1, 0, 1]
[0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 1, 1]
[0, 0, 1, 1, 0, 0]
[1, 1, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1]
[1, 1, 0, 0, 1, 1]
[1, 1, 1, 1, 0, 0]
[1, 1, 1, 1, 1, 1]

```

# Scoring

This is code golf; shortest code wins. Standard loop-holes apply. You may use built-in functions like "permute a sequence" so long as it wasn't designed specifically for this problem.

Your code should run in a reasonable amount of time for N \<= 6 (say, 10 minutes or less)

# Answer
## Pyth, 10 chars

```
P^cj49J2JQ

```

Try it here. Output is a list of sides each in the format. `[[min0, max0],[min1, max1],...]`.

```
P             All but the last element of
 ^       Q     the nth cartesian power of
   j49J2        the number 49 as a binary list [1,1,0,0,0,1]
  c     J         split into chunks of 2 [[1,1],[0,0],[0,1]]

```

In our output, we want all lists of `n` elements from `[[1,1],[0,0],[0,1]]`, except the one with only `[0,1]`'s. This is just the `n`th cartesian power of `[[1,1],[0,0],[0,1]]` with the last element removed.

The list `[[1,1],[0,0],[0,1]]` is created by converting 49 into binary and breaking into chunks of 2. One can do `.CU2 2` to get `[[0,0],[0,1],[1,1]` as all sorted sublists of 2 elements from `[0,1]`, but we need `[0,1]` at the start or end to remove the list with only it from the product.
> 5 votes

# Answer
## CJam (13 bytes)

```
49Yb2/rim*);`

```

Online demo

Output format is as a list of list of ranges: e.g. for input `1` (where the two sides are the points `(0, 0)` and `(1, 1)`) the output is `[[[1 1]] [[0 0]]]`.

### Dissection

```
49Yb2/   e# Generate the list of ranges: [[1 1] [0 0] [0 1]]
rim*     e# Take the nth Cartesian power
);       e# Remove the last one, which is the full hypercube
`        e# Format for output

```
> 4 votes

# Answer
# Ruby, ~~66~~ 63

Returns an array of strings, each one containing 2n `0`s and `1`s without separators.

```
->n{(0..3**n-2).map{|i|s=""
n.times{s+="0011"[-i%3,2];i/=3}
s}}

```

In a similar way to at at least one other answer it generates all possibilities of `["00","11","01"]` repeated n times, except `"0101....0101"`, by iterating through all the n-digit base 3 numbers `00..00` to `22..21` (deliberately missing `22..22`) and then substituting. Initially I had the string `"011101"` (`"01"` had to be at the end) but then I realised if I fed `-i` instead of `i` to the `%3` operation, I could swap the 2 and 1. I was then able to reduce the string to `"0011"`, overlapping the three possible 2-character strings I required.

**Ungolfed in test program**

```
f=->n{
  (0..3**n-2).map{|i|            #iterate through all n-digit base 3 numbers 00..00 to 22..21
    s=""
    n.times{                     #for each base 3 digit in i append the following to s
      s+="0011"[-i%3,2]          #0 --> 0 -->"00";   -1 --> 2 --> "11";   -2 --> 1 --> "01"
      i/=3                       #divide by 3 to remove the last base 3 digit from i
    }
    s                            #add s to the array being built by map.
  }
}

puts f[gets.to_i]

```

**Output n=2**

```
0000
1100
0100
0011
1111
0111
0001
1101

```
> 3 votes

# Answer
## CJam, 24 bytes

```
2ri2*m*{2/__:$=\2,a-*},p

```

Uses the same interleaved `[min0 max0 min1 max1 ...]` format as the test cases in the challenge. It solves `N = 10` in a couple of minutes.

Test it here.

### Explanation

```
2      e# Push a 2.
ri     e# Read input and convert to integer N.
2*     e# Multiply by 2.
m*     e# Get all 2N-tuples consisting of 0 and 1 as potential sides. A tuple is a valid
       e# side if a) all of its min/max pairs are sorted and b) not all of them are [0 1],
       e# because that corresponds to the entire N-dimensional hypercube.
{      e# Filter the tuples...
  2/   e#   Split the tuple into min/max pairs.
  __   e#   Make two copies.
  :$   e#   Sort each pair in the second copy.
  =    e#   Check for equality with the first copy.
  \    e#   Swap with the original list of pairs.
  2,a- e#   Remove all [0 1].
  *    e#   Repeat this array 0 or 1 times depending on the first result. This effectively
       e#   computes the logical AND of two truthy/falsy values.
},
p      e# Pretty-print the list of sides.

```
> 2 votes

# Answer
## ES7, 88 bytes

```
n=>[...Array(3**n-1)].map((_,i)=>[...(3**n+i).toString(3).slice(1)].map(x=>[x%2,+!!x]))

```

Turns out I ended up porting the Ruby solution, except I return a list of an array of a pair of bounds for each dimension, since that makes for the shortest code.
> 0 votes

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


title: Prime polynomials

text:
# Question
Title: Prime polynomials
Given a polynomial, determine whether it's prime.

A polynomial is `ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g`, where each term is a constant number (the coefficient) multiplied by a nonnegative integer power of `x`. The highest power with a nonzero coefficient is called the degree. For this challenge, we only consider polynomials of at least degree 1. That is, each polynomial contains some `x`. Also, we only use polynomials with integer coefficients.

Polynomials can be multiplied. For example, `(x+3)(2x^2-2x+3)` equals `2x^3+4x^2-3x+9`. Thus, `2x^3+4x^2-3x+9` can be factored into `x+3` and `2x^2-2x+3`, so it is composite.

Other polynomials can not be factored. For example, `2x^2-2x+3` is not the product of any two polynomials (ignoring constant polynomials or those with non-integer coefficients). Hence, it is prime (also known as irreducible).

## Rules

* Input and output can be through any standard way.
* Input can be a string like `2x^2-2x+3`, a list of coeffecients like `{2,-2,3}`, or any similar means.
* Output is either a truthy value if it's prime, or a falsey value if it's composite. You must yield the same truthy value for all primes, and the same falsey value for all composite polynomials.
* The input will be of at least degree 1 and at most degree 10.
* You may not use built-in tools for factorization (of integers or expressions) or equation solving.

## Examples

### True - prime

```
x+3
-2x
x^2+x+1
x^3-3x-1
-2x^6-3x^4+2
3x^9-8x^8-3x^7+2x^3-10

```

### False - composite

```
x^2
x^2+2x+1
x^4+2x^3+3x^2+2x+1
-3x^7+5x^6-2x
x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12

```

# Answer
# Mathematica, 224 bytes

```
f@p_:=(e=p~Exponent~x;r=Range[⌈e/-4⌉,(e+2)/4];e<2||FreeQ[PolynomialRemainder[p,Thread@{r,#}~InterpolatingPolynomial~x,x]&/@Tuples[#~Join~-#&[Join@@Position[#/Range@Abs@#,_Integer]]&/@#]~DeleteCases~{(a_)..},0|{}]&[p/.x->r])

```

---

**Explanation**:

Kronecker's method is used here. This method generates certain lower degree polynomials and tests whether there exists a factor of the original polynomial.

**Test cases**:

```
f/@{x+3, -2x, x^2+x+1, x^3-3x-1, -2x^6-3x^4+2, 3x^9-8x^8-3x^7+2x^3-10}
(* {True, True, True, True, True, True} *)

f/@{x^2, x^2+2x+1, x^4+2x^3+3x^2+2x+1, -3x^7+5x^6-2x, x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12}
(* {False, False, False, False, False} *)

```

It takes 14s on my laptop to conclude that `3x^9-8x^8-3x^7+2x^3-10` is prime.
> 5 votes

# Answer
## PARI/GP, 16 bytes, cheap as hell

For some reason this wasn't disallowed (noting that the command doesn't factor or equation-solve):

```
polisirreducible

```

Test case

```
%(x^2+x+1)

```

returns `1` (true). The other examples work similarly.

But to show that this is solvable the hard way, here's a full solution.

## Less cheap, but sloooooooooow

There's really no point golfing this.

```
Beauzamy(P)=
{
  my(d=poldegree(P),s,c);
  s=sum(i=0,d,polcoeff(P,i)^2/binomial(d,i));
  c = 3^(3/2 + d);
  c *= s / (4*d*Pi);
  abs(c * pollead(P))
}
factorpol(P)=
{
  my(B=Beauzamy(P)\1, t=B*2+1, d=poldegree(P)\2, Q);
  for(i=0,t^(d+1)-1,
    Q=Pol(apply(n->n-B, digits(i,t)));
    if(Q && poldegree(Q) && P%Q==0, return(Q))
  );
  0
}
irr(P)=
{
  factorpol(P)==0
}

```

Edit: Commenters have pointed out that the first method may be disallowed by good taste, the spirit of the rules, the Geneva Convention, standard loophole rules, etc. I don't agree, but in any case I posted the second version along with the first and certainly it seems acceptable.
> 2 votes

---
Tags: code-golf, math, primes, polynomials
---


# Question
Title: Can I make that shape with blocks, slabs, and stairs?
Consider a rectangular two-dimensional grid where each cell can either be empty (`.`) or full (`0`).

e.g.

```
..00....
0000....
.00000..
000...00
..000000
000.00..

```

The grid is considered infinite, all cells outside the depicted region are empty.

The goal is to cover the filled spaces and leave the empty spaces open using a set of 7 distinctly shaped bricks that each take up 4 cells (2×2) of the grid.

These are the 7 bricks:

* Blocks - 1 variant

```
11
11

```
* Slabs - 2 variants

```
..
22
```

```
33
..
```
* Stairs - 4 variants

```
.4
44
```

```
5.
55
```

```
66
.6
```

```
77
7.
```

These bricks must always align to a grid whose cells are twice as wide and tall as the cells of the input grid. Each brick can only occupy one cell of this larger grid but the smaller grid can be translated (shifted up, down, left, right) beneath the larger grid to give more options for finding a cover. Neither of the grids nor individual bricks may be rotated.

So one way to cover (a.k.a. solve) the example above is like this:

```
..11....
2211....
.47733..
447...22
..771133
227.11..

```

(Identical neighboring bricks can still cause ambiguity but carefully identifying the larger grid resolves that.)

An **invalid** solution for

```
000000
000000

```

is

```
566774
556744

```

because the bricks do not all align to the larger grid nor only occupy one cell of it.

A valid solution here is 3 blocks in a row:

```
111111
111111

```

And another valid solution involves 6 slabs:

```
......
222222
333333
......

```

So note that some input grids have **multiple solutions**.

An **invalid** solution for

```
00.00
00...

```

is

```
11.33
11...

```

because the bricks don't align to the larger grid. The slab would need to move left or right by one, but then of course the cover would be incomplete. This input grid has **no solution**.

# Challenge

Write a program that takes in (via stdin/command line) a rectangular block of text of `.`'s and `0`'s that represents a grid to be covered.

If there is a valid covering solution, print (via stdout) any *one* solution in the same manner as above, replacing all `0`'s with the appropriate `1` through `7` bricks.

If there is no solution, your program should not output anything, just quietly end normally.

## Notes

* The input and output do not need to have the same rectangular dimensions. Your output can have extraneous rows and/or columns of all `.`'s (as long as they don't invalidate the solution).
* It's also alright to trim rows and column's of all `.`'s if it won't affect the filled spaces. e.g.

```
222222
333333

```

is a valid solution to

```
000000
000000

```

Conversely, the two empty columns in `00..00` could not be removed since that would disarrange the filled spaces.
* You may optionally assume the input has a single trailing newline. A single trailing newline in the output is fine as well, even in the case of no solution.
* Grids that are completely empty (all `.`'s) and the trivial 0×0 grid are not input cases you need to worry about. But the 1×1 `0` grid is, as are all other grids that contain at least one `0`. (You may not assume the width or height of the input grid is even!)
* Instead of a program you may write a function that takes the input as a string argument and prints the output normally or returns it as a string. Any falsy value can be returned if there is no solution.
* You may use any 9 distinct printable ASCII characters in place of `.` `0` `1` `2` `3` `4` `5` `6` `7`. Just be sure to say what your substitutions were! Newlines must remain as is.

## Scoring

The shortest code in bytes wins. Tiebreaker is highest voted post.

*This challenge was inspired by blocks, slabs, and stairs in Minecraft, which follow the same rules described here. If you enjoy PPCG and Minecraft, you may want to check out the PPCG Minecraft Server.*

# Answer
> 6 votes
# **Python - 525 491 478 430 bytes**

```
r=range
def t(s):
 m=s.find("\n")+1
 for q in r(4):
  try:
   for i in r(-q%2,m-1,2):
    for j in r(-q/2,len(s)/m,2):
     k,g=j*m+i,""
     b=[k,k+1,k+m,k+m+1]
     for z in b:g+=a(s,z)
     for z in b:
      if a(s,z)!="d":s=s[:z]+`dict(dddd=0,zzdd=3,ddzz=2,zzzd=7,zzdz=6,zdzz=5,dzzz=4,zzzz=1)[g]`+s[z+1:]
   return s
  except:d
def a(v,i):
 try:
  if v[i]!="\n":return v[i]
  return "d"
 except:return "d"

```

**Explanation:** This is my first code golf, so it might not be optimal, but here's how it works. The function t(s) gives the result for the string passed in. First, it finds the number of columns, then goes through the four possible distinct translations by 1 (none, left, up, up-left) and tries to solve it for each one. It looks at each 2x2 block and maps it to a valid block number, given by a dictionary, and changes the zeros to the number.

If it finds one not in the dictionary, it abandons that specific offset and starts over with the next one. If it goes through all 4 offsets without finding a valid solution, it ends without outputting anything. a(v, i) allows for the default value outside the string, and ignores newline characters. Although it may end up with partial solutions through the duration of the run, it will always override them with the final correct one if it exists.

**Edit:** A different mapping of characters is used: . -\> d, 0 -\> z, all other numbers go to themselves. This applies to both input and output.

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


# Question
Title: Deciphering Option-Key Special Characters
## Back-story

After typing up your essay on your new Macbook, you look up at the screen and realize that you typed in ten pages of gibberish! Or is it? On further inspection, you come to find that your Option key was stuck this whole time and these special Option-key characters correspond to the ASCII keys on your keyboard!

## Challenge

Your challenge is to write the shortest possible program or function that converts an encoded Option-key input into ASCII output.

Here's the Option-key special characters to ASCII characters dictionary:

```
+---------+-------+-------+-------+
| OPT-KEY |  CODE | ASCII |  CODE |
+---------+-------+-------+-------+
|    ¡    |   161 |   1   |    49 |
|    ™    |  8482 |   2   |    50 |
|    £    |   163 |   3   |    51 |
|    ¢    |   162 |   4   |    52 |
|    ∞    |  8734 |   5   |    53 |
|    §    |   167 |   6   |    54 |
|    ¶    |   182 |   7   |    55 |
|    •    |  8226 |   8   |    56 |
|    ª    |   170 |   9   |    57 |
|    º    |   186 |   0   |    48 |
|    –    |  8211 |   -   |    45 |
|    ≠    |  8800 |   =   |    61 |
|    œ    |   339 |   q   |   113 |
|    ∑    |  8721 |   w   |   119 |
|    ®    |   174 |   r   |   114 |
|    †    |  8224 |   t   |   116 |
|    ¥    |   165 |   y   |   121 |
|    ø    |   248 |   o   |   111 |
|    π    |   960 |   p   |   112 |
|    “    |  8220 |   [   |    91 |
|    ‘    |  8216 |   ]   |    93 |
|    «    |   171 |   \   |    92 |
|    å    |   229 |   a   |    97 |
|    ß    |   223 |   s   |   115 |
|    ∂    |  8706 |   d   |   100 |
|    ƒ    |   402 |   f   |   102 |
|    ©    |   169 |   g   |   103 |
|    ˙    |   729 |   h   |   104 |
|    ∆    |  8710 |   j   |   106 |
|    ˚    |   730 |   k   |   107 |
|    ¬    |   172 |   l   |   108 |
|    …    |  8230 |   ;   |    59 |
|    æ    |   230 |   '   |    39 |
|    Ω    |   937 |   z   |   122 |
|    ≈    |  8776 |   x   |   120 |
|    ç    |   231 |   c   |    99 |
|    √    |  8730 |   v   |   118 |
|    ∫    |  8747 |   b   |    98 |
|    µ    |   181 |   m   |   109 |
|    ≤    |  8804 |   ,   |    44 |
|    ≥    |  8805 |   .   |    46 |
|    ÷    |   247 |   /   |    47 |
|         |   160 |       |    32 |
|    ⁄    |  8260 |   !   |    33 |
|    €    |  8364 |   @   |    64 |
|    ‹    |  8249 |   #   |    35 |
|    ›    |  8250 |   $   |    36 |
|    ﬁ    | 64257 |   %   |    37 |
|    ﬂ    | 64258 |   ^   |    94 |
|    ‡    |  8225 |   &   |    38 |
|    °    |   176 |   *   |    42 |
|    ·    |   183 |   (   |    40 |
|    ‚    |  8218 |   )   |    41 |
|    —    |  8212 |   _   |    95 |
|    ±    |   177 |   +   |    43 |
|    Œ    |   338 |   Q   |    81 |
|    „    |  8222 |   W   |    87 |
|    ‰    |  8240 |   R   |    82 |
|    ˇ    |   711 |   T   |    84 |
|    Á    |   193 |   Y   |    89 |
|    Ø    |   216 |   O   |    79 |
|    ∏    |  8719 |   P   |    80 |
|    ”    |  8221 |   {   |   123 |
|    ’    |  8217 |   }   |   125 |
|    »    |   187 |   |   |   124 |
|    Å    |   197 |   A   |    65 |
|    Í    |   205 |   S   |    83 |
|    Î    |   206 |   D   |    68 |
|    Ï    |   207 |   F   |    70 |
|    ˝    |   733 |   G   |    71 |
|    Ó    |   211 |   H   |    72 |
|    Ô    |   212 |   J   |    74 |
|        | 63743 |   K   |    75 |
|    Ò    |   210 |   L   |    76 |
|    Ú    |   218 |   :   |    58 |
|    Æ    |   198 |   "   |    34 |
|    ¸    |   184 |   Z   |    90 |
|    ˛    |   731 |   X   |    88 |
|    Ç    |   199 |   C   |    67 |
|    ◊    |  9674 |   V   |    86 |
|    ı    |   305 |   B   |    66 |
|    Â    |   194 |   M   |    77 |
|    ¯    |   175 |   <   |    60 |
|    ˘    |   728 |   >   |    62 |
|    ¿    |   191 |   ?   |    63 |
+---------+-------+-------+-------+

```

It's not that simple though... There are a five Option-key special characters that do not follow this trend, specifically (Option-key special characters and their corresponding lowercase ASCII characters):

```
Beginning of input or after special space (" ", code 160):

+---------+-------+-------+-------+
| OPT-KEY |  CODE | ASCII |  CODE |
+---------+-------+-------+-------+
|    `    |    96 |   ~   |   126 |
|    ´    |   180 |   E   |    69 |
|    ¨    |   168 |   U   |    85 |
|    ˆ    |   710 |   I   |    73 |
|    ˜    |   732 |   N   |    78 |
+---------+-------+-------+-------+

Otherwise:

+---------+-------+-------+-------+
| OPT-KEY |  CODE | ASCII |  CODE |
+---------+-------+-------+-------+
|    `    |    96 |   `   |    96 |
|    ´    |   180 |   e   |   101 |
|    ¨    |   168 |   u   |   117 |
|    ˆ    |   710 |   i   |   105 |
|    ˜    |   732 |   n   |   110 |
+---------+-------+-------+-------+

```

When any of these characters are found after the Option-key special space character () or at the beginning of the input, output the capitalized version of their ASCII equivalents. (Note that the capitalized version of "\`" is "~".) Otherwise, output the lowercase version of their ASCII equivalents.

Finally, do not attempt to decode any other characters, just output them.

## Rules & Grading

* All Code-Golf rules barring standard loopholes apply.
* Scores will be based on the number of bytes your program uses.
* The program with the smallest score (or the smallest number of bytes) will win!

## Examples

Input, output:

```
`´¨ˆ˜`
~euin`

´´ ´⁄
Ee E!

`` ´ ¨ ˆ ˜
~` E U I N

Ó´¬¬ø ∑ø®¬∂⁄
Hello world!

„˙å† ˆß ¥ø¨® ˜åµ´¿      Í´®©´å˜† ıˆ¬¬ˆå®∂ß⁄
What Is your Name?      Sergeant Billiards!

„˙´®´ ∂ø ¥ø¨ çøµ´ ƒ®øµ¿
Where do you come from?

„˙´˜ ˆ µø√´∂ †ø Áø®˚ß˙ˆ®´≤ †˙´®´ ∑åß å µå˜ ∑åˆ†ˆ˜© ƒø® µ´≥
When I moved to Yorkshire, there was a man waiting for me.

Óˆß ˜åµ´ ∑åß ∏å¬´ß†ˆ˜´≥ Ó´ çåµ´ ƒ®øµ Òå˜∂ø≥
His Name was Palestine. He came from Lando.

Åç®øßß †˙´ ®´´ƒ ¬å¥ ˜ø†˙ˆ˜©≥
Across the reef lay Nothing.

Â¥ ˜åµ´ ˆß ´å†ø˜≥
My Name Is Eaton.

ˆ˜† µåˆ˜·√øˆ∂‚ ” ß†∂ÚÚçø¨† ¯¯ ÆÓ´¬¬ø ∑ø®¬∂⁄Æ… ’
Int main(void) { std::cout << "Hello world!"; }

¡ ·™£¢‚ ∞§¶–•ª¡º
1 (234) 567-8910

ÓÅ‰Î ˇØ ˝´ˇ ÅÒÒ ÇÅ∏Í⁄
HARD TO GeT ALL CAPS!

Ø‰ ˆÍ ˆˇ¿
OR IS IT?

Ó´æß ˆ˜ †˙´ †øπ ¡ººﬁ⁄
He's In the top 100%!

```

# Answer
# JavaScript (ES6), 354 bytes (231 characters)

```
t=>[...t].map((c,i)=>~(x="`´¨ˆ˜".indexOf(c))?(t[i-1]==" "|!i?"~EUIN":"`euin")[x]:~(a=" ⁄`‹›ﬁ‡`·‚°±≤–≥÷º¡™£¢∞§¶•ªÚ…¯≠˘¿€ÅıÇÎ`Ï˝Ó`ÔÒÂ`Ø∏Œ‰Íˇ`◊„˛Á¸“«‘ﬂ—`å∫ç∂`ƒ©˙`∆˚¬µ`øπœ®ß†`√∑≈¥Ω”»’æÆ".indexOf(c))?String.fromCharCode(a+32):c).join``

```

## Explanation

*Note: This byte counter says it is 278 bytes, but I don't know what (if any) encoding it is using, so I went with UTF-8 for the byte count.*

```
t=>
  [...t].map((c,i)=>                      // for each character c at index i
    ~(x="`´¨ˆ˜".indexOf(c))?              // if it is a special character
      (t[i-1]==" "|!i?"~EUIN":"`euin")[x] // handle it
    :~(
      a=                                  // a = ASCII code of equivalent character (or -1)

        // Option characters, the index of each option character is the code of it's ASCII
        //     equivalent - 32, ` is used to pad empty positions since it will never match
        " ⁄`‹›ﬁ‡`·‚°±≤–≥÷º¡™£¢∞§¶•ªÚ…¯≠˘¿€ÅıÇÎ`Ï˝Ó`ÔÒÂ`Ø∏Œ‰Íˇ`◊„˛Á¸“«‘ﬂ—`å∫ç∂`ƒ©˙`∆˚¬µ`øπœ®ß†`√∑≈¥Ω”»’æÆ"

        .indexOf(c)
    )?String.fromCharCode(a+32)           // return the ASCII character if an option
                                          //     character was matched
    :c                                    // else return the character unchanged
  )
  .join``                                 // return output

```

## Test

```
var solution = t=>[...t].map((c,i)=>~(x="`´¨ˆ˜".indexOf(c))?(t[i-1]==" "|!i?"~EUIN":"`euin")[x]:~(a=" ⁄Æ‹›ﬁ‡æ·‚°±≤–≥÷º¡™£¢∞§¶•ªÚ…¯≠˘¿€ÅıÇÎ`Ï˝Ó`ÔÒÂ`Ø∏Œ‰Íˇ`◊„˛Á¸“«‘ﬂ—`å∫ç∂`ƒ©˙`∆˚¬µ`øπœ®ß†`√∑≈¥Ω”»’".indexOf(c))?String.fromCharCode(a+32):c).join``
```

```
<input type="text" id="input" value="„˙´˜ ˆ µø√´∂ †ø Áø®˚ß˙ˆ®´≤ †˙´®´ ∑åß å µå˜ ∑åˆ†ˆ˜© ƒø® µ´≥" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```
> 3 votes

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