Эвристический алгоритм решения задачи о минимальном количестве линий для размещения отрезков

Всем привет.  Мягко говоря, давно ничего не писал. Попробуем нарушить эту традицию )
Сегодня рассмотрим следующую интересную задачу.
Имеется некий список отрезков в одномерном пространстве. Каждый отрезок задан парой координат его левой и правой точек. Задача - найти минимальное количество линий, на которых можно разместить все эти отрезки таким образом, чтобы они не пересекались друг с другом.
В общем случае задача сводится к умному перебору.  Для разнообразия рассмотрим такую
категорию алгоритмов, как эвристические. Эти алгоритмы не гарантируют нахождение самого лучшего решения (хотя это и не исключено), но почти всегда дают вполне приемлемые результаты при сравнительно небольших временных затратах (этот показатель можно регулировать).

Давайте рассмотрим такой алгоритм. Будем действовать максимально просто.

Решение задачи о поиске двоичного периода числа на Haskell

Не так давно на хабре проскочила заметка, в которой автор описывал задачи, требующие решения для получения доступа на некую зарубежную биржу фриланса. Одна из задач звучала так: имеется некоторое целое число N в диапазоне от 1 до 1,000,000,000. Необходимо найти двоичный период этого числа. Что такое двоичный период ? Это количество символов двоичной последовательности наименьшей длины, которая будучи повторена минимум 2 раза приведет при её зацикливании к получению этого самого числа N на длине двоичного представления N.

На примерах это будет выглядеть так. Двоичный период чисел 1 или 0 не определен, так как двоичная "0" или "1" даже воспроизводя образ чисел 1 или 0 будет повторяться максимум 1 раз.

Двоичный период числа 127 равен 1, так как двоичное представление числа 127 - суть "1111111" (7 единиц), и двоичная последовательность наименьшей длины, которая при зацикливании воссоздаст двоичное представление числа 127 - это 1. А длина двоичного представления единицы тоже равна одному.

Рассмотрим число 955. Двоичное представление его есть "1110111011". Видно, что паттерн "1110" при повторе его 3 раза (третий раз - только первые 2 знака) даст нам полное повторение двоичного представления числа 955. Длина этого паттерна равна 4, а значит и двоичный период тоже равен 4.

Итак, суть понятна. Попробуем решить эту задачу на Haskell.

Задача о движущихся точках и её решение на языке Haskell

В блогах на сайте free-lance.ru не так давно один человек разместил задачу, условие которой в чуть облагороженном (мной :) виде звучит следующим образом:
===
Имеется N вершин, между ними есть ребра (длину ребер мы задаем сами целым числом). По ребрам ездят точки, которые могут ехать в обе стороны. При нахождении двух точек в одной вершине происходит столкновение. Соответственно, если точки едут по одному ребру навстречу друг другу, тоже произойдет столкновение. Движение точек задано списком вершин, через которые они проходят. Скорости точек равны единице. При
достижении конечной вершины точка исчезает. По заданной конфигурации сети и точек
определить, будет ли столкновение.
===
Попробуем написать решение этой задачи на Haskell.

Задача о составлении математических выражений на Хаскеле

В ЖЖ Романа Душкина не так давно был проведен конкурс на самое хорошее решение следующей задачи:
==
Даны числа 1, 5, 6 и 7. При помощи произвольного числа арифметических операций и
скобок необходимо составить такое математическое выражение из этих чисел, чтобы его
значение было равным 21. Данные числа можно использовать в выражении только по одному разу. Числа нельзя «склеивать» друг с другом (то есть из 1 и 5 получить 15).
==
Так как на конкурс я опоздал, да и решение у меня получилось наверняка не особо приятное :), опубликую его тут. Итак, в качестве языка выбираем Haskell.

Интересное об отступах в Haskell

Недавно тут меня в комментах один человек спрашивал на тему ошибки, связанной с неправильными отступами в Haskell. Загуглив на эту тему, нашел кое-что интересное. Haskell нормально проглатывает символы табуляции в исходном коде, но интерпретирует их как пробельные строки длиной 8 символов. Так как у меня в редакторе выставлен размер "таба" в 4 пробельных символа, то это дает некоторые интересные эффекты.

Рассмотрим следующий пример бестолкового кода:

f x y =
    let g = 
        x + 1 
    in g + y

Если отступы внутри тела функции f были получены применением символов табуляции, никакого сообщения об ошибке синтаксиса мы не увидим. Хотя должны были бы, так как строка "x + 1" должна быть сдвинута минимум на 1 символ вправо относительно "g" в предыдущей строке кода. Но так как символы табуляции Хаскелем разворачиваются в строки
пробелов длины 8, у нас "x+1" "уедет" значительно правее, и исходник будет обработан корректно.

Если же отступы в том же исходном тексте были честно получены при помощи пробельных символов, то при попытке его запуска мы получим сообщение "possibly incorrect indentation".

То есть, визуально одинаковый исходный код (при определенных настройках редактора) может быть и ошибочным, и нет. В любом случае, следует быть аккуратным и осторожным :)

Решение задачи о подсчете количества подчисел числа, на которые оно делится без остатка

Снова на Хабре проскочила статья-конкурс, посвященная Дню Программиста, который отмечается сегодня (кстати, с праздником всех причастных к сему событию :) В статье приводится самая простая задача, собственное решение которой на Хаскеле я и хочу привести ниже.
Итак, условие задачи:
==
Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка. Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4. Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.
==

Мое решение, не претендующее на какую-либо оптимальность:

Решение головоломки с хабра на Haskell

На днях на хабре проскочила заметка с одной простой, но изящной головоломкой.
Суть вкратце такова. Имеется автомат с пятью барабанами, где каждый барабан может принимать значение одной из карточных мастей (то есть, всего 4 положения). Каждый барабан руками можно вращать только в одну сторону на один шаг, при этом автоматически также могут вращаться остальные 4 барабана. Матрица таких вращений-сдвигов представлена ниже:
===

     1  2  3  4  5
    --------------
1:  +1 -1 +1  0  0
2:  +1 +1  0  0 -1
3:   0 -1 +1 -1  0
4:  -1  0  0 +1 +1
5:   0  0 -1 +1 +1

===
То есть, например, при вращении барабана N1 на один шаг (примем это направление за положительное), барабан N2 автоматически будет повернут на 1 шаг в обратном направлении, барабан N3 - так же как и барабан N1 - будет повернут на 1 шаг вперед, а положения барабанов N4 и N5 не изменятся.

Задача в следующем. Имеется начальное положение всех барабанов - 0 2 0 3 1, то есть, первый барабан в положении 0, второй - в 2, третий - в 0 и т.д.
Требуется найти такую последовательность поворотов барабанов, чтобы в итоге их положения приняли значения 0 0 2 0 0. Мы эту задачу чуть усложним и будем искать не просто последовательность, а последовательность минимальной длины.

Для решения будем использовать Haskell.

Решение еще некоторых задач на Haskell

Недавно на free-lance.ru в одном из заказов обнаружил вот такое тестовое задание на определение базовых навыков в области программирования:

1) Find the largest palindrome (a palindrome is a number that reads the same in either direction, e.g. 1221) formed by the product of two three-digit numbers.
{Correct answer: 906609}

2) Find the sum of the digits in the number 100! (i.e. 100 factorial)
{Correct answer: 648}

3) Given a list of pairs of numbers e.g. [(1,4), (2,5), (7,3), (4,6), (7,7)] find the longest sub-list that has the pairs sorted by the first entry in ascending order by the second in descending order, [(2,5), (7,3)].

Решение задачи J финальной части конкурса ACM ICPC 2011

Всем привет. Давно не брал я в руки шашек (в смысле, не писал ничего полезно-тематического). Сегодня мы с вами попробуем решить одну из задач, представленных в финальной части чемпионата мира по программированию среди студентов ACM ICPC 2011. С условиями задач вы можете ознакомиться здесь http://cm.baylor.edu/digital/icpc2011.pdf

Решать будем задачу J (problem J), потому как она мне сразу понравилась своей простотой )) В качестве языка программирования будем использовать Haskell (вообще, насколько я понял, на конкурсе принимались решения только на C++ или Java, но так как мы с вами в конкурсе не участвуем, позволим себе такую вольность).

Видеоурок "Вычисление конечной цепной дроби на Haskell"

Всем привет.
Продолжаем выпускать видеоуроки )
Сегодня записал небольшой видеоурок по решению упражнения N1.37 из SICP ("Структура и интерпретация компьютерных программ" Абельсона и сотоварищи) на тему вычисления конечной цепной дроби.

Сначала вкратце рассказываю, что такое бесконечная и конечная цепная дробь, каким образом с помощью неё можно вычислить коэффициент золотого сечения theta, а затем привожу решение задания на хаскеле - привести 2 варианта реализации функции вычисления конечной цепной дроби, порождающие рекурсивный и итеративный процессы,
и определить минимальное количество членов конечной цепной дроби, которая даст точность нахождения коэффициента золотого сечения в 4 знака после запятой.

Снова в видео есть некоторые огрехи, но зато они придают определенную живость повествованию ) Само видео, залитое на ютьюб, ниже:

Видеоурок "Функции высших порядков" (на примере Haskell)

Всем привет. Попробовал сделать свой первый видеоурок в Камтазии :)
В качестве темы выбрал "Функции высших порядков". Сразу говорю, что видео, скорее, для начинающих. Получилось, может быть, не очень удачно (и местами я несу какую-то околесицу), но учтите, что это мой первый опыт такого рода. Будем же любить друг друга и относиться чуть снисходительнее :).
Ну а если кому даже и понравится (вдруг!), то я буду только рад.
Вот само видео на youtube:

Haskell Platform 2010.2.0.0 и Cabal под Windows XP

Давеча столкнулся с интересной проблемой обновления пакетов в Haskell Platform 2010.2.0.0 (от июля 2010 года) под Windows XP. Изучал пример, в котором для перекодировки символов использовался модуль Encoding. Из коробки данный модель не входит в состав библиотек, поставляемых c Haskell Platform 2010.2.0.0.

Качать пакеты можно с http://hackage.haskell.org - хранилища различных пакетов модулей для хаскеля. Можно пробовать либо устанавливать пакеты вручную, либо использовать идущий вместе с хаскелем Cabal - средство для автоматической установки пакетов. Конечно, более интересным показался второй вариант. Тут же наткнулся на первые грабли.

Задача о картине, веревке и гвоздях

Недавно с помощью знакомого откопал, как я понимаю, старую задачу, условие которой формулируется следующим образом: Имеется картина, к которой обоими концами прикреплена длинная веревка. Необходимо повесить её на стене с помощью N гвоздей таким образом, чтобы при удалении любого (одного) гвоздя картина и веревка падали.

Для случая, когда гвоздь всего один, задача решается элементарно.
Будем разбираться, как её решить для 2-ух и более гвоздей. Рассмотрим ситуацию с 2-мя гвоздями. Обозначим их A и B. Введем операции (+) и (-), когда веревка обматывает гвоздь по часовой и, соответственно, против часовой стрелки. Таким образом, A + B означает, что гвозди A и B обмотаны веревкой по часовой стрелке 1 раз (по отдельности или вместе - в данном случае это не играет особой роли).
Также понятно, что A + (-A) = 0, так как мы оборачиваем гвоздь А по часовой стрелке, и тут же снимаем с него веревку против часовой стрелки. Итоговое значение 0 означает, что картину с веревкой ничего не удерживает, и они гарантированно упадут.
Удаление гвоздя будем отмечать заменой соответствующей буквы на число 0 (гвоздь перестает играть роль в процессе удержания картины). Таким образом, для того, чтобы условие задачи выполнялось, необходимо получить такую формулу, когда замена какой-либо одной (любой) буквы, обозначающей гвоздь, приводит всю формулу к нулевому значению.