title: Sort items based on dependency

text:
# Question
Title: Sort items based on dependency
# Goal

Sort a list of items ensuring that each item is listed after its specified dependencies.

# Input

An array of arrays of integers, where each integer specifies the 0-based or 1-based index of another item that this item must come after. The input may be an array or string or anything else human readable.

For example, a 0-based input:

```
[
  [ 2 ],    // item 0 comes after item 2
  [ 0, 3 ], // item 1 comes after item 0 and 3
  [ ],      // item 2 comes anywhere
  [ 2 ]     // item 3 comes after item 2
]

```

Assume there are no circular dependencies, there is always at least one valid order.

# Output

The numbers in order of dependency. An ambiguous order does not have to be deterministic. The output may be an array or text or anything else human readable.

Only one order should be given in the output, even where there are multiple valid orders.

Possible outputs for the above input include:

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

```

# Scoring

A function or program that completes this in the least number of bytes wins the glory of acceptance. The deadline is in 6 days.

# Answer
# Jelly, 8 bytes

```
ịÐL³ŒḊ€Ụ

```

This is based on the (unimplemented) depth approach from @xnor's Python answer.

Try it online!

### How it works

```
ịÐL³ŒḊ€Ụ  Main link. Input: A (list of dependencies)

 ÐL       Apply the atom to the left until a loop is reached, updating the left
          argument with the last result, and the right argument with the previous
          left argument.
ị         For each number in the left argument, replace it with the item at that
          index in the right argument.
   ³      Call the loop with left arg. A (implicit) and right arg. A (³).
    ŒḊ€   Compute the depth of each resulting, nested list.
       Ụ  Sort the indices of the list according to their values.

```
> 4 votes

# Answer
## Pyth, 21 bytes

```
hf.A.e!f>xYTxkTbQ.plQ

```

```
                    Q  input
                   l   length of input array
                 .p    all permutations of [0, 1, ..., lQ-2, lQ-1]
hf                     find the first permutation for which...
    .e          Q        map over the input array with indices...
       f       b           find all elements in each input subarray where...
        >xYT                 index of dependency is greater than...
            xkT              index of item
      !                    check whether resulting array is falsy (empty)
  .A                     is the not-found check true for [.A]ll elements?

```

Test:

```
llama@llama:~$ echo '[[2],[0,3],[],[2]]' | pyth -c 'hf.A.e!f>xYTxkTbQ.plQ'
[2, 0, 3, 1]

```
> 7 votes

# Answer
## Python 2, 73 bytes

```
l=input()
f=lambda n:1+sum(map(f,l[n]))
print sorted(range(len(l)),key=f)

```

Sorts the vertices by their descendant count, which `f` computes recursively. If a vertex points to another vertex, its descendants include the pointed vertex and all of that vertex's descendants, so it has strictly more descendants. So, it is placed later than the pointed vertex in the ordering, as desired.

The descendant count of a vertex is one for itself, plus the descendant counts of each of its children. Note that a descendant can be counted multiple times if there are multiple paths leading to it.

It would have also worked to used depth rather than descendant count

```
f=lambda n:1+max(map(f,l[n]))

```

except the `max` would need to give `0` on an empty list.
> 7 votes

# Answer
# Pyth, 19 bytes

```
hf!s-V@LQT+k._T.plQ

```

Try it online: Demonstration

### Explanation:

```
hf!s-V@LQT+k._T.plQ   implicit: Q = input list
               .plQ   all permutations of [0, 1, ..., len(Q)-1]
 f                    filter for permutations T, which satisfy:
      @LQT               apply the permutation T to Q
                         (this are the dependencies)
            ._T          prefixes of T
          +k             insert a dummy object at the beginning
                         (these are the already used elements)
    -V                   vectorized subtraction of these lists
   s                     take all dependencies that survived
  !                      and check if none of them survived
h                    print the first filtered permutation

```
> 4 votes

# Answer
# Bash + perl, 35 bytes

```
perl -pe's/^$/ /;s/\s/ $. /g'|tsort

```

### Example run

I/O is 1-indexed. Each array goes on a separate line, with whitespace as item separator.

```
$ echo $'4\n1\n\n3\n1 3 2' # [[4], [1], [], [3], [1, 3, 2]]
4
1

3
1 3 2
$ bash tsort <<< $'4\n1\n\n3\n1 3 2'
3
4
1
2
5

```

### How it works

`tsort` – which I learned about in @DigitalTrauma's answer – reads pairs of tokens, separated by whitespace, that indicate a partial ordering, and prints a total ordering (in form of a sorted list of all unique tokens) that extends the aforementioned partial ordering.

All numbers on a specific line are followed by either a space or a linefeed. The `s/\s/ $. /g` part of the Perl command replaces those whitespace characters with a space, the line number, and another space, thus making sure that each **n** on line **k** precedes **k**.

Finally, if the line is empty (i.e., consists only of a linefeed), `s/^$/ /` prepends a space to it. This way, the second substitution turns an empty line **k** into `k k`, making sure that each integer occurs at least once in the string that is piped to `tsort`.
> 4 votes

# Answer
# Bash + coreutils, 20 80

```
nl -v0 -ba|sed -r ':;s/(\S+\s+)(\S+) /\1\2\n\1 /;t;s/^\s*\S+\s*$/& &/'|tsort|tac

```

Input as space-separated lines, e.g.:

```
2
0 3

2

```
* `nl` adds zero-based indices to all lines
* `sed` splits depedency lists into simple dependency pairs, and makes incomplete dependencies dependent on themselves.
* `tsort` does the required topological sort
* `tac` puts the output reverse order

Ideone. Ideone with @Dennis' testcase
> 3 votes

# Answer
# Python 2, 143 118 116 bytes

A slightly more *random* approach.

```
from random import*
l=input()
R=range(len(l))
a=R[:]
while any(set(l[a[i]])-set(a[:i])for i in R):shuffle(a)
print a

```

Edits:

* fixed it, and actually saved some bytes too.
* Saved 2 bytes (thanks @Dennis)
> 2 votes

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


title: Classic Proof Fallacy

text:
# Question
Title: Classic Proof Fallacy
## The Background

So, we all know the classic proof that goes like this:

a = b
a² = ab
a² - b² = ab - b²
(a-b)(a+b) = b(a-b)
(a+b) = b
b+b = b
2b = b
2 = 1 (Ha ha!)
Of course, the mistake is that you can't divide by 0. Since a = b, a - b = 0, so there was a hidden division by 0.

## The Challenge

You have to replicate this proof. First, declare two integers a and b (it doesn't matter what you call them) that equal. Then declare aMod and bMod to be modifiable versions of a and b and initially equal to a and b, respectively. You must multiply them both by a, then subtract b\*b from both of them. You must then divide by a - b and then divide them by b (or a) to get. Then, print out aMod and bMod with an equal sign between them.

## The Underhanded

Of course, since you declared a and b to equal, a - b = 0, and dividing by 0 causes an error. So you must creatively fake it. Also, because you are trying to replicate the proof, the result on all the operations on aMod and bMod must not equal when printed. They don't have to equal exactly 2 and 1, just two numbers that don't equal.

Here is an example:

```
#include <iostream>
#define subtract(a, b) a - b

using namespace std;
int main()
{
    int a = 4, b = 4;
    int a_2 = a, b_2 = b;

    a_2 *= a;
    b_2 *= b;

    a_2 -= b * b;
    b_2 -= b * b;

    a_2 = a_2 / subtract(a, b);
    b_2 = b_2 / subtract(-b, -a); // a - b == (-b) - (-a)

    a_2 /= a;
    b_2 /= a;

    cout << a_2 << " = " << b_2 << " because I did the same operations on both of them.";

    return 0;
}

```

Maybe not the best one, but it illustrates the point.

## Bonus Underhanded

Instead of printing the equals sign, you can print out just the two variables (aMod and bMod), and then have code that appears to compare the two variables for equality but in actuality lies that they equal (and prints some form of `true`).

Remember, this is a popularity contest, so highest number of upvotes wins.
Also, a new version of mathematics called Mathematics 2.0 has made use of standard loopholes automatically invalidate a proof.

# Answer
> 17 votes
# JavaScript

```
var a=3,b=3,a2=3,b2=3
[a2,b2]=[a2*a,b2*a]
[a2,b2]=[a2-b*b,b2-b*b]
[a2,b2]=[a2/(a-b),b2/(a-b)]
console.log([a2/a,b2/a])

```

Output:

```
[1, NaN]

```

Note that 0/0 = NaN

### Hint

> Try add some semicolons.
> This program is actually `var a=3,b=3,a2=3,b2=3[a2,b2]=...=[a2/(a-b),b2/(a-b)];console.log([a2/a,b2/a])`.
> And the NaN is `[3/0,undefined/0]/3`.

# Answer
> 3 votes
# Python 2

I'm pretty sure it's obvious since everyone knows Python, but here's my attempt:

```
a=b=1
x,y=a*a,a*b
x,y=x-b*b,y-b*b
x,y=a+b/a-b,b
x,y=x/a,y/a
print(x==y)

```

It outputs `True`.

Hint:

> Check my division.

# Answer
> 2 votes
# Ruby

```
def calculate a,
  b = a
  left, right = a, b
  left, right = [left, right].map { |x| x * a     }
  left, right = [left, right].map { |x| x - b*b   }
  left, right = [left, right].map { |x| x / a - b }
  left, right = [left, right].map { |x| x / b     }
  puts $/=[left, right].join(' = ')
end

calculate 3,
STDOUT.write($/)

```

ideone

Hint:

> ,

Explanation:

> The two lines that end in commas cause the program to behave differently than it would. Without the commas, the method takes a single argument `a`, sets `b` equal to `a`, performs the transformations from the proof on each one (except due to some missing parentheses, it doesn't divide by 0), and outputs the result (With input of 3, it'd output "-1 = -1". With the trailing comma, however, the `b = a` line becomes part of the method signature, meaning that it's declaring a second argument with a default value. The method invocation at the end passes in the result of `STDOUT.write($/)`, which is 1 (the number of bytes it wrote to STDOUT, since `$/` is predefined to a newline character.) So a is 3 and b is 1, resulting in the equation starting off as "3 = 1". Garbage in, garbage out.

# Answer
> 2 votes
# GolfScript

Warning: this program is cheating a bit, in that it doesn't print aMod and bMod

```
1nt main(){
  int a = 2, b = 2;
  int aMod,bMod;
//The next line should throw and error, but why doesn't it??/
  aMod = (a*a - b*b) / (a-b);
//The next line should throw and error, but why doesn't it??/
  bMod = (b*a - b*b) / (a-b);
//The if should fail, but it works??/
  if(aMod == bMod)
    printf("1");
  return 0;
};

```

Try it here!

So what's going on?

> The first thing you may have noticed are the "forbidden trigraphs". But remember, this is GolfScript, not C! Also, probably noticed that it doesn't actually say "int main()", it says "1nt main()". In GolfScript, the "1" means push 1 onto the stack, and the "nt main" gets processed as two uninitialized variables, which do nothing. The two parentheses first add 1 to the top number of the stack, and then subtract one, essentially cancelling themselves out. The brackets denote a block that gets pushed onto the stack, and then the semicolon pops it off right away. So, at the end, we just have the original "1" that was pushed on, and at the end of a GolfScript program, the stack gets printed. This answer was inspired by this one.

# Answer
> 1 votes
## JavaScript

```
//Very badly written code!
//No! It is "poetic" code!
while(true){break;}{
let scrollMaxX = 3, screenX = 3;
var scrollBarWithBeerMax = scrollMaxX, Yscroll = screenX; for(var i = 0; i<1; i++){}}

scrollBarWithBeerMax *= scrollMaxX;
Yscroll *= screenX;

scrollBarWithBeerMax -= screenX * screenX;
Yscroll -= screenX * screenX;

scrollBarWithBeerMax /= (scrollMaxX - screenX);
Yscroll /= (scrollMaxX - screenX);

alert(scrollBarWithBeerMax + ' = ' + Yscroll);

```

Output:
http://jsbin.com/furino/2/edit?js,output JsBin doesn't seem to be able to execute this code. Use the browser console instead.

Why?

> scrollMaxX and screenX are already existing variables. They are built in in the browser. Thus, the result may vary. The let keyword only temporarily changes their value.

Another JavaScript one: It doesn't exactly follow the rules, it only outputs if the variables are equal or not.

```
var a = 2;
var b = 2;

var a_duplicate = a;
var b_duplicate = b;

a_duplicate*=a
b_duplicate*=b;

a_duplicate-=b*b;
b_duplicate-=b*b;

a_duplicate/=(a-b);
b_duplicate/=(a-b);

alert(a_duplicate==b_duplicate);

```

Why?

> NaN is not equal to NaN by IEEE float specifications. Thanks to Alex Van Liew for pointing out that this doesn't just apply to Javascript.

# Answer
> 1 votes
# Prolog

```
areEqual(A, B) :-
    Amod = A,
    Bmod = B,

    Amod = Amod * A,
    Bmod = Bmod * B,

    Amod = Amod - B*B,
    Bmod = Bmod - B*B,

    Amod = Amod / (A-B),
    Bmod = Bmod / (A-B),

    Amod = Amod / A,
    Bmod = Bmod / A,

    Amod == Bmod.

```

The output when `areEqual(4,4)` is called (or any other couple of numbers really):

```
false

```

Why?

> In Prolog, the operator "=" is not affectation ; it's "Unification". Therefore `Amod = Amod * A` fails because `Amod`has already been unified with `A`, and thus cannot possibly be unified with `Amod * A`. Prolog then immediatly stops executing the current rule and returns `false`.

# Answer
> 0 votes
## Fantom

```
a := 3
b := 3
duplicates := [a:b]
duplicates = duplicates.map {it * a}
duplicates = duplicates.map {it - b*b}
duplicates = duplicates.map {it / a-b}
echo(duplicates.join("") |Int a_2, Int b_2 ->Str| {"" +  a_2 + " = " + b_2})

```

Output:

```
-3 = 3

```

Why?

> \[a:b\] is a map, not a list. Not so sneaky, I know :(

# Answer
> 0 votes
# C

Classic proof fallacy requires classic C syntax misunderstanding. Sadly I have met some "high-level-only" developers who are convinced C is broken because of results similar to this code. If you know how C works it becomes fairly obvious, but if you saw the code and assumed it was a different language, it might not be.

```
a,b,LHS,RHS;
main(){
    a=2; b=2;
    LHS=a; RHS=b;

    //multiply both sides by a
    LHS,RHS *= a;
    //subtract b squared from both sides
    LHS,RHS -= b*b;
    //assert that it factors correctly
    if (LHS,RHS != (a+b)*(a-b), b*(a-b)) printf("ERROR!\n");
    //'hard' division, just to be sure the compiler doesn't remove it
    LHS,RHS /=! (a-b);
    //assert that a+a really is b+b
    if (a+a != b+b) printf("ERROR!\n");
    //now just divide them by b
    printf("%d = %d ? ", LHS/b, RHS/b);
    if (RHS = LHS)
        printf("true!");
    else
        printf("false!");
}

```

Of course it doesn't work quite as well when written more idiomatically with `#include <stdio.h>` and int's thrown in front of the declarations.

---
Tags: popularity-contest, math, underhanded
---


title: Build a simple room in ASCII-art

text:
# Question
Title: Build a simple room in ASCII-art
A room can be made up of connected rectangles, for instance an L-shaped room. Such a room can be described by a list of dimensions describing the size of each rectangle.

Assume you have two input lists. The first contains the width of rectangles stacked vertically over each other. The second contains the height of the rectangles.

As an example, the input `[4 6][3 2]` will be a 4-by-3 rectangle on top of a 6-by-2 rectangle. The figure below shows this shape. Note that the walls are considered "thin", thus it's the spaces between the wall that's determined by the input.

```
[4 6][3 2]
 ____
|    |
|    |
|    |_
|      |
|______|

```

The challenge is: Take a list of dimensions as input, and output the shape of the room as ASCII-art. The format must be as in the sample figures:

* All horizontal walls are shown using underscores
* All vertical walls are shown using bars
* There shall be no walls where the rectangles are connected
* The left wall is straight
* For more details, have a look at the test cases

Assumptions you can make:

* All dimensions are in the range `[1 ... 20]`
    + All *horizonal* dimensions are even numbers
* The number of rectangles will be in the range `[1 ... 10]`
* Only valid input is given
* Optional input format (you can decide the order of the input dimensions, please specify in the answer).

**Test cases:**

```
[2][1]
 __
|__|

---

[4][2]
 ____
|    |
|____|

---

[2 6 2 4][2 2 1 3]
 __
|  |
|  |___
|      |
|   ___|
|  |_
|    |
|    |
|____|

---

[2 14 6 8 4 18 2 10 4 2][1 2 3 1 2 1 1 1 2 1]
 __
|  |___________
|              |
|       _______|
|      |
|      |
|      |_
|     ___|
|    |
|    |_____________
|   _______________|
|  |______
|     ____|
|    |
|   _|
|__|

```

# Answer
> 1 votes
# Retina, ~~169~~ ~~150~~ 113 bytes

Byte count assumes ISO 8859-1 encoding.

```
\d+
$*
{+r`1(1*¶[^|]*(1+))
$1¶|$2|
}` (¶.*) 1+
$1
1
_
(\|_+)\|(?=¶\1_(_+))
$1|$2
T`w` `(\|_+)_?(?=_*\|.*¶\1)
^¶

```

The code contains a trailing space on a trailing newline.

Input format:

```
Height (separated by spaces)
Width (also separated by spaces)
```

For example:

```
1 2 3 1 2 1 1 1 2 1
2 14 6 8 4 18 2 10 4 2
```

Try it online!

# Answer
> 4 votes
## Python 3, ~~230~~ ~~223~~ ~~222~~ 217 bytes

```
def f(a):b=a[0]+[0];m=' _';print('\n'.join([' '+'_'*b[0]+' ']+['|'+' '*min(b[l],b[l+1])+m[b[l+1]<1]*(b[l]>b[l+1])+m[k]*(b[l]-b[l+1]-1)+'|'+m[k]*(b[l+1]-b[l]-1)for l,i in enumerate(zip(*a))for k in[0]*(i[1]-1)+[1]]))

```

*Thanks to @StewieGriffin @KevinLau for their help*

## Results

```
>>> f([[2, 14, 6, 8, 4, 18, 2, 10, 4, 2],[1, 2, 3, 1, 2, 1, 1, 1, 2, 1]])
 __
|  |___________
|              |
|       _______|
|      |
|      |
|      |_
|     ___|
|    |
|    |_____________
|   _______________|
|  |_______
|     _____|
|    |
|   _|
|__|

```

# Answer
> 4 votes
# JavaScript (ES6) 174

The only critical part is the horizontal row joining 2 parts of different widths, with the vertical bar on right side that can be in the middle or at the right end.

```
(p,h,q=-1,R=(n,s=' ')=>s.repeat(n))=>[...p,0].map((x,i)=>(x>q?p=x:(p=q,q=x),(~q?`
|`+R(q+(x<p)-!x)+R(x>q,'|'):' ')+R(p+~q+!x,'_')+R(x<p,'|')+R(h[i]-1,`
|${R(q=x)}|`))).join``

```

**TEST**

```
f=(p,h,q=-1,R=(n,s=' ')=>s.repeat(n))=>[...p,0].map((x,i)=>(x>q?p=x:(p=q,q=x),(~q?`
|`+R(q+(x<p)-!x)+R(x>q,'|'):' ')+R(p+~q+!x,'_')+R(x<p,'|')+R(h[i]-1,`
|${R(q=x)}|`))).join``

// Less golfed

F=(p,h, q=-1,
   R=(n,s=' ')=>s.repeat(n)
  )=>
  [...p, 0].map((x,i)=> (
    x>q? p=x : (p=q,q=x),
    (q>=0?`\n|`+R(q+(x<p)-!x)+R(x>q,'|'):' ')
    + R(p+~q+!x,'_') + R(x<p,'|')
    + R(h[i]-1,`\n|${R(q=x)}|`)
  )).join``

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

;[
  [[2],[1]],
  [[4],[2]],
  [[2, 6, 2, 4],[2, 2, 1, 3]],
  [[2, 14, 6, 8, 4, 18, 2, 10, 4, 2],[1, 2, 3, 1, 2, 1, 1, 1, 2, 1]]
].forEach(t=>{
  var w=t[0],h=t[1]
  console.log('['+w+'] ['+h+']\n'+f(w,h)+'\n')
})
```

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

# Answer
> 3 votes
# Ruby 191

First time golfing, also it's my first day with Ruby, so it's probably not the most elegant thing in the world, but it'll do?

```
def f(x)
a=x[0]+[0]
puts" #{'_'*a[0]} "
for i in 0..x[1].length-1
n,m=a[i,2].sort
puts"|#{' '*a[i]}|\n"*(x[1][i]-1)+'|'+' '*n+(a[i+1]<1?'_':m>a[i]?'|':' ')+'_'*(m-n-1)+(n<a[i]?'|':'')
end
end

```

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


title: Make a Snake Parser!

text:
# Question
Title: Make a Snake Parser!
Snakes look like this:

```
      >>>v
@     ^  v
^  >>>^  v
^        v
^<<<<<<<<<

```

The snake can cross over itself as in this case:

```
 @
 ^
>^>v
 ^<<

```

For a crossover to be valid, the characters on either side must be moving the same direction. The case of

```
 @
>^v
 ^<

```

can be considered unclear and invalid.

The output is a string of `WASD` representing going from the head to the tail (`@`).

**Given a snake that doesn't backtrack and isn't ambiguous, can you write a program that will output the string of moves that the snake takes?**

This is code-golf, so shortest answer wins!

### Test cases:

<sub>(Note: The `@` can be replaced with any character not in `v^<>`)</sub>

**Input:**

```
>>>>v
    v
  v<<  @
  v    ^
  >>>>>^

```

**Output:** `ddddssaassdddddww`

---

**Input:**

```
@>>v
^  v
^  v
^<<<

```

**Output:** `dddsssaaawww`

---

**Input:**

```
>>>v
   v       @
   v       ^
   >>>>v   ^
       >>>>^

```

**Output:** `dddsssddddsddddwww`

---

**Input:**

```
@<< v
  ^ v
v<^<<
v ^
>>^

```

**Output:** `ssaaaassddwwwwaa`

---

**Input:**

```
@v<v
^v^v
^v^<
^<

```

**Output:** `ssawwasssawww`

# Answer
> 7 votes
## Java, ~~626~~ ~~539~~ ~~536~~ 529 bytes

*-87 bytes by saving a few in a lot of places. Thanks goes to Mr Public for pointing some out.*

*-3 bytes because I can't manage to remove all the spaces first try (thanks mbomb007)*

*+8 bytes to fix for this case:*

```
@v<v
^v^v
^v^<
^<

```

*-15 bytes by front-loading variable declaration*

```
s->{String o="",t;String[]p=s.split("\n");int h=p.length,w=p[0].length(),y=0,x,b=0,a,n,m;char[][]d=new char[h][w];for(;y<h;y++)for(x=0;x<w;x++){d[y][x]=p[y].charAt(x);if(d[y][x]=='@')d[y][x]=' ';}for(;b<h;b++)for(a=0;a<w;a++){t="";x=a;y=b;n=0;m=0;while(!(y<0|y>h|x<0|x>w||d[y][x]==' ')){if(y+m>=0&y+m<h&x+n>=0&x+n<w&&d[y+m][x+n]==d[y-m][x-n])d[y][x]=d[y-m][x-n];n=m=0;switch(d[y][x]){case'^':t+="W";m--;break;case'<':t+="A";n--;break;case'v':t+="S";m++;break;case'>':t+="D";n++;}x+=n;y+=m;}o=t.length()>o.length()?t:o;}return o;}

```

Readable version:

```
static Function<String,String> parser = snake -> {
    // declare all variables in one place to minimize declaration overhead
    String output = "", path;
    String[] split = snake.split("\n");
    int h=split.length, w=split[0].length(), y=0, x, startY=0, startX, dx, dy;
    char[][] board = new char[h][w];
    // setup char[][] board
    for (; y<h; y++)
        for (x=0; x<w; x++) {
            board[y][x]=split[y].charAt(x);
            if(board[y][x]=='@')board[y][x]=' ';
        }
    // find the longest possible path
    for (; startY<h; startY++)
        for (startX=0; startX<w; startX++) {
            path = "";
            x=startX; y=startY; dx=0; dy=0;
            while (!(y<0 | y>h | x<0 | x>w || board[y][x] == ' ')) {
                if (y + dy >= 0 & y + dy < h & x + dx >= 0 & x + dx < w
                        && board[y + dy][x + dx] == board[y - dy][x - dx]) {
                    board[y][x] = board[y - dy][x - dx];
                } dx = dy = 0;
                switch(board[y][x]) {
                    case '^':path+="W";dy--;break;
                    case '<':path+="A";dx--;break;
                    case 'v':path+="S";dy++;break;
                    case '>':path+="D";dx++;break;
                }
                x+=dx; y+=dy;
            }
            output = path.length()>output.length()?path:output;
        }
    return output;
};

```

Takes a String like `v @\n>>>^`. Creates a path starting at each coordinate, then returns the longest one. The lookahead required for the overlapping paths was the hardest part.

# Answer
> 2 votes
# Ruby, 217

```
->a{r=''
z=a.index ?@
a.tr!('<^>v',b='awds').scan(/\w/){c=0
e,n=[a[z,c+=1][?\n]?p: c,d=c*a[/.*
/].size,a[z-c,c][?\n]?p: -c,-d].zip(b.chars).reject{|i,k|!i||a[v=i+z]!=k||0>v}.max_by{|q|q&[a[z]]}until n
z+=e
r=n*c+r}
r}

```

This starts at the `@` and walks backwards, looking for neighbors that point to the current position (`z`). In order to choose the right way at 4-way intersections, it favors neighbors pointing in the same direction (`max_by{...}`). If no immediate neighbors are found, it assumes that there must have been a cross-over and reaches out one level at a time until it finds one (`until n` and `c+=1`). This process repeats for the number of body segments (not including the head) (`.scan(/\w/){...}`).

The test case I added to the puzzle kept tripping me up, so I went form 182 char to 218. Those extra characters were all making sure my horizontal moves didn't go into the next/prev lines. I wonder if I can deal with that in a better way.

## Ungolfed:

```
f=->a{
  result=''
  position=a.index ?@ # start at the @
  a.tr!('<^>v',b='awds') # translate arrows to letters
  a.scan(/\w/){           # for each letter found...
    search_distance=0
    until distance
      search_distance+=1
      neighbors = [
        a[position,search_distance][?\n]?p: search_distance,  # look right by search_distance unless there's a newline
        width=search_distance*a[/.*\n/].size,   # look down (+width)
        a[position-search_distance,search_distance][?\n]?p: -search_distance, # look left unless there's a newline
        -width                  # look up (-width)
      ]
      distance,letter = neighbors.zip(b.chars).reject{ |distance, letter_to_find|
        !distance || # eliminate nulls
         a[new_position=distance+position]!=letter_to_find || # only look for the letter that "points" at me
         0>new_position # and make sure we're not going into negative indices
       }.max_by{ |q|
        # if there are two valid neighbors, we're at a 4-way intersection
        # this will make sure we prefer the neighbor who points in the same
        # direction we're pointing in.  E.g., when position is in the middle of
        # the below, the non-rejected array includes both the top and left.
        #   v
        #  >>>
        #   v
        # We want to prefer left.
        q & [a[position]]
        # ['>',x] & ['>'] == ['>']
        # ['v',x] & ['>'] == []
        # ['>'] > [], so we select '>'.
       }
    end
    position+=distance
    result=(letter*search_distance)+result # prepend result
  }
  result # if anyone has a better way of returning result, I'm all ears
}

```

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


title: Draw a Spinning Pinwheel

text:
# Question
Title: Draw a Spinning Pinwheel
Remember those fun pinwheels that you blow on and they spin round and round? Let's code one!

A pinwheel will have the set of characters `\ | / _` drawing its center and arms. One possible pinwheel could look like this:

```
    |
    |
    |_ ___
 ___|_|
      |
      |
      |

```

But what's a pinwheel that doesn't spin? No fun! We can make it spin by rearranging the symbols:

```
      /
\    /
 \  /
  \/\
   \/\
   /  \
  /    \
 /

```

The challenge is to create a program that takes three integers and outputs a pinwheel as specified below. The first of these is the number of arms it has, the second is the length of the pinwheel's arms, and the third is the number of times it will spin one-eighth of a revolution clockwise.

You can assume the following:

* The number of arms will always be 0, 1, 2, 4, or 8.
* All the arms will be equally spaced apart from each other.
* The initial position of the pinwheel will have its center like this:

```
 _
|_|

```
* If the number of arms is 1, you may decide which direction the arm points.
* If the number of arms is 2, you may decide to make the arms point vertically or horizontally.

You can write a full program that takes input through STDIN or command-line argument, or a function that takes input through function arguments. Your program must show a sequence of outputs that shows the pinwheel spinning, each separated by at least one empty line. The center of the pinwheel should not move by more than one space. You may output as many leading and trailing spaces as necessary.

Here are some examples:

0 2 1

```
 _
|_|

/\
\/

```

1 3 2

```
|
|
|_
|_|

   /
  /
 /
/\
\/

 _ ___
|_|

```

2 2 0

```
   _ __
__|_|

```

8 4 1

```
 \   |    /
  \  |   /
   \ |  /
    \|_/____
 ____|_|
     / |\
    /  | \
   /   |  \
  /    |   \

     |   /
 \   |  /
  \  | /
   \ |/
____\/\____
     \/\
     /| \
    / |  \
   /  |   \
  /   |

```

This is code golf, so shortest code wins. Good luck!

# Answer
# Python 2 ~~535 517 473~~ 468 bytes

Saved 5 bytes thanks to @Easterly Ink!

Input expected to be comma separated (i.e., numArms,armLength,numRots)

## Golfed Version

```
n,l,t=input()
b=[7,3,1,5,0,4,2,6][:n]
w=5+2*l
h=w-3
X=w/2
Y=h/2-1
z=range
d=[0,1,1,1,0,-1,-1,-1]
for j in z(t+1):
 g=[[' 'for _ in[1]*w]for _ in[1]*h];a=j%2;b=[(k+1)%8for k in b];print''
 if a:g[Y][X:X+2]='/\\';g[Y+1][X:X+2]='\\/'
 else:g[Y][X+1]='_';g[Y+1][X:X+3]='|_|'
 for k in b:k=k+8*a;x=[0,2,3,3,2,0,-1,-1,0,1,2,2,1,0,-2,-1][k]+X;y=[0,0,0,2,2,2,1,0,-1,-1,0,1,2,2,0,0][k]+Y;exec"g[y][x]='|/_\\\\'[k%4];x+=d[k%8];y+=d[(k-2)%8];"*l
 for k in z(h):print''.join(g[k])

```

## Ungolfed Version

```
numArms, armLength, rotAmount = input()

# Choose which arms to draw
arms = [0,4,2,6,1,5,3,7][:numArms]
for i in xrange(rotAmount+1):

    # Set up the grid spacing
    maxWidth = 5 + 2 * armLength
    maxHeight = 2 + 2 * armLength
    grid = [[' ' for x in xrange(maxWidth)] for y in xrange(maxHeight)]

    # Add the base square
    angle = i%2
    startX = len(grid[0])/2
    startY = len(grid)/2 - 1
    if angle:
        grid[startY][startX:startX+2] = '/\\'
        grid[startY+1][startX:startX+2] = '\\/'
    else:
        grid[startY][startX+1] = '_'
        grid[startY+1][startX:startX+3] = '|_|'

    for armNum in arms:
        # Determine where this arm starts
        armIdx = armNum + 8*angle;
        armX = [0,2,3,3,2,0,-1,-1,0,1,2,2,1,0,-2,-1][armIdx] + startX
        armY = [0,0,0,2,2,2,1,0,-1,-1,0,1,2,2,0,0][armIdx] + startY

        # Determine the direction it travels
        d = [0,1,1,1,0,-1,-1,-1]
        dirX = [0,1,1,1,0,-1,-1,-1][armIdx%8]
        dirY = [-1,-1,0,1,1,1,0,-1][(armIdx)%8]
        sym = '|/_\\'[armIdx%4]

        # Draw the arm
        for i in xrange(armLength):
            grid[armY][armX] = sym
            armX += dirX
            armY += dirY

    # Increment which arms to draw next
    arms = [(a+1)%8 for a in arms]
    for i in xrange(len(grid)):
        print ''.join(grid[i])
    print ''

```

## Explanation

Pretty simple when it's broken down. First figure out how big of grid is required, then plot the base square or diamond.

Each arm's starting location, symbol and direction is hardcoded in for each of the 8 possible arms for the square and diamond base. Then, drawing them is easy enough.

To rotate everything, I simply switch between the square and diamond base, then increment each of the arms, rotating them clockwise once.
> 4 votes

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


title: Print arrays from the middle out

text:
# Question
Title: Print arrays from the middle out
This is a code-golf question.

Given integers s and n the task is to output all arrays of length n which take values from -s to s. The only twist is that you must output them in the following order.

* The all zeros array of length n.
* All arrays of length n with elements from -1 to 1 excluding any array you have outputted before.
* All arrays of length n with elements from -2 to 2 excluding any array you have outputted before.
* And so on until you get to all arrays of length n with elements from -s to s excluding any array you have outputted before.

You should output one array per line. They can be space or comma separated.

Here is some non-complying python code that outputs the arrays/lists/tuples in the right order.

```
import itertools

s =  3
n = 2

oldsofar = set()
newsofar = set()
for i in xrange(s):
    for k in itertools.product(range(-i,i+1), repeat = n):
        newsofar.add(k)
    print newsofar - oldsofar
    oldsofar = newsofar.copy()
    print "***"

```

Extra glory (and an upvote from me) for answers that perform no set subtraction or equivalent.

# Answer
> 6 votes
# Jelly, 9 bytes

```
NRṗµAṀ€Ụị

```

No list subtraction was used in the making of this post. Try it online!

### How it works

```
NRṗµAṀ€Ụị  Main link. Arguments: s, n

N          Negate; yield -s.
 R         Range; yield [-s, ..., s].
  ṗ        Cartesian power; push all vectors of length n of those elements.
   µ       Begin a new, monadic link. Argument: L (list of vectors)
    A      Compute the absolute values of all vector components.
     Ṁ€    Get the maximum component of each vector.
       Ụ   Sort the indices of A according to the maximal absolute value of the
           corresponding vector's components.
        ị  Retrieve the vectors of A at those indices.

```

# Answer
> 6 votes
# MATL, 18 bytes

```
_G2$:iZ^t!|X>4#SY)

```

First input is `s`, second is `n`

This works in current version (15.0.0) of the language.

**Try it online!**

### Explanation

```
_      % take input s implicitly. Negate to obtain -s
G      % push input s again
2$:    % inclusive range from -s to s
i      % take input n
Z^     % Cartesian power. Gives 2D array, with each result on a row
t!     % duplicate and transpose
|      % absolute value
X>     % maximum of each column
4#S    % sort and push the indices of the sorting
Y)     % apply as row indices into the 2D array. Display implicitly

```

# Answer
> 4 votes
## Haskell, ~~61~~ 60 bytes

```
n#s=[c|b<-[0..s],c<-mapM id$[-b..b]<$[1..n],any((b==).abs)c]

```

Usage example: `2#2`-\> `[[0,0],[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1],[-2,-2],[-2,-1],[-2,0],[-2,1],[-2,2],[-1,-2],[-1,2],[0,-2],[0,2],[1,-2],[1,2],[2,-2],[2,-1],[2,0],[2,1],[2,2]]`.

How it works:

```
   b<-[0..s]                           -- loop b through 0 .. s
        c<-mapM id$[-b..b]<$[1..n]     -- loop c through all lists of length n
                                       -- made out of the numbers -b .. b
                                       -- ("[-b..b]<$[1..n]" is "replicate n [-b..b]";
                                       --  "mapM id" is "sequence")
[c|                 ,any((b==).abs)c]  -- keep c if it contains b or -b

```

Edit: @xnor pointed out that `mapM id` is `sequence`.

# Answer
> 2 votes
# Mathematica, 83 bytes

```
Print/@Select[Range[-#,b=#]~Tuples~a,Abs@#~MemberQ~b&]&/@Range[0,a=Input[];Input[]]

```

To use, put in a script and input `n` then `s` on separate lines. Prints each array as a curly-bracketed, comma-delimited list (e.g., `{-1, 0, 1}`). It works by taking every list of length `n` with numbers between `[-cur..cur]`, and and printing those which include either `-cur` or `cur`. It then repeats this for all `cur` in `[0..s]`. <sup>(This post contains 19 \` characters!)</sup>

# Answer
> 1 votes
## JavaScript (SpiderMonkey 30+), 134 bytes

```
(s,n)=>n?[for(a of f(s,n-1))for(i of Array(s*2+1).keys())[i-n,...a]].sort((a,b)=>g(a)-g(b),g=a=>Math.max(...a,-Math.min(...a))):[[]]

```

Uses the cartesian-power-and-sort approach, which I thought of separately, but I was recompiling SpiderMonkey at the time so I unable to answer this before @Dennis.

---
Tags: code-golf, array
---


title: Graph an equation!

text:
# Question
Title: Graph an equation!
Please note that this question is different from this question. This one asks for graphical output, while the other one asks for ascii art.

# Objective

Help! Timmy's graphing calculator broke! His calculator cannot graph anymore. However, he has found a way to add new programs and functions to his calculator. Your job is to write a program/function that graphs equations.

# Rules

* Your program/function should take in a string in the form of `"y = random equation involving x"` and graph it on the coordinate grid.
* Timmy's calculator doesn't have that much memory, so please try to make your code as short as possible.
* The operations needed are addition (`+`), subtraction (`-`), multiplication (`*`), division (`/`), exponentiation(`^`) and grouping(`()`)
* Your program/function should be able to graph from `x=-5` to `x=5`, and from `y=-5` to `y=5`.
* Color, axis labels, the grid, numbers, scale, and animation are optional.
* The minimum size of the image should be 50x50 pixels.

# Test Cases

### Input

`y = x ^ 2`

### Output

### Input

`y = 4 * x + 3`

### Output

Standard loopholes apply.

You may change the operators, but it adds +10% to your byte count.

# Answer
# Matlab, 35 bytes

```
ezplot(input(''));axis([-5 5 -5 5])

```

Input is a string like `'y=2*x^2'`.
> 1 votes

# Answer
# Mathematica, ~~89~~ 77 bytes

```
Plot[ToExpression[#~StringDrop~4],{x,-5,5},PlotRange->{-5,5},AspectRatio->1]&

```

Most of it is just formatting to make it look similar to the examples. Please inform me if something isn't required. Includes axis markers, which aren't explicitly disallowed.
> 0 votes

# Answer
# MATL, 40 * 1.1 = 44

```
K0h)5:p'(-5:.1:5)'XHYXUHUw2$XG-5,5hth1ZG

```

This works in current version (15.0.0) of the language. *EDIT (June 15, 2017): You can try it at **MATL Online!***

`.*`, `./` and `.^` are for multiplication, division and power (that is, add a dot in front).

The following shows an example result running on Matlab.
> 0 votes

# Answer
# RPL/2 15\*1.1 = 16.5

```
STEQ .5 *S DRAW

```

Timmy must key in the equation in capitals, e.g.'Y = X ^ 3', hence the 10% penalty.

The .5 is just luck: the default box is -10…10 × -10…10 with RPL/2.
> 0 votes

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


title: Walking on the Hypercube

text:
# Question
Title: Walking on the Hypercube
I recently read up on graph theory, especially hypercubes and thought about interesting ways to construct paths on them. Here's what I came up with.

As you might know, you can construct an n-dimensional hypercube by taking all n-tuples consisting of `1` and `0` as vertices and connect them, iff they differ in one digit. If you interpret these binary digits as an integer number, you end up with a graph with nicely numerated vertices. For example for `n=3`:

Let's say you want to take a walk on this hypercube and start at the vertex `0`. Now, how do you determine which vertex you want to visit next? The rule I came up with is to take the number `a` of the vertex you are on, flip its `mod(a,n)`s bit (zero-based indexing) and go to the resulting vertex. Formally this rule can be recursively defined as

```
a[m+1] = xor(a[m], 2^mod(a[m],n)).

```

By following this rule, you will always stay on the cube and travel along the edges. The resulting path looks like this

As you can see, you will walk in a circle! In fact, in all dimensions and for all starting points your path will end up in a loop. For example for `n=14` and `a[0]=0` it looks like this

For the avid ambler, the length of his planned route is quite a crucial information. So, your job is to write a function or a program that takes the hypercube dimension `n` an the starting vertex `a[0]` as inputs and output the number of vertices in the resulting loop.

## Test cases

```
n   a[0]   Output
-----------------
3   0      6
14  0      50
5   6      8
17  3      346

```

## Rules

* Standard loopholes are forbidden
* Output/Input may be in any suitable format
* You may assume `a[0]` to be a valid vertex

## Scoring

Shortest code in bytes wins.

If you have any additional information on this topic, I'd be glad to hear!

# Answer
> 4 votes
# Jelly, 9 bytes

```
%⁴2*^µÐḶL

```

Takes two command-line arguments.

```
%⁴2*^µÐḶL        A monadic link. Inputs: a_0. b also taken from command line.
%⁴2*^              Variadic link. Input: a
%⁴                   a modulo b. ⁴ is second input, b.
  2*                 Get 2 to that power
    ^                and bitwise xor with a.
     µ             Start a new, monadic link (input: a_0)
      ÐḶ             All elements of the cycle created when the preceding link
                     is applied repeatedly, starting with a_0.
        L            Length.

```

Try it here.

# Answer
> 2 votes
# Haskell, 124

```
import Data.Bits
(y:z:w)%(x:s)|x==y||x==z=[i|(i,r)<-zip[1..]s,r==x]!!0|0<1=w%s
g n=(tail>>=(%)).iterate(\a->xor a$2^mod a n)

```

This finds the circle by the two-pointers-going-around-in-different-speeds algorithm, and heavily uses/abuses Haskell's approach to lists (for example, the two pointers are actually lists).

`g` is the function that computes the answer. give it `n` and then `a[0]` and it will return the number to you (note that `n` should be defined to be of type `Int` to avoid type ambiguity).

# Answer
> 1 votes
# MATL, ~~38~~ ~~37~~ 28 bytes

```
xi`vt0)2y1G\^Z~yywP=fn~]2M1$

```

This works in current version(15.0.0) of the language.

**Try it online**!

### Explanation

```
x       % take first input: n. Delete (gets copied into clipboard G)
i       % take second input: initial value of a
`       % do...while loop
  v     %   concatenate all stack contents vertically
  t0)   %   duplicate. Get last element of that array: current a
  2     %   push 2
  y     %   duplicate second-top element in stack: current a
  1G    %   push first input (n)
  \     %   a modulo n
  ^     %   2 raised to that
  Z~    %   xor of that with current a
  yy    %   duplicate top two elements in stack: array of old a's and new a
  w     %   swap: move array of old a's to top
  P     %   reverse that array. So first entry is most recent a (before current)
  =f    %   indices of old values that equal current value. There may be 0 or 1
  n~    %   is it empty?
]       % if so, continue with a new iteration
2M      % push array of indices. It contains exactly 1 index
1$      % set 1 input for implicit display function, so it only displays the index

```

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

```
(n,a)=>{g=m=>m^1<<m%n;for(c=1,b=a;(b=g(g(b)))!=(a=g(a));)c++;return c}

```

Returns 18812 for (23, 10).

# Answer
> 1 votes
## Pyth, ~~22~~ 17 bytes

```
Lx^2%bQbl.uyNuyGE

```

Explanation:

```
Lx^2%bQbl.uyNuyGE     Implicit: Q=first line n. E=second line a[0].
Lx^2%bQb              y = lambda b: do one iteration
                      Then
             uyGE     Apply y until a previous result is found.
                      This makes sure we're in the cycle.
         .uyN         Then apply y again until a previous result is found.
                      Keep all intermediate values but not the repeat.
        l             Get the length; i.e. the length of the cycle.

```

Try it here.

---
Tags: code-golf, graph-theory
---


# Question
Title: Use all your language's keywords, ideally minimally
* Your program must contain all your language's keywords. Ideally, you should have each one exactly once (see Scoring). Of course, this means your language must actually have keywords, so esoteric languages are probably excluded, but just in case...
* Any language used must have a dedicated Wikipedia article created more than one month ago.
* The keywords in your program must be lexed as keywords and parsed as keyword statements or expressions (i.e. no containing them within strings or comments).

A "keyword" is defined according to the language's specification or documentation if it has no specification, and must additionally have a defined purpose within the language (Java programmers need not include `goto` and `const`). Your language might distinguish "keywords" from "reserved identifiers" or something similar; only those lexemes designated as keywords are required.

# Scoring

So as not to punish languages with more keywords, your score is

`l - k + 3r`

Where l is the length of your program in bytes, k is the combined length of all the keywords you used, and r is the combined length of any keywords that occurred more than once. So if your language has only one keyword, `for`, and your solution is `for for for`, your score is 11 - 9 + 3(6) = 20.

# Answer
# Python 3.4, 110

```
from os import*
def k(z):
 def c():return None;nonlocal z
class F:pass
global b
with open(devnull)as b:
 while b:
  if 1and 0is 0:continue
  elif 1:0
  else:
   for d in[]:yield not d;del d;break
 try:raise 1or False
 except:assert True
 finally:(lambda j:0)

```

Uses every keyword once. Note, in Python 3, `exec` and `print` are functions, not keywords.
> 6 votes

# Answer
# Brainfuck, 0

```
+-[]><,.

```

Score:

```
l = 8
k = 8
r = 0

l - k + 3r = 0

```

This program takes an input from the user and then prints it.
> 3 votes

---
Tags: code-challenge
---


title: Sort a nested list

text:
# Question
Title: Sort a nested list
You must write a program or function that sorts a nested list. Here are the rules for sorting a nested list:

Let's take this list as an example:

```
((5, 2), 2, 7, (2, 1, (3, 4)), 9)

```

Each element in this list has a "priority". An element counts as a number or a sublist. First, get the priority of each element at the same depth. If an element is just a number, its priority is the same as the number itself. If an element is a sublist, its priority is the sum of all the *numbers* in it, not including any sub-sublists.

So, the priorities of all the elements of depth **1** are:

```
 (  7 )  2  7  (    3       )  9
((5, 2), 2, 7, (2, 1, (3, 4)), 9)

```

Sort each element by priority. If there is a tie, you must keep the same order as the original list.

```
 2  (     3      )  (  7 )  7  9
(2, (2, 1, (3, 4)), (5, 2), 7, 9)

```

Repeat for every sublist. So on this sublist

```
(2, 1, (3, 4))

```

Our priorities look like:

```
 2  1  (  7  )
(2, 1, (3, 4))

```

So sorted, it looks like:

```
(1, 2, (3, 4))

```

`(3, 4)` is already sorted, so we're done. Repeat for `(5, 2)` which results in `(2, 5)` and we're done! Our final list is:

```
(2, (1, 2, (3, 4)), (2, 5), 7, 9)

```

# Rules:

* Highly doubtful, but just in case Mathematica has something for this, no nested list sorting builtins are allowed. Regular sorting functions *are* allowed.
* I/O can be in any reasonable format.
* Every sublist will contain at least one number or list. Also, sublists can be nested several levels deep. For example, in `(1, 2, (((3))))` the `(((3)))` has a priority of 0, since it has only sublists in it.
* Invalid lists (unmatched parentheses, non-numbers, wrong bracket types, negative numbers, etc.) result in undefined behavior.

# Test I/O:

```
(1, 2, 3) ---> (1, 2, 3)

(1, 2, 6, 3, 9, 8) ---> (1, 2, 3, 6, 8, 9)

(4, 3, (2), (1)) ---> ((1), (2), 3, 4)

(4, 3, (2), ((1))) ---> (((1)), (2), 3, 4)

(5, (1, 2, (9, 8))) ---> ((1, 2, (8, 9)), 5)

(3, (1, 2), (2, 1)) ---> (3, (1, 2), (1, 2))

(3, (1, 2, (99)), (2, 1, (34))) ---> (3, (1, 2, (99)), (1, 2, (34)))

(7, 2, (1, (9, 12)), (4, 3, 2, (1, 2))) ---> ((1, (9, 12)), 2, 7, (2, 3, (1, 2), 4))

```

Shortest answer in bytes wins.

# Answer
# Jelly, 13 bytes

```
fFSµ€Ụịß€µ¹<?

```

Try it online! or verify all test cases.

### How it works

```
fFSµ€Ụịß€µ¹<?  Main link. Input: A (list)

   µ€          Apply the chain to the left to each item B in A.
 F             Flatten B.
f              Filter; intersect B with flattened B, yielding a list.
               This returns the numbers in B if B is a list, [B] if B is a number.
  S            Compute the sum of the resulting list.
     Ụ         Sort the indices of A according to the computed sums.
       ß€      Recursively apply the main link to each B in A.
      ị        Retrieve the items of the list (right) at those indices (left).
         µ     Convert the preceding chain into a single link.
            ?  If:
           <     A compared with itself is truthy:
                   Execute the link to the left.
          ¹      Else, apply the identity function to A.

```

Comparing (`<`) a number with itself yields **0** (falsy), but comparing a non-empty list with itself yields a list of **0**'s (truthy), so `<` can be used to distinguish numbers from lists.
> 6 votes

# Answer
# Python 2, ~~114~~ ~~101~~ ~~78~~ ~~73~~ 62 bytes

```
k=lambda t:t*(t<[])or t.sort(key=k)or sum(z for z in t if[]>z)

```

I *knew* there was a better way to filter lists out.

Sorts a python list (and its sublists) in-place.

https://eval.in/540457 thanks @tac for letting me know in-place solutions are acceptable, and @xnor + @feersum for further optimizations!
> 17 votes

# Answer
# Lua, 172 bytes

```
function p(a)if type(a)~="table"then return a end s(a)local t=0 for i,v in next,a do t=t+p(v)end return t end
function s(t)table.sort(t,function(a,b)return p(a)<p(b)end)end

```

The function `s` sorts a Lua table (a data structure that serves as a list among other things in Lua) in place according to the rules.
> 4 votes

# Answer
# Mathematica, 50 bytes

```
#0/@SortBy[#,Tr@Cases[#,_Integer,{0,1}]&]~Check~#&

```

Simple recursive method that uses `SortBy`. Ignore the messages.
> 3 votes

# Answer
**Haskell, ~~160~~ ~~151~~ 135 bytes**

```
import Data.List
data T=N Int|T[T]deriving Show
p(N x)=x
p(T t)=sum$[x|N x<-t]
f(N x)=N x
f(T t)=T$sortBy((.p).compare.p)$map f$t

```

The first problem is nested lists. Haskell requires that all elements of a list have the same type; in particular, an integer and a list of integers aren't the same type. In other words, a variable-nested list *isn't a list, it's a rose tree!*

So first, we have to define a data type for rose trees:

```
data T = N Int | T [T]

```

(Strictly, `deriving Show` is only necessary if you want to *see* the results. But that's a technicality.) With this definition in place, we can write a list such as `(1, 2, (3, 4))` as

```
T [N 1, N 2, T [N 3, N 4]]

```

which is considerably less readable. But whatever; it's a trivial, mechanical translation. Prefix every number with `N` and every subtree with `T`.

Now we need to compute priorities. This would be easy if the priority of a subtree was simple the sum of *all* elements it contains. That would be a trivial recursive loop. But since it isn't, we need to define *two* functions: one which recurses, and one which does not.

```
p (N x) = x
p (T t) = sum $ map q t

q (N x) = x
q _     = 0

```

If we were to sum *all* subelements, then `q` would not need to exist, saving a huge number of characters. Oh well!

Edit: Actually, several commentors point out that you can avoid `q` using a list comprehension: `[ x | N x <- t]`. Good call, guys!

(In fact, `p` would not need to exist either; we could have the compiler auto-generate an `Ord` instance for us in a handful of characters, and this default implementation would match the spec.)

Finally, we need to recursive over all sub-trees and sort them:

```
f (N x) = N x
f (T t) = T $ sortBy (\ x y -> compare (p x) (p y)) $ map f $ t

```

That is, `f` sorts a tree by recursively applying itself to all elements (`map f`), and then calling the `sortBy` function to sort the top-level. The first line says that sorting a number does nothing, and is necessary to terminate the recursion.
> 3 votes

# Answer
# CLISP, 380 bytes

```
(defun q(L)(if(null L)L(append(append(q(car(s(cdr L)(car L))))(list(car L)))(q(cadr(s(cdr L)(car L))))))))(defun s(L E)(if(not(atom(car L)))(setq L(cons(q(car L))(cdr L))))(cond((null L)'(nil nil))((<(v(car L))E)(list(cons(car L)(car(s(cdr L)E)))(cadr(s(cdr L)E))))(T(list(car(s(cdr L)E))(cons(car L)(cadr(s(cdr L)E)))))))(defun v(L)(if(atom L)L(apply'+(remove-if-not #'atom L))))

```

Call the function q with a list.

I'm a lisp noob, please don't kill me^^
> 2 votes

# Answer
# Pyth, 15 bytes

```
L?sIbbossI#NyMb

```

Test suite

A recursive function, that works as follows:

```
L?sIbbossI#NyMb
L                  define y(b):
 ?sIb              If b is an integer:          (invariant under the s function)
     b             Return it.
            yMb    Else, apply y recursively to all of the elements of b,
      o            Then sort b by
        sI#N       For each element, the elements of that list that are integers.
                   This is luckily a nop on integers.
       s           Summed.

```
> 1 votes

# Answer
# Java, 219 bytes

```
import java.util.*;List f(List l){l.sort(Comparator.comparing(o->{if(o instanceof Integer)return(Integer)o;f((List)o);return((List) o).stream().filter(i->i instanceof Integer).mapToInt(i->(Integer)i).sum();}));return l;}

```

With line breaks:

```
import java.util.*;
List f(List l){
    l.sort(Comparator.comparing(o -> {
        if (o instanceof Integer)
            return (Integer) o;
        f((List) o);
        return ((List) o).stream().filter(i -> i instanceof Integer).mapToInt(i -> (Integer) i).sum();
    }));
    return l;
}

```

There's a lot of casting going on which really racks up the byte count. :P

Integer values are fed into a Comparator, and nested lists are sorted first before the sum of only the integer values are given to the Comparator. These values are how the Comparator determines their position within the list when it is sorted.

Try it here.
> 1 votes

# Answer
## JavaScript (ES6), 86 bytes

```
f=a=>a.map?a.map(f).sort((a,b)=>p(a)-p(b),p=a=>a.map?a.map(a=>t+=a.map?0:a,t=0)|t:a):a

```

All that array checking :-(
> 0 votes

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


title: There's an ant on my Rubik's Cube

text:
# Question
Title: There's an ant on my Rubik's Cube
A standard, solved, 3×3×3 Rubik's Cube has 6 differently colored faces, where each face is a 3×3 grid of squares of one color. The white face is opposite the yellow, the red opposite orange, the blue opposite green, and when white points upward, red is to the left of blue:

Imagine an ant sits on the center square of the white face, facing the red face. You can give him 3 commands:

* Forward (`^`) - take a step in the direction he's facing to the next grid square, stepping over an edge of the cube if necessary.
* Right (`>`) - rotate to the right (clockwise) by 90°, staying in the same grid square.
* Left (`<`) - rotate to the left (counter-clockwise) by 90°, staying in the same grid square.

Given an arbitrary list of commands, find the colors of the squares that the ant visits (not including the white starting square).

> For example, the command sequence `^^>^^<^^^` has a path that looks like this:
>
> The colors of the grid squares visited in order, not counting the starting square, are `white red red green green green yellow`, or just `wrrgggy`.

Write a program or function that takes in a string of the command characters `<^>` and prints or returns a string of the characters `wyrobg` (white, yellow, red orange, blue, green) that corresponds to the ant's path over the cube.

**The shortest code in bytes wins. Tiebreaker is earlier answer.**

## Notes

* The cube is in midair and the ant has effective pulvilli, so he can traverse the whole of the cube.
* The cube always remains in its solved state.
* A square's color is only recorded upon movement into the square, not rotation. The starting white square should not be recorded.
* A single optional trailing newline may be present in the input and/or output.

## Test Cases

```
input : output
```

```
[empty string] : [empty string]
^ : w
< : [empty string]
> : [empty string]
><><<<>> : [empty string]
>^ : w
<<^> : w
^<^<^<^< : wwww
^^ : wr
<^^ : wb
>><<<<^^ : wo
<^^^<^^^^<>^>^^>^ : wbbboooggyo
^^^^^^^^^^^^^^ : wrrryyyooowwwr
<<<^<^>^<^<^<^>^^^^<^>>>>>^^<^>^^<^>^>^>^>< : wwgrwgggoooobbbbyrby
^^>^^<^^^ : wrrgggy

```

# Answer
> 20 votes
# Perl, ~~156~~ ~~143~~ ~~134~~ ~~128~~ ~~127~~ ~~125~~ ~~120~~ ~~119~~ ~~117~~ ~~113~~ 109 bytes

Includes +1 for `-p`

Run with the control string on STDIN, e.g.

```
perl -p rubic.pl <<< "^^>^^<^^^"

```

`rubic.pl`:

```
@1=wryobg=~/./g;s##$n=w&$&;$y+=$x-=$y+=$x,@1[0,4,2,5,3,1]=@1while--$n%9;@{$n&&--$y%3}[3,0..2]=@1;$1[$n+9]#eg

```

## Explanation

Older version:

```
@f=gboyrw=~/./g;s##$n=w&$&;$y+=$x-=$y+=$x,@f=@f[2,4,1,3,0,5]while--$n%9;@f=@f[0,$y=1,5,2..4]if$n&&$y--<0;$f[$n+8]#eg

```

The challenge of this question is to find a coordinate system that makes it easy to track the position and direction of the ant and to still easily get the face identity.

The system I chose was to put standard `(x,y)` coordinates on the face the ant is on such that the ant is always facing in the negative `y` direction with the center of the face being `(0,0)`. So:

```
rotate right: (x',y') <- (-y,  x)
rotate left:  (x',y') <- ( y, -x)  alternatve: 3 right rotations
Step forward:   y' <- y-1

```

If `y` was already `-1` the ant will leave the current face and step onto the next one. In the new coordinate system there `x` keeps its value, but `y'` becomes 1.

This gives an easy coordinate system within a face. I also need something for the faces themselves. There I use an array consisting of

```
The face to right of the ant            g in the initial position
The face to the left of of the ant      b
The face behind the ant                 o
The face opposite to the ant            y
The face before the ant                 r
The face the ant is on                  w

```

So the initial array is `(g,b,o,y,r,w)`. Moving to the next face corresponds to rotating the last 4 elements, so moving from white to red makes this `(g,b,w,o,y,r)`. Turning right is a permutation of the first 5 elements giving `(o,r,b,y,g,w)`. Turning left is a simular permutation but can also be done by turning right 3 times, so applying this permutation 3 times. And not turning at all can also be done by applying the permutation 8 times. In fact turning right can also be done by applying the permutation 5 times.

Knowing this the program is rather simple:

```
@f=gboyrw=~/./g                 Set up the initial face orientation
s## ... #eg                     Process each control string character
                                {this is equivalent to s#.#...#eg because
                                the empty regex repeats the last
                                succesful regex)
$n=w&$&                         Calculate n, the number of right
                                rotations+1 modulo 9.
                                This abuses a coincidence of the control
                                characters:
                                 "<" & "w" = "4" -> 3 right rotations
                                 ">" & "w" = "6" -> 5 right rotations
                                 "^" & "w" = "V" = 0 but that is 9 mod 9
                                 so leads to 8 right rtations

$y+=$x-=$y+=$x,                 This is the same as ($x,$y)=(-$y,$x), so
                                a right rotation of the face coordinates
@f=@f[2,4,1,3,0,5]              Right rotation of the face array
   while --$n%9                 Rotate right n-1 times. After this n=0
                                If this was a step then n was effectively 0.
                                So rotate right 8 times leaving n=-9

    ... if $n                   If a step...
               $y--             ... decrease y ...
             &&$y--<0           ... but if y was already negative ...
@f=@f[0,$y=1,5,2..4]            ... change face and set y to 1

$f[$n+8]                        return the last element (current face)
                                if this was a step, otherwise empty

```

So for that last statement rotations lead to the empty string and steps forward lead to the current face. Therefore `$_` gets replaced by the faces visited on each step.

# Answer
> 13 votes
# Brachylog, 287 bytes

```
:1:2222:"w":"y":["r":"b":"o":"g"]{h""|[L:I:N:A:B:[C:D:E:F]]hhM("^",(NhI,CwX,EY,B:D:A:FZ;AwX,BY,[C:D:E:F]Z),NhJ,(I1,2313O;I2,(Nh2,N$($(O;Nh1,2222O;Nbh1,3223O;3322O);3322N,2332O;3223N,2233O;2233N,3132O;2332N,3231O);IJ,AX,BY,(M"<",[C:D:E:F]$(Z,N$(O;M">",[C:D:E:F]$)Z,N$)O)),Lb:J:O:X:Y:Z:1&}

```

Expects a string containing the moves as Input, and no Output, e.g. `brachylog_main("^^>^^<^^^",_).` will write `wrrgggy` to STDOUT.

### Explanation

```
§ There are 3 types of tiles we can be on: centers (noted 1), edges (2) and corners (3)
§ When we are on a tile, we can denote adjacent tiles in order: front, left, back, right
§ Similarly, we can denote the adjacent colors depending on the current one of the face
§
§ We start on the center (1) of face white ("w"). The adjacent tiles are 4 edges (2222)
§ The adjacent colors of white are red, blue, orange and green ("r":"b":"o":"g")
§ Yellow is opposite of white ("y")

§ We pass those initial conditions in an array, with the sequence of moves as first
§ element, as input to subpredicate 1

:1:2222:"w":"y":["r":"b":"o":"g"]{...}

§ SUB-PREDICATE 1

h""  § If the sequence of moves is empty, terminate the recursion
|    § Else...

§ Here are the variables' names of the input (which correspond to what's described in
§ the first few paragraphs)
[L:I:N:A:B:[C:D:E:F]]

§ If the move is "^"...
hhM("^",

   § The only way we change from one face to another is if the tile we end up on is of the
   § same type as the tile we started from
   (NhI,      § If this is the case
    CwX,      § Then write the color of the face we're facing, this face will now be the
              § current color
    EY,       § The third color in the list is now the opposite color
    B:D:A:FZ  § The opposite color is now the one we face, the color behind us (the third
              § in the list) is the one we were on, and the other 2 don't change

    § If the tiles are not the same type, then we don't change color
    ;
    AwX,         § Write the current color, this will remain the color
    BY,          § Opposite color stays the same
    [C:D:E:F]Z), § Other colors stay in the same order since we moved forward
    NhJ,              § The new tile type is the one we were facing
       (I1,2313O;     § If we were on the center, then the adjacent tiles are 2313
       I2,            § Else if we were on an edge
         (Nh2,N$($(O; § then if we were facing an edge (changed face), then the new types
                      § of tiles are a double circular permutation of the previous types
         Nh1,2222O;   § Else if we were facing a center, then the new tiles are 2222
         Nbh1,3223O;  § Else (corners) if the tile to our left is the center, then 3223
         3322O)       § Else 3322

       ;              § Else if we were on a corner
       3322N,2332O;   § then one of those 4 possibilities applies
       3223N,2233O;
       2233N,3132O;
       2332N,3231O)

§ Else if the move is NOT "^"
;
IJ,AX,BY,         § We stay on the same type of tile, same color, same opposite color
(M"<",            § if the move is "turn left"
    [C:D:E:F]$(Z, § Then we circular permute the adjacent colors to the left
    N$(O          § we also circular permute the adjacent tiles to the left
;M">",            § Else if the move is "turn right"
    [C:D:E:F]$)Z, § Then we do the same but with right circular permutations
    N$)O)
),
Lb:J:O:X:Y:Z:1&   § Recursively call sub-predicate 1 with the new input, and the next move

```

### Equivalent SWI-Prolog code

If you don't want to bother with Brachylog's compiler, you can run this solution in SWI-Prolog using the following code (this is what gets generated by Brachylog's compiler):

```
:- style_check(-singleton).

:- use_module(library(clpfd)).

brachylog_main(Input,Output) :-
    1=1,
    brachylog_subpred_1([Input,1,2222,"w","y",["r","b","o","g"]],V0).

brachylog_subpred_1(Input,Output) :-
    1=1,
    brachylog_head(Input, "").

brachylog_subpred_1(Input,Output) :-
    1=1,
    [L,I,N,A,B,[C,D,E,F]] = Input,
    brachylog_head([L,I,N,A,B,[C,D,E,F]], V0),
    brachylog_head(V0, M),
    ( 1=1,
    "^" = M,
    ( 1=1,
    brachylog_head(N, I),
    brachylog_write(C, X),
    Y = E,
    Z = [B,D,A,F]
    ;
    1=1,
    brachylog_write(A, X),
    Y = B,
    Z = [C,D,E,F]
    ),
    brachylog_head(N, J),
    ( 1=1,
    I = 1,
    O = 2313
    ;
    1=1,
    I = 2,
    ( 1=1,
    brachylog_head(N, 2),
    brachylog_math_circular_permutation_left(N, V1),
    brachylog_math_circular_permutation_left(V1, O)
    ;
    1=1,
    brachylog_head(N, 1),
    O = 2222
    ;
    1=1,
    brachylog_behead(N, V2),
    brachylog_head(V2, 1),
    O = 3223
    ;
    1=1,
    O = 3322
    )
    ;
    1=1,
    N = 3322,
    O = 2332
    ;
    1=1,
    N = 3223,
    O = 2233
    ;
    1=1,
    N = 2233,
    O = 3132
    ;
    1=1,
    N = 2332,
    O = 3231
    )
    ;
    1=1,
    J = I,
    X = A,
    Y = B,
    ( 1=1,
    "<" = M,
    brachylog_math_circular_permutation_left([C,D,E,F], Z),
    brachylog_math_circular_permutation_left(N, O)
    ;
    1=1,
    ">" = M,
    brachylog_math_circular_permutation_right([C,D,E,F], Z),
    brachylog_math_circular_permutation_right(N, O)
    )
    ),
    brachylog_behead(L, V3),
    brachylog_call_predicate([V3,J,O,X,Y,Z,1], V4).

brachylog_behead(X,Y) :-
    string(X),!,
    sub_string(X, 1, _, 0, Y)
    ;
    number(X),!,
    number_codes(X,[_|T]),
    catch(number_codes(Y,T),_,Y=[])
    ;
    atom(X),!,
    atom_codes(X,[_|T]),
    atom_codes(Y,T)
    ;
    X = [_|Y].

brachylog_math_circular_permutation_left(X,Y) :-
    string(X),!,
    string_codes(X,C),
    C = [H|T],
    append(T,[H],D),
    string_codes(Y,D)
    ;
    number(X),!,
    number_codes(X,C),
    C = [H|T],
    append(T,[H],D),
    number_codes(Y,D)
    ;
    atom(X),!,
    atom_codes(X,C),
    C = [H|T],
    append(T,[H],D),
    atom_codes(Y,D)
    ;
    X = [H|T],!,
    append(T,[H],Y).

brachylog_math_circular_permutation_right(X,Y) :-
    string(X),!,
    string_codes(X,C),
    append(T,[H],C),
    D = [H|T],
    string_codes(Y,D)
    ;
    number(X),!,
    number_codes(X,C),
    append(T,[H],C),
    D = [H|T],
    number_codes(Y,D)
    ;
    atom(X),!,
    atom_codes(X,C),
    append(T,[H],C),
    D = [H|T],
    atom_codes(Y,D)
    ;
    append(T,[H],X),
    Y = [H|T].

brachylog_call_predicate(X,Y) :-
    reverse(X,R),
    R = [N|RArgs],
    number(N),
    reverse(RArgs, Args),
    (
    N = 0,!,
    Name = brachylog_main
    ;
    atom_concat(brachylog_subpred_,N,Name)
    ),
    (
    Args = [UniqueArg],!,
    call(Name,UniqueArg,Y)
    ;
    call(Name,Args,Y)
    ).

brachylog_write(X,Y) :-
    X = [List,Format],
    is_list(List),
    string(Format),!,
    format(Format,List),
    flush_output,
    Y = List
    ;
    write(X),
    flush_output,
    Y = X.

brachylog_head(X,Y) :-
    string(X),!,
    sub_string(X, 0, 1, _, Y)
    ;
    number(X),!,
    number_codes(X,[A|_]),
    number_codes(Y,[A])
    ;
    atom(X),!,
    atom_codes(X,[A|_]),
    atom_codes(Y,[A])
    ;
    X = [Y|_].

```

# Answer
> 5 votes
# PowerShell, 882 bytes

**Usage**

Save the code in a script and call it like this from the command line. Assuming working directory is the current directory.

```
.\WalkingAntcg.ps1 "^^>^^<^^^"

```

**Code**

```
$o=[char[]]"grbowy";[int]$c=4;[int]$global:x=1;[int]$global:y=1;[int]$f=1;[int]$n=5;
$u={$c=$args[0];$1="341504251435240503210123".Substring($c*4,4);$2=$1*2-match".$($args[1]).";$3=$Matches[0];"$3";"012345"-replace([char[]]"$1$c"-join"|")}
function t{param($o,$x,$y)if($o){switch($y){0{switch($x){0{$x=2}1{$y=1;$x=2}2{$y=2}}}1{switch($x){0{$y=0;$x=1}2{$y=2;$x=1}}}2{switch($x){0{$x=0;$y=0}1{$x=0;$y=1}2{$x=0}}}}}else{switch($y){0{switch($x){0{$y=2}1{$x=0;$y=1}2{$x=0}}}1{switch($x){0{$y=2;$x=1}2{$y=0;$x=1}}}2{switch($x){0{$x=2}1{$x=2;$y=1}2{$y=0;$x=2}}}}}$global:x=$x;$global:y=$y}
([char[]]$args[0]|%{switch($_){'^'{$global:y++;if($global:y-eq3){$global:y=0;$c="$f";$f="$n";$z=&$u $c $f;$f,$n="$($z[0][1])","$($z[1])"}$o[$c]}
"<"{$z=&$u $c $f;$f,$n="$($z[0][0])","$($z[1])";t 0 $global:x $global:y}
">"{$z=&$u $c $f;$f,$n="$($z[0][2])","$($z[1])";t 1 $global:x $global:y}}})-join""

```

**Less golfed code with explanation**

```
# Recorded order of cube colours and their indexes
# Green=0,Red=1,Blue=2,Orange=3,White=4,Yellow=5
$o=[char[]]"grbowy"
[int]$c=4   # Ant is currently on this colour
[int]$global:x=1   # X coordinate on this face
[int]$global:y=1   # Y coordinate on this face
[int]$f=1   # Colour that the Ant is facing
[int]$n=5   # Colour beyond that the ant is facing.
# If the ant moves of this cube to the next this value becomes the one he is facing.
# It is also the only colour not neighboring this current colour.

# Anonymous function that will return the colour facing left and right
$u = {
# Cube relationships relative to position. Groups of 4 colours that are important given the order...
# Green=0-3,Red=4-7,Blue=8-11,Orange=12-15,White=16-19,Yellow=20-23
# Get the colours surrounding the current colour we are on and the surrounding ones
# String version: "owrygwbyrwoybwgygrbogrbo"
$c=$args[0]
#  "341504251435240501230123"
$1="341504251435240503210123".Substring($c*4,4)
# double the string so that we can get the characters before and after the facing colour reliably
# Assign the output to surpress a boolean. $2 is not used. Shorter than a cast
$2=$1*2-match".$($args[1]).";$3=$Matches[0]
# Return two values. First is the colours to the left,current and right as a string.
# Second is the colour beyond the one we are facing. If we were to move forward two blocks
# we would end up on this colour
"$3";"012345"-replace([char[]]"$1$c"-join"|")
}

# function that will transpose the ants position based on right/left rotation.
# Using current x and y determines what the tranposed values are and return them.
function t{
    param($o,$x,$y)
    # X = $1; Y = $2
    # Left 0 Right 1
    if($o){
        # Right Transpose
        # All values are hard coded to rotate to their new positions
        switch($y){
            0{switch($x){0{$x=2}1{$y=1;$x=2}2{$y=2}}}
            # 1,1 is in the center and nothing changes
            1{switch($x){0{$y=0;$x=1}2{$y=2;$x=1}}}
            2{switch($x){0{$x=0;$y=0}1{$x=0;$y=1}2{$x=0}}}
        }
    }else{
        # Left Transpose
        # All values are hard coded to rotate to their new positions
        switch($y){
            0{switch($x){0{$y=2}1{$x=0;$y=1}2{$x=0}}}
            # 1,1 is in the center and nothing changes
            1{switch($x){0{$y=2;$x=1}2{$y=0;$x=1}}}
            2{switch($x){0{$x=2}1{$x=2;$y=1}2{$y=0;$x=2}}}
        }

    }
    # Update global variables with the ones from this function
    $global:x=$x
    $global:y=$y
}

# Process each character passed by standard input
([char[]]$args[0]|%{
    switch($_){
        # Moving Forward
        '^'{
        $global:y++
        if($global:y-eq3){
            # We have walked of the colour onto the next one. Update coordinates to the next colour
            $global:y=0
            $c="$f"
            $f="$n"
            # Get the new neighboring colour indexes
            $z=&$u $c $f
            $f,$n="$($z[0][1])","$($z[1])"
        }
        # Output the colour we have just moved to.
        $o[$c]
        }
        # Turn Left
        "<"{$z=&$u $c $f;$f,$n="$($z[0][0])","$($z[1])"
        # Transpose the ants location by passing current location to the transposition function.
        t 0 $global:x $global:y
        }
        # Turn Right
        ">"{$z=&$u $c $f;$f,$n="$($z[0][2])","$($z[1])"
        # Transpose the ants location by passing current location to the transposition function.
        t 1 $global:x $global:y
        }
    }
}) -join ""
# Line above converts the output to a single string.

```

Using a lot of single letter variables used to records the ant current state (colour,position and orientation). The ant is always facing up. When a rotate instruction is read the cube is transposed in that direction. Hardcoded transposition matrices used to determine new position based on current position.

Code satisfies all examples in question.

# Answer
> 3 votes
# Tcl/Tk, 422 bytes

```
rename split S
array se {} [S wyywroorgbbg {}]
proc R a {foreach x [lassign $a y] {lappend b $x}
lappend b $y}
proc < {V H} {set ::H $V
set ::V [lreverse [R $H]]}
proc > {V H} [string map {V H H V} [info b <]]
proc ^ {V H} {
lassign $V x
lassign [set ::V [R $V]] y
set ::H [string map "$x $y $::($x) $::($y)" $::H]
puts -nonewline $y}
set V [S wwrrryyyooow {}]
set H [S wwgggyyybbbw {}]
foreach p [S {*}$argv {}] {$p $V $H}

```

Alas, I can't get it any smaller. Non-obfuscated version:

```
array set opposites [split wyywroorgbbg {}]

proc lrotate xs {
  foreach x [lassign $xs y] {
    lappend ys $x
  }
  lappend ys $y
}

proc < {V H} {
  set ::H $V
  set ::V [lreverse [lrotate $H]]
}

proc > {V H} {
  set ::H [lreverse [lrotate $V]]
  set ::V $H
}

proc ^ {V H} {
  lassign $V x
  lassign [set ::V [lrotate $V]] y
  set ::H [string map [list $x $y $::opposites($x) $::opposites($y)] $::H]
  puts -nonewline $y
}

set V [split wwrrryyyooow {}]
set H [split wwgggyyybbbw {}]
foreach p [split {*}$argv {}] {$p $V $H}
puts {}

```

It works by maintaining a list of horizontal and vertical cell colors. ^ \< and \> are all commands that properly permute the lists. The current cell is the first in each list.

# Answer
> 3 votes
# Ruby, 132

```
m=?w
g="bgoyr"
x=z=1
gets.bytes{|c|(m,g[2,3]=g[4],m+g[2,2]if(x+=1)%3<1
$><<m)if 93<c.upto(64){x,z,g=2-z,x,g[4]+g[2]+g[0]+g[3]+g[1]}}

```

This position system is sadly very similar to other answers out there. `x` and `z` track your position on the current face with `+x` being the direction of travel. Forward is always `x+=1`, and the bounds of each face are divisible by 3 (we don't care the number, just its modulus with 3).

`m` is the current face (this saves some bytes)

`g` is arranged `[left, right, behind, opposite, front]` so that we don't need to change `g[0..1]` on `^`

`<` is done simply by doing `>` three times.

# Answer
> 3 votes
# Java, ~~619~~ ~~605~~ ~~534~~ ~~517~~ 485 bytes

Well, here goes nothing...

At least it beat powershell!

-14 bytes thanks to @KevinCruijssen

And over 6 years later, -71 bytes (wow!) thanks to @ceilingcat . Try It Online!

And less than a year after that, @ceilingcat saved another 17 bytes. Try It Online!

OK @ceilingcat saved another 32 bytes, marking this as community wiki so they can make further edits. Try It Online!

```
String t(String f){int h[]={0,0,1},p[]={0,2,0},n[],i,s,r;String o="";for(int c:f.toCharArray()){r=r(p);n=h;if(c==94){for(s=i=3;i-->0;)if(h[i]==p[i]&p[i]!=0){s=i;n[1]=r<1?-1:r>4?1:n[1];i=2-r;if(i*i==1)n[0]=i;if(++i*i==1)n[2]=-i;i=0;}for(int a:n)p[++i]+=a;if(s<3)h[s]=0;o+="wgrboy".toCharArray()[r(p)];}i=r==3|r==5?2:r>0&r<3?1:0;r=h[s=r>-1&r<2?2:r>2&r<5?1:0];c-=61;if(c*c==1){h[s]=r==0?h[i]*c:0;h[i]=-r*c;}}return o;}int r(int[]p){return-1>p[0]?1:p[0]>1?3:p[1]>1?0:p[1]<-1?5:p[2]>1?2:4;}

```

## Explanation:

Unlike some of the other answers, which used used a 2-d coordinate system, I used a 3-d system to keep track of where the ant was.

The direction was also kept in a 3-d fashion to facilitate switching sides and movement.

Each face had one of the coordinates, x, y, or z, be set to 2 (or -2 for the opposite face) to signify which face it was.

Switching faces was accomplished by checking if the ant was about to go off (position and heading have a value that is same, but not 0), make sure it would "fall off" diagonally onto the next, and change the heading to be non-diagonal. This was surprisingly easy.

Turning was more difficult. Making sure it would always go the same direction required an extra if-else statement inside the check for each character, costing me many bytes. In addition, the "up" and "right" axes had to be hard-coded in for each side.

## Original ungolfed code

(Unchanged from previous edits for clarity in method)

```
private static String[] sides="w,g,r,b,o,y".split(",");
public static String traverse(String commands)
{
  int[] heading = {0,0,1};
  int[] pos = {0,2,0};
  int[] newheading;
  int i;
  int saved;
  String out = "";
  for(char command:commands.toCharArray())
  {
     if(command=='^')
     {
        newheading=heading;
        saved=3;
        for(i=0;i<3;i++)
        {
           if(heading[i]==pos[i]&pos[i]!=0)
           {
              saved=determineSide(pos);
              if(saved==0)newheading[1]=-1;
              if(saved==1)newheading[0]=1;
              if(saved==2)newheading[2]=-1;
              if(saved==3)newheading[0]=-1;
              if(saved==4)newheading[2]=1;
              if(saved==5)newheading[1]=1;
              saved=i;
              break;
           }
        }
        i=0;
        for(int c:newheading)
        {
           pos[i++]+=c;
        }
        if(saved<3)heading[saved]=0;
        out+=sides[determineSide(pos)];
     }
     newheading=getPlane(determineSide(pos));
     if(command=='>')
     {
        saved=heading[newheading[0]];
        if(saved==0)
        {
           heading[newheading[0]]=heading[newheading[1]];
           heading[newheading[1]]=0;
        }
        else
        {
           heading[newheading[1]]=-saved;
           heading[newheading[0]]=0;
        }
     }
     if(command=='<')
     {
        saved=heading[newheading[0]];
        if(saved==0)
        {
           heading[newheading[0]]=-heading[newheading[1]];
           heading[newheading[1]]=0;
        }
        else
        {
           heading[newheading[1]]=saved;
           heading[newheading[0]]=0;
        }
     }
  }
  return out;
}
public static int determineSide(int[] pos)
{
  return pos[0]==2?3:pos[0]==-2?1:pos[1]==2?0:pos[1]==-2?5:pos[2]==2?2:4;
}
public static int[] getPlane(int side)
{
  int[] out=new int[2];
  out[0]=side==0|side==1?2:side==3|side==4?1:0;
  out[1]=side==3|side==5?2:side==1|side==2?1:0;
  //side==0?{2,0}:side==1?{2,1}:side==2?{0,1}:side==3?{1,2}:side==4?{1,0}:{0,2};
  return out;
}

```

---
Tags: code-golf, string, grid, rubiks-cube
---


title: A classic sorting code-golf question

text:
# Question
Title: A classic sorting code-golf question
This is a code-golf question.

**Input**

A list of non-negative integers in whatever format is the most convenient.

**Output**

The same list in sorted order in whatever format is the most convenient.

**Restriction**

* Your code must run in O(n log n) time in the *worst case* where `n`is the number of integers in the input. This means that randomized quicksort is out for example. However there are many many other options to choose from.
* Don't use any sorting library/function/similar. Also don't use anything that does most of the sorting work for you like a heap library. Basically, whatever you implement, implement it from scratch.

You can define a function if you like but then please show an example of it in a full program actually working. It should run successfully and quickly on all the test cases below.

**Test cases**

```
In: [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
Out:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

In: [72, 59, 95, 68, 84]
Out:[59, 68, 72, 84, 95]

In: [2, 2, 1, 9, 3, 7, 4, 1, 6, 7]
Out:[1, 1, 2, 2, 3, 4, 6, 7, 7, 9]

In: [2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269]
Out:[667269,1925225, 2276714, 2397725,3088926, 3304534, 4274324, 4487711, 7806949, 8337622]

```

**Your answers**

Please state the sorting algorithm you have implemented and the length of your solution in the title of your answer.

**O(n log n) time sorting algorithms**

There are many O(n log n) time algorithms in existence. This table has a list of some of them.

# Answer
# Haskell, ~~87~~ ~~80~~ 89

```
s%[]=s
(x:a)%q|x<=q!!0=x:a%q
p%q=q%p
j(x:y:s)=x%y:j s
j a=a
r[x]=x
r s=r$j s
s=r.map(:[])

```

This is merge sort, implemented from the bottom up. first we package every element into it's own list, and then merge them two-by-two, and again merge them two-by-two, until we're left with one list.

`(%)` is the merge function
`j` merges pairs in a list of lists
`r` merges a complete list of lists
`s` is the sorting function.

Usage: Run an interpreter, and enter `s [3,5,2,6,7]`.

**Edit:** the way I was merging things before wasn't the right order, So to fix it I needed 9 more characters.
> 8 votes

# Answer
# JavaScript (ES6), ~~195~~ ~~193~~ ~~191~~ ~~189~~ ~~188~~ ~~186~~ ~~183~~ ~~182~~ ~~179~~ ~~174~~ 172 bytes

This is a heapsort implementation. I expect someone to come up with a shorter mergesort, but I like this one :P

Update: R mergesort beaten. Ruby up next :D

```
S=l=>{e=l.length
W=(a,b)=>[l[a],l[b]]=[l[b],l[a]]
D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)}
for(s=e>>1;s;)D(--s)
for(;--e;D(0))W(0,e)}

```

### Test (Firefox)

```
S=l=>{e=l.length
W=(a,b)=>[l[a],l[b]]=[l[b],l[a]]
D=s=>{for(;(c=s*2+1)<e;s=r<s?s:e)s=l[r=s]<l[c]?c:s,W(r,s=++c<e&&l[s]<l[c]?c:s)}
for(s=e>>1;s;)D(--s)
for(;--e;D(0))W(0,e)}

document.querySelector('#d').addEventListener("click",function(){a=JSON.parse(document.querySelector('#a').value);S(a);document.querySelector('#b').innerHTML=JSON.stringify(a)});
```

```
<textarea id="a">[9,4,1,2,7,3,5,8,6,10]</textarea><br><button id="d">Sort</button><br><pre id="b"></pre>
```
> 5 votes

# Answer
# Python3, 132 bytes

```
def S(l):
 if len(l)<2:return l
 a,b,o=S(l[::2]),S(l[1::2]),[]
 while a and b:o.append([a,b][a[-1]<b[-1]].pop())
 return a+b+o[::-1]

```

Simple mergesort. Lots of bytes were spent to make sure this actually runs in O(n log n), if only the *algorithm*, but not the *implementation* needs to be O(n log n), this can be shortened:

# Python3, 99 bytes

```
def m(a,b):
 while a+b:yield[a,b][a<b].pop(0)
S=lambda l:l[1:]and list(m(S(l[::2]),S(l[1::2])))or l

```

This is not O(n log n) because `.pop(0)` is O(n), making the merge function O(n^2). But this is fairly artificial, as `.pop(0)` could easily have been O(1).
> 4 votes

# Answer
# Jelly, 29 bytes, merge sort

Like orlp’s Python answer, this uses `list.pop(0)` under the hood, which is `O(n)`, but the implementation is formally `O(n log n)`.

```
ṛð>ṛḢð¡Ḣ;ñ
ç;ȧ?
s2Zß€ç/µL>1µ¡

```

Try it here.

## Explanation

```
               Define f(x, y):    (merge helper)
                 Implicitly store x in α.
ṛ    ð¡          Replace it with y this many times:
 ð>ṛḢ              (x > y)[0].
       Ḣ         Pop the first element off that list (either x or y).
        ;ñ       Append it to g(x, y).

               Define g(x, y):    (merge)
  ȧ?             If x and y are non-empty:
ç                  Return f(x, y)
                 Else:
 ;                 Return concat(x, y).

               Define main(z):    (merge sort)
       µL>1µ¡    Repeat (len(z) > 1) times:
s2                 Split z in chunks of length two.   [[9, 7], [1, 3], [2, 8]]
  Z                Transpose the resulting array.     [[9, 1, 2], [7, 3, 8]]
   ß€              Apply main() recursively to each.  [[1, 2, 9], [3, 7, 8]]
     ç/            Apply g on these two elements.     [1, 2, 3, 7, 8, 9]

```
> 3 votes

# Answer
# Julia, 166 bytes

```
m(a,b,j=1,k=1,L=endof)=[(j<=L(a)&&k<=L(b)&&a[j]<b[k])||k>L(b)?a[(j+=1)-1]:b[(k+=1)-1]for i=1:L([a;b])]
M(x,n=endof(x))=n>1?m(M(x[1:(q=ceil(Int,n÷2))]),M(x[q+1:n])):x

```

The primary function is called `M` and it calls a helper function `m`. It uses merge sort, which has *O*(*n* log *n*) as its worst case complexity.

Example use:

```
x = [9, 8, 3, 2, 4, 6, 5, 1, 7, 0]
println(M(x))              # prints [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
println(M(x) == sort(x))   # prints true

```

Ungolfed:

```
function m(a, b, i=1, k=1, L=endof)
    return [(j <= L(a) && k <= L(b) && a[j] < b[k]) || k > L(b) ?
            a[(j+=1)-1] : b[(k+=1)-1] for i = 1:L([a; b])]
end

function M(x, n=endof(x))
    q = ceil(Int, n÷2)
    return n > 1 ? m(M(x[1:q]), M([q+1:n])) : x
end

```
> 2 votes

# Answer
# R, 181 bytes, Mergesort

```
L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}

```

Indented, with newlines:

```
L=length
s=function(S)
    if(L(S)<2){
        S
    }else{
        h=1:(L(S)/2)
        A=s(S[h])
        B=s(S[-h])
        Z=c()
        if(A[L(A)]>B[1])
#Merge helper function incorporated from here ...
            while(L(A)&L(B))
                if(A[1]<B[1]){
                    Z=c(Z,A[1])
                    A=A[-1]
                }else{
                    Z=c(Z,B[1])
                    B=B[-1]
                }
#...to here. Following line both finishes merge function and handles 'else' case:
        c(Z,A,B)
    }

```

Test cases:

```
> L=length;s=function(S)if(L(S)<2){S}else{h=1:(L(S)/2);A=s(S[h]);B=s(S[-h]);Z=c();if(A[L(A)]>B[1])while(L(A)&L(B))if(A[1]<B[1]){Z=c(Z,A[1]);A=A[-1]}else{Z=c(Z,B[1]);B=B[-1]};c(Z,A,B)}
> s(c(2397725, 1925225, 3304534, 7806949, 4487711, 8337622, 2276714, 3088926, 4274324,  667269))
 [1]  667269 1925225 2276714 2397725 3088926 3304534 4274324 4487711 7806949 8337622
> s(c(2, 2, 1, 9, 3, 7, 4, 1, 6, 7))
 [1] 1 1 2 2 3 4 6 7 7 9
> s(c(72, 59, 95, 68, 84))
 [1] 59 68 72 84 95
> s(c(9, 8, 3, 2, 4, 6, 5, 1, 7, 0))
 [1] 0 1 2 3 4 5 6 7 8 9

```
> 2 votes

# Answer
## Scala, 243 Byte function (315 Bytes stand-alone app), Mergesort

This answer is intended to be a function, but can be expanded to be a stand-alone application.

Function-only (243 bytes):

```
object G{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
}

```

Stand-alone application(315 bytes):

```
object G extends App{
type S=Stream[Int]
def m(f:(S,S)):S=f match{
case(x#::a,b@(y#::_))if x<=y=>x#::m(a,b)
case(a,y#::b)=>y#::m(a,b)
case(a,Empty)=>a
case(_,b)=>b}
def s(a:S):S=if(a.length>1)((q:S,w:S)=>m(s(q),s(w))).tupled(a.splitAt(a.length/2))else a
println(s(args(0).split(",").map(_.toInt).toStream).toList)
}

```

Usage:

> Function: `G.s(List(**[Paste your array here]**).toStream).toList`
>
> Application: `sbt "run **[Paste your array here]**"`

Example Input:

```
scala> G.s(List(10,2,120,1,8,3).toStream).toList

(OR)

$ sbt "run 5423,123,24,563,65,2,3,764"

```

Output:

> res1: List\[Int\] = List(1, 2, 3, 8, 10, 120)
>
> OR
>
> List(2, 3, 24, 65, 123, 563, 764, 5423)

Constraints & considerations:

* Requires scalaz (very common library, not used for sorting here)
* Is 100% functional (nothing mutable!)

Attribution:
> 2 votes

# Answer
# Ruby, 167 bytes

Golfed merge sort algorithm, which has worst-case O(n log n)

```
f=->x{m=->a,b{i,j,l,y,z=0,0,[],a.size,b.size
while i<y&&j<z
c=a[i]<b[j]
l<<(c ?a[i]:b[j])
c ?i+=1:j+=1
end
l+=a[i,y]+b[j,z]}
l=x.size
l>1?m[f[x[0,l/2]],f[x[l/2,l]]]:x}

```

Test it here!

To test, copy and paste the code into the window, and add `puts f[x]` at the bottom, where x is an array with the input. (Make sure you select Ruby as the language, of course) For example, `puts f[[2, 2, 1, 9, 3, 7, 4, 1, 6, 7]]`
> 1 votes

# Answer
## Ruby, 297 bytes

Merge sort. Complete program, instead of a function. Requires two arguments at runtime: input file and output file, each with one element per line.

```
if $0==__FILE__;v=open(ARGV[0]).readlines.map{|e|e.to_i}.map{|e|[e]};v=v.each_slice(2).map{|e|a,b,r=e[0],e[1],[];while true;if(!a)||a.empty?;r+=b;break;end;if(!b)||b.empty?;r+=a;break;end;r<<(a[0]<b[0]?a:b).shift;end;r}while v.size>1;open(ARGV[1],"w"){|f|f.puts(v[0].join("\n"))if !v.empty?};end

```
> 1 votes

---
Tags: code-golf, array, sorting, restricted-complexity
---


title: Solve the Secretary Problem

text:
# Question
Title: Solve the Secretary Problem
The Secretary Problem is a famous problem described as thus:

1. You need a new secretary
2. You have N applicants that you can interview one at a time
3. You are able to score each applicant after the interview. Your scoring system will never give two applicants the same score
4. After you interview an applicant, you must give an immediate "yes" or "no"
5. You want the applicant with the highest score

The solution is to interview the first `floor(N/e)` applicants, and then accept the first applicant that has a higher score than all of the previous applicants. If none of the applicants are higher, then return the last applicant. Interestingly enough, this gives the top applicant `1/e` percent of the time. `e` refers to Euler's number. To get the value of `e`, you can use a builtin, `log`, or hardcode it to at least 5 decimal points.

# Input:

An non-empty array of unique non-negative integers no more than `2^31-1`.

# Output:

An integer representing the chosen candidate. To be clear the algorithm is:

1. Find the maximum element in the first `floor(N/e)` elements of the array.
2. Iterate through the remaining elements, and return the first element that is higher than the maximum found on step 1.
3. If none of the elements are higher, than return the last element.

For example, say your array was `[2,7,4,3,9,20]`, so `N = 6` and `floor(N/e) = 2`. The first 2 elements of the array is `[2,7]`. The max of `[2,7]` is `7`. The remaining elements are `[4,3,9,20]`. The first element that is greater than `7` is `9`, so we return `9`.

# Test Cases:

```
[0]         => 0
[100]       => 100
[100, 45]   => 100
[0, 1]      => 0
[45, 100]   => 45
[1, 4, 5]   => 4
[1, 5, 4]   => 5
[5, 4, 1]   => 1
[5, 1, 4]   => 4
[4, 1, 5]   => 5
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
=> 98
[10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30]
=> 30

```

Your solution must be `O(n)`, where `n` is the length of the array. If your language has a builtin that finds the maximum of an array, you can assume that the function takes `O(n)` (and hopefully it does).

Standard loopholes apply, and this is a , so the make the shortest answer in your favorite language!

# Answer
# Jelly, 13 bytes

```
L:Øe³ḣȯ-Ṁ<i1ị

```

Definitely an **O(n)** algorithm, hopefully an **O(n)** implementation. Try it online!

### How it works

```
L:Øe³ḣȯ-Ṁ<i1ị  Main link. Argument: A (list of scores)

L              Get the length of A.
 :Øe           Divide the length by e, flooring the result.
    ³ḣ         Retrieve the that many scores from the beginning of A.
      ȯ-       Logical OR; replace an empty list with -1.
        Ṁ      Compute the maximum of those scores.
         <     Compare each score in A with that maximum.
          i1   Find the first index of 1 (0 if not found).
            ị  Retrieve the element of A at that index (the last one if 0).

```
> 4 votes

# Answer
# CJam, 20 Bytes

```
q~___,1me/i<:e>f>1#=

```

Works similarly to Dennis's suggestion.

```
q~___                     Read array, duplicate three times
      ,                   Consume one to find the length
       1me/i              Push e then divide and take floor
            <             Take that many elements from the list
             :e>          Find maximum (Thanks to Dennis)
                f>        Label array elements larger than this as 1
                  1#      Find the first one (won't be in set of elements we've looked in)
                    =     Take that element from the final copy of the array. -1 gives us the last element as required

```
> 3 votes

# Answer
# MATL, ~~27~~ ~~25~~ 23 bytes

```
tttn1Ze/:)-1hX>>T0(f1))

```

Uses the same approach as A. Simmons' CJam answer.

**Try it online!**
> 2 votes

# Answer
## Java, ~~128~~ 118 bytes

```
a->{int c=(int)(a.length/Math.E),i=0,m=-1,t=0;for(;i<a.length;i++){t=a[i];if(i<c)m=t>m?t:m;if(t>m)return t;}return t;}

```

Indented:

```
static Function<Integer[], Integer> secretary2 = a -> {
    int c = (int) (a.length/Math.E),     // c = floor(N/E)
        i = 0, m = -1, t = 0;            // declare vars early to save bytes
    for (;i<a.length;i++) {              // for each element of input
        t = a[i];                        // cache element to save bytes
        if (i<c)                         // if before c
            m = t>m ? t : m;             // m = max(m, element)
        if (t>m)                         // if element > m
            return t;                    // return: we've found our best
    }                                    // if never found a good element
    return t;                            // return the last element
};

```
> 2 votes

# Answer
# JavaScript (ES6) 64

```
(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

```

*Less golfed*

```
(
 a,
 l=a.length/Math.E, // limit for stage 1
 x // init at undefined
)=>(
  a.every(v => --l > 0 // checking for >0 no need to floor
          ? x>v?1:x=v // stage 1, find max in x, always return truthy
          : (z=v)<x ) // stage 2, set z to current value and exit early if z>x
  , z // at last z has the last seen value
)

```

**Test**

```
f=(a,l=a.length/Math.E,x)=>(a.every(v=>--l>0?x>v?1:x=v:(z=v)<x),z)

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

;[
 [0], [100], [0,1], [1,2,3],
 [100, 45],
 [45, 100],
 [1, 4, 5],
 [1, 5, 4],
 [5, 4, 1],
 [5, 1, 4],
 [4, 1, 5],
 [10, 68, 52, 48, 81, 39, 85, 54, 3, 21, 31, 59, 28, 64, 42, 90, 79, 12, 63, 41, 58, 57, 13, 43, 74, 76, 94, 51, 99, 67, 49, 14, 6, 96, 18, 17, 32, 73, 56, 7, 16, 60, 61, 26, 86, 72, 20, 62, 4, 83, 15, 55, 70, 29, 23, 35, 77, 98, 92, 22, 38, 5, 50, 82, 1, 84, 93, 97, 65, 37, 45, 71, 25, 11, 19, 75, 78, 44, 46, 2, 53, 36, 0, 47, 88, 24, 80, 66, 87, 40, 69, 27, 9, 8, 91, 89, 34, 33, 95, 30],
[56, 7, 37, 73, 90, 59, 65, 61, 29, 16, 47, 77, 60, 8, 1, 76, 36, 68, 34, 17, 23, 26, 12, 82, 52, 88, 45, 89, 94, 81, 3, 24, 43, 55, 38, 33, 15, 92, 79, 87, 14, 75, 41, 98, 31, 58, 53, 72, 39, 30, 2, 0, 49, 99, 28, 50, 80, 91, 83, 27, 64, 71, 93, 95, 11, 21, 6, 66, 51, 85, 48, 62, 22, 74, 69, 63, 86, 57, 97, 32, 84, 4, 18, 46, 20, 42, 25, 35, 9, 10, 19, 40, 54, 67, 70, 5, 44, 13, 78, 96]
].forEach(t=>{
  var r=f(t)
  console.log(r+' : '+t)
})
```

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

# Answer
# Ruby, 64 bytes

```
->a{m=a[0...c=a.size/Math::E].max
a[c..-1].find{|n|n>m}||a[-1]}

```
> 1 votes

# Answer
# PARI/GP, 70 bytes

This may have trouble on older versions of gp when given a singleton, but it works at least from revision 18487.

```
v->m=vecmax(v[1..t=#v\exp(1)]);for(i=t+1,#v,v[i]>m&&return(v[i]));v[#v]

```
> 1 votes

# Answer
## JavaScript (ES6), 79 bytes

```
a=>(m=Math.max(...a.splice(0,a.length/Math.E)),a.slice(a.findIndex(x=>x>m))[0])

```

Works because `findIndex` returns `-1` on failure, but `a.slice(-1)[0]` returns the last element of the array as desired.
> 1 votes

# Answer
# Python 2, 87 bytes

```
a=input()
t=int(len(a)/2.71828)
m=max(a[:t]+[-1])
for x in a[t:]:
 if x>m:break
print x

```

The user enters the array as a list, with square brackets and commas. Python 2's `input()` command is convenient here.

Whether or not we terminate the process early, we hire the last person who got interviewed.
> 1 votes

# Answer
# Perl 6, 43 bytes

I think this is O(n)

```
{@^a.first(*>max @a[^floor @a/e])//@a[*-1]}

```
> 1 votes

# Answer
# Python 3.5; 110 bytes:

```
def Interview(h):k=max(h[0:int(len(h)/2.71828)-1]);n=max(h[int(len(h)/2.71828)-1:len(h)-1]);return max([k, n])

```

Basically, what the above does is that it firstly takes an array provided, "h" *as long as it includes **more than 5 items*** (for now...), finds the maximum value in the first (length of array (len(h))/ Euler's number (to 5 decimal places)) items of that array, and then returns that value as "k". Furthermore, "n" is the maximum value in the rest of the array. Finally, the value returned from the function is the maximum value in an array containing both "k" and "n".

**Note: The `max()` function of Python *is* O(n) complexity.**

Below is a more readable, **non-code-golf** **version** of the above code that has a random, unique 10-item array provided, to confirm that it works:

```
import random, math

def Interview():
    k = max(h[0:int(len(h)/math.e)-1])
    n = max(h[int(len(h)/math.e)-1:len(h)-1])
    return max([k, n])

h = random.sample(range((2*31)-1), 10)

print(Interview(h))

```
> 1 votes

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