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

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 2

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 3

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 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

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 6

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 7

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 8

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 !@$_; … }...*