Powyższe zdjęcie pokazuje sześciokątną siatkę sześciokątów. Każda komórka w siatce ma przypisany indeks, zaczynający się od środka i spiralnie wokół w lewo, jak pokazano. Pamiętaj, że siatka będzie kontynuowana w nieskończoność - powyższe zdjęcie jest po prostu pierwszą sekcją. Następny sześciokąt przylegałby do 60 i 37.

Twoim zadaniem jest ustalenie, czy dwie podane komórki na tej siatce sąsiadują ze sobą.

Napisz program lub funkcję, która przy dwóch indeksach komórek drukuje / zwraca prawdziwą wartość, jeśli dwie komórki są sąsiadujące, i wartość falsey, jeśli nie.

Jeśli nie jest to ograniczone względami praktycznymi, Twój kod powinien teoretycznie działać dla danych wejściowych dowolnej wielkości.

Prawdziwe przypadki testowe:

0, 1
7, 18
8, 22
24, 45
40, 64
64, 65

Przypadki testowe Falsey:

6, 57
29, 90
21, 38
38, 60
40, 63
41, 39
40, 40

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź w bajtach. Zachęca się do wyjaśnień, nawet w przypadku języków innych niż ezoteryczne.

Eliksir , 263 257 264 223 214 218 214 bajtów

a=fn x,y->i=&(&1*(&1-1)*3+1)
[x,y]=Enum.sort [x,y]
if x<1,do: y in 1..6,else: (y-x==1||fn->a=y-trunc i.((r=(:math.sqrt(12*x-3)+3)/6)+1)
t=trunc r
a in [0,1,rem(b=x-i.(t)+1, t)<1&&b-t*6!=0&&2]||b<2&&a==-1 end.())end

Wypróbuj online!

wersja bez golfa

def get_ring(x) do
    1/6*(:math.sqrt(12*x-3)+3)
end

def inv_get_ring(x), do: x*(x-1)*3+1

def ring_base(x), do: inv_get_ring(trunc(x))

def is_corner(x) do
    ring = trunc(get_ring(x))
    inv_ring = ring_base(ring)
    stuff = (x-inv_ring+1)
    rem(stuff, ring) == 0
end

def is_last(x),do: ring_base(get_ring(x)+1)-1 == x
def is_first(x),do: ring_base(get_ring(x)) == x

def hex_adj(x, y) do
    {x, y} = {min(x,y), max(x,y)}
    cond do 
        x == 0 ->y in 1..6      
        y-x==1 -> true
        true ->
            adj = trunc(inv_get_ring(get_ring(x)+1))
            number = if is_corner(x)&&!is_last(x), do: 2, else: 1
            if y-adj in 0..number do
                true
            else
                is_first(x) && y == adj-1
            end
    end
end

• trunc(number) Zwraca całkowitą część liczby
• rem(a,b) Zwraca resztę a / b
• cond do end Jest to równoważne z innymi klauzulami case if w wielu imperatywnych językach

Wyjaśnienie

get_ring (indeks)

Oblicza „pierścień” indeksu.

Przykład: 1 dla 1-6, 2 dla 7-18 itd.

Ma to zastosowanie tylko wtedy, gdy wynik jest flooredytowany. Końcowe cyfry oznaczają, jak daleko ta płytka jest wokół pierścienia.

inv_get_ring (pierścień)

Oblicza odwrotność get_ring(index).

ring_base (pierścień)

Oblicza indeks pierwszej płytki w ringu.

is_corner (indeks)

Narożniki to płytki, które mają trzy sąsiednie płytki w pierścieniu zewnętrznym. Najbardziej wewnętrzny pierścień składa się wyłącznie z narożników.

Przykłady: 21,24,27,30,33,36

is_last (indeks)

Jest to prawdą, jeśli ten indeks jest najwyższy w swoim pierścieniu.

is_first (indeks)

Jest to prawdą, jeśli jest to podstawka pierścienia.

MATL , 47 45 44 43 41 bajtów

s:"JH3/^6:^t5)w5:&)@qY"w@Y"]vYs0hG)d|Yo1=

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe .

Jako bonus, kod generuje sześciokątną spiralę, która śledzi pozycje centrów komórkowych, które można graficznie zobaczyć w MATL Online , modyfikując ostatnią część kodu.

Wyjaśnienie

Ogólna idea    Kod najpierw tworzy wystarczająco dużą sześciokątną spiralę z krokiem jednostkowym. Spirala jest zdefiniowana jako wektor liczb zespolonych reprezentujących pozycje centrów komórkowych. Indeksowanie do tego wektora liczbami wejściowymi i obliczanie bezwzględnej różnicy daje odległość między dwoma wskazanymi komórkami. Komórki przylegają tylko wtedy, gdy wynik wynosi 1. Jednak ze względu na niedokładności zmiennoprzecinkowe konieczne jest zaokrąglenie przed porównaniem z wartością 1.

Budowanie spirali    Spirala będzie miała wiele „warstw” równych sumie dwóch danych wejściowych. Jest to (znacznie) większe niż to konieczne i zapewnia, że ​​komórki wejściowe będą obecne w spirali.

Aby zbudować spiralę, najpierw jest obliczana liczba zespolona j ^2/3 (gdzie j jest jednostką urojoną). Podniesienie tego do wykładników od 1 do 6 daje podstawowy zestaw przesunięć, tak że po tych przesunięciach w kolejności wyśledziłby sześciokąt. Ten sześciokąt tworzyłby najbardziej wewnętrzną warstwę spirali, z tym wyjątkiem, że byłby „zamknięty”. W rzeczywistości chcemy, aby sześciokąt „wyrósł” na ostatnim etapie, a następnie prześledzimy większy sześciokąt z dwukrotnie większą liczbą punktów (ułożonych w grupach po dwa), aby utworzyć następną warstwę spirali; patrz ilustracja tutaj . Następna warstwa będzie miała trzy razy tyle punktów, co pierwsza (w grupach po trzy); patrz tutaj .

Aby to zrobić, jako krok „rosnący” wybiera się piąte przesunięcie z zestawu podstawowego (które wskazuje w kierunku południowo-wschodnim). Warstwa k zaczyna się od tego kroku, po czym następuje pierwsze pięć podstawowych kroków powtórzonych k razy, a następnie szósty krok (kierunek wschodni) powtórzony k -1 razy. Mamy nadzieję, że stanie się to wyraźniejsze, patrząc na dwie połączone powyżej liczby.

Powstały wektor, w tym wszystkie warstwy, reprezentuje złożone przemieszczenia, które śledziłyby spiralę. Skumulowana suma podaje rzeczywiste współrzędne centrów komórek.

Wreszcie, początkowa komórka, zlokalizowana na 0, jest dołączona do końca tego wektora. Wynika to z faktu, że MATL używa modułowego indeksowania 1, a indeks 0 odnosi się do ostatniego wpisu tablicy.

Testowanie sąsiedztwa    Wybrane są dwie komórki podane przez liczby wejściowe, ich współrzędne są odjęte, a wartość bezwzględna jest zaokrąglona i porównana z 1.

Skomentowany kod

s         % Implicitly input array of two numbers. Push their sum, say S
:         % Range [1 2 ... S]
"         % For each k in [1 2 ... S]
  J       %   Push 1j
  H3/     %   Push 2, then 3, then divide: gives 2/3
  ^       %   Power
  6:      %   Push [1 2 ... 6]
  ^       %   Element-wise power. This is the array of 6 basic displacements
  t5)     %   Duplicate. Get 5th entry
  w5:&)   %   Swap. Push subarray with entries 1st to 5th, then push 6th
  @qY"    %   Repeat the 6th displacement k-1 times
  w@Y"    %   Swap. Repeat 1st to 5th displacements k times
]         % End
v         % Concatenate everything into a column vector
Ys        % Cumulative sum. This gives the cell center coordinates
0h        % Append a 0
G)        % Index by the input vector
d|        % Absolute difference
Yo        % Round to nearest integer
1=        % Does it equal 1? Implicitly display

05AB1E (starsza wersja) , 30 29 27 bajtów

α2‹i1q}1ݹ+v12y*3-tîÌy+}Ÿ²å

Wypróbuj online!

Objaśnienie kodu:

α2‹i1q}                     : if the absolute diff of the two number is 1 or 0 return 1
                          ²å: return that the second number is in
                         Ÿ  : range of {
       1Ý                   :  create [0, 1]
         ¹+                 :  add the first number to the elements
           v            }   :  map that list
            12y*3-tîÌy+     :  calculate the corresponding value where it's an adjacency
                                }

Wyjaśnienie matematyki:

„Zmarnowałem” około 5 godzin, robiąc ten golf. Krótko mówiąc, zacząłem tworzyć wykres 2d danych wejściowych i rysować Xtam, gdzie były do ​​siebie przylegające. Potem znalazłem wzór. Szukałem go na OEIS i bingo! Znalazłem tę sekwencję i użyłem wzoru podanego na stronie internetowej.

C (gcc) , 175 173 bajtów

Dzięki Peter Taylor za złapanie błędu.

Dzięki pułapowi cat za -2 bajty. Ten ~ operator nadal jest moim głównym ślepym punktem.

c,r,C,L;y(a){a=a<L*2?L-a:a<L*3?-L:a<5*L?a-L*4:L;}z(a){L=ceil(sqrt(a/3.+.25)-.5);C=y(a-=3*L*~-L);L?L=y((L+a)%(L*6)):0;}f(a,b){z(a);c=C,r=L;z(b);a=a-b&&(abs(c-C)|abs(r-L))<2;}

Wypróbuj online!

To podejście koncentruje się na znalezieniu wiersza i kolumny dwóch komórek i porównaniu ich; żaden sąsiad nie może mieć odpowiadających sobie współrzędnych różniących się o więcej niż 1. Przesuwając się od środka na zewnątrz, zauważamy, że każda warstwa ma 6 komórek więcej niż poprzednia. Oznacza to, że najwyższy „wskaźnik” w każdej warstwie L ma postać 6 * (L * (L - 1) * (L - 2) ...) lub C = 6 * (L ² + L) / 2 , gdzie C jest „globalnym” numerem komórki. Przetasowując, otrzymujemy L ² + L - C / 3 = 0, co daje retrospekcję matematyki w szkole średniej. Z tego otrzymujemy wzór pułapu (sqrt (1/4 + C / 3) + 0,5). Podłączając do niego globalny indeks komórek, otrzymujemy, w której warstwie znajduje się komórka.

Ponieważ pierwsza komórka w każdej warstwie jest naturalnie o jeden wyższa niż najwyższa z poprzedniej warstwy, znajdujemy L _start = (6 * (L - 1) ² + (L - 1)) / 2, co upraszcza do 3 * (L ² - L). Z tego otrzymujemy indeks warstw L _indeks = C - L _start .

Następnie widzimy, że każda warstwa składa się z sześciu odcinków, każdy o długości L. Zaczynając od północnego wschodu i idąc w kierunku przeciwnym do ruchu wskazówek zegara, widzimy, że dla pierwszych dwóch odcinków (1 <= _wskaźnik L <= 2 * L) otrzymujemy kolumnę z L - L _indeksu . W następnej sekcji L * 2 <L _index <= L * 3 wszystkie komórki mają jedną kolumnę -L. Dwie następne sekcje to L * 3 < _indeks L <= L * 5 wraz z kolumnami zgodnie z _indeksem L - L * 4. I wreszcie wszystkie sekcje szóste mają swoje komórki w kolumnie L. Możemy przesunąć górne granice o jeden krok dalej aby zapisać niektóre bajty w kodzie.

A co z rzędami? Aby ponownie użyć kodu, obracamy siatkę, tak aby komórka 44 była prosto w górę. Następnie uruchamiamy tę samą logikę, co w przypadku kolumn, ale tym razem nazywamy wyniki „wierszami”. Oczywiście, zamiast obracać siatkę, po prostu obchodzimy wokół niej 1/6 okrążenia.

Python 3, 150 bajtów

def h(a,b):
 L=[];i=1
 while len(L)<a+b:r=sum((i*[1j**(k/3)]for k in range(4,16,2)),[]);r[0]+=1;L+=r;i+=1
 return.9<abs(sum(L[min(a,b):max(a,b)]))<1.1

Moje rozwiązanie zasadniczo opiera się na tej samej linii myślenia, co powyższe Luis Mendo. Jeśli napisany jest bardziej czytelny, kod jest dość zrozumiały:

def h(a,b):
    L=[]
    i=1
    while len(L)<a+b:
        l=sum((i*[1j**(k/3)]for k in range(4,16,2)),[])
        l[0]+=1
        L+=l
        i+=1
return .9<abs(sum(L[min(a,b):max(a,b)]))<1.1

1. funkcja hwykonuje następujące czynności:
2. Lista L będzie zawierać (złożone) pozycje każdej liczby.
3. i to numer dzwonka.
4. W pętli while podczas każdej iteracji dodawany jest nowy pierścień. Zamiast dowiedzieć się, ile pierścieni potrzebujemy, po prostu budujemy listę, dopóki nie będzie wystarczająco długa, aby zawierać znak + b, a następnie z pewnością będzie wystarczająco długa, aby pomieścić którykolwiek z nich.
5. „lista pierścieniowa” ljest połączeniem 6 list len ​​(i) razy wektora krokowego, gdzie wektor krokowy to 1j ** (2/3) do pewnej mocy. Zakres nie zaczyna się od 0, ale od 4, co powoduje obrót całej siatki. To pozwala mi zrobić:
6. l[0]+=1 w linii 6, która jest krokiem od jednego pierścienia do następnego.
7. L+=l łączy pełną listę i listę pierścieni.
8. Lista L zawiera tylko wektory krokowe, które wciąż muszą zostać zsumowane (zintegrowane), aby uzyskać pozycję. Przyjemną cechą jest to, że możemy po prostu zsumować wycinek od najniższej liczby do najwyższej, aby uzyskać ich odległość! Z powodu błędów zaokrągleń wynik nie będzie dokładnie 1, stąd 0,9 <... <1,1. Co ciekawe, przypadek zerowy h(0,0)lub h (0,1) jest traktowany niejawnie, ponieważ suma pustej listy wynosi zero. Gdybym był pewien, że a<btj. Argumenty będą się pojawiać w porządku rosnącym, mógłbym ogolić kolejne 14 bajtów, zastępując L[min(a,b):max(a,b)]je L[a:b], ale niestety!

PS: Nie wiedziałem, że to takie stare wyzwanie, pojawiło się na szczycie kilka dni temu i ciągle mnie dręczyło :)

Mathematica, 111 105 104 bajtów

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&

Wyjaśnienie:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&definiuje funkcję, rktóra pobiera dane wejściowe #i oblicza odległość (w liczbie komórek) do komórki 0. Robi to poprzez wykorzystanie wzorca w ostatnich komórkach każdej odległości / pierścienia: 0 = 3 (0 ^ 2 + 0), 6 = 3 (1 ^ 2 + 1), 18 = 3 (2 ^ 2 + 2), 36 = 3 (3 ^ 2 + 3), ... i odwracanie formuły dla tego wzorca. Zauważ, że dla komórki 0 faktycznie zajmuje ona podłogę (1/2) + i * (sqrt (3) / 6), którą oblicza w oparciu o komponenty, aby uzyskać 0 + 0 * i = 0.

Z rzdefiniowane r@#jest pierścień dla komórki #(wewnątrz definicji innej funkcji). #+3r@#-3(r@#)^2&nie pojawia się dokładnie w kodzie, ale pobiera numer komórki i odejmuje najwyższą liczbę komórek w następnym pierścieniu wewnętrznym, aby dać odpowiedź na pytanie „która to komórka bieżącego pierścienia?” Na przykład komórka 9 jest trzecią komórką pierścienia 2, więc r[9]wyprowadziłaby 2 i #+3r@#-3(r@#)^2&[9]wyprowadziłaby 3.

Z powyższą funkcją możemy skorzystać, aby znaleźć kąt biegunowy, kąt przeciwny do ruchu wskazówek zegara od promienia „komórka 0, komórka 17, komórka 58” do danej komórki. Ostatnia komórka każdego pierścienia jest zawsze pod kątem Pi / 6, a my obchodzimy pierścień w odstępach co Pi / (3 * liczba_pierścienia). Teoretycznie musimy obliczyć coś takiego jak Pi / 6 + (który_komórka_prądu_ring) * Pi / (3 * numer_krętu). Obrót obrazu nic jednak nie wpływa, więc możemy odrzucić część Pi / 6 (aby zaoszczędzić 6 bajtów). Łącząc to z poprzednią formułą i upraszczając, otrzymujemyPi(#/(3r@#)+1-r@#)&

Niestety nie jest to zdefiniowane dla komórki 0, ponieważ jej numer dzwonka to 0, więc musimy to obejść. Naturalnym rozwiązaniem byłoby coś takiego t=If[#==0,0,Pi(#/(3r@#)+1-r@#)]&. Ale ponieważ nie dbamy o kąt dla komórki 0 i ponieważ r@#się powtarza, możemy faktycznie zapisać bajt tutajt=Limit[Pi(#/(3x)+1-x),x->r@#]&

Teraz, gdy mamy numer pierścienia i kąt, możemy znaleźć pozycję komórki (środka), abyśmy mogli przetestować sąsiedztwo. Znalezienie rzeczywistej pozycji jest denerwujące, ponieważ pierścienie są sześciokątne, ale możemy po prostu udawać, że pierścienie są idealnymi okręgami, więc traktujemy numer pierścienia jako odległość do środka komórki 0. To nie będzie problem, ponieważ przybliżenie jest dość blisko. Używając postaci biegunowej liczby zespolonej , możemy przedstawić tę przybliżoną pozycję w płaszczyźnie zespolonej za pomocą prostej funkcji:p = r@#*Exp[I*t@#] &;

Odległość między dwiema liczbami zespolonymi na płaszczyźnie zespolonej jest podawana przez wartość bezwzględną ich różnicy, a następnie możemy zaokrąglić wynik, aby zająć się wszelkimi błędami z przybliżenia i sprawdzić, czy jest to równe 1. Funkcja, która w końcu czy ta praca nie ma nazwy, ale jest Round@Abs[p@#-p@#2]==1&.

Możesz wypróbować go online w piaskownicy Wolfram Cloud , wklejając poniższy kod i klikając Gear -> „Oceń komórkę” lub naciskając Shift + Enter lub Enter na klawiaturze numerycznej:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&[24,45]

Lub dla wszystkich przypadków testowych:

r=Floor[(1+Sqrt[(4#-1)/3])/2]&;t=Limit[Pi(#/(3x)+1-x),x->r@#]&;p=r@#*Exp[I*t@#]&;Round@Abs[p@#-p@#2]==1&//MapThread[#,Transpose[{{0,1},{7,18},{8,22},{24,45},{40,64},{64,65},{6,57},{29,90},{21,38},{38,60},{40,63},{41,39},{40,40}}]]&