How to stop recursing?

Question

Advent of Code Day 1 requires looping, in one form or another, over a long string of parentheses like ((((())(())(((()))(( etc. The idea is that ( goes up one "floor", ) goes down one floor, and the objectives are to print

1. the first index in the string where the floor number is negative and
2. the final floor when the end of the string is found.

The imperative solution with a for loop is simple (Python as an example):

def main():
    flr = 0
    basement = False
    for idx, elt in enumerate(text):
        flr += {
            "(": 1,
            ")": -1
        }.get(elt)

        if flr < 0 and not basement:
            print("first basement pos:", idx + 1)
            basement = True

    print("final floor:", flr)

The recursive functional solution is a little more complex, but still not too hard.

def worker(flr, txt, idx, basement):
    flr += {"(": 1, ")": -1}[ txt[0] ]

    if not (len(txt) - 1): return flr

    if flr < 0 and not basement:
        print("first basement floor index: ", idx + 1)
        basement = True

    return worker(flr, txt[1:], idx + 1, basement)


def starter(txt):
    flr, basement, idx = 0, False, 0
    return worker(flr, txt, idx, basement)


if __name__ == '__main__':
    __import__("sys").setrecursionlimit(int(1e5))
    print("final floor:", starter(text))

Both of these give the correct output of

first basement floor index:  1795
final floor: 74

when run against my challenge input.

_{except the second one is dumb because Python doesn't have tail call optimisation but never mind that}

How can I implement either of these in Factor? This is something I've been confused by ever since I started using Factor.

We can't just use a for loop because there's no equivalent that allows us to keep mutable state between iterations.

We could use a recursive solution:

: day-1-starter ( string -- final-floor )
  [ 0 ] dip 0 f day-1-worker 3drop "final floor: %s" printf ;

: day-1-worker 
  ( floor string index basement? -- floor string index basement? )
  day-1-worker  ! what goes here?
  ; recursive

Great, that's a skeleton, but what goes in the body of day-1-worker? Factor doesn't have any way to "early return" from a recursive call because there's no way to run the program in reverse and no concept of return -- that doesn't make any sense.

I get the feeling maybe recursion isn't the answer to this question in Factor. If it is, how do I stop recursing?

Answer 1

First of all, recursion is always the answer :) Since this is a challenge (and I don't know factor), just a hint: in your python solution you have used the side effect to print the first basement level. Quite unnecessary! You can use basemet argument to hold the floor number too, like this:

    def worker(flr, txt, idx, basement):
        flr += {"(": 1, ")": -1}[ txt[0] ]

        if not (len(txt) - 1): return [flr, basement] # <- return both

        if flr < 0 and not basement:
            #print("first basement floor index: ", idx + 1) # side effects go away!
            basement = idx+1 # <- a number in not False, so that's all
        return worker(flr, txt[1:], idx + 1, basement)

So now you get

    final,first_basement = worker(0, txt, 0, False)

Or, alternatively you can write 2 functions, first one seeks the index of first basement floor, the other one just computes the final floor. Having <2000 additional small steps is not a big deal even if you do care about performance.

Good luck!

Edit: as of your question concerning recursion in factor, take a look at the Ackermann Function in Factor and the Fibonacci sequence in Factor and you should get the idea how to "break the loop". Actually the only problem is in thinking (emancipate yourself from the imperative model :)); in functional languages there is no "return", just the final value, and stack-based languages you mention are other computational model of the same thing (instead of thinking of folding a tree one thinks about "pushing and poping to/from the stacks" -- which is btw a common way to implement the former).

Edit: (SPOILER!) I installed Factor and started playing with it (quite nice), for the first question (computing the final score) a possible solution is

    : day-1-worker (  string floor -- floor )
      dup length 0 = 
       [ drop ]
       [ dup first 40 =
         [ swap 1 + ]
         [ swap 1 - ]
         if
         swap rest
         day-1-worker ]
       if ;

    : day-1-starter ( string -- floor )
      0 swap day-1-worker ;

So now you can either write similar one for computing basement's index, or (which would be more cool!) to modify it so that it also manages index and basement... (Probably using cond would be wiser than nesting ifs).

Answer 2

You could use the cum-sum combinator:

: to-ups/downs ( str -- seq )
    [ CHAR: ( = 1 -1 ? ] { } map-as ;

: run-elevator ( str -- first-basement final-floor )
    to-ups/downs cum-sum [ -1 swap index 1 + ] [ last ] bi ;

IN: scratchpad "((())))(())(())(((()))((" run-elevator

--- Data stack:
7
2