#38: Spirals

posted on 2018-03-20

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 counter-clockwise 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.

1. Given a $k\ge 0$, find $s_k$.

2. Given a point $(\alpha, \beta)\in\mathbb{Z}^2$, find the $k$ such that $s_k = (\alpha,\beta)$.

3. 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.)

#37: Staircase Paths

posted 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:

1. $\sigma_0 = s$,

2. $s\leq \sigma_k \leq e$ (in the sense described above), and

3. 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.

#30: Combinator Practice

posted on 2018-01-30

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.

1. 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.

2. 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).$$

3. 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))$.

4. 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.

This blog covers math, challenge

View content from 2018-01, 2018-02, 2018-03