22
\$\begingroup\$

Your input is an array of numbers: a permutation of \$\{1, 2 \dots n\}\$ for some integer \$n \geq 2\$.

How many times must you repeat this list before you can "pick out" the numbers \$[1, 2 \dots n]\$ in order?

That is: find the lowest \$t \geq 1\$ so that \$[1, 2 \dots n]\$ is a subsequence of \$\text{repeat}(\text{input}, t)\$.

This is : write the shortest program or function that accepts a list of numbers and produces \$t\$.

Example

For [6,1,2,3,5,4], the answer is 3:

6,1,2,3,5,4    6,1,2,3,5,4    6,1,2,3,5,4
  ^ ^ ^   ^            ^      ^

Test cases

[2,1] -> 2
[3,2,1] -> 3
[1,2,3,4] -> 1
[4,1,5,2,3] -> 2
[6,1,2,3,5,4] -> 3
[3,1,2,5,4,7,6] -> 4
[7,1,8,3,5,6,4,2] -> 4
[8,4,3,1,9,6,7,5,2] -> 5
[8,2,10,1,3,4,6,7,5,9] -> 5
[8,6,1,11,10,2,7,9,5,4,3] -> 7
[10,5,1,6,11,9,2,3,4,12,8,7] -> 5
[2,3,8,7,6,9,4,5,11,1,12,13,10] -> 6
\$\endgroup\$

22 Answers 22

11
\$\begingroup\$

Jelly, 5 bytes

Ụ>ƝS‘

Try it online!

Ụ     -- Grade up. Indices that would sort the input
 >Ɲ   -- For each pair of adjacent values, is the left larger than the right?
   S  -- Sum the boolean results
    ‘ -- Increment by 1
\$\endgroup\$
8
\$\begingroup\$

Python 3, 36 bytes

f=lambda x,*p:p==()or(x-1in p)+f(*p)

Try it online!

The number of repeats needed is equal to the number of pairs x and x+1 such that the x+1 appears before x in the permutation, plus one.

\$\endgroup\$
8
\$\begingroup\$

Julia 1.0, 30 bytes

a->sum(diff(sortperm(a)).<0)+1

Try it online!

-2 bytes thanks to @dingledooper.

\$\endgroup\$
2
  • \$\begingroup\$ I believe sum works in place of count. \$\endgroup\$ Feb 4 at 5:30
  • \$\begingroup\$ Thanks. Julia is usually fussy about keeping Bools and Ints distinct, so I didn't expect that to work! \$\endgroup\$
    – Sundar R
    Feb 4 at 5:41
4
\$\begingroup\$

Vyxal, 6 bytes

⇧¯0<∑›

Try it Online!

Port of ovs's jelly answer.

⇧      # Grade up
 ¯0<   # Cumulative differences less than 0
    ∑› # Sum + 1
\$\endgroup\$
1
  • \$\begingroup\$ i was 24 hours too late :( \$\endgroup\$
    – DialFrost
    Feb 5 at 10:24
3
\$\begingroup\$

Wolfram Language (Mathematica), 33 31 30 bytes

-1 thanks to alephalpha

Count[#-##2&@@@#~Subsets~2,1]&

Try it online!

Input [list].

Doesn't work for \$n=1\$, but we're guaranteed \$n\ge 2\$.


Wolfram Language (Mathematica), 37 36 bytes

Tr@Boole[Set@a;Set[a,#,a]!=#-1&/@#]&

Try it online!

The number of repeats is also equal to the number of prefixes ...,x that don't contain x-1.

         Set@a;                     clear prefix
                              &/@#  for each:
                           #-1        predecessor
               Set[a,#,a]!=           not in prefix
Tr@Boole[                         ] count
\$\endgroup\$
1
  • \$\begingroup\$ Count[#~Subsets~{2}.{1,-1},1]+1& \$\endgroup\$
    – alephalpha
    Feb 4 at 3:00
3
\$\begingroup\$

R, 34 bytes

function(l)sum(diff(order(l))<0)+1

Try it online!

Port of e.g., Sundar R's answer.

R, 77 69 67 bytes

function(l){while(all(combn(rep(l,T),max(l),is.unsorted)))T=T+1
+T}

Try it online!

Brute force: combn(rep(input,t),max(input)) generates all length(input) subsequences of \$\text {repeat}(\text {input},t)\$, and check for one that is sorted.

-2 bytes thanks to pajonk.

\$\endgroup\$
2
  • \$\begingroup\$ I think here length(input)=max(input), so -2 bytes. \$\endgroup\$
    – pajonk
    Feb 4 at 6:06
  • \$\begingroup\$ @pajonk yes, of course, thank you. \$\endgroup\$
    – Giuseppe
    Feb 4 at 14:27
3
\$\begingroup\$

Haskell, 39 34 bytes

Thanks @Unrelated String for -3 bytes

Thanks @Bubbler for another -2 bytes

f[]=1
f(h:t)=sum[1|elem(h-1)t]+f t

Try it online!

Port of @dingledooper's Python answer

Answered as part of the current Haskell LYAL event. Tell me if there are any golfs, this is my first time coding in Haskell.

\$\endgroup\$
2
\$\begingroup\$

Factor, 42 bytes

[ arg-sort differences [ 0 < ] count 1 + ]

Port of @SundarR's Julia answer.

Explanation

Arg-sort the input (i.e. get the indices that sort the input), get their first-order differences, count how many elements are negative, and add one.

               ! { 6 1 2 3 5 4 }
arg-sort       ! { 1 2 3 5 4 0 }
differences    ! { 1 1 2 -1 -4 }
[ 0 < ] count  ! 2
1              ! 2 1
+              ! 3

Try it online!

\$\endgroup\$
2
\$\begingroup\$

MATL, 11 8 7 bytes

&Sd0<sQ

Try it online!

Straight port of my Julia answer (using the second output of sort in place of sortperm - thanks to @Giuseppe for that idea, saving me 3 bytes).

Another -1 byte thanks to @LuisMendo (so rusty with MATL I forgot & even existed!)

\$\endgroup\$
0
2
\$\begingroup\$

Octave, 24 bytes

@(a)nnz(tril(a==a'+1))+1

Try it online!

Port of @dingledooper's Python 3 answer.

\$\endgroup\$
2
\$\begingroup\$

APL(Dyalog Unicode), 4938 bytes SBCS

{0=⌈/⍵:1⋄~1∊⍺:1+⍵∇⍵⋄(⍵-1)∇⍨¯1+⍺↓⍨⍺⍳1}⍨

Try it on APLgolf!

A dfn submission which uses recursion (yuck) to keep track of things. Instead of looking for increasing numbers, we decrement the sequence and always look for a 1: this means that, as we recurse, we don't need to keep track of the number we are searching for.

contains the tail of the sequence where we can still look for 1s, and contains a copy of the original sequence, but decremented by the amount of times we already found the next digit.

Then, we just look for the next number in the sequence tail.

  • If it's there, chop the sequence tail and call the function recursively, after decrementing the original sequence again and the new tail.
  • If it's not there, use to reset the sequence tail, and add a 1 to the recursive result because we needed one extra repetition.

Recursion stops when the decremented copy of the original sequence has 0 as its largest element.


@Razetime also shared a “boring Jelly port” in the comments for 8 bytes:

1+1⊥2>/⍋
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Boring Jelly port: 1+1⊥2>/⍋ \$\endgroup\$
    – Razetime
    Feb 4 at 9:03
  • \$\begingroup\$ @Razetime lol 🤣 I tried solving this without looking at the other solutions, but didn't expect to be kicked in the butt so spectacularly! Will you post this as a separate solution or should I add it here w/ credit? \$\endgroup\$
    – RGS
    Feb 4 at 9:25
  • \$\begingroup\$ well it isn't particularly novel. I'd rather leave it as a comment and keep your answer unchanged. \$\endgroup\$
    – Razetime
    Feb 4 at 10:04
2
\$\begingroup\$

Brachylog, 9 8 bytes

{⊇Ċ-1}ᶜ<

Try it online!

Explanation

Saved 1 byte by porting everybody else's approach.

{⊇Ċ-1}ᶜ<
{    }ᶜ   Count how many ways there are to satisfy this predicate:
 ⊇          A subsequence of the input
  Ċ         Of length 2
   -        Has a difference (first element minus second element)
    1       Equal to 1 (first element is 1 + second element)
       <  The output is the next integer larger than that result

Old solution that implements the spec directly:

;.j₎⊇~o?∧
;           Pair the input with
 .          Some as-yet unknown value which will be the output
  j₎        Repeat the former a number of times equal to the latter (trying 0 first,
            then 1, then 2, etc., until the rest of the predicate succeeds)
    ⊇       Some subsequence of the result
     ~o     Is a sorted version of
       ?    The input
        ∧   Output whatever we calculated earlier as .

Try it online!

\$\endgroup\$
1
\$\begingroup\$

Python3, 109 bytes:

from itertools import*
f=lambda x,c=1:c if any(sorted(x)==[*i]for i in combinations(x*c,len(x)))else f(x,c+1)

Try it online!

Brute force solution, extremely slow.

Python3, 115 bytes:

v=lambda o,n:not o or(o[0]in n and v(o[1:],n[n.index(o[0])+1:])) 
f=lambda x,c=1:c if v(sorted(x),x*c)else f(x,c+1)

Try it online!

Much faster version.

\$\endgroup\$
2
  • \$\begingroup\$ For the slow one: 108 bytes. I just swapped the if else order so you could remove whitespace. You can do the same for the other one for one less byte \$\endgroup\$ Feb 3 at 22:19
  • \$\begingroup\$ 113 bytes by removing the paranthese after or and the matching parenthesis on the end (along with the extra whitespace at the end?!) \$\endgroup\$ Feb 3 at 22:26
1
\$\begingroup\$

JavaScript (ES6), 45 bytes

f=(a,k=0)=>a.some(n=>!a[k+=k+1==n])||1+f(a,k)

Try it online!

\$\endgroup\$
1
\$\begingroup\$

K (ngn/k), 8 bytes

1+/<':<:

Try it online!

Essentially a port of @ovs' Jelly answer.

  • <: grade-up the input (generates a permutation vector which would sort argument into ascending order)
  • <': check if each value is less than its predecessor
  • 1+/ take the sum, seeded with 1
\$\endgroup\$
1
\$\begingroup\$

Desmos, 55 bytes

l=sort([1...L.length],L)
f(L)=\total(\{l[2...]<l,0\})+1

Try It On Desmos!

Try It On Desmos! - Prettified

\$f(L)\$ takes in a list \$L\$ and returns the lowest value of \$t\$ as specified in the challenge.

The code basically just does the "grade up" trick that many of the other answers were doing.

\$\endgroup\$
1
\$\begingroup\$

Charcoal, 10 bytes

IΣEθ›κ⌕θ⊕ι

Try it online! Link is to verbose version of code. Based on @dingledooper's observation that the number of repeats is 1 plus the number of times x+1 appears before x, although because Find returns -1 when the value is not found, the formula believes n+1 appears before n, thus automatically adding the extra 1 to the result.

   θ        Input array
  E         Map over values
     κ      Current index
    ›       Is greater than
      ⌕     Index of
         ι  Current value
        ⊕   Incremented
       θ    In input array
 Σ          Take the sum
I           Cast to string
            Implicitly print
\$\endgroup\$
0
\$\begingroup\$

Retina 0.8.2, 28 bytes

\d+
$*
\b1(1*)\b(?=.*\b\1\b)

Try it online! Link includes test cases. Explanation: Uses @dingledooper's observation again.

\d+
$*

Convert to unary.

\b1(1*)\b(?=.*\b\1\b)

Count the matches of 1+$.1 that are followed by $.1. When this is positive, the word boundary anchors simply ensure that $.1 is exactly matched, but conveniently when $.1 is 0 we get an extra "false" match which automatically increments the final result for us.

\$\endgroup\$
0
\$\begingroup\$

05AB1E, 6 bytes

>kā<‹O

The same approach as @dingledooper's uses in his Python answer.

Try it online or verify all test cases.

Explanation:

>       # Increase each value in the (implicit) input-list by 1
 k      # Get the index of these values in the (implicit) input-list
        # (or -1 for the max+1 that isn't found)
  ā     # Push a list in the range [1,length] (without popping the list)
   <    # Decrease each by 1 to make the range [0,length)
    ‹   # Do a smaller than check for the values of the two lists
     O  # Sum the amount of truthy values
        # (which is output implicitly as result)
\$\endgroup\$
0
\$\begingroup\$

C (gcc), 70 57 bytes

i;t;f(a,n)int*a;{for(i=t=n;t;)a[i%n]+t+~n?i++:t--;a=i/n;}

Try it online!

Saved a whopping 13 bytes thanks to att!!!

Inputs a pointer to an array of numbers that are a permutation of \$\{1, 2 \dots n\}\$ and \$n\$ (because pointers in C carry no length info).
Returns how many times this array must be repeated before you can pick out the numbers \$\{1, 2 \dots n\}\$ in order.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ brute force 57 bytes: i;t;f(a,n)int*a;{for(i=t=n;t;)a[i%n]+t+~n?i++:t--;a=i/n;} \$\endgroup\$
    – att
    Feb 4 at 0:12
  • \$\begingroup\$ @att Awesome - thanks! :D \$\endgroup\$
    – Noodle9
    Feb 4 at 9:45
0
\$\begingroup\$

PHP, 81 74 67 bytes

array_reduce($a,function($c,$x){return[$x,$c[1]+($x<$c[0])];})[1]+1

Implementation of algorithm from ovs' answer: count all pairs where right < left, then add 1.

Since array_reduce takes only one "carry" param, but we want each iteration to know both the running total and the previous value, we make 'carry' be an array with both elements in, which is a few bytes shorter than making a global, but makes a warning the first time we access the (uninitialized) array.

Reduced from first submission by moving all calculation into the return.

Reduced further since it apparently doesn't need to be a program, just a code snippet that takes an array and outputs a value, so all the boilerplate can go away into a header/footer.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Perl 5, 58 bytes

sub{$_="@_;"x@_;my$i;1while++$i&&s/.*?\b$i\b//;1+@_-y/;//}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.