title: Self-shortening Prime Tester

text:
# Question
Title: Self-shortening Prime Tester
Let's get right in to it. Your challenge is to make a program that does these things depending on its input:

1. If the input is a number, output "Prime" if the number is a prime number and "Not prime" if the number isn't a prime number. You can assume the number is \> 1.
2. If the input is two numbers, output every single prime number between the first number (inclusive) and the second number (exclusive). You can assume the first number is smaller than the second.
3. Here comes the real challenge: if there's no input, the program should output a shorter version of itself that does exactly the same things as the original program. The program is not allowed to read from any file or from the web. The new program should also be able to do this. It should work for at least 5 generations. **The new program doesn't have to be in the same language as the first.**

# Scoring:

Your score is equal to the sum of the number of bytes in the first five generations of your submission (the submission itself being generation one). If the new code is hard-coded in to the first program, multiply the score by 1.5. **Lowest score wins.** (If you find some kind of flaw in the scoring system, please let me know in the comments)

# Answer
> 10 votes
# CJam, 66 + 65 + 64 + 63 + 62 = 320 ~~325~~ ~~355~~ bytes

The following 5 lines are the first 5 generations:

```
{     `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{    `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{   `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{  `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~
{ `(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~

```

The last one produces

```
{`(\1>+q~](\_,["_~"a{~mp'P"Not p"?"rime"@;}{~,>{mp},p;}]=~}_~

```

which still performs the prime tasks correctly.

Test it here.

## Explanation

The basic CJam quine is

```
{"_~"}_~

```

which can be extended very easily to a generalised quine. For an explanation of this see my answer here.

The basic ideas for this answer are:

* Start the quine with a bunch of spaces and remove one of these when quining.
* Get an array with all input numbers (0, 1 or 2) and choose some code to run depending on the length (by using it to index into an array).

Here is a breakdown of the code inside the quine:

```
"Remove a space from the block's string representation:";
`(\1>+
`      "Get the string representation of the block.";
 (\    "Slice off the leading '{' and pull the remaining string back up.";
   1>  "Remove the first character, i.e. a space.";
     + "Prepend the '{' to the string again.";

"Get the array of inputs and choose the code:";
q~](\_,[...]=~
q~             "Read and eval the input.";
  ]            "Wrap everything (including the string for the block) in an array.";
   (\          "Shift off the string and swap it with the rest of the array.";
     _,        "Duplicate the input array and get its length.";
       [...]=  "Use it to index into this array.";
             ~ "If there are no inputs there will now be an array on the top of the
                stack, which ~ will unwrap. Otherwise there will be a block which ~
                will evaluate.";

"If there is no input, push the string needed for the quine and put it in
 an array for ~ to unwrap:";
"_~"a

"If there is one input, test for primality:";
~mp'P"Not p"?"rime"@;
~mp                   "Unwrap the input array and test for primality.";
   'P"Not p"?         "Choose either 'P' or 'Not p' depending on the result.";
             "rime"   "Push the common part of the string.";
                   @; "Pull up the quine string and discard it.";

"If there are two inputs, print an array with all the primes in the range:";
~,>{mp},p;
~          "Unwrap the array leaving N and M on the stack.";
 ,         "Get a range [0 1 .. N-1].";
  >        "Drop the first M elements, giving [M M+1 .. N-1].";
   {mp},   "Filter to keep only the primes.";
        p  "Pretty-print the array.";
         ; "Discard the quine string.";

```

# Answer
> 6 votes
# C, Score: 553 + 552 + 551 + 550 + 549 = 2755,

# Original Length: 553, Avg: 551

# EDIT: Only 5 generations, not 6!

Looks like Martin beat me both in time and in score (by nearly an order of magnitude!). Ah, well.

The original program is as follows:

```
char*c="char*c=%c%s%c;k=%d,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%cv);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?%cPrime%c:%cNot prime%c);if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf(%c%cd %c,a);}";k=10000,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%v);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?"Prime":"Not prime");if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf("%d ",a);}

```

I'll unravel it a little bit for better understanding, but for it to work properly the new lines are NOT part of the program.

```
char*c="char*c=%c%s%c;k=%d,a;p(c,v,d){for(v=2;v<c;v++)d+=!(c%cv);return!d;}int main(int C,char**V){if(C==1){printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);return 0;}a=atoi(V[1]);if(C==2)printf(p(a,0,0)?%cPrime%c:%cNot prime%c);if(C==3)for(;a<atoi(V[2]);a++)if(p(a,0,0))printf(%c%cd %c,a);}";
k=10000,a;
p(c,v,d){
    for(v=2;v<c;v++)
        d+=!(c%v);
    return!d;
}
int main(int C,char**V){
    if(C==1){
        printf(c,34,c,34,k/10,37,34,34,34,34,34,37,34);
        return 0;
    }
    a=atoi(V[1]);
    if(C==2)
        printf(p(a,0,0)?"Prime":"Not prime");
    if(C==3)
        for(;a<atoi(V[2]);a++)
            if(p(a,0,0))
                printf("%d ",a);
}

```

The only thing that changes from program to program is the value of `k`, which loses exactly one digit every iteration. Interestingly, after the 5th generation, k becomes zero and stays there, so you can iterate ad infinitum and always have valid output.

# Answer
> 2 votes
# Tcl 253 + 252 + 251 + 250 + 249 = 1255 bytes

```
eval [set x {     proc q a\ b {incr b;expr $a%$b?\[q $a $b]:$a==$b}
proc 1 a {if [q $a 1] puts\ Prime {puts Not\ Prime}}
proc 2 a\ b {while $b-\$a {if [q $a 1] puts\ $a;incr a}}
proc 0 {} {puts "eval \[set x {[string ra $::x 1 end]}]"}
$argc {*}$argv}]

```

The code needs to end with a newline. Explanation:

```
eval [set x {...}]

```

Write the code into x, then execute it.

```
$argc {*}$argv

```

Execute the command which name is the argument length, passing the arguments along.

```
proc q a\ b {incr b;expr $a%$b?\[q $a $b]:$a==$b}

```

Returns 1 when a is prime, 0 else. Uses recursion; the second backslash prevents command substitution from the interpreter and enables the one from `expr` (which is lazy).

```
proc 1 a {if [q $a 1] puts\ Prime {puts Not\ Prime}}
proc 2 a\ b {while $b-\$a {if [q $a 1] puts\ $a;incr a}}

```

Straightforward implementation of the requirements.

```
proc 0 {} {puts "eval \[set x {[string ra $::x 1 end]}]"}

```

This is the quine, stripping a space from the beginning each time.

---
Tags: code-challenge, quine, primes, code-generation
---


title: Decrypting a block of AES

text:
# Question
Title: Decrypting a block of AES
Today your goal is to decrypt a secret message using AES. Given a ciphertext and key you will decrypt and print the message.

---

1. Your program may be in any language. It will be run with input on stdin, and its output on stdout will be checked for correctness.
2. The first line of input on stdin will be the 16 byte key, encoded in hexadecimal. The second line of input on stdin will be the 16 byte ciphertext, encoded in hexadecimal.
3. The output of the program must be the 16 byte message after decrypting the ciphertext using AES-128 with the given key. You must output the result interpreted as ASCII octets. You may assume that any result is valid ASCII after decrypting.
4. You may not use any library/built-in features that implement AES. You may use such features to convert between hex/binary/ASCII encodings.

Shortest code in bytes wins.

Example input and output:

```
bd8ab53f10b3d38576a1b9a15cf03834
02c0ee126cae50ba938a8b16f0e04d23

```

> Attack tomorrow.

And another:

```
f4af804ad097ba832906db0deb7569e3
38794338dafcb09d6b32b04357f64d4d

```

> Congratulations.

# Answer
## Python, 661 chars

```
R=range
I=lambda x:[int(x[2*i:2*i+2],16)for i in R(16)]
k=I(raw_input())
c=I(raw_input())
P=[]
x=1
for i in R(512):P+=[x];x^=x*2^(x>>7)*0x11b
S=[255&(99^j^(j>>4)^(j>>5)^(j>>6)^(j>>7))for i in R(256)for j in[(P[255-P.index(i)]if i else 0)*257]]
for r in R(10):
 for i in R(4):k+=[k[-16]^S[k[-3-(i>2)*4]]]
 k[-4]^=[1,2,4,8,16,32,64,128,27,54][r]
 for i in R(12):k+=[k[-16]^k[-4]]
for r in R(11):
 c=[x^y for x,y in zip(k[160-16*r:],c)]
 if r>9:break
 for i in[0,4,8,12]*(r>0):c[i:i+4]=[x^y^z^w for j in R(4)for x,y,z,w in[[P[a+P.index(v)]if v else 0 for a,v in zip((2*[104,238,199,223])[3-j:],c[i:i+4])]]]
 c=(c*13)[::13];c=map(S.index,c)
print''.join(map(chr,c))

```

`k` is the key, `c` is the ciphertext. I build P, the powers of 3 in the field, then `S`, the sbox. Then `k` is extended with the key schedule. Finally we do the AES decryption. Mixcolumns is the hard phase, all the other phases are pretty straightforward.
> 4 votes

---
Tags: code-golf, cryptography
---


title: Generate the galaxies of elite

text:
# Question
Title: Generate the galaxies of elite
**Introduction**

Elite was the first space trading video game, written and developed by David Braben and Ian Bell and published by Acornsoft for the BBC Micro and Acorn Electron computers in in September of 1984.

The Elite universe contains eight galaxies, each with 256 planets to explore. Due to the limited capabilities of 8-bit computers at the time, these worlds were procedurally generated. A single seed number is run through a fixed algorithm the appropriate number of times and creates a sequence of numbers determining each planet's complete composition (position in the galaxy, prices of commodities, and name and local details; text strings are chosen numerically from a lookup table and assembled to produce unique descriptions, such as a planet with "carnivorous arts graduates"). This means that no extra memory is needed to store the characteristics of each planet, yet each is unique and has fixed properties. Read more about this here: Elite random number generator

**Challenge**

Like the Elite game did, write a script which can procedurally generate a list of 8 galaxies each of which contains 256 planets. (You need to generate a total of 2048 planet names).

The 8 galaxy names can be defined before hand or procedurally generated. This is your choice.

**Output**

* Please post your script here and perhaps use paste bin or an equivalent to host your output.

**Rules**

* At a minimum your script must generate 2048 planet names and 8 galaxy names.
* Each 256 planets should be nested within the array of a galaxy.
* This is a popularity-contest! Try to make your code clever, interesting, slick or retro.
* This is not code-golf. As such, readable code is appreciated. Still, try to keep size low remember the original programmers only had 32Kb or memory to work within for the whole game.
* Repeats of planet names of more than 3 in a row is not allowed and a single planet name must not appear more than 5 times in the total 2048 planets.
* Input is optional and not required.
* Standard Loopholes apply.

**How to get kudos**

* If your script also generates economy, government, tech level, population, gross productivity, average radius and comments about each planet.
* If your planet names look organic (doesn't have to be in English) but for example 'Lave' looks better and is easier to read than 'Esdqzfjp'.
* If your planet names don't contain profanity such "Arse". I only mention this because the original programmers had to do this.
* If you do this challenge in BBC Basic.

# Answer
# Java

I just though I would start out this contest with something :). The names are organic and are generated on the fly. Run with any arguments to use interactive mode.

```
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;

public class Main {

    private final static int[][] frequencies = new int[][]{   //Generated with names from http://www.minorplanetcenter.net/iau/lists/MPNames.html
            {96, 323, 512, 445, 222, 113, 407, 249, 514, 134, 740, 1287, 975, 3188, 212, 235, 13, 2131, 997, 909, 501, 398, 226, 50, 355, 165, 3223},
            {626, 61, 8, 8, 877, 3, 3, 28, 322, 5, 7, 114, 9, 8, 425, 4, 0, 396, 44, 6, 260, 0, 7, 0, 51, 3, 40},
            {607, 4, 129, 16, 287, 9, 14, 1728, 248, 4, 364, 139, 9, 8, 518, 7, 18, 99, 27, 41, 94, 2, 0, 0, 49, 42, 102},
            {842, 49, 13, 46, 784, 17, 38, 45, 425, 18, 21, 65, 56, 31, 503, 10, 2, 224, 90, 70, 169, 13, 50, 0, 86, 37, 421},
            {326, 203, 264, 375, 284, 128, 231, 143, 513, 67, 261, 1436, 399, 1874, 159, 179, 9, 2873, 940, 680, 206, 402, 180, 64, 317, 125, 1527},
            {161, 7, 3, 1, 246, 170, 6, 6, 128, 5, 2, 61, 16, 5, 122, 3, 0, 253, 16, 28, 105, 3, 3, 0, 4, 0, 122},
            {596, 16, 27, 27, 595, 8, 62, 150, 250, 17, 16, 134, 32, 100, 319, 11, 6, 272, 53, 28, 258, 3, 18, 10, 46, 18, 507},
            {1360, 24, 33, 16, 1001, 2, 9, 14, 1219, 9, 55, 123, 93, 204, 683, 8, 0, 178, 55, 88, 383, 21, 50, 0, 96, 0, 453},
            {1104, 148, 802, 362, 646, 85, 333, 97, 47, 160, 477, 789, 486, 2022, 309, 149, 15, 501, 1007, 614, 137, 142, 65, 43, 146, 147, 1598},
            {309, 5, 6, 13, 183, 1, 2, 2, 224, 1, 15, 2, 4, 11, 354, 1, 0, 3, 15, 6, 132, 2, 0, 0, 8, 2, 103},
            {1094, 15, 10, 9, 614, 6, 7, 166, 718, 9, 39, 133, 32, 36, 737, 9, 0, 137, 92, 20, 343, 17, 25, 1, 153, 2, 494},
            {1219, 105, 66, 280, 1319, 87, 73, 55, 1259, 17, 77, 1034, 142, 35, 622, 80, 4, 38, 209, 146, 271, 67, 21, 0, 224, 33, 612},
            {1790, 139, 135, 14, 591, 6, 6, 21, 859, 9, 16, 16, 120, 23, 599, 121, 5, 24, 87, 11, 252, 3, 12, 0, 78, 7, 249},
            {1139, 159, 291, 744, 1103, 55, 881, 124, 1014, 72, 298, 80, 108, 519, 735, 52, 12, 110, 543, 495, 140, 27, 59, 10, 203, 120, 2308},
            {72, 299, 215, 258, 167, 138, 150, 288, 124, 62, 282, 824, 456, 1643, 200, 199, 5, 1054, 815, 457, 408, 698, 201, 26, 145, 96, 1181},
            {517, 9, 5, 2, 474, 17, 3, 204, 263, 0, 16, 95, 10, 6, 311, 131, 0, 147, 45, 34, 87, 0, 1, 0, 24, 2, 66},
            {1, 0, 0, 0, 1, 0, 0, 0, 30, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 116, 2, 1, 0, 0, 0, 5},
            {1518, 162, 175, 366, 1113, 44, 325, 86, 1469, 18, 204, 176, 211, 294, 1196, 58, 11, 294, 331, 505, 439, 57, 37, 4, 311, 44, 1349},
            {904, 66, 452, 26, 770, 22, 17, 935, 522, 13, 439, 132, 109, 56, 570, 131, 10, 28, 442, 932, 437, 46, 44, 0, 68, 50, 1616},
            {1009, 24, 60, 13, 1026, 20, 21, 607, 618, 29, 47, 74, 52, 35, 862, 12, 0, 399, 365, 481, 180, 18, 30, 1, 90, 125, 657},
            {164, 191, 273, 207, 233, 51, 186, 75, 170, 55, 238, 344, 292, 555, 55, 72, 5, 694, 672, 274, 13, 35, 23, 32, 76, 82, 421},
            {535, 3, 4, 4, 441, 0, 10, 3, 577, 1, 16, 28, 1, 12, 153, 4, 0, 26, 91, 4, 12, 1, 0, 0, 30, 1, 475},
            {516, 5, 2, 5, 289, 4, 2, 43, 290, 0, 17, 32, 11, 26, 109, 2, 0, 25, 57, 1, 33, 0, 1, 0, 13, 0, 49},
            {35, 2, 7, 2, 25, 2, 2, 3, 63, 1, 3, 5, 0, 0, 9, 1, 0, 4, 3, 5, 26, 1, 3, 0, 0, 0, 82},
            {557, 38, 55, 46, 138, 22, 26, 31, 72, 18, 44, 126, 75, 143, 238, 31, 1, 81, 108, 57, 214, 9, 27, 9, 6, 8, 706},
            {241, 12, 4, 22, 196, 0, 8, 146, 142, 0, 17, 11, 16, 15, 87, 2, 1, 11, 23, 11, 122, 10, 13, 0, 19, 49, 206},
            {1282, 1246, 1014, 818, 540, 466, 757, 928, 351, 680, 1207, 835, 1479, 552, 375, 957, 40, 795, 1710, 952, 150, 455, 435, 34, 288, 226, 0}
    };

    private final static int MIN_NAME_LENGTH = 4;

    private final static String INFO = "Type \"galaxy x\" to change galaxy. Type a number to get the name of that planet. Type \"exit\" or any invalid input to exit.";

    private final static Scanner in = new Scanner(System.in);
    private final static PrintStream out = System.out;

    public static void main(String[] args) throws Exception {

        if (args.length == 0){

            long seed = hash(System.nanoTime());

            for (int i = 0; i < 8; i++){

                long galaxySeed = (hash(i) ^ seed) + 1;
                out.println("Galaxy " + generateName(new Random(galaxySeed)));

                for (int j = 0; j < 256; j++){

                    long planetSeed = (hash(j) ^ galaxySeed) + 1;
                    out.println(generateName(new Random(planetSeed)));

                }
            }
            return;
        }

        out.println(INFO);

        out.println("Seed?");
        long seed = hash(in.nextLong());

        out.println("Galaxy?");
        long galaxySeed = hash(in.nextInt()) ^ seed;
        in.nextLine();//Get rid of rest of line.

        String galaxyName = generateName(new Random(galaxySeed));
        out.println("The name of your galaxy is " + galaxyName + ".");

        while (true){

            String input = in.nextLine().trim().toLowerCase();

            try {
                if (input.startsWith("galaxy")) {

                    int galaxy = Integer.parseInt(input.substring(6).trim());
                    galaxySeed = (hash(galaxy) ^ seed) + 1;

                    galaxyName = generateName(new Random(galaxySeed));
                    out.println("The name of your galaxy is " + galaxyName + ".");

                } else if (input.startsWith("exit")){
                    return;
                } else {

                    int planet = Integer.parseInt(input);
                    long planetSeed = (hash(planet) ^ galaxySeed) + 1;

                    String planetName = generateName(new Random(planetSeed));
                    out.println("The name of your planet is " + planetName + ".");

                }
            } catch (Exception e){
                return;
            }
        }

    }

    private static String generateName(Random rand) {

        int previousChar = randomIndex(frequencies[26], rand);
        String name = "" + (char)(previousChar + 'A');

        for (;;){

            int[] frequency = frequencies[previousChar].clone();

            frequency[26] *= Math.max(name.length() - (MIN_NAME_LENGTH - 1), 0) ; //Hack, reduces name lengths.

            int nextChar = randomIndex(frequency, rand);

            if (nextChar == 26){
                return name;
            }

            previousChar = nextChar;

            name += (char) (nextChar + 'a');
        }
    }

    private static int randomIndex(int[] frequencies, Random rand) {

        int total = Arrays.stream(frequencies).sum();

        int n = rand.nextInt(total);
        int i = 0;

        for (int frequency : frequencies){
            n -= frequency;
            if (n < 0){
                return i;
            }
            i++;
        }

        throw new IllegalStateException();
    }

    private static long hash(long i) {
        return (int) ((131111L*i)^i^(1973*i)%7919); //http://stackoverflow.com/a/9640543/4230423
    }
}

```

It uses the same code to generate galaxy names as planet names. Here are some example names:

```
Kanipeso
Danlerg
Deigaji
Kanialu
Fulla
Tirr
Smanger
Anikuraba
Dotia

```

For full output of 8 galaxies look here.
> 5 votes

---
Tags: popularity-contest
---


# Question
Title: Determine sets of associatively equivalent permutations of commutative operations
There are many types of binary operations, which can be categorized by their associative properties and their commutative properties.

* A binary operation `()` is *associative* if the order of operations between operands does not affect the result — i.e. if `(a(bc)) = ((ab)c)`.
* A binary operation `()` is *commutative* if the order of two operands within one operation does not affect the result — i.e. if `(ab) = (ba)`.

There are operations like addition and multiplication that are both associative and commutative, and operations like subtraction and division that are neither associative nor commutative.

There are also operations — such as the group composition operator — that are associative but not commutative.

But then there are operations that are commutative but not associative. These are more rare and not analyzed as much mathematically, but they occur. For example, rounded multiplication is such an operation. If you round a calculation to the nearest tenth after every multiplication, you can get anomalies like `(6.8 × 5.7) × 2.9 = 112.5` while `6.8 × (5.7 × 2.9) = 112.2`.

---

Let a permutation of the operands `P` in an operation tree (such as `((x(xx))((x(xx))x))`) be *associatively equivalent* to another permutation `Q`, if the operands in `P` can be rearranged by the commutative property to form an operation tree identical to the original.

For example, permutations `(a(b(c(de))))` and `(a(b(c(ed))))` of the operation tree `(x(x(x(xx))))` are equivalent, because `d` commutes with `e`. However, `(a(b(c(de))))` and `(a(b(d(ce))))` are not equivalent, because `(c(de))` is not equal to `(d(ce))`.

A more complex example might be `(((ab)c)(d(ef)))` and `(((ef)d)(c(ba)))`. Step-by-step, the two of these can be shown to be equivalent as follows:

```
(((ab)c)(d(ef))) = (((ba)c)(d(ef)))     since    a    commutes with    b
(((ba)c)(d(ef))) = (((ba)c)((ef)d))     since  (ef)   commutes with    d
(((ba)c)((ef)d)) = ((c(ba))((ef)d))     since  (ba)   commutes with    c
((c(ba))((ef)d)) = (((ef)d)(c(ba)))     since (c(ba)) commutes with ((ef)d)

```

Permutations of different operation trees are not comparable. `(a(b(c(de))))` and `((((ab)c)d)e)` are neither associatively equivalent nor associatively distinct, because their operation trees are different.

---

Your task is to build a program that will find all the associatively equivalent permutations of the operands of a given operation tree.

Your program will take input in the form given above, with brackets enclosing juxtaposed operators. The operands will always be lowercase letters, in alphabetical order starting from `a`, and will contain a maximum of 26 letters.

Your program will output a series of permutations of the letters, without the brackets, representing all of the permutations that are associatively equivalent with the original permutation.

For example, if you are given an input of:

```
((ab)(cd))

```

Then your program will output:

```
abcd
abdc
bacd
badc
cdab
cdba
dcab
dcba

```

Your program must be accompanied by a description of its algorithm, and a proof of its asymptotic runtime with respect to the number of operands in the operation tree. The program with the lowest asymptotic runtime in this manner wins.

# Answer
> 2 votes
Every parenthesis has in it two elements, either a terminal symbol, or another parenthesis. These two elements have two possible permutations, `ab` and `ba`.

This means that the expression forms a binary tree, and every node inside the tree has two possible permutations. So the total output is always *2n* where n is the number of parenthesis pairs. This means that an asymptotical algorithm will always do this amount of work.

For this optimal algorithm we will parse the expression, then recursively generate possibilities, 2 for each parenthesis pair. As seen in the paragraph above, this is optimal.

```
def parse(inp):
    c = inp.pop(0)
    while c == ")": c = inp.pop(0)

    if c == "(":
        return [parse(inp), parse(inp)]

    return c

def possibs(tree):
    if len(tree) == 2:
        for left_possib in possibs(tree[0]):
            for right_possib in possibs(tree[1]):
                yield left_possib + right_possib
                yield right_possib + left_possib
    else:
        yield tree

tree = parse(list("((ab)(cd))"))

for possib in possibs(tree):
    print(possib)

```

---
Tags: fastest-algorithm
---


title: Word search puzzle generation

text:
# Question
Title: Word search puzzle generation
Given a list of strings, find the **smallest square** matrix that contains each of the initial strings. The strings may appear horizontally, vertically or diagonally and forwards or backwards like in this question Word Search Puzzle.

Words should be placed in the square, with at least one word in each direction (horizontal, vertical and diagonal). Words should appear just one time.

So, the input is just a list of words. For example: `CAT, TRAIN, CUBE, BICYCLE`. One possible solution is:

```
B N * * * * *
* I * * C A T
* A C * * * *
* R * Y * * C
* T * * C * U
* * * * * L B
* * * * * * E

```

I replaced filling letters with asterisks just for clarity. The desired output should include random filling letters.

# Answer
# JavaScript (ES6), 595 ~~628 680~~

**Edit** Some cleanup and merge:
\- function P merged inside function R
\- calc x and z in the same .map
\- when solution found, set x to 0 to exit outer loop
\- merged definiton and call of W

**Edit2** more golfing, random fill shortened, outer loop revised ... see history for something more readable

~~Unlike the accepted answer,~~ this should work for most inputs. Just avoid single letter words. If an output is found, it's optimal and using all 3 directions.

The constraint of avoiding repeating words is very hard. I had to look for repeating word at each step adding word to the grid, and at each random fill character.

Main subfunctions:

* P(w) true if palindrome word. A palindrom word will be found twice when checking for repeated words.
* R(s) check repeating words on grid s
* Q(s) fill the grid s with random characters - it's recursive and backtrack in case of repeating word - and can fail.
* W() recursive, try to fill a grid of given size, if possibile.

The main function use W() to find an output grid, trying from a size of the longest word in input up to the sum of the length of all words.

```
F=l=>{
  for(z=Math.max(...l.map(w=>(w=w.length,x+=w,w),x=0));
      ++z<=x;
      (W=(k,s,m,w=l[k])=>w?s.some((a,p)=>!!a&&
            D.some((d,j,_,r=[...s],q=p-d)=>
              [...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
              &&R(r)&&W(k+1,r,m|1<<(j/2))
            )
          )
        :m>12&&Q(s)&&(console.log(''+s),z=x)
      )(0,[...Array(z*z-z)+99].map((c,i)=>i%z?1:'\n'))
    )
    D=[~z,-~z,1-z,z-1,z,-z,1,-1]
    ,R=u=>!l.some(w=>u.map((a,p)=>a==w[0]&&D.map(d=>n+=[...w].every(c=>u[q+=d]==c,q=p-d)),
      n=~([...w]+''==[...w].reverse()))&&n>0)
    ,Q=(u,p=u.indexOf(1),r=[...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'])=>
      ~p?r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1):1
    //,Q=u=>u.map((c,i,u)=>u[i]=c!=1?c:' ') // uncomment to avoid random fill
}

```

**Ungolfed** and explained (incomplete, sorry guys it's a lot of work)

```
F=l=>
{
  var x, z, s, q, D, R, Q, W;
  // length of longest word in z
  z = Math.max( ... l.map(w => w.length))
  // sum of all words length in x
  x = 0;
  l.forEach(w => x += w.length);

  for(; ++z <= x; ) // test square size from z to x
  {
    // grid in s[], each row of len z + 1 newline as separator, plus leading and trailing newline
    // given z==offset between rows, total length of s is z*(z-1)+1
    // gridsize: 2, z:3, s.length: 7
    // gridsize: 3, z:4, s.length: 13
    // ...
    // All empty, nonseparator cells, filled with 1, so
    // - valid cells have a truthy value (1 or string)
    // - invalid cells have falsy value ('\n' or undefined)
    s = Array(z*z-z+1).fill(1)
    s = s.map((v,i) => i % z != 0 ? 1 : '\n');

    // offset for 8 directions
    D = [z+1, -z-1, 1-z, z-1, z, -z, 1, -1]; // 4 diags, then 2 vertical, then 2 horizontal

    // Function to check repeating words
    R = u => // return true if no repetition
      ! l.some( w => // for each word (exit early when true)
      {
          n = -1 -([...w]+''==[...w].reverse()); // counter starts at -1 or -2 if palindrome word
          u.forEach( (a, p) => // for each cell if grid
          {
            if (a == [0]) // do check if cell == first letter of word, else next word
               D.forEach( d => // check all directions
                 n += // word counter
                   [...w].every( c => // for each char in word, exit early if not equal
                     u[q += d] == c, // if word char == cell, continue to next cell using current offset
                     q = p-d  // starting position for cell
                   )
               ) // end for each direction
          } ) // end for each cell
          return n > 0 // if n>0 the word was found more than once
      } ) // end for each word

    // Recursive function to fill empty space with random chars
    // each call add a single char
    Q =
    ( u,
      p = u.indexOf(1), // position of first remaining empty cell
      r = [...'ABCDEFGHIJHLMNOPQRSTUVWXYZ'] // char array to be random shuffled
    ) => {
      if (~p) // proceed if p >= 0
        return r.some((v,c)=>(r[u[p]=r[j=0|c+Math.random()*(26-c)],j]=v,R(u)&&Q(u)))||(u[p]=1)
      else
        return 1; // when p < 0, no more empty cells, return 1 as true
    }
    // Main working function, recursive fill of grid
    W =
    ( k, // current word position in list
      s, // grid
      m, // bitmask with all directions used so far (8 H, 4V, 2 or 1 diag)
      w = l[k] // get current word
    ) => {
      var res = false
      if (w) { // if current word exists
        res = s.some((a,p)=>!!a&&
            D.some((d,j,_,r=[...s],q=p-d)=>
              [...w].every(c=>r[q+=d]==c?c:r[q]==1?r[q]=c:0)
              &&R(r)&&W(k+1,r,m|1<<(j/2))
            )
          )
      }
      else
      { // word list completed, check additional constraints
        if (m > 12 // m == 13, 14 or 15, means all directions used
            && Q(s) ) // try to fill with random, proceed if ok
        { // solution found !!
          console.log(''+s) // output grid
          z = x // z = x to stop outer loop
          res = x//return value non zero to stop recursion
        }
      }
      return res
    };
    W(0,s)
  }
}

```

**Test** in Firefox/FireBug console

F(\['TRAIN', 'CUBE','BOX','BICYCLE'\])

```
,T,C,B,O,X,B,H,
,H,R,U,H,L,I,H,
,Y,A,A,B,E,C,B,
,D,H,S,I,E,Y,I,
,H,E,R,L,N,C,T,
,G,S,T,Y,F,L,U,
,H,U,Y,F,O,E,H,

```

*not filled*

```
,T,C,B,O,X,B, ,
, ,R,U, , ,I, ,
, , ,A,B, ,C, ,
, , , ,I,E,Y, ,
, , , , ,N,C, ,
, , , , , ,L, ,
, , , , , ,E, ,

```

F(\['TRAIN','ARTS','RAT', 'CUBE','BOX','BICYCLE','STORM','BRAIN','DEPTH','MOUTH','SLAB'\])

```
,T,A,R,C,S,T,H,
,S,R,R,L,U,D,T,
,T,B,A,T,N,B,P,
,O,B,O,I,S,A,E,
,R,B,A,X,N,H,D,
,M,R,M,O,U,T,H,
,B,I,C,Y,C,L,E,

```

F(\['AA','AB','AC','AD','AE','AF','AG'\])

```
,A,U,B,C,
,T,A,E,Z,
,C,D,O,F,
,Q,C,G,A,

```

F(\['AA','AB','AC','AD','AE','AF'\])

*output not filled* \- @nathan: now you can't add another A*x* without repetitions. You'll need a bigger grid.

```
,A, ,C,
, ,A,F,
,D,E,B,

```
> 6 votes

# Answer
## C#

Here's a simple implementation with still work to be done. There are very many combinations to get smallest size. So just used simplest algorithm in could think of.

```
class Tile
{
    public char C;
    public int X, Y;
}

class Grid
{
    List<Tile> tiles;

    public Grid()
    {
        tiles = new List<Tile>();
    }
    public int MaxX()
    {
        return tiles.Max(x => x.X);
    }
    public int MaxY()
    {
        return tiles.Max(x => x.Y);
    }
    public void AddWords(List<string> list)
    {
        int n = list.Count;
        for (int i = 0; i < n; i++)
        {
            string s = list[i];
            if(i==0)
            {
                Vert(s, 0, 0);
            }
            else if(i==n-1)
            {
                int my = MaxY();
                Diag(s, 0, my+1);
            }
            else
            {
                Horiz(s, 0, i);
            }
        }

    }
    private void Vert(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x+i;
            t.Y = y;
            tiles.Add(t);
        }
    }
    private void Horiz(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x+i;
            t.Y = y;
            tiles.Add(t);
        }
    }
    private void Diag(string s, int x, int y)
    {
        for (int i = 0; i < s.Length; i++)
        {
            Tile t = new Tile();
            t.C = s[i];
            t.X = x++;
            t.Y = y++;
            tiles.Add(t);
        }
    }
    public void Print()
    {
        int mx = this.MaxX();
        int my = this.MaxY();
        int S = Math.Max(mx, my) + 1;
        char[,] grid = new char[S, S];
        Random r = new Random(DateTime.Now.Millisecond);
        //fill random chars
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                grid[i, j] = (char)(r.Next() % 26 + 'A');
            }
        }
        //fill words
        tiles.ForEach(t => grid[t.X, t.Y] = t.C);
        //print
        for (int i = 0; i < S; i++)
        {
            for (int j = 0; j < S; j++)
            {
                Console.Write("{0} ", grid[i,j]);
            }
            Console.WriteLine();
        }
    }
}

class WordSearch
{
    public static void Generate(List<string>list)
    {
        list.Sort((x, y) =>
        { int s = 0; if (x.Length < y.Length)s = -1; else if (y.Length < x.Length)s = 1; return s; });
        list.Reverse();
        Grid g = new Grid();
        g.AddWords(list);
        g.Print();
    }

}

```

Test

```
class Program
{
    static void Main(string[] args)
    {
        string words = "CAT, TRAIN, CUBE, BICYCLE";
        string comma=",";
        List<string> w = words.Split(comma.ToArray()).ToList();
        List<string> t = new List<string>();
        foreach(string s in w)
        {
           t.Add(s.Trim());
        }
        WordSearch.Generate(t);

        Console.ReadKey();
    }
}

```
> 1 votes

---
Tags: code-golf, word-search
---


title: Reconstruct a Permutation

text:
# Question
Title: Reconstruct a Permutation
# Introduction

Suppose that you are handed a random permutation of `n` objects. The permutation is sealed in a box, so you have no idea which of the `n!` possible ones it is. If you managed to apply the permutation to `n` distinct objects, you could immediately deduce its identity. However, you are only allowed to apply the permutation to length-`n` binary vectors, which means you'll have to apply it several times in order to recognize it. Clearly, applying it to the `n` vectors with only one `1` does the job, but if you're clever, you can do it with `log(n)` applications. The code for that method will be longer, though...

This is an experimental challenge where your score is a combination of code length and *query complexity*, meaning the number of calls to an auxiliary procedure. The spec is a little long, so bear with me.

# The Task

Your task is to write a **named function (or closest equivalent)** `f` that takes as inputs a positive integer `n`, and a permutation `p` of the first `n` integers, using either 0-based or 1-based indexing. Its output is the permutation `p`. However, **you are not allowed to access the permutation `p` directly**. The only thing you can do with it is to apply it to any vector of `n` bits. For this purpose, you shall use an auxiliary function `P` that takes in a permutation `p` and a vector of bits `v`, and returns the permuted vector whose `p[i]`th coordinate contains the bit `v[i]`. For example:

```
P([1,2,3,4,0], [1,1,0,0,0]) == [0,1,1,0,0]

```

You can replace "bits" with any two distinct values, such as `3` and `-4`, or `'a'` and `'b'`, and they need not be fixed, so you can call `P` with both `[-4,3,3,-4]` and `[2,2,2,1]` in the same call to `f`. The definition of `P` is not counted toward your score.

# Scoring

The *query complexity* of your solution on a given input is the number of calls it makes to the auxiliary function `P`. To make this measure unambiguous, your solution must be deterministic. You can use pseudo-randomly generated numbers, but then you must also fix an initial seed for the generator.

In this repository you'll find a file called `permutations.txt` that contains 505 permutations, 5 of each length between 50 and 150 inclusive, using 0-based indexing (increment each number in the 1-based case). Each permutation is on its own line, and its numbers are separated by spaces. Your score is **byte count of `f` \+ average query complexity on these inputs**. Lowest score wins.

# Extra Rules

Code with explanations is preferred, and standard loopholes are disallowed. In particular, individual bits are indistinguishable (so you can't give a vector of `Integer` objects to `P` and compare their identities), and the function `P` always returns a new vector instead of re-arranging its input. You can freely change the names of `f` and `P`, and the order in which they take their arguments.

If you are the first person to answer in your programming language, you are strongly encouraged to include a test harness, including an implementation of the function `P` that also counts the number of times it was called. As an example, here's the harness for Python 3.

```
def f(n,p):
    pass # Your submission goes here

num_calls = 0

def P(permutation, bit_vector):
    global num_calls
    num_calls += 1
    permuted_vector = [0]*len(bit_vector)
    for i in range(len(bit_vector)):
        permuted_vector[permutation[i]] = bit_vector[i]
    return permuted_vector

num_lines = 0
file_stream = open("permutations.txt")
for line in file_stream:
    num_lines += 1
    perm = [int(n) for n in line.split()]
    guess = f(len(perm), perm)
    if guess != perm:
        print("Wrong output\n %s\n given for input\n %s"%(str(guess), str(perm)))
        break
else:
    print("Done. Average query complexity: %g"%(num_calls/num_lines,))
file_stream.close()

```

In some languages, it is impossible to write such a harness. Most notably, Haskell does not allow the pure function `P` to record the number of times it is called. For this reason, you are allowed to re-implement your solution in such a way that it also calculates its query complexity, and use that in the harness.

# Answer
> 11 votes
## J, ~~44.0693~~ 22.0693 = ~~37~~ 15 + 7.06931

If we can't call `P` on `i. n`, we can at least call `P` on each bit of `i. n` separately. The number of invocations of `P` is `>. 2 ^. n` (⌈log2*n*⌉). I believe this is optimal.

```
f=:P&.|:&.#:@i.

```

Here is an implementation of the function `P` which uses the permutation vector `p` and saves the number of invocations into `Pinv`.

```
P =: 3 : 0"1
 Pinv =: Pinv + 1
 assert 3 > # ~. y    NB. make sure y is binary
 p { y
)

```

Here is a testing harness that receives a permutation and returns the number of invocations of `p`:

```
harness =: 3 : 0
 Pinv =: 0
 p =: y
 assert y = f # y     NB. make sure f computed the right permutation
 Pinv
)

```

And here is how you can use it on the file `permutations.txt`:

```
NB. average P invocation count
(+/ % #) harness@".;._2 fread 'permutations.txt'

```

## Explanation

The short explanation is already provided above, but here is a more detailed one. First, `f` with spaces inserted and as an explicit function:

```
f =: P&.|:&.#:@i.
f =: 3 : 'P&.|:&.#: i. y'

```

Read:

> Let *f* be P under transposition under base-2 representation of the first *y* integers.

where *y* is the formal parameter to *f.* in J, the parameters to a (function) are called *x* and *y* if the verb is dyadic (has two parameters) and *y* if it is monadic (has one parameter).

Instead of invoking `P` on `i. n` (i.e. `0 1 2 ... (n - 1)`), we invoke `P` on each bit position of the numbers in `i. n`. Since all permutations permute in the same way, we can reassemble the permutated bits into numbers to get a permutation vector:

* `i. y` – integers from `0` to `y - 1`.
* `#: y``y` represented in base 2. This is extended to vectors of numbers in the natural way. For instance, `#: i. 16` yields:

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

```
* `#. y``y` interpreted as a base 2 number. Notably, this is the inverse to `#:`; `y ~: #. #:` always holds.
* `|: y``y` transposed.
* `u&.v y``u` under `v`, that is `vinv u v y` where `vinv` is the inverse to `v`. Notice that `|:` is its own inverse.
* `P y` – the function `P` applied to each vector in `y` by definition.

# Answer
> 3 votes
# Pyth 32 + 7.06931 = 37.06931

I found the following algorithm completely independent. But it's more or less the same thing as FUZxxl very short J solution (as far as I understand it).

First the definition of the function `P`, which permutes an bit-array according to an unknown permutation.

```
D%GHJHVJ XJ@HN@GN)RJ

```

And then the code, that determines the permutation.

```
Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG

```

This defines a function `g`, that takes two arguments. You can call it by `g5[4 2 1 3 0`. Here's an online demonstration. Never used so many (5) nested maps.

Btw I haven't actually made a test harness. Neither does the function `P` count how many times I call it. I have spend way to much time already figuring out the algorithm. But if you read my explanation, it's quite obvious that it uses `int(log2(n-1)) + 1` calls (`= ceil(log2(n))`). And `sum(int(log2(n-1)) + 1 for n in range(50, 151)) / 101.0 = 7.069306930693069`.

## Explanation:

I actually had quite a hard time finding this algorithm. It was not clear to me at all, how to achieve `log(n)`. So I started doing some experiments with small `n`.

First note: A bit-array gathers the same information as the complement bit-array. Therefore all bit-arrays in my solution have at most `n/2` active bit.

**n = 3:**

Since we can only use bit-array with 1 active bit, the optimal solution depends of two calls. E.g. `P([1, 0, 0])` and `P([0, 1, 0])`. The results tell us the first and second number of the permutation, indirectly we get the third one.

**n = 4:**

Here it get's a little bit interesting. We now can use two kinds of bit-array. Those with 1 active bit and those with 2 active bits. If we use a bit-array with one active bit, we only gather information about one number of the permutation, and fall back to `n = 3`, resulting in `1 + 2 = 3` calls of `P`. The interesting part is that we can do the same thing with only 2 calls, if we use bit-arrays with 2 active bits. E.g. `P([1, 1, 0, 0])` and `P([1, 0, 1, 0])`.

Let's say we get the outputs `[1, 0, 0, 1]` and `[0, 0, 1, 1]`. We see, that the bit number 4 is active in both output arrays. The only bit that was active in both input arrays was bit number 1, so clearly the permutation starts with `4`. Now it's easy to see, that bit 2 was moved to bit 1 (first output), and bit 3 was moved to bit 3 (second output). Therefore the permutation must be `[4, 1, 3, 2]`.

**n = 7:**

Now something bigger. I'll show the calls of `P` immediately. They are the once, that I came up with after a little thinking and experimenting. (Notice these are not the ones, that I use in my code.)

```
P([1, 1, 1, 0, 0, 0, 0])
P([1, 0, 0, 1, 1, 0, 0])
P([0, 0, 1, 1, 0, 1, 0])

```

If in the first two output arrays (and not in the third) the bit 2 is active, we know that the permutation moves bit 1 to bit 2, since bit one is the only bit that is active in the first two input arrays.

The important thing is, that (interpreting the inputs as matrix) each of the columns are unique. This remembered me on Hamming codes, where the same thing is accomplished. They simply take the numbers 1 to 7, and use their bit-representation as columns. I'll use the numbers 0 to 6. Now the nice part, we can interpret the outputs (again the columns) as numbers again. These tell us the result of the permutation applied to `[0, 1, 2, 3, 4, 5, 6]`.

```
   0  1  2  3  4  5  6      1  3  6  4  5  0  2
P([0, 1, 0, 1, 0, 1, 0]) = [1, 1, 0, 0, 1, 0, 0]
P([0, 0, 1, 1, 0, 0, 1]) = [0, 1, 1, 0, 0, 0, 1]
P([0, 0, 0, 0, 1, 1, 1]) = [0, 0, 1, 1, 1, 0, 0]

```

So we only have to trace back the numbers. Bit 0 ended up in bit 5, bit 1 ended up in bit 0, bit 2 ended up in bit 6, ... So the permutation was `[5, 0, 6, 1, 3, 4, 2]`.

```
Mmxmi_mbk2Cm%dHCm+_jk2*sltG]0GdG
M                                 define a function g(G, H), that will return
                                  the result of the following computation:
                                  G is n, and H is the permutation.
                m            G     map each k in [0, 1, ..., Q-1] to:
                  _                   their inverse
                   jk2                binary representation (list of 1s and 0s)
                 +                    extended with
                      *sltG]0         int(log2(Q - 1)) zeros
               C                   transpose matrix # rows that are longer
                                                   # than others are shortened
           m%dH                    map each row (former column) d of
                                   the matrix to the function P (here %)
          C                        transpose back
   m                              map each row k to:
    i    2                           the decimal number of the
     _mbk                            inverse list(k) # C returns tuple :-(
Let's call the result X.
 m                             G   map each d in [0, 1, ..., Q - 1] to:
  x         X                 d       the index of d in X

```

And the code for the permutation function:

```
D%GHJHVJ XJ@HN@GN)RJ
D%GH                     def %(G, H):  # the function is called %
    JH                     J = copy(H)
      VJ         )        for N in [0, 1, ..., len(J) - 1]:
         XJ@HN@GN            J[H[N]] = G[N]
                  RJ      return J

```

# Answer
> 2 votes
# Mathematica, 63 + 100 = 163

I'm using one-based permutations, since that's how indexing works in Mathematica.

First, the test harness. This is the query function `p` (user-defined names shouldn't be upper-case in Mathematica):

```
p[perm_, vec_] := (
   i += 1;
   vec[[Ordering@perm]]
   );

```

And input preparation along with the test loop:

```
permutations =
  ToExpression@StringSplit@# + 1 & /@
   StringSplit[Import[
     "https://raw.githubusercontent.com/iatorm/permutations/master/permutations.txt"
   ], "\n"];
total = 0;
(
    i = 0;
    result = f@#;
    If[# != result,
      Print["Wrong result for ", #, ". Returned ," result ", instead."]
    ];
    total += i;
    ) & /@ permutations;
N[total/Length@permutations]

```

And finally, my actual submission which uses the naive algorithm for now:

```
f=(v=0q;v[[#]]=1;Position[q~p~v,1][[1,1]])&/@Range@Length[q=#]&

```

Or with indentation:

```
f = (
     v = 0 q;
     v[[#]] = 1;
     Position[q~p~v, 1][[1, 1]]
) & /@ Range@Length[q = #] &

```

---
Tags: permutations, fewest-operations
---


title: Chinese Remainder Theorem

text:
# Question
Title: Chinese Remainder Theorem
The Chinese Remainder Theorem tells us that we can always find a number that produces any required remainders under different prime moduli. Your goal is to write code to output such a number in polynomial time. Shortest code wins.

For example, say we're given these constraints:

* \\$n \equiv 2 \mod 7\\$
* \\$n \equiv 4 \mod 5\\$
* \\$n \equiv 0 \mod 11\\$

One solution is \\$n=44\\$. The first constraint is satisfied because \\$44 = 6\times7 + 2\\$, and so \\$44\\$ has remainder \\$2\\$ when divided by \\$7\\$, and thus \\$44 \equiv 2 \mod 7\\$. The other two constraints are met as well. There exist other solutions, such as \\$n=814\\$ and \\$n=-341\\$.

**Input**

A non-empty list of pairs \\$(p\_i,a\_i)\\$, where each modulus \\$p\_i\\$ is a distinct prime and each target \\$a\_i\\$ is a natural number in the range \\$0 \le a\_i \< p\_i\\$. You can take input in whatever form is convenient; it doesn't have to actually be a list of pairs. You may not assume the input is sorted.

**Output**

An integer \\$n\\$ such that \\$n \equiv a\_i \mod p\_i\\$ for each index \\$i\\$. It doesn't have to be the smallest such value, and may be negative.

**Polynomial time restriction**

To prevent cheap solutions that just try \\$n=0, 1, 2, \dots\\$, and so on, your code must run in polynomial time in the *length of the input*. Note that a number \\$m\\$ in the input has length \\$Θ(\log m)\\$, so \\$m\\$ itself is not polynomial in its length. This means that you can't count up to \\$m\\$ or do an operation \\$m\\$ times, but you can compute arithmetic operations on the values.

You may not use an inefficient input format like unary to get around this.

**Other bans**

Built-ins to do the following are not allowed: Implement the Chinese Remainder theorem, solve equations, or factor numbers.

You may use built-ins to find mods and do modular addition, subtraction, multiplication, and exponentiation (with natural-number exponent). You *may not* use other built-in modular operations, including modular inverse, division, and order-finding.

**Test cases**

These give the smallest non-negative solution. Your answer may be different. It's probably better if you check directly that your output satisfies each constraint.

```
[(5, 3)]
3

[(7, 2), (5, 4), (11, 0)]
44

[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
1770977011

[(982451653, 778102454), (452930477, 133039003)]
68121500720666070

```

# Answer
> 9 votes
# Mathematica, ~~55~~ ~~51~~ 45

Modular inverse is banned, but modular exponentiation is allowed. By Fermat's little theorem, `n^(-1) % p == n^(p-2) % p`.

```
(PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&

```

Example:

```
In[1]:= f = (PowerMod[x=1##&@@#/#,#-2,#]x).#2&@@Thread@#&;

In[2]:= f[{{5, 3}}]

Out[2]= 3

In[3]:= f[{{7, 2}, {5, 4}, {11, 0}}]

Out[3]= 1584

In[4]:= f[{{5, 1}, {73, 4}, {59, 30}, {701, 53}, {139, 112}}]

Out[4]= 142360350966

```

---

Just for fun:

```
ChineseRemainder@@Reverse@Thread@#&

```

# Answer
> 6 votes
## Python 2, ~~165~~ ~~101~~ ~~99~~ ~~98~~ 85 bytes

Using Fermat's little theorem like the other answers. Doesn't bother with keeping final sum within modular range, since we're not interested in the smallest solution. Thanks Volatility for saving 13 bytes.

```
l=input();x=reduce(lambda a,b:a*b[0],l,1)
print sum(x/a*b*pow(x/a,a-2,a)for a,b in l)

[(5, 3)]
3
[(7, 2), (5, 4), (11, 0)]
1584
[(5, 1), (73, 4), (59, 30), (701, 53), (139, 112)]
142360350966

```

# Answer
> 4 votes
# Pyth, 40 37 36 29

```
M*G.^G-H2Hsm*edg/u*GhHQ1hdhdQ

```

Uses Fermat's little theorem, thanks to alephalpha. Computes using this formula.

# Answer
> 3 votes
**Ruby, 129**

Well, comrades, it seems Ruby solutions must be longer because modular exponentiation is not available without loading openssl library and doing conversions to OpenSSL::BN. Still, had fun writing it:

```
require("openssl")
z=eval(gets)
x=1
z.map{|a,b|x*=a}
s=0
z.map{|a,b|e=a.to_bn;s+=(x/a).to_bn.mod_exp(e-2,e).to_i*b*x/a}
puts(s)

```

# Answer
> 3 votes
# Python 2, 61

```
n=P=1
for p,a in input():n+=P*(a-n)*pow(P,p-2,p);P*=p
print n

```

This employs a variation of the product construction that other answers use.

The idea is to loop over the constraints and update the solution `n` to meet the current constraint without messing up the prior ones. To do so, we track the product `P` of the primes seen up to now, and observe that adding a multiple of `P` has no effect modulo any already-seen prime.

So, we just need to change `n` to satisfy `n%p == a` by adding the right multiple of `P`. We solve for the coefficient `c`:

`(n + P*c) % p == a`

This requires that `c = (a-n) * P^(-1)`, where the inverse is taken modulo `p`. As others note, the inverse can be computed by Fermat's Little Theorem as `P^(-1) = pow(P,p-2,p)`. So, `c = (a-n) * pow(P,p-2,p)`, and we update `n` by `n+= P * (a-n) * pow(P,p-2,p)`.

# Answer
> 1 votes
# Haskell, ~~68~~ 100 bytes

```
f l=sum[p#(m-2)*n*p|(m,n)<-l,let a#0=1;a#n=(a#div n 2)^2*a^mod n 2`mod`m;p=product(map fst l)`div`m]

```

Usage: `f [(5,1), (73,4), (59,30), (701,53), (139,112)]` -\> `142360350966`.

Edit: now with a fast "power/mod" function. Old version (68 bytes) with inbuilt power function:

```
f l=sum[l#m^(m-2)`mod`m*n*l#m|(m,n)<-l]
l#m=product(map fst l)`div`m

```

---
Tags: code-golf, math, number, number-theory, restricted-complexity
---


title: Square, Circle, Triangle, ...Gear?

text:
# Question
Title: Square, Circle, Triangle, ...Gear?
Using Algodoo and Paint I made these six 300×300 monochromatic images of four convenient shapes:

This class of images has the following properties:

* They are always 300×300 pixels, monochromatic (black and white only), and have exactly four white regions that correspond to a square, a circle, a triangle, and a gear.
* The shapes never overlap or touch each other, nor do they touch the image border or go out of bounds.
* The shapes always have the same size, but they may be rotated and positioned in any way.

(The shapes also have equal areas, though when rastered like this their pixel counts are unlikely to be exactly equivalent.)

# Challenge

Write the shortest program or function possible that takes in the filename of such an image and turns all the white pixels...

* red `(255, 0, 0)` if they are in the square.
* blue `(0, 0, 255)` if they are in the circle.
* green `(0, 255, 0)` if they are in the triangle.
* yellow `(255, 255, 0)` if they are in the gear.

e.g.

# Details

**Your program should work for effectively all possible input images.** (Only valid 300×300 monochromatic images will be input.) The six images I have provided are merely examples, you may not hardcode their output into your program.

**You may not use computer vision libraries or functions, built-in or external.** The point is to do this using your own pixel-level operations. You may use image libraries that simply let you open and modify images (e.g. PIL for Python).

You may use any common lossless image file formats for input and output as long as you stick to the color scheme.

You can take in the image filename as a function argument, from stdin, or from the command line. The output image can be saved to a new file, the same file, or simply displayed.

# Scoring

The submission with the fewest bytes wins. I may test submissions with additional images to determine their validity.

# Answer
> 8 votes
## J - 246,224 185 bytes

```
load'viewmat'
(viewmat~0,(255*4 3$_2|.#:3720)/:/:@(<([:}.(>./%+/%#)@:(+/&:*:@(-"1)+/%#)@(4$.$.@:=)&>)<"0@~.@,))@(~.@,i.])@(>./**@{.)@((0,(,-)#:>:i.3)&|.)^:_@(*i.@:$)@(0<readimg_jqtide_)

```

This was a fun one!

I reused the connected-components part I used for the "Am I in the biggest room" challenge, and used the ratio between average and maximum distance of all points to each component's center. I settled for this, as it's both scale and rotation invariant, and apparently good enough to distinguish between the shapes as given. Ranking this value from low to high gives me the order circle, gear, square and triangle, used to permute the colormap.

Displays the result using the viewmap addon. No toolboxes used except for file reading and output.

Robustness does not seem to be a requirement, this takes off 18 bytes. 2 more unnecessary spaces, replaced `&.>` by `&>` in `ratio` and `&.:` by `&:` in dcent for another 2 bytes.

Huge gain in both shortness and performance of `comp` using shifting instead of `cut` (`;.`). This way the image is replicated and shifted in all 8 directions instead of scanning it with a 3x3 window.

The `id` function was ridiculously complex for what it needed to do. Now it assigns id's to pixels in objects by multiplying the image with an array of unique numbers, hence setting the BG to zero.

Code a bit more explained:

```
load'viewmat'                                 NB. display only
imnames =: < ;. _2 (0 : 0)
C6IKR.png
DLM3y.png
F1ZDM.png
Oa2O1.png
YZfc6.png
chJFi.png
)

images =: (0<readimg_jqtide_) each imnames    NB. read all images in boxed array

id =: *i.@:$                                  NB. NB. assign one number to each non-background (non-zero) pixel
comp =: (>./ * *@{.)@shift^:_@id              NB. 8 connected neighbor using shift
  shift =: (>,{,~<0 _1 1)&|.                  NB. generate the original, and 8 shifted versions (automatically padding and cropping).
result =: comp each images                    NB. Execute comp verb for each image
col =: (~.@, i. ])                            NB. Color: give each component and BG a separate color.

NB. BG in 0, 0 Get all max distance to center % mean distance to center ratios
ratio  =: (< ([:}.rat@:dcent@getInd &>)  <"0@~.@,)
  getInd =: 4 $. $.@:=                        NB. get indices for component y in array x
  dcent  =: +/&.:*:@(-"1) +/%#                NB. distence from center each point
  rat    =: >./ % +/%#                        NB. ratio from distances

cm=: (255*4 3$_2|.#:3720)                     NB. colormap (except black).
(viewmat~ 0,cm /: /:@ratio )@col each result  NB. for each image, show the result, permuting the colormap according to ratio's

NB. almostgolf this
P1 =: (>./**@{.)@((0,(,-)#:>:i.3)&|.)^:_@(*i.@:$)@(0<readimg_jqtide_) NB. reading till components
P2 =: (<([:}.(>./%+/%#)@:(+/&:*:@(-"1)+/%#)@(4$.$.@:=)&>)<"0@~.@,) NB. recognition: get fraction mean vs max distance to center per component, toss BG.
P3 =: (viewmat~0,(255*4 3$_2|.#:3720)/:/:@P2)@(~.@,i.])@P1    NB. piece together : permute colormap, display components

NB. seriousgolf
load'viewmat'
f =:(viewmat~0,(255*4 3$_2|.#:3720)/:/:@(<([:}.(>./%+/%#)@:(+/&:*:@(-"1)+/%#)@(4$.$.@:=)&>)<"0@~.@,))@(~.@,i.])@((>./**@{.)@shift^:_)@(*i.@:$)@(0<readimg_jqtide_)
NB. example usage:
f&> imnames NB. do for all images

```

This one is a bit long to explain in detail, but will do if there is interest.

# Answer
> 31 votes
## Mathematica, ~~459~~ 392 bytes

```
f=(d=ImageData@Import@#/.{a_,_,_}:>a;(For[a={};b={#&@@d~Position~1},b!={},c=#&@@b;b=Rest@b;d[[##&@@c]]=0;a~AppendTo~c;If[Extract[d,c+#]==1,b=b⋃{c+#}]&/@{e={1,0},-e,e={0,1},-e}];m=1.Mean@a;m=#-m&/@a;n=Count[Partition[Norm/@SortBy[m,ArcTan@@#&],300,1,1],l_/;l[[150]]==Max@l];(d[[##&@@#]]=Round[n^.68])&/@a)&/@Range@4;Image[d/.n_Integer:>{{0,0,0},,{0,1,0},{1,0,0},,,,{1,1,0},{0,0,1}}[[n+1]]])&

```

Ungolfed:

```
f = (
 d = ImageData@Import@# /. {a_, _, _} :> a;
 (
    For[a = {}; b = {# & @@ d~Position~1},
     b != {},
     c = # & @@ b;
     b = Rest@b;
     d[[## & @@ c]] = 0;
     a~AppendTo~c;
     If[Extract[d, c + #] == 1,
        b = b ⋃ {c + #}] & /@ {e = {1, 0}, -e, e = {0, 1}, -e}
     ];
    m = 1. Mean@a; m = # - m & /@ a;
    n =
     Count[Partition[Norm /@ SortBy[m, ArcTan @@ # &], 300, 1, 1],
      l_ /; l[[150]] == Max@l];
    (d[[## & @@ #]] = Round[n^.68]) & /@ a
    ) & /@ Range@4;
 Image[d /.
   n_Integer :> {{0, 0, 0}, , {0, 1, 0}, {1, 0, 0}, , , , {1, 1,
       0}, {0, 0, 1}}[[n + 1]]]
) &

```

I could save 6 more bytes by turning `m=1.Mean@a;m=#-m&/@a;` into `m=#-Mean@a&/@a;`, but that significantly blows up execution time, which is annoying for testing. (Note, that this is two optimisations: pulling out the computation of `Mean@a` out of loop *and* using exact symbolic types instead of floating point numbers. Interestingly, the use of exact types is *a lot* more significant than computing the mean in every iteration.)

So this is approach number three:

* Detect areas by flood-fill.
* Find approximate centre of each area by averaging all pixel coordinates.
* Now for all pixels in the shape let's plot distance from vs angle to that centre:

The triangle has 3 clear maxima, the square 4, the gear 16, and the circle has tons, due to aliasing fluctuations about the constant radius.
* We find the number of maxima by looking at slices of 300 pixels (ordered by angle), and count the slices where the pixel at position `150` is the maximum.
* Then we just colour all pixels depending on the number of peaks (the circle is anything over 16, and usually yields around 20 peaks, due to the size of the slices).

Just for the record, if I use Ell's idea, and simply sort the regions by largest distance between any pixel and centre, I can do this in 342 bytes:

```
f=(d=ImageData@Import@#/.{a_,_,_}:>a;MapIndexed[(d[[##&@@#]]=#&@@#2)&,SortBy[(For[a={};b={#&@@d~Position~1},b!={},c=#&@@b;b=Rest@b;d[[##&@@c]]=0;a~AppendTo~c;If[Extract[d,c+#]==1,b=b⋃{c+#}]&/@{e={1,0},-e,e={0,1},-e}];a)&/@Range@4,(m=Mean@#;Max[1.Norm[#-m]&/@#])&],{2}];Image[d/.n_Integer:>{{0,0,0},{0,0,1},{1,1,0},{1,0,0},{0,1,0}}[[n+1]]])&

```

But I do not intend to compete with that, as long as everyone else is using their own original algorithms, instead of golfing down those of others.

# Answer
> 25 votes
# Java, ~~1204~~ ~~1132~~ ~~1087~~ 1076

Just to prove to myself that ***I*** can do this.

I included imports right next to the function declarations; these would have to be outside the class for this to work:

```
import java.awt.*;import java.awt.image.*;import java.io.*;import java.util.*;import javax.imageio.*;

BufferedImage i;Set<Point>Q;void p(String a)throws Exception{i=new BufferedImage(302,302,1);i.getGraphics().drawImage(ImageIO.read(new File(a)),1,1,null);Set<Set<Point>>S=new HashSet<>();for(int y=0;y<300;y++){for(int x=0;x<300;x++){if(!G(x,y)){Point p=new Point(x,y);Q=new HashSet<>();if(!S.stream().anyMatch(s->s.contains(p)))S.add(f(x,y));}}}Object[]o=S.stream().sorted((p,P)->c(p)-c(P)).toArray();s(o[0],255);s(o[1],255<<16);s(o[2],0xFF00);s(o[3],0xFFFF00);ImageIO.write(i.getSubimage(1,1,300,300),"png",new File(a));}boolean G(int x,int y){return i.getRGB(x,y)!=-1;}Set<Point>f(int x,int y){Point p=new Point(x,y);if(!Q.contains(p)&&!G(x,y)){Q.add(p);f(x-1,y);f(x+1,y);f(x,y-1);f(x,y+1);}return Q;}int c(Set<Point>s){return(int)s.stream().filter(p->G(p.x-2,p.y-1)||G(p.x-2,p.y+1)||G(p.x+1,p.y-2)||G(p.x-1,p.y-2)||G(p.x+2,p.y-1)||G(p.x+2,p.y+1)||G(p.x+1,p.y+2)||G(p.x-1,p.y+2)).count();}void s(Object o,int c){((Set<Point>)o).stream().forEach(p->{i.setRGB(p.x,p.y,c);});}

```

Ungolfed (and runnable; ie boilerplate added):

```
import java.awt.Point;
import java.awt.image.BufferedImage;
import java.io.File;
import java.util.HashSet;
import java.util.Set;
import javax.imageio.ImageIO;

public class SquareCircleTriangleGear {
    public static void main(String[]args){
        try {
            new SquareCircleTriangleGear().p("filepath");
        } catch (Exception ex) {
        }
    }
    BufferedImage i;
    Set<Point>Q;
    void p(String a)throws Exception{
        i = new BufferedImage(302,302,BufferedImage.TYPE_INT_RGB);
        i.getGraphics().drawImage(ImageIO.read(new File(a)),1,1,null);
        Set<Set<Point>>set=new HashSet<>();
        for(int y=0;y<300;y++){
            for(int x = 0;x<300;x++){
                if(i.getRGB(x,y)==-1){
                    Point p = new Point(x,y);
                    Q=new HashSet<>();
                    if(!set.stream().anyMatch((s)->s.contains(p))){
                        set.add(fill(x,y));
                    }
                }
            }
        }
        Object[]o=set.stream().sorted((p,P)->c(p)-c(P)).toArray();
        s(o[0],0x0000FF);
        s(o[1],0xFF0000);
        s(o[2],0x00FF00);
        s(o[3],0xFFFF00);
        ImageIO.write(i.getSubImage(1,1,300,300), "png", new File(a));
    }
    Set<Point>fill(int x, int y){
        Point p=new Point(x,y);
        if(!Q.contains(p)&&!i.getRGB(x,y)!=-1) {
        Q.add(p);
            fill(x-1,y);
            fill(x+1,y);
            fill(x,y-1);
            fill(x,y+1);
        }
        return Q;
    }
    int c(Set<Point>s){return (int)s.stream().filter(p->isBoundary(p.x,p.y)).count();}
    boolean isBoundary(int x, int y){
        return i.getRGB(x-2,y-1)!=-1||i.getRGB(x-2,y+1)!=-1||i.getRGB(x+1,y-2)!=-1||
               i.getRGB(x-1,y-2)!=-1||i.getRGB(x+2,y-1)!=-1||i.getRGB(x+2,y+1)!=-1||
               i.getRGB(x+1,y+2)!=-1||i.getRGB(x-1,y+2)!=-1;
    }
    void s(Object o,int c){
        ((Set<Point>)o).stream().forEach(p->{i.setRGB(p.x,p.y,c);});
    }
}

```

This works by iterating over every pixel of the image and flood-filling each time we reach a "hole". We add each flood-fill result as a `Set<Point>` to a `Set`. Then we determine which shape is which. This is done by looking at the number of boundary pixels of the shape. I defined boundary as a knight's move away from a black tile, since that would stay more constant between rotations and such. When we do this, it becomes clear that the shapes can be sorted by that value: Circle, Square, Triangle, Gear. So I sort and set all pixels of that shape to the correct color.

Note that the image I'm writing to is not directly taken from the file, because if I were to do that, Java would treat the image as black and white and filling with colors wouldn't work. So I have to create my own image with `TYPE_INT_RGB` (which is `1`). Also note that the image I'm doing work on is `302` by `302`; this is so that the Knight's distance algorithm doesn't need to worry about attempting to read out-of-bounds on the image. I fix this discrepancy in size by calling `i.getSubImage(1,1,300,300)`. Note: I may have forgotten to fix this when I uploaded the images, in which cases the images are 2 pixels too wide, but except for this fact, they should be correct

The function will overwrite the file whose path is passed in. Outputs:

# Answer
> 21 votes
# Python, ~~571 567~~ 528 bytes

Similarly to Quincunx's solution, it starts by flood-filling each shape with an index from 1 to 4. It then determines the identity of the shapes by the radius of their bounding circle. A color-palette is constructed accordingly and the image is saved as an indexed-color image.

**EDIT:** Missed the fact the shapes are guaranteed not to touch the image border. Shorter it is, then!

```
from PIL.Image import*;from numpy import*
I=open(sys.argv[1]).convert("P")
D=list(I.getdata())
W=300;R=range(W*W);N=range(5)
O=[[0,i,array([0,0])]for i in N];n=0
for i in R:
 if D[i]>4:
    n+=1;S=[i]
    while S:
     j=S.pop()
     if D[j]>4:D[j]=n;O[n][0]+=1;O[n][2]+=j%W,j/W;S+=[j+1,j-1,j+W,j-W]
for o in O[1:]:o[2]/=o[0];o[0]=0
for i in R:
 if D[i]:o=O[D[i]];v=(i%W,i/W)-o[2];o[0]=max(o[0],dot(v,v))
O.sort()
C=[0]*5+[255]*3+[0,255,0,0]*2;P=C[:]
for i in N:j=3*O[i][1];P[j:j+3]=C[3*i:3*i+3]
I.putdata(D);I.putpalette(P);I.save("o.png")

```

Takes an input filename on the command line and writes the output to `o.png`.

# Answer
> 7 votes
# Mathematica 225

---

**Update**:

The OP decided that this approach uses computer vision functions, so it's no longer in the running. I'll leave it posted however. Perhaps someone may find it of interest.

---

```
f@i_ := (m = MorphologicalComponents[ImageData@i];
Image@Partition[Flatten[(m)] /.
   Append[ ReplacePart[SortBy[ComponentMeasurements[m, "Circularity"], Last],
   {{1, 2} -> Yellow, {2, 2} -> Green, {3, 2} -> Red, {4, 2} -> Blue}], 0 -> Black],
Dimensions[m][[2]]])

```

`ImageData` returns the image as a matrix of 0's and 1's.

`Flatten` converts that matrix to a list.

`Morphological Components` finds the 4 clusters of pixels and assigns a distinct integer, 1, 2, 3, 4 to each pixel according to the cluster. 0 is reserved for the (black) background.

`ComponentMeasurements` tests the circularity of the clusters.

From most to least circular will always be: the circle, the square, the triangle, and the gear.

`ReplacePart` replaces each component integer with the respective RGB color, using the circularity sort.

`Partition...Dimensions[m][[2]]` takes the list of pixel colors, and returns a matrix the same dimensions as the input image.

`Image` converts the matrix of pixel colors to a colored image.

```
{f[img1],f[img2],f[img3],f[img4]}

```

# Answer
> 7 votes
# Mathematica, ~~354~~ ~~345~~ ~~314~~ ~~291~~ 288

Still golfing, could be shortened by a few more chars, but performance becomes unbearable. Uses the Variance to identify shapes:

```
f=(w=Position[z=ImageData@Import@#,1];r=Nearest;v@x_:=Variance@N[Norm[Mean@x-#]&/@x];Image[Plus@@(ReplacePart[0z/. 0->{0,0,0},#->r[{108,124,196,115}->List@@@{Blue,Red,Green,Yellow},v@#][[1]]]&/@Rest@NestList[(m=r[w=w~Complement~#];FixedPoint[Union@@(m[#,{8,2}]&/@#)&,{#&@@w}])&,{},4])])&

```

With spacing:

```
f = (w = Position[z = ImageData@Import@#, 1];
     r = Nearest;
     v@x_ := Variance@N[Norm[Mean@x - #] & /@ x];
     Image[Plus @@ (ReplacePart[ 0 z /. 0 -> {0, 0, 0}, # -> r[{108, 124, 196, 115} ->
                                              List @@@ {Blue, Red, Green, Yellow}, v@#][[1]]] & /@
     Rest@NestList[(m = r[w = w~ Complement~#];
                   FixedPoint[Union @@ (m[#, {8, 2}] & /@ #) &, {# & @@ w}]) &
                   , {}, 4])]) &

```

Testing:

```
s = {"https://i.stack.imgur.com/Oa2O1.png", "https://i.stack.imgur.com/C6IKR.png",
     "https://i.stack.imgur.com/YZfc6.png", "https://i.stack.imgur.com/F1ZDM.png",
     "https://i.stack.imgur.com/chJFi.png", "https://i.stack.imgur.com/DLM3y.png"};
Partition[f /@ s, 3] // Grid

```

Here it is completely ungolfed. Will add explanations later:

```
findOneZone[{universe_List, lastZone_List}] :=
 Module[{newUniverse, proximityFindFunc, seedElement},
  newUniverse = Complement[universe, lastZone];
  proximityFindFunc = Nearest@newUniverse;
  seedElement = {First@newUniverse};
  {newUniverse, FixedPoint[Union @@ (proximityFindFunc[#, {8, 2}] & /@ #) &, seedElement]}]

colorAssign[zone_List] :=
 Module[{
   vlist = {108, 124, 196, 115},
   cols = List @@@ {Blue, Red, Green, Yellow},
   centerVariance},
  centerVariance[x_List] := Variance@N[Norm[Mean@x - #] & /@ x];
  First@Nearest[vlist -> cols, centerVariance@zone]]

colorRules[zones_List] := (# -> colorAssign[#] & /@ zones)

main[urlName_String] :=
 Module[{pixels, FgPixelPositions, rawZones, zones},
  pixels = ImageData@Import@urlName;
  FgPixelPositions = Position[pixels, 1];
  (*fill and separate the regions*)
  rawZones = NestList[findOneZone[#] &, {FgPixelPositions, {}}, 4];
  zones = Rest[rawZones][[All, 2]];
  (*Identify,colorize and render*)
  Image@ReplacePart[ConstantArray[{0, 0, 0}, Dimensions@pixels],
    colorRules[zones]]]

s = {"https://i.stack.imgur.com/Oa2O1.png"};
main /@ s

```

# Answer
> 2 votes
# Python, ~~579~~ ~~577~~ ~~554~~ ~~514~~ ~~502~~ 501 bytes

For each shape, flood-fills it, then compute the distance between the centroid and the farthest point.

then the real surface of the shape is compared to the surface of a triangle, square, disc or wheel that would have the same size.

```
import math;from PIL.Image import*;A,R,_,I=abs,range(300),255,open(sys.argv[1]).convert('P');Q=I.load()
for j in R:
 for i in R:
  if Q[i,j]==_:
   X,Y,s,z,p=0,0,0,[],[(i,j)]
   while p:
    a,b=n=p.pop()
    if not(Q[n]!=_ or n in z):
     X+=a;Y+=b;z+=[n];p+=[(a,b-1),(a+1,b),(a,b+1),(a-1,b)];s+=1
   r=max([math.hypot(X/s-x,Y/s-y) for x,y in z]);C={1:A(s-(1.4*r)**2),2:A(s-r*r/3),3:A(s-math.pi*r*r),4:A(s-2.5*r*r)}
   for p in z:
    Q[p]=min(C,key=C.get)
I.putpalette([0,0,0,_]*3+[_,_,0])
I.show()

```

# Answer
> 1 votes
**C# 1086 bytes**

Yet another floodfill-solution, just for the record since there is no C# version here. Like Quincunx i wanted to prove myself that I can do it and there is not much differnce to his approach in Java.

* This solution does not use any recursion (but a stack) because i kept running into StackOverflows.
* The detection of borderpixels is simplified by looking at the 4 next pixels, if any of those is black, the current is a border pixel.

It accepts every imageformat.

* Parameter 1 = InputPath
* Parameter 2 = OutputPath

It probably can be stripped down a few charachters by removing all the static stuff and creating an instance of Program.

Readable Version:

```
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Drawing.Imaging;
using System.Linq;

class Program
{
    static Bitmap img;
    static int w, h;
    static ISet<Point> pointsDone = new HashSet<Point>();
    static void Main(string[] a)
    {
        img = new Bitmap(a[0]);
        w = img.Width;
        h = img.Height;
        Bitmap clone = new Bitmap(w,h, PixelFormat.Format32bppArgb);
        Graphics.FromImage(clone).DrawImage(img, 0, 0, w, h);
        img = clone;

        Color[] colors = new[] { Color.Blue, Color.Red, Color.Green, Color.Yellow };

        var shapes = new List<ISet<Tuple<bool, Point>>>();
        for(int x=0;x<w;x++)
            for (int y = 0; y < h; y++)
            {
                Point p = new Point(x, y);
                if (pointsDone.Add(p) && _isWhitePixel(p))
                    shapes.Add(_detectShape(p));
            }
        int index = 0;
        foreach (var shp in shapes.OrderBy(shp => shp.Count(item => item.Item1)))
        {
            foreach (var pixel in shp)
                img.SetPixel(pixel.Item2.X, pixel.Item2.Y, colors[index]);
            index++;
        }

        img.Save(a[1]);
    }

    private static ISet<Tuple<bool, Point>> _detectShape(Point p)
    {
        var todo = new Stack<Point>(new[] { p });
        var shape = new HashSet<Tuple<bool, Point>>();
        do
        {
            p = todo.Pop();
            var isBorderPixel = false;
            foreach (var n in new[] { new Point(p.X + 1, p.Y), new Point(p.X - 1, p.Y), new Point(p.X, p.Y + 1), new Point(p.X, p.Y - 1) })
                if (_isWhitePixel(n))
                {
                    if (pointsDone.Add(n))
                        todo.Push(n);
                }
                else isBorderPixel = true; // We know we are at the border of the shape
            shape.Add(Tuple.Create(isBorderPixel, p));

        } while (todo.Count > 0);
        return shape;
    }

    static bool _isWhitePixel(Point p)
    {
        return img.GetPixel(p.X, p.Y).ToArgb() == Color.White.ToArgb();
    }
}

```

Golfed:

```
using System;using System.Collections.Generic;using System.Drawing;using System.Drawing.Imaging;using System.Linq;class P{static Bitmap a;static int w,h;static ISet<Point> d=new HashSet<Point>();static void Main(string[] q){a=new Bitmap(q[0]);w=a.Width;h=a.Height;var c=new Bitmap(w,h,PixelFormat.Format32bppArgb);Graphics.FromImage(c).DrawImage(a,0,0,w,h);a=c;var e=new[]{Color.Blue,Color.Red,Color.Green,Color.Yellow};var f=new List<ISet<dynamic>>();for(int x=0;x<w;x++)for(int y=0;y<h;y++){Point p=new Point(x,y);if (d.Add(p)&&v(p))f.Add(u(p));}int i=0;foreach(var s in f.OrderBy(s=>s.Count(item=>item.b))){foreach(var x in s)a.SetPixel(x.p.X,x.p.Y,e[i]);i++;}a.Save(q[1]);}private static ISet<dynamic> u(Point p){var t=new Stack<Point>(new[]{p});var s=new HashSet<dynamic>();do{p=t.Pop();var b=false;foreach(var n in new[]{new Point(p.X+1,p.Y),new Point(p.X-1,p.Y),new Point(p.X,p.Y+1),new Point(p.X,p.Y-1)})if(v(n)){if (d.Add(n))t.Push(n);}else b=true;s.Add(new{b,p});}while (t.Count>0);return s;}static bool v(Point p){return a.GetPixel(p.X,p.Y).ToArgb()==Color.White.ToArgb();}}

```

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


title: Implement a Variable Length Hash

text:
# Question
Title: Implement a Variable Length Hash
My friend and I have this game that we play with words. It is a fun pastime and it involves "canceling out" letters in a word until there is nothing left. I am really tired of him being so much faster than me at it, so it is *your* job to implement it and let me finally beat him. Obviously, since I have to make the program as easy to hide as possible, it has to be small as possible.

## How does this game work?

The game is a pretty simple algorithm. It reduces a alphabetical string until it can't be reduced any further, thus making it a sort of hash. The actual game that we humans do is very hard to implement, but it can be simplified into the following algorithm:

You start by folding the alphabet in half and lining up the two pieces like such:

```
a b c d e f g h i j k l m
z y x w v u t s r p q o n

```

Then, starting from the middle, you assign the positive integers to the top half and the negative to the bottom:

```
a  b  c  d  e f g h i j k l m
13 12 11 10 9 8 7 6 5 4 3 2 1

z   y   x   w   v  u  t  s  r  p  q  o  n
-13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1

```

Then you take your string (we will be using `hello world`) and ignoring any non-alphabetical characters, translate it:

```
h e l l  o w   o  r  l d
6 9 2 2 -2 -10 -2 -5 2 10

```

Then you sum the letter values. The ones that lined up in the earlier diagram (e.g. `d` and `w`, `l` and `o`) will cancel out, while the others will add up.

```
sum(6 9 2 2 -2 -10 -2 -5 2 10 )=12

```

12 is the number for `b`, so the hash of `hello world` is `b`

For a word that completely cancels out (e.g. `love`), you output the "0 character": `-`. Note that in the input, `-` will still be disregarded. It only matters in the output.

If the number's magnitude is larger than 13, then you start doubling up on the `a`'s and the `z`'s You basically take as many `a`'s or `z`'s fit into the number and take whatever is left into the last letter like so:

```
code golf: 43.

```

Fits 3 `a`'s and has 4 left over:

```
aaa 4: j
result: aaaj

```

Hint: This part is basically `divmod` except that it rounds toward zero, not `-infinity` (e.g. -43 would become 3 `z`'s and and a `-4` which is `p` so `zzzp`).

Note: the dash does not come if the `a`'s or `z`'s fit in perfectly, only if it is exactly `0`.

## Clarifications:

* The hash is case **in**sensitive
* Standard Loopholes are not allowed
* I/O can be in any format that isn't too outlandish, stdin, stdout, command-line arg, function, etc.
* This is so shortest size in **bytes** wins.

## Examples:

```
hello world  -->  b

love  -->  -

this is an example -->  aak

hello *&*(&(*&%& world  -->  b

good bye --> ae

root users --> zzs

```

# Answer
# Pyth, 79 78 77 65 61 58

```
J+\-GK+0fTr13_14=ZsX@JzJKMe,pk*G/H13%H13@JxK?g\aZ>Z0_g\z_Z

```
> 4 votes

# Answer
# CJam, 46 bytes

Try it online, or try the test suite online.

```
lel{'n-_W>+_zE<*}%:+{_De<C~e>___0>-'n+'-?o-}h;

```

### Explanation

The algorithm works how you might expect: read the input, convert to lowercase, map each character to a value, sum the values, and print characters and adjust the sum accordingly until the sum is zero. Probably the most interesting optimization (although it only saves two bytes) is that negated character mappings are used instead, as this avoids swapping subtraction arguments to correct the sign when computing the mapped value and avoids swapping again when mapping back to a letter due to the subtraction of a negated value being replaceable by addition.

```
lel             "Read a line of input and convert all letters to lowercase.";
{               "Map each character:";
  'n-_W>+         "Map each character to its negated value by subtracting 'n'
                   and incrementing if the result is nonnegative.";
  _zE<*           "If the value is out of the letter range, use 0 instead.";
}%
:+              "Compute the sum of the mapped character values.";
{               "Do...";
  _De<C~e>        "Compute the sum clamped to the letter range.";
  __              "If the clamped sum is nonzero, ...";
  _0>-'n+         "... then produce the clamped sum mapped back to a letter by
                     decrementing if it is positive and adding 'n', ...";
  '-              "... else produce '-'.";
  ?
  o               "Output the character produced above.";
  -               "Subtract the clamped sum out of the sum.";
}h              "... while the sum is nonzero.";
;               "Clean up.";

```
> 4 votes

# Answer
# Clip 10, 87

```
Fr+`m[y?cAyg#Ay-v,-RRZ]0]}m.U`[Fx?x?<x0,:-/xR'z*m'm%xR!!%xR],:/xR'a*m'n%xR!!%xR]]'-[R13

```
> 2 votes

# Answer
# R, 258 bytes

```
function(s){a=13;r=data.frame;z=strsplit(gsub("[^a-z]","",tolower(s)),"")[[1]];d=r(l=rev(letters),h=c(-1*a:1,1:a));m=merge(r(l=z),d);n=sum(m$h);q=abs(n);v=rep(ifelse(n>0,"a","z"),q%/%a);paste0(paste(v,collapse=""),d$l[d$h==sign(n)*q%%a],ifelse(n==0,"-",""))}

```

This has to be the grossest R code ever. I figured R might be a decent choice since it has a vector of all letters "a" through "z" as a built-in global variable. But it turns out the rest is a mess.

Ungolfed + explanation:

```
function(s) {
    a <- 13              # Store the value associated with a
    r <- data.frame      # Store the `data.frame` function

    # Split the input into a vector, ignoring case and non-letters
    z <- strsplit(gsub("[^a-z]", "", tolower(s)), "")[[1]]

    # Create a data frame where the first column is the letters
    # z through a and the second is the associated scores
    d <- data.frame(l=reverse(letters), h=c(-1*a:1, 1:a))

    # Merge the split vector with the data frame of scores
    m <- merge(data.frame(l=z), d)

    # Get the total score for the input
    n <- sum(m$h)
    q <- abs(n)

    # Pad the output with a or z as necessary
    v <- rep(ifelse(n > 0, "a", "z"), q %/% a)

    # Collapse the vector of a's or z's into a string
    out1 <- paste(v, collapse="")

    # Look up the letter associated with remainder
    out2 <- d$l[d$h == sign(n)*q%%a]

    # If n = 0, we still want a dash
    out3 <- ifelse(n == 0, "-", "")

    # Return the concatenation of all pieces of the output
    paste0(out1, out2, out3)
}

```

This creates an unnamed function object that accepts a string as input and returns the associated hash value. To call it, give it a name, e.g. `f=function(s){...}`.

Examples:

```
> f("this is an example")
[1] "aak"

> f("root users")
[1] "zzs"

> f("love")
[1] "-"

> f("People like grapes.")
[1] "aaag"

```

Try it online!

Questions? I'll happily provide any further explanation. Suggestions? Suggestions are more than welcome!
> 1 votes

# Answer
# Haskell, 171 bytes

```
import Data.Char
m=13
l=zip['a'..'z'][-i|i<-[-m..m],i/=0]
p 0="-"
p n|n>m='a':p(n-m)|n<(-m)='z':p(n+m)|1<2=[c|(c,i)<-l,i==n]
f n=p$sum[y|Just y<-[lookup(toLower x)l|x<-n]]

```

Test run:

```
> map f ["hello world", "love", "this is an example", "hello *&*(&(*&%& world", "good bye", "root users"]
["b","-","aak","b","ae","zzs"]

```

How it works: `l` is a lookup table from letters to the corresponding value. Lookup all characters from the input string and discard those not found. Sum the resulting list. Depending on the sum `p` prints `-` or maybe first some `a`s or `z`s and finally (reverse-)lookups the letter from `l`.
> 1 votes

# Answer
# R - 200

```
function(s){l=letters
N=setNames
x=strsplit(tolower(s),'')[[1]]
n=(13:-13)[-14]
v=sum(N(n,l)[x[x%in%l]])
o=''
while(v){d=min(max(v,-13),13)
o=paste0(o,N(l,n)[as.character(d)])
v=v-d}
if(o=='')o='-'
o}

```
> 1 votes

---
Tags: code-golf, string, hashing
---