# 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_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  • Since links can rot, please include a description of the challenge here in your question. Commented May 15, 2015 at 5:54 • @200_success is it alright to quote verbatim from the page? Should I try and give a terser description? Commented May 15, 2015 at 6:17 • @user3467349 I went ahead and added some of the text from the original problem description (shortened it a little). Most important bit is the example input and output, since that'll let reviewers verify your code and any changes they might make. Commented May 15, 2015 at 14:50 • The page says that its license is CC-BY, so it is allowable to quote verbatim. The way Flambino summarized it is good too. Commented May 15, 2015 at 14:51 ## 1 Answer ### 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|
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}:"

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.
• @user3467349 Don't say that. Cleverness is good; real cleverness is knowing when to not to be too clever :) Regardless, your code is still indisputably faster than either of my attempts. A smattering of Ruby's syntactic sugar (first, last, etc.), and it's a very neat solution. As an addendum to my previous comment, I should say that of course Rubyists care about their code's performance too, but when deciding on a speed vs expressiveness/readability trade-off, there's just that little bit of bias toward the latter. Not enough to absolve my 1st attempt, though - that's just plain slow :) Commented May 17, 2015 at 14:46