Saturday, February 11, 2017

$7.11

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.

Sunday, February 5, 2017

Dirty Money: Code Challenge

There's a fun coding challenge to follow the dirty money that I discovered recently.

A shady Internet business has been discovered.

The website has been made public by a whistle blower. We have enough evidence about the dirty deals they did. But to charge them we need to get hands on precise numbers about the transactions that happened on their platform.

Unfortunately no record of the transactions could be seized so far. The only hint we have is this one transaction:

fd0d929f-966f-4d1a-89cd-feee5a1c5347.json

What we need is the total of all transactions in Dollar. Can you trace down all other transactions and get the total?

Be careful to count each transaction only once, even if it is linked multiple times. You can use whatever tool works best.

We need a way to extract the dollar amount from the transaction text. The dollars might be specified with period or a comma to represent the decimal point. We use regular expressions to look for the dollar amount and then convert to a number.

: dollars ( str -- $ )
    R/ \$\d*[,.]\d+/ first-match rest
    "," "." replace string>number ;

We will use a hash-set of visited links, and only if the link has not been visited will we http-get the contents of the URL, parse the JSON, and extract the dollar amount of both the transaction and any links it contains. The set of visited links will tell us how many total transactions we traced.

:: transaction ( url visited -- dollars )
    url visited ?adjoin [
        url http-get nip json> :> data
        data "content" of dollars
        data "links" of [ visited transaction ] map-sum +
    ] [ 0 ] if ;

: transactions ( url -- dollars #transactions )
    HS{ } clone [ transaction ] [ cardinality ] bi ;

That's all we need to solve the problem. We can run this with the initial URL and get the answer:

$9064.79 in 50 transactions.