C, 174 167 152 bytes
Recursive function f
, which leaks memory (152):
#include"object.h"
size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t*o=array_get_copy(a,i,0);t+=o->type==6?f(o->ary):1;}return t;}
Recursive f
which doesn't leak, using references, at 167:
#include"object.h"
size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t**o=array_get_ref(a,i,0);t+=*o->type==t_array?f(*o->ary):1;}return t;}
Ungolfed:
size_t get_recursize (const array_t* const a) {
pfn();
object_failnull(a);
size_t out = 0;
for (size_t i = 0; i < array_length(a); i++) {
object_t** o = array_get_ref(a, i, NULL);
if ( (*o)->type == t_array ) {
out += get_recursize((*o)->ary);
} else {
++out;
}
}
return out;
}
"But how," you ask, "can this be answered in C? Surely, there are no managed arrays in C, and you can't really have heterogeneous arrays...?"
"Aha," I reply, "for I have been working on a simple system of "objects" for (GNU-ish) C11 and ISO C++11".
The full demo program for this function is:
#include "../calc/object/object.h"
size_t get_recursize (const array_t* const a);
define_array_new_fromctype(ssize_t);
int main (void) {
size_t len = 6;
static const ssize_t h[6] = { -1, 3, -5, 7, -9, 11 };
array_t* a = array_new_from_ssize_t_lit(h, len, t_realint);
size_t rsize = get_recursize(a);
printf("Recursive size of a: %zu\n", rsize);
object_t* asobj = object_new(t_array, a);
array_destruct(a);
array_t* b = array_new(NULL, -1);
for (size_t j = 0; j < 10; j++) {
array_append(b, asobj);
}
object_destruct(asobj);
rsize = get_recursize(b);
printf("Recursive size of b: %zu\n", rsize);
asobj = object_new(t_array, b);
array_destruct(b);
array_t* c = array_new(NULL, -1);
for (size_t i = 0; i < 100; i++) {
array_append(c, asobj);
}
object_destruct(asobj);
rsize = get_recursize(c);
printf("Recursive size of c: %zu\n", rsize);
array_destruct(c);
return EXIT_SUCCESS;
}
size_t get_recursize (const array_t* const a) {
pfn();
object_failnull(a);
size_t out = 0;
for (size_t i = 0; i < array_length(a); i++) {
object_t** o = array_get_ref(a, i, NULL);
if ( (*o)->type == t_array ) {
out += get_recursize((*o)->ary);
} else {
++out;
}
}
return out;
}
Right now, it lives here and you'll need that repo to use this.
You'll also need the Fowler-Noll-Vo hash library, libfnv
, compiled for your platform. It's in that repository and you can also grab it here.
Then you can do cc -DNODEBUG size.c path/to/libfnv.a -o size
.
The implementation isn't necessarily efficient:
$ valgrind --leak-check=full --track-origins=yes --show-leak-kinds=all ./size
==24127== Memcheck, a memory error detector
==24127== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==24127== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==24127== Command: ./size
==24127==
Recursive size of a: 6
Recursive size of b: 60
Recursive size of c: 6000
==24127==
==24127== HEAP SUMMARY:
==24127== in use at exit: 0 bytes in 0 blocks
==24127== total heap usage: 22,900 allocs, 22,900 frees, 615,584 bytes allocated
==24127==
==24127== All heap blocks were freed -- no leaks are possible
==24127==
==24127== For counts of detected and suppressed errors, rerun with: -v
==24127== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
But it does work! The last commit to master (which this program compiled on) was 2 days ago, which means this submission is valid.
related – Jonathan Allan – 2016-11-19T02:13:33.633
Will the elements be strings, numbers, and recursive lists? – xnor – 2016-11-19T02:41:11.393
Note: Restricted the content of the lists after some discussion. I have edited the question to reflect this. Thanks to @xnor for the input! – Jonathan Allan – 2016-11-19T03:21:31.300
2I feel like this'd be a better challenge without having to account for strings. It's only add bytes to some languages IMO – Conor O'Brien – 2016-11-19T05:43:04.270
@ConorO'Brien or maybe I should have made it up to the answerer if they wished to treat a string as a list or not. Unfortunately I specifically asked the community both "Are there any edge cases I should add?", and "Is any clarification of the definition needed?" and got no response in the sandbox over nine days ...and now I suppose such a question would be a duplicate? – Jonathan Allan – 2016-11-19T05:54:51.497
@JonathanAllan I unfortunately don't check the sandbox as much as I would like ;) why should this be a dupe? – Conor O'Brien – 2016-11-19T05:56:12.953
@ConorO'Brien maybe it wouldn't - I don't really know! – Jonathan Allan – 2016-11-19T06:08:42.050
For future reference: these test cases are in a really clunky format to convert to any language that doesn't use this exact syntax, you should give them in a simpler format – cat – 2016-11-19T13:55:57.257
@cat could you explain what you mean? As far as I am aware (except for the containing
RS()
) it's about as simple as it gets while conveying the necessary information. – Jonathan Allan – 2016-11-19T21:35:17.333About the test case: the string mess of "[" and "]" does not add value. It just make them difficult to evaluate by hand for people (to check our results), while does not pose any problem for programs. – edc65 – 2016-11-20T08:22:19.037
@edc65 Not now, no; there was a perfectly valid point to them originally, before the question was changed (really, the sandbox failed us). I don't think that they are that hard for a human to parse though; note that they are grouped with like cases and have the expected result on the right. – Jonathan Allan – 2016-11-20T11:24:53.047
Some languages don't differentiate between strings and arrays/lists of characters. – Robert Fraser – 2016-12-18T13:54:16.943