Compression monopole

17

Étant donné une chaîne représentant l'état actuel d'un jeu de Monopoly au début du tour d'un joueur, compressez toutes les données nécessaires dans la plus petite sortie. Les réponses seront jugées par la taille de la sortie et la taille de la source .

Remarque: Il existe de nombreuses variantes régionales, mais toutes les références dans ce post aux noms de propriété, etc., sont basées sur ce tableau .

Contribution:

L'entrée sera donnée comme une seule ;chaîne séparée. Cette chaîne est donnée au programme de la manière habituelle dans la langue choisie, que ce soit stdin, arguments, etc.

L'entrée non formatée ressemble à ceci:

numPlayers                     (1 to 8)
whose turn                     (0 to numPlayers-1)
for each player:
    bankrupt?                  (true/false)
    money                      (0 to 2^16-1)
    get-out-of-jail-free cards (0 to 2)
    position                   (0 to 39) 
    jail turns                 (-1 to 2)
for 28 properties:
    owner                      (-1 to numPlayers-1)
    mortgaged?                 (true/false)
    improvement level          (0 to 5)
for 16 chance cards in deck:
    card index                 (-1 to 15)
for 16 community chest cards in deck:
    card index                 (-1 to 15)

Voici un exemple d' entrée formatée :

3;1;false;1546;0;14;-1;false;7692;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

Pris petit à petit:

3;1;

Il y a 3 joueurs, et c'est au tour du joueur 1 (indexé zéro, donc le deuxième joueur)

Joueurs

false;1546;0;14;-1;
false;7692;1;10;1;
true;

Le premier joueur:

  • n'est pas en faillite
  • a 1546 $ en caisse
  • possède 0 carte sans sortie de prison
  • est en position 14 (Virginia Ave)
  • n'est pas en prison

Le deuxième joueur est en prison, depuis un tour. Je ne sais pas pourquoi , puisqu'il a une carte GOoJF, mais il est là.

Le troisième joueur est en faillite, et plus d'informations ne sont ni requises ni fournies.

Propriétés

1;false;1;
1;false;0;
0;true;0;
-1;false;0;
-1;false;0;
-1;false;0;
...

Les propriétés sont répertoriées dans l'ordre autour du plateau, à partir de la Méditerranée et se terminant à Boardwalk. Les propriétés qui ne peuvent pas être détenues ne sont pas incluses dans cette liste, il y en aura donc un total de 28. Le niveau d'amélioration 0signifie non amélioré. Le niveau 1est une maison, jusqu'au niveau 5d'un hôtel. Un -1pour propriétaire signifie qu'il n'appartient à aucun joueur.

Selon les règles standard, un bien hypothéqué doit être la propriété et ne doit pas être amélioré. Une propriété améliorée doit être la propriété et ne doit pas être hypothéquée.

De plus, pour qu'une propriété soit améliorée, un joueur doit posséder la totalité du bloc de couleur. Aux fins de ce jeu, nous ne nous soucions pas si les propriétés sont améliorées "uniformément".

Notez que ces positions ne sont pas les mêmes que celles des joueurs indiquées ci-dessus. Par exemple, un joueur sur le 5poste serait sur Reading Railroad, qui est la troisième propriété de la liste (car Go, Community Chest et Income Tax ne peuvent pas être détenus). Les positions des joueurs vont de 0(Aller) dans le sens horaire à 39(Boardwalk).

Cartes

0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;
3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

Chacun des decks Chance et Community Chest a un 16total de cartes. Les chiffres sont présentés tels qu'ils apparaissent dans le jeu actuellement mélangé. Pour cet exemple, la première carte retirée du paquet Chance sera la carte 0, suivie de la carte 1(celui qui a mélangé ce paquet suce). La première carte tirée de la poitrine communautaire est la carte 3, puis 12.

Ne vous inquiétez pas ce que chaque carte des moyens (le texte de la carte), à l' exception de la carte 0. C'est la carte Get Out of Jail Free pour ce deck. Si un joueur le possède, ce sera à la fin de la liste, représenté par -1.

Production:

Vous devez sortir (sur console, stdout ou fichier) une représentation de l'état du jeu. Cela doit inclure toutes les informations nécessaires pour représenter le jeu. Par exemple, vous pouvez omettre (ou abréger) des propriétés non possédées, car elles ne peuvent être ni améliorées ni hypothéquées. L'entrée ne peut pas les omettre car il s'agit d'une liste non indexée.

La compression doit être effectuée de manière à pouvoir calculer la taille de sortie dans le pire des cas. Cela peut disqualifier certains algorithmes de compression (sauf si vous pouvez prouver le pire des cas et donner un exemple d'entrée dans le pire des cas).

À moins que votre code source ne soit déraisonnablement bavard, expliquez comment le jeu est représenté. Les réponses consistant uniquement en un programme de golf et une sortie compressée sont déconseillées. Par exemple, si vous omettez certaines valeurs, expliquez comment il est possible de les dériver de la sortie.

Pointage / Règles:

La notation est basée à la fois sur la taille de compression la plus défavorable en bits et sur la taille du code source en octets :

score = (outputBits * 2) + encoderSourceBytes

Une réponse complète doit comprendre:

  • Exemple de sortie
  • Source de l'encodeur
  • Source du décodeur (non comptée dans le score)

Tous les encodeurs doivent être des programmes complets et les failles standard sont interdites. L'utilisation de bibliothèques de compression intégrées ou externes est également interdite.

Le gagnant est la réponse avec le score le plus bas , tel que défini ci-dessus.

code-challenge compression Géobits
la source
Hm, pourquoi ne pas exiger un décodeur ainsi qu'une preuve que l'encodage fonctionne réellement (et est réversible)? Et qu'en est-il de l'inclusion de choses comme la compression gzip intégrée? Cela rendrait très difficile la détermination de la taille de compression la plus défavorable.
Martin Ender
@ m.buettner Edited. J'ai ajouté un peu sur les bibliothèques de compression et un peu sur la preuve du pire des cas. Je ne veux pas vraiment appliquer un décodeur. Les affiches peuvent les inclure si elles souhaitent prouver leur solution, mais elle ne sera pas comptée dans le score.
Geobits
Oh ouais, je ne proposais pas de les ajouter au score. Vous pourriez toujours avoir besoin d'un décodeur (non golfé) comme preuve. Cela permet de tester plus facilement si les soumissions peuvent traiter des cas spéciaux.
Martin Ender
@ m.buettner Vous soulevez un excellent point. C'est des décodeurs.
Geobits
2
The second player is in jail, and has been for one turn. I'm not sure why, since he has a GOoJF card, but he's there.Être en prison est une bonne catégorie car vous ne payez pas de loyer. :)
undergroundmonorail

Réponses:

4

(Une réponse a été récemment éditée, ce qui a attiré mon attention sur cette question, et j'ai décidé de l'essayer bien que ce soit une vieille question.)

Swift 1,2 - 1016 points (2 * 81 + 854)

La sortie est au pire de 81 octets, et change avec le nombre de joueurs.

L'une ou l'autre des deux méthodes fonctionne. La version Playground est légèrement plus longue.

Compress Playground

(Suppose Input.txtest dans le Playground Documents Directory)

// Compressor e(inputFileName, outputFileName)
import Cocoa;typealias S=String;typealias U=UInt8;func e(a:S,b:S){var d=NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask, true)as![S],g=d[0],r=S(contentsOfFile:"\(g)/\(a)",encoding:4,error:nil)!.componentsSeparatedByString(";"),z=[U](count:4,repeatedValue:0),c=[U](),p:()->Int={r.removeAtIndex(0).toInt()!},f:()->Bool={r.removeAtIndex(0)=="true" ?true:false},j=U(p());c+=[(j<<4)|(U(p()))];for _ in 0..<j{if f(){c+=[255]}else{let(t,g,v)=(UInt16(p()),U(p()),U(p()));c+=[(U(p()))|(g<<2),v,U(t>>8),U(t&255)]}};for _ in 0..<28{c+=[(U(bitPattern:Int8(p()))<<4)|((f() ?1:0)<<3)|(U(p()))]};for h in 0..<16{let y=h>7 ?1:0,x=Int8(p()),w=Int8(p());c+=[(U(bitPattern:x)<<4)|(U(bitPattern:w)&15)];z[y]=z[y]<<1;if x == -1{z[y]|=1};z[y+1]=z[y+1]<<1;if w == -1{z[y+1]|=1}};NSData(bytes:c+z,length:c.count+4).writeToFile("\(g)/\(b)",atomically:true)}

// Decompressor d(inputFileName, outputFileName)
func d(a:S,b:S){var d = NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask,true)as![String],e=d[0],i=NSData(contentsOfFile:"\(e)/\(a)")!,n=[UInt8](count:i.length,repeatedValue:0),o="";i.getBytes(&n,length:i.length);let k=n.removeAtIndex(0),j=k>>4;o+="\(j);\(k&15);";for _ in 0..<j{let h=n.removeAtIndex(0);if h>>7 == 1{o+="true;";continue};let p=n.removeAtIndex(0),b=n.removeAtIndex(0),c=n.removeAtIndex(0);o+="false;\(UInt16(b)<<8|UInt16(c));\(h>>2);\(p);\(h&0b11);"};for _ in 0..<28{let p=Int8(bitPattern:n.removeAtIndex(0)),mortgage=((p>>3)&1)==1 ?"true":"false";o+="\(p>>4);\(mortgage);\(p&7);"};var m=[U](count:4,repeatedValue:0);for i in reverse(0..<4){m[i]=n.removeLast()};for h in 0..<16{var i=h>7 ?1:0,z=n.removeAtIndex(0),x=Int8(z>>4),y=Int8(z&15),isUnowned1=m[i]&128;m[i]=m[i]<<1;let isUnowned2=m[i+1]&128;m[i+1]=m[i+1]<<1;if isUnowned1 != 0 {x=(-1)};if isUnowned2 != 0 {y=(-1)};o+="\(x);\(y);"};o.writeToFile("\(e)/\(b)",atomically:true,encoding:4,error:nil)}

// Test function to compare the files
func t(a:S,b:S)->Bool{let d=NSSearchPathForDirectoriesInDomains(.DocumentDirectory,.UserDomainMask,true)as![String],c=d[0],i=S(contentsOfFile:"\(c)/\(a)",encoding:4,error:nil)!,j=S(contentsOfFile:"\(c)/\(b)",encoding:4,error:nil)!;return i==j}
// Usage
e("Input.txt", "Output.bin")  // Encode
d("Output.bin", "Output.txt") // Decode
t("Input.txt", "Output.txt")  // Test -> Should output 'true'

Compress.swift - exécuté dans Terminal en utilisantswift Compress.swift

(Suppose Input.txt est sur le Desktop)

// Compressor - 854 Bytes
import Cocoa;typealias S=String;typealias U=UInt8;func e(a:S,b:S){var d=NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask, true)as![S],g=d[0],r=S(contentsOfFile:"\(g)/\(a)",encoding:4,error:nil)!.componentsSeparatedByString(";"),z=[U](count:4,repeatedValue:0),c=[U](),p:()->Int={r.removeAtIndex(0).toInt()!},f:()->Bool={r.removeAtIndex(0)=="true" ?true:false},j=U(p());c+=[(j<<4)|(U(p()))];for _ in 0..<j{if f(){c+=[255]}else{let(t,g,v)=(UInt16(p()),U(p()),U(p()));c+=[(U(p()))|(g<<2),v,U(t>>8),U(t&255)]}};for _ in 0..<28{c+=[(U(bitPattern:Int8(p()))<<4)|((f() ?1:0)<<3)|(U(p()))]};for h in 0..<16{let y=h>7 ?1:0,x=Int8(p()),w=Int8(p());c+=[(U(bitPattern:x)<<4)|(U(bitPattern:w)&15)];z[y]=z[y]<<1;if x == -1{z[y]|=1};z[y+1]=z[y+1]<<1;if w == -1{z[y+1]|=1}};NSData(bytes:c+z,length:c.count+4).writeToFile("\(g)/\(b)",atomically:true)}
// Decompressor
func d(a:S,b:S){var d = NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask,true)as![String],e=d[0],i=NSData(contentsOfFile:"\(e)/\(a)")!,n=[UInt8](count:i.length,repeatedValue:0),o="";i.getBytes(&n,length:i.length);let k=n.removeAtIndex(0),j=k>>4;o+="\(j);\(k&15);";for _ in 0..<j{let h=n.removeAtIndex(0);if h>>7 == 1{o+="true;";continue};let p=n.removeAtIndex(0),b=n.removeAtIndex(0),c=n.removeAtIndex(0);o+="false;\(UInt16(b)<<8|UInt16(c));\(h>>2);\(p);\(h&0b11);"};for _ in 0..<28{let p=Int8(bitPattern:n.removeAtIndex(0)),mortgage=((p>>3)&1)==1 ?"true":"false";o+="\(p>>4);\(mortgage);\(p&7);"};var m=[U](count:4,repeatedValue:0);for i in reverse(0..<4){m[i]=n.removeLast()};for h in 0..<16{var i=h>7 ?1:0,z=n.removeAtIndex(0),x=Int8(z>>4),y=Int8(z&15),isUnowned1=m[i]&128;m[i]=m[i]<<1;let isUnowned2=m[i+1]&128;m[i+1]=m[i+1]<<1;if isUnowned1 != 0 {x=(-1)};if isUnowned2 != 0 {y=(-1)};o+="\(x);\(y);"};o.writeToFile("\(e)/\(b)",atomically:true,encoding:4,error:nil)}
func t(a:S,b:S)->Bool{let d=NSSearchPathForDirectoriesInDomains(.DesktopDirectory,.UserDomainMask,true)as![String],c=d[0],i=S(contentsOfFile:"\(c)/\(a)",encoding:4,error:nil)!,j=S(contentsOfFile:"\(c)/\(b)",encoding:4,error:nil)!;return i==j}
e("Input.txt", "Output.bin")
d("Output.bin", "Output.txt")
println(t("Input.txt", "Output.txt"))

Exemple d'entrée / sortie

3;1;false;1534;0;14;0;false;34;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;6;9;4;-1;4;8;4;2;9;5;11;10;14;7;

.

31 00 0E 05 FE 05 0A 00 22 FF 11 10 08 F0 F0 F0
F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 F0 
F0 F0 F0 F0 F0 F0 01 23 45 67 89 AB CD EF 3C 69 
4F 48 42 95 BA E7 00 00 20 00
David Skrundz
la source
4

Pure C (3592 points)

La sortie est de 182 octets. La taille est O (1), c'est donc le pire des cas.

Cela utilise sscanf de manière extensive pour lire les fichiers, et vide simplement les structures sur disque.

J'ai dû modifier légèrement l'entrée, car votre exemple ne comprenait pas 28 propriétés.

Pour les variables, je les ai nommées à partir de la première lettre de ce que c'est, ou si cela entrait en conflit, la deuxième lettre (ou la suivante). Par exemple, Game, pLayer, pRoperty, etc.

compress.c (680 octets):

#import <stdio.h>
#import <stdint.h>
#define T(X) for(int i=0;i<(X);i++)
typedef uint8_t U;typedef struct{U p;U t;U a[16];U e[16];}G;typedef struct{U b;uint16_t m;U c;U p;U t;}L;typedef struct{int8_t o;U m;U i;}R;G g;L l[8];R r[28];main(){FILE *f=fopen("input.txt","r");fscanf(f,"%d;%d;",&g.p,&g.t);T(g.p){l[i].b=(fgetc(f)=='t');while(fgetc(f)!=';');if(!l[i].b){fscanf(f,"%d;%d;%d;%d;",&l[i].m,&l[i].c,&l[i].p,&l[i].t);}}T(28){fscanf(f,"%d;",&r[i].o);r[i].m=(fgetc(f)=='t');while(fgetc(f)!=';');fscanf(f,"%d;",&r[i].i);}T(16){fscanf(f,"%d;",&g.a[i]);}T(16){fscanf(f,"%d;",&g.e[i]);}f=fopen("c.dat","w");fwrite(&g,sizeof(G),1,f);fwrite(&l,sizeof(L),8,f);fwrite(&r,sizeof(R),28,f);}

compress.c (pré-golf)

#include "m.h"

#define NEXT_FIELD b=strchr(b,';')+1;

G g;
L l[8];
R r[28];

char a[1024];
char *b = a;

main() {
    FILE *i = fopen("input.txt", "r");
    fgets(a, 1024, i);
    fclose(i);

    sscanf(b, "%d;%d;", &g.p, &g.t);
    NEXT_FIELD NEXT_FIELD

    TIMES(g.p) {
        l[i].b = (*b == 't'); NEXT_FIELD
        if(!l[i].b) {
            sscanf(b, "%d;%d;%d;%d;", &l[i].m, &l[i].c, &l[i].p, &l[i].t);
            NEXT_FIELD NEXT_FIELD NEXT_FIELD NEXT_FIELD
        }
    }

    TIMES(28) {
        sscanf(b, "%d;", &r[i].o); NEXT_FIELD
        r[i].m = (*b == 't'); NEXT_FIELD
        sscanf(b, "%d;", &r[i].i); NEXT_FIELD
    }

    TIMES(16) {
        sscanf(b, "%d", &g.a[i]);
        NEXT_FIELD
    }

    TIMES(16) {
        sscanf(b, "%d", &g.e[i]);
        NEXT_FIELD
    }

    FILE *c = fopen("c.dat", "w");
    fwrite(&g, sizeof(G), 1, c);
    fwrite(&l, sizeof(L), 8, c);
    fwrite(&r, sizeof(R), 28, c);
    fclose(c);
}

decompress.c :

#import <stdio.h>
#import <stdint.h>

#define T(X) for(int i = 0; i < (X); i++)
typedef uint8_t U;

typedef struct {
    U p;
    U t;
    U a[16];
    U e[16];
} G;
typedef struct {
    U b;
    uint16_t m;
    U c;
    U p;
    U t;
} L;
typedef struct {
    int8_t o;
    U m;
    U i;
} R;

G g;
L l[8];
R r[28];

main() {
    FILE *c = fopen("c.dat", "r");
    fread(&g, sizeof(G), 1, c);
    fread(&l, sizeof(L), 8, c);
    fread(&r, sizeof(R), 28, c);
    fclose(c);

    FILE *d = fopen("output.txt", "w");

    fprintf(d, "%d;%d;", g.p, g.t);
    T(g.p) {
        fprintf(d, "%s;", l[i].b ? "true" : "false");
        if(!l[i].b){
            fprintf(d, "%d;%d;%d;%d;", l[i].m, l[i].c, l[i].p, l[i].t);
        }
    }
    T(28) {
        fprintf(d, "%d;%s;%d;", r[i].o, r[i].m ? "true" : "false", r[i].i);
    }
    T(16) { fprintf(d, "%d;", g.a[i] != 255 ? g.a[i] : -1); }
    T(16) { fprintf(d, "%d;", g.e[i] != 255 ? g.e[i] : -1); }

    fclose(d);
}

Entrée / sortie :

3;1;false;1546;0;14;0;false;7692;1;10;1;true;1;false;1;1;false;0;0;true;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;-1;false;0;0;1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;3;12;7;4;5;2;13;11;15;6;8;9;10;1;14;-1;

Compressé (182 octets):

0301 0001 0203 0405 0607 0809 0a0b 0c0d
0e0f 030c 0704 0502 0d0b 0f06 0809 0a01
0eff 0000 0a06 000e 0000 0000 0c1e 010a
0100 0100 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0000 0000 0000 0000 0000 0000 0000
0000 0100 0101 0000 0001 00ff 0000 ff00
00ff 0000 ff00 00ff 0000 ff00 00ff 0000
ff00 00ff 0000 ff00 00ff 0000 ff00 00ff
0000 ff00 00ff 0000 ff00 00ff 0000 ff00
00ff 0000 ff00 00ff 0000 ff00 00ff 0000
ff00 00ff 0000

Exécuter!

$ make compress decompress && ./compress && ./decompress && md5 input.txt output.txt
MD5 (input.txt) = fa655a5a17d67b188424ab0dcfdfb825
MD5 (output.txt) = fa655a5a17d67b188424ab0dcfdfb825
wjl
la source
Merci, j'ai roulé l'en-tête pour économiser un peu et fixé mon score pour compter les octets.
wjl
On dirait que vous pourriez enregistrer quelques octets avec un encodage de longueur d'exécution après. Je ne sais pas dans quelle mesure c'est faisable, mais si vous le faites via un octet d'échappement, cela devrait également fonctionner avec des données non répétitives. Il h.
cjfaure