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

$\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.

#36: Falling Leaves

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.

#35: All CARs and CDRs

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.

#34: All Manner of Brackets

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.

This blog covers math, challenge

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