The Oldest Plays the Piano

According to the legend, it was abigail the first who started to solve Diophantine equations using regular expressions.

A Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only.

Perl5.10 regexes provide extensions that make much easier to begin to deal with nonlinear Diophantine equations.

The following story sets a mathematical challenge that leads to a system of two Diophantine equations:

Two MIT math grads bump into each other while shopping at Fry’s. They haven't seen each other in over 20 years.

First grad to the second: "How have you been?"
Second: "Great! I got married and I have three daughters now."
First: "Really? How old are they?"
Second: "Well, the product of their ages is 72, and the sum of their ages is the same as the number on that building over there..."
First: "Right, ok... Oh wait... Hmm, I still don't know."
Second: "Oh sorry, the oldest one just started to play the piano."
First: "Wonderful! My oldest is the same age!"

The problem is to know the ages of the three daughters.

The following code uses the matching ('1'x72) =~ /^((1+)\2+)(\1+)$(?{ f($1, $2, $3) })(*FAIL)/ to produce all the solutions of the Diophantine equation x*y*z = 72:

use v5.10;
use strict;
use List::Util qw{sum};

my $product = shift || 72;

local our %u;
sub f {
  my @a = @_;
  @a = sort { $b <=> $a } (length($a[1]), length($a[0])/length($a[1]),
+ $product/length($a[0]) );

  local $" = ", ";
  say "(@a)\t ".sum(@a) unless exists($u{"@a"});
  $u{"@a"} = undef;
}

say "SOL\t\tNUMBER";
my @a =  ('1'x$product) =~
         /^((1+)\2+)(\1+)$
                   (?{ f($1, $2, $3)
                    })
           (*FAIL)
         /x;
[download]

When executed, this program produces the set of triples whose product is 72. The second column contains the potential number on the mentioned building:

$ ./oldestplayspiano.pl
SOL             NUMBER
(18, 2, 2)       22
(12, 3, 2)       17
(9, 4, 2)        15
(8, 3, 3)        14
(6, 6, 2)        14
(6, 4, 3)        13
(36, 2, 1)       39
(24, 3, 1)       28
(18, 4, 1)       23
(12, 6, 1)       19
(9, 8, 1)        18
[download]

Only if the number on that building is 14 there is more than one solution. All other cases produce a single solution. But the first math grad, in spite of having access to the two equations

           x*y*z = 72
           x+y+z = number on that building over there...
[download]

still says:
"Right, ok... Oh wait... Hmm, I still don't know."

Thus the number of the building was 14 and the solution is one of:

             (8, 3, 3)
             (6, 6, 2)
[download]

... but we know the "oldest one just started to play the piano".

Do you know of other "freak" examples of using regexes to solve combinatorial problems?

Comment on The Oldest Plays the Piano Select or Download Code

Replies are listed 'Best First'.
Re: The Oldest Plays the Piano by blokhead (Monsignor) on Sep 22, 2009 at 03:31 UTC
Do you know of other "freak" examples of using regexes to solve combinatorial problems? Here is a list of some that I know about (with an obvious selection bias -- the first three are due to Abigail, and the last three are some of my posts): RE: sieve of erothenes The N-queens problem using pure regexes Perl regular expression matching is NP-complete (offsite) Pure regex Hamiltonian Circuit solution Golf: Buying with exact change The greedy change-making problem using regexes blokhead	[reply]
Re^2: The Oldest Plays the Piano by ambrus (Abbot) on Sep 22, 2009 at 12:15 UTC
There's Re: Simple primality testing which links to an older node prime factorization using base 1. Then there's the amazing dc.sed script which implements arbitrary precision numeric calculations in decimal base in sed – you can find its source here or inside the tarball of gnu sed as a test. I don't really understand how it does the multiplication and division, but I could do the addittion on my own in a slightly more complicated way in Re^2: --- adding a column of integers (it's a loop of four substitutions, dc.sed has two and the teasing comment "could be done in one s/// if we could have >9 back-refs..." which I don't really believe). How about fibonacci numbers? Some snippets like Re: Fibonacci golf with one state variable use regex substitutions but then they're not really using the power of the regex engine. There must be some way to actually use the regular expression engine to generate fibonacci numbers though. Searching yields fibonacci regex and Fibonacci Regex. These test for fibonacci numbers rather than generating them but there's probably some way to convert them. Another idea is to use something like this but probably there's some nicer way to phrase it: `perl -le'$==1,(1x$_)=~/(^)(1\|11\1)*(?{$=++})^/,print$=for 0..20'` [download]	[reply] [d/l]
Re^3: The Oldest Plays the Piano by ambrus (Abbot) on Dec 22, 2009 at 12:09 UTC
See also Explain one liner for fibonacci. Update: Explain Fibonacci one-liner ?? too. Update 2010-07-21: Try this for Catalan numbers: `perl -le'$==0,(1x$_)=~/(^)(\|1(?2)(?2)(?(?{})))$(?{$=++})^/,print$=for +0..13'` [download] Update 2010-11-21: A nicer version for the Catalan numbers: `perl -le'$==0,(1x$_)=~/^(\|()1(?1)(?1)\2)$(?{$=++})^/,print$=for 0..13'` [download]	[reply] [d/l] [select]
Re: The Oldest Plays the Piano by CountZero (Bishop) on Sep 21, 2009 at 22:33 UTC
Solving diophantine equations works in Perl 5.8 as well: `# Solve 12x + 15y + 16z = 281 $_ = 'o' x 281; m/^(o)\1{11}(o)\2{14}(o*)\3{15}$/; print length($1),"\t", length($2),"\t", length($3),"\n";` [download] PS: I did not invent this, but found it somewhere and cannot remember where. CountZero A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James	[reply] [d/l]
Re^2: The Oldest Plays the Piano by didier (Vicar) on Sep 24, 2009 at 19:42 UTC
Very impressive. Could you describe the way the regex engine act to solve this? Many thanks for the answer if any :)	[reply]
Re^3: The Oldest Plays the Piano by CountZero (Bishop) on Sep 24, 2009 at 20:58 UTC
The way I think it works is that the regex-engine starts by grabbing the whole of the string for the first capture and then sees that it cannot match anything anymore and thus starts "giving back" character by character to match the other elements of the regex. As 'x' has to come in blocks of 12 elements, the regex for that variable is `(o*)\1{11}`, being whatever the regex-engine in trying, followed by 11 times that what is being tried for the first capture. 11 + 1 = 12, so you have your '12x'. The same goes for the other variables. Probably inside the regex there are some shortcuts and optimizations, but basically it is just "try everything until you find a solution". CountZero A program should be light and agile, its subroutines connected like a string of pearls. The spirit and intent of the program should be retained throughout. There should be neither too little or too much, neither needless loops nor useless variables, neither lack of structure nor overwhelming rigidity." - The Tao of Programming, 4.1 - Geoffrey James	[reply] [d/l]
Re: The Oldest Plays the Piano by deMize (Monk) on Sep 22, 2009 at 20:10 UTC
Did you deduce the building number just because he "still didn't know" and 14 was the only double? Isn't it possible he didn't know because of other reasons, rather than the available options. Maybe he just couldn't figure out all the options of factors of 72, maybe he couldn't literally see the building number :) Another thing, because the problem gave over 20 years, we can reason that it hasn't been over 30 years. If it was a trick question we couldn't propose that, but the significance of choosing 20 as opposed to 10 or 30 is a significant statement given the nature of the problem. Thus, you can rule out oldest daughters greater than 21. If it had been 20 years since he last saw his friend, he would have known about the eldest daughter. In the options given, the 36 y/o would have been 16 when they last saw each other. I chose 21 because if they were truely friends the one would have known the other's wife was pregnant since he last saw him, thus giving that extra year to know about it, without seeing his friend. Because the problem says "over" 20, you might want to change that 21 i chose above to something like 23 (reason to follow). The next significant number the problem would have said is "over 25." So the actual time should be between 20 and 25. Due to human psychology you can rule out 24 because a person would have said "almost 25" rather than "over 20" - you might argue the same for 23. So, given that assumption, you could reason the actual years since the two have last seen one another is between 21 and 23 :) Given this information, you can modify your formula to rule out any girls that are older than that. Thinking of these other factors is important in math modeling. What if the "oldest playing piano" was "the oldest can now vote?" That 24 and 36 become more significant in eligibility, which we have not selected by reason albeit conjectural and not empirical.	[reply]
Re^2: The Oldest Plays the Piano by casiano (Pilgrim) on Sep 23, 2009 at 07:23 UTC
Did you deduce the building number just because he "still didn't know" and 14 was the only double? Isn't it possible he didn't know because of other reasons, rather than the available options. Maybe he just couldn't figure out all the options of factors of 72, maybe he couldn't literally see the building number :) Maybe. But you have to take into account they are both MIT math grads. I guess here MIT math grads stands for ideally perfect maths (are they? ;-) and so we can presume he is able to solve the system with the two Diophantine equation. The other objection - that he couldn't see the building number - is more serious. I guess any MIT math grad - even if he has myopia and is lazy - has an excess of Perl hubris (As defined by Larry_Wall excessive pride, the sort of thing Zeus zaps you for ...) so that he will do whatever to show off his skills, including to cross the road to look at the number :-).	[reply]
Re^3: The Oldest Plays the Piano by deMize (Monk) on Sep 23, 2009 at 13:06 UTC
Ha. Yes, perhaps in a sane condition he would do just that, but let's not forget that time has taken its toll on him and if he didn't have "A Beautiful Mind" at one time, he might now. Thus, we could also suppose, in such a condition, that he is on medication, which have side effects, one which would displace the hubris instilled in him.	[reply]
Re^2: The Oldest Plays the Piano by markuhs (Scribe) on Oct 16, 2009 at 10:46 UTC
Thinking of these other factors is important in math modeling. And you should also consider, that it is unusual to have children 34 years apart... Not infeasible or unnormal, but unusual... At least that's what I would presume...	[reply]
Re: The Oldest Plays the Piano by spx2 (Deacon) on Sep 24, 2009 at 11:01 UTC
Interesting solution , reminds me of EWD666 where a similar problem is solved(but not with regexes,just pen and paper).	[reply]
Re^2: The Oldest Plays the Piano by grizzley (Chaplain) on Oct 16, 2009 at 12:14 UTC
I have heard the version with six sentences instead of 4, I'll try to find it.	[reply]
Re^2: The Oldest Plays the Piano by Anonymous Monk on Oct 13, 2009 at 19:39 UTC
Now that is very interesting problem. It should be solved with Perl too.	[reply]


go ahead... be a heretic
	PerlMonks