Optymalna strategia dla abstrakcyjnej gry


12

W wywiadzie otrzymałem następujący problem (którego już nie udało mi się rozwiązać, nie próbując oszukać mojej przeszłości): Gra rozpoczyna się od dodatniej liczby całkowitej . (Np. ) Liczba ta jest konwertowana na reprezentację binarną, a jest liczbą bitów ustawioną na . (Np. , )A 0 = 1234 N 1 A 0 = b 100 1101 0010 N = 5.A0A0=1234N1A0=b100 1101 0010N=5.

Gracz 1 wybiera liczbę mniejszą niż . musi mieć tylko jeden bit ustawiony na 1. (Np. ). Niech . (Np a_1 = 1234-512 = = 722 B10 1101 0010 ). Ruch jest ważny jeśli B_0 spełnia poprzednich ograniczeń, a liczba bitów ustawionych w A_1 nadal równa n .A 0 B 0 B 0 = b 10 0000 0000 = 512 A 1 = A 0 - B 0 A 1 = 1234 - 512 = 722 = b 10 1101 0010B0A0B0B0=b10 0000 0000=512ZA1=ZA0-b0A1=1234-512=722=b1011010010A 1b0ZA1

Gracz 2 kontynuuje od ZA1 , wybierając prawidłowy b1 , następnie gracz 1 kontynuuje od ZA2) i tak dalej. Gracz przegrywa, jeśli nie ma już żadnych ważnych ruchów.

Zakładając, że obaj gracze grają optymalnie, określ zwycięskiego gracza za pomocą dość wydajnej metody. (W mojej definicji problemu ograniczeniem było to, że program musi być w stanie dostarczyć rozwiązanie dla kilku milionów liczb wejściowych, które pasują do 32-bitowej liczby całkowitej ze znakiem). Oznacza to, że rozwiązaniem nie musi być w pełni analityczny.


Moim osobistym zainteresowaniem jest ustalenie, czy oczekiwanie ode mnie znalezienia i wdrożenia prawidłowego rozwiązania bez opinii zwrotnej na temat poprawności w ciągu 120 minut, które otrzymałem, było uzasadnione; lub jeśli było to jedno z tych pytań „zobaczmy, czy widzieli już tę zagadkę”.

Nie udało mi się, ponieważ zdecydowałem się wdrożyć coś, co wydawało się rozsądną strategią, która dała mi prawidłowe wyniki dla kilku przypadków testowych, które otrzymałem z góry, zmarnowałam zbyt dużo czasu na szybkie uruchomienie i skończyła się niepoprawnym podawaniem pełna wydajność, gdy mój czas się skończył.

Z perspektywy czasu powinienem był zastosować wyszukiwanie siłowe i zapamiętać częściowe rozwiązania dla małych liczb początkowych, ale z perspektywy czasu zawsze jest 20/20. Jestem jednak ciekawy, czy istnieje inne wspólne podejście, które wymknęło mi się z tropu.


Z opisu nie zrozumiałem, że wybrane ruchy muszą mieć pojedynczy bit ustawiony na 1 (myślałem, że to tylko część przykładu).
jjmontes

@jjmontes - Jest to pierwsza zasada wyboru numeru B - wszystkie przykłady są oznaczone jako takie, wszystko poza nawiasami jest ogólne. Czy masz sugestię, jak można by to wyjaśnić?
millimoose

1
Może „Gracz 1 wybiera liczbę mniejszą niż , która musi mieć tylko jeden bit ustawiony na 1.”? (może to tylko ja, ale musiałem przeczytać odpowiedź @orlp, aby zdać sobie sprawę, że to ograniczenie). b0A0
jjmontes

@ Veedrac - Człowieku, gdybym to wiedział, cały mój wysiłek włożony w to, aby bitcount działał dość szybko, nie byłby stratą. Odpowiedź wyjaśniająca, dlaczego to działa, byłaby doskonała.
millimoose

@millimoose Bitcount jest sprzętem dla większości nowoczesnych procesorów!
Veedrac

Odpowiedzi:


21

Poświęć chwilę na uświadomienie sobie, że jeśli możemy odjąć potęgę dwóch, a liczba ludności nie może się zmienić, musimy odjąć w pozycji, w której druga liczba to . Wynikiem tego jest zawsze w tej pozycji, a liczba nie zmienia się nigdzie indziej.011001

Innymi słowy, gra jest serią zamian , a gra kończy się, jeśli wszystkie są po prawej stronie. Pamiętaj, że nie można wcześnie zakończyć tej gry - nie możesz utknąć. Zawsze znajdziesz się w pozycji, w której wszystkie zera są po lewej stronie, a wszystkie z nich są po prawej stronie.1001

Jedynym decydującym czynnikiem w grze jest to, ile swapów potrzeba, aby dostać się do stanu, w którym wszystkie są po prawej, i nie ma strategii wygranej lub przegranej. Jedynym czynnikiem determinującym jest parzystość liczby transakcji zamiany.

Więc ile swapów to zajmuje? Zauważ, że s nie mogą się krzyżować, więc jeśli je ponumerujemy i prześledzimy poprzez swapy, pozostaną w tej samej kolejności w końcowym stanie. Każda zamiana przybliża ich do ostatecznej pozycji.1

Więc jeśli ta (licząc od prawej, skrajna prawa to ta ) znajduje się w pozycji z prawej, potrzebuje zamienia, aby dostać się do swojej właściwej pozycji. To daje nam algorytm do zliczania wymaganej liczby swapów:ja1101kk-ja

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

Teraz możemy po prostu spojrzeć na parytet, totalaby zobaczyć, kto wygra. Złożoność czasu wynosi .O(logn)


To wydaje się słuszne, natknąłem się na drobiazgi tego podejścia po przekazaniu. Chyba skończyłem, skacząc z pistoletu po rozpoczęciu kodowania i pogrążając się w wyniku pościgu za dziką gęsią.
millimoose

Myśląc o tym, fakt, że strategia nie ma znaczenia, oznacza, że ​​albo mam dość niejasny błąd w mojej implementacji, albo powinien on dać takie same wyniki, jak każda inna implementacja, w którą gra się poprawnie…
millimoose

5

Jednym ze sposobów rozwiązania takiego problemu jest:

  • Znajdź rozwiązanie dla kilku prostych wartości, korzystając z proponowanego przez ciebie „zapamiętywanego brute-force”.

  • Odgadnij odpowiedź (które pozycje wygrywają, a które tracą).

  • Spróbuj udowodnić swoją odpowiedź. Jeśli ci się uda, świetnie. W przeciwnym razie spróbuj znaleźć kontrprzykład i użyj go, aby odgadnąć inną odpowiedź. W tym przypadku pomocne może być rozwiązanie kilku innych przypadków.

Naprawdę trudno powiedzieć, ile czasu to zajmuje. Jednak w wywiadach niekoniecznie oczekuje się rozwiązania. Ankieterzy chcą raczej wiedzieć, jak podeszliście do rozwiązania problemu i jaki postęp udało wam się osiągnąć.


Tak, nie, odrzucili mnie, ponieważ moje wyniki były złe i zabrakło mi czasu.
millimoose

Zapamiętane podejście brutalnej siły byłoby poprawne, ponieważ nie wymaga skrótów dotyczących strategii. Byłoby jednak również - pomyślałem - powolne, a zapamiętywanie mogłoby być zbyt pracochłonne, aby nie przydało się wiele pomocy bez użycia głupich pamięci. A może nie, spróbuję później, aby usunąć to z mojego systemu.
millimoose

5

Zwróć uwagę na odpowiedź @ orlp, że chcemy parzystości sumy przesunięć z pozycji początkowej do pozycji końcowej. Dodajmy do tego adnotację:

       9876543210
       9 76 4  1    (positions at start)
start: 1011010010
end:   0000011111
            43210   (positions at end)

Więc chcemy

  ((1 - 0) + (4 - 1) + (6 - 2) + (7 - 3) + (9 - 4)) & 1
= ((1 + 4 + 6 + 7 + 9) - (0 + 1 + 2 + 3 + 4)) & 1
= ((1 + 0 + 0 + 1 + 1) - (0 + 1 + 0 + 1 + 0)) & 1

Pierwsza część to parzystość liczby bitów w pozycjach nieparzystych. Możesz to maskować, biorąc maksymalną liczbę całkowitą bez znaku, dzieląc przez 0b11 i negując.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (0 + 1 + 0 + 1 + 0)) & 1

Druga część to parzystość połowy liczby bitów x.

= (bitcount(x & ~(UINT_MAX / 0b11)) ^ (bitcount(x) >> 1)) & 1

bitcountmoże albo użyć popcntinstrukcji sprzętowej , albo może zostać zaimplementowany ręcznie, wykorzystując, że potrzebny jest tylko ostatni lub drugi do ostatniego bit, z takimi szybkimi redukcjami .

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.