curious_george
BAN USERAssuming they don't want the answer array in the same order as the original array, sorting first works fine.
- curious_george April 18, 2013Just noticed this doesn't handle situations where there is no solution. Oh well.
- curious_george April 18, 2013Given a start and end point, this finds the shortest path using BFS. I start count at 1 instead of 0 (and subtract 1 from count at the end) to keep the counting of squares from being mistaken as open spaces (1s). Not entirely sure how to have it *only* print the correct path, though....
def maze_bfs(maze, current, end_point, count=1)
current_x, current_y = current[0], current[1]
count += 1
maze[current_x][current_y] = count
if current == end_point
puts "*** count = #{count - 1}"
maze.each do |array|
puts array.inspect
end
return
end
if current_x > 0 && maze[current_x - 1][current_y] == 1
maze_bfs(maze, [current_x - 1, current_y], end_point, count)
end
if current_y > 0 && maze[current_x][current_y - 1] == 1
maze_bfs(maze, [current_x, current_y - 1], end_point, count)
end
if current_x < maze[0].length - 1 && maze[current_x + 1][current_y] == 1
maze_bfs(maze, [current_x + 1, current_y], end_point, count)
end
if current_y < maze.length - 1 && maze[current_x][current_y + 1] == 1
maze_bfs(maze, [current_x, current_y + 1], end_point, count)
end
end
maze = [
[0,0,1,1,1,0,0,0,1,1],
[0,0,1,0,0,0,0,0,1,0],
[0,0,1,1,1,1,1,1,1,0],
[0,0,0,1,0,0,0,0,1,0],
[0,0,0,1,1,1,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0],
[0,0,1,0,1,0,0,0,0,0],
[0,0,1,1,1,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0],
[0,0,0,1,0,0,0,0,0,0]
]
>> maze_bfs maze, [0, 9], [9, 3]
[0, 0, 12, 13, 14, 0, 0, 0, 2, 1]
[0, 0, 11, 0, 0, 0, 0, 0, 3, 0]
[0, 0, 10, 9, 8, 7, 6, 5, 4, 0]
[0, 0, 0, 10, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 11, 12, 1, 0, 0, 0, 0]
[0, 0, 0, 0, 13, 0, 0, 0, 0, 0]
[0, 0, 18, 0, 14, 0, 0, 0, 0, 0]
[0, 0, 17, 16, 15, 0, 0, 0, 0, 0]
[0, 0, 0, 17, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 18, 0, 0, 0, 0, 0, 0]
Not enough Ruby around here. I'm not sure how efficient this is given it backtracks over the result array when it's necessary. But it works. The instructions don't say what to do if there is no next greatest integer (like in the example [4, 45, 2, 25]) so in those cases I print -1.
def next_greatest_element(input)
return if input.nil? || input.empty?
length = input.length
answer = [-1] * (length)
tmp = -1
(input.length - 2).downto(0) do |index|
if input[index + 1] > input[index]
answer[index] = input[index + 1]
else
tmp_index = index + 1
while tmp_index < answer.length
if answer[tmp_index] > input[index]
answer[index] = answer[tmp_index]
break
end
tmp_index += 1
end
end
end
answer.join(', ')
end
>> next_greatest_element nil
=> nil
>> next_greatest_element [4, 45, 2, 25]
=> "45, -1, 25, -1"
>> next_greatest_element [4, 5, 25, 2, 30]
=> "5, 25, 30, 30, -1"
>> next_greatest_element [4, 5, 2, 25]
=> "5, 25, 25, -1"
>> next_greatest_element [10, 9, 8, 6, 2, 3, 1, 7, 11]
=> "11, 11, 11, 7, 3, 7, 7, 11, -1"
This is just a traversal. I chose pre-order b/c it made returning the Linked List easier. In Ruby!!
class << self
attr_accessor :linked_list
end
def self.convert_to_doubly_linked_list(root, current_pointer=nil)
return linked_list unless root
unless current_pointer
self.linked_list = LinkedList.new
linked_list.head = current_pointer = ListElement.new(root.value)
end
current_pointer.previous = ListElement.new(root.left.value) if root.left
current_pointer.next = ListElement.new(root.right.value) if root.right
convert_to_doubly_linked_list(root.left, current_pointer.previous)
convert_to_doubly_linked_list(root.right, current_pointer.next)
end
O(n) b/c it's a traversal.
>> head
=> ListElement: data = 100
>> head.next.next
=> ListElement: data = 175
>> head.previous.previous
=> ListElement: data = 25
Calculating the length of the list before you start is completely unnecessary. I agree with algos's solution. Here's the Ruby implementation of it.
- curious_george April 18, 2013