# Solve the Ruler Problem


# Initialize variables
distances = Array.new	# array of all the measurable distances
last_mark_number = 3
# Create array of all integer ruler marks

# Choose one combination for the number of marks being tested
# Creates an array of arrays of marks e.g [[1,2,3],[1,2,4],[1,2,5]...]
for ruler_length in 6..36
	all_marks = 1.step(ruler_length-1,1).to_a
	for marks_to_test in (last_mark_number-1)..(ruler_length-1)
		solution = false
		combinations_to_test = all_marks.combination(marks_to_test).to_a
		# Cycle through all combinations with fixed number of marks
		combinations_to_test.each do |mark_list|
			for i in 0..(marks_to_test-1) # this is the number of elements in mark_list
				distances.push(mark_list[i]) # Add distance from 0 to mark to the distance array
				#puts "#{mark_list[i]} #{distances}"

				distances.push(ruler_length - mark_list[i]) # Add distance from end to mark to the distance array
				#puts "#{mark_list[i]} #{distances}"
				
				for j in (i+1)..(marks_to_test-1)
					distances.push(mark_list[j] - mark_list[i]) # add distance between marks to distance array
					#puts "#{mark_list[i]} #{mark_list[j]} #{distances}"
				end
			end
			distances = distances.sort.uniq
			if distances.count == ruler_length-1 # if true, then found a solution
				puts "#{ruler_length} #{mark_list}"
				solution = true
				last_mark_number = marks_to_test
			end
			distances = Array.new
		end
		break if solution == true
	end
end