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

# #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}).$$

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

# #33: Random Arithmetic Problems

posted on 2018-01-31

### Part 1

Write a function random-expression which generates a random math expression built up by numbers, +, unary/binary -, *, /, ^, and sqrt. There should be two outputs: (1) the generated expression in unevaluated form, and (2) the evaluated answer. Decide on and explain your choice of arguments to random-expression to bound the size of the expression.

Bonus: Write this in both a dynamically typed language and a strictly typed language.

### Part 2

Extend evaluate-expression to take into account a variable called operator-table which contains the operators used in random generation and their arities. For example, the default table might look like this in Common Lisp:

(defvar *operator-table*
'((+    2)
(-    1 2)    ; unary and binary -
(*    2)
(/    2)
(expt 2)
(sqrt 1)))

Feel free to add information to the table as you see fit.

# #32: Promises from Scratch

posted on 2018-01-31

In the first challenge, we created a syntactic primitive called a thunk to construct delayed computations, which could later be run by simply calling them.

However, there is a slight problem. Suppose we make the following thunk:

(define x (thunk (display "Hello!") (+ 1 1)))

Then when we run the thunk by doing (x) in Scheme or (funcall x) in Common Lisp, it will print "Hello!" and compute 2 on each invocation. In Common Lisp notation:

(defvar *thunk*
(thunk
(format t "Hello!")
(+ 1 1)))

(funcall *thunk*)
; Prints: Hello!
; Returns: 2

(funcall *thunk*)
; Prints: Hello!
; Returns: 2

This may not be desirable if we want to simulate things such as call-by-need evaluation semantics.

In this exercise, create two abstractions, delay and force to ameliorate this issue. The delay abstraction should be similar to thunk in that it creates a delayed computation using lambda. We call the result of delay a promise.

The abstraction force is responsible now for actually evaluating the promise and producing an answer. However, using force a second time will give back a cached result.

Here's an example in Common Lisp notation:

(defvar *promise*
(delay
(format t "Hello!")
(+ 1 1)))

(force *promise*)
; Prints: Hello!
; Returns: 2

(force *promise*)
; Does not print.
; Returns: 2

# #31: Aperiodic Tiling

posted on 2018-01-30

Wang tiles are a collection of oriented squares with colored edges such that when you place the squares side-by-side with matching colors, the plane will tile aperiodically. That is to say, without rotating or reflecting the tiles, when placed according to the color matching rule, repetitions of tiles cannot occur within contiguous sections of the plane, as soon as the sections are large enough.

Wang tiles are specified by listing their colors starting with the top edge and going clockwise. One set of Wang tiles consists of 13 tiles using 4 colors. The tiles are listed below.

Wang Tiles
----------
RRRG
BRBG          Example Tile: RGBW
RGGG
WBRB                 Red
BBWB                +----+
WWRW                |    | Green
RGBW          White |    |
BWBR                +----+
BRWR                 Blue
GGBR
RWRG

### Part 1

Write a program that generates a random $M\times N$ rectangle of Wang tiles.

### Part 2

Suppose the centers of the squares are placed in the plane at integer lattice points. Then we can identify each square in the plane by its center.

Write a function (spiral n) which gives the $n$th coordinate of a spiral starting at $(0, 0)$ to $(1, 0)$ and proceeding counterclockwise. The first few values are:

0 => (0, 0)    3 => (0, 1)     6 => (-1, -1)
1 => (1, 0)    4 => (-1, 1)    7 => (0, -1)
2 => (1, 1)    5 => (-1, 0)    8 => (1, -1)

With this, write a function (wang-spiral n) which produces a Wang tiling valid on the coordinates (spiral 0) to (spiral (- n 1)).

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

# #29: Multiplying Long-Hand

posted on 2018-01-30

Modern CPUs only support multiplying integers of a fixed size, which is usually 32- or 64-bits.

In grade school, most of us learned how to multiply numbers long-hand; we write the two numbers down, one above the other, and proceed to do the multiplication. It often looks like so:


123
x 45
----
615
+ 492
------
5535

If you've forgotten this method for multiplying, you might consult a children's arithmetic book.

The goal of this exercise is to implement the long multiplication algorithm. While not required, it is certainly convenient if your language supports arbitrary precision integers out of the box.

### Part 1

As testing utilities, write two functions:

• (digits n) which takes a non-negative integer and produces a list of base-10 digits from least to most significant. For example, (digits 123) shall return (3 2 1). Decide on what (digits 0) should be.

• (undigits dlist) which does the opposite: takes a list of digits and produces a non-negative integer.

• Is any list of digits a valid representation of a non-negative integer?

• What is the precise relationship between digits and undigits?

### Part 2

Implement the long multiplication algorithm as a function long-multiply which takes two lists of base-10 numbers and produces a list representing the product.

### Part 3

Modify long-multiply to print out what the process might look like with pencil and paper. For example:

(display-long-multiply '(3 2 1) '(5 4))

; Outputs:
;
;    123
;   x 45
;   ----
;    615
; + 492
; ------
;   5535

### Part 4

If you implemented the previous parts successfully, you may not have done so with absolute mathematical correctness. Without loss of generality, suppose we are multiplying two $N$-digit numbers. Then, in the second step of the algorithm, we will produce the $N$ terms that we need to add up. When we perform the addition in each column, each of which consist of at most $N$ base-10 digits, our sum will likely exceed our digit size.

1. What is the maximum size of a number we could sum to in a column?

2. What is an example of two numbers whose multiplication process leads to that sum?

3. If we are truly constrained on a computer where every storable register, be it in the processor or RAM, is limited to holding a digit between 0 and 9, how can we modify the algorithm to accommodate?

Finally, perform the modifications to the algorithm.

# #28: QUOBOSORT

posted on 2018-01-30

You happen upon the following note, which seems to describe a novel algorithm for sorting.

QUOBOSORT: a sort made by ROBERT SMITH aka STYLEWARNING

Patents Pending.

SUMMARY
-------

Permute X until the minimum is in the first position of X. When this
occurs, QUOBOSORT the rest of X until we reach an empty listte.

ALGORITHM
---------

QUOBOSORT(X) :=
-- INPUT: a list of integers X
-- OUTPUT: sorted X in ascending order

Q0. Is X an empty list?
Yes: Return X.
No : Go to Q1.
Q1. Find the minimum M of X.
Q2. Randomly permute X.
Q3. Is M in the first position of X?
Yes: Concatenate M and QUOBOSORT(REST(X))
No : Go to Q2.

Implement this algorithm.

Extra Credit: Analyse the time and memory complexity of this algorithm.

# #27: Function Exponentiation

posted on 2018-01-30

### Part 1

Given any $f:X\to X$ and any non-negative integer $n$, define the function

​ $$\mathtt{fexpt}(f, n) := \underbrace{f\circ \cdots \circ f}_{n\text{ times}}.$$

Implement fexpt without mutation (i.e., without imperative loops or set!).

Extra Credit: Try to optimize the runtime of the functions resulting from fexpt.

### Part 2

The Babylonian method for computing square roots of positive numbers is as follows. To compute $\sqrt{X}$, start with an arbitrary positive number $x_0$. Define $x_n$ by the following recursive sequence:

​ $$x_{n+1} = \frac{1}{2}\left(x_n + \frac{x_n}{X}\right).$$

Then it can be proved that $\lim_{n\to\infty} x_n = \sqrt{X}$, and the sequence converges quadratically (the number of correct digits doubles with each iteration).

Implement this using fexpt.

# #26: Finding the Identity Matrix

posted on 2018-01-30

### Part 1

Given an $m \times n$ matrix of zeros and ones, write a function largest-identity that finds the size of the largest sub-matrix that is an identity matrix.

### Part 2

Write a version of largest-identity that allows for arbitrary row swaps.

# #25: Merging Lists

posted on 2018-01-30

### Part 1

Write a function merge-2 which takes two sorted lists and merges them into sorted order. This is an essential step of the merge sort algorithm.

### Part 2

Write a function like merge-2 that instead takes any number of sorted sequences.

### Part 3

Write these functions to work on infinite streams.

# #24: Run-Length Encoding

posted on 2018-01-30

### Part 1

Write a function rle :: [Integer] -> [(Integer, Integer)] to compute the run-length encoding of a list of integers. The result is a list of (<item>, <run-length>) pairs. Here are some test cases.

(rle '())                  ; => ()
(rle '(1))                 ; => ((1 1))
(rle '(1 1 1 2 2 3 2 3 3)) ; => ((1 3) (2 2) (3 1) (2 1) (3 2))

Try using your language's fold function and/or write in a functional fashion.

### Part 2

Run-length encoding can be applied to infinite streams as well, producing run-length encoded output. However, the function would never terminate if we were, say, given an infinite stream of 1's. As such, we might want to bound the size of the output run-lengths.

Write a function rle' whose type, written in Standard ML notation, is

(int option) * (int stream) -> (int, int) stream.

The first argument is an option type, which will be None if we should allow unbounded run-lengths, and Some n which bounds the run-lengths to at most n, a positive integer. Here are some test cases in Haskell:

take 1 $rle' None (repeat 1) -- never terminates rle' None <finite list> -- equal to: rle <finite-list> take 2$ rle' None [1, 1, 1, 2, 2, ...]     -- [(1, 3), (2, 2)]

# #3: Friendlier letrec

posted on 2018-01-30

Write with-definitions, a version of letrec which allows one to use define-like syntax in Scheme. For instance, I should be able to do:

(define (example x)
(with-definitions
((define (is-even? x) (zero? (remainder x 2)))
(define rofl "rolling on the floor laughing"))
(if (is-even? x)
(display rofl)
(display ":("))))

It's a little baroque and definitely not "minimal", but neither is being able to do

(define (f x) ...)

when you could also do  (define f (lambda (x) ...)) 

# #2: Conditional Mutation

posted on 2018-01-30

Create a procedure called set-if! such that

(set-if! <predicate> <symbol> <value>)

means that <symbol> is not set to <value> if <predicate> is not true.

1. Why can't this be a function in most languages?

2. What are the subtlties of the semantics of this? What behavior is not defined by the above?

# #1: Delayed Evaluation

posted on 2018-01-30

Define a macro thunk which will wrap the body of the macro inside a lambda. That is, define

(thunk
<body>)

so that we get

(lambda () <body>)

This can act as a primitive for delaying evaluation.

Update: See Challenge #32 for an extension of this challenge.

This blog covers math, challenge

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