Watrophy: code challenges by Robert Smith

Written on 2018-02-10

Prerequisites

The symbol $\mathbb{Z}^n$ denotes the set of all coordinate $n$-tuples with integer components. These are one kind of $n$-dimensional lattice.

Given two points $s=(s_1,\ldots, s_n)$ and $e=(e_1, \ldots, e_n)$, their taxicab distance is $$\Vert s-e\Vert_1 := \sum_{i=1}^n\vert s_i-e_i\vert.$$

Given a complex number $z$, we denote its normalization as $$\operatorname{N}(z) := \begin{cases} 0 & \text{if }z=0,\\ z/\vert z\vert & \text{otherwise.} \end{cases} $$

Challenge

A staircase path between two points, informally, is any path by going only right or up.

Formally, given the starting point $s \in\mathbb{Z}^n$ and ending point $e \in\mathbb{Z}^n$ with $s\leq e$ (i.e., each component of $s$ is less than or equal to each corresponding component of $e$), a staircase path is a sequence of $\ell:=1+\Vert s-e\Vert_1$ coordinates $\sigma_0,\ldots,\sigma_{\ell}$ with the following facts:

$\sigma_0 = s$,
$s\leq \sigma_k \leq e$ (in the sense described above), and
exactly one component of $\sigma_{k+1} - \sigma_k$ is $1$, with the other $n-1$ components equal to $0$.

Denote the set of all staircase paths from $s$ to $e$ as $\{s\to e\}$.

Part 1: Verify that facts 1–3 imply $\sigma_{\ell} = e$.

Next, consider the set $\mathbb{T}^{m\times n}$ defined as $n\times m$ matrices whose entries are complex numbers of unit modulus. For consistency with the above, let's suppose the bottom-left element of each matrix is identified by $(1,1)$ and top-right element is $(n, m)$.

Part 2: Implement the function $$f : \mathbb{T}^{m\times n}\to \mathbb{T}\cup\{0\}$$ defined by $$f(M) := \operatorname{N}\left(\sum_{\Sigma\in\{(1,1)\to(m,n)\}}\prod_{(x,y)\in\Sigma} M_{x,y}\right).$$

Extra Credit: Generalize $f$ to work on a tensor of any order.

#37: Staircase Paths

Prerequisites

Challenge