title: Vertically collapse text

text:
# Question
Title: Vertically collapse text
Say I have text like this (each word on one line, with no spaces)

```
Programming
Puzzles
&
Code
Golf

```

That makes no sense! It totally defies the laws of physics.

Your challenge is to remedy this impossible situation and collapse the text like so:

```
P
Prog
&uzz
Coderam
Golflesming

```

So that there is no empty space underneath any character but the characters retain their vertical order.

The goal is to satisfy the requirements but use the fewest bytes of source code possible.

# Answer
# Pyth, 10 bytes

```
jb_.T.T_.z

```

Try it online in the Pyth Compiler/Executor.

### Idea

We can achieve the desired output by applying four simple transformations:

1. Reverse the order of the lines:

```
Golf
Code
&
Puzzles
Programming

```
2. Transpose rows and columns:

```
GC&PP
oour
ldzo
fezg
lr
ea
sm
m
i
n
g

```

This top justifies, collapsing the original columns.
3. Transpose rows and columns:

```
Golflesming
Coderam
&uzz
Prog
P

```
4. Reverse the order of the lines:

```
P
Prog
&uzz
Coderam
Golflesming

```

### Code

```
        .z  Read the input as a list of strings, delimited by linefeeds.
       _    Reverse the list.
   .T.T     Transpose the list twice.
  _         Reverse the list.
jb          Join its strings; separate with linefeeds.

```
> 57 votes

# Answer
# Haskell, 62 bytes

```
import Data.List
p=reverse;o=transpose
f=unlines.p.o.o.p.lines

```

I'm very mature.
> 39 votes

# Answer
## Python 2, 104 bytes

```
l=[]
for x in input().split('\n'):n=len(x);l=[a[:n]+b[n:]for a,b in zip(l+[x],['']+l)]
print'\n'.join(l)

```

An iterative one-pass algorithm. We go through each line in order, updating the list `l` of lines to output. The new word effectively pushes from the bottom, shifting all letters above it one space. For example, in the test case

```
Programming
Puzzles
&
Code
Golf

```

after we've done up to `Code`, we have

```
P
Prog
&uzzram
Codelesming

```

and then adding `Golf` results in

```
P
Prog
&uzz
Coderam
Golflesming

```

which we can view as the combination of two pieces

```
P     |
Prog  |
&uzz  |
Code  | ram
Golf  | lesming

```

where the first piece got shifted up by `golf`. We perform this shifting with a `zip` of the output list with the element at the end (left side) and output list precedence by a blank line (right side), cutting off each part at the length of the new element.

It might seem more natural to instead iterate backwards, letting new letters fall from the top, but my attempt at that turned out longer.

For comparison, here's a `zip`/`filter` approach, with `map(None,*x)` used for `iziplongest` (109 bytes):

```
f=lambda z:[''.join(filter(None,x))for x in map(None,*z)]
lambda x:'\n'.join(f(f(x.split('\n')[::-1]))[::-1])

```
> 17 votes

# Answer
# CJam, 11 bytes

```
qN/W%zzW%N*

```

Try it online in the CJam interpreter.

### How it works

The idea in the same as in my Pyth answer.

```
q           e# Read from STDIN.
 N/         e# Split at linefeeds.
   W%       e# Reverse the resulting array.
     zz     e# Transpose it twice.
       W%   e# Reverse the resulting array.
         N* e# Join its strings; separate with linefeeds.

```
> 12 votes

# Answer
# JavaScript (ES6), 146

(The 2 newlines inside template strings are significant and counted)

The idea of @Dennis implemented in JavaScript. The lengthy S function do the transposition line by line and char by char, leaving the result in the `t` array.

```
a=>(S=z=>{for(t=[];z.join``;t.push(w))for(w='',n=z.length;n--;z[n]=z[n].slice(1))w+=z[n][0]||''},S(a.split`
`),S(t.reverse()),t.reverse().join`
`)

```

Less golfed inside the snippet (try in Firefox)

```
F=a=>(
  S=z=>{
    for(t=[];z.join``;t.push(w))
      for(w='',n=z.length;n--;z[n]=z[n].slice(1))
        w+=z[n][0]||''
  },
  S(a.split`\n`),
  S(t.reverse()),
  t.reverse().join`\n`
)
```

```
#I,#O { margin:0; width: 200px; height:100px; border: 1px solid #ccc }
```

```
<table><tr><td>
Input<br><textarea id=I>Programming
Puzzles
&
Code
Golf
</textarea></td><td>
Output<pre id=O></pre>
</td></tr></table>
<button onclick='O.innerHTML=F(I.value)'>go</button>
```
> 7 votes

# Answer
# R, 223 bytes

```
function(x){a=apply(do.call(rbind,lapply(p<-strsplit(strsplit(x,"\n")[[1]],""),function(x)c(x,rep(" ",max(lengths(p))-length(x))))),2,function(x)c(x[x==" "],x[x!=" "]));for(i in 1:nrow(a))cat(a[i,][a[i,]!=" "],"\n",sep="")}

```

This is an absurdly long, naïve way of doing it.

Ungolfed:

```
f <- function(x) {
    # Start by spliting the input into a vector on newlines
    s <- strsplit(x, "\n")[[1]]

    # Create a list consisting of each element of the vector
    # split into a vector of single characters
    p <- strsplit(s, "")

    # Pad each vector in p to the same length with spaces
    p <- lapply(p, function(x) c(x, rep(" ", max(lengths(p)) - length(x))))

    # Now that the list has nice dimensions, turn it into a matrix
    d <- do.call(rbind, p)

    # Move the spaces to the top in each column of d
    a <- apply(d, 2, function(x) c(x[x == " "], x[x != " "]))

    # Print each row, omitting trailing whitespace
    for (i in 1:nrow(a)) {
        cat(a[i, ][a[i, ] != " "], "\n", sep = "")
    }
}

```

You can try it online.
> 5 votes

# Answer
## Matlab / Octave, 99 bytes

```
function f(s)
c=char(strsplit(s,[10 '']));[~,i]=sort(c>32);[m,n]=size(c);c(i+repmat((0:n-1)*m,m,1))

```

**Example**:

Define an input string in a variable, say `s`. `10` is the line feed character:

```
>> s = ['Programming' 10 'Puzzles' 10 '&' 10 'Code' 10 'Golf'];

```

Call function `f` with input `s`:

```
>> f(s)
ans =
P
Prog
&uzz
Coderam
Golflesming

```

Or **try it online** (thanks to @beaker for help with the online Octave interpreter)
> 5 votes

# Answer
# JavaScript ES6, 119 bytes

```
F=s=>(C=o=>--a.length?C(a.reduce((p,c,i)=>c+p.slice((a[i-1]=p.slice(0,c.length)).length)))+`
`+o:o)(a=(s+`
`).split`
`)

```

Here it is ungolfed and in ES5 with comments explaining how it works:

```
function F(s) {
  var arr = (s+'\n').split('\n'); // Create an array of words and append an empty member
  return (function C(output) {
    return --arr.length ? // Remove the last item from the array
      C(arr.reduce(function(p,c,i) { // If the array still has length reduce it to a string and recurse
        var intersection = (arr[i-1] = p.slice(0, c.length)) // Overwrite the previous word with the part that intersects the current word
        return c + p.slice(intersection.length) // Add the part of the previous word that doesn't intersect to the current value
      })) + '\n' + output : output // Add the last level of recursions output on to the end of this
  })(arr);
}

input.addEventListener('input', updateOutput, false);

function updateOutput() {
  var oldLength = input.value.length;
  var start = this.selectionStart;
  var end = this.selectionEnd;
  input.value = input.value.split(/ +/).join('\n');
  var newLength = input.value.length;
  input.setSelectionRange(start, end + (newLength - oldLength));
  output.value = F(input.value).trim();
}

updateOutput();
```

```
textarea {
  width: 50%;
  box-sizing: border-box;
  resize: none;
  float: left;
  height: 10em;
}

label {
  width: 50%;
  float: left;
}
```

```
<p>Type in the input box below, spaces are automatically converted to newlines and the output updates as you type</p>
<label for="input">Input</label>
<label for="output">Output</label>
<textarea id="input">
Type inside me :)
</textarea>
<textarea id="output" disabled>
</textarea>
```
> 4 votes

# Answer
# APL (Dyalog Extended), ~~13~~ 11 bytesSBCS

-2 with my extensions to Dyalog APL.

Anonymous tacit function, taking and returning a character matrix.

```
~∘' '⍤1⍢⍉⍢⊖

```

Try it online!

`~` remove
the
`' '` spaces
from
`1` rows (lit. 1D sub-arrays)
while
transposed
while
flipped
> 4 votes

# Answer
## STATA, 323 bytes

Takes input in a file called a.b Only works for up to 24 characters now. Will update later to make it work with more. Also, doesn't work in the online compiler. Requires the non-free compiler.

```
gl l=24/
forv x=1/$l{
gl a="$a str a`x' `x'"
}
infix $a using a.b
gl b=_N
forv k=1/$l{
gen b`k'=0
qui forv i=$b(-1)1{
forv j=`i'/$b{
replace b`k'=1 if _n==`j'&a`k'==""
replace a`k'=a`k'[_n-1] if _n==`j'&a`k'==""
replace a`k'="" if _n==`j'-1&b`k'[_n+1]==1
replace b`k'=0
}
}
}
forv i=1/$b{
forv k=1/$l{
di a`k'[`i'] _c
}
di
}

```

Edit: moved the quietly (to suppress output) to the loop itself from each statement in the loop, saving 8 bytes.
> 3 votes

# Answer
# R, ~~190~~ ~~178~~ 175 Bytes

Probably still some room for golfing in this. Probably a couple of unnecessary operations in there

```
l=lapply;s=substring;C=rbind;d=do.call;cat(C(d(C,l(apply(d(C,l(a<-scan(,''),s,1:(w=max(nchar(a))),1:w))[(h=length(a)):1,],2,paste0,collapse=''),s,1:h,1:h))[,h:1],'\n'),sep='')

```

Ungolfed and explained

```
a<-scan(,'')    # get STDIN
h<-length(a)    # number of lines
w=max(nchar(a)) # length of longest line
M<-lapply(a,substring,1:w,1:w)   # create a list of split strings with empty chars
M<-do.call(rbind,M)[h:1,]        # turn it into a matrix with line order reversed
M<-apply(M,1,paste0,collapse='') # paste together the columns
M<-lapply(M,substring,1:h,1:h)   # split them back up
M<-do.call(rbind,M)[,h:1]        # reform a matrix
M<-rbind(M,'\n')                 # add some carriage returns
cat(M,sep='')   # output with seperators

```

Test Run. It is interesting to note that due to the way that scan works, the whole sentence can be input with spaces and still give the output as specified.

```
> l=lapply;s=substring;C=rbind;d=do.call;cat(C(d(C,l(apply(d(C,l(a<-scan(,''),s,1:(w=max(nchar(a))),1:w))[(h=length(a)):1,],2,paste0,collapse=''),s,1:h,1:h))[,h:1],'\n'),sep='')
1: Programming
2: Puzzles
3: &
4:     Code
5: Golf
6:
Read 5 items
P
Prog
&uzz
Coderam
Golflesming
> l=lapply;s=substring;C=rbind;d=do.call;cat(C(d(C,l(apply(d(C,l(a<-scan(,''),s,1:(w=max(nchar(a))),1:w))[(h=length(a)):1,],2,paste0,collapse=''),s,1:h,1:h))[,h:1],'\n'),sep='')
1: Programming Puzzles & Code Golf beta
7:
Read 6 items
P
Prog
&uzz
Code
Golfram
betalesming
>

```
> 3 votes

# Answer
# R, 171 bytes

```
S=scan(,"");while(any((D<-diff(N<-sapply(S,nchar)))<0)){n=max(which(D<0));S[n+1]=paste0(S[n+1],substr(S[n],N[n]+D[n]+1,N[n]));S[n]=substr(S[n],1,N[n]+D[n])};cat(S,sep="\n")

```

With newlines and indentation:

```
S=scan(,"") #Takes input from stdin
while(any((D<-diff(N<-sapply(S,nchar)))<0)){
    n=max(which(D<0))
    S[n+1]=paste0(S[n+1],substr(S[n],N[n]+D[n]+1,N[n]))
    S[n]=substr(S[n],1,N[n]+D[n])
}
cat(S,sep="\n")

```

Usage:

```
> S=scan(,"");while(any((D<-diff(N<-sapply(S,nchar)))<0)){n=max(which(D<0));S[n+1]=paste0(S[n+1],substr(S[n],N[n]+D[n]+1,N[n]));S[n]=substr(S[n],1,N[n]+D[n])};cat(S,sep="\n")
1: Programming
2: Puzzles
3: &
4: Code
5: Golf
6:
Read 5 items
P
Prog
&uzz
Coderam
Golflesming

```
> 2 votes

# Answer
# Jelly, 6 bytes (non-competing)

```
ỴṚZZṚY

```

Try it online!

### How it works

The idea in the same as in my Pyth answer.

```
ỴṚZZṚY  Main link. Argument: s (string)

Ỵ       Split at linefeeds.
 Ṛ      Reverse the order of the lines.
  ZZ    Zip/transpose twice.
    Ṛ   Reverse the order of the lines.
     Y  Join, separating by linefeeds.

```
> 2 votes

# Answer
# Turtlèd, 72 bytes, noncompeting

Fairly sure I could change approach to save bytes, but later.

:p Non-golf esolang beats regular langs :p

The odd thing about Turtlèd is it was originally made after discussion about ascii art langs, but it actually seems to be best at these kinds of challenges

Turtlèd can not take newline input but for multiple inputs, and this takes only one input: terminate each word with a space, including the last one.

```
!l[*,+r_][ l]ur[*,[ -.]+.[ r{ d}u+.]-.[ -.]{ l}[ l]r[ u]_]' d[ d]u[ ' r]

```

### Try it online!

## Explanation:

```
!                          Take string input
 l                         Move left, off the asterisk at the start of grid
  [*    ]                  Until cell is *
    ,+r_       write *, string pointer+=1, move right, write * if pointed char is last char
         [ l]ur    move left until finding a space, move up and right
               [*                                        ]     Until cell is *
                 ,                               write *
                  [   ]             until cell is [space]
                    -.               decrement string pointer, write pointed char
                       +.           increment and write string pointer
                         [         ] until cell is [space]
                           r{ d}     move right, move down until finding nonspace
                                u+.  move up, string pointer+=1 and write pointed char
                                    -.      decrement string pointer and write pointed char
                                      [   ]  until cell is [space]
                                        -.  string pointer-=1 and write pointed char
                                           { l}   move left until finding nonspace
                                               [ l]   move left until finding space
                                                   r   move right
                                                    [ u]  move up until finding space
                                                        _  write * if pointed char is last char
                                                          (if it is written, loop ends)

                                                          ' d[ d]u[ ' r] just cleanup

```
> 2 votes

# Answer
## Perl, 133 bytes

This was one of those challenges that changed in my head from being too hard, to being easy, to being a lot more code than I'd anticipated... I'm not particularly happy with the approach, I'm sure there's a much better way to reduce the `print pop@F...` bit perhaps using `-n` or just pure regex, but I can't get there right now... Originally I was using `say`, but I think I'd have to score that higher (`use 5.01`) because of `$'`.

```
@F=(/.+/g,@F)for<>;$_%=$#F,($x=length$F[$_++])<length$F[$_]&&($F[$_]=~/.{$x}/,$F[$_-1].=$',$F[$_]=$&)for 0..1e2;print pop@F,$/while@F

```

### Usage

Save as `vertically-collapse-text.pl`.

```
perl vertically-collapse-text.pl <<< 'Programming
Puzzles
&
Code
Golf'
P
Prog
&uzz
Coderam
Golflesming

```
> 2 votes

# Answer
# SmileBASIC, 90 bytes

```
X=RND(50)Y=RND(20)G=CHKCHR(X,Y+1)<33LOCATE X,Y+G?CHR$(CHKCHR(X,Y));
LOCATE X,Y?" "*G
EXEC.

```

Applies gravity to all text in the console. I'm not sure if this is valid, or if I have to use a string array.
> 2 votes

# Answer
# Ruby, ~~99~~ 82 bytes

Getting there...

```
f=->a,i=-1{a.map{|l|i+=1;(0...l.size).map{|c|a.map{|x|x[c]}.join[~i]}*''}.reverse}

```

An attempted explanation:

```
f=->a,i=-1{a.map{|l|i+=1; # For each line `l` with index `i` in string array `a`
(0...l.size).map{|c|        # For each column `c` in `l`
a.map{|x|x[c]}.join           # Make a string of non-nil characters `c` across `a`...
[~i]                          # ...and grap the `i`th character *from the end*, if any
}*''}.reverse}              # Join the characters grabbed from each column and reverse the result

```

Run it like this:

```
a = %w[
  Programming
  Puzzles
  &
  Code
  Golf
]
puts f[a]

```
> 1 votes

# Answer
# K, 30

```
{+{(-#x)$x@&~^x}'+x@\:!|/#:'x}

```

.

```
k){+{(-#x)$x@&~^x}'+x@\:!|/#:'x}("Programming";"Puzzles";,"&";"Code";"Golf")
"P          "
"Prog       "
"&uzz       "
"Coderam    "
"Golflesming"

```

Explanation

`x@\:!|/#:'x` extends each string to create a square char matrix.

```
k){x@\:!|/#:'x}("Programming";"Puzzles";,"&";"Code";"Golf")
"Programming"
"Puzzles    "
"&          "
"Code       "
"Golf       "

```

`+` transposes it

```
k){+x@\:!|/#:'x}("Programming";"Puzzles";,"&";"Code";"Golf")
"PP&CG"
"ru oo"
"oz dl"
"gz ef"
"rl   "
"ae   "
"ms   "
"m    "
"i    "
"n    "
"g    "

```

`{(-#x)$x@&~^x}` will remove any spaces from a string and then pad the string by its original length

```
k){(-#x)$x@&~^x}"a  b  c   de  f"
"         abcdef"

```

Apply that function to each of the transposed strings, then flip the output to get the result

```
k){+{(-#x)$x@&~^x}'+x@\:!|/#:'x}("Programming";"Puzzles";,"&";"Code";"Golf")
"P          "
"Prog       "
"&uzz       "
"Coderam    "
"Golflesming"

```
> 1 votes

# Answer
# pb \- 310 bytes

```
^w[B!0]{w[B=32]{vb[1]^b[0]}>}b[1]vb[1]>b[2]<[X]w[B!2]{t[T+B]b[0]>}b[0]v[T]w[X!-1]{b[1]<}b[1]vb[1]w[B!0]{w[B!0]{^w[B!0]{>}<<<<^[Y+1]w[B!0]{<}>t[B]b[0]w[B!1]{v}v<[X]w[B!0]{>}b[T]}b[0]vb[1]^w[X!0]{<vb[1]^t[B]b[0]^w[B!0]{^}b[T]w[B!0]{v}}vw[B!0]{^^w[B!0]{>}<b[0]vvw[B=0]{<}b[0]<[X]}^^>w[B=0]{vb[1]}v<<}>>^b[0]^<b[0]

```

What a disaster. I barely remember anything about how it works.

Because of the way pb's input works (a single line all at once), you have to use spaces instead of newlines in the input. If the interpreter wasn't garbage and you could include newlines in the input, the only change would be the `[B=32]` at the beginning becoming `[B=10]`.

I'm working on an update to pbi (the interpreter) that will clean up the visuals if you want to watch the program run. It still needs a lot of work but in the mean time, you can watch this program on YouTube.
> 1 votes

# Answer
# J, 17 bytes

```
-.&' '"1&.(|:@|.)

```

Quite pleasant solution.

Explanation:

```
-.&' '"1&.(|:@|.)  input: list of strings y
              |.   reverse lines
           |:@     then transpose
-.&' '"1           remove blanks from columns
        &.         and undo the inside
           |:@|.   (that is, transpose and reverse again.)

```

## Test case explained

```
   s
Programming
Puzzles
&
Code
Golf
   |.s
Golf
Code
&
Puzzles
Programming
   |:|.s
GC&PP
oo ur
ld zo
fe zg
   lr
   ea
   sm
    m
    i
    n
    g
   -.&' '"1|:|.s
GC&PP
oour
ldzo
fezg
lr
ea
sm
m
i
n
g
   |.-.&' '"1|:|.s
g
n
i
m
sm
ea
lr
fezg
ldzo
oour
GC&PP
   |.|:-.&' '"1|:|.s
P
Prog
&uzz
Coderam
Golflesming
   (-.&' '"1)&.(|:@|.)s
P
Prog
&uzz
Coderam
Golflesming
   -.&' '"1&.(|:@|.)s
P
Prog
&uzz
Coderam
Golflesming

```

## Test cases

```
   f =: -.&' '"1&.(|:@|.)
   f
-.&' '"1&.(|:@|.)
   f >'Programming';'Puzzles';'&';'Code';'Golf'
P
Prog
&uzz
Coderam
Golflesming
   g =: [: > [: <;._1 '|'&,
   g 'Programming|Puzzles|&|Code|Golf'
Programming
Puzzles
&
Code
Golf
   f g 'Programming|Puzzles|&|Code|Golf'
P
Prog
&uzz
Coderam
Golflesming
   F =: f @ g
   F &. > 'Programming|Puzzles|&|Code|Golf' ; '1|23|456|7890' ; '1234|567|89|0'
+-----------+----+----+
|P          |1   |1   |
|Prog       |23  |52  |
|&uzz       |456 |863 |
|Coderam    |7890|0974|
|Golflesming|    |    |
+-----------+----+----+

```
> 1 votes

# Answer
## Racket 312 bytes

```
(let((lr list-ref)(ls list-set)(sl string-length)(ss substring)(l(string-split s)))(let p((ch #f))
(for((i(-(length l)1)))(define s(lr l i))(define r(lr l(+ 1 i)))(define n(sl s))(define m(sl r))
(when(> n m)(set! l(ls l i(ss s 0 m)))(set! l(ls l(+ 1 i)(string-append r(ss s m n))))(set! ch #t)))(if ch(p #f)l)))

```

Ungolfed:

```
(define (f s)
  (let ((lr list-ref)
        (ls list-set)
        (sl string-length)
        (ss substring)
        (l (string-split s)))
    (let loop ((changed #f))
      (for ((i (sub1 (length l))))
        (define s (lr l i))
        (define r (lr l (add1 i)))
        (define n (sl s))
        (define m (sl r))
        (when (> n m)
          (set! l (ls l i (ss s 0 m)))
          (set! l (ls l (add1 i)(string-append r (ss s m n))))
          (set! changed #t)))
      (if changed (loop #f)
          l))))

```

Testing:

```
(f "Programming Puzzles & Code Golf")

```

Output:

```
'("P" "Prog" "&uzz" "Coderam" "Golflesming")

```
> 1 votes

# Answer
# Actually, 13 bytes

This uses the algorithm described in Dennis' Jelly answer. Input and output are both lists of strings. Unfortunately, the builtin transpose function does not work very well if the inner lists or strings aren't all the same length, which would kind of defeat the point of vertically collapsing in the first place. Golfing suggestions welcome. Try it online!

```
R2`;i(lZ♂Σ`nR

```

**Ungolfing**

```
          Implicit input s.
R         Reverse s.
2`...`n   Run the following function twice.
  ;i        Duplicate and flatten onto the stack.
  (l        Get the number of strings in the list.
  Z         Zip len strings together, which results in a list of lists of characters.
  ♂Σ        Sum each list of characters, which essentially joins them together.
           This function essentially transposes
R         Reverse the result.
          Implicit return.

```
> 1 votes

# Answer
# JavaScript (ES6), 103 bytes

```
v=>(v=v.split`
`).map(_=>v=v.map((x,i)=>v[++i]?x.slice(0,n=v[i].length,v[i]+=x.slice(n)):x))&&v.join`
`

```

Split on CR, outer map ensures we loop enough times to allow "gravity" to drop letters as far as they need to drop.

Inner map first checks if there is a next line, if so, and it is shorter, drop the overflow to the next line. i.e if the 1st line has "ABCD" and the 2nd line has "FG", drop the "CD" from 1st line to the 2nd so that the 1st line becomes "AB" and the 2nd becomes "FGCD".

As we do this as many times as there are lines, the letters drop as far as they should, leaving us with the desired outcome.
> 1 votes

# Answer
# Japt, 8 bytes

```
y kS ù y

```

Try it online!

### How it works

```
Uy kS ù y

Uy  Transpose at newline
kS  Replace spaces with nothing
ù   Left-pad to fit the longest line
y   Transpose at newline

```

There's also `z` which rotates the 2D string by a multiple of 90 degrees, but it somehow truncates the string when `height > length`.
> 1 votes

# Answer
# R, ~~s81~~ 52 bytes

```
function(x)apply(x,2,function(.).[order(!is.na(.))])

#old,longer version did the same but less efficiently
#function(x)apply(x,2,function(x){n<-na.omit(x);c(rep("",length(x)-length(n)),n)}))

```

I took some liberty in interpreting the question and presumed that the text is represented in a matrix with one character per cell, thus:

```
x <- as.matrix(read.fwf(textConnection("Programming
Puzzles
&
Code
Golf"), widths=rep(1, 11)))

```

So x becomes:

```
     V1  V2  V3  V4  V5  V6  V7  V8  V9  V10 V11
[1,] "P" "r" "o" "g" "r" "a" "m" "m" "i" "n" "g"
[2,] "P" "u" "z" "z" "l" "e" "s" NA  NA  NA  NA
[3,] "&" NA  NA  NA  NA  NA  NA  NA  NA  NA  NA
[4,] "C" "o" "d" "e" NA  NA  NA  NA  NA  NA  NA
[5,] "G" "o" "l" "f" NA  NA  NA  NA  NA  NA  NA

```

Now I use `order` and `[` to sort the columns so that the NA's come first and then all other values:

```
     V1  V2  V3  V4  V5  V6  V7  V8  V9  V10 V11
[1,] "P" NA  NA  NA  NA  NA  NA  NA  NA  NA  NA
[2,] "P" "r" "o" "g" NA  NA  NA  NA  NA  NA  NA
[3,] "&" "u" "z" "z" NA  NA  NA  NA  NA  NA  NA
[4,] "C" "o" "d" "e" "r" "a" "m" NA  NA  NA  NA
[5,] "G" "o" "l" "f" "l" "e" "s" "m" "i" "n" "g"

```

It becomes longer if it is required that the output be words:

```
s <- (function(x)apply(x,2,function(.).[order(!is.na(.))]))(x)
s[is.na(s)]<-""
apply(s, 1, paste, collapse="")
# [1] "P"           "Prog"        "&uzz"        "Coderam"     "Golflesming"

```
> 1 votes

# Answer
# 05AB1E, ~~10~~ 9 bytes

```
¶¡RζðмζR»

```

Try it online.

or with alternative start:

```
.BRøðмζR»

```

Try it online.

Similar approach as @Dennis♦' Pyth answer.
-1 byte thanks to *@Emigna* replacing `ðõ:` with `ðм`.

**Explanation:**

```
¶¡       # Split on new-lines
  R      # Reverse the list
   ζ     # Zip/Transpose with unequal-length items (with space filler by default)
ðм       # Remove all spaces
  ζ      # Zip/Transpose unequal-length items (with space filler) again
   R     # Reverse the list again
    »    # Join the list by newlines, and output implicitly

```

**Alternative explanation:**

```
.B      # Box (implicitly splits on new-lines and appends spaces)
   ø    # Zip/Transpose with equal-length items
        # Rest is the same

```
> 1 votes

# Answer
# R, ~~196~~ ~~189~~ 170 bytes

```
function(x){l=nchar;o=function(y)which(diff(l(y))<0)[1];d=function(x,i)"[<-"(x,i:(j<-i+1),c(a<-substr(x[i],1,l(x[j])),sub(a,x[j],x[i])));while(!is.na(o(x)))x=d(x,o(x));x}

```

A human-readable version:

```
f<-function(x){
  l=nchar;

  # find the first line in x that is longer than the next line
  # if no such line exists o(x) will be NA
  o = function(y) which(diff(l(y))<0)[1]

  # d(x,i) --> clips the line i in x, adding the remainder to x[i+1]
  d = function(x,i) "[<-"(x,i:(j<-i+1),
        c(a<-substr(x[i],1,l(x[j])), sub(a,x[j],x[i])))
         # a --> clipped x[i],      sub(a,x[j],x[i]) --> expanded x[j]

  while(!is.na(o(x)))x=d(x,o(x));x
}

```

How it works:

1. Take the first "bad" line, i.e., line which is longer than the next line, take the "extra" part and add it to the next line
2. Check if there are any "bad" lines left, if yes go to #1

(Or in other words, "superfluous" parts fall down until everything that can fall down has fallen down.)

Input: a character vector.

```
x<-readLines(textConnection("Programming\nPuzzles\n&\nCode\nGolf"))
f(x)
# [1] "P"           "Prog"        "&uzz"        "Coderam"     "Golflesming"

```
> 1 votes

# Answer
# Vyxal, 6 bytes

```
□Ṙ∩∩Ṙ⁋

```

Try it Online!

Uses the same idea as Pyth answer

# Explanation:

```
□      Input as a list separated by newlines
 Ṙ     Reverse
  ∩    Transpose rows and columns
   ∩   Same as above
    Ṙ  Reverse
     ⁋ Join by newlines
Implicit output the result

```
> 1 votes

# Answer
# Julia 0.6, 141 bytes

```
l=length
g(z,i)=(n=z[i];m=z[i+1];(N,M)=l.([n,m]);z[i:i+1]=[n[1:min(N,M)],m*n[M+1:N]])
f(s,w=split(s),d=1:l(w)-1)=(g.([w],[d d]);join(w,"\n"))

```

Try it online!

Broadcasting with `g.([w], [d d])` allows me to get rid of any map statement and saves me around 7 bytes.
> 0 votes

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


title: For xor Young (15+)

text:
# Question
Title: For xor Young (15+)
A Young diagram is a rectangular binary mask whose every row and every column are sorted in descending order.

It is easy to check that every rectangular binary mask can be formed by xor-ing together a finite number of Young diagrams.

This decomposition is by no means unique, but there will be a minimum number of Young diagrams required. Your task in this code golf challenge is given a number \\$k\\$ and an \\$m\\$-by-\\$n\\$ binary mask \\$b\\$ determine whether \\$b\\$ can be represented as xor of \\$k\\$ \\$m\\$-by-\\$n\\$ Young diagrams.

Example xor decompositions: These are minimal and can be used as test cases: Just take the leftmost pattern. The minimum number of Young diagrams is written just below it. If you take the pattern together with a smaller number you get a falsy test case and a truthy one otherwise. Your code needn't output the decomposition. It is typically not unique anyway.

```
1001        1000   1110   1111   1111   1111
0010   <-   0000   1100   1110   1111   1111
1001        0000   0000   1000   1110   1111
5

0010        1100   1110
0110   <-   1000   1110
1100        0000   1100
2

1001        1000   1100   1100   1110   1111
0100   <-   0000   1000   1100   1110   1110
1010        0000   0000   1000   1100   1110
5

1010        1000   1100   1110   1111   1111
1011   <-   0000   0000   1000   1100   1111
0010        0000   0000   0000   1100   1110
5

00111110        11000000   11110000   11110000   11111110   11111111   11111111
11101001   <-   00000000   11100000   11110000   11111000   11111110   11111111
00110111        00000000   00000000   11000000   11110000   11111000   11111111
6

10111010        10000000   11000000   11100000   11100000   11111000   11111100   11111110   11111111   11111111
10010111   <-   00000000   00000000   10000000   11100000   11110000   11111000   11111110   11111110   11111111
11100101        00000000   00000000   00000000   00000000   11100000   11111000   11111100   11111110   11111111
9

11100110        11100000   11110000   11110000   11111000   11111110   11111111   11111111
00110110   <-   00000000   11000000   11110000   11111000   11111110   11111111   11111111
00100001        00000000   00000000   00000000   11000000   11100000   11111110   11111111
7

10110011        10000000   11000000   11110000   11111000   11111000   11111100   11111111   11111111   11111111
00111100   <-   00000000   00000000   00000000   11000000   11111000   11111000   11111100   11111111   11111111
01110101        00000000   00000000   00000000   10000000   11110000   11111000   11111100   11111110   11111111
9

10110        10000   11000   11110   11111   11111
01111        00000   10000   11110   11110   11111
11101   <-   00000   00000   11100   11110   11111
10000        00000   00000   10000   11110   11110
00110        00000   00000   00000   11000   11110
5

00101        11000   11100   11110   11111   11111   11111
10010        00000   10000   11100   11110   11111   11111
10010   <-   00000   10000   11100   11110   11111   11111
10101        00000   10000   11000   11100   11110   11111
11011        00000   00000   00000   11000   11100   11111
6

0111101        1000000   1110000   1110000   1111100   1111110   1111111   1111111   1111111
1101000        0000000   1100000   1110000   1111000   1111100   1111100   1111111   1111111
1001100   <-   0000000   0000000   0000000   1000000   1110000   1111100   1111111   1111111
0000001        0000000   0000000   0000000   0000000   1110000   1110000   1111110   1111111
0110010        0000000   0000000   0000000   0000000   1000000   1110000   1111100   1111110
8

0001010        1000000   1000000   1110000   1111000   1111100   1111110   1111111   1111111
1000011        0000000   1000000   1100000   1100000   1111000   1111000   1111100   1111111
0100011   <-   0000000   0000000   1000000   1100000   1111000   1111000   1111100   1111111
1011010        0000000   0000000   0000000   1000000   1100000   1111000   1111100   1111110
1111110        0000000   0000000   0000000   0000000   0000000   0000000   0000000   1111110
8

011000101        100000000   111000000   111111000   111111100   111111110   111111110   111111110   111111111
000100001        000000000   000000000   111000000   111100000   111111110   111111110   111111110   111111111
111100111   <-   000000000   000000000   000000000   111100000   111111000   111111110   111111110   111111111
111100001        000000000   000000000   000000000   000000000   000000000   111100000   111111110   111111111
110000000        000000000   000000000   000000000   000000000   000000000   000000000   000000000   110000000
8

001100011        110000000   111100000   111110000   111110000   111111100   111111110   111111110   111111111   111111111   111111111
000110101        110000000   110000000   111000000   111110000   111111000   111111100   111111110   111111111   111111111   111111111
011011100   <-   100000000   110000000   110000000   111000000   111100000   111111000   111111000   111111100   111111111   111111111
100000001        000000000   100000000   110000000   110000000   111100000   111100000   111111000   111111000   111111110   111111111
110101001        000000000   000000000   000000000   110000000   111000000   111100000   111110000   111111000   111111110   111111111
10

```

Standard rules apply.

# Answer
# Python with numpy, ~~94~~ 93 bytes

```
from numpy import*
S=cumsum
f=lambda k,m:f(k-1,flip(S(S(flip(m),0),1)>0)^m)if k else any(m)<1

```

Attempt This Online!

Takes a sequence of sequences of `int`s.

---

This uses a greedy algorithm.

Let A be the smallest Young diagram that contains the input (that is, has 1s where the input has 1s). I claim that A is part of an optimal solution.

Observe that the AND of two Young diagrams is a Young diagram, and the OR of two Young diagrams is a Young diagram.

Firstly, any solution can be converted to a solution that lies within A by ANDing each diagram with A.

Next, if the solution is X,Y,Z, we can replace X and Y with X|Y and X&Y without changing the overall XOR. Apply the same process to X|Y and Z next, to obtain a solution that includes X|Y|Z; this necessarily contains A, and thus is equal to A. (A similar repeating process works on solutions of any size.)

---

After `flip` reverses the input, `cumsum` in each direction spreads positiveness forwards, then `>0` reduces the entries back to Booleans. `flip` again to return to the original orientation, then apply the XOR.
> 6 votes

# Answer
# Charcoal, 36 bytes

```
ＮθＷＳ⊞υＩ⪪⮌ι¹ＦθＵＭυＥκ⁻⌈Ｅ✂υλＬυ¹⌈…ξ⊕νμ⌈⌈υ

```

Try it online! Link is to verbose version of code. Takes input as `k` and then the binary mask represented as a list of newline-terminated strings, and outputs `-` if `k` was too small, nothing if `k` was sufficient. Explanation: Uses a greedy algorithm.

```
Ｎθ

```

Input `k`.

```
ＷＳ⊞υＩ⪪⮌ι¹

```

Convert the newline-terminated list of strings into a binary matrix, although flip it horizontally because that saves a byte.

```
Ｆθ

```

Loop `k` times.

```
ＵＭυＥκ⁻⌈Ｅ✂υλＬυ¹⌈…ξ⊕νμ

```

Flip only those bits in the array that have a `1` bit in the rectangle whose original corners are the bit and the bottom right corner of the array. The array of the bits that were flipped is itself a Young diagram and the result of the flip is the same as the XOR of that diagram with the array.

```
⌈⌈υ

```

If `k` was sufficient, then the array will be all `0`s, so its double maximum will also be `0`, but if it was insufficient, then the maximum row will contain a `1`, so the double maximum will also be `1`. This is then output in unary as a count of `-`s.

Example:

```
0010
0110
1100

```

All the `1`s get flipped because obviously any rectangle containing them contains a `1`, but the `0`s above and left also get flipped because there is a `1` in the rectangle from them to the bottom right corner. The Young matrix of bits that get flipped is therefore as follows:

```
1110
1110
1100

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 55 bytes

**-27 bytes thanks to @att.**

```
r/@r@#-#&~Nest~##==0#&
r=#@*FoldList[BitOr]@*#&@Reverse

```

Try it online!

---

## Wolfram Language (Mathematica), 82 bytes

```
If[#==0#,0,1+#0[#~BitXor~Map[Reverse@FoldList[BitOr,Reverse@#]&,#,{0,1}]]]&@#<=#2&

```

Try it online!

Or shorter if I can just take the matrix and output the minimum number \\$k\\$.

```
If[#==0#,0,1+#0[#~BitXor~Map[Reverse@FoldList[BitOr,Reverse@#]&,#,{0,1}]]]&

```

Try it online!
> 2 votes

# Answer
# Pyth, 39 bytes

```
Lm|MCd._CbWss=QmxMCdC,Q__Myy__MQ=hZ;>EZ

```

Try it online!

A port of @m90's answer, be sure to upvote them.
> 1 votes

# Answer
# Jelly, 25 bytes

```
ZLr0œċL⁸ḣ"ⱮFE$ƇḢ!^µÐ¡§§0e

```

A full program that accepts a rectangular list of lists of ones and zeros and a non-negative integer and prints `1` if possible or `0` if not.

**Try it online!**

This test-suite alters the code so it is callable as a dyadic Link (by replacing the `µ` with a newline and `Ç⁹`) and calls the link starting with `0` until a truthy result is found for each of the grids and returns the values reached. Note that going any higher is guaranteed to give a truthy result due to the implementation (repeatedly applying an operation and collecting up).

### How?

Greedily inverts the Young "cut-out" that contains all of the same elements with the maximal row-length array. Performs this \\$N\\$ times and then checks for the existence of an array with no ones.

```
ZLr0œċL⁸ḣ"ⱮFE$ƇḢ!^µÐ¡§§0e - Main Link: grid of 1s and 0s, G (n rows, m columns)
                   Ð¡     - repeat and collect (starting with G)...
                          - ...times: (implicit) second program argument, N
                  µ       - ...action: the monadic chain to the left - f(Current):
Z                         -   transpose (Current)
 L                        -   length
  r0                      -   inclusive range to 0 -> [m,...,2,1,0]
      L                   -   length (Current) -> n
    œċ                    -   combinations with replacement
                              -> [[m,m,m],...,[m,m,1],[m,m,0],[m,m-1,m-1],...,[0,0,0]]
       ⁸                  -   chain's left argument -> Current
          Ɱ               -   map with:
         "                -     zip with:
        ḣ                 -       head to
                              -> Young-style "cut-outs" reverse sorted by row-lengths
              Ƈ           -   keep those for which:
             $            -     last two links as a monad:
           F              -       flatten
            E             -       all equal?
               Ḣ          -   head
                !         -   factorial (vectorises) -> converts all 0s to 1s
                 ^        -   XOR (Current)
                     §    - sums
                      §   - sums
                       0  - zero
                        e - exists in?

```
> 1 votes

# Answer
# Python \+ NumPy, 82 bytes

```
from numpy import*
f=lambda k,m:~k<0<all(~m)|f(k-1,triu(m@m.T<2)@m@tril(m[0]<2)^m)

```

Attempt This Online!

As @m90 doesn't seem to want my golfs and I don't want to let them go to waste I post them here.

This takes the input mask as a boolean array.

#### How?

It uses that a cumsum can be written as multiplication with a triangular matrix. By choosing upper or lower triangles we can choose whether to sum from left to right or from right to left.

Also, note that matrix multiplication preserves the type, bool in this case, so we needn't restore any larger values to 1.

Also worthwhile noting that NumPy bools behave differently to Python bools w.r.t. to `~`.
> 1 votes

---
Tags: code-golf, decision-problem, binary-matrix
---


title: Optimal strategy for wandering robots

text:
# Question
Title: Optimal strategy for wandering robots
If the agent is at the origin it always moves right when you choose it.

The goal is to get one agent to 10.

The cost is the sum of the square of the total number of moves (left or right) taken by each individual agent until the first agent gets to 10. You want to minimise the expected cost

Once you have fixed a strategy you should run your code ten thousand times (each time up to the point where the first agent gets to 10) and report the average cost.

# Input and output

There is no input to this challenge. Your code need only output the mean cost over ~~10000~~ 100,000 runs as specified. However please do include an explanation of your strategy for choosing which agent to move when.

In short, the cost of moving a particular agent effectively increases each time you move it. This is a result of the scoring system. As another example, if you move agent 1 twice for your first two moves and it ends up back at the origin, it is now cheaper to move any other agent.

If two answers have the same strategy then the first answer wins. If two different strategies give similar mean costs then they should be rerun with ~~100,000~~ a million (or even more) iterations to see which is better.

A very simple strategy gives a mean cost of 6369. So the first hurdle is to do better than that.

# Winners

This question was first brilliantly solved optimally by Anders Kaseorg.

# Answer
> 9 votes
# Ruby, modified minimum product, average cost ~4950

```
f=->a,b{(0..3).min_by{|q|(9-a[q])**3*b[q]}}

```

Try it online!

Always select the agent that minimizes `(9-position)^3*(number of moves)`:

* On the first round, every agent makes a move.
* By using `9-a` instead of `10-a`, any agent in position 9 will try to move on the next iteration.
* Position seems to be more important than the cost projection, so after trying out different values, I found out that the third power is the best way to represent it.

The easiest strategy (round-robin) has a cost of about 7000.

If I let it run in a continuous loop, after a while the average stabilizes around 4950.

# Answer
> 8 votes
# Rust, cost = 4928.296960314256

Computed exactly (modulo floating point imprecision) with a non-random algorithm, but also measured as \\$4923.8 ± 2.6\\$ (\\$1σ\\$ confidence) with \\$10^7\\$ random runs of the actual game as a check.

### Strategy

Consider the following equivalent but wetter version of the game. There’s a tower of cells \\$(p, m)\\$ with eleven columns \\$0 ≤ p ≤ 10\\$ and infinitely many rows \\$m ≥ 0\\$ going downwards. We’ll call the first ten columns \\$p = 0, \dotsc, 9\\$ “live” and the last column \\$p = 10\\$ “dead”. Each live cell has a plugged drain in the floor, connected by equal-width pipes to its diagonal neighbors below. We start with \\$1\\$ liter of water in \\$(0, 0)\\$, with \\$4\\$ grains of sand floating in the water. Our goal is to control the plugs until one of the grains ends up in the dead column, while minimizing the expected sum of the squared row numbers of the grains at that time.

The reason to formulate the game like this is that our strategy does not need to look at the grains. Instead, we’re going to open the plugs in some fixed order, letting the grains float where they may, until 100% of the water flows into the dead column in the limit as all of the plugs are open. (We’re very good at opening plugs.)

I’ll explain in a moment how to decide which order we’ll use, but to motivate that, I first need to explain how to evaluate our expected score. Define “time \\$t\\$” to be the time when \\$t\\$ liters of water have flowed into the dead column. Then, because the grains of sand flow equivalently to water molecules, the distribution of time quadruples \\$(t\_1, \dotsc, t\_4)\\$ when the four grains enter the dead column is just the uniform distribution over \\$\[0, 1\]^4\\$. Therefore, the time \\$t\_\min = \min \\{t\_1, \dotsc, t\_4\\}\\$ when the score should be evaluated has a beta distribution \\$t\_\min \sim \mathrm{Beta}(1, 4)\\$, whose PDF is \\$4(1 - t)^3\\$.

Let \\$q\_{(p, m)}(t)\\$ be the amount of water in cell \\$(p, m)\\$ at time \\$t\\$; let \\$c\_{(p, m)}(t) = m^2q\_{(p, m)}(t)\\$ be its weighted cost, and \\$c\_{\textrm{live}}(t)\\$ (resp. \\$c\_{\textrm{dead}}(t)\\$) the sum over all live (resp. dead) cells. Then we can write our expected score as

\begin{split} &\int\_0^1 4(1 - t)^3 \left(3\frac{c\_{\textrm{live}}(t)}{1 - t} + c'\_{\textrm{dead}}(t)\right)\\,dt \\ &= \int\_0^1 12(1 - t)^2 c\_{\textrm{live}}(t)\\,dt + \int\_0^1 4(1 - t)^3 c'\_{\textrm{dead}}(t)\\,dt \\ &= \Bigl\[-4(1 - t)^3 c\_{\textrm{live}}(t)\Bigr\]\_0^1 - \int\_0^1 -4(1 - t)^3 c'\_{\textrm{live}}(t)\\,dt + \int\_0^1 4(1 - t)^3 c'\_{\textrm{dead}}(t)\\,dt \\ &= \int\_0^1 4(1 - t)^3 (c'\_{\textrm{live}}(t) + c'\_{\textrm{dead}}(t))\\,dt. \end{split}

Therefore, we see that our goal at each step is to minimize the total growth rate of the weighted cost of *all* cells (\\$c'\_{\textrm{live}}(t) + c'\_{\textrm{dead}}(t)\\$), relative to the rate of flow into the dead column (i.e. growth of \\$t\\$ itself). \\$4(1 - t)^3\\$ is decreasing, so we prefer to have smaller ratios earlier. This makes our strategy obvious: at each step, we’ll open the plug that minimizes this ratio, wait until all water has flowed out of that cell, and leave it open while proceeding to the following cells.

Since \\$c'\_{\textrm{live}}(t) + c'\_{\textrm{dead}}(t)\\$ is piecewise constant, the integral evaluates to an (infinite) sum, one that converges much more quickly than the Monte Carlo simulation. That’s how I determined the precise answer above.

### Code

Build and run with `cargo run --release`.

**`Cargo.toml`**

```
[package]
name = "wandering"
version = "0.1.0"
edition = "2021"

[dependencies]
rand = "0.8.5"

```

**`src/main.rs`**

```
use rand::prelude::*;
use rand::rngs::StdRng;
use std::collections::HashMap;

#[derive(Default, Debug)]
struct Rate {
    dead: f64,
    cost: f64,
    live: HashMap<(u32, u32), f64>,
}

fn add(map: &mut HashMap<(u32, u32), f64>, state: (u32, u32), value: f64) {
    if value != 0.0 {
        *map.entry(state).or_insert(0.0) += value;
    }
}

struct SortingHat {
    distribution: HashMap<(u32, u32), f64>,
    moves_frontier: [u32; 10],
    rates: HashMap<(u32, u32), Rate>,
    orders: HashMap<(u32, u32), usize>,
}

impl Default for SortingHat {
    fn default() -> SortingHat {
        let mut distribution = HashMap::new();
        distribution.insert((0, 0), 1.0);
        SortingHat {
            distribution,
            moves_frontier: [0_u32, 1, 2, 3, 4, 5, 6, 7, 8, 9],
            rates: HashMap::new(),
            orders: HashMap::new(),
        }
    }
}

impl SortingHat {
    fn get_order(&mut self, query_position: u32, query_moves: u32) -> usize {
        if let Some(&order) = self.orders.get(&(query_position, query_moves)) {
            return order;
        }

        loop {
            let (_, position, moves) = (0_u32..10)
                .zip(&self.moves_frontier)
                .filter(|&(position, &moves)| {
                    position + 1 == 10 || self.moves_frontier[position as usize + 1] > moves + 1
                })
                .map(|(position, &moves)| {
                    let mut cost = 0.0;
                    let mut dead = 0.0;
                    for new_position in [position.abs_diff(1), position + 1] {
                        cost += moves as f64 + 1. / 2.;
                        if new_position == 10 {
                            dead += 1. / 2.;
                        } else if let Some(new_rate) = self.rates.get(&(new_position, moves + 1)) {
                            dead += new_rate.dead / 2.;
                            cost += new_rate.cost / 2.;
                        }
                    }
                    (cost / dead, position, moves)
                })
                .min_by(|a, b| a.partial_cmp(&b).unwrap())
                .unwrap();

            self.orders.insert((position, moves), self.orders.len());

            let mut rate = Rate::default();
            for new_position in [position.abs_diff(1), position + 1] {
                rate.cost += moves as f64 + 1. / 2.;
                if new_position == 10 {
                    rate.dead += 1. / 2.;
                } else if let Some(new_rate) = self.rates.get(&(new_position, moves + 1)) {
                    rate.dead += new_rate.dead / 2.;
                    rate.cost += new_rate.cost / 2.;
                    for (&newer_state, live_rate) in &new_rate.live {
                        add(&mut rate.live, newer_state, live_rate / 2.);
                    }
                } else {
                    add(&mut rate.live, (new_position, moves + 1), 1. / 2.);
                }
            }

            if let Some(mass) = self.distribution.remove(&(position, moves)) {
                for (&new_state, live_rate) in &rate.live {
                    add(&mut self.distribution, new_state, live_rate * mass);
                }
            }

            for old_rate in self.rates.values_mut() {
                if let Some(live_rate) = old_rate.live.remove(&(position, moves)) {
                    old_rate.dead += rate.dead * live_rate;
                    old_rate.cost += rate.cost * live_rate;
                    for (&new_state, new_live_rate) in &rate.live {
                        *old_rate.live.entry(new_state).or_insert(0.0) += new_live_rate * live_rate;
                    }
                }
            }

            self.rates.remove(&(position + 1, moves + 1));
            self.rates.insert((position, moves), rate);
            self.moves_frontier[position as usize] += 2;

            if (position, moves) == (query_position, query_moves) {
                return self.orders.len() - 1;
            }
        }
    }

    fn strategy(&mut self, positions: &[u32; 4], num_moves: &[u32; 4]) -> usize {
        (0..4)
            .min_by_key(|&agent| self.get_order(positions[agent], num_moves[agent]))
            .unwrap()
    }
}

fn test(mut rng: impl Rng, mut strategy: impl FnMut(&[u32; 4], &[u32; 4]) -> usize, runs: u32) {
    let mut count = 0;
    let mut mean = 0.0;
    let mut m2 = 0.0;
    let mut mean_stdev = f64::NAN;

    for _ in 0..runs {
        let mut positions = [0; 4];
        let mut num_moves = [0; 4];
        loop {
            let agent = strategy(&positions, &num_moves);
            if positions[agent] == 0 || rng.gen() {
                positions[agent] += 1;
            } else {
                positions[agent] -= 1;
            }
            num_moves[agent] += 1;
            if positions[agent] == 10 {
                break;
            }
        }
        let sample: f64 = num_moves.into_iter().map(|m| (m as f64).powi(2)).sum();

        count += 1;
        let delta = sample - mean;
        mean += delta / count as f64;
        m2 += delta * delta * (1. - 1. / count as f64);
        mean_stdev = (m2 / (count as f64 * (count - 1) as f64)).sqrt();
        if count % 100 == 0 {
            eprint!("\r\x1b[K{count}: {mean} ± {mean_stdev}");
        }
    }
    eprint!("\r\x1b[K");
    println!("{count}: {mean} ± {mean_stdev}");
}

fn main() {
    let rng = StdRng::seed_from_u64(0);
    let mut sorting_hat = SortingHat::default();
    test(
        rng,
        |positions, num_moves| sorting_hat.strategy(positions, num_moves),
        10000000,
    )
}

```

# Answer
> 6 votes
# Python 3 (PyPy), 4957.6 +/- 2.6 (10M trials)

```
def expco(positions, num_moves,depth=0) -> float:
    if depth==0:
        return min((10**2 - positions[i] ** 2)
            * (5 * 10**2 - positions[i] ** 2 + 6 * num_moves[i] - 2)/3 for i in range(4))
    return (10 not in positions)and min(
       expco([abs(p-(i==j)) for j,p in enumerate(positions)],
             [m+(i==j) for j,m in enumerate(num_moves)],depth-1)/2 +
       expco([p+(i==j) for j,p in enumerate(positions)],
             [m+(i==j) for j,m in enumerate(num_moves)],depth-1)/2 +
       num_moves[i]*2+1 for i in range(4))
def strategy(positions, num_moves, depth=1) -> int:
    return min(range(4), key = lambda i:
       expco([abs(p-(i==j)) for j,p in enumerate(positions)],
             [m+(i==j) for j,m in enumerate(num_moves)],depth)/2 +
       expco([p+(i==j) for j,p in enumerate(positions)],
             [m+(i==j) for j,m in enumerate(num_moves)],depth)/2 +
       num_moves[i]*2+1)

```

Try it online!

This is a simple brute force search on top of @Anders Kaseorg's formula (and code).

The score given was obtained with search depth 1, i.e. for each agent compute the expected cost if we can switch agents once immediately after the first move and take the best.

Apologies for the messy code.

# Answer
> 5 votes
# Python 3, cost ≈ 5034.3 ± 2.7

\\$1σ\\$ confidence, evaluated with \\$10^7\\$ runs.

```
def strategy(positions, num_moves):
    return min(
        range(4),
        key=lambda i: (10**2 - positions[i] ** 2)
        * (5 * 10**2 - positions[i] ** 2 + 6 * num_moves[i] - 2),
    )

```

Try it online! (\\$10^5\\$ runs)

### How it works

If we were to pick one agent at position \\$p\\$ that’s previously moved \\$m\\$ times, and use it for the rest of the game, the expected additional cost would be exactly

$$f(p, m) = \frac13(10^2 - p^2)(5⋅10^2 - p^2 + 6m - 2).$$

(You can verify that

$$m^2 + f(p, m) = (m + 1)^2 + \frac12(f(\lvert p - 1\rvert, m + 1) + f(p + 1, m + 1))$$

and \\$f(10, m) = 0\\$.)

At each step, we pick the agent that minimizes this quantity. (We don’t restrict ourselves to using it for the rest of the game.)

# Answer
> 4 votes
# 5050? ± 26.64

```
def strategy(positions, num_moves):
  E = [100, 99, 96, 91, 84, 75, 64, 51, 36, 19]
  _, n = min(((E[p] + m) ** 2 - m ** 2, i) for p, m, i in zip(positions, num_moves, range(4)))
  return n

```

Try it online!

Use minimal \\$\left(E(P\_i)+M\_i\right)^2-M\_i^2\\$, where \\$E(X)\\$ is a pre-calculated array $$\left\[E(0),\dots,E(9)\right\]=\left\[100, 99, 96, 91, 84, 75, 64, 51, 36, 19\right\]$$

generated by following codes

```
syms E0 E1 E2 E3 E4 E5 E6 E7 E8 E9 EA
solve([E0-E1-1, E1-(E0+E2)/2-1, E2-(E1+E3)/2-1, E3-(E2+E4)/2-1, E4-(E3+E5)/2-1, E5-(E4+E6)/2-1, E6-(E5+E7)/2-1, E7-(E6+E8)/2-1, E8-(E7+E9)/2-1, E9-(E8+EA)/2-1, EA])

```

Try it online!

The driver code is used from other posts.

# Answer
> 4 votes
# Python 3, cost ≈ 4928.4 ± 1

I believe this is essentially optimal. Thank you to @usul for the inspiration.

```
import functools

f = lambda p, m: (1. / 3) * (100 - p * p) * (500 - p * p + 6 * m - 2)

@functools.lru_cache(None)
def gittins_value(p, m, l):
    if m >= 400:
        return f(p, m)
    if p == 0:
        v_next = gittins_value(p + 1, m + 1, l)
    else:
        v_next = 0.5 * gittins_value(p - 1, m + 1, l)
        if p != 9:
            v_next += 0.5 * gittins_value(p + 1, m + 1, l)
    return min((2 * m + 1) + v_next, l)

@functools.lru_cache(None)
def gittins_index(p, m):
    low = 2 * m + 1
    high = f(p, m)
    while True:
        mid = 0.5 * (low + high)
        v = gittins_value(p, m, mid)
        if v < mid:
            high = mid
        else:
            low = mid
        if abs(high - low) <= 1e-6:
            break
    return 0.5 * (low + high)

def strategy(p, m):
    indices = [gittins_index(p_i, m_i) for p_i, m_i in zip(p, m)]
    return indices.index(min(indices))

```

# Answer
> 3 votes
# R / Rcpp: 5006 ± 7.31, or 4932 ± 3.63

Score computed by taking the average of 20 million simulated games. Bounds are a 95% bootstrap confidence interval with 10,000 iterations.

Thanks to Anders Kaseorg for pointing out a typo in my code that caused the solution to accidentally be optimal. Reader, may all your future bugs behave thusly. The following description explains the 5006 solution with a note for how to get the 4932 solution.

## Strategy:

Let's consider a simplified version of the environment in order to construct a risk heuristic. We'd like to be able to treat `n` consecutive movements of an agent as independent, but that won't be true if the agent ever reaches position 0 or 10 during those movements.

Suppose instead that each of the number lines is infinite in both directions, and that the probability of moving right is always 0.5 (even at position 0). In this simplified case, if we move a single agent `n` consecutive times, we may treat the resulting `k` number of movements to the right as binomially distributed.

At each step, let `n = 10 - x`, where `x` is the agent's position on the number line. Since the agent's movements are independent in the simplified environment, we can calculate the probability that the agent has moved backwards given `k` moves to the right as

$$Prob = 1 - \sum\_{k=\lceil \frac{n}{2} \rceil}^n \dbinom n k \cdot 0.5^k \cdot (1-0.5)^{n-k}$$

Note: If you incorrectly move the one-minus inside the sum, the solution becomes near optimal for reasons that are unclear.

Let the cost function be the increase in cost accrued by moving the agent `n` times:

$$ Cost = (x + n)^2 - (x)^2 $$

Then define the risk of moving an agent as

$$ Risk = Prob \cdot Cost $$

and at each step move the agent with the lowest risk.

## Intuition:

The idea is to calculate the risk that over the minimum number of steps an agent would need to reach the goal, the agent ends up moving backwards instead of forwards, i.e. We try to maximize the chance that the chosen agent will move closer to the goal. Minimizing this risk heuristic appears to perform fairly well even though the method does not take into account the effect of the order of the movements, nor the effect of reaching the zero position.

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

//* Initialize Environment
// [[Rcpp::export]]
NumericMatrix initEnv() {
  return(NumericMatrix (4, 2));
}

//* Update Environment
// [[Rcpp::export]]
NumericMatrix updateEnv(NumericMatrix x, int a) {

  //Update move counter
  x(a, 1) = x(a, 1) + 1;

  //Update position
  if(x(a, 0) == 0){
    x(a, 0) = 1;
  } else {
    RNGScope scope;
    NumericVector r = Rcpp::runif(1, 0.0, 1.0);
    if(r[0] <= 0.5){
      x(a, 0) = x(a, 0) - 1;
    } else {
      x(a, 0) = x(a, 0) + 1;
    }
  }

  //Return
  return(x);

}

//* Calculate Loss
// [[Rcpp::export]]
double envCost(NumericMatrix x) {
  double lambda = 0;
  for(int i = 0; i < 4; i++){
    lambda = lambda + pow(x(i, 1), 2);
  }
  return(lambda);
}

//* Calculate Risk
// [[Rcpp::export]]
double agentRisk(NumericMatrix x, int a) {

  //Parameters
  int pos = x(a, 0);
  int n = 10 - pos;

  //Calculate risk correctly
  double prob = 0;
  double cost = pow(x(a, 1) + n, 2) - pow(x(a, 1), 2);
  for(int k = ceil(n / 2); k <= n; k++){
    prob = prob + (Rf_choose(n, k) * pow(0.5, k) * pow(0.5, n - k));
  }
  prob = 1 - prob;

  //Calculate risk with typo
  //double prob = 0;
  //double cost = pow(x(a, 1) + n, 2) - pow(x(a, 1), 2);
  //for(int k = ceil(n / 2); k <= n; k++){
  //  prob = prob + (1 - Rf_choose(n, k) * pow(0.5, k) * pow(0.5, n - k));
  //}

  //Return
  return(prob * cost);

}

//* Simulate Game
// [[Rcpp::export]]
List simGame() {

  //Generate environment
  NumericMatrix en = initEnv();

  //Complete game
  bool done = false;
  while(!done){

    //Parameters
    int a = 0;
    double lambda = agentRisk(en, 0);

    //Calculate risks and choose action
    for(int i = 1; i < 4; i++){
      double lambda_new = agentRisk(en, i);
      if(lambda_new < lambda){
        a = i;
        lambda = lambda_new;
      }
    }

    //Update game
    en = updateEnv(en, a);

    //Check victory conditions
    for(int i = 0; i < 4; i++){
      if(en(i, 0) >= 10){
        done = true;
        break;
      }
    }

  }

  //Return
  return(
    List::create(
      Named("state") = en,
      Named("cost") = envCost(en)
    )
  );

}

```

# Answer
> 2 votes
# Rust, cost = ~5032 (1M iterations)

```
const depth: usize = 1200;
const iterations: usize = 1_000_000;

lazy_static! {
    static ref EXPECTED_SCORES: [[usize; 10]; depth] = {
        let mut expected_scores = [[1_000_000usize; 10]; depth];

        for i in (0..depth-1).rev() {
            for j in 0..10 {
                if j == 0 {
                    expected_scores[i][j] = expected_scores[i + 1][j + 1].saturating_add(2 * i + 1);
                } else if j == 9 {
                    expected_scores[i][j] =
                        (expected_scores[i + 1][j - 1] / 2).saturating_add(2 * i + 1);
                } else {
                    expected_scores[i][j] = (expected_scores[i + 1][j + 1]/ 2)
                    .saturating_add(expected_scores[i + 1][j - 1] / 2)
                    .saturating_add(2 * i + 1);
                }
            }
        }

        expected_scores
    };
}

#[derive(Copy, Clone, Eq, PartialEq, Debug)]
struct Agent {
    position: u8,
    actions: u32,
}

fn strategy(agents: [Agent; 4]) -> usize {
    return (0..4)
        .min_by_key(|i| EXPECTED_SCORES[(agents[*i].actions as usize).min(depth - 1)][agents[*i].position as usize])
        .unwrap();
}

```

Basically pre-computes a table of expected scores then uses that.

Playground link Need to reduce iterations if you don't want it to time out.

# Answer
> 2 votes
# Python 3 (PyPy), 5027.1 ± 8.3

```
def strategy(positions, num_moves) -> int:
    return min(
        range(4),
        key=lambda i: (10 - positions[i] + 2*num_moves[i]) * (10 - positions[i]),
    )

```

Try it online!

Copies the function/testing template from Anders Keorg's answer.

Chooses the agent with the minimal best-case cost \\$(10-\mathit{position}+\mathit{moves})^2-\mathit{moves}^2=(10-\mathit{position}+2\mathit{moves})(10-\mathit{position})\\$.

# Answer
> 2 votes
# C++: ~4953 (100 million iterations)

```
#include <bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) { return uniform_int_distribution<int>(a, b)(rng);}

int main() {
    const int NRIT = 100'000'000;
    auto go = [&] {
        int l[4] = { 10,10,10,10 }, t[4] = {}, sol = 0;
        auto cost = [&](int nr) {return l[nr] * (4 * t[nr] * l[nr] + 6); };
        while (1) {
            pair<int, int> best = { INT_MAX, -1 };
            for (int i = 0; i < 4; ++i)
                best = min(best, { cost(i), i });
            int opt = best.second;
            sol += 2 * t[opt]++ + 1;
            if (l[opt] == 10)
                --l[opt];
            else {
                if (rand(0,1))
                    --l[opt];
                else
                    ++l[opt];
            }
            if (!l[opt])
                return sol;
        }
    };
    long long total = 0;
    for (int i = 0; i < NRIT; ++i)
        total += go();
    cout << (double)(total) / NRIT;

}

```

I misread the question at first and thought it had a 1/2 chance to move backwards or stay still. This chooses the agent with the least expected cost to finish, according to my calculations and the (wrong) assumption it can't go backwards.

\\$ \text{cost} = (10-p)(4 \cdot (10-p) \cdot m+6)\\$

I want to add 10 000 iterations is definitely not enough, I could cherrypick 10k iterations to get 4790, which is far from the real average. Standardised testing also encounters the issue of different number generators, which can actually make a small difference (it did from my testing).

# Answer
> 2 votes
# Python: ~4973

**TL;DR** By Gittins theory, there is an optimal solution of the following form, but it has some complicated replacement for `approx_grades` and this is a heuristic.

```
import random,numpy

def approx_grade(x,n):
  if x <= 0:
    return 2*n+1 + approx_grade(1, n+1)
  else:
    return 2**(10-x) * (9 - x) + (2**(11-x) -2)*(2*n + 1)

def sim(num_players):
  xs = [0]*num_players
  ns = [0]*num_players
  grades = [approx_grade(0,0)]*num_players
  while True:
    i = numpy.argmin(grades)  # STRATEGY HERE
    ns[i] += 1
    if xs[i] == 0:
      xs[i] = 1
    elif random.random() <= 0.5:
      xs[i] += 1
      if xs[i] == 10:
        return sum([n*n for n in ns])
    else:
      xs[i] -= 1
    grades[i] = approx_grade(xs[i], ns[i])

T = 100000
scores = [sim(4) for t in range(T)]
print(numpy.mean(scores))

```

This is a special case of the Gittins index theorem, and there is a very nice exposition of essentially this game in the 2003 paper *On Playing Golf with Two Balls*\[1\]

\[1\] https://epubs.siam.org/doi/abs/10.1137/S0895480102408341

Notice we can rephrase the cost as: when we move an agent that has taken n steps so far, we pay 2n+1 immediately, and the total cost at the end is the sum of all payments made along the way. Note 2n+1 = (n+1)^2 - n^2.

The key point is that for any given agent i and state of the agent (i.e. location x\[i\] and number of steps so far n\[i\]), there is an **index** or "grade" we can give the agent that perfectly captures how desirable it is to choose that agent next. The optimal strategy is to pick the agent with the best grade. **One agent's grade does not depend on the others' states!**

The grade is the following number. Imagine we had a fifth agent with the ability to magically teleport to the end for a cost g. And imagine we are playing the game with only agent i and the magic agent. If g is very small, we will just choose the magic agent. But if g is large, we will take a risk and play agent i, see what happens, and then decide whether to use the magic agent or play agent i again.

There is some magic number g(x\[i\],n\[i\]) where we are indifferent between the magic agent and i. That number is the grade.

---

Now, in theory the grade is polynomial-time computable, but it's pretty complex. So I used the following approximation: suppose the optimal strategy in the magic game is to keep trying agent i as long as they move right, but as soon as they move left, pay g to stop. Then the index for step 9 would satisfy

$$ g(9,n) = 2n + 1 + \frac{1}{2}g(9,n) . $$

The left side is if we pay g(9,n) for the magic agent to halt immediately, and the right side is if we pay 2n+1 to advance agent i: with probability half we terminate and pay nothing, and with probability half we go left, at which point we pay g(9,n) to stop.

This solves to g(9,n) = 4n+2.

Similarly, at location 8, we should be indifferent between paying g(8,n) to stop, or paying 2n+1 to get a half chance to go left -- when we pay g(8,n) to stop -- and a half chance to go right -- when we repeat the game at step 9.

$$ g(8,n) = 2n+1 + \frac{1}{2} g(8,n) + \frac{1}{2}\left(2(n+1)+1 + \frac{1}{2}g(8,n)\right) . $$

If we repeat this logic, we get an approximation to the grade which is

$$ g(x,n) = 2^{10-x}(9-x) + (2^{11-x}-2)(2n+1) . $$

After dealing with the special case of x=0, I get this code. Apparently it's still pretty suboptimal as another answer gets ~4927.

---

Note: I used multiprocessing to run 8 million total reps in 36min on a laptop, and got an average of just under 4973. I also reimplemented in C++ with probably hundreds of millions of reps and it seemed to converge to about 4974.5. But the quality of the RNG and precision arithmetic matters! C's built in rand() gave basically nonsense.

# Answer
> 0 votes
# R / Rcpp: 4937 ± 4.22

Average of 15 million simulated games. Bounds are a 95% bootstrap confidence interval with 15,000 iterations.

As a supplement to the wonderful Gittins index answers, I wanted to show an empirical method that produces the same result. This solution predicts which robot to move using a neural net that's been trained by a genetic algorithm.

## Strategy:

In order to optimally move our robots across the number lines, we need to determine a function that maps each robot's state information to a value that represents our decision to move it. This is called an action-value function. For simplicity, let's choose to always move the robot with the highest action-value.

At this point we could use the Gittins index as our action-value, but let's empirically estimate an action-value function instead.

### Estimating the Action-Value Function

I decided to use a neural net (NN) to approximate the action-value function. The NN is fully connected with two hidden layers, each having ten neurons. Weights are initialized using the He method, and biases are initialized uniformly on \\$\[-1,1\]\\$. The activation functions are all rectified linear units (ReLU), except the activation function for the output, which is a ReLU clamped to \\$\[0, 1\]\\$.

Neural nets often have better performance when the inputs are symmetrically distributed and on the interval \\$\[-1, 1\]\\$, but in this problem the input state information of a robot is its current position on the interval \\$\[0 .. 9\]\\$ and the number of times it has been moved on the interval \\$\[0 .. \infty)\\$.

I transformed the position of the robot to the \\$\[-1, 1\]\\$ interval by shifting and scaling.

To transform the total number of moves I first simulated 10 million games in which I always moved the same robot. This gave a distribution for the total number of moves, which I used to estimate an upper bound. The distribution of the total number of moves is heavily right skewed, so I applied a log transform to reduce skew, and then normalized the result using the log of my estimated upper bound in order to arrive at the \\$\[-1, 1\]\\$ interval for total number of moves. Note: Because the total number of moves can be zero, I added one to the total number of moves before taking the log.

### Training the Neural Net

In reinforcement learning there are a number of well-established methods for training neural nets that predict action-values, but I have decided to completely ignore them because I've been having a lot of fun with genetic algorithms recently. There's no fun like gradient-free fun.

The genetic algorithm that I used updated NN weights and biases, but not the NN architecture itself. The initial population was 225 chromosomes, and fitness for each chromosome was calculated by evaluating its corresponding action-value function over 7500 games.

It is often desirable for neural net weights and biases to be relatively small and for the model's learned representation to be distributed across the neurons. To achieve this, I added batch normalization to the hidden layers of the neural nets. Regularizing the models in this way greatly improved performance and helped to ensure that the mutation function continued to be effective late in training by keeping the weights and biases close to the mutation function's generating distributions.

The batch normalization's \\$\gamma\\$ and \\$\beta\\$ parameters were also updated by the genetic algorithm.

## Learned Action-Values:

This graph shows the final neural net's predicted action-values for robots in the most commonly traversed subset of the state space. Note: Because these estimated action-values are not with reference to any rewards, they only have meaning with respect to each other. I have arbitrarily scaled them to be between zero and one.

## Code:

**R Code to Generate Policy**

```
# Parameters
iters <- 100
popNum <- 225
layers <- c(10, 10)
neval <- 7500
mutRate <- 0.001

# Evolve
population <- generatePopulation(popNum, layers, neval)
out <- rep(NA, iters)
for(i in 1:iters){

  # Evaluate population fitness
  fitness = evaluatePopulation(population, neval)
  out[i] = mean(fitness)

  # Keep track of best policy so far
  minFit = fitness[length(fitness)]
  if(min(fitness) <= minFit){
    minFit = min(fitness)
    minPolicy = population[[which.min(fitness)]]
  }

  # Selection
  cutoff = quantile(fitness, 0.5)
  population = population[fitness <= cutoff]

  # Crossover
  offspringNum = (popNum - length(population))
  offspring = lapply(1:offspringNum, function(i){
    inds = sample(1:length(population), 2, FALSE)
    crossover(population[[ inds[1] ]], population[[ inds[2] ]])
  })
  population = c(population, offspring)

  # Mutate
  population = lapply(1:length(population), function(i){
    mutate(population[[i]], rate = mutRate)
  })

  # Elitism
  eliteInds = c(round(0.99 * popNum):popNum)
  population[eliteInds] = lapply(eliteInds, function(i){minPolicy})

}

```

**R Code Helper Functions**

```
#' Evaluate Population
#' @export
evaluatePopulation <- function(population, neval){
  sapply(population, function(x){
    return(mean(evaluatePolicy(x, neval)))
  })
}

#' Generate Random Population
#' @export
generatePopulation <- function(size, layers, neval, maxCost = Inf){

  # Population
  population = list()

  # Increase yield
  while(TRUE){

    # Generate seed population
    out = lapply(1:size, function(i){
      generateChromosome(layers)
    })

    # Calculate fitness
    fitness = evaluatePopulation(out, neval)
    fitness[fitness > maxCost] = NA
    inds = order(fitness)
    out = out[inds]
    fitness = fitness[inds]

    # Seed population
    population = c(population, out[!is.na(fitness)])

    # Report
    if(length(population) >= size){
      population = population[1:size]
      break
    } else {
      message(paste0("Found: ", length(population)))
    }

  }

  # Return
  return(population)

}

```

**Rcpp Code for Genetic Algorithm**

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

//* Initialize Environment
// [[Rcpp::export]]
NumericMatrix initEnv() {
  return(NumericMatrix (4, 2));
}

//* Update Environment
// [[Rcpp::export]]
NumericMatrix updateEnv(
    NumericMatrix env,
    int a
) {

  //Increase movement count
  env(a, 1) += 1;

  //Move robot
  if(env(a, 0) == 0){
    env(a, 0) = 1;
  } else {
    NumericVector r = Rcpp::runif(1, 0.0, 1.0);
    if(r[0] >= 0.5){
      env(a, 0) += 1;
    } else {
      env(a, 0) -= 1;
    }
  }

  //Return
  return(env);

}

//* Calculate Total Cost
// [[Rcpp::export]]
double envCost(NumericMatrix env) {
  double lambda = 0;
  for(int i = 0; i < env.nrow(); i++){
    lambda += pow(env(i, 1), 2);
  }
  return(lambda);
}

//* Generate Chromosome
// [[Rcpp::export]]
List generateChromosome(
  IntegerVector layers
) {

  //Create container for the NN matrices
  List chrom;

  //Create weight and bias matrices for each layer
  for(int i = 0; i < layers.length() + 1; i++){

    //Determine matrix dimensions
    int inputNum;
    int outputNum;
    if(i == 0){
      inputNum = 2;
      outputNum = layers[i];
    } else if(i == layers.length()){
      inputNum = layers[i - 1];
      outputNum = 1;
    } else {
      inputNum = layers[i - 1];
      outputNum = layers[i];
    }

    //Initialize weights and biases
    NumericVector wtList = Rcpp::rnorm(outputNum * inputNum, 0.0, sqrt(0.5 * inputNum));
    NumericVector biList = Rcpp::runif(outputNum, -1.0, 1.0);
    NumericMatrix wt (outputNum, inputNum, wtList.begin());
    NumericMatrix bi (outputNum, 1, biList.begin());

    //Record
    List chLayer = List::create(
      Named("wt") = wt,
      Named("bi") = bi
    );
    chrom.push_back(chLayer);

  }

  //Initialize batch normalization matrix
  NumericMatrix batch (layers.length(), 2);
  NumericVector batchVals = Rcpp::rnorm(batch.size(), 0.0, 1.0);
  for(int i = 0; i < batch.size(); i++){
    batch[i] = batchVals[i];
  }

  //Return
  List out = List::create(
    Named("layers") = layers,
    Named("chrom") = chrom,
    Named("batch") = batch
  );
  return(out);

}

//* Crossover
// [[Rcpp::export]]
List crossover(
    List x,
    List y,
    double rate = -1,
    double scale = -1
) {

  //Set parameters
  NumericVector probs = Rcpp::runif(2, 0.0, 1.0);
  if(rate >= 0){
    probs[0] = rate;
  }
  if(scale >= 0){
    probs[1] = scale;
  }

  //Crossover the NN
  List out = clone(x);

  //Access the components
  List chrom = out["chrom"];
  List xChrom = x["chrom"];
  List yChrom = y["chrom"];

  //Crossover weights and biases
  for(int i = 0; i < chrom.length(); i++){

    //Reference the layer
    List chLayer = chrom[i];
    List xLayer = xChrom[i];
    List yLayer = yChrom[i];

    //Access the matrices
    NumericMatrix wt = chLayer["wt"];
    NumericMatrix bi = chLayer["bi"];
    NumericMatrix xWt = xLayer["wt"];
    NumericMatrix xBi = xLayer["bi"];
    NumericMatrix yWt = yLayer["wt"];
    NumericMatrix yBi = yLayer["bi"];

    //Crossover
    LogicalVector doCross_wt = (Rcpp::runif(wt.size(), 0.0, 1.0) < probs[0]);
    LogicalVector doCross_bi = (Rcpp::runif(bi.size(), 0.0, 1.0) < probs[0]);
    for(int j = 0; j < wt.size(); j++){
      if(doCross_wt[j]){
        wt[j] = probs[1] * (xWt[j] - yWt[j]) + xWt[j];
      }
    }
    for(int j = 0; j < bi.size(); j++){
      if(doCross_bi[j]){
        bi[j] = probs[1] * (xBi[j] - yBi[j]) + xBi[j];
      }
    }

  }

  //Crossover gamma and beta
  NumericMatrix batch = out["batch"];
  NumericMatrix xBatch = x["batch"];
  NumericMatrix yBatch = y["batch"];
  LogicalVector doCross_yb = (Rcpp::runif(batch.size(), 0.0, 1.0) < probs[0]);
  for(int i = 0; i < batch.size(); i++){
    if(doCross_yb[i]){
      batch[i] = probs[1] * (xBatch[i] - yBatch[i]) + xBatch[i];
    }
  }

  //Return
  return(out);

}

//* Mutate
// [[Rcpp::export]]
List mutate(
    List x,
    double rate = -1
) {

  //Set parameters
  NumericVector probs = Rcpp::runif(1, 0.0, 1.0);
  if(rate >= 0){
    probs[0] = rate;
  }

  //Access components
  List out = clone(x);
  List chrom = out["chrom"];

  //Mutate weights and biases
  for(int i = 0; i < chrom.length(); i++){

    //Access the weights and biases
    List chLayer = chrom[i];
    NumericMatrix wt = chLayer["wt"];
    NumericMatrix bi = chLayer["bi"];

    //Mutate
    int numInputs = wt.ncol();
    LogicalVector doMut_wt = (Rcpp::runif(wt.size(), 0.0, 1.0) <= probs[0]);
    LogicalVector doMut_bi = (Rcpp::runif(bi.size(), 0.0, 1.0) <= probs[0]);
    for(int j = 0; j < wt.size(); j++){
      if(doMut_wt[j]){
        wt[j] = Rcpp::rnorm(1, 0.0, sqrt(0.5 * numInputs))[0];
      }
    }
    for(int j = 0; j < bi.size(); j++){
      if(doMut_bi[j]){
        bi[j] = Rcpp::runif(1, -1.0, 1.0)[0];
      }
    }

  }

  //Mutate gamma and beta
  NumericMatrix batch = out["batch"];
  LogicalVector doMut_yb = (Rcpp::runif(batch.size(), 0.0, 1.0) <= probs[0]);
  for(int i = 0; i < batch.size(); i++){
    if(doMut_yb[i]){
      batch[i] = Rcpp::rnorm(1, 0.0, 1.0)[0];
    }
  }

  //Return
  return(out);

}

//* Neural Net Prediction
//*
//* Environment:
//* env[0] = Position
//* env[1] = Total moves
//*
// [[Rcpp::export]]
NumericVector predictNN(
    NumericVector env,
    List chromosome
) {

  //Initialize the output
  NumericVector pred (1);

  //Process environment
  //Normalizing to be in [-1, 1]
  NumericVector vIn (2);
  vIn[0] = (env[0] / 5 - 1);
  vIn[1] = 2 * (log(env[1] + 1) / log(2000)) - 1;

  //Compute NN outputs
  List chrom = chromosome["chrom"];
  NumericMatrix batch = chromosome["batch"];
  for(int i = 0; i < chrom.length(); i++){

    //Access the layer
    List chLayer = chrom[i];
    NumericMatrix wt = chLayer["wt"];
    NumericMatrix bi = chLayer["bi"];

    //Calculate activation
    NumericVector vOut (wt.nrow());
    for(int j = 0; j < wt.nrow(); j++){
      NumericVector wtVec = wt(j, _);
      NumericVector biVec = bi(j, _);
      NumericVector act = {sum(wtVec * vIn) + biVec};
      vOut[j] = act[0];
    }

    //Apply batch normalization
    if(vOut.size() > 1){
      vOut = (vOut - mean(vOut)) / sd(vOut);
      vOut = batch(i, 0) * vOut + batch(i, 1);
    }

    //Apply ReLU
    for(int j = 0; j < vOut.length(); j++){
      NumericVector relu = {0.0, vOut[j]};
      vOut[j] = max(relu);
    }

    //Copy
    vIn = clone(vOut);

  }

  //Record
  pred[0] = vIn[0];

  //Return
  return(Rcpp::clamp(0.0, pred, 1.0));

}

//* NN Prediction to Action
// [[Rcpp::export]]
int predToResponse(NumericVector pred){

  //Calculate response
  double maxPred = max(pred);
  IntegerVector response;
  for(int i = 0; i < 4; i++){
    if(pred[i] >= maxPred){
      response.push_back(i);
    }
  }
  int action = Rcpp::sample(response, 1)[0];

  //Return
  return(action);

}

//* Evaluate Chromosome
// [[Rcpp::export]]
NumericVector evaluatePolicy(
    List chromosome,
    int iters
) {

  //Initialize parameters
  NumericVector out (iters);
  NumericVector pred (4);

  //Run episodes
  for(int i = 0; i < iters; i++){

    //Episode parameters
    NumericMatrix env = initEnv();

    //Complete episode
    bool done = false;
    while(!done){

      //Update state
      for(int j = 0; j < 4; j++){
        NumericVector state = env(j, _);
        pred[j] = predictNN(state, chromosome)[0];
      }
      int a = predToResponse(pred);
      env = updateEnv(env, a);

      //Check victory condition
      for(int j = 0; j < 4; j++){
        if(env(j, 0) >= 10){
          out[i] = envCost(env);
          done = true;
          break;
        }
      }

    }

  }

  //Return
  return(out);

}

```

---
Tags: code-challenge
---


# Question
Title: Check if a string is entirely made of the same substring
This is taken from this question (with permission ofcourse). I'll quote:

> Create a function which takes a string, and it should return true or false based on whether the input consists of ***only*** a repeated character sequence. The length of given string is always greater than 1 and the character sequence must have at least one repetition.

Some examples:

```
'aa' //true
'aaa' //true
'abcabcabc' //true
'aba' //false
'ababa' //false
'weqweqweqweqweqw' // false

```

Specifically, the check for a string strictly composed of repeating substrings (**Update**) can output any true or false representation, but no error output please. Strictly alphhanumeric strings. Otherwise standard code golf rules. This is Code Golf, so shortest answer in bytes for each language wins.

# Answer
# Brachylog, ~~4~~ 3 bytes

```
ġ=Ṁ

```

Try it online!

## Explanation

```
ġ=Ṁ    Implicit input, say "abcabc"
ġ      Split into chunks of equal lengths (except maybe the last one): ["abc","abc"]
 =     Apply the constraint that all of the chunks are equal,
  Ṁ    and that there are multiple of them.

```

The program prints `true.` if the constraints can be satisfied, and `false.` if not.
> 13 votes

# Answer
# JavaScript (ES6), 22 bytes

Returns a Boolean value.

```
s=>/^(.*)\1+$/.test(s)

```

Try it online!

---

# Without a regular expression,  ~~33~~  29 bytes

Returns either `null` (falsy) or an object (truthy).

```
s=>(s+s).slice(1,-1).match(s)

```

Try it online!

NB: Technically, \\$s\\$ is converted to a regular expression for *match()*, so the above title is a lie.
> 20 votes

# Answer
# grep, 19

```
grep -qxE '(.+)\1+'

```

### Test

```
while read; do
  <<<"$REPLY" grep -qxE '(.+)\1+' && t="true" || t="false"
  echo "$REPLY: $t"
done < infile

```

Output:

```
aa: true
aaa: true
abcabcabc: true
aba: false
ababa: false
weqweqweqweqweqw: false

```
> 10 votes

# Answer
# Japt, 6 bytes

```
²é ¤øU

```

Saved one byte thanks to @Shaggy

Try it online!

```
        Implicit input, stored in variable 'U'
²       U+U, "abcabc" -> "abcabcabcabc"
 é      Rotate 1 char to the right "abcabcabcabc" -> "cabcabcabcab"
   ¤    Remove first two chars, "cabcabcabcab" -> "bcabcabcab"
    øU  Check if U is in the above

```
> 9 votes

# Answer
# Java, ~~25~~ 24 bytes

-1 byte thanks to Olivier Grégoire!
Boring regex answer

```
s->s.matches("(.+)\\1+")

```

Try it online!
~~*It's just 1 byte longer than the python answer aaaaa*~~ I'm tied now :)
> 9 votes

# Answer
# Excel, 26 bytes

```
=FIND(A1,A1&A1,2)<=LEN(A1)

```

Inputs from A1, outputs to whatever cell you put this formula.
> 7 votes

# Answer
# , 28 bytes

```
grepl("(.+)\\1+$",scan(,''))

```

Try it online!

Simple Regex version. R is (sometimes) very similar to Python, so this is similar to TFeld's Python 2 regex answer, albeit shorter!

### Question (if anyone knows the answer)

I am still confused why this works, as the substring can be any length and will always work, and still works when I add a letter to the front of a valid string, like "cABABABABAB". If I personally read the regex, I see `(.+)`, which captures any group of any length. And then `\\1+$` which repeats the captured group any number of times until the end.

So why doesn't it capture just "AB" and find that it is repeated until the end of the string, especially since there is no restriction specified as to where the substring can start?
> 7 votes

# Answer
# Retina 0.8.2, 9 bytes

```
^(.+)\1+$

```

Try it online! Link includes test cases.
> 6 votes

# Answer
# Jelly,  ~~5~~  4 bytes

I see now that the optimal way is to follow xnor's method!

```
Ḋ;Ṗw

```

A monadic Link that accepts a list of characters and outputs an integer - the shortest possible length of a repeating slice or zero if none exists. Note that zero is falsey while non-zero numbers are truthy in Jelly.

**Try it online!**

### How?

```
Ḋ;Ṗw - Link: list of characters, S   e.g. "abcabcabc"   or "abababa"
Ḋ    - dequeue S                           "bcabcabc"       "bababa"
  Ṗ  - pop from S                         "abcabcab"       "ababab"
 ;   - concatenate                "bcabcabcabcabcab"       "bababaababab"
   w - first index of sublist     3  ^---here!             0  (not found)

```
> 6 votes

# Answer
# Python 2, 24 bytes

```
lambda s:s in(s*2)[1:-1]

```

Try it online!

Shamelessly stolen from xnor's answer to the original question.

---

More intuitive version:

# Python 2, ~~59~~ ~~55~~ 53 bytes

```
lambda s:s in[len(s)/i*s[:i]for i in range(1,len(s))]

```

Try it online!

---

**Boring regex version:**

# Python 2, 44 bytes

```
lambda s:re.match(r'(.+)\1+$',s)>0
import re

```

Try it online!
> 4 votes

# Answer
# Perl 5 `-p`, 14 bytes

```
$_=/^(.*)\1+$/

```

Try it online!
> 4 votes

# Answer
# , <sup>~~26 25 15~~</sup> 14 bytes

Using xnor method

```
+./@E.}:@}.@,~

```

Try it online!

## original (two different approaches)

# , 25 bytes

```
1<1#.(#%#\)=<\+/@E.&:>"{]

```

Try it online!

# , 26 bytes

```
1<1#.-@#\([:(-:##{.)<\)"{]

```

Try it online!
> 4 votes

# Answer
# Pyke, 4 bytes

```
+tO{

```

Try it here!

```
+    -    input+input
 t   -   ^[1:]
  O  -  ^[:-1]
   { - input in ^

```
> 4 votes

# Answer
# Wolfram Language (Mathematica), ~~24~~ 23 bytes

```
StringMatchQ[x__..~~x_]

```

Try it online!

```
StringMatchQ[           (*a function that checks if its input (string) matches:*)
             x__..      (*a sequence of one or more characters, repeated one or more times*)
                  ~~x_] (*and one more time*)

```
> 4 votes

# Answer
# GNU Bash, 28 bytes

```
[[ ${1:1}${1::-1} == *$1* ]]

```

Save the above script into a file, and run `bash file.sh "string to test"`.

Exit code 0 is truthy and non-zero is falsy. (as all Unix shells would interpret)
> 4 votes

# Answer
# PowerShell, ~~23~~ 24 bytes

+1 byte to fully match rules

```
"$args"-match"^(.+)\1+$"

```

Try it online!

Pretty boring. Based on the other Regex answers. Luckily PowerShell doesn't use `\` as an escape character!
> 3 votes

# Answer
# 05AB1E, 5 bytes

xnor's method from the previous question appears to be optimal in 05AB1E as well.

```
«¦¨så

```

Try it online! or as a Test Suite

**Explanation**

```
«       # append input to input
 ¦¨     # remove the first and last character of the resulting string
   så   # check if the input is in this string

```
> 3 votes

# Answer
## C# (Visual C# Interactive Compiler), 70 bytes

xnor's shameless adaptation (**46 bytes**)

```
s=>(s+s).Substring(1,s.Length*2-2).Contains(s)

```

My non Regex Solution:

```
s=>s.Select((x,y)=>y).Count(z=>s.Replace(s.Substring(0,z+1),"")=="")>1

```

Explanation:

Replace every possible substring that starts at index 0 with an empty string. If the result is an empty string, the string is entirely made of that substring. Since this includes evaluating the entire string with itself, the amount of expected results must be greater than 1.

Example: **abcabc**

Possible substrings starting at index 0:

```
'a', 'ab', 'abc', 'abca', 'abcab', 'abcabc'

```

If we replace them with empty strings

```
Substring          Result

'a'         =>     'bcbc'
'ab'        =>     'cc'
'abc'       =>     ''
'abca'      =>     'bc'
'abcab'     =>     'c'
'abcabc'    =>     ''

```

Since there is a substring other than 'abcabc' that returns an empty string, the string is entirely made of another substring ('abc')

Try it online!
> 3 votes

# Answer
# Python 3, ~~62~~ ~~60~~ ~~56~~ 54 bytes

*-4 bytes thanx to ArBo*

```
lambda s:s in(len(s)//l*s[:l]for l in range(1,len(s)))

```
1. Iterate over all possible prefixes in the string.
2. Try to build the string out of the prefix.
3. Return whether this succeeds with any prefix at all.

Try it online!
> 3 votes

# Answer
# Ruby `-n`, ~~16~~ 13 bytes

-3 bytes thanks to south

For completeness, more or less the same as the other regex answers. Prints `0` for truthy, `nil` for falsey.

```
p~/^(.+)\1+$/

```

Attempt This Online!
> 3 votes

# Answer
# Japt, 10 bytes

*Returns a positive number if truthy and 0 if falsey. If you want a bool output just add  flag*

```
å+ k@rXÃÊÉ

```

---

```
å+ k@rXÃÊÉ      Full program. Implicit input U.
                    e.g: U = "abcabcabc"
å+              Take all prefixes
                         U = ["a","ab","abc","abca","abcab","abcabc","abcabca","abcabcab","abcabcabc"]
   k@           Filter U by:
     rXÃ        Values that return false (empty string)
                when replacing each prefix in U
                e.g: ["bcbcbc","ccc","","bcabc","cabc","abc","bc","c",""]
                                take ↑                             and ↑
                     U = ["abc","abcabcabc"]
         ÊÉ     Get U length and subtract 1. Then return the result

```

Try it online!
> 2 votes

# Answer
# Husk, 6 bytes

```
Ṡ€ȯhtD

```

Try it online!

I feel like this is one byte more than optimal, but I couldn't find an arrangement that made the explicit composition `ȯ` unnecessary.

# Explanation

```
Ṡ€      Find the argument in the result of applying the following function to the argument
  ȯhtD  Duplicate the argument, then remove the first and last elements.

```
> 2 votes

# Answer
# Mathematica 11.x, 74 bytes

```
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&

```

where, throughout, `#` represents the input string, and

```
StringCases[#,<pattern>]

```

finds substrings of the input string matching the pattern

```
StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")

```

This pattern requires matches, `x`, must start at the start of the string and must satisfy the condition that (1) the match is not the whole input string and (2) if we replace occurrences of the match in the input string with the empty string we obtain the empty string. Finally, comparing the list of matches to the empty list,

```
{}!=

```

is `True` if the list of matches is nonempty and `False` if the list of matches is empty.

Test cases:

```
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["aa"]
(*  True  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["aaa"]
(*  True  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["abcabc"]
(*  True  *)

```

and

```
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["aba"]
(*  False  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["ababa"]
(*  False  *)
{}!=StringCases[#,StartOfString~~x__/;(x!=#&&StringReplace[#,x->""]=="")]&["weqweqweqweqweqw"]
(*  False  *)

```
> 2 votes

# Answer
# Python 3, 84 bytes

```
import textwrap
lambda s:any(len(set(textwrap.wrap(s,l)))<2 for l in range(1,len(s)))

```

Uses `textwrap.wrap` (thanks to this answer) to split the string into pieces of length `n` to test each possible length of repeating substring. The split pieces are then compared to each other by adding them to a set. If all of the pieces are equal, and the set is of length 1, then the string must be a repeating string. I used `<2` instead of `==1` because it saves a byte, and the length of the input string was guaranteed to be greater than zero.

If there is no `n` for which repeating substrings of length `n` make up the entire string, then return false for the whole function.
> 2 votes

# Answer
# C++ (gcc), 36 bytes

```
#define f(x)(x+x).find(x,1)<x.size()

```

Try it online!

Another port of xnor's solution. Uses a macro to expand the argument into the expression. The argument is assumed to be of type `std::string`.
> 2 votes

# Answer
# Clean, 73 bytes

*Doesn't use regex.*

```
import StdEnv,Data.List
$s=or[isPrefixOf s(cycle t)\\t<-tl(tails s)|t>[]]

```

Try it online!

Defines `$ :: [Char] -> Bool`.
Checks if the given string is a prefix of the repetition of any sub-string taken from the end.
> 2 votes

# Answer
# Zsh, 19 bytes

Outputs via error code:

```
[[ $1$1 = ?*$1*? ]]

```

Try it online!

However, the challenge did specify "output on stdout":

### Zsh, 22 bytes

Outputs an empty string if true, and a non-empty string for false:

```
<<<${${:-$1$1}/?*$1*?}

```

If the output must be fixed:

### Zsh, 25 bytes

Outputs `0` for true, `1` for false

```
[[ $1$1 = ?*$1*? ]]
<<<$?

```

Try it online!

---

The heart of these solutions is `?*$1*?`, which is a glob which matches the string in question surrounded by at least one character on each side: `*` is a string of any length, and `?` is a single character. This is an alternate version of xnor's solution, but using globs to match extra characters rather than removing leading and trailing characters.
> 2 votes

# Answer
# Vyxal `r`, ~~5~~ 4 bytes

```
dḢṪc

```

*-1 byte by porting xnor's answer from the other question*

Try it online!

Concatenates the string to itself, removes the first and last characters, then checks if the input string is in that.
> 2 votes

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

```
&/1_=':#'=:

```

Try it online!

*Thanks to PyGamer0 for the "check if all the values of a list are equal" code snippet!*

Return `1` for true and `0` for false

Explanations:

```
&/1_=':#'=:  Main function. Takes implicit input with : on the right-most
         =   Group the characters into a dictionary
       #'    Get the length in the values of each of the keys
             (The values are the occurence positions of the characters in the string)
      :      Apply everything on the left to the right
    ='       Check if the values of the values in the dictionary are equal
  1_         Weed out the first one (as we know it will always be false)
&/           Get the minimum value

```
> 2 votes

# Answer
# T-SQL, 47 bytes

Using @Xnor's method:

```
DECLARE @ varchar(max)='ababab'

PRINT sign(charindex(@,left(@+@,len(@)*2-1),2))

```

Keeping old answer as it contains some nice golfing(67 bytes):

```
DECLARE @y varchar(max)='abababa'

,@ INT=0WHILE
replace(@y,left(@y,@),'')>''SET
@+=1PRINT @/len(@y)^1

```

**Explanation:** This script is repeatingly trying to replace the input '@y' with the first '@' characters of the input '@y' with nothing, while increasing '@'.

> if you replace 'ab' in 'ababab' with nothing you have an empty string

Eventually the result will be empty. If this happens when the loop variable is equal to the length of the varchar, the criteria is false/0 because '@'=len(@y) (there was no repeating varchar).

```
iif(@=len(@y),0,1)

```

can be golfed into this

```
@/len(@y)^1

```

because the length of '@y' can not be 0 and '@' will never exceed the length @y.

**Try it online**
> 1 votes

# Answer
# QlikView Variable, 27 bytes

This should be defined as a variable, which then allows you to pass parameters, e.g. `$1` as your input value.

It returns `0` or `-1` (equivalent to QlikView's `TRUE()` function).

```
=substringcount($1&$1,$1)>2

```
> 1 votes

# Answer
# Swift, 196 bytes

```
func r(s:String)->Bool{guard let k=s.dropFirst().firstIndex(where:{$0==s.first}) else{return false};let v=s[...k].dropLast();var w=v;while s.hasPrefix(w) && s.count>=(w+v).count{w+=v};return s==w}

```

Try it online!
> 1 votes

# Answer
# Icon, 46 bytes

```
procedure f(s);return find(s,(s||s)[2:-1]);end

```

Try it online!

Another port of xnor's solution.
> 1 votes

# Answer
# K (oK), 29 bytes

```
{0<+/(1=#?:)'(0N,'1_!#x)#\:x}

```

Try it online!
> 1 votes

# Answer
# Red, 72 bytes

```
func[s][repeat i length? s[parse s[copy t i skip some t end(return 1)]]]

```

Try it online!

Returns `1` for `True`
> 1 votes

# Answer
# sed, 48

Using the more efficient algorithm described in this answer:

```
s=abcabc
<<<"$s" sed -nE 's/.*/&\n&&/; /^([^\n]+)\n..*\1.*.$/!q5' \
  && echo true \
  || echo false

```
> 1 votes

# Answer
# TI-BASIC, 14 bytes

```
length(Ans)>inString(Ans+Ans,Ans,2

```

Input is a string in `Ans`.
Output is true (1) or false (0) as requested by the challenge.

**Examples:**

```
"HELLO
HELLO
prgmCDGF17
               0
"AB
AB
prgmCDGF17
               0
"ABAB
ABAB
prgmCDGF17
               1

```

**Explanation:**

```
length(Ans)>inString(Ans+Ans,Ans,2   ;full program

            inString(                ;get the index of
                             Ans,    ; the input in
                     Ans+Ans,        ; the input concatenated with itself
                                 2   ; starting at the second character
                                     ; (returns index of concatenated piece
                                     ;  if not found elsewhere)
length(Ans)                          ;and then get the length of the input
           >                         ;is the length greater than the index?
                                     ; result is left in "Ans"
                                     ; 1 if true, 0 if false
                                     ;implicit print of "Ans"

```

---

**Note:** TI-BASIC is a tokenized language. Character count does ***not*** equal byte count.
> 1 votes

# Answer
# C (gcc), 37 bytes

```
#define f(x)strcmp(strstr(1+x x,x),x)

```

Try it online!

Yet another port of xnor's solution. Using C macros to create the concatenated string, where the macro assumes the argument is a string literal.
> 1 votes

# Answer
# Perl 6, 14 bytes

```
{?/^(.+)$0+$/}

```

Try it online!
> 1 votes

# Answer
# Swift 4.2/Xcode 10.2, ~~123~~ 84 bytes

```
(1...s.count-1).contains{s==String(repeating:String(s.prefix($0)),count:s.count/$0)}

```

Try it online!
> 1 votes

# Answer
# SmileBASIC 3, 72 bytes

Prints `1` for true and `0` for false.

```
LINPUT L$W=LEN(L$)FOR I=1TO W/2IF LEFT$(L$,I)*(W/I)==L$THEN?1STOP
NEXT?0

```

## Explained

```
LINPUT L$       'read line of input
W=LEN(L$)       'store length of input
FOR I=1 TO W/2  'loop over all prefixes
 'if this prefix repeated to length of input equals input, print 1 and stop
 IF LEFT$(L$,I)*(W/I)==L$ THEN ?1 STOP
NEXT
?0              'print 0 because check failed

```
> 1 votes

# Answer
# Perl 6, 14 bytes

```
*~~/^(.+)$0+$/

```

Or for the same amount

```
{m/^(.+)$0+$/}

```

Much the same as other answers with a simple regex. First one uses Whatever block and a smart matcher to run the regex, and the second does a match on the block input with the implied value. Both return Match objects which are truthy on success, and Nil which is falsey on fairly.

Try it online!
> 1 votes

# Answer
# Lua, 50 bytes

Another port of xnor's solution:

```
s=io.read()t=s..s print(s.find(t.sub(t,2,#t-1),s))

```

Prints indexes if true, 'nil' otherwise.

Try it online!
> 0 votes

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