Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Concours


Index du Forum » Concours » Compression Ultime !
Kirafi Hors ligne Membre Points: 2180 Défis: 10 Message

Compression Ultime !

Posté le 02/02/2016 00:34

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
Cliquer pour enrouler
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
Cliquer pour enrouler

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 !


Ne0tux Hors ligne Membre d'honneur Points: 3524 Défis: 265 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.
Mes principaux jeux : Ice Slider - CloneLab - Arkenstone

La Planète Casio est accueillante : n'hésite pas à t'inscrire pour laisser un message ou partager tes créations !
Kirafi Hors ligne Membre Points: 2180 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
Pour des parties rapides
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)
Autres
Franchement ils valent le coups
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)
Dark storm En ligne Labélisateur Points: 11631 Défis: 176 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

Finir est souvent bien plus difficile que commencer. — Jack Beauregard
Kirafi Hors ligne Membre Points: 2180 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
Pour des parties rapides
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)
Autres
Franchement ils valent le coups
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)
Dark storm En ligne Labélisateur Points: 11631 Défis: 176 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.
Finir est souvent bien plus difficile que commencer. — Jack Beauregard

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 96 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd