4 февр. 2010 г.

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

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

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

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

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

e.v.e комментирует...

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

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

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

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

Захарджан комментирует...

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
Роботу дается слегка больший шанс шагнуть вперед, чем назад. Иначе переполнение стека возникает.
Конечно, это не хвостовая рекурсия :-)

Владимир Долженко комментирует...

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

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

Владимир Долженко комментирует...

@Захарджан:

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

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

т.е.

(def position (atom 0))

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

e.v.e комментирует...

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

Владимир Долженко комментирует...

@e.v.e

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

e.v.e комментирует...

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

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

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

Владимир Долженко комментирует...

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

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

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

Владимир Долженко комментирует...

@Михаил

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

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

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

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

Захарджан комментирует...

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

http://gist.github.com/305420

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

Владимир Долженко комментирует...
Этот комментарий был удален автором.
Владимир Долженко комментирует...

@Захарджан

безусловно - эта идея - 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