Anonymous user
Summarize and say sequence: Difference between revisions
Updated D entry, added faster D entry
(Shorter C entry) |
(Updated D entry, added faster D entry) |
||
Line 515:
void main() {
enum int limit = 1_000_000;
int max_len;
int[] max_vals;
foreach (n; 1 .. limit) {
if (seq.length > max_len) {
max_len = seq.length;
Line 531:
writeln("iterations: ", max_len);
writeln("sequence:");
foreach (idx, val;
writefln("%2d %s", idx + 1, val);
}</lang>
Line 559:
20 19281716151413427110
21 19182716152413228110</pre>
===Faster Version===
{{trans|C}}
<lang d>import core.stdc.stdio, core.stdc.stdlib;
struct Rec {
int length;
Rec*[10] p;
}
__gshared int nn;
__gshared Rec* rec_root;
Rec* findRec(char* s, Rec* root) nothrow {
int c;
Rec* next;
while (true) {
c = *s;
s++;
if (!c)
break;
c -= '0';
next = root.p[c];
if (!next) {
nn++;
next = cast(Rec*)calloc(1, Rec.sizeof);
assert(next);
root.p[c] = next;
}
root = next;
}
return root;
}
void nextNum(char* s) nothrow {
int[10] cnt;
for (int i = 0; s[i]; i++)
cnt[s[i] - '0']++;
foreach_reverse (i; 0 .. 10) {
if (!cnt[i])
continue;
s += sprintf(s, "%d%c", cnt[i], i + '0');
}
}
int getLen(char* s, int depth) nothrow {
auto r = findRec(s, rec_root);
if (r.length > 0)
return r.length;
depth++;
if (!r.length)
r.length = -depth;
else
r.length += depth;
nextNum(s);
depth = 1 + getLen(s, depth);
if (r.length <= 0)
r.length = depth;
return r.length;
}
void freeRec(Rec* root) nothrow {
if (!root)
return;
foreach (sub; root.p)
freeRec(sub);
free(root);
}
void main() nothrow {
enum MAXN = 1_000_000;
int[100] longest;
int nLongest, ml;
char[32] buf;
rec_root = cast(Rec*)calloc(1, Rec.sizeof);
foreach (i; 0 .. MAXN) {
sprintf(buf.ptr, "%d", i);
int l = getLen(buf.ptr, 0);
if (l < ml)
continue;
if (l > ml) {
nLongest = 0;
ml = l;
}
longest[nLongest] = i;
nLongest++;
}
printf("seq leng: %d\n\n", ml);
foreach (i; 0 .. nLongest) {
sprintf(buf.ptr, "%d", longest[i]);
// print len+1 so we know repeating starts from when
foreach (l; 0 .. ml + 1) {
printf("%2d: %s\n", getLen(buf.ptr, 0), buf.ptr);
nextNum(buf.ptr);
}
printf("\n");
}
printf("alloc: %d\n", nn);
//freeRec(rec_root);
}</lang>
Maybe a little faster than the C entry (run-time is 1.5 seconds). Same output as the C entry.
=={{header|Go}}==
Brute force
| |||