狗爺語錄

During old Orkut days, I had been diving into a challenging yet simple mathematical problem. It all starts from the statement: use 4 4’s to form 44, with arithmetic operators or joining digits together. Of course, the answer is simple:

44+4-4=44
44*4/4=44

There are lots of similar answers. And the fun starts from here: what if the answer is not 44, but any other positive integer? What if the 4 basic digits are not all 4’s, but all possible single digits? For example: use 2,6,7,9 to form 21. So a Japanese and me started the mind boggling marathon, finding answers from 1 to 100. It was a lengthy journey, and when we have finally gone through every integer, I wrote a simple Perl script to check the results (If you want to save it, please rename it to check-rpn.pl) (The code is posted below instead of storing it as file). It makes use of Perl Math::RPN module and dc so that I don’t need to handle any parenthesis. Although not well written, it is sufficient for my purpose.

However, the problem is, I didn’t save the result The results are still kept in my hard disk, but are quite large to post. After verification, I found that both of us missed 3 solvable integers.

The code

#!/usr/bin/perl -w

use strict;
use Math::RPN;

# this is the desired result
my $result=10;

my @output = `which dc 2>/dev/null`;
@output or die "dc not found, can't run script.\n";

my @operator=qw(+ - * / j);

foreach my $i (0..9) {
  foreach my $j (0..9) {
    foreach my $k (0..9) {
      foreach my $l (0..9) {
	foreach my $a (@operator) {
	  foreach my $b (@operator) {
	    foreach my $c (@operator) {

		# first 2 must be number, and last one must be operator
		# it's impossible to have both 3rd and 4th fields as operator
		my @combination = (
			"$i,$j,$k,$l,$a,$b,$c",
			"$i,$j,$k,$a,$l,$b,$c",
			"$i,$j,$a,$k,$l,$b,$c",
			"$i,$j,$k,$a,$b,$l,$c",
			"$i,$j,$a,$k,$b,$l,$c"
		);
		foreach my $expression (@combination) {
		  next if ($expression =~ /0,\//);
		  next if (($expression =~ /[^\d],j/) || ($expression =~ /[^1-9j],\d,j/));
		  my $expreal = $expression;
		  $expreal =~ s/,(\d),j/,10,*,$1,+/g;

		  # use dc to check division by zero, because perl script
		  # will bail out if it encounter division by zero.
		  if ($expreal =~ /[^\d],\//) {
		    my $expdc = $expreal;
		    $expdc =~ s/,/ /g;
		    my $check = `echo '$expdc' | dc 2>&1 1>/dev/null`;
		    next if ($check =~ /divide by zero/);
		  }

		  my $ans = rpn ($expreal);
		  print join("", sort ($i, $j, $k, $l)).": ".$expression."\n" if ($ans == $result);
		}

	    }
	  }
	}
      }
    }
  }
}

2006-05-24 Update: avoid usage of latex plugin when I don’t need to.

2006-05-28 Update: The Japanese guy is Katsutoshi Seki. He is quite a nice guy and was popular among very active Orkut users. Until Brazilian ‘take over’ Orkut, that is.