Der Nahtschnitt-Algorithmus oder eine komplexere Version davon wird für die inhaltsbezogene Größenänderung von Bildern in verschiedenen Grafikprogrammen und Bibliotheken verwendet. Lass es uns spielen!

Ihre Eingabe wird ein rechteckiges zweidimensionales Array von Ganzzahlen sein.

Ihre Ausgabe ist dasselbe Array, eine Spalte enger, wobei ein Eintrag aus jeder Zeile entfernt wird, wobei diese Einträge einen Pfad von oben nach unten mit der niedrigsten Summe aller solcher Pfade darstellen.

https://en.wikipedia.org/wiki/Seam_carving

In der obigen Abbildung wird der Wert jeder Zelle in Rot angezeigt. Die schwarzen Zahlen sind die Summe aus dem Wert einer Zelle und der niedrigsten schwarzen Zahl in einer der drei darüber liegenden Zellen (auf die die grünen Pfeile zeigen). Die weiß hervorgehobenen Pfade sind die beiden Pfade mit der niedrigsten Summe, beide mit einer Summe von 5 (1 + 2 + 2 und 2 + 2 + 1).

In einem Fall, in dem zwei Pfade für die niedrigste Summe gebunden sind, spielt es keine Rolle, welche Sie entfernen.

Die Eingabe sollte von stdin oder als Funktionsparameter erfolgen. Es kann in einer Weise formatiert werden, die für die Sprache Ihrer Wahl geeignet ist, einschließlich Klammern und / oder Trennzeichen. Bitte geben Sie in Ihrer Antwort an, wie die Eingabe erwartet wird.

Die Ausgabe sollte in einem eindeutig begrenzten Format oder als Funktionsrückgabewert in der Entsprechung Ihrer Sprache zu einem 2D-Array (einschließlich verschachtelter Listen usw.) erfolgen.

Beispiele:

Input:
1 4 3 5 2
3 2 5 2 3
5 2 4 2 1
Output:
4 3 5 2      1 4 3 5
3 5 2 3  or  3 2 5 3
5 4 2 1      5 2 4 2

Input:
1 2 3 4 5
Output:
2 3 4 5

Input:
1
2
3
Output:
(empty, null, a sentinel non-array value, a 0x3 array, or similar)

BEARBEITEN: Die Zahlen sind alle nicht negativ und jede mögliche Naht hat eine Summe, die in eine vorzeichenbehaftete 32-Bit-Ganzzahl passt.

CJam, 51 44 Bytes

{_z,1$,m*{_1>.-W<2f/0-!},{1$.=:+}$0=.{WtW-}}

Dies ist eine anonyme Funktion, mit der ein 2D-Array aus dem Stapel entfernt und zurückgegeben wird.

Probieren Sie die Testfälle online im CJam-Interpreter aus . ¹

Idee

Dieser Ansatz iteriert über alle möglichen Kombinationen von Zeilenelementen, filtert diejenigen heraus, die nicht den Nähten entsprechen, sortiert nach der entsprechenden Summe, wählt das Minimum aus und entfernt die entsprechenden Elemente aus dem Array. ²

Code

_z,   e# Get the length of the transposed array. Pushes the number of columns (m).
1$,   e# Get the length of the array itself. Pushes the number of rows (n).
m*    e# Cartesian power. Pushes the array of all n-tuples with elements in [0 ... m-1].
{     e# Filter:
  _1> e#     Push a copy of the tuple with first element removed.
  .-  e#     Vectorized difference.
  W<  e#     Discard last element.
  2f/ e#     Divide all by 2.
  0-  e#     Remove 0 from the results.
  !   e#     Push 1 if the remainder is empty and 0 otherwise.
},    e#     Keep only tuples which pushed a 1.

      e# The filtered array now contains only tuples that encode valid paths of indexes.

{     e# Sort by:
  1$  e#     Copy the input array.
  .=  e#     Retrieve the element of each row that corresponds to the index in the tuple.
  :+  e#     Add all elements.
}$    e#
0=    e# Retrieve the tuple of indexes with minimum sum.
.{    e# For each row in the array and the corresponding index in the tuple:
  Wt  e#     Replace the element at that index with -1.
  W-  e#     Remove -1 from the row.
}

¹ _{Beachten Sie, dass CJam nicht zwischen leeren Arrays und leeren Strings unterscheiden kann, da Strings nur Arrays sind, deren Elemente Zeichen sind. Somit ist die Zeichenfolgendarstellung sowohl für leere Arrays als auch für leere Zeichenfolgen gleich "".}

² _{Während die zeitliche Komplexität des auf der Wikipedia-Seite gezeigten Algorithmus für eine n × m- Matrix 0 (nm) betragen sollte, ist diese mindestens 0 (m ⁿ ) .}

Haskell, 187 Bytes

l=length
f a@(b:c)=snd$maximum$(zip=<<map(sum.concat))$map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)$iterate((\e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e])=<<)[[y]|y<-[0..l b-1]]!!l c

Anwendungsbeispiel:

*Main> f [[1,4,3,5,2],[3,2,5,2,3],[5,2,4,2,1]]
[[4,3,5,2],[3,5,2,3],[5,4,2,1]]

*Main> f [[1],[2],[3]]
[[],[],[]]

*Main> f [[1,2,3,4,5]]
[[2,3,4,5]]

So funktioniert es, Kurzversion: Liste aller Pfade (1) erstellen, pro Pfad entsprechende Elemente (2) entfernen und alle verbleibenden Elemente (3) summieren. Nimm das Rechteck mit der größten Summe (4).

Längere Version:

Input parameters, assigned via pattern matching:
a = whole input, e.g. [[1,2,4],[2,5,6],[3,1,6]]
b = first line, e.g. [1,2,4]
c = all lines, except first, e.g. [[2,5,6],[3,1,6]]

Step (1), build all paths:

iterate((\e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e])=<<)[[y]|y<-[0..l b-1]]!!l c

     [[y]|y<-[0..l b-1]]           # build a list of single element lists
                                   # for all numbers from 0 to length b - 1
                                   # e.g. [[0],[1],[2]] for a 3 column input.
                                   # These are all possible start points

     \e@(f:_)->[f-1:e,f:e,min(f+1)(l b-1):e]
                                   # expand a list of paths by replacing each
                                   # path with 3 new paths (up-left, up, up-right)

     (...)=<<                      # flatten the list of 3-new-path lists into
                                   # a single list

     iterate (...) [...] !! l c    # repeatedly apply the expand function to
                                   # the start list, all in all (length c) times.


Step (2), remove elements

map(zipWith((uncurry((.drop 1).(++)).).flip splitAt)a)

     (uncurry((.drop 1).(++)).).flip splitAt
                                   # point-free version of a function that removes
                                   # an element at index i from a list by
                                   # splitting it at index i, and joining the
                                   # first part with the tail of the second part

      map (zipWith (...) a) $ ...  # per path: zip the input list and the path with
                                   # the remove-at-index function. Now we have a list
                                   # of rectangles, each with a path removed

Step (3), sum remaining elements

zip=<<map(sum.concat)             # per rectangle: build a pair (s, rectangle)
                                  # where s is the sum of all elements


Step (4), take maximum

snd$maximum                      # find maximum and remove the sum part from the
                                 # pair, again.

IDL 8,3, 307 Bytes

Meh, ich bin sicher, das wird nicht gewinnen, weil es lange dauert, aber hier ist eine einfache Lösung:

pro s,a
z=size(a,/d)
if z[0]lt 2then return
e=a
d=a*0
u=max(a)+1
for i=0,z[1]-2 do begin
e[*,i+1]+=min([[u,e[0:-2,i]],[e[*,i]],[e[1:*,i],u]],l,d=2)
d[*,i]=l/z[0]-1
endfor
v=min(e[*,-1],l)
r=intarr(z[1])+l
for i=z[1]-2,0,-1 do r[0:i]+=d[r[i+1],i]
r+=[0:z[1]-1]*z[0]
remove,r,a
print,reform(a,z[0]-1,z[1])
end

Ungolfed:

pro seam, array
  z=size(array, /dimensions)
  if z[0] lt 2 then return
  energy = array
  ind = array * 0
  null = max(array) + 1
  for i=0, z[1]-2 do begin
    energy[*, i+1] += min([[null, energy[0:-2,i]], [energy[*,i]], [energy[1:*,i], null]], loc ,dimension=2)
    ind[*, i] = loc / z[0] - 1
  endfor
  void = min(energy[*,-1], loc)
  rem = intarr(z[1]) + loc
  for i=z[1]-2, 0, -1 do rem[0:i] += ind[rem[i+1], i]
  rem += [0:z[1]-1]*z[0]
  remove, rem, array
  print, reform(array, z[0]-1, z[1])
end

Wir erstellen iterativ das Energiearray und verfolgen, in welche Richtung die Naht verläuft, und erstellen dann eine Entfernungsliste, sobald wir die endgültige Position kennen. Entfernen Sie die Naht durch 1D-Indizierung und stellen Sie die neuen Abmessungen wieder her.

JavaScript ( ES6 ) 197 209 215

Schritt für Schritt Implementierung des Wikipedia-Algorithmus.

Vermutlich kann mehr gekürzt werden.

Testen Sie das Snippet in Firefox.

// Golfed

F=a=>(u=>{for(r=[i=p.indexOf(Math.min(...p))];l--;i=u[l][i])(r[l]=[...a[l]]).splice(i,1)})
(a.map(r=>[r.map((v,i)=>(q[i]=v+~~p[j=p[i+1]<p[j=p[i-1]<p[i]?i-1:i]?i+1:j],j),q=[++l]),p=q][0],p=[l=0]))||r

// LESS GOLFED

U=a=>{
  p = []; // prev row
  u = a.map( r => { // in u the elaboration result, row by row
      q=[];
      t = r.map((v,i) => { // build a row for u from a row in a
        j = p[i-1] < p[i] ? i-1 : i; // find position of min in previous row
        j = p[i+1] < p[j] ? i+1 : j;
        q[i] = v + ~~p[j]; // values for current row
        // ~~ convert to number, as at first row all element in p are 'undefined'
        return j;//  position in u, row by row
      });
      p = q; // current row becomes previous row 
      return t;
  });
  n = Math.min(...p) // minimum value in the last row
  i = p.indexOf(n); // position of minimum (first if there are more than one present)
  r = []; // result      
  // scan u bottom to up to find the element to remove in the output row
  for(j = u.length; j--;)
  {
    r[j] = a[j].slice(); // copy row to output
    r[j].splice(i,1); // remove element
    i = u[j][i]; // position for next row
  }
  return r;
}

// TEST        
out=x=>O.innerHTML += x + '\n';        

test=[
  [[1,4,3,5,2],[3,2,5,2,3],[5,2,4,2,1]],
  [[1,2,3,4,5]],
  [[1],[2],[3],[4]]
];  

test.forEach(t=>{
  out('Test data:\n' + t.map(v=>'['+v+']').join('\n'));
  r=F(t);
  out('Golfed version:\n' + r.map(v=>'['+v+']').join('\n'))      
  r=U(t);
  out('Ungolfed version:\n' + r.map(v=>'['+v+']').join('\n'))
})  

<pre id=O></pre>

Pip, 91 Bytes

Dies wird keine Preise gewinnen, aber ich hatte Spaß daran zu arbeiten. Leerzeichen dienen nur kosmetischen Zwecken und sind nicht in der Byteanzahl enthalten.

{
 p:{(zaj-1+,3RMv)}
 z:a
 w:,#(a0)
 Fi,#a
  Fjw
   Ii
    z@i@j+:MN(pi-1)
 s:z@i
 Ti<0{
  j:s@?MNs
  a@i@:wRMj
  s:(p--i)
 }
 a
}

Dieser Code definiert eine anonyme Funktion, deren Argument und Rückgabewert verschachtelte Listen sind. Es implementiert den Algorithmus von der Wikipedia-Seite: a(das Argument) sind die roten Zahlen undz sind die schwarzen Zahlen.

Hier ist eine Version mit Testgeschirr:

f:{p:{(zaj-1+,3RMv)}z:aw:,#(a0)Fi,#aFjwIiz@i@j+:MN(pi-1)s:z@iTi<0{j:s@?MNsa@i@:wRMjs:(p--i)}a}
d:[
 [[1 4 3 5 2]
  [3 2 5 2 3]
  [5 2 4 2 1]]
 [[1 2 3 4 5]]
 [[1]
  [2]
  [3]]
 ]
Fld
 P(fl)

Ergebnisse:

C:\> pip.py minSumSeam.pip -p
[[4;3;5;2];[3;5;2;3];[5;4;2;1]]
[[2;3;4;5]]
[[];[];[]]

Und hier ist die grobe Entsprechung in Python 3. Wenn jemand eine bessere Erklärung des Pip-Codes möchte, fragen Sie einfach in den Kommentaren.

def f(a):
    z = [row.copy() for row in a]
    w = range(len(a[0]))

    for i in range(len(a)):
        for j in w:
            if i:
                z[i][j] += min(z[i-1][max(j-1,0):j+2])
    s = z[i]
    while i >= 0:
        j = s.index(min(s))
        del a[i][j]
        i -= 1
        s = z[i][max(j-1,0):j+2]
    return a