使用递归求解 q 中的 Euler 18

Question

我已经在 q 中编写了这段代码来解决 Euler 18 问题，如下面的 link 所述，使用递归。

尽管该代码有效，但效率不高，并且在金字塔大小大于 3000 时会发生堆栈溢出。我如何才能使此代码更多 efficient.I 相信最佳代码可以少于 30 个字符。

pyr:{[x]
    lsize:count x;
    y:x;
    $[lsize <=1;y[0];
    [.ds.lastone:x[lsize - 1];
    .ds.lasttwo:x[lsize - 2];
    y:{{max (.ds.lasttwo)[x] +/: .ds.lastone[x],.ds.lastone[x+1]}each til count .ds.lasttwo};
    $[(count .ds.lasttwo)=1;y:{max (.ds.lasttwo) +/: .ds.lastone[x],.ds.lastone[x+1]}0;y:y[]];
    x[lsize - 2]:y;
    pyr[-1_x]]]
 }

Answer 1

要在 q 中正确实现此逻辑，您需要使用副词。

首先，要快速找到滚动最大值，您可以使用 prior 副词。例如：

q)input:(75;95 64;17 47 82;18 35 87 10;20 04 82 47 65;19 01 23 75 03 34;88 02 77 73 07 63 67;99 65 04 28 06 16 70 92;41 41 26 56 83 40 80 70 33;41 48 72 33 47 32 37 16 94 29;53 71 44 65 25 43 91 52 97 51 14;70 11 33 28 77 73 17 78 39 68 17 57;91 71 52 38 17 14 91 43 58 50 27 29 48;63 66 04 68 89 53 67 30 73 16 69 87 40 31;04 62 98 27 23 09 70 98 73 93 38 53 60 04 23)
q)last input
4 62 98 27 23 9 70 98 73 93 38 53 60 4 23
q)1_(|) prior last input
62 98 98 27 23 70 98 98 93 93 53 60 60 23

最后一行输出一个向量，该向量具有输入向量中每个连续对之间的最大值。一旦你有了这个，你可以将它添加到下一行并重复。

q)foo:{y+1_(|) prior x}
q)foo[input 14;input 13]
125 164 102 95 112 123 165 128 166 109 122 147 100 54

然后，要将此函数应用到整个对象上，请使用 over 副词：

q)foo over reverse input
,1074

编辑：上述方法可以进一步推广。

q 提供移动最大值函数mmax。有了这个你可以找到 "the x-item moving maximum of numeric y"，它概括了上面 prior 的用法。例如，您可以使用它来查找输入最后一行中的对或 三元组 的移动最大值：

q)last input
4 62 98 27 23 9 70 98 73 93 38 53 60 4 23
q)2 mmax last input
4 62 98 98 27 23 70 98 98 93 93 53 60 60 23
q)3 mmax last input
4 62 98 98 98 27 70 98 98 98 93 93 60 60 60

mmax可以用来简化上面的foo：

q)foo:{y+1_ 2 mmax x}

这个特别好的地方在于，它可用于泛化到具有更宽三角形的此问题的变体。例如，下面的三角形在每一行上还有两个值，您可以从一行上的任意点移动到它下面一行的左侧、中间或右侧。

    5
  5 6 7
6 7 3 9 1

使用递归求解 q 中的 Euler 18

using recursion for solving Euler 18 in q

kdb