Random Walk

using GLib;
using Gee;


static inline int python_modulo(int a, int b) {
    int r = a % b;
    r += ((int) (r != 0) & ((r ^ b) < 0)) * b;
    return r;
}


class CoordinateSystem : Object {
    internal uint[] shape;

    public CoordinateSystem (uint[] shape)
        requires (this.is_valid_shape (shape))
    {
        this.shape = shape;
    }

    static inline bool is_valid_shape (uint[] shape) {
        foreach (var n in shape) {
            if (n < 0) return false;
        }
        return shape.length != 0;
    }

    public inline uint dimensions {
        get { return this.shape.length; }
    }

    public uint size {
        get {
            uint result = 1;
            foreach (var v in this.shape) {
                result *= v;
            }
            return result;
        }
    }

    public bool is_valid_coordinates(uint[] values) {
        if (values.length == this.dimensions) {
            for (var i = 0; i < values.length; ++i) {
                if (values[i] < 0 || values[i] >= this.shape[i]) return false;
            }
            return true;
        } else {
            return false;
        }
    }

    public new Coordinate get (uint index)
        requires (index >= 0)
    {
        var result = new uint[this.shape.length];
        for (int i = 0; i < this.shape.length; ++i) {
            result[i] = index % this.shape[i];
            index /= this.shape[i];
        }
        assert (index == 0);
        return new Coordinate (this, result);
    }

    public Coordinate[] get_sample (uint count)
        requires (count <= this.size)
    {
        var result = new Coordinate[count];
        var selected = new HashSet<uint> ();
        uint j = 0;

        for (var i = 0; i < count; ++i) {
            do {
                j = Random.int_range (0, (int32) this.size);
            } while (j in selected);
            selected.add (j);
            result[i] = this[j];
        }
        return result;
    }
}

class Coordinate : Object {
    CoordinateSystem coordinate_system;
    uint[] coordinates;

    public Coordinate (CoordinateSystem coordinate_system, uint[] coordinates)
        requires (coordinate_system.is_valid_coordinates (coordinates))
    {
        this.coordinate_system = coordinate_system;
        this.coordinates = coordinates;
    }

    public inline int dimensions {
        get { return this.coordinates.length; }
    }

    public bool equals(Coordinate other) {
        if (this.coordinates.length == other.coordinates.length) {
            for (var i = 0; i < this.coordinates.length; ++i) {
                if (this.coordinates[i] != other.coordinates[i]) return false;
            }
            return true;
        } else {
            return false;
        }
    }

    public uint hash () {
        uint x = 0x345678, mult = 100003;
        for (var i = 0; i < this.coordinates.length; ++i) {
            x = (x ^ this.coordinates[i]) * mult;
            mult += 82520 + 2 * i;
        }
        return x + 97531;
    }

    public void move(int[] delta)
        requires (delta.length == this.dimensions)
    {
        for (var i = 0; i < delta.length; ++i) {
            this.coordinates[i] =
                python_modulo (((int) this.coordinates[i] + delta[i]),
                    (int) this.coordinate_system.shape[i]);
        }
    }
}

class Walker : Object {
    public Coordinate coordinate;
    public uint id;

    public Walker (Coordinate coordinate, uint id) {
        this.coordinate = coordinate;
        this.id = id;
    }

    public void random_move() {
        var delta = new int[this.coordinate.dimensions];
        delta[Random.int_range (0, this.coordinate.dimensions)] =
            Random.boolean () ? -1 : 1;
        this.coordinate.move(delta);
    }
}


class WalkerCounter : Object {
    public Walker walker;
    public uint count = 0;

    public WalkerCounter(Walker walker) {
        this.walker = walker;
    }
}


class Simulation : Object {
    Walker[] walkers;

    public Simulation (Walker[] walkers) {
        this.walkers = walkers;
    }

    public Simulation.with_randomly_placed_walkers (
        CoordinateSystem coordinate_system, uint count
    ) {
        var walkers = new Walker[count];
        var coordinates = coordinate_system.get_sample (count);
        for (var i = 0; i < count; ++i) {
            walkers[i] = new Walker(coordinates[i], i);
        }
        this (walkers);
    }

    public uint size {
        get { return this.walkers.length; }
    }

    public void step () {
        var coordinate2walkers = new HashMap<Coordinate, WalkerCounter> (
            Coordinate.hash, (EqualFunc) Coordinate.equals);
        foreach (var walker in this.walkers) {
            walker.random_move();

            var walker_counter = coordinate2walkers[walker.coordinate];
            if (walker_counter == null) {
                walker_counter = new WalkerCounter (walker);
                coordinate2walkers[walker.coordinate] = walker_counter;
            }
            walker_counter.count += 1;
        }
        var i = 0;
        foreach (var walker_counter in coordinate2walkers.values) {
            if (walker_counter.count == 1) {
                this.walkers[i++] = walker_counter.walker;
            }
        }
        this.walkers.resize (i);
    }
}

static int main (string[] args) {
    var simulation = new Simulation.with_randomly_placed_walkers (
        new CoordinateSystem ({100, 100}), 500);
    for (var i = 0; i < 100; ++i) {
        simulation.step ();
        stdout.printf ("%u walkers left in step %d\n", simulation.size, i);
        if (simulation.size <= 1) break;
    }
    return 0;
}