В предыдущей статье (Clojure и Project Euler, часть 1) я описал решение первых 3 задач из проекта Эйлер с использованием clojure — достаточно молодого языка, но имеющего известных родителей.
В этой статье я продолжу знакомить читателя (да и себя тоже) с этим забавным джава-лиспом. И покажу решение ещё 3 несложных задач из Эйлера.
Задание
Найти максимальное произведение 2 трёхзначных чисел, которое является палиндромом.
Алгоритм
1. Создать пос-ть всех произведений.
2. Отфильтровать, оставив только палиндромы.
3. Найти максимум.
Код
Сначала определим ф-цию, определяющую, палиндром строка или нет.
Я решил тренировать силу воли и стараться писать код с комментариями, по крайней мере ф-ции.
Стоит отметить 4 вещи.
1. Описание ф-ции пишется послее её имени и перед списком аргументов. Это описание будет отображаться, когда вы будете вызывать (doc your-function).
2. В clojure все предикаты (я их понимаю как ф-ции от одной переменной, возвращающие true или false) обычно заканчиваются на вопросительный знак.
3. Т.к. мы передаём число, то должны его преобразовать к в строку сначала, это делается с помощью ф-ции str.
4. word имеет тип String, а (reverse word) возвращает уже последовательность и при простом сравнении всегда будет false. Поэтому надо сделать из word тоже пос-ть. Это мы и делаем с помощью (seq word).
Теперь основная часть:
С (reduce max… ) должно быть более менее понятно, просто берёт максимум от пос-ти, которую она получает.
В (filter… ) мы фильтруем пос-ть чисел и оставляем только палиндромы, причём сразу передаём туда наш предикат palindrom?, а не анонимную ф-цию, как в предыдущие разы.
Более наглядный пример for:
Задание
Вывести минимальное число, которое делится на все числа от 1 до 20 включительно.
Алгоритм
Берём и находим наименьшее общее кратное 20 чисел.
Код
Конечно можно написать свой НОК, но мы не будем… Лучше воспользуемся готовыми ф-циями, а точнее библиотеками. Обычно вместе c clojure подключают сразу и clojure-contrib (http://clojure.org/libraries) — сборку библиотек, написанных, как я понимаю, простыми пользователями. Clojure-contrib идёт просто в jar-файле и включается в путь наравне c clojure.jar. Тут есть много всяких разных полезностей. Можно отметить, что в библиотеке lazy-seq есть пос-ть Фиббоначи и пос-ть простых чисел, которые мы писали в прошлой статье. Но нас сейчас будет интересовать библиотека math, в которой есть ф-ция lcm — НОК.
Подключаем:
И решаем:
Я буду пропускать некоторые задачи, которые не требуют никаких особых новых знаний языка, а только реализации. Так что перейду сразу к 8:
Задание
Дано число с 1000 знаками и надо найти в нём 5 последовательных цифр, которые дают максимальное произведение и вывести это произведение. Само число можно посмотреть тут: (http://projecteuler.net/index.php?section=problems&id=8)
Алгоритм
1. Сначала надо это число ввести в программу, я решил сохранить его в файл и прочитать оттуда, потому что в записывать его редакторе не очень удобно. Заодно поработаем с библиотеками самой джавы.
2. Разбить число на пос-ть групп по 5 цифр.
3. Перемножить и взять максимум.
Код
Число (20 строк по 50 символов) хранится в файле input.txt
Тут можно увидеть знакомые классы BufferedReader и FileReader. Создавать новые экземляры класса можно через ф-цию new, в которой второй параметр — название класса, третий, четвёртый и т.д. — аргументы для конструктора этого класса. Стоит заметить, что мы можем и импортировать класс, чтобы не писать полное имя, но импортировать сразу все классы из пакета, как в джаве, не можем. Надо по одному.
Вызывать методы на экземпляре класса можно через точку: (.methodName instance arg1 arg2 ...).
Напишем метод, который будет превращать строку в пос-ть цифр:
Тут стоит отметить, что к статическим методам и переменным классов джавы можно обращаться через ClassName/methodName.
А теперь основная часть:
Тут используется забавная ф-ция partition, которая возвращает пос-ть подпоследовательностей данной пос-ти :)
В общем в нашем случае он разбила пос-ть цифр, на пос-ть, элементы которой — группы по 5 цифр, с шагом 1.
Вот пожалуй и всё пока. Напоследок хотел бы дать ссылку на сайтик, в котором собраны решения на кложуре заданий из Эйлера, сам неожиданно для себя наткнулся. Там правда не все, но всё же можно посмотреть какие бывают варианты и поучиться, думаю: http://clojure-euler.wikispaces.com/
В этой статье я продолжу знакомить читателя (да и себя тоже) с этим забавным джава-лиспом. И покажу решение ещё 3 несложных задач из Эйлера.
Задача 4
Задание
Найти максимальное произведение 2 трёхзначных чисел, которое является палиндромом.
Алгоритм
1. Создать пос-ть всех произведений.
2. Отфильтровать, оставив только палиндромы.
3. Найти максимум.
Код
Сначала определим ф-цию, определяющую, палиндром строка или нет.
Я решил тренировать силу воли и стараться писать код с комментариями, по крайней мере ф-ции.
(defn palindrom?
"Returns true if x is palindrom,
false otherwise."
[x]
(let [s (str x)]
(= (seq s) (reverse s))))
Стоит отметить 4 вещи.
1. Описание ф-ции пишется послее её имени и перед списком аргументов. Это описание будет отображаться, когда вы будете вызывать (doc your-function).
2. В clojure все предикаты (я их понимаю как ф-ции от одной переменной, возвращающие true или false) обычно заканчиваются на вопросительный знак.
3. Т.к. мы передаём число, то должны его преобразовать к в строку сначала, это делается с помощью ф-ции str.
4. word имеет тип String, а (reverse word) возвращает уже последовательность и при простом сравнении всегда будет false. Поэтому надо сделать из word тоже пос-ть. Это мы и делаем с помощью (seq word).
Теперь основная часть:
(reduce max
(filter palindrom?
(for [ i (range 100 1000) j (range i 1000)] (* i j))))
С (reduce max… ) должно быть более менее понятно, просто берёт максимум от пос-ти, которую она получает.
В (filter… ) мы фильтруем пос-ть чисел и оставляем только палиндромы, причём сразу передаём туда наш предикат palindrom?, а не анонимную ф-цию, как в предыдущие разы.
(for [ i (range 100 1000) j (range i 1000)] (* i j))тут используется ф-ция for, которая возвращает пос-ть. В ней указываются локальные переменные в скобках [ ], которые обычно и используются в циклах (не знаю как правильно их назвать, но думаю, что все знают где используются i и j). Сама пос-ть формируется из значений выражения, стоящего после биндинга [ ]. В нашем случае это просто произведение i и j. Тут ещё небольшое улучшение в том, что j пробегает не от 100 до 1000, а от текущего i, что ускоряет работу.
Более наглядный пример for:
(for [i (range 1 5) j (range i 5)] [i j])
; Получим пос-ть векторов: ([1 1] [1 2] [1 3] [1 4] [2 2] [2 3] [2 4] [3 3] [3 4] [4 4])
Задача 5
Задание
Вывести минимальное число, которое делится на все числа от 1 до 20 включительно.
Алгоритм
Берём и находим наименьшее общее кратное 20 чисел.
Код
Конечно можно написать свой НОК, но мы не будем… Лучше воспользуемся готовыми ф-циями, а точнее библиотеками. Обычно вместе c clojure подключают сразу и clojure-contrib (http://clojure.org/libraries) — сборку библиотек, написанных, как я понимаю, простыми пользователями. Clojure-contrib идёт просто в jar-файле и включается в путь наравне c clojure.jar. Тут есть много всяких разных полезностей. Можно отметить, что в библиотеке lazy-seq есть пос-ть Фиббоначи и пос-ть простых чисел, которые мы писали в прошлой статье. Но нас сейчас будет интересовать библиотека math, в которой есть ф-ция lcm — НОК.
Подключаем:
(use 'clojure.contrib.math)
И решаем:
(reduce lcm (range 1 21))
Я буду пропускать некоторые задачи, которые не требуют никаких особых новых знаний языка, а только реализации. Так что перейду сразу к 8:
Задача 8
Задание
Дано число с 1000 знаками и надо найти в нём 5 последовательных цифр, которые дают максимальное произведение и вывести это произведение. Само число можно посмотреть тут: (http://projecteuler.net/index.php?section=problems&id=8)
Алгоритм
1. Сначала надо это число ввести в программу, я решил сохранить его в файл и прочитать оттуда, потому что в записывать его редакторе не очень удобно. Заодно поработаем с библиотеками самой джавы.
2. Разбить число на пос-ть групп по 5 цифр.
3. Перемножить и взять максимум.
Код
Число (20 строк по 50 символов) хранится в файле input.txt
(def number
(let [reader (new java.io.BufferedReader (new java.io.FileReader "input.txt"))]
(reduce str (for [i (range 20)] (.readLine reader)))))
Тут можно увидеть знакомые классы BufferedReader и FileReader. Создавать новые экземляры класса можно через ф-цию new, в которой второй параметр — название класса, третий, четвёртый и т.д. — аргументы для конструктора этого класса. Стоит заметить, что мы можем и импортировать класс, чтобы не писать полное имя, но импортировать сразу все классы из пакета, как в джаве, не можем. Надо по одному.
Вызывать методы на экземпляре класса можно через точку: (.methodName instance arg1 arg2 ...).
Напишем метод, который будет превращать строку в пос-ть цифр:
(defn to-digit-seq
"Converts string st
to sequence of digits."
[st]
(map #(Character/getNumericValue %) st))
Тут стоит отметить, что к статическим методам и переменным классов джавы можно обращаться через ClassName/methodName.
А теперь основная часть:
(reduce max
(map #(reduce * %)
(partition 5 1 (to-digit-seq number))))
Тут используется забавная ф-ция partition, которая возвращает пос-ть подпоследовательностей данной пос-ти :)
В общем в нашем случае он разбила пос-ть цифр, на пос-ть, элементы которой — группы по 5 цифр, с шагом 1.
Вот пожалуй и всё пока. Напоследок хотел бы дать ссылку на сайтик, в котором собраны решения на кложуре заданий из Эйлера, сам неожиданно для себя наткнулся. Там правда не все, но всё же можно посмотреть какие бывают варианты и поучиться, думаю: http://clojure-euler.wikispaces.com/
