Practicing algorithms using Polyglot Notebooks - part 3 - helpers
Tags: csharp, dotnet, algorithms, dp
Published: 2022-12-28 22:01:36

In the previous post [Practicing algorithms using Polyglot Notebooks - part 2 - introduction](https://dev.to/kkoziarski/practicing-algorithms-using-polyglot-notebooks-part-2-introduction-1egd) the execution and assert part was a bit messy with a lot of code repeating for each algorithm. We can reduce this part by using short extension methods instead.

Instead of writing:
```csharp
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);
    Console.WriteLine($"f({targetSum}, {numbersStr}) => {outputStr}, actual: {resultStr}{ (resultStr == outputStr ? " ✔" : " | WRONG!!! ❌") }");
}
```

we will be able to make it more concise:
```csharp
foreach (var (targetSum, numbers, output) in testCases) {
    var result = HowSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result?.Str(), output?.Str());
}
Asrt.Flush();
```


## Helpers

![helpers cell](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ku3ecmwaxp398nzdnaok.png)


We need a set of methods that will help us to prepare, execute, assert and write results.

In the last example above, you can notice three new methods:
- `Log(...)`
- `.Str()`
- `Asrt.Flush()`

Those are helper methods that were added as first *code cell* in the notebook and should be executed at beginning (first action after the notebook is open).

### Reminder - reusing previous cells

You can access methods and variables from previous cells in next cells, but only if you execute the previous cells first.
![polyglot notebooks - previous values](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wzhrj0ra7zn8m0zyknf8.png)

Methods and variables from previous cells will not be available in next cells until you execute those previous cells first. Similarly, if you change values or method implementation in previous cells without executing those cells then only old values will be available in next cells.

![polyglot notebooks - previous values error](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7lzped6n6zixmyfnsk9l.png)

## Helper methods
Every algorithm is (and should be) independent and does not depend on any other cell **except helpers** cell.

### `Asrt` class
This is a simple static helper class to assert condition, collect errors and write summary line at the end of cell.
```csharp
public static class Asrt {
    private static bool hasErrors;
    public static string T(bool condition) {
        if (!condition) {
            hasErrors = true;
        }
        return condition ? "" : " | WRONG!!! ❌";
    }

    public static void Flush() {
        if (hasErrors) {
            hasErrors = false;
            Console.WriteLine("\n❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌ ❌");
            // throw new System.Data.DataException("Invalid result");
        } else {
            Console.WriteLine("\n✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅ ✅");
        }
    }
}
```
The `T(bool condition)` method is used inside `Log(...)` method to print assert results.
The `Flush()` method must be called at the end of each cell to write summary line and reset `hasErrors` flag. It is very important to always call it at the end if you use `Log()` method in a cell, otherwise you will get an incorrect result in a next cell.

![summary - errors](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nmbpzv3ocqpgy02lahx3.png)

![summary - success](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9ylbnngi1exushwopmzv.png)

### `Log(...)` method
This is a helper method that prints the result for each test case. It accepts function description (`funcDefStr`) as first argument, `result` as current return value from algorithm function and `expected` as expected value. The last parameter is optional and allows you to override default comparison logic.

```csharp
public static void Log<T>(string funcDefStr, T result, T expected, bool? condition = null) {
    condition = condition ?? EqualityComparer<T>.Default.Equals(result, expected);
    Console.Write($"{funcDefStr} => ");
    Console.Write($"{(result == null ? "<null>" : result)}");
    if (condition == false) {
        Console.Write($" expected: {expected}");
    } else {
        Console.Write(" ✔");
    }
    Console.WriteLine(Asrt.T(condition == true));
}
```

![log method output](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/isl4xgm208nbm3o2gwfi.png)


### `.Str()` method
This is an extension method which converts IEnumerable<T> to JSON string array `new int[] { 1, 2, 3 }` => `[1,2,3]` or `new List<string> { "aa", "bb", "cc" }` => `[aa, bb, cc]`.

```csharp
public static string Str(this IEnumerable<int> arr, int? size = null) => { ... }

public static string Str(this IEnumerable<object> arr, int? size = null) { ... }
```



## Example algorithms
Here are some algorithms which are returning different result types - primitives (`int`), array (`int[]`) and array of arrays (`string[][]`) to demonstrate different usages of helper methods.

### Fib
```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;
}

(int intput, int output)[] testCases = {
    (6, 8),
    (7, 13),
    (8, 21),
    (45, 1134903170),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Log($"f({input})", result, output);
}
Asrt.Flush();
```

### HowSum
For `IEnumerable<T>` results use `.Str()` method to convert result into JSON string. This is an extension method for `IEnumerable<T>`.
If you want to sort result first, use `.SortNStr()` to sort elements firts and then convert sequence to JSON string.

```csharp
"✅HowSum memoization".Display();

public int[] HowSum(int targetSum, int[] numbers, Dictionary<int, int[]> memo) {
    if (targetSum < 0) return null;
    if (targetSum == 0) return new int[0];
    if (memo.ContainsKey(targetSum)) return memo[targetSum];

    foreach (int n in numbers) {
        int remainder = targetSum - n;

        var result = HowSum(remainder, numbers, memo);
        if (result != null) {
            result = result.Append(n).ToArray();
            memo[targetSum] = result;
            return result;
        }
    }

    memo[targetSum] = null;
    return null;
}

(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),
};

foreach (var (targetSum, numbers, output) in testCases) {
    var result = HowSum(targetSum, numbers, new());
    Log($"f({targetSum}, {numbers.Str()})", result?.SortNStr(), output?.SortNStr());
}
Asrt.Flush();
```

### AllConstruct
For two dimensional results use `.Str2()` instead. This is an extension method for `IEnumerable<IEnumerable<object>>` or `int[][]`.

```csharp
"✅AllConstruct memoization".Display();

public List<List<string>> AllConstruct(string target, string[] wordBank, Dictionary<string, List<List<string>>> memo) {
    if (target == string.Empty) return new() { new List<string>() };
    if (memo.ContainsKey(target)) return memo[target];

    List<List<string>> result = new();

    foreach (string word in wordBank) {
        if (target.StartsWith(word)) {
            string suffix = target.Substring(word.Length);

            var suffixWays = AllConstruct(suffix, wordBank, memo);

            foreach (var way in suffixWays) {
                List<string> targetWay = new();
                targetWay.Add(word);
                targetWay.AddRange(way);
                result.Add(targetWay);
            }
        }
    }

    memo[target] = result;
    return result;
}

(string target, string[] wordBank, string[][] output)[] testCases = {
    ("purple", FromJson<string[]>("[ 'purp', 'p', 'ur', 'le', 'purpl' ]"), FromJson<string[][]>(@"
     [
        [ 'purp', 'le' ],
        [ 'p', 'ur', 'p', 'le' ],
     ]")),
     ("abcdef", FromJson<string[]>("[ 'ab', 'abc', 'cd', 'def', 'abcd', 'ef', 'c' ]"), FromJson<string[][]>(@"
     [
        [ 'ab', 'cd', 'ef' ],
        [ 'ab', 'c', 'def' ],
        [ 'abc', 'def' ],
        [ 'abcd', 'ef' ],
     ]")),
    ("skateboard", FromJson<string[]>(" ['bo', 'rd', 'ate', 't', 'ska', 'sk', 'boar' ]"), FromJson<string[][]>("[]")),
    ("eeeeeeeeeeeeeeeeeeeeeeeeeeeef", FromJson<string[]>(" [ 'e', 'ee', 'eee', 'eeee', 'eeeee', 'eeeeee' ]"), FromJson<string[][]>("[]")),
};

foreach (var (target, wordBank, output) in testCases) {
    var result = AllConstruct(target, wordBank, new());
    Log($"f('{target}', '{wordBank.Str()}')", result?.Str2(), output?.Str2());
}
Asrt.Flush();
```

## Navigation
For easier navigation between cells, you can use **breadcrumbs**

![polyglot notebooks - breadcrumbs](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lx06fwrsdrwe8xsry7xv.png)

or press `CTRL+SHIFT+O` to find cell by title

![polyglot notebooks - jump to by title](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dpllz95g1wkgi14t3b3d.png)

All C# algorithms notebook from the dynamic programming course can be found [here](https://gist.github.com/kkoziarski/90b8af82120c130fe7c3d1a9230e4f6a)