What's the most elegant 10-20 line function you've seen/written?

Question

In the vein of What is the coolest thing you can do in <10 lines of simple code? Help me inspire beginners!, but for non-beginners: Tell us about some of your fast solutions to complex problems, or ingenious uses of little-known language features.

Two examples I (and I'm sure everyone else) have seen are Quake's Inverse Square Root and Duff's Device

Answer 1

Hanoi tower is the most efficient implementation I've ever seen.

As long as your language can support recursion, you can implement it

Answer 2

One-liner in Microsoft Powershell language to build pipe with some XML file containing request, invoking webservice and doing something with result. All it using only bare Powershell and Windows without 3rd party plugins or products.

Answer 3

Using the Sieve algorithm to find primes can be quite neat. I made that in a parallellized manner once, but I'm afraid used 88 lines in Oz.

Answer 4

The below Scheme code is from CS 61A Lecture 12: Hierarchical Data.

The professor told to the students that this is probably the most beautiful piece of code
they'll see in their life and they should study it.

(define make-tree cons)
(define datum car)
(define children cdr)

(define (leaf? node)
  (null? (children node)) )

(define (treemap fn tree)
  (make-tree (fn (datum tree))
             (map (lambda (child) (treemap fn child))
                  (children tree) )))

treemap creates a treeB from treeA where datumB = fn(datumA)

tree is a list of nodes, the first node (car) points to a datum and each of the rest (children) nodes points to a tree.

Edit: example,

;;; Test treemap
(define (leaves . seq)
  (map (λ (x) (make-tree x '())) seq))

(define treeA
  (make-tree 1
             (list (make-tree 2 (leaves 3 4))
                   (make-tree 5 (leaves 6 7 8)) )))

(define (x*10 x)
  (* x 10))

> treeA
(1 (2 (3) (4)) (5 (6) (7) (8)))
> (treemap x*10 treeA)
(10 (20 (30) (40)) (50 (60) (70) (80)))
>

Answer 5

Recursive solutions are always at the top of my list for elegance:

def fact (n):
    if (n < 2):
        return 1
    return n * fact (n-1)

Preemptive community wiki since that's what poll questions should have been anyway :-)

Answer 6

Virtually all the code I write these days is python. It's rare that individual functions are over 10 lines long (unit tests are usually longer, but that's another story). If it were me, I'd want to inspire beginners with readability over brevity.

But, in the spirit of the question, here's one of my favorite quicksort implementations in 3 or 4 lines (naturally in python):

def qsort(L):
    if len(L) <= 1: return L
    return qsort( [ lt for lt in L[1:] if lt < L[0] ] ) + \
        [ L[0] ]  +  qsort( [ ge for ge in L[1:] if ge >= L[0] ] )

Answer 7

If you're talking elegant code, you can't go past a functional language.
I was going to post this as a reply to paxdiablo, but I think this deserves it's own answer.
Haskell:

fac n = product [1..n]

Answer 8

Not really for beginners, but this combines the two extremes: a functional, but (probably) "crude" language. Then again, it's not really for beginners either:

template <class T, class U>
struct TypeList {
   typedef T Head;
   typedef U Tail;
};

As much as I'd like to say the Scheme code (for one example) is cooler, a recursive factorial or binary search tree doesn't even get into the same league. For something in Scheme that's short and cool, I'd nominate this:

 (define (curry f n) 
   (if (zero? n) 
       (f) 
       (lambda args 
         (curry (lambda rest 
                  (apply f (append args rest))) 
                (- n (length args))))))

Especially for somebody like me who spent some time playing with ML, and grew to like currying, this definite a cool piece of code. Compared to this, a TypeList is (arguably) a bit less elegant, but probably more useful. To give credit where due, the typelist code is Andre Alexandrescu's. I'm not sure where the Scheme currying code originated -- there have been enough variations that I'm not sure you could track down who wrote this exact one (and I don't remember where I got it...)

Edit: to head off the inevitable arguments: C++ (as a whole) isn't a functional language, but meta-programming with templates is (and TypeLists are purely a compile-time metaprogramming kind of thing...)

Answer 9

This is the Y-Combinator in C#

public Func<T, T> Y(Func<Func<T, T>, Func<T, T>> f)
{
    return x => f(Y(f))(x);
}

Answer 10

I like how this factorial function in Clojure shows off higher-order functions (i.e. the multiplication function is passed as an argument to reduce):

(defn fac [n]
    (reduce #'* (range 1 (+ n 1))))

Also, since range returns a lazy sequence of numbers, you don't instantiate a huge array of numbers when performing factorial on large numbers.

Answer 11

Here's the coolest thing I've written in the last hour. It's not all that cool, in fact, it's butt ugly and uncommented. But it works and checks for errors in the input. And through formatting abuse the main function comes in at exactly the prescribed 20 lines. It is a 4 function calculator (all left associative) with precedence and terminated with a semicolon (precedence of multiply > divide > add > subtract, not precisely correct since multiply should equal divide, etc). Skips whitespace. No parentheses, but it wouldn't be hard. It relies on the workings of the shunting yard algorithm to prevent bad things from happening (e.g. stack underflow, loop termination). That is what I think is cool about it. It's important to check for bugs at the low detail level, but at some point, you're going to have to use complicated algorithms (not that this one is all that complicated), and rely on some analysis independent of your code to make sure things work correctly.

#include <cstring>
#include <new>
#include <vector>
#include <iomanip>
#include <iostream>

int main(int argc, char **argv) {
try {
  const char precedence_table[] = "*/+-;";
  char   op = '\0';
  std::vector<char>   operator_stack;
  operator_stack.push_back('\0');
  double x;
  std::vector<double> operand_stack;
  while (op != ';') {
    std::cin >> x >> std::ws >> op;
    if (!std::cin || !strchr(precedence_table, op)) throw std::exception();
    operand_stack.push_back(x);
    while (strchr(precedence_table, operator_stack.back()) <= strchr(precedence_table, op)) {
      switch (operator_stack.back()) {
        case '*': operand_stack[operand_stack.size()-2] *= operand_stack.back(); break;
        case '/': operand_stack[operand_stack.size()-2] /= operand_stack.back(); break;
        case '+': operand_stack[operand_stack.size()-2] += operand_stack.back(); break;
        case '-': operand_stack[operand_stack.size()-2] -= operand_stack.back(); break; }
      operand_stack.pop_back();
      operator_stack.pop_back(); }
    operator_stack.push_back(op); }
  std::cout << operand_stack.back(); }
catch (std::exception &e) {
  std::cout << e.what(); }
}

Answer 12

Ahhh i just wrote on about 20 mins ago

I was using FTP.dir(), and by default, it prints results to sys.stdout. If you want to grab the results to do something with them, you need a callback function.

At first, it looked like this:

def get_dirs(self):
    # self.store_dirs was the callback funcion
    self.ftp.dir('/www/', self.store_dirs)

def store_dirs(self, fileinfo):
    self.dirs.append(fileinfo[56:])

Then it became this

def get_dirs(self, line = None):
    if line == None:
        self.ftp.dir('/www/', self.get_dirs)
    else:
        self.dirs.append(line[56:])

so now the one function will grab and store the files' info :)

Answer 13

I like metaprogramming.

template<int P, int M> struct moduli {
    static const int modulus = P%M && moduli<P,M-1>::modulus;
};
template<int P> struct isPrime {
    static const bool value = moduli<P,P-1>::modulus;
};
template<> struct isPrime<1> { static const bool value = true; };
template<int P> struct moduli<P, 1> { static const int modulus = 1; };

static_assert(isPrime<N>::value, "is prime");

Translated with g++ -c -DN=number-to-test -std=c++0x prime.cpp the compiler will tell you wether number-to-test is not prime.

g++ -c -DN=100 -std=c++0x prime.cpp
prime.cpp:18: error: static assertion failed: "is prime"

If the number is prime nothing is printed - mainly because there is no neat sounding static_assert message.

Answer 14

I just love these lines. They sort a file with the use of mmap and qsort. I wrote it 5 years ago and still I can look at it and smile...

void sort_time_track_db(time_track_db *db) {
    void *mptr;
    struct stat sb;
    if (fstat(fileno(db->fp), &sb))
        return;
    mptr = mmap(NULL,
                sb.st_size,
                PROT_READ | PROT_WRITE,
                MAP_SHARED,
                fileno(db->fp),
                0);
    fflush(db->fp);
    qsort(mptr + sizeof(time_track_db) - sizeof(time_track_entry),
          db->num, 
          sizeof(time_track_entry), 
          mcompare_func);
    munmap(mptr, sb.st_size);
}

Answer 15

Quicksort in haskell:

quicksort [] = []
quicksort (x:xs) = quicksort (filter (< x) xs) ++ [x] ++ quicksort (filter (>= x) xs)

Answer 16

Some people consider it awesome that Peter Norvig, ranking egg-head at Google, wrote a spelling corrector in 20 lines of Python.

Here's a link to the full story: http://norvig.com/spell-correct.html

And here's the code, if you don't want to read the story:

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   s = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in s if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in s if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in s for c in alphabet if b]
   inserts    = [a + c + b     for a, b in s for c in alphabet]
   return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words): return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

Examples:

>>> correct('speling')
'spelling'
>>> correct('korrecter')
'corrector'

Answer 17

This is from the Cinch Framework:

public static string GetPropertyName<T>(
        Expression<Func<T, Object>> propertyExpression)
    {
        var lambda = propertyExpression as LambdaExpression;
        MemberExpression memberExpression;
        if (lambda.Body is UnaryExpression)
        {
            var unaryExpression = lambda.Body as UnaryExpression;
            memberExpression = unaryExpression.Operand as MemberExpression;
        }
        else
        {
            memberExpression = lambda.Body as MemberExpression;
        }

        var propertyInfo = memberExpression.Member as System.Reflection.PropertyInfo;

        return propertyInfo.Name;
    }

Not only does this let you avoid using magic strings in implementing INotifyPropertyChanged, but it allows code like this:

private static readonly PropertyChangedEventArgs FooArgs = ObservableHelper.CreateArgs<Bar>(x => x.Foo);
public string Foo
get
{
    return _foo;
}
set 
{
    _foo = value;
    OnPropertyChanged(FooArgs);
}

Because you are creating the PropertyChangedEventArgs only once, it runs faster than:

OnPropertyChanged("Foo");

And it also provides compile time checking :-).

Answer 18

This is an in-place string filter function that I wrote a while ago.

void filterStringWithLength (char * p1, size_t length, char minChar, char maxChar)
{
    char *p2 = p1;

    while (length--)
        *p2 >= minChar && *p2 <= maxChar ? *p1++ = *p2++ : p2++; *p1 = 0;
}

Answer 19

It's not really 10 lines and not really a function but someone asked for a solver to enigmatic calculus, i.e. find the digits to assign to letters to have a meaningful system:

ab + acd = aec
e * da = bfg
dge + bg = chi
ab * e = dge
acd / da = bg
aec - bfg = chi

The solution was:

#include <list>
#include <cmath>
#include <vector>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <ext/numeric>
#include <iterator>
#include <functional>
#include <boost/bind.hpp>
using namespace std;
static const int fact_10 = 3628800;
static const int tenpowers[] = {1, 10, 100, 1000, 10000 /*, ... */ };
struct equation {
  struct valorize {
    int s; const vector<int>& idx_m;
    valorize(const vector<int>&idx) : s(0), idx_m(idx) { }
    int operator()(int tot, char b) { return tot+idx_m[b-'a']*tenpowers[s++]; }
  };
  int operator()(const vector<int>& idx) const {
    int opa=accumulate(opa_m.rbegin(), opa_m.rend(), 0, valorize(idx));
    int opb=accumulate(opb_m.rbegin(), opb_m.rend(), 0, valorize(idx));
    int res=accumulate(res_m.rbegin(), res_m.rend(), 0, valorize(idx));
    switch(operator_m) {
      case '+': return abs(opa+opb-res);
      case '-': return abs(opa-opb-res);
      case '*': return abs(opa*opb-res);
      case '/': return abs(opa-opb*res);
    }
  }
  friend istream& operator>>(istream& in, equation& e) { char dummy; 
    return in >> e.opa_m >> e.operator_m >> e.opb_m >> dummy >> e.res_m; }
protected:
  string opa_m, opb_m, res_m;
  char operator_m;
};
int main(int argc, char* argv[]) {
  if(argc != 2) { cerr << "ces file.dat" << endl; return 1; }
  vector<equation> eqns; ifstream dat(argv[1]);
  if(dat) copy(istream_iterator<equation>(dat), istream_iterator<equation>(), 
           back_inserter(eqns));
  else { cerr <<  "can't open " << argv[1] << endl; return 1; }
  vector<int> x(10); iota(x.begin(), x.end(), 0);
  typedef list< vector<int> > sol_list;
  sol_list solutions;
  for(int ii(0); ii != fact_10; ++ii) {
    if(!accumulate(eqns.begin(),eqns.end(),0,boost::bind(std::plus<int>(),_1, 
     boost::bind(&equation::operator(), _2, boost::ref(x)))))
      solutions.push_back(x);
    next_permutation(x.begin(), x.end());
  }
  for(sol_list::iterator si = solutions.begin(); si!= solutions.end(); ++si)
    copy(si->begin(), si->end(), ostream_iterator<int>(cout << endl, " "));
  cout << endl;
}

Ah, wait... it was about elegance!