Programmieren lernen

PROGRAM GO;

(*
  Idea: Each tile is a tri-state (one of 0/1/2). Hence, we can use a
  tri-ary representation. For simplicity, we write always 5 tiles
  into one byte. This works because 3^5 <= 2^8. For 19 x 19 tiles, one
  needs 19*19/5 = 73 bytes.

  One could do with 72 bytes, as the Shannon entropy is only 71.5.
  However, then one would have to represent the whole board as one
  BIGINT (even using INT64 does not help, as 64/log_2(3) = 40.4).
*)

CONST
  N = 19;  // 19 x 19 board
  L = 73;  // # bytes needed, 19*19 / floor(8/log_2(3))

TYPE
  TBoard = ARRAY [0..N-1,0..N-1] OF Byte; // 0=empty, 1=black, 2=white
  TMem   =  ARRAY [0..L-1] OF Byte;

PROCEDURE RandomBoard (VAR board : TBoard);
// Fill board randomly
VAR i,j : INTEGER;
BEGIN
  Randomize;
  FOR i := Low(board) TO High(board) DO
    FOR j := Low(board[i]) to High(Board[i]) DO
      board[i,j] := Random(3);
END;

PROCEDURE PrintBoard (CONST board : TBoard);
// Print board to console
VAR
  i,j : INTEGER;
  str : STRING;
BEGIN
  str := '-BW';                     // Characters for empty / black / white
  FOR i := Low(board) TO High(board) DO
  BEGIN
    FOR j := Low(board[i]) to High(Board[i]) DO
      Write(' ',str[Board[i,j]+1],' ');
    Writeln;
  END;
END;

PROCEDURE CompressBoard (CONST board : TBoard; VAR mem : TMem);
// Compress board into mem.
// Group 5 cells, store cell[1]*1 + cell[2]*3 + cell[3]*0 + ...
//             ... + cell[5]*81
VAR i,j,k,base : INTEGER;
BEGIN
  k := -1;                              // index into mem
  base := 1000;                         // start new memory cell
  FOR i := Low(board) TO High(board) DO
    FOR j := Low(board[i]) to High(Board[i]) DO
    BEGIN
      IF base*3 > 256 THEN              // no space left, use next cell
      BEGIN
        Inc(k); mem[k] := 0; base := 1; // initialize next cell
      END;
      Inc(mem[k],board[i,j]*base);      // poke current tile into current cell
      base := base * 3;                 // base 3
    END;
END;

PROCEDURE UncompressBoard (CONST mem : TMem; VAR board : TBoard);
// Uncompress mem into board
// Each memory cell contains 5 tiles
VAR i,j,k,base : INTEGER;
BEGIN
  k := -1;
  base := 1000;
  FOR i := Low(board) TO High(board) DO
    FOR j := Low(board[i]) to High(Board[i]) DO
    BEGIN
      IF base*3 > 256 THEN
      BEGIN
        Inc(k); base := 1;
      END;
      board[i,j] := (mem[k] div base) mod 3;
      base := base * 3;
    END;
END;


VAR
  b1,b2 : TBoard;          // two boards
  m     : TMem;            // one memory
  
BEGIN
  RandomBoard(b1);         // b1 is random
  Writeln('b1');           // output
  PrintBoard(b1);
  CompressBoard(b1,m);     // b1 -> memory
  UncompressBoard(m,b2);   // memory -> b2
  Writeln('b2');           // output b2, hopefully same as b1 :-)
  PrintBoard(b2);
END.

                

Lösung von: Martin Hirt (ETH Zürich)