* writing an "artful" algorithm
@ 2003-04-17 15:12 John Stoneham
2003-04-17 22:08 ` Samuel Tardieu
` (3 more replies)
0 siblings, 4 replies; 8+ messages in thread
From: John Stoneham @ 2003-04-17 15:12 UTC (permalink / raw)
For those who like puzzles and have a little bit of free time, you may
want to try your hand at this, and I'd like any input from those who do.
Here is my issue. While throwing together a quick program to solve a
"simple" math puzzle, I realized that, even though the program worked
and produced the desired result, the algorithm itself was *ugly*, with
many nested for-loops and multi-line conditionals. Something like this:
for ...
if ...
for ...
if ...
for ...
if ...
...continue to required depth...
[solution test code]
... close if's and loop's back up to prev. depth...
end if;
end loop;
end if;
end loop;
end if;
end loop;
Each if-condition was more complex than the previous, culminating in a
monstrosity that spanned 7 lines in the body of the "solution test
code", which in total was only an additional dozen or so lines. In
short, the "solution test" was simple, but getting there was ugly. BUT
IT MADE SENSE TO ME AT THE TIME.
So now I'm working on a different puzzle: write the most "artful"
solution to the problem, or, to put it another way, "How would Knuth do
it?" Now, I'm no computer scientist, and I'm certainly not an expert
programmer, but I just feel there is a "better" way to write programs
than this. It's like a person who does multiplication by counting on
their fingers: it works but it sure ain't pretty.
The original math puzzle was based on an extra-credit problem that my
daugher was assigned. For our purposes, I've decided to make the problem
a little different, and here is my revised version (this also keeps the
original problem and solution harder to find for other students):
Find two 5-digit numbers (base 10) whose product is a 10-digit number;
there is the condition that no digit can be repeated in either 5-digit
number, and all the digits in the product must be unique. One
consequence of this condition with the number of digits required in each
number, is that a solution which contains a number with a leading 0 is
valid, even though it "appears" that this number would really be a 4- or
9-digit number. For example, for the two 5-digit numbers, one may use
(13_542 * 60_978) or ([0]9_231 * 84_756) but not (11_235 * 68_879) nor
(12_345 * 56_789), and the product may be 3_245_786_109 or
[0_]987_654_321 but not 1_123_456_789. Find all the solutions.
Going back to my example snippet above, I had decided to represent each
digit as a single integer, and use the for loops to cycle through all
the possible combinations (hence the nested loops). The if-conditions
made sure that digits were not repeated (hence, the deeper the if into
the loops the more complex it was). To construct the 5-digit numbers out
of the digits, the first digit was multiplied by 10_000 and added to the
second which was multiplied by 1_000, etc. The product was deconstructed
in a reverse manner to get its individual digits, which were then
compared with each other to make sure none repeated. Other small details
were checked, such as testing for a leading 0, and products larger than
10 digits, etc, to make sure we had a valid solution, and if so it was
displayed. As I said before, this method made sense to me, and still
does, but the resulting code just looks bad.
This does seem like the imperative way to work out the problem, and I
think just about any other imperative approach would look about the
same, even if it used vectors or records in its representation. It would
still need to test individual digits and generate and test every
possible combination. But what about the functional approach? Would it
be more "artful" here? Would it even be possible to use a functional
approach for such a problem?
Take off your shoes, roll up your sleeves, and feel free to jump in!
--
John S. (to email, reverse the domain)
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: writing an "artful" algorithm
2003-04-17 15:12 writing an "artful" algorithm John Stoneham
@ 2003-04-17 22:08 ` Samuel Tardieu
2003-04-17 22:17 ` Samuel Tardieu
2003-04-18 4:57 ` Steve
` (2 subsequent siblings)
3 siblings, 1 reply; 8+ messages in thread
From: Samuel Tardieu @ 2003-04-17 22:08 UTC (permalink / raw)
John Stoneham wrote:
> For those who like puzzles and have a little bit of free time, you may
> want to try your hand at this, and I'd like any input from those who do.
Job done, thanks, it was fun :)
> Here is my issue. While throwing together a quick program to solve a
> "simple" math puzzle, I realized that, even though the program worked
> and produced the desired result, the algorithm itself was *ugly*, with
> many nested for-loops and multi-line conditionals.
Hopefully, neither nested "for" loops nor multi-line conditionals
are needed (this would be a maintenance nightmare in a big project).
The worst nesting used in my proposed solution is a "if" within a
"for" loop, at the price of several exit points in the two procedures
used.
> Each if-condition was more complex than the previous, culminating in a
> monstrosity that spanned 7 lines in the body of the "solution test
> code", which in total was only an additional dozen or so lines. In
> short, the "solution test" was simple, but getting there was ugly. BUT
> IT MADE SENSE TO ME AT THE TIME.
As soon as you nest two loops, you should stop, look at your code,
look at the problem you are trying to solve and ask to yourself
"what am I doing wrong?". Sometimes, it makes perfect sense, as you
underline. Quite often, it means that the solution you are
implementing may be way too complex.
> Going back to my example snippet above, I had decided to represent each
> digit as a single integer, and use the for loops to cycle through all
> the possible combinations (hence the nested loops). The if-conditions
> made sure that digits were not repeated (hence, the deeper the if into
> the loops the more complex it was). To construct the 5-digit numbers out
> of the digits, the first digit was multiplied by 10_000 and added to the
> second which was multiplied by 1_000, etc. The product was deconstructed
> in a reverse manner to get its individual digits, which were then
> compared with each other to make sure none repeated. Other small details
> were checked, such as testing for a leading 0, and products larger than
> 10 digits, etc, to make sure we had a valid solution, and if so it was
> displayed. As I said before, this method made sense to me, and still
> does, but the resulting code just looks bad.
You have probably added too many checks. As you can see in comments
of my solution, those cases can be automatically handled by the
general algorithm.
In short: do not overcomplicate the problem. Zero does not deserve
any special consideration there.
Disclaimer: this is a quick response to an amusing problem. It can
probably be improved (I mean "shortened" and "factored") a lot by
careful thinking. "To attain knowledge, add things every day; to
obtain wisdom, remove things every day" (Lao Tzu, in _Tao Te Ching_).
Sam
--
Samuel Tardieu -- sam@rfc1149.net -- http://www.rfc1149.net/sam
package Artful is
-- Build with:
-- gnatmake -z -O -gnatp artful
-- Execute with:
-- ./artful
-- Problem description (from John Stoneham <captnjameskirk@moc.oohay> on
-- comp.lang.ada): find all pairs of five digits decimal numbers with
-- all 10 digits used whose product use all 10 digits.
-- Simplification of the problem (with the same result):
-- + eliminate cases where the right term would be bigger than the left
-- term (cut off duplicate results and trim entire branches in
-- resolution tree)
-- + do not test for the number of digits in the result:
-- - if the result has too few digits, duplicate leading zeroes will be
-- detected (as we test 10 successive digits using a shift register)
-- - if the result has too many digits, a duplicate digit will be found
-- + do not test for any special condition (leading zero) on the terms,
-- as we impose 10 digits too, so all 10 will be used (including
-- exactly one zero somewhere)
pragma Elaborate_Body;
end Artful;
with Ada.Text_IO;
package body Artful is
type Term is range 0000000000 .. 9999999999;
Left, Right : aliased Term := 00000;
Used_Digits : array (0 .. 9) of Boolean := (others => False);
procedure Check_Result;
procedure Change_Digit (T : access Term; D : in Term);
------------------
-- Change_Digit --
------------------
-- Digits are changed from the leftmost to the rightmost one,
-- starting with the left term. T is an access to the digit
-- being worked on, D contains the increment corresponding
-- to the digit we are currently working on (10**k).
-- When all the digits of the right term are set, we go
-- to the left term (leftmost digit).
procedure Change_Digit (T : access Term; D : in Term) is
T_Orig : Term;
begin
if Left < Right then
return; -- Cut off symetric cases
end if;
if D = 0 and then T.all /= Left then -- Both terms complete
Check_Result; -- Test product validity
return;
end if;
if D = 0 then -- Left term complete
Change_Digit (Right'Access, 10000); -- Work on right term
return;
end if;
T_Orig := T.all; -- Preserve state
for I in 0 .. 9 loop
if not Used_Digits (I) then -- Digit is not a duplicate
Used_Digits (I) := True; -- Mark digit as used
Change_Digit (T, D/10); -- Next digit
Used_Digits (I) := False; -- Free digit
end if;
T.all := T.all + D; -- Increment current digit
end loop;
T.all := T_Orig; -- Restore original state
end Change_Digit;
------------------
-- Check_Result --
------------------
procedure Check_Result is
Prod : constant Term := Left*Right;
Shifted : Term := Prod;
Used : array (0 .. 9) of Boolean := (others => False);
Digit : Natural;
begin
Shifted := Prod; -- Rightmost digit tested at each pass
Used := (others => False);
for I in 0 .. 9 loop
Digit := Natural (Shifted mod 10);
if Used (Digit) then
return; -- Duplicate digit in product => failure
end if;
Used (Digit) := True;
Shifted := Shifted / 10;
end loop;
Ada.Text_IO.Put_Line ("Result found: " &
Term'Image (Left) &
" * " &
Term'Image (Right) &
" = " &
Term'Image (Prod));
end Check_Result;
begin
Change_Digit (Left'Access, 10000);
end Artful;
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: writing an "artful" algorithm
2003-04-17 15:12 writing an "artful" algorithm John Stoneham
2003-04-17 22:08 ` Samuel Tardieu
@ 2003-04-18 4:57 ` Steve
2003-04-18 5:51 ` tmoran
2003-04-22 20:38 ` Dan Eilers
2003-05-19 23:19 ` John Atwood
3 siblings, 1 reply; 8+ messages in thread
From: Steve @ 2003-04-18 4:57 UTC (permalink / raw)
"John Stoneham" <captnjameskirk@moc.oohay> wrote in message
news:Tvzna.1484$Kb5.65920135@newssvr12.news.prodigy.com...
[snip]
> Find two 5-digit numbers (base 10) whose product is a 10-digit number;
> there is the condition that no digit can be repeated in either 5-digit
> number, and all the digits in the product must be unique. One
> consequence of this condition with the number of digits required in each
> number, is that a solution which contains a number with a leading 0 is
> valid, even though it "appears" that this number would really be a 4- or
> 9-digit number. For example, for the two 5-digit numbers, one may use
> (13_542 * 60_978) or ([0]9_231 * 84_756) but not (11_235 * 68_879) nor
> (12_345 * 56_789), and the product may be 3_245_786_109 or
> [0_]987_654_321 but not 1_123_456_789. Find all the solutions.
[snip]
>
> Take off your shoes, roll up your sleeves, and feel free to jump in!
>
The approach used here is to generate a list containing all 5 digit numbers
containing unique digits. Then sequence through the list generating
products and testing the unique digits condition on the product.
The list of 5 digit numbers is created using the recursive "Gen" routine.
The "Level" argument indicates how many digits have been accumulated into
the "Value". The
"Available" parameter is an array listing the digits that are not contained
in "Value".
This approach generates all combinations of 5 unique digits without ever
comparing digits.
with Ada.Integer_Text_IO;
with Ada.Long_Long_Integer_Text_Io;
with Ada.Text_Io;
procedure CLAexercise is
subtype Digit_Type is Natural range 0 .. 9;
type Digit_Array is array( Positive range <> ) of Digit_Type;
type Five_Unique_Digits_Array_Type is array( 1 .. 99_999 ) of Natural;
Five_Unique_Digits_Array : Five_Unique_Digits_Array_Type;
Number_Of_Five_Digit_Elements : Natural := 0;
Product : Long_Long_Integer;
procedure Gen( Level : Natural; Available : Digit_Array; Value : Natural )
is
begin
if Level = 5 then
Number_Of_Five_Digit_Elements := Number_Of_Five_Digit_Elements + 1;
Five_Unique_Digits_Array( Number_Of_Five_Digit_Elements ) := Value;
else
Gen( Level => Level + 1,
Available => Available( Available'First + 1 .. Available'Last ),
Value => Value * 10 + Available( Available'First ) );
for Idx in Available'First + 1 .. Available'Last - 1 loop
Gen( Level => Level + 1,
Available => Available( Available'First .. Idx - 1 ) &
Available( Idx + 1 .. Available'Last ),
Value => Value * 10 + Available( Idx ) );
end loop;
Gen( Level => Level + 1,
Available => Available( Available'First .. Available'Last - 1 ),
Value => Value * 10 + Available( Available'Last ) );
end if;
end Gen;
function Has_Unique_Digits( Value : Long_Long_Integer ) return Boolean is
type Digit_Bit_Array_Type is array( Long_Long_Integer range 0 .. 9 ) of
Boolean;
Digit_Bit_Array : Digit_Bit_Array_Type := ( others => False );
Test_Value : Long_Long_Integer := Value;
Low_Digit : Long_Long_Integer;
begin
for Iter in 1 .. 10 loop
Low_Digit := Test_Value mod 10;
if Digit_Bit_Array( Low_Digit ) then
return False;
end if;
Digit_Bit_Array( Low_Digit ) := True;
Test_Value := Test_Value / 10;
end loop;
return True;
end Has_Unique_Digits;
begin
Gen( 0, ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ), 0 );
for Left in 1 .. Number_Of_Five_Digit_Elements loop
for Right in 1 .. Number_Of_Five_Digit_Elements loop
Product := Long_Long_Integer( Five_Unique_Digits_Array( Left ) )
* Long_Long_Integer( Five_Unique_Digits_array( Right ) );
if Product > 99_999_999 and then
Product < 10_000_000_000 and then
Has_Unique_Digits( Product ) then
Ada.Text_Io.Put( "Left: " );
Ada.Integer_Text_Io.Put( Five_Unique_Digits_Array( Left ) );
Ada.Text_Io.Put( " Right: " );
Ada.Integer_Text_Io.Put( Five_Unique_Digits_Array( Right ) );
Ada.Text_Io.Put( " Product: " );
Ada.Long_Long_Integer_Text_Io.Put( Product );
Ada.Text_Io.New_Line;
end if;
end loop;
end loop;
end CLAexercise;
Steve
(The Duck)
> --
> John S. (to email, reverse the domain)
>
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: writing an "artful" algorithm
2003-04-18 4:57 ` Steve
@ 2003-04-18 5:51 ` tmoran
0 siblings, 0 replies; 8+ messages in thread
From: tmoran @ 2003-04-18 5:51 UTC (permalink / raw)
> > there is the condition that no digit can be repeated in either 5-digit
> > number, and all the digits in the product must be unique. One
>
> The approach used here is to generate a list containing all 5 digit numbers
> containing unique digits. Then sequence through the list generating
> products and testing the unique digits condition on the product.
Clearly (casting out nines) the product must be a multiple of 9, so
either one of the multipliers is a multiple of 9, ie sum of its digits
mod 9 = 0, or both are multiples of 3, ie, sum of digits mod 3 = 0.
That should reduce the number of trial multiplies.
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: writing an "artful" algorithm
2003-04-17 15:12 writing an "artful" algorithm John Stoneham
2003-04-17 22:08 ` Samuel Tardieu
2003-04-18 4:57 ` Steve
@ 2003-04-22 20:38 ` Dan Eilers
2003-04-23 13:12 ` John Stoneham
2003-05-19 23:19 ` John Atwood
3 siblings, 1 reply; 8+ messages in thread
From: Dan Eilers @ 2003-04-22 20:38 UTC (permalink / raw)
John Stoneham <captnjameskirk@moc.oohay> wrote in message news:<Tvzna.1484$Kb5.65920135@newssvr12.news.prodigy.com>...
> So now I'm working on a different puzzle: write the most "artful"
> solution to the problem, or, to put it another way, "How would Knuth do
> it?" ...
Well, you are in luck. Knuth's techniques for generating permutations
are explained in gory detail in section 7.2.1.2 of The Art of Computer
Programming, (part of the long-awaited Volume 4), and available online
at:
http://www-cs-staff.Stanford.EDU/~knuth/fasc2b.ps.gz
See in particular the answers to exercises 9 and 41.
-- Dan Eilers
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: writing an "artful" algorithm
2003-04-22 20:38 ` Dan Eilers
@ 2003-04-23 13:12 ` John Stoneham
0 siblings, 0 replies; 8+ messages in thread
From: John Stoneham @ 2003-04-23 13:12 UTC (permalink / raw)
Dan Eilers wrote:
> Well, you are in luck. Knuth's techniques for generating permutations
> are explained in gory detail in section 7.2.1.2 of The Art of Computer
> Programming, (part of the long-awaited Volume 4), and available online
> at:
>
> http://www-cs-staff.Stanford.EDU/~knuth/fasc2b.ps.gz
>
> See in particular the answers to exercises 9 and 41.
>
> -- Dan Eilers
Wow, thanks! I did not realize that "previews" of Vol. 4 were online.
I've had an extremely busy week and haven't been able to revisit this
problem, but I look forward to reading through those sections and
exercises, and hopefully I'll be able to take another crack at it this
weekend.
--
John S. (to email, reverse the domain)
^ permalink raw reply [flat|nested] 8+ messages in thread
* Re: writing an "artful" algorithm
2003-04-17 15:12 writing an "artful" algorithm John Stoneham
` (2 preceding siblings ...)
2003-04-22 20:38 ` Dan Eilers
@ 2003-05-19 23:19 ` John Atwood
3 siblings, 0 replies; 8+ messages in thread
From: John Atwood @ 2003-05-19 23:19 UTC (permalink / raw)
John Stoneham <captnjameskirk@moc.oohay> wrote:
>For those who like puzzles and have a little bit of free time, you may
> <snip>
>
>This does seem like the imperative way to work out the problem, and I
>think just about any other imperative approach would look about the
>same, even if it used vectors or records in its representation. It would
>still need to test individual digits and generate and test every
>possible combination. But what about the functional approach? Would it
>be more "artful" here? Would it even be possible to use a functional
>approach for such a problem?
Here's a functional solution to a similar problem:
http://www.cs.nott.ac.uk/~gmh/bib.html#countdown
Graham Hutton. Journal of Functional Programming,
12(6):609-616, Cambridge University Press, November 2002.
We systematically develop a functional program that
solves the countdown problem, a numbers game in
which the aim is to construct arithmetic expressions
satisfying certain constraints. Starting from a formal
specification of the problem, we present a simple but
inefficient program that solves the problem, and prove
that this program is correct. We then use program fusion
to calculate an equivalent but more efficient program,
which is then further improved by exploiting arithmetic
properties.
John
^ permalink raw reply [flat|nested] 8+ messages in thread
end of thread, other threads:[~2003-05-19 23:19 UTC | newest]
Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2003-04-17 15:12 writing an "artful" algorithm John Stoneham
2003-04-17 22:08 ` Samuel Tardieu
2003-04-17 22:17 ` Samuel Tardieu
2003-04-18 4:57 ` Steve
2003-04-18 5:51 ` tmoran
2003-04-22 20:38 ` Dan Eilers
2003-04-23 13:12 ` John Stoneham
2003-05-19 23:19 ` John Atwood
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox