Practicing algorithms using Polyglot Notebooks - part 3 - helpers
Krzysztof Koziarski
Posted on December 28, 2022
In the previous post Practicing algorithms using Polyglot Notebooks - part 2 - introduction 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:
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:
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
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.
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.
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.
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.
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.
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));
}
.Str() method
This is an extension method which converts IEnumerable to JSON string array new int[] { 1, 2, 3 } => [1,2,3] or new List<string> { "aa", "bb", "cc" } => [aa, bb, cc].
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
"✅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.
"✅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[][].
"✅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
or press CTRL+SHIFT+O to find cell by title
All C# algorithms notebook from the dynamic programming course can be found here
Posted on December 28, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related
