NEW BLOG. 3D Printing.

Now it is time for 3D Printing! Review of the info in the blog is
advised.

1 files changed, 332 insertions, 0 deletions

diff --git a/_posts/2023-04-18-3d-printing.md b/_posts/2023-04-18-3d-printing.md
new file mode 100644
index 0000000..ed44141
--- /dev/null
+++ b/_posts/2023-04-18-3d-printing.md
@@ -0,0 +1,332 @@
+---
+title: 3D Printing
+categories: [Technical Logs, Individual]
+tags: [dart]
+math: true
+
+image:
+    path: https://codejam.googleapis.com/dashboard/get_file/AQj_6U1yXmbP6Nf5PONAMbqVd5eyM5BBSbjggzDn9H6vS3ATQiqbGVrfZ0ABoAbBkn8IWocYoj1rdJim6VkTTOP4/3d_printing.png
+    alt: "3 printers with their own ink levels."
+---
+
+> This page is still in WIP. A lot of information is missing or not reviewed.
+{: .prompt-danger }
+
+---
+
+Try this problem by yourself first! Check the [Code Jam Page](https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a4672b).
+
+## Overview
+
+We have three printers, each with its own ink levels. We have $C_i$ for the ink
+level of Cyan on the $i$th printer, $M_i$ for the Magenta level, $Y_i$ for the
+color Yellow and $K_i$ for Black. The ink is measured on units. On each printer
+we want to print a big D that requires 1,000,000 units of ink. Each D must have
+the same color. We need to find that color.
+
+What we want is to find $c, m, y, k$ integers such that
+
+$$
+\begin{eqnarray}
+&   c \leq C_i \qquad m \leq M_i \qquad y \leq Y_i \qquad k \leq K_i \,, \qquad
+\forall i, \; 1 \leq i \leq 3 .
+\end{eqnarray}
+$$
+
+To solve this problem, it is sufficient that the integers satisfy the following
+inequalities:
+
+$$
+\begin{eqnarray}
+&   c \leq \min(C_1, C_2, C_3) \qquad
+    m \leq \min(M_1, M_2, M_3) \\
+&   y \leq \min(Y_1, Y_2, Y_3) \qquad
+    k \leq \min(K_1, K_2, K_3) .
+\end{eqnarray}
+$$
+
+We can then set each integer to the minimum of the ink of its corresponding
+color. Finally, depending on the sum of the integers, we can determine if the
+problem is impossible or if we can find a solution.
+
+<br>
+<div style="text-align: center;">O &nbsp; &nbsp; O &nbsp; &nbsp; O</div>
+<div style="text-align: center;">o o o</div>
+<div style="text-align: center;">...</div>
+<br>
+
+## Context
+
+We're give three printers. Each one has its own ink levels for Cyan ($C_i$),
+Magenta ($M_i$), Yellow ($Y_i$) and Black ($K_i$). We need to print three big
+D's for the *Database Design Day* logo. Each D must be printed on one printer
+and all of the D's must have the same color. That is, we must select a color
+with four levels of ink $c$, $m$, $y$ and $k$ such that $c \leq C_i$, $m \leq M_i$, $y \leq Y_i$ and $k \leq K_i$, for $1 \leq i \leq 3$.
+
+The total amount of ink needed to print a single D is $10^6$ units. There may
+exist more than one possible solution or even none. If at least one solution
+exists, we can output any solution. If there's none, we print `IMPOSSIBLE`.
+
+### A minimum property
+
+We have the following property:
+
+$$
+\begin{eqnarray}
+  &  \text{If} \quad a \leq b \quad \text{and} \quad a \leq c \quad
+     \text{then} \quad a \leq \min(b, c) .
+\end{eqnarray}
+$$
+
+To see why this is true, we can divide it in two cases:
+
+1. **Case $b \leq c$.** Then $\min(b, c) = b$. And because $a \leq b$, then $a
+   \leq \min(b, c)$.
+1. **Case $b > c$.** Then $\min(b, c) = c$. And because $a \leq c$, then $a
+   \leq \min(b, c)$.
+
+> It is analogous to see that if $a \leq b, \; a \leq c$ and $a \leq d$, then $a
+\leq \min(b, c, d)$. Try it yourself!
+{: .prompt-tip}
+
+<br>
+<div style="text-align: center;">O &nbsp; &nbsp; O &nbsp; &nbsp; O</div>
+<div style="text-align: center;">o o o</div>
+<div style="text-align: center;">...</div>
+<br>
+
+## Solution
+
+To solve this problem, let's take another look at the inequalities at the
+beginning of this section and expand them:
+
+$$
+\begin{eqnarray}
+ &  c \leq C_1 \qquad m \leq M_1 \qquad y \leq Y_1 \qquad k \leq K_1 , \\
+ &  c \leq C_2 \qquad m \leq M_2 \qquad y \leq Y_2 \qquad k \leq K_2 , \\
+ &  c \leq C_3 \qquad m \leq M_3 \qquad y \leq Y_3 \qquad k \leq K_3
+\end{eqnarray}
+$$
+
+Using [a minimum property](#a-minimum-property) on each ink, we then have that:
+
+$$
+\begin{eqnarray}
+ &  c \leq \min(C_1, C_2, C_3) , \qquad
+    m \leq \min(M_1, M_2, M_3) , \\
+ &  y \leq \min(Y_1, Y_2, Y_3) , \qquad
+    k \leq \min(K_1, K_2, K_3) .
+\end{eqnarray}
+$$
+
+### The algorithm
+
+Having everything prepared, we can explain the following algorithm that searches
+for a possible solution:
+
+1. Set `my_color = [0, 0, 0, 0]`.
+1. Assign the current color `COL = Cyan`.
+1. Compute `col = min(COL_1, COL_2, COL_3)` and assign `my_color[i] = col`,
+   where `i` is the respective color position.
+1. Compute the sum of the integers in `my_color` and store it in `sum_of_units`.
+1. Is `sum_of_units >= 1 000 000`?
+    - If it is, compute `difference = sum_of_units - 1,000,000` and assign
+       `my_color[i] = my_color[i] - difference`. That is your color!
+    - If it is not, assign `COL` to the next color (Magenta, Yellow or Black)
+      and return to step 3.
+1. If you're out of colors and `sum_of_units` is still less than 1,000,000, then
+   it is impossible to solve the problem. Thus, print `IMPOSSIBLE`.
+
+Let's see some examples on how this works.
+
+### Examples
+
+<div style="text-align: center; font-weight: bold;">Input 1</div>
+
+$$
+\begin{align*}
+  C_1 &= 768\,763 &\qquad M_1 &= 148\,041 &\qquad Y_1 &= 178\,147 &\qquad K_1 &=
+  984\,173 \\
+  C_2 &= 699\,508 &\qquad M_2 &= 515\,362 &\qquad Y_2 &= 534\,729 &\qquad K_2 &=
+  714\,381 \\
+  C_3 &= 949\,704 &\qquad M_3 &= 625\,054 &\qquad Y_3 &= 946\,212 &\qquad K_3 &=
+  951\,187
+\end{align*}
+$$
+
+<div style="text-align: center; font-weight: bold;">Steps 1</div>
+
+1. $\texttt{my_color} = [0, 0, 0, 0]$.
+1. We'll start with the color Cyan.
+1. $\min(C_1, C_2, C_3) = 699\,508$. We assign this value to $\texttt{my_color}
+   = [699\,508,\; 0,\; 0,\; 0]$.
+1. $\texttt{sum_of_units} = 699\,508 + 0 + 0 + 0 = 699\,508$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Nope.** Now follow with the color Magenta.
+1. $\min(M_1, M_2, M_3) = 148\,041$. We assign this value to $\texttt{my_color}
+   = [699\,508,\; 148\,041,\; 0,\; 0]$.
+1. $\texttt{sum_of_units} = 699\,508 + 148\,041 + 0 + 0 = 847\,549$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Nope.** Now follow with the color Yellow.
+1. $\min(Y_1, Y_2, Y_3) = 178\,147$. We assign this value to $\texttt{my_color}
+   = [699\,508,\; 148\,041,\; 178\,147,\; 0]$.
+1. $\texttt{sum_of_units} = 699\,508 + 148\,041 + 178\,147 + 0 = 1\,025\,696$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Yup.** $\texttt{difference} = 1\,025\,696 - 1\,000\,000 = 25\,696$.
+  - $\texttt{my_color[3]} = 178\,147 - 25\,696 = 152\,451$.
+  - $\texttt{my_color} = [699\,508,\; 148\,041,\; 152\,451,\; 0]$ is our color!
+
+<br>
+
+<div style="text-align: center; font-weight: bold;">Input 2</div>
+
+$$
+\begin{align*}
+  C_1 &= 1\,000\,000 &\qquad M_1 &= 1\,000\,000 &\qquad Y_1 &= 0 &\qquad K_1 &=
+  0 \\
+  C_2 &= 0 &\qquad M_2 &= 1\,000\,000 &\qquad Y_2 &= 1\,000\,000 &\qquad K_2 &=
+  1\,000\,000 \\
+  C_3 &= 999\,999 &\qquad M_3 &= 999\,999 &\qquad Y_3 &= 999\,999 &\qquad K_3 &=
+  999\,999
+\end{align*}
+$$
+
+<div style="text-align: center; font-weight: bold;">Steps 2</div>
+
+1. $\texttt{my_color} = [0, 0, 0, 0]$.
+1. We'll start with the color Cyan.
+1. $\min(C_1, C_2, C_3) = 0$. We assign this value to $\texttt{my_color}
+   = [0,\; 0,\; 0,\; 0]$.
+1. $\texttt{sum_of_units} = 0 + 0 + 0 + 0 = 0$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Nope.** Now follow with the color Magenta.
+1. $\min(M_1, M_2, M_3) = 999\,999$. We assign this value to $\texttt{my_color}
+   = [0,\; 999\,999,\; 0,\; 0]$.
+1. $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Nope.** Now follow with the color Yellow.
+1. $\min(Y_1, Y_2, Y_3) = 0$. We assign this value to $\texttt{my_color}
+   = [0,\; 999\,999,\; 0,\; 0]$.
+1. $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Nope.** Now follow with the color Black.
+1. $\min(K_1, K_2, K_3) = 0$. We assign this value to $\texttt{my_color}
+   = [0,\; 999\,999,\; 0,\; 0]$.
+1. $\texttt{sum_of_units} = 0 + 999\,999 + 0 + 0 = 999\,999$.
+1. $\texttt{sum_of_units} \geq 1\,000\,000$?
+  - **Nope.** We're out of colors. D:
+  - Print `IMPOSSIBLE`.
+
+### The Code
+
+Remember that Code Jam asks us to read the ink levels from the input. For the
+examples above, the input would have looked like this:
+
+```
+2
+768763 148041 178147 984173
+699508 515362 534729 714381
+949704 625054 946212 951187
+1000000 1000000 0 0
+0 1000000 1000000 1000000
+999999 999999 999999 999999
+```
+{: file='Input'}
+
+To read the input, we need to first read the first integer $T$ and then repeat
+our algorithm $T$ times. Here's the code on how to read the printers input:
+
+```dart
+String get_input_string()
+{
+    // Read input. If it is null, return an empty string.
+    var my_input = stdin.readLineSync();
+    if (my_input != null)
+        return my_input;
+    else
+        return '';
+}
+
+List<List<int>> get_printers_input()
+{
+    // The result will be a list of lists of integers.
+    List<List<int>> printers = [];
+    for (int j = 0; j < 3; j++)
+    {
+        // We read the whole input line once. This is the info of one printer.
+        String input_line = get_input_string();
+        // We split the input using the space (' ') as a separator.
+        List<String> input_split = input_line.split(' ');
+        // We create a new list of integers, consisting of the four integers
+        // that we have read.
+        List<int> input_ints = [
+            int.parse(input_split[0]),
+            int.parse(input_split[1]),
+            int.parse(input_split[2]),
+            int.parse(input_split[3])
+        ];
+        // Finally we append the new list to our resulting list of printers.
+        printers.add(input_ints);
+    }
+    return printers;
+}
+```
+
+With the printers info, we can then code the algorithm.
+
+```dart
+List<dynamic> give_color_x(List<List<int>> printers, int color_pos)
+{
+    // Return the color on position `color_pos`.
+    return <dynamic>[
+        printers[0][color_pos],
+        printers[1][color_pos],
+        printers[2][color_pos]
+        ];
+}
+
+List<int> return_solution(List<List<int>> printers)
+{
+    List<int> my_colors = [0, 0, 0, 0];
+    for (int i = 0; i < 4; i++)
+    {
+        // Select color `i` and compute the minimum.
+        num min_units = give_color_x(printers, i).cast<num>().reduce(min);
+        // Assign the minimum to our variable `min_colors`.
+        my_colors[i] = min_units.toInt();
+        // Compute the sum of all our ink units.
+        int sum_of_units = my_colors.reduce((a, b) => a + b);
+
+        if (sum_of_units >= 1000000)
+        {
+            // If the sum is more than 1,000,000, compute the difference and
+            // subtract it from the last used color.
+            int difference = sum_of_units - 1000000;
+            my_colors[i] = my_colors[i] - difference;
+            break;
+        }
+    }
+    return my_colors;
+}
+```
+
+We then finally check if the sum of our colors is exactly 1,000,000. If it is,
+there's our solution! If it isn't, it is impossible.
+
+<br>
+<div style="text-align: center;">O &nbsp; &nbsp; O &nbsp; &nbsp; O</div>
+<div style="text-align: center;">o o o</div>
+<div style="text-align: center;">...</div>
+<br>
+
+## Alternative Solutions
+
+There was a slight variation from our approach. Instead of computing the minimum
+of an ink and immediately seeing if the sum is greater than or equal to
+1,000,000, we would compute the minimum of each ink first. If the sum of the
+minimum of the inks is greater than or equal to 1,000,000, then it was possible
+to find a solution. We would then calculate the difference between the sum and
+1,000,000. Finally we would subtract the difference from an ink. Here was my
+problem. If the difference was greater than a single ink, we would choose
+multiple inks to subtract from. I thought that checking after every ink was an
+easier problem than subtracting from possibly multiple inks.