# Question
Title: Compute the maximum number of runs possible for as large a string as possible
\[This question is a follow up to Compute the runs of a string \]

> A period `p` of a string `w` is any positive integer `p` such that `w[i]=w[i+p]` whenever both sides of this equation are defined. Let `per(w)` denote the size of the smallest period of `w` . We say that a string `w` is periodic iff `per(w) <= |w|/2`.

So informally a periodic string is just a string that is made up from another string repeated at least once. The only complication is that at the end of the string we don't require a full copy of the repeated string as long as it is repeated in its entirety at least once.

For, example consider the string `x = abcab`. `per(abcab) = 3` as `x[1] = x[1+3] = a`, `x[2]=x[2+3] = b` and there is no smaller period. The string `abcab` is therefore not periodic. However, the string `ababa` is periodic as `per(ababa) = 2`.

As more examples, `abcabca`, `ababababa` and `abcabcabc` are also periodic.

For those who like regexes, this one detects if a string is periodic or not:

```
\b(\w*)(\w+\1)\2+\b

```

The task is to find all **maximal** periodic substrings in a longer string. These are sometimes called **runs** in the literature.

> A substring `w` is a maximal periodic substring (run) if it is periodic and neither `w[i-1] = w[i-1+p]` nor `w[j+1] = w[j+1-p]`. Informally, the "run" cannot be contained in a larger "run" with the same period.

Because two runs can represent the same string of characters occurring in different places in the overall string, we will represent runs by intervals. Here is the above definition repeated in terms of intervals.

> A run (or maximal periodic substring) in a string `T` is an interval `[i...j]` with `j>=i`, such that
>
> * `T[i...j]` is a periodic word with the period `p = per(T[i...j])`
> * It is maximal. Formally, neither `T[i-1] = T[i-1+p]` nor `T[j+1] = T[j+1-p]`. Informally, the run cannot be contained in a larger run with the same period.

Denote by `RUNS(T)` the set of runs in string `T`.

**Examples of runs**

* The four maximal periodic substrings (runs) in string `T = atattatt` are `T[4,5] = tt`, `T[7,8] = tt`, `T[1,4] = atat`, `T[2,8] = tattatt`.
* The string `T = aabaabaaaacaacac` contains the following 7 maximal periodic substrings (runs): `T[1,2] = aa`, `T[4,5] = aa`, `T[7,10] = aaaa`, `T[12,13] = aa`, `T[13,16] = acac`, `T[1,8] = aabaabaa`, `T[9,15] = aacaaca`.
* The string `T = atatbatatb` contains the following three runs. They are: `T[1, 4] = atat`, `T[6, 9] = atat` and `T[1, 10] = atatbatatb`.

Here I am using 1-indexing.

**The task**

Write code so that for each integer n starting at 2, you output the largest numbers of runs contained in any binary string of length `n`.

**Score**

Your score is the highest `n` you reach in 120 seconds such that for all `k <= n`, no one else has posted a higher correct answer than you. Clearly if you have all optimum answers then you will get the score for the highest `n` you post. However, even if your answer is not the optimum, you can still get the score if no one else can beat it.

**Languages and libraries**

You can use any available language and libraries you like. Where feasible, it would be good to be able to run your code so please include a full explanation for how to run/compile your code in Linux if at all possible.

**Example optima**

In the following: `n, optimum number of runs, example string`.

```
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011

```

**What exactly should my code output?**

For each `n` your code should output a single string and the number of runs it contains.

**My Machine** The timings will be run on my machine. This is a standard ubuntu install on an AMD FX-8350 Eight-Core Processor. This also means I need to be able to run your code.

**Leading answers**

* **49** by Anders Kaseorg in **C**. Single threaded and run with L = 12 (2GB of RAM).
* **27** by cdlane in **C**.

# Answer
> 9 votes
# C

This does a recursive search for optimal solutions, heavily pruned using an upper bound on the number of runs that could be finished by the unknown remainder of the string. The upper bound computation uses a gigantic lookup table whose size is controlled by the constant `L` (`L=11`: 0.5 GiB, `L=12`: 2 GiB, `L=13`: 8 GiB).

On my laptop, this goes up through *n* = 50 in 100 seconds; the next line comes at 142 seconds.

```
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N (8*sizeof(unsigned long long))
#define L 13
static bool a[N], best_a[N];
static int start[N/2 + 1], best_runs;
static uint8_t end_runs[2 << 2*L][2], small[N + 1][2 << 2*L];

static inline unsigned next_state(unsigned state, int b)
{
    state *= 2;
    state += b;
    if (state >= 2 << 2*L) {
        state &= ~(2 << 2*L);
        state |= 1 << 2*L;
    }
    return state;
}

static void search(int n, int i, int runs, unsigned state)
{
    if (i == n) {
        int r = runs;
        unsigned long long m = 0;
        for (int p = n / 2; p > 0; p--) {
            if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                m |= 1ULL << start[p];
                r++;
            }
        }
        if (r > best_runs) {
            best_runs = r;
            memcpy(best_a, a, n*sizeof(a[0]));
        }
    } else {
        a[i] = false;
        do {
            int r = runs, bound = 0, saved = 0, save_p[N/2], save_start[N/2], p, s = next_state(state, a[i]);
            unsigned long long m = 0;
            for (p = n/2; p > i; p--)
                if (p > L)
                    bound += (n - p + 1)/(p + 1);
            for (; p > 0; p--) {
                if (a[i] != a[i - p]) {
                    if (i - start[p] >= 2*p && !(m & 1ULL << start[p])) {
                        m |= 1ULL << start[p];
                        r++;
                    }
                    save_p[saved] = p;
                    save_start[saved] = start[p];
                    saved++;
                    start[p] = i + 1 - p;
                    if (p > L)
                        bound += (n - i)/(p + 1);
                } else {
                    if (p > L)
                        bound += (n - (start[p] + p - 1 > i - p ? start[p] + p - 1 : i - p))/(p + 1);
                }
            }
            bound += small[n - i - 1][s];

            if (r + bound > best_runs)
                search(n, i + 1, r, s);
            while (saved--)
                start[save_p[saved]] = save_start[saved];
        } while ((a[i] = !a[i]));
    }
}

int main()
{
    for (int n = 0; n <= N; n++) {
        if (n <= 2*L) {
            for (unsigned state = 1U << n; state < 2U << n; state++) {
                for (int b = 0; b < 2; b++) {
                    int r = 0;
                    unsigned long long m = 0;
                    for (int p = n / 2; p > 0; p--) {
                        if ((b ^ state >> (p - 1)) & 1) {
                            unsigned k = state ^ state >> p;
                            k &= -k;
                            k <<= p;
                            if (!(k & ~(~0U << n)))
                                k = 1U << n;
                            if (!((m | ~(~0U << 2*p)) & k)) {
                                m |= k;
                                r++;
                            }
                        }
                    }
                    end_runs[state][b] = r;
                }
                small[0][state] = end_runs[state][0] + end_runs[state][1];
            }
        }

        for (int l = 2*L < n - 1 ? 2*L : n - 1; l >= 0; l--) {
            for (unsigned state = 1U << l; state < 2U << l; state++) {
                int r0 = small[n - l - 1][next_state(state, 0)] + end_runs[state][0],
                    r1 = small[n - l - 1][next_state(state, 1)] + end_runs[state][1];
                small[n - l][state] = r0 > r1 ? r0 : r1;
            }
        }

        if (n >= 2) {
            search(n, 1, 0, 2U);
            printf("%d %d ", n, best_runs);
            for (int i = 0; i < n; i++)
                printf("%d", best_a[i]);
            printf("\n");
            fflush(stdout);
            best_runs--;
        }
    }
    return 0;
}

```

Output:

```
$ gcc -mcmodel=medium -O2 runs.c -o runs
$ ./runs
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
23 17 00100101001011010010100
24 18 001001100100110110011011
25 19 0010011001000100110010011
26 20 00101001011010010100101101
27 21 001001010010110100101001011
28 22 0010100101101001010010110100
29 23 00101001011010010100101101011
30 24 001011010010110101101001011010
31 25 0010100101101001010010110100101
32 26 00101001011010010100101101001011
33 27 001010010110100101001011010010100
34 27 0001010010110100101001011010010100
35 28 00100101001011010010100101101001011
36 29 001001010010110100101001011010010100
37 30 0010011001001100100010011001001100100
38 30 00010011001001100100010011001001100100
39 31 001001010010110100101001011010010100100
40 32 0010010100101101001010010110100101001011
41 33 00100110010001001100100110010001001100100
42 35 001010010110100101001011010110100101101011
43 35 0001010010110100101001011010110100101101011
44 36 00101001011001010010110100101001011010010100
45 37 001001010010110100101001011010110100101101011
46 38 0010100101101001010010110100101001011010010100
47 39 00101101001010010110100101101001010010110100101
48 40 001010010110100101001011010010110101101001011010
49 41 0010100101101001010010110100101101001010010110100
50 42 00101001011010010100101101001011010110100101101011
51 43 001010010110100101001011010110100101001011010010100

```

Here are *all* optimal sequences for *n* ≤ 64 (not just the lexicographically first), generated by a modified version of this program and many hours of computation.

# A remarkable nearly-optimal sequence

The prefixes of the infinite fractal sequence

```
1010010110100101001011010010110100101001011010010100101…

```

that is invariant under the transformation 101 ↦ 10100, 00 ↦ 101:

```
  101   00  101   101   00  101   00  101   101   00  101   101   00  …
= 10100 101 10100 10100 101 10100 101 10100 10100 101 10100 10100 101 …

```

seem to have very nearly optimal numbers of runs—always within 2 of optimal for *n* ≤ 64. The number of runs in the first *n* characters divided by *n* approaches (13 − 5√5)/2 ≈ 0.90983. But it turns out this is not the optimal ratio—see comments.

# Answer
> 2 votes
Since it's not a race if there's only one horse, I'm submitting my solution though it's only a fraction the speed of Anders Kaseorg's and a only a third as cryptic. Compile with:

> gcc -O2 run-count.c -o run-count

The heart of my algorithm is a simple shift and XOR scheme:

A run of zeros in the XOR result that's greater than or equal to the current period/shift indicates a run in the original string for this period. From this you can tell how long the run was and where it starts and ends. The rest of the code is overhead, setting up the situation and decoding the results.

I'm hoping it will make at least 28 after two minutes on Lembik's machine. (I wrote a pthread version, but only managed to make it run even slower.)

```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>

enum { START = 0, WIDTH } ;

// Compare and shuffle just one thing while storing two
typedef union {
    uint16_t token;
    uint8_t data[sizeof(uint16_t)];
} overlay_t;

#define SENTINAL (0)  // marks the end of an array of overlay_t

#define NUMBER_OF_BITS (8 * sizeof(uint64_t))

void period_runs(uint64_t xor_bits, uint8_t nbits, uint8_t period, overlay_t *results) {

    overlay_t *results_ptr = results;
    uint8_t count = 0;

    for (uint8_t position = 0; position < nbits; position++) {

        if (xor_bits & 1ULL) {

            if ((nbits - position) < period) {
                break;  // no room left to succeed further
            }

            if (count >= period) {  // we found a run

                results_ptr->data[START] = position - (count - 1);
                results_ptr->data[WIDTH] = period + count;
                results_ptr++;
            }

            count = 0;
        } else {

            count++;
        }

        xor_bits >>= 1;
    }

    if (count >= period) {  // process the final run, if any

        results_ptr->data[START] = 0;
        results_ptr->data[WIDTH] = period + count;
        results_ptr++;
    }

    results_ptr->token = SENTINAL;
}

void number_runs(uint64_t number, uint8_t bit_length, overlay_t *results) {

    overlay_t sub_results[bit_length];
    uint8_t limit = bit_length / 2 + 1;
    uint64_t mask = (1ULL << (bit_length - 1)) - 1;

    overlay_t *results_ptr = results;
    results_ptr->token = SENTINAL;

    for (uint8_t period = 1; period < limit; period++) {

        uint64_t xor_bits = mask & (number ^ (number >> period));  // heart of the code
        period_runs(xor_bits, bit_length - period, period, sub_results);

        for (size_t i = 0; sub_results[i].token != SENTINAL; i++) {

            bool stop = false;  // combine previous and current results

            for (size_t j = 0; !stop && results[j].token != SENTINAL; j++) {

                // lower period result disqualifies higher period result over the same span
                stop = (sub_results[i].token == results[j].token);
            }

            if (!stop) {

                (results_ptr++)->token = sub_results[i].token;
                results_ptr->token = SENTINAL;
            }
        }

        mask >>= 1;
    }
}

int main() {

    overlay_t results[NUMBER_OF_BITS];

    for (uint8_t bit_length = 2; bit_length < 25; bit_length++) {

        int best_results = -1;
        uint64_t best_number = 0;

        for (uint64_t number = 1ULL << (bit_length - 1); number < (1ULL << bit_length); number++) {

            // from the discussion comments, I should be able to solve this
            // with just bit strings that begin "11...", so toss the rest
            if ((number & (1ULL << (bit_length - 2))) == 0ULL) {

                continue;
            }

            uint64_t reversed = 0;

            for (uint8_t i = 0; i < bit_length; i++) {

                if (number & (1ULL << i)) {

                    reversed |= (1ULL << ((bit_length - 1) - i));
                }
            }

            if (reversed > number) {

                continue;  // ~ 1/4 of bit_strings are simply reversals, toss 'em
            }

            number_runs(number, bit_length, results);
            overlay_t *results_ptr = results;
            int count = 0;

            while ((results_ptr++)->token != SENTINAL) {

                count++;
            }

            if (count > best_results) {

                best_results = count;
                best_number = number;
            }
        }

        char *best_string = malloc(bit_length + 1);
        uint64_t number = best_number;
        char *string_ptr = best_string;

        for (int i = bit_length - 1; i >= 0; i--) {

            *(string_ptr++) = (number & (1ULL << i)) ? '1' : '0';
        }

        *string_ptr = '\0';

        printf("%u %d %s\n", bit_length, best_results, best_string);

        free(best_string);
    }

    return 0;
}

```

Output:

```
> gcc -O2 run-count.c -o run-count
> ./run-count
2 1 11
3 1 110
4 2 1100
5 2 11000
6 3 110011
7 4 1100100
8 5 11001100
9 5 110010011
10 6 1100110011
11 7 11001100100
12 8 110110011011
13 8 1100100010011
14 10 11001001100100
15 10 110010011001000
16 11 1100100110010011
17 12 11001100100110011
18 13 110011001001100100
19 14 1101001011010010100
20 15 11010110100101101011
21 15 110010011001001100100
22 16 1100101001011010010100
23 17 11010010110100101001011
24 18 110100101001011010010100
25 19 1100100110010001001100100
26 20 11010010100101101001010010
27 21 110010011001000100110010011
28 22 1101001010010110100101001011

```

---
Tags: math, fastest-code, optimization
---


title: Four is the magic number

text:
# Question
Title: Four is the magic number
I didn't check the sandbox before posting this challenge - it looks like this challenge was proposed by Cᴏɴᴏʀ O'Bʀɪᴇɴ.

Given an integer input, write a program that prints the "four is a magic number" riddle

* Four is the magic number
* Five is four and four is the magic number
* Six is three and three is five and five is four and four is the magic number
* Eleven is six and six is three and three is five and five is four and four is the magic number
* Five Hundred is eleven and eleven is six and six is three and three is five and five is four and four is the magic number

If you already know the riddle, or are too ~~lazy to solve it~~ anxious to find out what the riddle is, here's an explanation

> The next number is the number of letters in the previous number. So, for example, **five** has **four** letters, so the next number is **four**.
> **six** has **three** letters, so the next number is **3**, and **three** has **five** letters, so the next number is **5**, and **five** has **four** letters, so the next number is **4**
> The reason the riddle ends at four is because four has four letters, and four is four and four is four and four is four... (four is the magic number)

## Test Cases

```
0 =>
  Zero is four and four is the magic number
1 =>
  One is three and three is five and five is four and four is the magic number
2 =>
  Two is three and three is five and five is four and four is the magic number
3 =>
  Three is five and five is four and four is the magic number
4 =>
  Four is the magic number
5 =>
  Five is four and four is the magic number
6 =>
  Six is three and three is five and five is four and four is the magic number
7 =>
  Seven is five and five is four and four is the magic number
8 =>
  Eight is five and five is four and four is the magic number
9 =>
  Nine is four and four is the magic number
10 =>
  Ten is three and three is five and five is four and four is the magic number
17 =>
  Seventeen is nine and nine is four and four is the magic number
100 =>
  One Hundred is ten and ten is three and three is five and five is four and four is the magic number
142 =>
  One Hundred Forty Two is eighteen and eighteen is eight and eight is five and five is four and four is the magic number
1,000 =>
  One Thousand is eleven and eleven is six and six is three and three is five and five is four and four is the magic number
1,642 =>
  One Thousand Six Hundred Forty Two is twenty nine and twenty nine is ten and ten is three and three is five and five is four and four is the magic number
70,000 =>
  Seventy Thousand is fifteen and fifteen is seven and seven is five and five is four and four is the magic number
131,072 =>
  One Hundred Thirty One Thousand Seventy Two is thirty seven and thirty seven is eleven and eleven is six and six is three and three is five and five is four and four is the magic number
999,999 =>
  Nine Hundred Ninety Nine Thousand Nine Hundred Ninety Nine is fifty and fifty is five and five is four and four is the magic number

```

## Rules

* The input may either be taken from `STDIN` or as an argument to a function
* The input will be a positive number between 0 and 999,999
* The input will *only* contain numbers (it will follow the regex `^[0-9]+$`)
* The input can either be taken as an integer or a string
* When converted to a word string, spaces and hyphens should not be included in the count (100 \[One Hundred\] is 10 characters, not 11. 1,742 \[One thousand Seven hundred Forty-Two\] is 31 characters, not 36)
* When converted to a string, 100 should be One Hundred, not A Hundred or Hundred, 1000 should be One Thousand, not A Thousand or Thousand.
* When converted to a string 142 should be One Hundred Forty Two, not One Hundred *and* Forty Two
* The output is **case-insensitive**, and should follow the format "**N** is **K** and **K** is **M** and **M** is ... and four is the magic number" (unless the input is 4, in which case the output should simply be "four is the magic number")
* The output *can* use numbers instead of letters ("5 is 4 and 4 is the magic number" instead of "five is four and four is the magic number") as long as your program is always consistent
* The output can either be the return value of a function, or printed to `STDOUT`
* Standard loopholes apply
* This is , so the shortest program in bytes wins. Good luck!

## Bonus

**-30 bytes** if the program works when the input is between -999,999 and 999,999.

Negative numbers, when converted to words, just have "negative" in front of them. For example `-4` is "Negative Four", *Negative Four is twelve and twelve is six and six is three and three is five and five is four and four is the magic number*

**-150 bytes** if the program does not use any built-in functions for generating the string representation of the number

## Leaderboard

This is a Stack Snippet that generates both a leaderboard and an overview of winners by language.

To ensure your answer shows up, please start your answer with a headline using the following Markdown template

```
## Language Name, N bytes

```

Where N is the size, in bytes, of your submission

If you want to include multiple numbers in your header (for example, striking through old scores, or including flags in the byte count), just make sure that the actual score is the *last* number in your header

```
## Language Name, <s>K</s> X + 2 = N bytes

```

```
var QUESTION_ID=67344;var OVERRIDE_USER=20634;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(-?\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 9 votes
## Bash + common utilities (including bsd-games), 123 - 30 = 93 bytes

```
for((n=$1;n-4;n=m)){
m=`number -l -- $n|sed 's/nus/&&/;s/\W//g'`
s+="$n is $[m=${#m}] and "
}
echo $s 4 is the magic number

```

Luckily the output from the bsd-games `number` utility is almost exactly what we need. Output numbers are all written numerically and not in words as per the 8th bullet point:

```
$ ./4magic.sh 131072
131072 is 37 and 37 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
$ ./4magic.sh -4
-4 is 12 and 12 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
$

```

# Answer
> 6 votes
# C, 263 261 bytes - 180 = 81

```
char*i="jmmonnmoonmpprrqqsrrjjddeeecdd",x;f(n,c){return!n?n:n<0?f(-n,8):n<100?c+i[n<20?n:n%10]-i[20+n/10]:f(n/1000,8)+f(n/100%10,7)+f(n/100%10,0)+c;}main(int c,char**v){for(c=atoi(*++v);c-4;c=x)printf("%d is %d and ",c,x=c?f(c,0)):4;puts("4 is the magic number");}

```

Inspired by the answer from Cole Cameron. I thought I might be able to do better without the macro definition. Although I eventually managed, it did take some squeezing to achieve!

It requires a host character set with consecutive letters (so ASCII is okay, but EBCDIC won't work). That's for the pair of lookup tables. I chose `j` as the zero character, and took advantage of needing two lookups, so I could subtract one from the other rather than having to subtract my zero from both.

## Commented version:

```
char*i=
    "jmmonnmoon"                /* 0 to 9 */
    "mpprrqqsrr"                /* 10 to 19 */
    "jjddeeecdd";               /* tens */
char x;                /* current letter count */

f(n,c){
return
    !n?n                        /* zero - return 0 (ignore c) */
    :n<0?f(-n,8)                /* negative n (only reached if c==0) */
    :n<100?c+i[n<20?n:n%10]-i[20+n/10] /* lookup tables */
    :
      f(n/1000,8)               /* thousand */
    + f(n/100%10,7)             /* hundred */
    + f(n%100,0)                /* rest */
    + c;                        /* carry-in */
}
main(int c, char**v)
{
    for(c=atoi(*++v);c-4;c=x)
        printf("%d is %d and ",c,x=c?f(c,0):4);
    puts("4 is the magic number");
}

```

There's an obvious extension to support millions, by replacing `f(n/1000,8)` with `f(n/1000000,7)+f(n/1000%1000,8)`.

## Test output

```
0 is 4 and 4 is the magic number
1 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
2 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
3 is 5 and 5 is 4 and 4 is the magic number
4 is the magic number
5 is 4 and 4 is the magic number
6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
7 is 5 and 5 is 4 and 4 is the magic number
8 is 5 and 5 is 4 and 4 is the magic number
9 is 4 and 4 is the magic number
10 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
17 is 9 and 9 is 4 and 4 is the magic number
100 is 10 and 10 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
142 is 18 and 18 is 8 and 8 is 5 and 5 is 4 and 4 is the magic number
1000 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
1642 is 29 and 29 is 10 and 10 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
70000 is 15 and 15 is 7 and 7 is 5 and 5 is 4 and 4 is the magic number
131072 is 37 and 37 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number
999999 is 50 and 50 is 5 and 5 is 4 and 4 is the magic number

```

# Answer
> 4 votes
## Swift 2, ~~408~~ 419 - 30 = 389 Bytes

I would be able to get rid of 176 bytes if it Swift wasn't so verbose with regular expressions (removing hyphens and spaces) \*glares at Apple\*

```
func c(var s:Int)->String{var r="";while(s != 4){r+="\(s)";let f=NSNumberFormatter();f.numberStyle=NSNumberFormatterStyle.SpellOutStyle;let v=f.stringFromNumber(s)!;s=v.stringByReplacingOccurrencesOfString("[- ]",withString:"",options:NSStringCompareOptions.RegularExpressionSearch,range:Range<String.Index>(start:v.startIndex,end:v.endIndex)).utf8.count+(s<0 ?3:0);r+=" is \(s) and "};return r+"4 is the magic number"}

```

This can be tested on swiftstub.com, here

I ran a little for loop, and it turns out that `100003` is the number between 0 and 999999 has the longest string result, which has 6 iterations, and is

> **100003** is **23** and **23** is **11** and **11** is **6** and **6** is **3** and **3** is **5** and **5** is **4** and **4** is the magic number

### Ungolfed

```
func a(var s: Int) -> String{
    var r = ""
    while(s != 4){
        r+="\(s)"

        let f = NSNumberFormatter()
        f.numberStyle = NSNumberFormatterStyle.SpellOutStyle
        let v = f.stringFromNumber(s)!
        s = v.stringByReplacingOccurrencesOfString(
            "[- ]",
            withString: "",
            options: NSStringCompareOptions.RegularExpressionSearch,
            range: Range<String.Index>(start: v.startIndex, end: v.endIndex)
        ).utf8.count + (s < 0 ? 3 : 0)

        r+=" is \(s) and "
    }
    return r+"4 is the magic number"
}

```

# Answer
> 4 votes
## Mathematica, 156 - 30 = 126 bytes

```
a=ToString;({a@#," is ",a@#2," and "}&@@@Partition[NestWhileList[#~IntegerName~"Words"~StringCount~LetterCharacter&,#,#!=4&],2,1])<>"4 is the magic number"&

```

I'm simply surprised that this uses strings and *isn't* ridiculously long.

# Answer
> 4 votes
# Haskell, 285 - 180 = 105 Bytes

In fact, there is no built-in at all for displaying number. I still dissatisfied with the score. Feel free to comment. I will experiment further, though. Still the score is better than Swift's score

```
c n|n<0=8+c(-n)|n>999=r 1000+8|n>99=7+r 100|n>19=r 10+2-g[30..59]+g[20..29]|n>15=r 10-1|2>1=[0,3,3,5,4,4,3,5,5,4,3,6,6,8,8,7]!!n where{g=fromEnum.elem n;r k=c(mod n k)+c(div n k)}
m 4="4 is the magic number"
m 0="0 is 4 and "++m 4
m n=show n++" is "++show(c n)++" and "++m(c n)

```

usage

```
m 7
"7 is 5 and 5 is 4 and 4 is the magic number"
m 999999
"999999 is 50 and 50 is 5 and 5 is 4 and 4 is the magic number"

```

Explanation.

`m` is trivial enough, however, the `c` is not. `c` is the function to count the number of character the english name of number.

```
c n |n<0=8+c(-n) -- Add word "negative" in front of it, the length is 8
    |n>999=r 1000+8 -- the english name for number with form xxx,yyy is xxx thousand yyy
    |n>99=7+r 100 -- the english name for number with form xyy is x hundred yy
    |n>19=r 10+2-g[30..59]+g[20..29] -- the english name for number with form xy with x more
                                     -- than 1 is x-ty. However *twoty>twenty,
                                     -- *threety>thirty, *fourty>forty, *fivety>fifty.
    |n>10=r 10-1-g(15:18:[11..13]) -- the english name for number with form 1x is x-teen.
                                     -- However, *oneteen>eleven, *twoteen>twelve,
                                     -- *threeteen>thirteen, *fiveteen>fifteen,
                                     -- *eightteen>eighteen
    |2>1=[0,3,3,5,4,4,3,5,5,4,3]!!n -- for number 0-10, the length is memorized. 0 is 0
                                    -- because it is omitted. Input zero is handled
                                    -- separately. If we defined 0 to be 4, then
                                    -- 20 => twenty zero.
  where g   =fromEnum.elem n      -- Check if n is element of argument array, if true, 1 else 0
        r k=c(mod n k)+c(div n k) -- Obvious.

```

# Answer
> 4 votes
# C, 268 - 180 = 88 bytes

```
#define t(x,o)n<x?o:f(n/x)+(n%x?f(n%x):0)
char*i="4335443554366887798866555766";f(n){return t(1000,t(100,n<20?n<0?8+f(-n):i[n]-48:i[n/10+18]-48+(n%10?f(n%10):0))+7)+8;}main(n){for(scanf("%d",&n);n^4;n=f(n))printf("%d is %d and ",n,f(n));puts("4 is the magic number");}

```

Try it here.

## Ungolfed

```
/* Encode number length in string (shorter representation than array) */
char*i="4335443554366887798866555766";

f(n)
{
    return n < 1000
        ? n < 100
            ? n < 20
                ? n < 0
                    ? 8 + f(-n) /* "Negative x" */
                    : i[n] - 48 /* "x" */
                : i[n/10+18] + (n%10 ? f(n%10) : 0) /* 20-99 */
            : f(n/100) + (n%100 ? f(n%100) : 0) + 7 /* x hundred y */
        : f(n/1000) + (n%1000 ? f(n%1000) : 0) + 8; /* x thousand y */
}

main(n)
{
    /* Keep printing until you get to the magic number */
    for(scanf("%d",&n);n^4;n=f(n))
        printf("%d is %d and ",n,f(n));
    puts("4 is the magic number");
}

```

# Answer
> 3 votes
## Java, 800 - 150 = 650 bytes

```
class G{static String e="",i="teen",j="ty",k="eigh",y="thir",d="zero",l="one",n="two",m="three",h="four",s="five",c="six",t="seven",b=k+"t",g="nine",D="ten",L="eleven",N="twelve",M=y+i,H=h+i,S="fif"+i,C=c+i,T=t+i,B=k+i,G=g+i,o="twen"+j,p=y+j,q="for"+j,r="fif"+j,u=c+j,v=t+j,w=k+j,x=g+j,A=" ",O=" hundred ",z,E;public static void main(String a[]){z=e;int l=new Integer(a[0]);do{E=a(l,1,e);l=E.replace(A,e).length();z=z+E+" is "+a(l,1,e)+" and ";}while(l!=4);System.out.print(z+h+" is the magic number");}static String a(int P,int _,String Q){String[]f={e,l,n,m,h,s,c,t,b,g,D,L,N,M,H,S,C,T,B,G,e,D,o,p,q,r,u,v,w,x};int R=20,X=10,Y=100,Z=1000;return P==0?(_>0?d:e):(P<R?f[P]+Q:(P<Y?(f[R+(P/X)]+" "+a(P%X,0,e)).trim()+Q:(P<Z?a(P/Y,0,O)+a(P%Y,0,e)+Q:a(P/Z,0," thousand ")+a((P/Y)%X,0,O)+a(P%Y,0,e)+Q)));}}

```

### De-golfed

```
class G {

   static String e="",i="teen",j="ty",k="eigh",y="thir",d="zero",l="one",n="two",m="three",h="four",s="five",c="six",t="seven",b=k+"t",g="nine",D="ten",L="eleven",N="twelve",M=y+i,H=h+i,S="fif"+i,C=c+i,T=t+i,B=k+i,G=g+i,o="twen"+j,p=y+j,q="for"+j,r="fif"+j,u=c+j,v=t+j,w=k+j,x=g+j,A=" ",O=" hundred ",z,E;

   public static void main(String a[]){
     z = e;
     int l = new Integer(a[0]);
     do {
             E = a(l,1,e);
             l = E.replace(A,e).length();
             z = z+E+" is "+a(l,1,e)+" and ";
     } while(l!=4);
     System.out.println(z+h+" is the magic number");
   }

   static String a(int P,int _,String Q) {
     String[] f = {e,l,n,m,h,s,c,t,b,g,D,L,N,M,H,S,C,T,B,G,e,D,o,p,q,r,u,v,w,x};
     int R=20,X=10,Y=100,Z=1000;
     return P==0?(_>0?d:e):(P<R?f[P]+Q:(P<Y?(f[R+(P/X)]+" "+a(P%X,0,e)).trim()+Q:(P<Z?a(P/Y,0,O)+a(P%Y,0,e)+Q:a(P/Z,0," thousand ")+ a((P/Y)%X,0,O)+a(P%Y,0,e)+Q)));
   }
}

```

# Answer
> 3 votes
## QC, 265 - 30 - 150 = 85 bytes

```
(✵1:oaT%=ta100%=ha100/⌋T%=X[0 3 3 5 4 4 3 5 5 4 3 6 6 8 8 7 7 9 8 8]=Y[6 6 5 5 5 7 6 6]=a0≟4a20<Xt☌YtT/⌋2-☌Xo☌+▲▲hXh☌7+0▲+)(❆1:na0<8*=ba‖1000/⌋=ca1000%=nbb✵8+0▲a✵++){I4≠:EEI" is "++=II❆=EEI" and "++=E!}E"4 is the magic number"+

```

**Test suite**

Ungolfed:

```
(✵1:
oaT%=                                        # ones
ta100%=                                      # tens
ha100/⌋T%=                                   # hundreds
X[0 3 3 5 4 4 3 5 5 4 3 6 6 8 8 7 7 9 8 8]=  # length of "zero", "one", "two", ..., "nineteen"
Y[6 6 5 5 5 7 6 6]=                          # length of "twenty", ..., "ninety"
a0≟
  4
  a20<
    Xt☌
    YtT/⌋2-☌ Xo☌ +
  ▲
▲
hXh☌7+0▲+)

(❆1:
na0<8*=                 # if negative, add 8
ba‖1000/⌋=              # split aaaaaa into bbbccc
ca1000%=
n bb✵8+0▲ a✵ ++)

{I4≠:EEI" is "++=II❆=EEI" and "++=E!}E"4 is the magic number"+

```

# Answer
> 2 votes
## JavaScript, 382 - 150 - 30 = 202 bytes

```
var o=[0,3,3,5,4,4,3,5,5,4],f=s=>(s[1]==1?[3,6,6,8,8,7,7,9,8,8][s[0]]:o[s[0]]+(s.length>1?[0,3,6,6,5,5,5,7,6,6][s[1]]:0))+(s.length==3?(7+o[s[2]]-(o[s[2]]==0?7:0)):0),l=n=>{var s=(""+n).split("").reverse();return f(s.slice(0,3))+(s.length>3?(f(s.slice(3,6))+8):0)};(n=>{var s="";while(n!=4){s+=n+" is ";n=n>=0?l(n):(l(-n)+8);s+=n+" and ";}console.log(s+"4 is the magic number");})()

```

The input is given as the parameter to the Immediately-Invoked Function Expression.

Test input:

```
999999 ->
    999999 is 50 and 50 is 5 and 5 is 4 and 4 is the magic number
17 ->
    17  is 9 and 9 is 4 and 4 is the magic number
-404 ->
    -404 is 23 and 23 is 11 and 11 is 6 and 6 is 3 and 3 is 5 and 5 is 4 and 4 is the magic number

```

De-golfed:

```
// array of the lengths of digits in ones place:
// one is 3, two is 3, three is 5, etc... zero is a special case
// and is assigned zero length because zero is never written out in a number name
var o=[0,3,3,5,4,4,3,5,5,4],

// function that computes the length of a substring of the input
// because the input is 6 digits, it can be broken into two 3 digit subsections
// each of which can have it's length calculated separately
f=s=>
  (
  s[1]==1? // check for if the tens digit is a one
    // when the tens is a one, pull the string length from an array that represents
    // ten, eleven, twelve, thirteen, etc...
    [3,6,6,8,8,7,7,9,8,8][s[0]]
  :
    // when the tens digit is not a one, add the ones digit normally and...
    o[s[0]]
    +
    // add the tens digit length from the array that represents
    // zero, ten, twenty, thirty, forty, fifty, sixty, seventy, eighty, ninety
    (s.length>1?[0,3,6,6,5,5,5,7,6,6][s[1]]:0)
  )
  +
  (
  s.length==3? // check if the length is 3 and weren't not accidentally trying to do something wierd with a minus sign
    // if so, then we have to add a hundred (7 characters) to the length and the
    // length of the ones digit that is in the hundreds place like
    // 'one' hundred or 'two' hundred
    (7+o[s[2]]-
      (
        // also, if the hundreds place was a zero, subtract out those 7 characters
        // that were added because 'hundred' isn't added if there's a zero in its
        // place
        o[s[2]]==0?
          7
        :
          0
      )
    )
  :
    // if the length wasn't 3, then don't add anything for the hundred
    0
  ),

// function that computes the length of the whole six digit number
l=n=>{
  // coerce the number into a string and then reverse the string so that the
  // ones digit is the zeroth element instead of last element
  var s=(""+n).split("").reverse();
  return
    // calculate the character length of the first 3 characters
    // like in the number 999888, this does the '888'
    f(s.slice(0,3))
    +
    // then if there actually are any characters after the first 3
    (s.length>3?
        // parse the character length of the second 3 characters
        (f(s.slice(3,6))+8)
      :
        0
    )
};
// lastly is the Immediately-Invoked Function Expression
(n=>{
  var s="";
  // as long as we haven't reached four, just keep going through the loop
  while(n!=4){
    s+=n+" is ";
    n=n>=0?l(n):(l(-n)+8) // this handles negatives by only passing positive values to l and then just adding 8 onto the length for negatives
    s+=n+" and ";
  }
  // finally just say that '4 is the magic number'
  console.log(s+"4 is the magic number");
})(999999)

```

# Answer
> 1 votes
# Moo, ~~182~~ 176/~~192~~ 188 bytes - 30 = 146/158

188 byte version:

```
u=$string_utils;s="";i=args[1];while(i-4)j=u:english_number(i);s=s+j+(s?" and "+j|"")+" is ";i=length(u:strip_chars(j,"- "}));endwhile;return s+(s?"four and "|"")+"four is the magic number"

```

176 byte **implementation-dependent** version:

```
s="";i=args[1];while(i-4)j=#20:english_number(i);s=s+j+(s?" and "+j|"")+" is ";i=length(#20:strip_chars(j," -"));endwhile;return s+(s?"four and "|"")+"four is the magic number"

```

Both are functions.

# Answer
> 1 votes
# Python 641-150 = 501 bytes

At least it isn't longer than Java! It is based on this except using strings.

**EDIT**: I forgot about 0 and that I need to say "5 is 4", not skip to "4 is the magic number" - that added a bit to the score.

```
w={0:"zero",1:"one",2:"two",3:"three",4:"four",5:"five",6:"six",7:"seven",8:"eight",9:"nine",10:"ten",11:"eleven",12:"twelve",13:"thirteen",14:"fourteen",15:"fifteen",16:"sixteen",17:"seventeen",18:"eighteen",19:"nineteen",20:"twenty",30:"thirty",40:"forty",50:"fifty",60:"sixty",70:"seventy",80:"eighty",90:"ninety"}
s=""
def i(n):
 global s
 e=""
 o=n%10
 t=n%100
 h=n/100%10
 th=n/1000
 if th:
  e+=i(th)
  e+='thousand'
 if h:
  e+=w[h]
  e+='hundred'
 if t:
  if t<20 or o==0:
   e+=w[t]
  else:
   e+=w[t-o]
   e+=w[o]
 if len(e)==4:s+="4 is the magic number";print s
 else: s+="%d is %d and "%(n,len(e));i(len(e))
In=input()
i(In)

```

Try it here!

# Answer
> 1 votes
## PHP, 168 - 30 = 138 bytes

```
function m($i){$e=strlen(preg_replace('/[^a-z-]/','',(new NumberFormatter("en",5))->format($i)));echo($i==$e?"":"$i is $e and "),($e==4?"4 is the magic number":m($e));}

```

---
Tags: code-golf, number
---


title: Bring ASCII art to the 3rd dimension

text:
# Question
Title: Bring ASCII art to the 3rd dimension
In this challenge, You have to bring ASCII art (which are usually 2D) to 3D!

# How?

like this,

```
X X DD
 X  D D
X X DD

```

to...

```
  X X DD
 X X DD D
X X DDDD
 X XDDD
X X DD

```

# Then How do we do *that*?

Given the ascii art and `N`, repeat this `N` times.

* for every character (we will call this `A`):
* let `B` be the character which is exactly 1 right and 1 up from `A`
* if `B` is a space or is undefined:
* set `B` to `A`.

# Specs

* The first input can be a string with newline characters or a list of strings representing the 2D ASCII art.
* You are allowed to use `%END%` to tag the end of input, but this is not required.
* The second input will be `N`. It will be a positive integer.
* all the lines of the strings will be the same length.

# Examples

Input: `("###\n###",1)`

Output:

```
 ###
####
###

```

# Rules

Basic rules apply.

also, If you have questions, be sure to ask in the comments!

# Answer
## Perl, 81 bytes

**75 bytes code + 6 for `-i -n0`.<br>Note that the `\e` characters are ASCII `\x1b` but `\e` is used for ease of testing.**

Please note that this solution uses ANSI escape sequences and requires a compatible terminal, as well as using the `-i` commandline argument to pass in the number of 'dimensions' you'd like.

```
$n=s/^//mg-1;s/ /\e[1C/g;print(s/^/\e[${^I}C/grm."\e[${n}A"),--$^I for($_)x$^I

```

### Usage:

In a Linux compatible terminal, run `PS1=` first to ensure your prompt doesn't overwrite the displayed image.

```
perl -i10 -n0e '$n=s/^//mg-1;s/ /\e[1C/g;print(s/^/\e[${^I}C/grm."\e[${n}A"),--$^I for($_)x$^I' <<< '
ROFL:ROFL:ROFL:ROFL
         _^___
 L    __/   [] \
LOL===__        \
 L      \________]
         I   I
        --------/
'

          ROFL:ROFL:ROFL:ROFL
         ROFL:ROFL:ROFL:ROFL
        ROFL:ROFL:ROFL:ROFL
       ROFL:ROFL:ROFL:ROFL\
      ROFL:ROFL:ROFL:ROFL\_]
     ROFL:ROFL:ROFL:ROFL\_]
    ROFL:ROFL:ROFL:ROFL\_]/
   ROFL:ROFL:ROFL:ROFL\_]/
  ROFL:ROFL:ROFL:ROFL\_]/
 ROFL:ROFL:ROFL:ROFL\_]/
   LOL==___^___]_\_\_]/
  LOL==__/ \_[]_\_\_]/
 LOL===__ \______\_]/
  L      \________]/
          I---I---/
         --------/

perl -i3 -n0e '$n=s/^//mg-1;s/ /\e[1C/g;print(s/^/\e[${^I}C/grm."\e[${n}A"),--$^I for($_)x$^I' <<< 'X X DD
 X  D D
X X DD
'
   X X DD
  X X DD D
 X X DDDD
  X XDDD
 X X DD

```
> 18 votes

# Answer
## CJam, ~~25~~ 24 bytes

```
{{' 1$f+La@+..{sS@er}}*}

```

An unnamed block that expects a list of strings and the number of repetitions on the stack and leaves a new list of strings instead.

Test it here. (Includes a test wrapper that reads the string from STDIN for convenience.)

### Explanation

```
{       e# Repeat this block N times...
  '     e#   Push a space character.
  1$    e#   Copy the current grid.
  f+    e#   Prepend the space to each line of the grid.
  La    e#   Push [[]].
  @+    e#   Pull up the other copy of the grid and prepend the [].
        e#   We've now got two copies of the grid, one shifted right by
        e#   a cell and one shifted down by a cell. We now want to replace
        e#   spaces in the latter with the corresponding character in the
        e#   former.
  ..{   e#   For each pair of characters in corresponding positions...
    s   e#     Turn the character in the down-shifted grid into a string.
    S   e#     Push " ".
    @   e#     Pull up the character from the right-shifted grid.
    er  e#     Replace spaces with that character.
  }
}*

```
> 8 votes

# Answer
## APL, 49 bytes

```
{⎕UCS 32⌈{s+(s=0)×1⊖¯1⌽s←0⍪⍵,0}⍣⍺⊣(32∘≠×⊣)⎕UCS↑⍵}

```

Input: vector of character vectors. Example:

```
      2 {⎕UCS 32⌈{s+(s=0)×1⊖¯1⌽s←0⍪⍵,0}⍣⍺⊣(32∘≠×⊣)⎕UCS↑⍵} 'X X DD' ' X  D D' 'X X DD'
  X X DD
 X X DD D
X X DDDD
 X XDDD
X X DD

```

How it works:

* `↑⍵` turns the argument into a matrix of chars
* `⎕UCS` from char to integer
* `(32∘≠×⊣)` substitute the spaces (32) with zeroes
* `...⍣⍺⊣` apply ⍺ (the left argument) times the function on the left
* `s←0⍪⍵,0` border with zeroes on top and on the right the argument
* `1⊖¯1⌽` rotate 1 up and 1 right
* `s+(s=0)×` sum to the original the shifted version but only on top of the zeroes of the original
* `32⌈` turns back the zeroes into 32s
* `⎕UCS` from integer to char
> 4 votes

# Answer
# MATL, 24 bytes

```
:"ct32>*TTYatFTEqYSy~*+c

```

Input format is

```
2
{'X X DD', ' X  D D', 'X X DD'}

```

So the other example is

```
1
{'###', '###'}

```

The output contains extra whitespace, which is allowed by the challenge.

**Try it online!**

---

If a 2D char array is acceptable as input (I've asked the OP twice...), the first `c` can be removed, so **23 bytes**:

```
:"t32>*TTYatFTEqYSy~*+c

```

Input format in this case is (all strings have equal lengths, which may require right-padding with spaces):

```
2
['X X DD '; ' X  D D'; 'X X DD ']

```

**Try it online!**

---

### Explanation

```
:        % Input number n implicitly. Generate [1 2 ... n]
"        % For loop: repeat n times
  c      %   Convert to char array. In the first iteration it inputs a cell array of
         %   strings implicitly and converts to a 2D char array, right-padding with
         %   spaces. In the next iterations it does nothing, as the top of the stack
         %   is already a 2D char array
  t32>*  %   Convert characters below 32 into 0
  TT     %   Push array [1 1]
  Ya     %   Pad the 2D char array with one zero in the two directions (up/down,
         %   left/right), on both sides
  t      %   Duplicate
  FTEq   %   Push array [-1 1]
  YS     %   Circularly shift the 2D char array one unit up and one unit right
  y      %   Push a copy of the non-shifted 2D array
  ~      %   Logical negate: nonzero entries become 0, zero entries become 1. This
         %   will be used as a mask for entries that need to be changed. Since the
         %   values at those entries are zero, we can simply add the new values. We do
         %   that by multiplying the mask by the shifted array and adding to the
         %   non-shifted array
  *      %   Multiply element-wise
  +      %   Add element-wise
  c      %   Convert the 2D array back to char
         % End for
         % Implicitly display

```
> 4 votes

# Answer
## Convex, 23 bytes

Byte count assumes CP-1252 encoding.

```
{{' 1$f+La@+..{sS@Ë}}*}

```

An unnamed block that expects a list of strings and the number of repetitions on the stack and leaves a new list of strings instead.

Try it online!

This is a direct port of my CJam answer to Convex (which is heavily based on CJam). The only difference is that Convex uses `Ë` instead of `er` for transliteration, saving one byte. Thanks to GamrCorps for letting me know about it.
> 3 votes

# Answer
# Pyth, ~~54~~ 33 bytes

```
ju+++dhG.bsmh|-d;;.t,Y+dNdtGGeG.*

```

Test suite.
> 2 votes

# Answer
# Ruby, 95 bytes

```
->a,n{n.downto(0){|i|f="<Esc>[1C"
$><<a.gsub(/^/,f*i).gsub(" ",f)+(i>0?"<Esc>[#{a.lines.size-1}A":"")}}

```

Each `<Esc>` is a literal ESC character (`0x1b`).

## Usage

Assign the lambda to a variable e.g. `func`.

```
art = <<END
X X DD
 X  D D
X X DD
END

func[art, 2]
# Prints:
#   X X DD
#  X X DD D
# X X DDDD
#  X XDDD
# X X DD

```

## Ungolfed

```
->(art, num) {
  num.downto(0) do |i|
    forward = "\e[1C"
    $> << art.gsub(/^/, forward * i).gsub(" ", forward) +
            (i > 0 ? "\e[#{art.lines.size - 1}A" : "")
  end
}

```

The `forward` escape sequence, `\e[1C`, moves the cursor forward (right) 1 space and `\e[<n>A` moves it up `n` lines. Basically what this code does is print the "layers" back to front, replacing spaces with the `forward` sequence to avoid overwriting the other layers with a space.
> 2 votes

# Answer
# Python 2, 116 bytes

```
S=' '
def f(a,d):e=[S*len(`a`)];exec"a=[''.join(t[t[1]>S]for t in zip(S+x,y+S))for x,y in zip(a+e,e+a)];"*d;return a

```

I’ll golf this more soon.
> 2 votes

# Answer
## JavaScript (ES6), 128 bytes

```
f=(a,n)=>n?f((a=[``,...a].map(s=>[...s||` `])).map((b,i)=>i--&&b.map((c,j)=>a[i][++j]>' '?0:a[i][j]=c))&&a.map(b=>b.join``),n-1):a

```

Accepts and returns an array of strings, prepends an extra row for the output, ensures each row contains at least a space, splits them all up into characters, loops though trying to copy the characters to the row above and column to the right, then recursively calls itself to complete the loop.
> 2 votes

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


title: How much snow did you get?

text:
# Question
Title: How much snow did you get?
My apologies for the wordiness. We had fun with it at work in our internal golfing, but it required a few emails for clarification, so I hope I captured most of that the first time.

## PROBLEM

Given a “simulated” snowfall snapshot (as a string, stdin or parameter to your function/method), report on 4 values: minimum depth, maximum depth, average depth, and duration.

Here’s a formatted example to illustrate the input:

```
* * **
** * ***
** *  *
*
--------

```

The ‘\*’ is a snowflake and the ‘-‘ is the ground. Imagine all of those “snowflakes” falling toward the ground. This is the final “snapshot”:

```
*
*
** * **
********
--------

```

You need to report on:

1. Minimum depth - count the shortest “pile” (1, in example above)
2. Maximum depth - count the tallest “pile” (4, in example above)
3. Average depth - average count of all “piles” (1.9, in example above - rounding to tenths)
4. Duration - (each “fall” = 1 second) - time from the first snapshot to the last snapshot (3 seconds, in example above)

Another example for reference:

```
     *
   *   *
      *
*
--------

```

Final snapshot:

```
*  * ***
--------

```

## INPUT

The starting “snapshot” will have 8 “rows”, 8 “columns”, and be pipe-delimited (the pipes separate the rows). For example (excluding quotes):

```
“        |        |        |        |     *  |   *   *|      * |*       |--------”

```

## OUTPUT

The 4 values pipe-delimited on a single line: **0|1|.6|3** or **0|5|1|1**

# Answer
> 1 votes
## Perl, 128 chars

```
map{$d++;s/\*/$d{$-[0]}++;$t&&$t<$d or$t=$d/ge}split'\|',<>;map{$A+=$_/8}@m=sort values%d;printf"$m[0]|$m[-1]|%.1f|%d\n",$A,8-$t

```

# Answer
> 6 votes
## Python, 153 characters

```
s=raw_input()
R=range(8)
C=[s[i::9].count('*')for i in R]
print"%d|%d|%.1f|%d"%(min(C),max(C),sum(C)/8.,max(8-s[i::9].find('*')-C[i]for i in R if C[i]))

```

# Answer
> 1 votes
## Windows PowerShell, 180 ~~189~~

```
$a=(0..7|%{$x=$_;-join(0..7|%{$s[$_*9+$x]})})
$b=$a-replace' '|%{$_.length}|sort
"{0}|{1}|{2:.0}|{3}"-f($b[-1..0]+(($b-join'+'|iex)/8),($a|%{($_-replace'^ +|\*').length}|sort)[-1])

```

Input comes in as `$s`.

History:

* 2011-02-10 01:53 (189) – First attempt.
* 2011-02-10 02:03 (180) – Format string to the rescue. Only downside: It outputs numbers in regional format, no longer strictly conforming to the task specification. Still, that's a problem shared by the C# solution as well so I guess that's ok.

# Answer
> 0 votes
A couple other language results from our internal golfing:

## C#, 188 characters (easily readable)

```
int a = 0, b = 8, c = 0, d = 0, f, i, j, x;
for (i = 0; i < 8; i++)
{
      f = x = 0;
      for (j = 0; j < 8; )
            if (s[i + j++ * 9] == '*')
            {
                  x = x > 0 ? x : 9 - j;
                  f++;
            }

      d += f;
      a = f > a ? f : a;
      b = f < b ? f : b;
      c = x - f > c ? x - f : c;
}

Console.Write("{0}|{1}|{2:.0}|{3}", b, a, d / 8f, c);

```

## Ruby, 173 characters

```
s=gets;n=8;a=o=l=0;8.times{|i|f=x=0;8.times{|j|if(s[i+j*9].chr=='*'):x=8-j if x==0;f+=1;end}
o+=f;a=f if f>a;n=f if f<n;l=x-f if x-f>l}
printf "%d|%d|%.1f|%d",n,a,o.to_f/8,l

```

# Answer
> 0 votes
# PHP, 139 bytes

```
<?for(;$y<8;$y++)for($x=0;++$n[$x],$x<8;$x++)'!'>$argv[1][$y*9+$x]&&--$n[$x]?$b[$x]++:0;print_r([min($n),max($n),array_sum($n)/8,max($b)]);

```

for each column, count no. of snowflakes and no. of spaces below the first snowflake, then calculate
takes string as argument from command line

**breakdown** and golfing steps

```
$i=$argv[1];
for(;$y<8;$y++)         # $y=row
{
    for($x=0;$x<8;$x++) # $x=column
    {
        // loop body: 32+26=58 bytes
        if('*'==$i[$p=$y*9+$x])$n[$x]++;# if snowflake: increase snowflakes count
        elseif($n[$x]+=0)$b[$x]++;      # elseif has snowflakes: increase blanks count
                                        # +=0: min needs a value in every column

        // -> golf if/elseif to ternaries, 16+9+25+1 = 51 (-7)
#       '*'==$i[$y*9+$x]
#           ? $n[$x]++
#           : (($n[$x]+=0)?$b[$x]++:0)
#       ;

        // golfing on the ternary, 15+23+9+1 = 48 (-3)
#       '!'>$i[$y*9+$x]                 # -1: char<'!' <=> char==' '
#           ? ($n[$x]+=0)?$b[$x]++:0    # -2: inverted condition -> eliminated parens
#           : $n[$x]++
#       ; # 15+23+9+1-2=46

        // increase snowflakes count in any case (initialization)
        // (needs curlies; elminate them by moving increase to the for condition)
        // decrease snowflakes count for blank
#       ++$n[$x];if('!'>$i[$y*9+$x]&&--$n[$x])$b[$x]++; # if: 47
#       ++$n[$x];'!'>$i[$y*9+$x]&&--$n[$x]?$b[$x]++:0;  # ternary: 46
    }
}
print_r([min($n),max($n),array_sum($n)/8,max($b)]); # calculate and print results

```

add `round(...,1)` around `array_sum($n)/8` for rounding (+9)

# Answer
> 0 votes
## *Mathematica*, ~115

```
"        \n        \n* * **  \n        \n** * ***\n** *  * \n*       \n--------"

Most/@ToCharacterCode@%~Partition~9/10-16/5
Min@#|Max@#|Mean@#~Round~.1|Position[#,1][[{-1,1},1]].{1,-1}-1&@Total@%

```

> ```
> 1 | 4 | 1.9 | 4
>
> ```

In this post I had to resort to the escaped string form `\n` as paste and copy loses spaces. In the Front End I can enter it like this:

# Answer
> 0 votes
# JavaScript, 328 Bytes

Not particularly short, but it's what I've got.

```
var input = "        |        |        |* * **  |        |** * ***|** *  * |*       |--------";

(s=>{var l=s.split("|"),a=[0,0,0,0,0,0,0,0],o=[8,0,0,0],b;for(i=0;i<l.length;i++){if(!b&&l[i]!="        ")o[3]=7-i,b=1;for(j=0;j<l[i].length;j++){a[j]+=l[i][j]=="*"?1:0}}for(i=0;i<a.length;i++){if(a[i]<o[0])o[0]=a[i];if(a[i]>o[1])o[1]=a[i];o[2]+=a[i];}console.log(o[0]+"|"+o[1]+"|"+(o[2]/a.length).toFixed(1)+"|"+o[3]);})(input)

```

De-golfed:

```
var input = "        |        |        |        |     *  |   *   *|      * |*       |--------";

(s=>{
  var splits = s.split("|");
  var arr = [0,0,0,0,0,0,0,0];
  var b;
  var o=[8,0,0,0];
  for (var i = 0; i < splits.length; i++) {
    if (!b&&splits[i]!="        ") {
      o[3] = 7-i;b=1;
    }
    for (var j = 0; j < splits[i].length; j++) {
      arr[j]+=splits[i][j]=="*"?1:0;
    }
  }
  for (var i = 0; i < arr.length; i++) {
    if (arr[i]<o[0]) {
      o[0]=arr[i];
    }
    if (arr[i]>o[1]) {
      o[1]=arr[i];
    }
    o[2]+=arr[i];
  }
  console.log(o[0]+"|"+o[1]+"|"+(o[2]/arr.length).toFixed(1)+"|"+o[3]);
})(input)

```

---
Tags: code-golf
---


title: Reverse Bayer Filter of an image

text:
# Question
Title: Reverse Bayer Filter of an image
Almost all digital camera sensors are organized in a grid of photosensors. Each photo sensor is sensitive for one of the primary colors: red, green and blue. The way those photo sensors are organized is called the Bayer filter, after its inventor, Bryce Bayer of Eastman Kodak. After an image is taken, four photo sensors compose the RGB value of one pixel in the resulting image. Your task is to reverse that process and colorize the resulting pixels according to their filter color. For the sake of simplicity, we will ignore gamma correction.

For example: the "normal" forward Bayer filter steps are:

* a lightray with a Pantone Beeswax color hits the sensor;
* the BGGR (Blue - Green / Green - Red) filter decomposes this into four rays.
* The four rays hit the sensor, which reads: 81 - 168 / 168 - 235 (sensor values range from 0 - 255);
* The Bayer filter translates this to one RGB pixel with color (235, 168, 81).

The reverse Bayer filter steps are:

* RGB pixel with color (235, 168, 81) is split into four pixels with RGB values: (0,0,81) - (0,168,0) / (0,168,0) - (235,0,0).

## Challenge

You should write the shortest possible function or program that does the following:

* Take a filename as in input and output the DeBayered image.
* The output may be written to a file or displayed on the screen.
* The output must be twice the width and twice the height of the original image.
* Each pixel of the input image must be mapped according to the BGGR (Blue - Green / Green - Red) Bayer filter pattern as explained graphically in the following picture:
* We'll assume that both green photosensors receive the same signal, so both the G values in the Bayer matrix are equal to the G value in the RGB image.
* You may *not* return an array representation of the resulting image. The output must be an image or a file (in any suitable image format) that can be displayed as an image.

## Example

Given this file as an input:

The resulting image should be:

## Reference python implementation:

```
from PIL import Image
import numpy
import sys

if len(sys.argv) == 1:
    print "Usage: python DeByer.py <<image_filename>>"
    sys.exit()

# Open image and put it in a numpy array
srcArray = numpy.array(Image.open(sys.argv[1]), dtype=numpy.uint8)
w, h, _ = srcArray.shape

# Create target array, twice the size of the original image
resArray = numpy.zeros((2*w, 2*h, 3), dtype=numpy.uint8)

# Map the RGB values in the original picture according to the BGGR pattern#

# Blue
resArray[::2, ::2, 2] = srcArray[:, :, 2]

# Green (top row of the Bayer matrix)
resArray[1::2, ::2, 1] = srcArray[:, :, 1]

# Green (bottom row of the Bayer matrix)
resArray[::2, 1::2, 1] = srcArray[:, :, 1]

# Red
resArray[1::2, 1::2, 0] = srcArray[:, :, 0]

# Save the imgage
Image.fromarray(resArray, "RGB").save("output.png")

```

Remember: this is a , so shortest code wins!

# Answer
> 6 votes
# Pyth, 26 bytes

```
MXm03H@GH.wsMsgLRRR,U2tU3'

```

Expects the input filename with quotation marks on stdin, and writes to `o.png`. Example output:

# Answer
> 6 votes
# Matlab, ~~104~~ 92 bytes

This makes use of the 3d-array/matrix representation of RGB images in Matlab, as well as the Kronecker product which is exactly what we need creating this new 2x2 "metapixel" form each source pixel. The output is then displayed in a popup window.

```
a=double(imread(input('')));for n=1:3;b(:,:,n)=kron(a(:,:,n),[1:2;2:3]==n)/255;end;imshow(b)

```

Resized screencapture:

# Answer
> 5 votes
# Python 3, ~~259~~ 254 bytes

```
from PIL.Image import*
o=open(input())
w,h=o.size
n=new('RGB',(2*w,2*h))
P=Image.putpixel
for b in range(w*h):x=b//h;y=b%h;r,g,b=o.getpixel((x,y));c=2*x;d=2*y;G=0,g,0;P(n,(c,d),(0,0,b));P(n,(c+1,d),G);P(n,(c,d+1),G);P(n,(c+1,d+1),(r,0,0))
n.save('o.png')

```

The input filename is given in standard input. Outputs to `o.png`.

Example usage:

```
$ echo mona-lisa.jpg | python bayer.py

```

# Answer
> 4 votes
# Mathematica ~~118~~ 127 bytes

The original submission used an actual picture as input. This uses a filename instead.

It applies two replacement rules to the image data of the referenced file:

1. For each row of the image data matrix,replace each pixel {r,b,g} with a blue pixel, {0,0,b} followed by a green pixel, {0,g,0};
2. Separately, for each row of the image data matrix, replace each pixel {r,b,g} with a green pixel {0,g,0} followed by a red pixel, {r,0,0};

Then `Riffle` (i.e. interleave) the matrices resulting from 1 and 2.

```
Image[Riffle[#/.{{_,g_,b_}:>(s=Sequence)[{0,0,b},{0,g,0}]}&/@(m=Import[#,"Data"]/255),#/.{{r_,g_,_}:>s[{0,g,0},{r,0,0}]}&/@m]]&

```

---

```
Image[Riffle[#/.{{_,g_,b_}:>(s=Sequence)[{0,0,b},{0,g,0}]}&/@(m=Import[#,"Data"]/255),#/.{{r_,g_,_}:>s[{0,g,0},{r,0,0}]}&/@m]]&["mona.jpg"]

```

# Answer
> 3 votes
# J, ~~100~~ ~~96~~ 90 bytes

```
load'bmp'
'o'writebmp~,./,./($a)$2 1 1 0(_2]\(2^0 8 8 16)*{)"1(3#256)#:,a=:readbmp]stdin''

```

This is a script in J that reads the filename of the input image from stdin and outputs the result to a file named `o`. The input and output images will both be in `bmp` format. It also expects only the filename to be input, meaning that leading and trailing whitespace should not be present.

### Sample Usage

```
$ echo -n mona.bmp | jconsole reversebayer.ijs

```

### Explanation

```
A=:readbmp]stdin''  Store the image in A as a 2d array of 24-bit rgb ints
,                   Flatten it into a list
(3#256) #:          Convert each 24-bit int to a tuple of 8-bit r/g/b ints
2 1 1 0 {"1         Select each column in BGGR order
(2^0 8 8 16) *      Shift each color to make it a 24-bit rgb value
_2 ]\               Convert each row from dimensions 1x4 to 2x2
($A) $              Reshape the list of 2x2 matrices into a matrix of
                    2x2 matrices with dimensions matching A
,./                 Append the 2x2 matrices by column
,./                 Append the 2x2 matrices by row - This is now a matrix of
                     24-bit rgb values with twice the dimensions of A
'o'writebmp~        Write the image array to a bmp file named 'o'

```

# Answer
> 0 votes
# Python 2, ~~256~~ 275 bytes

First I simplified the original code:

```
from PIL import Image
from numpy import*
import sys

# Open image and put it in a numpy array
srcArray = array(Image.open(sys.argv[1]), dtype=uint8)
w, h, _ = srcArray.shape

# Create target array, twice the size of the original image
resArray = zeros((2*w, 2*h, 3), dtype=uint8)

# Map the RGB values in the original picture according to the BGGR pattern#

# Blue
resArray[::2, ::2, 2] = srcArray[:, :, 2]

# Green (top row of the Bayer matrix)
resArray[1::2, ::2, 1] = srcArray[:, :, 1]

# Green (bottom row of the Bayer matrix)
resArray[::2, 1::2, 1] = srcArray[:, :, 1]

# Red
resArray[1::2, 1::2, 0] = srcArray[:, :, 0]

# Save the imgage
Image.fromarray(resArray, "RGB").save("o.png")

```

Then minify to:

```
from PIL import Image
from numpy import*
import sys
a=array(Image.open(sys.argv[1]),dtype=uint8)
w,h,_=a.shape
b=zeros((2*w,2*h,3),dtype=uint8)
b[::2,::2,2]=a[:,:,2]
b[1::2,::2,1]=a[:,:,1]
b[::2,1::2,1]=a[:,:,1]
b[1::2,1::2,0]=a[:,:,0]
Image.fromarray(b,"RGB").save("o.png")

```

Resulting in the image `o.png`:

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


title: Collect and place items

text:
# Question
Title: Collect and place items
The goal of this challenge is to collect selected items in a list and move them to a certain location in the list.

As a visual example, take the input values (represented by black boxed integers) and a corresponding list of truthy values where true denotes the item is selected (represented by blue boxes, where `T` is truthy and `F` is falsy):

The first logical step is to separate the items marked truthy and not truthy into their corresponding lists. Note that relative order in each list must be maintained (i.e. the order of selected items must be `1,4,5`, and the order of unselected items must be `2,3,6,7`)!

The second logical step is given an index in the remaining list of unselected items, insert all selected items before the item at the given index. Assuming indexing starts at 0, suppose you want to insert the selection at index 3. This corresponds to the spot before the `7` box, so the selected items should be inserted before the `7`.

The final solution is then `2,3,6,1,4,5,7`.

Note that this logical diagram depicts one way this could be done; your program does not need to take the same logical steps as long as the output always produces the same observable result.

# Input

Your program is given 3 inputs:

1. A list of integers representing the items. This may be an empty list. This list will always consist of unique positive integers, not necessarily in sorted order (i.e. 5 will not be in the list twice).
2. A list of truthy/falsy values with the same length as the list of items, where a truthy value represents that the item at the same index has been selected.
3. An integer representing where to insert the selection. You may choose what the index of the first item of the list is as long as it is constant in every run of your program (e.g. the first item could be index 0 or index 1). Please specify which convention your program adheres to. This index should be in the range `[starting_idx, ending_idx+1]`, i.e. it will always be a valid index. For the case index is `ending_idx+1`, the selection should be inserted at the end of the list. You may assume this integer will fit into your language's native integer type.

The input may come from any source desired (stdio, function parameter, etc.)

# Output

The output is a list representing the final sequence of items. This can be to any source desired (stdio, return value, function output parameter, etc.). You are allowed to modify any of the inputs in-place (for example, given a modify-able list as a function parameter, and having your function operate in-place on that list).

# Test cases

All of the following test cases assume 0-based indexing. I've used 0 and 1 to indicate falsy/truthy values respectively for the selection mask.

Test cases happen to have lists formatted as `[a,b,c]`, but as long as your input lists represent a finite ordered sequence that's fine.

**Input:**

```
[]
[]
0

```

**Output:**

```
[]

```

**Input:**

```
[1,2,3,4,5,6,7]
[1,0,0,1,1,0,0]
3

```

**Output:**

```
[2,3,6,1,4,5,7]

```

**Input:**

```
[1,2,3,4,5,6,7]
[1,0,0,1,1,0,0]
0

```

**Output:**

```
[1,4,5,2,3,6,7]

```

**Input:**

```
[1,2,3,4,5,6,7]
[1,0,0,1,1,0,0]
4

```

**Output:**

```
[2,3,6,7,1,4,5]

```

**Input:**

```
[1,2,3,4,5,6,7]
[1,1,1,1,1,1,1]
0

```

**Output:**

```
[1,2,3,4,5,6,7]

```

**Input:**

```
[1,2,3,4,5,6,7]
[0,0,0,0,0,0,0]
5

```

**Output:**

```
[1,2,3,4,5,6,7]

```

**Input:**

```
[1,3,2,5,4,6]
[1,0,0,1,1,0]
3

```

**Output:**

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

```

# Scoring

This is code golf; shortest answer in bytes wins. Standard loopholes are prohibited. You are allowed to use any built-ins desired.

# Answer
> 10 votes
# MATL, 9 bytes

```
&)i:&)bwv

```

This solution accepts an array of `T` (true) and `F` (false) values as the second input. Also for the first test case, with empty arrays, it produces no output.

**Try it Online!** and a slightly modified version for all test cases.

**Explanation**

```
    % Implicitly grab the first two inputs
&)  % Index into the first array using the boolean, places two items on the stack:
    % 1) The values where the boolean is TRUE and 2) the values where it is FALSE.
i   % Explicitly grab the third input (N)
:   % Create an array from 1...N
&)  % Index into the FALSE group using this array as an index. Puts two items on the stack:
    % 1) The first N elements of the FALSE group and 2) other members of the FALSE group
b   % Bubble the TRUE members up to the top of the stack
w   % Flip the top two stack elements to get things in the right order
v   % Vertically concatenate all arrays on the stack
    % Implicitly display the result

```

# Answer
> 5 votes
# Mathematica, ~~66~~ 62 bytes

Saved 4 bytes from @MartinEnder.

```
a=#2~Extract~Position[#3,#4>0]&;##&@@@Insert[##~a~0,##~a~1,#]&

```

Anonymous function. Takes the 1-based index, the list, and the markers as input and returns the reordered list as output.

# Answer
> 3 votes
## Haskell, 70 bytes

```
m%n=[e|(e,b)<-zip m n,b]
(l#s)p|(h,t)<-splitAt p$l%(not<$>s)=h++l%s++t

```

Usage example: `([1,2,3,4,5,6,7]#[True,False,False,True,True,False,False]) 3` -\> `[2,3,6,1,4,5,7]`.

How it works:

```
m%n=[e|(e,b)<-zip m n,b]        -- helper function, that extracts the elements of m
                                -- with corresponding True values in n
(l#s)p                          -- l: list of values
                                   s: list of booleans
                                   p: position to insert
  |                   (not<$>s) -- negate the booleans in s
                    l%          -- extract elements of l
          splitAt p             -- split this list at index p
   (h,t)<-                      -- bind h to the part before the split
                                -- t to the part after the split
     = h++l%s++t                -- insert elements at True positions between h and t

```

# Answer
> 3 votes
## JavaScript (ES6), 76 bytes

```
(a,b,c)=>(d=a.filter((_,i)=>!b[i]),d.splice(c,0,...a.filter((_,i)=>b[i])),d)

```

# Answer
> 1 votes
# Jelly, 10 bytes

```
¬+\>⁵Ḥ³oỤị

```

Try it online!

### How it works

```
¬+\>⁵Ḥ³oỤị  Main link.
            Arguments: x (list of Booleans), y (list of inputs), z (index)
¬           Logical NOT; invert all Booleans in x.
 +\         Take the cumulative sum.
            This replaces each entry with the number of zeroes up to that entry.
   >⁵       Compare the results with z.
            This yields 0 for the first z zeroes, 1 for all others. The behavior
            for ones is not important.
    Ḥ       Unhalve; multiply the previous resulting by 2.
     ³o     Take the element-wise logical NOT of x and the previous result.
            This replaces all but the first z zeroes in x with twos.
       Ụ    Grade up; sort the indices of the result according to the corr. values.
        ị   Retrieve the items of y at those indices.

```

# Answer
> 0 votes
## C#, 132 bytes

```
int[]r(int[]a,bool[]b,int l){var x=a.Where((i,j)=>!b[j]);return x.Take(l).Concat(a.Where((i,j)=>b[j])).Concat(x.Skip(l)).ToArray();}

```

**ungolfed:**

```
    public static int[] r(int[] a,bool[] b,int l)
    {
        var x = a.Where((i, j) => !b[j]);
        return x.Take(l).Concat(a.Where((i, j) => b[j])).Concat(x.Skip(l)).ToArray();
    }

```

improvement ideas appreciated.

# Answer
> 0 votes
## Python 3, 106 93 bytes

```
def f(x,y,z):
 t,f=[],[]
 for n in range(len(x)):(f,t)[y[n]].append(x[n])
 f[z:z]=t
 return f

```

Older version:

```
def f(x,y,z):
 t,f=[],[]
 for n in range(len(x)):
  if y[n]:t+=[x[n]]
  else:f+=[x[n]]
 f[z:z]=t
 return f

```

# Answer
> 0 votes
# Python 3, 91 bytes

```
def f(a,x,i):b=[c for c,z in zip(a,x)if z<1];return b[:i]+[c for c in a if(c in b)<1]+b[i:]

```

where `a` is the elements/numbers list,`x` is the `True/False` list and `i` is the index.

Multiline version for improved readability:

```
def f(a,x,i):
    b=[c for c,z in zip(a,x)if z<1]
    return b[:i]+[c for c in a if(c in b)<1]+b[i:]

```

How does it work?

The call to `zip(a,x)` results in a list of tuples where each of them contains the info: `(element,0|1)`. Then a list comprehension is used to determine the elements that have a `0/False` value associated and stores them in the variable `b`.

So `[c for c,z in zip(a,x)if z<1]` creates a list that contains all the elements that have a `0`(`False`) value associated.

After that, the list of elements which have a `True|1` value associated (which is determined by checking which elements of `a` are not present in `b` : `[c for c in a if(c in b)<1]`) is inserted in the list with all the elements that have a `0`(`False`) value associated (list `b`) at the specified index `i` and the resulting list is returned.

---
Tags: code-golf, sorting
---


title: Visualize chain rule

text:
# Question
Title: Visualize chain rule
# Definition

The chain rule with two functions state that:

```
D[f(g(x))] = f'(g(x)) * g'(x)

```

Or, alternatively:

```
D[f1(f2(x))] = f1'(f2(x)) * f2'(x)

```

The chain rule with three functions state that:

```
D[f(g(h(x)))] = f'(g(h(x))) * g'(h(x)) * h'(x)

```

Or, alternatively:

```
D[f1(f2(f3(x)))] = f1'(f2(f3(x))) * f2'(f3(x)) * f3'(x)

```

Et cetera.

# Task

* Given an integer between 2 and 21, output the chain rule with that many functions, either in the first form or in the second form.
* Please specify if you are using the second form.

# Specs

* The format of the string must be exactly that stated above, with:
    1. all the spaces kept intact
    2. a capitalized `D`
    3. a square bracket immediately following `D`
    4. the asterisk kept intact
* One extra trailing space (U+0020) is allowed.
* Leading zeros in the function names in the second form (e.g. `f01` instead of `f1`) is allowed.

# Testcases

If you use the first form:

```
input output
2     D[f(g(x))] = f'(g(x)) * g'(x)
3     D[f(g(h(x)))] = f'(g(h(x))) * g'(h(x)) * h'(x)

```

If you use the second form:

```
input output
2     D[f1(f2(x))] = f1'(f2(x)) * f2'(x)
3     D[f1(f2(f3(x)))] = f1'(f2(f3(x))) * f2'(f3(x)) * f3'(x)

```

### Leaderboard

```
var QUESTION_ID=86652,OVERRIDE_USER=48934;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 6 votes
## Python 2, 79 bytes

```
f=lambda n:0**n*"D[x] ="or f(n-1).replace("x","f%d(x)"%n)+1%n*" *"+" f%d'(x)"%n

```

Outputs with numbered functions.

Builds the output by repeatedly replacing each `x` with `fn(x)`, then appending `* fn'(x)`. The `*` is omitted for `n==1`.

Compare to the iterate program (92 bytes):

```
r="D[x] = ";n=0
exec'n+=1;r=r.replace("x","f%d(x)"%n)+"f%d\'(x) * "%n;'*input()
print r[:-3]

```

---

**96 bytes:**

```
n=input();r='';s='x'
while n:s='f%d(%%s)'%n%s;r=" * f%d'"%n+s[2:]+r;n-=1
print"D[%s] = "%s+r[3:]

```

Outputs with numbered functions.

Accumulates the nested function `f1(f2(f3(x)))` in `s` and the right-hand-side expression in `r`. The string formatting is clunky; f-strings from 3.6 would do better.

# Answer
> 6 votes
# Sesos, 49 bytes

```
0000000: 2ac992 63fb92 245fb6 6c57be 255bbe 2cc9bf 6d49da  *..c..$_.lW.%[.,..mI.
0000015: 025e7f fdced0 fd67f8 fcde33 b6a7b2 643d4f 65597e  .^.....g...3...d=OeY~
000002a: f77a72 dd73cf fe                                  .zr.s..

```

Try it online

### Disassembled

```
set numin
add 68   ; 'D'
put
sub 7    ; '=' - 'D'
fwd 1
add 32   ; ' '
fwd 1
add 91   ; '['
put
add 2    ; ']' - '['
fwd 1
add 102  ; 'f'
fwd 1
add 40   ; '('
fwd 3
add 120  ; 'x'
rwd 2
get
jmp
    jmp
        fwd 1
        add 1
        rwd 3
        put
        add 1
        fwd 1
        put
        fwd 1
        sub 1
    jnz
    sub 1
    rwd 1
    add 1    ; ')' - '('
    fwd 3
    put
    rwd 1
    jmp
        rwd 3
        sub 1
        fwd 1
        put
        fwd 1
        add 1
        fwd 1
        sub 1
    jnz
    rwd 4
    put
    get
    add 41   ; ')'
    rwd 1
    put
    rwd 1
    put
    get
    add 42   ; '*'
    fwd 1
    put
    fwd 2
    put
    add 1
    fwd 1
    sub 2    ; '\'' - ')'
    put
    add 1    ; '(' - '\''
    put
    fwd 1
jnz
fwd 2
put
rwd 5
put

```

# Answer
> 3 votes
# JavaScript (ES6), 89 bytes

```
f=n=>--n?f(n).replace(/x/g,`${c=(n+15).toString(36)}(x)`)+` * ${c}'(x)`:`D[f(x)] = f'(x)`

```

Or 75 bytes using the second form:

```
f=n=>n>1?f(n-1).replace(/x/g,`f${n}(x)`)+` * f${n}'(x)`:`D[f1(x)] = f1'(x)`

```

Or 82/64 bytes if I'm allowed an extra `1 *` term:

```
f=n=>n?f(n-1).replace(/x/g,`${c=(n+14).toString(36)}(x)`)+` * ${c}'(x)`:`D[x] = 1`
f=n=>n?f(n-1).replace(/x/g,`f${n}(x)`)+` * f${n}'(x)`:`D[x] = 1`

```

# Answer
> 1 votes
# Ruby, 72 bytes

Second form. Port to Ruby from @Neil answer.

```
f=->n{n>1?f[n-1].gsub(?x,"f#{n}(x)")+" * f#{n}'(x)":"D[f1(x)] = f1'(x)"}

```

# Answer
> 1 votes
# Julia, 66 bytes

```
!x=x>1?replace(!~-x,"x","f$x(x)")*" * f$x'(x)":"D[f1(x)] = f1'(x)"

```

Port of @Neil's ES6 answer. Uses the second form.

# Answer
> 0 votes
# Python 2, 174 bytes

```
i=input()+1
a=lambda x:'('.join(['f%d'%e for e in range(x,i)])+'(x'+')'*(i-x)
print'D[%s] = %s'%(a(1),' * '.join(["f%d'%s%s)"%(e+1,'('*(i-e-2>0),a(e+2))for e in range(i-1)]))

```

Lots of room left to be golfed here. Uses the second form (`f1`, `f2`, etc.).

# Answer
> 0 votes
# JavaScript (ES6), 194 bytes

```
n=>{s="D[";for(i=1;i<=n;i++)s+="f"+i+"(";s+="x";s+=")".repeat(n);s+="] = ";for(i=1;i<=n;i++){s+="f"+i+"'(";for(j=i+1;j<=n;j++)s+="f"+j+"(";s+="x";s+=")".repeat(n-i+1);if(i-n)s+=" * ";}return s;}

```

31 bytes saved thanks to @LeakyNun.

It's an anonymous lambda function. I'm sure there's some way to shorten this...

## Ungolfed

```
var chain = function(n) {
    var str = "D["; // derivative symbol
    for (var i = 1; i <= n; i++) {
        str += "f"+i+"("; // put in n functions, each labeled f1(, f2(, etc.
    }
    str += "x"; // add in the function input, usually "x"
    for (var i = 0; i < n; i++) {
        str += ")"; // add in n end parentheses
    }
    str += "] = "; // add in the end bracket and the equals operator
    for (var i = 1; i <= n; i++) {
        str += "f"+i+"'("; // add in all n of the outer functions with the prime operator
        for (var j = i+1; j <= n; j++) {
            str += "f"+j+"("; // add in all of the inner functions
        }
        str += "x"; // add in the input, "x"
        for (var j = 1; j <= n; j++) {
            str += ")"; // close the parentheses
        }
        if (i !== n) {
            str += " * "; // the multiplication of all of the outer primed functions
        }
    }
    return str;
};

```

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---


title: Calculate the number e

text:
# Question
Title: Calculate the number e
From Wikipedia:

> The number e is an important mathematical constant that is the base of the natural logarithm. It is approximately equal to 2.71828, and is the limit of (1 + 1/n)n as n approaches infinity.

## Challenge

Calculate the number e to 15 digits after the decimal point.

This means that your output must start with `2.718281828459045` or equivalent.

Your program can output digits after the required output - these may be accurate or inaccurate, inaccuracy after 15 digits does not disqualify you from the challenge. Your program may also output nothing after the required 15 digits.

This is , shortest implementation in bytes wins.

## Constraints

* You may not use built in constants or hardcode the number.
* Standard loopholes and rules apply.

## Reference Implementation (Ruby)

```
def e(i)
  e = 1.0                        # make it floating point
  i.times { |n|                  # loop repeats n times
    e += 1.0/(1..n+1).reduce(:*) # factorial - no factorial function
  }                              # in the Ruby standard library
  return e
end
e(200)                           # Almost certainly will return e

```

# Answer
> 0 votes
# Haskell, ~~33~~ 31 Bytes

*-2 Bytes thanks to @xnor*

```
sum[1/product[1..i]|i<-[0..99]]

```

Straightforward implementation of the series definition. (I have posted a version of this to Reddit before.)

# Answer
> 0 votes
## Haskell, 25 bytes

```
f 99=0;f n=1+f(n+1)/n;f 0

```

26 bytes:

```
foldr(\x y->1+y/x)0[1..99]

```

---
Tags: code-golf, number
---


title: Number to String

text:
# Question
Title: Number to String
# Number to String

## Instructions

Convert a signed 32-bit integer to a string (base-10 preferably) without any string formatting calls (or built in type coercion that will directly convert a number to a string).

Negative numbers must include leading `-`.

## Score Calculation

Shortest byte length; Tie breaker by efficiency (execution time)

# Answer
> 4 votes
# JavaScript ES6, ~~61~~ ~~57~~ ~~46~~ ~~45~~ 42 bytes

Apparently this is what you want.

Apparently Leaky Nun saved me 17 bytes.

Output in binary:

```
f=n=>n<0?"-"+f(-n):n?f(n>>1)+"01"[n%2]:"0"

```

Output in decimal:

```
f=n=>n<0?"-"+f(-n):n<10?"0123456789"[n]:f(n/10|0)+f(n%10)

```

# Answer
> 3 votes
# Jelly, ~~14~~ 12 bytes

```
~~”-“”<?0³AD+48Ọ~~
<0”-x³AD+48Ọ

```

Try it online!

---
Tags: code-golf, restricted-source
---


title: CAPTCHA Modified by Evil Mathematician

text:
# Question
Title: CAPTCHA Modified by Evil Mathematician
# CAPTCHA Modified by Evil Mathematician

I accidentally incurred the wrath of an eccentric passive-aggressive mathematician. As part of his demented idea of payback, he modified the CAPTCHA system on my favorite website. Up until now, it would just ask a moderately challenging math question, like `3+2^4`, and I would simply type the answer, `19`, to verify that I am a human being. But now, thanks to my mathematical nemesis, the CAPTCHA questions are obnoxiously hard to calculate by hand and it keeps me from logging into my profile!

From what I can tell, this is what he has done. The CAPTCHA images seem to still be the same, but the way it calculates the correct answer has changed. It takes the expression displayed in the image and rotates the operations. You wouldn't believe how long it took me to figure this out T\__T.

Because of this fiasco, I need a program/function that takes in one of these expressions as a string, evaluates it and returns the result so that I can log onto my website! **To make this a game, fewest bytes win.**

Ok, you have the idea, lets walk through an example. Suppose that the CAPTCHA displayed an image with `6+5+4-3*2/1`. Normally the answer would `9`. Instead, we now have to rotate the operations to the right and that gives us `6/5+4+3-2*1`. At this point, we evaluate it to be `6.2`

## Summary

Steps to evaluate the string input:

1. **Rotate** the operation to the right
2. **Evaluate** the result

## Specifications

* Full program or function
* Standard I/O
* Takes an expression
* Prints/Returns the evaluated result
    + After the op rotation
* Possible operations are `+-/*^`
    + The negatives for negative numbers stays with the number when rotating
    + Follow the normal order of operations after the rotation is completed
    + Using integer division is allowed
* Possible numbers are positive/negative integers
    + This does not include `0`
* Parentheses could be included, but aren't rotated

## Test Cases

```
Input     -> Output
1+3       -> 4
7+6       -> 13
1+1-2     -> 2
3*4+2     -> 11
-7^4      -> -2401
3*7+1-3   -> -1
-9+4/4    -> 1.75
(4*1)+8   -> 40
1+2-3*4/5 -> -16.5
1+-2*3    -> 1
3*4--2    -> 11
30-2/7    -> 8
120*3-4+10-> 122
(13^-12)+11 -> 1

```

**Update**

* \[16-07-28\] Fixed typo in last test case. I had posted the expression after rotating it once \>\___\> , so that rotating a second time gave an incorrect answer. It is fixed now! Thanks to @sintax!
* \[16-08-13\] Removed broke test case. Thanks again to @sintax!

# Answer
> 3 votes
# Dyalog APL, 30, but soon to be 16 bytes

```
⍎w⊣((w∊f)/w)←¯1⌽w∩f←'+-×÷'⊣w←⍞

```

Ungolfed, explained version:

`w ← ⍞` Prompt for input (of the expression) and assign to *w*

`f ← '+-×÷'` assign the symbols to *f*

`((w ∊ f) / w) ← ¯1 ⌽ w ∩ f` using membership of *f* as mask, reassign those positions in *w* to the corresponding character in the cyclic 1-step-right rotated intersection of *w* and *f* (the symbols)

`⍎w` execute the modified expression

There is no special handling of minus/negative, because APL uses the distinct symbols `-` and `¯`.

See the rotation of symbols on TryAPL!

In version 16 it will be much shorter as a function which takes the expression as argument:

```
⍎¯1∘⌽@(∊∘'+-×÷')

```

Execute  the negative one step rotation `¯1∘⌽` done on `@` members of the symbols set `(∊∘'+-×÷')`.

# Answer
> 6 votes
# Python 3.5, ~~118~~ ~~113~~ 164 bytes:

```
from re import*
def R(U):Z='(?<!\d)-\d+|\d+|[()]';O=sub(Z,'',U);print(eval(sub(Z,'%s',U).translate(str.maketrans(O,O[::-1])).replace('^','**')%tuple(findall(Z,U))))

```

A named function. Can probably be golfed down more. This will take quite a while and apparently plenty of memory to compute the solution for the input:

```
((22^22)+2*2^2^2^2*2-2+222222+22222*-2222-2*222*2*2+2^-2+(2+2+2+2+2)+222/222+2+22*2*2)*2*2*2

```

~~I started processing this with my program about 30 minutes ago as of the time of this edit (9:52 PM on July 27, 2016) and it is still going.~~ ~~EDIT: Well, it eventually started to take up too much memory, so I had to stop it at around 1 hour after I started, at around 10:52 PM on July 7, 2016.~~

EDIT # 2: Well, even for the updated last test case it's pretty much the same thing, as it takes quite a while for my program to start finding the answer before it eventually quits out on me with error code 137.

Try It Online for the Rest of the Test Cases! (Ideone)

# Answer
> 3 votes
## Python 3, 195 bytes:

```
import re;I=input();x=[i for i in I if i in'+-*/^'];print(eval(''.join([i[0]+i[1]for i in[i for i in map(list,zip(*[[i for i in re.split('[+*/^-]',I)],x[-1:]+x[:-1]+['']]))]]).replace('^','**')))

```

Takes input on STDIN and leaves a number on STDOUT. I know that R. Kap already posted a Python answer, but the method I used is actually pretty interesting, so I thought I'll post this anyway.

The program first makes an the list: `[chunks splitted by math chars, math chars rotated to the right]`. It then transposes the array, flattens, converts to string, and evaluates.

# Answer
> 3 votes
## JavaScript (ES7), 154 bytes

```
f=
s=>[(s=s.replace(/(\(*-?\d+\)*)(.?)/g,(_,d,o)=>a.push(d)&&o,a=[])).slice(-1),...s.slice(0,-1)].map((o,i)=>a[i]+=o)&&eval(a.join` `.replace(/\^/g,'**'))
;
```

```
<input id=i placeholder=Input><input id=o placeholder=Output><input type=button value=Go onclick=o.value=f(i.value);>
```

Works by removing the values into a separate array so that the operators can be rotated.

# Answer
> 2 votes
## Matlab, 114 chars

Okay, so the last test case evaluates to `Inf` (once rotated, the expression 2^222222 appears...), but otherwise, all test cases hit.

Dealing with negatives, especially non-initial negatives, gave me fits.

```
i=input('');d=regexp(i(2:end),'[^\d|\)|\(]');d=d(~[0 d(2:end)-d(1:end-1)==1]);i(d+1)=i(1+d([end,1:end-1]));eval(i)

```

Inputs should be wrapped in single quotes (e.g., `'2+3/5-(12*5)'`), as per Matlab standard for string inputs.

Ungolfed and commented:

```
i=input('');                        # Get input from stdin.
d=regexp(i(2:end),'[^\d|\)|\(]');   # Find the positions of non-digit/paren characters
                                    # in the non-initial portion of the input.
d=d(~[0 d(2:end)-d(1:end-1)==1]);    # If there are consecutive operator-type characters,
                                    # assume the second is a negativity indicator and
                                    # delete its index from our list of operator indices.
i(d+1)=i(1+d([end,1:end-1]));       # Replace each non-initial operator character of the
                                    # input with its own right-rotated operator from our
                                    # list of operator characters
eval(i)                             # Evaluate the string expression we just built.

```

---
Tags: code-golf, math
---


title: Teach me how to add!

text:
# Question
Title: Teach me how to add!
Everyone knows how to add numbers by hand, right?––Well, I hope so, but for anyone who needs a quick reminder:

To add `17282` and `1342`, you proceed as follows:

1. place the larger (value wise, not number of digits) number above the smaller number and match up the digits

```
17282
 1342

```
2. draw the plus sign (+) to the left of the equation on the second row. The plus sign must be flush with the left side.

```
 17282
+ 1342

```
3. draw a line of dashes (-) with one dash in each column of the digits of the first line

```
 17282
+ 1342
 -----

```
4. evaluate the expression and write the digits above each column if you need to 'carry' them

```
   1
 17282
+ 1342
 -----
 18624

```

Your output is what you get after applying step #4. You may have trailing whitespace, but there may not be any leading zeroes.

You must write a program or a function that prints or returns the output.

The input can be taken as either two separate inputs or an array with two items; the type of the inputs can be either string or integer.

This is code golf so shortest code in bytes wins!

**Edit:**

The largest number you could expect to receive as output/the sum is the largest integer that your system will display without exponents (thanks to Adám).

**More examples:**

```
Input:
1596, 8404
Output:
1111
 8404
+1596
 ----
10000

Input:
1776, 76
Output:
  11
 1776
+  76
 ----
 1852

Input:
123, 456
Output:
 456
+123
 ---
 579

```

# Answer
> 4 votes
# Dyalog APL, 90 bytes

```
{⌽↑(⊂⌽s),⍨↓⌽(' + ',⍨' 1'⊃⍨l<⍴s),'-'⍪⍨w⍪⍨' 1'[10|(⍎¨(-l←⍴⍉w)↑s←⍕+/⍵)-(+/0 10⊤⍎)¨⊂[0]w←⍕⍪⍵]}

```

Takes list of two numbers as argument. Needs `⎕IO←0` which is default on many systems.

```
      f←{⌽↑(⊂⌽s),⍨↓⌽(' + ',⍨' 1'⊃⍨l<⍴s),'-'⍪⍨w⍪⍨' 1'[10|(⍎¨(-l←≢⍉w)↑s←⍕+/⍵)-(+/0 10⊤⍎)¨⊂[0]w←⍕⍪⍵]}
      f¨(17282 1342)(1596 8404)(1776 76)(123 456)
┌──────┬─────┬─────┬────┐
│   1  │1111 │  11 │    │
│ 17282│ 1596│ 1776│ 123│
│+ 1342│+8404│+  76│+456│
│ -----│ ----│ ----│ ---│
│ 18624│10000│ 1852│ 579│
└──────┴─────┴─────┴────┘

```

TryAPL online! Note that `⎕IO` has been set and  has been emulated with `e` as  is banned from TryAPL for security reasons.

### Ungolfed and explained

> `{` An anonymous function
>
> > `w ← ⍕ ⍪⍵` *w* gets the textified vertical arrangement of the argument (the numbers to be added)
> >
> > `l ← ≢ ⍉w` *s* gets the count of rows in the transposed *w* (i.e. the number of columns in *w*)
> >
> > `s ← ⍕ +/⍵` *s* gets the textified sum of the argument
> >
> > `' 1'[`... index into the string " 1", so zeros give spaces, and ones give character 1s.
> >
> > > `⊂[0] w` enclose down, gets list of pairs of corresponding digits in the numbers
> > >
> > > `(+/ 0 10 ⊤ ⍎)¨` for each pair; make into digit(s), then sum
> > >
> > > `(⍎¨ (-l) ↑ s)-` chop left-most digit of grand total to the width of the longest input, then make each character into separate number and subtract the column sums (if the sum does not add up to the total, the discrepancies are due to carrys, so this gives us each column's carry)
> > >
> > > `10|` division remainder when divided by 10
> >
> > `]` \[end of indexing\]
> >
> > `w⍪⍨` stack the input numbers below
> >
> > `'-'⍪⍨` stack a minus below each column
> >
> > `(' + ',⍨' 1'⊃⍨l<⍴s),` prepend a space to the 2nd line, a plus to the 3nd, a space to the 4rd, and a one or space to the 1st – depending on if the sum is wider than the widest input (meaning we need a carry high over the plus )
> >
> > mirror right-left (so left-justification will be to the right)
> >
> > make table into list of lines (so that differing line lengths are allowed
> >
> > `(⊂⌽s),⍨` append the sum
> >
> > combine list of lines into table (padding the right with spaces as needed)
> >
> > mirror back to normal
>
> `}` \[end of function\]\`

# Answer
> 4 votes
# Python 2.7, ~~201~~ ~~192~~ ~~161~~ ~~155~~ ~~167~~ ~~164~~ 182 bytes:

(*Saved 2 bytes (`192->190`) thanks to TheBikingViking*)

```
def Q(T,Y):O,D=sorted([T,Y]);E=len(`D`);print'%s\n %s\n+%*s\n %s\n %d'%(''.join([' ',i[0]][len(i)>1]for i in[`sum(map(int,u))`for u in zip(`D`,'%0*d'%(E,O))]),D,E,O,'-'*E,sum([T,Y]))

```

A named function that takes input in any order while outputting the correct answer in order of magnitude from top to bottom.

Try it Online! (Ideone)

---

Alternatively, if allowed to take input in order of magnitude (i.e. bigger number first, then smallest), then here is a much smaller solution which also uses a named function at **164 bytes**:

```
def Q(T,Y):E=len(`T`);print'%s\n %d\n+%*d\n %s\n %d'%(''.join([' ',i[0]][len(i)>1]for i in[`sum(map(int,u))`for u in zip(`T`,`Y`.zfill(E))]),T,E,Y,'-'*E,sum([T,Y]))

```

Try this Version Online! (Ideone)

# Answer
> 2 votes
# Ruby, ~~192~~ 191 bytes

Returns a multiline string. Input is an array with two strings.

Try it online!

```
->o{x,y=o.sort_by!(&:to_i).map{|e|e.reverse.chars}
a,b=o.map &:to_i
k=' '
y.zip(x).map{|z|i,j=z.map &:to_i
k=i+j+k.to_i<10?' ':1}.reverse*''+"
 %s
+%#{s=y.size}s
 %s
%#{s+1}s"%[b,a,?-*s,a+b]}

```

# Answer
> 0 votes
# C (ansi), ~~392~~ 384 Bytes

Saved 8 thanks to Value Ink (392-\>384)

## Code:

```
char c[9],d[9],p[99]=" %s\n%0s\n+%0s\n %s\n%0i",*t,*b;k,r;main(a,i,m,n)char**i;{m=strlen(i[1]);n=strlen(i[2]);m==n?(strcmp(i[1],i[2])<0?t=i[2],b=i[1]:(t=i[1],b=i[2])):m<n?t=i[2],b=i[1]:(t=i[1],b=i[2]);n>m?:(n^=m,m=n^m,n=n^m);p[18]=p[5]=1+(p[10]=48+n);while(k<n)d[k]=45,a=(n-++k>=0)*(t[n-k]-48)+(m-k>=0)*(b[m-k]-48),r+=a*pow(10,k-1),c[n-k-1]=32+(a+c[n-k]%2>9)*17;printf(p,c,t,b,d,r);}

```

## With Spacing:

```
char c[9],d[9], p[99] = " %s\n%0s\n+%0s\n %s\n%0i", *t,*b;
k,r;
main(a,i,m,n)char**i;{
    m=strlen(i[1]);     //get length of num 1
    n=strlen(i[2]);     //get length of num 2
                        //Set the larger number to the top pointer
    m==n?(strcmp(i[1],i[2])<0?t=i[2],b=i[1]:(t=i[1],b=i[2])):m<n?t=i[2],b=i[1]:(t=i[1],b=i[2]);
    n>m?:(n^=m,m=n^m,n=n^m); //set n to the longer length
    p[18]=p[5]=1+(p[10]=48+n); //set the buffers in the printf string

    while(k<n)     //for every number
        d[k]=45,   //add a dash
        a=(n-++k>=0)*(t[n-k]-48)+(m-k>=0)*(b[m-k]-48), //do the addition
        r+=a*pow(10.,(float)k-1), //add to result
        c[n-k-1]=32+(a+c[n-k]%2>9)*17;  //set 1 if carry or a space otherwise

    printf(p,c,t,b,d,r);    //print to stdio
}

```

## Usage:

### Compile Params:

```
gcc -O3 -ansi -lm -o add add.c

```

### Input:

```
./add 2834 97829

```

### Output:

```
  11 1
  97829
 + 2834
  -----
 100663

```

## Notes:

Only works on numbers up to 8 in length - formatting is hard or I'm really bad at it

I feel like my approach was suboptimal

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