Ragnulf issueshttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues2017-05-02T14:42:44Zhttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/8Implémentation de l'algo CFOP2017-05-02T14:42:44ZGuillaume CLOCHARDImplémentation de l'algo CFOP### État de l'art.
Deux types d'algorithmes :
1. les algos réalisables à la main (débutant, CFOP, etc.)
2. les algos plus mathématiques (Thistlethwaite, Kociemba, ..., utilisant des propriétés sur les ensembles des cubes)
On choi...### État de l'art.
Deux types d'algorithmes :
1. les algos réalisables à la main (débutant, CFOP, etc.)
2. les algos plus mathématiques (Thistlethwaite, Kociemba, ..., utilisant des propriétés sur les ensembles des cubes)
On choisi de partir en premier lieu sur l'implémentation de CFOP.
Il semble que ce soit un algo du type 1 qui soit un des plus rapides et donnant les solutions les plus courtes d'après [ce papier](http://www.diva-portal.org/smash/get/diva2:812006/FULLTEXT01.pdf).
On trouve que c'est un bon compromis entre réalisabilité et complexité mathématique.
### CFOP = 4 étapes
1. résoudre la croix (**C**ross)
2. résoudre les deux premiers étages (**F**2L)
3. Orienter dernier étage (**O**LL)
4. Permutations sur le dernier étage (**P**LL)
Plus d'infos :
- [Wikipedia](https://en.wikipedia.org/wiki/CFOP_Method)
- [Youtube](https://www.youtube.com/watch?v=VwvGWNfcgs8)
----
Tâches :
- Cross (Jimmy @E134177U)
- F2L
- OLL
- PLLhttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/7Pistes pour optimisation de la modélisation2016-01-03T20:54:20ZGuillaume CLOCHARDPistes pour optimisation de la modélisationTâches
-----
- [ ] Abandon du dictionnaire
- [ ] Comparaison tableau `numpy` vs codage entiersTâches
-----
- [ ] Abandon du dictionnaire
- [ ] Comparaison tableau `numpy` vs codage entiershttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/6Validation du cube2016-01-08T16:13:13ZGuillaume CLOCHARDValidation du cubeOn doit être sûr que le cube donné en entré est solvable. :point_up:
Ce qui implique plusieurs choses :
1. s'assurer que la chaîne est correcte (54 facettes, 1 face par couleur, 9 facettes de chaque couleur, etc). Vérifié par #5 ....On doit être sûr que le cube donné en entré est solvable. :point_up:
Ce qui implique plusieurs choses :
1. s'assurer que la chaîne est correcte (54 facettes, 1 face par couleur, 9 facettes de chaque couleur, etc). Vérifié par #5 .
2. s'assurer que les petits cubes sont corrects ([*corner and edge parity*](http://math.stackexchange.com/a/127627)). Vérifié par #5.
3. s'assurer que le cube est solvable. Ce qui reste à faire ici.
Les étapes 1. et 2. validées, il semble qu'on puisse lancer un algorithme sur le cube sans problème. Arrivé à la dernière étapes des algorithmes (à confirmer : tous les algorithmes ?) on peut détecter certains patterns qui sont synonymes d'un cube non solvables.
:link: Voir :
- [How do I tell if the cube is unsolvable from a given state?](http://jeays.net/rubiks.htm#unsolvable)
- [Unsolvable Rubik’s Cube](http://ruwix.com/the-rubiks-cube/unsolvable-rubiks-cube-invalid-scramble/)
- [How do I check if my cube is unsolvable? How can I fix it if it is?](http://solvethecube.com/faq)
Un cube non solvable est généralement créé en désassemblant ou rassemblant les pièces du cube. On a qu'une chance sur 12 d'assembler un cube dans un état solvable.
---
### Tâches
- [x] S'assurer de la validité des petits cube. cf. #5
- [x] S'assurer de la validité de l'état du cube (à l'implémentation de l'algo)https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/5Lecture de la chaîne d'entrée2015-12-03T14:44:52ZGuillaume CLOCHARDLecture de la chaîne d'entrée### Tâches
- [x] Instantiation d'un `Cube` à partir de la chaîne en entrée. (Jimmy @E134177U)
- [x] Validation de la chaîne d'entrée (mais pas de l'état du cube) (Guillaume @E132397K)### Tâches
- [x] Instantiation d'un `Cube` à partir de la chaîne en entrée. (Jimmy @E134177U)
- [x] Validation de la chaîne d'entrée (mais pas de l'état du cube) (Guillaume @E132397K)https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/4Modélisation du cube2015-12-01T20:00:29ZGuillaume CLOCHARDModélisation du cube### Objectif
- modéliser l'état du cube
- être économe en mémoire
- permettre une économie d'opérations lors des rotations
- implémenter les rotations sur le cube
### Les choix
**Modélisation des petits cube.**
Idée...### Objectif
- modéliser l'état du cube
- être économe en mémoire
- permettre une économie d'opérations lors des rotations
- implémenter les rotations sur le cube
### Les choix
**Modélisation des petits cube.**
Idée : `data['FRU'] = ['R', 'B', 'G']` pour signaler que le cube front-right-up est rouge-bleu-vert
Ainsi, lors d'une rotation, on économise quelques opérations par rapport au stockage des 48 face de couleurs.
Par exemple : lors de la rotation d'une face, il y a rotation d'un coin.
Pour ce coin, dans la méthode des 48 faces, il faut effectuer modifications (pour les 3 faces du coin), là où la méthode des petits cubes permet une unique affectation.
De même pour une arrête : 2 modifications pour la méthodes des faces contre une modification unique pour la méthodes des petits cubes.
Mais un coin peut effectuer une rotation sur lui même (par exemple pour FRU, faire les rotations R puis U).
On doit donc également stocker l'état de rotation du cube par rapport à son état initial.
Pour une arrête : 2 états. Pour un coin : 3 états.
Ainsi :
```
cubes[<coin>] = [<couleur>, <couleur>, <couleur>, <état>] #un coin
cubes[<arête>] = [<couleur>, <couleur>, <état>] #une arête
```
Exemple : actions R puis U sur le cube FRU
```
start : FRU = [W, B, O, 0] #état de rotation initial = 0
R : RBU = FRU;
RBU[3] += 1 #le cube a tourné
On voudrait avoir RBU = [B, O, W]
mais ça nous oblige à faire 3 opérations.
U : FRU = RBU #ici, le cube n'a pas tourné
```
Donc, `get_facette('FRU', 0)` (on demande la facette F) ne doit pas renvoyer `W`, mais `B`. Et cela est rendu possible par l'information d'état de rotation.
Calcul du nombre d'opérations pour une rotation d'une face :
- option des 54 facettes
19 facettes à bouger, donc 19 opérations d'affectation
- options des cubes
- 4 coins à bouger (4 affectations, 4 incrémentation/décrémentation dans le pire des cas)
- 4 arêtes à bouger (idem)
= 16 opérations (seulement 3 de moins que l'option des 54 facettes, mais la situation où touts les cubes de la face tournent sur eux même n'arrive que 1/3 des fois)
**Avantages de l'option des cubes :**
- un peu moins d'opérations
- un concept plus proche de la réalité pour les développeurs
- modélise la relation d'appartenance des facettes à un petit cube
- plus facile de vérifier la validité du rubik's cube donné (pas de couleurs opposées dans un petit cube)
**Inconvénients :**
- impact en mémoire plus lourd ?
(dictionnaire ou tableau de tableau)
- opérations plus coûteuses sur un dictionnaire ou sur un tableau de tableau ?
**Modélisation des couleurs**
On code le stockage des couleurs. Pas de chaînes de caractères mais un entier. Gain de place en mémoire.
```
White (W) = 0
Blue (B) = 1
Red (R) = 2
Green (G) = 3
Orange (0) = 4
Yellow (Y) = 5
```
### Implémentation
**Dans un premier temps :**
- on choisi d'utiliser un dictionnaire pour stocker chaque petit cube
- chaque petit cube pointe sur un tableau `numpy` (plus léger qu'une liste Python)
Utiliser un tableau `numpy` pour stocker les couleurs d'un petit cube.
Exemple : `[0, 5]` pour blanc-jaune (arête impossible).
*Implémentation rapide pour lancer le projet (lecture, résolution).*
```python
cube.data = {
'FRU' : [0, 2]
...
}
```
**Dans un second temps, envisager :**
- abandon du dictionnaire
Coder chaque cube comme un entier dans [0, 20] et utiliser un tableau `numpy`.
exemple : `[<listes des couleurs de FRU>, <liste des couleurs de FU>, ...]`
- abandon du tableau `numpy` pour le stockage des couleurs d'un coin et utiliser des entiers (gain de place).
exemple : `523` code un coin
```python
coin = 523
a = coin // 100 // 5
b = coin // 10 % 10 // 2
c = coin % 10 // 3
```
À voir si c'est plus rapide lors de l'accès aux couleurs.
-----
### Tâches :
- [x] Modélisation du cube (Guillaume @E132397K)
- [x] Affichage du cube pour debug (format 54 facettes) (Guillaume @E132397K)
- [x] Implémentation des rotations (Jimmy @E136732X)
- [x] Comparer avec une modélisation 48 facettes (Arnaud @E134067A)
- [x] Rotations du cube sur lui même (Tom @E134636T)
https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/3Réunion #12015-11-18T18:21:21ZGuillaume CLOCHARDRéunion #1
### Ordre du jour :
- état des recherches, évocation des quelques algorithmes repérés
- découpage du projet en sous-parties
- réflexion sur la modélisation du cube
- point sur `git`
- répartition des premières tâches
### Com...
### Ordre du jour :
- état des recherches, évocation des quelques algorithmes repérés
- découpage du projet en sous-parties
- réflexion sur la modélisation du cube
- point sur `git`
- répartition des premières tâches
### Comment on voit le projet :
1. **Une modélisation du cube**
- être économe en place mémoire
- implémenter les opérations de rotation
- faire un choix économisant les opération de 3.
2. **Une lecture de l'entrée**
- créer une instance du cube en détectant d'éventuelles erreurs d'entrée
3. **Une résolution du cube par l'implémentation d'un algorithme**
- choisir un algorithme
----
*18/11/12*
**Participants** :
- Arnaud @E134067A
- Jimmy @E134177U
- Jimmy @E136732X
- Quentin @E134323D
- Tom @E134636T
- Guillaume @E132397K https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/2Misc.2015-11-18T18:22:22ZGuillaume RASCHIAMisc.Vous pouvez également "détourner" les Issues pour ouvrir des discussions collectives, comme ici. bonne continuation ! Vous pouvez également "détourner" les Issues pour ouvrir des discussions collectives, comme ici. bonne continuation ! https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/1Comprendre le système d'issue2015-11-18T18:22:23ZGuillaume CLOCHARDComprendre le système d'issueLe répartition et le partage des tâches doit se faire par le système d'issue interne à Gitlab :point_up:
L'idée est de décrire ici la tâche à effectuer.
Exemple : Écrire le module de lecture d'entré.
- [x] Lire la chaîne
- [x] Vérifi...Le répartition et le partage des tâches doit se faire par le système d'issue interne à Gitlab :point_up:
L'idée est de décrire ici la tâche à effectuer.
Exemple : Écrire le module de lecture d'entré.
- [x] Lire la chaîne
- [x] Vérifier que la chaîne est valide
- [x] Sub-task 1
- [x] Sub-task 2
- [ ] Retourner une nouvelle instance du rubik's cube
Voilà voilà.
(On peut utiliser du [Markdown](https://gitlab.univ-nantes.fr/help/markdown/markdown) et c'est cool :thumbsup:)Jimmy DOREJimmy DORE