Професионална програма
Loading...
netherblood avatar netherblood 95 Точки

[Homework] Combinatorial Algorithms - Snakes*

Аз я докарах до тука:
http://pastebin.com/Sf4g7t3k

Разбрах, че може с алгоритъм който пропуска дубликати, или с ротация на матрица да се отрежат дубликати, но нямам идея как да го имплементирам като код.
Ако някой може да ми обясни задачата, ще съм му много благодарен.

 

Тагове:
0
Структури от данни и алгоритми 12/04/2016 13:32:42
a_rusenov avatar a_rusenov 1103 Точки
Best Answer

Супер си се сетил с матрицата да си следиш да не се захапе змията. :) Това, което остава е за всяка генерирана поредица да генерираш и нейните възможни варианти при ротации/флипове. Най-лесно това става като работиш със стрингове, а не да ротираш/флипваш цели матрици. Например, SRRD при хоризонтален флип става SRRU (просто обръщаш U с D и обратно). Ротация по часовниковата стрелка е на същия принцип, само че там посоките се променят така - R -> D, L -> U, D -> L, U -> R.

Всички възможни флипове/ротации на 1 поредица ги вкарваш в един HashSet<string>. Когато генерираш нова поредица и нейните флипове/ротации -> проверяваш дали вече няма такава в хешсета. И това работи, но дава само за 50/100, защото при достатъчно голямо n програмата заспива.

И тука идва моментът как да оптимизираме:

След достатъчно рисунки забелязваме, че за почти всяка 1 поредица генерираме още 8 чрез ротации/флипове. Почти всички от тях са дубликати по условие и е излишно да въртим през тях. Затова извикваме първоначално GenSnake от SR... нататък (змията SR е началото на рекурсията). Така си спестяваме генерирането на SU..., SL... и SD... змии, които и без това не ни трябват (задраскани са в картинката).

От тук нататък единствения друг вариант, който генерираме е хоризонтален флип на текущия (напр. SRRU -> SRRD). Защо? Защото само до него можем да достигнем, когато генерираме змии, започващи с SR...

До момента да обобщим: когато генерираме 1 редица, генерираме и флипнатия вариант. Ако в хешсета вече съществува 1 от двете -> редицата се дублира и нищо не правим. В противен случай, добавяме и вариантите на текущата редица в сета и я принтираме.
---------
Остана още едно нещо - възможно е да генерираме поредици като SRDD (дублира се с SRRU). Обаче от SRRU само с ротации/флипове не можем да стигнем до SRDD. Причината е, че взимаме предвид началото S и посоките, в които се движим. По условие обаче това са 2 еднакви поредици. 

  • Как от SRRU получаваме SRDD тогава? Обръщаме реда на на SRRU и получаваме SDLL (виж картинката). След този reverse имаме вариант, получен в следствие на ротации на SRDD. Затова ротираме получената фигура надясно (по часовниковата стрелка), докато тя не започва с SR... (Защо? Защото само тогава ни интересува. Контрапример: ако я добавим като SDLL тя е недостижима от текущото генериране на змии).

И в крайна сметка, освен оригиналния и флипнатия, запазваме и този reversed вариант. Това са трите варианта, които ни интересуват за всяка една змия, когато тя започва с SR... Всички останали са ненужни.

Като цяло доста трябва да се порисува, за да се схване идеята. Ако не е станало ясно, пишете да доразяснявам. И ако някой има по-добър/оптимален алгоритъм, нека споделя. :)

8
13/04/2016 02:49:11
netherblood avatar netherblood 95 Точки

Страхотно обяснено и с картинка какво повече да иска човек.

Благодаря много Наско!

2
netherblood avatar netherblood 95 Точки

Един бърз и може би глупав въпрос:
Защо SRDD не се смята за уникална комбинация?
Моето решение генерира 5 комбинации за n = 4 а примерите показват 4.

Ето го и то, все още неоптимизирано:
http://pastebin.com/YkziJtbz

1
a_rusenov avatar a_rusenov 1103 Точки

SRDD е SRRU ротирано 1 път наляво + reverse.

0