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?

Arrangement

adventofcode.com says it generates different input for each user, so you'd better just paste the input you got. I thought about pasting example input like "((((())))))(())(((()))((" with final floor 2 and basement 11, but maybe your original input is better because it informs how long the input string might be -- however it's not that relevant to the question, so it's up to you :) – Baggs

@Baggs Ahahaha, it never occured to me that link is per-login. Mine is 7009 characters long (which is why I sys.setrecursionlimit(10000)), so I guess I could include it as one long line, but the point was that the given implementations are correct. – Arrangement

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

Baggs

You are absolutely correct and this would be the solution for e.g. Haskell. The problem in the question is that Factor doesn't really have a concept of "return", it just keeps executing one word after another like Joy and so I'm not sure how to stop the recursion when I've found the solution. – Arrangement

but can't day1-worker be something like: <check if string is empty (string -- bool)> [<leave the result>] [<set the new arg values on stack> day1-worker] if – Baggs

I checked, yes it can be something like that :) edited the answer once more. watch out, it's a spoiler! does this answer your question about "stoping recursion"? – Baggs

"recursion is always the answer"... yes! ^_^ – Mimimimic

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

Sonora

Answer 3

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
}

Mimimimic

kudos for Y! I think it would be even more fun if you don't name it's result value "worker" but just apply it "in situ" -- as that's the power of Y. – Baggs

@Baggs well because I give a curried function to Y, it allows me to partially apply it. This way worker can be reused multiple times with varying input without having to recite the entire Y(........................) each time you want to compute another string of ((()))()(). Naming the partially applied result worker and having the power to use/read/understand it like a normal function is a lot more practical. And the fact that this is possible demonstrates an even greater power of Y. – Mimimimic

@Baggs I've edited my post to demonstrate the simple reusability of worker – Mimimimic