# Question
Title: Fastest array-by-array nearest neighbour search
**Intro -** Nearest neighbour comparison between two arrays is something that can be done very efficiently when only 1 variable per array is involved, because it can be done by sorting and then performing a rolling comparison. However, for a 2 variable comparison this sort operation cannot be done anymore and another smart way has to be thought of. Hence the challenge:

**Challenge -** The challenge is to write a code that can, for each row in array A, find a row in array B such that (A\[i,1\]-B\[j,1\])^2+(A\[i,2\]-B\[j,2\])^2 is minimal and that then stores the corresponding row number j. The perfect minimum (0) is a perfect match of A\[i,1\] with B\[j,1\] and of A\[i,2\] with B\[j,2\].

As a code example I have a very clunky loop written in R

```
N=nrow(SetA)
for (i in 1:N){

      #calculate vector with distance of row i to the entire SetB
      vec=with(SetB,(SetA[i,x]-x)^2+(SetA[i,y]-y)^2)

      #calculate minimum of that vector and store the index
      indexVec[i,ind:=which.min(vec)]
}

```

**Some sidenotes -** If it matters (not sure it will) assume that both arrays have 10k rows. Ties can be decided at 'random' e.g. determined by processing sequence or whatever way is more convenient in your code.

**Example in/out -** For clarity, here is the sample input

```
SetA=[1 3;2 4;3 5;4 6;5 7]
SetB=[2 2.5; 4 3.1; 2 2.0; 3 3.0; 6 5.0;]

```

and the expected sample output

```
indexVec=[1;4;4;5;5]

```

where the values in indexVec indicate where the nearest neighbour of row i in SetA is located in SetB.

Fastest code (as tested on my i5-4210U) wins. The testset will consist of 2 arrays of 10k rows and 2 columns filled with floating point numbers between -1E10 and +1E10. Of course seeded with the same seed to remove any unfairness.

**Feel free to use whatever language, but I am also very interested in an optimized version of the R code above.**

# Answer
## C++, .0007 seconds

Uses a simple grid to place all the points of B, then looks up the points of A starting at the grid point to which it maps.

```
#include <stdio.h>
#include <stdlib.h>
#include <thread>
#include <sys/time.h>

double mytime() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec + tv.tv_usec * 1e-6;
}

typedef float vector[2];

#define T 4
// N must be a multiple of T
#define N 10000

// Width of grid.  Should be about sqrt(N)
#define W 100

vector a[N];
vector b[N];
int min[N];

float dist(vector x, vector y) {
    float a = x[0]-y[0];
    float b = x[1]-y[1];
    return a*a+b*b;
}

int mindist_test(vector x, vector *y, int n) {
    float best = dist(x, y[0]);
    int bestidx = 0;
    for(int i = 1; i < n; i++) {
        float d = dist(x, y[i]);
        if(best > d) {
            best = d;
            bestidx = i;
        }
    }
    return bestidx;
}

typedef struct cell cell;
struct cell {
    vector v;
    cell *next;
};

cell *grid[W][W];
cell cells[N];

float minx, miny, scalex, scaley, scale, scale2;

void build() {
    // Find bounds
    minx = b[0][0];
    miny = b[0][1];
    float maxx = b[0][0];
    float maxy = b[0][1];
    for(int i = 1; i < N; i++) {
        if(minx > b[i][0])
            minx = b[i][0];
        if(maxx < b[i][0])
            maxx = b[i][0];
        if(miny > b[i][1])
            miny = b[i][1];
        if(maxy < b[i][1])
            maxy = b[i][1];
    }
    scalex = (maxx - minx + .00001) / W;
    scaley = (maxy - miny + .00001) / W;
    scale = scalex < scaley ? scalex : scaley;
    scale2 = scale * scale;

    // Place B vectors in grid
    for(int i = 0; i < N; i++) {
        cells[i].v[0] = b[i][0];
        cells[i].v[1] = b[i][1];
        int x = int((b[i][0] - minx) / scalex);
        int y = int((b[i][1] - miny) / scaley);
        cells[i].next = grid[x][y];
        grid[x][y] = &cells[i];
    }
}

int find(vector v) {
    // Start checking at grid[x][y]
    int x = int((v[0] - minx) / scalex);
    int y = int((v[1] - miny) / scaley);

    float mindist = 1e30;
    cell *mincell;

    // Look in grid cells within radius r
    for(int r = 1; r < W; r++) {
        for(int i = x-r; i <= x+r; i++) {
            if(i < 0 || i >= W) continue;
            for(int j = y-r; j <= y+r; j++) {
                if(j < 0 || j >= W) continue;
                for(cell *c = grid[i][j]; c != NULL; c = c->next) {
                    float d = dist(v, c->v);
                    if(mindist > d) {
                        mindist = d;
                        mincell = c;
                    }
                }
            }
        }
        // If we've found a point close enough, stop.
        // The next iterations' points are guaranteed to be at least distance r*scale away.
        if(mindist < (r*r)*scale2)
            break;
    }
    return mincell - cells;
}

void thr(int t) {
    int base = N/T*t;
    for(int i = 0; i < N/T; i++) {
        min[base+i] = find(a[base+i]);
    }
}

int main(int argc, char *argv[]) {
    // Initialize
    for(int i = 0; i < N; i++) {
        a[i][0] = rand() / (RAND_MAX/1000000.);
        a[i][1] = rand() / (RAND_MAX/1000000.);
        b[i][0] = rand() / (RAND_MAX/1000000.);
        b[i][1] = rand() / (RAND_MAX/1000000.);
    }

    // Run & time
    double start = mytime();
    build();
    std::thread* threads[T];
    for(int t = 0; t < T; t++) {
        threads[t] = new std::thread(thr, t);
    }
    for(int t = 0; t < T; t++) {
        threads[t]->join();
    }
    double stop = mytime();
    printf("time: %f\n", stop - start);

    // Check results
    for(int i = 0; i < N; i++) {
        int j = min[i];
        int k = mindist_test(a[i], b, N);
        if(dist(a[i], b[j]) != dist(a[i], b[k])) {
            printf("BAD %d: %d %f %f\n", i, j, dist(a[i], b[j]), dist(a[i], b[k]));
        }
    }
}

```

Compile with

```
g++ -O3 -std=c++11 -stdlib=libc++ grid.cc -o grid

```
> 7 votes

# Answer
# Mathematica 0.035230 secs

## Update

The latest version required

* **0.035230 sec for 10k rows of data**
* 0.419461 sec for 100k rows
* 4.975199 sec for 1 million rows

---

```
nf = Nearest[Thread[B -> Range[n]]]

```

The nearest function, `nf`, delivers a 100 fold speedup over the prior approach. This is due to the creation of a lookup table for positions:

```
r[m_]:= RandomReal[{-E^10,E^10},{m,2}]
n = 10000;
A = r[n];
B = r[n];
(nf = Nearest[Thread[B -> Range[n]]];
 Flatten@(nf[#, 1][[1]] & /@ A);) // AbsoluteTiming

```

> {0.035230, Null}

---

**Example**

```
n = 10;
A = r[n]
B = r[n]
(nf = Nearest[Thread[B -> Range[n]]]; Flatten@(nf[#, 1][[1]] & /@ A))

```

> (\*A \*)
> {{3944.81, 10711.}, {-12978.5, -7807.64}, {-7309.13, 15.5648}, {-2695.33, 6309.87}, {14819.7, 21796.6}, {20681.7, -296.336}, {-7396.73, -9588.16}, {73.5495, -7730.14}, {-20361.8, -4616.41}, {21576.4, -18024.}}
>
> (\*B \*)
> {{21382., -597.126}, {5872.82, 6305.16}, {-10502.4,2378.9}, {-5643.86, 19461.4}, {-4986.97, -2173.96}, {10024.5, 14230.6}, {6747.26, 6242.93}, {15714.1, -18345.4}, {-21971., -5052.04}, {-17088.2, 3853.11}}
>
> (\*Output \*)
> {2, 9, 5, 2, 6, 1, 5, 5, 9, 8}

---

I'm including 2 earlier approaches to highlight the improvements in speed due to seemingly minor tweaks.

## Prior approach

This takes about 3.5 seconds for arrays of {10^4,2},

This makes it 10 times slower than the above approach, but 10 times faster than my first, naive, implementation.

The key improvement was to look for positions through one call. It also uses the built-in Nearest function (but doesn't exploit it nearly as well as the current version).

```
r[m_]:= RandomReal[{-E^10,E^10},{m,2}]
n=10000;
A=r[n];
B=r[n];
nf = Nearest[B];
Flatten@Position[B, #] & /@ (nf[#, 1][[1]] & /@ A); // AbsoluteTiming

```

> {3.554101, Null}

---

## First attempt

This unoptimized version takes 40 seconds for 10k rows.

```
r:= RandomReal[{-E^10,E^10},{10^4,2}]
nearness[{r1_,c1_},array_]:=Total[({r1,c1}-#)^2]&/@array
nearestPosition[aArray_,bArray_]:=Position[z=nearness[#,bArray],Min[z]][[1,1]]&/@aArray

```

Test

```
A = r
B = r
nearestPosition[A, B]; // AbsoluteTiming

```

> {40.141484, Null}
> 5 votes

# Answer
# Python 3

```
from scipy import spatial
import numpy as np

def nearest_neighbour(points_a, points_b):
    tree = spatial.cKDTree(points_b)
    return tree.query(points_a)[1]

```

**0.05 seconds for 10k rows of data**, 0.7 seconds for 100k rows, and 7.6 seconds for a million rows.

Originally I wanted to implement the approach myself, but why do so, when NumPy and SciPy offer everything you want.

The idea is to build a KD-tree of the points b. Using this KD-tree you can effectively search for the nearest points, since you can restrict the search space quite a bit. I'm not completely sure about the implementation of SciPy, but you can check out one algorithm at Wikipedia.

The complexity of this should be about `O(N*log(N))` for computing the KD-tree (`N` is the number of entries) and `O(log(N))` for a single search on average. If `N = #a = #b`, the total complexity is `O(N*log(N))`, which is a lot better than the brute force approach with `Theta(N^2)`

## Tests

The output of example in Michiel's post is `[0 3 3 4 4]` (Off by one because R).

```
a = np.array([[1, 3],[2, 4],[3, 5],[4, 6],[5, 7]])
b = np.array([[2, 2.5],[4, 3.1],[2, 2.0],[3, 3.0],[6, 5.0]])
print(nearest_neighbour(a, b))

```

Testing it for `n = 10k`:

```
import time
n = 10**4
points_a = np.random.rand(n, 2)
points_b = np.random.rand(n, 2)

start_time = time.time()
result = nearest_neighbour(points_a, points_b)
end_time = time.time()
print("n = {:7d}, {:.3f} seconds".format(n, end_time - start_time))

```

You can view the complete program at Gist.
> 4 votes

# Answer
**R**

You can vectorize your operations for a bit more speed. If you need something faster, move to a different language lol.

```
# Original data
SetA = matrix(c(1, 3, 2, 4, 3, 5, 4, 6, 5, 7), nrow = 2)
SetB = matrix(c(2, 2.5, 4, 3.1, 2, 2.0, 3, 3.0, 6, 5.0), nrow = 2)

# 10k random sample data
SetA = matrix(sample(1:20, 20000, replace = T), nrow = 2)
SetB = matrix(sample(1:20, 20000, replace = T), nrow = 2)

apply(X = SetA, MARGIN = 2, FUN = function(z) which.min((SetB[1,]-z[1])^2 + (SetB[2,]-z[2])^2))

```

Takes me ~2.6s to run 10k points.

edit:

Vectorized it a bit more. This version is another 0.3s faster than the solution above.

```
apply(X = SetA, MARGIN = 2, FUN = function(z) {which.min(colSums((z-SetB)^2))})

```
> 3 votes

# Answer
## C++ with AVX, brute force, 0.013 seconds

10K isn't that big, right? Just plow through the O(n^2) algorithm using AVX instructions to do it really fast. I'm using single-precision floating point, I hope that is ok.

Update: now with threads!

```
#include <stdio.h>
#include <immintrin.h>
#include <thread>
#include <sys/time.h>

double mytime() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec + tv.tv_usec * 1e-6;
}

typedef float vector[2];

// for each 0<=i<4, finds y[j] closest to x[i] 0<=j<n.
// puts the resulting j's in r[0..3].
void mindist(vector *xp, vector *yp, int n, int *r) {
    // Load 4 vectors from x
    __m256 x = _mm256_load_ps(&xp[0][0]);

    // Best distance & its index found so far, for the 4 x vectors.
    // Packed strangely in the 8 32-bit-float-sized slots.
    // 0: dist0
    // 1: dist1
    // 2: idx0
    // 3: idx1
    // 4: dist2
    // 5: dist3
    // 6: idx2
    // 7: idx3
    __m256 best = _mm256_set_ps(0, 0, 1e30, 1e30, 0, 0, 1e30, 1e30);

    // Indexes are floats, integer addition doesn't come until AVX2
    __m256 idx = _mm256_set_ps(3,2,0,0,1,0,0,0);
    __m256 idxinc = _mm256_set_ps(4,4,0,0,4,4,0,0);

    // Process 4 y vectors at a time
    for(int i = 0; i < n; i += 4) {
        __m256 y = _mm256_load_ps(&yp[i][0]);

        for(int j = 0; j < 4; j++) {
            // Compute difference of vectors
            __m256 diff = _mm256_sub_ps(x, y);

            // Square each component
            __m256 square = _mm256_mul_ps(diff, diff);

            // Add pairs.  Results are in floats 0,1,4,5
            __m256 sum = _mm256_hadd_ps(square, square);
            // Set remaining slots using indexes
            sum = _mm256_blend_ps(sum, idx, 0b11001100);

            // Compare with best distance so far
            __m256 cmp = _mm256_cmp_ps(sum, best, _CMP_LT_OQ);
            // Duplicate comparison masks to index slots
            cmp = _mm256_permute_ps(cmp, 0b01000100);

            // Take new distance/index if it is smaller
            best = _mm256_blendv_ps(best, sum, cmp);

            // Shuffle b & idx vectors around.  This trickery
            // puts all 4 b vectors in all 4 slots.
            if(j == 0 || j == 2) {
                // abcd -> cdab
                y = _mm256_permute2f128_pd(y, y, 0x01);
                idx = _mm256_permute2f128_pd(idx, idx, 0x01);
            } else {
                // abcd -> badc
                y = _mm256_permute_pd(y, 0b0101);
                idx = _mm256_permute_ps(idx, 0b10110000);
            }
        }
        idx = _mm256_add_ps(idx, idxinc);
    }
    // Extract results
    best = _mm256_cvtps_epi32(best);
    r[0] = _mm256_extract_epi32(best, 2);
    r[1] = _mm256_extract_epi32(best, 3);
    r[2] = _mm256_extract_epi32(best, 6);
    r[3] = _mm256_extract_epi32(best, 7);
}

// number of threads
#define T 4

// N must be a multiple of 4*T
#define N 10000

vector a[N] __attribute__((aligned(32)));
vector b[N] __attribute__((aligned(32)));
int min[N];

float dist(vector x, vector y) {
    float a = x[0]-y[0];
    float b = x[1]-y[1];
    return a*a+b*b;
}

int mindist_test(vector x, vector *y, int n) {
    float best = dist(x, y[0]);
    int bestidx = 0;
    for(int i = 1; i < n; i++) {
        float d = dist(x, y[i]);
        if(best > d) {
            best = d;
            bestidx = i;
        }
    }
    return bestidx;
}

void thr(int t) {
    for(int i = 0; i < N/T; i += 4) {
        mindist(&a[N/T*t+i], b, N, &min[N/T*t+i]);
    }
}

int main(int argc, char *argv[]) {
    // Initialize
    for(int i = 0; i < N; i++) {
        a[i][0] = rand() / (RAND_MAX/1000000.);
        a[i][1] = rand() / (RAND_MAX/1000000.);
        b[i][0] = rand() / (RAND_MAX/1000000.);
        b[i][1] = rand() / (RAND_MAX/1000000.);
    }

    // Run & time
    double start = mytime();
    std::thread* threads[T];
    for(int t = 0; t < T; t++) {
        threads[t] = new std::thread(thr, t);
    }
    for(int t = 0; t < T; t++) {
        threads[t]->join();
    }
    double stop = mytime();
    printf("time: %f\n", stop - start);

    // Check results
    for(int i = 0; i < N; i++) {
        int j = min[i];
        int k = mindist_test(a[i], b, N);
        if(dist(a[i], b[j]) != dist(a[i], b[k])) {
            printf("BAD %d: %d %f %f\n", i, j, dist(a[i], b[j]), dist(a[i], b[k]));
        }
    }
}

```

Compiled on my mac with

```
clang++ -O3 -mavx -std=c++11 -stdlib=libc++ avx4.cc -o avx4

```
> 1 votes

# Answer
## C++11

(Naive approach with O(N^2) complexity. With a kd-tree it could probably be improved a lot. I'll work on it in the future)

Okay, this C++ code should work a lot better than the matlab code posted below. In my computer it runs in ~0.5s for the 10k values. I've compiled it in VS, but it should work in linux, although I don't know the command line code to compile it properly, I guess it will need `-std=c++11` and maybe `-pthread` for the threading.

As for the loading from file, I would need the format of the loaded file to prepare it for you. As it is right now, it creates a rng and fills the two arrays with random floats.

```
#include <chrono>
#include <iostream>
#include <limits>
#include <thread>
#include <random>

#define ROWS 10000
#define sqdiff(a,b) (((b)-(a))*((b)-(a)))
void NN(float a[][2], float b[][2], int c[], int length)
{
    for (int i = 0; i < length; ++i)
    {
        int k = 0;
        float m = std::numeric_limits<float>::infinity();
        float x = a[i][0];
        float y = a[i][1];
        for (int j = 0; j < ROWS; j += 4)
        {
            {
                float d = sqdiff(x, b[j][0]) + sqdiff(y, b[j][1]);
                if (d < m) k = j;
            }
            {
                float d = sqdiff(x, b[j+1][0]) + sqdiff(y, b[j+1][1]);
                if (d < m) k = j;
            }
            {
                float d = sqdiff(x, b[j+2][0]) + sqdiff(y, b[j+2][1]);
                if (d < m) k = j;
            }
            {
                float d = sqdiff(x, b[j+3][0]) + sqdiff(y, b[j+3][1]);
                if (d < m) k = j;
            }
        }
        c[i] = k;
    }
}

void InitializeRandomArray(float* a, int length)
{
    std::default_random_engine generator;
    std::uniform_real_distribution<float> distribution;

    for (int i = 0; i < length; ++i)
    {
        a[i] = distribution(generator);
    }
}

int main(int argc, char** argv)
{
    float a[ROWS][2];
    float b[ROWS][2];
    int c[ROWS];

    std::thread* threads[4];

    // Initialization
    InitializeRandomArray((float*)a, ROWS*2);
    InitializeRandomArray((float*)b, ROWS*2);

    // Time counter
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();

    // Computation
    for (int t = 0; t < 4; ++t)
    {
        threads[t] = new std::thread(NN, &(a[ROWS/4*t]), b, &(c[ROWS/4*t]), ROWS/4);
    }

    // Thread joining
    for (int t = 0; t < 4; ++t)
    {
        threads[t]->join();
        delete threads[t];
    }

    // Output of time used
    end = std::chrono::system_clock::now();
    std::chrono::duration<double> elapsed_seconds = end - start;
    std::cout << "elapsed time: " << elapsed_seconds.count() << "s" << std::endl;

    return 0;
}

```

---

## Matlab

This version runs as slow as a turtle, it took about 6s for 1k arrays in octave. In matlab i believe it may run faster, but can't check it right now as I don't have it installed in this computer.

```
function [c] = NN(a, b)
    c = zeros(size(a,1),1);

    for i=1:size(a,1)
        [_,c(i)] = min(sum((b-a(i,:)).^2, 2));
    end
end

```

I'm sure this can be made very optimized in C but I lack the time to implement it right now.
> 0 votes

# Answer
## R

```
N=nrow(SetA)
for (i in 1:N){
      vec=with(SetB,(SetA[i,x]-x)^2+(SetA[i,y]-y)^2)

      indexVec[i,ind:=which.min(vec)]
}

```

**18 seconds for 10k rows**

I am quite sure that it should be possible to make this much more efficient
> 0 votes

---
Tags: fastest-code, optimization
---


title: Create a Scalable Valentine's Day Heart

text:
# Question
Title: Create a Scalable Valentine's Day Heart
Happy Valentine's Day! To celebrate this day of love and happiness (or sadness and loneliness for those of us who are single...), let's write some code to create some hearts!

Specifically, if you take this challenge upon you, you are to write code to output a heart/hearts as an **image file**, with the ability to easily change the dimensions of the image (both width and height, separately). You could take input into your program to get the dimensions, or two simple variables that can be changed would be enough (or a couple constants). If you do opt for the variables, no more than two tokens of the program should be changed to adjust the size.

So for instance, you could write a program to output this image (with variable width and height, of course):

However, that heart isn't that interesting. It's just a plain heart. I challenge you to create the most creative and interesting heart that you can!

# Answer
> 1 votes
# Bash: 16 characters

```
echo -e "\u2665"

```

output (when unicode supported)

Ah wait, it must be an image?

# ImageMagick: 137 characters

```
w=99
h=199
convert -size ${w}x$w -gravity center -font WebDings -fill red label:Y h.gif
convert h.gif -resize ${w}x$h\! h2.gif

```

output (when WebDings font installed)

# Answer
> 1 votes
# Java

```
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import javax.imageio.ImageIO;

import static java.lang.Math.PI;
import static java.lang.Math.cbrt;
import static java.lang.Math.pow;
import static java.lang.Math.sqrt;

public class Heart {
    public static double scale(int x, int range, double l, double r) {
        double width = r - l;
        return (double) x / (range - 1) * width + l;
    }

    public static void main(String[] args) throws IOException {
        BufferedImage img = new BufferedImage(1000, 1000, BufferedImage.TYPE_INT_RGB);
        final double max_heart = 0.679; // This is the approximate max value that can come out of the heart function (found by trial and error)
        double max = 0.0;
        for (int x = 0; x < img.getWidth(); x++) {
            for (int y = 0; y < img.getHeight(); y++) {
                double xv = scale(x, img.getWidth(), -1.2, 1.2);
                double yv = scale(y, img.getHeight(), -1.3, 1);
                double heart = heart(xv, yv);
                int r = 0xFF;
                int gb = (int) (0xFF * (max_heart - heart));
                int rgb = (r << 16) | (gb << 8) | gb;
                img.setRGB(x, y, rgb);
            }
        }
        ImageIO.write(img, "png", new File("location/heart.png"));
    }

    public static double heart(double xi, double yi) {
        double x = xi;
        double y = -yi;
        double temp = 5739562800L * pow(y, 3) + 109051693200L * pow(x, 2) * pow(y, 3) - 5739562800L * pow(y, 5);
        double temp1 = -244019119519584000L * pow(y, 9) + pow(temp, 2);
        if (temp1 < 0) {
            return topHeart(x, y, temp, temp1);
        }
        double temp2 = sqrt(temp1);
        double temp3 = cbrt(temp + temp2);
        if (temp3 != 0) {
            double part1 = (36 * cbrt(2) * pow(y, 3)) / temp3;
            double part2 = 1 / (10935 * cbrt(2)) * temp3;
            double looseparts = 4.0 / 9 - 4.0 / 9 * pow(x, 2) - 4.0 / 9 * pow(y, 2);
            double sqrt_body = looseparts + part1 + part2;
            if (sqrt_body >= 0) {
                return sqrt(sqrt_body);
            } else {
                return -1;
            }
        } else {
            return Math.sqrt(Math.pow(2.0 / 3, 2) * (1 - Math.pow(x, 2)));
        }
    }

    private static double topHeart(double x, double y, double temp, double temp1) {
        //complex arithmetic
        double[] temp3 = cbrt_complex(temp, sqrt(-temp1));
        double[] part1 = polar_reciprocal(temp3);
        part1[0] *= 36 * cbrt(2) * pow(y, 3);
        double[] part2 = temp3;
        part2[0] /= (10935 * cbrt(2));
        toRect(part1, part2);
        double looseparts = 4.0 / 9 - 4.0 / 9 * pow(x, 2) - 4.0 / 9 * pow(y, 2);
        double real_part = looseparts + part1[0] + part2[0];
        double imag_part = part1[1] + part2[1];
        double[] result = sqrt_complex(real_part, imag_part);
        toRect(result);

        if (Math.abs(result[1]) < 1e-5) {
            return result[0];
        }
        return -1;
    }

    public static double[] cbrt_complex(double a, double b) {
        double r = Math.hypot(a, b);
        double theta = Math.atan2(b, a);
        double cbrt_r = cbrt(r);
        double cbrt_theta = 1.0 / 3 * (2 * PI * Math.floor((PI - theta) / (2 * PI)) + theta);
        return new double[]{cbrt_r, cbrt_theta};
    }

    public static double[] sqrt_complex(double a, double b) {
        double r = Math.hypot(a, b);
        double theta = Math.atan2(b, a);
        double sqrt_r = Math.sqrt(r);
        double sqrt_theta = 1.0 / 2 * (2 * PI * Math.floor((PI - theta) / (2 * PI)) + theta);
        return new double[]{sqrt_r, sqrt_theta};
    }

    public static double[] polar_reciprocal(double[] polar) {
        return new double[]{1 / polar[0], -polar[1]};
    }

    public static void toRect(double[]... polars) {
        for (double[] polar: polars) {
            double a = Math.cos(polar[1]) * polar[0];
            double b = Math.sin(polar[1]) * polar[0];
            polar[0] = a;
            polar[1] = b;
        }
    }
}

```

To scale, just change the x/y dimensions of this line (the first line in the main function):

```
BufferedImage img = new BufferedImage(1000, 1000, BufferedImage.TYPE_INT_RGB);

```

Output (for a size of `1000` by `1000`):

---

On wikipedia, there is a 3D heart shown. This was my inspiration; I thought to myself, "Why not use a 3D heart and use the Z output as color?" So that's exactly what I did. However, I didn't use the exact same formula; I used this implicit equation for a 3D heart:

I played around in Mathematica, (I think I switched `z` and `y`) and solved for `z`, yielding this really ugly equation (click for full size):

Then, I "simply" implemented the function in Java. Okay, it wasn't so simple. I had to do some checks to avoid exceptions (no sqrts of negative numbers). But there is one case where we do need to take a sqrt of a negative number (IE delve into the complex world) in order to get a real output. That's why I have the `topOfHeart` function; it does the computation for that part. If I replace the call to that function with `return -1`, this is the image I get instead (smallified):

A couple interesting things to note:

* I do a lot of `return -1` to show that I reached an invalid value, but I don't handle this in the `main` function. This results in a color of `0xFFADAD` \- a lovely shade of pink
* The complex number functions are semi-interesting. I switch between polar and rectangular coordinates, since polar coordinates make multiplicative operations easier, while rectangular coordinates make additive operations easier.

+ `cbrt_complex` and `sqrt_complex` are actually very interesting. Using wolframalpha, I found this formula for the nth root of a complex number (polar form):
    + taking the reciprocal of a polar coordinate complex number is easy: `r e` -\> `1/r e<sup>-iθ</sup>`
    + multiplying by a real number `d` is also easy: `r e` -\> `d r e`

---
Tags: popularity-contest, image-processing
---


# Question
Title: Pseudo-quine polyglot language-detection counters
Quines are fun. Polyglots are fun, too. Polyglot Quines exist, but we can raise the bar even higher.

Write a file that contains a valid program for languages α, β, and γ. When the file is executed (possibly after compiling it) as a language α or β program, the program's output shall be of the same form as a valid submission to this contest. If your file is executed as a language γ program, it shall output a number. The value of this number is the chain of previous executions of the program interpreted as a binary number.

This explanation might be a bit hard to understan, so here is an example. Let Α, Β, and Γ be functions that execute their input as a language α, β, or γ resp. program and return the output of these programs. Let *x* be a valid submission to this contest. Then the following expression, where we process *x* through language β, α, β, α, α, β, and γ in this order, shall yield 41, since 4110 = 1010012.

> Γ(Β(Α(Α(Β(Α(Β(*x*)))))))

You may not assume that penultimate execution in the chain is an execution in language β. For the case where your original submission is directly executed as a language γ program, it shall print 0.

Your program shall behave correctly for up to sixteen compilations in the chain; that is, the highest number your program might print out at the end is 215 \- 1. Of course, your program is allowed to support longer compilation chains.

This is a popularity contest to encourage creative solutions. The submission with the highest vote tally wins.

# Answer
# Python 2, Python 3, \>\<\> (Fish)

```
#;n0
import sys
x='\\\'\nn#;n0import sysx=v=int(1/2*2)sys.stdout.write(x[4:7]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[7:8]),sys.stdout.write(x[2:3]),sys.stdout.write(x[8:18]),sys.stdout.write(x[2:3]),sys.stdout.write(x[18:20]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[3:4]),sys.stdout.write(x[4:7]),sys.stdout.write(x[7:8]),sys.stdout.write(x[8:18]),sys.stdout.write(x[18:20]),sys.stdout.write(x[20:32]),sys.stdout.write(x[32:851]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[1:2]),sys.stdout.write(x[2:3]),sys.stdout.write(x[20:32]),sys.stdout.write(x[2:3]),sys.stdout.write(x[32:851])n'
v=int(1/2*2)
sys.stdout.write(x[4:7]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[7:8]),sys.stdout.write(x[2:3]),sys.stdout.write(x[8:18]),sys.stdout.write(x[2:3]),sys.stdout.write(x[18:20]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[3:4]),sys.stdout.write(x[4:7]),sys.stdout.write(x[7:8]),sys.stdout.write(x[8:18]),sys.stdout.write(x[18:20]),sys.stdout.write(x[20:32]),sys.stdout.write(x[32:851]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[1:2]),sys.stdout.write(x[2:3]),sys.stdout.write(x[20:32]),sys.stdout.write(x[2:3]),sys.stdout.write(x[32:851])

```

## Python explanation

The Python 2 and Python 3 interpreters work similarly except the `v=int(1/2*2)` variable gets different values (`0` and `1`) as Python 2 uses float division and Python 3 uses integer division.

In every run they add the expression `+0*2` or `+1*2` to the first line (after `#;n`) and to the `x` string (after the last write command). The \>\<\> interpreter uses the first addition and the Pythons use the second one to create correct quines.

Code after `B(A(B(B(x))))`:

```
#;n+1*2+0*2+1*2+1*20
import sys
x='\\\'\nn#;n0import sysx=v=int(1/2*2)sys.stdout.write(x[4:7]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[7:8]),sys.stdout.write(x[2:3]),sys.stdout.write(x[8:18]),sys.stdout.write(x[2:3]),sys.stdout.write(x[18:20]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[3:4]),sys.stdout.write(x[4:7]),sys.stdout.write(x[7:8]),sys.stdout.write(x[8:18]),sys.stdout.write(x[18:20]),sys.stdout.write(x[20:32]),sys.stdout.write(x[32:851]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[1:2]),sys.stdout.write(x[2:3]),sys.stdout.write(x[20:32]),sys.stdout.write(x[2:3]),sys.stdout.write(x[32:851])+1*2+0*2+1*2+1*2n'
v=int(1/2*2)
sys.stdout.write(x[4:7]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[7:8]),sys.stdout.write(x[2:3]),sys.stdout.write(x[8:18]),sys.stdout.write(x[2:3]),sys.stdout.write(x[18:20]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[0:1]),sys.stdout.write(x[1:2]),sys.stdout.write(x[0:1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[3:4]),sys.stdout.write(x[4:7]),sys.stdout.write(x[7:8]),sys.stdout.write(x[8:18]),sys.stdout.write(x[18:20]),sys.stdout.write(x[20:32]),sys.stdout.write(x[32:851]),sys.stdout.write(chr(43)+str(v)+chr(42)+chr(50)),sys.stdout.write(x[851:-1]),sys.stdout.write(x[3:4]),sys.stdout.write(x[1:2]),sys.stdout.write(x[2:3]),sys.stdout.write(x[20:32]),sys.stdout.write(x[2:3]),sys.stdout.write(x[32:851])

```

## \>\<\> (Fish) explanation

When you run the \>\<\> interpreter the code pointer bounces back from the `#` wraps around the first line and starting from the end of the first line and heading West starts pushing numbers onto the stack. If an operator comes (`+` or `*`) it pops the top two elements from the stack and pushes back the result. With this method we end up with the base2 representation of the previous runs (`13` in the former example). This is the desired number so we output it with `n` and terminate with `;`.
> 13 votes

---
Tags: popularity-contest, quine, polyglot
---


title: Rotor Routers on a Grid

text:
# Question
Title: Rotor Routers on a Grid
# Input

Your input is a single string, separated by newlines into `2n+1` lines of length `2n+1`, for some integer `n ≥ 0`. The integer `n` is not part of the input; you'll have to compute it from the string. The lines are composed of the "direction characters" `>^<v`. If newlines pose a problem, you can replace them by vertical pipes `|`.

The input forms a square grid of size `(2n+1)x(2n+1)`, and each cell of the grid is interpreted as a *rotor router*, which points in one of the four cardinal directions. We proceed to drop a *token* on the router at the center of the grid, and then the routers will move it around in the following way. When the token lands on a router, the router turns 90 degrees in the counter-clockwise direction, and moves the token one step in the new direction it points to. If it lands on another router, the process is repeated, but eventually, the token will fall off the grid.

# Output

Your output is the final configuration of the routers, in the same format as the input.

# Example

As an example input, consider the `3x3` grid

```
<^<
^**>**<
>^v

```

where the central router has been highlighted to indicate the token (it's a bit hard to see). The central router rotates to face north, and moves the token to the central cell of the top row:

```
<**^**<
^^<
>^v

```

This router rotates to face west, and sends the token to the top left corner:

```
**<**<<
^^<
>^v

```

The router in the corner sends the token south, so it's now at the leftmost cell of the middle row:

```
v<<
**^**^<
>^v

```

That router rotates to face west and sends the token off the grid.

```
v<<
<^<
>^v

```

This is the final grid configuration, so your program should output it. Note that in more complex examples, the token can pass the same router multiple times before falling off the grid.

# Rules

You can write either a function or a full program. This is code-golf, so the lowest byte count wins. Standard loopholes are disallowed. You can decide whether there is a trailing newline in the input and/or output.

# Test Cases

```
Input:
v
Output:
>

Input:
<^<
^><
>^v
Output:
v<<
<^<
>^v

Input:
>>^>>
v<vv<
>^>^<
^<>>^
vvv>>
Output:
>>^>>
>v>>v
^>>vv
^^>>>
v^<<^

Input:
<^^^^^^^^
<<^^^^^^>
<<<^^^^>>
<<<<^^>>>
<<<<^>>>>
<<<vv>>>>
<<vvvv>>>
<vvvvvv>>
vvvvvvvv>
Output:
>>>>>>>>v
^>>>>>>vv
^^>>>>vvv
^^^>>vvvv
<<<<<vvvv
^^^^<<vvv
^^^<<<<vv
^^<<<<<<v
^<<<<<<<<

```

# Answer
# CJam, ~~62~~ ~~61~~ 63 bytes

Try it online

```
Nq_N#):D;+_,2/{:P"^<v>^

"_P4$=#:X)=t_,0PX[1DW*WDSP]=-e>e<}h;1>

```

Expanded and commented:

```
Nq              "Read the input grid";
_N#):D;         "Calculate the vertical delta (line length + 1)";
+               "Prepend a newline to the grid";
_,2/            "Calculate the initial position as the length of the grid
                 string divided by 2";
{               "Do...";
  :P"^<v>^

"
  _P4$=           "Get the character indexed by the position in the grid";
  #:X             "Map the character to an operation number:
                   '^'=>0, '<'=>1, 'v'=>2, '>'=>3, '^'=>4, '\n'=>5, '\n'=>6
                   (the unreachable duplicate mappings are important below)";
  )=t             "Set the character indexed by the position in the grid to
                   the result of mapping the operation number + 1 backwards";
  _,0PX[1DW*WDSP]="Map the operation number to a negated delta (this occurs
                   after rotating routers, which means that operation n should
                   act like the character corresponding to operation n + 1):
                   0=>1, 1=>-delta, 2=>-1, 3=>delta, 5=>position";
  -e>e<           "Subtract the negated delta from the position and clamp it to
                   [0, length of the grid string] (array indices are circular,
                   so the length of the grid string will act like the index 0
                   and point to the initial newline next iteration, which will
                   *really* set the position to 0)";
}h              "... while the position is not 0 (i.e. not at the initial
                 newline)";
;1>             "Clean up and remove the initial newline";

```

My solution operates on the input as a flat string, so there's only one position value to keep track of and virtually no pre/postprocessing; there are only 2 bytes of preprocessing to add newline to the beginning of the grid and 2 bytes of postprocessing to remove it from the output. But these 4 bytes are well worth the cost as they let me keep newlines in and "execute" them like routers, but they "rotate" into another newline and set the position to zero. And the main loop ends when the position becomes zero.
> 3 votes

# Answer
# CJam, ~~90~~ 69 bytes

```
q_,mqi):L_*Lm2/(:X;{_X_@="^<v>"_@#_[WL1LW*]=X+:X;)=tX)L%XW>XLL(*<**}g

```

~~Huge for now,~~ Can still be reduced a lot.

Try it online here
> 2 votes

# Answer
# JavaScript (ES6) 121 ~~120 127 129~~

A named function that gets the string as an input parameter and returns the output.
Assuming the input string is terminated with a newline.

**Edit** bug fix, .search() does not work well with `undefined`

```
F=s=>(o=~s.search('\n'),s=[...s],
R=p=>~(u='^<v>'.indexOf(s[p]))?R(p+[-1,-o,1,o][u],s[p]='<v>^'[u]):s)(-~o*o/2-1)
.join('')

```

**Ungolfed** and explained

```
F=s=>{
  o = s.search('\n')+1; // offset to next row
  s = [...s]; // string to array
  R=p=>{ // recursive search functiom, parameter p is current position in grid
    u = '^<v>'.indexOf(s[p]); // find direction
    if (u<0) return s; // if no direction found, out of grid -> stop recursion
    s[p] = '<v>^'[u] // set new direction into the array cell
    return R(p+[-1,o,1,-o][u]) // call recursive function with new position
  }
  return R((o-1)*o/2-1) // start recursive search with initial position at grid center
  .join('') // array to string
}

```

**Test** In Firefox/FireBug console

```
s='<^^^^^^^^\n\
<<^^^^^^>\n\
<<<^^^^>>\n\
<<<<^^>>>\n\
<<<<^>>>>\n\
<<<vv>>>>\n\
<<vvvv>>>\n\
<vvvvvv>>\n\
vvvvvvvv>\n'
console.log(F(s))

```

*Output*

```
>>>>>>>>v
^>>>>>>vv
^^>>>>vvv
^^^>>vvvv
<<<<<vvvv
^^^^<<vvv
^^^<<<<vv
^^<<<<<<v
^<<<<<<<<

```
> 1 votes

---
Tags: code-golf, grid
---


# Question
Title: What golfing languages are better suited as an object for genetic programming?
I see GolfScript, Pyth, CJam and similar languages can make compex-ish algorithms in few bytes. This terseness makes think about genetic programming applications (using said languaes as the thing being mutated).

I assume that to make a good GP language, it should have following characteristics:

* Programs are typically short;
* Random bytes should have high change of being a well-formed program;
* Programs should compile and run fast;
* Typical programs should not fall into endless loop often, or such loops should be early-detectable in most cases;
* Contatenations, extraction of substrings, small modifications should often lead to something related to the original program;
* Program should be easy to put in a sandbox (i.e. should not crash the interpreter);
* Be turing-complete or near it.

How much languages typically used for golfing suit for genetic programming?

# Answer
I would be surprised if any golfing languages were appropriate for genetic programming. Pyth, at least, is very unlikely to form a valid program with random bytes, and I believe the same is true of most golfing languages. This, if nothing else, probably invalidates them as genetic programming languages.
> 1 votes

---
Tags: genetic-algorithms
---


title: Code Golf: Leibniz Series

text:
# Question
Title: Code Golf: Leibniz Series
This is the same question as Solve the CodeSprint4 Leibniz code golf challenge in Python in 66 characters. The variation is that I'm a C programmer. My code for the above question is:

```
#include <math.h>
main(){
int i,t,p;
scanf("%d",&t);
while(t--)
{
double s=1;
scanf("%d",&p);
for(i=1;i<p;++i)
s+=pow(-1,i)/(2*i+1);
printf("%.12lf\n",s);
}
}

```

Now I just need to know the places where I could reduce my code length.

# Answer
1. Do everything in one line.
2. Don't read number of test cases, scanf will return -1 on EOF
3. Don't include anything, `pow(-1,i)` can be replaced by `1-i%2*2`
4. Do the sum loop in reverse to save a variable.

Here is my 102 bytes code

```
main(n){gets(&n);for(double s;s=scanf("%d",&n)>0;printf("%.15f\n",s))while(--n)s+=(1-n%2*2)/(1.+2*n);}

```
> 4 votes

# Answer
Remove include and replace pow by check.
Use the fact that scanf returns number of read and saved fields.
Replace while via for.
Remove figure brackets.
Use %f in printf for double - only scanf needs %lf.

I didn't check if following code works fine, but even if smth is wrong, the correct result have to be somewhere near it:

```
main(){
int i,t,p;
double s;
for(scanf("%d",&t);t--;printf("%.12f\n",s))
for(s=i=scanf("%d",&p);i<p;++i)
s+=(i&1?-1:1)/(2.*i+1);
}

```

By the way, what about making all variables double instead of int?
> 1 votes

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


# Question
Title: Extract URI parts without using libraries
Given a URI like:

```
postgres://username:password@hostname:PORT/dbname

```

Extract it all into an array data-structure, like so:

```
['postgres', 'username', 'password', 'hostname', 'PORT', 'dbname']

```

More info: http://en.wikipedia.org/wiki/URI\_scheme#Generic\_syntax

### Rules

* No use of external libraries or web-services

### Scoring

* Your score will be the number of bytes in your code (whitespace not included) multiplied by your bonus. Initial bonus is 1.0.
* Concision is king (codegolf!)
* Use of regular expressions will increase your bonus by 0.50
* Use of internal libraries (that need explicit importing) will increase your bonus by 0.50
* Extra -0.8 bonus for getting query string also

# Answer
> 2 votes
# CJam, 15 bytes * 0.8 = 12

```
l":@?#"'/er'/%p

```

Reads the uri via STDIN. Updated to parse query string and fragments too.

**Code explanation**:

```
l                    "Read a line from STDIN";
 ":@?#"              "Put this string on stack";
       '/er          "Replace all occurrences of characters in above string by /";
           '/%       "Split on runs of /";
              p      "Print the array";

```

Try it online here

# Answer
> 0 votes
## APL, 24

```
 {⍵⊂⍨⍵∊⎕AV[∊65 17+¨⊂⍳26]}

```

Example:

```
 ]display {⍵⊂⍨⍵∊⎕AV[∊65 17+¨⊂⍳26]}'postgres://username:password@hostname:PORT/dbname'
┌→────────────────────────────────────────────────────────────┐
│ ┌→───────┐ ┌→───────┐ ┌→───────┐ ┌→───────┐ ┌→───┐ ┌→─────┐ │
│ │postgres│ │username│ │password│ │hostname│ │PORT│ │dbname│ │
│ └────────┘ └────────┘ └────────┘ └────────┘ └────┘ └──────┘ │
└∊────────────────────────────────────────────────────────────┘

```

Note: ⎕ML variable must be set to 3 in Dyalog APL

# Answer
> 0 votes
# Ruby, 43

```
%w[:// : @ /].map{|t|u.gsub! t,' '}
u.split

```

Since the OP doesn't specify how to take input and produce output, I'm assuming the URI is located in `u` as a `String`. There is no output; `u.split` returns an Array in the correct format (`["postgres", "username", "password", "hostname", "PORT", "dbname"]`).

The code itself is simple. Replace `"://"`, `":"`, `"@"` and `"/`" with a space, then split on whitespace.

# Answer
> -1 votes
## Python (characters: 207, score: 240)

```
reduce(list.__add__,reduce(list.__add__,map(lambda e: map(lambda i: i.split('/'),e),map(lambda j: j.split(':'),(lambda e:e[e.find('/')+2:].split('@'))('postgres://username:password@hostname:PORT/dbname')))))

```

### Expanded out

```
reduce(list.__add__,
       reduce(list.__add__,
              map(lambda e: map(lambda i: i.split('/'), e),
                  map(lambda elem: elem.split(':'),
                      (lambda e: e[e.find('//') + 2:].split('@'))(
                          'postgres://username:password@hostname:PORT/dbname'
                      )
                  )
              )
       )
)

```

Note: in real-cases use `from operator import add`

---
Tags: code-golf, string, restricted-source
---


title: Morra, the Noble Game of Kings

text:
# Question
Title: Morra, the Noble Game of Kings
# Background

The game of Morra is a simple game. In the "original" version, several players simultaneously throw out a number 0-5 with their hands while guessing the total sum of everyone's hands. The version I'll use here has been modified to increase the potential for non-trivial strategy, and it is described below:

* There are two players.
* Like in rock-paper-scissors, the players move simultaneously.
* Each turn, each player chooses a number 0-5 and also *guesses* their opponents choice of 0-5. This means that two numbers are output each turn. To clarify, both numbers output should be in the range 0-5, inclusive.
* If you guess your opponent's choice correctly but your opponent did not guess correctly, you win a certain number of points equal to the sum of the two numbers played. For example, if the numbers played were 3 and 5, a correct guess would be worth 8 points.
* If both or neither players guess correctly, no points are awarded.
* The person with the most points after 1000 rounds wins that game.

---

# The Tournament

The tournament will be done in a round-robin style and will be run by creating each possible pairing of contestant. For each victory, the contestant gains 2 victory points. Each tie results in 1 victory point. No victory points are gained for a loss.

Intuitively, the winner of the tournament shall be the contestant with the most victory points against others.

---

# How to Enter

There will be two methods of submitting bots to compete. The first, and much preferred method, is to implement a Java interface supplied by the controller. The second method is to write an independent program.

Let's cover the Java method first. The interface you will need to implement is `Player` and it defines two methods: `public String getName()` identifies your bot, and `public int[] getMove(String[] args)` takes `args` as an array of six strings, `mychoices myguesses myscore opponentchoices opponentguesses opponentscore`. An example is the following:

```
042 045 0 324 432 6

```

This means that I chose 0 on the first round and guessed that my opponent was going to throw a 0. My opponent threw a 3 and guessed I would throw a 4. In the third round, my opponent made the correct guess that I would throw a 2, meaning that he gains 2+4=6 points.

Your method will return an array of two integers, which are your choice and guess, respectively. An example is `{4,2}`for a choice of 4 and a guess of 2.

Here is an example of a complete Java bot written as a method. If you want, your submission only has to include what's going in the `getMove` method.

```
import java.util.Random;
/**
 * A simple example Morra bot to get you started.
 */
public class ExampleBot implements Player
{
    public String getName()
    {
        return "ExampleBot";
    }

    public int[] getMove(String [] args)
    {
        //easiest way I know to break down to create a move history
        //(just contains their throw history)
        char[] theirThrowsC = args[3].toCharArray();
        int[] theirThrows = new int[theirThrowsC.length];
        for(int i = 0; i < theirThrowsC.length; i++)
        {
            theirThrows[i] = Integer.parseInt(Character.toString(theirThrowsC[i]));
        }

        //get my score
        int myScore = Integer.parseInt(args[2]);

        Random r = new Random();
        int guess = r.nextInt(6);
        if(theirThrows.length > 0)
        {
            guess = theirThrows[theirThrows.length-1];
        }

        //throws a random number, guesses what they threw last
        return new int[] {r.nextInt(6),guess};
    }

    public static int otherMethod(int example) //you can write additional static methods
    {
        return 0;
    }
}

```

## As an Independent Program

I am currently limited in my support of additional languages. Besides Java, I can accept programs written in Python 3.4, Perl 5, or Ruby 2.1.5. If there is a language that several people seem to want, I'll do my best to add it.

The input to your program will be arguments on the command line. It could look like this:

```
perl awesomebot.plx 042 045 0 324 432 6

```

The output of your program should be your choice followed by your guess, each followed by whitespace.

Please include in your answer the exact command needed to run it. Keep in mind that I'm running Windows 8.1.

---

# Extra Rules

## Saving State and Timeouts

Your program will be allowed to create one text file in the local directory, where you can store information. This information will kept throughout the tournament but deleted afterwards. Give the file a name I can identify.

There is a time limit of 500 milliseconds for your code to respond. Failure to respond in the time limit (or giving an invalid move) will result in forfeiture of that particular match. Java submissions currently have a passive timeout (which I may upgrade to active), whereas non-Java submissions have an active timeout where their process is terminated after 500 milliseconds.

## More submission rules

* You are allowed multiple submissions, as long as they abide by the rules and don't tag-team.
* Each entry must be unique. You can't make an exact copy of another bot's logic in a different language.
* The bots cannot interact with each other (to form a team of any sort).
* You can't use the logic of the other bots inside of your bot to, say, identify your competitor and predict its actions. You can, of course, try to determine the strategy of your opponent.
* Don't attempt to mess with the controller, other contestants, or my computer. Don't connect to external information sources.

# The Controller

The current version of the controller is found here. It is written in Java 8. The "Tournament" file is the main controller, which also contains the list of competitors (if you want to host your own competitions).

---

# Leaderboard

I haven't really been able to update the leaderboard very often. I am rather busy this weekend. By "rather busy" I mean no access to a computer from 6:30 AM to 9:30 PM. Here are the scores after 5 runs. The "Echo" bot kept forfeiting for some reason (might be my fault, I haven't investigated yet).

```
  170 - Quinn and Valor
  158 - Historian
  142 - DeltaMax
  140 - MorraCowbell
  132 - Extrapolator
  115 - Rainbolt
  102 - Popularity
  100 - Interpolator
   83 - CounterBot
   80 - Basilisk
   76 - Erratica
   65 - Trendy
   63 - Scholar
   62 - RandomGuesser
   60 - KingFisher
   59 - NullifierBot
   55 - EvolvedBot
   48 - Confused

```

---

# Credit

Many thanks to Rainbolt and Peter Taylor for their help with the controller.

# Answer
## Morra Cowbell

For anyone looking for significance in the name of this bot, the name *Morra* makes me think of Space Italian, so I reckoned I needed a name which played on that. Other candidates included *Morra fool you* and *Morra for me*.

This is a full class implementing the `Player` interface. Explanation below.

```
import java.util.Random;

public class MorraCowbell implements Player {
    private final Random rnd = new Random();

    public String getName() {
        return "MorraCowbell";
    }

    public int[] getMove(String[] args) {
        int[] prior = new int[36];
        for (int i = 0; i < 36; i++) prior[i] = 1;
        // args: myChoices myGuesses myScore opponentChoices opponentGuesses opponentScore
        if (args.length == 6 && args[3].length() == args[4].length()) {
            for (int i = 0; i < args[3].length(); i++) prior[6*(args[3].charAt(i) - '0') + (args[4].charAt(i) - '0')]++;
        }

        int[] weights = new int[6];
        for (int r = 0; r < 6; r++) {
            for (int s = 0; s < 6; s++) {
                for (int t = 0; t < 6; t++) {
                    weights[r] += (r + s) * ((r + s == 5 ? 1 : 0) + (r == t ? -1 : 0)) * prior[s * 6 + t];
                }
            }
        }

        // Find the best window.
        int[][] magic = new int[][] {
            { 7776, 6480, 5400, 4500, 3750, 3125 }, { 3125, 2500, 2000, 1600, 1280, 1024 }, { 1875, 1500, 1200, 960,
            768, 640 }, { 1125, 900, 720, 576, 480, 400 }, { 1620, 1296, 1080, 900, 750, 625 }, { 1296, 1080, 900, 750,
            625, 500 }, { 750, 625, 500, 400, 320, 256 }, { 675, 540, 432, 360, 300, 250 }, { 648, 540, 450, 375, 300,
            250 }, { 375, 300, 250, 200, 160, 128 }, { 375, 300, 240, 200, 160, 128 }, { 450, 375, 300, 240, 192, 160,
            128 }, { 324, 270, 225, 180, 150, 125 }, { 270, 225, 180, 144, 120, 100, 80 }, { 225, 180, 150, 120, 96,
            80 }, { 225, 180, 144, 120, 96, 80 }, { 324, 270, 216, 180, 150, 125, 100, 80, 64 }, { 135, 108, 90, 72, 60,
            50 }, { 135, 108, 90, 75, 60, 50, 40, 32 }, { 108, 90, 75, 60, 48, 40, 32 }, { 54, 45, 36, 30, 25, 20, 16 },
            { 54, 45, 36, 30, 24, 20, 16 }
        };
        long bestN = 0;
        int bestD = 1, bestIdx = -1, bestA[] = null;
        for (int[] A : magic) {
            for (int i = 0; i < A.length - 5; i++) {
                long n = 0;
                int d = 0;
                for (int j = 0; j < 6; j++) {
                    n += weights[j] * A[i + j];
                    d += A[i + j];
                }
                if (n * bestD > bestN * d) {
                    bestN = n;
                    bestD = d;
                    bestIdx = i;
                    bestA = A;
                }
            }
        }

        int r = rnd.nextInt(bestD);
        for (int i = 0; i < 6; i++) {
            r -= bestA[bestIdx + i];
            if (r < 0) return new int[] { i, 5 - i };
        }

        // Just a precaution: this should be unreachable.
        return new int[] { 0, 5 };
    }
}

```

### Explanation

I started by analysing games with fewer fingers. The simplest non-trivial one allows calls of `0` or `1` and has the following payoff table (values are payoff for the row player):

```
       (0,0) (0,1) (1,0) (1,1)
      +-----------------------
(0,0) |  0     0    -1     0
(0,1) |  0     0     0     1
(1,0) |  1     0     0    -1
(1,1) |  0    -1     1     0

```

The `(0,0)` strategy is dominated by `(0,1)`, so we can reduce the table to

```
       (0,1) (1,0) (1,1)
      +-----------------
(0,1) |  0     0     1
(1,0) |  0     0    -1
(1,1) | -1     1     0

```

Now the `(1,0)` strategy is dominated by `(0,1)`, so we can further reduce the table to

```
       (0,1) (1,1)
      +-----------
(0,1) |  0     1
(1,1) | -1     0

```

And now `(1,1)` is dominated by `(0,1)`, so we end up with

```
       (0,1)
      +-----
(0,1) |  0

```

Therefore always playing `(0,1)` is a Nash equilibrium. But the curious thing is that it's not the only one. This is a symmetric zero-sum game, so the expected payoff is 0, and any mixed strategy combining `(0,1)` and `(1,0)` where `(0,1)` is picked at least 50% of the time achieves that payoff. So we have a one-dimensional space of Nash equilibria.

It seems to be the case, although I haven't proven it, that `n`-finger Morra has an `n`-dimensional polytope of Nash equilibria which are mixed strategies between the `n+1` `(pick, guess)` pairs for which `pick + guess = n`.

The magic numbers in the code above encode the 32 vertices of the 5-dimensional polytope of Nash equilibria. I found them by setting up a linear programming instance which represented the polytope and then using random objective functions. The reason for encoding all 32 rather than picking one is simple: the expected payoff is 0, so I need to do better than expected to get a win. I essentially assume that the other player is using a mixed strategy and estimate the distribution based on their pick history. Then I select the polytope vertex which maximises my expected gain against that estimated distribution.

QuinnAndValor demonstrates the vulnerability of the assumption that the other player is using a mixed strategy. By detecting a player which uses the strategies from the Nash equilibria it is able to switch into a random walk mode where, playing a non-equilibrium strategy, it is liable on average to lose, but it only needs to gain a lead once and then it can revert to playing pairs for which `pick + guess = n`. So the Nash equilibria for a single game don't generalise trivially to Nash equilibria for the repeated game, which allows more complex strategies.
> 18 votes

# Answer
# Quinn and Valor (Updated)

Quinn and Valor are an elite ranger team. With crossbow and claw, they rip apart every opponent dares to challenge them.

```
import java.util.ArrayList;
import java.util.List;

interface Champion extends Player {
}

/*
 * Quinn and Valor are an elite ranger team. With crossbow and claw, they ...
 */
public class QuinnAndValor implements Champion {

    private final Champion quinn = new Quinn();
    private final Champion valor = new Valor();

    private int checker;
    private int myScore, opScore;
    private boolean ulted;
    private boolean teemoDetected;
    private boolean quinnNeverLose, valorNeverLose;
    private int quinnScore, valorScore;
    private int quinnRound, valorRound;

    public QuinnAndValor() {
        checker = check() ? 0 : 1;
    }

    // Check if is a fine use
    private static boolean check() {
        return Thread.currentThread().getStackTrace()[3].getClassName().equals(
                "Tournament");
    }

    @Override
    public String getName() {
        return quinn + " and " + valor;
    }

    @Override
    public int[] getMove(String[] args) {
        // Punish for bad usage
        switch (checker) {
        case 1:
            checker++;
            return new int[] { -1, -1 };
        case 2:
            checker++;
            return null;
        case 3:
            throw new Error("Mua he he heh!");
        default:
            if (checker > 0)
                throw new Error("Mua he he heh!");
            break;
        }

        int round = args[0].length();
        if (round == 0) {
            // Buy starting items
            myScore = opScore = 0;
            teemoDetected = false;
            quinnNeverLose = valorNeverLose = true;
            quinnScore = valorScore = quinnRound = valorRound = 0;
            ((Valor) valor).reset();
        }

        if (ulted = useUltimate(args)) {
            valorRound++;
            return valor.getMove(args);
        } else {
            quinnRound++;
            return quinn.getMove(args);
        }
    }

    /*
     * Quinn's ultimate has a lengthy cool-down, especially at lower ranks, so
     * we have to use it only when needed.
     */
    private boolean useUltimate(String[] args) {
        int round = args[0].length();
        int lastMyScore = myScore;
        int lastOpScore = opScore;
        myScore = Integer.parseInt(args[2]);
        opScore = Integer.parseInt(args[5]);
        int score = (myScore - opScore) - (lastMyScore - lastOpScore);
        if (ulted) {
            valorScore += score;
            valorNeverLose &= score >= 0;
        } else {
            quinnScore += score;
            quinnNeverLose &= score >= 0;
        }

        if (round < 100) {
            // Haven't hit level 6 yet
            return false;
        }

        if (myScore > opScore) {
            // We're already winning. Press on with strategy impossible to lose
            if (quinnNeverLose && quinnRound >= 50)
                return false;
            if (valorNeverLose && valorRound >= 50)
                return true;
        } else if (myScore < opScore) {
            // Although Quinn can blind others to counter them, she can be
            // counter be Teemo who also has blind! Don't fall for this!
            if (!teemoDetected) {
                teemoDetected = true;
                for (int i = round - 20; i < round; i++)
                    if (args[3].charAt(i) + args[4].charAt(i) != 'e')
                        teemoDetected = false;
            }
            if (teemoDetected)
                return true;
        }

        if (valorRound < 100) {
            // If we never use our ultimate, how can we know how strong it is?
            return true;
        }

        if (quinnScore < 0 && valorScore < 0)
            return valorRound < quinnRound;
        else
            return quinnScore * valorRound < valorScore * quinnRound;
    }

    @Override
    public String toString() {
        return getName();
    }

    /*
     * Quinn is a female Demacian elite ranger.
     *
     * @see Valor
     */
    public static class Quinn implements Champion {
        @Override
        public String getName() {
            return "Quinn";
        }

        /*
         * Magic!
         */
        @Override
        public int[] getMove(String[] args) {
            int t = (int) ((Math.sqrt(Math.random() * 168 + 1) - 1) / 2);
            return new int[] { 5 - t, t };
        }

        @Override
        public String toString() {
            return getName();
        }
    }

    /*
     * Valor is Quinn's Demacian eagle.
     *
     * @see Quinn
     */
    public static class Valor implements Champion {
        @Override
        public String getName() {
            return "Valor";
        }

        private int lastRound;
        private double[][] c;

        public void reset() {
            lastRound = 0;
            c = new double[6][6];
        }

        /*
         * Magic!
         */
        @Override
        public int[] getMove(String[] args) {
            int round = args[0].length();
            int[] b = new int[6];
            for (int i = round - 12; i < round; i++)
                b[args[0].charAt(i) - '0']++;
            {
                double deWeight = Math.pow(0.95, round - lastRound);
                for (int i = 0; i < 6; i++)
                    for (int j = 0; j < 6; j++)
                        c[i][j] *= deWeight;
                double weight = 1;
                for (int i = round - 1; i >= lastRound; i--) {
                    c[args[3].charAt(i) - '0'][args[4].charAt(i) - '0'] += weight;
                    weight *= 0.95;
                }
            }
            lastRound = round;

            List<int[]> pq = new ArrayList<>(1);
            double e = Integer.MIN_VALUE;
            for (int i = 0; i < 6; i++)
                for (int j = 0; j < 6; j++) {
                    double f = 0;
                    for (int k = 0; k < 6; k++)
                        f += (i + j) * c[j][k];
                    for (int k = 0; k < 6; k++)
                        f -= (i + k) * c[k][i];
                    // recently played moves are dangerous
                    f -= b[i] * b[i] * ((round + 11) / 12);
                    if (f >= e) {
                        if (f > e) {
                            pq.clear();
                            e = f;
                        }
                        pq.add(new int[] { i, j });
                    }
                }
            return pq.get((int) (Math.random() * pq.size()));
        }

        @Override
        public String toString() {
            return getName();
        }
    }
}

```

They almost always win against all Java solution on my machine.

## Edit:

I admit Quinn and Valor failed to duel Historian, but I still have good faith in them to win the tournament.

My principle is, for any solution with `choice + guess == 5`, also playing with `choice + guess == 5` grantees keeping your advantage.

## Update:

Well... everything just got complicated.
> 11 votes

# Answer
# Scholar

Scholar tries to learn from the moves of its opponent, choosing the one his opponene less guessed and guessing the one his opponent most used. But theory isn't everything, so Scholar doesn't do very well...

```
import java.util.HashMap;

public class Scholar implements Player
{
    public static int[] pm = new int[6];
    public static int[] pg = new int[6];
    public static HashMap<Integer, Integer> lm = new HashMap<>();
    public static HashMap<Integer, Integer> lg = new HashMap<>();

    public String getName()
    {
        return "Scholar";
    }

    public int[] getMove(String[] a)
    {
        int r = a[0].length();
        for (int i = 0; i < 6; i++) { pm[i]=0; pg[i]=0; }
        for (int i = 0; i < a[3].length(); i++) {
            int m = Integer.parseInt(String.valueOf(a[4].charAt(i)));
            int g = Integer.parseInt(String.valueOf(a[3].charAt(i)));
            pm[m]++; pg[g]++;
        }
        for (int i = 0; i < pm.length; i++) { lm.put(i, pm[i]); lg.put(i, pg[i]); }

        if (r < 1) {
            return new int[] { 3, 3 };
        } else {

            int mm = lm.entrySet().stream().min((x, y) -> x.getValue() > y.getValue() ? 1 : -1).get().getKey();
            int mg = lg.entrySet().stream().max((x, y) -> x.getValue() > y.getValue() ? 1 : -1).get().getKey();
            return new int[] { mm, mg };
        }
    }
}

```
> 6 votes

# Answer
# Historian

*(Updated: same logic, shorter code and **100 times faster** but you can use only one Historian bot at a tournament.)*

Uses weighted random to choose a throw-guess pair based on the effectiveness of using only that pair against opponents previous history. The weights are the squares ot the achievable scores.

```
public class Historian implements Player {
    private static java.util.Random r = new java.util.Random();
    private static int[] sc=new int[36]; //reseted between games, use only one Historian bot
    public String getName() {return "Historian";}
    public int[] getMove(String [] a) {
        if (a[3].length()==0)  {sc=new int[36]; for(int i=0;i<6;i++) sc[i*6+(5-i)]=5-i;}
        else {int t=a[3].charAt(a[3].length()-1)-'0'; int g=a[4].charAt(a[3].length()-1)-'0';
            for(int i=0; i<6; i++) {sc[i*6+t]+=i+t; sc[g*6+i]-=t+g;}}
        int sum=0; for(int i=0; i<36; i++) {sum+=(sc[i]<1)?1:sc[i]*sc[i];}
        int seed=r.nextInt(sum);int mt=-1;
        while (seed>=0) {seed-=(sc[++mt]<1)?1:sc[mt]*sc[mt];}
        return new int[] {(int)(mt/6),mt%6};} }

```

Beats `Quinn and Valor` *(not anymore)* and loses to `Morra Cowbell`. In the tournament with most of the bots `Historian` comes second to `Quinn and Valor`.
> 6 votes

# Answer
# DeltaMax

*(Updated to not use files and added a new section. Also modified to no longer get stuck tying in the first section.)*

Consists of a couple of strategies which start simple then get more complex — if you clear one, it moves you to the next section.

* **Section 1:** Guess `{0, 5}` consistently
* **Section 2:** Check if your last 4 guesses form a constant, linear or quadratic pattern and keep guessing the pattern until it breaks
* **Section 3:** Check if you guess an abnormally low amount of some number (less than 1/13) and choose that number
* **Section 4:** Analyse bigrams in your choices and look at what's more likely to come out next
* **Section 5:** Look at the past 100 rounds and pick the `(choice, guess)` pair which would have the best expectation, weighted so that recent rounds are more important
* **Section final:** Guess randomly, with higher likelihood of having low choices and high guesses. If you get here, then DeltaMax has given up and would like to say, "good game".

To find out which strat was used in the end, uncomment the

```
if (myChoices.length == 999) { System.out.println(strat); }

```

line.

Apologies for the horrid Java, I spent my afternoon piecing bits together and relearning the language :)

```
import java.io.*;
import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

public class DeltaMax implements Player
{
    private int strat = 100;

    public String getName() { return "DeltaMax"; }

    public int[] toInts(String s) {
        char [] chars = s.toCharArray();
        int[] ints = new int[chars.length];

        for (int i = 0; i < chars.length; i++){
            ints[i] = Integer.parseInt(Character.toString(chars[i]));
        }

        return ints;
    }

    public int mod6(int n) {
        n = n % 6;
        if (n < 0) { n += 6; }
        return n;
    }

    public int[] getMove(String [] args)
    {
       int[] myChoices = toInts(args[0]);
       int[] myGuesses = toInts(args[1]);
       int myScore = Integer.parseInt(args[2]);
       int[] opponentChoices = toInts(args[3]);
       int[] opponentGuesses = toInts(args[4]);
       int opponentScore = Integer.parseInt(args[5]);

       int rounds = myChoices.length;

       if (rounds == 0) { strat = 100; }
       Random r = new Random();

       // if (myChoices.length == 999) { System.out.println(strat); }

       if (strat == 100) { // Section 1 - {0, 5}
           if (opponentScore - myScore > 21 || (opponentScore >= myScore && rounds > 100)) {
               strat = 200;
           } else {
               return new int[] {0, 5};
           }
       }

       if (strat == 200) { // Section 2 - Mini interpolator
           int w = opponentChoices[opponentChoices.length - 4];
           int x = opponentChoices[opponentChoices.length - 3];
           int y = opponentChoices[opponentChoices.length - 2];
           int z = opponentChoices[opponentChoices.length - 1];

           if (w == x && x == y && y == z) { // Constant
               return new int[] { r.nextInt(4) + 2, w };
           }

           if (mod6(x-w) == mod6(y-x) && mod6(y-x) == mod6(z-y)) { // Linear
               return new int[] { r.nextInt(4) + 2, mod6(z + (z-y)) };
           }

           if (mod6((y-x) - (x-w)) == mod6((z-y) - (y-x))) { // Quadratic
               return new int[] { r.nextInt(4) + 2, mod6((z-y) + mod6((y-x) - (x-w))) };
           }

           strat = 300;
       }

       if (strat == 300) { // Section 3 - exploit least guessed
           int [] counts = new int[6];

           for (int i = 0; i < rounds; i++) {
               counts[opponentGuesses[i]] += 1;
           }

           int minCount = rounds;

           for (int i = 0; i < 6; i++) {
               if ((counts[i] <= 1 || counts[i] * 13 < rounds) && counts[i] < minCount) {
                   minCount = counts[i];
               }
           }

           if (minCount == rounds) {
               strat = 400;
           } else {
               ArrayList<Integer> choices = new ArrayList<Integer>();

               for (int i = 0; i < 6; i++) {
                   if (counts[i] == minCount) {
                       choices.add((Integer) i);
                   }
               }

               int choice = choices.get(r.nextInt(choices.size()));

               // {0, 0} is about the worst thing you can do, so DeltaMax tries to avoid that
               if (choice == 0) {
                   return new int[] { 0, r.nextInt(4) + 2 };
               } else {
                   return new int[] { choice, r.nextInt(6) };
               }
           }
       }

       if (strat == 400) { // Section 4 - bigrams
           if (opponentScore - myScore > 42 || (opponentScore >= myScore && rounds > 300)){
               strat = 500;
           } else {
               int[] opponentScores = new int[6];
               int opponentLast = opponentChoices[opponentChoices.length - 1];

               int[] myScores = new int[6];
               int myLast = myChoices[myChoices.length - 1];

               for (int i = 0; i < opponentChoices.length - 1; i++) {
                   if (opponentChoices[i] == opponentLast) {
                       opponentScores[opponentChoices[i+1]] += 1;
                   }

                   if (myChoices[i] == myLast) {
                       myScores[myChoices[i+1]] += 1;
                   }
               }

               int maxIndex = -1;
               int maxScore = 0;

               int minIndex = -1;
               int minScore = rounds;

               for (int i = 0; i < 6; i++) {
                   if (opponentScores[i] >= maxScore) {
                       maxScore = opponentScores[i];
                       maxIndex = i;
                   }

                   if (myScores[i] <= minScore) {
                       minScore = myScores[i];
                       minIndex = i;
                   }
               }

               if (minIndex == 0 && maxIndex == 0) {
                   return new int[] { 0, r.nextInt(4) + 2 };
               } else {
                   return new int[] { minIndex, maxIndex };
               }
           }
       }

       if (strat == 500) { // Section 5 - best expectation
           if (opponentScore - myScore > 84 || (opponentScore >= myScore && rounds > 800)){
               strat = 573;
           } else {
               int minLen = Math.min(rounds, 100);

               double bestScore = 0;
               int bestGuess = 0;
               int bestChoice = 5;

               for (int guess = 0; guess < 6; guess++) {
                   for (int choice = 0; choice < 6; choice++) {
                       double score = 0;
                       int start = rounds - minLen;

                       for (int i = start; i < rounds; i++) {
                           if (opponentGuesses[i] == choice && opponentChoices[i] != guess) {
                               score -= (choice + opponentChoices[i]) * ((double) i - start) / minLen;
                           } else if (opponentGuesses[i] != choice && opponentChoices[i] == guess) {
                               score += (choice + opponentChoices[i]) * ((double) i - start) / minLen;
                           }
                       }

                       if (score > bestScore) {
                           bestScore = score;
                           bestGuess = guess;
                           bestChoice = choice;
                       }
                   }
               }

               if (bestChoice == 0 && bestGuess == 0) {
                   return new int[] { r.nextInt(4) + 2, bestGuess };
               } else {
                   return new int[] {bestChoice, bestGuess};
               }
           }
       }

       // Section final - hope for the best
       int num = (int) Math.floor(Math.sqrt(r.nextInt(35)));
       return new int[] {5 - num, num};
    }
}

```
> 6 votes

# Answer
# Extrapolator (v1.1)

Extreme extrapolation from one of the Nash-equilibriums of a simpler game.

I support the terse answer format! (In python-style.)

```
public class Extrapolator implements Player {
    private static java.util.Random r = new java.util.Random();
    public String getName() { return "Extrapolator"; }
    public int[] getMove(String [] args) {
        int t=-1;
        for(int c=15,s=r.nextInt(60);s>=0;s-=c,c-=2,t++);
        return new int[] {t,5-t}; } }

```

Seems to tie with the Magic Cow (Morra Cowbell) and beats other entries I checked.
> 5 votes

# Answer
# Trendy

Trendy takes a look at the opponent's past moves, weighting them by recency. Guesses the weightiest, and picks one shifted up slightly from that. Here it is, in all its glory:

```
public class Trendy implements Player{public String getName(){return "Trendy";}public int[]getMove(String[]a){float h=0,c[]=new float[6];int i=0,l=a[3].length(),p=0;for(;i<l;)c[a[3].charAt(i++)-48]+=(float)i/l;for(i=0;i<6;i++)if(c[i]>h)h=c[p=i];return new int[]{(p+2)%6,p};}}

```

The only thing I can compare it with now is Cowbell. It loses by a small margin the majority of the time, but comes out on top often enough for my liking. We'll see how it does with more competitors.
> 4 votes

# Answer
## Random Guesser

This is really straight-forward. It effectively rolls a d6, and adds another roll to the previous roll for its guess. It won't win, but it'll provide a nice benchmark.

```
import java.util.Random;

public class RandomGuesser implements Player {
    private final Random rnd = new Random();
    public String getName() { return "RandomGuesser"; }

    public int[] getMove(String[] args) {
        return new int[] { rnd.nextInt(6), rnd.nextInt(6) };
    }
}

```
> 4 votes

# Answer
# Rainbolt

Takes the difference between the last two numbers our opponent guessed, adds that to our opponent's latest guess, finds the modulus, and avoids choosing that number at all costs. For example, if you guess {5,4,3} (decreasing by one) then we would avoid choosing 2 at all costs.

Takes the difference between the last two numbers our opponent chose, adds that to our opponent's latest choice, and guesses that number. For example, if you guess {1,4,5,2} (increasing by threes) then we would guess 5.

Avoids pointless or very close to pointless rolls.

```
public class Rainbolt implements Player {

    public String getName() {
        return "Rainbolt";
    }

    public int[] getMove(String[] args) {
        int[] yourChoices = toIntArray(args[3]);
        int[] yourGuesses = toIntArray(args[4]);

        int myChoice;
        if (yourGuesses.length > 1) {
            int latest = yourGuesses[yourGuesses.length - 1];
            int secondLatest = yourGuesses[yourGuesses.length - 2];
            int numberToAvoid = (2 * latest - secondLatest + 6) % 6;
            do {
                myChoice = rollRandom();
            } while (myChoice == numberToAvoid);
        } else {
            myChoice = rollRandom();
        }

        int myGuess;
        if (yourChoices.length > 1) {
            int latest = yourChoices[yourChoices.length - 1];
            int secondLatest = yourChoices[yourChoices.length - 2];
            myGuess = (2 * latest - secondLatest + 6) % 6;
        } else {
            myGuess = rollRandom();
        }

        if ((myChoice + myGuess) < 3) {
            do {
                myGuess = rollRandom();
            } while ((myChoice + myGuess) < 3);
        }

        return new int[] { myChoice, myGuess };
    }

    private static int[] toIntArray(String arg) {
        int[] result = new int[arg.length()];
        for (int i = 0; i < arg.length(); i++)
            result[i] = Character.getNumericValue(arg.charAt(i));
        return result;
    }

    private static int rollRandom() {
        return (int) (Math.random() * 6);
    }
}

```
> 4 votes

# Answer
# Confused, Python 3

An unnecessarily complicated entry. Even I don't know what it does.

```
import sys
from random import *

if len(sys.argv) == 7:
    mn,mg,ms,on,og,os = [list(map(int, v)) for v in sys.argv[1:]]
    s,t = sum(mn+on)%5, sum(mg+og)%5
    n = [0]*3+list(range(6))*5+[5,0,5]
    m = [1,0,5,4]+n[:-2:s//9+1]
    numoptions = [n.extend(n[i+s::5+t]+[i]*i*(6+t)) for i in n[:]] and n
    guessoptions = [m.extend(m[i+t//2::8]+[i]*i*(5+s)) for i in m[:]] and m
    num = choice(numoptions)
    guess = choice(guessoptions)
else:
    num, guess = randint(0, 5), randint(0, 5)

sys.stdout.write('%u %u\n' % (num, guess))

```

Although this advanced algorithm seems to perform worse than random in this tournament, and uses significant memory and run-time, it has stunning results for certain values of 5 ;-)
> 4 votes

# Answer
# CounterBot

Does not *counter* anyone but rather counts through 0-5 in a circle (`0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4 ...`)

```
import java.util.Random;

public class Counter implements Player {

    int lastChoice = new Random().nextInt(6); //Chooses a random starting number

    public String getName() {
        return "CounterBot";
    }

    public int[] getMove(String[] args) {
        int[] oChoices = new int[6]; //Array to store the amount of individual choices of the opponent

        for (int i = 0; i < args[3].length(); i++) {
            int index = Integer.parseInt(String.valueOf(args[3].charAt(i))); //get that choice
            oChoices[index]++; //Increment the number corresponding the choice
        }
        int guess = 0, last = 0;
        for (int i = 0; i < oChoices.length; i++) { //Increment over the choices' array
            if (oChoices[i] > last) { //If the number has been chosen more often than the one before
                last = oChoices[i]; //Set the new maximum value (later the last maximum value)
                guess = i; //Set it as the next guess
            }
        }
        lastChoice++; //Increment our choice
        lastChoice %= 6; //Make sure it's within the bounds of 0-5 ie. modulo 6 (6 modulo 6 = 0)
        return new int[]{lastChoice, guess}; //return our choice and guess
    }
}

```
> 3 votes

# Answer
# Evolved Bot

I evolved this bot to be the best random based bot.

```
import java.util.Arrays;

public class EvolvedBot implements Player {

    private static final double MUTATION_RATE = .2;
    private static final double CROSS_OVER_RATE = .5;

    private final double[] pickProbabilities;
    private final double pickSum;
    private final double[] guessProbabilities;
    private final double guessSum;

    public EvolvedBot(){
        this(new double[]{1.0069058661897903, 0.8949716031797937, 0.5249198534098369, 0.437811964976626, 0.2630925750209125, 0.4862172884617061},
                new double[]{0.6336558074769376, 0.13700756148363913, 0.9586621925124863, 0.11223159366330251, 0.8931390659502754, 0.662974949440039});
    }

    public EvolvedBot(double[] pickProbabilities, double[] guessProbabilities) {
        this.pickProbabilities = pickProbabilities;
        this.guessProbabilities = guessProbabilities;
        pickSum = Arrays.stream(pickProbabilities).sum();
        guessSum = Arrays.stream(guessProbabilities).sum();
    }

    @Override
    public String getName() {
        return "EvolvedBot"/* + ": " + Arrays.toString(pickProbabilities) + Arrays.toString(guessProbabilities)*/;
    }

    @Override
    public int[] getMove(String[] args) {
        int[] move = new int[]{5, 5};
        double pick = Math.random() * pickSum;
        double guess = Math.random() * guessSum;
        for (int i = 0; i < 6; i++){
            if (pick >= 0) {
                pick -= pickProbabilities[i];
                if (pick < 0) {
                    move[0] = i;
                }
            }
            if (guess >= 0){
                guess -= guessProbabilities[i];
                if (guess < 0){
                    move[1] = i;
                }
            }
        }
        return move;
    }

    public EvolvedBot mutate(double mutationRate){
        double[] pickProbabilities = Arrays.copyOf(this.pickProbabilities, 6);
        double[] guessProbabilities = Arrays.copyOf(this.guessProbabilities, 6);

        for (int i = 0; i < 6; i++){
            pickProbabilities[i] = Math.max(pickProbabilities[i] + (Math.random() * 2 - 1) * mutationRate, 0);
        }

        for (int i = 0; i < 6; i++){
            guessProbabilities[i] = Math.max(guessProbabilities[i] + (Math.random() * 2 - 1) * mutationRate, 0);
        }

        return new EvolvedBot(pickProbabilities, guessProbabilities);
    }

}

```
> 3 votes

# Answer
# Interpolator

*(Switched to Java since Python was causing problems)*

Uses polynomial interpolation on the last 10 opponent choices to work out the opponent's next number, then does the same to its own choices and *avoids* choosing that number. Also, Interpolator has a slight bias against choosing 0 or 5, and its choice is sometimes affected by its guess:

* If it guesses 0 it will never choose 0
* If it guesses 5 it will always choose 0 or 1

```
import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class Interpolator implements Player
{
    private final int TAIL_LENGTH = 10;

    public String getName()
    {
        return "Interpolator";
    }

    public int[] toInts(String s) {
        char [] chars = s.toCharArray();
        int[] ints = new int[chars.length];

        for (int i = 0; i < chars.length; i++){
            ints[i] = Integer.parseInt(Character.toString(chars[i]));
        }

        return ints;
    }

    public int mod6(int n) {
        n = n % 6;
        if (n < 0) { n += 6; }
        return n;
    }

    public int interpolate(int[] nums){
        boolean allEqual = true;

        for (int i = 0; i < nums.length; i++){
            if (nums[i] != nums[0]){
                allEqual = false;
            }
        }

        if (allEqual) {
            return nums[0];

        } else {
            int [] newNums = new int[nums.length - 1];

            for (int i = 0; i < nums.length - 1; i++){
                newNums[i] = nums[i+1] - nums[i];
            }

            return nums[nums.length - 1] + interpolate(newNums);
        }
    }

    public int[] tail(int[] nums) {
        int minLength = Math.min(TAIL_LENGTH, nums.length);
        int[] tailArray = new int[minLength];

        for (int i = 0; i < minLength; i++){
            tailArray[i] = nums[nums.length - minLength + i];
        }

        return tailArray;
    }

    public int[] getMove(String [] args)
    {
        Random r = new Random();

        if (args[0].length() == 0){
            return new int[] {r.nextInt(5), r.nextInt(5)};
        }

        int[] myChoices = toInts(args[0]);
        int[] opponentChoices = toInts(args[3]);
        int[] opponentGuesses = toInts(args[4]);

        int guess = mod6(interpolate(tail(opponentChoices)));
        int avoid = mod6(interpolate(tail(myChoices)));

        if (guess == 5){ return new int[] {r.nextInt(2), 5}; }

        int[] choiceArray = {0, 1, 1, 2, 2, 3, 3, 4, 4, 5};
        ArrayList<Integer> choices = new ArrayList<Integer>();
        for (int i = 0; i < choiceArray.length; i++) { choices.add(choiceArray[i]); }

        choices.removeAll(Collections.singleton((Integer) avoid));
        if (guess <= 0) { choices.removeAll(Collections.singleton((Integer) 0)); }
        int choice = choices.get(r.nextInt(choices.size()));

        return new int[] {choice, guess};
    }
}

```
> 3 votes

# Answer
# Popularity, Python 3

Compute guess based on popular numbers used in the past by the opponent. The numbers used recently have more weight. The number choice is often the same as the guess.

```
import sys
from random import *

if len(sys.argv) == 7:
    mn,mg,ms,on,og,os = [list(map(int, v)) for v in sys.argv[1:]]
    n = list(range(6))
    guess = choice(n + on[-100:] + on[-20:]*8)
    num = choice(n + [guess]*6)
else:
    num, guess = randint(0, 5), randint(0, 5)

sys.stdout.write('%u %u\n' % (num, guess))

```
> 3 votes

# Answer
# Basilisk, Python

According to legend, The Basilisk is the king of the serpents. (source) I figured that's an appropriate name for a bot that plays "The Noble Game Of Kings" and is written in python. =D This bot strikes fear into the heart of the other bots, and causes death with a single glance.

```
import sys
import random

args = sys.argv
argc = len(args)
if argc < 6:
    sys.exit()

myChoices = args[1]
myGuesses = args[2]
myScore = args[3]
opponentChoices = args[4]
opponentGuesses = args[5]
opponentScore = args[6]

if len(myChoices) == 0:
    print (random.randint(0, 5))
    print (random.randint(0, 5))
    sys.exit()

guesses = [0, 0, 0, 0, 0, 0]
for char in opponentGuesses:
    i = int(char)
    guesses[i] += 1

#Will default towards smaller guesses to minimize opponent winnings
#For example, if the guess list is
#[5, 3, 7, 3, 4, 8]
#This will return 1. (index of the first 3)
myNextMove = guesses.index(min(guesses))

list = [
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]]
i = 0

while i < len(myGuesses) - 1:
    myGuess = int(myGuesses[i])
    opponentResponse = int(opponentChoices[i+1])
    list[myGuess][opponentResponse] += 1
    i += 1

myPreviousGuess = int(myGuesses[-1])
relevantList = list[myPreviousGuess]

#Defaults towards higher moves.
#For example, if the list is
#[3, 8, 6, 8, 0, 7]
#This will return 3 (index of the last 8)
highestValue = -1
highestIndex = -1
for i in range(len(relevantList)):
    if relevantList[i] >= highestValue:
        highestValue = relevantList[i]
        highestIndex = i

myNextGuess = highestIndex

print (myNextMove)
print (myNextGuess)

```

This runs on a pretty simple strategy. I'm not expecting it to win, but it was fun to write. This is also my first KoTH challenge, so I'm excited to see how well it performs.

### How it picks its next move.

The Basilisk always makes the move that his opponent has guessed the least number of times. In case of a tie, he will pick the smaller number. (to minimize the opponents number of points.)

### How it picks its next guess.

The Basilisk will pick the most likely response to its previous guess. For example, If last time, it guessed a 3, it will go back through all of the previous times that it has guessed a 3, and then return the most common opponent move that comes after a guess of 3. In case of a tie, it will pick the larger number (to maximize the number of points it could make.)

On a technical note, will this run correctly? Is print() sufficient, or should I use something like sys.stdout.write() like the other Pythonistas have done?
> 2 votes

# Answer
## Ditto

This turns into the opponent, but behind by one guess/choice.

```
import java.util.Random;

public class Ditto implements Player {
    private final Random rnd = new Random();
    public String getName() { return "Ditto"; }

    // myChoices myGuesses myScore oppChoices oppGuesses oppScore
    public int[] getMove(String[] args) {
        if(args[0] == null || args[0].isEmpty()) {
            return new int[] { rnd.nextInt(6), rnd.nextInt(6) };
        }
        int[] myChoices = toIntArray(args[0]);
        int[] myGuesses = toIntArray(args[1]);
        //int myScore = Integer.parseInt(args[2]);
        int[] oppChoices = toIntArray(args[3]);
        int[] oppGuesses = toIntArray(args[4]);
        //int oppScore = Integer.parseInt(args[5]);

        return new int[] { oppChoices[oppChoices.length-1], oppGuesses[oppGuesses.length-1] };
    }

    private static int[] toIntArray(String arg) {
        int[] result = new int[arg.length()];
        for (int i = 0; i < arg.length(); i++)
            result[i] = Character.getNumericValue(arg.charAt(i));
        return result;
    }
}

```
> 2 votes

# Answer
## NullifierBot, Java

Always throws 0 to minimize any opponent winnings. If the opponent ever guesses my number, they only earn what they threw.

Always guesses 5 to maximize my winnings. Since I can't get any points from my throw, I want to get as many from the opponent. I could randomly guess, but where's the fun in that?

```
public class NullifierBot implements Player
{
    public String getName()
    {
        return "NullifierBot";
    }

    public int[] getMove(String [] args)
    {
        // always throws 0 to minimize opponents score
        // always guesses 5 to maximize my score
        return new int[] {0, 5};
    }
}

```
> 1 votes

# Answer
# Erratica, Java

Not great, but it was originally designed to be mostly random, until the value of the trade-off popped out at me. Manages to lose consistently vs. Counter Bot \>\_\<

```
import java.util.Random;
class Erratica implements Player
{
    private final Random rnd = new Random();

    public String getName() {
        return "Erratica";
    }

    public int[] getMove(String[] args) {
        if(args[0] == null || args[0].isEmpty())
        {
            return new int[]{rnd.nextInt(4)/3+4,rnd.nextInt(4)/3};
        }
        int[] myChoices = toIntArray(args[0]);
        int[] myGuesses = toIntArray(args[1]);
        int myScore = Integer.parseInt(args[2]);
        int[] opponentChoices = toIntArray(args[3]);
        int[] opponentGuesses = toIntArray(args[4]);
        int opponentScore = Integer.parseInt(args[5]);
        int round = opponentChoices.length + 1;
        int choice=0;
        int guess=0;
        if(round<7)
        {
            if(rnd.nextFloat()<(0.1f*(float)round-0.1f))
            {
                choice=(opponentChoices[round-2]+opponentGuesses[round-2])%6;
            }else
            {
                choice=rnd.nextInt(6);
            }
            if(rnd.nextFloat()<(0.1f*(float)round-0.1f))
            {
                guess=opponentChoices[round-2];
            }else
            {
                guess=rnd.nextInt(6);
            }
            return new int[]{choice, rnd.nextInt(6)/5*(5-choice-guess)+guess};
        }else
        {
            int lastError=Math.abs(opponentGuesses[round-2]-myChoices[round-2]);
            for(int i=round-2; i>round-8;i--)
            {
                if(lastError<rnd.nextInt(6))
                {
                    lastError++;
                }else
                {
                    lastError--;
                }
                if(lastError<0)
                    lastError+=6;

            }
            lastError = lastError%6; //shouldn't change
            switch(rnd.nextInt(4))
            {
                case 0:
                    choice=(myChoices[round-2-lastError-round/10])%6;
                    break;
                case 1:
                    choice=(myChoices[lastError+round/10])%6;
                    break;
                default:
                    choice = rnd.nextInt(6);
                    break;
            }

            lastError=Math.abs(myGuesses[round-2]-opponentChoices[round-2]);
            for(int i=round-2; i>round-8;i--)
            {
                if(lastError<rnd.nextInt(6))
                {
                    lastError++;
                }else
                {
                    lastError--;
                }
                if(lastError<0)
                    lastError+=6;
            }
            lastError = lastError%6; //shouldn't change
            switch(rnd.nextInt(4))
            {
                case 0:
                    guess=(opponentChoices[round-2-lastError-round/10])%6;
                    break;
                case 1:
                    guess=(opponentChoices[lastError+round/10])%6;
                    break;
                default:
                    guess = rnd.nextInt(4);
                    break;
            }
        }

        if(myScore>opponentScore)
            switch(rnd.nextInt(2)){
                case 0:
                    choice=5-guess;
                    break;
                case 1:
                    guess=5-choice;
                    break;
                default:
                    break;
            }
        return new int[]{choice, guess};
    }

    private static int[] toIntArray(String arg) {
        int[] result = new int[arg.length()];
        for (int i = 0; i < arg.length(); i++)
            result[i] = Character.getNumericValue(arg.charAt(i));
        return result;
    }
}

```
> 1 votes

# Answer
# Echo, Ruby

```
mychoices, myguesses, myscore, opponentchoices, opponentguesses, opponentscore = $*

unless mychoices
 puts "0 5"
 exit
end

if mychoices.size > 990 && myscore == '0'
  nextchoice = rand(1..5)
else
  nextchoice = opponentchoices[-1].to_i
end

recentchoices = opponentchoices[/.{0,100}$/]

nextguess = (0..5).max_by do |choice|
  (recentchoices.count(choice.to_s)+1) * (nextchoice + choice)
end

puts "%s %s"%[nextchoice,nextguess]

```

Plays the last play the opponent made, on the theory that anybody can make a bot that they cannot predict. Guesses based on expectation value using a hundred-move sample.
> 1 votes

# Answer
# KING FISHER

```
    import java.util.Random;
public class KingFisher {

    private Random rnd = new Random();
    private int wins = 0;
    private int loses = 0;
    private int median = 0;
    private int medianMoved = 0;
    private int[] weightedLow = {40,65,80,90,95};
    private int[] weightedHigh = {5,15,30,55,95};
    private boolean highWeightMethod = true;

    public String getName() {
        return "KingFisher";
    }

    public int[] getMove(String [] args)
    {
        char[] mc  = args[0].toCharArray();
        char[] mg  = args[1].toCharArray();
        char[] oc  = args[3].toCharArray();
        char[] og  = args[4].toCharArray();
        int len = mc.length;
        int currentGuess = 0;
        int currentChoice = 0;
        if(len < 10)
            return new int[] {rnd.nextInt(6),rnd.nextInt(6)};
        int[] guessWeight = {0,0,0,0,0,0};
        int[] guessWeightTotal = {0,0,0,0,0,0};
        for(int a = 0; a< len;a++)
            guessWeight[oc[a]-48]++;
        if(!highWeightMethod){

            int[] whiteList = {1,1,1,1,1,1};
            for(int b = 0;b<3;b++){

                int min = 0;
                int max = 0;
                int minIndex = 0;
                int maxIndex = 0;
                for(int a = 0;a<6;a++){

                    if(whiteList[a] == 1){

                        min = guessWeight[a];
                        max = guessWeight[a];
                        minIndex = a;
                        maxIndex = a;
                        break;
                    }
                }

                for(int a = 0; a<6;a++){

                    if(whiteList[a] == 1){

                        if(guessWeight[a]<min){

                            min = guessWeight[a];
                            minIndex = a;
                        }
                        if(guessWeight[a]>max){

                            max = guessWeight[a];
                            maxIndex = a;
                        }
                    }
                }
                guessWeight[maxIndex] = min;
                guessWeight[minIndex] = max;
                whiteList[maxIndex] = 0;
                whiteList[minIndex] = 0;
            }
        }

        for(int a = 0; a< 6;a++)
            for(int b = 0; b<=a;b++)
                guessWeightTotal[a]+=guessWeight[b];
        int randInt = rnd.nextInt(guessWeightTotal[5]);
        for(int a = 0; a<6;a++){

            if(randInt < guessWeightTotal[a]){
                currentGuess = a;
                break;
            }
        }

        if(mg[len-1] == oc[len-1]){
            wins++;
            median++;
        }
        if(og[len-1] == mc[len-1]){
            loses++;
            median--;
        }
        if(median > 2){

            medianMoved++;
            median = 0;
        }
        if(median < -2){

            medianMoved--;
            median = 0;
        }

        randInt = rnd.nextInt(95);
        if((wins-medianMoved)>(loses+medianMoved)){

            for(int a = 0; a<6;a++){

                if(randInt < weightedLow[a]){
                    currentChoice = a;
                    break;
                }
            }
        }
        else{

            for(int a = 0; a<6;a++){

                if(randInt < weightedHigh[a]){
                    currentChoice = a;
                    break;
                }
            }
        }
        if(medianMoved < -5){

            highWeightMethod = !highWeightMethod;
            medianMoved = 0;
        }
        return new int[] {currentChoice,currentGuess};

    }
}

```

This guy consist out of bad guessing alghorithms that use weighted arrays mostly.
> 1 votes

# Answer
Uh uh. I know what you're thinking. "Is he gonna pick five or something else?" Well to tell you the truth in all this excitement I'm kinda not sure myself, but being this is a .44 Method, the most powerful method in the world and would overload your stack right away, you've gotta ask yourself one question: "Do I feel lucky?"

Well, do ya, punk?

```
public class DirtyHarry implements Player {

    @Override
    public String getName() {
        return "DirtyHarry";
    }

    @Override
    public int[] getMove(String[] args) {
        return new int[]{5, 5};
    }
}

```
> 1 votes

---
Tags: game, king-of-the-hill
---