I've been working on this challenge for a week:There are two sequences. The first sequence consists of digits 0 and 1, the second one consists of letters A and B. The challenge is to determine whether it's possible to transform a given binary sequence into a string sequence using the  following rules:0 can be transformed into non empty sequence of letters A (A, AA, AAA etc.) 1 can be transformed into non empty sequence of letters A (A, AA, AAA etc.) or to non empty sequence of letters B (B, BB,  BBB etc) e.g.Examples:1010 AAAAABBBBAAAA                -> Yes00 AAAAAA                         -> Yes01001110 AAAABAAABBBBBBAAAAAAA    -> Yes1100110 BBAABABBA                 -> NoHere is the first small sample to feed the program and here is the second large sample.I have 3 working solutions, but they're painfully slow.My first idea was to build a regex for each test case, test if it matched and map Yes or Noputs IO.readlines(ARGV[0]).map { |l| l.chomp.split(' ') }.map { |a|  index = 0  a[1].match(a[0].chars.to_a.inject('^') { |result, digit|     result + (digit == '1' ? '([A|B])\\' : '(A)\\') + #{index += 1}{0,}   } + '$') ? 'Yes' : 'No'}It works fine with the small sample, but takes forever with the large one.So I thought about backtracking and tried itdef check_char_number(char, number)  (number == '0' && char == 'A') || number == '1'enddef check(string, numbers, current_char)  return true if string.empty? && numbers.empty?  return false if string.empty?      return false if current_char != string[0] && !check_char_number(string[0], numbers[0])  if string[0] == current_char    r = check(string[1..-1], numbers, current_char)    return r if r  end  return check(string[1..-1], numbers[1..-1], string[0]) if check_char_number(string[0], numbers[0])    return falseendputs IO.readlines(ARGV[0]).map(&:chomp).map(&:split).map { |a|  r = 0  l1 = a[0].length  l2 = a[1].length  if l1 > l2 or l1 < 1 or l2 < 1    r = 'No'  else    r = check(a[1], a[0], nil) ? 'Yes' : 'No'    puts finished: #{r}  end  r}But it's still so slowSo I was getting desperate and started looking around on GitHub to see how other people did it, and found something interesting in pythonI don't have any academic degree in CS I learned everything with books and MIT courses and I can't tell if what he's using is a known technique to solve this sort of problems. I feel like I barely understand it (spent a lot of time with the debugger to see what happens step by step) and I'd really love to know if a Wikipedia page could explain this better or if this is completely home-made.I ported it ruby and my second question is: even though it is significantly faster than the previous two why is it sill five to seven times slower than his solution:def check_number_with_partial_string(number, partial_string)  #45% of runtime spent here!  return !partial_string.include?('B') if number == '0'  return !(partial_string.include?('A') && partial_string.include?('B')) if number == '1'enddef check_matching(numbers, string, matching_matrix, row = 0, column = 0)  return if matching_matrix[-1][-1] == true  return if row >= matching_matrix.size or column >= matching_matrix[row].size  return if matching_matrix[row][column]  (column...string.length).each do |c|    matching_matrix[row][c] = false    if check_number_with_partial_string(numbers[row], string[column...(c + 1)])      matching_matrix[row][c] = true      check_matching(numbers, string, matching_matrix, row + 1, c + 1)    end  endendputs IO.readlines(ARGV[0]).map(&:chomp).map(&:split).map { |a|  matrix = Array.new(a[0].length).map { |b| Array.new(a[1].length) }  check_matching(a[0], a[1], matrix)  matrix[-1][-1] ? 'Yes' : 'No'}I profiled it and it seems 45% of the time is spent in the first little methodTime profiler
CodeEval Sequence Transformation
ruby;programming challenge;regex;comparative review;time limit exceeded
I focussed exclusively on your last bit of code. I'm afraid I only managed a ~1.8x speed increase. I think a lot of comes down to Ruby's itself not being the quickest thing going - at least not when it comes to this particular algorithm.Long story short: Convert your number and letter strings to integer arrays. For whatever reason, that's where I found a performance increase. I'll leave the explanation to someone with deeper knowledge of Ruby's string handling.There may be a totally different way to do this, which'll be super-fast in Ruby, but I haven't investigated that. Generally, though, Ruby aims for expressiveness and readability, and this algorithm doesn't play to Ruby's strengths.Anyway, review time! I've only changed minor stuff to make it more Ruby-like; the algorithm itself is as it ever was (for good or bad)You'll still find that the majority of the time is spent in that first method. For one, it's being called constantly, and for another, it's doing the most work. Anything else in the code is just loops and boolean logic. But check_number_with_partial_string is the one actually doing the real checking of numbers to letters. So it's no wonder it weighs heavy on the performance.check_number_with_partial_stringThe logic's iffy. By which I mean that there is literally one if too many. The number will be either 1 or 0, so why the extra check? Also, no need to (potentially) call include?('B') twice. Store it once, use it twice.There might also be a micro-optimization here if we flip the second return value around. If we've stored includes?('B') already and it's false, we can check that first, and, since the expression uses &&, the check for includes?('A') doesn't need to run.Should maybe just be called partial_match?check_matchingFor the sake of line-length, I'd probably just call the matrix matrix. It's not about to be confused with anythingFavor || over or for boolean logic (here's a good explanation)matching_matrix[row][c] = false is unnecessary since the initial value of that index is nil which is already false'y. But since check_number_with_partial_string returns a bool, we can skip a bit and just assign its return value to the index.The overall name is a bit misleading. I'd imagine it would return something, since it's called check - but it doesn't.Read loopRight now, the entire map must run before anything is printed. You can use IO#each_line instead of loading everything into memory at once. And print for each test case. I've changed it, but the original may be faster(!)Use do..end for multiline blocks (though if you keep the puts outside, the lower precedence of do..end compared to {...} will trip you up)Use Array.new with a block instead of creating and then mapping an array to fill itPull named variables from the split string to keep things readable (no opaque array indices)In the end, I had:def check_number_with_partial_string(number, string)  includes_b = string.include?(66) # ASCII 'B'  return !includes_b if number == 0  !(includes_b && string.include?(65)) # ASCII 'A'enddef check_matching(numbers, string, matrix, row = 0, column = 0)  return if matrix[-1][-1]  return if row >= matrix.size || column >= matrix[row].size  return if matrix[row][column]  (column...string.length).each do |c|    matrix[row][c] = check_number_with_partial_string(numbers[row], string[column...(c + 1)])    check_matching(numbers, string, matrix, row + 1, c + 1) if matrix[row][c]  endendFile.open(ARGV[0]).each_line do |line|  digits, string = line.chomp.split  digits = digits.chars.map(&:to_i)  string = string.chars.map(&:ord)  matrix = Array.new(digits.length) { Array.new(string.length) }  check_matching(digits, string, matrix)  puts matrix[-1][-1] ? 'Yes' : 'No'endAgain, as far as I can tell, any increased performance came from mapping the two strings to integers.For some sample input I generated (where everything always matches), I got ~43 sec for the code above, versus ~83 sec for the original. That's obviously not the most rigorous test, but it seemed consistent with different input sizes.Maybe there are more gains to be had somewhere, but I didn't find 'em (but I didn't try to do more overall restructuring either). Maybe someone else will spot something. But again (again) this just seems to me to be an algorithm that doesn't play to Ruby's strengths.