Forums Casio - Concours

Index du Forum | Concours | Compression Ultime !
Kirafi
Hors ligne
Membre
Niveau: Confirmé
Points: 1931
Défis: 10
Message
Posté le 02/02/2016 00:34

Compression Ultime ! :

Salut les Casionautes !

Aujourd'hui votre mission si vous l'acceptez est de réussir à compresser au maximum les matrice M et N (elle font 4*20 et comportent des valeurs entre 0 et 9)[/i].
Matrice M
0, 2, 2, 2, 5, 5, 6, 6, 9, 8, 7, 7, 7, 7, 7, 7, 0, 1, 2, 1
7, 7, 7, 8, 8, 9, 6, 5, 2, 1, 0 ,3, 3, 5, 4, 4, 7, 4, 5, 2
0, 5, 8, 8 ,8 ,8, 8, 8, 8, 8, 8, 8, 1, 0, 0, 2, 0, 0 ,4, 6
4, 5, 8, 9, 5 ,6, 5, 4, 2, 1, 4, 5, 3, 6, 5, 8, 1, 2, 6, 6
Matrice N

0, 1, 2, 3, 4, 5, 6 ,7, 8, 9, 0 ,1, 2 ,3 ,4, 5, 6, 7 ,8, 9
9, 8, 7, 6, 5, 4 ,3, 2, 1, 0, 9, 8, 7, 5, 4, 3, 2, 1, 0, 6
0, 0, 1, 1, 2, 2, 3, 3, 4 ,5, 6 ,8, 9, 5, 4 ,8, 5, 2, 3, 1
9, 1, 5, 4 ,8, 9, 5, 8, 4, 0, 4, 4, 0, 0, 0, 1, 5, 6, 9, 5


Une fois ceci fait, vous devez également créer le décompresseur dans un autre programme qui stockera les valeurs dans la matrice A, bien entendu, votre décompresseur devra gérer les 2 matrices .

:!: Le code compressé des matrices devra être mis dans un sous-programme qui sera appelé par votre décompresseur, pour que je puisse facilement évaluer la taille en octets du code compressé :!:
La taille en octets du décompresseur n'est pas limitée, il peut être énorme ce ne sera pas pris en compte !
La vitesse de décompression n'est pas prise en compte, votre programme peut mettre une heure à tout décompresser ce n'est pas grave, du moment que ça fonctionne.

Puis vous m'envoyez votre code, et de mon côté je vérifie les performances avec un programme qui se déroule comme suit :

Lancement du programme "Mat.M-N" qui initialisera la première fois la matrice M (commune à tous les participants).
Lancement de votre programme qui stockera les valeurs dans la matrice A.
Lancement du programme "Comparer" qui comparera les 2 matrices pour voir si elles sont identiques .
Puis je recommence en initialisant la matrice N .

Voilà, le concepteur du meilleur code compressé se verra décerner le titre de "Compressor" , sur ce, que le meilleur gagne !

iPod
Jusqu'où pourras-tu aller dans ce jeu "partie rapide" qu'est Dextris (élu Jeu Du Mois)
Pourras-tu survivre plus de 20 secondes dans ce fameux tunnel appelé Graviton
Rebondis entre les murs en évitant les piques dans SpikeBird
Pourras-tu éviter de te faire écraser dans FallBlocs (élu Jeu Du Mois)
Réussiras-tu à rendre uniforme la grille Spin (élu Jeu Du Mois)
Autres
Deviens l'amiral de la marine dans SeaRush (jeu concours) (élu Jeu Du Mois)
La version 2048 tactile amélioré au plus haut point : 2048 Delux !
Pars à la recherche des morceaux d'étoile dans Lumyce (élu Jeu Du Mois)
L'adaptation du célèbre jeu de reflexion 2048 Tactile (élu Jeu Du Mois)
Remet de l'ordre dans cette mare à grenouille de délinquants dans Hopper



Ne0tux
Hors ligne
Membre d'honneur
Niveau: Aucun
Points: 2813
Défis: 252
Message
Citer : Posté le 02/02/2016 14:34 | #
On peut faire rentrer les deux matrices en 40 caractères donc une solution finale de 64 octets (24+40*1 pour une Str) est envisageable.

Tu n'as pas précisé si le poids des algorithmes rentrait en compte ou si c'était juste le poids des matrices compressées qui importait.
----------------------------------
Deviens le roi de la banquise avec Ice Slider !
Sauras-tu sortir entier des locaux infernaux de CloneLab ?!?
Prêt à risquer ta peau face à Smaug le vilain dragon en cherchant l'Arkenstone ?
Projets de la communauté que je soutiens
Timeless II d'Alex_1186
Calc Center : un système de succès sur Casio
Le futur Jeu d'aventure de Remiweb
Le très attendu Pokemon de Dodormeur
La suite du premier volet : Robscape 2 de Ray
Zelda de Smash'
L'audacieux Projet Evolution de TheProg
Le fameux Yu-Gi-Oh d'Intelligide
Sans oublier cette folie qu'est MMGOC
On en trépignerait : Jetpack Joyride, de Drakalex
Kirafi
Hors ligne
Membre
Niveau: Confirmé
Points: 1931
Défis: 10
Message
Citer : Posté le 02/02/2016 18:13 | #
Ah oui pardon je modifie ce qoir dans le post principal ' , effectivement quand je demande à avoir 2 programmes séparé, un pour le code compressé et un pour le décompresseur, c'est pour avoir directement les octets du code

Oui après ces matries sont pas trop grandes , tu penses que je devrais augmenter la taille ?
----------------------------------
iPod
Jusqu'où pourras-tu aller dans ce jeu "partie rapide" qu'est Dextris (élu Jeu Du Mois)
Pourras-tu survivre plus de 20 secondes dans ce fameux tunnel appelé Graviton
Rebondis entre les murs en évitant les piques dans SpikeBird
Pourras-tu éviter de te faire écraser dans FallBlocs (élu Jeu Du Mois)
Réussiras-tu à rendre uniforme la grille Spin (élu Jeu Du Mois)
Autres
Deviens l'amiral de la marine dans SeaRush (jeu concours) (élu Jeu Du Mois)
La version 2048 tactile amélioré au plus haut point : 2048 Delux !
Pars à la recherche des morceaux d'étoile dans Lumyce (élu Jeu Du Mois)
L'adaptation du célèbre jeu de reflexion 2048 Tactile (élu Jeu Du Mois)
Remet de l'ordre dans cette mare à grenouille de délinquants dans Hopper
Dark storm
Hors ligne
Administrateur
Niveau: Aucun
Points: 9288
Défis: 169
Message
Citer : Posté le 02/02/2016 19:41 | #
Ok. J'ai fais quelques tests en TD de physique aujourd'hui. La matrice 21×7 sur laquelle je travaille est générée aléatoirement au début du programme selon la formule Int (10×(Ran# ^x → Mat A[L, C]. On a donc un prédominance de 0 suivant la valeur de x (dans mes tests, x ∈ {3, 5, 7}).

J'ai compressé les données comme suit :

1) Indexage dans une liste (List 1) de la matrice (ce qui permettra de lier des symboles récurrents sur deux lignes).
2) Groupement par séries de symboles dans deux listes (liste 2 : symbole, liste 3 : nombre d'occurences), avec une limite de 28 occurrences d'affilés.
3) Compression dans une string. Si le nombre d'occurrence du caractère est supérieur ou égal à 3, on met une lettre représentant le nombre d'occurrences (A = 3, …, Z = 28, d'où la limite de 28 caractères par groupe, mais c'est facilement amélioré) puis le caractère. Sinon y'a que le caractère.
4) Affichage du ratio de compression : 100 × (1 - StrLen(Str 1) ÷ Dim List 1)

En moyenne, pour x = 3 je tourne à 20-25% de compression, x = 5 je monte à 25-35%, x = 7 à 35-50%. Mais pour une map créée à la main, donc avec des lignes de tiles (un mur par exemple), j'ai compressé à 80% !

Je vais continuer mes tests
----------------------------------
Soutenez-les !





#YAPHPH
Kirafi
Hors ligne
Membre
Niveau: Confirmé
Points: 1931
Défis: 10
Message
Citer : Posté le 02/02/2016 20:05 | #
Ah tiens j'avais pas pensé à mettre les coefficients de récurrence dans une autre liste teh .
80% c'est assez énorme !
----------------------------------
iPod
Jusqu'où pourras-tu aller dans ce jeu "partie rapide" qu'est Dextris (élu Jeu Du Mois)
Pourras-tu survivre plus de 20 secondes dans ce fameux tunnel appelé Graviton
Rebondis entre les murs en évitant les piques dans SpikeBird
Pourras-tu éviter de te faire écraser dans FallBlocs (élu Jeu Du Mois)
Réussiras-tu à rendre uniforme la grille Spin (élu Jeu Du Mois)
Autres
Deviens l'amiral de la marine dans SeaRush (jeu concours) (élu Jeu Du Mois)
La version 2048 tactile amélioré au plus haut point : 2048 Delux !
Pars à la recherche des morceaux d'étoile dans Lumyce (élu Jeu Du Mois)
L'adaptation du célèbre jeu de reflexion 2048 Tactile (élu Jeu Du Mois)
Remet de l'ordre dans cette mare à grenouille de délinquants dans Hopper
Dark storm
Hors ligne
Administrateur
Niveau: Aucun
Points: 9288
Défis: 169
Message
Citer : Posté le 02/02/2016 22:43 | #
Disons que quand la map ressemble à ceci, ça compresse vraiment fort :

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1
1 1 1 0 0 0 2 2 0 1 1 1 2 0 0 0 0 0 1 0 1
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 2 3 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Soit 21×5 = 105 valeurs

Ça donne (sans les espaces oncalc) :
W1 C0 1 C0 B1 B0 B1 A0 2 2 0 A1 2 C0 1 0 A1 K0 1 1 2 3 V1


Soit 35 caractères, donc un ration de compression de 66%. Et encore, c'est une petite map avec pas tant de vide ou de longs murs que ça.
----------------------------------
Soutenez-les !





#YAPHPH


Index du Forum | Concours | Compression Ultime !
Publicité et partenaires
Casio Education
Casio éducation

TI-Planet
Casiopeia
Casiopeia
CasioFan, la communauté ClassPad
CasioFan
CodeWalrus
CodeWalrus

Planète Casio v42 © créé par Neuronix et Muelsaco 2004 - 2015 | Il y a 71 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements
Rugby Manager | Jeu de basket | Jeu de handball | Jeu de tennis | Nova Raider | Réparation téléphone | Soccer Rush | Tasty Tale

Planète Casio est un site communautaire indépendant, géré bénévolement et n'est donc pas affilié à Casio | Toute reproduction de Planète Casio, même partielle, est interdite
Les fichiers, programmes et autres publications présents sur Planète Casio restent la propriété de leurs auteurs respectifs et peuvent être soumis à des licences ou des copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd