Sort a scrambled itinerary (Google apac test problem)

Question

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_flights)
end

def print_flights(case_num, ordered_flights) 
    flights = (0...ordered_flights.size).step(2).map {|i| ordered_flights[i] + '-' + ordered_flights[i+1] }.join ' '
    puts "CASE ##{case_num}: #{flights}"
end

while not $stdin.eof?
    num_cases = $stdin.readline.strip.to_i
    (1..num_cases).each {
        |num|
        tickets = {} 
        num_flights = $stdin.readline.strip.to_i
        (0...num_flights).each {
            tickets[$stdin.readline.strip] = $stdin.readline.strip 
        }
        ordered_flights = order_flights(tickets)
        print_flights(num, ordered_flights)
    }
end

Example input:

The first line contains the number of test cases T, after which T cases follow. For each case, it starts with an integer N. There are N flight tickets follow. Each of the next 2 lines contains the source and destination of a flight ticket.

2
1
SFO
DFW
4
MIA
ORD
DFW
JFK
SFO
DFW
JFK
MIA

Expected output:

Case #1: SFO-DFW
Case #2: SFO-DFW DFW-JFK JFK-MIA MIA-ORD

Answer 1

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.