jump to navigation

Solving Combinatoric Problems with List Comprehensions 10 May 2015

Posted by Oliver Mason in algorithm, erlang.
Tags: , ,
add a comment

My daughter had some maths homework the other day:

You have 4 bags, each full of the numbers 1, 3, 5, and 7 respectively. Take 10 of the numbers that when added up make 37. What numbers are they?

So far so good: that sounds easy enough. But a bit of trial and error quickly leads nowhere. Something can’t be right. So, let’s get the computer to work it out.

As I haven’t done much Erlang recently I thought I’d give it a go. And, during a casual glance at Armstrong’s Programming in Erlang I thought I’d finally understood list comprehensions, so I wrote the following program:
-module(comb).
-export([result/0]).
result() ->
[{A+B+C+D+E+F+G+H+I+J,A,B,C,D,E,F,G,H,I,J}||
A <- [1,3,5,7],
B <- [1,3,5,7],
C <- [1,3,5,7],
D <- [1,3,5,7],
E <- [1,3,5,7],
F <- [1,3,5,7],
G <- [1,3,5,7],
H <- [1,3,5,7],
I <- [1,3,5,7],
J <- [1,3,5,7],
A+B+C+D+E+F+G+H+I+J =:= 37].

I declare a module with one function, `result/0`. This finds me ten variables that can take any of the four specified values and add up to 37. Simples!

The list comprehension has ten generators, and one filter; it will return a tuple with the sum and the individual variables’ values.

Erlang R16B01 (erts-5.10.2) [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]
Eshell V5.10.2 (abort with ^G)
1> comb:result().
[]
2>

WTF???! An empty list?! So I try changing the 37 to another value, like 36.
3> comb:result().
[{36,1,1,1,1,1,3,7,7,7,7},
{36,1,1,1,1,1,5,5,7,7,7},
{36,1,1,1,1,1,5,7,5,7,7},
{36,1,1,1,1,1,5,7,7,5,7},
{36,1,1,1,1,1,5,7,7,7,5},
[etc, etc].

So it does work! Only, there doesn’t seem to be an answer to the question. And with a bit of logical reasoning it is obvious: when adding two odd numbers, you get an even number. So adding ten odd numbers also yields an even number, but 37 is odd.

What I learnt from this exercise: thinking about the problem beforehand can save you time, as there was no need to write a program at all. But then, I did get to use list comprehensions, and have learnt how powerful they are. And it neatly shows Erlang’s Prolog roots as well.

Tags for Erlang 17 March 2008

Posted by Oliver Mason in erlang.
Tags:
2 comments

The ‘ctags’ program creates a ‘tags’ file, which indexes routines/methods/functions in C source files (and a variety of other languages. The editor vile (my ‘IDE’) can make use of those: you position the cursor on the name of a function, press ^], and the editor jumps to its definition (loading the appropriate source file). The tags file consists of the function name, the file name, and a search pattern.

Running ctags on an Erlang source file does not produce any usable results, unsurprisingly. However, the file format is so simple that a straightforward shell-script will do:

#!/bin/sh
rm -f tags
for i in *.erl
do
cat $i | grep "^[a-z0-9_]*(" |
sed "s/^\([^(]*\)(.*$/\1/" | uniq |
awk  -v file=$i '{printf("%s    %s\\
   /^%s(/\n",$0,file,$0);}' >> tags
done

(The double backslash indicates a line break, as the end of the line would otherwise be outside the box and invisible)

This file processes all *.erl files in a directory, extracts the function names (a sequence of letters, numbers, underscores beginning on the first column and followed by an open round bracket), and creates the correct lines for the tags file.

Works fine so far.