Today is a cold and dark day in the Twin Cities of Minneapolis and St. Paul. It has been raining all day. The forecast matched the day. Hopefully tomorrow it will be nicer.
Yesterday evening my wife and I were sitting in the living room watching YouTube videos. All was working as expected. At some point I decided to look for a video to watch so I picked up my phone that was sitting next to me on the couch. The phone was dead. I tried powering it up at no avail. I thought the battery might have discharged. Strange because when I picked it up from the wireless charger the phone was about 100% charged.
I tried pressing button sequences to restart the phone. That did not work.
I pulled my cell phone out of the OtterBox case. The phone looks like new. I decided not to open the actual phone thinking I might cause an additional problem. I put my phone back into the OtterBox case.
I then decided to put the phone to charge on a wireless charger. After half hour or so later I tried to power up the phone. It was not able to power up. I then tried with a regular plug-in charger. Half hour later the phone was still completely dead. Decided to take my Pixel 4 phone to T-Mobile and see if they can diagnose and hopefully fix the issue. We will find more about it today after work…
…Later in the day I took my cell phone to the T-Mobile store closest to home. They were able to rest the phone. All is back to normal. I did ask if T-Mobile would carry the Pixel 5 phone. Apparently they have no plans to do so. My wife and I might switch to Apple for the first time when our Pixel phones need to be replaced.
Today I continued watching the YouTube video Dynamic Programming – Learn to Solve Algorithmic Problems & Coding Challenges. As I am watching the video I try to solve the problems before the author provides a complete solution. That way I can learn more from it.
Before we get into the actual problem I want to share with you the following recipe:
Memoization Recipe 1. Have a solution, with recursion, that works (lacks performance). o visualize the problem as a tree. o implement the tree using recursion o leaves of tree as base cases o test it (maybe slow but correct) 2. Make it efficient. o add a memo object (key -> value e.g., array, hash map) o add a base case to return memo values o store return values into the memo
The first step describes how we should approach solving a dynamic programming. By visualizing simple versions of the problem we should be able to implement a recursion tree. Once we have a base or brute force solution we should make sure it works. At that point we can move on and optimize it using memoization.
The second step describes the steps that we should take to implement memoization.
One should keep in mind that every problem might be somewhat different, but in general the steps should help.
Write a function `boolean canSum(int targetSum, int[] numbers)` that takes in a targetSum and an array of numbers as arguments. The function should return a boolean indicating weather 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 numbers are non-negative.
The description of the problem is well done. We are given a target sum integer and an array of non-negative integers. Witch such arguments we need to determine if it is possible to sum numbers from the array and be able to replicate the target value. If we can we return true; otherwise we return false.
The video author uses JavaScript to solve the problem. We will use Java and the VSCode IDE on a Windows 10. Of course you can use the programming language and IDE of your choice to solve it.
One way or the other we need to generate a test scaffold that will collect the data for the input parameters, generate the arguments, pass the arguments to the method of interest and display the result \ answer.
7 2,3,6,7 main <<< targetSum: 7 main <<< numbers: [2, 3, 6, 7] canSum <<< callCounter: 5 main <<< ans: true 8 2,3,5 main <<< targetSum: 8 main <<< numbers: [2, 3, 5] canSum <<< callCounter: 5 main <<< ans: true 1 2 main <<< targetSum: 1 main <<< numbers: [2] canSum <<< callCounter: 1 main <<< ans: false 1 1 main <<< targetSum: 1 main <<< numbers: [1] canSum <<< callCounter: 2 main <<< ans: true 2 1 main <<< targetSum: 2 main <<< numbers: [1] canSum <<< callCounter: 3 main <<< ans: true 7 2,3 main <<< targetSum: 7 main <<< numbers: [2, 3] canSum <<< callCounter: 5 main <<< ans: true 7 5,3,4,7 main <<< targetSum: 7 main <<< numbers: [5, 3, 4, 7] canSum <<< callCounter: 5 main <<< ans: true 7 2,4 main <<< targetSum: 7 main <<< numbers: [2, 4] canSum <<< callCounter: 4 main <<< ans: false 8 2,3,5 main <<< targetSum: 8 main <<< numbers: [2, 3, 5] canSum <<< callCounter: 5 main <<< ans: true 300 7,14 main <<< targetSum: 300 main <<< numbers: [7, 14] canSum <<< callCounter: 1,134,903,169 <=== NO memoization main <<< ans: false 300 7,14 main <<< targetSum: 300 <=== WITH memoization main <<< numbers: [7, 14] canSum <<< callCounter: 43 main <<< ans: false
The first input line represents the target sum. The second line holds the values for the integer numbers.
Our test code seems to be able to read the two lines and display the variables that it created and populated.
Our code seems to display the call counter which we have seen in the last few posts. The reason is to emphasize the difference in the number of times a recursive call is made without and with memoization.
Finally the result of the function \ method of interest is displayed.
Please note that the callCounter displayed in the test cases is when memoization has already been implemented. As you should expect due to the target value and the number of values in the array the value of the call counters should not be large.
If you scroll at the last two test cases, we have the call counter without memoization followed by the same example with memoization. Big difference!!!
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read and assign the target value ****
int targetSum = Integer.parseInt(br.readLine().trim());
// **** read and create int[] array of 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));
// **** call the function and display the result ****
System.out.println("main <<< ans: " + canSum(targetSum, numbers));
}
The test scaffold is quite simple and matches our observations previously talked about. I do not believe there is much to be added. In this post I progressed through the problem and just left the completed code. That said it is very simple, as we will seen in a few, to run the code with or without memoization.
/**
* Write a function `boolean canSum(int targetSum, int[] numbers)` that takes in a
* targetSum and an array of numbers as arguments.
*
* The function should return a boolean indicating weather 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 numbers are non-negative.
*
* Entry point call.
*
* m = target sum
* n = array length
*
* Without memoization: Time: O(n ^ m) and Space: O(m)
* With memoization: Time: O(m * n) and Space: O(m)
*/
static boolean canSum(int targetSum, int[] numbers) {
// **** initialization ****
boolean ans = false;
int[] callCounter = new int[1];
TreeMap<Integer, Boolean> memo = new TreeMap<>();
// **** start recursion ****
ans = canSum(targetSum, numbers, memo, callCounter);
// ???? ????
System.out.println("canSum <<< callCounter: " + callCounter[0]);
// **** return result ****
return ans;
}
This is the entry call for the recursive method. We will use a TreeMap for memoization. Since the values in the execution tree do not repeat generating a different outcome, we can just keep the result and use it as often as needed when we encounter the same value.
We then enter the recursive call. Note that we do not need the call counter variable. That is only used to collect and display the number of times our recursive call is invoked.
After the recursion is completed we display the call counter and the result.
/**
* Write a function `boolean canSum(int targetSum, int[] numbers)` that takes in a
* targetSum and an array of numbers as arguments.
*
* The function should return a boolean indicating weather 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 numbers are non-negative.
*
* Recursive call.
*/
static boolean canSum( int targetSum,
int[] numbers,
TreeMap<Integer, Boolean> memo,
int[] callCounter) {
// ???? increment call counter ????
callCounter[0]++;
// **** base cases(s) ****
if (targetSum == 0) return true;
if (targetSum <= 0) return false;
// **** initialization ****
boolean found = false;
// **** loop making recursive call (or getting value from memo) ****
for (int i = 0; i < numbers.length && !found; i++) {
// **** for ease of use ****
int rem = targetSum - numbers[i];
// **** make recursive call (or get it from memo) ****
if (rem >= 0) {
// **** if not in memo; recurse and update memo ****
if (!memo.containsKey(rem)) // comment this line to disable memoization !!!
memo.put(rem, canSum(rem, numbers, memo, callCounter));
// **** get value from memo ****
found = memo.get(rem);
}
}
// **** return answer ****
return found;
}
When we enter the recursive call we increment the call counter.
We then check the base cases that we should be able to infer from the execution tree. If you have questions, I encourage you to watch the video in question on YouTube.
We now check all the values from the numbers array. We compute the remainder value for each and then check if we do not have it in the memoization data structure. If not we generated and update the data structure. Once we get to the final instruction in the loop we can use the memorized value.
Note that if we encounter a true during the execution, we can drop out of the loop.
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