-
Notifications
You must be signed in to change notification settings - Fork 5
programming clojure project euler
ohyecloudy edited this page Apr 28, 2013
·
1 revision
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
(reduce + (filter #(or (= 0 (rem % 3)) (= 0 (rem % 5))) (range 1 1000)))Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.
>>피보나치 수열에서 400백만 이하의 모든 짝수들을 합한 결과는?
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
(take-while (filter #(<= % 20) (fibo)))(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
( reduce + (for [n (fibo) :while (> 4000000 n) :when (even? n)] n))(def fibo-seq (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
(reduce +
(filter even?
(take-while (fn [n] (< n 4000000)) fibo-seq)))(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
(reduce + (filter even? (take-while #(>= 4000000 %) (fibo)))); 피보나치 수열 구하는 공식
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
; 4백만 이하의 피보나치 수열 집합
(defn under-4m [] (take-while #(< % 4000000) (fibo)))
; 4백만 이하의 짝수
(defn geteven [] (filter even? (under-4m)))
; 짝수들의 합
(defn addeven [] (reduce + (geteven)))- 코드를 보니 박일님이랑 동일하군요 ㅡㅡ;
; 피보나치 수열을 구한다.
(defn fibo []
(map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
;
(defn second-problem [n]
(reduce + ;시퀀스를 더한다.
(filter even? ;시퀀스 중에서 짝수만 필터링 한다.
(take-while #(<= % n) ;시퀀스 중에서 n 보다 작을때 까지의 컬렉션을 구한다.
(fibo))))) ;피보나치 수열을 구한다.1:1 user=> (second-problem 4000000)
4613732
- 저도 같네요 ㅎㅎ
(def opt-fibo-seq (map first (iterate (fn [[a b]] [b (+ a (* 4 b))]) [2 8])))
(reduce + (take-while #(<= % 4000000) opt-fibo-seq))- 프로그래밍 문제일 뿐 아니라 수학문제 이기도 한 것을 확인할 수 있었습니다..
- 하지만 실행속도 차이는 거의 없네요.
(defn fibo_sab [x]
(filter even? (take-while #(<= % x)(map first(iterate( fn [[a b]] [b ( + a b )]) [0 1]))))
)(reduce + (fibo 4000000))- 둘이 열심히 삽질해서 결국 풀었네요
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
- 소수를 구하고싶었습니다
(defn isPrime [number]
(loop [result number x number]
(if (= 1 x) true
(if(zero? (rem result (dec x)) )
true
(recur (result) (dec x))))))
;(if (zero? (rem num (dec num))
; true
; (recur (isPrime num))))
(isPrime 5); n을 m으로 나누었을때 나누어 떨어지면 true를 반환 아니면 false를 반환
(defn div? [n m](zero? (rem n m)))
; n의 약수들의 시퀀스를 반환 한다.
(defn divisors [n]
(lazy-seq
(filter #(div? n %) (range 2 (/ n 2)))))
; n을 이루는 가장 작은 소수를 반환 한다.
(defn smallest-prime-factor [n]
(first (divisors n)))
(def divisors (memoize divisors))
; 가장 큰 소수를 구한다.
(defn lagest-prime-factor [n]
(loop [x n]
(if (nil? (smallest-prime-factor x))
x
(recur (/ x (smallest-prime-factor x) )))))
; 덤~ 소수인지 판단.
(defn prime? [n]
(= n (lagest-prime-factor n)))
(def smallest-prime-factor (memoize smallest-prime-factor)); step 1 : 그냥 풀어본 방식
(defn whole-number [] (iterate inc 2))
;
(defn is-not-primes? [s n]
(if (= (rem s n) 0) false true))
;
(defn first-prime [n]
(first (drop-while #(is-not-primes? n %) (whole-number))))
;
(defn large-prime [n]
(loop [n1 n]
(if (= n1 (first-prime n1))
n1
(recur (quot n1 (first-prime n1)))
)
)
)
;
(time (large-prime 600851475143))
"Elapsed time: 27.165184 msecs"
6857; step 2 : iterate 시작지점을 n 부터 하는 방식으로 수정
(defn rest-number [n] (iterate inc n))
;
(defn is-not-primes? [s n]
(if (= (rem s n) 0) false true))
;
(defn first-prime [n r]
(first (drop-while #(is-not-primes? n %) (rest-number r ))))
;
(defn large-prime [n]
(loop [n1 n r 2]
(if (= n1 (first-prime n1 r))
n1
(recur (quot n1 (first-prime n1 r)) (first-prime n1 r))
)
)
)
;
(time (large-prime 600851475143))
"Elapsed time: 18.362669 msecs"
6857; step 3 : let 을 써서 반복 실행을 막은 버전
(defn rest-number [n] (iterate inc n))
(defn is-not-primes? [s n]
(if (= (rem s n) 0) false true))
(defn first-prime [n r]
(first (drop-while #(is-not-primes? n %) (rest-number r ))))
; quot
(defn large-prime [n]
(loop [n1 n r 2]
;(println n1)
(let [fp (first-prime n1 r)]
(if (= n1 fp)
n1
(recur (quot n1 fp) fp)
)
)
)
)
(time (large-prime 600851475143))
"Elapsed time: 13.368179 msecs"
6857(ns problem3
(use: clojure.contrib.lazy-seqs))
(defn findMaxPrime
([n primes]
(findMaxPrime n primes 0))
([n pri mx]
(if (> (first pri) n)
(println mx)
(if (= 0 (rem n (first pri)))
(findMaxPrime (/ n (first pri)) (rest pri) (first pri))
(findMaxPrime n (rest pri) mx)))))
(time (findMaxPrime 600851475143 primes)); 문제 3 : Find the largest prime factor of a composite number.
; recur 를 쓴 버전
; recur 의 인자는 loop 의 binding 인자를 다시 바인딩하기 때문에 서로 갯수가 같아야 한다.
; 소인수분해 최적화 알고리즘은 전혀 적용하지 않았음. 기억이 안 나...
(defn div-pf-recur [x n]
(loop [x x n n]
;(println x n)
(if (= x n)
n
(if (= (rem x n) 0)
(recur (quot x n) n)
(recur x (inc n))
)
)
)
)
(time (div-pf-recur 600851475143 2))
"Elapsed time: 10.16023 msecs"
6857(defn divedsth [a b] ( = (mod a b) 0 ))
(defn test [a b] (if (> a b) (if (divedsth a b) (test (/ a b) b) (test a (inc b))) b))
(defn biggest_prime_num [a] (test a 2))
(biggest_prime_num 600851475143 ) -> 오버플로우A palindromic number reads the same both ways.
The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 99.
Find the largest palindrome made from the product of two 3-digit numbers.
- 세자리 숫자 두 개의 조합을 만듬
- palindromic number인지 확인하기 위해 문자열로 만든뒤 뒤집어서 비교함
(ns Problem4
(:use clojure.contrib.combinatorics))
(defn palindromic-number?
[number]
(let [num1 (str number)
num2 (. (. (new StringBuffer (str number)) reverse) toString)]
(. num1 equals num2)))
(reduce max
(filter palindromic-number?
(map #(* (first %) (second %))
(selections (range 100 1000) 2))))(defn rev-num [n]
(loop [x n s 0]
(if (< 0 x)
(recur (quot x 10) (+ (* s 10)(rem x 10)))
s
)
)
)
(defn pal? [n]
(if (= n (rev-num n)) true false))
(first
(sort >
(filter pal?
(for [a (range 100 999) b (range 100 999)] (* a b))
)
)
)(reduce max (filter #(=(apply str (reverse (str %))) (str %))
(for[a (range 100 999) b (range 100 999)](* a b)))))2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
(defn divedsth [a b] ( = (mod a b) 0 ))
(defn do_ [x y] (loop [a x b y] (if (<= b 10)
(if (divedsth a b)
(recur a (inc b))
( recur (inc a) 1)) a )))
(do_ 1 1)(defn cm?[input]
(every? zero? ( map #(rem input %) (range 1 21) ))
)
(defn lcmlist? []
(take 1
(filter cm? (map #(* 20 %) (iterate inc 1)))
)
)
(defn lcmlist2? []
;(take 1
(filter cm? (map #(/ 2432902008176640000 %) (range 1 21)))
;)
)
(time (lcmlist?))(defn is-divided? [n r]
(if ( = (rem n r) 0) true false )
)
(defn is-divide-range? [n]
(every? #(is-divided? n %) (range 1 21))
)
; 무식하게 구하는 방법 느려서 결과를 확인 못했습니다.
(defn find-num []
(first
(filter #(is-divide-range? %) (iterate inc 1)
)
))
(defn divisors [n ]
(filter #(is-divided? n %) (range 1 (+ n 1)))
)
(defn my-gcd [a b]
(first (sort > (filter #(> % 0 ) (for [_a (divisors a) _b (divisors b)] (if (= _a _b) _a 0)))))
)
(defn my-lcm [a b]
(/ (* a b) (my-gcd a b))
)
; 최소공배수 까지만 함수를 만들고 문제는 못풀었습니다 ㅠㅠ; n의 약수들의 시퀀스를 반환 한다.
(defn divisors [n]
(lazy-seq
(filter #(div? n %) (range 1 (inc n)))))
;최대공약수
(defn gcd [a b]
( last
( for [c (divisors a) d (divisors b):when (= c d)] c)) )
;최소공배수
(defn lcm [a b]
(/ (* a b) (gcd a b)))
;
(defn foo [result x]
(if (zero? x)
result
(recur (lcm x (dec x) (dec x))))); 라이브러리의 lcm 사용
(ns ch6
(:use clojure.contrib.math))
(reduce lcm (range 1 21))
; 라이브러리 코드
(defn gcd "(gcd a b) returns the greatest common divisor of a and b" [a b]
(if (or (not (integer? a)) (not (integer? b)))
(throw (IllegalArgumentException. "gcd requires two integers"))
(loop [a (abs a) b (abs b)]
(if (zero? b) a,
(recur b (mod a b))))))
(defn lcm
"(lcm a b) returns the least common multiple of a and b"
[a b]
(when (or (not (integer? a)) (not (integer? b)))
(throw (IllegalArgumentException. "lcm requires two integers")))
(cond (zero? a) 0
(zero? b) 0
:else (abs (* b (quot a (gcd a b))))))(ns project-euler)
(defn calc-GCD [x y]
(if (zero? x) y
(if (zero? y) x (calc-GCD y (rem x y) ))
))
(calc-GCD 0 2)
(calc-GCD 2 0)
(calc-GCD 6 3)
(defn calc-LCM [x y]
(/ (* x y) (calc-GCD x y)))
(calc-LCM 4 7)
; 1~10까지 LCM은2520
(range 1 11)
;1~10까지 순차적으로 LCM을 구한다.
(defn calc-total-LCM [a]
(def sum 1)
; loop를 사용해서 시퀀스에서 하나씩 빼내고 빌때까지 반복
(def sum (calc-LCM sum (first a)))
sum
)
(calc-total-LCM '(8, 4))
The sum of the squares of the first ten natural numbers is,
1^2^ + 2^2^ + ... + 10^2^ = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)^2^ = 55^2^ = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
(int (- (Math/pow (reduce + (range 1 101)) 2) (reduce + (for [n (range 1 101)] (Math/pow n 2))))); 1~100까지 더한 숫자의 제곱에서 1~100까지 각 숫자의 제곱을 더한 수를 뺀다.
;
; 제곱을 구한다.
(defn squre [n]
(* n n))
; 1~n까지 각 숫자의 제곱을 더한다.
(defn sum-first-squre [n]
(reduce + (map squre (range 1 (inc n)))))
; 1~n까지 숫자를 더한다.
(defn sum-first-n [n]
(reduce + (range 1 (inc n))))
; 1~n까지 더한 숫자의 제곱에서 1~n까지 각 숫자의 제곱을 더한 수를 뺀다.
(defn projecteula6 [n]
(- (squre (sum-first-n n)) (sum-first-squre n))); 손으로 2 * sigma(n * (sigma k [k= n+1 ~ 100])) [n = 1 ~ 99] 를 구했습니다.
; 이 식을 간략화 하면 2 * sigma(n * (5050 - n*(n+1)/2)) [n = 1 ~ 99] 이고
; 이를 클로저 한줄로 표현.
(* 2 (reduce + (map #(* % (- 5050 (/ (* % (+ % 1)) 2))) (range 1 100))))
; "Elapsed time: 0.866711 msecs"(defn sumofsquare [n]
(reduce + (map #(expt % 2) n)))
(defn squareofsum [n]
(expt (reduce + n) 2))
(defn euler6 [n]
(- (squareofsum n) (sumofsquare n)))
(deftest test_sumofsquare
(is (= 14 (sumofsquare (range 1 4))))
(is (= 385 (sumofsquare (range 1 11)))))
(deftest test_squareofsum
(is (= 36 (squareofsum (range 1 4))))
(is (= 3025 (squareofsum (range 1 11)))))
(deftest test_euler6
(is (= 2640 (euler6 (range 1 11))))
(is (= 0 (euler6 (range 1 101)))))
(run-tests)
(euler6 (range 1 101))A Pythagorean triplet is a set of three natural numbers, a b c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
(ns Problem9
(:use clojure.contrib.combinatorics))
(defn makeTriple
[pair]
[(first pair)
(second pair)
(- 1000 (+ (second pair) (first pair)))])
(defn pythagorean?
[triple]
(= (+ (* (first triple) (first triple))
(* (second triple) (second triple)))
(* (last triple) (last triple))))
(defn validOrder?
[pair]
(< (first pair) (second pair)))
(reduce *
(first
(filter pythagorean?
(map makeTriple
(filter validOrder?
(combinations (range 1 (/ 1000 2)) 2)))))); 피타고라스 트리플 시퀀스 생성.
; http://en.wikipedia.org/wiki/Pythagorean_triple 의 Euclid's Fomula 참고.
(defn phytagorean_triplet [t]
(for [n (range 1 (+ t 1)) m (range 1 n)]
[(- (* n n) (* m m)) (* 2 n m) (+ (* n n) (* m m))]))
; 트리플이 합이 1000 인 것의 첫번째를 가져와서 * 로 reduce
(reduce *
(first (drop-while #(not (= (reduce + %) 1000)) (phytagorean_triplet 1000))))(ns your-namespace
(:use clojure.contrib.math))
(defn get-c [a b]
(+ (* a a) (* b b)))
; a^2 + b ^ 2 가 정수의 제곱값인가?
(defn pythagorean? [a b]
(if (= 0 (last (exact-integer-sqrt (get-c a b))))
true
false
)
)
; a < b 인 범위 중에서 pythagorean 인 경우를 찾아 seq 로 만든다.
(defn get-pyta-to [n]
(for [a (range 1 n) b (range (+ a 1) n) :when (pythagorean? a b)]
(let [c (first (exact-integer-sqrt (get-c a b)))]
(seq [(* a b c) a b c (+ a b c)])
)
)
)
; * a b c 값을 얻는다.
(defn euler9 [n s]
(first
(first
(filter #(= s (last %)) (get-pyta-to n))
)
)
)
(euler9 1000 1000)In the 2020 grid below, four numbers along a diagonal line have been marked in red.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 '''26''' 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 '''63''' 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 '''78''' 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 '''14''' 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
The product of these numbers is 26 63 78 14 = 1788696.
What is the greatest product of four adjacent numbers in any direction (up, down, left, right, or diagonally) in the 2020 grid?
(def grid (indexed [ 8 2 22 97 38 15 0 40 0 75 4 5 7 78 52 12 50 77 91 8
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4 56 62 0
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 3 49 13 36 65
52 70 95 23 4 60 11 42 69 24 68 56 1 32 56 71 37 2 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 3 45 2 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 2 62 12 20 95 63 94 39 63 8 40 91 66 49 94 21
24 55 58 5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 9 75 0 76 44 20 45 35 14 0 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 3 80 4 62 16 14 9 53 56 92
16 39 5 42 96 35 31 47 55 58 88 24 0 17 54 24 36 29 85 57
86 56 0 48 35 71 89 7 5 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 5 94 47 69 28 73 92 13 86 52 17 77 4 89 55 40
4 52 8 83 97 35 99 16 7 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 3 46 33 67 46 55 12 32 63 93 53 69
4 42 16 73 38 25 39 11 24 94 72 18 8 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 4 36 16
20 73 35 29 78 31 90 1 74 31 49 71 48 86 81 16 23 57 5 54
1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48]))
(def values
(for [y (range 0 17) x (range 0 17)]
[
(reduce * (map second (take 4 (drop (+ x (* y 20)) grid))))
(reduce * (map second (take 4
(filter #(= 0 (rem (- (first %) (+ x (* y 20))) 20))
(drop (+ x (* y 20)) grid)))))
(reduce * (map second (take 4
(filter #(= 0 (rem (- (first %) (+ x (* y 20))) 21))
(drop (+ x (* y 20)) grid)))))
(reduce * (map second (take 4
(filter #(= 0 (rem (- (first %) (+ (+ x 3) (* y 20))) 19))
(drop (+ (+ x 3) (* y 20)) grid)))))
]))
(reduce max (flatten values))(def P11Data [[ 8 2 22 97 38 15 0 40 0 75 4 5 7 78 52 12 50 77 91 8]
[49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 4 56 62 0]
[81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 3 49 13 36 65]
[52 70 95 23 4 60 11 42 69 24 68 56 1 32 56 71 37 2 36 91]
[22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80]
[24 47 32 60 99 3 45 2 44 75 33 53 78 36 84 20 35 17 12 50]
[32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70]
[67 26 20 68 2 62 12 20 95 63 94 39 63 8 40 91 66 49 94 21]
[24 55 58 5 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72]
[21 36 23 9 75 0 76 44 20 45 35 14 0 61 33 97 34 31 33 95]
[78 17 53 28 22 75 31 67 15 94 3 80 4 62 16 14 9 53 56 92]
[16 39 5 42 96 35 31 47 55 58 88 24 0 17 54 24 36 29 85 57]
[86 56 0 48 35 71 89 7 5 44 44 37 44 60 21 58 51 54 17 58]
[19 80 81 68 5 94 47 69 28 73 92 13 86 52 17 77 4 89 55 40]
[ 4 52 8 83 97 35 99 16 7 97 57 32 16 26 26 79 33 27 98 66]
[88 36 68 87 57 62 20 72 3 46 33 67 46 55 12 32 63 93 53 69]
[ 4 42 16 73 38 25 39 11 24 94 72 18 8 46 29 32 40 62 76 36]
[20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 4 36 16]
[20 73 35 29 78 31 90 1 74 31 49 71 48 86 81 16 23 57 5 54]
[ 1 70 54 71 83 51 54 69 16 92 33 48 61 43 52 1 89 19 67 48]])
(defn get-data
[data x y]
(nth (nth data y) x))
(defn product-x
[data x y]
(reduce * (for [px (range x (+ x 4))] (get-data data px y))))
(defn product-y
[data x y]
(reduce * (for [py (range y (+ y 4))] (get-data data x py))))
(defn product-rb
[data x y]
(reduce * (for [delta (range 0 4)] (get-data data (+ x delta) (+ y delta)))))
(defn product-lb
[data x y]
(reduce * (for [delta (range 0 4)] (get-data data (- x delta) (+ y delta)))))
(reduce max (for [x (range 0 17) y (range 0 17)]
(max
(product-x P11Data x y)
(product-y P11Data x y)
(product-rb P11Data x y)
(product-lb P11Data (+ x 3) y))))- 제가 제일 어렵게 푼듯 -_-...
(defn getBigProductEach4Pair [n]
(reduce max (map #(reduce * %) (partition-all 4 1 n))))
(deftest test-getBigProductEach4Pair
(is (= 5040 (getBigProductEach4Pair [1 2 3 4 5 6 7 8 9 10]))))
; ({:idx [0 0], :val 1} {:idx [0 1], :val 2} ... {:idx [2 4], :val 15})
(def testdata
(map-indexed
(fn [index value]
{:idx [(quot index 5) (rem index 5)] :val value})
[01 02 03 04 05
06 07 8 9 10
11 12 13 14 15]))
(defn getXnumbers [data line]
(for [n data :when (= line (first (get n :idx)))] (get n :val)))
(deftest test-getXnumbers
(is (= [1 2 3 4 5] (getXnumbers testdata 0)))
(is (= [6 7 8 9 10] (getXnumbers testdata 1))))
(defn getYnumbers [data line]
(for [n data :when (= line (last (get n :idx)))] (get n :val)))
(deftest test-getYnumbers
(is (= [1 6 11] (getYnumbers testdata 0)))
(is (= [2 7 12] (getYnumbers testdata 1))))
; 왼쪽대각선은 x,y 좌표의 합
(defn getLeftDiagonalnumbers [data line]
(for [n data :when (= line (reduce + (get n :idx)))] (get n :val)))
(deftest test-getLeftDiagonalnumbers
(is (= [1] (getLeftDiagonalnumbers testdata 0)))
(is (= [2 6] (getLeftDiagonalnumbers testdata 1)))
(is (= [3 7 11] (getLeftDiagonalnumbers testdata 2)))
(is (= [15] (getLeftDiagonalnumbers testdata 6)))
)
; 오른쪽대각선은 x,y 좌표의 차
(defn getRightDiagonalnumbers [data line]
(for [n data :when (= line (- (last (get n :idx)) (first (get n :idx) )))] (get n :val)))
(deftest test-getRightDiagonalnumbers
(is (= [11] (getRightDiagonalnumbers testdata -2)))
(is (= [6 12] (getRightDiagonalnumbers testdata -1)))
(is (= [2 8 14] (getRightDiagonalnumbers testdata 1)))
(is (= [5] (getRightDiagonalnumbers testdata 4)))
)
(run-tests)
(def Eulerdata (map-indexed
(fn [index value] {:idx [(quot index 20) (rem index 20)] :val value}) [
8 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 8
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 63 94 39 63 8 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72
21 36 23 9 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 9 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 8 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 8 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
]))
(max
(reduce max (for [x (range 0 20)] (getBigProductEach4Pair (getXnumbers Eulerdata x))))
(reduce max (for [x (range 0 20)] (getBigProductEach4Pair (getYnumbers Eulerdata x))))
(reduce max (for [x (range 0 (+ 19 19))] (getBigProductEach4Pair (getLeftDiagonalnumbers Eulerdata x))))
(reduce max (for [x (range -19 19)] (getBigProductEach4Pair (getRightDiagonalnumbers Eulerdata x))))
)Let's call S the (infinite) string that is made by concatenating the consecutive positive integers (starting from 1) written down in base 10.
Thus, S = 1234567891011121314151617181920212223242...
It's easy to see that any number will show up an infinite number of times in S.
Let's call f(n) the starting position of the nth occurrence of n in S.
For example, f(1)=1, f(5)=81, f(12)=271 and f(7780)=111111365.
Find sigma f(3^k) for 1 <= k <= 13.
; ("1" "2" ... "10" "11"..)
(def whole-number-str (map str (iterate inc 1)))
; "123" -> ("1" "2" "3")
(defn to-single-digit-seq [s] (filter #(not= %1 "") (seq (.split s ""))))
; ("1" .. "9" "1" "0" "1" "1" ...)
(def single-digit-seq (mapcat to-single-digit-seq whole-number-str))
; n=2, ("12" "23" ... "91" "10" "01" "11" ...)
; n=3, ("123" 234" ... "910" "101" ...)
(defn make-final [n]
(letfn [(final-seq
[coll1 coll2 n]
(if (zero? n)
coll1
(recur (map #(str %1 %2) coll1 coll2) (rest coll2) (dec n))))]
(final-seq single-digit-seq (rest single-digit-seq) (dec n))))
(defn find-index [n]
(letfn [(semi-index
[coll current match goal]
(if (= match goal)
current
(recur
(rest coll)
(inc current)
(if (= (str n) (first coll)) (inc match) match)
goal)))]
(semi-index (make-final (.length (str n))) 0 0 n)))
; 여기 까지 해서 (find-index 12) 이렇게 하면 271 은 나오는데
; 큰 숫자를 넣으면 heap 할당 에러가 남. ㅠ.ㅠ(defn make-final2 [n]
(letfn [(final-seq
[coll1 coll2 n]
(if (zero? n)
(map #(list %1 %2) coll1 (iterate inc 1))
(recur (map #(str %1 %2) coll1 coll2) (rest coll2) (dec n))))]
(final-seq single-digit-seq (rest single-digit-seq) (dec n))))
(defn find-index2-sub [n]
(filter #(= (str n) (first %)) (make-final2 (.length (str n)))))
(defn find-index2 [n]
(second (first (drop (dec n) (find-index2-sub n)))))
; 조금 간단하게 만들었지만 역시 heap 에러. 알고리즘을 바꿔야 할듯; 간만에 근성으로 달려보네요. 대학때 생각나요..ㅠ.ㅠ
(defn find-max-sub-match-index-from-end [s t]
(letfn [(find-sub
[idx src tgt]
(if (or (= (apply str (take (.length tgt) src)) tgt) (= 0 (.length tgt)))
idx
(recur (inc idx) src (apply str (rest tgt)))))]
(find-sub 0 s t)))
(defn find-index3 [n]
(letfn [(find-sub
[coll cur-index match-count match-goal count-goal]
(if (= match-count count-goal)
cur-index
(let [drop-count
(find-max-sub-match-index-from-end
match-goal
(apply str (take (.length match-goal) coll)))]
(if (zero? drop-count)
(recur
(drop (.length match-goal) coll)
(+ cur-index (.length match-goal))
(inc match-count)
match-goal
count-goal)
(recur
(drop drop-count coll)
(+ cur-index drop-count)
match-count match-goal count-goal)))))]
(find-sub single-digit-seq 0 0 (str n) n)))
(reduce + (pmap find-index3 (take 13 (iterate #(* % 3) 3))))
; 물리적 메모리는 남아있는데. java.lang.OutOfMemoryError: GC overhead limit exceeded.
; 이런 에러를 내며 끝났네요 흑.