Монеты и взвешивания

[thedeemon]

Пару недель назад увидел у mr_aleph задачку: есть 12 одинаковых с виду монет, одна из них фальшивая - отличается по весу, но неизвестно в какую сторону, нужно за максимум 3 взвешивания на чашечных весах ее найти. Если знать легче она или тяжелее, то решается очень просто, но вот без этой информации у меня быстро найти решение не получилось. Потом еще несколько раз иногда возвращался к ней мыслями, но так и не решил, даже при поддержке других членов семьи.

mr_aleph тогда написал: Но потом меня посетила интересная мысль, что (мета)задача написать программу, которая строит стратегию поиска фальшивой монеты из N монет за M взвешиваний, это хороший программисткий этюд.

С этим я полностью согласен, поэтому решил написать программу, и пусть японский компьютер мне придумывает аргоритм. Задачка получилась довольно интересная, ведь не сразу ясно как именно описать предметную область и как должен выглядеть ответ: программа должна не найти монету, а по заданному числу монет и взвешиваний найти алгоритм решения задачи. В итоге у меня получилось такое решение из сотни строк Окамла с активным применением функций сильно высокого порядка и ленивых вычислений. Для 4 монет и 2 взвешиваний результат работы выглядит так:

Weigh [1 and 2]:
 if left heavier then 
  last weighting [2 and 4]:
   if left lighter then fake is 2
   if equal then fake is 1
 if left lighter then 
  last weighting [2 and 4]:
   if left heavier then fake is 2
   if equal then fake is 1
 if equal then 
  last weighting [2 and 4]:
   if left heavier then fake is 4
   if left lighter then fake is 4
   if equal then fake is 3

А для 9 монет и 3 взвешиваний вот так. Решение исходной задачки с 12 монетами программа выдала вот такое, неоптимальное но вроде рабочее. При поиске решения у меня плохо учитывается симметрия ситуаций, поэтому с ростом числа монет время работы растет очень быстро: решение для 8 монет находится за 0,2 секунды, для 9 - за 1,6с, для 10 - за 38с, а про 12 монет железяка думала 5 часов. :)

В коде очень порадовало место, где делаются выводы из очередного взвешивания:

let not_heavy (l,n,h) = (l,n,false);;
let not_light (l,n,h) = (false,n,h);;
let is_normal (l,n,h) = (false,true,false);;

let eval st w outcome = (* определение нового состояния из заданных состояния, взвешивания и результата *)
  let f = match outcome with
    | LeftLighter -> (function Left -> not_heavy | Right -> not_light | Out -> is_normal)
    | LeftHeavier -> (function Left -> not_light | Right -> not_heavy | Out -> is_normal)
    | Equal       -> (function Left  | Right -> is_normal | Out -> identity) in
  List.map2 f w st;;

Если взвешивание показало, что левая чашка легче, значит на левой не может быть тяжелой монеты, на правой не может быть легкой, а все неучаствовавшие во взвешивании монеты гарантировано нормальные. Аналогично для симметричного случая. Если весы показали равенство, значит на весах все монеты нормальные, а про остальные ничего нового сказать нельзя. Здесь f - функция, которая принимает позицию монеты и возвращает другую функцию, которая из старого состояния информации о монете делает новое. С учетом карринга, это все равно что одна функция с двумя параметрами - позицией монеты и старым состоянием, возвращающая новое состояние. Так она и используется.

Comments

[mr-aleph.livejournal.com]

кстати, в комментариях yelagin87 упомянул, что задача решается в общем виде, поэтому можно написать не подборное решение =)

[deni-ok.livejournal.com]

Ну это почти коды Хэмминга, только троичные. Классическое решение Дайсона описано здесь
http://kvant.mirror1.mccme.ru/1979/10/kak_obnaruzhit_falshivuyu_mone.htm

Используя эту теорию (и ограничиваясь только предельными для каждого числа взвешиваний случаями)

-- findCoin ищет фальшивую монету в списке xs длины (3^n-3)/2
-- все элементы списка, кроме одного, д.б. одинаковыми
findCoin xs n = case (elemIndex lmarker rm, elemIndex rmarker rm, 2*length xs) of 
                  (Just idx,  Nothing, n) -> (idx, "Heavy")
                  (Nothing,  Just idx, n) -> (idx, "Light")
                  (_, _, _)               -> error "Wrong attempt :)"
  where lmarker = map (\x -> 2-x) rmarker
        rmarker = makeMarker xs n 
        rm = rightMarkers n

-- список правых маркеров
rightMarkers 2 = [[0,1],[1,2],[2,0]]
rightMarkers n = [xs ++ [y] | xs <- prev, y <-[0,1,2]] ++ 
                 [head xs : xs | xs <- prev, 
                    if n>3 
                    then head xs == head (tail xs) 
                    else True]
                  where prev = rightMarkers (n-1)

-- makeMarker монтирует маркер фальшивой монеты
-- (правый для лёгкой и левый для тяжелой sic! в статье наоборот)
-- weigh сравнивает "веса" двух списков
-- takeCoins берет из списка xs подмножества M(i,0) и M(i,2) через
-- их индексы в списке правых маркеров
makeMarker xs n = map (weigh . takeCoins xs n) [0..(n-1)]
   where weigh (xs, ys) = fromEnum $ compare (sum xs) (sum ys)
         takeCoins xs n i = (elems i 0 rm, elems i 2 rm)
         elems i leg = map (xs !!) . findIndices ((== leg) . (!! i))
         rm = rightMarkers n

Проверка

> findCoin [3,3,3,3,3,7,3,3,3,3,3,3] 3
(5,"Heavy")
> findCoin (replicate 12 3 ++ 2 : replicate 26 3) 4
(12,"Light")

[thedeemon.livejournal.com]

Я специально не стал гуглить решения, хотелось самому сначала что-то найти. После этого уже нашел простое универсальное решение в СУНЦовых лекциях Андреевой, оно, кажется, чуть лучше, чем у Дайсона - за 3 взвешивания решает до 13 монет, за 4 - 40 и т.д.

[deni-ok.livejournal.com]

Не, тут проблема в точной формулировке. Если мы должны определить, легче или тяжелее фальшивая монета, то за 3 взвешивания не более 12, за 4 - не более 39 и т.д. А если это не так, то 13, 40 и т.д. Алгоритм Дайсона легко модифицируется простым откладыванием в сторону одной монетки: если при всех взвешиваниях получилось ровно (маркер из одних 1), то фальшивая - она, но мы не знаем, легче она или тяжелее.

много добър

[(Anonymous)]

Трябва да проверя:)