'"Lucky tickets" exercise'

OK, I know this is stupid. I am toying with Haskell, and this task is a textbook example of list comprehensions. Create a list of “lucky ticket numbers”, where the number is six decimal digits, and lucky is when the sum of the first three digits is equal to the sum of the last three digits:

lucky_list =
    [[a,b,c,x,y,z] | a<-[0..9], b<-[0..9], c<-[0..9],
                     x<-[0..9], y<-[0..9], z<-[0..9],
                     a+b+c == x+y+z]
main = putStrLn $ show $ length lucky_list

this runs in 650+ ms on my system. Can we improve on that? Let’s iterate over possible sums (which are from 0 to 27 since 9+9+9=27). For each sum, combine the distinct triples that sum to that. We can iterate over possible pairs of digits (x,y), getting the third digit as (z = sum-x-y). Here is what we get:

lucky_list =
    [x++y | s <- [0..27], x <- triples_with_sum s, y <- triples_with_sum s ]
  where
    triples_with_sum s =
      [[x,y,s-x-y] | x<-[lx .. hx], y<-[ly x .. hy x]]
        where
          lx   | s < 18     = 0
               | otherwise  = s-18
          hx   | s > 9      = 9
               | otherwise  = s
          ly x | s-x-9 < lx = lx
               | otherwise  = s-x-9
          hy x | s-x > 9    = 9
               | otherwise  = s-x
    -- This expression is less optimized but is much simpler:
    -- a <- [0..9], b <- [0..9], let c = s-a-b, c >= 0, c <= 9]
    -- Speed difference is not noticable
main = putStrLn $ show $ length lucky_list

That’s better: about 80 ms. Now we try to do it in C:

#include <stdio.h>

typedef void (*iterator_t)(int a, int b, int s, void (*func)(), int x, int y);

static int count = 0;
#define lsize 65535
static char lucky_list [lsize][6];

static void
give_result(int a, int b, int s, iterator_t iterator, int x, int y)
{
	//printf("[%d,%d,%d,%d,%d,%d]\n", a, b, s-a-b, x, y, s-x-y);
	if (count < lsize) {
		lucky_list[count][0] = a;
		lucky_list[count][1] = b;
		lucky_list[count][2] = s-a-b;
		lucky_list[count][3] = x;
		lucky_list[count][4] = y;
		lucky_list[count][5] = s-x-y;
	}
	count++;
}

static void
iterate_triplets(int a, int b, int s, iterator_t iterator, int p, int q)
{
	int lx = s-18;
	int hx = s;
	if (lx < 0) lx = 0;
	if (hx > 9) hx = 9;

	//if (a >= 0)
	//	printf("%d: %d, %d, %d [%d..%d]\n",
	//		s, a, b, s-a-b, lx, hx);

	for (int x = lx; x <= hx; x++) {
		int ly = s-x-9;
		int hy = s-x;
		if (ly < lx) ly = lx;
		if (hy > x) hy = x;

		for (int y = ly; y <= hy; y++) {
			(*iterator)(x, y, s, give_result, a, b);
			if (x != y) {
				(*iterator)(y, x, s, give_result, a, b);
			}
		}
	}
}

int
main(int argc, char *argv[])
{
	for (int s = 0; s<=27; s++) {
		iterate_triplets(-1, -1, s, iterate_triplets, -1, -1);
	}
	printf("%d\n", count);
	return 0;
}

This was so much longer! And harder to understand. But the speed is so high we could not measure it!.

RSS Atom Generated by Hakyll