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

EDIT

I originally misread how your were computing the basement value. I've updated the answers below

---

Here's a JavaScript solution. Sorry I have no idea how this converts to Factor. reduce is an iterative process

const worker = txt=>
  txt.split('').reduce(({floor, basement}, x, i)=> {
    if (x === '(')
      return {floor: floor + 1, basement}
    else if (basement === null && floor === 0)
      return {floor: floor - 1, basement: i}
    else
      return {floor: floor - 1, basement}
  }, {floor: 0, basement: null})
 
let {floor, basement} = worker('((((())(())(((()))((')
console.log(floor)    //=> 6
console.log(basement) //=> null; never reaches basement

---

The answer above relies on some some .split and .reduce which may not be present in your language. Here's another solution using Y-combinator and only the substring built-in (which most languages include). This answer also depends on your language having first-class functions.

const U = f=> f (f)
const Y = U (h=> f=> f (x=> h (h) (f) (x)))

const strhead = s=> s.substring(0,1)
const strtail = s=> s.substring(1)

const worker = Y (f=> ({floor, basement})=> i=> txt=> {
  // txt is empty string; return answer
  if (txt === '')
    return {floor, basement}

  // first char in txt is '(', increment the floor
  else if (strhead (txt) === '(')
    return f ({floor: floor + 1, basement}) (i+1) (strtail (txt))

  // if basement isn't set and we're on floor 0, we found the basement
  else if (basement === null && floor === 0)
    return f ({floor: floor - 1, basement: i}) (i+1) (strtail (txt))

  // we're already in the basement, go down another floor
  else
    return f ({floor: floor - 1, basement}) (i+1) (strtail (txt))
}) ({floor: 0, basement: null}) (0)

{
  let {floor, basement} = worker('((((())(())(((()))((')
  console.log(floor)    //=> 6
  console.log(basement) //=> null; never reaches basement
}

{
  let {floor, basement} = worker(')(((((')
  console.log(floor)    //=> 4
  console.log(basement) //=> 0
}

{
  let {floor, basement} = worker('((())))')
  console.log(floor)    //=> -1
  console.log(basement) //=> 6
}

Answer 3

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