Advent of Code Day 1需要以一种或另一种形式循环在一长串括号上,如 ((((())(())(((()))((
等等。这个想法是(
上一层“楼”,)
下降一层,目标是打印
使用 for 循环的命令式解决方案很简单(以 Python 为例):
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)
递归函数式解决方案稍微复杂一些,但仍然不太难。
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))
这两个都给出了正确的输出
first basement floor index: 1795
final floor: 74
当反对我的挑战输入时。
除了第二个是愚蠢的,因为 Python 没有尾调用优化,但没关系
如何在 Factor 中实现其中任何一个?自从我开始使用 Factor 以来,这就是我一直困惑的事情。
我们不能只使用 for 循环,因为没有等价物允许我们在迭代之间保持可变状态。
我们可以使用递归解决方案:
: 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
太好了,那是一个骨架,但是
day-1-worker
的 body 里有什么东西? Factor 无法从递归调用中“提前返回”,因为无法反向运行程序,也没有返回的概念——这没有任何意义。我觉得也许递归不是 Factor 中这个问题的答案。如果是,我该如何停止递归?
最佳答案
您可以使用 cum-sum
组合器:
: 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
关于recursion - 如何停止递归?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/38151229/