Kompresi Monopoli

17

Diberikan string yang mewakili keadaan saat ini dari permainan Monopoli pada awal giliran pemain, kompres semua data yang diperlukan ke dalam output terkecil. Jawaban akan dinilai berdasarkan ukuran output dan ukuran sumber .

Catatan: Ada banyak variasi regional, tetapi semua referensi dalam posting ini untuk nama properti, dll, didasarkan pada forum ini .

Memasukkan:

Input akan diberikan sebagai ;string terpisah. String ini diberikan kepada program dengan cara apa pun yang biasa dalam bahasa yang Anda pilih, apakah itu stdin, argumen, dll.

Input yang belum diformat terlihat seperti ini:

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)

Contoh input yang diformat adalah ini:

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;

Diambil sedikit demi sedikit:

3;1;

Ada 3 pemain, dan giliran pemain 1 (diindeks nol, jadi pemain kedua )

Pemain

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

Pemain pertama:

  • tidak bangkrut
  • memiliki uang tunai $ 1546
  • memiliki 0 kartu bebas-keluar-penjara
  • ada di posisi 14 (Virginia Ave)
  • tidak ada di penjara

Pemain kedua ada di penjara, dan sudah satu giliran. Saya tidak yakin mengapa , karena dia memiliki kartu GOoJF, tetapi dia ada di sana.

Pemain ketiga bangkrut, dan informasi lebih lanjut tidak diperlukan atau diberikan.

Properti

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

Properti terdaftar secara berurutan di sekitar papan, mulai dari Mediterania dan berakhir di Boardwalk. Properti yang tidak dapat dimiliki tidak termasuk dalam daftar ini, sehingga akan ada total 28. Tingkat peningkatan 0berarti tidak ditingkatkan. Level 1adalah satu rumah, hingga level 5untuk sebuah hotel. A -1untuk pemilik berarti itu tidak dimiliki oleh pemain mana pun.

Menurut aturan standar, properti yang digadaikan harus dimiliki dan tidak boleh diperbaiki. Properti yang diperbaiki harus dimiliki dan tidak boleh digadaikan.

Selain itu, agar properti ditingkatkan, pemain harus memiliki seluruh blok warna. Untuk keperluan game ini, kami tidak peduli jika properti ditingkatkan "merata".

Perhatikan bahwa posisi ini tidak sama dengan posisi pemain yang diberikan di atas. Sebagai contoh, seorang pemain pada 5posisi akan berada di Reading Railroad, yang merupakan properti ketiga dalam daftar (karena Go, Community Chest, dan Pajak Penghasilan tidak dapat dimiliki). Posisi pemain berjalan dari 0(Go) searah jarum jam ke 39(Boardwalk).

Kartu-kartu

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;

Setiap dek Peluang dan Peti Komunitas memiliki 16kartu total. Angka-angka disajikan ketika mereka muncul di dek yang sedang dikocok. Untuk contoh ini, kartu pertama yang ditarik dari dek Peluang akan berupa kartu 0, diikuti oleh kartu 1(siapa pun yang mengocok dek itu menyebalkan). Kartu pertama yang ditarik dari dada Komunitas adalah kartu 3, lalu 12.

Jangan khawatir tentang apa yang masing-masing kartu berarti (teks kartu), kecuali untuk kartu 0. Itulah kartu Keluar dari Penjara untuk dek itu. Jika seorang pemain memilikinya, itu akan berada di akhir daftar, diwakili sebagai -1.

Keluaran:

Anda harus menampilkan (untuk menghibur, stdout, atau file) representasi dari kondisi permainan. Ini harus mencakup semua informasi yang diperlukan untuk mewakili permainan. Misalnya, Anda dapat menghilangkan (atau menyingkat) properti yang tidak dimiliki, karena tidak dapat ditingkatkan atau digadaikan. Input tidak dapat menghilangkannya karena ini adalah daftar yang tidak terindeks.

Kompresi harus dilakukan dengan cara yang Anda dapat menghitung ukuran keluaran terburuk. Ini dapat mendiskualifikasi algoritma kompresi tertentu (kecuali Anda dapat membuktikan kasus terburuk, dan memberikan contoh input terburuk).

Kecuali kode sumber Anda adalah tidak masuk akal verbose, memberikan penjelasan tentang bagaimana permainan diwakili. Jawaban yang terdiri atas program golf dan output yang dikompres tidak disarankan. Misalnya, jika Anda menghilangkan nilai-nilai tertentu, jelaskan bagaimana cara menurunkannya dari output.

Penilaian / Aturan:

Penilaian didasarkan pada ukuran kompresi terburuk dalam bit , dan ukuran kode sumber dalam byte :

score = (outputBits * 2) + encoderSourceBytes

Jawaban lengkap harus mencakup:

  • Contoh keluaran
  • Sumber pembuat enkode
  • Sumber dekoder (tidak dihitung terhadap skor)

Semua penyandi harus program lengkap, dan celah standar dilarang. Menggunakan pustaka kompresi internal atau eksternal juga dilarang.

Pemenangnya adalah jawaban dengan skor terendah , sebagaimana didefinisikan di atas.

code-challenge compression Geobit
sumber
Hm, mengapa tidak memerlukan dekoder serta bukti bahwa pengkodean benar-benar berfungsi (dan dapat dikembalikan)? Juga bagaimana dengan memasukkan hal-hal seperti kompresi gzip bawaan? Itu akan membuatnya sangat sulit untuk mengetahui ukuran kompresi terburuk.
Martin Ender
@ m.buettner Diedit. Saya menambahkan sedikit tentang pustaka kompresi, dan sedikit tentang bukti kasus terburuk. Saya tidak benar-benar ingin menegakkan decoder. Poster dapat menyertakan mereka jika mereka ingin membuktikan solusi mereka, tetapi itu tidak dihitung dengan skor.
Geobits
Oh ya, saya tidak menyarankan untuk menambahkannya ke skor. Anda masih bisa memerlukan decoder (tidak bertali) sebagai bukti. Itu membuatnya lebih mudah untuk menguji apakah pengiriman dapat menangani kasus khusus.
Martin Ender
@ m.buettner Anda membuat poin yang bagus. Decoder itu.
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.Berada di penjara adalah lategame yang bagus karena Anda tidak membayar sewa. :)
undergroundmonorail

Jawaban:

4

(Sebuah jawaban baru-baru ini diedit, yang membawa pertanyaan ini menjadi perhatian saya, dan saya memutuskan untuk mencobanya walaupun itu adalah pertanyaan lama.)

Swift 1.2 - 1016 Poin (2 * 81 + 854)

Outputnya paling buruk 81 byte, dan berubah dengan jumlah pemain.

Salah satu dari kedua metode ini berfungsi. Versi Playground sedikit lebih panjang.

Compress Playground

(Asumsi Input.txtada di 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 - dijalankan di Terminal menggunakanswift Compress.swift

(Asumsi Input.txtada di 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"))

Contoh Input / Output

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
sumber
4

Pure C (3592 poin)

Outputnya adalah 182 byte. Ukurannya O (1), jadi ini adalah kasus terburuk.

Ini menggunakan sscanf secara ekstensif untuk membaca file, dan hanya membuang struct ke disk.

Saya harus sedikit memodifikasi input, karena contoh Anda tidak menyertakan 28 properti.

Untuk variabel, saya menamai mereka dari huruf pertama dari apa itu, atau jika itu akan bertentangan, huruf kedua (atau selanjutnya). Misalnya, Game, pLayer, pRoperty, dll.

compress.c (680 bytes):

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

kompres.c (pra-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);
}

Input / output :

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;

Terkompresi (182 byte):

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

Menjalankannya!

$ make compress decompress && ./compress && ./decompress && md5 input.txt output.txt
MD5 (input.txt) = fa655a5a17d67b188424ab0dcfdfb825
MD5 (output.txt) = fa655a5a17d67b188424ab0dcfdfb825
wjl
sumber
Terima kasih, saya memutar header untuk menghemat sedikit, dan memperbaiki skor saya untuk menghitung byte.
wjl
Sepertinya Anda dapat menyimpan beberapa byte dengan pengodean run-length setelahnya. Tidak yakin seberapa layaknya itu tetapi jika Anda melakukannya melalui byte melarikan diri itu juga harus dilakukan dengan baik dengan data yang tidak berulang. Heh.
cjfaure