In the previous post: Practicing algorithms using Polyglot Notebooks - part 1 (setup) I've described how to install and configure Polyglot Notebooks (formerly .NET Interactive notebooks).
In this post I will show you how to start practicing algorithms in C# using Polyglot Notebooks.
I will implement some test cases from the best dynamic programming course in the world:
Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges
The course from freeCodeCamp.org uses JavaScript but I will show you how to do that in C# and Polyglot Notebooks (you can also use JavaScript in Polyglot Notebooks)
First algorithm
Structure
One algorithm will consist of three parts:
- Description - a markdown cell with problem description
-
Practice - a code cell - placeholder - contains empty method and test cases
- this is the main cell you should work in and once completed, remove its content for next time
-
Solution - a code cell with solution - marked with ✅
- it should be collapsed by default and used only when you stuck and need a reminder
Create algorithm
1. Problem description - Fib
Create a markdown cell and type the description:
## Fibonacci memorization
Write a function `fib(n)` that takes in a number as an argument.
The function should return the `n-th` number of the Fibonacci sequence.
The 0th number of the sequence is 0.
The 1th number of the sequence is 1.
2. Practice - Fib
Below the problem description create a code cell - with method placeholder and test cases, as well execution and assert part.
"Fibonacci memoization".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
return -1;
}
// test cases
(int intput, int output)[] testCases = {
(7, 13),
(8, 21),
};
// execution
foreach (var (input, output) in testCases) {
var result = Fib(input, memo: new());
// assert
Console.WriteLine($"f({input}) => {output}, actual: {result}{ (result == output ? " ✔" : " | WRONG!!! ❌") }");
}
3. Solution - Fib
Create a new code cell with full implementation. This is a copy of the previous cell but the Fib
method has actual implementation.
Solution cell is marked with ✅ so it's easier to recognize.
"✅Fibonacci memoization".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
if (n <= 2) return 1;
if (memo.ContainsKey(n)) return memo[n];
int result = Fib(n-1, memo) + Fib(n-2, memo);
memo[n] = result;
return result;
}
// test cases
(int intput, int output)[] testCases = {
(7, 13),
(8, 21),
};
// execution
foreach (var (input, output) in testCases) {
var result = Fib(input, memo: new());
// assert
Console.WriteLine($"f({input}) => {output}, actual: {result}{ (result == output ? " ✔" : " | WRONG!!! ❌") }");
}
Output
Solution cells should be committed to git. Methods in practice cells should be committed empty so you can go back to it at any time - with fresh start and without a need to remove its implementation before starting practice.
More complex results
What if we have a method that returns a non-primitive type? Let's look at method:
int[] HowSum(int targetSum, int[] numbers)
As you can see, this method returns an array. We need to check if its result is the same as expected.
Problem description - HowSum
## HowSum tabulation
Write a function `howSum(targetSum, numbers)` that takes in a `targetSum` and an array of numbers as arguments.
The Function should return an array containing any combination of elements that add up to exactly the `targetSum`. If there is no combination that adds up to the `targetSum`, then return null.
Solution - HowSum
Let's create a solution cell for this
"✅HowSum tabulation".Display();
public int[] HowSum(int targetSum, int[] numbers) {
int[][] dp = new int[targetSum + 1][];
dp[0] = new int[0]; //[]
for (int i = 0; i <= targetSum; i++) {
if (dp[i] != null) {
foreach (int n in numbers) {
if (i + n <= targetSum) {
var list = new List<int>(dp[i].Length + 1);
list.AddRange(dp[i]);
list.Add(n);
dp[i + n] = list.ToArray(); // [ ...d[i], n]
}
}
}
}
return dp[targetSum];
}
// test cases
(int targetSum, int[] numbers, int[] output)[] testCases = {
(7, new int[] { 2,3 }, new int[] { 3,2,2 }),
(7, new int[] { 5,3,4,7 }, new int[] { 4,3 }),
(7, new int[] { 2,4 }, null),
(8, new int[] { 2,3,5 }, new int[] {2,2,2,2 }),
(300, new int[] { 7,14 }, null),
};
// execution
foreach (var (targetSum, numbers, output) in testCases) {
var result = HowSum(targetSum, numbers);
var numbersStr = Newtonsoft.Json.JsonConvert.SerializeObject(numbers);
var resultStr = Newtonsoft.Json.JsonConvert.SerializeObject(result);
var outputStr = Newtonsoft.Json.JsonConvert.SerializeObject(output);
// assert
Console.WriteLine($"f({targetSum}, {numbersStr}) => {outputStr}, actual: {resultStr}{ (resultStr == outputStr ? " ✔" : " | WRONG!!! ❌") }");
}
The idea is very simple - convert all complex types into strings and compare strings. For our purposes this is good enough.
In the next post Practicing algorithms using Polyglot Notebooks - part 3 - helpers I will show you how to simplify the last part (execution and assert inside foreach
) to avoid code duplication in each cell and make the code more concise.
Gist for this article can be found here
Top comments (0)