Bristol Challenge NN Algorithm source

bristol-nn.rb

# nearest neighbour
# coded in the ugliest way possible :) ouch, mapreduce!

vertices = 91
puts 'Enter distances'
distances = Array.new(vertices) { gets.chomp.split(';').map {|n| n.to_i } }
puts 'Enter durations'
durations = Array.new(vertices) { gets.chomp.split(';').map {|n| n.to_i } }
puts 'Enter place names'
placenames = Array.new(vertices) { gets.chomp.split(';') }
p durations
puts 'Enter weights'
weights = gets.chomp.split(';').map {|n| n.to_f * 1.2}

def dp(n)
  return '%.2f' % n
end

def nn(a, vw, s, placenames, distances)
  hotel = 'Temple Way, Bristol BS1 6BF'
  can_pass = (0...91).to_a
  route = [s]
  messages = []
  total_time = vw[route.last]
  total_dist = 0
  day = 1
  new_day = true
  day_time = 0
  md = 0
  until can_pass.empty?
    sort_symb = :dur
    
    next_vert = (0...91).to_a
      .select {|v| can_pass.include? v}
      .map {|v| {:v => v, :dist => distances[route.last][v], :dur => a[route.last][v]}}
      .sort {|v, w| v[sort_symb] <=> w[sort_symb]}
      .first
    route.push next_vert[:v]
    
    travel_dist = next_vert[:dist]
    travel_time = next_vert[:dur]
    spend_time = vw[next_vert[:v]] * 60
    
    unless new_day
      messages.push "Travel #{dp(travel_dist / 1000.0)} km taking #{dp(travel_time / 60.0)} min"
      total_time += travel_time
      day_time += travel_time
      total_dist += travel_dist
    else
      messages.push "Travel  km from hotel taking  min"
      messages.push "@@ DISTANCE FROM #{hotel} TO #{placenames[route.last][2]},#{placenames[route.last][3]}"
      md = day_time if day_time > md
      day_time = 0
    end
    new_day = false
    
    messages.push "Stay at #{placenames[route.last][1]} for #{dp(spend_time / 60.0)} min"
    total_time += spend_time
    day_time += spend_time
    
    if day_time >= 3600 * 8.2 #|| next_vert[:v] == 66 - 1 # st. george's
      new_day = true
      messages.push "Travel  km to hotel taking  min"
      messages.push "@@ DISTANCE FROM #{placenames[route.last][2]},#{placenames[route.last][3]} TO #{hotel}"
      messages.push "End of day #{day}"
      messages.push "Spent #{dp(day_time / 3600.0)} hours travelling Bristol today"
      messages.push "(stay at hotel)"
      day += 1
      messages.push "Start of day #{day}"
    end
    
    can_pass.delete next_vert[:v]
  end
  messages.push "Total distance travelled: #{dp(total_dist / 1000.0)} km"
  return {:r => route, :w => total_time, :m => messages, :d => md}
end

routes = (0...vertices).to_a.map {|v| nn(durations, weights, v, placenames, distances)}
shortest = routes.sort {|v, w| v[:w] <=> w[:w]}.first
#shortest = nn(durations, weights, 0, placenames, distances)
p shortest[:w]
shortest[:m].each {|s| puts s}