Add blog

3 files changed, 225 insertions, 0 deletions

diff --git a/challenge-192/jo-37/blog.txt b/challenge-192/jo-37/blog.txt
new file mode 100644
index 0000000000..46b76605fb
--- /dev/null
+++ b/challenge-192/jo-37/blog.txt
@@ -0,0 +1 @@
+https://github.com/jo-37/perlweeklychallenge-club/blob/master/challenge-192/jo-37/ch-2.pdf
diff --git a/challenge-192/jo-37/ch-2.pdf b/challenge-192/jo-37/ch-2.pdf
new file mode 100644
index 0000000000..301eec4bb4
--- /dev/null
+++ b/challenge-192/jo-37/ch-2.pdf
diff --git a/challenge-192/jo-37/ch-2.tex b/challenge-192/jo-37/ch-2.tex
new file mode 100644
index 0000000000..41d5bc7f7e
--- /dev/null
+++ b/challenge-192/jo-37/ch-2.tex
@@ -0,0 +1,224 @@
+\documentclass{article}
+%\usepackage[paperwidth=8.5in,paperheight=39in]{geometry}
+\pagestyle{empty}
+\setlength{\parindent}{0pt}
+\setlength{\parskip}{1ex}
+\begin{document}
+\part*{The Counter to Equilibrium}
+\section*{Task 2: Equal Distribution}
+\textbf{Submitted by:} Mohammad S Anwar
+
+You are given a list of integers greater than or equal to zero, $@list$.
+
+Write a script to distribute the number so that each members are same.
+If you succeed then print the total moves otherwise print $-1$.
+
+Please follow the rules (as suggested by Niels 'PerlBoy' van Dijke) 
+\begin{itemize}{}{}
+\item You can only move a value of $1$ per move
+\item You are only allowed to move a value of $1$ to a direct
+  neighbor/adjacent cell 
+\end{itemize}
+
+\subsubsection*{Example 1}
+Input: $@list = (1, 0, 5)$ \\
+Output: $4$
+
+Move \#1: $(1, 1, 4)$ \\
+(2nd cell gets $1$ from the 3rd cell) \\
+Move \#2: $(1, 2, 3)$ \\
+(2nd cell gets $1$ from the 3rd cell) \\
+Move \#3: $(2, 1, 3)$ \\
+(1st cell gets $1$ from the 2nd cell) \\
+Move \#4: $(2, 2, 2)$ \\
+(2nd cell gets $1$ from the 3rd cell)
+
+\subsubsection*{Example 2}
+Input: $@list = (0, 2, 0)$\\
+Output: $-1$
+
+It is not possible to make each same.
+
+\subsubsection*{Example 3}
+Input: $@list = (0, 3, 0)$\\
+Output: $2$
+
+Move \#1: $(1, 2, 0)$ \\
+(1st cell gets $1$ from the 2nd cell) \\
+Move \#2: $(1, 1, 1)$ \\
+(3rd cell gets $1$ from the 2nd cell)
+
+\section*{Definitions}
+A \textit{move}, i.e. the transfer of a unit from one element to one
+of its immediate neighbors will be called \textit{shift left} or
+\textit{shift right} in the following.
+
+Given a distribution $(a_1,\ldots, a_n)$, we define the
+\textit{cumulative distribution}
+\begin{displaymath}
+  (s_1,\ldots,s_n) := (a_1, a_1 + a_2,\ldots,a_1 +\ldots+ a_n) =
+  \left(\sum_{i=1}^k a_i \right)_{k=1}^n
+\end{displaymath}
+
+\section*{Properties}
+\subsection*{Moves}
+Consider an element $a_i > 0$.
+
+We can perform a \textit{shift left} from position $i$ to $i - 1$ if
+$i > 1$: 
+\begin{displaymath}
+  a_k' = \left\{
+    \begin{array}{ll}
+      a_k + 1 & \textrm{if } k = i - 1 \\
+      a_k - 1 & \textrm{if } k = i \\
+      a_k & \textrm{otherwise}
+    \end{array}
+  \right.
+\end{displaymath}
+In terms of $s$:
+\begin{displaymath}
+  s_k' = \left\{
+    \begin{array}{ll}
+      s_k + 1 & \textrm{if } k = i - 1 \\
+      s_k & \textrm{otherwise}
+    \end{array}
+  \right.
+\end{displaymath}
+We can perform a \textit{shift right} from positon $i$ to $i + 1$ if
+$i < n$: 
+\begin{displaymath}
+  a_k' = \left\{
+      \begin{array}{ll}
+        a_k - 1 & \textrm{if } k = i \\
+        a_k + 1 & \textrm{if } k = i + 1 \\
+        a_k & \textrm{otherwise}
+      \end{array}
+    \right.
+\end{displaymath}
+In terms of $s$:
+\begin{displaymath}
+  s_k' = \left\{
+    \begin{array}{ll}
+      s_k - 1 & \textrm{if } k = i \\
+      s_k & \textrm{otherwise}
+    \end{array}
+  \right.
+\end{displaymath}
+
+\subsection*{Effects}
+Now we know exactly how a single move affects the cumulative
+distribution: 
+\begin{itemize}{}{}
+\item A \textit{shift left} increments the cumulative distribution at
+  the target position by one.
+\item A \textit{shift right} decrements the cumulative distribution at
+  the source position by one.
+\item All other values of the cumulative distribution remain unchanged.
+\end{itemize}
+
+\section*{Disequilibrium}
+
+There exists an equilibrium distribution if and only if
+\begin{displaymath}
+  s_n \bmod n = 0  
+\end{displaymath}
+Let's assume there is an equilibrium distribution for the given
+numbers.
+Then there is a \textit{cumulative equilibrium distribution}
+\begin{displaymath}
+  (e_1,\ldots,e_n) := (s_n / n, 2 s_n / n,\ldots,s_n)
+  = \left(k s_n / n\right)_{k=1}^n
+\end{displaymath}
+Note that $e_n = s_n$ and $e_i < e_{i+1}$ for $i = 1,\ldots,n-1$.
+
+Considering the cumulative distribution:
+\begin{enumerate}
+\item 
+Suppose there is an $i$ with $s_i > e_i$.
+Then $i < n$ because $s_n = e_n$.
+If $a_i > 0$ then a \textit{shift right} from position $i$ to $i + 1$
+decrements $s_i$ by one.
+Otherwise (if $a_i = 0$), $s_{i - 1} = s_i > e_i > e_{i - 1}$ and we
+may repeat the consideration at $i - 1$.
+At least one of $a_1,\ldots,a_i$ must be non-zero because otherwise
+$s_i > e_i$ cannot hold. 
+
+\textbf{Decrementing:} \\
+If there is an $i$ with $s_i > e_i$, then there is a $j$ with
+$1 \leq j \leq i$, $a_j > 0$ and $s_i = s_j > e_j$.
+With a \textit{shift right} from position $j$ to $j + 1$, $s_j$ can be
+decremented by one.
+
+\textbf{Example:}
+\begin{eqnarray*}
+  a & = & (2, 7, 0, 0, 1) \\
+  s & = & (2, 9, 9, 9, 10) \\
+  e & = & (2, 4, 6, 8, 10)
+\end{eqnarray*}
+Select $i = 4$: $s_4 = 9 > 8$ but $a_4 = 0$.
+Looking left, we arrive at $j = 2$ having $s_2 = 9 > 4$ and $a_2 > 0$
+where we can perform a \textit{shift right} from position $2$ to $3$
+resulting in
+\begin{eqnarray*}
+  a' & = & (2, 6, 1, 0, 1) \\
+  s' & = & (2, 8, 9, 9, 10)  
+\end{eqnarray*}
+
+\item
+Suppose there is an $i$ with $s_i < e_i$.
+
+Then $i < n$ because $s_n = e_n$.
+If $a_{i + 1} > 0$ then a shift left from position $i + 1$ to $i$
+increments $s_i$ by one. 
+Otherwise (if $a_{i + 1} = 0$), $s_i = s_{i + 1} < e_i < e_{i + 1}$
+and we may repeat the consideration at $i + 1$.
+At least one of $a_{i + 1},\ldots,a_n$ must be non-zero because
+otherwise $s_i < e_i$ cannot hold.
+
+\textbf{Incrementing:} \\
+If there is an $i$ with $s_i < e_i$, then there is a $j$ with
+$i \leq j < n$, $a_{j + 1} > 0$ and $s_i = s_j < e_j$.
+With a \textit{shift left} from position $j + 1$ to $j$, $s_j$ can be
+incremented by one.
+
+\textbf{Example:}
+\begin{eqnarray*}
+  a & = & (1, 0, 0, 7, 2) \\
+  s & = & (1, 1, 1, 8, 10) \\
+  e & = & (2, 4, 6, 8, 10)
+\end{eqnarray*}
+Select $i = 1$: $s_1 = 1 < 2$ but $a_2 = 0$
+Looking right, we arrive at $j = 3$ having $s_3 = 1 < 6$ and $a_4 > 0$
+where we can perform a \textit{shift left} from position $4$ to $3$
+resulting in
+\begin{eqnarray*}
+  a' & = & (1, 0, 1, 6, 2) \\
+  s' & = & (1, 1, 2, 8, 10)  
+\end{eqnarray*}
+\end{enumerate}
+
+\subsection*{Existence}
+From the previous section we already know that a single move
+increments or decrements exactly one element of the cumulative
+distribution by one. 
+
+Now we have shown that in a distribution deviating from the
+cumulative equilibrium distribution, there always exists a legal
+move that reduces the overall deviation. 
+
+\section*{Solution}
+We have shown that for every deviation from the equilibrium
+distribution there is a move that reduces the difference between the
+cumulative distribution and the cumulative equilibrium distribution by
+one.
+The number of moves to achieve the equilibrium distribution is
+therefore the sum of the absolute differences between the cumulative
+distribution and the cumulative equilibrium distribution:
+\begin{displaymath}
+  m = \sum_{i=1}^n |s_i - e_i|
+\end{displaymath}
+This is a nice result for mathematicians: It gives the required number
+of moves without actually providing them.
+(However, from the above discussion it becomes clear that any legal
+move reducing the overall deviation may be chosen at any time.)
+\end{document}
\ No newline at end of file