Einführung

Ein Feld sei ein Rechteck, das nur mit den Zeichen -und gefüllt ist [0-9]. Ein Beispiel für ein Feld ist:

11-011123
111-010--
0010---01
111-01234

Sie sehen, dass dieses Feld in drei kleinere Bereiche unterteilt wurde:

Um die Punktzahl eines kleineren Bereichs zu berechnen, addieren wir einfach alle Zahlen. Beispielsweise:

11
111
0010
111

1 + 1 + 1 + 1 + 1 + 0 + 0 + 1 + 0 + 1 + 1 + 1 = 9

Die Gesamtpunktzahl für diesen Bereich beträgt 9 . Wir machen jetzt dasselbe für den zweiten Bereich:

   011123
    010

0 + 1 + 1 + 1 + 2 + 3 + 0 + 1 + 0 = 9

Die Gesamtpunktzahl beträgt ebenfalls 9 . Nun müssen wir den letzten Bereich untersuchen:

       01
    01234

0 + 1 + 0 + 1 + 2 + 3 + 4 = 11

Dies hat eine Gesamtpunktzahl von 11 . Die höchste Punktzahl auf dem Feld ist 11, also müssen wir diese ausgeben.

Die Aufgabe

Bei einem gegebenen Feld (in Form einer 2D-Zeichenfolge, eines Arrays usw.) wird die höchste Punktzahl auf dem Feld ausgegeben . Sie können davon ausgehen, dass die angegebenen Felder immer mindestens eine Ziffer enthalten. Das ist Code-Golf , also gewinnt die Einsendung mit der geringsten Anzahl von Bytes!

Testfälle

Testfall 1:

Input:
1

Output:
1

Testfall 2:

Input:
1-1-1-1
-1-1-1-
2-1-1-1
-1-1-1-

Output:
2

Testfall 3:

Input:
12-45-
4-65-9
87-654
12-487
45----
684764

Output:
69

Testfall 4:

Input:
111-12
------
21--10

Output:
3

MATL , 54 51 49 Bytes

n:"G~1@(2Y6Z+leG45>1e*5M@)*]vtz:"otY*g]G48-X:*sX>

Die Eingabe ist ein 2D-Zeichen-Array im MATL (AB) -Format mit einem ;Zeilentrennzeichen. Die Eingaben im Beispiel und in den Testfällen sind jeweils:

['11-011123';'111-010--';'0010---01';'111-01234']
['1']
['1-1-1-1';'-1-1-1-';'2-1-1-1';'-1-1-1-']
['12-45-';'4-65-9';'87-654';'12-487';'45----';'684764']
['111-12';'------';'21--10']

Probieren Sie es online!

Erläuterung

Dies funktioniert durch Erstellen einer Adjazenzmatrix des Graphen, der durch die Beziehung "verbunden" definiert ist. Betrachten Sie als Beispiel das 3 × 4-Feld

52-4
15-8
3-72

Einträge in einem 2D-Array lassen sich in MATL mithilfe der linearen Indexierung (Spalten-Hauptindexierung) leicht beschreiben. Im 3 × 4-Fall wird der lineare Index jedes Eintrags als angegeben

1  4  7 10
2  5  8 11
3  6  9 12

Die Adjazenzmatrix wird mithilfe der Matrixmultiplikation in Schritten erstellt. Im ersten Schritt werden unmittelbare Nachbarn berücksichtigt. Beispielsweise ist der mit 3 indizierte Punkt ein Nachbar von sich selbst und der mit Index 2. Es ist kein Nachbar von 6, da dieser Punkt keine Nummer gemäß dem Feld enthält. In diesem Beispiel ist die Adjazenzmatrix der Beziehung "unmittelbarer Nachbar" die als gegebene 12 × 12-Matrix L

1 1 0 1 0 0 0 0 0 0 0 0
1 1 1 0 1 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0 0 0
0 1 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0
0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 1 0 1 1

(Es ist ersichtlich, dass Spalte 3 1in den Zeilen 2 und 3 einen Wert hat .) Diese Matrix ist immer symmetrisch und ihre Diagonale hat einen Wert 1für Punkte, die keinen Wert enthalten -.

Der nächste Schritt wäre die Adjazenzmatrix der Beziehung "verbunden mit höchstens einem Punkt dazwischen ". Um es zu erhalten, genügt es, L mit sich selbst zu multiplizieren und Einträge ungleich Null auf zu setzen 1. Im Allgemeinen wird die Adjazenzmatrix der Beziehung "verbunden durch einen Pfad" M erhalten, indem L auf einen Exponenten (im Matrixsinn) angehoben wird , der die maximal mögliche Pfadlänge darstellt. Eine obere der maximalen Weglänge gebunden ist , die Anzahl der von Null verschiedenen Einträge in L .

Das direkte Berechnen der Matrixleistung kann zu einem Überlauf führen, da große Zahlen schnell auftreten. Daher ist es besser, nach und nach mit derselben Matrix zu multiplizieren und Einträge ungleich Null nach jedem Schritt in 1 umzuwandeln, um zu verhindern, dass sich große Zahlen aufbauen.

Die Spalte i von M stellt die Punkte dar, die (durch einen beliebigen Pfad) mit dem Punkt i verbunden sind . Das Ebenenfeld kann nun in linearer Reihenfolge auf einen Spaltenvektor c reduziert werden, wobei jeder Eintrag die entsprechende Zahl oder einen undefinierten Wert für enthält -. Also in diesem Fall wäre c

5
1
3
2
5
-
-
-
7
4
8
2

Wenn man jede Spalte von M elementweise mit c multipliziert und die Summe jeder Spalte berechnet , erhält man für jeden Punkt i die Gesamtpunktzahl des Flächenpunktes , zu dem i gehört. Ein Bereich wird durch alle Punkte definiert, die miteinander verbunden sind. Beachten Sie, dass viele Spalten dasselbe Ergebnis liefern. Die Spalten i und j ergeben nämlich die gleiche Summe, wenn die Punkte i und j verbunden sind (zur gleichen Fläche gehören). Das Endergebnis ist das Maximum dieser Summen.

        % Implicitly take input: 2D char array
n:      % Range [1,...,N], where N is number of entries in the input
"       % For loop. Each iteration builds a row of matrix L
  G     %   Push input again
  ~     %   Logical negate: transform into matrix of zeros
  1     %   Push 1, to be written into a matrix entry
  @     %   Iteration index. Ranges from 1 to N
  (     %   Write that 1 into the N-th entry (linear order)
  2Y6   %   Push array [0 1 0; 1 1 1; 0 1 0]: mask of immediate neighbours
  Z+    %   Convolve and keep same-size result
  le    %   Linearize into row array
  G45>  %   Array of same size as the input that contains 1 for numbers, 0 for '-'
  1e    %   Linearize into row array
  *     %   Multiply element-wise
  5M    %   Push last array again: 1 for numbers, 0 for '-'
  @)    %   Get 0 or 1 value of that array corresponding to current iteration
  *     %   Multiply. This is to give a row of zeros for non-numbers
]       % End. We have all rows of L in the stack
v       % Concatenate all rows into a matrix: L.
tz:     % Duplicate. Range [1,...,K], where K is the number of nonzeros in L
"       % For loop. Repear K times. This loop computes the 0/1 matrix power
  o     %   Convert matrix entries to double
  tY*   %   Duplicate and matrix-multiply
  g     %   Convert to logical values, that is, nonzero values become 1
]       % End. We have matrix M
G48-    % Convert input chars to the corresponding numbers by subtractig 48
X:      % Linearize into column array. This is vector c
*       % Element-wise multiplication with broadcast (implicit repetition)
s       % Sum of each column. Gives a row array
X>      % Maximum of that row array
        % Implicitly display

JavaScript (ES6), 157 Byte

s=>[...o=s].map((n,i)=>o=n<'.'|(a=[...s]).map(_=>a.map((c,j)=>c>'-'&c<10&(a[j+1]|a[j-1]|a[j+l]|a[j-l])>90?a[n-=-c,j]=99:0),a[i]=99)|o>n?o:n,l=~s.search`
`)|o

Erläuterung

Nimmt ein Eingabefeld als String. Summiert für jede Zahl im Feld alle Zahlen im Bereich. Dazu wird jede Zahl im Feld mehrmals durchlaufen und die Zahl zur Punktzahl hinzugefügt, wenn eine benachbarte Zelle eine zuvor gezählte Zahl enthält. Zählzahlen, die Teil des Bereichs sind, werden dargestellt, indem sie auf 99 gesetzt werden, damit sie nicht erneut gezählt werden. Gibt die höchste Punktzahl als Zahl aus.

var solution =

s=>
  [...o=s].map((n,i)=>o=n<'.'|             // for each number on the field
                                           // n = area score
      (a=[...s])                           // a = array of each field character
      .map(_=>                             // loop to ensure whole area is found
        a.map((c,j)=>                      // for each cell c at index j
          c>'-'&c<10&                      // if the current cell is a number
          (a[j+1]|a[j-1]|a[j+l]|a[j-l])>90 // and an adjacent cells is in the area
          ?a[n-=-c,j]=99:0                 // add the cell to the area
        ),                                 // and the number to the score
        a[i]=99                            // mark the starting cell as counted
      )
      |o>n?o:n,                            // o = output (max of o and n)
    l=~s.search`
`                                          // l = line length of field
  )
  |o                                       // return o

<textarea id="input" rows="6" cols="40">12-45-
4-65-9
87-654
12-487
45----
684764</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>

Pyth, 93 Bytes

A,hlh.zjJ\-.zKsm?qdJd\#HD'b=KXKbJR+i@HbTsm?&&gd0<dlKq@Kd\#'d0[tbhb-bG+bG;Wh=NxK\#=+Y'N)h.MZY

Probieren Sie es online!

Wie es funktioniert

Erster Schritt: Lesen Sie die Eingabe

A,hlh.zjJ\-.zKsm?qdJd\#H
A,                           Assign the following to G and H:
  hlh.z                          G = increment(length(first(all_input())))
       jJ\-.z                    H = join(J="-",all_input())
                m       H    for d in H:
                 ?qdJ            if equal(d,J):
                     d               add d to the list
                                 else:
                      \#             add "#" to the list
                             end
               s             sum the list
              K              assign to K

Sample input:
11-011123
111-010--
0010---01
111-01234

G = 10
H = "11-011123-111-010---0010---01-111-01234" (note the extra dashes connecting each line)
J = "-"
K = "##-######-###-###---####---##-###-#####"

Zweiter Schritt: Definieren Sie eine Funktion, um einen Bereich auszuwerten

D'b=KXKbJR+i@HbTsm?&&gd0<dlKq@Kd\#'d0[tbhb-bG+bG;
D'b                                             ;  def quote(b):
   =KXKbJ                                              K[b] = J
         R+                                            return the sum of A and B, where:
           i@HbT                                         A = to_integer(H[b],10)

                 m                   [tbhb-bG+bG         for d in {dec(b), inc(b), minus(b,G), add(b,G)}:
                  ?&&                                      if .... and ........ and ............... :
                     gd0                                      d>=0
                        <dlK                                           d<len(K)
                            q@Kd\#                                                  equal(K[d],"#")
                                  'd                           add quote(d) to temp_list
                                                           else:
                                    0                          add 0 to temp_list
                s                                        B = sum(temp_list)

Basically, this function (quote) is given a starting
point (b), and then recursively find its neighbour and
add their values to the output.

Dritter Schritt: Lesen Sie alle Bereiche und finden Sie das erforderliche Maximum

Wh=NxK\#=+Y'N)h.MZY
Wh=NxK\#     )         while inc(N=find(K,"#")):   --while K still has "#"
        =+Y'N              Y+= quote(N)
               .MZY    find the maximum of Y,
              h        then print the first.