## Project Euler

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

### Re: Project Euler

jaap wrote:a = 0-a; might as well be a = -a;, and I'd prefer that kind of statement to numerator *= -1; but those are just quibbles.
Interesting. Yeah, I totally agree with this and I've now changed it in my code. As I said, I'm just learning Java, and I guessed while writing the code that a = -a; was almost certain to work how I thought, but I decided to just play it safe. (I wrote basically all of the code I posted before I did any testing at all...I haven't learned how to do "unit tests" in any simple fashion.)
jaap wrote:You could also use a=Math.Abs(a); instead of if (a < 0) { a = 0-a; }.
Like I said:
Wildcard wrote:I'm sure they are implemented in a Java library somewhere, but doing it myself is helping me learn the ins and outs of Java.
But I know I will need to know the libraries also, so thank you!
jaap wrote:There is an interesting thing about calculating combinations this way. You can swap the f.divided and f.times instructions, and you'll find that your fraction object never has a denominator other than 1.
Haha, good point. I had thought about that earlier but somehow in my head I was thinking of both steps downward, i.e. comb(10,4) as 10/4*9/3*8/2*7/1, in which case the object would have a unit denominator at the end but not necessarily in the middle. But I checked my code again and...duh...I implemented the "divided" in an upward iterator anyways, so you're right. Overflow prevention is what I was going for, but as you said:
jaap wrote:This can overflow in that multiplication in cases where your version would not, but if you are worried about that you can use the gcf function to cast out common factors between i and c, and between i and (n+1-i) before multiplying, just like in your Fraction.times function.
This is a great point. I think I will change my code accordingly, just so comb(n,k) doesn't depend on the Fraction class...which I will admit is an odd dependency. Still, I'm happy I wrote it like this because it was the first custom class I wrote and "Fraction" seems a whole lot less...well, contrived as a class than anything given as an example when I was learning about classes.

Thanks for the pointers!
There's no such thing as a funny sig.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Project Euler

Wildcard wrote:Overflow prevention is what I was going for, but as you said:
jaap wrote:This can overflow in that multiplication in cases where your version would not, but if you are worried about that you can use the gcf function to cast out common factors between i and c, and between i and (n+1-i) before multiplying, just like in your Fraction.times function.
This is a great point. I think I will change my code accordingly, just so comb(n,k) doesn't depend on the Fraction class...which I will admit is an odd dependency. Still, I'm happy I wrote it like this because it was the first custom class I wrote and "Fraction" seems a whole lot less...well, contrived as a class than anything given as an example when I was learning about classes.

Keep in mind though that this is overkill in most cases. It only comes into play if the k*comb(n,k) is larger than what a (signed) long integer can hold. I tend to just use the simple version (which is much faster as it doesn't have the two gcf calls in it), and only worry about overflow later.

By the way, I too have a Fraction class as it certainly is useful for some PE problems. Actually, I also have a class for calculating Comb(n,k) which does it just by building part of Pascal's triangle, and then remembers those numbers. This can come in handy if you need a lot of Comb(n,k) calculations for various n & k, as it can be faster to pre-compute the lot instead of re-computing each time.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

### Re: Project Euler

jaap wrote:Keep in mind though that this is overkill in most cases. It only comes into play if the k*comb(n,k) is larger than what a (signed) long integer can hold. I tend to just use the simple version (which is much faster as it doesn't have the two gcf calls in it), and only worry about overflow later.
A fair point. Actually I started out using int as the type for all the variables involved, but that failed because the actual answer itself (not an intermediate value) was larger than an int. So I switched it all to longs and didn't bother changing the calculation methods.
By the way, I too have a Fraction class as it certainly is useful for some PE problems. Actually, I also have a class for calculating Comb(n,k) which does it just by building part of Pascal's triangle, and then remembers those numbers. This can come in handy if you need a lot of Comb(n,k) calculations for various n & k, as it can be faster to pre-compute the lot instead of re-computing each time.
Nice! Yeah, I'm studying/working on a lot of things concurrently (Cormen et. al., MIT Maths for CS, PE, a Java tutorial) so while I am familiar with the concept of memoization, I haven't yet seen examples in Java nor worked out for myself how best to do it in Java.

Just now I browsed through some PE problems and lit on problem 24, which I solved with paper and an old-fashioned calculator in less than 3 minutes. I think I will still program an implementation in Java of the algorithm I used, though. It's a pretty good one, and I'd like the practice with Java.

@jaap: Would you mind referring me to a simple memoized implementation of a factorial method in Java? That would probably help me a lot, just seeing how the memoization is implemented....

Actually, maybe I do know enough to implement it. I suppose you would have to have it in its own class so a field could memoize the results, right? And then since you want an open-ended number of (very large) results, you probably couldn't use an array, but would have to use an ArrayList of longs. (?)
There's no such thing as a funny sig.

jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

### Re: Project Euler

Wildcard wrote:@jaap: Would you mind referring me to a simple memoized implementation of a factorial method in Java? That would probably help me a lot, just seeing how the memoization is implemented....

Actually, maybe I do know enough to implement it. I suppose you would have to have it in its own class so a field could memoize the results, right? And then since you want an open-ended number of (very large) results, you probably couldn't use an array, but would have to use an ArrayList of longs. (?)

Yes, that's exactly what I did, though in this case it was an ArrayList<ArrayList<Long>> to make it a two-dimensional structure to hold Comb(n,k).

You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

### Re: Project Euler

Wildcard wrote:Thanks for the pointers!

OT: Those pointers don't seem aligned! They don't seem aligned at all!

--edit--

I solved problem 99 with a shellscript oneliner
Spoiler:

Code: Select all

`\$ awk -F, '{printf "%f %d^%d line: %d\n",\$2*log(\$1), \$1, \$2, NR}' < p099_base_exp.txt | sort | tail -n1`
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

Wildcard
Candlestick!
Posts: 253
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

### Re: Project Euler

jaap wrote:<Some Java code with <these mysterious <angle> brackets.>>

So far I have not come across an adequate explanation for those angle brackets in Java. It would help if I knew what to search for...what are they even called? Generics? Or mappings? Or what? (EDIT: Never mind, I'm figuring it out.)

I learned file I/O for Java well enough to do problem 8 as follows:
Spoiler:

Code: Select all

`public static long solveEuler8(String fileName, int num) throws IOException {    //Returns the maximum product of (num) consecutive digits from the given file.    //Non-digit characters are ignored.  0 is not.        BufferedReader in = new BufferedReader(new FileReader(fileName));        long maxProduct = 0;        int list[] = new int[num];    int index = 0;    boolean listFilled = false;    long runningProduct = 1;        for (int nextChar = in.read(); nextChar != -1 ; nextChar = in.read()) {        int nextNum = digitToValue(nextChar);        if (nextNum == -1) continue;    //ignore line breaks and non digit chars        if (nextNum == 0) {            index = 0;            listFilled = false;            runningProduct = 1;            continue;        }        if (listFilled) runningProduct /= list[index];        runningProduct *= nextNum;        list[index] = nextNum;        index++;        if (!listFilled && (index != num)) continue;        listFilled = true;        index %= num;        maxProduct = (maxProduct > runningProduct) ? maxProduct : runningProduct;    }    in.close();    return maxProduct;}public static int digitToValue(int c) {    // This could just as easily accept a "char" value.    if (c < '0' || c > '9') return -1;    return (c - '0');}`
The nested conditionals kept my head spinning for a bit—at one point I was three "if" blocks deep. Then I refactored it all to this. And, it all ran correctly first try!

EDIT: Disappointed in problem 9; I don't even see how I would code it, it's so easy to solve on paper. To be fair, I wouldn't have thought so if I hadn't played with pythagorean triplets before.
Spoiler:
Given:
A^2 + B^2 = C^2
A+B+C = 1000
A, B, C are whole numbers

Find:
A*B*C

A = 2pq
B = p^2 - q^2
C = p^2 + q^2
p > q
p, q are whole numbers

A+B+C = 2p^2 + 2pq = 1000
p^2 + pq = 500
p(p+q) = 500 and p > q, so p+q < 2p.

Factors list:
1*500
2*250
4*125
5*100
10*50
20*25

p = 20
q = 5
There's no such thing as a funny sig.

Thesh
Posts: 6577
Joined: Tue Jan 12, 2010 1:55 am UTC

### Re: Project Euler

Well, you can always brute force the solution. There are more eloquent mathematical solutions, but sometimes you won't know them and you either need to figure out the math or just write the brute force solution.
Summum ius, summa iniuria.

Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

### Re: Project Euler

(offtopic)

Wildcard wrote:

Code: Select all

`   public static long comb(int n, int k) {            if (n-k < k) {         return comb(n, n-k);      }      Fraction f = new Fraction(1,1);      for (int i = 1; i <= k; i++) {         f.divided(i);         f.times(n+1 - i);      }      return f.getNumerator();   }//I'm not showing the class this method is in because it's irrelevant.public class Fraction {   public Fraction(long numerator, long denominator) {      super();            if (denominator > 0) {         this.numerator = numerator;         this.denominator = denominator;         } else {         this.numerator = -numerator;         this.denominator = -denominator;      }            long gcf = gcf(numerator, denominator);      if (gcf > 1) {         numerator /= gcf;         denominator /= gcf;      }   }      private long numerator;   private long denominator;      public long getNumerator() {      return numerator;   }      public long getDenominator() {      return denominator;   }      public double value() {      double num = numerator;      double den = denominator;      return num/den;   }      public void times(long n) {      long gcf = gcf(n, denominator);      if (gcf > 1) {         n /= gcf;         denominator /= gcf;      }      numerator *= n;   }      public void divided(long n) {      long gcf = gcf(n, numerator);      if (gcf > 1) {         n /= gcf;         numerator /= gcf;      }      denominator *= n;      if (denominator < 0) {         numerator *= -1;         denominator *= -1;      }   }      public void times(Fraction f) {      long numer = f.getNumerator();      long denom = f.getDenominator();            long gcf1 = gcf(numerator, denom);      long gcf2 = gcf(numer, denominator);      if (gcf1 > 1) {         numerator /= gcf1;         denom /= gcf1;      }      if (gcf2 > 1) {         numer /= gcf2;         denominator /= gcf2;      }            numerator *= numer;      denominator *= denom;   }      public void divided(Fraction f) {      this.times(f.reciprocal());   }      public Fraction reciprocal() {      Fraction f = new Fraction(denominator, numerator);      return f;   }      public static long gcf(long a, long b) {      if (a < 0) {         a = 0-a;      }      if (b < 0) {         b = 0-b;      }      if (a > b) {         long temp = a;         a = b;         b = temp;      }      if (a == 0) {         return b;      }      return gcf(b % a, a);   }   @Override   public String toString() {      if (denominator == 1) {         return Long.toString(numerator);      }      return numerator + "/" + denominator;   }}`
This (Fraction) is the first custom class I have written in Java. (I mean, the first class that's actually designed to be instantiated. Of course everything is in a class in Java. But you know what I mean.)

Anyone see any holes in it?

This is poor interface design, as explained in chapter 2 (page 8-23) of this paper. For some reason it does seem to be a common pattern in Java, though. The paper is about C++ so not everything in that chapter is relevant for you, but it still highlights some problems with the (naieve) consistent use of getter/setter functions that also apply to Java.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Project Euler

Jplus wrote:(offtopic)

Wildcard wrote:This (Fraction) is the first custom class I have written in Java. (I mean, the first class that's actually designed to be instantiated. Of course everything is in a class in Java. But you know what I mean.)

Anyone see any holes in it?

This is poor interface design, as explained in chapter 2 (page 8-23) of this paper. For some reason it does seem to be a common pattern in Java, though. The paper is about C++ so not everything in that chapter is relevant for you, but it still highlights some problems with the (naieve) consistent use of getter/setter functions that also apply to Java.
I'll be honest. I only quickly skimmed your link, but I noticed literally nothing in it that I think is applicable to a rational class in Java, other than a missing equals() method... I'm not even sure I see anything additional that I would say is applicable to a rational class in C++.

-----

My main comment other than missing equals is that your times/divided functions should not mutate, but should return a new Fraction object with the computed value. You could create new functions, say timesAssign or something like that, that mutate this. I think this will much better match expectations and behavior of most numeric classes in Java.

Others comments: a Fraction(long x) constructor (equivalent to Fraction(x, 1)) would be useful. value could be renamed to doubleValue to match the function in java.lang.Number. I don't like the name divided; it doesn't match times in tense; I don't really like anything, but I'd probably go with div even though I often dislike abbreviations.

Finally, I didn't look for actual bugs, so don't take this as me saying there aren't any.

Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

### Re: Project Euler

Increasingly offtopic, so spoilered.
Spoiler:
EvanED wrote:
Jplus wrote:This is poor interface design, as explained in chapter 2 (page 8-23) of this paper. For some reason it does seem to be a common pattern in Java, though. The paper is about C++ so not everything in that chapter is relevant for you, but it still highlights some problems with the (naieve) consistent use of getter/setter functions that also apply to Java.
I'll be honest. I only quickly skimmed your link, but I noticed literally nothing in it that I think is applicable to a rational class in Java, other than a missing equals() method... I'm not even sure I see anything additional that I would say is applicable to a rational class in C++.

Pages 9-11 are approximately 100% applicable to rational classes (or prototypes/interfaces/what have you) in C++, Java, C#, PHP, JavaScript, Python, Ruby, Scala and any other language with object encapsulation that you may think of. For that matter, it is applicable to any class/prototype/interface whatsoever. The entire paper has a very broad scope and the message of chapter 2 is essentially this: the getter/setter idiom is an antipattern because it is inherently nonorthogonal. It's just a coincidence that the specific example is not a rational class.

(It's not a coincidence that the example as well as the rest of the paper is in C++ rather than Java, because the author designed the STL. Still, the underlying idea is general enough to apply to any language.)
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Contact:

### Re: Project Euler

Spoiler:
Jplus wrote:the getter/setter idiom is an antipattern because it is inherently nonorthogonal. It's just a coincidence that the specific example is not a rational class.
I don't think that's there at all! He's not saying getter/setters are bad, he's saying think about what your design is and the consequences it has for how you can use it, and that getters/setters play into that. For example, his final design has a getter -- size! Let's look at his arguments about his vector class. He argues (1) there's not really a downside to exposing references to the things in the vector ("But I do not know a single realistic scenario when hiding memory locations inside our data structure helps and exposure hurts") and (2) not doing so severely limits what you can do. For rationals, I think the first is unequivocally false and the second is probably false.

(1) In the case of the vector, the vector doesn't impose any invariants on the things it holds. A rational design of a Rational class (sorry) does: that the number is stored in reduced form. There is no downside to letting the client arbitrarily modify the stuff in the vector, but allowing arbitrary modification to the Rational's fields would allow its invariants to break. That's a big downside and the main reason you want encapsulation in the first place. (Note that vector does not expose either the pointer or size directly, because it needs to maintain the invariant that each vector owns the array whose size is stored in that vector!)

(2) He gives two examples (sort and swap) of algorithms that might want to work on elements of the vector, both of which benefit from being able to mutate the vector's array's contents directly. But what would be the analogous thing that you would want to with the numerator and denominator of your Rational? Really, about the best thing I can think of is to take the reciprocal with swap(r.numer, r.denom), which I see as pretty unconvincing. It's also basically impossible to do in Java, which means that you "couldn't" design your interface to allow that anyway. In addition, if you were to take the (very very very reasonable) design that your Rationals should be immutable, there's basically guaranteed to be no benefit to exposing the fields directly.

C++, Java, C#, PHP, JavaScript, Python, Ruby, Scala and any other language with object encapsulation that you may think of
But it's not! You know how I know? Because if you were to write a vector class in at least Java, the original interface he presents and it would be the right decision! Why? Because you can't write a indexing function that returns a reference to the indexed element, because the language doesn't give you the tools to do that! But that's OK in this case (at least for sort), because the sort function knows to call get and set. Demanding that something that you want to sort supports that interface isn't any more restrictive that demanding that what you want to sort supports operator[] that you can assign to, it's just different. The language in question absolutely has dramatic effects on what API choices are good or bad, both because of the language's power and because of conventions and libraries that have built up around it. operator[] was the right choice for std::vector, but get/set is the right choice for java.util.List.

(That being said, because of what I wrote above a C++ rational class with basically the same interface as Wildcard's, modulo some things like providing operator * instead of times() but retaining numerator/denominator getters that don't return references, would be the right way to go most of the time.)

Jplus
Posts: 1721
Joined: Wed Apr 21, 2010 12:29 pm UTC
Location: Netherlands

### Re: Project Euler

Alright, you convinced me.
"There are only two hard problems in computer science: cache coherence, naming things, and off-by-one errors." (Phil Karlton and Leon Bambrick)

coding and xkcd combined

(Julian/Julian's)