Random D geekout
H. S. Teoh
hsteoh at quickfur.ath.cx
Fri Apr 20 17:27:07 PDT 2012
On Fri, Apr 20, 2012 at 04:25:30PM +0200, ixid wrote:
> As a D learner this thread is very interesting. It would be great to
> maintain it with a polished and error catching version that
> incorporates people's tweaks.
What I posted was a pared-down simplified version of the actual code I
was working on. I've since done a few more iterations on it, and I
thought I should perhaps post the entire code here as a complete example
of a relatively simple but non-trivial D program that does something
useful.
Some points of note in the code:
- I've factored out the code that does the AA lookups, because I found
myself needing nested blocks in the input file. So the parseBlock()
function does the real work, while the input file format is
essentially specified by the loadSpec() function in the form of a
nested AA structure containing delegates that implement parsing. I
think I like this much better than my original version; it's much more
reusable, and arguably easier to read.
- Arguably, parseConds can be put into loadSpec() as well, but I'm
anticipating needing to parse conditions from different places in the
future, so it's a good idea to put encapsulate it as a separate
function.
- Exceptions that occur during parsing are caught by code that iterates
over lines, and exception messages are prefixed with the offending
filename/line number. This is done in parseBlock(), and it can handle
exceptions coming from anywhere (such as deeply nested inside one of
the parsing delegates). Prefixed exceptions are translated into a
different exception type, so that we don't prefix the same message
more than once (parseBlock is called reentrantly by some of the
delegates, so an exception occurring deep inside the call stack may
traverse several instances of parseBlock during stack unwinding).
- I wrote a simple template for switching between regex() and ctRegex!()
via a -version flag to the compiler. The regexes have also been
hoisted out of inner loops, so that it doesn't introduce too much
unnecessary overhead (besides, they're now compile-time evaluated so
any such remaining overhead should be minimal). Gotta love D's CTFE
capabilities!
- Another D coolness: finding the length of the longest name in a People
array, in a single line of code:
auto maxnamelen = reduce!"max(a,b.name.length)"(1, spec.people);
- To my great embarrassment, I didn't write any unittests. I should go
to a corner and weep now.
- I'm sure that there's still lots of room for improvement; I'm by no
means an expert in D. So criticisms, flames, fanmail, etc., are all
welcome. ;-)
About the program itself:
The purpose of the program is to automatically assign M people out of a
pool of N people to a recurring event on a rotating basis. For example,
generate a toilet-scrubbing rotation schedule every Saturday for N
roommates, or a guard duty schedule of 2 people each, etc..
While the basic problem is trivial, this program supports conditions and
exclusive tags.
- Conditions basically indicate when a particular person is not
available (e.g., person is away and won't be back till a certain date,
person has conflicting event at that time, preplanned vacation,
preplanned sickness, etc.).
- Exclusive tags basically say that two people having the same tag are
not to be assigned to the same slot (e.g., they have personality
conflicts and shouldn't be put together alone, or they're involved
with another event that can only spare 1 person at a time, etc.).
- There's also a mixup parameter that lets you introduce some randomness
into the rotation (for example, once in a while pair you up with a
different person on guard duty, just for some variety). This is to
break the tedium of the same old people being assigned together all
the time.
- Currently the output is just plain ole text. But it's not hard to add
the capability of outputting, say, iCalendar format, HTML, XML, JSON,
or whatever your favorite overhyped format is. All you need is to
appropriately format the contents of the 'assigned' array and the date
'dt' in genSched().
//----------------------------------snip---------------------------------
/**
* Simple program to schedule assignments of N people to M slots on a
* rotational basis.
*/
import std.algorithm;
import std.array;
import std.conv;
import std.datetime;
import std.random;
import std.regex;
import std.stdio;
import std.string;
//version = CtRgx;
template Re(string re) {
version(CtRgx) {
enum Re = ctRegex!re;
} else {
static Re = regex(re);
}
}
struct ParseCtxt(R) {
string fname;
R lines;
int linenum;
}
class ParseException : Exception {
this(string msg) {
super(msg);
}
}
class Condition {
abstract bool opCall(Date dt);
}
class SingleDateCond : Condition {
Date dt;
this(Date dt) { this.dt = dt; }
}
class DateRangeCond : Condition {
Date start, end;
this(Date start, Date end) {
this.start = start;
this.end = end;
}
}
class NotCond : DateRangeCond {
this(Date single_date) { super(single_date, single_date); }
this(Date start, Date end) { super(start, end); }
override bool opCall(Date dt) {
return dt < this.start || dt > this.end;
}
}
class AfterCond : SingleDateCond {
this(Date dt) { super(dt); }
override bool opCall(Date dt) {
return dt > this.dt;
}
}
struct Person {
string name, phone, email;
bool[string] tags;
Condition[] conditions;
bool eligible(Date dt) {
foreach (cond; conditions) {
if (!cond(dt))
return false;
}
return true;
}
}
struct SchedSpec {
string name;
Date startdate, enddate;
Duration period;
int ppl_per_event;
int mixup;
Person[] people;
// People tagged with a tag in this list will not be scheduled together
bool[string] excl_tags;
bool[string] getExclTags(Person candidate) {
bool[string] tags;
foreach (tag; candidate.tags.keys) {
if (!(tag in excl_tags))
continue;
tags[tag] = true;
}
return tags;
}
}
alias void delegate(string key, string value) attrDg;
alias void delegate(string key) blockDg;
void parseBlock(R)(ref ParseCtxt!R ctxt, attrDg[string] attrDefs,
blockDg[string] blockDefs=null)
{
attrDg invalidAttr = delegate(string key, string value) {
throw new Exception("Unknown attribute '%s'".format(key));
};
blockDg invalidBlock = delegate(string key) {
throw new Exception("Unrecognized block '%s'".format(key));
};
auto blankLineRe = Re!`^\s*(#.*)?$`;
auto attrRe = Re!`^\s*(\w+)\s+(.*)$`;
auto blockRe = Re!`^\s*(\w+)\s*:\s*$`;
auto endRe = Re!`^\s*end\s*$`;
while (!ctxt.lines.empty) {
auto line = ctxt.lines.front();
ctxt.linenum++;
debug writefln("[%d]>>%s$", ctxt.linenum, line);
try {
if (match(line, blankLineRe)) {
ctxt.lines.popFront();
continue; // skip comments & empty lines
} else if (auto m = match(line, attrRe)) {
auto key = m.captures[1].idup;
auto value = m.captures[2].idup;
attrDefs.get(key, invalidAttr)(key, value);
} else if (auto m = match(line, blockRe)) {
auto key = m.captures[1].idup;
ctxt.lines.popFront();
blockDefs.get(key, invalidBlock)(key);
} else if (match(line, endRe)) {
return;
} else {
throw new Exception("Unrecognized spec: %s"
.format(line));
}
} catch(ParseException e) {
throw e;
} catch(Exception e) {
throw new ParseException("%s:%d: %s"
.format(ctxt.fname, ctxt.linenum, e.msg));
}
ctxt.lines.popFront();
}
}
Date parseDate(string dts) {
auto dateRe = Re!`^\s*(\d{4})-(\d\d)-(\d\d)\s*$`;
auto m = match(dts, dateRe);
if (!m)
throw new Exception("Invalid date '%s'".format(dts));
return Date(to!int(m.captures[1]), to!int(m.captures[2]),
to!int(m.captures[3]));
}
Date[2] parseDateRange(string str) {
auto rangeRe = Re!`^\s*(\d+-\d+-\d+)(?:\s+to\s+(\d+-\d+-\d+))?`;
auto m = match(str, rangeRe);
if (!m)
throw new Exception("Invalid date range '%s'".format(str));
auto start = parseDate(m.captures[1]);
auto end = (m.captures.length >= 2 && m.captures[2].length > 0) ?
parseDate(m.captures[2]) : start;
return [start, end];
}
Duration parseDur(string durs) {
auto daysRe = Re!`^\s*(\d+)\s*days\s*$`;
auto weeksRe = Re!`^\s*(\d+)\s*weeks\s*$`;
if (auto m = match(durs, daysRe)) {
return dur!"days"(to!int(m.captures[1]));
} else if (auto m = match(durs, weeksRe)) {
return dur!"weeks"(to!int(m.captures[1]));
}
throw new Exception("Unrecognized duration '%s'".format(durs));
}
void parseConds(C)(ref C ctxt, ref Condition[] conds) {
parseBlock(ctxt, [
"after": (string key, string value) {
conds ~= new AfterCond(parseDate(value));
},
"not": (string key, string value) {
auto range = parseDateRange(value);
conds ~= new NotCond(range[0], range[1]);
}
]);
}
SchedSpec loadSpec(string fname) {
auto specfile = File(fname, "r");
scope(exit) specfile.close();
alias typeof(specfile.byLine()) L;
auto ctxt = ParseCtxt!L(fname, specfile.byLine());
SchedSpec spec;
parseBlock(ctxt, [
"name": (string key, string value) {
spec.name = value.idup;
},
"startdate": (string key, string value) {
spec.startdate = parseDate(value);
},
"enddate": (string key, string value) {
spec.enddate = parseDate(value);
},
"period": (string key, string value) {
spec.period = parseDur(value);
},
"ppl_per_event": (string key, string value) {
spec.ppl_per_event = to!int(value);
},
"mixup": (string key, string value) {
spec.mixup = to!int(value);
},
"exclusive_tags": (string key, string value) {
foreach (tag; splitter(value, Re!`\s+`)) {
spec.excl_tags[tag] = true;
}
}
], [
"person": (string key) {
Person person;
parseBlock(ctxt, [
"name": (string key, string value) {
person.name = value;
},
"phone": (string key, string value) {
person.phone = value;
},
"email": (string key, string value) {
person.email = value;
},
"tags": (string key, string value) {
foreach (tag; splitter(value,
Re!`\s+`))
{
person.tags[tag] = true;
}
}
], [
"conditions": (string key) {
parseConds(ctxt, person.conditions);
}
]);
spec.people ~= person;
}
]);
return spec;
}
void summarize(SchedSpec spec) {
writefln("Specification '%s':", spec.name);
writefln("\tStart date: %s", spec.startdate);
writefln("\tEnd date: %s", spec.enddate);
writefln("\tRepeat period: %s", spec.period);
writefln("\tPeople per event: %d", spec.ppl_per_event);
writefln("\tTotal people: %d", spec.people.length);
}
enum string[] monthAbbrev = [
"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct",
"Nov", "Dec"
];
void genSched(SchedSpec spec) {
//summarize(spec);
Person[] queue = spec.people[0..$];
randomShuffle(queue);
auto maxnamelen = reduce!"max(a,b.name.length)"(1, spec.people);
Date dt = spec.startdate;
while (dt <= spec.enddate) {
Person[] assigned;
bool[string] excl_tags;
foreach (i; 0 .. spec.ppl_per_event) {
// Find eligible person for assignment
bool eligible(Person p, Date dt) {
if (!p.eligible(dt))
return false;
// Check for exclusive tag conflicts
auto ptags = spec.getExclTags(p);
foreach (tag; ptags.byKey()) {
if (tag in excl_tags)
return false;
}
return true;
}
auto j = countUntil!eligible(queue, dt);
if (j == -1)
throw new Exception("No eligible assignees "~
"found on %s!".format(dt));
// Move person into assigned list
assigned ~= queue[j];
replaceInPlace(queue, j, j+1, cast(Person[])[]);
// Add person's exclusive tags to the current set of
// exclusive tags.
foreach (tag; spec.getExclTags(assigned[$-1]).byKey())
{
excl_tags[tag] = true;
}
}
// Put assigned people back to the end of the queue, but with a
// probability of permuting the order so that we get a mix of
// different groupings every now and then.
foreach (p; assigned) {
insertInPlace(queue, queue.length -
uniform(0, spec.mixup+1), [p]);
}
writef("%04d %s %2d:", dt.year, monthAbbrev[dt.month-1], dt.day);
foreach (p; assigned) {
writef("\t%-*s", maxnamelen, p.name);
}
writeln();
dt += spec.period;
}
}
int showhelp(string progname) {
writefln("Usage: %s [inputfile]", progname);
return 1;
}
int main(string[] args) {
assert(args.length >= 1);
try {
if (args.length <= 1)
return showhelp(args[0]);
auto inputfile = args[1];
auto spec = loadSpec(inputfile);
genSched(spec);
} catch(Exception e) {
writefln("Error: %s", e.msg);
}
return 0;
}
//----------------------------------snip---------------------------------
T
--
Guns don't kill people. Bullets do.
More information about the Digitalmars-d
mailing list