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

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

false

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

hello.core=> (defn my-add [op1 op2] (+ op1 op2))

3

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

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;

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: `2``3``5` and `7`. Thus, Prime Prime numbers are `3``4``5`and `6``4` 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: `2``3``5` and `7`. Thus, Prime Prime numbers are `3``4``5`and `6``4` 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[n-1];

print(lps("ABACAA"))```