Gibt es Bergringe?

14

Herausforderung

Bestimmen Sie anhand einer Matrix positiver Ganzzahlen, ob es "Ringe" von Bergen gibt. Die formale Definition für diese Herausforderung lautet: Wenn eine Matrix aus positiven ganzen Zahlen gegeben ist, gibt es eine positive ganze Zahl, nfür die es einen geschlossenen Ring von Zellen in der Matrix gibt, der streng größer ist als nderjenige, bei dem alle im Ring eingeschlossenen Zellen kleiner oder gleich sind zu n.

Nehmen wir ein wahres Beispiel:

3 4 5 3
3 1 2 3
4 2 1 3
4 3 6 5

Wenn wir setzen nauf 2:

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

Wie wir deutlich sehen können, bilden die 1s entlang der Kante einen Ring.

Wir definieren einen Ring als eine geordnete Ansammlung von Zellen, wobei benachbarte Zellen in der Ansammlung ebenfalls benachbart sind (Kante oder Ecke). Darüber hinaus muss der Ring mindestens eine Zelle enthalten. Das heißt, der Versuch, die gesamte Matrix mit Ausnahme der Zellen in der Auflistung mit BFS-Flood-Flood zu füllen und niemals eine Zelle in der Auflistung zu durchlaufen, muss mindestens eine Zelle verfehlen.

Wahrheitstestfälle

4 7 6 5 8 -> 1 1 1 1 1
6 2 3 1 5 -> 1 0 0 0 1 (n = 3)
6 3 2 1 5 -> 1 0 0 0 1
7 5 7 8 6 -> 1 1 1 1 1

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

1 3 1
3 1 3
1 3 1

7 5 8 7 5 7 8 -> if you have n = 4, you get an interesting ridge shape around the top and right of the grid
8 4 4 2 4 2 7
6 1 8 8 7 2 7
5 4 7 2 5 3 5
5 6 5 1 6 4 5
3 2 3 2 7 4 8
4 4 6 7 7 2 5
3 2 8 2 2 2 8
2 4 8 8 6 8 8

5 7 6 8 6 8 7 -> there is an island in the outer ring (n = 4), but the island is a ring
5 3 2 4 2 4 7
6 3 7 8 5 1 5
8 2 5 2 8 2 7
8 3 8 8 8 4 7
6 1 4 1 1 2 8
5 5 5 5 7 8 7

150 170 150
170 160 170
150 170 150

Falsche Testfälle

1 2 3 2 1 -> this is just a single mountain if you picture it graphcially
2 3 4 3 2
3 4 5 4 3
2 3 4 3 2
1 2 3 2 1

4 5 4 3 2 -> this is an off-centered mountain
5 6 5 4 3
4 5 4 3 2
3 4 3 2 1

1 1 1 1 1 -> this is four mountains, but they don't join together to form a ring
1 2 1 2 1
1 1 1 1 1
1 2 1 2 1
1 1 1 1 1

3 3 3 3 3 -> there is a ring formed by the `3`s, but the `4` in the middle is taller so it doesn't qualify as a mountain ring
3 1 1 1 3
3 1 4 1 3
3 1 1 1 3
3 3 3 3 3

3 4 4 4 3
4 4 3 4 4
3 3 3 3 4
4 4 3 4 4
3 4 4 4 3

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
22 23 24 25 26

Regeln

  • Es gelten Standardlücken
  • Dies ist , daher wird die kürzeste Antwort in Bytes in jeder Sprache zum Gewinner ihrer Sprache erklärt. Es werden keine Antworten akzeptiert.
  • Die Eingabe kann als jede vernünftige Form für eine Matrix positiver Ganzzahlen angesehen werden
  • Die Ausgabe kann als zwei sinnvolle, konsistente, unterschiedliche Werte angegeben werden, die [wahr] oder [falsch] angeben.
HyperNeutrino
quelle
Für was nist der dritte "wahrheitsgemäße" Testfall eigentlich wahrheitsgemäß? [1,2] ?
Erik der Outgolfer
@EriktheOutgolfer Die Dreierringe grenzen aneinander. Also ja.
user202729

Antworten:

3

Jelly , 38 Bytes

Ẇ€Z$⁺Ẏµ,ZẈ>2ẠµƇµḊṖZƊ⁺FṀ<,Z.ịḊṖ$€Ɗ€ƊȦ)Ṁ

Probieren Sie es online!

Gibt 1 aus, wenn die Matrix Gebirgszüge enthält, andernfalls 0 .

Wie es funktioniert (etwas veraltet)

Möglicherweise kann ich den Code etwas kürzen, sodass dieser Abschnitt wahrscheinlich einer intensiven Bearbeitung unterzogen wird.

Der Hilfslink

,Z.ịḊṖ$€Ɗ€ – Helper link. Let S be the input matrix.
,Z         – Pair S with its transpose.
        Ɗ€ – For each matrix (S and Sᵀ), Apply the previous 3 links as a monad.
  .ị       – Element at index 0.5; In Jelly, the ị atom returns the elements at
             indices floor(x) and ceil(x) for non-integer x, and therefore this
             returns the 0th and 1st elements. As Jelly is 1-indexed, this is the
             same as retrieving the first and last elements in a list.
    ḊṖ$€   – And for each list, remove the first and last elements.

Zum Beispiel mit einer Matrix in der Form:

A(1,1) A(1,2) A(1,3) ... A(1,n)
A(2,1) A(2,2) A(2,3) ... A(2,n)
A(3,1) A(3,2) A(3,3) ... A(3,n)
...
A(m,1) A(m,2) A(m,3) ... A(m,n)

Dies gibt die Arrays zurück (die Reihenfolge spielt keine Rolle):

A(1,2), A(1,3), ..., A(1,n-1)
A(m,2), A(m,3), ..., A(m,n-1)
A(2,1), A(3,1), ..., A(m-1,1)
A(2,n), A(3,n), ..., A(m-1,n)

Kurz gesagt, dies erzeugt die äußersten Zeilen und Spalten, wobei die Ecken entfernt werden.

Der Hauptlink

Ẇ€Z$⁺Ẏµ,ZẈ>2ẠµƇµḊṖZƊ⁺FṀ<ÇȦ)Ṁ – Main link. Let M be the input matrix.
Ẇ€                           – For each row of M, get all its sublists.
  Z$                         – Transpose and group into a single link with the above.
    ⁺                        – Do twice. So far, we have all contiguous sub-matrices.
     Ẏ                       – Flatten by 1 level.
      µ      µƇ              – Filter-keep those that are at least 3 by 3:
       ,Z                      – Pair each sub-matrix S with Sᵀ.
         Ẉ                     – Get the length of each (no. rows, no. columns).
          >2                   – Element-wise, check if it's greater than 2.
            Ạ                  – All.
               µ          )  – Map over each sub-matrix S that's at least 3 by 3
                ḊṖ           – Remove the first and last elements.
                  ZƊ         – Zip and group the last 3 atoms as a single monad.
                    ⁺        – Do twice (generates the inner cells).
                     FṀ      – Flatten, and get the maximum.
                       <Ç    – Element-wise, check if the results of the helper
                               link are greater than those in this list.
                         Ȧ   – Any and all. 0 if it is empty, or contains a falsey
                               value when flattened, else 1.
                           Ṁ – Maximum.
Mr. Xcoder
quelle
2

Sauber , 224 ... 161 Bytes

import StdEnv,StdLib
p=prod
~ =map
^ =reverse o$
@ =transpose o~(^o^)
$l=:[h:t]|h>1=l=[1: $t]
$e=e
?m=p[p(~p(limit(iterate(@o@)(~(~(\a|a>b=2=0))m))))\\n<-m,b<-n]

Probieren Sie es online!

Definiert die Funktion ? :: [[Int]] -> Int, die zurückgibt, 0wenn ein Ring vorhanden ist, und 1ansonsten.

Verwandeln Sie die Matrix in 2s für Berge und 0s für Täler und fluten Sie sie dann mit 1s ein, bis sich das Ergebnis nicht mehr ändert. Wenn 0es für eine Berghöhe noch welche gibt, ist das Produkt 0.

Οurous
quelle
1

JavaScript (Node.js) , 302 Byte

a=>a.some((b,i)=>b.some((n,j)=>(Q=(W=(i,j,f)=>[a.map((b,I)=>b.map((t,J)=>I==i&J==j)),...a+0].reduce(A=>A.map((b,I)=>b.map((t,J)=>f(I)(J)&&(A[I-1]||b)[J]|(A[I+1]||b)[J]|b[J-1]|b[J+1]|t))))(i,j,I=>J=>a[I][J]<=n)).some((b,i)=>b.some((d,j)=>d&&!i|!j|!Q[i+1]|b[j+1]==b.b))<!/0/.test(W(0,0,I=>J=>!Q[I][J]))))

Probieren Sie es online!

Überprüft, ob der Fluss von einem Punkt aus die Grenze nicht erreichen kann, während die Grenze zu jedem Punkt laufen kann

l4m2
quelle