Софтуерно Инженерство
Loading...
+ Нов въпрос
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

[Homework] Алгоритми - Combinatorial Algorithms - Problem{7} - Cubes

Някой би ли ли споделил решение на тази задача. Малко май прилича на предната задача, понеже вероятно пак ще има ротации, но все пак нещо не се сещам как да подходя.

Благодаря предварително.

Filkolev avatar Filkolev 4501 Точки
Best Answer

Понеже това е триизмерна фигура, може да я въртиш по три оси. Съответно може да направиш три метода, които въртят даден куб по трите оси. За всеки куб ако завъртиш по три пъти по всяка от осите ще получиш всички възможни производни на въпросния куб (9) - пазиш тези в списък и сравняваш с комбинациите, които трябва да провериш. А въпросните комбинации за проверка може да получиш чрез пермутиране (без повторение) на входния стринг (задача, която трябва вече да е позната).

В моето решение съм сложил доста криптични методи за въртене, работя с масив от символи и просто казвам при дадената посока на завъртане кой елемент къде отива - примерно:

temp[0] = currentCube[3];
temp[1] = currentCube[0];

и т.н. Ти разбира се може да ползваш други структури, но подходът би трябвало да работи независимо от начина, по който предпочетеш да го имплементираш.

3
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Мерси, Фил. Докарах я донякъде. Т.е. или по-малко отколкото трябва да са комбинациите или повечеsmiley.
Нещо и трудно се дебъгва тази задача. Ако ти се занимава, може да хвърлиш едно око на кода.

Цък.

0
verito898 avatar verito898 270 Точки

Някой има ли работещо решение на тази задача. И аз мисля, че трябва да са пермутации без повторения, но  при входни данни {1 1 2 2 2 3 3 3 3 3 3 3}  генерираните ротации са общо 7920, а output-a е 340 . Как изхода ще се сведе до такова малко число при положение, че вариантите за въртене на куб-а са винаги 24 ?

Код на текущото решение : http://pastebin.com/ThxZkGJc

Линк към задачата в judge : https://judge.softuni.bg/Contests/Practice/Index/114#0

На кратко:  взимам входните данни от тях генерирам куб и го завъртам по всички възможни начини, като запазвам тези стойности. След това генерирам всички възможни разбърквания и сравнявам ако текущото разбъркване и някоя от пермутациите на куба съвпадат, ако не съответно увеличавам output-a ии т.н.

Ще съм благодарна ако някой помогне :))) 

0
28/08/2016 09:41:54
Valleri avatar Valleri 292 Точки

За решаването много ми помогна тази страница: http://www.euclideanspace.com/maths/discrete/groups/categorise/finite/cube/
Излиза, че възможните пермутации  са 23. Написах си 23 метода за всяка една пермутация и ги добавих към Хешсет, и преди да добавя някой куб в резултатите проверявам дали не е в генерираните.
Решение:
https://github.com/Vallerious/Algorithms/blob/master/Algo/Cubes.cs

1
viraco4a avatar viraco4a 28 Точки

Ще предложа още едно решение: https://pastebin.com/4324Zs0E 

Почти един ден се мъчих, но логиката ми се струва интуитивна:

1) Дефинирам клас Cube, който има 12 пропърита - 12-тте edge-a на куба, кръстени по възможно най-ясен начин (FrontTop, FrontLeft... etc.)

2) Имам масив int[], в който ще пермутирам с повторения цветовете, също така HashSet, пазещ уникалните ми решения и отделен HashSet, в който пазя всички завъртени варианти при получен от пермутацията куб

3) Самото въртене съм го разделил на въртене по azimuth, elevation и roll (за да мине последният тест, който е много тегав, подозирам с вход 1 1 1 2 2 2 3 3 3 4 4 4, въртя само 3-пъти по az и el, което е достатъчно, макар че не звучи интуитивно, а по roll си въртя 4 пъти). И съм го направил супер ръчно: представям си въртене например по азимут и връщам куб, в който edge по edge съм го завъртял. Аналогично за другите въртенета. Не е много умно, но по-умно не се сетих, а според мен е по-лесно и интуитивно от тия 23 пермутации, които колегата Valleri предлага (нищо лично, много добро решение, в началото и аз бях тръгнал по този начин, но като видях, че друг го е направил и му е отнело 500+ реда се отказах)

4) За да сравнявам макс бързо и лесно кубовете ми, трансформирам всички параметри със стрингбилдър в стрингове, които фактически пазя в hashset-a

Наистина бих се радвал да видя някакво авторско или що-годе интелигентно решение, най-вече за избора на колекция, в която да се пазят кубовете. Някой например ползвал ли е решение, ползващо това: http://planning.cs.uiuc.edu/node102.html, където в нашия случай ъглите на завъртане алфа, бета и гама са всички по 90 градуса и тия матрици се опростяват до единици, нули и минус единици.

1
02/04/2018 16:55:53