posted on 20180320
Recall that the symbol $\mathbb{Z}^2$ denotes the set of all coordinate pairs with integer components.
A spiral of length $n\ge 1$ is a counterclockwise spiral starting at $(0,0)$ extending to the right to $(n,0)$, wrapping around so as to cover $\mathbb{Z}^2$ completely.
Consider the following spiral of length $2$.
******
 
* **** *
  (0,0)  
* * x*x *
  (2,0) 
* *****

****** ...
The points of the spiral have a natural ordering. The above spiral can be written as a sequence $s$ where $$ \begin{align} s_0 &= (0,0), & s_3 &= (2,1),\\ s_1 &= (1,0), & s_4 &= (1,1),\\ s_2 &= (2,0), & s_5 &= (0,1), \end{align} $$ and so on.
There are three challenges. Given an $n\ge 1$, do the following.
Given a $k\ge 0$, find $s_k$.
Given a point $(\alpha, \beta)\in\mathbb{Z}^2$, find the $k$ such that $s_k = (\alpha,\beta)$.
Print the spiral of length $2$ to the terminal by printing the values of $k$ in their correct positions. (And make it look nice by ensuring the numbers are aligned and reasonably spaced out.)
posted on 20180210
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 se\Vert_1 := \sum_{i=1}^n\vert s_ie_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} $$
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 se\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 $n1$ 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 bottomleft element of each matrix is identified by $(1,1)$ and topright 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.
posted on 20180130
In Challenge #15, we wrote a few simple combinators. Here we write a few more.
In addition to combinator practice, this exercise will be written so as to practice math notation comprehension.
For each of these, implement the combinator and write the most general type for that combinator.
Combinator $C_1$ which "flips" the arguments of binary function. It takes $f : X\times Y\to Z$ to $C_1 f = f' : Y \times X \to Z$ such that for all $x\in X$ and $y \in Y$, $$f(x,y) = f'(y,x).$$ This combinator is an involution because $C_1^2$ is the identity.
Combinator $C_2$ which duplicates an argument to a binary function. It takes $f : X\times X\to Z$ to $C_2 g = f' : X \to Z$ such that for all $x\in X$, $$f(x,x) = f(x).$$
Combinator $C_3$ which takes two functions with the same domain $X$, and produces a function taking $x\in X$ and returning $(f(x), g(x))$.
Combinator $C_4$ which takes a function, and produces a curried function of two arguments, such that the second argument supplied is effectively ignored.
Fun Fact: In Haskell, the combinators above are called flip
, join
,
liftM2 (,)
, and (const .)
respectively.