Mur de brique

 Le site « hackerrank.com » permet à quiconque d’y définir un profile et de tenter de résoudre des problèmes non triviaux pour prouver leur habilité en programmation. Un problème est offert et tu entres la solution dans une forme définie, tu appuies sur « verify », ils vérifient la solution avec des données et affichent une belle note à ton dossier si réussi. Un employeur peut chercher des candidats dans leur base de donnée.

Le problème

 Vous possédez une infinité de bloques de hauteur 1 et dont la longueur peut être de 1, 2, 3 ou 4. Avec ces bloques il faut construire un mur de hauteur n et de largeur m avec les caractéristiques suivantes :

 -pas de trou

 -les briques sont toutes placées horizontalement

         -le mur doit être solide avec aucune ligne droite verticale qui traverse toutes les rangées de brique (juste du mortier de haut en bas).

Combien de murs différents?

Voici une solution du site « medium.com »

#####################################################

def legoBlocks(n, m):
   MOD = (10**9 +7)

   # Step 1: O(W)
   # The number of combinations to build a single row
   # As only four kinds of sizes, so
   # base case:
   # if width is 0, combination is 1
   # if width is 1, combination is 1
   # if width is 2, combination is 2
   # if width is 3, combination is 4
   row_combinations = [1, 1, 2, 4]

   # Build row combinations up to current wall's width
   while len(row_combinations) <= m:
       row_combinations.append(sum(row_combinations[-4:]) % MOD)

   # Step 2: O(W)
   # Compute total combinations
   # for constructing a wall of height N of varying widths
   total = [pow(c, n, MOD) for c in row_combinations]

   # Step 3: O(W^2)
   # Find the number of unstable wall configurations
   # for a wall of height N of varying widths
   unstable = [0, 0]

   # Divide the wall into left part and right part,
   # and calculate the combination of left part and right part.
   # From width is 2, we start to consider about violation.
   for i in range(2, m + 1):
   # i: current total width
   # j: left width
   # i - j: right width
   # f: (left part - previous vertical violation)*right part
       f = lambda j: (total[j] - unstable[j]) * total[i - j]
   result = sum(map(f, range(1, i)))
   unstable.append(result % MOD)

   # Print the number of stable wall combinations
   return (total[m] - unstable[m]) % MOD

Trois étapes pour résoudre le problème

1- tous les cas une ligne

2- étendre à toutes les lignes

3- soustraire les mur instables

#####################################################

# solution récursive
#
MOD=10**9+7
def one_row(n): # ways to tile a single row with blocks of width 4,3,2,1
   dp=[0]*max(n+1,5)
   dp[0] = 1
   for i in range(1,n+1):
       sum_=0
       for j in range(1,4+1):
           sum_+=dp[i-j]
       dp[i] = sum_
   return dp[n]

def all_possibilities(n, m):
   return one_row(m) ** n

def legoBlocksR(n, m):  # n is height m is width
   # print(f"one_row {one_row(5)}")
   if m == 1: return 1
   all_poss = all_possibilities(n, m) % MOD
   # print(f"all_poss {all_poss}")
   broken = 0
   for i in range(1, m):
       broken += (legoBlocksR(n, i) * all_possibilities(n, m - i))
   return (all_poss - broken) % MOD
#
# fin solution récursive

###############################################

Autre solution non récursive prise sur YouTube d’une dame qui participe au concours « hackerrank »

url : www.youtube.com/watch?v=u9fL52Hryiw

#solution dame video
def legoBlocksD(h,w):
   modulo = 10**9+7
   row = [0 for _ in range(w+1)]
   if w>=1:
       row[1] = 1
   if w>=2:
       row[2] = 2
   if w>=3:
       row[3] = 4
   if w>=4:
       row[4] = 8
   if w>=5:
       for i in range(5,w+1):
           row[i] = (row[i-1]+row[i-2]+row[i-3]+row[i-4]) % modulo

   total = row.copy()
   for _ in range(2,h+1):
       for i in range(w+1):
           total[i] = (row[i] * total[i]) % modulo

   solid = [0 for _ in range(w+1)]
   solid[1] = 1
   for ww in range(2, w+1):
       unsolid_sum = 0
       for i in range(1,w):
           unsolid_sum += ((solid[i]*total[ww-i]) % modulo)
       solid[ww] = (total[ww] - unsolid_sum) % modulo

   return solid[w] % modulo

##########################################