CodeEval Sequence Transformation

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                -> Yes
00 AAAAAA                         -> Yes
01001110 AAAABAAABBBBBBAAAAAAA    -> Yes
1100110 BBAABABBA                 -> No

Here 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 No

puts 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,}" 
  } + '

It works fine with the small sample, but takes forever with the large one.

So I thought about backtracking and tried it

```
def check_char_number(char, number)
  (number == '0' && char == 'A') || number == '1'
end

def 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 false
end

puts IO.readlines(ARGV[0]).map(&:chomp).map(&:split).map { |a|
  r = 0
) ? 'Yes' : 'No'
}

It works fine with the small sample, but takes forever with the large one.

So I thought about backtracking and tried it

```
def check_char_number(char, number)
(number == '0' && char == 'A') || number == '1'
end

def 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 false
end

puts IO.readlines(ARGV[0]).map(&:chomp).map(&:split).map { |a|
r = 0

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_string

• The 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_matching

• For the sake of line-length, I'd probably just call the matrix matrix. It's not about to be confused with anything

• Favor || 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 loop

• Right 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 it

• Pull 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'
end

def 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]
  end
end

File.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'
end

Again, 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.

StackExchange Code Review Q#64872, answer score: 2