# Question
Title: Powerprogramming: O(1^N), O(N^1), O(2^N), O(N^2) all in one
Write a program (or function) that exhibits four common big O time complexities depending on how it is run. In any form it takes in a positive integer N which you may assume is less than 231.

1. When the program is run in its **original** form it should have **constant** complexity. That is, the complexity should be **Θ(1)** or, equivalently, **Θ(1^N)**.
2. When the program is **reversed** and run it should have **linear** complexity. That is, the complexity should be **Θ(N)** or, equivalently, **Θ(N^1)**.
(This makes sense since `N^1` is `1^N` reversed.)
3. When the program is **doubled**, i.e. concatenated to itself, and run it should have **exponential** complexity, specifically **2N**. That is, the complexity should be **Θ(2^N)**.
(This makes sense since the `2` in `2^N` is double the `1` in `1^N`.)
4. When the program is **doubled *and* reversed** and run it should have **polynomial** complexity, specifically **N2**. That is, the complexity should be **Θ(N^2)**.
(This makes sense since `N^2` is `2^N` reversed.)

These four cases are the only ones you need to handle.

Note that for preciseness I'm using big theta (Θ) notation instead of big O because the runtimes of your programs must be bounded both above and below by the required complexities. Otherwise just writing a function in O(1) would satisfy all four points. It is not too important to understand the nuance here. Mainly, if your program is doing k\*f(N) operations for some constant k then it is likely in Θ(f(N)).

> # Example
>
> If the original program were
>
> ```
> ABCDE
>
> ```
>
> then running it should take constant time. That is, whether the input N is 1 or 2147483647 (231-1) or any value in between, it should terminate in roughly the same amount of time.
>
> The reversed version of the program
>
> ```
> EDCBA
>
> ```
>
> should take linear time in terms of N. That is, the time it takes to terminate should be roughly proportional to N. So N = 1 takes the least time and N = 2147483647 takes the most.
>
> The doubled version of the program
>
> ```
> ABCDEABCDE
>
> ```
>
> should take two-to-the-N time in terms of N. That is, the time it takes to terminate should be roughly proportional to 2N. So if N = 1 terminates in about a second, N = 60 would take longer than the age of the universe to terminate. (No, you don't have to test it.)
>
> The doubled and reversed version of the program
>
> ```
> EDCBAEDCBA
>
> ```
>
> should take squared time in terms of N. That is, the time it takes to terminate should be roughly proportional to N\*N. So if N = 1 terminates in about a second, N = 60 would take about an hour to terminate.

# Details

* **You need to show or argue that your programs are running in the complexities you say they are.** Giving some timing data is a good idea but also try to explain why theoretically the complexity is correct.
* It's fine if in practice the times your programs take are not perfectly representative of their complexity (or even deterministic). e.g. input N+1 might sometimes run faster than N.
* The environment you're running your programs in *does* matter. You can make basic assumptions about how popular languages never intentionally waste time in algorithms but, for example, if you know your particular version of Java implements bubble sort instead of a faster sorting algorithm, then you should take that into account if you do any sorting.
* For all complexities here assume we are talking about worst-case scenarios, not best-case or average-case.
* The space complexity of the programs does not matter, only the time complexity.
* The programs may output anything. It only matters that they take in positive integer N and have the correct time complexities.
* Comments and multiline programs are allowed. (You may assume `\r\n` reversed is `\r\n` for Windows compatibility.)

# Big O Reminders

From fastest to slowest it's `O(1), O(N), O(N^2), O(2^N)` (order 1, 2, 4, 3 above).

Slower terms always dominate, e.g. `O(2^N + N^2 + N) = O(2^N)`.

`O(k*f(N)) = O(f(N))` for constant k. So `O(2) = O(30) = O(1)` and `O(2*N) = O(0.1*N) = O(N)`.

Remember `O(N^2) != O(N^3)` and `O(2^N) != O(3^N)`.

Neat big O cheat sheet.

# Scoring

This is normal code golf. The shortest original program (the constant time one) in bytes wins.

# Answer
> 38 votes
# Python 3, 102 bytes

```
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

```

Try it online!

This is of O(1^n), since this is what the program does:

* evaluate the input
* create the array \[0\]
* print it

---

Reversed:

```

try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

```

Try it online!

This is of O(n^1), since this is what the program does:

* evaluate the input
* create the array \[0\]\*input (0 repeated as many times as the input)
* print it

---

Doubled:

```
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*k**l(tnirp
except:k=2#2=k:tpecxe
print(k**l*[0])#1=k;))(tupni(lave=l:yrt

```

Try it online!

This is of O(2^n), since this is what the program does:

* evaluate the input
* create the array \[0\]
* print it
* try to evaluate the input
* fail
* create the array \[0\]\*(2^input) (0 repeated as many times as 2^input)
* print it

---

Doubled and reversed:

```

try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt
try:l=eval(input());k=1#)]0[*l**k(tnirp
except:k=2#2=k:tpecxe
print(l**k*[0])#1=k;))(tupni(lave=l:yrt

```

Try it online!

This is of O(n^2), since this is what the program does:

* evaluate the input
* create the array \[0\]\*input (0 repeated as many times as the input)
* print it
* try to evaluate the input
* fail
* create the array \[0\]\*(input^2) (0 repeated as many times as the input squared)
* print it

# Answer
> 18 votes
# Perl 5, ~~82~~ ~~73~~ 71+1 (for -n flag) = 72 bytes

I'm certain I can golf this (a lot) more, but it's bedtime, I've spent enough time debugging as is, and I'm proud of what I have so far anyway.

```
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

```

The program itself doesn't use the input, and just evaluates a string beginning with a comment and then does a single string substitution, so this is clearly in constant time. It's basically equivalent to:

```
$x="#";
eval $x;
$x=~s/#//;

```

Doubled:

```
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;
#x$=_$;
$x.=q;#say for(1..2**$_)#)_$..1(rof _$=+x$;;
eval $x;$x=~s/#//;

```

The bit that actually takes exponential time is the second eval: it evaluates the command `say for(1..2**$_)`, which lists all the numbers from 1 to 2^N, which clearly takes exponential time.

Reversed:

```
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

```

This (naively) computes the summation of the input, which clearly takes linear time (since each addition is in constant time). The code that actually gets run is equivalent to:

```
$x+=$_ for(1..$_);
$_=$x;

```

The last line is just so that when these commands are repeated it will take quadratic time.

Reversed and doubled:

```
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#
;//#/s~=x$;x$ lave
;;$x+=$_ for(1..$_)#)_$**2..1(rof yas#;q=.x$
;$_=$x#

```

This now takes the summation of the summation of the input (and adds it to the summation of the input, but whatever). Since it does order `N^2` additions, this takes quadratic time. It's basically equivalent to:

```
$x=0;
$x+=$_ for(1..$_);
$_=$x;
$x+=$_ for(1..$_);
$_=$x;

```

The second line finds the summation of the input, doing `N` additions, while the fourth does `summation(N)` additions, which is `O(N^2)`.

# Answer
> 17 votes
# Actually, 20 bytes

```
";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

```

Try it online!

Input: `5`

Output:

```
rⁿ@╜╖1(;
[0]
5

```

---

Reversed:

```
";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

```

Try it online!

Output:

```
rⁿ╜╖1(;
[0, 1, 2, 3, 4]
5

```

---

Doubled:

```
";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"";(1╖╜ⁿr"ƒ"rⁿ@╜╖1(;"

```

Try it online!

Output:

```
rⁿ@╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31]
rⁿ@╜╖1(;
rⁿ@╜╖1(;
[0]

```

---

Doubled and reversed:

```
";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"";(1╖╜@ⁿr"ƒ"rⁿ╜╖1(;"

```

Try it online!

Output:

```
rⁿ╜╖1(;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24]
rⁿ╜╖1(;
rⁿ╜╖1(;
[0, 1, 2, 3, 4]

```

---

## Main idea

Actually is a stack-based language.

* `abc` is a program which has O(1n) complexity, and its double has O(2n) complexity.
* `def` is a program which has O(n1) complexity, and its double has O(n2) complexity.

Then, my submission is `"abc"ƒ"fed"`, where `ƒ` is evaluate. That way, `"fed"` will not be evaluated.

### Generation of individual program

The pseudocode of the first component `;(1╖╜ⁿr`:

```
register += 1 # register is default 0
print(range(register**input))

```

The pseudocode of the second component `;(1╖╜ⁿ@r`:

```
register += 1 # register is default 0
print(range(input**register))

```

# Answer
> 4 votes
# Jelly, 20 bytes

Partly inspired by Leaky Nun's Actually solution.

The leading and trailing newlines are significant.

### Normal:

```

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

```

Try it online!

Input: `5`

Output:

```
610

```

---

### Reversed:

```

⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

```

Try it online!

Input: `5`

Output:

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

```

---

### Doubled

```

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

⁵Ŀ⁵
R
R²
2*R
‘
⁵Ŀ⁵

```

Try it online!

Input: `5`

Output:

```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]10

```

---

### Doubled and Reversed

```

⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

⁵Ŀ⁵
‘
R*2
²R
R
⁵Ŀ⁵

```

Try it online!

Input: `5`

Output:

```
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]10

```

---

### Explanation

The key here is in `Ŀ`, which means "calls the link at index n as a monad." The links are indexed top to bottom starting at 1, excluding the main link (the bottom-most one). `Ŀ` is modular as well, so if you try to call link number 7 out of 5 links, you'll actually call link 2.

The link being called in this program is always the one at index 10 () no matter what version of the program it is. However, which link is at index 10 depends on the version.

The  that appears after each `Ŀ` is there so it doesn't break when reversed. The program will error out at parse-time if there is no number before `Ŀ`. Having a  after it is an out of place nilad, which just goes straight to the output.

**The original version** calls the link , which computes n+1.

**The reversed version** calls the link `R`, which generates the range 1 .. n.

**The doubled version** calls the link `2*R`, which computes 2n and generates the range 1 .. 2n.

**The doubled and reversed version** calls the link `²R`, which computes n2 and generates the range 1 .. n2.

# Answer
> 4 votes
# Befunge-98, 50 bytes

## Normal

```
\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@
&$< ^&;

```

This is by far the simplest program of the 4 - the only commands that are executed are the following:

```
\+]
  !
  : @
&$< ^&;

```

This program does some irrevelant stuff before hitting a "turn right" command (`]`) and an arrow. Then it hits **2** "take input" commands. Because there is only 1 number in input and because of how TIO treats `&`s, the program exits after 60 seconds. If there are 2 inputs (and because I can without adding bytes), the IP would travel up into the "end program" function.

Try it online!

## Reversed

```
;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

```

This one is a little more complicated. the relevant commands are as follows:

```
;&^  $
  >:*[
;< $#]#; :. 1-:!k@
  :

```

which is equivalent to

```
;&^                   Takes input and sends the IP up. the ; is a no-op
  :                   Duplicates the input.
  >:*[                Duplicates and multiplies, so that the stack is [N, N^2
     $                Drops the top of the stack, so that the top is N
     ]#;              Turns right, into the loop
         :.           Prints, because we have space and it's nice to do
            1-        Subtracts 1 from N
              :!k@    If (N=0), end the program. This is repeated until N=0
;< $#]#;              This bit is skipped on a loop because of the ;s, which comment out things

```

The important part here is the  `:. 1-:!k@` bit. It's useful because as long as we push the correct complexity onto the stack before executing in a lower time complexity, we can get the desired one. This will be used in the remaining 2 programs in this way.

Try it online!

## Doubled

```
\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;
[*:>@
&$< ^&;

```

And the relevant command are:

```
\+]
  !
  :
&$< ^&;\+]#:\-1vk  !:;#
@k!:-1 .: ;#]#$ <;

```

This program goes into 2 loops. First, it follows the same path as the normal program, which pushes 1 and N onto the stack, but instead of wrapping around to the second `&`, the IP jumps over a comment into a loop that pushes `2^N`:

```
        vk!:    If N is 0, go to the next loop.
      -1        Subtract 1 from N
 +  :\          Pulls the 1 up to the top of the stack and doubles it
  ]#            A no-op
\               Pulls N-1 to the top again

```

The other bits on line 4 are skipped using `;`s

After (2^N) is pushed onto the stack, we move down a line into the aforementioned printing loop. Because of the first loop, the time complexity is Θ(N + 2^N), but that reduces to Θ(2^N).

Try it online!

## Doubled and Reversed

```
;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\;&^ <$&
 @>:*[
;< $#]#; :. 1-:!k@
#;:!  kv1-\:#]+\

```

The relevant commands:

```
;&^

;< $#]#; :. 1-:!k@

 @>:*[

  :

```

This functions almost identically to the reversed program, but the `N^2` is not popped off of the stack, because the first line of the second copy of the program is appended to the last line of the first, meaning that the drop command (`$`) never gets executed, so we go into the printing loop with `N^2` on the top of the stack.

Try it online!

# Answer
> 0 votes
# JavaScript (Node.js), 90 bytes

```
f=n=>n&&f(--n)+f(n);f(t);var t=process.argv[1]//;);--i;]1[vgra.ssecorp:t*t?t=i=t rav(rof"

```

Try it online!

Trivial

---
Tags: code-golf, integer, source-layout, restricted-complexity, set-theory
---


title: Quickly Prove Me Wrong!

text:
# Question
Title: Quickly Prove Me Wrong!
## Introduction

This is the evolution of this previous challenge which was about checking satisfieability of normal formulae in conjunctive normal form (CNF). However, this problem is NP-complete and watching algorithms finish is just boring, so we're gonna simplify the problem!

## Specification

### Input

**You may tune the following input specification to optimally match your language as long as you don't encode additional information.**
Your input will be a list of implications. Each implication has a list of variables on the left and a single variable on the right. Variables may be represented using your favorite representation (integer, strings, whatever), for the sake of this specification, characters will be used. The list on the left side may be empty and there may not be a variable on the right. The variable on the right side will not appear on the left side of the same implication.

Example input:

```
[A -> B; B -> A]
[A,B,C -> D; B,C -> E; -> A; B -> ]

```

### Output

Your output will be a truthy or a falsy value.

### What to do?

You need to determine whether the given formula is satisfieable and output truthy if it is satisfieable and falsy if not.
`A,B -> C` means that if A and B need to hold then C needs to hold as well.
`-> C` means that C always needs to hold (this is short-hand for `True -> C`).
`A,B ->` means that if A and B need to hold, so does falsum and thus there is a contradiction, thus if you find such an implication where A and B hold, you can immediately output falsy (this is short-hand for `A,B -> False`).
The list of implications all need to hold at the same time.

Because this problem is also known as HORNSAT, it is P-complete and to avoid trivial solutions to this, your solution **must run in polynomial time and you must provide reasoning why your solution does so**.

### Who wins?

This is , thus the shortest solution in bytes wins! Standard rules apply.

## Examples

### with Explanation

`[A,B -> C; C ->; -> A; A -> B]` A needs to hold, thus B needs to hold, thus C needs to hold and thus you found a contradiction.
`[A,B -> D; C ->; -> A; A -> B]` A needs to hold, thus B needs to hold, thus D needs to hold, however C doesn't need to hold and thus this formula is satisfieable.

### without Explanation

```
[A -> B; B -> A] => 1
[A,B,C -> D; B,C -> E; -> A; B -> ] => 1
[A,B -> C; C ->; -> A; A -> B] => 0
[A,B -> D; C ->; -> A; A -> B] => 1
[P -> ; -> S ; P -> R; Q -> U; R -> X; S -> Q; P,U -> ; Q,U -> W] => 1
[-> P; Q -> ; T -> R; P -> S; S -> T; T,P -> Q ] => 0

```

# Answer
> 3 votes
# Alice, 45 bytes

```
/;;?dhE..';F>@.>F*.?oK
\'..zi;w!";-$"'!?n-$-/

```

Try it online!

Input is in the form `A->B;B->A` with no spaces. Output is `Jabberwocky` if the formula is satisfiable, and nothing otherwise.

### Explanation

This follows a standard template for programs that run entirely in ordinal mode. Unwrapped, the program is:

```
';.diEw.";->".!Fn.$o;.?zh;.!';F$@'>?*-?-K

';.     Push a semicolon and duplicate it
d       Join these two semicolons into a single string and push it, without removing the originals
        This puts ";;" on top of the stack, with a ";" under it (and an irrelevant ";" under that)
i       Take input
E       Insert input between the only pair of characters in ";;"
w       Push return address (start main loop)
.       Duplicate current set of implications
";->"   Push this string
.!      Copy to tape (to get it again later with fewer bytes)
F       Check whether this string is in current set of implications
n       Negate result: "Jabberwocky" if no match, "" if match
.$o     Output this string if nonempty (no unit clauses remain)
;       Discard top of stack: if the previous command didn't output, this puts the implications back on the TOS
        If the previous command did output, this discards the implications and puts ";" on the TOS
.       Duplicate
?z      Remove everything up to and including the first ";->"
h;      Take first character of remaining string: this is the literal in the first unit clause,
        or ";" if the clause is simply "->" (or if "Jabberwocky" was output earlier)
.!      Copy to tape, since we will need it later
';F     Check whether this character contains (i.e., is) a semicolon
$@      If so, terminate
        (Replace "A" in the next two lines with the actual value of the literal in this unit clause)
'>?*-   Remove all instances of ">A"; this destroys all clauses that imply A
?-      Remove all instances of "A"
K       Return to start of main loop

```

Each command in the main loop takes polynomial time, and each iteration of the loop either terminates the program or destroys at least one clause. Hence, the entire program runs in polynomial time.

# Answer
> 2 votes
# Python 2, ~~312~~ ~~244~~, 243 bytes

```
from sympy import*;s=input()
l=' ||,|&|;->|;1>>|[->|[1>>|->;|>>0;|->]|>>0]|;|)&(|->|>>|[|(|]|)|(|((|>>|)>>'.split('|')
for i in zip(l[::2],l[1::2]):s=s.replace(*i)
for i in range(65,91):y=chr(i);vars()[y]=Symbol(y)
print satisfiable(eval(s))>0

```

Try it online!

**Some explications** The input is converted to the appropriate format of sympy module, then verifying satisfiability.

**Is it time-polynomial?**

I performed a set of experimental tests that shows that the algorithm is linear. Randomly, I took `N` implications, with `N in [1..1000]`, over a number of variables between 1 and 26. After that I do one thousand of satisfiability test for each `N`. Finally I plot the average in millisecond.

# Answer
> 2 votes
## APL, 49 bytes

```
{×∧/∨/¨≢¨¨{(2⊃¨⍵/⍨0=≢¨⊃¨⍵)∘{x y←⍵⋄(x~⍺)y}¨⍵}⍣≡⊢⍵}

```

This function takes an array of implications, where each implication is a 2-element array, with the first element containing the variables before the arrow and the second containing the variable after the arrow if there is one.

E.g. `[A,B,C -> D; B,C -> E; -> A; B -> ]` is represented as:

```
('ABC' 'D')('BC' 'E')('' 'A')('B' '')

```

The elements need not be letters but could be anything as long as they can be compared.

Explanation:

* `{`...`}⍣≡⊢⍵`: run the following function on the input until a fixpoint is found

+ `(`...`)∘`: Find the current units:

    - `⊃¨⍵`: For each implication in the input, take the first element
        - `0=≢¨`: See which are empty
        - `⍵/⍨`: Select those implications
        - `2⊃¨`: Select the second element from each
    + `{`...`}¨⍵`: For each implication, given the units:

    - `x y←⍵`: unpack the implication into its first and second component
        - `(x~⍺)y`: remove the previous units from the first component and leave the second one alone
* `≢¨¨`: find the length of each inner element. If the clause is unsatisfiable, there is at least one (0,0) element (i.e. `[] -> []`, True → False).
* `∨/¨`: for each implication, find the GCD of the lengths of its parts. If unsatisfiable, this will be `0`.
* `∧/`: find the LCM of all the GCDs. If unsatisfiable, this will be `0`.
* `×`: return the sign, so a boolean value is returned (0 for unsatisfiable, 1 for satisfiable).

Polynomiality proof:

The main loop (`{`...`}⍣≡`) will run until there are no more reducible implications. Each step, all current known facts are removed from the left hand side of each implication. Because each implication can only have 0 or 1 variables on its right hand side, the size of the set of knowable facts is bounded by the amount of implications, meaning the loop will run at most `n` times.

The main loop further contains a number of maps over the list of implications, meaning the total running time is `O(n^2)`.

Link to tests cases being run on tio.run.

# Answer
> 0 votes
# JavaScript (Node.js), 69 bytes

```
f=x=>x.some(t=>t.a.every(v=>x[~v])&!x[~t.b]&&[x[~t.b]=1])?f(x):!x[~0]

```

Try it online!

Flow each `true` and check if `false` is true

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


title: Un-Merge a List

text:
# Question
Title: Un-Merge a List
# Introduction

Most of you are familiar with the merge sort algorithm for sorting a list of numbers. As part of the algorithm, one writes a helper function called `merge` that combines two sorted lists into one sorted list. In Python-like pseudocode, the function usually looks something like this:

```
function merge(A, B):
  C = []
  while A is not empty or B is not empty:
    if A is empty:
      C.append(B.pop())
    else if B is empty or A[0] ≤ B[0]:
      C.append(A.pop())
    else:
      C.append(B.pop())
  return C

```

The idea is to keep popping the smaller of the first elements of `A` and `B` until both lists are empty, and collect the results into `C`. If `A` and `B` are both sorted, then so is `C`.

Conversely, if `C` is a sorted list, and we split it into any two subsequences `A` and `B`, then `A` and `B` are also sorted and `merge(A, B) == C`. Interestingly, this does not necessarily hold if `C` is not sorted, which brings us to this challenge.

# Input

Your input is a permutation of the first `2*n` nonnegative integers `[0, 1, 2, ..., 2*n-1]` for some `n > 0`, given as a list `C`.

# Output

Your output shall be a truthy value if there exist two lists `A` and `B` of length `n` such that `C == merge(A, B)`, and a falsy value otherwise. Since the input contains no duplicates, you don't have to worry about how ties are broken in the `merge` function.

# Rules and Bonuses

You can write either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

Note that you are not required to compute the lists `A` and `B` in the "yes" instances. However, if you actually output the lists, you receive a **bonus of -20%**. To claim this bonus, you must output only one pair of lists, not all possibilities. To make this bonus easier to claim in strongly typed languages, it is allowed to output a pair of empty lists in the "no" instances.

Brute forcing is not forbidden, but there is a **bonus of -10%** for computing all of the last four test cases in under 1 second total.

# Test Cases

Only one possible output is given in the "yes" instances.

```
[1,0] -> False
[0,1] -> [0] [1]
[3,2,1,0] -> False
[0,3,2,1] -> False
[0,1,2,3] -> [0,1] [2,3]
[1,4,0,3,2,5] -> False
[4,2,0,5,1,3] -> [4,2,0] [5,1,3]
[3,4,1,2,5,0] -> [4,1,2] [3,5,0]
[6,2,9,3,0,7,5,1,8,4] -> False
[5,7,2,9,6,8,3,4,1,0] -> False
[5,6,0,7,8,1,3,9,2,4] -> [6,0,8,1,3] [5,7,9,2,4]
[5,3,7,0,2,9,1,6,4,8] -> [5,3,7,0,2] [9,1,6,4,8]
[0,6,4,8,7,5,2,3,9,1] -> [8,7,5,2,3] [0,6,4,9,1]
[9,6,10,15,12,13,1,3,8,19,0,16,5,7,17,2,4,11,18,14] -> False
[14,8,12,0,5,4,16,9,17,7,11,1,2,10,18,19,13,15,6,3] -> False
[4,11,5,6,9,14,17,1,3,15,10,12,7,8,0,18,19,2,13,16] -> [4,17,1,3,15,10,12,7,8,0] [11,5,6,9,14,18,19,2,13,16]
[9,4,2,14,7,13,1,16,12,11,3,8,6,15,17,19,0,10,18,5] -> [9,4,2,16,12,11,3,8,6,15] [14,7,13,1,17,19,0,10,18,5]

```

# Answer
> 3 votes
# Pyth, 39 * 0.9 * 0.8 = 28.08

```
#aY->QxQeS-QsY&YsY)KfqylTlQmsdty_Y%tlKK

```

This program clams all two bonuses. It prints a pair of lists, if un-merging is possible, else an empty list, which is a falsy value in Pyth (and Python).

```
Input:  [5,3,7,0,2,9,1,6,4,8]
Output: ([9, 1, 6, 4, 8], [5, 3, 7, 0, 2])
Input:  [5,7,2,9,6,8,3,4,1,0]
Output: [] (falsy value)

```

You can test it online, but it may be a bit slower than the offline version. The offline version solves each of the test cases in \<0.15 seconds on my laptop.

Probably (one of) the first time, a Pyth solution uses actively **Exceptions** (it saved at least 1 char). It uses the same idea as Peter Taylor's solution.

```
                         preinitialisations: Q = input(), Y = []
#                 )     while 1: (infinite loop)
        eS-QsY             finds the biggest, not previous used, number
      xQ                   finds the index
    >Q                     all elements from ... to end
   -          &YsY         but remove all used elements
 aY                        append the resulting list to Y

When all numbers are used, finding the biggest number fails,
throws an exception and the while loop ends.
This converts [5,3,7,0,2,9,1,6,4,8] to [[9, 1, 6, 4, 8], [7, 0, 2], [5, 3]]

        msdty_Y  combine the lists each for every possible subset of Y (except the empty subset)
 fqylTlQ         and filter them for lists T with 2*len(T) == len(Q)
K                and store them in K

%tlKK        print K[::len(K)-1] (prints first and last if K, else empty list)

```

# Pyth, 30 * 0.9 = 27.0

I haven't really tried solving it without printing the resulting lists. But here's a quick solution based on the code above.

```
#aY->QxQeS-QsY&YsY)fqylsTlQtyY

```

I basically only removed the print statement. The output is quite ugly though.

```
Input:  [0,1,2,3]
Output: [[[3], [2]], [[3], [1]], [[2], [1]], [[3], [0]], [[2], [0]], [[1], [0]]] (truthy value)
Input:  [5,7,2,9,6,8,3,4,1,0]
Output: [] (falsy value)

```

Try it online.

# Answer
> 4 votes
## GolfScript (35 * 0.9 = 31.5)

```
{.$-1>/~,)\.}do;]1,\{{1$+}+%}/)2/&,

```

The online demo is quite slow: on my computer, it runs all of the tests in under 0.04 seconds, so I claim the 10% reduction.

### Explanation

> The suffix of C which starts with the largest number in C must come from the same list. Then this reasoning can be applied to (C - suffix), so that the problem reduces to subset sum.

# Answer
> 2 votes
# APL, 62 50 44 * 90% = 39.6

```
{(l÷2)⌷↑(⊢∨⌽)/(2-/(1,⍨⍵≥⌈\⍵)/⍳l+1),⊂l=⍳l←⍴⍵}

```

Try it here.

# Answer
> 0 votes
# JavaScript (Node.js), 103 bytes * 0.9 * 0.8

```
f=(x,u,a=[],b=[],y=[...x],c=y.pop())=>b[0]<a[0]?0:1/c?f(y,~-u,[c,...a],b)||f(y,~u,[c,...b],a):u?0:[a,b]

```

Try it online!

~~JavaScript (Node.js), 105 bytes * 0.9 * 0.8
```
f=(x,u=0,a=[],b=[],y=[...x],c=y.pop())=>b[0]<a[0]?0:1/c?f(y,u-1,[c,...a],b)||f(y,~u,[c,...b],a):u?0:[a,b]

```
Try it online!
JavaScript (Node.js), 115 bytes * 0.9 * 0.8
```
f=(x,u=0,a=[],b=[],y=[...x],c=y.pop())=>1/c?!(b[0]<c)&&f(y,u-1,[c,...a],b)||!(a[0]<c)&&f(y,~u,[c,...b],a):u?0:[a,b]

```
Try it online!
~~

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


title: ETAOIN SHRDLU golf

text:
# Question
Title: ETAOIN SHRDLU golf
**Short and sweet description of the challenge:**
Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input.

**Really long, dry and thorough specification:**

* Your program/function will receive as input a string of text, which will contain one or more uppercase and/or lowercase letters and may also contain punctuation, numerals, symbols, and other non-alphabetic characters.
* The program/function must output **only** the 26 UPPERCASE letters of the English alphabet, including those that do not appear in the input, ordered from most to least frequent based on how many times they appear in the input.
* The frequency is calculated case-insensitively, but the output must be in uppercase.
* If two or more letters have the same frequency, they may be in any order.
* The only other output that is allowed is optional leading or trailing whitespace, such as a trailing newline. No other output inclusing whitespace is allowed.
* Undefined behavior is allowed for input that does not contain any letters.

---

**Example input:**

```
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent vitae erat velit. Mauris gravida euismod libero ut tincidunt. Phasellus elit dui, consectetur et egestas in, aliquam vitae diam. Donec eget varius ante. Vestibulum cursus diam aliquet, egestas orci quis, placerat dolor. Proin vel nisi lectus. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Aliquam erat volutpat. Etiam libero tortor, ornare id dui eget, posuere dignissim libero. Pellentesque commodo consequat volutpat. Integer hendrerit sapien libero, vel viverra augue facilisis sit amet. Quisque consectetur eget nisl quis dignissim. Ut lacinia pretium quam a placerat.
Morbi sed interdum risus, nec pretium lectus. Morbi imperdiet est id accumsan molestie. Duis sed fermentum nisl. Nunc vitae augue mattis, dictum lectus vel, accumsan nisl. Sed ultricies adipiscing rhoncus. Vivamus eu lacus a enim venenatis eleifend. Praesent consectetur tortor non eleifend ultricies. Mauris et odio posuere, auctor erat at, fringilla est. Proin in vestibulum erat. Maecenas congue commodo ante vel varius. Sed tempus mi ut metus gravida, nec dictum libero dapibus. Morbi quis viverra elit. Ut pharetra neque eget lacus tincidunt dictum. Fusce scelerisque viverra tellus et pretium.
Fusce varius adipiscing odio. Nulla imperdiet faucibus sem, at rhoncus ipsum adipiscing vitae. Phasellus imperdiet congue lacus et mollis. Nullam egestas mauris magna, et mollis lectus varius ut. Sed sollicitudin adipiscing dolor, vel elementum elit laoreet molestie. Aliquam nec nulla vel sem ultrices ullamcorper. Nullam nec felis magna. Duis sodales orci non justo aliquam tempus. Integer mi diam, tempor sed vulputate et, varius et nunc. Vestibulum sodales ipsum id mi pharetra, ut convallis mi accumsan. Sed dictum volutpat vestibulum.
Quisque ac dolor sagittis, aliquam libero at, euismod enim. Nulla ullamcorper posuere nulla vitae varius. Nam at dolor non libero elementum pellentesque in in lorem. Fusce porttitor turpis in quam placerat varius. Donec lorem orci, condimentum eu sapien sit amet, aliquet commodo magna. Quisque sed lectus sit amet arcu euismod accumsan et non nunc. Phasellus placerat congue metus, feugiat posuere leo dictum quis. Sed ultricies feugiat eros dignissim bibendum.
Mauris scelerisque consectetur libero eget varius. Aenean neque nunc, ullamcorper vitae orci in, auctor ornare sapien. Nam lacinia molestie imperdiet. Nam vitae mattis nibh. Vestibulum consequat tellus ac nisi sagittis pulvinar. Nullam mollis ornare quam, et venenatis leo porttitor sit amet. Nulla urna neque, dignissim non orci ut, volutpat ultrices erat. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Pellentesque vestibulum tellus nec eros faucibus porta.

```

**Example output:**

```
EITUSALNROMCDPVGQBFHJKWXYZ

```

Note: there is a 5 way tie between `KWXYZ` for that input.

## Edit:

The competition is over! Thanks to everyone who participated. And now for the winner(s!): Both Dennis' CJam and isaacg's Pyth answers came in at a whopping 19 characters. Taking Dennis' advice, I'm going to mark his answer as accepted because his was the first to reach 19 characters. Honorable mentions go to Ilmari Karonen's third-place Golfscript answer at 22 chars as well as undergroundmonorail's 75-char Python answer that got the most upvotes. Once again, thanks to everyone who participated!

# Answer
# CJam, ~~21~~ 19 bytes

```
qeu:A;'[,65>{A\-,}$

```

Try it online.

### Example

```
$ cjam etaoin.cjam <<< "~XyxY YyxZ"
YXZABCDEFGHIJKLMNOPQRSTUVW

```

(no newline)

### How it works

```
qeu:A; " Read from STDIN, convert to uppercase, save in the variable “A” and discard, ";
'[,    " Push an array of all ASCII characters before “[” (NUL to “Z”).               ";
65>    " Remove the first 64 characters (NUL to “@”).                                 ";
{      " Sort the array of characters by the following mapping:                       ";
  A\   " Swap the character with the string saved in variable “A”.                    ";
  -    " Remove all occurrences of the character from the string.                     ";
  ,    " Push the length of the string.                                               ";
}$     "                                                                              ";

```

More occurrences means more characters get removed, so the most frequent characters appear at the beginning of the array.
> 26 votes

# Answer
# Python 2 or 3 - ~~77~~ 75 bytes

```
f=lambda s:''.join(sorted(map(chr,range(65,91)),key=s.upper().count))[::-1]

```

I had an answer before that grabbed input from STDIN, but I realized it was technically invalid. I used `input()` which gets only a single line, but the question's example input implies that it should handle multiple lines at once. To meet spec, I turned my answer into a function that takes a string argument. To my surprise, it was two bytes smaller! It didn't occur to me that `print(...)` and `input()` were longer than `f=lambda s:` and `s`.

This also makes the answer compatible with both Python 2 and Python 3. Originally it was only Python 3, because it used `input()` (which was called `raw_input()` in 2). Now that it's a function, it works in both.

**Explained**

```
                                  range(65,91)                              # The numbers 65 to 90
                          map(chr,range(65,91))                             # Convert to ASCII

                                                    s                       # The input string
                                                    s.upper()               # Convert to uppercase
                                                    s.upper().count         # Function literal for 'how many times the argument appears in the string'

                   sorted(map(chr,range(65,91)),key=s.upper().count)        # Sort by that function
           ''.join(sorted(map(chr,range(65,91)),key=s.upper().count))       # Concatenate to string
           ''.join(sorted(map(chr,range(65,91)),key=s.upper().count))[::-1] # Step through by -1 (i.e. reverse string)

  lambda s:''.join(sorted(map(chr,range(65,91)),key=s.upper().count))[::-1] # Make it a function (`return` is implicit for lambdas)
f=lambda s:''.join(sorted(map(chr,range(65,91)),key=s.upper().count))[::-1] # Give it a name

```
> 43 votes

# Answer
# Bash, 65 bytes

```
(tr a-z A-Z;echo {A..Z})|fold -1|sort|uniq -c|sort -nr|tr -dc A-Z

```

### Example

```
$ bash etaoin.sh <<< "~AbaB BbaC"
BACZYXWVUTSRQPONMLKJIHGFED

```

### How it works

```
(              #
  tr a-z A-Z   # Turn lowercase into uppercase letters.
  echo {A..Z}  # Print all uppercase letters.
) |            #
fold -1 |      # Split into lines of length 1.
sort |         # Sort those lines (required for piping to uniq).
uniq -c |      # Print the frequencies of all lines.
sort -nr |     # Sort by frequency (reversed).
tr -dc A-Z     # Remove everything that's not an uppercase letter.

```
> 15 votes

# Answer
# Pyth 1.0.2, 19 20

```
=ZUwsVm;dSm[cZkk)UG

```

Try it here: http://ideone.com/fork/YlWpEJ

Learn more about Pyth here: http://esolangs.org/wiki/Pyth

Example:

> Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input.

Gives:

> TENOHARSIULGFPYDCBWQMZXVKJ

Explanation:

`=ZUw`: Convert input to uppercase and store in Z.

`sV`: Print the sum of the reverse of

`m;d`: The last entries of

`S`: Sorted by their first entry, in increasing order

`m[cZkk)`: The lists \[count of k in Z, k\]

`UG`: For k in the uppercase letters.

Rough Python equivalent:

```
G='abcdefghijklmnopqrstuvwxyz'
Z=copy(upper(input()))
print(_sum(rev(_map(lambda d:d.pop(),sorted(_map(lambda k:_list(count(Z,k),k),upper(G)))))))

```

---

This is not entry, I just thought people might like to see it. In Pyth 1.0.4, the following program is a solution in 10 characters:

```
JUwo_cJNUG

```

Explanation:

`JUw`: Convert input to uppercase and store in J.

`o`: (Print) Sort by

`_cJN`: -1\*(count of N in J)

`UG`: Over N in the uppercase letters.

It is not a legal solution because several of the changes from Pyth 1.0.2 to 1.0.4, including the addition of the `o`, sort by, function, were in response to this problem.
> 12 votes

# Answer
# Javascript (*ES6*) 119 117

**Edit:** (-2) Removed the need for `toUpperCase` using a case-insensitive RegEx in the `split` call.

```
a=prompt(f=x=>a.split(RegExp(x,'i')).length)
alert([...'ABCDEFGHIJKLMNOPQRSTUVWXYZ'].sort((b,c)=>f(c)-f(b)).join(''))

```

**Alternative (same length):** Condensed the sort and character counting into a single function.

```
a=prompt()
alert([...'ABCDEFGHIJKLMNOPQRSTUVWXYZ'].sort(f=(b,c)=>c?f(c)-f(b):a.split(RegExp(b,'i')).length).join(''))

```

# As a function: 105 104

**Edit:** (-1) Condensed the sort and character counting into a single function.

```
F=a=>[...'ABCDEFGHIJKLMNOPQRSTUVWXYZ'].sort(f=(b,c)=>c?f(c)-f(b):a.split(RegExp(b,'i')).length).join('')

```
> 11 votes

# Answer
# GolfScript, 22 chars

```
:?91,+-26>{.32+]?\-,}$

```

Try it online.

### Explanation:

* `:?` assigns the input string to the symbol `?`. (I use a punctuation symbol so that the following number `91` is not parsed as part of the symbol name.)
* `91,` constructs a list of the numbers from 0 to 90 (ASCII code of `Z`).
* `+` appends this list to the input string, thereby converting it from an array of ASCII codes to a string (and conveniently also removing the input string from the stack).
* `-26>` takes the last 26 characters of this string, producing a string containing the uppercase ASCII letters from `A` to `Z`.
* The `{ }$` applies the code block to all the characters in the input string, and sorts those characters according to the result.
* Inside the code block, `.` duplicates the character and `32+` converts the copy from uppercase to lowercase. The `]` collects these two characters into an array, `?\-` takes the input string stored in `?` and removes all occurrences of the characters in the array from it, and `,` counts the length of the remaining string, which will be the sort key. The characters will be sorted in ascending order by this key, and thus in descending order by number of occurrences.
> 10 votes

# Answer
# Haskell, 110 bytes

```
import Data.List
import Data.Char
a%f=compare(f a).f
f t=sortBy(% \c->length$filter((/=c).toUpper)t)['A'..'Z']

```

Example usage:

```
λ> f "Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input."
"ETNAHORISULFGPBCDYMQWJKVXZ"

```
> 8 votes

# Answer
## Ruby 2.0, 53 characters

**EDIT**: Fixed to work correctly with multiline strings, thanks @durron597!

```
f=->s{$><<(?A..?Z).sort_by{|c|-s.upcase.count(c)}*''}

```

Creates a function called `f` which can be used as follows:

```
f['jackdaws love my big sphinx of quartzzz']

```

Prints to STDOUT:

```
AZOSICGHEJKLMBFPQRDTUVWXYN

```
> 7 votes

# Answer
## Perl, ~~54~~ 46 bytes

**UPDATE:** after further optimizations it could be squeezed to **46** bytes: (thx dennis for `-n`/`{}` hack; chinese perl goth for `<=>`-\>`-` hack)

```
s/./$h{uc$&}++/eg}{say sort{$h{$b}-$h{$a}}A..Z

```

It is to be run with run with `perl -nE`

Original solution (does not need special Perl options):

```
s/./$h{uc$&}++/egfor<>;print sort{$h{$b}<=>$h{$a}}A..Z

```

Verified in Perl 5.8.3, 5.14.2

*If you get a warning, separate `eg` and `for` with a space (+1 char), if you mind*

example usage:

```
$ python -c 'import this' | perl -le 's/./$h{uc$&}++/egfor<>;print sort{$h{$b}<=>$h{$a}}A..Z' 2>/dev/null
ETAISONLRHPBUCDYMFGXVWKZJQ

```

EXPLANATION: On each character (`.`) of each input line (`for<>`), apply a substitution "pattern", which in fact is evaluated as an expression (`e` flag of the `s///`), that increments an upcased (`uc`) character (`.`/`$&` is shorter than more obvious `(.)`/`$1`) count in the (uninitialized) hash (`%h`). Then, the letter frequency hash is used in a sort comparison function to print out upper-case alphabet in the right order.
> 6 votes

# Answer
# R, 123 bytes

The code is improved thanks to the suggestions by @RichieCotton.

```
text <- "Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input."

f=function(x){b=plyr::count(toupper(strsplit(x,"")[[1]]));c=merge(LETTERS,b,all.x=T);paste(c[order(-c$freq),1],collapse="")}

f(text)

```

Output:

```
> f(text)
[1] "ETNAHORISULFGPBCDYMQWJKVXZ"

```
> 5 votes

# Answer
# AppleScript, 278

I noticed that `"a" = "A"` is true in AppleScript. I can use this in code golf, but the rest of the script is too wordy. I used AppleScript 1.8.3.

This defines a function `f`. If you add `f("a string")` at the bottom of the script and run it in the Script Editor, it will show the result.

```
on c(n)
ASCII character(64+n)
end
on f(s)
set{a,r}to{{},""}
repeat with i from 1 to 26
set j to 0
repeat with b in s
if b&""=c(i)then set j to j+1
end
set a to a&j
end
repeat with j from 0 to(count s)
repeat with i from 1 to 26
if a's item i=j then set r to c(i)&r
end
end
r
end

```

Formatted and commented:

```
-- Returns nth letter of alphabet.
on c(n)
    ASCII character (64 + n)
end c

-- Returns letters in s sorted by frequency.
on f(s)
    -- a: list of letter counts
    -- r: resulting string
    set {a, r} to {{}, ""}

    -- For each letter from A to Z,
    -- count letters in string s.
    repeat with i from 1 to 26
        set j to 0
        repeat with b in s
            -- Can't use b = c(i), because
            -- b is a reference to a string
            -- and = never dereferences its
            -- operands. Get contents of b,
            -- here by coercing b to string.
            if b & "" = c(i) then set j to j + 1
        end repeat
        -- Set item i of a to count j.
        set a to a & j
    end repeat

    -- Sort letters by frequency.  Do a counting sort
    -- because AppleScript lacks a sort command.
    repeat with j from 0 to (count s)
        repeat with i from 1 to 26
            if a's item i = j then set r to c(i) & r
        end repeat
    end repeat
    r
end f

-- Example call:
f("Now is the time for all good men to come to the aid of their country.")
-- Result: "OTEIRNMHLFDCAYWUSGZXVQPKJB"

```
> 5 votes

# Answer
## VBScript 181 109

Updated to use a completely different algorithm. Beats JavaScript!

Pretty:

```
dim b(99):i=ucase(inputbox(k))
for y=65to 90
    c=chr(y)
    a=len(replace(i,c,k))
    b(a)=c+b(a)
next
msgbox join(b,k)

```

Golfed:

```
dim b(99):i=ucase(inputbox(k)):for y=65to 90:c=chr(y):a=len(replace(i,c,k)):b(a)=c+b(a):next:msgbox join(b,k)

```
> 4 votes

# Answer
## J 41 35 Bytes

```
(u:65+i.26)([\:[#/.~@,e.~#])toupper

```

Demo:

```
i=: 'This is a test to see whether this is still working'
(u:65+i.26)([\:[#/.~@,e.~#])toupper i
STIEHLORWAGKNBCDFJMPQUVXYZ

```

Explanation:

```
(u:65+i.26) & ( [ \: [ #/.~@,e.~#]) toupper) )
ABCDE...          |    |    |   |      uppercase the right argument
                  |    |    |   \copy from right only member from left
                  |    |     \append the left argument
                  |    \ Afterwards Count apperances of each letter
                  \ Sort the left according to the appearances

```

The key is to append the left array, such that all letters are available, and already in order. A funny consequence of using a noun as third tine to the fork is that it works as verb as well as as phrase.
> 4 votes

# Answer
## SAS - 217 (I think)

Input should be placed on the line after the cards4 statement, or on the appropriate punch cards for your system. I think this approach saves a few characters vs. attempting to quote the input.

```
data a;
input;
S = upcase(compress(_INFILE_,,'ak'));
do i=1 to length(S);
l=substr(S,i,1);
output;
end;
cards4;
;;;;
run;
proc sql;
select l into :o separated by '' from
(select l, 1/count(l) as f from a group by l) order by f;
quit;

```

I'm aware that this doesn't meet the full spec, as it only returns characters that appear in the input string. I might need to rethink this a bit.
> 4 votes

# Answer
# C++, 185 183 179 177 bytes

Not expected to win, of course (can C++ ever win?) but a fun exercise nonetheless.

```
#include <algorithm>
#include <stdio.h>
int f[256],p;main(){for(p=65;p<91;p++)f[p]=p;while(~(p=getchar()))f[p&95]+=256;p=256;std::sort(f,f+p);while(p--)f[p]&95&&putchar(f[p]);}

```

Explanation:

```
#include <algorithm>         // for std::sort
#include <stdio.h>           // for getchar, putchar
int f[256],p;                // declare an array of count-prefixed chars, and a counter
main(){
    for(p=65;p<91;p++)       // 65 == 'A', 91 == the character after 'Z'
        f[p]=p;              // set the character for the slot
    while(~(p=getchar()))    // read characters until EOF
        f[p&95]+=256;        // increment the packed count for the character stripped of the 'lowercase bit'
    p=256;                   // start a countdown
    std::sort(f,f+p);        // sort the array
    while(p--)               // do the countdown
        f[p]&95 &&           // if the masked-off character is set...
          putchar(f[p]);     // print it
}

```
> 4 votes

# Answer
## Groovy - ~~130~~ ~~123~~ ~~115~~ ~~112~~ ~~98~~ 92

As per @cfrick's advice (twice!):

```
f={('A'..'Z').collectEntries{c->[c,it.grep(~/(?i)$c/).size()]}.sort{-it.value}*.key.join()}

```

A small test (shamelessly stolen from @jpjacobs):

```
assert f('This is a test to see whether this is still working') ==
    'STIEHLORWAGKNBCDFJMPQUVXYZ'

```

And the proposed test is also passing
> 4 votes

# Answer
# Jelly, 9 bytes

```
ØAŒuċ¥@ÞU

```

# Explanation

```
ØAŒuċ¥@ÞU  Main Link
       Þ   Sort
ØA         The uppercase alphabet by
  Œuċ¥@    number of occurrences in the input:
  Œu       Uppercase
    ċ      Count occurrences
     ¥     Grammar: Last two links as a dyad
      @    Swap arguments
        U  Reverse (because sort sorts up)

```

This reads as "sort the uppercase alphabet by the number of occurrences in the input uppercased, reversed", which is a rather literal translation of the challenge :P

Try it online!

This challenge was linked to Jelly HyperTraining where we solved the challenge. I posted this because I was the first to reach 10 bytes.

-1 byte thanks to Erik the Outgolfer (JHT teacher)
> 4 votes

# Answer
# J - ~~38~~ 35 char

A function taking input on the right as a string. Not a winner, but it was fun to write.

```
(u:65+i.26)([\:[#/.~@,e.~#])toupper

```

Explained:

* `toupper` is a verb in the standard library that upcases a string. That then becomes the right argument of the verb, while the left argument is the alphabet: ASCII codepoints 65 to 90.
* `[` and `,e.~#])` selects (`#`) those letters in the right arg (`]`) that are elements of (`e.~`) the left, and then prepends (`,`) the left arg (`[`). To wit, we keep only the uppercase chars, and add a single copy of the alphabet to the end, to make sure we catch them all.
* `#/.~@` then gives the frequencies of each character. It so happens that this is given in alphabetical order, so right afterwards we can downsort (`\:`) the alphabet (the left argument `[`).

A quick lazy example below. Feel free to try it for yourself at tryj.tk.

```
   (u:65+i.26)([\:[#/.~@,e.~#])toupper 'Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input.'
ETNAHORISULFGPBCDYMQWJKVXZ

```
> 3 votes

# Answer
## VBScript 157 156 bytes

Edit: changed msgbox(p) to msgbox p

More readable:

```
s=ucase(InputBox(z))    'z is empty.
L=len(s)
Dim a(255)
for i=1to L
    x=asc(mid(s,i))
    a(x)=a(x)+1
next
for t=0to L
    For i=65To 90
        If a(i)=t then p=chr(i)&p
    next
next
msgbox p

```

Golfed: (155 characters + 1 carriage return)

```
s=ucase(InputBox(z)):L=len(s):Dim a(255):for i=1to L:x=asc(mid(s,i)):a(x)=a(x)+1:next:for t=0to L:For i=65To 90:If a(i)=t then p=chr(i)&p
next:next:msgbox p

```

I had it at 171 earlier with code that I found more interesting, but comfortablydrei's sorting method is shorter and requires len(s), which makes a "for" shorter than the "while" for the first loop. (yawn)

```
's=UCase(InputBox(Z))&8 'just need any extra character.  0-7 don't work because &7 is octal

s=UCase(InputBox(Z)) 'nevermind
Dim a(999)
While Len(s)
    x=Asc(s) 'returns ascii of first char
    a(x)=a(x)-1 'going negative saves a character later...
    s=Mid(s,2) 'doesn't care if you run out of string
Wend
for j=1 to 26 'this used to be   While Len(p)<26
    For i=65To 90
        If a(i)<a(y) Then y=i 'it is barely not worth it to do a(i)+a(i+32)>a(y) here to skip the ucase() above
    Next
    p=p&Chr(y)
    a(y)=1 'if I didn't go negative this would have to be -1.  arrays default to 0.
Next
MsgBox(p)

```
> 3 votes

# Answer
# Perl, 78 bytes

```
undef$/;$i=<>;$r{$i=~s/$_//gi}.=$_ for A..Z;print$r{$_}for sort{$b<=>$a}keys%r

```
* Only the 26 uppercase ASCII letters without any white space are output in frequency order.
* Tied characters are given in alphabetic order.

Result for the example in the question:

```
EITUSALNROMCDPVGQBFHJKWXYZ

```

**Ungolfed:**

```
# read input
# ----------
undef $/; # disable input separator
$i = <>;  # $i holds the complete input as one string

# analyze
# -------
# For each uppercase letter (A upto Z) its occurences are counted
# via the number of substitutions made by s/$_//gi. The lowercase
# letter is included via modifier "i".
#
# The occurrence count is then used as key for hash %r.
# The uppercase letter is appended to the value of that hash entry.
$r{$i =~ s/$_//gi} .= $_ for A..Z;

# output
# ------
# The hash keys are sorted numerically in reverse order by
# the specified sort function.
print $r{$_} for sort {$b<=>$a} keys %r

```
> 3 votes

# Answer
## T-SQL 178

Basically, this is my VBScript solution but implemented in SQL.

This is XML output abuse to concatenate a column. In practical use, it can be joined to an outer table to emulate `GROUP_CONCAT` functions in MySQL and others.

Declaring the `@` variable:

```
DECLARE @ CHAR(1024)= 'enter your text here';

```

Code:

```
with y AS(
    SELECT UPPER(@)i,0l,91y
    UNION ALL
    SELECT i,len(replace(i,char(y-1),'')),y-1
    FROM y
    WHERE y>65
)
SELECT LTRIM(
(
    SELECT char(y)
    FROM y
    WHERE y<91
    ORDER BY l
    FOR XML PATH(''))
)

```
> 3 votes

# Answer
## C# (and LINQ) 255 226 210 Bytes

Using Patrick Huizinga's advice, the query syntax is now shorter:

```
namespace System.Linq{class P{static void Main(string[]a){Console.Write((from c in(a[0]+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").ToUpper()where c>'@'&&c<'['group c by c into g orderby-g.Count()select g.Key).ToArray());}}}

```

**Explanation:**

```
Console.Write(
    (from c //declare our range variable
       in (a[0] + "ABCDEFGHIJKLMNOPQRSTUVWXYZ").ToUpper() //declare the datasource
     where c > '@' && c < '[' //include only letters
     group c by c into g //run of the mill group by
     orderby -g.Count() //order by descending
     select g.Key //we only want the actual letters
     ).ToArray() //mash it all into an array
  );

```

**Equivalent method syntax (217):**

```
namespace System.Linq{class P{static void Main(string[]a){Console.Write((a[0]+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").ToUpper().GroupBy(c=>c).OrderBy(c=>-c.Count()).Where(c=>c.Key>'@'&&c.Key<'[').Select(c=>c.Key).ToArray());}}}

```

**Original post:**

> ```
> namespace System.Linq{class P{static void Main(string[]a){(a[0]+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").ToUpper().GroupBy(c=>c).OrderByDescending(c=>c.Count()).Where(c=>c.Key>'@'&&c.Key<'[').ToList().ForEach(c=>Console.Write(c.Key));}}}
>
> ```
>
> This is my first ever submission and I should be doing things at work but this just looked like so much fun because I felt like I could actually participate for once.
>
> **Explanation:**
>
> ```
> (a[0] + "ABCDEFGHIJKLMNOPQRSTUVWXYZ") //ensure each character appears once
>   .ToUpper()
>   .GroupBy(c => c) //get access to .Count()
>   .OrderByDescending(c => c.Count())
>   .Where(c => c.Key > '@' && c.Key < '[') //exclude anything other than letters
>   .ToList() //Only lists have a .ForEach() :(
>   .ForEach(c => Console.Write(c.Key)); //print output
>
> ```
>
> I never use the method syntax for LINQ so this was a learning experience for me :) also thinking about it now I could save 2 bytes by replacing the character literals with their integer counterparts, but, meh.
>
> Shortened thanks to tips from ProgramFOX and Num Lock :)
>
> The equivalent query syntax (slightly longer):
>
> ```
> (from c in (a[0]+"ABCDEFGHIJKLMNOPQRSTUVWXYZ").ToUpper() where c>'@'&&c<'[' group c by c into g orderby g.Count() descending select g.Key).ToList().ForEach(c=>Console.Write(c));
>
> ```
> 3 votes

# Answer
# PHP - 105 bytes

```
<?preg_filter(~‹§æ“Ö¢‹ö,'$f[$0&ﬂ]++',join('',range(a,z)).$argv[1]);arsort($f);foreach($f as$l=>$F)echo$l;

```

Here's a hexdump, cause of the special characters:

```
0000000 3c 3f 70 72 65 67 5f 66 69 6c 74 65 72 28 7e dc
0000010 a4 be d2 85 a2 dc 9a 2c 27 24 66 5b 24 30 26 df
0000020 5d 2b 2b 27 2c 6a 6f 69 6e 28 27 27 2c 72 61 6e
0000030 67 65 28 61 2c 7a 29 29 2e 24 61 72 67 76 5b 31
0000040 5d 29 3b 61 72 73 6f 72 74 28 24 66 29 3b 66 6f
0000050 72 65 61 63 68 28 24 66 20 61 73 24 6c 3d 3e 24
0000060 46 29 65 63 68 6f 24 6c 3b
0000069

```

And a slightly less golfed version:

```
<?
preg_filter(           // regular expression
  "#[A-z]#e",          // matches every letter + 'eval' flag
  '$f[$0&ﬂ]++',        // so this code runs for every letter
                       // $f is an array whose indices are uppercase letters
                       //   and whose values represent the number of occurences
                       // lowercase is converted to uc with the bitwise and
                       //   ﬂ is 11011111 in binary, every bit except for 32's is set
  join('', range(a,z)) // adding abcdefghijklmnopqrstuvwxyz to the input
    .$argv[1]);        //   because not all letters have to appear in the input
arsort($f);            // sort $f in reverse, maintaining indices
foreach($f as$l=>$F)   //
  echo$l;              // print each index in order

```

Example:

```
 $ php etaoin_shrdlu.php "This function sorts an array such that array indices maintain their correlation with the array elements they are associated with."
 ATIRESHNOCYUWMDLFXZBVGPQKJ

```
> 3 votes

# Answer
# C# in LINQPad - 203 Bytes

I took a different approach to the answer of Logan Dam. I made sure first that every character in the input string is sorted by its appearance and only exists once in the output string. After that I added every missing character from the alphabet to the output string.

```
void e(string i){var a="";foreach(var d in i.ToUpper().GroupBy(x=>x).OrderByDescending(u=>u.Count()))if(d.Key<91&&d.Key>64){a+=d.Key;}for(int x=65;x<91;x++)if(!a.Contains((char)x)){a+=(char)x;}a.Dump();}

```

Sadly it wouldn't beat Logan Dam's answer if I would have made in Visual Studio.

More readable version:

```
void e(string i)
    {
        var a = "";
        foreach (var d in i.ToUpper().GroupBy(x => x).OrderByDescending(u => u.Count()))
        {
            if (d.Key < 91 && d.Key > 64)
            {
                a += d.Key;
            }
        }
        for (int x = 65; x < 91; x++)
        {
            if (!a.Contains((char)x))
            {
                a += (char)x;
            }
        }
        a.Dump();
    }

```
> 3 votes

# Answer
# C++ ~~701~~  ~~322~~  232 bytes

First version 701 bytes (idiomatic STL usage)

```
#define _HAS_TRADITIONAL_STL 1
#include <numeric>
#include <iostream>
#include <iterator>
#include <string>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#define ALL(x) x.begin(), x.end()
using namespace std;
typedef istream_iterator<char> iic;typedef pair<int, char> pic;map<char, int> c;set<pic> d;
void f1(char x) {c[x]--;}
void f2(const pic &p) {d.insert(make_pair(p.second, p.first));}
int main(){string s(26, 0);stdext::iota(ALL(s), 65);copy(ALL(s), ostream_iterator<char>(cout));transform(iic(cin), iic(), back_inserter(s), toupper);for_each(ALL(s), f1);for_each(ALL(c), f2);transform(ALL(c2), ostream_iterator<char>(cout), select2nd<pic>());}

```

Expanded clean version :

```
#define _HAS_TRADITIONAL_STL 1
#include <numeric>
#include <iostream>
#include <iterator>
#include <string>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
using namespace std;

typedef istream_iterator<char> iic;
map<char, int> counts;
set<pair<int, char> > counts2;

void docount(char ch) { counts[ch]--; }
void toCounts2(const pair<char, int> &p) { counts2.insert(make_pair(p.second, p.first)); }

int main()
{
    string s(26, 0);
    stdext::iota(s.begin(), s.end(), 65);
    transform(iic(cin), iic(), back_inserter(s), toupper);
    for_each(s.begin(), s.end(), docount);
    for_each(counts.begin(), counts.end(), toCounts2);
    transform(counts2.begin(), counts2.end(), ostream_iterator<char>(cout), select2nd< pair<int, char> >());
}

```

The idea is to demonstrate a "proper" C++ program without any hacks. Ignore the boilerplate and the fact that this only compiles on VC++

**Explanation :**

We fill A to Z into a string with **iota()**, this ensures that when we count the occurrences, each character appears even if it's not in the input.

**transform()** copies character by character from standard input and puts it into the end of s after calling **toupper()** on each one

The count of each character is decremented in the map (by maintaining negative counts we can have descending sort without extra code)

The counts map entries are copied to a set of pairs, swapping (char, count) to (count, char). Since sets are ordered, we get them sorted by decreasing frequency count

Finally we copy the set's content to standard out, using transform, and using **select2nd()** to pick out only the second member of the pair.

The code is fairly readable. A C++11 solution would look much prettier, since we can use lambdas

C++11 version - no need of lambdas, but auto and range based for makes things very clean (come to think of it you can do very similar with regular C++98)

```
#include<iostream>
#include<iterator>
#include<map>
#include<set>
using namespace std;int main(){istream_iterator<char> b(cin),e;map<char,int> c;set<pair<int,char>> d;for(char i='A';i<='Z';++i){--c[i];}for(auto i=b;i!=e;++i){c[toupper(*i)]--;}for(auto p:c){d.insert(make_pair(p.second,p.first));}for(auto p:d){cout<<p.second;}}

```

Expanded version :

```
#include <iostream>
#include <iterator>
#include <map>
#include <set>
using namespace std;
int main()
{
    istream_iterator<char> b(cin), e;
    map<char, int> c;
    set<pair<int, char>> d;
    for(char i = 'A'; i <= 'Z'; ++i) {--c[i];}
    for(auto i = b; i != e; ++i) {c[toupper(*i)]--;}
    for(auto p : c) { d.insert(make_pair(p.second, p.first)); }
    for(auto p : d) { cout << p.second; }
}

```

Next iteration (why read from stdin when we have argv):

```
#include <set>
#include <iostream>
int c[256];int main(int n, char **s){std::set<std::pair<int,char>> d;while(*s[1]){c[toupper(*s[1]++)]--;}for(n=65;n<92;++n){d.insert(std::make_pair(--c[n],n));}for(auto p:d){std::cout<<p.second;}}

```

Expanded version:

```
#include <set>
#include <iostream>
int c[256];
int main(int n, char **s)
{
    std::set<std::pair<int, char>> d;
    while (*s[1])
    {
        c[toupper(*s[1]++)]--;
    }
    for (n = 65; n < 92; n++)
    {
        d.insert(std::make_pair(--c[n], n));
    }
    for (auto p : d)
    {
        std::cout << p.second;
    }
}

```
> 3 votes

# Answer
# APL, ~~26~~ 20 characters

~~`⎕a[⍒+/⎕a∘.=('\w'⎕r'\u0')⍞]`~~

`⎕a[⍒+/⎕a∘.=1(819⌶)⍞]`

-6 thanks to Adam.
> 2 votes

# Answer
## C++ 377

Implements qsort using letter counts in array n to sort alphabet in array A. Run via command line: `golf.exe < in.txt`

```
int n[26],c,k,N;
char A[26];
int C(const void*a,const void*b)
{
int i=(int)(*(char*)a -'A');
int j=(int)(*(char*)b -'A');
return n[j]-n[i];
}
int main()
{
for(;k<26;k++)
{
A[k]=k+'A';
}
N=sizeof(A);
c=getchar();
while(c>0)
{
c=toupper(c);
c=c-'A';
if(c>=0&&c<26)n[c]++;
c=getchar();
}
qsort(A,N,1,C);
for(k=0;k<N;k++)
{
putchar(A[k]);
}
return 0;
}

```
> 2 votes

# Answer
# C, 117(119) bytes

```
x[256];m=1;char c;main(){while(c=getchar()+1)++x[c-1&95];for(;m=x[++c]<x[m]?m:c;x[m<65|m>90||c?m*!c:putchar(m)]=-1);}

```
* Some inputs containing ASCII codes \>= 128 will incorrectly increase letter frequencies. To fix this, replace the constant `95` with `223`, at a cost of 1 extra byte.
* This will terminate early on inputs containing the character with ASCII code 255. To fix this at the cost of 1 extra byte, change `char c;` to just `c;` and `++c` to `c=c+1%255`.
> 2 votes

# Answer
**PowerShell - 139 chars**

First, I'm not an PowerShell expert. Pretty sure there are shorter than this. But was happy with it and decided to share.

```
$a = Read-host
$b = ($a.ToUpper() -replace '[^A-Z]','').ToCharArray() + (65..90|%{[char[]]$_})|Group|sort Count -desc|%{$_.Name}
-join $b

```

---

***How it works:***

```
$a = Read-host            # read from stdin and save into a string var $a
$a.ToUpper()              # Convert the string to UPPERCASE
-replace'[^A-Z]',''       # Remove all non A-Z characters from the str
(...).ToCharArray()       # Convert the inner object (string) to a Char Array
+  (65..90|%{[char[]]$_}) # Create another char array with A-Z chars expanded,
                          #  and append it to the previous one.
|Group                    # Group the char array by value for each element,
                          #  consolidates them and count each char occurrence. Example:
                          #  Count | Name
                          #  ----- | -----
                          #      4 | B
                          #      1 | F
                          #      2 | C
                          #     .. | ..
                          #
|sort Count -desc         # Sorts the previous hash-table by the 'Count' column
                          #   in desc ordering
|%{$_.Name}               # Grab only the 'Name' column from the previous sorted hash-table.
                          # The retuslt obj will be a simple char array again,
                          #   with the letters in the desired order
$b = (...)                # Saves the resulting char array into a new variable $b
-join $b                  # join the resulting char array elements into a single
                          #   string, and print it to stdout.

```
> 2 votes

# Answer
# Ceylon, 98 bytes

```
String f(String s)=>String(('A':26).sort(byDecreasing((Object c)=>s.uppercased.count(c.equals))));

```
> 2 votes

# Answer
# Java 8, ~~171~~ ~~169~~ ~~154~~ ~~139~~ 138 bytes

```
s->{int x=26,a[]=new int[96],i,l;for(int c:s)a[c&~32]++;for(;x-->0;System.out.printf("%c",l),a[l]=-1)for(i=l=65;i<91;i++)l=a[i]>a[l]?i:l;}

```

Surprised there wasn't a Java answer yet.

-27 bytes thanks to *@OlivierGrégoire*.
-6 bytes thanks to *@Nevay*.

**Explanation:**

Try it here.

```
s->{               // Method with character-array parameter and no return-type
  int x=26,        //  Counter-integer, starting at 26
  a[]=new int[96], //  Integer array with 96x 0
  i,l;             //  Index integers
  for(int c:s)     //  Loop (1) over the input-array
    a[c&~32]       //   Convert the character to uppercase, and use it's index in the array
             ++;   //   and increase the integer at that current index by 1
                   //  End of loop (1) (implicit / single-line body)
  for(;x-->0       //  Loop (2) from 26 down to 0 (exclusive)
      ;            //    After every iteration:
       System.out.printf("%c",l+65),
                   //     Print the highest frequency uppercase letter
       a[l]=-1)    //     And then change it's frequency to -1, since we're done with it
    for(i=l=65;    //   Reset both `i` and `l` to 65
        i<91;i++)  //   Inner loop (3) from 65 to 91 (exclusive)
      l=a[i]>a[l]? //    If the current frequency is larger than the `l`'th frequency:
         i         //     Change `l` to the current index `i`
        :          //    Else:
         l;        //     Leave `l` the same
                   //   End of inner loop (3) (implicit / single-line body)
                   //  End of loop (2) (implicit / single-line body)
}                  // End of method

```
> 2 votes

# Answer
# Japt, 8 bytes

```
;Bñ@kX l

```

Try it

```
;Bñ@kX l     :Implicit input of string U
;B           :Uppercase alphabet
  ñ          :Sort by
   @         :Passing each X through the following function
    kX       :  Case-insensitively remove all occurences of X from U
       l     :  Length

```
> 2 votes

# Answer
## Scala 184 170 136 132

```
 def c(s:String){print((('A'to'Z').mkString+s).filter(_.isLetter).groupBy(x=>x.toUpper).toSeq.sortBy(-_._2.size).map(_._1).mkString)}

```

**Full Version**

```
  def c(s: String) {
    print((('A' to 'Z').mkString + s).filter(_.isLetter).groupBy(x => x.toUpper).toSeq.sortBy(-_._2.size).map(_._1).mkString)
  }

```
> 1 votes

# Answer
## R, 111 characters

Another solution in R (using only base R):

```
f=function(x)cat(names(sort(table(factor(strsplit(gsub("[^A-Z]","",toupper(x)),"")[[1]],LETTERS)),d=T)),sep="")

```

Explanation:

`toupper(x)` makes the input upper case.
`gsub("[^A-Z]","",...)` gets rid of everything non alphabetical.
`strsplit(...,"")[[1]]` splits the character string into a vector of single characters.
`factor(...,LETTERS)` makes a factor out of it with uppercase letters as possible levels.
`table(...)` build a frequency table of each factor levels.
`sort(...,d=T)` sorts it according to its values, in decreasing order.
`names(...)` takes the names of the elements (aka the upper case letters).
`cat(...,sep="")` prints the result to stdout with no separator.
And everything wrapped into a function to make it directly comparable with djurio solution.

Usage:

```
> f=function(x)cat(names(sort(table(factor(strsplit(gsub("[^A-Z]","",toupper(x)),"")[[1]],LETTERS)),d=T)),sep="")
> f("Lorem ipsum dolor sit amet, consectetur adipiscing elit. Praesent vitae erat velit. Mauris gravida euismod libero ut tincidunt. Phasellus elit dui, consectetur et egestas in, aliquam vitae diam. Donec eget varius ante. Vestibulum cursus diam aliquet, egestas orci quis, placerat dolor. Proin vel nisi lectus. Class aptent taciti sociosqu ad litora torquent per conubia nostra, per inceptos himenaeos. Aliquam erat volutpat. Etiam libero tortor, ornare id dui eget, posuere dignissim libero. Pellentesque commodo consequat volutpat. Integer hendrerit sapien libero, vel viverra augue facilisis sit amet. Quisque consectetur eget nisl quis dignissim. Ut lacinia pretium quam a placerat.
+ Morbi sed interdum risus, nec pretium lectus. Morbi imperdiet est id accumsan molestie. Duis sed fermentum nisl. Nunc vitae augue mattis, dictum lectus vel, accumsan nisl. Sed ultricies adipiscing rhoncus. Vivamus eu lacus a enim venenatis eleifend. Praesent consectetur tortor non eleifend ultricies. Mauris et odio posuere, auctor erat at, fringilla est. Proin in vestibulum erat. Maecenas congue commodo ante vel varius. Sed tempus mi ut metus gravida, nec dictum libero dapibus. Morbi quis viverra elit. Ut pharetra neque eget lacus tincidunt dictum. Fusce scelerisque viverra tellus et pretium.
+ Fusce varius adipiscing odio. Nulla imperdiet faucibus sem, at rhoncus ipsum adipiscing vitae. Phasellus imperdiet congue lacus et mollis. Nullam egestas mauris magna, et mollis lectus varius ut. Sed sollicitudin adipiscing dolor, vel elementum elit laoreet molestie. Aliquam nec nulla vel sem ultrices ullamcorper. Nullam nec felis magna. Duis sodales orci non justo aliquam tempus. Integer mi diam, tempor sed vulputate et, varius et nunc. Vestibulum sodales ipsum id mi pharetra, ut convallis mi accumsan. Sed dictum volutpat vestibulum.
+ Quisque ac dolor sagittis, aliquam libero at, euismod enim. Nulla ullamcorper posuere nulla vitae varius. Nam at dolor non libero elementum pellentesque in in lorem. Fusce porttitor turpis in quam placerat varius. Donec lorem orci, condimentum eu sapien sit amet, aliquet commodo magna. Quisque sed lectus sit amet arcu euismod accumsan et non nunc. Phasellus placerat congue metus, feugiat posuere leo dictum quis. Sed ultricies feugiat eros dignissim bibendum.
+ Mauris scelerisque consectetur libero eget varius. Aenean neque nunc, ullamcorper vitae orci in, auctor ornare sapien. Nam lacinia molestie imperdiet. Nam vitae mattis nibh. Vestibulum consequat tellus ac nisi sagittis pulvinar. Nullam mollis ornare quam, et venenatis leo porttitor sit amet. Nulla urna neque, dignissim non orci ut, volutpat ultrices erat. Cum sociis natoque penatibus et magnis dis parturient montes, nascetur ridiculus mus. Pellentesque vestibulum tellus nec eros faucibus porta.")
EITUSALNROMCDPVGQBFHJKWXYZ
> f("Based off ETAOIN SHRDLU, your challenge is to write the shortest program or function in any language that outputs the 26 letters of the English alphabet based on their frequency in the input.")
ETNAHORISULFGPBCDYMQWJKVXZ

```
> 1 votes

# Answer
# Retina, ~~81~~ 75 bytes

The language (especially the Sort mode) is newer than the challenge.

```
;
{T`;L`L`.$
}`[^Z]$
$0$0
T`l`L
Os`.
[^A-Z]

(.)\1*
$0¶
O#$^`.*
$.0
¶

D`.

```

**Try it online**

### Explanation:

```
;               # Add the entire alphabet plus a bunch of semicolons into the input
{T`;L`L`.$          # (so that all letters are included in the input at least once)
}`[^Z]$             #
$0$0                #
T`l`L           # Translate all lowercase into uppercase
Os`.            # Sort all characters by code point
[^A-Z]          # Remove non-letters

(.)\1*          # Separate same characters by newlines
$0¶
O#$^`.*         # Sort backwards numerically by the length
$.0
¶               # Remove newlines

D`.             # Remove excess letters

```
> 1 votes

# Answer
# K4, 16 bytes

**Solution:**

```
.Q.A@>+/.Q.a=/:_

```

Try it online! (Note this is an oK port/demonstration as there is no TIO for K4).

**Example:**

Note that the input string is stored as variable 'x' for ease:

```
q)\
  .Q.A@>+/.Q.a=/:_x
"EITUSALNROMCDPVGQBFHJKWXYZ"

```

**Explanation:**

```
.Q.A@>+/.Q.a=/:_  / the solution
               _  / convert to lowercase
            =/:   / equals each right (/:)
        .Q.a      / lowercase alphabet "a..z"
      +/          / sum
     >            / descending sorted indices
    @             / index into
.Q.A              / uppercase alphabet "A..Z"

```

**Notes:**

In `q/kdb+` it would be 27 bytes:

```
.Q.A idesc sum .Q.a=/:lower

```
> 1 votes

# Answer
# Vyxal, 8 bytes

```
kAµ?⇧nO⌐

```

Try it Online!

```
kA       # Uppercase alphabet
  µ    ⌐ # Reverse sorted by...
      O  # Count of...
     n   # This item in...
   ?⇧    # Uppercase input

```
> 1 votes

# Answer
# BQN, 24 bytes

```
{'A'+⍒+˝(⥊-⌜"aA")=⌜↕26}

```

A tacit function that accepts a single argument.

-8 from ovs.
> 1 votes

# Answer
# Perl, 43 bytes

adding 1 for `-n`, as usual.

I know variable variables are generally a bad idea and shouldn't be used, but hey it's code golf :)

```
#!perl -n
${uc$_}++for/\w/g}{print+sort{$$b-$$a}A..Z

```
> 0 votes

# Answer
# k4, 21 bytes

```
  {.Q.A@<<>#:'.Q.a#=_x}
  {.Q.A@<<>#:'.Q.a#=_x}@,/0:`:e
"EITUSALNROMCDPVGQBFHJKWXYZ"

```

This approach uses the builtin alphabetic constants `.Q.a` (the lowercase letters) and `.Q.A` (the uppercase) to do the filtering and translation back to upper. The process:

* `_`: convert to lowercase (leaves non-letters untouched)
* `=`: group into associative array of characters and their indices
* `.Q.a#`: take only lowercase letters (includes empty lists for characters that did not occur)
* `#:'`: count each value in the array
* `>`: get the keys of the array ordered by its values, descending
* `<<`: find the position where each item would appear if the list were sorted
* `.Q.A@`: apply that list of positions back to the list of uppercase letters

The last two steps are conceptually a bit tricky; they basically allow you to permute one list according to another. See the `q` documentation for `rank` for more details.

(Note that if we stop before the translation back to uppercase, we have a correct result, but in lowercase:

```
  {>#:'.Q.a#=_x}@,/0:`:e
"eitusalnromcdpvgqbfhjkwxyz"

```

and a code length of 14!)
> 0 votes

# Answer
# PHP 135 Bytes

I know I'm late but I wanted to post anyway:

```
function a($b){
  $b=strtoupper($b);
  foreach(range('A','Z') as $c){
   $d[$c]=substr_count($b, $c);
  }
  arsort($d);
  return implode(array_keys($d));
}
echo a($z); //let $z be the supplied string.

```

golfed:

```
function a($b){$b=strtoupper($b);foreach(range('A','Z') as $c){$d[$c]=substr_count($b, $c);}arsort($d);return implode(array_keys($d));}echo a($z);

```
> 0 votes

# Answer
**VB.net**

```
Dim r = String.Join("",( From a In "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                         Group Join c In t On a Equals c Into Group
                         Order By Group.Count Descending
                       ).Select(Function(g) g.a))

```
> 0 votes

# Answer
# Factor, ~~327~~ ~~261~~ 248 bytes

:o

```
CONSTANT: a "ABCDEFGHIJKLMNOPQRSTUWXYZ"
: s ( s -- s ) >array [ 1string ] map ;
[ >upper s dup a s [ [ = ] curry ] map [ [ count ] curry ] map [ call( x -- x ) ] with map [ a s union natural-sort ] dip zip [ last ] sort-with [ first ] map "" join ]

```

Writing this took a while since I'm still learning the language, but it was fun.

Run the above code, then do `"string" swap call` to call the lambda. Less golfed:

```
USING: arrays ascii assocs combinators kernel sequences
  sequences.generalizations sets sorting strings ;
IN: input-freq

CONSTANT: alph "ABCDEFGHIJKLMNOPQRSTUWXYZ"

: alphabet-counter ( -- alph-quot )
  alph string>array [
    [ = ] curry
  ] map [
    [ count ] curry
  ] map ;

: string>array ( str -- array )
  >array [ 1string ] map ;

: freq-find ( str -- freqmap )
  >upper string>array dup alphabet-counter
  [ call( x -- x ) ] with map
  [ alph string>array union natural-sort ] dip zip
  [ last ] sort-with [ first ] map "" join ;

```
> 0 votes

# Answer
## Lua, 226 Bytes

I'm coming in long after this contest has ended, but I though it would be fun to do :). Also, it may be one of the longest submission down here, but actually took me some time to find a clever way to do it. It may still be golfable I'll explain it below, but right now, here's the code:

```
f,t={},{}(...):upper():gsub("%u",function(c)c=c:byte()-64 f[c]=f[c]and f[c]+1or 1 end)for i=1,26
do c=(i+64 ..''):char()f[i]=f[i]and f[i]or 0 x=f[i]t[x]=t[x]and c..t[x]or c end
for i=#...,0,-1 do io.write(t[i]and t[i] or'')end

```

It's a full program, taking its input via command-line argument as a string.

### Ungolfed and explanations

```
f={}                       -- f will be our array for counting iteration
t={}                       -- t will be the sorted array
(...):upper()              -- convert the input in all uppercase
     :gsub("%u",function(c)-- then iterate over each uppercase letter in it
  c=c:byte()-64            -- set c at its position in the alphabet
  f[c]=f[c]                -- if f[c] is set (letter already encountered)
       and f[c]+1          -- increment it
       or 1                -- else, we set it to 1
end)
   -- At that point, wev'e counted each character, let's sort based on occurence!
for i=1,26                 -- iterate on the size of the alphabet
do
  c=(i+64 ..''):char()     -- c is the character corresponding to the current i
  f[i]=f[i]and f[i]or 0    -- if c wasn't in the input, initialise a counter at 0
  x=f[i]                   -- set x to the number of occurence of c
  t[x]=t[x]                -- if t[x] is set, two or more letter have the same count
       and c..t[x]         -- so concatenate the string in t[x] with the new letter
       or c                -- else, just set it
end

for i=#...,0,-1            -- iterate from the size of input to 0
do
    io.write(t[i]          -- if we have i occurence of letter(s)
         and t[i]          -- output them
         or'')             -- else, output an empty string
end

```

This algorythm is *really* inefficient. It works because arrays don't exist in lua, we only use tables, which are associative arrays. Which means I can map `t[123456]='B'` even if `t[1]` doesn't exist. It makes sorting the number of occurence really fast, but if you want to find them, the time will depend on the size of the input you gave to the program.
> 0 votes

# Answer
# Mathcad, 102 "bytes"

Mathcad doesn't index strings, so the function f converts the string to a vector of its equivalent character codes (subtracting A's code to aid indexing). f then counts each occurence of the letters A..Z (taking 32 of the values of codes \>= "a" to implicitly convert case).

Then there's a verbose sequence of nested functions that sort the character codes by count in ascending order, extract the sorted codes in reverse order and add the "A" offset back, and convert the resulting character code vector back into a string.

I interpret Mathcad "bytes" as the number of keyboard / menu operations necessary to create a Mathcad symbol.

* Identifier names, eg submatrix, are typed in letter-by-letter, hence the byte count = number of characters in the name.
* Type ' to add a balanced pair of parentheses
* Array indices are entered by typing the array name and then the character '\[' followed by the indices. For c<sub>25</sub>, this would be the 4 bytes c \[ 2 5.
* Type ctl-shft-# A to create a "for loop"; this results in a for programming construct that automatically displays the for keyword and the element-of symbol, plus three placeholders. The placeholders are for the iteration variable, it's range and the main body of the loop, respectively.
* Type \] to add a new programming line. See the image below ...
> 0 votes

# Answer
## Floroid \- 37 bytes

```
Ba:''.y(t(R(P,w(65,91)),fi=a.fk.fm))D

```

A little late to the party, but here it is. An Floroid port of @undergroundmonorails answer.

This language was made some time after this challenge, therefore this isn't competing.
> 0 votes

# Answer
# PHP, 92+1 bytes (late entry)

```
$r=count_chars(strtoupper($argn));arsort($r);foreach($r as$c=>$n)$c>64&$c<91&&print chr($c);

```

Run as pipe with `-nR` or try it online.
> 0 votes

# Answer
# 05AB1E, 9 bytes

```
lAΣ¢}ÙRáu

```

Try it online!

---

More interesting 10-byte version:

# 05AB1E, 10 bytes

```
l{γéJAìÚRá

```

Try it online!
> 0 votes

# Answer
# Burlesque, 12 bytes

```
ZZ:rdf:q[~\m

```

Try it online!

```
ZZ  # To caps
:rd # Filter for alpha
f:  # Frequency list (zipped count, char, sorted by frequency)
q[~ # Take tails (char)
\m  # Map-concat

```
> 0 votes

# Answer
# Perl 5 `-n0`, 41 bytes

```
for$x(A..Z){$;[pos=-split/$x/i].=$x};say@

```

Try it online!
> 0 votes

# Answer
# Thunno 2, 8 bytes

```
kAÞ$RncṄ

```

Try it online!

#### Explanation

```
kAÞ$RncṄ  # Implicit input
kA        # Uppercase alphabet
  Þ    Ṅ  # Reverse-sorted by:
   $R     #  Uppercase input
     nc   #  Count occurrences
          # Implicit output

```
> 0 votes

# Answer
# Raku, 38 bytes

```
{[~] ('A'..'Z').sort:{-.uc.comb($^x)}}

```

Try it online!

* `('A' .. 'Z').sort: { ... }` sorts the capital letters by whatever the brace-delimited anonymous subroutine returns for each.
* `.uc` converts the input string to uppercase.
* `.comb($^x)` counts how many times the character `$^x` (the implicit argument to the function) appears in the uppercased input string.
* `-` returns the negative of the character count, so the letters are sorted in order of decreasing frequency.
* `[~]` joins the sorted letters into a single string.
> 0 votes

# Answer
# Nibbles, 8 bytes (16 nibbles)

```
+=~|_\$u,+%.@`)$

```

```
+=~|_\$u,+%.@`)$        # full program
+=~|_\$u,+%.@`)$$       # with implicit arg added;
   |                    # filter
    _                   # printable characters
                        # (default value for _ when no STDIN)
                        # by
     \$u                #   is it an uppercase character?
 =~                     # now split these letters into groups, sorted by:
        ,               #   length
         +              #   (after flattening)
          $     $       #   of using this letter to split
            @           #   input
           .            #   mapped
             `)$        #     to uppercase
+                       # and finally flatten the sorted groups

```
> 0 votes

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


title: Return the flipped version of a number

text:
# Question
Title: Return the flipped version of a number
When a number is shown on a calculator, it's possible to consider what various transformations of that number would look like. For example, on a seven-segment display, 2 is shown like this:

And when flipped horizontally it looks like this:

As such, the mirror image of 2 is 5.

The task in this challenge is to take a single-digit number, and return the number that's its mirror image (if possible). If its mirror image does not look like a number, return the number rotated 180 degrees (if possible). If neither of these are the case, return -1.

Here's the full list of inputs and outputs your program needs to handle:

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

```

As a challenge, the shortest code wins!

# Answer
## Haskell - ~~43~~ 31

43 characters without anything fancy.

```
f 0=0
f 8=8
f 2=5
f 5=2
f 6=9
f 9=6
f _= -1

```

Got it down to 31 characters by making it a partial function.

```
f=([0,-1,5,-1,-1,2,9,-1,8,6]!!)

```
> 34 votes

# Answer
# GolfScript, 15 14

I read the spec again and found that the input must be a string.

```
"0.5..29.86"\?

```

To run:

```
echo -n 2 | ruby golfscript.rb a.gs

```

Old version(which has integer input):

```
[0.5..2 9.8 6]?

```

The newer one(14 byte) is somewhat inspired by the CJam answer by aditsu.
> 23 votes

# Answer
## PowerShell - 27

```
'0 5  29 86'.indexof($args)

```
> 20 votes

# Answer
# Python 2.x - 28

```
'015..29.86'.find(`input()`)

```
> 13 votes

# Answer
# JavaScript ~~37~~ 36

```
alert("0_5__29_86".search(prompt()))

```
> 11 votes

# Answer
**BEFUNGE 93 - ~~18~~ ~~14~~ 20 Bytes**

I guess the commentators are right, though Befunge being a 2d language lines are kinda different. Still, in this instant, the commentators are right.

```
&1g01g-.
! &  #* )'

```

Steps:

```
&

```

Reads input as a numerical value x, and pushes it on the stack.

```
1g

```

Gets the character value c (so, like '!' = 33, or '\*' = 42. An empty cell = 32) at position x, 1.

```
01g-.

```

Reads the character value of cell 0,1 (33), subtracts it from c, and outputs it as a numerical value.
> 9 votes

# Answer
# CJam, 20 bytes

```
q25691347`"5296W"er~

```

Try it online.

### Output

```
$ for i in {0..9}; { cjam <(echo 'q25691347`"5296W"er~') <<< $i; echo; }
0
-1
5
-1
-1
2
9
-1
8
6

```

### How it works

```
q          " Read from STDIN. The leaves a string on the stack.            ";
25691347`  " Push the string '25691347'.                                   ";
"5296W"    " Push the string '5296W'.                                      ";
er         " Perform character transliteration.                            ";
~          " Evaluate the result. Examples: '2' returns 2, 'W' returns -1. ";

```
> 8 votes

# Answer
# JavaScript (ECMAScript 6) 25

```
x=>'1060039097'[x]-(x!=6)

```

# JavaScript (ECMAScript 5) 43

```
function f(x){return'1060039097'[x]-(x!=6)}

```

UPDATE: edc65 has suggested a much better technique. toothbrush has suggested a much better language. At this point, my primary contributions are debugging and gumption.
> 8 votes

# Answer
# Java - 49

```
long f(int a){return(0x790a300601L>>(a*4)&15)-1;}

```

Here, `0x790a300601` is a value stuffed with the desired outputs, with one added to make them positive. The values are stored in nibbles within the value, so a bit of shifting and masking is required to pop them out.

# Java - 100 (fun option)

```
int f(int a){Random r=new Random(0x2000A2F47D6Fl);int b=0;for(;a>=0;a--)b=r.nextInt(11)-1;
return b;}

```

Not the smallest option, but a bit of fun. I found a random seed that produces the correct values when called *X* times (where 0 \>= *X* \<= 9).
> 8 votes

# Answer
# bash 29

```
tr 1-9 x5xx29x86|sed s/x/-1/g

```

e.g.

```
$ echo 0 1 2 3 4 5 6 7 8 9 | tr 1-9 x5xx29x86|sed s/x/-1/g
0 -1 5 -1 -1 2 9 -1 8 6

```
> 6 votes

# Answer
# Kona \- 29

This function returns the element `x` from the array `0 -1 5...`

```
f:{0 -1 5 -1 -1 2 9 -1 8 6@x}

```

Examples:

```
> f 2
  5
> f 5
  2
> f 8
  8

```
> 4 votes

# Answer
# JavaScript 36 ~~37~~ ~~41~~

```
alert('0x'+'65b558f5ec'[prompt()]-6)

```

as ES6 function - 27:

```
f=v=>'0x'+'65b558f5ec'[v]-6

```
> 4 votes

# Answer
# Sclipting, 11 characters

```
걄럣뉥밈결⓷方分결剩貶

```

Finally I have found a Windows computer with Visual Studio installed to build its interpreter. And it has defeated my GolfScript code easily.

It reads `18453063256\11\?/11%(` in GolfScript.
> 4 votes

# Answer
# APL (Dyalog Extended), 22 bytes

```
⊢⌷{1-⍨⎕A⍳'BAGAADKAJH'}

```

Explanation:

```
⊢⌷{1-⍨⎕A⍳'BAGAADKAJH'}
      ⎕A⍳'BAGAADKAJH'     ⍝ numeric vector 2 1 7 1 1 4 11 1 10 8
   1-⍨                    ⍝ decrement:     1 0 6 0 0 3 10 0  9 7
⊢⌷                        ⍝ value at index ⍵ in the lut

```

Try it online!
> 4 votes

# Answer
# J - ~~28~~ 27 bytes

You know what I like? Simplicity (28 bytes). Note that in J, `_1` is negative one (-1).

```
f=:{&0 _1 5 _1 _1 2 9 _1 8 6

```

Add a little complexity and you have 27 bytes.

```
f=:-{&0 2 _3 4 5 3 _3 8 0 3

```

Example:

```
   f 2
5
   f 6
9
   f 5
2
...

```
> 3 votes

# Answer
# CJam - 14

Input/output version:

```
"0 5  29 86"q#

```

Stack version (assumes the number is on the stack):

```
[0W5WWY9W8 6]=

```

Try them at http://cjam.aditsu.net/
> 3 votes

# Answer
# Perl, 27 26

Count includes the `p` flag

```
y/2569/5296/,s/[1347]/-1/

```

Usage:

```
$ echo 7 | perl -pe y/2569/5296/,s/[1347]/-1/
-1

```

***Wait, did Perl just beat J? :)***
> 3 votes

# Answer
## ECMAScript 6, 24

```
f=x=>~-++'0n5nn29n86'[x]

```

Using normal JavaScript it would be 33:

```
alert(~-++'0n5nn29n86'[prompt()])

```
> 3 votes

# Answer
# Marbelous 34 bytes

```
}0
=6=9=2=5=0=8?0
+3-3+3-3....--

```

It's not the shortest solution, but it's not the longest either.

**How it works**

`}0` spawns a marble representing the first command line input. This marble drops down the next tick, onto the `=6` cell. `=6` is a comparison cell, it pushes any marble with value 6 down and all others to the right. This line-up of comparison cells pushes marbles right until they equal a desired value. 0 and 8 just fall through and get printed when tehy fall off the bottom of the board, 6 and 2, and 9 and 5 first get 3 added to them, subtracted from them respectively. If a marble doesn't equal any of the desired values, it lands on the `?0` cell, which turn any marble into a 0 marble1. This marble then gets decremented and falls off the board.

1 A `?n` marble technically turns any marble into a marble between 0 and n. This has the nice side effect that `?0` turns anything into 0.
> 3 votes

# Answer
# MATLAB - 35

I would wrap this in a function with `n` as the only parameter.

```
f=[0,-1,5,-1,-1,2,9,-1,8,6];
f(n+1)

```

35 characters.
> 2 votes

# Answer
# TI-BASIC, ~~24~~ 22

```
-1+int(11fPart(11^Ans.0954191904

```

This encodes the possible outputs in a lookup table stored as a base-11 floating point number; the (N+1)th base-11 digit after the decimal point is extracted from the table to get the value of the inverted digit. In base 11 the number is `.106003A097`, and the digits of this less one are exactly `0,-1,5,-1,-1,2,9,-1,8,6`.

edc65's trick of subtracting one in the case of 6 leads to this 24-byte solution, where `⑩^(` is a single one-byte token:

```
-(Ans≠6)+int(10fPart(.1060039097⑩^(Ans

```

The string approach is 29 bytes:

```
-(Ans≠6)+expr(inString("1060039097",Ans+1,1

```

The array approach (which Ypnpyn also took) is 30 bytes, assuming the number is stored in X:

```
{1,0,6,0,0,3,10,0,9,7}-1:Ans(X+1

```

24 -\> 22: Removed two extra digits of precision in the magic constant.
> 2 votes

# Answer
# C - 47 bytes \[was 48 Bytes\]

```
f(i){return(int[]){1,0,6,0,0,3,10,0,9,7}[i]-1;}

```

To add I/O (which other answers didn't always) for 86 bytes:

```
main(i){i=(int[]){1,0,6,0,0,3,10,0,9,7}[getchar()-48]-1;i<0?puts("-1"):putchar(i+48);}

```
> 2 votes

# Answer
# 05AB1E, 13 bytes

```
0®5®®Y9®8 6¹@

```

Try it online!

-3 thanks to Emigna.

Explanation:

```
0®5®®Y9®8 6¹@ Takes an integer from STDIN.
0®5®®Y9®8 6   Push 0, r=-1, 5, r=-1, r=-1, Y=2, 9, r=-1, 8, 6.
           ¹  Push first input item.
            @ Pop and push the 0-indexed stack item at the respective index.

```
> 2 votes

# Answer
# Python - 34

```
f=lambda n:ord("A@F@@CJ@IG"[n])-65

```
> 1 votes

# Answer
## Java, 58 ~~59~~

```
int f(int i){int[]a={1,0,6,0,0,3,10,0,9,7};return a[i]-1;}

```

OR

```
int f(int i){return new int[]{1,0,6,0,0,3,10,0,9,7}[i]-1;}

```
> 1 votes

# Answer
# C - 117 108 106 77 76 bytes

```
a[]={1,0,6,0,0,3,10,0,9,7};main(int c,char**b){printf("%d",a[*b[1]-48]-1);}

```

Not the best language for golfing, but oh well...
Compile with `gcc progname.c -o progname`. (Ignore the warnings, or add `-include stdio.h` to the compile command.)

> Usage: ./progname \<number\>

**EDIT**

As per @bebe's suggestion, here is an example that takes the input from STDIN instead:

# C - 68 51 bytes

```
main(){printf("%d","106003:097"[getchar()-48]-49);}

```
> 1 votes

# Answer
## JavaScript 42 37

Run it on the console of your browser

```
alert(~-[1,,6,,,3,10,,9,7][prompt()])

```
> 1 votes

# Answer
# J (24, function)

(the input panel isn't playing nice. Paste the following in a python interpreter and my answer shall be revealed:)

```
print "f=:{&(_3+3 u:'^C^B^B^E^L^B^K\t')"

```
> 1 votes

# Answer
# Clojure - 36

```
#(case % 2 5 5 2 6 9 9 6 0 0 8 8 -1)

```
> 1 votes

# Answer
# Perl, 22B

`perl -pe "y/25690/52960/or$_=-1"`

Based off https://codegolf.stackexchange.com/a/32012/19039, but shorter. 1B penalty for -p.
> 1 votes

# Answer
# Turtlèd, 40 bytes (noncompeting)

```
!.(3'1)(4'1)(1l'-)(2'5l)(5'2)(6'9l)(9'6)

```

**Try it online!**

Explanation

```
!                                          take input
 .                                         write first char of input to cell
  (3'1)                                    if cell is 3, write 1
       (4'1)                               if cell is 4, write 1
            (1l'-)                         If cell is 1, move left and write -
                  (2'5l)                   If cell is 2, write 5 and move left
                        (5'2)              If cell is 5, write 2
                             (6'9l)        If cell is 6, write 9 and move left
                                   (9'6)   If cell is 9, write 6

```
> 1 votes

# Answer
# Jelly, 14 bytes

```
ị“-5--29-860”V

```

Try it online!

Explanation:

```
ị“-5--29-860”V Takes argument as an integer.
 “-5--29-860”  "-5--29-860" (1-indexed string).
ị              Return the xth char of the string above (y) (x=argument).
             V Eval. - is the same as -1.

```
> 1 votes

# Answer
# PHP, ~~48~~ 39 bytes

Thanks to Jörg Hülsermann

```
<?=[0,-1,5,-1,-1,2,9,-1,8,6][$argv[1]];

```

Try it online!

---

**Older versions**

```
$m=-1;echo [0,$m,5,$m,$m,2,9,$m,8,6][$argv[1]];

```

Try it online!
> 1 votes

# Answer
# Vyxal, 16 bytes

```
kd`0u5uu29u86`⇿ₑ

```

Try it Online!

Simply push the digits 0 to 9, push the string `0u5uu29u86` (the mapping of each number - `u` pushes -1 in Vyxal), transliterate and evaluate as Vyxal.
> 1 votes

# Answer
# Excel, 31 bytes

```
=MID(1060039097,A1+1,1)-(A1<>6)

```
> 1 votes

# Answer
# Python 3.11 - 24

```
lambda x:"0.5..29.86"[x]

```

Based on this Python 2.x answer by Willem.
> 1 votes

# Answer
# **Python - 92**

```
f=lambda x:x if x in(0,8)else(5if x==2 else(2if x==5 else(6if x==9 else(9if x==6 else -1))))

```

Usage:

```
>>> f(2)
5
>>> f(3)
-1

```
> 0 votes

# Answer
## Python - 73 bytes

```
r=[2,5,2,9,6,9,8,8,0,0]
f=lambda x:-1 if x not in r else r[r.index(x)+1]

```

Or, for one digit numbers only :

```
r=[0,-1,5,-1,-1,2,9,-1,8,6]
f=lambda x:r[x]

```
> 0 votes

# Answer
## Java, 75

```
int f(int i){return i>8?6:i>7?8:i>6?-1:i>5?9:i>4?2:i>2?-1:i>1?5:i>0?-1:0;}

```
> 0 votes

# Answer
# PowerShell 32

```
(0,-1,5,-1,-1,2,9,-1,8,6)[$args]

```
> 0 votes

# Answer
# F# - 37 bytes

```
let f n=[0;-1;5;-1;-1;2;9;-1;8;6].[n]

```

Usage:

```
> f 2
val it : int = 5
> f 9
val it : int = 6
> f 4
val it : int = -1

```
> 0 votes

# Answer
## TI-BASIC, 35

```
{1,0,6,0,0,3,10,0,9,7}→L1:L1(X+1)-1

```

Previous attempt, 42:

```
6(X=2)+3(X=5)+10(X=6)+9(X=8)+7(X=9)-1+(X=0

```
> 0 votes

# Answer
## C++ 85

Uses nested ternary statements.

```
int main(){int a;cin>>a;a=(a==2)?5:(a==5?2:(a==6?9:(a==9?6:(a%8==0?a:-1))));cout<<a;}

```
> 0 votes

# Answer
# Bash 26

```
bc<<<`tr 0-9 106003A097`-1

```

eg.

```
for i in {0..9}; do echo $i|
  bc<<<`tr 0-9 106003A097`-1
done
0
-1
5
-1
-1
2
9
-1
8
6

```
> 0 votes

# Answer
# Python3: 47

A very basic implementation, that accepts a input and translates accordingly.

```
print([0,-1,5,-1,-1,-1,9,-1,8,6][int(input())])

```

PEP8 is of course sacrificed for the sake of characters. This doesn't come close to rivaling the other Python solution near the top. However, as my first golf, I don't think it's *that* bad :).
> 0 votes

# Answer
# Haskell (full program), 63

```
main=interact$maybe"-1"(:"").(`lookup`zip"025689""052986").head

```

Call main, and whatever character your input starts with gets used. Anything that isn't '0', '2', '5', '6', '8', or '9' prints "-1". Unfortunately `show` wraps characters in single quotes, so the output wouldn't have been consistent, so I had to use `(:"")` (or `(:[])`).
> 0 votes

# Answer
# Batch - 79

```
set /aa=%1+1&for /f "tokens=%a%" %%1 in ("0 -1 5 -1 -1 2 9 -1 8 6") do echo>%%1

```

Used as `filename.bat number`, output is as a file with the name of the correct number.
> 0 votes

# Answer
# Zozotez LISP 87

```
((:'f(\(k n v)(? k(?(=(a k)n)(a v)(f(d k)n(d v)))'-1)))'(0 2 5 6 8 9)(r)'(0 5 2 9 8 6))

```

This assumes you start it by seeding one of the REPL supplied so the printing actually is done by Without a driver/REPL you need 3 chars extra:

```
(p((:'f(\(k n v)(? k(?(=(a k)n)(a v)(f(d k)n(d v)))'-1)))'(0 2 5 6 8 9)(r)'(0 5 2 9 8 6)))

```
> 0 votes

# Answer
# Ruby, 30 bytes

What, no Ruby solution yet?

```
p'0 5  29 86'.index($*[0])||-1

```

Takes the input as a command-line argument.
> 0 votes

# Answer
# Pyth - 16 bytes

```
x[ZZ5ZZ2 9Z8 6)Q

```

Doesn't really count because Pyth was created after this was posted, but it's still pretty neat.
> 0 votes

# Answer
# dimwit ~~24~~ 23 bytes (non-competing)

**Edit:** removed end bracket, as it is not necessary

Another question that I thought could be good for working on the language with...

```
R2,5,6,9,[1-7]}5,2,9,6,-1

```

### Explanation:

* `R` \- map replace
* `2,5,7,9,[1-7]}` \- the searches. Since 2, 5, 6, and 9 are checked first, 1-7 can be used and will simply check if it's 1, 3, 4, or 7. 0 and 8 will therefore stay the same.
* `5,2,9,6,-1` \- the replacements. So 2 is replaced by 5, 5 is replaced by 2, etc.

### Try it Here
> 0 votes

# Answer
# C (gcc), ~~46~~ 27 bytes

```
f(i){i="BAGAADKAJH"[i]-66;}

```

Try it online!
> 0 votes

# Answer
# Thunno 2, 14 bytes

```
6 8u9yuu5u0K$i

```

Try it online!

```
¿£Ṣƥ*ðdiṅ×Ɗ€¿i

```

Try it online!

#### Explanation

```
6 8u9yuu5u0K$i  # Implicit input
6 8u9yuu5u0     # Push 6,8,-1,9,2,-1,-1,5,-1,0
           K    # Wrap the stack (reversed)
            $i  # Index the input in
                # Implicit output

```

```
¿£Ṣƥ*ðdiṅ×Ɗ€¿i  # Implicit input
¿£Ṣƥ*ðdiṅ×Ɗ€¿   # Push compressed list
                # [0,-1,5,-1,-1,2,9,-1,8,6]
             i  # Index the input in
                # Implicit output

```
> 0 votes

# Answer
# , 18 bytes

```
_1".{&'0x5xx29x86'

```

Attempt This Online!

```
_1".{&'0x5xx29x86'
    {&'0x5xx29x86'  NB. index into a string literal
_1".                NB. eval the result using _1 as a default value

```
> 0 votes

# Answer
# JavaScript (Node.js), 25 bytes

```
x=>'0x'+'106003a097'[x]-1

```

Try it online!
> 0 votes

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