Re [m-dev.] ICFP Contest: simple position reachability inkblot

[Peter Moulder]

Preprocesses the track to find the reachable bit of finishing line.
(Some maps contain unreachable finishing line squares.)

As a simple correctness check, I've made it output the refined
map along with a path corresponding to some notion of shortest path.
(Not euclidean shortest, as is evident from e.g. 5_Car.xpm.)

You may be pained to learn I wrote it in C++.

For use with something like

  mkdir annotated;	\
  for i in *.trk; do	\
    b=`basename $i .trk`;	\
    ./reachability < $i | ./ann-trk2xpm.sh > annotated/$b.xpm; \
  done

ann-trk2xpm.sh:

  #! /bin/sh
  cat <<EOF
  /* XPM */'
  static char *track[] = {
  "1024 768 10 1",
  ".	c #333333",
  "*	c #ffff55",
  "!	c #884400",
  "g	c #00ff00",
  "r	c #ff0000",
  "w	c #ffffff",
  "b	c #0000ff",
  "^	c #000000",
  "|	c #ff8800",
  "=	c #cccc00",
  EOF
  sed '1,2d;s/^/"/;3,769s/$/",/;770s/$/"};/' $1

reachability.cc appended.

pjm.


/* Read in the track, and preprocess it by doing reachability analysis.
 * In particular, get rid of bogus finish lines.
 */
#include <assert.h>
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::vector;

#define HEADER "1024\n768\n"

enum { Y, X, N_DIMS };
typedef unsigned dimT;

static unsigned const height = 768;
static unsigned const width = 1024;

static char const
	reachable_road = '^',
	reachable_finish = '|',
	unseen_road = '.',
	unseen_finish = '!';

static char const barriers[] = {'r', 'g', 'b', 'w'};



class unchecked_pt {
private:
	unsigned coord[2];

private:
	void assert_good() const {
		assert(coord[Y] <= height);
		assert(coord[X] <= width);
	}

public:
	explicit unchecked_pt(unsigned i, unsigned j) {
		coord[Y] = i;
		coord[X] = j;
		assert_good();
	}

	unsigned y() const {
		return coord[Y];
	}

	unsigned x() const {
		return coord[X];
	}

	unsigned get(dimT d) const {
		assert((unsigned) d < N_DIMS);
		return coord[d];
	}
};

static unchecked_pt const len(height, width);

class pt
{
private:
	unsigned coords;

	explicit pt(unsigned const ix)
		: coords(ix)
	{
		assert(ix < width * height);
	}

public:
	pt(pt const &o)
		: coords(o.coords)
		{}

	explicit pt(unsigned i, unsigned j) {
		assert(i < height);
		assert(j < width);
		coords = i * width + j;
		assert(coords < width * height);
	}

	static pt from_ix(unsigned const ix) {
		return pt(ix);
	}

	unsigned y() const {
		return coords / width;
	}

	unsigned x() const {
		return coords % width;
	}

	unsigned get(dimT d) const {
		assert((unsigned) d < N_DIMS);
		return (d == Y ? y() : x());
	}

	unsigned ix() const {
		assert(coords < width * height);
		return coords;
	}
};

static unsigned travelled[height * width];

static unsigned
get_travelled(pt const p) {
	return travelled[p.ix()];
}

static void
set_travelled(pt const p, unsigned t) {
	assert(t != ~0u);
	unsigned &x = travelled[p.ix()];
	assert(x == ~0u);
	x = t;
}

static char track[height * width + 2];

static char
get_track(pt const p) {
	char const ret = track[p.ix()];
	return ret;
}

static void
set_track(pt const &p, char const tr) {
	track[p.ix()] = tr;
}

static unsigned arrived_from[width * height];

static pt
find_start()
{
	unsigned ret_i, ret_j;
	bool found = false;
	for(unsigned i = 0; i < height; ++i) {
		for(unsigned j = 0; j < width; ++j) {
			pt const p(i, j);
			if(get_track(p) == '*') {
				assert(!found);
				ret_i = i; ret_j = j;
				found = true;
			}
		}
	}
	assert(found);
	pt const ret(ret_i, ret_j);
	set_track(ret, unseen_road);
	return ret;
}


static void
find_next_level(unsigned const t, vector<pt> const &curr,
		vector<pt> &next, bool &found_finish, pt &first_finish)
{
	assert(!curr.empty());
	assert(next.empty());
	assert(!found_finish);
	for(vector<pt>::const_iterator ci( curr.begin()), ciEnd(curr.end());
	    ci != ciEnd; ++ci) {
		pt const p(*ci);
		assert(get_travelled(p) == ~0u);
		set_travelled(p, t);
		assert(get_track(p) == reachable_road);

		int offset[N_DIMS];
		/* Iterate over 0,1,-1 so that straight lines are faster. */
		for(offset[Y] = 0; offset[Y] <= 1; offset[Y] = 1 - 2*offset[Y]) {
			unsigned const p2_y = p.y() + offset[Y];
			if(p2_y >= len.y())
				continue;
			for(offset[X] = 0; offset[X] <= 1; offset[X] = 1 - 2*offset[X]) {
				unsigned const p2_x = p.x() + offset[X];
				if(p2_x >= len.x())
					continue;
				pt const p2(p2_y, p2_x);
				switch(get_track(p2)) {
				case unseen_road:
					next.push_back(p2);
					set_track(p2, reachable_road);
					arrived_from[p2.ix()] = p.ix();
					continue;

				case 'r': case 'g': case 'b': case 'w':
					continue;

				case unseen_finish:
					if(offset[X] != 1)
						continue;
					set_track(p2, reachable_finish);
					arrived_from[p2.ix()] = p.ix();
					if(!found_finish) {
						found_finish = true;
						first_finish = p2;
					}
					continue;

				case reachable_road:
				case reachable_finish:
					continue;

				default:
					fprintf(stderr,
						"Unexpected road square `%c'.\n",
						get_track(p2));
					break;
				}
			}
		}
	}
}


/* Change reachable road to '^', and reachable finish to '|'. */
static void
paint_reachable(pt const start, pt &first_finish)
{
	for(unsigned i = 0; i < height; ++i) {
		for(unsigned j = 0; j < width; ++j) {
			pt const p(i, j);
			int const x = get_track(p);
			assert(x != reachable_road);
			assert(x != reachable_finish);
			assert((x == unseen_road)
			       || (x == unseen_finish)
			       || (memchr(barriers, x, sizeof(barriers))
				   != NULL));
		}
	}

	vector<pt> level_a, level_b;
	level_a.push_back(start);
	set_track(start, reachable_road);
	assert(level_a.size() == 1);

	unsigned t = 0;
	memset(travelled, 0xff, sizeof(travelled));
	memset(arrived_from, 0xff, sizeof(arrived_from));
	bool found_finish = false;
	for(;;) {
		level_b.clear();
		find_next_level(t, level_a, level_b, found_finish, first_finish);
		++t;
		if(found_finish)
			break;
		assert(!level_b.empty());

		level_a.clear();
		find_next_level(t, level_b, level_a, found_finish, first_finish);
		++t;
		if(found_finish)
			break;
		assert(!level_b.empty());
	}
}

static void
paint_shortest(pt const &first_finish, pt const &start)
{
	pt curr(first_finish);
	while(curr.ix() != start.ix()) {
		set_track(curr, '=');
		curr = pt::from_ix(arrived_from[curr.ix()]);
	}
}

int main()
{
	char smallbuf[sizeof(HEADER)];

	cin.read(smallbuf, sizeof(HEADER) - 1);
	assert(memcmp(smallbuf, HEADER, sizeof(HEADER) - 1) == 0);
	for(unsigned i = 0; i < 768; ++i) {
		char *track_row = track + i * width;
		assert(track_row + 1025 <= track + sizeof(track));
		track_row[1024] = '\0';
		cin.read(track_row, 1025);
		assert(track_row[1024] == '\n');
	}
	cin.read(smallbuf, 1);
	assert(cin.eof());

	pt const start(find_start());
	pt first_finish(0,0);
	paint_reachable(start, first_finish);
	paint_shortest(first_finish, start);

	cout << HEADER;
	for(unsigned i = 0; i < height; ++i) {
		char const *track_row = track + i * width;
		cout.write(track_row, width);
		cout.put('\n');
	}
}


--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------