?

Log in

Ant Puzzle solutions - leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).

Tags:, , , ,
Security:
Subject:Ant Puzzle solutions
Time:05:44 pm
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).

Points where the sum of the digits of the x coordinate plus the sum of the digits of the y coordinate are greater than 25 are inaccessible to the ant. For example, the point (59,79) is inaccessible because 5 + 9 + 7 + 9 = 30, which is greater than 25.

How many points can the ant access if it starts at (1000, 1000), including (1000, 1000) itself?

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

mystack; mystack.push({1000, 1000}); while (!mystack.empty()) { const P p = mystack.top(); mystack.pop(); if (seen.find(map_p(p)) == seen.end()) { seen.insert(map_p(p)); if (sum_digits(p.x) + sum_digits(p.y) <= 25) { count++; mystack.push({ (int16_t)(p.x + 1), p.y }); mystack.push({ (int16_t)(p.x - 1), p.y }); mystack.push({ p.x, (int16_t)(p.y + 1) }); mystack.push({ p.x, (int16_t)(p.y - 1) }); } } } return count; } int main() { printf("%u\n", ant()); return 0; }


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 Previous Entry Share Next Entry

(Anonymous)
Subject:Got it
Link:(Link)
Time:2011-09-20 11:32 pm (UTC)
Sorry. and Never Mind

There's no implied or actual boundaries on the "array" so the ant *can* walk to 1001, 1002, etc.

Thanks.
(Reply) (Thread)

Ant Puzzle solutions - leonardo
View:Recent Entries.
View:Archive.
View:Friends.
View:Profile.
View:Website (My Website).