DEV Community

Cover image for Practicing algorithms using Polyglot Notebooks - part 2 - introduction
Krzysztof Koziarski
Krzysztof Koziarski

Posted on

Practicing algorithms using Polyglot Notebooks - part 2 - introduction

#csharp #dotnet #algorithms #dp

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.
Enter fullscreen mode Exit fullscreen mode

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!!! ❌") }"); }
Enter fullscreen mode Exit fullscreen mode

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!!! ❌") }"); }
Enter fullscreen mode Exit fullscreen mode

Output

algorithm cells

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)
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

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!!! ❌") }"); }
Enter fullscreen mode Exit fullscreen mode

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)