GDC Project Euler: problem 191 – Jaroslaw Pawlak

  • Difficulty: Intermediate

  • First solutions:

FIRST

I have tried very dirty brute solution first. I have created a set of Strings and tried to create all possible strings. Then the idea was to simply remove from the set those which contains “AAA” or more than one “L”. Size of set would be the answer. Even though 3^30 is a large number, I did not expect that it will be too large for a computer. But I was wrong: 3^30 strings, each 30 characters long which is at least 60B per string (16 bits * number of characters). It gives almost 11PB memory required… Well, I am not surprised that 6GB RAM was not enough and I got OutOfMemoryError in Java.

SECOND

The second idea was firstly to check the condition before adding a string to the set – if a string contains “AAA” or “L” twice, then do not add it to the set. Size of set would be the answer and no removing would be necessary. Secondly, I realized that the set is redundant at all, as I can use an integer instead and only increase its value by one whenever a string fulfills condition.

private static final int DAYS = 30;
private static int result = 0;
public static void main(String[] args) {

init(“”);
System.out.println(result);

}
private static void init(String x) {

if (x.contains(“AAA”)) {

// no prize

} else if (x.contains(“L”)

&& x.replaceFirst(“L”, “”).contains(“L”)) {

// no prize

} else {

if (x.length() == DAYS) {

result++;

} else {

init(x.concat(“A”));
init(x.concat(“O”));
init(x.concat(“L”));

}

}

}

This solution did not so much memory, the only problem was computation time, which again was much longer than I expected. The answer for 15 days was found in less than 10 seconds, but with each day more, time increases about 3 times. For 30 days it would find a solution in over 4 years… One-minute-problem, right? ;)

THIRD

Main idea remained the same as mentioned before, but because of generality of java String class it was too slow. I have implemented my own String class, dedicated for this problem. One of the optimizations was to check only last three characters before each concatenation – if all three were “A”, stop concatenating in this branch. Java’s String class was always looking through entire String. Second optimization was adding two boolean values to my String: containesOneL and containesTwoL. Lastly, this implementation did not require from me any universal methods, I did not check the correctness of arguments given and so on. It allowed me to achieve the best possible performance for this solution. My entire String class was about 45 lines of code in length.

class MyString {

public static int max = 30;

private char[] values = new char[max];
private boolean containsOneL = false;
private boolean containsTwoL = false;
private int last = -1;

public MyString concat(char value) {

MyString result = new MyString();
System.arraycopy(this.values, 0, result.values, 0, this.values.length);
result.values[result.last = this.last + 1] = value;
result.containsOneL = this.containsOneL;
result.containsTwoL = this.containsTwoL;
if (value == ‘L’) {

if (result.containsOneL) {

result.containsTwoL = true;

} else {

result.containsOneL = true;

}

}
return result;

}

public boolean containsDoubleL() {

return containsTwoL;

}

public boolean containsTripleA() {

return last >= 2

&& values[last] == ‘A’
&& values[last-1] == ‘A’
&& values[last-2] == ‘A’;

}

public int length() {

return last + 1;

}

@Override
public String toString() {

String result = “”;
for (int i = 0; i <= last; i++) {

result += values[i];

}
return result;

}

}

This implementation was able to find an answer in a reasonable time, but exceeded one minute. I had a look on others solutions and found some really interesting – some of them (even in Java) had less than 10 lines of code and obviously no one rewrote String class…

  • Techniques used:

Java program with my own implementation of string class. Later, simple recursion.

  • How much time did it take:

First solution (written in about 30 minutes) required too much memory and was unable to find a solution.

Second solution (applying changes to previous one took about 5 minutes) should be able to find an answer in about 4 years. Ok, so it was also unable to find a solution.

Third, and still not perfect solution, I have been writing for about two hours and it has found a solution in 400 seconds.

Final solution (after I have seen others’ solutions) I have implemented in about 30 minutes and it found an answer in 55 seconds.

Class MyString can be totally removed as there is no need to store previous characters in the string:

private static int count(int a, int l, int length) {

if (a >= 3 || l >= 2) {

return 0;

}
if (length == 0) {

return 1;

}
int r = 0;
r += count(a + 1, l, length – 1); // A
r += count(0, l + 1, length – 1); // L
r += count(0, l, length – 1); // O
return r;

}

An answer is count(0, 0, 30).

  • Problems encountered:

3^30 proved to be too large number for a computer and the program required impossible amounts of memory.

Using all-purpose structure did not achieve necessary performance and implementation of dedicated structure was required.

  • What I have learnt:

As in the previous problem 12 brute solution could not be used for large numbers. Solution using all-purpose structures also did find a solution in a reasonable time. Rewriting parts of this structure and dedicating it to a particular problem only has greatly improved a performance.

About Jaroslaw Pawlak

I have done MSci in Computer Science at King’s College London and currently work as Software Engineer specialising in Java. I spend most of my time in front of computer improving my programming (and other) skills or just relaxing with a good game. I also train some sports but at the moment I am not a member of any club. I love cycling and volleyball, but I have also played a lot of football, tennis and trained martial arts.

Posted on June 9, 2011, in GDC Project Euler Challenge, Project Euler. Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: