title: A determinant optimization challenge

text:
# Question
Title: A determinant optimization challenge
Consider 30 by 30 Toeplitz matrices all of whose entries are 0 or 1. This challenge is a simple optimization challenge to find the matrix with the largest determinant possible.

**Input** None

**Output** A 30 by 30 Toeplitz matrix all of whose entries are 0 or 1 along with its determinant.

**Score** The determinant of the matrix you output. If two people get the same score, the first answer wins.

**Leading entries so far**

* 65,455,857,159,975 in **Matlab** by Nick Alger (roughly (10^13.8)
* 65,455,857,159,975 in **Python** by isaacg (roughly 10^13.8)
* 39,994,961,721,988 in **Mathematica** by 2012rcampion ( roughly 10^13.6)
* 39,788,537,400,052 in **R** by Flounderer (roughly 10^13.6)
* 8,363,855,075,832 in **Python** by Vioz- (roughly 10^12.9)
* 6,984,314,690,903 in **Julia** by Alex A. (roughly 10^12.8)

---

**Annoying additional constraints July 16 2015**

If it is at all possible, please use arbitrary or high precision arithmetic to compute the final output determinant so that we can be sure what it really is (it should always be an integer). In python this should be helpful.

# Answer
> 11 votes
# Matlab, 65,455,857,159,975 (10^13.8159)

The method is gradient ascent in the interior of the cube \[0,1\]^59, with many random initial guesses, and rounding at the end to make everything zeros and ones.

**Matrix:**

```
0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0
0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1
1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1
1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1
1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0
0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1
1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1
1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1
1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0
0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1
1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0
0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0
0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0
0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1
1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0   0
0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1   0
0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0   1
1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1   0
0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1   1
1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0   1
1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1   0
0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0   1
1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0   0
0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0   0
0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0   0
0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1   0
0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1   1
1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1   1
1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0   1
1   1   1   0   0   0   0   1   0   1   1   0   1   0   0   1   0   0   0   1   0   1   1   1   0   1   1   1   0   0

```

**Code:**

```
% Toeplitz 0-1 determinant optimization

n = 30;
m = n + n-1;

toeplitz_map = @(w) toeplitz(w(n:-1:1), w(n:end));

objective = @(w) det(toeplitz_map(w));

detgrad = @(A) det(A)*inv(A)';

toeplitz_map_matrix = zeros(n^2,m);
for k=1:m
    ek = zeros(m,1);
    ek(k) = 1;
    M = toeplitz_map(ek);
    toeplitz_map_matrix(:,k) = M(:);
end

gradient = @(w) (reshape(detgrad(toeplitz_map(w)),1,n^2)*...
                 toeplitz_map_matrix)';

%check gradient with finite differences
w = randn(m,1);
dw = randn(m,1);
s = 1e-6;
g_diff = (objective(w+s*dw) - objective(w))/s;
g = gradient(w)'*dw;
grad_err = (g - g_diff)/g_diff

warning('off')
disp('multiple gradient ascent:')
w_best = zeros(m,1);
f_best = 0;
for trial=1:100000
    w0 = rand(m,1);
    w = w0;
    alpha0 = 1e-5; %step size
    for k=1:20
        f = objective(w);
        g = gradient(w);
        alpha = alpha0;
        for hh=1:100
            w2 = w + alpha*g;
            f2 = objective(w2);
            if f2 > f
                w = w2;
                break;
            else
                alpha = alpha/2;
            end
        end

        buffer = 1e-4;
        for jj=1:m
            if (w(jj) > 1)
                w(jj) = 1 - buffer;
            elseif (w(jj) < 0)
                w(jj) = 0 + buffer;
            end
        end
    end

    w = round(w);
    f = objective(w);
    if f > f_best
        w_best = w;
        f_best = f;
    end
    disp(trial)
    disp(f_best)
    disp(f)
end

M = toeplitz_map(w_best);

```

**The math behind computing the gradient:**

In the elementwise inner product (Ie., Hilbert-Schmidt inner product), the gradient of the determinant has Riesz representative G given by

G = det(A)A^(-\*).

The map, J, from optimization variables (diagonal values) to toeplitz matrices is linear, so the overall gradient g is the composition of these two linear maps,

g = (vec(G)\*J)',

where vec() is the vectorization operator that takes a matrix and unfolds it into a vector.

**Interior gradient ascent:**

After this all you have to do is pick an initial vector of diagonal values w\_0, and for some small step sizes alpha iterate:

1. w\_proposed = w\_k + alpha\*g\_k
2. to get w\_(k+1), take w\_proposed and truncate values outside of \[0,1\] to 0 or 1
3. repeat until satisfied, then round everything to 0 or 1.

My result achieved this determinant after doing roughly 80,000 trials with uniform random initial guesses.

# Answer
> 11 votes
# Python 2 with Numpy, 65,455,857,159,975 ~= 10^13.8

This is hill climbing, as straightforward as can be. Final determinant calculation performed using SymPy to enusure an exact result. All matrices found with this determinant are circulant.

Matrices found with this determinant, given as value of diagonal from bottom left to upper right:

```
01000100101101000011100111011101000100101101000011100111011
01011101110011100001011010010001011101110011100001011010010
01100001000111011101001110100101100001000111011101001110100
01110100111010010110000100011101110100111010010110000100011
01011101110001000011010010111001011101110001000011010010111
01000101100010110100111101110001000101100010110100111101110
01000100101101000011100111011101000100101101000011100111011

```

The first one, as a matrix:

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

```

Code:

```
import numpy as np
import sympy as sp
import random
import time
SIZE = 30

random.seed(0)

def gen_diag():
    return [random.randint(0, 1) for i in range(SIZE*2 - 1)]

def diag_to_mat(diag):
    return [diag[a:a+SIZE] for a in range(SIZE-1, -1, -1)]

def diag_to_det(diag):
    matrix = diag_to_mat(diag)
    return np.linalg.det(matrix)

def improve(diag):
    old_diag = diag
    really_old_diag = []
    while really_old_diag != old_diag:
        really_old_diag = old_diag
        for flip_at in range(SIZE * 2 - 1):
            new_diag = old_diag[:]
            new_diag[flip_at] ^= 1
            old_diag = max(old_diag, new_diag, key=diag_to_det)
    return old_diag

overall_best_score = 0
time.clock()
while time.clock() < 500:
    best = improve(gen_diag())
    best_score = diag_to_det(best)
    if best_score > overall_best_score:
        overall_best_score = best_score
        overall_best = best
        print(time.clock(), sp.Matrix(diag_to_mat(overall_best)).det(), ''.join(map(str,overall_best)))

mat = diag_to_mat(overall_best)

sym_mat = sp.Matrix(mat)

print(overall_best)
print(sym_mat.det())

```

# Answer
> 10 votes
# R, 39 788 537 400 052

Here is my attempt to do a genetic algorithm but only with asexual reproduction. I hope I understood the challenge correctly. Edit: sped it up a bit, tried a different random seed, and restricted to 100 generations.

```
    options(scipen=999)

toeplitz <- function(x){
# make toeplitz matrix with first row
# x[1:a] and first col x[(a+1):n]
# where n is the length of x and a= n/2
# Requires x to have even length
#
# [1,1] entry is x[a+1]

N <- length(x)/2
out <- matrix(0, N, N)
out[1,] <- x[1:N]
out[,1] <- x[(N+1):length(x)]
for (i in 2:N){
  for (j in 2:N){
    out[i,j] <- out[i-1, j-1]
  }
}

out
}

set.seed(1002)

generations <- 100
popsize <- 25
cols <- 60
population <- matrix(sample(0:1, cols*popsize, replace=T), nc=cols)
numfresh <- 5 # number of totally random choices added to population

for (i in 1:generations){

fitness <- apply(population, 1, function(x) det(toeplitz(x)) )
mother <- which(fitness==max(fitness))[1]

population <- matrix(rep(population[mother,], popsize), nc=cols, byrow=T)
for (i in 2:(popsize-numfresh)){
  x <- sample(cols, 1)
  population[i,x] <- 1-population[i,x]
}
for (i in (popsize-numfresh +1):popsize){
  population[i,] <- sample(0:1, cols, replace=T)
}

print(population[1,])
print(fitness[mother])
print(det(toeplitz(population[1,]))) # to check correct

}

```

Output:

```
print(population[1, 1:(cols/2)]) # first row
print(population[1, (cols/2+1):(cols)]) # first column (overwrites 1st row)

to <- toeplitz(population[1,])

for (i in 1:(cols/2)) cat(to[i,], "\n")

1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0
0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1
1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0
0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0
0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0
0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1
1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1
1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1
1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1
1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0
0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1
1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1
1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1
1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0
0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0 0
0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 0
0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0
0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0 1
1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0
0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 0
0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0
0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0
0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1
1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0
0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1
1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1
1 1 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1

```

# Answer
> 3 votes
# Julia, 6,984,314,690,902.998

This just constructs 1,000,000 random Toeplitz matrices and checks their determinants, recording the maximum encountered. Hopefully someone will come up with an elegant analytical solution, but in the meantime...

```
function toeplitz(a, b)
    n = length(a)
    T = Array(Int, n, n)
    T[1,:] = b
    T[:,1] = a
    for i = 2:n
        T[i,2:n] = T[i-1,1:n-1]
    end
    T
end

d = 0
A = Any[]

for i = 1:1000000
    # Construct two random 0,1 arrays
    r1 = rand(0:1, 30)
    r2 = rand(0:1, 30)

    # Compute the determinant of a toeplitz matrix constructed
    # from the two random arrays
    D = det(toeplitz(r1, r2))

    # If the computed determinant is larger than anything we've
    # encountered so far, add it to A so we can access it later
    D > d && begin
        push!(A, (D, r1, r2))
        d = D
    end
end

M,N = findmax([i[1] for i in A])

println("Maximum determinant: ", M, "\n")
println(toeplitz(A[N][2], A[N][3]))

```

You can view the output here.

# Answer
> 3 votes
# Mathematica, 39,994,961,721,988 (10^13.60)

A simple simulated annealing optimization method; no optimization or tuning yet.

```
n = 30;
current = -\[Infinity];
best = -\[Infinity];
saved = ConstantArray[0, {2 n - 1}];
m := Array[a[[n + #1 - #2]] &, {n, n}];
improved = True;
iters = 1000;
pmax = 0.1;
AbsoluteTiming[
 While[improved || RandomReal[] < pmax,
   improved = False;
   a = saved;
   Do[
    Do[
      a[[i]] = 1 - a[[i]];
      With[{d = Det[m]},
       If[d > best,
          best = d;
          current = d;
          saved = a;
          improved = True;
          Break[];,
          If[d > current || RandomReal[] < pmax (1 - p/iters),
           current = d;
           Break[];,
           a[[i]] = 1 - a[[i]];
           ]
          ];
        ;
       ],
      {i, 2 n - 1}];,
    {p, iters}];
   ];
 ]
best
Log10[best // N]
a = saved;
m // MatrixForm

```

Sample output:

```
{20.714876,Null}
39994961721988
13.602
(1  1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0
0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0
0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0
0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0
0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1
1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0
0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0
0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0
0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0
0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1
1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1
1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0
0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1
1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1
1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1   0
0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1   1
1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1   1
1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0   1
1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1   0
0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1   1
1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0   1
1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0   0
0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0   0
0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0   0
0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1   0
0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0   1
1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1   0
0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1   1
1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1   1
1   1   0   1   0   0   0   0   1   1   0   1   1   1   0   1   1   0   1   1   0   0   0   0   1   0   0   0   0   1

)

```

# Answer
> 1 votes
# Python 2, 8 363 855 075 832

This has a very basic, nearly nonexistent strategy involved.

```
from scipy import linalg

start = 2**28
mdet  = 0
mmat  = []
count = 0
powr  = 1
while 1:
 count += 1
 v = map(int,bin(start)[2:].zfill(59))
 m = [v[29:]]
 for i in xrange(1,30):
     m += [v[29-i:59-i]]
 d = 0
 try: d = linalg.det(m, check_finite=False)
 except: print start
 if d > mdet:
     print d
     print m
     mdet = d
     mmat = m
     start += 1
     powr = 1
 else:
     start += 2**powr
     powr += 1
     if start>(2**59-1):
         start-=2**59-1
         powr = 1
 if count%10000==0: print 'Tried',count

```

Here is the best matrix it found after ~5,580,000 tries:

```
1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0
1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0 1
1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1 0
0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1 1
1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0 1
0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1 0
1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0 1
0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0 0
0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1 0
1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0 1
1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 0
0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0
0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0 0
0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0 0
0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0 0
0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1 0
1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1 1
0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1 1
1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 1
1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0
1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1
1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1
1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1
1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1 0
1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1 1
1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0 1
0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0 0
0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 0
1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1
0 1 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1

```

Still running...

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


# Question
Title: Approximate a given image using only colors from a given list
# The Specs

* Your program must read the image from one file and write the results to another file, the name of at least the first of which should be taken from the input
* You may accept and return any image format or formats, as long as you specify in your answers which ones you are using
* An exception should be thrown if the specified source file does not exist
* The final image must be as close as possible to the initial image (by per-pixel euclidean metric on RGB values) while using only colors from a list read from the file "colors.txt" (it will not necessarily use all of them)
* When determing the nearest color, you should use the euclidean metric on RGB values, Δc=sqrt((Δr)2+(Δg)2+(Δb)2), when two or more colors on the list are equally close, any of those colors is valid
* The list of colors given will be formatted with one rgb color code on each line, with spaces seperating the red, green, and blue values
* You may assume that at least three but no more than 1,000 colors will be listed

**This is code golf, so the shortest program wins**

# Some test cases:

**(if RGB values in the output images do not exactly match those in the list, this is due to a problem with Java's ImageIO.write)**

input:

colors.txt:

```
255 0 0
250 150 0
255 50 0
0 0 200
0 0 80
0 0 0

```

output:

---

input:

colors.txt:

```
100 60 0
0 0 20
0 0 70
0 20 90
15 15 15
100 100 100
120 120 120
150 150 150

```

output:

---

input:

colors.txt:

```
0 0 0
10 20 15
25 25 20
35 30 20
40 35 25
55 55 60
70 60 50
130 100 80
130 140 145
140 100 70
165 130 90
200 160 130
230 210 220
250 250 250

```

output:

---

input:

colors.txt:

```
0 0 0
70 50 40
80 0 0
120 100 90
120 120 120
170 150 90
170 170 170
170 200 195
190 140 100
190 205 165
210 170 120

```

output:

Again, I put together a java program to generate the sample output. I'll golf it down a little further, and then I may post it as an answer later.

# Answer
> 3 votes
# Mathematica ~~109 100 97~~ 111

Update: now outputs the image as required.

The function, *f*, replaces a single pixel with the closest pixel found in the input file (in this case, "colors.txt").

*t* is the output file.

The function, *g*, applies *f* to each pixel in the input image.

```
g[i_,h_,t_]:=Export[t,(c=Import[h,"Data"]/255;
f@p_:=Sort[{p~EuclideanDistance~#,#}&/@c][[1,2]];f~ImageApply~i)]

```

**Test Cases**

Example 1: Seascape

```
(*creating "colors.txt"*)
    c = "255 0 0
      250 150 0
      255 50 0
      0 0 200
      0 0 80
      0 0 0";
    Export["colors.txt", c]

```

---

Example 2: Earth from moon

I'll skip the part about storing the color info into "colors.txt". It closely follows example 1.

---

Example 3: Jupiter

---

Example 4: American Gothic

# Answer
> 3 votes
# Python \[3\] + Pillow, 276 272 267

Takes 2 parameters: name of source image file and name of file with colors list. Tested on Py3, may work on Py2 too.

My first attempt in code golf, so probably not very impressive (and similar to dieter's code).

```
import sys
import PIL.Image as P
i,c=sys.argv[1:]
c,z=[tuple(int(i)for i in e.split())for e in open(c).readlines()],P.open(i)
x,y=z.size
p=z.load()
for _ in range(x*y):
    j,k=_//y,_%y
    d={sum((i-j)**2for i,j in zip(p[j,k],a)):a for a in c};p[j,k]=d[min(d)]
z.save(i*2)

```

Ungolfed:

(displays output image instead of saving, and is a bit safer, because removes empty lines from colors file)

```
# coding: utf-8

import sys
from PIL import Image

def similarImage(img, colors):
    if isinstance(img, str):
        img = Image.open(img)
    x, y = img.size
    pixels = img.load()
    for i in range(x):
        for j in range(y):
            pixels[i,j] = getClosestColor(pixels[i,j], colors)
    img.show()

def getColorDistanceSq(c1, c2):
    #root not needed
    return sum((i-j)**2 for i,j in zip(c1, c2))

def getClosestColor(col, colBase):
    colDist = {getColorDistanceSq(col, c) : c for c in colBase}
    return  colDist[min(colDist)]

def parseColors(desc):
    desc = desc.split('\n')
    desc = [i for i in desc if i != '']
    return [tuple(int(i) for i in d.split()) for d in desc]

def main():
    imgFile   = sys.argv[1]
    with open(sys.argv[2]) as f:
        colors = parseColors(f.read())
    similarImage(imgFile, colors)

if __name__ == "__main__": main()

```

# Answer
> 2 votes
# Python 2.7, 279

Reads the name of the input image and the name of the color map for commandline arguments. usage is

```
python script.py <image file> <colors.txt>

```

It saves the new image as a file with the same name, preceded by an extra tilde :

```
from sys import*;from PIL.Image import*;f=argv[1]
c,I,X=[[int(x)for x in l.split()]for l in file(argv[2])],open(f),range
w,h=I.size;P=I.load()
for j in X(h):
 for i in X(w):
  r,g,b=P[i,j];C={(R,G,B):(R-r)**2+(G-g)**2+(B-b)**2for R,G,B in c};P[i,j]=min(C,key=C.get)
I.save('~'+f)

```

# Answer
> 1 votes
# Java, 726 bytes

Too bad all the imports and main class eat up some many bytes, but it's a standalone program after all. Nevertheless, it was a nice and fun challenge to work on.

This golf can be run by issuing `java M.class inputImage.png outputImage.png colours.txt`, or equivalent.

```
import java.awt.*;import java.awt.image.*;import java.io.*;import java.nio.file.*;import javax.imageio.*;class M {public static void main(String[]a)throws Exception{BufferedImage i=ImageIO.read(new File(a[0]));int w,h,k,r,g,b,t,z,q;w=i.getWidth();h=i.getHeight();BufferedImage o=new BufferedImage(w,h,2);for(int x=0;x<w;x++){for(int y=0;y<h;y++){Color v=null;k=i.getRGB(x,y);r=k>>16&0xff;g=k>>8&0xff;b=k&0xff;double e=999;for(String n:Files.readAllLines(Paths.get(a[2]))){String[]m=n.split(" ");t=Integer.parseInt(m[0]);z=Integer.parseInt(m[1]);q=Integer.parseInt(m[2]);double d=Math.sqrt((t-r)*(t-r)+(z-g)*(z-g)+(q-b)*(q-b));if(d<e){e=d;v=new Color(t,z,q);}}o.setRGB(x,y,v.getRGB());}}ImageIO.write(o,"png",new File(a[1]));}}

```

# Answer
> 0 votes
# Java, ~~861~~ ~~849~~ ~~842~~ 836 bytes

I think there's probably room for improvement here.

```
import java.awt.*;import java.awt.image.*;import java.io.*;import java.util.*;import javax.imageio.*;import static java.lang.Math.*;class D{static void g(Color c,ArrayList<Color>h,int x,int y,BufferedImage b){double d=450;Color e=null;for(Color f:h){double g=sqrt(pow(c.getRed()-f.getRed(),2)+pow(c.getGreen()-f.getGreen(),2)+pow(c.getBlue()-f.getBlue(),2));if(g<d){e=f;d=g;}}b.setRGB(x, y, e.getRGB());}public static void main(String[]a)throws Exception{ArrayList<Color>c=new ArrayList<Color>();Scanner b=new Scanner(new File("colors.txt"));while(b.hasNext())c.add(new Color(b.nextInt(),b.nextInt(),b.nextInt()));b=new Scanner(System.in);BufferedImage i=ImageIO.read(new File(b.next()));int x=i.getWidth(),y=i.getHeight();for(;--x>=0;)for(int z=0;z<y;z++)g(new Color(i.getRGB(x,z)),c,x,z,i);ImageIO.write(i,"jpg",new File(b.next()));}}

```

Takes the names of the source and target image files from user input, reads the color list from colors.txt. Supports .jpg, .png, and probably others for input. Supports only .jpg for output.

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


title: Number of valid mazes

text:
# Question
Title: Number of valid mazes
Given a `WxH` grid, how many possible mazes are there?

Things you know about the maze:

1. The grid is exactly `H` squares high and `W` squares wide.
2. There are three types of squares: Start, Finish, and Empty. Your maze must contain exactly 1 Start and 1 Finish, and all remaining squares are Empty.
3. There are walls surrounding the entire maze.
4. Walls can exist on the edge between any two squares, unless it breaks the below rule:
5. There must exist a path from the Start square to the Finish square.

Therefore, given two numbers, `W` and `H`, you must return a single number representing the number of possible square/wall configurations. You are guaranteed that `W*H > 1`

For example, the `2x2` maze has exactly `100` different possible configurations.

This is a so the shortest answer wins!

# Answer
> 3 votes
# Python 2, ~~329~~ 310 bytes

```
from itertools import*
w,h=input()
R=range(w*h)
p=product
n=0
Z=[(x,y)for x,y in p(R,R)if abs(x%w-y%w)+abs(x/w-y/w)<2]
for s,f,W in p(R,R,p(*[((),z)for z in Z if z[0]<z[1]])):
 V={s};C=[s];v=0
 while C:
  c=C.pop();v|=c==f!=s;V|={c}
  for o,q in Z:C+=(c==o)*len({q,(o,q),(q,o)}-(V|set(W)))/3*[q]
 n+=v
print n

```

This is the golfed (and much more inefficient) version of the program I was using while discussing the problem with @Nathan. I can save a few bytes by replacing some space indents with tabs, but I'll save that for later.

The algorithm is simply generate every maze, then flood fill from the start, seeing if we pass the finish at some point or not.

---
Tags: code-golf, maze
---


title: Fill in the Number Blanks

text:
# Question
Title: Fill in the Number Blanks
You are given a list of 2-tuples of positive integers, of the form:

`a1 b1, a2 b2, ..., an bn`

In other words, the 2-tuples are comma-separated, and the integers within each tuple are space-separated. All of the `a` numbers are in strictly increasing order, as well as the `b`s. Your goal is to "fill in the gaps." What is meant by that is the following:

* If ai+1 == ai+1, don't do anything.
* Else if ai+1 \< ai+1, you will insert tuples into the sequence as follows: ai bi, ai+1 bi+1, ai+2 bi+1, ..., ai+1-1 bi+1, ai+1 bi+1.

In other words, if there is a "gap" in the ai, then you will insert more into the list with the inserted `b`s to be bi+1 (the end of the gap).

**Example**:

Input: `6 125, 7 170, 10 185`

Output: `6 125, 7 170, 8 185, 9 185, 10 185`

**Scoring**: the score of the submission is the number of bytes needed to construct a program to, when given a string as described above, output in the same format the "filled" list of tuples.

Lowest score wins!

# Answer
> 2 votes
# Pyth, ~~31~~ 30 bytes

```
Jsrz7Pjds,R+ehfghTdcJ2\,}hJePJ

```

*1 byte thanks to Jakube.*

At the high level, for each number in the range of the a's, the list is filtered for a's greater than that number, then the b from the first such tuple is used as the b.

Demonstration.

# Answer
> 4 votes
# CJam, ~~42~~ ~~41~~ ~~39~~ 38 bytes

```
q~,]:T(\-2=),>{IST2/z~\{I<!}#=,',S}fI&

```

Try it online in the CJam interpreter.

# Answer
> 4 votes
# Python 2, ~~192~~ ~~180~~ 171 Bytes

Unfortunately, it takes a *ton* of bytes to parse the input and format output. Also, thanks to Sp3000 for kicking my brain into gear :)

```
n=[map(int,x.split())for x in input().split(',')]
for i in range(len(n)-1):j=0;exec'print n[i][0]+j,`n[i+(j>0)][1]`+",",;j+=1;'*(n[i+1][0]-n[i][0])
print n[-1][0],n[-1][1]

```

# Answer
> 4 votes
# Python 3.5.0b1+, 123 bytes

```
L=map(eval,(input()+",").split())
o=""
while L:
 *L,a,b=L;x=a-1
 while[x,b,*L][-2]<a:o=", %d %d"%(a,*b)+o;a-=1
print(o[2:])

```

Parsing the input was a pain, so I just ignored it and parsed it as is. This means that

```
6 125, 7 170, 10 185

```

gets parsed as

```
[6, (125,), 7, (170,), 10, (185,)]

```

hence the splat in the string formatting.

# Answer
> 3 votes
# JavaScript (*ES6*), 97 ~~103~~

Finding the question wording hard to understand, I based my work on the example.

~~First try, there could be a shorter way with just 1 split~~ Scanning the input string in a single pass using replace.

```
f=l=>
  l.replace(/\d+/g,b=>{
    for(i=p||a-1;a&&i++<a;p=a)o+=`, ${i} `+b;
    a=a?0:b
  },p=a=o='')
&&o.slice(2)

// TEST

out=x=>O.innerHTML+=x+'\n'

test=v=>out(v+'\n->'+f(v))

test('6 125, 7 170, 10 185')
```

```
<pre id=O></pre>
<input id=I><button onclick='test(I.value)'>-></button>
```

.

# Answer
> 2 votes
# Haskell, 152 bytes

```
p(x,y)=", "++show x++' ':show y
(a:b:c)%x|a<x=c%x|0<1=(x,b)
g a=p.(a%)=<<[0+head a..last$init a]
main=interact$drop 2.g.(map(read.fst).lex=<<).words

```

### How it works

`p` is a simple string formatting helper function:

```
>>> p (6, 125)
", 6 125"

```

`(%)` is a "lookup" function for filling in blanks:

```
>>> let nums = [6, 125, 7, 135, 10, 185]
>>> nums % 8
(8,185)

```

`[head a..last$init a]` is the range of numbers to use: from the first integer parsed until the second-to-last integer parsed. (The `0+` helps the type-checker infer that the whole program deals with `Num` values; otherwise `read` doesn't know what to parse.) Then we `concatMap` (or `=<<`) our previous functions over the range to get one big string. That's what `g` does:

```
>>> g nums
", 6 125, 7 135, 8 185, 9 185, 10 185"

```

Finally, there's `main`. It's of the form `interact$s`, so all we care about is the function `s :: String -> String` that turns *stdin* into *stdout*.

First, to read input, we split into words:

```
>>> (words) "6 125, 7 170, 10 185"
["6","125,","7","170,","10","185"]

```

Then we `concatMap` the function `map(read.fst).lex` over this list. For one word, this does:

```
>>> (map(read.fst).lex) "125," :: [Int]
[125]

```

So for a list of words, you get `concat [[6], [125], [7], ...] == [6, 125, 7...]`, which is the list we want to pass to `g`. Finally, we `drop` the leading `", "` from the string `g` gives us.

# Answer
> 2 votes
# CJam, 34 bytes

```
ri_[_q~,]:,2/::fe&:.e|+ee>Sf*", "*

```

I started with golfing Dennis's answer but finally it becomes nothing like the original.

Try it online.

# Answer
> 2 votes
# Perl, 67 bytes

(66 characters code + 1 character command line option)

```
s/(\b\d+ \d+)(?=, (?!(??{$k=$1+1}) ).+( \d+))/"$1, ".$k.$2/e&&redo

```

Execution example:

```
perl -pe 's/(\b\d+ \d+)(?=, (?!(??{$k=$1+1}) ).+( \d+))/"$1, ".$k.$2/e&&redo' <<< "6 125, 7 170, 10 185"

```

**Explanation:** General approach is to construct a regex which is capable of looking ahead to the next token to determine if it increases by one (regex is rubbish at arithmetic, so we add a perl execution to do the addition, then look for that). If it does not, we replace this match with the original text, plus the new token with the increased index. We then repeat this multiple times on the input until it does not change.

For the below explanation, a 'section' is the comma separated value, and the 'tokens' are the space separated values within this.

```
 s/
   (\b\d+ \d+)             # Matches the first two numbers in a section
   (?=,                 # Look ahead to the next section
     (?!(??{$k=$1+1}) ) # Make sure the first token in the next section is not increased by one, store this value in $k. Happily, although our $1 contains TWO space separated numbers, it increases the first number and ignores the second - strange behaviour in Perl.
     .+                 # Ignore the actual value of first token of the next section (i.e. the index)
     ( \d+)             # Create a backreference on the second (i.e. the value)
   )
 /                      # Start the replacement string...
   "$1, "               # Put the first section back into the result
   .$k                  # Append the increased index
   .$2                  # Append the value of the next token
 /e                     # Modifier - allows us to execute Perl inside the RegEx
 &&redo              # Repeat until it no longer changes the string

```

# Answer
> 1 votes
## C#, 174 bytes

Indented for clarity:

```
class P{
    static void Main(string[]z){
        int a=0,b,i=-1;
        while(++i<z.Length){
            b=int.Parse(z[i++]);
            while(a<b)
                System.Console.Write((a==0?"":", ")+(a+=a==0?b:1)+" "+z[i].Trim(','));
        }
    }
}

```

# Answer
> 1 votes
# Python 3, 232 bytes

Not really *that* short, but it uses a different method to the Python solution already posted

```
l=list(map(int,[y for x in input().split(',')for y in x.split(' ')]))
f=[];x=1
while x:
 x=0
 for i in range(0,len(l)-2,2):
  if l[i+2]-l[i]>1:l[:i+2]+=l[i]+1,;l[:i+3]+=l[i+4],;x+=1
for n in range(len(l)):print(l[n],end=','if n%2 else' ')

```

# Answer
> 1 votes
# Bash + coreutils, 87

```
tr , \\n|while read a b
do for((p=p?p:a-1;p++<a;c=1)){
echo -n ${c+, }$p $b
}
p=$a
done

```

### Test output:

```
$ echo "6 125, 7 170, 10 185" | ./fillblanks.sh
6 125, 7 170, 8 185, 9 185, 10 185

```

# Answer
> 0 votes
## Java, 229 bytes

I *think* I've whittled this down as much as I can. I would be interested to see if there is a better approach that leads to a shorter Java answer:

```
String f(String s){String r="",g=" ",x[]=s.split(",\\s"),z[];int i=0,p=0,l=x.length,a,b;while(i<l){z=x[i].split(g);a=new Integer(z[0]);b=new Integer(z[1]);if(i++>0)while(a>++p)r+=p+g+b+", ";r+=a+g+b+(i==l?"":", ");p=a;}return r;}

```

Formatted:

```
String f(String s) {
    String r = "", g = " ", x[] = s.split(",\\s"), z[];
    int i = 0, p = 0, l = x.length, a, b;
    while (i < l) {
        z = x[i].split(g);
        a = new Integer(z[0]);
        b = new Integer(z[1]);
        if (i++ > 0)
            while (a > ++p)
                r += p + g + b + ", ";
        r += a + g + b + (i == l ? "" : ", ");
        p = a;
    }
    return r;
}

```

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


title: ASCII art compression

text:
# Question
Title: ASCII art compression
The following challenge is basically a simpler version of the one proposed by Dennis (Lossy ASCII art compression). I found the idea super interesting but a bit too convulted, and seeing as it didn't seem to be getting much attention I decided to modify it a little bit.

You'll be downloading 5 ASCII art text files, each of them composed only of the following characters:

```
@#+';:,.`

```

Each char represents a different brightness level (1-10 from @ to the whitespace).

Given a quality ratio q, which varies from 0.5 to 0.9 in 0.1 increments, your job is to **output a compressed version of each ASCII file, while making those files able to decompress themselves.**

That is to say, ImageX.txt is compressed by Program.py into CompImageX-xx.cpp (xx being the quality of the compressed image). Once CompImageX-xx.c is executed, a final decompressed image ImageX-xx.txt is created.

The .py and .c extensions are just an example, you can write the compressor and compressed images in any language that you want (doesn't have to be the same language for both, but you can't use different languages for different images).

The quality changes the image output in a relatively simple way. We'll call the array of usable chars Arr. Each char of ImageX becomes Arr\[RoundHalfDown((Arr.Index(char)\*q))\], with the exception of the whitespace which remains the same no matter the quality.

```
RoundHalfDown(0.6) = RoundHalfDown(0.7) = RoundHalfDown(1) = 1

RoundHalfDown(0.5) = RoundHalfDown(0.4) = RoundHalfDown(0) = 0

```

For a short example:

```
 '#;@

```

at q=0.5 would become

```
 #@+@`

```

You have to implement your own compressor, can't use any libraries that handle it for you.

You can view the images here and download them from here.

**Your score is the square root of the size of your compressor, multiplied by the sum of the size of all the compressed files --\> sqrt(c)\*sum(f). Lowest score wins.**

```
USER                    LANGUAGE                    SCORE
Dennis                  CJam                        1046877

```

# Answer
# CJam → CJam, score 1046877.4413

I'm not going to participate in my own challenge, but since this one doesn't contain its core part (figuring out the optimal transformation to make the original image more compressible), here I go:

```
q"@#+';:,.` ":P9,easdf*.4f+:iPf=S+er_N/z,:L;N-__&W%:Pf#2f+e`{(2b1>}%
e_P,2+b256b:c`P`":P,2+\256b\b{_2,#)_(@a?)+}%{(2-a\2b)*}%e_Pf="L"/N*"

```

The linefeed is for "readability" only.

It should be possible to improve the score by improving or simplifying the compression.

### Summary

```
e# Read the input and modify the palette according to the quality.

q"@#+';:,.` ":P9,easdf*.4f+:iPf=S+er

e# Compute the line length and the unique characters of the palette.

_N/z,:L;N-__&W%:P

e# Replace each character by its index in the palette, plus two.

f#2f+

e# Perform run-length ecnoding, saving the runs using bijective base-2 numeration.
e# All related code has been adapted from this answer:
e# http://codegolf.stackexchange.com/a/53065

e`{(2b1>}%

e# Convert from base length(palette)+2 to byte array (string).

e_P,2+b256b:c`

e# Push the palette and the code for the decoder.

P`":P,2+\256b\b{_2,#)_(@a?)+}%{(2-a\2b)*}%e_Pf="L"/N*"

```

### Score

```
$ LANG=en_US
$ for i in {1..5}; do for q in 0.{5..9}; do
> cjam comp.cjam $q < image$i.txt > image-$i-$q.cjam
> done; done
$ wc -c comp.cjam
136 comp.cjam
$ wc -c image*.cjam
 2131 image-1-0.5.cjam
 2248 image-1-0.6.cjam
 2346 image-1-0.7.cjam
 2350 image-1-0.8.cjam
 2446 image-1-0.9.cjam
 3006 image-2-0.5.cjam
 3718 image-2-0.6.cjam
 3894 image-2-0.7.cjam
 3356 image-2-0.8.cjam
 4064 image-2-0.9.cjam
 2949 image-3-0.5.cjam
 2947 image-3-0.6.cjam
 3582 image-3-0.7.cjam
 3784 image-3-0.8.cjam
 3745 image-3-0.9.cjam
 2879 image-4-0.5.cjam
 2887 image-4-0.6.cjam
 3379 image-4-0.7.cjam
 3615 image-4-0.8.cjam
 3537 image-4-0.9.cjam
 4427 image-5-0.5.cjam
 4802 image-5-0.6.cjam
 5536 image-5-0.7.cjam
 6030 image-5-0.8.cjam
 6111 image-5-0.9.cjam
89769 total

```
> 2 votes

---
Tags: code-golf, ascii-art, compression
---


title: Backwards Long Addition

text:
# Question
Title: Backwards Long Addition
The standard long addition method:

> The standard algorithm for adding multidigit numbers is to align the addends vertically and add the columns, starting from the ones column on the right. If a column exceeds ten, the extra digit is "carried" into the next column. (wikipedia)

A long addition example:

```
 145
+ 98
-----
 243

```

Backwards long addition is similar but you start adding from the leftmost column and carry to the next column (on it's right). If the last (ones) column produces a carry you write it behind the current sum in the next column. If there is no carry in the last column no extra column is needed.

```
 145
+ 98
-----
 1341

```

Explanation for the above example by columns, left to right: `1 = 1; 4+9 = 10(carried) + 3; 5+8+1(carry) = 10(carried) + 4; 1(carry) = 1`

You should write a program or function which receives two positive integers as input and returns their sum using backwards long addition.

## Input

* Two positive integers.

## Output

* An integer, the sum of the two input numbers using backwards long addition.
* There should be no leading zeros. (Consider `5+5=1` or `73+33=7`.)

## Examples

Format is `Input => Output`.

```
1 3 => 4
5 5 => 1
8 9 => 71
22 58 => 701
73 33 => 7
145 98 => 1341
999 1 => 9901
5729 7812 => 26411

```

# Answer
> 8 votes
# Pyth, 16 bytes

Still new to Pyth, but this looks promising..

```
s_`smvs.[_d0lzcz

```

The idea here is simple. To do backwards addition, you need backwards numbers. We take the input, reverse it, make sure that it has same number of digits be adding trailing 0, sum the two numbers, reverse it again and make sure no leading zero exists.

**Code expansion**

```
              cz          # Take the input and Python split it. Splits on space automatically
    m                     # Now we map over these two strings
         _d               # Reverse the string
       .[  0lz            # Pad it with 0 on right so that its length is same as input length
     vs                   # We have array of character and number, stringify and eval
   s                      # Sum the numbers in array
  `                       # Stringify
 _                        # Reverse
s                         # Convert back to number, removing leading 0

```

Try it online here

# Answer
> 3 votes
# CJam, 22 bytes

```
q:QS/{W%Q,0e]s~}/+sW%~

```

This is pretty much the same algorithm as the Pyth answer, just a bit longer due to different syntax.

**Code expansion**

```
q:Q                     e# Read the input and store it in Q
   S/                   e# Split the input on space.
     {         }/       e# Now we map over the two values in the array
      W%                e# Reverse the number treating it like a string
        Q,0e]           e# Right pad it with enough 0 to make its length same as input
             s~         e# Convert to string and evaluate to get integer
                 +s     e# Sum the two numbers and convert the sum to string
                   W%~  e# Reverse the sum as a string and evaluate to remove leading 0

```

Try it online here

# Answer
> 3 votes
# Python 2, ~~80~~ 78 Bytes

I didn't intend to have to reverse at the end, but apparently I need to.. I will fix this (maybe)!

*Thanks to Alex A. for saving 2 bytes, and flornquake for saving 3 bytes!*

```
a,b=input();s=0
while a+b:s=s*10+a%10+b%10;a/=10;b/=10
print int(str(s)[::-1])

```

Input like so: `num1, num2`.

# Answer
> 3 votes
# CJam, 26 bytes

This is the first time I'm using CJam, I don't know many operators yet so it's surely sub-optimal. Gotta start somewhere :)

```
l~]$~s_,@s\0e[sW%i\W%i+sW%

```

Try it online.

Ungolfed:

```
l~    e# Takes input
]$~   e# Wrap in array, sort and unwrap
s_,   e# Convert highest to string, push length
@s\   e# Setup stack for padding (["hi" "lo" len])
0e[s  e# Left pad with zeroes and convert to string
W%i\  e# Reverse digits, convert to int, swap stack
W%i+  e# Reverse digits, convert to int, sum
sW%   e# Convert result to string and reverse digits
      e# Stack is automatically printed

```

# Answer
> 2 votes
# Bash + coreutils, 62

Not sure if this counts or not, but it does give the right answers (for 32-bit integers):

```
r()(printf %09d#01 $1|rev)
rev<<<$[`r $1`+`r $2`]|sed s/^0\*//

```

### Test output:

```
$ for t in "1 3" "5 5" "8 9" "22 58" "73 33" "145 98" "999 1" "5729 7812"
do ./backlongadd.sh $t; done
4
1
71
701
7
1341
9901
26411
$

```

# Answer
> 1 votes
# Java, ~~337~~ 312 bytes

Not quite a golfed language or solution, but it at least works and was fun to write. There's quite a few byte penalties to this approach, but I'm mostly happy with it.

```
void g(int a,int b){String p=(a>b?a:b)+"",o=(a>b?b:a)+"",s="";int m=p.length(),i=0,c=0,t;for(;i++<m;)o=(o.length()==m?"":"0")+o;for(i=-1;i++<m-1;){t=Integer.parseInt(p.charAt(i)+"")+Integer.parseInt(o.charAt(i)+"")+c;c=0;if(t>9){c=1;t=Integer.parseInt((t+"").charAt(1)+"");}s+=t;}System.out.print(s+(c>0?c:""));}

```

Input/Output:

```
g(8,9)    --> 71
g(145,98) --> 1341
g(999,1)  --> 9901

```

Spaced and tabbed out:

```
void g(int a,int b){

    String p=(a>b?a:b)+"",
      o=(a>b?b:a)+"",
      s="";

    int m=p.length(),
      i=0,
      c=0,
      t;

    for(;i++<m;)
      o=(o.length()==m?"":"0")+o;

    for(i=-1;i++<m-1;){
      t=Integer.parseInt(p.charAt(i)+"")+Integer.parseInt(o.charAt(i)+"")+c;
      c=0;
      if(t>9){
        c=1;
        t=Integer.parseInt((t+"").charAt(1)+"");
      }
      s+=t;
    }
    System.out.print(s+(c>0?c:""));
  }

```

# Answer
> 1 votes
# , 22 bytes

```
ii`\`e@e@\-{0+}d#\#+`o
```

Padding zeros, can be golfed a lot.

# Answer
> 0 votes
# Julia, ~~190~~ ~~173~~ ~~163~~ 160 bytes

```
f(a,b)=(n=ndigits;d=digits;m=max(n(a),n(b));C=reverse([0,d(a,10,m).+d(b,10,m)]);for i=1:m C[i+1]+=C[i]÷10;C[i]=C[i]%10end;c=join(C);int(c[end]=='0'?chop(c):c))

```

This creates a function `f` that accepts two integers and returns an integer.

Ungolfed + explanation:

```
function f(a,b)
    # Determine the maximum number of digits between a and b
    m = max(ndigits(a), ndigits(b))

    # Create an array as the elementwise sum of the digits of
    # a and b with a single trailing 0, where the digit arrays
    # are left padded with zeros to each have length m
    C = reverse([0, digits(a, 10, m) .+ digits(b, 10, m)])

    # Carry digits as necessary
    for i = 1:m
        C[i+1] += C[i] ÷ 10
        C[i] = C[i] % 10
    end

    # Join the array into a string
    c = join(C)

    # If the string has a trailing zero, lop it off, then
    # convert the string to an integer and return it
    int(c[end] == '0' ? chop(c) : c)
end

```

# Answer
> 0 votes
## JavaScript (ES6), 112 bytes

```
g=(a,b,r=z=>+[...z].reverse().join``,x=(a<b?a:b)+'')=>r(r(y=(a<b?b:a)+'')+r('0'.repeat(y.length-x.length)+x)+'')

```

### Algorithm

1. Determine the smaller number (`x`)
2. Pads `x` with leading zeroes up to the length of the bigger number `y`
3. Reverse both strings, cast to integer, add them together and convert it back to a string
4. Reverse that string and cast to integer to get rid of leading zeroes

### Demo

As with all ES6 code, it only works in Firefox at time of writing:

```
g=(a,b,r=z=>+[...z].reverse().join``,x=(a<b?a:b)+'')=>r(r(y=(a<b?b:a)+'')+r('0'.repeat(y.length-x.length)+x)+'')

// For demonstration purposes
console.log = x => X.innerHTML += x + '\n';

console.log(g(1,3));
console.log(g(5,5))
console.log(g(8,9))
console.log(g(22,58))
console.log(g(73,33))
console.log(g(145,98))
console.log(g(999,1))
console.log(g(5729,7812))
```

```
<pre><output id=X></output></pre>
```

# Answer
> 0 votes
## PHP, 112 bytes

Same algorithm as my JavaScript answer. It's sad that PHP has the same amount of chars (unless my other answer can be golfed further). Then again, the built-in string functions and implicit conversions really helped.

```
function g($a,$b,$r='strrev'){echo$r($r($y=max($a,$b))+$r(str_pad($x=min($a,$b),strlen($y)-strlen($x),0,0)))+0;}

```

Unminified:

```
function g($a, $b) {
    $y = max($a,$b);
    $x = min($a,$b);
    echo strrev(strrev($y) + strrev(str_pad($x, strlen($y) - strlen($x), 0, STR_PAD_LEFT))) + 0;
}

```

# Answer
> 0 votes
## Python 3, 92 bytes

For what it's worth (if anything), this function accepts an *arbitrary* number of inputs and adds them all.

```
r=lambda *a:int(str(sum(map(int,(format(n,'0>'+str(len(str(max(a)))))[::-1]for
n in a))))[::-1])

```

Ungolfed version:

```
def rsum(*summands):
    l = len(str(max(summands)))
    fmt = '0>' + str(l)
    reverse_summands = (format(n, fmt)[::-1] for n in summands)
    reverse_sum = sum(int(nrev) for nrev in reverse_summands)
    return int(str(reverse_sum)[::-1])

```

It's the same approach as Digital Trauma's answer: pad the shorter number with leading zeroes, reverse them, add them, and reverse the sum. The bulk of the code is int-to-string-to-int-to... conversion.

# Answer
> 0 votes
# Pyth, 17 bytes

```
s_`isM.TmsMdc_z)T

```

An alternative method without 0 padding.

---
Tags: code-golf, arithmetic
---


title: Conversion to Boolean satisfiability

text:
# Question
Title: Conversion to Boolean satisfiability
Given a matrix M all of whose entries are 0 or 1, we want to known whether there exists a non-zero vector **v** with each element in {-1, 0, 1}, such that M**v** = **0**.

An easy way to do this is just to try all possible vectors v. The M is m by n then there are 3n \- 1 such vectors. But of course this is PPCG, so we don't want to do anything so simple!

Instead, this task is to convert the problem into an instance of Boolean satisfiability problem.

**Input**

An m by n matrix M written out with one row per line each space separated. The first list has m and n on it, space separated. For example this 3 by 4 matrix M.

```
3 4
1 1 0 1
0 1 1 0
0 0 1 1

```

In this case there **does not** exist a non-zero vector v, all of whose entries are -1,0 or 1 such that Mv = 0.

**Output**

An instance of 3-SAT in simplified DIMACS format.

The instance of 3-SAT that you output should be satisfiable if and only if there exists a non-zero vector v, all of whose entries are -1,0 or 1 such that Mv = 0.

The file format will be in a simplified version of the DIMACS format using this specification taken from http://www.satcompetition.org/2009/format-benchmarks2009.html

---

```
c
c start with comments
c
c
p cnf 5 3
1 -5 4 0
-1 5 3 4 0
-3 -4 0

```

The file can start with comments, that is lines begining with the character c. Right after the comments, there is the line p cnf nbvar nbclauses indicating that the instance is in CNF format; nbvar is the exact number of variables appearing in the file; nbclauses is the exact number of clauses contained in the file. Then the clauses follow. Each clause is a sequence of distinct non-null numbers between -nbvar and nbvar ending with 0 on the same line; it cannot contain the opposite literals i and -i simultaneously. Positive numbers denote the corresponding variables. Negative numbers denote the negations of the corresponding variables.

---

**Score**

I will test your code on a 20 by 40 matrix and the score will be the total number of non-comment lines in your 3-SAT instance. Smaller is better.

**Running time of your code**

Your code should take less than 1 minute to run. I don't want to restrict the languages used but I will attempt to test any code I can run otherwise I will just trust the timing you give. For small instances you could of course just compute the answer but this won't work for matrices of the size I will test.

**More examples**

Your 3-SAT instances for the following matrices should be unsatisfiable.

```
1 1 0 1
0 1 1 0
0 0 1 1

1 1 0 1 0
0 1 1 0 1
0 0 1 1 0
0 0 0 1 1

1 0 0 1 0 1 1 0 0
1 1 0 0 1 0 1 1 0
0 1 1 0 0 1 0 1 1
0 0 1 1 0 0 1 0 1
0 0 0 1 1 0 0 1 0
0 0 0 0 1 1 0 0 1

1 1 0 1 0 0 1 1 1 0 0 1
1 1 1 0 1 0 0 1 1 1 0 0
0 1 1 1 0 1 0 0 1 1 1 0
0 0 1 1 1 0 1 0 0 1 1 1
0 0 0 1 1 1 0 1 0 0 1 1
0 0 0 0 1 1 1 0 1 0 0 1
0 0 0 0 0 1 1 1 0 1 0 0

```

Your 3-SAT instances for the following matrices should be satisfiable.

```
1 1 0 1 1 1 0
1 1 1 0 1 1 1
0 1 1 1 0 1 1
0 0 1 1 1 0 1
0 0 0 1 1 1 0

1 0 1 0 0 1 0 0 0
0 1 0 1 0 0 1 0 0
0 0 1 0 1 0 0 1 0
0 0 0 1 0 1 0 0 1
0 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 1 0

1 0 0 1 1 1 0 1 0 0 1 1
0 1 0 0 1 1 1 0 1 0 0 1
0 0 1 0 0 1 1 1 0 1 0 0
0 0 0 1 0 0 1 1 1 0 1 0
0 0 0 0 1 0 0 1 1 1 0 1
0 0 0 0 0 1 0 0 1 1 1 0
0 0 0 0 0 0 1 0 0 1 1 1

```

---

**A possible short cut for the busy programmer**

One possibly easier route to tacking this problem could be to output Pseudo-Boolean Constraints. See page 6 of http://www.cril.univ-artois.fr/PB12/format.pdf for example. There are then different open source tools and libraries which will convert that to 3-SAT.

# Answer
# OCaml, ≤ 475318

After defining the basic logic gates (I ended up using only AND and OR), I compose them to make a variable for each of the possible partial sums of a row of M and v. A total of *O(mn2)* variables/clauses are used. This is an initial effort that doesn't make any attempt to simplify the formula. In the worst case (a matrix with no zeroes), it generates 475,318 clauses for a 20x40 matrix.

```
let rec genlist f n =
    match n with
    | 0 -> []
    | n -> let e = f() in e :: genlist f (n-1)
;;

let numvars = ref 0 ;;
type var = V of int | Const of bool;;
let mkv () = incr numvars; V !numvars;;
type clause = Cl1 of var | Cl2 of var*var | Cl3 of var*var*var ;;
let clauses = ref [] ;;
let req (x:clause) = if x <> Cl1(Const true) then clauses := x :: !clauses ;;
let deref = (!);;
let (!) = function
    | V x -> V (-x)
    | Const c -> Const (not c)
;;

let mkeq (a:var) (b:var) = match a,b with
    | Const true, b -> b
    | Const false, b -> !b
    | a, Const true -> a
    | a, Const false -> !a
    | a,b -> let v = mkv() in
    req@@Cl3 ( !v, a, !b ) ;
    req@@Cl3 ( !v, !b, a ) ;
    req@@Cl3 ( v, a, b ) ;
    req@@Cl3 ( v, !a, !b );
    v
;;

let mkxor a b = ! (mkeq a b) ;;

let mkor (a:var) (b:var) = match a,b with
    | Const false, b -> b
    | Const true, _ -> Const true
    | _, Const true -> Const true
    | a, Const false -> a
    | a,b -> let v = mkv() in
    req@@Cl2 ( v, !a ) ;
    req@@Cl2 ( v, !b ) ;
    req@@Cl3 ( !v, a, b ) ;
    v
;;

let mkand a b = ! (mkor !a !b) ;;

let mkorl l =
    let rec mkorl_ = function
        | a::b::tl -> mkor (mkor a b) (mkorl_ tl)
        | a::[] -> a
        | [] -> Const false
    in mkorl_ (List.filter (function | Const false -> false | _ -> true) l)
;;
let nextsums sums (minus1, zero, plus1) =
    let rec nextsums_ prev sums (minus1, zero, plus1) =
    match sums with
        | cur::next::tl ->
            ( mkorl [mkand minus1 next; mkand zero cur; mkand plus1 prev] ) ::
            ( nextsums_ cur (next::tl) (minus1, zero, plus1) )
        | cur::_ ->
            (mkor (mkand zero cur) (mkand plus1 prev)) ::
            ( nextsums_ cur [] (minus1, zero, plus1) )
        | _ -> [mkand plus1 prev]
    in
    (mkand minus1 (List.hd sums)) ::
    nextsums_ (Const false) sums (minus1, zero, plus1)
;;

let rec entry_zero row v sums maxsum =
    if row=[] then List.nth sums maxsum else
    if List.hd row = 0 then entry_zero (List.tl row) (List.tl v) sums maxsum else
    let (a,b,c) = List.hd v in
    let elemv = if List.hd row = -1 then (c,b,a) else (a,b,c) in
    entry_zero (List.tl row) (List.tl v) (nextsums sums elemv) (maxsum+1)
;;

let req1of3 (a,b,c) =
    req@@Cl2(!a, !b);
    req@@Cl2(!a, !c);
    req@@Cl2(!b, !c);
    req@@Cl3(a, b, c);;

let rdint () = Scanf.bscanf Scanf.Scanning.stdin " %d" (fun x -> x) ;;

let m = rdint();;
let n = rdint();;

let vec = genlist (fun () -> (mkv(), mkv(), mkv()) ) n;;
List.iter req1of3 vec;;

let mat = genlist (fun () -> genlist rdint n) m;;

List.iter (fun row -> req@@Cl1 (entry_zero row vec [Const true] 0) ) mat;;

let nonzeros = List.map (function _,z,_ -> !z) vec ;;
req@@Cl1 (mkorl nonzeros) ;;

exception Bug of string;;
let str_clause (cl:clause) = match cl with
    | Cl1(V a) -> Printf.sprintf "%d 0" a
    | Cl2(V a,V b) -> Printf.sprintf "%d %d 0" a b
    | Cl3(V a,V b,V c) -> Printf.sprintf "%d %d %d 0" a b c
    | _ -> raise @@ Bug "there seems to be";;
let (!) = deref;;

Printf.printf "p cnf %d %d\n" !numvars (List.length !clauses) ;;
List.iter (fun cl -> print_endline (str_clause cl)) !clauses ;;

```
> 3 votes

# Answer
# Python, n/a

Not a full answer, but this turns matrices into PBS instances that can be transformed into 3-SAT instances by standard tools:

```
import fileinput

def pos_vec(i): return "x" + str(1 + 2*i)
def neg_vec(i): return "x" + str(1 + 2*i+1)

def print_pseudo(M):
    print(" ".join("1 x" + str(i) for i in range(1, len(M[0])*2 + 1)) + " > 0;")
    for v in range(len(M[0])):
        print("1 {} 1 {} < 2;".format(pos_vec(v), neg_vec(v)))

    for r in range(len(M)):
        terms = []
        for c in range(len(M[0])):
            if M[r][c]:
                terms.append("1 {}".format(pos_vec(c)))
                terms.append("-1 {}".format(neg_vec(c)))
        print(" ".join(terms) + " = 0;")

M = [[int(b) for b in line.split()] for line in fileinput.input()]
print_pseudo(M)

```
> 1 votes

---
Tags: code-challenge, math
---


title: Transit all day every day

text:
# Question
Title: Transit all day every day
In addition to contributing to Stack Overflow and other SE sites, I like to ride public transit during my free time. I'd be spending a fortune on cash fare and/or bus tickets every month if I didn't have a bus pass. But for the average passenger, how much would you need to ride to make it worthwhile to buy a pass?

## Input

Two parameters: Passenger age and transit usage report.

Standard loopholes apply. You can read input from CLI arguments, function arguments, or a file (whichever works best for your language).

### Transit usage log format

Each line represents a trip:

```
<date> <time> <route number> <start> à <destination>
<date> <time> <route number> <start> à <destination> // comments, if any

```

Date is in ISO 8601 format. Time is 24 hour format (hours and minutes, both with leading zeros). The remaining information on the line is irrelevant for this question.

### Fare structure

Tickets are $1.60 each.

```
            Child (0-5)    Child (6-12)  Student (13-19)   Adult (20+)
Cash           Free           1.90            3.55            3.55
Tickets        Free              1               2               2
DayPass        Free           8.30            8.30            8.30
Monthly pass   Free            n/A           82.25          103.25

```

### Transfers

When paying with cash or tickets, a transfer (proof of payment) will be provided. The validity of the transfer is calculated as follows:

* Until 04:30 the next day if time of boarding is after 22:00, else
* 105 minutes from time of boarding on weekends, else
* 90 minutes from time of boarding

If you have a valid transfer at the start of a trip, you do not have to pay anything.

For the purposes of this question, make the following assumptions:

* All routes cost the same
* You never lose your transfer or day pass
* You do **not** have a transfer from the last day of the previous month.

### Day pass

If more than $8.30 in cash is spent in a day, a day pass is cheaper.

A day pass is valid from 03:00 to 03:00 the next day. If a day pass is purchased at 02:30, it is only good for 30 minutes!

## Output

Output may be in the form of a return value or written to STDOUT. A trailing newline is permitted.

Your program/function must output the cost of each option as follows (order does not matter):

```
C: $50.45
T: $44.1
J: $47.25
P: $100.75

```

J represents the calculation for a combination of cash with day passes where a day pass would have been cheaper.

Numbers must be truncated to at most two decimal places. Trailing zeros can be omitted.

For passengers age 6 through 12, passes are unavailable so any non-digit output for `P` is OK (whether it be false, empty string, nil, null, not a number, "Infinity", etc.)

### Bonus

-5% if you indicate the least expensive valid option in the output by printing any printable character before method of payment. For example:

```
P: $NaN
C: $117.80
*T: $99.20
J: $117.80

```

## Test cases

### Input transit usage log

```
body {white-space: pre; font-family: monospace}
```

```
2015-04-01 02:28 95 Barrhaven Centre à Laurier
2015-04-01 06:31 98 Laurier à Tunney's Pasture
2015-04-01 06:51 176X Tunney's Pasture à Merivale/Rossdale
2015-04-01 08:06 176 Merivale/Family Brown à Laurier
2015-04-01 22:16 97 Campus à Lincoln Fields
2015-04-01 22:51 95 Lincoln Fields à Barrhaven Centre
2015-04-02 02:00 95 Barrhaven Centre à Laurier
2015-04-02 19:01 95 Campus à Barrhaven Centre
2015-04-02 22:31 170 Barrhaven Centre à Fallowfield
2015-04-02 23:22 95 Fallowfield à Trim
2015-04-02 00:41 95 Trim à Barrhaven Centre
2015-04-02 03:48 95 Barrhaven Centre à Laurier
2015-04-02 20:25 95X Laurier à Mackenzie King
2015-04-02 20:49 95 Mackenzie King à Barrhaven Centre
2015-04-02 23:58 95 Barrhaven Centre à Laurier
2015-04-04 21:26 96 Laurier à Lincoln Fields
2015-04-04 21:51 94 Lincoln Fields à Fallowfield
2015-04-04 22:10 95 Fallowfield à Barrhaven Centre
2015-04-04 22:38 95 Barrhaven Centre à Hurdman
2015-04-04 23:24 95 Hurdman à Mackenzie King
2015-04-05 00:03 1 Dalhousie/York à Johnston/Bank
2015-04-05 00:43 97 Greenboro à Lincoln Fields
2015-04-06 01:41 95 Lincoln Fields à Fallowfield
2015-04-06 02:11 95 Fallowfield à Barrhaven Centre
2015-04-06 05:21 95 Longfields à Laurier
2015-04-06 18:17 94 Laurier à Mackenzie King
2015-04-06 18:49 95 Mackenzie King à Barrhaven Centre
2015-04-06 23:18 95 Barrhaven Centre à Place d'Orléans
2015-04-06 00:41 95 Place d'Orléans à Barrhaven Centre
2015-04-06 02:01 95 Barrhaven Centre à Laurier
2015-04-06 19:15 94 Laurier à Mackenzie King
2015-04-06 19:49 95 Mackenzie King à Barrhaven Centre
2015-04-06 23:51 170 Strandherd à Fallowfield
2015-04-07 00:21 DH Fallowfield à Baseline
2015-04-07 00:39 95 Baseline à Laurier
2015-04-07 17:20 71 Mackenzie King à Berrigan/Edge
2015-04-07 23:18 95 Barrhaven Centre à Laurier
2015-04-09 00:40 95 Trim à Barrhaven Centre
2015-04-09 02:00 95 Barrhaven Centre à Laurier
2015-04-09 16:32 41 Campus à Hurdman
2015-04-09 16:37 94 Hurdman à St. Laurent
2015-04-09 17:41 95 St. Laurent à Campus
2015-04-10 01:06 95 Laurier à Barrhaven Centre
2015-04-10 02:01 95 Barrhaven Centre à Laurier
2015-04-10 17:15 66 Campus à Lincoln Fields
2015-04-10 17:44 95 Lincoln Fields à Barrhaven Centre
2015-04-10 23:38 95 Barrhaven Centre à Longfields
2015-04-11 00:05 95 Longfields à Laurier
2015-04-11 01:30 95 Laurier à Barrhaven Centre
2015-04-11 04:47 95 Barrhaven Centre à Fallowfield //stop engine
2015-04-11 05:17 95 Fallowfield à Laurier
2015-04-11 17:15 94 Laurier à Mackenzie King
2015-04-11 17:41 95 Mackenzie King à Barrhaven Centre
2015-04-11 23:30 170 Barrhaven Centre à Fallowfield
2015-04-12 00:21 95 Fallowfield à Laurier
2015-04-12 17:30 98 Laurier à Mackenzie King
2015-04-12 21:25 95 Laurier à Barrhaven Centre
2015-04-12 23:18 95 Barrhaven Centre à Laurier
2015-04-13 07:01 16 Laurier/Cumberland à Tunney's Pasture
2015-04-13 07:27 176X Tunney's Pasture à Merivale/Meadowlands
2015-04-13 09:12 176 Merivale/Baseline à LeBreton
2015-04-13 09:21 96 LeBreton à Blair
2015-04-14 00:34 95 Laurier à Barrhaven Centre
2015-04-14 02:30 95 Barrhaven Centre à Laurier
2015-04-14 07:06 86C Laurier à Tunney's Pasture
2015-04-14 07:21 176 Tunney's Pasture à Merivale/Meadowlands
2015-04-14 08:54 86 Meadowlands/Merivale à Laurier
2015-04-14 18:43 97X Laurier à Hurdman
2015-04-14 18:55 95 Hurdman à St. Laurent
2015-04-14 19:23 95 St. Laurent à Barrhaven Centre
2015-04-14 23:18 95 Barrhaven Centre à Trim
2015-04-15 00:38 95 Trim à Laurier
2015-04-15 08:00 35 Laurier à Mackenzie King
2015-04-15 08:35 94 Mackenzie King à Campus
2015-04-15 22:15 95 Laurier à Barrhaven Centre
2015-04-16 02:01 95 Barrhaven Centre à Laurier
2015-04-16 21:01 95 Laurier à Woodroffe/Tallwood
2015-04-16 21:34 86 Meadowlands/Woodroffe à Meadowlands/Merivale
2015-04-16 21:56 176 Merivale/Meadowlands à Barrhaven Centre
2015-04-17 02:00 95 Barrhaven Centre à Laurier
2015-04-17 11:52 96 Laurier à Bayshore
2015-04-17 13:21 96 Bayshore à Campus
2015-04-17 22:10 95X Campus à Baseline
2015-04-17 22:47 95 Baseline à Barrhaven Centre
2015-04-18 02:53 95 Barrhaven Centre à Laurier
2015-04-18 20:14 86X Laurier à Hurdman
2015-04-18 20:22 94 Hurdman à St. Laurent
2015-04-18 20:44 94 St. Laurent à Fallowfield
2015-04-18 21:43 95 Fallowfield à Barrhaven Centre
2015-04-19 00:58 95 Barrhaven Centre à Laurier
2015-04-19 15:16 95 Laurier à Mackenzie King
2015-04-19 16:22 94 Mackenzie King à Hurdman
2015-04-19 16:34 98 Hurdman à South Keys
2015-04-19 16:51 97 South Keys à Airport
2015-04-19 17:21 97 Airport à Laurier
2015-04-19 21:30 95 Laurier à Barrhaven Centre
2015-04-19 23:18 95 Barrhaven Centre à Laurier
2015-04-20 19:30 95 Laurier à Barrhaven Centre
2015-04-20 23:18 95 Barrhaven Centre à Trim
2015-04-21 00:38 95 Trim à Laurier
2015-04-21 19:30 95 Laurier à Barrhaven Centre
2015-04-22 02:00 95 Barrhaven Centre à Laurier
2015-04-22 19:30 95 Laurier à Barrhaven Centre
2015-04-23 01:28 95 Barrhaven Centre à Woodroffe/Medhurst
2015-04-23 02:11 95 Woodroffe/Medhurst à Laurier
2015-04-23 19:30 95 Laurier à Barrhaven Centre
2015-04-23 23:18 95 Barrhaven Centre à Trim
2015-04-24 00:38 95 Trim à Laurier
2015-04-24 23:15 95 Laurier à Barrhaven Centre
2015-04-25 00:23 95 Barrhaven Centre à Rideau St.
2015-04-25 01:44 96 Rideau St à Laurier
2015-04-25 16:58 86B Laurier à Albert/Bank
2015-04-25 17:44 87 Mackenzie King à Laurier
2015-04-26 01:25 95 Laurier à Barrhaven Centre
2015-04-27 01:04 95 Laurier à Rideau St
2015-04-27 01:31 95 Rideau St à Laurier
2015-04-27 17:25 41 Campus à Heron/Baycrest
2015-04-27 17:54 112 Baycrest/Heron à Elmvale
2015-04-27 18:30 114 Elmvale à Hurdman
2015-04-27 18:41 94 Hurdman à Laurier
2015-04-29 02:02 95 Barrhaven Centre à Laurier
2015-04-29 17:01 8 Campus à Heron
2015-04-29 17:37 118 Heron à Baseline
2015-04-29 18:01 95 Baseline à Barrhaven Centre
2015-04-29 20:32 95 Barrhaven Centre à Mackenzie King
2015-04-29 21:31 2 Rideau St à Bank/Queen
2015-04-29 21:35 95 Albert/Bank à Barrhaven Centre
2015-04-30 02:02 95 Barrhaven Centre à Laurier
2015-04-30 02:20 86C Campus à Mackenzie King
2015-04-30 02:44 96 Mackenzie King à Campus
2015-04-30 19:36 95 Laurier à Strandherd
```

### Output

```
$ node --harmony golfed.js trips.txt 5 "Toddler"
P: $0.00
C: $0.00
T: $0.00
J: $0.00
$ node --harmony golfed.js trips.txt 10 "Child"
P: $NaN
C: $117.80
T: $99.20
J: $117.80
$ node --harmony golfed.js trips.txt 15 "Student"
P: $82.25
C: $220.10
T: $198.40
J: $194.20
$ node --harmony golfed.js trips.txt 61 "Adult"
P: $103.25
C: $220.10
T: $198.40
J: $194.20

```

# Answer
> 2 votes
I'm going to kick off my own question by providing my own golfed solutions in two languages. These functions write to STDOUT.

## CoffeeScript, 438 bytes

```
F=(I,a)->f=[C=T=x=A=0,1.9,K=3.55,K,0,1,2,2];J=[];I.split('\n').map((r)->W=new Date w=r[..9];(y=+w[-2..]-((h=R.getUTCHours())<3);C+=f[A=a>19&&3||a>12&&2||a>5&&1||0];T+=f[A+4]*1.6;J[y]=J[y]||0;J[y]++;x=h>21&&+W+1026e5||h<3&&+W+162e5||+R+(R.getUTCDay()%6&&54e5||63e5))if x<R=new Date r=w+'T'+r[11..15]+':00');o={P:[0,NaN,Z=82.25,Z+21][A],C:C,T:T,J:J.reduce ((p,v)->v*f[A]>8.3&&p+8.3||p+v*f[A]),0};console.log(O+': $'+$.toFixed 2)for O,$ of o

```

## JavaScript (ES6), 445 bytes

```
F=(I,a)=>{f=[C=T=x=0,1.9,K=3.55,K,0,1,2,2],J=[];I.split('\n').map(r=>{W=new Date(w=r[s='slice'](0,10));if((R=new Date(r=w+'T'+r[s](11,16)+':00'))>x){y=+w[s](-2)-(V=(h=R.getUTCHours())<3);C+=f[A=a>19?3:a>12?2:a>5?1:0];T+=f[A+4]*1.6;J[y]=J[y]||0;J[y]++;x=h>21?+W+1026e5:V?+W+162e5:+R+(R.getUTCDay()%6?54e5:63e5)}});for($ in(o={P:[0,NaN,Z=82.25,Z+21][A],C:C,T:T,J:J.reduce((p,v)=>v*f[A]>8.3?p+8.3:p+v*f[A],0)}))console.log($+': $'+o[$].toFixed(2))}

```

## JavaScript (ES5), 474 bytes

There really wasn't much ES6 other than arrow functions.

```
F=function(I,a){f=[C=T=x=0,1.9,K=3.55,K,0,1,2,2],J=[];I.split('\n').map(function(r){W=new Date(w=r[s='slice'](0,10));if((R=new Date(r=w+'T'+r[s](11,16)+':00'))>x){y=+w[s](-2)-(V=(h=R.getUTCHours())<3);C+=f[A=a>19?3:a>12?2:a>5?1:0];T+=f[A+4]*1.6;J[y]=J[y]||0;J[y]++;x=h>21?+W+1026e5:V?+W+162e5:+R+(R.getUTCDay()%6?54e5:63e5)}});for($ in(o={P:[0,NaN,Z=82.25,Z+21][A],C:C,T:T,J:J.reduce(function(p,v){return v*f[A]>8.3?p+8.3:p+v*f[A]},0)}))console.log($+': $'+o[$].toFixed(2))}

```

### Demo

```
F = function(I, a) {
  f = [C = T = x = 0, 1.9, K = 3.55, K, 0, 1, 2, 2], J = [];
  I.split('\n').map(function(r) {
    W = new Date(w = r[s = 'slice'](0, 10));
    if ((R = new Date(r = w + 'T' + r[s](11, 16) + ':00')) > x) {
      y = +w[s](-2) - (V = (h = R.getUTCHours()) < 3);
      C += f[A = a > 19 ? 3 : a > 12 ? 2 : a > 5 ? 1 : 0];
      T += f[A + 4] * 1.6;
      J[y] = J[y] || 0;
      J[y] ++;
      x = h > 21 ? +W + 1026e5 : V ? +W + 162e5 : +R + (R.getUTCDay() % 6 ? 54e5 : 63e5)
    }
  });
  for ($ in (o = {
    P: [0, NaN, Z = 82.25, Z + 21][A],
    C: C,
    T: T,
    J: J.reduce(function(p, v) {
      return v * f[A] > 8.3 ? p + 8.3 : p + v * f[A]
    }, 0)
  })) console.log($ + ': $' + o[$].toFixed(2))
}

// Demonstration stuff
console.log = function(x) {
  O.innerHTML += x + '\n'
}

F(D.innerHTML, 5);
console.log('<hr>Child');
F(D.innerHTML, 10);
console.log('<hr>Student');
F(D.innerHTML, 15);
console.log('<hr>Adult');
F(D.innerHTML, 20);
```

```
<div id=D hidden style=display:none>
2015-04-01 02:28 95 Barrhaven Centre à Laurier
2015-04-01 06:31 98 Laurier à Tunney's Pasture
2015-04-01 06:51 176X Tunney's Pasture à Merivale/Rossdale
2015-04-01 08:06 176 Merivale/Family Brown à Laurier
2015-04-01 22:16 97 Campus à Lincoln Fields
2015-04-01 22:51 95 Lincoln Fields à Barrhaven Centre
2015-04-02 02:00 95 Barrhaven Centre à Laurier
2015-04-02 19:01 95 Campus à Barrhaven Centre
2015-04-02 22:31 170 Barrhaven Centre à Fallowfield
2015-04-02 23:22 95 Fallowfield à Trim
2015-04-02 00:41 95 Trim à Barrhaven Centre
2015-04-02 03:48 95 Barrhaven Centre à Laurier
2015-04-02 20:25 95X Laurier à Mackenzie King
2015-04-02 20:49 95 Mackenzie King à Barrhaven Centre
2015-04-02 23:58 95 Barrhaven Centre à Laurier
2015-04-04 21:26 96 Laurier à Lincoln Fields
2015-04-04 21:51 94 Lincoln Fields à Fallowfield
2015-04-04 22:10 95 Fallowfield à Barrhaven Centre
2015-04-04 22:38 95 Barrhaven Centre à Hurdman
2015-04-04 23:24 95 Hurdman à Mackenzie King
2015-04-05 00:03 1 Dalhousie/York à Johnston/Bank
2015-04-05 00:43 97 Greenboro à Lincoln Fields
2015-04-06 01:41 95 Lincoln Fields à Fallowfield
2015-04-06 02:11 95 Fallowfield à Barrhaven Centre
2015-04-06 05:21 95 Longfields à Laurier
2015-04-06 18:17 94 Laurier à Mackenzie King
2015-04-06 18:49 95 Mackenzie King à Barrhaven Centre
2015-04-06 23:18 95 Barrhaven Centre à Place d'Orléans
2015-04-06 00:41 95 Place d'Orléans à Barrhaven Centre
2015-04-06 02:01 95 Barrhaven Centre à Laurier
2015-04-06 19:15 94 Laurier à Mackenzie King
2015-04-06 19:49 95 Mackenzie King à Barrhaven Centre
2015-04-06 23:51 170 Strandherd à Fallowfield
2015-04-07 00:21 DH Fallowfield à Baseline
2015-04-07 00:39 95 Baseline à Laurier
2015-04-07 17:20 71 Mackenzie King à Berrigan/Edge
2015-04-07 23:18 95 Barrhaven Centre à Laurier
2015-04-09 00:40 95 Trim à Barrhaven Centre
2015-04-09 02:00 95 Barrhaven Centre à Laurier
2015-04-09 16:32 41 Campus à Hurdman
2015-04-09 16:37 94 Hurdman à St. Laurent
2015-04-09 17:41 95 St. Laurent à Campus
2015-04-10 01:06 95 Laurier à Barrhaven Centre
2015-04-10 02:01 95 Barrhaven Centre à Laurier
2015-04-10 17:15 66 Campus à Lincoln Fields
2015-04-10 17:44 95 Lincoln Fields à Barrhaven Centre
2015-04-10 23:38 95 Barrhaven Centre à Longfields
2015-04-11 00:05 95 Longfields à Laurier
2015-04-11 01:30 95 Laurier à Barrhaven Centre
2015-04-11 04:47 95 Barrhaven Centre à Fallowfield //stop engine
2015-04-11 05:17 95 Fallowfield à Laurier
2015-04-11 17:15 94 Laurier à Mackenzie King
2015-04-11 17:41 95 Mackenzie King à Barrhaven Centre
2015-04-11 23:30 170 Barrhaven Centre à Fallowfield
2015-04-12 00:21 95 Fallowfield à Laurier
2015-04-12 17:30 98 Laurier à Mackenzie King
2015-04-12 21:25 95 Laurier à Barrhaven Centre
2015-04-12 23:18 95 Barrhaven Centre à Laurier
2015-04-13 07:01 16 Laurier/Cumberland à Tunney's Pasture
2015-04-13 07:27 176X Tunney's Pasture à Merivale/Meadowlands
2015-04-13 09:12 176 Merivale/Baseline à LeBreton
2015-04-13 09:21 96 LeBreton à Blair
2015-04-14 00:34 95 Laurier à Barrhaven Centre
2015-04-14 02:30 95 Barrhaven Centre à Laurier
2015-04-14 07:06 86C Laurier à Tunney's Pasture
2015-04-14 07:21 176 Tunney's Pasture à Merivale/Meadowlands
2015-04-14 08:54 86 Meadowlands/Merivale à Laurier
2015-04-14 18:43 97X Laurier à Hurdman
2015-04-14 18:55 95 Hurdman à St. Laurent
2015-04-14 19:23 95 St. Laurent à Barrhaven Centre
2015-04-14 23:18 95 Barrhaven Centre à Trim
2015-04-15 00:38 95 Trim à Laurier
2015-04-15 08:00 35 Laurier à Mackenzie King
2015-04-15 08:35 94 Mackenzie King à Campus
2015-04-15 22:15 95 Laurier à Barrhaven Centre
2015-04-16 02:01 95 Barrhaven Centre à Laurier
2015-04-16 21:01 95 Laurier à Woodroffe/Tallwood
2015-04-16 21:34 86 Meadowlands/Woodroffe à Meadowlands/Merivale
2015-04-16 21:56 176 Merivale/Meadowlands à Barrhaven Centre
2015-04-17 02:00 95 Barrhaven Centre à Laurier
2015-04-17 11:52 96 Laurier à Bayshore
2015-04-17 13:21 96 Bayshore à Campus
2015-04-17 22:10 95X Campus à Baseline
2015-04-17 22:47 95 Baseline à Barrhaven Centre
2015-04-18 02:53 95 Barrhaven Centre à Laurier
2015-04-18 20:14 86X Laurier à Hurdman
2015-04-18 20:22 94 Hurdman à St. Laurent
2015-04-18 20:44 94 St. Laurent à Fallowfield
2015-04-18 21:43 95 Fallowfield à Barrhaven Centre
2015-04-19 00:58 95 Barrhaven Centre à Laurier
2015-04-19 15:16 95 Laurier à Mackenzie King
2015-04-19 16:22 94 Mackenzie King à Hurdman
2015-04-19 16:34 98 Hurdman à South Keys
2015-04-19 16:51 97 South Keys à Airport
2015-04-19 17:21 97 Airport à Laurier
2015-04-19 21:30 95 Laurier à Barrhaven Centre
2015-04-19 23:18 95 Barrhaven Centre à Laurier
2015-04-20 19:30 95 Laurier à Barrhaven Centre
2015-04-20 23:18 95 Barrhaven Centre à Trim
2015-04-21 00:38 95 Trim à Laurier
2015-04-21 19:30 95 Laurier à Barrhaven Centre
2015-04-22 02:00 95 Barrhaven Centre à Laurier
2015-04-22 19:30 95 Laurier à Barrhaven Centre
2015-04-23 01:28 95 Barrhaven Centre à Woodroffe/Medhurst
2015-04-23 02:11 95 Woodroffe/Medhurst à Laurier
2015-04-23 19:30 95 Laurier à Barrhaven Centre
2015-04-23 23:18 95 Barrhaven Centre à Trim
2015-04-24 00:38 95 Trim à Laurier
2015-04-24 23:15 95 Laurier à Barrhaven Centre
2015-04-25 00:23 95 Barrhaven Centre à Rideau St.
2015-04-25 01:44 96 Rideau St à Laurier
2015-04-25 16:58 86B Laurier à Albert/Bank
2015-04-25 17:44 87 Mackenzie King à Laurier
2015-04-26 01:25 95 Laurier à Barrhaven Centre
2015-04-27 01:04 95 Laurier à Rideau St
2015-04-27 01:31 95 Rideau St à Laurier
2015-04-27 17:25 41 Campus à Heron/Baycrest
2015-04-27 17:54 112 Baycrest/Heron à Elmvale
2015-04-27 18:30 114 Elmvale à Hurdman
2015-04-27 18:41 94 Hurdman à Laurier
2015-04-29 02:02 95 Barrhaven Centre à Laurier
2015-04-29 17:01 8 Campus à Heron
2015-04-29 17:37 118 Heron à Baseline
2015-04-29 18:01 95 Baseline à Barrhaven Centre
2015-04-29 20:32 95 Barrhaven Centre à Mackenzie King
2015-04-29 21:31 2 Rideau St à Bank/Queen
2015-04-29 21:35 95 Albert/Bank à Barrhaven Centre
2015-04-30 02:02 95 Barrhaven Centre à Laurier
2015-04-30 02:20 86C Campus à Mackenzie King
2015-04-30 02:44 96 Mackenzie King à Campus
2015-04-30 19:36 95 Laurier à Strandherd
</div>

<pre id=O></pre>
```

---
Tags: code-golf, date
---


title: Creating Distinct Sums

text:
# Question
Title: Creating Distinct Sums
You should write a program or function which receives an integers as input and outputs or returns two integers whose sum is the first one.

There is one further requirement: **no number can be part of the output for two different inputs**.

## Details

* You should be able to handle inputs for at least the range `-32768 .. 32767` (inclusive).
* If your datatype can't handle arbitrary whole numbers, that is fine but your algorithm should work for arbitrary large and small numbers in theory.

## Examples

Each block shows a part of a correct or incorrect solution in the format of `input => output`.

```
1 => 6 -5
2 => -2 4
15 => 20 -5

Incorrect, as `-5` is used in two outputs.

```

```
-5 => -15 10
0 => 0 0
1 => 5 6
2 => -5 7

Incorrect, as `5 + 6` isn't `1`.

```

```
-1 => -1 0
0 => 6 -6
2 => 1 1

Can be correct if other outputs doesn't collide.

```

This is code golf so the shortest entry wins.

# Answer
> 9 votes
# Pyth, 8 bytes

```
_J^Q3+QJ

```

Demonstration. Equivalent to the Python 2 code:

```
Q=input()
J=Q**3
print -J
print Q+J

```

So, the output has form `(-n**3, n+n**3)`

Some outputs:

```
-5 (125, -130)
-4 (64, -68)
-3 (27, -30)
-2 (8, -10)
-1 (1, -2)
 0 (0, 0)
 1 (-1, 2)
 2 (-8, 10)
 3 (-27, 30)
 4 (-64, 68)
 5 (-125, 130)

```

These are distinct because cubes are far enough spaced that adding `n` to `n**3` is not enough to cross the gap to the next cube :`n**3 < n+n**3 < (n+1)**3` for positive `n`, and symmetrically for negative `n`.

# Answer
> 8 votes
# Snowman 0.1.0, 101 chars

```
}vg0aa@@*45,eQ.:?}0AaG0`NdE`;:?}1;bI%10sB%nM2np`*`%.*#NaBna!*+#@~%@0nG\]:.;:;bI~0-NdEnMtSsP" "sP.tSsP

```

Input on STDIN, space-separated output on STDOUT.

This uses the same method as isaacg's answer.

Commented version with newlines, for "readability":

```
}vg0aa          // get input, take the first char
@@*45,eQ.       // check if it's a 45 (ASCII for -) (we also discard the 0 here)
// this is an if-else
:               // (if)
  ?}0AaG        // remove first char of input (the negative sign)
  0`NdE`        // store a -1 in variable e, set active vars to beg
;
:               // (else)
  ?}1           // store a 1 in variable e, set active vars to beg
;bI             // active variables are now guaranteed to be beg
%10sB           // parse input as number (from-base with base 10)
%nM             // multiply by either 1 or -1, as stored in var e earlier
2np`*`          // raise to the power of 2 (and discard the 2)
%.              // now we have the original number in b, its square in d, and
                //   active vars are bdg
*#NaBna!*+#     // add abs(input number) to the square (without modifying the
                //   input variable, by juggling around permavars)
@~%@0nG\]       // active vars are now abcfh, and we have (0>n) in c (where n is
                //   the input number)
:.;:;bI         // if n is negative, swap d (n^2) and g (n^2+n)
~0-NdEnM        // multiply d by -1 (d is n^2 if n is positive, n^2+n otherwise)
tSsP            // print d
" "sP           // print a space
.tSsP           // print g

```

Commentary on the very first Snowman solution on PPCG: I think my design goal of making my language as confusing as possible has been achieved.

This actually could have been a lot shorter, but I'm an idiot and forgot to implement negative numbers for string -\> number parsing. So I had to manually check whether there was a `-` as the first character and remove it if so.

# Answer
> 6 votes
# Pyth, ~~15~~ 11 bytes

*4 bytes thanks to @Jakube*

```
*RQ,hJ.aQ_J

```

Demonstration.

This maps as follows:

```
0  -> 0, 0
1  -> 2, -1
-1 -> -2, 1
2  -> 6, -4
-2 -> -6, 4

```

And so, on, always involving `n^2` and `n^2 + n`, plus or minus.

# Answer
> 5 votes
# APL, 15 bytes

```
{(-⍵*3)(⍵+⍵*3)}

```

This creates an unnamed monadic function that returns the pair -n^3 (`-⍵*3`), n+n^3 (`⍵+⍵*3`).

You can try it online.

# Answer
> 2 votes
# , ~~17 15~~ 9 bytes

Uses some new features of O.

```
Q3^.Q+p_p
```

**Older Version**

```
[i#.Z3^*\Z3^)_*]o
```

# Answer
> 2 votes
# Pyth - 11 10 bytes

Just multiplies by 10e10 and -10e10+1 Thanks to @xnor for showing me that I could use `CG` for the number.

```
*CGQ_*tCGQ

```

Try it online here.

# Answer
> 1 votes
# Python 3, ~~29~~ 27

## Edit: doesn't meet the requirement in the 2nd "Details" bullet point

*Bonus: it works from -99998 to 99998 inclusive*

---

```
lambda n:[99999*n,-99998*n]

```

This creates an anonymous function\*, which you can use by enclosing in brackets and then placing the argument in brackets afterwards like this:

```
(lambda n:[99999*n,-99998*n])(arg)

```

\*Thanks to @vioz- for suggesting this.

---

Example input / output:

```
>>> (lambda n:[99999*n,-99998*n])(1)
[99999, -99998]
>>> (lambda n:[99999*n,-99998*n])(2)
[199998, -199996]
>>> (lambda n:[99999*n,-99998*n])(0)
[0, 0]
>>> (lambda n:[99999*n,-99998*n])(-1)
[-99999, 99998]
>>> (lambda n:[99999*n,-99998*n])(-2)
[-199998, 199996]
>>> (lambda n:[99999*n,-99998*n])(65536)
[6553534464, -6553468928]

```

# Answer
> 0 votes
# Haskell, 16 bytes

I shamelessly copied @xnor's method. There probably isn't much better than this.

```
f x=(-x^3,x^3+x)

```

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


title: Modular Fibonacci Cycles

text:
# Question
Title: Modular Fibonacci Cycles
The Fibonacci sequence is a well known and famous sequence, where each successive element is the sum of the previous two. A modular Fibonacci sequence is the same, except that the addition is performed over a finite field, or to put it another way, a modulo operation is performed after each addition.

For instance, the modular Fibonacci sequence with starting values `1, 1` and modulus `5` is:

```
1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, ...

```

At this point, the sequence is once again `1, 1`, and so the sequence will repeat, cyclically, with a cycle length of 20.

Your challenge is to find the (minimal) cycle length for a specific starting pair and modulus, in the fewest bytes.

**Details:** The initial values will both be in the range `0 <= i,j < m`, where `m` is the modulus. The initial values will not both be zero, and the modulus will be at least 2. You may take the input in any standard means or format, in any order, function, program or similar, and output via return or print. Standard loopholes apply.

**Examples:**

```
First element, second element, modulus:

1, 1, 5 => 20
1, 1, 4 => 6
2, 4, 6 => 8
3, 3, 6 => 3

```

This is code golf - shortest code in bytes wins. Good luck!

# Answer
# Python, 56

```
g=lambda a,b,m,u=0:u!=(a,b)and-~g(b,(a+b)%m,m,u or(a,b))

```
> 15 votes

# Answer
# Retina, ~~69~~ 61 bytes

This was great fun to write!

```
(1* )(1*).*
x$2$1$0
(1*)(?=.* \1$)

)`x(1* 1*) .* \1 .*
x
x
1

```

Each line should go to its own file but you can run the code as one file with the `-s` flag.

Takes input in unary, in format `j i m` and gives output in unary.

The four substitution pairs do the followings:

* Add next element and increase step counter.
* Take modulo of the new element.
* If we reached the starting numbers delete everything except step counter. This will break the loop of the first three steps.
* Convert step count to unary number.

The string has the following format during the computation (with `(?#comments)`):

```
x*(?#number of steps)(1* )+(?#sequence, reversed)1*(?#modulus)

```

The code makes use of some observations:

* The modulus can be part of the sequence as it is bigger than any other number causing no false positive match.
* There will always be a number between the two repeating pair. I.e.output will always be at least 3. (The 3rd number can be the same as the 1st if the sequence starts as `x,0,x,x,...`)
* You have to subtract the modulo from the new number at most once.

Every substitution step shown in its own line for the example `j=1, i=1, m=4`:

```
1 1 1111
x11 1 1 1111
x11 1 1 1111
x11 1 1 1111
xx111 11 1 1 1111
xx111 11 1 1 1111
xx111 11 1 1 1111
xxx11111 111 11 1 1 1111
xxx1 111 11 1 1 1111
xxx1 111 11 1 1 1111
xxxx1111 1 111 11 1 1 1111
xxxx 1 111 11 1 1 1111
xxxx 1 111 11 1 1 1111
xxxxx1  1 111 11 1 1 1111
xxxxx1  1 111 11 1 1 1111
xxxxx1  1 111 11 1 1 1111
xxxxxx1 1  1 111 11 1 1 1111
xxxxxx1 1  1 111 11 1 1 1111
xxxxxx
xxxxxx
xxxxxx
xxxxxx
111111

```
> 9 votes

# Answer
# Haskell, ~~76~~ 71 bytes

```
p x y m=[i|(p,i)<-zip(x#y)[0..],(x,y)==p]!!1where x#y=(x,y):y#mod(x+y)m

```

Usage example: `p 1 1 5` -\> `20`.

How it works: `#` builds an infinite list of `(i,i+1)` pairs of the modular Fibonacci sequence. e.g. with `m==5`: `1#1`-\> `[(1,1),(1,2),(2,3),(3,0)...]`. The list comprehension `[i| ... ]` returns a list of indices of the positions of `(x,y)` within `x#y`. From this list I take the second element (-\> `!!1`), because the first (index `0`) is always at the beginning of `x#y`.

Edit: replaced `elemIndices` from `Data.List` with my own version.
> 5 votes

# Answer
# Pyth, 18 17 16 15 bytes

```
fqQu,eG%sGvzTQ1

```

Example input:

```
6
[2, 4]

```

Will output `8`.

It works by outputting increasingly long Fibonacci sequences (in pairs), until the end is the same as the start.
> 5 votes

# Answer
# C, 78 72 bytes

An essentially straightforward C solution. Perhaps there is a shorter solution by considering analytic expressions for Pisano periods of generalized Fibonacci numbers, though this thesis from 2013 makes it look like such expressions are not known.

```
g(o,t,m,N,M,i,v){N=o;M=t;for(i=1;v=N+M,N=M,M=v%m,N-o|M-t;i++);return i;}

```

Readable version, by way of explanation, is

```
int f(int one, int two, int mod) {
  int new_one, new_two, i, tmp;
  new_one = one;
  new_two = two;
  for(i = 1;
      tmp = new_one + new_two, new_one = new_two, new_two = tmp % mod,
      new_one - one | new_two - two;
      i++);
  return i;
}

```

And the examples

```
$ ./mod_fib 1 1 5
20
$ ./mod_fib 1 1 4
6
$ ./mod_fib 3 3 6
3
$ ./mod_fib 2 4 6
8

```

EDIT: returning the value instead of printing it is allowed in the spec and saves 6 bytes.
> 5 votes

# Answer
# Prolog, 116 bytes

```
a(A,B,M,R):-f([B,A],A,B,M,1,R).
f([A,B|T],X,Y,M,Z,R):-Z=0,Y=A,X=B,length(T,R);C is(A+B)mod M,f([C,A,B|T],X,Y,M,0,R).

```

Example: `a(1,1,5,R).` outputs `R = 20 .`
> 4 votes

# Answer
# CJam, 23 bytes

```
q~:MM*{_2$+M%}*]2ew(a#)

```

Reads whitspace-separated numbers from STDIN, in the same order as in the question.

Works by generating **m2** more numbers, pairing all and searching the index of the first pair in the rest.

Try it online in the CJam interpreter.
> 4 votes

# Answer
Much shorter answers have been posted, but:

# EcmaScript 6, 67 64 62  56 bytes

```
let f=(d,e,m,a=e,b=d+e)=>a^d||b^e?f(d,e,m,b,(a+b)%m)+1:1

```

Examples:

```
f(1,1,5) //20
f(1,1,4) // 6

```
> 1 votes

# Answer
## Perl, 88 bytes

```
($v,$w,$m)=@ARGV;$x=$v;$y=$w;do{$c++;($x,$y)=($y,($x+$y)%$m)}while($x-$v||$y-$w);print$c

```

Arguments given on the command line, in the order as in the question.
> 0 votes

---
Tags: code-golf, math, sequence, fibonacci
---


title: Generate Probabilities around a Numpad

text:
# Question
Title: Generate Probabilities around a Numpad
Inspired by this question earlier today, I'd like to see interesting ways various programming languages can turn a numpad into probabilities. Commonly, tile-based games will allow you to use a numpad to move in any direction based on where your character currently is. When making an AI for these games, `Math.random() * 8` is not sufficient, so I had to get a little creative to make the movement look and feel somewhat natural.

A numpad is defined as such:

```
7 | 8 | 9
- - - - -
4 | x | 6
- - - - -
1 | 2 | 3

```

Please note, 5 is an invalid number, as you cannot move onto yourself.

All examples will use these probabilities: `[50, 40, 30, 20, 10]`

If I wanted to generate probabilities around `8`, it would look like this:

```
40 | 50 | 40
-- | -- | --
30 | xx | 30
-- | -- | --
20 | 10 | 20

```

The output would be `[20, 10, 20, 30, 30, 40, 50, 40]` (with 5 omitted) or `[20, 10, 20, 30, null, 30, 40, 50, 40]` (with 5 present)

If I wanted to generate them around `1`, it would look like this:

```
30 | 20 | 10
-- | -- | --
40 | xx | 20
-- | -- | --
50 | 40 | 30

```

The output would be `[50, 40, 30, 40, 20, 30, 20, 10]` (with 5 omitted) or `[50, 40, 30, 40, null, 20, 30, 20, 10]` (with 5 present)

You may write a full program that takes the input in any usual way (command line, stdin) and prints the output, or you may write a function with a number argument, that prints or returns the output. Your program or function should accept one number - the position to generate around. You should use these probabilities: `[50, 40, 30, 20, 10]` (they do not have to be hardcoded).

Shortest code in bytes wins. Standard loopholes are disallowed. Answers posted in the linked thread are disallowed. Trailing or leading spaces are allowed. You may treat position `4` as absent or empty, depending on your preference. I'm not too picky on output format - print it out as comma-separated strings or as an array.

(This is my first question, go easy on me!)

# Answer
# CJam, 27 bytes

```
12369874s_$\_r#m<f{#4-z)0S}

```

Try it online in the CJam interpreter.

### Idea

If we go through the digits around **5** in counterclockwise fashion, we obtain the string `12369874` or any of its rotations (depending on the starting point).

After rotating this string so that the input digit **n** is at the leftmost position, the digits in the rotated string have the following probabilities:

```
50 40 30 20 10 20 30 40

```

If we consider the indexes of these digits, which are

```
 0  1  2  3  4  5  6  7

```

subtract **4** from each to yield

```
-4 -3 -2 -1  0  1  2  3

```

and take absolute values to get

```
 4  3  2  1  0  1  2  3

```

we only have to add **1** and append a **0** to get the desired probabilities.

### Code

```
12369874s                   e# Push "12369874".
         _$                 e# Push a sorted copy, i.e., "12346789".
           \                e# Swap it with the unsorted original.
            _r#             e# Find the index of the input in an unsorted copy.
               m<           e# Rotate the unsorted original that many units left.
                 f{       } e# For each character C in "12346789":
                            e#   Push the rotated string.
                   #        e#   Find the index of C.
                    4-      e#   Subtract 4.
                      z     e#   Compute the absolute value.
                       )    e#   Add 1.
                        0S  e#   Push a 0 and a space.

```
> 5 votes

# Answer
# Prolog, 166 bytes

```
a(A,R):-I:J:K:L:M=50:40:30:20:10,B is abs(5-A),member(B:S,[4:[I,J,K,J,L,K,L,M],3:[J,I,J,K,K,L,M,L],2:[K,J,I,L,J,M,L,K],1:[J,K,L,I,M,J,K,L]]),(A/5>1,reverse(S,R);S=R).

```

This uses the fact that the result for 9 is the reverse of the result for 1, same for 2 and 8, 3 and 7 and 4 and 6. There are recognizable patterns to go from the result of 1 to the results of 2,3 and 4 but I'm pretty sure it would be longer to code this than hardcoding the sequences for 1 to 4, which is what I did.

Example: `a(7,R).` outputs `R = [30, 20, 10, 40, 20, 50, 40, 30]`.
> 2 votes

# Answer
# Python - 115

```
a=[50,40,30,20,10,20,30,40]
b=[0,1,2,7,8,3,6,5,4]
def v(n):
 c=8-b[n-1]
 return[(a[c:]+a[:c])[e]for e in b if e-8]

```

`a` is an array with the values in order around the numpad (counter-clockwise from 1), and `b` maps numbers on the numpad to positions around it. Based on the number of spaces around the numpad for the input number (determined using `b`), it makes an array with that many elements moved from the front of `a` to the end, then uses `b` again to rearrange the elements to correspond with numpad numbers.
> 0 votes

# Answer
# Pyth - 38 bytes

Uses kinda the same technique as the Python answer except with base compression for the two arrays.

```
J_jC"3ê"T*RTm@.<jC"<àR"T-8@JtQd.DJ4

```

Try it here online.
> 0 votes

# Answer
# Java, 190

```
void g(int n){int i[]={8,0,1,2,7,8,3,6,5,4};String v="54321234",s="";n=i[n];if(n>0)v=v.substring(8-n)+v.substring(0,8-n);for(n=0;n++<9;s=", ")if(n!=5)System.out.print(s+v.charAt(i[n])+"0");}

```

`String v` holds the probabilities (divided by 10) in countrclockwise order with input = 1 being the default 50.

`int[]i` translates the input into an index into v. For example, `v.charAt(i[1])` is `5`. Inputs 0 and 5 are invalid so both i\[0\] and i\[5\] have a placeholder value of 8 which is the index for '\0' at the end of v.

I rotate the numbers in v to the right by the value i\[n\], and then print the probabilities as comma separated strings.
> 0 votes

---
Tags: code-golf
---