F#, Project Euler - Problem #4 (2)

내 생산물 2009/05/22 11:03


 Project Euler를 F#으로 푸는 작업은 계속 틈나는 대로 하고 있는데..
 안그래도 구독자가 별로 없는 블로그에 계속 그것만 올리면..
 구독자들에게 짜증을 줄까봐 자제하고 있습니다.ㅋ


 아무튼 Neon군이 리플로 제안한 방식으로 구현해보았습니다.
 일단 기존 방식은 무식하게 세자리 숫자의 곱을 모두 계산 하는 방식이었는데
 새로운 방식은 세자리 숫자의 곱 중에서 큰 수 순서대로 숫자를 뽑습니다.
 그리고, (123 * 312) 과 (312 * 123)은 같은 값이기 때문에 한번만 계산 합니다.


set [ (999*999, 999, 999) ]

    |> Seq.unfold (fun pq ->

        let head = pq.MaximumElement

        let product, a, b = head

        let newElements =

            set [ ((a-1)*b, a-1, b); (a*(b-1), a, b-1) ]

                |> Set.filter (fun (_, a, b) -> a <= b)

        Some (product, ((pq.Remove head) + newElements)))

    |> Seq.filter is_parlindrome

    |> Seq.hd

    |> printfn "Problem #4 = %d"



Priority Queue 구현에서 일반적으로 사용되는 Heap를 사용하는 것이 가장 좋아 보이지만...
F#에서 쓰기 쉬운 Set (Binary Tree) 기반으로 구현 하였습니다.




'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #4 (2)  (0) 2009/05/22
F#, Project Euler - Problem #12  (0) 2009/05/12
F#, Project Euler - Problem #20  (0) 2009/05/12
F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
Posted by U_Seung
TAG F#, FSharp, Problem4, project euler
트랙백 0개, 댓글 0개가 달렸습니다.

F#, Project Euler - Problem #12

내 생산물 2009/05/12 13:58

Problem #12. What is the value of the first triangle number to have over five hundred divisors?

번역: 500개가 넘는 (양의) 약수를 가진 첫번째 triangle number는 ?

먼저 triangle number의 수열은 아래와 같이 구할 수 있다.

Version1. 정의에 가까운 가장 직관적인 방식..

let triangle_numbers =

    let rec triangle_number =

        function 0 -> 1 | n -> (n + 1 + triangle_number (n-1))

    Seq.init_infinite triangle_number



Version 2. Recursive call을 제거..

let triangle_numbers = Seq.unfold (fun (n, i) -> Some(n, (n+i, i+1))) (1, 2)



Version 3. 최적화.

let triangle_numbers = Seq.init_infinite (fun n -> (n+2)*(n+1) / 2)



triangle number의 수열을 구했으니 답을 구하면..

let factorize n =

    let rec factorize_horse n factor count result =

        if (n <= 1) then

            count::result

        else

            match (n % factor) with

            | 0 -> (factorize_horse (n/factor) factor (count+1) result)

            | _ -> (factorize_horse n (factor+1) 0 (count::result))          

    factorize_horse n 2 0 []

        |> List.filter (fun x -> x<>0)

 

let factor_count n =

    factorize n

        |> List.map (fun x -> x+1 )

        |> List.fold_left (*) 1

 

triangle_numbers

    |> Seq.filter (fun x -> 500 < (factor_count x))

    |> Seq.hd

    |> printfn "Problem #12 = %d"



약수의 개수를 빨리 구하려고, 소인수 분해를 하였다.
약수 개수를 구하기 위해 모든 약수가 무엇인지 다 파악한다면..
얼마나 느릴지는 장담할 수 없음. ㅋ



'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #4 (2)  (0) 2009/05/22
F#, Project Euler - Problem #12  (0) 2009/05/12
F#, Project Euler - Problem #20  (0) 2009/05/12
F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
Posted by U_Seung
TAG F#, FSharp, project euler
트랙백 0개, 댓글 0개가 달렸습니다.

F#, Project Euler - Problem #20

내 생산물 2009/05/12 13:42

Problem #20. Find the sum of the digits in the number 100!

번역: 100! 값의 모든 자릿수의 합을 구하시오.


 여러가지 방법이 있을 수 있지만.
 가장 직관적인 방법은 계산해서 더하면 된다.


open Microsoft.FSharp.Math

 

(BigInt.Factorial (BigInt 100)).ToString()

    |> Seq.map (fun x -> (int x) - (int '0'))

    |> Seq.sum

    |> printfn "Problem #20 = %d"






'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #4 (2)  (0) 2009/05/22
F#, Project Euler - Problem #12  (0) 2009/05/12
F#, Project Euler - Problem #20  (0) 2009/05/12
F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
Posted by U_Seung
TAG F#, FSharp, project euler
트랙백 0개, 댓글 0개가 달렸습니다.

F#, Project Euler - Problem #5

내 생산물 2009/05/11 10:35

#Problem 5. What is the smallest number that is evenly divisible by all of the numbers from 1 to 20?

번역: 1부터 20까지 수로 모두 나누어 떨어지는 수 중 가장 작은 수는?


뭐 복잡하게 설명할 것 없이
최소공배수(LCM, Lowest Common Multiple)를 구하는 문제다.
Result = (lcm ...... (lcm (lcm 1 2) 3) 4) ... 20)


let lcm x y =

    let rec gcd x y =

        match y with

        | 0 -> x

        | _ -> (gcd y (x%y))

    x * (y / (gcd x y))

 

{1 .. 20}

    |> Seq.fold lcm 1

    |> printfn "Problem #5 = %d"




조금 어려운 문제로 번호를 넘겨야 할 듯...

'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #4 (2)  (0) 2009/05/22
F#, Project Euler - Problem #12  (0) 2009/05/12
F#, Project Euler - Problem #20  (0) 2009/05/12
F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
Posted by U_Seung
TAG F#, FSharp, project euler
트랙백 0개, 댓글 0개가 달렸습니다.

F#, Project Euler - Problem #4

내 생산물 2009/05/11 10:25


해석: 두 개의 세자리 숫자를 곱해서 만들 수 있는 가장 큰 palindrome을 만드시오.


 직관적으로..
 - 모든 세자리 숫자의 조합을 만들어서 이를 곱한다.
 - 이 값이 Palindrome 이지 검사한다.
 - Palindrome 중 가장 큰 숫자를 추출한다.

#light

 

let is_parlindrome x =

    let rec reverse y result =

        match y with

        | 0 -> result

        | _ -> (reverse (y/10) (result*10 + y%10))

    (reverse x 0) = x

 

[ for i in [100 .. 999] do

        for j in [100 .. 999] do

            yield i*j ]

    |> List.filter is_parlindrome

    |> Seq.max

    |> printfn "Problem #4 = %d"





'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #12  (0) 2009/05/12
F#, Project Euler - Problem #20  (0) 2009/05/12
F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
F#, Project Euler - Problem #2  (0) 2009/05/10
Posted by U_Seung
TAG F#, FSharp, palindrome, project euler
트랙백 0개, 댓글 2개가 달렸습니다

F#, Project Euler - Problem #3

내 생산물 2009/05/10 19:40
Problem3. What is the largest prime factor of the number 600851475143 ?

번역: 600851475143 를 나누었을 때, 나누어 떨어지는 수 중 가장 큰 소수(Prime number)는 ?


 직관적으로 풀면...
 해당 숫자의 제곱근 부터 차례로 1씩 감소 하면서..
 해당 숫자를 나눌 수 있는지..
 소수인지 확인하면 됩니다.


 주어진 숫자가 좀 커서 int 범위로 포함진 않습니다.
 다행이 제곱근은 int 범위에 있습니다.

#light

 

let target_number = 600851475143UL;

let max_candidate = (int (sqrt (float target_number)))

 

let is_prime i =

    [2 .. i-1]

    |> Seq.exists (fun x -> i%x = 0)

    |> not

 

let is_factor_of x =

    target_number%(uint64 x) = 0UL

 

[max_candidate .. -1 .. 2]

    |> Seq.filter is_factor_of

    |> Seq.filter is_prime

    |> Seq.hd

    |> printfn "Problem #3 = %d"



가장 큰 수부터 검사하기 때문에 head를 찍으면 됩니다.

참고로... is_factor_of 와 is_prime 의 줄을 바꾸면
Performance 는 끔찍해집니다.

-----------------

좀 비 직관적이지만...

let rec find_last_prime_factor (n: uint64) (i: uint64) (result: uint64) =

    if (n <= 1UL) then

        result

    else

        if (n % i = 0UL) then

            (find_last_prime_factor (n/i) i i)

        else

            (find_last_prime_factor n (i+1UL) result)

 

find_last_prime_factor target_number 2UL 0UL

    |> printfn "Problem #3 = %d"



이렇게 풀 수도 있습니다.


'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #20  (0) 2009/05/12
F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
F#, Project Euler - Problem #2  (0) 2009/05/10
테터 데스크 설치 - 미투데이 최근글 표시하기.  (2) 2007/06/11
Posted by U_Seung
TAG F#, FSharp, problem, project euler
트랙백 0개, 댓글 0개가 달렸습니다.

F#, Project Euler - Problem #1

내 생산물 2009/05/10 19:25
참조: Project Euler


 요즘 지루함을 달래기 위해서 함수형 언어인 F#을 공부해보고 있습니다.
 특별한 목표가 없으면 잘 안되기 때문에..
 Project Euler(오일러)의 문제들도 같이 풀어 보고 있습니다.


Problem #1. Add all the natural numbers below one thousand that are multiples of 3 or 5.

매우 간단한 문제라서...
설명하는게 무의미 할 것 같습니다.

세 가지 버전을 만들어 보았습니다.

#light

 

let p1_1 = (Seq.sum (Seq.filter (fun x -> (x%3) * (x%5) = 0) [1 .. 999]))

printfn "Problem #1 = %d" p1_1

 

let p1_2 = [1 .. 999] |> Seq.filter (fun x -> (x%3) * (x%5) = 0) |> Seq.sum

printfn "Problem #1 = %d" p1_2

 

let p1_3 = (Seq.sum [for i in 1..999 do if (i%3 * i%5) = 0 then yield i])

printfn "Problem #1 = %d" p1_3


개인적으로는 두번째 스타일을 가장 좋아 합니다.






'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #5  (0) 2009/05/11
F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
F#, Project Euler - Problem #2  (0) 2009/05/10
테터 데스크 설치 - 미투데이 최근글 표시하기.  (2) 2007/06/11
Popfly로 만든 축제 자료집  (6) 2007/06/06
Posted by U_Seung
TAG F#, FSharp, project euler
트랙백 0개, 댓글 2개가 달렸습니다

F#, Project Euler - Problem #2

내 생산물 2009/05/10 17:30

변역: 피보나치 수열 중 4000만이 넘지 않은 짝수의 합을 구하시오.


 문제를 보는 순간 헉...
 예전에 다른 언어 열심히 풀어본 문제랑 너무 비슷하다는거...



 일단 답을 빨리 구해보려고, 이전 python소스를 약간 고쳐서 만들었다.

from itertools import *

def fibs():
    yield 1;
    yield 1;
    h, t = tee(fibs())
    t.next()
    for i in imap(lambda (a,b):a+b, izip(h, t)):
            yield i

print sum(takewhile(lambda x: x<=4000000, ifilter(lambda x: x%2==0, fibs())))

결과가 매우 잘 나왔다.
개인적으로 이런 스타일이 좋아서 ...
이와 비슷한 fibs() 코드를 F#으로 만들 방법을 찾았다.


let rec fibs = seq { yield! [1; 1]; for (x, y) in Seq.zip fibs (Seq.skip 1 fibs) -> x + y}

 

printfn "Problem #2 = %d" (fibs

    |> Seq.take_while (fun x -> x <= 4000000)

    |> Seq.filter (fun x -> x%2 = 0)

    |> Seq.sum) ;;


위 Python 코드와 크게 다를게 없는 코드다.
문제는 답은 나올 거 같은데 1000만년이 걸릴 것 같다는 ;;;;



어쩔 수 없이 fibs 함수를 수정할 수 밖에 없었다.

let fibs = (1,1) |> Seq.unfold (fun (a, b) -> Some(a, (b, a+b)))

 

printfn "Problem #2 = %d" (fibs

    |> Seq.take_while (fun x -> x <= 4000000)

    |> Seq.filter (fun x -> x%2 = 0)

    |> Seq.sum) ;;





뭐.. 속편하게 만드는 방법은... 
아래와 같이 Iterative하게 만드는 방법도 있다.

let rec even_fibs_sum a b sum =

    if (a <= 4000000) then

        (even_fibs_sum b (a+b) (sum+a-(a%2)*a))

    else

        sum

 

printfn "Problem #2 = %d" (even_fibs_sum 1 1 0)





'내 생산물' 카테고리의 다른 글

F#, Project Euler - Problem #4  (2) 2009/05/11
F#, Project Euler - Problem #3  (0) 2009/05/10
F#, Project Euler - Problem #1  (2) 2009/05/10
F#, Project Euler - Problem #2  (0) 2009/05/10
테터 데스크 설치 - 미투데이 최근글 표시하기.  (2) 2007/06/11
Popfly로 만든 축제 자료집  (6) 2007/06/06
Silverlight에서 한글 쉽고, 가볍게 사용하기  (13) 2007/05/23
Posted by U_Seung
TAG F#, FSharp, project euler
트랙백 0개, 댓글 0개가 달렸습니다.