perplexus.info :: Algorithms : Metapuzzle II

Metapuzzle II (Posted on 2023-02-14)

In solving the puzzle Phi Proximity Poser, a computer-minded solver might consider trying every possible configuration of formulae, in RPN form, where numbers are pushed onto a stack, and pulled by the dyadic operations, two of them off the stack at a time, replacing them with the result.

But how many formulae can be made so they can be evaluated, assuming one is going to try all possibilities by brute force? The easy part is that there are 9! ways of ordering the digits; the hard part is the placement of the operations.

Determine the overall number of valid formulae for part I of the Proximity puzzle.

Note: It's not expected that you exclude situations where intermediate results of zero are used as divisors.

As a bonus, do this for part II.

Submitted by Charlie

No Rating

Solution: (Hide)

We need 9 digit and 8 operations in some order.
There are 9! = 362880 ways of arranging the digits.
Then:
s='*********++++++++'; w=uniqueperms(s); length(w) goodCt=0; for i=1:length(w) way=w(i,:); good=true; stackCt=0; for j=1:length(way) if way(j)=="*" stackCt=stackCt+1; else if stackCt<2 good=false; break end stackCt=stackCt-1; end end if good goodCt=goodCt+1; end end goodCt
finds that of the 24310 ways of inserting places for the 8 operations, only 1430 will have 2 operands available in the stack to work on for each of the 362880 ways of arranging the digits.
For each of the ways found so far, there are 4^8 = 65536 ways of choosing the set and order of the operations.
That's 362880 * 1430 * 65536 = 34,007,836,262,400, over 34 trillion formulae possible.
Of course, the RPN equivalent of (1+2)*(3+4) vs (4+3)*(1+2), as part of a larger formula, would be counted separately, as they are different formulae.

Comments: ( You must be logged in to post comments.)

	Subject	Author	Date
	correction to link in puzzle	Charlie	2023-02-22 13:11:03

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (1)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info