Data structure research

[silexu]

Let's plan a discussion on Wednesday to define the final structure!

[cosminpolifronie]

Hello!

[silexu]

V-am arătat la un moment dat o aplicație luată de pe Google Play: CubeX

Îl contactasem pe autor și l-am întrebat despre data structure. Mi-a sugerat să mă uit pe https://github.com/muodov/kociemba

Ce este dezvoltat acolo este în primul rând o soluție destul de complexă pentru algoritmul optim dar și o soluție destul de bună cred pentru reprezentarea cubului, precum și o implementare a operațiilor.

Dacă aveți timp aruncați o privire.

[cosminpolifronie]

Din cate am inteles, algoritmul asta reprezinta intregul cub folosind 5 int-uri. M-am tot uitat pe cod si nu pot sa zic ca inteleg cum a reprezentat lucrurile sau cum face operatiile. Nefiind familiar cu lucruri din astea legate de Rubik, sau de teoria grupurilor, sunt total pierdut momentan.

https://stackoverflow.com/a/527260 https://en.wikipedia.org/wiki/Optimal_solutions_for_Rubik's_Cube#Thistlethwaite.27s_algorithm (algoritmul Kociemba e o imbunatatire a Thistlethwaite)

[silexu]

Bune referințe!

Am găsit și eu discuția respectivă pe stackoverflow. Din păcate nu m-a lămurit cum putem continua, alegând propunerile din discuție, cu ceea ce vrem să facem, în mod special rezolvarea optimă. Iar al doilea articol are teoria despre rezolvare, foarte interesantă de altfel, dar nu zice nimic de reprezentarea cubului.

În schimb repozitory-ul de care v-am povestit ne oferă destul de multe informații.

Astfel sunt 3 tipuri de reprezentări: facecube_t - 6 array-uri de câte 9 valori care descriu fiecare față cu elementele ei; cubiecube_t - 2 array-uri cu câte 8 valori pentru poziționarea și orientarea colțurilor și 2 array-uri cu câte 12 valori pentru poziționarea și orientarea marginilor coordcube_t - nu m-a lămurit foarte mult dar cred că e folosit în calcularea distanței variantei curente fața de final.

Primele 2 au funcții de conversie de la unul la altul iar cubiecube pare să aibă și funcții de rotire, dar nu sunt foarte sigur cum se folosesc efectiv. Primul cred că poate fi folosit cu succes la desenare față cu față, al doilea dacă fiecare cub se desenează independent și o dată cu totul. Am discutat cu autorul și avem acceptul să folosim sursele atâta timp cât e un proiect educațional. Am reușit să pun fișierele într-o structură de proiect VS, pot să vă trimit o arhivă pe mail. Dacă e cineva priceput la QT ar putea face ceva similar.

Din păcate resolvarea unui cub, chiar și simplu, crapă; mai trebuie investigat, dar cred că se poate porni cu vizualizarea.

Dacă vă plictisiți puteți citi și niște teorie: http://web.mit.edu/sp.268/www/rubik.pdf

[silexu]

http://www.algosome.com/articles/rubiks-cube-computer-simulation.html

[vladvrabie]

Pe site-ul celor care au demontrat ca God's number e 20 am citit ceva documentatie legata de reprezentarea cubului: http://cube20.org/src/ Primul, cubepos, e o clasa mai generala de reprezentare a cubului, este orientata catre performanta. Subcapitolele 19-27 explica ce conventii au pentru notatii si miscari. Al doile, kocsymm, e o specializare a reprezentarii cubului pentru Kociemba.

[silexu]

Vlad, sunt deschis la orice structură de date, atâta timp cât puteți face translatarea între cea de vizualizare și cea de rezolvare. De asemenea dacă se pot identifica ușor piesele unde se află pentru pattern solving.

[cosminpolifronie]

Ramanem la structura cu 6 matrice, pentru moment.

[cosminpolifronie]

Teapa, ca nu e asa simplu :dagger: