Dziś znów zagadka. Tym razem jednak o wiele ciekawsza niż ostatnio i na pewno z prawidłowym rozwiązaniem, które podam za kilka dni, o ile rzecz jasna któryś z Czytelników nie poda wcześniej poprawnej odpowiedzi w komentarzu.
A więc tak: jesteśmy w pociągu. Ale nie w jakimś tam sobie byle jakim pociągu, tylko w takim specjalnym: zapętlonym. Coś jakby wąż pożerający własny ogon, pociąg ma same wagony (bez lokomotywy), które są ustawione w kółko i połączone jeden z drugim.
Pociąg nie ma okien.
W każdym wagonie jest dokładnie jedna żarówka oraz pstryczek, za pomocą którego możemy tę żarówkę włączyć lub wyłączyć. Albo zapalić lub zgasić, jak zwał tak zwał.
Możemy:
- Przechodzić między wagonami oraz
- Przełączać żarówki w każdym wagonie
Nie możemy:
- Zajrzeć do sąsiedniego wagonu, żeby sprawdzić czy żarówka się tam świeci czy nie (między wagonami są automatyczne drzwi)
- Wyjść ani nawet wyjrzeć z pociągu na zewnątrz
- Oznaczać wagonów w żaden sposób z wyjątkiem włączania lub wyłączania żarówek.
Nie wiemy ile jest wszystkich wagonów.
Wiemy natomiast, że żarówki we wszystkich wagonach są na dzień dobry powłączane losowo – w jednych się świecą, w innych nie.
No i teraz pytanie: jak w najmniejszej liczbie kroków (rozumianych jako przejścia z wagonu do wagonu) ustalić ponad wszelką wątpliwość ile jest wszystkich wagonów w tym pociągu?
P.S. W treści zagadki nie ma ani słowa o minimalnej liczbie wagonów – załóżmy więc, że dolnym ograniczeniem jest 2. Nie ma to za bardzo sensu z technicznego punktu widzenia, ale z drugiej strony pociąg stojący w kółko na okrągłym torze też nie ma, więc się wyrównuje.
Trzeba oznaczyć któryś wagon i mierzyć ilość wagonów względem niego. Proponuję algorytm w stylu: zapamiętujemy stan światła w pierwszym wagonie (startowym) i idziemy powiedzmy w prawo, ustawiając stan światła tak, by był odwrotny niż w wagonie startowym i licząc wagony. Za każdym razem, gdy w nowym wagonie napotkamy przy wejściu stan jak w startowym, zmieniamy go i wracamy do startowego sprawdzić, czy przypadkiem się nie zmienił. Jeśli się zmienił – właśnie poznaliśmy ilość wagonów. Jeśli nie – wracamy do wagonu, gdzie dokonaliśmy zmianę i kontynuujemy podróż.
Algorytm można usprawnić: jak zgasisz światło w N-tym wagonie (dla wygody zakładam, że w początkowym [numer zero] jest włączone) i po powrocie do startowego stwierdzisz, że dalej się pali, to idziesz w drugą stronę (gasząc ewentualne światła) tak długo, aż znajdziesz ciąg przynajmniej N zgaszonych i dopiero wtedy szukasz kolejnego z zapalonym światłem i po jego zgaszeniu wracasz na początek – dzięki temu w każdym kolejnym cyklu zajdziesz znacznie dalej niż w poprzednim.
No właśnie kombinuję i na razie wymyśliłem, że w jedną stronę od startowego ustawiamy wszystkie światła w stan zapalony, w drugą – zgaszony i zliczamy ilości wagonów o znanym stanie w obie strony niezależnie. Przy każdej zmianie stanu idziemy do najdalszego znanego wagonu o stanie z którego zmienialiśmy i po sprawdzeniu kontynuujemy z niego w kierunku gdzie jest wagon o nieznanym stanie.
To Twoje nie zapętli się w skrajnym przypadku? Ciąg „przynajmniej N zgaszonych” może się nigdy nie skończyć. 😉
Jeśli wagon startowy jest zapalony – a z założenia jest, jeśli nie jesteśmy w fazie powrotnej – to zapętlenie nam nie grozi. A ustawiania różnych stanów po obu stronach trochę nie rozumiem – co to nam daje, skoro i tak po dojściu do wagonu w innym stanie trzeba wrócić na początek?
Z założenia wagon startowy jest zapalony lub nie. Co do reszty się nie wypowiadam, żeby za dużo nie podpowiedzieć i dać szansę innym.
Jak nie jest zapalony, to można zapalić albo traktować zapalone i zgaszone na odwrót, więc na jedno wychodzi.
Zgadza się
Wykombinowałem lepszy algorytm: zapalamy światło w wagonie zero i idziemy w poszukiwaniu drugiego z zapalonym światłem; jak go znajdziemy na pozycji N, to idziemy dalej w poszukiwaniu ciągu dokładnie N – 1 ciemnych wagonów, z jasnymi wagonami przed i po, gasząc wszystko po drodze. Jak już takowy znajdziemy, to znajdujemy się w kończącym ciąg jasnym wagonie na pozycji M, który być może jest tym samym co N, więc gasimy i wracamy sprawdzić. Jeśli N dalej się świeci, to wracamy na start i idziemy w drugą stronę szukając ciągu co najmniej M – N ciemnych, po którym nastąpi jeden jasny, N – 1 ciemnych i znowu jeden jasny… I tak dalej. Nawet jeśli nie będzie to optymalne, to przynajmniej bardzo wydajne – choć też i pamięciożerne, jeśli nie mamy przy sobie czegoś do pisania.