This article on Project Euler has to be the best I’ve ever read at explaining my fascination with programming. Definitely worth the read!

# Tag Archives: Java

# Euler Problem 67

As indicated in the problem description, this one is just like #18. The only difference is instead of manually creating an ArrayList of int[], I downloaded the file directly and parsed each line to populate the ArrayList. Here’s the algorithm excerpt from the complete class to execute and display the results.

public void algorithm () { ArrayList<int[]> triangle = new ArrayList<int[]>(); String line = ""; ArrayList<String> list = new ArrayList<String>(); try { URL raw_data = new URL("http://projecteuler.net/project/triangle.txt"); BufferedReader in = new BufferedReader(new InputStreamReader(raw_data.openStream())); while ((line = in.readLine()) != null) { list.add(line); } in.close(); } catch (Exception e) { say(e+"\n"); } say ("Loaded File.\n\n"); say (String.valueOf(list.size())); for (String a : list) { ArrayList<Integer> c = new ArrayList<Integer>(); for (String b: a.split(" ")) { c.add(Integer.valueOf(b)); } int [] d = new int [c.size()]; int x = 0; for (int n: c) { d[x] = n; x++; } triangle.add(d); } for (int i = triangle.size()-2; i >= 0; i--) { int [] row = new int [i+1]; for (int j = 0; j <= i; j++) { int sum1 = triangle.get(i)[j] + triangle.get(i+1)[j]; int sum2 = triangle.get(i)[j] + triangle.get(i+1)[j+1]; if (sum1 > sum2) row[j] = sum1; else row[j] = sum2; } triangle.remove(i); triangle.add(i, row); for (int n : row) say(n+" "); say("\n"); } say("\nAnswer = "+String.valueOf(triangle.get(0)[0])); }

# Euler Problem 65

The trauma I went through on Problem 64 made this one a breeze. I also used BigFractions class from this website.

public String algorithm () { int [] a = new int [100]; a[0] = 2; int k = 1; for (int i = 1; i <= 99; i=i+3) { if (i <= 99) a[i] = 1; if (i+1 <= 99) a[i+1] = 2*k++; if (i+2 <= 99) a[i+2] = 1; } BigFraction F = new BigFraction(a[99],1); for (int i = 99; i >= 1; i--) { F = F.inverse(); F = F.add(a[i-1]); } int sum = 0; String num = F.numerator().toString(); for (int n = 0; n <= num.length()-1; n++) sum += Integer.parseInt(num.substring(n, n+1)); return String.format("\nAnswer = %s\n", String.valueOf(sum)); }

# Euler Problem 64

This one was brutal. Initially I tried writing classes to do Square Roots of BigDecimal and Fractions of BigDecimal. What a Big mess. It was also a learning experience using Regex to find matching patterns in the results. Not pretty and pretty damn slow. My attempts usually ran for 20+ hours at a time.

After three weeks of always getting wrong answers, I started reading mathematical papers. This one caught my eye. Theorem 2.3 shows a method to determine length of a Continued Fraction. The paper even had a super short C routine that I translated for my purposes. No Big Decimal. No Regex. No need to import anything. Kind of embarrassing actually.

Works in about 6 seconds on verbose and 61 miliseconds with no reporting.

public String algorithm () { int count = 0; for (int n = 1; n <= 10000; n++) { if ((int)Math.sqrt(n) == Math.sqrt(n)) continue; int period = period_length(n); if (period % 2 != 0) count++; v.appendText(String.format("n:%d period:%d count:%d\n", n, period, count)); } return String.format("\nAnswer = %s\n", String.valueOf(count)); } public int period_length (int n) { int a_0, a, b, c, b_0, c_0, result=0; a_0 = (int) Math.sqrt(n); b = a_0; b_0 = b; c = n - a_0*a_0; c_0 = c; do { a = (a_0 + b) / c; b = a*c - b; c = (n - b*b) / c; result++; } while ((b != b_0) || (c != c_0)); return result; }

# Euler Problem 63

Ummm, am I missing something here? This worked first try.

public String algorithm () { int count = 0; for (int power = 1; power <= 100; power++) { for (int base = 1; base <= 100; base++) { BigInteger Big = new BigInteger(String.valueOf(base)); Big = Big.pow(power); if (Big.toString().length() == power) { count++; v.appendText(String.format("Count:%d Base:%d Power:%d Value:%s\n", count, base, power, Big.toString())); } } } return String.format("\nAnswer = %s\n", String.valueOf(count)); }

# Euler Problem 62

This one is cool. I figured out two new algorithms that I’m sure will be handy later on.

1) Custom signatures. When comparing long lists, its sometimes easier to create a parallel list of representative tokens. This makes filtering, sorting, counting much easier.

2) Collections can be used to sort lists, but also to count duplicates in them. The frequency method is very fast and useful.

public String Problem () { ArrayList<String> cubeList = new ArrayList<String>(); ArrayList<String> S = new ArrayList<String>(); for (long i = 345; i <= 9999; i++) { String cube = String.valueOf((long)i*i*i); cubeList.add(cube); String sig = ""; int [] d = {0,0,0,0,0,0,0,0,0,0}; for (int c = 0; c <= cube.length()-1; c++) d[Integer.parseInt(cube.charAt(c)+"")]++; for (int n = 0; n <= 9; n++) sig += d[n]; S.add(sig); } String Five = ""; for (String s:S) if (Collections.frequency(S, s) == 5) { Five = s; break; } return String.valueOf(cubeList.get(S.indexOf(Five))); }

# Euler Problem 61

This one seemed tricky, but in the end was a pretty straight forward solution once I simplified the digit checking. The other trick was using my old Permutations class from a previous problem.

public String Problem () { Permutations P = new Permutations(); ArrayList<String> List = P.makePerms("345678"); int sum = 0; int [] s = new int[6]; main: for (String i: List) { for (int n = 0; n <= 5; n++) s[n] = i.charAt(n)-48; ArrayList<Integer> P1 = genList(s[0]); ArrayList<Integer> P2 = genList(s[1]); ArrayList<Integer> P3 = genList(s[2]); ArrayList<Integer> P4 = genList(s[3]); ArrayList<Integer> P5 = genList(s[4]); ArrayList<Integer> P6 = genList(s[5]); for (int p1: P1) for (int p2: P2) if (front(p2) == back(p1)) for (int p3: P3) if (front(p3) == back(p2)) for (int p4: P4) if (front(p4) == back(p3)) for (int p5: P5) if (front(p5) == back(p4)) for (int p6: P6) if (front(p6) == back(p5)) if (back(p6) == front(p1)) { System.out.format("%d+%d+%d+%d+%d+%d=%d\n",p1,p2,p3,p4,p5,p6,p1+p2+p3+p4+p5+p6); sum = p1+p2+p3+p4+p5+p6; break main; } } return String.valueOf(sum); } public int P (int type, int n) { int result = 0; if (type == 3) result = n*(n+1)/2; if (type == 4) result = n*n; if (type == 5) result = n*(3*n-1)/2; if (type == 6) result = n*(2*n-1); if (type == 7) result = n*(5*n-3)/2; if (type == 8 ) result = n*(3*n-2); return result; } public ArrayList<Integer> genList (int type) { ArrayList<Integer> list = new ArrayList<Integer>(); int n = 0; while (P(type,n) < 10000) { if (P(type,n) > 999 && P(type,n) % 100 > 9) list.add(P(type,n)); n++; } return list; } public int front (int p) { return (int) Math.floor (p/100); } public int back (int p) { return p % 100; } public class Permutations { ArrayList<String> Perms = new ArrayList<String>(); public ArrayList<String> makePerms (String s) { Perms.clear(); p1("",s); return Perms; } public void p1(String prefix, String s) { int N = s.length(); if (N == 0) { if (Perms.contains(prefix) == false) Perms.add(prefix); } else for (int i = 0; i < N; i++) p1(prefix + s.charAt(i), s.substring(0, i) + s.substring(i+1, N)); } }