Die hungrige Maus

85

16 Käsestapel werden auf ein 4x4-Quadrat gelegt. Sie sind von bis beschriftet . Der kleinste Stapel ist 1 und der größte ist 16 .116116

Die hungrige Maus ist so hungrig, dass sie immer direkt zum größten Stapel (dh 16 ) geht und ihn sofort isst.

Danach geht es zum größten Nachbarhaufen und frisst diesen schnell auf. (Ja ... es ist wirklich hungrig.) Und so weiter, bis es keinen Nachbarhaufen mehr gibt.

Ein Stapel kann bis zu 8 Nachbarn haben (horizontal, vertikal und diagonal). Es gibt kein Umwickeln.

Beispiel

Wir beginnen mit folgenden Käsestapeln:

37105681213159114141162

Die hungrige Maus frisst zuerst 16 und dann ihren größten Nachbarstapel, nämlich 11 .

37105681213159🐭41412

Die nächsten Züge sind , , , , , , , , und in genau dieser Reihenfolge.131210815149673

🐭5412

Es gibt keinen Käse mehr um die hungrige Maus, also hört es dort auf.

Die Herausforderung

In Anbetracht der anfänglichen Käsekonfiguration muss Ihr Code die Summe der verbleibenden Stapel drucken oder zurückgeben, sobald die hungrige Maus aufgehört hat, sie zu essen.

Für das obige Beispiel lautet die erwartete Antwort .12

Regeln

  • Da die Größe der Eingabematrix fest ist, können Sie sie entweder als 2D-Array oder als eindimensionales Array annehmen.
  • Jeder Wert von bis wird garantiert genau einmal angezeigt.116
  • Das ist .

Testfälle

[ [ 4,  3,  2,  1], [ 5,  6,  7,  8], [12, 11, 10,  9], [13, 14, 15, 16] ] --> 0
[ [ 8,  1,  9, 14], [11,  6,  5, 16], [13, 15,  2,  7], [10,  3, 12,  4] ] --> 0
[ [ 1,  2,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12], [13, 14, 15, 16] ] --> 1
[ [10, 15, 14, 11], [ 9,  3,  1,  7], [13,  5, 12,  6], [ 2,  8,  4, 16] ] --> 3
[ [ 3,  7, 10,  5], [ 6,  8, 12, 13], [15,  9, 11,  4], [14,  1, 16,  2] ] --> 12
[ [ 8,  9,  3,  6], [13, 11,  7, 15], [12, 10, 16,  2], [ 4, 14,  1,  5] ] --> 34
[ [ 8, 11, 12,  9], [14,  5, 10, 16], [ 7,  3,  1,  6], [13,  4,  2, 15] ] --> 51
[ [13, 14,  1,  2], [16, 15,  3,  4], [ 5,  6,  7,  8], [ 9, 10, 11, 12] ] --> 78
[ [ 9, 10, 11, 12], [ 1,  2,  4, 13], [ 7,  8,  5, 14], [ 3, 16,  6, 15] ] --> 102
[ [ 9, 10, 11, 12], [ 1,  2,  7, 13], [ 6, 16,  4, 14], [ 3,  8,  5, 15] ] --> 103
Arnauld
quelle
32
+1 für diesen
Luis Mendo
2
... mach das 103:[[9, 10, 11, 12], [1, 2, 7, 13], [6, 16, 4, 14], [3, 8, 5, 15]]
Jonathan Allan
9
Was für eine schön geschriebene Herausforderung! Ich werde es für die besten Nominierungen im Hinterkopf behalten.
20.
9
Nachdem ich falsch gelesen hatte, war ich ein wenig traurig, dass dies kein hungriger Elch war.
Akozi
1
Diese Herausforderung erinnert mich an die Maus im Labyrinthprogramm für den TXO-Computer. Dieses Spiel wurde bereits in den 1950er Jahren geschrieben und der Legende nach war der txo der erste transistorisierte Computer der Welt. Ja, ob Sie es glauben oder nicht, jemand hat zu Zeiten Ihres Großvaters Videospiele geschrieben.
Walter Mitty

Antworten:

11

Python 2 , 133 130 Bytes

a=input();m=16
for i in range(m):a[i*5:i*5]=0,
while m:i=a.index(m);a[i]=0;m=max(a[i+x]for x in[-6,-5,-4,-1,1,4,5,6])
print sum(a)

Probieren Sie es online!

Nimmt eine abgeflachte Liste von 16 Elementen auf.

Wie es funktioniert

a=input();m=16

# Add zero padding on each row, and enough zeroes at the end to avoid index error
for i in range(m):a[i*5:i*5]=0,

# m == maximum element found in last iteration
# i == index of last eaten element
# eaten elements of `a` are reset to 0
while m:i=a.index(m);a[i]=0;m=max(a[i+x]for x in[-6,-5,-4,-1,1,4,5,6])
print sum(a)
Bubbler
quelle
Der Ausdruck a[i+x]for x in[-6,-5,-4,-1,1,4,5,6]für benachbarte Zellen kann auf abgekürzt werden a[i+j+j/3*2-6]for j in range(9)(der Null-Eintrag ist harmlos). Python 3 kann sicher kürzer sein, wenn ein Längen-8-Bytestring hartcodiert wird, aber Python 2 ist möglicherweise insgesamt noch besser.
20.
1
Obwohl Ihre Zero - Padding Schleife clever ist, sieht es aus wie es kürzer ist eine 2D - Liste zu nehmen: a=[0]*5 for r in input():a=r+[0]+a. Vielleicht gibt es eine noch kürzere Lösung für das Aufteilen von Strings, die keine Iteration erfordert.
20.
8

Python 2 , 111 Bytes

i=x=a=input()
while x:x,i=max((y,j)for j,y in enumerate(a)if i>[]or 2>i/4-j/4>-2<i%4-j%4<2);a[i]=0
print sum(a)

Probieren Sie es online!

An Bubbler angepasste Methoden- und Testfälle . Nimmt eine flache Liste auf STDIN.

Der Code prüft, ob zwei flache Indizes sich berühren iund jstellt die sich berührenden Zellen dar, indem überprüft wird, ob sowohl Zeilenunterschiede i/4-j/4als auch Spaltendifferenzen i%4-j%4streng zwischen -2 und 2 liegen. Beim ersten Durchgang wird diese Prüfung automatisch erfolgreich durchgeführt, sodass der größte Eintrag unabhängig von der Nachbarschaft gefunden wird.

xnor
quelle
8

MATL , 50 49 47 Bytes

16:HZ^!"2G@m1ZIm~]v16eXK68E16b"Ky0)Y)fyX-X>h]s-

Die Eingabe ist eine Matrix, die ;als Zeilentrennzeichen verwendet wird.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

16:HZ^!  % Cartesian power of [1 2 ... 16] with exponent 2, transpose. Gives a 
         % 2-row matrix with 1st column [1; 1], 2nd [1; 2], ..., last [16; 16] 
"        % For each column, say [k; j]
  2      %   Push 2
  G@m    %   Push input matrix, then current column [k; j], then check membership.
         %   This gives a 4×4 matrix that contains 1 for entries of the input that
         %   contain k or j 
  1ZI    %   Connected components (based on 8-neighbourhood) of nonzero entries.
         %   This gives a 4×4 matrix with each connected component labeled with
         %   values 1, 2, ... respectively
  m~     %   True if 2 is not present in this matrix. That means there is only
         %   one connected component; that is, k and j are neighbours in the
         %   input matrix, or k=j
]        % End
v16e     % The stack now has 256 values. Concatenate them into a vector and
         % reshape as a 16×16 matrix. This matrix describes neighbourhood: entry 
         % (k,j) is 1 if values k and j are neighbours in the input or if k=j
XK       % Copy into clipboard K
68E      % Push 68 times 2, that is, 136, which is 1+2+...+16
16       % Push 16. This is the initial value eaten by the mouse. New values will
         % be appended to create a vector of eaten values
b        % Bubble up the 16×16 matrix to the top of the stack
"        % For each column. This just executes the loop 16 times
  K      %   Push neighbourhood matrix from clipboard K
  y      %   Copy from below: pushes a copy of the vector of eaten values
  0)     %   Get last value. This is the most recent eaten value
  Y)     %   Get that row of the neighbourhood matrix
  f      %   Indices of nonzeros. This gives a vector of neighbours of the last
         %   eaten value
  y      %   Copy from below: pushes a copy of the vector of eaten values
  X-     %   Set difference (may give an empty result)
  X>     %   Maximum value. This is the new eaten value (maximum neighbour not
         %   already eaten). May be empty, if all neighbours are already eaten
  h      %   Concatenate to vector of eaten values
]        % End
s        % Sum of vector of all eaten values
-        % Subtract from 136. Implicitly display
Luis Mendo
quelle
Idk MatLab, aber können Sie ein wenig sparen, wenn Sie -136 anstelle von +136 drücken?
Titus
@ Titus Hm, ich verstehe nicht, wie
Luis Mendo
oder andersherum: ich dachte statt 1) ​​Drücke 136 2) Drücke jeden gegessenen Wert 3) Summiere gegessene Werte 4) Subtrahiere von 136 -> 1) Drücke 136 2) Drücke negativ von gegessenem Wert 3) Summiere Stapel. Aber da es offensichtlich nur ein Byte ist; Es ist wahrscheinlich kein Gewinn.
Titus
@Titus Ah, ja, ich denke das braucht die gleiche Anzahl von Bytes. Außerdem benötige ich jeden verzehrten Wert (nicht den negativen) für die eingestellte Differenz. die Verneinung müsste am Ende erfolgen
Luis Mendo
6

PHP, 177 174 171 Bytes

for($v=16;$v;$u+=$v=max($p%4-1?max($a[$p-5],$a[$p-1],$a[$p+3]):0,$a[$p-4],$a[$p+4],$p%4?max($a[$p-3],$a[$p+1],$a[$p+5]):0))$a[$p=array_search($v,$a=&$argv)]=0;echo 120-$u;

Führen Sie mit -nr, geben Sie Matrixelemente als Argumente an oder probieren Sie es online aus .

Titus
quelle
5

JavaScript, 122 Byte

Ich habe mehr als ein paar falsche Kurven gefahren und jetzt habe ich keine Zeit mehr für weiteres Golfen, aber es funktioniert zumindest. Werde morgen wiederkommen (oder, wenn ich mich kenne, heute Abend im Zug nach Hause!), Wenn ich eine Minute finde.

a=>(g=n=>n?g([-6,-5,-4,-1,1,4,5,6].map(x=>n=a[x+=i]>n?a[x]:n,a[i=a.indexOf(n)]=n=0)|n)-n:120)(16,a=a.flatMap(x=>[...x,0]))

Probieren Sie es online aus

Zottelig
quelle
3
+1 für flatMap(): p
Arnauld
: Ich denke, dies ist das erste Mal, dass ich es zum Golfspielen benutze! Aus Interesse (und um mir ein Ziel zu geben, wenn ich darauf zurückkomme), was war Ihre Punktzahl, als Sie es versuchten?
Shaggy
Habe heute keine Minute Zeit, darauf zurückzukommen. Hoffentlich kann ich dann morgen mit ganz neuen Augen von vorne anfangen.
Shaggy
Ich habe meine Lösung gepostet.
Arnauld
5

R , 128 124 123 112 110 Bytes

function(r){r=rbind(0,cbind(0,r,0),0)
m=r>15
while(r[m]){r[m]=0
m=r==max(r[which(m)+c(7:5,1)%o%-1:1])}
sum(r)}

Probieren Sie es online!

Es erstellt eine 4x4-Matrix (die mir geholfen hat, Dinge zu visualisieren), füllt sie mit Nullen auf, beginnt dann mit 16 und durchsucht die umgebenden "Stapel" nach den nächstgrößeren und so weiter.

Abschließend wird eine Warnung ausgegeben, die jedoch keine Auswirkungen hat und das Ergebnis nicht ändert.

BEARBEITEN: -4 Bytes durch Komprimieren der Initialisierung der Matrix in 1 Zeile.

EDIT: -1 danke an Robert Hacken

EDIT: -13 Bytes, die die Vorschläge von Giuseppe und Robin Ryder kombinieren.

Sumner18
quelle
Sie können ein Byte speichern, r==16für das Sie Änderungen vornehmen r>15.
Robert Hacken
1
117 Bytes - verwandle es in eine Funktion, die eine Matrix nimmt und mache ein Aliasing mit der which.
Giuseppe
2
112 Bytes besser als @ Giuseppes Vorschläge: Sie können mals logische statt als ganze Zahl speichern und müssen daher nur whicheinmal statt zweimal aufrufen .
Robin Ryder
110 Bytes mit @RobinRyders Golf und dem Komprimieren der Nachbarschaftsnachbarschaftsmatrix.
Giuseppe
1
@ Sumner18 X%o%Yist ein Alias ​​für outer(X,Y,'*'). outerist eine der praktischsten Funktionen, da sie als "Broadcast" -Funktion von Octave / MATLAB / MATL mit beliebigen (vektorisierten) Operatoren fungieren kann. Sehen Sie hier ; auch praktisch in seltenen fällen ist kroneckerdie auf dieser seite verlinkte.
Giuseppe
4

Kohle , 47 Bytes

EA⭆ι§αλ≔QθW›θA«≔⌕KAθθJ﹪θ⁴÷θ⁴≔⌈KMθA»≔ΣEKA⌕αιθ⎚Iθ

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

EA⭆ι§αλ

Konvertieren Sie die eingegebenen Zahlen in alphabetische Zeichen (A = 0 .. Q = 16) und drucken Sie sie als 4x4-Raster.

≔Qθ

Beginnen Sie mit dem Essen des Q, dh 16.

W›θA«

Wiederholen, während es etwas zu essen gibt.

≔⌕KAθθ

Finden Sie heraus, wo sich der Stapel befindet. Dies ist eine lineare Ansicht in Hauptreihenfolge.

J﹪θ⁴÷θ⁴

In Koordinaten konvertieren und zu diesem Ort springen.

≔⌈KMθ

Finde den größten benachbarten Stapel.

Iss den aktuellen Haufen.

≔ΣEKA⌕αιθ

Wandle die Stapel zurück in ganze Zahlen und nimm die Summe.

⎚Iθ

Löschen Sie die Zeichenfläche und geben Sie das Ergebnis aus.

Neil
quelle
3

Powershell, 143 141 136 130 122 121 Bytes

$a=,0*5+($args|%{$_+0})
for($n=16;$i=$a.IndexOf($n)){$a[$i]=0
$n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]}$a|%{$s+=$_}
$s

Weniger Golf-Testskript:

$f = {

$a=,0*5+($args|%{$_+0})
for($n=16;$i=$a.IndexOf($n)){
    $a[$i]=0
    $n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]
}
$a|%{$s+=$_}
$s

}

@(
    ,( 0  , ( 4,  3,  2,  1), ( 5,  6,  7,  8), (12, 11, 10,  9), (13, 14, 15, 16) )
    ,( 0  , ( 8,  1,  9, 14), (11,  6,  5, 16), (13, 15,  2,  7), (10,  3, 12,  4) )
    ,( 1  , ( 1,  2,  3,  4), ( 5,  6,  7,  8), ( 9, 10, 11, 12), (13, 14, 15, 16) )
    ,( 3  , (10, 15, 14, 11), ( 9,  3,  1,  7), (13,  5, 12,  6), ( 2,  8,  4, 16) )
    ,( 12 , ( 3,  7, 10,  5), ( 6,  8, 12, 13), (15,  9, 11,  4), (14,  1, 16,  2) )
    ,( 34 , ( 8,  9,  3,  6), (13, 11,  7, 15), (12, 10, 16,  2), ( 4, 14,  1,  5) )
    ,( 51 , ( 8, 11, 12,  9), (14,  5, 10, 16), ( 7,  3,  1,  6), (13,  4,  2, 15) )
    ,( 78 , (13, 14,  1,  2), (16, 15,  3,  4), ( 5,  6,  7,  8), ( 9, 10, 11, 12) )
    ,( 102, ( 9, 10, 11, 12), ( 1,  2,  4, 13), ( 7,  8,  5, 14), ( 3, 16,  6, 15) )
    ,( 103, ( 9, 10, 11, 12), ( 1,  2,  7, 13), ( 6, 16,  4, 14), ( 3,  8,  5, 15) )
) | % {
    $expected, $a = $_
    $result = &$f @a
    "$($result-eq$expected): $result"
}

Ausgabe:

True: 0
True: 0
True: 1
True: 3
True: 12
True: 34
True: 51
True: 78
True: 102
True: 103

Erläuterung:

Erster , fügen obere und untere Grenzen von 0 und ein eindimensionalen Array bilden:

0 0 0 0 0
# # # # 0
# # # # 0
# # # # 0
# # # # 0

     ↓

0 0 0 0 0 # # # # 0 # # # # 0 # # # # 0 # # # # 0

Powershell gibt zurück, $nullwenn Sie versuchen, den Wert hinter dem Ende des Arrays abzurufen.

Zweitens begann die Schleife biggest neighbor pilevon 16 bis zu einem Maximum ungleich Null. Und annullieren Sie es (die hungrige Maus isst es).

for($n=16;$i=$a.IndexOf($n)){
    $a[$i]=0
    $n=(-1,1+-6..-4+4..6|%{$a[$i+$_]}|sort)[-1]
}

Drittens die Summe der verbleibenden Stapel.

mazzy
quelle
3

SAS, 236 219 Bytes

Eingabe auf Lochkarten, eine Zeile pro Raster (durch Leerzeichen getrennt), Ausgabe im Protokoll.

Diese Herausforderung wird durch einige Einschränkungen von Arrays in SAS etwas erschwert:

  • Es gibt keine Möglichkeit, die Zeilen- und Spaltenindizes eines übereinstimmenden Elements aus einem mehrdimensionalen Datenschritt-Array zurückzugeben. Sie müssen das Array als 1-d behandeln und sie dann selbst herausarbeiten.
  • Wenn Sie die Grenzen überschreiten, gibt SAS einen Fehler aus und bricht die Verarbeitung ab, anstatt null / null zurückzugeben.

Aktualisierung:

  • Entfernte infile cards;Anweisung (-13)
  • Platzhalter a:für Array-Definition anstelle von a1-a16(-4) verwendet

Golf gespielt:

data;input a1-a16;array a[4,4]a:;p=16;t=136;do while(p);m=whichn(p,of a:);t=t-p;j=mod(m-1,4)+1;i=ceil(m/4);a[i,j]=0;p=0;do k=max(1,i-1)to min(i+1,4);do l=max(1,j-1)to min(j+1,4);p=max(p,a[k,l]);end;end;end;put t;cards;
    <insert punch cards here>
    ; 

Ungolfed:

data;                /*Produce a dataset using automatic naming*/
input a1-a16;        /*Read 16 variables*/
array a[4,4] a:;     /*Assign to a 4x4 array*/
p=16;                /*Initial pile to look for*/
t=136;               /*Total cheese to decrement*/
do while(p);         /*Stop if there are no piles available with size > 0*/
  m=whichn(p,of a:); /*Find array element containing current pile size*/
  t=t-p;             /*Decrement total cheese*/
  j=mod(m-1,4)+1;    /*Get column number*/
  i=ceil(m/4);       /*Get row number*/
  a[i,j]=0;          /*Eat the current pile*/
                     /*Find the size of the largest adjacent pile*/
  p=0;
  do k=max(1,i-1)to min(i+1,4);
    do l=max(1,j-1)to min(j+1,4);
      p=max(p,a[k,l]);
    end;
  end;
end;
put t;              /*Print total remaining cheese to log*/
                    /*Start of punch card input*/
cards; 
  4  3  2  1  5  6  7  8 12 11 10  9 13 14 15 16 
  8  1  9 14 11  6  5 16 13 15  2  7 10  3 12  4 
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 
 10 15 14 11  9  3  1  7 13  5 12  6  2  8  4 16 
  3  7 10  5  6  8 12 13 15  9 11  4 14  1 16  2 
  8  9  3  6 13 11  7 15 12 10 16  2  4 14  1  5 
  8 11 12  9 14  5 10 16  7  3  1  6 13  4  2 15 
 13 14  1  2 16 15  3  4  5  6  7  8  9 10 11 12 
  9 10 11 12  1  2  4 13  7  8  5 14  3 16  6 15 
  9 10 11 12  1  2  7 13  6 16  4 14  3  8  5 15 
;                    /*End of punch card input*/
                     /*Implicit run;*/
user3490
quelle
1
+1 für die Verwendung von Lochkarten in PPCG :)
GNiklasch
3

Haskell , 163 Bytes

o f=foldl1 f.concat
r=[0..3]
q n=take(min(n+2)3).drop(n-1)
0#m=m
v#m=[o max$q y$q x<$>n|y<-r,x<-r,m!!y!!x==v]!!0#n where n=map(z<$>)m;z w|w==v=0|0<1=w
f=o(+).(16#)

Probieren Sie es online!

Die fFunktion nimmt die Eingabe als eine Liste von 4 Listen mit 4 ganzen Zahlen.

Leicht ungolfed

-- helper to fold over the matrix
o f = foldl1 f . concat

-- range of indices
r = [0 .. 3]

-- slice a list (take the neighborhood of a given coordinate)
-- first we drop everything before the neighborhood and then take the neighborhood itself
q n = take (min (n + 2) 3) . drop (n - 1)

-- a step function
0 # m = m -- if the max value of the previous step is zero, return the map
v # m = 
    -- abuse list comprehension to find the current value in the map
    -- convert the found value to its neighborhood,
    -- then calculate the max cell value in it
    -- and finally take the head of the resulting list
    [ o max (q y (q x<$>n)) | y <- r, x <- r, m!!y!!x == v] !! 0 
       # n -- recurse with our new current value and new map
    where 
        -- a new map with the zero put in place of the value the mouse currently sits on 
        n = map (zero <$>) m
        -- this function returns zero if its argument is equal to v
        -- and original argument value otherwise
        zero w 
            | w == v = 0
            | otherwise = w

-- THE function. first apply the step function to incoming map,
-- then compute sum of its cells
f = o (+) . (16 #)
Max Yekhlakov
quelle
3

JavaScript (ES7), 97 Byte

Übernimmt die Eingabe als abgeflachtes Array.

f=(a,s=p=136,m,d)=>a.map((v,n)=>v<m|(n%4-p%4)**2+(n-p)**2/9>d||(q=n,m=v))|m?f(a,s-m,a[p=q]=0,4):s

Probieren Sie es online!

Kommentiert

f = (                    // f= recursive function taking:
  a,                     // - a[] = flattened input array
  s =                    // - s = sum of cheese piles, initialized to 1 + 2 + .. + 16 = 136
      p = 136,           // - p = position of the mouse, initially outside the board
  m,                     // - m = maximum pile, initially undefined
  d                      // - d = distance threshold, initially undefined
) =>                     // 
  a.map((v, n) =>        // for each pile v at position n in a[]:
    v < m |              //   unless this pile is not better than the current maximum
    (n % 4 - p % 4) ** 2 //   or (n % 4 - p % 4)²
    + (n - p) ** 2 / 9   //      + (n - p)² / 9
    > d ||               //   is greater than the distance threshold:
    (q = n, m = v)       //     update m to v and q to n
  )                      // end of map()
  | m ?                  // if we've found a new pile to eat:
    f(                   //   do a recursive call:
      a,                 //     pass a[] unchanged
      s - m,             //     update s by subtracting the pile we've just eaten
      a[p = q] = 0,      //     clear a[q], update p to q and set m = 0
      4                  //     use d = 4 for all next iterations
    )                    //   end of recursive call
  :                      // else:
    s                    //   stop recursion and return s
Arnauld
quelle
Ja, dem wäre ich nie nahe gekommen!
Shaggy
3

Java 10, 272 248 Bytes

m->{int r=0,c=0,R=4,C,M=1,x,y,X=0,Y=0;for(;R-->0;)for(C=4;C-->0;)if(m[R][C]>15)m[r=R][c=C]=0;for(;M!=0;m[r=X][c=Y]=0)for(M=-1,C=9;C-->0;)try{if((R=m[x=r+C/3-1][y=c+C%3-1])>M){M=R;X=x;Y=y;}}catch(Exception e){}for(var Z:m)for(int z:Z)M+=z;return M;}

Die Zellen werden wie in meiner Antwort für die Herausforderung Alle die einzelnen Acht überprüft .
-24 Bytes dank @ OlivierGrégoire .

Probieren Sie es online aus.

Erläuterung:

m->{                       // Method with integer-matrix parameter and integer return-type
  int r=0,                 //  Row-coordinate for the largest number, starting at 0
      c=0,                 //  Column-coordinate for the largest number, starting at 0
      R=4,C,               //  Row and column indices (later reused as temp integers)
      M=1,                 //  Largest number the mouse just ate, starting at 1
      x,y,X=0,Y=0;         //  Temp integers
  for(;R-->0;)             //  Loop `R` in the range (4, 0]:
    for(C=4;C-->0;)        //   Inner loop `C` in the range (4, 0]:
      if(m[R][C]>15)       //    If the current cell is 16:
        m[r=R][c=C]        //     Set `r,c` to this coordinate
          =0;              //     And empty this cell
  for(;M!=0;               //  Loop as long as the largest number isn't 0:
      ;                    //    After every iteration:
       m[r=X][c=Y]         //     Change the `r,c` coordinates,
         =0)               //     And empty this cell
    for(M=-1,              //   Reset `M` to -1
        C=9;C-->0;)        //   Inner loop `C` in the range (9, 0]:
          try{if((R=       //    Set `R` to:
            m[x=r+C/3-1]   //     If `C` is 0, 1, or 2: Look at the previous row
                           //     Else-if `C` is 6, 7, or 8: Look at the next row
                           //     Else (`C` is 3, 4, or 5): Look at the current row
             [y=c+C%3-1])  //     If `C` is 0, 3, or 6: Look at the previous column
                           //     Else-if `C` is 2, 5, or 8: Look at the next column
                           //     Else (`C` is 1, 4, or 7): Look at the current column
               >M){        //    And if the number in this cell is larger than `M`
                 M=R;      //     Change `M` to this number
                 X=x;Y=y;} //     And change the `X,Y` coordinate to this cell
          }catch(Exception e){}
                           //    Catch and ignore ArrayIndexOutOfBoundsExceptions
                           //    (try-catch saves bytes in comparison to if-checks)
  for(var Z:m)             //  Then loop over all rows of the matrix:
    for(int z:Z)           //   Inner loop over all columns of the matrix:
      M+=z;                //    And sum them all together in `M` (which was 0)
  return M;}               //  Then return this sum as result
Kevin Cruijssen
quelle
könnten Sie nicht int r = c = X = Y = 0, R = 4, M = 1, x, y; ?
Serverfrog
@ Serverfrog Ich fürchte, das ist nicht möglich, wenn die Variablen in Java deklariert werden. Ihr Vorschlag brachte mich auf die Idee, ein Byte zu speichern, indem Sie verwenden int r,c,R=4,M=1,x,y,X,Y;for(r=c=X=Y=0;, also danke. :)
Kevin Cruijssen
1

J 82 Bytes

g=.](]*{:@[~:])]_1}~[:>./]{~((,-)1 5 6 7)+]i.{:
[:+/[:(g^:_)16,~[:,0,~0,0,0,.~0,.]

Probieren Sie es online!

Ich plane dies morgen zum Golfplatz, und vielleicht eine J-ish Lösung ähnlich wie diese schreibe ein , aber ich dachte , ich würde den abgeflachte Ansatz versuchen , da ich das nicht vorher getan hatte.

Jona
quelle
Benötigen Sie wirklich das ganz links ]in g?
Galen Ivanov
1
Danke Galen, du hast recht. Es ist das geringste Problem mit diesem Code :) Ich habe eine viel bessere Lösung, die ich implementieren werde, wenn ich Zeit habe.
Jonah
1

Rot , 277 Bytes

func[a][k: 16 until[t:(index? find load form a k)- 1
p: do rejoin[t / 4 + 1"x"t % 4 + 1]a/(p/1)/(p/2): 0
m: 0 foreach d[-1 0x-1 1x-1 -1x0 1x0 -1x1 0x1 1][j: p + d
if all[j/1 > 0 j/1 < 5 j/2 > 0 j/2 < 5 m < t: a/(j/1)/(j/2)][m: t]]0 = k: m]s: 0
foreach n load form a[s: s + n]s]

Probieren Sie es online!

Die Lösung ist wirklich lang und ich bin nicht zufrieden damit, aber ich habe so viel Zeit damit verbracht, sie für die Arbeit in TIO zu reparieren (anscheinend gibt es viele Unterschiede zwischen der stabilen Win- und Linux-Version von Red), also poste ich sie trotzdem ...

Besser lesbar:

f: func [ a ] [
    k: 16
    until [
        t: (index? find load form a n) - 1
        p: do rejoin [ t / 4 + 1 "x" t % 4 + 1 ]
        a/(p/1)/(p/2): 0
        m: 0
        foreach d [ -1 0x-1 1x-1 -1x0 1x0 -1x1 0x1 1 ] [
            j: p + d
            if all[ j/1 > 0
                    j/1 < 5
                    j/2 > 0
                    j/2 < 5 
                    m < t: a/(j/1)/(j/2)
            ] [ m: t ]
        ]
        0 = k: m
    ]
    s: 0
    foreach n load form a [ s: s + n ]
    s
]
Galen Ivanov
quelle
1

Jelly ,  31 30  29 Bytes

³œiⱮZIỊȦ
⁴ṖŒPŒ!€Ẏ⁴;ⱮṢÇƇṪ
FḟÇS

Da die Methode viel zu langsam ist, um innerhalb von 60s mit der Maus ausgeführt zu werden, 16beginnt sie damit 9und begrenzt ihre Fähigkeit so, dass sie nur 9s oder weniger essen kann. Probieren Sie es online aus! (also hier isst sie 9, 2, 7, 4, 8, 6, 3verlassen 97).

Wie?

³œiⱮZIỊȦ - Link 1, isSatisfactory?: list of integers, possiblePileChoice
³        - (using a left argument of) program's 3rd command line argument (M)
   Ɱ     - map across (possiblePileChoice) with:
 œi      -   first multi-dimensional index of (the item) in (M)
    Z    - transpose the resulting list of [row, column] values
     I   - get the incremental differences
      Ị  - insignificant? (vectorises an abs(v) <= 1 test)
       Ȧ - any and all? (0 if any 0s are present in the flattened result [or if it's empty])

⁴ṖŒPŒ!€Ẏ⁴;ⱮṢÇƇṪ - Link 2, getChosenPileList: list of lists of integers, M
⁴               - literal 16
 Ṗ              - pop -> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
  ŒP            - power-set -> [[],[1],[2],...,[1,2],[1,3],...,[2,3,7],...,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]]
      €         - for each:
    Œ!          -   all permutations
       Ẏ        - tighten (to a single list of all these individual permutations)
        ⁴       - (using a left argument of) literal 16
          Ɱ     - map across it with:
         ;      -   concatenate (put a 16 at the beginning of each one)
           Ṣ    - sort the resulting list of lists
             Ƈ  - filter keep those for which this is truthy:
            Ç   -   call last Link as a monad (i.e. isSatisfactory(possiblePileChoice)
              Ṫ - tail (get the right-most, i.e. the maximal satisfactory one)

FḟÇS - Main Link: list of lists of integers, M
F    - flatten M
  Ç  - call last Link (2) as a monad (i.e. get getChosenPileList(M))
 ḟ   - filter discard (the resulting values) from (the flattened M)
   S - sum
Jonathan Allan
quelle
Ach ja, Power-Set ist nicht genug!
Jonathan Allan
2
@Arnauld - endlich ein bisschen Zeit zum Golfen: D Das sollte funktionieren, ist aber (viel) zu langsam, um mit dem zuvor verwendeten Testfall bei TIO zu laufen.
Jonathan Allan
Könnte der Abwähler bitte ein Feedback geben? Dies funktioniert, hat eine vollständige und klare Erklärung und ist derzeit auch der kürzeste Eintrag.
Jonathan Allan
Ich habe zugestimmt, aber angesichts des O ((n ^ 2)!) Dieser Antwort wünschte ich, die Herausforderung hätte polynomielle Zeit benötigt.
Lirtosiast
1

Nicht meine beste Arbeit. Es müssen einige Verbesserungen vorgenommen werden, von denen einige für den verwendeten Algorithmus von grundlegender Bedeutung sind. Ich bin sicher, dass nur ein verbessert werden kann int[], aber ich konnte nicht herausfinden, wie Nachbarn auf diese Weise effizient aufgezählt werden können. Ich würde gerne eine PowerShell-Lösung sehen, die nur ein eindimensionales Array verwendet!

PowerShell Core , 348 Byte

Function F($o){$t=120;$a=@{-1=,0*4;4=,0*4};0..3|%{$a[$_]=[int[]](-join$o[(3+18*$_)..(3+18*$_+13)]-split',')+,0};$m=16;while($m-gt0){0..3|%{$i=$_;0..3|%{if($a[$i][$_]-eq$m){$r=$i;$c=$_}}};$m=($a[$r-1][$c-1],$a[$r-1][$c],$a[$r-1][$c+1],$a[$r][$c+1],$a[$r][$c-1],$a[$r+1][$c-1],$a[$r+1][$c],$a[$r+1][$c+1]|Measure -Max).Maximum;$t-=$m;$a[$r][$c]=0}$t}

Probieren Sie es online!


Mehr lesbare Version:

Function F($o){
    $t=120;
    $a=@{-1=,0*4;4=,0*4};
    0..3|%{$a[$_]=[int[]](-join$o[(3+18*$_)..(3+18*$_+13)]-split',')+,0};
    $m=16;
    while($m-gt0){
        0..3|%{$i=$_;0..3|%{if($a[$i][$_]-eq$m){$r=$i;$c=$_}}};
        $m=($a[$r-1][$c-1],$a[$r-1][$c],$a[$r-1][$c+1],$a[$r][$c+1],$a[$r][$c-1],$a[$r+1][$c-1],$a[$r+1][$c],$a[$r+1][$c+1]|Measure -Max).Maximum;
        $t-=$m;
        $a[$r][$c]=0
    }
    $t
}
Jeff Freeman
quelle
Oh ja, seltsame Sache, die mir aufgefallen ist, ist, dass der Versuch, das in PSv5 zu tun, (array|sort)[-1]statt Measure -maxzu arbeiten, im Kern falsche Ergebnisse lieferte. Keine Ahnung warum.
Veskah,
Ja, das ist komisch. Ich habe es getestet, (0..10|sort)[-1]aber es gibt 10 auf PSv5 zurück, aber 9 auf PS Core. Dies liegt daran, dass es in lexikografischer Reihenfolge anstatt in numerischer behandelt wird. Schade, dass.
Jeff Freeman
Klassisches Microsoft, das die wichtigen Dinge ändert.
Veskah,
Ich stimme in diesem Fall zu. Ich bin mir nicht sicher, warum PS Core Sort ein Array von int32 in ein Array von Strings wirft. Aber das gerät ins Wanken, also schweife ich ab. Danke für die Umstrukturierung!
Jeff Freeman
1

C (gcc), 250 Bytes

x;y;i;b;R;C;
g(int a[][4],int X,int Y){b=a[Y][X]=0;for(x=-1;x<2;++x)for(y=-1;y<2;++y)if(!(x+X&~3||y+Y&~3||a[y+Y][x+X]<b))b=a[C=Y+y][R=X+x];for(i=x=0;i<16;++i)x+=a[0][i];return b?g(a,R,C):x;}
s(int*a){for(i=0;i<16;++i)if(a[i]==16)return g(a,i%4,i/4);}

Probieren Sie es online!

Hinweis: Diese Übermittlung ändert das Eingabearray.

s()ist die Funktion, die mit einem Argument einer veränderlichen Variable aufgerufen werden soll int[16](das ist dasselbe im Speicher wie ein int[4][4], als das es g()interpretiert wird).

s()Findet die Position von 16im Array und übergibt diese Informationen an. Hierbei ghandelt es sich um eine rekursive Funktion, die eine Position annimmt, die Nummer an dieser Position auf 0 setzt und dann:

  • Wenn sich eine positive Zahl daneben befindet, suchen Sie nach der Position der größten benachbarten Zahl

  • Anderenfalls geben Sie die Summe der Zahlen im Array zurück.

Pizzapants184
quelle
s(int*a){for(i=0;a[i]<16;++i);return g(a,i%4,i/4);}
RiaD
Wenn g die Summe von gegessen zurückgibt, müssen Sie die Summe darin nicht berechnen.
Geben Sie
Kannst du bitweise oder stattdessen wenn logisch oder?
RiaD
211 Bytes
Ceilingcat
1

Add ++ , 281 Bytes

D,f,@@,VBFB]G€=dbLRz€¦*bMd1_4/i1+$4%B]4 4b[$z€¦o
D,g,@@,c2112011022200200BD1€Ω_2$TAVb]8*z€kþbNG€lbM
D,k,@~,z€¦+d4€>¦+$d1€<¦+$@+!*
D,l,@@#,bUV1_$:G1_$:
D,h,@@,{l}A$bUV1_$:$VbU","jG$t0€obU0j","$t€iA$bUpVdbLRG€=€!z€¦*$b]4*$z€¦o
y:?
m:16
t:120
Wm,`x,$f>y>m,`m,$g>x>y,`y,$h>x>y,`t,-m
Ot

Probieren Sie es online!

Dies ist eine komplizierte Angelegenheit.

Überprüfen Sie alle Testfälle

Wie es funktioniert

Für diese Erklärung verwenden wir die Eingabe

M=[37105681213159114141162]

x1x16M4x4

  • f(x,M)4x4xMx=16Mf(x,M)=(4,3)

  • g(M,y)f(x,M)g(M,f(x,M))=11

    Dies implementiert die beiden Hilfsfunktionen:

    k(x)

    l(M,y)

  • h(y,M)0

016120(1+2++14+15)

0

0

  • f(y,m)16Mx:=(4,3)
  • g(x,y)0
  • h(x,y)160
  • tm

Schließlich wird t ausgegeben , dh die verbleibenden, nicht gesammelten Werte.

Caird Coinheringaahing
quelle
1

C # (.NET Core) , 258 Byte

Ohne LINQ. Das using System.Collections.Generic dient zur Formatierung nach - die Funktion benötigt es nicht.

e=>{int a=0,b=0,x=0,y=0,j=0,k;foreach(int p in e){if(p>15){a=x=j/4;b=y=j%4;}j++;}e[x,y]=0;while(1>0){for(j=-1;j<2;j++)for(k=-1;k<2;k++){try{if(e[a+k,b+j]>e[x,y]){x=a+k;y=b+j;}}catch{}}if(e[x,y]<1)break;e[x,y]=0;a=x;b=y;}a=0;foreach(int p in e)a+=p;return a;}

Probieren Sie es online!

Destroigo
quelle
1

Perl 6 , 151 136 126 125 119 Bytes

{my@k=$_;my $a=.grep(16,:k)[0];while @k[$a] {@k[$a]=0;$a=^@k .grep({2>$a+>2-$_+>2&$a%4-$_%4>-2}).max({@k[$_]})};[+] @k}

Super schäbige Lösung. Übernimmt die Eingabe als abgeflachtes Array.

Probieren Sie es online!

bb94
quelle
1

Perl 5 -MList::Util=sum -p , 137 Bytes

splice@F,$_,0,0for 12,8,4;map{$k{++$,}=$_;$n=$,if$_&16}@F;map{map{$n=$_+$"if$k{$"+$_}>$k{$n}&&!/2|3/}-6..6;$k{$"=$n}=0}@F;$_=sum values%k

Probieren Sie es online!

Xcali
quelle
1

K (ngn / k) , 49 Bytes

{{h[,x]:0;*>(+x+0,'1-!3 3)#h}\*>h::(+!4 4)!x;+/h}

Probieren Sie es online!

Die Eingabe ( x) ist ein 1D-Array

(+!4 4)!x ein Wörterbuch, das die Koordinatenpaare den Werten von x

h:: einer globalen Variablen zuweisen h

*> der Schlüssel, der dem Maximalwert entspricht

{ }\ Wiederholen Sie diesen Vorgang bis zur Konvergenz und sammeln Sie die Zwischenwerte in einer Liste

h[,x]:0 Die aktuelle Position auf Null setzen

+x+0,'1-!3 3 Nachbarpositionen

( )#hFiltern Sie sie hals kleineres Wörterbuch

*>Welcher Nachbar hat den Maximalwert? Es wird die aktuelle Position für die neue Iteration

+/hGeben Sie zum Schluss die Summe der hverbleibenden Werte zurück

ngn
quelle
1

Wolfram Language (Mathematica) , 124 115 Bytes

(p=#&@@Position[m=Join@@ArrayPad[#,1],16];Do[m[[p]]=0;p=MaximalBy[#&@@p+{0,-1,1,-5,5,-6,6,-7,7},m[[#]]&],16];Tr@m)&

Probieren Sie es online!

Dies nimmt ein 2D-Array, füllt es auf jeder Seite auf und glättet es dann sofort, damit wir keine Bytes für die Indizierung aufwenden müssen. Die einzigen Kosten hierfür sind Join@@die Abflachung. Danach geht es weiter wie unten.

124-Byte-Version für ein 2D-Array: Probieren Sie es online aus!

Meistens meine eigene Arbeit, mit ein bisschen abgeleitet von der 149-Byte-Antwort von J42161217 .

Ungolfed:

(p = #& @@ Position[m = #~ArrayPad~1,16];     m = input padded with a layer of 0s
                                              p = location of 16
Do[
    m = MapAt[0&,m,p];                        Put a 0 at location p
    p = #& @@ MaximalBy[                      Set p to the member of
        p+#& /@ Tuples[{0,-1,1},2],             {all possible next locations}
        m~Extract~#&],                        that maximizes that element of m,
                                              ties broken by staying at p+{0,0}=p.
16];                                        Do this 16 times.
Tr[Tr/@m]                                   Finally, output the sum of m.
)&
Lirtosiast
quelle