Introduction

A falling path starts with an element in the first row and chooses one that is directly below itself (same column) or diagonally left or right. This proceeds from the top row to the bottom row.

The minimum falling path minimizes the sum of the elements in the path.

The maximum falling path maximizes the sum of the elements in the path.

Project #1

Find the minimum falling path starting at a randomly selected cell in the top row.

• create a 5x5 square grid to start (or larger)
• insert random numbers (integers 1 to 100?) into each cell (row,col)
  (an integer may appear more than once in the grid?)
• select a random starting cell in the top row
• calculate the minimum falling path
• display the path's cells and the path total value
• display the grid? allow up to 10x10 grid?

Note: Using a seed will generate the same random values for testing.

Project #2

Create an interactive program to let a user to

• select the size of the grid
• select minimum or maximum falling path
• display the path's cells and the path total value
• display the grid? allow up to 10x10 grid?

Create a function that can do both minimum and maximum falling path's?

Project #3

Use a non-square (rectangular) grid. How about a grid with holes in it?

Project #4

Generate performance statistics for you algorithm.

• start with a 3x3 square grid
• collect performance statistics
• increase the grid size (Step by 5?)
• increase to a 30x30 grid (or more?)
• plot the performance statistics

Links

Minimum Falling Path Sum (YouTube)
Minimum Falling Path Sum II (YouTube)