Algorithm - Costliest Possible Route in Grid Puzzle

Question

Objective

Find the most expensive path from the top-left of a square grid to the bottom-right such that its total cost is below a given threshold.

Scenario

1. You are given a square NxN grid.
2. You are given a maximum cost.
3. Every cell in the grid has a cost. The top-left cell has cost 0.
4. The cost of a path is the sum of the costs of the cells in the path. Its "cost surplus" is the result of subtracting its cost from the maximum cost.
5. Movement is always either right one cell or down one cell.
6. The starting point is the top-left cell of the grid and the goal is the bottom-right cell.
7. You must output the smallest cost surplus of any path with a non-negative cost surplus, or -1 if there is no such path (The maximum cost is not enough).

Input restrictions

1. N will be between 1 and 20 inclusive.
2. The maximum cost will be between 1 and 200 inclusive.
3. The cost of each cell will be between 0 and 10 inclusive.

Examples

1. Maximum cost: 9
   Grid:

   0 1 5
   2 3 2
   2 3 2
   

   Expected output: 0
   Explanation: there is a path 0 2 2 3 2 with cost 9 and cost surplus 0.

2. Maximum cost: 15
   Grid:

   0 1 5
   2 3 2
   2 3 2
   

   Expected output: 5
   Explanation: the most expensive path is 0 1 5 2 2 with cost 10 and cost surplus 5.

3. Maximum cost: 6
   Grid:

   0 1 5
   2 3 2
   2 3 2
   

   Expected output: -1
   Explanation: the least expensive path is 0 1 3 2 2 with cost 8, which is greater than 6.

Answer 1

GolfScript (53 bytes)

~.,[1]*\{[[\]0\zip{~2$|2@?*}/](;}/-1=2.$)?|2base\~>1?

Expects input in the format

15 [[0 1 5][2 3 2][2 3 2]]

Online demo which covers three test cases.

The approach is to build up a list of possible running totals to each cell as a bitmask, extract the relevant lower bits, base-convert to a list of 0 and 1, and look for the index of the first 1.

Dissection

~              # Eval input: puts N and grid on the stack
.,[1]*         # Set up initial row cost bitmask: 2^0 for each column
\{             # For each row in grid:
  [            #   Stack: N prev-row-bitmask this-row-cost
    [\]0\zip   #   Pair up prev-row-bitmask and this-row-cost and push 0 under them
    {          #   For each pair:
      ~        #     Stack: N left-cell-bitmask cost up-cell-bitmask
      2$|2@?*  #     this-cell-bitmask = (left-cell-bitmask | up-cell-bitmask) << cost
    }/
  ](;          #   Gather row into an array and drop the 0 we inserted for the -1th cell
}/
-1=            # Take the bitmask of the bottom-right cell. Stack: N bottom-right-bitmask
2.$)?|         # Or 2^N to ensure that we get enough bits from the base conversion
2base          # Base conversion
\~>            # Take the last (least significant) N+1 bits
1?             # Find the first index (hence smallest cost surplus) of the value 1

Answer 2

CJam, 72 71 bytes

q~:Q,mqi:L(2*0aa\{{_[~__)L%1L?+]\[~__L/)L=1L?+]}%}*{Qf=:+}%f-{W>},$W+0=

This is really long and I think a different approach to the question is the only way to get it shorter.

Try it online here

Input is in the following format : <Steps> [<Flat Grid>] . For ex:

9 [0 1 5 2 3 2 2 3 2]

And output is the cost remaining, so 1 in above example.

*Note that [0 1 5 2 3 2 2 3 2] is just a flat representation of the grid

0 1 5
2 3 2
2 3 2

How it works (slightly outdated):

q~                                     "Read the input and evaluate it";
  :Q                                   "Store the array in Q";
    ,mqi:L                             "Do floor of square root of its length";
          LL+((                        "Double length and decrease 2 from the double";
               0aa                     "Put [[0]] on stack. This is the starting index"
                                       "for any path in the grid";
                  \{ ... }*            "Swap to but L + L - 1 on top and run the code"
                                       "block that many times";
 {{_[~__)L%1L?+]\[~__L/)L=1L?+]}%}*    "This block calculates indexes of all possible";
                                       "paths from top left to bottom right of the grid";
 {                            }%       "Map each array based on this code block";
  _[~                                  "Copy the array and start a new array with the"
                                       "contents of the copied one";
     __                                "Make two copies of the last element of the array";
       )L%                             "Increment the element and calculate module L";
          1L?                          "Choose L if module is 0, 1 otherwise";
             +]                        "Add it to the copy of last array element. With"
                                       "this, we have created one of the two possible"
                                       "next step, that is going right. Except if we are"
                                       "on the last column, then go down";
               \[~                     "Swap and start a new array with contents of"
                                       "the original array";
                  __                   "Make two copies of the last element";
                    L/)                "Divide the 2nd copy by L and add 1 to the result";
                       L=1L?           "If index belongs to last row, choose 1, else L";
                            +]         "Add to the first copy of last element and close"
                                       "the array. Now we have the second possible next"
                                       "step, i.e. going down. But if we are on last row"
                                       "then go right";
{Qf=:+}%                               "Map this block on the array containing all"
                                       "possible path indexes";
 Qf=                                   "Get the corresponding cell amount array";
    :+                                 "Sum the array elements to get total path cost";
        {1$)<},                        "Filter out paths which are not possible. i.e."
                                       "paths having total cost more than first input";
               $W=                     "Sort and get the last (highest) path cost";
                  -                    "decrement from input to get remaining steps";

Answer 3

VBScript 191

This assumes that the array is in a variable called A and the cost is in a variable called c.

Dim M
Sub f(s,i,j,v)
If i>s And j=s And v<=c And M<v Then M=v
If i>s Or j>s Then Exit Sub
f s,i+1,j,v+A(i)(j)
f s,i,j+1,v+A(i)(j)
End Sub
f UBound(A),0,0,0
If M=0Then MsgBox-1 Else MsgBox c-M

To run it put the following lines at the top of a file called x.vbs then paste in the code above and just double click or execute cscript x.vbs

A=Array(Array(0,1,5),Array(2,3,2),Array(2,3,2))
c=6

Answer 4

CJam, 71 69 68 bytes

I didn't look at anything from Optimizer's answer, except its size and input format... so the size is complete coincidence. But I think this can be golfed a fair bit.

l~:L,mqi(:X2*2\#:Y[{IY+2b(;_:+X={0_@{X*)+_L=@+\}/}*;}fI]f-{W>},$W+0=

Test it here.

The input on STDIN is in the form of the maximum steps and the unrolled grid as a CJam array:

9 [0 1 5 2 3 2 2 3 2]

Explanation:

"Prepare input:";
l~:L,mqi(:X2*2\#:Y
l~                    "Read and eval input.";
  :L                  "Store grid in L.";
    ,mqi(:X           "Get length, square root, cast to int, decrement, store in X.";
           2*2\#:Y    "Multiply by 2, raise 2 to this power, store in Y.";

[{...}fI]             "For I in 0 to Y-1. Collect in array.";

"Determine path:";
IY+2b(;_:+X=
IY+                   "I + Y.";
   2b                 "Convert to base 2.";
     (;               "Drop leading 1.";
       _:+            "Duplicate and sum.";
          X=          "Check for equality with X.";

{...}*                "If equals, execute this (otherwise, don't).":

"Determine remaining weight:";    
0_@{X*)+_L=@+\}/
0                     "Push 0. This is the sum.";
 _                    "Push another 0. This is the current position in the grid.";
  @                   "Pull up path description. 1 -> down, 0 -> right.";
   {          }/      "For each step...";
    X*)               "Multiply by X, increment.";
       +              "Add to current position.";
        _L=           "Duplicate and extract grid element.";
           @+         "Pull up sum and add.";
             \        "Swap with position.";

;                     "Pop... either the invalid path or the last position.";

f-                    "Subtract each sum from the maximum step number.";
  {W>},               "Filter out negative results.";
       $              "Sort.";
        W+            "Append a -1.";
          0=          "Take the first element.";