minimum_distance(CODEEVAL)

codeeval ruby

配列の距離の和の最小値を求める問題。

CHALLENGE DESCRIPTION:

Alice is looking for a sorority to join for her first year at Acme University. There is a street consisting entirely of sorority houses near the university, and some of her high school friends have already joined sorority houses on the street. (More than one of her friends may live at the same sorority house.)
　
Alice wants to visit her friends frequently, and needs a program that will help her pick an optimal house to visit them from. Each sorority house has a street number that indicates its location on the street. The optimal location will minimize the sum of differences between the number of Alice’s house and the number of her friends' houses.
　
For example: Alice’s friends live at houses 3, 3, 5, and 7. Alice moves in at house 4. Then the distances to her friends' houses are 1, 1, 1, and 3, totaling 6. 　

INPUT SAMPLE:

The input consists of several integers on a line, separated by spaces. The first integer F contains the number of friends (0 < F < 100). Then F street addresses A follow (0 < A < 10000).

4 3 3 5 7
3 20 30 40

OUTPUT SAMPLE:

6
20

CONSTRAINTS:

  1. Number of friends: 0 < F < 100
  2. Street addresses: 0 < A < 10000
  3. Number of test cases is 10.

My Code

#!/usr/bin/env ruby -w

def minimum_distance(addresses)
  distances = []
  addresses.each do |address|
    distances << addresses.inject(0) { |sum, a| sum += (a - address).abs }
  end
  distances.min
end

ARGF.each_line do |line|
  numbers = line.chomp.split.map(&:to_i)
  _firends_number = numbers.first
  addresses = numbers[1..-1]
  puts minimum_distance(addresses)
end

別解

distances の数が大量だと遅くなる。
テストデータに5000個ぐらい突っ込んで、以下のように書いて比較して見たところ、
下記の方が早かった。データの個数が少ない場合は、ほぼ同じ。

def minimum_distance(addresses)
  min_distance = nil
  addresses.each do |address|
    distance = addresses.inject(0) { |sum, a| sum += (a - address).abs }
    min_distance ||= distance
    min_distance = [min_distance, distance].min
  end
  min_distance
end

余談だけど、Benchmark#compare! ってすごい便利。何倍遅いかも表示してくれる。知らなかった。

Warming up --------------------------------------
    minimum_distance     1.000  i/100ms
   minimum_distance2   246.156k i/100ms
Calculating -------------------------------------
    minimum_distance    999.161k (± 2.5%) i/s -      2.895M
   minimum_distance2      8.381M (± 9.0%) i/s -     41.600M in   5.006365s

Comparison:
   minimum_distance2:  8381223.1 i/s
    minimum_distance:   999161.5 i/s - 8.39x  slower
require "benchmark/ips"

def minimum_distance(addresses)
  distances = []
  addresses.each do |address|
    distances << addresses.inject(0) { |sum, a| sum += (a - address).abs }
  end
  distances.min
end

def minimum_distance2(addresses)
  min_distance = nil
  addresses.each do |address|
    distance = addresses.inject(0) { |sum, a| sum += (a - address).abs }
    min_distance ||= distance
    min_distance = [min_distance, distance].min
  end
  min_distance
end

Benchmark.ips do |x|
  x.report("minimum_distance") do
    ARGF.each_line do |line|
      numbers = line.chomp.split.map(&:to_i)
      _firends_number = numbers.first
      addresses = numbers[1..-1]
      minimum_distance(addresses)
    end
  end
  x.report("minimum_distance2") do
    ARGF.each_line do |line|
      numbers = line.chomp.split.map(&:to_i)
      _firends_number = numbers.first
      addresses = numbers[1..-1]
      minimum_distance2(addresses)
    end
  end
  x.compare!
end