// CS 509 Advanced Programming II
// Spring 2003
// Programming Assignment 4 Example Solution
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <string>
#include <sys/time.h>
#include <unistd.h>
#include <cassert>
#include <iomanip>
#include <sstream>
#include "maximum-placement.h"
#include "debugp.h"
// Towns are printed in three-character fields; lines are 80 characters long.
const unsigned
fwidth = 3,
lwidth = 80;
// The function that finds maximal placements.
typedef uvec (* mp_fun)(const umat &);
// Deja vu, c++ style.
static void check_times(time_t, time_t);
static void run_test(bool, const umat &);
static void print_time(time_t);
static void print_times(const char * const, time_t, time_t);
static uvec timed_run(mp_fun, const umat &, time_t &);
std::ostream & operator << (std::ostream &, const uvec &);
std::ostream & operator << (std::ostream &, const umat &);
static void print_emsg(const char * const);
static umat gen_map(void);
static bool connected(const umat &, unsigned, unsigned);
static void one_road_out(umat &);
static void place(const umat &, uvec, uvec &, unsigned);
static bool ok(const umat &, const uvec &, unsigned &, unsigned &);
static void map_ok(const umat &);
static void
check_answer(const umat & map, const uvec & answer, const uvec & check) {
// Determine if answer is a valid compared to check; die with an error
// message if it isn't.
const unsigned ems = 100;
char emsg[ems];
debugp(8) << "computed answer = " << answer
<< "\ncheck answer = " << check
<< "\nmap =\n" << map << "\n";
if (answer.size() > map.size()) {
snprintf(emsg, ems, "found %u town%s; the map only has %u town%s",
answer.size(), (answer.size() == 1 ? "" : "s"),
map.size(), map.size() == 1 ? "" : "s");
print_emsg(emsg);
}
if (answer.size() < check.size()) {
snprintf(emsg, ems, "found %u town%s; the check found %u town%s",
answer.size(), (answer.size() == 1 ? "" : "s"),
check.size(), check.size() == 1 ? "" : "s");
print_emsg(emsg);
}
unsigned t1, t2;
if (!ok(map, answer, t1, t2)) {
std::ostringstream oss;
oss << "placed witness-criminals in adjacent towns "
<< t1 << " and " << t2
<< ".\n\nComputed placement:\n" << answer << "\n"
<< "Check placement:\n" << check << "\n"
<< "Map:\n" << map;
print_emsg(oss.str().c_str());
}
assert(ok(map, check, t1, t2));
}
static uvec
check_mp(const umat & map) {
// Return a maximal witness-criminal placement for the given map.
uvec towns;
place(map, uvec(), towns, map.size());
return towns;
}
static void
check_times(time_t answert, time_t checkt) {
// Compare an answer time to a check time and print a message if the answer
// time's too slow compared to the check time. Return true iff the time's
// are good.
if (answert > 2*checkt) {
print_times("\n!!! ", answert, checkt);
exit(EXIT_FAILURE);
}
}
static bool
connected(const umat & map, unsigned i, unsigned j) {
// Return true iff the given towns are connected by a road in the given map.
debugp(2) << "i = " << i << ", j = " << j << ", map size = " << map.size()
<< "\n";
assert((i != j) and (map.size() > i) and (map.size() > j));
const uvec::const_iterator e = map[i].end();
return std::find(map[i].begin(), e, j) != e;
}
static umat
gen_map(void) {
// Return a randomly generated map.
int towns = (random() % 50) + 1;
umat map(towns);
debugp(1) << "Generate a " << towns << " towns map.\n";
for (unsigned i = std::max(1, towns/4); i > 0; i--) {
one_road_out(map);
debugp(1) << "intermediate map is\n" << map << "\n";
}
debugp(1) << "final map is\n" << map << "\n";
map_ok(map);
return map;
}
int
main(int argc, char * argv[]) {
bool telltime = false;
unsigned seed = getpid();
int c;
extern char *optarg;
extern int optind;
while ((c = getopt(argc, argv, "ts:d:")) != EOF)
switch (c) {
case 't':
telltime = true;
break;
case 's':
seed = atoi(optarg);
break;
case 'd':
debugp_flags = atoi(optarg);
break;
case '?':
std::cerr << "Command format is \"" << argv[0]
<< " [-t] [-sn] [-dn]\".\n";
return EXIT_FAILURE;
default:
assert(!"getopt() went berserk");
}
if (optind != argc) {
std::cerr << "Command format is \"" << argv[0]
<< " [-t] [-sn | -nn]\".\n";
return EXIT_FAILURE;
}
srandom(seed);
check_mp(gen_map());
for (unsigned i = 0; i < 5; i++)
run_test(telltime, gen_map());
}
// A functor that returns false iff town t is larger than the number of towns
// in a map.
struct bad_town {
const unsigned max;
bad_town(unsigned t) : max(t) { }
bool operator () (unsigned t) {
return t >= max;
}
};
static void
map_ok(const umat & map) {
// Check the given map for correctness: no self-loops, all towns legal, and
// at most one road between any two towns. Die with an error if the check
// fails.
for (unsigned i = 0; i < map.size(); i++) {
const uvec::const_iterator e = map[i].end();
uvec towns(map[i]);
if (std::find(map[i].begin(), e, i) != e) {
std::cerr << "Town " << i << " has a road to itself.\n";
std::cerr << "Map = \n" << map << "\n";
abort();
}
uvec::const_iterator
t = std::find_if(map[i].begin(), e, bad_town(map.size()));
if (t != e) {
std::cerr << "Town " << i << " has a road to a bad town " << *t << ".\n";
std::cerr << "Map = \n" << map << "\n";
abort();
}
std::sort(towns.begin(), towns.end());
t = std::adjacent_find(towns.begin(), towns.end());
if (t != towns.end()) {
std::cerr << "Town " << i << " has duplicate roads to town "
<< *t << ".\n";
std::cerr << "Map = \n" << map << "\n";
abort();
}
}
}
static bool
ok(const umat & map, const uvec & towns, unsigned & t1, unsigned & t2) {
// Return true if the given set of towns is a legal placement relative to the
// given map. If it's not, store the two offending towns in the given
// references.
const uvec::const_iterator e = towns.end();
for (uvec::const_iterator i = towns.begin(); i != e - 1; i++)
for (uvec::const_iterator j = i + 1; j != e; j++) {
const uvec & adjacent = map[*i];
const uvec::const_iterator tp =
std::find(adjacent.begin(), adjacent.end(), *j);
if (tp != adjacent.end()) {
t1 = *i;
t2 = *tp;
return false;
}
}
return true;
}
static void
one_road_out(umat & map) {
// Make sure each town is connected to at least one other town.
uvec v(map.size());
unsigned i;
for (i = 0; i < v.size(); i++)
v[i] = i;
std::random_shuffle(v.begin(), v.end());
for (i = 0; i < v.size() - 1; i++)
if (v[i] == i)
std::swap(v[i], v.back());
if (v.size() - 1 == v.back())
v.pop_back();
for(i = 0; i < v.size(); i++)
if (!connected(map, i, v[i])) {
map[i].push_back(v[i]);
map[v[i]].push_back(i);
}
}
std::ostream &
operator << (std::ostream & os, const uvec & uv) {
// Print uv to the output stream os, returning os.
const unsigned flds = lwidth/fwidth;
for (unsigned i = 0; i < uv.size(); i++) {
if ((i > 0) && ((i % flds) == 0))
os << '\n';
os << std::setw(fwidth) << uv[i];
}
return os;
}
std::ostream &
operator << (std::ostream & os, const umat & um) {
// Print um to the output stream os, returning os.
unsigned i;
for (i = 0; i < um.size(); i++)
os << std::setw(fwidth) << i << ": " << um[i] << '\n';
return os;
}
static void
place(const umat & map, uvec current, uvec & best, unsigned level) {
// Compute a maximum placement over the given map; storing the towns in the
// placement in the given vector. Only the first level towns in the map are
// considered; best contains the best placement found so far.
if (level-- + current.size() > best.size()) {
// Assume the town level isn't part of the solution and see what happens.
place(map, current, best, level);
// Now assume the town level is part of the solution.
current.push_back(level);
unsigned t1, t2;
if (ok(map, current, t1, t2)) {
// The solution with the town level is valid; remember the solution if
// it's larger than the current best solution.
if (best.size() < current.size())
best = current;
// Now try to extend the solution with one of the remaining unconsidered
// towns.
place(map, current, best, level);
}
}
}
static void
print_emsg(const char * const emsg) {
// Print to std-err the error message given in emsg, then die.
std::cerr << "\n!!! Computed maximal placement " << emsg << ".\n";
exit(EXIT_FAILURE);
}
static void
print_time(time_t t) {
// Convert the micosecond time interval t into a conveniently small number
// and print it to std-err.
if (t < 1000)
fprintf(stderr, "%5u usec", static_cast<unsigned>(t));
else if (t < 100000)
fprintf(stderr, "%5.1f msec", static_cast<double>(t)/1000.0);
else
fprintf(stderr, "%5.1f sec", static_cast<double>(t)/1000000.0);
}
static void
print_times(const char * const prefix, time_t answert, time_t checkt) {
// Compare an answer time to a check time and print a message if the answer
// time's too slow compared to the check time. Return true iff the time's
// are good.
fprintf(stderr, "%sComputed maximum-placement() time is", prefix);
print_time(answert);
fprintf(stderr, " vs.\ncheck maximum-placement() time ");
print_time(checkt);
fprintf(stderr, " (x%3.1f slower than check time).\n",
static_cast<double>(answert)/static_cast<double>(checkt));
}
static void
run_test(bool telltime, const umat & map) {
// Feed map to the two maximum-placement procedures, and compare the results.
// If telltime is true, print the execution times for each mp procedure.
debugp(4) << "test map:\n" << map << "\n";
time_t answert, check_answert;
const uvec
check_ans = timed_run(check_mp, map, check_answert),
ans = timed_run(maximum_placement, map, answert);
debugp(4) << "map size = " << map.size()
<< ", answer size = " << ans.size()
<< ", check size = " << check_ans.size() << ".\n";
if (telltime)
print_times("", answert, check_answert);
check_answer(map, ans, check_ans);
check_times(answert, check_answert);
}
static uvec
timed_run(mp_fun mf, const umat & map, time_t & et) {
// Run the maximum-placement procedure mf against map, returning the result
// returned by mf. Also return in et the execution time in usecs.
struct timeval s, e;
gettimeofday(&s, NULL);
const uvec a = (* mf)(map);
gettimeofday(&e, NULL);
if (s.tv_sec < e.tv_sec) {
e.tv_sec--;
e.tv_usec += 1000000;
}
et = (e.tv_sec - s.tv_sec)*1000000 + (e.tv_usec - s.tv_usec);
return a;
}
static char
revision[] = "$Revision: 1.9 $",
date[] = "$Date: 2003/03/23 21:36:32 $";
syntax highlighted by Code2HTML, v. 0.9