Code mini-golf

Here are some simple puzzles to exercise your brain.

1. Write partial-apply-left, a function that takes a binary function and the left input of the binary function and returns the unary function that takes the right input and then applies the binary function to both inputs.

For example:

  ;; Define *foo* as a procedure that conses 'a onto its argument.
  > (defvar *foo* (partial-apply-left #'cons 'a))

  > (funcall *foo* 'b)
  (A . B)

  > (funcall *foo* 42)
  (A . 42)

2. Write distribute, a function that takes a binary function, a left input, and a list of right inputs, and returns a list of the results of applying the binary function to the left input and each of the right inputs. (Hint: Use partial-apply-left)

For example:

  > (distribute #'cons 'a '( (b c d) e 42))
  ((A B C D) (A . E) (A . 42))

3. Write removals, a function that takes a list and returns a list of lists, where each sublist is the original list with exactly one element removed.

For example:

  > (removals '(a b c))
  ((B C) (A C) (A B))

Hint:

• One removal is the CDR of the list.
• Other removals can be constructed by (distributed) consing the CAR onto the removals of the CDR.

4. Write power-set, a function that takes a list and returns the power set of that list (the set of all subsets of the original list).

For example:

  > (power-set '(a b c))
  (() (C) (B) (B C) (A) (A C) (A B) (A B C))

Hint:

Note how the power set of a list can be constructed from the power set of its CDR by adding the CAR to each subset in the power set of the CDR.

5. Write power-set-gray that returns the subsets sorted so each subset differs from the previous subset by a change of one element (i.e., each subset is equal to the next subset with either one element added or one element removed). This is called a Gray code ordering of the subsets.

For example:

  > (power-set-gray '(a b c))
  (() (C) (B C) (B) (A B) (A B C) (A C) (A))

Hint:

When appending the two halves of the power set, reverse the order of the second half.

Puzzle: Read Preserving Comments

Here is a little Lisp puzzle for you:

I want to read a Lisp file and produce a list of the top-level forms in the file, but I want to preserve comments. Any comment that appears on a line within a top-level form should be associated with that form. Comments that appear by themselves at top level should be associated with the following top-level form. For example, if the file contains:

;;; -*- Lisp -*-

;; This file is a test
  
(in-package "CL-USER")

;; This is the test function:
(defun foo (arg)
  ;; This function does nothing
  (declare (ignore arg))
  nil)    ;; Return nil

(defparameter *x* 42)
(defparameter *y* 99)  ;; This is y

;; The BAR function doesn't do anything either

(defun bar ()  
  nil)

;; Trailing comment in file.

Then I want to produce the following list:

'(";;; -*- Lisp -*-

;; This file is a test
  
(in-package \"CL-USER\")
"
 "
;; This is the test function:
(defun foo (arg)
  ;; This function does nothing
  (declare (ignore arg))
  nil)    ;; Return nil
"
 "
(defparameter *x* 42)
"
 "(defparameter *y* 99)  ;; This is y
"
 "
;; The BAR function doesn't do anything either

(defun bar ()  
  nil)
"
 "
;; Trailing comment in file.
")

This puzzle is not difficult, but it is tricky to get the edge cases right.

Out of Practice List-fu

How is your list-fu? Mine gets rusty when I don’t manipulate lists for a while. Here are some simple puzzles to get the rust out.

1. Write a function that takes a list of items and maps a function over the pairs of items in the list, in the following way: The first argument to the function is taken from one of the elements in the list. The second argument is taken from one of the subsequent elements in the list. E.g., if the list is (a b c d), then

(map-pairs (lambda (x y) ‘(F ,x ,y)) ’(a b c d))

((F A B) (F A C) (F A D) (F B C) (F B D) (F C D))

2. Write a function revmap that is like mapcar, but the result is in reverse order.

3. Write a function map-cons that takes a car and a list of cdrs, and returns a list of the car consed on each of the cdrs.

4. Write a function revmappend that is like alexandria:mappend but is more efficient because it doesn’t try to preserve the order of the elements.

5. Write a function remove-one-element that takes a list of n elements and returns n lists of n-1 elements, where each sublist has one element removed from the original list.