# Question
Title: Finding Collatz-like rules with many loops
*This code-challenge is related to the code-golf question Analyzing Collatz-like sequences but the goal is quite different here.*

*If you are familiar with Collatz-like sequences you can skip to the section "The task".*

We define a Collatz-like rule with 3 positive integers:

* `d > 1` divisor
* `m > 1` multiplier
* `i > 0` increment

(In the original Collatz sequence `d = 2`, `m = 3` and `i = 1`.)

For a Collatz-like rule and a positive integer `n` starting value we define a sequence `s` in the following manner:

* `s(0) = n`
* if `k > 0` and `s(k-1) mod d = 0` then `s(k) = s(k-1) / d`
* if `k > 0` and `s(k-1) mod d != 0` then `s(k) = s(k-1) * m + i`

An example sequence with `d = 2, m = 3, i = 5` and `n = 80` will be `s = 80, 40, 20, 10, 5, 20, 10, 5, 20, ...`.

Every sequence will either reach higher values than any given bound (i.e. the sequence is divergent) or get into an infinite loop (for some `t` and `u` (`t!=u`) the `s(t) = s(u)` equality will be true).

Two loops are said to be different if they don't have any common elements.

## The task

You should write a program which finds a Collatz-like rule with many different loops. Your score will be the number of found loops. (You don't have to find all of the possible loops and higher score is better.)

The program could be specialized in any manner to produce the best score.

For proof the program should output the values of `d`, `m`, `i` and the smallest values from every found loop.

## Example

```
For d=3 m=7 i=8 the loops are

LOOP 15 5 43 309 103 729 243 81 27 9 3 1
LOOP 22 162 54 18 6 2
LOOP 36 12 4

So a valid proof with a score of 3 could be

d=3 m=7 i=8 min_values=[1 4 2]

```

You can validate your result with this Python3 code. The program expects a list of space-separated integers `d m i min_value_1 min_value_2 ...` as input.

# Answer
## Java, arbitrary score with relatively small numbers

In my previous answer, I considered only *primitive loops*. It turns out that there's a massive benefit to be gained by considering more complex loops.

Let the *loop structure* `n_0 ... n_{k-1}` denote a loop which has `n_0` multiply operations, then a division, then `n_1` multiplications, then a division, etc. If we start with `x_0` and loop back to `x_0` then we get the constraint

```
-(d^k - m^n) x + (d^{b_0}m^0 + d^{b_1}m^1 + ... + d^{b_{n-1}}m^{n-1}) i

```

where `n = n_0 + ... + n_{k-1}` and `k > b_0 >= b_1 >= ... >= b_{n-1}` with the transitions at points corresponding to division steps.

The big bonus is the divisibility constraint: `(d^k - m^n) | i` is sufficient for `x` to exist and **doesn't depend on the breakdown of the loop structure**. However, because we have small `d` we have to worry about a new problem.

The map `x -> mx + i (mod d)` is a permutation of `0 .. d-1`, and the length of the cycle which contains `0` places an upper bound on the length of a step in the loop sequence. So we have to pick `d` to satisfy two constraints: `d^k - m^n > 0` and the cycle length of `0` under the permutation `x -> mx - m^n` is greater than `n`.

If we do that, though, the net result is that for much smaller increments than in the primitive case we can get a number of loops whose growth is related to necklaces. We have two free variables: in the interests of keeping it simple, we'll pick `n = 2k`. Then the score is OEIS A082936`(k+1)`.

This program allows you to specify `k` via the command line. If `k` isn't specified it defaults to `15` (and will take a while to run).

```
import java.math.BigInteger;
import java.util.*;

public class PPCG47835 {

    public static void main(String[] args) {
        int k = args.length > 0 ? Integer.parseInt(args[0]) : 15;

        BigInteger TWO = BigInteger.valueOf(2);
        int n = 2 * k;
        // We want d to allow steps of up to n without getting a division "too early".
        BigInteger d, i;
    nd: for (d = BigInteger.valueOf((k + 1) | 1); true; d = d.add(TWO)) {
            i = d.pow(k).subtract(BigInteger.ONE.shiftLeft(n));
            if (i.signum() < 0) continue;

            // Find multiplicative inverse of m and additive inverse of i.
            BigInteger half = d.add(BigInteger.ONE).shiftRight(1);
            BigInteger negI = d.subtract(i.mod(d));
            BigInteger inv = BigInteger.ZERO;
            for (int j = 0; j < n; j++) {
                inv = inv.add(negI).multiply(half).mod(d);
                // If we get a division too early, reject this value of d.
                if (inv.signum() == 0) continue nd;
            }

            break;
        }

        System.out.print(d); System.out.print(" ");
        System.out.print("2 "); // m is hard-coded for optimisation reasons
        System.out.print(i); System.out.print(" ");

        visit(d, i, new int[k], 0, n);
    }

    private static long visit(BigInteger d, BigInteger i, int[] a, int off, int unused) {
        long count = 0;
        if (off == a.length - 1) {
            a[off] = unused;

            if (canonical(a)) {
                BigInteger x0 = BigInteger.ZERO, dj = BigInteger.ONE;
                int tail = 0;
                for (int step : a) tail += step;
                for (int step : a) {
                    x0 = x0.add(dj.shiftLeft(tail));
                    tail -= step;
                    x0 = x0.subtract(dj.shiftLeft(tail));
                    dj = dj.multiply(d);
                }

                // Find min element of loop
                BigInteger x = x0, min = x0;
                for (int step : a) {
                    x = x.add(i).shiftLeft(step).subtract(i).divide(d);
                    if (x.compareTo(min) < 0) min = x;
                }
                System.out.print(min); System.out.print(" ");
                count++;
            }
        }
        else {
            for (a[off] = 0; a[off] <= unused; a[off]++) {
                count += visit(d, i, a, off + 1, unused - a[off]);
            }
        }

        return count;
    }

    private static boolean canonical(int[] a) {
        for (int i = 1; i < a.length; i++) {
            // If (a[i], a[i+1], ..., a[n], a[0], ...) < (a[0], a[1], ..., a[n]) then not canonical
            int cmp = 0;
            for (int j = 0; j < a.length; j++) {
                int l = a[(i + j) % a.length];
                if (l < a[j]) return false;
                if (l > a[j]) { cmp = 1; break; }
            }
        }
        return true;
    }
}

```

A table of values for small `k` is

```
k     d   m                        i                             count            time*
1     5   2                                            1                    1      <  10 ms
2     9   2                                           65                    3      <  10 ms
3    11   2                                         1267                   10      <  10 ms
4    11   2                                        14385                   43      <  10 ms
5    13   2                                       370269                  201      ~  20 ms
6    19   2                                     47041785                 1038      ~ 100 ms
7    19   2                                    893855355                 5538      ~ 200 ms
8    19   2                                  16983497505                30667      ~ 200 ms
9    25   2                                3814697003481               173593      ~   1 s
10   29   2                              420707232251625              1001603      ~   6 s
11   29   2                            12200509761511525              5864750      ~  40 s
12   29   2                           353814783188691825             34769374      ~   5 mins
13   29   2                         10260628712891493325            208267320      ~  30 mins
14   37   2                       9012061295994739864233           1258579654   Est.   3 hours
15   37   2                     333446267951814233346669           7663720710   Est.  20 hours
16   37   2                   12337511914217162067306945          46976034379   Est.   6 days
17   37   2                  456487940826035138224277733         289628805623   Est.  40 days
18   53   2             10888439761782913818653903872953        1794932468571   Est. 200 days
19   53   2            577087307374494432392024159626573       11175157356522   Est.   4 years
20   53   2          30585627290848204916790749477648625       69864075597643   Est.  30 years
21   53   2        1621038246414954860589963598385138149      438403736549145   Est. 200 years
22   53   2       85915027059992607611268286218691365993     2760351032959050   Est.   1 millennium
23   53   2     4553496434179608203397220031607758574013    17433869214973754   Est.   7 millennia
24   53   2   241335311011519234780052665123279669128225   110420300879752990   Est.  50 millennia

```

* Time estimates are for my desktop and do not take into account Moore's law.

By way of comparison, the primitive loop approach gets a count of 256 with `d`, `m`, `i`

```
115792089237316195423570985008687907853269984665640564039457584007913129639937 2 [encoded data, 19651 characters]

```
> 3 votes

# Answer
## GolfScript, arbitrary score

```
~:l 2:m.@?):d\1 l,{m\)?d-*}/abs.{1 m 3$)?-*m@)?d-m(*/}+l,/]' '*

```

This takes an integer on stdin and outputs a sequence with that many loops, in the input format of the Python tester. The online demo runs it for `l = 4` and produces output `17 2 1755 117 405 1365 26325`; this fork of the tester verifies it.

### Explanation

In order to keep it simple, I restricted the analysis to *primitive loops*: ones with only one division.

```
(x -> mx + i)^n = (x -> m^n x + (m^n - 1)/(m-1) i)

```

so this means that I'm looking for solutions to

```
m^n x + (m^n - 1)/(m - 1)i = dx

```

or

```
(m^n - d) x + (m^n - 1)/(m - 1)i = 0

```

When `n > 0, m > 1, m^n - d != 0` this has exactly one solution for `x`. `m - 1 > 0` and `m^n - 1 > 0`, so in order for the solution to be positive we require `m^n - d < 0`, and in order for the solution to be an integer we require `d - m^n` to be a factor of `(m^n - 1)/(m - 1)i`.

The rest may already be obvious. We pick the desired score, `l`. We're going to find primitive loops of length `1` to `l`, so we want `d - m^l > 0`. To get a smallish output we pick `m = 2, d = 2^l + 1`. Then to get an easy guarantee of the divisibility constraints we pick `i` to be the absolute value of `(m - d)(m^2 - d)...(m^l - d)`.
> 8 votes

# Answer
# Python 3, (d = 2, m = 3, i = 96521425) → Score = 2369

The program below writes the output to `collatz.txt`, and also prints summaries to the shell.

I used the observation that, if `(d, m, i)` had a lot of loops, then in general `(d, m, i*k)` also tended to have a lot of loops for different values of `k`. I started with `(2, 3, 13)`, and eventually worked `i` up like so:

```
13 -> 65 -> 1235 -> 35815 -> 250705 -> 2757755 -> 13788775 -> 96521425

```

before ending up with the lengthy output that can be found here.

The respective scores of the above chain are (using a bound of `10000`):

```
10 -> 16 -> 28 -> 146 -> 304 -> 535 -> 766 -> 1094

```

2369 was obtained by bumping the bound up to `100000`.

This raises a question similar to the one that @orlp has brought up — if I keep doing this multiplication process, will I always be able to get more and more loops? If anyone can prove that, then they'd probably win :)

```
from collections import defaultdict
import itertools

def f(d, m, i, bound=1000):
    D = defaultdict(set)
    S = set()

    for j in range(1, bound):
        A = [j]
        B = {j}

        for _ in range(bound):
            if j > bound**3:
                break

            if j % d == 0:
                j //= d

            else:
                j = j*m + i

            if j in B:
                S.add(min(A[A.index(j):]))
                break

            A.append(j)
            B.add(j)

    return S

N = 1000
THRESHOLD = 0
BOUND = 10000

MULTIPLIER = 96521425

with open("collatz.txt", "w") as outfile:
    for d, m, i in itertools.product([2], [3], range(1, N)):
        result = f(d, m, MULTIPLIER*i, bound=BOUND)

        if len(result) > THRESHOLD:
            print(d, m, MULTIPLIER*i, " ".join(map(str, sorted(result))), file=outfile, flush=True)
            print(d, m, MULTIPLIER*i, len(result))

```

---

*(Proof in progress for a possibly different arbitrary score method)*

Pick `d`, `m`, `i` such that `d` and `i` are coprime and suppose we have a loop for `(d, m, i)`:

```
a_0 -> a_1 -> a_2 -> ... -> a_(n-1) -> a_n = a_0

```

Now pick `k` coprime to `i` and `d`, and we want to look at `(d, m, i*k)`. Consider the number `k*a` for some `a`.

* If `d` divides `a` then `d` divides `k*a`, and in this case we map `k*a -> k*a/d = k*(a/d)`.
* Otherwise, `d` can't divide `k*a` since `d` and `k` are coprime, and we map `k*a -> m*(k*a) + i*k = k*(m*a + i)`.

Hence one step for `a` in `(d, m, i)` is equivalent to one step for `k*a` in `(d, m, i*k)`. This forms a bijection between the loop in `(d, m, i)` with the loop

```
k*a_0 -> k*a_1 -> k*a_2 -> ... k*a_(n-1) -> k*a_n = k*a_0

```

in `(d, m, i*k)`.

This means that `(d, m, i*k)` has at least as many loops as `(d, m, i)`. But since `i` is coprime to `d`, we can apply the same reasoning to any loops in `(d, m, k)`.

(This explains why the multiplication method managed to give at least as many loops each time, but the proof is incomplete until I can constrain `i`, `k` such it *always* gives strictly more loops each time).
> 4 votes

---
Tags: code-challenge, math, number, sequence
---


title: Finding Symmetries in Squares

text:
# Question
Title: Finding Symmetries in Squares
Write a program or function that takes in a list of positive integers. Each of these integers represents the side length of a square on a 2D plane. Each square can be moved to any integer coordinates in the plane, but it can't rotate and it can't overlap other squares.

Using a different printable ASCII character for each square (excluding space which is used for emptiness) your program/function needs to print any single arrangement of the squares that has a horizontal or vertical line of reflectional symmetry. If no such arrangement exists then nothing should be printed.

The squares are different characters just so they can be told apart. Only the shape made by the union of all the squares needs to be symmetrical. You can assume the list will not contain more than 94 elements (as there are 94 characters).

For example, if the input was `[2, 1, 2, 2, 2]`, a possible output is:

```
DD--
DD--
Z
FFPP
FFPP

```

This shape has a horizontal line of reflectional symmetry; its top and bottom halves are mirror images. Here are some other possibilities: (Note that the squares don't need to touch and any characters can be used as long as no two squares are made of the same character.)

```
  55
  55
  %%
  %%
@
  HH
  HH
  ((
  ((
```

```
       G

     11 33
     11 33

    22   44
    22   44
```

The line of symmetry could also be the boundary between characters, e.g. for `[2, 4]`:

```
!!!!
!!!!  ++
!!!!  ++
!!!!

```

Some sets of squares are impossible to arrange symmetrically, e.g. `[1, 2, 3]`:

```
AAA BB C
AAA BB         (these can't be vertically or horizontally symmetric => no output)
AAA

```

And remember that the overall shape may be symmetric even if the square boundaries aren't. e.g. a valid output for `[2, 1, 1, 1, 1, 4]` is:

```
AA----
AA----
BC----
DE----

```

Similarly, a valid output for `[1, 1, 2, 3, 5]` is:

```
44444
44444
44444
44444
44444
33301
33322
33322

```

# Notes

* The input list will always have from 1 to 94 elements.
* Take input in any reasonable way: stdin, command line, text file, function arg. It can be slightly formatted to suit your needs, e.g. `{1, 2, 3, 4}` or `[1 2 3 4]`.
* Output to stdout or similar. Any amounts of leading/trailing spaces or newlines are fine as long as the resulting shape has the line of symmetry.
* A diagonal line of symmetry does not count (else this would be super easy). Also, it has to be reflectional symmetry, not rotational or transitional.
* I'm honestly not sure how computationally difficult this task is. You may post partial answers that solve some subset of the problem (especially if you want to show off a particularly clever algorithm). These are not eligible to win.
    + For example, you might assume that the input always has at least one symmetrical arrangement (so lists like `[1, 2, 3]` are never input).
    + Or, for example, you may only consider arrangements where the square boundaries, as well as the overall shape, are symmetrical. In this case, `[1, 1, 2, 3, 5]` would have no output.
    + If you want to go crazy, you could extend the idea to rectangles or even polyominoes.

# Scoring

Your score is the size of your program in bytes. The lowest score wins. Tiebreaker goes the the answer posted first.

# Answer
> 4 votes
# Python 2, ~~460~~ ~~452~~ 437 bytes

```
exec"""def f(L):
 if[]==L:
  X{2}[map(" ".__lt__,q)for q in G]);Z{2}zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x)
 for n in range(T*T):
  i=n%T;j=n/T
  if all({1}=" "{0}):
{0}:{1}chr(32+len(L))
   r=f(L[:-1])
{0}:{1}" "
   if r:return r""".format("   for a,b in[(a,b)for a in R for b in R]","G[i+a][j+b]=","=filter(sum,")
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)

```

Only mildly golfed for now, but here's something to get things started. I tried using `exec` for lines 10 and 12, but for some reason it didn't let me.

Input the list `L` via STDIN, e.g. `[2, 1, 2, 2, 2]`. The program simply tries every possibility of placing squares in a `sum(L) x sum(L)` grid.

Sample output (blank lines removed for compactness):

```
[2, 1, 2, 2, 2]

%%
%%
$$
$$
"
##
##
!!
!!

[2, 4]

""""
""""
""""
""""
 !!
 !!

[2, 1, 1, 1]

$!!
#!!
 "

[1, 1, 2, 3, 5]

%%%%%
%%%%%
%%%%%
%%%%%
%%%%%
$$$##
$$$##
$$$"!

[1, 4, 1, 8]

$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
$$$$$$$$
# """" !
  """"
  """"
  """"

[8, 1, 4, 1]

$   !!!!!!!!
    !!!!!!!!
####!!!!!!!!
####!!!!!!!!
####!!!!!!!!
####!!!!!!!!
    !!!!!!!!
"   !!!!!!!!

(The algorithm starts placing from the last square first, prioritising left then up)

```

---

Slightly less confusing version (452 bytes):

```
def f(L):
 if[]==L:
  X=filter(sum,[map(" ".__lt__,q)for q in G]);Z=filter(sum,zip(*X));C=Z==Z[::-1]or X==X[::-1]
  if C:print"\n".join(map("".join,G))
  return C
 x=L[-1];T=S-x+1;R=range(x);V=[(a,b)for a in R for b in R]
 for n in range(T*T):
  i=n%T;j=n/T
  if all(G[i+a][j+b]<"!"for a,b in V):
   for a,b in V:G[i+a][j+b]=chr(32+len(L))
   r=f(L[:-1])
   for a,b in V:G[i+a][j+b]=" "
   if r:return r
L=input()
S=sum(L)
G=[S*[" "]for _ in[0]*S]
f(L)

```

---
Tags: code-golf, ascii-art, geometry, printable-ascii, packing
---


title: Summing colored graphs

text:
# Question
Title: Summing colored graphs
In some cases, often in physics, you have to sum graphs. Your challenge is to write, in a language of your choice, a program or function that takes multiple graphs as images, calculates all possible sums, and outputs the result.

## Graphs

The graphs are images that contain a white (`rgb(255, 255, 255)`) background with a non-white pixel in each column. Examples:

The values of the script are represented as the Y positions of the colored pixels. The value at a certain X coordinate is equal to the Y position of the uppermost colored pixel in that column, with coordinates starting from 0 at the bottom left. There may or may not be additional colored pixels below those pixels for aesthetical reasons.

## Task

Your task is to write, in a language of your choice, a program or function that takes multiple graphs as images, calculates all the possible `2^n - 1` sums, and outputs the result.

A sum of graphs is a graph where each column's value is equal to the sum of the values of the corresponding column in each of the input graphs.

The graphs will come in multiple colors. The result image must contain all possible sums of the graphs as other graphs, including the original graphs but excluding the zero sum.

The color of each sum is determined by the average of the colors of the graphs included, for example, graphs of colors `rgb(255, 0, 255)` and `rgb(0, 255, 255)` would produce a graph of `rgb(128, 128, 255)` (may also be rounded down).

The resulting image should be as high as required to fit all graphs. This means you may have to output an image larger than any of the inputs.

The order in which the resulting graphs are drawn to the resulting image does not matter, i.e. if result graphs overlap, you may choose which one is on top, but it has to be one of the graphs, not a combination of their colors.

You may assume that the input images are of equal width, that all columns of the images have at least one non-white pixel, and that the heights of the images (including output) are below 4096 pixels.

## Example

Input A:

Input B:

Example output:

(In case someone is interested, I copy-pasted the data for these from random companies' stock charts. That was the first way I found to get realistic data as CSV.)

## Rules

* You may choose any bitmap image input file format.
* You may choose any bitmap image output file format, which doesn't have to match the input.
* You may use image processing libraries, however any functions to complete this task directly are banned.
* Standard loopholes apply.
* This is , so shortest code in bytes wins.

## Graph generator script

Here is a Python 2 script that generates graphs. Input is given in lines, with the three first lines as the RGB color and the rest as data, terminated by EOF.

```
import PIL.Image as image
import sys

if len(sys.argv) < 2:
    sys.stderr.write("Usage: graphgen.py <outfile> [infile]")
    exit(1)
outfile = sys.argv[1]
if len(sys.argv) > 2:
    try:
        stream = open(sys.argv[2], "r")
        data = stream.read()
        stream.close()
    except IOError as err:
        if err.errno == 2:
            sys.stderr.write("File \"{0}\" not found".format(sys.argv[2]))
        else:
            sys.stderr.write("IO error {0}: {1}".format(err.errno, err.strerror))
        exit(1)
else:
    data = sys.stdin.read()

try:
    items = map(int, data.strip().split("\n"))
    red, green, blue = items[:3]
    items = items[3:]
    highest = max(items)
except (ValueError, TypeError, IndexError):
    sys.stderr.write("Invalid value(s) in input")

img = image.new("RGB", (len(items), highest + 1), (255, 255, 255))

prev = items[0]
img.putpixel((0, highest - items[0]), (red, green, blue))
for x, item in enumerate(items[1:]):
    img.putpixel((x + 1, highest - item), (red, green, blue))
    if item < prev:
        for i in range(item + 1, prev):
            img.putpixel((x, highest - i), (red, green, blue))
    else:
        for i in range(prev + 1, item):
            img.putpixel((x + 1, highest - i), (red, green, blue))
    prev = item

img.save(outfile, "png")

```

# Answer
## MATLAB, 405

Call via: `f('https://i.stack.imgur.com/ffCzR.png','https://i.stack.imgur.com/zHldg.png')`

```
function f(varargin)
for k=1:nargin
i=im2double(imread(varargin{k}))
V(k,:)=size(i,1)-cellfun(@(V)find(any(V~=1,3),1),num2cell(i,[1,3]))
C(k,:)=i(find(any(i(:,1,:)~=1,3),1),1,:)
end
s=2^nargin-1
G=dec2bin(1:s)-'0'
C=bsxfun(@rdivide,G*C,sum(G,2))
V=G*V
m=max(V(:))
r=ones(m+1,size(V,2))
g=r
b=r
for i=1:s
M=bsxfun(@eq,(m:-1:0).',V(i,:))
r(M)=C(i,1)
g(M)=C(i,2)
b(M)=C(i,3)
end
imwrite(cat(3,r,g,b),'S.png')

```
> 3 votes

# Answer
# Python, 422

Call from commandline `python plotsum im1.png im2.png im3.png`

```
import sys
from numpy import*
from scipy import misc as m
R=m.imread
r=range
a=array
N=sys.args[1:]
L=len(N)
P=[map(argmin,R(n,1).T)for n in N]               #converts image to list of heights, counting from the top
C=a([R(N[i])[P[i][0],0,:]for i in r(L)])         #finds and stores the colour
P=a([len(R(N[i]))-a(P[i])for i in r(L)])         #flips the numbers, measures actual heights from bottom
w=len(P[0])
h=max(sum(P,0))+1                                    #compute dimensions
G=ones((h,w,3))*255                                  #and make a white grid
for i in r(1,2**L):
 z=where(a(list(bin(i)[2:].zfill(L)))=='1');y=sum(P[z],0)    #sum the graphs
 for x in r(w):G[y[x],x,:]=average(C[z],0)                   #average the colours
m.imsave('S.png',G[::-1])                            #flip image vertically and save

```

Example output
Another example

That was a tricky one, high-level array operations and using arrays as indices helps a lot here. I dont expect to see solutions under 1000 bytes except in Mathematica and Matlab
> 4 votes

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


title: Words of centuries

text:
# Question
Title: Words of centuries
I'd like to get a list of words that are strongly connected with a particular time epoch, for example, 19th century, 20th century and 21st century. I suspect that nobody used a word like "smartphone" in 19th and 20th century, and, vice versa, nobody still uses a word like "grubble" anymore in 21th century.

# Input data

I have quite a few books, laid out in a following directory structure:

* On the first level, you have directories named after years when book was published, i.e. from `1801` to `2015`.
* On the following levels, there could be individual book files or any number of nested directories (for example, grouping books by authors, by genres, by publishers, etc). Ultimately, there's at least a single book inside every such directory. Let's say that names of these files and directories are limited by whatever's allowed on VFAT filesystem (i.e. `\` `/` `:` `*` `?` `"` `<` `>` `|` are not allowed).

No other files exist in this structure (for example, a program file would be located elsewhere, no results of previous runs, temporary files, etc).

All book files have the same pure text format, using only ASCII character set. Words are continuous non-empty character sequences of word characters, i.e. `[A-Za-z0-9_]+`.

> For example, contents of this short book:
>
> `Here you go, that's APL13-X for your 4923/YR_3.`
>
> have the following words: `Here`, `you`, `go`, `that`, `s`, `APL13`, `X`, `for`, `your`, `4923`, `YR_3`.

Comparison of words is *case insensitive*, that is `Here`, `here` and `HERE` is the same word.

# The task

I want to have a program that, being started in a top directory of this structure, would generate 3 files named `19`, `20`, `21`. Each of these files should contain a list of words which occur only in relevant century books and not in any other century's single book (words separated with a newline). Words can be in any case, but all words given in such file must appear only once.

# Sample test cases

If you want a sample test case, feel free to use my one, available either as zip file or git repo.

# Scoring

Standard code golf rules apply. Shortest answer (written in a language released before 2015-03-16) wins after 3 weeks would pass (on 2015-04-06). Secondary nominations are "shortest answer in any non-esoteric, general purpose language" and "shortest answer per language".

**P.S.** Please note that "19th century" is defined as 1801..1900 inclusive, that is `1900` is still 19th.

# Answer
> 0 votes
# Ruby, 231 bytes

```
require'set'
m=[]
Dir['**/*'].map{|n|(m[(n[0..3].to_i-1)/100-18]||=Set.new).merge(IO.read(n).split(/\W/).map{|x|x.upcase})rescue''}
u=[m[0]-m[1]-m[2],m[1]-m[0]-m[2],m[2]-m[0]-m[1]]
3.times{|i|IO.write"#{i+19}",u[i].to_a.join("\n")}

```

In slighty more readable form with comments, with lvalues extracted:

```
require'set'
m = []
Dir['**/*'].map { |n|
  # Determine century from first 4 characters of path
  c = (n[0..3].to_i - 1) / 100
  # Make array indices 1 char long (0-1-2) instead of 2 chars (19-20-21)
  c -= 18
  # Initialize per-century array entry with empty set, if required
  m[c] ||= Set.new
  # Read file as a string, split by words, uppercase everything
  # (not lowercase, because "upcase" saves 2 bytes vs "downcase"),
  # merge into the set we've prepared; ignore any possible exceptions
  # (i.e. trying to read the directory as a string)
  m[c].merge(IO.read(n).split(/\W/).map { |x| x.upcase }) rescue ''
}

# New array of sets with unique words per century
u = [
  m[0] - m[1] - m[2],
  m[1] - m[0] - m[2],
  m[2] - m[0] - m[1]
]

# Output of this array entries, each to individual file
3.times { |i|
  IO.write "#{i + 19}", u[i].to_a.join("\n")
}

```

# Answer
> 1 votes
# R, ~~284~~ 266

Reads in every file from the specified working directory and uniquely adds their words to the appropriate century word vector. Each word vector is compared to the others and the words that are not in are written out.

```
C=as.character;S=strsplit;L=tolower;U=unlist;W=list();for(f in list.files(r=T)){Y=C((strtoi(U(S(f,'/'))[1])-1)%/%100+1);W[[Y]]=unique(L(c(W[[Y]],U(S(scan(f,w=C()),'[^A-Za-z0-9_]',p=T)))))};for(i in 1:3)cat(W[[i]][!L(W[[i]])%in%L(U(W[-i]))],file=names(W)[i],sep='\n')

```

**Caveats:**

* Assumes the current directory is pointing in the right place. Otherwise use `setwd()`
* There must be at least one file per century and no additional files outside the 19th, 20th and 21st centuries.

In a more readable form

```
setwd("some/directory/here");
# Commonly used functions
C=as.character;
S=strsplit;
L=tolower;
U=unlist;
# Initialise word list
W=list();
# for each file in working directory
for(f in list.files(r=T)){
    # Determine century from first part of path.
    Y=C((strtoi(U(S(f,'/'))[1])-1)%/%100+1);
    # Scan the file splitting on non letters/numbers/underscore
    # refreshing the unique list of words for the century
    W[[Y]]=unique(L(c(W[[Y]],U(S(scan(f,w=C()),'[^A-Za-z0-9_]',p=T)))))
    };
# Write out the words for each century that aren't in the other centuries
for(i in 1:length(W))
    cat(W[[i]][!L(W[[i]])%in%L(U(W[-i]))],file=names(W)[i],sep='\n')

```

# Answer
> 0 votes
# Shell script (reference solution, 879 bytes)

```
#!/bin/sh

# This program uses temporary files, but no need to perform any kind
# of cleanup in a real answer.

# Given a stream of lines on the stdin, rejects all lines that match
# lines in a file given in first argument. Both stdin stream and a
# given file must be sorted the same way.
reject()
{
    diff -u - "$1" | grep '^-' | cut -c2- | sed 1d
}

# Collect lists of words
for YEAR in ????; do
    CENTURY=$((($YEAR - 1) / 100 + 1))
    find "$YEAR" -type f -print0 |
        xargs -0 sed 's/\(.*\)/\L\1/g; s/[^A-Za-z0-9_]/\n/g;' >>words_$CENTURY
done

# Make lists unique and sorted
for C in 19 20 21; do
    sort -u <words_$C >words_unique_$C
done

# Output results
cat words_unique_19 | reject words_unique_20 | reject words_unique_21 >19
cat words_unique_20 | reject words_unique_19 | reject words_unique_21 >20
cat words_unique_21 | reject words_unique_19 | reject words_unique_20 >21

```

# Answer
> 0 votes
# Shell script, 233 bytes

```
J(){
diff -u - $1|grep ^-|cut -c2-|sed 1d
}
for Y in *; do
C=$(((Y-1)/100-18))
find $Y -type f -exec sed 's/\(.*\)/\L\1/;s/[^A-Za-z0-9_]/\n/g' {} +>>W$C
done
S(){
sort -u
}
S<W0>A
S<W1>B
S<W2>C
J B<A|J C>19
J A<B|J C>20
J A<C|J B>21

```

Basically a very compressed version of reference solution. Everything that could be replaced with 1-letter name was replaced. Still works in minimal sh.

---
Tags: code-golf, string, regular-expression, file-system
---


title: The Nano Core War

text:
# Question
Title: The Nano Core War
This is an adaption of Core War, a programming KOTH dating back to the 20th century. To be more specific, it is using an incredibly simplified instruction set primarily based off of the original proposal.

## Background

In Core War, there are two programs battling for control over the computer. The goal of each program is to win by locating and terminating the opposing program.

The battle takes place within the main memory of the computer. This memory is called the Core, and it contains 8192 addresses. When the battle starts, the code for each competitor (called a warrior) is placed in a random chunk of memory. Program execution alternates between warriors, performing one instruction of each. Each instruction is capable of modifying a part of the Core, leading to the possibility of self-modifying programs.

The goal is to terminate the opposing program. A program terminates when it attempts to execute an invalid instruction, which is any `DAT` instruction.

# The Instruction Set

Each program consists of a series of low-level instructions, each of which takes two fields, called the A and B fields.

This instruction set draws heavily from the original spec. The main changes are 1) clarification on adding/subtracting commands, and 2) a change of the `#` addressing mode to allow it to be used anywhere. Most full versions of Core Wars have over 20 opcodes, 8 addressing modes, and a set of "instruction modifiers."

## Opcodes

Each instruction must have one of seven different opcodes.

* **`DAT A B`** \- (data) - This simply holds the numbers `A` and `B`. Importantly, a process dies when it attempts to execute a DAT instruction.
* **`MOV A B`** \- (move) - This moves the contents of memory location `A` to memory location `B`. Here is a demonstration of before-and-after:

```
MOV 2 1
ADD @4 #5
JMP #1 -1

```

```
MOV 2 1
JMP #1 -1
JMP #1 -1

```
* **`ADD A B`** \- (add) - This adds the contents of memory location `A` to memory location `B`. The two first fields of both are added, and the second fields are added.

```
ADD 2 1
MOV @4 #5
JMP #1 -1

```

```
ADD 2 1
MOV @5 #4
JMP #1 -1

```
* **`SUB A B`** \- (subtract) - This subtracts the contents of memory location `A` from (and stores the result into) memory location `B`.

```
SUB 2 1
MOV @4 #5
JMP #1 -1

```

```
SUB 2 1
MOV @3 #6
JMP #1 -1

```
* **`JMP A B`** \- (jump) - Jump to location `A`, which will be executed next cycle. `B` must be a number but does nothing (you can use it to store information, though).

```
JMP 2 1337
ADD 1 2
ADD 2 3

```

The jump means that `ADD 2 3` will be executed next cycle.
* **`JMZ A B`** \- (jump if zero) - If both fields of line `B` are 0, then the program jumps to location `A`.

```
JMZ 2 1
SUB 0 @0
DAT 23 45

```

Since the two fields of instruction 1 are 0, the DAT command will be executed next turn, leading to imminent death.
* **`CMP A B`** \- (compare and skip if not equal) - If the fields in instructions `A` and `B` are not equal, skip the next instruction.

```
CMP #1 2
ADD 2 #3
SUB @2 3

```

Since the two fields of instructions 1 and 2 are equal in value, the ADD command is *not* skipped and is executed next turn.

When two instructions are added/subtracted, the two fields (A and B) are added/subtracted pair-wise. The addressing mode and opcode are not changed.

## Addressing Modes

There are three kinds of addressing modes. Each of the two fields of an instruction has one of these three addressing modes.

* **Immediate `#X`** \- `X` is the line to be used directly in computation. For example, `#0` is the first line of the program. Negative lines refer to lines in the core before the start of program.

```
... //just a space-filler
...
ADD #3 #4
DAT 0 1
DAT 2 4

```

This will add the first of the two DAT lines to the second, since those are in lines 3 and 4, respectively. You would not want to use this code, however, because the DAT will kill your bot on the next cycle.
* **Relative `X`** \- The number `X` represents the location of a target memory address, relative to the current address. The number at this location is used in computation. If line `#35` is being executed and contains `-5`, then line `#30` is used.

```
... //just a space-filler
...
ADD 2 1
DAT 0 1
DAT 2 4

```

This will add the second DAT line to the first.
* **Indirect `@X`** \- The number `X` represent a relative address. The contents at that location are temporarily added to the number X to form a new relative address, from which the number is retrieved. If line `#35` is being executed, and its second field is `@4`, and the second field of line `#39` contains the number `-7`, then line `#32` is used.

```
... //just a space-filler
...
ADD @1 @1
DAT 0 1
DAT 2 4

```

This will add the first DAT to the second, but in a more convoluted way. The first field is @1, which gets the data from that relative address, which is the first field of the first DAT, a 0. This is interpreted as a second relative address from that location, so 1+0=1 gives the total offset from the original instruction. For the second field, @1 gets the value from that relative address (the 1 in the second field of the first DAT) and adds it to itself in the same way. The total offset is then 1+1=2. So, this instruction is executed similarly to `ADD 1 2`.

Each program can contain up to 64 instructions.

When a round starts, the two programs are placed randomly in a memory bank with 8192 locations. The instruction pointer for each program starts at the beginning of the program and is incremented after each execution cycle. The program dies once its instruction pointer attempts to execute a `DAT` instruction.

## Parameters of the Core

The core size is 8192, with a timeout of 8192\*8 = 65536 ticks. The core is cyclic, so writing to address 8195 is the same as writing to address 3. All unused addresses are initialized to `DAT #0 #0`.

Each competitor must not be longer than 64 lines. Integers will be stored as 32-bit signed integers.

## Parsing

In order to make programming easier for competitors, I will add a line-label feature to the parser. Any words that occur on a line before an opcode will be interpreted as line labels. For example, `tree mov 4 6` has the line label `tree`. If, anywhere in the program, there is a field that contains `tree` `#tree` or `@tree`, a number will be substituted. Also, capitalization is ignored.

Here is a example of how line labels are substituted:

```
labelA add labelB @labelC
labelB add #labelC labelC
labelC sub labelA @labelB

```

Here, labels A, B, and C are on lines 0, 1, and 2. Instances of `#label` will be substituted with the line number of the label. Instances of `label` or `@label` are substituted with the relative location of the label. Addressing modes are preserved.

```
ADD 1 @2
ADD #2 1
SUB -2 @-1

```

# Scoring

For each pair of contestants, every possible battle is performed. Since the outcome of a battle depends on the relative offsets of the two programs, every possible offset (about 8000 of them) is tried. Furthermore, each program has a chance to move first in each offset. The program that wins the majority of these offsets is the winner of the pair.

For each pair-up that a warrior wins, it is awarded 2 points. For each tie, a warrior is awarded 1 point.

You are allowed to submit more than one warrior. The typical rules for multiple submissions apply, such as no tag-teaming, no cooperating, no king-making, etc. There's not really any room for this in Core War anyways, so it shouldn't be a big deal.

# The Controller

The code for the controller, along with two easy example bots, is located here. Since this competition (when run using the official settings) is completely deterministic, the leaderboard you create will be the exact same as the official leaderboard.

## Example Bot

Here is an example bot that demonstrates some features of the language.

```
main mov bomb #-1
     add @main main
     jmp #main 0
bomb dat 0 -1

```

This bot operates by slowly erasing all other memory in the core by replacing it with a "bomb." Since the bomb is a `DAT` instruction, any program which reaches a bomb will be destroyed.

There are two line labels, "main" and "bomb" which serve to replace numbers. After preprocessing, the program looks like this:

```
MOV 3 #-1
ADD @-1 -1
JMP #0 0
DAT 0 -1

```

The first line copies the bomb to the line immediately above the program. The next line adds the value of the bomb (`0 -1`) to the move command, and it also demonstrates a use of the `@` addressing mode. This addition causes the move command to point to a new target. The next command unconditionally jumps back to the start of the program.

---

# Current Leaderboard

> 24 - Turbo
> 22 - DwarvenEngineer
> 20 - HanShotFirst
> 18 - Dwarf
> 14 - ScanBomber
> 10 - Paranoid
> 10 - FirstTimer
> 10 - Janitor
> 10 - Evolved
> 6 - EasterBunny
> 6 - CopyPasta
> 4 - Imp
> 2 - Slug

Pairwise Results:

```
Dwarf > Imp
CopyPasta > Imp
Evolved > Imp
FirstTimer > Imp
Imp > Janitor
Imp > ScanBomber
Slug > Imp
DwarvenEngineer > Imp
HanShotFirst > Imp
Turbo > Imp
EasterBunny > Imp
Paranoid > Imp
Dwarf > CopyPasta
Dwarf > Evolved
Dwarf > FirstTimer
Dwarf > Janitor
Dwarf > ScanBomber
Dwarf > Slug
DwarvenEngineer > Dwarf
HanShotFirst > Dwarf
Turbo > Dwarf
Dwarf > EasterBunny
Dwarf > Paranoid
Evolved > CopyPasta
FirstTimer > CopyPasta
Janitor > CopyPasta
ScanBomber > CopyPasta
CopyPasta > Slug
DwarvenEngineer > CopyPasta
HanShotFirst > CopyPasta
Turbo > CopyPasta
CopyPasta > EasterBunny
Paranoid > CopyPasta
Evolved > FirstTimer
Evolved > Janitor
ScanBomber > Evolved
Evolved > Slug
DwarvenEngineer > Evolved
HanShotFirst > Evolved
Turbo > Evolved
EasterBunny > Evolved
Paranoid > Evolved
Janitor > FirstTimer
ScanBomber > FirstTimer
FirstTimer > Slug
DwarvenEngineer > FirstTimer
HanShotFirst > FirstTimer
Turbo > FirstTimer
FirstTimer > EasterBunny
FirstTimer > Paranoid
ScanBomber > Janitor
Janitor > Slug
DwarvenEngineer > Janitor
HanShotFirst > Janitor
Turbo > Janitor
Janitor > EasterBunny
Janitor > Paranoid
ScanBomber > Slug
DwarvenEngineer > ScanBomber
HanShotFirst > ScanBomber
Turbo > ScanBomber
ScanBomber > EasterBunny
ScanBomber > Paranoid
DwarvenEngineer > Slug
HanShotFirst > Slug
Turbo > Slug
EasterBunny > Slug
Paranoid > Slug
DwarvenEngineer > HanShotFirst
Turbo > DwarvenEngineer
DwarvenEngineer > EasterBunny
DwarvenEngineer > Paranoid
Turbo > HanShotFirst
HanShotFirst > EasterBunny
HanShotFirst > Paranoid
Turbo > EasterBunny
Turbo > Paranoid
Paranoid > EasterBunny

```

The latest update (new versions of Turbo and Paranoid) took about 5 minutes to run on an old laptop. I would like to thank Ilmari Karonen for his improvements to the controller. If you have a local copy of the controller, you should update your files.

# Answer
> 11 votes
# Dwarven Engineer

A new and improved Dwarf. Wins against everything else submitted so far. The fancy corestep-optimized step size is probably overkill here.

```
        MOV bomb    @aim
aim     MOV bomb    @-6326
        SUB step    aim
step    JMZ #0      6328
        MOV 0       1
bomb    DAT 0       3164

```

Notable features include the fast bombing loop that throws two bombs in four cycles, for an average bombing speed of 0.5c in old Core War jargon, and the use of `JMZ` to detect when the bombing run is complete and it's time to switch to plan B (here, an Imp).

---

I used to play Core War back in the 90's (some of you may have seen the basic guidebook I wrote back in '97), so I thought it would be interesting to see which old strategies from the RedCode '88 / '94 world might be useful in this variant.

My first thoughts were:

* There's no `SPL`, thus no replicators (and no imp rings/spirals). This should make bombers strong. (Also, all those fancy bombing strategies designed to deal with replicators and imp spirals? Totally needless and useless here. Just bomb with any `DAT`s.)
* Then again, `CMP` scanning is still potentially faster than bombing, so a fast scanner *could* have a chance.
* The absence of in/decrements makes core clears very slow. In fact, a core clear in this variant is pretty much just a bomber with a (suboptimal) step size of ±1. Again, this also hurts scanners; a one-shot scanner → bomber strategy *might* work, though.
* Quickscanners / quickbombers (an early-game strategy using an unrolled scanning / bombing loop, for those not so familar with Core War jargon) are still potentially useful, but only against long programs (which they themselves are, so there's a kind of a feedback effect here). Hard to say if it's really worth the trouble.
* The scoring system is interesting. Ties score half as much points as a win (rather than 1/3, as in traditional Core War), making them more attractive. Then again, about the only program likely to score lots of ties under these rules is an imp. (Also, the absence of de/increments makes imp gates hard, so even simple imps actually *do* have a chance of scoring a tie if they reach their opponent alive.)
* Also, because the final rankings only depend on which programs you beat, and not how *much* you beat them by, it tends to favor generalist entries. It's better to just barely beat *all* of your opponents, than to totally destroy half of them and just barely lose to the rest.
* Because the code is public, it's *always* possible to find a program that can beat any given earlier submission — possibly even several of them — no matter how good they are in general. Such tricks (like tuning your step size to hit your opponent just before they hit you) can easily seem cheap, though. And, of course, the target player could always just submit a new version with different constants.

Anyway, the upshot of all this is that I decided that I should try to write either a fast bomber or a *very* fast scanner, and *maybe* tack a quickscanner/bomber onto it. Out of those options, a fast bomber seemed the simplest and most likely to work.

At that point, I spent way too much time tweaking and optimizing PhiNotPi's interpreter code, because I figured I'd probably be running lots of brute force trials to optimize the constants. As it happens, I never had to do that — the code above is pretty much the first version that actually worked (after a couple of failed attempts that just committed suicide due to silly bugs).

---

The trick that makes my bomber fast is using indirect addressing to throw two bombs for each `ADD`. Here's how it work:

1. On the first cycle, we execute `MOV bomb @aim`. This copies the `bomb` instruction to whereever in the core the B-field of `aim` points to (initially, exactly 6326 instructions before `aim`, or 6328 instructions before `step`; you'll see why those numbers matter later).
2. On the next step, we execute the `aim` instruction itself! On the first pass, it looks like this: `MOV bomb @-6326`. Thus, it copies `bomb` to the location that the B-field of the instruction at 6326 lines before itself points to.

So, what is there at 6326 lines before `aim`? Why, it's the copy of `bomb` we just placed there one cycle earlier! And we just happened to arrange things so that the B-field of `bomb` has a non-zero value, so the new bomb will not be copied on top of the old one, but some distance away (in fact, here the distance is 3164, which is half of our nominal step size 6328; but other offsets could work, perhaps even better).
3. On the next cycle, we adjust our aim with `SUB step aim`, which subtracts the values of the `step` instruction (which also happens to be the jump we're going to execute next, although it *could've* been just a simple `DAT` somewhere) from `aim`.

(One detail to note here is that we *kind of* want the A-value of `step` to be zero, so that we'll still throw the same bombs on the next iteration. Even that isn't strictly necessary, though; only the bombs thrown by the *first* instruction need to have their B-field equal to 3164, the rest can be anything.)
4. Next, the `JMZ` check that the instruction 6328 steps away from it is still zero, and if so, jumps back to the top of the code. Now, 6328 is the step size of our bomber, and is divisible by 8 (but not 16); thus, if we just kept throwing bombs every 6328 steps, we'd eventually get back to where we started, having bombed every eighth instruction in the core (and with the extra bombs offset by 3163 = 6328/2 ≡ 4 (mod 8), we would've hit every *fourth* instruction).

But we started our bombing run at 6328 instructions *before* the `JMZ`, and stepped backwards by -6328 at every iteration, so we're going to bomb the location 6328 steps *after* the `JMZ` just one iteration before we would hit the `JMZ` itself. So when the `JMZ` detects a bomb at 6328 instructions after it, that's a sign that we've covered as much of the core as we can without hitting ourself, and should switch to a backup strategy before we kill ourself.
5. As for the backup strategy, it's just a plain old `MOV 0 1` imp, because I couldn't think of anything better for now. The way I see it, if we've bombed every fourth location of the core and still haven't won, we're probably fighting something very small or very defensive, and might as well just try to survive and settle for a tie. It's OK, because such small or defensive programs generally aren't very good at killing anything else, and so even if we only win a few fights by chance, we'll probably still come out ahead.

---

**Ps.** ~~In case anyone else wants it, here's my slightly improved fork of PhiNotPi's tournament code. It's about twice as fast, saves old battle results so that you don't need to re-run them, and fixes what I believe to be a minor bug in the battle results calculation.~~ The changes have been merged into the mainline version by PhiNotPi. Thanks!

# Answer
> 11 votes
# Turbo

```
main   add three target
test   jmz -1 @target
bomb   mov three @target
       sub j1 target
       mov jump @target
       sub j1 target
       mov copy @target
       sub j1 target
two    mov decr @target
j1     jmp @target 1
target dat -8 -8
decr   sub #two 3
copy   mov 2 @2
jump   jmp -2 0
three dat -9 -9

```

My 2nd ever CoreWar attempt. Designed to beat Dwarf. Scans by 3's for data, then puts a bomb every 2. Each stage runs in only 3 instructions, in a hope that Dwarf's bombs miss it.

**NEW Turbo++**: Now enhanced. It scans backward until it finds data, then moves itself there, then bombs backward. The hope is that the move either clobbers the opponent, or is to a place already bombed and therefore safe(ish).

...And an edit to make it scan more sparsely makes it beat everyone!

# Answer
> 9 votes
# Dwarf

A common and simple program that represents a dwarf throwing stones. It places a `DAT` instruction every four addresses.

```
add 2 3
mov 2 @2
jmp -2 #4
dat #0 #4

```

EDIT: Fixes addressing. Apparently the addressing modes are different from the spec the OP linked to.

# Answer
> 9 votes
# Graph View

This can be used as a debugging tool. It displays the core and shows the location of the player. To use it you have to call it from code. I have also provided a modifed `Game.java` that automatically displays the GraphView.

PhiNotPi and Ilmari Karonen recently changed the Controller. Ilmari Karonen has been kind enough to provide an updated GameView at this location.

```
import javax.swing.*;
import java.awt.*;

public class GameView extends JComponent{

    final static Color[] commandColors = new Color[]{
            Color.black, //DAT
            Color.blue,  //MOV
            Color.blue,  //ADD
            Color.blue,  //SUB
            Color.blue,  //JMP
            Color.blue,  //JMZ
            Color.blue,  //CMP
    };

    final static Color[] specialColors = new Color[]{
            new Color(0,0,0),
            new Color(190, 255, 152),
            Color.yellow,
            new Color(0, 93, 14),
            new Color(96, 92, 4),
            new Color(0, 93, 14),
            new Color(96, 92, 4),
            new Color(0, 93, 14),
            new Color(96, 92, 4)
    };

    final static Color playerOneColor = Color.green;
    final static Color playerTwoColor = Color.white;

    final Game game;

    int playerOneLocation;
    int playerTwoLocation;

    final static int width = 128;
    final static int height = 64;

    public GameView(Game game) {
        this.game = game;
    }

    @Override
    public void paint(Graphics g) {
        int pixelWidth = getSize().width;
        int pixelHeight = getSize().height;
        if (width > pixelWidth){
            pixelWidth = width;
            setSize(width, pixelHeight);
        }
        if (height > pixelHeight){
            pixelHeight = height;
            setSize(pixelWidth, height);
        }
        int squareWidth = Math.min(pixelWidth / width, pixelHeight / height);
        for (int x = 0; x < squareWidth * width; x += squareWidth){
            for (int y = 0; y < squareWidth * height; y += squareWidth){
                int index = (y / squareWidth) * width + (x / squareWidth);
                Color color = commandColors[game.core[index][0]];
                if (game.coreData[index] != 0){
                    color = specialColors[game.coreData[index]];
                }
                if (index == playerOneLocation){
                    color = playerOneColor;
                }
                if (index == playerTwoLocation){
                    color = playerTwoColor;
                }
                g.setColor(color);
                g.fillRect(x, y, squareWidth, squareWidth);
            }
        }
    }

    public void setLocations(int p1loc, int p2loc){
        this.playerOneLocation = p1loc;
        this.playerTwoLocation = p2loc;
    }
}

```

Modified Game.java:

```
import javax.swing.*;
import java.util.Random;
import java.util.ArrayList;
import java.util.Arrays;
/**
 * This runs a game of Core Wars between two players.  It can be called mutiple times.
 *
 * @author PhiNotPi
 * @version 3/10/15
 */
public class Game
{
    final Player p1;
    final Player p2;
    final int coreSize;
    final int coreSizeM1;
    final int maxTime;
    final int debug;
    public int[][] core;
    public int[] coreData; //Used in debugging.
    int offset1;
    int offset2;
    Random rand;
    ArrayList<int[]> p1code;
    ArrayList<int[]> p2code;
    int p1size;
    int p2size;
    GameView gameView;
    int time = 1000000; //Time in nanoseconds between frames
    public Game(Player A, Player B, int coreSize, int maxTime, int debug)
    {
        p1 = A;
        p2 = B;

        coreSize--;
        coreSize |= coreSize >> 1;
        coreSize |= coreSize >> 2;
        coreSize |= coreSize >> 4;
        coreSize |= coreSize >> 8;
        coreSize |= coreSize >> 16;
        coreSize++;

        this.coreSize = coreSize;
        this.coreSizeM1 = coreSize - 1;
        this.maxTime = maxTime / 2;
        this.debug = debug;
        core = new int[coreSize][5];
        rand = new Random();
        p1code =  p1.getCode();
        p1size = p1code.size();
        p2code =  p2.getCode();
        p2size = p2code.size();
        if (debug == 1){
            gameView = new GameView(this);
            JFrame frame = new JFrame("Game");
            frame.add(gameView);
            frame.setVisible(true);
            frame.setDefaultCloseOperation(WindowConstants.DISPOSE_ON_CLOSE);
            frame.setSize(128, 64);
            coreData = new int[coreSize];
        }
    }

    public int runAll()
    {
        int sum = 0;
        for(int i = 0; i < coreSize - p1size - p2size; i++)
        {
            sum += run(i) - 1;
        }
        if(sum > 0)
        {
            return 1;
        }
        if(sum < 0)
        {
            return -1;
        }
        return 0;
    }

    public int run()
    {
        return run(rand.nextInt(coreSize - p1size - p2size + 1));
    }

    public int run(int deltaOffset)
    {
        core = new int[coreSize][5];
        //offset1 = rand.nextInt(coreSize);
        offset1 = 0;
        for(int i = 0; i != p1size; i++)
        {
            //System.arraycopy(p1.getCode().get(i), 0, core[(offset1 + i) % coreSize], 0, 5 );
            int[] line = p1code.get(i);
            int loc = (offset1 + i) & coreSizeM1;
            core[loc][0] = line[0];
            core[loc][1] = line[1];
            core[loc][2] = line[2];
            core[loc][3] = line[3];
            core[loc][4] = line[4];
            if (debug != 0){
                coreData[loc] = 1;
            }
        }
        offset2 = offset1 + p1size + deltaOffset;
        for(int i = 0; i != p2size; i++)
        {
            //System.arraycopy(p2.getCode().get(i), 0, core[(offset2 + i) % coreSize], 0, 5 );
            int[] line = p2code.get(i);
            int loc = (offset2 + i) & coreSizeM1;
            core[loc][0] = line[0];
            core[loc][1] = line[1];
            core[loc][2] = line[2];
            core[loc][3] = line[3];
            core[loc][4] = line[4];
            if (debug != 0){
                coreData[loc] = 2;
            }
        }

        int p1loc = offset1 & coreSizeM1;
        int p2loc = offset2 & coreSizeM1;
        for(int time = 0; time != maxTime; time++)
        {
            if(debug != 0)
            {
                //printCore(p1loc,p2loc);
                //System.out.println("p1loc " + p1loc);
                //System.out.println("offset " + offset1);
                gameView.setLocations(p1loc, p2loc);
                gameView.repaint();
                try {
                    Thread.sleep(time / 1000000, time % 1000000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }

            if(core[p1loc][0] == 0)
            {
                return 0;
            }
            p1loc = execute(p1loc, offset1, 1);

            if(debug != 0)
            {
                //printCore(p1loc,p2loc);
                //System.out.println("p2loc " + p2loc);
                //System.out.println("offset " + offset2);
                gameView.setLocations(p1loc, p2loc);
                gameView.repaint();
                /*try {
                    Thread.sleep(time);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }*/
            }
            if(core[p2loc][0] == 0)
            {
                return 2;
            }
            p2loc = execute(p2loc, offset2, 2);

        }
        return 1;
    }
    public int execute(int ploc, int offset, int player)
    {
        int line1 = offset + core[ploc][3];
        if(core[ploc][1] != 0)
        {
            line1 += ploc - offset;
        }
        if(core[ploc][1] == 2)
        {
            line1 += core[line1 & coreSizeM1][3];
        }
        int line2 = offset + core[ploc][4];
        if(core[ploc][2] != 0)
        {
            line2 += ploc - offset;
        }
        if(core[ploc][2] == 2)
        {
            line2 += core[line2 & coreSizeM1][4];
        }
        line1 = line1 & coreSizeM1;
        line2 = line2 & coreSizeM1;
        int opcode = core[ploc][0];
        ploc = (ploc + 1) & coreSizeM1;
        //String opDescription = "";
        if(opcode == 1)
        {
            core[line2][0] = core[line1][0];
            core[line2][1] = core[line1][1];
            core[line2][2] = core[line1][2];
            core[line2][3] = core[line1][3];
            core[line2][4] = core[line1][4];
            if (debug != 0) {
                coreData[line2] = player + 2;
            }
            return ploc;
            //opDescription = "Moved from " + line1 + " to " + line2;
        }
        if(opcode == 2)
        {
            core[line2][3] += core[line1][3];
            core[line2][4] += core[line1][4];
            if (debug != 0) {
                coreData[line2] = player + 4;
            }
            return ploc;
            //opDescription = "Added " + line1 + " to " + line2;
        }
        if(opcode == 3)
        {
            core[line2][3] -= core[line1][3];
            core[line2][4] -= core[line1][4];
            if (debug != 0) {
                coreData[line2] = player + 6;
            }
            return ploc;
                //opDescription = "Subtracted " + line1 + " to " + line2;
        }
        if(opcode == 4)
        {
            ploc = line1;
            return ploc;
                //opDescription = "Jumped to " + line1;
        }
        if(opcode == 5)
        {
                if(core[line2][3] == 0 && core[line2][4] == 0)
                {
                    ploc = line1;
                    //opDescription = "Jumped to " + line1;
                }
                else
                {
                    //opDescription = "Did not jump to " + line1;
                }
                return ploc;
        }
        if(opcode == 6)
        {
            if(core[line1][3] == core[line2][3] && core[line1][4] == core[line2][4])
            {
                //opDescription = "Did not skip because " + line1 + " and " + line2 + " were equal.";
            }
            else
            {
                ploc = (ploc + 1) & coreSizeM1;
                //opDescription = "Skipped because " + line1 + " and " + line2 + " were not equal.";
            }
            return ploc;
        }
        if(debug != 0)
        {
            //System.out.println(opDescription);
        }
        return ploc;
    }
    /*public void printCore(int p1loc, int p2loc)
    {
        int dupCount = 0;
        int[] dupLine = new int[]{0,0,0,0,0};
        for(int i = 0; i < core.length; i++)
        {
            int[] line = core[i];
            if(Arrays.equals(line, dupLine) && i != p1loc && i != p2loc)
            {
                if(dupCount == 0)
                {
                    System.out.println(Player.toString(line));
                }
                dupCount++;
            }
            else
            {
                if(dupCount == 2)
                {
                    System.out.println(Player.toString(dupLine));
                }
                else if(dupCount > 2)
                {
                    System.out.println("    " + (dupCount - 1) + " lines skipped.");
                }
                System.out.println(Player.toString(line));
                if(i == p1loc)
                {
                    System.out.print(" <- 1");
                }
                if(i == p2loc)
                {
                    System.out.print(" <- 2");
                }
                dupLine = line;
                dupCount = 1;
            }
        }
        if(dupCount == 2)
        {
            System.out.println(Player.toString(dupLine));
        }
        else if(dupCount > 2)
        {
            System.out.println("    " + (dupCount - 1) + " lines skipped.");
        }
    }*/
}

```

# Answer
> 8 votes
# Evolved

~~I honestly don't get how it works. It seems to construct its source code before doing anything. I would love it if someone gave me an explanation for how it works.~~

After studying it, I found that it is simply a modified dwarf with an imp guard. Instead of bombing the enemies with `DAT` instructions, it shuffles the enemies code. It also bombs every two registers instead of every four registers. Given enough time, it would undoubtedly destroy itself.

```
MOV -2 #-1
MOV #4 -9
SUB -5 #6
MOV #1 1
MOV #-6 #4
SUB @8 @7
JMP -3 @4
DAT #-4 8
JMP -1 9
JMP 5 #-10
CMP @-1 #0
SUB 3 #-10
JMP @10 #-9
JMZ #1 10
MOV #3 2
ADD @9 @-3
CMP #-3 @7
DAT @0 @-2
JMP @-7 #6
DAT @-8 -6
MOV @0 #9
MOV #2 1
DAT @6882 #-10
JMP @3 4
CMP @8 2
ADD -7 @11
ADD @1 #-9
JMZ @-5 7
CMP 11 5526
MOV @8 6
SUB -6 @0
JMP 1 11
ADD @-3 #-8
JMZ @-14 @-5
ADD 0 @-8
SUB #3 @9
JMP #-1 5
JMP #9 @1
CMP -9 @0
SUB #4 #-2
JMP #-8 5
DAT -1 @-10
MOV 6 #2
CMP @-11 #-14
ADD @4 @-3
MOV @5 #-6
SUB -3 -2
DAT @-10 #-1
MOV #-13 #-6
MOV #1 5
ADD 5 #-5
MOV -8 @-1
DAT 0 10
DAT #5 #7
JMZ 6 -5
JMZ -12 -11
JMP 5 @-7
MOV #7 -3
SUB #-7 @-3
JMP -4 @-11
CMP @-5 #-2
JMZ @-1 #0
ADD #3 #2
MOV #5 @-6

```

# Answer
> 7 votes
# CopyPasta

Never participated to a CoreWar, this simple program is just trying to copy-paste himself and then execute the copy. It may not have the correct behavior, please tell me if it is the case.

It is too pacifist and can't win in fact.

```
MOV 6 0
MOV @-1 @-1
CMP @-2 3
JMP 4242 0
SUB -3 -4
JMP -4 0
DAT 0 4244

```

# Answer
> 6 votes
# Janitor

It should check if the following addresses are empty and if not it cleans them (thus, hopefully, erasing the opponent bot).

**Edit:** This new version should be quicker (now that I understood the `JMZ` command and the `@` reference correctly).

```
JMZ 2 6
MOV 4 @-1
ADD 2 -2
JMP -3 0
DAT 0 1
DAT 0 0

```

# Answer
> 6 votes
# FirstTimer

If it does work, it should try to take position at the start of the core and create a defens

```
main MOV 5 #0
     ADD #data #main
     CMP #main #max
     JMP #0 0
     JMP #main 0
     MOV #data #100
     ADD #data -1
     JMP -2 0
data DAT 1 1
max  DAT 8 3

```

# Answer
> 5 votes
# ScanBomber

Remove my comments before compiling. Scans for a while, then bombs when it finds a program. It probably will still lose to my Dwarf, though.

```
scan add #eight #range  ; scan
jmz #scan @range
sub #six #range
fire mov #zero @range   ; bombs away! (-6)
add #two #range
mov #zero @range
add #two #range
mov #zero @range
add #two #range
mov #zero @range        ; (+0)
add #two #range
mov #zero @range
add #two #range
mov #zero @range
add #two #range
mov #zero @range
add #two #range
mov #zero @range        ; (+8)
range jmp #scan 6
two dat 0 2
six dat 0 6
zero dat 0 0
eight dat 0 8

```

# Answer
> 5 votes
# Han Shot First (v2)

I figured the competition could use some more diversity, so here's my second entry: a one-shot `CMP` scanner.

This is **version 2**, with improved anti-Imp defenses — it can now beat Imp, if only by just one point. It still loses to Dwarven Engineer, but beats everything else so far, putting it currently in tied first place.

```
scan    ADD bomb    aim
aim     CMP 17      12
        JMZ scan    #-3
loop    MOV bomb    @aim
        ADD step    aim
step    JMP loop    #2
bomb    DAT 10      10

```

It works by comparing adjacent core locations 5 steps apart, at 10-step intervals, until it finds a difference. When it does, it starts throwing bombs at 2-step intervals until it kills its opponent or loops all the way around the core to reach itself.

If the scan does *not* find anything else, it will eventually loop around and find its own code and attack it. This would be suicidal, but for the fortunate coincidence that the first bomb lands squarely on the `aim` line, causing the next bomb to be thrown 12 positions (rather than the usual 2) down the core, conveniently skipping the code. (This also happens with 50% probability if the scan does find something, but fails to kill the opponent.) Since the core size is a multiple of two, this will also keep happening if the bombing run loops around, eliminating the need for a further backup strategy.

(This self-bombing trick was originally a pure coincidence — I had planned for a completely different way to switch from scanning to bombing mode if nothing was found, but when I first tested the code, the constants just happened to be right to make it work this way, and I decided to stick with it.)

# Answer
> 4 votes
# Imp

```
MOV 0 1

```

Simply inches through the program.

# Answer
> 4 votes
# Slug

```
     mov    ones    @-1024
     mov    from    -3
     mov    here    -3
loop mov    @-5 @-4
     add    ones  -5
     jmz    -17 -6
     add    ones  -8
     jmp    loop    42
ones dat    1   1
from dat    2   2
here dat    -11 -11

```

Crawls through memory space backwards. Occasionally throws a bomb far away.

# Answer
> 4 votes
# Paranoid

Kind of a copy-pasta but it will check if the code have been modified by bombing. If so it copy past a dwarf and execute it. If I manage to make the GameView again I'll try to change some of the constants.

```
copy    MOV data copy
loop    MOV @-1 @-1
    CMP @copy end
out JMP check 0
    SUB loop copy
    JMP loop 0
data    DAT 0 4109
check   MOV data copy
loop2   CMP @copy @copy
    JMP ok 0
    MOV aah 2
ok  CMP @copy end
    JMP 4098 0
    SUB loop copy
    JMP loop2 0
panic   MOV end copy
    MOV jump out
    JMP loop 0
jump    JMP 4124 0
dwarf   ADD 2 bomb
    MOV bomb @bomb
    JMP dwarf 4
bomb    DAT 0 4
aah JMP 3 0
end DAT 19 4127

```

# Answer
> 3 votes
# Easter Bunny

He enjoys hopping backwards :)

```
loop mov 0 -10
     add data loop
     cmp -7 data
     jmp -13 0
     jmp loop 0
data dat 1 1

```

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


title: Calculate a rock rolling down a hill

text:
# Question
Title: Calculate a rock rolling down a hill
# Introduction

Sisyphus was having some troubles at work lately. It seems he just never gets anything done, and he would love to find a solution to this problem.

His current employment requires rolling a rock up a hill. He usually does his job well, but every time he is near the top of the hill it rolls down again.

He is getting really frustrated with his job and wants to solve the problem scientifically by having a computer simulate the rock rolling down the hill.

It so happens that Sisyphus isn't particularly good at programming, so maybe you can help him out?

# The Challenge

After this silly introduction, let's come to business. Your program will receive an illustration of the hill and the rock which looks similar to this:

```
#o
##
###
######
########

```

Where `#` represents a part of the hill and `o` represents the rock.

You now have to implement a program which moves the rock 1 layer down. For example, the output of the above should be:

```
#
##o
###
######
########

```

If there is a horizontally even area, the hill just rolls horizontally, so...

```
o
########

```

...this would just make the stone roll sideways.

```
 o
########

```

If there is a vertical area, the rock falls down one step, so...

```
#o
#
#
#####

```

...would yield...

```
#
#o
#
#####

```

You will also receive the width and height of the image respectively in one line above the image. So, in complete, our sample input would look like this:

```
10 5
#o
##
###
######
#########

```

*(Note that the whitespace here are spaces. Select the text and see what I mean.)*

## Some details

* When the rock is already in the last line when running the program, you can choose to either terminate the program or output the unchanged input
* The hill only ever goes downwards
* Your program should format the output exactly the same as the input (including the dimensions), so if you pipe the output of the program to itself, it calculates the next step.
* You can assume there is always a way to the bottom, so input where the path is "blocked" may cause undefined behaviour
* You can assume there is always a space in the last line. The rock should "rest" there, so after calling the program a few times, always piping it's output into itself, you should end up with the rock in the last line, laying where the space previously was.
* You may accept input in any form you like (stdin, file,...). You have to post the WHOLE program (so all pre-initialized variables count as code).
* The lines are terminated with `\n`.
* You can get some example inputs here (make sure you copy the spaces correctly!)
* This is , so the working submission with the least **bytes** wins.
* The winner will be chosen on July 26th, 2014. You can post solutions after that, but you can't win

If you have any questions, let me know in the comments.

**Happy golfing!**

# Answer
## Regex (.NET, Perl, PCRE, JavaScript, ... flavours), 25 bytes

Yes, this will create some debate again, whether a regular expression is a valid program, but I'll pre-empt that and say that this submission is just for fun and doesn't need to be considered for the winner. (As opposed to the 31 byte Perl variant at the bottom ;).)

So here is a pure regex replacement solution.

Pattern (note the trailing space):

```
o(( *)\n#*)(?=\2) |o

```

Replacement (note the leading space):

```
 $1o

```

The byte count is for the sum of the two.

You can test it at http://regexhero.net/tester/. Make sure to choose Unix-style line endings and "preserve pasted formatting" when pasting. If it still doesn't work, you still have pasted Windows-style line endings. The easiest fix in that case is to replace `\n` with `\r\n` in the pattern to see that it works.

Here is a **48 byte** ECMAScript 6 function using this

```
f=(s)=>s.replace(/o(( *)\n#*)(?=\2) |o /,' $1o')

```

Finally, I've also got an actual program. It's **31 bytes** of Perl (including two bytes for `p` and `0` flags; thanks to Ventero for the suggestion!).

```
s/o(( *)\n#*)(?=\2) |o / $1o/

```

If you want to test it, don't even save it in a file, just do

```
perl -p0e 's/o(( *)\n#*)(?=\2) |o / $1o/' < hill.txt

```
> 38 votes

# Answer
# Python - 190

Slicing and concatenation horror, along with way too many variables. I'm certain this can be golfed more, but I can't think of any clever python functions right now. Input is stored in string `s`.

```
r=" "
o="o"
i=s.index(o)
b=i+int(s.split(r)[1])
q=s[:i]+r
x=s[b+3:]
try:
 a=s[b+1:b+3]
 if a[0]==r:s=q+s[i+1:b+1]+o+r+x
 elif a[1]==r:s=q+s[i+1:b+2]+o+x
 else:s=q+o+s[i+2:]
except:1
print(s)

```

Since python strings are immutable, I replace a character by concatenating all the characters before, my new character, and all the characters after. I use the hill width and indexing to determine where the rock should roll to.
> 4 votes

# Answer
## Ruby, 65/55 characters

Figured I'd see how long a solution is that doesn't just throw a regex on the problem.

```
r=gets p
r[r[(r[k=1+~/o/+x=r.to_i,2]=~/ /||-x)+k]&&=?o]=" "
$><<r

```

As expected, it's not as short as m.buettner's regex solution - but not much longer either.

When using interpreter flags, this can be shortened to 55 characters (53 for the code, 2 for the flags):

```
sub$_[($_[k=1+~/o/+x=$_.to_i,2]=~/ /||-x)+k]&&=?o," "

```

Run the code like this:

```
ruby -p0e 'sub$_[($_[k=1+~/o/+x=$_.to_i,2]=~/ /||-x)+k]&&=?o," "' < input

```
> 3 votes

# Answer
## HTML JavaScript - 251 chars

(**251** if you count the code inside the single quotes that reads the input and returns the output. **359** if you count the input box, input string, button, etc. **192** if you count just that does the work.)

**Golf code:**

```
<pre id="i">10 5
#o
##
##
######
######### </pre><button onclick='i=document.getElementById("i");h=i.innerHTML;if(p=h.
match(/([\s\S]*?)([# ]+)(o *\n)(#+)([\s\S]*)/)){if(p[4].length>p[2].length+1)p[3]=p[3].
replace("o "," o");else{p[3]=p[3].replace("o"," ");p[5]="o"+p[5].substr(1);}p[0]="";
h=p.join("");}i.innerHTML=h;'>Go</button>

```

http://goo.gl/R8nOIK
Click "Go" over and over.

**Method**

I uses String.match() to break hill into 5 parts, then I change one or two parts. I'm learning JavaScript, so any suggestions would be appreciated.

**Readable Code**

```
<pre id="io">10 5
#o
##
##
######
######### </pre>

<button onclick='

    // get image
    io = document.getElementById("io");
    image = io.innerHTML;

    // break image into five parts
    // 1(10 5\n#         \n##        \n) 2(### ) 3(o     \n) 4(######) 5(    \n######### )
    if (parts = image.match(/([\s\S]*?)([# ]+)(o *\n)(#+)([\s\S]*)/)) {

        // move rock to the right
        if (parts[4].length > parts[2].length + 1)
            parts[3] = parts[3].replace("o ", " o");

        // or move rock down
        else {
            parts[3] = parts[3].replace("o", " ");
            parts[5] = "o" + parts[5].substr(1);
        }

        // return new image
        parts[0] = "";
        image = parts.join("");

        // MAP io:i image:h parts:p
    }
    io.innerHTML = image;
'>Go</button>

```
> 3 votes

# Answer
# Python 2 - ~~289~~ 252 bytes

```
p=raw_input
w,h=map(int,p().split())
m=[p()for a in[0]*h]
j=''.join
f=lambda s:s.replace('o ',' o')
for i,r in enumerate(m):
 x=r.find('o')
 if x+1:y=i;break
if m[y+1][x]=='#':m=map(f,m);x+=1
print w,h
print'\n'.join(map(j,zip(*map(f,map(j,zip(*m))))))

```

I made some significant improvements but this is still terrible. A couple more bytes can be saved by converting this to Python 3 but I can't be arsed.

First, I find the rock. If the character immediately below it is `'#'`, replace every instance of `'o '` with `' o'`. Since there's guaranteed to be an extra space at the end, this will always move the rock to the right.

Regardless of if I just did that or not, I transpose the whole grid with `zip(*m)`. Then, I do another replacement of `'o '` with `' o'`. If there's a space to the right of the rock, that means that in the real grid there's a space below it, so it gets moved. Then I transpose back and print.
> 2 votes

# Answer
# Python (201)

```
import sys
print(input())
g=list(sys.stdin.read())
o='o'
x=g.index(o)
n=x+g.index('\n')+1
try:
 if g[n]==' ':g[n]=o
 elif g[n+1]==' ':g[n+1]=o
 else:g[x+1]=o
 g[x]=' '
except:1
print(*g,sep='',end='')

```
> 2 votes

# Answer
# awk, 152

```
awk 'NR==1{w=$2}{if(NR<=w&&$0~/o/){r=index($0,"o");g=$0;getline;if(index($0,"# ")<=r){sub("o"," ",g);sub(" ","o")}else{sub("o "," o",g)}print g}print}'

```

## More Readable

```
    awk '
  NR==1{  //If we're at the first line, set the width from the second column in the header.
    width=$2
  }
  {
    if(NR<=width && $0~/o/){   //If not at the bottom, look for the line with the rock.
      rockIndex=index($0,"o"); //Set the position of the rock.
      orig=$0;                 //Remember the current line so we can compare it to the next.
      getline;                 //Get the next line.

      if(index($0,"# ")<= rockIndex){  //Move down: if the rock is on a cliff or on a slope,
        sub("o"," ",orig);             //update the orig so that the rock is removed
        sub(" ", "o")                  //and update the current (first available position).
      }
      else {                           //Move right: if the rock is on flat ground,
        sub("o "," o", orig)           //update the orig so the the rock is advanced.
      }
      print orig                       //Print the line we skipped (but stored
    }                                  //and updated based on the line we're now on).
    print                              //Print the line we're now on.
  }
'

```
> 2 votes

# Answer
## php 485 484 chars

I know this is massive compared to entry by m.buettner but is best I can do for now. I think there must be a quicker way to turn the input string into a multi dimensional array but it is very late now.

And although it it uncompetitive I liked this puzzle. Would like the extension to show where the ball ends up, or after a set number of steps, perhaps added after the width and height on the input line. Could add that very easily to this version.

Here is my code: Input is in the first variable.

```
<?
$a.='10 5
#o
##
###
######
#########';$b=array();$c=explode("\n",$a);$d=explode(" ",$c[0]);$e=$d[0];$f=$d[1];unset($c[0]);$g=0;foreach($c as $h){$b[$g]=str_split($h);++$g;}for($i=0;$i<$f;++$i){for($j=0;$j<$e;++$j){if($b[$i][$j]=='o'){$k=$j;$l=$i;$b[$i][$j]=' ';}}}if($b[$l+1][$k]!='#'){$b[$l+1][$k]='o';}else if($b[$l+1][$k+1]!='#'){$b[$l+1][$k+1]='o';}else{$b[$l][$k+1]='o';}echo"$e $f\n";for($i=0;$i<$f;++$i){for($j=0;$j<$e;++$j){echo $b[$i][$j];}echo "\n";}

```

You can see it here in action on codepad

Edit: Changed codepad and code above as was outputting 0 instead of o, which caused problem when I tried to feed the output back into the program. Fixed now and saved one char!
> 1 votes

# Answer
## Groovy - 263 261 256 chars

Golfed. Read the file into a String, and use a function `p` to emulate a function `String.putAtIndex(index,value)`:

```
o="o"
b=" "
s=new File(args[0]).text
z={s.size()-it}
s=s[0..z(2)]
w=s.find(/\n.*?\n/).size()-1
p={i,v->s=s[0..i-1]+v+((i<z(0)-2)?s[i+1..z(1)]:"")}
try{
t=s.indexOf o
i=w+t
j=i+1
x=t+1
(s[i]==b)?x=i:(s[j]==b)?x=j:0
p x,o
p t,b
}catch(Exception e){}
print s

```

Ungolfed (somewhat):

```
o = "o"
b = " "
s = new File(args[0]).text
z = {s.size()-it}
s = s[0..z(2)]
w = s.find(/\n.*?\n/).size()-1

putAtIndex = { i,val ->
    s = s[0..i-1] + val + ((i<z(0)-2)?s[i+1..z(1)]:"")
}

try {
    t=s.indexOf o
    i=w+t
    j=i+1
    x=t+1
    // default x as horizontal move
    // check for (a) directly below (b) below and over one
    (s[i]==b) ? x=i : ( (s[j]==b) ? x=j : 0)
    putAtIndex x,o
    putAtIndex t,b
} catch (Exception e) {}
print s

```
> 1 votes

# Answer
# C (182)

```
char b[1024],*x,*n;main(z){read(0,b,1024);n=index(b,10)+1;x=index(n,'o');z=index(n,10)-n;n=x+z+1;if(n[1]){if(*n==32)*n='o';else if(n[1]==32)n[1]='o';else x[1]='o';*x=32;}printf(b);}

```

Or, if you actually want to read the code:

```
char b[1024],*x,*n; //1024 byte buffer hard coded
main(z){
    read(0,b,1024);
    n=index(b,10)+1; //start of line 2
    x=index(n,'o');
    z=index(n,10)-n; //10='\n'
    n=x+z+1; //reusing n
    if(n[1]){ //if not 0
        if(*n==32) //32=' '
            *n='o';
        else if(n[1]==32)
            n[1]='o';
        else
            x[1]='o';
        *x=32;
    }
    printf(b);
}

```
> 1 votes

# Answer
## R, 234

```
require(stringr)
g=scan(,"")
g=do.call(rbind,strsplit(str_pad(g,m<-max(nchar(g)),"r"),""))
if(g[(x<-which(g=="o"))+1]==" "){g[x+1]="o";g[x]=""}else{if(!is.na(g[x+1])){g[x+(n<-nrow(g))]="o";g[x]=""}}
for(i in 1:n) cat(g[i,],"\n",sep="")

```

String manipulation is not R's strongest point.

More readably:

```
require(stringr) # load package `stringr`, available from CRAN. required for `str_pad`
g=scan("")       # read input from console
g=do.call(       # applies the first argument (a function) to the second argument (a list of args to be passed)
  rbind,         # "bind" arguments so that each one becomes the row of a matrix
  strsplit(      # split the first argument by the second
    str_pad(g,max(nchar(g)),"r"," "), # fill each row with whitespace
    "")
)
if(g[(x<-which(g=="o"))+1]==" ") { # if the next element down from the "o" is " "...
  g[x+1]="o";g[x]=""               # make it an "o" and replace the current element with ""
} else {
  if(!is.na(g[x+1])) {             # if the next element down is not empty (i.e. out of range)
    g[x+nrow(g)]="o"; g[x]=""      # move "o" right
  }
}
for(i in 1:n) cat(g[i,],"\n",sep="") # print to console

```
> 1 votes

# Answer
## Clojure - 366 chars

Without regex. Required input file named "d". Golfed:

```
(def s(slurp "d"))(def w(-(.length(re-find #"\n.*?\n" s))2))(def t(.indexOf s "o"))(def i(+ t w 1))(defn g[i,j,x,c](cond (= x i) \ (= x j) \o :else c))(defn j[i,j] (loop[x 0](when(< x (.length s))(print(g i j x (.charAt s x)))(recur(inc x)))))(try(cond(= \ (.charAt s i))(j t i)(= \ (.charAt s (inc i)))(j t (inc i)):else (j t (inc t)))(catch Exception e (print s)))

```

Ungolfed:

```
(def s (slurp "d"))
(def w (- (.length (re-find #"\n.*?\n" s)) 2))
(def t (.indexOf s "o"))
(def i (+ t w 1))
(defn g [i,j,x,c] (cond (= x i) \ (= x j) \o :else c))

(defn j [i,j] (loop [x 0]
     (when (< x (.length s))
     (print (g i j x (.charAt s x))) (recur (inc x)))))

(try (cond (= \ (.charAt s i)) (j t i)
           (= \ (.charAt s (inc i))) (j t (inc i))
           :else (j t (inc t)))(catch Exception e (print s)))

```

Sample run (just one case, for brevity):

```
bash-3.2$ cat d
6 7
#
#
#
## o
####
####
#####

bash-3.2$ java -jar clojure-1.6.0.jar hill.clj
6 7
#
#
#
##
####o
####
#####

```

I'm a newbie. Suggestions welcome.
> 1 votes

# Answer
# MATLAB, 160

```
function r(f)
F=cell2mat(table2array(readtable(f)));
m=@(d)mod(d-1,size(F,1));C=find(F=='o');P=find(F==' ');N=min(P(P>C&m(P)>=m(C)));F([C,N])=F([N,C]);
disp(F);

```

The painful part is the file-input. The actual computation would be only 114 bytes:

```
function F=r(F)
m=@(d)mod(d-1,size(F,1));C=find(F=='o');P=find(F==' ');N=min(P(P>C&m(P)>=m(C)));F([C,N])=F([N,C]);

```
> 1 votes

---
Tags: code-golf
---


title: Calculate π with quadratic convergence

text:
# Question
Title: Calculate π with quadratic convergence
Write a function or complete program that takes a positive number `n` and performs `n` steps of an iterative algorithm for calculating π that has quadratic convergence (i.e. it approximately doubles the number of accurate digits at every iteration) then returns or prints out 2n correct digits (including the beginning 3). One such algorithm is the Gauss–Legendre algorithm, but you are free to use a different algorithm if you prefer.

**Examples:**

input `1` → output `3.1`
input `2` → output `3.141`
input `5` → output `3.1415926535897932384626433832795`

**Requirements:**

* Each iteration of the algorithm must perform a constant number of basic operations such as addition, subtraction, multiplication, division, power and root (with integer exponent/degree) - each such operation on "big" integer/decimal numbers is counted as one even if it involves one or more loops internally. To be clear, trigonometric functions and powers involving complex numbers are not basic operations.
* The algorithm is expected to have an initialization step which must also have a constant number of operations.
* If the algorithm needs 1 or 2 more iterations to get to 2n correct digits, you can perform up to `n+2` iterations instead of just `n`.
* If it wasn't clear enough, after the correct 2n digits, your program must **not** print anything else (such as more correct digits, wrong digits or the complete works of Shakespeare).
* Your program must support values of `n` from 1 to at least 20.
* Your program should not take more than an hour for `n`=20 on a modern computer (not a hard rule, but try to keep it reasonable).
* The program must not obtain more than 20 accurate digits after the initialization and first iteration of the algorithm.
* The program must be runnable in Linux using freely available software.
* The source code must use only ASCII characters.

**Scoring:**

Straightforward code golf, shortest code wins.

**Winner:**

The winner is Digital Trauma, I finally finished running his code on n=20 (just kidding). Special prize goes to primo for his very fast python solution and different algorithm :)

# Answer
> 14 votes
# dc, 99 bytes

Golfed:

```
2?dsi1+^k1dddsa2v/sb4/stsp[lalb*vlalb+2/dla-d*lp*ltr-stsasblp2*spli1-dsi0<m]dsmxK2/1-klalb+d*4lt*/p

```

With whitespace and comments for "readability":

```
2?dsi               # Push 2. push input n, duplicate and store in i
1+^k                # Set calculation precision to 2^(n+1)
1dddsa              # Push four 1s. Store 1st in a
2v/sb               # Store 1/sqrt(2) in b
4/st                # Store 1/4 in t
sp                  # Store 1 in p
[                   # Start iteration loop macro
lalb*v              # Save sqrt(a*b) on stack
lalb+2/d            # Save a[i+1] = (a[i]+b[i])/2 on stack and duplicate
la-d*lp*ltr-        # Save t-p(a[i]-a[i+1])^2 on the stack
st                  # Store t result from stack
sa                  # Store a result from stack
sb                  # Store b result from stack
lp2*sp              # Store 2p in p
li1-dsi0<m]         # Decrement iteration counter i; recurse into macro if < 0
dsmx                # Duplicate, store and run macro
K2/1-k              # Set display precision to 2^n-1
lalb+d*4lt*/        # Save (a+b)^2/4t on stack
p                   # Print result

```

`dc` needs to be told how many digits of precision should be used. The calculation precision needs to be higher than the final display precision, so the calculation precision is set to be `2^(n+1)` digits. I have verified the accuracy of the output with n=10 against http://www.angio.net/pi/digits/pi1000000.txt.

This slows down dramatically for larger n; n=12 takes 1.5 mins on my VM. Running a few different samples shows the time complexity is O(e^n) (not surprising). Extrapolating this to n=20 would have a runtime of 233 days. Oh well. Better than heat-death-of-the-universe at least.

This is moderately golfed - the stack is used to eliminate temporary variables during the calculations of each iteration, but there is possibly more use of the stack to shorten this more.

```
$ dc glpi.dc <<< 1
3.1
$ dc glpi.dc <<< 2
3.141
$ dc glpi.dc <<< 5
3.1415926535897932384626433832795
$ time dc glpi.dc <<< 7
3.1415926535897932384626433832795028841971693993751058209749445923078\
164062862089986280348253421170679821480865132823066470938446

real    0m0.048s
user    0m0.039s
sys 0m0.000s
$

```

If you don't like `dc` wrapping output at 70 chars, you can set the environment variable `DC_LINE_LENGTH` to 0:

```
$ DC_LINE_LENGTH=0 dc glpi.dc <<< 8
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648
$

```

# Answer
> 10 votes
# R, 156 bytes

Let's get this party started... with the absolute naivest implementation of the Gauss-Legendre algorithm ever.

```
for(i in 1:scan()){if(i<2){a=p=Rmpfr::mpfr(1,2e6);t=a/4;b=t^t}else{x=(a+b)/2;b=(a*b)^.5;t=t-p*(a-x)^2;a=x;p=2*p};o=(a+b)^2/(4*t)};cat(Rmpfr::format(o,2^i))

```

Ungolfed + explanation:

```
# Generate n approximations of pi, where n is read from stdin
for (i in 1:scan()) {

    # Initial values on the first iteration
    if (i < 2) {
        a <- p <- Rmpfr::mpfr(1, 1e7)
        t <- a/4
        b <- t^t
    } else {
        # Compute new values
        x <- (a + b) / 2
        b <- (a*b)^0.5
        t <- t - p*(a - x)^2

        # Store values for next iteration
        a <- x
        p <- 2*p
    }

    # Approximate pi
    o <- (a + b)^2 / (4*t)
}

# Print the result with 2^n digits
cat(Rmpfr::format(o, 2^i))

```

The `mpfr()` function is part of the `Rmpfr` package. It creates an `mpfr` object using the first argument as the value and the second argument as the number of bits of precision. We assign `a` and `p` to 1, and by defining `t` based on `a` (and `b` based on `t`), the `mpfr` type propogates to all four variables, thereby maintaining precision throughout.

As mentioned, this requires the R package `Rmpfr`, which is an acronym for "R Multiple Precision Floating point Reliable." The package uses GMP in the background. Unfortunately base R does not have the ability to do high-precision arithmetic, hence the package dependency.

Don't have `Rmpfr`? No sweat. `install.packages("Rmpfr")` and all of your dreams will come true.

Notice that `2e6` was specified as the precision. That means we have 2,000,000 bits of precision, which is enough to maintain precision for at least `n` = 20. (Note: `n` = 20 takes a long time but less than an hour on my computer.)

The approach here is literally just a regurgitation of the formulas on the Wikipedia page, but hey, we have to start somewhere.

Any input is welcome as always!

---

I had to rewrite a lot of this but I still have to acknowledge that Peter Taylor helped me knock *70 bytes* off of my first score. In the words of DigitalTrauma, "boom."

# Answer
> 7 votes
# Python 2, 214 bytes

This challenge presented a good excuse for me to learn the Decimal module. The Decimal numbers have definable precision and have square root support. I have set the precision to a conservative estimate of the accuracy depending on the loop count.

### Update

I have updated the program to improve accuracy and speed, at the expense of golfing. By using the decimal `sqrt()` method and replacing the `x**2` usage with `x*x`, it is now 200 times faster. This means it can now compute 20 loops giving a million digit result in 6.5 hours. The Decimal numbers often have an error in the last digit (caused by operations on the limit of precision), so the program now uses and discards 5 extra digits so only accurate digits are printed.

```
from decimal import*
d=Decimal
e=input()
getcontext().prec=5+(1<<e)
k=d(1)
j=d(2)
g=j*j
h=k/j
a=k
b=k/j.sqrt()
t=k/g
p=k
for i in[0]*e:f=a;a,b=(a+b)/j,(a*b).sqrt();c=f-a;t-=c*c*p;p+=p
l=a+b
print str(l*l/g/t)[:-5]

```

Sample run:

```
$ echo 1 | python min.py
3.1
$ echo 2 | python min.py
3.141
$ echo 3 | python min.py
3.1415926
$ echo 5 | python min.py
3.1415926535897932384626433832795
$ echo 12 | python min.py
3.141592653589793238462643383279502884197169399375105820974944592307816406286208
99862803482534211706798214808651328230664709384460955058223172535940812848111745
02841027019385211055596446229489549303819644288109756659334461284756482337867831
65271201909145648566923460348610454326648213393607260249141273724587006606315588
17488152092096282925409171536436789259036001133053054882046652138414695194151160
94330572703657595919530921861173819326117931051185480744623799627495673518857527
24891227938183011949129833673362440656643086021394946395224737190702179860943702
77053921717629317675238467481846766940513200056812714526356082778577134275778960
91736371787214684409012249534301465495853710507922796892589235420199561121290219
60864034418159813629774771309960518707211349999998372978049951059731732816096318
59502445945534690830264252230825334468503526193118817101000313783875288658753320
83814206171776691473035982534904287554687311595628638823537875937519577818577805
32171226806613001927876611195909216420198938095257201065485863278865936153381827
96823030195203530185296899577362259941389124972177528347913151557485724245415069
59508295331168617278558890750983817546374649393192550604009277016711390098488240
12858361603563707660104710181942955596198946767837449448255379774726847104047534
64620804668425906949129331367702898915210475216205696602405803815019351125338243
00355876402474964732639141992726042699227967823547816360093417216412199245863150
30286182974555706749838505494588586926995690927210797509302955321165344987202755
96023648066549911988183479775356636980742654252786255181841757467289097777279380
00816470600161452491921732172147723501414419735685481613611573525521334757418494
68438523323907394143334547762416862518983569485562099219222184272550254256887671
79049460165346680498862723279178608578438382796797668145410095388378636095068006
42251252051173929848960841284886269456042419652850222106611863067442786220391949
45047123713786960956364371917287467764657573962413890865832645995813390478027590
09946576407895126946839835259570982582262052248940772671947826848260147699090264
01363944374553050682034962524517493996514314298091906592509372216964615157098583
87410597885959772975498930161753928468138268683868942774155991855925245953959431
04997252468084598727364469584865383673622262609912460805124388439045124413654976
27807977156914359977001296160894416948685558484063534220722258284886481584560285
06016842739452267467678895252138522549954666727823986456596116354886230577456498
03559363456817432411251507606947945109659609402522887971089314566913686722874894
05601015033086179286809208747609178249385890097149096759852613655497818931297848
21682998948722658804857564014270477555132379641451523746234364542858444795265867
82105114135473573952311342716610213596953623144295248493718711014576540359027993
44037420073105785390621983874478084784896833214457138687519435064302184531910484
81005370614680674919278191197939952061419663428754440643745123718192179998391015
91956181467514269123974894090718649423196156794520809514655022523160388193014209
37621378559566389377870830390697920773467221825625996615014215030680384477345492
02605414665925201497442850732518666002132434088190710486331734649651453905796268
56100550810665879699816357473638405257145910289706414011097120628043903975951567
71577004203378699360072305587631763594218731251471205329281918261861258673215791
98414848829164470609575270695722091756711672291098169091528017350671274858322287
18352093539657251210835791513698820914442100675103346711031412671113699086585163
98315019701651511685171437657618351556508849099898599823873455283316355076479185
35893226185489632132933089857064204675259070915481416549859461637180270981994309
92448895757128289059232332609729971208443357326548938239119325974636673058360414
28138830320382490375898524374417029132765618093773444030707469211201913020330380
19762110110044929321516084244485963766983895228684783123552658213144957685726243
34418930396864262434107732269780280731891544110104468232527162010526522721116603
96665573092547110557853763466820653109896526918620564769312570586356620185581007
29360659876486117

```

The ungolfed code:

```
from decimal import *
d = Decimal

loops = input()
# this is a conservative estimate for precision increase with each loop:
getcontext().prec = 5 + (1<<loops)

# constants:
one = d(1)
two = d(2)
four = two*two
half = one/two

# initialise:
a = one
b = one / two.sqrt()
t = one / four
p = one

for i in [0]*loops :
    temp = a;
    a, b = (a+b)/two, (a*b).sqrt();
    pterm = temp-a;
    t -= pterm*pterm * p;
    p += p

ab = a+b
print str(ab*ab / four / t)[:-5]

```

# Answer
> 5 votes
## Python (2.7) - 131 bytes

```
from gmpy import*
n=input()
p=a=fsqrt(mpf(8,4<<n));b=0
exec"a=fsqrt(a/2);b=1/(a-a*b+b/a+1);p*=b+a*a*b;a+=1/a;"*n
print`p`[5:2**n+6]

```

***Update:** Now using `gmpy` rather than `gmpy2`. For whatever reason, in `gmpy2` setting the precision on a single value doesn't propagate to other values. The result of any calculation reverts back to the precision of the current context. Precision does propagate in `gmpy`, which seems more intuitive to me. It's also considerably less verbose.*

Using one of the many algorithms devised by Borwein and Borwein, slightly refactored. n=20 takes about 11 seconds on my box. Not the most efficient method, but still not bad.

---

**Refactoring**

The original algorithm was the following:

Refactoring was done incrementally, but the end result is that

The major simplification happens in *pn+1*. It's also slightly faster due to having eliminated a division.

The current implementation pushes *an* back one iteration in the calculation of *pn+1*, which allows for a different initialization of *p0* (*2√2*), but is otherwise identical.

---

**Sample Usage**

```
$ echo 1 | python pi-borwein.py
3.1

$ echo 2 | python pi-borwein.py
3.141

$ echo 5 | python pi-borwein.py
3.1415926535897932384626433832795

$ echo 10 | python pi-borwein.py
3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342117067982148086513282306647093844609550582231725359408128481117450284102701938521105559644622948954930381964428810975665933446128475648233786783165271201909145648566923460348610454326648213393607260249141273724587006606315588174881520920962829254091715364367892590360011330530548820466521384146951941511609433057270365759591953092186117381932611793105118548074462379962749567351885752724891227938183011949129833673362440656643086021394946395224737190702179860943702770539217176293176752384674818467669405132000568127145263560827785771342757789609173637178721468440901224953430146549585371050792279689258923542019956112129021960864034418159813629774771309960518707211349999998372978049951059731732816096318595024459455346908302642522308253344685035261931188171010003137838752886587533208381420617177669147303598253490428755468731159562863882353787593751957781857780532171226806613001927876611195909216420198938095257201065485863278

```

# Answer
> 3 votes
# bc and Newton's method, 43 bytes

Newton's method for finding zeros of any function converges quadratically and the algorithm is way simpler than for Gauss-Legendre. It basically boils down to:

So here goes the according snippet:

```
n=20;x=3;scale=2^n;while(n--)x-=s(x)/c(x);x

```

A bit more readable:

```
/* desired number of iterations */
n = 20;

/* starting estimate for pi */
x = 3;

/* set precision to 2^n */
scale = 2^n;

/* perform n iteration steps */
while(n--)
  // f:=sin, f'=cos
  x -= s(x)/c(x)

```

To test this, run `bc -l` in a shell and paste the above snippet. Be prepared to wait for a while; `n=20` has been running for about 5min now and no end in sight, yet. `n=10` takes about 40s.

---
Tags: code-golf, pi
---