Инженерная задачка для программистов

Оче­ред­ная зада­ча на нестан­дарт­ное мыш­ле­ние и логику. 

Внут­ри одно­го слож­но­го меха­низ­ма вра­ща­ет­ся диск — в одну или дру­гую сторону. 

Для рабо­ты меха­низ­ма важ­но пони­мать, в какую сто­ро­ну кру­тит­ся диск, но загля­нуть внутрь при рабо­те мы не можем. Мак­си­мум, что нам раз­ре­ша­ют сде­лать инже­не­ры, — поста­вить дат­чик и нане­сти на диск чёр­ную и белую краску.

Усло­вия:

  • Крас­ки мож­но нане­сти сколь­ко угод­но, это не повли­я­ет на рабо­ту диска.
  • Крас­ки сме­ши­вать нель­зя. Из белой и чёр­ной крас­ки нель­зя сде­лать серую.
  • Дат­чик не сра­ба­ты­ва­ет, если крас­ка не нанесена.
  • Мы не можем заме­рить ско­рость вра­ще­ния дис­ка или вре­мя пока­за чёр­ной или белой краски.
  • Дат­чик видит толь­ко после­до­ва­тель­ность из чёр­но­го (Ч) и бело­го (Б) цве­тов, напри­мер ЧБЧБ.
  • На сме­ну и появ­ле­ния цве­та дат­чик реа­ги­ру­ет момен­таль­но при любой ско­ро­сти вращения.

👉 Как нам покра­сить диск, что­бы в любой момент по после­до­ва­тель­но­сти чёр­ных и белых цве­тов мы мог­ли опре­де­лить направ­ле­ние вращения? 

Решение

Пер­вая мысль — поде­лить диск на сек­то­ра и по оче­ре­ди их закра­сить в чёр­ные и белые цвета:

Задача на логику для программистов

Но при такой рас­крас­ке мы не смо­жем опре­де­лить, в какую сто­ро­ну вра­ща­ет­ся диск, пото­му что у нас все­гда будет такая последовательность:

ЧБЧБЧБЧБЧБЧБЧБЧБЧБЧ…

Попро­бу­ем подой­ти с дру­гой сто­ро­ны: пусть весь диск будет белым, а на нём будут три чёр­ных сек­то­ра — сна­ча­ла один, а чуть подаль­ше — два дру­гих, близ­ко друг к дру­гу. По идее так мы смо­жем понять при вра­ще­нии, какой сек­тор идёт пер­вым — оди­нар­ный или двойной:

Задача на логику для программистов

Увы, это не рабо­та­ет: как бы диск ни вра­щал­ся, всё рав­но мы полу­чим один и тот же резуль­тат, пото­му что дат­чик не учи­ты­ва­ет вре­мя про­хож­де­ния, а реа­ги­ру­ет толь­ко на цвет. 

ЧБЧБЧБЧБЧБЧБЧБЧБЧБЧБ…

❗️ А теперь подключаем изобретательность

Наш дат­чик не реа­ги­ру­ет, если диск не покра­шен. По логи­ке, как толь­ко диск начи­на­ет быть покра­шен­ным, дат­чик начи­на­ет реа­ги­ро­вать. То есть мы полу­чим новую инфор­ма­цию в двух случаях:

  • Был один цвет, начал­ся другой.
  • Не было ника­ко­го цве­та, появил­ся какой-то цвет.

Это зна­чит, что у нас есть новый спо­соб изме­рять вра­ще­ние дис­ка — через «отсут­ствие цве­та» и повтор одно­го и того же цве­та. Если не закра­ши­вать часть дис­ка, то дат­чик такие части изме­рять не будет, а зано­во сре­а­ги­ру­ет на новое появ­ле­ние чёр­но­го или бело­го цвета.

Полу­ча­ет­ся, что наша зада­ча — при­ду­мать такую после­до­ва­тель­ность из Ч и Б, кото­рая в раз­ные сто­ро­ны чита­ет­ся по-разному.

Самая про­стая после­до­ва­тель­ность, кото­рая под­хо­дит под эти усло­вия — ЧЧБЧББ. При дол­гом изме­ре­нии полу­чим такое:

ЧЧБЧББЧЧБЧББЧЧБЧББ

А при вра­ще­нии в обрат­ную сто­ро­ну после­до­ва­тель­ность пре­вра­тит­ся в ББЧБЧЧ и при дол­гом изме­ре­нии ста­нет такой:

ББЧБЧЧББЧБЧЧББЧБЧЧ

Даже если её повто­рить мно­го раз, мы не най­дём в ней первую после­до­ва­тель­ность ЧЧБЧББ. Зна­чит, зада­ча про­грам­ми­ста — заме­рить хотя бы 12 сим­во­лов, поме­стить их в мас­сив и най­ти в нём одну или вто­рую базо­вую последовательность. 

Оста­лось нари­со­вать это на диске:

Задача на логику для программистов