# Determine whether a car can get around a route with a limited amount of gas

Using any programming language that supports functions, have the function

``````is_enough(strArr)
``````

that take `strArr` which will be an an array consisting of the following elements:

• `N` which will be the number of gas stations in a circular route
• and each subsequent element will be the string `g:c` where
• `g` is the amount of gas in gallons at that gas station and
• `c` will be the amount of gallons of gas needed to get to the following gas station.

For example `strArr` may be:

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

Your goal is to return the index of the starting gas station that will allow you to travel around the whole route once, otherwise return the string "impossible".

For the example above there are 4 gas stations, and your program should return the string "1" because:

• Starting at station 1 you receive 3 gallons of gas and spend 1 getting to the next station.

• Then you have 2 gallons + 2 more at the next station and you spend 2 so you have 2 gallons when you get to the 3rd station.

• You then have 3 but you spend 2 getting to the final station,

• At the final station you receive 0 gallons and you spend your final gallon getting to your starting point.

Starting at any other gas station would make getting around the route impossible, so the answer is "1".

If there are multiple gas stations that are possible to start at, return the smallest index (of the gas station). `N` will be `>= 2`.

Correct Sample Outputs:

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

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

The winner will be the one to use the shortest code although it will be long.

-
What's the objective winning criterion? I'm voting to close because there's no way to tell who the winner is. – Doorknob Feb 4 '14 at 17:54
Just put a code-golf tag on it and it'll be ok. – daniero Feb 4 '14 at 18:10
Voting to close just because of a missing tag is a bit draconian, wouldn’t you say? Just add the tag. – Timwi Feb 4 '14 at 18:33
Are there always precisely `N+1` elements in `strArr`? This would make `N` redundant in case the language already provides a way of getting the length of the array, right? (it'd still be useful for e.g. C though.) – FireFly Feb 4 '14 at 18:45
Two of the answers are interpreting the spec as requiring the name `is_enough` (9 chars); three are using a single-char name, and one doesn't name the function at all. Could you please clarify what is permissible? – Peter Taylor Feb 4 '14 at 23:28

## APL (70)

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

Explanation:

• `1↓⍵`: drop the first element (length), we don't need it
• `{`...`}¨`: for each of the gas stations...
• `⎕ML←3`: set `⎕ML` to 3 within the inner function (changes behaviour of `⊂`)
• `⍵⊂⍨⍵≠':'`: split the string on `:`
• `⍎¨`: evaluate each part
• `-/`: subtract the second number from the first (giving net effect for each gas station)
• `K←`: store them in K
• `Z←⍳⍴K`: get the indices for the gas station (`1` to length of `K`), store in `Z`
• `⌽∘K¨Z`: rotate `K` by each value of `Z`, giving an array of arrays
• `¯1⌽`: rotate this array to the left by 1 (to put the unchanged one first instead of last)
• `+\¨`: make a running sum for each inner array
• `0∧.≤¨`: for each running sum, see if there are negative values
• `Z/⍨`: select from `Z` those elements for which the running sum had no negative values
• `×⍴G←`: store in `G`. If `G` has any elements:
• `:⊃G`: return the first element of `G`.
• `⋄'impossible'`: otherwise, return `impossible`.
-

# Bash 178170161 157

Rather straight forward.

``````is_enough(){((t=(n=\$1-1)<0))&&echo impossible||(x=(n \${@:3} \$2);for z in \${@:2};do(((t+=\${z%:*}-\${z#*:})<0))&&is_enough \${x[*]}&&return;done;echo \$[\$#-++n])}
``````

Spaced out:

``````is_enough() {
((t=(n=\$1-1)<0)) && echo impossible || (
x=(n \${@:3} \$2);
for z in \${@:2};do
(((t+=\${z%:*}-\${z#*:})<0)) && is_enough \${x[*]} && return;
done;
echo \$[\$#-++n]
)
}
``````
-

## Ruby, 111

Here's a Ruby solution using `eval`:

``````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}"}
``````

Example usage:

``````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"
``````

EDIT: Corrected function name and return type.

-

# 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"}
``````

Test:

``````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
``````
-
Spec requires a string to be returned in all cases. – boothby Feb 4 '14 at 21:26
@boothby I can't find that requirement anywhere in the spec. Can you quote? – Jan Dvorak Feb 4 '14 at 22:01
For the example above there are 4 gas stations, and your program should return the string "1" because: – boothby Feb 4 '14 at 23:41
Ah screw it; Chron's solution is much shorter anyways :D – daniero Feb 5 '14 at 13:16

## Python, 131

I find this one-liner fairly satisfying.

``````E=lambda s:([`i`for i in range(1,len(s)+1)if reduce(lambda r,t:r+eval(t[0]+'-'+t[-1])*(r>=0),s[i:]+s[1:i],0)>=0]+['impossible'])[0]
``````
-

## GolfScript (72 chars)

``````{(~\{':'/{~}/-}%[\),1>{;.{1\$-1>*+}*-1>\(+\},~"impossible"]1=}:is_enough;
``````

Online demo

This performs the obvious brute force approach. The most interesting bit IMO is the determination of whether the partial sums of an array of delta-fuel ever drops below 0:

``````{1\$-1>*+}*-1>
``````

This saves 1 char over the more obvious

``````[{1\$+}*]{0<},!
``````

If the output were indexed at 0 rather than at 1, an alternative approach to rotating the array would be preferable:

``````{(;{':'/{~}/-}%:A[,,{A\{(+}*{1\$-1>*+}*-1>},~"impossible"]0=}:is_enough;
``````

But this approach isn't easily adopted to indexing at 1:

``````{(;{':'/{~}/-}%:A[,),1>{A\({(+}*{1\$-1>*+}*-1>},~"impossible"]0=}:is_enough;
``````

or

``````{(;{':'/{~}/-}%:A[,,{A\{(+}*{1\$-1>*+}*-1>},{)}%~"impossible"]0=}:is_enough;
``````
-