Worst Case Manhattan Ausschluss

20

Stellen Sie sich ein W x H- Gitter von Quadraten vor, das sich toroidal umschließt. Die Elemente werden wie folgt in das Raster eingefügt.

Der erste Gegenstand kann auf ein beliebiges Feld gelegt werden, nachfolgende Gegenstände dürfen sich jedoch nicht innerhalb eines Manhattan-Abstands R zu einem vorherigen Gegenstand befinden (auch als Von Neumann-Nachbarschaft der Reichweite R bekannt ). Wenn Sie die Positionen sorgfältig auswählen, können Sie eine große Anzahl von Elementen in das Raster einfügen, bevor keine gültigen Positionen mehr vorhanden sind. Betrachten Sie stattdessen das gegenteilige Ziel: Was ist die niedrigste Anzahl von Elementen, die platziert werden können und keine weiteren gültigen Positionen belassen?

Hier ist eine Ausschlusszone mit Radius 5:

Ausschlusszone für Radius 5

Hier ist eine weitere Ausschlusszone für Radius 5, diesmal in der Nähe der Kanten, damit das Umwicklungsverhalten ersichtlich wird:

Wickelradius 5 Sperrzone

Eingang

Drei ganze Zahlen:

  • W : Breite des Gitters (positive ganze Zahl)
  • H : Höhe des Gitters (positive ganze Zahl)
  • R : Radius der Ausschlusszone (nicht negative ganze Zahl)

Ausgabe

Eine Ganzzahl N , die die kleinste Anzahl von Elementen darstellt, die platziert werden können, um weitere gültige Platzierungen zu verhindern.

Einzelheiten

  • Ein Radius von Null ergibt eine Ausschlusszone von 1 Quadrat (dasjenige, auf das der Gegenstand gelegt wurde).
  • Ein Radius von N schließt die Zone aus, die in N orthogonalen Schritten erreicht werden kann (denken Sie daran, dass die Kanten toroidal gewickelt sind).

Ihr Code muss für den einfachen Fall von R = 0 funktionieren, muss jedoch nicht für W = 0 oder H = 0 funktionieren .

Ihr Code muss sich auch mit dem Fall befassen, in dem R > W oder R > H ist .

Zeitlimit und Testfälle

Ihr Code muss in der Lage sein, alle Testfälle zu verarbeiten, und jeder Testfall muss innerhalb von 5 Minuten abgeschlossen sein. Dies sollte einfach sein (die Beispiel-JavaScript-Lösung dauert für jeden Testfall einige Sekunden). Das Zeitlimit besteht hauptsächlich darin, den extremen Brute-Force-Ansatz auszuschließen. Der beispielhafte Ansatz ist immer noch ziemlich brachial.

Wenn Ihr Code auf einem Computer innerhalb von 5 Minuten ausgeführt wird, auf einem anderen jedoch nicht, ist dies ausreichend.

Testfälle in den Formulareingaben: Ausgabe alsW 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 zum Visualisieren und Herumspielen von Ideen

Code-Snippet anzeigen

Beispiel (ungolfed) Lösung

Nur ein Beispiel für kleine Leistungen (resultierend aus einem Radius, der nicht viel kleiner als die Breite und Höhe ist). Kann mit jedem der Testfälle umgehen, gibt aber bei den meisten größeren Fällen auf.

Code-Snippet anzeigen

code-golf geometry grid packing Trichoplax
quelle
4
Geniales Code-Snippet!
Stretch Maniac
@StretchManiac Dank :) Ich versuche , JavaScript zu lernen , so jedes Feedback ist willkommen
Trichoplax
1
Das ist ein ziemlich netter Ausschnitt. Ich mag das Farbschema auch. Ist es aus einer Palette?
Meilen
@miles danke - die Farben werden nur erraten und dann ein wenig feinabgestimmt (aber nicht viel - es sind immer noch alle 3-stelligen Farbcodes anstatt 6). Sie können die im dritten Zeilenblock verwendeten Farben im Snippet-Code sehen.
Trichoplax

Antworten:

5

Python 2, 216 182 Bytes

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)

Eingabe wie f(16,16,8). Verwendet fast den gleichen Algorithmus wie @ trichoplax , jedoch mit Mengen. Ursprünglich habe ich den ersten Artikel nicht bei platziert (0, 0), aber dies hat ihn in den letzten Fällen zum Ersticken gebracht.

Alle oben genannten Fälle sind innerhalb von 10 Sekunden abgeschlossen. Tatsächlich sind die Fälle so klein, dass ich etwas weniger effizient arbeiten konnte, sodass ich einen Scheck entfernen konnte, der nach doppelten Zuständen suchte.

(Danke an @trichoplax für die Hilfe beim Golfen)

Erweitert:

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
quelle
2

Python 3, 270 262 260 251 246 226

(Dank an Sp3000 für:

  • -~ stattdessen +1 , wodurch ich in der letzten Zeile ein Leerzeichen nachher verliere return .
  • überflüssige Klammern verlieren W*H .
  • Lambdas ...
  • Alles auf eine Linie setzen.
  • Python Modulo %liefert positive Ergebnisse für negative Zahlen, um weitere 20 Bytes zu sparen)

Dies ist die JavaScript-Beispielantwort von der in Python 3 portierten Frage.

Um zu vermeiden, dass so viele Funktionsargumente übergeben werden müssen, habe ich die beiden unterstützenden Funktionen in der Berechnungsfunktion so verschoben, dass sie den Gültigkeitsbereich teilen. Ich habe auch jede dieser Funktionen in einer einzigen Zeile zusammengefasst, um die Kosten für das Einrücken zu vermeiden.

Erläuterung

Bei diesem ziemlich brachialen Ansatz wird das erste Objekt auf (0, 0) gesetzt und anschließend alle ausgeschlossenen Felder markiert. Anschließend wird ein Element rekursiv an allen verbleibenden gültigen Feldern platziert, bis alle Felder ausgeschlossen sind, und die erforderliche Mindestanzahl von Elementen wird zurückgegeben.

Golf Code:

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))

Ungolfed-Code:

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])))

Der ungolfed Code definiert eine Funktion und enthält auch Code, mit dem er über die Befehlszeile aufgerufen werden kann. Der Golf-Code definiert lediglich die Funktion, die für Standard-Code-Golf-Fragen ausreicht .

Wenn Sie den Golf Code von der Kommandozeile aus testen möchten, ist hier die Kommandozeilenbehandlung enthalten (aber nicht Golf):

Kommandozeilen testbarer Golf Code

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])))
Trichoplax
quelle