Some AI Product Ideas

In no particular order:

Podcast AI that skips ads

Podcast AI that edits the hosts repetitive monologues down to a fucking question (on interview podcasts)

Podcast AI that notices when they’re doing a “live” episode and fixes the inevitably shitty audio

Transportation AI that lives on phone and monitors your travel speeds, elevation changes, weather, how many other passengers you usually travel with (Bluetooth?), current vehicle costs including repairs and insurance, and recommends eg “sell your 2018 Jeep and buy a 2012 Corolla”

(or even “sell your 2012 Corolla and buy an e-bike and rent a truck as needed once every 3 months” etc)

Why I don’t use emacs package.el

There was a discussion over at Reddit (link below) where someone was sharing that they couldn’t get things working due to dependency hell so they just used VS Code instead.

In response i wrote the following:

[–]lovela47 1 point 7 minutes ago

I ran into this exact problem. I got constantly broken by package developers changing APIs and dependencies willy-nilly and things not working. People in “the ecosystem” seem to think users (even technical) have hours to spend filing bug reports on API breakage etc. Sorry, no thanks. Hours of back-and-forth and often the result will be something like “it’s not my fault it’s package X’s fault, just upgrade”.

Even though I dislike it and am complaining, I believe it’s actually fine. People are providing really cool stuff for free after all (eg magit). But it still became not worth it for me personally to deal with the whole package.el lifestyle. And I suspect there are many other stories like yours where people just got tired of chasing breakage and moved on.

FWIW my solution has been to vendor all Elisp packages (and their dependencies) I depend on in git repos that I control. Upgrades are rarely performed unless something really good happens that’s worth upgrading for. In many cases the library updates are not really worth it anyway e.g. “lib X needs to use f.el now” ok fine? but as a user that buys me nothing tbh

As a result of vendoring libs i’ve had literally years of stability. For example, I’m running magit v2.8.0-something and it already does everything I need, so why upgrade?

Package ecosystem folk are unlikely to want to hear this but, the juice from getting onto package.el and friends kinda isn’t worth the squeeze IMO. I’m sure everyone has good intentions, but in the limit all it takes is one git push that breaks you, and you’re sitting there with a broken system when you need to get your job done.

Fundamentally the “upgrade libraries over the network at text editor startup and pray someone somewhere did the MxN integration testing for free” approach is not something I can rely on for real work

Reddit discussion: https://old.reddit.com/r/emacs/comments/yxragm/for_whose_use_emacs_and_vs_code_when_and_why_you/

Don’t break APIs

Been using emacs long enough I guess it’s my turn to write “hey why are you breaking decades old APIs fucknuts” to emacs-devel

Shoutout to the absolute legend IMAP guy

https://web.archive.org/web/20161010002312/http://compgroups.net/comp.emacs/line-move-visual/274792

I mean, it’s pretty uncool by today’s standards of conduct, but can relate strongly to the “you’re breaking my shit and I’m real mad about it” vibe he’s putting out there

Sadly it seems the “well you should have read the changelog” nerds have won the day and now every software product is like this: an endless treadmill of upgrades that usually don’t provide huge (or any) benefits but still require you to pay attention to them and apply some workaround to get back (if you’re lucky) to where you already were.

On the design of CLI tools on unix

I just posted the following comment on some other website:


My greatest wish is that CLI tools on Unix would return 0 on success and remain silent by default unless a verbose flag is passed or an error occurs, so they could be properly scripted.

So many tools fail in this regard and assume I want to have a colorful, Unicode-laden interactive “experience” in my terminal. No thanks. If I will use the tool more than say 3 times I want to automate it away so I can move on to something more interesting

See also: Style section of McIlroys intro the Unix docs: http://danluu.com/mcilroy-unix/

How to make Word Ladders using graph search

Introduction

Word ladders are lists of words where each word is the same as the preceding word except that one letter differs. They were invented and popularized by Lewis Carroll, who called them “word links” or “doublets” [Knuth1993]. For example, here is a word ladder:

words woods woons toons trons trone trope grope grape graph

In this post we will learn how to make word ladders using a computer program. Specifically, we will learn the method for doing this as it is described in Knuth’s book The Stanford GraphBase. At a high level, the method is as follows:

  1. Read in a file of words, all of which have the same length (in this case we will use 5-letter words).
  2. Construct a graph from the words, where each vertex in the graph represents a word, and that vertex’s neighbors are each words that differ from the current vertex’s word by one letter.
  3. Assign edge weights to the graph such that you can use the weights to find the shortest path between two vertices. (The weight assignments given by Knuth to his wordlist are based on his assessment of how common the words are, but in our case we will use a different wordlist, to which we will assign arbitrary weights based on a “checksum” of the characters in each word for expedience.)
  4. Find the shortest path (by weight), and print out all of the words associated with the vertices along that path.
  5. Congratulations, you have made a word ladder!

Here is a very small example of the type of graph we are discussing:

A word ladder graph

Description

First things first. We need a file of words. Let’s use the word list from the popular game Wordle. We can download a copy from Github here. Save it to a file called words. We will write a short Perl program to find our word ladder. To build the graph in our program, we will use the Graph module from CPAN. It has a lot of functionality, including an implementation of Dijkstra’s algorithm that we’ll use to extract the ladders.

my $g     = Graph::Undirected->new;
my @words = slurp('words');

Next, we slurp in the list of words and sort them based on their “weights” (really, a “checksum” which is just the sum of chr() values). See the chksum() subroutine below for the details. This sorting step is necessary to help us later. Later on, we will use this sorted order, since it will mean we don’t need to check every word against every other word; we only need to check a word W against all of the previous words W-1, W-2, …, W-n. How do we know which words are “previous”? Because we did the sorting step.

my %chksum;
for my $word (@words) {
    $chksum{$word} = chksum($word);
}
@words = sort { $chksum{$a} <=> $chksum{$b} } @words;

In this section, we generate the hash tables that will be used later on to determine if two words are “adjacent” to one another in the graph. The question of adjacency we’re using here is: are they the same except for one letter? For example, “grape” and “graph” are adjacent, while “plane” and “plows” are not.

my %words;
for my $word (@words) {
    $g->add_vertex($word);
    my @word = split //, $word;
    for (my $i = 0; $i < @word; $i++) {
        my $c = $word[$i];
        $word[$i] = '_';
        my $variant = join '', @word;
        push @{$words{$variant}}, $word;
        $word[$i] = $c;
    }
}

Now that we have tables storing all of the “holey variants” of each word, we iterate over the table keys. For each key, we add edges between all of the values associated with that key. This should work because the data structure looks something like:

{
      "_ords" => ["words", "cords", ...],
      ...,
}

We also weight the edges using an arbitrary scheme whereby for each pair of vertices (UV) we generate a “checksum” for each vertex’s word, and set the edge weight to the difference between the larger and smaller checksums.

my $edge_count = 0;
for my $k (keys %words) {
    my $vertices = $words{$k};
    for (my $i = 0; $i < @$vertices; $i++) {
        for (my $j = 0; $j < $i; $j++) {
            my $u     = $vertices->[$i];
            my $v     = $vertices->[$j];
            my $v_sum = $chksum{$v};
            my $u_sum = $chksum{$u};
            my $weight
              = $v_sum > $u_sum ? $v_sum - $u_sum : $u_sum - $v_sum;
            $g->add_weighted_edge($u, $v, $weight);
            $edge_count++;
        }
    }
}

Now that the graph is built and populated, we can start operating on it. We will now look for a path from a starting word to some other word by traversing a “word ladder”, which in graph terms means we will find the shortest path (based on the “checksums” calculated above) using Dijkstra’s algorithm.

my $start = 'words';
my $end   = 'graph';

say qq{Looking for a path between '$start' and '$end'};
my @path = $g->SP_Dijkstra($start, $end);

say qq{PATH: };
say for @path;

Using the Wordle word list results in a graph with 12947 vertices and 46098 edges. This means running the program takes about 10-15 seconds on my aging, $400 Windows laptop. It will likely be much faster on your machine.

$ perl word_ladders words 
Looking for a path between 'words' and 'graph'
PATH: 
words
woods
woons
toons
trons
trone
trope
grope
grape
graph

Implementation

What follows is a full implementation of the code described above.

#!perl

use strict;
use warnings;
use autodie;
use feature qw/ say /;
use Graph;

sub main {

    my $g     = Graph::Undirected->new;
    my @words = slurp('words');
    my %chksum;

    for my $word (@words) {
        $chksum{$word} = chksum($word);
    }

    @words = sort { $chksum{$a} <=> $chksum{$b} } @words;
    my %words;

    for my $word (@words) {
        $g->add_vertex($word);
        my @word = split //, $word;
        for (my $i = 0; $i < @word; $i++) {
            my $c = $word[$i];
            $word[$i] = '_';
            my $variant = join '', @word;
            push @{$words{$variant}}, $word;
            $word[$i] = $c;
        }
    }

    my $edge_count = 0;

    for my $k (keys %words) {
        my $vertices = $words{$k};
        for (my $i = 0; $i < @$vertices; $i++) {
            for (my $j = 0; $j < $i; $j++) {
                my $u     = $vertices->[$i];
                my $v     = $vertices->[$j];
                my $v_sum = $chksum{$v};
                my $u_sum = $chksum{$u};
                my $weight
                  = $v_sum > $u_sum ? $v_sum - $u_sum : $u_sum - $v_sum;
                $g->add_weighted_edge($u, $v, $weight);
                $edge_count++;
            }
        }
    }

    my $start = 'words';
    my $end   = 'graph';

    say qq[Looking for a path between '$start' and '$end'];
    my @path = $g->SP_Dijkstra($start, $end);

    say qq[PATH: ];
    say for @path;
}

sub chksum {
    ## String -> Integer
    my $word = shift;
    my $sum  = 0;
    for my $c (split //, $word) {
        $sum += ord($c);
    }
    return $sum;
}

sub slurp {
    ## Pathname -> Array
    my $f = shift;
    open my $in, '<', $f;
    local $/;
    my @lines = split /\n/, <$in>;
    close $in;
    return @lines;
}

main();

References

[Knuth1993] Knuth, The Stanford GraphBase: A Platform for Combinatorial Computing. Addison-Wesley,

Solving the SEND MORE MONEY problem with Mathematica

(Image courtesy Jorge Jaramillo under Creative Commons license)

The SEND MORE MONEY problem is described as follows.  How do we convert the characters in the equation SEND + MORE = MONEY into numbers such that the formula (in this case, a simple addition) holds?

This type of puzzle is also known as a cryptarithm (“secret arithmetic”), since the numbers have been substituted with a code made of letters.

There are a number of ways to solve this problem.  For example, it can be done using exhaustive search, as described here.  It can also be solved using logic programming, as in this Prolog example.  Another way to solve it is with a discrete optimization modeling language like MiniZinc.  (In fact, it’s quite easy to solve with MiniZinc, but we’ll leave that for another time.)

Recently I became curious if there was a way to solve this using Mathematica.  A web search yielded this page on StackOverflow, which includes several nice example programs.  However, there was a problem: I am still learning the Mathematica language, and most of the solutions didn’t make much sense to me.

Therefore, I resolved to dive in and figure out how to solve it myself in a way that I could actually understand.

My first attempt was based on one of the examples from the StackOverflow post linked above, but “simplified” so that I could understand it, since it only used one function, FindInstance.  The good news is, it was able to find a solution.  The bad news is, it was not the solution, but instead just one of the many solutions that are possible if you don’t have a global “alldifferent” constraint – in this case, it found a solution with all zeroes, which is trivially true but not very interesting:

FindInstance[{(1000 s + 100 e + 10 n + d ) + ( 
     1000  m + 100 o + 10 r + e ) == (10000 m + 1000 o + 100 n + 
     10 e + y)}, {s, e, n, d, m, o, r, y}, Integers]
{{s -> 0, e -> 0, n -> 0, d -> 0, m -> 0, o -> 0, r -> 0, y -> 0}}

For my next attempt, I discovered that FindInstance accepts an argument that tells it how many solutions to find.  I asked it to find 2 solutions, in the hope that at least one of them would be something other than a list of zeroes.  In that respect, I was not disappointed:

FindInstance[{(1000 s + 100 e + 10 n + d ) + ( 
     1000  m + 100 o + 10 r + e ) == (10000 m + 1000 o + 100 n + 
     10 e + y)}, {s, e, n, d, m, o, r, y}, Integers, 2]
{{s -> 5, e -> -47, n -> -34, d -> 16, m -> 16, o -> -2, r -> -2, 
  y -> -138421}, {s -> 6, e -> 14, n -> 18, d -> -3, m -> -1, o -> 47,
   r -> 24, y -> -27409}}

However, the results were still not what I was trying to achieve: the solutions it found used large numbers and/or negative numbers, whereas I was looking for numbers between 0 and 9, as shown in the answer on this page.

It turns out we are still missing some important constraints of the problem that need to be captured if we want to find a solution. Let’s try to list them all out:

1. The numbers corresponding to the letters must add up properly according to the equation (this part is done, as we have already encoded this for FindInstance above)
2. The numbers in the solution must be between 0 and 9
3. Every number in the solution must be different

Since we have already encoded the equation (constraint #1), we next need to figure out how to encode constraint #2: “the numbers must be between 0 and 9”.  One way to do it is to write everything out by hand in a form that could be passed to FindInstance, like this:

{d + 101 e + 1000 m + 10 n + 100 o + 10 r + 1000 s == 
  10 e + 10000 m + 100 n + 1000 o + y, 0 <= s <= 9, 0 <= e <= 9, 
 0 <= n <= 9, 0 <= d <= 9, 0 <= m <= 9, 0 <= o <= 9, 0 <= r <= 9, 
 0 <= y <= 9}

However, that’s a lot of writing.  Also it won’t really generalize to other problems of this type.  After doing all this work, I’d rather have something more general that I can try to use in future programs.

After a lot of playing around with Mathematica, I discovered that it has a couple of functions Join and Thread, that can be used to build up lists of terms without actually evaluating them, so you can pass them into functions to evaluate later.  Join joins several lists of things together, while Thread kind of “maps” a function across a list of terms without actually evaluating the function. This results in a new list of terms where the function is “written into” the code so that you can evaluate it.  This reminded me a bit of building up lists of atoms, etc., in a quoted list in a Lisp program, albeit with a very different flavor.

In any case, below we are using these functions to join two lists: 1) the actual equation we want to solve, and 2) the constraints on the values in that equation.

Join[{1000 s + 100 e + 10 n + d + 1000  m + 100 o + 10 r + e == 
   10000 m + 1000 o + 100 n + 10 e + y }, 
 Thread[0 <=  # <= 9 ] & @ {s, e, n, d, m, o, r, y}]
{d + 101 e + 1000 m + 10 n + 100 o + 10 r + 1000 s == 
  10 e + 10000 m + 100 n + 1000 o + y, 0 <= s <= 9, 0 <= e <= 9, 
 0 <= n <= 9, 0 <= d <= 9, 0 <= m <= 9, 0 <= o <= 9, 0 <= r <= 9, 
 0 <= y <= 9}


Looking at the output above, it appears to be in the right format for passing into FindInstance. Let’s try it:

FindInstance[
 Join[{1000 s + 100 e + 10 n + d + 1000  m + 100 o + 10 r + e == 
    10000 m + 1000 o + 100 n + 10 e + y}, 
  Thread[0 <=  # <= 9 ] & @ {s, e, n, d, o, r, y}, 
  Thread[0 < # <= 9] &@{m} ], {s, e, n, d, m, o, r, y}, Integers, 1]
{{s -> 9, e -> 9, n -> 0, d -> 5, m -> 1, o -> 1, r -> 8, y -> 4}}

This is an answer, but again it’s not the answer; specifically, we are looking for an answer that meets our constraint #3: “Every number in the solution must be different”.

Looking at the above, we see that there is an additional constraint we still need to capture: not only do the letters have to be between 0 and 9 (constraint #2 above), but the letter M has to be between 1 and 9.  This is obvious if you look at the equation, since if M were 0, then S + M = 0 would mean that S + 0 = O, which would mean S = O.  Also, M would not appear in the output of the addition if it were equal to zero.

We can encode this additional constraint as shown in the example below, by passing a third list to Join with the constraint on M that it be greater than zero – but still less than 9, like the others.

Join[{1000 s + 100 e + 10 n + d + 1000  m + 100 o + 10 r + e == 
   10000 m + 1000 o + 100 n + 10 e + y }, 
 Thread[0 <=  # <= 9 ] & @ {s, e, n, d, o, r, y}, 
 Thread[0 < # <= 9 ] & @ {m}]
{d + 101 e + 1000 m + 10 n + 100 o + 10 r + 1000 s == 
  10 e + 10000 m + 100 n + 1000 o + y, 0 <= s <= 9, 0 <= e <= 9, 
 0 <= n <= 9, 0 <= d <= 9, 0 <= o <= 9, 0 <= r <= 9, 0 <= y <= 9, 
 0 < m <= 9}

After playing around for a while with FindInstance, I realized that while it’s very good at finding 1 .. n solutions to a problem, there wasn’t a way (that I could see) to be sure that it was getting all of the solutions.  Further, it wasn’t clear how to apply what would essentially be the “alldifferent” constraint to the results (our constraint #3 from above).

FindInstance[
 Join[{1000 s + 100 e + 10 n + d + 1000  m + 100 o + 10 r + e == 
    10000 m + 1000 o + 100 n + 10 e + y }, 
  Thread[0 <=  # <= 9 ] & @ {s, e, n, d, o, r, y}, 
  Thread[0 < # <= 9 ] & @ {m}], {s, e, n, d, m, o, r, y}, Integers]
{{s -> 9, e -> 9, n -> 0, d -> 5, m -> 1, o -> 1, r -> 8, y -> 4}}

Luckily, while reading the documentation for FindInstance, I discovered the Solve function, which has the nice property that it will accept the same arguments as FindInstance, but will go ahead and find all of the solutions. It turns out there are quite a few (keep scrolling):

Solve[Join[{1000 s + 100 e + 10 n + d + 1000  m + 100 o + 10 r + e == 
    10000 m + 1000 o + 100 n + 10 e + y }, 
  Thread[0 <=  # <= 9 ] & @ {s, e, n, d, o, r, y}, 
  Thread[0 < # <= 9 ] & @ {m}], Integers]
{{d -> 0, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 0}, {d -> 0, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 0}, {d -> 0, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 1}, {d -> 0, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 1}, {d -> 0, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 2}, {d -> 0, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 2}, {d -> 0, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 3}, {d -> 0, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 3}, {d -> 0, e -> 4, m -> 1, n -> 4, o -> 0, r -> 0, s -> 9, 
  y -> 4}, {d -> 0, e -> 4, m -> 1, n -> 5, o -> 0, r -> 9, s -> 9, 
  y -> 4}, {d -> 0, e -> 5, m -> 1, n -> 5, o -> 0, r -> 0, s -> 9, 
  y -> 5}, {d -> 0, e -> 5, m -> 1, n -> 6, o -> 0, r -> 9, s -> 9, 
  y -> 5}, {d -> 0, e -> 6, m -> 1, n -> 6, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 0, e -> 6, m -> 1, n -> 7, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 0, e -> 7, m -> 1, n -> 7, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 0, e -> 7, m -> 1, n -> 8, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 0, e -> 8, m -> 1, n -> 8, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 0, e -> 8, m -> 1, n -> 9, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 0, e -> 9, m -> 1, n -> 0, o -> 1, r -> 9, s -> 9, 
  y -> 9}, {d -> 0, e -> 9, m -> 1, n -> 9, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 1, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 1}, {d -> 1, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 1}, {d -> 1, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 2}, {d -> 1, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 2}, {d -> 1, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 3}, {d -> 1, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 3}, {d -> 1, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 4}, {d -> 1, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 4}, {d -> 1, e -> 4, m -> 1, n -> 4, o -> 0, r -> 0, s -> 9, 
  y -> 5}, {d -> 1, e -> 4, m -> 1, n -> 5, o -> 0, r -> 9, s -> 9, 
  y -> 5}, {d -> 1, e -> 5, m -> 1, n -> 5, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 1, e -> 5, m -> 1, n -> 6, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 1, e -> 6, m -> 1, n -> 6, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 1, e -> 6, m -> 1, n -> 7, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 1, e -> 7, m -> 1, n -> 7, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 1, e -> 7, m -> 1, n -> 8, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 1, e -> 8, m -> 1, n -> 8, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 1, e -> 8, m -> 1, n -> 9, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 1, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 0}, {d -> 2, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 2}, {d -> 2, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 2}, {d -> 2, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 3}, {d -> 2, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 3}, {d -> 2, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 4}, {d -> 2, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 4}, {d -> 2, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 5}, {d -> 2, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 5}, {d -> 2, e -> 4, m -> 1, n -> 4, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 2, e -> 4, m -> 1, n -> 5, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 2, e -> 5, m -> 1, n -> 5, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 2, e -> 5, m -> 1, n -> 6, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 2, e -> 6, m -> 1, n -> 6, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 2, e -> 6, m -> 1, n -> 7, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 2, e -> 7, m -> 1, n -> 7, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 2, e -> 7, m -> 1, n -> 8, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 2, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 2, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 1}, {d -> 3, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 3}, {d -> 3, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 3}, {d -> 3, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 4}, {d -> 3, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 4}, {d -> 3, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 5}, {d -> 3, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 5}, {d -> 3, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 3, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 3, e -> 4, m -> 1, n -> 4, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 3, e -> 4, m -> 1, n -> 5, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 3, e -> 5, m -> 1, n -> 5, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 3, e -> 5, m -> 1, n -> 6, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 3, e -> 6, m -> 1, n -> 6, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 3, e -> 6, m -> 1, n -> 7, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 3, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 3, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 3, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 2}, {d -> 4, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 4}, {d -> 4, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 4}, {d -> 4, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 5}, {d -> 4, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 5}, {d -> 4, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 4, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 4, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 4, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 4, e -> 4, m -> 1, n -> 4, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 4, e -> 4, m -> 1, n -> 5, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 4, e -> 5, m -> 1, n -> 5, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 4, e -> 5, m -> 1, n -> 6, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 4, e -> 6, m -> 1, n -> 7, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 4, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 4, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 2}, {d -> 4, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 3}, {d -> 5, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 5}, {d -> 5, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 5}, {d -> 5, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 5, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 5, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 5, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 5, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 5, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 5, e -> 4, m -> 1, n -> 4, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 5, e -> 4, m -> 1, n -> 5, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 5, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 5, e -> 6, m -> 1, n -> 7, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 5, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 2}, {d -> 5, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 3}, {d -> 5, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 4}, {d -> 6, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 6}, {d -> 6, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 6}, {d -> 6, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 6, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 6, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 6, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 6, e -> 3, m -> 1, n -> 3, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 6, e -> 3, m -> 1, n -> 4, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 6, e -> 4, m -> 1, n -> 5, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 6, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 6, e -> 6, m -> 1, n -> 7, o -> 0, r -> 8, s -> 9, 
  y -> 2}, {d -> 6, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 3}, {d -> 6, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 4}, {d -> 6, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 5}, {d -> 7, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 7}, {d -> 7, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 7}, {d -> 7, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 7, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 7, e -> 2, m -> 1, n -> 2, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 7, e -> 2, m -> 1, n -> 3, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 7, e -> 3, m -> 1, n -> 4, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 7, e -> 4, m -> 1, n -> 5, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 7, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, 
  y -> 2}, {d -> 7, e -> 6, m -> 1, n -> 7, o -> 0, r -> 8, s -> 9, 
  y -> 3}, {d -> 7, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 4}, {d -> 7, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 5}, {d -> 7, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 6}, {d -> 8, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 8}, {d -> 8, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 8}, {d -> 8, e -> 1, m -> 1, n -> 1, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 8, e -> 1, m -> 1, n -> 2, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 8, e -> 2, m -> 1, n -> 3, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 8, e -> 3, m -> 1, n -> 4, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 8, e -> 4, m -> 1, n -> 5, o -> 0, r -> 8, s -> 9, 
  y -> 2}, {d -> 8, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, 
  y -> 3}, {d -> 8, e -> 6, m -> 1, n -> 7, o -> 0, r -> 8, s -> 9, 
  y -> 4}, {d -> 8, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 5}, {d -> 8, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 6}, {d -> 8, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 7}, {d -> 9, e -> 0, m -> 1, n -> 0, o -> 0, r -> 0, s -> 9, 
  y -> 9}, {d -> 9, e -> 0, m -> 1, n -> 1, o -> 0, r -> 9, s -> 9, 
  y -> 9}, {d -> 9, e -> 1, m -> 1, n -> 2, o -> 0, r -> 8, s -> 9, 
  y -> 0}, {d -> 9, e -> 2, m -> 1, n -> 3, o -> 0, r -> 8, s -> 9, 
  y -> 1}, {d -> 9, e -> 3, m -> 1, n -> 4, o -> 0, r -> 8, s -> 9, 
  y -> 2}, {d -> 9, e -> 4, m -> 1, n -> 5, o -> 0, r -> 8, s -> 9, 
  y -> 3}, {d -> 9, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, 
  y -> 4}, {d -> 9, e -> 6, m -> 1, n -> 7, o -> 0, r -> 8, s -> 9, 
  y -> 5}, {d -> 9, e -> 7, m -> 1, n -> 8, o -> 0, r -> 8, s -> 9, 
  y -> 6}, {d -> 9, e -> 8, m -> 1, n -> 9, o -> 0, r -> 8, s -> 9, 
  y -> 7}, {d -> 9, e -> 9, m -> 1, n -> 0, o -> 1, r -> 8, s -> 9, 
  y -> 8}}

However, as noted above, most of these solutions don’t pass the “alldifferent” constraint that we need for this problem. In order to pick out the solution that maps a unique integer to each letter, we had to write the code below.  It’s saying basically “of this list of solutions, give me all those whose number of unique (distinct) values is the same as the total number of variables”.  In other words, we pluck out the answer(s) which assign a unique number to each letter.  It turns out there is only one:

Select[%, 
 Function[CountDistinct[Values[#]] == 
   Length[{s, e, n, d, m, o, r, y}]]]
{{d -> 7, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, y -> 2}}

Is this the right answer?  Let’s check it:

9567 + 1085 == 10652
True

Yes, it looks like we’ve found the answer.  Putting it all together in one block of code, we get the following:

sols := Solve[
   Join[{1000 s + 100 e + 10 n + d + 1000  m + 100 o + 10 r + e == 
      10000 m + 1000 o + 100 n + 10 e + y }, 
    Thread[0 <=  # <= 9 ] & @ {s, e, n, d, o, r, y}, 
    Thread[0 < # <= 9 ] & @ {m}], Integers];

Select[sols, 
 Function[CountDistinct[Values[#]] == 
   Length[{s, e, n, d, m, o, r, y}]]]
{{d -> 7, e -> 5, m -> 1, n -> 6, o -> 0, r -> 8, s -> 9, y -> 2}}

Thanks to my friend Justin for reading a draft of this post.

References

Solving a puzzle in the wild with MiniZinc

In a recent episode of the excellent Art of Mathematics podcast (specifically the one called A beautiful theorem with an ugly proof), the host Dr. Carol Jacoby offers the listener the following puzzle to solve:

Can you find a list of numbers such that they can be listed in an array with the properties that:

  • The 0th cell contains how many zeroes are in the array,
  • The 1st cell contains how many ones,
  • The 2nd cell contains how many twos,
  • …,
  • The nth cell contains how many ns

While going through the solution to the puzzle in the next episode, Dr. Jacoby mentioned that it was not incredibly hard to solve, but it was difficult to find an elegant proof that there was only one solution.

I spent some time noodling with this problem in my notebook, trying to discover (1) one or more solutions (obviously), and (2) properties of the problem that might lead to a proof. However I am no mathematician, so although I did find some solutions for various (small) values of n, I did not figure out how to prove anything about them.

It occurred to me that it could be fun to write a program to solve this problem. Lately, I have been working through the online course Basic Modeling for Discrete Optimization, which uses a declarative constraint programming language called MiniZinc. MiniZinc is developed by a team that includes one of the course instructors, Dr. Peter Stuckey, who also wrote an interesting book on constraint programming called Programming with Constraints, which is on my to-read list.

As I was working through the discrete optimization course, I thought: why not take a crack at this problem with MiniZinc? Although my MiniZinc programming capabilities are still at the “baby talk” level, that’s still enough to do useful work.

Before we share the actual MiniZinc program below, let’s restate the problem slightly differently so that it’s closer to the form MiniZinc will need:

  • Give me an integer n=10 that represents the maximum value of the array 0..9
  • Give me a set of integers we can use for indexing into the above array
  • Create the actual array (let’s call it xs) based on the above specification
  • Constraint: xs element 0 contains how many zeroes are in the array
  • Constraint: xs element 1 contains how many ones are in the array
  • … and so on for 2 through 9, until we reach the end of the array (in this case it has ten elements)
  • Find a solution that satisfies the above constraints

The complete program listing is below. I won’t try to explain the syntax here (for that see the MiniZinc tutorial), but you should be able to puzzle it out if you’ve done much programming.

Invoke it like so:

$ minizinc -a aom.mzn

This should result in the following output. The double line at the bottom means that this is the best/optimal solution.

10 = [6, 2, 1, 0, 0, 0, 1, 0, 0, 0]
----------
==========

Program Listing

% aom.mzn -- Puzzle from an episode of the podcast "The Art of Mathematics"

int: n = 10;

set of int: INDEX = 1 .. n;

array[INDEX] of var 0..9: x;

% The 0th cell contains how many zeroes are in the array.
% The 1st cell contains how many ones.
% The 2nd cell contains how many twos.
% ...
% The 9th cell contains how many nines.

constraint forall(i in INDEX)(x[i] = sum(j in INDEX)(x[j] = i-1));

% I wrote the "unrolled loop" below first, then combined them into the
% 'forall' expression you see above.

% constraint x[1] = sum(i in INDEX)(x[i] = 0);
% constraint x[2] = sum(i in INDEX)(x[i] = 1);
% constraint x[3] = sum(i in INDEX)(x[i] = 2);
% constraint x[4] = sum(i in INDEX)(x[i] = 3);
% constraint x[5] = sum(i in INDEX)(x[i] = 4);
% constraint x[6] = sum(i in INDEX)(x[i] = 5);
% constraint x[7] = sum(i in INDEX)(x[i] = 6);
% constraint x[8] = sum(i in INDEX)(x[i] = 7);
% constraint x[9] = sum(i in INDEX)(x[i] = 8);
% constraint x[10] = sum(i in INDEX)(x[i] = 9);

solve satisfy;

output ["\(sum(x)) = \(x)\n"];

% eof