title: Plurality Voting with Cellular Automata

text:
# Question
Title: Plurality Voting with Cellular Automata
There's a really important problem in cellular automata called the Majority problem:

> The majority problem, or density classification task is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.
>
> ...
>
> Given a configuration of a two-state cellular automata with i + j cells total, i of which are in the zero state and j of which are in the one state, a correct solution to the voting problem must eventually set all cells to zero if i \> j and must eventually set all cells to one if i \< j. The desired eventual state is unspecified if i = j.

Although it has been proven that no cellular automata can solve the majority problem in all cases, there are many rules that can can solve it in the majority of cases. The Gacs-Kurdyumov-Levin automaton has an accuracy of about 78% with random initial conditions. The GKL rule isn't complicated:

* Radius of 3, meaning that the cell's new state depends on 7 previous cells: itself, the 3 cells to the right, and the 3 cells to the left.
* If a cell is currently `O`, its new state is the majority of itself, the cell to its left, and the cell 3 steps to its left.
* If a cell is currently `1`, its new state is the majority of itself, the cell to its right, and the cell 3 steps to its right.

Here is an example:

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

```

In this example, the cellular automaton correctly calculated that 8 \> 6. Other examples take longer periods of time, and produce some cool patterns in the meantime. Below are two examples I randomly found.

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

```

---

## Taking it to the next level

As far as my internet research has shown, almost all academic research on the majority problem has been conducted with 2-state CAs. In this challenge, we are going to expand the majority problem to **3-state CAs**. I will call this the *plurality problem*. Plurality, or relative majority, refers to the condition in which one of the options has more votes than each of the alternatives, but not necessarily a majority of all votes.

**Problem Statement**

1. There is a 3-state 1D cellular automaton with radius 3.
2. There are **151** cells with a circular boundary condition.
3. These cells are given a random starting state, on the sole condition that 1 of the 3 states has a strict plurality. "Random" means an independent uniform distribution for each cell.
4. The accuracy of a rule is the percentage of (valid) random initial conditions in which all of the cells synchronize to the correct state (the one with plurality) **within 10000 generations**.
5. The goal is to find a rule with high accuracy,

Plurality edge cases: Any configuration with 50/50/51 is a valid starting configuration (since there is a strict plurality), while any configuration with 51/51/49 is not valid (since there is not a strict plurality).

The search space is 3^3^7 (~3e1043), far outside the reach of any exhaustive search. This means that you will need to make use of other techniques, like genetic algorithms, in order to solve this problem. It will also take some human engineering.

The 10000 generation rule is subject to change, depending on the runtimes/accuracy of the rules people find. If it is too low to allow reasonable rates of convergence, then I can raise it. Alternatively, I can lower it to serve as a tie-breaker.

## Winning

The winner is the person who submits the radius-3 CA rule with the highest accuracy out of all of the contestants.

Your submission should include...

* A description of the rule (using Wolfram code if necessary)
* The accuracy rate and sample size
* A reasonably-sized *explanation* of how you discovered the rule, including programs you wrote to solve it, or any "manual" engineering. (This being the most interesting part, since everything else is just raw numbers.)

## Prior Work

* A paper by Juille and Pollack, describing how they evolved a 2-state rule with 86% accuracy.
* This paper used r=3, 149-cell, 2-state CAs. It did not attempt to the solve the majority problem, however, but instead to find rules that quickly resulting in an alternating all-`1`-all-`0` pattern. Despite these differences, I suspect many techniques will be similar.
* A (not very helpful because it's behind a paywall) paper by Wolz and de Oliviera which currently hold the 2-state record

# Answer
# Sort of GKL plus hill climbing, 61.498%

* If a cell is a 0, look at the cells 3 to the left, 1 to the left and at itself. Set value to majority. If it's a tie, stay the way you are.
* If a cell is a 1, look at the cells 3 to the right, 1 to the right and at itself. Set value to majority. If it's a tie, stay the way you are.
* If a cell is a 2, look at the cells 2 to the left, 2 to the right and 3 to the right. Set value to majority. If it's a tie, stay the way you are.

I got 59453 right out of 100000 total, 59.453%

Some mutating and hill-climbing resulted in 61498/100000 = 61.498%.

I'll probably test a bit more and will post some more information later.
> 6 votes

# Answer
# "Just toss out the 2s and do GKL" -- 55.7%

It's not so easy to guess what a good rule would be, so I tried to at least come up with something that would score above 1/3. The strategy is to try to get the right answer when the majority state is 0 or 1, and accept the loss if it's 2. It scored 56.5% over 100,000 trials, which is somehow slightly better than what would be expected from multiplying 78% (score of GKL) * 2/3 (fraction of the time when answer is 0 or 1) = 52%.

More concretely, the strategy is as follows:

* If the cell is 0 or 1, take the majority of the 3 cells as in the GKL strategy, but ignoring any neighbors that are 2. If it's a tie, leave the cell unchanged.
* If the cell is 2, choose whichever is more numerous of 0 or 1 in the entire neighborhood. If it's a tie, choose the leftmost value that is 0 or 1. If all the neighbors are 2, stay 2.

I used this code to test:

```
#include <iostream>
#include <algorithm>
#include <string.h>
#include <random>
#include <cassert>

#define W 151
#define S 3
#define R 3

typedef int state;

struct tape {
    state s[R+W+R];
    state& operator[](int i) {
        return s[i + R];
    }
    template<typename Rule> void step(Rule r) {
        for(int i = 0; i < R; i++) s[i] = s[W + i];
        for(int i = 0; i < R; i++) s[R + W + i] = s[R + i];
        for(int i = 0; i < W; i++) {
            s[i] = r(s + R + i);
        }
        memmove(s + R, s, W * sizeof(*s));
    }

    state unanimous() {
        state st = (*this)[0];
        for(int i = 1; i < W; i++) {
            if((*this)[i] != st)
                return -1;
        }
        return st;
    }
};

std::ostream& operator<<(std::ostream& s, tape& t) {
    for (int i = 0; i < W; i++)
        s << t[i];
    return s;
}

state randomize(tape& t) {
    static std::mt19937 rg(390332);
    begin:
    int c[S]{};
    for(int i = 0; i < W; i++) {
        state s = rg() % S;
        c[s]++;
        t[i] = s;
    }
    state* smax = std::max_element(c, c + R);
    int nmaj = 0;
    for (int n : c) nmaj += n == *smax;
    if (nmaj > 1) goto begin;
    return smax - c;
}

template<bool PrintSteps, typename Rule> int simulate(Rule r, int trials, int giveup) {
    int successes = 0;
    for(state s = 0; s < S; s++) {
        state t[2 * R + 1];
        for(int i = 0; i <= 2 * R; i++) t[i] = s;
        assert(r(t + R) == s);
    }
    while(trials--) {
        tape tp;
        state desired = randomize(tp);
        int steps = giveup;
        while(steps--) {
            tp.step(r);
            state u = tp.unanimous();
            if(~u) {
                bool correct = u == desired;
                if(PrintSteps) {
                    std::cout << correct << ' ' << giveup - steps << '\n';
                }
                successes += correct;
                break;
            }
        }
    }
    return successes;
}

struct ixList {
    int n;
    int i[2 * R + 1];
};

state rule_justTossOutThe2sAndDoGKL(const state* t) {
    const ixList ixl[] = {
        { 3,{ -3, -1, 0 } },
        { 3,{ 0, 1, 3 } },
        { 6,{ -3, -2, -1, 1, 2, 3 } }
    };
    int c[S]{};
    for (int i = 0; i < ixl[*t].n; i++)
        c[t[ixl[*t].i[i]]]++;
    if (c[0] > c[1]) return 0;
    if (c[1] > c[0]) return 1;
    if (*t < 2) return *t;
    for (int i = -R; i <= R; i++)
        if (t[i] < 2) return t[i];
    return 2;
}

int main()
{
    int nt = 100000;
    int ns = simulate<false>(rule_justTossOutThe2sAndDoGKL, nt, 10000);

    std::cout << (double)ns / nt << '\n';
    return 0;
}

```
> 5 votes

# Answer
# "Just steal whatever's best and evolve it", bleh

Edit: in its current state this answer, rather than finding better patterns, finds a better random sample.

This answer encodes/decodes solutions by enumerating all states as ternary numbers (least-significant digit first). The solution for 59.2%:

```
000000000010010010000000000000000000000000000000000000000000010000010000110000000
000000000010010010000000000111111101111111111111111111000011000010011011000011010
000000000012010011001000000021111111111120111211111111000000000000011010000010000
000011000010022110000000202000000002000000000020000000001010000000011011000011010
020000000010010010001000000111101111111111111111111111010011000011111111010011010
000000000010010010000000000111111111101111111111112111000011010110111011010011011
000000000010010010000000000010000000000000000100002011000000000100011010020010000
000020020010010010000200000111102111111111111111111101000011010010111011000011011
000100000010010010000000000121111111111111111111111111000210000012011011002011010
000000000010010110000000000111112112111111111001111111000010000010011011000011010
000000000010010120000200000111211111111111111111110111110011010011100111010011011
000000000010010010000000000011111111111111111111111111000011010010111211210012020
010000000010010010020100020111110111111111111111111110010111010011011111010111011
002000000010010010000000000111110111111111211111111111001111111111111111111111111
000000000110010010000000000111111111111111211111111111010111011111111111011111011
001000000010010010000000000011111101111111111111110111000011010010111011010011010
001000000010010110000000000111111111111111102111110111010111011111111111011111101
000000000210010010000000000111111111111111111111011111010011010011111111010111011
000000000010010010000000000112111111111111111111101011000000000000011010000010000
000000000010010010000000000111111111111111111111111111000011010010111011010011011
000200000012010010000000000111111111111112111111111111000010000210011211001011010
000000000010010211000002000111111111111111111111111111000001010010111011010011010
000021200010210010000101100111111111111211111110110211010111021111111101010111111
000000000010010010000000000111111111111101111111111111010011010111111111010110021
000200000010010010000000010111111111101111111121112111000210001010011011000011010
000000000010010010000000000111111111111111111111111111210011010021111111010111011
000020000010010010000000000111111111111111111111111111000011010010121011010011012

```

This answer was evolved from feersum's 55.7%, using the following code. This code requires libop, which is my personal C++ header-only library. It's very easy to install, just do `git clone https://github.com/orlp/libop` in the same directory as where you've saved the program. I suggest compiling with `g++ -O2 -m64 -march=native -std=c++11 -g`. For speedy development I also suggest precompiling libop by running the above command on `libop/op.h`.

```
#include <cstdint>
#include <algorithm>
#include <iostream>
#include <cassert>
#include <random>

#include "libop/op.h"

constexpr int MAX_GENERATIONS = 500;
constexpr int NUM_CELLS = 151;

std::mt19937_64 rng;

double worst_best_fitness;

// We use a system with okay-ish memory density. We represent the ternary as a
// 2-bit integer. This means we have 32 ternaries in a uint64_t.
//
// There are 3^7 possible states, requiring 4374 bits. We store this using 69
// uint64_ts, or little over half a kilobyte.

// Turn 7 cells into a state index, by encoding as ternary.
int state_index(const int* cells) {
    int idx = 0;
    for (int i = 0; i < 7; ++i) {
        idx *= 3;
        idx += cells[6-i];
    }
    return idx;
}

// Get/set a ternary by index from a 2-bit-per-ternary encoded uint64_t array.
int get_ternary(const uint64_t* a, size_t idx) {
    return (a[idx/32] >> (2*(idx % 32))) & 0x3;
}

void set_ternary(uint64_t* a, size_t idx, int val) {
    assert(val < 3);
    int shift = 2*(idx % 32);
    uint64_t shifted_val = uint64_t(val) << shift;
    uint64_t shifted_mask = ~(uint64_t(0x3) << shift);
    a[idx/32] = (a[idx/32] & shifted_mask) | shifted_val;
}

struct Rule {
    uint64_t data[69];
    double cached_fitness;

    Rule(const char* init) {
        cached_fitness = -1;
        for (auto i : op::range(69)) data[i] = 0;
        for (auto i : op::range(2187)) set_ternary(data, i, init[i] - '0');
    }

    double fitness(int num_tests = 1000);

    Rule* random_mutation(int num_mutate) const {
        auto new_rule = new Rule(*this);

        auto r = op::range(2187);
        std::vector<int> indices;
        op::random_sample(r.begin(), r.end(),
                          std::back_inserter(indices), num_mutate, rng);

        for (auto idx : indices) {
            set_ternary(new_rule->data, idx, op::randint(0, 2, rng));
        }

        new_rule->cached_fitness = -1;
        return new_rule;
    }

    int new_state(const int* cells) const {
        return get_ternary(data, state_index(cells));
    }

    void print_rule() const {
        for (auto i : op::range(2187)) {
            std::cout << get_ternary(data, i);
            if (i % 81 == 80) std::cout << "\n";
        }
    }
};

struct Automaton {
    uint64_t state[5];
    int plurality, generation;

    Automaton() : generation(0) {
        for (auto i : op::range(5)) state[i] = 0;

        int strict = 0;
        while (strict != 1) {
            int votes[3] = {};
            for (auto i : op::range(NUM_CELLS)) {
                int vote = op::randint(0, 2, rng);
                set_ternary(state, i, vote);
                votes[vote]++;
            }

            // Ensure strict plurality.
            plurality = std::max_element(votes, votes + 3) - votes;
            strict = 0;
            for (auto i : op::range(3)) strict += (votes[i] == votes[plurality]);
        }
    }

    void print_state() {
        for (int i = 0; i < 151; ++i) std::cout << get_ternary(state, i);
        std::cout << "\n";
    }

    bool concensus_reached() {
        int target = get_ternary(state, 0);
        for (auto i : op::range(NUM_CELLS)) {
            if (get_ternary(state, i) != target) return false;
        }

        return true;
    }

    void next_state(const Rule& rule) {
        uint64_t new_state[5] = {};

        std::vector<int> cells;
        for (auto r : op::range(-3, 4)) {
            cells.push_back(get_ternary(state, (r + NUM_CELLS) % NUM_CELLS));
        }

        for (auto i : op::range(NUM_CELLS)) {
            set_ternary(new_state, i, rule.new_state(cells.data()));
            cells.erase(cells.begin());
            cells.push_back(get_ternary(state, (i + 4) % NUM_CELLS));
        }

        for (auto i : op::range(5)) state[i] = new_state[i];
        generation++;
    }
};

double Rule::fitness(int num_tests) {
    if (cached_fitness == -1) {
        cached_fitness = 0;
        int num_two = 0;
        for (auto test : op::range(num_tests)) {
            Automaton a;
            while (a.generation < MAX_GENERATIONS && !a.concensus_reached()) {
                a.next_state(*this);
            }

            if (a.generation < MAX_GENERATIONS &&
                get_ternary(a.state, 0) == a.plurality &&
                a.plurality == 2) num_two++;

            cached_fitness += (a.generation < MAX_GENERATIONS &&
                               get_ternary(a.state, 0) == a.plurality);

            if (cached_fitness + (num_tests - test) < worst_best_fitness) break;
        }

        if (num_two) std::cout << cached_fitness << " " << num_two << "\n";

        cached_fitness;
    }

    return cached_fitness;
}

int main(int argc, char** argv) {
    std::random_device rd;
    rng.seed(42); // Seed with rd for non-determinism.

    const char* base =
        "000000000010010010000000000000000000000000000000000000000000000000010000000000000"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111000000000000011010000010000"
        "000000000010010010000000000000000000000000000000000000000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011011"
        "000000000010010010000000000000000000000000000000000000000000000000011010000010000"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011011"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111011111111111111111111111111"
        "000000000010010010000000000111111111111111111111111111010111011111111111011111111"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011010"
        "000000000010010010000000000111111111111111111111111111010111011111111111011111111"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000000000000011010000010000"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011011"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011010"
        "000000000010010010000000000111111111111111111111111111010111011111111111011111111"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000010000010011011000011010"
        "000000000010010010000000000111111111111111111111111111010011010011111111010111011"
        "000000000010010010000000000111111111111111111111111111000011010010111011010011012"
    ;

    // Simple best-only.
    std::vector<std::unique_ptr<Rule>> best_rules;
    best_rules.emplace_back(new Rule(base));
    worst_best_fitness = best_rules.back()->fitness();
    while (true) {
        const auto& base = *op::random_choice(best_rules.begin(), best_rules.end(), rng);
        std::unique_ptr<Rule> contender(base->random_mutation(op::randint(0, 100, rng)));

        // Sort most fit ones to the beginning.
        auto most_fit = [](const std::unique_ptr<Rule>& a, const std::unique_ptr<Rule>& b) {
            return a->fitness() > b->fitness();
        };

        if (contender->fitness() >= best_rules.back()->fitness()) {
            std::cout << contender->fitness();
            double contender_fitness = contender->fitness();
            best_rules.emplace_back(std::move(contender));
            std::sort(best_rules.begin(), best_rules.end(), most_fit);
            if (best_rules.size() > 5) best_rules.pop_back();
            std::cout << " / " << best_rules[0]->fitness() << "\n";
            worst_best_fitness = best_rules.back()->fitness();

            if (contender_fitness == best_rules.front()->fitness()) {
                best_rules.front()->print_rule();
            }
        }
    }

    return 0;
}

```
> 2 votes

# Answer
# Hand Coded, 57.541%

This actually only looks at the 5 cells above it. It could probably be improved by increasing the range it looks at. Ran with 100,000 test cases.

Algorithm:

```
If above == 0:
   if to the left there are only 2s or there is a 1 separated by 2s
       next state = 2
   else
       next state = 0
If above == 1:
   if to the right there are only 2s or there is a 0 separated by 2s
       next state = 2
   else
       next state = 1
If above == 2:
   ignore 0s to the left if the 0 is left of a 1 on the left
   ignore 1s to the right if the 1 is right of a 0 on the right
   if the closest 0 on the left is closer than the closest 1 on the right
       next state = 0
   else if the closest 1 on the right is closer than the closest 0 on the left
       next state = 1
   else
       next state = 2

```

Gene:

```
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222222222222
000000000222222222000222222111111111111111111111111111222111111111111111111111111
000000000222222222000222222111111111111111111111111111000000000111111111222111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222222222222
000000000222222222000222222111111111111111111111111111222111111111111111111111111
000000000222222222000222222111111111111111111111111111000000000111111111222111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222222222222222222222222222222000000000222222222222222222
000000000222222222000222222111111111111111111111111111222111111111111111111111111
000000000222222222000222222111111111111111111111111111000000000111111111222111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222
000000000222222222000222222111111111111111111111111111000222222111111111111111111
000000000222222222000222222222222222222222222222222222000000000222222222000222222

```

Testing code:

```
import java.lang.Math.*
import java.util.*

const val RADIUS = 3;
const val STATES = 3;
const val DIAMETER = 2 * RADIUS + 1
const val TAPE_LENGTH = 151

val CODE_SIZE = pow(STATES.toDouble(), DIAMETER.toDouble()).toInt()

const val GRADE_RUNS = 100000
const val GRADE_MAX_TIME = 10000

operator fun IntArray.inc() : IntArray {
    val next = this.clone()
    var i = 0
    while (i < size) {
        if (this[i] == STATES - 1) {
            next[i] = 0
        } else {
            next[i]++
            break
        }
        i++
    }
    return next
}
val IntArray.index : Int
    get() {
        var total = 0
        for (i in (size - 1) downTo 0) {
            total *= STATES
            total += this[i]
        }
        return total
    }

interface IRule {
    operator fun get(states : IntArray) : Int
}

fun IntArray.equalsArray(other: IntArray) = Arrays.equals(this, other)

class Rule : IRule {

    constructor(rule : IRule) {
        val start = IntArray(DIAMETER)
        var current = start.clone()

        code = IntArray(CODE_SIZE)
        try {
            do {
                code[current.index] = rule[current]
                current++
            } while (!current.equalsArray(start));
        } catch (e : Throwable) {
            println(Arrays.toString(code))
            println(Arrays.toString(current))
            throw e
        }
    }
    constructor(code : IntArray) {
        this.code = IntArray(CODE_SIZE) { if (it < code.size) code[it] else 0 }
    }

    val code : IntArray

    override fun get(states: IntArray) : Int {
        return code[states.index]
    }

    override fun toString() : String {
        val b = StringBuilder()
        for (i in 0 until CODE_SIZE) {
            if (i > 0 && i % pow(STATES.toDouble(), RADIUS.toDouble() + 1).toInt() == 0) {
                b.append('\n')
            }
            b.append(code[i])
        }
        return b.toString()
    }

    fun grade() : Double {
        var succeeded = 0
        for (i in 0 until GRADE_RUNS) {
            if (i % (GRADE_RUNS / 100) == 0) {
                println("${i/(GRADE_RUNS / 100)}% done grading.")
            }
            var tape : Tape
            do {
                tape = Tape()
            } while (tape.majority() == -1);
            val majority = tape.majority()
            val beginning = tape
            var j = 0
            while (j < GRADE_MAX_TIME && !tape.allTheSame()) {
                tape = tape.step(this)
                j++
            }
            if (tape.stabilized(this) && tape.majority() == majority) {
                succeeded++
            }/* else if (beginning.majority() != 2) {
                println(beginning.majority())
                tape = beginning
                for (j in 1..100) {
                    println(tape)
                    tape = tape.step(this)
                }
                println(tape)
            }*/
        }
        return succeeded.toDouble() / GRADE_RUNS
    }

}

fun getRandomState() : Int {
    return (random() * STATES).toInt()
}

class Tape(val tape : IntArray) {

    constructor() : this(IntArray(TAPE_LENGTH) { getRandomState() } )

    fun majority() : Int {
        val totals = IntArray(STATES)

        for (cell in tape) {
            totals[cell]++
        }

        var best = -1
        var bestScore = -1

        for (i in 0 until STATES) {
            if (totals[i] > bestScore) {
                best = i
                bestScore = totals[i]
            } else if (totals[i] == bestScore) {
                best = -1
            }
        }

        return best
    }

    fun allTheSame() : Boolean {
        for (i in 1 until TAPE_LENGTH) {
            if (this[i] != this[0]) {
                return false
            }
        }
        return true
    }

    operator fun get(index: Int) = tape[((index % TAPE_LENGTH) + TAPE_LENGTH) % TAPE_LENGTH]

    fun step(rule : IRule) : Tape {
        val nextTape = IntArray ( TAPE_LENGTH )

        for (i in 0 until TAPE_LENGTH) {
            nextTape[i] = rule[IntArray(DIAMETER) { this[i + it - RADIUS] }]
        }

        return Tape(nextTape)
    }

    fun stabilized(rule : IRule) = allTheSame() && majority() == step(rule).majority()

    override fun toString() : String {
        val b = StringBuilder()
        for (cell in tape) {
            b.append(cell)
        }
        return b.toString()
    }

}

fun main(args : Array<String>) {
    val myRule = Rule(object : IRule {
        override fun get(states: IntArray): Int {
            if (states[3] == 0) {
                if (states[2] == 1) {
                    return 2
                } else if (states[2] == 0) {
                    return 0
                } else if (states[1] == 1) {
                    return 2
                } else if (states[1] == 0) {
                    return 0
                } else {
                    return 2
                }
            } else if (states[3] == 1) {
                if (states[4] == 0) {
                    return 2
                } else if (states[4] == 1) {
                    return 1
                } else if (states[5] == 0) {
                    return 2
                } else if (states[5] == 1) {
                    return 1
                } else {
                    return 2
                }
            } else {
                if (states[2] == 0) {
                    if (states[4] != 1) {
                        return 0
                    }
                } else if (states[4] == 1) {
                    return 1
                }
                if (states[1] == 0 && states[2] != 1) {
                    if (states[5] != 1) {
                        return 0
                    }
                } else if (states[5] == 1 && states[4] != 0) {
                    return 1
                }
                return 2
            }
        }

    })
    var tape = Tape()
    println(myRule.grade())
}

```

Example
> 0 votes

---
Tags: code-challenge, optimization, cellular-automata
---


title: Crunch vowels out of a string

text:
# Question
Title: Crunch vowels out of a string
# Task description

Sometimes, you really need to fit something you’re writing in a small space. It may be tempting to drop the vowels and wrt lk ths – and failing that, who really needs spaces? Thssprfctlrdbl!

Write a function or program that removes lowercase vowels `aeiou`, and then spaces, and then *any* characters from an **input string**. Furthermore, each time you remove a character, it must be the **rightmost** character eligible for removal. It must repeat this process until the string is **no longer than some given input length**.

<sup>† “This is perfectly readable!” But if you’re reading this footnote, it probably isn’t, really... :)</sup>

# Examples

Here, you can see this process applied for successively smaller input sizes:

```
23: Hello, Code Golf World!
22: Hello, Code Golf Wrld!
21: Hello, Code Glf Wrld!
20: Hello, Cod Glf Wrld!
19: Hello, Cd Glf Wrld!
18: Hell, Cd Glf Wrld!
17: Hll, Cd Glf Wrld!
16: Hll, Cd GlfWrld!
15: Hll, CdGlfWrld!
14: Hll,CdGlfWrld!
13: Hll,CdGlfWrld
12: Hll,CdGlfWrl
11: Hll,CdGlfWr
(etc.)

```

After squeezing the string down to 17 characters, we run out of vowels to remove, so the next character we remove is the rightmost space; when we hit 14 characters, we’ve removed all vowels *and* spaces, so we simply start munching the string from right to left.

Here is some ~~pseudocode~~ Python code that solves this challenge:

```
def crunch_string(string, to_length):
    while len(string) > to_length:
        # Store the best candidate index for deletion here.
        best = None

        # First, find the rightmost vowel's index.
        for i in range(len(string)):
            if string[i] in 'aeiou':
                best = i

        # If there were no vowels, find the rightmost space's index.
        if best is None:
            for i in range(len(string)):
                if string[i] == ' ':
                    best = i

        # If there were no spaces either, use the final index.
        if best is None:
            best = len(string) - 1

        # Remove the selected character from the string.
        string = string[:best] + string[best + 1:]

    # Return the string once `len(string) <= to_length`.
    return string

```

# Rules

* This is , so the shortest code in bytes wins.
* The input string will consist of the printable ASCII characters from space (, decimal 32) up to and including tilde (`~`, decimal 126). There will be no uppercase vowels `AEIOU` in the string. In particular, there will be no Unicode, tabs, or newlines involved.
* Call the input string *s*, and the input target length *t*. Then 0 \< t ≤ length(*s*) ≤ 10000 is guaranteed. (In particular, the input string will never be empty. If *t* = length(*s*), you should just return the string unmodified.)

# Test cases

```
Input:  50, Duis commodo scelerisque ex, ac consectetur metus rhoncus.
Output: Duis commodo scelerisque ex, ac cnscttr mts rhncs.

Input:  20, Maecenas tincidunt dictum nunc id facilisis.
Output: Mcnstncdntdctmnncdfc

Input:  150, golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf
Output: glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glf glfglfglfglfglfglfglfglfglfglf

```

# Answer
> 6 votes
# MATL, 20 bytes

```
t11Y2mEG32=+K#Si:)S)

```

**Try it online!**

```
t       % implicitly input string. Duplicate
11Y2    % predefined literal 'aeiou'
m       % ismember. Gives true for input characters that are vowels
E       % multiply by 2
G       % push input string again
32      % ASCII for space
=       % gives true for input characters that are spaces
+       % add: gives 2 for vowels, 1 for space, 0 for non-vowels-and-non space
K#S     % sort and push only the indices of the sorting. Sorting is stable, so first
        % will be non-vowels-and-non space characters in their original order, then
        % spaces in their original order, then vowels in their original order
i       % input number n of characters that should be kept
:       % range [1,2,...,n]
)       % index with that: keep first n indices of the sorting
S       % sort those indices to restore their original order
)       % index into input string to keep only those characters. Implicitly display

```

# Answer
> 11 votes
# Perl, ~~48~~ ~~45~~ 43 bytes

Includes +4 for `-Xlpi` (-X can be left out but leaves ugly warnings on STDERR)

Run with the number after the `-i` option and the input on STDIN (supports multiple lines too). e.g. `perl -Xlpi50 crunch.pl <<< "Duis commodo scelerisque ex, ac consectetur metus rhoncus."`

`crunch.pl`:

```
s/.*\K[aeiou]|.*\K |.$// while pos=-$^I

```

# Answer
> 6 votes
# JavaScript (ES6), ~~66~~ 61 bytes

*Saved 5 bytes thanks to @Neil*

```
f=(s,n)=>s[n]?f(s.replace(/(.*)[aeiou]|(.*) |.$/,"$1$2"),n):s

```

I don't think the regex is golfable further. Surprisingly, the shortest I can come up with to remove front-to-back is a byte longer:

```
f=(s,n)=>s[n]?f(s.replace(/(.*?)[aeiou]|(.*?) |./,"$1$2"),n):s

```

### More interesting attempt (ES7), 134 bytes

```
(s,n,i=0)=>[for(c of s)[/[aeiou]/.test(c)*2+(c<'!'),i++,c]].sort(([x],[y])=>x-y).slice(0,n).sort(([,x],[,y])=>x-y).map(x=>x[2]).join``

```

This uses an approach similar to the MATL answer.

# Answer
> 2 votes
# sh + gnu sed, ~~78~~ 61

Supply the string to `STDIN`, the length as first argument.

```
rev|sed -r ":                       # reverse + invoke sed + jump label ":"
/..{$1}/!q                          # if the length is not greater $1, quit
p                                   # print
s/[aeiou]//                         # delete the first vowel
t                                   # if successful, start over at ":"
s/ //                               # delete the first space
t                                   # if successful, start over at ":"
s/.//                               # delete the first character
t"|rev                              # if successful, start over at ":" + reverse

```

# Answer
> 1 votes
# Perl, 68

Removing from the right adds a ton of characters, maybe there is a better way to do this.

```
$_=reverse;while(length>$^I){s/[aeiou]//||s/ //||s/.//}$_=reverse

```

Use `-i` to input the number. It is 65 characters plus 3 for the `i`, `p`, and `l` on the command line.

Run with:

```
echo 'Hello, Code Golf World!' | perl -i13 -ple'$_=reverse;while(length>$^I){s/[aeiou]//||s/ //||s/.//}$_=reverse'

```

# Answer
> 1 votes
## Java 8, 303 bytes

```
(s,j)->{String t="";for(int i=s.length()-1;i>=0;t+=s.charAt(i--));while(t.length()>j&&t.matches(".*[aeiou].*"))t=t.replaceFirst("[aeiou]","");while(t.length()>j&&t.contains(" "))t=t.replaceFirst("\\s","");s="";for(int i=t.length()-1;i>=0;s+=t.charAt(i--));return s.substring(0,Math.min(t.length(),j));};

```

This is WAY too long. Ill try to shorten it soon. It would be much shorter if java had a method for reversing strings and backward replacements.

Test with the following:

```
public class StringCruncher {
    public static void main(String[] args) {
        Tester test = (s,j)->{String t="";for(int i=s.length()-1;i>=0;t+=s.charAt(i--));while(t.length()>j&&t.matches(".*[aeiou].*"))t=t.replaceFirst("[aeiou]","");while(t.length()>j&&t.contains(" "))t=t.replaceFirst("\\s","");s="";for(int i=t.length()-1;i>=0;s+=t.charAt(i--));return s.substring(0,Math.min(t.length(),j));};
        System.out.println(test.crunch("golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf", 150));
    }
}
interface Tester {
    String crunch(String s, int j);
}

```

# Answer
> 1 votes
# Scala, 160 bytes

```
type S=String;def f(s:S,l:Int)={def r(s:S,p:S):S=if(s.size>l){val j=s.replaceFirst("(?s)(.*)"+p,"$1");if(j==s)s else r(j,p)}else s;r(r(r(s,"[aeiou]")," "),".")}

```

Tester:

```
val t="Hello, Code Golf World!"
println((t.size to 11 by -1).map(f(t,_)).mkString("\n"))

```

# Answer
> 1 votes
**C#, 180 bytes**

```
string c(int l,string s){while(s.Length>l){int i=0;Func<string,bool>f=t=>(i=s.LastIndexOfAny(t.ToCharArray()))!=-1;if(!(f("aeiou")||f(" ")))i=s.Length-1;s=s.Remove(i,1);}return s;}

```

Tester:

```
using System;
class Crunch
{
    static int Main()
    {
        var x = new Crunch();
        Console.WriteLine(x.c(50, "Duis commodo scelerisque ex, ac consectetur metus rhoncus."));
        Console.WriteLine(x.c(20, "Maecenas tincidunt dictum nunc id facilisis."));
        Console.WriteLine(x.c(150, "golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf golf"));
        Console.Read();
        return 0;
    }
    string c(int l,string s){while(s.Length>l){int i=0;Func<string,bool>f=t=>(i=s.LastIndexOfAny(t.ToCharArray()))!=-1;if(!(f("aeiou")||f(" ")))i=s.Length-1;s=s.Remove(i,1);}return s;}

    static string crunch(int len, string str)
    {
        Console.WriteLine($"{str.Length}: {str}");
        while (str.Length > len) {
            int idx=0;
            Func<string,bool> f = s => (idx = str.LastIndexOfAny(s.ToCharArray()))!= -1;
            if (!(f("aeiou") || f(" "))) idx = str.Length-1;
            str = str.Remove(idx,1);
            Console.WriteLine($"{str.Length}: {str}");
        }
        return str;
    }
}

```

# Answer
> 1 votes
# Dyalog APL, ~~77~~ ~~45~~ 42 bytes

```
t[⌽i~⌽⎕↓⌽∪∊(t∊'aeiou')(' '=t)1/¨⊂i←⍳⍴t←⌽⍞]

```

`t[``]` letters of *t* with indices...
`t←⌽⍞` *t* gets reversed text input
`i←⍳⍴t` *i* gets indices of length of *t*
`/¨⊂i` multiple (3) boolean selections of elements of *i*:
1. `(t∊'aeiou')` boolean where vowel
2. `(' '=t)` boolean where space
3. `1` all `∪∊` unique of the enlisted (flattened) 3 selections
`⌽⎕↓⌽` drop last evaluated-inputted characters (same as `(-⎕)↓`)
`⌽i~` reverse the remaining indices after removing some

---

Original answer:

```
⎕{⍺≥≢⍵:⌽⍵⋄∨/⍵∊⍨v←'aeiou':⍺∇⍵/⍨~<\(⍳⍴⍵)∊⍵⍳v⋄' '∊⍵:⍺∇⍵/⍨~<\(⍳⍴⍵)=⍵⍳' '⋄⍺∇1↓⍵}⌽⍞

```

Ehm, yeah, that *is* a bit hard to read. Basically the direct translation of OP into APL:

1. Reverse input.
2. If required length is longer or equal to the count of (reversed) input string, then return reversed (reversed) argument.
3. Else, if argument has any vowel, remove the first (i.e. last) one and call recursively on what remains.
4. Else, if argument has any space, remove the first (i.e. last) one and call recursively on what remains.
5. Else, remove the first (i.e. last) character and call recursively on what remains.

# Answer
> 1 votes
# Lua, 120 bytes

```
s=arg[2]:reverse()a=s:len()-arg[1]s,n=s:gsub('[aeiou]','',a)s,m=s:gsub(' ','',a-n)print(s:gsub('.','',a-n-m):reverse())

```

Takes input as command line arguments, in the format `lua crunch.lua 10 "This is a string"`, with output `Ths sstrng`.

Explanation:

```
-- Set 's' to the reverse of the string
s=arg[2]:reverse()
-- Set 'a' to the number of characters to be removed
a=s:len()-arg[1]
-- Remove 'a' vowels, set 'b' to the number of substitutions
s,b=s:gsub('[aeiou]','',a)
-- Remove 'a-b' spaces, set 'c' to the number of substitutions
s,c=s:gsub(' ','',a-b)
-- Remove 'a-b-c' characters, and print the now un-reversed string
print(s:gsub('.','',a-b-c):reverse())

```

# Answer
> 0 votes
# Mathematica, 201 Bytes

```
f@x_:=StringReplaceList[x,"a"|"e"|"i"|"o"|"u"->""];g@x_:=StringReplaceList[x," "->""];x_~l~y_:=NestWhile[If[f@#!={},Last@f@#,If[g@#!={},Last@g@#,Last@StringReplaceList[#,_->""]]]&,x,StringLength@#!=y&]

```

There must be a better way than this..

# Answer
> 0 votes
# R, ~~169~~ 143 bytes

```
function(x,y){d=utf8ToInt(x);o=c(rev(which(d%in%utf8ToInt('aeiou'))),rev(which(d==32)));intToUtf8(d[sort(tail(c(o,setdiff(nchar(x):1,o)),y))])}

```

\*edit saved 36 bytes through rewrite with `utf8ToInt` -\> `intToUtf8` conversions not `strstplit` and `paste0(...,collapse)`

ungolfed with explanation

```
function(x,y){d=utf8ToInt(x);         # convert string (x) to integer
o=c(
 rev(which(d%in%utf8ToInt('aeiou'))), # index of vowels (reversed)
 rev(which(d==32)));                  # index of spaces
 intToUtf8(d[                         # convert subset back to character
   sort(tail(                         # return the first y index of
                                      # "left over" characters
   c(o,setdiff(nchar(x):1,o))         # combine vowels, spaces and
                                      # other indices in appropriate order
  ,y))])}

```

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


# Question
Title: Reproportioning a population by adding fixed sized groups
## Introduction

Say you have a population of people. This population is made up of 100 Alices and 25 Bobs. So, 80% of the population are Alices and 20% are Bobs. We want to change the proportional makeup of the population to be 62% Alices and 38% Bobs.

## Rules

1. You can only add to the population. You cannot take any away from the starting population.
2. You can only add in multiples of the original subpopulation size. So following the above example, you can only add batches of 100 Alices to the group; likewise, you can only add batches of 25 Bobs to the group.
3. You have a pool of unlimited Alices and Bobs that are not in the population yet.
4. The algorithm must be able to handle N different name groups (e.g. N=4: Alice, Bob, Carol, David).

### Pseudocode framework

```
# 100 Alices, 25 Bobs, 35 Carols, 60 Davids
starting_population = (100, 25, 35, 60)

# Goal percentages, must sum to 100
reproportion_goal = (10, 20, 30, 40)

# Reproportion the population to meet the goal percentages, following the rules
new_population = reproportion_population(starting_population, reproportion_goal)

```

## Winner

Create an algorithm to re-proportion the population following the rules with an arbitrary starting\_population and reproportion\_goal.

The winning algorithm will solve the above-quoted problem in the fastest time on a single-core single-CPU i686 system with fixed clock speed. The algorithm must also solve other reasonable cases through the same code-path. That is, do not special-case for the example data.

I will use many thousands of iterations to test the timing of the approach. VM/runtime startup times will not be counted. The algorithm will be warmed up before timing starts. You can specify the specific version of framework you would like me to run your code under, and if I can reasonably set it up, I will.

## Introduction

Say you have a population of people. This population is made up of 100 Alices and 25 Bobs. So, 80% of the population are Alices and 20% are Bobs. We want to change the proportional makeup of the population to be 62% Alices and 38% Bobs.

## Rules

1. You can only add to the population. You cannot take any away from the starting population.
2. You can only add in multiples of the original subpopulation size. So following the above example, you can only add batches of 100 Alices to the group; likewise, you can only add batches of 25 Bobs to the group.
3. You have a pool of unlimited Alices and Bobs that are not in the population yet.
4. The algorithm must be able to handle N different name groups (e.g. N=4: Alice, Bob, Carol, David).

### Pseudocode framework

```
# 100 Alices, 25 Bobs, 35 Carols, 60 Davids
starting_population = (100, 25, 35, 60)

# Goal percentages, must sum to 100
reproportion_goal = (10, 20, 30, 40)

# Reproportion the population to meet the goal percentages, following the rules
new_population = reproportion_population(starting_population, reproportion_goal)

```

## Winner

Create an algorithm to re-proportion the population following the rules with an arbitrary starting\_population and reproportion\_goal.

The winning algorithm will solve the above-quoted problem in the fastest time on a single-core single-CPU i686 system with fixed clock speed. The algorithm must also solve other reasonable cases through the same code-path. That is, do not special-case for the example data.

I will use many thousands of iterations to test the timing of the approach. VM/runtime startup times will not be counted. The algorithm will be warmed up before timing starts. You can specify the specific version of framework you would like me to run your code under, and if I can reasonably set it up, I will.

### Dates (deadline and winner)

Deadline for submissions is before March 14, 2016. I will post benchmarks by March 20. Feel free to answer after these dates, but I can't commit to re-benchmarking submissions after March 14.

# Answer
# C

```
void reproportion(
        const unsigned int n,
        const unsigned int *const starting_population,
        const unsigned int *const reproportion_goal,
        unsigned int *const new_population)
{
    unsigned int unit = 1U;

    for(unsigned int i = 0U; i != n; ++i) {
        unit *= starting_population[i];
    }

    for(unsigned int i = 0U; i != n; ++i) {
        new_population[i] = reproportion_goal[i] * unit;
    }
}

```

This assumes that the original subpopulation sizes are greater than zero. `starting_population = { 0, 1, 2 }` and `reproportion_goal = { 0, 50, 50 }` would give the incorrect result of `new_population = { 0, 0, 0 }`. If the original subpopulation size can be zero, `unit *= starting_population[i];` should be preceded by `if(starting_population[i] != 0U)`.

Call this function from within your program like so:

```
#include <stdio.h>

int main(void)
{
    unsigned int starting_population[] = { 1, 2, 31, 4 };
    unsigned int reproportion_goal[] = { 25, 25, 40, 10 };
    unsigned int new_population[4];

    reproportion(4, starting_population, reproportion_goal, new_population);

    for(int i = 0; i < 4; ++i) {
        printf("%d ", new_population[i]);
    }
}

```
> 6 votes

# Answer
# Javascript ES6

I'm not really sure how you time these things but here's what I have

```
(p,g)=>g.map(_=>_*m,m=p.reduce((l,o)=>o*l))

```

the instinct to use

```
(p,g)=>g.map(_=>_*p.reduce((l,o)=>o*l))

```

to save a few bytes is overwhelming, but I suspect js isn't smart enough to reuse the p.reduce for each iteration

\[I know this gives back larger than necessary solutions, but I don't think that a minimal solution was a requirement :) \]

Usage

```
f=(p,g)=>g.map(_=>_*m,m=p.reduce((l,o)=>o*l))

f([100, 25],[62, 38])
//outputs [155000, 95000]
//sum of those is 250000

//155000/250000 = 0.62

f([100, 25, 35, 60] ,[10, 20, 30, 40])
//outputs [52500000, 105000000, 157500000, 210000000]
//sum of those is 525000000

```
> 1 votes

# Answer
# Matlab

This function is very fast, but doesn't return the minimal solution

```
function s=reproportion_population(a,T)
s=prod(lcm(a,T)).*T;

```

This version returns the minimal solution.

```
function s=reproportion_population(a,T)
L=lcm(a,T);
g=prod(L)./a;
r=g(1);
rt=T(1);
for i=1:numel(g)-1
    r=gcd(r,g(i+1));
    rt=gcd(rt,T(i+1));
end
s=g./r.*a.*T/rt;

```

Usage is, for both versions, `new_population = reproportion_population(starting_population, reproportion_goal)`, for example,

```
reproportion_population([100 25],[62 38])

```

which returns `[182590000 111910000]` (first version) or `[3100 1900]` (second version), or

```
reproportion_population([100 25 35 60],[10 20 30 40])

```

which returns `[2520000000 5040000000 7560000000 10080000000]` (first version) `[2100 4200 6300 8400]` (second version).

If you don't have Matlab, it should work as-is in Octave, although you need to need to add `endfunction` at the end of the file (I think---I don't have Octave).
> 1 votes

# Answer
# Rust

To change the cases, simply change the numbers in the vectors (if you want commandline arguments instead, I can do that). On my computer I ran

```
time for i in {1..1000}; do target/release/population > /dev/null; done;

```

and got the output

```
real    0m4.202s
user    0m0.748s
sys 0m3.613s

```

I'm not sure how much actual optimization there is to be done, and how much will even show because its so fast.

```
fn reproportion_population(
    starting_population: &Vec<usize>,
    reproportion_goal: &Vec<usize>,
) -> Vec<usize> {
    let mut prod: usize = 1;
    let mut size: usize = 0;

    for i in starting_population {
        size += 1;
        prod *= *i;
    }

    let mut answers: Vec<usize> = vec![0; size];

    for i in 0..size {
        answers[i] = reproportion_goal[i] * prod;
    }

    answers
}

fn main() {
    let starting_population: Vec<usize> = vec![100, 25, 35, 60, 100];

    let reproportion_goal: Vec<usize> = vec![10, 20, 30, 30, 10];

    let answers: Vec<usize> = reproportion_population(&starting_population, &reproportion_goal);

    /*
    // the following prints out POPULATION: PERCENT with a newline for each pop.
    // the percent is given as a decimal.

    let mut total: usize = 0;
    for i in 0..reproportion_goal.len() {
        total += answers[i];
    }
    for i in 0..reproportion_goal.len() {
        println!("{}: {}", answers[i], (answers[i] as f64)/(total as f64));
    }
    */
}

```

To compile (after rust+cargo are installed) run `cargo build --release`. To run `./target/release/<binary_name>`.
> 1 votes

# Answer
## Python

Assuming that any valid solution is acceptable, and not the minimal solution...

```
def reproportion_pop(start_pop, pop_goal):
 import operator
 reduced = reduce(operator.mul, start_pop)
 new_pop = []
 for x in range(len(start_pop)):
  new_pop.append(reduced*pop_goal[x])
 return new_pop

```

This can be put in a .py file, pasted into an interpreter, or run Here, whichever you prefer.

Function call is in the form of `reproportion_pop(list_of_start_pop, list_of_pop_goal)`

Examples:

```
> reproportion_pop([100,25],[62,38])
[155000, 95000]

> reproportion_pop([100,25,35,60],[10,20,30,40])
[52500000, 105000000, 157500000, 210000000]

```
> 1 votes

---
Tags: fastest-code
---


title: ValiDate ISO 8601 by RX

text:
# Question
Title: ValiDate ISO 8601 by RX
# Challenge

Find the shortest regex that

1. validates, i.e. matches, every possible date in the *Proleptic* Gregorian calendar (which also applies to all dates before its first adoption in 1582) and
2. does not match any invalid date.

## Output

Output is therefore truthy or falsey.

## Input

Input is in any of 3 expanded ISO 8601 date formats – no times.

The first two are `±YYYY-MM-DD` (year, month, day) and `±YYYY-DDD` (year, day). Both need special-casing for the leap day. They are naively matched separately by these extended RXs:

```
(?<year>[+-]?\d{4,})-(?<month>\d\d)-(?<day>\d\d)
(?<year>[+-]?\d{4,})-(?<doy>\d{3})

```

The third input format is `±YYYY-wWW-D` (year, week, day). It is the complicated one because of the complex leap week pattern.

```
(?<year>-?\d{4,})-W(?<week>\d\d)-(?<dow>\d)

```

A basic, but insufficient validity check for all three combined would look something like this:

```
[+-]?\d{4,}-((0\d|1[0-2])-([0-2]\d|3[01]) ↩
            |([0-2]\d\d|3[0-5]\d|36[0-6]) ↩
            |(W([0-4]\d|5[0-3])-[1-7]))

```

# Conditions

A **leap year** in the Proleptic Gregorian calendar contains the **leap day** `…-02-29` and thus it is 366 days long, hence `…-366` exists. This happens in any year whose ordinal number is divisible by 4, but not by 100 unless it’s also divisible by 400. **Year zero** exists in this calendar and it is a leap year.

A **long year** in the ISO week calendar contains a 53rd week, which one could term a “**leap week**”. This happens in all years where 1 January is a Thursday and additionally in all leap years where it’s a Wednesday. It turns out to occur every 5 or 6 years usually, in a seemingly irregular pattern.

A year has at least 4 digits. Years with more than 10 digits do not have to be supported, because that’s close enough to the age of the universe (ca. 14 billion years). The leading plus sign is optional, although the actual standard suggests it should be required for years with more than 4 digits.

Partial or truncated dates, i.e. with less than day-precision, must not be accepted.

The parts of the date notation, e.g. the month, do *not* have to be matched by a group that could be referenced.

# Rules

This is code-golf. The shortest regex without executed code wins. **Update:** You may use features like recursion and balanced groups, but will be fined by a factor of 10, which the character count then is multiplied with! This is now different from the rules in Hard code golf: Regex for divisibility by 7. Earlier answer wins a tie.

# Test cases

## Valid tests

```
2015-08-10
2015-10-08
12015-08-10
-2015-08-10
+2015-08-10
0015-08-10
1582-10-10
2015-02-28
2016-02-29
2000-02-29
0000-02-29
-2000-02-29
-2016-02-29
200000-02-29
2016-366
2000-366
0000-366
-2016-366
-2000-366
2015-081
2015-W33-1
2015-W53-7
 2015-08-10

```

The last one is optionally valid, i.e. leading and trailing spaces in input strings may be trimmed.

## Invalid formats

```
-0000-08-10     # that's an arbitrary decision
15-08-10        # year is at least 4 digits long
2015-8-10       # month (and day) is exactly two digits long, i.e. leading zero is required
015-08-10       # year is at least 4 digits long
20150810        # though a valid ISO format, we require separators; could also be interpreted as a 8-digit year
2015 08 10      # separator must be hyphen-minus
2015.08.10      # separator must be hyphen-minus
2015–08–10      # separator must be hyphen-minus
2015-0810
201508-10       # could be October in the year 201508
2015 - 08 - 10  # no internal spaces allowed
2015-w33-1      # letter ‘W’ must be uppercase
2015W33-1       # it would be unambiguous to omit the separator in front of a letter, but not in the standard
2015W331        # though a valid ISO format we require separators
2015-W331
2015-W33        # a valid ISO date, but we require day-precision
2015W33

```

## Invalid dates

```
2015        # a valid ISO format, but we require day-precision
2015-08     # a valid ISO format, but we require day-precision
2015-00-10  # month range is 1–12
2015-13-10  # month range is 1–12
2015-08-00  # day range is 1–28 through 31
2015-08-32  # max. day range is 1–31
2015-04-31  # day range for April is 1–30
2015-02-30  # day range for February is 1–28 or 29
2015-02-29  # day range for common February is 1–28
2100-02-29  # most century years are non-leap
-2100-02-29 # most century years are non-leap
2015-000    # day range is 1–365 or 366
2015-366    # day range is 1–365 in common years
2016-367    # day range is 1–366 in leap years
2100-366    # most century years are non-leap
-2100-366   # most century years are non-leap
2015-W00-1  # week range is 1–52 or 53
2015-W54-1  # week range is 1–53 in long years
2016-W53-1  # week range is 1–52 in short years
2015-W33-0  # day range is 1–7
2015-W33-8  # day range is 1–7

```

# Answer
# PCRE (also Perl), 778 bytes

```
/^([+-]?\d*((([02468][048]|[13579][26]|\d\d(?!00))([02468][048]|[13579][26]))|\d{4}(?!-02-29|-366))-((?!02-3|(0[469]|11)-31|000)((0[1-9]|1[012])-(0[1-9]|[12]\d|30|31)|([012]\d\d|3([0-5]\d|6[0-6])))|(W(?!00)([0-4]\d|51|52)-[1-7]))|((\+?\d*([02468][048]|[13579][26])|-\d*([02468][159]|[13579][37]))(04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99)|(\+?\d*([02468][159]|[13579][37])|-\d*([02468][26]|[13579][048]))(05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95)|(\+?\d*([02468][26]|[13579][048])|-\d*([02468][37]|[13579][159]))(01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96)|\+?\d*(([02468][37]|[13579][159])(03|14|20|25|31|36|42|53|59|64|70|76|81|87|92|[049]8))|-\d*(([02468][048]|[13579][26])([059]2|08|13|19|24|30|36|41|47|58|64|69|75|80|86|97)))-W53-[1-7])$/

```

I have included the delimiters in the byte count to show that it doesn't rely on any flags.

It does **not** match valid dates within other strings, such as `1234-56-89 2016-02-29 9876-54-32`. The regex is shorter by not checking for a maximum of 10 digits for the year.

Extended with comments:

```
/^  # Start of pattern (no leading space)
  (
    # YEAR
    # Optional sign and digits if more than 4 in year
    [+-]?\d*(
      # Years 00??, 04??, 08?? ... 92??, 96?? OR dd not followed by 00
      # followed by 00, 04, 08 ... 92, 96 OR
      (([02468][048]|[13579][26]|\d\d(?!00))([02468][048]|[13579][26])) |
      # any year not followed by 29 February or day 366
      \d{4}(?!-02-29|-366)
    # dash
    ) -
    # MONTH AND DAY, or DAY OF YEAR, or WEEK OF YEAR AND DAY if less than 53 weeks
    (
      # Not (30 or 31 February OR 31 April, June, September or December OR day 0)
      (?!02-3|(0[469]|11)-31|000)
      (
        # Month         dash         day         OR
        (0[1-9]|1[012]) - (0[1-9]|[12]\d|30|31) |
        # 001-299 OR 300-359 OR 360-366
        ([012]\d\d | 3([0-5]\d | 6[0-6]))
      # OR
      ) |
      (
        # W    01-52    dash    1-7
        W(?!00)([0-4]\d|51|52)-[1-7]
      )
    # OR
    ) |
    # WEEK OF YEAR AND DAY only if week is 53
    (
      # Optional plus and extra year digits
      \+?\d*(
        # Years +0303 - +9998
        ([02468][37]|[13579][159])(03|14|20|25|31|36|42|53|59|64|70|76|81|87|92|[049]8)
      ) |
      # Minus and extra year digits
      -\d*(
        # Years -0002 - -9697
        ([02468][048]|[13579][26])([059]2|08|13|19|24|30|36|41|47|58|64|69|75|80|86|97)
      ) |
      # Years +0004 - +9699, -0104 - -9799
      (\+?\d*([02468][048]|[13579][26])|-\d*([02468][159]|[13579][37]))
          (04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99) |
      # Years +0105 - +9795, -0205 - -9895
      (\+?\d*([02468][159]|[13579][37])|-\d*([02468][26]|[13579][048]))
          (05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95) |
      # Years +0201 - +9896, -0301 - -9996
      (\+?\d*([02468][26]|[13579][048])|-\d*([02468][37]|[13579][159]))
          (01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96)
    # dash W 53 dash 1-7
    )-W53-[1-7]
  # End of pattern (no trailing space)
  )$/x

```
> 4 votes

# Answer
# PCRE: ~~603~~ ~~940~~ ~~947~~ ~~949~~ 956 bytes

```
^\s*[+-]?(\d{4,10}-((00[1-9]|0[1-9]\d|[12]\d\d|3[0-5]\d|36[0-5])|(0[1-9]|1[0-2])-(0[1-9]|1\d|2[0-8])|(0[13-9]|1[0-2])-(29|30)|(0[13578]|1[02])-31|W(0[1-9]|[1-4]\d|5[0-2])-[1-7]))|((\d{2,8}([13579][26]|[2468][048]|0[48])|(\d{0,6}([13579][26]|[02468][048])00))-(366|02-29))|(\+?\d{0,6}(([02468][048]|[13579][26])([26]0|71|[38]2|[49]3|[05]4|15|[27]6|37|[48]8|[09]9)|([02468][159]|[13579][37])(50|[16]1|[27]2|33|[48]4|[09]5|[15]6|67|[27]8|[38]9)|([02468][26]|[13579][048])([48]0|[09]1|[15]2|63|[27]4|[38]5|[49]6|[05]7|[16]8|29)|([02468][37]|[13579][159])([27]0|[38]1|[49]2|[05]3|[16]4|25|[37]6|87|[049]8|[5]9))|-\d{0,6}(([02468][048]|[13579][26])(0[28]|1[39]|24|3[06]|4[17]|5[28]|6[49]|75|8[06]|9[27])|([02468][159]|[13579][37])(0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39])|([02468][26]|[13579][048])(0[51]|16|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95)|([02468][37]|[13579][159])(0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16])))-W53-[1-7]\s*$

```

**Note:** Some pairs of parentheses could possibly be dropped.

## Divisibility by 4

The multiples of 4 repeat in a simple pattern:

* 00, 04, 08, 12, 16,
20, 24, 28, 32, 36,
40, 44, 48, 52, 56,
60, 64, 68, 72, 76,
80, 84, 88, 92, 96, …

This, or the inverse, could be matched by a likewise simple regular expression for all two-digit numbers with leading zero:

```
(?<divisible-by-four>[13579][26]|[02468][048])
(?<not-divisible-by-four>[13579][048]|[02468][26]|\d[13579])

```

It could save some bytes if there were character classes for odd and even digits (like `\o` and `\e`), but there are not as far as I’m aware.

## Years

That expression would suffice for the Julian calendar, but the Gregorian leap year detection needs to special-case trailing `00` with century divisibility by 4:

```
(?<leap-year>[+-]?(\d{2,8}([13579][26]|[2468][048]|0[48])|(\d{0,6}([13579][26]|[02468][048])00))
(?<year>[+-]?\d{4,10})

```

This would need some changes to outlaw `-0000-…` (along with `-00000-…` etc.) or to enforce the plus sign for positive year numbers with more than 4 digits. The latter would be rather simple, but is not required:

```
(?<leap-year>([+-]?(\d\d([13579][26]|[2468][048]|0[48])|(([13579][26]|[02468][048])00)))|([+-](\d{3,8}([13579][26]|[2468][048]|0[48])|(\d{1,6}([13579][26]|[02468][048])00))))
(?<year>([+-]?\d{4})|([+-]\d{5,10}))

```

## Day of year

Three-digit ordinal dates are rather simple, we just have to restrict `-366` to leap years (and disallow `-000`).

```
(?<ordinal-day>-(00[1-9]|0[1-9]\d|[12]\d\d|3[0-5]\d|36[0-5]))
(?<ordinal-leap-day>-366)

```

## Day of month of year

The seven months with 31 days are `01` January, `03` March, `05` May, `07` July, `08` August, `10` October and `12` December. Just four month have exactly 30 days, `04` April, `06` June, `09` September and `11` November. Finally, `02` February has 28 days in common years and 29 in leap years. We can first construct a regular expression for the always valid days `01` through `28` and then add special cases.

```
(?<month-day>-(0[1-9]|1[0-2])-(0[1-9]|1\d|2[0-8]))
(?<short-month-day>-(0[13-9]|1[0-2])-(29|30))
(?<long-month-day>-(0[13578]|1[02])-31)
(?<month-leap-day>-02-29)

```

Neither month nor day must be `00` which was not covered by an earlier version.

## Day of week of year

All years include 52 weeks

```
(?<week-day>-W(0[1-9]|[1-4]\d|5[0-2])-[1-7])

```

Long years that include `-W53` repeat in a 400-year cycle, e.g. add 2000 for the current cycle and find the current year in the third entry:

* 004, 009, 015, 020, 026, 032, 037, 043, 048, 054, 060, 065, 071, 076, 082, 088, 093, 099,
* 105, 111, 116, 122, 128, 133, 139, 144, 150, 156, 161, 167, 172, 178, 184, 189, 195,
* 201, 207, 212, 218, 224, 229, 235, 240, 246, 252, 257, 263, 268, 274, 280, 285, 291, 296,
* 303, 308, 314, 320, 325, 331, 336, 342, 348, 353, 359, 364, 370, 376, 381, 387, 392, 398.

Each of the four centuries has a unique pattern. There is probably not much room for optimization.

1. `04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99`
2. `05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95`
3. `01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96`
4. `03|08|14|20|25|31|36|42|48|53|59|64|70|76|81|87|92|98`

We can group by either digit to find out that we can save two bytes or so:

* Grouped by 1st digit.
    1. `0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39]`
    2. `05|1[16]|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95`
    3. `0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16]`
    4. `0[38]|14|2[05]|3[16]|4[28]|5[39]|64|7[06]|8[17]|9[28]`
* Grouped by 2nd digit.
    1. `[26]0|71|[38]2|[49]3|[05]4|15|[27]6|37|[48]8|[09]9`
    2. `50|[16]1|[27]2|33|[48]4|[09]5|[15]6|67|[27]8|[38]9`
    3. `[48]0|[09]1|[15]2|63|[27]4|[38]5|[49]6|[05]7|[16]8|29`
    4. `[27]0|[38]1|[49]2|[05]3|[16]4|25|[37]6|87|[049]8|[5]9`

The century number is easily matched again by a variation of the divisibility expression.

* 1st century: `[02468][048]|[13579][26]`
* 2nd century: `[02468][159]|[13579][37]`
* 3rd century: `[02468][26]|[13579][048]`
* 4th century: `[02468][37]|[13579][159]`

So far, this does only work for positive years, including year zero. For negative years, we have to subtract the values from the list above from 400 and do the rest again, because the pattern is not symmetric.

1. `02|08|13|19|24|30|36|41|47|52|58|64|69|75|80|86|92|97`
2. `04|09|15|20|26|32|37|43|48|54|60|65|71|76|82|88|93|99`
3. `05|11|16|22|28|33|39|44|50|56|61|67|72|78|84|89|95`
4. `01|07|12|18|24|29|35|40|46|52|57|63|68|74|80|85|91|96`

or

1. `0[28]|1[39]|24|3[06]|4[17]|5[28]|6[49]|75|8[06]|9[27]`
2. `0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39]`
3. `0[51]|16|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95`
4. `0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16]`

## Putting it all together

### Any year

```
[+-]?\d{4,10}-((00[1-9]|0[1-9]\d|[12]\d\d|3[0-5]\d|36[0-5])|(0[1-9]|1[0-2])-(0[1-9]|1\d|2[0-8])|(0[13-9]|1[0-2])-(29|30)|(0[13578]|1[02])-31|W(0[1-9]|[1-4]\d|5[0-2])-[1-7])

```

### Leap-day year additions

```
[+-]?(\d{2,8}([13579][26]|[2468][048]|0[48])|(\d{0,6}([13579][26]|[02468][048])00))-(366|02-29)

```

### Leap-week year additions

```
+?\d{0,6}(([02468][048]|[13579][26])([26]0|71|[38]2|[49]3|[05]4|15|[27]6|37|[48]8|[09]9)|([02468][159]|[13579][37])(50|[16]1|[27]2|33|[48]4|[09]5|[15]6|67|[27]8|[38]9)|([02468][26]|[13579][048])([48]0|[09]1|[15]2|63|[27]4|[38]5|[49]6|[05]7|[16]8|29)|([02468][37]|[13579][159])([27]0|[38]1|[49]2|[05]3|[16]4|25|[37]6|87|[049]8|[5]9))-W53-[1-7]
-\d{0,6}(([02468][048]|[13579][26])(0[28]|1[39]|24|3[06]|4[17]|5[28]|6[49]|75|8[06]|9[27])|([02468][159]|[13579][37])(0[49]|15|2[06]|3[27]|4[38]|54|6[05]|7[16]|8[28]|9[39])|([02468][26]|[13579][048])(0[51]|16|2[28]|3[39]|44|5[06]|6[17]|7[28]|8[49]|95)|([02468][37]|[13579][159])(0[17]|1[28]|2[49]|35|4[06]|5[27]|6[38]|74|8[05]|9[16]))-W53-[1-7]

```
> 9 votes

---
Tags: code-golf, date, regular-expression
---


title: Diagram of a leaper

text:
# Question
Title: Diagram of a leaper
Given an input of a pair of nonnegative integers describing a leaper in chess, output a diagram of the squares to which the leaper can move.

From Wikipedia's description:

> An (m,n)-leaper is a piece that moves by a fixed type of vector between its start square and its arrival square. One of the coordinates of the vector 'start square – arrival square' must have an absolute value equal to m and the other one an absolute value equal to n. \[...\] For instance, the knight is the (1,2)-leaper.

In normal-people-speak, an (m,n)-leaper can move m squares in any direction, turn 90 degrees, and move n more squares. For example, a (1,2)-leaper (also known as the *knight*) can move to these squares:

```
.E.E.
E...E
..S..
E...E
.E.E.

```

where `S` represents the start square, `E` represents the end square, and `.` represents an empty square. This must also be your output for the input `1 2` (and `2 1`).

Specifically, the output must

* be a square grid with side length `max(m,n) * 2 + 1`.
* contain exactly one `S`, located in the center of the square.
* contain `E`s at the positions that a (m,n)-leaper at `S` could move to.
* contain dots (`.`) at all other positions.

You may assume that `m ≥ 0`, `n ≥ 0`, `m + n > 0`, and that `m` and `n` are integers.

Output may be a single string, an array of lines, or an array of arrays of characters.

Since this is , the shortest code in bytes will win.

Test cases (all test cases should work with input integers swapped as well):

```
4 1
...E.E...
.........
.........
E.......E
....S....
E.......E
.........
.........
...E.E...

2 2
E...E
.....
..S..
.....
E...E

3 0
...E...
.......
.......
E..S..E
.......
.......
...E...

1 1
E.E
.S.
E.E

0 1
.E.
ESE
.E.

12 13
.E.......................E.
E.........................E
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
.............S.............
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
...........................
E.........................E
.E.......................E.

```

# Answer
# Javascript, ~~153~~ 151 bytes

```
x=>y=>(G=(g,h)=>~[b-x,b+x][X='indexOf'](g)&&~[b-y,b+y][X](h),r=[...Array((b=x>y?x:y)*2+1)]).map((_,i)=>r.map((_,j)=>G(i,j)|G(j,i)?'E':b-i|b-j?'.':'S'))

```

Ungolfed with explanation:

```
f=                                     // saves the function in f
    x=>y=>(                            // currying the leaping numbers
        G=(g,h)=>                      // helper function
            ~[b-x,b+x][X='indexOf'](g) // check if g/x is in a goal square by x
                &&                     // and
            ~[b-y,b+y][X](h),          // if h/y is in a goal square by y
        r=[...Array(                   // row or column
            (b=x>y?x:y)*2+1            // of Math.max(x,y)*2+1 squares
        )]                             // stored in r
    ).map((_,i)=>                      // map r with i being the row index
        r.map((_,j)=>                  // for each row map a column with j being its index
            G(i,j)|G(j,i)              // if this square is one possible goal
                ?'E'                   // then 'E'
            :b-i|b-j                   // if is not the middle square
                ?'.'                   // then '.'
            :'S'                       // else 'S'
        )                              // end/next column setup
    )                                  // end function

P.addEventListener('click',_=>(
    a=I.value.split`,`,
    O.innerHTML=f(+a[0])(+a[1]).map(x=>x.join``).join`\n`
));
```

```
<input id=I value="1,2"><button id=P>Play</button><pre id=O>
```
> 1 votes

---
Tags: code-golf, ascii-art, grid, chess
---


title: Fairy chess "leaper" movement patterns

text:
# Question
Title: Fairy chess "leaper" movement patterns
A leaper is a category of fairy chess piece which moves by "jumping." A normal knight is a (1,2)-leaper, meaning each move involves moving a distance of 1 square in an orthogonal direction and 2 squares in the perpendicular direction.

```
.o.o.
o...o
..N..
o...o
.o.o.

```

There are many different leapers. The (1,3)-leaper is called the Long Knight, or Camel. Its move pattern looks like this:

```
..o.o..
.......
o.....o
...L...
o.....o
.......
..o.o..

```

There's also the (2,2) Alfil...

```
o...o
.....
..A..
.....
o...o

```

...and even the (0,1) Wazir.

```
.o.
oWo
.o.

```

## Challenge

Given a pair of numbers as input, output the corresponding movement diagram. You may write a program or function, with input provided via STDIN/command-line or as an argument, and output provide by STDOUT or the return value. This is **code-golf**.

**Input**

Input will be a comma-separated list of two integers and an uppercase letter. The two integers will be in the range `0-7` (inclusive) and in non-decreasing order. Trailing newline optional for input and output.

Here are the inputs for the above four examples:

```
1,2,N
1,3,L
2,2,A
0,1,W

```

**Output**

Output will be a square-shaped multiline string. The capital letter will be placed in the center to represent the current location of the piece. The movement locations will be represented by either 4 or 8 lowercase `o`s. All other spaces in the square will be filled with periods.

If the movement pattern is `0,0`, output just the capital letter.

As a hint, if the second integer (the larger one) has value N, then the square will always have side length 2N+1. The `o`s will always be on the perimeter of the square.

## Additional Testcases

```
1,1,F

o.o
.F.
o.o

5,7,Q

..o.........o..
...............
o.............o
...............
...............
...............
...............
.......Q.......
...............
...............
...............
...............
o.............o
...............
..o.........o..

0,0,J

J

```

# Answer
# Ruby,107

```
->a,b,n{(-b..b).map{|i|s='..'*b+?.
i%b==0&&(i==0?s[b]=n :s[b+a]=s[b-a]=?o)
i.abs==a&&s[0]=s[-1]=?o
puts s}}

```

Ungolfed in test program

```
f=->a,b,n{
  (-b..b).map{|i|                           #iterate from -i to i (lines of grit)
    s='..'*b+?.                             #make a string of 2n+1 .'s
    i%b==0&&(i==0?s[b]=n :s[b+a]=s[b-a]=?o) #if i%b=0 plot the centre character (if i=0) or the o's on the top and bottom rows
    i.abs==a&&s[0]=s[-1]=?o                 #if i.abs=a plot the o's in left and right columns
    puts s                                  #having substituted the .'s with o and centre as necessary, output the current line
  }
}

a=gets.to_i
b=gets.to_i
n=gets.chop
f[a,b,n]

```
> 2 votes

# Answer
# Pyth, 40 bytes

```
JASv<2zFZK+rH_1SHFY,LZKp?qJSY\o?sY\.ez)k

```

I'm learning Pyth! Try it out.

## Explanation

```
J             J =
 A                (G, H) =
  S                        sorted(
   v<2z                           eval(input[:-2]))

FZK+rH_1SH    for Z in K = [H, H-1, ..., 0] + [1, 2, ..., H]:
  FY,LZK          for Y in [(Z, k) for k in K]:
    p                 print the following value without newline:
     ?qJSY\o              if J = sorted(Y): 'o'
       ?sY\.              if sum(Y) != 0:   '.'
         ez               else:             input[-1]
  )               end for
k                 print newline

```
> 1 votes

# Answer
## JavaScript (ES6), ~~163~~ ~~161~~ 145 bytes

```
(x,y,c,m=a=>`\n`+a.slice(1).reverse().join``+a.join``,a=Array(y+1).fill`.`,q=a.map(_=>[...a]))=>m(q.map(m,q[x][y]=q[y][x]='o',q[0][0]=c)).slice(2)

```

Where `\n` is the literal new line character. Works by generating the bottom right quadrant and mirroring it along both axes.

Edit: Saved 2 bytes thanks to @edc65.

(I got here via a duplicate question which allowed an array result which would have been 19 bytes shorter, but didn't guarantee nondecreasing order, which wasted 8 bytes.)
> 1 votes

# Answer
# JavaScript (ES6) 144 ~~150~~

```
(a,b,c,g=Array(b-~b).fill`.`)=>(g=g.map(x=>[...g])).map(x=>x.join``,[b-a,b+a].map(t=>g[t][0]=g[0][t]=g[t][2*b]=g[2*b][t]='o'),g[b][b]=c).join`
`

```

**Less golfed**

```
(a,b,c)=> {
  var g=Array(b*2+1).fill('.');
  g=g.map(x=>[...g]);
  var q=(t)=>
    g[t][0] =
    g[0][t] =
    g[t][2*b] =
    g[2*b][t] = 'o';
  q(b+a);
  q(b-a);
  g[b][b] = c;
  return g.map(x=> x.join('')).join('\n')
}

```

**Test**

```
f=(a,b,c,g=Array(b-~b).fill`.`)=>(g=g.map(x=>[...g])).map(x=>x.join``,[b-a,b+a].map(t=>g[t][0]=g[0][t]=g[t][2*b]=g[2*b][t]='o'),g[b][b]=c).join`
`

console.log=x=>O.textContent+=x+'\n'

t=`1,2,N
1,3,L
2,2,A
0,1,W
1,1,F
5,7,Q`.split`\n`
.forEach(t=>([x,y,z]=t.split`,`, console.log(t+'\n'+f(+x,+y,z)+'\n')))
```

```
<pre id=O></pre>
```
> 0 votes

---
Tags: code-golf, ascii-art, chess
---


title: Help Jason format his JSON

text:
# Question
Title: Help Jason format his JSON
Jason has a big JSON but it's unreadable, so he needs to prettify it.

## Formatting Spec

The JSON has 4 different types:

* Numbers; Just `0-9`
* Strings; Double quoted `"` strings escaped with `\`
* Arrays; Delimited by `[]`, with items separated by `,`, items can be any of these types
* Objects; Delimited by `{}`, format is `key: value` where key is a string and value is any of these types

Spacing

* Arrays should have exactly one space after the commas between items
* Objects should have have just one space between the key and the value, after the `:`

Indentation

* Each nesting level is indented 2 more than the previous
* Each object key/value pair is always on its own line. Objects are indented
* An array is indented across multiple lines if it contains another array or object. Otherwise the array remains on one line

## Rules

* Built-ins which trivialize this task are **not** allowed.
* As always standard loopholes are disallowed

## Examples

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

```

```
{"a":1,"b":4}
{
  "a": 1,
  "b": 4
}

```

```
"foo"
"foo"

```

```
56
56

```

```
{"a":[{"b":1,"c":"foo"},{"d":[2,3,4,1], "a":["abc","def",{"d":{"f":[3,4]}}]}]}
{
  "a": [
    {
      "b": 1,
      "c": "foo"
    },
    {
      "d": [2, 3, 4, 1],
      "a": [
        "abc",
        "def",
        {
          "d": {
            "f": [3, 4]
          }
        }
      ]
    }
  ]
}

```

```
[2,["foo123 ' bar \" baz\\", [1,2,3]]]
[
  2,
  [
    "foo123 ' bar \" baz\\",
    [1, 2, 3]
  ]
]

```

```
[1,2,3,"4[4,5]"]
[1, 2, 3, "4[4,5]"]

```

```
[1,2,3,{"b":["{\"c\":[2,5,6]}",4,5]}]
[
  1,
  2,
  3,
  {
    "b": ["{\"c\":[2,5,6]}", 4, 5]
  }
]

```

# Answer
## JavaScript (ES6), 368 bytes

```
f=(s,r=[],i='',j=i+'  ',a=[])=>s<'['?([,,r[0]]=s.match(s<'0'?/("(?:\\.|[^"])*")(.*)/:/(\d+)(.*)/))[1]:s<'{'?(_=>{for(;s<']';s=r[0])a.push(f(s.slice(1),r,j));r[0]=s.slice(1)})()||/\n/.test(a)?`[
${j+a.join(`,
`+j)}
${i}]`:`[${a.join`, `}]`:(_=>{for(a=[];s<'}';s=r[0])a.push(f(s.slice(1),r,j)+': '+f(r[0].slice(1),r,j));r[0]=s.slice(1)})()||`{
${j+a.join(`,
`+j)}
${i}}`

```

Less golfed:

```
function j(s, r=[], i='') { // default to no indentation
    if (s < '0') { // string
        let a = s.match(/("(?:\\.|[^"])*")(.*)/);
        r[0] = a[2]; // pass the part after the string back to the caller
        return a[1];
    } else if (s < '[') { // number
        let a = s.match(/(\d+)(.*)/);
        r[0] = a[2]; // pass the part after the string back to the caller
        return a[1];
    } else if (s < '{') { // array
        let a = [];
        while (s < ']') { // until we see the end of the array
            s = s.slice(1);
            a.push(j(s, r, i + '  ')); // recurse with increased indentation
            s = r[0]; // retrieve the rest of the string
        }
        r[0] = s.slice(1); // pass the part after the string back to the caller
        if (/\n/.test(a.join())) { // array contained object
            return '[\n  ' + i + a.join(',\n  ' + i) + '\n' + i + ']';
        } else {
            return '[' + a.join(', ') + ']';
        }
    } else { // object
        let a = [];
        while (s < '}') { // until we see the end of the object
            s = s.slice(1);
            let n = j(s, r, i + '  ');
            s = r[0].slice(1);
            let v = j(s, r, i + '  ');
            a.push(n + ': ' + v);
            s = r[0]; // retrieve the rest of the string
        }
        r[0] = s.slice(1); // pass the part after the string back to the caller
        return '{\n  ' + i + a.join(',\n  ' + i) + '\n' + i + '}';
    }
}

```
> 1 votes

---
Tags: code-golf, string, json
---


title: Read an analog clock

text:
# Question
Title: Read an analog clock
You are given the positions of the minute and hour hands of an analog clock as an angle of clockwise rotation from the top (12). So a hand pointing at 9 is at an angle if 270, and a hand pointing exactly in between 12 and 1 is at an angle of 15.

Input will be two integer angles (in any order of your choice) between 0 and 359. Minute hand will be a multiple of 60, hour hand will be a multiple of 5. Output will be the time, given as two integers separated by a colon (and nothing more).

**Sample data**

(Hour hand first)

```
195 180 - 6:30
355 300 - 11:50
280 120 - 9:20
0 0 - 12:00
10 120 - 12:20

```

# Answer
> 5 votes
# JavaScript ES6, 22 bytes

```
a=>b=>(0|a/30)+":"+b/6

```

Try it online (all browsers work)

# Answer
> 5 votes
## Pyth, 9 bytes

```
j\:.DyQ60

```

Explanation:

```
          - autoassign Q = eval_input()
     yQ   -   Q*2
   .D  60 -  divmod(^, 60)
j\:       - ":".join(^)

```

Try it here

Or try a test suite

# Answer
> 3 votes
# Jelly, ~~13~~ 7 bytes

Le code:

```
Ḥd60j“:

```

L'explanation:

```
         # Uses only the hour hand, (355)
Ḥ        # Double this, (355 × 2 = 710)
 d60     # Divmod 60, ([710 : 60, 710 % 60] = [11, 50])
    j“:  # Join by “:”, (11:50)

```

Try it online!

# Answer
> 1 votes
## PHP, 50 bytes

```
function t($h,$m){echo floor($h/30)?:12.":".$m/6;}

```

Set `$h` and `$m` to whatever values you like, and off you go.

# Answer
> 1 votes
# Pyth, 11 bytes

```
++/E30\:/E6

```

Try it online or Test Suite

Alternative version but the same size:

```
j\:[/E30/E6

```

## Explanation

~~Ab~~uses the fact that Python does integer division by default

```
  /E30       Divide `\` input `E` by 30
 +    \:     Add literal `:`
+       /E6  Add input `E` divided by 6

```

# Answer
> 1 votes
# Retina, ~~93~~ 107 bytes

Byte count assumes ISO 8859-1 encoding

Had to fix a bug, code wasn't working for 0 in input and 0 minutes was shown as a single zero, not two. Fix for 0 in input didn't add any extra characters, but the minutes and new test case added some extra weight...

So...uh...integer division with regex?

```
(\d+) (\d+)
30$*' $1$*';¶6$*' $2$*';
m+`^('+) \1('*);('*)$
$1 $2;$3'
.+;

('*)¶('*)
$.1:$.2
:0$
:00
\`^0
12

```

Input is hours and minutes separated by space. Hours come first.

Try it online!

# Answer
> 0 votes
# Python 2.7, ~~35~~ 28 characters

Needs hour hand as a first input; ignores the minute hand input.

```
lambda i:`i/30`+":"+`i*2%60`

```

7 characters less thanks to @DenkerAffe by using lambda instead of `input()` and `print`.

# Answer
> 0 votes
# Perl 21 + 1 = 22 bytes

```
$_=($==$_/30).$".<>/6

```

Requires the `-p` flag and takes input on multiply lines. Requires `-l` for multiply inputs:

```
$ (echo $'195\n180';echo $'355\n300';echo $'280\n120') | perl -pl analclock.pl
6 30
11 50
9 20

```

Assigning to `$=` will always yield an integer `print($= = 1.23)` =\> `1`

# Answer
> 0 votes
## Pyke, ~~10~~ 9 bytes

```
2*60.DRJ:

```

Explanation:

```
2*        - a = eval_input_or_not() * 2
  60.D    - a,b = divmod(a, 60)
      R   - a,b = rot_2(a,b)
       J: - ":".join([a,b])

```

# Answer
> 0 votes
# 05AB1E, 11 bytes

Code:

```
30/ï':I6/ïJ

```

Explanation:

```
30/          # Divide implicit input by 30
   ï         # Convert to int
    ':       # Add the ':'-character
      I6/ï   # Input divided by 6 and converted to int
          J  # Join the stack

```

Try it online

Uses **CP-1252** encoding.

# Answer
> 0 votes
# R, 29 bytes

```
cat(scan()%/%c(30,6),sep=':')

```

# Answer
> 0 votes
# CJam, 11 bytes

```
ri30/':ri6/

```

**Try it online!**

# Answer
> 0 votes
# MATL, 10 bytes

```
720/2$15XO

```

The hour in the output has a leading zero if less than `10`.

**Try it online!**

```
720/      % take first input and divide by 720
2$15XO    % format as HH:MM

```

# Answer
> 0 votes
# Perl 6, 54 bytes

```
{sprintf "%d:%02d",($^a div 30||12),$^b/6}

```

This accounts for 0 hours -\> 12:00, as well as having two digits in the minutes place

# Answer
> 0 votes
# DUP, 12 bytes

```
[2*60/.':,.]

```

`Try it here.`

Anonymous lambda that takes minutes then hours as arguments. Usage:

```
180 195[2*60/.':,.]!

```

# Explanation

```
[          ] {lambda}
 2*          {double hours}
   60/       {divmod by 60}
      .      {output quotient}
       ':,   {output :}
          .  {output remainder}

```

# Answer
> 0 votes
# Milky Way 1.6.5, 27 bytes

```
'2*60m":";+;?{_;+_^12;+0+}!

```

---

### Explanation

```
'2*                          ` double the input (195) -> [390]
   60m                       ` divmod TOS by 60 -> [6, 30]
      ":";+;                 ` add a colon -> [":30", 6]
            ?{_;+_^12;+0+}   ` format HH:MM -> ["6:30"]
                          !  ` output TOS

```

# Answer
> 0 votes
# Japt, 14 bytes

```
U/30|0 +':+V/6

```

Test it online!

I really need to implement a shorter way to floor...

# Answer
> 0 votes
# CJam, 11 bytes

```
ri2*60md':\

```

An alternate approach using divmod.

**Try it online!**

# Answer
> 0 votes
## Lua, 101 Bytes

A solution only using the hour argument. It is a full program taking the input via command-line argument `lua readAnalogClock.lua 355`. You could call it with 2 arguments, but the second one is never used.

```
i=arg[1]j=i%30i=(i-j)/30print(((i<1 and 12or i)..''):gsub("%..*","")..":"..(2*j..''):gsub("%..*",""))

```

### Ungolfed

```
i=arg[1]                  -- initialise i with the hours angle
j=i%30                    -- initialise j with the minute part of i
i=(i-j)/30                -- round i to the previous hour
print(
  ((i<1 and 12or i)..'')  -- replace 0 by 12 and make it a string
    :gsub("%..*","")      -- remove decimal part of hour (which is .0)
  ..":"                   -- concatenate with the separator
  ..(2*j..'')             -- makes a string containing the minutes
    :gsub("%..*",""))     -- remove decimal part of minutes

```

---
Tags: code-golf, date
---


title: Permutation Square Root

text:
# Question
Title: Permutation Square Root
In math, a permutation ***σ*** of order ***n*** is a bijective function from the integers 1...***n*** to itself. This list:

```
2 1 4 3

```

represents the permutation ***σ*** such that ***σ***(1) = 2, ***σ***(2) = 1, ***σ***(3) = 4, and ***σ***(4) = 3.

A square root of a permutation ***σ*** is a permutation that, when applied to itself, gives ***σ***. For example, `2 1 4 3` has the square root ***τ*** =`3 4 2 1`.

```
k           1 2 3 4
τ(k)        3 4 2 1
τ(τ(k))     2 1 4 3

```

because ***τ***(***τ***(k)) = ***σ***(k) for all 1≤k≤n.

### Input

A list of ***n***\>0 integers, all between 1 and ***n*** inclusive, representing a permutation. The permutation will always have a square root.

You may use a list of 0...***n-1*** instead as long as your input and output are consistent.

### Output

The permutation's square root, also as an array.

### Restrictions

Your algorithm must run in polynomial time in ***n***. That means you can't just loop through all ***n***! permutations of order ***n***.

Any builtins are permitted.

### Test cases:

Note that many inputs have multiple possible outputs.

```
2 1 4 3
3 4 2 1

1
1

3 1 2
2 3 1

8 3 9 1 5 4 10 13 2 12 6 11 7
12 9 2 10 5 7 4 11 3 1 13 8 6

13 7 12 8 10 2 3 11 1 4 5 6 9
9 8 5 2 12 4 11 7 13 6 3 10 1

```

# Answer
> 5 votes
# Perl, ~~124~~ 122 bytes

Includes +3 for `-alp`

Run with the 1 based permutation on STDIN:

```
rootperm.pl <<< "8 3 9 1 5 4 10 13 2 12 6 11 7"

```

`rootperm.pl`:

```
map{//;@{$G[-1]^$_|$0{$_}}{0,@G}=(@G=map{($n+=$s{$_=$F[$_-1]}++)?():$_}(0+$',0+$_)x@F)x2,%s=$n=0for@F}@F;$_="@0{1..@F}"

```

Complexity is ***O(n^3)***

# Answer
> 2 votes
# Mathematica, 165 ~~167~~ bytes

An unnamed function.

```
PermutationList[Cycles@Join[Riffle@@@#~(s=Select)~EvenQ@*(l=Length)~SortBy~l~Partition~2,#[[Mod[(#+1)/2Range@#,#,1]&@l@#]]&/@#~s~OddQ@*l]&@@PermutationCycles@#,l@#]&

```

Semi-ungolfed:

```
PermutationList[
    Cycles@Join[
        Riffle@@@Partition[SortBy[Select[#,EvenQ@*Length],Length], 2],
        #[[Mod[(Length@#+1)/2Range@Length@#,Length@#,1]]]& /@ Select[#,OddQ@*Length]
    ]& @@ PermutationCycles @ #,
    Max@#
]&

```

# Answer
> 0 votes
# Prolog - 69 chars

```
p([],_,[]). p([H|T],B,[I|U]):-p(T,B,U),nth1(H,B,I). f(X,Y):-p(Y,Y,X).

```

Explanation:

```
permutate([], _, []).                 % An empty permutation is empty
permutate([X|Xs], List, [Y|Ys]) :-    % To permutate List
  permutate(Xs, List, Ys),            % Apply the rest of the permutation
  nth1(X, List, Y).                   % Y is the Xth element of List

root(Permutation, Root) :-            % The root of Permutation
  permutate(Root, Root, Permutation). % Applied to itself, is Permutation

```

---
Tags: code-golf, permutations, restricted-complexity
---


title: Write a Morse Calculator

text:
# Question
Title: Write a Morse Calculator
Write a program or function that takes a mathematical expression in Morse code as input, and returns the solution in Morse code.

Valid operations are plus: `+` and minus: `_` (underscore). You can assume you will only receive non-negative integer input, and that the result will be non-negative.

The expression will contain at least two terms, and maximum ten terms. There won't be two adjacent operators i.e. `.----+_-....`, and there won't be parentheses.

Digits are seperated by single spaces. You can choose to have the operators separated from the numbers by a single space on each side (see examples).

The Morse equivalent for the digits 0-9 are:

```
0  -----
1  .----
2  ..---
3  ...--
4  ....-
5  .....
6  -....
7  --...
8  ---..
9  ----.

```

**Examples:**

```
Input
Output

.----+.----  (1+1=2) Optional input: .---- + .----
..---

-...._...--  (6-3=3) Optional input: -.... _ ...--
...--

..---_...--+..--- (2-3+2=1)
1

..---+...--_....-+---.._.....  (2+3-4+8-5=4)
....-

.---- ..---_-....+...-- ...--  (12-6+33=39)
...-- ----.

----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----  (90+9+29-55+8+6-1+9+9-20=84)
---.. ....-

```

Standard rules regarding I/O formats etc. apply. A few trailing spaces, and a single newline are accepted. You can't split the number over several lines. You can't use `eval` or equivalent.

This is code golf, so the shortest code in bytes win.

# Answer
> 3 votes
## Pyth, ~~69~~ 63 bytes

```
J_.:s*R5"-.-"5jdm@Jsd`s*MC,mssdc`MKmxJdcz)"-1"+1mtyq\+@cz)dx_1K

```

Try it here

Or use a test suite

Explanation

```
J_.:s*R5"-.-"5                                                  - Construct the morse sequence 0-10
              jd                                                - Prettify output (join by spaces)
                m@Jsd                                           - Get the morse for each character in output
                     `s                                         - Convert to a string
                         C,mssdc`MKmxJdcz)"-1"                  - Get the numbers
                       *M                                       - Multiply the numbers by the operators
                                              +1mtyq\+@cz)dx_1K - Turn `+` and `_` to +-1

```

Saved 6 bytes thanks to @Jakube!

# Answer
> 5 votes
# Retina, 132 bytes

A messy, first pass solution.

```
(-)+\.+
5$*.$#1$*.
(-|(\.))+ ?
$#2
\d+
$*
+`(1(_)1|(_1+)|_|\+)(.*)
$2$4$3
1+
$.0
\d
$*x5$*-
(x)+x{5}-*
$#1$*-xxxx
(\S{5})\S*
$1
x
.

```

Try it online!

# Answer
> 3 votes
# MATL, ~~75~~ ~~71~~ ~~69~~ 68 bytes

```
5:t!<t~v45+cXIO1Oj6ZC"@2#0)Iw!Xmfqb+wXK32=?10*}*+K?K9\6-O}V47-Y)Z{Zc

```

**Try it online!**

### General explanation

I use code format in the following so that indentation expresses the nesting of operations.

```
The input is split into chunks of 6 characters. The last chunk will have
5 characters padded by a 0 char.
   A 0 is initially pushed. This will contain the accumulated global result.
      Each operand (sequence of digits) is processed as follows. A "sign digit",
      1 or -1, has been previously pushed according to whether the preceding
      operator was + or - (for the first operand 1 is used as sign digit).
      Then a 0 is pushed. This will contain the accumulated operand value.
         Each digit of the operand is transformed into the a number `0`...`9` and
         accumulated to the operand value, with successive multiplications by `10`.
      When a + or - is detected, the current operand is finished. So it is
      multiplied by its sign digit, and added to the acumulated global result.
      A new sign digit is pushed (1 for +, -1 for -), and a new 0 is pushed
      as initial accumulated operand value for the next operand.
   When a 0 char is detected instead of + or -, this marks the end of the input.
   The current global accumulated result is the definitive value. This is
   tranformed into Morse digits and displayed.

```

### Detailed explanation

```
5:t!<         % first half of the 10x5 array of Morse digits, with 0 for - and 1 for .
t~v           % vertically concat second half, i.e. first half vertically flipped
45+cXI        % transform 0 1 to chars - . Copy this "digit table" to clipboard I
O             % push 0: initial value for accumulated global result
1             % push 1: sign digit for first operand
O             % push 0: initial value of operand
j             % input string
6ZC           % arrange 6-length non-overlapping blocks as columns. Last is 0-padded
"             %   for each column
  @           %   push column
  2#0)        %   split into last element and vector or remaining elements
  I           %   push digit table
  w!          %   swap and transposed into a row
  Xmfq        %   index of that row in the digit table. Subtract 1: gives the digit
  b+          %   bubble up current operand value to top. Add to the new found digit
  wXK         %   swap last char of column (+,-,space,0) to top. Copy to clipboard K
  32=         %   is it space?
  ?           %   if so
    10*       %     multiply by 10. The operand will continue with next digit
  }           %   else: the operand is done
    *         %     multiply by sign digit
    +         %     add this operand with its sign to accumulated global result
    K         %     push last char of column again
    ?         %     if it's not 0
      K9\6-   %       push 1 if it's a +, -1 if it's a -: sign digit of next operand
      O       %       push 0 to initiallize accumulated operand value of next operand
    }         %     else: it's a 0: we're done computing the result
      V       %       convert result to string to get its digits
      47-Y)   %       index the rows of the digit table that was initially pushed
      Z{Zc    %       join rows by spaces
              %     end if, implicit
              %   end if, implicit
              % end for each, implicit
              % display, implicit

```

# Answer
> 1 votes
# Javascript (es6) 236 bytes

plenty of room for improvement

```
q=>(q.replace(/[.-]{5}/g,q=>(a=q.split`.`.length)&&q[4]=='-'?a-1:11-a).replace(/ /g,'').split(/([_+])/).reduce((l,o)=>l+(+o?(n=='_'?-(+o):+o):(n=o)&&0),0,n='')+[]).split``.map(u=>(((a='.....')+'-----').slice(5-u)+a).substr(0,5)).join` `

```

---

broken up
```
q=>
 (
 //grab each set of 5 dits/dahs
 q.replace(/[.-]{5}/g,

  //count dits
  //if last digit is '-' return dits-1
  //else return 11-dits
  q=>(a=q.split`.`.length)&&q[4]=='-'?a-1:11-a)

   //remove spaces and split on operators + and _
   .replace(/ /g,'').split(/([_+])/)

    //reduce the array into one element
    //start with 0;
    //when we come across a number add it to the total
    //when we come across an operator change current op to it
    .reduce((l,o)=>l+(+o?(n=='_'?-(+o):+o):(n=o)&&0),0,n='')

  //cast to string
  +[])

 //turn to array
 .split``

  //turn each digit back to morse
  .map(u=>(".....-----".slice(5-u)+'.....').substr(0,5)).join` `

```

*usage*

```
f=q=>(q.replace(/[.-]{5}/g,q=>(a=q.split`.`.length)&&q[4]=='-'?a-1:11-a).replace(/ /g,'').split(/([_+])/).reduce((l,o)=>l+(+o?(n=='_'?-(+o):+o):(n=o)&&0),0,n='')+[]).split``.map(u=>(((a='.....')+'-----').slice(5-u)+a).substr(0,5)).join` `

f("----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----")

```

# Answer
> 0 votes
### Pure bash, ~~366~~ 317

```
a=----- p='v+=($a);a=${a/-/.}';q=${p/-?././-};. <(echo $p{,,,,} $q{,,,,});p(){
[ ${1:0:1} = . ]&&{ b=${1%%-*};o+=${#b};}||{ b=${1%%.*} o+=$[(5+${#b})%10];};}
s=${1//[-.]/};for i in ${1//[+_]/ };do p $i;t=${s:0:1};o+=${t// };s=${s:1};done
r=$[${o//_/-}];for ((i=0;i<${#r};i++));do w+=(${v[${r:i:1}]});done;echo ${w[@]}

```

Ok, I could save 10 bytes to reach **307** by written 1st line:

```
v=(----- .---- ..--- ...-- ....- ..... -.... --... ---.. ----.);p(){

```

instead of (but I like):

```
a=----- p='v+=($a);a=${a/-/.}';q=${p/-?././-};. <(echo $p{,,,,} $q{,,,,});p(){

```

Sample:

```
cat >/tmp/morseCalc.sh <<'eof'
#!/bin/bash
a=----- p='v+=($a);a=${a/-/.}';q=${p/-?././-};. <(echo $p{,,,,} $q{,,,,});p(){
[ ${1:0:1} = . ]&&{ b=${1%%-*};o+=${#b};}||{ b=${1%%.*} o+=$[(5+${#b})%10];};}
s=${1//[-.]/};for i in ${1//[+_]/ };do p $i;t=${s:0:1};o+=${t// };s=${s:1};done
r=$[${o//_/-}];for ((i=0;i<${#r};i++));do w+=(${v[${r:i:1}]});done;echo ${w[@]}
eof
chmod +x /tmp/morseCalc.sh

for test in 1+1 6-3 2-3+2 2+3-4+8-5 12-6+33 90+9+29-55+8+6-1+9+9-20 ;do
    string="$(sed 's/ \.\.\.-\.-$//;s/ \.-\.-\. /+/g;s/ -\.\.\.\.- /_/g' <(
        xargs < <(morse -s -- $test)))"
    out="$(/tmp/morseCalc.sh "$string")"
    res=$(morse -sd <<< "$out")
    echo "$test: $string = $out -> $res"
  done |
    fold -w 80 -s

1+1: .----+.---- = ..--- -> 2
6-3: -...._...-- = ...-- -> 3
2-3+2: ..---_...--+..--- = .---- -> 1
2+3-4+8-5: ..---+...--_....-+---.._..... = ....- -> 4
12-6+33: .---- ..---_-....+...-- ...-- = ...-- ----. -> 39
90+9+29-55+8+6-1+9+9-20: ----. -----+----.+..--- ----._.....
.....+---..+-...._.----+----.+----._..--- ----- = ---.. ....- -> 84

```

or if `morse` converter is not installed:

```
for test in .----+.---- -...._...-- ..---_...--+..---  \
 ..---+...--_....-+---.._..... ".---- ..---_-....+...-- ...--" "----. -----+\
----.+..--- ----._..... .....+---..+-...._.----+----.+----._..--- -----" ;do
    echo $test $(
        bash <(sed '$s/;f/;echo "(${o\/\/_\/-}=$r)";f/' /tmp/morseCalc.sh
            ) "$test" )
  done |
    fold -w80 -s

.----+.---- (1+1=2) ..---
-...._...-- (6-3=3) ...--
..---_...--+..--- (2-3+2=1) .----
..---+...--_....-+---.._..... (2+3-4+8-5=4) ....-
.---- ..---_-....+...-- ...-- (12-6+33=39) ...-- ----.
----. -----+----.+..--- ----._..... .....+---..+-...._.----+----.+----._..---
----- (90+9+29-55+8+6-1+9+9-20=84) ---.. ....-

```

---
Tags: code-golf, arithmetic, morse
---