VMWare Garbage Wars 2015: Team NecroFiles

solution.rb

require 'net/http'

#$IP = '172.16.180.128'
# $IP = '192.168.125.129'
$IP = '172.16.18.230'
$PORT = '8080'
$OBJECTS_API = 'api/sector/%d/objects' 
$ROOTS_API = 'api/sector/%d/roots'

def get_request link
	uri = URI.parse link
	http = Net::HTTP.new(uri.host, uri.port)
	request = Net::HTTP::Get.new(uri.request_uri)
	http.request request
end

def post_traj sector, traj
	url = "http://#{$IP}:#{$PORT}/api/sector/#{sector}/company/NecroFiles/trajectory"
	uri = URI.parse url
	params = traj.kind_of?(Array) ? {trajectory: traj.join(' ')} : {trajectory: traj}
	request = Net::HTTP.post_form(uri, params)
end

def get_sector_map sector
	result = get_request("http://#{$IP}:#{$PORT}/#{$OBJECTS_API}" % sector)
	if result.code == "404"
		p "ERROR! No such sector #{sector} found when requesting to get its map."
		nil
	elsif result.code == "200"
		result.body
	end

# 	ret = <<END
# 1 2
# 1 6
# 2 20
# 2 30
# 4 6
# 6 9
# 6 1223
# 1223 21
# 4 7
# 108 94
# 108 7
# 100 101
# 101 100
# END
# 	ret
end

def build_graph sector
	graph = nil

	sector_map = get_sector_map sector
	if sector_map
		graph = Hash.new { |h,k| h[k] = Array.new } # represented as an adjacency list
		sector_map.each_line do |pair|
			from,to = pair.chomp.split.map { |num| num.to_i }
			graph[from] << to
		end
	end

	graph
end

def get_roots sector
	result = get_request("http://#{$IP}:#{$PORT}/#{$ROOTS_API}" % sector)
	if result.code == "404"
		p "ERROR! No such sector #{sector} found when requesting to get its roots."
		nil
	elsif result.code == "200"
		result.body
	end

# 	ret = <<END
# 4
# 9
# 6
# END
# 	ret
end

def mark_forbidden_dfs graph, node, forbidden_nodes, visited
	dfs_stack = Array.new
	dfs_stack.push node
	until dfs_stack.empty?
		cur = dfs_stack.pop
		visited << cur

		forbidden_nodes << cur unless forbidden_nodes.include? cur
		
		if graph[cur]
			graph[cur].each do |neighbor|
				unless visited.include? neighbor
					dfs_stack.push neighbor
				end
			end
		end
	end
end

def get_forbidden_nodes graph, visited, sector
	forbidden = Array.new

	roots = get_roots sector
	if roots
		roots.each_line do |root|
			forbidden << root.chomp.to_i
		end
	end

	a = forbidden.dup
	a.each do |sys_node|
		mark_forbidden_dfs graph, sys_node, forbidden, visited
	end

	forbidden
end

def unvisited_neighbors graph, node, visited
	graph[node].select { |a| !visited.include? a }
end

def hit_dead_end? graph, node, visited
	!graph[node] || graph[node].empty? || unvisited_neighbors(graph, node, visited).empty?
end

def dfs graph, node, forbidden, visited, sector, path
	if forbidden.include? node
		p "ERROR FORBIDDEN NODE"
		return
	end

	path << node
	visited << node

	if hit_dead_end? graph, node, visited
		$all_white_paths[sector] << path.dup
	end

	if graph[node]
		graph[node].each do |neighbor|
			unless (visited.include? neighbor) || (forbidden.include? neighbor)
				dfs graph, neighbor, forbidden, visited, sector, path
			end
		end
	end

	path.delete node
end

def uncollected_from path, sector
	path.select { |node| !$collected_nodes[sector].include? node }
end

def choose_best_path sector # by number of uncollected nodes in the path
	best_path = Array.new
	best_node_count = 0
	$all_white_paths[sector].each do |path|
		uncollected = uncollected_from path, sector
		if uncollected.length > best_node_count
			best_path = path
			best_node_count = uncollected.length
		end
	end
	best_path
end

def strategic_advance top_sector
	best_path = Array.new
	sector_of_best_path = 0
	# p 'starting iterations'
	1.upto top_sector do |sector|
		best_path_in_sector = choose_best_path sector
		
		if uncollected_from(best_path_in_sector, sector).length > uncollected_from(best_path, sector_of_best_path).length
			best_path = best_path_in_sector
			sector_of_best_path = sector
		end
	end

	# p best_path.size
	# p post_traj sector_of_best_path, best_path
	old_size = $collected_nodes[sector_of_best_path].size
	best_path.each { |collected| $collected_nodes[sector_of_best_path] << collected }
	$collected_nodes[sector_of_best_path].uniq!
	$all_collected += ($collected_nodes[sector_of_best_path].size - old_size)
	$all_white_paths[sector_of_best_path].delete best_path
end

def nodes_in_graph graph, forbidden_nodes
	counted = Array.new
	graph.each do |node,neighbors|
		counted << node unless (counted.include? node) || (forbidden_nodes.include? node)
		neighbors.each { |node| counted << node unless (counted.include? node) || (forbidden_nodes.include? node) }
		# this is needed because vertices with no neighbors aren't included as keys
	end
	counted.length
end

$all_collected = 0
num_nodes = 0

$all_white_paths = Array.new
$collected_nodes = Array.new

1.upto 10 do |i|
	visited = Array.new
	$all_white_paths[i] = Array.new
	$collected_nodes[i] = Array.new
	path = Array.new

	graph = build_graph i
	forbidden_nodes = get_forbidden_nodes graph, visited, i
	# p "GOT GRAPH!!!!"

	num_nodes += nodes_in_graph(graph, forbidden_nodes)

	if graph
		graph.keys.each do |node|
			dfs(graph, node, forbidden_nodes, visited, i, path) unless visited.include?(node) || forbidden_nodes.include?(node)
		end
	end

	# strategic_advance i
end

while $all_collected < num_nodes
	strategic_advance 10
end