Programming tools philosophy.

Alex Tweedly alex at tweedly.net
Thu Oct 27 17:02:12 EDT 2005


Mark Wieder wrote:

>Steve-
>
>Wednesday, October 26, 2005, 11:48:00 PM, you wrote:
>
>  
>
>>>"What is the largest integer whose digits are all different (and do
>>>not include 0) that is divisible by each of its individual digits?"
>>>      
>>>
>>The biggest I get is 864312, have not tested all yet.  12346789  
>>through 98764321 does not yield a result.
>>    
>>
>
>Thanks, but I'm actually more interested in the program that finds the
>answer than in the result itself. Can you show your work?
>  
>
Warning - I have both my code and my reasoning below ..... so don't 
scroll down and read it unless you don't mind seeing that already ...



















Well, I decided to do some more analysis first ...

(As Petzold said :

If the answer contains a 5, then it cannot contain any even digit, so 
the max possible value would be <= 97531.
So we can safely assume there is no '5', provided the final result is > 
97531.


That leaves us 8 digits, 98764321.
If the final answer includes the digit '9', then the sum of its digits 
must also be divisible by 9.
The ones we have add up to 40 - so we'd need to drop the 4 (or drop 
multiple digits).
If we dropped the 9, the max value would be <= 8764321

Assume we instead drop the 4 - and provided we get an answer > 8764321 
that is an OK assumption.

That's as far as I can go with analysis. Time for some brute force.

We can either construct possible answers (just from the digits left) and 
test them against the other criteria, or simply construct numbers and 
test them against all criteria, including these one. I decided on the 
latter - probably faster to construct numbers in a repeat loop.

The answer is

> 9867312  is OK
> 1002 229 208 68

This is large enough to validate the assumptions above; the last number 
is the time taken, i.e. 68 milliseconds !!
CP's version (in ANSI C) took "< 1 second"
Who says interpreted langauges are slow ?   <LOL>

The other numbers output are explained in the code below:

> --> all handlers
>
> on mouseUp
>     
>     put 0 into tCount1   -- numbers considered
>     put 0 into tCount2   -- numbers which pass first filter : no 0,5,4
>     put 0 into tCount3   -- numbers which pass "repeated digit" test
>     put the millisecs into tStart
>     repeat with tNum = 9876321 down to 1 step -9
>         add 1 to tCount1
>         if "0" is in tNum then next repeat
>         if "5" is in tNum then next repeat
>         if "4" is in tNum then next repeat
>         add 1 to tCount2
>         put true into possible
>         repeat with i = 1 to the number of chars in tNum
>             put char i of tNum into c
>             if c is in char i+1 to -i of tNum then
>                 put false into possible
>                 exit repeat
>             end if
>             add 1 to tCount3
>             if (tNum / c) is not an integer then
>                 put false into possible
>                 exit repeat
>             end if
>         end repeat
>         -- oh for a "exit repeat <name>" or equivalent !!
>         if possible then exit repeat   
>     end repeat
>     put tNum && " is OK" & cr after msg
>     put tCount1 && tCount2 && tCount3 && the millisecs - tSTart & cr 
> after msg
> end mouseUp




-- 
Alex Tweedly       http://www.tweedly.net

-------------- next part --------------
No virus found in this outgoing message.
Checked by AVG Free Edition.
Version: 7.1.361 / Virus Database: 267.12.5/149 - Release Date: 25/10/2005


More information about the use-livecode mailing list