# Question
Title: Output the nth rational number according to the Stern-Brocot sequence
The Stern-Brocot sequence is a Fibonnaci-like sequence which can be constructed as follows:

1. Initialise the sequence with `s(1) = s(2) = 1`
2. Set counter `n = 1`
3. Append `s(n) + s(n+1)` to the sequence
4. Append `s(n+1)` to the sequence
5. Increment `n`, return to step 3

This is equivalent to:

Amongst other properties, the Stern-Brocot sequence can be used to generate every possible positive rational number. Every rational number will be generated exactly once, and it will always appear in its simplest terms; for example, `1/3` is the 4th rational number in the sequence, but the equivalent numbers `2/6`, `3/9` etc won't appear at all.

**We can define the nth rational number as `r(n) = s(n) / s(n+1)`, where `s(n)` is the nth Stern-Brocot number, as described above.**

Your challenge is to write a program or function which will output the nth rational number generated using the Stern-Brocot sequence.

* The algorithms described above are 1-indexed; if your entry is 0-indexed, please state in your answer
* The algorithms described are for illustrative purposes only, the output can be derived in any way you like (other than hard-coding)
* Input can be via STDIN, function parameters, or any other reasonable input mechanism
* Ouptut can be to STDOUT, console, function return value, or any other reasonable output stream
* Output must be as a string in the form `a/b`, where `a` and `b` are the relevant entries in the Stern-Brocot sequence. Evaluating the fraction before output is not permissable. For example, for input `12`, output should be `2/5`, not `0.4`.
* Standard loopholes are disallowed

This is , so shortest answer in bytes will win.

**Test cases**

The test cases here are 1-indexed.

```
n    r(n)
--  ------
1    1/1
2    1/2
3    2/1
4    1/3
5    3/2
6    2/3
7    3/1
8    1/4
9    4/3
10   3/5
11   5/2
12   2/5
13   5/3
14   3/4
15   4/1
16   1/5
17   5/4
18   4/7
19   7/3
20   3/8
50   7/12
100  7/19
1000 11/39

```

OEIS entry: A002487
Excellent Numberphile video discussing the sequence: Infinite Fractions

# Answer
> 3 votes
# Jelly, 14 bytes

```
3ẋḶŒpḄċ
’Ç”/⁸Ç

```

Try it online!

Ooh, looks like I can beat the accepted answer by @Dennis, and in the same language at that. This works using a formula from OEIS: the number of ways to express (the number minus 1) in hyperbinary (i.e. binary with 0, 1, 2 as digits). Unlike most Jelly programs (which work either as a full program or a function), this one works only as a full program (because it sends part of the output to stdout, and returns the rest; when used as a full program the return value is sent to stdout implicitly, so all the output is in the same place, but this wouldn't work for a function submission).

This version of the program is *very* inefficient. You can create a much faster program that works for all input up to 2ⁿ via placing *n* just after the  on the first line; the program has O(*n* × 3ⁿ) performance, so keeping *n* small is fairly important here. The program as written sets *n* equal to the input, which is clearly large enough, but also clearly too large in almost all cases (but hey, it saves bytes).

## Explanation

As usual in my Jelly explanations, text in braces (e.g. `{the input}`) shows something that automatically filled in by Jelly due to missing operands in the original program.

**Helper function** (calculates the *n*th denominator, i.e. the *n*+1th numerator):

```
3ẋḶŒpḄċ
3ẋ       3, repeated a number of times equal to {the argument}
  Ḷ      Map 3 to [0, 1, 2]
   Œp    Take the cartesian product of that list
     Ḅ   Convert binary (or in this case hyperbinary) to a number
      ċ  Count number of occurrences of {the argument} in the resulting list

```

The first five bytes are basically just generating all possible hyperbinary numbers up to a given length, e.g. with input 3, the output of  is \[\[0,1,2\],\[0,1,2\],\[0,1,2\]\] so the cartesian product is \[\[0,0,0\],\[0,0,1\],\[0,0,2\],\[0,1,0\],…,\[2,2,1\],\[2,2,2\]\].  basically just multiplies the last entry by 1, the penultimate entry by 2, the antepenultimate entry by 4, etc., and then adds; although this is normally used to convert binary to decimal, it can handle the digit 2 just fine, and thus works for hyperbinary too. Then we count the number of times the input appears in the resulting list, in order to get an appropriate entry in the sequence. (Luckily, the numerator and denominator follow the same sequence).

**Main program** (asks for the numerator and denominator, and formats the output):

```
’Ç”/⁸Ç
’Ç      Helper function (Ç), run on {the input} minus 1 (‘)
  ”/    {Output that to stdout}; start again with the constant '/'
    ⁸Ç  {Output that to stdout}; then run the helper function (Ç) on the input (⁸)

```

Somehow I keep writing programs that take almost as many bytes to handle I/O as they do to solve the actual problem…

# Answer
> 11 votes
## Haskell, ~~78 77 65~~ 58 bytes

Shamelessly stealing the optimized approach gives us:

```
(s#t)0=show s++'/':show t
(s#t)n=t#(s+t-2*mod s t)$n-1
1#1

```

Thanks to @nimi for golfing a few bytes using an infix function!

(Still) uses 0-based indexing.

---

The old approach:

```
s=(!!)(1:1:f 0)
f n=s n+s(n+1):s(n+1):(f$n+1)
r n=show(s n)++'/':(show.s$n+1)

```

Damn the output format... And indexing operators. EDIT: And precedence.

Fun fact: if heterogenous lists were a thing, the last line could be:

```
r n=show>>=[s!!n,'/',s!!(n+1)]

```

# Answer
> 11 votes
## CJam (20 bytes)

```
1_{_@_2$%2*-+}ri*'/\

```

Online demo. Note that this is 0-indexed. To make it 1-indexed, replace the initial `1_` by `T1`.

### Dissection

This uses the characterisation due to Moshe Newman that

> the fraction `a(n+1)/a(n+2)` can be generated from the previous fraction `a(n)/a(n+1) = x` by `1/(2*floor(x) + 1 - x)`

If `x = s/t` then we get

```
  1 / (2 * floor(s/t) + 1 - s/t)
= t / (2 * t * floor(s/t) + t - s)
= t / (2 * (s - s%t) + t - s)
= t / (s + t - 2 * (s % t))

```

Now, if we assume that `s` and `t` are coprime then

```
  gcd(t, s + t - 2 * (s % t))
= gcd(t, s - 2 * (s % t))
= gcd(t, -(s % t))
= 1

```

So `a(n+2) = a(n) + a(n+1) - 2 * (a(n) % a(n+1))` works perfectly.

```
1_           e# s=1, t=1
{            e# Loop...
  _@_2$%2*-+ e#   s, t = t, s + t - 2 * (s % t)
}
ri*          e# ...n times
'/\          e# Separate s and t with a /

```

# Answer
> 6 votes
# Jelly, 16 bytes

```
L‘Hị⁸Sṭ
1Ç¡ṫ-j”/

```

Try it online! or verify all test cases.

### How it works

```
1Ç¡ṫ-j”/  Main link. Argument: n

1         Set the return value to 1.
 Ç¡       Apply the helper link n times.
   ṫ-     Tail -1; extract the last two items.
     j”/  Join, separating by a slash.

L‘Hị⁸Sṭ   Helper link. Argument: A (array)

L         Get the length of A.
 ‘        Add 1 to compute the next index.
  H       Halve.
   ị⁸     Retrieve the item(s) of A at those indices.
          If the index in non-integer, ị floors and ceils the index, then retrieves
          the items at both indices.
    S     Compute the sum of the retrieved item(s).
     ṭ    Tack; append the result to A.

```

# Answer
> 5 votes
## 05AB1E, ~~34~~ ~~33~~ ~~25~~ 23 bytes

```
XX‚¹GÂ2£DO¸s¦ìì¨}R2£'/ý

```

**Explanation**

```
XX‚                        # push [1,1]
   ¹G           }          # input-1 times do
     Â                     # bifurcate
      2£                   # take first 2 elements of reversed list
        DO¸                # duplicate and sum 1st copy, s(n)+s(n+1)
           s¦              # cut away the first element of 2nd copy, s(n)
             ìì            # prepend both to list
               ¨           # remove last item in list
                 R2£       # reverse and take the first 2 elements
                    '/ý    # format output
                           # implicitly print

```

Try it online

Saved 2 bytes thanks to Adnan.

# Answer
> 4 votes
# Python 2, ~~85~~ 81 bytes

```
x,s=input(),[1,1]
for i in range(x):s+=s[i]+s[i+1],s[i+1]
print`s[x-1]`+"/"+`s[x]`

```

This submission is 1-indexed.

Using a recursive function, 85 bytes:

```
s=lambda x:int(x<1)or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`

```

If an output like `True/2` is acceptable, here's one at 81 bytes:

```
s=lambda x:x<1 or x%2 and s(x/2)or s(-~x/2)+s(~-x/2)
lambda x:`s(x)`+"/"+`s(x+1)`

```

# Answer
> 4 votes
# MATL, 20 bytes

```
FT+"@:qtPXnosV47]xhh

```

This uses the characterization in terms of binomial coefficients given in the OEIS page.

The algorithm works in theory for all numbers, but in practice it is limited by MATL's numerical precision, and so it doesn't work for large entries. The result is accurate for inputs up to `20` at least.

**Try it online!**

### Explanation

```
FT+      % Implicitly take input n. Add [0 1] element-wise. Gives [n n+1]
"        % For each k in [n n+1]
  @:q    %   Push range [0 1 ... k-1]
  tP     %   Duplicate and flip: push [k-1 ... 1 0]
  Xn     %   Binomial coefficient, element-wise. Gives an array
  os     %   Number of odd entries in that array
  V      %   Convert from number to string
  47     %   Push 47, which is ASCII for '\'
]        % End for each
x        % Remove second 47
hh       % Concatenate horizontally twice. Automatically transforms 47 into '\'
         % Implicitly display

```

# Answer
> 3 votes
# C (GCC), 79 bytes

Uses 0-based indexing.

```
s(n){return!n?:n%2?s(n/2):s(-~n/2)+s(~-n/2);}r(n){printf("%d/%d",s(n),s(n+1));}

```

Ideone

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

```
f=(i,n=0,d=1)=>i?f(i-1,d,n+d-n%d*2):n+'/'+d

```

1-indexed; change to `n=1` for 0-indexed. The linked OEIS page has a useful recurrence relation for each term in terms of the previous two terms; I merely reinterpreted it as a recurrence for each fraction in terms of the previous fraction. Unfortunately we don't have inline TeX so you'll just have to paste it onto another site to find out how this formats:

$$ \frac{a}{b} \Rightarrow \frac{b}{a + b - 2(a \bmod b)} $$

# Answer
> 3 votes
# m4, 131 bytes

```
define(s,`ifelse($1,1,1,eval($1%2),0,`s(eval($1/2))',`eval(s(eval(($1-1)/2))+s(eval(($1+1)/2)))')')define(r,`s($1)/s(eval($1+1))')

```

Defines a macro `r` such that `r(n)` evaluates according to the spec. Not really golfed at all, I just coded the formula.

# Answer
> 3 votes
## Python 2, 66 bytes

```
f=lambda n:1/n or f(n/2)+n%2*f(-~n/2)
lambda n:`f(n)`+'/'+`f(n+1)`

```

Uses the recursive formula.

# Answer
> 3 votes
## Actually, 18 bytes

```
11,`│;a%τ@-+`nk'/j

```

Try it online!

This solution uses Peter's formula and is likewise 0-indexed. Thanks to Leaky Nun for a byte.

Explanation:

```
11,`│;a%τ@-+`nk'/j
11                  push 1, 1
  ,`│;a%τ@-+`n      do the following n times (where n is the input):
                      stack: [t s]
    │                 duplicate the entire stack ([t s t s])
     ;                dupe t ([t t s t s])
      a               invert the stack ([s t s t t])
       %              s % t ([s%t s t t])
        τ             multiply by 2 ([2*(s%t) s t t])
         @-           subtract from s ([s-2*(s%t) s t])
           +          add to t ([t+s-2*(s%t) t])
                      in effect, this is s,t = t,s+t-2*(s%t)
              k'/j  push as a list, join with "/"

```

# Answer
> 2 votes
# MATL, ~~32~~ 30 bytes

```
1i:"tt@TF-)sw@)v]tGq)V47bG)Vhh

```

This uses a direct approach: generates enough members of the sequence, picks the two desired ones and formats the output.

**Try it online!**

# Answer
> 2 votes
# R, 93 bytes

```
f=function(n)ifelse(n<3,1,ifelse(n%%2,f(n/2-1/2)+f(n/2+1/2),f(n/2)))
g=function(n)f(n)/f(n+1)

```

Literally the simplest implementation. Working on golfing it a bit.

# Answer
> 2 votes
# Ruby, 49 bytes

This is 0-indexed and uses Peter Taylor's formula. Golfing suggestions welcome.

```
->n{s=t=1;n.times{s,t=t,s+t-2*(s%t)};"#{s}/#{t}"}

```

# Answer
> 2 votes
## Maple

```
0: do 1/(1+floor(%)-frac(%))od;

```

Uses % which is the ditto operator reevaluating the last expression.

# Answer
> 1 votes
# \>\<\>, 34+2 = 36 bytes

After seeing Peter Taylor's excellent answer, I re-wrote my test answer (which was an embarrassing 82 bytes, using very clumsy recursion).

```
&01\$n"/"on;
&?!\:@}:{:@+@%2*-&1-:

```

It expects the input to be present on the stack, so +2 bytes for the `-v` flag. Try it online!

# Answer
> 1 votes
# Octave, 90 bytes

```
function f(i)S=[1 1];for(j=1:i/2)S=[S S(j)+S(j+1) (j+1)];end;printf("%d/%d",S(i),S(i+1));end

```

# Answer
> 1 votes
# C#, ~~91~~ 90 bytes

```
n=>{Func<int,int>s=_=>_;s=m=>1==m?m:s(m/2)+(0==m%2?0:s(m/2+1));return$"{s(n)}/{s(n+1)}";};

```

Casts to `Func<int, string>`. This is the recursive implementation.

Ungolfed:

```
n =>
{
    Func<int,int> s = _ => _; // s needs to be set to use recursively. _=>_ is the same byte count as null and looks cooler.
    s = m =>
        1 == m ? m               // s(1) = 1
        : s(m/2) + (0 == m%2 ? 0 // s(m) = s(m/2) for even
        : s(m/2+1));             // s(m) = s(m/2) + s(m/2+1) for odd
    return $"{s(n)}/{s(n+1)}";
};

```

Edit: -1 byte. Turns out C# doesn't need a space between `return` and `$` for interpolated strings.

# Answer
> 1 votes
## Python 2, 59 bytes

```
s,t=1,1;exec"s,t=t,s+t-2*(s%t);"*input();print'%d/%d'%(s,t)

```

Uses Peter's formula and is similarly 0-indexed.

Try it online

# Answer
> 1 votes
# J, 29 bytes

```
([,'/',])&":&([:+/2|]!&i.-)>:

```

## Usage

Large values of *n* require a suffix of `x` which denotes the use of extended integers.

```
   f =: ([,'/',])&":&([:+/2|]!&i.-)>:
   f 1
1/1
   f 10
3/5
   f 50
7/12
   f 100x
7/19
   f 1000x
11/39

```

# Answer
> 1 votes
# Mathematica, ~~108~~ ~~106~~ 101 bytes

```
(s={1,1};n=1;a=AppendTo;t=ToString;Do[a[s,s[[n]]+s[[++n]]];a[s,s[[n]]],#];t@s[[n-1]]<>"/"<>t@s[[n]])&

```

# Answer
> 1 votes
# , 84 bytes

```
function(n,K=c(1,1)){for(i in 1:n)K=c(K,K[i]+K[i+1],K[i+1])
paste0(K[i],"/",K[i+1])}

```

Try it online!

The older R implementation doesn't follow the specs, returning a floating point rather than a string, so here's one that does.

# Answer
> 1 votes
# APL (Dyalog Unicode), 56 bytes (SBCS)

```
{1(⍵{s←⍺⊃⍵⋄t←⍵[n←⍺+1]⋄⍺=⍺⍺:,/⍕¨s'/'t⋄n∇⍵,(s+t),t})1 1}

```

Try it online!

Inner operator:

```
{                 ⍝ ⍺ is counter, ⍺⍺ is input, ⍵ is sequence
 s ← ⍺ ⊃ ⍵       ⍝ s is the ⍺th element of ⍵ (1-indexed), i.e. s(n)
⋄t ← ⍵[n←⍺+1]     ⍝ t is s(n+1). Also create variable n that holds ⍺+1
⋄⍺ = ⍺⍺:          ⍝ If counter equals the n we want to reach
  s ÷ t           ⍝ Return s(n) / s(n+1)
⋄n ∇ ⍵,(s+t),t   ⍝ Otherwise, call itself again with counter incremented
                 ⍝ and the new terms added to the sequence
                 ⍝ ∇ is self reference and , is concatenate
}

```

The outer function just calls the inner one with 1 as the initial value of the counter, `1 1` as the initial sequence, and its right argument as the left operand of the inner operator (n).

# Answer
> 0 votes
# PARI/GP, 33 bytes

```
f(n)=if(n,(1+f(n\2)^q=n%2*2-1)^q)

```

Attempt This Online!

---
Tags: code-golf, math, sequence, rational-numbers
---


title: Character insertion on letterboards

text:
# Question
Title: Character insertion on letterboards
You know those letterboards outside old-style cinemas which show upcoming films - perhaps you have a miniature one in your home?

If you've operated one, you'll know that you can normally add letters from either side of a row. But the slots (in which you slide letters) are thin, so it's impossible to swap the order of two letters once you've put them on.

Thus, you can't just go putting the letters on in any order - there's a restricted set of orders which actually work...

---

## More formally:

Given a string \\$ S \\$, an ordered list \\$ \sigma= (\sigma\_i)\_{i=0}^k \\$ of characters, we will say \\$ S \\$ is \\$\sigma\\$-*writable* if it is possible to write \\$ S \\$ on a (initially empty) row of a letterboard, by adding (all) the characters from \\$ \sigma \\$, in order. Characters can be inserted on either side of the row, but can **not** pass over existing characters.

For example, **ABBA** is **(B,A,B,A)**-writable, by the following process:

```
                (empty row)
--> B           (insert B from left)
--> AB          (insert A from left)
    ABB  <--    (insert B from right)
    ABBA <--    (insert A from right)

```

But it is *not* **(A,A,B,B)**-writable, since after inserting the initial two **A**s, there is no way to put a **B** in between them.

Trivially, every \\$ S \\$ is *not* \\$\sigma\\$-writable if \\$ \sigma \\$ is not a permutation of the characters of \\$ S \\$.

---

## The Challenge

Your task is to write a program which, given a string \\$ S \\$ of ASCII uppercase letters, and list \\$\sigma\\$, determines whether \\$ S \\$ is \\$\sigma\\$-writable. This is , so the shortest code wins!

You may assume \\$ \sigma \\$ has the same length as \\$ S \\$, although you may not assume it is a permutation of \\$ S \\$.

---

## Test Cases

In the format \\$ S \\$, \\$ \sigma \\$ (as a string).

Truthy inputs:

```
ORATOR, OTRARO
SEWER, EWSER
COOL, COOL
CHESS, SEHSC
AWAXAYAZ, AXYAWAZA
SERENE, ERENES

```

Falsy inputs:

```
SEWER, EWSRE
BOX, BOY
ABACUS, ACABUS
SSSASSS, SSSSASS

```

# Answer
> 8 votes
# Jelly, 8 bytes

```
ŒPUṚ;"Ɗi

```

Try it online!

Takes the letter-list \\$\sigma\\$ on the left and the target word \\$S\\$ on the right, returning a non-negative integer (truthy) if the word can be formed and 0 (falsy) otherwise.

Inspired by a brief exchange with caird coinheringaahing.

```
ŒP          Powerset of σ: list of all sublists of σ, not necessarily contiguous.
  U         Reverse each, then
   Ṛ        reverse the entire list,
    ;"Ɗ     and concatenate corresponding elements of the unmodified powerset:
ŒPUṚ;"Ɗ     it's ordered so that each sublist's complement is at the complementary index.
       i    Find the first index of S in that result, or 0 if not found.

```

# Answer
> 4 votes
# Python 3, ~~68~~ 65 bytes

```
f=lambda s,x,a="":x and f(s,y:=x[1:],x[0]+a)|f(s,y,a+x[0])or a==s

```

Try it online!

# Answer
> 4 votes
# , 22 18 bytes

```
e.((,.~,,.),.)/@|.

```

Try it online!

This builds up all possibilities recursively using a single reduction.

* `@|.` Since J evaluates from right to left, first we reverse our candidate list.
* `((,.~,,.) )/` This simply left-zips the next left element in the reduction with the results so far `,.` and cats that `,` with the right-zip `,.~` of the results so far, thereby giving us all possibilities (since the only way to proceed is to left-append or right-append each next element to what we already have).
    + `(( ),.)/` You might wonder about this *extra* `,.`. This is a J technicality that arises because the zips require the right side to be a table. But in the first step of the reduction, the right side is an atom, and this extra `,.` table-izes that atom. In later steps, when the right side is already a table, table-ize has no effect.

# Answer
> 4 votes
# Factor \+ `math.combinatorics`, 64 bytes

```
[ all-subsets dup [ reverse ] map reverse [ prepend ] 2map in? ]

```

Port of Unrelated String's Jelly answer.

Try it online!

And my original answer:

---

# Factor, ~~74~~ 69 bytes

```
[ { ""} swap [ '[ _ prefix dup reverse 2array ] map-flat ] each in? ]

```

Try it online!

Iterative approach. Works roughly like this:

```
EWSER
^
E
----------------------
EWSER
 ^
WE EW
----------------------
EWSER
  ^
SWE WES SEW EWS
----------------------
EWSER
   ^
ESWE SWEE EWES WESE ESEW SEWE EEWS EWSE
----------------------
EWSER
    ^
RESWE ESWER RSWEE SWEER REWES EWESR RWESE WESER RESEW ESEWR RSEWE SEWER REEWS EEWSR REWSE EWSER

```

Then check if the first input is in this final list.

# Answer
> 4 votes
# Brachylog, ~~12~~ 10 bytes

*-2 bytes thanks to Fatalize*

```
Ė|k↰;?tᵗpc

```

A predicate that takes the list of characters \\$\sigma\\$ as its input parameter and the string \\$S\\$ as its output parameter, succeeding if \\$S\\$ is \\$\sigma\\$-writable and failing if it is not. (Both \\$\sigma\\$ and \\$S\\$ are taken as Brachylog strings.) Try it online!

### Explanation

The predicate is recursive:

```
Ė|k↰;?tᵗpc
Ẹ            Base case: input and output are both the empty string
 |           Or (recursive case):
   ↰         Call this predicate recursively on
  k          The input with its last character removed
    ;?tᵗ     Put the result in a list with the original input's last character
        p    Try both permutations of that list
         c   Concatenate the elements into a single string
             which must match the output parameter

```

# Answer
> 2 votes
# JavaScript (ES6), 45 bytes

Expects two strings as `(S)(sigma)`. Same recursive approach as 97.100.97.109.

```
S=>g=([c,...b],o)=>c?g(b,[o]+c)|g(b,c+o):o==S

```

Try it online!

# Answer
> 2 votes
# Jelly, 12 bytes

Employs the inverse test of a post by pxeger \- here.

```
JŒ!<ƝṢƑ$Ƈịċ⁸

```

A dyadic Link that accepts the sign, \\$S\\$, on the left and the deck of letters, \\$\sigma\\$, on the right and yields a positive integer (truthy) if possible or \\$0\\$ (falsey) if not.

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

### How?

First, this constructs a list of all permutations of the indices of \\$S\\$ which do not decrease after their first increase.

e.g. for \\$S\\$ of length four:

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

```

It then uses these to index into the deck, \\$\sigma\\$, to construct all the possible signs and counts the occurrences of the sign, \\$S\\$.

```
JŒ!<ƝṢƑ$Ƈịċ⁸ - Link: list of characters S, list of characters D (sigma)
J            - range of length (S) -> [1,2,3,...,length(S)]
 Œ!          - all permutations
        Ƈ    - filter keep those for which:
       $     -   last two links as a monad:
    Ɲ        -     for neighbouring pairs:
   <         -       less than?
      Ƒ      -     is invariant under?:
     Ṣ       -       sort
         ị   - index into (D) (vectorises)
           ⁸ - chain's left argument = S
          ċ  - count occurrences

```

# Answer
> 2 votes
# sclin, 26 bytes

```
^set"__ _`"Q rev"++"dip :?

```

Try it here! Port of Unrelated String's clever answer.

For testing purposes (use `-i` flag if running locally):

```
"ORATOR""OTRARO", "SEWER""EWSER", "COOL""COOL", "CHESS""SEHSC", "AWAXAYAZ""AXYAWAZA",.
"SEWER""EWSRE", "BOX""BOY", "ABACUS""ACABUS", "SSSASSS""SSSSASS",.
,` ( ,_. ) map
^set"__ _`"Q rev"++"dip :?

```

## Explanation

Prettified version:

```
^set ( __ _` ) Q rev \++ dip :?

```

Assuming inputs *S*, *σ*:

* `^set` powerset of *σ*
* `( __ _` ) Q` duplicate, reverse each, reverse
* `rev \++ dip` prepend to powerset
* `:?` whether *S* is in resulting array

---

# sclin, 38 bytes

```
1<>: _` ,_"\++ Q rev ++ +`"fold rev :?

```

Try it here!

For testing purposes (use `-i` flag if running locally):

```
"ORATOR""OTRARO", "SEWER""EWSER", "COOL""COOL", "CHESS""SEHSC", "AWAXAYAZ""AXYAWAZA",.
"SEWER""EWSRE", "BOX""BOY", "ABACUS""ACABUS", "SSSASSS""SSSSASS",.
,` ( ,_. ) map
1<>: _` ,_ "\++ Q rev ++ +`"fold rev :?

```

## Explanation

Prettified version:

```
1<>: _` ,_ ( \++ Q rev ++ +` ) fold rev :?

```

Assuming inputs *S*, *σ*:

* `1<>:` split *σ* into head and tail
* `_` ,_ (...) fold` fold over tail with head as initial accumulator...
    + `\++ Q` vectorized suffix
    + `rev ++` vectorized prefix
    + `+`` concat prefixes and suffixes, thereby preserving flatness of accumulator
* `rev :?` whether *S* exists in resulting array of prefixes/suffixes

# Answer
> 2 votes
# Curry (PAKCS), 33 bytes

```
[]![]=1
(x:s?s++[x])!(t++[x])=s!t

```

Try it online!

Returns `1` for truthy, and nothing otherwise. It might return the same `1` multiple times for truthy result.

# Answer
> 2 votes
# 05AB1E (legacy), 7 bytes

```
æÂís+Iå

```

Port of *@UnrelatedString*'s Jelly answer, so make sure to upvote him/her as well!
Inputs in the order \\$\sigma,S\\$. Outputs `1`/`0` for truthy/falsey respectively.

Try it online or verify all test cases.

**Explanation:**

```
æ        # Get the powerset of the (first) implicit input `σ`
 Â       # Bifurcate it; short for Duplicate & Reverse copy
  í      # Reverse each string in this reversed copy
   s     # Swap so the unmodified powerset-list is at the top of the stack
    +    # †Concatenate the strings at the same positions in the list together
     Iå  # Check if the second input `S` is in this list
         # (after which the result is output implicitly)

```

: The `+` is the reason for the legacy version of 05AB1E (built in Python), which allows concatenation of strings and vectorizes. In the new version of 05AB1E (build in Elixir), the `s+` should have been `øíJ` instead: try it online.

# Answer
> 2 votes
# C (clang), ~~134~~ ~~132~~ 131 bytes

-1 byte thanks to ceilingcat!

```
o;*t;f(*r,a,b,s){r?t=r,s="",*t=0:0;*t|=!strcmp(a,s);for(int v=2,c=*(char*)b;v--&&c;f(0,a,b+1,o))asprintf(&o,"%s%s",v?s:&c,v?&c:s);}

```

Try it online!

# Answer
> 2 votes
# Japt, 11 bytes

Takes `σ` as the first input.

```
à
íiUmÔÔ øV

```

Try it

```
à\níiUmÔÔ øV     :Implicit input of strings U=σ & V=S
à                :Combinations of U
 \n              :Reassign to U
   í             :Interleave U with
     Um          :  Map U
       Ô         :    Reverse
        Ô        :  Reverse
    i            :Reduce each pair by prepending
          øV     :Does the resulting array contain V

```

# Answer
> 1 votes
# Charcoal, 17 bytes

```
⊞υωＦＳ≔⁺⁺ιυ⁺υιυ№υＳ

```

Try it online! Link is to verbose version of code. Takes the list as the first argument and the string as the second argument and outputs a `-` for each order of insertions that writes the string (this is always even because the first character can be inserted from either side). Explanation:

```
⊞υω

```

Start with an empty board.

```
ＦＳ

```

Loop over the list of characters.

```
≔⁺⁺ιυ⁺υιυ

```

Prefix and suffix the character to all of the strings found so far.

```
№υＳ

```

Output the number of occurrences of the desired string.

# Answer
> 1 votes
# Python 3.8 (pre-release), 88 bytes

```
f=lambda a,b,s={}:f(a,b[1:],{b[0]+t for t in s}|{t+b[0]for t in s}|{b[0]})if b else{a}&s

```

Try it online!

I rewrote it using sets and recursion, empty set is falsy, builds up a set of increasing string that get appended and prepended by the next character.

# Answer
> 1 votes
# Nibbles, 7 bytes (14 nibbles)

```
?!.\;`_0$\$@:

```

Nibbles port of Unrelated String's Jelly answer: upvote that one!

```
?!.\;`_0$\$@:
     `_0$       # all subsequences of arg1
    ;           # (save that for later)
   \            # reverse the list
  .      \$     # and map over it reversing each subsequence
 !              # now zip this together with
           @    # the saved of subsequences
            :   # by concatenation
?               # and find the index of arg2
                # (or 0 if not found)

```

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


title: Capped string ladder

text:
# Question
Title: Capped string ladder
Given a string `s` and a positive integer `N`, gradually duplicate each character more and more until `N` duplicates, and then staying at `N` duplicates until `N` characters away from the end, then step down again.

For example, given `abalone` and `3`:

```
a    we start with 1 copy
bb   then 2 copies
aaa  then 3 copies, which is our second parameter
lll  so we continue using 3 copies
ooo  until we reach the end
nn   where we use 2 copies
e    and then finally 1 copy

```

and the result would be `abbaaalllooonne`.

It is guaranteed that the string has length greater than `2N` and only has characters from `a` to `z`.

More testcases:

```
N string       output
2 aaaaa        aaaaaaaa
3 abcdabcdabcd abbcccdddaaabbbcccdddaaabbbccd

```

This is . Shortest answer in bytes wins. Standard loopholes apply.

# Answer
# Jelly, 6 bytes

```
JṡFṢị⁸

```

Try it online!

### How it works

```
JṡFṢị⁸  Main link. Arguments: s (string), n (integer)

J       Get the indices of s.
 ṡ      Split the indices into overlapping chunks of length n.
  F     Flatten the array of chunks.
   Ṣ    Sort the resulting array of indices.
    ị⁸   Get the characters of s at these indices.

```

### Sample run

```
JṡFṢị⁸  "abalone", 3

J       [1, 2, 3, 4, 5, 6, 7].
 ṡ      [[1, 2, 3], [2, 3, 4], [3, 4, 5], [4, 5, 6], [5, 6, 7]]
  F     [1, 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, 7]
   Ṣ    [1, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 7]
    ị⁸  "abbaaalllooonne"

```
> 11 votes

# Answer
# Python 2, 57 bytes

```
f=lambda s,n,i=1:s and s[0]*len(s[:i][:n])+f(s[1:],n,i+1)

```

Try it online!

Also 57:

**Python 2, 57 bytes**

```
f=lambda s,n,i=1:s and s[0]*len(s[:i])+f(s[1:],n,i+(i<n))

```

Try it online!
> 7 votes

# Answer
# JavaScript (ES6), ~~67~~ 65 bytes

*-2 bytes thanks to Chas Brown's shorter method using `min()`.*

```
s=>n=>s.replace(/./g,(c,i)=>c.repeat(Math.min(i+1,s.length-i,n)))

```

Takes input in currying syntax: `f("abalone")(3)`.

## Test Snippet

```
f=
s=>n=>s.replace(/./g,(c,i)=>c.repeat(Math.min(i+1,s.length-i,n)))
```

```
<div oninput="O.value=f(S.value)(+N.value)">String: <input id=S> N: <input id=N size=3></div>Out: <input id=O size=50 disabled>
```
> 6 votes

# Answer
# Jelly,  ~~8~~ 7 bytes

```
J««U$⁸x

```

Try it online!

**How it Works**

```
J««U$⁸x - main link, input e.g. abalone
J        - range of length of letters: [1,2,3,4,5,6,7]
 «       - minimum of each term with second input: [1,2,3,3,3,3,3]
  «U$    - termwise minimum with the reverse:
                    min([1,2,3,3,3,3,3],[3,3,3,3,3,2,1])=[1,2,3,3,3,2,1]
     ⁸x  - repeat each character of the input a number of times corresponding to elements:
                    a*1;b*2;a*3...e*1 = abbaaalllooonne

```

*-1 byte thanks to @LeakyNun*
> 6 votes

# Answer
## Haskell, ~~61~~ 60 bytes

*Thanks to @Laikoni for helping to shave off 1 byte*

```
n#s=do(i,c)<-zip[1..]s;replicate(minimum[n,i,length s-i+1])c

```

Try it online!

Ungolfed:

```
(#) n string = do
    (i, char) <- zip [1..] string
    replicate (minimum [n, i, length(string)-i+1]) char

```
> 2 votes

# Answer
# Haskell (Lambdabot), 74 bytes

```
r=replicate
f x n=join$zipWith r([1..n]++r(length x-2*n)n++reverse[1..n])x

```

Try it online!
> 1 votes

# Answer
# J, 24 bytes

```
(<.&n<./(|.,:[)>:i.#s)#s

```

The bit in parens -- `(<.&n<./(|.,:[)>:i.#s)` -- creates the `1 2 ... n n n ... 2 1` array, as follows:

```
                   #s    length of s, call it L
                 i.      numbers 0 1 ... L-1
               >:        increment by 1, now 1 2 ... L
        (|.,:[)          fork: |. = reverse, ,: = stack, [ = identity
                         resulting in  L ... 2 1
                                       1 2 ... L
     <./                 min of each element of the top and bottom row
 <.&n                    min of each resulting elm and n

```

once we have that, J's `#` operator automatically does exactly what asked for, duplicating each element the number of times specified.

Curious to see a J expert's improvment on this...
> 1 votes

# Answer
# Japt, ~~11~~ 10 bytes

```
ËpVm°TEnUÊ

```

Test it

---

## Explanation

Implicit input of string `U` and integer `V`.

```
Ë

```

Map over `U` and replace every character.

```
Vm

```

Get the minimum of `V`, ...

```
°T

```

`T` (initially `0`) incremented by 1, ...

```
EnUÊ

```

And the index of the current character (`E`) subtracted from (`n`) the length (`Ê`) of `U`.

```
p

```

Repeat the current character that many times.

Implicitly output the final string.
> 1 votes

# Answer
# PHP\>=7.1, 75 bytes

```
for([,$a,$n]=$argv;--$z?:($x=$a[$i]).$z=min($n,strlen($a)-$i,++$i);)echo$x;

```

PHP Sandbox Online

# PHP\>=7.1, 78 bytes

```
for([,$a,$n]=$argv;~$x=$a[$i];)for($z=min($n,strlen($a)-$i,++$i);$z--;)echo$x;

```

PHP Sandbox Online

# PHP\>=7.1, 80 bytes

```
for([,$a,$n]=$argv;$i<$l=strlen($a);)echo str_repeat($a[$i],min($n,$l-$i,++$i));

```

PHP Sandbox Online
> 1 votes

# Answer
# , 87 bytes

```
function(N,s)paste(rep(strsplit(s,"")[[1]],c(1:N,rep(N,nchar(s)-2*N),N:1)),collapse="")

```

Try it online!
> 1 votes

# Answer
# Python 2 68 bytes

```
f=lambda s,n:''.join(s[i]*min(i+1,len(s)-i,n)for i in range(len(s)))

```
> 0 votes

# Answer
# Husk, ~~10~~ 9 bytes

```
₁₁ṀR
↔z↑N

```

Try it online!

The first line is the main function, it repeats each letter *n* times and then calls the second line twice.

The second line takes at most N letters from each group of repeated letters, where N is the 1-based index of the group, then reverses the list.
> 0 votes

# Answer
# Haskell, 68 bytes

```
g 1
g _""_=""
g i(a:b)n=(a<$[1..min(length b+1)$min i n])++g(i+1)b n

```

Try it online!
> 0 votes

# Answer
# APL (Dyalog), 15 bytes

```
{⍵/⍨⍺⌊i⌊⌽i←⍳≢⍵}

```

`{``}` function where left argument (cap) is  and right argument (string) is :

`≢⍵` count the number of characters in the string

generate that many **ɩ**ntegers

`i←` store in *i*

reverse

`i⌊` pairwise minimum with *i*

`⍺⌊` pairwise minimum with the cap

`⍵/⍨` use those numbers to replicate the letters of the string

Try it online!
> 0 votes

# Answer
# F#, 96 bytes

```
let f(s:string)n=Seq.mapi(fun i c->System.String(c,Seq.min[i+1;s.Length-i;n]))s|>String.concat""

```

Try it online!

A port of Justin Mariners javascript answer
> 0 votes

# Answer
# Java (OpenJDK 8), ~~101~~ 97 bytes

```
n->s->{int i=0,j;for(char c:s)for(j=s.length-i++,j=j<i?j:i,j=j<n?j:n;j-->0;)System.out.print(c);}

```

Try it online!

So much playing with indices...
> 0 votes

# Answer
Abalone is a type of fish (well, a shellfish), therefore…

# \>\<\>, 79 bytes

```
&i1\
0(?\:1+:&::&@)?$~i:@
&~}\&~1
0(?\:&::1+&@)?$~}}:
 ~r\
?!v>l?!;:o$1-:@
~~<^

```

Try it online, or watch it at the fish playground!

Reads the string from STDIN, and assumes the number is already on the stack.

Explanation: The second, fourth and sixth lines are the main loops. The details are some ugly stack manipulation, but in broad strokes, first, the second line fills the stack alternating between a character of input and **min**(*i**n*), where *n* is the length cap and *i* is the index of the character in the input: for "abalone", 3, the stack looks like

```
"a", 1, "b", 2, "a", 3, "l", 3, "o", 3, "n", 3, "e", 3, -1=EOF, 3

```

Next, line 4 goes through the stack in the same way in reverse, to get the right hand end capped properly:

```
"a", 1, "b", 2, "a", 3, "l", 3, "o", 3, "n", 2, "e", 1, -1

```

Then the sixth line takes each character–number pair and prints the character as many times as the number.
> 0 votes

# Answer
# Ruby, 59 bytes

Port of xnor’s Python 2 answer.

```
F=->s,n,i=1{s[0]?s[0]*s[...i][...n].size+F[s[1..],n,i+1]:s}

```

Attempt This Online!
> 0 votes

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


title: Conversions Galore!

text:
# Question
Title: Conversions Galore!
Imagine that there are \\$n\\$ different types of objects \\$O\_1,O\_2,O\_3,\ldots,O\_n\\$ and they each have a conversion factor \\$k\_1,k\_2,k\_3,\ldots,k\_n\\$. You can, for any \\$1\le i\le n\\$, convert \\$k\_i\\$ amount of \\$O\_i\\$ into \\$1\\$ of any **other** type of object.

# Task

Your objective is to output all the possible ending configurations of the amount of each of the \\$n\\$ objects after **all possible conversions have been made**, given the initial amount of each object \\$A=a\_1,a\_2,a\_3,\ldots,a\_n\\$ and a list \\$K\\$ of the conversion factor of each object. **Duplicate outputs are not allowed**. It is guaranteed that all conversion factors are greater than \\$1\\$ to prevent infinite conversions.

# Example

Let's say that the amount of each object is `A=[4,1,0]` and the conversion factors are `K=[2,3,4]`.

One way to go about converting each of these is to first convert all the \\$O\_1\\$'s into \\$O\_3\\$'s, resulting in `[0,1,2]`. We can also convert some of the \\$O\_1\\$'s to \\$O\_2\\$'s and the rest to \\$O\_3\\$, resulting in `[0,2,1]`.

But if we convert all the \\$O\_1\\$'s to \\$O\_2\\$'s, we get `[0,3,0]`, which can still be reduced. From `[0,3,0]` we can either convert to \\$O\_1\\$ or \\$O\_3\\$, resulting in `[1,0,0]` and `[0,0,1]` respectively.

So the final output would be:

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

```

# Test Cases

```
A, K ->
output

[4,1,0], [2,3,4] ->
[0,1,2]
[0,2,1]
[1,0,0]
[0,0,1]

[99,99,99], [99,100,100] ->
[1,0,99]
[1,99,0]
[1,0,0]
[0,1,0]
[0,0,1]

[3,0,0], [3,3,3] ->
[0,1,0]
[0,0,1]

[3,0,0,3], [3,3,3,3] ->
[0,0,1,1]
[0,1,0,1]
[1,0,0,1]
[0,1,1,0]
[1,0,1,0]
[1,1,0,0]
[0,0,2,0]
[0,2,0,0]

[4,5], [3,3] ->
[0,1]

```

If you want to generate more test cases, check out this reference implementation that I wrote (if you find any bugs in it, please tell me! I'm not 100% sure that it's right...).

---

This is , so the shortest code in bytes wins!

# Answer
# Charcoal, 56 bytes

```
⊞υθＦυＦΦＬι¬‹§ικ§ηκＦ⁻ＥΦＬι⁻λκＥι⎇⁼ξκ⁻ν§ηκ⁺ν⁼ξλυ⊞υλＩΦυ⬤ι‹λ§ημ

```

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

```
⊞υθ

```

Start a breadth-first search for reachable configurations.

```
Ｆυ

```

Loop over the reachable configurations as they are found.

```
ＦΦＬι¬‹§ικ§ηκ

```

Loop over the available conversion sources.

```
Ｆ⁻ＥΦＬι⁻λκＥι⎇⁼ξκ⁻ν§ηκ⁺ν⁼ξλυ

```

Loop over the possible conversion destinations, generating the resulting configurations, but exclude previously seen configurations.

```
⊞υλ

```

Save the new configuration for further processing.

```
ＩΦυ⬤ι‹λ§ημ

```

Output only the ending configurations.
> 3 votes

# Answer
# Python 3, ~~175~~ 173 bytes

```
def g(a,b,r,t=1):
	A=enumerate(a)
	for i,x in A:
		for j,y in A:
			if(i!=j)*x>=b[i]:c=[*a];c[i]-=b[i];c[j]+=1;t=g(c,b,r)
	if t:r+=[(*a,)]
def f(a,b):g(a,b,r:=[]);return{*r}

```

Attempt This Online!

Returns the set of arrays (as tuples).
> 2 votes

# Answer
# Python3, 225 bytes:

```
E=enumerate
def f(a,b):
 q,s=[a],[a]
 while q:
  a,F=q.pop(0),0
  for j,k in E(a):
   if k>=b[j]:
    F=1
    for i,A in E(a):
     Y=eval(str(a));Y[j]-=b[j];Y[i]+=1
     if Y not in s and i!=j:q+=[Y];s+=[Y]
  if 0==F:yield a

```

Try it online!
> 1 votes

# Answer
# JavaScript (ES6), 109 bytes

Expects `(K)(A)`. Returns a set of strings.

```
(K,s=new Set)=>g=A=>K.map((v,i)=>A[i]<v||A.map((_,j,[...B])=>j-i&&g(B,B[i]-=v,A.u=++B[j])))|A.u?s:s.add(A+'')

```

Try it online!
> 1 votes

# Answer
# Haskell, 155 bytes

```
import Data.List
f v i l=take i l++v+l!!i:drop(i+1)l
o!k|l<-[0..length o-1]=nub$(#k)=<<[f 1j$f(0-k!!i)i o|j<-l,i<-l,o!!i>=k!!i,j/=i]
e#k|e!k>[]=e!k|1>0=[e]

```

Try it online!

* Imported Data.List for removing duplicates using nub.
* *f* modify element in list at *i*
* *o!k* converts k\*1 of each *o* in every ways
* *e#k* returns *e* if not convertible, else apply *!* again
> 1 votes

# Answer
# Pyth, 51 bytes

```
DydI!s/VdQRaYdVldVldI&nNHg@dN@QN yXHXN=Gd_@QN1;yE{Y

```

Try it online!

### Explanation

```
Dyd                                                    define y(d)
   I!s/VdQRaYd                                         if no conversions left, put d in Y and end function
              Vld                                      for N in range(len(d))
                 Vld                                   for H in range(len(d))
                    I&nNHg@dN@QN                       if N!=H and d[N] is large enough to be converted
                                 yXHXN=Gd_@QN1;        convert type N to type H and recursively call y on the new list
                                               yE      call y on the input list
                                                 {Y    remove duplicates from the output Y

```
> 0 votes

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


title: Take the square root of a string

text:
# Question
Title: Take the square root of a string
### Motivation

In this challenge your task was to multiply two strings, this naturally introduces a way to take the square root of a string.

### How does it work?

Given a string (for example `pub`) the first thing you need to do, is to determine the ASCII code for each character:

```
"pub" -> [112, 117, 98]

```

Next you map these codes to the range `[0..94]` by subtracting `32` of each value:

```
[112, 117, 98] -> [80, 85, 66]

```

Now you need to find for each value its root modulo `95` (eg. `40*40 % 95 = 80`, you could also pick `55`):

```
[80, 85, 66] -> [40, 35, 16]

```

And finally you'll map it back to the range `[32..126]` and convert it back to a string:

```
[40, 35, 16] -> [72, 67, 48] -> "HC0"

```

Indeed `"HC0" ⊗ "HC0" = "pub"` as you can verify with a solution from the other challenge here.

---

The ones familiar with modular arithmetic probably noticed that the square root modulo `95` does not always exist, for example there's no root for `2`. In such a case the square root of a string is not defined and your program/function may crash, loop indefinetly etc.

For your convenience, here's the list of chars that have a square root (the first one is a space):

```
 !$%&)+03489:>CDGLMQVW]`bjlpqu

```

### Rules

* You will write a program/function that takes a string (or list of chars) as an argument and returns *any* square root if it exists
* You may assume that the input always has a square root
* The input may consist of an empty string
* The input will be in the printable range (`[32..126]`)
* The output is either printed to the console or you return a string if the square root exists
* In case the square root doesn't exist, the behavior of your program/function is left undefined
* If you choose to print the root to the console trailing newlines or whitespaces are fine

### Test cases

Note that these are not necessarily the only solutions:

```
''              -> ''
'pub'           -> 'HC0'
'pull!'         -> 'HC33!'
'M>>M'          -> '>MM>'
'49'            -> '4%'
'64'            -> undefined
'Hello, World!' -> undefined

```

# Answer
# sh + coreutils, 58 bytes

```
tr '$%&)+0389:>CDGLMQVW]`bjpqu' 1u.#:BFO%+M/L2Aa,795d0@H=C

```

Try it online!

The modular square root is typically not unique; we have 2 or 4 choices for each character except . We don’t need to translate , `!`, `4`, `l` since each is already a square root of itself. For the remaining characters, we choose images that don’t need to be escaped for the shell or `tr`.
> 10 votes

# Answer
# Python 3, ~~57~~ 56 bytes

```
lambda s:s.translate({k*k%95+32:k+32for k in range(95)})

```

`translate` uses a mapping from "Unicode ordinals to Unicode ordinals". Thus, we don't need `chr`/`ord` conversions. Note: it doesn't crash when the char has no root.

Saved 1 byte thanks to @jonathan-allan

The value of the mapping is the greatest root in range 0..94 of the key. To have the least root (as in the examples), use:

```
lambda s:s.translate({k*k%95+32:k+32for k in range(95,0,-1)})

```

(61 bytes)

```
>>> [s.translate({k*k%95+32:k+32for k in range(95,0,-1)}) for s in ['','pub','pull!','M>>M','49','64','Hello, World!']]
['', 'HC0', 'HC33!', '>MM>', '4%', '64', 'He33o,\x7f9or3d!']

```
> 7 votes

# Answer
# Python 2, 80 bytes

```
lambda s:''.join([chr(i+32)for i in range(95)if i*i%95==ord(c)-32][0]for c in s)

```

Try it online!

Throws IndexError if no root exists.
> 3 votes

# Answer
# Japt, ~~16~~ 15 bytes

```
c@H+LÇ²%95+HÃbX

```

Try it online!

Saved a byte by looking at the 05AB1E answer (using `L` = 100 instead of `95`). Now Japt is the shortest, a quite rare occurance :-D

### Explanation

```
 c@ H+LÇ   ²  %95+HÃ bX
UcX{H+LoZ{Zp2 %95+H} bX}   Ungolfed
                           Implicit: U = input string, H = 32, L = 100
UcX{                   }   Map each charcode X in the input to the following:
      Lo                     Create the array [0, 1, ..., 98, 99]
        Z{         }         and map each item Z to
          Zp2                  Z ** 2
              %95              mod 95
                 +H            plus 32.
                     bX      Find the first index of X in this array. This gives the
                             smallest square root (mod 95) of (X - 32).
    H+                       Add 32 to map this back into the printable range.
                           Implicit: output result of last expression

```
> 3 votes

# Answer
# Jelly, ~~18~~ ~~17~~ 16 bytes

```
95Ḷ²%95+32żØṖFyO

```

Try it online! (comes with test-suite footer)

Saved 2 bytes by doing a complete rewrite. ~~Also the first time I've found use for `}`.~~

### Explanation

The code first calculates all square characters, and then maps them to their respective square roots.

```
95Ḷ²%95+32żØṖFyO    Main link. Argument: S (string)
95                    Take 95.
  Ḷ                   Get the array [0, 1, ..., 94].
   ²                  Square each to get [0, 1, ..., 8836].
    %95               Get each square modulo 95 to get [0, 1, ..., 1].
       +32            Add 32 to get [32, 33, ..., 33].
           ØṖ         Get the list of printables [" ", "!", ..., "~"].
          ż           Interleave with printables to get [[32, " "], ..., [33, "~"]].
             F        Flatten the mapping to [32, " ", ..., 33, "~"].
               O      Get the code point of each character in input.
              y       Map the code points to the correct output characters using the map.

```
> 2 votes

# Answer
# Mathematica, 94 bytes

```
(R[x_]:=Min@Select[Range@45,Mod[#^2,95]==x&];FromCharacterCode[R/@(ToCharacterCode@#-32)+32])&

```

Try it online!
> 2 votes

# Answer
## JavaScript, 82 bytes

*Collaborated with @ETHproductions*

```
s=>s.map(x=>(g=z=>z*z%95==x.charCodeAt(0)-32?String.fromCharCode(z+32):g(z+1))(0))

```

*Input and output are in the form of a char array.*

### Test snippet

```
var f=s=>s.map(x=>(g=z=>z*z%95==x.charCodeAt(0)-32?String.fromCharCode(z+32):g(z+1))(0))

console.log(f([...""]));
console.log(f([..."pub"]));
console.log(f([..."pull!"]));
console.log(f([..."M>>M"]));
console.log(f([..."49"]));
```
> 2 votes

# Answer
# 05AB1E, 17 bytes

```
vтLn95%žQykk33+ç?

```

The algorithm is very similar to the Jelly and Japt answer (Had something else before but that only got me to 19 bytes)

### Explanation

```
vтLn95%žQykk33+ç?
v                 # For each character of the input...
 тL                # Push [1..100]
   n               # Square every element of the list
    95%            # And take it modulo 95
       žQyk        # Push the index of the current character in the printable ascii range
           k       # Push the index of that in the list created earlier
            33+    # Add 33 to the result
               ç   # And convert it back to a character
                ?  # Print the character

```

Try it online!
> 2 votes

# Answer
## Mathematica 82 Bytes

```
FromCharacterCode[Solve[x^2==#,Modulus->95][[1,1,2]]+32&/@(ToCharacterCode@#-32)]&

```

Using Solve's ability to do modular arithmetic.
> 2 votes

# Answer
# Ruby, 65 bytes

```
->s{s.chars.map{|c|((0..94).find{_1**2%95+32==c.ord}+32).chr}*""}

```

Attempt This Online!
> 2 votes

# Answer
# Mathematica, 60 bytes

```
FromCharacterCode[PowerMod[ToCharacterCode@#-32,1/2,95]+32]&

```

Anonymous function. Takes a string as input and returns a string as output. Errors on invalid input.
> 1 votes

# Answer
# Perl 6, 53 bytes

```
{[~] .comb.map({32+first *²%95==.ord-32,^95})».chr}

```

Try it online!
> 1 votes

# Answer
# Factor, ~~59~~ 55 bytes

```
[ [ 32 - 95 iota [ sq 95 mod = ] with find 32 + ] map ]

```

Try it online!
> 1 votes

# Answer
# Go, 120 bytes

```
func f(s[]rune)[]rune{
for i:=range s{for k:=0;k<95;k++{r:=rune(k*k%95+32)
if r==s[i]{s[i]=rune(k+32)
break}}}
return s}

```

Attempt This Online!
> 1 votes

# Answer
# JavaScript, 56 bytes

```
s=>Buffer(s).map(x=>(g=y=>y*y%95+32-x?g(++y):y+32)``)+``

```

Try it online!
> 1 votes

# Answer
# Pip, 33 bytes

```
FiA*a YyAE((SQ,h)%95+32@?i)+32 Cy

```

Try It Online!

---

# Pip, 37 bytes

```
FiA*a-32 YyAE((SQ_%95=i)FI,h)@0+32 Cy

```

Try It Online!
> 0 votes

---
Tags: code-golf, string, printable-ascii
---


title: Does it repeat?

text:
# Question
Title: Does it repeat?
A string of characters repeats if it contains two consecutive substrings that are equivalent.

For example, `2034384538452` repeats as it contains `3845` twice, consecutively.

Therefore, your challenge is to decide whether a string contains a repeating substring. You may take the input as a string or an array of characters.

You will never receive an empty input, and the length of the substring (if it exists) may be 1 or more.

I use `1` and `0` here as my truthy and falsy values, but you may use different values, as long as they are truthy and falsy in your language.

## Examples:

```
abcab -> 0
bdefdefg -> 1
Hello, World! -> 1
pp.pp/pp -> 1
q -> 0
21020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021012102012101202102012021012102012021020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120210121020120210201210120210201202101210201210120210121020120210201210120210121020121012021020120210121020121012021012102012021020121012021020120210121020120210201210120210121020121012021020120 -> 0

```

(The last example was generated from the amount of ones between each zero in the Thue-Morse sequence)

# Answer
# Retina, 6 bytes

```
(.+)\1

```

Try it online!

Positive value for truthy; zero for falsey.

## How it works

Returns the number of matches of the regex `/(.+)\1/g`.
> 12 votes

# Answer
# Brachylog, 3 bytes

```
s~j

```

Try it online!

```
s~j
s    exists a sublist of input
 ~j  which is the result of a juxtaposition of something

```
> 10 votes

# Answer
# Jelly, ~~6~~ 5 bytes

```
Ẇµ;"f

```

This is a full program. TIO can't handle the last test case without truncating it.

Try it online! (last test case truncated to 250 digits)

### How it works

```
Ẇµ;"f  Main link. Argument: s (string)

Ẇ      Words; generate all substrings of s.
 µ     New chain. Argument: A (substring array)
  ;"   Vectorized concatenation; concatenate each substring with itself.
    f  Filter; keep "doubled" substrings that are also substrings.
       This keeps non-empty string iff the output should be truthy, producing
       non-empty output (truthy) in this case and empty output (falsy) otherwise.

```
> 7 votes

# Answer
# Mathematica, 32 bytes

```
StringMatchQ[___~~x__~~x__~~___]

```
> 5 votes

# Answer
# Java, 27 bytes

```
a->a.matches(".*(.+)\\1.*")

```

Pretty much a duplicate of the Retina answer, but there's no way Java's getting any shorter.
> 5 votes

# Answer
# 05AB1E, 5 bytes

```
Œ2×åZ

```

Try it online!

Outputs 1 as truthy value and 0 as falsy value

### Explanation

```
Œ2×åZ
Œ     # Substrings of input
 2×   # duplicate them (vectorized)
   å  # Is the element in the input? (vectorized)
    Z # Maximum value from list of elements

```
> 5 votes

# Answer
# Python, 38 bytes

```
import re
re.compile(r'(.+)\1').search

```

Try it online!

Yawn, a regex. Checks if the string contains a string of one of more characters `.+` followed by that same string that was just captured. The output search object is Truthy if there's at least one match, as can be checked by `bool`.

Using `compile` here saves over writing a lambda:

```
lambda s:re.search(r'(.+)\1',s)

```

---

# Python, 54 bytes

```
f=lambda s:s>''and(s in(s*2)[1:-1])|f(s[1:])|f(s[:-1])

```

Try it online!

Searches for a substring that is composed two or more equal strings concatenated, as checked by `s in(s*2)[1:-1]` as in this answer. Substrings are generated recursively by choosing to cut either the first or last character. This is exponential, so it times out on the large test case.

Near misses:

```
f=lambda s,p='':s and(s==p)*s+f(s[1:],p+s[0])+f(s[:-1])
f=lambda s,i=1:s[i:]and(2*s[:i]in s)*s+f(s[1:])+f(s,i+1)

```

The first one doesn't use Python's `in` for checking substrings, and so could be adapted to other languages.
> 4 votes

# Answer
# Pyth - ~~10~~ ~~9~~ 8 bytes

```
f}+TTQ.:

```

Returns a list of all the repeating substrings (which if there aren't any, is an empty list, which is falsy)

Try It

Explanation:

```
f}+TTQ.:
      .:    # All substrings of the input (implicit):
f           # filter the list of substrings T by whether...
  +TT       # ...the concatenation of the substring with itself...
 }   Q      # ...is a substring of the input

```
> 4 votes

# Answer
# PHP, 32 bytes

```
<?=preg_match('#(.+)\1#',$argn);

```

Try it online!

# PHP, 38 bytes

```
<?=preg_match('#(.+)(?(1)\1)#',$argn);

```

Try it online!
> 3 votes

# Answer
# Cheddar, 60 bytes

```
n->(|>n.len).any(i->(|>i).any(j->n.index(n.slice(j,i)*2)+1))

```

Try it online!
> 3 votes

# Answer
# Python 3, ~~73~~ 66 bytes

*-7 bytes thanks to @LeakyNun*

```
lambda s:any(2*s[j:i]in s for i in range(len(s))for j in range(i))

```

Try it online!
> 2 votes

# Answer
# Perl 6, 11 bytes

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

```

Test it

## Expanded:

```
{        # bare block lambda with implicit parameter ｢$_｣

  ?      # Boolify the following
         # (need something here so it runs the regex instead of returning it)

  /      # a regex that implicitly matches against ｢$_｣
    (.+) # one or more characters stored in $0
     $0  # that string of characters again
  /
}

```
> 2 votes

# Answer
# PHP, 32 bytes

```
<?=preg_match('#(.+)\1#',$argn);

```

Run as pipe with `-F`. Sorry Jörg, I hadn´t noticed You had posted the same.

**non-regex version, ~~84~~ 82 bytes**

```
    for($s=$argn;++$e;)for($i=0;~$s[$i];)substr($s,$i,$e)==substr($s,$e+$i++,$e)&&die

```

exits with return code `0` for a repeat, times out (and exits with error) for none. Run as pipe with `-nr`.
assumes printable ASCII input; replace `~` with `a&` for any ASCII.
> 2 votes

# Answer
# Japt, 8 ~~\+ 1~~ = ~~9~~ 8 bytes

```
f"(.+)%1

```

Try it online. Outputs `null` for falsy, and an array containing all the repeating strings for truthy.

# Explanation

```
 f"(.+)%1
Uf"(.+)%1" # Implicit input and string termination
Uf         # Find in the input
  "(.+)%1" #   a sequence followed by itself
 f         # and return the matched substring
           # output the return value

```
> 1 votes

# Answer
# JavaScript (ES6), 19 bytes

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

```
> 1 votes

# Answer
# Pyth, 15 bytes

```
.E.nm.bqNYtdd./

```

Try it!
> 1 votes

# Answer
# , 6 bytes

```
ø¨.«©±

```

Try it online!

Test Suite!

The program outputs `0` for falsey values, and a positive integer for positive values.

(Note that there was a small bug, so I had to gain 1 byte. Now after the bugfix, I will be able to replace  with `\x82`)

### Explanation

```
ø                     " This is a recent addition to V. This command takes in a regex
                      " and replaces the line with the number of matches of the regex
 ¨.«©±                " The compressed regex. This decompresses to \(.\+\)\1

```
> 1 votes

# Answer
## Cheddar, 16 bytes

```
@.test(/(.+)\1/)

```

This is a function. Try it online!
> 1 votes

# Answer
# Ruby `-n`, 10 bytes

Takes input on stdin. Prints the index of the first repeated substring for truthy and `nil` for falsey.

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

```

Attempt This Online!
> 1 votes

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


title: Garlandification

text:
# Question
Title: Garlandification
# Garland Words

A *garland word* is a word which can be strung together like a garland, because it ends with the same letters it starts with. These groups of letters can even overlap!

For example, `underground` is a garland word of order `3`, because it starts and end with the same 3 characters, `und`. This means it could be strung together like `undergroundergrounderground...`.

`alfalfa` is a garland word, too! It's of order 4. It starts and ends with `alfa`. It can be strung together like so: `alfalfalfalfa`.

A process which I call garlandifying is where once you determine the order `n` of a garland word, you take the original word and add the segment required to have it loop as a garland `n` times. So, since `onion` is an order `2` garland word, you would take `onion`, chop off the first `2` letters to get `ion` and add that to the end `2` times to get `onionionion`.

# Objective

Make a *program or function* which takes input from **standard input or a function argument** and prints out or returns the word, garlandified.

All words will be lowercase, and the highest possible order for a word is `length(word) - 1`.

# Example I/O

```
"onion"       --> "onionionion"
"jackhammer"  --> "jackhammer"
"abracadabra" --> "abracadabracadabracadabracadabracadabra"
""            --> ""
"zvioz"       --> "zviozvioz"
"alfalfa"     --> "alfalfalfalfalfalfa"
"aaaa"        --> "aaaaaaa"

```

---

This is , so least number of bytes wins.

# Answer
> 12 votes
# Pyth, ~~19~~ 18 bytes

```
+z*>Kf!xz>zT1zl>zK

```

Try it online: Demonstration or Test harness

### Explanations:

```
+z*>Kf!xz>zT1zl>zK   implicit: z = input string
     f      1        find the first number T >= 1, which satisfies:
         >zT            all but the first T chars of z
       xz               index of ^ in z
      !                 == 0
    K                store in K
                     the order is length(z) - K
   >K        z       the last K chars
  *                  repeated
              l>zK   len(all but the last K chars) times
+z                   insert z at the beginning

```

# Answer
> 14 votes
# Python, 60 bytes

```
f=lambda s,i=1:s.find(s[i:])and f(s,i+1)or(len(s)-i)*s[:i]+s

```

Was hoping for better, but oh well. `s.find` works neatly here in place of `not s.startswith`.

# Answer
> 12 votes
# Retina, 58 bytes

```
.+
$0#$0
(.*)(.+)#.*\1$
$0#$1#$2-
+`\w#(\w*)-
#$1-$1
#.*-
<empty line>

```

Each line should go to its own file but you can run the code as one file with the `-s` flag.

The four substitution pairs do the followings:

* Duplicate word so we can search for overlaps too.
* Append the word split up at `order` number of characters.
* Append the last part `order` times.
* Keep the original word and the lastly appended part and drop everything else.

The string states for the example `onion`:

```
onion
onion#onion
onion#onion#on#ion-
onion#onion##ion-ionion
onionionion

```

# Answer
> 11 votes
## Haskell, 64 bytes

```
g s=[b>>a|(a,b)<-map(`splitAt`s)[1..],and$zipWith(==)s b]!!0++s

```

Tests:

```
λ: g "onion"       == "onionionion"
True
λ: g "jackhammer"  == "jackhammer"
True
λ: g "abracadabra" == "abracadabracadabracadabracadabracadabra"
True
λ: g ""            == ""
True
λ: g "zvioz"       == "zviozvioz"
True
λ: g "alfalfa"     == "alfalfalfalfalfalfa"
True
λ: g "aaaa"        == "aaaaaaa"
True

```

# Answer
> 10 votes
# Java, ~~160~~ 157 bytes

```
static void g(String s){int i=s.length(),o;for(String p=s;i-->0;)if(s.endsWith(s.substring(0,i))){for(o=i;o-->0;)p+=s.substring(i);System.out.print(p);i=0;}}

```

Input/Output:

```
 g("abracadabra"); --> "abracadabracadabracadabracadabracadabra"

```

Spaced and tabbed for readability:

```
static void g(String s){
int i=s.length(),o;
for(String p=s;i-->0;)
    if(s.endsWith(s.substring(0,i))){
        for(o=i;o-->0;)
            p+=s.substring(i);
        System.out.print(p);
        i=0;
    }
}

```

Suggestions welcome.

# Answer
> 8 votes
# Sed: ~~87~~ 84 characters

(83 characters code + 1 character command line option.)

```
h
s/(.*)./& \1/
T
s/(.+) \1.*/ \1 \1/
t
g
q
:
s/^([^ ]+)(.*)[^ ]$/\1 \1\2/
t
s/ //g

```

Sample run:

```
bash-4.3$ sed -r 'h;s/(.*)./& \1/;T;s/(.+) \1.*/ \1 \1/;t;g;q;:;s/^([^ ]+)(.*)[^ ]$/\1 \1\2/;t;s/ //g' <<< 'underground'
undergroundergroundergrounderground

```

# Answer
> 7 votes
# CJam, ~~24~~ 23 bytes

```
q_:Q,{~)Q>Q\#!},W>~_Q>*

q_:Q                       e# Read the input, take a copy and store it in Q too
    ,{        },           e# Take the length of the input and filter [0 .. len - 1] array
      ~)                   e# Same as number * -1
        Q>                 e# Take last number characters. Call this string S
          Q\#!             e# See if Q starts with S. After the filter, we will only have
                           e# those numbers from [0 .. len - 1] array which are valid orders
                W>~        e# Take the last order number, if exists.
                   _Q>*    e# Garlandify the input order times.

```

Just to start it with something..

Try it online here

# Answer
> 5 votes
## Matlab: ~~97~~ ~~89~~ 82 bytes

Function that uses a regular expression with lookbehind and a capture group:

```
function t=f(s)
n=sum(regexp(s,'(.*$)(?<=^\1.+)'))-1;t=[s(repmat(1:n,1,end-n)) s];

```

That `sum` is needed to handle the empty-string input (convert `[]` into `0`).

Examples:

```
> f('onion'), f('jackhammer'), f('abracadabra'), f(''), f('zvioz'), f('alfalfa'), f('aaaa')
ans =
onionionion
ans =
jackhammer
ans =
abracadabracadabracadabracadabracadabra
ans =
   Empty string: 1-by-0
ans =
zviozvioz
ans =
alfalfalfalfalfalfa
ans =
aaaaaaa

```

# Answer
> 4 votes
# REGXY, ~~53~~ 49 bytes

Uses REGXY, a regex substitution based language

```
//$'#/
/.(.+)#\1\K/#/
a/(#).(.*#)|#.*/$'$1$2/
//a

```

**Overview:** A number of regular expressions are applied. An example run would look like:

```
onion (input)
onion#onion (line 1 regex)
onion#on#ion (line 2 regex - find the repeated section and separate with #)
onionion#n#ion (line 3 regex - the length of the middle token is the garland order, remove a character and append the third token onto the original string on the left)
onionionion##ion (line 4 regex is a pointer to line 3 - repeat the previous again)
onionionion##ion (line 4 regex is a pointer to line 3 - strip everything after and including the #)

```

**Detailed explanation** The following is a line by line breakdown of the regexes:

```
//$'#/

```

This is a regex substitution which matches the first empty string (i.e. the start of the string) and replaces it with everything to the right of the match (`$'`) followed by a hash. For example, it will turn `onion` into `onion#onion`.

```
/.(.+)#\1\K/#/

```

This line finds the section which overlaps by looking for a group of characters immediate preceding the # (`(.+)`) which are the same on the other side of the # (`\1`). The \K just means 'forget that I matched anything', meaning it will not actually be replaced in the substitution. This effectively, this means we just add a # to the position after the overlap has been found, turning `onion#onion` into `onion#on#ion`.

```
a/(#).(.*#)|#.*/$'$1$2/

```

The initial 'a' is just a label for the regex. After this, we find the first # followed by a single character (`.`) and capture everything after this until the next # (`.*#`). We replace this with everything to the right of the match, i.e. the last token ($'), followed by a # (`$1`), followed by the second token less a character (we treat this as a counter, decreasing it each iteration). In the case of onion#on#ion, the two tokens we backreference on are shown in brackets, and the section the entire regex matches is between the pipes: `onion|(#)o(n#)|ion`. We then replace the bits we match (between the pipes) with `$'` (everything to the right of the match, i.e. 'ion'), then $1 (the #), then $2 (n#), meaning we end up with `onion|(ion)(#)(n#)|ion` (brackets show the three tokens in the replacement string).

If the regex fails to match in the first alternation (everything before the pipe), we must have decreased our counter to zero, meaning there are no characters inside the second token. Instead, we look at the second part of the pattern, `#.*`. This simply replaces everything after the first # with `$'$1$2`. Since there are no backreferences created by this alternation, and there is nothing to the right of the match (`.*` matches until the end of the string), we terminate the match and return the result.

```
//a

```

This is just a pointer to the previous line, ensuring we continue to execute the regex substitution until it fails to match any more.

# Answer
> 3 votes
# jq 1.5: 91 characters

(87 characters code + 4 characters command line option.)

```
.+. as$t|[range(1;length)|select($t[:.]==$t[-.:])]|(max//0)as$i|[range($i)|$t[$i:]]|add

```

Sample run:

```
bash-4.3$ jq -R -r -f judy.jq <<< 'underground'
undergroundergroundergrounderground

```

# Answer
> 3 votes
# rs, ~~51~~ 48 bytes

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

```

TAKE THAT, RETINA AND SED!!!!! ;)

Cut off 3 bytes thanks to @randomra.

Live demo and test cases.

Note that the `jackhammer` test case is not there. There's a bug in the handling of spaces in the web interface that causes it to print incorrect output. The offline version of `rs` handles it correctly.

51-byte version:

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

```

Live demo and test cases for original.

# Answer
> 2 votes
## JavaScript (ES6), 95 bytes

```
f=s=>{for(e=i=s.length;i&&e;)s+=s.slice(--i).repeat(!(e=!s.endsWith(s.slice(0,i)))*i);return s}

```

### Demo

Firefox only for now:

```
f = s => {
  for (e = i = s.length; i && e;) s += s.slice(--i).repeat(!(e = !s.endsWith(s.slice(0, i))) * i);
  return s
}

console.log = x => X.innerHTML += x + '\n';

console.log(f('onion'));
console.log(f('jackhammer'));
console.log(f('abracadabra'));
console.log(f(''));
console.log(f('zvioz'));
console.log(f('alfalfa'));
console.log(f('aaaa'));
```

```
<pre id=X></pre>
```

# Answer
> 2 votes
## JavaScript (ES6), 82 bytes

```
g=(s,i=t=s.length)=>s.endsWith(c=s.slice(0,--i))?c+s.slice(i-t).repeat(i+1):g(s,i)

```

*\[Deleted my original answer, because I've now learned ES6 and was interested in finding a recursive solution to this challenge\]*

**Example**

```
g=(s,i=t=s.length)=>s.endsWith(c=s.slice(0,--i))?c+s.slice(i-t).repeat(i+1):g(s,i)

console.log(g('onion'));
console.log(g('jackhammer'));
console.log(g('abracadabra'));
console.log(g(''));
console.log(g('zvioz'));
console.log(g('alfalfa'));
console.log(g('aaaa'));
```

# Answer
> 2 votes
# Vyxal, ~~14~~ 13 bytes

```
ÞKvḟǓṘ†Tt~ȯẋJ

```

Try it Online! (test suite)

**Explanation:**

```
ÞKvḟǓṘ†Tt~ȯẋJ # whole program

ÞK            # get all suffixes of implicit input
  vḟ          # then find each first occurrence in the input
    Ǔ         # rotate the list to the left
     Ṙ        # then reverse
      †       # logical NOT each item
       T      # get indices of elements which are truthy
        t     # get tail
          ȯ   # slice the input from it until the end
         ~    #  just push it, do not pop the used items yet
           ẋ  # repeat the sliced input tail amount of times
            J # then join with the input

```

# Answer
> 1 votes
## CoffeeScript + ES6, 77 bytes

Same approach as my JavaScript answer.

```
f=(s,e=i=s.length)->s+=s[i..].repeat !(e=!s.endsWith s[...i])*i while--i&&e;s

```

# Answer
> 1 votes
## C

```
#include <stdio.h>
#include <string.h>

int main(int argc, char **argv) {
    char *str   = NULL;
    char *p     = NULL;
    int len     = 0 ;
    int i       = 0;
    int j       = 0;
    int k       = 0;
    int loop    = 0;

    if (argc == 1 )
        return 0;

    str = argv[1];
    len = strlen(str);

    if (len %2) {
        loop = len/2 + 1;
    }
    else {
        loop = len/2;
    }

    p = &str[len/2];
    for (i = 0; i < loop ; i++) {
        if (str[k] == *(p++)) {
            k++;
        }
        else
            k = 0;
    }

    printf("k = %d\n", k);
    printf("%s", str);
    p = &str[k];
    for (j =0; j < k ; j++) {
        printf("%s", p);
    }
    return 0;
}

```

# Golfed: 195 bytes - GCC

```
main(int c,char**a){
char *s=a[1],*p;int i=0,j=0,k=0,z,l=strlen(a[1]);
z=l%2?-~(l/2):l/2;p=&s[l/2];
for(;i<z;i++)k=s[k]==*(p++)?-~k:0;
printf("k=%d\n",k);puts(s);p= &s[k];
for(;j<k;j++)puts(p);}

```

# Answer
> 1 votes
# Groovy ~~75~~ ~~57~~ 55 bytes

```
f={w->x=w;w.find{x-=it;!w.indexOf(x)};w+(w-x)*x.size()}

```

Amazing how coming back to something the day after can help

### Ungolfed:

```
f = {w ->

//Set x equal to w
    x=w

//Loop through the characters of w until we return true
    w.find {

//set x equal to x minus the first instance of the current character, i.e.     the word minus the first character
        x-=it

//Returns the index of the first occurance of the string of chars x, when this is 0 (false) we want to return true, so negate it
        !w.indexOf(x)
    }

//When we've escaped the loop, if we've found a match return the word plus the word minus the match multiplied by the lengh of the match.
    w+(w-x)*x.size()
}

```

# Answer
> 1 votes
# Ruby, 75 bytes

```
->s{t=(1...s.size).map{s[_1..]}.find{s[/^#{_1}/]}
t ?s+s[(o=t.size)..]*o:s}

```

Attempt This Online!

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


title: Shortest hex dumping program

text:
# Question
Title: Shortest hex dumping program
### Challenge

Create a console program to display each byte of a file.

---

### Winning

Since this is , fewest bytes wins.

---

### Rules

* Program **must be a console application**, meaning that it will be ran from some sort of command-line interpreter;
* Every byte must be uppercase hexadecimal, separated by a space, and it must be 2 digits; *(put number 0 before it if it has 1 digit)*
* File **must be read** using IO or alternative, and not hard-coded;
* File path must be specified as a **command-line argument or a user prompt (like STDIN)**;
* **No loopholes please**;

---

### Example

test.txt (ends with LF)

```
Hello World!

```

```
$ ./hexdump.exe test.txt
48 65 6C 6C 6F 20 57 6F 72 6C 64 21 0A

```

# Answer
> 11 votes
# C (gcc) on \*nix, ~~73~~ 71 bytes

```
i;main(c,v)int**v;{for(c=open(v[1],0);read(c,&i,1);printf("%02X ",i));}

```

Try it online! Test suite

*-2 bytes thanks to Johan du Toit*

This relies on `O_RDONLY == 0` and on `int_one == 1` where `int int_one; *(char*)&int_one = 1;`.

# Answer
> 6 votes
# Java 11, ~~156~~ 154 bytes

```
import java.nio.file.*;interface M{static void main(String[]a)throws Exception{for(int b:Files.readAllBytes(Path.of(a[0])))System.out.printf("%02X ",b);}}

```

-2 bytes thanks *to @Holger*.

Try it online by using `./.input.tio` as argument file-path, which will have a given input as file-content.

**Explanation:**

```
import java.nio.file.*;        // Required import for Files and Paths
interface M{                   // Class
  static void main(String[]a)  //  Mandatory main method
      throws Exception{        //  With mandatory thrown clause for the readAllBytes builtin
                                         a[0]    // Get the first argument
                                 Path.of(    )   // Get the file using that argument as path
              Files.readAllBytes(             )  // Get all bytes from this file
    for(int b:                                 ) // Loop over each of them:
      System.out.printf(                         //  And print the current byte
                        "%02X ",b);}}            //  As uppercase hexadecimal with leading 0
                                                 //  and trailing space as delimiter

```

# Answer
> 6 votes
# Ruby, 26 bytes

```
$<.bytes{|b|$><<"%02X "%b}

```

Try it online!

# Answer
> 6 votes
# PHP, ~~60~~ ~~59~~ 54 bytes

```
<?=wordwrap(bin2hex(implode(file($argv[1]))),2,' ',1);

```
* -1 byte thanks to manassehkatz
* -5 bytes thanks to Blackhole

Try it online!

# Answer
> 6 votes
# PowerShell, ~~45~~ 40 bytes

```
"$(gc $args -ra|% *ay|%{'{0:X2}'-f+$_})"

```

Try it online!

*-5 bytes thanks to mazzy*

# Answer
> 5 votes
# Perl 5 (`-aF//`), 23 bytes

```
printf"%02X ",ord for@F

```

TIO

# Answer
> 5 votes
## Python 3, 59 bytes

-11 bytes thanks to Mostly Harmless!

-8 bytes thanks to James K Polk!

-24 bytes thanks to Blue!

```
print(' '.join('%02X'%ord(i)for i in open(input()).read()))

```

Try it online!

This is pretty straightforward; it opens a filename given as input on STDIN, reads it, converts each character to its ASCII value, converts each number to hex, strips off the `"0x"` that precedes hexademical values in Python, pads the value with a zero if necessary, then joins the values together with spaces.

# Answer
> 4 votes
# APL (Dyalog Unicode), 16 bytes

Anonymous tacit prefix function. Returns (and implicitly prints, if the value isn't otherwise consumed) a two-row matrix with the top 4 bits represented as a decimal number 0–15 in the top row and the bottom 4 bits similarly represented in the bottom row. That is, the matrix has as many columns as the file has bytes.

```
16 16⊤83 ¯1∘⎕MAP

```

Try it online!

`⎕MAP` map the argument filename to an array
with parameters:
`¯1` the entire length of the file
`83` read as 8-bit integers

`16 16⊤` convert (anti-base) to 2-position hexadecimal

# Answer
> 3 votes
# Bash,  ~~33~~  23 bytes

...with a lot of help:
-3 thanks to manatwork
-4 thanks to spuck
-3 thanks to Nahuel Fouilleul

```
echo `xxd -c1 -p -u $1`

```

**Try it online!**

Note that the TIO link above uses input - we can write files locally, so this shows it working as a program taking a file path.

# Answer
> 3 votes
# Kotlin, ~~130~~ ~~127~~ ~~104~~ ~~93~~ 92 bytes

```
fun main(a:Array<String>){java.io.File(a[0]).readBytes().forEach{print("%02X ".format(it))}}

```

Try it online!

Edit: -11 bytes thanks to @ChrisParton

Edit: Working TIO

Edit: -1 byte thanks to @KevinCruijssen

# Answer
> 2 votes
# Haskell, ~~145~~ 143 bytes

```
import System.Environment
import Text.Printf
import Data.ByteString
main=getArgs>>=Data.ByteString.readFile.(!!0)>>=mapM_(printf"%02X ").unpack

```

# Answer
> 2 votes
# Dart, ~~140~~ 134 bytes

```
import'dart:io';main(a){print(new File(a[0]).readAsBytesSync().map((n)=>n.toRadixString(16).toUpperCase().padLeft(2,'0')).join(' '));}

```

Try it online!

-6 bytes because I forgot to reduce variable names

# Answer
> 2 votes
# Perl 6, 45 bytes

```
@*ARGS[0].IO.slurp(:bin).list.fmt('%02X').say

```

Try it online!

* `@*ARGS[0]` is the first command-line argument.
* `.IO` turns that (presumed) filename into an `IO::Path` object.
* `.slurp(:bin)` reads the entire file into a `Buf` buffer of bytes. (Without the `:bin` the file contents would be returned as a Unicode string.)
* `.list` returns a list of the byte values from the buffer.
* `.fmt('%02X')` is a `List` method that formats the elements of the list using the given format string, then joins them with spaces. (Convenient!)
* `.say` prints that string.

# Answer
> 2 votes
# Rust, 141 bytes (contributed version)

```
use std::{io::*,fs::*,env::*};fn main(){for x in File::open(args().nth(1).unwrap()).unwrap().bytes(){print!("{:02X} ",x.unwrap())}println!()}

```

# Rust, 151 bytes (original version)

```
fn main(){std::io::Read::bytes(std::fs::File::open(std::env::args().nth(1).unwrap()).unwrap()).map(|x|print!("{:02X} ",x.unwrap())).count();println!()}

```

# Answer
> 2 votes
# Emojicode, ~~186~~ 162 bytes

```
filesb❗❗b❗➕256 16❗1 2❗ ❗❗

```

Try it online here.

Ungolfed:

```
 files    Import the files package into the default namespace
    Main code block
 b   For each b in ...
     (ignoring IO errors)
       ... the byte representation of the file ...
       ... read from user input:
  ❗ ❗
       Print ...
       ... in upper case (numbers in bases > 10 are in lower case) ...
       ... the concatenation of:
         b ❗ ➕ 256   b + 256 (this gives the leading zero in case the hex representation of b is a single digit) ...
              16   ... represented in hexadecimal ...
           ❗
         1 2   ... without the leading one,
      ❗
          ... and a space

    ❗❗

```

# Answer
> 2 votes
## bash+Stax, 6+4+1=11 bytes

This is complete theory craft at this point. You can't actually run this. If everything works according to its spec this would work, but not everything does yet.

The bash script is

```
]<$1

```

and the stax program must be compiled and saved to \] is

```
╛↕ßú┼_

```

Set your character set to ISO 8859-1 (Windows-1252 won't work here) and go

Unpacked and explained

```
_          push all input as a single array
F          run the rest of the program for each element of the array
 |H        write the hex of the byte to standard output
 |         write a space to standard output

```

# Answer
> 2 votes
# Node.js, 118 bytes

```
console.log([...require("fs").readFileSync(process.argv[2])].map(y=>(y<16?0:"")+y.toString(16).toUpperCase()).join` `)

```

What the result looks like:

Btw the content of `test.txt` in the example is as follows:

> `做乜嘢要輸出大楷姐，搞到要加番toUpperCase()去轉番，咁就13byte啦。`
> (Why on earth is upper-case output necessary. I had to add the conversion with `toUpperCase()`, and that cost 13 bytes.)

# Answer
> 1 votes
# Python 3, 75 bytes

Mostly a copy of Maxwell's python 2 answer.

```
import sys
print(' '.join('%02X'%b for b in open(sys.argv[1],'rb').read()))

```

# Answer
> 1 votes
# , 98 Bytes

```
import std;void main(string[]s){File(s[1]).byChunk(9).joiner.each!(a=>writef("%02X ",a.to!byte));}

```

Try it Online!

# Answer
> 1 votes
# Forth (gforth), 71 bytes

```
: f slurp-file hex 0 do dup c@ 0 <# # # #> type space 1+ loop ;
1 arg f

```

Try it online!

*TIO has `3 arg` in the last line because TIO passes "-e bye" to the command line parser before passing in the code*

### Code Explanation

```
: f             \ start a function definition
  slurp-file    \ open the file indicated by the string on top of the stack,
                \ then put its contents  in a new string on top of the stack
  hex           \ set the interpreter to base 16
  0 do          \ loop from 0 to file-length - 1 (inclusive)
    dup c@      \ get the character value from the address on top of the stack
    0 <# # # #> \ convert to a double-length number then convert to a string of length 2
    type        \ output the created string
    space       \ output a space
    1+          \ add 1 to the current address value
  loop          \ end the loop
;               \ end the word definition
1 arg f         \ get the filename from the first command-line argument and call the function

```

# Answer
> 1 votes
# Racket, 144 bytes

This submission does output a trailing space, and no trailing newline. Let me know if this is considered a loophole :)

```
(command-line #:args(f)(for([b(call-with-input-file f port->bytes)])(printf"~a "(string-upcase(~r b #:base 16 #:min-width 2 #:pad-string"0")))))

```

## Cleaned up

```
(command-line #:args (f)
 (for ([b (call-with-input-file f port->bytes)])
   (printf "~a "
           (string-upcase
            (~r b #:base 16 #:min-width 2 #:pad-string "0")))))

```

# Answer
> 1 votes
## Javascript, 155 bytes

```
for(b=WScript,a=new ActiveXObject("Scripting.FileSystemObject").OpenTextFile(b.Arguments(0));;b.echo(('0'+a.read(1).charCodeAt(0).toString(16)).slice(-2)))
```

# Answer
> 1 votes
## VBScript, 143 bytes

```
set a=CreateObject("Scripting.FileSystemObject").OpenTextFile(WScript.Arguments(0)):while 1 WScript.echo(right("0"+Hex(Asc(a.read(1))),2)):wend
```

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~94~~ 89 bytes

```
Print@ToUpperCase@StringRiffle@IntegerString[BinaryReadList@Last@$ScriptCommandLine,16,2]

```

Try it online!

The code is quite self-explanatory because of the long command names. It should be read mostly from right to left:

```
$ScriptCommandLine       is a list of {scriptname, commandlinearg1, commandlinearg2, ...}
Last@...                 extracts the last command-line argument
BinaryReadList@...       reads the named file into a list of bytes
IntegerString[...,16,2]  converts each byte to a 2-digit hex string (lowercase)
StringRiffle@...         converts this list of strings into a single string with spaces
ToUpperCase@...          converts the string to uppercase
Print@...                prints the result to stdout

```

# Answer
> 1 votes
# Gema, 45 characters

```
?=@fill-right{00;@radix{10;16;@char-int{?}}}

```

Sample run:

```
bash-5.0$ gema '?=@fill-right{00;@radix{10;16;@char-int{?}}} ' <<< 'Hello World!'
48 65 6C 6C 6F 20 57 6F 72 6C 64 21 0A

```

Try it online!

# Answer
> 1 votes
# Pyth, 12 bytes

```
jdcr1.Hjb'w2

```

Try it online!

Takes input as user prompt (no way to access command-line arguments AFAIK).

```
jd           # join on spaces
  c        2 # chop into pieces of length 2
   r1        # convert to uppercase
     .H      # convert to hex string, interpreting as base 256 (*)
       jb    # join on newlines
         '   # read file as list of lines
          w  # input()

```

(\*) I'm not 100% sure if this is intended, but one base 256 digit (as in, one character), will always convert into exactly 2 hex digits, eliminating the need to pad with zeroes.

# Answer
> 0 votes
### C# .NET Framework 4.7.2 - ~~235~~ ~~213~~ ~~203~~ ~~191~~ ~~175~~ 140 bytes

Try it online!

```
using System.IO;class P{static void Main(string[]a){foreach(var b in File.ReadAllBytes(a[0])){System.Console.Write(b.ToString("X2")+" ");}}}

```

---

```
using System;
using System.IO;

namespace hexdump
{
    class Program
    {
        static void Main(string[] args)
        {
            // Read the bytes of the file
            byte[] bytes = File.ReadAllBytes(args[0]);

            // Loop through all the bytes and show them
            foreach (byte b in bytes)
            {
                // Show the byte converted to hexadecimal
                Console.Write(b.ToString("X2") + " ");
            }
        }
    }
}

```

# Answer
> 0 votes
# 05AB1E, 18 bytes

```
IvyÇh2j' 0.:' Jvy?

```

Try it online!

Explanation:

```
IvyÇh2j' 0.:' Jvy?
Iv                 Loop through each character in input
  y                Push current character
   Ç               ASCII value
    h              Convert to hexadecimal
     2j            Pad with at least 2 spaces
       ' 0.:       Replace all spaces with 0s
            ' J    Add space to end
               vy? Convert to string and print
IvyÇh2j' 0.:' Jvy?

```

# Answer
> 0 votes
# Free Pascal, 81 B

```
var c:char;begin while not EOF do begin read(c);write(hexStr(ord(c),2):3)end end.

```

Note, output has a leading blank and no trailing newline:
`48 65 6C 6C 6F 20 57 6F 72 6C 64 21 0A`

---

**−3 B**: By default the FPC (FreePascal Compiler) has the “FPC compiler compatibility mode” selected. When compiling in FPC’s “ISO standard compiler compatibility mode” the file buffer variables (here specifically `input^`) and “low-level” I/O routines like `get` become available. The following code needs to be compiled with `fpc ‑MISO sourceCode.pas`:

```
begin while not EOF do begin write(hexStr(ord(input^),2):3);get(input)end end.

```

---

**−10 B**: *Furthermore*, *if* `input` was guaranteed to be non-empty, we can use a `repeat … until …` loop instead of the bulky `while … do begin … end`:

```
begin repeat write(hexStr(ord(input^),2):3);get(input)until EOF end.

```

---
Tags: code-golf
---