11
\$\begingroup\$

A Sumac sequence starts with two integers: t1 and t2.

The next term, t3, = t1 - t2

More generally, tn = tn-2 - tn-1

The sequence ends when tn < 0.

Your challenge: Write a program or function that prints the length of a Sumac sequence, starting with t1 and t2.

  • t1 and t2 are integers within your language's range.
  • Standard loopholes apply.

Test cases

t1  t2       sumac_len(t1,t2)

120  71      5
101  42      3
500  499     4
387  1       3

Bonus street cred:

3    -128    1
-314 73      2

This is code-golf, so shortest answer in bytes wins.

\$\endgroup\$

closed as unclear what you're asking by xnor, Laikoni, Rɪᴋᴇʀ, Erik the Outgolfer, MD XF Nov 25 '17 at 1:15

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • \$\begingroup\$ Closely related, if not a duplicate \$\endgroup\$ – Mr. Xcoder Nov 23 '17 at 15:32
  • 2
    \$\begingroup\$ This seems to be a good challenge, but is a little unclear. Are we supposed to take t1 and t2 as input? And what is i in the test cases? \$\endgroup\$ – caird coinheringaahing Nov 23 '17 at 15:32
  • 2
    \$\begingroup\$ Is it guaranteed that t1 and t2 are >= 0? \$\endgroup\$ – user202729 Nov 23 '17 at 15:33
  • 6
    \$\begingroup\$ @Blacksilver Huh? What's that bonus exactly? Bonus are generally discouraged anyway \$\endgroup\$ – Luis Mendo Nov 23 '17 at 15:59
  • 6
    \$\begingroup\$ Do we have to handle t_1 = t_2 = 0? Does "bonus street cred" mean we don't have to handle t_1 < 0 or t_2 < 0? \$\endgroup\$ – xnor Nov 23 '17 at 17:16

20 Answers 20

8
\$\begingroup\$

Husk, 8 bytes

→V<¡oG-↔

Takes input as a 2-element list. Try it online!

Explanation

→V<¡oG-↔  Implicit input, say p=[101,42]
   ¡      Iterate on p:
       ↔    Reverse: [42,101]
    oG-     Cumulative reduce by subtraction: [42,59]
          Result is infinite list [[101,42],[42,59],[59,-17],[-17,76],[76,-93]...
 V<       Find the first index where adjacent pairs are lexicographically increasing.
          In our example [42,59] < [59,-17], so this gives 2.
→         Increment: 3
\$\endgroup\$
8
\$\begingroup\$

Haskell, 22 bytes

a#b|b<0=1|c<-a-b=1+b#c

Try it online!

I really wish there was a way to pattern match for a negative number...

Explanation

a#b|b<0=1|c<-a-b=1+b#c

a#b                     -- define a function (#) that takes two arguments a and b
   |b<0                 -- if b is negative...
       =1               -- return 1
         |              -- otherwise...
          c<-a-b        -- assign a-b to c...
                =  b#c  -- and return the result of (#) applied to b and c...
                 1+     -- incremented by 1
\$\endgroup\$
  • \$\begingroup\$ I think the explanation is less clear than the code itself for once. :P \$\endgroup\$ – Sriotchilism O'Zaic Nov 23 '17 at 17:19
  • \$\begingroup\$ @WheatWizard That's most probably because I suck at explanations. :P \$\endgroup\$ – totallyhuman Nov 23 '17 at 17:28
3
\$\begingroup\$

Husk, 12 11 bytes

V<0t¡ȯF-↑2↔

Try it online!

Takes the bonus street cred for whatever that's worth.

Explanation

    ¡ȯ       Repeatedly apply the function to the right to the list of all
             previous values and collect the results in an infinite list.
          ↔  Reverse the list of previous results.
        ↑2   Take the first two values (last two results).
      F-     Compute their difference (using a fold).
   t         Discard the first element.
V<0          Find the first index of a negative value.
\$\endgroup\$
2
\$\begingroup\$

Ruby, 29 bytes

->a,b{(1..a).find{a<b=a-a=b}}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ a<b=a-a=b ...How does Ruby parse that..? \$\endgroup\$ – totallyhuman Nov 23 '17 at 16:15
2
\$\begingroup\$

MATL, 13 bytes

`yy-y0<~]N2-&

This handles negative inputs (last two test cases).

Try it online! Or verify all test cases.

Explanation

`        % Do...while
  yy     %   Duplicate top two elements. Implicit inputs first time
  -      %   Subtract
  y      %   Duplicate from below: push previous term
  0<~    %   Is it 0 or greater? This is the loop condition
]        % End. Proceed with next iteration if top of the stack is true
N        % Push number of elements in stack
2-       % Subtract 2
&        % Specify that the next function, namely implicit display, should
         % only display the top of the stack
\$\endgroup\$
2
\$\begingroup\$

Brain-Flak, 142 90 bytes

((()){{}<(({}({}))[({}[{}])({})])([(({})<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}>}<>)

Try it online!

Not very short. Takes input backwards.

Explanation

(
 (())   #Push 1
 {      #Until 0
  {}    #Pop (+1 to counter)
  <(({}({}))[({}[{}])({})])  #tn = tn-1 - tn-2
  ([(({})<(())>)](<>)){({}())<>}{}{((<{}>))<>{}}{}<>{}>  #Greater than 0?
 }      #End loop
 <>     #Get rid of everything
)       #Push result
\$\endgroup\$
2
\$\begingroup\$

05AB1E, 11 bytes

[DŠ-D0‹#]NÌ

Try it online!

Explanation

Takes input as t2, t1

[             # start a loop
 DŠ           # duplicate top of stack and move it down 2 positions
   -          # subtract the top 2 values
    D0‹#      # if a copy of the top value is negative, break loop
        ]     # end loop
         NÌ   # push iteration index+2
\$\endgroup\$
1
\$\begingroup\$

Mathematica, 55 bytes

(t=1;While[Last@LinearRecurrence[{-1,1},#,t++]>0];t-2)&

Try it online!

and now the regular boring approach by @totallyhuman

Mathematica, 25 bytes

If[#2<0,1,1+#0[#2,#-#2]]&

Try it online!

\$\endgroup\$
  • \$\begingroup\$ FYI, the regular boring approach is less than half as long. \$\endgroup\$ – totallyhuman Nov 23 '17 at 18:03
  • 1
    \$\begingroup\$ @totallyhuman boring indeed... you can save a byte #1 to # \$\endgroup\$ – J42161217 Nov 23 '17 at 18:07
1
\$\begingroup\$

J, 22 bytes

[:#({:,-/)^:(0<{:)^:a:

How it works:

                  ^:a: - Repeat until the result stops changing, store the results in a list
          ^:(0<{:)     - repeat if the second term is positive
   ({:,-/)             - makes a tuple (second, first minus second)
[:#                    - number of elements in the list ([: caps the fork)

Try it online!

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

C (gcc), 32 27 26 bytes

-5 bytes thanks to totallyhuman's abuse of gcc (seems to work on tcc too)
-1 byte thanks to PrincePolka

f(a,b){a=b<0?:1+f(b,a-b);}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 26 bytes since, b<0 evaluates to 1, change ?1:1 to ?:1 \$\endgroup\$ – PrincePolka Nov 24 '17 at 18:35
0
\$\begingroup\$

Python 2, 29 bytes

f=lambda a,b:b<0 or-~f(b,a-b)

Try it online!

Returns True instead of 1.

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

JavaScript (ES6), 24 bytes

Returns true instead of 1.

f=(a,b)=>b<0||1+f(b,a-b)

Test cases

f=(a,b)=>b<0||1+f(b,a-b)

console.log(f(120,  71  )) //    5
console.log(f(101,  42  )) //    3
console.log(f(500,  499 )) //    4
console.log(f(387,  1   )) //    3

console.log('Bonus street cred:')
console.log(f(3,    -128)) //    1
console.log(f(-314, 73 ))  //    2

\$\endgroup\$
  • 1
    \$\begingroup\$ @totallyhuman Then you would need f(b)(a-b) so no saving. \$\endgroup\$ – Mr. Xcoder Nov 23 '17 at 15:40
  • \$\begingroup\$ What if a<0? (1 more to go) \$\endgroup\$ – user202729 Nov 23 '17 at 15:48
  • \$\begingroup\$ Update: you are no longer required to support negative input, but it's cool if you do. \$\endgroup\$ – SIGSTACKFAULT Nov 23 '17 at 16:00
0
\$\begingroup\$

Pyth, 11 bytes

This is a recursive function that takes two arguments, G and H. The link is slightly modified in order to actually call the function on the given input.

M|<H0hgH-GH

Test suite.

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

APL (Dyalog), 23 bytes

2∘{0>-/⍵:⍺⋄(⍺+1)∇-⍨\⌽⍵}

Try it online!

How?

2∘ - with an initial accumulator of 2,

-/⍵ - if the next term

0> - is below 0,

- return the accumulator. otherwise,

(⍺+1) - increase the accumulator

- and recurse with

-⍨\⌽⍵ - the last two items reversed and differenced.

      {⍵} 8 2
8 2
      {⌽⍵} 8 2
2 8
      {-⍨\⌽⍵} 8 2
2 6
\$\endgroup\$
0
\$\begingroup\$

Java (OpenJDK 8), 44 bytes

int f(int a,int b){return b<0?1:1+f(b,a-b);}

Try it online!

Shortest iterative I found (50 bytes)

(a,b)->{int c=1;for(;b>=0;c++)b=a-(a=b);return c;}

Try it online!

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

dc, 24 bytes

?[dsb-1rlbrd0<a]dsaxz1-p

Try it online!

Explanation

?                         # read input                | 71 120
 [dsb-1rlbrd0<a]          # push string               | [string] 71 120
                dsa       # copy top to register a    | [string] 71 120
                   x      # execute the string        | -5 27 1 1 1 1
                    z     # push length of stack      | 6 -5 27 1 1 1 1
                     1-   # decrement top by 1        | 5 -5 27 1 1 1 1
                       p  # print top

 # string in register a:

  dsb                     # copy top to register b    | 71 120
     -                    # subtract                  | 49
      1                   # push 1                    | 1 49
       r                  # swap top two elements     | 49 1
        lb                # load register b           | 71 49 1
          r               # swap top two elements     | 49 71 1
           d0<a           # if top < 0 execute register a
\$\endgroup\$
0
\$\begingroup\$

Z80 Assembly, 10 bytes

This version attempts to do the "street cred" version of the task. However, for the suggested test case where t1=-314, t2=73 this program produces answer "0", which, frankly, makes a little bit more sense than "2".

SumacLen:
        xor a           ; HL = t[1], DE = t[2], A is the counter
Loop:   bit 7,h
        ret nz          ; stop if HL is negative
        inc a
        sbc hl,de       ; HL = t[3], DE = t[2]
        ex de,hl        ; HL = t[2], DE = t[3]
        jr Loop

The test program for ZX Spectrum 48K written using Sjasmplus assembler can be downloaded here. A compiled snapshot is also available.

\$\endgroup\$
  • \$\begingroup\$ Presumably the non-bonus version uses Loop: ret c instead? \$\endgroup\$ – Neil Nov 24 '17 at 10:14
  • \$\begingroup\$ Yes, checking the sign bit of H would no longer be needed. "bit 7,h" can be removed and "ret nz" replaced by "ret c", with "inc a" moving just in front of it. 8 bytes altogether. \$\endgroup\$ – introspec Nov 24 '17 at 10:24
  • \$\begingroup\$ Yeah; the 2 result is really just a thing with my program. \$\endgroup\$ – SIGSTACKFAULT Nov 24 '17 at 12:23
  • \$\begingroup\$ Do you mean that 0 is an acceptable answer for that test case? Or do you mean that it would be better to modify my program to output 2? \$\endgroup\$ – introspec Nov 24 '17 at 13:04
0
\$\begingroup\$

Java (OpenJDK 8), 85 75 bytes

(b,c)->{int d,k=1;for(;;){if(c<0)break;else{d=c;c=b-c;b=d;k++;}}return k;};

Try it online!

ungolfed:

(b,c)->{
    int d,k=1;
    for(;;){
        if(c<0)
            break;
        else{
            d=c;
            c=b-c;
            b=d;
            k++;
        }
    }
    return k;
};
\$\endgroup\$
  • 1
    \$\begingroup\$ I believe this would be shorter as a lambda. \$\endgroup\$ – Potato44 Nov 24 '17 at 6:03
  • \$\begingroup\$ @Potato44 indeed, but I did not have time yesterday to do it, but I did it now and saved 10 bytes. \$\endgroup\$ – Luca H Nov 24 '17 at 6:19
0
\$\begingroup\$

Common Lisp, 59 42 bytes

(defun f(a b)(if(< b 0)1(1+(f b(- a b)))))

Try it online!

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

Perl 6, 24 19 bytes

-5 bytes thanks to Brad Gilbert b2gills.

{+(|@_,*-*...^0>*)}

Try it online!

Explanation: The whole thing in the parentheses is exactly the sequence in question (|@_ are the first 2 terms (= the two parameters), *-* is a function that takes two arguments and returns their difference, and * <0 is the stopping condition (term less than 0). We omit the last term with ^ after the ...). We then force the numerical context by the + operator, which yields the length of the sequence.

\$\endgroup\$
  • \$\begingroup\$ {+(|@_,*-*...^0>*)} \$\endgroup\$ – Brad Gilbert b2gills Nov 24 '17 at 16:15
  • \$\begingroup\$ @BradGilbertb2gills: Thank you. I had a large break with golfing, so I'm a bit rusty. What I don't get, though, is why you must put the space in * <0*, but why you don't need it in 0>*`... \$\endgroup\$ – Ramillies Nov 24 '17 at 16:27
  • \$\begingroup\$ The space is needed so it doesn't get confused with %h<a> \$\endgroup\$ – Brad Gilbert b2gills Nov 25 '17 at 0:35

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