Найти - Пользователи
Полная версия: Задачка про домино
Начало » Центр помощи » Задачка про домино
1
polsovatel
Всем добрый день!
Изучаю Python и наткнулся на задачку на сайте Checkio.
Попытался решить ее используя два словаря, не вышло. Подскажите пожалуйста, в каком направлении идти? Вот вообщем -то задача:

У вас есть коробка с домино. Костяшки домино состоят из двух цифр от 0 (пустая) до 6. Костяшки не имеют направления и 1-6 это тоже самое, что 6-1. Стандартный набор состоит из 28 разных костяшек - все комбинации пар цифр.

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

Например, вам достались эти костяшки:
1-5, 2-5, 3-5, 4-5, 3-4
Тогда вы можете построить такие полные цепочки:
1-5, 5-3, 3-4, 4-5, 5-2
1-5, 5-4, 4-3, 3-5, 5-2
Ваша задача в этой миссии - сосчитать, сколько полных цепочек вы можете составить, используя все заданные костяшки домино.

Примечание. Цепочки должны быть уникальны. Перевернутая цепочка не считается уникальной: “1-2, 2-3, 3-4, 4-5” и “5-4, 4-3, 3-2, 2-1” - это одна и та же цепочка.

Входные данные: Строка с описанием костяшек домино. Например, “5-4, 4-3, 3-2, 2-1”.

Выходные данные: Целое число. Максимальное число полных цепочек, которые вы можете построить, используя все костяшки.
scidam
Я бы делал так:

1) Написал бы функцию, которая на вход принимает строку, а на выходе выдает массив пар – каждая пара при этом характеризуют костяшку домино. Более того, всегда x1>= y1, т.е. первое число в паре не меньше второго.
2) Написал бы функцию, которая проверят является ли данный набор полной цепочкой
3) И если не вдумываться в алгоритм, то взял бы из itertools функцию, которая генерирует все перестановки и проверял бы каждую функцией из п. 2. подсчитывал число таких случаев.
Можно, конечно, улучшить алгоритм, думаю, просматривая не все перестановки.


polsovatel
scidam
Я бы делал так:1) Написал бы функцию, которая на вход принимает строку, а на выходе выдает массив пар – каждая пара при этом характеризуют костяшку домино. Более того, всегда x1>= y1, т.е. первое число в паре не меньше второго.2) Написал бы функцию, которая проверят является ли данный набор полной цепочкой3) И если не вдумываться в алгоритм, то взял бы из itertools функцию, которая генерирует все перестановки и проверял бы каждую функцией из п. 2. подсчитывал число таких случаев. Можно, конечно, улучшить алгоритм, думаю, просматривая не все перестановки.
Большое спасибо!
This is a "lo-fi" version of our main content. To view the full version with more information, formatting and images, please click here.
Powered by DjangoBB