Project Euler Solutions in F#
От: Димчанский Литва http://dimchansky.github.io/
Дата: 03.06.09 19:29
Оценка: 14 (2)
Когда начал изучать F#, то, для усвоения материала, решал задачки с сайта Project Euler.
Потом, ввиду отсутствия времени, как-то забросил решение задачек, а сейчас осваиваю git и в качестве "тренировки на кошках" закинул решенные задачи на GitHub.
Код может быть и не причесанный, от задачи к задачи куски кода могли копипаститься, решения могли быть не оптимальными и т.п.
Может кому-то будет интересно:
Project Euler Solutions in F#
Public Clone URL: git://github.com/dimchansky/project-euler-solutions-in-fsharp.git
Пинайте сколько угодно, приемлю любую критику.
Re: Project Euler Solutions in F#
От: Пельмешко Россия blog
Дата: 05.06.09 13:40
Оценка: :)
Здравствуйте, Димчанский, Вы писали:
Д>Пинайте сколько угодно, приемлю любую критику.

Я нисколько не отношусь к ФЯ, стало просто интересно тоже попробовать чё-нить написать...
Задание 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
Re[2]: Project Euler Solutions in F#
От: Димчанский Литва http://dimchansky.github.io/
Дата: 05.06.09 14:43
Оценка:
Здравствуйте, Пельмешко, Вы писали:

П>Я нисколько не отношусь к ФЯ, стало просто интересно тоже попробовать чё-нить написать...

П>Задание 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
Re: Project Euler Solutions in F#
От: Plague Россия  
Дата: 11.06.09 07:53
Оценка:
Здравствуйте, Димчанский, Вы писали:

Д>Пинайте сколько угодно, приемлю любую критику.


Как бы не критика, но всеж...

Делал эти задачки (к сожалению, не все) на Haskell. Стало интересно, про F# слышал но не видел, а ща предоставился случай взглянуть в сравнении.
Как-то на Haskell решения получались на один-два порядка короче и элегантней, про производительность ничего не скажу, но всеж.
+1 за стремление вааще и за отдельно выложенные решения =)

Мне у них свалка с решениями не понравилась, сложно листать и искать решение на нужном языке.
Re[2]: Project Euler Solutions in F#
От: Димчанский Литва http://dimchansky.github.io/
Дата: 11.06.09 08:04
Оценка:
Здравствуйте, Plague, Вы писали:

P>Делал эти задачки (к сожалению, не все) на Haskell. Стало интересно, про F# слышал но не видел, а ща предоставился случай взглянуть в сравнении.

P>Как-то на Haskell решения получались на один-два порядка короче и элегантней, про производительность ничего не скажу, но всеж.
P>+1 за стремление вааще и за отдельно выложенные решения =)

Единственное, не забывайте, что решая эти задачи, я только начинал осваивать язык и вообще парадигму функционального программирования, поэтому стоит ожидать, что и я мог решать задачи более многословно. Т.е. вполне возможно, что многие решения можно упростить.
Но сколько довелось самому почитать обучающую литературу по Haskell, то он действительно выглядит менее многословным.

P>Мне у них свалка с решениями не понравилась, сложно листать и искать решение на нужном языке.


Да, согласен, свалку решений можно было бы и как-то систематизировать по языкам.
Re[3]: Project Euler Solutions in F#
От: Аноним  
Дата: 11.06.09 09:52
Оценка: 3 (1) +1 :)))
Здравствуйте, Аноним, Вы писали:

А>Какой-то все ж F# многословный..

Да впрочем и Хаскель тоже..
>./ (#~ (-:|.&.":)"0) , */~ i.999
Re[4]: Project Euler Solutions in F#
От: Quintanar Россия  
Дата: 11.06.09 15:39
Оценка: 3 (1)
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Аноним, Вы писали:


А>>Какой-то все ж F# многословный..

А>Да впрочем и Хаскель тоже..
А>
>./ (#~ (-:|.&.":)"0) , */~ i.999


Больно много писанины

|/x@&x=0$|:'$x:,/x*/:x:!1000
Re[5]: Project Euler Solutions in F#
От: Аноним  
Дата: 11.06.09 15:53
Оценка:
Здравствуйте, Quintanar, Вы писали:

Q>Больно много писанины

Q>
Q>|/x@&x=0$|:'$x:,/x*/:x:!1000
Q>


Ну без пробелов-то одинаково получается — по 28 символов:
>./(#~(-:|.&.":)"0),*/~i.999

только код какой-то нечитабельный выходит..
Re[3]: Project Euler Solutions in F#
От: yuriylsh  
Дата: 14.06.09 03:10
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, Пельмешко, Вы писали:


П>>Здравствуйте, Димчанский, Вы писали:

Д>>>Пинайте сколько угодно, приемлю любую критику.
П>>на глаз с такой же скоростью
А>Какой-то все ж 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

можно плавно превратить в такой:

printfn "%d" ([1 .. 3 .. 999] @ [1 .. 5 .. 999]  |> Seq.fold (+) 0 )


Меня тоже можно пинать, ибо тоже только учусь функциональщине и 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.
Re[4]: Project Euler Solutions in F#
От: Аноним  
Дата: 14.06.09 13:14
Оценка: 3 (1)
Здравствуйте, yuriylsh, Вы писали:

Y>Человек же сказал, что только учился F# (я тоже этим сейчас занят )


Так у меня меня никаких претензий к человеку и не было. Была только легкая критика самого языка F#, который мне кажется более многословным нежели тот же Хаскель.
А так я и сам, в свое время, изучал язык на задачах ProjectEuler (правда то был J) вот даже пример моего решения (нашел в своем "архиве") той же задачи:
2 года назад было так:
>./,(0:`([*])@.((-:|.)@:":@*))"0/~ (+(i.@(1000&-))) 100

Сейчас бы было так:
>./ , (* (-:|.)@":)@*/~ 100+i.900

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]
Re[5]: Project Euler Solutions in F#
От: yuriylsh  
Дата: 14.06.09 15:58
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, yuriylsh, Вы писали:


Y>>Человек же сказал, что только учился F# (я тоже этим сейчас занят )


А>Так у меня меня никаких претензий к человеку и не было.


Да и у меня претнзий к тебе небыло

А>Была только легкая критика самого языка F#, который мне кажется более многословным нежели тот же Хаскель.


Наверное он более многолсовен, тебе видней — я Хаскела не знаю Судя по примеру — да, компактней. Хотя мне после С# (а в прошлой жизни C++) кажется вполне такой компактенький Следует оговориться, что до ООП в F# я еще не дошел, чтобы цельную картину иметь для сравнения

А>А так я и сам, в свое время, изучал язык на задачах ProjectEuler (правда то был J) вот даже пример моего решения (нашел в своем "архиве") той же задачи:

А>2 года назад было так:
А>
>>./,(0:`([*])@.((-:|.)@:":@*))"0/~ (+(i.@(1000&-))) 100
А>

А>Сейчас бы было так:
А>
>>./ , (* (-:|.)@":)@*/~ 100+i.900
А>

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.
Re[4]: Project Euler Solutions in F#
От: samius Япония http://sams-tricks.blogspot.com
Дата: 15.06.09 18:49
Оценка: +1
Здравствуйте, yuriylsh, Вы писали:

Y>Глянул еще первое задание, этот код:


Y>
Y>let naturalNumbersBelow limit = {1..limit-1}
Y>let naturalMultiplesOf3Or5Below limit = naturalNumbersBelow limit |> Seq.filter(fun v -> v % 3 = 0 || v % 5 = 0)
Y>let sumOfAllTheMultiplesOf3Or5Below limit = naturalMultiplesOf3Or5Below limit |> Seq.fold (fun a b -> a + b) 0
Y>let sumOfAllTheMultiplesOf3Or5Below1000 = sumOfAllTheMultiplesOf3Or5Below 1000
Y>print_any sumOfAllTheMultiplesOf3Or5Below1000
Y>

Y>можно плавно превратить в такой:

Y>
Y>printfn "%d" ([1 .. 3 .. 999] @ [1 .. 5 .. 999]  |> Seq.fold (+) 0 )
Y>

Можно-то можно. Ответ совпал?
З.ы. Есть еще такой метод специальный sum, чтобы fold (+) 0 не писать
Re[5]: Project Euler Solutions in F#
От: yuriylsh  
Дата: 15.06.09 19:46
Оценка: +1
Здравствуйте, samius, Вы писали:

Y>>
Y>>printfn "%d" ([1 .. 3 .. 999] @ [1 .. 5 .. 999]  |> Seq.fold (+) 0 )
Y>>

S>Можно-то можно. Ответ совпал?
S>З.ы. Есть еще такой метод специальный sum, чтобы fold (+) 0 не писать

Согласен, должно было быть так:

printfn "%d" ([0 .. 3 .. 999] @ [0 .. 5 .. 999]  |> Seq.fold (+) ([0 .. 15 .. 999] |> Seq.fold (-) 0))


Ну или так:

printfn "%d" (([0 .. 3 .. 999] @ [0 .. 5 .. 999]  |> Seq.sum) -  ([0 .. 15 .. 999] |> Seq.sum))
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.
Re[6]: Project Euler Solutions in F#
От: Oyster Украина https://github.com/devoyster
Дата: 25.06.09 09:35
Оценка:
Здравствуйте, Аноним, Вы писали:

А>Ну без пробелов-то одинаково получается — по 28 символов:

А>
>>./(#~(-:|.&.":)"0),*/~i.999
А>

И я в пипкомер!

>./(*(-:|.)@":"0),*/~i.1e3

26 символов. Помедленнее работает, конечно. Писал сам ) учу вот J на днях, использую Project Euler, который когда-то прорешивал на Nemerle.

А>только код какой-то нечитабельный выходит..


Ага.

[офф]
Кстати, я недавно думал о читабельности J/K. Проблема в том, что его сложно декомпозировать в мозгу в тот вид, в котором алгоритм воспринимается. Но языки, в которых получается много букав, транслировать в мозг тоже непросто, потому что сложнее объять весь код. Так что тут ... не факт, что J всегда в проигрыше в плане читабельности.
[/офф]
Re: Project Euler Solutions in F#
От: Oyster Украина https://github.com/devoyster
Дата: 25.06.09 10:33
Оценка:
Здравствуйте, Димчанский, Вы писали:

Д>Когда начал изучать F#, то, для усвоения материала, решал задачки с сайта Project Euler.


Интересно. Когда-то делал похоже — решал их же, но на Nemerle. Если есть интерес общественности, готов потратить время и выложить.
Re[7]: Project Euler Solutions in F#
От: Аноним  
Дата: 25.06.09 10:41
Оценка: 1 (1)
Здравствуйте, Oyster, Вы писали:

А>>
>>>./(#~(-:|.&.":)"0),*/~i.999
А>>

O>И я в пипкомер!

Ну раз вы так... 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.

Re[2]: Project Euler Solutions in F#
От: Пельмешко Россия blog
Дата: 27.06.09 15:42
Оценка:
Здравствуйте, 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)

Тут можно без списка, тем более мутабельного, просто хотелось глянуть на результаты побыстрее...
Re[3]: Project Euler Solutions in F#
От: samius Япония http://sams-tricks.blogspot.com
Дата: 27.06.09 18:36
Оценка:
Здравствуйте, Пельмешко, Вы писали:

П>Тут можно без списка, тем более мутабельного, просто хотелось глянуть на результаты побыстрее...


Побыстрее???
Брут-форсом даже без кэширования степеней цифр считается меньше 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"
Re[4]: Project Euler Solutions in F#
От: Пельмешко Россия blog
Дата: 27.06.09 19:14
Оценка:
Здравствуйте, samius, Вы писали:

S>Здравствуйте, Пельмешко, Вы писали:

П>>Тут можно без списка, тем более мутабельного, просто хотелось глянуть на результаты побыстрее...

S>Побыстрее???

S>Брут-форсом даже без кэширования степеней цифр считается меньше 2х секунд

Вы меня не так поняли, я не про производительность моего решения говорил, просто криво выразился.
Мне надо было быстрее увидеть ("глянуть") какие числа попадают под отбор чтобы убедиться в правильности,
поэтому я воспользовался List<T>, а не по-честному в рекурсии собрал list или seq, это я и объяснил последним предложением.

А насчёт производительности — посмотрите сколько выполняется вариант топикстартера.
Re[3]: Project Euler Solutions in F#
От: samius Япония http://sams-tricks.blogspot.com
Дата: 27.06.09 21:00
Оценка:
Здравствуйте, Пельмешко, Вы писали:

П>Вот мой вариант:

П>
П>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
П>


let solve2 p =
    let digits = [0..9]
    let pows = [| for i in 0 .. 9 -> pown i p |]
    
    let rec loop n c ds sum =
        if c > p then 
            if n = ds then 
                printfn "%d" n
                sum + n 
            else sum
        else
            digits |> List.fold (fun s d -> loop (n*10 + d) (c+1) (ds + pows.[d]) s) sum
    loop 0 0 0 -1

Мой вариант Вашего варианта (работает немного дольше), но менее запутанный.
Re[4]: Project Euler Solutions in F#
От: samius Япония http://sams-tricks.blogspot.com
Дата: 27.06.09 21:32
Оценка:
Здравствуйте, samius, Вы писали:

По случаю хочу поинтересоваться у знатаков вот по какому вопросу

В этом коде

S>
S>let solve2 p =
S>    let digits = [0..9]
S>    ...
S>    digits |> List.fold (fun s d -> loop (n*10 + d) (c+1) (ds + pows.[d]) s) sum
S>


список цифр нужен только для того, чтобы сделать по нему fold. Но этот список легко генерируется.
можно было бы это все переписать в

state1 |> Seq.unfold (fun ...) |> Seq.fold (fun ...) state2

вот их сингатуры
val unfold : ('State -> ('T * 'State) option) -> 'State -> seq<'T>
val fold : ('State -> 'T -> 'State) -> 'State -> seq<'T> -> 'T

А теперь хочется чего-то нехорошего. Хочется какой-то метод, который бы делал unfold и fold сразу. Брать какое-то состояние, метод его обработки, и крутить состояние в методе, но возвращать не последовательность значений, а результирующее состояние.

val ??? : ('State -> 'State option) 'State -> 'State

Быть может есть такой метод, а я его просто еще не открыл для себя?
Re: Project Euler Solutions in Nemerle
От: Oyster Украина https://github.com/devoyster
Дата: 02.07.09 13:14
Оценка: 22 (2)
Как писал выше, даю ссылку на мои решения задач с Project Euler (задачи с 1 по 89 включительно) на языке Nemerle: http://code.google.com/p/projecteuler-solutions-in-nemerle/source/browse/#svn/trunk/ProjectEuler/Tasks.

Несколько комментариев к выложенному мной коду:


Надеюсь, кому-то будет полезно и интересно.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.