Najgorszy przypadek wykluczenia Manhattanu

20

Wyobraź sobie siatkę kwadratów W na H, która owija się toroidalnie. Elementy są umieszczane na siatce w następujący sposób.

Pierwszy przedmiot można umieścić na dowolnym polu, ale kolejne przedmioty nie mogą znajdować się w odległości R Manhattanu od jakiegokolwiek poprzedniego przedmiotu (znanego również jako sąsiedztwo Von Neumanna w zakresie R ). Staranne wybranie pozycji pozwala na umieszczenie dużej liczby elementów na siatce, zanim nie będzie już żadnych prawidłowych pozycji. Zamiast tego rozważ przeciwny cel: jaka jest najniższa liczba przedmiotów, które można umieścić i nie pozostawiają żadnych dalszych ważnych pozycji?

Oto strefa wykluczenia w promieniu 5:

Strefa wykluczenia promienia 5

Oto kolejna strefa wykluczenia w promieniu 5, tym razem w pobliżu krawędzi, więc zachowanie zawijania jest widoczne:

Promień owijania 5 stref wykluczenia

Wejście

Trzy liczby całkowite:

  • W : szerokość siatki (dodatnia liczba całkowita)
  • H : wysokość siatki (dodatnia liczba całkowita)
  • R : promień strefy wykluczenia (nieujemna liczba całkowita)

Wynik

Liczba całkowita N , która jest najmniejszą liczbą elementów, które można umieścić, uniemożliwiając dalsze prawidłowe umieszczenie.

Detale

  • Promień zera daje strefę wykluczenia 1 kwadrat (ten, na którym został umieszczony przedmiot).
  • Promień N wyklucza strefę, do której można dotrzeć w N stopni ortogonalnych (pamiętaj, że krawędzie zawijają się toroidalnie).

Twój kod musi działać w trywialnym przypadku R = 0, ale nie musi działać dla W = 0 lub H = 0.

Twój kod musi radzić sobie z przypadkiem, gdy R > W lub R > H .

Termin i przypadki testowe

Kod musi obsługiwać wszystkie przypadki testowe, a każdy przypadek testowy musi zostać ukończony w ciągu 5 minut. To powinno być łatwe (przykładowe rozwiązanie JavaScript zajmuje kilka sekund dla każdego przypadku testowego). Limit czasu ma głównie na celu wykluczenie podejścia o ekstremalnej brutalnej sile. Przykładowe podejście jest wciąż dość brutalne.

Jeśli kod zostanie ukończony w ciągu 5 minut na jednym komputerze, ale nie na innym, będzie wystarczająco blisko.

Przypadki testowe w postaci danych wejściowych: dane wyjściowe jakoW H R : N

5 4 4 : 1
5 4 3 : 2
5 4 2 : 2
5 4 1 : 5

7 5 5 : 1
7 5 4 : 2
7 5 3 : 2
7 5 2 : 4

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

 7  6  4 : 2
 7  6  2 : 4
11  7  4 : 3
11  9  4 : 4
13 13  6 : 3
11 11  5 : 3
15 14  7 : 2
16 16  8 : 2

Snippet, który pomaga wizualizować i bawić się pomysłami

Pokaż fragment kodu

Przykładowe rozwiązanie (niestosowane do golfa)

Tylko przykład dla małych wyjść (wynikających z promienia niewiele mniejszego niż szerokość i wysokość). Może obsłużyć dowolny z przypadków testowych, ale przekroczy limit czasu i zrezygnuje z większości większych przypadków.

Pokaż fragment kodu

code-golf geometry grid packing trichopaks
źródło
4
Niesamowity fragment kodu!
Stretch Maniac
@StretchManiac dzięki :) Próbuję nauczyć się JavaScript, więc każda opinia jest mile widziana
trichoplax
1
To całkiem niezły fragment. Podoba mi się również ten schemat kolorów. Czy to z palety?
mile
@miles dziękuję - kolory są po prostu zgadywane, a następnie nieco dostrojone (ale nie wiele - nadal są to wszystkie 3-znakowe kody kolorów zamiast 6). Kolory używane w trzecim bloku linii w kodzie snippet są widoczne.
trichopaks

Odpowiedzi:

5

Python 2, 216 182 bajtów

def f(W,H,R):L={(i%W,i/W)for i in range(W*H)};M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R};g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1]);return g(M)

Dane wejściowe jak f(16,16,8). Korzysta z tego samego algorytmu co próbka @ trichoplax , ale z zestawami. Początkowo nie umieszczałem pierwszego przedmiotu (0, 0), ale sprawiło to, że zadławił się w kilku ostatnich przypadkach.

Wszystkie powyższe sprawy zakończone w ciągu 10 sekund, znacznie poniżej limitu. W rzeczywistości przypadki są na tyle małe, że miałem trochę miejsca, aby być mniej wydajnym, co pozwoliło mi na usunięcie kontroli sprawdzającej, czy nie występują duplikaty stanów.

(Dzięki @trichoplax za pomoc w grze w golfa)

Rozszerzony:

def f(W,H,R):
  # All cells
  L={(i%W,i/W)for i in range(W*H)}                 

  # Mask: Complement of exclusion zone around (0, 0) 
  M={(x,y)for x,y in L if min(x,W-x)+min(y,H-y)>R}

  # Place recursively
  g=lambda s:min([1+g(s-{((a+x)%W,(b+y)%H)for x,y in L-M})for a,b in s]or[1])
  return g(M)
Sp3000
źródło
2

Python 3, 270 262 260 251 246 226

(Podziękowania dla Sp3000 za:

  • -~ zamiast +1 , co pozwala mi stracić miejsce po return ostatniej linii.
  • tracąc zbędne nawiasy wokół W*H .
  • lambdas ...
  • umieszczając wszystko w jednym wierszu.
  • python modulo %daje dodatni wynik dla liczb ujemnych, aby zapisać kolejne 20 bajtów)

To jest przykładowa odpowiedź JavaScript na pytanie zadane w Pythonie 3.

Aby uniknąć konieczności przekazywania tak wielu argumentów funkcji, przesunąłem dwie funkcje pomocnicze do funkcji obliczeniowej, aby dzieliły jej zakres. Skondensowałem również każdą z tych funkcji w jednej linii, aby uniknąć kosztów wcięć.

Wyjaśnienie

To dość brutalne podejście ustawia pierwszy element na (0, 0), a następnie zaznacza wszystkie wykluczone kwadraty. Następnie rekurencyjnie umieszcza element na wszystkich pozostałych ważnych polach, aż wszystkie kwadraty zostaną wykluczone, i zwraca minimalną wymaganą liczbę elementów.

Kod do gry w golfa:

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

Nieskluczony kod:

def calculate(W, H, R):
    starting_min = W * H + 1
    cells = [0] * (W * H)
    grid_state = grid_with_item_added(cells, 0, 0, W, H, R)
    return min_from_here(grid_state, starting_min, W, H, R) + 1

def min_from_here(grid_state, starting_min, W, H, R):
    no_cells = True
    min = starting_min
    for x in range(W):
        for y in range(H):
            if grid_state[x + W * y] == 0:
                no_cells = False
                new_grid_state = grid_with_item_added(grid_state, x, y, W, H, R)
                m = min_from_here(new_grid_state, starting_min, W, H, R)
                if m < min:
                    min = m

    if no_cells:
        return 0
    else:
        return min + 1

def grid_with_item_added(grid_state, x, y, W, H, R):
    grid = grid_state[:]
    for a in range(W):
        for b in range(H):
            if manhattan_distance(a, b, x, y, W, H) <= R:
                grid[a + W * b] = 1

    return grid

def manhattan_distance(a, b, c, d, W, H):
    horizontal = min(abs(W + c - a) % W, abs(W + a - c) % W)
    vertical = min(abs(H + d - b) % H, abs(H + b - d) % H)
    return horizontal + vertical


if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(calculate(int(arguments[0]), int(arguments[1]), int(arguments[2])))

Nieskluczony kod definiuje funkcję, a także zawiera kod umożliwiający jej wywołanie z wiersza poleceń. Kod do gry w golfa po prostu określa funkcję, która jest wystarczająca dla standardowych pytań golfowych .

Jeśli chcesz przetestować kod do gry w golfa z wiersza poleceń, oto on z obsługą wiersza poleceń (ale nie golfem):

Kod do gry w golfa do testowania z linii poleceń

def C(W,H,R):r=range;M=lambda g:min([M(G(g,x,y))for x in r(W)for y in r(H)if g[x+W*y]]or[-1])+1;G=lambda g,x,y:[g[a+W*b]if min((x-a)%W,(a-x)%W)+min((y-b)%H,(b-y)%H)>R else 0for b in r(H)for a in r(W)];return-~M(G([1]*W*H,0,0))

if __name__ == '__main__':
    import sys
    arguments = sys.argv[1:]
    if len(arguments) < 3:
        print('3 arguments required: width, height and radius')
    else:
        print(C(int(arguments[0]), int(arguments[1]), int(arguments[2])))
trichopaks
źródło