checkerboard.py

import random

recur_calls = 0
dp_calls = 0

def make_board(n, max_val_mag):
  board = []
  for i in range(n):
    board.append([])
    for j in range(n):
      board[i].append(random.randrange(-max_val_mag, max_val_mag + 1))
  return board

def print_board(board):
  for row in reversed(board):
    print(' '.join([str(val).rjust(3) for val in row]))

def print_board_and_soln(board, soln, n, exit_idx):
  def print_row(row, taken):
    vals = [str(val).rjust(3) for val in row]
    # Print "path taken" column in green.
    vals[taken] = '%s%s%s' % ('\033[92m', vals[taken], '\033[0m')
    print(' '.join(vals))

  # Reverse board and solution so we print last row at top instead of bottom.
  board = list(reversed(board))
  soln  = list(reversed(soln))
  taken = exit_idx - 1
  
  for row_idx in range(n):
    print_row(board[row_idx], taken)
    direction = soln[row_idx][taken]
    if direction == 'dl':   # Move down-left.
      taken -= 1
    elif direction == 'dr': # Move down-right.
      taken += 1
    else: # Move straight down, so don't change column.
      pass

def plot_path_r(board, soln, i, j, n):
  global recur_calls
  recur_calls += 1

  cell_val = board[i - 1][j - 1]
  if i == 1: # Bottom row, so can't travel anywhere else.
    return cell_val

  # In leftmost column, so can only down or down-right.
  elif 1 < i <= n and j == 1:
    a = plot_path_r(board, soln, i - 1, j,     n) + cell_val
    b = plot_path_r(board, soln, i - 1, j + 1, n) + cell_val
    if a >= b: # max(a, b) = a, so go down
      soln[i - 1][j - 1] = 'd'
      return a
    else:      # max(a, b) = b, so go down-right
      soln[i - 1][j - 1] = 'dr'
      return b

  # In one of middle columns, so can go down-left, down, or down-right.
  elif 1 < i <= n and 1 < j <  n:
    a = plot_path_r(board, soln, i - 1, j - 1, n) + cell_val
    b = plot_path_r(board, soln, i - 1, j,     n) + cell_val
    c = plot_path_r(board, soln, i - 1, j + 1, n) + cell_val
    if a >= b:
      if a >= c: # max(a, b, c) = a, so go down-left
        soln[i - 1][j - 1] = 'dl'
        return a
      else:      # max(a, b, c) = c, so go down-right
        soln[i - 1][j - 1] = 'dr'
        return c
    else:
      if b >= c: # max(a, b, c) = b, so go down
        soln[i - 1][j - 1] = 'd'
        return b
      else:      # max(a, b, c) = c, so go down-right
        soln[i - 1][j - 1] = 'dr'
        return c

  # In rightmost column, so can only go down-left or down.
  elif 1 < i <= n and j == n:
    a = plot_path_r(board, soln, i - 1, j - 1, n) + cell_val
    b = plot_path_r(board, soln, i - 1, j,     n) + cell_val
    if a >= b:
      soln[i - 1][j - 1] = 'dl' # max(a, b) = a, so go down-left
      return a
    else:
      soln[i - 1][j - 1] = 'd'  # max(a, b) = b, so go down
      return b

def plot_path_recursive(board, n):
  # Make blank initial solution, which will record our eventual path.
  soln = [n*[0] for i in range(n)]

  # Find max val in top row, representing terminal step in optimal path from
  # which we "exit" the board.
  exit_idx = None
  exit_val = float('-inf')
  for j in range(1, n + 1):
    val = plot_path_r(board, soln, n, j, n)
    if val > exit_val:
      exit_idx = j
      exit_val = val

  print_board_and_soln(board, soln, n, exit_idx)
  return exit_val

def plot_path_dp(board, n):
  global dp_calls

  # Make blank initial solution, which will record our eventual path.
  soln = [n*[0]    for i in range(n)]
  opt  = [n*[None] for i in range(n)]

  for i in range(1, n + 1):
    for j in range(1, n + 1):
      dp_calls += 1
      cell_val = board[i - 1][j - 1]
      if i == 1: # Bottom row, so can't travel anywhere else.
        opt[i - 1][j - 1] = cell_val

      # In leftmost column, so can only down or down-right.
      elif 1 < i <= n and j == 1:
        a = opt[i - 2][j - 1] + cell_val
        b = opt[i - 2][j]     + cell_val
        if a >= b: # max(a, b) = a, so go down
          soln[i - 1][j - 1] = 'd'
          opt[i - 1][j - 1] = a
        else:      # max(a, b) = b, so go down-right
          soln[i - 1][j - 1] = 'dr'
          opt[i - 1][j - 1] = b

      # In one of middle columns, so can go down-left, down, or down-right.
      elif 1 < i <= n and 1 < j < n:
        a = opt[i - 2][j - 2] + cell_val
        b = opt[i - 2][j - 1] + cell_val
        c = opt[i - 2][j]     + cell_val
        if a >= b:
          if a >= c: # max(a, b, c) = a, so go down-left
            soln[i - 1][j - 1] = 'dl'
            opt[i - 1][j - 1] = a
          else:      # max(a, b, c) = c, so go down-right
            soln[i - 1][j - 1] = 'dr'
            opt[i - 1][j - 1] = c
        else:
          if b >= c: # max(a, b, c) = b, so go down
            soln[i - 1][j - 1] = 'd'
            opt[i - 1][j - 1] = b
          else:      # max(a, b, c) = c, so go down-right
            soln[i - 1][j - 1] = 'dr'
            opt[i - 1][j - 1] = c

      # In rightmost column, so can only go down-left or down.
      elif 1 < i <= n and j == n:
        a = opt[i - 2][j - 2] + cell_val
        b = opt[i - 2][j - 1] + cell_val
        if a >= b: # max(a, b) = a, so go down-left
          soln[i - 1][j - 1] = 'dl'
          opt[i - 1][j - 1] = a
        else:      # max(a, b) = b, so go down
          soln[i - 1][j - 1] = 'd'
          opt[i - 1][j - 1] = b

  # Find max val in top row, representing terminal step in optimal path from
  # which we "exit" the board.
  exit_idx = None
  exit_val = float('-inf')
  for j in range(1, n + 1):
    val = opt[-1][j - 1]
    if val > exit_val:
      exit_idx = j
      exit_val = val

  print_board_and_soln(board, soln, n, exit_idx)
  return exit_val

def main():
  n = 8

  for i in range(1000):
    board = make_board(n, 5)
    recur_value = plot_path_recursive(board, n)
    print()
    dp_value    = plot_path_dp(board, n)
    print()
    print('Highest possible value via recursion:',           recur_value)
    print('Highest possible value via dynamic programming:', dp_value)
    if dp_value != recur_value:
      raise Exception('Solutions do not match')
    print('\n')
    #print(recur_calls, dp_calls)

def test_case():
  board = [
    [-4,   0,   0,   3,   4,  -3,   4,   5],
    [ 0,  -5,   2,   2,  -1,  -1,   1,   3],
    [-4,  -2,   5,  -1,   3,   0,   3,   0],
    [-2,   3,   3,  -5,   1,   3,   1,  -5],
    [ 0,   1,  -3,  -1,   3,   4,   3,   0],
    [-3,   0,  -3,   1,   1,   5,   3,  -2],
    [-2,  -1,   3,   5,   4,  -3,  -5,  -5],
    [ 0,   1,   0,   2,   4,   4,   1,   1],
   ]
  board = list(reversed(board))
  n = len(board)

  print('Highest possible value via recursion:', plot_path_recursive(board, n))
  print()
  print('Highest possible value via dynamic programming:', plot_path_dp(board, n))

main()