title: Write the fastest Fibonacci

text:
# Question
Title: Write the fastest Fibonacci
This is yet another challenge about the Fibonacci numbers.

The goal is to compute the 20'000'000th Fibonacii number as fast as possible. The decimal output is about 4 MiB large; it starts with:

> 28543982899108793710435526490684533031144309848579

The MD5 sum of the output is

> fa831ff5dd57a830792d8ded4c24c2cb

You have to submit a program that calculates the number while running and puts the result to `stdout`. The fastest program, as measured on my own machine, wins.

Here are some additional rules:

* You have to submit the source code and a binary runnable on an x64 Linux
* The source code must be shorter than 1 MiB, in case of assembly it is also acceptable if only the binary is that small.
* You must not include the number to be computed in your binary, even in a disguised fashion. The number has to be calculated at runtime.
* My computer has two cores; you are allowed to use parallelism

I took a small implementation from the Internet which runs in about 4.5 seconds. It should not be very difficult to beat this, assuming that you have a good algorithm.

# Answer
> 4 votes
**C with GMP, 3.6s**

Gods, but GMP makes code ugly. With a Karatsuba-style trick, I managed to cut down to 2 multiplies per doubling step. Now that I'm reading FUZxxl's solution, I'm not the first to have the idea. I've got a couple more tricks up my sleeve... maybe I'll try 'em out later on.

```
#include <gmp.h>
#include <stdio.h>

#define DBL mpz_mul_2exp(u,a,1);mpz_mul_2exp(v,b,1);mpz_add(u,u,b);mpz_sub(v,a,v);mpz_mul(b,u,b);mpz_mul(a,v,a);mpz_add(a,b,a);
#define ADD mpz_add(a,a,b);mpz_swap(a,b);

int main(){
    mpz_t a,b,u,v;
    mpz_init(a);mpz_set_ui(a,0);
    mpz_init(b);mpz_set_ui(b,1);
    mpz_init(u);
    mpz_init(v);

    DBL
    DBL
    DBL ADD
    DBL ADD
    DBL
    DBL
    DBL
    DBL ADD
    DBL
    DBL
    DBL ADD
    DBL
    DBL ADD
    DBL ADD
    DBL
    DBL ADD
    DBL
    DBL
    DBL
    DBL
    DBL
    DBL
    DBL
    DBL /*Comment this line out for F(10M)*/

    mpz_out_str(stdout,10,b);
    printf("\n");
}

```

Built with `gcc -O3 m.c -o m -lgmp`.

# Answer
> 11 votes
**Sage**

Hmm, you seem to assume that the fastest is going to be a compiled program. No binary for you!

```
print fibonacci(2000000)

```

On my machine, it takes 0.10 cpu seconds, 0.15 wall seconds.

edit: timed on the console, instead of the notebook

# Answer
> 5 votes
**Haskell**

This is my own try, although I did not wrote the algorithm by myself. I rather copied it from haskell.org and adapted it to use `Data.Vector` with its famous stream fusion:

```
import Data.Vector as V
import Data.Bits

main :: IO ()
main = print $ fib 20000000

fib :: Int -> Integer
fib n = snd . V.foldl' fib' (1,0) . V.dropWhile not $ V.map (testBit n) $ V.enumFromStepN (s-1) (-1) s
    where
        s = bitSize n
        fib' (f,g) p
            | p         = (f*(f+2*g),ss)
            | otherwise = (ss,g*(2*f-g))
            where ss = f*f+g*g

```

This takes around 4.5 seconds when compiled with GHC 7.0.3 and the following flags:

```
ghc -O3 -fllvm fib.hs

```

# Answer
> 4 votes
## COW

```
 MoO moO MoO mOo MOO OOM MMM moO moO
 MMM mOo mOo moO MMM mOo MMM moO moO
 MOO MOo mOo MoO moO moo mOo mOo moo

```

Moo! (Takes a while. Drink some milk...)

# Answer
> 2 votes
Mathematica, interpreted:

```
First@Timing[Fibonacci[2 10^6]]

```

Timed:

```
0.032 secs on my poor man's laptop.

```

And of course, no binary.

# Answer
> 2 votes
# Ocaml, 0.856s on my laptop

Requires the zarith library. I used Big\_int but it's dog slow compared to zarith. It took 10 minutes with the same code! Most of the time was spent *printing* the damn number (9½ minutes or so)!

```
module M = Map.Make
  (struct
    type t = int
    let compare = compare
   end)

let double b = Z.shift_left b 1
let ( +. ) b1 b2 = Z.add b1 b2
let ( *. ) b1 b2 = Z.mul b1 b2

let cache = ref M.empty
let rec fib_log n =
  if n = 0
  then Z.zero
  else if n = 1
  then Z.one
  else if n mod 2 = 0
  then
    let f_n_half = fib_log_cached (n/2)
    and f_n_half_minus_one = fib_log_cached (n/2-1)
    in f_n_half *. (f_n_half +. double f_n_half_minus_one)
  else
    let f_n_half = fib_log_cached (n/2)
    and f_n_half_plus_one = fib_log_cached (n/2+1)
    in (f_n_half *. f_n_half) +.
    (f_n_half_plus_one *. f_n_half_plus_one)
and fib_log_cached n =
    try M.find n !cache
    with Not_found ->
      let res = fib_log n
      in cache := M.add n res !cache;
      res

let () =
  let res = fib_log 20_000_000 in
  Z.print res; print_newline ()

```

I can't believe how much a difference the library made!

# Answer
> 1 votes
## Haskell

On my system, this runs almost as fast as FUZxxl's answer (~18 seconds instead of ~17 seconds).

```
main = print $ fst $ fib2 20000000

-- | fib2: Compute (fib n, fib (n+1)).
--
-- Having two adjacent Fibonacci numbers lets us
-- traverse up or down the series efficiently.
fib2 :: Int -> (Integer, Integer)

-- Guard against negative n.
fib2 n | n < 0 = error "fib2: negative index"

-- Start with a few base cases.
fib2 0 = (0, 1)
fib2 1 = (1, 1)
fib2 2 = (1, 2)
fib2 3 = (2, 3)

-- For larger numbers, derive fib2 n from fib2 (n `div` 2)
-- This takes advantage of the following identity:
--
--    fib(n) = fib(k)*fib(n-k-1) + fib(k+1)*fib(n-k)
--             where n > k
--               and k ≥ 0.
--
fib2 n =
    let (a, b) = fib2 (n `div` 2)
     in if even n
        then ((b-a)*a + a*b, a*a + b*b)
        else (a*a + b*b, a*b + b*(a+b))

```

# Answer
> 1 votes
## C, naive algorithm

Was curious, and I hadn't used gmp before... so:

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

int main(int argc, char *argv[]){
    int n = (argc>1)?atoi(argv[1]):0;

    mpz_t temp,prev,result;
    mpz_init(temp);
    mpz_init_set_ui(prev, 0);
    mpz_init_set_ui(result, 1);

    for(int i = 2; i <= n; i++) {
        mpz_add(temp, result, prev);
        mpz_swap(temp, result);
        mpz_swap(temp, prev);
    }

    printf("fib(%d) = %s\n", n, mpz_get_str (NULL, 10, result));

    return 0;
}

```

fib(1 million) takes about 7secs... so this algorithm won't win the race.

# Answer
> 1 votes
I implemented the matrix multiplication method (from sicp, http://sicp.org.ua/sicp/Exercise1-19) in SBCL but it takes about 30 seconds to finish. I ported it to C using GMP, and it returns the correct result in about 1.36 seconds on my machine. It's about as fast as boothby's answer.

```
#include <gmp.h>
#include <stdio.h>

int main()
{
  int n = 20000000;

  mpz_t a, b, p, q, psq, qsq, twopq, bq, aq, ap, bp;
  int count = n;

  mpz_init_set_si(a, 1);
  mpz_init_set_si(b, 0);
  mpz_init_set_si(p, 0);
  mpz_init_set_si(q, 1);
  mpz_init(psq);
  mpz_init(qsq);
  mpz_init(twopq);
  mpz_init(bq);
  mpz_init(aq);
  mpz_init(ap);
  mpz_init(bp);

  while(count > 0)
    {
      if ((count % 2) == 0)
        {
          mpz_mul(psq, p, p);
          mpz_mul(qsq, q, q);
          mpz_mul(twopq, p, q);
          mpz_mul_si(twopq, twopq, 2);

          mpz_add(p, psq, qsq);    // p -> (p * p) + (q * q)
          mpz_add(q, twopq, qsq);  // q -> (2 * p * q) + (q * q)
          count/=2;
        }

      else
       {
          mpz_mul(bq, b, q);
          mpz_mul(aq, a, q);
          mpz_mul(ap, a, p);
          mpz_mul(bp, b, p);

          mpz_add(a, bq, aq);      // a -> (b * q) + (a * q)
          mpz_add(a, a, ap);       //              + (a * p)

          mpz_add(b, bp, aq);      // b -> (b * p) + (a * q)

          count--;
       }

    }

  gmp_printf("%Zd\n", b);
  return 0;
}

```

# Answer
> 1 votes
## Java: 8 seconds to compute, 18 seconds to write

```
public static BigInteger fibonacci1(int n) {
    if (n < 0) explode("non-negative please");
    short charPos = 32;
    boolean[] buf = new boolean[32];
    do {
        buf[--charPos] = (n & 1) == 1;
        n >>>= 1;
    } while (n != 0);
    BigInteger a = BigInteger.ZERO;
    BigInteger b = BigInteger.ONE;
    BigInteger temp;
    do {
        if (buf[charPos++]) {
            temp = b.multiply(b).add(a.multiply(a));
            b = b.multiply(a.shiftLeft(1).add(b));
            a = temp;
        } else {
            temp = b.multiply(b).add(a.multiply(a));
            a = a.multiply(b.shiftLeft(1).subtract(a));
            b = temp;
        }
    } while (charPos < 32);
    return a;
}

public static void main(String[] args) {
    BigInteger f;
    f = fibonacci1(20000000);
    // about 8 seconds
    System.out.println(f.toString());
    // about 18 seconds
}

```

# Answer
> 0 votes
# Go

It's embarrasingly slow. On my computer it takes a little less than 3 minutes. It's only 120 recursive calls, though (after adding the cache). Note that this may use a lot of memory (like 1.4 GiB)!

```
package main

import (
    "math/big"
    "fmt"
)

var cache = make(map[int64] *big.Int)

func fib_log_cache(n int64) *big.Int {
    if res, ok := cache[n]; ok {
        return res
    }
    res := fib_log(n)
    cache[n] = res
    return res
}

func fib_log(n int64) *big.Int {
    if n <= 1 {
        return big.NewInt(n)
    }

    if n % 2 == 0 {
        f_n_half := fib_log_cache(n/2)
        f_n_half_minus_one := fib_log_cache(n/2-1)
        res := new(big.Int).Lsh(f_n_half_minus_one, 1)
        res.Add(f_n_half, res)
        res.Mul(f_n_half, res)
        return res
    }
    f_n_half := fib_log_cache(n/2)
    f_n_half_plus_one := fib_log_cache(n/2+1)
    res := new(big.Int).Mul(f_n_half_plus_one, f_n_half_plus_one)
    tmp := new(big.Int).Mul(f_n_half, f_n_half)
    res.Add(res, tmp)
    return res
}

func main() {
    fmt.Println(fib_log(20000000))
}

```

---
Tags: fastest-code, fibonacci
---


title: Complete a Tournament Bracket

text:
# Question
Title: Complete a Tournament Bracket
Your task is to create a program which outputs a completed tournament bracket given a list of entrants, their seeds, and their scores in each game; in the fewest characters possible.

**Input**

Your entrants will have the following data. You can organize your data in whatever form you like, but you *cannot* pre-sort your array or do any other pre-processing. The scores represent an entrant's score in each round, in other words they determine who moves on to the next round.

```
Example Input #1
[   {name: "James",         seed: 1,    scores: [12, 6,]}
,   {name: "Sarah",         seed: 4,    scores: [1, 16]}
,   {name: "Andre 3000",    seed: 3,    scores: [3000, 3000]}
,   {name: "Kim",           seed: 2,    scores: [20, 4]}
]

Example Input #2
[   {name: "Andy",  seed: 1,    scores: [1, 8, 4]}
,   {name: "Kate",  seed: 4,    scores: [1, 1, 8]}
,   {name: "Steve", seed: 3,    scores: [30, 1, 0]}
,   {name: "Linda", seed: 5,    scores: [4, 4, 5]}
,   {name: "Kyle",  seed: 2,    scores: [21, 0, 18]}
]

```

**Output**

Your output should resemble the examples below, and must follow these rules:

1. For each round in the tournament, the entrants are paired up and those pairs are output.
2. In the event of an odd entrant count, your program must account for and output byes. The entrant who gets the bye is the entrant who has been given the fewest bye weeks so far, and in the event of a tie, the best seed (1 is the best).
3. Pairing is based on the seed. Excluding byes, the best seed (1 is the best) is paired with the worst, the next best is paired with the next worst seed, etc.
4. The best seeds should be first in the pair, and at the top of the bracket.
5. The tournament champion should be output.

.

```
Example Output #1 (for input #1)
Round 1
James vs Sarah
Kim vs Andre 3000
Round 2
James vs Andre 3000
Champion
Andre 3000

Example Output #2 (for input #2)
Round 1
Kyle vs Linda
Steve vs Kate
Andy BYE
Round 2
Andy vs Steve
Kyle BYE
Round 3
Andy vs Kyle
Champion
Kyle

```

Extra props for anyone who codes a separate version of their program which prints an actual bracket.

**Scoring**

Assume input is correct, standard loopholes, etc and so forth. This is code golf, so fewest bytes win. In the event of a tie, most votes win. Good luck!

# Answer
# CJam, ~~156 151~~ 144 bytes

```
q~0f+{{1=}$_,2%{{W=}$())+aa\{1=}$\}L?\_,2//)W%a+z\+_{0f=_,1={~" BYE"+a}*" vs "*N\}%"Round "U):U+\+\{{2=0=}$W=_2=(;2\t}%_W=2=}g~0=a"Champion"\]N*

```

This can definitely be golfed further.

The input is in an array of array format, like:

```
[["James" 1 [12 6 15]] ["Sarah" 4 [3 2 5]] ["Franko" 2 [20 1 5]] ["Max" 5 [22 10 7]] ["Arthur" 3 [20 15 20]]]

```

where each array element is the detail about the user in `[name seed score_array]` format

The output for the above input is:

```
Round 1
Franko vs Max
Arthur vs Sarah
James BYE
Round 2
James vs Max
Arthur BYE
Round 3
Arthur vs Max
Champion
Arthur

```

Try it online here
> 4 votes

---
Tags: code-golf
---


title: Reverse the Polarity

text:
# Question
Title: Reverse the Polarity
The aim of this challenge is to write a program that satisfies the following conditions:

* The program is not palindromic, or essentially palindromic (meaning that it is possible to remove characters to make it a palindrome without changing the effects of the program).
* The program is not an involution (meaning that it does not produce its original input when run on its output)
* The **reversed-polarity** program is the inverse of the normal program; so when the reversed program is run on the output of the normal program, it returns the original input.

What does **reversed-polarity** mean? Well, it differs between languages.

* For most non-esolangs, this means reversing the order of sub-operations in a single operation, reversing the order of arguments, and reversing the contents of hard-coded lists/arrays/tuples/dictionaries/stacks/queues/etc, as well as reversing the order of code-blocks and stand-alone lines (but not lines within blocks)

Examples:

**Haskell**: `x`mod`y` -\> `y`mod`x`;`zipWith ((*3).(+)) [1,2,3] [4,5,6]` -\> `zipWith ((+).(*3)) [6,5,4] [3,2,1]`

**Python**: `2**3` -\> `3**2`; `for x,y in [(1,2),(3,4),(5,6)]` -\> `for y,x in [(6,5),(4,3),(2,1)]`

* For languages that have 1-character functions (like Pyth, APL), simply reverse the string of instructions
* For 1-dimensional esolangs like BF, reverse the instructions **or** swap the polarity; polarity swaps are `[]` -\> `{}`, `+` -\> `-`, `-` -\> `+`, `>` -\> `<`, `<` -\> `>`, `.` -\> `,` and `,` -\> `.` (but not both)
* For 2-dimensional esolangs like Befunge, you may either perform a reflection across the x- or y- axes or a diagonal, rotate 180 degrees, or do a combination of a reflection and a rotation

Commutative operations are allowed, but palindromic ones are not: `2*x` is fine, but `x+x` is bad. The definition of a polarity-reversal is pretty loose, but use your judgment as to what makes sense; the object isn't to find the most clever loophole, but to find the most clever solution.

This is a popularity contest, so a very clever loophole may be popular, but try to keep within the spirit of this challenge. The winner will be announced once there are at least 10 solutions with at least 1 upvote, and there is at least one solution with more upvotes than there are submissions with at least 1 upvote; or in 1 month, whichever comes first. This is my first challenge, so try to be fair and give me constructive feedback, but also let me know if this is an unreasonable challenge or it is in any way miscategorized or ambiguous. If you have questions about a language that don't fit into any of the pigeonholes I have set out here, comment, and I will bend to the will of the community if there is a strong outcry for a particular clarification or rule-change.

# UPDATE

It has been exactly 1 month since this contest was started (I just happened to check on it by chance, not knowing that I was actually on time). As this is a popularity contest, the winner (by a landslide) is Pietu1998-Befunge. Even though the bottom components (the text reverser and the backwards-alphabet) are both involutions, the encoder/decoder are not, so there is no problem there. Bonus points (in my mind) for managing to write "BEFUNGE" down the middle. I personally liked the novelty of Zgarb's Theseus solution, because the language looks cool (if restricted). Thanks to everyone for participating, and while the winner has been chosen, I am leaving this contest completely open, and welcome future submissions.

# Answer
> 41 votes
# Befunge

Whoa, that was a job, even with the editor I made for this challenge. Here's what I got, a nice 11x12 block:

```
v$,g6<6g,$v
v,$ _^_ $,v
1W>v\B\v>L1
~T+:1E1:-O~
+F00-F-02L+
>:|6gUg6|:>
{a@>^N^>@z`
>1+|@G$| +>
:^9< E<  ^1
~>7^@_,#:>:
 xD>65 ^=P~
v,-\+**<  v

```

It does a couple of things, sadly only for lowercase letters.

## What it does

When run normally, it performs a Caesar cipher on the input.

```
abcxyz      -> bcdyza
exampletext -> fybnqmfufyu

```

When flipped horizontally, it reverses said cipher. This is the requirement for the challenge, but it doesn't end here.

```
bcdyza      -> abcxyz
fybnqmfufyu -> exampletext

```

When flipped *vertically*, it ciphers input with a reverse alphabet. This can be considered the opposite approach to the Caesar cipher.

```
abcxyz      -> zyxcba
exampletext -> vcznkovgvcg

```

Finally, when rotated 180 degrees, it reverses input. I have a feeling it has to be a reverse of something (hint: the input).

```
abcxyz      -> zyxcba
exampletext -> txetelpmaxe

```

## How it works

The block basically consists of four semi-overlapping algorithms.

### Caesar cipher encoder

```
v$,g6<
v,$ _^
1 >v\
~ +:1
+ 00-
>:|6g
{a@>^

```

### Caesar cipher decoder (flipped horizontally)

```
v$,g6<
v,$ _^
1 >v\
~ -:1
+ 20-
>:|6g
`z@>^

```

### Reverse alphabet cipher (flipped vertically)

```
v,-\+**<
   >65 ^
~>7^
:^9<
>1+|@
   >^

```

### Text reverser (rotated 180 degrees)

```
v  <
~
:>:#,_@
1^  <
>+ |$
   >^

```

# Answer
> 18 votes
# Brainfuck, 5

```
,+.-,

```

Possibly for the first time ever, Brainfuck produces an answer that is competitive on code length. Shame it's not a code-golf question.

Inputs a byte (character) , increments it, and outputs the result. The comma at the end is waiting for another input, which if given will be ignored. There is nothing in the spec about proper termination :-)\*

\*(or about doing something useful with all the code in both directions)

**Typical results (second character if given is ignored).**

Forward: `B` --\> `C`

Reverse: `B` --\> `A` or `C` --\> `B`

# Answer
> 11 votes
# Marbelous

Here is a simple one to start us off. It reads one character from STDIN, increments and prints it.

```
--
]]
00
]]
++

```

If we rotate this by 180° (without swapping brackets), or mirror it in the x-axis, we get

```
++
]]
00
]]
--

```

which reads a byte from STDIN and decrements it.

You can test it here.

I might look into some more complicated Marbelous programs, but I'm sure es1024 will beat me to it. ;)

## Explanation

The `00` is a marble with value 0 (which is arbitrary). The `]]` devices read a byte from STDIN - that is, if a marble falls through them, the marble's value is changed into the read byte. The `++` and `--` devices simply increment or decrement a marble's value (mod 256) and let it fall through. When a marble falls off the board, the byte is written to STDOUT.

Therefore, the two devices at the top are simply ignore because control flow never reaches them.

# Answer
> 5 votes
# Marbelous

This board takes one argument (`x`) and returns `(101 * x) mod 256`.

```
.. @5 .. }0 }0 @1 .. @0 .. @2 ..
.. /\ Dp << \\ .. &0 >0 &1 .. ..
!! @3 .. << }0 .. \/ -- \/ .. }0
@4 .. .. &0 @1 /\ &0 65 &1 /\ @2
/\ Dp .. @4 .. .. @3 @0 @5 !! \\

```

Mirroring the **cells** along the y-axis will result in a board that takes one argument (`y`) and returns `(101 * y + 8 * y) mod 256`, which is the inverse of the first board.

```
.. @2 .. @0 .. @1 }0 }0 .. @5 ..
.. .. &1 >0 &0 .. \\ << Dp /\ ..
}0 .. \/ -- \/ .. }0 << .. @3 !!
@2 /\ &1 65 &0 /\ @1 &0 .. .. @4
\\ !! @5 @0 @3 .. .. @4 .. Dp /\

```

Test this here. Cylindrical boards and Include libraries should both be checked.

**Example input/output**:

```
Original Board:      Mirrored Board:
Input   Output       Input    Output
025     221          221      025
042     146          146      042
226     042          042      226

```

Please note that Marbelous only allows for passing of positive integers as arguments, and these integers are passed into the program modulo 256 by the interpreter.

`101` was chosen for two reasons: it is a prime (and every possible input to this program results in a unique output), and the inverse operation involved `109`, which is a convenient distance of 8 away from `101`.

## Brief Explanation

The column containing the cells (from top to bottom) `@0 >0 -- 65 @0` runs the same in both boards, and loops `101` times before heading to the right. On either side of the `>0` branch is a different synchroniser; which one is chosen depends on whether the board is mirrored or not.

On each side, in sync with the center loop, the input is repeatedly summed, thus obtaining `101*x mod 256`. On the reversed board, two copies of the input are also bit shifted twice to the left (`input * 4`), then summed and left in a synchroniser.

Once the center loop finishes, the summed up marbles are sent for printing, which is on the side of the board (left for original board, right for mirrored). After printing, a `!!` cell is reached, terminating the board. Note that the loop that gave `101 * x` continues to run by itself until the board is terminated.

`Dp` simply prints out the result as a decimal number.

# Answer
> 5 votes
# Theseus

This may be considered as a loophole, but I like the language, so here goes. This program defines a function `f` on natural numbers that maps *3n* to *3n+1*, *3n+1* to *3n+2*, and *3n+2* to *3n*, for every *n*.

```
data Num = Zero | Succ Num

iso f :: Num <-> Num
  | n                          <-> iter $ Zero, n
  | iter $ m, Succ Succ Succ n <-> iter $ Succ m, n
  | iter $ m, Succ Succ Zero   <-> back $ m, Zero
  | iter $ m, Succ Zero        <-> back $ m, Succ Succ Zero
  | iter $ m, Zero             <-> back $ m, Succ Zero
  | back $ Succ m, n           <-> back $ m, Succ Succ Succ n
  | back $ Zero, n             <-> n
  where iter :: Num * Num
        back :: Num * Num

```

Theseus is a reversible language with a Haskell-like syntax, where every function is invertible (discounting issues with non-termination). It is highly experimental, and designed for research purposes. The above code defines a datatype for natural numbers, and the function `f`. Given an input number, you pattern-match to it on the left-hand side (it always matches `n`). Then you look at the pattern on the right. If that pattern has a label (here `iter`), you proceed to pattern-match it on the left-hand side, and again take the corresponding value on the right-hand side. This repeats until you have an unlabeled value on the right, and that is your output. The patterns on the left, and on the right, must be exhaustive and non-overlapping (separately for each label). Now, to "reverse the polarity" of `f`, I do the following.

* Swap the two values of every label. This does not change the semantics of `f`.
* Swap the right- and left-hand-sides in the function body. This defines the inverse function of `f` *by design*.

The result:

```
iso f :: Num <-> Num
  | iter $ n, Zero             <-> n
  | iter $ n, Succ m           <-> iter $ Succ Succ Succ n, m
  | back $ Zero, m             <-> iter $ Succ Succ Zero, m
  | back $ Succ Succ Zero, m   <-> iter $ Succ Zero, m
  | back $ Succ Zero, m        <-> iter $ Zero, m
  | back $ Succ Succ Succ n, m <-> back $ n, Succ m
  | n                          <-> back $ n, Zero
  where iter :: Num * Num
        back :: Num * Num

```

# Answer
> 3 votes
# tr

```
a b

```

**Example:**

```
$ echo "apple" | tr a b
bpple
$ echo "bpple" | tr b a
apple

```

Only a true inverse on the domain of strings that don't include both 'a' and 'b'.

# Answer
> 2 votes
# Another Marbelous answer

The original right shifts the command line input (an 8 bit value), adding a leading one if a 1 gets lost by shifting. (`0000 0001 -> 1000 0000`)

```
{0 ..
~~ ..
>> {0
-2 =0
.. ^0
\/ }0
}0 Sb
<< ..
\\ ..
:Sb
// ..
Sb >>
}0 ..
^7 }0
{0 \/

```

Rotating this board by 180° (but leaving the content of each cell the same) Changes the program so that it left shifts (`1000 0000 -> 0000 0001`)

```
\/ {0
}0 ^7
.. }0
>> Sb
.. //
:Sb
.. \\
.. <<
Sb }0
}0 \/
^0 ..
=0 -2
{0 >>
.. ~~
.. {0

```

You can test it here. (you'll need to turn on 'Display output as decimal numbers')

## Explanation

Both program consist of two boards, the main board (which gets the command line input) and `Sb`. Lets have a look at both versions of the main board, only looking at cells that can be reached in their respective orientation (since marbles typically can't go upwards and the input devices are not at the top):

```
original:      flipped:
   }0          }0
}0 Sb          .. }0
<< ..          >> Sb
\\ ..          .. //

```

Those are pretty straightforward boards, both take two copies of the input (which take the place of the `}0`cells. The original feeds one version into a left shift device `<<` the flipped version puts it in a right shift device `>>` These perform a bitshift but unfortunately discard any lost bits. Which is where the `Sb` boards come in, they check if bitshifting the value they're fed will result in a bit being lost and return a value to be added to the result to counteract the lost bit.

Here's the relevant part of the original `Sb`board for the original program:

```
}0
^7
{0

```

This one is incredibly easy, \`^7' checks the value of the most significant bit. If this one is 1, performing a left shift would cause this bit to be lost. So this board outputs the value of this bit as an 8 bit value to be added to the result of the bitshift.

For the flipped version, `Sb`has to look at the least significant bit and return `128` or `0`, this is a little bit more complicated:

```
}0
^0 ..
=0 -2
{0 >>
.. ~~
.. {0

```

If the least significant bit (as tested by `^0`) is 0, it just returns 0. If it is one, `^0` will output `1`. This will fail the equality test with `0` `=0` and thus be push to the right. We then subtract 2 `-2`to get 255, left shift `>>` to get 127 and perform a binary not `~~` to get 128 (we could also simply have added one `++` to get 128, but where's the fun in that?)

---
Tags: popularity-contest
---


# Question
Title: Algorithm for finding a regex for a list of "words"
I just discovered this website and was amazed. Somehow this challenge popped into my mind: Provided a very long list of words; Write or describe an algorithm which finds a regex to match them all.

Ex.: A very long list of Dates, model-numbers, CD-Codes, ISBNs et cetera.

I hope it's not too big or does not belong here. Please refer to downvote in that case but write a comment and I will delete this.

Edit: Sorry at my clumsy attempt. I fear there is not a very sharp goal. Of course .\* is not what I look for :) Here are some specifications:

* It has to match all *words*
* It has to group characters and find out what kind of characters are in that group, e.g. identify that an american date always consits of one to four numbers, then a slash etc.
* It does not need to be able to identify transverses etc
* There is a huge list of not-to-match-examples available as well

Winner is the one who can write a code which does what I described for one of my examples (or a similar one). In case that no code is committed, the winner is the one who can convince me, that the described algorithm *could* work.

# Answer
In Java 8:

```
public class Reg{

    public static void main(String... args){
        System.out.println(args[0].replaceAll(",", "|"));
    }

}

```

Matches only the strings inputed. Expects input to be of form:

goodWord1,goodWord2,goodWord3...(space)badWord1,badWord2,badWord3...

**Edit:** Edited for new requirements. Now accepts a list of bad words also. It also now works in Java 7.
> 2 votes

---
Tags: regular-expression
---


title: Treasure Hunting on a Deserted Island

text:
# Question
Title: Treasure Hunting on a Deserted Island
## Introduction

You are stranded on a deserted island with some servants and are hunting for treasure. The longer one searches, the more treasure one finds. The fewer people searching, the more each person finds.

Due to limited supplies, the leader has decided that a few people, up to a quarter of the group, shall be left to die each night. He has decided not to tell anyone exactly how many people shall die on any given day ahead of time.

You are in control of a small group of 5 people, who shall venture out of camp to find treasure for you.

## Objective

The objective of this competition is to amass as much treasure as possible. Every turn that your servants do not attempt to return to camp, they will find a certain number of pieces of treasure. Your servants may return to camp at different times.

Each turn that a worker stays out to search for treasure, the worker finds `1+R` pieces of treasure, where `R` is the number of workers (out of all the bots) already back in camp. Dead bots do not factor into this calculation.

At the start of each day, a random number (`n`) from `2` to `max(3, floor(num_live_players/4))` will be chosen. (For 10 players on day 1, this is `2` to `max(3,50/4)=12`. For 20 players on day 1, this would be `2` to `max(3,100/4)=25`.) This number represents the number of players who will be left to die for that day, and will not be given to your program.

If a servant is one of the last `n` people to return, he/she will die and be unable to transfer the treasure he/she found to your possession. Furthermore, the servant will be unable to participate in treasure hunting for the rest of the adventure.

Your final score is the average amount of treasure you obtained per adventure (run of the controller).

If more people attempt to return to camp on the same turn than there are open slots, random numbers will determine who gets in and who dies.

A day on this island from sunrise to sunset lasts 30 turns. As there are many dangerous animals at night, failure to return by sunset means that you will not be allowed into the camp.

## Input/Output

Your program should run for the entirety of the simulation.

At the start of the simulation, `INDEX I` will be inputted, where `I` is the index of your bot (this index is counted from 1 up).

At the start of each day, `START_DAY D/N` will be inputted to your program, where `D` is the day number (starting from `1`), and `N` is equal to `max(3, floor(num_live_players/4))`, which is the maximum number of people who may die on that particular day.

At the start of each turn, `START_TURN T` will be inputted to your program, where `T` is the turn number (starting from `1`).

Once your program receives this, it should respond with a list of your servants' moves, each separated by a comma.

Valid moves are:

* `R`: Try to return to camp.
* `S`: Stay looking for treasure.
* `N`: Servant is already dead or in camp.

Entering an invalid move will be interpretted as `S` if the bot is alive and not in camp, and `N` otherwise.

At the end of each turn, a string shall be passed to your program:

```
END_TURN [Turn #] [Bot 1 Moves] [Bot 2 Moves] ...

```

where each bot's servants' moves are separated by commas.

These moves will be one of the following:

* `R`: Successfully returned to camp that turn.
* `r`: Failed to return to camp that turn.
* `S`: Still looking for treasure.
* `D`: Died on an earlier turn.
* `N`: Already back at camp.

Bots and servants remain in the same order throughout the entire simulation.

For example:

```
INDEX 2
....
END_TURN 8 N,N,N,N,N r,r,r,r,D D,D,D,N,R S,D,D,N,D

```

Here, you are the second bot (`r,r,r,r,r`), who tried to return all four servants that are still alive (and unluckily failed on all four). Bot 1's servants are all back in camp. Bot 3 has three dead servants, one more back in camp, and a fifth servant who successfully returned. Bot 4 has one servant who stayed (and will die, as this is the last turn of a day), one servant in camp, and three dead servants.

After each of these strings, unless a string signaling the end of the day has also been outputted (see below), your program is to output your servants' next moves, separated by commas. All servants must be accounted for (with `N` if already in camp, and `D` if already dead). Invalid moves will be treated as `S` if the servant is not already in camp/dead. Example:

```
N,N,S,S,R

```

which means:

```
Servant # | Action
     1    | Do nothing.
     2    | Do nothing.
     3    | Stay put (keep looking for treasure).
     4    | Stay put (keep looking for treasure).
     5    | Try to return to camp.

```

At the end of a day, the following string shall be passed after the last turn's `END` string, informing everyone on who is alive:

```
END_DAY [Day #] [Bot 1 Status] [Bot 2 Status]

```

where the status is a comma separated list of either `A` (alive) or `D` (dead). The following day begins immediately after.

The simulation ends when there are fewer than 6 live servants. Your program will receive the following input at the end of the simulation:

```
EXIT

```

## Rules/Details

* Only on turns where your action is `S` will you find treasure.
* Number of simulations run: **1000 times**
* Your program should not take any more than 1 second to determine moves.
* Your program should not exit early; it will be started exactly once.
* Make sure that the output buffer (if applicable) is flushed after each output.
* **Files may be written to in your bot's folder (`./players/BotName/`). Your bot name is whatever you name your bot, with all non-alphanumeric characters removed and written in CamelCase. Entries may save data between runs of the controller, as runs are done sequentially.**
* Your program must exit after receiving `EXIT`.
* Programs that fail to compile or throw errors or output invalid text (not in the format of 5 characters separated by commas) may be excluded from the competition. A newline must follow each output.
* The controller may be found on GitHub.

***Please include the bot name, language+version, code, and command to compile (if applicable) and run your bot.***

## Example

Text outputted by the program is prefixed here with a `>`. Your program should not output this character.

```
INDEX 2
START_DAY 1/3
START_TURN 1
>S,S,S,S,S
END_TURN 1 S,R,S,S,S S,S,S,S,S
START_TURN 2
>S,S,S,S,S
END_TURN 2 S,N,S,R,S S,S,S,S,S
START_TURN 3
>R,R,S,S,S
END_TURN 3 R,N,R,N,R R,R,S,S,S
START_TURN 4
>N,N,S,S,S
END_TURN 4 N,N,N,N,N N,N,S,S,S
START_TURN 5
>N,N,R,R,R
END_TURN 5 N,N,N,N,N N,N,r,r,R
END_DAY 1 A,A,A,A,A A,A,D,D,A
START_DAY 2/3
START_TURN 1
>S,S,N,S,N
END_TURN 1 R,R,R,R,R S,S,D,D,N
END_DAY 2 A,A,A,A,A D,D,D,D,D
EXIT

```

The scores for the above example are:

```
Bot#    Day 1   Day 2   Total
1       10      0       10
  S1    1+2     0       3
  S2    0       0       0
  S3    1+2     0       3
  S4    1       0       1
  S5    1+2     0       3

2       20      0       20
  S1    1+2     0       3
  S2    1+2     0       3
  S3    0       0       0
  S4    0       0       0
  S5    1+2+3+8 0       14

```

The winner is therefore the player, bot 2. Note that the winner does not have to survive to the absolute end. (Also note that the player could have remained until turn 30 on day 1, since the camp would not be full until the player sent one more bot back).

## Scores

```
Bot               Score
Bob               2939.422
Statisticians     2905.833
Morning Birds     1652.325
Evolved           1578.285
Slow Returners    1224.318
Wandering Fools   1065.908
Randomizers       735.313
Drunkards         0
Plague            0

```

Logs are available on GitHub. Results per each trial are available on this google spreadsheet.

# Answer
# Bob - C++

```
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>

using namespace std;

int compare(int i, int j)
  {
  if (i < j)
    return (-1);
  if (i == j)
    return (0);
  if (i > j)
    return (1);
  }

int main()
  {
  int index;
  int day;
  int turn;
  int slash_index;
  int to_die;
  int num_alive;
  int mine_alive;
  int turn_to_return;
  bool returned;
  string line;
  vector<int> last_returns;
  vector<int> today_returns;

  getline(cin, line);

  if (line.compare(0, 6, "INDEX ") != 0)
    {
    cerr << "INVALID INDEX LINE \"" << line << "\"" << endl;

    return (-1);
    }

  index = atoi(line.substr(6).c_str()) - 1;

  while (1) // Day loop
    {
    getline(cin, line);
    if (line.compare(0, 4, "EXIT") == 0)
      {
      return (0);
      }
    else if (line.compare(0, 9, "START_DAY") != 0 || (slash_index = line.find('/')) == string::npos)
      {
      cerr << "INVALID START_DAY \"" << line << "\"" << endl;
      return (-1);
      }

    day = atoi(line.substr(10, slash_index - 10).c_str());
    to_die = atoi(line.substr(slash_index + 1, line.length() - slash_index - 1).c_str());

    if (day != 1)
      {
      if (to_die > num_alive)
        {
        turn_to_return = 30;
        }
      else
        {
        turn_to_return = last_returns[last_returns.size() - to_die] - 1;
        }
      }

    returned = false;

    for (turn = 1; turn <= 30; ++turn)
      {
      getline(cin, line);

      if (line.compare(0, 4, "EXIT") == 0)
        {
        return (0);
        }
      if (line.compare(0, 7, "END_DAY") == 0)
        {
        goto end_day;
        }
      if (line.compare(0, 10, "START_TURN") != 0)
        {
        cerr << "INVALID START_TURN \"" << line << "\"" << endl;
        }

      if (day == 1)
        {
        switch (compare(turn, 30))
          {
            case -1:
              cout << "S,S,S,S,S" << endl;
              break;

            case 0:
              cout << "R,R,R,R,R" << endl;
              break;

            case 1:
              cout << "N,N,N,N,N" << endl;
              break;
          }
        }
      else
        {
        if (returned)
          {
          cout << "N,N,N,N,N" << endl;
          }
        /*
        else if (num_alive - today_returns.size() < to_die)
          {
          cout << "R,R,R,R,R" << endl;
          returned = true;
          }
        */
        else if (turn >= turn_to_return)
          {
          cout << "R,R,R,R,R" << endl;
          returned = true;
          }
        else
          {
          cout << "S,S,S,S,S" << endl;
          }
        }

      getline(cin, line);

      if (line.compare(0, 4, "EXIT") == 0)
        {
        return (0);
        }
      if (line.compare(0, 8, "END_TURN") != 0)
        {
        cerr << "INVALID END_TURN \"" << line << "\"" << endl;
        }

      stringstream ss(line);
      string item;
      int i = 0;
      while (getline(ss, item, ' '))
        {
        i++;
        if (i > 2 && i - 3 != index)
          {
          int num_to_add = count(item.begin(), item.end(), 'R'); // Add turn to today_returns for each servant that returned
          for (int j = 0; j < num_to_add; j++)
            {
            today_returns.push_back(turn);
            }
          }
        }

      }

    getline(cin, line);

  end_day:

    if (line.compare(0, 4, "EXIT") == 0)
      {
      return (0);
      }
    else if (line.compare(0, 7, "END_DAY") != 0)
      {
      cerr << "INVALID END_DAY \"" << line << "\"" << endl;
      return (-1);
      }

    stringstream ss(line);
    string item;
    int i = 0;
    num_alive = 0;
    while (getline(ss, item, ' '))
      {
      i++;
      if (i > 2 && i - 3 != index)
        {
        num_alive += count(item.begin(), item.end(), 'A');
        }
      else if (i - 3 == index)
        {
        mine_alive = count(item.begin(), item.end(), 'A');
        }
      }

    last_returns = today_returns;
    today_returns.clear();

    }

  return (0);
  }

```

To Compile:

```
g++ -o Bob.exe Bob.cpp

```

To Run:

```
./players/Bob/Bob.exe

```
> 5 votes

# Answer
# Statisticians, Python 3

The statisticians always work together. On the first turn, they return to the camp when two thirds of their opponents have done so. On the subsequent turns, they rely on the data they have collected from the previous turns to predict the habits of the other servants, and try to return to the camp at the last safe moment.

# Program

```
# Team of treasure-hunting statisticians
# Run with:
# python3 statisticians.py

num_others = None
running = True
while running:
    msg = input().split()
    msg_type = msg.pop(0)
    if msg_type == "INDEX":
        my_index = int(msg[0])-1
    elif msg_type == "START_DAY":
        day, max_deaths = tuple(map(int, msg[0].split('/')))
    elif msg_type == "START_TURN":
        turn = int(msg[0])
        if day == 1:
            if turn == 1:
                print("S,S,S,S,S")
            elif turn == 30 or num_active <= max_deaths * 4/5:
                print("R,R,R,R,R") # On first day, return when 4/5 of  maximum number of dying servants remain
            else:
                print("S,S,S,S,S")
        elif turn >= 29 or len(expected_servants[turn+1]) <= max(2, max_deaths * 3/4) or len(expected_servants[turn]) <= max(2, max_deaths * 1/4):
            print("R,R,R,R,R") # If many servants are expected to return next turn or someone is sure to die, return to camp
        else:
            print("S,S,S,S,S") # Otherwise, keep going
    elif msg_type == "END_TURN":
        turn = int(msg.pop(0))
        others_moves = [tuple(s.split(',')) for s in msg[:my_index] + msg[my_index+1:]]
        if num_others is None: # End of first turn, initialize variables that depend on number of servants
            num_others = len(others_moves)
            others_history = [{} for i in range(num_others)]
        if day == 1:
            num_active = sum([move.count('S') for move in others_moves])
        for i, moves in enumerate(others_moves): # Log the return habits of other bots
            if turn == 1:
                others_history[i][day] = [0]*5
            for j, move in enumerate(moves):
                if move == "R": # Only safely returned servants are taken into account
                    others_history[i][day][j] = turn
                    if day > 1:
                        for future_turn in range(turn, 30):
                            expected_servants[future_turn].discard((i,j))
    elif msg_type == "END_DAY":
        day = int(msg.pop(0))
        my_statuses = tuple(msg[my_index].split(','))
        others_statuses = [tuple(s.split(',')) for s in msg[:my_index] + msg[my_index+1:]]
        expected_servants = [set() for i in range(30)] # Compute the sets of expected servants for each turn
        for i in range(num_others):
            for j in range(5):
                if others_statuses[i][j] == 'A':
                    turn_sum = 0
                    for day_num in others_history[i]:
                        turn_sum += others_history[i][day_num][j]
                    for turn in range(turn_sum//day):
                        expected_servants[turn].add((i,j))
    elif msg_type == "EXIT":
        running = False

```

As you can see, I shamelessly stole the program structure from @Mike Sweeney.

# Command

```
python3 statisticians.py

```

*EDIT: Fixed a bug in the check for returning home. They should perform somewhat better now.*

*EDIT 2: The statisticians are now smarter than before: they keep track of which servants have returned to the camp in the current day, and adjust their predictions accordingly. Also, they take more risks, returning to the camp when 3/4 of the maximum number of dying servants remain. This pushes them back to the top (just barely; Bob has become very dangerous).*
> 6 votes

# Answer
# Drunkards, Perl 5

A bit too much alcohol and they'll never find their way back to camp.

This entry is primarily an example, but will participate.

## Program

```
#!/usr/bin/perl
use 5.10.1;
$| = 1; # disable buffering
@actions = qw(S S S S S);

$_ = <>; ~/^INDEX (\d+)/;
$index = $1;

while(<>){
    if(index($_, 'START_TURN') == 0){
        say join(',', @actions);
    }elsif(index($_, 'END_DAY') == 0){
        # update actions based on who is alive
        # index 1-indexed; first bot at position 2.
        # this is not actually necessary for Drunkards, as all of Drunkards'
        #  servants will die on day 1 in any case.
        # This check is here simply as an example.
        my @status = split(',',(split(' '))[$index + 1]);
        my $i;
        for($i = 0; $i < 5; ++$i){
            # action is S if alive, N if dead. Servants will never be in camp.
            $actions[$i] = $status[$i] eq 'A' ? 'S' : 'N';
        }
    }elsif(index($_, 'EXIT') == 0){
        exit 0;
    }
}

```

## Command

```
perl ./players/Drunkards/Drunkards.pl

```
> 5 votes

# Answer
# Morning Birds

The early bird catches the worm!!!

```
package players.MorningBirds;

import java.io.*;
import java.util.*;

/*
 * Java 7
 *
 * Compile with "javac ./players/MorningBirds/MorningBirds.java"
 * Run with "java players.MorningBirds.MorningBirds"
 *
 * Servants find treasure from morning until noon.
 * At noon they go to bed to prepare for next day.
 *
 * According to Benjamin Franklin, "Early to bed, early to rise, keeps a
 *      man healthy, WEALTHY, and wise."
 *
 *
 */
public class MorningBirds {

    protected final static String STARTDAY = "START_DAY";

    protected final static String STARTTURN = "START_TURN";

    protected final static String ENDTURN = "END_TURN";

    protected final static String ENDDAY = "END_DAY";

    protected final static String MOVERETURN = "R";

    protected final static String MOVESEARCH = "S";

    protected final static String MOVENOTHING = "N";

    protected final static String RETURNED = "R";

    protected final static String FAILEDRETURN = "r";

    protected final static String SEARCHING = "S";

    protected final static String DEAD = "D";

    protected final static String SLEEPING = "N";

    protected final static String EXIT = "EXIT";

    protected final static String ALIVE = "A";

    protected enum Status{SEARCHING, DEAD, RETURNED}

    protected enum Move{RETURN, SEARCH, NOTHING}

    protected int index;

    protected int day;

    protected int turnNum;

    protected int howManyTeams;

    protected int howManyWillDieTodayAtMost;

    protected int howManyHaveDiedToday;

    protected int howManyEnemyPlayers;

    protected int howManyAliveEnemyPlayers;

    protected int howManyEnemyTeams;

    protected int howManyDeadEnemyPlayers;

    protected int howManyReturnedEnemyPlayers;

    protected int howManySearchingEnemyPlayers;

    protected int howManyTotalPlayers;

    protected int howManyTotalAlivePlayers;

    protected int howManyTotalDeadPlayers;

    protected int howManyTotalReturnedPlayers;

    protected int howManyTotalSearchingPlayers;

    protected int howManyOwnAlivePlayers;

    protected int howManyOwnDeadPlayers;

    protected int howManyOwnReturnedPlayers;

    protected int howManyOwnSearchingPlayers;

    protected Status[] statuses = new Status[5];

    protected Status[][] allStatuses = null;

    protected List<Status[][]> allDayStatuses = null;

    protected List<List<Status[][]>> allTimeStatuses = new ArrayList<>();

    protected BufferedReader in = new BufferedReader(
            new InputStreamReader(System.in));

    public static void main (String args[]) throws Exception{
        new MorningBirds().start();
    }

    public void start() throws Exception{

        index = Integer.parseInt(in.readLine().split("\\s")[1]);
        Arrays.fill(statuses, Status.SEARCHING);

        while(true){
            String[] input = in.readLine().split("\\s");
            if (input[0].equals(ENDTURN) || input[0].equals(ENDDAY)){
                updateStatus(input);
            } else if (input[0].equals(EXIT)){
                return;
            } else if (input[0].equals(STARTDAY)){
                updateDay(input);
            } else if (input[0].equals(STARTTURN)){
                updateTurn(input);
                doTurn(input);
            }

        }

    }

    protected void updateStatus(String[] input){
        if (allStatuses == null && input[0].equals(ENDTURN)){
            allStatuses = new Status[input.length - 2][5];
            for (Status[] enemyStatus : allStatuses){
                Arrays.fill(enemyStatus, Status.SEARCHING);
            }
            howManyTeams = input.length - 2;
            howManyEnemyTeams = input.length - 3;
            howManyTotalPlayers = howManyTeams * 5;
            howManyTotalAlivePlayers = howManyTotalPlayers;
            howManyTotalSearchingPlayers = howManyTotalAlivePlayers;
            howManyAliveEnemyPlayers = howManyTotalPlayers - 5;
            howManyEnemyPlayers = howManyEnemyTeams * 5;
            howManyOwnAlivePlayers = 5;
            howManyOwnSearchingPlayers = 5;
            howManySearchingEnemyPlayers = howManyAliveEnemyPlayers;
        }
        for ( int j = 0; j < howManyTeams; j++){
            String[] stats = input[j + 2].split(",");
            for(int i = 0; i < 5; i++){
                switch (stats[i]){
                    case "R":
                    case "N":
                        if (allStatuses[j][i] != Status.RETURNED){
                            howManyTotalReturnedPlayers++;
                            howManyTotalSearchingPlayers--;
                            if (j == index - 1) {
                                howManyOwnReturnedPlayers++;
                                howManyOwnSearchingPlayers--;
                            } else {
                                howManyReturnedEnemyPlayers++;
                                howManySearchingEnemyPlayers--;
                            }
                        }
                        allStatuses[j][i] = Status.RETURNED;
                        break;
                    case "A":
                    case "S":
                        if (allStatuses[j][i] != Status.SEARCHING){
                            howManyTotalReturnedPlayers--;
                            howManyTotalSearchingPlayers++;
                            if (j == index - 1) {
                                howManyOwnReturnedPlayers--;
                                howManyOwnSearchingPlayers++;
                            } else {
                                howManyReturnedEnemyPlayers--;
                                howManySearchingEnemyPlayers++;
                            }
                        }
                        allStatuses[j][i] = Status.SEARCHING;
                        break;
                    case "r":
                    case "D":
                        if (allStatuses[j][i] != Status.DEAD){
                            howManyTotalAlivePlayers--;
                            howManyTotalDeadPlayers++;
                            howManyHaveDiedToday++;
                            howManyTotalSearchingPlayers--;
                            if (j == index - 1){
                                howManyOwnAlivePlayers--;
                                howManyOwnDeadPlayers++;
                                howManyOwnSearchingPlayers--;
                            } else {
                                howManyAliveEnemyPlayers--;
                                howManyDeadEnemyPlayers++;
                                howManySearchingEnemyPlayers--;
                            }
                        }
                        allStatuses[j][i] = Status.DEAD;
                        break;
                    default:
                        break;
                }
            }
        }
        statuses = allStatuses[index - 1];
        if (input[0].equals(ENDTURN)){
            allDayStatuses.add(allStatuses.clone());
        }
        if (input[0].equals(ENDDAY)){
            Status[][] statusesToAdd = new Status[howManyTeams][5];
            for (int i = 0; i < statusesToAdd.length; i++){
                for (int j = 0; j < statusesToAdd[i].length; j++){
                    if (allStatuses[i][j] == Status.SEARCHING){
                        statusesToAdd[i][j] = Status.RETURNED;
                    } else {
                        statusesToAdd[i][j] = Status.DEAD;
                    }
                }
            }
            while (turnNum <= 30){
                allDayStatuses.add(statusesToAdd.clone());
                turnNum++;
            }
            allTimeStatuses.add(allDayStatuses);
        }
    }

    protected void updateDay(String[] input) throws Exception{
        day = Integer.parseInt(input[1].split("/")[0]);
        howManyWillDieTodayAtMost = Integer.parseInt(input[1].split("/")[1]);
        howManyHaveDiedToday = 0;
        allDayStatuses = new ArrayList<>();
        if (day == 1){
            Arrays.fill(statuses, Status.SEARCHING);
            howManyOwnAlivePlayers = 5;
            howManyOwnSearchingPlayers = 5;
        }
    }

    protected void updateTurn(String[] input){
        turnNum = Integer.parseInt(input[1]);
    }

    protected void doTurn(String[] input){
        Move[] moves = new Move[5];
        for (int i = 0; i < 5; i++){
            if (statuses[i] == Status.DEAD ||
                        statuses[i] == Status.RETURNED) {
                moves[i] = Move.NOTHING;
                continue;
            } else {
                moves[i] = doMove(i);
            }
        }
        String[] outputs = new String[5];
        for (int i = 0; i < 5; i++){
            switch (moves[i]){
                case SEARCH:
                    outputs[i] = MOVESEARCH;
                    break;
                case RETURN:
                    outputs[i] = MOVERETURN;
                    break;
                case NOTHING:
                    outputs[i] = MOVENOTHING;
            }
        }
        String totalOutput = "";
        for(String output : outputs){
            if (totalOutput != ""){
                totalOutput += ",";
            }
            totalOutput += output;
        }
         System.out.println(totalOutput);
    }

    //Implement this method differently for different
    //strategies.
    public Move doMove(int playerNumber){
        if (turnNum >= 15){
            return Move.RETURN;
        }
        return Move.SEARCH;
    }

    /**
     * Returns the status of one of your players.
     * Your players have numbers 1 to 5 inclusive.
     * Throws exception if number is outside range.
     *
     */
    protected Status getStatus(int player){
        if (player > 5 || player < 1){
            throw new IllegalArgumentException(
                    "getStatus(" + player +") failed.");
        }
        return statuses[player - 1];
    }

    /**
     * Returns the status of a player in a team.
     * Team numbers start with 1 inclusive.
     * Players have numbers 1 to 5 inclusive.
     * Throws exception if argument player is outside range.
     * Throws exception if argument team is less than 1 or is greater
     * than the number of teams.
     * Returns Status.SEARCHING if day == 1 and turnNum == 1 and argument
     * team >= 1.
     */
    protected Status getStatus(int team, int player){
        if (team < 1 || player < 1 || player > 1 ||
                (team > howManyTeams && day == 1 && turnNum == 1)){
            throw new IllegalArgumentException(
                    "getStatus(" + team + ", " + player + ") failed.");
        }
        if (day == 1 && turnNum == 1 && team >= 1){
            return Status.SEARCHING;
        }
        return allStatuses[team - 1][player - 1];
    }

    /**
     * Returns the status of a player in a team at the end of argument
     * turn.
     * Team numbers start with 1 inclusive.
     * Players have numbers 1 to 5 inclusive.
     * Turns have numbers 0 to 30 inclusive.
     * Status at turn 0 is equal to status at start of turn 1.
     * Throws exception if argument turn hasn't happened yet.
     * Throws exception if argument player is outside range.
     * Throws exception if argument team is less than 1 or is greater
     * than the number of teams.
     */
    protected Status getStatus(int turn, int team, int player){
        if (turn == 0){
            if (day == 1){
                return Status.SEARCHING;
            } else {
                return getStatus(day - 1, 30, team, player);
            }
        }
        if (turnNum <= turn || turn < 0|| player > 5 || player < 1 ||
                team < 1 || team > howManyTeams){
            throw new IllegalArgumentException("getStatus(" + turn +
                    ", " + team + ", " + player + ") failed.");
        }
        return allDayStatuses.get(turn - 1)[team - 1][player - 1];
    }

    /**
     * Returns the status of a player in a team at the end of argument
     * turn on the day of argument day.
     * Team numbers start with 1 inclusive.
     * Players have numbers 1 to 5 inclusive.
     * Turns have numbers 0 to 30 inclusive.
     * Days have numbers 1 inclusive and up.
     * Status at turn 0 is equal to status at start of turn 1.
     * Throws exception if argument day hasn't ended yet or is less
     * than one.
     * Throws exception if argument turn is out of range.
     * Throws exception if argument player is outside range.
     * Throws exception if argument team is less than 1 or is greater
     * than the number of teams.
     */
    protected Status getStatus(int day, int turn, int team, int player){
        if (turn == 0){
            if (day == 1){
                return Status.SEARCHING;
            } else {
                return getStatus(day - 1, 30, team, player);
            }
        }
        if (this.day <= day || day < 1 || turn > 30 || turn < 0 ||
                player > 5 || player < 1 ||
                team < 1 || team > howManyTeams){
            throw new IllegalArgumentException("getStatus(" + day + ", "
                    + turn + ", " + team + ", " + player + ") failed.");
        }
        return allTimeStatuses.get(day - 1).get(turn - 1)[team - 1][player - 1];
    }

}

```

**Edit:** Made it so anyone could easily subclass it. Just redefine `doMove(int playerNumber)` for your own bot. I have added several helpful fields and methods. I have extensively tested it. It does **not** save the statuses from previous simulations. Please tell me if there are any problems.

Compile with: `javac ./players/MorningBirds/MorningBirds.java`

Run with: `java players.MorningBirds.MorningBirds`
> 4 votes

# Answer
# Randomizers - Ruby

Just to mess up statistics driven bots, the randomizers are quite unpredictable. All of them do return at once, at a random turn in an attempt to strand others.

(Not influenced by other players.)

```
def min(a,b);(a<b)?a:b;end
x=""
r=0
while x != "EXIT"
  x=gets.chomp
  if x =~ /^START_DAY/
    r = min(rand(30),rand(30))
  end
  if x =~ /^START_TURN (\d*)/
    puts ($1.to_i>r)?'R,R,R,R,R':'S,S,S,S,S'
  end
end

```
> 3 votes

# Answer
# Wandering Fools, Python 2

This is a simple Python bot that sends out the servants until a preset "goback" time is reached, then they try to enter camp and stay until the next day.

It is also a basic framework for more complex bots that others may wish to use. It is, however, untested with the judge engine, so let me know if I have made an error.

## Program

```
import sys
from random import randint, choice
team = range(5)

while True:
    inp = sys.stdin.readline().split()
    cmd = inp.pop(0)
    if cmd == 'INDEX':
        teamnum = int(inp[0]) - 1   # using zero based indexing
    elif cmd == 'START_DAY':
        daynum, deadnum = [int(v) for v in inp[0].split('/')]
        # Set up strategy for the day:
        goback = [randint(5,25) for i in team]
    elif cmd == 'START_TURN':
        turn = int(inp[0])
        # Output actions [R]eturn, [S]earch, [N]othing here:
        actions = ['S' if turn < goback[i] else 'R' for i in team]
        sys.stdout.write( (','.join(actions)) + '\n' )
        sys.stdout.flush()
    elif cmd == 'END_TURN':
        endturn = int(inp.pop(0))
        status = [v.split(',') for v in inp]  # R,r,S,D,N
        # [R]eturned, [r]ejected, [S]earching, [D]ead, [N]othing
        mystatus = status[teamnum]
    elif cmd == 'END_DAY':
        endturn = int(inp.pop(0))
        alive = [v.split(',') for v in inp]  # [A]live or [D]ead
        myalive = alive[teamnum]
    elif cmd == 'EXIT':
        sys.exit(0)

```

## Command

```
python WanderingFools.py

```

Edit: Changed action deciding code after rule clarification.
> 2 votes

# Answer
**Evolved**

I used Genetic Programming (through JGAP) to make this bot. It came up with a simple answer that beats all others (barely).

```
package players.Evolved;

import players.MorningBirds.*;
import java.util.*;

public class Evolved extends MorningBirds{

    List<Integer> scrambled = new ArrayList<>();

    public static void main(String[] args) throws Exception{
        new Evolved().start();
    }

    public Evolved() throws Exception{
        super();
    }

    @Override
    public MorningBirds.Move doMove(int playerNum){
        if (!(howManyTotalSearchingPlayers < (turnNum - getScrambled(index)))){
            return Move.SEARCH;
        } else {
            return Move.RETURN;
        }
    }

    @Override
    protected void updateStatus(String[] input){
        super.updateStatus(input);
        if (input[0].equals(ENDTURN) && (Integer.parseInt(input[1]) == 1)){
            for (int i = 1; i <= howManyTeams; i++){
                scrambled.add(i);
            }
            Collections.shuffle(scrambled);
        }
    }

    public int getScrambled(int in){
        if (in > scrambled.size() || in < 1 ){
            return in;
        }
        return scrambled.get(in - 1);
    }
}

```

Compile with: `javac players/Evolved/Evolved.java`

Run with: `java players.Evolved.Evolved`

**Edit:** Grrr... Bob messed me up!!!

**Edit:** Yay!!! Bob, got killed by a nasty plague!!!
> 2 votes

# Answer
# SlowReturners - Ruby

Sends one servant back every 5 turns.

```
x=""
while x != "EXIT"
  x=gets.chomp
  if x =~ /^START_TURN (\d*)/
    puts (1..5).map{|i|(i<=$1.to_i/5)?"R":"S"}.join(",")
  end
end

```
> 1 votes

# Answer
# **Plague**

Plague is a disease. It is not rational. It is predictable. Diseases cannot collect treasure, nor do they care for treasure. Plague makes other players sick. The wise ones stay home and forget about treasure. The foolish ones are always foolish and will never get much treasure. Evolved is (fortunately) immune to Plague. He is also wise. He goes and collects treasure, and does not die.

```
package players.Plague;

import players.MorningBirds.MorningBirds;

public class Plague extends MorningBirds{

    public static void main(String[] args) throws Exception{
        new Plague().start();
    }

    public Plague() throws Exception{
        super();
    }

    @Override
    public MorningBirds.Move doMove(int playerNum){
        if (day > howManyTotalDeadPlayers){
            return Move.SEARCH;
        } else {
            return Move.RETURN;
        }
    }
}

```

Compile with: `javac players/Plague/Plague.java`

Run with: `java players.Plague.Plague`

*Bob and Statisticians are now resistant to plague.*
> 1 votes

---
Tags: king-of-the-hill
---


title: Magical Squares

text:
# Question
Title: Magical Squares
A perfect square is a number that is the square of an integer.

However, let's define something called a **Magical Square**, which is a perfect square with the following restriction:

The perfect square must be the sum of the numbers 1...N for some natural number N. Write a program that calculates the first X magical squares:

The first magical square is 1 (not 0, since N \>= 1). The values of X are: 1 \<= X \<= 15. The program should be efficient and your score is the time taken to calculate the magical squares in seconds. The winner is the program that runs in the least amount of time. Please also include the generated numbers.

You can't hard-code the values, or read them from a file, etc. They *MUST* be calculated by the program.

Some examples: 1, 36, 1225, ...

# Answer
> 3 votes
# CJam, 1 ms

```
UXD{_34*2$m2+}*]1>N*

```

This uses the following known recurrence relation:

```
N[k] = 34 * N[k-1] - N[k-2] + 2

```

### Timing/Output

```
$ cjam <(echo 'es:T; UXD{_34*2$m2+}*]1>N* esT-`p'); echo
"1"
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796
2172602007770041
73804512832419600
2507180834294496361
85170343853180456676

```

# Answer
> 1 votes
# Java 7, 467945 ns = .467945 ms

Using sudo's formula:

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

public class SquareTriangle{
    public static void main(String[] args){
        PrintStream out = new PrintStream(System.out, false);
        long startTime = System.nanoTime();
        for (int i = 0; i < 100000; i++){
            BigInteger a = 0;
            BigInteger b = 1;
            BigInteger c;
            for (int i = 0; i < 15; i++){
                out.println(b);
                c = b;
                b =  c.multiply(BigInteger.valueOf(34)).subtract(a)
                         .add(BigInteger.valueOf(2));
                a = c;
            }
        }
        long endTime = System.nanoTime();
        out.flush();
        System.out.println((endTime - startTime)/100000 + " ns");
    }
}

```

Takes an average of 467945 ns per run on my very slow computer.

Here are the numbers:

```
1
36
1225
41616
1413721
48024900
1631432881
55420693056
1882672131025
63955431761796
2172602007770041
73804512832419600
2507180834294496361
85170343853180456676
2893284510173841030625

```

**Edit:** Now flushes the output stream *after* it is timed, not during.

---
Tags: number, fastest-code
---


title: Generalized Gematria Calculator

text:
# Question
Title: Generalized Gematria Calculator
Create a bidirectional Gematria calculator, for any given sequence of Unicode characters as the alphabet.

# Gematri-What?

Gematria is a system of assigning numerical values to symbols, developed by ancient Greeks and adopted by ancient Jews. It is in a way like ASCII or Unicode, it's just non-linear... See the following table (full table is available in the link above):

```
Index     Letter   Letter name  Value
--------------------------
  0         א         "Alef"     1
  1         ב         "Bet"      2

           ...

  8         ט         "Tet"      9
  9         י         "Yud"      10
 10         כ         "Kaf"      20

           ...

 17         צ        "Tsady"     90
 18         '        "Kuf"       100
 19         ר        "Resh"      200

           ...

```

The names of letters are not important, only their index in the "Array" of the alphabet and the respective numerical value. The Hebrew alphabet only has 22 letters (not including "final" letters), so the maximum available value is 400.

If we borrow this system to the English alphabet (A-Z) we will end up with A=1, B=2... L=30... U=300... Z=800.

Two things we need to know.

1. One of the most important features in this system is calculating the "Gematria Value" of a **word**, by **summing up** its letters' values. (Some say there is a mystical connection between words, or phrases (when the value of space is zero) - that share the same Gematria Value).
2. Any non-negative Integer can be represented in symbols. For example (and let's stay with the English alphabet for now) the value of 32 is LB (L=30 + B=2). The value of 1024 is ZTKD (800+200+20+4. Note that ZSSKD is also 1024, but that's not a legal representation, since it can be compacted).

# The Challenge

Write a program / a function / a code snippet in your language-of-choice, which is first set up with an alphabet (see API below) and then accept an argument. That argument may be an Integer, or a word/phrase. If it's an Integer - your program should output/return its representation in the alphabet symbols - the most compacted one (see (2) above). If it is a word or a phrase, your program should output/return the Gematria Value (by summing up symbols' values, not counting whitespaces, see (1) above).

# API

Your program/function should accept 3 arguments. You can get them from STDIN, or as function arguments, you can even assume they are variables which initialized programmatically prior to your function invocation.

* First argument - the first character (in Unicode) of the alphabet.
* Second argument - the last character (in Unicode) of the alphabet.
* Third argument - An Integer, to be represented in symbols, OR a phrase which is created by the given alphabet.

Output / Return Value: Depending on the third argument, as explained above.

# Assumptions

* First two arguments will always be one character long each, and the second will always be grater than the first.
* The sequence (first until last, inclusive) will never include any of the values 30-39 (which represent the digits 0-9), otherwise it will make the third argument ambiguous. **EDIT:** It won't contain space as well, since in phrases spaces are counted as zeros.
* The third argument, in case it's a phrase, may only contain spaces and letters of the given alphabet. Empty string is not a valid input (you can assume it's not empty). In case it's an Integer, you can assume it's a positive Integer.

# Examples

```
Input                Output

A Z CODE GOLF        175
a s 512              sssssjb
A B 7                BBBA
≐ ⊐ ≤≫ ≥            1700

```

# Scoring

`Score = upvotes - length/100.0`

Your code should be short, but more-importantly popular. Negative scores can also play along. The winner will be the answer with highest score in a week from now, 2014-11-29 19:20:00 UTC.

# Answer
> 4 votes
# CJam, ~~80~~ ~~75~~ 70 bytes, Upvotes - 0.7

```
Arc:Irc\-):N,f#{9,:)f*~}%N<lS-_A,s&{i{1${1$)<},)\,I+o-}h;;}{If-\f=:+}?

```

Test it here.

This is a full program, which takes input from STDIN and prints the result to STDOUT.

I'm not really sure how I'm supposed to shoot for popularity here, so I'm simply golfing this, hoping to get a reasonably impressive code size instead. ;)

I believe the int-to-string conversion can still be improved, but I don't see it right now.

Thanks to Optimizer for reminding me about set intersection and that empty arrays are falsy.

```
A                                   "Push integer 10.";
 rc:I                               "Read token, convert to character, save in I.";
     rc                             "Read token, convert to character.";
       \-)                          "Swap, subtract, increment.";
          :N                        "Store number of characters in N.";
            ,                       "Turn into range [0 1 2 ... N-1].";
             f#                     "Map 10^i onto that range.";
               {       }%           "Map this block onto the powers of 10.";
                9,                  "Create range [0 1 2 ... 8].";
                  :)                "Increment each element.";
                    f*              "Multiply each by the current power of 10.";
                      ~             "Unwrap/dump the resulting array.";
                                    "Now we've got the values of the first 9N digits.";
                         N<         "That's too much, so truncate to the first N.";
                           l        "Read the rest of the line.";
                            S-      "Remove spaces.";
                              _     "Duplicate string and get first character.";
                               A,   "Create range [0 1 2 ... 9].";
                                 s  "Turn into string '0123456789'.";
                                  & "Intersection of characters.";

{                      }{        }? "If/else depending on whether the result is empty.";
                                    "If it was a digit...";
 i                                  "Convert string to integer.";
  {                }h               "While that integer isn't zero...";
   1$                               "Copy digit values.";
     {    },                        "Filter digit values.";
      1$                            "Copy remaining integer.";
        )<                          "Increment, compare.";
                                    "This discards values greater than the integer.";
            )\                      "Slice off last digit value, and swap with list.";
              ,I+                   "Get length of list and add to I.";
                 o                  "Print character.";
                  -                 "Subtract digit value from integer.";
                     ;;             "Empty stack.";
                                    "If the string was not a number...";
                         I          "Push initial character.";
                          f-        "Subtract it from each character in string.";
                            \       "Swap differences and digit values.";
                             f=     "Use differences to index into the values.";
                               :+   "Sum up all the values.";

```

In the second case, the result is left on the stack, which is printed automatically at the end of the program.

# Answer
> 5 votes
# Java 7, Score = Upvotes - 3.97

Yay!!! Java!!! The world's favourite golfing language in the world. What, you can actually golf in java??? Well, it's kind of like using a bulldozer to putt.

`a` is expected to contain the first character. `b` is expected to contain the last character. `c` is expected to have the input string.

Here is the function golfed:

```
int d=0;try{d=Integer.parseInt(c);}catch(Exception e){}int l=b-a+1;char[]f=new char[l];int[]g=new int[l];int h=1;int i=1;g[0]=1;f[0]=a;int j;for(j=1;j<b-a+1;){g[j]=(h+=i);f[j]=(char)(f[j++-1]+1);i*=h==10*i?10:1;}if(d==0){h=0;for(char k:c.toCharArray()){for(j=0;j<l;j++){if(f[j]==k){h+=g[j];}}}System.out.println(h);}else{c="";for(j=l;j>0;){if(g[--j]<=d){c+=f[j];d-=g[j++];}}System.out.println(c);}

```

Here it is indented with structure code:

```
public class G{

    public static void main(String[] args){
        new G(args);
    }

    public G(String[] args){
        a = args[0].charAt(0);
        b = args[1].charAt(0);
        for (int i = 2; i < args.length; i++){
            c += args[i];
        }
        function();
    }

    char a;

    char b;

    String c = "";

    void function(){
        int d=0;
        try{
            d=Integer.parseInt(c);
        }catch(Exception e){}
        int l=b-a+1;
        char[]f=new char[l];
        int[]g=new int[l];
        int h=1;
        int i=1;
        g[0]=1;
        f[0]=a;
        int j;
        for(j=1;j<b-a+1;){
            g[j]=(h+=i);
            f[j]=(char)(f[j++-1]+1);
            i*=h==10*i?10:1;
        }
        if(d==0){
            h=0;
            for(char k:c.toCharArray()){
                for(j=0;j<l;j++){
                    if(f[j]==k){
                        h+=g[j];
                    }
                }
            }
            System.out.println(h);
        }else{
            c="";
            for(j=l;j>0;){
                if(g[--j]<=d){
                    c+=f[j];
                    d-=g[j++];
                }
            }
            System.out.println(c);
        }
    }
}

```

Here it is completely expanded:

```
public class Generator{

    public static void main(String[] args){
        beginning = args[0].charAt(0);
        end = args[1].charAt(0);
        for (int i = 2; i < args.length; i++){
            phrase += args[i];
        }
        function();
    }

    static char beginning;

    static char end;

    static String phrase = "";

    static void function(){
        int convertTo = 0;
        try{
             convertTo = Integer.parseInt(phrase);
        } catch (Exception e){}
        char[] alphabet = new char[end - beginning + 1];
        int[] values = new int[alphabet.length];
        int value = 1;
        int base = 1;
        values[0] = 1;
        alphabet[0] = beginning;
        int i;
        for (i = 1; i < values.length;){
            values[i] = (value += base);
            alphabet[i] = (char)(alphabet[i++-1]+1);
            base*=value==10*base?10:1;
        }
        if(convertTo==0){
            value = 0;
            for (char character : phrase.toCharArray()){
                for (i = 0; i < alphabet.length;i++){
                    if (alphabet[i] == character){
                        value += values[i];
                    }
                }
            }
            System.out.println(value);

        } else {
            phrase = "";
            for (i = values.length;i > 0;){
                if (values[--i] <= convertTo){
                    phrase += alphabet[i];
                    convertTo -= values[i++];
                }
            }
            System.out.println(phrase);

        }
    }
}

```

# Answer
> 3 votes
# Haskell, 188 bytes; Upvotes - 1.88

This is a full-blown STDIN-to-STDOUT program, heavily golfed. *EDIT: Now in under 200 bytes! EDIT2: Saved one byte with @proudhaskeller's suggestion.*

```
x=[1..9]++map(*10)x
f(a:_:b:_:z@(u:_))|u>'/'&&u<':'=w$read z|1<2=show.sum$map v z where v ' '=0;v c=x!!(length[a..c]-1);w 0="";w n=(\c->c:w(n-v c))$last[d|d<-[a..b],v d<=n]
main=interact$f

```

It constructs the infinite list of values `x = [1,2,3,4,5,6,7,8,9,10,20,30,..]` on the first line, and does I/O on the third line. The value of a letter `c`, given the range `[a..b]`, is then the value at position `length [a..c] - 1` of `x`. On the second line, we branch on the first letter `u` of the third argument, and either sum its gematria values (if `u` is not a digit), or greedily construct a word with the given value (if `u` is a digit).

Ungolfed version with more readable variable names:

```
values = [1..9] ++ map (*10) values
f (low:_:high:_:rest@(first:_))
  | first > '/' && first < ':' = construct $ read rest
  | otherwise                  = show . sum $ map value rest
  where value ' '   = 0
        value c     = values !! (length [low..c] - 1)
        construct 0 = ""
        construct n = (\c -> c : construct (n - value c)) $
                      last [d | d <- [low..high], value d <= n]
main = interact $ f

```

# Answer
> 2 votes
## APL (upvotes - 1.05)

```
{U←⎕UCS⋄A←V↑∊(10*0,⍳⌊9÷⍨V←1+|-/U⍺)∘.×⍳9⋄⍬≢0↑⍵:+/A[1+(U⍵~' ')-U⊃⍺]⋄U(U⊃⍺)+{⍵≤0:⍬⋄(¯1+A⍳T),∇⍵-T←⊃⌽A/⍨⍵≥A}⍵}

```

This is a function that takes the two characters on the left, and the argument to be converted on the right:

```
      'A' 'Z'{U←⎕UCS⋄A←V↑∊(10*0,⍳⌊9÷⍨V←1+|-/U⍺)∘.×⍳9⋄⍬≢0↑⍵:+/A[1+(U⍵~' ')-U⊃⍺]⋄U(U⊃⍺)+{⍵≤0:⍬⋄(¯1+A⍳T),∇⍵-T←⊃⌽A/⍨⍵≥A}⍵}'CODE GOLF'
175
      gematria←{U←⎕UCS⋄A←V↑∊(10*0,⍳⌊9÷⍨V←1+|-/U⍺)∘.×⍳9⋄⍬≢0↑⍵:+/A[1+(U⍵~' ')-U⊃⍺]⋄U(U⊃⍺)+{⍵≤0:⍬⋄(¯1+A⍳T),∇⍵-T←⊃⌽A/⍨⍵≥A}⍵}
      'A' 'Z' gematria 'CODE GOLF'
175
      'a' 's' gematria 512
sssssjb
      'A' 'B' gematria 7
BBBA
      '≐' '⊐' gematria '≤≫ ≥'
1700

```

Ungolfed version:

```
gematria←{
   ⍝ get Unicode values for characters
   first last←⎕UCS¨⍺
   amount←1+last-first
   ⍝ find the value for each character in the alphabet
   alphabet←amount↑∊(10*0,⍳⌊amount÷9)∘.×⍳9

   ⍝ right arg is string: calculate number
   ⍬≢0↑⍵: +/ alphabet[1+(⎕UCS ⍵~' ')-first]

   ⍝ otherwise, right arg is number: find string
   ⎕UCS first+{
      ⍝ number ≤ 0? empty string
      ⍵≤0:⍬

      ⍝ find highest value we can subtract
      val←⊃⌽(⍵≥alphabet)/alphabet

      ⍝ return it, followed by the conversion of the rest of the number
      (¯1+alphabet⍳val), ∇⍵-val
   }⍵
}

```

# Answer
> 1 votes
# CJam, 70 bytes, #Upvotes - 0.7

```
{{_9%)A@9/#*}%}:M;rcrc),\i>:QlS-_@&{Qf#M:+}{i{Q,,M{1$)<},)Q@,=@@-}h;}?

```

This assumes that a valid input will be passed. Takes input from STDIN like the API spec says and prints result to STDOUT.

Examples:

```
Input                Output

A Z CODE GOLF        175
a s 512              sssssjb
A B 7                BBBA
≐ ⊐ ≤≫ ≥            1700

```

Try it online here

**Block wise explanation**:

```
{{_9%)A@9/#*}%}:M;
{             }:M;              "Define a function M which takes an input array of"
                                "indeces and calculates the Gematri number for them";
 {          }%                  "Run this code block for each element of the array";
  _9%)                          "Copy the number, take modulus by 9 and increment it";
      A@                        "Put 10 on stack, and rotate to get the number on top";
        9/                      "Integer divide the number by 9";
          #                     "Calculate 10 to the power the above quotient";
           *                    "Multiply the above result by modulus 9";

rcrc),\i>:QlS-_@&
rcrc                            "Read the first two characters, representing the lower"
                                "and upper end of the character list";
    ),                          "Increment the upper end and get a list of U to ASCII 0"
                                "characters where U is the upper limit";
      \i                        "Swap and convert the lower limit to its ASCII number";
        >:Q                     "Slice the character list to get our desired character"
                                "list range and store it in Q";
           lS-                  "Read the rest of the line as string and remove spaces";
              _@&               "Take a copy, get Q on top of stack and take"
                                "intersection with the input string. If the resulting"
                                "string is empty, then the third input was a number";
                 {...}{...}?    "First code block is for string input and second for"
                                "number input based on the above intersected string";

{Qf#M:+}
 Qf#                            "For each character of input string, calculate its"
                                "position in Q";
    M                           "Get the Gematri numbers for these inceces";
     :+                         "Sum them all to get the final Gematri number for the"
                                "input string"

{i{Q,,M{1$)<},)Q@,=@@-}h;}
 i                              "Convert the input number string to integer";
  {                   }h        "Run the code block till we get 0 on top of stack";
   Q,,M                         "Get the first length(Q) Gematri numbers";
       {1$)<},                  "Filter and take only which are less than input number";
              )                 "Pop the last number from the filtered array. This is"
                                "The maximum Gematri number that can be deducted";
               Q@               "Put Q on stack and rotate the remaining filtered array"
                                "to top of stack";
                 ,              "Calculate the length of that array, which is also the"
                                "index of the Gematri number used.";
                  =             "Get the corresponding character to that Gematri number";
                   @@-          "Put the number and Gematri number on top and subtract."
                                "The next loop runs on the above result now";
                        ;       "Pop the resedual 0 from stack. The remaining stack now"
                                "contains just the Gematri characters."

```

---
Tags: code-challenge, string, arithmetic, unicode, base-conversion
---