Codejam 2015 - Only A working

A.py

import itertools

def solve(S):
    for people_added in itertools.count():
        standing = people_added
        Sp = S[:]
        for i,n in enumerate(Sp):
            if i <= standing:
                standing += n
                Sp[i] = 0
            else:
                break
        else:
            return people_added


lines = open('input').readlines()[1:]
for i, line in enumerate(lines):
    S = list(map(int,line.split()[1]))
    s = solve(S)
    print("Case #%d:" % (i+1), s)

B.py

"""
My error: I always divide the plate by 2, there are cases where 3 is more optimal
"""

import itertools,sys

def solve(plates0):
    states = [(plates0[:],False)]
    for t in itertools.count():
        new_states = []
        for plates,special in states:
            if sum(plates) == 0:
                return t
            #do nothing
            new_states.append((plates,False))
            #try to move the maximum of things from the biggest plate
            #to an empty plate
            i,n = max(enumerate(plates), key=lambda x:x[1])
            new_plates = plates[:]
            n1, n2 = n // 2 + n % 2, n // 2
            if n1 > 0 and n2 > 0:
                new_plates[i] = n1
                new_plates.append(n2)
                new_states.append((new_plates,True))
        for i, state in enumerate(new_states):
            plates, special = state
            if not special:
                for j,p in enumerate(plates):
                    plates[j] = max(p-1,0)
        states = new_states

lines = open(sys.argv[1]).readlines()
T = int(lines[0])
lines = lines[1:]
for i in range(T):
    plates = list(map(int,lines[1].split()))
    s = solve(plates)
    print("Case #%d:" % (i+1), s, plates)
    lines = lines[2:]

C.py

"""
Too slow, didn't find a good strategy
"""

I,J,K = 2,3,5

def mul(x,y):
    sign = 1 if x*y > 0 else -1
    x,y = abs(x),abs(y)
    r = None
    if x == 1:
        r = y
    elif y == 1:
        r = x
    elif x == y:
        r = -1
    elif x == I:
        if y == J:
            r = K
        else:
            r = -J #k
    elif x == J:
        if y == I:
            r = -K
        else:
            r = I
    elif x == K:
        if y == I:
            r = J
        else:
            r = -I
    return r*sign


def from_s(s):
    for x in s:
        if x == 'i':
            yield I
        elif x == 'j':
            yield J
        elif x == 'k':
            yield K

def to_s(l):
    r = ''
    for x in l:
        r += "" if x > 0 else "-"
        if x == 1:
            r += 1
        elif x == I:
            r += 'i'
        elif x == J:
            r += 'j'
        elif x == K:
            r += 'k'
        else:
            return False
    return r

def reduce(l):
    s = 1
    for x in l:
        s = mul(s,x)
    return s

assert mul(J,K) == I
assert mul(J,I) == -K
assert mul(-J,-K) == mul(J,K)
assert mul(-K, -K) == -1
assert reduce(from_s('jijiji')) == K

def solve(s,R):
    if len(s)*R < 3:
        return False
    S = list(from_s(s*R))
    s1 = 1
    for p1 in range(0,len(S)-2):
        s1 = mul(s1,S[p1])
        if s1 == I:
            s3 = 1
            for p3 in range(len(S)-1,p1+1):
                s3 = mul(s3, S[p3])
                if s3 == K:
                    p2r = reduce(S[p1+1:p3])
                    if p2r == J:
                        return True
    return False

lines = open('input').readlines()
T = int(lines[0])
lines = lines[1:]
for i in range(T):
    R = int(lines[0].split()[1])
    eq = lines[1].strip()
    s = solve(eq,R)
    print("Case #%d:" % (i+1), "YES" if s else "NO")
    lines = lines[2:]

D.py

"""
not working, should have done it on paper with case-based example (there are not many configurations possible)
"""

import sys, random, math

DEBUG = True

def log(*x,**kw):
    if DEBUG:
        print(*x,**kw)

def bounds(p):
    minx = min(p,key=lambda x:x[0])[0]
    miny = min(p,key=lambda x:x[1])[1]
    maxx = max(p,key=lambda x:x[0])[0]
    maxy = max(p,key=lambda x:x[1])[1]
    return minx,miny,maxx,maxy

def same(p1,p2):
    minx1,miny1,_,_ = bounds(p1)
    minx2,miny2,_,_ = bounds(p2)
    decx,decy = minx2-minx1,miny2-miny1
    p2_left = set(list(p2))
    for c in p1:
        nc = (c[0]+decx,c[1]+decy)
        if nc in p2_left:
            p2_left.remove(nc)
        else:
            return False
    return True

def visu(p):
    minx,miny,maxx,maxy = bounds(p)
    for y in range(miny,maxy+1):
        for x in range(minx,maxx+1):
            if (x,y) in p:
                log('X',end='')
            else:
                log('.',end='')
        log()
    log('~')

def rot(x,y):
    return -y,x

assert rot(1,0) == (0,1)
assert rot(10,2) == (-2,10)
assert rot(*rot(10,2)) == (-10,-2)

def havesame(x,L):
    for y in L:
        if same(x,y):
            return True
    return False

def trans(p):
    L = []
    r1 = {rot(x,y) for x,y in p}
    r2 = {rot(x,y) for x,y in r1}
    r3 = {rot(x,y) for x,y in r2}
    for r in p, r1,r2,r3:
        if not havesame(r, L):
            L.append(r)
        m1 = {(x,-y) for x,y in r}
        m2 = {(-x,y) for x,y in r}
        m3 = {(-x,-y) for x,y in r}
        for m in m1,m2,m3:
            if not havesame(m,L):
                L.append(m)
    return L

def gen(n):
    if n == 1:
        return [{(0,0)}]
    pieces = []
    for p in gen(n-1):
        for c in p:
            for d in (1,0),(0,1),(-1,0),(0,-1):
                nc = (c[0]+d[0],c[1]+d[1])
                if nc not in p:
                    np = set(list(p))
                    np.add(nc)
                    for p2 in pieces:
                        if havesame(np, trans(p2)):
                            break
                    else:
                        pieces.append(np)
    return pieces

a = {(1, 0), (0, 0), (1, 1), (2, 1)}
b = {(0, -1), (1, 0), (0, 0), (1, 1)}
assert havesame(a, trans(b))

def vizT(T):
    for l in T:
        for x in l:
            log(x,end='')
        log()

def can_place(p, x, y, T, R, C):
    minx,miny,maxx,maxy = bounds(p)
    xmax, ymax = x+(maxx-minx), y+(maxy-miny)
    if xmax >= C or ymax >= R:
        return False
    for c in p:
        Tx,Ty = (c[0]-minx)+x,(c[1]-miny)+y
        if T[Ty][Tx] != 1:
            return False
    return True

def place(p, x, y, T, R, C):
    minx,miny,maxx,maxy = bounds(p)
    for c in p:
        Tx,Ty = (c[0]-minx)+x,(c[1]-miny)+y
        T[Ty][Tx] = 0

def full(T):
    return sum(sum(l) for l in T) == 0

def already_there(T0,Ts):
    for T in Ts:
        for i,l in enumerate(T):
            if l != T0[i]:
                break
        else:
            return True
    return False

def try_to_complete(pieces, T0, R, C):
    Ts = [T0]
    X = len(pieces[0])
    while True:
        nextTs = []
        for T in Ts:
            S = sum(sum(l) for l in T)
            if 0 < S < X:
                return False
            if full(T):
                return True
            for p in pieces:
                for ptrans in trans(p):
                    for y in range(R):
                        for x in range(C):
                            if can_place(ptrans, x, y, T, R, C):
                                T2 = [L[:] for L in T]
                                place(ptrans, x, y, T2, R, C)
                                if not already_there(T2, nextTs):
                                    nextTs.append(T2)
        if len(nextTs) == 0:
            return False
        Ts = nextTs
    return True

def try_to_complete_R(pieces, T, R, C, p): #p = p_rich
    placed_one_time = False
    for ptrans in trans(p):
        for y in range(R):
            for x in range(C):
                if can_place(ptrans, x, y, T, R, C):
                    placed_one_time = True
                    log("placed at",x,y)
                    T2 = [L[:] for L in T]
                    place(ptrans, x, y, T2, R, C)
                    vizT(T2)
                    log('-')
                    ret = try_to_complete(pieces, T2, R, C)
                    if ret:
                        log("GABRIEL managed to complete it!")
                        return True, placed_one_time
    log("GABRIEL didn't managed to complete it! placed ?",placed_one_time)
    return False, placed_one_time

def solve(X, R, C):
    if X == 1:
        return "GABRIEL"
    pieces = gen(X)
    #random.shuffle(pieces)
    line1 = [1 for _ in range(C)]
    T1 = [line1[:] for _ in range(R)]
    line2 = [1 for _ in range(R)]
    T2 = [line2[:] for _ in range(C)]
    for p in pieces:
        log("RICHARD pick:")
        visu(p)
        log()
        completed, placed_one_time = try_to_complete_R(pieces, T1, R, C,p)
        if not completed and placed_one_time:
            return "RICHARD"
    return "GABRIEL"

assert can_place({(1, 0), (0, 0), (1, -1)},0,0,[(1,1,1) for _ in range(3)],3,3)
assert solve(3, 3, 4) == "GABRIEL"

L = open(sys.argv[1]).readlines()[1:]
for i, l in enumerate(L):
    params = list(map(int,l.split()))
    r = solve(*params)
    print("Case #%d:" % (i+1),r,params)