دومینو

دستورالعمل‌ها

یک زنجیره از دومینو بسازید.

روشی را محاسبه کنید که با آن بتوان مجموعه‌ای مشخص از سنگ‌های دومینو را طوری مرتب کرد که یک زنجیره‌ی دومینوی درست تشکیل دهند. در این زنجیره، نقطه‌های یک نیمه از هر سنگ باید با نقطه‌های نیمه‌ی مجاور سنگ کنارش یکسان باشد. به‌علاوه، نقطه‌های روی نیمه‌های سنگ‌هایی که همسایه ندارند (سنگ اول و آخر) باید با هم یکسان باشند.

برای مثال، با داشتن سنگ‌های [2|1]، [2|3] و [1|3] باید چیزی مثل [1|2] [2|3] [3|1] یا [3|2] [2|1] [1|3] یا [1|3] [3|2] [2|1] و از این قبیل محاسبه کنید، جایی که اعداد اول و آخر یکسان‌اند.

برای سنگ‌های [1|2]، [4|1] و [2|3] زنجیره‌ی حاصل معتبر نیست: اعداد اول و آخر [4|1] [1|2] [2|3] یکسان نیستند. 4 != 3

ممکن است برخی از موارد آزمون در حل یک زنجیره از سنگ‌های تکراری استفاده کنند؛ در این حالت فرض کنید از چند مجموعه‌ی دومینو استفاده می‌شود.

پیاده‌سازی

تنها یک تابع Go به اسم MakeChain تعریف کنید که یک برش از دومینوها را می‌پذیرد و تلاش می‌کند یک زنجیره‌ی معتبر از دومینوها بسازد.

MakeChain باید امضای زیر را داشته باشد:

type Domino [2]int

func MakeChain(input []Domino) (chain []Domino, ok bool)

نتیجه‌ی منطقی ok مشخص می‌کند که آیا فهرست دومینوهای ورودی می‌تواند در قالب یک زنجیره‌ی معتبر چیده شود یا نه. فهرست ورودی خالی معتبر در نظر گرفته می‌شود و یک دومینوی تنها که دو طرفش یکسان است هم معتبر است.

نتیجه‌ی chain برشی است از صفر یا چند دومینو که به ترتیبی چیده شده‌اند که زنجیره‌ی معتبر را نشان می‌دهد. پذیرفتنی است (و انتظار هم می‌رود) که دومینوهای input لازم باشد بچرخند تا هر طرفشان با دومینوی مجاورشان در زنجیره مطابقت کند. دومینوهای ابتدا و انتهای زنجیره هم باید از طرف بیرونی با یکدیگر مطابقت داشته باشند.

اگر برش ورودی دومینوها نتواند در قالب یک زنجیره‌ی معتبر چیده شود، MakeChain می‌تواند برای نتیجه‌ی chain مقدار nil را برگرداند، اما باید برای نتیجه‌ی ok مقدار false را برگرداند.

از آنجا که ممکن است برای یک فهرست ورودی بیش از یک چینش معتبر وجود داشته باشد، وقتی ok برابر «درست» است، برنامه‌ی آزمون فقط اعتبار زنجیره را بررسی می‌کند.