diff options
Diffstat (limited to '_posts')
| -rw-r--r-- | _posts/2023-04-18-3d-printing.md | 332 |
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 O 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 O 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 O 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. |