Wednesday, July 27, 2016

Clojure (3) prefix notation

we are used to using 3 + 5 if we add two numbers
Clojure is different from what we are familiar with.

(+ 2 3) this is clojure add form.

if we add numbers not only two, code will be complicated
ex)  add(add(add(2, 3),5),6)

clojure is so simple
(+ 2 3 5 6)

and result is the same





Wednesday, July 20, 2016

Clojure (2) hash map and check-login function

Is there HashMap in clojure
Yes It it.

below is hash map and check-login function
(def users 
  {"kyle" {:password "secretk" :number-pets 2}
   "siva" {:password "secrets" :number-pets 4}
   "rob" {:password "secretr" :number-pets 6}
   "george" {:password "secretg" :number-pets 8}})

(defn check-login[username password]
    (let [actual-password ((users username):password)]
        (= actual-password password)))


try to use check-login function
hello.core=> (check-login "kyle" "secretks")
false

hello.core=> (check-login "kyle" "secretk")
true

Clojure (1) add two number

First time, I blog about Clojure.
IDE = Nightcode1.0.1

this code is from Clojure in action and I rewrited it.

With REPL I run.

Sum two values
hello.core=> (+ 1 2)
3

make function add two values
hello.core=> (defn my-add [op1 op2] (+ op1 op2))
#'hello.core/my-add

use add function
hello.core=> (my-add 1 2)
3

use add function
hello.core=> (my-add 1000000000000000000 300000000000000000000)
301000000000000000000N


도개걸윷모 개가 나올 확률~!

이건 경우의 수 문제입니다.
(난이도는 Easy 입니다.)

어느날 갑자기 도개걸윷모중에서 개가 나올 확률을 물어본다면 무엇이라고 대답하시겠어요?? 
저한테 있었던 일이에요.

1/5 ? 음.. 아닌데.. ㅠ 갑자기 말을 못했던 기억이..

그러면 다시 정리해서 작성해보죠.

말을 다시 바꾸어서 4개의 동전이 있습니다. 
4개의 동전을 던졌을때 2개의 동전이 앞이 나오는 경우는 몇가지인가요?

동전 1개당 앞 뒤가 있으니 경우의 수는 2개이며
총 4개라고 했으니 

2*2*2*2 즉 2^4  16개가 나옵니다.
그중에 2개가 앞이 나올 경우의 수는

1. (O, O , X, X)
2. (O, X , O, X)
3. (O, X , X, O)
4. (X, O, O, X)
5. (X, O, X, O)
6. (X, X, O, O)

즉 첫번째를 포함한경우 3
2번째를 포함하고 그 이하인 경우 2
3번째를 포함하고 그 이한경우 1

총 6가지가 나옵니다. 

어렵지 않지요??

접근 1 : 모든 경우의 수를 나열한다.

접근 2 : 경우의 수를 수학적으로 계산한다.

같은 것이 있는 순열이 있습니다.  (증명은 수학의 정석 참고하시면 됩니다.)
일반적으로 계산 식은 

(총갯수!/중복이 있는 수! * 중복이 있는 수!....)
위의 예제로 다시 정리하면
4!/2!*2! = 6이 나옵니다.

이렇게 되면 아주 큰 수도 간단한 수학적 지식으로 풀 수가 있겠죠??

Tuesday, July 19, 2016

Project Euler 160 Factorial trailing digits

It took about 8days from start to solving this problem (last non-zero digits of factorial)
First time I searched 0 to 1000000000000.
I doubt that my computer compute this logig in my life?
and searching how to find last zeros count of N factorial

finally I made condition

ex) 10! = 1 * 2* 3* 4 * 5* 6* 7 * 8 *9 *10

2*5 make 0 digit

so we should find multiple of 5
5, 10 that is all

5 = 5*1
10 = 5*2

10! = 5^2 * 2! * (10a +1) (10a +2)  (10a +3) (10a +4) (10a +6).. (10a +9) mod m
10! = 10^2 * 2! * (10a +1) (5a+1) (10a+3) (5a+2) (10a+6 )... (10a+9)..

what if 100! and m is 10 ???

100! = 10^20 * 20! *  ((10a +1) (5a+1) (10a+3) (5a+2) (10a+6 )... (10a+9))^10

so we can use this and solve 1000000000000 ! mod 100000






https://projecteuler.net/problem=160

For any N, let f(N) be the last five digits before the trailing zeroes in N!.
For example,
9! = 362880 so f(9)=36288
10! = 3628800 so f(10)=36288
20! = 2432902008176640000 so f(20)=17664
Find f(1,000,000,000,000)

PrimePrime count sieve of Eratosthenes.

this problem is from codefights.
https://codefights.com/challenge/doXskkj8PMAJ27Epk/main

try to find prime numbers by using  sieve of Eratosthenes.
and count luckyprimeprime.

I think this is not difficult though.

 int c, t, s, i;
 int luckyandprimeprime(int l, int r) {
  int[] p = new int[100001];
  
  s = p.length;
  for ( i = 2; i < s; i++, t=0) 
   while ((t += i) < s) 
    p[t]++;   

  for (i = 0; i < l; i++)
   if (p[i] == 1)
    c++;

  for (i = l; i <= r; i++) {
   if (p[i] == 1)
    c++;

   if (p[c] == 1)
    t++;
  }
  return t;
 }

Recently Lucky learnt how to check if the given number is prime or not. Bunny, Lucky's friend, decided to give her a task to test her skills.
Let's call number P Prime Prime if the number of prime numbers in the range [1, P] is prime. Bunny asked Lucky to calculate the number of Prime Prime numbers in the range [l, r]. Can you you help her?
Example
For l = 1 and r = 10, the output should be
luckyandprimeprime(l, r) = 4.
There're 4 prime numbers in the given range: 235 and 7. Thus, Prime Prime numbers are 345and 64 numbers altogether.
Input/Output
  • [time limit] 3000ms (java)
  • [input] integer l
    Constraints:
    1 ≤ l ≤ r.
  • [input] integer r
    Constraints:
    l ≤ r ≤ 105.
  • [output] integer
    The number of Prime Prime numbers in the range [l, r].




Recently Lucky learnt how to check if the given number is prime or not. Bunny, Lucky's friend, decided to give her a task to test her skills.
Let's call number P Prime Prime if the number of prime numbers in the range [1, P] is prime. Bunny asked Lucky to calculate the number of Prime Prime numbers in the range [l, r]. Can you you help her?
Example
For l = 1 and r = 10, the output should be
luckyandprimeprime(l, r) = 4.
There're 4 prime numbers in the given range: 235 and 7. Thus, Prime Prime numbers are 345and 64 numbers altogether.
Input/Output
  • [time limit] 3000ms (java)
  • [input] integer l
    Constraints:
    1 ≤ l ≤ r.
  • [input] integer r
    Constraints:
    l ≤ r ≤ 105.
  • [output] integer
    The number of Prime Prime numbers in the range [l, r].

Friday, July 8, 2016

cutting a rod

I studied cuttingrod dp alogorithm.

first cuttingrod is recursive function
and
cuttingRodDP is dynamic problem.

If we want to use by using recursive function
to speed up. we have to use memoized array



def cuttingRod(s, arr):

    m = arr[s-1]
    for i in range(1,int(s/2)+1):
        left=  i
        right =s-i
        val = cuttingRod(left, arr) + cuttingRod(right,arr)
        print(left, right, val)
        m= max(m, val )

    return m

def cuttingRodDP(s, arr):

    m = [0 for i in range(len(arr)+1)]
    for i in range(1, len(arr)+1):
        m[i]= arr[i-1]


    maxValue =0
    for i in range(1, len(arr)+1):
        for j in range(1,i+1):
           maxValue =  max(maxValue, m[j] + m[i-j])
        m[i] = maxValue
        print(m)

    return maxValue


arr= [ 1 ,  5,   8 ,  9 , 10,  17,  17,  20]
print(cuttingRod(len(arr), arr))

print(cuttingRodDP(len(arr), arr))

Wednesday, July 6, 2016

Largest palindromic subsequence in pyhton

# link site is http://www.geeksforgeeks.org/dynamic-programming-set-12-longest-palindromic-subsequence/


def lps(str):
    n = len(str)

    L = [[0 for col in range(n)] for row in range(n)]

    for i in range(n):
        L[i][i] =1
    #count    for cl in range(2, n+1):
         for i in range(0, n-cl+1):
            j= i+cl-1
            if str[i] == str[j] and cl ==2 :
                L[i][j] =2            elif str[i] == str[j]:
                 L[i][j] = L[i+1][j-1] + 2            else :
                L[i][j] = max(L[i][j-1], L[i+1][j])
    print(L)
    return L[0][n-1];

print(lps("ABACAA"))