Сообщение Re[7]: Золотые слитки Гериона от 07.02.2016 23:21
Изменено 08.02.2016 8:36 Буравчик
Здравствуйте, Кодт, Вы писали:
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 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 -- список всех перестановок
, 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 -- мешок не порвался после перестановки
]
Два взвешивания | |
| |
Re[7]: Золотые слитки Гериона
Здравствуйте, Кодт, Вы писали:
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
UPDATE: сделал небольшой рефакторинг, чтоб понятней было
К>А покажи свою программу, что ли.
Да мне не жалко. Но как всегда запутано все, сделано наспех. Добавил комментариев.
Это программа для проверки решения, а не для поиска решения.
У нас даны взвешивания. Для опровержения решения пытаемся найти контрпример — такие веса слитков, которые проходят эти взвешивания и при этом слиток 1кг будет иметь другой вес. Проверяются все перестановки весов слитков (11! вариантов). Выводится "ок" или контрпример — как надо поменять веса.
import qualified Data.Map as Map
import Data.List
-- список взвешиваний
actions =
[ [1, 2, 3, 4]
, [1, 2, 3, 5]
, [1, 2, 6]
, [1, 3, 6]
, [1, 4, 6]
]
-- запускаем
main = find_kontrprimer actions of
Nothing -> putStrLn "ok"
Just mapper -> putStrLn $ "bad solve\n" ++ show mapper
-- максимальный вес, который выдерживает мешок
bag_max_weight = 11
-- слитки
boxes = [1..11]
-- проверка, что мешок не порвется
bag_unhurt acts = all (<= bag_max_weight) $ map sum acts
-- перестановка слитков во взвешиваниях
convert_boxes acts mapper = map (map (mapper Map.!)) acts
-- список перестановок весов слитков, список словарей (старый вес => новый вес)
mappers = [ Map.fromList $ zip boxes new_boxes | new_boxes <- permutation boxes]
-- проверка, что данная перестановка является контрпримером для взвешиваний
-- т.е. при всех взвешиваниях мешок не порвался и это стало возможным когда слиток 1 имеет вес отличный от 1кг
is_kontrprimer mapper acts = (mapper Map.! 1 /= 1) && (bag_unhurt $ convert_boxes acts mapper)
-- поиск контрпримера
find_kontrprimer acts = find is_kontrprimer mappers
UPDATE: сделал небольшой рефакторинг, чтоб понятней было