文章/答案/技术大牛

发布

社区首页 >问答首页 >最小跳数

问最小跳数
EN

Code Golf用户

提问于 2013-10-20 15:05:14

回答 7查看 2.1K关注 0票数 14

给定一个数字序列，找到从起始位置到终点的最小跳转次数，然后再回到起始位置。

序列中的每个元素表示从该位置移动的最大移动数。

在任何位置，你都可以跳到最大的k移动，其中k是存储在那个位置的值。到达终点后，你只能使用那些以前没有用过的跳跃姿势。

输入将给出一个由单个空格分隔的数字序列。输出应该是一个数字，这是使用的最小跳转数。如果无法到达终点并返回起始位置，则打印-1。

输入：

2 4 2 2 3 4

输出：

6人(3人到达终点，3人返回)

输入

1%0

输出

-1

Note

假设序列的所有数字都是非负的。

编辑1

这句话“因此，应该清楚，一个人总是可以跳下最后的位置。”可能会让人困惑，所以我把它从问题中删除了。这对这个问题没有任何影响。

获奖标准:

胜利者是代码最短的人。

code-golf

puzzle-solver

回答 7

Code Golf用户

发布于 2013-10-25 23:03:29

APL(Dyalog)，116

f←{{⊃,/{2>|≡⍵:⊂⍵⋄⍵}¨⍵}⍣≡1{(⍴⍵)≤y←⊃⍺:⍵⋄⍵[y]=0:0⋄x←⍵⋄x[y]←0⋄∇∘x¨,∘⍺¨y+⍳y⌷⍵},⍵}
{0≡+/⍵:¯1⋄(⌊/+/0=⍵)-+/0=x}↑⊃,/f¨⌽¨f x←⎕

测试用例

      2 4 2 2 3 4 2 2
6
      1 0
¯1
      1 1 1 1
¯1
      3 1 2 0 4
3
      1
0

逼近

该方法是使用递归函数进行蛮力搜索。

从位置1开始，将当前位置的值设置为0，并生成可以从当前位置跳到的位置数组。将新位置和修改后的数组传递给自己。基本情况是当当前位置的值为0(不能跳转)或到达末尾时。

然后，对于生成的每个数组，将其反转并再次进行搜索。因为跳转位置设置为0，所以我们不能再从那里跳下去。

对于最后到达的数组，找出最小个数为0's的数组，减去初始数组中0's的个数，得到实际执行的跳转次数。

票数 4

Code Golf用户

发布于 2013-10-22 03:21:13

Mathematica 351

注:这还没有完全高尔夫；而且，输入需要调整，以适应所需的格式。而且，不跳到同一位置的两倍规则需要实施。还有一些代码格式化问题需要解决。但这是个开始。

图由对应于每个位置的节点构成，即表示跳转的每个输入数字。DirectedEdge[node1, node2]表示从node1跳到节点2是可能的。最短路径是从开始到结束，然后从端到开始。

f@j_:=
(d={v=FromCharacterCode/@(Range[Length[j]]+96),j}\[Transpose];
w[n_,o_:"+"]:={d[[n,1]],FromCharacterCode/@(ToCharacterCode[d[[n,1]]][[1]]+Range[d[[n,2]]]  
If[o=="+",1,-1])};
  
y=Graph[Flatten[Thread[DirectedEdge[#1,#2]]&@@@(Join[w[#]&/@Range[8],w[#,3]&/@Range[8]])]];

(Length[Join[FindShortestPath[y,v[[1]],v[[-1]]],FindShortestPath[y,v[[-1]],v[[1]]]]]-2)
/.{0-> -1})

使用

f[{2,4,2,2,3,4,2,2}]
f[{3,4,0,0,6}]
f[{1,0}]

6 3 -1

票数 3

Code Golf用户

发布于 2013-10-22 21:17:20

Python 304

我认为这个新方法解决了(我希望！)与2,0案及类似案件有关的所有问题：

在这个版本中，输入序列被遍历(如果可能的话)直到结束，然后我们用反向序列再次开始这个过程。现在我们可以保证，对于每一个有效的解决方案，其中一个跳转到最后一个元素上。

## Back and forward version

# Changed: now the possible jumps from a given L[i] position  
# are at most until the end of the sequence 
def AvailableJumps(L,i): return range(1,min(L[i]+1,len(L)-i))

# In this version we add a boolean variable bkw to keep track of the
# direction in which the sequence is being traversed
def Jumps(L,i,n,S,bkw):
    # If we reach the end of the sequence...
    # ...append the new solution if going backwards
    if (bkw & (i == len(L)-1)): 
            S.append(n)
    else:
        # ...or start again from 0 with the reversed sequence if going forward
        if (i == len(L)-1):
            Jumps(L[::-1],0,n,S,True)    
        else:
            Laux = list(L)
            # Now we only have to disable one single position each time
            Laux[i] = 0
            for j in AvailableJumps(L,i):
                Jumps(Laux,i+j,n+1,S,bkw)

def MiniJumpBF(L):
    S = []        
    Jumps(L,0,0,S,False)
    return min(S) if (S) else -1

这些是金色的版本：

def J(L,i,n,S,b):
    if (i == len(L)-1):
        S.append(n) if b else J(L[::-1],0,n,S,True)
    else:
        L2 = list(L)
        L2[i] = 0
        for j in range(1,min(L[i]+1,len(L)-i)):
            J(L2,i+j,n+1,S,b)
def MJ(L):
    S = []        
    J(L,0,0,S,False)
    return min(S) if (S) else -1

还有一些例子：

MJ( [2, 4, 2, 2, 3, 4, 2, 2] ) -->  6
MJ( [0, 2, 4, 2, 2, 3, 4, 2, 2] ) -->  -1
MJ( [3, 0, 0, 1, 4] ) -->  3
MJ( [2, 0] ) -->  -1
MJ( [1] ) -->  0
MJ( [10, 0, 0, 0, 0, 0, 10, 0, 0, 0, 10, 0, 0, 0, 0, 0, 10] ) -->  4
MJ( [3, 2, 3, 2, 1] ) -->  5
MJ( [1, 1, 1, 1, 1, 1, 6] ) -->  7
MJ( [7, 1, 1, 1, 1, 1, 1, 7] ) -->  2

票数 3

页面原文内容由Code Golf提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://codegolf.stackexchange.com/questions/12931

复制

相似问题

问最小跳数
EN

输入：

输出：

输入

输出

Note

编辑1

获奖标准:

回答 7

Code Golf用户

APL(Dyalog)，116

测试用例

逼近

Code Golf用户

Mathematica 351

使用

Code Golf用户

Python 304

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问最小跳数EN

输入：

输出：

输入

输出

Note

编辑1

获奖标准:

回答 7

Code Golf用户

APL(Dyalog)，116

测试用例

逼近

Code Golf用户

Mathematica 351

使用

Code Golf用户

Python 304

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问最小跳数
EN