?

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:Nice analysis
Link:(Link)
Time:2011-09-20 01:51 pm (UTC)
I, too, considered the original Python code way too complex for no reason.
Also, even in the original code: if Python runs only 2x slower than F#, then heck, F# compiler needs a lot of work...

See also:
http://stackoverflow.com/questions/5850243/fsharp-runs-my-algorithm-slower-than-python
(Reply) (Thread)


leonardo_m
Subject:Re: Nice analysis
Link:(Link)
Time:2011-09-21 12:27 am (UTC)
Thank you for your info. From Stackoverflow site it seems that asking for unboxed tuples in the set, the original F# shap code will probably become faster.
(Reply) (Parent) (Thread)

(Anonymous)
Subject:I must be reading this wrong?!!
Link:(Link)
Time:2011-09-20 11:06 pm (UTC)
I can't understand how the ant ever gets out of his corner at 1000,1000. If we imagine the 2-dimensional array with subscript values increasing to the right and downwards, the 6 cells around the ant's starting position have the following values for
sum_digits(x) + sum_digits(y)

52 53 27
53 54 28
27 28 2

He's starting on the 2 (1000,1000)... BUT he can't step to any of his surrounding cells! ??? How do you ever arrive at a Count greater than 1?

Thanks. I've tried to figure out what I'm interpreting incorrectly for more time than I'd like to admit... Still can't see it...
(Reply) (Thread)


leonardo_m
Subject:Re: I must be reading this wrong?!!
Link:(Link)
Time:2011-09-21 12:26 am (UTC)
> I've tried to figure out what I'm interpreting incorrectly for more time than I'd like to admit...

TV and movies show us people that learn and understand mathematics quickly. But most people need *lot* of time and thinking to even understand small bits of mathematics or to solve small problems. Math is hard. Keep learning.
(Reply) (Parent) (Thread)

(Anonymous)
Subject:Re: I must be reading this wrong?!!
Link:(Link)
Time:2011-09-21 02:44 am (UTC)
>> TV and movies show us people that learn and understand mathematics quickly. <<

Hmmm... Didn't have much to do with understanding math... I initially got the wrong impression that the array was constrained to particular dimensions, and that the ant was initialized to a corner that had no exit...

BTW... I tried this out on an 9 year old 1.7 GHz computer with an old Delphi compiler, and got the right answer in 90-100 ms. It's a bit more verbose than these languages, though it adds some readability; and the code suffers from my initial impression that the array size was limited; and it would need a more efficient sparse bit array for values much greater than 25... ... ... but here's some code:

type

TVisitCounter = class
private
FCount, FXSize, FYSize, FMaxSumDigits : cardinal;
Seen : TBits;
public
property Count : cardinal read FCount;
constructor Create(XSize, YSize, MaxSumDigits : cardinal);
destructor Destroy; override;
function Visited(x, y : cardinal) : boolean;
procedure JustVisited(x, y : cardinal);
procedure Visit(x, y : cardinal);
end;

///////// ...

IMPLEMENTATION

...

function SumOfDigits(c : cardinal): cardinal;
begin
result := 0;
repeat
inc(result, c mod 10);
c := c div 10;
until c = 0;
end;

procedure TForm1.writeln(s: string);
begin
Memo1.Lines.Add(s);
end;

procedure TForm1.btnRunVisitCounterClick(Sender: TObject);
var vc : TVisitCounter;
begin
TickMark;
vc := TVisitCounter.Create(1000, 1000, 25);
try
vc.Visit(1000, 1000);
writeln(TicksElapsedStr);
writeln('I COME UP WITH: ' + IntToStr(vc.Count));
finally
vc.Free;
end;
end;

{ TVisitCounter }

constructor TVisitCounter.Create(XSize, YSize, MaxSumDigits : cardinal);
begin
FCount := 0;
FXSize := XSize;
FYSize := YSize;
FMaxSumDigits := MaxSumDigits;
Seen := TBits.Create;
Seen.Size := XSize * YSize * 2; // Guessing at size needed... DEBUG Needs larger for larger maxSumDigits
end;

destructor TVisitCounter.Destroy;
begin
Seen.Free;
inherited;
end;

procedure TVisitCounter.Visit(x, y: cardinal);
begin
if not Visited(x, y) then
if SumOfDigits(x) + SumOfDigits(y) <= FMaxSumDigits then begin
inc(FCount);
JustVisited(x, y);
Visit(x + 1, y);
Visit(x - 1, y);
Visit(x, y + 1);
Visit(x, y - 1);
end;
end;

function TVisitCounter.Visited(x, y: cardinal): boolean;
begin
{$IFDEF DEBUG}
if pred(x) * FXSize + y > Seen.Size then
RAISE EXCEPTION.CREATE('"SEEN" TBITS NOT LARGE ENOUGH; ASKING FOR ' + INTTOSTR(pred(x) * FXSize + y) +
' BUT SIZE IS ONLY ' + INTTOSTR(SEEN.Size));
{$ENDIF}
result := Seen.Bits[pred(x) * FXSize + y];
end;

procedure TVisitCounter.JustVisited(x, y: cardinal);
begin
Seen.Bits[pred(x) * FXSize + y] := true;
end;
(Reply) (Parent) (Thread)

(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)


leonardo_m
Link:(Link)
Time:2011-09-21 12:28 am (UTC)
On Reddit, with a comment:
http://www.reddit.com/r/programming/comments/kkw3d/simple_ant_puzzle/
(Reply) (Thread)

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