Polyglot Notebook (.NET Interactive notebooks) - dynamic programming - introduction

.gitattributes

###############################################################################
# Set default behavior to automatically normalize line endings.
###############################################################################
* text=auto

# Never modify line endings of dib files
*.dib text eol=lf

dotnet.code-workspace

{
	"folders": [
		{
			"path": "."
		}
	],
	"settings": {
		"omnisharp.enableAsyncCompletion": true,
		"omnisharp.useModernNet": true,
		"interactiveWindow.collapseCellInputCode": "always",
		"notebook.showFoldingControls": "always",
		"notebook.cellToolbarVisibility": "hover",
		"notebook.cellFocusIndicator": "border",
		"notebook.diff.ignoreMetadata": false,
		"notebook.diff.ignoreOutputs": true,
		"notebook.dragAndDropEnabled": false,
		"notebook.lineNumbers": "on",
		"notebook.outline.showCodeCells": true,
		"notebook.diff.enablePreview": false,
		"notebook.consolidatedOutputButton": false,
		"notebook.compactView": false,
		"notebook.output.textLineLimit": 50,
		"vsicons.associations.files": [
			{ "icon": "pddl_happenings", "extensions": ["dib"], "format": "svg" }
		],
		"files.exclude": {
			"**/.gitattributes": true,
			"**/.gitignore": true,
			"**/*.code-workspace": true
		}
	},
	"extensions": {
		"recommendations": [
			"vscode-icons-team.vscode-icons",
			"ms-dotnettools.dotnet-interactive-vscode",
		]
	}
}

dynamic-programming-notebook.dib

#!meta

{"kernelInfo":{"defaultKernelName":null,"items":[{"name":"csharp","languageName":"C#","aliases":["c#","cs"]},{"name":"fsharp","languageName":"F#","aliases":["f#","fs"]},{"name":"pwsh","languageName":"PowerShell","aliases":["powershell"]},{"name":"javascript","languageName":"JavaScript","aliases":["js"]},{"name":"html","languageName":"HTML"},{"name":"sql","languageName":"SQL"},{"name":"kql","languageName":"KQL"},{"name":"mermaid","languageName":"Mermaid"},{"name":"httpRequest","languageName":"http"},{"name":"value"}]}}

#!markdown

# Dynamic Programming - Learn to Solve Algorithmic Problems & Coding Challenges

https://www.youtube.com/watch?v=oBt53YbR9Kk

Learn how to use Dynamic Programming in this course for beginners. It can help you solve complex programming problems, such as those often seen in programming interview questions about data structures and algorithms.

This course was developed by Alvin Zablan from Coderbyte. Coderbyte is one of the top websites for technical interview prep and coding challenges.

This course uses images and animations to help you visualize problems and important concepts. After understanding problems conceptually, you will learn how to solve them in JavaScript using Dynamic Programming. Even though JavaScript is used in this course, you will learn concepts and knowledge that you can apply to other programming languages.

## ⭐️ Course Contents ⭐️
- fib memoization
- gridTraveler memoization
- canSum memoization
- howSum memoization
- bestSum memoization
- canConstruct memoization
- countConstruct memoization
- allConstruct memoization
- fib tabulation
- gridTraveler tabulation
- canSum tabulation
- howSum tabulation
- bestSum tabulation
- canConstruct tabulation
- countConstruct tabulation
- allConstruct tabulation

__👇👇👇RUN THIS FIRST👇👇👇__

#!markdown

## Fibonacci memoization - no helpers

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.

#!csharp

"Fibonacci memoization - no helpers".Display();
public int Fib(int n, Dictionary<int, int> memo = null) {
    return -1;
}

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

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Console.WriteLine($"f({input}) => {output}, actual: {result}{ (result == output ? " ✔" : " | WRONG!!! ❌") }");
}

#!csharp

"✅Fibonacci memoization - no helpers".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 = {
    (7, 13),
    (8, 21),
};

foreach (var (input, output) in testCases) {
    var result = Fib(input, memo: new());
    Console.WriteLine($"f({input}) => {output}, actual: {result}{ (result == output ? " ✔" : " | WRONG!!! ❌") }");
}

#!markdown

## HowSum tabulation - no helpers

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.

#!csharp

"HowSum tabulation - no helpers".Display();

public int[] HowSum(int targetSum, int[] numbers) {
    return new int[0];
}

(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);
    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!!! ❌") }");
}

#!csharp

"✅HowSum tabulation - no helpers".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];
}

(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);
    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!!! ❌") }");
}