title: Eeny, meeny, miny, moe

text:
# Question
Title: Eeny, meeny, miny, moe
# Introduction

The childhood song *Eeny, meeny, miny, moe* was often used to select who was "it" when playing tag. Everyone would stand in a circle and point at one person selected at random. They would sing:

> Eeny, meeny, miny, moe,
> Catch a tiger by the toe.
> If he hollers, let him go,
> Eeny, meeny, miny, moe.

As they sung each word, they pointed at the next person in the circle. The person being pointed to when the final "moe" was sung would be "it". The children would immediately stand up and scatter.

# Goal

Implement the shortest program in bytes that takes an input, the number of children, and lists the words that were sung when they were being pointed at.

The winner will be selected in one week.

# Input

From STDIN, a single, positive integer, the number of children. This may be more than the number of words in the song.

# Output

Writes to STDOUT a list where each line represents a child and contains the word sung while they were being pointed at. If there are too many children, empty lines may be omitted.

# Requirements

* Always start with the first child.
* Display the words without punctuation.
* The final "moe" should be emphasised as "MOE!" including punctuation.

# Example

## Input

```
3

```

## Output

```
Eeny moe tiger toe hollers go miny
meeny Catch by If let Eeny MOE!
miny a the he him meeny

```

## Input

```
7

```

## Output

```
Eeny by him
meeny the go
miny toe Eeny
moe If meeny
Catch he miny
a hollers MOE!
tiger let

```

## Input

```
1

```

## Output

```
Eeny meeny miny moe Catch a tiger by the toe If he hollers let him go Eeny meeny miny MOE!

```

## Input

```
21

```

## Output

```
Eeny
meeny
miny
moe
Catch
a
tiger
by
the
toe
If
he
hollers
let
him
go
Eeny
meeny
miny
MOE!

```

# Answer
# TeaScript, 82 bytes

```
D`${a="Ey Ú9y ·ny "}¶e C® a g by e e If  Ò@s ¤t m go ${a}MOE!`q.KαtΣj═)j╝

```

Decompress, chunk, transpose, join, output.

## Explanation

```
              // Implicit: x = input
D`...blah...` // Decompress "Eeny miny moe..."
q             // Split
Kα            // chunk into x-size blocks (α == x)
t             // Transpose
Σ             // Loop through lines
j═)             // Join with spaces
j╝            // Join with newline

```

Try it online

---

**Non-competing 81 byte**

The `α` wasn't getting chained `.` so I had to bug fix this

```
D`${a="Ey Ú9y ·ny "}¶e C® a g by e e If  Ò@s ¤t m go ${a}MOE!`qKαtΣj═)j╝

```
> 5 votes

# Answer
# Pyth, ~~103~~ ~~89~~ 84 chars

*Saved 18 bytes with string compression, thanks to @Dennis and @FryAmTheEggman*
*Saved another byte thanks to @isaacg*

Warning: there are many unprintables in the code; use the links below to try it.

```
VQjd%Q>cs[J."@y)òÎ5O¹c×Ú"."@yæ\J}ÇZH66¥ÓÀD¸¶=ðÉ §J%ÔþÖúÅ="J"MOE!")\@N

```

Try it online | Test suite

Could probably be golfed. Suggestions welcome!

### How it works

```
VQjd%Q>cs[J."..."."..."J"MOE!")\@N    Implicit: Q = eval(input)
VQ                                    For each item N in range 0...int(Q):
         [                    )        Create an array out of the following:
          J."..."                       Set J to this string, decompressed. ("Eeny@meeny@miny@")
                 ."..."                 This string, decompressed. ("moe@Catch@...let@him@go@")
                       J                J.
                        "MOE!"          "MOE!".
        s                              Join the array with the empty string.
       c                       \@      Split the result on "@".
      >                          N     Cut off the first N items.
    %Q                                 Take every Qth item.
  jd                                   Join with spaces.

```
> 6 votes

# Answer
# Jelly, 84 bytes

```
“£Dṡ“Ṙ©“Ė“¡Ḳ⁵“=U“¡Ẹ⁵“¡Ṇm“ȯf“ŀQ“ÞṖċ¥“ṅ_“Ẉ1“¡æḷ“¡ƒmxĠ“¡ṇƭEỤr“¡Þ¦»ṫ-2;;“MOE!”W¤sƓZj€⁶j⁷

```

Try it online!
> 5 votes

# Answer
# JavaScript (ES6), 167 bytes

```
l=Array(n=+prompt()).fill``;`${s=`Eeny meeny miny `}moe Catch a tiger by the toe If he hollers let him go ${s}MOE!`.split` `.map((w,i)=>l[i%n]+=w+` `);alert(l.join`
`)
```

## Explanation

```
l=Array(              // l = array of lines
  n=+prompt()         // n = input number
).fill``;             // initialise l as empty strings

`${s=`Eeny meeny miny `}moe Catch a tiger by the toe If he hollers let him go ${s}MOE!`

.split` `.map((w,i)=> // for each word w
  l[i%n]+=w+` `       // add it to the lines
);
alert(l.join`
`)                    // output the lines

```
> 5 votes

# Answer
## Haskell, ~~160~~ 157 bytes

```
import Data.Lists
unlines.map unwords.transpose.(`chunksOf`(["moe Catch a tiger by the toe If he hollers let him go","MOE!"]>>=words.("Eeny meeny miny "++)))

```

Prepend `"Eeny meeny miny "` to the other parts (`"moe Catch ..."` and `"MOE!"`), concatenate both strings, split into words, take chunks of required size, transpose and concatenate again into a single string.

@Mauris found 3 bytes by factoring out the common substring "Eeny meeny miny " and making `f` pointfree.
> 4 votes

# Answer
## Ruby, 160 bytes

```
puts (a=[*%w[Eeny meeny miny moe Catch a tiger by the toe If he hollers let him go Eeny meeny miny MOE!].each_slice(gets.to_i)])[0].zip(*a[1..-1]).map{|x|x*' '}

```

All my attempts at "compressing" the string have just made it longer. ~~Still trying...~~

```
puts                      # output to STDOUT...
(a=                       # assign this stuff to the variable a
 [*                       # convert to array...
  %w[blah blah]           # %w splits on spaces
  .each_slice(gets.to_i)  # split into slices of input number
 ]
)[0]                      # take the first element of a
.zip(*a[1..-1])           # zip it with the remaining elements
                          #   because transpose complains about ragged 2D arrays
.map{|x|x*' '}            # join all sub-arrays on space
                          #   puts automatically inserts newlines for us

```
> 3 votes

# Answer
## Python 3, ~~279~~ ~~278~~ ~~272~~ 173 bytes

(thanks to Mathias Ettinger who literally saved me **100+ BYTES!**)

```
s=" Eeny meeny miny moe Catch a tiger by the toe If he hollers let him go Eeny meeny miny moe!";w=s.split();i=input();i=int(i)
for z in range(i):W=w[z::i];print(" ".join(W))

```

If anyone has tips or sugestions I'd really appreciate them. Thanks!
> 3 votes

# Answer
# Python 2, ~~154~~ 147 bytes

**EDIT:** Thanks Joe Willis!

```
i=input()
s='Eeny meeny miny '
for j in range(i):print' '.join((s+'moe Catch a tiger by the toe If he hollers let him go '+s+'MOE!').split()[j::i])

```

This uses the trick that \[0::n\] prints the nth element of the list.

Try it here
> 3 votes

# Answer
# JavaScript (ES6), 189 bytes:

```
a=prompt(),b=Array(a--).fill``,c=0;"Eeny meeny miny moe Catch a tiger by the toe If he hollers let him go Eeny meeny miny MOE!".split` `.map(v=>(b[c]+=v+' ',c+=c>a-1?-c:1));alert(b.join`\n`)

```

# Explanation:

```
a=prompt(), //Get the STDIN
b=Array(a--).fill``, //Make an array based on how many kids there are
c=0; //Start the iteration variable
"Eeny meeny miny moe Catch a tiger by the toe If he hollers let him go Eeny meeny miny MOE!"
.split` `.map(
    v=>(
        b[c] += v + ' ',
        c += c > a - 1 ? -c : 1
    )
);alert(b.join`\n`)

```
> 3 votes

# Answer
# Japt, ~~90~~ ~~87~~ 86 bytes

```
Uo mW{V=`EydÚ9yd·nyd` +`¶C®»dgdbydÈIfddÒ@sd¤tdmdgod{V}MOE!` qd f@Y%U¥W} m¸·

```

Lots of unprintables. Try it online!

### How it works

```
              // Implicit: U = input
Uo mW{     }  // Create the range 0...U and map each item W to:
V=`...`       //  Set V to this string, decompressed. "Eenydmeenydmined"
+`...{V}MOE!` //  Concatenate it with this string, decompressed, with V inserted.
qd            //  Split at "d"s.
f@Y%U¥W       //  Filter to only the items where (index % U == W).
m¸            // Map each item by joining with spaces.
·             // Join the result with newlines.

```

I've tried compressing the string with different delimiters. The only thing more efficient than spaces would be a lowercase letter, but most of these are already used, and thus, can't be used to split the string. Here's how much compression is achieved with the remaining ones:

```
space -> 69 bytes
c -> 66 (including a null byte)
d -> 65
j -> 69
k -> 69
p -> 68
q -> 69
s -> 61 (but there's an s in "hollers")
u -> 65
w -> 67
x -> 69
y -> 69

```

Currently I'm using `d`. It may be possible to save a byte with `s`, substituting some other letter in `hollers`.
> 2 votes

# Answer
# Mathematica, 154 bytes

```
StringRiffle[Thread@Partition[StringSplit@"Eeny meeny miny moe Catch a tiger by the toe If he hollers let him go Eeny meeny miny MOE!",#,#,1,""],"
"," "]&

```

Uses the split-chunk-transpose-join-output method of most of the other answers.
> 2 votes

# Answer
# MATLAB, 167 bytes/characters:

```
n=input('');s='Eeny meeny miny ';s=strsplit([s 'moe Catch a tiger by the toe If he hollers let him go ' s 'MOE!']);f=@fprintf;for i=1:n f('%s ',s{i:n:end});f('\n');end

```

# Explanation:

```
n=input('');             % Grab the input (number of children)
s='Eeny meeny miny ';    % Common string portion
% Build the full string and split into cell array at spaces
s=strsplit([s 'moe Catch a tiger by the toe If he hollers let him go ' s 'MOE!']);
f=@fprintf;              % Just a shorthand for later (only saves 1 char here)
for i=1:n                % Loop to the number of children
    f('%s ',s{i:n:end}); % Print each nth word, shifted by child
    f('\n');             % Start each child's words on a new line
end

```

Won't be winning any awards for the length of this one, but it was fun. :-)
> 2 votes

---
Tags: code-golf, string, kolmogorov-complexity
---


title: Calculate the Lunar Phase

text:
# Question
Title: Calculate the Lunar Phase
# Introduction

**tl;dr**

In this challenge you have to calculate the moon's phase for a given date.

---

This challenge is inspired by the ~~game~~ *psycho social audiovisual experiment* "Superbrothers: Sword & Sworcery EP". In *S:S&S EP* the moon's phases are important to the outcome of the adventure as some events occur only at a specific point in time.

The question is: *Which lunar phase is present on a specific date.* Each main phase – from new moon to first quarter to full moon to third quarter – is about 7.38 days long. The whole lunar cycle is roughly 29.52 days. Based on these values various methods of calculation exist.1

# Input

* A date based on the Gregorian calendar, between 1 January 1970 and 31 December 2116.
* You can choose one of the following formats: `yyyy-mm-dd`, `dd.mm.yyyy`, `dd/mm/yyyy`, `yyyymmdd` or `ddmmyyyy`.

# Output

Output the index `[0-7]` of the lunar phase based on this zero-indexed array:

```
['New moon', 'Waxing crescent', 'First quarter', 'Waxing gibbous', 'Full moon', 'Waning gibbous', 'Third quarter', 'Waning crescent`]

```

# Requirements

* You can write a program or a function. If you go with an anonymous function, please include an example of how to invoke it.
* Input is accepted from `STDIN`, command line arguments, as function parameters or from the closest equivalent.
* This is so shortest answer in bytes wins.
* Built-ins or external libraries that calculate the moon phase are not allowed.2
* Standard loopholes are disallowed.

# Tests

The values are: `date | index of the phase | illumination | name`

A full lunar cycle:

```
08.02.2016 | 0 |   0% | New moon
07.02.2016 | 7 |   2% | Waning crescent
07.02.2016 | 7 |   2% | Waning crescent
06.02.2016 | 7 |   6% | Waning crescent
05.02.2016 | 7 |  12% | Waning crescent
04.02.2016 | 7 |  19% | Waning crescent
03.02.2016 | 7 |  28% | Waning crescent
02.02.2016 | 7 |  37% | Waning crescent
01.02.2016 | 6 |  47% | Third quarter
31.01.2016 | 5 |  56% | Waning gibbous
30.01.2016 | 5 |  65% | Waning gibbous
29.01.2016 | 5 |  74% | Waning gibbous
28.01.2016 | 5 |  82% | Waning gibbous
27.01.2016 | 5 |  89% | Waning gibbous
26.01.2016 | 5 |  94% | Waning gibbous
25.01.2016 | 5 |  98% | Waning gibbous
24.01.2016 | 4 | 100% | Full moon
23.01.2016 | 3 | 100% | Waxing gibbous
22.01.2016 | 3 |  97% | Waxing gibbous
21.01.2016 | 3 |  93% | Waxing gibbous
20.01.2016 | 3 |  86% | Waxing gibbous
19.01.2016 | 3 |  77% | Waxing gibbous
18.01.2016 | 3 |  67% | Waxing gibbous
17.01.2016 | 3 |  56% | Waxing gibbous
16.01.2016 | 2 |  45% | First quarter
15.01.2016 | 1 |  33% | Waxing crescent
14.01.2016 | 1 |  23% | Waxing crescent
13.01.2016 | 1 |  14% | Waxing crescent
12.01.2016 | 1 |   7% | Waxing crescent
11.01.2016 | 1 |   2% | Waxing crescent
10.01.2016 | 0 |   0% | New moon

```

Random test cases:

```
14.12.2016 | 4 | 100% | Full moon
16.10.1983 | 3 |  75% | Waxing gibbous
04.07.1976 | 2 |  47% | First quarter
28.11.1970 | 0 |   0% | New moon

```

As most methods aren't accurate to a scientific level and you also get mixed results on different websites for a couple of these days, it is acceptable if your results are within a *± 1 day* range.

# Bonus

Reduce your byte count and *withdraw*:

* **15%** – Print the actual name of the phase as listed in section **Output** instead of its index.
* **25%** – Print the dates of the upcoming new and full moon separated by a whitespace or newline on empty input.

---

1 For example: Calculating phase on Wikipedia.
2 Sorry Mathematica.

# Answer
# Python ~~2~~ 3, ~~255~~ ~~204~~ ~~180~~ 178 bytes

This is answer is inaccurate by a day or two in several places, including for some of the test cases, though I was told that some inaccuracy was acceptable. At any rate, the motion of the moon is never very exact and this function remains generally correct (or at least, it doesn't vary too far).

**Edit:** In the course of correcting my code and making it more accurate, I have golfed it down considerably.

**Edit:** This code is now a one-line Python 3 program. (Credit to TimmyD for the name "magic numbers")

```
p,q,r=(int(i)for i in input().split("-"));t=q<3;y=p-2000-t;i,j=divmod(((r+(153*(q+12*t-3)+2)//5+365*y+y//4-y//100+y//400+11010)*86400-74100)%2551443,637861);print((86400<=j)+2*i)

```

Ungolfed:

```
def jul(p,q,r):
    '''
    The Julian Day Number (JDN) of the input minus the JDN of January 7, 1970,
    the first new moon after January 1, 1970.
    '''
    t=q<3
    y=p-2000-t  # -2000 years to push day 0 to January 1, 2000
    return r+(153*(q+12*t-3)+2)//5+365*y+y//4-y//100+y//400+11010
    # +11010 days to push day 0 to January 7, 1970

def moon(s):
    '''
    Input format: yyyy-mm-dd

    An attempt at explaining the "magic numbers"
    - 29.53059 days is close to 2551443 seconds, so I used that
    - The offset of +12300 seconds because the new moon of 1970-01-07 was at 2035 UTC
      or 12300 seconds before midnight. For those of you saying that this pushes
      the beginning of my calendar to 2035, *6* January 1970, yes it does.
      But if I need to the calendar to recognize 1970-01-07 as the day of the new moon
      which means that midnight needed to be a positive number of seconds, 0 <= x < 86400.
      Basically, I hacked it together, and +12300 worked.
    '''
    d = 86400
    p,q,r = map(int, s.split("-"))
    z=(jul(p,q,r)*d+12300)%2551443  # 2551443 is about the number of seconds in a lunar month
    div, mod = divmod(z, 637861)    # 637861 seconds is about a quarter of a lunar month
                                    # div is what part of the lunar month this is (0 - 3)
                                    # mod is seconds since the start of the main phase
    return 2*div + (86400 <= mod)   # 2*div for the main phase, and
                                    # is mod >= the number seconds in a day?
                                    # (+0 if within a day of the main phase, +1 otherwise)

```
> 3 votes

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


title: Know a sequence by its subsequences

text:
# Question
Title: Know a sequence by its subsequences
## Introduction

Suppose you and your friend are playing a game. Your friend thinks of some particular sequence of `n` bits, and your task is to deduce the sequence by asking them questions. However, the only type of question you're allowed to ask is "How long is the longest common subsequence of your sequence and `S`", where `S` is any sequence of bits. The fewer questions you need, the better.

## The task

Your task is to write a program or function that takes as input a positive integer `n`, and a binary sequence `R` of length `n`. The sequence may be an array of integers, a string, or some other reasonable type of your choice. Your program shall output the sequence `R`.

Your program is **not** allowed to access the sequence `R` directly. The **only** thing it's allowed to do to `R` is to give it as input to the function `len_lcs` along with another binary sequence `S`. The function `len_lcs(R, S)` returns the length of the longest common subsequence of `R` and `S`. This means the longest sequence of bits which occurs as a (not necessarily contiguous) subsequence in both `R` and `S`. The inputs of `len_lcs` which may be of different lengths. The program should call this function on `R` and other sequences some number of times, and then reconstruct the sequence `R` based on that information.

## Example

Consider the inputs `n = 4` and `R = "1010"`. First, we might evaluate `len_lcs(R, "110")`, which gives `3`, since `"110"` is the longest common subsequence of `"1010"` and `"110"`. Then we know that `R` is obtained from `"110"` by inserting one bit at some position. Next, we might try `len_lcs(R, "0110")`, which returns `3` since the longest common subsequences are `"110"` and `"010"`, so `"0110"` is not correct. Then we try `len_lcs(R, "1010")`, which returns `4`. Now we know that `R == "1010"`, so we can return that sequence as the correct output. This required 3 calls to `len_lcs`.

## Rules and scoring

In this repository, you'll find a file called `subsequence_data.txt` containing 100 random binary sequences of lengths between 75 and 124. They were generated by taking three random floats between 0 and 1, taking their average as `a`, and then flipping an `a`-biased coin `n` times. You score is the **average number of calls to `len_lcs`** on these sequences, lower score being better. Your submission should record the number of calls. There are no time limits, except that you should run your program on the file before submitting it.

Your submission shall be deterministic. PRNGs are permitted, but they must use today's date, `200116` (or closest equivalent), as the random seed. You are not allowed to optimize your submission against these particular test cases. If I suspect this is happening, I will generate a new batch.

This is not code golf, so you're encouraged to write readable code. Rosetta Code has a page on the longest common subsequence; you may use that to implement `len_lcs` in your language of choice.

# Answer
# Java, ~~99.04~~ ~~98.46~~ 97.66 lcs() calls

### How it works

Exaple: Our line that is to be reconstructed is `00101`. First we find out how many zeros there are, by comparing (here comparing = computing lcs with the original string) by a zeros only string `00000`. Then we go through each position, flip the `0` to a `1` and check if we now have a longer common substring. If yes, accept and go to next position, if no, flip the current `1` back to a `0` and go to next position:

```
For our example of "00101" we get following steps:
input  lcs  prev.'best'
00000  3    0           //number of zeros
̲10000  3    3           //reject
0̲1000  3    3           //reject
00̲100  4    3           //accept
001̲10  4    4           //reject
0010̲1  5    4           //accept

```

### Optimizations

This is just a "naive" implementation, perhaps it would be possible to find a more sophisticated alogrithm checking multiple positions at once. But I am not sure if there really *is* a better one (e.g. based on the calculation of parity bits similar to the Hamming code), as you can always just evaluate the *length* of the common substring.

For one given line of digits, this algorithm needs exactly `#ofDigitsUntilTheLastOccurenceOf1 + 1` checks. (Substract one if the last digits is an `1`.)

EDIT: One small optimization: If we just checked the 2nd last digit and we still need to insert a `1`, we know for sure that it must be in the very last position, and can omit the corresponding check.

EDIT2: I just noticed you can apply above idea to the last `k` ones.

It might of course be possible to achieve a slightly lower score with the this optimization, by reordering the all lines first, because it could be, that you get more lines with ones at the very end but that would obviously be and optimization for the current test cases which is no longer funny.

### Runtime

The upper limit is `O(#NumberOfBits)`.

### Full code

Here the full code:

```
package jcodegolf;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

// http://codegolf.stackexchange.com/questions/69799/know-a-sequence-by-its-subsequences

public class SequenceReconstructor {
    public static int counter = 0;
    public static int lcs(String a, String b) { //stolen from http://rosettacode.org/wiki/Longest_common_subsequence#Java
        int[][] lengths = new int[a.length()+1][b.length()+1];

        // row 0 and column 0 are initialized to 0 already

        for (int i = 0; i < a.length(); i++)
            for (int j = 0; j < b.length(); j++)
                if (a.charAt(i) == b.charAt(j))
                    lengths[i+1][j+1] = lengths[i][j] + 1;
                else
                    lengths[i+1][j+1] =
                        Math.max(lengths[i+1][j], lengths[i][j+1]);

        // read the substring out from the matrix
        StringBuffer sb = new StringBuffer();
        for (int x = a.length(), y = b.length();
             x != 0 && y != 0; ) {
            if (lengths[x][y] == lengths[x-1][y])
                x--;
            else if (lengths[x][y] == lengths[x][y-1])
                y--;
            else {
                assert a.charAt(x-1) == b.charAt(y-1);
                sb.append(a.charAt(x-1));
                x--;
                y--;
            }
        }

        counter ++;
        return sb.reverse().toString().length();
    }

    public static String reconstruct(String secretLine, int lineLength){
        int current_lcs = 0;
        int previous_lcs = 0;
        char [] myGuess = new char[lineLength];
        for (int k=0; k<lineLength; k++){
            myGuess[k] = '0';
        }

        //find the number of zeros:
        int numberOfZeros = lcs(secretLine, String.valueOf(myGuess));
        current_lcs = numberOfZeros;
        previous_lcs = numberOfZeros;

        if(current_lcs == lineLength){ //were done
            return String.valueOf(myGuess);
        }

        int numberOfOnes = lineLength - numberOfZeros;
        //try to greedily insert ones at the positions where they maximize the common substring length
        int onesCounter = 0;
        for(int n=0; n < lineLength && onesCounter < numberOfOnes; n++){

            myGuess[n] = '1';
            current_lcs = lcs(secretLine, String.valueOf(myGuess));

            if(current_lcs > previous_lcs){ //accept

                previous_lcs = current_lcs;
                onesCounter ++;

            } else { // do not accept
                myGuess[n]='0';
            }

            if(n == lineLength-(numberOfOnes-onesCounter)-1 && onesCounter < numberOfOnes){ //lets test if we have as many locations left as we have ones to insert
                                                                // then we know that the rest are ones
                for(int k=n+1;k<lineLength;k++){
                    myGuess[k] = '1';
                }
                break;
            }

        }

        return String.valueOf(myGuess);
    }

    public static void main(String[] args) {
        try {

            //read the file
            BufferedReader br;

            br = new BufferedReader(new FileReader("PATH/TO/YOUR/FILE/LOCATION/subsequence_data.txt"));

            String line;

            //iterate over each line
            while ( (line = br.readLine()) != null){

                String r = reconstruct(line, line.length());
                System.out.println(line);     //print original line
                System.out.println(r);        //print current line
                System.out.println(counter/100.0);  //print current number of calls
                if (! line.equals(r)){
                    System.out.println("SOMETHING WENT HORRIBLY WRONG!!!");
                    System.exit(1);
                }

            }

        } catch(Exception e){
            e.printStackTrace();;
        }

    }

}

```
> 10 votes

---
Tags: subsequence, fewest-operations
---


title: Bézout's Identity

text:
# Question
Title: Bézout's Identity
## Introduction to Bézout's identity

The GCD of two integers A, B is the largest positive integer that divides both of them leaving no remainder. Now because of Euclid's property that each integer N can be divided by another integer M as follows:

there exist pairs u,v such that we can write:

Since there is an infinite amount of those pairs, we'd like to find special ones. There are in fact exactly (A,B not being zero) two such pairs that satify

---

e.g.

---

## Challenge

The goal of this challenge is to find the (ordered) pair of coefficients (u,v) that satify the above constraints and where u must be positive. This narrows down the output to a unique pair.

---

## Input

We may assume that the input is positive, also A will always be larger than B (A \> B).

---

## Output

The output of our program/function must be the (ordered) pair specified in the challenge.

---

## Rules

One must not use built-in extended Euclidean algorithms (e.g. in Mathematica one is allowed to use `GCD` but not `ExtendedGCD` \- which would fail for 5,3 anyways).

The answer may be a full program (taking input via STDIN or similar and output via STDOUT) or a function (returning the pair).

Beside the pair (u,v) there shall not be any output, trailing newlines or spaces are allowed. (brackets or commas are fine)

This is code golf, all standard loopholes are forbidden and the program with the lowest byte count wins.

---

## Examples

```
(A, B) -> (u, v)
(42, 12) -> (1, -3)
(4096, 84) -> (4, -195)
(5, 3) -> (2, -3)
(1155, 405) -> (20, -57)
(37377, 5204) -> (4365, -31351)
(7792, 7743) -> (7585, -7633)
(38884, 2737) -> (1707, -24251)
(6839, 746) -> (561, -5143)
(41908, 7228) -> (1104, -6401)
(27998, 6461) -> (3, -13)
(23780, 177) -> (20, -2687)
(11235813, 112358) -> (8643, -864301)

```

# Answer
# MATL, 37 ~~40~~ bytes

```
ZdXK2Gw/:1G*1GK/t_w2$:XI2G*!+K=2#fIb)

```

Uses release (9.3.1), which is earlier than this challenge.

This is a brute force approach, so it may not work for large inputs.

**Try it online!** The online compiler is based on a newer release, but produces the same results.

### Explanation

```
Zd            % implicitly input A and B. Compute their GCD. Call that C
XK            % copy C to clipboard K
2Gw/:         % vector [1, 2, ..., B/C]
1G*           % multiply that vector by A
1GK/t_w2$:    % vector [-A/C, -A/C+1 ..., A/C]
XI            % copy to clipboard I
2G*           % multiply that vector by B
!+            % all pairwise sums of elements from those vectors
K=2#f         % find row and column indices of sum that equals C
Ib)           % index second vector with column (indexing first vector with
              % row is not needed, because that vector is of the form [1, 2, ...])

```
> 1 votes

# Answer
## Haskell, 51 bytes

```
a#b=[(u,-v)|v<-[1..],u<-[1..v],gcd a b==u*a-v*b]!!0

```

Usage example: `27998 # 6461` -\> `(3,-13)`.

This is a brute force approach which finds all combinations of `u` and `v` that are valid solutions ordered by `u` and picks the first one. This takes some time to run for large `|v|`.
> 7 votes

# Answer
# Python 3, ~~101~~ 106 bytes

**Edit:** Added some improvements and corrections suggested by Bruce\_Forte.

An answer that uses the extended Euclidean algorithm. It's a bit clunky in places though, and I hope to golf it some more. I could convert to Python 2 to save a byte on integer division (`//`) but I'm not sure how Python 2's `%` modulus operator works with a negative second argument, as that is crucial for getting the output right.

```
def e(a,b):
 r=b;x=a;s=z=0;t=y=1
 while r:q=x/r;x,r=r,x%r;y,s=s,y-q*s;z,t=t,z-q*t
 return y%(b/x),z%(-a/x)

```

Ungolfed:

```
def e(a, b):
    r = b
    x = a    # becomes gcd(a, b)
    s = 0
    y = 1    # the coefficient of a
    t = 1
    z = 0    # the coefficient of b
    while r:
        q = x / r
        x, r = r, x % r
        y, s = s, y - q * s
        z, t = t, z - q * t
    return y % (b / x), z % (-a / x) # modulus in this way so that y is positive and z is negative

```
> 3 votes

# Answer
# Ruby, 83 bytes

I think there are a few ways to fine-tune and golf this solution, but I like it so far. Maybe I'll try an extended Euclidean algorithm solution next.

```
->x,y{a=b=0;y.downto(0).map{|u|(-x..0).map{|v|a,b=u,v if u*x+v*y==x.gcd(y)}};p a,b}

```

**How it works**

This code starts with a loop of `u` from `y` down to 0, with an inner loop of `v` from `-x` to 0, inside which we check every `u` and `v` if `u*x+v*y == gcd(x, y)`. Since there could be multiple matches along the way (this uses a very exhaustive search), we start far from 0 so that when we get the last of the multiple matches, it's the one where `|u|` and `|v|` are closest to 0.

```
def bezout(x,y)
  a=b=0
  y.downto(0).each do |u|
    (-x..0).each do |v|
      if u*x + v*y == x.gcd(y)
        a,b=u,v
      end
    end
  end
  p a,b
end

```
> 1 votes

# Answer
# Mathematica, 80 bytes

```
f@l_:=Mod@@NestWhile[{Last@#,{1,-Quotient@@(#.l)}.#}&,{{1,0},{0,1}},Last@#.l>0&]

```

---

**Explanation**:

Extended Euclidean algorithm is used here, in a `Nest` style. The method that the coefficients are stored in arrays makes it possible to use `Dot`.

Another possible representation is simply using symbolic expression, like `u a - v b` with `{a->19, b->17}`. Such representation makes use of the feature of Mathematica and is interesting, but it is much longer in bytes.

---

**Test cases**:

```
f[{5, 3}]              (* {2, -3} *)
f[{42, 12}]            (* {1, -3} *)
f[{11235813, 112358}]  (* {8643, -864301} *)

```
> 1 votes

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


title: Decipher the mathematical symbols

text:
# Question
Title: Decipher the mathematical symbols
*If you've read the book* Contact *by Carl Sagan, this challenge may seem familiar to you.*

---

Given an input of a set of mathematical equations consisting of a number, an unknown operator, another number, and a result, deduce which operators represent addition, subtraction, multiplication, or division.

Each input equation will always consist of

* a non-negative integer
* one of the letters `A`, `B`, `C`, or `D`
* another non-negative integer
* the character `=`
* a final non-negative integer

concatenated together. For example, a possible input is `1A2=3`, from which you can deduce that `A` represents addition. Each of the integers will satisfy `0 ≤ x ≤ 1,000`.

However, it's not always as simple as that. It is possible for there to be ambiguity between:

* `5A0=5`: addition/subtraction
* `1A1=1`: multiplication/division
* `0A5=0`: multiplication/division
* `2A2=4`: addition/multiplication
* `4A2=2`: subtraction/division
* `0A0=0`: addition/subtraction/multiplication

and so on. The challenge is to use this ability to narrow down choices, combined with process of elimination, to figure out what operator each letter represents. (There will always be at least one input equation, and it will always be possible to unambiguously, uniquely match each letter used in the input with a single operator.)

For example, let's say the input is the following equations:

* `0A0=0`: this narrows A down to addition, subtraction, or multiplication (can't divide by 0).
* `10B0=10`: B has to be either addition or subtraction.
* `5C5=10`: C is obviously addition, which makes B subtraction, which makes A multiplication.

Therefore, the output for these input equations should match `A` with `*`, `B` with `-`, and `C` with `+`.

Input may be given as either a single whitespace-/comma-delimited string or an array of strings, each representing one equation. Output may be either a single string (`"A*B-C+"`), an array (`["A*", "B-", "C+"]`), or a dictionary / dict-like 2D array (`{"A": "*", ...}` or `[["A", "*"], ...]`).

You may assume that a number will never be divided by another number it isn't divisible by (so, you don't need to worry about whether division should be floating point or truncated).

Since this is , the shortest code in bytes wins.

Test cases:

```
In                       Out
-------------------------------
0A0=0 10B0=10 5C5=10     A*B-C+
100D100=10000            D*
4A2=2 4B2=2 0A0=0        A-B/
15A0=15 4B2=2 2C2=0      A+B/C-
1A1=1 0A0=0              A*
0A0=0 2A2=4 5B0=5 2B2=4  A*B+
2A2=4 0C0=0 5B0=5 5A0=5  A+B-C*
0A1000=0 4A2=2           A/

```

# Answer
> 9 votes
# MATL, 53 bytes

```
j61tthYX'+-*/'X{Y@!"t'ABCD'!XKX{@YXU?K@Y}hwxKGm1L3$).

```

Uses current version (10.1.0)

*EDIT (June 12, 2016): to adapt to changes in the language, replace `Y}` by `g` and `1L3$)` by `Y)`. The link below incorporates those modifications*

**Try it online!**

### Explanation

This tests all possible permutations of the four operators in a loop until one permutation makes all equations true.

To test if equations are true, a regex is applied to replace the four letters by the operators (in the order dictated by the current permutation), and the string is converted to numbers (evaluated). This gives an array with as many numbers as equations, in which equations that are true become `1` and equations that are false become `0`. If this vector only contains `1` values, we're done.

The solution found assigns operators to the four letters, but not all of them necessarily appear in the input. So a final test is done to discard not used letters (and their matching operators).

```
j            % input data string
61           % '=' (ASCII)
tth          % duplicate twice and concat: '==' (ASCII)
YX           % regexprep to change '=' into '==' in input string
'+-*/'       % push string
X{           % transform into cell array {'+','-','*','/'}
Y@!          % all permutations, each in a column
"            % "for" loop. Iterate columns (that is, permutations)
  t          %   duplicate data string containing '=='
  'ABCD'!XK  %   create column array ['A';'B';'C';'D'] and copy to clipboard K
  X{         %   transform into column cell array {'A';'B';'C';'D'}
  @          %   push column cell array with current permutation of operator symbols
  YX         %   regexprep. Replaces 'A',...,'D' with current permutation of operators
  U          %   convert to numbers, i.e. evaluate string
  ?          %   if all numbers are 1 (truthy result): found it! But before breaking...
    K        %     push column array ['A';'B';'C';'D']
    @Y}      %     push column array with current permutation of operator symbols
    h        %     concatenate horizontally into 4x2 char array
    wx       %     delete original input so it won't be displayed
    K        %     push ['A';'B';'C';'D']
    G        %     push input string
    m        %     logical index that tells which of 'A',...,'D' were in input string
    1L3$)    %     apply that index to select rows of the 4x2 char array
    .        %     we can now break "for" loop
             %   implicitly end "if"
             % implicitly end "for"
             % implicitly display stack contents

```

# Answer
> 6 votes
# Python, 278 characters

My first answer on code golf...

It is just a function implementing a brute force algorithm, you call it passing as argument the string of equations.

```
from itertools import *
def f(s):
    l=list("ABCD")
    for p in permutations("+-*/"):
        t=s
        for v,w in zip(l+["="," "],list(p)+["=="," and "]):
            t=t.replace(v, w)
        try:
            o=""
            if eval(t):
                for c,r in zip(l,p):
                    if c in s:
                        o+=c+r
                return o
        except:
            pass

```

# Answer
> 4 votes
# JavaScript (ES6), ~~213~~ 208 bytes

```
f=(l,s="+-*/",p="",r)=>s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

```

## Explanation

Input and output are strings.

Defines a function `f` which doubles as a recursive function for generating all the permutations of the operators and tests complete permutations with the input equations using `eval`.

```
f=(
  l,                          // l = input expression string
  s="+-*/",                   // s = remaining operators
  p="",                       // p = current permutation of operators
  r                           // r is here so it is defined locally
)=>
  s?                          // if there are remaining operators
    [...s].map(o=>            // add each operator o
      r=f(
        l,
        s[g="replace"](o,""), // remove it from the list of remaining operators
        p+o                   // add it to the permutation
      )
        ||r                   // r = the output of any permutation (if it has output)
    )
    &&r                       // return r
  :                           // else if there are no remaining operators
    l.split` `.every(x=>      // for each expression
      (q=x.split`=`)          // q = [ equation, result ]
      [1]==eval(              // if the results is equal to the eval result

        // Replace each letter with the current permutation
        q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])
      )
    )

    // If all results matched, add permutation symbols to present characters and return
    &&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")

```

## Test

Test does not use default arguments for browser compatibility.

```
var solution = f=(l,s,p,r)=>s==null&&(s="+-*/",p="",0)?0:s?[...s].map(o=>r=f(l,s[g="replace"](o,""),p+o)||r)&&r:l.split` `.every(x=>(q=x.split`=`)[1]==eval(q[0][g](/[A-D]/g,m=>p[(a="ABCD").search(m)])))&&a[g](/./g,(c,i)=>l.match(c)?c+p[i]:"")
```

```
<input type="text" id="input" value="2A2=4 0C0=0 5B0=5 5A0=5" />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```

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


title: Display 2d array as ASCII table

text:
# Question
Title: Display 2d array as ASCII table
The task is to display ascii table for a given array.

### Input

The input is an 2D matrix. The matrix's row length is same with the length of an array. Alternatively, you can take input of an 2D matrix with the first row is a header. The outer dimension is the row.

Example Input:

```
[["License","2008-05-08","2009-03-11","2011-11-22","2013-08-12","2015-11-19"],["GPLv2","58.69%","52.2%","42.5%","33%","23%"],["GPLv3","1.64%","4.15%","6.5%","12%","9%"],["LGPL 2.1","11.39%","9.84%","?","6%","5%"],["LGPL 3.0","? (<0.64%)","0.37%","?","3%","2%"],["GPL family together","71.72% (+ <0.64%)","66.56%","?","54%","39%"]]

```

### Output

The output of a table looks like below.

```
+---------------------+-------------------+------------+------------+------------+------------+
| License             | 2008-05-08        | 2009-03-11 | 2011-11-22 | 2013-08-12 | 2015-11-19 |
+---------------------+-------------------+------------+------------+------------+------------+
| GPLv2               | 58.69%            | 52.2%      | 42.5%      | 33%        | 23%        |
| GPLv3               | 1.64%             | 4.15%      | 6.5%       | 12%        | 9%         |
| LGPL 2.1            | 11.39%            | 9.84%      | ?          | 6%         | 5%         |
| LGPL 3.0            | ? (<0.64%)        | 0.37%      | ?          | 3%         | 2%         |
| GPL family together | 71.72% (+ <0.64%) | 66.56%     | ?          | 54%        | 39%        |
+---------------------+-------------------+------------+------------+------------+------------+

```

Each cell has exactly one space on the left and at least one space on the right, padded until the bars aligned. However, at least one cell has only one space on its right.

### Test cases

```
Input:
[["Hello", "World", "!!!"],["aa", "bbbbbbbbb", "CcC"], ["Pyth",  "CJam", "GolfScript"]]

Output:
+-------+-----------+------------+
| Hello | World     | !!!        |
+-------+-----------+------------+
| aa    | bbbbbbbbb | CcC        |
| Pyth  | CJam      | GolfScript |
+-------+-----------+------------+

```

### Example submission

```
function ascii_table(array, header) {
    var lengths = array[0].map(function(_, i) {
        var col = array.map(function(row) {
            if (row[i] != undefined) {
                return row[i].length;
            } else {
                return 0;
            }
        });
        return Math.max.apply(Math, col);
    });
    array = array.map(function(row) {
        return '| ' + row.map(function(item, i) {
            var size = item.length;
            if (size < lengths[i]) {
                item += new Array(lengths[i]-size+1).join(' ');
            }
            return item;
        }).join(' | ') + ' |';
    });
    var sep = '+' + lengths.map(function(length) {
        return new Array(length+3).join('-');
    }).join('+') + '+';
    if (header) {
        return sep + '\n' + array[0] + '\n' + sep + '\n' +
            array.slice(1).join('\n') + '\n' + sep;
    } else {
        return sep + '\n' + array.join('\n') + '\n' + sep;
    }
}

```

This is , so the submission with the least amount of bytes wins!

# Answer
# CJam, 58 bytes

Anyone know trick of golfing in CJam?

```
q~z_{:,:e>)}%_{)'-*'++}%'+\+N+@@.{f{Se]"| "\+}}z'|N+f+1$f+

```
> 3 votes

# Answer
## vim, ~~139~~ ~~138~~ 134

```
$x0xqq%ls<cr><esc>@qq@q:se nosol|%s/,/\t/g|%s/]/\t./|%!column -t -s'<C-v><Tab>'<cr>qwf";;h<C-v>GI|<esc>@wq@wll<C-v>Gls|<esc>0<C-v>Gs| <esc>:%s/"//g<cr>Yp:s/[^|]/-/g|s/|/+/g<cr>YggpkP

```

Accepts input in the form shown in the test cases. May or may not be valid, as this relies on the input string never containing any `"`, `,`, `]`, or `|` characters.

If the input has to be able to contain `]`s, then `:%s/]/\t./<cr>` can be replaced with `qe$s<Tab>.<esc>j@eq@e` for 2 extra chars. There is no easy way to allow `",|` in the input.

Must be run in a Unix environment, as it relies on the `column` command line tool.

Slightly outdated explanation (by one revision, but that was just a bit of rearranging):

```
:se nosol<cr>    we need this later: G in visual block shouldn't go to BOL
$x0x             delete the surrounding pair of brackets
qq               record a macro
 %ls<cr><esc>    put each element of the big array on its own line
 @qq             recurse
@q               play back the macro until EOF
:%s/,/\t/g<cr>   replace all remaining commas with tabs
:%s/]/\t./<cr>   replace the ] at the end of lines with tabs and a dot
                 we need this for the line at the right edge of the table
:%!column -t     run the whole file through `column' on tabs
 -s'<C-v><Tab>
 '<cr>
qw               record another macro
 f";;            go forward 3 "s--that is, to the next "column"
 h               go back to the middle of the column
 <C-v>GI|<esc>   insert a line behind the cursor from top to bottom
 @wq             recurse
@w               play back until EOF
ll               move right before the line of dots we added earlier
<C-v>Gl          select the dots
s|<esc>          replace with a line (top to bottom)
0<C-v>G          select all the opening brackets
s| <esc>         again, (the leftmost) line
:%s/"//g<cr>     kill all the quotes around the data
Yp               duplicate bottom line
:s/[^|]/-/g<cr>  replace everything that's not a line with a dash
:s/|/+/g<cr>     now replace the lines with plus signs
YggpkP           put the separators before and after the first line

```

Thanks smpl for a byte!
> 9 votes

# Answer
# JavaScript (ES6), 210 ~~212 219~~

**Edit** 2 bytes saved thx @Neil

```
a=>(J=(m,j)=>j+m.join(j)+j,a.map(r=>r.map((c,i)=>s[i]>(l=c.length)?0:s[i]=l),s=[]),t=J(s.map(n=>'-'.repeat(n+2)),'+'),z=a.map(r=>J(r.map((c,i)=>' '+c+' '.repeat(s[i]+1-c.length)),'|')),z[0]+=`
`+t,t+J(z,`
`)+t)

```

**TEST**

```
F=a=>(
  J=(m,j)=>j+m.join(j)+j,
  a.map(r=>r.map((c,i)=>s[i]>(l=c.length)?0:s[i]=l),s=[]),
  t=J(s.map(n=>'-'.repeat(n+2)),'+'),
  z=a.map(r=>J(r.map((c,i)=>' '+c+' '.repeat(s[i]+1-c.length)),'|')),
  z[0]+='\n'+t,
  t+J(z,'\n')+t
)

Z=[["License","2008-05-08","2009-03-11","2011-11-22","2013-08-12","2015-11-19"],["GPLv2","58.69%","52.2%","42.5%","33%","23%"],["GPLv3","1.64%","4.15%","6.5%","12%","9%"],["LGPL 2.1","11.39%","9.84%","?","6%","5%"],["LGPL 3.0","? (<0.64%)","0.37%","?","3%","2%"],["GPL family together","71.72% (+ <0.64%)","66.56%","?","54%","39%"]]

O.textContent=F(Z)
```

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

# Answer
# Python 2, 190

This solution makes use of list comprehensions and generator expressions. It accepts a list of lists, and returns a string in the required format.

```
def b(i):
 d=[max(map(len,c))for c in zip(*i)]
 a='+'+''.join('-'*h+'--+'for h in d)
 e=['|'+''.join(' '+f.ljust(h)+' |'for h,f in zip(d,j))for j in i]
 return'\n'.join([a,e[0],a]+e[1:]+[a])

```

The code before the minifier:

```
def mktable(data):
    sizes = [max(map(len, column)) for column in zip(*data)]
    divider = '+' + ''.join('-'*size+'--+' for size in sizes)
    lines = ['|' + ''.join(
                ' ' + value.ljust(size) + ' |' for size, value in zip(sizes, row)
                )
                for row in data]
    return '\n'.join([divider, lines[0], divider] + lines[1:] + [divider])

data = [
    ["License","2008-05-08","2009-03-11","2011-11-22","2013-08-12","2015-11-19"],
    ["GPLv2","58.69%","52.2%","42.5%","33%","23%"],
    ["GPLv3","1.64%","4.15%","6.5%","12%","9%"],
    ["LGPL 2.1","11.39%","9.84%","?","6%","5%"],
    ["LGPL 3.0","? (<0.64%)","0.37%","?","3%","2%"],
    ["GPL family together","71.72% (+ <0.64%)","66.56%","?","54%","39%"]
    ]

table = mktable(data)
print table

```

which outputs:

```
+---------------------+-------------------+------------+------------+------------+------------+
| License             | 2008-05-08        | 2009-03-11 | 2011-11-22 | 2013-08-12 | 2015-11-19 |
+---------------------+-------------------+------------+------------+------------+------------+
| GPLv2               | 58.69%            | 52.2%      | 42.5%      | 33%        | 23%        |
| GPLv3               | 1.64%             | 4.15%      | 6.5%       | 12%        | 9%         |
| LGPL 2.1            | 11.39%            | 9.84%      | ?          | 6%         | 5%         |
| LGPL 3.0            | ? (<0.64%)        | 0.37%      | ?          | 3%         | 2%         |
| GPL family together | 71.72% (+ <0.64%) | 66.56%     | ?          | 54%        | 39%        |
+---------------------+-------------------+------------+------------+------------+------------+

```
> 2 votes

# Answer
# MATLAB, ~~244 239 229~~ 226

```
a=eval(regexprep(input(''),{'], *?[','[[',']]','"'},{';','{','}',''''}));s=size(a);c=repmat(' | ',s(1),1);b=c;for i=1:s(2)
x=char(a{:,i});b=[b x c];end
h=b(1,:);r=h*0+'-';r(h=='|')='+';b=[r;h;r;b(2:end,:);r];disp(b(:,2:end-1))

```

Explanation to follow.

---

Test case:

Input:

```
'[["License","2008-05-08","2009-03-11","2011-11-22","2013-08-12","2015-11-19"],["GPLv2","58.69%","52.2%","42.5%","33%","23%"],["GPLv3","1.64%","4.15%","6.5%","12%","9%"],["LGPL 2.1","11.39%","9.84%","?","6%","5%"],["LGPL 3.0","? (<0.64%)","0.37%","?","3%","2%"],["GPL family together","71.72% (+ <0.64%)","66.56%","?","54%","39%"]]'

```

Output:

```
+---------------------+-------------------+------------+------------+------------+------------+
| License             | 2008-05-08        | 2009-03-11 | 2011-11-22 | 2013-08-12 | 2015-11-19 |
+---------------------+-------------------+------------+------------+------------+------------+
| GPLv2               | 58.69%            | 52.2%      | 42.5%      | 33%        | 23%        |
| GPLv3               | 1.64%             | 4.15%      | 6.5%       | 12%        | 9%         |
| LGPL 2.1            | 11.39%            | 9.84%      | ?          | 6%         | 5%         |
| LGPL 3.0            | ? (<0.64%)        | 0.37%      | ?          | 3%         | 2%         |
| GPL family together | 71.72% (+ <0.64%) | 66.56%     | ?          | 54%        | 39%        |
+---------------------+-------------------+------------+------------+------------+------------+

```
> 1 votes

# Answer
# Ruby, ~~129~~ ~~126~~ ~~127~~ 126 characters

```
->a{t=?|
a.transpose.map{|c|t+=" %-#{c.map(&:size).max}s |"}
[d=(t%a[0].map{p}).tr('| ','+-'),a.map{|r|t%r}.insert(1,d),d]*$/}

```

Sample run:

```
2.1.5 :001 > puts ->a{t=?|;a.transpose.map{|c|t+=" %-#{c.map(&:size).max}s |"};[d=(t%a[0].map{p}).tr('| ','+-'),a.map{|r|t%r}.insert(1,d),d]*$/}[[["License","2008-05-08","2009-03-11","2011-11-22","2013-08-12","2015-11-19"],["GPLv2","58.69%","52.2%","42.5%","33%","23%"],["GPLv3","1.64%","4.15%","6.5%","12%","9%"],["LGPL 2.1","11.39%","9.84%","?","6%","5%"],["LGPL 3.0","? (<0.64%)","0.37%","?","3%","2%"],["GPL family together","71.72% (+ <0.64%)","66.56%","?","54%","39%"]]]
+---------------------+-------------------+------------+------------+------------+------------+
| License             | 2008-05-08        | 2009-03-11 | 2011-11-22 | 2013-08-12 | 2015-11-19 |
+---------------------+-------------------+------------+------------+------------+------------+
| GPLv2               | 58.69%            | 52.2%      | 42.5%      | 33%        | 23%        |
| GPLv3               | 1.64%             | 4.15%      | 6.5%       | 12%        | 9%         |
| LGPL 2.1            | 11.39%            | 9.84%      | ?          | 6%         | 5%         |
| LGPL 3.0            | ? (<0.64%)        | 0.37%      | ?          | 3%         | 2%         |
| GPL family together | 71.72% (+ <0.64%) | 66.56%     | ?          | 54%        | 39%        |
+---------------------+-------------------+------------+------------+------------+------------+

```
> 1 votes

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


title: Apples are falling down

text:
# Question
Title: Apples are falling down
# Introduction

There is an Apple tree trunk positioned between -2 to 2 on the x-axis, where some apples fall down around it:

```
        |   |
        |   |
<-------|---|------->
       -2   2

```

Everyday, *n* apples fall down. Each apple maintains its *x coordinate* as falls straight to the ground.

But if it lands on top of another apple, it will roll according to the following rules until it reaches the ground or a supporting layer of apples:

1. If the space at *x+1* at its current height is empty the current apple goes there.
2. Else if the space at *x-1* is empty the current apple goes there.
3. Otherwise the current apple stays where it is on top of that other apple.

# Challenge

The input will be the *n* starting positions of each apple in order. You can take it as an array or as separated numbers or in any other valid way, just make sure you explain it in your answer.

The output should be an ASCII drawing of the tree trunk and the apples around. You are *not required* to draw the x-axis to the left of the leftmost apple and to the right of the rightmost apple, but you do need to draw it anywhere it is beneath some apple. You can also extend the tree above the highest apple.

You can assume all *x-coordinates* are between -100 and 100, but not between -2 and 2.

This is .. The shortest answer in bytes wins!

# Examples

Input: `[-3, 5, 5, -4, -4, 5, -3]`

Output:

```
  a|   |
aaa|   | aaa
---|---|----

```

---

Input: `[3, 3, 3, 3, 8, 9]`

Output:

```
|   |a
|   |aaa  aa
|---|-------

```

---

Input: `[-5, -5, -5, -5, -5, -5, -5, -5, -5]`

Output:

```
  a  |   |
 aaa |   |
aaaaa|   |
-----|---|

```

# Answer
> 1 votes
## PHP, 230 bytes

I've added the first two newlines for readibility.

```
function($l){for($y=count($l);$y>=0;$f[]="$a|   |$a")$a=str_repeat($y--?$w=' ':'-',99);
foreach($l as$x){for($x+=101,$s=$y=0;!$s;$b[$x]!=$w?$b[$x+1]!=$w?$b[$x-1]!=$w?$s=1:--$x
:++$x:0)$b=$f[$y++];$f[$y-2][$x]=a;}echo join('
',$f);};

```

`Ideone`

Here is the ungolfed version:

```
function drawApples(array $listStartX)
{
    $field = [];
    $maximalHeight = count($listStartX);
    for ($y = $maximalHeight; $y >= 0; --$y)
    {
        $line = str_repeat($y > 0 ? ' ' : '-', 98);
        $field[] = $line .'|   |'. $line;
    }

    foreach ($listStartX as $x)
    {
        $x += 100;
        for ($y = 0; true; ++$y)
        {
            if ($field[$y][$x] === ' ') {
                continue;
            }

            if ($field[$y][$x + 1] === ' ') {
                ++$x;
                continue;
            }

            if ($field[$y][$x - 1] === ' ') {
                --$x;
                continue;
            }

            $field[$y - 1][$x] = 'a';
            break;
        }
    }

    echo implode("\n", $field);
}

```

# Answer
> 1 votes
# Python 2.7, 282 bytes

```
from collections import*;a=Counter();a[2]=-1;a[-2]=-1
for d in input():
 while 0<=a[d+1]<a[d]:d+=1
 while 0<=a[d-1]<a[d]:d-=1
 a[d]+=1
m=max(a.values())+1
print'\n'.join(''.join(' '*(m-a[i]-1)+'a'*a[i]+'-'if i**2!=4 else'|'*m for i in range(min(a),max(a)+1))[i::m]for i in range(m))

```

`Ideone`

Well… I tried.

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