Skip to content

Instantly share code, notes, and snippets.

@soharu
Created June 18, 2014 11:02
Show Gist options
  • Save soharu/3d8abd49e217076aa343 to your computer and use it in GitHub Desktop.
Save soharu/3d8abd49e217076aa343 to your computer and use it in GitHub Desktop.
IPSC 2014 B1
#!/usr/bin/env python
import unittest
import os
import sys
r, s, m = 43, 22, 2**32
X = []
def setup(xs):
X[:] = xs
x.cache.clear()
c.cache.clear()
def memoize(f):
def wrapper(i):
if i not in cache:
cache[i] = f(i)
return cache[i]
cache = wrapper.cache = {}
return wrapper
@memoize
def x(i):
if i >= 43:
return (x(i-s) - x(i-r) - c(i-1)) % m
else:
return X[i]
@memoize
def c(i):
if i >= 43 and x(i-s) - x(i-r) - c(i-1) < 0:
return 1
else:
return 0
class RandomGenerator:
def __init__(self, xs):
setup(xs)
self.i = 43
def random(self):
i = self.i
self.i += 1
return x(i)
class TestRandomGenerator(unittest.TestCase):
def test_sample(self):
rg = RandomGenerator([(999999999 * (i ** 3)) % m for i in range(43)])
self.assertEqual(rg.random(), 1050500563)
self.assertEqual(rg.random(), 4071029865)
self.assertEqual(rg.random(), 4242540160)
def get_new_postion_ang_value(rg, num_empty):
pos = rg.random() % num_empty
if (rg.random() % 10) == 0:
new_value = 4
else:
new_value = 2
return (pos, new_value)
def s2ns(str):
return [int(x) for x in str.split()]
def move_left(num_cells, cells):
values = []
new_cells = []
for i in range(num_cells):
if cells[i] != 0:
values.append(cells[i])
for i in range(len(values) - 1):
if values[i] == values[i + 1]:
values[i] *= 2
values[i + 1] = 0
for i in range(len(values)):
if values[i] != 0:
new_cells.append(values[i])
while len(new_cells) < num_cells:
new_cells.append(0)
return new_cells
def move_right(num_cells, cells):
values = []
new_cells = []
for i in range(num_cells):
if cells[i] != 0:
values.append(cells[i])
values = values[::-1]
for i in range(len(values) - 1):
if values[i] == values[i + 1]:
values[i] *= 2
values[i + 1] = 0
for i in range(len(values)):
if values[i] != 0:
new_cells.append(values[i])
while len(new_cells) < num_cells:
new_cells.append(0)
return new_cells[::-1]
class TestMove(unittest.TestCase):
def test_move_left(self):
self.assertEqual(move_left(8, [2,0,2,2,2,0,0,2]), [4,4,2,0,0,0,0,0])
self.assertEqual(move_left(4, [2,2,2,2]), [4,4,0,0])
self.assertEqual(move_left(4, [2,4,2,2]), [2,4,4,0])
self.assertEqual(move_left(4, [2,4,2,4]), [2,4,2,4])
self.assertEqual(move_left(4, [2,4,0,4]), [2,8,0,0])
self.assertEqual(move_left(4, [0,2,2,2]), [4,2,0,0])
self.assertEqual(move_left(4, [2,0,2,2]), [4,2,0,0])
self.assertEqual(move_left(4, [2,2,0,2]), [4,2,0,0])
self.assertEqual(move_left(4, [2,2,2,0]), [4,2,0,0])
self.assertEqual(move_left(4, [4,2,2,0]), [4,4,0,0])
def test_move_right(self):
self.assertEqual(move_right(8, [2,0,2,2,2,0,0,2]), [0,0,0,0,0,2,4,4])
self.assertEqual(move_right(8, [0,0,0,0,2,4,4,8]), [0,0,0,0,0,2,8,8])
self.assertEqual(move_right(8, [8,0,0,0,2,4,4,8]), [0,0,0,0,8,2,8,8])
self.assertEqual(move_right(4, [2,2,2,2]), [0,0,4,4])
self.assertEqual(move_right(4, [2,4,2,2]), [0,2,4,4])
self.assertEqual(move_right(4, [2,4,2,4]), [2,4,2,4])
self.assertEqual(move_right(4, [2,4,0,4]), [0,0,2,8])
self.assertEqual(move_right(4, [0,2,2,2]), [0,0,2,4])
self.assertEqual(move_right(4, [2,0,2,2]), [0,0,2,4])
self.assertEqual(move_right(4, [2,2,0,2]), [0,0,2,4])
self.assertEqual(move_right(4, [2,2,2,0]), [0,0,2,4])
self.assertEqual(move_right(4, [4,2,2,0]), [0,0,4,4])
def solve(num_cell, cells, xs, num_dirs, directions):
rg = RandomGenerator(xs)
for d in directions:
if d == 'l':
new_cells = move_left(num_cell, cells)
else:
new_cells = move_right(num_cell, cells)
num_empty = sum(1 if c == 0 else 0 for c in new_cells)
if num_empty == 0:
return new_cells
if new_cells == cells:
continue
pos, value = get_new_postion_ang_value(rg, num_empty)
if d == 'l':
new_cells[num_cell - num_empty + pos] = value
else:
new_cells[pos] = value
cells = new_cells
return cells
def main():
rl = lambda: sys.stdin.readline()
n = int(rl())
for i in range(n):
rl().strip() # ignore a blank line
result = solve(num_cell = int(rl().strip()),
cells = s2ns(rl().strip()),
xs = s2ns(rl().strip()),
num_dirs = int(rl().strip()),
directions = rl().strip())
print ' '.join([str(x) for x in result])
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment