Skip to content

Instantly share code, notes, and snippets.

@lwalen
Created May 14, 2016
Embed
What would you like to do?
Get the shortest possible unique substring that references each book of the bible
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment