regular expression remove font-size

recent I made regular expression for removing font-size tag in style attribute

this is what I made

        private static String removeFontSizeFromStyle(String styleContent) {
  String fontPattern = "[fF][oO][nN][tT]-[sS][iI][zZ][eE]\\s*:\\s*[0-9.]+[a-zA-Z%]*\\s*+;?";

  return styleContent.replaceAll(fontPattern, "");
 }

이번주 읽을 도서 "미래를 바꾼 아홉가지 알고리즘"

지하철에서 한번 읽어봐야겠다 일고 난후 후기 올리겠음.

요즘 근황

다른 사람들 블로그를 보다 보면 한번씩 근황에 대해서 글이 올라온다.
요즘에는 이런저런을 하고 있고 그러다보니 오랫만에 블로그에 글을 남긴다는 내용이다.
5년만에 처음 회사에 이직을 했다. 개발하는게 자신이 있었고 그전부터 꾸준히 공부를 해오고있었다는 자신감이 있었는데 막상 이직을 해보니 회사에서 기존 개발되어있는 내용들을 숙지하는것이 보통일이 아니다 그전에는 오래되어서 모르는거 있으면 쉽게 쉽게 물어보고 모든게 익숙해서 내가 원하는대로 쉽게 했었는데 아무래도 적응기간이 필요한것 같다.

이제 한달이 지나가는것 같다.
나의 숨구멍이 조금씩 트이는것 같아 기분이 좋은데 일을 처리하는 속도가 안올라서 큰일이다.
조금만더 여유가 생기면 알고리즘공부를 다시 계속 해야겠다.

Nginx로 할 수 있는 것들

nginx에서 제공하는 기능들이 거의 아파치에서 이미 지원하고 있는 기능들이 많다.

내가 알고 있는 nginx에서 사용할 수 있는 기능

1. 프락시 서버

2. 여러대 서버 로드 밸런싱

  - ip hash 라고 계속해서 똑같은 ip의 서버를 바라보게 하는 스펙.

3. static 서버

4. cgi server

5. rewriteurl -> Semantic Url 을 위해서 사용함.

의문 1 만약에 로드밸런싱을 하고 있는데 서버가 다운되었을 경우는 어떻게 되는가??? 한번 더 찾아봐야겠다.

closure usage in javascript

This is bad source all nodes are show "nodes.length-1" when you click any node

var add_the_handler = function (nodes){
 var i;
 for(i=0; i<nodes.length; i+=1){
  nodes[i].onclick = function(e){
   alert(i);
  }
 }
}

this is a good pattern compared to above function

var add_the_handler = function (nodes){
 var i;
 for(i=0; i<nodes.length; i+=1){
  nodes[i].onclick = function(i){
   return function(e){
    alert(i)
   };
  }(i)
 }
}

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

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이 나옵니다.

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

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: 2, 3, 5 and 7. Thus, Prime Prime numbers are 3, 4, 5and 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, 5and 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].

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

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

Project Euler 155 Counting Capacitor Circuits

It was very complicated and hard problem when I saw this problem for the first time.
at that time I thought I could not solve this one.
and actually gave up to solve it. because I can't come up with any idea and Algorithm.

after one year from that time with algorithm study.
I have confidence and retry to solve it.
I got an answer of that problem.

Hint is dynamic problem and bruteforce and hashset

that is all
If you have more detail of it reply plz~


https://projecteuler.net/problem=155

An electric circuit uses exclusively identical capacitors of the same value C.
The capacitors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other capacitors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to n identical capacitors, we can make circuits having a range of different total capacitances. For example, using up to n=3 capacitors of 60 F each, we can obtain the following 7 distinct total capacitance values:

If we denote by D(n) the number of distinct total capacitance values we can obtain when using up to n equal-valued capacitors and the simple procedure described above, we have: D(1)=1, D(2)=3, D(3)=7 ...

Find D(18).

Reminder : When connecting capacitors C₁, C₂ etc in parallel, the total capacitance is C_T = C₁ + C₂ +...,
whereas when connecting them in series, the overall capacitance is given by: 

Project Euler 200 prime-proof sqube

We shall define a sqube to be a number of the form, p²q³, where p and q are distinct primes.
For example, 200 = 5²2³ or 120072949 = 23²61³.

The first five squbes are 72, 108, 200, 392, and 500.

Interestingly, 200 is also the first number for which you cannot change any single digit to make a prime; we shall call such numbers, prime-proof. The next prime-proof sqube which contains the contiguous sub-string "200" is 1992008.

Find the 200th prime-proof sqube containing the contiguous sub-string "200".

this problem is not hard but for fun~!
hint is generate numbers until 10^13

Project Euler 201 Subsets with a unique sum

For any set A of numbers, let sum(A) be the sum of the elements of A.
Consider the set B = {1,3,6,8,10,11}.
There are 20 subsets of B containing three elements, and their sums are:

sum({1,3,6}) = 10,
sum({1,3,8}) = 12,
sum({1,3,10}) = 14,
sum({1,3,11}) = 15,
sum({1,6,8}) = 15,
sum({1,6,10}) = 17,
sum({1,6,11}) = 18,
sum({1,8,10}) = 19,
sum({1,8,11}) = 20,
sum({1,10,11}) = 22,
sum({3,6,8}) = 17,
sum({3,6,10}) = 19,
sum({3,6,11}) = 20,
sum({3,8,10}) = 21,
sum({3,8,11}) = 22,
sum({3,10,11}) = 24,
sum({6,8,10}) = 24,
sum({6,8,11}) = 25,
sum({6,10,11}) = 27,
sum({8,10,11}) = 29.

Some of these sums occur more than once, others are unique.
For a set A, let U(A,k) be the set of unique sums of k-element subsets of A, in our example we find U(B,3) = {10,12,14,18,21,25,27,29} and sum(U(B,3)) = 156.

Now consider the 100-element set S = {1², 2², ... , 100²}.
S has 100891344545564193334812497256 50-element subsets.

Determine the sum of all integers which are the sum of exactly one of the 50-element subsets of S, i.e. find sum(U(S,50)).

I solved this problem for 2hours coding.
I was'nt able to solve this using brutefoce, so I made algorithm.

Project Euler 401 Sum of squares of divisors

The divisors of 6 are 1,2,3 and 6.
The sum of the squares of these numbers is 1+4+9+36=50.

Let sigma2(n) represent the sum of the squares of the divisors of n. Thus sigma2(6)=50.

Let SIGMA2 represent the summatory function of sigma2, that is SIGMA2(n)=∑sigma2(i) for i=1 to n.
The first 6 values of SIGMA2 are: 1,6,16,37,63 and 113.

Find SIGMA2(10¹⁵) modulo 10⁹.

I have to found SIGMA2(10^15)

for bruteforce I cant't solve in my life time

hint 

1^2 + 2^2 + 3^2 + 4^2+ 5^2 + .... N^2 = n(n+1)(2n+1)/6

and what you can do is find answer.~!!!!!!

Project Euler 110

In the following equation x, y, and n are positive integers.

1 x

+

1 y

=

1 n

It can be verified that when n = 1260 there are 113 distinct solutions and this is the least value of n for which the total number of distinct solutions exceeds one hundred.

What is the least value of n for which the number of distinct solutions exceeds four million?

My solution~!

1/x + 1/y = 1/n
n/x + n/y = 1
n + nx/y = x
ny + nx = xy
xy - ny -nx =0
xy -ny -nx + n^2 = n^2
(x-n)(y-n) = n^2

if I change x-n = A
               y-n = B

AB = n^2
A and B is divisor of n^2
so we can calculate count of divisors of n^2.

just find n that divisorCount/2 exceeds four million.

Project Euler 148 Pascal's triangle

I solved this one by looking at pattern. Triangular number fractal??? anyway I just used triangular function. from F(1) to F(7) = n(n+1)/2 F(7^2) = F(7)*F(7) F(7^3) = F(7)*F(7)*F(7) what is if F(7^a-3) ? we know that the power of 7 grater than (7^a)-3 is a so we can find this val v = 7^a/7^(a-1) r = 7^a mod 7^(a-1) and finally got recursive function F(7^a-1) = if (r >0) F(v)*F(7)*F(7) + (v+1) * F(r) else F(v)*F(7)*F(7) and Finally I got answer quickly index : 1 1 index : 2 11 index : 3 111 index : 4 1111 index : 5 11111 index : 6 111111 index : 7 1111111 index : 8 1......1 index : 9 11.....11 index : 10 111....111 index : 11 1111...1111 index : 12 11111..11111 index : 13 111111.111111 index : 14 11111111111111 index : 15 1......1......1 index : 16 11.....11.....11 index : 17 111....111....111 index : 18 1111...1111...1111 index : 19 11111..11111..11111 index : 20 111111.111111.111111 index : 21 111111111111111111111 index : 22 1......1......1......1 index : 23 11.....11.....11.....11 index : 24 111....111....111....111 index : 25 1111...1111...1111...1111 index : 26 11111..11111..11111..11111 index : 27 111111.111111.111111.111111 index : 28 1111111111111111111111111111 index : 29 1......1......1......1......1 index : 30 11.....11.....11.....11.....11 index : 31 111....111....111....111....111 index : 32 1111...1111...1111...1111...1111 index : 33 11111..11111..11111..11111..11111 index : 34 111111.111111.111111.111111.111111 index : 35 11111111111111111111111111111111111 index : 36 1......1......1......1......1......1 index : 37 11.....11.....11.....11.....11.....11 index : 38 111....111....111....111....111....111 index : 39 1111...1111...1111...1111...1111...1111 index : 40 11111..11111..11111..11111..11111..11111 index : 41 111111.111111.111111.111111.111111.111111 index : 42 111111111111111111111111111111111111111111 index : 43 1......1......1......1......1......1......1 index : 44 11.....11.....11.....11.....11.....11.....11 index : 45 111....111....111....111....111....111....111 index : 46 1111...1111...1111...1111...1111...1111...1111 index : 47 11111..11111..11111..11111..11111..11111..11111 index : 48 111111.111111.111111.111111.111111.111111.111111 index : 49 1111111111111111111111111111111111111111111111111 index : 50 1................................................1 index : 51 11...............................................11 index : 52 111..............................................111 index : 53 1111.............................................1111 index : 54 11111............................................11111 index : 55 111111...........................................111111 index : 56 1111111..........................................1111111 index : 57 1......1.........................................1......1 index : 58 11.....11........................................11.....11 index : 59 111....111.......................................111....111 index : 60 1111...1111......................................1111...1111 index : 61 11111..11111.....................................11111..11111 index : 62 111111.111111....................................111111.111111 index : 63 11111111111111...................................11111111111111 index : 64 1......1......1..................................1......1......1 index : 65 11.....11.....11.................................11.....11.....11 index : 66 111....111....111................................111....111....111 index : 67 1111...1111...1111...............................1111...1111...1111 index : 68 11111..11111..11111..............................11111..11111..11111 index : 69 111111.111111.111111.............................111111.111111.111111 index : 70 111111111111111111111............................111111111111111111111

Project Euler 169

I sovled thinking about more than 10hours.

anyway sovled it.

hint
1. binary
2. even number , odd number

Project Euler 277 A Modified Collatz sequence

My answer was
left - right and right - left brute force

any good idea is expand sequence and find x

anyway I success

Project Euler 162 Hexadecimal numbers

This problem I thought about more than 2 hours.

My access was combination~!

and Finally got answer O(n^3)

16length ^ 3

Other people solved it O(n)

Project Euler 387 Harshad Numbers

This is an easy problem.
when we solve problem there are something to be considered.
I will tell you one tip.


1. from small number to Big number
 - problem give us find big number for example sum of over 10^14. just find the answer of smaller number ex) 10^3, 10^4 and check your logic if it is working fine.

I solve this problem by using dp.

Project Euler 500

I thought much time and finally got hint

min heap

Project Euler 501 Eight Divisors

I think much time to solve this problem.

but easily i got depressed

because finding primes under 10^12 is too big.

my computer can only 10^9 by using Prime sieve.

so I had to find how to count primeCount under some number.

finally I solved it~!

problem 287 in project euler

I took 5 hours to solve this problem. thinking time and coding time is 5hours 1.my first approch this problem was math approach D1, D2, D3, D4 and there is nothing related to math. 2. second was finding pattern. with eclipse tool I was able to draw D1, to D7 but nothing found without only one thing that is black circle. 3. thought lots time and look deeply more and more. 4. finally found that It could be possible that whether all blocks are colorerd black or not if I check only four couners. 5. divide and conquer bruteforce check. 6. I got answer after 5min process. I think it it too long. 7. I started customized removing duplicated conditions. 8. 10second. 9. I changed Math.pow to a * a . 10 finally I can solve this one within 1 second

codefights turnsOnRoad

I divide into 4 side
right, top, left, bottom and finally check.



this is problem
https://codefights.com/challenge/7WzF2fGJA6nKaMbNR

Cross Bridge in minimum time in codefights

This is veryintersting and I just worte down some testcases and
found algorithm.
someday I will write detail of this problem.


my code is here

 int c, l;
 int Bridge(int[] t) {
  l=t.length;
  Arrays.sort(t);
  
  while(l>3) {
   c+= Math.min( 2*t[1],  t[l - 2] + t[0]) + t[l-1] + t[0];
   l-=2;   
  }
  return c+= l<3?t[l-1]:t[1] + t[0]+t[2];
 }

https://codefights.com/challenge/K4HYozLrbRoLHkt8P

MaxCupCake in codefights

this is good problem.

https://codefights.com/challenge/X33imTX2FSqhSLTtJ


My code is

        int c, i,t;
 int MaxCupCakes(int N, int[] P, int K) {
  for (; i < P.length; i++ ) {
   t= (P[i] -c -1);
   if(K<=t) break;
   K=K-t;
   c=P[i];
  }  
  return c+K<= N ?c+K : -1;  
 }

best code is here

 int MaxCupCakes(int n, int[] P, int k) {
     for(int i:P) 
         if(i<=k)k++;
           
  return  k>n ?-1 : k ;
 }

Max and Caroline, two girls in their mid-twenties, work at a Brooklyn restaurant as waitresses. Together, they dream of starting up their cupcake business.

One day Max comes with a box of N cupcakes numbered according to their quality from 1 to N. Caroline has a list of cupcakes P that should be removed from the box.

Your task it to find the quality of the Kth cupcake after the cupcakes from the list P are removed from the box.

If it is not possible to get the Kth cupcake, return -1 instead.

Example

For N = 4, P = [1] and K = 2, the output should be
MaxCupCakes(N, P, K) = 3.

Initially there were cupcakes of the following quality:
1, 2, 3, 4.
According to P, the cupcake with quality 1 should be removed, so only the following cupcakes are left:
2, 3, 4.
The 2nd cupcake in this list is 3, thus the output should be 3 as well.


[input] integer N

The number of cupcakes, 4 ≤ N ≤ 109.


[input] array.integer P

A sorted array of positive integers, the cupcakes to be removed.
0 ≤ P.length ≤ 500,
1 ≤ P[i] ≤ N.


[input] integer K

A positive integer, the 1-based number of the cupcake to find.


[output] integer

The quality of the Kth cupcake, or -1 if less than K cupcakes are left.

problem 243

hint is EulerPhi / n-1

and second focus is how to short running time~!

topcoder srm 690 div2 medium

이문제를 O(N^2) 이 아닌 방법으로 찾아보려고 하다가 결국에는
O(N^2)방법으로 풀었다.
부등호 하나 잘못 작성해서
system run 에서는 fail ㅠ.ㅠ
다음부터는 조금 더 꼼꼼히 해봐야겠다.,

Minimum coin numbers

this is somehow easy dynamic problem.

this is my python code

coins = [1, 2, 5, 10, 20, 50, 100, 500, 1000]

def find(coins, target):

    list = [];
    for i in reversed(range(len(coins))):
         print(coins[i])
         while target>= coins[i]:
             target = target - coins[i]
             list.append(coins[i])

    return list

list = find(coins, 93 )
print(list)

Topcoder SRM 689 NonDeterministicSubstring

this problem is about

Problem Statement
	You are given two Strings: A and B. Each character in A is either '0' or '1'. Each character in B is '0', '1', or '?'. A string C matches B if we can change B into C by changing each '?' in B either to '0' or to '1'. Different occurrences of '?' may be changed to different digits. For example, C = "0101" matches B = "01??". Note that each character in C must be either '0' or '1', there cannot be any '?' remaining. Consider all possible strings that match B. How many of these strings occur as a (contiguous) substring in A? Compute and return their number. Note that we only count each good string once, even if it has multiple occurrences in A.
Definition
	Class: NonDeterministicSubstring Method: ways Parameters: String, String Returns: long Method signature: long ways(String A, String B) (be sure your method is public)
Limits
	Time limit (s): 2.000 Memory limit (MB): 256 Stack limit (MB): 256
Constraints
-	A will contain between 1 and 50 characters, inclusive.
-	B will contain between 1 and 50 characters, inclusive.
-	Each character in A will be '0' or '1'.
-	Each character in B will be '0', '1' or '?'.
Examples
0)
	"00010001" "??" Returns: 3 There are four strings that match B: the strings "00", "01", "10", and "11". Out of these, the string "11" does not occur in A as a substring. The other three do occur, hence the answer is 3.
1)
	"00000000" "??0??0" Returns: 1 There are 16 different strings that match B, but out of those only the string "000000" is a substring of A.
2)
	"001010101100010111010" "???" Returns: 8 Each of the 8 strings that match B occurs somewhere in A.
3)
	"00101" "??????" Returns: 0 Here, the length of B is greater than the length of A. Clearly, a string that matches this B cannot be a substring of this A.
4)
	"1101010101111010101011111111110001010101" "???????????????????????????????????" Returns: 6

=========================================================
My approach


1. A>B and
2. Find B length
3. Make all possible String with length of B and push HashSet
4. HashSet will filter duplication.
5. and finally only unique strings remain in hashset
6. compare all string with B if index of character is not ?
7. count all if it is match


my code is below

public long ways(String A, String B){
  HashSet<String> set = new HashSet<String>();
  
  int blen = B.length();
  for (int i = 0; i <= A.length()-blen; i++) {
   set.add(A.substring(i, i+blen));
  }
  
  Iterator<String> iter =  set.iterator();
  int count =0;
  while (iter.hasNext()) {
   String str = iter.next();
   boolean found = true;   
   for (int i = 0; i < blen; i++) {
    if(B.charAt(i)!= '?'){
     if(A.charAt(i) != B.charAt(i)){
      found =false;
      break;
     }
    }
   }
   if(found){
    count++;
   }
  }
  return count;
 }

how can we know this array is sorted in java

this is easy example

        int o = a[0] < a[1] ? 0 :1;
 for (int i = 1; i < a.length-1; i++) 
   if( 0!= (a[i] < a[i+1]?0:1) )   return "not sorted";
 return o ==0?"ascending" : "descending";

Project Euler problem 303

My effort to solve it

1. make 3digit generator and divide with n

2. 9999 is never solved in time.

3. find 9, 99, 999, 9999 in pattern.

4. finally solve it in 9s

find the ways to make specific number with dice

this problem is about hexanacci number

               long a = 0,b= 0,c= 0,d= 0,e= 0,f=1, t = 0;
  
  for (int i = 1; i <= n; i++) {
   t = a+b+c+d+e+f;   
   a=b;
   b=c;
   c=d;   
   d=e;
   e=f;
   f=t;
  }
  return t+"";

Hexanacci numbers: a(n+1) = a(n)+...+a(n-5) with a(0)=...=a(4)=0, a(5)=1. 

huffman coding ( encoding and decoding) algorithm in python

this is short code written by python.

Huffman encoding and decoding

I studied using this site and write code 

http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

import random

dic = {}
class MinHeapNode:
    def setNode(self, left, right, freq, char):
        self.left = left
        self.right = right
        self.freq = freq
        self.char = char
        return self
def huffmanCoding(arr, freq):
    heapArr = []

    for i in range(len(arr)):
        heapArr.append(MinHeapNode().setNode(None, None , freq[i], arr[i]))
        print(heapArr[i].freq, heapArr[i].char)

    while(len(heapArr)>1):
       left = heapArr.pop(0)
       right = heapArr.pop(0)
       insertionSort(heapArr, MinHeapNode().setNode(left, right, left.freq+right.freq, left.char + right.char))

    rootheap= heapArr.pop()

    return rootheap


def printHeap(heap, str):
    if heap.left != None:
        printHeap(heap.left, str + '0')

    if heap.right !=None:
        printHeap(heap.right, str + '1' )

    if heap.left == None:
        print(heap.char, str)
        dic[heap.char] = str

def insertionSort(heapArr, heap):
    index = len(heapArr)
    for i in range(len(heapArr)):
        if heap.freq < heapArr[i].freq:
           index  = i
           break
    heapArr.insert(index, heap)

def makeNewString(arr, freq):

    freqcopy = freq[:]
    arrcopy = arr[:]
    strval = ''
    while len(freqcopy) >0:
        number = random.randrange(0,len(freqcopy))
        freqcopy[number] = freqcopy[number]-1        strval = strval + arrcopy[number]
        if freqcopy[number] == 0:
            freqcopy.pop(number)
            arrcopy.pop(number)

    return strval

def endcoding(str):
    strval = ''    for i in range(len(str)):
        strval = strval + dic[str[i]]

    return strval

def huffmandecode(rootheap, strvalencoded):

    index = 0;
    orgstr = '';

    while index < len(strvalencoded):
        str = getchar(rootheap, index, strvalencoded)
        index = index + len(dic[str])
        orgstr = orgstr + str
    return orgstr

def getchar(rootheap, index, strvalencoded):
    if rootheap.left == None:
        return rootheap.char

    number = int(strvalencoded[index])
    if number ==0:
        return getchar(rootheap.left, index+1, strvalencoded)

    if number ==1:
        return getchar(rootheap.right, index+1, strvalencoded)

arr = ['a', 'b', 'c', 'd', 'e', 'f']
freq = [5, 9, 12, 13, 16, 45]
rootheap = huffmanCoding(arr, freq)

printHeap(rootheap, '')

strval  = makeNewString(arr, freq)
print("org     ", strval)

strvalencoded = endcoding(strval)
print("encoded ",strvalencoded)

orgencoded = huffmandecode(rootheap, strvalencoded)
print("decoded ", orgencoded)

problem 293

This problem was some how easy.

Using DFS and Set

I could solve it.

python disjoint set (union find)

# make setdef MakeSet(number):
    return node().set(number)

# find rootdef find(x):
    if x.parent.number == x.number:
        return x
    else:
        return find(x.parent)

# merge two setsdef union(x, y):
    xRoot = find(x)
    yRoot = find(y)
    xRoot.parent = yRoot


class node():
    def set(self, number):
        self.parent = self        self.number = number
        return self
# make setsets = list(map(lambda x:MakeSet(x), range(10)))
for i in range(len(sets)):
    print(sets[i].number, sets[i].parent)

# one set is 0-4 super root is 4for i in range(0, 4):
    union(sets[i], sets[i+1])

# the otehr set is 5~9 super root is 9for i in range(5, len(sets)-1):
    union(sets[i], sets[i+1])

# test for all nodes finding root nodefor i in range(len(sets)):
    print(i ," parent -> ", find(sets[i]).number)

Problem 491

Examples:

Is the number 2547039 divisible by 11?

First find the difference between sum of its digits at odd and even places.

(Sum of digits at odd places) - (Sum of digits at even places)

= (9 + 0 + 4 + 2) - (3 + 7 + 5)

= 15 - 15 = 0

The number is 0, so the number 2547039 is divisible by 11

I approach this problem by using above condition.

1. recursive function

2. combination

my java code is below

package numberFrom400;

import java.util.Arrays;

import euler.util.EulerUtil;

public class number491 {
 
 public static long totalCase = 0;
 
 public static int total = 0;
 
 public static int sum = 90;
 
 public static void main(String args[]){
  
  long start = System.currentTimeMillis();
  int numbers[] = new int[10];
  searching(0, 0, numbers);
  
  System.out.println(totalCase);
  System.out.println(System.currentTimeMillis()-start);
 }
 
 
 public static void searching(int position, int count, int[]arr ){
  if(position>=arr.length){
   if(count == 10){
    // 여기서 시작한다. 왼쪽 섬
    int subsum = 0;
    for (int i = 0; i < arr.length; i++) {
     if(arr[i] != 0){
      int val = i *arr[i];
      subsum += val;
     }
    }
    
    if((subsum -(sum - subsum))%11 ==0){
//     System.out.println("this num is divisible");
//     System.out.println(Arrays.toString(arr));
//     System.out.println(Arrays.toString(reversse(arr)) + " re ");
     // 여기가 Divisible이 가능한 위치
     
     int twocount = 0;
     for (int i = 0; i < arr.length; i++) {
      if(arr[i]== 2){
       twocount ++;
      }
     }
     
     long leftCase = EulerUtil.getFactorial(10)/(long)Math.pow(2, twocount);
     if(arr[0] ==1  ){
      leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount));
     }else if (arr[0] ==2) {
      leftCase = (leftCase - EulerUtil.getFactorial(9)/(long)Math.pow(2, twocount-1));
     }
     
     int[] reverse = reversse(arr);
     
     // right case
     twocount = 0;
     for (int i = 0; i < reverse.length; i++) {
      if(reverse[i]== 2){
       twocount ++;
      }
     }
     
     long rightCase = EulerUtil.getFactorial(10)/(long)Math.pow(2, twocount);
     
     totalCase = totalCase + (leftCase * rightCase );
    }else{
    }
    
    total++;
    return;
   }else if(count > 5){
    return;
   }
   return; 
  }
  
  for (int i = 0; i < 3; i++) {
   
   arr[position] = i;
   searching(position+1, count+i, arr);
   arr[position] = 0;
  }
 }
 
 
 public static int[] reversse (int arr[]){
  int reverse[]= new int[arr.length];
  for (int i = 0; i < arr.length; i++) {
   reverse[i] = 2 - arr[i];
  }
  return reverse;
 }
 
}