С 25 по 28 марта на Hackerrank проходил контест по функциональному программированию Lambda Calculi - March 2016. Я в нём участвовал и расскажу немного о впечатлениях.
Утром 25 марта до начала контеста я пошёл в близлежащее кафе Агафредо, чтобы подкрепиться и начать конкурс там. В первые минуты после начала контеста я занимался тем, что открывал вкладки и читал задания, пытаясь при этом не пролить кофе. Олимпиадный опыт участия и проведения ACM помог, почти про все задачи были понятно, как их решать.
Первые впечатления
- «Functions or Not» — Ad Hoc задача — сортируем список, проверяем, есть ли дубликаты
- «Compute the Perimeter of a Polygon» — простейшая геометрия, посчитать (внезапно!) периметр — тупо суммируем длины
- «Compute the Area of a Polygon» — простейшая геометрия, посчитать площадь — берём соседние отрезки, считаем ориентированную площадь треугольника (она же косое произведение) и суммируем
- «Concave Polygon» — тут я думал, что тоже простейшая геометрия, но оказалось, что она не так проста, как я думал. Об этой задаче чуть позже
- «Tree Manager» — задача на зипперы, нужно двигаться по дереву и менять его, выполняя команды
- «Fighting Armies» — тут я думал, что нужно будет писать дерево с балансировками и прочим, но выяснилось, что пакет containers разрешен, и можно взять стандартный Data.Map
- «Simplify the Algebraic Expressions» — нужно упростить выражение, задача на технику
Я начал решать, и после пары ошибок компиляции понял, что стоило порешать задачи для тренировки. Решив первые три задачи, я понял, что пора бы идти на работу… Утром некоторые коллеги удивились, что я написал, что буду через час, а вроде пришёл на работу, но делаю что-то совершенно другое, сидя на диване и попивая лимонад. Увы, это помогло не слишком сильно, ни одна задача не решилась (но для некоторых был написан ввод и вывод).
Simplify the Algebraic Expressions
Поскольку я уже успел потыкаться во все задачи кроме этой и понять, что там нужно думать, я собираюсь решить Simplify, поскольку в ней думать не нужно, а нужно аккуратно всё запрограммировать. В задаче даны арифметические выражения (с одной переменной, и делением только для чисел, причём нацело), нужно раскрыть все скобки. К сожалению, формат входа описан не слишком чётко.
Беру Parsec, пишу парсер входных данных, пишу простейшее вычисление (поскольку полиномы не выше пятой степени, делаю на списках из шести элементов) и чуть более сложный вывод. Проходит один тест, на двух валится, на четвёртом выдаёт неправильный ответ. Думаю.
Добавляю костыль. Перестаёт валиться на одном из тестов, выдаёт правильный ответ. Ругаю нечёткость формата входа.
Думаю. Добавляю кучу скобок ко входным данных, нахожу тест, на котором программа работает неверно. Думаю. Чиню.
Все тесты проходят. На часах 931 минута, или 15:31 с начала контеста.
Concave Polygon
Очень поздним вечером я понимаю, что раз в задаче порядок обхода точек многоугольника может быть любым, и нужно ответить, является ли он выпуклым, то нужно проверять, есть ли хотя бы одна точка внутри многоугольника из остальных — тогда он вогнутый, или нет — тогда выпуклый.
Пытаюсь писать, используя имеющийся код для ориентированной площади и проверяя сумму углов между внутренней точкой и парами соседних. Понимаю, что в коде куча подгона и костылей, и… переписываю всё на ray tracing.
Работает, всё проходит, 1004 минуты = 16:44 с начала. Смотрю на таблицу лидеров, отмечаю соперников, которые могут меня обогнать, ложусь спать.
Fighting Armies
Утром вижу, что mipt_vi002 лёг спать позже и обогнал меня. Думаю позавтракать в Агафредо и сажусь решать.
В этой задаче нужно искать максимум в наборе, удалять максимум из набора, добавлять число в набор и объединять два набора.
Пишу на Map. На последних тестах валится по таймауту. Переписываю на Set. На последних тестах валится по таймауту. Переписываю на IntMap (IntMap Int). На последних тестах валится по таймауту.
И тут я замечаю, что в задаче сказано “вход может быть очень большим”. Беру ByteString, немного шаманю — и тесты проходят. Время 1433 минут = 23:53 с начала.
Tree Manager
Мне остаётся победить один тест. Думаю аккуратно расписать случаи. В задаче можно менять значение в узле; печатать его; переходить к левому и правому брату, родителю и сыну с указанным номером; вставлять левого и правого брата и самого левого сына; удалять текущее поддерево.
Расписываю. Ничего не нахожу. Пишу случайные команды. Вижу неправильный ответ.
Исправляю ошибку с переходом к родителю (у меня зиппер, т.е. левые братья записаны в списке, причём голова — брат текущей вершины, поэтому при переходе наверх надо переворачивать левых братьев).
data Tree = Tree { val :: Val, children :: [Tree] }
deriving (Eq,Show)
-- Зиппер для дерева - это:
-- - родитель (если есть)
-- - левые братья
-- - текущее дерево
-- - правые братья
data Hole = Hole { parents :: Maybe Hole
, lefts :: [Tree]
, current :: Tree
, rights :: [Tree]
} deriving (Eq,Show)
cur :: Hole -> Val
cur = val . current
changeCur :: Val -> Hole -> Hole
changeCur new (Hole ps ls c rs) =
Hole ps ls (c { val = new }) rs
goLeft (Hole ps (l:ls) c rs) = Hole ps ls l (c:rs)
goRight (Hole ps ls c (r:rs)) = Hole ps (c:ls) r rs
-- ошибка: было ls ++ [c] ++ rs
goUp (Hole (Just p) ls c rs) =
p { current = (current p) { children = reverse ls++[c]++ rs }}
-- ошибка: было (take (k-1) cs)
goDown k now@(Hole p ls (Tree v cs) rs) =
Hole (Just now)
(reverse $ take (k-1) cs)
(cs!!(k-1))
(drop k cs)
insertLeft x (Hole p ls c rs) = Hole p (empty x : ls) c rs
insertRight x (Hole p ls c rs) = Hole p ls c (empty x : rs)
insertChild x (Hole p ls (Tree v cs) rs) =
Hole p ls (Tree v $ empty x : cs) rs
-- ошибка: было ls ++ rs
delete (Hole (Just p) ls c rs) =
p { current = (current p) { children = reverse ls ++ rs }}Отправляю, тесты проходят. На часах 1464 минуты, или 24:24 с начала контеста. Смотрю таблицу — в десятке. Успокаиваюсь, иду в Агафредо завтракать.
Итоговая таблица контеста
После завершения
Через несколько дней контест завершился, при этом я внезапно оказался на одно место выше (почему-то исчез тот, кто был на первом месте) — на шестом; когда же подвели окончательные итоги и посчитали рейтинг — я написал сюда. Жду футболку с Hackerrank…
Мансур Зиятдинов
9 апреля 2016