Rosetta Code

Solving coin problems: Difference between revisions

Page Discussion

Solving coin problems (view source)

Revision as of 07:19, 25 January 2020

1,447 bytes removed ,  4 years ago
→‎{{header|Perl}}: step 4: remove dead code, reorganize, reformat
(→‎{{header|Perl}}: step 3: cut down on copy/paste boiler-plate, streamline initialization, clarify need for MAXIMA)
(→‎{{header|Perl}}: step 4: remove dead code, reorganize, reformat)
Line 519:
);
 
my $decimal = qr/(?:[1-9][0-9]*\.?[0-9]*)|(?:0?\.[0-9]+)/;
my(@words,@eqns,@vars,@types);
my $float = qr/(?:[1-9][0-9]*\.?[0-9]*)|(?:0?\.[0-9]+)/;
 
sub add_type {
my ($type,$value) = @_;
push @vars, "v_$type: $value";
push @types, $type;
}
 
while (<DATA>) {
chomp;
next if /^\s*$/ or /^\s*#.*$/; # skip blank and comment lines
my($count,$total) = (0, 0);
@words = @eqns = @vars = @types = ();
 
my($count, $total) = (0, 0);
next if /^\s*$/ or /^\s*#.*$/; # skip blank and comment lines
our @words = our @eqns = our @vars = our @types = ();
s/-/ /g; # convert hyphens to spaces
$_ = lc($_); # convert to lower case
 
sub add_type {
# tokenize sentence boundaries
s/ my([\.\?\!]$type,$value) /= $1\n/g@_;
push @vars, "v_$type: $value";
s/([\.\?\!])$/ $1\n/g;
push @types, $type;
# tokenize other punctuation and symbols
}
s/\$(.)/\$ $1/g; # prefix
s/(.)([\;\:\%',¢])/$1 $2/g; # suffix
s/\btwice\b/two times/g;
# Fractions
s/half.dollar(s?)/half_dollar/g;
s/\bone half\b/0.5/g;
s/\bhalf\b/0.5/g;
 
# Step 1: standardize language
# Remove noise words
s/\b(the|a|to|of|i|is|that|it|on|you|this|for|but|with|are|have|be|at|or|was|so|if|out|not|he|she|they|has|do|does)\b\s*//g;
 
s/-/ /g; # convert hyphens to spaces
# Convert English number-names to numbers
$_ = lc($_); # convert to lower case
foreach my $key (keys %nums) { s/\b$key\b/$nums{$key}/eg; }
 
# tokenize sentence boundaries, punctuation, symbols
s/(\d) , (\d)/$1 $2/g;
s/([\d) and (.\d?\!]) /$1 $21\n/g;
s/([\.\?\!])$/ $1\n/g;
s/\$(.)/\$ $1/g; # prefix
s/(.)([\;\:\%',¢])/$1 $2/g; # suffix
 
# fractions/multipliers
s/\b(\d\d) (\d) 100\b/($1 + $2) * 100/eg;
s/half.dollars?/half_dollar/g;
s/\b(\d{1,2}) 100\b/$1 * 100/eg;
s/\b(one )?half\b/0.5/g;
s/\btwice\b/two times/g;
 
# convert English number-names to numbers
s/((?:${num} )*${num})/sum(split(" ",$1))/eg;
foreach my $key (keys %nums) { s/\b$key\b/$nums{$key}/eg }
 
# remove plurals
s/dollar coin/dollar_coin/g;
s/quarters/(quarter|dime|nickel|dollar|coin|bill)s/$1/g;
s/dimespennies/dimepenny/g;
s/nickels/nickel/g;
s/pennies/penny/g;
s/dollars/dollar/g;
s/coins/coin/g;
s/bills/bill/g;
s/(\d+) dollar\b/\$ $1/g;
 
# misc
# Rules for coin problems
s/dollar coin/dollar_coin/g;
# Rule triggers are just regexes
s/(\d+) dollar\b/\$ $1/g;
s/((?:\d+ )*\d+)/sum(split(' ',$1))/eg;
 
# remove non-essential words
add_type("dollar_coin",100) if /dollar_coin/;
s/\b(the|a|to|of|i|is|that|it|on|you|this|for|but|with|are|have|be|at|or|was|so|if|out|not|he|she|they|has|do|did|does)\b\s*//g;
add_type("half_dollar",50) if /half_dollar/;
add_type("quarter",25) if /quarter/;
add_type("dime",10) if /dime/;
add_type("nickel",5) if /nickel/;
add_type("penny",1) if /penny/;
 
# Step 2: assign numeric values to terms
while(/(${float}) (?:times )?as many \$ (\d+) bill as \$ (\d+) bill/g) {
push @eqns, "n_$2 = $1 * n_$3";
}
 
add_type('dollar_coin',100) if /dollar_coin/;
while(/(${float}) (?:times )?as many (\w+) as (\w+)/g) {
add_type('half_dollar',50) if /half_dollar/;
push @eqns, "n_$2 = $1 * n_$3";
add_type('quarter',25) if /quarter/;
}
add_type('dime',10) if /dime/;
add_type('nickel',5) if /nickel/;
add_type('penny',1) if /penny/;
add_type($1, 100 * $1) while /\$ (\d+) bill/g;
 
# Step 3: determine algebraic relationships
while(/(\d+) more (\w+) than (\w+)/g) {
push @eqns, "n_$2 = n_$3 + $1";
}
 
while (/(\d+$decimal) less(?:times )?as many \$ (\wd+) thanbill as \$ (\wd+) bill/g) { push @eqns, "n_$2 = n_$3 * $1" }
while (/($decimal) (?:times )?as many (\w+) as (\w+)/g) { push @eqns, "n_$2 = n_$3 -* $1"; }
while (/(\d+) more (\w+) than (\w+)/g) { push @eqns, "n_$2 = n_$3 + $1" }
}
while (/(\d+) less (\w+) than (\w+)/g) { push @eqns, "n_$2 = n_$3 - $1" }
while (/(\d+) less \$ (\d+) bill than \$ (\d+) bill/g) { push @eqns, "n_$2 = n_$3 - $1" }
 
if (/same number (\w+) , (\w+) (?:, )?and (\w+)/) {
push @eqns, "n_$1 = n_$2";
push @eqns, "n_$2 = n_$3";
}
} elsif(/same number (\w+) and (\w+)/){
push @eqns, "n_$1 = n_$2";
}
 
if (/(\d+) (?:\w+ )*?consists/ or /(?<!\$ )(\d+) coin/ or /[^\$] (\d+) bill/) {
$count = $1; push @vars, "count: $count"
or /(\d+) (?:\w+ )*?,?consisting/
}
or /total (\d+)(?! ¢)/
or /(?<!\$ )(\d+) coin/
or /[^\$] (\d+) bill/
or /number [^\?\!\.0-9]*?(\d+)/) {
$count = $1;
push @vars, "count: $count";
}
 
if (/total (?:\w+ )*\$ ($decimal)/ or /valu(?:e|ing) \$ (${float}decimal)/ or /\$ ($decimal) ((bill|coin) )?in/) {
$total = 100 * $1;
or /valu(?:e|ing) \$ (${float})/
push @vars, "total: $total";
or /\$ (${float}) ((bill|coin) )?in/) {
}
$total = 100 * $1;
push @vars, "total: $total";
}
 
if (/total (?:\w+ )*?(${float}decimal) ¢/) {
$total = $1;
push @vars, "total: $total";
}
 
# Step 4: tally final total value, coin count
# Rules for stamp problems
s/stamps/stamp/g;
while(/(\d+) ¢ stamp/g) { add_type("$1_stamp", $1); }
if(/cost (?:\w+ )*?\$ (${float}) (?!each)/) { $total = 100 * $1; push @vars, "total: $total"; }
 
# sum total, dot product of values and quantities
# Rules for unusual types
my $dot_product = join(' + ', map {"n_$_ * v_$_"} uniq @types);
while(/(\w+) cost \$ (${float}) each/g) { add_type($1, 100 * $2); }
if(/made \$ (${float})/)push {@eqns, $"total = 100$dot_product" *if $1;total pushand @vars, "total: $total"types; }
 
# count of all coins, sum of counts of each coin type
# Rules for bill problems
while(/\ my $trace = join(\d' +) bill/g)', map { add_type("n_$1,_"} 100uniq * $1@types); }
while(/(\d+) times as many \$ (\d+) bill as \$ (\d+) bill/g) { push @eqns, "n_$2count = $1trace" *if n_$3"count and @types; }
while(/(\d+) more \$ (\d+) bill than \$ (\d+) bill/g) { push @eqns, "n_$2 = n_$3 + $1"; }
while(/(\d+) less \$ (\d+) bill than \$ (\d+) bill/g) { push @eqns, "n_$2 = n_$3 - $1"; }
if(/\$ (${float}) in bill/) { $total = 100 * $1; push @vars, "total: $total"; }
 
# Step 5: prepare batch file for external processing, run 'MAXIMA', output results
# Rules for greeting card example
if(/consisting (.+?)costing \$ (${float}) each and (.+?)costing \$ (${float}) each/) {
my ($t1,$v1,$t2,$v2) = ($1,$2,$3,$4);
$t1 =~ s/ $//; $t1 =~ s/ /_/g;
$t2 =~ s/ $//; $t2 =~ s/ /_/g;
add_type($t1,100*$v1);
add_type($t2,100*$v2);
}
 
printf "problem: %s\n", s/\n/ /gr; # condensed problem statement
# Rules for notebook paper example
if(/sells ([^\$]+)\$ (${float}) (\w+) and ([^\$]+)\$ (${float}) (\w+)/) {
my ($t1,$v1,$u1,$t2,$v2,$u2) = ($1,$2,$3,$4,$5,$6);
$t1 =~ s/ $//; $t1 =~ s/ /_/g;
$t2 =~ s/ $//; $t2 =~ s/ /_/g;
add_type($t1,100*$v1);
add_type($t2,100*$v2);
if($u1 eq $u2){
if(/purchased (\d+) ${u1}(?:s|es)? (?:\w+ )*?and paid \$ (${float})/){
$count = $1; push @vars, "count: $count";
$total = 100*$2; push @vars, "total: $total";
}
}
}
 
my $maxima_vars = join("\$\n", uniq @vars);
# Rules ALL coin problems obey...
my $maxima_eqns = '['. join(', ', @eqns) . ']';
# Rule no 1: Total is sum over all coin types of coin value times coin number
my $maxima_find = '['. join(', ', map {"n_$_"} @types) . ']';
# i.e., total = dot product of values and quantities
my $dot = join(" + ", map {"n_$_ * v_$_"} uniq @types);
if($total && scalar @types){ push @eqns, "total = $dot"; }
 
if (@eqns and @vars) {
# Rule no 2: Count of all coins is sum of counts of each coin type
my $tracemaxima_script = join("time +. ",'_' map. {"n_$_"}rand uniq. @types)'.max';
open my $script, '>', $maxima_script or die "Couldn't open temporary file: $!\n";
if($count && scalar @types){ push @eqns, "count = $trace"; }
print $script <<~"END";
$maxima_vars\$
solve($maxima_eqns, $maxima_find);
END
close $script;
 
open my $maxima_output, "/opt/local/bin/maxima -q -b $maxima_script |" or die "Couldn't open maxima: $!\n";
printf "problem: %s\n", s/\n/ /gr; # condensed problem statement
while (<$maxima_output>) {
print "solution: $1\n" if /\(\%o\d+\)\s+\[\[([^\]]+)\]\]/; # only display solution
}
close $maxima_output;
unlink $maxima_script;
 
# Prepare MAXIMA} batchelse file{
print $results "Couldn't deduce enough information to formulate equations.\n"
my $maxima_vars = join("\$\n", uniq @vars);
}
my $maxima_eqns = "[". join(", ", @eqns) . "]";
print $results "\n";
my $maxima_find = "[". join(", ", map {"n_$_"} @types) . "]";
my $maxima_script = "${maxima_vars}\$\nsolve(${maxima_eqns}, ${maxima_find});\n";
if(scalar @eqns && scalar @vars) {
my $temp = time() . "_" . rand() . ".max";
open(TEMP, ">$temp") || die "Couldn't open temp file: $!\n";
print TEMP $maxima_script;
close TEMP;
open(MAXIMA, "maxima -q -b $temp |") || die "Couldn't open maxima: $!\n";
while (<MAXIMA>) {
print "solution: $1\n" if /\(\%o\d+\)\s+\[\[([^\]]+)\]\]/; # only display solution
close MAXIMA;
unlink $temp;
} else {
print "Couldn't deduce enough information to formulate equations.\n"
}
print "\n";
}
 
Line 711 ⟶ 649:
A small child has 6 more quarters than nickels. If the total amount of coins is $3.00, find the number of nickels and quarters the child has.
 
A child'schilds bank contains 32 coins consisting of nickels and quarters. If the total amount of money is $3.80, find the number of nickels and quarters in the bank.
 
A person has twice as many dimes as she has pennies and three more nickels than pennies. If the total amount of the coins is $1.97, find the numbers of each type of coin the person has.
Line 762 ⟶ 700:
solution: n_quarter = 11, n_nickel = 5
 
problem: child 'schilds bank contains 32 coin consisting nickel and quarter . total amount money $ 3.80 , find number nickel and quarter in bank .
 
solution: n_quarter = 11, n_nickel = 21
SqrtNegInf
2,392

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/232048"