banal.rb

#banal.rb


def banal(ary)
  b = c = ary
  unless ary.size <= 2
    b = banal(ary[0..(ary.size/2)-1])
    c = banal(ary[(ary.size/2)..-1])
  else
    if b[0] == c[0] 
      return b[0]
    else
      return nil
    end
  end
  
  if b == c
    return b
  else
    return guess(b,c,ary)
  end
end

def guess(b,c,ary)
  bs = ary.select {|x| x == b}
  cs = ary.select {|x| x == c}
  if bs.size <= ary.size/2 and cs.size <= ary.size/2
    return nil
  elsif bs.size > cs.size
    return b
  elsif cs.size > bs.size
    return c
  end
end

def genCase
  x = []
  1000.times do 
    if rand(10) == 9
      x << rand(9)
    else
      x << 0
    end
  end
  return x
end

10.times do 
  arr = genCase
  p arr.size, arr.count(0), banal(arr)
end

p banal([0,0,1,1])
p banal([0,1,2,3,4,5,6,7,8,9,1,2,3,4,5])