--- title: 3D Printing (Team) categories: [Technical Logs, Team] tags: [] math: true date: 2023-04-24 13:46:27 -0600 authors: [adriz, salma] image: path: https://codejam.googleapis.com/dashboard/get_file/AQj_6U1yXmbP6Nf5PONAMbqVd5eyM5BBSbjggzDn9H6vS3ATQiqbGVrfZ0ABoAbBkn8IWocYoj1rdJim6VkTTOP4/3d_printing.png alt: "3 printers with their own ink levels." --- Try this problem by yourself first! Check the [Code Jam Page](https://codingcompetitions.withgoogle.com/codejam/round/0000000000876ff1/0000000000a4672b). ## Overview In this technical log, we will discuss different algorithmic solutions to a Google Code Jam problem where we are given three printers with different amounts of ink in their cartridges. The objective is to find a color that can be printed by all three printers using the ink they have. The color must be composed of four non-negative integers representing the amount of cyan, magenta, yellow, and black ink needed, adding up to the number of units needed to print a D.
O     O     O
o o o
...

## Context We are given three printers with their own ink levels. Ink levels are measured in units. Each printer has four different colors: Cyan, Magenta, Yellow and Black. We want to select a color defined by the number of units of cyan, magenta, yellow and black needed to form the color. Every printer must have sufficient ink to print a big D that requires $10^6$ units of ink to be printed. Representing this problem in mathematical terms will help us find the solution. Suppose the printer $i$ has a cyan ink level of $C_i$, a magenta ink level of $M_i$, yellow ink level of $Y_i$ and black ink level of $K_i$. What we want to find is $c$, $m$, $y$ and $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} $$ Notice that if $c \leq C_1$, $c \leq C_2$, $c \leq C_3$, then $c \leq \min \\{ C_1,\ C_2,\ C_3 \\}$. Thus, it is sufficient to find $c$, $m$, $y$ and $k$ integers such 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} $$ On the other hand, we also need that $$ \begin{eqnarray} & c + m + y + k = 10^6 . \end{eqnarray} $$ Finally, we have an extra restraint. Every cartridge has between 0 and $10^6$ units of ink. This is everything we need to find a solution to our problem.
O     O     O
o o o
...

## Solution The main idea for the solution to this problem is to iterate through all test cases, obtaining the available ink in each level for each printer and evaluating it to find a color that can be printed by all printers. To do the latter, first we need to find the cartridges that have the least amount of ink and use that value as a base for the ink that will be used in the other two printers. Then we can add up the values of each color until the sum is exactly $10^6$, if it exceeds $10^6$ we should subtract the excess of ink, if it falls short then we should indicate that there is no color that can be used to print a D in the three printers. The final step of the process is to display the results. 1. Initialize a variable for the test case counter. 1. For each test case, do the following: 1. Read the ink levels for each of the three printers. 1. Find the minimum ink level for each color (CMYK) across the three printers. 1. Calculate the total ink level by summing the minimum ink levels for each color. 1. Check if the total ink level is $10^6$: 1. If true, we have a valid result, and no further calculations are needed. 1. If false, adjust the ink levels as needed to ensure their sum is equal to $10^6$: 1. Calculate the difference between the total ink level and $10^6$. 1. Iterate through the minimum ink levels array and do the following: 1. If the difference is greater than the current color ink level, subtract the color ink level from the difference and set the color ink level to 0. 1. If the difference is less than the current color ink level, subtract the difference from the color ink level and break the loop. 1. If it falls short, print `IMPOSSIBLE`. 1. Print the adjusted ink levels for each color (CMYK). The solution ensures that we obtain a color that can be printed by all three printers using their available ink levels, or otherwise indicate that it is impossible to print such a color.
O     O     O
o o o
...

## Alternative Solutions Even if the algorithm implemented for all languages is basically the same, every code we built has slight differences in their approach to input reading, output formatting, and iteration. In this section we will analyze each step of the algorithm, comparing and contrasting all the solutions. 1. Initialize a variable for the test case counter. Dart, Kotlin, Python 1, and Python 2 initialize the counter implicitly by using a loop with a range. TypeScript explicitly initializes a `count` variable. 1. Read the ink levels for each of the three printers. Dart, Kotlin, and Python 1 handle reading input in the main loop, whereas Python 2 and TypeScript use separate input handling. Python 2 uses a function (`find_color`) that takes the number of test cases and printer data as arguments, while TypeScript reads printer data as strings and then converts them into arrays of numbers. 1. Find the minimum ink level for each color (CMYK) across the three printers. Dart, Kotlin, and TypeScript use a similar approach, calculating minimum ink levels for each color directly using a conditional or `Math.min()` function. Python 1 uses NumPy's `amin()` function to find the minimum ink level for each color, while Python 2 uses nested loops in the `find_color()` function to find the minimum ink levels. 1. Calculate the total ink level by summing the minimum ink levels for each color. Dart, Kotlin, and Python 2 sum the ink levels directly within the main loop, while Python 1 uses NumPy's `sum()` function. TypeScript uses the `reduce()` function to calculate the total ink level. 1. Check if the total ink level is $10^6$ and adjust the ink levels as needed. All implementations follow a similar approach, using conditional statements to check the total ink level and adjusting ink levels as needed. Python 2, however, separates this logic into the `find_color()` function. 1. Print the adjusted ink levels for each color (CMYK). Dart, Kotlin, Python 1, and Python 2 handle output formatting within the main loop, using different ways to concatenate strings (e.g., string interpolation in Dart and Kotlin). TypeScript defines a separate loop for printing the output. ### Pros and cons of each alternative | Language | Pros | Cons | |:-|:-|:-| | Dart | | Does not use any data structure
optimizations, such as lists or
tuples, which could potentially
simplify the implementation and
improve code readability. | | Kotlin | Reads input and prints output
within the main loop, simplifying
the code structure. | Does not separate the logic for
finding the ink levels into a
separate function, which could
make the code less modular and
harder to reuse or refactor. | | Python code 1 | Makes use of NumPy for array
operations, which can be efficient
for larger datasets. | Uses multiple for-loops to handle
printer input, which could make
the code less readable and harder
to maintain, especially when
dealing with a larger number of
printers. | | Python code 2 | Separates the logic for finding the
ink levels into a separate function,
making the code more modular
and reusable. | Does not use any specialized
libraries or built-in functions to
optimize the calculation of the
minimum ink levels, which may
lead to a less efficient or slower
solution. Nested loops in the
`find_color()` function make
the code slightly less readable. | | Typescript | | Uses hard-coded input values for
testing, making it less flexible for
testing with different input cases. | | Dart, Kotlin and
Typescript | Use of greedy algorithm for
adjusting ink levels, which leads
to more efficient code by
reducing the number of iterations. | | | Kotlin and Dart | | Less efficient loop for adjusting
the ink levels, as it could require
additional iterations. | | Python code
1 and 2 | Use of list comprehension in
reading inputs results in concise
code. | | {: width="10" height="1000" .w-75}