Когда начал изучать F#, то, для усвоения материала, решал задачки с сайта Project Euler.
Потом, ввиду отсутствия времени, как-то забросил решение задачек, а сейчас осваиваю git и в качестве "тренировки на кошках" закинул решенные задачи на GitHub.
Код может быть и не причесанный, от задачи к задачи куски кода могли копипаститься, решения могли быть не оптимальными и т.п.
Может кому-то будет интересно: Project Euler Solutions in F#
Public Clone URL: git://github.com/dimchansky/project-euler-solutions-in-fsharp.git
Пинайте сколько угодно, приемлю любую критику.
Здравствуйте, Димчанский, Вы писали: Д>Пинайте сколько угодно, приемлю любую критику.
Я нисколько не отношусь к ФЯ, стало просто интересно тоже попробовать чё-нить написать...
Задание 4 у меня вроде проще получилось, без строк, с рекурсией, на глаз с такой же скоростью:
let rec dig (v, i) = if i = 0 then v % 10 else dig(v/10, i-1)
let isPoly x =
let rec count (v, n) =
if v < 10 then n
else count (v/10, n+1)
let c = count (x, 0)
Seq.for_all (fun i -> dig(x, i) = dig(x, c-i)) { 0 .. c / 2 }
let problem4 min max =
seq { for i in max .. -1 .. min do
for j in i .. -1 .. min do
yield (i * j) }
|> Seq.filter isPoly
|> Seq.max
Здравствуйте, Пельмешко, Вы писали:
П>Я нисколько не отношусь к ФЯ, стало просто интересно тоже попробовать чё-нить написать... П>Задание 4 у меня вроде проще получилось, без строк, с рекурсией, на глаз с такой же скоростью:
Да, строки там у меня были наверное от лени проверять симметрию через числа, т.к. для строк алгоритм как бы ясен сразу, т.е. с отдельными цифрами и умножением играться не надо было.
Re[2]: Project Euler Solutions in F#
От:
Аноним
Дата:
10.06.09 23:43
Оценка:
Здравствуйте, Пельмешко, Вы писали:
П>Здравствуйте, Димчанский, Вы писали: Д>>Пинайте сколько угодно, приемлю любую критику. П>на глаз с такой же скоростью
Какой-то все ж F# многословный..
isPoli n = fs == reverse fs
where fs = show n
solution n = maximum [i*j | i <- [1..n], j <- [i..n], isPoli i*j]
main = print $ solution 999
Здравствуйте, Димчанский, Вы писали:
Д>Пинайте сколько угодно, приемлю любую критику.
Как бы не критика, но всеж...
Делал эти задачки (к сожалению, не все) на Haskell. Стало интересно, про F# слышал но не видел, а ща предоставился случай взглянуть в сравнении.
Как-то на Haskell решения получались на один-два порядка короче и элегантней, про производительность ничего не скажу, но всеж.
+1 за стремление вааще и за отдельно выложенные решения =)
Мне у них свалка с решениями не понравилась, сложно листать и искать решение на нужном языке.
Здравствуйте, Plague, Вы писали:
P>Делал эти задачки (к сожалению, не все) на Haskell. Стало интересно, про F# слышал но не видел, а ща предоставился случай взглянуть в сравнении. P>Как-то на Haskell решения получались на один-два порядка короче и элегантней, про производительность ничего не скажу, но всеж. P>+1 за стремление вааще и за отдельно выложенные решения =)
Единственное, не забывайте, что решая эти задачи, я только начинал осваивать язык и вообще парадигму функционального программирования, поэтому стоит ожидать, что и я мог решать задачи более многословно. Т.е. вполне возможно, что многие решения можно упростить.
Но сколько довелось самому почитать обучающую литературу по Haskell, то он действительно выглядит менее многословным.
P>Мне у них свалка с решениями не понравилась, сложно листать и искать решение на нужном языке.
Да, согласен, свалку решений можно было бы и как-то систематизировать по языкам.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Пельмешко, Вы писали:
П>>Здравствуйте, Димчанский, Вы писали: Д>>>Пинайте сколько угодно, приемлю любую критику. П>>на глаз с такой же скоростью А>Какой-то все ж F# многословный.. А>
А>isPoli n = fs == reverse fs
А> where fs = show n
А>solution n = maximum [i*j | i <- [1..n], j <- [i..n], isPoli i*j]
А>main = print $ solution 999
А>
Человек же сказал, что только учился F# (я тоже этим сейчас занят )
В F# можно несколько короче изначального варианта (хотя я не претендую на самый краткий вариант):
let filter s = List.rev (Seq.to_list s) = (Seq.to_list s)
printfn "%d" ((seq { for i in [100 * 100..999 * 999] do if filter (i.ToString()) then yield i }) |> Seq.fold(max) 0)
У тебя, кстати, если я правильно понял, анализируются не произведение 3-значных чисел, а произведения всех чисел от 1 до 999
Глянул еще первое задание, этот код:
let naturalNumbersBelow limit = {1..limit-1}
let naturalMultiplesOf3Or5Below limit = naturalNumbersBelow limit |> Seq.filter(fun v -> v % 3 = 0 || v % 5 = 0)
let sumOfAllTheMultiplesOf3Or5Below limit = naturalMultiplesOf3Or5Below limit |> Seq.fold (fun a b -> a + b) 0
let sumOfAllTheMultiplesOf3Or5Below1000 = sumOfAllTheMultiplesOf3Or5Below 1000
print_any sumOfAllTheMultiplesOf3Or5Below1000
Меня тоже можно пинать, ибо тоже только учусь функциональщине и F# в частности
Luck in life always exists in the form of an abstract class that cannot be instantiated directly and needs to be inherited by hard work and dedication.
Здравствуйте, yuriylsh, Вы писали:
Y>Человек же сказал, что только учился F# (я тоже этим сейчас занят )
Так у меня меня никаких претензий к человеку и не было. Была только легкая критика самого языка F#, который мне кажется более многословным нежели тот же Хаскель.
А так я и сам, в свое время, изучал язык на задачах ProjectEuler (правда то был J) вот даже пример моего решения (нашел в своем "архиве") той же задачи:
2 года назад было так:
Y>В F# можно несколько короче изначального варианта (хотя я не претендую на самый краткий вариант): Y>
Y>let filter s = List.rev (Seq.to_list s) = (Seq.to_list s)
Y>printfn "%d" ((seq { for i in [100 * 100..999 * 999] do if filter (i.ToString()) then yield i }) |> Seq.fold(max) 0)
Y>
Только тут ошибка — тестируются не произведения пары трехзначных чисел, а все числа от 100*100 до 999*999 что приводит к неправильному результату.
Можно конечно и на F# написать покороче с более-менее приемлимой производительностью... например вот так:
printfn "%A" <| Seq.max (seq{
for i in 10 .. 999 do
for j in i .. 999 do
let ps = (i*j).ToString().ToCharArray()
if Array.forall2 (=) ps (Array.rev ps) then yield i*j }
(хоть тут и создается дополнительный (реверсированный) массив)
Но штука в том, что на Хаскеле можно записать и вот так, в одну строку (почти что в ровень с J):
maximum [p | i <- [100..999], j <- [i..999], let (p,ps) = (i*j,show p), ps == reverse ps]
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, yuriylsh, Вы писали:
Y>>Человек же сказал, что только учился F# (я тоже этим сейчас занят )
А>Так у меня меня никаких претензий к человеку и не было.
Да и у меня претнзий к тебе небыло
А>Была только легкая критика самого языка F#, который мне кажется более многословным нежели тот же Хаскель.
Наверное он более многолсовен, тебе видней — я Хаскела не знаю Судя по примеру — да, компактней. Хотя мне после С# (а в прошлой жизни C++) кажется вполне такой компактенький Следует оговориться, что до ООП в F# я еще не дошел, чтобы цельную картину иметь для сравнения
А>А так я и сам, в свое время, изучал язык на задачах ProjectEuler (правда то был J) вот даже пример моего решения (нашел в своем "архиве") той же задачи: А>2 года назад было так: А>
Y>>В F# можно несколько короче изначального варианта (хотя я не претендую на самый краткий вариант): Y>>
Y>>let filter s = List.rev (Seq.to_list s) = (Seq.to_list s)
Y>>printfn "%d" ((seq { for i in [100 * 100..999 * 999] do if filter (i.ToString()) then yield i }) |> Seq.fold(max) 0)
Y>>
А>Только тут ошибка — тестируются не произведения пары трехзначных чисел, а все числа от 100*100 до 999*999 что приводит к неправильному результату.
Точно, в погоне за краткостью и сам не выдержал условия...
А>Можно конечно и на F# написать покороче с более-менее приемлимой производительностью... например вот так: А>
А>printfn "%A" <| Seq.max (seq{
А> for i in 10 .. 999 do
А> for j in i .. 999 do
А> let ps = (i*j).ToString().ToCharArray()
А> if Array.forall2 (=) ps (Array.rev ps) then yield i*j }
А>
А>(хоть тут и создается дополнительный (реверсированный) массив)
+1
А>Но штука в том, что на Хаскеле можно записать и вот так, в одну строку (почти что в ровень с J): А>
А>maximum [p | i <- [100..999], j <- [i..999], let (p,ps) = (i*j,show p), ps == reverse ps]
А>
Компактненько
Luck in life always exists in the form of an abstract class that cannot be instantiated directly and needs to be inherited by hard work and dedication.
Luck in life always exists in the form of an abstract class that cannot be instantiated directly and needs to be inherited by hard work and dedication.
Здравствуйте, Аноним, Вы писали:
А>Ну без пробелов-то одинаково получается — по 28 символов: А>
>>./(#~(-:|.&.":)"0),*/~i.999
А>
И я в пипкомер!
>./(*(-:|.)@":"0),*/~i.1e3
26 символов. Помедленнее работает, конечно. Писал сам ) учу вот J на днях, использую Project Euler, который когда-то прорешивал на Nemerle.
А>только код какой-то нечитабельный выходит..
Ага.
[офф]
Кстати, я недавно думал о читабельности J/K. Проблема в том, что его сложно декомпозировать в мозгу в тот вид, в котором алгоритм воспринимается. Но языки, в которых получается много букав, транслировать в мозг тоже непросто, потому что сложнее объять весь код. Так что тут ... не факт, что J всегда в проигрыше в плане читабельности.
[/офф]
Ну раз вы так... 25 символов без потери производительности:
>./,(*(-:|.)@":)@*/~i.1e3
O>[офф] O>Кстати, я недавно думал о читабельности J/K. Проблема в том, что его сложно декомпозировать в мозгу в тот вид, в котором алгоритм воспринимается. O>[/офф]
Говорят, что нужно менять мышление и тогда все будет шоколадно:
A contributor to the J forum recently made the point that for J aficionados, J phrases can become a more natural medium for expressing ideas than any natural language equivalent.
Здравствуйте, Oyster, Вы писали:
O>Здравствуйте, Димчанский, Вы писали: O>Интересно. Когда-то делал похоже — решал их же, но на Nemerle. Если есть интерес общественности, готов потратить время и выложить.
Интерес есть, хотелось бы сравнить с F#, выложите, пожалуйста, если будет время, буду очень рад
Здравствуйте, Димчанский, Вы писали: Д>Пинайте сколько угодно, приемлю любую критику.
Ни в коем случае не пинание,
просто сравню Ваш и мой вариант решения задания #30...
let powerValue = 5I
let answer =
let maxValue d = (pow 10I d) - 1I
let maxDigits =
{for d in 1I..10I -> (d, maxValue d, d * pow 9I powerValue)} |>
Seq.first (fun (d, value, sum) ->
if value > sum then Some(d) else None) |> Option.get
{10I .. maxValue maxDigits} |> Seq.filter (fun v ->
v = (v.ToString() |>
Seq.map (fun d -> int(d)-int('0')) |>
Seq.map (fun d -> pow (bigint.FromInt32(d)) powerValue) |>
Seq.fold (+) 0I)) |>
Seq.fold (+) 0I
print_any answer
Ещё задаче к 20ой мозг начал отвергать seq<a'> + ФВП в пользу божественной рекурсии
Быстрее гораздо, вроде даже лаконичнее получилось и без bigint обошёлся...
Вот мой вариант:
let solve n =
let pows = [| for i in 0 .. 9 -> pown i n |]
let list = new ResizeArray<int>()
let rec test i x s =
let rec loop j =
if j < pows.Length then test (i+1) (10*x+j) (s+pows.[j]); loop (j+1)
if i <= n then loop 0
elif x = s && s > 1 then list.Add(s);
test 0 0 0; list |> Seq.sum
printfn "problem30 = %d" (solve 5)
Тут можно без списка, тем более мутабельного, просто хотелось глянуть на результаты побыстрее...
Здравствуйте, Пельмешко, Вы писали:
П>Тут можно без списка, тем более мутабельного, просто хотелось глянуть на результаты побыстрее...
Побыстрее???
Брут-форсом даже без кэширования степеней цифр считается меньше 2х секунд
let digits =
let rec digs l = function 0 -> list | x -> digs (x % 10::l) (x/10)
digs List.empty
let test y n =
let sum = digits n |> List.map (fun x -> pown x y) |> List.sum
n = sum
seq { 2..1000000 } |> Seq.filter (test 5) |> Seq.sum |> printfn "%d"
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Пельмешко, Вы писали: П>>Тут можно без списка, тем более мутабельного, просто хотелось глянуть на результаты побыстрее...
S>Побыстрее??? S>Брут-форсом даже без кэширования степеней цифр считается меньше 2х секунд
Вы меня не так поняли, я не про производительность моего решения говорил, просто криво выразился.
Мне надо было быстрее увидеть ("глянуть") какие числа попадают под отбор чтобы убедиться в правильности,
поэтому я воспользовался List<T>, а не по-честному в рекурсии собрал list или seq, это я и объяснил последним предложением.
А насчёт производительности — посмотрите сколько выполняется вариант топикстартера.