Wzajemnie atakujące królowe

26

Niech szachownica 8x8 będzie reprezentowana przez dowolne dwie różne wartości, przy czym jedna wartość będzie pustym kwadratem, a druga królową. W poniższych przykładach używam 0 jako pustych kwadratów i 1 jako królowych. Na przykład:

Królowe na szachownicy

jest dany przez

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

Rozważ liczbę par królowych, które atakują każdą z nich, co najmniej o jedno pole kwadratowe (dla przypomnienia królowe atakują ortogonalnie i po przekątnej). W powyższym przykładzie poniższy niesamowity brzydki schemat pokazuje wszystkie te pary jako strzałki.

Atakowanie królowych

Znaleziono powyżej 43 par, podając następujący przypadek testowy:

Input:
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1
Output: 43

Wyzwanie

Napisz program, który, biorąc pod uwagę stan planszy reprezentowany przez dwie różne wartości, wypisuje liczbę par królowych, które atakują się nawzajem, z co najmniej jednym kwadratem między nimi.

  • Możesz wpisać w dowolnym dogodnym formacie, który używa dwóch wartości do przedstawienia pustych kwadratów i królowych, np. Ciąg 64 "." Dla pustych kwadratów i "Q" dla królowych według rzędów od dołu do góry, 8x8 macierz booleanów, lista liczb całkowitych 0 i 1 itd., o ile jest to wyjaśnione w twoim rozwiązaniu
  • Dane wyjściowe to liczba całkowita
  • Obowiązują standardowe metody we / wy, a standardowe luki są zabronione
  • To jest kod golfowy, więc wygrywa najkrótsza odpowiedź w bajtach

Przypadki testowe:

W formacie 0 i 1, gdzie 0 to puste kwadraty, a 1 to królowe:

Input:
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 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 0

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 0

Input:
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 0 0 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
Output: 1

Input:
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 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
Output: 10

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 4

Input:
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 11
code-golf  chess  binary-matrix 
— JMigst
źródło
Przed opublikowaniem mojej drugiej wersji powinienem był zapytać: czy 254 dla królowej i 0 dla pustego kwadratu są dopuszczalnymi wartościami wejściowymi?
— Arnauld
@Arnauld Możesz wprowadzać dane w najbardziej dogodnym formacie, który wykorzystuje dwie wartości do przedstawienia pustych kwadratów i królowych. Więc na pewno jest w porządku
— JMigst
Dzięki. Zapytałem, ponieważ uważam, że ta zasada może być zbyt liberalna, jeśli potraktowana dosłownie. Mógłbym poprosić o przekazanie ciągu zawierającego większość kodu JS dla królowych i po prostu ocenić to w programie. (Ale może temu zapobiec domyślna luka. Nie jestem pewien.)
— Arnauld

Odpowiedzi:

14

Python 2 , 105 bajtów

lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

Wypróbuj online!

Wyjaśnienie

Pobieramy dane wejściowe jako ciąg 64 znaków '0'lub '1'. Używając plasterków kroków, rzucamy cztery „linie wzroku” z każdej napotkanej królowej. Na przykład, gdy i = 10 i d = 7 , oznaczenie królowej jako ♥, a płytki wybrane przez b[i+d::d]█:

1 0 1 1 1 0 0 0
1 0 ♥ 0 1 0 1 1
1 █ 1 0 1 1 0 1
█ 1 0 1 0 1 0 █
0 1 1 0 0 1 █ 1
1 0 0 0 1 █ 0 0
0 1 0 0 █ 1 1 1
0 1 1 █ 0 1 0 1

Oczywiście nie chcemy, aby wizja owijała się wokół planszy w ten sposób. Obliczamy więc, jak daleko krawędź planszy jest w każdym kierunku, i oglądamy płytki b[i+d::d][:…].

Dla każdej pary kierunków płytek liczymy:

ray.find('1')*int(c)>0

To się nie powiedzie za każdym razem

  • cnie jest królową; lub
  • królowa, którą ten promień widzi, jest zbyt blisko ( findzwraca 0); lub
  • ten promień nie widzi królowej ( findzwraca -1).

Każda para królowych jest sprawdzana tylko raz, ponieważ promienie są zawsze rzucane do przodu w kolejności czytania, od „wcześniejszej” królowej do „późniejszej”.

— Lynn
źródło
10

JavaScript (ES7), 86 bajtów

Pobiera dane wejściowe jako tablicę 64 liczb całkowitych z 254 dla królowej i 0 dla pustego kwadratu.

a=>[s=0,6,7,8].map(d=>a.map(g=(n,p)=>(p%8-(p+=~d)%8)**2<n%4?a[p]?s+=n&1:g(n/2,p):0))|s

Wypróbuj online!

Ta wersja wykorzystuje niedopełnienie arytmetyczne, aby uzyskać warunek zatrzymania w części rekurencyjnej.

JavaScript (ES7), 89 bajtów

Pobiera dane wejściowe jako tablicę 64 bitów.

a=>[s=0,6,7,8].map(d=>a.map(g=(n,p,x)=>(p%8-(p+=~d)%8)**2>1|p<0?0:a[p]?s+=!x&n:g(n,p)))|s

Wypróbuj online!

W jaki sposób?

Rekurencyjnie wywołujemy nazwaną funkcję zwrotną, map()aby przejść przez kwadraty w danym kierunku. Chociaż tak naprawdę nie potrzebujemy zawartości trzeciego parametru wywołania zwrotnego (tablica map()została wywołana), używamy go jednak pośrednio, aby wiedzieć, czy jest to pierwsza iteracja, czy nie.

arr.map (wywołanie zwrotne funkcji (currentValue [, index [, tablica]])

To jest zmienna x w kodzie.

a =>                        // given the input array a[]
  [ s = 0,                  // initialize the sum s to 0
    6, 7, 8 ].map(d =>      // for each direction d in [0, 6, 7, 8]:
    a.map(g = (n, p, x) =>  //   for each square n at position p in a[]:
      (                     //     we are out of the board if:
        p % 8 -             //       - abs(p % 8 - p' % 8) is greater than 1
        (p += ~d) % 8       //         where p' = p - (d + 1)
      ) ** 2 > 1 |          //         (squaring is shorter than using Math.abs)
      p < 0 ?               //       - or p' is less than 0
        0                   //       if so, stop recursion
      :                     //     else:
        a[p] ?              //       if there's a queen on the target square:
          s +=              //         increment s if:
            !x &            //           x is undefined (this is not the 1st iteration)
            n               //           and n = 1 (there's a queen on the source square)
        :                   //       else:
          g(n, p)           //         do a recursive call to g(), with x undefined
    )                       //   end of inner map()
  ) | s                     // end of outer map(); return s
— Arnauld
źródło
8

Ślimaki , 14 bajtów

A
rdaa7\1\0+\1

Wypróbuj online!

Dane wejściowe mają format 0/1, bez spacji w wierszach.

Ślimaki zostały stworzone z myślą o wyzwaniu PPCG w zakresie projektowania w języku 2D . Co najważniejsze, domyślnie wyświetla liczbę znalezionych dopasowań, co idealnie nadaje się do tego wyzwania.

A ustawia opcję „wszystkie ścieżki”, tak że jeśli królowa jest w wielu parach, każda z tych par wygeneruje dopasowanie.

rdaa7ustawia kierunek dopasowania na S, SE, E i NE. Ustawienie wszystkich kierunków ( z) spowodowałoby podwójne liczenie.

\1\0+\1dopasowuje a 1, następnie jeden lub więcej 0s, a następnie drugi 1.

— TwiNight
źródło
6

APL (Dyalog Classic) , 41 39 32 bajtów

(+/+⌿-⌈⌿)2<⌿0⍪⊢,⍉,8 31⍴⊢,≠⍨,⌽,≠⍨

Wypróbuj online!

≠⍨ jest „nie równy sobie” - macierz zerowa 8x8

⊢,≠⍨,⌽,≠⍨- jeśli oryginalna macierz jest ABC..., to wyrażenie zwraca:

A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0 0
I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0 0 0
Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0 0 0 0
Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0 0 0 0 0
G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0 0 0 0 0 0
O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0 0 0 0 0 0 0
W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0 0 0 0 0 0 0 0
E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E 0 0 0 0 0 0 0 0

8 31⍴ przekształca go z 8x32 na 8x31, ponownie wykorzystując elementy w kolejności rzędów głównych:

A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

⊢,⍉, przygotowuje oryginalną matrycę i jej transpozycję (dodatkowe spacje dla przejrzystości):

A B C D E F G H  A I Q Y G O W E  A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
I J K L M N O P  B J R Z H P X F  0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
Q R S T U V W X  C K S A I Q Y G  0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
Y Z A B C D E F  D L T B J R Z H  0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
G H I J K L M N  E M U C K S A I  0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
O P Q R S T U V  F N V D L T B J  0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
W X Y Z A B C D  G O W E M U C K  0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
E F G H I J K L  H P X F N V D L  0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

2<⌿0⍪dodaje 0 na górze i porównuje użycie <każdego elementu z elementem pod nim, więc otrzymujemy 1 dla wiodącej 1 w każdej pionowej grupie 1, i otrzymujemy 0 wszędzie indziej

+⌿-⌈⌿ sumy według kolumny minus maksima według kolumny - obliczamy liczbę przerw między grupami 1 w każdej kolumnie, 0 jeśli nie ma

+/ suma

— ngn
źródło
3

Retina 0.8.2 , 60 58 bajtów

1
¶1$';___¶
_
$n$%`7$*_
(.)(?=.*;(_)*)(?<-2>.)*
$1
m`^10+1

Wypróbuj online! Pobiera dane wejściowe jako 8-znakowe ciągi binarne rozdzielone przecinkami, ale nagłówek konwertuje podany format. Wyjaśnienie:

1
¶1$';___¶

Stwórz wszystkie podłazy planszy, zaczynając od królowej. Dodaj wartość znacznika do każdego podłańcucha. Edycja: Zapisano 2 bajty, pozostawiając niektóre ciągi śmieci; są one skutecznie ignorowane.

_
$n$%`7$*_

Podziel każdy znacznik na obejmujący zakres i dodaj 7 do niezerowych elementów.

(.)(?=.*;(_)*)(?<-2>.)*
$1

Usuń każdy ciąg znaków, który jest równy długości znacznika. Jest to równoważne ze znalezieniem każdego promienia na wschód, południowy zachód, południe lub południowy wschód od każdej królowej.

m`^10+1

Policz wszystkie promienie, które przechodzą przez co najmniej jeden pusty kwadrat przed spotkaniem z inną królową.

— Neil
źródło
3

JavaScript (ES6) + SnakeEx , 38 bajtów

s=>snakeEx.run('m:<*>10+1',s).length/2

Pobiera dane wejściowe w formularzu '10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'. Okazuje się, że SnakeEx może być nadal używany poza oryginalnym wyzwaniem!

— LegionMammal978
źródło
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.