Re: Breaking for loops based on found results

>>>>> "Ståle" == Ståle Undheim writes:

Ståle> The problem here is that the 3rd result I find is actually the
Ståle> correct one, but I end up finding all the palindromes when I
Ståle> just want to find the largest. What I want here is that if a*b
Ståle> is a palindrome, I don't need to examine smaller values of b,
Ståle> and if a*999 is smaller than the biggest palindrome, I don't
Ståle> need to examine further.

It's better to check a*a instead of a*999.

Ståle> Are there ways to implement checks like this? Is there a
Ståle> functional and short way to solve this, or do I need to rewrite
Ståle> to using while loops?

And here's a short, pure-functional solution that is efficient
(takes all three early exits you identified):

def loop1(a:Int,winner:Int):Int =
if(a < 100 || a * a <= winner) winner
else {
def loop2(p:Int):Int =
if(p <= winner) loop1(a - 1,winner)
else if(isPalindrome(p)) loop1(a - 1,p)
else loop2(p - a)
loop2(a * a)
}
loop1(999,0)

Looks something you'd write in your freshman Scheme class, eh?

For comparison, here's the while version:

var winner = 0
var a = 999
while(a >= 100) {
var p = a * a
if(p <= winner) return winner
while(p > winner) {
if(isPalindrome(p)) { winner = p; p = 0 }
else p -= a
}
a -= 1
}
winner

I do not see any elegant way to solve this using for or higher-order
functions while remaining purely functional and taking all three early
exits.

Of all the solutions, I think the one you posted that uses for and a
single var is the most readable.

Seth Tisue wrote:
>>>>>> Ståle> The problem here is that the 3rd result I find is actually the
>>>>>> Ståle> correct one, but I end up finding all the palindromes when I
>>>>>> Ståle> just want to find the largest. What I want here is that if a*b
>>>>>> Ståle> is a palindrome, I don't need to examine smaller values of b,
>>>>>> Ståle> and if a*999 is smaller than the biggest palindrome, I don't
>>>>>> Ståle> need to examine further.
>>>>>>
>>>>>> It's better to check a*a instead of a*999.
>>>>>>
>>>>>>

Seth,

Actually a*a doesn't result in the correct answer. Using a*999 > max
asks the question is there some value in the range a - 999 that might
get me a larger palindrome. Testing for a^2 > max aborts too many
possible values.

Anyway neither of those tests results in a minimum of calls to
isPalindrome. The code below gets the minimum number of tests so far.
The intent is to only test what's necessary to finding minimum values
for the b loop works and is a little more intuitive for me. (actually
keeping the other a*999 < max results in 1 less test but adds a line of
code).

Is there a way to inline minb in the code below? I tried a couple of
things but they didn't work.

def minb(x:Int, y:Int) = if (x == 0) y else (x / y).toInt
var max = 0
var tests = 0;
val palindromes = for {
a <- 100 to 999 reverse;
b <- minb(max, a) to 999 reverse;
c = a*b;
val t:Unit = {tests = tests + 1;}
if (c> max && isPalindrome(c.toString()))
} yield {max=c;max}
println("tests: " + tests)

>>>>> "Brett" == Brett Knights writes:

>>>>>>> It's better to check a*a instead of a*999.

Brett> Actually a*a doesn't result in the correct answer.

You're right. I was looking at my own code and hadn't noticed it
differed from yours in a crucial respect.

Brett> Is there a way to inline minb in the code below? I tried a
Brett> couple of things but they didn't work.

b <- (if(max == 0) a else (max / a)) to 999 reverse

should work, I think