#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Nov  4 23:11:59 2025

@author: vincentleprince
"""

"""Données"""

CoutsTaches = [[2,8,6,7],[1,3,15,5]] # coût des tâches

CoutsTrans = [[1,2,1],[2,2,3]]  # coût des transitions

n = len(CoutsTaches[0])



""" Résolution de bas en haut
"""


Sol = [[0,0,0,0],[0,0,0,0]]

Sol[0][0] , Sol[1][0] = CoutsTaches[0][0] , CoutsTaches[1][0]





for i in range(1,n):
    Sol[0][i] = min(Sol[0][i-1] , Sol[1][i-1] + CoutsTrans[1][i-1]) \
                                      + CoutsTaches[0][i]
    Sol[1][i] = min(Sol[1][i-1] , Sol[0][i-1] + CoutsTrans[0][i-1]) \
                                      + CoutsTaches[1][i]
    
print(min(Sol[0][n-1],Sol[1][n-1]))


# Version permettant d'obtenir le chemin

Sol = [[0 for etape in range(n)] for numCh in range(2)]
Sol[0][0] , Sol[1][0] = CoutsTaches[0][0] , CoutsTaches[1][0]

tabPrec = [[None for etape in range(n)] for numCh in range(2)]





for i in range(1,n):
    for numCh in range(2):
        autreCh = 1 - numCh # numéro de l'autre machine
        
        if  Sol[autreCh][i-1]  + CoutsTrans[autreCh][i-1]< Sol[numCh][i-1] :
            Sol[numCh][i] = Sol[autreCh][i-1]  + CoutsTrans[autreCh][i-1] \
                                       + CoutsTaches[numCh][i]
            tabPrec[numCh][i] = autreCh
        else :
            Sol[numCh][i] = Sol[numCh][i-1] + CoutsTaches[numCh][i]
            tabPrec[numCh][i] = numCh


# On détermine le coût minimal d'un chemin ainsi que le numéro de la chaîne d'arrivée  :

if Sol[0][n-1] < Sol[1][n-1]:
    coutMin , numCh = Sol[0][n-1] , 0
else :
    coutMin , numCh = Sol[1][n-1] , 1
    
# On reconstruit le chemin en partant de l'arrivée
cheminOpt = [numCh]
k = n-1 # numéro de l'étape correspondant à numCh
while k > 0:
    numCh = tabPrec[numCh][k]
    cheminOpt.append(numCh)
    k -= 1

cheminOpt.reverse()  
print(coutMin)
print(cheminOpt)

            
"""Résolution par mémoïzation"""

Sol = [[0 for etape in range(n)] for numCh in range(2)]
 
tabPrec = [[None for etape in range(n)] for numCh in range(2)]


def remplitSol(numCh,i):
    if i == 0:
        Sol[numCh][i]  = CoutsTaches[numCh][0]
    else : 
        if Sol[numCh][i]  == 0:
            autreCh = 1 - numCh
            remplitSol(numCh,i-1)
            remplitSol(autreCh,i-1)
            if  Sol[autreCh][i-1]  + CoutsTrans[autreCh][i-1] <  Sol[numCh][i-1]:
                Sol[numCh][i]  =  Sol[autreCh][i-1]  + CoutsTrans[autreCh][i-1] \
                                                   + CoutsTaches[numCh][i]
                tabPrec[numCh][i]  = autreCh
            else : 
                Sol[numCh][i]  = Sol[numCh][i-1] +  CoutsTaches[numCh][i]
                tabPrec[numCh][i] = numCh

for numCh in range(2):
    remplitSol(numCh,n-1)
    
print(Sol)
print(tabPrec)