title: The Will Rogers Phenomenon

text:
# Question
Title: The Will Rogers Phenomenon
The so-called Will Rogers phenomenon describes a way to tweak statistics by raising the average in two (multi)sets when one element is moved between the two sets. As a simple example, consider the two sets

```
A = {1, 2, 3}
B = {4, 5, 6}

```

Their arithmetic means are `2` and `5`, respectively. If we move the `4` to `A`:

```
A = {1, 2, 3, 4}
B = {5, 6}

```

Now the averages are `2.5` and `5.5`, respectively, so both averages have been raised through a simple regrouping.

As another example, consider

```
A = {3, 4, 5, 6} --> A = {3, 5, 6}
B = {2, 3, 4, 5} --> B = {2, 3, 4, 4, 5}

```

On the other hand, it's not possible to raise both averages for the sets

```
A = {1, 5, 9}
B = {4, 5, 7, 8}

```

## The Challenge

Given two lists of non-negative integers, determine whether it is possible to raise both averages by moving a single integer from one list to the other.

The average of an empty list is not defined, so if one of the lists contains only one element, this element cannot be moved.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be taken in any convenient string or list format.

You must not assume that the elements in each list are unique, nor that they are sorted. You may assume that both lists contain at least one element.

Output should be truthy if both averages can be raised by moving a single integer and falsy otherwise.

This is code golf, so the shortest answer (in bytes) wins.

## Test Cases

Truthy:

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

```

Falsy:

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

```

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

To make sure that 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 of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
<script>site = 'meta.codegolf'; postID = 5314; isAnswer = true; QUESTION_ID = 53913</script><script src='https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js'></script><script>jQuery(function(){var u='https://api.stackexchange.com/2.2/';if(isAnswer)u+='answers/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJeRCD';else u+='questions/'+postID+'?order=asc&sort=creation&site='+site+'&filter=!GeEyUcJFJO6t)';jQuery.get(u,function(b){function d(s){return jQuery('<textarea>').html(s).text()};function r(l){return new RegExp('<pre class="snippet-code-'+l+'\\b[^>]*><code>([\\s\\S]*?)</code></pre>')};b=b.items[0].body;var j=r('js').exec(b),c=r('css').exec(b),h=r('html').exec(b);if(c!==null)jQuery('head').append(jQuery('<style>').text(d(c[1])));if (h!==null)jQuery('body').append(d(h[1]));if(j!==null)jQuery('body').append(jQuery('<script>').text(d(j[1])))})})</script>
```

# Answer
> 11 votes
# Pyth, ~~29~~ ~~28~~ ~~26~~ 24 bytes

*Thanks to @Jakube for saving me 3 bytes with `.p` and `L`.*

Very simple, checks if any elements in list 2 are greater than mean of list 1 and less than mean of list 2, then repeats with list 1 and list 2 switched.

```
Lcsblbff&>YyhT<YyeTeT.pQ

```

Prints an a non-empty list for truthy, and `[]` for falsey.

```
L                    Define y(b). Pyth has no builtin for mean
 c                   Float div
  sb                 Sum of b
  lb                 Length of b
f        .pQ         Filter all permutations of input
 f     eT            Filter the last element of the filter var
  &                  Logical and
   >Y                Inner filter var greater than
    y                Call the mean function we defined earlier
     hT              First element of outer filter var
   <Y                Inner filter var less than
    y                Mean of
     eT              Last element of outer filternvar

```

Try it online here.

Test Suite.

# Answer
> 7 votes
# Haskell, ~~58~~ 57

```
x%y=any(\n->(\g->g x<0&&g y>0)$sum.map(n-))x
x?y=x%y||y%x

```

we can check if we enlarge or lower the average by checking whether the element to remove or include is bigger or smaller than the average.

we can check that by checking if the average is smaller or bigger than an element by removing that element from the array, and checking whether the new array's average is negative or positive, which in turn is just as checking whether the sum is positive or negative.

checking that is put very simply as `sum.map(-n+)`.

# Answer
> 7 votes
## Python 3, 74

```
lambda*L:any(sum(C)/len(C)>x>sum(D)/len(D)for(C,D)in[L,L[::-1]]for x in C)

```

Takes two lists as input. Checks if the first list has an element that's bigger than it's average but smaller than the other one's. Then, does the same for the two inputs swapped. Having a two-layer list comprehension was shorter than defining a separate function to try the two orders (82):

```
f=lambda A,B:any(sum(A)/len(A)>x>sum(B)/len(B)for x in A)
lambda A,B:f(A,B)|f(B,A)

```

# Answer
> 6 votes
# Mathematica, ~~49~~ 47 bytes

```
m=Mean;MemberQ[#2,x_/;m@#<x<m@#2]&@@#~SortBy~m&

```

Evaluates to a pure function that expects input in the form `{list1, list2}`.

# Answer
> 4 votes
# APL, ~~45~~ 40 bytes

Saved 5 bytes thanks to Moris Zucca!

```
{U←∊⍺⍵[⊃⍒M←(+/÷≢)¨⍺⍵]⋄1∊(U<⌈/M)∧(U>⌊/M)}

```

This creates an unnamed dyadic function that accepts arrays on the left and right and returns 1 or 0.

```
{
  M←(+/÷≢)¨⍺⍵          ⍝ Compute the mean of each array
  U←∊⍺⍵[⊃⍒M]           ⍝ Get the array with the larger mean
  1∊(U<⌈/M)∧(U>⌊/M)    ⍝ Any smaller mean < U < larger mean
}

```

You can try it online.

# Answer
> 3 votes
# R, ~~66~~ 52 Bytes

As an unnamed function, that accepts 2 vectors. Got rid of some spurious whichs.

```
function(a,b)any(a<(m=mean)(a)&a>m(b),b<m(b)&b>m(a))

```

Tests

```
> f=
+ function(a,b)any(a<(m=mean)(a)&a>m(b),b<m(b)&b>m(a))
> f(c(1), c(2, 3))
[1] TRUE
> f(c(1, 2, 3), c(4, 5, 6))
[1] TRUE
> f(c(3, 4, 5, 6), c(2, 3, 4, 5))
[1] TRUE
> f(c(6, 5, 9, 5, 6, 0), c(6, 2, 0, 9, 5, 2))
[1] TRUE
> f(c(0, 4), c(9, 1, 0, 2, 8, 0, 5, 5, 4, 9))
[1] TRUE
>
> f(c(1), c(2))
[1] FALSE
> f(c(2, 4), c(5))
[1] FALSE
> f(c(1, 5), c(2, 3, 4, 5))
[1] FALSE
> f(c(2, 1, 2, 3, 1, 3), c(5, 1, 6))
[1] FALSE
> f(c(4, 4, 5, 2, 4, 0), c(9, 2, 10, 1, 9, 0))
[1] FALSE
>

```

# Answer
> 3 votes
## SAS/IML, 67

```
start m(a,b);return((a>b[:]&&a<a[:])||(b>a[:]&&b<b[:]))[<>];finish;

```

It uses subscript reduction operators to get the answer, returning 0 if no element is found that matches the requirements or 1 if one is found.

Non-golfed, here I return the actual value itself using matrix multiplication:

```
proc iml;
  b={1 2 3 4 5 6 7 8 9 };
  a={2 3 4 5 6};
  start m(a,b);
  return (a#(a>b[:] && a < a[:]) || b#(b>a[:] && b < b[:]))[<>];
  finish;

  z= m(a,b);
  print z;
quit;

```

Tests:

```
%macro test(a,b,n);
  z&n=m({&a},{&b});
  print z&n;
%mend test;

proc iml;
  b={1 2 3 4 5 };
  a={2 3 4 5 6 7};
start m(a,b);return((a>b[:]&&a<a[:])||(b>a[:]&&b<b[:]))[<>];finish;

* True;
 %test(1,2 3,1);
 %test(1 2 3,4 5 6,2);
 %test(3 4 5 6, 2 3 4 5,3);
 %test(6 5 9 5 6 0,6 2 0 9 5 2,4);
 %test(0 4, 9 1 0 2 8 0 5 5 4 9,5);
* False;
 %test(1,2,6);
 %test(2 4, 5,7);
 %test(1 5, 2 3 4 5,8);
 %test(2 1 2 3 1 3, 5 1 6,9);
 %test(4 4 5 2 4 0, 9 2 10 1 9 0,10);

quit;

```

(Condensed for readability)

> z1 1
>
> z2 1
>
> z3 1
>
> z4 1
>
> z5 1
>
> z6 0
>
> z7 0
>
> z8 0
>
> z9 0
>
> z10 0

# Answer
> 2 votes
# Python 2.7, ~~102~~ ~~98~~ 96

```
lambda p:any([1for i in 0,1for e in p[i]if g[i^1]<e<g[i]]for g in[[sum(l)*1./len(l)for l in p]])

```

Takes the input as array of the 2 inputs and returns boolean.
The logic is -find the avg of the 2 lists, then find an element such that it's less than the avg of its own list and but greater than the average of the other list.

Testing it for the given inputs is demo-ed here

# Answer
> 2 votes
# CJam, 28 bytes

```
{{_:+1$,d/\+}%$~(m],@0=i)>&}

```

This is an anonymous function that pops a two-dimensional array from the stack and leaves an array of movable elements in return.

In supported browsers, you can verify all test cases at once in the CJam interpreter.

### Test cases

**Code**

```
q~]{{_:+1$,d/\+}%$~(m],@0=i)>&}%:p

```

**Input**

```
[[1] [2 3]]
[[1 2 3] [4 5 6]]
[[3 4 5 6] [2 3 4 5]]
[[6 5 9 5 6 0] [6 2 0 9 5 2]]
[[0 4] [9 1 0 2 8 0 5 5 4 9]]
[[1] [2]]
[[2 4] [5]]
[[1 5] [2 3 4 5]]
[[2 1 2 3 1 3] [5 1 6]]
[[4 4 5 2 4 0] [9 2 10 1 9 0]]

```

**Output**

```
[2]
[4]
[4]
[5]
[4]
""
""
""
""
""

```

### How it works

If A and B are the arrays and **avg(A) ≤ avg(B)** we simply check if **B ∩ {⌊avg(A)⌋+1, …, ⌈avg(B)⌉-1}** is non-empty. Any element in this intersection could be moved from **B** to **A** to increase both averages.

```
{          }%              e# For each of the arrays:
 _:+                       e#   Compute the sum of its elements.
    1$,                    e#   Compute its length.
       d/                  e#   Cast to Double and perform division.
         \+                e#   Prepend the computed average to the array.
             $             e# Sort the arrays (by the averages).
              ~            e# Dump both arrays on the stack.
               (           e# Shift out the higher average.
                m]         e# Round up to the nearest integer b.
                  ,        e# Push [0 ... b-1].
                   @0=     e# Replace the array with lower average by its average.
                      i)   e# Round down to the nearest integer a and add 1.
                        >  e# Skip the first a integer of the range.
                           e# This pushes [a+1 ... b-1].
                         & e# Intersect the result with the remaining array.

```

This pushes the array of all elements of the array with higher average that can be moved to increase both averages. This array is empty/falsy if and only if no elements can be moved to achieve this result.

# Answer
> 1 votes
# Ruby, 86

```
A=->x{x.reduce(0.0,:+)/x.size}
F=->q{b,a=q.sort_by{|x|A[x]};a.any?{|x|x<A[a]&&x>A[b]}}

```

Takes as input an array containing the two arrays.

Tries to find a sub average item from the group with the higher average that is greater than the average of the other group.

Test: http://ideone.com/444W4U

# Answer
> 1 votes
## Matlab, 54

Using an anonymous function:

```
f=@(A,B)any([B>mean(A)&B<mean(B) A>mean(B)&A<mean(A)])

```

Examples:

```
>> f=@(A,B)any([B>mean(A)&B<mean(B) A>mean(B)&A<mean(A)])
f =
    @(A,B)any([B>mean(A)&B<mean(B),A>mean(B)&A<mean(A)])

>> f([1 2 3],[4 5 6])
ans =
     1

>> f([3 4 5 6],[2 3 4 5])
ans =
     1

>> f([1 5 9],[4 5 7 8])
ans =
     0

```

# Answer
> 1 votes
## C#, 104

```
bool f(int[]a,int[]b){double i=a.Average(),j=b.Average();return a.Any(x=>x<i&&x>j)||b.Any(x=>x<j&&x>i);}

```

Example Calls:

```
f(new []{1,2,3}, new []{4,5,6})
f(new []{1}, new []{2, 3})
f(new []{1, 2, 3}, new []{4, 5, 6})
f(new []{3, 4, 5, 6}, new []{2, 3, 4, 5})
f(new []{6, 5, 9, 5, 6, 0}, new []{6, 2, 0, 9, 5, 2})
f(new []{0, 4}, new []{9, 1, 0, 2, 8, 0, 5, 5, 4, 9})

f(new []{1}, new []{2})
f(new []{2, 4}, new []{5})
f(new []{1, 5}, new []{2, 3, 4, 5})
f(new []{2, 1, 2, 3, 1, 3}, new []{5, 1, 6})
f(new []{4, 4, 5, 2, 4, 0}, new []{9, 2, 10, 1, 9, 0})

```

# Answer
> 0 votes
# C++14, 157 bytes

As unnamed lambda, returns by the last parameter `r`. Assumes `A`,`B` to be containers like `vector<int>` or `array<int,>`.

```
[](auto A,auto B,int&r){auto m=[](auto C){auto s=0.;for(auto x:C)s+=x;return s/C.size();};r=0;for(auto x:A)r+=x<m(A)&&x>m(B);for(auto x:B)r+=x<m(B)&&x>m(A);}

```

Ungolfed:

```
auto f=
[](auto A,auto B,int&r){
  auto m=[](auto C){
   auto s=0.;
   for(auto x:C) s+=x;
   return s/C.size();
  };
  r=0;
  for (auto x:A) r+=x<m(A)&&x>m(B);
  for (auto x:B) r+=x<m(B)&&x>m(A);
}
;

```

Usage:

```
int main() {
  std::vector<int>
    a={1,2,3}, b={4,5,6};
  //  a={1,5,9}, b={4,5,7,8};
  int r;
  f(a,b,r);
  std::cout << r << std::endl;
}

```

---
Tags: code-golf, math, array, decision-problem
---


title: Make your program sequential!

text:
# Question
Title: Make your program sequential!
Your task, if you choose to accept it, is simple.

# Objective

You must make a program that, when run, prints some (as many as you want) terms in a sequence that you choose. The sequence must be a valid OEIS sequence. The twist is that when you take the characters from your code that make up your sequence, string them together and run them *in the same language*, you should get the formula for the nth of your sequence for your sequence.

# Example

Let's say I made this program:

```
abcdefghij

```

and chose the sequence of squares: http://oeis.org/A000290

and I chose it to print the first 5 terms of the sequence, the output should be:

```
1, 4, 9, 16, 25

```

Note: the output is flexible, you can choose what delimiter you want separating the terms, but the delimiter should be noticeable so that each of the terms of the sequence can be differentiated.

Now, the character at index 1 is `a`. The character at index 4 is `d`. The character at index 9 is `i`. So my new program would be:

```
adi

```

and it would have to print the formula for the nth term for my sequence, which is:

```
n^2

```

Simple!

## Other things

* You must print a minimum of 5 terms.
* You may choose to 0- or 1-index.
* Repeated numbers means repeated characters.
* If your sequence isn't in order (e.g. it goes backwards), then your code still follows it (e.g. your code is written backwards).
* You must use and only use the numbers in bounds of your answer, even if it has already gone out of bounds. You cannot use numbers from the same sequence you did not print.
* If your sequence does not officially have a formula, you may use the first 3 letters of the name stated on the OEIS website (e.g. the fibonacci sequence would print `fib` and the lucas-lehmer sequence would print `luc`).

Remember, this is , so shortest answer, in bytes, wins!

# Answer
# 05AB1E, 10 bytes, A008585

This code outputs the first **11** elements of the sequence **3n**.

```
3TÝ' §n*»J

```

Try it online!

**Explanation**

```
3            # push 3
             # STACK: 3
 TÝ          # push range [0 ... 10]
             # STACK: 3, [0,1,2,3,4,5,6,7,8,9,10]
   ' §       # push a space char converted to string
             # STACK: 3, [0,1,2,3,4,5,6,7,8,9,10], " "
      n      # square the string
             # STACK: 3, [0,1,2,3,4,5,6,7,8,9,10]
       *     # multiply the top 2 elements of the stack
             # STACK: [0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30]
        »    # join by newlines
         J   # join to string

```

Taking every *nth* item (0-indexed) gives:

```
3'nJ

```

which outputs 3n
> 3 votes

# Answer
# Python 2, 35 Bytes

I decided to use the obvious sequence A000027, which essentially has the formula `n` ;) If you run the following code:

```
#print'n'
n=1
exec'print n;n+=1;'*8

```

You get the output:

```
1
2
3
4
5
6
7
8

```

And if you take the 8 characters from my source code (0-indexed), you get this:

```
print'n'

```

Which simply prints `n`.

---

If you were hoping for a more exciting answer, here's a Python 2 solution for `n^2`, i.e. A000290:

```
#p  r    i      n        t          '            n              ^                2                  '
n=1
exec'print n*n;n+=1;'*10

```
> 5 votes

# Answer
# 05AB1E, ~~7~~ 6 bytes, A000027

```
5L'n s

```

Try it online!

Explanation:

```
5L      # Push [1, 2, 3, 4, 5]
  'n    # Push "n"
        # Do nothing
     s  # Swap (only in original program)
        # Implicit print

```
> 4 votes

# Answer
# Octave, 64 bytes A000290

I went for the `n^2` one:

```
@()(1:5 ).^2 % '        n          ^            2              '

```

Take the terms 1, 4, 9, 16, 25, 36, 49 and 64 to get:

```
@()'n^2'

```

which prints:

```
n^2

```
> 3 votes

# Answer
# 05AB1E, ~~30~~ 28 bytes, A000290

This is the sequence of squares

```
"  n    ^      2        "5Ln

```

Outputs the first 5 terms of the sequence with the formula `n^2`:

```
[1, 4, 9, 16, 25]

```

Try it online!

This is 1-indexed. So taking the characters from the code that make up the sequence, I get

```
"n^2"

```

Which outputs

```
n^2

```

Try it online!

### Explanation

```
"  n    ^      2        "              # push this string
                         5             # push 5
                          L            # push range [1, ..., 5]
                            n          # square it
                                       # implicit output

```
> 2 votes

# Answer
# MATL, 8 bytes, A000027

*Thanks to Oliver for a correction interpreting the challenge*

```
'n'  5:&

```

The code prints `1 2 3 4 5`. Keeping only the first give chars it prints `n`.

Try it online!
> 1 votes

# Answer
# Octave, 49 bytes, A109234

```
@()  1      :      5     %'floor (n*sin h(1)) ';]

```

The sequence `floor(n*sinh(1))` are all numbers from `1` and up, except `6, 13, 20, 26, 33, 40, 46, _3, _0, _6 ...` So, the characters used to make `1 2 3 4 5` must be placed in those positions. The remaining positions are used for the string explaining the function.
> 1 votes

# Answer
# Wonder, 16 bytes A005843

```
 0";2"tk 5gen *2

```

This was once DASH, but has now been renamed to Wonder.

Outputs the first 6 even numbers. Note the leading space. Keeping the indices 0, 2, 4, 6, and 8 yields:

```
 "2t

```

Which prints `2t`.

# Explanation

```
0";2"

```

This is just a string and a number.

```
tk 5gen *2

```

This generates an infinite list of even numbers starting from 0, then takes the first 5 items from that list.
> 1 votes

# Answer
# 05AB1E, 15 bytes, A001477

```
"n-1"     žhSðý

```

Uses the **CP-1252** encoding. Try it online!
> 0 votes

# Answer
# Haystack, ~~21~~ ~~10~~ 9 Bytes

Haystack has had a lot of new features added in the past few days :) Of course, I am going to use A000027. Here's the inital program:

```
<"n"o|OR4

```

This will print out:

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

```

And if you take the characters 1-5, 0-indexed, you get:

```
"n"o|

```

Which prints `n`.

---

If you want to have some more fun, here's a solution for A000290:

```
^"_(n\D2l^
3keU02/:[W
D5m"5s\ih_
Cr:OF]uAIe
hWd>g|AkuH
/6R>ud*O,\
)G:q$n|4y{
:|v\X:?dP/

```

> If you want to see only the necessary chars, click here.

This will print the first 7 squares, and their corresponding chars in the above program, 0-indexed, are:

```
"n^2"O|

```

Which prints `n^2`.
> 0 votes

---
Tags: code-golf, sequence, source-layout
---


title: Efficient Typing on a Game Boy

text:
# Question
Title: Efficient Typing on a Game Boy
Many old **Game Boy** games often required string input from the user. However, there was no keyboard. This was handled by presenting the user with a "keyboard screen" like so:

The 'character pointer' would begin on letter A. The user would navigate to each desired character with the D-Pad's four buttons (`UP`, `DOWN`, `LEFT` and `RIGHT`), then press `BUTTON A` to append it to the final string.

*Please note:*

* ***The grid wraps around***, so pressing `UP` whilst on letter A would take you to T.
* The 'character pointer' stays put after appending a letter

# The Challenge

The above keyboard has options to change case and is an irregular shape. So, for simplicity, in this challenge we will use the following keyboard (the bottom right is ASCII char 32, a space):

```
A B C D E F G
H I J K L M N
O P Q R S T U
V W X Y Z .

```

Typing on keyboards like this is extremely slow - so, to make this easier, your task is to write a program which tells the user the ***fastest possible way*** to type a given string. If there are multiple fastest ways, you only need to show one.

The output key should be:

* `>` for `RIGHT`
* `<` for `LEFT`
* `^` for `UP`
* `v` for `DOWN`
* `.` for `BUTTON A` (append current letter to string)

For example, when given the string `DENNIS`, the solution would look like this:

```
>>>.>.>>v..>>.>>>v.

```

# Rules / Details

* Please remember, the grid wraps around!
* You may submit a full program or a function, as long as it takes the initial string and produces a solution string. Whitespace / trailing newlines are irrelevant as long as the output is correct.
* You can assume input will only consist of characters typable on the specified keyboard, but it may be empty.
* This is , so the shortest code wins. Standard code-golf loopholes apply.

# Test Cases

*There are usually multiple solutions of the same length. For each test case, I've included the optimum length, and an example. You don't need to print the length in your answer, just the solution.*

```
FLP.TKC  ->  25 steps:  <<.<v.<<<v.<<<v.^.<<^.<^.
MOYLEX   ->  23 steps:  <<v.>>v.>>>v.>^^.^.<<^.
FEERSUM  ->  18 steps:  <<.<..<vv.>.>>.<^.
MEGO     ->  14 steps:  <<v.<^.>>.>vv.

A CAT    ->  17 steps:  .<^.>>>v.<<.<<vv.
BOB      ->  10 steps:  >.<vv.>^^.

(space)  ->  3 steps:   <^.
(empty)  ->  0 steps:   (empty)

```

You can view my testcase generator on repl.it \- please notify me if there are any bugs.

Thank you everyone for the submissions! User ngn is currently the winner with 61 bytes, but if anyone can find a shorter solution, the little green tick can be moved ;)

# Answer
> 4 votes
# Dyalog APL, 61 bytes

`4 7∘{∊'.',⍨⍉↑b⍴¨¨'^v' '<>'⌷¨⍨⊂¨a>b←a⌊⍺-a←⍺|↓2-/0,⍺⊤⍵⍳⍨⎕a,'.'}`

assumes `⎕IO←0`

`⎕a,'.'` the alphabet followed by a full stop

`⍵⍳⍨` find the argument's chars there as indices 0..26 (`' '` and all others will be 27)

`⍺⊤` encode in base 7 (note the left arg  is bound to `4 7`), get a 2×n matrix

`0,` prepend zeros to the left

`2-/` differences between adjacent columns

split the matrix into a pair of vectors

`a←⍺|` take them modulo 4 and 7 respectively, assign to `a`

`b←a⌊⍺-a` make `b` the smaller of `a` and its modular inverse

`'^v' '<>'⌷¨⍨⊂¨a>b` choose `^` or `v` for the first vector and `<` or `>` for the second, based on where `a` differs from `b`

`b⍴¨¨` repeat each of those `b` times

`⍉↑` mix the two vectors into a single matrix and transpose it, get an n×2 matrix

`'.',⍨` append `.`-s on the right

flatten

# Answer
> 6 votes
## JavaScript (ES6), 147 bytes

```
s=>s.replace(/./g,c=>(q=p,p="AHOVBIPWCJQXDKRYELSZFMY.GNU ".indexOf(c),"<<<>>>".substring(3,((p>>2)+10-(q>>2))%7)+["","v","vv","^"][p-q&3]+"."),p=0)

```

An interesting behaviour of `substring` is that it exchanges the arguments if the second is less than the first. This means that if I calculate the optimal number of left/right presses as a number between -3 and 3, I can add 3, and take the substring of `<<<>>>` starting at 3 and I will get the correct number of arrows. Meanwhile the down/up presses are simply handled by looking up an array using a bitwise and of the difference in rows with 3; this way is slightly shorter as there are fewer array elements.

# Answer
> 4 votes
# Ruby, 107 bytes

```
->s{c=0
s.tr(". ","[\\").bytes{|b|b-=65
print ["","^","^^","v"][c/7-b/7],(d=(c-c=b)%7)>3??>*(7-d):?<*d,?.}}

```

**Ungolfed in test program**

```
f=->s{                                 #Input in s.
  c=0                                  #Set current position of pointer to 0.
  s.tr(". ","[\\").                    #Change . and space to the characters after Z [\
  bytes{|b|                            #For each byte b,
    b-=65                              #subtract 65 so A->0 B->1 etc.
    print ["","^","^^","v"][c/7-b/7],  #Print the necessary string to move vertically.
    (d=(c-c=b)%7)>3?                   #Calculate the horizontal difference c-b (mod 7) and set c to b ready for next byte.
       ?>*(7-d):?<*d,                  #If d>3 print an appropriate number of >, else an appropriate number of <.
    ?.                                 #Print . to finish the processing of this byte.
  }
}

#call like this and print a newline after each testcase
f["FLP.TKC"];puts
f["MOYLEX"];puts
f["FEERSUM"];puts
f["MEGO"];puts
f["A CAT"];puts
f["BOB"];puts

```

# Answer
> 1 votes
## Python 2, 298 bytes

This is longer than it should be, but...

```
def l(c):i="ABCDEFGHIJKLMNOPQRSTUVWXYZ. ".index(c);return[i%7,i/7]
def d(f,t,a=abs):
 v,h=l(t)[1]-l(f)[1],l(t)[0]-l(f)[0]
 if a(h)>3:h=h-7*h/a(h)
 if a(v)>2:v=v-4*v/a(v)
 return'^v'[v>0]*a(v)+'<>'[h>0]*a(h)
s="A"+input()
print''.join([d(p[0],p[1])+'.'for p in[s[n:n+2]for n in range(len(s))][:-1]])

```

Any help would be greatly appreciated!

Takes input in quotation marks.

`l` returns the location of a character in the keyboard.

The two `if` statements in the middle of `d` are for checking if it would be optimal to 'wrap' around the keyboard.

The input, `s` has `"A"` prepended to it because the initial position of the cursor is `A`.

We loop through the string in pairs, discarding the last one (which is not a pair: `[:-1]`), finding the minimum distance between the two halves of the pair.

Thanks to Flp.Tkc for telling me that I can do `a=abs` instead of saying `abs` every time!

# Answer
> 1 votes
**Mathematica, 193 bytes**

**Golf**

```
StringJoin@@(StringTake[">>><<<",Mod[#〚2〛,7,-3]]<>StringTake["vv^",Mod[#〚1〛,4,-1]]<>"."&/@Differences[FirstPosition[Partition[ToUpperCase@Alphabet[]~Join~{"."," "},7],#]&/@Characters["A"<>#]])&

```

**Readable**

```
In[1]:= characters = ToUpperCase@Alphabet[]~Join~{".", " "}

Out[1]= {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", ".", " "}

In[2]:= keyboard = Partition[characters, 7]

Out[2]= {{"A", "B", "C", "D", "E", "F", "G"}, {"H", "I", "J", "K", "L", "M", "N"}, {"O", "P", "Q", "R", "S", "T", "U"}, {"V", "W", "X", "Y", "Z", ".", " "}}

In[3]:= characterPosition[char_] := FirstPosition[keyboard, char]

In[4]:= xToString[x_] := StringTake[">>><<<", Mod[x, 7, -3]]

In[5]:= yToString[y_] := StringTake["vv^", Mod[y, 4, -1]]

In[6]:= xyToString[{y_, x_}] := xToString[x] <> yToString[y] <> "."

In[7]:= instructionsList[input_] := xyToString /@ Differences[characterPosition /@ Characters["A" <> input]]

In[8]:= instructions[input_] := StringJoin @@ instructionsList[input]

In[9]:= instructions["DENNIS"]

Out[9]= ">>>.>.>>v..>>.>>>v."

```

# Answer
> 0 votes
# Java 8, 1045 bytes

## Golf

```
staticchar[][]a={{'A','B','C','D','E','F','G'},{'H','I','J','K','L','M','N'},{'O','P','Q','R','S','T','U'},{'V','W','X','Y','Z','.',''}};staticintm=Integer.MAX_VALUE;staticStringn="";staticboolean[][]c(boolean[][]a){boolean[][]r=newboolean[4][];for(inti=0;i<4;i)r[i]=a[i].clone();returnr;}staticvoidg(inti,intj,boolean[][]v,chard,Stringp){v[i][j]=true;if(a[i][j]==d&&p.length()<m){m=p.length();n=p;}if(i-1<0){if(!v[3][j])g(3,j,c(v),d,p"^");}elseif(!v[i-1][j])g(i-1,j,c(v),d,p"^");if(i1>3){if(!v[0][j])g(0,j,c(v),d,p"v");}elseif(!v[i1][j])g(i1,j,c(v),d,p"v");if(j-1<0){if(!v[i][6])g(i,6,c(v),d,p"<");}elseif(!v[i][j-1])g(i,j-1,c(v),d,p"<");if(j1>6){if(!v[i][0])g(i,0,c(v),d,p">");}elseif(!v[i][j1])g(i,j1,c(v),d,p">");}publicstaticvoidmain(String[]args){boolean[][]v=newboolean[4][7];Scannerx=newScanner(System.in);Strings=x.next();Stringpath="";intp=0;intq=0;for(inti=0;i<s.length();i){chart=s.charAt(i);g(p,q,c(v),t,"");path=n".";n="";m=Integer.MAX_VALUE;for(intj=0;j<4;j){for(intk=0;k<7;k){if(a[j][k]==t){p=j;q=k;}}}}System.out.println(path);}

```

## Readable

```
static char[][] a = {
        {'A','B','C','D','E','F','G'},
        {'H','I','J','K','L','M','N'},
        {'O','P','Q','R','S','T','U'},
        {'V','W','X','Y','Z','.',' '}
};
static int m = Integer.MAX_VALUE;
static String n="";

static boolean[][] c(boolean[][] a){
    boolean [][] r = new boolean[4][];
    for(int i = 0; i < 4; i++)
        r[i] = a[i].clone();
    return r;
}

static void g(int i, int j,boolean[][] v,char d,String p) {

    v[i][j] = true;
    if (a[i][j]==d && p.length()<m){
        m=p.length();
        n=p;
    }

    if (i-1<0) {
        if(!v[3][j])
            g(3, j, c(v), d, p + "^");
    }
    else if (!v[i-1][j])
        g(i-1, j, c(v), d, p + "^");

    if (i+1>3) {
        if(!v[0][j])
            g(0, j, c(v), d, p + "v");
    }
    else if(!v[i+1][j])
        g(i+1, j, c(v), d, p + "v");

    if (j-1<0) {
        if(!v[i][6])
            g(i, 6, c(v), d, p + "<");
    }
    else if (!v[i][j-1])
        g(i, j-1, c(v), d, p + "<");

    if (j+1>6) {
        if (!v[i][0])
            g(i, 0, c(v), d, p + ">");
    }
    else if (!v[i][j+1])
        g(i, j+1, c(v), d, p + ">");

}

public static void main(String[] args) {
    boolean[][] v = new boolean[4][7];
    Scanner x = new Scanner(System.in);
    String s = x.next();
    String path="";
    int p=0;
    int q=0;
    for(int i=0;i<s.length();i++){
        char t=s.charAt(i);
        g(p,q,c(v),t,"");
        path+=n+".";
        n="";
        m=Integer.MAX_VALUE;
        for(int j=0;j<4;j++){
            for(int k=0;k<7;k++){
                if(a[j][k]==t) {
                    p=j;
                    q=k;
                }
            }
        }

    }
    System.out.println(path);
}

```

## Explanation

The solution is a direct approach: poorly optimized brute force. The method `g(...)` is a basic depth first search going through each permutation (up, down, left, right). With some slight modifications in ordering for the test cases I get the output:

```
<<.v<.v<<<.v<<<.^.^<<.^<.
v<<.v>>.v>>>.^^>.^.^<<.
<<.<..^^<.>.>>.^<.
v<<.^<.>>.^^>.
.^<.v>>>.<<.^^<<.
>.^^<.^^>.
^<.
// new line for the last

```

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


title: Golf the Pigeonhole sort

text:
# Question
Title: Golf the Pigeonhole sort
Implement the Pigeonhole sort. This is a variant of the Bucket sort, and its logic is very simple: index your items (by a given function) and then return all non-empty indexes' items.

Your program/function should get an array of items in the most comfortable way for your language of choice, (i.e. a parameter, stdin, etc.), and in any format you like (for example: JSON). It should return/output a sorted array.

Do not modify the given array.

The second parameter that will be given to your program/function will be the "sort-by function". For exmaple, in JavaScript it will be something like `function(item){return item.id;}`.

For simplicity, you can assume this function returns a **unique positive Integer** for each item in the given array.

Shortest code wins. Only ASCII is allowed.

# Answer
## J (39)

```
f=:1 :'y{~z i.g#~+/z=/g=.i.>:>./z=.u y'

```

Explanation:

* `z=.u y`: apply the function `u` to the argument `y`. The function should distribute over the array.
* `g=.i.>:>./z`: Make the 'holes' (in the range `[0..max(u(y))]`).
* `+/z=/g`: for each hole, get how many elements it contains.
* `g#~`: replicate each hole coordinate by how many elements it contains (so if holes 3 and 5 had 1 element, and hole 8 had 3, we get `3 5 8 8 8`).
* `z i.`: look up the position of each value in `z`. For example, if `u y` is 5 for the 3rd element of `y`, this gives `3` for `5`.
* `y{~z`: look up the matching elements in the starting array

Examples:

```
   f=:1 :'y{~z i.g#~+/z=/g=.i.>:>./z=.u y'

   NB. functions and data
   ascii=:a.&i.
   text=:'here is some text to sort'
   length=:#&>
   arrays=:1 2;3;4 5 6 7;8 9 10 NB. these will be sorted by length

   NB. show effect of functions
   ascii text
104 101 114 101 32 105 115 32 115 111 109 101 32 116 101 120 116 32 116 111 32 115 111 114 116
   length arrays
2 1 4 3

   NB. sort
   ascii f text
     eeeehimooorrsssttttx
   length f arrays
┌─┬───┬──────┬───────┐
│3│1 2│8 9 10│4 5 6 7│
└─┴───┴──────┴───────┘

```
> 1 votes

# Answer
# Ruby, 43

```
def s a,*b,&f
a.map{|x|b[f[x]]=x}
b-[p]
end

```

Calling looks like

```
p s(["a","ccc","bb","eeeee"],&:length)
  -> ["a", "bb", "ccc", "eeeee"]

```

Tricks: `*b` in the arg list creates an empty output array (so long as you don't, y'know, pass any args). `&f` creates a lambda reference to the passed-in block that can be called via `f[]` (normal Ruby convention is to use `yield`). `a.map` iterates over the input array without modifying it and is one character shorter than `a.each`. `b-[p]` strips out the nil values, equivalent to `b.compact`.
> 2 votes

# Answer
# Python 2 - 98 92 bytes

```
def p(l,f):
 x=[None]*max(map(f,l))
 for e in l:x[f(e)-1]=e
 return[i for i in x if i!=None]

```

`l` is the list to sort, `f` is the sort-by function.

Ungolfed (a bit):

```
def pigeonhole(list, sort_function):
    max_value = max(map(sort_function, list)) # Find how big the final list has to be
    sorted_list = [None] * max_value # Create a list of that many Nones

    for element in list:
        sorted_list[sort_function(element) - 1] = element # Subtract one because sort_function returns positive ints and lists are 0-indexed

    return [element for element in sorted_list if element is not None] # Filter out Nones and return

def return_same(x):
    return x # This sort function will make the pigeonhole sort ints normally. There's no reason it has to be this function, it just has to return positive ints.

print pigeonhole([8, 4, 5, 9, 11, 3], return_same) # [3, 4, 5, 8, 9, 11]

```
> 1 votes

# Answer
## Groovy - 135 chars

Using Groovy 2.2.1, inspired by undergroundmonorail's answer, though here input data and sort function are specified in files:

```
e={new GroovyShell().evaluate(new File(args[it]))}
l=e(0)
f=e(1)
s=new Object[l.max{f(it)}]
l.each{s[f(it)-1]=it}
println s.findAll{it}

```

As an assist to the reader, `l` = list of items (from file), `f` = sort function (from file), `s` = sorted list, and `e` = simple convenience function to evaluate data as code.

An example command-line looks like:

```
groovy P.groovy data.txt f.txt

```

where data.txt is:

```
[8,4,5,9,11,3]

```

and f.txt is:

```
{ x -> x }

```
> 0 votes

# Answer
# JavaScript - 92

I believe this is what is asked for.

```
function s(a,b){c=[];a.map(function(e){c[b(e)]=e});return c.filter(function(f){return !!f})}

```

Test:

```
console.log(s([{id:3},{id:5},{id:7},{id:1}],function(x){return x.id}));

```

returns:

```
[1: Object, 3: Object, 5: Object, 7: Object]
1: Object
id: 1
3: Object
id: 3
5: Object
id: 5
7: Object
id: 7

```

EDIT: fixed as per @Jacob's comments.
> 0 votes

# Answer
# C++14, 154 bytes

As unnamed lambda:

```
#include<map>
#include<vector>
[](auto&v,auto f){std::map<int,int>m;for(int c:v)m[f(c)]=c;std::vector<int>r;for(auto p:m)r.push_back(p.second);return r;}

```

Assumes `v` to be a container like `vector<int>`, could also be `int[]`

Ungolfed:

```
auto f =
[](auto&v, auto f){
  std::map<int,int> m;
  for(int c:v)
    m[f(c)]=c;
  std::vector<int> r;
  for(auto p:m)
    r.push_back(p.second);
  return r;
};

```

Usage:

```
int main() {
  std::vector<int> v={5,2,1,3,4};
  auto w = f(v, [](int x){return x;});
  for (auto c:w) std::cout << c << ", ";
  std::cout << "\n";
}

```
> 0 votes

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


title: That's one odd mountain!

text:
# Question
Title: That's one odd mountain!
Inspired by *Display a chain of little mountains with an odd number on the top of it!* by @sygmei.

Why have a chain of mountains when you can have one massive one?

Make a program that takes an input number and prints a mountain with every odd number up to the input number.

(Where "south west" means `directly below and to the left`, and "south east" means `directly below and to the right`)

Every number will have a `/` south west of it, and a `\` south east. It starts from `1` at the top, and the next number will go south west of a `/` or south east of a `\`. The next number will go in the line closest to the top and to the left most possible.

For a multidigit number, just the 1st digit needs to be in the right place with the other digits directly after, and only the first digit should have `\` and `/` coming out from it.

The mountain up to 1 or 2 is just:

```
 1
/ \

```

A mountain up to 3 or 4 is just:

```
   1
  / \
 3
/ \

```

For 25 or 26:

```
         1
        / \
       3   5
      / \ / \
     7   9   11
    / \ / \ / \
   13  15  17  19
  / \ / \ / \ / \
 21  23  25
/ \ / \ / \

```

Last two lines where the input is 121:

```
 111 113 115 117 119 121
/ \ / \ / \ / \ / \ / \

```

And the last two lines where the input is 1019:

```
 993 995 997 999 1001100310051007100910111013101510171019
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \

```

You may assume that the input will be greater than 0 and less than 10001 (exclusive).

Trailing spaces are OK, and extra leading spaces are alright as long as there is the same on all lines.

This is , so the shortest program in bytes wins.

An ungolfed answer to this can be found online here (In Python on repl.it) if you need more test cases.

# Answer
# 05AB1E, ~~54~~ ~~52~~ ~~47~~ 46 bytes

```
ÅÉ¹L£D€g__ÏRv"/ \ "yg×N·©úˆyvy4yg-ð×}J®>úˆ}¯R»

```

Try it online!

**Explanation**

```
                                                # implicit input n
ÅÉ                                              # push a list of uneven numbers up to input
  ¹L£                                           # divide into sublists of length 1,2,3...n
     D€g__Ï                                     # remove empty sublists
           R                                    # reverse list
            v                                   # for each sublist
             "/ \ "                             # push the string "/ \ "
                   yg×                          # repeat it len(sublist) times
                      N·©ú                      # prepend (sublist index)*2 spaces
                          ˆ                     # add to global list
                           yv                   # for each number in sublist
                             y4yg-ð×            # prepend spaces until length is 4
                                    }           # end inner loop
                                     J          # join to string
                                      ®>ú       # prepend (sublist index)*2+1 spaces
                                         ˆ      # add to global list
                                          }     # end outer loop
                                           ¯    # push global list
                                            R   # reverse it
                                             »  # join rows by space and columns by newline
                                                # implicitly print

```

I could have saved 5 bytes with `ÅÉ¹L£D€g__ÏRv"/ \ "yg×N·©úˆy4jJðÛ®>úˆ}¯R»` if only I'd pushed that bugfix for **j** I wrote several weeks ago **:/**
> 5 votes

# Answer
## Batch, 335 bytes

```
@echo off
set i=
set/ac=w=0
:l
set i=  %i%
set/aw+=2,c+=w
if %c% lss %1 goto l
set s=
set t=
set/ac=w=1
for /l %%a in (1,2,%1) do call:c %%a
echo  %s%
echo%t%
exit/b
:c
if not %c%==0 goto g
echo%i%%s%
set i=%i:~2%
echo%i%%t%
set s=
set t=
set/aw+=1,c=w
:g
set n=%1   (three trailing spaces)
set s=%s%%n:~0,4%
set t=%t% / \
set/ac-=1

```
> 3 votes

# Answer
## Python 2, ~~160~~ ~~149~~ 143 bytes

*Thanks TFeld for saving 11 bytes and Artyer for saving 6 bytes*

```
x=range(1,input()+1,2);y=[];i=1
while x:y+=[''.join('%-4d'%j for j in x[:i]),'/ \ '*len(x[:i])];x=x[i:];i+=1
while y:print' '*~-len(y)+y.pop(0)

```
> 3 votes

# Answer
## Perl, 134

**133 bytes + 1 for `-p` option**

```
 $l="/ \\ ";$t=" ";while($c++<$_) {$t.=sprintf'%-4d',$c++;$v.=$l;if ($i++>=$j){$t=~s/^/  /gm;$t.="
  $v
 ";$i=$v="";$j++}}$_="$t
$v";

```

Formatted version (original golfed version uses real "new lines" instead of \n)

```
$l="/ \\ ";
$t=" ";
while($c++<$_) {
   $t.=sprintf'%-4d',$c++;
   $v.=$l;
   if ($i++>=$j){
      $t=~s/^/  /gm;
      $t.="\n  $v\n ";
      $i=$v="";
      $j++
   }
}
$_="$t\n$v";

```
> 2 votes

# Answer
# Bash, 425 bytes

```
f() { k=0; o=""; l=1; for (( c=1; c<=$1; c++ )); do o="$o$c "; let c++ k++; if [ $l -eq $k ]; then o=$o"\n"; k=0; let l++; fi; done; s=$[$(echo -e $o | wc -l)*2-1]; p() { for c in $(seq $1); do echo -n " "; done }; IFS=$'\n'; for n in $(echo -e $o); do unset IFS; p $s; let s--; for w in $n; do echo -n "$w"; p $[4-${#w}]; done; echo; p $s; for c in $(seq $(echo $n|wc -w)); do echo -n "/ \ "; done; echo; let s-- j++; done }

```

Formatted:

```
l=1
k=0
o=""
for (( c=1; c<=$1; c++ ))
do
        o="$o$c "
        let c++ k++
        if [ $l -eq $k ]
        then
                o=$o"\n"
                k=0
                let l++
        fi
done
s=$[$(echo -e $o | wc -l)*2-1]
p() {
        for c in $(seq $1)
        do
                echo -n " "
        done
}
IFS=$'\n'
for n in $(echo -e $o)
do
        unset IFS
        p $s
        let s--
        for w in $n
        do
                echo -n "$w"
                p $[4-${#w}]
        done
        echo
        p $s
        for c in $(seq $(echo $n|wc -w))
                do echo -n "/ \ "
        done
        echo
        let s-- j++
done

```
> 2 votes

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


title: Inverse permutation index

text:
# Question
Title: Inverse permutation index
## Introduction

The lexicographical permutations of a list with *n* elements can be numbered from 0 to *n*! - 1. For example, the 3! = 6 permutations of `(1,2,3)` would be `(1,2,3)`, `(1,3,2)`, `(2,1,3)`, `(2,3,1)`, `(3,1,2)`, `(3,2,1)`.

When a permutation is applied to a list, its elements are ordered in the same order as the numbers in the permutation. For example, applying the permutation `(2,3,1)` to `l = (a,b,c)` yields `(l[2],l[3],l[1]) = (b,c,a)`.

The inverse of a permutation is defined as the permutation that reverses this operation, i.e. applying a permutation and then its inverse (or vice versa) does not modify the array. For example, the inverse of `(2,3,1)` is `(3,1,2)`, since applying that to `(b,c,a)` yields `(a,b,c)`.

Also, a permutation's inverse applied to the permutation itself yields the integers 1…*n*. For example, applying `(3,1,2)` to `(2,3,1)` yields `(1,2,3)`.

We now define the function *revind*(*x*) as the index of the inverse permutation of the permutation with index *x*. (This is A056019, if you're interested.)

Since a permutation with index *i* only modifies the last *k* items of the list iff 0 ≤ *i* \< *k*!, we can add any number of elements to the start of the list without affecting *revind*(*i*). Therefore the length of the list does not affect the result.

## Challenge

Your task is to implement *revind*(*x*). You will write a full program or function that takes a single nonnegative integer *x* as input/argument and outputs/returns the result as a single nonnegative integer.

The input and output may be 0-indexed or 1-indexed, but this must be consistent between them.

Builtins that generate permutations by index, return the index of a permutation or find the inverse permutation are banned. (Builtins that generate all permutations or the next permutation are allowed.)

Standard rules apply.

## Examples

The examples below are 0-indexed.

```
Input    Output
0        0
1        1
2        2
3        4
4        3
5        5
6        6
13       10
42       51
100      41
1000     3628
2000     3974
10000    30593
100000   303016

```

## Reference implementation (Python 3)

```
def revind(n):
    from math import factorial
    from itertools import permutations, count
    l = next(filter(lambda x: factorial(x) > n, count(1)))
    pms = list(permutations(range(l)))
    return [k for k in range(len(pms)) if tuple(pms[n][i] for i in pms[k]) == pms[0]][0]

```

# Answer
> 6 votes
# Jelly, 6 bytes

```
ịŒ!⁺iR

```

I/O uses 1-based indexing. *Very* slow and memory-hungry.

### Verification

As long as the input does not exceed **8! = 40320**, it is sufficient to consider all permutations of the array **\[1, …, 8\]**. For the last test case, the permutations of **\[1, …, 9\]** suffice.

With slightly modified code that only considers the permutations of the first **8** or **9** positive integers, you can Try it online! or verify all remaining test cases.

### How it works

```
ịŒ!⁺iR  Main link. Argument: n

 Œ!     Yield all permutations of [1, ..., n].
ị       At-index; retrieve the n-th permutation.
   ⁺    Duplicate the Œ! atom, generating all permutations of the n-th permutation.
     R  Range; yield [1, ..., n].
    i   Index; find the index of [1, ..., n] in the generated 2D array.

```

## Alternate approach, 6 bytes (invalid)

```
Œ!Ụ€Ụi

```

It's just as long and it uses the forbidden *grade up* atom , but it's (arguably) more idiomatic.

By prepending **8** (or **9** for the last test case), we can actually Try it online!

### How it works

```
Œ!Ụ€Ụi  Main link. Argument: n

Œ!      Yield all permutations of [1, ..., n].
  Ụ€    Grade up each; sort the indices of each permutation by the corresponding
        values. For a permutation of [1, ..., n], this inverts the permutation.
    Ụ   Grade up; sort [1, ..., n!] by the corresponding inverted permutations
        (lexicographical order).
     i  Index; yield the 1-based index of n, which corresponds to the inverse of
        the n-th permutation.

```

# Answer
> 6 votes
# Mathematica, 74 bytes

```
Max@k[i,Flatten@Outer[i=Permutations[j=Range@#];k=Position,{i[[#]]},j,1]]&

```

Uses 1-indexing. Very inefficient. (uses ~11GB of memory when the input is `11`)

# Explanation

```
j=Range@#

```

Generate a list from 1 to N. Store that in `j`.

```
i=Permutations[...]

```

Find all permutations of `j`. Store that in `i`.

```
k=Position

```

Store the `Position` function in `k`. (to reduce byte-count when using `Position` again)

```
Flatten@Outer[...,{i[[#]]},j,1]

```

Find the inverse permutation of the N-th permutation.

```
Max@k[i,...]

```

Find the `k` (`Position`) of the inverse permutation in `i` (all permutations)

# Using built-ins, ~~46~~ 43 bytes

```
a[(a=Ordering)/@Permutations@Range@#][[#]]&

```

1-indexed.

# Answer
> 6 votes
# 05AB1E, ~~14~~ 13 bytes

~~Very memory inefficient.~~ Now even more memory inefficient (but 1 byte shorter).
0-based range.
Uses CP-1252 encoding.

```
ƒ¹ÝœD¹èNkˆ}¯k

```

Try it online! or as a Modified test suite

**Explanation**

```
ƒ               # for N in range[0 .. x]
 ¹ÝœD           # generate 2 copies of all permutations of range[0 .. x]
     ¹è         # get permutation at index x
       Nkˆ      # store index of N in that permutation in global list
         }      # end loop
          ¯k    # get index of global list (inverse) in list of permutations

```

# Answer
> 5 votes
# MATL, 15 bytes

```
:Y@tGY)Z)G:=!Af

```

Input and output are 1-based.

Similar to @MartinEnder's CJam answer, but finds the inverse permutation by composing all possible permutations with that specified by the input, and seeing which has become the identity permutation.

It runs out of memory in the online compiler for input `10`.

Try it online!

### Explanation

```
:      % Implicitly input N. Push range [1 2 ... N]
Y@     % Matrix witll all permutations of size N. Each permutation is a row
tGY)   % Duplicate. Get the N-th row
Z)     % Use that as a column index into the matrix of all permutations
G:=    % Compare each row with [1 2 ... N]
!Af    % Find index of the row that matches. Implicitly display

```

# Answer
> 5 votes
# Pyth, 12 bytes

```
xJ.phQxL@JQh

```

Test suite

0 indexed.

Explanation:

```
xJ.phQxL@JQh
xJ.phQxL@JQhQ    Implicit variable introduction
                 Q = eval(input())
  .phQ           Form all permutations of range(Q+1), namely [0, 1, .. Q]
 J               Save to J.
        @JQ      Take the Qth element of J.
      xL   hQ    Map all elements of [0, 1, ..., Q] to their index in above
x                Find the index in J of the above.

```

# Answer
> 4 votes
## CJam, 16 bytes

```
ri_)e!_@=_$\f#a#

```

Indices are 0-based.

Try it online!

I doesn't get a lot more inefficient than this... runs out of memory with Java's default settings for inputs greater than `8` (but works in principle for arbitrary inputs given a sufficient number of universes of time and memory).

### Explanation

```
ri    e# Read input and convert to integer N.
_)e!  e# Duplicate N, get all permutations of [0 1 ... N].
_@=   e# Duplicate permutations, get the Nth permutation.
_$    e# Duplicate and sort to get the sorted range [0 1 ... N].
\f#   e# For each of these values, get its index in the Nth permutation.
      e# This inverts the permutation.
a#    e# Find the index of this new permutation in the list of all permutations.

```

# Answer
> 3 votes
## GAP, 108 bytes

```
h:=l->n->PositionProperty(l,p->l[n]*p=());
f:=n->h(Set(SymmetricGroup(First([1..n],k->Factorial(k)>=n))))(n);

```

1-indexed. Newlines not counted, they are not needed. I don't really have to assign the final function to a name, but ...

`h` is a curried function taking a list of permutations and an index into that list and returning the index of the inverse permuation. Without restrictions, I'd just do `Position(l,l[n]^-1)`. `f` calls that function with the sorted permutations of a big enough symmetric group and the given `n`.

I could just write `SymmetricGroup(n)`, then the function could be computed for values up to 9. Since there are already much smaller solutions, I prefer to be able to do this:

```
gap> f(100001);
303017

```

A really efficient 0-indexed solution that works for arguments below 99! (and can be made to work for arguments below 999! at the cost of one byte) is this one:

```
f:=function(n)
 local m,l,p,i,g;
 m:=First([1..99],k->Factorial(k)>n);
 g:=List([m-1,m-2..0],Factorial);
 l:=[1..m];
 p:=[];
 for i in g do
  Add(p,Remove(l,QuoInt(n,i)+1));
  n:=n mod i;
 od;
 return Sum(ListN(List([1..m],i->Number([1..Position(p,i)],j->p[j]>i)),g,\*));
end;

```

After deleting whitespace, this has 255 bytes.

# Answer
> 3 votes
# J, ~~55~~ 50 bytes

```
g=:/:~i.@#
[:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]

```

Based on the J essay on Permutation Index.

This code only requires memory on the order of `n` but uses more time since it sorts the list `n` times and searches it `n` times for each index.

Using the builtin `/:` which is able to find the grade of a list and the inverse of a permutation, there is a 42 byte solution that is more efficient.

```
[:(#\.#.+/@(<{.)\.)@/:(-i.)@>:/:@/:@,/@#:]

```

This version only requires 44 seconds to compute the last test case when compared against the other which requires 105 seconds.

## Usage

```
   g =: /:~i.@#
   f =: [:(#\.#.+/@(<{.)\.)@g(-i.)@>:g@g@,/@#:]
   (,.f"0) 0 1 2 3 4 5 6 13 42 100 1000 2000 10000
    0     0
    1     1
    2     2
    3     4
    4     3
    5     5
    6     6
   13    10
   42    51
  100    41
 1000  3628
 2000  3974
10000 30593
   timex 'r =: f 100000'
105.787
   r
303016

```

# Answer
> 3 votes
## JavaScript (ES6), ~~163~~ ~~120~~ 110 bytes

```
f=(n,a=[],i=0,r=0,[j,...b]=a)=>n?a.splice(n%-~i,0,i)|f(n/++i|0,a,i):i?f(n,b,i-1,b.reduce((r,k)=>r+=k>j,r*i)):r
```

```
<input type=number min=0 oninput=o.textContent=f(+this.value)><pre id=o>
```

0-indexed. Works by converting the index to a permutation, inverting it, then converting back to an index. Edit: Saved about 25% by making `f` invert and reverse the permutation, then making `g` convert the reversed permutation back to an index. Saved a further 10 bytes by combining the two recursive calls into a single function. Ungolfed:

```
function index(n) {
    var a = [0];
    for (var i = 1; n = Math.floor(n / i); i++) {
        var j = i - n % (i + 1);
        for (var k = 0; k < i; k++) {
            if (a[k] > j) a[k]++;
        }
        a.push(j);
    }
    a = [...a.keys()].map(k => a.indexOf(k));
    while (i) {
        n *= i--;
        j = a.pop();
        for (k = 0; k < i; k++) {
            if (a[k] > j) n++;
        }
    }
    return n;
}

```

# Answer
> 3 votes
# Jelly, ~~14 13~~ 9 bytes

-4 bytes thanks to @Dennis (which he golfed further using the quick  in his answer)

```
Œ!ịịŒ!$iR

```

Another very slow implementation.
1-based indexing employed here, so expected results are:

```
input:  1 2 3 4 5 6 7 8  9 10 11
output: 1 2 3 5 4 6 7 8 13 19  9

```

No point in even putting up an online IDE link, as TIO kills at an input of `10`. Local results (last is very slow and required a tonne of memory!):

```
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 1
1
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 2
2
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 3
3
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 4
5
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 5
4
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 6
6
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 7
7
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 8
8
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 9
13
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 10
19
C:\Jelly\jelly-master>python jelly -fu D:\jelly_scripts\revPerm.txt 11
9

```

### How?

```
Œ!ịịŒ!$iR - Main link 1: n
      $   - last two links as a monad
    Œ!    -     permutations of implicit range [1,2,3,...,n]
   ị      -     value at index n (the nth permutation)
Œ!        - permutations of implicit range [1,2,3,...,n]
  ị       - value at index (the indexes of the permuted values in the nth permutation)
       i  - index of
        R - range [1,2,3,...,n]

```

Note: no need to sort the permutations as we are using the same ordering for both finding the permutation and and it's inverse.

# Answer
> 2 votes
# Python 2, ~~116~~ 114 bytes

```
from itertools import*
def f(n):r=range(n+1);l=list(permutations(r));print l.index(tuple(l[n].index(v)for v in r))

```

**repl.it**

0-based. Slow and memory hungry but short on bytes.

---

### Using no permutation functions; both memory and time efficient. ~~289~~ 285 bytes

-4 bytes thanks to @Christian Sievers (full permutation already formed)

```
h=lambda n,v=1,x=1:v and(n>=v and h(n,v*x,x+1)or(v,x-1))or n and h(n-1,0,n*x)or x
i=lambda p,j=0,r=0:j<len(p)and i(p,j+1,r+sum(k<p[j]for k in p[j+1:])*h(len(p)-j-1,0))or r
def f(n):t,x=h(n);g=range(x);o=g[:];r=[];exec"t/=x;x-=1;r+=[o.pop(n/t)];n%=t;"*x;return i([r.index(v)for v in g])

```

I know it's code golf but I think @Pietu1998 is interested in efficient implementations also.

See it in action at **repl.it**

While this uses more bytes than the reference implementation comparing for `n=5000000`:

```
ref:    6GB 148s
this: 200KB <1ms

```

`f` is the reverse index function.

`f` first gets the next factorial above `n`, `t`, and the integer whose factorial that is, `x` by calling `h(n)`, and sets `g=range(x)`, the items that will make up the permutation, `o=g[:]`, and the permutation holder, `r=[]`

Next it constructs the permutation at index `n` by `pop`ing the indexes of the factorial base representation of `n` in turn from the items, `o`, and appending them to `r`. The factorial base representation is found by div and mod of `n` with `t` where `t` is div'd by `x` and `x` decrements down to `1`.

Finally it finds the index of the reverse permutation by calling `i` with the reverse permutation, `[r.index(v)for v in g]`

`h` is a dual-purpose function for either calculating a factorial of a non-negative integer or calculating both the next factorial above a non-negative integer and the integer that makes that factorial.

In it's default state `v=1` and it does the latter by multiplying `v` by `x` (also initially `1`) and incrementing `x` until `n` is at least as big, then it returns `v` and `x-1` in a tuple.

To calculate `n!` one calls `h(n,0)` which multiples `x` (initially `1`) by `n` and decrements `n` until `n` is `0` when it returns `x`.

`i` provides the lexicographical index of a permutation, `p`, of the items `[0,1,...n]` by adding up the products of the factorial of the factorial base of each index, `h(len(p)-j-1,0)`, and how many items to the right of the index are less than the value at that index, `sum(k<p[j]for k in p[j+1:])`.

# Answer
> 1 votes
# Python 2, ~~130~~ 129 bytes

```
p=lambda x,k,j=1:x[j:]and p(x,k/j,j+1)+[x.pop(k%j)]
n=input();r=range(n+2);k=0
while[p(r*1,n)[i]for i in p(r*1,k)]>r:k+=1
print k

```

# Answer
> 1 votes
# Actually, ~~18~~ 11 bytes

This answer uses the algorithm in Dennis' Jelly answer but is 0-indexed. Golfing suggestions welcome! Try it online!

```
4╞r;)╨E╨♂#í

```

**Ungolfing**

```
      Implicit input n.
4╞    Push 4 duplicates of n. Stack: n, n, n, n
r;)   Push the range [0...n], and move a duplicate of that range to BOS for later.
╨E    Push the n-length permutations of [0...n] and get perm_list[n].
        Stack: perm_list[n], n, [0...n]
╨     Push the n-length permutations of perm_list[n].
♂#    Convert every "list" in the zip to an actual list.
        Stack: perm(perm_list[n]), [0...n]
í     Get the index of [0...n] in the list of permutations of perm_list[n].
      Implicit return.

```

---
Tags: code-golf, combinatorics, permutations
---


# Question
Title: Hexagonal coordinates: Polar to Cartesian
Wikipedia says about Polar Coordinates:

> In mathematics, the polar coordinate system is a two-dimensional coordinate system in which each point on a plane is determined by a distance from a reference point and an angle from a reference direction.

This seems perfect for describing hexagonal grids. Take the following hexagonal grid for example:

```
  A B C
 D E F G
H I J K L
 M N O P
  Q R S

```

Our reference point will be the center of the hexagon ('J'), and our reference angle will be to the top left corner of the hexagon ('A'). However, we'll describe the angle in terms of the number of *clockwise steps* around the outside of the hexagon from this point, not in angles. So we'll call it "Step number" instead of angle.

For example, 'C' is at (2, 2) because it has a radius of 2 (since it is two rings away from the center, 'J'), and an step number of 2 (2 clockwise steps forward from 'A'). Similarly, 'O' is at (1, 3), because it is one ring away from the center, and three clockwise steps forward from 'E' (which is on the reference angle).

For completeness, 'J' is at (0, 0), since you need 0 steps out and 0 steps clockwise to reach it.

Now, you can also describe a hexagonal with Cartesian Coordinates, but because of the offset this is a little weird. Just like with our polar coordinates, we will put the center at (0, 0). Each space takes up a coordinate also, so 'K' is at (2, 0), not (1, 0). This would put 'A' at (-2, 2), and 'O' at (1, -1).

# The challenge

Given polar hexagonal coordinates, output the same coordinates in Cartesian coordinates. You may take these coords, and the output the answer in any reasonable format. This means that you may reverse the order of the inputs if you like. This also means you could output the coords as (Y, X), but if you do, please mention this in your answer to avoid confusion.

You do not have to handle negative radii, but you may get negative angles, or angles that go more than a full revolution around the hexagon. For example, you may receive (1, 10), or (1, -2) as input. These would both correspond to 'N' in our previous hexagon. You do *not* have to handle non-integers for input.

# Sample IO

```
#Polar      #Cartesian
(0, 0)      (0, 0)
(1, 2)      (2, 0)
(6, 0)      (-6, 6)
(2, -3)     (-3, -1)
(4, 23),    (-5, 3)
(5, -3),    (-8, 2)
(10, 50),   (-20, 0)
(6, 10),    (10, 2)
(8, 28),    (0, -8)
(8, -20),   (0, -8)

```

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

```
(r,d)=>[...Array(d+r*6)].map((_,i)=>x+="431013"[y+="122100"[i=i/r%6|0]-1,i]-2,x=y=-r)&&[x,-y]

```

Test snippet:

```
f=(r,d)=>[...Array(d+r*6)].map((_,i)=>x+="431013"[y+="122100"[i=i/r%6|0]-1,i]-2,x=y=-r)&&[x,-y]

g=([r,d],e)=>console.log(`f(${r},${d}):`, `[${f(r,d)}]`, "expected:", `[${e}]`)

g([0,0],[0,0])
g([1,2],[2,0])
g([6,0],[-6,6])
g([2,-3],[-3,-1])
g([4,23],[-5,3])
g([5,-3],[-8,2])
g([10,50],[-20,0])
g([6,10],[10,2])
g([8,28],[0,-8])
g([8,-20],[0,-8])
```

# Answer
> 1 votes
## JavaScript (ES6), 95 bytes

```
f=(r,t,x=-r,y=r,d=2,e=0)=>t<0?f(r,t+r*6):t>r?g(r,t-r,x+r*d,y+r*e,d+e*3>>1,e-d>>1):[x+t*d,y+t*e]

```

Explanation: The solution for a zero angle is simply `-r,r`, so we start at that point. If the angle is negative, we add on a whole hexagon and call ourselves recursively, otherwise we start walking around the hexagon with a `d,e=2,0` step. Where possible, we leap `r` such steps, then rotating the step using the formula `d+e*3>>1,e-d>>1` to progress to the next side. Finally we take any remaining steps to reach our destination.

---
Tags: code-golf, math, geometry, hexagonal-grid
---


title: Generate a cipher

text:
# Question
Title: Generate a cipher
Generate a cipher given a number and string

Your task is simple. Given a string `s` and a number `0 <= n <= 9` as inputs, insert a pseudo-random printable ASCII character between each character of the string `n` times. Such that for each character of `s` there are `n` random characters between them. Spaces should be trimmed.

**Input:**

* string `s` phrase to encrypt in the cipher
* integer `n` in the range of `0 <= n <= 9`

**Example:**

Input:

```
The treasure is here
2

```

Output:

> **T**!0**h**32**e**F4**t**0i**r**lk**e**hm**a**7y**s**#0**u**\*&**r**\*h**e**!2**i**H^**s**B,**h**!@**e**0)**r**$h**e**

---

This is so the shortest code wins! Good Luck and have fun!

# Answer
> 7 votes
# 05AB1E, 11 bytes

```
ð-vy²FžQ.RJ

```

Try it online!

**Explanation**

```
ð-           # remove spaces from input string
  v          # for each char in the string
   y         # push the char
    ²F       # input-2 number of times do:
      žQ.R   # push a random ascii character
          J  # join to string

```

# Answer
> 7 votes
# C#, ~~141~~ 131 bytes

Pretty similar to @Geobit's Java answer, except longer currently :(

```
(I,n)=>{var R=new System.Random();var o="";int i,r;foreach(var c in I)if(c>32)for(i=r=0,o+=c;i++<n;){r=R.Next(33,127);o+=(char)r;}return o;};

```

Full lambda stuff:

```
Func<string, int, string> a = (I,n) =>
{
    var R=new System.Random();
    var o="";
    int i;
    foreach(var c in I)
        if(c>32)
            for(i=0,o+=c;i++<n;o+=(char)R.Next(33,127));
    return o;
};

```

# Answer
> 6 votes
## Java 7, ~~132~~ 124 bytes

```
String f(int n,char[]a){String o="";int i;for(char b:a)if(b>32)for(i=0,o+=b;i++<n;o+=(char)(33+Math.random()*94));return o;}

```

Nothing fancy, just a double loop like you'd expect. Outer to loop the string, inner to fill in randoms:

```
String f(int n,char[]a){
    String o="";
    int i;
    for(char b:a)
        if(b>32)
            for(i=0,
                o+=b;
                    i++<n;
                        o+=(char)(33+Math.random()*94));
    return o;
}

```

# Answer
> 5 votes
## Pyke, ~~12~~ ~~11~~ 9 bytes

```
d-FQV~KHs

```

Try it here!

```
d-        -  remove spaces from input
  F       - for i in ^:
   QV     -  repeat (number) times:
     ~KH  -    random_from(printable)
        s -   sum(^)

```

Trailing random characters is fine according to OP.

# Answer
> 5 votes
# Octave, 43 bytes

```
@(s,n)[s(s>32);33+94*rand(n,nnz(s>32))](:)'

```

This takes a string `s` and an integer `n` as input. A string in Octave is simply an array of characters. `s>32` is a logical map with `1` for any non-space characers. The code appends a matrix with `n` rows and the same number of columns as `s(s>32)` has, containing floating point numbers between 33 and 126. It is implicitly rounded to integers and converted to ASCII-characters when it's concatenated with the string `s`. `(:)'` straightens this to a horizontal array of characters.

**Test it here!**

# Answer
> 4 votes
# Python 2, ~~123~~ ~~122~~ ~~118~~ ~~114~~ 98 Bytes

Man, I wish `random` wasn't so expensive (and that we didn't have to filter for spaces). Now we have big savings from being allowed to have cipher characters at the end :) Anyways, here ya go:

```
from random import*
f=lambda s,n:s and(' '<s[0])*eval('s[0]'+'+chr(randint(32,126))'*n)+f(s[1:],n)

```

# Answer
> 4 votes
# JavaScript (Firefox 30+), 96 bytes

```
(s,n)=>s.replace(/. */g,x=>x[0]+String.fromCharCode(...[for(_ of Array(n))Math.random()*95+32]))

```

Pure ES6 is two bytes longer:

```
(s,n)=>s.replace(/. */g,x=>x[0]+String.fromCharCode(...[...Array(n)].map(_=>Math.random()*95+32)))

```

---

Here's a really cool approach which is sadly 26 bytes longer:

```
(s,n)=>String.raw({raw:s.split` `.join``},...[for(_ of s)String.fromCharCode(...[for(_ of Array(n))Math.random()*95+32])])

```

# Answer
> 3 votes
## CJam, ~~21~~ 18 bytes

```
lS-(ol~f{{95mrSc+\}*}

```

Try it online!

Prints `n` random trailing characters.

### Explanation

```
lS-        e# Read line and remove spaces.
l~         e# Read and evaluate another line.
f{         e# For each character (passing in N)...
  {        e#   Do this N times...
    95mr   e#     Push random integer in [0, 95).
    Sc+    e#     Add to space character, giving a random printable ASCII character.
  }*
}
           e# All characters remaining on the stack are printed implicitly
           e# at the end of the program.

```

# Answer
> 3 votes
## R, 97 bytes

Unnamed function taking inputs `x` (string) and `n`.

```
function(x,n,l=nchar(x))for(i in 1:l)cat(substr(x,i,i),if(i<l)intToUtf8(sample(32:126,n)),sep="")

```

Try it on R-fiddle

# Answer
> 3 votes
**Q/KDB+, 39 36 34 Bytes**

```
raze{""sv(raze x;`char$40+n?87)}prior s
(,/)({""sv((,/)x;`char$40+n?87)}':)s

```

```
(,/)({""sv((,/)x;10h$40+n?87)}':)s

```

Variables in use:

```
s:"The treasure is here"
n:2

```

This uses the prior adverb, which applies the function to it's left between each item to the right and its predecessor. (Essentially, applies function to the left between each character on the right.)

Generate n random numbers between 40 and 126 then convert them to a character equivilent: (q seems to only have characters for these)

```
`char$40+n?87

//Possible characters.
()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~

```

Example output:

```
TVghrveVp Rpti+r0sea3a9nsIjuRXrAReJ; +di=ys`{ ikhKTe4trTZesz

```

**EDIT:**
Saved 3 bytes by converting q's raze into (,/) using the k notation and similarly changed prior to \`: Thanks to @slackwear for the update, shaved 2 bytes :)

# Answer
> 3 votes
# Bash, 124 bytes

Pure *bash* \+ *coreutils*, no control flow structures, no sub-languages, no "eval"

**Golfed**

```
E() { N=${1// /};paste <(fold -1<<<$N) <(tr -cd "\\40-\\176"<\/dev\/urandom|head -c$(($2*${#N}-$2))|fold -$2)|tr -d '\t\n';}

```

**Test**

```
>E "The treasure is here" 2
TkZhf(e&Rt@FrS,edha+-sJTuh.rX@eVKi+3s<7hftey8r*/e

```

# Answer
> 2 votes
# Java 8, 114 bytes

## Golfed

```
(n,s)->s.chars().forEach((c)->{if(c>32)for(int i=0;i<=n;)System.out.print((char)(++i==1?c:33+Math.random()*94));})

```

Lambda that accepts an Integer and a String. Inspired by the Java 7 answer, double loop using some Java 8 Stream syntax (`String.chars`) to save a few bytes.

### Input

```
3, "Hello world!"

```

### Output

```
HfKIedb3l<-Ul%}vod"Bw\"|oa`%rH-}l/-{dMS;!B#X

```

# Answer
> 2 votes
## Scala, ~~95~~ 94 Bytes

```
def c(s:String,i:Int)=s.filter(_>32).mkString(scala.util.Random.alphanumeric.take(i).mkString)

```

Nothing overly fancy, besides the use of mkString on a String. It treats the string as a list of characters, and allows me to insert a separator between them. My separator is the appropriate number of randomly generated alphanumeric characters.

# Answer
> 2 votes
# Perl 5, 81 bytes

```
($_,$n)=<>;chomp;y/ //d;$\=chop;print map{$_,map{chr 33+int rand 94}1..$n}split//

```

I hope the following helps you understand what the one-liner does:

```
($_, $n) = <STDIN>;  # Reads in the string into $_,
                     # and the number into $n, from standard input.
                     # (<STDIN> works slightly different from <>.)
chomp($_);           # Removes the newline from the string.
$_ =~ tr/ //d;       # `Tr/`ansliterates ASCII space characters
                     # into nothing, effectively `/d`eleting them.
$\ = chop($_);       # Chop()s off the last character out of $_ and
                     # appends it to the output when print()ing.
                     # (Perl always prints $\ after you call print().)
print( map {         # Each element of [List 1] will be mapped to:
    $_,              #   -- Itself, and
                     # (When mapping, each element is available as $_.)
    map {            # (`map` resembles `foreach` but returns a list.)
        chr(         #   -- A random ASCII character, in the range
          33 + int(rand(94)) ) # from 33 (!, hex 21) to 126 (~, hex 7E)
    } 1..$n          # ...$n times! (Over the range 1 to $n, actually.)
} split(//, $_) );   # [List 1] is $_, split() into characters.

```

# Answer
> 2 votes
## \>\<\> (Fish), ~~107~~ ~~106~~ 103 bytes

```
<v}:{r&" "
1xv+
2<v+
v}<
<~v!?=&:&:
6.>ol2-?!;a
:{{:}l1-[rv
v2<
<1x|!}:}-1<v!?:{{:o-+
^3<v ~}}r]~<
.40<

```

Try it online!

It isn't super random, but it is random. Just place the string and integer on the stack (Example: "Hello world!", 5).

```
Input: "Hello world!", 5
Output: H^\^]^eceeedldcdeclgfffhowhhfggojkkkkrdccedl]]\]\d

```

## Full Explanation

This is a slightly older version of the code, until I update the explanation. It's mostly the same, just maybe a bit easier to read:

```
< v}:{r&" "
+1xv
+2<v
   }
:&:<~ v!?=&
?!;a6.>ol2-
:{{:}l1-[rv
v2<
<1x|!}:}-1<v!?:{{:o+*
^3<v ~}}r]~<
.43<

```

We'll pretend the string parameter is `s` and the integer parameter is `i`.

```
< v}:{r&" "

```

The `<` tells the fish to immediately move left, which wraps around to `" "`, which adds a space characted to the stack. Then the fish travels over `&`, which adds the space to the register. `r` reverses the stack and `{:}` shifts the stack to the left (putting `i` on the end of the stack), copies the value on the end of the stack, then shifts it to the right. `v` tells the fish to begin moving downwards.

```
+1xv
+2<v
   }

```

`x` tells the fish to move in a random direction, ultimately resulting in the fish going right and continuing downwards, or pass over `1+` or `2+` beforehand. These add 1 or 2 respectively to the number on the end of the stack. If the fish travels upwards, it hits `v` again and travels back down. `}` shifts the stack to the right, then having `i` at position 1 on the stack and this new variable at position 0 (we'll call it `m`).

```
:&:<~ v!?=&

```

This section is a function, let's call it **whitespaceTrimmer**. It begins where the `<` is. It simply strips spaces that're on the end of the stack (so the beginning of the string) until it runs into a non-space character.

So immediately the fish swims into a `<` and must travel to the left. It then runs into `:&:&` which copies the value on the end of the stack, places the space from the register onto the end of the stack, copies it, then places it back onto the register.

Then the fish hits `=?!v ~`, or more specifically, `=`, which pops the last two values (the two we just created) off of the stack, compares them, places a 1 on the end of the stack if they're equal, and a 0 on the end of the stack if they're different. The `?` pops the new value off the end of the stack, if it is 0 it doesn't execute the next instruction, which in this case is `!`, it instead executes `v`, which orders the fish to move downwards (exiting the function).

If it is 1 however, then it has found a space, so it executes the `!` which is a trampoline, and that causes the fish to skip the next instruction, which is a `v`, so the fish continues. In front of the fish, it sees `~` which tells it to pop the last value off the stack (confirmed to be a space), then the fish continues, and runs the function again.

```
?!;a6.>ol2-

```

The fish is immediately told to swim right by a `>`, then output the last character on the stack by `o` (which, the first time this is run, is the first character of `s`). It gets the length of the stack from `l`, places a `2` on the end of the stack, then `-` causes 2 to be subtracted from `l`. It hits `?!;` which, remembering what `?` does, causes the fish to skip the `!` if the stack is empty, and land on `;`, which ends the program.

Following if there are still characters on the stack, we execute `!` which causes the fish to bounce over the `;` and execute `a6.`, which stores `a` (AKA `10`), and `6` on the end of the stack, which are `x, y` coordinates for `.`, which pops them off the end of the stack, then teleports the fish to `10, 6`, and execute the instruction to the right of that postion (as the fish is swimming right).

This is less complicated than it sounds when you realise `y` position 6 is the line below this one. `x` position 10 is then `v`, and to the right of that is , which is a no-op. This causes the fish to continue swimming right and actually begin execution at the beginning of the line...

```
:{{:}l1-[rv
v2<
<1x|!}:}-1<v!?:{{:o+*
^3<v ~}}r]~<
.43<

```

So this is the function that adds the random text in between the characters. It's a bit of a mouthful, but that's just because I tried to make it a little bit extra random. Let's call this **genRandomChars**.

The `:{{:}l1-[rv` is actually the setup for the function, and less-so part of the actual function itself. The fish first swims over `:{{` which copies the value on the end of the stack, then shifts it to the left twice. If you recall that `i` was at postion 1 on the stack, then you'd know `i` is now on the end of the stack.

The fish then swims over `:}` which copies `i`, and shifts the stack to the right, placing `i` both at the beginning and end of the stack. `l1-[` has the fish place the length on the end of the stack, subtract 1 from it, then `[` creates a new stack, moving `l-1` (stack length minus 1) values to the new stack (so just leaving `i` on the old stack). Then the fish simply hits `rv` which reverses the stack again (I think creating a new stack reverses it for some reason), and orders the fish to swim downwards once more, truely beginning the function at the `<` below.

So currently the end of the stack has `m` and our temporary `i`, which we'll call `ti`. Immediately the fish swims over `1-}`, which subtracts 1 from `ti` and moves it to the beginning of the stack. Then `:}` which simply copies `m` and moves it to the beginning of the stack (putting `ti` at stack position 1).

This is when we hit this little thing:

```
v2<
<1x|!
^3<

```

This is actually dead simple. The `!` causes the fish to skip `|` and execute `x`. Remembering what `x` does, we remember this makes the fish move in any 4 directions. `|` is simply a mirror, and causes the fish to swim back to `x`. So basically, the fish will place 1, 2, or 3 onto the end of the stack, and continue moving left, wrapping around.

The fish then executes `*+o` which causes the last two values on the stack to be popped off, multiplied together, and the result push back on, then the same thing with addition, then the final value is popped off the stack and outputted with `o`. Our stack is now relatively normal again containing just \[`m`, `ti`, `s`\].

`:}}:` causes the value on the end of the stack (basically `s` position 0) ot be copied, then the stack is shifted to the right twice (placing `ti` on the front again), then `ti` is copied. `?!v` should be pretty easy to understand by now. Basically if `ti` is 0 then we exit the function with `v`, otherwise we execute `!` and skip `v` (doing another loop).

If `ti` is 0 and we are done outputting slightly random characters, then we execute `v` and see:

```
   v ~}}r]~<
.43<

```

Nothing too fancy here. We remove `ti` from the stack via `~`. Then `]` is new, it pops all our values off the stack and places them on the old stack! Because of the reversal issue we reverse with `r`, then shift the stack right twice with `}}~`, shufting the stack to the right, giving us \[`m`, `i`, `s`\], the `~` is to remove the extra duplicated `s[0]` from earlier in the function as we'd need it if we were doing a loop (but we're not, we're exiting). `v` tells the fish to swim down and into `>34.` (inverted to show execution order), which tells the fish to simply swim left and into `3, 4` (because the `.` is a jump!). `3, 4` is actually just to the right of the beginning `whitespaceTrimmer`, which is perfect because we are travelling left.

Following all this logic we can follow the fish until the stack is ultimately empty and program exits just after `whitespaceTrimmer` is executed.

# Answer
> 1 votes
## Clojure, ~~126~~ ~~123~~ ~~118~~ ~~122~~ 117 bytes

```
(defn c[m n](apply str(remove #(=\space %)(mapcat #(apply str %(for [_(range n)](char(rand-nth(range 32 127)))))m))))

```

Maps over the message, inserts random characters in, then concatenates the result.

The instructions suggest that all spaces should be stripped from the result string. If only spaces from the original message are supposed to be stripped, I can change that.

Ungolfed:

```
(defn cipher [message n]
  (apply str
    (remove #(= \space %)
        (mapcat #(apply str %
                     (for [_ (range n)]
                       (char (rand-nth (range 32 127)))))
                message))))

```

# Answer
> 1 votes
# Python 3, 127 Bytes

```
import random
a,b=input(),input()
print(''.join([x+''.join([chr(random.randint(33,126))for c in range(int(b))]) for x in a]))

```

Probably way longer than necessary, but this is mine golfed so far.

# Answer
> 1 votes
# PHP, 96 bytes

Takes String as argument 1 and Number as argument 2

```
for(;($s=str_replace(' ','',$argv[1]))[$j]>'';)echo$i++%($argv[2]+1)?chr(rand(33,127)):$s[$j++];

```

Try it online

# Answer
> 1 votes
# Python 3, 133 Bytes

```
from random import *
c=int(input())
print(''.join([i+''.join([chr(randint(33,126))for i in range(c)])for i in input().strip(' ')])[:-c])

```

# Answer
> 1 votes
# Node.js, 88 bytes

```
(s,n)=>s.replace(/./g,c=>c!=" "?c+crypto.randomBytes(n).toString`base64`.substr(0,n):"")

```

Example outputs:

```
f("The treasure is here", 2)
// THphdwekAtMArbSeU1aDTsZWuqnr2yek1iyUsKshqXewvrVCeTi

f("The treasure is here", 2)
// TYshlcep6t4Iru7e29aQ1sl/uvQrlzeSJihysDhhOLe1urpte1m

```

Try it online!

# Answer
> 1 votes
# C, ~~102~~ 100 bytes

-2 bytes for skipping `continue`.

```
i;f(char*s,int n){do{while(*s==32)++s;putchar(*s);i=n;while(i--)putchar(32+rand()%95);}while(*s++);}

```

Ungolfed:

```
i;
f(char*s,int n){
 do{
  while(*s==32)++s;
  putchar(*s);
  i=n;
  while(i--)
    putchar(32+rand()%95);
 }while(*s++);
}

```

Usage:

```
main(){
  char a[]="A   A A";
  f(a,3);
}

```

---
Tags: code-golf, string, random, cryptography
---


# Question
Title: Can I take your order: a Chipotle concept conund
# Challenge

Your program will take in a string from **stdin**, and output multiple lines to **stdout**.

An example of input looks like this:

My favorite Chipotle order:

> B1113YNNY

Let's break it down:

* The first character is either A (burrito), or B (burrito bowl).
* The second character is 1 (black beans), or 2 (pinto beans).
* The third character is either 1 (white rice), or 2 (brown rice).
* The fourth character is either 1 (chicken), 2 (sofritas), or 3 (steak).
* The fifth character is either 1 (mild salsa), 2 (medium salsa), or 3 (hot salsa).
* The last four characters are Y if they want the item, or N otherwise:
* character 6 is corn
* character 7 is guacamole
* character 8 is sour cream
* character 9 is cheese

A working program for this challenge will output this to **stdout**:

> burrito bowl with:
> black beans
> white rice
> chicken
> hot salsa
> corn
> cheese

Replace the above words with the words acquired from input.

# Clarifications.

Standard loopholes are disallowed.
You may *only* get input from stdin, and *only* put output to stdout.

# Answer
> 1 votes
# Python 3, 293 bytes

```
j=input();a,b,c,d,e,f,g,h,i=[1-ord(c)%7%5for c in j];print('\n'.join(('burrito'+[' bowl',''][a]+' with:',['pinto','black'][b]+' beans',['brown','white'][c]+' rice',['sofritas','chicken','steak'][d],['medium','mild','hot'][e]+' salsa'))+'\ncorn'*f+'\nguacamole'*g+'\nsour cream'*h+'\ncheese'*i)

```

Mostly basic lookups with a little modulo trickery for the indexes of items:
`AB123YN` yielding indexes `-1,-2,1,0,-1,1,0` respectively, and
using string multiplication for the optional items rather than a lookup.

# Answer
> 1 votes
## Python 2, ~~302~~ 298 bytes

```
o=input()
print"\n".join([s[0]+s[1+(ord(c)+1)%3]+s[-1]for(x,c)in zip(["burrito ,,bowl, with:",",black,pinto, beans",",white,brown, rice",",chicken,sofritas,chicken,",",mild,medium,hot, salsa"],o)for s in[x.split(",")]]+[x for(x,c)in zip(["corn","guacamole","sour cream","cheese"],o[5:])if c=="Y"])

```

EDIT: according to the consensus on meta, I'm allowed to use `input` instead of `raw_input`, requiring the user of the program to type his or her Chipotle order in quotes! Thanks, @StevenH. for informing me of this.

# Answer
> 0 votes
# Python 2, ~~336~~ 335 Bytes

```
q,i=input(),int
print"burrito "+{"A":"","B":"bowl"}[q[0]]+" with:\n"+["black","pinto"][i(q[1])-1]+" beans\n"+["white","brown"][i(q[2])-1]+" rice\n"+["chicken","sofritas","steak"][i(q[3])-1]+"\n"+["mild","medium","hot"][i(q[4])-1]+" salsa\n"+"\n".join([x for y,x in enumerate(["corn","guacamole","sour cream","cheese"]) if q[y+5]=="Y"])

```

Try it online!

Removed one byte by renaming `int`: `i=int`

# Answer
> 0 votes
## Batch, ~~445~~ 364 bytes

```
@echo off
set/ps=
set l=call:l
%l%"burrito with:" "burrito bowl with:"
%l%"black beans" "pinto beans"
%l%"white rice" "brown rice"
%l%chicken sofritas steak
%l%"mild salsa" "medium salsa" "hot salsa"
%l%corn
%l%guacamole
%l%"sour cream"
%l%cheese
exit/b
:l
for %%a in (B N 2 3 3)do if %s:~0,1%==%%a shift
if not "%~1"=="" echo %~1%
set s=%s:~1%

```

New rewrite saved me 81 bytes. Reading from STDIN conveniently saves a byte over using the command line. Each character of the input is processed in turn to select from a list of options; the characters `B`, `N` and `2` cause the second option to be chosen, while `3` causes the third option to be chosen.

# Answer
> 0 votes
# Pyth, 225 Bytes

```
=rQ0s["burrito "?xGhQ"bowl "k"with:")+@,"pinto""black"shtQ" beans"+@,"brown""white"shttQ" rice"@c"steak chicken sofritas")s@Q3+@c"hot medium mild")s@Q4" salsa"seMf}\y@QhT[,5"corn\n",6"guacamole\n",7"sour cream\n",8"cheese\n")

```

# Answer
> 0 votes
## Racket 544 bytes

```
(let*((s(read-line))(l(string->list s))(lr list-ref)(d displayln)(p display)(c -1)(g(λ()(set! c(+ 1 c))(lr l c))))
(match(g)[#\A(d"burrito with:")][#\B(d"burrito bowl with:")])(match(g)[#\1(d"black beans")][#\2(d"pinto beans")])
(match(g)[#\1(d"white rice")][#\2(d"brown rice")])(match(g)[#\1(d"chicken")][#\2(d"sofritas")][#\3(d"steak")])
(match(g)[#\1(p"mild ")][#\2(p"medium ")][#\3(p"hot ")])(d"salsa")(match(g)[#\Y(d"corn")][#\N""])
(match(g)[#\Y(d"guacamole")][#\N""])(match(g)[#\Y(d"sour cream")][#\N""])(match(g)[#\Y(d"cheese")][#\N""]))

```

Ungolfed:

```
(define (f)
  (let* ((s (read-line))
         (l (string->list s))
         (lr list-ref)
         (d displayln)
         (p display)
         (c -1)
         (g (lambda() (set! c (add1 c)) (lr l c))))
    (match (g)
      [#\A (d "burrito with:")]
      [#\B (d "burrito bowl with:")])
    (match (g)
      [#\1 (d "black beans")]
      [#\2 (d "pinto beans")])
    (match (g)
      [#\1 (d "white rice")]
      [#\2 (d "brown rice")])
    (match (g)
      [#\1 (d "chicken")]
      [#\2 (d "sofritas")]
      [#\3 (d "steak")])
    (match (g)
      [#\1 (p "mild ")]
      [#\2 (p "medium ")]
      [#\3 (p "hot ")])
    (d "salsa")
    (match (g)
      [#\Y (d "corn")]
      [#\N ""])
    (match (g)
      [#\Y (d "guacamole")]
      [#\N ""])
    (match (g)
      [#\Y (d "sour cream")]
      [#\N ""])
    (match (g)
      [#\Y (d "cheese")]
      [#\N ""])))

```

Testing:

```
(f)

burrito bowl with:
black beans
white rice
chicken
hotsalsa
corn
cheese

```

# Answer
> 0 votes
# PHP, 301 Bytes

```
<?="burrito".($i=$_GET[a])[0]>A?" bowl":""," with:\n".[black,pinto][$i[1]>1]." beans\n".[white,brown][$i[2]>1]." rice\n".[_,chicken,sofritas,steak][$i[3]]."\n".[_,mild,medium,hot][$i[4]]." salsa".["","\ncorn"][$i[5]>N].["","\nguacamole"][$i[6]>N].["","\nsour cream"][$i[7]>N].["","\ncheese"][$i[8]>N];

```

Previous version 311 Bytes

```
<?printf("burrito%s with:\n%s beans\n%s rice\n%s\n%s salsa%s%s%s%s",($i=$_GET[a])[0]>A?" bowl":"",[black,pinto][$i[1]>1],[white,brown][$i[2]>1],[_,chicken,sofritas,steak][$i[3]],[_,mild,medium,hot][$i[4]],["","\ncorn"][$i[5]>N],["","\nguacamole"][$i[6]>N],["","\nsour cream"][$i[7]>N],["","\ncheese"][$i[8]>N]);

```

# Answer
> 0 votes
# C#, 737 Bytes

*Not going to win any prizes here...*

Golfed:

```
string O(string s){var c=new List<string>();var m=new Dictionary<int,List<string>>(){{0,new List<string>(){"burrito","burrito bowl"}},{1,new List<string>(){"","black beans","pinto beans"}},{2,new List<string>(){"","white rice","brown rice"}},{3,new List<string>(){"","chicken","sofritas","steak"}},{4,new List<string>(){"","mild salsa","medium salsa","hot salsa"}},{5,new List<string>(){"corn"}},{6,new List<string>(){"guacamole"}},{7,new List<string>(){"sour cream"}},{8,new List<string>(){"cheese"}},};for(int i=0;i<s.Length;i++){if(i==0){c.Add(s[0]=='A'?m[0][0]:m[0][1]+" with:");continue;}if(i>4){c.Add(s[i]=='Y'?m[i][0]:"");continue;}c.Add(m[i][int.Parse(s[i]+"")]);}return string.Join("\n",c.Where(o =>!string.IsNullOrEmpty(o)));}}

```

Ungolfed:

```
public string O(string s)
{
  var c = new List<string>();

  var m = new Dictionary<int, List<string>>()
  {
    {0, new List<string>(){"burrito", "burrito bowl"}},
    {1, new List<string>(){"", "black beans", "pinto beans"}},
    {2, new List<string>(){ "", "white rice", "brown rice"}},
    {3, new List<string>(){ "", "chicken", "sofritas", "steak"}},
    {4, new List<string>(){ "", "mild salsa", "medium salsa", "hot salsa"}},
    {5, new List<string>(){"corn"}},
    {6, new List<string>(){"guacamole"}},
    {7, new List<string>(){"sour cream"}},
    {8, new List<string>(){"cheese"}},
  };

  for (int i = 0; i < s.Length; i++)
  {
    if (i == 0)
    {
      c.Add(s[0] == 'A' ? m[0][0] : m[0][1] + " with:");
      continue;
    }

    if (i > 4)
    {
      c.Add(s[i] == 'Y' ? m[i][0] : "");
      continue;
    }

    c.Add(m[i][int.Parse(s[i]+"")]);
  }

  return string.Join("\n", c.Where(o => !string.IsNullOrEmpty(o)));
}

```

Testing:

```
  var chipotleOrder = new ChipotleOrder();
  Console.WriteLine(chipotleOrder.P(Console.ReadLine()));
  Console.ReadLine();

```

Output:

```
burrito bowl with:
black beans
white rice
chicken
hot salsa
corn
cheese

```

# Answer
> 0 votes
# JavaScript (ES6), 267

```
a=>[...a].map((c,i,a,s=x=>`
`+(','+x).split`,`[c])=>i--?i--?i--?i--?i?c>'N'?(c=i,s`corn,guacamole,sour cream,cheese`):'':s`mild,medium,hot`+' salsa':s`chicken,sofritas,steak`:s`white,brown`+' rice':s`black,pinto`+' beans':'burrito'+(c>'A'?' bowl':'')+' with:').join``

```

*Less golfed*

```
a=>
[...a].map((c,i,a,s=x=>'\n'+(','+x).split`,`[c])=>
       i--?i--?i--?i--?i?
       c>'N'?(c=i,s`corn,guacamole,sour cream,cheese`):''
       :s`mild,medium,hot`+' salsa'
       :s`chicken,sofritas,steak`
       :s`white,brown`+' rice'
       :s`black,pinto`+' beans'
       :'burrito'+(c>'A'?' bowl':'')+' with:'
).join``

```

**Test**

```
f=
a=>[...a].map((c,i,a,s=x=>`
`+(','+x).split`,`[c])=>i--?i--?i--?i--?i?c>'N'?(c=i,s`corn,guacamole,sour cream,cheese`):'':s`mild,medium,hot`+' salsa':s`chicken,sofritas,steak`:s`white,brown`+' rice':s`black,pinto`+' beans':'burrito'+(c>'A'?' bowl':'')+' with:').join``

function update()
{
  O.textContent=f(I.value);
}

update()
```

```
<input id=I value="B1113YNNY" oninput='update()'><pre id=O></pre>
```

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


# Question
Title: Is it a Linearized Tree? (Breadth-first Edition)
## Background

An unlabelled tree may look like this:

```
   o
 / | \
o  o  o
|    / \
o   o   o

```

To *linearize* this tree, we first label each node `o` with it's number of child nodes:

```
   3
 / | \
1  0  2
|    / \
0   0   0

```

and then write the numbers in a list in a breath-first manner, meaning line by line and left to right:

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

```

This is a unique and unambiguous representation of the tree above, meaning that no two different pure trees will have the same linearizations and that we can reconstruct the original tree from the list.

Although each tree corresponds to a certain integer list, not each integer list represents a valid linearized tree: For example `[2, 0, 0, 0]` does not represent a valid tree, if we try to de-linearize it we end up with this tree

```
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
            / \          / \        / \
                        0          0   0

```

but still have a `0` left in the list and nowhere to put it. Similarly `[2, 0]` is not a valid tree linearization either, as the de-linearized tree has an empty child spot:

```
  2
 / \
0

```

## Task

Given an integer list, decide whether it is a valid linearization of a tree using as few bytes as possible. You may write a full program or a function.

**Input:** A non-empty list of non-negative integers.

**Output:** A truthy value if the list is a linearization of a tree, a falsy value otherwise.

## Testcases

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

```
Falsy
```
[0, 1]
[2, 0]
[2, 0, 0, 0]
[1, 0, 1]
[3, 2, 1, 0]
[2, 0, 0, 2, 0, 0]
[4, 1, 0, 3, 0, 0, 0, 0]
[4, 2, 0, 3, 1, 0, 0, 0, 0, 0]

```

# Answer
## Haskell, 44 bytes

```
f[n:k]=iterate f[k]!!n
f _=[]
g x=f[x]==[[]]

```

Defines a function `g` that takes a list and returns a boolean. See it pass all test cases.

## Explanation

This relies on the fact that depth-first and breadth-first linearizations produce the same arrays. See Martin's answers for details; basically they both give the same arithmetical condition on the array.

The function `f` is given the input list wrapped in a singleton list. It pops one number `n` off the list, then calls itself `n` times on the remaining list to process the children of the popped node (depth first). Popping the empty list results in `[]`, which I use as an error state. The function `g` checks that the end result is `[[]]`, the unique non-erroneous state with no unprocessed nodes. If Haskell was weakly typed, I could just use `0` or something as the error state, and wouldn't have to wrap the input into another list.
> 4 votes

# Answer
## Mathematica, 38 bytes

```
Last@#<0<=Min@Most@#&@Accumulate[#-1]&

```

The basic idea is that we keep track of a number of nodes to fill. Each element in the list uses up one node and adds as many as it has children. So each element `i` changes the total count by `i-1`. This count is off by one, because should be starting from `1` (the root), not `0`.

For the tree to be valid we a) can never go below `0` throughout the list, because we wouldn't have anywhere to place the current node and b) need to end up with `-1` at the end, otherwise we've got unused nodes left.

We obtain this running total of remaining nodes with `Accumulate[#-1]` (which computes the prefix sums of the input list minus one). And then we check that the last element and *only* the last element is `-1` with:

```
Last@#<0<=Min@Most@#

```

Note that checking that the last element is negative is sufficient, since we can never decrement by more than `1`, so if the last values was `-2` or lower it would be impossible for the minimum the others to be non-negative.
> 3 votes

# Answer
## Retina, 29 bytes

```
\d+
$*
^(?<-1>(1)*,)*$(?(1)!)

```

Try it online! (The first line enables a linefeed-separated test suite.)

### Explanation

The basic idea is the same as that of my Mathematica answer: we keep track of a running total of remaining nodes, ensure it never goes below zero but ends on zero. However, the way this is implemented with regex is very different.

```
\d+
$*

```

This simply converts the input to unary, turning each integer `n` into `n` 1s.

```
^(?<-1>(1)*,)*$(?(1)!)

```

This is where the real magic happens. It's a fairly short regex that matches only valid trees, but it's mechanics are quite subtle.

I'm using balancing groups to keep track of the number of nodes, which are a way to work with stacks inside the regex.

First off, of course such a stack can never have a negative depth, so we can't really end up with a representation of `-1` at the end, as we do in the Mathematica solution. However, we can note that the final element of the input *has* to be zero on a valid stack (otherwise we couldn't end up with `-1`). It turns out that it actually saves bytes to check *both* that we end on zero and with zero remaining nodes.

So here is a breakdown of the regex:

```
^        e# Anchor the match to the beginning of the string.
(?<-1>   e# Each repetition of this group will match one number.
         e# We can ignore the <-1> for now.
  (1)*   e#   Match each unary digit of the current number, pushing
         e#   a capture onto stack 1. This increments our total of
         e#   remaining nodes by 1 for each child.
  ,      e#   Match a comma. Note that this requires that there is at
         e#   least one more number in the list.
)*       e# At the end of the repetition the <-1> pops one capture from
         e# the stack. This is the node that the current number itself
         e# takes up.
$        e# Match the end of the string. This requires the input to end
         e# in a zero, because the last thing we matched was a comma.
(?(1)!)  e# Make sure that stack 1 is empty, so that we don't have any
         e# unused nodes.

```
> 2 votes

# Answer
## CJam (20 bytes)

```
{X0@{+\(_0>{\}*}/|!}

```

Online test suite. This is an anonymous block which takes an array on the stack and leaves 0 or 1 on the stack.

### Dissection

In pseudocode this is:

```
p = 1
q = 0
foreach (i in input):
  q += i
  if (--p <= 0):      # in practice, if (--p == 0):
      p, q = q, p
return (p | q) == 0   # i.e. p == 0 && q == 0

```

`q` accumulates the sum of the labels of the nodes at the current level in the tree; `p` counts down the nodes remaining in the current level.
> 1 votes

# Answer
## Labyrinth, 17 bytes

```
(
+?
;-)
,_"
@@,!

```

Try it online!

Truthy output is `-1` and falsy output is empty. Defining truthy and falsy in Labyrinth is a bit tricky, because Labyrinth's branches are principally ternary. However, the only way to construct a conditional with reliably two branches, you can only do this:

```
>"F
 T

```

In this case, I'd consider moving straight ahead falsy (because the direction of movement is unaffected) and turning truthy. These correspond to zero and non-zero respectively. The reason I'm using an empty output to represent zero is that, if you were to pipe the output back into another Labyrinth program, the input operator `?` would actually push a zero if the input is empty, so I consider the empty string a valid representation of zero.

### Explanation

The algorithm is still the same as in my Mathematica and Retina answers, but due to Labyrinth's control flow, it works a bit different this time:

* We don't work with the total counter off-by-one here. Instead we a) work with a negative counter and b) initialise it to `-11` initially, so that we want the counter to be negative throughout the list and hit zero on the last input. This actually simplifies the control flow here.
* Instead of building the full list and checking whether it contained the wrong value, there are three possible termination conditions:

1. We hit EOF before reaching a total count of zero. In that case there are unused nodes left and we print nothing.
    2. We reach zero *and* we're at EOF. In this case, we've got a valid tree.
    3. We reach zero and aren't at EOF yet. In this case, we ran out of nodes before covering all elements, and we print nothing.

As for the actual code, we start in the top left corner. The `(` turns the implicit zero on top of the stack into a `-1`, which will be the running total. We then enter the very tight main loop of the program, `+?-)"_,;+`:

```
+   Add the top two values. This does nothing on the first iteration,
    but gets rid of a helper-zero on subsequent iterations.
?   Read and push integer.
-   Subtract it from running total.
)   Increment.
"   No-op. There is a branch at this point. If the running total is zero,
    we move straight ahead onto the , (see below). Otherwise, the loop continues.
_   Push a zero. This is necessary to prevent the IP from turning south.
,   Read a character. This will either be the next separator (some positive
    number) or EOF (-1). If it's EOF, the IP turns south and the program
    terminates. Otherwise, the loop continues.
;   Discard the separator.

```

That leaves only the cases where we've reduced the running total to zero at some point. The IP moves onto the lower-right `,` and reads another character to check if we've reached EOF. If not, the value will be positive and the IP turns west towards the `@` and the program terminates. If we did reach EOF, the IP turns east and prints the `-1` with `!`. The IP will then worm its way towards the lower left `@` via a slightly weird path to terminate the program.
> 1 votes

# Answer
## Python, 82 bytes

```
lambda l:len(l)==sum(l)+1 and not any(list(l[x]>=len(l)-x for x in range(len(l))))

```

Need more test cases.
> 0 votes

# Answer
# Pyth, 13 bytes

```
qxsM._tMQ_1tl

```

We start by calculating the current filled-ness of the tree at all points in the input representation. That portion of the idea is largely borrowed from Martin Ender, so thanks to him. `sM._tMQ`

Once we have this list, we check if the first index containing `-1` (`x..._1`) is the length of the input minus one (`q...tl(Q)`).

Don't believe it works? Try it yourself!
> 0 votes

---
Tags: code-golf, graph-theory, decision-problem, tree-traversal
---