6

代码第一天的出现需要以一种或另一种形式循环在一长串括号中，例如((((())(())(((()))((等。这个想法是(上一层“楼层”，)下一层，目标是打印

  1. 楼层号为负的字符串中的第一个索引，并且
  2. 找到字符串末尾时的最后一层。

带有 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什么？Factor 没有任何方法可以从递归调用中“提前返回”，因为没有办法反向运行程序，也没有返回的概念——这没有任何意义。

我觉得递归可能不是 Factor 中这个问题的答案。如果是，我如何停止递归？

4

3 回答 3

3

首先，递归始终是答案 :) 因为这是一个挑战（而且我不知道因素），所以只是一个提示：在您的 python 解决方案中，您使用了副作用来打印地下室的第一层。完全没必要！您也可以使用basemet参数来保存楼层号，如下所示：

    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)

所以现在你得到

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

或者，您也可以编写 2 个函数，第一个寻找地下一层的索引，另一个只计算最后一层。即使您确实关心性能，拥有 <2000 个额外的小步骤也不是什么大不了的事。

祝你好运！

编辑：关于你关于因子递归的问题，看看因子中的阿克曼函数和因子中的斐波那契数列，你应该知道如何“打破循环”。实际上唯一的问题是思考（从命令式模型中解放自己:)）；在函数式语言中没有“返回”，只有最终值，而您提到的基于堆栈的语言是同一事物的其他计算模型（而不是考虑折叠一棵树，而是考虑“向/从堆栈推入和弹出” "——顺便说一句，这是实现前者的常用方法）。

编辑：（剧透！） 我安装了Factor并开始使用它（非常好），对于第一个问题（计算最终分数），一个可能的解决方案是

    : 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 ;

所以现在你可以写一个类似的来计算地下室的索引，或者（这会更酷！）修改它，以便它也管理索引和地下室......（可能使用cond比嵌套if s 更明智）。

于 2016-07-01T18:21:59.270 回答
3

您可以使用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
于 2016-07-03T14:17:40.737 回答
2

编辑

我最初误读了您计算basement价值的方式。我已经更新了下面的答案

这是一个 JavaScript 解决方案。抱歉，我不知道这如何转换为因子。reduce是一个迭代过程

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

上面的答案依赖于一些可能在您的语言.split中.reduce不存在的内容。这是另一个使用 Y-combinator 的解决方案，并且只有substring内置的（大多数语言都包括）。这个答案还取决于您的语言是否具有一流的功能。

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
}

于 2016-07-02T06:36:07.007 回答