背景

这张照片说明了问题:

我可以控制红圈.目标是蓝色三角形.黑色箭头表示目标将移动的方向.

我想以最少的步数收集所有目标.

每回合我必须向左/向右/向上或向下移动1步.

每转一圈,目标也会根据棋盘上显示的方向移动一步.

演示

我在Google appengine上发布了一个可玩的问题演示.

如果有人能够击败目标分数,我会非常感兴趣,因为这会显示我当前的算法不是最理想的.(如果你管理这个,应该打印祝贺信息!)

问题

我目前的算法与目标数量的关系非常严重.时间以指数方式上升,对于16条鱼来说已经是几秒钟了.

我想计算板尺寸为32*32和100个移动目标的答案.

题

用于计算收集所有目标的最小步骤数的有效算法(理想情况下是Javascript)是什么？

我试过的

我目前的方法是基于记忆,但它非常慢,我不知道它是否总能产生最佳解决方案.

我解决了"收集一组给定目标并最终达到特定目标的最小步数是多少？"的子问题.

通过检查先前要访问的目标的每个选择来递归地解决子问题.我假设尽可能快地收集前一个目标子集然后尽快从你结束的位置移动到当前目标(尽管我不知道这是否是一个有效的假设)总是最佳的.

这导致计算n*2 ^ n个状态,其非常快速地增长.

当前代码如下所示:

var DX=[1,0,-1,0];
var DY=[0,1,0,-1]; 

// Return the location of the given fish at time t
function getPt(fish,t) {
  var i;
  var x=pts[fish][0];
  var y=pts[fish][1];
  for(i=0;i<t;i++) {
    var b=board[x][y];
    x+=DX[b];
    y+=DY[b];
  }
  return [x,y];
}

// Return the number of steps to track down the given fish
// Work by iterating and selecting first time when …

背景

我一直试图弄清楚为什么我的AI已经做了一些疯狂的动作,我在使用Python 2.7.2时将问题追溯到以下行为

>>> print [2]>[1]
True
>>> print (2,)>(1,)
True
>>> print [2]>(1,)
False                 (WHY?)

>>> print [2]<[1]
False
>>> print (2,)<(1,)
False
>>> print [2]<(1,)
True                  (WHY?)

它似乎表现为列表总是小于元组.

这不是我对文档的期望

使用相应元素的比较,按字典顺序比较元组和列表.这意味着要比较相等,每个元素必须比较相等,并且两个序列必须是相同类型并且具有相同的长度.

如果不相等,则序列的排序与它们的第一个不同元素相同.例如,cmp([1,2,x],[1,2,y])返回与cmp(x,y)相同的值.如果相应的元素不存在,则首先排序较短的序列(例如,[1,2] <[1,2,3]).

题

这里发生了什么？我是否可以比较元组和列表 - 或者我可能只允许将自己的相同类型进行比较？

背景

我已经训练了一个卷积神经网络,我希望其他人能够使用而不需要很难安装像Theano这样的库(我发现在Linux上安装很简单,但在Windows上很难).

我使用Numpy/Scipy编写了一个实现速度非常快的实现,但如果速度提高两到三倍会更好.

我试过的

90%的时间用于以下行:

conv_out = np.sum([scipy.signal.convolve2d(x[i],W[f][i],mode='valid') for i in range(num_in)], axis=0)

该行被调用32次(每个特征映射一次),num_in是16(前一层中的特征数).总的来说,这一行很慢,因为它导致对convolve2d例程的32*16 = 512次调用.

x [i]仅为25*25,W [f] [i]为2*2.

题

有没有更好的方法在Numpy/Scipy中表达这种类型的卷积层会更快执行？

(我只使用此代码来应用学习的网络,因此我没有很多图像可以并行完成.)

码

进行计时实验的完整代码是:

import numpy as np
import scipy.signal
from time import time

def max_pool(x):
    """Return maximum in groups of 2x2 for a N,h,w image"""
    N,h,w = x.shape
    return np.amax([x[:,(i>>1)&1::2,i&1::2] for i in range(4)],axis=0)

def conv_layer(params,x):
    """Applies a convolutional layer (W,b) followed by 2*2 pool followed by RelU on x"""
    W,biases = params
    num_in = W.shape[1]
    A = …

问题

Pi = 3.14159 26 5358979323846 26 433 ...所以重复的第一个2位数子串是26.

找到重复的第一个20位子字符串的有效方法是什么？

约束

• 我有大约500千兆字节的Pi(每个数字1个字节),大约500千兆字节的磁盘空间.

• 我有大约5千兆字节的RAM免费.

• 我感兴趣的是一种适用于任意序列的高效算法,而不是Pi本身的特定答案.换句话说,即使打印的数字是正确的,我对"print 123 .... 456"形式的解决方案也不感兴趣.

我试过的

我将每个子字符串放入一个哈希表并报告第一次碰撞.

(哈希表构造为排序链表的数组.数组的索引由字符串的底部数字(转换为整数)给出,并且存储在每个节点中的值是Pi扩展中的位置子串最初出现的地方.)

这工作正常,直到我用完RAM.

为了扩展到更长的序列,我考虑过:

• 为从特定范围开始的所有子字符串生成哈希值,然后继续搜索其余数字.这需要为每个范围重新扫描整个Pi序列,因此变为N ^ 2阶

• 将一组20位子串分组到多个文件,然后使用哈希表分别查找每个文件中的第一个重复.不幸的是,使用这种方法,我的磁盘空间不足,因此需要20次通过数据.(如果我以1000位开头,那么我最终会得到1000个20位数的子串.)

• 每字节存储2位Pi,以释放更多内存.

• 将基于磁盘的后备存储添加到我的哈希表.我担心这会表现得非常糟糕,因为没有明显的参考地点.

有更好的方法吗？

更新

1. 我尝试了Adrian McCarthy的qsort方法,但这似乎比找到重复的哈希慢一点

2. 我查看了btilly的MapReduce建议,用于并行化算法,但它在我的单台计算机上严重IO绑定,因此不适合我(使用我的单个磁盘驱动器)

3. 我实现了supercat的方法,用于昨晚分割文件并在前180亿个数字中搜索19位数字的子串.

4. 这找到16场比赛,所以我用Jarred的建议重新检查19位数的比赛,找到前20位数的比赛

要搜索180亿个数字需要3个小时来分割文件,然后40分钟再重新扫描文件以查找匹配项.

回答

在Pi的十进制扩展内,在位置1,549,4062,637和17,601,613,330处找到20位子串84756845106452435773.

非常感谢大家!

背景

我有一个代码生成器，可以在 Rust 中生成长表达式，但编译器似乎不能很好地处理这个问题。在这些示例中，为了简单起见，我使用常量/加法，但实际上我希望支持涉及变量和其他编程结构的更复杂的表达式。

例子

fn main() {
  let _x = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
// ...
// 500 identical lines
// ...
+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1
;
}

当我尝试编译它时它崩溃了Segmentation fault (core dumped)。（它的中间行数较少，所以我认为这只是表达式长度引起的崩溃。）

我尝试过的

额外的括号

我尝试过在不同的地方放入括号。在每行的开头和结尾添加括号可以阻止崩溃，但需要一小时来编译（并且由于操作顺序不同，还会更改语义）：

fn main() {
  let _x = 1+(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)
+(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)
+(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)
// ...
// 8000 identical lines
// ...
+(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)
+(1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1)
;
}

法斯特瓦尔

fasteval看起来处理表达式的速度要快得多，但只能处理基本的变量操作和函数调用，因此不会处理表达式和更复杂的 Rust 代码的混合。

变量

将每个表达式分解为许多生成的变量（每个二元运算符一个）也可以阻止崩溃，但变量数量的编译时间仍然是二次方（例如，添加 8000 个数字需要 9 秒，添加 16000 个数字需要 37 秒）。

将表达式分解为多个函数

这感觉应该可行，但代码生成方面需要做很多工作。

改变编译器

查看 Rust 编译器源代码，看起来速度缓慢可能是由于在进行树操作时对抽象语法节点进行了大量克隆。感觉很多时候底层数据是不可变的，因此可以重用对现有不可变数据的引用，而不是复制所有树。然而，这感觉可能需要相当多的努力才能开始工作。

问题

有没有其他方法可以避免 Rust …

BACKGROUND

When playing around, I often write simple recursive functions looking something like:

def f(a,b):
    if a>=0 and b>=0:
        return min( f(a-1,b) , f(b,a-1) ) # + some cost that depends on a,b
    else:
        return 0

(For example, when computing weighted edit distances, or evaluating recursively defined mathematical formulas.)

I then use a memoizing decorator to cache the results automatically.

PROBLEM

When I try something like f(200,10) I get:

RuntimeError: maximum recursion depth exceeded

This is as expected because the …

背景

在Windows上使用64位Steel Bank Common Lisp进行简单的身份识别时:

(defun a (x)
   (declare (fixnum x)) 
   (declare (optimize (speed 3) (safety 0))) 
  (the fixnum x))

我发现反汇编如下:

* (disassemble 'a)

; disassembly for A
; Size: 13 bytes
; 02D7DFA6:       84042500000F20   TEST AL, [#x200F0000]      ; safepoint
                                                              ; no-arg-parsing entry point
;       AD:       488BE5           MOV RSP, RBP
;       B0:       F8               CLC
;       B1:       5D               POP RBP
;       B2:       C3               RET

我理解的是:

mov rsp, rbp
pop rbp
ret  

从函数操作执行标准返回,但我不明白为什么有这些行:

TEST AL, [#x200F0000]  // My understanding is that this …

是否可以在Nimrod中使用函数指针？

我试过的是:

type fptr = (proc(int):int)

proc f(x:int): int = 
  result = x+1

var myf : fptr = f

echo myf(0)

但是当我尝试编译时,我得到:

Hint: added path: 'C:\Users\Peter\.babel\pkgs\' [Path]
Hint: used config file 'C:\Program Files (x86)\Nimrod\config\nimrod.cfg' [Conf]
Hint: system [Processing]
Hint: hello3 [Processing]
Error: internal error: GetUniqueType
Traceback (most recent call last)
nimrod.nim               nimrod
nimrod.nim               handleCmdLine
main.nim                 mainCommand
main.nim                 commandCompileToC
modules.nim              compileProject
modules.nim              compileModule
passes.nim               processModule
passes.nim               processTopLevelStmt
cgen.nim                 myProcess
ccgstmts.nim             genStmts
ccgexprs.nim             expr
ccgstmts.nim             genStmts
ccgexprs.nim             expr
ccgstmts.nim             genVarStmt
ccgstmts.nim             genSingleVar …

背景

我正在移植现有的C程序,以使用Emscripten作为在线游戏.

问题是Emscripten希望程序围绕一个被调用60次的单个函数进行组织.这对于主游戏循环是可以的,除了有很多地方代码显示一组选项然后等待按键来选择选项.这表示为使用getch()等待按键的调用层次结构中的深层函数.我发现很难看到如何将其纳入运行然后完成的函数所需的Emscripten样式.

题

当代码调用一个调用了函数的函数时,它调用了一个函数,有一种简单的方法可以保存调用堆栈的整个状态,以便以后可以返回到同一个地方吗？

我试过的

1. 我目前使用的方法是设置一个全局状态变量来指示我当前的位置,并将堆栈中所有看起来很重要的内容写入静态变量.然后我从所有功能返回.要重新输入,我使用全局变量来决定调用哪个函数以及从保存的数据重新加载哪些变量.但是,这涉及编写大量额外代码,并且非常容易出错.

2. 我想知道如何使用线程进行游戏逻辑并只是从GUI线程发送消息,但是Emscripten中的当前线程API似乎要求我尝试将所有游戏数据复制到一条消息中,这样就会感觉更多的工作为了一点利益.

3. Emscripten支持setjmp/longjmp,但据我所知,这只能完成一半的工作.我想我可以使用longjmp简单地从一个深层函数返回到上层,但我不知道我可以用它来以后再回到原来的位置.

关于如何做到这一点的任何更好的想法？

背景

我正在玩一个迷你高尔夫游戏,使用three.js和弹药物理库的ammo.js转换,但是我在让球实际移动方面遇到了一些麻烦.

(我在penguinspuzzle.appspot.com/minigolf.html上放了一个演示,如果你想看看它在实践中是如何工作的.)

题

什么是一个很好的算法,以提供迷你高尔夫球的更逼真的运动？

我试过的

在ammo.js中,有摩擦,线性阻尼和旋转阻尼选项.

当球滚动时,摩擦设置似乎没有太大影响.

我正在使用

body.setRestitution(0.8);
body.setFriction(1);
body.setDamping(0.2,0.1); // linear damping, rotational damping

问题

由于线性阻尼值较高,球似乎减速得太快.

价值较低似乎需要很长时间才能最终停止.

当球在空中时,完全应用线性阻尼似乎是不合理的.

分析

我认为问题可能是ammo.js中的线性阻尼导致指数减慢.

我试过了:

1. 录制高尔夫击球的视频
2. 测量每个框架中球的位置
3. 根据时间绘制球的位置和速度

结果如下所示.在我看来,速度曲线更接近于线性而非指数.

有什么建议让算法让ammo.js更加真实吗？