Как перестать повторяться?

Появление первого дня кода требует зацикливания в той или иной форме над длинной строкой скобок, например ((((())(())(((()))(( и т.д. Идея в том, что ( поднимается на один "этаж", ) спускается на один этаж, и цель состоит в том, чтобы напечатать

  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.

Мы не можем просто использовать цикл 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? Фактор не имеет никакого способа "досрочного возврата" из рекурсивного вызова, потому что нет способа запустить программу в обратном порядке и нет понятия возврата - это не имеет никакого смысла.

У меня такое чувство, что рекурсия не является ответом на этот вопрос в Факторе. Если это так, как я могу прекратить повторение?

Источник

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 дополнительных маленьких шагов не имеет большого значения, даже если вы заботитесь о производительности.

Удачи!

Отредактируйте: что касается вашего вопроса о рекурсии в факторе, взгляните на функцию Аккермана в факторе и последовательность Фибоначчи в факторе, и вы должны получить представление о том, как "разорвать петлю". На самом деле единственная проблема в мышлении (освободить себя от императивной модели:)); в функциональных языках нет "возврата", только конечное значение, и языки на основе стека, о которых вы говорите, являются другой вычислительной моделью того же самого (вместо того, чтобы думать о сворачивании дерева, мы думаем о "выталкивании и извлечении из стеков" " - что, кстати, является общим способом реализации первого).

Изменить: (СПОЙЛЕР!) Я установил фактор и начал играть с ним (довольно приятно), для первого вопроса (вычисление окончательного балла) возможное решение

    : 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 было бы разумнее, чем вложение, если s).

Источник

Вы могли бы использовать 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
Источник

РЕДАКТИРОВАТЬ

Я изначально неправильно понял, как вы вычисляли 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-комбинатора и только 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
}

Источник
Другие вопросы по тегам