Wohin geht die Schlange?

35

Schreiben Sie eine Funktion (mit möglichst wenigen Bytes), die ein zweidimensionales Array mit einer beliebigen Anzahl von Spalten und Zeilen enthält, in denen:

  • 0 stellt leeren block dar,
  • 1 stellt Schlangenblock dar.

Die Funktion muss die Anzahl der möglichen Pfade zurückgeben, die die Schlange zurückgelegt hat.

Beispiel 1:

Eingang:

[
  [1,1,1,1,1],
  [0,0,0,0,1],
  [0,0,0,0,1],
]

Ausgabe: 2

Im obigen Beispiel wird die Funktion zurückgegeben, 2da die Antwort eine der folgenden ist:

Bildbeschreibung hier eingeben

Beispiel 2:

Eingang:

[
  [1,1,1,1],
  [0,0,1,1],
  [0,0,1,1],
]

Ausgabe: 6

In diesem Beispiel wird die Funktion zurückgegeben, 6da die Antwort eine der folgenden ist:

Bildbeschreibung hier eingeben

Hinweis:

Bei der Bewertung der Eingabe können Sie davon ausgehen, dass:

  • Die Arrays, die Spalten darstellen, haben immer die gleiche Größe (die Arrays sind also rechteckig).
  • Es gibt mindestens einen gültigen Pfad.
  • Die Schlange kann nicht durch die Ränder gehen (wie es in einigen Versionen der Schlange vorkommen kann);
  • Die Schlange wird immer mindestens 2 Blöcke haben;
  • Die Schlange kann sich nicht diagonal bewegen.
  • Die Wege sind gerichtet. (Zwei Pfade, die an unterschiedlichen Positionen enden, aber ansonsten genau gleich aussehen, sind nicht derselbe Pfad. Dies ergibt die Gesamtsumme.)
Adelin
quelle
13
Willkommen bei PPCG! Schöne erste Herausforderung.
Laikoni
5
Kleine Anmerkung: "Es wird immer mindestens eine Zeile und eine Spalte geben" ist überflüssig, da die Schlange immer mindestens 2 Blöcke hat.
Stewie Griffin
2
Vorgeschlagene Testfälle: die von @StewieGriffin und [[0,0,1,1],[0,0,1,1],[0,0,1,1]]. Die meisten Antworten geben 16, aber eine gibt 15.
Kevin Cruijssen
2
Es scheint, dass alle (einschließlich mir) bisher davon ausgegangen sind, dass zwei Pfade, die an verschiedenen Positionen enden, aber ansonsten genau gleich aussehen, nicht der gleiche Pfad sind. Ich denke, das muss explizit spezifiziert werden.
Arnauld
2
@Arnauld - das stimmt. Zwei Pfade, die an unterschiedlichen Positionen enden, aber ansonsten genau gleich aussehen, sind nicht der gleiche Pfad . Dies summiert sich zur Gesamtsumme. In deinem Beispiel sollte die Summe 16 sein, wenn ich mich nicht irre - ich kann jetzt nicht genau rechnen, aber du bekommst den Punkt
Adelin

Antworten:

11

Wolfram Language (Mathematica) , 16 + 83 = 99 Bytes

Bibliotheksimportanweisung (16 Byte):

<<Combinatorica`

Tatsächlicher Funktionskörper (83 Bytes):

Length@HamiltonianCycle[MakeGraph[#~Position~1~Join~{1>0},##||Norm[#-#2]==1&],All]&

Probieren Sie es online!


Beachten Sie, dass in der Frage nur die Anzahl der Hamilton-Pfade in der Grafik abgefragt wird.

Aus irgendeinem Grund HamiltonianPathfunktioniert die Funktion jedoch nicht wirklich mit gerichteten Graphen ( Beispiel ). Daher habe ich die in dieser Mathematica.SE- Frage beschriebene Problemumgehung verwendet :

  • Fügen Sie einen Scheitelpunkt (genannt True) hinzu, der mit allen anderen Scheitelpunkten verbunden ist.
  • Zählen Sie die Anzahl der Hamilton-Zyklen in der resultierenden Grafik.

Der Graph wird MakeGraphmithilfe der Booleschen Funktion erstellt (ärgerlicherweise gibt es keine direkt äquivalente integrierte Funktion) ##||Norm[#-#2]==1&, die Truegenau dann zurückgibt, wenn eines der Argumente Trueoder der Abstand zwischen den beiden Scheitelpunkten vorliegt 1.


Tr[1^x]kann nicht anstelle von verwendet Length@xwerden und <2kann nicht anstelle von verwendet werden ==1.


HamiltonianPathkann verwendet werden, wenn der Graph ungerichtet ist, wobei der Funktionskörper 84 Bytes benötigt (genau 1 Byte mehr als die aktuelle Einreichung):

Length@HamiltonianPath[MakeGraph[#~Position~1,Norm[#-#2]==1&,Type->Undirected],All]&

Probieren Sie es online!

user202729
quelle
10

JavaScript (ES6), 154 134 Byte

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>r&&r[x]&&[-1,0,1,2].map(d=>r[r[x]=0,/1/.test(m)?g(_,x+d%2,y+~-d%2):++n,x]=1)),n=0)|n/4

Probieren Sie es online!

Wie?

Methode

Ausgehend von jeder möglichen Zelle füllen wir die Matrix mit Fluten und löschen alle Zellen auf unserem Weg. Immer dann , wenn die Matrix nicht mehr enthält 1 ‚s, erhöhen wir die Anzahl n der möglichen Pfade.

Jeder gültige Pfad wird aufgrund der in der letzten Zelle gewählten Richtung viermal gezählt, was eigentlich keine Rolle spielt. Daher ist das Endergebnis n / 4 .

Rekursive Funktion

Anstatt die rekursive Funktion g () aus dem Rückruf der zweiten Map () wie folgt aufzurufen ...

m=>m.map((r,y)=>r.map((_,x)=>(g=(x,y,r=m[y])=>...g(x+dx,y+dy)...)(x,y)))

... definieren wir die rekursive Funktion g () direkt als Rückruf von map () :

m=>m.map((r,Y)=>r.map(g=(_,x,y,r=m[y=1/y?y:Y])=>...g(_,x+dx,y+dy)...))

Trotz der ziemlich langen Formel, y=1/y?y:Ydie benötigt wird, um den Anfangswert von y festzulegen, werden insgesamt 2 Bytes gespart.

Kommentierter Code

m =>                           // given the input matrix m[][]
  m.map((r, Y) =>              // for each row r[] at position Y in m[][]:
    r.map(g = (                //   for each entry in r[], use g() taking:
      _,                       //     - the value of the cell (ignored)
      x,                       //     - the x coord. of this cell
      y,                       //     - either the y coord. or an array (1st iteration),
                               //       in which case we'll set y to Y instead
      r = m[y = 1 / y ? y : Y] //     - r = the row we're currently located in
    ) =>                       //       (and update y if necessary)
      r && r[x] &&             //     do nothing if this cell doesn't exist or is 0
      [-1, 0, 1, 2].map(d =>   //     otherwise, for each direction d,
        r[                     //     with -1 = West, 0 = North, 1 = East, 2 = South:
          r[x] = 0,            //       clear the current cell
          /1/.test(m) ?        //       if the matrix still contains at least one '1':
            g(                 //         do a recursive call to g() with:
              _,               //           a dummy first parameter (ignored)
              x + d % 2,       //           the new value of x
              y + ~-d % 2      //           the new value of y
            )                  //         end of recursive call
          :                    //       else (we've found a valid path):
            ++n,               //         increment n
          x                    //       \_ either way,
        ] = 1                  //       /  do r[x] = 1 to restore the current cell to 1
      )                        //     end of map() over directions
    ),                         //   end of map() over the cells of the current row
    n = 0                      //   start with n = 0
  ) | n / 4                    // end of map() over the rows; return n / 4
Arnauld
quelle
10

Jelly , 12 11 Bytes

ŒṪŒ!ạƝ€§ÐṂL

Probieren Sie es online!


Erläuterung.

ŒṪ               Positions of snake blocks.
  Œ!             All permutations.
                 For each permutation:
    ạƝ€             Calculate the absolute difference for each neighbor pair
       §            Vectorized sum.
                 Now we have a list of Manhattan distance between snake
                    blocks. Each one is at least 1.
        ÐṂL      Count the number of minimum values.
                    Because it's guaranteed that there exists a valid snake,
                    the minimum value is [1,1,1,...,1].
user202729
quelle
Neue Funktionen erweisen sich als äußerst nützlich.
user202729
Wie wäre es, §ỊMLanstatt §ỊP€Sein Byte zu speichern - ich denke, es sollte funktionieren?
Jonathan Allan
... oder §ÐṂLwas ist ein bisschen schneller.
Jonathan Allan
@ JonathanAllan Funktioniert nur, wenn das Ergebnis ungleich Null ist.
user202729
@ JonathanAllan Also es endet tatsächlich funktioniert.
user202729
8

Python 2 , 257 246 241 234 233 227 214 210 Bytes

lambda b:sum(g(b,i,j)for j,l in e(b)for i,_ in e(l))
e=enumerate
def g(b,x,y):d=len(b[0])>x>-1<y<len(b);c=eval(`b`);c[d*y][d*x]=0;return d and b[y][x]and('1'not in`c`or sum(g(c,x+a,y)+g(c,x,y+a)for a in(1,-1)))

Probieren Sie es online!


Gerettet

  • -8 Bytes, danke an Kevin Cruijssen
  • -14 Bytes, danke an user202729
TFeld
quelle
1
Die richtige Sprache für den Job?
Neil
5

Python 2, 158 Bytes

E=enumerate
g=lambda P,x,y:sum(g(P-{o},*o)for o in P if x<0 or abs(x-o[0])+abs(y-o[1])<2)+0**len(P)
lambda L:g({(x,y)for y,r in E(L)for x,e in E(r)if e},-1,0)

Probieren Sie es online!

KSab
quelle
3

Haskell , 187.155 Bytes

r=filter
l=length
(a,b)?(x,y)=abs(a-x)+abs(b-y)==1
l#x=sum[p!r(/=p)l|p<-x]
p![]=1
p!l=l#r(p?)l
f x|l<-[(i,j)|i<-[0..l x-1],j<-[0..l(x!!0)-1],x!!i!!j>0]=l#l

Probieren Sie es online!

user28667
quelle