Advent of Code 2017, Day 1: Sum of digits matching the next digit (circular list)

Question

I haven't used C++ for quite a while and wanted to practice a bit, so I decided to start simple and work through the Advent of Code 2017.

This is my solution to Part 1 of the Day 1 exercise "Inverse Captcha":

The captcha requires you to review a sequence of digits (your puzzle input) and find the sum of all digits that match the next digit in the list. The list is circular, so the digit after the last digit is the first digit in the list.

For example:

• 1122 produces a sum of 3 (1 + 2) because the first digit (1) matches the second digit and the third digit (2) matches the fourth digit.
• 1111 produces 4 because each digit (all 1) matches the next.
• 1234 produces 0 because no digit matches the next.
• 91212129 produces 9 because the only digit that matches the next one is the last digit, 9.

My program works as follows:

1. Read one line from stdin
2. Convert the line character-wise to a vector of decimal digits
3. Calculate the sum of matching digits
4. Write the result to stdout

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
// Convert the first line of the input stream to a vector of digits.
std::vector<int> read_digits(std::istream& input) {
 std::string line;
 std::getline(input, line);
 std::vector<int> digits(line.size());
 std::transform(
 std::cbegin(line), std::cend(line), std::begin(digits),
 [](char c) { return c - '0'; }
 );
 return digits;
}
// Return the sum of all digits in the list that match the next digit
// (the first digit is the "next" digit of the last digit).
int reverse_captcha(const std::vector<int>& digits) {
 int sum = 0;
 for (auto p = std::begin(digits); p != std::end(digits); p++) {
 auto next_p =
 (std::next(p) == std::end(digits)) ?
 std::begin(digits) : std::next(p);
 if (*p == *next_p) sum += *p;
 }
 return sum;
}
int main() {
 std::cout << reverse_captcha(read_digits(std::cin)) << '\n';
}

I'm compiling it with clang++-4.0 -std=c++14. I'm not sure if I actually use features of the newest standard, but I don't want to restrict myself to older versions.

Here are a few things I'm particularly curious about:

• How can I separate iterating over the pairs of digits from calculating their sum if the pairs are equal? If I were using Python I would write one or two small generator functions, but I don't know yet if there is an equally simple way to do this in C++, or if this would become overkill.

• Is there an elegant way to avoid the extra step of constructing a string line before creating the vector of digits?

• Using - '0' for converting char → int feels like a hack to me, is there really no purpose-built function for this? (I'm used to int('5') → 5 from Python)

• Incomputable: Actually you could write return {std::istream_iterator<char>{}, {}}; in read_digits. If I remember correctly, constructor should not complain.
• mkrieger1: @Incomputable Could you elaborate? Where would I incorporate input (or line?) and where would I put the conversion from char('5') to int(5)?
• mkrieger1: Oh I think I see what you mean, but wouldn't that only work on whitespace-delimited input?
• Incomputable: No. Reading char never skips anything, and reads one character from input stream.
• Incomputable: Actually you don't need to copy anything into anything. You can create an iterator from input stream and work on that. Just save the first and the previous characters. IMO not a big gain though.

Answer 1

I think std::rotate can lead to a somewhat simpler approach:

1. get the input
2. create a copy
3. rotate the copy by one element
4. Accumulate the sum of elements that match between the two

Code might look something on this general order:

int sum_matching(std::vector<int> const &digits) {
 std::vector<int> copy{digits};
 std::rotate(copy.begin(), copy.begin()+1, copy.end());
 int sum = 0;
 for (int i=0; i<digits.size(); i++)
 if (digits[i] == copy[i])
 sum += digits[i];
 return sum;
}

I'm pretty sure you could hijack std::inner_product to do that final loop, but given its name, that would be misleading, so probably better avoided. On the other hand, if your compiler includes all the latest C++17 goodness, you could use std::transform_reduce though:

int main() {
 std::vector<int> inputs{1, 2, 3, 3, 1};
 std::vector<int> copy{inputs};
 std::rotate(copy.begin(), copy.begin()+1, copy.end());
 int result = std::transform_reduce(inputs.begin(), inputs.end(), 
 copy.begin(), 
 0,
 [](int a, int b) { return a + b; },
 [](int a, int b) { return a==b ? a : 0; });
 std::cout << result << "\n";
}

If you'd like to play with that using a (strictly prototype) implementation of transform_reduce, it's not terribly complex--something on this order:

template<class InputIterator1, 
 class InputIterator2, 
 class T, 
 class BinaryOperation1, 
 class BinaryOperation2>
T transform_reduce(InputIterator1 first1, InputIterator1 last1,
 InputIterator2 first2,
 T init,
 BinaryOperation1 binary_op1,
 BinaryOperation2 binary_op2) 
{
 for ( ; first1 != last1; ++first1, ++first2) {
 init = binary_op1(init, binary_op2(*first1, *first2));
 }
 return init;
}

Note, however, that this is a purely serial implementation--part of the intent of transform_reduce is that it will support parallel implementation, which this doesn't (but that's mostly a restriction that binary_op1 and binary_op2 must be commutative and associative, not a requirement on the implementation). Note that the standard includes a number of overloads of std::transform_reduce--I've included an implementation of the one used in the preceding code.

• Incomputable: One can also hijack std::transform by supplying noop output iterator. It is unfortunate that std::accumulate does not provide a version for two ranges, or N.
• mkrieger1: Can rotate also be used without making a copy, but using some sort of reference or "view" on the original container?
• Jerry Coffin: @mkrieger1: If you wanted to avoid the copy, you could use something a little like (but definitely not quite identical to) the mod_iterator I posted in a previous answer. With C++ 17, you can easily do without the make_mod_iterator as well, making this approach more convenient.
• Incomputable: @JerryCoffin, I believe it will violate most of the iterator category requirements, as range "should have an end". Though as output iterator into ring buffer would be nice. Btw, in my solution I went the other around, e.g. operate in place.
• Konrad Rudolph: It’s universally known and accepted that std::inner_product’s name is misleading anyway. So nobody relies on its name for its semantics, and using it here wouldn’t be all that surprising. But yes, unfortunately its name is misleading. Maybe there should be a proposal to add an alias (in the <algorithm> header).

Answer 2

Consider extending digits with

 digits.push_back(*digits.begin());

This way you wouldn't need to worry about a next() == end():

 for (auto first = digits.begin(), second = next(first);
 second != digits.end();
 ++first, ++second) {
 sum += (*first == *second)? *first: 0;
 }

• Peter Cordes: I'm not sure if a single-digit input is supposed to be counted or not. This interpretation makes sense, though: It's its own next digit, so it matches itself. But if that's not the right interpretation, you'd have to explicitly check for the single-digit case and not count it. But anyway, +1 for this because it avoids making a second copy of the whole list, and avoids extra work inside the loop. Peeling the last iteration would probably be even more efficient, but DRY says not to do that.

Answer 3

CodeReview

The code does a lot of unnecessary copying. Otherwise it is pretty solid. May be actually having second iterator would be nicer. That way, the code check only the second iterator.

---

Alternative Solution

I actually started thinking about it, and found out that no copying around is needed. One can memorize the first and the previous char and find the sum. The nature of the algorithm is that it performs only one pass, which is the same as pass over any sequence at all.

#include <iterator>
#include <iostream>
template <typename InputIterator>
int reverse_captcha(InputIterator first, InputIterator last)
{
 if (first == last) {return {};}
 char leading_digit = *first++;
 if (first == last) {return {};}
 char prev_digit{leading_digit};
 int sum{0};
 while (first != last)
 {
 if (*first == prev_digit)
 {
 sum += *first - '0';
 }
 prev_digit = *first++;
 }
 if (leading_digit == prev_digit)
 {
 sum += leading_digit - '0';
 }
 return sum;
}
int main()
{
 auto res = reverse_captcha(std::istream_iterator<char>{std::cin}, {});
 std::cout << res << '\n';
}

---

This has multiple drawbacks, but also multiple benefits.

Benefits

• Relies only on performance of char retrieval. One can make it fast, or make it slow

• Works on any range which support single pass

• More in line with standard algorithms, thus has the potential to be well understood in terms of usage.

Drawbacks

• Benefit #1 is also a drawback

• More tedious implementation, which makes it easier to get wrong

• Overgeneralization?

• Incomputable: I haven't tested this, but I'm sure it won't fail in obvious cases. It does certainly compile though.
• Peter Cordes: This is what I was thinking, too. Expanding each ASCII digit to an int, and then copying that, is just totally unnecessary. However, multiple single-byte cin>> function calls are probably slow (and probably don't optimize away into larger reads), so getline is probably not a bad idea. Then looping over a buffer of characters will let the compiler auto-vectorize with SIMD packed-compare, though. (e.g. on x86, load and overlapping unaligned load, then pcmpeqb (packed compare) / psubb (set1('0') / pand(mask off bytes that weren't equal) / horizontal sum + add psadbw / paddq)
• Incomputable: @PeterCordes, as I mentioned at the bottom of the post, this really wasn’t much about quality as it was about usage of standard library :)
• Peter Cordes: But is there any way to use istream_iterator<char>{std::cin} that compiles efficiently? I had a look, and this doesn't: godbolt.org/g/pfggez. A function call for each character. (Which presumably has to lock/unlock cin, not to mention all the function-call overhead in the calling code setting up args.) If not, this makes it hard to recommend std::istream_iterator<char> over getline if you know you want whole lines, and that lines aren't unreasonably long.
• Incomputable: @PeterCordes, I did edit it now. Hopefully I didn't miss anything from what you said.

Answer 4

Don't use std::transform

When in doubt, don't. This:

std::vector<int> digits(line.size());
std::transform(
 std::cbegin(line), std::cend(line), std::begin(digits),
 [](char c) { return c - '0'; }

Is just so much more complicated than this:

std::vector<int> digits;
digits.reserve(line.size());
for (char c : line) {
 digits.push_back(c - '0');
}

Don't use non-member begin/end

You're using standard containers. They have member begin/end. It's a natural thing to use and long predates the non-member functions. The non-members only make sense to be used in generic code, or on types that don't have the members. As-is, you're neither adding more functionality (w.r.t. generic code) nor adding to readability (it's longer to type, and the important part - the container - now comes last).

So this:

for (auto p = std::begin(digits); p != std::end(digits); p++) {
 auto next_p =
 (std::next(p) == std::end(digits)) ?
 std::begin(digits) : std::next(p);
 if (*p == *next_p) sum += *p;
}

Could become:

for (auto p = digits.begin(); p != digits.end(); p++) {
 auto next_p =
 (std::next(p) == digits.end()) ?
 digits.begin() : std::next(p);
 if (*p == *next_p) sum += *p;
}

Could become, since vector's iterators are random-access:

for (auto p = digits.begin(); p != digits.end(); p++) {
 auto next_p = (p + 1 == digits.end()) ? digits.begin() : p + 1;
 if (*p == *next_p) sum += *p;
}

Could become, since using iterators doesn't really give you anything:

for (size_t i = 0; i < digits.size(); ++i) {
 auto next_i = (i + 1 == digits.size()) ? 0 : i + 1;
 if (digits[i] == digits[next_i]) sum += digits[i];
}

Could become, since we don't have to deal with modulus awkwardness:

for (size_t i = 0; i < digits.size(); ++i) {
 if (digits[i] == digits[(i + 1) % digits.size()]) {
 sum += digits[i];
 }
}

• Incomputable: I somewhat agree with the point about non member begin/end. I believe their true power unleashes when ADL kicks in (given that it is written to use ADL). It seems like there is a lot of tension about this. About iterators, for me iterators always look easier to comprehend. I never got used to index based algorithms.
• Barry: @Incomputable There's no tension. If you're writing generic code, you have to do using std::begin; begin(x) If you're not writing generic code, just do the thing that works? I don't see the point of writing std::begin(x) over x.begin().
• Incomputable: my IDE has macros for non member version. I can read both versions with the same comprehension, so I guess it is about personal taste.
• Peter Cordes: (i+1) % digits.size() is quite bad for performance. Compilers don't realize that it only wraps at most once, and use an actual 64-bit DIV instruction inside the loop! (See gcc+clang+ICC on godbolt.org/g/hrwzFX). This is about 30x slower than auto next_i = (i + 1 == digits.size()) ? 0 : i + 1; or the OP's code which compiles to a CMOV. Peeling the wrap-around condition out of the loop entirely is even better. @vnp's suggestion to push a 2nd copy of the first digit solves it cleanly without violating DRY.
• Konrad Rudolph: I disagree with a number of your items here. Do use the free functions, they are more than acceptable: uniform interfaces aren’t only beneficial for generic code (but don’t use std:: in front, ADL will find them anyway). Do use std::transform — that’s what it’s there for (though in this particular case the added verbosity does make it less robust). Do use iterators, they are (virtually always) less error-prone than using indices. In fact, forget about indices on sequential container access altogether. The default idiom should always be to work on ranges. Indices are a low-level hack.