fork download
copy 
  1. # your code goes here
  2. import numpy as np
  3. import sys
  4.  
  5. MAX_SIZE = 25
  6.  
  7. class Latin(object):
  8.     def __init__(self, size):
  9.         self.size = size
  10.         self.possible = np.full((size, size, size), True, dtype=bool)
  11.         self.count = np.full((3, size, size), size, dtype=int)
  12.         self.chosen = np.full((3, size, size), -1, dtype=int)
  13.  
  14.     def decision(self):
  15.         axis, u, v = np.unravel_index(np.where(self.chosen == -1, self.count, self.size).argmin(), self.count.shape)
  16.         assert self.count[axis, u, v] != 0
  17.         if self.chosen[axis, u, v] == -1:
  18.             ws, = np.rollaxis(self.possible, axis)[:, u, v].nonzero()
  19.             return axis, u, v, list(ws)
  20.         else:
  21.             return None, None, None, None
  22.  
  23.     def choose(self, axis, u, v, w):
  24.         t = [u, v]
  25.         t[axis:axis] = [w]
  26.         i, j, k = t
  27.         assert self.chosen[0, j, k] == self.chosen[1, i, k] == self.chosen[2, i, j] == -1
  28.  
  29.         self.count[1, :, k] -= self.possible[:, j, k]
  30.         self.count[2, :, j] -= self.possible[:, j, k]
  31.         self.count[0, :, k] -= self.possible[i, :, k]
  32.         self.count[2, i, :] -= self.possible[i, :, k]
  33.         self.count[0, j, :] -= self.possible[i, j, :]
  34.         self.count[1, i, :] -= self.possible[i, j, :]
  35.         self.count[0, j, k] = self.count[1, i, k] = self.count[2, i, j] = 1
  36.         self.possible[i, j, :] = self.possible[i, :, k] = self.possible[:, j, k] = False
  37.         self.possible[i, j, k] = True
  38.         self.chosen[0, j, k] = i
  39.         self.chosen[1, i, k] = j
  40.         self.chosen[2, i, j] = k
  41.  
  42. def compress(square):
  43.     square = np.array(square, dtype=int)
  44.     size, size = square.shape
  45.     assert 0 < size <= MAX_SIZE
  46.     latin = Latin(size)
  47.     chosen = np.stack(np.argmax(square[:, :, np.newaxis] == np.arange(size)[np.newaxis, np.newaxis, :], axis=axis) for axis in range(3))
  48.     num, denom = size - 1, MAX_SIZE
  49.     while True:
  50.         axis, u, v, ws = latin.decision()
  51.         if axis is None:
  52.             break
  53.         w = chosen[axis, u, v]
  54.         num += ws.index(w)*denom
  55.         denom *= len(ws)
  56.         latin.choose(axis, u, v, w)
  57.     return '{:b}'.format(num + 1)[1:]
  58.  
  59. def decompress(bits):
  60.     num = int('1' + bits, 2) - 1
  61.     size = num % MAX_SIZE + 1
  62.     num //= MAX_SIZE
  63.     latin = Latin(size)
  64.     while True:
  65.         axis, u, v, ws = latin.decision()
  66.         if axis is None:
  67.             break
  68.         latin.choose(axis, u, v, ws[num % len(ws)])
  69.         num //= len(ws)
  70.     return latin.chosen[2].tolist()
  71.  
  72. total = 0
  73.  
  74. while True:
  75.         square = [list(map(int, l.split(','))) for l in iter(lambda: next(sys.stdin), '\n')]
  76.         print square
  77.  
  78.         if not square:
  79.             break
  80.  
  81.         bits = compress(square)
  82.         assert set(bits) <= {'0', '1'}
  83.         assert square == decompress(bits)
  84.         print('Square {}: {} bits'.format(len(square), len(bits)))
  85.         total += len(bits)
  86.  
  87. print('Total: {} bits = {} bytes'.format(total, total/8.0))
Runtime error #stdin #stdout #stderr 0.12s 25344KB
comments (?)
stdin
copy 
0

0,1
1,0

2,0,1
0,1,2
1,2,0
stdout
copy 
[[0]]
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 81, in <module>
  File "prog.py", line 47, in compress
AttributeError: 'module' object has no attribute 'stack'
https://ideone.com/fKGSQd
language:
Python (cpython 2.7.16)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!