| ||||||||||

A simple problem found here, "F# for python programmers", from page 42: http://combiol.org/fs/FSUG_FS4PPv2.pptx Ant puzzle: There is an ant which can walk around on a planar grid. The ant can move one space at a time left, right, up or down. That is, from (x, y) the ant can go to (x+1, y), (x-1, y), (x, y+1), and (x, y-1). The author compares a Python2 solution with a F# solution (with the idea that the F# is better), the solutions offered (sorry, no text here, just images): In a successive slide it shows that the Python implementation returns the correct result (148848) in about 12.4 seconds, but only on certain compuer, while on another one it produces a stack overflow, while the F# version returns the correct result in 5.8 seconds (and only one machine is tested). I don't know enough about F# to comment, but that Python solution is just bad. This was my first python version, and it has given the right result on the first try: from collections import deque import psyco; psyco.full() def sum_digits(n): tot = 0 while n: tot += n % 10 n //= 10 return tot def ant(): seen = set() count = 0 stack = deque([(1000, 1000)]) while stack: p = stack.pop() if p not in seen: seen.add(p) x, y = p if sum_digits(x) + sum_digits(y) <= 25: count += 1 stack.append((x+1, y )) stack.append((x-1, y )) stack.append((x, y+1)) stack.append((x, y-1)) return count print ant() It gives no stack overflows, and on my oldish PC (Celeron 2.3 GHz, Python v2.6.6) runs in about 0.56 seconds (more than ten times faster than the F# version that maybe runs on a faster PC), without Psyco it runs in about 1.28 seconds. And in my opinion its code is simpler than the F# version. In the standard library of the D language there is no stack data structure yet, so I have used recursion (and there is no hash set yet, so I have used a built-in hash map), this is a basic version, similar to the first one I have written: import std.stdio; struct P { int x, y; } int sumDigits(int n) { int sum = 0; while (n) { sum += n % 10; n /= 10; } return sum; } uint[P] seen; size_t count; void walk(P p) { if (p !in seen) { seen[p] = 0; if (sumDigits(p.x) + sumDigits(p.y) <= 25) { count++; walk(P(p.x+1, p.y)); walk(P(p.x-1, p.y)); walk(P(p.x, p.y+1)); walk(P(p.x, p.y-1)); } } } void main() { walk(P(1000, 1000)); writeln(count); } It runs in about 0.27 seconds if I compile it with (DMD 2.055): dmd -L/STACK:1000000 -O -release -inline ant_puzzle1_d.d This is a faster D version (0.20 seconds run time), but it cheats a little because it knows the max size of the stack (but I think a dynamic stack implemented with a deque, is not much slower than this, even if it doesn't use a region allocator): import std.stdio, std.typetuple; size_t ant() pure nothrow { static int sumDigits(int n) pure nothrow { int sum = 0; while (n) { sum += n % 10; n /= 10; } return sum; } static struct P { short x, y; } // This speeds up the hashing... static uint mapP(in P p) pure nothrow { return (p.x << 16) + p.y; } uint[uint] seen; size_t count; P[44_000] stack = void; size_t stackLen; stack[stackLen] = P(1000, 1000); stackLen++; while (stackLen) { immutable P p = stack[stackLen - 1]; stackLen--; if (mapP(p) !in seen) { seen[mapP(p)] = 0; if (sumDigits(p.x) + sumDigits(p.y) <= 25) { count++; foreach (s; TypeTuple!(P(1,0), P(-1,0), P(0,1), P(0,-1))) { stack[stackLen] = P(cast(short)(p.x+s.x), cast(short)(p.y+s.y)); stackLen++; } } } } return count; } void main() { writeln(ant()); } A C++0x translation, it uses a dynamic stack: #include <stdio.h> #include <stdint.h> #include <stack> #include <boost/unordered_set.hpp> using namespace std; inline int sum_digits(int n) { int sum = 0; while (n) { sum += n % 10; n /= 10; } return sum; } struct P { int16_t x, y; }; inline uint32_t map_p(const P p) { return (p.x << 16) + p.y; } size_t ant() { size_t count = 0; boost::unordered_set<uint32_t> seen; stack Its runtime is 0.12 seconds if I compile it with G++ 4.6.1 like this: g++ -std=c++0x -Wall -Wextra -s -Ofast ant_puzzle_cpp.cpp -o ant_puzzle_cpp All the code shown here: http://www.fantascienza.net/leonardo/js/ant_puzzle.zip | ||||||||||

comments: Leave a comment |