Hope you are having a wonderful day! The temperature in the Twin Cities of Minneapolis and St. Paul continues to be way above normal. Today is going to be another spring day with temperatures in the upper 90Fs. My wife and I continue to walk after breakfast. The days are sunny so it is very nice to get our daily walk out of the way early.
Yesterday we had a short thunderstorm with heavy rain. The rain lasted about 30 minutes. It was good for the plants. Tomorrow we also expect some rain.
Something that we have noted in the past couple weeks is that there are more insects. We had to swat a couple flies and a couple bugs in our place. We can also see a few of mosquitoes and wasps. I guess that is to be expected when the weather gets warmer than average. Hope all is going well with farmers. Their crops feed livestock and us. This weekend my wife and I will go to a couple Farmers Markets. On Saturday we will stop by the one in Apple Valley and on Sunday the one in St. Paul. Will let you know our findings next week.
I continue watching the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges and experimenting with the exercises. The exercises are implemented using JavaScript. In this post I will use Java and the VSCode IDE on a Windows 10 computer. At this time I have about 1 hour left in the 5-hour video.
Write a function `canSum(targetSum, numbers)` that takes in a targetSum and an array of numbers as arguments. The function should return a boolean indicating whether or not it is possible to generate the targetSum using numbers from the array. You may use an element of the array as many times as needed. You may assume that all input members are nonnegative. m = targetSum n = numbers.length Time: O(m*n) - Space O(m)
We have seen this problem before. We solved it using dynamic programming and recursion without and with memoization. Today we will solve the problem using tabulation.
For this pass we need to determine if given a target sum and an array of integers we can generate the target sum.
boolean canSum(int targetSum, int[] numbers) {
}
The function of interest illustrated by the specified signature should return true if we can generate the target sum; otherwise it should return false.
0 2,3,5,7,11 main <<< targetSum: 0 main <<< numbers: [2, 3, 5, 7, 11] main <<< canSum: true 7 2,3 main <<< targetSum: 7 main <<< numbers: [2, 3] canSum <<< table: [true, false, true, true, true, true, true, true] main <<< canSum: true 7 5,3,4,7,11 main <<< targetSum: 7 main <<< numbers: [5, 3, 4, 7, 11] canSum <<< table: [true, false, false, true, true, true, true, true] main <<< canSum: true 7 2,4 main <<< targetSum: 7 main <<< numbers: [2, 4] canSum <<< table: [true, false, true, false, true, false, true, false] main <<< canSum: false 8 2,3,5,11 main <<< targetSum: 8 main <<< numbers: [2, 3, 5, 11] canSum <<< table: [true, false, true, true, true, true, true, true, true] main <<< canSum: true 300 7,34 main <<< targetSum: 300 main <<< numbers: [7, 34] canSum <<< table: [true, false, false, false, false, false, false, true, false, false, false, false, false, false, true, false, false, false, false, false, false, true, false, false, false, false, false, false, true, false, false, false, false, false, true, true, false, false, false, false, false, true, true, false, false, false, false, false, true, true, false, false, false, false, false, true, true, false, false, false, false, false, true, true, false, false, false, false, true, true, true, false, false, false, false, true, true, true, false, false, false, false, true, true, true, false, false, false, false, true, true, true, false, false, false, false, true, true, true, false, false, false, true, true, true, true, false, false, false, true, true, true, true, false, false, false, true, true, true, true, false, false, false, true, true, true, true, false, false, false, true, true, true, true, false, false, true, true, true, true, true, false, false, true, true, true, true, true, false, false, true, true, true, true, true, false, false, true, true, true, true, true, false, false, true, true, true, true, true, false, true, true, true, true, true, true, false, true, true, true, true, true, true, false, true, true, true, true, true, true, false, true, true, true, true, true, true, false, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true] main <<< canSum: true
Our test scaffold is presented with two input lines. The first represents the `targetSum` and the second the `numbers` that we will used as arguments to call the function of interest.
Our test scaffold seems to read the two lines, generate the two variables and display them. The function of interest is called and the result is displayed.
On some test cases we also display the table generated by the tabulation process in the function of interest.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read target sum ***
int targetSum = Integer.parseInt(br.readLine().trim());
// **** read numbers ****
int[] numbers = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< targetSum: " + targetSum);
System.out.println("main <<< numbers: " + Arrays.toString(numbers));
// **** compute and display result ****
System.out.println("main <<< canSum: " + canSum(targetSum, numbers));
}
The test scaffold code seems to match closely our description while we took a look at the test cases. I have nothing to add to it at this time.
**** Tabulation Recipe **** 1. Visualize the problem as a table 2. Size the table based on the inputs 3. Initialize the table with some values 4. Seed the trivial answer into the table 5. Iterate through the table 6. Fill further positions based on the current position
The tabulation recipe contains the steps that we need to take to properly implement the technique. We have seen it in a previous post.
Let’s see if we can associate each step to the code that follows for the `canSum` function.
/**
* Write a function `canSum(targetSum, numbers)` that takes in a
* targetSum and an array of numbers as arguments.
*
* The function should return a boolean indicating whether or not it
* is possible to generate the targetSum using numbers from the array.
*
* You may use an element of the array as many times as needed.
*
* You may assume that all input members are nonnegative.
*
* m = targetSum
* n = numbers.length
* Time: O(m*n) - Space O(m)
*/
static boolean canSum(int targetSum, int[] numbers) {
// **** sanity check(s) ****
if (targetSum == 0) return true;
// **** initialization ****
boolean[] table = new boolean[targetSum + 1];
table[0] = true; // base case
// **** loop through the table ****
for (int i = 0; i <= targetSum; i++) {
// **** check if true ****
if (table[i] == true) {
// **** loop through the numbers array ****
for (int j = 0; j < numbers.length; j++) {
// **** for ease of use ****
int num = numbers[j];
// **** if valid index; set to true ****
if (i + num <= targetSum) table[i + num] = true;
}
}
}
// ???? ????
System.out.println("canSum <<< table: " + Arrays.toString(table));
// **** return result ****
return table[targetSum];
}
We start by performing sanity checks. The check if true makes the function return avoiding the initialization of variables. This test is used in the first test case in the list of test cases.
We need to visualize the problem as a table. This is one of the hardest steps.
In this case we come up with a 1D array of Boolean with the proper size. We could have used `targetSum` but the array would work best if we use `targetSum` + 1 as we will see working with the code. In this step we sized the table based on the inputs.
Note that when declaring an array of Boolean, Java by default initializes the entries by setting then to `false`. We need to set the first entry to true because that is our base case. When given a `targetSum` of 0, we can generate it with using any integer array. These couple lines implement the third: initialize the table with some values and fourth steps: seed the trivial answer into the table from our recipe.
We now enter a couple loops that will update the values from our table. Before traversing the list of numbers we make sure that the current table entry is set to `true`. If so we loop once per number in the `numbers` array. Making sure we do not exceed the size of the table, we update the associated entries. This set of steps implement the last entry of our recipe: fill further positions based on the current position.
Before returning we display the table. This is not part of the solution. This is done to make sure we understand what is going on. We are shifting a cursor and updating entries in the table which is part of the tabulation recipe.
When all is set and done, our function of interest returns the last value in the table array.
Setting things up and figuring how the inner loop works seem to be the most complicated steps in the recipe. This is why it is extremely important to practice this technique by solving as many problems as possible.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John