Zadanie

W zadaniu posiadamy listę robotów z podanymi koordyatami startowymi i wektorami prędkości na sekundę.

p=0,4 v=3,-3

Przykładowo powyżej mamy robota na pozycji x=0 y=4, który będzie się poruszał z każdą sekundą o 3 pola w prawo i 3 w dół.

Nasza mapa jest ograniczona z lewej i górnej strony przez 0 a z prawej i dolnej przez największe wartości x i y ze wszystkich robotów, jeśli robot miałby wyjść poza planszę teleportuje on się na drugą stronę.

Naszym zadaniem jest zasymulować ruch robotów przez 100 iteracji. Jako wynik musimy policzyć ile robotów znajduje się w każdym kwadrancie (ignorujemy roboty idealnie pomiędzy dwoma kwadrantami).

Pomysł

Można by zadanie rozwiązać naiwnie iterując po każdej sekundzie ale możemy wziąć pod uwagę, że ten ruchy zaczynające się na początku osi koordynatów będą cykliczne, dodatkowo możemy rozważać koordynaty x i y niezależnie od siebie, spójrzmy na przykład.

Załóżmy że najbardziej oddalony na prawo bot miał x=5, patrząc na bota zaczynającego na x=0, mającego prędkość vx=2, spróbujmy zanelźć jego pozycję po 4 sekundach

1 sekunda: x=2
2 sekunda: x=4
3 sekunda: x=1 (po teleportacji)
4 sekunda: x=3

Możemy policzyć całkowitą drogę bota jaką musi przejść jako: sx = t * vx, gdzie t to czas, vx to prędkość w osi x. W naszym przypadku sx = 4 * 2 = 8. Jako że plansza jest cykliczna możemy wziąć resztę z dzielenia przez długość planszy. 8 % 5 = 3.

A co z robotami które nie zaczynają w wartości 0? Możemy je przesunąć do punktu 0 i dopiero wtedy policzyć resztę z dzielenia z tego co zostało po odjęciu drogi którą musieliśmy przejść do granicy planszy.

def cycle1d(val, delta, length):
    to_boundary = length - val
    if to_boundary >= delta:  # jeśli nie przekroczyliśmy granicy
        newval = val + delta
    else:
        delta -= to_boundary
        newval = delta % length
    return newval % length

W powyższym kodzie val to wartość początkowa dla jednego koordynatu, delta to droga którą musimy przejść, length to długość planszy. Funkcja zwraca nam nową wartość po przejściu delta pól.

Niestety funkcja ta nie działa dla wartości ujemnych, ale możemy ją zmodyfikować aby działała dla obu przypadków, robiąc lustrzane odbicie problemu na początku i na końcu uzyskując wynik.

Zmodyfikowana funkcja:

def cycle1d(val, delta, length):
    neg = False
    if delta < 0:
        neg = True
        delta = -delta
        val = length - val

    to_boundary = length - val
    if to_boundary >= delta:
        newval = val + delta
    else:
        delta -= to_boundary
        newval = delta % length

    if neg:
        return (length - newval) % length
    return newval % length

Rozwiązanie

Cały kod będzie wyglądał tak:

import re
import sys
from collections import defaultdict

# parsowanie
PATTERN = r"p=(-?\d+),(-?\d+) v=(-?\d+),(-?\d+)\n"

robots = []
for match in re.findall(PATTERN, sys.stdin.read()):
    robots.append(list(map(int, match)))

lenx = max(robots, key=lambda r: r[0])[0] + 1
leny = max(robots, key=lambda r: r[1])[1] + 1

SECONDS = 100


def cycle1d(val, delta, length):
    neg = False
    if delta < 0:
        neg = True
        delta = -delta
        val = length - val

    to_boundary = length - val
    if to_boundary >= delta:
        newval = val + delta
    else:
        delta -= to_boundary
        newval = delta % length

    if neg:
        return (length - newval) % length
    return newval % length


# zwraca kwadrant w którym znajduje się punkt (lub -1 jeśli na granicy)
def quadrant(x, y, lenx, leny):
    quad = 0
    if x == lenx // 2 or y == leny // 2:
        return -1
    if x > lenx // 2:
        quad += 1
    if y > leny // 2:
        quad += 2
    return quad


counter = defaultdict(lambda: 0)
for x, y, vx, vy in robots:
    newx, newy = cycle1d(x, vx * SECONDS, lenx), cycle1d(y, vy * SECONDS, leny)
    quad = quadrant(newx, newy, lenx, leny)
    counter[quad] += 1

part1 = 1
for k, v in counter.items():
    if k == -1:
        continue
    part1 *= v

print(part1)

Po uruchomieniu kodu otrzymujemy poprawny wynik w bardzo krótkim czasie, mam nadzieję że nasza optymalizacja przyda się w drugiej części…

Część druga

Jak przeczytałem treść zadania złapałem się za głowę, okazało się że w pewnej iteracji roboty formują z siebie choinkę… to tyle. To znaczy że i tak musimy symulować każdą kolejną iterację i moja optymalizacja w części pierwszej będzie totalnie bezużyteczna. Już kilka razy pisałem o przewczesnej optymalizacji, tutaj mamy przykład dlaczego tego nie robić.

Ale wracając do zadania, zmienię kod tak aby symulował ruchy robotów i w każdej iteracji, renderował ich pozycje w terminalu (czyli po prostu wypisywał planszę na ekranie, zaznaczając puste miejsca kropką a roboty np. hashtagiem). Dodam też lekką przerwę pomiędzy wypisywaniem, żebym mógł zobaczyć choinkę.

Kod jest dużo krótszy:

import time

def render(robots):
    grid = [["." for _ in range(lenx)] for _ in range(leny)]
    for x, y, _, _ in robots:
        grid[y][x] = "#"
    return "\n".join("".join(row) for row in grid)

while True:
    for i in range(len(robots)):
        x, y, vx, vy = robots[i]
        robots[i][0] = (x + vx) % lenx
        robots[i][1] = (y + vy) % leny

    print(it)
    print(render(robots))
    time.sleep(0.1)

Po uruchomieniu oglądałem jak roboty poruszają się po planszy, przez jakieś 30 sekund, ale nie zauważyłem tam żadnej choinki. Uznałem że trzeba sobie to jakoś uprościć.

Nie wiemy nic o tym jak powinna wyglądać ta choinka, ale możemy spróbować zgadnąć coś o niej, uznałem że na pewno punkty będą w miarę blisko siebie, więc spróbujmy obliczyć centrum masy wszystkich robotów, następnie możemy policzyć odległośc każdego robota od tego centrum i w ten sposób otrzymamy wartoś chaosu, która im mniejsza tym bardziej punkty są skupione w centrum. (Jak sobie teraz o tym myślę to wymyśliłem po prostu nową nazwę na wariancję).

def dist(ax, ay, bx, by): # użyjemy dystansu Manhattan
    return abs(ax - bx) + abs(ay - by)


def chaos(robots):
    xcenter, ycenter, _, _ = np.mean(robots, axis=0)  # ignorujemy prędkości
    score = 0
    for x, y, _, _ in robots:
        score += dist(x, y, xcenter, ycenter)
    return score

Teraz możemy zaimplementować funkcję, która będzie renderowała planszę tylko jeśli ma ona najmniejszy dotychczas widziany chaos.

best = float("inf")
it = 0
while True:
    for i in range(len(robots)):
        x, y, vx, vy = robots[i]
        robots[i][0] = (x + vx) % lenx
        robots[i][1] = (y + vy) % leny

    score = chaos(robots)
    if score < best:
        print(it)
        best = score
        print(score)
        print(render(robots))
    it += 1

Po uruchomieniu po kilku sekundach możemy zobaczyć choinkę!

Podsumowanie

Zadanie było nietypowe, ale ciekawe. Przez to że nie wiedzieliśmy jak ma wyglądać choinka trudno było wymyślić jakąś prostą strategię, ale ostatecznie wpadnięcie na w miarę poprawną heurystykę pomogło znaleźć rozwiązanie.