17
\$\begingroup\$

Given a string representing the current state of a game of Monopoly at the beginning of a player's turn, compress all the necessary data into the smallest output. Answers will be judged by output size and source size.

Note: There are many regional variations, but all references in this post to property names, etc, are based on this board.


Input:

Input will be given as a single ; separated string. This string is given to the program in whatever way is customary in your chosen language, whether that's stdin, arguments, etc.

The unformatted input looks like this:

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)

An example formatted input is this:

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;

Taken bit by bit:

3;1;

There are 3 players, and it is player 1's turn (zero-indexed, so the second player)

Players

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

The first player:

  • is not bankrupt
  • has $1546 cash on hand
  • owns 0 get-out-of-jail-free cards
  • is on position 14 (Virginia Ave)
  • is not in jail

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.

The third player is bankrupt, and more information is neither required nor given.

Properties

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

Properties are listed in order around the board, starting from Mediterranean and ending at Boardwalk. Properties that cannot be owned are not included in this list, so there will be a total of 28. Improvement level 0 means unimproved. Level 1 is one house, up to level 5 for a hotel. A -1 for owner means it is not owned by any player.

According to standard rules, a property that is mortgaged must be owned and must not be improved. A property that is improved must be owned and must not be mortgaged.

In addition, for a property to be improved, a player must own the entire color block. For the purposes of this game, we do not care if properties are being improved "evenly".

Note that these positions are not the same as the player positions given above. For instance, a player on the 5 position would be on Reading Railroad, which is the third property in the list (since Go, Community Chest, and Income Tax cannot be owned). Player positions run from 0(Go) clockwise to 39(Boardwalk).

Cards

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;

Each of the Chance and Community Chest decks have 16 total cards. The numbers are presented as they appear in the currently shuffled deck. For this example, the first card pulled off the Chance deck will be card 0, followed by card 1 (whoever shuffled that deck sucks). The first card pulled from Community chest is card 3, then 12.

Don't worry about what each card means (the card text), except for card 0. That is the Get Out of Jail Free card for that deck. If a player owns it, it will be at the end of the list, represented as -1.


Output:

You must output (to console, stdout, or file) a representation of the game state. This must include all information required to represent the game. For example, you could omit (or abbreviate) unowned properties, since they can neither be improved or mortgaged. The input cannot omit them because it is an unindexed list.

Compression should be done in a way that you can compute worst-case output size. This may disqualify certain compression algorithms (unless you can prove the worst case, and give an example of worst-case input).

Unless your source code is unreasonably verbose, give an explanation of how the game is represented. Answers consisting of nothing but a golfed program and compressed output are discouraged. For example, if you are omitting certain values, explain how it is possible to derive them from the output.


Scoring/Rules:

Scoring is based both on worst-case compression size in bits, and source code size in bytes:

score = (outputBits * 2) + encoderSourceBytes

A complete answer must include:

  • Output example
  • Encoder source
  • Decoder source (not counted against score)

All encoders must be complete programs, and standard loopholes are forbidden. Using built-in or external compression libraries is also forbidden.

The winner is the answer with the lowest score, as defined above.

\$\endgroup\$
  • \$\begingroup\$ Hm, why not require a decoder as well as a proof that the encoding actually works (and is revertible)? Also what about including stuff like built-in gzip compression? That would make it really hard to figure out the worst-case compression size. \$\endgroup\$ – Martin Ender May 1 '14 at 16:56
  • \$\begingroup\$ @m.buettner Edited. I added a bit about compression libraries, and a bit about proof of worst-case. I don't really want to enforce a decoder. Posters can include them if they wish to prove their solution, but it won't be counted against the score. \$\endgroup\$ – Geobits May 1 '14 at 17:15
  • \$\begingroup\$ Oh yeah, I wasn't suggesting to add them to the score. You could still require an (ungolfed) decoder as proof. That makes it easier to test whether submissions can handle special cases. \$\endgroup\$ – Martin Ender May 1 '14 at 17:19
  • \$\begingroup\$ @m.buettner You make an excellent point. Decoders it is. \$\endgroup\$ – Geobits May 1 '14 at 17:24
  • 2
    \$\begingroup\$ 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. Being in jail is good lategame because you're not paying rent. :) \$\endgroup\$ – undergroundmonorail May 1 '14 at 17:50
4
\$\begingroup\$

(An answer was recently edited, which brought this question to my attention, and I decided to give it a try although its an old question.)

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

The output is at worst 81 bytes, and changes with the amount of players.

Either of the two methods work. The Playground version is slightly longer.

Compress Playground

(Assumes Input.txt is in the 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 - run in Terminal using swift Compress.swift

(Assumes Input.txt is on the 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"))

Sample 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
\$\endgroup\$
4
\$\begingroup\$

Pure C (3592 points)

The output is 182 bytes. The size is O(1), so this is the worst case.

This uses sscanf extensively to read the files, and simply dumps the structs to disk.

I had to slightly modify the input, as your example didn't include 28 properties.

For variables, I named them from the first letter of what it is, or if that would conflict, the second (or subsequent) letter. For example, Game, pLayer, pRoperty, etc.

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

compress.c (pre-golfed)

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

Compressed (182 bytes):

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 

Run it!

$ make compress decompress && ./compress && ./decompress && md5 input.txt output.txt
MD5 (input.txt) = fa655a5a17d67b188424ab0dcfdfb825
MD5 (output.txt) = fa655a5a17d67b188424ab0dcfdfb825
\$\endgroup\$
  • \$\begingroup\$ Thanks, I rolled the header in to save a bit, and fixed my score to count bytes. \$\endgroup\$ – wjl May 2 '14 at 21:16
  • \$\begingroup\$ Looks like you could save some bytes with run-length encoding after. Not sure how feasible that is but if you do it via an escape byte it should also do well with non-repeating data. Heh. \$\endgroup\$ – cjfaure May 3 '14 at 9:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.