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

Extra Credit

Draw your artwork.

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

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.

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

Furthermore, answer the following questions:

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.

Answer these questions:

What is the maximum size of a number we could sum to in a column?
What is an example of two numbers whose multiplication process leads to that sum?
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)]
take 3 $ rle' (Some 2) [1, 1, 1, 2, 2, ...] -- [(1, 2), (1, 1), (2, 2)]
rle' (Some n) (repeat x)                    -- equal to: repeat (x, n)

#23: Computing Tangent

posted on 2018-01-30

The tangent of a number $\tan x$ is defined as $\sin x/\cos x$. We can compute tangent by using this definition, or we can make use of a so-called addition formula. The addition formula for tangent is

$$\tan (a + b) = \frac{\tan a + \tan b}{1 - \tan a \tan b}.$$

If we wish to compute $\tan x$, then we can compute $\tan(x/2 + x/2)$:

$$\tan(\tfrac{x}{2} + \tfrac{x}{2}) = \frac{\tan\tfrac{x}{2} + \tan\tfrac{x}{2}}{1-(\tan\tfrac{x}{2})(\tan\tfrac{x}{2})}=\frac{2\tan\tfrac{x}{2}}{1-(\tan\tfrac{x}{2})^2}$$

We also know something about tangent when the argument is small, namely that tangent is almost linear: $\tan x\approx x$

Part 1

Write a recursive function tangent using the methods above to compute the tangent of a number. It is not necessary to handle undefined cases (odd multiples of $\pi/2$).

Part 2

Write an iterative version of tangent called tangent-iter which avoids tree recursion (i.e., doesn't consume any stack space due to recursion).

Test Cases

Test your code by comparing against your language's built in tangent function. Note that your results may not match precisely, due to the linear approximation ($\tan x \approx x$) and due to other floating point issues.

#22: Curried Application

posted on 2018-01-30

Write a function (@ f x y z …) which applies f to x, and then applies the result of that to y, and so on. For example, clog satisfies the following functional relation: (@ clog 2 5) == ((clog 2) 5). More generally, we have the functional relations:

$(@\, f) = f$
$(@\, f\, x_1 \ldots x_n) = ((@\,f\,x_1 \ldots x_{n-1})\, x_n)$

#21: Defining Curried Functions

posted on 2018-01-30

Part 1

Write define-curried which defines a curried function. That is,

(define-curried-function (clog b x)
  (/ (log x) (log b)))

will define clog so that it's equivalent to:

(lambda (b)
  (lambda (x)
    (/ (log x) (log b))))

Part 2

Note: This is difficult or impossible to write in full generality in some languages.

Write a combinator called $\mathrm{curry}_n\,f$ which takes a function $f$ of $n\ge 1$ arguments, and produces a fully curried version of $f$. (If you can compute $n$ from $f$, when you may elide $n$ as an argument.) It should satisfy the following equations:

$\mathrm{curry}_1\,f = f$ for unary $f$, and
$\mathrm{curry}_n\,f = x_1\mapsto\mathrm{curry}_{n-1}\big( (x_2, \ldots x_n)\mapsto f(x_1,\ldots, x_n)\big)$ for $n$-ary $f$.

#20: Uninitialized Locals

posted on 2018-01-30

Write a macro locals which acts sort of like let, but allows uninitialized values. (If your language doesn't support uninitialized variables, then you can bind them to your false value, like #f in Scheme.) For example:

(locals (a b (c 1) d)
  (set! a 5)
  (+ a c))

==> 6

#19: Multi-Function Application, Curried

posted on 2018-01-30

Write a unary function appList* which satisfies the following equation:

(appList L x) == ((appList* L) x)

The function appList* is said to be a curried version of appList.

#18: Multi-Function Application

posted on 2018-01-30

Given a list of $n$ unary functions $L:=(f_1, f_2,\ldots,f_n)$, write a function (appList L x) that returns $(f_1(x), f_2(x), \ldots, f_n(x))$. For example:

(appList (list sin cos tan) 3.14)
;; ==> (0.00159265291648683 -0.99999873172754 -0.00159265493640722)

#17: Square and Diagonal Matrices

posted on 2018-01-30

Write functions square-matrix? and diagonal-matrix? to determine if a matrix is square (same number of rows and columns), or if a matrix is diagonal (the only non-zero entries are those on the diagonal).

#16: Matrix Transpose

posted on 2018-01-30

Suppose a matrix is represented as a list of equally sized lists representing the rows. Write a function to transpose a matrix in this representation. Transposition is a process where every row becomes a column, and every column becomes a row.

#15: Simple Combinators

posted on 2018-01-30

Part 1

Implement the following combinators, high-order functions that are usually composed together. (Here we specify the type signatures in Haskell-like notation.)

(constantly x), a function which takes an argument x and produces a unary function which always returns x.
Using constantly, implement yes which always returns a true value, and no which always returns a false value.
(complement f), a function which takes a function returning a Boolean, and produces another function which does the same but with the Boolean inverted.
(conjunction f g) which returns a function which takes an argument and returns true iff both f and g are satisfied by x.
(disjunction f g) which is like conjunction but checks iff either f or g are satisfied by the input.

One should note the similarity between these functions and some of the basic unary and binary Boolean predicates.

Part 2

Write out the type signature of each of the above functions.

Part 3

Implement Fizz Buzz using these combinators.

#14: Shunting Yard

posted on 2018-01-30

Read about and implement the shunting-yard algorithm.

#13: Simple `destructuring-bind`

posted on 2018-01-30

In Common Lisp, there's a macro called destructuring-bind which allows you to "take apart" a list and bind the parts to variables. It's a primitive form of pattern matching for lists.

Implement a basic version that allows the following to work:

(define lst '(1 2 3))
(define cns '(1 . 2))

(destructuring-bind (a b c) lst
  (+ a b c))                    ; ==> 6

(destructuring-bind (a . b) cns
  (+ a b))                      ; ==> 3

(destructuring-bind (a . b) lst
  (map (lambda (x) (+ a x)) b)) ; ==> (3 4)

#12: Intraword Scramble

posted on 2018-01-30

Wirte a fincuton wcihh teaks a snetnece as a srintg and sberalmcs the mlddie lretets of each word, keiepng the first and last ltretes of each word itnact. You can asmuse "ieadl" ipunt: no pntitcoauun, no nbuemrs, etc.

#11: C-style Loops

posted on 2018-01-30

Part 1

Implement a C-style for-loop without using another explicit imperative looping construct.

(for ((<var> <init>) <condition> <post-loop-thing>)
  <body>)

For example:

 (for ((i 0) (< i 10) (set! i (+ 1 i)))
  (display i)
  (newline))

which would print 0 through 9. Unlike C, i's scope is limited.

Part 2

Now extend for so you can do (for (<var> in <list>) …) to iterate over lists. This is (almost) equivalent to Common Lisp's dolist macro.

Part 3

Generalize the results of Part 2 so that the user can "program" the for-loop with iteration semantics of any data type. As an example of what this may mean, though you might do it differently, is to have a table of predicates, like so in Common Lisp:

(defvar *for-loop-extensions*
         ; predicate    ???
        '((listp        ???)
          (vectorp      ???)
          ...))

;; for-loop should now work with at least
;; lists and vectors.
(for (i in #(1 2 3))
  (print i))

I've put ??? so as to not spoil what they could be.

#10: Using Degrees

posted on 2018-01-30

For better or for worse, some disciplines use degrees as a measure of angle. Write a macro with-degrees which causes the trigonometric functions sin, cos, and tan to use degrees and not radians within the lexical scope of with-degrees. For example,

(with-degrees
  (+ (sin 30) (sin 90)))

should return 1.5.

Note: This is much less straightforward in Common Lisp than it is in Scheme due to Common Lisp's packaging rules.

#9: Cleaner `define*`

posted on 2018-01-30

In challenge #8, you wrote a define macro called define*. However, this can be awkward and even inefficient when we have a cond or a case. Consider:

(define* (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Each time we compute a yet-uncomputed Fibonacci number, we have to check if it's 0 first, then 1, then we can proceed to compute.

In this challenge, we want to be allowed to define constant cases which add to the memoization table immediately. Let's call this definition procedure def. The syntax looks as follows:

(def fib
  (0) => 0
  (1) => 1
  (n) => (+ (fib (- n 1))
            (fib (- n 2))))

This will create a function fib which will have the results of (fib 0) and (fib 1) memoized, and allow for the general case. When we do call the general case for an unmemoized function, we no longer have to crawl the cond, because there is none. So we save comparisons each time it's called.

For multi-argument functions, it would be illegal to have clauses like (4 b c) => .... You can safely assume the last case will be the variable case.

#8: Memoized `define`

posted on 2018-01-30

Write a macro define* that looks like define but memoizes results, i.e., it'll save the value of the result so next time around, it just looks up the result.

Follow Up: Discuss some of the subtle decisions one has to make in writing define*.

Extra Credit: Do it without namespace pollution (except for the defined function name of course).

#7: Lisp's `setq`

posted on 2018-01-30

In Common Lisp, setq takes any number of argument pairs. For example,

(setq x 1 y 2 z 3)

will set the value of x to 1, y to 2, and z to 3. Implement this in Scheme.

Follow Up: Discuss which behavior was not defined in the above example, and what choices you made to define them.

#6: Bogosort

posted on 2018-01-30

Implement Bogosort. Bogosort is a sorting algorithm defined as so:

INPUT x: a finite sequence of numbers
OUTPUT: the input sequence in ascending order

Step 1. If x is in ascending order, return x.
Step 2. Shuffle the elements of x uniformly randomly. Go to Step 1.

#5: Standard ML's `ref`

posted on 2018-01-30

In Standard ML and similar languages, one is not able to mutate the bindings to values. It is not possible to do something like x = 1 followed by x = 2. Instead, a special purpose cell is allocated, called a ref, whose contents can be modified. In Standard ML, ref is defined by the following signature:

signature REF =
  sig
    type 'a ref

    (* create a ref containing a value*)
    val ref : 'a -> 'a ref

    (* retrieve the contents of this value *)
    val op ! : 'a ref -> 'a

    (* Change the value of the ref *)
    val op := : 'a ref * 'a -> unit
  end

Implement ref. In Scheme, the behavior of ref might be like so:

; create a
(define a (ref 9))
(set-ref! a 8)
(deref a) ; ==> 8

#4: Partitions of an Integer

posted on 2018-01-30

Similar in spirit to the counting change problem from SICP, write a function to compute the partitions of an integer. A partition of a non-negative integer $N$ is a non-increasing sequence of positive integers less than or equal to $N$ that they sum to $N$.

All of the partitions of $4$ are $(4)$, $(3, 1)$, $(2, 2)$, $(2, 1, 1)$, and $(1, 1, 1, 1)$.

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

Follow up questions:

Why can't this be a function in most languages?
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.

Introducing Watrophy

posted on 2018-01-29

For almost as long as I can remember, I've frequented sprawling online communities of programmers in order to learn more about the craft of writing code. This has given me the opportunity to meet many folks of many backgrounds, with the common thread that we (usually!) like to create software.

I've been particularly grateful for the fact that some of these individuals found me to be helpful in their pursuit to learn programming languages and the techniques they often come with. Around 10 years ago, I frequently mentored on Scheme and Standard ML, focusing on techniques from functional programming and meta-programming. Almost always, the techniques are more valuable than the languages themselves, since they pay dividends. One way to learn is through practice, and so I frequently posed small exercises to teach a concept.

With the help of @qu1j0t3, I've managed to unearth some of the exercises I wrote dating back almost a decade, which have been remastered and posted here.

This website is a log of challenges—old and new—to strengthen your programming muscle. If you're a programmer by occupation, maybe you say wat a lot at your ordinary stock of languages, projects, frameworks, and tools. Or maybe you're just bored. If you're a hobbyist, maybe you don't find a lot of practical material on these subjects without getting lost in the depths of academia. Whatever the reason you program, I think these exercises may be sufficiently interesting, short, and insightful.

These exercises differ from a few other kinds of exercises.

They're a little more difficult than the average set of "koans".
They're a little more biased toward statically and dynamically typed functional programming.
They're not as mathematically oriented as Project Euler.
They're usually not optimized for competitive programming, like TopCoder or HackerRank.
They have nothing to do with code golf, unless you want them to.

While there is currently no implemented ranking system, it wouldn't matter anyway, since good solutions typically characterized by their aesthetic and technique, not run time or memory consumption.

I hope to update this at least once a week. Feel free to subscribe to any of the following feeds:

RSS and Atom feeds for any and all posts.
RSS and Atom feeds of challenges only.

This blog covers math, challenge

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

Content from 2018-01

Part 1

Part 2

Part 1

Part 2

Extra Credit

Part 1

Part 2

Part 3

Part 4

Part 1

Part 2

Part 1

Part 2

Part 1

Part 2

Part 3

Part 1

Part 2

Part 1

Part 2

Test Cases

Part 1

Part 2

Part 1

Part 2

Part 3

Part 1

Part 2

Part 3