Ustal, czy siatka zawiera inną siatkę

10

Wyzwanie
Utwórz funkcję przyjmuje dwie dwuwymiarowe tablice Znaków (lub Ciągów, jeśli język programowania nie ma znaków jako typu danych) jako danych wejściowych: a i b. Jeśli twój język nie obsługuje tych danych wejściowych, możesz użyć innej standardowej zmiennej jednobajtowej.

Twoim zadaniem jest ustalenie, czy b zawiera a. Jeśli tak jest, zwróć wartość true. W przeciwnym razie zwróć false.

Przykładowe przypadki testowe

a:

123
456
789

b:

123
456
789

powinien zwrócić true.

a:

code
golf

b:

thisis
code!!
golf!!
ohyeah

powinien zwrócić true.

a:

abcd
efgh
ijkl

b:

abcdef
ghijkl
mnopqr

powinien zwrócić wartość false.

a:

abc
def

b:

1abc2
3def4
5ghi6

powinien zwrócić true

a:

ab
cd

b:

#ab##
##cd#

powinien zwrócić wartość false

Najmniej bajtów wygrywa.

Zaryzykować
źródło
2
Witaj w codegolf! Zredagowałem twoje przypadki testowe, aby (mam nadzieję) uczynić je nieco bardziej przejrzystymi. Pamiętaj, że mamy piaskownicę do pracy nad wyzwaniami przed opublikowaniem ich na main. Powodzenia!
FryAmTheEggman
2
Czy mogę również wziąć pierwszą tablicę jako tablicę ciągów, a drugą jako ciąg oddzielony znakami nowej linii, mimo że mój język (C #) ma wbudowany typ znaków?
Wcielenie nieznajomości
@Neil Przypadki testowe 2 i 3 nie są kwadratowe.
Robin Ryder
5
Czy możesz dodać prawdziwy przypadek testowy, w którym anie bma lewej krawędzi, oraz przypadek testowy falsey, w którym każda linia apojawia się w kolejnych liniach, bale z lewą krawędzią przesuniętą naprzemiennie?
Kudłaty
@EmbodimentofIgnorance tak
Hazard

Odpowiedzi:

9

Brachylog (v2), 4 bajty

s\s\

Wypróbuj online!

Najłatwiej uruchomić w pełnym programie, jak zwykle o , z określony jako argument wiersza polecenia, b na standardowe wejście. Pytanie pyta o funkcję, a program działa również jako funkcja, b po lewej, a po prawej, a wyjście generuje wyjątek wtedy i tylko wtedy, gdy decyzja jest fałszywa .

Wyjaśnienie

s\s\
s     a substring of rows of {the left input}
 \…\  assert rectangular; swap row and column operations
  s   a substring of <s>rows</s> columns of {the above matrix}
      {implicit} assert that the result can be {the right input}

„Twierdzenie prostokątne” jest oczywiście bezcelowe, ponieważ pytanie to już gwarantuje. Reszta programu wykonuje dla nas wyszukiwanie siatki, identyfikując podłańcuch wierszy i kolumn, tj. Submatrix.

Meta-dyskusja

Wcześniej mieliśmy bardzo podobne pytanie ; Spodziewałbym się, że większość odpowiedzi na jedno pytanie można zmienić na odpowiedzi na drugie. Myślę jednak, że jest to bardziej przyjemna wersja.

ais523
źródło
Najkrótsza odpowiedź tutaj, więc ją zaakceptuję.
Hazard
7

Python 2 , 67 bajtów

f=lambda a,b,r=4:b*r and f(a,b[1:],r)|f(a,zip(*b)[::-1],r-1)or a==b

Wypróbuj online!

Pobiera dane wejściowe jako listy krotek znaków.

Próbuje wszystkich podsiatek bi sprawdza, czy ajest wśród nich. Podsiatki są generowane przez rekurencyjne rozgałęzienie podczas usuwania pierwszego rzędu blub obracania go o 90 stopni. Po dokładnie czterech obrotach sprawdza, czy przycięty w dół bjest równy a.

xnor
źródło
1
@mazzy Myślę, że siatki wejściowe powinny być prostokątami.
xnor
5

J , 21 15 8 7 bajtów

1#.,@E.

Wypróbuj online!

-7 bajtów dzięki Bolce Bussiere

oryginalna odpowiedź

J , 21 15 bajtów

<@[e.&,$@[<;.3]

Wypróbuj online!

-6 bajtów dzięki FrownyFrog

w jaki sposób

  • <@[ zapakowany lewy arg
  • $@[<;.3] wszystkie prostokąty w prawym arg o tym samym kształcie co lewy arg
  • teraz przekaż je jako lewy i prawy argument do ...
  • lewy arg jest wiązem prawego arg, po spłaszczeniu obu e.&,
Jonasz
źródło
Myślę, że to może być<@[e.&,$@[<;.3]
FrownyFrog
Ach, oczywiście! Jeśli chcesz wyzwań, spójrz na tę potworność, którą splamiłem stroną
Jonah
1
-7 bajtów: +/@:,@E.. E. jest właściwie stworzony do tego wyzwania.
Bolce Bussiere
tyvm @BolceBussiere. zaktualizuję to dziś wieczorem.
Jonasz
4

Węgiel drzewny , 26 bajtów

⌈⭆η⭆ι⁼θE✂ηκ⁺Lθκ¹✂νμ⁺L§θ⁰μ¹

Wypróbuj online! Link jest do pełnej wersji kodu. Mocno oparty na mojej odpowiedzi na Count ciągłych podmacierzy , jedyną różnicą jest to, że zamiast brać sumę dopasowań, biorę maksimum, a ze względu na niejawną konwersję łańcucha ze względu na użycie wyniku jest już ciąg, który zapisuje bajt.

Neil
źródło
4

05AB1E , 10 bajtów

øŒεøŒI.å}à

Pobiera bjako pierwsze wejście, ajako drugie. Oba dane wejściowe jako macierze znaków.

Port odpowiedzi 05AB1E @ Mr.Xcodera na to pokrewne wyzwanie , więc go oceń!

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

øŒ          # Get the sublists of every column of the (implicit) input `b`
  ε         # Map each list of sublists to:
   øŒ       #  Get the sublists of every column again
            #  (now we have all sub-matrices of `b`)
     I    #  Check if the second input `a` is in this list of sub-matrices
          # After the map: check if any are truthy by taking the maximum
            # (which is output implicitly as result)
Kevin Cruijssen
źródło
3

Python 2 , 106 118 113 bajtów

lambda a,b,L=len:any(sum(A==B[j:j+L(A)]for A,B in zip(a,b[i:]))==L(a)for i in range(L(b))for j in range(L(b[0])))

Wypróbuj online!

Chas Brown
źródło
@ Neil: Naprawiono teraz.
Chas Brown
3

JavaScript (ES6) , 131 112 105 bajtów

105 bajtów:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&x.some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(l,j)==2*j)))

Wypróbuj online!

Zmiany:

  • m[i]na xi n[z]na l: Całkowicie zapomniałem, że te zmienne zostały już zaimplementowane
  • &&na &: obie strony operatora są już logiczne, więc operator bitowy będzie działał

112 bajtów:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].some((c,j)=>n.every((l,z)=>(m[i+z]+'').indexOf(n[z],j)==2*j)))

Wypróbuj online!

Zmiany:

  • map((c,j)=>{...}).some(s=>s)w some((c,j)=>{...}): Redundancja
  • m[i+z].join()into m[i+z]+'': krótszy sposób na konwersję tablicy na ciąg
  • indexOf(n[z].join(),j)w indexOf(n[z],j): The indexOf metody już konwertuje n[z] na sznurku

131 bajtów:

f=(m,n)=>m.some((x,i)=>i<=m.length-n.length&&m[i].map((c,j)=>n.every((l,z)=>m[i+z].join().indexOf(n[z].join(),j)==2*j)).some(s=>s))

Wypróbuj online!

Czytelny:

function f (m, n) {
  return m.some((x, i) => {
    return i <= m.length - n.length
      && m[i].map((c, j) => {
        return n.every((l, z) => {
          return m[i + z].join().indexOf(n[z].join(), j) == 2 * j
        })
      })
        .some(s => s)
  })
}

Zamiast porównywać poszczególne wartości, sprawdziłem, czy linie z siatki N są zawarte w liniach siatki M, a jeśli tak, to przy jakich indeksach. Jeśli wszystkie linie są uwzględnione, zaczynając od tego samego indeksu, wówczas siatka N jest zawarta w siatce M.

M. Paviza
źródło
2

PowerShell , 71 102 85 98 bajtów

dzięki @Jo King; dodane przypadki testowe.

param($a,$b)!!($a|%{$p=[regex]::Escape($_)
$b|sls $p -a -ca|% m*}|group index|?{"$a"-ceq$_.Group})

Wypróbuj online!

Mniej golfa:

param($a,$b)

$matches = $a|%{
    $pattern = [regex]::Escape($_)
    $b|Select-String $pattern -AllMatches -CaseSensitive|% Matches
}

$relevantGroupsByMatchPosition = $matches|group index|?{
    "$a"-ceq$_.Group  # the '$_.Group' contains matches in source order
                      # -ceq is case sensitivity equation operator
                      # -ceq performs an implicit conversion to the left operand type
}

!!($relevantGroupsByMatchPosition)  # true if the variable is not $null
mazzy
źródło
1

JavaScript, 150 bajtów

f=(a,b)=>{_='length';for(r=i=0;i<=b[_]-a[_];i++)for(j=0;j<=b[0][_]-a[0][_];j++){u=0;a.map((l,y)=>l.map((c,x)=>u=u||b[i+y][j+x]!=c));r=r||!u;}return r}

Wypróbuj online

Johan du Toit
źródło