6

コードの出現 1 日目では、何らかの形式で、長い括弧の文字列((((())(())(((()))((などをループする必要があります。アイデアは、(1 つの「フロア」を上って、)1 つのフロアを下って、目的は印刷することです。

  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にはテールコールの最適化がないため、2番目のものはダムですが、気にしないでください

これらのいずれかを 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

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 ソリューションです。申し訳ありませんが、これがどのように Factor に変換されるのかわかりません。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 に答える