You are given twelve coins, one of which is counterfeit. The counterfeit coin looks identical to the other eleven, but weighs either slightly less or]]>

You are given twelve coins, one of which is counterfeit. The counterfeit coin looks identical to the other eleven, but weighs either slightly less or slightly more. To help identify the counterfeit you are given a balance scale that you may use up to three times.

Before solving the problem, the problem must be well understood. While this seems obvious, it is relatively easy to overlook an aspect of the problem description that can greatly simplify things. In addition to considering what is stated in the problem, it is often just as crucial to evaluate what is **not** stated. Keeping this in mind while assessing the description, we can determine eight things.

- There are precisely twelve coins.
- One of them is
*guaranteed*to be a counterfeit coin (the case of no counterfeit coin does not need to be considered). - The only tool available is a simple balance scale.
- The balance scale may be used a maximum of three times.
- Not every coin needs to be a part of every weighing (which may seem silly to point out but is crucial to the solution).
- Coins may be weighed more than once and in any combination.
- All we have to do is
*identify*the counterfeit coin, not whether it is heavy or light. - Any scale use only makes sense if the number of coins is equal on each side.

Being able to leave coins out is essential. Without this possibility, every coin must be on the left or right for every scale use. That would only give us two options for a coin at each weighing. With only two options and three uses of the scale permitted, there would be \(2^3 = 8\) unique combinations (three bits of information). Eight unique combinations would not be enough to identify the counterfeit with twelve coins on the table. Leaving a coin out adds another possible state, resulting in \(3^3 = 27\) unique combinations (three trits of information).

One unfortunate stipulation, which makes this problem so interesting, is that it is unknown whether the counterfeit coin is lighter or heavier than the others. The lack of certainty is significant because when one side of the scale is heavy, it only tells us that a counterfeit is currently on the scale, not which side it is on. Therefore a particular combination of trits and its inverse would have to point to the same coin as the counterfeit. This dual nature limits the number of options to half of the original possible combinations, theoretically allowing the ability to identify 13.5 coins (though this is impossible) successfully.

With the problem well understood, it is now possible to develop a system that uniquely identifies any coin as counterfeit. The system will also consider whether the coin is heavier or lighter than the others.

The table below shows the potential patterns assuming that the coin is based on the left plate by default. Since it is a balance scale, the coins can not reasonably only use the left side to start. The table illustrates all the potential combinations of trits that could produce unique information.

Another critical aspect is that both a sequence and its inverse point to the same coin. One sequence represents the case where the coin is heavy and the other when the coin is light. Inversion only applies when a coin is on the scale with (\neg L \rightarrow R) (inverting (L) being down means (R) must be down and vice-versa). The "half option" mentioned above is the unlikely case where a coin is not included in any comparisons (meaning none of the weighed coins is counterfeit). Being entirely excluded has an inverse that is still the same information (not included). Therefore, this option cannot reveal whether the counterfeit coin is heavy or light.

In no particular pattern order, the table below shows a theoretical way to uniquely identify which of fourteen coins could be counterfeit and which of thirteen are either heavier or lighter than the others.

Coin | Heavy Pattern | Light Pattern |
---|---|---|

A | \(LLL\) | \(RRR\) |

B | \(LLR\) | \(RRL\) |

C | \(LRR\) | \(RLL\) |

D | \(LRL\) | \(RLR\) |

E | \(NLL\) | \(NRR\) |

F | \(NLR\) | \(NRL\) |

G | \(LNL\) | \(RNR\) |

H | \(LNR\) | \(RNL\) |

I | \(LLN\) | \(RRN\) |

J | \(LRN\) | \(RLN\) |

K | \(NNL\) | \(NNR\) |

L | \(NLN\) | \(NRN\) |

M | \(LNN\) | \(RNN\) |

N | \(NNN\) | \(NNN\) |

The table entries obviously cannot work directly as the first use of the scale would put nine coins on the left side and none on the right, which ultimately tells us nothing. The trick is selecting each round to maximize the information obtained.

💡

For the problem to work within the confines of its description, some coins flip their heavy/light patterns so that the scale always has the same number of coins on each side. The swapping of some columns gives a new pattern table utilizing a compatible subset of options:

Coin | Heavy Pattern | Light Pattern |
---|---|---|

B | \(LLR\) | \(RRL\) |

C | \(LRR\) | \(RLL\) |

D | \(LRL\) | \(RLR\) |

E | \(NLL\) | \(NRR\) |

F | \(NLR\) | \(NRL\) |

G | \(LNL\) | \(RNR\) |

H | \(RNL\) | \(LNR\) |

I | \(RRN\) | \(LLN\) |

J | \(RLN\) | \(LRN\) |

K | \(NNR\) | \(NNL\) |

L | \(NRN\) | \(NLN\) |

M | \(RNN\) | \(LNN\) |

By reading down the Heavy Pattern column in the table we can assign coins to the scale plates for each round and verify that there is always the same number of coins on each side.

Round | Left Plate Coins | Right Plate Coins |
---|---|---|

1 | BCDG | HIJM |

2 | BEFJ | CDIL |

3 | DEGH | BCFK |

For this solution to be valid, it must work. The table below shows the results of the three uses of the scale with an interpretation according to the above tables. The results use the following letters as a shorthand:

- \(N\): Scale did not tip in either direction (balanced).
- \(L\): The left plate was heavier.
- \(R\): The right plate was heavier.

Result | Meaning |
---|---|

\(NNN\) | There is no counterfeit coin (hidden coin N) |

\(LRL\) | D is a heavy counterfeit coin |

\(NLN\) | L is a light counterfeit coin |

To make things easier, the solution maps a unit square to the square defined by the pair of vectors. In other words:

\begin{align} (0, 0, 1) &\mapsto A \\ (0, 1, 1) &\mapsto B \\ (1, 0, 1) &\mapsto C \\ (1, 1, 1) &\mapsto D \end{align}Using the above notation, it is possible to start calculating the matrix which will take any 2D point in unit coordinates and convert it to projected coordinates.

\[ \left[ { \begin{array}{ccc} M_{11} & M_{12} & M_{13} \\ M_{21} & M_{22} & M_{23} \\ M_{31} & M_{32} & 1 \end{array} } \right] \]With the mapping to point \(A\) being straightforward, two entries can already be solved for (subscripts \(x\) and \(y\) are for the 2D components):

\begin{align} M_{13} &= A_x \\ M_{23} &= A_y \end{align}Using the unit mappings with the matrix and factoring in the perspective divide required for points gets the following system of equations for matrix elements to known points.

\begin{align} {M_{12} + A_x}\over{M_{32} + 1} &= B_x \\ \\ {M_{22} + A_y}\over{M_{32} + 1} &= B_y \\ \\ {M_{11} + A_x}\over{M_{31} + 1} &= C_x \\ \\ {M_{22} + A_x}\over{M_{31} + 1} &= C_y \\ \\ {M_{11} + M_{12} + A_x}\over{M_{31} + M_{32} + 1} &= D_x \\ \\ {M_{21} + M_{22} + A_x}\over{M_{31} + M_{32} + 1} &= D_y \end{align}Multiplying both sides by the left-hand denominator and arranging all matrix terms to the left and all constant terms to the right changes the equations to:

\begin{align} M_{12} - B_{x}M_{32} &= B_x - A_x \\ M_{22} - B_{y}M_{32} &= B_y - A_y \\ M_{11} - C_{x}M_{31} &= C_x - A_x \\ M_{21} - C_{y}M_{31} &= C_y - A_y \\ M_{11} + M_{12} - D_{x}M_{31} - D_{x}M_{32} &= D_x - A_x \\ M_{21} + M_{22} - D_{y}M_{31} - D_{y}M_{32} &= D_y - A_y \end{align}Setting up the equations to perform Gaussian Elimination on them yields:

\[ \begin{array}{cccccccc} M_{11} & M_{12} & M_{21} & M_{22} & M_{31} & M_{32} \\ 1 & 0 & 0 & 0 & -C_x & 0 & = & C_x - A_x \\ 0 & 1 & 0 & 0 & 0 & -B_x & = & B_x - A_x \\ 0 & 0 & 1 & 0 & -C_y & 0 & = & C_y - A_y \\ 0 & 0 & 0 & 1 & 0 & -B_y & = & B_y - A_y \\ 1 & 1 & 0 & 0 & -D_x & -D_x & = & D_x - A_x \\ 0 & 0 & 1 & 1 & -D_y & -D_y & = & D_y - A_y \end{array} \]The top four rows are already in a nice enough form that their equations can be extracted directly:

\begin{align} M_{11} &= (1 + M_{31})C_x - A_x \\ M_{12} &= (1 + M_{32})B_x - A_x \\ M_{21} &= (1 + M_{31})C_y - A_y \\ M_{22} &= (1 + M_{32})B_y - A_y \end{align}Subtracting out the first two rows from the fifth row and the middle two rows from the last row results in:

\[ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & C_x - D_x & B_x - D_x & = & D_x + A_x - B_x - C_x \\ 0 & 0 & 0 & 0 & C_y - D_y & B_y - D_y & = & D_y + A_y - B_y - C_y \end{array} \]These two equations serve as the starting point for determining the \(M_{31}\) and \(M_{32}\) terms. Focusing on simplifying the \(M_{31}\) term first through division yields:

\[ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & 1 & {B_x - D_x}\over{C_x - D_x} & = & {D_x + A_x - B_x - C_x}\over{C_x - D_x} \\ 0 & 0 & 0 & 0 & 1 & {B_y - D_y}\over{C_y - D_y} & = & {D_y + A_y - B_y - C_y}\over{C_y - D_y} \end{array} \]Subtraction of the top equation from the bottom and subsequent division results in the very large (but ultimately very simple) equation for \(M_{32}\):

\begin{align} \left( { \frac{B_y - D_y}{C_y - D_y} - \frac{B_x - D_x}{C_x - D_x} } \right) M_{32} &= \frac{D_y + A_y - B_y - C_y}{C_y - D_y} - \frac{D_x + A_x - B_x - C_x}{C_x - D_x} \\ M_{32} &= \frac{\frac{D_y + A_y - B_y - C_y}{C_y - D_y} - \frac{D_x + A_x - B_x - C_x}{C_x - D_x}}{\frac{B_y - D_y}{C_y - D_y} - \frac{B_x - D_x}{C_x - D_x}} \end{align}Dividing out the \(M_{32}\) term instead before subtracting the bottom equation from the top and dividing solves for \(M_{31}\).

\[ \begin{array}{cccccccc} 0 & 0 & 0 & 0 & {C_x - D_x}\over{B_x - D_x} & 1 & = & {D_x + A_x - B_x - C_x}\over{B_x - D_x} \\0 & 0 & 0 & 0 & {C_y - D_y}\over{B_y - D_y} & 1 & = & {D_y + A_y - B_y - C_y}\over{B_y - D_y} \end{array} \]$$ M_{31} = \frac{\frac{D_x + A_x - B_x - C_x}{B_x - D_x} - \frac{D_y + A_y - B_y - C_y}{B_y - D_y}}{\frac{C_x - D_x}{B_x - D_x} - \frac{C_y - D_y}{B_y - D_y}} $$Continuing forward with \(M_{31}\) and using algebraic techniques to consolidate and simplify terms brings about:

\begin{align} M_{31} =& \frac{(D_x + A_x - B_x - C_x)(B_y - D_y) - (D_y + A_y - B_y - C_y)(B_x - D_x)}{(B_x - D_x)(B_y - D_y)} \\ &\cdot \frac{(B_x - D_x)(B_y - D_y)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} \\ \\ =& \frac{(D_x + A_x - B_x - C_x)(B_y - D_y) - (D_y + A_y - B_y - C_y)(B_x - D_x)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} \\ \\ =& { \scriptsize \frac{(A_x - C_x)(B_y - D_y) - (B_x - D_x)(B_y - D_y) - (A_y - C_y)(B_x - D_x) + (B_x - D_x)(B_y - D_y)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} } \\ \\ =& \frac{(A_x - C_x)(B_y - D_y) - (A_y - C_y)(B_x - D_x)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} \end{align}Doing the same for \(M_{32}\):

\begin{align} M_{32} =& \frac{(D_y + A_y - B_y - C_y)(C_x - D_x) - (D_x + A_x - B_x - C_x)(C_y - D_y)}{(C_y - D_y)(C_x - D_x)} \\ &\cdot \frac{(C_y - D_y)(C_x - D_x)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} \\ \\ =& \frac{(D_y + A_y - B_y - C_y)(C_x - D_x) - (D_x + A_x - B_x - C_x)(C_y - D_y)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} \\ \\ =& {\scriptsize \frac{(A_y - B_y)(C_x - D_x) - (C_x - D_x)(C_y - D_y) - (A_x - B_x)(C_y - D_y) + (C_x - D_x)(C_y - D_y)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} } \\ \\ =& \frac{(A_y - B_y)(C_x - D_x) - (A_x - B_x)(C_y - D_y)}{(B_y - D_y)(C_x - D_x) - (B_x - D_x)(C_y - D_y)} \end{align}With the equations simplified it becomes a little easier to see that it is a combination of several vectors based on the provided \(A, B, C, D\) points. Also notable is that \(M_{31}\) and \(M_{32}\) share a denominator. Using \(^{\curvearrowleft}\) to be mean rotating a vector counter-clockwise by \(90^{\circ}\), the equations for each matrix component become:

\begin{align} u &= \overrightarrow{DC} \cdot \overrightarrow{DB}^{\curvearrowleft} \\ M_{31} &= \frac{\overrightarrow{CA} \cdot \overrightarrow{DB}^{\curvearrowleft}}{u} \\ M_{32} &= \frac{\overrightarrow{DC} \cdot \overrightarrow{BA}^{\curvearrowleft}}{u} \\ \\ M_{11} &= (1 + M_{31})C_x - A_x \\ M_{12} &= (1 + M_{32})B_x - A_x \\ M_{21} &= (1 + M_{31})C_y - A_y \\ M_{22} &= (1 + M_{32})B_y - A_y \end{align}Placing these calculated values in the matrix allows for transforming arbitrary points from normalized space into the projected space defined by \(\overrightarrow{AB}\) and \(\overrightarrow{CD}\). It is important to divide by the resulting \(z\) term to normalize the resulting 2D coordinate just as you would divide by the resulting \(w\) term for a 3D perspective transformation.

]]>One advantageous operation is rendering a Bezier curve when working with path nodes. In most cases, you do not care about the bounds of the curve itself because it is a line, the drawing area is of fixed size, or the view is movable. On the other hand, wanting to size an SVG view box to a Bezier curve means that calculating the precise bounds of the curve is very useful.

Calculating the bounds first requires the equation by which Beziers are defined. The equation for a point on a cubic Bezier \(\textbf{B}(t)\) is defined as (notice the presence of the binomial theorem):

$$ \textbf{B}(t) = (1 - t)^3\textbf{P}_0 + 3(1 - t)^2t\textbf{P}_1 + 3(1 - t)t^2\textbf{P}_2 + t^3\textbf{P}_3 $$

The curve is officially defined for the \([0,1]\) range. Locating the bounds requires finding precisely where the curve "turns around" in either the \(x\) or \(y\) direction. These are called the inflection points and are readily found by the proper application of calculus. If you do not want to see how the calculus is done, you can skip past it.

The first step to finding the inflection points is calculating the curve's derivative. It is possible to find the inflection points in every dimension using the calculated derivative. Due to the nature of the curve, every inflection point that is both a real number and within the \([0,1]\) range will be an excellent candidate for calculating the overall bounds.

The derivative is pretty straightforward if you know how to apply the chain rule, the product rule. Remember that the points are constants and work one chunk at a time.

The first chunk is pretty easy, thanks to the chain rule.

\begin{align}

\textbf{B}(t) &= (1 - t)^3\textbf{P}_0 + \dots & u &= 1 - t\cr

&= u^3\textbf{P}_0 + \dots\cr\cr

\textbf{B}'(t) &= 3u^2u'\textbf{P}_0 + \dots & u' &= -1\cr

&= -3(1-t)^2\textbf{P}_0 + \dots \cr

&= -3(t^2 - 2t + 1)\textbf{P}_0 + \dots

\end{align}

The second chunk is a bit more complicated, and at first glance, there are two ways to do it. One way involves simply expanding the term, and the other way uses a combination of the product rule and the chain rule.

By way of expansion, there are only a few steps.

\begin{align}

\textbf{B}(t) &= \dots + 3(1 - t)^2t\textbf{P}_1 + \dots \cr

&= \dots + 3(t^2 -2t + 1)t\textbf{P}_1 + \dots \cr

&= \dots + 3(t^3 -2t^2 + t)\textbf{P}_1 + \dots \cr

\textbf{B}'(t) &= \dots + 3(3t^2 -4t + 1)\textbf{P}_1 + \dots

\end{align}

Combining the product and chain rules is more complex than expanding the term, even though the first step seems like a logical jump.

\begin{align}

\textbf{B}(t) &= \dots + 3(1 - t)^2t\textbf{P}_1 + \dots \cr

&= \dots + 3u^2t\textbf{P}_1 + \dots & u &= 1 - t \cr

\textbf{B}'(t) &= \dots + (6uu't + 3u^2)\textbf{P}_1 + \dots & u' &= -1 \cr

&= \dots + 3(u^2 - 2ut)\textbf{P}_1 + \dots \cr

&= \dots + 3((1-t)^2 - 2(1-t)t)\textbf{P}_1 + \dots\cr

&= \dots + 3(t^2 - 2t + 1 - 2t + 2t^2)\textbf{P}_1 + \dots \cr

&= \dots + 3(3t^2 -4t + 1)\textbf{P}_1 + \dots \cr

\end{align}

Both ultimately yielded the same result, though an initial substitution instinct resulted in more work. Being aware of this while looking at the third term expansion seems like the better choice, especially considering the simplicity.

\begin{align}

\textbf{B}(t) &= \dots + 3(1 - t)t^2\textbf{P}_2 + \dots \cr

&= \dots + 3(t^2 - t^3)\textbf{P}_2 + \dots \cr

\textbf{B}'(t) &= \dots + 3(2t - 3t^2)\textbf{P}_2 + \dots \cr

\end{align}

The final term is straightforward to derive and is just one step.

\begin{align}

\textbf{B}(t) &= \dots + t^3\textbf{P}_3 \cr

\textbf{B}'(t) &= \dots + 3t^2\textbf{P}_3

\end{align}

Adding all the pieces together results in a derivative similar to the original equation.

$$ \textbf{B}'(t) = -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3 $$

From the previous section we calculated that the derivative is:

$$ \textbf{B}'(t) = -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3 $$

The next step to finding the points of inflection for each dimension \((x, y, z)\) is to solve that equation for the values of \(t\) that make \(\textbf{B}'(t) = 0\) for that dimension. This seems like an impossible task given the size of the equation, but on closer inspection, it is clear that there are no higher-order terms than \(t^2\). Perhaps the equation can be rearranged in terms of \(t\) so that the quadratic equation can be used to solve it. Turning the equation into standard quadratic form takes only a few steps.

\begin{align}

\textbf{B}'(t) &= -3(t^2 - 2t + 1)\textbf{P}_0 + 3(3t^2 -4t + 1)\textbf{P}_1 + 3(2t - 3t^2)\textbf{P}_2 + 3t^2\textbf{P}_3\cr

0 &= 3(-(t^2 - 2t + 1)\textbf{P}_0 + (3t^2 -4t + 1)\textbf{P}_1 + (2t - 3t^2)\textbf{P}_2 + t^2\textbf{P}_3)\cr

&= -(t^2 - 2t + 1)\textbf{P}_0 + (3t^2 -4t + 1)\textbf{P}_1 + (2t - 3t^2)\textbf{P}_2 + t^2\textbf{P}_3\cr

&= -\textbf{P}_0t^2 + 2\textbf{P}_0t - \textbf{P}_0 + 3\textbf{P}_1t^2 - 4\textbf{P}_1t + \textbf{P}_1 - 3\textbf{P}_2t^2 + 2\textbf{P}_2t + \textbf{P}_3t^2\cr

&= -\textbf{P}_0t^2 + 3\textbf{P}_1t^2 - 3\textbf{P}_2t^2 + \textbf{P}_3t^2 + 2\textbf{P}_0t - 4\textbf{P}_1t + 2\textbf{P}_2t - \textbf{P}_0 + \textbf{P}_1\cr

&= (-\textbf{P}_0 + 3\textbf{P}_1 - 3\textbf{P}_2 + \textbf{P}_3)t^2 + (2\textbf{P}_0 - 4\textbf{P}_1 + 2\textbf{P}_2)t + (-\textbf{P}_0 + \textbf{P}_1)

\end{align}

To make things a little easier, it makes sense to go ahead and save off the groupings in simple variables, making composition into the quadratic formula much easier.

\begin{align}

0 &= at^2 + bt + c\cr

\text{where:}\cr

a &= \textbf{P}_3 - 3\textbf{P}_2 + 3\textbf{P}_1 - \textbf{P}_0\cr

b &= 2\textbf{P}_2 - 4\textbf{P}_1 + 2\textbf{P}_0\cr

c &= \textbf{P}_1 - \textbf{P}_0

\end{align}

I flipped the order of the points around so the subtraction lines up a little nicer, but other than that, it is a simple substitution that plugs nicely into the quadratic formula.

\begin{gather}

\Delta = b^2 - 4ac\cr

\frac{-b \pm \sqrt\Delta}{2a}

\end{gather}

Notice that the delimiter is kept separate because there is no real answer if \(\Delta < 0\).

Now that things are in easy-to-digest pieces, it is time to implement all the hard work into some code. Since the derivative only gives the values in terms of \(t\), they will need to be plugged into the Bezier equation in order to get the actual \((x,y)\) points of the inflection.

There will be four functions in total. The first accepts the \((x,y)\) points to apply the derivative. The second accepts just a single dimension for each point to apply the derivative. The third calculates the result of \((x,y)\) points and a \(t\) value with the Bezier equation. The fourth and final function calculates the Bezier equation for a single dimension. In JavaScript it looks like this:

```
function getBezierInflectionPoints(p0, p1, p2, p3) {
return getBezierInflectionPointsForDimension(p0.x, p1.x, p2.x, p3.x)
.concat(getBezierInflectionPointsForDimension(p0.y, p1.y, p2.y, p3.y))
.map(function(t) {
return getBezierPoint(p0, p1, p2, p3, t);
});
}
function getBezierInflectionPointsForDimension(p0, p1, p2, p3) {
var a = p3 - 3 * p2 + 3 * p1 - p0,
b = 2 * p2 - 4 * p1 - 2 * p0,
c = p1 - p0,
delimiter = b * b - 4 * a * c,
value = 0,
values = [];
if (delimiter >= 0) {
value = (-b + Math.sqrt(delimiter)) / (2 * a);
if (value > 0 && value < 1) {
values.push(value);
}
value = (-b - Math.sqrt(delimiter)) / (2 * a);
if (value > 0 && value < 1) {
values.push(value);
}
}
return values;
}
function getBezierPoint(p0, p1, p2, p3, t) {
return {
x: getBezierPointForDimension(p0.x, p1.x, p2.x, p3.x, t),
y: getBezierPointForDimension(p0.y, p1.y, p2.y, p3.y, t)
};
}
function getBezierPointForDimension(p0, p1, p2, p3, t) {
return Math.pow(1 - t, 3) * p0
+ 3 * Math.pow(1 - t, 2) * t * p1
+ 3 * (1 - t) * Math.pow(t, 2) * p2
+ Math.pow(t, 3) * p3;
}
```

The critical thing to remember is that rendered Bezier curves have a width (otherwise, you could not see it unless it is filled in, of course). It is a good idea to add and subtract half of the stroke-width to both the \(x\), and \(y\) coordinates that come back from the function to ensure that the curve is not "cut in half" at the boundaries.

It is also a good idea to avoid unnecessary calculations whenever possible. This is very easy because of how Bezier curves are defined mathematically. If the middle points in the set exist within the bounds of the outer points (\(\textbf{P}_1\) and \(\textbf{P}_2\) exist within \([\textbf{P}_0, \textbf{P}_3]\)) no additional calculation needs to be done beyond the bounds of the outer points (factoring in stroke-width of course). While this may only eliminate a few cases here and there, quite a few operations get saved in the process. The thing to keep in mind is that if either point strays outside the \([\textbf{P}_0, \textbf{P}_3]\) bounds, the full calculations should be run.

Are there any approximations that can be done to save on math? Sure, but this gives you precise boundaries, and the number of calculations saved is generally not going to be significant. Besides, how frequently will this code be run, and is it the bottleneck?

]]>One thing that has come up at work is the size and speed of our git repository. It is over 4GB with more than 15,700 commits and just under 46,000 files. This makes things very slow. It has also made cloning the repository physically impossible as the server

]]>One thing that has come up at work is the size and speed of our git repository. It is over 4GB with more than 15,700 commits and just under 46,000 files. This makes things very slow. It has also made cloning the repository physically impossible as the server runs out of memory about 60% of the way through (I tried continuously between 22:00 and 1:00 last night/this morning). As such, it has been decided that this needs to be corrected.

One thing was that we used to keep many SVGs and Adobe Illustrator files in our history. We could remove these and free up half the repository, but do we need all our history since the beginning of this repo? The answer was no. We do not need anything older than three months. We plan to split the repo apart to give each team a different repo. Having separate repositories avoids merges similar to those that have destroyed work in the past.

The question is how to get rid of these commits? There are many resources for doing this, including a great Stack Overflow post and a convenient tip on Code Project, and in the Git docs themselves. At first, I sought to remove the offending images folder from the history separately from the date-based removal, but this was not necessary because three months ago, this was already removed from the repository. As such, I merely needed to delete everything more than three months old. Things were a bit tricky, though, because of how `git filter-branch`

behaved regarding variables in the shell. Ultimately I ended up with the solution below for cleaning out the history. The script is not the whole solution. After running it, it is necessary to repack and forcibly push it to the server. The push is a **destructive** operation, so everyone with a copy will likely need to download the repository again, or you risk the old stuff coming back. The code below is for a Mac, so particular parameters may need to change.

```
git filter-branch --commit-filter '\
commitDate=$(echo "$GIT_COMMITTER_DATE" | cut -d " " -f 1 | cut -d "@" -f 2);\
oldDate=$(date -v-3m -v0H -v0M -v0S "+%s");\
if [ $commitDate -lt $oldDate ];\
then\
skip_commit "$@";\
else\
git commit-tree "$@";\
fi' -- --all
```

]]>Recently I decided to clear out my mobile notifications on Twitter in their entirety. This sounds simple enough, but I had about 102 handles being sent to my phone and there was no way to tell which from the site. Feel free to look. Since there was no easy way

]]>Recently I decided to clear out my mobile notifications on Twitter in their entirety. This sounds simple enough, but I had about 102 handles being sent to my phone and there was no way to tell which from the site. Feel free to look. Since there was no easy way to clear all mobile notifications without just turning them off entirely I set out to do it programmatically.

First thing I needed to know was how to trigger native click events, luckily Mozilla has a page for that. With this under my arm I headed into my browser and opened up the command console. Luckily Twitter identifies users being followed with a "notifying" class name, but it is higher in the hierarchy than one might expect. After a lot of messing around I learned that I could not do it all in one fell swoop because any delays using JavaScript's `setTimeout()`

method got cleared out when the page changed (at least on Chrome), I assume this is a security measure, and it's generally pretty good that it's there. In this case, however, it became quite a nuisance. I also learned that I couldn't just keep "clicking" the "Turn off mobile notifications" button without first opening the actual drop-down. I would wager a guess that this is another security measure of sorts.

In the end I had to run a line of code 102 times to clear out the notifications, but that's not too bad (considering it is just up-arrow, enter over and over) compared to hunting this all manually. This little script simply opens the drop-down for the first user in the list that you are receiving notifications for, and then "clicks" the "Turn off mobile notifications" button after 1 second. You can run it in a console, or in the browser's URL bar by first prefixing it with "`javascript:`

", just remember to scroll all the way to the bottom of your following page before you use it (so everyone can load). If Twitter just had a more friendly interface in this area, none of this would even be necessary.

```
(function(){var e=new MouseEvent('click',{'view':window,'bubbles':true,'cancelable':true});var a=document.getElementsByClassName("notifying");if(a[0]){a[0].getElementsByClassName("dropdown-toggle")[0].dispatchEvent(e);setTimeout(function(){a[0].getElementsByClassName("device-notifications-off-text")[0].dispatchEvent(e);},1000);}})();
```

Here is something a little more readable so you can get an idea for how it works:

```
(function()
{
var e = new MouseEvent('click', {'view':window,
'bubbles':true,
'cancelable':true});
var a = document.getElementsByClassName("notifying");
if (a[0]) {
a[0].getElementsByClassName("dropdown-toggle")[0].dispatchEvent(e);
setTimeout(function()
{
a[0].getElementsByClassName("device-notifications-off-text")[0].dispatchEvent(e);
},1000);
}
})();
```

]]>A physics problem typically involves using a given angle and velocity to determine where a projectile lands. This is all well and good, but when working on a game with projectiles, you already know where it should land and at what angle it should be launched. This article shows the

]]>A physics problem typically involves using a given angle and velocity to determine where a projectile lands. This is all well and good, but when working on a game with projectiles, you already know where it should land and at what angle it should be launched. This article shows the process by which I solved the basic physics equations to take in the desired difference in distance, height, and launch angle to give you the required velocity in return. If you are not interested in the work, you can skip to the solution. Without further ado, here is how I solved the equations.

\begin{align}

x\prime &= x + tv\cos\theta\cr

y\prime &= y + tv\sin\theta - \frac{1}{2}gt^2

\end{align}

\begin{align}

x\prime - x &= tv\cos\theta\tag{x.1}\cr

d &= tv\cos\theta\label{x.2}\tag{x.2}

\end{align}

\begin{align}

0 &= y - y\prime + tv\sin\theta - \frac{1}{2}gt^2\tag{y.1}\cr

0 &= h + tv\sin\theta - \frac{1}{2}gt^2\label{y.2}\tag{y.2}

\end{align}

To make things more obvious, we will replace the differences with a single variable, namely \(d = x\prime - x\) (where \(d\) is the intended travel distance), and \(h = y - y\prime\) (where \(h\) is how high the projectile starts relative to its ending height).

For this equation to work, time cannot be a factor. In truth, it does not matter how long the projectile takes to get there, just that we arrive. If you need time later, divide the range by the \(x\) velocity component. Since the \(y\) equation has a quadratic for time, we will solve that one.

Using the condensed height equation in \(\eqref{y.2}\), we can solve using the quadratic formula (and some basic negation cancellation).

\begin{align}

t = \frac{v\sin\theta \pm \sqrt{v^2\sin^2\theta + 2gh}}{g}\label{t}\tag{t}

\end{align}

Since we know that what is coming out of the square root is positive, we can eliminate the possibility of a negative option being the one we ultimately want. The projectile is supposed to be moving forwards after all.

Now that we have time eliminated from \(\eqref{t}\), we need to plug it in to the \(\eqref{x.2}\) equation.

$$ d = \frac{v\cos\theta}{g}\left[v\sin\theta + \sqrt{v^2\sin^2\theta + 2gh}\right] $$

Then we need to solve that monster for \(v\). We start by moving \(g\) over, and distributing \(v\cos\theta\).

\begin{align}

dg =& v\cos\theta\left[v\sin\theta + \sqrt{v^2\sin^2\theta + 2gh}\right]\nonumber\cr

=& v^2\sin\theta\cos\theta + v\cos\theta\sqrt{v^2\sin^2\theta + 2gh}\nonumber\cr

=& v^2\sin\theta\cos\theta + \sqrt{v^4\sin^2\theta\cos^2\theta + 2ghv^2\cos^2\theta}

\end{align}

We then isolate the square root and square both sides to eliminate it and consolidate common terms.

\begin{align}

dg - v^2\sin\theta\cos\theta &= \sqrt{v^4\sin^2\theta\cos^2\theta + 2ghv^2\cos^2\theta}\cr

d^2g^2& - 2dgv^2\sin\theta\cos\theta + v^4\sin^2\theta\cos^2\theta\cr

&= v^4\sin^2\theta\cos^2\theta + 2ghv^2\cos^2\theta\cr

d^2g^2 - 2dgv^2\sin\theta\cos\theta &= 2ghv^2\cos^2\theta\cr

d^2g^2 &= 2ghv^2\cos^2\theta + 2dgv^2\sin\theta\cos\theta

\end{align}

We continue to eliminate like terms, extract the velocity component, and re-balance.

\begin{align}

d^2g &= 2hv^2\cos^2\theta + 2dv^2\sin\theta\cos\theta\cr

d^2g &= v^2\left(2h\cos^2\theta + 2d\cos\theta\sin\theta\right)\cr

v^2 &= \frac{d^2g}{2h\cos^2\theta + 2d\cos\theta\sin\theta}

\end{align}

Using trig identities, we can simplify the equation and keep like terms.

\begin{align}

v^2 &= \frac{d^2g}{2h\cos^2\theta + d\sin2\theta}\cr

v^2 &= \frac{d^2g}{h\cos2\theta + h + d\sin2\theta}

\end{align}

We are pretty much done here. We just need to take the square root and integrate it into code.

$$ v = \sqrt{\frac{d^2g}{h\cos2\theta + h + d\sin2\theta}} $$

Where:

\begin{align}

g &= 9.81 \text{(or whatever your gravity is)}\cr

h &= y - y\prime\cr

d &= x\prime - x\cr

&\arctan(\tfrac{h}{d})<\theta<\frac{pi}{2}

\end{align}

The code itself is pretty straightforward. Below is an example function that I wrote to handle doing the mathematics of finding the velocity.

```
// This function determines the required velocity to reach the range at the given height and angle
private float DoTheMath(float distance, float height, float angle)
{
// Doubled values to make things easier
float doubleDistance = 2f * distance;
float doubleAngle = 2f * angle;
// The lowest angle is a direct shot at an infinite velocity
float lowestAngle = Mathf.Atan2(height, distance) * 2;
// If the angle doesn't fall within the (lowestPossible, 90) range, there is no solution
if (angle >= Mathf.PI || angle <= -lowestAngle) {
return 0;
}
// I figured this equation out after working through the standard physics equations.
// See: http://plantingcode.net/finding-initial-velocity-given-angle-and-distance/
return Mathf.Sqrt((9.81f * doubleDistance) / (height * Mathf.Cos(doubleAngle) + height + distance * Mathf.Sin(doubleAngle)));
}
```

]]>The Unity documentation it indicates that all public variables are made available in the inspector for direct editing. While this is handy, it is also dangerous. This article will cover a few things regarding public variables, and how to avoid them in Unity.

In a earlier post I

]]>The Unity documentation it indicates that all public variables are made available in the inspector for direct editing. While this is handy, it is also dangerous. This article will cover a few things regarding public variables, and how to avoid them in Unity.

In a earlier post I made mention of public variables, specifically in a class-based architecture. One of the dangers of public variables is that *anything* can change their value. When testing Napkin Western (working title) on a tablet, some of the variables were corrupted from the values set in the Inspector. The values changed from 6 and 15 to 2.435e-43 and 2.643e-45 respectively.

What's the solution? Simple, set the access to all your variables, functions, enums, etc. to exactly what they should be. Make only variables public that absolutely need to be. Then take advantage of the `[HideInInspector]`

to keep certain public variables hidden, and`[SerializeField]`

to show hidden or private variables. This way things won't get accidentally modified, and you will have access to all the pieces you need while retaining the proper level of access.

Long compile times are a real chore when it comes to testing things. It is especially cumbersome when all you are doing is making small edits resulting in 2 seconds worth of editing, and 2 minutes waiting for compiling.

One place where this is particularly the case is shader

]]>Long compile times are a real chore when it comes to testing things. It is especially cumbersome when all you are doing is making small edits resulting in 2 seconds worth of editing, and 2 minutes waiting for compiling.

One place where this is particularly the case is shader debugging. This is the actual problem that prompted me to find such a solution. Being a Unity project for mobile devices, Napkin Western must be tested on its target platform, from time to time. In this particular instance, my nifty hand-crafted shader specifically took issue with the mobile device for no apparent reason. Since compiling for the platform takes a fair amount of time, and all I needed to do was make minor changes to find the issue, I had to come up with another solution.

The solution? Make 6 different versions of the shader; yes, 6. Each version had one thing to test within its code. That way I could independently verify each of 6 different components to see if any of them were the cause of the problem without having to compile the game 6 times. Then I loaded in some spheres and gave each one a different version of the shader.

So, what ended up being the problem with my awesome custom toon/cel shader? Oddly enough, nothing you would expect. It ended up being the fact that I tried to condense my code by using a ternary instead of an expanded if/else statement. I never caught this because it worked fine during the standard visual tests yet, for some odd reason, when testing on the various available Android devices, it resulted in an all black shader effectively always evaluating the ternary to false.

]]>To expand on my post about enumerations I'm going to look at Finite State Machines in a relatively general sense. Let's start with breaking down what exactly a Finite State Machine is. We can look at the descriptive words to see that it is a machine,

]]>To expand on my post about enumerations I'm going to look at Finite State Machines in a relatively general sense. Let's start with breaking down what exactly a Finite State Machine is. We can look at the descriptive words to see that it is a machine, or system, that consists of a finite number of states. Great, but what does that *mean*? In a sense it is a way to package your code so only the desired pieces run at the desired time, this makes them very useful for succinct organization. In the rest of the article we'll look at different ways to implement the system, as well as the pros and cons of each.

The first thing to look at is how to define the states within the machine. Many coders will jump to strings as they allow infinite descriptive variation for the states. Another option is to use numbers to label the states. The real question is, why not take advantage of both? I strongly recommend using `enums`

for states whenever possible, they give you the descriptiveness of strings while retaining the efficiency of numbers. Since enums are technically numbers you can increment (`++`

) and decrement (`--`

) them, but refer to them by a text definition.

There are also a few different ways to actually make a state machine. A state machine usually will reside within the main loops of an object, or its update function if it has one. Popular ways to do a state machine include either a `switch`

statement, or `if, else`

tree:

```
public void Update()
{
switch (state) {
case State.state1:
// TODO
break;
case State.state2:
// TODO
break;
default:
// etc.
}
if (state == State.state1) {
// TODO
} else if (state == State.state2) {
// TODO
} else {
// etc.
}
}
```

Here is where I disagree. Instead of a `switch`

or `if, else`

tree I think that it is important to keep the states as separate `if`

statements. This way when your logic changes the state, you can compute the next state right away instead of waiting for the next update. Sometimes you may want to wait for the next update for some particular reason, but typically this is not necessary. While this only works for states going up the tree in progression, you can very easily structure your program as it is below thereby making sure all logic is complete before continuing.

```
public void Update()
{
bool done = true;
do {
if (state == State.state1) {
done = DoState1();
}
if (state == State.state2) {
done = DoState2();
}
if (state == State.state3) {
done = DoState3();
}
// etc.
} while(!done);
}
```

You may have noticed that I am calling functions for each state. I firmly believe in having a modular approach to one's code. It's better to break it off into a function and end up only having one place calling it, then to have to restructure it into a function later. It's also a lot easier to take advantage of `return`

to only use as much of the code as you need. With the functional approach you can also call the logic of an earlier state in a later state if you happen to switch states, or need to correct any missing data. Enclosing your state machine within a `while`

block is really not necessary, but it can allow you to have less frequent update functions and not waste an update cycle on a change.

In a nutshell this is what makes a FSM (everything has an acronym). Your game, or object, works on a series of states thereby limiting the code needed to run. States help keep things well organized and can even prevent erroneous errors bleeding in from rogue code by limiting exposure. Later I will get into the importance of Classes and Object/Aspect oriented programming (OOP / AOP) and how important organization and convention is.

]]>Fans of Doctor Who will probably shun me for that titling. What are enumerators, or, more specifically, `enums`

? To put it succinctly, enums are words that are actually numbers. What does this mean? It means that when you write your code you can check for words, but when it gets

Fans of Doctor Who will probably shun me for that titling. What are enumerators, or, more specifically, `enums`

? To put it succinctly, enums are words that are actually numbers. What does this mean? It means that when you write your code you can check for words, but when it gets compiled the compiler takes those words and replaces them with numbers. You may wonder why to bother with such a thing. It's pretty simple really. Enums allow you to have readable code while keeping a small overhead. They are better than character strings because they are smaller, and they are better than just plain integers because they can be rearranged, and are much more readable. Below is an example enum use:

```
enum Skills = {
Heal,
Harm,
Strengthen,
Weaken,
BuffArmor,
CorrodeArmor,
EnhanceAccuracy,
DegradeAccuracy,
PushPull
}
public void ApplySkill(Skills skillType, float amount)
{
switch (skillType) {
case Skills.Heal:
health += amount;
break;
case Skills.Harm:
health -= amount;
break;
.
.
.
}
}
```

You could just use integers, but it would be hard to keep track of which number represented what over a larger code-base. And while you could use strings, capitalization is not your friend, not only that, but professionally enums are the accepted solution as it will reduce the memory footprint and compiled file size.

]]>I would like to take this post to explain why using C# in Unity is a better idea than Javascript. If you end up not needing multiple returns for functions, non-type-specific logic, or are okay with the wonky auto-completion for Javascript, then that is okay. On the other hand, if

]]>I would like to take this post to explain why using C# in Unity is a better idea than Javascript. If you end up not needing multiple returns for functions, non-type-specific logic, or are okay with the wonky auto-completion for Javascript, then that is okay. On the other hand, if you want to take advantage of those features, and more read on.

C# and Javascript are different, but similar. If you are coming from a C++ background (like myself), then you may find C# more familiar to begin with. Below is a quick list of what I will be covering that makes C# more friendly.

- Strict typing
- Parameters as reference (a.k.a. multiple function returns)
- Generic Functions (a.k.a. type independent logic)
- Multidimensional Arrays
- Full access to C# features*
- Auto-completion
- Unity is built with it

*Some newer features of C# are not supported because Unity compiles the code itself

First we will cover C# strict typing requirement. You may be wondering why having to declare access level and type for everything is a good thing. Not only will you need to do it when coding professionally for a back-end, but explicitly declaring types has two major benefits. The first is that it will always every be one thing, and so you can't accidentally shoot yourself in the foot at runtime. Secondly, having an explicit type will help to reduce memory costs. This is because the type is known and does not need to fluctuate.

There are two ways to pass parameters to a function by reference in C#. These are `ref`

and `out`

. The main difference between `ref`

and `out`

is that `out`

does not need to be declared before it is passed to the function. In either case, when a function modifies a value that is passed in by reference, that change persists outside the function. This lets one function "return" multiple values while keeping the return open for other indications.

Generic functions are awesome, if you have ever been in a situation where you are copy pasting code, but only changing the calling script, then generic functions are for you. They take the form of `public void Foo<T>(T param)`

and can include the statement `where T : BaseClass`

before the opening braces to limit what types are allowed. MSDN has some good documentation on what makes generics awesome. Then, since you know the shared base class contains the function definition, you can call the function once with the referenced script instead of having to copy paste your logic tree and change up who calls it. Remember, if you are copy pasting in code, then chances are you can do it a better way.

Another really big thing that C# has over Javascript in Unity is multidimensional arrays. Or, more simply, arrays of arrays. This is incredibly useful for any number of reasons, 2D, 3D and 4D grids for example. Depending on your game you may not need it, but having it can certainly be helpful.

Unity makes Javascript support a number of handy features such as true Object Oriented Programming and polymorphism. These and other handy features are natively supported in C#. For a complete breakdown of C#, I strongly suggest looking at the MSDN documentation.

You may think that auto-completion within MonoDevelop is rather trivial. I did too until it started getting in the way of my coding. One perfect example is `for (var i : int = 0; i < something; i++)`

. What's wrong with that? Start typing it in Javascript, and this will happen: `for (var int = 0; int <`

right there it autocompleted `i`

to `int`

. When this happens enough, it becomes very very frustrating. There are a number of other cases where this happens, or some variables just aren't indexed, but so far in C# I haven't run into these problems.

Finally, Unity was built in C#. This means that C# code will integrate natively. While the Javascript is compiled resulting in very little to no difference in terms of cost, C# has just given me the better treatment all around. Then again I'm coming from a C++ background, so your experiences may differ.

]]>There are a few things that you will want to keep in mind when working with touch in Unity. Mobile devices pass click events with their touch events, platform dependent compilation, rotations are a special type all their own, sometimes Unity hands back one thing when you need another, collisions

]]>There are a few things that you will want to keep in mind when working with touch in Unity. Mobile devices pass click events with their touch events, platform dependent compilation, rotations are a special type all their own, sometimes Unity hands back one thing when you need another, collisions are odd, and much more. This is the first of many posts on the quirks of Unity.

If you are planning to support multiple platforms, I highly recommend taking advantage of platform dependent compilation. This will help to avoid several conflicts, and will cut back on stacked code considerably.

The reason for the push is that all *tested* mobile devices will pass a **click event alongside a touch event**. What does this mean? Well, it means that if you have just single click input, you don't actually have to code in a touch handler. This is

A future post will provide the basic methods for handling touch input by the user and making it able to share a handling function with the mouse.

]]>