fork download 
  1. # /r/dailyprogrammer
  2. # Challenge 150
  3. # by /u/Sakuya_Lv9
  4.  
  5. class WordList
  6.  
  7.     def initialize arr
  8.         @list = arr
  9.         @list.each { |s| s.chomp! }
  10.     end
  11.  
  12.     def has_prefix? word
  13.         has_word? word, :partial
  14.     end
  15.  
  16.     def has_word? word, mode=:exact
  17.         if mode == :partial
  18.             partial = true
  19.         elsif mode == :exact
  20.             partial = false
  21.         else
  22.             raise ArgumentError
  23.         end
  24.  
  25.         range = 0..@list.length
  26.         regexp = Regexp.compile('\A' + word) if partial
  27.         while not range.begin == range.end
  28.             mid = (range.end - range.begin) / 2 + range.begin
  29.             w = @list[mid]
  30.             case w <=> word
  31.             when -1
  32.                 range = (mid + 1)..range.end
  33.             when 0
  34.                 return true
  35.             when 1
  36.                 return true if partial && regexp =~ w
  37.                 range = range.begin..mid
  38.             end
  39.         end
  40.         false
  41.     end
  42.  
  43. end
  44.  
  45. class Solution
  46.     attr_accessor :words
  47.  
  48.     def initialize words
  49.         @words = words
  50.     end
  51.  
  52.     def to_s
  53.         return words.join(" ").capitalize + "."
  54.     end
  55.  
  56. end
  57.  
  58. class PartialSolution
  59.     attr_accessor :wordlist
  60.     attr_accessor :list
  61.     attr_accessor :words
  62.     attr_accessor :done
  63.  
  64.     def initialize wordlist, list, words=[]
  65.         @wordlist = wordlist
  66.         @list = list
  67.         @words = words
  68.     end
  69.  
  70.     def add_word word
  71.         list = list_minus_word word
  72.         PartialSolution.new @wordlist, list, (@words.clone << word)
  73.     end
  74.  
  75.     def list_minus_word word
  76.         list = @list.dup
  77.         list.map! do |x|
  78.             x.dup
  79.         end
  80.         word.each_char do |char|
  81.             list.each do |string|
  82.                 string.slice! 0 if string[0] == char
  83.             end
  84.         end
  85.         list
  86.     end
  87.  
  88.     # returns array containing list of
  89.     # PartialSolutions with one more word
  90.     #
  91.     # returns Solution object if it is done
  92.     def explode
  93.         return [Solution.new(@words)] if list[0].empty? and list[1].empty?
  94.         words = get_words
  95.         array = []
  96.         words.each do |word|
  97.             array << (self.add_word word)
  98.         end
  99.         return array
  100.     end
  101.  
  102.     def get_words word=""
  103.         words = []
  104.         list = list_minus_word word
  105.  
  106.         [0, 1].each do |n|
  107.             next if list[n].empty?
  108.             w = word + list[n][0]
  109.             if @wordlist.has_prefix? w
  110.                 words << (get_words w)
  111.                 if @wordlist.has_word? w
  112.                     words << w
  113.                 end
  114.             end
  115.         end
  116.  
  117.         words.flatten
  118.     end
  119.  
  120. end
  121.  
  122. class DisemvoweledString
  123.     attr_accessor :list
  124.     attr_accessor :mode
  125.  
  126.     def initialize list, mode=:return_everything
  127.         @list = list
  128.         @mode = mode
  129.     end
  130.  
  131.     # this is almost the main method
  132.     def solve_for_original
  133.         # wordlist = WordList.new(IO.readlines("enable1.txt"))
  134.         wordlist = WordList.new(%w{ asteroids cheating daff dis et eth fen fend host lo off rids sae the this tor we wile will })
  135.         partial_solutions = [PartialSolution.new(wordlist, @list)]
  136.         solutions = []
  137.  
  138.         while partial_solutions.length != 0
  139.             if partial_solutions.last.class == Solution
  140.                 solutions << partial_solutions.pop
  141.                 if @mode == :return_ASAP
  142.                     return solutions
  143.                 end
  144.             else
  145.                 partial_solutions.concat partial_solutions.pop.explode
  146.             end
  147.         end
  148.  
  149.         return solutions
  150.     end
  151.  
  152. end
  153.  
  154. # nah, not going to change it
  155. input = ["wwllfndffthstrds","eieoeaeoi"]
  156. input.each do |s| s.chomp! end
  157.  
  158. puts DisemvoweledString.new(input).solve_for_original
Success #stdin #stdout 0.02s 7476KB
comments (?)
stdin 
Standard input is empty
stdout 
We wile lo fen daff et host rids.
We will fend off eth asteroids.
We will fend off eth sae tor dis.
We will fend off the asteroids.
We will fend off the sae tor dis.
https://ideone.com/EmnT7x
language:
Ruby (ruby 2.5.5)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!