May 28th, 2015
The web comic XKCD recently published the following tournament bracket featuring match-ups like
ORSON WELLS vs. H.G. WELLS and
VAN HALEN vs. VAN MORRISON vs. VAN WILDER.
So, who won? It seems probable to me that XKCD’s author Randall Munroe has in mind some way to decide these matches. If he published how the matches were to be decided, I missed it. However, based on some previous XKCD comics like Geohashing and Externalities, I think it’s a safe guess that it involves hashing.
So, how could we decide this? We could take the hash of each name and then in each match, the largest hash value wins. That, however, has the unfortunate side effect that the winner of the tournament would be the same regardless of the organization of the brackets.
I opted to decide the match between
OSCAR DE LA RENTA and
OSCAR DE LA HOYA by taking the SHA3-512 hash of the strings
OSCAR DE LA RENTA vs. OSCAR DE LA HOYA and
OSCAR DE LA HOYA vs. OSCAR DE LA RENTA. The winner is the one whose name appeared first in the string with the smallest hash value. For three and four person contests, I used all permutations of the players involved (separated by
The winner? RYAN ADAMS beat out BILL PAXTON in the final.
The code for this project was a breeze thanks to
#'ALEXANDRIA:MAP-PERMUTATIONS and my
TRACK-BEST library. Here is a the meat of the whole thing which uses an evaluation function (here, it’s SHA3-512 of the
vs. separated player list) and a way to compare the evaluations (here, a simple
#'ARRAY-LESSP) and runs through all of the players.
(labels ((rank-one-match (players depth)
(track-best:track (first players)
(funcall eval-permutation players depth)))
(find-winner (players depth)
(track-best:with-track-best (:order-by-fn compare-permutations)
(alexandria:map-permutations (lambda (players)
(rank-one-match players depth))
Here is the full source file for the tournament: tourney.lisp. Here is a text description of the whole tournament. And, here is a graphic with the outcomes of all of the matches.
I updated my track-best library to allow you to keep all of the the things tied for best. The
WITH-TRACK-BEST macro now accepts the
:KEEP-TIES keyword parameter.
Here are some examples of using the
:KEEP-TIES option. For all of the examples, we will use the same sequence of
(defun track-numbers ()
(track :one 1)
(track :uno 1)
(track :two 2)
(track :dos 2)
Here are some calls with
NIL (the default):
(with-track-best (:keep 1 :keep-ties nil) (track-numbers))
=> (values :TWO 2)
(with-track-best (:keep 3 :keep-ties nil) (track-numbers))
=> (values (:TWO :DOS :ONE) (2 2 1))
Here are some calls with
(with-track-best (:keep 1 :keep-ties t) (track-numbers))
=> (values (:TWO :DOS) (2 2))
(with-track-best (:keep 3 :keep-ties t) (track-numbers))
=> (values (:TWO :DOS :ONE :UNO) (2 2 1 1))
In doing a problem set from the Internet a few weeks ago, I found myself writing awkward constructions with
LOOP to try to find the best one (or two or three) things in a big bag of things based on various criteria: similarity to English, hamming distance from their neighbor, etc.
I wrote a macro that encapsulated the pattern. I’ve reworked that macro into a library for public use.
There are a variety of examples in the README and the tests directory.
Here is one example to pique your interest. Suppose you have some data about the elevations of various cities in various states and you (being a Moxy Fruvous fan) want to know
What Is the Lowest Highest Point? Here’s how you might tackle that with the
(let ((data '(("Alabama" ("Birmingham" 664)
("Alaska" ("Anchorage" 144)
("Arizona" ("Grand Canyon" 6606)
(with-track-best (:order-by-fn #'<)
(dolist (state-info data)
(multiple-value-bind (city altitude)
(dolist (city-info (rest state-info))
(track (first city-info) (second city-info))))
(track (list (first state-info) city) altitude)))))
With this limited dataset, the end result would be
(VALUES '("Alaska" "Fairbanks") 531). The inner
WITH-TRACK-BEST finds the highest city in each state. The outer
WITH-TRACK-BEST finds the lowest of these.