Часто задача требует реальных массивов. Возьмем, к примеру, задачу для реализации Befunge или> <>. Я попытался использовать Array
модуль для этого, но он действительно громоздок, так как мне кажется, что я слишком многословен. Кто-нибудь может мне помочь, как решить такие задачи кода-гольфа менее многословно и более функционально?
11
Ответы:
Прежде всего, я рекомендую взглянуть на Data.Vector , в некоторых случаях более хорошую альтернативу Data.Array .
Array
иVector
идеально подходят для некоторых случаев запоминания, как показано в моем ответе «Поиск максимальных путей» . Однако некоторые проблемы просто не легко выразить в функциональном стиле. Например, задача 28 в Project Euler требует суммирования чисел на диагонали спирали. Конечно, должно быть довольно легко найти формулу для этих чисел, но построение спирали является более сложной задачей.Data.Array.ST предоставляет тип изменяемого массива. Однако ситуация типа является беспорядком: он использует класс MArray для перегрузки каждого из своих методов, кроме runSTArray . Таким образом, если вы не планируете возвращать неизменный массив из действия изменяемого массива, вам придется добавить одну или несколько сигнатур типа:
Тем не менее, мое решение для Euler 28 оказалось довольно приятным и не требовало такой сигнатуры, потому что я использовал
runSTArray
.Использование Data.Map в качестве «изменяемого массива»
Если вы хотите реализовать алгоритм изменяемого массива, другой вариант - использовать Data.Map . Когда вы используете массив, вы бы хотели иметь такую функцию, которая изменяет один элемент массива:
К сожалению, это потребует копирования всего массива, если реализация не использует стратегию копирования при записи, чтобы избежать ее, когда это возможно.
Хорошая новость заключается в том ,
Data.Map
имеет такую функцию, вставка :Поскольку
Map
реализован внутри как сбалансированное двоичное дерево,insert
занимает только O (log n) время и пространство и сохраняет оригинальную копию. Следовательно,Map
не только обеспечивает несколько эффективный «изменяемый массив», который совместим с моделью функционального программирования, но он даже позволяет вам «вернуться в прошлое», если вам так угодно.Вот решение Euler 28 с использованием Data.Map:
Шаблоны взрыва предотвращают переполнение стека, вызванное тем, что элементы-накопители (курсор, число и карта) не используются до самого конца. Для большинства гольф-кодов входные регистры не должны быть достаточно большими, чтобы нуждаться в этом положении.
источник
Глибный ответ: не используйте массивы. Ответ не так прост: попробуйте переосмыслить свою проблему, чтобы она не требовала массивов.
Часто проблему с некоторыми мыслями можно решить без какого-либо массива, подобного структуре. Например, вот мой ответ на Эйлера 28:
То, что выражено в этом коде, это образец последовательности чисел, растущих вокруг прямоугольной спирали. Не было необходимости фактически представлять саму матрицу чисел.
Ключ к размышлению вне массивов - это думать о том, что на самом деле означает проблема, а не о том, как вы можете представить ее в виде байтов в оперативной памяти. Это приходит с практикой (возможно, поэтому я так много играю в гольф)
Другим примером является то, как я решил нахождение максимальных путей кода-гольфа. Там метод прохождения частичных решений в виде волны через матрицу, строка за строкой, выражается непосредственно операцией сгиба. Помните: на большинстве процессоров вы не можете работать с массивом в целом сразу: программе придется со временем работать через него. Может не потребоваться весь массив сразу в любое время.
Конечно, некоторые проблемы сформулированы таким образом, что они изначально основаны на массивах. Такие языки, как> <>, Befunge или Brainfuck, имеют в своей основе массивы. Тем не менее, даже там, массивы часто можно обойтись. Например, посмотрите мое решение для интерпретации Brainfuck , реальное ядро его семантики - молния . Чтобы начать думать таким образом, сфокусируйтесь на моделях доступа и структуре, более близкой к значению проблемы. Часто это не нужно вводить в изменяемый массив.
Когда все остальное терпит неудачу, и вам нужно использовать массив - советы @ Joey - хорошее начало.
источник