Solution to SKI Trees

Author: Chieu Nguyen

This puzzle consists of 11 binary-branching trees, each with a list of names marked as S, K, or I. For each one, the names are those of ski trails from a particular ski resort in North America, and the tree can be superimposed on the official trail map of that resort such that every path from root to terminal corresponds to a skiable path in the resort. There are the same number of terminal points in the tree as given ski trail names, and each terminal point lies on a unique ski trail in the set.

The trees are actually representations of expressions in the SKI combinator calculus, where each terminal node represents one of the basic combinators S, K, or I, and each nonterminal node represents the functional application of the left child expression to the right child expression.

Each expression reduces to a Church numeral, which is either I (representing 1) or the result of applying a successor function S(S(KS)K) to I repeatedly. Each application increases the value by 1.

One can figure out which Church numeral is represented by reducing the SKI expression (applying the definitions of the three basic combinators to subtrees repeatedly) and counting how many times the successor function appears, adding that to 1. The value can also be computed by applying the SKI expression to a natural number successor function (one that adds 1 to its argument and returns the result), and applying the result of that to 0: this should yield the natural number corresponding to the Church numeral. Alternatively, the SKI expression can be applied to an arbitrary function X and an arbitrary function Y: the number of X's in the result is the integer.

The following table lists the SKI expressions represented by each tree, in Lisp-style notation because that (and Unlambda notation) is easily transcribable from the tree and easily embedded in code.

ResortLongitudeSKI expressionNumberIndexed letter
Canyons111.55° W((s (((i (i s)) (k s)) k)) ((s (((i s) (k s)) k)) i))3N
Okemo72.72° W((s ((s (k s)) k)) ((s ((s (k s)) (i k))) ((((k k) i) i) (i i))))3E
Panorama116.24° W(((i s) (((i s) (k s)) k)) (((i s) ((s (k s)) k)) ((s ((s (k s)) k)) i)))4O
Steamboat106.81° W(((s i) (i i)) ((s ((s (k s)) k)) ((k (i (i (i (i i))))) (s (k i)))))4A
Sugarloaf70.31° W((s ((s (k s)) k)) (((s i) i) ((s ((s (k (i s))) (i k))) (i i))))5R
Sun Valley114.36° W((((s i) ((i k) ((i s) (i ((s (k s)) k))))) (i i)) (i i))2U
Telluride107.85° W((((s ((i i) (i (k s)))) k) ((s ((s (k s)) (i (i (i k))))) (k i))) i)1T
Tremblant74.59° W(((s ((s (k s)) k)) ((s ((s (k s)) k)) i)) ((s ((s (k s)) k)) i))8N
Vail106.38° W((s ((s (k s)) k)) (((k i) i) (i (i (i ((s (i ((s (k s)) k))) i))))))3I
Waterville Valley71.53° W(((s i) (k (((i s) ((s (k s)) k)) i))) (((i s) i) i))4E
Whistler Blackcomb122.95° W(((s ((((k s) k) i) i)) (i i)) ((i (i i)) ((((k s) i) ((s (k s)) k)) i)))16M

Use the number as an index into the short name of the ski resort. Since the resorts are given in alphabetical order by their name, the indexed letters must be reordered. Arrange the letters by the physical location of the ski resort, and reading from west to east, they spell out the answer MOUNTAINEER.

This file is a solution in Scheme that interprets SKI calculus in terms of lambda calculus. It also embeds the SKI expressions of the trees and prints out the numbers represented.

Of course, there is no need to resort to lambdas if your language already has SKI combinators built in. Here is another solution in Unlambda, an esoteric programming language based on the SKI calculus. Each SKI expression is directly embedded and applied to a function that prints out an asterisk.