CareerCup

// ZoomBA
def ways_to_dist( target_value ){
   count = 0
   q = list() // create a queue
   q.enqueue ( [0,0,list(0)] ) // add to it
   // now the loop
   while ( !empty(q) ){
     #( prev_inc , cur_sum , path ) = q.dequeue()
     continue ( cur_sum > target_value ) // obvious, nothing else can do
     continue ( cur_sum == target_value  ) {
       println( path ) // for debug diagnostic
       count +=1 // increment possible scenarios
     }
     for ( inc : [1,5,10,25 ] ){
        if ( inc >= prev_inc ){ // ensure sorted path
           q.enqueue( [ inc , cur_sum + inc , path + inc  ] )
        }
     }
   }
   return count
}
println ( ways_to_dist( 42 ))

if ( inc >= prev_inc ){ // ensure sorted path

As you can see we only add to the queue when we have seen that current increment should be larger than the previous increment. This way the resulting path remains sorted.

How does this work ?

How do you ensure that the same combination i.e (1+5+10 and 10+1+5) is not present in queue ?