#! /usr/bin/env ruby

if ARGV.length != 1
        abort("Incorrect arguments - needs input file")
elsif not File.exist? (ARGV[0])
	abort("File #{ARGV[0]} did not exist")
end

file = ARGV[0]

def truthy?(val)
	!val.nil? and val != [] and val != ""
end

def arrangements(candidate, other_candidates, run_lengths, cache)
#	puts "Looking for #{run_lengths} (#{truthy?(run_lengths)}) in #{candidate} (#{truthy?(candidate)}), #{other_candidates.nil? '' : other_candidates.join(", ")}"
	puts "Looking for #{run_lengths} in #{candidate}, #{other_candidates.nil? ? '' : other_candidates.join(",")}"
	if !truthy?(candidate) and !truthy?(run_lengths)
		puts "Combos: 1 (both empty)"
		return 1
	elsif !truthy?(run_lengths) and !candidate.include? "#" and (!truthy?(other_candidates) or other_candidates.all? {|candidate| truthy?(candidate)})
		return 1
	elsif (!truthy?(candidate) and truthy?(run_lengths)) or (!truthy?(run_lengths) and candidate.include? "#")
		puts "Combos: 0 (fail)"
		return 0
	end
	find_length = run_lengths.first

	cached = cache[[candidate, other_candidates, run_lengths]]
	if !cached.nil?
		puts "Combos: #{cached} (cached)"
		return cached
	end
		
	
	combo_count = 0

	if find_length == candidate.length
		# We found a perfect match!
		new_candidate = other_candidates[0]
		new_other_candidates = other_candidates[1..]
		combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache)
		if truthy?(candidate) and !candidate.include? "#"
			# What if we skip this all all question mark candidate and try later?
			combo_count += arrangements(new_candidate, new_other_candidates, run_lengths, cache)
		end
	elsif find_length < candidate.length
		if candidate[find_length] != "#"
			if find_length == candidate.length - 1
				new_candidate = other_candidates[0]
				new_other_candidates = other_candidates[1..]
			else
				new_candidate = candidate[(find_length+1)..]
				new_other_candidates = other_candidates
			end
			# We found a substring match that ends in a valid place
			combo_count += arrangements(new_candidate, new_other_candidates, run_lengths[1..], cache)
		end
		if candidate[0] == "?"
			# We've got space, so try the other combo
			combo_count += arrangements(candidate[1..], other_candidates, run_lengths, cache)
		end
	else
		# This candidate must all be good parts
		combo_count += arrangements(other_candidates[0], other_candidates[1..], run_lengths, cache)
	end
	puts "Combos: #{combo_count}\n"
	cache[[candidate, other_candidates, run_lengths]] = combo_count
	combo_count
end

cache = Hash.new

combos = File.open(file, "r").each_line(chomp: true).map do |line|
        symbols, run_lengths_str = line.split(" ")
        run_lengths = run_lengths_str.split(",").map(&:to_i)
        candidates = symbols.split(".").filter {|candidate| candidate != ""}
	candidate = candidates.shift
	line_arrangements = arrangements(candidate, candidates, run_lengths, cache)
	puts "Line arrangements: #{line_arrangements}\n\n"
	line_arrangements
end
puts "#{combos} = #{combos.sum}"