4 февр. 2010 г.

Задачка: Робот на бесконечной лестнице

На бесконечной лестнице находится робот у которого есть API - подняться вверх. Однако не всякая попытка поднятся вверх заканчивается успехом - робот может как поднятся на верх на 1 ступеньку - функция API вернёт 1 - или съехать ниже на 1 ступеньку - возвращаемое значение -1.

Не используя локальных переменных, циклов и формальных параметров функции написать алгоритм, поднимающий гарантированно робота на 10 ступеней вверх

Задачка скорее разминка для хвоста в целях попрактиковаться на clojure

18 комментариев:

Unknown комментирует...

Очевидно, что никаких "гарантированно" быть при такой постановке задачи не может. Достаточно рассмотреть случай, когда вызов всегда обламывается... Никакой алгоритм не спасёт...

Нужна вероятностная формулировка условия.

migmit комментирует...

void upOneStep(){
if (!robotApiUp()){
upOneStep();
upOneStep();
}
}
void main(){
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
upOneStep();
}

zahardzhan комментирует...

http://gist.github.com/305420

(defn up []
(int (Math/pow -1 (inc (.nextInt (new java.util.Random) 2)))))

(defn up-10 []
(->> (repeatedly up)
(take 10)
(apply +)))

(first (filter (partial = 10) (repeatedly up-10)))

Михаил комментирует...

Прикольная задача, но никто не дал её решения на Java. Вот моё решение:
http://code.google.com/p/khomutetskiy-project/source/browse/trunk/UNIVER/src/ru/susu/tasks/Robot.java
Роботу дается слегка больший шанс шагнуть вперед, чем назад. Иначе переполнение стека возникает.
Конечно, это не хвостовая рекурсия :-)

Vladimir Dolzhenko комментирует...

@Михаил - ваше решение на java ничем принципиально не отличается от решения migmit'а - решение, для любого императивного языка - такое же можно написать и на javascript, perl, python и т.п, и на clojure в т.ч.

Другое дело - решение Захарджан'а - true functionally programming approach - и действительно бомба.

Vladimir Dolzhenko комментирует...

@Захарджан:

идея - супер, но в реализации ошибка:

попробуйте проверить алгоритм с такую заранее известной последовательностью движений робота: [-1 1 1]

т.е.

(def position (atom 0))

(def movements (cycle [-1 1 1]))
(defn up []
( do
(reset! position (inc @position))
(nth movements @position)
)
)

Unknown комментирует...

Владимир, интересна всё таки формальная постановка задачи ^^'

Vladimir Dolzhenko комментирует...

@e.v.e

можно считать, что вероятность подняться у робота больше, чем опустится - нмв - это разумное предположение.

Unknown комментирует...

@Владимир Долженко,

а гарантировано, что означает?

с единичной вероятностью?

Vladimir Dolzhenko комментирует...

что робот окажется на ровно на 10 ступенек выше, чем был в начале движения.

Михаил комментирует...

@Владимир Долженко
Принципиальное отличие состоит в том, что мое решение работает, в отличии от решения migmit(по-моему это большая разница). Принципиальное ограничение моего решения - это глубина стека рекурсии. На данный момент я не могу сказать можно ли сделать имитацию хвостовой рекурсии на императивном языке при заданных ограничениях на использование циклов, переменных и параметров функции. Я подумаю на этот счет :-)
Кстати, именно сейчас изучаю ФП по видео-лекциям на http://www.intuit.ru/department/pl/funcprog/.

Vladimir Dolzhenko комментирует...

@Михаил

может тогда объясните смысл условия
if (trulyUp() == 1) ?

если единственная точка выхода из trulyUp это return 1;

Михаил комментирует...

@Владимир Долженко
Тупанул... Решение у migmit ведь верное. Изменил свой код.

zahardzhan комментирует...

Спасибо, автор, ты наставил меня на путь истинный. Лови однострочник:

http://gist.github.com/305420

(first (filter (partial = 10) (iterate #(+ % (up)) 0)))

Vladimir Dolzhenko комментирует...
Этот комментарий был удален автором.
Vladimir Dolzhenko комментирует...

@Захарджан

безусловно - эта идея - the best, если чуть приукрасить код (на 1 оператор меньше)

(take-while #(< % 10) (iterate #(+ % (up)) 0))

Light комментирует...

Хотел быстро написать однострочник на python. Ан нет, одной функции для реализации чистого ФП не хватает. Но если бы она была, выглядело это б примерно так.

map(lambda i:i, takewhile(lambda x: x <10, ireduce(lambda x,y: x+y, imap(lambda x: x(), repeat(api)))))


Где imap, repeat, takewhile - функции модуля itertools, а ireduce определяется следующим образом:

def ireduce(func, iterable, init=None):
if init is None:
iterable = iter(iterable)
curr = iterable.next()
else:
curr = init
for x in iterable:
curr = func(curr, x)
yield curr

ps правда стоит учесть что эти функции в любом случае реализуются через циклы, либо на уровне библиотек питона, либо на уровне c-реализации.

Анонимный комментирует...

До кучи haskell вариант:

import System.Random
import Control.Monad

up = do
r <- randomIO
print ("doing up: " ++ show(r :: Bool))
return r

upmultiM 0 = return ()
upmultiM steps = do
u <- up
if u then upmultiM (steps - 1) else upmultiM (steps + 1)

main = upmultiM 10