CODEWITHSUNDEEP
rubyregex
ordinary
ordinary

Reputation: 6133

Ruby regex to remove all consecutive letters from string

Here is the problem (from Codeforces)

Polycarp thinks about the meaning of life very often. He does this constantly, even when typing in the editor. Every time he starts brooding he can no longer fully concentrate and repeatedly presses the keys that need to be pressed only once. For example, instead of the phrase "how are you" he can type "hhoow aaaare yyoouu".

Polycarp decided to automate the process of correcting such errors. He decided to write a plug-in to the text editor that will remove pairs of identical consecutive letters (if there are any in the text). Of course, this is not exactly what Polycarp needs, but he's got to start from something!

Help Polycarp and write the main plug-in module. Your program should remove from a string all pairs of identical letters, which are consecutive. If after the removal there appear new pairs, the program should remove them as well. Technically, its work should be equivalent to the following: while the string contains a pair of consecutive identical letters, the pair should be deleted. Note that deleting of the consecutive identical letters can be done in any order, as any order leads to the same result.

Here is my solution.. For some reason it fails an extremely large test case. Mine seems to get rid of more letters than it is supposed to. Is this regular expression incorrect?

str = gets.chomp

while str =~ /(.)\1/
  str.gsub!(/(.)\1+/,'')
end

puts str

EDIT -- This solution doesn't work because it gets rid of all consecutive groups of characters. It should only get rid of duplicates. If I do it this way, which I believe to be correct, it times out on extremely large strings:

str = gets.chomp

while str =~ /(.)\1/
  str.gsub!(/(.)\1/,'')
end

puts str

Upvotes: 4

Views: 2822

Answers (2)

the Tin Man
the Tin Man

Reputation: 160571

Why does it have to be a regular expression?

'foobar'.squeeze
=> "fobar"

"hhoow aaaare yyoouu".squeeze
=> "how are you"

squeeze is a useful tool for compressing runs of all characters, or specific ones. Here are some examples from the documentation:

"yellow moon".squeeze                  #=> "yelow mon"
"  now   is  the".squeeze(" ")         #=> " now is the"
"putters shoot balls".squeeze("m-z")   #=> "puters shot balls"

If "aab" becomes "b", then you're not following the example given in the question, which is "hhoow" turns into "how". By your statement it would be "w", and "yyoouu" would be "". I think you're reading too much into it and not understanding the problem based on their sample input and sample output.

Upvotes: 8

jbw
jbw

Reputation: 83

ha, harder than I thought when I first read. What about

s = "hhoow aaaareer yyoouu"
while s.gsub!(/(.)\1+/, '')
end
puts s

which leaves s == 'w' if i understand the problem correctly.

Upvotes: 1

Related Questions