title: Is this graph a tree?

text:
# Question
Title: Is this graph a tree?
Given an undirected graph, find out if it is a tree.

A tree is an undirected graph in which there is exactly one path between any two vertices. In other word, the graph is both acyclic and connected.

## Input

You can take input in any reasonable format. Here are some example formats:

* an adjacency matrix, e.g., `[[0,1,1,0],[1,0,1,1],[1,1,0,0],[0,1,0,0]]`;
* an adjacency list, e.g., `{1:[2,3],2:[1,3,4],3:[1,2],4:[2]}`;
* an edge list, e.g., `[(1,2),(1,3),(2,3),(2,4)]`;
* a built-in graph object, e.g., `Graph[{1,2,3,4},{1<->2,1<->3,2<->3,2<->4}]` in Mathematica.

All the above examples represent the following graph, which is not a tree:

```
1---2---4
 \ /
  3

```

Here I use numbers `1,2,3,4` to represent the vertices. You may also use, for example, `0,1,2,3`.

You may assume that:

* The graph is non-empty.
* The graph has no loop (an edge connecting a vertex with itself) or multi-edge (two or more edges that connect the same two vertices).
* Each vertex is connected to at least one other vertex.

## Output

A value representing whether the graph is a tree. You can choose to

* output truthy/falsy using your language's convention (swapping is allowed), or
* use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

This is , so the shortest code in bytes wins.

## Testcases

Here I take inputs as edge lists.

### Truthy

```
[(1, 2)]
[(1, 2), (2, 3), (2, 4)]
[(1, 2), (2, 3), (3, 4), (4, 5)]
[(1, 2), (1, 3), (2, 4), (2, 5)]
[(1, 3), (1, 6), (1, 7), (2, 3), (2, 5), (4, 7)]

```

### Falsy

```
[(1, 2), (3, 4)]
[(1, 2), (1, 3), (2, 3), (2, 4)]
[(1, 2), (1, 3), (2, 3), (4, 5)]
[(1, 3), (1, 5), (2, 3), (3, 4), (4, 5)]
[(1, 2), (3, 4), (3, 5), (4, 5), (4, 7), (6, 7)]

```

# Answer
# Jelly, ~~7~~ ~~6~~ ~~5~~ 4 bytes (thanks @Jonathan Allan!)

```
ṖÆḊ’

```

Try it online!

```
Ṗ      Delete the last row of the input matrix
 ÆḊ    Compute sqrt(det(A A^T)), where A is the result of the previous step
   ’   Decrement

```

Accepts the oriented incidence matrix of the graph. Based on Kirchhoff's Theorem, the fact that a graph has exactly one spanning tree if and only if it's a tree graph, and the fact that the Laplacian matrix of a graph can be easily computed from its oriented incidence matrix as follows: $$L=BB^T$$ where *L* is the Laplacian matrix and *B* is the oriented incidence matrix. Outputs a truthy value if the graph is ***not*** a tree, and a falsy value if it is.

After deleting the last row from the incidence matrix () and multiplying by its transpose, the result will be equal to the Laplacian matrix with the last row and last column deleted: exactly what we need. `ÆḊ` transposes, multiplies, *and* computes the determinant for us: perfect! It also takes the square root of the result, but for reasons I'll explain later, this isn't a problem.

The determinant of the matrix product mentioned previously, the square of the result of all but the last step, is the number of spanning trees of the graph. This is 0 for a non-fully-connected graph, 1 for a tree, and 2 or more for a fully-connected non-tree graph. Now, I mentioned that `ÆḊ` takes the square root of the determinant. Is this a problem? It isn't, since the square root of 0 is 0, the square root of 1 is 1, and the square root of a number greater than 1 will also be a number greater than 1. Therefore, after decrementing (), the result will be falsy (0) if and only if the determinant is 1: that is, if and only if the graph is a tree graph.

If the number of nodes happens to be one greater than the number of edges, deleting the last row will result in a square matrix. In this case, `ÆḊ` will simply compute the determinant, so won't this lead to incorrect outputs? It won't, since for a square matrix *A*: $$\sqrt{\det(A A^T)} = \sqrt{\det(A) \det(A^T)} = \sqrt{\det(A) \det(A)} = |\det(A)|$$ Therefore, the result will still be exactly what we need (since the determinant of the matrix in question is guaranteed to be non-negative).
> 11 votes

# Answer
# Python NumPy, 49 bytes

```
lambda M:M.sum()<2*len(M)*(M**0-M/M.size).I.all()
```

Attempt This Online!

Takes adjacency matrix as input.

### How

We check two things:

1. number of edges is number of vertices - 1
2. graph is connected

To check 2 we use

1. powers M^n of the adjacency matrix describe paths of length n
2. the graph will be connected iff the sum I + M + M^2 + M^3 + ... has no zero elements. (We can always scale M so that this sum converges.)
3. the sum in 2 is a geometric series and can be written as (I-M)^-1

# Python NumPy, 43 bytes (@Command Master)

```
lambda M:M.sum()<3*len(M)*(M**len(M)).all()
```

Attempt This Online!

This requires the main diagonal to be set in the input.
> 10 votes

# Answer
# Wolfram Language (Mathematica), 10 bytes

```
TreeGraphQ

```

Try it online!

So I find a builtin in Mathematica... (my first Mathematica answer btw :D)
> 9 votes

# Answer
# 05AB1E, ~~14~~ 13 bytes

```
ZLœεIk€à{āQ}à

```

Try it online!

-1 thanks to @Kevin Cruijssen

Takes input as an edge list, with vertices indexed 1,2,3,...,n.

## Explanation

Uses the fact that a graph is a tree iff there's a way to order its vertices such that all but one appear exactly once as the maximum value in some edge. Proof:

* The minimum value in each connected component won't appear, so if there's only one value missing there must be a single connected component.
* If there's a cycle there must be more then \\$n-1\\$ edges, so the list of the maximum value in each won't be of length \\$ n-1 \\$.
* If the graph is a tree, its preorder scan would satisfy the condition.

```
Z       push the maximum value in the edge list, the size of the graph
L       push the list [1, 2, ..., n]
œ       push all permutations of it
ε       map each permutations to:
 I       push the input
 k       find the index of each vertex in each edge in the given permutation, 0-based
 €à      find the maximum value in each pair
 {       sort that list
 ā       push the list [1, 2, ..., len(arr)]
 Q       and compare it to the sorted list of indices
}
à        take the maximum value - return 1 if any of the values are 1, else 0

```
> 8 votes

# Answer
# K (ngn/k), 26 bytes

```
{&//{|/'x*\:x}/x&~2-/3-/x}

```

Try it online!

The input is an adjacency matrix with 1s along the diagonal and symmetric with respect to transposition.

The condition tested is: the total number of 1s in the adjacency matrix is \\$3n-2\\$ and its transitive closure consists only of 1s.

`{` `}` function with implicit argument `x`

`3-/` subtract all rows of the matrix from the constant 3. The 3 will be broadcast to match the length of a row, so it's effectively \\$3n\\$. The result is a vector.

`2-/` subtract the items of the vector from the constant 2. The result is a scalar: \\$(\sum\_i\sum\_j A\_{ij})-3n+2\\$.

`~` "not", i.e. "is equal to 0?"

`x&` "and" with the original matrix, i.e. zero it if the first condition is not true

`{|/'x*\:x}/` transitive closure

* `{` `}/` repeat until convergence
* `x*\:x` a 3d array of the matrix's row-by-column products
* `|/'` boolean or-sum of each

`&//` boolean and over the entire matrix
> 6 votes

# Answer
# MATL, 11 bytes

```
ZyGRzQ=GYeh

```

This uses the same approach as loopy walt's Python/Numpy answer.

Input is a square logical matrix, where entries `T` and `F` denote `true` and `false` respectively. This represents the adjacency matrix of the graph.

Output is a truthy/falsy value, specifically a non-empty array of zeros and ones, which is truthy if and only if if it does not contain any zero.

Try it online! Or verify all test cases (footer includes truthiness/falsihood test)

### How it works

```
Zy    % Implicit input: square matrix. Size: gives a two-element row vector
GR    % Push input again. Take the upper triangular part
zQ    % Number of nonzeros. Add 1
=     % Are they equal? Element-wise
G     % Push input again
Ye    % Logical version of matrix exponential. This computes A*e^A, where A
      % is the adjacency matrix, replacing non-zero entries by 1 (and
      % avoiding numerical precision issues). The result indicates for each
      % node which nodes it is connected to
h     % Concatenate horizontally. This reshapes into a row vector (the two
      % concatenated arrays are a row vector and a square matrix). Implicit
      % display

```
> 5 votes

# Answer
# Ruby, 53 bytes

```
->l{*r=1;l.all?{|a,b|(a==l||r!=r-=[l=a])&&r!=r|=[b]}}

```

Try it online!

Assume the list is sorted.
> 3 votes

# Answer
# Charcoal, 26 bytes

```
ＷΦ⁻θυ∨¬υ⁼¹ΣＥκ⊙υ№ξμ⊞υ⊟ι¬⁻θυ

```

Try it online! Link is to verbose version of code. Takes an edge list as input and outputs a Charcoal boolean, i.e. `-` for a tree, nothing if not. Identifies non-trees with multi-edges and non-trees with loops if they are not the last edge on the list. Explanation:

```
ＷΦ⁻θυ∨¬υ⁼¹ΣＥκ⊙υ№ξμ

```

Except on the first iteration, only consider those edges where exactly one vertex has been previously visited. While at least one such edge exists...

```
⊞υ⊟ι

```

... mark one of those edges has having been visited.

```
¬⁻θυ

```

Check that there are no unvisited edges left. An edge may remain unvisited if it is part of a cycle (in which case both of its vertices will have become visited) or if it is disconnected (in which case neither of its vertices were visited). If neither holds then the original graph was a tree.
> 3 votes

# Answer
# Vyxal, 13 bytes

```
LÞefA?LT*?f∑>

```

Try it Online!

Takes input as an adjacency matrix with 1s on the main diagonal. Port of @loopy walt's second answer from @Command Master, upvote that!

```
LÞefA?LT*?f∑>
L             # Get the length of the input
 Þe           # Matrix exponentiate it to that
   f          # Flatten
    A         # Are all non-zero? Call this X
     ?L       # Get the length of the input again
       T      # Triple it (multiply by 3)
        *     # Multiply this by X. Call this Y
         ?f∑  # Get the flattened sum of the input
            > # Is Y greater than this?

```

# Jelly, ~~13~~ 12 bytes

```
æ*LȦ×L×3>ẎS$

```

Try it online!

-1 byte thanks to Jonathan Allan.

Same.

```
æ*LȦ×L×3>ẎS$
æ*           - Matrix exponentiate the input to...
  L          - Its length.
   Ȧ         - After flattening, are they all non-zero?
    ×L       - Multiply this by the length of the input.
      ×3     - Multiply by 3.
        >    - Is this greater than...
         ẎS$ - The flattened sum of the input?

```
> 3 votes

# Answer
# Jelly, 14 bytes

```
ŒPḊFQLƊ_LƊ€ȧ/’

```

A monadic Link that accepts an edge list and yields a zero (falsey) if a tree or a non-zero integer (truthy) if not a tree.

**Try it online!** Or see the test-suite.

### How?

We know that (a) the number of edges must be exactly one less than the number of vertices and (b) there must be no sub-graph (including the whole graph, but excluding the empty graph) which has the same number of vertices and edges. So this finds the difference between vertex count and edge count for every non-empty set of edges, checks that all are non-zero and that the result for the full set of edges is \\$1\\$.

```
ŒPḊFQLƊ_LƊ€ȧ/’ - Link: list of edges
ŒP             - get the powerset of the edges (N.B. full-set is rightmost)
  Ḋ            - dequeue (removes the empty set)
          €    - for each:
         Ɗ     -   last three links as a monad:
      Ɗ        -     last three links as a monad:
   F           -       flatten the current set of edges
    Q          -       deduplicate -> distinct vertices used by this set of edges
     L         -       length -> vertex count
        L      -     length of this set of edges -> edge count
       _       -     subtract -> vertex count - edge count
            /  - reduce by:
           ȧ   -   logical AND -> 1 if a tree, 0,2,3,... otherwise
             ’ - decrement -> zero (falsey) if a tree non-zero (truthy) otherwise

```

---

If one takes an adjacency matrix with all vertices also identified as self-connected \\$12\\$ bytes is possible - see Steffan's answer.

---

If one takes the Laplacian matrix then \\$6\\$ bytes is possible - see Alex's answer.
> 3 votes

# Answer
# Python, <sup>~~108~~ ~~102~~</sup> 95 bytes

```
f=lambda g,s=0,v={0}:(v.add(s),[f(g,c)for c in g[s]-v],len(v)==len(g)==sum(map(len,g))//2+1)[2]
```

Attempt This Online!

Program to convert edge list to adjacency list can be found here
> 2 votes

# Answer
# JavaScript (ES6), 69 bytes

Expects a 0-indexed adjacency list. Returns *false* for a tree, or *true* otherwise.

```
a=>a.some(g=(b,i,m,k=i/i)=>b.map(j=>k-=m^(q=m|1<<i)&&!g(a[j],j,q))|k)

```

Try it online!

### Commented

```
a =>               // a[] = adjacency list
a.some(            // for each entry in a[]:
g = (              //   invoke the recursive function g taking:
  b,               //     b[] = adjacent vertices at the current position
  i,               //     i   = current position
  m,               //     m   = bitmask of visited vertices
  k = i / i        //     k   = counter initialized to 1 if i > 0,
) =>               //           or to NaN if i = 0
  b.map(j =>       //   for each vertex j in b[]:
    k -=           //     decrement k if:
      m ^ (        //       i was not already visited, i.e. m is not equal
        q =        //       to the new bitmask q where
        m | 1 << i //       i is marked as visited
      ) &&         //       and
      !g(          //       the result of this recursive call is 0:
        a[j],      //         list of adjacent vertices at the new position
        j,         //         new position
        q          //         updated bitmask of visited vertices
      )            //       end of recursive call
  ) | k            //   end of map(); return k, which is 0 if one and only
                   //   one path to the root was found, or still NaN if the
                   //   root was already reached, or non-zero'ish otherwise
)                  // end of some()

```
> 2 votes

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

```
c=>c[(g=(i,p)=>c[i].every(j=>j==p||c[t++]&&g(j,i)))(t=1)*t]

```

Try it online!

Input as 0-indexed adjacency list. Output falsy for a tree, truthy otherwise.

```
c=>  // input 0-indexed adjacency list
c[
  (g=              // function `g` returns `false` if any
                   //   circular paths are found
                   // And after function `g`, the global
                   //   variable `t` is set to the number
                   //   of node we visited, or in the other
                   //   word, the number of nodes in the tree
    (i,            // Starting from node `i`
     p)=>          // Do not go back to previous node `p`
                   //   or the "parent" node `p` if we consider
                   //   it as a tree
                   // `p` is initialed to `undefined`, as root
                   //   node do not have a parent
    c[i].every(    // `c[i]` is all nodes connected to `i`
      j=>          // For all nodes `j` that connected to `i`
        j==p||     // if the node is not the parent node
        c[t++]&&   // we visit the node `j`
                   // increase the counter of node visited `t`
                   // for a graph contains `n` nodes, if this is
                   //   the `n+1`th node we visit, we know there
                   //   a circular in the graph. We use `c[t]` to
                   //   detect it and report falsy
        g(j,i)     // we visit the following node `j`
))(
  t=1              // Mark node `1` as visited, so initial `t` to 1
)                  // Visit the graph starting from node `1`
                   // As graph in this question would at least
                   // contains 2 nodes, we can safely use node
                   // `1` as the initial node
*t]                // If there is a loop, `false*t` is `0`
                   //   And `c[0]` is always truthy
                   // If there is not a loop, `true*t` is `t`
                   //   If all nodes are connected, the number of
                   //     nodes we visited is the number of nodes
                   //     in the graph. As nodes are 0-indexed,
                   //     `c[t]` is `undefined`, which is falsy
                   //   If some nodes are not connected to node `1`,
                   //     the number of nodes we visited is less
                   //     than the number of nodes in the graph.
                   //     And `c[t]` would be truthy.

```

---

# JavaScript (Node.js), 66 bytes

```
m=>(g=(i,p,j=-1)=>m.map(r=>r[++j!=p&&i]&&m[t++]&&g(j,i))|t-j)(t=0)

```

Try it online!

Input a 0/1 matrix. Output falsy for a tree, truthy otherwise.

```
m=>(
g=(     // search the matrix
  i,    // start from node `i`
  p,    // with previous node is `p`
  j=-1  // index of inner loop, initial to -1
)=>m.map(r=>( // for each nodes that
  r[++j!=p&& // not the one where we come from
    i]&&     // and is connected to `i`
  m[t++]&& // increase counter for visited nodes `t`
           // if we had visited `length+1` nodes, there is a loop
           //     and we should stop here
  g(j,i) // visit the next node `j`
))|t-j   // return 0 if we visited every nodes once
)(
t=0        // initial count of node visited to `0`
           // as node `0` is not counted into `t`
           // the final `t` is "how many nodes we visited" - 1
)

```
> 2 votes

# Answer
# C (clang), 177 bytes

```
r,q,*o,*z;c(v,p,i){for(q|=1<<v;i--;)z[v]&1<<i?q&1<<i?r|=i^p:c(i,v,9):0;}f(*s){z=calloc(9,4);q=r=0;for(o=s;*o;o+=2)z[*o]|=1<<o[1],z[o[1]]|=1<<*o;for(c(*s,0,9);*++s;)r|=~q&1<<*s;}

```

Try it online!

-7 bytes thanks to ceilingcat.

Function `c` recursively checks for cyclicity in the graph and then we simply see if all the vertices were visited.

**Caveat:**

Only works for vertices numbered 1 to 8
> 1 votes

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


title: Interleave strings

text:
# Question
Title: Interleave strings
Inspiration.* I cannot believe we have not had this challenge before:

**Task**

Given one or more printable ASCII strings, interleave them by taking one character from each string, cyclically until out of characters. If a string runs out of characters before the others, just skip that one from then on.

**Examples**

`SIMPLE` gives `SIMPLE`

`POLLS` and `EPEES` gives `PEOPLELESS`

`LYES` and `APRONS` gives `LAYPERSONS`

`ABCDE` and `a c` and `123 567` gives `Aa1B 2Cc3D E567`

`"\n$?*` and  (empty string) and `,(.)"`  (trailing space) gives `",\(n.$)?"*`  (trailing space)

---

* There are shorter APL solutions.

# Answer
> 23 votes
# Jelly, 1 byte

```
Z

```

Try it online!

The “transpose” built-in will do exactly this to a list of strings.

# Answer
> 8 votes
# Python 2, ~~101~~ ~~89~~ ~~86~~ 69 bytes

~~I'm hoping I can get this into a lambda somehow, shortening it down by making it recursive.~~ It isn't ideal because you would hope transposing is shorter, unfortunately it isn't (from what I have managed to come up with so far).

```
f=lambda s:' '*any(s)and''.join(x[:1]for x in s)+f([x[1:]for x in s])

```

Old solutions:

```
w=input();o=''
while any(w):
 for i in range(len(w)):o+=w[i][:1];w[i]=w[i][1:]
print o
```

`lambda s:''.join(''.join([c,''][c<' ']for c in x)for x in map(None,*[list(y)for y in s]))`

```
w=input();o=''
while any(x>=' 'for x in w):
 for i in range(len(w)):o+=w[i][:1];w[i]=w[i][1:]
print o
```

*thanks to mathmandan for making me feel dumb ;) saved me a bunch of bytes! (on an old solution)*

# Answer
> 8 votes
## Perl 6, 34 32 bytes

```
{[~] flat roundrobin |$_».comb}

```

```
{roundrobin(|$_».comb).flat.join}

```

A lambda that takes an array of strings as argument, and returns a string.

(Try it online)

# Answer
> 7 votes
## CJam, 4 bytes

```
qN/z

```

Try it online!

We can also write an unnamed function for 4 bytes, which expects a list of strings on top of the stack:

```
{zs}

```

Try it online!

# Answer
> 7 votes
# Pyth - 3 bytes

Very simple, will add expansion later, on mobile.

```
s.T

```

Test Suite

```
s                         Join all the strings together
 .T                       Transpose, without chopping off overhang
  (Q implicit)

```

# Answer
> 6 votes
# JavaScript (ES6), ~~52~~ 46 bytes

```
f=([[c,...s],...a])=>s+a?c+f(s+s?[...a,s]:a):c

```

Takes input as an array of strings and outputs as a single string.

### Test snippet

```
f=([[c,...s],...a])=>s+a?c+f(s+s?[...a,s]:a):c

g=a=>console.log("Input:",JSON.stringify(a),"Output:",JSON.stringify(f(a)))

g(["SIMPLE"])
g(["POLLS","EPEES"])
g(["LYES","APRONS"])
g(["ABCDE","a c","123 567"])
g(["\"\\n$?*",",(.)\" "]) // Backslash and quote are escaped, but in/output are correct
```

# Answer
> 6 votes
# Haskell, 33 bytes

```
import Data.List
concat.transpose

```

Try it on Ideone. Usage:

```
Prelude Data.List> concat.transpose$["ABCDE","a c","123 567"]
"Aa1B 2Cc3D E567"

```

---

### Without using a build-in: (~~38~~ 34 bytes)

```
f[]=[]
f x=[h|h:_<-x]++f[t|_:t<-x]

```

Try it on Ideone. 4 bytes off thanks to Zgarb! Usage:

```
Prelude> f["ABCDE","a c","123 567"]
"Aa1B 2Cc3D E567"

```

# Answer
> 5 votes
# PHP, ~~68~~ 67 bytes

```
for(;$f=!$k=$f;$i++)for(;y|$v=$argv[++$k];$f&=""==$c)echo$c=$v[$i];

```

Loops over command line arguments. Run with `-r`.

After the inner loop, `$f` is `1` when all strings are finished, `0` else (bitwise `&` casts `""==$c` to int).
Next iteration of the outer loop: copy `$f` to `$k` (saves one byte from `$k=0`) and toggle `$f`:
When all strings are done, `$f` is now `false` and the loop gets broken.

# Answer
> 5 votes
# C, ~~114~~ 84 bytes

-20 bytes for not calculating the length.

```
i,b;f(char**s){b=1;while(b){i=-1;b=0;while(s[++i]>0)if(*s[i])putchar(*s[i]++),++b;}}

```

Accepts array of char pointers and requires last item to be a null-pointer (see usage).

Ungolfed and usage:

```
i,b;f(char**s){
 b=1;
 while(b){
  i=-1;
  b=0;
  while(s[++i]>0)
   if(*s[i])
    putchar(*s[i]++),++b;
 }
}

int main(){
 char*a[]={
//  "POLLS","EPEES"
//  "LYES","APRONS"
 "ABCDE","a c","123 567"
 ,0};
 f(a);
 puts("");
}

```

# Answer
> 5 votes
# , 13 bytes

```
({~/:)&;#\&.>

```

Try it online!

Based on the inspiration for this question.

Another way to do it takes 27 bytes but operates using transpose. Most of the bytes are to handle the automatically added zeroes from padding.

```
[:u:0<:@-.~[:,@|:(1+3&u:)&>

```

## Explanation

```
({~/:)&;#\&.>  Input: list of boxed strings S
          &.>  For each boxed string x in S
        #\       Get the length of each prefix from shortest to longest
                 This forms the range [1, 2, ..., len(x)]
                 Rebox it
(    )         Operate on S and the prefix lengths
      &;         Raze both
   /:            Grade up the raze of the prefix lengths
 {~              Index into the raze of S using the grades
               Return

```

# Answer
> 4 votes
## Retina, 13 bytes

Byte count assumes ISO 8859-1 encoding.

```
O$#`.
$.%`
¶

```

Try it online!

### Explanation

```
O$#`.
$.%`

```

This is based on the standard transposition technique in Retina. We sort (`O`) all non-linefeed characters (`.`), by (`$#`) the number of characters in front of them on the same line (`$.%``), i.e. their horizontal position.

The second stage then simply removes linefeeds from the input.

# Answer
> 4 votes
# Java, 19+155=174 160

```
String f(java.util.Queue<String> q){String s,r="";while(!q.isEmpty()){s=q.poll();r+=s.isEmpty()?"":s.charAt(0);if(s.length()>1)q.add(s.substring(1));}return r;}

```

Ungolfed:

```
  String f(java.util.Queue<String> q) {
    String s, r = "";
    while (!q.isEmpty()) {
      s = q.poll();
      r += s.isEmpty() ? "" : s.charAt(0);
      if (s.length() > 1) {
        q.add(s.substring(1));
      }
    }
    return r;
  }

```

Output:

> SIMPLE
>
> PEOPLELESS
>
> LAYPERSONS
>
> Aa1B 2Cc3D E567
>
> ",(n.$)?"\*

First modification: merged string declaration to save some bytes. Removed `import`, it was used by the `main()` method (not shown here) that also needed `LinkedList`. It is fewer bytes to referece `Queue` directly.

# Answer
> 4 votes
# Python 2, 58 bytes

```
lambda*m:''.join(map(lambda*r:''.join(filter(None,r)),*m))

```

Try it online!

# Answer
> 3 votes
# Actually, ~~7~~ 6 bytes

Golfing suggestions welcome! Try it online!

**Edit:** -1 byte thanks to Teal pelican.

```
a Z♂ΣΣ

```

**Ungolfing**

```
          Implicit input each string.
a         Invert the stack so that the strings are in the correct order.
<space>   Get the number of items on the stack, len(stack).
Z         Zip all len(stack) strings into one, transposing them.
♂Σ        sum() every transposed list of chars into strings.
Σ         sum() again to join the strings together.

```

# Answer
> 3 votes
# PHP, 77 bytes

## Golfed

```
function($a){for($d=1;$d!=$s;$i++){$d=$s;foreach($a as$v)$s.=$v[$i];}echo$s;}

```

Anonymous function that takes an array of strings.

I'm sure this could be golfed more, but it's early. On each iteration, we grab the i-th letter from each given string and append it to our final string, one at a time. PHP just throws warnings if we access bits of strings that don't exist, so that's fine. We only stop when no changes have been made after looping through all the strings once.

I feel like the usage of `$d` can be golfed more, but it's early. :P

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

```
f=([[c,...s],...a])=>c?c+f([...a,s]):a+a&&f(a)
```

```
<textarea oninput=o.textContent=f(this.value.split`\n`)></textarea><div id=o>
```

# Answer
> 2 votes
# Bash + GNU utilities, 55

```
 eval paste `sed "s/.*/<(fold -1<<<'&')/g"`|tr -d \\n\\t

```

I/O via STDIN (line-separated) and STDOUT.

The `sed` formats each line to a bash process substitution. These are then `eval`ed into `paste` to do the actual interleaving. `tr` then removes unnecessary newlines and tabs.

Ideone.

# Answer
> 2 votes
# PHP, 63 bytes

Note: uses IBM-850 encoding

```
for(;$s^=1;$i++)for(;n|$w=$argv[++$$i];$s&=$x<~■)echo$x=$w[$i];

```

Run like this:

```
php -r 'for(;$s^=1;$i++)for(;n|$w=$argv[++$$i];$s&=$x<~■)echo$x=$w[$i];' "\"\n\$?*" "" ",(.)\" " 2>/dev/null;echo
> ",\(n.$)?"*

```

# Explanation

```
for(                       # Iterate over string index.
  ;
  $s ^= 1;                 # Continue until $s (stop iterating) is 1.
                           # Flip $s so each iteration starts with $s
                           # being 1.
  $i++                     # Increment string index.
)
  for(
    ;
    "n" | $w=$argv[++$$i]; # Iterate over all input strings. OR with "n"
                           # to allow for empty strings.
    $s &= $x<~■            # If last character printed was greater than
                           # \x0 (all printable chars), set $s to 0,
                           # causing the loop to continue.
  )
    echo $x = $w[$i];      # Print char $i of current string.

```

# Answer
> 2 votes
## Python 2, 128 96

I was hoping not to have to use itertools

```
a=lambda a:"".join([i for i in reduce(lambda: b,c:b+c, map(None,*map(lambda m:list(m),a)) if i])

```

Ungolfed

```
 a=lambda a:                              #Start a lambda taking in a
    "".join(                              #Join the result together with empty string
        [i for i in reduce(               #For every item, apply the function and 'keep'
           lambda: b,c:b+c,               #Add lists from...
                map(None,*map(            #None = Identity function, over a map of...
                    lambda m:list(m), a)  #list made for mthe strings m
                   ) if i                 #truthy values only (otherwise the outer map will padd with None.
       ])

```

# Answer
> 2 votes
# Python 3, 75 Bytes

I know the other Python one is shorter, but this is the first time I've used `map` ever in my life so I'm pretty proud of it

```
lambda n:''.join(i[k]for k in range(max(map(len,n)))for i in n if len(i)>k)

```

# Answer
> 2 votes
# Pip, 3 bytes

```
WVg

```

Try it online!

The `WV` (weave) builtin does exactly this. It's commonly used as a binary operator to weave two iterables together, but it can also be used as a unary operator to weave a list of iterables together. Here, `g` is the list of command-line arguments.

# Answer
> 2 votes
# Python 3, 59 bytes

```
f=lambda s:s and s[0][:1]+f(s[1:]+[s[0][1:]][:s[0]>""])or""

```

A recursive function that takes a list of strings and returns a string. Try it online!

### Explanation

We're going to build the interleaved string one character at a time. There are several cases to consider:

* Is the first string in the list nonempty? Take its first character, move the rest of it to the end of the list, and recurse.
* Is the first string in the list empty? Remove it from the list and recurse.
* Is the list of strings empty? Then we're done. Return empty string.

The implementation goes as follows:

```
f = lambda s: s and ... or ""

```

Define `f` to be a function of one argument, `s`, which is a list of strings. If `s` is nonempty, do the `...` part (see below); otherwise, return `""`.

```
s[0][:1] + f(...)

```

Since we now know `s` is nonempty, we can refer to its first element, `s[0]`. We don't know yet whether `s[0]` is empty, though. If it isn't, we want to concatenate its first character to a recursive call; if it is, we can concatenate the empty string to a recursive call. Slicing everything left of index 1 works in both cases.

```
s[1:] + ...

```

The argument to the recursive call is going to be all but the first element of `s`, concatenated to either a 1-element list (the rest of `s[0]` if it was nonempty) or an empty list (if `s[0]` was empty).

```
[s[0][1:]][:s[0] > ""]

```

We put `s[0][1:]` (the part of `s[0]` after the first character, which is the empty string if `s[0]` is empty) into a singleton list and then take a slice of that list. If `s[0]` is empty, `s[0] > ""` is `False`, which is treated as `0` in a slice; thus, we slice from index 0 to index 0--an empty slice. If `s[0]` is not empty, `s[0] > ""` is `True`, which is treated as `1`; thus, we slice from index 0 to index 1--the whole 1-element list.

---

If lists of single-character strings can be used in place of strings, this solution can be **54 bytes**:

```
f=lambda s:s and s[0][:1]+f(s[1:]+(s[0]and[s[0][1:]]))

```

Try it online!

# Answer
> 2 votes
# K (ngn/k), 13 bytes

```
<!/,/'(!#:)'\

```

Try it online!

Port of miles's J and DLosc's BQN. For a language with flatten and grade/sort-by but not zip-longest, I guess this is one of the best possible approaches.

More straightforward port would be `{(,/x)@<,/!'#'x}` because K doesn't have fork or over. But it is possible to use K train by abusing repeat-scan:

```
<!/,/'(!#:)'\
      (   )'\   Given a list of strings, apply this to each list
                until convergence and collect all intermediate values
                (including the input):
       !#:        get the indices of the list
                This always converges after step 1, giving (x;!#x)
   ,/'          Flatten each
<!/             Sort first by second

```

# Answer
> 1 votes
# C, ~~75~~ 71 bytes

Only limitation is the output length. Currently it's 99, but can be easily stretched to 999 (+1 byte).

```
i;main(a,b)char**b;{a--;for(;i<99;i++)*b[i%a+1]&&putchar(*b[i%a+1]++);}

```

Ungolfed:

```
i;
main( a, b )
char **b;
{
    a--;
    for( ; i < 99; i++ )
        *b[i % a + 1] && putchar( *b[i % a + 1]++ );
}

```

# Answer
> 1 votes
# Oracle SQL, 195 bytes

```
    select listagg(b,'') within group(order by l,o) from(select substr(a,level,1) b,level l,o from i start with length(a)>0 connect by prior a=a and level<=length(a) and prior sys_guid() is not null)

```

Takes its input from a table named `i` with columns `a` (containing the string) and `o` (order of the string):

```
    create table i (a varchar2(4000), a integer)

```

Explanation:
We're exploiting `CONNECT BY` to break up the strings into each of the characters making them up. `PRIOR SYS_GUID()` being `NOT NULL` ensures we don't end up stuck in a loop.
We then concatenate the single characters with `LISTAGG` but we shuffle them around with an `ORDER BY` clause, ordering them first by their position in the original string and only then by the string they came from.

Not as short as the other answers but SQL isn't really meant as a string manipulation language :)

# Answer
> 1 votes
# Perl 5, + `-0n` 24 bytes

```
1while s/^./!print$&/gem

```

Try it online!

## Explanation

`-0n` slurps the input into `$_` and repeatedly replaces the first char of each line with the result of negating the `print` of each match (which is the empty string since `print` returns `1` by default)

# Answer
> 1 votes
# , 73 bytes

```
for(i in 1:max(nchar(s<-scan(,""))))for(j in seq(s))cat(substr(s[j],i,i))

```

Try it online!

Explanation: very simple (but verbose), just loop through printing `i`th character of the `j`th string. Fortunately, `substr` returns an empty string if given an out-of-range input.

# Answer
> 1 votes
# Jq 1.5, 49 bytes

```
map(explode)|transpose|map(map(values)[])|implode

```

Explanation

```
                      # example input:          ["LYES","APRONS"]
  map(explode)        # make list of ordinals   [[76,89,69,83],[65,80,82,79,78,83]]
| transpose           # zip lists               [[76,65],[89,80],[69,82],[83,79],[null,78],[null,83]]
| map(map(values)[])  # rm nulls and flatten    [76,65,89,80,69,82,83,79,78,83]
| implode             # convert back to string  "LAYPERSONS"

```

Sample Run

```
$ paste input <(jq -Mrc 'map(explode)|transpose|map(map(values)[])|implode' input)
["SIMPLE"]                  SIMPLE
["POLLS","EPEES"]           PEOPLELESS
["LYES","APRONS"]           LAYPERSONS
["ABCDE", "a c", "123 567"] Aa1B 2Cc3D E567
["\"\\n$?*", "", ",(.)\" "] ",\(n.$)?"*

$ echo -n 'map(explode)|transpose|map(map(values)[])|implode' | wc -c
  49

```

**Try it online**

# Answer
> 1 votes
# Factor, 22 bytes

```
[ round-robin ""like ]

```

Try it online!

# Answer
> 1 votes
# Vyxal `s`, 1 byte

Try it Online!

# Answer
> 1 votes
# BQN, ~~23~~ 10 bytes

*Massive savings by porting miles's J solution*

```
↕∘≠¨⍋⊸⊏○∾⊢

```

Anonymous tacit function that takes a list of strings and returns a string. Try it at BQN online!

### Explanation

```
↕∘≠¨⍋⊸⊏○∾⊢
   ¨         For each string in the argument list:
  ≠            Take its length
↕∘             and make a range from 0 to that number (exclusive)
             With that list of lists of indices as the left argument
          ⊢  and the original list of lists of strings as the right argument:
        ○∾     Flatten both lists
      ⊸⊏       Index into the flattened string using
    ⍋          the grade-up of the flattened list of indices

```

Grade up, for those unfamiliar with APL-related languages, is an operation that takes a list and returns a permutation of its indices, such that if the items in the list were reordered according to the order of the indices, the list would become sorted ascending. For example:

```
Indices:  0 1 2 3 4 5
List:     3 1 4 1 5 9

Grade up: 1 3 0 2 4 5
Sorted:   1 1 3 4 5 9

```

This operation is useful for sorting one list according to the values of another list, as seen in the above solution.

# Answer
> 0 votes
## Python, 112 bytes

```
i=len(x)if len(x)>len(y) else len(y) h=0 a="" while h<i: if h<len(x) a+=x[h] if h<len(y): a += y[h] h+=1 print a

```

# Answer
> 0 votes
# Perl 5, 53 bytes

```
$i=0,map{push@{$a[$i++]},$_}/./g for<>;print@$_ for@a

```

Try it online!

**Method**

Creates a two dimensional array where the number of rows is equal to the length of the longest string and the maximum number of columns is equal to the number of strings. Then output each row of the array without spacing.

# Answer
> 0 votes
# TXR Lisp, 20 bytes

```
(opip weave cat-str)

```

Run:

```
1> (opip weave cat-str)
#<intrinsic fun: 0 param + variadic>
2> [*1 "LYES" "APRONS"]
"LAYPERSONS"
3> [*1 "ABCDE" "a c" "" "123 567"]
"Aa1B 2Cc3D E567"
4> [*1 "\"\\n$?*" "" ",(.) "]
"\",\\(n.$)? *"

```

The `weave` function is lazy, so it returns a list, which is why we have to force the result to a string. Being lazy, it can weave infinite sequences. For instance, we can weave the even and odd natural numbers, which are themselves infinite lazy lists:

```
5> (take 20 (weave (range 2 : 2) (range 1 : 2)))
(2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19)

```

# Answer
> 0 votes
# K (oK), ~~35~~ 29 bytes

**Solution:**

```
{`c$r@&~^r:,/+(`i$x)[;!#,/x]}

```

Try it online!

**Example:**

```
> {`c$r@&~^r:,/+(`i$x)[;!#,/x]}("ABCDE";"a c";"123 567")
"Aa1B 2Cc3D E567"
> {`c$r@&~^r:,/+(`i$x)[;!#,/x]}("\n$?*";"";",(.)\" ")
"\n,$(?.*)\" "
> {`c$r@&~^r:,/+(`i$x)[;!#,/x]}("POLLS";"EPEES")
"PEOPLELESS"

```

**Explanation:**

Use 2nd-level indexing to pull out indices from 0 to max (length of flattened list) across all input lists. Any indexing beyond the bound of the sub-list will return a null. Flip (rotates 90), flatten, and then pull out the non-null results.

**Notes:**

* I cast to integer (`i$`) so that we get useful nulls, as space () is considered null for a char list which means you cant tell nulls from valid spaces.
* Also I couldnt get the TIO to work with input (worked fine in the oK repl) so the TIO link includes the "ABCDE"... example.

# Answer
> 0 votes
## Python3 -66

Python3 version of this one:

```
lambda*m:''.join(map(lambda*r:''.join([_f for _f in r if _f]),*m))

```

A super golfed version:

```
exec(bytes('慬扭慤洪✺⸧潪湩洨灡氨浡摢⩡㩲✧樮楯⡮彛潦⁲晟椠⁲晩张嵦Ⱙ洪⤩','u16')[2:])

```

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 86 bytes

```
a=>a.SelectMany(b=>b.Select((c,i)=>(i,c))).OrderBy(b=>b.i).Aggregate("",(s,x)=>s+x.c);

```

Try it online!

# Answer
> 0 votes
# Knight, 103 bytes

```
;=m=iF;W=xP;=mI>mLx mLxE++"=x"=i+1i" x"W+=m-mT1;=j~1W>i=j+1j;O+G E+"x"+1jF1'\'E++++"=x"+1j"Sx"+1j"F1''"

```

Try it online!

# Answer
> 0 votes
# Python, 68 bytes

```
lambda S:filter(None,chain(*zip_longest(*S)))
from itertools import*
```

Attempt This Online!

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


title: Crack the Caesar cipher

text:
# Question
Title: Crack the Caesar cipher
The Caesar cipher is a simple and famous cipher, where the letters of the alphabet are rotated by some secret amount. For example, if our secret rotation is `3`, we would replace `a` with `d`, `b` with `e`, `w` with `z`, `x` with `a` and so on.

Here is an example (rotation amount: 10):

```
Robo sc kx ohkwzvo

```

This cipher is very weak, because short common English words like "I", "a", "is", "an", "if", etc. are easy to detect. Your task is to crack a Caesar cipher, that is, recover the rotation amount from the ciphertext. As additional input, you are given a list (or set) of words, which the plaintext can contain. It is guaranteed that there is only one answer.

# Examples

```
"Ifmmp Xpsme!", ["world", "banana", "hello"]
-> 1

"Nc cd, Kadcn?", ["cogito", "et", "ergo", "tu", "sum", "brute"]
-> 9

"boring", ["boring"]
-> 0

"bccb foo", ["abba", "gpp", "cddc"]
-> 25

" !\"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz{|}~", ["zabcdefghijklmnopqrstuvwxy"]
-> 1

"bcsbdbebcsb", ["abracadabra", "za", "aq"]
-> 1

```

# IO rules

The ciphertext can contain any printable ascii characters. The dictionary (list of words) contains strings made of lowercase letters (a-z). Words are separated by non-letters. Only letters are rotated (punctuation is ignored). You will output an integer in the range `[0,25]`

# Answer
> 6 votes
# Ruby, 66 bytes

Curried function that takes the dictionary first and the ciphertext second.

```
->w{f=->s{s=~/^([^a-z]|#{w*?|})*$/i?0:1+f[s.tr'a-zA-Z','ZA-Y'*2]}}
```

Attempt This Online!

From the dictionary a regex can be generated that only matches decoded text:

```
irb> w
=> ["world", "banana", "hello"]
irb> /^([^a-z]|#{w*?|})*$/i
=> /^([^a-z]|world|banana|hello)*$/i

```

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

*Saved 1 byte thanks to @l4m2*

Expects `(string)(dictionary)`, where the dictionary is a set.

```
s=>g=(d,k=25)=>s.match(/[a-z]+/gi).some(s=>!d.has(Buffer(s).map(c=>(c%32+k)%26+97)+''))&&1+g(d,k-1)

```

Try it online!

# Answer
> 2 votes
# Vyxal 2.4.1, 19 bytes

```
λ?⇩⌈Ǎka:nǓ$vĿ?vcA;ṅ

```

Try it Online!

Basically, try a cipher of each rotation and output the rotation number where all the words are in the dictionary.

2 can play at the legacy version saving bytes game.

## Explained

```
λ?⇩⌈Ǎka:nǓ$vĿ?vcA;ṅ
λ                ;ṅ   # Find the first integer n, such that
 ?⇩                   #   the lowercase input
   ⌈                   #   split on spaces
    Ǎ                 #    and with all non-alphabet letters removed
             ?vcA     #    contains all words from the input after
           vĿ         #    being transliterated according to the mapping:
     ka:nǓ$           #      lowercase alphabet → lowercase alphabet rotated left n times

```

# Answer
> 2 votes
# 05AB1E (legacy), ~~19~~ 18 bytes

```
[DIlÐáмS¡åP#ADÀ‡}N

```

First input is the list of words, second the sentence.

Try it online or verify all test cases.

Uses the legacy version of 05AB1E because of three reasons, each saving a single byte:

1. works on a list of strings, whereas the new version requires a map around it - `ADÀ‡}` would have been `εADÀ‡]` in that case;
2. `N` outputs the last index outside of a loop, whereas this is just `0` in the new version and we would have to use the counter variable - `N` would have been `¾`, and `¼` would have to be added after the `#`;
3. `¡` in the new version would keep empty strings as items, and we would have to remove them - so an additional `á` would have to be added after the `¡` to only keep the words.

**Explanation:**

```
[         # Loop indefinitely:
 D        #  Duplicate the current list
          #  (which will be the first implicit input-list in the first iteration)
  I       #  Push the second input-sentence
   l      #  Convert it to lowercase
    Ð     #  Triplicate it
     á    #  Only leave the letters of the top copy
      м   #  Remove all those letters from the second copy
       S  #  Convert the non-letters to a list of characters
        ¡ #  Split the lowercase sentence on these non-letters
  å       #  Check for each word if it's in the list
   P      #  Check if this is truthy for all of them
    #     #  If it is: stop the infinite loop
  ADÀ‡    #  Caesar Cipher the words in the list once:
  A       #   Push the lowercase alphabet: "abcdefghijklmnopqrstuvwxyz"
   DÀ     #   Duplicate, and rotated once: "bcdefghijklmnopqrstuvwxyza"
     ‡    #   Transliterate the words in the list
}N        # After the loop: push the last 0-based index
          # (which is output implicitly as result)

```

# Answer
> 2 votes
# Retina 0.8.2, 83 bytes

```
T`L`l
[^a-z¶]+
@
^
¶
{ms`\A(#*)¶@?((\w+\b)(?=.*¶\3$)@?)+$.*
$.1
^\B
#
T`l`zl`^.*¶.*

```

Try it online! Takes input as a line of ciphertext followed by each dictionary entry on a separate line. Explanation:

```
T`L`l

```

Lowercase everything.

```
[^a-z¶]+
@

```

Change non-letters to a marker to simplify matching.

```
^
¶

```

Prepend a blank line to hold the result.

```
{`

```

Repeat until the result is found.

```
ms`\A(#*)¶@?((\w+\b)(?=.*¶\3$)@?)+$.*
$.1

```

If all the words in the ciphertext are in the dictionary then replace the whole buffer with the result.

```
^\B
#

```

If the result has not been found then increment the rotation amount.

```
T`l`zl`^.*¶.*

```

If the ciphertext is still present then rotate it.

# Answer
> 2 votes
# , ~~99~~ 103 bytes

*Edit: Thanks to pajonk for bug-spotting, which unfortunately cost +4 bytes (also thanks to pajonk)*

```
f=function(x,d)`if`(all(x%in%d),0,1+f(gsub("[^a-z]","",chartr("a-zA-Z","za-za-y",scan(t=x,,x))),d))%%26

```

Try it online!

# Answer
> 1 votes
# JavaScript (Node.js), 132 bytes

```
y=>f=x=>eval(`/(?<![a-z])(?!${y}(?![a-z]))[a-z]/i`).test(x)&&f(x.replace(/[a-z]/ig,t=>(t=parseInt(t,36)-1,t-9?t:35).toString(36)))+1

```

Try it online!

As always, long part adding 1 to letter

# Answer
> 0 votes
# Python, 120 bytes

```
f=lambda s,d,t=-1:~-any([chr((ord(c)%32+t)%26+97)for c in w]in d for w in re.findall(r'\w+',s))and-~f(s,d,~-t)
import re
```

Attempt This Online!

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


title: Compare two poker hands

text:
# Question
Title: Compare two poker hands
## **Challenge:**

Given two five-card hands, determine which one wins by the standard ranking of poker hands.

## **Input:**

Ten cards separated by spaces from stdin or as command line arguments, whichever you prefer. The first five cards are Player 1's hand while the last five are Player 2's hand. Each card will be a two letter string of the form RS where R is rank and S is suit. The ranks range from 2-9, T for ten, and J, Q, K, and A for Jack, Queen, King, and Ace respectively. The suits are H, D, C, S for Hearts, Diamonds, Clubs, and Spades respectively. You must output the number of the player that wins: '1' or '2'.

## **Examples of Cards:**

```
AS - the Ace of Spades
QD - the Queen of Diamonds
2C - the Two of Clubs
TH - the Ten of Hearts

```

## **Input to Output Examples:**

```
5H 5C 6S 7S KD 2C 3S 8S 8D TD -> 2

```

Explanation: Player 1 has a Pair of Fives while Player 2 has a Pair of Eights.

```
5D 8C 9S JS AC 2C 5C 7D 8S QH -> 1

```

Explanation: Neither Player has anything special, but Player 1's high card is an Ace while Player 2's high card is a Queen.

```
2D 9C AS AH AC 3D 6D 7D TD QD -> 2

```

Explanation: Player 1 has Three Aces, Player 2 has a Flush of Diamonds.

```
4D 6S 9H QH QC 3D 6D 7H QD QS -> 1

```

Explanation: Both players have a Pair of Queens, but Player 1's second highest card is a Nine whereas Player 2's is a Seven.

## **Rules and Clarifications:**

* Refer to the standard ranking of poker hands for the details of comparing hands.
* You may assume that there are no repeated cards in each pair of hands.
* You may assume that there is a definite winner in each case.
* Suit does not factor into the ranking of a hand. For example, two royal flushes of different suits are equal (therefore any input where both players have a royal flush is invalid by the preceding rule).
* As this is code golf, the shortest answer wins.

## **Notes:**

# Answer
> 3 votes
## Haskell - ~~352~~ 339 characters

```
import Data.List
v h=10*(sum$map(\l->l*l)g)+b g:k where
  (g,k)=unzip$reverse$sort$map(\r->(length r,head r))$group$sort$map(maybe 0 id.(`elemIndex`"23456789TJQKA").head)h
  b(1:_)=f(map(!!1)h)+t k;b _=0
f(y:z)|all(==y)z=75;f _=0
t[y,_,_,_,z]|y-z==4=70;t[12,3,2,1,0]=65;t _=0
w(a,b)|v a>v b="1\n";w _="2\n"
main=interact$w.splitAt 5.words

```

Runs:

```
& echo "5H 5C 6S 7S KD 2C 3S 8S 8D TD" | runhaskell 25056-Poker.hs
2

& echo "5D 8C 9S JS AC 2C 5C 7D 8S QH" | runhaskell 25056-Poker.hs
1

& echo "2D 9C AS AH AC 3D 6D 7D TD QD" | runhaskell 25056-Poker.hs
2

& echo "4D 6S 9H QH QC 3D 6D 7H QD QS" | runhaskell 25056-Poker.hs
1

```

Ungolf'd and commented, so you can see the techinque:

```
import Data.List

value :: [String] -> [Int]
value hand = 10 * (sum $ map (\l->l*l) groups) + bonus groups : kicker
    -- ^ Value of a hand is 10 times the sum of the squares of the group lengths
    -- plus the straight & flush bonus, followed by the kicker (to break ties)
    -- This 10 * sum-of-squares + bonus works out to put the hands in category
    -- order, and then they only need to be ordered by card ranks.
  where
    -- | The cards are sorted into groups by matching rank, then the groups
    -- sorted by length and rank: For example: "7C 7D 7H QS 2S" will becomes
    -- [(3,7),(1,Q),(1,2)]. This is like a run-length encoding. Finally, the
    -- groups lengths, and the kicker ranks are taken apart into two lists.
    -- N.B: kicker here includes the ranks of the groups, unlike the poker term.

    (groups,kicker) = unzip             -- split apart
        $ reverse $ sort                -- reverse sort by (length,rank)
        $ map (\r->(length r,head r))   -- turn groups into (length,rank) pairs
        $ group $ sort                  -- group sorted ranks
        $ map (maybe 0 id . (`elemIndex`"23456789TJQKA") . head) hand
            -- take first letter of each card in the hand, and map to [0..12]

    -- | Give a bonus for flush and straight to hands with five cards,
    -- or equivalently hands where the largest group length is just 1
    bonus (1:_ ) = flush (map (!!1) hand)   -- flush takes the suits of the hand
                   + straight kicker        -- straight takes the ranks
    bonus _      = 0

    -- | A flush is if all suits match the first suit
    flush (y:z) | all (==y) z = 75
                | otherwise   =  0

    -- | There are two kinds of straight.
    -- N.B: If there are five groups, then there are no duplicate ranks
    straight [y,_,_,_,z] | y-z == 4 = 70    -- normal, high to low
    straight [12,3,2,1,0]           = 65    -- ace is low, but it sorts high
    straight _                      =  0

wins :: ([String], [String]) -> String
wins (a,b) | value a > value b = "1\n"
           | otherwise         = "2\n"

main = interact $ wins . splitAt 5 . words

```

# Answer
> 2 votes
# Python - ~~774~~ ~~722~~ ~~707~~ ~~698~~ 685 chars

```
import sys
t,q,e,u='--23456789TJQKA','SDCH',enumerate,len
_=lambda c,i=0:chr(97+c[i])
def j(s):
 v,g,l=[0]*15,[0]*4,''
 for c in s:
  r,s=c[0],c[1];v[t.find(r)]+=1;g[q.find(s)]+=1
 c,h,k,m,f=0,0,[0,0,[],[],[]],0,0
 for x,i in e(v):
  for b in[2,3,4]:
   if i==b:k[b]+=[x]
 v[1]=v[14]
 for x,i in e(v):
  if i:
   c+=1
   if c==5:m,h=1,x
   if i==1:l+=_([x])
  else:c=0
 f,l,d=max(g)//5*2,l[::-1],'';z=f+m
 if z==3:d='z'+l
 if k[4]:d='y'+_(k[4])+l
 if k[2] and k[3]:d='x'+_(k[3])+_(k[2])
 if z==2:d='w'+l
 if z==1:d='v'+_([h])
 if k[3]:d='u'+_(k[3])+l
 if u(k[2])>1:d='t'+_(k[2],1)+_(k[2])+l
 if u(k[2])==1>u(k[3]):d='s'+_(k[2])+l
 return d or l
p=sys.argv
print(1+(j(p[1:6])<j(p[6:])))

```

I chose to generate a string for each hand that represents it, starting with a character for the type of hand, followed by characters describing the particular variation of the type (for example, which card did you just have 4 of?), followed by the values of the remaining cards in case of a tie (if both players have the same double pair, the 5th card will have to decide who wins). I've tested it quite extensively, but I don't actually play poker, so I hope I got it right. Also, I know it's not fully golfed yet, I can probably shave off a few dozen chars later on.

# Answer
> 2 votes
# JavaScript - ~~526~~ 508

```
function a(b){b=b.split(" ");var c=b.splice(5,5),d=[],e=[],r=[8,9,5,6,1,2,3,10,4,7],A=14,K=13,Q=12,J=11,S={"S":1,"C":2,"H":4,"D":8};for(i=0;i<5;i++){d.push(b[i].split('')[1]);b[i]=b[i].split('')[0];e.push(c[i].split('')[1]);c[i]=c[i].split('')[0]}function p(w,m){var v,i,o,s=1<<w[0]|1<<w[1]|1<<w[2]|1<<w[3]|1<<w[4];for(i=-1,v=o=0;i<5;i++,o=Math.pow(2,w[i]*4)){v+=o*((v/o&15)+1)}v=v%15-((s/(s&-s)==31)||(s==0x403c)?3:1);v-=(m[0]==(m[1]|m[2]|m[3]|m[4]))*((s==0x7c00)?-5:1);return r[v]}alert(p(b,d)>p(c,e)?1:2)}

```

usage:

```
a("5H 5C 6S 7S KD 2C 3S 8S 8D TD");

```

ungolfed:

```
function a(b) {
b = b.split(" ");
var c=b.splice(5,5),
        d=[],
        e=[],
        r=[8,9,5,6,1,2,3,10,4,7],
        A=14,
        K=13,
        Q=12,
        J=11,
        S={"S":1,"C":2,"H":4,"D":8};

    for (i=0;i<5;i++) {
        d.push(b[i].split('')[1]);
        b[i] = b[i].split('')[0];
        e.push(c[i].split('')[1]);
        c[i] = c[i].split('')[0];
    }

function p(w,m){
  var v, i, o, s = 1<<w[0]|1<<w[1]|1<<w[2]|1<<w[3]|1<<w[4];
  for (i=-1, v=o=0; i<5; i++, o=Math.pow(2,w[i]*4)) {v += o*((v/o&15)+1);}
  v = v % 15 - ((s/(s&-s) == 31) || (s == 0x403c) ? 3 : 1);
  v -= (m[0] == (m[1]|m[2]|m[3]|m[4])) * ((s == 0x7c00) ? -5 : 1);
  return r[v];
}

alert(p(b,d)>p(c, e)?1:2);
}

```

source

# Answer
> 2 votes
**Python 3, 454 characters**

```
def z(v,u):
 v.sort();o,d,w=0,{2:0,3:0},[0]+v[:-1]
 if v[4]==13 and T(w):v=w
 t,f=T(v),len(set(u))==1
 for p,c in set((p,v.count(p)) for p in v):
  if c==4:o+=2**77
  d[c]=d.get(c,0)+1;o+=2**(c*14+p)
 if f+t:o+=2**(71+f*4+t*3)
 elif d[3]:o+=2**(73+3*d[2])
 o+=2**(70+d[2]);return o
i,c,T=input().split(),'-23456789TJQKA',lambda v:all(v[i]==v[0]+i for i in range(5))
v,u=[c.find(x[0]) for x in i],[x[1] for x in i]
print(1+(z(v[:5],u[:5])<z(v[5:],u[5:])))

```

Function z evaluates a hand to a single integer, which is effectively serving as an ordinal using Python's arbitrary precision integers. Its parameters, v and u, are lists of the values (2-14) and suits (single-char strings). The first two lines of z sort the cards, initialize relevant structures, and check if we have a low-ace straight. We then check for a straight or flush on the next line. The internal loop iterates the counts of different cards, solves the 4-of-a-kind case, tallies, and adds the appropriate ordinal. The last 3 lines of z solve the ordinals of all the other hand ranks -- flushes, straights, and straight-flushes, followed by 3-of-a-kind and full houses, followed by two pair, pair, and high card.

In the main area, we parse the input, declare lambda v (which checks for straights), and the last line evaluate the hands and prints the result.

# Answer
> 1 votes
# perl, 801 733 chars

I believe this is a pretty straight-forward implementation. Basically, for each hand, we sort the suits and the faces separately. Then we make another copy of the faces with aces counting low so we can check for straights with low aces. Then we determine if we have a flush or straight, and what the high card is. Then we just check for matches in order of score (first we check for straight flushes, then four of a kinds, etc.). The actual score is just the concatenation of the type of hand followed by the face values of the cards in the order they matter (that's \_s() in the ungolfed version, u() in the golfed version). Here it is:

```
@l{2..9,qw(T J Q K A)}=2..14;sub u{join"",map{$_>9?$_:"0$_"}shift,ref$_[0]?$$_[0]:map{$h[$_]}@_}sub e{$p[$_[0]-1]-1==$p[$_[0]]}sub f{@p=@_;e(1)&&e(2)&&e(3)&&e 4}sub h{$h[$_[0]]==$h[$_[1]]}sub i{h(@_[0,1])&&h @_[2,3]}sub t{@s=sort map{substr($_,1)}@_;$f=$s[0]eq$s[4];@l=@h=sort{$b<=>$a}map{$l{substr($_,0,1)}}@_;@l=(@l[1..4],1)while$l[0]==14;$s=0;if(f@l){$s=1;$h=$l[0]}else{$h=$h[0];$s=1 if f@h}$f&&$s?u 9,\$h:h(4,1)?u 7,4,0:h(3,0)?u 7,3,4:i(4,3,2,0)?u 6,0,4:i(4,2,1,0)?u 6,4,0:$f?u 5,0:$s?u 4,\$h:h(4,2)?u 3,4,0,1:h(3,1)?u 3,3,0,4:h(2,0)?u 3,2..4:i(4,3,2,1)?u 2,2,4,0:i(4,3,1,0)?u 2,1,4,2:i(3,2,1,0)?u 2,1,3,4:h(4,3)?u 1,4,0,1,2:h(3,2)?u 1,3,0,1,4:h(2,1)?u 1,2,0,3,4:h(1,0)?u 1,1..4:u 0,0..4}print t(@ARGV[0..4])gt t(@ARGV[5..9])?1:2

```

And here's the less-golfed equivalent:

```
use strict;
use warnings;

# ace high or low in straights, otherwise high
# T = ten, J = jack, Q = queen, K = king, A = ace

# 0 high card
# 1 one pair
# 2 two pair
# 3 3 of a kind
# 4 straight
# 5 flush
# 6 full house
# 7 four of a kind
# 9 straight flush (royal flush a subclass of straight flush)

my %l;@l{2..9,qw(T J Q K A)}=2..14;
sub score {
  my @suits = sort map { substr($_,1) } @_;
  my @faces_h = sort { $b <=> $a } map { $l{substr($_,0,1)} } @_;
  my @faces_l = @faces_h;
  @faces_l = (@faces_l[1..4], 1) while $faces_l[0] eq 14;
  my $is_flush = $suits[0] eq $suits[4];
  my ($is_straight, $high_card);
  if($faces_l[0]-1==$faces_l[1] &&
     $faces_l[1]-1==$faces_l[2] &&
     $faces_l[2]-1==$faces_l[3] &&
     $faces_l[3]-1==$faces_l[4]) {
    $is_straight=1;
    $high_card = $faces_l[0];
  } else {
    $high_card = $faces_h[0];
    if($faces_h[0]-1==$faces_h[1] &&
       $faces_h[1]-1==$faces_h[2] &&
       $faces_h[2]-1==$faces_h[3] &&
       $faces_h[3]-1==$faces_h[4]) {
      $is_straight=1;
    }
  }
  return _s(9, \$high_card) if $is_flush && $is_straight;
  return _s(7, 4,0) if $faces_h[4] == $faces_h[1];
  return _s(7, 3,4) if $faces_h[3] == $faces_h[0];
  return _s(6, 0,4) if $faces_h[4] == $faces_h[3] && $faces_h[2] == $faces_h[0];
  return _s(6, 4,0) if $faces_h[4] == $faces_h[2] && $faces_h[1] == $faces_h[0];
  return _s(5, 0) if $is_flush;
  return _s(4, \$high_card) if $is_straight;
  return _s(3, 4,0,1) if $faces_h[4] == $faces_h[2];
  return _s(3, 3,0,4) if $faces_h[3] == $faces_h[1];
  return _s(3, 2,3,4) if $faces_h[2] == $faces_h[0];
  return _s(2, 2,4,0) if $faces_h[4] == $faces_h[3] && $faces_h[2] == $faces_h[1];
  return _s(2, 1,4,2) if $faces_h[4] == $faces_h[3] && $faces_h[1] == $faces_h[0];
  return _s(2, 1,3,4) if $faces_h[3] == $faces_h[2] && $faces_h[1] == $faces_h[0];
  return _s(1, 4,0,1,2) if $faces_h[4] == $faces_h[3];
  return _s(1, 3,0,1,4) if $faces_h[3] == $faces_h[2];
  return _s(1, 2,0,3,4) if $faces_h[2] == $faces_h[1];
  return _s(1, 1,2,3,4) if $faces_h[1] == $faces_h[0];
  return _s(0, 0..4);
}

sub _s {
  join "", map { $_ > 9 ? $_ : "0$_" } shift,
    ref $_[0] ? $$_[0] : map { $faces_h[$_] } @_
  # my @a=@_;
  #  if(ref $a[1]) {
  #    $a[1]=${$a[1]};
  #  } else {
  #    $a[$_]=$faces_h[$a[$_]] for 1..$#a;
  #  }
  #  join "", map { $_ < 10 ? "0$_" : $_ } @a;
}

my @p1 = @ARGV[0..4];
my @p2 = @ARGV[5..9];

my $s1 = score(@p1);
my $s2 = score(@p2);
print $s1 gt $s2 ? 1 : 2;

```

---
Tags: code-golf, game
---


title: Optimal strategy to defeat the wizard

text:
# Question
Title: Optimal strategy to defeat the wizard
In this game, you can look inside one box at a time chosen by you. When you do that, you can see how many coins there are in that box.

The wizard has one last twist for you. At any point, you can choose to give up on this set of boxes and get him to start the whole process again (with a new random \\$x\\$). Of course, if you have looked in all the 9 boxes and you still have not found 10 coins you have no choice but to give up and start again. But you might want to give up earlier too. Sadly you never get any money back so your costs just carry on building.

Your goal is to devise a strategy that will get you the wish at the minimum expected cost. You should report your mean cost.

# Testing

Once you have chosen your strategy, you should run it until you get the wish 10,000 times and report the mean cost. If two answers have the same strategy, the one posted first wins. If two strategies have similar mean costs you may need to test it 100,000 or even more times to tell the difference.

# Input and output

There is no input in this challenge. The output is just the mean cost to get a wish. To test your code you will need to implement both the wizard and your strategy.

# Answer
> 6 votes
# Python, cost = \\$\frac{654510644704}{387420489}\\$ = 1689.4063770179175

An optimal strategy, computed and evaluated exactly with this code (which uses a similar Newton’s method search as a comment of mine on your previous challenge, and is equivalent to Nitrodon’s comment on this one).

```
import math
import random

def strategy(opened, found):
    return found >= [0, 2, 3, 4, 5, 6, 7, 8, 9][opened]

count, mean, m2 = 0, 0.0, 0.0

for run in range(10000):
    cost = 0

    while True:
        coins = [0] * 10
        for i in range(random.randrange(1, 11)):
            coins[random.randrange(10)] += 1

        opened, found = 0, 0
        while found != 10 and opened != 9 and strategy(opened, found):
            found += coins[opened]
            cost += 2**opened
            opened += 1
        if found == 10:
            break

    count += 1
    delta = cost - mean
    mean += delta / count
    m2 += delta**2 * (1 - 1 / count)

mean_stdev = math.sqrt(m2 / (count * (count - 1)))
print(f"{mean} ± {mean_stdev}")

```

Try it online!

# Answer
> 3 votes
# R / Rcpp: 1688.758 ± 0.740

Evaluated on 15 million simulated games. Error values are a bootstrap confidence interval with 10,000 iterations. The learned policy matches Anders' optimal policy.

## Method

The policy to minimize cost was learned using double n-step SARSA, a reinforcement learning algorithm. The optimal policy was learned by training 15 agents in parallel, where each agent's current policy was replaced by the average of all agents' policies every 100,000 actions. The optimal policy was found in about 4.5e8 actions, or ~150,000 epsiodes at 3000 actions per episode.

The algorithm's learning parameters were set as follows: discount factor `gamma = 0.17258`, learning rate `alpha = 0.3904111`, and epsilon-greedy action selection `epsilon = 0.2702468`. I originally wrote the algorithm as an n-step SARSA but settled on `n = 1`. The learning parameters were found using model-based Bayesian optimization. I used 105 points for the initial design and searched 50 sequentially proposed points.

### Reward Shaping

When reaching a new state by opening a box, the agent's reward was the sum of the value of the found coins, where coin `n` is worth \\$2^{n-1}\\$, minus the cost of the opened box. When giving up the set of boxes and starting over, the agent's reward was the negative sum of the value of the coins it had found during the episode if the episode was possible to have won; otherwise, the agent's reward was zero. In all cases a constant reward of `-1` was applied.

## Learned Policy

The below photo shows the policy learned by the agent. A black square indicates that if the agent has collected the corresponding number of coins by opening that many boxes, it will continue to open boxes. Otherwise, the agent will give up the set of boxes.

## Code

**R code to initialize the state-action space**

```
#' Initialize the State-Action Space
initStateSpace <- function(){

  #Generate full grid
  space = expand.grid(
    numOpenBox = 0:9,
    numCoins = 0:10,
    act = c(0:1)
  )

  #Remove states where no boxes are open, but positive coins found
  inds = (space$numOpenBox == 0) & (space$numCoins > 0)
  space = space[!inds,]

  #Remove states where all boxes are open, but action is open box
  inds = (space$numOpenBox == 9) & (space$act == 1)
  space = space[!inds,]

  #Add columns for value
  space$valueA = 0
  space$valueB = 0

  #Return
  return(as.matrix(space))

}

```

**Rcpp code for the algorithm, simulation, and evaluation** Note: Because the episode is cyclical, I opted not to handle updating the state-action values for pairs within n steps of the terminal state.

```
#include <Rcpp.h>
using namespace Rcpp;

//* Place Coins in Boxes
// [[Rcpp::export]]
NumericVector setCoins() {

  //Sample number of coins
  NumericVector coinSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  NumericVector boxSet = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  NumericVector nCoins = Rcpp::sample(coinSet, 1);
  NumericVector boxInds = Rcpp::sample(boxSet, nCoins[0], true);

  //Assign coins to boxes
  NumericVector out (10);
  for(int i = 0; i < 10; i++){
    for(int j = 0; j < boxInds.length(); j++){
      if(i == boxInds[j] - 1){
        out[i] = out[i] + 1;
      }
    }
  }

  //Return
  return(out);

}

//* Subset State-Action Space by State
// [[Rcpp::export]]
NumericMatrix subsetSpace(
    NumericVector state,
    NumericMatrix stateSpace
) {

  //Find rows that match the input state
  LogicalVector inds (stateSpace.nrow(), false);
  for(int i = 0; i < inds.length(); i++){
    if(stateSpace(i, 0) == state[0] & stateSpace(i, 1) == state[1]){
      inds[i] = true;
    }
  }

  //Subset the state-action space to the input state
  NumericMatrix out(sum(inds), stateSpace.ncol());
  for(int i = 0, j = 0; i < inds.length(); i++){
    if(inds[i]){
      out(j, _) = stateSpace(i, _);
      j = j + 1;
    }
  }

  //Return
  return(out);

}

//* Choose action
// [[Rcpp::export]]
double chooseAction(
    NumericVector state,
    NumericMatrix stateSpace,
    double epsilon
) {

  //Subset state-action space to input state
  NumericMatrix localSpace = subsetSpace(state, stateSpace);

  //Epsilon-greedy action selection
  double action;
  if(Rcpp::runif(1, 0.0, 1.0)[0] <= epsilon){
    IntegerVector actionSet = Rcpp::seq(0, localSpace.nrow() - 1);
    IntegerVector actionInd = Rcpp::sample(actionSet, 1);
    action = localSpace(actionInd[0], 2);
  } else {
    NumericVector value = (localSpace(_, 3) + localSpace(_, 4)) / 2;
    int actionInd = Rcpp::which_max(value);
    action = localSpace(actionInd, 2);
  }

  //Return
  return(action);

}

//* Calculate Reward
// [[Rcpp::export]]
double calculateReward(NumericVector state, NumericVector boxState) {
  double reward = 0;
  int openBoxes = state[0];
  int coinsFound;
  if(state[2] == 1) {

    //Reward for opening box is value of coins found minus cost of box
    coinsFound = boxState[openBoxes];
    reward += -pow(2, openBoxes);
    for(int j = 0; j < coinsFound; j++){
      reward += pow(2, state[1] + j);
    }

  } else {

    //Reward for shuffling is regret if the game was possible to complete
    if(sum(boxState) == 10 & boxState[9] == 0) {
      for(int j = 0; j < state[1]; j++){
        reward += -pow(2, j);
      }
    }

  }

  //Constant negative reward
  reward += -1;

  //Return
  return(reward);

}

//* Take Action
// [[Rcpp::export]]
NumericVector takeAction(NumericVector state, NumericVector boxState) {
  double reward = calculateReward(state, boxState);
  if(state[2] == 1) {
    int openBoxes = state[0];
    state[0] = state[0] + 1;
    state[1] = state[1] + boxState[openBoxes];
    state[2] = -1;
    state[3] = reward;
  } else {
    state = {0, 0, 1, reward};
  }
  return(state);
}

//* Find State-Action Index
// [[Rcpp::export]]
int findStateIndex(
    NumericVector state,
    NumericMatrix stateSpace
) {
  int index = NA_INTEGER;
  for(int i = 0; i < stateSpace.nrow(); i++){
    if(stateSpace(i, 0) == state[0] & stateSpace(i, 1) == state[1] & stateSpace(i, 2) == state[2]){
      index = i;
      break;
    }
  }
  return(index);
}

//* Create Record
// [[Rcpp::export]]
NumericMatrix createRecord(int n) {
  NumericVector v (2 * (n + 1), -1.0);
  return(NumericMatrix (n + 1, 2, v.begin()));
}

//* Copy State to Record
// [[Rcpp::export]]
NumericMatrix copyToRecord(
  NumericVector state,
  NumericMatrix stateSpace,
  NumericMatrix record
) {

  //Find index of state-action pair
  int pairInd = findStateIndex(state, stateSpace);

  //Write to first open index if possible
  bool openSlot = false;
  for(int i = 0; i < record.nrow(); i++){
    if(record(i, 0) == -1){
      record(i, 0) = pairInd;
      record(i, 1) = state[3];
      openSlot = true;
      break;
    }
  }

  //Otherwise, shift down and write
  if(!openSlot){
    for(int i = 1; i < record.nrow(); i++){
      record(i - 1, 0) = record(i, 0);
      record(i - 1, 1) = record(i, 1);
    }
    record(record.nrow() - 1, 0) = pairInd;
    record(record.nrow() - 1, 1) = state[3];
  }

  //Return
  return(record);

}

//* Calculate Return
// [[Rcpp::export]]
double calculateReturn(
  NumericMatrix record,
  double gamma
) {
  double g = 0;
  for(int i = 1; i < record.nrow(); i++){
    g = g + pow(gamma, i - 1) * record(i, 1);
  }
  return(g);
}

//* Update State-Action Value
// [[Rcpp::export]]
NumericMatrix updateStAcValue(
  NumericMatrix record,
  NumericMatrix stateSpace,
  double gamma,
  double alpha
) {

  //Double SARSA
  //Randomly select A or B values to update
  IntegerVector vSet = {0, 1};
  vSet = Rcpp::sample(vSet, 1);
  vSet.push_back(1 - vSet[0]);

  //Shift vSet to match value column numbers
  vSet = vSet + 3;

  //Update state-action value
  int n = record.nrow() - 1;
  double G = calculateReturn(record, gamma);
  G = G + pow(gamma, n) * stateSpace(record(n, 0), vSet[0]);
  stateSpace(record(0, 0), vSet[1]) += alpha * (G - stateSpace(record(0, 0), vSet[1]));

  //Return
  return(stateSpace);

}

//* Learn Policy
// [[Rcpp::export]]
NumericMatrix learnPolicy(
    NumericMatrix stateSpace,
    double gamma,
    double alpha,
    double epsilon,
    int n,
    int iters
) {

  //Loop episodes
  int i = 0;
  while(true){

    //Initialize n-step Sarsa
    NumericMatrix record = createRecord(n);
    NumericVector boxState = setCoins();
    NumericVector state = {0, 0, 1, 0};

    //Record initial state
    record(0, 0) = findStateIndex(state, stateSpace);

    //Complete episode
    double t = 0;
    double tau = 0;
    double T = R_PosInf;
    bool done = false;
    while(!done) {

      //Take action
      if(state[2] == 1){
        state = takeAction(state, boxState);
        state[2] = chooseAction(state, stateSpace, epsilon);
      } else if(state[2] == 0) {
        state = takeAction(state, boxState);
        boxState = setCoins();
      }

      //Update record
      record = copyToRecord(state, stateSpace, record);

      //Update state-action values
      tau = t - n + 1;
      if(tau >= 0){
        stateSpace = updateStAcValue(record, stateSpace, gamma, alpha);
      }

      //Complete
      t = t + 1;
      if(state[1] == 10){
        done = true;
      }

      //Break loop when all iterations are complete
      i += 1;
      if(i >= iters){
        break;
      }

    }

    //Break loop when all iterations are complete
    if(i >= iters){
      break;
    }

  }

  //Return
  return(stateSpace);

}

//* Evaluate Policy
// [[Rcpp::export]]
NumericVector evaluatePolicy(
  NumericMatrix stateSpace,
  int iters
) {
  NumericVector out (iters, 0.0);
  for(int i = 0; i < iters; i++){
    NumericVector boxState = setCoins();
    NumericVector state = {0, 0, 1, 0};
    bool done = false;
    while(!done) {
      if(state[2] == 1){
        out[i] += pow(2, state[0]);
        state = takeAction(state, boxState);
        state[2] = chooseAction(state, stateSpace, 0.0);
      } else if(state[2] == 0) {
        state = {0, 0, 1, 0};
        boxState = setCoins();
      }
      if(state[1] == 10){
        done = true;
      }
    }
  }
  return(out);
}

```

**R code to learn and evaluate policy** Learning parameters found using Model-Based Bayesian Optimization

```
#Create a policy by parallel RL
#Learns the optimal policy in 4.5e8 actions over 15 agents
#Or ~150,000 episodes total at 3000 actions per episode
#Agents replace their policies with the average policy every 100,000 actions
numAgents = 15
for(i in 1:300){

  #Generate initial policies
  if(i == 1){
    policy = lapply(1:numAgents, function(c){
      learnPolicy(
        initStateSpace(),
        n = 1,
        gamma = 0.17258,
        alpha = 0.3904111,
        epsilon = 0.2702468,
        iters = 1500000 / numAgents
      )
    })
    policy = Reduce("+", policy) / numAgents

  } else {

  #Use the average of the initial policies to seed new agents
    policy = lapply(1:numAgents, function(c){
      learnPolicy(
        policy,
        n = 1,
        gamma = 0.17258,
        alpha = 0.3904111,
        epsilon = 0.2702468,
        iters = 1500000 / numAgents
      )
    })
    policy = Reduce("+", policy) / numAgents

  }

}

#Evaluate policy over 15mil episodes
summary(evaluatePolicy(policy, 15000000))

```

---
Tags: code-challenge, optimization
---


# Question
Title: An algorithm to find even sublime numbers
A perfect number is a positive integer whose sum of divisors (except itself) is equal to itself. E.g. 6 (1 + 2 + 3 = 6) and 28 (1 + 2 + 4 + 7 + 14 = 28) are perfect.

A **sublime number** (OEIS A081357) is a positive integer whose count and sum of divisors (including itself) are both perfect. E.g. 12 is a sublime number because:

* the divisors of 12 are 1, 2, 3, 4, 6, 12
* the count of divisors is 6 (perfect)
* the sum of divisors is 28 (perfect)

The next smallest known sublime number is

```
6086555670238378989670371734243169622657830773351885970528324860512791691264

```

and these two numbers are the only known sublime numbers as of 2022. The necessary and sufficient conditions for even sublime numbers have been found in this paper (pdf), but it remains unknown whether odd sublime numbers exist.

The paper outlines the "algorithm" to find even sublime numbers:

> Suppose \\$p\\$ is a prime with the following properties,
>
> * \\$q = 2^p − 1\\$ is a prime.
> * \\$2^q − 1\\$ is a prime.
> * \\$q − 1\\$ can be partitioned into distinct primes \\$l\_1, \cdots , l\_{p−1}\\$ such that \\$m\_i = 2^{l\_i} − 1\\$ are also prime for all \\$i\\$.
>
> Then \\$n = 2^{q−1} ( \prod{m\_i} )\\$ is a sublime number.

This heavily relies on Mersenne primes, which are primes in the form of \\$2^n-1\\$. Let's define *Mersenne exponents* be the values of \\$n\\$ such that \\$2^n-1\\$ is prime. The list of known Mersenne exponents can be found on this Wikipedia page; it starts with

```
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, ...

```

and only around 50 such exponents are known.

We can rewrite the algorithm in terms of a known set \\$L\\$ of Mersenne exponents:

> Loop over \\$p \in L\\$:
>
> * Check that \\$q = 2^p - 1 \in L\\$. If so,
> * For each subset \\$\\{ l\_i \\}\\$ of \\$L\\$ of size \\$p-1\\$:
>     + If it sums to \\$q-1\\$,
>     + output \\$n = 2^{q-1} ( \prod{(2^{l\_i}-1)} )\\$ as a sublime number found.

Since the list of actual Mersenne exponents is fairly limited, we wouldn't get any more sublime numbers by using this algorithm on it. So let's run it on an arbitrary set of positive integers instead.

## Challenge

Given a set of positive integers \\$L\\$, evaluate all possible outputs (values of \\$n\\$) the algorithm above would give you. Since \\$p=1\\$ is kind of an edge case, you may assume that \\$L\\$ does not contain 1.

You may assume that \\$L\\$ is nonempty. If you take \\$L\\$ as a list (as opposed to an unordered set), you may assume that it is sorted. You may output the values of \\$n\\$ in any order, and may output the same value multiple times. If multiple subsets satisfy the condition for a single \\$p\\$, all possible resulting \\$n\\$s must be output.

Standard rules apply. The shortest code in bytes wins.

## Examples

If \\$L=\\{2,3\\}\\$, \\$p=2\\$ satisfies the condition:

* 2 is in \\$L\\$ and \\$2^2-1 = 3\\$ is also in \\$L\\$.
* A subset of size \\$p-1 = 1\\$ with sum \\$q-1 = 2\\$ exists: \\$\\{2\\}\\$.
* The output is \\$n = 2^{3-1} (2^2-1) = 12\\$.

For \\$L = \\{2, 3, 4, 7\\}\\$, \\$p=3\\$ also does:

* 3 is in \\$L\\$ and \\$2^3-1 = 7\\$ is also in \\$L\\$.
* A subset of size \\$p-1 = 2\\$ with sum \\$q-1 = 6\\$ exists: \\$\\{2,4\\}\\$. (\\$\\{3,3\\}\\$ does not work since it is just \\$\\{3\\}\\$.)
* The output is \\$n = 2^{7-1} (2^2-1)(2^4-1) = 2880\\$.

## Test cases

```
L => [n]
[2] => []
[2, 3] => [12]
[2, 3, 4] => [12]
[2, 3, 4, 7] => [12, 2880]
[3, 4, 7] => []
[3, 4, 5, 6, 7, 15] =>
  [218480640 = 2^14(2^3-1)(2^4-1)(2^7-1),
   223985664 = 2^14(2^3-1)(2^5-1)(2^6-1)]
[2, 3, 5, 7, 15] => [12] (suggested by Jonathan Allan)
(actual Mersenne exponents, truncated and 2 removed)
[3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607] =>
  [6086555670238378989670371734243169622657830773351885970528324860512791691264
   = 2^126(2^3-1)(2^5-1)(2^7-1)(2^19-1)(2^31-1)(2^61-1)]

```

# Answer
# PARI/GP, 108 bytes

```
l->forsubset(#l,s,setminus([p=#s+1,q=2^p-1],l)||sum(i=1,#s,l[s[i]])-q--||print(prod(i=1,#s,2^l[s[i]]-1)<<q))
```

Attempt This Online!

Takes input as sorted lists.
> 6 votes

# Answer
# JavaScript (V8),  ~~119~~  117 bytes

Given a list of integers, prints the pseudo-sublime numbers.

```
L=>L.map(g=(p,_,a,s=L.includes(q=2**p-1)*--q,o=2**q)=>--p?a.map((x,i)=>g(p,_,a.slice(i+1),s-x,o*2**x-o)):s||print(o))

```

Try it online!

### Commented

```
L =>                    // L[] = input list
L.map(g =               // for each element in L[],
  (                     // invoke the recursive callback function g:
    p,                  //   p = current element from L[]
    _,                  //   (ignored index of this element)
    a,                  //   a[] = input list (truncated on subsequent calls)
    s = L.includes(     //   test whether L[] includes:
      q = 2 ** p - 1    //     q = 2 ** p - 1
    ) * --q,            //   decrement q and save either 0 or q in s,
                        //   which is our target sum
    o = 2 ** q          //   o = output product, initialized to 2 ** q
  ) =>                  //
  --p ?                 //   decrement p; if it's not 0:
    a.map((x, i) =>     //     for each element x at position i in a[]:
      g(                //       do a recursive call:
        p,              //         new value of p
        _,              //         (ignored index)
        a.slice(i + 1), //         remove the i + 1 first elements of a[]
        s - x,          //         subtract x from s
        o * 2 ** x - o  //         multiply o by 2 ** x - 1
      )                 //       end of recursive call
    )                   //     end of inner map()
  :                     //   else (p = 0):
    s || print(o)       //     print o if s = 0
)                       // end of outer map()

```
> 5 votes

# Answer
# Vyxal, ~~34~~ 24 bytes

```
ṗ'L›:E‹"?↔‹n∑ḟɾ;ƛ∑JEn±-Π

```

Try it Online!

~~Mess.~~ Well, still a mess, but -10 bytes by porting Jonathan Allan's Jelly answer, upvote that!
> 4 votes

# Answer
# Jelly, ~~37~~ 36 bytes (thanks @Steffan!)

```
2*’
§=⁹aÇP€×2*⁹¤ʋ
Ñe³ƊƇµ’³œcç"Ñ’$F¹Ƈ

```

Try it online!

Also a mess.

Link 1: computes \\$2^x-1\\$

```
2    Two
 *   To the power of the input
  ’  Decrement

```

Link 2: given a list of subsets of length \\$p-1\\$ of the input list, and \\$q-1\\$ (as defined in the question), return a list with all valid answers or 0.

```
§=⁹aÇP€×2*⁹¤ʋ
§              Compute the sum of each sublist (vectorizes at depth 1)
 =             Check if equal to... (vectorizes)
  ⁹            ...q-1
   a           Logical AND with...
            ʋ  ...the four previous links as a dyad
    Ç              The previous link as a monad (2^x-1 for each x in each subset)
      €            For each subset:
     P                 Compute the product
       ×           Multiply by...
           ¤       ...a nilad followed by some links, as a nilad:
        2              Two
         *             To the power of...
          ⁹            ...q-1

```

Link 3 (main link): given the input list, outputs all valid answers.

```
Ñe³ƊƇµ’³œcç"Ñ’$F¹Ƈ
    Ƈ               Filter the list using:
   Ɗ                    The last three links as a monad
Ñ                           The next link as a monad (wraps around to link 1)
 e                          Check if it's present in...
  ³                         ...the input list
     µ              Start a new monadic chain
(At this point, the list contains all 'p' in the input list such that 2^p-1 is also in the input list.)
      ’             Decrement
        œc          All combinations of ... of any length in the list (vectorizes over the right argument)
       ³            The input list
           "        Zipping over the left and right arguments:
          ç             Call the previous link as a dyad, with the next link as the right argument
              $     The last two links as a monad:
            Ñ           The next link (wraps around to link 1) on each valid 'p', thus generating all the candidates for 'q'
             ’          Decrement (thus generating all the candidates for q-1)
               F    Flatten
                 Ƈ  Filter the list using:
                ¹   The truth value of each element itself (thus removing all falsy values from the list)

```
> 4 votes

# Answer
# Jelly, 27 bytes

```
L‘2*’ṭƲf’iS{Ṗ
ŒPçƇµ;S2*_ṠP)

```

A monadic Link that accepts a list of distinct integers greater than \\$1\\$ and yields a list of the implied pseudo-sublime numbers.

**Try it online!** Or see the test-suite.

### How?

```
L‘2*’ṭƲf’iS{Ṗ - Helper Link, valid subset?: Subset; L
L             - length of Subset
 ‘            - increment -> p'
      Ʋ       - last four links as a monad - f(p'):
  2           -   two
   *          -   exponentiate (p')
    ’         -   decrement -> q'
     ṭ        -   tack -> [p', q']
       f      - filter keep only those of [p', q'] which are in L
                We now have one of: []; [p']; [q']; or [p'=p, q'=q]
        ’     - decrement -> F (e.g. F=[p-1, q-1])
           {  - using left argument, Subset:
          S   -   sum
         i    - first 1-indexed index of that sum in F or 0 if not found
            Ṗ - pop (implicit range [1..that])
                This yields:
                  [] (falsey) when i resulted in 0 or 1; or
                  [1] (truthy) when i resulted in 2 (i.e. p'=p, q'=q, and q-1=sum)

ŒPçƇµ;S2*_ṠP) - Link, get pseudo-sublimes: set of integers > 1, L
ŒP            - powerset of L -> all subsets we could make
   Ƈ          - filter-keep those for which:
  ç           -   call the Helper Link - f(subset, L)
    µ       ) - for each:
                             e.g. [a, b, ..., n]
      S       -   sum (Subset)    a + b + ... + n = q-1
     ;        -   concatenate  -> [    a,     b, ...,     n,    q-1 ]
       2      -   two
        *     -   exponentiate -> [  2^a,   2^b, ...,   2^n, 2^(q-1)]
          Ṡ   -   sign (Subset)-> [    1,     1, ...,     1]
         _    -   subtract     -> [2^a-1, 2^b-1, ..., 2^n-1, 2^(q-1)]
           P  -   product      -> pseudo-sublime number

```
> 4 votes

# Answer
# Charcoal, 46 bytes

```
ＩＥΦＥＸ²ＬθΦθ＆ιＸ²μ∧⁼Σι⊗⊖Ｘ²Ｌι∧№θ⊕Ｌι№θ⊕Σι×Ｘ²ΣιΠ⊖Ｘ²ι

```

Try it online! Link is to verbose version of code. Explanation:

```
ＩＥΦＥＸ²ＬθΦθ＆ιＸ²μ

```

For each subset of the input list, such that...

```
∧⁼Σι⊗⊖Ｘ²Ｌι

```

... the sum of each subset is two less than twice two to the power of its size, and...

```
∧№θ⊕Ｌι

```

... the size of the subset is one less than one of the integers in the input list, and...

```
№θ⊕Σι

```

... the sum of the subset is also one less than one of the integers in the input list, ...

```
×Ｘ²ΣιΠ⊖Ｘ²ι

```

... raise two to the power of each of the integers in the subset, decrement the results, take the product, and multiply by two to the power of the sum of the subset.
> 3 votes

# Answer
# Brachylog, 45 bytes

```
∋P{;2↔^-₁}Q∈?∧P-₁~lċS⊆?∧S++₁Q-₁;2↔^R∧S↰₁ᵐ×;R×

```

Try it online!

This is a generator that can be used to get all results.

There are surely some shorter ways to express things.

### Explanation

```
∋P              P is an element of the input
  {;2↔^-₁}Q     Q = 2^P - 1
          Q∈?   Q is an element of the input
∧
P-₁~lċS         S is a list of length P-1
      S⊆?       S is a subset of the input
∧
S++₁Q           The elements of S sum to Q-1
    Q-₁;2↔^R    R = 2^(Q-1)
∧
S↰₁ᵐ            Map the first predicate {;2↔^-₁} to each element of S
    ×           Multiply the result
     ;R×        Multiply with R

```
> 3 votes

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

-6 bytes porting *@JonathanAllan*'s Jelly answer, thanks to *@Steffan*:

```
æʒg>Do<‚Ã<yOk}εo<PyOo*

```

Try it online or verify all test cases.

**Original ~~30~~ 28 bytes answer:**

```
æεg>©å*®o<åyO®oÍ©Q*iyo<®oªP,

```

Outputs the results on separated lines to STDOUT.

Try it online or verify all test cases.

**Explanation:**

```
æ            # Get the powerset of the (implicit) input-list
 ʒ           # Filter the inner lists `y` by:
             #  (implicitly push list `y`)
  g          #  Pop and get the length of list `y`
   >         #  Increase it by 1
    D        #  Duplicate this length+1
     o       #  Take 2 to the power this value
      <      #  Decrease it by 1
       ‚     #  Pair them together: [length+1,2**(length+1)-1]
        Ã    #  Only keep those values from the (implicit) input-list
  <          #  Decrease each remaining value by 1
   yO        #  Push the sum of list `y`
     k       #  Get its 0-based index in the list of 0, 1, or 2 items
             #  (only 1 is truthy in 05AB1E)
 }ε          # After the filter: map over the remaining inner lists `y`:
   o         #  Take 2 the power each value in the list
    <        #  Decrease each by 1
     P       #  Take the product of these values
      yO     #  Then push the sum of list `y`
        o    #  Take 2 to the power this sum as well
         *   #  And multiply it to the earlier product
             # (after which the list is output implicitly as result)

```

```
æ            # Get the powerset of the (implicit) input-list
 ε           # For each over the inner lists `y`:
             #  (implicitly push list `y`)
  g          #  Pop and get the length of list `y`
   >         #  Increase it by 1
    ©        #  Store it in variable `®` (without popping)
     å       #  Check that it's in the (implicit) input-list
      *      #  Multiply this 0 or 1 to the (implicit) input-list,
             #  so we either have a list of 0s, or the unmodified input-list
  ®          #  Push length+1 from variable `®` again
   o         #  Pop and push 2 to the power this
    <        #  Decrease it by 1
     å       #  Check if it's in the earlier list (the input-list or list of 0s)
  yO         #  Push the sum of the current list `y`
    ®o       #  Push 2 to the power `®` again
      Í      #  Decrease it by 2
       ©     #  Store this as new variable `®` (without popping)
        Q    #  Check if it's equal to the sum
  *i         #  If both checks are truthy:
    y        #   Push list `y` again
     o       #   Calculate 2 to the power each value in the list
      <      #   Then decrease each by 1
       ®     #   Push variable `®`: 2**(length+1)-2
        o    #   Get 2 to the power this value
         ª   #   Append it to the list
          P  #   Get the product of this list
           , #   Pop and print it to STDOUT with trailing newline

```
> 1 votes

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


title: Implement Level-Index Addition

text:
# Question
Title: Implement Level-Index Addition
Level-index is a system of representing numbers which has been proposed as an alternative to floating-point formats. It claims to virtually eliminate overflow (and underflow, in its symmetric form) from the vast majority of computations.

The usual floating-point format internally represents a number \\$x\\$ in terms of a mantissa \\$m\in\[1,2)\\$ and an integer exponent \\$e\\$, where \\$x=m\times2^e\\$. In contrast, level-index represents a number by an integer level \\$l\ge0\\$ and an index \\$i\in\[0,1)\\$, defined by
\\$l+i=\psi(x)=\begin{cases} x,&x\<1\\ 1+\psi(\log x),&\text{otherwise.} \end{cases}\\$
Equivalently, \\$l\\$ and \\$i\\$ together represent the power tower number \\$x=\psi^{-1}(l+i)=\operatorname{exp}^l(i)\\$. Accordingly, \\$\psi^{-1}\\$ grows very fast; \\$\psi^{-1}(5)\\$ has more than a million digits to the left of the decimal point.

## Task

Given two numbers \\$\psi(a),\psi(b)\\$, compute their level-index sum \\$\psi(a+b)\\$. You may choose to input or output the level and index together or separately.

Your solution should be accurate to at least six digits after the decimal point and terminate in a reasonable time for all \\$\psi(a+b)\<8\\$, and may not assume your floating-point representation has infinite precision.

### Test cases

```
ψ(a)    ψ(b)    ψ(a+b)              a           b           a+b
0       0       0.0000000000000000  0           0           0
1       1       1.6931471805599453  1           1           2
2       2       2.5265890341390445  2.718281828 2.718281828 5.436563657
3       3       3.2046791426805201  1.5154262e1 1.5154262e1 3.0385245e1
4       4       4.0161875057657443  3.8142791e6 3.8142791e6 7.6285582e6
5       5       5.0000000044114734  2.3e1656520 2.3e1656520 4.7e1656520
1.70879 2.44303 2.6490358380192970  2.031531618 4.746554831 6.778086449
0.8001  3.12692 3.1367187876590184  0.8001      2.2470167e1 2.3270267e1
2.71828 3.14159 3.2134989633416356  7.774915755 2.368508064 3.1459996e1
4.6322  4.6322  4.6322790036002559  1.79455e308 1.79455e308 3.58910e308
4.80382 4.80382 4.8038229252940133  5.9037e4932 5.9037e4932 1.1807e4933

```

# Answer
# SageMath, 93 bytes

```
lambda x,y:h(p(x)+p(y))
h=lambda x:x>1 and 1+h(log(x))or x
p=lambda x:x>1 and exp(p(x-1))or x

```

Try it online!
> 3 votes

# Answer
# Python NumPy, 178 bytes

```
def f(I):
 i,j=sort(I)
 if 4+i>j<5.5:
  j=[add,logaddexp][l:=i>1](p(j-l),p(i-l))
  while j>=1:l+=1;j=log(j)
  j+=l
 return j
p=lambda x:x>1 and exp(p(x-1))or x
from numpy import*
```

Attempt This Online!

Saved a bit by borrowing @Noodle9's `p` function.

### Previous Python NumPy, 202 bytes

```
def f(I):
 i,j=sort(I);l,*c=0,
 if 4+i>j<5.5:
  l=i>1
  for y in i,j:
   r=y%1
   while y>=1+l:r=exp(r);y-=1
   c+=r,
  j=[add,logaddexp][l](*c)
  while j>=1:l+=1;j=log(j)
 return l+j
from numpy import*
```

Attempt This Online!

I'm sure this can be golfed quite a bit.

### How

With the given accuracy requirements we need something to bridge the gap between small values (\<4.5, say) where we can use exp without overflowing and large (\>5.5) where we can simply use the max. Luckily, NumPy has `logaddexp` built in which saves us one level of exponentiating.
> 1 votes

---
Tags: code-golf, restricted-time, floating-point
---