Visualization Notes: April 2022

Thursday, April 28, 2022

🏙 Controlled Inflation

Codejam 1B 2022. Thinking about Task 2

xxxxxxxxxx
 
import networkx as nx,pylab as pl
def graph(minmax):
    g=nx.MultiDiGraph()
    n=len(minmax)
    g.add_node('start0')
    g.add_edge('start0','min0',weight=minmax[0][0])
    g.add_edge('start0','max0',weight=minmax[0][1])
    for i in range(n):
        g.add_node('min%d'%i)
        g.add_node('max%d'%i)
        g.add_edge('min%d'%i,'max%d'%i,
                   weight=minmax[i][1]-minmax[i][0])
        g.add_edge('max%d'%i,'min%d'%i,
                   weight=minmax[i][1]-minmax[i][0])
        if i!=n-1:
            g.add_edge('min%d'%i,'min%d'%(i+1),
                       weight=abs(minmax[i][0]-minmax[i+1][0]))
            g.add_edge('min%d'%i,'max%d'%(i+1),
                       weight=abs(minmax[i][0]-minmax[i+1][1]))
            g.add_edge('max%d'%i,'min%d'%(i+1),
                       weight=abs(minmax[i][1]-minmax[i+1][0]))
            g.add_edge('max%d'%i,'max%d'%(i+1),
                       weight=abs(minmax[i][1]-minmax[i+1][1]))
    return g
def path(g):
    sum=10**12
    gl=list(g.nodes)
    min_path=[]
    for node in [gl[-1],gl[-2]]:
        for path in nx.all_simple_paths(g,'start0',node):
            if set(path)==set(gl):
                path_len=nx.path_weight(g,path,'weight')
                print(' '.join(path),'=>',path_len)
                if sum>path_len: 
                    sum=path_len
                    min_path=path
    return sum,min_path

xxxxxxxxxx
 
minmax=[[10,40],[20,60],[50,60],[100,110],[30,70]]
n=len(minmax); g=graph(minmax)
sum,min_path=path(g)
print('\n min_path:\n',' '.join(min_path),'=>',sum)

xxxxxxxxxx
 
for i in range(len(min_path)-1):
    print((min_path[i],min_path[i+1]),
          g.get_edge_data(min_path[i],min_path[i+1]))

xxxxxxxxxx
 
def gdraw(g,n):
    fig=pl.figure(1,figsize=(8,6),dpi=60)
    pos=nx.planar_layout(g)
    nx.draw(
        g,pos,with_labels=True,
        font_color='white',node_size=1500,
        node_color='slategray',edge_color='slategray')
    el=[('min%d'%i,'max%d'%i) for i in range(n)]+\
       [('max%d'%i,'min%d'%i) for i in range(n)]
    nx.draw_networkx_edges(
        g,pos,edgelist=el,
        edge_color='darkred',width=2)
    pl.show()
gdraw(g,n)

Sunday, April 17, 2022

📑 Chain Reactions

Codejam Qualification Round 2022. Task 4

Python Only


class DGraph:
    def __init__(self,n,f,p):
        self.N=n
        self.P=p
        self.F=f
        self.G={k:0 for k in range(n)}
        self.D={k:0 for k in range(n)}
    def add_edges(self):
        for i,el in enumerate(self.P):
            self.G[i]=el-1
            if el!=0:
                self.D[el-1]+=1 
    def max_fun(self):
        indegree=self.D
        inits=[]
        for i in range(self.N):
            if indegree[i]==0:
                inits.append(i)
        fmin=[10**12]*self.N
        fsum=sum([self.F[i] for i in inits])
        while inits:
            i=inits.pop(0)
            node=self.G[i]
            if node!=-1:
                indegree[node]-=1
                fmin[node]=min([fmin[node],self.F[i]])
                if indegree[node]==0:
                    inits.append(node)
                    self.F[node]=max([self.F[node],fmin[node]])
                    fsum+=self.F[node]-fmin[node]
        return fsum
T=int(input())
for t in range(T):
    N=int(input())
    F=list(map(int,input().split()))
    P=list(map(int,input().split()))
    dgraph=DGraph(N,F,P)
    dgraph.add_edges()
    FSUM=dgraph.max_fun()
    print('Case #{}: {}'.format(t+1,FSUM))

xxxxxxxxxx
 
class DGraph:
    def __init__(self,n,f,p):
        self.N=n
        self.P=p
        self.F=f
        self.G={k:0 for k in range(n)}
        self.D={k:0 for k in range(n)}
    def add_edges(self):
        for i,el in enumerate(self.P):
            self.G[i]=el-1
            if el!=0:
                self.D[el-1]+=1 
    def max_fun(self):
        indegree=self.D
        inits=[]
        for i in range(self.N):
            if indegree[i]==0:
                inits.append(i)
        fmin=[10**12]*self.N
        fsum=sum([self.F[i] for i in inits])
        while inits:
            i=inits.pop(0)
            node=self.G[i]
            if node!=-1:
                indegree[node]-=1
                fmin[node]=min([fmin[node],self.F[i]])
                if indegree[node]==0:
                    inits.append(node)
                    self.F[node]=max([self.F[node],fmin[node]])
                    fsum+=self.F[node]-fmin[node]
        return fsum
@interact
def chain_reaction(
    T=slider([1,2,3],default=1),
    N=input_box('4 5 8',type=str,label='N',width=30,height=1),
    F=input_box('60 20 40 50\n'+\
                '3 2 1 4 5\n'+\
                '100 100 100 90 80 100 90 100',
                type=str,label='F',width=30,height=3),
    P=input_box('0 1 1 2\n'+\
                '0 1 1 1 0\n'+\
                '0 1 2 1 2 3 1 3',
                type=str,label='P',width=30,height=3)):
    N=int(str(N).split(' ')[T-1])
    F=[int(el) for el in str(F).split('\n')[T-1].split()]
    P=[int(el) for el in str(P).split('\n')[T-1].split()]
    print(T,N,F,P)
    dgraph=DGraph(N,F,P)
    dgraph.add_edges()
    FSUM=dgraph.max_fun()
    print('Case #{}: {}'.format(T,FSUM))

Sunday, April 10, 2022

📑 3D Printing 2

Codejam Qualification Round 2022. Task 2 Variant 2

Python Only


def gen_vector(v,s=10**6):
    if sum(v) < s:
        yield 'IMPOSSIBLE'
    else:
        for c in range(v[0],1,-1):
            m=min([v[1],10**6-c])
            y=min([v[2],10**6-c-m])
            k=10**6-c-m-y
            yield '%d %d %d %d'%(c,m,y,k)
T=int(input())
for t in range(T):
    N=[]
    for i in range(3):
        N.append(list(map(int,input().split())))
    v=[min([N[i][j] for i in range(3)]) 
       for j in range(4)]
    print('Case #%d: %s'%(t+1,next(gen_vector(v))))

xxxxxxxxxx
 
def gen_vector(v,s=10**6):
    if sum(v)<s:
        yield 'IMPOSSIBLE'
    else:
        for c in range(v[0],1,-1):
            m=min([v[1],10**6-c])
            y=min([v[2],10**6-c-m])
            k=10**6-c-m-y
            yield '%d %d %d %d'%(c,m,y,k)
@interact
def ddd_printing(
    T=slider([1,2,3],default=1),
    N1=input_box('300000 200000 300000 500000\n'+\
                 '1000000 1000000 0 0\n'+\
                 '768763 148041 178147 984173',
                 type=str,label='N1',width=30,height=3),
    N2=input_box('300000 200000 500000 300000\n'+\
                 '0 1000000 1000000 1000000\n'+\
                 '699508 515362 534729 714381',
                 type=str,label='N2',width=30,height=3),
    N3=input_box('300000 500000 300000 200000\n'+\
                 '999999 999999 999999 999999\n'+\
                 '949704 625054 946212 951187',
                 type=str,label='N3',width=30,height=3)):
    N1=str(N1).split('\n')
    N2=str(N2).split('\n')
    N3=str(N3).split('\n')
    NN=[[N1[i],N2[i],N3[i]] for i in range(3)]
    print('C M Y K:')
    [print(el) for el in NN[T-1]+['\n']]
    N=[[int(n) for n in NN[T-1][i].split()]
       for i in range(3)]
    v=[min([N[i][j] for i in range(3)]) 
       for j in range(4)]
    gen=gen_vector(v)
    print('Case #%d: %s'%(T,next(gen)))

Saturday, April 9, 2022

📑 Punched Cards 2

Codejam Qualification Round 2022. Task 1 Variant 2

Python Only


def gen_table(r,c):
    for i in range(2*r+1):
        for j in range(2*c+1):
            if (i < 2 and j < 2):
                yield '.'
            else:
                el=((j+1)%2)*((i+1)%2)*'+'+\
                   (j%2)*((i+1)%2)*'-'+\
                   ((j+1)%2)*(i%2)*'|'+\
                   (j%2)*(i%2)*'.'
                yield el
        yield '\n'
T=int(input())
for t in range(T):
    N=input()
    [R,C]=[int(n) for n in N.split()]
    gen=gen_table(R,C)
    print('Case #{}:'.format(t+1))
    print(''.join(gen))

xxxxxxxxxx
 
def gen_table(r,c):
    for i in range(2*r+1):
        for j in range(2*c+1):
            if (i<2 and j<2):
                yield '.'
            else:
                el=((j+1)%2)*((i+1)%2)*'+'+\
                   (j%2)*((i+1)%2)*'-'+\
                   ((j+1)%2)*(i%2)*'|'+\
                   (j%2)*(i%2)*'.'
                yield el
        yield '\n'
@interact
def punched_cards(
    T=slider([1,2,..,5],default=1),
    RCS=input_box('4 3|2 2|5 8|2 5|4 6',
                  type=str,label='R C',width=50)):
    RC=str(RCS).split('|')
    pretty_print('Rows & Columns:',RC[:T])
    for t in range(T):
        [R,C]=[int(rc) for rc in RC[t].split()]
        gen=gen_table(R,C)
        print('Case #{}:'.format(t+1))
        print(''.join(gen))

📑 Double or One

Codejam 1A Round 2022. Task 1

Python Only


T=int(input())
for t in range(T):
    S=input()
    NS=''; i=0; temp=''
    while i < len(S)-1:
        if (len(set(S[i:])) == 1) and (len(S[i:]) > 1):
            NS+=S[i:-1]
            break
        else:
            if S[i+1] > S[i]:
                NS+=2*temp+2*S[i]
                temp=''
            elif S[i+1] < S[i]:
                NS+=temp+S[i]
                temp=''
            else:
                temp+=S[i]
        i+=1  
    print('Case #{}: {}'.format(t+1,NS+S[-1]))


def gen_first(S):
    i=0; temp=''
    while i < len(S)-1:
        if (len(set(S[i:])) == 1) and (len(S[i:]) > 1):
            yield S[i:-1]
            break
        else:
            if S[i+1] > S[i]:
                yield 2*temp+2*S[i]
                temp=''
            elif S[i+1] < S[i]:
                yield temp+S[i]
                temp=''
            else:
                temp+=S[i]
        i+=1
    yield S[-1]
T=int(input())
for t in range(T):
    S=input()
    NS=''.join(gen_first(S))
    print('Case #{}: {}'.format(t+1,NS))

xxxxxxxxxx
 
@interact
def twice_ones(
    T=[1,2,3],
    S=input_box('PEEL\nAAAAAAAAAA\nCODEJAMDAY',
                 type=str,label='S',width=20,height=3)):
    S=str(S).split('\n'); s=S[T-1]
    print('input: ',s)
    ns=''; i=0; temp=''
    while i < len(s)-1:
        if (len(set(s[i:])) == 1) and (len(s[i:]) > 1):
            ns+=s[i:-1]
            break
        else:
            if s[i+1] > s[i]:
                ns+=2*temp+2*s[i]
                temp=''
            elif s[i+1] < s[i]:
                ns+=temp+s[i]
                temp=''
            else:
                temp+=s[i]
        i+=1  
    print('Case #{}: {}'.format(T,ns+s[-1]))

Sunday, April 3, 2022

📑 Dice Rows

Codejam Qualification Round 2022. Task 3

Python Only


T=int(input())
for t in range(T):
    N=int(input())
    S=input()
    k=N
    if k>4:
        S=sorted([int(s) for s in S.split()])[::-1]
        k=N=min([N,S[0]])
        for i in range(N):
            if S[i] < N-i:
                k-=1
    print('Case #{}: {}'.format(t+1,k))

xxxxxxxxxx
 
@interact
def dice_rows(
    T=[1,2,3,4],
    N=input_box('4,6,10,2',
                 type=str,label='N',width=24,height=1),
    S=input_box('6 10 12 8\n5 4 5 4 4 4\n10 10 7 6 7 4 4 5 7 4\n10 5',
                 type=str,label='S',width=20,height=4)):
    N=str(N).split(','); n=int(N[T-1])
    S=str(S).split('\n'); s=S[T-1]
    print(n,'dices with a certain number of sides:',s)
    k=n
    if k>4:
        s=sorted([int(el) for el in s.split()])[::-1]
        k=n=min([n,s[0]])
        for i in range(n):
            if s[i]<n-i:
                k-=1
    print('Case #{}: {}'.format(T,k))

📑 3D Printing

Codejam Qualification Round 2022. Task 2

Python Only


T=int(input())
for t in range(T):
    C,M,Y,K=[],[],[],[]
    for i in range(3):
        N=input()
        N=[int(n) for n in N.split()]
        C+=[N[0]]; M+=[N[1]]; Y+=[N[2]]; K+=[N[3]]
    c,m,y,k=min(C),min(M),min(Y),min(K)
    if c+m+y+k<10**6:
        R='IMPOSSIBLE'
    else:
        m=min([m,10**6-c])
        y=min([y,10**6-c-m])
        k=10**6-c-m-y
        R='{} {} {} {}'.format(c,m,y,k)
    print('Case #{}: {}'.format(t+1,R))

xxxxxxxxxx
 
@interact
def ddd_printing(
    T=slider([1,2,3],default=1),
    N1=input_box('300000 200000 300000 500000\n'+\
                 '1000000 1000000 0 0\n'+\
                 '768763 148041 178147 984173',
                 type=str,label='N1',width=30,height=3),
    N2=input_box('300000 200000 500000 300000\n'+\
                 '0 1000000 1000000 1000000\n'+\
                 '699508 515362 534729 714381',
                 type=str,label='N2',width=30,height=3),
    N3=input_box('300000 500000 300000 200000\n'+\
                 '999999 999999 999999 999999\n'+\
                 '949704 625054 946212 951187',
                 type=str,label='N3',width=30,height=3)):
    N1=str(N1).split('\n')
    N2=str(N2).split('\n')
    N3=str(N3).split('\n')
    NN=[[N1[i],N2[i],N3[i]] for i in range(3)]
    print('C M Y K:')
    [print(el) for el in NN[T-1]+['\n']]
    C,M,Y,K=[],[],[],[]
    for i in range(3):
        N=[int(n) for n in NN[T-1][i].split()]
        C+=[N[0]]; M+=[N[1]]; Y+=[N[2]]; K+=[N[3]]  
    c,m,y,k=min(C),min(M),min(Y),min(K)
    if c+m+y+k<10**6:
        R='IMPOSSIBLE'
    else:
        m=min([m,10**6-c])
        y=min([y,10**6-c-m])
        k=10**6-c-m-y
        R='{} {} {} {}'.format(c,m,y,k)
    print('Case #{}: {}'.format(T,R))

📑 Punched Cards

Codejam Qualification Round 2022. Task 1

Python Only


T=int(input())
for t in range(T):
    N=input()
    print('Case #{}:'.format(t+1))
    [R,C]=[int(n) for n in N.split()]
    str1='..+-+'+(C-2)*'-+'
    str2='..|.|'+(C-2)*'.|'
    str3='+-+-+'+(C-2)*'-+'
    str4='|.|.|'+(C-2)*'.|'
    [print(el) for el in [str1,str2,str3,str4,str3]]
    for i in range(R-2):
        print(str4)
        print(str3)

xxxxxxxxxx
 
@interact
def punched_cards(
    T=slider([1,2,..,5],default=1),
    RCS=input_box('4 3|2 2|5 8|2 5|4 6',
                  type=str,label='R C',width=50)):
    RC=str(RCS).split('|')
    pretty_print('Rows & Columns:',RC[:T])
    for t in range(T):
        print('Case #{}:'.format(t+1))
        [R,C]=[int(rc) for rc in RC[t].split()]
        str1='..+-+'+(C-2)*'-+'
        str2='..|.|'+(C-2)*'.|'
        str3='+-+-+'+(C-2)*'-+'
        str4='|.|.|'+(C-2)*'.|'
        [print(el) for el in [str1,str2,str3,str4,str3]]
        for i in range(R-2):
            print(str4)
            print(str3)