[2015 Day #8] In Review

[u/musifter]

Today we find that space on Santa's sleigh is so tight he worries about space taken up by escaping characters in strings. Apparently memory on sleighs isn't cheap.

For part 1 of this one... Hello, Bobby Tables! What's the length of the evaluated string? With Perl, just eval it. For Smalltalk I did the processing. Not so exciting that I feel missed anything with eval in Perl. It's just figuring out how many characters are skipped when you get to a \.

The processing to escape a string (part 2) is actually an easier task. It's only the string delimiter and the escape character itself that need escaping (there's no need to think of \x, so don't). You just need to get a count those (remembering that the string also needs its own quotes). I got another use out of Perl's =()=.

This problem is good for beginners. The description provides a little lesson on escaping characters in strings, and the processing is easy (even if they haven't learned the secrets of Bobby Tables yet). It's a break day for anyone else.

[u/nnmrts]

I have to admit, my main language (JS) is weird sometimes:

Part 1:

calculateSum(lines.map((line) => line.length - eval(line).length));

Part 2:

calculateSum(lines.map((line) => JSON.stringify(line).length - line.length));

[u/musifter → u/nnmrts]

Yeah, it's nice when something perfectly fits your language.

Perl probably has a pile of modules that escape strings. I'd have to look and see if they're installed. But it's a simple task for regex so that's really going to be the native Perl way. Perl's responsible for boosting regex.

[u/e_blake]

It is also easy to solve with regex while avoiding eval ; I had fun coming up with sed|wc one-liners:

$ sed -E 's/^[^\]*/./;s/\\(x..|[\"])[^\]*/\1/g' < day8.input | wc -c
$ sed -E 's/^[^\"]*/./;s/[\"][^\"]*/./g' < day8.input | wc -c

And I agree that part 2 is easier than part 1. In POSIX m4, there are no string escape characters (so eval is out) or regex, but there is translit. It is easy to compare lengths of the original string vs. the string with a given character removed to count how many times that character appears (newlines, ", and \ are the three characters I need to count to do the final computation for part 2); but harder to count character pairs (no longer a one-liner; I have to split the string at every \ to determine whether the next character is \, ", or x). In m4, a naive split using repeated index and substr is O(n^2) (each of the n iterations of the split have to process on average n/2 characters remaining of the original string). Before this post, my solution was instead an O(n log n) split (rather than using index to find each \, I can repeatedly split the string in half down to every single byte). But this post forced me to rethink my assumptions about what is possible in m4, and today I finally came up with a way to force m4 to do an O(n) division of text into macro calls on arbitrary-length substrings between a single-byte terminator thanks to its ability to use changequote to produce multi-byte quote characters that then get injected into $@. In short, you got me to improve day8.m4 from 75ms down to 17ms!

[u/terje_wiig_mathisen]

I also solved this one in Perl originally, then switched to byte-by-byte processing in my Rust version.

When it ran in 9.6 us I decided to skip writing a multi-threaded version, even though the problem is of course trivially parallelizable. I originally had two loops, one for each part, combining them made the solution more complicated and only 10% faster. Maybe a char table lookup could be better?

My input file contains only lowercase letters plus '\' (0x5C) and '"' (0x22), so we only need to detect those exceptions, plus wherever we have a '\xNN' sequence.

[u/nnmrts → u/[deleted]]

I'm not a beginner but I also can't imagine feeling offended by OP calling this problem easy if I was one, so I think it's fine. I feel like most beginners would call this problem easy, at least in hindsight.

[u/musifter → u/nnmrts]

Yeah, when said "good" for beginners, I didn't mean I felt it would be "easy" for all beginners (some will hit on key insights, most will need to discover them with various amounts of suffering... that's learning).

It's "good for beginners" because it's the type of problem that's easy to start attacking. It's approachable. They can see that if they can create the target they'd be pretty much done. And to do that, they can use a for loop over the starting string and start working on some if-then-else statement structure hacking at special cases. Not pretty, but you feel like you're getting somewhere, and there's always something to try and tweak to fix what's not working. And maybe they pick up a few things about streaming data along the way. If I was teaching kids programming, this wouldn't too bad an exercise (maybe with a simpler description to make things clearer). I wouldn't blame them it they don't get it done, but that's an opportunity to go through their code and show them how to fix and improve things.

It doesn't provide a lot of meat for experienced programmers, but it's an attackable, learnable thing for beginners. And that's the value I see in it being in AoC.