title: Is it a max-heap?

text:
# Question
Title: Is it a max-heap?
A heap, also known as a priority-queue, is an abstract data type. Conceptually, it's a binary tree where the children of every node are smaller than or equal to the node itself. (Assuming it's a max-heap.) When an element is pushed or popped, the heap rearranges itself so the the biggest element is the next to be popped. It can easily be implemented as a tree or as an array.

Your challenge, should you choose to accept it, is to determine if an array is a valid heap. An array is in heap form if every element's children are smaller than or equal to the element itself. Take the following array as an example:

```
[90, 15, 10, 7, 12, 2]

```

Really, this is a binary tree arranged in the form of an array. This is because every element has children. 90 has two children, 15 and 10.

```
       15, 10,
[(90),         7, 12, 2]

```

15 also has children, 7 and 12:

```
               7, 12,
[90, (15), 10,        2]

```

10 has children:

```
                      2
[90, 15, (10), 7, 12,  ]

```

and the next element would also be a child of 10, except that there isn't room. 7, 12 and 2 would all also have children if the array was long enough. Here is another example of a heap:

```
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

```

And here is a visualization of the tree the previous array makes:

Just in case this isn't clear enough, here is the explicit formula to get the children of the i'th element

```
//0-indexing:
child1 = (i * 2) + 1
child2 = (i * 2) + 2

//1-indexing:
child1 = (i * 2)
child2 = (i * 2) + 1

```

You must take an non-empty array as input and output a truthy value if the array is in heap order, and a falsy value otherwise. This can be a 0-indexed heap, or a 1-indexed heap as long as you specify which format your program/function expects. You may assume that all arrays will only contain positive integers. You may *not* use any heap-builtins. This includes, but is not limited to

* Functions that determine if an array is in heap-form
* Functions that convert an array into a heap or into heap-form
* Functions that take an array as input and return a heap data-structure

You can use this python script to verify if an array is in heap-form or not (0 indexed):

```
def is_heap(l):
    for head in range(0, len(l)):
        c1, c2 = head * 2 + 1, head * 2 + 2
        if c1 < len(l) and l[head] < l[c1]:
            return False
        if c2 < len(l) and l[head] < l[c2]:
            return False

    return True

```

# Test IO:

All of these inputs should return True:

```
[90, 15, 10, 7, 12, 2]
[93, 15, 87, 7, 15, 5]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[100, 19, 36, 17, 3, 25, 1, 2, 7]
[5, 5, 5, 5, 5, 5, 5, 5]

```

And all of these inputs should return False:

```
[4, 5, 5, 5, 5, 5, 5, 5]
[90, 15, 10, 7, 12, 11]
[1, 2, 3, 4, 5]
[4, 8, 15, 16, 23, 42]
[2, 1, 3]

```

As usual, this is code-golf, so standard loopholes apply and the shortest answer in bytes wins!

# Answer
# Jelly, ~~11~~ ~~9~~ 5 bytes

```
x2:ḊṂ

```

4 bytes removed thanks to Dennis!

Try it here.

### Explanation

```
x2          Duplicate each element.
:Ḋ          Each element divided by the input with the first element removed,
            as integer, so there is a 0 only if some element in the duplicated
            list is less than the corresponding element in the other.
            There are also elements left unchanged, but it doesn't matter as
            the input is all positive.
Ṃ           Minimum in the list.

```
> 7 votes

# Answer
## JavaScript (ES6), ~~34~~ 30 bytes

```
a=>!a.some((e,i)=>e>a[i-1>>1])

```

Edit: Fixing my code for the spec clarification cost 1 byte, so thanks to @edc65 for saving 4 bytes.
> 10 votes

# Answer
# Haskell, 33 bytes

```
f(a:b)=and$zipWith(<=)b$a:b<*"xx"

```

or

```
and.(zipWith(<=).tail<*>(<*"xx"))

```
> 5 votes

# Answer
# J, 24 bytes

```
*/@:<:]{~0}:@,<.@-:@i.@#

```

## Explanation

```
*/@:<:]{~0}:@,<.@-:@i.@#  Input: s
                       #  Count of s
                    i.@   Create range [0, 1, ..., len(s)-1]
                 -:@      Halve each
              <.@         Floor each
         0   ,            Prepend a zero to it
          }:@             Remove the last value to get the parent indices of each
      ]                   Identity function to get s
       {~                 Take the values from s at the parent indices
    <:                    For each, 1 if it is less than or equal to its parent else 0
*/@:                      Reduce using multiplication and return

```
> 4 votes

# Answer
# MATL, ~~13~~ 12 bytes

```
ttf2/k)>~4L)

```

Try it online! Or verify all test cases.

An array is truthy if it is non-empty and all its entries are nonzero. Otherwise it's falsy. Here are some examples.

### Explanation

```
t     % Take input implicitly. Duplicate
tf    % Duplicate and push indices of nonzero entries. This gives [1 2 ... n] where n
      % is input size
2/k   % Divide by 2 and round down
)     % Index into input. Gives array of parents, except for the first entry
>~    % True for entries of the input that don't exceed those in the array of parents
4L)   % Discard first entry

```
> 3 votes

# Answer
## Python 2, 45 bytes

```
f=lambda l:l==[]or l[len(l)/2-1]/l.pop()*f(l)

```

Outputs 0 for Falsy, nonzero for Truthy.

Checks that the last element is less than or equal to its parent at index `len(l)/2-1`. Then, recurses to check that the same is True with the last element of the list removed, and so on until the list is empty.

---

**48 bytes:**

```
f=lambda l,i=1:l==l[:i]or l[~-i/2]/l[i]*f(l,i+1)

```

Checks that at each index `i`, the element is at most its parent at index `(i-1)/2`. The floor-division produces 0 if this is not the case.

Doing the base case as `i/len(l)or` gives the same length. I had tried zipping at first, but got longer code (57 bytes).

```
lambda l:all(map(lambda a,b,c:b<=a>=c,l,l[1::2],l[2::2]))

```
> 2 votes

# Answer
# Vyxal `r`, 5 bytes

```
hJY≥A

```

Try it Online!
> 2 votes

# Answer
# R, ~~97 88~~ 82 bytes

Hopefully I've understood this correctly. Now to see if I can get rid of some more bytes. Ditched the rbind and put in an sapply and deal with 1-based vector properly.

Implemented as an unnamed function

```
function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)

```

With a few of the test cases

```
> f=
+ function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
> f(c(90, 15, 10, 7, 12, 2))
[1] TRUE
> f(c(93, 15, 87, 7, 15, 5))
[1] TRUE
> f(c(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))
[1] TRUE
> f(c(5, 5, 5, 5, 5, 5, 5, 5))
[1] TRUE
> f(c(4, 5, 5, 5, 5, 5, 5, 5))
[1] FALSE
> f(c(90, 15, 10, 7, 12, 11))
[1] FALSE
> f(c(4, 8, 15, 16, 23, 42))
[1] FALSE

```
> 1 votes

# Answer
# CJam, ~~19~~ ~~16~~ ~~13~~ 12 bytes

```
q~_:_\(;./:*

```

Golfed off 3 bytes thanks to Dennis.

Try it here.
> 1 votes

# Answer
# Pyth, 8 bytes

```
.AgV.i+h

       hQ      first element of input
      +  Q     plus input
    .i    Q    interleaved with input
  gV       Q   vectorized greater-than-or-equal comparison with input
.A             check if all results are true

```

Try it online
> 1 votes

# Answer
# Retina, 51 bytes

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

```

Try it online!

---

Takes a space-separated list of numbers as input. Outputs `1`/`0` for truthy/false
> 1 votes

# Answer
# C (GCC), ~~63~~ 60 bytes

*-3 bytes thanks to @Juan Ignacio Díaz*

```
f(v,n,b,j)int*v;{for(b=j=0;n+~j;)b|=v[j/2]<v[++j];return!b;}
```

Attempt This Online!

Original note of the 63 bytes version:

> I know 2 bytes can be saved by inverting the meaning of the values `0` and `1`, but I prefer to keep it this way.
> 1 votes

# Answer
# C++14, ~~134~~ 105 bytes

```
#define M(d) (2*i+d<c.size()&&(c[i]<c[2*i+d]||f(c,2*i+d)==0))
int f(auto&c,int i=0){return!(M(1)||M(2));}

```

Requires `c` to be a container supporting `.operator[](int)` and `.size()`, like `std::vector<int>`.

Ungolfed:

```
int f(auto& c, int i=0) {
    if (2*i+1<c.size() && c[i] < c[2*i+1]) return 0;
    if (2*i+2<c.size() && c[i] < c[2*i+2]) return 0;
    if (2*i+1<c.size() && (f(c,2*i+1) == 0)) return 0;
    if (2*i+2<c.size() && (f(c,2*i+2) == 0)) return 0;
    return 1;
}

```

Could be smaller if truthy=`0` and falsy=`1` would be allowed.
> 0 votes

# Answer
# R, 72 bytes

A slightly different approach from the other R answer.

```
x=scan();all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)

```

Reads input from stdin, creates a vector of all of the comparison pairs, subtracts them from each other, and checks that the result is a negative number or zero.

### Explanation

Read input from stdin:

```
x=scan();

```

Create our pairs. We create indices of `1...N` (where `N` is the length of `x`) for the parent nodes. We take this twice as each parent has (maximally) two children. We also take the children, `(1...N)*2` and `(1...N)*2+1`. For indices beyond the length of `x`, R returns `NA`, 'not available'. For input `90 15 10 7 12 2`, this code gives us `90 15 10 7 12 2 90 15 10 7 12 2 15 7 2 NA NA NA 10 12 NA NA NA NA`.

```
                  x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)]

```

In this vector of pairs, each element has its partner at a distance of `N*2` away. For example, item 1's partner is located at position 12 (6\*2). We use `diff` to calculate the difference between these pairs, specifying `lag=N*2` to compare the items to their correct partners. Any operations on `NA` elements simply return `NA`.

```
             diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)

```

Finally, we check that all of these returned values are less than `1` (i.e. that the first number, the parent, was bigger than the second number, the child), excluding `NA` values from consideration.

```
         all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)

```
> 0 votes

# Answer
# Actually, 16 bytes

This answer is largely based on jimmy23013's Jelly answer. Golfing suggestions welcome! Try it online!

```
;;2╟┬Σ1(tZ`i<`Mm

```

**Ungolfing**

```
         Implicit input a.
;;       Duplicate a twice.
2╟       Wrap two of the duplicates into a list.
┬        Transpose the duplicates.
Σ        Sum all of the columns to get a flat list like this:
           [a_0, a_0, a_1, a_1, ..., a_n, a_n]
         This gets the parent nodes of the heap.
1(t      Get a[1:] using the remaining duplicate of a.
         This is a list of the child nodes of the heap.
Z`i<`M   Check if every child node is less than its parent node.
m        Get the minimum. This returns 1 if a is a max-heap, else 0.
         Implicit return.

```
> 0 votes

---
Tags: code-golf, array, data-structures, decision-problem
---


title: Periodic Table of Elements - Code Golf

text:
# Question
Title: Periodic Table of Elements - Code Golf
Based on Practical Golf - US States

Your task is to find the abbreviation (symbol) of an element given the element name, up to and including ununoctium (118). Use the periodic table on Wikipedia.

Thanks to squeamish ossifrage, you can find a full list of elements to abbreviations at http://pastebin.com/DNZMWmuf.

You may not use any external resources. In addition, you may not use any built-in data specifically about the elements of the periodic table. Standard loopholes apply.

**Input**

Input may be from stdin, file, `prompt`, `input` etc.

Input Format:

All of the following are valid inputs:

```
Carbon
carbon
CARBON
cArBOn

```

Essentially, the element name - case insensitive.

You do not have to handle misspellings or any invalid element name. Invalid input is undefined behavior.

**Output**:

The symbol for the element. The first character **must** be capitalized and the rest **must** be lowercase.

Example output: `C`

Test cases:

```
Carbon -> C
NiTROGen -> N
Sodium -> Na
Gold -> Au
Silver -> Ag
Tin -> Sn

```

There are many more elements than states, so I expect it to be harder to find a general rule for these.

This is code golf. Shortest code wins!

# Answer
> 30 votes
# CJam, ~~337~~ ~~297~~ ~~293~~ ~~232~~ ~~220~~ ~~201~~ 200 bytes

```
leu:E2f^3b2+4%_"53N5903CVCT4":i3/=~Ef+b\%]53b"gØâ^ÃP·^À4Î¾^ß^E5^W^Ma{áª^B¤±´oòæ»^XÊQÑ»4Å¾DÙÝòÙ 0^ÝþKa6^Ó£,Ûkû¥¡ùh^E"256b7b6a/0a3**<)5md@5a/,(" ¬^GH/N¿·%^U^RU1²Bd
òë^Ð¼~í^ÌéáU"256b25b'Af+2/='J-'Q/"UU"*\)_5=)*E%2<?(\el

```

The above code uses caret notation, since it contains control characters.

At the cost of 24 additional bytes (for a total of 224), those characters can be avoided.

```
leu:E2f^3b2+4%_"53N5903CVCT4":i3/=~Ef+b\%]53b
"' NwEvKv6e8@]jO4G)=b{L!v@hFQ/oCN)*|BRxvNRL+LO7NI(pLs4[d87$Q%8R\t+' M5JU"
{32f-95b}:B~7b6a/0a3**<)5md@5a/,(
"&y.$h*z^t\rQPUc]l8F h$=18C^r|vD~S"
B25b'Af+2/='J-'Q/"UU"*\)_5=)*E%2<?(\el

```

You can try this code in the CJam interpreter.

### Test cases

```
$ base64 -d > elements.cjam <<< bGV1OkUyZl4zYjIrNCVfIjUzTjU5MDNDVkNUNCI6aTMvPX5FZitiXCVdNTNiImfY4oNQt4A0zr6fBTUXDWF74aoCpLG0b/LmuxjKUdG7NMW+RNnd8tmgMJ3+S2E2k6Ms22v7paH5aAUiMjU2YjdiNmEvMGEzKio8KTVtZEA1YS8sKCIgrAdIL06/tyUVElUxskJkCvLrkLx+7Yzp4VUiMjU2YjI1YidBZisyLz0nSi0nUS8iVVUiKlwpXzU9KSpFJTI8PyhcZWw=
$ cksum elements.cjam
952664534 200 elements.cjam
$ for e in Carbon NiTROGen Sodium Gold Silver Tin; do LANG=en_US cjam elements.cjam <<< $e; echo; done
C
N
Na
Au
Ag
Sn

```

### How it works

The first step is to read the element name from STDIN and apply a rather elaborated hash function, which maps all element names in the range **\[0, 225\]**:

```
l eu :E          " Read a line from STDIN, convert to uppercase and save in E.            ";
2 f^             " XOR each character code with 2.                                        ";
3 b              " Convert to integer; consider the resulting array a base 3 number.      ";
2 + 4 %          " Add 2 and take the result modulo 4. Result: R                          ";
"53N5903CVCT4":i " Push [53 51 78 53 57 48 51 67 86 67 84 52].                            ";
3 / =            " Retrieve the chunk of length 3 that corresponds to R. Result: C        ";
~ E f+           " Add C[2] to all character codes of E.                                  ";
b                " Convert to integer; consider the resulting array a base C[1] number.   ";
\ %              " Take the integer modulo C[0]. Result: M                                ";
] 53 b           " Push H := 53 * R + M.                                                  ";

```

Many element symbols are formed by the first and second, first and third, first and fourth, first and fifth or first and tenth (which is just the first) character of the element's English name. We are going to represent these elements by numbers from 0 to 4 respectively. All remaining elements (represented by 5) will require a lookup table.

The resulting table can be pushed as follows:

```
"gØâ^ÃP·^À4Î¾^ß^E5^W^Ma{áª^B¤±´oòæ»^XÊQÑ»4Å¾DÙÝòÙ 0^ÝþKa6^Ó£,Ûkû¥¡ùh^E"256b7b6a/0a3**

```

The array of character codes gets converted from base 256 to base 7 and 6's are replaced by runs of three 0's.

This is the decision table D:

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

```

The necessary action for the element with hash **1**, e.g., corresponds to the first element of the this array. Array elements that do not correspond to any element's hash are also zero, which allows the **(0 0 0) ↦ 6** compression.

Now, we interpret D for hash H.

```
< ) 5 md     " Push D[:H-1] (D[H-1] / 5) (D[H-1] % 5).                                    ";
@ 5a / , (   " Count the number of 5's in D[:H-1] (by splitting at [5]). Result: I        ";

```

Next, we push the lookup table. If we append **j** to single-character symbols and replace **Uu** with **Q**, each symbol will be exactly two characters long. It can be pushed as follows:

```
" ¬^GH/N¿·%^U^RU1²Bd
òë^Ð¼~í^ÌéáU"256b25b'Af+2/

```

The array of character codes gets converted from base 256 to base 25, the character code of **A** gets added to all digits (casting to Character in the process) and the result is split into chunks of length two.

This is the lookup table L:

```
["QP" "YB" "PD" "SN" "QO" "QT" "QS" "SB" "KJ" "TM" "FE" "PB" "AU" "WJ" "CN" "SG" "RF" "CM" "CU" "HG" "NA" "RG" "AG"]

```

Now, we proceed to compute potential element names.

```
=                " Push L[I].                                                             ";
'J - 'Q / "UU" * " Remove J's and replace Q's with runs of two U's.                       ";
\ ) _ 5 = ) *    " Push S := (D[H-1] % 5 + 1) * ((D[H-1] % 5 + 1 == 5) + 1).              ";
E %              " Push every Sth character of E.                                         ";
2 <              " Discard all but the first two characters.                              ";

```

The stack now contains

```
B M N

```

where **B** is the Boolean **D\[H-1\] / 5**, **M** is the name retrieved from the lookup table an **N** is the element name formed by selecting characters from E.

We're almost done:

```
?                " If B, push M; else, push N.                                            ";
( \              " Extract the first character from the string.                           ";
el               " Convert the rest to lowercase.                                         ";

```

# Answer
> 44 votes
# C, 452

A good hash function helps. There may be better ones. (Improvements suggested by @ugoren et al.)

```
h;main(c){char*p="Sn)Cu&V$U#Mo#Rf#Sg&Cs#Y+FTa%Rb)S'Nd#GaK&Mg'Zr$PtPm%ReUuo#SmDy(Ac$Lu%W&CaRa(Cf)EuB#Ds%Md$Uus*NpIn$H&YbIr*BeEs*Tc#I(FlRuC#ThSrBh/NaCoLrKr&Nb$CePb$Ne'Am)At*PdLa#Tl%HgMt,CrTbBk$Rh&Rn4TeZn$HfAg%Fm)Xe$AlScFePo$As'HeO#LvN&DbGe#Ho&Mn$Cd+Ni$Rg$HsBr$AuSi#Pr&Uup#Se*Ti#Tm$Er$Sb&PPu&Cm$GdBa'Cn&UutLiFr#Ar#Bi#NoOs%Pa4Cl";while((c=getchar())>64)h=(h+c%32+74)*311%441;while(h)if(*p<65?h-=*p++-34,0:1)for(h--;*++p>96;);do putchar(*p++);while(*p>96);}

```

Ungolfed with comments:

```
int h;
main(c) {

  /* Hashed element symbols. Characters #$% etc. are used as padding: */
  char *p="Sn)Cu&V$U#Mo#Rf#Sg&Cs#Y+FTa%Rb)S'Nd#GaK&Mg'Zr$PtPm%ReUuo#SmDy(Ac$Lu%W&C"
          "aRa(Cf)EuB#Ds%Md$Uus*NpIn$H&YbIr*BeEs*Tc#I(FlRuC#ThSrBh/NaCoLrKr&Nb$CeP"
          "b$Ne'Am)At*PdLa#Tl%HgMt,CrTbBk$Rh&Rn4TeZn$HfAg%Fm)Xe$AlScFePo$As'HeO#Lv"
          "N&DbGe#Ho&Mn$Cd+Ni$Rg$HsBr$AuSi#Pr&Uup#Se*Ti#Tm$Er$Sb&PPu&Cm$GdBa'Cn&Uu"
          "tLiFr#Ar#Bi#NoOs%Pa4Cl";

  /* This hash function gives a unique result for each element: */
  while((c=getchar())>64) h=(h+c%32+74)*311%441;

  /* Find the corresponding position in the hashed data */
  while(h) {
    if(*p<65?h-=*p++-34,0:1) {      /* Step over an abbreviation */
      for(h--;*++p>96;);            /* Skip padding */
    }
  }

  /* Output first uppercase character and all following lowercase characters: */
  do {
    putchar(*p++);
  } while(*p>96);
}

```

I used brute force to find this hash; This was the only one with a hash size of ≤512 that had no collisions. I didn't check alternative spellings though, and there might be better functions with different algorithms (e.g. using XOR instead of addition).

The hash function maps text strings to values from 0 to 440. "Tin" hashes to zero, so "Sn" is at the start of the table. The next 7 positions are empty. To keep the code compact, this is indicated by the ASCII value 34+7=41 (")"). Next comes "Copper" (8), four empty cells (34+4=38="&"), and "Vanadium" (13). After calculating a hash, the program steps through the table, subtracting 1 for every capital letter followed by 0 or more lowercase letters, and subtracting (ASCII VALUE)-34 for every non-alphabet character. When the value reaches zero, we have found the correct result.

# Answer
> 13 votes
# JavaScript ES6, 690 ~~708~~ bytes

```
for(n=prompt()[l='toLowerCase'](i=0);!(c='HHeLiBeBCNFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo'.match(x=/[A-Z][a-z]*/g)['HyHeLitBeryBorCarNitFluNeonSoMagAlSiliPhSuChlArgPotCalcScTitVChrManIroCobNicCoppZinGalGeArsSelBrKRubStYttrZirNioMoTecRuthenRhoPaSilvCadInTinAnTelIoXCaeBaLanCePraNeodPromSaEuGadTerDyHoErThuYtteLuHafTaTuRheOsIriPlaGoMerThaLeBiPolAsRadoFrRadiAcThoProtUrNepPluAmCuBerkCaliEiFeMenNoLawRutherDuSeaBohHasMeiDaRoCopeUnuntFleUnunpLivUnunsUnuno'.match(x).map(a=>a[l]()).indexOf(n.slice(0,i++))]);)
alert(c)

```

The first array holds the symbols, and the second array holds the minimum letters necessary to tell which element is being referred to. Thanks to core1024 and edc65 for helping shorten it. Test at http://jsfiddle.net/xjdev4m6/2/. Slightly more readable:

```
n=prompt().toLowerCase()
e='HyHeLitBeryBorCarNitFluNeonSoMagAlSiliPhSuChlArgPotCalcScTitVChrManIroCobNicCoppZinGalGeArsSelBrKRubStYttrZirNioMoTecRuthenRhoPaSilvCadInTinAnTelIoXCaeBaLanCePraNeodPromSaEuGadTerDyHoErThuYtteLuHafTaTuRheOsIriPlaGoMerThaLeBiPolAsRadoFrRadiAcThoProtUrNepPluAmCuBerkCaliEiFeMenNoLawRutherDuSeaBohHasMeiDaRoCopeUnuntFleUnunpLivUnunsUnuno'.match(x=/[A-Z][a-z]*/g).map(a=>a.toLowerCase())
s='HHeLiBeBCNFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo'.match(x)
for(i=0;i<7;i++){
  if(c=s[e.indexOf(n.slice(0,i))]){
    alert(c,i=8) // i=8 breaks out of the loop so the result is only alerted once
  }
}

```

# Answer
> 10 votes
**Ruby 1.9+, 565 471 447  444**

A one-liner. Because nothing is "impossible to do with regexes"...
(Just saved 94 chars by adding another regex) ((and 24 by simplifying them))

```
p"VAlAmA.sArAcAnt|SbA.tBaB..kBeBiB.hBrBDyD.+sD.bE..sErEuF..mFrFlu|F@FlG.dGaGeG|AuH.fH.sHeHoHInIro|FeIrIKrL.vL.+rLaLiLuL|PbM.gMoM.+dM.nM.+tM|HgC.+sC.dC.+fCeCar|C@C....nCaCu|CmCop|CuCoC.rC.lN.+dN.+pNeN..bNit|N@NoNiOsOP..mPa|PdP...aPrP.uP..tPot|KPoPR.*n$RaR.+gR.eRhR.+bR.+fRuS.mScS.+gSeS..v|AgSiSo|NaS.rSTaT.cT.+bTeThu|TmT..lThTin|SnTiTu|WU.u.oU.u.pU.u.sU.u.tUXeY.+bYZ.nZ.r"
.split(/(?<!\|)(?=[A-Z])/).find{|r|/^#{r}/i.match *$*}.gsub /.*\||\W/,''

```

*(newline after string added for "readability", remove for test)*

usage: `ruby periodic.rb aluminum` $\>

Explanation:
Splitting the string on leading capitals returns an array of regex to match against element names. The only alphabetic characters allowed in each are those from the abbreviation\*. They are ordered such that the first match found when comparing to the command line argument `*$*` is the correct one. The trailing gsub strips out the non-alpha characters before printing.

\*Odd abbreviations like "Fe" for "Iron" are handled by a `|` element: "Iro|Fe". The first choice is what is actually matched; the gsub then removes all characters up to the '|', leaving the actual abbreviation.

Test framework (requires @squeamish's list: downloaded as 'table.txt' in the working directory).

```
def testfunc(name)
  #replace with however you call your code
  return `ruby1.9.3 periodic2.rb #{name}`.chomp()
end

elements= File.new('table.txt').readlines.map{|s|s.chomp}

elements.each{|l|
  a,n=l.split(' ')
  r = testfunc(n)
  print "#{n} => #{a} "
  if r!=a then
    print ("FAIL: gave #{r}\n")
    exit
  else
    print("\tOK\n")
  end
}
print("PASS: #{elements.size} elements matched\n")

```

# Answer
> 4 votes
## Ruby, 1068 bytes

```
require"zlib"
require"base64"
$><<eval(Zlib::Inflate.inflate(Base64.decode64"eJwlU8tu2zAQ/Bee+QW6CLYTx0FiR7CdtsmNkmhJCEUKfKQViv57Z9YnE+vd2ZnZ0d+1j2Go6oO2bipzpQ5W6SmPU6nU66S0jatzldqiGmLwVb3VJrZ87NAmoyf9Zx0sKm/alRCnqt5riw514lAvqCejtBm8TZU6Dgp984SGjcMuN3WhUhfsGkNaxqpudHG3Eqv6okdHPLVDXxwIuYmAzCalqn7RxnWkuQN2Z3yPxktH8sbjeQWg8QbV+oceY5iJE1kbDICOHpBE3JNka1zG3wHT3ZeF3hOmw7LYiGpB1XeV+sSIcY4rnwydmQn0hPmYLFduEqpOnhdWg4jcYmlclwyRL3iWdiLTc6s07PNYe0E15wjc+kNPsSOrT9Sm0HLXCZ3BrW0P0iBou9FbyIPSkkfYrs6F1vXsPY9C0aC36entNxVs4LjpZ/EKVX8/ybOnLqzHr8/TzCO0FODgvbreb4dV9bO2npx+oWSTzO6g1ER5bnlZn0eDvIgr9wbqN8kCtIEUG/qVKejFFQvRzYyx2fC6FzxLDAuej4VMg8PzqSeYOHAFrTUtEWAPK80QKQeYwf+B+4gVY5HLXGeaicFKfbS0yGaAvRL35mXsJnwNjnwF3+KHlKv6p4aV4iCIp1lQ3yAyTuLrMxY4k2lXk8kABm8KCXY06wCDR0YDmIiqFf+xfUpzgdYtw+QCc9GAdMqGnDZZtPKAzKLxHYp7JvR+nzNjjZVs7XjhKPpGWpgN8tgYGWNu3rVdcuEnt/DjykRtwG/GOdC5EYfvh5nJWjK+/WJYphts3d2YhZQRrMck0eauPXt9z95jz6/EUuEJEszvyOS9xnsIYcH5xmiLhQ9MkWkDqhcYE0YhvmU0U5ITcMWUGeMjTYgzTqAeUA3W5wFgHMPHhxU7prP4DLD3gmZnY/gGNSflxbIMzROCDnWv31JOUk7yDh3fQf37D7D/kWs="))[gets.downcase[1..5].to_sym]

```

Input via STDIN.

The shortest unique substrings of the element names are from the second to the sixth character (or the end of the name if its too short). So I'm simply getting those and looking them up in a hash. I also compressed the hash because that saves another 200 bytes. Here is what the hash itself looks like:

```
{ydrog:?H,elium:"He",ithiu:"Li",eryll:"Be",oron:?B,arbon:?C,itrog:?N,xygen:?O,luori:?F,eon:"Ne",
 odium:"Na",agnes:"Mg",lumin:"Al",ilico:"Si",hosph:?P,ulfur:?S,hlori:"Cl",rgon:"Ar",otass:?K,
 alciu:"Ca",candi:"Sc",itani:"Ti",anadi:?V,hromi:"Cr",angan:"Mn",ron:"Fe",obalt:"Co",ickel:"Ni",
 opper:"Cu",inc:"Zn",alliu:"Ga",erman:"Ge",rseni:"As",eleni:"Se",romin:"Br",rypto:"Kr",ubidi:"Rb",
 tront:"Sr",ttriu:?Y,ircon:"Zr",iobiu:"Nb",olybd:"Mo",echne:"Tc",uthen:"Ru",hodiu:"Rh",allad:"Pd",
 ilver:"Ag",admiu:"Cd",ndium:"In",in:"Sn",ntimo:"Sb",ellur:"Te",odine:?I,enon:"Xe",esium:"Cs",
 arium:"Ba",antha:"La",erium:"Ce",raseo:"Pr",eodym:"Nd",romet:"Pm",amari:"Sm",uropi:"Eu",
 adoli:"Gd",erbiu:"Tb",yspro:"Dy",olmiu:"Ho",rbium:"Er",huliu:"Tm",tterb:"Yb",uteti:"Lu",
 afniu:"Hf",antal:"Ta",ungst:?W,heniu:"Re",smium:"Os",ridiu:"Ir",latin:"Pt",old:"Au",ercur:"Hg",
 halli:"Tl",ead:"Pb",ismut:"Bi",oloni:"Po",stati:"At",adon:"Rn",ranci:"Fr",adium:"Ra",ctini:"Ac",
 horiu:"Th",rotac:"Pa",raniu:?U,eptun:"Np",luton:"Pu",meric:"Am",urium:"Cm",erkel:"Bk",alifo:"Cf",
 inste:"Es",ermiu:"Fm",endel:"Md",obeli:"No",awren:"Lr",uther:"Rf",ubniu:"Db",eabor:"Sg",
 ohriu:"Bh",assiu:"Hs",eitne:"Mt",armst:"Ds",oentg:"Rg",opern:"Cn",nuntr:"Uut",lerov:"Fl",
 nunpe:"Uup",iverm:"Lv",nunse:"Uus",nunoc:"Uuo"}

```

# Answer
> 4 votes
# JavaScript (Node.js), 298 bytes

```
s=>(i=`23>3c9@94=4E33:3Q0I3:9[020G0O3@74M9=4A6@4;7J5H96?9K0L723E4343A4R40A0T9D3J5H4?4?3J329>9P9;359:0B9^3=95h6:9<6M0~D0@0N3<3;0:9@4<4<6H3I3`.replace(/\D/g,s=>"2".repeat(Buffer(s)[0]-56))[h=parseInt(s,36)*184%901])-9?s[0]+[s[i-1]]:`Ag,Fe,Hg,,W,Sn,K,Cu,Pb,,Sb,Au,,Na`.split`,`[h%418%48%15]||'Uu'+s[4]

```

Try it online!

## How?

### Element groups

We split the elements into 3 groups:

* **Group 1**: 12 elements whose symbol is the first letter of their name, such as `Carbon -> C`.
* **Group 2**: 91 elements whose symbol is the first letter of their name, followed by the \\$n\\$-th letter (0-indexed) with \\$1\le n \le6\\$. Examples: `Helium -> He` (\\$n=1\\$), `Zirconium -> Zr` (\\$n=2\\$).
* **Group 3**: 15 elements that do not belong to the other groups, such as `Iron -> Fe`.

This means that all elements can be encoded with a single digit: we use \\$0\\$ for group 1, \\$n+1\\$ for group 2 and \\$9\\$ for group 3. (Obviously, we'll need some extra data for group 3. More on that later.)

It is worth noting that 44 symbols simply consist of the first two letters of the element name. That's almost 50% of group 2. These ones will be encoded with a `"2"`, so that's the padding character that we want to use in our lookup string.

### Hash function, lookup string and compression

We apply the following hash function (found by brute-force) on the input string:

```
h = parseInt(s, 36) * 184 % 901

```

The corresponding lookup string is \\$899\\$ characters long, which is pretty big.

But, by design, we have many runs of consecutive \\$2\\$'s in there. Our compression strategy is to replace each run of \\$2\\$'s of length \\$2\le n\le70\\$ with the character whose ASCII code is \\$n+56\\$ (that's the range going from `":"` to `"~"`).

The compressed string is only \\$132\\$ characters long.

You can see the decompression process here:

Try it online!

### Decoding

Groups 1 and 2 are decoded the same way:

```
s[0] + [s[i - 1]]

```

(NB: For group 1, `s[-1]` is undefined and `[undefined]` is coerced to an empty string.)

For group 3, we use another hash function and another lookup string (also found by brute-force):

```
`Ag,Fe,Hg,,W,Sn,K,Cu,Pb,,Sb,Au,,Na`.split`,`[h % 418 % 48 % 15]

```

There are 4 remaining superheavy elements that are not included above. Because they are referred to by their temporary names and thanks to the systematic nomenclature, we can build the symbols for these ones by concatenating `"Uu"` with the fifth letter of their name:

```
    v
Unun**t**rium   -> Uut
Unun**p**entium -> Uup
Unun**s**eptium -> Uus
Unun**o**ctium  -> Uuo
    ^
```

Hence the last part of the code:

```
|| 'Uu' + s[4]

```

# Answer
> 3 votes
# Python - ~~652 649~~ 637

My hash table is based on the combination of every second and every third character of the uppercase name:

```
import re
def f(s,c='S<8F0FCE;2.ACR;J@W$;BI8>GD*?GnHQ<K>&T\(51IAg/Y?S2=169.,325(F(98?>?=^97DUCITX;SJ`0C<P9iLP/G4B,A(-A?(3QLLZ;81D(.4F;L8GaVP[=\=cOX3U,LQl6:E9/OXdSe(4,TSV/=FN98?K.18Q>R$+<GG[IS-4?;4H;T/IMq9<LXMYH4HG<>>KTT,>IIEM,[Nf<,:Z60(A9fImZTMRTcM?[lVg^qC}',e='HHeLiBeBCNOFNeNaMgAlSiPSClArKCaScTiVCrMnFeCoNiCuZnGaGeAsSeBrKrRbSrYZrNbMoTcRuRhPdAgCdInSnSbTeIXeCsBaLaCePrNdPmSmEuGdTbDyHoErTmYbLuHfTaWReOsIrPtAuHgTlPbBiPoAtRnFrRaAcThPaUNpPuAmCmBkCfEsFmMdNoLrRfDbSgBhHsMtDsRgCnUutFlUupLvUusUuo'):
 U=s.upper();X=lambda x:chr(32+sum(ord(u)-65for u in x))
 return re.findall('[A-Z][a-z]*',e)[zip(c[::2],c[1::2]).index((X(U[1::3]),X(U[:-1:2])))]

```

Here is the corresponding generator:

```
table = '''
H     Hydrogen
He    Helium
...
Uuo   Ununoctium
'''

table = map(lambda l: l.split(), table.split('\n')[1:-1])

abbr = []
for name in map(str.upper, zip(*table)[1]):
    abbr.append(chr(32+sum(ord(u)-65 for u in name[1::3]))+
                chr(32+sum(ord(u)-65 for u in name[:-1:2])))
print 'c=' + ''.join(abbr)
print 'e=' + ''.join(zip(*table)[0])
print 'Unique' if len(table) == len(set(abbr)) else 'Duplicates'

```

There's probably room for improvements, especially compressing the two long strings.

Tested with:

```
for short, name in table:
    if f(name) != short:
        print "Wrong result!"

```

# Answer
> 3 votes
# CJam, ~~462 449 434 401 391 384~~ 382

With help from Dennis.

## Code

Nested ternary ifs are ***probably*** not the right way to do this in CJam.

```
rel_"ruthen"#!"Ru"{_"tel"#!"Te"{__5{\_ceu\@=+_}:U~"PdYbRgCmCn"{\#)!}:X~{;__4U"RnPaCfDs"X{;_3U"NbCsNdPmTbPtTlBkEsFmMdLrMt"X{;2U"MgClCrMnZnAsRbSrZrTcCdSmGdHfReAtNpPuDbBhHsLv"X{;__"sili"#{;__ceu\1=@2=++"SodIroCopSilTinAntThuGolMerLeaTunPotRutSeaHydBorCarNitOxyFluPhoSulVanYttIodUra"\#3d/m[)"_NaFeCuAgSnSbTmAuHgPbWKRfSgHBCNOFPSVYIU"S%\=_"_"={;_1U"Un"={;4="Uu"\+}*}*}"Si"?}*}*}*}*}?}?]W=

```

With indents:

```
rel
_"ruthen"#!"Ru"
{
_"tel"#!"Te"
{
  __5{\_ceu\@=+_}:U~
  "PdYbRgCmCn"{\#)!}:X~
  {
   ;__4U
   "RnPaCfDs"X
   {
    ;_3U
    "NbCsNdPmTbPtTlBkEsFmMdLrMt"X
    {
     ;2U
     "MgClCrMnZnAsRbSrZrTcCdSmGdHfReAtNpPuDbBhHsLv"X
     {

       ;__"sili"#
       {
        ;__ceu\1=@2=++"SodIroCopSilTinAntThuGolMerLeaTunPotRutSeaHydBorCarNitOxyFluPhoSulVanYttIodUra"\#3d/m[)"_ Na Fe Cu Ag Sn Sb Tm Au Hg Pb W K Rf Sg H B C N O F P S V Y I U"S%\=_"_"=
        {;_1U"Un"={;4="Uu"\+}*}*
       }
      "Si"?

     }*
    }*
   }*
  }*
 }?
}?
]W=

```

Many of the symbols are just the first two letters of the element's name. These are handled in the second-deepest layer of nested if statements. Many others are the first and third letter, or the first and fourth letter - these are handled in successive outer layers. Symbols where only the first letter appears, and complete irregulars, are handled in the fifth and third deepest layers respectively.

There are a few where it gets confused (`TelLurium` vs `ThaLlium`, or `SILicon` vs `SILver`, or `RUThenium` vs `RUTherfordium`). These are handled separately.

A lot of golfing could be done here, mostly by reusing code blocks and improving handling of irregulars.

# Answer
> 3 votes
# PHP, 507 485 476 466 characters

Usage: enter the element name as GET parameter '0' - elements.php?0=carbon

Algorithm: Run through the data string, pulling out substring,abbreviation code pairs. If the substring matches the start of the element passed in, use the abbreviation code to determine what to output: If the code starts with a letter, output it as a string. If it is a number N, output the first letter of the element + the Nth letter. The Unun elements are special-cased with the code '|'. If no substring is found that matches the name passed in, output the first two characters of the name as the abbreviation.

Readable Code:

```
<?
$l=ucfirst(strtolower($_GET[0]));
for(
  $m[3]="AnSbArs2As2Berk3Boh2BoBCad2Cae3Cali4CarCChl2Ch2Cope5CopCuCu5Da4Du2Ei3Fe3FluFGad2GoAuHaf2Ha2HyHIo0IroFeLaw3LePbLiv2Mag2Man2Mei3Men3MeHgNeod3Nep2Nio3NiNOxOPa5PhPPla3Plu2PotKProm3Pro4Rado4Rhe2Roe5Rub2Ruther6Sa2Sea6SilvAgSoNaSt2SuSTec2Ter3Tha3Thu6TinSnTuWUn|UUVVYtte5YYZin2Z2";
  preg_match('/(.[a-z]*)(.[a-z]*)(.*)/',$m[3],$m)
;)
    if(strstr($l,$m[1]))
        echo($x=$m[2][0])>'@'?$x>'{'?"Uu$l[4]":$m[2]:$l[0].$l[$x],die;
echo$l[0],$l[1];

```

Condensed:

```
<?$l=ucfirst(strtolower($_GET[0]));for($m[3]="AnSbArs2As2Berk3Boh2BoBCad2Cae3Cali4CarCChl2Ch2Cope5CopCuCu5Da4Du2Ei3Fe3FluFGad2GoAuHaf2Ha2HyHIo0IroFeLaw3LePbLiv2Mag2Man2Mei3Men3MeHgNeod3Nep2Nio3NiNOxOPa5PhPPla3Plu2PotKProm3Pro4Rado4Rhe2Roe5Rub2Ruther6Sa2Sea6SilvAgSoNaSt2SuSTec2Ter3Tha3Thu6TinSnTuWUn|UUVVYtte5YYZin2Z2";preg_match('/(.[a-z]*)(.[a-z]*)(.*)/',$m[3],$m);)if(strstr($l,$m[1]))echo($x=$m[2][0])>'@'?$x>'{'?"Uu$l[4]":$m[2]:$l[0].$l[$x],die;echo$l[0],$l[1];

```

# Answer
> 3 votes
# 05AB1E, ~~121~~ ~~117~~ ~~112~~ ~~110~~ 109 bytes

```
•S²c¾rƒã∞Øø”.ÑSZl›¹'•2в°T•2nZιć‹ε˜Órv†„₃}Z$+àFQ$•7в1.•®DÝ∍ÌoƵižÒƵaŒ•2ô.;.;6ÝIS¬ì:slƵ{ö•X»²ÄµÕΛεĀδkM•9ävy%}èÙ™

```

Try it online! or validate all test cases.

# Answer
> 2 votes
## Golfscript - 1052 821

```
{.91<32*+}%:x;'H
He
Li
Be
B
C
N
F
Ne
Na
Mg
Al
Si
P
S
Cl
Ar
K
Ca
Sc
Ti
V
Cr
Mn
Fe
Co
Ni
Cu
Zn
Ga
Ge
As
Se
Br
Kr
Rb
Sr
Y
Zr
Nb
Mo
Tc
Ru
Rh
Pd
Ag
Cd
In
Sn
Sb
Te
I
Xe
Cs
Ba
La
Ce
Pr
Nd
Pm
Sm
Eu
Gd
Tb
Dy
Ho
Er
Tm
Yb
Lu
Hf
Ta
W
Re
Os
Ir
Pt
Au
Hg
Tl
Pb
Bi
Po
At
Rn
Fr
Ra
Ac
Th
Pa
U
Np
Pu
Am
Cm
Bk
Cf
Es
Fm
Md
No
Lr
Rf
Db
Sg
Bh
Hs
Mt
Ds
Rg
Cn
Uut
Fl
Uup
Lv
Uus'n/'hy
he
lit
bery
bor
car
nit
flu
neon
so
mag
al
sili
ph
su
chl
arg
pot
calc
sc
tit
v
chr
man
iro
cob
nic
copp
zin
gal
ge
ars
sel
br
k
rub
st
yttr
zir
nio
mo
tec
ruthen
rho
pa
silv
cad
in
tin
an
tel
io
x
cae
ba
lan
ce
pra
neod
prom
sa
eu
gad
ter
dy
ho
er
thu
ytte
lu
haf
ta
tu
rhe
os
iri
pla
go
mer
tha
le
bi
pol
as
rado
fr
radi
ac
tho
prot
ur
nep
plu
am
cu
berk
cali
ei
fe
men
no
law
ruther
du
sea
boh
has
mei
da
ro
cope
ununt
fle
ununp
liv
ununs
ununo'n/[{x\?)}/]1?=

```

Explanation:

```
{        }%                              Map these ops to the input string:
 .91<32*+                                   Add 32 if less than 91 (convert to lowercase, in essence)
           :x;                           Store to x.
              '...'  '...'               The first array is the symbols, the second is the names.
                                         (stripped down to the minimum necessary)
                   n/     n/             Convert them to arrays.
                             {    }/     For each element in the name array...
                              x\?)          ...return 1 if the element is found in the input.
                            [       ]    Gather every element in an array...
                                     1?  Find the 1 in the array (the only element name match)...
                                       = ...then return that symbol in the symbol array.
                               (implied) Print.

```

# Answer
> 2 votes
## JavaScript (1100)

Naive implementation shining in its simplicity. Unique sub string from the start of the name is simply mapped to symbol.

```
e={hy:"H",he:"He",lit:"Li",bery:"Be",bor:"B",car:"C",nit:"N",ox:"O",flu:"F",neon:"Ne",so:"Na",mag:"Mg",al:"Al",sili:"Si",ph:"P",su:"S",chl:"Cl",arg:"Ar",pot:"K",calc:"Ca",sc:"Sc",tit:"Ti",v:"V",chr:"Cr",man:"Mn",iro:"Fe",cob:"Co",nic:"Ni",copp:"Cu",zin:"Zn",gal:"Ga",ge:"Ge",ars:"As",sel:"Se",br:"Br",k:"Kr",rub:"Rb",st:"Sr",yttr:"Y",zir:"Zr",nio:"Nb",mo:"Mo",tec:"Tc",ruthen:"Ru",rho:"Rh",pa:"Pd",silv:"Ag",cad:"Cd",in:"In",tin:"Sn",an:"Sb",tel:"Te",io:"I",x:"Xe",cae:"Cs",ba:"Ba",lan:"La",ce:"Ce",pra:"Pr",neod:"Nd",prom:"Pm",sa:"Sm",eu:"Eu",gad:"Gd",ter:"Tb",dy:"Dy",ho:"Ho",er:"Er",thu:"Tm",ytte:"Yb",lu:"Lu",haf:"Hf",ta:"Ta",tu:"W",rhe:"Re",os:"Os",iri:"Ir",pla:"Pt",go:"Au",mer:"Hg",tha:"Tl",le:"Pb",bi:"Bi",pol:"Po",as:"At",rado:"Rn",fr:"Fr",radi:"Ra",ac:"Ac",tho:"Th",prot:"Pa",ur:"U",nep:"Np",plu:"Pu",am:"Am",cu:"Cm",berk:"Bk",cali:"Cf",ei:"Es",fe:"Fm",men:"Md",no:"No",law:"Lr",ruther:"Rf",du:"Db",sea:"Sg",boh:"Bh",has:"Hs",mei:"Mt",da:"Ds",ro:"Rg",cope:"Cn",ununt:"Uut",fle:"Fl",ununp:"Uup",liv:"Lv",ununs:"Uus",ununo:"Uuo"}
n=prompt().toLowerCase()
for(i in e)n.indexOf(i)?i:alert(e[i])

```

# Answer
> 2 votes
## C# (826)

not the greatest but I thought I'd try it with the handicap of c#.

```
using System;class P{static string s="HyHHe1Li1Be1BoBCaCNitNOxOFlFNe1SoNaMaMgAl1Sil1PhPSuSChClAr1PotKCal1Sc1Tit1VaVChrCrManMnIrFeCo1Ni1CopCuZiZnGa1Ge1ArsAsSe1Br1Kr1RuRbStSrYtYZirZrNioNbMo1TecTcRut1Rh1PaPdSiAgCadCdIn1TiSnAnSbTel1IoIXe1CaeCsBa1La1Ce1Pra1NeoNdPrPmSaSmEu1GadGdTeTbDy1Ho1Er1ThTmYttYbLu1HaHfTa1TuWRheReOs1Iri1PlPtGoAuMeHgThaTlLePbBi1Po1AsAtRaRnFr1Rad1Ac1Tho1ProPaUrUNepNpPluPuAm1CuCmBerBkCaliCfEiEsFeFmMenMdNo1LawLrRuthRfDuDbSeaSgBohBhHasHsMeiMtDaDsRoRgCopeCnUnUutFle1UnuUupLivLvUnunUus",n,t,k;static void Main(){var d=new System.Collections.Specialized.StringDictionary();while(s!=""){k=g;d[k]=g;if(d[k]=="1")d[k]=k.Substring(0,2);};t=Console.ReadLine();while(t!=""&!d.ContainsKey(t))t=t.Remove(t.Length-1);Console.Write(d[t]);}static string g{get{n="";do n+=s[0];while((s=s.Remove(0,1))!=""&&s[0]>96);return n;}}}

```

So I wrote a program to turn the full name of elements (e.g. carbon) in to the smallest but still unique string possible and did this for all elements with respect to all the other unique strings. I then serialized that in to a big ugly string where capital letters denote the start of "chunks", with chunks alternating between being keys and values. Like KeyValueKey2Value2 etc.

This script desterilizes that big string and cuts a character off the end of the inputted string until it finds it in the dictionary made from the big string.

(I should add my knowledge of C# isn't amazing and the original submission I made was just using things I knew but I've subsequently had some tricks pointed out to me by others.)

# Answer
> 2 votes
# Haskell, 920 817 807 776 Chars

After working far too long creating a system of rules for what characters of an elements name are included in its symbol, and a bit of tinkering, I managed to write a script that translates element to symbol easily. Iron was a problem for me, because I could sample certain characters from GOld, SilVer, TiN, LEad, SoDium, MerCury, ANtimony, PotaSsium, and TUngsten, converting them to an unused periodic symbol (I chose whichever sampling made it simplest to integrate them into the existing rules), and then translating after symbolic conversion; Iron, however, was a problem, because Ir, Io, and In are all used already. This was initially 920 characters, but I realized that the final pattern match (the largest) didn't need to be there, as it either let things drop through (which it didn't) or matched all of them; therefore, I replaced it with a catch-all wildcard. After that, I further golfed from 817 to 808 by abbreviating some patterns using wild-cards in such a way that they were still unique to that element name (e.g. the only element with a 'w' in its name is Lawrencium, so "\*w" matches that in 1 less character than "Law").

Here is my code. I tested it for all of the elements, and I coded it so that it automatically converted its input to titlecase, so no issues with case sensitivity.

## EDIT 1

I further reduced it to 776 characters by replacing the case expression in t with a pattern match (this makes sense because the case expression was testing the raw operand as opposed to an expression in terms of the operand), removing unnecessary parentheses, and re-expressing `e` as a newline-delimited string instead of a list of strings, and later splitting it in the main function. Because these changes are purely golfing, I have left the human-readable version unchanged.

```
import Data.Char
m _[]=True;m[]_=False;m k@(c:s)x@(y:z)=case y of{']'->m s x;'['->let(i,(_:j))=break(==']')z in(c`elem`i)&&m s j;'?'->m s z;'*'->null z||m k z||m s z||m s x;_->c==y&&m s z};p(a:t)(x:y)=case a of{'.'->x:p t y;'_'->p t y;_->a:p t y};p[]_=[];e="Iro\nUn\nCu Pa Ro Y*e\nR*r\n*pp\nCop Rado\nSea Thu\nCali Da P*ot Tha\nA*s Boh ?ub Ch [CG]ad [HM]a Liv Nep Plu Rhe S[ato] Tec Tin Z\nB*k Cae [ES]i *w Nio [FM]e N*d Pro Pla Ter\nBor Car Flu Hy Io Nit Ox Ph Su [UVY]\n*";s="Fe ._._. .____. .f .u .n ._____. .___. ._. .__. . ..";t"Sv"="Ag";t"Sd"="Na";t"Go"="Au";t"Le"="Pb";t"Mc"="Hg";t"An"="Sb";t"Ps"="K";t"Tu"="W";t"Tn"="Sn";t x=x;main=interact$unlines.map(\(a:b)->let y=toUpper a:map toLower b in t$p(snd.head.filter(any(m y).fst)$zip(map words$lines e)$words s)y).lines

```

Human-Readable Version (newlines, spacing, verbose names, comments: 2311 Chars)

```
import Data.Char

-- Test against search-pattern strings
match _ [] = True
match [] _ = False
match k@(c:s) x@(y:z) = case y of
']' -> match s x
'[' -> let (i,(_:j)) = break (==']') z in (c `elem` i) && match s j
'?' -> match s z
'*' -> null z || match k z || match s z || match s x
 _  -> c == y && match s z

-- Write according to name-pattern string
pattern (a:t) (x:y) = case a of
'.' -> x : (pattern t y)
'_' -> (pattern t y)
 _  -> a : (pattern t y)
pattern [] _ = []

-- Search-Patterns for the elements
elements=["Iro", -- Iron -> Fe
      "Un", -- UnUn-Blank-ium (1,3,5)
      "Cu Pa Ro Y*e", -- CuriuM PallaDium RoentGenium YtterBium (1,6)
      "R*r", -- Rutherfordium (1,f)
      "*pp", -- Copper (1,u)
      "Cop Rado", -- Copernicium Radon (1,n)
      "Sea Thu", -- SeaborGium ThuliuM (1,7)
      "Cali Da P*ot Tha", -- CaliFornium DarmStadtium ProtActinium PotaSsium (1,5)

      {- AsTatine ArSenic BoHrium DuBnium RuBidium ChLorine ChRome CaDmium
      GaDolinium HaFnium HaSsium MaNganese MaGnesium LiVermorium NePtunium
      PlUtonium RhEnium SaMarium StRontium SoDium TeChnetium TiN ZiNc
      ZiRconium (1,3) -}

      "A*s Boh ?ub Ch [CG]ad [HM]a Liv Nep Plu Rhe S[ato] Tec Tin Z",

      {- BerKelium CaeSium EinSteinum SilIcon SilVer LawRencium NioBium
      FerMium MenDelevium MeiTnerium MerCury NeoDymium ProMethium PlaTinum
      TerBium (1,4) -}

      "B*k Cae [ES]i *w Nio [FM]e N*d Pro Pl Ter",

      {- Boron Carbon Fluorine Hydrogen Nitrogen Oxygen Phosphorous Sulphur
      Uranium Vanadium Yttrium (1) -}

      "Bor Car Flu Hy Io Nit Ox Ph Su [UVY]",
      "*"] -- Everything else (1,2)

-- respective naming patterns for searches
symbol = "Fe ._._. .____. .f .u .n ._____. .___. ._. .__. . .."

-- Translate fake symbols
translate x = case x of
"Sv" -> "Ag" -- SilVer
"Sd" -> "Na" -- SoDium
"Go" -> "Au" -- GOld
"Le" -> "Pb" -- LEad
"Mc" -> "Hg" -- MerCury
"An" -> "Sb" -- ANtimony
"Ps" -> "K" -- PotaSsium
"Tu" -> "W" -- TUngsten
"Tn" -> "Sn" -- TiN
  _  -> x  -- Keep everything else the same

main = interact $ unlines . map (\(a:b) -> let y = (toUpper a) : (map toLower b) in t $ p (snd.head.filter (any (m y) . fst) $ zip (map words e) $ words s) $ y) . lines

```

If anyone is interested in an explanation for any part of this, feel free to ask.

# Answer
> 1 votes
JavaScript (E6) 1433

Here is un upper limit

```
F=n=>'0H0HYDROGEN0He0HELIUM0Li0LITHIUM0Be0BERYLLIUM0B0BORON0C0CARBON0N0NITROGEN0O0OXYGEN0F0FLUORINE0Ne0NEON0Na0SODIUM0Mg0MAGNESIUM0Al0ALUMINIUM0Si0SILICON0P0PHOSPHORUS0S0SULFUR0Cl0CHLORINE0Ar0ARGON0K0POTASSIUM0Ca0CALCIUM0Sc0SCANDIUM0Ti0TITANIUM0V0VANADIUM0Cr0CHROMIUM0Mn0MANGANESE0Fe0IRON0Co0COBALT0Ni0NICKEL0Cu0COPPER0Zn0ZINC0Ga0GALLIUM0Ge0GERMANIUM0As0ARSENIC0Se0SELENIUM0Br0BROMINE0Kr0KRYPTON0Rb0RUBIDIUM0Sr0STRONTIUM0Y0YTTRIUM0Zr0ZIRCONIUM0Nb0NIOBIUM0Mo0MOLYBDENUM0Tc0TECHNETIUM0Ru0RUTHENIUM0Rh0RHODIUM0Pd0PALLADIUM0Ag0SILVER0Cd0CADMIUM0In0INDIUM0Sn0TIN0Sb0ANTIMONY0Te0TELLURIUM0I0IODINE0Xe0XENON0Cs0CAESIUM0Ba0BARIUM0La0LANTHANUM0Ce0CERIUM0Pr0PRASEODYMIUM0Nd0NEODYMIUM0Pm0PROMETHIUM0Sm0SAMARIUM0Eu0EUROPIUM0Gd0GADOLINIUM0Tb0TERBIUM0Dy0DYSPROSIUM0Ho0HOLMIUM0Er0ERBIUM0Tm0THULIUM0Yb0YTTERBIUM0Lu0LUTETIUM0Hf0HAFNIUM0Ta0TANTALUM0W0TUNGSTEN0Re0RHENIUM0Os0OSMIUM0Ir0IRIDIUM0Pt0PLATINUM0Au0GOLD0Hg0MERCURY0Tl0THALLIUM0Pb0LEAD0Bi0BISMUTH0Po0POLONIUM0At0ASTATINE0Rn0RADON0Fr0FRANCIUM0Ra0RADIUM0Ac0ACTINIUM0Th0THORIUM0Pa0PROTACTINIUM0U0URANIUM0Np0NEPTUNIUM0Pu0PLUTONIUM0Am0AMERICIUM0Cm0CURIUM0Bk0BERKELIUM0Cf0CALIFORNIUM0Es0EINSTEINIUM0Fm0FERMIUM0Md0MENDELEVIUM0No0NOBELIUM0Lr0LAWRENCIUM0Rf0RUTHERFORDIUM0Db0DUBNIUM0Sg0SEABORGIUM0Bh0BOHRIUM0Hs0HASSIUM0Mt0MEITNERIUM0Ds0DARMSTADTIUM0Rg0ROENTGENIUM0Cn0COPERNICIUM0Uut0UNUNTRIUM0Fl0FLEROVIUM0Uup0UNUNPENTIUM0Lv0LIVERMORIUM0Uus0UNUNSEPTIUM0Uuo0UNUNOCTIUM'
.match(RegExp('([^0]+)0+'+n,'i'))[1]

```

**Test** in FireFox/FireBug console

```
F('Rutherfordium')

```

*Output*

```
Rf

```

# Answer
> 1 votes
# SmileBASIC, ~~1763~~ ~~1418~~ ~~1204~~ 1128 bytes

```
INPUT E$Hro$="H
Hiu$="He
Lhi$="Li
Byl$="Be
Bon$="B
Cbo$="C
Nro$="N
Oge$="O
For$="F
Nn$="Ne
Siu$="Na
Mne$="Mg
Ami$="Al
Sic$="Si
Psp$="P
Sfu$="S
Cor$="Cl
Aon$="Ar
Pas$="K
Cci$="Ca
Snd$="Sc
Tan$="Ti
Vad$="V
Com$="Cr
Mga$="Mn
In$="Fe
Cal$="Co
Nke$="Ni
Cpe$="Cu
Zc$="Zn
Gli$="Ga
Gma$="Ge
Aen$="As
Sen$="Se
Bmi$="Br
Kpt$="Kr
Rid$="Rb
Son$="Sr
Yri$="Y
Zco$="Zr
Nbi$="Nb
Myb$="Mo
Thn$="Tc
Rhe$="Ru
Rdi$="Rh
Pla$="Pd
Sve$="Ag
Cmi$="Cd
Iiu$="In
T$="Sn
Aim$="Sb
Tlu$="Te
Iin$="I
Xon$="Xe
Csi$="Cs
Biu$="Ba
Lth$="La
Pse$="Pr
Ndy$="Nd
Pme$="Pm
Sar$="Sm
Eop$="Eu
Gol$="Gd
Tbi$="Tb
Dpr$="Dy
Hmi$="Ho
Eiu$="Er
Tli$="Tm
Yer$="Yb
Let$="Lu
Hni$="Hf
Tta$="Ta
Tgs$="W
Rni$="Re
Oiu$="Os
Idi$="Ir
Pti$="Pt
Gd$="Au
Mcu$="Hg
Tll$="Tl
Ld$="Pb
Bmu$="Bi
Pon$="Po
Aat$="At
Ron$="Rn
Fnc$="Fr
Riu$="Ra
Ain$="Ac
Tri$="Th
Pta$="Pa
Uni$="U
Ntu$="Np
Pto$="Pu
Ari$="Am
Ciu$="Cm
Bke$="Bk
Cif$="Cf
Est$="Es
Fmi$="Fm
Mde$="Md
Nel$="No
Lre$="Lr
Dni$="Db
Sbo$="Sg
Bri$="Bh
Hsi$="Hs
Mtn$="Mt
Dms$="Ds
Rnt$="Rg
Cer$="Cn
Unt$="Uut
Fro$="Fl
Unp$="Uup
Ler$="Lv
Uns$="Uus
Uno$="Uuo
S$=VAR(E$[0]+MID$(E$,3,2))IF"Cm"==S$*!VAL(".1"+E$[1])THEN S$="Ce
IF LEN(E$)>12THEN S$="Rf
?S$

```

I chose 3 characters which were mostly unique (the 0th, 2nd, and 3rd), which leaves 2 special cases: Cerium/Curium are both "Ciu", and Ruthenium/Rutherfordium are both "Rhe". For Ciu, I check if the second character of the name is "e" or "E", and for "Rhe", I check the length of the name.

`VAR(name)` returns the variable with that name. Variable names are case insensitive.

# Answer
> 1 votes
# Retina, ~~291~~ ~~286~~ 276 bytes

```
.*
$u
Pot
K
op
u
Iro
Fe
Silv
Ag
Tin
Sn
0L`.*f|[RS].*g|[CGP]a.*d|(As|Ch|G|Law|Ma|Me.|Pla?|Prot?|Rado|St|Tha|Unun|Zi).|Flu|N[ei]o?[bdpt]|[ACEH].*s|[BDLRST].[bcehmv]|..+r[bkmn]s?|[CT]h?u.*m|..
\B.*\B

T`l``[FHKNOSVY][at-y]|Cb|Bo|Io|Ph|Ur
So
Na
An
Sb
Tu
W
Go
Au
Mc
Hg
Le
Pb
U.
U$l

```

Try it online!

Verification script (Python)

## Explanation

```
.*
$u

```

Convert the first letter of the input to uppercase and the rest to lowercase.

```
0L`.*f|[RS].*g|[CGP]a.*d|(As|Ch|G|Law|Ma|Me.|Pla?|Prot?|Rado|St|Tha|Unun|Zi).|Flu|N[ei]o?[bdpt]|[ACEH].*s|[BDLRST].[bcehmv]|..+r[bkmn]s?|[CT]h?u.*m|..

```

Truncate each element name, ending with the intended second letter. The default case `..` matches the first two letters of the element name.

```
\B.*\B

```

Keep only the first and last letter.

```
T`l``[FHKNOSVY][at-y]|Cb|Bo|Io|Ph|Ur

```

Remove the lowercase letters from the single-letter abbreviations.

```
U.
U$l

```

Insert the `u` for the elements that require it.

---

The rest of the program deals with various special-case replacements. Some of these occur before the main regex because those elements share their first two letters with another.

# Answer
> 0 votes
# T-SQL, ~~900 894~~ 676 bytes

```
SELECT ISNULL((SELECT LEFT(value,3)FROM
STRING_SPLIT('Sb An-As Ars-At Ast-Bk Berk-Bh Boh-B  Bor-Cd Cad-Cs Cae-Cf Cali-C  Car-Cl Chl-Cr Chr-Cn Cope-Cu Copp-Cm Cu-Ds Da-Db Du-Es Ei-Fm Fe-F  Flu-Gd Gad-Au Go-Hf Haf-Hs Has-H  Hy-I  Io-Fe Iro-Lr Law-Pb Le-Lv Liv-Mg Mag-Mn Man-Mt Mei-Md Men-Hg Mer-Nd Neod-Np Nep-Nb Nio-N  Nit-O  Ox-Pd Pa-P  Ph-Pt Pla-Pu Plu-K  Pot-Pm Prom-Pa Prot-Rn Rado-Re Rhe-Rg Ro-Rb Rub-Rf Ruther-Sm Sa-Sg Sea-Ag Silv-Na So-Sr St-S  Su-Tc Tec-Tb Ter-Tl Tha-Tm Thu-Sn Tin-W  Tu-UuoUnuno-UupUnunp-UusUnuns-UutUnunt-U  Ur-V  V-Yb Ytte-Y  Yttr-Zn Zin-Zr Zir'
    ,'-')m,t WHERE e LIKE SUBSTRING(value,4,9)+'%'),
(SELECT UPPER(LEFT(e,1))+LOWER(SUBSTRING(e,2,1))FROM t))

```

Returns are for readability only, the second line is one very long string.

`STRING_SPLIT` is supported in SQL 2016 and higher.

Input is taken via a pre-existing table **t** with varchar field **e**, per our IO standards. Output is padded with spaces to 3 characters; the rules were unclear on whether that was ok. If necessary, I can add a `TRIM`.

The input table is joined with a table generated with a list of all element symbols (padded to 3 characters) with the shortest unique prefix for each element name (`X` is sufficient for *Xenon*, but *Rutherfordium* requires `Ruther` to distinguish it from *Ruthenium*).

**EDIT 1**: Saved 218 characters by removing the 44 entries from the list whose symbol is the first two letters of their name; the `ISNULL` function is used to see if the first query fails to return a row, and if so, generates the symbol (properly cased) from the input element name.

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


title: Implement Sleep Sort

text:
# Question
Title: Implement Sleep Sort
Sleep Sort is an integer sorting algorithm I found on the Internet. It opens an output stream, and for each input numbers in parallel, delay for the number seconds and output that number. Because of the delays, the highest number will be outputted last. I estimate it has O(n + m), where n is the number of elements and m is the highest number.

Here is the original code in Bash

```
#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

```

Here is the pseudocode

```
sleepsort(xs)
 output = []
 fork
   for parallel x in xs:
     sleep for x seconds
     append x to output
 wait until length(output) == length(xs)
 return output

```

Your task is to implement Sleep Sort as a function in the programming language of your choice. You can neglect any concurrency factors such as race conditions and never lock any shared resources. The shortest code wins. The function definition counts toward the code length.

The input list is limited to non-negative integers only, and the length of the input list is expected to reasonably long (test at least 10 numbers) so race conditions never happen. and assuming race conditions never happen.

# Answer
A kind of lame **Perl** attempt, 59 55 52 38 **32 characters**:

`map{fork||exit print sleep$_}@a`

**Barebones: 25 Characters:**

...if you don't mind the sort results as die output:

`map{fork||die sleep$_}@a`

**With all the trimmings:**

(for maximum challenge compliance, **44** characters)

`sub t{map{fork||exit print sleep$_}@_;wait}`

If you let perl do the wait for you, **39** characters:

`sub t{map{fork||exit print sleep$_}@_}`

And again, if you don't mind `die()`, **32** characters...

`sub t{map{fork||die sleep$_}@_}`

Note that in Perl 6, or when the 'say' feature is declared, it is possible to replace the `print` function with `say`, saving a character in each instance. Obviously since `die` both terminates the forked process and writes the output, it remains the shortest solution.
> 17 votes

# Answer
**C**, 127 characters, a rather obvious solution:

```
main(int c,char**v){
#pragma omp parallel for num_threads(c)
for(int i=1;i<c;++i){int x=atoi(v[i]);sleep(x);printf("%d ",x);}}

```

(Compiled with `gcc -std=c99 -fopenmp sort.c` and ignoring all warnings.)
> 21 votes

# Answer
## APL (~~15~~ 13)

```
{⎕←⍵⊣⎕DL⍵}&¨⎕

```

What it does:

```
¨⎕       : for each element of the input
&        : do on a separate thread
⎕DL⍵    : wait approx. ⍵ seconds
⎕←⍵     : output ⍵

```
> 16 votes

# Answer
## Ruby 1.9, 32 characters

As a function:

```
s=->a{a.map{|i|fork{p sleep i}}}

```

If we can just use a predefined variable, it reduces to 25 characters:

```
a.map{|i|fork{p sleep i}}

```
> 15 votes

# Answer
**JavaScript**, 65 characters *(depending on whether you use `console.log` or something else for outputting the result)*

```
a.map(function(v){setTimeout(function(){console.log(v)},v*1000)})

```

This assumes that `a` is an array of non-negative integers and that `map()` exists on the array prototype (JavaScript 1.6+).
> 14 votes

# Answer
Four tries in Erlang:

Output to the console, have taken the liberty to do this each `9ms * Number` since this is plenty enough to make it work (tested on a Atom embedded board = slow):

**Needs 60 chars**

```
s(L)->[spawn(fun()->timer:sleep(9*X),io:write(X)end)||X<-L].

```

Output to the console is total un-Erlangish, so we send a message to process `P` instead:

**Needs 55 chars**

```
s(P,L)->[spawn(fun()->timer:sleep(9*X),P!X end)||X<-L].

```

Sending after a time can also be done differently (this even works with `1ms * Number`):

**Needs 41 chars**

```
s(P,L)->[erlang:send_after(X,P,X)||X<-L].

```

Actually this is a bit unfair since the built in function `send_after` is a late comer and needs the namespace `erlang:` prefixed, if we consider this namespace imported (done on module level):

**Needs 34 chars**

```
s(P,L)->[send_after(X,P,X)||X<-L].

```
> 9 votes

# Answer
# Python - 81 ~~93~~ ~~148~~ ~~150~~ ~~153~~

Tweaking @BiggAl's code, since that's the game we're playing....

```
import threading as t,sys
for a in sys.argv[1:]:t.Timer(int(a),print,[a]).start()

```

**... or 97 ~~175~~ with delayed thread starting**

```
import threading as t,sys
for x in [t.Timer(int(a),print,[a]) for a in sys.argv[1:]]:x.start()

```

---

Takes input via the command line, ala

```
./sleep-sort\ v0.py 1 7 5 2 21 15 4 3 8

```

---

As with many python golfs, there comes a point where the code is compact enough that aliasing variables to shorten names doesn't even save characters.

This one is funky though because it aliases sys and threading BOTH as t, so sys.argv becomes t.argv. Shorter than from foo import \*, and a net character savings! However I suppose Guido wouldn't be pleased...

~~Note to self - learn c and stop golfing in python.~~ HOLY COW THIS IS SHORTER THAN THE C SOLUTION!
> 7 votes

# Answer
## C# - 137 characters

Here is an answer in C# (updated with degrees of parallelism as commented)

```
void ss(int[]xs){xs.AsParallel().WithDegreeOfParallelism(xs.Length).Select(x=>{Thread.Sleep(x);return x;}).ForAll(Console.WriteLine);}

```
> 7 votes

# Answer
## Java (aka never wins at codegolf) : ~~234~~ ~~211~~ 187 chars

```
public class M{public static void main(String[]s){for(final String a:s)new Thread(){public void run(){try{sleep(Long.parseLong(a));}catch(Exception e){}System.out.println(a);}}.start();}}

```

ungolfed:

```
public class M {
    public static void main(String[] s) {
        for(final String a:s) new Thread(){
            public void run() {
                try {
                    sleep(Long.parseLong(a));
                } catch(Exception e){}
                System.out.println(a);
            }
        }.start();
    }
}

```
> 7 votes

# Answer
# ColdFusion (8+), 109 bytes

```
<cfloop array="#a#" index="v"><cfthread><cfthread action="sleep" duration="#v*1000#"/>#v#</cfthread></cfloop>

```

Ungolfed:

```
<cfloop array="#a#" index="v">
  <cfthread><cfthread action="sleep" duration="#v*1000#"/>#v#</cfthread>
</cfloop>

```

This assumes that `<cfoutput>` is in effect. A few characters could be saved by writing it all on one line.
> 6 votes

# Answer
### Scala - 42 40 characters (special case)

If you have a thread pool at least the size of the number of list elements:

```
a.par.map{i=>Thread.sleep(i);println(i)}

```

### Scala - 72 characters (general)

```
a.map(i=>new Thread{override def run{Thread.sleep(i);println(i)}}.start)

```
> 6 votes

# Answer
## Javascript - 52 characters

```
for(i in a)setTimeout("console.log("+a[i]+")",a[i])

```
> 5 votes

# Answer
## Haskell - 143 characters

```
import Control.Concurrent
import System
d=threadDelay
f x=d(10^6*x)>>print x
g s=mapM(forkIO.f)s>>d(10^6*maximum s+1)
main=getArgs>>=g.map read

```

This probably could be made a shorter by taking input on stdin if that were an option, but it's late and either way, it's still 104 characters for the function itself.
> 5 votes

# Answer
# Befunge-98, 38 31 bytes

I know this is an old challenge, but I just recently discovered both sleepsort and 2D languages, had an idea about how to combine them, and looked for a place to post it, so here we are.

```
&#vt6j@p12<'
v:^ >$.@
>:!#^_1-

```

The main IP reads a number (`&`), then hits the `t` which clones it: one proceeds on the same line and cycles, reading new numbers and generating new childs until it reaches EOF which terminates the sequence. All the child processes get stuck in a closed loop (the `v` and `^` of the third column) until the main IP finishes reading the input and executes the sequence of commands `'<21p`, which puts the character `<` at position (1,2), overwriting the `^` and freeing all the child processes, which start to simultaneously cycle, reducing by 1 their number at each iteration. Since execution speed of different IPs is synchronized in befunge, they will terminate (and print their value) in order, sorting the input list.
> 5 votes

# Answer
A little late to the party:

## Maple - 91 83 characters

In 91:

```
M:=():use Threads in p:=proc(n)Sleep(n);:-M:=M,n;end:Wait(map(i->Create(p(i)),L)[])end:[M];

```

In 83:

```
M:=():use Threads in Wait(seq(Create(proc(n)Sleep(n);:-M:=M,n end(i)),i=L))end:[M];

```

(This needs Maple version 15, and expects the list to be sorted in L)
> 3 votes

# Answer
## C, 70 69 chars

Doesn't wait for child processes to return, otherwise works.

```
main(n) {
    while(~scanf("%d",&n)?fork()||!printf("%d\n",n,sleep(n)):0);
}

```
> 3 votes

# Answer
## Haskell, 90

```
import Control.Concurrent
s::[Int]->IO()
s=mapM_(\x->forkIO$threadDelay(x*9999)>>print x)

```

I hope this meets all the requirements.
> 3 votes

# Answer
# Rust, 125 bytes

Used the depricated `sleep_ms` function so I don't need to write a long duration.

```
|p:Vec<u32>|p.into_iter().for_each(|i|{use std::thread::{spawn,sleep_ms};spawn(move||{sleep_ms(i*1000);println!("{}",i)});});

```

playground link
> 3 votes

# Answer
# JavaScript, 38 bytes

```
a=>a.map(x=>setTimeout(alert,x*1e3,x))

```
> 3 votes

# Answer
## PHP 57 bytes

```
<?for(;$i=fgets(STDIN);)pcntl_fork()?:die($i.usleep($i));

```

pcntl\_fork() is only available under linux.
> 2 votes

# Answer
Bash (38):

```
xargs -P0 -n1 sh -c 'sleep $0;echo $0'

```

Edit: Floating-point from stdin, separated by spaces or newlines.
> 2 votes

# Answer
# , 11 chars / 22 bytes

```
ïć⇝שĤ⇀ôa,a⸩

```

`Try it here (Firefox only).`

`שĤ⇀ôa`, this looks cool.
> 2 votes

# Answer
## PowerShell 7, 40 bytes

Filters are a kind of function:

```
filter f{$args|% -Pa{sleep $_;$_}-Th 99}

PS C:\> f 3 2 1
1
2
3

```

It uses Powershell 7's ForEach-Object -Parallel feature, which defaults to 5 threads, so has `-ThrottleLimit 99` to make it at work for the required 10 numbers.
> 2 votes

# Answer
Just some tweaking from @rmckenzie 's version:

## Python delayed thread start in ~~155~~ ~~152~~ ~~114~~ ~~108~~ 107:

```
import sys, threading as t
for x in [t.Timer(int(a),sys.stdout.write,[a]) for a in sys.argv[1:]]:x.start()

```

## Python without delay in ~~130~~ ~~128~~ ~~96~~ ~~95~~ 93:

```
import sys,threading as t
for a in sys.argv[1:]:t.Timer(int(a),sys.stdout.write,[a]).start()

```

Managed a few more optimisations, using `Timer` instead of `Thread`, which has a more concise call and removed the need to import `time`. Delayed thread start method benefits from list comprehension as it removes the need to initialise the list seperately at the start, although it's two characters longer (`"["+"]"+" "-":"`) than the for loop so it's useless without delayed start, and you have to be careful to use a list rather than a generator, or you're not actually creating the timer threads until you chunk through the generator.

Does anyone else have any optimisations?

---

The trick with `as` helps, but in 2.7.1 you can only import one module into an alias, and after some playing about you can't even `import mod1,mod2 as a,b`, you have to `import mod1 as a, mod2 as b`. It still saves a few characters, but isn't quite the cure-all I thought it was... And in fact it's better to leave sys as sys. Aliasing threading still helps though...
> 1 votes

# Answer
## Clojure, 54

`(defn s[n](doseq[i n](future(Thread/sleep i)(prn i))))`
> 1 votes

# Answer
# C++11, 229 bytes

```
#import<future>
#import<iostream>
using namespace std;int main(int a,char**v){auto G=new future<void>[a];while(--a){G[a]=move(async([=](){this_thread::sleep_for(chrono::seconds(atoi(v[a])));cout<<v[a]<<" "<<flush;}));}delete[]G;}

```

Ungolfed and usage:

```
#import<future>
#import<iostream>
using namespace std;
int main(int a,char**v){
 auto G=new future<void>[a];
 while(--a){
  G[a]=move(async(
   [=](){
    this_thread::sleep_for(chrono::seconds(atoi(v[a])));
    cout<<v[a]<<" "<<flush;
   }
  ));
 }
 delete[]G;
}

```
> 1 votes

# Answer
# Rust - 150 bytes

And this is why you don't code golf in Rust, it's more verbose than Java ;). Depends on external crate `crossbeam`, it would be even worse without it.

```
|x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}

```

Complete test program:

```
fn main() {
    let z =
    |x|{extern crate crossbeam;crossbeam::scope(|s|for&v in x{s.spawn(move||{std::thread::sleep(std::time::Duration::from_secs(v));println!("{}",v)});})}
    ;
    z(&[4, 2, 3, 5, 7, 8, 9, 1, 6, 10])
}

```
> 1 votes

# Answer
# Julia 1.0, 41 bytes

```
!l=@sync l.|>i->@async sleep(i)println(i)

```

Try it online!

`@async` adds the task to the machine's scheduler queue, and `@sync` waits for all `@async`s to finish
> 1 votes

# Answer
# C (clang), 72 bytes

```
main(n){~scanf("%d",&n)?fork()?wait(main()):printf("%d ",n+sleep(n)):0;}

```

I chose clang but it also works on gcc.

1. takes input from stdin
2. fork()
3. if it's the child, then sleep (returns 0 if sleep succeeded, see `sleep(3)`) and print the number... if it's the parent call main recursively (which implicitly returns 0 since C99).
4. when there's no more input we return from `main()` and start waiting for the children, the children also call `wait()` a number of times depending on the recursion depth but they don't have any children so that fails immediately for them.

Try it online!
> 1 votes

# Answer
Kind of boring, port of C#, just to get started with the language again:

**F# - 90 characters**

```
PSeq.withDegreeOfParallelism a.Length a|>PSeq.iter(fun x->Thread.Sleep(x);printfn "%A" x)

```
> 0 votes

# Answer
# JavaScript, 74

```
function(a){for(i=0;i<a.length;i++)setTimeout('alert('+a[i]+')',a[i]*1e3)}

```

or 71/65 characters with nonstandardness:

```
function(a){a.map(function(v){setTimeout('console.log('+v+')',v*1e3)})}

```
> 0 votes

# Answer
## Tcl 8.6, 41 chars

```
lmap c $argv {after $c "puts $c"};vwait f

```

You have to kill it with `^C`
> 0 votes

# Answer
# VB.NET 100 bytes

Because VB.Net requires single line lambdas to contain only one statement, this code has to have the multiple lines:

```
Array.ForEach(i, Async Sub(x)
Await Threading.Tasks.Task.Delay(x*1000)
Console.WriteLine(x)
End Sub)

```

Ungolfed:

```
Option Strict Off

Sub Main(i() as String)
    Array.ForEach(i, Async Sub(x)
                         Await Threading.Tasks.Task.Delay(x * 1000)
                         Console.WriteLine(x)
                     End Sub)
End Sub

```

---

However I'm not sure if you count imports statements in the byte counts because if you don't count them then I could write this:

# VB.NET 71 bytes

```
a.ForEach(i, Async Sub(x)
Await t.Delay(x*1000)
c.WriteLine(x)
End Sub)

```

Ungolfed:

```
Option Strict Off
Imports t = System.Threading.Tasks.Task
Imports c = System.Console
Imports a = System.Array

Sub Main(i() as String)
    a.ForEach(i, Async Sub(x)
                     Await t.Delay(x * 1000)
                     c.WriteLine(x)
                 End Sub)
End Sub

```
> 0 votes

# Answer
# Groovy, 47 bytes

Assumes numbers are given on the command line...

```
args.each{i->Thread.start{sleep(i*22)print i}}

```
> 0 votes

# Answer
**Mathematica, 34 or 36 bytes**

```
RunScheduledTask[Print@#,{#,1}]&/@

```

Just append the list to be sorted to the end of this code and evaluate. If it needs to be a valid function definition then it takes two extra bytes:

```
RunScheduledTask[Print@#,{#,1}]&/@#&

```
> 0 votes

# Answer
# Java 9, 82 bytes

```
i->{i.parallelStream().map(j->{Thread.sleep(j);System.out.println(j);return 0;});}
i->{                                                                             }  //lambda: arguments: List<int> i
    i.parallelStream().map(                                                    );   //iterate over each item in a parallel thread
                           j->{                                               }     //lambda: arguments: int j
                               Thread.sleep(j);                                     //sleep j milliseconds
                                               System.out.println(j);               //print that int
                                                                     return 0;      //just some return value to fullfil the requirements of map()

```
> 0 votes

# Answer
# Java - 106 bytes

```
l->l.forEach(x->new Thread(()->{try{Thread.sleep(x);System.out.println(x);}catch(Exception e){}}).start())

```

Complete test program:

```
import java.util.List;
import java.util.function.Consumer;

public class CG {
    public static void main(String[] args) {
        Consumer<List<Integer>> sleepSort = l->l.forEach(x->new Thread(()->{try{Thread.sleep(x);System.out.println(x);}catch(Exception e){}}).start());
        sleepSort.accept(List.of(3423, 143, 4545, 2545, 764, 5121, 2333, 944, 6555, 1066));
    }
}

```
> 0 votes

# Answer
# Japt, 11 bytes

```
Ëe3 t{OpD
P

```

Try it online!

### Unpacked & How it works

```
UmD{De3 t{OpD
P

UmD{  Map input array with the function...
De3 t{  Run the following function after D * 1000 milliseconds...
OpD       Print D with newline

P     Set "" as the thing to implicitly print

```

JS's `setTimeout` is obviously the winner. Unlike `setInterval` which is low-capped at 10ms, `setTimeout` doesn't have such an arbitrary limit.

If the delay need not be in seconds, the following works (and gives the result much faster):

## 8 bytes

```
Ët{OpD
P

```

Try it online!
> 0 votes

# Answer
# PowerShell 6, 34 bytes

```
$args|%{$(sleep $_;$_)&}|rcjb -wai

```

Try it online!

See Background operator &

---

# PowerShell, 48 bytes

```
$args|%{sajb{sleep $args;$args}-ar $_}|rcjb -wai

```

Try it online!

where:

* `sajb` is the predefined alias for `start-job` and
* `rcjb` is the predefined alias for `receive-job`

The default `ThrottleLimit` is 32.
> 0 votes

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


title: Make a Lost Compass

text:
# Question
Title: Make a Lost Compass
Lost is a 2-Dimensional programming language where the instruction pointer starts at a random location, moving in a random direction. A description of the language can be found at the bottom of the post for completeness' sake and a tutorial for the language can be found in the above link.

The task here is simple to describe: Write a non-empty lost program which when run will output the direction that was selected at the beginning of execution.

The four directions are:

* `N` for north
* `E` for east
* `S` for south
* `W` for west

You may output them with any capitalization you please and with an optional trailing newline.

# Description

Lost operates on a grid where each instruction is a character of the source. Lost's instruction pointer (ip) moves through the grid in one of the four cardinal directions. When it goes off one side of the grid it wraps around to the other as if the program were written on a torus.

Lost's memory is stored in a main stack and a scope. Both are stacks padded with zeros at the bottom. At the end of execution the contents of the main stack are printed and the scope discarded. Lost also stores a single value called the "safety", which begins on.

Programs can only terminate when the safety is off.

## Doors

* `[` Reflects the ip if it is moving east; becomes `]` if the ip is moving horizontally
* `]` Reflects the ip if it is moving west; becomes `[` if the ip is moving horizontally

## Jumps

* `!` Skips the next operation
* `?` Pops off the top of the stack and jumps if not zero

## Stack manipulation

* `:` Duplicates the top of the stack
* `$` Swaps the top two items of the stack
* `(` Pops from the stack and pushes to the scope
* `)` Pops from the scope and pushes to the stack

## Literals

* `0`-`9` pushes n to the top of the stack
* `"` Starts and ends a string literal. During a string literal commands are not run and instead their character values are pushed to the stack.

## Operations

* `+` Adds the top two numbers
* `*` Multiplies the top two numbers
* `-` Multiplies the top by -1

## Control

* `%` Turns the safety off
* `#` Turns the safety on
* `@` Ends execution if the safety is off (starts on)

---

The following operations are present in Lost but cannot be used for this challenge, since doing so instantly makes the challenge impossible.

* `\` Swaps the x and y directions
* `/` Swaps the x and y directions and multiplies them by -1
* `|` Multiplies the horizontal direction by -1
* `>` Tells the ip to move east
* `<` Tells the ip to move west
* `v` Tells the ip to move south
* `^` Tells the ip to move north

# Answer
# ~~1749~~ 1533 bytes

```
%(6.99*+@+6*97(((((%#%%%%%%%#%%#%%%%%
%(((((99*6+@+*976((%%(((((((%((%(((((
%((699*+@+6*97(((((%((((((((((((((((((((
%(((((99*6+@+*976((%2(2(2(2(2(2(2(2(2(2(
%((699*+@+6*97(((((%9(9(9(9(9(9(9(9(9(9(
%(((((99*6+@+*976((%9(9(9(9(9(9(9(9(9(9(
%((699*+@+6*97(((((%*9*9*9*9*9*9*9*9*9*9
%(((((99*6+@+*976((%+9+9+9+9+9+9+9+9+9+9
#%(699*+@+6*97((((%#@*@*@*@*@*@*@*@*@*@*
%(((((99*6+@+*976((%+2+2+2+2+2+2+2+2+2+2
%((699*+@+6*97(((((%6+6+6+6+6+6+6+6+6+6+
(#%(((99*6+@+*976(%#*@*@*@*@*@*@*@*@*@*@
%((699*+@+6*97(((((%8+8+8+8+8+8+8+8+8+8+
(%((((99*6+@+*976((%9*9*9*9*9*9*9*9*9*9*
%((699*+@+6*97(((((%(8(8(8(8(8(8(8(8(8(8
(((%((99*6+@+*976((%(9(9(9(9(9(9(9(9(9(9
(((699*+@+6*97(((((%(6(6(6(6(6(6(6(6(6(6
2(((((99*6+@+*976((%((((((((((((((((
((69.9*+@+6*97(((((%((((((((%((%((
%(((%(99*6+@+*976((%%%%%%%%%#%%#
+6.*97%%#%%#%%%%%%%((((699*+@
*976((((%((%((((((((%(((((99*6+@+
((((((((((((((((((((%((699*+@+6*97(
2(2(2(2(2(2(2(2(2(2(%(((((99*6+@+*976(
9(9(9(9(9(9(9(9(9(9(%((699*+@+6*97(((
9(9(9(9(9(9(9(9(9(9(%(((((99*6+@+*976(
*9*9*9*9*9*9*9*9*9*9%((699*+@+6*97(((
+9+9+9+9+9+9+9+9+9+9%(((((99*6+@+*976(%
@*@*@*@*@*@*@*@*@*@*#%(699*+@+6*97(((%#
+2+2+2+2+2+2+2+2+2+2%(((((99*6+@+*976((%
6+6+6+6+6+6+6+6+6+6+%((699*+@+6*97(((
*@*@*@*@*@*@*@*@*@*@#%((((99*6+@+*976(%#
8+8+8+8+8+8+8+8+8+8+%((699*+@+6*97(((
9*9*9*9*9*9*9*9*9*9*%(((((99*6+@+*976((%
(8(8(8(8(8(8(8(8(8(8%((699*+@+6*97(((
(9(9(9(9(9(9(9(9(9(9%(((((99*6+@+*976
(6(6(6(6(6(6(6(6(6(6%((699*+@+6*97((
6(((((((((((((((((((%(((((99*6+@+*97
7.9(((((%((%((((((((#%(699*+@+6*
+*976%(%#((#%(9.9*6+@

```

Try it online! Verify it!

This works similarly to the one posted in chat, with a shorter execution part and some extra stuff trimmed off the right edge. I've golfed about a hundred bytes off the edges, but perhaps I should look for a shorter inner section before that.

Here is a formatter that takes a few lines and formats them in this square, though some minor edits to the lines/columns with `@`s in them are necessary to get it actually working.
> 11 votes

# Answer
# ~~504~~ 503 bytes

```
+6*9+ 18((%(( 77*54*+@
6*9+-09((%(( 99*54*+@+
*9+ 18((%(( 77*54*+@+6
9+-09((%(( 99*54*+@+6*
+ 18((%(( 77*54*+@+6*9
-09((%(( 99*54*+@+6*9+
18((%(( 77*54*+@+6*9+
9((%(( 99*54*+@+6*9+-0
((%(( 77*54*+@+6*9+ 18
(%(( 99*54*+@+6*9+-09(
%(( 77*54*+@+6*9+ 18((
(( 99*54*+@+6*9+-09((%
( 77*54*+@+6*9+ 18((%(
 99*54*+@+6*9+-09((%((
77*54*+@+6*9+ 18((%((
9*54*+@+6*9+-09((%(( 9
*54*+@+6*9+ 18((%(( 77
54*+@+6*9+-09((%(( 99*
4*+@+6*9+ 18((%(( 77*5
*+@+6*9+-09((%(( 99*54
+@+6*9+ 18((%(( 77*54*
@+6*9+-09((%(( 99*54*+

```

Try it online!

After a `%` is reached, switching off the safety, there are enough `(`s to empty the stack. Next:

```
Going east:  99*54*+@  produces 101 (e)
             77*54*+@  produces  69 (E)
Going south: 97*54*+@  produces  83 (S)
             79*54*+@  produces  83 (S)
Going west:  90-+9*6+@ produces  87 (W)
             81 +9*6+@ produces  87 (W)
Going north: 91-+9*6+@ produces  78 (N)
             80 +9*6+@ produces  78 (N)

```

-1 by removing one `(`, allowing one more line to be one byte shorter.
> 8 votes

---
Tags: code-golf, self-referential, lost
---


title: Is it a heapable sequence?

text:
# Question
Title: Is it a heapable sequence?
A binary max heap is a rooted tree with integer labeled nodes such that:

* No node has more than 2 children.
* The label of every node is greater than all of its children.

We say a sequence of integers is **heapable** if there exists a binary max heap, whose labels are the sequence's elements, such that if \\$p\\$ is the parent of \\$n\\$, then the sequence has \\$p\\$ before \\$n\\$.

Alternatively, a sequence is heapable if there is a way to initialize a binary max heap whose root is its first element, and then insert the remaining elements one at a time in the order they appear in the sequence, while maintaining the binary max heap property.

For example:

* The sequence `[100, 19, 17, 36, 25, 3, 2, 1, 7]` is heapable, with this heap showing why. In the heap, `19` is the parent of `3`, and `19` comes in the sequence before `3` does. This is true for any parent and child.
* The sequence `[100, 1, 2, 3]` is not heapable. If the sequence was heapable, each parent must be both larger, and come before, any of its children. Thus, the only possible parent of `1`, `2`, and `3` is `100`. But this is impossible in a binary heap, as each parent has at most two children.

Given a non-empty array of distinct positive integers, determine if it is heapable.

This is so the goal is to minimize your source code as measured in bytes.

## Test cases

```
[4, 1, 3, 2] -> True
[10, 4, 8, 6, 2] -> True
[100, 19, 17, 36, 25, 3, 2, 1, 7] -> True
[6, 2, 5, 1, 3, 4] -> True

[100, 1, 2, 3] -> False
[10, 2, 6, 4, 8] -> False
[10, 8, 4, 1, 5, 7, 3, 2, 9, 6] -> False

```

Notes:

* The typical array representation of a heap is a heapable sequence, but not all heapable sequences are in this form (as the above examples show).
* Most sources define heapable sequences with a min heap, rather than a max heap. It's not a big difference, but I imagine programmers are more familiar with max heaps than min heaps.
* This is a standard rules apply.

# Answer
> 5 votes
# Haskell, 100 bytes

```
x!(q@(n,y):z)=[(2,x):(n-1,y):z|y>x,n>0]++map(q:)(x!z)
x!_=[]
g(x:y)=[]<foldl((.(!)).(>>=))[[(2,x)]]y

```

Try it online!

## Explanation

We look for a heap using breadth first search. We keep track of the nodes and the number of available children in a list. We discard any nodes that already have two children. They are just not necessary any more since we only care about *if* there is a solution, not what it is.

At each step we attempt to insert a value at every location allowing it if we find a node with available children and a value greater than the value we are inserting.

If we manage to find a way to insert every value then we return `True` otherwise `False`.

# Answer
> 4 votes
# BQN, 35 bytesSBCS

```
{⟨⟩:1;×⊑⍒?0;∨´∧´¨¨¨⊔⟜v¨⥊↕2¨v←1↓}

```

Run online!

**Commented**

```
{
  ⟨⟩:1   ;  # The empty sequence is heapable
  ×⊑⍒?0 ;  # Not heapable if the maximum is not at index 0
  v←1↓     # Now consider the sequence without the first value
  ∨´        # It is heapable if any ...
  ⊔⟜v¨⥊↕2¨v #   ... way of splitting it
  ∧´¨¨¨    #   ... results in two heapable subsequences
}

```

# Answer
> 2 votes
# JavaScript (ES7), 81 bytes

Returns \\$0\\$ or \\$1\\$.

```
f=([v,...a],t=[2**32-3])=>!v|t.some((x,i)=>x/4>v&x%4<2&&f(a,b=[...t,v*4],b[i]++))

```

Try it online!

### How?

We don't really need to keep track of the exact structure of the binary tree. In particular, we don't need to 'remember' the parent of a given node as long as we are sure that it was a valid connection when we added it.

We store the tree as a list of integers where the 2 least significant bits represent the number of child nodes and the higher bits represent the value of the node.

For instance a \\$6\\$ with 1 child node is stored as \\$25\\$:

```
11001
\_/\/
 |  \_ 1 child node
 +---- value = 6

```

We do a recursive search, looking for all valid parents for a given value. For each valid connection, we update the parent and simply add the child at the end of the list.

The list is initialized with a pseudo node whose value is \\$2^{32}-3\\$ so that the root node can be attached to it:

```
11111111111111111111111111111101
\____________________________/\/
              |                \_ 1 child
              +------------------ max. possible value with
                                  this encoding scheme

```

# Answer
> 0 votes
# Python3, 170 bytes:

```
def f(v):
 q=[({v.pop(0):[]},v)]
 while q:
  r,V=q.pop(0)
  if[]==V:return 1
  for i in r:
   if i>V[0] and len(r[i])<2:q+=[({**r,i:r[i]+[V[0]],V[0]:[]},V[1:])]
 return 0

```

Try it online!

---
Tags: code-golf, decision-problem, data-structures
---