Информация об изменениях

Сообщение Re[7]: Золотые слитки Гериона от 07.02.2016 23:21

Изменено 07.02.2016 23:59 Буравчик

Старый текст
Новый текст
Разница

Здравствуйте, Кодт, Вы писали:

К>А покажи свою программу, что ли.

Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.

Это программа для проверки решения, а не для поиска решения.

У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.

import qualified Data.Map as Map
import Data.List



-- максимальный вес, который выдерживает мешок
bag_max_weight = 11

-- слитки
boxes = [1..11]

-- список взвешиваний
actions = 
    [ [1, 2, 3, 4]
    , [1, 2, 3, 5]
    , [1, 2, 6]
    , [1, 3, 6]
    , [1, 4, 6]
    ]
    
-- запускаем
main = case check_permutations actions boxes of
    []  -> putStrLn "ok"
    d:_ -> putStrLn $ "bad solve\n" ++ show d



-- проверка, что мешок не порвется
good_actions ws = all (<= bag_max_weight) $ map sum ws

-- перестановка слитков во взвешиваниях
convert_actions mapper actions = map (map (mapper Map.!)) actions

-- пытаемся поменять веса слитков так, чтобы слиток 1кг стал другого веса и при всех взвешиваниях мешок не порвался
-- если нашли такой вариант, то увы... взвешивания не указывают однозначно на слиток 1кг
check_permutations actions boxes = 
       [ mapper          
       | new_boxes <- permutations boxes   -- список всех перестановок
       , mapper <- [Map.fromList $ zip boxes new_boxes]   -- dict (старый вес -> новый вес)
       , mapper Map.! 1 /= 1   -- нужны только такие перестановки, которые меняют вес 1кг слитка
       , actions_after_permutation <- [convert_actions mapper actions]   -- веса слитков после перестановки
       , good_actions actions_after_permutation   -- мешок не порвался после перестановки
       ]

	Два взвешивания
	`actions = [ [1, 2, 3, 5] , [1, 4, 6] ]`

import qualified Data.Map as Map
import Data.List



-- максимальный вес, который выдерживает мешок
bag_max_weight = 11

-- слитки
boxes = [1..11]

-- список взвешиваний
actions = 
    [ [1, 2, 3, 4]
    , [1, 2, 3, 5]
    , [1, 2, 6]
    , [1, 3, 6]
    , [1, 4, 6]
    ]
    
-- запускаем
main = case check_permutations actions boxes of
    []  -> putStrLn "ok"
    d:_ -> putStrLn $ "bad solve\n" ++ show d



-- проверка, что мешок не порвется
good_actions ws = all (<= bag_max_weight) $ map sum ws

-- перестановка слитков во взвешиваниях
convert_actions mapper actions = map (map (mapper Map.!)) actions

-- пытаемся поменять веса слитков так, чтобы слиток 1кг стал другого веса и при всех взвешиваниях мешок не порвался
-- если нашли такой вариант, то увы... взвешивания не указывают однозначно на слиток 1кг
check_permutations actions boxes = 
       [ mapper          
       | new_boxes <- permutations boxes   -- список всех перестановок
       , let mapper = Map.fromList $ zip boxes new_boxes   -- dict (старый вес -> новый вес)
       , mapper Map.! 1 /= 1   -- нужны только такие перестановки, которые меняют вес 1кг слитка
       , let actions_after_permutation = convert_actions mapper actions   -- веса слитков после перестановки
       , good_actions actions_after_permutation   -- мешок не порвался после перестановки
       ]

	Два взвешивания
	`actions = [ [1, 2, 3, 5] , [1, 4, 6] ]`