Sort a concatenated sequence

Question

Consider a sequence based on recurrence relations, f(n) = f(n-1)+f(n-2), starting with f(1) = x1, f(2) = x2. For x1 = 2, x2 = 1, the sequence begins like this:

2  1  3  4  7  11  18  29  47  76  123  199  322  521  843

Concatenating this into a string will give:

213471118294776123199322521843

Now, divide this list into the smallest possible numbers that gives y(n) > y(n-1). Start with the first number, then the second etc. The first output number should always be a single digit. Pad the last number with the required number of zeros.

2 13 47 111 829 4776 12319 93225 218430

You will get two numbers, (x1, x2) as input, on any convenient format, and the challenge is to output the sorted list.

Rules:

• Function and programs are OK
• The initial sequence shall have exactly 15 numbers (The last number is f(15)).
• x1 and x2 are non-negative (zero is possible).
• The output can be on any convenient format
• The output vector y must be created so that y2 > y1.
  • First the smallest possible y1, then the smallest possible y2, then y3 and so on.
• If x1 = x2 = 0 then output 15 zeros (on the same format as other output, i.e. not 000000000000000).

Examples:

Input: 1 1
Output: 1  12  35  81  321  345  589  1442  3337 7610

Input: 3 2
Output: 3  25  71  219  315  0811 3121  23435 55898 145300
                             |
                             Optional leading zero 
Input: 0 0
Output: 0  0  0  0  0  0  0  0  0  0  0  0  0  0  0

The shortest code in bytes wins. Please include a link to an online interpreter if possible.

Answer 1

JavaScript ES6, 127 135

(a,b)=>eval("for(n=r=[],v=13,o=a+n+b;v--;a=b,b=t)o+=t=b+a;for(d of o+'0'.repeat(99))(n+=d)>+v&&(r.push(v=n),n='');+v?r:[...o]")

Test

F=(a,b)=>eval("for(n=r=[],v=13,o=a+n+b;v--;a=b,b=t)o+=t=b+a;for(d of o+'0'.repeat(99))(n+=d)>+v&&(r.push(v=n),n='');+v?r:[...o]")

// less golfed

U=(a,b)=>{
  for(n=r=[], o=a+n+b, v=13; v--; a=b, b=t)
    o+= t= b+a;
  for(d of o+'0'.repeat(99))
    if ((n+=d) > +v)
      r.push(v=n), n='';
  return +v ? r : [...o]
}

function test(){
  var i = I.value.match(/\d+/g)
  O.textContent = i.length > 1 ? F(+i[0],+i[1]) : ''
}
test()

A,B : <input id=I value='0 1' oninput='test()'>
<pre id=O></pre>

Answer 2

JavaScript ES6, 187 180 187 184 182 179 175 172 165 160 155 154 bytes

(a,b)=>eval('d=""+a+b;for(i=-12,j=1;++i<99;)i<2?(c=b,d+=b=a+b,a=c,r=a?[d[0]]:"0,".repeat(15)):(f=+d.slice(j,i))>r[r.length-1]?(r.push(f),j=++i-1):d+=0;r')

I get similar results when run it for 1,1 and 3,2 test cases. 0,0 has taken an excess 26 bytes...

De-golf + converted to ES5 + demo:

function s(a, b) {
  d = "" + a + b;
  for (i = -12, j = 1; ++i < 99;)
    i < 2 ?
      (c = b, d += b = a + b, a = c, r = a ? [d[0]] : "0,".repeat(15))
    : (f = +d.slice(j, i)) > r[r.length - 1] ?
      (r.push(f), j = ++i - 1)
      : d += 0;
  return r
}
document.write(
   s(1,1)+"<br>"+
   s(3,2)+"<br>"+
   s(0,0)
)

Answer 3

Pyth, 56 bytes

LsgM.:sMb2?sQsM.WyHX_1Z`0u?yGX_1GHaGHjkhM.u,eNsN14QYmZ15

Test suite

Explanation:

First, we check whether the input is precisely 0, 0. If so, print 15 zeros.

Otherwise, we produce the sequence, with jkhM.u,eNsN14Q. This is similar to the standard Pyth algorithm for the Fibonacci sequence.

Next, we reduce over this string. The accumulator is a list of strings, representing each number in the divided sequence. At each reduction step, we take the next character, and check whether the accumulator is in order, using the helper function y, defined with LsgM.:sMb2, which is truthy iff the input is out of order. If it is in order, we append the next character to the list as its own number. If not, we add the next character to the end of last string. This is accomplished with u?yGX_1GHaGH ... Y.

Next, we perform a functional while loop. The loop continues until the running list is in order, reusing the helper function. At each step, a 0 is added to the end of the last string in the list. This is accomplished with .WyHX_1Z`0.

Finally, the strings are converted to integers, with sM, and printed.

---

Pyth, 51 bytes

LsgM.:sMb2?sQsM.WyHX_1Z`0hf!yT_./jkhM.u,eNsN14QmZ15

I believe this works, but it is far too slow to test - it's a brute force solution for dividing the string.

---

I will be making some improvements to the X function, but the above code works in the version of Pyth that was most recent when the question was posted.

Answer 4

JavaScript (ES6), 162 bytes

(a,b)=>(k=[...Array(15).keys(y="")],p=-1,z=k.map(_=>0),a|b?[...k.map(f=n=>n--?n?f(n)+f(n-1):b:a).join``,...z].map(d=>+(y+=d)>p?(p=y,y=" ",p):"").join``:z.join` `)

Explanation

(a,b)=>(
  k=[...Array(15).keys(y="")],     // k = array of numbers 0 to 14, initialise y
  p=-1,                            // initialise p to -1 so that 0 is greater than p
  z=k.map(_=>0),                   // z = array of 15 zeroes
  a|b?[                            // if a and b are not 0
      ...k.map                     // for range 0 to 14
      (f=n=>n--?n?f(n)+f(n-1):b:a) // recursive sequence function (0 indexed)
      .join``,                     // join result of f(0) to f(14) as a string
      ...z                         // append zeroes for padding
    ].map(d=>                      // for each digit of concatenated result
      +(y+=d)                      // append the digit to the current number y
      >p?(                         // if the current number is greater than the previous p
        p=y,                       // set previous to the current number
        y=" ",                     // reset y (with space as a separator)
        p                          // output the current number (with space at the start)
      ):""                         // else add nothing to the output
    )
    .join``                        // return the output as a string
  :z.join` `                       // return a bunch of zeroes if a and b are 0
)

Test

var solution = (a,b)=>(k=[...Array(15).keys(y="")],p=-1,z=k.map(_=>0),a|b?[...k.map(f=n=>n--?n?f(n)+f(n-1):b:a).join``,...z].map(d=>+(y+=d)>p?(p=y,y=" ",p):"").join``:z.join` `)

x1 = <input type="number" id="x1" value="3" /><br />
x2 = <input type="number" id="x2" value="2" /><br />
<button onclick="result.textContent=solution(+x1.value,+x2.value)">Go</button>
<pre id="result"></pre>

Answer 5

Mathematica, 192 bytes

f[{0,0}]:=0~Table~15
f@l_:=(t=0;q={};If[#>0,q~Join~{10^⌈Log10[t/#]⌉#},q]&[Last@#]&@FoldList[If[#>t,AppendTo[q,t=#];0,#]&[10#+#2]&,0,Flatten@IntegerDigits@SequenceFoldList[#+#2&,l,Range@13]])

Test cases:

f[{2, 1}]
(* {2, 13, 47, 111, 829, 4776, 12319, 93225, 218430} *)
f[{3, 2}]
(* {3, 25, 71, 219, 315, 811, 3121, 23435, 55898, 145300} *)
f[{0, 0}]
(* {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} *)

The lengths of the function names are killing me.

Answer 6

Haskell, 165 159 152 142 141 bytes

w=take 15
x#y=x:scanl(+)y(x#y)
0%0=w[0,0..]
x%y=g(-1)(w(x#y)++0%0>>=show)(-1)
g _""_=[]
g b l@(h:t)a|b>a=b:g 0l b|1<2=g(max 0b*10+read[h])t a

Usage example: 3 % 2 -> [3,25,71,219,315,811,3121,23435,55898,145300].

Online demo (with a main wrapper).

How it works:

w=take 15
x#y=x:scanl(+)y(x#y)              -- fibonacci sequence generator for x and y

0%0=w[0,0..]                      -- special case 0%0
x%y=g(-1)(w(x#y)++0%0>>=show)(-1) -- calculate fib sequence, add some extra 0 and
                                  -- flatten all digits into a single string.
                                  -- start calculating the resulting sequence

g _""_=[]                         -- if we don't have digits left, stop.
                                  -- the final 0 in the second parameter is ignored.
g b l@(h:t)a
  |b>a=b:g 0l b                   -- if the current number is greater than the
                                  -- previous one, take it and start over.
  |1<2=g(max 0b*10+read[h])t a    -- otherwise add the next digit and retry.
                                  -- The "max" fixes the initial call with -1.

Answer 7

K (ngn/k), 61 bytes

(|/<':){@[x;t-1;(0^x t)+10*]_t:1+*&~0>':x}/.',/$13{x,+/-2#x}/

Try it online!

• .',/$13{x,+/-2#x}/ builds the sequence, converting it into a list of (integer) digits
• (|/<':) is used as the while condition, causing iteration to continue so long as there is any number in the list smaller than its predecessor
• t:1+*&~0>':x identifies the index immediately after the first value less than or equal to its predecessor
• @[x;t-1;(0^x t)+10*] is used to merge numbers in the list together; e.g. 1 2 becomes 12 2. Since indexing a list out of bounds returns a null, we zero-fill with 0^. This handles the last iteration, where we may need to append additional 0's
• @[...]_t removes the "leftover" value at index t from the left-hand-side list (e.g. 12 2 becomes 12)

Answer 8

PowerShell, 167 166 bytes

param($x,$w)if($w-lt($x-eq0)){"0`n"*15;exit}[char[]]("$x"+-join(0..13|%{$w;$w=$x+($x=$w)}))|%{$z+="$_";if(+$z-gt$y){($y=$z);$z=""}};if($z){while(+$z-lt$y){$z+="0"}$z}

Saved a byte by eliminating the $s variable and just feeding the output loop directly.

Ungolfed and commented:

param($x,$w)           # Take input parameters as x and w
if($w-lt($x-eq0)){     # If x=0, ($x-eq0)=1, so $w-lt1 implies w=0 as well
  "0`n"*15             # Print out 15 0's separated by newlines
  exit                 # And exit program
}                      # otherwise ...
[char[]](              # Construct the sequence string as a char-array
"$x"+-join(            # Starting with x and concatenated with a joined array
  0..13|%{             # Loop
    $w                 # Add on w
    $w=$x+($x=$w)      # Recalculate for next loop iteration
  }
))|%{                  # Feed our sequence as a char-array into a loop
  $z+="$_"             # z is our output number, starts with the first digit
  if(+$z-gt$y){        # If z is bigger than y (initialized to 0)
    ($y=$z)            # Set y equal to z and print it
    $z=""              # Reset z to nothing to start building the next number
  }
}
if($z){                # If there is remaining digits, we need to pad zeroes
  while(+$z-lt$y){     # Until z is bigger than y
    $z+="0"            # Tack on a zero
  }
  $z                   # Print the final number
}

Answer 9

Perl 6, 107 bytes

{$_=@=(|@_,*+*...*)[^15].join.comb;.sum??[.shift,{last if !@$_;until (my$a~=.shift//0)>$^b {};$a}...*]!!$_} # 107

Usage:

# give it a lexical name for ease of use
my &code = {...}

# use ｢eager｣ because the anonymous block returns a lazy array
# and ｢say｣ doesn't ask it to generate the values
say eager code 2, 1;
# [2 13 47 111 829 4776 12319 93225 218430]
say eager code 1, 1;
# [1 12 35 81 321 345 589 1442 3337 7610]
say eager code 3, 2;
# [3 25 71 219 315 0811 3121 23435 55898 145300]
say eager code 0, 0;
# [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
say eager code 0, 1;
# [0 1 12 35 81 321 345 589 1442 3337 7000]

Explanation

creates a Fibonacci like sequence, starting with the arguments (@_) slipped (|) in

|@_,*+*...*

takes the first 15 elements of that sequence

(…)[^15]

combines that into a single string (.join), splits it into a sequence of individual characters (.comb) and stores that in the "default" scalar ($_) after coercing the sequence into a mutable array, by first storing it in an anonymous array (@)

$_=@=(…)[^15].join.comb;

it finds the sum of the values in the default scalar, and if that is zero returns the default scalar, which will contain an array of 15 zeros

.sum?? … !!$_

if the sum isn't zero, it creates a list by first shifting off the first element in the default scalar

.shift, … 

followed by generating the rest of the values, checking it against the previous one ($^b)
if the default scalar runs out of values, use 0 instead (//0)

…,{ … ;until (my$a~=.shift//0)>$^b {};$a}...*

stopping when there is no elements left in the default scalar

…,{last if !@$_; … }...*

Answer 10

Jelly, 39 bytes

-.ị
ÇSṭƊ13¡DFŒṖḌ<ƝṖẠƊƇḢṪ×⁵ṭƲÇ>/$¿µṁS?15

Try it online!

This is unbelievably inefficient, both time-wise and memory-wise. You can see it in action for up to \$f(11)\$ on TIO, but it times out if you include up to \$f(15)\$. Luckily, the run time does not heavily depend on the input, so is generally constant. However, Python will usually error due to memory restrictions

How it works

This works by generating all partitions of the digits of the sequence and keeping those which are strictly ascending, ignoring the last element. Due to the way Jelly generates the partitions of a list, this yields the intended array as the first such partition.

-.ị - Helper link. Takes an array, A, on the left
-.  - Yield -0.5
  ị - Take the -0.5th element of A, which returns the last 2 elements

ÇSṭƊ13¡DFŒṖḌ<ƝṖẠƊƇḢṪ×⁵ṭƲÇ>/$¿µṁS?15 - Main link. Takes [a,b] on the left
                                ?   - If statement:
                               S    -   Condition: sum (i.e. a ≠ 0, b ≠ 0)
                             µ      -   If:
   Ɗ                                -     Define a monad f(A):
Ç                                   -       Take the last two elements of A
 S                                  -       Take their sum
  ṭ                                 -       Tack the sum to the end of A
    13¡                             -     Repeat f(A) 13 times, starting with A = [a, b]
       D                            -     Convert to digits
        F                           -     Flatten into an array, D
         ŒṖ                         -     Yield all partitions of D
           Ḍ                        -     Convert arrays back to decimals
                Ɗ                   -     Define a monad g(A):
             Ɲ                      -       Over overlapping pairs of A:
            <                       -         Is less than?
              Ṗ                     -       Remove the last
               Ạ                    -       All true?
                 Ƈ                  -     Keep the partitions which are true under g(A)
                  Ḣ                 -     Take the first one, P
                            ¿       -     While loop:
                           $        -       Condition:
                        Ç           -         Last 2 elements of P
                         >/         -         First is greater than the second
                       Ʋ            -       Body:
                   Ṫ                -         Last element of P
                    ×⁵              -         Times 10
                      ṭ             -         Tack to the end of P
                              ṁ  15 -   Else: Repeat to length 15

Answer 11

Stax, ⁵³ 52 bytes

Ü⌐↓├¶cRU!>πf_╙ⁿεd╔╘≥↔IQ┘┼▐↓▒Φ╙ε☺ÉL╚Jö┤Å☺╠╓§j╨áuf░╢A╬

Run and debug it

Not too well optimized, can probably be shortened a lot.

However, pretty proud that I managed to make it work for all the testcases.

It uses the X and Y registers to store previous values while comparing them in the loop, then pushes X to stack when the Y is greater than it.