Laisser Aêtre un mpar nmatrice rectangulaire de positifs entiers, où met nsont également positifs entiers.

Nous nous intéressons aux chemins RoD («droite ou bas») de la cellule supérieure gauche de la cellule Ainférieure droite; dans un chemin RoD, chaque cellule successive du chemin est soit une cellule à droite de, soit une cellule en bas de la cellule précédente.

Étant donné un tel chemin RoD, nous pouvons prendre la somme des cellules Adans ce chemin.

Par exemple, considérons la matrice 4 x 3:

[ [1, 2, 3, 4],
  [5, 1, 6, 7],
  [8, 2, 1, 1] ]

Ensuite, nous pouvons considérer le chemin RoD:

1 > 2   3   4
    v
5   1   6   7
    v
8   2 > 1 > 1

qui a une somme de 1+2+1+2+1+1=8. Il convient de noter que ce chemin a la plus petite somme de tous les chemins RoD possibles du coin supérieur gauche au coin inférieur droit de cette matrice.

Ainsi, le défi proposé est de fournir la fonction / le programme le plus court dans la langue de votre choix qui génère la somme minimale qu'un chemin RoD du coin supérieur gauche au coin inférieur droit peut avoir dans une matrice donnée A.

Les failles habituelles interdites sont en vigueur. Votre contribution peut être dans n'importe quel format raisonnable; votre sortie doit être un entier.

C'est du golf de code; les réponses sont notées par nombre d'octets.

Cas de test

[ [5] ] -> 5

[ [5, 2] ] -> 7

[ [5], 
  [2] ] -> 7

[ [ 9 , 1 , 12, 3 ],
  [ 12, 11, 6 , 11],
  [ 12, 9 , 2 , 11] ] -> 40

[ [ 6 , 8 , 11, 2 ],
  [ 3 , 6 , 7 , 6 ],
  [ 6 , 2 , 8 , 12] ] -> 37

[ [ 4 , 5 , 8 , 4 ],
  [ 6 , 5 , 9 , 4 ],
  [ 2 , 5 , 6 , 8 ] ] -> 31

[ [ 4 , 5 , 15, 18, 30],
  [ 26, 26, 3 , 4 , 5 ],
  [ 7 , 9 , 29, 25, 14],
  [ 16, 1 , 27, 13, 27],
  [ 23, 11, 25, 24, 12],
  [ 17, 23, 7 , 14, 5 ] ] -> 94

[ [ 10, 15, 7 , 2 , 9 ],
  [ 24, 5 , 2 , 1 , 25],
  [ 2 , 12, 14, 30, 18],
  [ 28, 4 , 12, 22, 14],
  [ 15, 21, 21, 11, 4 ],
  [ 21, 15, 21, 29, 9 ] ] -> 103

J , 42 octets

v(+}.<.}:)&.>/@{.[:</.(2#v=._1+1#.$){.!._]

Essayez-le en ligne!

Comment ça fonctionne

v(+}.<.}:)&.>/@{.[:</.(2#v=._1+1#.$){.!._]
                         v=._1+1#.$         Sum of two dimensions - 1; assign to v
                                            (v is a verb)
                      (2#          ){.!._]  Extend the given array in both dimensions
                 [:</.  Extract the antidiagonals as boxed arrays
v             @{.  Take the first `v` antidiagonals
 (       )&.>/     Reduce over unboxed items:
   }.<.}:            Given the right item R, take the minimum of R[1:] and R[:-1]
  +                  Add to the left item

Illustration

1 2 3 4  Input array, dimensions = 3,4
5 1 6 7
8 2 1 1

1 2 3 4 _ _  Extended to 6,6 with filler _ (infinity)
5 1 6 7 _ _
8 2 1 1 _ _
_ _ _ _ _ _
_ _ _ _ _ _
_ _ _ _ _ _

1            Diagonalize and take first 6 rows
5 2
8 1 3
_ 2 6 4
_ _ 1 7 _
_ _ _ 1 _ _

Reduction: left+min(right[1:], right[:-1])
1                                          1  => 8
5 2                               5  2  => 10 7
8 1 3                   8 1 3  => 12 5 11
_ 2 6 4      _ 2 6 4 => _ 4 8 12
_ _ 1 7 _ => _ _ 2 8 _
_ _ _ 1 _ _

JavaScript (ES6), 78 77 76 octets

m=>(M=g=s=>(v=(m[y]||0)[x])?g(s+=v,y++)|g(s,x++,y--)*x--|M<s?M:M=s:0)(x=y=0)

Essayez-le en ligne!

Commenté

m => (                      // m[] = input matrix
  M =                       // initialize the minimum M to a non-numeric value
  g = s =>                  // g = recursive function taking the current sum s
    (v = (m[y] || 0)[x]) ?  //   if the current cell v is defined:
      g(s += v, y++) |      //     do a recursive call at (x, y + 1)
      g(s, x++, y--) * x--  //     do a recursive call at (x + 1, y)
      |                     //     if at least one call did not return 0 (which means
                            //     that we haven't reached the bottom-right corner)
      M < s ?               //     or M is less than s (false if M is still non-numeric):
        M                   //       return M unchanged
      :                     //     else:
        M = s               //       update M to s, and return this new value
    :                       //   else (we're outside the bounds of the matrix):
      0                     //     return 0
)(x = y = 0)                // initial call to g with s = x = y = 0

Haskell, 63 57 octets

f x@((a:_:_):c:d)=a+min(f$c:d)(f$tail<$>x)
f x=sum$id=<<x

Essayez-le en ligne!

f x@((a:_:_):c:d)=           -- if it's at least a 2x2 matrix
   a+min                     -- add the top left element to the minimum of the
                             -- path costs of
        f$c:d                --   the matrix with the first row dropped and
        f$tail<$>x           --   the matrix with the first column dropped
f x=                         -- else, i.e. a 1xm or nx1 matrix, i.e. a vector
    sum$id=<<x               -- return the sum of this vector

MATL , 38 36 30 29 octets

Merci à @Giuseppe d' avoir signalé une erreur, maintenant corrigée.

lyZyqsG&nghZ^Yc!tsGz=Z)Ys)sX<

Essayez-le en ligne! Ou vérifiez tous les cas de test .

Explication

l        % Push 1
y        % Input, implicit. Duplicate from below. Pushes the input below
         % the current 1, and a copy of the input on top
Zy       % Size of input. Gives [m, n]
qs       % Subtract 1 element-wise, sum. Gives m+n-2
G        % Push input again
&n       % Push size as two separate numbers. Gives m, n
gh       % Transform n into 1 and concatenate horizontally. Gives [m, 1]
Z^       % Cartesian power of [m, 1] raised to m+n-2. This produces the
         % Cartesian tuples as row of a matrix. A typical tuple may be
         % [1, m, 1, m, m]. This will define a path along the matrix in
         % linear, column-wise indexing (down, then across). So 1 means
         % move 1 step down, and m means move m steps "down", which is
         % actually 1 step to the right
Yc       % Concatenate strcat-like. This prepends the 1 that is at the
         % bottom of the stack to each row
!        % Transpose. Each tuple (extended with initial 1) is now a column
!ts      % Duplicate, sum of each column
Gz       % Number of nonzeros of input. Gives m*n-1
=Z)      % Keep only columns that sum m*n. That means that, starting from
Ys       % Cumulative sum of each column. This defines the path
)        % Index: pick entries specified by the path
s        % Sum of each column
X<       % Minimum
         % Display, implicit

R , 90 octets

function(m){l=sum(m|1)
if(l>1)for(i in 2:l)m[i]=m[i]+min(m[i-1],m[max(0,i-nrow(m))])
m[l]}

Essayez-le en ligne!

La solution naïve: parcourez le tableau (en bas des colonnes), en remplaçant chaque entrée par la somme d'elle-même et le minimum de ses voisins ci-dessus et à gauche, s'ils existent, puis renvoyez la dernière entrée.

Perl 6 , 57 54 octets

my&f={|.flat&&.[0;0]+min (f(.[1..*]),f $_>>[1..*])||0}

Essayez-le en ligne!

Explication

my&f={                                               }  # Function f
      |.flat&&  # Return empty slip if matrix is empty
              .[0;0]+  # Value at (0,0) plus
                     min  # Minimum of
                          f(.[1..*])   # Rows 1..*
                                     f $_>>[1..*]  # Columns 1..*
                         (          ,            )||0  # Or 0 if empty

Röda , 100 89 octets

f A{g={|x,y|{g(x-1,y)if[x>0];g(x,y-1)if[y>0];[0]if[x+y=0]}|min|[A[x][y]+_]}g#A-1,#A[0]-1}

Essayez-le en ligne!

-9 octets grâce au charlatan des vaches

Python 3 , 108 octets

def f(A,m,n,i=0,j=0):r=i+1<m and f(A,m,n,i+1,j);d=j+1<n and f(A,m,n,i,j+1);return A[i][j]+min(r or d,d or r)

Essayez-le en ligne!

Non golfé

def f(A, m, n, i=0, j=0):
    right = i + 1 < m and f(A, m, n, i + 1, j)
    down  = j + 1 < n and f(A, m, n, i, j + 1)
    return A[i][j] + min(right or down, down or right)

Gelée , 21 octets

ZI_.ỊȦ
ŒJŒPÇƇLÐṀœị⁸§Ṃ

Essayez-le en ligne!

Comment?

ZI_.ỊȦ - Link 1: isDownRight?: List of 2d indices (limited to having no repetitions)
Z      - transpose
 I     - deltas (vectorises)
  _.   - subtract 1/2 (vectorises)
    Ị  - insignificant? (effectively _.Ị here is like "v in {0,1}? 1 : 0")
     Ȧ - any & all (0 if a 0 is present when flattened, else 1)

ŒJŒPÇƇLÐṀœị⁸§Ṃ - Main Link: list of lists of integers, A
ŒJ             - multi-dimensional indices of A
  ŒP           - power-set
     Ƈ         - filter keep only those truthy by:
    Ç          -   last link as a monad
       ÐṀ      - filter keep only those maximal by:
      L        -   length
           ⁸   - chain's left argument, A
         œị    - multi-dimensional index into (vectorises)
            §  - sum each
             Ṃ - minimum

APL (Dyalog Classic) , 37 32 octets

{⊃⌽,9e9(⊢⌊⍵+(2⊣⌿⍪)⌊2⊣/,)⍣≡+⍀+\⍵}

Essayez-le en ligne!

+⍀+\ des sommes partielles horizontalement et verticalement - cela fournit une surestimation initiale pour les chemins vers chaque carré

9e9(... )⍣≡appliquer "..." jusqu'à convergence, à chaque étape en passant un très grand nombre (9 × 10 ⁹ ) comme argument de gauche

, ajouter 9e9 -s à gauche de l'estimation actuelle

2⊣/ prendre la première de chaque paire de cellules consécutives, en supprimant efficacement la dernière colonne

2⊣⌿⍪ même chose verticalement - mettre 9e9 en haut et déposer la dernière rangée

(2⊣⌿⍪) ⌊ 2⊣/, minima

⍵+ ajouter la matrice d'origine

⊢⌊ essayer d'améliorer les estimations actuelles avec ce

⊃⌽, cellule en bas à droite

Fusain , 46 octets

≔Ｅ§θ⁰∧κΣ§θ⁰ηＦθ«≔§η⁰ζＦＬι«≔⁺⌊⟦§ηκζ⟧§ικζ§≔ηκζ»»Ｉζ

Essayez-le en ligne! Le lien est vers la version détaillée du code. Explication: Ce serait probablement plus court s'il y avait trois arguments reducedans Charcoal.

≔Ｅ§θ⁰∧κΣ§θ⁰η

Préremplissez le tableau de travail avec de grandes valeurs à l'exception de la première qui est zéro.

Ｆθ«

Faites une boucle sur les lignes de l'entrée.

≔§η⁰ζ

Initialisez le total actuel avec le premier élément du tableau de travail.

ＦＬι«

Faites une boucle sur les colonnes de l'entrée.

≔⁺⌊⟦§ηκζ⟧§ικζ

Prenez le minimum du total actuel et de l'élément actuel du tableau de travail et ajoutez l'élément actuel de l'entrée pour donner le nouveau total actuel.

§≔ηκζ

Et stockez-le dans le tableau de travail prêt pour la ligne suivante.

»»Ｉζ

Imprimez le total une fois la saisie terminée.

Gelée , 17 octets

XL,1ẋLḊŒ!1;ⱮÄịẎ§Ṃ

Essayez-le en ligne!

Java 8, 197 193 octets

m->{int r=m.length-1,c=m[0].length-1,i=r,a;for(;i-->0;m[i][c]+=m[i+1][c]);for(i=c;i-->0;m[r][i]+=m[r][i+1]);for(i=r*c;i-->0;r=m[i/c][i%c+1],m[i/c][i%c]+=a<r?a:r)a=m[i/c+1][i%c];return m[0][0];}

-4 octets grâce à @ceilingcat .

Essayez-le en ligne.

Explication générale:

En fait, j'ai déjà fait ce défi il y a environ un an avec le projet Euler # 81 , sauf qu'il était limité à une matrice carrée au lieu d'unN parM matrice. J'ai donc légèrement modifié mon code à l'époque pour en tenir compte.

Je fais d'abord la somme de la dernière ligne et de la colonne la plus à droite de la dernière cellule vers l'arrière. Utilisons donc l'exemple de matrice du défi:

1, 2, 3, 4
5, 1, 6, 7
8, 2, 1, 1

La dernière cellule reste la même. La seconde dernière cellule de la rangée du bas est la somme: 1+1 = 2et de même pour la seconde dernière cellule de la colonne de droite: 1+7 = 8. Nous continuons à le faire, alors maintenant la matrice ressemble à ceci:

 1,  2,  3, 12
 5,  1,  6,  8
12,  4,  2,  1

Après cela, nous regardons toutes les lignes restantes une par une de bas en haut et de droite à gauche (sauf pour la dernière colonne / ligne), et nous recherchons chaque cellule à la fois en dessous et à droite de la cellule pour voir lequel est plus petit.

Ainsi, la cellule contenant le nombre 6devient 8, car en 2dessous, elle est plus petite que sa 8droite. Ensuite, nous regardons le 1suivant (à gauche), et faisons de même. Cela 1devient 5, car le 4dessous est plus petit que le 8droit.

Donc, après avoir terminé avec l'avant-dernière ligne, la matrice ressemble à ceci:

 1,  2,  3, 12
10,  5,  8,  8
12,  4,  2,  1

Et nous continuons à le faire pour toute la matrice:

 8,  7, 11, 12
10,  5,  8,  8
12,  4,  2,  1

Maintenant, la toute première cellule contiendra notre résultat, qui est 8 dans ce cas.

Explication du code:

m->{                    // Method with integer-matrix input and integer return-type
  int r=m.length-1,     //  Amount of rows minus 1
      c=m[0].length-1,  //  Amount of columns minus 1
      i=r,              //  Index integer
      a;                //  Temp integer
  for(;i-->0;m[i][c]+=m[i+1][c]);
                        //  Calculate the suffix-sums for the rightmost column
  for(i=c;i-->0;m[r][i]+=m[r][i+1]);
                        //  Calculate the suffix-sums for the bottom row
  for(i=r*c;i-->0       //  Loop over the rows and columns backwards
      ;                 //     After every iteration:
       r=m[i/c][i%c+1], //      Set `r` to the value left of the current cell
       m[i/c][i%c]+=a<r?//      If `a` is smaller than `r`:
                 a      //       Add `a` to the current cell
                :       //      Else:
                 r)     //       Add `r` to the current cell
      a=m[i/c+1][i%c];  //    Set `a` to the value below the current cell
  return m[0][0];}      //  Return the value in the cell at index {0,0} as result

Brachylog , 26 25 octets

∧≜.&{~g~g|hhX&{b|bᵐ}↰+↙X}

Essayez-le en ligne!

-1 octet car la coupure n'est pas nécessaire - vous ne pouvez pas prendre la tête d'une liste vide

Il y a probablement beaucoup de place pour jouer au golf, mais j'ai besoin de dormir.

L'approche se résume à essayer chaque valeur pour la sortie, la plus petite en premier, ( ∧≜.) jusqu'à ce qu'un chemin puisse être trouvé ( b|bᵐ) dans le coin inférieur droit ( ~g~g) qui produit cette somme ( hhX&...↰+↙X).

Java (JDK) , 223 octets

Prend les entrées sous forme de liste 2D d'entiers.

19 octets supplémentaires pour import java.util.*;inclus.

import java.util.*;m->{var l=m.get(0);int s=m.size(),c=l.size(),x=-1>>>1,a=l.get(0);return s*c<2?a:Math.min(s>1?n.n(new Vector(m.subList(1,s))):x,c>1?n.n(new Vector<>(m){{replaceAll(l->new Vector(l.subList(1,c)));}}):x)+a;}

Essayez-le en ligne!

Comment ça fonctionne

import java.util.*;                                     // Import needed for Vector class
m->{                                                    // Lambda that takes a 2D list of integers
    var r=m.get(0);                                     // Store first row in variable
    int h=m.size(),                                     // Store number of rows
        w=r.size(),                                     // Store number of columns
        x=-1>>>1,                                       // Store int max
        a=r.get(0);                                     // Store the current cell value
    return h*w<2?a:                                     // If matrix is single cell return value
        Math.min(                                       // Otherwise return the minimum of...

            h>1?                                        // If height is more than 1
                n.n(                                    // Recursively call this function with 
                    new Vector(m.subList(1,h))):        // a new matrix, without the top row
                x,                                      // Otherwise use int max as there is no row below this

            w>1?                                        // If width is more than 1
                n.n(new Vector<>(m){{                   // Recursively call this function with a new matrix             
                    replaceAll(                         // where all columns have been replaced with 
                        l->new Vector(l.subList(1,w))   // cloned lists without the leftmost column
                    );
                }}):                                    // Otherwise use int max as there is
                x                                       // no column to the right of this
        )+a;                                            // Add the current cell value to the result before returning
}

Python 2 , 86 octets

f=lambda A:len(A)>1<len(A[0])and A[0][0]+min(f(zip(*A)[1:]),f(A[1:]))or sum(sum(A,()))

Essayez-le en ligne!

Si Best la transposition de A, alors la définition du problème implique cela f(A)==f(B).

A[1:]est le tableau Amanquant sa ligne supérieure. zip(*A[1:])est le tableau Amanquant de sa colonne la plus à gauche et transposé. sum(sum(A,()))est la somme de tous les éléments A.

Si An'a qu'une seule colonne ou une seule ligne, il n'y a qu'un seul chemin, donc fretourne la somme de tous les éléments dans A; sinon, nous récursions et renvoyons la somme de A[0][0]+ le plus petit fde Amanquer la ligne du haut et fde Amanquer la colonne la plus à gauche.