IPSC 2014 B1

gistfile1.py

#!/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()