Legal Tender : Puzzles Into Backtracking


Money is *the* prime mover for any society. Apparently, with only a bit of push, monkeys got introduced to currency and soon after they monetised the worlds oldest profession in their society. For mathematicians and alike, though, money is something that historically found it’s place as Natural Numbers, till the advent of finance, where it was put into Continuum. Thus 0.000000001 INR is a valid amount for investment giants, given transaction of such amount happens very frequently ( it does ).

But, as mundane people like us can’t really comprehend such absurdities, we instead focus on children’s puzzles involving money. It is well known fact that in olden days, people used to carry different denominations of currency. It was an abundant practice in India till 2 months ago, when such notions became of the past. While entirely historical in nature, such puzzles involving different denominations of currencies are interesting to solve from a programming interview perspective now:

Given coins of different denominations ( 1, 2, 5, 10 ),  how many ways can you make an amount ‘n’ ?

An obvious problem lies with the statement. To get an amount say “3”, are these options equivalent : 2 + 1 , 1 + 2 ? Only a combinatorial mind would have questions like this, but for common people, there is no difference. Thus we establish that a decomposition in currencies should be defined as a mapping of the form:

{ denomination_used : count_of_amount_used , ... }

Thus, for *3*, there are 2 options using denominations ( 1, 2, 5, 10 ) :

decompose(3) := [ {1:3} , {1:1,2:1} ] 

The problem given now is to write a function decompose(n), which will list the different ways of decomposing the amount *n* using the basic blocks of ( 1,2,5,10 ).

Recursive Thinking to Back Tracking

Standard way of solving this problem is known as back-tracking. Let’s start with having a box of currency and two papers and a pencil, and keep a total amount made. At every step we do the following:

  1. If we can add any of (1,2,5,10) and the total does not exceed *n*, then
  2. Note down the current currency configuration ( decomposition ) in first paper, and then add the amount.
  3. If we have reached exactly *n* already, then in second paper note down the final configuration, only if such a configuration (decomposition) does not exist in the final paper. ( If it exists, then we wasted our time )
  4. Finally, We go back to the first paper, and go back to the last configuration. Then, we try again.

It is this [4] step for which, the idea is given the name back-tracking!

Let’s have a pseudo code for this approach :

AMOUNTS = [ 1, 2, 5, 10 ]

def decompose( current_config, valid_configs, n ){
  // get the current monetary sum of the config
  cur_total = sum( current_config ) -> { $.o.key * $.o.value }
  for ( amount : AMOUNTS ){
    // clone current config 
    config = dict( current_config ,true) 
    config[amount] += 1 // increase count for the denomination
    if ( cur_total + amount == n ) {
      // java HashMap has a bug on hashcode impl, so use string
       config = str( config )
       if ( !( config @ valid_configs) ){
        // new config, add to valids 
         valid_configs += config
       }
    } else if ( cur_total + amount < n ){
      // possible to continue...
      decompose( config , valid_configs , n )
    } 
  }
}

valid_configs = set()
decompose( {1:0,2:0,5:0,10:0} , valid_configs, 4 ) 
println( valid_configs )

Note that, in the above implementation, the approach is recursive, it is very easy to write backtracking this way.

Alternate Thinking, Declarative : Join

Now, there is this problem that we really do not know what our back-tracking code is really tracking. To keep a track on the tracker, we can imagine the following. A configuration, as aptly defined is a map with keys as the denominations, and values are the count of them. Minimum count, for obvious reason for a valid configuration must be 0, and maximum for key must be n/ key. For example, the max for key 10, for *n* = 4 should be 4/10 = 0 ( For computation on natural numbers, if b does not divide a, then a/b = 0 ).

Now, we can visualise the counts in the configuration more clearly :

1 -> [0,1,2,…,n] ; 2 -> [0,1,..,n/2] ; so on and so forth. Possible configurations can be written as :

10  5   2   1  // amounts 
=================
0   0   0   0  // invalid 
0   0   0   1  // not there ...
...
0   0   2   0  // valid and final    

This generates a table (matrix). Above table is a cartesian product of these values ( math guys call them row vectors ).

c1  : [ 0, 1, ..., n  ] 
c2  : [ 0 , ..., n/2  ]
c5  : [ 0 , ..., n/5  ]
c10 : [ 0 , ..., n/10 ]
// options are products of these 
options = c1 * c2 * c5 * c10 

In this format, there are always distinct alternatives we are picking, hence the following declarative code is a perfect symbol of purest form of declarative thinking in its full glory, devoid of any explicit logical constructs or extraneous variables – it simply reads like a mathematical formula ( albeit terse ) :

AMOUNTS = [ 1, 2, 5, 10 ]

def decompose( n ){
  // create a list of ranges to be passed as arguments to the join 
  options_args = list( AMOUNTS ) -> { [0 : n/$.o + 1 ] }
  join( @ARGS = options_args ) :: { // join over the ranges 
    // calculate total from the join result ( tuple ) 
    n == sum( $.o ) -> { AMOUNTS[ $.i ] * $.o }
    // select configuration (tuple) when sum (total) is exactly n 
  }
}
// now print it 
println( decompose( 4 ) )

Wonderful, is not it? Add new denomination, delete them, the code does not change at all! The whole back-tracking problem – we did solve in a fully controlled, non recursive manner which reminds us of SQL! It is way more optimal than the backtracking one. Will it be always possible to convert a problem of backtracking into a join ( or cardinal product ) ? The answer, unfortunately, is NO. Joins can only work with finite sequences, not infinite sequences. Backtracking, however, can go over potentially infinite sequences.

Epilogue

Not convinced? The whole idea of backtracking actually stems from Cantor, and moreover, enumeration of all rational numbers are possible through backtracking. But there are infinite rational numbers. Perhaps this simplistic formulation is not formally accurate, perhaps it is, it should not deter us.

But I don’t have to know an answer. I don’t feel frightened by not knowing things, by being lost in a mysterious universe within any purpose, which is the way it really is, so far as I can tell. It doesn’t frighten me.

Previous Big Data, Kings And Prophets
Next STEVE JOBS : THE 10 YEARS OLD INTRODUCTION OF THE IPHONE AND ITS LASTING EFFECT ON JOURNALISM.

No Comment

Leave a reply

Your email address will not be published. Required fields are marked *