Как я уже упоминал, на дарксторах Лавки происходит множество удивительных операционных процессов. Например, переборка яиц. Как минимум такую строчку я видел в одной из волшебных экселек. Я пока не убедился, что это именно то, что я себе представил, но предположим, что суть процесса в том, чтобы перекомплектовать лотки так, чтобы не продавать разбитые яйца.
А это неплохая задачка для собеседований или контестов - подумал я. И попытался решить ее. Вообще я обычно не люблю, когда в условия алгоритмических задачек добавляют каких-то неуместных лирических героев и прочий сторителлинг - обычно он выглядит натянутым. Тут - другое дело, тут сама задачка рождается из физического мира, а это мы любим. Сформулируем задачку так:
Написать функцию, которая на вход принимает строку. В строке последовательности нулей (целое яйцо) и единиц (битое яйцо) по 10 в ряд (лоток вмещает 10 яиц) разделены пробелами (считаем, что входные данные корректны). На выходе нужно в аналогичном формате получить лотки так, чтобы в начале строки были все целые, в правой - битые, а также количество лотков, которые можно считать товарными (содержащие только целые яйца).
Пример:
'0101010101 1010101010 0101010101' -> '0000000000 0000011111 1111111111', 1.Сначала подойдем к решению этой задачки в классической алгоритмической парадигме - в один проход двумя встречными итераторами со свапом. Оказалось, тут не так мало корнер-кейсов, как казалось. Тем не менее, получаем какое-то такое решение:
def eggs(s):
lst = list(s)
i, j, full = 0, len(lst)-1, 0
while (lst[j] == '1' or lst[j] == ' ') and j >= 0:
j -= 1
while i<j:
if lst[i] == ' ':
full += 1
elif lst[i] == '1':
lst[i], lst[j] = lst[j], lst[i]
j -= 1
while (lst[j] == '1' or lst[j] == ' ') and j>i:
j -= 1
i += 1
if i == len(lst)-1 or lst[i] == ' ':
full +=1
return ''.join(lst), full{}
Не самое элегантное и читаемое. Любой олимпиадник тут же сочтет это решение довольно наивным и предложит альтернативу. Особенно если мы еще и целимся в правила код-гольфа (кто не знает - это такой вид контеста, где нужно решить задачу наименьшим количеством символов кода). Например, в таком духе (тут я осознанно не пускаюсь в лишние оптимизации и сокращения, чтобы сохранить хоть толику читаемости. Это в контестах/код-гольфе код чисто write-only, а мы тут просто балуемся):
def eggs(s):
solid = s.count('0')
full = solid // 10
res_full = ('0' * 10 + ' ') * full
res_mixed = '0' * (solid % 10) + '1' * (10 - (solid % 10 if solid % 10 else 10))
res_broken = (' ' + '1' * 10) * (len(s.split()) - full - (1 if res_mixed else 0))
if not res_mixed:
res_broken = res_broken.lstrip()
return (res_full + res_mixed + res_broken).strip(), full
{}
Однако, представим себе на минутку, что наш код будет исполняться не на кремниевых кристаллах, а на органических соединениях с костями и кожей. И кладовщик не может в моменте подбросить все несколько десятков яиц в воздух и поймать их в правильные ячейки. Так что возвращаемся к первому решению и начинаем его операционно оптимизировать, чтобы избежать лишних перекладываний, например, в случае целиком битых лотков. Но это уже - другая история.
P.S. Я сомневаюсь, что мы правда пишем алгоритмы таких ручных операций. Этот пост - лишь еще одно метафорическое описание отличий операционного продукта от pure-digital.
P.P.S. На всякий случай оставлю тесткейсы для задачки - https://telegra.ph/tests-12-09-3. Кто напишет в комментариях самое короткое решение (по правилам код-гольфа), получит от меня в личку мой любимый стикерпак и ссылку на вакансии)
