Recursive range iteration 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 &lt; 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 &lt; 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 =&gt; 0 &lt; a &amp;&amp; a &lt;= child_values.length).map!(a =&gt; 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 =&gt; 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.)
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.