Practicing algorithms using Polyglot Notebooks - part 2 - introduction
Tags: csharp, dotnet, algorithms, dp
Published: 2022-12-28 22:00:56

In the previous post: [Practicing algorithms using Polyglot Notebooks - part 1 (setup)](https://dev.to/kkoziarski/practicing-algorithms-using-polyglot-notebooks-part-1-setup-1fp3) 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](https://www.youtube.com/watch?v=oBt53YbR9Kk)

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:
```markdown
## 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. 
   ```csharp
"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.
```csharp
"✅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

![algorithm cells](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v6mzf51hjv97htaiq0nh.png)

*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:
```csharp
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
```markdown
## 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

```csharp
"✅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](https://dev.to/kkoziarski/practicing-algorithms-using-polyglot-notebooks-part-3-helpers-56ag) 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](https://gist.github.com/kkoziarski/f297f9aec84de630639567f5af358a93)