programming clojure project euler - andstudy/forge GitHub Wiki

project euler

problem 1

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

problem 2

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](/andstudy/forge/wiki/a-b) [b (+ a b)]) [0 1])))
(take-while (filter #(<= % 20) (fibo)))

ν˜„μˆ˜λͺ… μ‚½μ§ˆν›„ 성곡!

(defn fibo []
 (map first (iterate (fn [a b](/andstudy/forge/wiki/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](/andstudy/forge/wiki/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](/andstudy/forge/wiki/a-b) [b (+ a b)]) [0 1])))
(reduce + (filter even? (take-while #(>= 4000000 %) (fibo))))

λ°•λ―Όμš± -μ²˜μŒλΆ€ν„° 천천히 짜본 버전 -

; ν”Όλ³΄λ‚˜μΉ˜ μˆ˜μ—΄ κ΅¬ν•˜λŠ” 곡식
(defn fibo []
  (map first (iterate (fn [a b](/andstudy/forge/wiki/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](/andstudy/forge/wiki/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
  • 저도 κ°™λ„€μš” γ…Žγ…Ž

λ°•μƒν˜ ν™ˆνŽ˜μ΄μ§€ λ‹΅ 제좜 ν›„ Overview λ₯Ό 읽어보고 λ§Œλ“  버전

(def opt-fibo-seq (map first (iterate (fn [a b](/andstudy/forge/wiki/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](/andstudy/forge/wiki/a-b) [b ( + a b )]) [0 1]))))
)(reduce + (fibo 4000000))
  • λ‘˜μ΄ μ—΄μ‹¬νžˆ μ‚½μ§ˆν•΄μ„œ κ²°κ΅­ ν’€μ—ˆλ„€μš”

problem 3

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 ) -> μ˜€λ²„ν”Œλ‘œμš°

problem 4

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

chy

(reduce max (filter #(=(apply str (reverse (str %))) (str %)) 
  (for[a (range 100 999) b (range 100 999)](* a b)))))

problem 5

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

problem 6

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

problem 9

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)

problem 11

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

problem 305

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.

λ°•μƒν˜

Try#1

; ("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 ν• λ‹Ή μ—λŸ¬κ°€ 남. γ… .γ… 

Try#2

(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 μ—λŸ¬. μ•Œκ³ λ¦¬μ¦˜μ„ λ°”κΏ”μ•Ό ν• λ“―

Try#3

; κ°„λ§Œμ— κ·Όμ„±μœΌλ‘œ λ‹¬λ €λ³΄λ„€μš”. λŒ€ν•™λ•Œ μƒκ°λ‚˜μš”..γ… .γ… 
(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.
; 이런 μ—λŸ¬λ₯Ό λ‚΄λ©° λλ‚¬λ„€μš” 흑.