Recursive range iteration

Question

I decided to do Advent of Code this year in D, and the following is my solution to day 8.

Algorithm aside, I was specifically wondering if there was a better way to use ranges in a recursive manner here. I feel like I should be able to do write the functions in a more generic way (not just int[], avoiding the .array in main), and without destroying the original array in the process - avoiding the temporary variable p1.

My use of the header variable seems suspect to me as well - basically I want a popFront that returns a value, I think, but have been unable to find anything like that.

I'm also happy to hear general advice about usual best practices and efficiencies.

import std.algorithm;
import std.conv;
import std.file;
import std.range;
import std.stdio;
import std.string;

int count_metadata(ref int[] r)
{
    auto header = r.take(2);
    int num_child = header.front;
    int num_metadata = header.back;
    r = r.drop(2);
    int count;
    for (int i; i < num_child; i++) {
        count += r.count_metadata;
    }
    count += r.take(num_metadata).sum;
    r = r.drop(num_metadata);
    return count;
}

int node_value(ref int[] r)
{
    auto header = r.take(2);
    int num_child = header.front;
    int num_metadata = header.back;
    r = r.drop(2);
    int[] child_values;
    for (int i; i < num_child; i++) {
        child_values ~= node_value(r);
    }
    int count;
    if (num_child == 0) {
        count = r.take(num_metadata).sum;
    } else {
        // ignore out of range
        count = r.take(num_metadata).filter!(a => 0 < a && a <= child_values.length).map!(a => child_values[a - 1]).sum;
    }
    r = r.drop(num_metadata);
    return count;
}

void main(string[] args)
{
    // integers separated by spaces
    auto input = readText(args[1]).split.map!(a => to!int(a)).array;
    //auto input = [2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2];
    auto p1 = input.dup;
    writeln("Metadata total: ", count_metadata(p1));
    writeln("Node value: ", node_value(input));
}

(args[1] is a file with integers separated by spaces, sample input is commented out below it.)

Answer 1

First, I'd prefer to parse the int[] into a Node[] or somesuch - I'd even argue the name of node_value is a code smell indicating that it should be a member called value of a type called Node. I believe this is part of what causes your consternation with the header variable.

Speaking of names, D naming conventions generally avoids underscores except for constants, so more idiomatic names would be nodeValue and countMetadata (which would perhaps more correctly be called sumMetadata).

One of the reasons you should parse to Node[] is it factors out the common parts between node_value and count_metadata, making their responsibilities clearer and the code easier to follow - remember, you're writing code for the next person who looks at it; the computer is happy with a string of bits that nobody can read.

Now, you mention genericity. For the most part, replacing (ref int[] r) with (R)(ref R r) if (isForwardRange!R) will deal with this. This templates the functions on the type of the range passed. Your code otherwise uses range functions (front, popFront, take, etc), so so no other change is necessary.

However, due to the structure of the file format, you will need to read all child nodes before getting at the metadata of a node. This limits the possible laziness of the solution. Since you are always iterating over every node, this doesn't matter a whole lot, but since that's one of the great benefits of ranges, it's worth pointing out.

As for consuming the range, there is no very simple, unobtrusive solution. You need to either create a temporary variable (like p1), have a duplicate function for the non-ref case, or use inner functions:

int count_metadata(R)(R r0) if (isForwardRange!R) { int impl(ref R r) { // Same code as before, but call impl instead of count_metadata } return impl(r); }

You also mentioned efficiency. I don't think I can improve much on that. Both count_metadata and node_value are O(n), and my proposed solution doesn't change that.

Answer 2

I spoke with some people on the #d IRC channel, and came up with a few things

The main bit of which was using the recursive function to return the range, rather than the result and using a reference parameter as the actual output. Makes the function a bit "harder" to use, but ultimately makes the implementation much easier and more generalisable (see R template parameter). This also means that the .array and .dup can be removed from the main function

I'd still like a function that pops and returns the value, so repeated .front & .popFront() isn't necessary, but seems like that might be a design decision, like C++'s std::stack::pop

Also added some unittest blocks to hold the examples

import std.algorithm;
import std.conv;
import std.file;
import std.range;
import std.stdio;

R sum_metadata(R)(R r, ref int count)
{
    int num_child = r.front;
    r.popFront;
    int num_metadata = r.front;
    r.popFront;

    for (int i; i < num_child; i++) {
        r = r.sum_metadata(count);
    }

    count += r.take(num_metadata).sum;
    return r.dropExactly(num_metadata);
}

R node_value(R)(R r, ref int count)
{
    int num_child = r.front;
    r.popFront;
    int num_metadata = r.front;
    r.popFront;

    int[] child_values;
    for (int i; i < num_child; i++) {
        int val;
        r = r.node_value(val);
        child_values ~= val;
    }

    if (num_child == 0) {
        count += r.take(num_metadata).sum;
    } else {
        // Ignore out of range
        count += r.take(num_metadata).filter!(a => 0 < a && a <= child_values.length).map!(a => child_values[a - 1]).sum;
    }
    return r.drop(num_metadata);
}

void main(string[] args)
{
    auto input = readText(args[1]).split.map!(a => to!int(a));
    int sum;
    input.sum_metadata(sum);
    writeln("Metadata total: ", sum);
    int val;
    input.node_value(val);
    writeln("Node value: ", val);
}

unittest
{
    auto input = [2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2];
    int sum;
    input.sum_metadata(sum);
    assert(sum == 138);
}

unittest
{
    auto input = [2, 3, 0, 3, 10, 11, 12, 1, 1, 0, 1, 99, 2, 1, 1, 2];
    int val;
    input.node_value(val);
    assert(val == 66);
}