def goto(coord):
	x, y = coord[0], coord[1]
	yDist = get_pos_y() - y # Positive if drone is north of the target space 
	xDist = get_pos_x() - x # Positive if drone is east of the target space 
	halfWorldSize = get_world_size()/2
	
	while get_pos_y() != y:
		if yDist >= halfWorldSize or (-halfWorldSize <= yDist and yDist < 0):
			move(North)
		else:
			move(South)
	
	while get_pos_x() != x:
		if xDist >= halfWorldSize or (-halfWorldSize < xDist and xDist < 0):
			move(East)
		else:
			move(West)
	
def field_grid(size):
	field = []
	for x in range(size):
		for y in range(size):
			field.append((x,y))
	return field

def field_chess_grid(size, black):
	field = []
	for x in range(size):
		for y in range(size):
			if (x + y) % 2 == black:
				field.append((x,y))
	return field

def field_plant_grid(size, element):
	field = {}
	for x in range(size):
		for y in range(size):
			field[(x,y)] = element
	return field

def index(x, y, width):
	return x * width + y

def get_inventory():
	inventory = {}
	for item in Items:
		inventory[item] = num_items(item)
	return inventory


def init_plant(size, element):
	if element == Entities.Grass:
		clear()
		do_a_flip()
		return
	
	# generate field
	field = field_grid(size)
	for cell in field:
		goto(cell)
		harvest()
		better_plant(element)
			

def harvest_field(size):
	field = field_grid(size)
	for cell in field:
		goto(cell)
		if can_harvest():
			harvest()
		

def replant(coords, element):
	for coord in coords:
		goto(coord)
		plant(element)

def is_sorted(arr):
	for i in range(len(arr)-1):
		if arr[i] > arr[i+1]:
			return False
	return True

def check_seeds():
	seeds = [Items.Carrot_Seed, Items.Pumpkin_Seed, Items.Sunflower_Seed, Items.Cactus_Seed]
	inventory = get_inventory()
	goal = {}
	size = get_world_size()*get_world_size()

	for seed in seeds:
		diff = abs(inventory[seed] - size)
		if diff > size:
			goal[seed] = 0
		else:
			goal[seed] = diff

	for g in goal:
		amount = goal[g]
		if amount > 0:
			#quick_print("buying", g, amount)
			if g == Items.Carrot_Seed:
				if num_items(Items.Wood)/12 > amount and num_items(Items.Hay) > amount:
					trade(g, amount)

			if g == Items.Pumpkin_Seed:
				if num_items(Items.Carrot)/9 > amount:
					trade(g, amount)

			if g == Items.Sunflower_Seed:
				if num_items(Items.Carrot) > amount:
					trade(g, amount)
			
			if g == Items.Cactus_Seed:
				if num_items(Items.Gold) > amount:
					trade(g, amount)

def sum(arr):
	count = 0
	for el in arr:
		count += el
	return count

def sum_from_dict(d):
	count = 0
	for el in d:
		count += d[el]
	return count

def better_plant(p):
	if p == Entities.Grass or p == Entities.Bush or p == Entities.Tree:
		if get_ground_type() != Grounds.Turf:
			harvest()
			till()
	if p == Entities.Carrots or p == Entities.Pumpkin or p == Entities.Sunflower:
		check_seeds()
		if get_ground_type() != Grounds.Soil:
			harvest()
			till()
		while get_water() < 0.8 and num_items(Items.Water_Tank) > 10:
			use_item(Items.Water_Tank)
		if num_items(Items.Pumpkin) > 10:
			if num_items(Items.Fertilizer) < 1:
				trade(Items.Fertilizer)
			use_item(Items.Fertilizer)
	if p == Entities.Cactus:
		check_seeds()
		if get_ground_type() != Grounds.Soil:
			harvest()
			till()
	plant(p)

def insertion_sort(array):
	for step in range(1, len(array)):
		key = array[step]
		j = step - 1

		# Compare key with each element on the left of it until an element smaller than it is found
		# For descending order, change key<array[j] to key>array[j].        
		while j >= 0 and key < array[j]:
			array[j + 1] = array[j]
			j = j - 1

		# Place key at after the element just smaller than it.
		array[j + 1] = key
	return array