Ragnulf issueshttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues2017-05-02T14:42:44Zhttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/28Ne plus utiliser test.py2017-05-02T14:42:44ZGuillaume CLOCHARDNe plus utiliser test.pyhttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/27Ajouter delay au début du tuto2017-05-02T14:42:44ZGuillaume CLOCHARDAjouter delay au début du tutoPar exemple 5sec pour avoir le temps de lire le message "placer le cube face bleu en face ) vous, etc."Par exemple 5sec pour avoir le temps de lire le message "placer le cube face bleu en face ) vous, etc."https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/26Faire des stats2017-05-02T14:42:44ZGuillaume CLOCHARDFaire des stats- longueur des solutions
- occupation mémoire
- temps de calcul
Des moyennes, des écart-type, des jolis graphes
@E134323D - longueur des solutions
- occupation mémoire
- temps de calcul
Des moyennes, des écart-type, des jolis graphes
@E134323D https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/24--colors ne marche plus2017-05-02T14:42:44ZGuillaume CLOCHARD--colors ne marche plusProbablement depuis utilisation de `getopt`.
![ss__2016-01-08_at_09.16.27_](https://gitlab.univ-nantes.fr/E132397K/Ragnulf/uploads/fb4bf7578b8fcebcdbbac931281580fe/ss__2016-01-08_at_09.16.27_.png)
Probablement depuis utilisation de `getopt`.
![ss__2016-01-08_at_09.16.27_](https://gitlab.univ-nantes.fr/E132397K/Ragnulf/uploads/fb4bf7578b8fcebcdbbac931281580fe/ss__2016-01-08_at_09.16.27_.png)
Arnaud LangelierArnaud Langelierhttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/23Intégration des tests unitaires2017-05-02T14:42:44ZGuillaume CLOCHARDIntégration des tests unitairesMettre à jour branche `tests` et merge sur master.Mettre à jour branche `tests` et merge sur master.https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/22Ajout détection double raccourcis2017-05-02T14:42:44ZGuillaume CLOCHARDAjout détection double raccourciscf. branche heuristic_buildercf. branche heuristic_builderhttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/21Ajout documentation2017-05-02T14:42:44ZGuillaume CLOCHARDAjout documentationCompléter le [README](README.md) et la [wiki](https://gitlab.univ-nantes.fr/E132397K/Ragnulf/wikis/home) :
- utilisation
- fonctionnement
- sources
- répartition tâches
-----
- [x] README
- [ ] Wiki (Jimmy @E136732X)Compléter le [README](README.md) et la [wiki](https://gitlab.univ-nantes.fr/E132397K/Ragnulf/wikis/home) :
- utilisation
- fonctionnement
- sources
- répartition tâches
-----
- [x] README
- [ ] Wiki (Jimmy @E136732X)https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/20Renommer Cube.face_resolu() en Cube.face_resolue()2017-05-02T14:42:44ZGuillaume CLOCHARDRenommer Cube.face_resolu() en Cube.face_resolue()![.](https://s-media-cache-ak0.pinimg.com/736x/fd/4f/42/fd4f42ef177a9fcde53cb1bfb2b024b8.jpg)![.](https://s-media-cache-ak0.pinimg.com/736x/fd/4f/42/fd4f42ef177a9fcde53cb1bfb2b024b8.jpg)https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/19Optimiser l'utilisation des listes temporaires2017-05-02T14:42:44ZGuillaume CLOCHARDOptimiser l'utilisation des listes temporairesÉviter ça : https://gitlab.univ-nantes.fr/E132397K/Ragnulf/blob/optimisation/algo.py#L842
cc @E134177U @E134323D @E134636T @E136732X Éviter ça : https://gitlab.univ-nantes.fr/E132397K/Ragnulf/blob/optimisation/algo.py#L842
cc @E134177U @E134323D @E134636T @E136732X https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/18algo_cfop() ne renvoie pas une suite correcte2017-05-02T14:42:44ZGuillaume CLOCHARDalgo_cfop() ne renvoie pas une suite correcte**Problème :**
J'ai voulu appliquer la suite de mouvements retournée par `algo_cfop()` sur un cube.
La fonction résout bien le cube (`print(cube)` est ok), mais quand on applique la suite
de mouvements, il semble qu'il y ai un probl...**Problème :**
J'ai voulu appliquer la suite de mouvements retournée par `algo_cfop()` sur un cube.
La fonction résout bien le cube (`print(cube)` est ok), mais quand on applique la suite
de mouvements, il semble qu'il y ai un problème à la fin.
**Reproduire :**
Lancer ce code
```python
from lire_entree import lecture_cube
from algo import algo_cfop
cube = 'OGRBWYBGBGYYOYOWOWGRYOOOBGBRRYRBWWWRBWYGROWGRYBRGYWBOG'
error, c = lecture_cube(cube)
mouvements = algo_cfop(c)
print(c) #va retourner un cube ok
error, c0 = lecture_cube(cube) #algo_cfop modifie c, on en crée un autre
for m in mouvements:
method = getattr(c0, 'rot_' + m)
method()
print(c0) #un cube non résolu
```
![capture](https://gitlab.univ-nantes.fr/E132397K/Ragnulf/uploads/d390ca7ba8f122d1aca43913ad5bbd33/capture.png)
Problème (haut) vs attendu (bas)
Voir la branche [`tuto`](https://gitlab.univ-nantes.fr/E132397K/Ragnulf/blob/tuto) pour un affichage pas à pas de la résolution du cube.https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/17poqb.py2017-05-02T14:42:44ZGuillaume CLOCHARDpoqb.pyImplémenter la lecture, résolution et affichage de la solution dans `poqb.py`.
---
Arnaud @E134067A Implémenter la lecture, résolution et affichage de la solution dans `poqb.py`.
---
Arnaud @E134067A https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/16Optimisation de l'algo2017-05-02T14:42:44ZGuillaume CLOCHARDOptimisation de l'algoOptimiser l'algo CFOP.
Pistes :
- implémenter les méthodes avancées de CFOP
- repérer les combinaisons inutiles (ex: R, Ri)
Voir :
- https://www.speedsolving.com/wiki/index.php/CFOP
---
@E134177U @E134323D @E136732X @E13...Optimiser l'algo CFOP.
Pistes :
- implémenter les méthodes avancées de CFOP
- repérer les combinaisons inutiles (ex: R, Ri)
Voir :
- https://www.speedsolving.com/wiki/index.php/CFOP
---
@E134177U @E134323D @E136732X @E134636Thttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/15Optimisation algo2017-05-02T14:42:44ZGuillaume CLOCHARDOptimisation algoOptimiser l'algo CFOP.
Pistes :
- implémenter les méthodes avancées de CFOP
- repérer les combinaisons inutiles (ex: R, Ri) --> idée du script qui tourne quelques heures/jours/semaines pour détecter les différents patterns pouvant...Optimiser l'algo CFOP.
Pistes :
- implémenter les méthodes avancées de CFOP
- repérer les combinaisons inutiles (ex: R, Ri) --> idée du script qui tourne quelques heures/jours/semaines pour détecter les différents patterns pouvant être optimisés
Voir :
- https://www.speedsolving.com/wiki/index.php/CFOP
---
@E134177U @E134323D @E136732X @E134636T @E132397K https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/14Sortie animée2017-05-02T14:42:44ZGuillaume CLOCHARDSortie animéeProposer une sortie avec une résolution du cube étape par étape animée.
Voir http://www.darkcoding.net/software/pretty-command-line-console-output-on-unix-in-python-and-go-lang/
- [x] Animation pas à pas de la résolution
- [x] Par...Proposer une sortie avec une résolution du cube étape par étape animée.
Voir http://www.darkcoding.net/software/pretty-command-line-console-output-on-unix-in-python-and-go-lang/
- [x] Animation pas à pas de la résolution
- [x] Paramètre vitesse `--speed=10`
- [ ] Paramètre `--bash` pour Git Bash Windows
- [x] Paramètre `--tuto` utilisé dans `poqb.py` pour appeler l'animation
---
Arnaud @E134067A
Guillaume @E132397Khttps://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/13Recherche sur lecture webcam2017-05-02T14:42:44ZGuillaume CLOCHARDRecherche sur lecture webcamArnaud @E134067A ?Arnaud @E134067A ?https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/12Recherche sur affichage 3D2017-05-02T14:42:44ZGuillaume CLOCHARDRecherche sur affichage 3DJimmy @E134177U Jimmy @E134177U https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/114ème étape de l'algo CFOP2017-05-02T14:42:44ZGuillaume CLOCHARD4ème étape de l'algo CFOPJimmy @E136732X ?Jimmy @E136732X ?https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/10Coder les rotations doubles2017-05-02T14:42:44ZGuillaume CLOCHARDCoder les rotations doublesDu type F2, R2, etc.
Arnaud @E134067A ?Du type F2, R2, etc.
Arnaud @E134067A ?https://gitlab.univ-nantes.fr/E132397K/Ragnulf/-/issues/9Tests unitaires2017-05-02T14:42:44ZGuillaume CLOCHARDTests unitairesPourquoi pas mettre en place des tests unitaires.
On est pas en retard et ça peut être intéressant de voir comment marche ces machins là. :sunglasses: Pourquoi pas mettre en place des tests unitaires.
On est pas en retard et ça peut être intéressant de voir comment marche ces machins là. :sunglasses: https://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/25Préparer présentation2022-07-06T10:17:58ZGuillaume CLOCHARDPréparer présentation# Consignes
Évoquer :
- encodage du Cube
- méthode(s) de résolution
- performance : longueur des solutions, occupation mémoire et temps de calcul
- fonctionnalités supplémentaires développées
- démonstration (optionnel)
#...# Consignes
Évoquer :
- encodage du Cube
- méthode(s) de résolution
- performance : longueur des solutions, occupation mémoire et temps de calcul
- fonctionnalités supplémentaires développées
- démonstration (optionnel)
# Plan
1. Structure du cube
2. Algorithme de résolution
1. CFOP
2. longueur des solutions, occupation mémoire, temps de calul
3. Fonctionnalités bonus
1. Affichage dans le terminal
2. Quelques tests unitaires
4. Gestion de projet
5. *Démo*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 DOREhttps://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/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/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/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/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 !