## Wednesday, September 9, 2015

### project euler 320 problem

https://projecteuler.net/problem=230

1. A
2. B
3. AB
4. BAB
5. ABBAB
6. BABABBAB
.......

At first, I tired to find some repeated pattern.  between A And B.
Maybe I took one hour to find it.
but the result was failed. there is no pattern and had not to think about findind pattern.
Finally I thought this way.

A :
14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679

B:
82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196

Fibonaci (n) = Fibonaci(n-2) + Fibonaci(n-1);

so make array to put length of F(n);

arr[1] = 100;
arr[2] = 100;
arr[3] = 200;
arr[4] = 300;
arr[5] = 500;

if i want to find 320 I should find from arr[5]
because 500 covered 320 index word.
and find 20 position from arr[4];
arr[4] is made of arr[2] + arr[3]
next find 20 position of arr[2]

if the index of arr[] is 1 or 2, the answer is arr[1 Or to].charIndex(20);

My java code is below.
(Actually It is dirty code, need to be refactored)

```import java.math.BigInteger;
import java.util.ArrayList;

/**
* 처음에는 BB가 중복되서 나오는 숫자의 일정한 패턴이 있는줄 알았다.
* 알고보니 일정한 패턴은 없네..
*
* 그래서 접근하는 방법은 역 Search 방법이다.
* @author ddavid
*
*/
public class number230 {

public static String first ="1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
public static String second ="8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196";

public static BigInteger total = BigInteger.ZERO;

public static void main(String args[]){

long start= System.currentTimeMillis();
real();

System.out.println(System.currentTimeMillis()-start);

}

public static void DAB(long num){
String subFirst = "";
String subSecond = "";
subFirst = first;
subSecond = second;
long val =  num;
System.out.println("val : " + val);

for (int k = 0; k <15; k++) {

String temp =subFirst+subSecond;

subFirst = subSecond;
subSecond = temp;

if(subSecond.length() > val){
System.out.println(subSecond.charAt((int)val-1));
break;
}
}
}

public static void realDAB(long num){
long val =  num;  // 81420679895522450
//  long val =  35;  // 81420679895522450

System.out.println("val  : " + val);
ArrayList<Long> cntList  = new ArrayList<Long>();
while (true) {
long two = cntList.get(cntList.size()-1);
long one = cntList.get(cntList.size()-2);

long sum = one+two;
if(sum > val){
break;
}
}
find(cntList.size()-1, val, cntList, 0);
}

public static void real(){
for (int i = 0; i < 18; i++) {
long val =  (long)(127+19*i)* (long)Math.pow(7, i);  // 81420679895522450
//   long val =  35;  // 81420679895522450

System.out.println("val  : " + val);
ArrayList<Long> cntList  = new ArrayList<Long>();
while (true) {
long two = cntList.get(cntList.size()-1);
long one = cntList.get(cntList.size()-2);

long sum = one+two;
if(sum > val){
break;
}
}
find(cntList.size()-1, val, cntList, i);
}
System.out.println(total.toString());
}

public static void find(int index, long position, ArrayList<Long> cntList, int i){
if(index == 1 || index ==0){
System.out.println("index : " + index + "  position : " + position );

if(index == 0){
System.out.println(first.charAt((int)position -1));
total= total .add(BigInteger.valueOf((long)Math.pow(10, i)).multiply(BigInteger.valueOf(Long.valueOf(first.charAt((int)position -1) +""))) );
}else{
System.out.println(Long.valueOf(second.charAt((int)position -1) +""));
total= total .add(BigInteger.valueOf((long)Math.pow(10, i)).multiply(BigInteger.valueOf(Long.valueOf(second.charAt((int)position -1) +""))) );
}
return;
}
if(position <= cntList.get(index -2)){   // one 위치인경우
find(index-2,  position  , cntList, i);
}else{ // last 위치인경우
find(index-1, position - cntList.get(index -2), cntList, i);
}
}
}
```