Friday 7 September 2012

Operator precedence

Alright, this is my first passage lablled with "coding" although there have been a few MATLAB passage already.

As you can see from the right-hand side of the blog, there's a new label associated with Project Euler -- fun programming and maths challenge and you guys could hv a go for it.

I'm not going to write a long one like I did before, and I'm just going to share a few thoughts about the problem, problem 093 from Project Euler.

And I'm serious: don't copy my code to find the answer. It rips your satisfaction and chance to learn in solving the problem.

The question is: using + - * / () and 4 numbers, we can combine them to give a series of number. For example the number 1 2 3 4 can form 36 numbers. However only 1 ~ 28 are form consecutively, while 29 can't be done. Find 4 number so that the longest chain of number from 1 to n can be formed.

It's hard to list out all possible operations, so are there any methods to kill this problem? The idea here is: there are 3 "main operator" (+ - * /) in the formula, while the bracket change the order of calculation, so we have to find a way to substitute the precedence of calculation.

One should notice that this idea has a high overlapping with the simple programming:
a = 1
a += 1
a *= 2
print a
This gives (1+1)*2 = 4, not 1+1*2 = 3, however we don't even employ bracket there. The point is: when we assign the order of calculation, an array of bracket appears natrually in the calculation.

When we write a program that calculates step by step, like:
a = 520
a += 2
a *= 17
a += -34
a *= (1/17)
print a
It's equivalent to ((((520+2)*17)-34)*1/17)

However there is a problem. Observing the above bracket array you can notice that the brackets are one in another and the big one includes all. There are no separate pair of brackets. To solve this one we need extra method like recursion, but for 4 numbers the only exception is (a+b)*(c+d) as well as (a+b)/(c+d). Let's write a pseudo code here:

define operator(a,b,n) #a,b: numbers to operate, n: operator id (+-*/)
xs = set()
define ord(n) #to find the longest chain
for permutations of possible (a,b,c,d):
for permutations of operator:
xs.add operator(a,operator(b(operator(c,d,i),j),k)
print longest chain's digit

In fact, one of the original version of the related problem does not use 1,2,3,4, but 4,4,4,4. By this program we also verify that 4 4's only gives a chain from 1 to 9.

There are several interesting question

1) When we change the questions to 5 or more numbers, how can we use recursion to deal with the question?
2) When we introduce square and square root as legal operator in the formula how can we deal with the problem? Assume square root and square can only use once on each number (i.e. we can't do x^2 ^2)
This is easy -- for each permutations, set another operator that permutes (1,2,3) to like (1,2,3), (1,2,9), (1,4,9), (1,4,9) and do the operator combinations.

And therefore here's a harder question for you: we allow factorial AND multiple factorials (Two implications: 1: (x!)!, e.g. (3!)! = 720, 2: x!!, please read wikipedia), how can be code this one?

3) In one of the forum I hold before, there's a post asking people to combine seven 4's to form number chains from 1 to n. + - x / () ! multiple !, square, square root are permitted. How long is the chain? I can tell you that the answer exceeds 1000 by manual trials.