Project Euler #17

[Hunter McMillen]

Hey everyone,

Problem 17 on project euler is this:

If the numbers 1 to 5 are written out in words: one, two, three, four, five,
then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words,
how many letters would be used?

I've written the program and it works for 1 to 5, but when I use 1-1000 im getting an extra 100 letters in my result and im not really sure why.

Here's the code:

  
    /*
	  If the numbers 1 to 5 are written out in words: one, two, three, four, five, 
	  then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.
	  
	  If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, 
	  how many letters would be used? 
     */
	  
	 public class Euler17
   {
      public static String[] ones = 
      { "","one","two","three","four","five","six","seven","eight","nine","ten",
         "eleven","twelve","thirteen","fourteen","fifteen","sixteen","seventeen","eighteen","nineteen"};
   
      public static String[] tens = 
      {"","ten","twenty","thirty","fourty","fifty","sixty","seventy","eighty","ninety"};
   
      public static String[] hundreds = 
      {"","onehundred","twohundred","threehundred","fourhundred","fivehundred","sixhundred",
         "sevenhundred","eighthundred","ninehundred"}; 
   
       public String word(int arg)
      {
         String withAnd = "";
      
         if(arg == 1000)
         {
            return "onethousand";
         }
      
         if(arg < 20)
         {
            return ones[arg];
         }
      
         if(arg < 100)
         {
				//divided arg by 10 gives it the correct index position in the array of tens
				//example: 80 is at position 8 in the tens array
				//80/10 = 8. tens[8] = "eighty"
            return tens[arg/10] + word(arg%10);
         }
      
			// if the number is not an even hundred value i.e 100, 200, 300
			// then you have to add and to it according to the problem specs
			//getting the remainder when divided by 100 allows you to see
			//if the number needs an and
			// ex: 124 % 100 = 24, so the answer would be onehundredandtwentyfour
         withAnd = word(arg % 100);
         
         if(withAnd.length() > 0)
            withAnd = "and" + withAnd;
				
			return hundreds[arg/100] + withAnd;
      }//end word
		
		public int letterCt(int arg)
		{
			System.out.println(word(arg));
			System.out.println(word(arg).length());
			return word(arg).length();
		}
		
		public static void main(String[] args)
		{
			int result = 0;
			
			for(int i = 1; i <= 1000; i++)
			{
				System.out.println("numWord: " + i);
				result += new Euler17().letterCt(i);
			}
			
			System.out.println("Result: " + result);
		}//end main
   }//end Euler17

the result I get is 21224, the actual answer is 21124

Any help would be great.
Thanks,
Hunter.

[Uli Hofstoetter]

"fourty" is misspelled, it should be "forty".

Regards,
Uli

[Adam Michalik]

Wow, Uli, that's a keen eye you have! I've read the code twice and thought to myself "everything seems fine" Didn't think to check the spelling

[Hunter McMillen]

Thank you very much Uli, I cant believe I missed that.

[Uli Hofstoetter]

You're welcome.

But i am not sure, if i should thank you or hate you for pointing me to Euler project, which i did not know before ... i guess it will cost me plenty of time and nerves in the near future ;)

[Campbell Ritchie]

Project Euler is by no means easy. It requires no slight mathematical ability. And you will have to produce a completely different solution for no 17

[Hunter McMillen]

What's wrong with the one above?

[Uli Hofstoetter]

Nothing wrong with your approach, i guess Campbell wanted to challenge my ambition to create my own solution.

[Jesper de Jong]

Project Euler is fun if you like mathematics and programming. So far I have solved problems 1 to 18 and 67. For most of them, I wrote small programs in Ruby instead of Java. My Ruby solution to #17 is pretty similar to your Java solution. (I don't have it here, so I can't post my Ruby program right now...).

Problem #17 is one of the more straightforward (easy) problems, some of the other problems are much harder and require you to think hours about the mathematics to find an efficient algorithm.

[Campbell Ritchie]

Uli Hofstoetter wrote:i guess Campbell wanted to challenge my ambition to create my own solution.

Exactly

[Hunter McMillen]

what was your ruby solution for problem 18 Jesper?

Here's my solution in Ruby:

   
 $tri = [
  [75], 
  [95, 64], 
  [17, 47, 82],
  [18, 35, 87, 10],
  [20, 4, 82, 47, 65],
  [19, 1, 23, 75, 3, 34],
  [88, 2, 77, 73, 7, 63, 67],
  [99, 65, 4, 28, 6, 16, 70, 92],
  [41, 41, 26, 56, 83, 40, 80, 70, 33],
  [41, 48, 72, 33, 47, 32, 37, 16, 94, 29],
  [53, 71, 44, 65, 25, 43, 91, 52, 97, 51, 14],
  [70, 11, 33, 28, 77, 73, 17, 78, 39, 68, 17, 57],
  [91, 71, 52, 38, 17, 14, 91, 43, 58, 50, 27, 29, 48],
  [63, 66, 4, 68, 89, 53, 67, 30, 73, 16, 69, 87, 40, 31],
  [4, 62, 98, 27, 23, 9, 70, 98, 73, 93, 38, 53, 60, 4, 23]
  ]
 
def solve(row, col)
  return 0 if row == $tri.length
  puts "$tri row: #{row} col: #{col} = #{$tri[row][col]}"
  return $tri[row][col] + [solve(row + 1, col), solve(row+1, col+1)].max
end
 
puts solve(0, 0)

Ruby is awesome
Hunter.

[Garrett Rowe]

I can tell you now that that solution, although elegant, will not scale to Problem 67

[Jesper de Jong]

My solution to problem 18 will scale, and also solves problem 67 in a fraction of a second.

Do you want me to post it here? It will spoil the fun of finding it out for yourself...

[Hunter McMillen]

haha, no don't post it, ill figure it out then post mine in the thread.

[Hunter McMillen]

Got it

Height = 100;
$tri  = triangle with 100 rows, i didn't put it all here because its massive
 
 i = Height - 2
 
 def maxNum(num1, num2)
   if(num1 > num2)
    num1
  else
    num2
  end
end


while(i >= 0)
  for j in (0..i)
      $tri[i][j] += maxNum( $tri[i+1][j], $tri[i+1][j+1])
  end
  
  i = i - 1
end


puts "The max path of the triangle from top to bottom is: " + $tri[0][0].to_s

Solves in a few seconds
Hunter.

[Piet Verdriet]

Hunter McMillen wrote:Got it

...

Solves in a few seconds
Hunter.

Well done Hunter! Smart to do this "bottoms up".
; )

[Jesper de Jong]

Here's my Ruby implementation:

#!/usr/bin/env ruby
# Oplossing voor Project Euler problemen 18 en 67

triangle = []

filename = ARGV.length > 0 ? ARGV[0] : "input018.txt"
File.open(filename) {|file| file.each {|line| triangle << line.split.map {|s| s.to_i}}}

while triangle.length > 1
	r = []
	triangle[-2].each_with_index do |n,i|
		r << n + [triangle[-1][i], triangle[-1][i + 1]].max
	end
	triangle[-2].replace(r)
	triangle.delete_at(-1)
end

puts triangle[0][0]

[Garrett Rowe]

And just join in the multi-language parae here, here's my solution in Haskell

reduceT xss = red (reverse xss)
    where
        red yss = case (yss) of
                     [[y]] -> y
                     (x:y:rest) -> red (maxMerge x y : rest)
        maxMerge xs ys = case (xs, ys) of
                          (_, [])            -> []
                          ((x:z:zs), (y:ys)) -> y + max x z : maxMerge (z:zs) ys
                          
parse = map (map read . words) . lines

answer67 = readFile "triangle.txt" >>= putStrLn . show . reduceT . parse

I assure you it made perfect sense to me when I wrote it ~6 months ago, I haven't written a lot of Haskell since then so even I'm having a hard time understanding whats going on in this function. I know I used the bottom up approach, and that it gave me the right answer very quickly. I love writing Haskell but I really hate reading it... go figure.

[Garrett Rowe]

[epilogue] After looking at it for about 5 minutes, I get what I did here. It probably helps that I already knew the algorithm. I really should have used type annotations (optional in Haskell) to help me out. I take back what I said about Haskell, or at least amend it to read "I hate reading someone else's Haskell", with the caveat being that my own code can start looking like someone else's code in about 6 months.[/epilogue]

[Hunter McMillen]

I like yours better than mine Jesper, it uses Ruby functions to solve, mine uses a function i defined and a loop structure found in most languages, I'm new to ruby, I didn't know it had a max function.

Hunter.

[Jesper de Jong]

You didn't know that Ruby had a max function (it's a method of Ruby's class Array)? But you're using it yourself in line 23 of your post above!

You can do very nifty things with Ruby. For example, to add all elements in an array together, you can do this:

sum = array.inject {|m,n| m + n}

Or to multiply them, you can do this:

product = array.inject(1) {|m,n| m * n}

And you can even modify existing classes (this technique is called monkey patching), which allows you to add useful methods to class Enumerable, for example:

class Enumerable
  def sum
    self.inject {|m,n| m + n}
  end

  def product
    self.inject(1) {|m,n| m * n}
  end
end

That will allow you to do things like this:

puts [1, 2, 3, 4, 5].sum
puts (1..10).product

[Martijn Verburg]

Garrett Rowe wrote:[epilogue] After looking at it for about 5 minutes, I get what I did here. It probably helps that I already knew the algorithm. I really should have used type annotations (optional in Haskell) to help me out. I take back what I said about Haskell, or at least amend it to read "I hate reading someone else's Haskell", with the caveat being that my own code can start looking like someone else's code in about 6 months.[/epilogue]

Just try reading C++ that's been converted from Haskell *shudder*, one of my uni profs was just insane .

[Hunter McMillen]

Well, I have a selective memory I suppose. Thanks for the tip about "monkey patching" i didn't know that. The inject method is also a really simplified way to do what java does in like 10 lines so thats cool, I actually just ordered a beginners Ruby textbook, so I should be learning a lot more soon.

Hunter.