Merge pull request #7151 from jo-37/contrib

Solutions to challenge 192

5 files changed, 375 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
diff --git a/challenge-192/jo-37/perl/ch-1.pl b/challenge-192/jo-37/perl/ch-1.pl
new file mode 100755
index 0000000000..826eff4f07
--- /dev/null
+++ b/challenge-192/jo-37/perl/ch-1.pl
@@ -0,0 +1,83 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0;
+use experimental 'signatures';
+
+our ($tests, $examples);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [--] [N]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+N
+    integer to be bit-flipped in decimal, hexadecimal, octal or binary
+    notation
+
+EOS
+
+
+### Input and Output
+
+# Interpret or numify the input string
+say flip_bits(/^0/ ? oct : 0 + $_) for shift;
+
+
+### Implementation
+
+# Extending the task to any integer.  Negative values work out-of-the
+# box, but zero needs a closer examination.  As zero has no bit set, it
+# has no significant bit.  To be able to flip one single zero-bit, we
+# need this single bit to be regarded significant. 
+
+sub flip_bits ($n) {
+    # Get the bit left of the highest significant bit from a copy of $n.
+    # This value minus one masks all relevant bits.
+    # Edge cases:
+    # - 0b0 and 0b1 both lead to $l = 0b10 and a mask of 0b1.
+    # - If the bit in $l gets shifted out, $l becomes zero and the
+    #   mask -1, i.e. all bits set.
+    my ($c, $l) = ($n, 2);
+    $l <<= 1 while $c >>= 1;
+
+    # Flip bits and mask the significant bits.
+    ~$n & ($l - 1);
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is flip_bits(5), 2, 'Example 1';
+        is flip_bits(4), 3, 'Example 2';
+        is flip_bits(6), 1, 'Example 3';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        is flip_bits(0), 1, 'out of scope: 0';
+        is flip_bits(-1), 0, 'out of scope: -1';
+        is flip_bits(-2), 1, 'out of scope -2';
+        is flip_bits(0x8000), 0x7fff, 'flip 16 bits';
+        is flip_bits(85), 42, 'The universal question';
+        {
+            no warnings 'portable';
+            is flip_bits(0x8000000000000000), 0x7fffffffffffffff,
+            'flip 64 bits';
+        }
+	}
+
+    done_testing;
+    exit;
+}
diff --git a/challenge-192/jo-37/perl/ch-2.pl b/challenge-192/jo-37/perl/ch-2.pl
new file mode 100755
index 0000000000..7739cca720
--- /dev/null
+++ b/challenge-192/jo-37/perl/ch-2.pl
@@ -0,0 +1,67 @@
+#!/usr/bin/perl -s
+
+use v5.16;
+use Test2::V0;
+use List::Util qw(reduce reductions);
+
+our ($tests, $examples, $verbose);
+
+run_tests() if $tests || $examples;	# does not return
+
+die <<EOS unless @ARGV;
+usage: $0 [-examples] [-tests] [N...]
+
+-examples
+    run the examples from the challenge
+ 
+-tests
+    run some tests
+
+N...
+    non-negative integers
+
+EOS
+
+
+### Input and Output
+
+say num_moves(@ARGV);
+
+
+### Implementation
+
+# See the blog
+# https://github.com/jo-37/perlweeklychallenge-club/blob/master/challenge-192/jo-37/blog.pdf
+# for a derivation of the formula behind this implementation.
+
+sub num_moves {
+    my @cum = reductions {$a + $b} @_;
+    return -1 if $cum[-1] % @_;
+    my ($eq, $step) = (0, $cum[-1] / @_);
+
+    reduce {$a + abs($b - ($eq += $step))} 0, @cum;
+}
+
+
+### Examples and tests
+
+sub run_tests {
+    SKIP: {
+        skip "examples" unless $examples;
+
+        is num_moves(1, 0, 5), 4, 'Example 1';
+        is num_moves(0, 2, 0), -1, 'Example 2';
+        is num_moves(0, 3, 0), 2, 'Example 3';
+    }
+
+    SKIP: {
+        skip "tests" unless $tests;
+
+        is num_moves(1, 2, 3, 4, 5, 6, 7), 28, 'counted by hand';
+        is num_moves(5, 5, 5, 5, 5), 0, 'equilibrium';
+        is num_moves(5, 0, 0, 0, 0), 10, '4 + 3 + 2 + 1';
+	}
+
+    done_testing;
+    exit;
+}