Get the shortest possible unique substring that references each book of the bible

book.rb

#!/usr/bin/env ruby

BOOKS = ['Genesis', 'Exodus', 'Leviticus', 'Numbers', 'Deuteronomy', 'Joshua', 'Judges', 'Ruth', '1 Samuel', '2 Samuel', '1 Kings', '2 Kings', '1 Chronicles', '2 Chronicles', 'Ezra', 'Nehemiah', 'Esther', 'Job', 'Psalms', 'Proverbs', 'Ecclesiastes', 'Song of Solomon', 'Isaiah', 'Jeremiah', 'Lamentations', 'Ezekiel', 'Daniel', 'Hosea', 'Joel', 'Amos', 'Obadiah', 'Jonah', 'Micah', 'Nahum', 'Habakkuk', 'Zephaniah', 'Haggai', 'Zechariah', 'Malachi', 'Matthew', 'Mark', 'Luke', 'John', 'Acts', 'Romans', '1 Corinthians', '2 Corinthians', 'Galatians', 'Ephesians', 'Philippians', 'Colossians', '1 Thessalonians', '2 Thessalonians', '1 Timothy', '2 Timothy', 'Titus', 'Philemon', 'Hebrews', 'James', '1 Peter', '2 Peter', '1 John', '2 John', '3 John', 'Jude', 'Revelation'].freeze

books = BOOKS.map{ |b| b.gsub(' ', '') }.sort

partials = {}
shortest = {}
i = 0

while true
	books.each_with_index do |b|
		chars = b[0..i]

		if !partials[chars]
			partials[chars] = {}
		end

		partials[chars][b] = true
	end

	all_one = true

	partials.each do |k, v|
		if v.length == 1
			shortest[v.first.first] = k
			books.delete(v.first.first)
		end
	end

	if books.length == 0
		break
	end

	i += 1
end

BOOKS.each do |b|
	puts "#{shortest[b.gsub(' ', '')]}\t#{b}"
end