There are a **n** balls numbered from 0 to **n-1** (0,1,2,3,etc). Most of them have the same weight, but one is heavier. Your task is to find it.

Your function will receive two arguments - a `scales` object, and a ball count. The `scales` object has only one method:

```python
    get_weight(left, right)
```

where `left` and `right` are arrays of numbers of balls to put on left and right pan respectively.

If the method returns `-1` - left pan is heavier

If the method returns `1` - right pan is heavier

If the method returns `0` - both pans weigh the same

So what makes this the "ubermaster" version of this kata? First, it's not restricted to 8 balls as in the previous versions - your solution has to work for 8-500 balls. 

Second, you can't use the scale any more than mathematically necessary. Here's a chart:

    ball count | uses
    -----------------
           0-9 |    2
         10-27 |    3
         28-81 |    4
        82-243 |    5
       244-500 |    6

Too hard? Try lower levels by [tiriana](http://www.codewars.com/users/tiriana):

* [novice](http://www.codewars.com/kata/544047f0cf362503e000036e)
* [conqueror](http://www.codewars.com/kata/54404a06cf36258b08000364)
* [master](http://www.codewars.com/kata/find-heavy-ball-level-master)

Source: codewars | Difficulty: EASY
Tags: Ad-hoc

Starter code: def find_ball(scales, ball_count):
	

Solutions:
def find_ball(scales, n):
	select = list(range(n))
	while len(select) > 1:
		(left, right, unused) = (select[::3], select[1::3], select[2::3])
		if len(select) % 3 == 1:
			unused.append(left.pop())
		select = [left, unused, right][scales.get_weight(left, right) + 1]
	return select.pop()


def find_ball(scales, ball_count):
	balls = range(ball_count)
	while len(balls) > 1:
		x = len(balls) / 3 + (len(balls) % 3 > 0)
		(j, k, l) = (balls[:x], balls[x:x * 2], balls[x * 2:])
		balls = [l, k, j][scales.get_weight(j, k)]
	return balls[0]


from math import ceil

def find_ball(scales, n):
	li = list(range(n))
	while len(li) != 1:
		d = ceil(len(li) / 3)
		who = scales.get_weight(li[:d], li[-d:])
		li = [li[d:-d], li[-d:], li[:d]][who]
	return li[0]


def find_ball(scales, ball_count):

	def find_number(numbers):
		length = len(numbers)
		if length == 1:
			return numbers[0]
		n = length // 3 + (length % 3 == 2)
		(left, right, remaining) = (numbers[:n], numbers[n:2 * n], numbers[2 * n:])
		result = scales.get_weight(left, right)
		if result < 0:
			return find_number(left)
		elif result > 0:
			return find_number(right)
		else:
			return find_number(remaining)
	return find_number(list(range(ball_count)))


import math

def find_ball(scales, lRange):
	if type(lRange) == int:
		lRange = range(lRange)
	if len(lRange) == 1:
		return lRange[0]
	slice = int(math.ceil(len(lRange) / 3.0))
	res = scales.get_weight(lRange[:slice], lRange[slice:slice * 2])
	if res == -1:
		return find_ball(scales, lRange[:slice])
	elif res == 1:
		return find_ball(scales, lRange[slice:slice * 2])
	else:
		return find_ball(scales, lRange[slice * 2:])


import math as m

def find_baller(s, r):
	count = len(r)
	if count == 1:
		return r[0]
	size = 3 ** (m.ceil(m.log(count, 3)) - 1)
	x = size
	if size > count - size:
		x -= 2 * size - count
	parts = [r[:x], r[x:-x], r[-x:]]
	x = s.get_weight(parts[0], parts[2]) + 1
	print(x)
	return find_baller(s, parts[x])

def find_ball(s, count):
	return find_baller(s, list(range(count)))


from math import log

def find_ball(scales, ball_count):
	count = 2 if ball_count <= 9 else int(log(ball_count, 3)) + 1 if str(log(ball_count, 3))[-2:] != '.0' else int(log(ball_count, 3))
	res = [i for i in range(ball_count)]
	for i in range(count):
		if len(res) <= 2:
			break
		flag = scales.get_weight(res[:(len(res) + 1) // 3], res[len(res) - (len(res) + 1) // 3:])
		if flag == -1:
			res = res[:(len(res) + 1) // 3]
		elif flag == 1:
			res = res[len(res) - (len(res) + 1) // 3:]
		elif flag == 0:
			res = res[(len(res) + 1) // 3:len(res) - (len(res) + 1) // 3]
	if len(res) == 1:
		return res[0]
	return res[0] if scales.get_weight(res[:1], res[1:]) == -1 else res[1]


def split(scales, next):
	if len(next) == 1:
		return next[0]
	elif len(next) == 2:
		w = scales.get_weight([next[0]], [next[1]])
		if w == 1:
			return next[1]
		else:
			return next[0]
	elif len(next) == 3:
		w = scales.get_weight([next[0]], [next[1]])
		if w == 0:
			return next[2]
		elif w == -1:
			return next[0]
		else:
			return next[1]
	lock_size = (len(next) + 1) // 3
	l = next[:lock_size]
	r = next[lock_size:lock_size + lock_size]
	f = next[lock_size + lock_size:]
	return find(scales, f, l, r)

def find(scales, free, first, second):
	w = scales.get_weight(first, second)
	if w == 0:
		return split(scales, free)
	elif w == -1:
		return split(scales, first)
	elif w == 1:
		return split(scales, second)

def find_ball(scales, ball_count):
	next = list(range(ball_count))
	return split(scales, next)


def find_ball(scales, ball_count):
	return find(scales, [*range(ball_count)])

def find(scales, balls):
	l = len(balls)
	if l == 1:
		return balls[0]
	l = -(l // -3)
	(a, b, c) = (balls[:l], balls[l:l + l], balls[l + l:])
	v = scales.get_weight(a, b)
	if v == -1:
		return find(scales, a)
	if v == 1:
		return find(scales, b)
	return find(scales, c)


def find_ball(scales, n=8):
	balls = list(range(n))
	while len(balls) > 1:
		(left, right, out) = (balls[::3], balls[1::3], balls[2::3])
		if len(balls) % 3 == 1:
			out.append(left.pop())
		balls = [left, out, right][scales.get_weight(left, right) + 1]
	return balls.pop()