APL 中的惯用图表

Question

APL 非常适合解决数组类型问题，但我很好奇如何最好地处理 APL 中的图形。我正在玩 leet 问题，例如问题662. 二叉树的最大宽度，该练习适用于具有值/左/右指针样式的 Node 对象，但是测试用例使用像[1,3,null,5,3]. 符号被压缩；未压缩的将是[[1], [3,null], [5,3,null,null]]. 逐层阅读给出[[1], [3], [5,3]]（所以2是最宽的层）。

\n

另一个例子，

\n

[5,4,7,3,null,2,null,-1,null,9]给出答案 2\n

\n

所以我不确定处理树木的惯用方法。我使用类吗？还是数组最好？在这两种情况下，我如何转换输入？

\n

我想出了几个解决方案，但都感觉不优雅。（抱歉没有评论）

\n

 convert\xe2\x86\x90{\n     prev \xe2\x86\x90 {(-\xe2\x8c\x882\xc3\xb7\xe2\x8d\xa8\xe2\x89\xa2\xe2\x8d\xb5)\xe2\x86\x91\xe2\x8d\xb5}\n     nxt\xe2\x86\x90{\n         \xe2\x8d\xb5\xe2\x89\xa1\xe2\x8d\xac:\xe2\x8d\xba\n         m\xe2\x86\x902/\xc3\x97prev \xe2\x8d\xba\n         cnt\xe2\x86\x90+/m\n         (\xe2\x8d\xba,(m\\cnt\xe2\x86\x91\xe2\x8d\xb5))nxt(cnt\xe2\x86\x93\xe2\x8d\xb5)\n     }\n\n     (1\xe2\x86\x91\xe2\x8d\xb5)nxt(1\xe2\x86\x93\xe2\x8d\xb5)\n }\n

\n

或者，

\n

convert \xe2\x86\x90 {\n     total\xe2\x86\x90(+/\xc3\x97\xe2\x8d\xb5)\n     nxt\xe2\x86\x90{\n         double\xe2\x86\x90\xc3\x971,2\xe2\x86\x932/0,\xe2\x8d\xb5\n         (((+/double)\xe2\x86\x91\xe2\x8d\xba)@\xe2\x8a\xa2)double\n     }\n     \xe2\x8d\xb5 nxt\xe2\x8d\xa3{(+/\xc3\x97\xe2\x8d\xba)=total}1\n }\n\n

\n

两种解决方案都受到限制，因为它们假设0是null。

\n

一旦我解压了输入，它就只是按其顺序分层的问题

\n

\xe2\x8c\x88/(1+\xe2\x8c\x88/-\xe2\x8c\x8a/)\xe2\x88\x98\xe2\x8d\xb8\xc2\xa8\xc3\x97nodes\xe2\x8a\x86\xe2\x8d\xa8\xe2\x8d\xb82*\xc2\xaf1+\xe2\x8d\xb3\xe2\x8c\x882\xe2\x8d\x9f\xe2\x89\xa2nodes\n

\n

在Python中，我可以使用其他方法来遍历，即在每个深度的基础上跟踪最左/最右的节点。

\n

注意：这可能是两个问题，一个是解压缩，另一个是如何遍历一般图，但一个取决于另一个

\n

有任何想法吗？

\n

Answer 1

Co-dfns 编译器的工作为使用 APL 工作树/图等数据结构提供了很多见解。

\n

论文：GPU 上托管的数据并行编译器

\n

GitHub 存储库：github.com/Co-dfns/Co-dfns（项目自述文件中有许多相关的好东西）

\n

然而这篇论文相当冗长，因此对于这个特定的练习，我将简要解释如何进行它。

\n

\n

该练习适用于具有值/左/右指针样式的 Node 对象，但是测试用例使用像[1,3,null,5,3].

\n

\n

我们真的用以下方法来构建树吗Node类型对象构建树来获得问题的答案吗？你可以用Python之类的东西编写解决方案并将其转换为APL，但这会失去用APL编写它的全部意义......

\n

请注意，输入已经是一个数组！是二叉树的bfs遍历。（不过，co-dfns 编译器使用 dfs 遍历顺序）

\n

所以，实际上我们需要做的只是为输入构建一个如下所示的矩阵[1,3,2,5,3,null,9]（\xe2\x8d\xac是 null 的占位符值）：

\n

1 \xe2\x8d\xac \xe2\x8d\xac \xe2\x8d\xac \xe2\x8d\x9d level 0\n3 2 \xe2\x8d\xac \xe2\x8d\xac \xe2\x8d\x9d level 1\n5 3 \xe2\x8d\xac 9 \xe2\x8d\x9d level 2\n

\n

对于这个问题，我们不需要知道哪个节点的父节点是哪个节点。\n我们甚至可以做类似的事情，通过滥用输入没有负值的事实（即使数字可能是负数，实际上我们只关心关于它是否为空），并更改\xe2\x8d\xac为\xc2\xaf1or0并使其更容易计算答案。

\n

所以问题变成了：“根据输入数组计算树的矩阵表示作为变量，然后通过tree计算每个级别的宽度，然后输出就是（注意第一级别是 level-0）”这是使用错误宽度的定义。我将在下面展示如何纠正它+/0<tree2*level

\n

实际上，从输入到矩阵的转换非常容易，提示：\xe2\x86\x91。

\n

      1 (3 2) 5\n\xe2\x94\x8c\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xac\xe2\x94\x80\xe2\x94\x90\n\xe2\x94\x821\xe2\x94\x823 2\xe2\x94\x825\xe2\x94\x82\n\xe2\x94\x94\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x80\xe2\x94\x80\xe2\x94\xb4\xe2\x94\x80\xe2\x94\x98\n      \xe2\x86\x911 (3 2) 5\n1 0\n3 2\n5 0\n

\n

感谢您指出我原来的解决方案在构造树矩阵方面存在问题。

\n

这是构建树的正确方法。为了区别0for null 和填充，我在输入数组中添加 1，so2表示非 null，1is 表示 null。

\n

 buildmatrix\xe2\x86\x90{\n     \xe2\x8e\x95IO\xe2\x86\x900\n     in\xe2\x86\x901+(\xe2\x8a\x82\xe2\x8a\x82\'null\')(\xe2\x89\xa2\xe2\x8d\xa41 0)\xe2\x8e\x95JSON \xe2\x8d\xb5\n     \xe2\x8d\x9d Build the matrix\n     loop\xe2\x86\x90{\n         (n acc)\xe2\x86\x90\xe2\x8d\xba\n         0=\xe2\x89\xa2\xe2\x8d\xb5:acc\n         cur\xe2\x86\x90n\xe2\x86\x91\xe2\x8d\xb5\n         (2\xc3\x97+/2=cur)(acc,\xe2\x8a\x82cur)\xe2\x88\x87 n\xe2\x86\x93\xe2\x8d\xb5\n     }\n     \xe2\x86\x911 \xe2\x8d\xac loop in\n }\n

\n

然而，由于这里宽度的定义是：

\n

\n

一层的宽度定义为末端节点（最左边和最右边的非空节点）之间的长度，其中末端节点之间的空节点也计入长度计算中。

\n

\n

我们可以在尝试重建树时计算宽度（使用前一级别的模式计算每个级别的宽度\\）/：

\n

如果上一级是1011下一级是100010

\n

 1   0   1   1\n1 0 0 0 0 0 1 0\n

\n

      (2/1 0 1 1)\\1 0 0 0 1 0\n1 0 0 0 0 0 1 0\n

\n

因此不需要构造完整的矩阵，练习的答案就是：

\n

 width\xe2\x86\x90{\n     \xe2\x8e\x95IO\xe2\x86\x900\n     in\xe2\x86\x90(\xe2\x8a\x82\xe2\x8a\x82\'null\')(\xe2\x89\xa2\xe2\x8d\xa41 0)\xe2\x8e\x95JSON \xe2\x8d\xb5\n     \xe2\x8d\x9d strip leading trailing zero\n     strip\xe2\x86\x90(\xe2\x8c\xbd\xe2\x8d\xb3\xe2\x88\x981\xe2\x86\x93\xe2\x8a\xa2)\xe2\x8d\xa32\n     \xe2\x8d\x9d Build the matrix\n     loop\xe2\x86\x90{\n         (prev mw)\xe2\x86\x90\xe2\x8d\xba\n         0=\xe2\x89\xa2\xe2\x8d\xb5:mw\n         cur\xe2\x86\x90\xe2\x8d\xb5\xe2\x86\x91\xe2\x8d\xa8n\xe2\x86\x902\xc3\x97+/prev\n         ((\xe2\x8a\xa2,\xe2\x8d\xa5\xe2\x8a\x82mw\xe2\x8c\x88\xe2\x89\xa2)strip cur\\\xe2\x8d\xa82/prev)\xe2\x88\x87 n\xe2\x86\x93\xe2\x8d\xb5\n     }\n     (,1)1 loop 1\xe2\x86\x93in\n }\n

\n

      width \'[1,null,2,3,null,4,5,6]\'\n2\n

\n

有趣的事实是，您可能可以在其他非基于数组的语言（如 Haskell）中执行相同的操作。因此，无需在外观相似的语言之间翻译现有算法，而是通过以 APL 方式思考，您可以找到解决问题的新算法！

\n