#!/usr/local/bin/perl6 # Find expressions involving four 9s that evaluate to various # non-negative integers. Expressions can involve the operators # +,-,*,/ and %, and may use as many parentheses as they like. # # Since the search space is sufficiently small, this program # uses an exhaustive search to evaluate all possible expressions # involving four 9s. It also takes advantage of Perl 6's rational # arithmetic to allow intermediate expressions to sometimes not # be integral, as long as the final result is. (ie. 9/9/9*9) my @Found; sub show_all(Int \$limit) { for 0..\$limit { if @Found[\$_].defined { say "\$_ = @Found[\$_]" } else { say \$_; } } exit(0); } sub record(Str \$exp is copy, Rat \$val) { my Int \$vi = \$val.Int; if 0 <= \$vi && \$vi == \$val && !@Found[\$vi].defined { \$exp ~~ s:g/\(9\)/9/; # Minor easy cleanup @Found[\$vi] = \$exp; } } my @seen; sub dfs(Str \$exp, Rat \$val, Int \$nines, Bool \$neg_ok) { # If we have all four 9s, try recording this expression. if !\$nines { record \$exp, \$val; return; } # Optimize away redundant search trees return if @seen[\$nines].{\$val.perl}++; # Try a few creative ways of adding two 9s to the expression if \$nines >= 2 { dfs("\$exp + 9 / 9", \$val + 1, \$nines - 2, True); dfs("\$exp + 9 * 9", \$val + 81, \$nines - 2, True); dfs("\$exp - 9 / 9", \$val - 1, \$nines - 2, False); dfs("\$exp - 9 * 9", \$val - 81, \$nines - 2, False); dfs("9 / 9 - (\$exp)", 1 - \$val, \$nines - 2, False) if \$neg_ok; dfs("9 * 9 - (\$exp)", 81 - \$val, \$nines - 2, False) if \$neg_ok; dfs("(\$exp) / (9 + 9)", \$val / 18, \$nines - 2, \$neg_ok); dfs("(\$exp) * (9 + 9)", \$val * 18, \$nines - 2, \$neg_ok); dfs("(\$exp) * (9 - 9)", 0/1, \$nines - 2, False); dfs("(\$exp) * 9 / 9", \$val, \$nines - 2, \$neg_ok); dfs("(9 + 9) / (\$exp)", 18 / \$val, \$nines - 2, \$neg_ok) if \$val != 0; dfs("(9 + 9) * (\$exp)", 18 * \$val, \$nines - 2, \$neg_ok) if \$val != 0; } # Try adding exactly one 9 to the expression dfs("\$exp + 9" , \$val + 9, \$nines - 1, True ); dfs("\$exp - 9" , \$val - 9, \$nines - 1, False ); dfs("9 - \$exp" , 9 - \$val, \$nines - 1, False ) if \$neg_ok; dfs("(\$exp) * 9", \$val * 9, \$nines - 1, \$neg_ok); dfs("(\$exp) / 9", \$val / 9, \$nines - 1, \$neg_ok); dfs("(\$exp) % 9", \$val % 9, \$nines - 1, True ); dfs("9 / (\$exp)", 9 / \$val, \$nines - 1, \$neg_ok) if \$val != 0; dfs("9 % (\$exp)", 9 % \$val, \$nines - 1, \$neg_ok) if \$val != 0; # Try adding no new 9s to the expression as a last resort dfs(" -(\$exp)", -\$val, \$nines, False) if \$neg_ok; } sub MAIN(\$limit) { dfs("9 / 9", 1/1, 2, True); dfs("9 - 9", 0/1, 2, False); dfs("9 + 9", 18/1, 2, True); dfs("9", 9/1, 3, False); show_all(\$limit.Int); }