wmutex

Ok, in prima faza identificam grupurile de litere care sunt deja ordonate (fiindca le vom muta pe toate o data):

F,{W, X, Y, Z}, {K, L}, A, T, U, J, {N, O}, S,{D, E}, P, V, C, B, {G, H, I}, {Q, R}, M

Dat fiind ca fiecare grup poate fi adus in pozitia corecta dintr-o singura mutare (mut pe cu A la inceput, apoi B dupa A, apoi C dupa B, apoi {D,E} dupa C etc.) rezulta ca o limita superioara a numarului minim de mutari e 16, fiindca sunt 17 grupuri in total.

Cat despre numarul minim... mai treb'e vazut. :-)

wmutex

Ok, pornind de la grupurile deja ordonate (intre acolade) o sa descriu seria de "mutari" punand cu litere ingrosate grupul care trebuie pozitionat (si urmeaza a fi mutat), si cu "^" locul de inserare. Ideea e de a vea "in fata" in permananta literele ordonate:

0: ^F, {W, X, Y, Z}, {K, L}, A, {T, U}, J, {N, O}, S, {D, E}, P, V, C, B, {G, H, I}, {Q, R}, M (initial)

1: A, ^F, {W, X, Y, Z}, {K, L}, {T, U}, J, {N, O}, S, {D, E}, P, V, C, B, {G, H, I}, {Q, R}, M

2: {A, B}, ^F, {W, X, Y, Z}, {K, L}, {T, U}, J, {N, O}, S, {D, E}, P, V, C, {G, H, I}, {Q, R}, M

3: {A, B, C}, ^F, {W, X, Y, Z}, {K, L}, {T, U}, J, {N, O}, S, {D, E}, P, V, {G, H, I}, {Q, R}, M

4: {A, B, C, D, E, F}, ^{W, X, Y, Z}, {K, L}, {T, U}, J, {N, O}, S, P, V, {G, H, I}, {Q, R}, M

5: {A, B, C, D, E, F, G, H, I}, ^{W, X, Y, Z}, {K, L}, {T, U}, J, {N, O}, S, P, V, {Q, R}, M

6: {A, B, C, D, E, F, G, H, I, J}, ^{W, X, Y, Z}, {K, L}, {T, U}, {N, O}, S, P, V, {Q, R}, M

7: {A, B, C, D, E, F, G, H, I, J, K, L}, ^{W, X, Y, Z}, {T, U}, {N, O}, S, P, V, {Q, R}, M

8: {A, B, C, D, E, F, G, H, I, J, K, L, M}, ^{W, X, Y, Z}, {T, U}, {N, O}, S, P, V, {Q, R}

9: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O}, ^{W, X, Y, Z}, {T, U}, S, P, V, {Q, R}

10: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P}, ^{W, X, Y, Z}, {T, U}, S, V, {Q, R}

11: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R}, ^{W, X, Y, Z}, {T, U}, S, V

12: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S}, ^{W, X, Y, Z}, {T, U, V}

13: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z}

Am obtinut sirul ordonat din 13 mutari. Chestia e ca nu-mi dau seama daca asta e cea mau buna strategie. Daca ar fi, ar trebui sa pot demonstra matematic ca-i asa, dar nu-mi trece nici o idee prin cap. Cred ca problema e inca deschisa.

catanedelcu

informatie suplimentara :  numarul de "mutari" este  mai mic decat 10.  

Chestia asta miroase a cubul lui Rubik  :D .Autorul , as pune pariu, a inceput de la alfabet si l-a ”măscărit” . Algoritmic se rezolva cum zice wmutex , evident, dar , ca si la cub, nr. teoretic de mutari , in functie de configuratia fețelor, e mai mic.

madd

Eu am reusit din 10 mutari; sirul scris cursiv este cel care va fi mutat urmatorul si cel ingrosat este cel mutat la momentul respectiv.
Initiai avem: F W X Y Z K L A T U J N O S D E P V C B G H I Q R M
-----------------
1. F K L A T U J N O S D E P V C B G H I Q R M W X Y Z
2. A T U J F K L N O S D E P V C B G H I Q R M W X Y Z
3. A T U J F K L N O S D E P Q R M V C B G H I  W X Y Z
4. A T U J F K L N O P Q R S D E M V C B G H I W X Y Z
5. A J F K L N O P Q R S D E M T U V C B G H I W X Y Z
6. A J F K L D E M N O P Q R S T U V C B G H I W X Y Z
7. A C B G H I J F K L D E M N O P Q R S T U V W X Y Z
8. A C B D E G H I J F K L M N O P Q R S T U V W X Y Z
9. A C B D E F G H I J K L M N O P Q R S T U V W X Y Z
10. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

babbidi

1. (WXYZ) dupa M
F, K, L, A, T, U, J, N, O, S, D, E, P, V, C, B, G, H, I, Q, R, M, W, X, Y, Z,
2. (T, U, J, N, O, S, D, E, P, V) intre M si W
F, K, L, A, C, B, G, H, I, Q, R, M, T, U, J, N, O, S, D, E, P, V, W, X, Y, Z,
3. (Q, R, M, T, U) intre P si V
F, K, L, A, C, B, G, H, I, J, N, O, S, D, E, P, Q, R, M, T, U, V, W, X, Y, Z,
4. (N, O, S,) intre M si T
F, K, L, A, C, B, G, H, I, J, D, E, P, Q, R, M, N, O, S, T, U, V, W, X, Y, Z,
5. (P, Q, R, ) intre O si S
F, K, L, A, C, B, G, H, I, J, D, E, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
6. (G, H, I, J) intre F si K
F, G, H, I, J, K, L, A, C, B,  D, E, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
7. (C) intre B si D
F, G, H, I, J, K, L, A, B, C, D, E, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,
8. (F, G, H, I, J, K, L,) intre E si M
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z,

wmutex

Hmm... m-am mai gandit... pare o problema mai degraba "greedy" decat "quicksort". O sa incerc sa gasesc, la fiecare pas, mutarea care duce la ordonarea a cat mai multe litere.

Tantôt. :-)

wmutex

Ok, sa vedem. Folosesc aceleasi notatii: literele ingrosate urmeaza sa fie mutate, "^" denota locul in care urmeaza sa fie mutate. La final e (numarul de grupuri litere ordonate), pe care-l vreau sa scada cat mai mult la fiecare pas:


0: F, {W, X, Y, Z}, {K, L}, A, {T, U}, ^J, {N, O}, S, {D, E}, P, V, C, B, {G, H, I}, {Q, R}, M    (16)

1: F, {W, X, Y, Z}, {K, L}, A, {T, U, V}, C, B, {G, H, I, J}, {N, O}, S, ^{D, E}, {P, Q, R}, M   (13)

2: F, ^{W, X, Y, Z}, {K, L}, {A, B}, {G, H, I, J}, {N, O}, {S, T, U, V}, {C, D, E}, {P, Q, R}, M    (10)

3: {F, G, H, I, J}, {N, O}, {S, T, U, V, W, X, Y, Z}, {K, L}, {A, B, C, D, E}, {P, Q, R}, ^M   (7)

4: {F, G, H, I, J}, {N, O}, {A, B, C, D, E}, ^{P, Q, R, S, T, U, V, W, X, Y, Z}, {K, L, M}   (5)

5: {A, B, C, D, E, F, G, H, I, J}, ^{N, O, P, Q, R, S, T, U, V, W, X, Y, Z}, {K, L, M}   (3)

6: {A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z}   (1)


Acuma, nu stiu cum sa demonstrez ca "lacomia" duce intr-devar la cea mai buna solutie. Daca ma chinui sa-mi aduc aminte algoritmica din facultate... programarea dinamica ar trebui sa dea ce-a mai buna solutie. Dar fara computer, doar pe hartie, mi-e groaza sa m-apuc, si n-am chef de cod acum. Daca se ofera cineva... :-)

knowing

nu primim si o problema bonus :?