Cherry pickup algorithm

An in-depth look at the Cherry Pickup problem on Leetcode.com.

Tue Apr 03 2018

One of the harder questions on Leetcode.com is the Cherry Pickup. I hope this post shines a light on this problem for many people struggling with the solution.

Problem description by Leetcode.com

The problem as described by Leetcode is as follows:

In a N x N grid representing a field of cherries, each cell is one of three possible integers.

0 means the cell is empty, so you can pass through;

1 means the cell contains a cherry, that you can pick up and pass through;

-1 means the cell contains a thorn that blocks your way.

Your task is to collect maximum number of cherries possible by following the rules below:

Starting at the position (0, 0) and reaching (N-1, N-1) by moving right or down through valid path cells (cells with value 0 or 1);

After reaching (N-1, N-1), returning to (0, 0) by moving left or up through valid path cells;

When passing through a path cell containing a cherry, you pick it up and the cell becomes an empty cell (0);

If there is no valid path between (0, 0) and (N-1, N-1), then no cherries can be collected.

Symbols we will use to describe the problem

This post aims to simplify the problem and we will be using different symbols. These are outlined below.

[[],[]] / Matrix of matrixes - Field of cherries
1 - 🍓 - Cherry
0 - No cherry (possibly already collected)
-1 - ᚦ (thorn that blocks the cherry collector)
🚶 - Cherry collector
- Can one make one round-trip collection
- Can only move down or right on his way to x=N-1, y=N-1
- Can only move up or left on his way to x=0, y=0

Quiz

A few quiz questions below will help to understand the problem by example.

Question 1 What is the maximum number of cherries, the collector can collect in the following field?

[[🍓, ᚦ, 0, 0, 0, 0],
 [🍓, ᚦ, 0, 0, 0, 0],
 [🍓, ᚦ, 0, 0, 0, 0],
 [🍓, ᚦ, 0, 0, 0, 0],
 [🍓, ᚦ, 0, 0, 0, 0],
 [🍓, ᚦ, 0, 0, 0, 0]]

Answer = none because he can never reach his target.

Question 2 What about for this field?

[[0,  0,  0,  0,  0,  🍓],
 [🍓,  ᚦ,  0,  0,  0,  0],
 [🍓,  🍓, 🍓,  0,  0,  0],
 [🍓,  ᚦ,  0,  0,  0,  0],
 [🍓,  ᚦ,  0,  0,  🍓,  0],
 [🍓,  0,  0,  0,  0,  0]]

Lets find out!

//On the way down - 5 cherries
[[🚶,  0,  0,  0,  0,  🍓],
 [🚶,  ᚦ,  0,  0,  0,  0],
 [🚶,  🍓, 🍓,  0,  0,  0],
 [🚶,  ᚦ,  0,  0,  0,  0],
 [🚶,  ᚦ,  0,  0,  🍓,  0],
 [🚶,  🚶,  🚶,  🚶,  🚶,  🚶]]

//Return journey - 3 cherries
[[🚶,  0,  0,  0,  0,  🍓],
 [🚶,  ᚦ,  0,  0,  0,  0],
 [🚶,  🚶,  🚶,  🚶,  0,  0],
 [0,  ᚦ,  0,  🚶,  0,  0],
 [0,  ᚦ,  0,  0,  🚶,  0],
 [0,  0,  0,  0,  0,  🚶]]

Answer = 8

Notice one cherry is still left in the field, in the top right corner. Picking up that cherry would have meant leaving more cherries unpicked in the field. The reason we cannot possibly pick up all of the cherries in the field is because we can only move in down/right on the way down, then up/left on the return journey. We can only make one roundtrip cherry collection.

Let us think about this further and come up with some other truths that may later help us, before writing any code

Cherries can only be picked up once. They are gone once picked up
You cannot hit a thorn and continue. You must avoid thorns
You may cross over a path you have already traveled. Sometimes this is wise to avoid thorns and get to other cherries
Every path that can be traveled by going up/left from the destination (N-1, N-1) can also be identically traveled by going down and right from the origin (0,0).
- Optimization alert. Therefore two people traveling down/right ‘one way’ can make the same cherry pickups as one person doing a ‘round-trip.’

Source code

Source code in JavaScript for working out the max number of cherries you can pick up with two people, starting at the origin 0,0 and ending at the destination N-1, N-1 both with the restriction of only being able to move down or right.

The recursion ensures that we explore all viable paths
The Math.max ensures that we choose the two most lucrative paths

var cherryPickup = function (grid) {
    var maxY = grid.length;
    var maxX = grid[0].length;
    var memo = {};
    function dp(yPersonA, xPersonA, xPersonB) {
        //work out corrosponding Y variable for personB. (works since personA and personB have made the same number of moves)
        var yPersonB = yPersonA + xPersonA - xPersonB;

        //key for the current state
        var memoKey = yPersonA + "_" + xPersonA + "_" + xPersonB;

        //work out if we are out of bounds
        var overTheEdge = maxY == yPersonA || maxY == yPersonB || maxX == xPersonA || maxX == xPersonB; //we are actually over the edge HERE!!
        if (overTheEdge) {
            return -999999;
        }

        var personAHitAThorn = grid[yPersonA][xPersonA] == -1;
        var personBHitAThorn = grid[yPersonB][xPersonB] == -1;
        if (personAHitAThorn || personBHitAThorn) {
            //impossible move, either over the edge or directly on a thorn
            return -999999;
        } else if (yPersonA == maxY - 1 && xPersonA == maxX - 1) {
            //reached the target finally
            return grid[yPersonA][xPersonA];
        } else if (memo[memoKey] !== undefined) {
            //already visited
            return memo[memoKey];
        } else {

            var personAHasCherry = grid[yPersonA][xPersonA] === 1;
            var personBHasCherry =
                yPersonB !== yPersonA && xPersonB !== xPersonA && //if personA didn't take it first!
                grid[yPersonB][xPersonB] === 1;

            var cherriesCollectedByBothPeopleThisTurn =
                (personAHasCherry ? 1 : 0) +
                (personBHasCherry ? 1 : 0);

            //both people make all possible single moves they can make (down and right)
            //personB by definition will likely always be on a different path than personA since:
            //   *   it will generate more COMBINED cherries (see above cherriesCollectedByBothPeopleThisTurn)
            var maxCherriesCollectedByBothPeopleForRemainingTurns = Math.max(
                Math.max(
                    dp(yPersonA, xPersonA + 1, xPersonB + 1), //personA right personB right
                    dp(yPersonA + 1, xPersonA, xPersonB + 1)), //personA down personB right
                Math.max(
                    dp(yPersonA, xPersonA + 1, xPersonB), //personA right personB down
                    dp(yPersonA + 1, xPersonA, xPersonB)) //personA down personB down
                );

            var cherriesCollectedRecursive = cherriesCollectedByBothPeopleThisTurn + maxCherriesCollectedByBothPeopleForRemainingTurns;
            memo[memoKey] = cherriesCollectedRecursive;
            return cherriesCollectedRecursive;
        }
    }

    return Math.max(0, dp(0, 0, 0));
}

Cherry pickup algorithm

An in-depth look at the Cherry Pickup problem on Leetcode.com.

Problem description by Leetcode.com

Symbols we will use to describe the problem

Quiz

Source code

Find the number of non-contiguous islands in a 2d matrix world

Using recursion and depth-first search to find all islands in a given 2d matrix world

Find the median in a data stream

Adding incoming data in a way that it's optimized to always knowing the median

First missing positive

Find the first missing positive integer in an array in O(array_length) time from LeetCode

Median of two arrays

Getting the median of two sorted arrays in O(log(small_array_length)).

Merge k sorted linked lists

Disseminating the "merge k sorted linked lists" problem from Leetcode.com.

Setup Isso comments on your website today

This guide goes through everything you need to get the open source commenting software Isso running on your website for completely free with Google Cloud.

ZigZag conversion algorithm

A dive into the ZigZag letter conversion on Leetcode.com. Letters initially are written in a zig-zag formation and must be read back from left to right.

Cherry pickup algorithm

An in-depth look at the Cherry Pickup problem on Leetcode.com.

Autocomplete with static files [4/4] - Implementing autocomplete with generated static files

At this stage, we should have already have generated our 'data source' of autocomplete JSON files. We can now finally implement a working text box with autocomplete functionality, which consumes these files.

Autocomplete with static files [3/4] - Building an autocomplete static file generator

In this post we will be implementing an autocomplete static file generator, using the principles, learned in the past two articles in this series. Also within this post is a working demo which produces static autocomplete JSON files for a CSV.

Autocomplete with static files [2/4] - Visualization of words in a Trie

An interactive visualization of how to implement autocomplete without a backend server, using only static files. This post will help with understanding the underpinnings of autocomplete using a Trie data structure.

Autocomplete with static files [1/4] - Introduction

An introduction to static files and the benefits of generating static files for your autocomplete implementation.

Representing numbers, using sticks and stones.

NHibernate QueryOver examples using the C# library

QueryOver is a powerful wrapper for the NHibernate ORM Criteria API. It is type-safe with a familiar syntax to Lambda expressions and LINQ. This post covers a nice range of real-world usage examples.

Creating an Android app, with a large offline database (over 4GB)

Today we will be covering large SQLite databases with the Android PhoneGap framework. We will be going over the challenges and opportunities of running offline Android apps with scale.

Linking in-text citations to numbered references on a page

In this post, we will be adding a usability feature by adding hover functionality to citations. When hovering over a citation, we will show the corresponding reference text. In this example, we are dealing with unstructured HTML and using a set of business rules to link the citations to references.