Skip to content

Instantly share code, notes, and snippets.

@zyphlar
Last active Aug 29, 2015
Embed
What would you like to do?
Finding first intersection of a turtle's path (N,E,S,W)
def solution(instructions)
position = [0,0]
directions = [
[0,1], # north
[1,0], # east
[0,-1], # south
[-1,0] # west
]
current_dir = 0;
history = []
instructions.each_with_index do |num_steps,index|
direction = directions[ index % 4 ] # only 4 directions, 0th step is 0th direction
history << Array.new(position)
num_steps.times do
position[0] += direction[0]
position[1] += direction[1]
# check to see if we've passed here before
for h_pos in 0..index-1 # don't overflow and get up to the current nil step
if ( (history[h_pos][0]..history[h_pos+1][0]).include?(position[0]) and (history[h_pos][1]..history[h_pos+1][1]).include?(position[1]) )
return index+1
end
end
end
end
return 0 # no intersection
end
require 'rspec'
describe "solution finds first intersection" do
it "with given example" do
solution([1, 3, 2, 5, 4, 4, 6, 3, 2]).should == 7
end
it "one instruction" do
solution([1]).should == 0
end
it "maximal instructions" do
solution([1000000,1000000,1000000,1000000,1000000]).should == 4 # square spiral
end
it "minimal instructions" do
solution([1,1,1,1,1]).should == 4 # square spiral
end
it "no intersection" do
solution([1, 2, 3, 4, 5, 6, 7, 8, 9]).should == 0
end
end
@pmatos
Copy link

pmatos commented Apr 19, 2015

Interesting solution. It's possible to do it in O(n) time. Your solution is not O(n) though as far as I can see.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment