Re: Factor

Today, someone blogged about a fun problem:

“A mathematician purchased four items in a grocery store. He noticed that when he added the prices of the four items, the sum came to $7.11, and when he multiplied the prices of the four items, the product came to $7.11.”

In some ways, this is similar to the SEND + MORE = MONEY problem that I blogged about awhile ago. You can always approach this problem with an direct and iterative solution, but instead we will use the backtrack vocabulary to solve this problem with less code.

We’ll be solving this exactly, using integer “numbers of cents”, progressively restricting the options, and then calling fail if the solution is not found, so we check the next. The first valid solution will be returned:

:: solve-711 ( -- seq )
    711 <iota> amb-lazy :> w
    711 w - <iota> amb-lazy :> x
    711 w - x - <iota> amb-lazy :> y
    711 w - x - y - :> z

    w x * y * z * 711,000,000 = [ fail ] unless

    { w x y z } ;

Using it, we get our answer:

IN: scratchpad solve-711 .
{ 120 125 150 316 }

And that is: $1.20, $1.25, $1.50, and $3.16.