小编גלע*_*רקן的帖子

我遇到了这个非常有趣的问题,我们有一个4x4的迷宫和一个机器人试图进入目标.问题是,您必须找到一系列预定义命令,这些命令将始终导致机器人到达目标.

假设我们有一个像这样的迷宫:

x . . .
. # # .
. # # .
. . . g

这种特殊的迷宫可以用例如命令序列来解决,DDDRRR或者RRRDDD,其中R =右,L =左,U =上,D =下(duh).

然而,这些序列都不会解决这个迷宫:

x . # .
. . . .
# . . .
. . . g

机器人总是从左上角开始,目标总是在右下方,迷宫始终是2D 4x4矩阵.

我已经实现了一个算法,让我获得了78个命令的获胜序列.我确信至少存在29个命令的解决方案(其他人完成了这个).

这个问题实际上已经有几年了,所以我丢失了当时使用的算法,但基本的想法是在我生成的所有迷宫中搜索,并始终选择导致解决最多的路线迷宫.这实际上让我得到了一个略长于78的序列; 我手动减少了一些命令,我​​发现这些命令是多余的.

是的,暴力迫使需要几年的时间.

如果我的记忆服务,可能的迷宫少于4000(可能的迷宫是左上角和右下角之间的路径存在).

哦!机器人在执行命令期间至少一次访问目标就足够了.也就是说,在最后一个命令之后,它不必坐在目标上.

我有没有抓住任何人的兴趣？我应该如何处理这个问题以获得更有效的答案？谢谢你考虑:)

好玩的东西:Pastebin

这是一个(非常)匆忙拼凑的Java片段.它应该编译运行:)程序有点同时播放~4000个迷宫.程序对UP,LEFT,DOWN和RIGHT进行输入(w,a,s,d),然后模拟移动,显示一些统计数据.如果你尝试的话,你可以在屏幕上看到的是每个位置的每个迷宫中的障碍物总量,以及每个迷宫的当前位置总量.这很难解释:)问我是否有问题.

再说一遍......不要介意可怕的代码.它是在20分钟内写成的

进展

我从这个用户的答案中间接得到了这个想法(之后由于某种原因被删除),并在聊天中进一步用Mooing Duck建模.我们的想法是找到一个解决迷宫右侧的序列.也就是说,解决所有迷宫中至少一半的解决方案,并且从一开始就镜像并再次运行解决剩余的迷宫.

插图:

首先找到一个序列,其第一个命令是RIGHT,它解决了这个迷宫:

0 1 0 0
0 1 0 …

寻找同步和异步递归函数的特定实现,这些函数可以用作将未来递归函数转换为平面迭代的起点.

以下是递归函数的两个示例:同步和异步.

我正在寻找的是使用没有递归的堆栈的实现.

例如,它可能会像这样工作:

var output = syncStack(myRecursiveFunctionTurnedIterative, [])

或者,如果那是不可能的,那么只需使用堆栈重新实现下面的两个函数,这应该是一个足够好的开始.例如

var stack = []

function circularReferences(object, references, stack) {
  var output = {}
  if (object.__circularid__) return true
  Object.defineProperty(object, '__circularid__', { value: id++ })
  for (var key in object) {
    var value = object[key]
    if (value && typeof value == 'object') {
      console.log(value)
      stack.push(???)
      circularReferences()
      stack.pop()
      if (is) output[key] = '[Circular]'
    } else {
      output[key] = value
    }
  }
}

这个问题的原因是,多年来我一直在努力学习如何做到这一点,但从未找到过(a)容易记住如何做的系统,以及(b)实用的系统.

同步

var …

给定 (1, 2, 3,..N) 的两个排列，

Consider for n = 5

5 4 3 2 1  
3 2 4 1 5  

在两个排列中找到使 index(a)<index(b) 的对 (a,b) 的数量？
在上述情况下，答案是 4。

(4,1) index(4)<index(1) in both permutations.
(3,1) 
(2,1)
(3,2)

我们可以在 O(n ² ) 中轻松完成此操作，但我觉得我们可以在 O(nlogn) 中完成此操作。你能帮忙吗？

另一个例子...

for n = 5

3 4 1 5 2 
1 3 2 5 4

这里的答案是 5

(3,4) index(3)<index(4) in both perms.
(3,5) index(3)<index(5) in both perms.
(3,2)
(1,5)
(1,2)  

这是我第一次尝试使用(我理解的)动态编程.我正试图解决这个有趣的问题:A*允许的启发式,用于在网格上滚动

该q函数尝试向后递归,跟踪骰子的方向(visited技术上是下一个单元格,但在递归方面"访问"以防止无限的来回循环).虽然我不确定它提供的答案是否是最佳解决方案,但它似乎确实提供了答案.

我希望有关如何实现某种记忆以加速它的想法 - 我试图实现类似memoized_fib(在这里看到)的东西lookup而不是成功,而不是!!映射q到组合列表(i,j)但是Nothing没有双关语意图.

Haskell代码:

import Data.List (minimumBy)
import Data.Ord (comparing)

fst3 (a,b,c) = a

rollDie die@[left,right,top,bottom,front,back] move
  | move == "U" = [left,right,front,back,bottom,top]
  | move == "D" = [left,right,back,front,top,bottom]
  | move == "L" = [top,bottom,right,left,front,back]
  | move == "R" = [bottom,top,left,right,front,back]

dieTop die = die!!2

leftBorder = max 0 (min startColumn endColumn - 1)
rightBorder = min columns (max …

考虑以下字母排列:

    B
   O A
  N R I
 D E N T

从顶部字母开始,选择以下两个字母之一,Plinko风格,直到你到达底部.无论你选择什么样的路径,你都会创建一个四个字母的单词:BOND,BONE,BORE,BORN,BARE,BARN,BAIN或BAIT.DENT读到底部的事实只是一个很好的巧合.

我想帮助找出一个可以设计这种布局的算法,其中从顶部到底部的每条可能路径都会从(提供的)字典中生成一个不同的单词.程序的输入将是起始字母(在该示例中为B)和字长n(在该示例中为4).它将返回组成这种布局的字母,或者返回表示不可能的消息.它不一定是确定性的,因此它可能会生成具有相同输入的不同布局.

到目前为止,我还没有想到比蛮力方法更好的东西.也就是说,对于26^[(n+2)(n-1)/2]为布局底部选择字母的所有方法,检查所有可能的2^(n-1)路径是否给出字典中的单词.我考虑过某种前缀树,但路径可以交叉并分享与我混淆的字母.我对Python最熟悉,但至少我只是想要一个可以解决这个问题的算法或方法.谢谢.

让我们N成为一个数字(10<=N<=10^5).

我必须将它分成3个数字(x,y,z),以便验证以下条件.

1. x<=y<=z 
2. x^2+y^2=z^2-1;
3. x+y+z<=N

我必须找到一个方法中给定数字可以得到多少组合.

我尝试了如下,但它需要花费很多时间才能获得更高的数字并导致超时...

int N= Int32.Parse(Console.ReadLine());
List<String> res = new List<string>();

//x<=y<=z
int mxSqrt = N - 2;
int a = 0, b = 0;
for (int z = 1; z <= mxSqrt; z++)
{
    a = z * z;
    for (int y = 1; y <= z; y++)
    {
        b = y * y;
        for (int x = 1; x <= y; x++)
        {
            int x1 …

我挑战自己写讨论到计算器的简单版本在这里,并用的方式,通过查找字符串检索运营商想出了:

ops = [("+", (+)), ("-", (-)), ("*", (*)), ("/", (/))]

这很好.
但是,当我尝试将("^",(^)),("mod",(mod))或("div",(div))添加到列表中时,我受到了欢迎:

Ambiguous type variable `a0' in the constraints:
  (Fractional a0) arising from a use of `/' at new2.hs:1:50-52
  (Integral a0) arising from a use of `mod' at new2.hs:1:65-67
  (Num a0) arising from a use of `+' at new2.hs:1:14-16
Possible cause: the monomorphism restriction...

或者,在没有(/)的情况下对六个运算符进行分组也很好,但是当我尝试创建一个可以返回七个运算符中的任何一个的函数时(通过使用if-else,或查找两个不同的函数),我给了我各种错误列表,例如).返回六个中的任何一个都很好,或仅使用(+),( - ),(*)和(/)工作正常,使用简单的函数:

findOp op = fromJust $ lookup op ops

什么是基于字符串或其他东西存储和检索这七个运算符中任何一个的便捷方法？或许我应该考虑另一种计算计算器的解析输入字符串的方法？(我认为eval和parsec被排除在此练习之外,我宁愿不使用-XNoMonomorphismRestriction,如果这是一个选项)

这是我的基本计算器,可以用正确的优先级解析+, - ,*和/,我希望继续和玩具:

import Data.Maybe

ops = [("+", (+)), ("-", (-)), …

使用以下输入，

[1, 2, 3, 4]

我正在尝试获得以下输出

[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]

目前我已经做了这样的算法，但是时间复杂度不好。

def find(height):
    num1 = 0
    out = []
    for i in range(len(height)):
        num2 = 1
        for j in range(len(height)):
            temp = []
            for x in range(num1, num2):
                temp.append(height[x])
            num2 += 1
            if temp: out.append(temp)
        num1 += 1
    return out

有什么办法可以加速该算法吗？

我对Haskell中运算符优先级的规则感到困惑.
更具体地说,为什么:

*Main> 2 * 3 `mod` 2
0

与此不同？

*Main> 2 * mod 3 2
2

如果我误用了标题中的大字,请原谅我; 我不太了解他们,但希望他们描述我的问题.我写了一个精心设计的方案来尝试根据这些要求对字符串进行编码.对于长度为10 ^ 4或更高的字符串,我编写的代码非常慢,我想知道 - 因为它一次处理200个块(尽管有时仅向前移动一个字符以获取下一个块),是否可以被修改以更快或更线性地输出结果(例如,立即输出处理的每200个字符的结果).任何有关该或其他明显优化的帮助将不胜感激.

根据电话的建议,我简化了我的例子:

encode xs = encode' xs [] where
  encode' []     result = result
  encode' (z:zs) result
    | null test = encode' zs (result ++ [z])
    | otherwise = encode' (drop numZsProcessed zs) (result ++ processed)
   where test = ..some test
         toProcess = take 200 (z:zs)
         processed = ..do something complicated with toProcess
         numZsProcessed = ..number of z's processed