path: root/_posts/2023-04-18-3d-printing.md

---
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.