Ruby Program/Problem

Question

Given a string of characters as input, without using regular expression or pattern matching, how to get the output, if the characters matches aaa should output 1 and if the characters matches aBa should output 2. (Note: Should not re-process characters so as to output both “1” and “2” when processing the same input)

So for example:

given 'aaBaBaaaBaaa' it should output 211

given 'aaaBaBaaaaBBaBaBa' it should output 1212

Thanks in advance.

Unable to figure how how your output maps to your input, need a better description of the problem. What does aaaaaaaa yield, a single "1"? — user229044
– user229044 ♦, Commented Jan 7, 2010 at 18:13
@meagar: As I read it, the patterns can't overlap. So "aaaaaaaa" would parse as "[aaa][aaa]aa", yielding "11" — Drew Dormann
– Drew Dormann, Commented Jan 7, 2010 at 18:17
What happens if two patterns match? Such as you were given the patterns "aaa" and "aaaa"? — EmFi
– EmFi, Commented Jan 7, 2010 at 19:56
This sounds very much like stackoverflow.com/questions/2018244/… — Bob Jarvis - Слава Україні
– Bob Jarvis - Слава Україні, Commented Jan 8, 2010 at 12:44

kejadlen · Accepted Answer · 2010-01-07 22:02:00Z

6

Sounds like you want a state machine:

require 'statemachine'

state_machine = Statemachine.build do
  trans :_, :a, :a
  trans :_, :B, :_
  trans :a, :a, :aa
  trans :a, :B, :aB
  trans :aa, :a, :_, 'print 1'
  trans :aa, :B, :aB
  trans :aB, :a, :_, 'print 2'
  trans :aB, :B, :_
end

"aaBaBaaaBaaa".each_char do |i|
  state_machine.process_event(i)
end

state_machine.reset
puts

"aaaBaBaaaaBBaBaBa".each_char do |i|
  state_machine.process_event(i)
end

answered Jan 7, 2010 at 22:02

kejadlen

1,5991 gold badge10 silver badges10 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

andrykonchin · Accepted Answer · 2010-01-07 18:26:10Z

4

without using regular expression or pattern matching

#input = 'aaBaBaaaBaaa'
input = 'aaaBaBaaaaBBaBaBa'
codes = {'aaa' => 1, 'aBa' => 2}
patterns = codes.keys
output = []

current = 0
length = input.length

while current <= length - 1
    is_find = false
    patterns.each do|pattern|
        len = pattern.length
        if input[current, len] == pattern
            output << codes[pattern]
            current += len
            is_find = true
            break
        end
    end

    current += 1 if !is_find
end

p output

answered Jan 7, 2010 at 18:26

andrykonchin

2,5923 gold badges18 silver badges29 bronze badges

6 Comments

Beanish Over a year ago

p output.join - he wanted a string ;) Nicely done though, solved the problem and then added the flexibility of adding new "codes" of any length.

Dharam Gollapudi Over a year ago

Excellent. How about the same in JAVA?

EmFi Over a year ago

The algorithm is pretty solid, so the solution in Java is pretty much the same. Biggest changes are you lose access to Ruby's each iterator, and hashes aren't part of the default types. There are many ways around that. For starters, you could import java.util.HashMap, or you could redefine the codes hash as an array of code objects.

Dharam Gollapudi Over a year ago

After reviewing the code again, and the given conditions of not using regular expression or pattern matching, I believe although the solution is good it doesn't satisfy all the conditions. Isn't (if input[current, len] == pattern) considered as pattern matching?

he_the_great Over a year ago

@satynos It is only pattern matching only if you also consider, if "Hello" == "Hello" to also be pattern matching. And if you do, then your requirements can't be satisfied.

|

Collectives™ on Stack Overflow

Ruby Program/Problem

2 Answers 2

Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related