# Question
Title: Find highest scoring matrix without property X
This challenge is partly an algorithms challenge, partly an optimization challenge and partly simply a fastest code challenge.

A cyclic matrix is fully specified by its first row `r`. The remaining rows are each cyclic permutations of the row `r` with offset equal to the row index. We will allow cyclic matrices which are not square so that they are simply missing some of their last rows. We do however always assume that the number of rows is no more than the number of columns. For example, consider the following 3 by 5 cyclic matrix.

```
10111
11011
11101

```

We say a matrix has property X if it contains two non-empty sets of columns with non-identical indices which have the same (vector) sum. The vector sum of two columns is simply an element-wise summation of the two columns. That is the sum of two columns containing `x` elements each is another column containing `x` elements.

The matrix above trivially has property X as the first and last columns are the same. The identity matrix never has property X.

If we just remove the last column of the matrix above then we get an example which does not have property X and would give a score of 4/3.

```
1011
1101
1110

```

**The task**

The task is to write code to find the highest scoring cyclic matrix whose entries are all 0 or 1 and which *does not* have property X.

**Score**

Your score will be the number columns divided by the number of rows in your best scoring matrix.

**Tie Breaker**

If two answers have the same score, the one submitted first wins.

In the (very) unlikely event that someone finds a method to get unlimited scores, the first valid proof of such a solution will be accepted. In the even more unlikely event that you can find a proof of optimality of a finite matrix I will of course award the win too.

**Hint**

Getting a score of 12/8 is not too hard.

**Languages and libraries**

You can use any language which has a freely available compiler/interpreter/etc. for Linux and any libraries which are also freely available for Linux.

**Leading entries**

* 36/19 by Peter Taylor (Java)
* 32/17 by Suboptimus Prime (C#)
* 21/12 by justhalf (Python 2)

# Answer
## 16/9 20/11 22/12 28/15 30/16 32/17 34/18 36/19 (Java)

This uses a number of ideas to reduce the search space and cost. View the revision history for more details on earlier versions of the code.

* It's clear that wlog we can consider only circulant matrices in which the first row is a Lyndon word: if the word is non-prime then it must have property X, and otherwise we can rotate without affecting the score or property X.
* Based on heuristics from the observed short winners, I'm now iterating through the Lyndon words starting at the ones with 50% density (i.e. the same number of `0` and `1`) and working out; I use the algorithm described in *A Gray code for fixed-density necklaces and Lyndon words in constant amortized time*, Sawada and Williams, *Theoretical Computer Science* 502 (2013): 46-54.
* An empirical observation is that the values occur in pairs: each optimum Lyndon word that I've found scores the same as its reversal. So I get about a factor of two speedup by only considering one half of each such pair.
* My original code worked with `BigInteger` to give an exact test. I get a significant speed improvement, at the risk of false negatives, by operating modulo a large prime and keeping everything in primitives. The prime I've chosen is the largest one smaller than 257, as that allows multiplying by the base of my notional vector representation without overflowing.
* I've stolen Suboptimus Prime's heuristic that it's possible to get quick rejections by considering subsets in increasing order of size. I've now merged that idea with the ternary subset meet-in-the-middle approach to test for colliding subsets. (Credit to KennyTM for suggesting trying to adapt the approach from the integer subset problem; I think that xnor and I saw the way to do it pretty much simultaneously). Rather than looking for two subsets which can include each column 0 or 1 times and have the same sum, we look for one subset which can include each column -1, 0, or 1 times and sum to zero. This significantly reduces the memory requirements.
* There's an extra factor of two saving in memory requirements by observing that since each element in `{-1,0,1}^m` has its negation also in `{-1,0,1}^m` it's only necessary to store one of the two.
* I also improve memory requirements and performance by using a custom hashmap implementation. To test 36/19 requires storing 3^18 sums, and 3^18 longs is almost 3GB without any overhead - I gave it 6GB of heap because 4GB wasn't enough; to go any further (i.e. test 38/20) within 8GB of RAM would require further optimisation to store ints rather than longs. With 20 bits required to say which subset produces the sum that would leave 12 bits plus the implicit bits from the bucket; I fear that there would be too many false collisions to get any hits.
* Since the weight of the evidence suggests that we should look at `2n/(n+1)`, I'm speeding things up by just testing that.
* There's some unnecessary but reassuring statistical output.

```
import java.util.*;

// Aiming to find a solution for (2n, n+1).
public class PPCG41021_QRTernary_FixedDensity {
    private static final int N = 36;
    private static int density;
    private static long start;
    private static long nextProgressReport;

    public static void main(String[] args) {
        start = System.nanoTime();
        nextProgressReport = start + 5 * 60 * 1000000000L;

        // 0, -1, 1, -2, 2, ...
        for (int i = 0; i < N - 1; i++) {
            int off = i >> 1;
            if ((i & 1) == 1) off = ~off;
            density = (N >> 1) + off;

            // Iterate over Lyndon words of length N and given density.
            for (int j = 0; j < N; j++) a[j] = j < N - density ? '0' : '1';
            c = 1;
            Bs[1] = N - density;
            Bt[1] = density;
            gen(N - density, density, 1);
            System.out.println("----");
        }

        System.out.println("Finished in " + (System.nanoTime() - start)/1000000 + " ms");
    }

    private static int c;
    private static int[] Bs = new int[N + 1], Bt = new int[N + 1];
    private static char[] a = new char[N];
    private static void gen(int s, int t, int r) {
        if (s > 0 && t > 0) {
            int j = oracle(s, t, r);
            for (int i = t - 1; i >= j; i--) {
                updateBlock(s, t, i);
                char tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                gen(s-1, t-i, testSuffix(r) ? c-1 : r);
                tmp = a[s - 1]; a[s - 1] = a[s+t-i - 1]; a[s+t-i - 1] = tmp;
                restoreBlock(s, t, i);
            }
        }
        visit();
    }

    private static int oracle(int s, int t, int r) {
        int j = pseudoOracle(s, t, r);
        updateBlock(s, t, j);
        int p = testNecklace(testSuffix(r) ? c - 1 : r);
        restoreBlock(s, t, j);
        return p == N ? j : j + 1;
    }

    private static int pseudoOracle(int s, int t, int r) {
        if (s == 1) return t;
        if (c == 1) return s == 2 ? N / 2 : 1;
        if (s - 1 > Bs[r] + 1) return 0;
        if (s - 1 == Bs[r] + 1) return cmpPair(s-1, t, Bs[c-1]+1, Bt[c-1]) <= 0 ? 0 : 1;
        if (s - 1 == Bs[r]) {
            if (s == 2) return Math.max(t - Bt[r], (t+1) >> 1);
            return Math.max(t - Bt[r], (cmpPair(s-1, t, Bs[c-1] + 1, Bt[c-1]) <= 0) ? 0 : 1);
        }
        if (s == Bs[r]) return t;
        throw new UnsupportedOperationException("Hit the case not covered by the paper or its accompanying code");
    }

    private static int testNecklace(int r) {
        if (density == 0 || density == N) return 1;
        int p = 0;
        for (int i = 0; i < c; i++) {
            if (r - i <= 0) r += c;
            if (cmpBlocks(c-i, r-i) < 0) return 0;
            if (cmpBlocks(c-i, r-1) > 0) return N;
            if (r < c) p += Bs[r-i] + Bt[r-i];
        }
        return p;
    }

    private static int cmpPair(int a1, int a2, int b1, int b2) {
        if (a1 < b1) return -1;
        if (a1 > b1) return 1;
        if (a2 < b2) return -1;
        if (a2 > b2) return 1;
        return 0;
    }

    private static int cmpBlocks(int i, int j) {
        return cmpPair(Bs[i], Bt[i], Bs[j], Bt[j]);
    }

    private static boolean testSuffix(int r) {
        for (int i = 0; i < r; i++) {
            if (c - 1 - i == r) return true;
            if (cmpBlocks(c-1-i, r-i) < 0) return false;
            if (cmpBlocks(c-1-i, r-1) > 0) return true;
        }
        return false;
    }

    private static void updateBlock(int s, int t, int i) {
        if (i == 0 && c > 1) {
            Bs[c-1]++;
            Bs[c] = s - 1;
        }
        else {
            Bs[c] = 1;
            Bt[c] = i;
            Bs[c+1] = s-1;
            Bt[c+1] = t-i;
            c++;
        }
    }

    private static void restoreBlock(int s, int t, int i) {
        if (i == 0 && (c > 0 || (Bs[1] != 1 || Bt[1] != 0))) {
            Bs[c-1]--;
            Bs[c] = s;
        }
        else {
            Bs[c-1] = s;
            Bt[c-1] = t;
            c--;
        }
    }

    private static long[] stats = new long[N/2+1];
    private static long visited = 0;
    private static void visit() {
        String word = new String(a);

        visited++;
        if (precedesReversal(word) && testTernary(word)) System.out.println(word + " after " + (System.nanoTime() - start)/1000000 + " ms");
        if (System.nanoTime() > nextProgressReport) {
            System.out.println("Progress: visited " + visited + "; stats " + Arrays.toString(stats) + " after " + (System.nanoTime() - start)/1000000 + " ms");
             nextProgressReport += 5 * 60 * 1000000000L;
        }
    }

    private static boolean precedesReversal(String w) {
        int n = w.length();
        StringBuilder rev = new StringBuilder(w);
        rev.reverse();
        rev.append(rev, 0, n);
        for (int i = 0; i < n; i++) {
            if (rev.substring(i, i + n).compareTo(w) < 0) return false;
        }
        return true;
    }

    private static boolean testTernary(String word) {
        int n = word.length();
        String rep = word + word;

        int base = 1;
        for (char ch : word.toCharArray()) base += ch & 1;

        // Operating base b for b up to 32 implies that we can multiply by b modulo p<2^57 without overflowing a long.
        // We're storing 3^(n/2) ~= 2^(0.8*n) sums, so while n < 35.6 we don't get *too* bad a probability of false reject.
        // (In fact the birthday paradox assumes independence, and our values aren't independent, so we're better off than that).
        long p = (1L << 57) - 13;
        long[] basis = new long[n];
        basis[0] = 1;
        for (int i = 1; i < basis.length; i++) basis[i] = (basis[i-1] * base) % p;

        int rows = n / 2 + 1;
        long[] colVals = new long[n];
        for (int col = 0; col < n; col++) {
            for (int row = 0; row < rows; row++) {
                colVals[col] = (colVals[col] + basis[row] * (rep.charAt(row + col) & 1)) % p;
            }
        }

        MapInt57Int27 map = new MapInt57Int27();
        // Special-case the initial insertion.
        int[] oldLens = new int[map.entries.length];
        int[] oldSupercounts = new int[1 << 10];
        {
            // count = 1
            for (int k = 0; k < n/2; k++) {
                int val = 1 << (25 - k);
                if (!map.put(colVals[k], val)) { stats[1]++; return false; }
                if (!map.put(colVals[k + n/2], val + (1 << 26))) { stats[1]++; return false; }
            }
        }
        final long keyMask = (1L << 37) - 1;
        for (int count = 2; count <= n/2; count++) {
            int[] lens = map.counts.clone();
            int[] supercounts = map.supercounts.clone();
            for (int sup = 0; sup < 1 << 10; sup++) {
                int unaccountedFor = supercounts[sup] - oldSupercounts[sup];
                for (int supi = 0; supi < 1 << 10 && unaccountedFor > 0; supi++) {
                    int i = (sup << 10) + supi;
                    int stop = lens[i];
                    unaccountedFor -= stop - oldLens[i];
                    for (int j = oldLens[i]; j < stop; j++) {
                        long existingKV = map.entries[i][j];
                        long existingKey = ((existingKV & keyMask) << 20) + i;
                        int existingVal = (int)(existingKV >>> 37);

                        // For each possible prepend...
                        int half = (existingVal >> 26) * n/2;
                        // We have 27 bits of key, of which the top marks the half, so 26 bits. That means there are 6 bits at the top which we need to not count.
                        int k = Integer.numberOfLeadingZeros(existingVal << 6) - 1;
                        while (k >= 0) {
                            int newVal = existingVal | (1 << (25 - k));
                            long pos = (existingKey + colVals[k + half]) % p;
                            if (pos << 1 > p) pos = p - pos;
                            if (pos == 0 || !map.put(pos, newVal)) { stats[count]++; return false; }
                            long neg = (p - existingKey + colVals[k + half]) % p;
                            if (neg << 1 > p) neg = p - neg;
                            if (neg == 0 || !map.put(neg, newVal)) { stats[count]++; return false; }
                            k--;
                        }
                    }
                }
            }
            oldLens = lens;
            oldSupercounts = supercounts;
        }

        stats[n/2]++;
        return true;
    }

    static class MapInt57Int27 {
        private long[][] entries;
        private int[] counts;
        private int[] supercounts;

        public MapInt57Int27() {
            entries = new long[1 << 20][];
            counts = new int[1 << 20];
            supercounts = new int[1 << 10];
        }

        public boolean put(long key, int val) {
            int bucket = (int)(key & (entries.length - 1));
            long insert = (key >>> 20) | (((long)val) << 37);
            final long mask = (1L << 37) - 1;

            long[] chain = entries[bucket];
            if (chain == null) {
                chain = new long[16];
                entries[bucket] = chain;
                chain[0] = insert;
                counts[bucket]++;
                supercounts[bucket >> 10]++;
                return true;
            }

            int stop = counts[bucket];
            for (int i = 0; i < stop; i++) {
                if ((chain[i] & mask) == (insert & mask)) {
                    return false;
                }
            }

            if (stop == chain.length) {
                long[] newChain = new long[chain.length < 512 ? chain.length << 1 : chain.length + 512];
                System.arraycopy(chain, 0, newChain, 0, chain.length);
                entries[bucket] = newChain;
                chain = newChain;
            }
            chain[stop] = insert;
            counts[bucket]++;
            supercounts[bucket >> 10]++;
            return true;
        }
    }
}

```

The first one found is

```
000001001010110001000101001111111111

```

and that's the only hit in 15 hours.

Smaller winners:

```
4/3:    0111                       (plus 8 different 8/6)
9/6:    001001011                  (and 5 others)
11/7:   00010100111                (and 3 others)
13/8:   0001001101011              (and 5 others)
15/9:   000010110110111            (and 21 others)
16/9:   0000101110111011           (and 1 other)
20/11:  00000101111011110111       (and others)
22/12:  0000001100110011101011     (and others)
24/13:  000000101011101011101011   (and others)
26/14:  00000001101110010011010111 (and others)
28/15:  0000000010000111100111010111 (and others)
30/16:  000000001011001110011010101111 (and probably others)
32/17:  00001100010010100100101011111111 (and others)
34/18:  0000101000100101000110010111111111 (and others)

```
> 11 votes

# Answer
## Python 2 - 21/12

*In the process of proving that a `2-(3/n)` always exists for any `n`*

Inspired by this question, I used De Bruijn Sequence to brute force the possible matrices. And after bruteforcing for `n=6,7,8,9,10`, I found a pattern that the highest solution is always in the shape of `(n, 2n-3)`.

So I created another method to bruteforce just that shape of matrix, and use multiprocessing to speed things up, since this task is highly distributable. In 16-core ubuntu, it can find solution for `n=12` in around 4 minutes:

```
Trying (0, 254)
Trying (254, 509)
Trying (509, 764)
Trying (764, 1018)
Trying (1018, 1273)
Trying (1273, 1528)
Trying (1528, 1782)
Trying (1782, 2037)
Trying (2037, 2292)
Trying (2292, 2546)
Trying (2546, 2801)
Trying (2801, 3056)
Trying (3056, 3310)
Trying (3820, 4075)
Trying (3565, 3820)
Trying (3310, 3565)
(1625, 1646)
[[0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0]
 [0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0]
 [0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0]
 [1 0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0]
 [0 0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1]
 [0 1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0]
 [1 0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0]
 [0 1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1]
 [1 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0]
 [1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1]
 [1 1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1]
 [1 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 1 1 1]]
(12, 21)
Score: 1.7500

real    4m9.121s
user    42m47.472s
sys 0m5.780s

```

The bulk of computation goes to checking property X, which requires checking all subsets (there are `2^(2n-3)` subsets)

Note that I rotate the first row to the left, not to the right as in the question. But these are equivalent since you can just reverse the whole matrix. =)

The code:

```
import math
import numpy as np
from itertools import combinations
from multiprocessing import Process, Queue, cpu_count

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    alphabet = list(range(k))
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

def generate_cyclic_matrix(seq, n):
    result = []
    for i in range(n):
        result.append(seq[i:]+seq[:i])
    return np.array(result)

def generate_cyclic_matrix_without_property_x(n=3, n_jobs=-1):
    seq = de_bruijn(2,n)
    seq = seq + seq[:n/2]
    max_idx = len(seq)
    max_score = 1
    max_matrix = np.array([[]])
    max_ij = (0,0)
    workers = []
    queue = Queue()
    if n_jobs < 0:
        n_jobs += cpu_count()+1
    for i in range(n_jobs):
        worker = Process(target=worker_function, args=(seq,i*(2**n-2*n+3)/n_jobs, (i+1)*(2**n-2*n+3)/n_jobs, n, queue))
        workers.append(worker)
        worker.start()
    (result, max_ij) = queue.get()
    for worker in workers:
        worker.terminate()
    return (result, max_ij)

def worker_function(seq,min_idx,max_idx,n,queue):
    print 'Trying (%d, %d)' % (min_idx, max_idx)
    for i in range(min_idx, max_idx):
        j = i+2*n-3
        result = generate_cyclic_matrix(seq[i:j], n)
        if has_property_x(result):
            continue
        else:
            queue.put( (result, (i,j)) )
            return

def has_property_x(mat):
    vecs = zip(*mat)
    vector_sums = set()
    for i in range(1, len(vecs)+1):
        for combination in combinations(vecs, i):
            vector_sum = tuple(sum(combination, np.array([0]*len(mat))))
            if vector_sum in vector_sums:
                return True
            else:
                vector_sums.add(vector_sum)
    return False

def main():
    import sys
    n = int(sys.argv[1])
    if len(sys.argv) > 2:
        n_jobs = int(sys.argv[2])
    else:
        n_jobs = -1
    (matrix, ij) = generate_cyclic_matrix_without_property_x(n, n_jobs)
    print ij
    print matrix
    print matrix.shape
    print 'Score: %.4f' % (float(matrix.shape[1])/matrix.shape[0])

if __name__ == '__main__':
    main()

```

---

### Old answer, for reference

The optimal solution so far (`n=10`):

```
(855, 872)
[[1 1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0]
 [1 0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1]
 [0 1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1]
 [1 0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0]
 [0 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1]
 [1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0]
 [0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1]
 [0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0]
 [1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0]
 [1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 0 1]]
(10, 17)
Score: 1.7000

```

For `n=7`:

```
(86, 97)
[[0 1 1 1 0 1 0 0 1 1 1]
 [1 1 1 0 1 0 0 1 1 1 0]
 [1 1 0 1 0 0 1 1 1 0 1]
 [1 0 1 0 0 1 1 1 0 1 1]
 [0 1 0 0 1 1 1 0 1 1 1]
 [1 0 0 1 1 1 0 1 1 1 0]
 [0 0 1 1 1 0 1 1 1 0 1]]
(7, 11)
Score: 1.5714

```

A solution with the shape as described by OP (`n=8`):

```
(227, 239)
[[0 1 0 1 1 1 1 1 0 1 1 0]
 [1 0 1 1 1 1 1 0 1 1 0 0]
 [0 1 1 1 1 1 0 1 1 0 0 1]
 [1 1 1 1 1 0 1 1 0 0 1 0]
 [1 1 1 1 0 1 1 0 0 1 0 1]
 [1 1 1 0 1 1 0 0 1 0 1 1]
 [1 1 0 1 1 0 0 1 0 1 1 1]
 [1 0 1 1 0 0 1 0 1 1 1 1]]
(8, 12)
Score: 1.5000

```

But a better one (`n=8`):

```
(95, 108)
[[0 1 1 0 0 1 0 0 0 1 1 0 1]
 [1 1 0 0 1 0 0 0 1 1 0 1 0]
 [1 0 0 1 0 0 0 1 1 0 1 0 1]
 [0 0 1 0 0 0 1 1 0 1 0 1 1]
 [0 1 0 0 0 1 1 0 1 0 1 1 0]
 [1 0 0 0 1 1 0 1 0 1 1 0 0]
 [0 0 0 1 1 0 1 0 1 1 0 0 1]
 [0 0 1 1 0 1 0 1 1 0 0 1 0]]
(8, 13)
Score: 1.6250

```

It also found another optimal solution at `n=9`:

```
(103, 118)
[[0 1 0 1 1 1 0 0 0 0 1 1 0 0 1]
 [1 0 1 1 1 0 0 0 0 1 1 0 0 1 0]
 [0 1 1 1 0 0 0 0 1 1 0 0 1 0 1]
 [1 1 1 0 0 0 0 1 1 0 0 1 0 1 0]
 [1 1 0 0 0 0 1 1 0 0 1 0 1 0 1]
 [1 0 0 0 0 1 1 0 0 1 0 1 0 1 1]
 [0 0 0 0 1 1 0 0 1 0 1 0 1 1 1]
 [0 0 0 1 1 0 0 1 0 1 0 1 1 1 0]
 [0 0 1 1 0 0 1 0 1 0 1 1 1 0 0]]
(9, 15)
Score: 1.6667

```

The code is as follows. It's just brute force, but at least it can find something better than OP's claim =)

```
import numpy as np
from itertools import combinations

def de_bruijn(k, n):
    """
    De Bruijn sequence for alphabet k
    and subsequences of length n.
    """
    alphabet = list(range(k))
    a = [0] * k * n
    sequence = []
    def db(t, p):
        if t > n:
            if n % p == 0:
                for j in range(1, p + 1):
                    sequence.append(a[j])
        else:
            a[t] = a[t - p]
            db(t + 1, p)
            for j in range(a[t - p] + 1, k):
                a[t] = j
                db(t + 1, t)
    db(1, 1)
    return sequence

def generate_cyclic_matrix(seq, n):
    result = []
    for i in range(n):
        result.append(seq[i:]+seq[:i])
    return np.array(result)

def generate_cyclic_matrix_without_property_x(n=3):
    seq = de_bruijn(2,n)
    max_score = 0
    max_matrix = []
    max_ij = (0,0)
    for i in range(2**n+1):
        for j in range(i+n, 2**n+1):
            score = float(j-i)/n
            if score <= max_score:
                continue
            result = generate_cyclic_matrix(seq[i:j], n)
            if has_property_x(result):
                continue
            else:
                if score > max_score:
                    max_score = score
                    max_matrix = result
                    max_ij = (i,j)
    return (max_matrix, max_ij)

def has_property_x(mat):
    vecs = zip(*mat)
    vector_sums = set()
    for i in range(1, len(vecs)):
        for combination in combinations(vecs, i):
            vector_sum = tuple(sum(combination, np.array([0]*len(mat))))
            if vector_sum in vector_sums:
                return True
            else:
                vector_sums.add(vector_sum)
    return False

def main():
    import sys
    n = int(sys.argv[1])
    (matrix, ij) = generate_cyclic_matrix_without_property_x(n)
    print ij
    print matrix
    print matrix.shape
    print 'Score: %.4f' % (float(matrix.shape[1])/matrix.shape[0])

if __name__ == '__main__':
    main()

```
> 9 votes

# Answer
## 24/13 26/14 28/15 30/16 32/17 (C#)

**Edit:** Deleted outdated info from my answer. I'm using mostly the same algorithm as Peter Taylor (**Edit:** looks like he is using a better algorithm now), although I've added some of my own optimizations:

* I've implemented "meet in the middle" strategy of searching for column sets with the same vector sum (suggested by this KennyTM's comment). This strategy improved memory usage a lot, but it's rather slow, so I've added the `HasPropertyXFast` function, that quickly checks if there are small set with equal sums before using "meet in the middle" approach.
* While iterating through column sets in the `HasPropertyXFast` function, I start from checking column sets with 1 column, then with 2, 3 and so on. The function returns as soon as the first collision of column sums is found. In practice it means that I usually have to check just a few hundreds or thousands of column sets rather than millions.
* I'm using `long` variables to store and compare entire columns and their vector sums. This approach is at least an order of magnitude faster than comparing columns as arrays.
* I've added my own implementation of hashset, optimized for `long` data type and for my usage patterns.
* I'm reusing the same 3 hashsets for the entire lifetime of the application to reduce the number of memory allocations and improve performance.
* Multithreading support.

Program output:

```
00000000000111011101010010011111
10000000000011101110101001001111
11000000000001110111010100100111
11100000000000111011101010010011
11110000000000011101110101001001
11111000000000001110111010100100
01111100000000000111011101010010
00111110000000000011101110101001
10011111000000000001110111010100
01001111100000000000111011101010
00100111110000000000011101110101
10010011111000000000001110111010
01001001111100000000000111011101
10100100111110000000000011101110
01010010011111000000000001110111
10101001001111100000000000111011
11010100100111110000000000011101
Score: 32/17 = 1,88235294117647
Time elapsed: 02:11:05.9791250

```

Code:

```
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

class Program
{
    const int MaxWidth = 32;
    const int MaxHeight = 17;

    static object _lyndonWordLock = new object();

    static void Main(string[] args)
    {
        Stopwatch sw = Stopwatch.StartNew();
        double maxScore = 0;
        const int minHeight = 17; // 1
        for (int height = minHeight; height <= MaxHeight; height++)
        {
            Console.WriteLine("Row count = " + height);
            Console.WriteLine("Time elapsed: " + sw.Elapsed + "\r\n");

            int minWidth = Math.Max(height, (int)(height * maxScore) + 1);
            for (int width = minWidth; width <= MaxWidth; width++)
            {
#if MULTITHREADING
                int[,] matrix = FindMatrixParallel(width, height);
#else
                int[,] matrix = FindMatrix(width, height);
#endif
                if (matrix != null)
                {
                    PrintMatrix(matrix);
                    Console.WriteLine("Time elapsed: " + sw.Elapsed + "\r\n");
                    maxScore = (double)width / height;
                }
                else
                    break;
            }
        }
    }

#if MULTITHREADING
    static int[,] FindMatrixParallel(int width, int height)
    {
        _lyndonWord = 0;
        _stopSearch = false;

        int threadCount = Environment.ProcessorCount;
        Task<int[,]>[] tasks = new Task<int[,]>[threadCount];
        for (int i = 0; i < threadCount; i++)
            tasks[i] = Task<int[,]>.Run(() => FindMatrix(width, height));

        int index = Task.WaitAny(tasks);
        if (tasks[index].Result != null)
            _stopSearch = true;

        Task.WaitAll(tasks);
        foreach (Task<int[,]> task in tasks)
            if (task.Result != null)
                return task.Result;

        return null;
    }

    static volatile bool _stopSearch;
#endif

    static int[,] FindMatrix(int width, int height)
    {
#if MULTITHREADING
        _columnSums = new LongSet();
        _left = new LongSet();
        _right = new LongSet();
#endif

        foreach (long rowTemplate in GetLyndonWords(width))
        {
            int[,] matrix = new int[width, height];
            for (int x = 0; x < width; x++)
            {
                int cellValue = (int)(rowTemplate >> (width - 1 - x)) % 2;
                for (int y = 0; y < height; y++)
                    matrix[(x + y) % width, y] = cellValue;
            }

            if (!HasPropertyX(matrix))
                return matrix;

#if MULTITHREADING
            if (_stopSearch)
                return null;
#endif
        }

        return null;
    }

#if MULTITHREADING
    static long _lyndonWord;
#endif

    static IEnumerable<long> GetLyndonWords(int length)
    {
        long lyndonWord = 0;
        long max = (1L << (length - 1)) - 1;
        while (lyndonWord <= max)
        {
            if ((lyndonWord % 2 != 0) && PrecedesReversal(lyndonWord, length))
                yield return lyndonWord;

#if MULTITHREADING
            lock (_lyndonWordLock)
            {
                if (_lyndonWord <= max)
                    _lyndonWord = NextLyndonWord(_lyndonWord, length);
                else
                    yield break;

                lyndonWord = _lyndonWord;
            }
#else
            lyndonWord = NextLyndonWord(lyndonWord, length);
#endif
        }
    }

    static readonly int[] _lookup =
    {
        32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4, 7, 17,
        0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 20, 8, 19, 18
    };

    static int NumberOfTrailingZeros(uint i)
    {
        return _lookup[(i & -i) % 37];
    }

    static long NextLyndonWord(long w, int length)
    {
        if (w == 0)
            return 1;

        int currentLength = length - NumberOfTrailingZeros((uint)w);
        while (currentLength < length)
        {
            w += w >> currentLength;
            currentLength *= 2;
        }

        w++;

        return w;
    }

    private static bool PrecedesReversal(long lyndonWord, int length)
    {
        int shift = length - 1;

        long reverse = 0;
        for (int i = 0; i < length; i++)
        {
            long bit = (lyndonWord >> i) % 2;
            reverse |= bit << (shift - i);
        }

        for (int i = 0; i < length; i++)
        {
            if (reverse < lyndonWord)
                return false;

            long bit = reverse % 2;
            reverse /= 2;
            reverse += bit << shift;
        }

        return true;
    }

#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _left = new LongSet();
#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _right = new LongSet();

    static bool HasPropertyX(int[,] matrix)
    {
        long[] matrixColumns = GetMatrixColumns(matrix);
        if (matrixColumns.Length == 1)
            return false;

        return HasPropertyXFast(matrixColumns) || MeetInTheMiddle(matrixColumns);
    }

    static bool MeetInTheMiddle(long[] matrixColumns)
    {
        long[] leftColumns = matrixColumns.Take(matrixColumns.Length / 2).ToArray();
        long[] rightColumns = matrixColumns.Skip(matrixColumns.Length / 2).ToArray();

        if (PrepareHashSet(leftColumns, _left) || PrepareHashSet(rightColumns, _right))
            return true;

        foreach (long columnSum in _left.GetValues())
            if (_right.Contains(columnSum))
                return true;

        return false;
    }

    static bool PrepareHashSet(long[] columns, LongSet sums)
    {
        int setSize = (int)System.Numerics.BigInteger.Pow(3, columns.Length);
        sums.Reset(setSize, setSize);
        foreach (long column in columns)
        {
            foreach (long sum in sums.GetValues())
                if (!sums.Add(sum + column) || !sums.Add(sum - column))
                    return true;

            if (!sums.Add(column) || !sums.Add(-column))
                return true;
        }

        return false;
    }

#if MULTITHREADING
    [ThreadStatic]
#endif
    static LongSet _columnSums = new LongSet();

    static bool HasPropertyXFast(long[] matrixColumns)
    {
        int width = matrixColumns.Length;

        int maxColumnCount = width / 3;
        _columnSums.Reset(width, SumOfBinomialCoefficients(width, maxColumnCount));

        int resetBit, setBit;
        for (int k = 1; k <= maxColumnCount; k++)
        {
            uint columnMask = (1u << k) - 1;
            long sum = 0;
            for (int i = 0; i < k; i++)
                sum += matrixColumns[i];

            while (true)
            {
                if (!_columnSums.Add(sum))
                    return true;
                if (!NextColumnMask(columnMask, k, width, out resetBit, out setBit))
                    break;
                columnMask ^= (1u << resetBit) ^ (1u << setBit);
                sum = sum - matrixColumns[resetBit] + matrixColumns[setBit];
            }
        }

        return false;
    }

    // stolen from Peter Taylor
    static bool NextColumnMask(uint mask, int k, int n, out int resetBit, out int setBit)
    {
        int gap = NumberOfTrailingZeros(~mask);
        int next = 1 + NumberOfTrailingZeros(mask & (mask + 1));

        if (((k - gap) & 1) == 0)
        {
            if (gap == 0)
            {
                resetBit = next - 1;
                setBit = next - 2;
            }
            else if (gap == 1)
            {
                resetBit = 0;
                setBit = 1;
            }
            else
            {
                resetBit = gap - 2;
                setBit = gap;
            }
        }
        else
        {
            if (next == n)
            {
                resetBit = 0;
                setBit = 0;
                return false;
            }

            if ((mask & (1 << next)) == 0)
            {
                if (gap == 0)
                {
                    resetBit = next - 1;
                    setBit = next;
                }
                else
                {
                    resetBit = gap - 1;
                    setBit = next;
                }
            }
            else
            {
                resetBit = next;
                setBit = gap;
            }
        }

        return true;
    }

    static long[] GetMatrixColumns(int[,] matrix)
    {
        int width = matrix.GetLength(0);
        int height = matrix.GetLength(1);

        long[] result = new long[width];
        for (int x = 0; x < width; x++)
        {
            long column = 0;
            for (int y = 0; y < height; y++)
            {
                column *= 13;
                if (matrix[x, y] == 1)
                    column++;
            }

            result[x] = column;
        }

        return result;
    }

    static int SumOfBinomialCoefficients(int n, int k)
    {
        int result = 0;
        for (int i = 0; i <= k; i++)
            result += BinomialCoefficient(n, i);
        return result;
    }

    static int BinomialCoefficient(int n, int k)
    {
        long result = 1;
        for (int i = n - k + 1; i <= n; i++)
            result *= i;
        for (int i = 2; i <= k; i++)
            result /= i;
        return (int)result;
    }

    static void PrintMatrix(int[,] matrix)
    {
        int width = matrix.GetLength(0);
        int height = matrix.GetLength(1);

        for (int y = 0; y < height; y++)
        {
            for (int x = 0; x < width; x++)
                Console.Write(matrix[x, y]);
            Console.WriteLine();
        }

        Console.WriteLine("Score: {0}/{1} = {2}", width, height, (double)width / height);
    }
}

class LongSet
{
    private static readonly int[] primes =
    {
        17, 37, 67, 89, 113, 149, 191, 239, 307, 389, 487, 613, 769, 967, 1213, 1523, 1907,
        2389, 2999, 3761, 4703, 5879, 7349, 9187, 11489, 14369, 17971, 22469, 28087, 35111,
        43889, 54869, 68597, 85751, 107197, 133999, 167521, 209431, 261791, 327247, 409063,
        511333, 639167, 798961, 998717, 1248407, 1560511, 1950643, 2438309, 3047909,
        809891, 4762367, 5952959, 7441219, 9301529, 11626913, 14533661, 18167089, 22708867,
        28386089, 35482627, 44353297, 55441637, 69302071, 86627603, 108284507, 135355669,
        169194593, 211493263, 264366593, 330458263, 413072843, 516341057, 645426329,
        806782913, 1008478649, 1260598321
    };

    private int[] _buckets;
    private int[] _nextItemIndexes;
    private long[] _items;
    private int _count;
    private int _minCapacity;
    private int _maxCapacity;
    private int _currentCapacity;

    public LongSet()
    {
        Initialize(0, 0);
    }

    private int GetPrime(int capacity)
    {
        foreach (int prime in primes)
            if (prime >= capacity)
                return prime;

        return int.MaxValue;
    }

    public void Reset(int minCapacity, int maxCapacity)
    {
        if (maxCapacity > _maxCapacity)
            Initialize(minCapacity, maxCapacity);
        else
            ClearBuckets();
    }

    private void Initialize(int minCapacity, int maxCapacity)
    {
        _minCapacity = GetPrime(minCapacity);
        _maxCapacity = GetPrime(maxCapacity);
        _currentCapacity = _minCapacity;

        _buckets = new int[_maxCapacity];
        _nextItemIndexes = new int[_maxCapacity];
        _items = new long[_maxCapacity];
        _count = 0;
    }

    private void ClearBuckets()
    {
        Array.Clear(_buckets, 0, _currentCapacity);
        _count = 0;
        _currentCapacity = _minCapacity;
    }

    public bool Add(long value)
    {
        int bucket = (int)((ulong)value % (ulong)_currentCapacity);
        for (int i = _buckets[bucket] - 1; i >= 0; i = _nextItemIndexes[i])
            if (_items[i] == value)
                return false;

        if (_count == _currentCapacity)
        {
            Grow();
            bucket = (int)((ulong)value % (ulong)_currentCapacity);
        }

        int index = _count;
        _items[index] = value;
        _nextItemIndexes[index] = _buckets[bucket] - 1;
        _buckets[bucket] = index + 1;
        _count++;

        return true;
    }

    private void Grow()
    {
        Array.Clear(_buckets, 0, _currentCapacity);

        const int growthFactor = 8;
        int newCapacity = GetPrime(_currentCapacity * growthFactor);
        if (newCapacity > _maxCapacity)
            newCapacity = _maxCapacity;
        _currentCapacity = newCapacity;

        for (int i = 0; i < _count; i++)
        {
            int bucket = (int)((ulong)_items[i] % (ulong)newCapacity);
            _nextItemIndexes[i] = _buckets[bucket] - 1;
            _buckets[bucket] = i + 1;
        }
    }

    public bool Contains(long value)
    {
        int bucket = (int)((ulong)value % (ulong)_buckets.Length);
        for (int i = _buckets[bucket] - 1; i >= 0; i = _nextItemIndexes[i])
            if (_items[i] == value)
                return true;

        return false;
    }

    public IReadOnlyList<long> GetValues()
    {
        return new ArraySegment<long>(_items, 0, _count);
    }
}

```

Configuration file:

```
<?xml version="1.0" encoding="utf-8" ?>
<configuration>
  <runtime>
    <gcAllowVeryLargeObjects enabled="true" />
  </runtime>
</configuration>

```
> 7 votes

---
Tags: code-challenge, binary-matrix
---


# Question
Title: Calculate a pi-based sequence with a pi-based frequence
## Introduction

Pi is

```
3.1415926535897932384626433832795028841971693993751058209749445923078164062862089...

```

Let's treat each digit as an instruction as to how to get to the next digit.

* The first digit is 3.
* Counting three digits after the first digit, we arrive at 1.
* One digit after this 1 is a 5.
* Five digits after that is 3.
* Three digits later is 9.

The digits included in this sequence are in bold: **3**.14**15**9265**3**58**9**79323846**2**6**4**33...

If a digit is 0, the next digit is 10 later.

## Challenge

Given a positive integer `n` less than 1000, find out how many of the first `n` digits of pi, including the initial 3, are in the sequence.

Furthermore, your code's characters must have a "pi-based frequency". Choose any character; your program must use exactly three of that character. Choose another character, use exactly one of it. Choose another character, use it four times. You may continue for as long as you wish, but each character chosen must be different.

For example, the following snippet complies with the frequency rules (but produces the wrong output):

```
print "r\"rriiiittttnttttppppp"
# Uses 3 quotation marks, 1 space, 4 r's, 1 \, 5 i's, 9 t's, 2 n's, and 6 p's.

```

For the purposes of "pi-based frequency", treat the digit 0 as 10.

You may write a function or a full program. You may not use any built-in constants, trigonometry functions, or complex number functions to find pi.

Shortest code in characters wins. The tiebreaker is the most votes.

## Examples

```
Input  Output
-------------
 1      1
 2      1
 3      1
 4      2
 5      3
 28     8
 77     17
 123    28
 328    73
 625    122
 999    189

```

# Answer
> 4 votes
## Mathematica, 253 bytes

```
f=(For[i=0;j=1,j<=#,j+=Mod[RealDigits[9801/Sqrt@8/Sum[(4j)!(1103+26390j)/(j!)^4/396^(4j),{j,0,125}],10,999][[1,j]]-1,10]+1;++i];"99iiiitS===oooo8862^^^^^^\uusRRRRRRqqqqqqqqMMMMmlllllllgggggggFFFeeeeeeeeDDDDDDaaaaa55555555<<{{\{{{{{{}}}}}}}}--@@@@@@";i)&

```

Ungolfed:

```
f = (
   For[i = 0; j = 1, j <= #,
    j += Mod[
       RealDigits[
          9801/Sqrt@8/
           Sum[(4 j)! (1103 + 26390 j)/(j!)^4/396^(4 j), {j, 0, 125}],
           10, 999][[1, j]] - 1, 10] + 1; ++i];
   "99iiiitS===oooo8862^^^^^^uusRRRRRRqqqqqqqqMMMMmlllllllgggggggFFFeeeeeeeeDDDDDDaaaaa55555555<<{{{{{{{{}}}}}}}}--@@@@@@";
   i
   ) &

```

Usage is `f[999]`.

A whopping 122 bytes are used to pad the code with a useless string to get the right character frequencies. I'll try to improve that tomorrow.

The character frequencies should match the digits of pi in this order:

```
3#/&(,![)4+9j0it"S=;]ro862^usRqM1mlgFfeDda5<{}-@

```

I confirmed that there is *some* correct order with the following snippet:

```
Sort[Last /@
   Tally[Characters@
     "f=(For[i=0;j=1,j<=#,j+=Mod[RealDigits[9801/Sqrt@8/Sum[(4j)!(\
1103+26390j)/(j!)^4/396^(4j),{j,0,125}],10,999][[1,j]]-1,10]+1;++i];\"\
99iiiitS===oooo8862^^^^^^\
uusRRRRRRqqqqqqqqMMMMmlllllllgggggggFFFeeeeeeeeDDDDDDaaaaa55555555<<{{\
{{{{{{}}}}}}}}--@@@@@@\";i)&"]] ==
 Sort[RealDigits[Pi, 10, 48][[1]] /. 0 -> 10]

```

I'm computing pi with Ramanujan's series. It converges to 1000 digits in 125 terms. Due to golfing reasons, I recompute the 999 necessary digits for every single digit of the subsequence, but it still completes within a second for `n = 999` on my machine.

# Answer
> 4 votes
# C++, 550 428

```
#include<iostream>
long a[3505],b,c=3505,d,e,f=10000,g,h,i,j,k,l,x,z;int main(){int P[1000];int M[4];for(;(b=c-=14)>0;){for(;--b>0;){d*=b;if(h==0)d+=2000*f;else d+=a[b]*f;g=b+b-1;a[b]=d%g;d/=g;}h=e+d/f;i=h;for(j=0;j<4;j++){M[j]=i%10;i/=10;}for(j=3;j>=0;j--){P[z]=M[j];z++;};d=e=d%f;}std::cin>>k;j=0;while(j<k){x=P[j];(x==0)?x=10:x;j+=x;l++;}std::cout<<l;}//{{{:+-2220000%,ddhhhhiiiiiiijjnorrt, # # # ,MQQQRRRSSSSSSSSTTTTTTTTT:}}}

```

I'm not 100% confident that my code has a π-based frequence. I will check tomorrow. If it works, there is a direct correspondance between the frequencies of the following characters and the 60 first digits of π.

```
  zdj(mxakcb)1[*uPes>0M34t;l]g+=n%wo-,hQ{}Rr<f/Si :sT#2
  3.141592653589793238462643383279502884197169399375105820974944

```

The craziest part is the computation of π. It is done thanks to an implementation of a fascinating spigot algorithm:

> **Edit:** you can generate *n* digits of π with this 288 characters-long program: :)

```
#include<iostream>
#include<vector>
using namespace std;long b,c,d,e,f=10000,g,h,l;int main(){cout<<"? ";cin>>l;cout<<": ";l=(l/4+1)*14;c=l;vector<long> a;a.resize(l);for(;(b=c-=14)>0;){for(;--b>0;){d*=b;if(h==0)d+=2000*f;else d+=a[b]*f;g=b+b-1;a[b]=d%g;d/=g;}h=e+d/f;cout<<h;d=e=d%f;}}

```

---
Tags: code-golf, restricted-source, sequence, pi
---


# Question
Title: WinAli - Virtual CPU for understanding assembly language
WinAli is a model assembler for Windows. It emulates a real CPU and is meant to help students learning and understanding the Assembly language.

German Wikipedia article: http://de.wikipedia.org/wiki/WinAli (there is no english article at the moment)

In case you want to test your produced output: Link to Google Drive (the program itself is in German but is easy to use even if you don't understand German)

### Some information about WinAli (data and syntax)

**Data types:**

The only data type in WinAli is a 2 byte long "Integer" which is in fact a *Smallint* or *short*. So you don't have to take care of correct types. This is also rounded when dividing.

**Variables and constants:**

Variables are defined like this after the commands:

```
name DS F

```
* *name* is obviously the name of the variable
* *DS* is the keyword for a new variable
* *F* defines the length of the variable in bits; this is zero-based and hexadecimal so F = 16 bits

Constants are very similar:

```
name DC value

```
* *name* is simply the name of the constant
* *DC* is the keyword for a new constant
* *value* is the value assigned to that constant e.g. `two DC '2'`
* You don't need to specify constants at the end of the code. You can also write them inline with the `LDA` (load) operation e.g. `LDA 0,'2'`. This loads "2" into register 0 (the accumulator).

**Syntax:**

The code is aligned into 4 columns which are separated by a space or tab:

```
label command params comment

```
* *label* is used for the `b label` command (`goto label`) and is often skipped.
* *command* one of the commands listed below.
* *params* one or two parameters with at least one register and if needed another register, variable, stack or address; these parameters are separated by a comma (`,`).
* *comments* (optional) a comment prefixed with `;` or `*` until the end of the line.

### **Small code reference:**

*There are more commands but for this challenge you only need those:*

* `INI A` Stores the next user input into variable `A`
* `OUTI A` Outputs the value the variable `A` is holding. You can't use a register here for some reason.
* `LDA 0,A` Loads the value of `A` into register 0
* `STA 0,A` Stores the value of register 0 into the variable `A`
* `ADD 0,A` Adds the value of `A` to the value of register 0
* `SUB 0,A` Multiplies the value of `A` with the value of register 0
* `DIV 0,A` Divides the value of `A` by the value of register 0
* `EOJ` Defines the end of the job i.e. executable code. Variable and constant declarations begin after this mark.

*Not explicitly needed for this challenge:*

* `program START 0` Sets the first address to be executed to 0 i.e. the next line (`program` is just the name of the program but is needed for the compiler)
* `END program` Ends the program i.e. stop executing, even if other operations would follow

# Your challenge!

Write a program or script that takes a mathematical expression with constant numbers and variables and outputs the WinAli code that takes all variables as input and outputs the result of that expression.

* *You don't need to output the `START` and `END` commands*
* Even though there are 16 registers defined in WinAli we only use register 0, which is the accumulator for all calculations
* You can't use two variables as parameters of a command. You have to save all your results into the accumulator (register 0)
* The input is always on the form of either `x:=(a+b)/c` or simply `(a+b)/c`, you decide
* You only need to take care of `+ - * / (ADD, SUB, MUL, DIV)`, so *no complex calculations like roots, squares or even sinus*
* *Tip:* Try to first extract simple expressions with only 2 arguments e.g. `a:=a+b` then `x:=a/c`
* *Tip:* Your program is allowed to use additional (auxiliary) variables if you can't overwrite variables that are not used later in your code. Define them as `h1 DS F`.
* *Tip:* Empty lines are useless. Try to avoid them. (You really don't need them)

**Example:**

```
Mathematical expression:
 x := (a+b)*c

Expected output (empty lines are for easier reading):
    INI a
    INI b
    INI c

    LDA 0,a
    ADD 0,b
    MUL 0,c
    STA 0,a

    OUTI a
    EOJ
a   DS F
b   DS F
c   DS F

```

## Scoring:

Your score is defined by the length of your code **+** the length of the output of the following expressions:

```
x:=a+b+c*c/d

x:=(a+b)/c-d

x:=a-b*c-d/e

x:=2*a-b*c+d

```
* *-10%* if your code can handle unary minus in expressions.

*In case of a tie, the answer that produces the shortest working WinAli code wins.*

**The solutions may not be hardcoded in any way. I will validate each answer with additional expressions to make sure your answer is correct.**

# Answer
# Perl 5: 948, 355 code + 593 output

After some golfing. Previous shorter version did not properly parse `(a+b)-4*c`.

```
%m=split'\b','-SUB+ADD/DIV*MUL<LDA>STA';$i='(\w+|(?<!\w|\))-\d+)';
$_=<>;@x{@y=/([a-z]\w*)/gi}=@y;print"\tINI $_
"for@x=keys%x;
$f=$_,$x.="<$&>".($g=(grep$f!~$_,a..zz)[0]),$x{$g}=s/@/$g/
while s|\($i\)|$1|g,s|$i[*/]$i|@|||s|$i[+-]$i|@|;$_="$x
\tOUTI $_\tEOJ
";s/>$i<\1//g;s!(^|\b)[-+/*<>]!\n\t$m{$&} 0,!g;
s!-?\d+$!'$&'!mg;print;print"$_\tDS F
"for keys%x

```

Example use:

```
$perl winali.pl <<<"2*a-b*c+d"
    INI b
    INI a
    INI d
    INI c

    LDA 0,'2'
    MUL 0,a
    STA 0,a
    LDA 0,b
    MUL 0,c
    STA 0,b
    LDA 0,a
    SUB 0,b
    ADD 0,d
    STA 0,b
    OUTI b
    EOJ
b   DS F
a   DS F
d   DS F
c   DS F

```
> 4 votes

---
Tags: code-golf, math, assembly, optimized-output
---


title: Scriptbot Warz!

text:
# Question
Title: Scriptbot Warz!
# Scriptbot Warz!

---

The results are in and *Assassin* is our champion, winning 2 of 3 matches! Thanks to everyone who submitted their Scriptbots! Special thanks to *horns* for *BestOpportunityBot* which displayed excellent pathing and made full use of all action options.

**Map 1**

Assassin took out BestOpportunityBot early on, and the rest of the match was pretty boring. Detailed play-by-play here.

1. Assassin: 10 HP, 10 Damage Dealt, 3 Damage Taken
2. The Avoider v3: 10 HP, 0 Damage Dealt, 0 Damage Taken
3. Gotta Finish Eating: 10 HP, 0 Damage Dealt, 0 Damage Taken
4. BestOpportunityBot: 0 HP, 3 Damage Dealt, 10 Damage Taken

**Map 2**

BestOpportunityBot did most of the work on this match, but Assassin was able to take him out in the end. Detailed play-by-play here.

1. Assassin: 2 HP, 10 Damage Dealt, 9 Damage Taken
2. BestOpportunityBot: 0 HP, 32 Damage Dealt, 10 Damage Taken
3. The Avoider v3: 0 HP, 0 Damage Dealt, 12 Damage Taken
4. Gotta Finish Eating: 0 HP, 0 Damage Dealt, 11 Damage Taken

**Map 3**

BestOpportunityBot pushed everyone into traps on this match. Very cool. Detailed play-by-play here.

1. BestOpportunityBot: 10 HP, 30 Damage Dealt, 0 Damage Taken
2. Assassin: 0 HP, 0 Damage Dealt, 0 Damage Taken
3. Gotta Finish Eating: 0 HP, 0 Damage Dealt, 0 Damage Taken
4. The Avoider v3: 0 HP, 0 Damage Dealt, 0 Damage Taken

---

*Thanks for your answers! Since there are just 4 Scriptbots, we are abandoning the tournament plans for three free-for-all matches, one on each of the maps below. The scriptbot with the highest win record wins. In the event of a tie, we will enter into sudden death wherein the scriptbot who breaks the tie first wins.*

---

Your task, should you choose to accept it, is to code a Scriptbot which can traverse an ASCII map and destroy its opponents. Each battle will take the form of a random-starting-order turn-based game where each Scriptbot has a chance to spend their energy points (EP) to take actions. The GameMaster script will feed input to, and interpret output from each Scriptbot.

## Environment

Each Scriptbot is contained within its own directory where it can read from the `map` and `stats` files and read/write to the `data` file. The `data` file can be used to store any persistent information you might find useful.

### The stats File

The `stats` file contains information about your opponents and is formatted as follows. Each player is represented on a separate row. The first column is a player ID (`@` means you). The second column is the health of that player.

```
1,9HP
@,10HP
3,9HP
4,2HP

```

### The map File

The `map` file might look something like this...

```
####################
#   #          #   #
# 1 #          # 2 #
#                  #
###              ###
#                  #
#      #           #
#       #     !    #
#        #         #
#       !####      #
#      ####!       #
#         #        #
#    !     #       #
#           #      #
#                  #
###              ###
#                  #
# 3 #          # @ #
#   #          #   #
####################

```

... or this...

```
######################################
#       # 1        #   @             #
#       #          #          #!     #
#       #          #          ####   #
#  #    #  #       #         !#!     #
#  #    #  #       #      #####      #
#  ###     #    ####    #         #  #
#          #    #!      ###       #  #
#  ######  #    #       #     #####  #
#  #!      #    ######  #        !#  #
#  ###     #            #         #  #
#  #    2  #            #   4     #  #
######################################

```

... or this...

```
###################
###!!!!!!#!!!!!!###
##!             !##
#! 1     !     2 !#
#!       !       !#
#!               !#
#!               !#
#!      !!!      !#
## !!   !!!   !! ##
#!      !!!      !#
#!               !#
#!               !#
#!       !       !#
#! 3     !     @ !#
##!             !##
###!!!!!!#!!!!!!###
###################

```

... or it might look totally different. Either way, the characters used and their meaning will remain the same:

* `#` A wall, impassable and impenetrable.
* `1`, `2`, `3`... A number representing an enemy player. These numbers correspond to the player ID in the `stats` file.
* `!` A trap. Scriptbots who move onto these locations will die immediately.
* `@` Your Scriptbot's location.
* Open space which you are free to move around in.

## Gameplay

The GameMaster script will assign a random starting order to the Scriptbots. The Scriptbots are then invoked in this order while they are still alive. Scriptbots have 10 Health Points (HP), and start with 10 Energy Points (EP) each turn, which they may use to move or attack. At the start of each turn, a Scriptbot will heal for one HP, or be granted one additional EP if already at 10 HP (thus running may be a viable strategy at times).

The battle ends when only one Scriptbot survives or when 100 turns have passed. If multiple Scriptbots are alive at the end of a battle, their place is determined based on the following criteria:

1. Most health.
2. Most damage dealt.
3. Most damage taken.

## Scriptbot Input

The GameMaster will print the battle map to a file named `map` which the Scriptbot will have access to read from. The map might take any form, so it is important that the Scriptbot be able to interpret it. Your Scriptbot will be invoked with one parameter indicating EP. For example...

```
:> example_scriptbot.py 3

```

The Scriptbot will be invoked until it spends all of its EP or a maximum of 10 11 times. The map and stats files are updated before each invocation.

## Scriptbot Output

Scriptbots should output their actions to stout. A list of possible actions are as follows:

* `MOVE <DIRECTION> <DISTANCE>`

Costs 1 EP per `DISTANCE`. The `MOVE` command moves your Scriptbot around the map. If there is something in the way such as a wall or another Scriptbot, the GameMaster will move your Scriptbot as far as possible. If a `DISTANCE` greater than the Scriptbot's remaining EP is given, the GameMaster will move the Scriptbot until its EP runs out. `DIRECTION` may be any compass direction of `N`, `E`, `S`, or `W`.
* `PUSH <DIRECTION> <DISTANCE>`

Costs 1 EP per `DISTANCE`. The `PUSH` command enables a Scriptbot to move another Scriptbot. The Scriptbot issuing the command must be directly next to the Scriptbot being pushed. Both Scriptbots will move in the direction indicated if there is not an object blocking the Scriptbot being pushed. `DIRECTION` and `DISTANCE` are the same as for the `MOVE` command.
* `ATTACK <DIRECTION>`

Costs one EP. The `ATTACK` command deals 1 damage to any Scriptbot directly next to the issuing Scriptbot and in the direction specified. `DIRECTION` is the same as for the `MOVE` command.
* `PASS`

Ends your turn.

## Supported Languages

To keep this reasonable for me, I will accept the following languages:

* Java
* Node.js
* Python
* PHP

You are limited to libraries which are commonly packaged with your languages out of the box. Please do not make me locate obscure libraries to make your code work.

## Submission and Judging

Post your Scriptbot source code below and give it a cool name! Please also list the version of the language you used. All Scriptbots will be reviewed for tomfoolery so please comment well and do not obfuscate your code.

You may submit more than one entry, but please make them totally unique entries, and not versions of the same entry. For instance, you may want to code a Zerg Rush bot and a Gorilla Warfare bot. That's fine. Do not post Zerg Rush v1, Zerg Rush v2, etc.

On November 7th I will collect all answers and those which pass the initial review will be added to a tournament bracket. The champion gets the accepted answer. The ideal bracket is shown below. Since there will likely not be exactly 16 entries, some brackets may end up being only three or even two bots. I will try to make the bracket as fair as possible. Any necessary favoritism (in the event that a bye week is needed for instance) will be given to the bots which were submitted first.

```
BOT01_
BOT02_|
BOT03_|____
BOT04_|    |
           |
BOT05_     |
BOT06_|___ |
BOT07_|  | |
BOT08_|  | |_BOT ?_
         |___BOT ?_|
BOT09_    ___BOT ?_|___CHAMPION!
BOT10_|  |  _BOT ?_|
BOT11_|__| |
BOT12_|    |
           |
BOT13_     |
BOT14_|____|
BOT15_|
BOT16_|

```

## Q&A

*I'm sure I've missed some details, so feel free to ask questions!*

> May we trust that a map file is always surrounded by # symbols? If not, what happens in the event that a bot attempts to walk off the map? - BrainSteel

Yes the map will always be bounded by # and your Scriptbot will start inside of these bounds.

> If there is no bot present in the direction specified in a PUSH command, how does the command function? - BrainSteel

The GameMaster will do nothing, zero EP will be spent, and the Scriptbot will be called again.

> Do unused EP accumulate? - feersum

No. Each Scriptbot will start the round/turn with 10 EP. Any EP not spent will go to waste.

> I think I've got it, but just to clarify: with bots A and B, is the order of events A@10EP-\>MOVE MAP\_UPDATE B@10EP-\>PUSH MAP\_UPDATE A@9EP-\>ATTACK MAP\_UPDATE B@9EP-\>ATTACK ..., or A@10EP-\>MOVE A@9EP-\>ATTACK ... MAP\_UPDATE B@10EP-\>PUSH B@9EP-\>ATTACK ... MAP\_UPDATE? In other words, is all action in one controller-bot query loop atomic? If so, why the loop? Why not return a single file with all the actions to be completed? Otherwise bots will have to write out their own state files to keep track of multi-action sequences. The map/stats file will only be valid prior to the first action. - COTO

Your second example is close, but not quite right. During a turn, the Scriptbot is invoked repeatedly until their EP is spent, or a maximum of 11 times. The map and stats files are updated before each invocation. The loop is useful in the event that a bot gives invalid output. The GameMaster will deal with the invalid output and involke the bot again, giving the bot a chance to correct for it's mistake.

> will you release the GameMaster script for testing? - IchBinKeinBaum

The GameMaster script will not be released. I would encourage you to create a map and stats file to test your bot's behavior.

> If robotA pushes robotB into a trap, is robotA credited with "damage dealt" points equal to the current health of robotB? - Mike Sweeney

Yes, that is a good idea. A bot will be granted damage points equal to the health of a any bot that it pushes into a trap.

# Answer
> 1 votes
# Assassin (Java 1.7)

Tries to kill enemies whenever possible, otherwise moves one field. It is pretty good in finding the path to an enemy, but doesn't do anything to hide from other bots.

```
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.List;

public class Assassin {
    private final Path dataPath = Paths.get("data");
    private final Path mapPath = Paths.get("map");
    private final Path statsPath = Paths.get("stats");
    private final List<Player> players = new ArrayList<>();
    private final int energy;
    private Map map = null;

    public Assassin(int energy) {
        this.energy = energy;
    }

    private void doSomething() {
        if (dataFileEmpty()) {
            calculateTurn();
        }
        printStoredOutput();
    }

    private boolean dataFileEmpty() {
        try {
            return !Files.exists(dataPath) || Files.size(dataPath)  == 0;
        } catch (IOException e) {
            return true;
        }
    }

    private void printStoredOutput() {
        try {
            List<String> lines = Files.readAllLines(dataPath, StandardCharsets.UTF_8);
            //print first line
            System.out.println(lines.get(0));
            //delete first line
            lines.remove(0);
            Files.write(dataPath, lines, StandardCharsets.UTF_8);
        } catch (IOException e) {
            System.out.println("PASS");
        }
    }

    private void calculateTurn() {
        try {
            readStats();
            readMap();
            if (!tryKill())  {
                sneakCloser();
            }
        } catch (IOException e) {}
    }

    private void readStats() throws IOException{
        List<String> stats = Files.readAllLines(statsPath, StandardCharsets.UTF_8);
        for (String stat : stats) {
            String[] infos = stat.split(",");
            int hp = Integer.parseInt(infos[1].replace("HP", ""));
            players.add(new Player(stat.charAt(0), hp));
        }
    }

    private void readMap() throws IOException{
        List<String> lines = Files.readAllLines(mapPath, StandardCharsets.UTF_8);
        Field[][] fields = new Field[lines.size()][lines.get(0).length()];
        for (int row = 0; row < lines.size(); row++) {
            String line = lines.get(row);
            for (int col = 0; col < line.length(); col++) {
                fields[row][col] = new Field(line.charAt(col), row, col);
            }
        }
        map = new Map(fields);
    }

    private boolean tryKill() {
        Field me = map.getMyField();
        for (Field field : map.getEnemyFields()) {
            for (Field surrField : map.surroundingFields(field)) {
                List<Direction> dirs = map.path(me, surrField);
                if (dirs != null) {
                    for (Player player : players) {
                        //can kill this player
                        int remainderEnergy = energy - dirs.size() - player.hp;
                        if (player.id == field.content && remainderEnergy >= 0) {
                            //save future moves
                            List<String> commands = new ArrayList<>();
                            for (Direction dir : dirs) {
                                commands.add("MOVE " + dir + " 1");
                            }
                            //attacking direction
                            Direction attDir = surrField.dirsTo(field).get(0);
                            for (int i = 0; i < player.hp; i++) {
                                commands.add("ATTACK " + attDir);
                            }
                            if (remainderEnergy > 0) {
                                commands.add("PASS");
                            }
                            try {
                                Files.write(dataPath, commands, StandardCharsets.UTF_8);
                            } catch (IOException e) {}
                            return true;
                        }
                    }
                }
            }
        }
        return false;
    }

    private void sneakCloser() {
        Field me = map.getMyField();
        for (Direction dir : Direction.values()) {
            if (!map.move(me, dir).blocked()) {
                List<String> commands = new ArrayList<>();
                commands.add("MOVE " + dir + " 1");
                commands.add("PASS");
                try {
                    Files.write(dataPath, commands, StandardCharsets.UTF_8);
                } catch (IOException e) {}
                return;
            }
        }
    }

    public static void main(String[] args) {
        try {
            new Assassin(Integer.parseInt(args[0])).doSomething();
        } catch (Exception e) {
            System.out.println("PASS");
        }
    }

    class Map {
        private Field[][] fields;

        public Map(Field[][] fields) {
            this.fields = fields;
        }

        public Field getMyField() {
            for (Field[] rows : fields) {
                for (Field field : rows) {
                    if (field.isMyPos()) {
                        return field;
                    }
                }
            }
            return null; //should never happen
        }

        public List<Field> getEnemyFields() {
            List<Field> enemyFields = new ArrayList<>();
            for (Field[] rows : fields) {
                for (Field field : rows) {
                    if (field.hasEnemy()) {
                        enemyFields.add(field);
                    }
                }
            }
            return enemyFields;
        }

        public List<Field> surroundingFields(Field field) {
            List<Field> surrFields = new ArrayList<>();
            for (Direction dir : Direction.values()) {
                surrFields.add(move(field, dir));
            }
            return surrFields;
        }

        public Field move(Field field, Direction dir) {
            return fields[field.row + dir.rowOffset][field.col + dir.colOffset];
        }

        public List<Direction> path(Field from, Field to) {
            List<Direction> dirs = new ArrayList<>();
            Field lastField = from;
            boolean changed = false;

            for (int i = 0; i < energy && lastField != to; i++) {
                List<Direction> possibleDirs = lastField.dirsTo(to);
                changed = false;
                for (Direction dir : possibleDirs) {
                    Field nextField = move(lastField, dir);
                    if (!nextField.blocked()) {
                        lastField = nextField;
                        changed = true;
                        dirs.add(dir);
                        break;
                    }
                }
                if (!changed) {
                    return null; //not possible
                }
            }
            if (lastField != to) {
                return null; //not enough energy
            }
            return dirs;
        }
    }

    class Field {
        private char content;
        private int row;
        private int col;

        public Field(char content, int row, int col) {
            this.content = content;
            this.row = row;
            this.col = col;
        }

        public boolean hasEnemy() {
            return content == '1' || content == '2' || content == '3' || content == '4';
        }

        public List<Direction> dirsTo(Field field) {
            List<Direction> dirs = new ArrayList<>();
            int distance = Math.abs(row - field.row) + Math.abs(col - field.col);

            for (Direction dir : Direction.values()) {
                int dirDistance = Math.abs(row - field.row + dir.rowOffset) +
                        Math.abs(col - field.col + dir.colOffset);
                if (dirDistance < distance) {
                    dirs.add(dir);
                }
            }
            if (dirs.size() == 1) { //add near directions
                for (Direction dir : dirs.get(0).nearDirections()) {
                    dirs.add(dir);
                }
            }
            return dirs;
        }

        public boolean isMyPos() {
            return content == '@';
        }

        public boolean blocked() {
            return content != ' ';
        }
    }

    class Player {
        private char id;
        private int hp;

        public Player(char id, int hp) {
            this.id = id;
            this.hp = hp;
        }
    }

    enum Direction {
        N(-1, 0),S(1, 0),E(0, 1),W(0, -1);

        private final int rowOffset;
        private final int colOffset;

        Direction(int rowOffset, int colOffset) {
            this.rowOffset = rowOffset;
            this.colOffset = colOffset;
        }

        public Direction[] nearDirections() {
            Direction[] dirs = new Direction[2];
            for (int i = 0; i < Direction.values().length; i++) {
                Direction currentDir = Direction.values()[i];
                if (Math.abs(currentDir.rowOffset) != Math.abs(this.rowOffset)) {
                    dirs[i%2] = currentDir;
                }
            }
            return dirs;
        }
    }
}

```

# Answer
> 3 votes
**The Avoider v3**

A simple minded bot. It is afraid of other robots and traps. It will not attack. It ignores the stats file and does not think ahead at all.

This is mainly a test to see how the rules would work, and as a dumb opponent for other competitors.

Edit: Now will PASS when no MOVE is better.

Edit2: Robots can be '1234' instead of '123'

The Python Code:

```
import sys
maxmoves = int(sys.argv[1])

ORTH = [(-1,0), (1,0), (0,-1), (0,1)]
def orth(p):
    return [(p[0]+dx, p[1]+dy) for dx,dy in ORTH]

mapfile = open('map').readlines()[::-1]
arena = dict( ((x,y),ch)
    for y,row in enumerate(mapfile)
    for x,ch in enumerate(row.strip()) )
loc = [loc for loc,ch in arena.items() if ch == '@'][0]

options = []
for direc in ORTH:
    for dist in range(maxmoves+1):
        newloc = (loc[0]+direc[0]*dist, loc[1]+direc[1]*dist)
        if arena.get(newloc) in '#!1234':
            break
        penalty = dist * 10  # try not to use moves too fast
        if newloc == loc:
            penalty += 32   # incentive to move
        for nextto in orth(newloc):
            ch = arena.get(nextto)
            if ch == '#':
                penalty += 17  # don't get caught againt a wall
            elif ch in '1234':
                penalty += 26  # we are afraid of other robots
            elif ch == '!':
                penalty += 38  # we are very afraid of deadly traps
        options.append( [penalty, dist, direc] )

penalty, dist, direc = min(options)
if dist > 0:
    print 'MOVE', 'WESN'[ORTH.index(direc)], dist
else:
    print 'PASS'  # stay still?

```

# Answer
> 3 votes
# BestOpportunityBot

This ended up being a little longer than I intended...and I'm not sure if I understand the rules for turns completely, so we'll see how this does.

```
from sys import argv
from enum import IntEnum

with open("map") as map_file:
    map_lines = map_file.read().splitlines()

with open("stats") as stats_file:
    stats_data = stats_file.read().splitlines()

ep = argv[1]

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __add__(lhs, rhs):
        if (type(rhs) == tuple or type(rhs) == list):
            return Point(lhs.x + rhs[0], lhs.y + rhs[1])
        return Point(lhs.x + rhs.x, lhs.y + rhs.y)

    def __sub__(lhs, rhs):
        if (type(rhs) == tuple or type(rhs) == list):
            return Point(lhs.x - rhs[0], lhs.y - rhs[1])
        return Point(lhs.x - rhs.x, lhs.y - rhs.y)

    def __mul__(lhs, rhs):
        return Point(lhs.x * rhs, lhs.y * rhs)

    def __str__(self):
        return "(" + str(self.x) + ", " + str(self.y) + ")"

    def __repr__(self):
        return "(" + str(self.x) + ", " + str(self.y) + ")"

    def __eq__(lhs, rhs):
        return lhs.x == rhs.x and lhs.y == rhs.y

    def __hash__(self):
        return hash(self.x) * 2**32 + hash(self.y)

    def reverse(self):
        return Point(self.y, self.x)

dirs = (Point(0, 1), Point(1, 0), Point(0, -1), Point(-1, 0))

class Bot:
    def __init__(self, pos, ch, hp):
        self.pos = pos
        self.ch = ch
        self.hp = hp

    def __str__(self):
        return str(self.pos) + " " + str(self.ch) + " " + str(self.hp)

    def __repr__(self):
        return str(self.pos) + " " + str(self.ch) + " " + str(self.hp)

class MyBot(Bot):
    def __init__(self, pos, ch, hp, ep):
        self.ep = ep
        super().__init__(pos, ch, hp)

    def __str__(self):
        return super().__str__() + " " + self.ep

    def __repr__(self):
        return super().__repr__() + " " + self.ep

class Arena:
    def __init__(self, orig_map):
        self._map = list(zip(*orig_map[::-1]))
        self.bots = []
        self.me = None

    def __getitem__(self, indexes):
        if (type(indexes) == Point):
            return self._map[indexes.x][indexes.y]
        return self._map[indexes[0]][indexes[1]]

    def __str__(self):
        output = ""
        for i in range(len(self._map[0]) - 1, -1, -1):
            for j in range(len(self._map)):
                output += self._map[j][i]
            output += "\n"
        output = output[:-1]
        return output

    def set_bot_loc(self, bot):
        for x in range(len(self._map)):
            for y in range(len(self._map[x])):
                if self._map[x][y] == bot.ch:
                    bot.pos = Point(x, y)

    def set_bots_locs(self):
        self.set_bot_loc(self.me)
        for bot in self.bots:
            self.set_bot_loc(bot)

    def adjacent_bots(self, pos=None):
        if type(pos) == None:
            pos = self.me.pos
        output = []
        for bot in self.bots:
            for d in dirs:
                if bot.pos == pos + d:
                    output.append(bot)
                    break
        return output

    def adjacent_bots_and_dirs(self):
        output = {}
        for bot in self.bots:
            for d in dirs:
                if bot.pos == self.me.pos + d:
                    yield bot, d
                    break
        return output

    def look(self, position, direction, distance, ignore='', stopchars='#1234'):
        current = position + direction
        output = []
        for i in range(distance):
            if (0 <= current.x < len(self._map) and
                0 <= current.y < len(self._map[current.x]) and
                (self[current] not in stopchars or self[current] in ignore)):
                output += self[current]
                current = current + direction
            else:
                break
        return output

    def moveable(self, position, direction, distance):
        current = position + direction
        output = []
        for i in range(distance):
            if (0 <= current.x < len(self._map) and
                0 <= current.y < len(self._map[current.x]) and
                self[current] == ' '):
                output += self[current]
            else:
                break
        return output

    def danger(self, pos, ignore=None): # damage that can be inflicted on me
        output = 0
        adjacents = self.adjacent_bots(pos)
        hps = [bot.hp for bot in adjacents if bot != ignore]
        if len(hps) == 0:
            return output

        while max(hps) > 0:
            if 0 in hps:
                hps.remove(0)

            for i in range(len(hps)):
                if hps[i] == min(hps):
                    hps[i] -= 1
                output += 1
        return output

    def path(self, pos): # Dijkstra's algorithm adapted from https://gist.github.com/econchick/4666413
        visited = {pos: 0}
        path = {}

        nodes = set()

        for i in range(len(self._map)):
            for j in range(len(self._map[0])):
                nodes.add(Point(i, j))

        while nodes:
            min_node = None
            for node in nodes:
                if node in visited:
                    if min_node is None:
                        min_node = node
                    elif visited[node] < visited[min_node]:
                        min_node = node

            if min_node is None:
                break

            nodes.remove(min_node)
            current_weight = visited[min_node]

            for _dir in dirs:
                new_node = min_node + _dir
                if self[new_node] in ' 1234':
                    weight = current_weight + 1
                    if new_node not in visited or weight < visited[new_node]:
                        visited[new_node] = weight
                        path[new_node] = min_node

        return visited, path

class MoveEnum(IntEnum):
    Null = 0
    Pass = 1
    Attack = 2
    Move = 3
    Push = 4

class Move:
    def __init__(self, move=MoveEnum.Null, direction=Point(0, 0), distance=0):
        self.move = move
        self.dir = direction
        self.dis = distance

    def __repr__(self):
        if self.move == MoveEnum.Null:
            return "NULL"
        elif self.move == MoveEnum.Pass:
            return "PASS"
        elif self.move == MoveEnum.Attack:
            return "ATTACK " + "NESW"[dirs.index(self.dir)]
        elif self.move == MoveEnum.Move:
            return "MOVE " + "NESW"[dirs.index(self.dir)] + " " + str(self.dis)
        elif self.move == MoveEnum.Push:
            return "PUSH " + "NESW"[dirs.index(self.dir)] + " " + str(self.dis)

arena = Arena(map_lines)
arena.me = MyBot(Point(0, 0), '@', 0, ep)

for line in stats_data:
    if line[0] == '@':
        arena.me.hp = int(line[2:-2])
    else:
        arena.bots.append(Bot(Point(0, 0), line[0], int(line[2:-2])))

arena.set_bots_locs()

current_danger = arena.danger(arena.me.pos)

moves = [] # format (move, damage done, danger, energy)

if arena.me.ep == 0:
    print(Move(MoveEnum.Pass))
    exit()

for bot, direction in arena.adjacent_bots_and_dirs():
    # Push to damage
    pushable_to = arena.look(arena.me.pos, direction,
                             arena.me.ep + 1, ignore=bot.ch)
    if '!' in pushable_to:
        distance = pushable_to.index('!')
        danger = arena.danger(arena.me.pos + (direction * distance), bot)
        danger -= current_danger
        moves.append((Move(MoveEnum.Push, direction, distance),
                      bot.hp, danger, distance))

    # Push to escape
    pushable_to = arena.look(arena.me.pos, direction,
                             arena.me.ep + 1, ignore=bot.ch, stopchars='#1234!')
    for distance in range(1, len(pushable_to)):
        danger = arena.danger(arena.me.pos + (direction * distance), bot)
        danger += bot.hp
        danger -= current_danger
        moves.append((Move(MoveEnum.Push, direction, distance),
                      0, danger, distance))

    # Attack
    bot.hp -= 1
    danger = arena.danger(arena.me.pos) - current_danger
    moves.append((Move(MoveEnum.Attack, direction), 1, danger, 1))
    bot.hp += 1

culled_moves = []

for move in moves: # Cull out attacks and pushes that result in certain death
    if current_danger + move[2] < arena.me.hp:
        culled_moves.append(move)

if len(culled_moves) == 1:
    print(culled_moves[0][0])
    exit()
elif len(culled_moves) > 1:
    best_move = culled_moves[0]

    for move in culled_moves:
        if move[1] - move[2] > best_move[1] - best_move[2]:
            best_move = move
        if move[1] - move[2] == best_move[1] - best_move[2] and move[3] < best_move[3]:
            best_move = move

    print (best_move[0])
    exit()

# Can't attack or push without dying, time to move

moves = []

if current_danger > 0: # Try to escape
    for direction in dirs:
        moveable_to = arena.moveable(arena.me.pos, direction, ep)

        i = 1

        for space in moveable_to:
            danger = arena.danger(arena.me.pos + (direction * i))
            danger -= current_danger
            moves.append((Move(MoveEnum.Move, direction, i), 0, danger, i))
            i += 1

    if len(moves) == 0: # Trapped and in mortal danger, attack biggest guy
        adjacents = arena.adjacent_bots()
        biggest = adjacents[0]
        for bot in adjacents:
            if biggest.hp < bot.hp:
                biggest = bot
        print (Move(MoveEnum.Attack, biggest.pos - arena.me.pos))
        exit()

    best_move = moves[0]
    for move in moves:
        if ((move[2] < best_move[2] and best_move[2] >= arena.me.hp) or
            (move[2] == best_move[2] and move[3] < best_move[3])):
            best_move = move

    print(best_move[0])
    exit()

else: # Seek out closest target with lower health
    distances, path = arena.path(arena.me.pos)

    bot_dists = list((bot, distances[bot.pos]) for bot in arena.bots)

    bot_dists.sort(key=lambda x: x[1])

    target = bot_dists[0]

    for i in range(len(bot_dists)):
        if bot_dists[i][0].hp <= arena.me.hp:
            target = bot_dists[i]
            break

    pos = target[0].pos
    for i in range(target[1] - 1):
        pos = path[pos]

    print (Move(MoveEnum.Move, pos - arena.me.pos, 1))
    exit()

# Shouldn't get here, but I might as well do something
print (Move(MoveEnum.Pass))

```

# Answer
> 1 votes
# Gotta Finish Eating

Python:

```
import sys
print 'PASS'

```

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