Kompresja monopolowa

Biorąc pod uwagę ciąg reprezentujący bieżący stan gry Monopoly na początku tury gracza, skompresuj wszystkie niezbędne dane do najmniejszej wydajności. Odpowiedzi zostaną ocenione na podstawie wielkości wyjściowej i rozmiaru źródła .

Uwaga: Istnieje wiele odmian regionalnych, ale wszystkie odniesienia w tym poście do nazw nieruchomości itp. Są oparte na tej tablicy .

Wejście:

Dane wejściowe będą podawane jako pojedynczy ;oddzielony ciąg. Łańcuch ten jest przekazywany programowi w dowolny sposób, który jest zwyczajowo wybrany w wybranym języku, niezależnie od tego, czy jest to standardowe, argumenty itp.

Niesformatowane dane wejściowe wyglądają następująco:

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)

Przykładem sformatowanego wejścia jest:

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;

Wykonano krok po kroku:

3;1;

Jest 3 graczy, a teraz jest tura 1 gracza (zero indeksów, więc drugi gracz)

Gracze

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

Pierwszy gracz:

nie jest bankrutem
ma pod ręką 1546 $ gotówki
posiada 0 kart wolnych od więzienia
zajmuje pozycję 14 (Virginia Ave)
nie jest w więzieniu

Drugi gracz jest w więzieniu i był na jedną turę. Nie jestem pewien dlaczego , skoro ma kartę GOoJF, ale on tam jest.

Trzeci gracz jest bankrutem, a więcej informacji nie jest ani wymaganych, ani podawanych.

Nieruchomości

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

Właściwości są wymienione w kolejności wokół planszy, zaczynając od Morza Śródziemnego, a kończąc na Boardwalk. Właściwości, które nie mogą być własnością, nie są uwzględnione na tej liście, więc będzie ich ogółem 28. Poziom ulepszenia 0oznacza nieulepszony. Poziom 1to jeden dom, do poziomu 5dla hotelu. A -1dla właściciela oznacza, że nie jest własnością żadnego gracza.

Zgodnie ze standardowymi zasadami nieruchomość obciążona hipoteką musi być własnością i nie może być ulepszana. Ulepszona nieruchomość musi być własnością i nie może być obciążona hipoteką.

Ponadto, aby poprawić właściwość, gracz musi posiadać cały blok kolorów. Na potrzeby tej gry nie obchodzi nas, czy właściwości są poprawiane „równomiernie”.

Zauważ, że te pozycje nie są takie same jak pozycje graczy podane powyżej. Na przykład gracz na 5pozycji byłby na Reading Railroad, która jest trzecią własnością na liście (ponieważ Go, Community Chest i podatek dochodowy nie mogą być własnością). Pozycje graczy biegną od 0(Go) zgodnie z ruchem wskazówek zegara do 39(Boardwalk).

Karty

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;

Każda z talii Chance i Community Chest ma 16całkowitą liczbę kart. Liczby są prezentowane w takiej postaci, w jakiej pojawiają się w aktualnie potasowanej talii. W tym przykładzie pierwszą kartą wyciągniętą z talii Szansy będzie karta 0, a następnie karta 1(ktokolwiek przetasował tę talię jest do bani). Pierwsza karta wyciągnął z wspólnotowym piersi jest karta 3, a następnie 12.

Nie martw się o to, co oznacza każda karta (tekst karty), z wyjątkiem karty 0. To jest karta Get Out of Jail Free dla tej talii. Jeśli gracz jest właścicielem, będzie on na końcu listy, reprezentowany jako -1.

Wynik:

Musisz wyprowadzić (do konsoli, standardu lub pliku) reprezentację stanu gry. Musi zawierać wszystkie informacje wymagane do reprezentowania gry. Na przykład możesz pominąć (lub skrócić) własności nieposiadane, ponieważ nie można ich ulepszyć ani obciążyć hipoteką. Dane wejściowe nie mogą ich pominąć, ponieważ jest to lista nieindeksowana.

Kompresję należy wykonać w sposób umożliwiający obliczenie wielkości wyjściowej najgorszego przypadku. Może to zdyskwalifikować niektóre algorytmy kompresji (chyba że możesz udowodnić najgorszy przypadek i podać przykład najgorszego przypadku).

O ile Twój kod źródłowy nie jest zbyt szczegółowy, podaj wyjaśnienie, w jaki sposób gra jest reprezentowana. Odpowiedzi składające się wyłącznie z programu golfowego i skompresowanego wyjścia są odradzane. Na przykład, jeśli pomijasz pewne wartości, wyjaśnij, w jaki sposób można je uzyskać z danych wyjściowych.

Punktacja / zasady:

Punktacja opiera się zarówno na rozmiarze kompresji najgorszego przypadku w bitach , jak i rozmiarze kodu źródłowego w bajtach :

score = (outputBits * 2) + encoderSourceBytes

Pełna odpowiedź musi zawierać:

Przykład wyjściowy
Źródło enkodera
Źródło dekodera (nie liczone do wyniku)

Wszystkie kodery muszą być kompletnymi programami, a standardowe luki są zabronione. Korzystanie z wbudowanych lub zewnętrznych bibliotek kompresji jest również zabronione.

Zwycięzcą jest odpowiedź o najniższym wyniku, jak zdefiniowano powyżej.

code-challenge compression Geobity
źródło

Hm, dlaczego nie wymagać dekodera, a także dowodu, że kodowanie faktycznie działa (i jest odwracalne)? A co z włączeniem takich rzeczy jak wbudowana kompresja gzip? To naprawdę utrudniłoby określenie najgorszego rozmiaru kompresji.

Martin Ender

@ m.buettner Edytowane. Dodałem trochę o bibliotekach kompresji i trochę o dowodzie najgorszego przypadku. Naprawdę nie chcę wymuszać dekodera. Plakaty mogą je uwzględnić, jeśli chcą udowodnić swoje rozwiązanie, ale nie zostanie to wliczone do wyniku.

Geobity

O tak, nie sugerowałem dodawania ich do partytury. Nadal możesz wymagać (nie golfowego) dekodera jako dowodu. Ułatwia to sprawdzenie, czy zgłoszenia mogą obsługiwać specjalne przypadki.

Martin Ender

@ m.buettner Robisz doskonały punkt. Dekodery to.

Geobity

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.Przebywanie w więzieniu jest dobrą grą strategiczną, ponieważ nie płacisz czynszu. :)

undergroundmonorail

Odpowiedzi:

(Niedawno zredagowano odpowiedź, która zwróciła moją uwagę na to pytanie, i postanowiłem spróbować, chociaż jest to stare pytanie).

Swift 1,2 - 1016 punktów (2 * 81 + 854)

Wyjście ma w najgorszym przypadku 81 bajtów i zmienia się wraz z liczbą graczy.

Każda z tych dwóch metod działa. Wersja Playground jest nieco dłuższa.

Kompresuj plac zabaw

(Zakłada się, że Input.txtjest w 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 - uruchom w Terminalu używającswift Compress.swift

(Zakłada się, że Input.txtjest 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"))

Przykładowe wejście / wyjście

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
źródło

Pure C (3592 punktów)

Dane wyjściowe to 182 bajty. Rozmiar to O (1), więc jest to najgorszy przypadek.

Używa sscanf do odczytu plików i po prostu zrzuca struktury na dysk.

Musiałem nieco zmodyfikować dane wejściowe, ponieważ twój przykład nie zawierał 28 właściwości.

W przypadku zmiennych nazwałem je od pierwszej litery tego, co to jest, a jeśli byłoby to sprzeczne, z drugą (lub kolejną) literą. Na przykład Game, pLayer, pRoperty itp.

compress.c (680 bajtów):

#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 (gra w golfa)

#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);
}

dekompresować. 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);
}

Wejście / wyjście :

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;

Skompresowany (182 bajty):

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

Uruchom!

$ make compress decompress && ./compress && ./decompress && md5 input.txt output.txt
MD5 (input.txt) = fa655a5a17d67b188424ab0dcfdfb825
MD5 (output.txt) = fa655a5a17d67b188424ab0dcfdfb825

wjl
źródło

Dzięki, zwinąłem nagłówek, żeby trochę zaoszczędzić, i poprawiłem swój wynik, by zliczał bajty.

wjl

Wygląda na to, że możesz zapisać kilka bajtów za pomocą kodowania długości przebiegu po. Nie jestem pewien, czy jest to wykonalne, ale jeśli robisz to za pomocą bajtu ucieczki, powinno również dobrze sobie radzić z danymi powtarzającymi się. Heh

cjfaure