# Next cyclic suffix

We will say a string $$\x\$$ is cyclic maximal if there is no way to cycle its elements to get a lexicographically larger string. In other words there is no $$\a\$$ and $$\b\$$ such that $$\a \oplus b = x\$$ and $$\b \oplus a > x\$$, where $$\\oplus\$$ is concatenation.

For example [3,2,3,3] is not cyclic maximal because you can cycle the 2 to the end to get [3,3,3,2] which is greater. [9,2,1,2,6] is cyclic maximal because 9 is unambiguously the largest value and it is in the first place, so any cycling will but a smaller value in the first spot.

The challenge here is to take a prefix $$\p\$$, and a positive integer $$\n\$$, and find the lexicographically largest suffix, $$\s\$$, of size $$\n\$$, such that $$\p \oplus s\$$ is cyclic maximal.

# Specifics

You will take as input a non-empty list of non-negative integers representing the prefix and an integer representing the size of the desired suffix.

You may output either the suffix $$\s\$$, or the entire string $$\p\oplus s\$$. The suffix should contain only non-negative integers.

You may assume there is always a valid $$\s\$$ which makes $$\p\oplus s\$$ cyclic maximal.

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

# Test cases

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

• Two questions: 1. How does n affect my output and 2. Can I assume the string is made out of single digits? Mar 19 at 19:21
• @Joao-3 1. $n$ is the size of the ouput. I edited the challenge to repeat that. 2. No. Mar 19 at 19:26
• The problem is clear and well-specified, but I am curious to know what motivated it or what applications it has? Mar 19 at 19:43
• @Jonah A variation of this problem that inspired this challenge came up for me working with cyclically reduced words for problems related to the automorphisms of free groups. I've simplified things to reduce the amount of background knowledge required and make it more suitable for code-golf, so I can't say for sure I know an application for this specific problem. Mar 19 at 19:46

# Jelly, 13 bytes

ṀŻṗ³;ṙJṀƊƑƊƇṪ


Try It Online!

-2 bytes thanks to Jonathan Allan

### Explanation

ṀŻṗ³;ṙJṀƊƑƊƇṪ    Main Link (left = list, right = n)
Ṁ                max of list = k
Ż               [0, ..., k]
ṗ              cartesian product with n
Ƈ     filter elements that are truthy when
³;                the original list ++ this element
ṙJ              finding all rotations
Ṁ             and taking the max element
Ƒ           returns the same thing
Ṫ    take the last element


# JavaScript (Node.js), 102 bytes

f=(x,n,i=x[0])=>n?f([...x,i],n-1)||i--&&f(x,n,i):x.some((_,j)=>x.some(c=>z=x[++j%x.length]-c)&z>0)?0:x


Try it online!

Brute-force

# Uiua, 32 bytes

⊢⇌▽≡(/×≤°⊂⍚↻⇡⧻⟜¤.⊂)¤⟜(☇1⇡↯:+1/↥)


Try it on the pad!

# 05AB1E, 16 bytes

ZÝIãʒ¹ìDā._{θQ}θ


Explanation:

Z               # Push the maximum of the first (implicit) input-list (without popping)
Ý              # Pop and push a list in the range [0,max]
Iã            # Take the cartesian product with the second input-integer n
ʒ           # Filter this list of n-sized lists by:
¹ì         #  Prepend the first input-list
D        #  Duplicate this list
ā       #  Push a list in the range [1,length] (without popping)
._     #  For each value, rotate the list that many times to the left
{    #  Sort this list of lists lexicographical
θ   #  Pop and leave just the last/maximum one
Q  #  Check whether it equals the duplicated unrotated list
}θ          # After the filter: leave the last/maximum valid suffix
# (which is output implicitly as result)


# Python 3, 105 bytes

f=lambda a,n:n and max(f(a+[i],n-1)for i in range(a[0]+1))or(max(a[i:]+a[:i]for i in range(len(a)))==a)*a


Try it online!

# Nekomata + -1, 13 bytes

Ṁ→↔$ŧᵖ{,:xŘṀ=  Attempt This Online! A port of @hyper-neutrino's Jelly answer. Ṁ→↔$ŧᵖ{,:xŘṀ=   Take a prefix p and a positive integer n as input
Ṁ               Maximum of p
→              Increment
↔             Reverse range ([max(p), max(p)-1, ..., 0])
\$ŧ           Find an n-tuple of elements from the range
ᵖ{         Check that it satisfies the following condition:
,            Join the n-tuple with the prefix
:           Duplicate
xŘ         Get a list of all rotations
Ṁ        Maximum
=       Check if it's equal to the original list


-1 finds the first solution, which is the lexicographically largest one because the range is reversed.

# Ruby, 80 bytes

->l,n{w=[0]*n;n.times{|i|w[i]+=1until (z=l+w)!=z.map{z=z.rotate}.max;w[i]-=1};w}


Try it online!

# Python3, 180 bytes

from itertools import*
R=range
def f(l,n):
for k in product(*[R(max(l),-1,-1)for _ in R(n)]):
T=[*l,*k]
if all(T>=T[j:]+T[:j]for i in R(len(T))for j in R(1,len(T))):return k


Try it online!

# Charcoal, 35 bytes

≔⊕⌈θζＩ⌈ΦＥＸζη⁺θ﹪÷ιＸζ…⁰ηζ⁼ι⌈ＥιＥι§ι⁺μξ


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

   θ                                Input p
⌈                                 Maximum
⊕                                  Incremented
≔   ζ                               Save in variable
ζ                         Saved value
Ｘ                          Raised to power
η                        Input n
Ｅ                           Map over implicit range
θ                      Input p
⁺                       Concatenated with
ι                   Current value
÷                    Vectorised divide
ζ                 Saved value
Ｘ                  Vectorised raised to power
…                Range from
⁰               Literal integer 0 to
η              Input p
﹪                     Vectorised Modulo
ζ             Saved value
Φ                            Filtered where
ι           Current list
⁼            Equals
ι        Current list
Ｅ         Map over elements
ι      Current list
Ｅ       Map over elements
ι    Current list
§     Cyclically indexed by
μ  Inner index
⁺   Plus
ξ Innermost index
⌈          Take the maximum
⌈                             Take the maximum
Ｉ                              Cast to string


37 bytes for a fast version:

Ｆη⊞θ§⌈ΦＥ⊕⌈θ⁺θＥ⁻ηι∧¬μκ⁼κ⌈ＥκＥκ§κ⁺νπＬθＩθ


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

Ｆη


Loop over the number of additional digits.

⊞θ§⌈ΦＥ⊕⌈θ⁺θＥ⁻ηι∧¬μκ⁼κ⌈ＥκＥκ§κ⁺νπＬθ


See which digit, when suffixed to the digits so far, plus filled to the final length with zeros, is the maximal that produces a cyclic maximal list, and append that to the list.

Ｉθ


Output the final list.

# Scala 3, 169 bytes

A port of @tsh's Python answer in Scala.

Golfed version. Attempt This Online!

def g(s:Seq[Int],r:Int):Seq[Int]=if(r==0){val x=(0to s.size-1).map(i=>s.drop(i)++s.take(i)).max;if(x==s)s else Nil}else(0 to s.max).map(i=>g(s:+i,r-1)).maxBy(_.mkString)


Ungolfed version. Attempt This Online!

object Main {
def generateMaxSequence(initialSequence: List[Int], stepsRemaining: Int): List[Int] = {
if (stepsRemaining == 0) {
val rotatedSequences = for (i <- initialSequence.indices) yield initialSequence.drop(i) ++ initialSequence.take(i)
val maxSequence = rotatedSequences.max
if (maxSequence == initialSequence) initialSequence else List.empty[Int]
} else {
val maxValue = initialSequence.max
(0 to maxValue).map { i =>
generateMaxSequence(initialSequence :+ i, stepsRemaining - 1)
}.maxBy(_.mkString)
}
}

def main(args: Array[String]): Unit = {
// Test cases
println(generateMaxSequence(List(9), 3))
println(generateMaxSequence(List(4, 2, 1), 3))
println(generateMaxSequence(List(9, 0, 9), 2))
println(generateMaxSequence(List(9, 8, 0, 9, 8), 2))
println(generateMaxSequence(List(9, 8, 0, 9, 8), 3))
println(generateMaxSequence(List(9, 8, 0, 9, 8), 4))
println(generateMaxSequence(List(9, 9, 0, 9), 1))
println(generateMaxSequence(List(5, 4), 5))
//println(generateMaxSequence(List(10, 6, 2), 4))
}
}