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

[deniok]

Вынесу-ка коммент как пост.

Во френдленте потихоньку обсуждается классическая задача про 12 монеток с одной фальшивой среди них, которую нужно найти за 3 взвешивания (и определить тяжелее она или легче настоящих). И ее обобщение на случай m монеток и n взвешиваний.

На самом деле это почти коды Хэмминга, только троичные. Там мы ищем побитый бит, используя контрольные биты (хранящие значения некоторых разумных функций от контролируемого). Здесь мы ищем поддельную монетку, используя значения некоторых разумных взвешиваний (разумных функций от взвешиваемого).

Классическое решение Дайсона описано здесь. Коротко:

• Каждой монетке присваивается некоторый маркер (в виде кода в троичной системе счисления). Правильное кодирование - главный залог успеха.


• Значение каждого разряд маркера монетки (0,1 или 2) показывает, на какую чашу весов класть эту монетку (левую, не класть, правую) при взвешивании с номером равным номеру разряда.


• Результаты взвешиваний образуют последовательность значений троичного разряда (склонилось влево - 0, не склонилось - 1, вправо - 2).


• Фокус в том, что, при "правильном" исходном кодировании, эта последовательность значений совпадает с маркером фальшивой монетки.

Я захаскеллировал это добро (ограничиваясь только предельными для каждого числа взвешиваний случаями, то есть (3^n-3)/2 монеток для n взвешиваний)

-- findCoin ищет фальшивую монету в списке xs длины (3^n-3)/2 за n взвешиваний
-- все элементы списка, кроме одного, д.б. одинаковыми
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 монтирует правый маркер фальшивой монеты
-- 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")

Есть ещё довольно мутная статья в английской википедии, откуда, однако, можно при некотором усердии почерпнуть знания о связи этих монеток с теорией Шенона и кодами Хэмминга.

UPD: Как справедливо заметили в комментах, алгоритма не видно, а найти в списке отличающееся число можно короче. Стоило бы выделить

coinsNumbers n i = (elems i 0 rm, elems i 2 rm)
   where elems i leg = findIndices ((== leg) . (!! i))
         rm = rightMarkers n

возвращающий номера монет, которые нужно класть на чашки весов при i-ом взвешивании

*Coins> coinsNumbers 3 0
([0,1,2,9],[6,7,8,11])
*Coins> coinsNumbers 3 1
([6,7,8,9],[3,4,5,11])
*Coins> coinsNumbers 3 2
([0,3,6,11],[2,5,8,10])

а затем, записав результаты взвешиваний в троичной системе, искать номер фальшивой монетки как индекс соответствующего правого маркера в списке

*Coins> rightMarkers 3
[[0,1,0],[0,1,1],[0,1,2],[1,2,0],[1,2,1],[1,2,2],[2,0,0],[2,0,1],[2,0,2],[0,0,1],[1,1,2],[2,2,0]]

То есть сам алгоритм задается функциями rightMarkers и coinsNumbers, а findCoin и makeMarker - это просто тестовое окружение. Последнюю теперь можно переписать, выразив её через coinsNumbers:

makeMarker xs n = map (weigh . takeCoins xs n) [0..(n-1)]
   where weigh (ys, zs) = fromEnum $ compare (sum ys) (sum zs)
         takeCoins xs n i = (map (xs !!) $ fst (cn i), map (xs !!) $ snd (cn i))
         cn i = coinsNumbers n i

Comments

[thedeemon.livejournal.com]

Имплементить чужое решение не так интересно, как искать свое. :)

[deni-ok.livejournal.com]

Я просто помнил про эту статью :)

[thedeemon.livejournal.com]

Решением это можно назвать с натяжкой. Получили функцию, которая из списка чисел находит отличающееся, ее можно и проще реализовать. ;)
Программа должна либо выдать алгоритм, оперирующий весами и монетами (положить такие-то монеты туда-то, если результат такой, сделать то-то), либо, что уже менее интересно, реализовать такой алгоритм в этих терминах (а не сравнивать sum xs, где каждый из xs известен).

[deni-ok.livejournal.com]

Да, немножко мутно написал. Алгоритм там по ходу монтируется, а затем используется. Стоило бы выделить

coinsNumbers n i = (elems i 0 rm, elems i 2 rm)
   where elems i leg = findIndices ((== leg) . (!! i))
         rm = rightMarkers n

возвращающий номера монет, которые нужно класть на чашки весов при i-ом взвешивании

*Coins> coinsNumbers 3 0
([0,1,2,9],[6,7,8,11])
*Coins> coinsNumbers 3 1
([6,7,8,9],[3,4,5,11])
*Coins> coinsNumbers 3 2
([0,3,6,11],[2,5,8,10])

а затем, записав результаты взвешиваний в троичной системе, искать номер фальшивой монетки как индекс соответствующего правого маркера в списке

*Coins> rightMarkers 3
[[0,1,0],[0,1,1],[0,1,2],[1,2,0],[1,2,1],[1,2,2],[2,0,0],[2,0,1],[2,0,2],[0,0,1],[1,1,2],[2,2,0]]

(или левого, превратив нули в двойки и наоборот в случае неудачного первого поиска). Сейчас пост поправлю.