# Question
Title: Count balanced binary strings matching any of a set of masks
A *binary string* is a string which contains only characters drawn from *01*. A *balanced binary string* is a binary string which contains exactly as many *0*s as *1*s.

You are given a positive integer *n* and an arbitrary number of masks, each of which is *2n* characters long, and contains only characters drawn from *012*. A binary string and a mask match if it is the same length and agrees on the character in every position where the mask doesn't have a *2*. E.g. the mask *011022* matches the binary strings *011000*, *011001*, *011010*, *011011*.

Given *n* and the masks as input (separated by newlines), you must output the number of distinct balanced binary strings which match one or more of the masks.

## Examples

Input

```
3
111222
000112
122020
122210
102120

```

Reasoning

* The only balanced binary string matching *111222* is **111000**.
* The only balanced binary string matching *000112* is **000111**.
* The balanced binary strings matching *122020* are *111000* (already counted), **110010** and **101010**.
* The balanced binary strings matching *122210* are *110010* (already counted), *101010* (already counted) and **100110**.
* The balanced binary strings matching *102120* are **101100** and *100110* (already counted).

So the output should be

```
6

```

---

Input

```
10
22222222222222222222

```

Reasoning

* There are *20 choose 10* balanced binary strings of length 20.

Output

```
184756

```

## Winner

The winner will be the one that computes the competition input the fastest, of course treating it the same way as it would any other input. (I use a determined code in order to have a clear winner and avoid cases where different inputs would give different winners. If you think of a better way to find the fastest code, tell me so).

### Competition input

http://pastebin.com/2Dg7gbfV

# Answer
> 2 votes
# C

If you're not on Linux, or otherwise having trouble compiling, you should probably remove the timing code (`clock_gettime`).

```
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long int binomial(int n, int m) {
  if(m > n/2) {
    m = n - m;
  }
  int i;
  long int result = 1;
  for(i = 0; i < m; i++) {
    result *= n - i;
    result /= i + 1;
  }
  return result;
}

typedef struct isct {
  char *mask;
  int p_len;
  int *p;
} isct;

long int mask_intersect(char *mask1, char *mask2, char *mask_dest, int n) {

  int zero_count = 0;
  int any_count = 0;
  int i;
  for(i = 0; i < n; i++) {
    if(mask1[i] == '2') {
      mask_dest[i] = mask2[i];
    } else if (mask2[i] == '2') {
      mask_dest[i] = mask1[i];
    } else if (mask1[i] == mask2[i]) {
      mask_dest[i] = mask1[i];
    } else {
      return 0;
    }
    if(mask_dest[i] == '2') {
      any_count++;
    } else if (mask_dest[i] == '0') {
      zero_count++;
    }
  }
  if(zero_count > n/2 || any_count + zero_count < n/2) {
    return 0;
  }
  return binomial(any_count, n/2 - zero_count);
}

int main() {

  struct timespec start, end;
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);

  int n;
  scanf("%d", &n);
  int nn = 2 * n;

  int m = 0;
  int m_max = 1024;

  char **masks = malloc(m_max * sizeof(char *));

  while(1) {
    masks[m] = malloc(nn + 1);
    if (scanf("%s", masks[m]) == EOF) {
      break;
    }
    m++;
    if (m == m_max) {
      m_max *= 2;
      masks = realloc(masks, m_max * sizeof(char *));
    }
  }

  int i = 1;
  int i_max = 1024 * 128;

  isct *iscts = malloc(i_max * sizeof(isct));

  iscts[0].mask = malloc(nn);
  iscts[0].p = malloc(m * sizeof(int));

  int j;
  for(j = 0; j < nn; j++) {
    iscts[0].mask[j] = '2';
  }
  for(j = 0; j < m; j++) {
    iscts[0].p[j] = j;
  }
  iscts[0].p_len = m;

  int i_start = 0;
  int i_end = 1;
  int sign = 1;

  long int total = 0;

  int mask_bin_len = 1024 * 1024;
  char* mask_bin = malloc(mask_bin_len);
  int mask_bin_count = 0;

  int p_bin_len = 1024 * 128;
  int* p_bin = malloc(p_bin_len * sizeof(int));
  int p_bin_count = 0;

  while (i_end > i_start) {
    for (j = i_start; j < i_end; j++) {
      if (i + iscts[j].p_len > i_max) {
        i_max *= 2;
        iscts = realloc(iscts, i_max * sizeof(isct));
      }
      isct *isct_orig = iscts + j;
      int x;
      int x_len = 0;
      int i0 = i;
      for (x = 0; x < isct_orig->p_len; x++) {
        if(mask_bin_count + nn > mask_bin_len) {
          mask_bin_len *= 2;
          mask_bin = malloc(mask_bin_len);
          mask_bin_count = 0;
        }
        iscts[i].mask = mask_bin + mask_bin_count;
        mask_bin_count += nn;
        long int count =
            mask_intersect(isct_orig->mask, masks[isct_orig->p[x]], iscts[i].mask, nn);
        if (count > 0) {
          isct_orig->p[x_len] = isct_orig->p[x];
          i++;
          x_len++;
          total += sign * count;
        }
      }
      for (x = 0; x < x_len; x++) {
        int p_len = x_len - x - 1;
        iscts[i0 + x].p_len = p_len;
        if(p_bin_count + p_len > p_bin_len) {
          p_bin_len *= 2;
          p_bin = malloc(p_bin_len * sizeof(int));
          p_bin_count = 0;
        }
        iscts[i0 + x].p = p_bin + p_bin_count;
        p_bin_count += p_len;
        int y;
        for (y = 0; y < p_len; y++) {
          iscts[i0 + x].p[y] = isct_orig->p[x + y + 1];
        }
      }
    }

    sign *= -1;
    i_start = i_end;
    i_end = i;

  }

  printf("%lld\n", total);

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

  int seconds = end.tv_sec - start.tv_sec;
  long nanoseconds = end.tv_nsec - start.tv_nsec;
  if(nanoseconds < 0) {
    nanoseconds += 1000000000;
    seconds--;
  }

  printf("%d.%09lds\n", seconds, nanoseconds);
  return 0;
}

```

Example cases:

```
robert@unity:~/c/se-mask$ gcc -O3 se-mask.c -lrt -o se-mask
robert@unity:~/c/se-mask$ head testcase-long
30
210211202222222211222112102111220022202222210122222212220210
010222222120210221012002220212102220002222221122222220022212
111022212212022222222220111120022120122121022212211202022010
022121221020201212200211120100202222212222122222102220020212
112200102110212002122122011102201021222222120200211222002220
121102222220221210220212202012110201021201200010222200221002
022220200201222002020110122212211202112011102220212120221111
012220222200211200020022121202212222022012201201210222200212
210211221022122020011220202222010222011101220121102101200122
robert@unity:~/c/se-mask$ ./se-mask < testcase-long
298208861472
0.001615834s
robert@unity:~/c/se-mask$ head testcase-hard
8
0222222222222222
1222222222222222
2022222222222222
2122222222222222
2202222222222222
2212222222222222
2220222222222222
2221222222222222
2222022222222222
robert@unity:~/c/se-mask$ ./se-mask < testcase-hard
12870
3.041261458s
robert@unity:~/c/se-mask$

```

(Times are for an i7-4770K CPU at 4.1 GHz.) Be careful, `testcase-hard` uses around 3-4 GB of memory.

This is pretty much an implementation of inclusion-exclusion method blutorange came up with, but done so that it will handle intersections of any depth. ~~The code as written is spending a lot of time on memory allocation, and will get even faster once I optimize the memory management.~~

I shaved off around 25% on `testcase-hard`, but the performance on the original (`testcase-long`) is pretty much unchanged, since not much memory allocation is going on there. I'm going to tune a bit more before I call it: I think I might be able to get a 25%-50% improvement on `testcase-long` too.

# Mathematica

Once I noticed this was a #SAT problem, I realized I could use Mathematica's built-in `SatisfiabilityCount`:

```
AbsoluteTiming[
 (* download test case *)
 input = Map[FromDigits,
   Characters[
    Rest[StringSplit[
      Import["http://pastebin.com/raw.php?i=2Dg7gbfV",
       "Text"]]]], {2}]; n = Length[First[input]];
 (* create boolean function *)
 bool = BooleanCountingFunction[{n/2}, n] @@ Array[x, n] &&
   Or @@ Table[
     And @@ MapIndexed[# == 2 || Xor[# == 1, x[First[#2]]] &, i], {i,
      input}];
 (* count instances *)
 SatisfiabilityCount[bool, Array[x, n]]
]

```

Output:

```
{1.296944, 298208861472}

```

That's 298,208,861,472 masks in 1.3 seconds (i7-3517U @ 1.9 GHz), including the time spent downloading the test case from pastebin.

# Answer
> 4 votes
# ruby, pretty fast, but it depends upon the input

*Now speed-up by a factor of 2~2.5 by switching from strings to integers.*

Usage:

```
cat <input> | ruby this.script.rb

```

Eg.

```
mad_gaksha@madlab ~/tmp $ ruby c50138.rb < c50138.inp2
number of matches: 298208861472
took 0.05726237 s

```

The number of matches for a single mask a readily calculated by the binomial coefficient. So for example `122020` needs 3 `2`s filled, 1 `0` and 2 `1`. Thus there are `nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3` different binary strings matching this mask.

An intersection between n masks m\_1, m\_2, ... m\_n is a mask q, such that a binary string s matches q only iff it matches all masks m\_i.

If we take two masks m\_1 and m\_2, its intersection is easily computed. Just set m\_1\[i\]=m\_2\[i\] if m\_1\[i\]==2. The intersection between `122020` and `111222` is `111020`:

```
122020 (matched by 3 strings, 111000 110010 101010)
111222 (matched by 1 string, 111000)
111020 (matched by 1 string, 111000)

```

The two individual masks are matched by 3+1=4 strings, the interesection mask is matched by one string, thus there are 3+1-1=3 unique strings matching one or both masks.

I'll call N(m\_1,m\_2,...) the number of strings matched all m\_i. Applying the same logic as above, we can compute the number of unique strings matched by at least one mask, given by the inclusion exclusion principle and see below as well, like this:

```
N(m_1) + N(m_2) + ... + N(m_n) - N(m_1,m_2) - ... - N(m_n-1,m_n) + N(m_1,m_2,m_3) + N(m_1,m_2,m_4) + ... N(m_n-2,m_n-1,m_n) - N(m_1,m_2,m_3,m_4) -+ ...

```

There are many, many, many combinations of taking, say 30 masks out of 200.

**So this solution makes the assumption that not many high-order intersections of the input masks exist, ie. most n-tuples of n\>2 masks will not have any common matches.**

Use the code here, the code at ideone may be out-dated.

I added a function `remove_duplicates` that can be used to pre-process the input and delete masks `m_i` such that all strings that match it also match another mask `m_j`.,For the current input, this actually takes longer as there are no such masks (or not many), so the function isn't applied to the data yet in the code below.

Code:

```
# factorial table
FAC = [1]
def gen_fac(n)
  n.times do |i|
    FAC << FAC[i]*(i+1)
  end
end

# generates a mask such that it is matched by each string that matches m and n
def diff_mask(m,n)
  (0..m.size-1).map do |i|
    c1 = m[i]
    c2 = n[i]
    c1^c2==1 ? break : c1&c2
  end
end

# counts the number of possible balanced strings matching the mask
def count_mask(m)
  n = m.size/2
  c0 = n-m.count(0)
  c1 = n-m.count(1)
  if c0<0 || c1<0
    0
  else
    FAC[c0+c1]/(FAC[c0]*FAC[c1])
  end
end

# removes masks contained in another
def remove_duplicates(m)
  m.each do |x|
    s = x.join
    m.delete_if do |y|
      r = /\A#{s.gsub(?3,?.)}\Z/
      (!x.equal?(y) && y =~ r) ? true : false
    end
  end
end

#intersection masks of cn masks from m.size masks
def mask_diff_combinations(m,n=1,s=m.size,diff1=[3]*m[0].size,j=-1,&b)
  (j+1..s-1).each do |i|
    diff2 = diff_mask(diff1,m[i])
    if diff2
      mask_diff_combinations(m,n+1,s,diff2,i,&b) if n<s
      yield diff2,n
    end
  end
end

# counts the number of balanced strings matched by at least one mask
def count_n_masks(m)
  sum = 0
  mask_diff_combinations(m) do |mask,i|
    sum += i%2==1 ? count_mask(mask) : -count_mask(mask)
  end
  sum
end

time = Time.now

# parse input
d = STDIN.each_line.map do |line|
  line.chomp.strip.gsub('2','3')
end
d.delete_if(&:empty?)
d.shift
d.map!{|x|x.chars.map(&:to_i)}

# generate factorial table
gen_fac([d.size,d[0].size].max+1)

# count masks
puts "number of matches: #{count_n_masks(d)}"
puts "took #{Time.now-time} s"

```

---

This is called the inclusion exclusion principle, but before somebody had pointed me to it I had my own proof, so here it goes. Doing something yourself feels great though.

Let us consider the case of 2 masks, call then `0` and `1`, first. We take every balanced binary string and classify it according to which mask(s) it matches. `c0` is the number of those that match only mask `0`, `c1` the nunber of those that match only `1`, `c01` those that match mask `0` and `1`.

Let `s0` be the number sum of the number of matches for each mask (they may overlap). Let `s1` be the sum of the number of matches for each pair (2-combination) of masks. Let `s_i` be the sum of the number of matches for each (i+1) combination of masks. The number of matches of n-masks is the number of binary strings matching all masks.

If there are n masks, the desired output is the sum of all `c`'s, ie. `c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1)`. What the program computes is the alternating sum of all `s`'s, ie. `s = s_0-s_1+s_2-+...+-s_(n-1)`. We wish to proof that `s==c`.

n=1 is obvious. Consider n=2. Counting all matches of mask `0` gives `c0+c01` (the number of strings matching only 0 + those matching both `0` and `1`), counting all matches of `1` gives `c1+c02`. We can illustrate this as follows:

```
0: c0 c01
1: c1 c10

```

By definition, `s0 = c0 + c1 + c12`. `s1` is the sum number of matches of each 2-combination of `[0,1]`, ie. all uniqye `c_ij`s. Keep in mind that `c01=c10`.

```
s0 = c0 + c1 + 2 c01
s1 = c01
s = s0 - s1 = c0 + c1 + c01 = c

```

Thus `s=c` for n=2.

Now consider n=3.

```
0  : c0 + c01 + c02 + c012
1  : c1 + c01 + c12 + c012
2  : c2 + c12 + c02 + c012
01 : c01 + c012
02 : c02 + c012
12 : c12 + c012
012: c012

s0 = c0 + c1 + c2 + 2 (c01+c02+c03) + 3 c012
s1 = c01 + c02 + c12 + 3 c012
s2 = c012

s0 = c__0 + 2 c__1 + 3 c__2
s1 =          c__1 + 3 c__2
s2 =                   c__2

s = s0 - s1 + s2 = ... = c0 + c1 + c2 + c01 + c02 + c03 + c012 = c__0 + c__1 + c__2 = c

```

Thus `s=c` for n=3. `c__i` represents the of all `c`s with (i+1) indices, eg `c__1 = c01` for n=2 and `c__1 = c01 + c02 + c12` for n==3.

For n=4, a pattern starts to emerge:

```
0:   c0 + c01 + c02 + c03 + c012 + c013 + c023 + c0123
1:   c1 + c01 + c12 + c13 + c102 + c103 + c123 + c0123
2:   c2 + c02 + c12 + c23 + c201 + c203 + c213 + c0123
3:   c3 + c03 + c13 + c23 + c301 + c302 + c312 + c0123

01:  c01 + c012 + c013 + c0123
02:  c02 + c012 + c023 + c0123
03:  c03 + c013 + c023 + c0123
12:  c11 + c012 + c123 + c0123
13:  c13 + c013 + c123 + c0123
23:  c23 + c023 + c123 + c0123

012:  c012 + c0123
013:  c013 + c0123
023:  c023 + c0123
123:  c123 + c0123

0123: c0123

s0 = c__0 + 2 c__1 + 3 c__2 + 4 c__3
s1 =          c__1 + 3 c__2 + 6 c__3
s2 =                   c__2 + 4 c__3
s3 =                            c__3

s = s0 - s1 + s2 - s3 = c__0 + c__1 + c__2 + c__3 = c

```

Thus `s==c` for n=4.

In general, we get binomial coefficients like this (↓ is i, → is j):

```
   0  1  2  3  4  5  6  .  .  .

0  1  2  3  4  5  6  7  .  .  .
1     1  3  6  10 15 21 .  .  .
2        1  4  10 20 35 .  .  .
3           1  5  15 35 .  .  .
4              1  6  21 .  .  .
5                 1  7  .  .  .
6                    1  .  .  .
.                       .
.                          .
.                             .

```

To see this, consider that for some `i` and `j`, there are:

* x = ncr(n,i+1): combinations C for the intersection of (i+1) mask out of n
* y = ncr(n-i-1,j-i): for each combination C above, there are y different combinations for the intersection of (j+2) masks out of those containing C
* z = ncr(n,j+1): different combinations for the intersection of (j+1) masks out of n

As that may sound confusing, here's the defintion applied to an example. For i=1, j=2, n=4, it looks like this (cf. above):

```
01:  c01 + c012 + c013 + c0123
02:  c02 + c012 + c023 + c0123
03:  c03 + c013 + c023 + c0123
12:  c11 + c012 + c123 + c0123
13:  c13 + c013 + c123 + c0123
23:  c23 + c023 + c123 + c0123

```

So here x=6 (01, 02, 03, 12, 13, 23), y=2 (two c's with three indices for each combination), z=4 (c012, c013, c023, c123).

In total, there are `x*y` coefficients `c` with (j+1) indices, and there are `z` different ones, so each occurs `x*y/z` times, which we call the coefficient `k_ij`. By simple algebra, we get `k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1)`.

So the index is given by `k_ij = nCr(j+1,i+1)` If you recall all the defintions, all we need to show is that the alternating sum of each column gives 1.

The alternating sum `s0 - s1 + s2 - s3 +- ... +- s(n-1)` can thus be expressed as:

```
s_j = c__j * ∑［(-1)^(i+j) k_ij］ for i=0..n-1
     = c__j * ∑［(-1)^(i+j) nCr(j+1,i+1)］ for i=0..n-1
     = c__j * ∑［(-1)^(i+j) nCr(j+1,i)］｛i=0..n｝ - (-1)^0 nCr(j+1,0)
     = (-1)^j c__j

s   = ∑［(-1)^j  s_j］ for j = 0..n-1
    = ∑［(-1)^j (-1)^j c__j)］ for j=0..n-1
    = ∑［c__j］ for j=0..n-1
    = c

```

Thus `s=c` for all n=1,2,3,...

# Answer
> 1 votes
# C

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gsl/gsl_combination.h>

int main (int argc, char *argv[]) {

    printf ("reading\n");
    char buffer[100];
    gets(buffer);
    char n = atoi(buffer);

    char *masks[1000];
    masks[0] = malloc(2 * n * sizeof(char));
    char c,nrows,j,biggestzerorun,biggestonerun,currentzerorun,currentonerun = 0;

    while ((c = getchar()) && c != EOF) {
        if (c == '\n') {
            nrows++;
            if (currentonerun > biggestonerun) {
                biggestonerun = currentonerun;
            }
            if (currentzerorun > biggestzerorun) {
                biggestzerorun = currentzerorun;
            }
            j=currentonerun=currentzerorun=0;
            masks[nrows] = malloc(2 * n * sizeof(char));
        } else if (c == '0') {
            masks[nrows][j++] = 1;
            currentzerorun++;
            if (currentonerun > biggestonerun) {
                biggestonerun = currentonerun;
            }
            currentonerun=0;
        } else if (c == '1') {
            masks[nrows][j++] = 2;
            currentonerun++;
            if (currentzerorun > biggestzerorun) {
                biggestzerorun = currentzerorun;
            }
            currentonerun=0;
        } else if (c == '2') {
            masks[nrows][j++] = 3;
            currentonerun++;
            currentzerorun++;
        }
    }
    if (currentonerun > biggestonerun) {
        biggestonerun = currentonerun;
    }
    if (currentzerorun > biggestzerorun) {
        biggestzerorun = currentzerorun;
    }

    printf("preparing combinations\n");

    int nmatches=0;

    gsl_combination *combination = gsl_combination_calloc(2*n, n);

    printf("entering loop:\n");

    do {
        char vector[2*n];
        char currentindex, previousindex;
        currentonerun = 0;
        memset(vector, 1, 2*n);

        // gsl_combination_fprintf (stdout, combination, "%u ");
        // printf(": ");

        for (char k=0; k<n; k++) {
            previousindex = currentindex;
            currentindex = gsl_combination_get(combination, k);
            if (k>0) {
                if (currentindex - previousindex == 1) {
                    currentonerun++;
                    if (currentonerun > biggestonerun) {
                        goto NEXT;
                    }
                } else {
                    currentonerun=0;
                    if (currentindex - previousindex > biggestzerorun) {
                        goto NEXT;
                    }
                }
            }
            vector[currentindex] = 2;
        }

        for (char k=0; k<=nrows; k++) {
            char ismatch = 1;
            for (char l=0; l<2*n; l++) {
                if (!(vector[l] & masks[k][l])) {
                    ismatch = 0;
                    break;
                }
            }
            if (ismatch) {
                nmatches++;
                break;
            }
        }

        NEXT: 1;

    } while (
        gsl_combination_next(combination) == GSL_SUCCESS
    );

    printf ("RESULT: %i\n", nmatches);

    gsl_combination_free(combination);
    for (; nrows>=0; nrows--) {
        free(masks[nrows]);
    }
}

```

Good luck getting the big input to run on this - it'll probably take all night to get through approx. 60^30 permutations! Maybe an intermediate sized dataset might be a good idea?

---
Tags: combinatorics, fastest-code, balanced-string
---


title: Let's play Meta tic-tac-toe!

text:
# Question
Title: Let's play Meta tic-tac-toe!
# Lets play a game of Meta tic-tac-toe!

This is a tournament of Meta tic-tac-toe. The rules of Meta tic-tac-toe are as follows:

1. All of the regular rules of tic-tac-toe apply.
2. There are nine boards arranged to make one master board. Like so:

```
0|1|2 || 0|1|2 || 0|1|2
----- || ----- || -----
3|4|5 || 3|4|5 || 3|4|5
----- || ----- || -----
6|7|8 || 6|7|8 || 6|7|8
========================
0|1|2 || 0|1|2 || 0|1|2
----- || ----- || -----
3|4|5 || 3|4|5 || 3|4|5
----- || ----- || -----
6|7|8 || 6|7|8 || 6|7|8
========================
0|1|2 || 0|1|2 || 0|1|2
----- || ----- || -----
3|4|5 || 3|4|5 || 3|4|5
----- || ----- || -----
6|7|8 || 6|7|8 || 6|7|8

```

board 0 refers to the top left board, board 1 refers to the top middle board... like this

```
0|1|2
-----
3|4|5
-----
6|7|8

```

If I say board 3, tile 4, that means the center tile of the board on the middle left.
3. You are only allowed to move in one of the smaller boards.
4. If you win one of the smaller boards, that **entire board** counts as your tile.
5. If one of the boards becomes filled before either bot has won it, it counts as nobodies tile.
6. Whoever wins the master board wins!

However, there is an important twist. Let's say I go in board 7, tile 2. That means on your turn, you can **only** go in board 2. Then let's say you go in board 2, tile 5. Now on my turn, I can **only** go in board 5. Let's say that board 1 is full. (There are no more spots left, or one of us has already won board 1) Now if I go in board 5, tile 1, you can go in any of the boards you want.

These rules can be regarded as:

1. You must play in the board corresponding to the position played by the previous player.
    * If X plays in board 2, tile 5; O must play in board 5
2. If the target board is full (a tie) or already has a victor, the next move is unconstrained.
3. A board with a winner may **not** be played into, even on an unconstrained move.

If this is a little bit confusing, you can try it online here. (make sure to switch from "first tile wins" to "3 tiles in a row")

Now here are the rules of the challenge.

1. You must write a bot that plays this game.
2. Bot 1 is Xs, and it gets to go first. It will be called with these command line arguments (without the stuff in parentheses):

```
X         (whose turn)
--------- (board 0)
--------- (board 1)
--------- (board 2)
--------- (board 3)
--------- (board 4)
--------- (board 5)
--------- (board 6)
--------- (board 7)
--------- (board 8)
--------- (master board)
xx        (last move)

```

The first character represents who the bot is. In this case, bot 1 plays as X. The next 9 lines refers to the 9 boards. The 11th line refers to the master board. The "xx" is the last move. Now, bot1 must print two numbers between 0 and 8. Number 1 is the board your bot is moving in, and number 2 is the tile in said board. The controller will keep track of this move. Let's say bot 1 prints 38. Now the board will look like this:

```
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
==========================
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |X ||  | |  ||  | |
==========================
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |

```

and bot2 will be called with these arguments:

```
O
---------
---------
---------
--------X
---------
---------
---------
---------
---------
---------
38

```
3. Now bot 2 must move in board 8 (because bot1 placed an x in tile 3). Let's say bot2 prints 84. Now the board looks like this.

```
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
==========================
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |X ||  | |  ||  | |
==========================
 | |  ||  | |  ||  | |
----- || ----- || -----
 | |  ||  | |  ||  |O|
----- || ----- || -----
 | |  ||  | |  ||  | |

```

now bot1 is going to be called with these arguments:

```
X
---------
---------
---------
--------X
---------
---------
---------
---------
----0----
---------
84

```
4. Now bot1 must move in board 4. However, bot1 is a naughty little bot, and decides to move in board 3. It prints '30'. The board does not change at all. The master bot keeps track of this. Now bot2 will be called with these arguments:

```
O
---------
---------
---------
--------X
---------
---------
---------
---------
----0----
---------
xx

```
5. Now bot 2 can go anywhere it wants (except for 38 and 84, of course). This continues until somebody wins 3 of the master boards in a row. Then, there is a second matchup where bot2 is X and gets to go first.
6. This repeats until every single bot has played every other bot.

# Scoring

The scoring works like this:

The winner of a each match gets `100 + number of open spots` points. That way, it is more valuable if your bot wins quickly. Every time your bot makes an invalid move, it loses 1 point. If after 250 rounds, neither bot has won, each bot loses 10 points, and we go on to the next round.

---

Everything will be put into a directory that contains

1. The controller bot. This is a C++ program that I have written. You can look at the controller bot source code here. Please let me know if you see something that isn't right with the controller.
2. A text file named `instructions.txt` This file will look something like this:

```
[Total number of bots that are competing]

[bot1Name] [bot1 command to run]
[bot2Name] [bot2 command to run]
...

```
3. A folder for each bot. This folder will hold your program (Whether it's a script or a binary) and ONE text file named `data.txt` that your bot can read and write whatever it wants to.

# Technical specifications and rule clarifications

* Any bot that attempts to read/write something from anywhere not inside of it's folder will be kicked from the game.
* Your program must be able to run on a macbook running Yosemite. Currently supported languages are python (2.7.9 and 3.4.2), C/C++, objective-C, perl, ruby, bash, PHP, Java, C#, javascript and Haskell. There are a lot more, but these are just the ones I can think of right now. I will add more as time goes on. If you want to compete in a specific language, message me or comment, and I'll add it to the list if possible.
* If a board is won, but there is still space, you still cannot move into one of the open spots.
* Note that the working directory of your submission will be the directory that contains the controller and all the other bots, NOT the directory that contains your bot.
* Please post along with your controller bot code the correct command to compile (if applicable) and to run your bot. Most of this will be done from the OS X terminal, which is fairly similar to a linux terminal.
* Bots must complete in under a second. Unfortunately, I am not quite competent enough to add a timer to the controller bot. However, I will manually time the bots.

---

# Results!

Well, I was right. I forgot to make the controller bot check to see if the masterBoard is full. If the masterBoard is full, then EVERY move is invalid, but it continues to call the bots, which is probably why there were so many invalid moves. I have it fixed now. Here are the official results with the most current version of all of the bots.

```
Bot 1, goodRandBot, has 1 wins and made 0 illegal moves, for a total of 133 points.
Bot 2, naiveBot, has 3 wins and made 48 illegal moves, for a total of 361 points.
Bot 3, depthBot, has 5 wins and made 0 illegal moves, for a total of 664 points.
Bot 4, middleBot, has 1 wins and made 20 illegal moves, for a total of 114 points.

With 4 bots, This program took 477.471 seconds to finish.

```

Depth Bot is the reigning champion! At least, for right now.

# Answer
# Python 2.7, Depth

An alpha-beta pruning implementation without anything too fancy. It does try to order moves in a less naive way to maximize the alpha-beta eliminations. I will probably try to speed it up, but honestly I don't know how competitive Python can be if it comes down to a question of speed.

```
class DepthPlayer:
    def __init__(self,depth):
        self.depth = depth

    def score(self,master,subs,last_move):
        total = 0
        for x in range(3):
            for y in range(3):
                c = master[3*y+x]
                if c == 0:
                    total += sum(subs[3*y+x])
                else:
                    total += c*10
                    for (dx,dy) in [(1,-1),(1,0),(0,1),(1,1)]:
                        if x+dx<=2 and 0<=y+dy<=2 and master[3*(y+dy)+(x+dx)] == c:
                            total += c*10
        if last_move is None or master[last_move[1]] != 0 or 0 not in subs[last_move[1]]:
            total += 5
        return total

    def winner(self,board):
        for y in range(3):
            row = board[3*y:3*y+3]
            if 0!=row[0]==row[1]==row[2]:
                return row[0]
        for x in range(3):
            col = board[x:9:3]
            if 0!=col[0]==col[1]==col[2]:
                return col[0]
        if 0!=board[0]==board[4]==board[8]:
            return board[0]
        if 0!=board[2]==board[4]==board[6]:
            return board[2]

        return 0

    def parse(self,input):
        lines = input.split('\n')
        team = lines[0]
        subs_str = lines[1:10]
        master_str = lines[10]
        last_move_str = lines[11]

        master = [1 if c==team else 0 if c=='-' else -1 for c in master_str]
        subs = [[1 if c==team else 0 if c=='-' else -1 for c in sub_str] for sub_str in subs_str]
        if last_move_str == 'xx':
            last_move = None

        else:
            last_move = [int(c) for c in last_move_str]
        return master,subs,last_move

    def alphabeta(self, master,subs,last_move, depth, alpha, beta, player):
        if depth == 0:
            return self.score(master,subs,last_move),None
        w = self.winner(master)
        if w != 0:
            return w*1000,None

        if player:
            v = -10000
            best = None
            for n_master,n_subs,n_last_move in self.all_moves(master,subs,last_move,1):
                nv,_ = self.alphabeta(n_master,n_subs,n_last_move, depth-1, alpha, beta, False)
                if nv>v:
                    v = nv
                    best = n_last_move
                alpha = max(alpha, v)
                if beta <= alpha:
                    break
            return v,best
        else:
            v = 10000
            best = None
            for n_master,n_subs,n_last_move in self.all_moves(master,subs,last_move,-1):
                nv,nb = self.alphabeta(n_master,n_subs,n_last_move, depth-1, alpha, beta, True)
                if nv<v:
                    v = nv
                    best = n_last_move
                beta = min(beta, v)
                if beta <= alpha:
                    break
            return v,best

    def make_move(self,master,subs,move,player):
        n_subs = [sub[:] for sub in subs]
        n_master = master[:]
        n_subs[move[0]][move[1]] = player
        if n_master[move[0]] == 0:
            n_master[move[0]] = self.winner(n_subs[move[0]])
        return n_master,n_subs,move

    def sub_moves(self,board):
        first = []
        second = []
        third = []
        for i in range(9):
            if board[i] != 0:
                continue
            y,x = divmod(i,3)
            c=-2
            if   x==0 and 0!=board[i+1]==board[i+2]>c: c=board[i+1]
            elif x==1 and 0!=board[i-1]==board[i+1]>c: c=board[i-1]
            elif x==2 and 0!=board[i-2]==board[i-1]>c: c=board[i-2]
            if   y==0 and 0!=board[i+3]==board[i+6]>c: c=board[i+3]
            elif y==1 and 0!=board[i-3]==board[i+3]>c: c=board[i-3]
            elif y==2 and 0!=board[i-6]==board[i-3]>c: c=board[i-6]
            if i in [0,4,8] and 0!=board[(i+4)%12]==board[(i+4)%12]>c: c=board[i-6]
            if i in [2,4,6] and 0!=board[6 if i==2 else i-2]==board[2 if i==6 else i+2]>c: c=board[i-6]

            if c==-2:   third.append(i)
            elif c==-1: second.append(i)
            else:       third.append(i)
        return first+second+third

    def all_moves(self,master,subs,last_move,player):
        if last_move is not None and master[last_move[1]]==0 and 0 in subs[last_move[1]]:
            for i in self.sub_moves(subs[last_move[1]]):
                yield self.make_move(master,subs,[last_move[1],i],player)

        else:
            for j in range(9):
                if master[j]==0 and 0 in subs[j]:
                    for i in self.sub_moves(subs[j]):
                        yield self.make_move(master,subs,[j,i],player)

    def move(self,master,subs,last_move):
        return self.alphabeta(master,subs,last_move, self.depth, -10000, 10000, True)[1]

    def run(self,input):
        result = self.move(*self.parse(input))
        if result:
            return str(result[0])+str(result[1])

def print_board(subs,player):
    string = ""
    for row in range(9):
        for sub in subs[row/3*3:row/3*3+3]:
            for c in sub[row%3*3:row%3*3+3]:
                string += "-XO"[c*(1 if player=='X' else -1)]
            string += ' '
        if row%3 == 2:
            string += '\n'
        string += '\n'
    print string

def to_string(master,subs,last_move,player):
    string = player+'\n'
    for sub in subs:
        for c in sub:
            string += "-XO"[c*(1 if player=='O' else -1)]
        string += '\n'
    for c in master:
        string += "-XO"[c*(1 if player=='O' else -1)]
    string += '\n'+str(last_move[0])+str(last_move[1])
    return string

import sys
command = '\n'.join(sys.argv[1:])
print DepthPlayer(8).run(command)

```

To run it, you can simply do `python Depth.py <input>`, though I would suggest using `pypy` as it speeds it up noticeably.

Also I don't know how fast your system is but you can modify the first argument to `DepthPlayer` at the very end to be higher if it can still run in the specified time (on my system it completed almost all things very quickly with a depth of 7 or 8, but there were a few cases that were near or above a second so I set it to 6 to be safe).
> 5 votes

# Answer
# Java, Naive

If possible, it wins. Otherwise, it prevents an opponent from winning.

```
import java.util.Arrays;

public class Naive {

    public static void main(String[] args) {

        char[][] board = new char[9][9];
        for (int i = 0; i < 9; i++) {
            board[i] = args[i + 1].toCharArray();
        }
        char[] metaBox = args[10].toCharArray();

        char a = args[0].charAt(0),
                b = (char) ('X' + 'O' - a);

        int legalBox = args[11].charAt(1) - '0';
        boolean legalAnywhere = legalBox == 'x' - '0';
        if (!legalAnywhere) {
            if (wins(board[legalBox], 'X') || wins(board[legalBox], 'O')) {
                legalAnywhere = true;
            }
        }
        a:
        if (!legalAnywhere) {
            for (int i = 0; i < 9; i++) {
                if (board[legalBox][i] == '-') {
                    break a;
                }
            }
            legalAnywhere = true;
        }

        if (legalAnywhere) {
            chooseMove(board, metaBox, a, b);
        } else {
            chooseMove(board, metaBox, a, b, legalBox);
        }
    }

    static boolean canWinWith(char[] box, char c) {
        for (int i = 0; i < 9; i++) {
            if (wins(box, i, c)) {
                return true;
            }
        }
        return false;
    }

    static boolean wins(char[] box, int move, char c) {
        char[] copy = Arrays.copyOf(box, 9);
        copy[move] = c;
        return wins(copy, c);
    }

    static boolean wins(char[] box, char c) {
        return (box[0] == c && box[1] == c && box[2] == c)
               || (box[3] == c && box[4] == c && box[5] == c)
               || (box[6] == c && box[7] == c && box[8] == c)
               || (box[0] == c && box[3] == c && box[6] == c)
               || (box[1] == c && box[4] == c && box[7] == c)
               || (box[2] == c && box[5] == c && box[8] == c)
               || (box[0] == c && box[4] == c && box[8] == c)
               || (box[2] == c && box[4] == c && box[6] == c);
    }

    static void endWith(int box, int i) {
        System.out.println("" + box + i);
        System.exit(0);
    }

    private static void chooseMove(char[][] board, char[] metaBox, char a, char b, int legalBox) {
        for (int i = 0; i < 9; i++) {
            if (wins(board[legalBox], i, a) && board[legalBox][i] == '-') {
                endWith(legalBox, i);
            }
        }
        for (int i = 0; i < 9; i++) {
            if (wins(board[legalBox], i, b) && board[legalBox][i] == '-') {
                endWith(legalBox, i);
            }
        }
        for (int i = 0; i < 9; i++) {
            if (board[legalBox][i] == '-') {
                if (!canWinWith(board[i], b)) {
                    endWith(legalBox, i);
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            if (board[legalBox][i] == '-') {
                endWith(legalBox, i);
            }
        }
        throw new RuntimeException("No move chosen!");
    }

    private static void chooseMove(char[][] board, char[] metaBox, char a, char b) {
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (wins(board[box], i, a) && board[box][i] == '-') {
                    endWith(box, i);
                }
            }
        }
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (wins(board[box], i, b) && board[box][i] == '-') {
                    endWith(box, i);
                }
            }
        }
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (board[box][i] == '-') {
                    if (!canWinWith(board[i], b)) {
                        endWith(box, i);
                    }
                }
            }
        }
        for (int box = 0; box < 9; box++) {
            for (int i = 0; i < 9; i++) {
                if (board[box][i] == '-') {
                    endWith(box, i);
                }
            }
        }
        throw new RuntimeException("No move chosen!");
    }
}

```
> 2 votes

# Answer
# Python 2, MiddleBot

MiddleBot likes the middle. Before the central game (4) is won, it will try to grab the centre square of as many games as possible, forcing the opponent back to the middle game again and again.
Once this is done, it tries to win any games it can, or just fills the first available space if not (need to work on its late game, I think)

```
from random import randint
import sys
command_in = '\n'.join(sys.argv[1:])
class MiddleBot:

    def scan_in(self,the_game):

        lines = the_game.split('\n')
        self.us = lines[0]
        if self.us == 'X':
            self.them = 'O'
        else:
            self.them = 'X'
        self.games = lines[1:10]
        self.metagame = lines[10]
        self.last_move = lines[11]

        try:
            self.sub_board = int(self.last_move[1])
        except ValueError:
            self.sub_board = self.last_move[1]

    def empty(self,game,target):
        if self.games[int(game)][int(target)] == '-':
            self.emptycell = 1
        else: self.emptycell = 0

    def empty_fill(self,game):
        #checks for next empty space, fills it
        for k in xrange(0,8):
            self.empty(game,k)
            if self.emptycell == 1:
                self.first_empty_space = k
                break
            if self.emptycell == 0:
                game = randint(0,8)
                self.first_empty_space = 4

    def aim_for_target(self,game,target):
        if self.games[int(game)][int(target)] == '-':
            self.move = `game` + `target`
        else:
            self.empty_fill(game)
            self.move = `game` + `self.first_empty_space`

    #define all win conditions
    win = [0]*8
    win[0] = [0,1,2]
    win[1] = [3,4,5]
    win[2] = [6,7,8]
    win[3] = [0,3,6]
    win[4] = [1,4,7]
    win[5] = [2,5,8]
    win[6] = [0,4,8]
    win[7] = [2,4,6]

    #check if current board state is one move away from 'us' winning
    def aim_for_win(self,game):
            for k in xrange(0,len(self.win)):
                if self.games[self.sub_board][self.win[k][0]] == self.games[self.sub_board][self.win[k][1]] == self.us:
                    self.empty(self.sub_board,self.win[k][2])
                    if self.emptycell == 1:
                        self.move = `self.sub_board`+`self.win[k][2]`
                    else:
                        self.empty_fill(self.sub_board)
                        self.move = `self.sub_board`,`self.first_empty_space`
                elif self.games[self.sub_board][self.win[k][0]] == self.games[self.sub_board][self.win[k][2]] == self.us:
                    self.empty(self.sub_board,self.win[k][1])
                    if self.emptycell == 1:
                        self.move = `self.sub_board`+`self.win[k][1]`
                    else:
                        self.empty_fill(self.sub_board)
                        self.move = `self.sub_board`+`self.first_empty_space`
                elif self.games[self.sub_board][self.win[k][1]] == self.games[self.sub_board][self.win[k][2]] == self.us:
                    self.empty(self.sub_board,self.win[k][0])
                    if self.emptycell == 1:
                        self.move = `self.sub_board`+`self.win[k][0]`
                    else:
                        self.empty_fill(self.sub_board)
                        self.move = `self.sub_board`+`self.first_empty_space`
                else:
                    self.empty_fill(self.sub_board)
                    self.move = `self.sub_board`+`self.first_empty_space`

    def play(self):
        #If the middle board is not won, aim for the middle square of each board
        if self.metagame[4] == '-':
            if self.sub_board == 4 or self.sub_board == 'x':
                self.aim_for_target(4,4)
            else:
                self.aim_for_target(self.sub_board,4)
        else:
            #once the middle board is won, pretty much plays randomly, aiming to win if it can, otherwise just filling the first empty space in each subgame
            played = 0
            if self.sub_board == 'x':
                self.sub_board = randint(0,8)
            while played == 0:
                if self.metagame[int(self.sub_board)] == '-':
                    self.aim_for_win(self.sub_board)
                    played = 1
                else:
                    self.sub_board = randint(0,8)
        return self.move

    def run(self,game_board):
        self.scan_in(game_board)
        self.play()
        return self.move

print MiddleBot().run(command_in)

```

To run it, `python MiddleBot.py <input>` It seems to happily run under a second for me, so hopefully it will for you as well
> 2 votes

# Answer
Might as well throw my own bot into the mix.

# python 2, goodRandomBot

```
import sys
from random import choice

args = sys.argv
if len(args) < 13:
    print ("I can't work with this!\n")
    sys.exit()

whoAmI = args[1];
masterBoard = list(args[11])
board = []
for i in range(2, 11):
    board.append(list(args[i]))

oppMove = args[12]

def findAllValidMoves(board, masterBoard):
    validMoves = []
    for row in range(9):
        if masterBoard[row] != '-':
            continue
        for col in range(len(board[row])):
            if board[row][col] == '-':
                validMoves.append(str(row) + str(col))
    return validMoves

validMoves = []
if oppMove == "xx" or masterBoard[int(oppMove[1])] != "-":
    validMoves = findAllValidMoves(board, masterBoard)

else:
    row = int(oppMove[1])
    for col in range(len(board[row])):
        if board[row][col] == '-' and masterBoard[row] == "-":
            validMoves.append(str(row) + str(col))

if (validMoves == []):
    validMoves = findAllValidMoves(board, masterBoard)

print choice(validMoves)

```

This bot doesn't care where it moves, as long as it is a valid move. Picks at random from all valid moves, and makes an average of `0` invalid moves.
> 0 votes

---
Tags: game, king-of-the-hill, tic-tac-toe
---


title: The Star-Spangled Code Challenge

text:
# Question
Title: The Star-Spangled Code Challenge
The flag of the United States of America contains, in its canton, 50 stars, representing the 50 states.

In the past, when there were fewer states, there were of course fewer stars, and they were arranged differently. For example, from 1912-1959 (after the admission of New Mexico and Arizona but before Alaska), there were 48 stars in a 6×8 rectangular arrangement.

The 37-star flag used from 1867-1877 (after the admission of Nebraska but before Colorado) had an asymmetric star pattern.

In case a 51st state is added in the future, the Army Institute of Heraldry has already developed a preliminary design for a new flag.

But there's no *general* algorithm for arranging the stars, so let's make one!

# The challenge

**Write a program that will, for a given number of stars to place in the canton (blue part) of a US flag, output optimal coordinates at which to place those stars.** The coordinate system is defined with the canton \[*not* the flag as a whole\] with 0≤x≤W and 0≤y≤H.

For the purpose of this challenge, an “optimal” arrangement is defined as one that **minimizes the mean (Euclidean) distance between a point in the canton and the center of the nearest star.**

A straightforward (if maybe suboptimal) algorithm to approximate this value is:

```
def mean_distance_to_nearest_star(stars, width, height, point_density=100):
   """
   Approximate the mean distance between a point in the rectangle
   0 < x < width and 0 < y < height, and the nearest point in stars.

   stars -- list of (x, y) points
   width, height -- dimensions of the canton
   """
   total = 0.0
   nx = round(width * point_density)
   ny = round(height * point_density)
   for ix in range(nx):
       x = (ix + 0.5) * width / nx
       for iy in range(ny):
          y = (iy + 0.5) * width / ny
          min_dist = float('inf')
          for sx, sy in stars:
              min_dist = min(min_dist, math.hypot(x - sx, y - sy))
          total += min_dist
   return total / (nx * ny)

```

Your program shall take three command-line arguments (not counting the program name itself):

1. The number of stars to put in the canton.
2. The width of the canton. (Must accept floating-point values.)
3. The height of the canton. (Must accept floating-point values.)

(If your preferred programming language doesn't support command-line arguments, do something reasonably equivalent, and document it in your answer.)

The output should consist of comma-separated X and Y values, one to a line. (Order of the points doesn't matter.)

For example:

```
~$ flagstar 5 1.4 1.0
0.20,0.20
0.20,0.80
0.70,0.50
1.20,0.20
1.20,0.80

```

# Additional rules & notes

* I have the right to close loopholes in the rules at any time.
* ~~Deadline for answers is **Friday, July 4** at 24:00 CDT (UTC-05:00).~~ Due to lack of answers, the deadline has been extended. TBA.
* Include in your answer:
    + Your program's code
    + An explanation of how it works
    + Its output with the command-line arguments `50 1.4 1.0`
* Your program must run within a reasonable amount of time: At most 5 min on a typical PC. I won't be ultra-strict about this, but will disqualify your program if it takes *hours*.
* Your program must be deterministic, i.e., always give exactly the same output for the same arguments. So, don't depend on `time()` or `rand()`. Monte Carlo methods are OK as long as you roll your own PRNG.
* Only the center points of the stars matter. Don't worry about trying to avoid overlap or anything like that.

# Scoring

* Minimize the mean distance from a point in the canton to the nearest star. (See above.)
* You may be scored based on any historical US flags, between 13 and 50 stars. The exact algorithm for weighting scores into a single ranking will be posted later.
* In case of a tie, the winner will be chosen by number of net upvotes.
* I will probably post a program of my own, but will exclude myself from being eligible for the checkmark.

# Answer
> 4 votes
# Javascript - move stars towards most isolated point

(with an animation of the process)

The approach is very simple:

* choose a large number of random points
* find the nearest star to each
* choose the point for which the nearest star is most distant
* move that star nearer to that point

This process is repeated a large number of times, gradually decreasing the amount by which the stars are moved. This reduces the maximum distance from a point to the nearest star, indirectly reducing the mean distance from a point to the nearest star.

As required by the question, this does not use the built in random function, instead using xorshift.

Much of the code covers set up and animation - the part that applies the algorithm is the function `adjustStars`.

# Code

You can watch the process in progress in the Stack Snippet below.

```
stars = [];
timeoutId = 0;

resetRandomNumberGenerator();

function resetRandomNumberGenerator() {
  rng_x = 114; // Numbers for the random number generator.
  rng_y = 342;
  rng_z = 982;
  rng_w = 443;
}

$(document).ready(function() {
  c = document.getElementById('canton');
  ctx = c.getContext('2d');
  resizeCanvas();
});

function stop() {
  clearTimeout(timeoutId);
}

function arrange() {
  clearTimeout(timeoutId);
  resetStars();
  resetRandomNumberGenerator();
  maxStepSize = Math.min(cantonWidth, cantonHeight) / 4;
  adjustStars(maxStepSize, 8000, 10000);
}

function resizeCanvas() {
  cantonWidth = parseFloat($('#width').val());
  cantonHeight = parseFloat($('#height').val());
  starRadius = cantonHeight / 20;
  document.getElementById('canton').width = cantonWidth;
  document.getElementById('canton').height = cantonHeight;
  ctx.fillStyle = 'white';
  resetStars();
}

function resetStars() {
  stop();
  stars = [];
  population = parseInt($('#stars').val(), 10);
  shortSide = Math.floor(Math.sqrt(population));
  longSide = Math.ceil(population / shortSide);
  if (cantonWidth < cantonHeight) {
    horizontalStars = shortSide;
    verticalStars = longSide;
  } else {
    horizontalStars = longSide;
    verticalStars = shortSide;
  }
  horizontalSpacing = cantonWidth / horizontalStars;
  verticalSpacing = cantonHeight / verticalStars;
  for (var i = 0; i < population; i++) {
    x = (0.5 + (i % horizontalStars)) * horizontalSpacing;
    y = (0.5 + Math.floor(i / horizontalStars)) * verticalSpacing;
    stars.push([x, y]);
  }
  drawStars();
  updateOutputText();
}

function adjustStars(stepSize, maxSteps, numberOfPoints) {
  $('#stepsRemaining').text(maxSteps + ' steps remaining');
  points = randomPoints(numberOfPoints);
  mostIsolatedPoint = 0;
  distanceToNearestStar = 0;
  for (var i = 0; i < numberOfPoints; i++) {
    point = points[i];
    x = point[0];
    y = point[1];
    star = stars[nearestStar(x, y)];
    d = distance(x, y, star[0], star[1]);
    if (d > distanceToNearestStar) {
      distanceToNearestStar = d;
      mostIsolatedPoint = i;
    }
  }
  point = points[mostIsolatedPoint];
  x = point[0];
  y = point[1];

  starToMove = nearestStar(x, y);

  star = stars[starToMove];
  separationX = x - star[0];
  separationY = y - star[1];
  if (separationX || separationY) {
    hypotenuse = distance(x, y, star[0], star[1]);
    currentStep = Math.min(stepSize, hypotenuse / 2);
    deltaX = currentStep * separationX / hypotenuse;
    deltaY = currentStep * separationY / hypotenuse;
    star[0] += deltaX;
    star[1] += deltaY;
    if (star[0] < 0) star[0] = 0;
    if (star[0] > cantonWidth) star[0] = cantonWidth;
    if (star[1] < 0) star[1] = 0;
    if (star[1] > cantonHeight) star[1] = cantonHeight;

    drawStars();
    updateOutputText();
  }

  if (maxSteps > 0) {
    timeoutId = setTimeout(adjustStars, 10, stepSize * 0.9992, maxSteps - 1, numberOfPoints);
  }
}

function updateOutputText() {
  starText = '';
  for (var i = 0; i < stars.length; i++) {
    starText += stars[i][0] + ', ' + stars[i][1] + '\n';
  }
  $('#coordinateList').text(starText);
}

function randomPoints(n) {
  pointsToReturn = [];
  for (i = 0; i < n; i++) {
    x = xorshift() * cantonWidth;
    y = xorshift() * cantonHeight;
    pointsToReturn.push([x, y]);
  }
  return pointsToReturn;
}

function xorshift() {
  rng_t = rng_x ^ (rng_x << 11);
  rng_x = rng_y;
  rng_y = rng_z;
  rng_z = rng_w;
  rng_w = rng_w ^ (rng_w >> 19) ^ rng_t ^ (rng_t >> 8);
  result = rng_w / 2147483648
  return result
}

function nearestStar(x, y) {
  var distances = [];
  for (var i = 0; i < stars.length; i++) {
    star = stars[i];
    distances.push(distance(x, y, star[0], star[1]));
  }
  minimum = Infinity;
  for (i = 0; i < distances.length; i++) {
    if (distances[i] < minimum) {
      minimum = distances[i];
      nearest = i;
    }
  }
  return nearest;
}

function distance(x1, y1, x2, y2) {
  var x = x2 - x1;
  var y = y2 - y1;
  return Math.sqrt(x * x + y * y);
}

function drawStars() {
  ctx.clearRect(0, 0, cantonWidth, cantonHeight);
  for (i = 0; i < stars.length; i++) {
    star = stars[i];
    x = star[0];
    y = star[1];
    drawStar(x, y);
  }
}

function drawStar(x, y) {
  ctx.beginPath();
  ctx.moveTo(x, y - starRadius);
  ctx.lineTo(x - 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.lineTo(x + 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x - 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x + 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.fill();
}
```

```
canvas {
  margin: 0;
  border: medium solid gray;
  background-color: blue;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<input id='stars' onchange='resetStars()' type='number' value='13' min='13' max='50' maxlength='2' step='1'>stars
<br>
<input id='width' onchange='resizeCanvas()' type='number' value='494' min='1' max='500' maxlength='3' step='any'>width
<br>
<input id='height' onchange='resizeCanvas()' type='number' value='350' min='1' max='500' maxlength='3' step='any'>height
<br>
<button type='button' onclick='resetStars()'>Reset Stars</button>
<button type='button' onclick='arrange()'>Arrange Stars</button>
<button type='button' onclick='stop()'>Stop</button>
<textarea id='stepsRemaining' rows='1' readonly></textarea>
<br>
<canvas id='canton' width='494' height='350'></canvas>
<br>
<textarea id='coordinateList' rows='50' cols='40' readonly></textarea>
```

# Output for 50 stars

(width = 1.4, height = 1.0)

Mean distance estimated at 0.0655106697162357.

Coordinates:

```
0.028377044205135808, 0.2128159150679491
0.10116766857540277, 0.05156676609341312
0.2903566419069437, 0.07216263690037035
0.49154061258041604, 0.004436102736309105
0.6930026352073071, 0.07060477929576484
1.0988644764108417, 0.022979778480838074
1.1735677936511582, 0.18600858289592742
1.3056806950504931, 0.062239869036660435
0.3967626880807638, 0.24483447327177033
0.27004118129346155, 0.40467589936498805
0.4996665039421278, 0.13023282430440133
0.5148978532656602, 0.6161298793146592
0.5907056537744844, 0.2614323599301046
0.8853042432872087, 0.048123917861564044
0.7753680330575412, 0.22938793622044834
1.365432954694329, 0.2355377720528128
0.1985172068244217, 0.23551298706793927
0.4477558465270544, 0.4170264112485973
0.6084424566752479, 0.7764909501169484
0.6099528761580699, 0.4395002434593519
0.9506038166406011, 0.34903243854585914
1.1898331497634231, 0.5756784243472182
1.0933574395540542, 0.46422120794648786
1.1516574254138159, 0.2930213338333888
0.07646053006349718, 0.40665000611360175
0.0634456093015551, 0.5853189455014883
0.3470036636019768, 0.5938838331082922
0.7591083341283029, 0.4005456925638841
0.9745306853981277, 0.184624209972443
1.3552011948311598, 0.549607060691302
1.3334000268566828, 0.7410204535471169
1.2990417572304487, 0.39571229988825735
0.05853941030364222, 0.7734808757471414
0.19396697551982484, 0.5678753467094985
0.7103231124251072, 0.5955041661956884
0.6168410756137566, 0.948561537739087
0.8967624790188228, 0.5368666961690878
0.9751229155529001, 0.8323724819557795
0.9987127931392165, 0.652902038374714
1.3231032600971289, 0.9164326184290812
0.20785221980162555, 0.7566700629874374
0.3987967842137651, 0.7678025218448816
0.44395949605458546, 0.9137553802571048
0.775611700149756, 0.9029717946067138
0.806442448003616, 0.7328147396477286
0.9481952441521928, 0.9872963855418118
1.1528689317425114, 0.9346775634274639
1.1651295140721658, 0.7591158327925681
0.09316709042512515, 0.934205211493484
0.2769325337580081, 0.9341145493466471

```

# Answer
> 3 votes
Here's a simple example. It always arranges the stars into a rectangular grid, and optimizes it by choosing the factorization in which the grid cells are as close to square as possible. It works great when the number of stars has a divisor close to its square root, and pessimally when the number of stars is prime.

```
from __future__ import division
import math
import sys

def divisors(n):
    """
    Return all divisors of n (including n itself) as a set.
    """
    result = {1, n}
    # Use +2 instead of +1 to allow for floating-point error.
    for i in range(2, int(math.sqrt(n)) + 2):
        if n % i == 0:
            result.add(i)
            result.add(n // i)
    return result

def squareness(width, height):
    """
    Given the dimensions of a rectangle, return a value between 0 and 1
    (1 iff width == height) measuring how close it is to being a square.
    """
    if width and height:
        return min(width / height, height / width)
    else:
        return 0.0

def star_grid(num_stars, width, height):
    """
    Return the factors (x, y) of num_stars that optimize the mean
    distance to the nearest star.
    """
    best_squareness = 0.0
    best_dimensions = (None, None)
    for nx in divisors(num_stars):
        ny = num_stars // nx
        sq = squareness(width / nx, height / ny)
        if sq > best_squareness:
            best_squareness = sq
            best_dimensions = (nx, ny)
    return best_dimensions

def star_coords(num_stars, width, height):
    """
    Return a list of (x, y) coordinates for the stars.
    """
    nx, ny = star_grid(num_stars, width, height)
    for ix in range(nx):
        x = (ix + 0.5) * width / nx
        for iy in range(ny):
            y = (iy + 0.5) * height / ny
            yield (x, y)

def _main(argv=sys.argv):
    num_stars = int(argv[1])
    width = float(argv[2])
    height = float(argv[3])
    for coord in star_coords(num_stars, width, height):
        print('%g,%g' % coord)

if __name__ == '__main__':
    _main()

```

# Output for 50 stars

(width = 1.4, height = 1.0)

A 10×5 rectangle.

```
0.07,0.1
0.07,0.3
0.07,0.5
0.07,0.7
0.07,0.9
0.21,0.1
0.21,0.3
0.21,0.5
0.21,0.7
0.21,0.9
0.35,0.1
0.35,0.3
0.35,0.5
0.35,0.7
0.35,0.9
0.49,0.1
0.49,0.3
0.49,0.5
0.49,0.7
0.49,0.9
0.63,0.1
0.63,0.3
0.63,0.5
0.63,0.7
0.63,0.9
0.77,0.1
0.77,0.3
0.77,0.5
0.77,0.7
0.77,0.9
0.91,0.1
0.91,0.3
0.91,0.5
0.91,0.7
0.91,0.9
1.05,0.1
1.05,0.3
1.05,0.5
1.05,0.7
1.05,0.9
1.19,0.1
1.19,0.3
1.19,0.5
1.19,0.7
1.19,0.9
1.33,0.1
1.33,0.3
1.33,0.5
1.33,0.7
1.33,0.9

```

# Answer
> 0 votes
# Javascript - move a star randomly if mean distance is reduced

(with an animation of the process)

This doesn't give such a busy animation as my first answer, having long periods with no movement as potential rearrangements are tested and rejected. However, the final result has a lower mean distance, so this method is an improvement.

The approach is still very simple:

* Choose a star at random
* Move it a random distance in a random direction
* If the mean distance is reduced, keep the new position

This process is repeated a large number of times, gradually decreasing the amount by which the stars are moved. The random choice of distance to move is biased towards smaller distances, so progress is in small alterations interspersed with the occasional larger jump. Each step takes longer than in my first answer, as measuring the mean distance is a slow process requiring sampling the entire canton.

As required by the question, this does not use the built in random function, instead using xorshift.

Much of the code covers set up and animation - the part that applies the algorithm is the function `adjustStars`.

# Code

You can watch the process in progress in the Stack Snippet below.

```
stars = [];
timeoutId = 0;

resetRandomNumberGenerator();

function resetRandomNumberGenerator() {
  rng_x = 114; // Numbers for the random number generator.
  rng_y = 342;
  rng_z = 982;
  rng_w = 443;
}

$(document).ready(function() {
  c = document.getElementById('canton');
  ctx = c.getContext('2d');
  resizeCanvas();
});

function stop() {
  clearTimeout(timeoutId);
}

function arrange() {
  clearTimeout(timeoutId);
  resetStars();
  resetRandomNumberGenerator();
  maxStepSize = Math.min(cantonWidth, cantonHeight) / 16;
  adjustStars(maxStepSize, 7000, 15000);
}

function resizeCanvas() {
  cantonWidth = parseFloat($('#width').val());
  cantonHeight = parseFloat($('#height').val());
  starRadius = cantonHeight / 20;
  document.getElementById('canton').width = cantonWidth;
  document.getElementById('canton').height = cantonHeight;
  ctx.fillStyle = 'white';
  resetStars();
}

function resetStars() {
  stop();
  stars = [];
  population = parseInt($('#stars').val(), 10);
  shortSide = Math.floor(Math.sqrt(population));
  longSide = Math.ceil(population / shortSide);
  if (cantonWidth < cantonHeight) {
    horizontalStars = shortSide;
    verticalStars = longSide;
  } else {
    horizontalStars = longSide;
    verticalStars = shortSide;
  }
  horizontalSpacing = cantonWidth / horizontalStars;
  verticalSpacing = cantonHeight / verticalStars;
  for (var i = 0; i < population; i++) {
    x = (0.5 + (i % horizontalStars)) * horizontalSpacing;
    y = (0.5 + Math.floor(i / horizontalStars)) * verticalSpacing;
    stars.push([x, y]);
  }
  drawStars();
  updateOutputText();
}

function adjustStars(stepSize, maxSteps, numberOfPoints) {
  $('#stepsRemaining').text(maxSteps + ' steps remaining');
  var points = randomPoints(numberOfPoints);
  currentMean = meanDistance(stars, points);
  potentialStars = shiftedStars(stepSize);
  potentialMean = meanDistance(potentialStars, points);
  if (potentialMean < currentMean) {
    stars = potentialStars;
  }
  drawStars();
  updateOutputText();

  if (maxSteps > 0) {
    timeoutId = setTimeout(adjustStars, 10, stepSize * 0.999, maxSteps - 1, numberOfPoints);
  }
}

function shiftedStars(stepSize) {
  shifted = [];
  chosenOne = Math.floor(xorshift() * stars.length);
  for (i = 0; i < stars.length; i++) {
    star = stars[i];
    x = star[0];
    y = star[1];
    if (i === chosenOne) {
      for (n = 0; n < 10; n++) {
        x += xorshift() * stepSize;
        x -= xorshift() * stepSize;
        y += xorshift() * stepSize;
        y -= xorshift() * stepSize;
      }
      if (x < 0) x = 0;
      if (x > cantonWidth) x = cantonWidth;
      if (y < 0) y = 0;
      if (y > cantonHeight) y = cantonHeight;
    }
    shifted.push([x, y]);
  }
  return shifted;
}

function meanDistance(arrayOfStars, arrayOfPoints) {
  var totalDistance = 0;
  for (i = 0; i < arrayOfPoints.length; i++) {
    point = arrayOfPoints[i];
    x = point[0];
    y = point[1];
    totalDistance += nearestStarDistance(x, y, arrayOfStars);
  }
  return totalDistance / arrayOfPoints.length;
}

function randomPoints(numberOfPoints) {
  var arrayOfPoints = [];
  for (i = 0; i < numberOfPoints; i++) {
    x = xorshift() * cantonWidth;
    y = xorshift() * cantonHeight;
    arrayOfPoints.push([x, y]);
  }
  return arrayOfPoints;
}

function updateOutputText() {
  starText = '';
  for (var i = 0; i < stars.length; i++) {
    starText += stars[i][0] + ', ' + stars[i][1] + '\n';
  }
  $('#coordinateList').text(starText);
}

function xorshift() {
  rng_t = rng_x ^ (rng_x << 11);
  rng_x = rng_y;
  rng_y = rng_z;
  rng_z = rng_w;
  rng_w = rng_w ^ (rng_w >> 19) ^ rng_t ^ (rng_t >> 8);
  result = rng_w / 2147483648
  return result
}

function nearestStarDistance(x, y, starsToUse) {
  var distances = [];
  for (var i = 0; i < stars.length; i++) {
    star = starsToUse[i];
    distances.push(distance(x, y, star[0], star[1]));
  }
  minimum = Infinity;
  for (i = 0; i < distances.length; i++) {
    if (distances[i] < minimum) {
      minimum = distances[i];
    }
  }
  return minimum;
}

function distance(x1, y1, x2, y2) {
  var x = x2 - x1;
  var y = y2 - y1;
  return Math.sqrt(x * x + y * y);
}

function drawStars() {
  ctx.clearRect(0, 0, cantonWidth, cantonHeight);
  for (i = 0; i < stars.length; i++) {
    star = stars[i];
    x = star[0];
    y = star[1];
    drawStar(x, y);
  }
}

function drawStar(x, y) {
  ctx.beginPath();
  ctx.moveTo(x, y - starRadius);
  ctx.lineTo(x - 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.lineTo(x + 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x - 0.951 * starRadius, y - 0.309 * starRadius);
  ctx.lineTo(x + 0.588 * starRadius, y + 0.809 * starRadius);
  ctx.fill();
}
```

```
canvas {
  margin: 0;
  border: medium solid gray;
  background-color: blue;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.0/jquery.min.js"></script>
<input id='stars' onchange='resetStars()' type='number' value='13' min='13' max='50' maxlength='2' step='1'>stars
<br>
<input id='width' onchange='resizeCanvas()' type='number' value='494' min='1' max='500' maxlength='3' step='any'>width
<br>
<input id='height' onchange='resizeCanvas()' type='number' value='350' min='1' max='500' maxlength='3' step='any'>height
<br>
<button type='button' onclick='resetStars()'>Reset Stars</button>
<button type='button' onclick='arrange()'>Arrange Stars</button>
<button type='button' onclick='stop()'>Stop</button>
<textarea id='stepsRemaining' rows='1' readonly></textarea>
<br>
<canvas id='canton' width='494' height='350'></canvas>
<br>
<textarea id='coordinateList' rows='50' cols='40' readonly></textarea>
```

# Output for 50 stars

(width = 1.4, height = 1.0)

Mean distance estimated at 0.06402754713808706.

Coordinates:

```
0.08147037630270487, 0.07571240182553095
0.24516777356538358, 0.0803538189052793
0.431021735247462, 0.07821284835132788
0.6001163609128221, 0.08278495286739646
0.7668077034213632, 0.0821321119375313
0.941333266969696, 0.08040530195264808
1.1229190363750599, 0.07255685332834291
1.3074771164489858, 0.07681674948141588
0.09227450444336446, 0.2257047798057907
0.33559513774978766, 0.20668611954667682
0.5182463448452704, 0.23841239342827816
0.6630614113293541, 0.26097114328053417
0.821886619004045, 0.23577904321258844
1.012597304977012, 0.23308200382761057
1.174938874706673, 0.22593017096601203
1.3285181935709358, 0.24024108928169902
0.0746772556909648, 0.3920030109869904
0.23006559905554042, 0.3204287339854068
0.4086004105498357, 0.3507788129168045
0.5669847710831315, 0.4371913211100495
0.7399474422203116, 0.41599441829489137
0.9099913571857917, 0.36933063808924294
1.1170137101288482, 0.3905679602615213
1.3037811235560612, 0.3979526346564911
0.09290206345982034, 0.5678420747594305
0.23463227399157258, 0.47552307265325633
0.4042403660145938, 0.5030345851947539
0.6611151741402685, 0.5918138006294138
0.8237963249937061, 0.5663224022272697
0.9812774216782155, 0.5032518469083094
1.146386501309064, 0.570255729516661
1.3185563715676663, 0.5571870810112576
0.07541940949872694, 0.7356649763259809
0.2877585652075202, 0.6321535875762999
0.4952646673275116, 0.6343336480073624
0.6965646728710738, 0.9178076185211137
0.7903485281657828, 0.7508031981325222
0.9774998621426763, 0.6683301268754337
1.1539480102558823, 0.7513836972857155
1.3177199931376755, 0.7245296168327016
0.22215183098388988, 0.7769843436963862
0.4048364942297627, 0.7779653803681718
0.5021290208205218, 0.9254525763987298
0.6058821167972933, 0.7683130432395833
0.8777330967719849, 0.9201076171801651
0.9894820530574747, 0.8172934111543102
1.1143371956097312, 0.9265012354173626
1.3045771339439551, 0.9069856484512913
0.0930066325438706, 0.9157592790749175
0.2959676633891297, 0.9251379492518523

```

---
Tags: code-challenge, geometry
---


# Question
Title: Find minimum difference between numbers in array
STDIN: Array of integers

STDOUT: Smallest difference (the difference between the closest two numbers in the array).

Rules: Given an array of positive integers find the difference between the closest two numbers in the array. Performance should be taken into consideration.

Example:

STDIN: \[55, 99, 6, 29, 1, 523, 3\]

STDOUT: 2 (e.g. 3-1)

Scoring: Although somewhat informal, the shortest, most efficient (performance wise) will win. Creativity will also be taken into consideration.

# Answer
# The R language

**23 characters, O(n log n)**

```
min(diff(sort(scan())))

```

Example:

```
> min(diff(sort(scan())))
1: 55 99 6
4: 29 1 523 3
8:
Read 7 items
[1] 2

```

...The `[1] 2` shows the result `2`. (the \[1\] is to keep track of where in the result vector your are since in R all values are vectors - in this case of length 1)
> 6 votes

# Answer
## Mathematica, 23

```
Min@Differences@Sort@#&

```
> 5 votes

# Answer
### JavaScript, 127 characters

This is a function that takes the array as a string. It may be O((n-1)²/2+n/2-1/2). I have no idea.

```
function(s){s=eval(s);a=Math.abs;m=a(s[i=0]-s[j=1]);for(;i<s.length;j=++i)for(;++j<s.length;)m=(v=a(s[i]-s[j]))<m?v:m;return m}

```
> 2 votes

# Answer
# Scala, O(n log n)

## Script that reads from STDIN (113 chars)

```
val s=Console.readLine.split(",").map(_.toInt).sortBy(i=>i)
if(s.size<2)0 else s.tail.zip(s).map(x=>x._1-x._2).min

```

## Function (94 chars)

```
def m(l:Seq[Int])=if(l.size<2)0 else{val s=l.sortBy(i=>i);s.tail.zip(s).map(x=>x._1-x._2).min}

```
> 2 votes

# Answer
# J, 28

```
<./&(}.-}:)@/:~&.(".&stdin)_

```

Very straightforward J, drawn down by I/O and parsing. For those who don't read J fluently:

* `&` and `@` compose verbs
* `<. /` yields a vector's minimum
* `( }. - }: )` performs pairwise substraction
* `/: ~` sorts up
* `&.` performs dark magic so that the next two are used both in the input and output directions
* `".` parses/presents J data
* `stdin` takes care of I/O
* `_` is a dummy argument to `stdin`
> 2 votes

# Answer
# O(n) space and time

## C++ (1644 chars)

Reads from stdin

```
#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>

int radix(int const& a, int const& r) {return (a >> (r << 3)) & 0xFF;}

template <int R_>
int radix(int const& a) {return radix(a, R_);}

template <typename It_, typename Cont_>
void distribution(It_ first, It_ const& last, Cont_& d_vector, int const& r) {
        d_vector.resize(256, 0);
        std::fill(d_vector.begin(), d_vector.end(), 0);
        for(; first != last; ++first)
                d_vector[radix(*first, r)]++;
}

template <typename It_, typename Cont_>
void split(It_ first, It_ const& last, Cont_& d_vector, Cont_& slots, int const& r) {
        int cnt = 0;
        for(int i=0; i<256; cnt += d_vector[i++])
                std::swap(d_vector[i], cnt);

        slots.resize(cnt, 0);
        for(; first != last; ++first)
                slots[d_vector[radix(*first, r)]++] = *first;
}

int main(int argc, char* const argv[]) {
        std::istream_iterator<int> in(std::cin);
        std::istream_iterator<int> end;
        std::vector<int>           numbers;

        /// Read numbers
        std::copy(in, end, std::back_inserter(numbers));

        /// Sanity checks
        if(1 >= numbers.size()) {
                std::cerr << "not enough numbers" << std::endl;
                return -1;
        }

        /// Sort the numbers 4 times using different radix
        std::vector<int> d_vector(256, 0);
        std::vector<int> slots;
        for(int r=0; r<4; ++r) {
                distribution(numbers.begin(), numbers.end(), d_vector, r);
                split(numbers.begin(), numbers.end(), d_vector, slots, r);
                numbers.swap(slots);
        }

        /// Compute the min difference
        int prev = numbers[1];
        int min  = prev-numbers[0];
        for(std::size_t i=2; i<numbers.size(); ++i) {
                min = std::min(min, numbers[i]-prev);
        }
        std::cout << min << std::endl;
        return 0;
}

```
> 2 votes

# Answer
## APL, 16/18 characters

```
x←⎕⋄⌊/2-/(x[⍒x])

```

Or with explicit output:

```
x←⎕⋄⎕←⌊/2-/(x[⍒x])

```

Example:

```
      x←⎕⋄⌊/2-/(x[⍒x])
⎕:
      55 9 6 29 1 523 3
2

```

Explanation:

* First expression:
    + `x←⎕`: Get the input array (  ) and assign it (  ) to `x`.
* : Expression separator.
* Second expression, right to left:
    + `(x[⍒x])`: Sort the input. `⍒x` returns the set of indices needed to sort `x` in descending order, which is used to index `x` ( `x[...]` ).
    + `2-/`: Splits ( `/` ) the input array into pairs ( `2` ) and finds the difference ( `-` ) between each pair.
    + `⌊/`: Reduce ( `/` ) the array using the floor function (  ).

I used Dyalog APL for this.
> 2 votes

# Answer
# K, 15

......

```
{min@1_-':x@<x}

```
> 2 votes

# Answer
## APL 14

(original...21 chars)

```
{⌊/|{(0≠⍵)/⍵},⍵∘.-⍵}⎕

```

(edit new shorter...15 chars)

```
{⌊/|0~⍨,⍵∘.-⍵}⎕

```

(edit again...14 chars)

```
⌊/|0~⍨,y∘.-y←⎕

```

assuming no two numbers are the same

```
⍝ y←⎕     bring in input
⍝ y∘.-y   create subtraction table of array y against array y
⍝ 0~⍨     remove zeros (from same element against itself
⍝                       on diagonal)
⍝ |       absolute value
⍝ ⌊/      reduce with minimum

```
> 2 votes

# Answer
## D (124 chars) O(n log n) time complexity

```
void main(){int[]a;int b;while(readf("%d ",&b))a~=b;b=~0>>>1;sort!(d,c){d-=c;c=d<0?-d:d;b=b<c?b:c;return d;}(a);writeln(b);}

```

using the comparator to keep a running min *while* sorting
> 1 votes

# Answer
# Haskell, 71 characters, O(n log n)

```
import List;f x=zipWith(-)(tail x)x
main=readLn>>=print.minimum.f.sort

```
> 1 votes

# Answer
# Python 2.6, 56 48 characters, O(n log n)

New version utilizing `min`, `diff`, and `sort` from numpy. Inspired by Tommy's answer.

```
from numpy import*
print min(diff(sort(input()))

```

Original version. Inspired by Zachary Vance's answer.

```
a=sorted(input())
print min(y-x for x,y in zip(a,a[1:]))

```
> 1 votes

# Answer
**C# 180 Characters**

```
using System;using System.Linq;class P{static void Main(int[]a){Action<int[]> b=Array.Sort;b(a);a=a.Select((c,d)=>(a.Length>d+1?a[d+1]-c:-1)).ToArray();b(a);Console.Write(a[1]);}}

```

Readable:

```
using System;
using System.Linq;
class P
{
    static void Main(int[]a)
    {
        Action<int[]> b = Array.Sort;
        b(a);
        a = a.Select((c, d) => (a.Length > d + 1 ? a[d + 1] - c : -1)).ToArray();
        b(a);
        Console.Write(a[1]);
    }
}

```
> 1 votes

# Answer
## Java

```
public static int minDifference(int[] A) {
    Arrays.sort(A);
    if (A.length > 1) {
        int d = Math.abs(A[0] - A[1]);
        for (int i = 0; i <= A.length; i++) {
            if (i + 1 < A.length) {
                int t = Math.abs(A[i] - A[i + 1]);
                if (t < d) d = t;
            }
        }
        return d;
    }
    return -1;
}

```

-1 is returned when an array is too short
> 1 votes

# Answer
# Mathematica 39

Sort standard input,subtract each element n from each element n+1, take the absolute value of those differences, and find the minimum of those.

```
Min[Abs[RotateLeft@# - #] &[Sort@Input[]]]

```
> 1 votes

# Answer
## Perl, 49 characters, O(n log n)

```
say+(sort{$a-$b}map$a*1-($a=$_),sort{$b-$a}<>)[1]

```

The input should be on separate lines; the output is printed after input ends. (I can also make it parse comma-separated input on one line by using the `-naF,` command line switches and replacing `<>` with `@F`.) The `say` command is available since Perl 5.10.0 with the `-E` switch or with `use 5.010`; per meta its use is allowed at no extra cost.

This uses the same sort-and-diff trick as almost everyone else, with a slight twist to deal with the fact that Perl has no built-in diff command. It first sorts the input in descending order, substracts each number from the previous one in the list and re-sorts the result in ascending order. This leaves one negative value (zero minus the largest input) in front of the list, so the code actually outputs the *second* smallest value. Of course, this only works as long as the input contains at least one positive number, but fortunately the spec says that *all* input values must be positive.

(Also, the latest version plays silly tricks with expression evaluation order to shave off a few more chars: apparently `$a-($a=$_)` always evaluates to 0, but `$a*1-($a=$_)` ends up saving the previous value of `$a` on stack before changing it, avoiding the need to store it in a separate variable. With Perl, there ain't no such thing as "undefined behavior"... :)
> 0 votes

# Answer
# J, 10 chars

```
<./2-/\\:~

```

It doesn't include explicit input/output, but appending a list to the end like `<./2-/\\:~1,2,3` or `<./2-/\\:~1 2 3` works as one would expect. I'm not too familiar with J's explicit I/O, unfortunately.

Explanatory refactoring:

```
sort_down =: \:~
pair_sub =: 2&(-/\)
min =: <./
min pair_sub sort_down 1 2 3

```

`pair_sub` is slightly altered, since J has some rules for precedence and verb composition that makes `pair_sub =: 2-/\` give an error and `pair_sub =: 2&-/\` give a different output when used in the sentence `min pair_sub sort_down 1 2 3` as compared to `<./2-/\\:~ 1 2 3`.
> 0 votes

# Answer
Java O(n)

```
public int minimumDifference(int[] arr) {
    int minimum = 0;

    if (null != arr) {
        int length = arr.length;
        if (length == 1) {
            minimum = arr[0];
        }
        if (length == 2) {
            minimum = Math.abs(arr[0] - arr[1]);
        } else if (length > 2) {
            int minimumSoFar = arr[0];
            int secondMinimumSoFar = arr[0];
            for (int i = 0; i < length; i++) {
                if (arr[i] < minimumSoFar) {
                    minimumSoFar = arr[i];
                }
                if (arr[i] > minimumSoFar && arr[i] < secondMinimumSoFar) {
                    secondMinimumSoFar = arr[i];
                }
            }
            minimum = secondMinimumSoFar - minimumSoFar ;
        }
    }
    return minimum;
}

```
> 0 votes

# Answer
Python 3.1.3, 77 chars

```
a=sorted(eval(input()))
print(min([abs(x-y)for x,y in zip(a[::2],a[1::2])]))

```
> -1 votes

---
Tags: code-challenge
---


# Question
Title: Detecting anagrams within a Parent String
Given two strings, a parent string and a query string respectively, your task is to determine how many times the query string, *or an anagram of the query string*; appears in the parent string, in a case-sensitive search.

Examples of Behaviour

**Input 1**

```
AdnBndAndBdaBn
dAn

```

**Output 1**

```
4

```

**Explanation** The substrings are highlighted in bold below:

**Adn**BndAndBdaBn

AdnB**ndA**ndBdaBn

AdnBn**dAn**dBdaBn

AdnBnd**And**BdaBn

Note the search MUST be case sensitive for all searches.

**Input 2**

```
AbrAcadAbRa
cAda

```

**Output 2**

```
2

```

This must work for standard ASCII only. This is code-golf, so shortest number of characters will get the tick of approval. Also please post a non-golfed version of your code along with the golfed version.

# Answer
# Pyth, ~~11~~ 10 bytes

```
lfqSzST.:w

```

1 byte golf thanks to @Jakube.

Demonstration.

Takes the query string, followed by the parent string on a new line.

Ungolfed:

```
z = input()
len(filter(lambda T: sorted(z) == sorted(T), substrings(input())

```
> 5 votes

# Answer
# CJam, 13 bytes

```
le!lf{\/,(}:+

```

(12 bytes, if overlapping is allowed)

```
l$_,lew:$\e=

```

Input goes like:

```
dAn
AdnBndAndBdaBn

```

i.e.

```
<query string>
<parent string>

```

*Thanks to Dennis for saving 3 bytes in the overlapping scenario*

Try it online here
> 3 votes

# Answer
# Python 2, ~~124~~ 118 bytes

**Try it here**

This is an anonymous lambda function. It can probably still be golfed further.

```
import re,itertools as i
lambda p,q:sum(len(re.findall('(?='+''.join(i)+')',p))for i in set(i.permutations(q,len(q))))

```

Ungolfed:

```
from itertools import*
import re
def f(p,q):
    c=0
    for i in set(permutations(q,len(q))):
        c+=len(re.findall('(?='+''.join(i)+')',p))
    print c

```
> 2 votes

# Answer
# JavaScript ES6, 95 bytes

```
f=(p,q,n=0,s=a=>[...a].sort().join(''))=>[...p].map((_,i)=>n+=s(p.substr(i,q.length))==s(q))&&n

```

This is a function that takes two arguments like this: `f(parent,query)`.

It goes through all substrings of the parent string of the length of the query string and sorts them. If they are the same as the sorted query string, it increments `n`. Sorting string is annoying because it must be converted to an array, sorted, and converted back to a string. Ungolfed and testable code below.

```
var f = function(p, q) {
  var n = 0
  var s = function(a) {
    return a.split('').sort().join('')
  }

  p.split('').map(function(_, i) {
    n += s(p.substr(i, q.length)) == s(q)
  })
  return n
}

// testing code below
document.getElementById('go').onclick = function() {
  var parent = document.getElementById('parent').value,
    query = document.getElementById('query').value;
  document.getElementById('output').innerHTML = f(parent, query);
}
```

```
<label>Parent: <input id="parent" value="AdnBndAndBdaBn"/></label><br />
<label>Query:  <input id="query" value="dAn"/></label><br />
<button id="go">Go</button><br />
<samp id="output">—</samp> anagrams found
```
> 2 votes

# Answer
# Haskell, ~~77~~ 68 bytes

```
import Data.List
p#s=sum[1|x<-tails p,sort s==sort(take(length s)x)]

```

Usage:

```
*Main> "AdnBndAndBdaBn" # "dAn"
4
*Main> "AbrAcadAbRa" # "cAda"
2
*Main> "abacacaba"# "aac"
2

```

How it works: parent string is `p`, query string is `s`.

`tails` creates a list of it's parameter with successively removing the first element, e.g. `tails "abcd" -> ["abcd","bcd","cd","d",""]`. For every element `x` of this list take a `1` if the sorted first `n` elements (where `n` is the length of `s`) equal the sorted `s`. Sum the `1`s.

Edit: `tails` instead of explicit recursion
> 2 votes

# Answer
# Python 2, ~~76~~ 70 bytes

This lambda function iteratively compares each sorted substring with the target substring. The matches are counted and returned.

```
lambda a,d:sum(sorted(d[n:n+len(a)])==sorted(a)for n in range(len(d)))

```

The ungolfed code:

```
f = lambda substr, text: sum(
    sorted(text[n:n+len(substr)]) == sorted(substr)
    for n in range(len(text))
    )

def test(tests):
    for t in tests.split():
        substr, text  = t.split(',')
        print t, f(substr, text)

tests = '''ba,abcba dAn,AdnBndAndBdaBn aac,abacacaba'''
test(tests)

```

and the test output:

```
ba,abcba 2
dAn,AdnBndAndBdaBn 4
aac,abacacaba 2

```
> 2 votes

# Answer
# Python, 61 bytes

```
s=sorted
f=lambda a,b:a>''and(s(b)==s(a[:len(b)]))+f(a[1:],b)

```

This is a recursive algorithm. It checks whether the initial characters of the parent string, once sorted, are the same as the query string, sorted. Then, it recursive on the parent string with its first character removed. It terminates when the parent string is empty.
> 2 votes

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


# Question
Title: Scientist Seals Stranded upon an Iceberg
**Introduction**

A family of seals are stranded upon an iceberg in the Arctic Circle. There is a radio transmitter located on the iceberg which the seals can use to call for help. However, only the daddy seal knows how to operate the radio transmitter. And worse, the ice is very slippery this time of year, so the seals will slide uncontrollably until they hit another seal or slide off the edge of the iceberg, making it very difficult for the daddy seal to reach the radio transmitter. Luckily, one of the seals is a computer scientist, so she decides to write a program to figure out how to manoeuvre the daddy seal to the radio transmitter. As there is not much space on the ice to write a program, she decides to make the program use as little bytes as possible.

**Input Description**

The seal's program will take input in from STDIN, command line arguments, or user input functions (such as `raw_input()`). It cannot be preinitialised in a variable (e.g. "This program expects the input in a variable `x`").

The first line of the input consists of two comma separated integers in the form

```
A,B

```

Following that is `B` lines consisting of `A` characters each. Each line can only contain characters out of the following:

* `.`: The cold, cold, ocean. The map will always have this as a border.
* `#`: A part of the iceberg.
* `a`...`z`: A seal that is not the daddy seal on the iceberg.
* `D`: The daddy seal on the iceberg.
* `*`: The radio transmitter.

(Note that the daddy seal is always notated with an uppercase `D`. A lowercase `d` is simply a regular seal.)

**Output Description**

According to the following rules regarding how the seals can move, output a list of instructions for the seals on how they should move to get the daddy seal to the radio transmitter.

1. **Rule:** All seals can move up (`U`), down (`D`), left (`L`), and right (`R`). They cannot slide diagonally.
2. **Rule:** Upon moving, a seal will continue to move in the same direction until it collides with another seal or falls into the sea.
    1. If a seal collides with another seal, it will stop moving. The seal it collided with will **not** move.
    2. If a seal falls into the sea, it will drown and disappear from the map. That is, it does not act as a collider for other seals and it cannot be moved again.
3. **Rule:** Two seals cannot move at the same time, neither can a seal be moved while another one is still moving. The next seal can only be moved once the previous seal has stopped moving.
4. **Rule:** There is no restriction regarding moving a seal multiple times, or the number of seals that drown.
5. **Rule:** A correct solution will have the daddy seal *end* at the radio transmitter. The daddy seal cannot simply *pass* the transmitter while sliding.

The output will consist of several lines, each in the form

```
A,B

```

Where `A` is the seal to move (`D` for the daddy seal, `a`...`z` for others), and `B` is the direction to move the seal (either `U`, `D`, `L`, or `R`). Note that you **do not need to find the shortest route.** Any route that gets the daddy seal to the goal is an acceptable output.

**Example Inputs and Outputs**

Input:

```
25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................

```

Output:

```
D,R

```

Input:

```
9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........

```

Output (one possible output out of many):

```
m,R
b,L
D,U
D,R
D,D
D,L

```

Input:

```
26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................

```

Output (one possible output out of many):

```
v,D
D,L

```

If you have any other questions, please ask in the comments.

# Answer
# Python 3, 520 bytes

```
R=range
g=[list(input())for i in R(int(input().split(',')[1]))]
f=set(sum(g,[]))-set(".#*")
L=8
def P(p,g):
 if len(p)>L:return
 for s in f:
  c=sum(y.index(s)for y in g if s in y)
  if c<1:continue
  r,=[n for n in R(len(g))if s in g[n]]
  for d in R(4):
   m=p+s+",%s\n"%"LURD"[d];G=[y[:]for y in g];o="#";i,j=I,J=r,c
   while"#"==o:G[i][j]="#";G[I][J]=s;i,j=I,J;I,J=i+d%2*(d-2),j+(~d%-2&d-1);o=G[I][J]
   if"."==o:G[i][j]="#"
   if"D"==s:
    if"."==o:continue
    if"*"==o:print(m);1/0
   P(m,G)
while 1:P("",g);L+=4

```

I may do a more detailed explanation later if people want, but basically this runs a depth-first search with iterative deepening on the state space of possible moves. If a move causes the daddy seal to fall off, it is immediately rejected. If the daddy ends up next to the transmitter, the sequence of moves is printed, and the program divides by zero to force an exit.

I can make the code run significantly faster by adding `if G!=g:` at the beginning of the second-last line, for 8 extra bytes--this rejects moves that don't change anything, such as `k,L` in the first test case.

The runtime varies noticeably from one run to the next, even with the same input--evidently a result of the fact that I pick the next seal to move by iterating over a `set`, which is an unordered type. I timed the second test case at 5 minutes 30 seconds, though it didn't seem that long the first time I ran it. With the optimization mentioned above, it's more like 40 seconds.
> 6 votes

# Answer
# JavaScript (ES6) 322 ~~334 323~~

**Edit2** Added animation in the snippet

**Edit** Bug fix, remember initial posiiton of '\*', so I find it even when a seal slide over it and erase it.

Implemented as a function with the input string as parameter (probably invalid but waiting for a clarification). Output via popup.
The problem with multiline string input in JavaScript is that `prompt` does not manage it well.

As for the algorithm: a BFS, should find an optimal solution. I keep a queue of game status in variable `l`, the status beeing the character grid `g` and the sequence of moves so far `s`. Besides, there is a set of grids obtained so far in variable `k`, to avoid exploring the same grid again and again.

The main loop is

* dequeue a game status
* try all possibile moves, enqueue the status after each valid move (IIF the resulting grid is not already present)
* if solution found then exit the loop

```
F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,'']],k=[];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  alert(t)
}

```

Run Snippet to test in FireFox

```
F=s=>{
  o=~s.match(/\d+/),g=[...z=s.replace(/.*/,'')];
  for(l=[[g,k=[]]];[g,s]=l.shift(),!g.some((c,p)=>
      c>'A'&&[-1,1,o,-o].some((d,j)=>{
        t=s+' '+[c,'LRUD'[j]];
        for(q=p;(u=g[q+d])<'.';)q+=d;
        return(c<'a'&z[q]=='*')||
        c>'D'|u>'.'&&!(
          f=[...g],u=='.'?0:f[q]=c,f[p]='#',
          k[h=f.map(v=>v>'D'?0:v)]||(k[h]=l.push([f,t]))
        )
      })
    ););
  return t
}

$('.T td').each(function(i,td) { $('.R td').eq(i).text(F($(td).text())) });

$(".R").on('click','td',function(){
  var i = $(this).index();
  var $td = $('.T td').eq(i);
  var t = $td.text().trim();
  animate($td, $td.text().trim(), $('.R td').eq(i).text().trim());
});

$('#GO').on('click',function() {
  var s = T0.value, h=F(s)
  console.log(s)
  $('#R0').text(h);
  animate($('#A'), s,h);
});

function animate($out, s, h){
  o=~s.match(/\d+/),g=[...s.replace(/.*/,'')];

  fr=[g.join('')];
  h.replace(/.,(.)/g, (c,d)=>{
    i = g.indexOf(c=c[0]);
    d = [-1,1,o,-o]['LRUD'.search(d)]
    for(;g[i+d]<'.';i+=d)
    {
      g[i]='#',z=[...g],g[i+d]=c,z[i+d]='<b>'+c+'</b>', fr.push(z.join(''))
    }
    if(g[i+d]=='.')
    {
      g[i]='#', fr.push(g.join(''))
    }
  })

  var fa = ()=>{
    var f=fr.shift();
    f ? $out.html(f) : (
      clearInterval(i),
      $out.text(s),
      $out.toggleClass('Anim')
  )};
  $out.toggleClass('Anim');
  fa();
  var i=setInterval(fa, 500);
}
```

```
td { vertical-align: top; font-family: monospace; white-space: pre; }
textarea { width: 99%;  height:10em;}
pre { margin: 0; }
.R td { background: #fdc; padding: 6px 0; }
.R td:hover { background: #ffc }
.T td { background: #ddf}
B { color: red }
.T td.Anim, td.Anim { background: #ffc; }
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<table cellspacing=5>
  <tr>
    <th colspan=4>Predefined tests</th>
  </tr>
  <tr class=T>
    <td>25,5
.........................
.#######################.
.####D#############*k###.
.#######################.
.........................</td>
    <td>9,7
.........
.a#####b.
.#####d#.
.##l*###.
.###m#p#.
.#D#.#c#.
.........</td>
<td>26,5
..........................
.###..................###.
.l*##########v#########D#.
.###..................###.
..........................</td>
<td>8,5
........
.##c###.
.a#*#D#.
.##b###.
........</td>
    </tr>
  <tr><td colspan=4>Click on solution text to start animation</td>
  </tr>
  <tr class=R>
    <td></td><td></td><td></td><td></td>
  </tr>
  <tr><th colspan=2>Your test  </th></tr>
  <tr><td colspan=2><textarea id=T0></textarea></td>
    <td colspan=2 id=A></td>
  </tr>
  <tr>
    <td colspan=2>Find solution and animate <button id=GO>go</button></td>
    <td colspan=2 id=R0></td>
  </tr>
</table>
```
> 4 votes

# Answer
## C++, 628 bytes

Well, this didn't turn out very short:

```
#include <set>
#include <iostream>
using namespace std;struct R{string b,m;bool operator<(R r)const{return b<r.b;}};int w,h,t,j,k,z=1;char c,f;set<R> p,q;int m(R r,int x,int d,char a){for(j=x,c=r.b[x];(f=r.b[j+=d])==35;);if(c-68||f-46){r.b[x]=35;if(f-46)r.b[j-d]=c;r.m+=c;r.m+=44;r.m+=a;r.m+=10;if(c==68&j-d==t){cout<<r.m;z=0;}if(p.count(r)+q.count(r)==0){q.insert(r);}}}int main(){cin>>w>>c>>h>>c;R r;string l;for(;k++<h;){getline(cin,l);r.b+=l;}t=r.b.find(42);r.b[t]=35;q.insert(r);for(;z;){r=*q.begin();q.erase(q.begin());p.insert(r);for(k=0;z&&k<w*h;++k){if(r.b[k]>64){m(r,k,-1,76);m(r,k,1,82);m(r,k,-w,85);m(r,k,w,68);}}}}

```

I chose C++ because I wanted to use the data structures (`set`, `string`), but it's inherently quite verbose. The solution does reasonably well on performance, solving test 2 in a little over 2 seconds on a MacBook Pro, even though it's not optimized for runtime.

Code before starting to eliminate whitespace and some other length reduction:

```
#include <set>
#include <iostream>

using namespace std;

struct R {
    string b, m;
    bool operator<(R r) const {return b < r.b; }
};

int w, h, t;
set<R> p, q;
bool z = true;

void m(R r, int k, int d, char a) {
    int j = k;
    char s = r.b[k], f;
    for (; (f = r.b[j += d]) == 35;);
    if (s - 68 || f - 46) {
        r.b[k] = 35;
        if (f - 46) {
            r.b[j - d] = s;
        }
        r.m += s;
        r.m += 44;
        r.m += a;
        r.m += 10;
        if (s == 68 && j - d == t) {
            cout << r.m;
            z = false;
        }
        if (p.count(r) + q.count(r) == 0) {
            q.insert(r);
        }
    }
}

int main() {
    char c;
    cin >> w >> c >> h >> c;
    string b, l;
    int k;
    for (k = 0; k < h; ++k) {
        getline(cin, l);
        b += l;
    }

    t = b.find(42);
    b[t] = 35;

    R r;
    r.b = b;
    q.insert(r);

    for ( ; z; ) {
        r = *q.begin();
        q.erase(q.begin());
        p.insert(r);

        for (k = 0; z && k < w * h; ++k) {
            c = r.b[k];
            if (c > 64) {
                m(r, k, -1, 76);
                m(r, k, 1, 82);
                m(r, k, -w, 85);
                m(r, k, w, 68);
            }
        }
    }

    return 0;
}

```

The core idea behind the algorithm is that two sets are maintained:

* `q` is the set of configurations that are pending processing.
* `p` is the set of configurations that have been processed.

The algorithm starts with the initial configuration in `q`. In every step, a configuration is popped from `q`, added to `p`, all possible seal movements are generated, and the resulting new configurations inserted into `q`.

Test run:

```
bash-3.2$ ./a.out <test1
D,R
bash-3.2$ time ./a.out <test2
p,U
c,U
p,R
c,L
m,L
b,L
a,L
D,U
b,L
D,R
D,D
D,L

real    0m2.267s
user    0m2.262s
sys 0m0.003s
bash-3.2$ ./a.out <test3
v,U
D,L
bash-3.2$

```
> 1 votes

---
Tags: code-golf
---


# Question
Title: Determine whether rational coordinates are in the right Sierpinski triangle
The Sierpinski triangle is a set of points on the plane which is constructed by starting with a single triangle and repeatedly splitting all triangles into four congruent triangles and removing the centre triangle. The right Sierpinski triangle has corners at `(0,0)`, `(0,1)` and `(1,0)`, and looks like this:

Some equivalent definitions of this set are as follows:

* Points in the `n`th iteration of the process described above, for all `n`.
* Points `(x,y)` with `0 <= x <= 1` and `0 <= y <= 1` such that for all positive integers `n`, the `n`th bit in the binary expansion of x and y are not both `1`.
* Let `T = {(0,0),(1,0),(0,1)}`

Let `f` be a function on sets of 2D points defined by the following:

`f(X) = {(0,0)} ∪ {(x+t)/2 | x∈X, t∈T}`

Then the right Sierpinski triangle is the topological closure of the least fixed point (by set containment) of `f`.

* Let `S` be the square `{(x,y) | 0<=x<=1 and 0<=y<=1}`

Let `g(X) = S ∩ {(x+t)/2 | x∈(X), t∈T}` (where `T` is as defined above)

Then the right Sierpinski triangle is the greatest fixed point of `g`.

# Challenge

Write a program or function which accepts 4 integers, `a,b,c,d` and gives a truthy value if `(a/b,c/d)` belongs to the right Sierpinski triangle, and otherwise gives a falsey value.

# Scoring

This is a code golf. Shortest code in bytes wins.

# Test cases

The following are in the right Sierpinski triangle:

```
0 1 0 1
0 1 12345 123456
27 100 73 100
1 7 2 7
8 9 2 21
8 15 20 63
-1 -7 2 7

```

The following are not in the right Sierpinski triangle:

```
1 1 1 1
-1 100 1 3
1 3 1 3
1 23 1 7
4 63 3 66
58 217 4351 7577
-1 -7 3 7

```

# Answer
# Python 2, 68

```
lambda n,d,N,D:1>=n/d>=0<=N/D<=1and(n<<abs(D*d))/d&(N<<abs(D*d))/D<1

```

A nice way to check for gasket membership made ugly. If we were guaranteed that the inputs are non-negative and in the unit square, we would have 38:

```
lambda n,d,N,D:(n<<D*d)/d&(N<<D*d)/D<1

```

The idea is that we check whether a point lies within the gasket by checking whether their binary fraction expansions bitwise-AND to 0. To get the first `k` character of the expansion, we bit-shift the numerator `k` bits left before integer-dividing by the denominator. We need to make `k` sufficiently large to catch a repeat. We note that the binary expansion `n/d` has period at most `d`, so the joint expansions have period at most `d*D`, so `k=d*D` suffices.

The rest is to check whether the fraction is in the box and insulate against inputs given like `-1/-3`.
> 5 votes

---
Tags: code-golf, fractal, rational-numbers
---