Sort a scrambled itinerary (Google apac test problem)

This is my first time writing ruby - and I was mainly hoping to get some feedback and stylistic pointers.

The algorithm is pretty straight-forward, since Google guarantees airports aren't repeated I store all the tickets in a hash table and then sort from random insertion points, which should be worst case \$O(n \log n)\$.

Original problem description


Once upon a day, Mary bought a one-way ticket from somewhere to somewhere with some flight transfers. For example: SFO->DFW DFW->JFK JFK->MIA MIA->ORD.


Unfortunately, after she received the tickets, she messed up the tickets and she forgot the order of the tickets.


Help Mary rearrange the tickets to make the tickets in correct order.

```
def merge_ordered_flights(ordered_flights)
while ordered_flights.size > 1
flights = ordered_flights.pop
ordered_flights.each do |a|
if a[0] == flights[-1]
a.insert(0, *flights)
break
elsif a[-1] == flights[0]
a.insert(-1, *flights)
break
end
end
end
return ordered_flights[0] #flatten
end

def order_flights(tickets)
ordered_flights = []
iter = 0
while true
#Get an arbitrary arrival, destination flight pair
arv, dest = tickets.shift
if arv == nil
break #Done if we are out of tickets
end
ordered_flights[iter] = []
ordered_flights[iter].push(arv, dest)
#And append follow-up destinations until we can't find one
#(It's the final destination, or the other tickets have already been sorted)
while true
arv = dest
dest = tickets.delete(dest)
if dest == nil
break #End of current chain
end
ordered_flights[iter].push(arv, dest)
end
iter += 1
end
#Now combine the ordered flight arrays into a single array
return merge_ordered_flights(ordered

Style notes:

• The Ruby convention is 2 spaces of indentation

• Use braces for single-line blocks, but do...end for multi-line blocks.

-
Keep the block parameters on the starting line; i.e. don't do this

(1..num_cases).each {
    |num|

-
Use #nil? rather than == nil, empty? when checking array lengths, #first/#last when accessing the start/end of an array, etc..

-
Postfix conditions for single-line, single-branch conditionals. E.g. this:

if arv == nil 
    break #Done if we are out of tickets
end

becomes:

break if arv.nil? # Done if we are out of tickets

-
Instead of iterating through ranges like (0...n) you can use n.times instead. E.g. n.times { |i| puts i } will produce the same as (0...n).each { |i| puts i }

-
You missed a single pair of parentheses in a method call: .join ' ' :)

Granted, you can write Ruby without parentheses (Seattle style Ruby). Personally though, I like 'em (except for puts and print), but there are arguments for and against.

Code notes:

Instead of $stdin.readline.strip, you can use the more common gets.chomp. #gets is just a shortcut for $stdin.readline, and #chomp chops off the linebreak, but leaves other whitespace intact.

When possible use methods like #map and #reduce and their ilk instead of modifying a closed-over object from inside a block. E.g. this:

tickets = {} 
# ...
(0...num_flights).each {
    tickets[$stdin.readline.strip] = $stdin.readline.strip 
}

can be written in a few different ways - #each_with_object is probably the cleanest:

tickets = num_flights.times.each_with_object({}) do |_, tickets|
  tickets[gets.chomp] = gets.chomp
end

Alternatively, you could read the lines, and chunk them up afterward:

lines = (num_flights * 2).times { gets.chomp }
tickets = Hash[ lines.each_slice(2).to_a ]

You can do something similar in #print_flights instead of using step(2):

def print_flights(case_num, ordered_flights)
  tickets = ordered_flights.each_slice(2).map { |pair| pair.join("-") }
  puts "CASE ##{case_num}: #{tickets.join(" ")}"
end

Typically, Ruby coders avoid "raw" array indices and index arithmetic like array[i+1] in favor of more expressive code.

Lastly, #order_flights has side-effects: It deletes entries from the tickets hash you pass to it. Sure, it doesn't matter for this particular exercise, but side-effects are side-effects and should be avoided.

The algorithm itself looks fine to me. I might write it like so:

def read_tickets
  count = gets.chomp.to_i
  count.times.map do
    [gets.chomp, gets.chomp]
  end
end

def sort_tickets(tickets)
  flights = tickets.dup # make a copy to modify
  stops = flights.shift
  until flights.empty?
    from, to = flights.shift
    if from == stops.last
      stops.push(to) # could also use <<, but #push keeps "symmetry" with #unshift
    elsif to == stops.first
      stops.unshift(from)
    else
      flights.push [from, to]
    end
  end
  stops.each_cons(2).to_a
end

case_count = gets.chomp.to_i
case_count.times do |t|
  tickets = read_tickets
  ordered = sort_tickets(tickets).map { |ticket| ticket.join("-") }
  puts "Case ##{t+1}: #{ordered.join(" ")}"
end

Pretty much the same algorithm, just written differently. Notice however that I never actually use hashes, just nested arrays. Unfortunately, it's sloooow (the else branch and #each_cons are probably to blame, but I haven't checked). Still, style-wise it might give you some ideas.

An alternative, which does use hashes, would be to scan the tickets to find the first leg of the journey. After that, a single loop through should put them in order.

def read_tickets
  count = gets.chomp.to_i
  count.times.each_with_object({}) do |_, tickets|
    tickets[gets.chomp] = gets.chomp
  end
end

def print_sorted_tickets(tickets)
  inverted = tickets.invert
  from, to = tickets.detect { |from, to| inverted[from].nil? } # find first
  print " #{from}-#{to}"
  while tickets[to]
    from, to = [to, tickets[to]]
    print " #{from}-#{to}"
  end
  print "\n"
end

case_count = gets.chomp.to_i
case_count.times do |t|
  print "Case ##{t+1}:"
  tickets = read_tickets
  print_sorted_tickets(tickets)
end

I've combined sorting and printing only because I can. I'd prefer sorting and then printing, like above, or at least returning a string. The code can easily be changed to support that, but I figured I'd try combining the two. And this runs about as fast as your solution (somewhat surprisingly - I figured #invert would be more expensive).

By the way, one could "manually" create the inverse hash immediately when reading the input, instead of using #invert. But I don't think it'll make that much difference. Either case would be trading memory for simplicity.

StackExchange Code Review Q#90799, answer score: 3