posted on 2018-02-10

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}
$$

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.

posted on 2018-02-08

Imagine you have a $k$-ary rooted tree $T$ defined by the following diagram:

```
[ A ]
[ / \ ]
[ B C ]
T := [ / \ / \ ].
[ D E F G ]
[ / \ \ ]
[ H I J ]
```

The leaves of $T$ are $$\operatorname{leaves}(T) := \{\mathtt{H}, \mathtt{I}, \mathtt{E}, \mathtt{J}, \mathtt{G}\}.$$ Imagine the leaves fall off though an operation called $\operatorname{fall}$ so that $\operatorname{fall}(T)$ is

```
[ A ]
[ / \ ]
fall(T) = [ B C ].
[ / / ]
[ D F ]
```

After another iteration, we get $\operatorname{fall}^2(T)$, which is

```
[ A ]
fall²(T) = [ / \ ].
[ B C ]
```

And $\operatorname{fall}^3(T) = \mathtt{A}$, the root.

Write a function which takes *any* $k$-ary rooted tree $T$ and prints
out the sequence
$$\ell_i(T) := \big(\operatorname{leaves}\circ\operatorname{fall}^i\big)(T)$$
for $0\leq i \leq n$ where $n$ is defined such that
$\operatorname{fall}^n(T)$ is the root of $T$. (Since it is a
sequence, it should be printed in order.)

For the example above, in somewhat abbreviated notation, we have $$\ell(T) := (\mathtt{HIEJG}, \mathtt{DF}, \mathtt{BC}, \mathtt{A}).$$

*Thanks to Steven Heidel for
telling me about this wonderful problem.*

posted on 2018-02-06

Most Lisps have combinations of `car`

and `cdr`

built in, usually up
to four levels deep, e.g., `caaddr`

and `cdaddr`

are built-ins
referring to

`(`*lambda* (x) (car (car (cdr (cdr x)))))
; and
(*lambda* (x) (cdr (car (cdr (cdr x)))))

respectively. Implement a macro `(generate-cxr n)`

which generates the
definitions of all `car`

/`cdr`

combinations up to `n`

times.

If your language doesn't support macros or dynamic definitions, write
a function of the same name which produces a list of all `car`

/`cdr`

combinations as anonymous functions.

**Extra Credit**: Implement this as efficiently as possible, using the
least amount of space.

posted on 2018-02-06

We all know the problem of checking/counting parentheses pairs. This time, given a list of open and close characters which must match each other, check if the expression is valid. For example, consider the following pairs:

```
(defparameter *open-close-pairs*
'((#\( . #\))
(#\[ . #\])
(#\{ . #\})
(#\< . #\>)))
```

Write a function `validate`

which takes a string like `"({<>[()]}[])"`

and a table of open-close pairs and return a Boolean indicating the
validity of the string.