USING: kernel math sequences combinators accessors ;
IN: project-euler.215

TUPLE: node two three ;
TUPLE: term { count integer } ;

: <node> ( l r -- t ) node boa ; inline
: <term> ( n -- t ) term boa ; inline
: <failure> ( -- t ) 0 <term> ; inline
: <success> ( -- t ) 1 <term> ; inline

: failure? ( t -- ? ) count>> zero? ; inline

: add-terms ( t t -- t ) [ count>> ] bi@ + <term> ; inline

: choice ( t p q -- t t )
  [ [ two>> ] [ three>> ] bi ] 2dip bi* ; inline

GENERIC: total ( t -- n )
M: node total [ total ] dup choice + ;
M: term total count>> ;

: merge ( t t -- t )
   2dup [ node? ] bi@ [
     [ [ [ two>>   ] bi@ merge ]
       [ [ three>> ] bi@ merge ] 2bi <node>
     ] [ nip ] if
   ] [
     [ drop ] [ add-terms ] if
   ] if ;


GENERIC: h-1 ( t -- t )
GENERIC: h0 ( t -- t )
GENERIC: h1 ( t -- t )
GENERIC: h2 ( t -- t )

M: node h-1 [ h1 ] [ h2 ] choice merge ;
M: term h-1 drop <failure> ;

M: node h0 drop <failure> ;
M: term h0 ;

M: node h1 
    [ [ h1 ] [ h2 ] choice merge ]
    [ [ h0 ] [ h1 ] choice merge ] bi <node> ;
M: term h1 drop <failure> ;

M: node h2 [ h1 ] [ h2 ] choice merge <failure> swap <node> ;
M: term h2 dup failure? [ <failure> <node> ] unless ;

: stepper ( t -- t )
  [ h-1 ] [ h1 ] choice swap <node> ;

: first-row ( n -- t )
  [ <failure> <success> <failure> ] dip
  1- [ over roll <node> ] times 2nip ;

: solve-215 ( width height -- ways )
  [ first-row ] dip 1- [ stepper ] times total ;