Уведомления

Группа в Telegram: присоединиться | Jabber-конференция сообщества: pythonua@conference.jabber.ru

#1 Фев. 13, 2018 14:05:32

polsovatel
Зарегистрирован: 2016-01-08
Сообщения: 29
Репутация: +  0  -
Профиль   Отправить e-mail  

Задачка про домино

Всем добрый день!
Изучаю 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”.

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

Офлайн

#2 Фев. 14, 2018 06:51:06

scidam
Зарегистрирован: 2016-06-15
Сообщения: 282
Репутация: +  34  -
Профиль   Отправить e-mail  

Задачка про домино

Я бы делал так:

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


Офлайн

#3 Фев. 14, 2018 11:10:32

polsovatel
Зарегистрирован: 2016-01-08
Сообщения: 29
Репутация: +  0  -
Профиль   Отправить e-mail  

Задачка про домино

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

Офлайн

Board footer

Модераторировать

Powered by DjangoBB

Lo-Fi Version