确定一辆汽车是否能用有限的汽油绕过一条路线。

Question

使用任何支持函数的编程语言，都具有以下功能

is_enough(strArr) 

它采用strArr，它将是一个由以下元素组成的数组：

• N，它将是一个循环路线上加油站的数量。
• 每个后续元素都是字符串g:c，其中
  • g是那个加油站里加仑的煤气量，
  • c将是到达以下加油站所需的加仑汽油量。

例如，strArr可能是：

["4","3:1","2:2","1:2","0:1"]. 

您的目标是返回启动加油站的索引，这将使您可以绕整个路线一次，否则返回字符串“不可能”。

对于上面的例子，有4个加油站，您的程序应该返回字符串"1“，因为：

• 从1站开始，你会收到3加仑的汽油，然后花1加仑到下一站。
• 然后你有2加仑+2在下一个站，你花了2加仑，所以你有2加仑当你到达第三站。
• 然后你有3个，但你花了2个到达最后的车站，
• 在最后一站，你得到0加仑，你花你的最后一加仑达到你的起点。

从任何其他加油站出发都不可能绕开路线，所以答案是"1“。

如果有多个加油站可以启动，返回最小的指数(加油站)。N将是>= 2。

正确的样本输出：

Input: ["4","1:1","2:2","1:2","0:1"]
Output: "impossible"

Input: ["4","0:1","2:2","1:2","3:1"]
Output: "4"

获胜者将使用最短的代码，尽管它将是长的。

Answer 1

Ruby，111

下面是一个使用eval的Ruby解决方案：

is_enough=->a{_,*s=a
"#{(1..s.size).find{|i|g=0;s.rotate(i-1).all?{|x|g+=eval x.tr ?:,?-;g>=0}}||:impossible}"}

示例用法：

is_enough[%w(4 3:1 2:2 1:2 0:1)] #=> "1"
is_enough[%w(4 1:1 2:2 1:2 0:1)] #=> "impossible"
is_enough[%w(4 0:1 2:2 1:2 3:1)] #=> "4"
is_enough[%w(4 1:2 2:1 4:3 0:1)] #=> "2"
is_enough[%w(4 0:1 2:2 1:2 3:1)] #=> "4"
is_enough[%w(4 0:1 0:1 4:1 0:1)] #=> "3"
is_enough[%w(8 0:1 0:1 4:1 0:1 2:1 3:1 0:0 0:1)] #=> "3"

编辑:修正的函数名和返回类型。

Answer 2

APL (70)

{×⍴G←Z/⍨0∧.≤¨+\¨¯1⌽⌽∘K¨Z←⍳⍴K←{⎕ML←3⋄-/⍎¨⍵⊂⍨⍵≠':'}¨1↓⍵:⊃G⋄'impossible'}

解释：

• 1↓⍵：删除第一个元素(长度)，我们不需要它
• {.}¨：每个加油站.
  • ⎕ML←3：在内部函数中将⎕ML设置为3(更改⊂的行为)
  • ⍵⊂⍨⍵≠':'：在:上拆分字符串
  • ⍎¨：评估每个部分
  • -/：从第一个加油站减去第二个数字(给出每个加油站的净效果)

• K←：将它们存储在K中
• Z←⍳⍴K：获取加油站的索引(1到K的长度)，存储在Z
• ⌽∘K¨Z：按Z的每个值旋转K，给出一个数组
• ¯1⌽：将该数组左转1(将未更改的数组放在前面而不是最后)
• +\¨：为每个内部数组创建一个运行和
• 0∧.≤¨：对于每个运行的和，看看是否有负值
• Z/⍨：从Z中选择运行和没有负值的元素
• ×⍴G←：商店在G。如果G有任何元素：
• :⊃G：返回G的第一个元素。
• ⋄'impossible'：否则，返回impossible。

Answer 3

Ruby 132

g=->a{n,*a=a.map{|e|e.split(?:).map &:to_i}
(r=(0...n[0]).find{|i|a.rotate(i).inject(0){|m,(j,k)|m&&m>=0&&m+j-k}})?r+1:"impossible"}

测试：

irb(main):003:0> g[["4","1:1","2:2","1:2","0:1"]]
=> "impossible"
irb(main):004:0> g[["4","0:1","2:2","1:2","3:1"]]
=> 4