Pick "least congested" number in a Ruby array

Question

I have an intellectual curiosity that I would love your thoughts on. Don't necessarily need a whole solution; just want to get more eyes on it.

Given:

• An array of integers (with the possibility of duplicates)
• A range of "acceptable" integers to choose from.

Problem:

Weight the integers in r based on how "congested" they are in a. Two factors go into how "congested" an integer is:

1. How many times does it appear in the a? The more frequent, the more congested.
2. How many immediate neighbors does it have? The closer the neighbors, the more congested.

#1 weights much more heavily than #2 (how much? not sure; I just think it ought to be "a lot").

Example:

a = [1, 1, 2, 4, 6, 8, 8, 8, 8, 9, 10, 10]

r = (1..11)

Solution Idea:

Here's a quick (and dirty, definitely) solution that I came up with; seems to do the job:

$a = [1, 1, 2, 4, 6, 8, 8, 8, 8, 9, 10, 10]
$r = (1..11)

def how_congested?(integer)
  ((10 * $a.count(integer) + 2.5 * number_of_neighbors(integer))/100)
end

def number_of_neighbors(integer)
  count = 0
  hash = Hash[$a.uniq.map.with_index.to_a]
  index = hash[integer]

  count += 1 unless hash[integer + 1].nil?
  count += 1 unless hash[integer - 1].nil?
  count
end

$r.each do |i|
  puts "Congestion of ##{ i }: #{ how_congested?(i) }"
end

# Congestion of #1: 0.225
# Congestion of #2: 0.125
# Congestion of #3: 0.05
# Congestion of #4: 0.1
# Congestion of #5: 0.05
# Congestion of #6: 0.1
# Congestion of #7: 0.05
# Congestion of #8: 0.425
# Congestion of #9: 0.15
# Congestion of #10: 0.225
# Congestion of #11: 0.025

Issue:

• This takes into account immediate neighbors, but not neighbors 2 spots away, 3 spots away, etc. I think there should be some sort of sliding scale (e.g., "next-door" neighbors count 2x as much as neighbors 2 spots away, etc.).
• I came up with this "algorithm" on a napkin, but I'm wondering if there's a more intelligent way to do it?

Appreciate your thoughts!

Answer 1

Check this out:

class Congestion
  attr_accessor :array, :range

  def initialize(array, range)
    @array = array
    @range = range
  end

  def how_congested?(integer)
    ((10 * self.array.count(integer) + 2.5 * weight_of_neighbors(integer)) / 100)
  end

  def weight_of_neighbors(integer)
    weight = 0
    @array.uniq.each do |elem|
      weight += case (elem - integer).abs
                when 1 then 3
                when 2 then 2
                when 3 then 1.5
                when 4 then 1.25
                when 5 then 1
                else 0
                end
    end
    weight
  end

  def calculate
    self.range.each do |i|
      congestion = how_congested?(i)
      puts "Congestion of #{i}: #{congestion}"
    end
  end
end

a = [1, 1, 2, 4, 6, 8, 8, 8, 8, 9, 10, 10]
r = (1..11)

c = Congestion.new(a, r)
c.calculate

Which ends up looking like this:

# Congestion of 1: 0.3375
# Congestion of 2: 0.25625
# Congestion of 3: 0.2625
# Congestion of 4: 0.29375
# Congestion of 5: 0.3125
# Congestion of 6: 0.325
# Congestion of 7: 0.3
# Congestion of 8: 0.60625
# Congestion of 9: 0.3125
# Congestion of 10: 0.35625
# Congestion of 11: 0.1875

Basically the relevant change here is that it takes the integer we are interested in, subtracts it from the current element of the array, then gets the positive version of that number.