OMG!! I ranked in the top 1000 for day 19:
It was an interesting challenge, which I solved in a very interesting (and potentially unusual) way.
The part 2 twist is really twisted, too. He pretty much tells you you’ll have to do something specific to the problem as the general approach would require way too much work.
The presumed logical approach to dealing with this problem would be a state machine… you have states you enter into and leave via rule numbers. And with some back tracking (read recursion) you could probably get that approach to work for part 1. I thought of that before deciding my approach, and that is basically what regex does for you… it builds a state machine with backtracking support. So I figure I would have my code translate the rules into a regex string and let the regex pattern matcher do all the work. That worked great for part 1, here’s a sample of the output:
Number of rules: 130
regexStr: (a((b(a((a(ba|ab)|b(bb|aa))b|(a(aa|b(a|b))|bba)a)|b((bab|(a(a|b)|ba)a)b|(baa|(aa|ba)b)a)) … very truncated …
Number of messages: 458
Part 2 throws in a serious twist thou… the expressions can now be self-referential… My approach for this was kind of ugly, but it allowed me to trap out the changes needed without having to rewrite all my code:
private void _buildRecursive(final StringBuilder sb, final int ruleNumber)
{
if (inRule2Mode)
{
if (ruleNumber == 8)
{
handlePart2Rule8(sb);
return;
}
if (ruleNumber == 11)
{
handlePart2Rule11(sb);
return;
}
}
then all I had to do was figure out what changes to make to handle the two new rules. For one, it would match inputs like a, aa, aaa, aaaa, aaaaa, and so on, so a simple (a+) matches one more more a’s. For the second one, that was harder. Here you want to match patters where there are the same number of a’s as b’s like: ab aabb aaabbb aaaabbbb and so on. General regex is not well equipped for this, you can say a+b+ but that would match a different number of a’s and b’s. (I did try to cheat with this approach, but I generated a wrong (too high) number, and also got the warning about how it interestingly matched someone else’s answer.)
The only way I could think to handle this in regex was to make pretty long set of specific rules specifying the numbers. So I generated a regex containing (ab|a{2}b{2}|a{3}b{3}|a{4}b{4}|a{5}b{5}| … and had to decide how high to go. I stopped at 20, which was apparently enough for this problem.
Here’s my main code:
final RuleWrangler rw = new RuleWrangler();
final RuleReader rr = new FileRuleReader(FILE);
int numberOfRules = 0;
while (rr.isMoreInput())
{
final String rule = rr.getNextRule();
numberOfRules++;
rw.addRule(rule);
}
System.out.println("Number of rules: " + numberOfRules);
final Pattern p1 = rw.getMasterPattern(0);
final MessageReader mr = new FileMessageReader(FILE);
int numberOfMessages = 0;
int numberOfValidMessages = 0;
while (mr.isMoreInput())
{
final String message = mr.getNextMessage();
numberOfMessages++;
final Matcher m = p1.matcher(message);
if (m.matches()) numberOfValidMessages++;
}
System.out.println("Number of messages: " + numberOfMessages);
System.out.println("Part 1: " + numberOfValidMessages);
rw.toggleToPart2Mode();
final Pattern p2 = rw.getMasterPattern(0);
final MessageReader mr2 = new FileMessageReader(FILE);
int numberOfValidMessages2 = 0;
while (mr2.isMoreInput())
{
final String message = mr2.getNextMessage();
final Matcher m = p2.matcher(message);
if (m.matches()) numberOfValidMessages2++;
}
System.out.println("Number of messages: " + numberOfMessages);
System.out.println("Part 2: " + numberOfValidMessages2);
I must have been getting pretty tired by then, but I finally got a clue and decided to input his provided example as a unit test and I needed the debugger to see my stupidity.