Palindrome Problem - Minimum number of characters to make a text palindrome

[Legjendat]

So, I'm having a very difficult task here. I need to analyze a certain text and find the minimum number of characters it needs to become a palindrome. The text will not have any special characters or numbers, just alphabet letters. Now, I've made some progression and have tried a lot of situations correctly, but in some situations I've gotten wrong outputs on the MINIMUM number of characters needed. I've tested the below texts:

AAABBBBCCCCC - AAABBBBCCCCCBBBBAAA ✓ 7
CCCCCBBBBAAA - AAABBBBCCCCCBBBBAAA ✓ 7
BBBBCCCCCAAA - AAABBBBCCCCCBBBBAAA ✓ 7
FASLLI - FAS-I-LLI-SAF ✓ 4
ARBEN - ARBEN-EBRA ✓ 4
ARBENA - ARBEN-EBR-A ✓ 3
ARBANA - ARBAN-ABR-A ✓ 3
ALL - ALL-A ✓ 1
ALLLL - ALLLL-A ✓ 1
BAOUB - BAOU-OA-B ✓ 2
ASDRFFF - ASDRFFF-DRSA ✓ 4
AAABBB - AAABBB-AAA / BBB-AAABBB ✓ 3
ARBENARBEN - ARBENARBEN-EBRANEBRA ✓ 9
ALLALL - ALLALL-A WRONG , outputs "4" when all there's needed is 1.
AAABBBBAAABBBBCCCCC - CCCCCBBBB-AAABBBBAAABBBBCCC WRONG, outputs 14 when all there's needed is 9 chars. In this case there should be noted that there are 2 palindromes within the text (as in substrings which may have something to do with the wrong output that I get, but I can't find what it is).

If anyone can help me with what is going wrong with the 2 cases in which the output is wrong I would appreciate it very very much. My code is below.

[highlight=vb]

Public Class Form1

Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click

Dim counter As Integer = 0, counter2 As Integer = 0, temp As Integer = 0
Dim Half As Integer
Dim Test As Boolean = False
RichTextBox1.Text = RichTextBox1.Text.Replace(" ", "")
RichTextBox1.Text = RichTextBox1.Text.Replace(".", "")
RichTextBox1.Text = RichTextBox1.Text.Replace(vbLf, "")

Dim j As Integer = RichTextBox1.Text.Length

If RichTextBox1.Text.Length Mod 2 Then
' just for help to test MsgBox("You've put an odd no. of Chars.")
Half = Math.Floor((RichTextBox1.Text.Length - 1) / 2)

For i = 0 To Half - 1

For j = RichTextBox1.Text.Length - 1 To 0 Step -1
If i < Half Then
If RichTextBox1.Text.Chars(i) = RichTextBox1.Text.Chars(j) Then
MsgBox(RichTextBox1.Text.Chars(i) & RichTextBox1.Text.Chars(j))
counter = counter + 2
Else
MsgBox("Same chars at respective places are " & counter)
Test = True
MsgBox("Test became true")
Exit For
End If
i += 1
Else
'i += 1
End If
' i = i + 1
Next

If Test = True Then Exit For

Next

Else
' just for help to test MsgBox("You've put an even no. of Chars.")
Half = Math.Floor((RichTextBox1.Text.Length) / 2)
MsgBox(Half)

For i = 0 To Half - 1

For j = RichTextBox1.Text.Length - 1 To Half Step -1
If i < Half Then
If RichTextBox1.Text.Chars(i) = RichTextBox1.Text.Chars(j) Then
' MsgBox(RichTextBox1.Text.Chars(i) & RichTextBox1.Text.Chars(j))
counter = counter + 2

Else
MsgBox("Same chars at respective places are " & counter)
Test = True
MsgBox("Test became true")
Exit For
' j -= 1
End If
i += 1
' Exit For

End If

Next

If Test = True Then Exit For

Next

End If

If counter / 2 = Half Then
MsgBox("This text is a palindrome, it doesn't need any additional character.")
Else

' For j = RichTextBox1.Text.Length - 1 To 1 Step -1
'If RichTextBox1.Text.Chars(j) = RichTextBox1.Text.Chars(j - 1) Then

For i = 0 To RichTextBox1.Text.Length - 2
If RichTextBox1.Text.Chars(i + 1) = RichTextBox1.Text.Chars(i) Then
counter2 = counter2 + 1
MsgBox("The no. of same straight chars atm is " & counter2)
If temp <= counter2 Then
temp = counter2
MsgBox("Biggest same straight char no. is " & temp)
End If

MsgBox(counter2)
Else
counter2 = 0
End If

Next
If counter2 <= temp Then
counter2 = temp
End If
MsgBox("Temp =" & temp)

MsgBox("This text is not a palindrome, it needs " & (RichTextBox1.Text.Length - 1 - counter - temp) & " chars to become one.")
End If
'MsgBox(counter)

End Sub

End Class

[/highlight]

 

[snarfblam]

I'm a little confused as to how you get from the input to the output. The code is also difficult to read. Comments are sparse and everything is shoved into a single function. I'd like to help, but I already have a headache.

 

[Legjendat]

Added some detailed info on how i am trying to make things work below.

i'm a little confused as to how you get from the input to the output. The code is also difficult to read. Comments are sparse and everything is shoved into a single function. I'd like to help, but i already have a headache.

so, i'm having a very difficult task here. I need to analyze a certain text and find the minimum number of characters it needs to become a palindrome. The text will not have any special characters or numbers, just alphabet letters. Now, i've made some progression and have tried a lot of situations correctly, but in some situations i've gotten wrong outputs on the minimum number of characters needed. I've tested the below texts:

Aaabbbbccccc - aaabbbbcccccbbbbaaa ✓ 7
cccccbbbbaaa - aaabbbbcccccbbbbaaa ✓ 7
bbbbcccccaaa - aaabbbbcccccbbbbaaa ✓ 7
faslli - fas-i-lli-saf ✓ 4
arben - arben-ebra ✓ 4
arbena - arben-ebr-a ✓ 3
arbana - arban-abr-a ✓ 3
all - all-a ✓ 1
allll - allll-a ✓ 1
baoub - baou-oa-b ✓ 2
asdrfff - asdrfff-drsa ✓ 4
aaabbb - aaabbb-aaa / bbb-aaabbb ✓ 3
arbenarben - arbenarben-ebranebra ✓ 9
allall - allall-a wrong , outputs "4" when all there's needed is 1.
Aaabbbbaaabbbbccccc - cccccbbbb-aaabbbbaaabbbbccc wrong, outputs 14 when all there's needed is 9 chars. In this case there should be noted that there are 2 palindromes within the text (as in substrings which may have something to do with the wrong output that i get, but i can't find what it is).

If anyone can help me with what is going wrong with the 2 cases in which the output is wrong i would appreciate it very very much. My code is below.

[highlight=vb]


'the program is in gui, so i have a windows form, a richtextbox and a button.
Public class form1

private sub button1_click(sender as system.object, e as system.eventargs) handles button1.click

dim counter as integer = 0, counter2 as integer = 0, temp as integer = 0
dim half as integer
dim test as boolean = false
richtextbox1.text = richtextbox1.text.replace(" ", "")
richtextbox1.text = richtextbox1.text.replace(".", "")
richtextbox1.text = richtextbox1.text.replace(vblf, "")
'up to now i removed the spaces, dots and lines from the text as i want to analyze pure text ie letters only.


Dim j as integer = richtextbox1.text.length

if richtextbox1.text.length mod 2 then
' just for help to test msgbox("you've put an odd no. Of chars.")
half = math.floor((richtextbox1.text.length - 1) / 2)

'finding the mid point of the inputted text(text is typed on the richtextbox)

'* all msgboxes below are only for helping purposes, they help me check what the program is doing.

For i = 0 to half - 1

for j = richtextbox1.text.length - 1 to 0 step -1
if i < half then
if richtextbox1.text.chars(i) = richtextbox1.text.chars(j) then
msgbox(richtextbox1.text.chars(i) & richtextbox1.text.chars(j))
counter = counter + 2
else
msgbox("same chars at respective places are " & counter)
test = true
msgbox("test became true")
exit for
end if
i += 1
else
'i += 1
end if
' i = i + 1
next

if test = true then exit for

next

'up to now, the code will check if the text is palindrome or not when the
'no. Of characters is odd. It will compare first char to last, 2nd char to 2nd
'char from end and so on, if they are not equal, it means the given text is
'not a palindrome, this code also finds the minimum no. Of chars to make
'a given text a palindrome if there are no repeated letters on the text, ie
'visual needs 6-1 letters to become a palindrome.


Else
' just for help to test msgbox("you've put an even no. Of chars.")
half = math.floor((richtextbox1.text.length) / 2)
msgbox(half)

for i = 0 to half - 1

for j = richtextbox1.text.length - 1 to half step -1
if i < half then
if richtextbox1.text.chars(i) = richtextbox1.text.chars(j) then
' msgbox(richtextbox1.text.chars(i) & richtextbox1.text.chars(j))
counter = counter + 2

else
msgbox("same chars at respective places are " & counter)
test = true
msgbox("test became true")
exit for
' j -= 1
end if
i += 1
' exit for

end if

next

if test = true then exit for

next

end if

'the code between the last "big" commenting up to now does the same
'thing as in the "big" commenting, but for a text with an even no. Of
'characters.






If counter / 2 = half then
msgbox("this text is a palindrome, it doesn't need any additional character.")

'i think the above code is self-explanatory, if the counter made it to the
'half, then the text is self explanatory, else it isn't and we get some more
'piece of code.
Else

' for j = richtextbox1.text.length - 1 to 1 step -1
'if richtextbox1.text.chars(j) = richtextbox1.text.chars(j - 1) 'then

for i = 0 to richtextbox1.text.length - 2
if richtextbox1.text.chars(i + 1) = richtextbox1.text.chars(i) then
counter2 = counter2 + 1
msgbox("the no. Of same straight chars atm is " & counter2)
if temp <= counter2 then
temp = counter2
msgbox("biggest same straight char no. Is " & temp)
end if

msgbox(counter2)
else
counter2 = 0
end if

next
if counter2 <= temp then
counter2 = temp
end if
msgbox("temp =" & temp)

'now, the code in the block above will try to find the minimum of chars
'needed for text with consecutive same letters, ie aaabbbbccccc. It will put
'the result of (times letter is repeated) into a second counter. This value
'will then be passed to another variable, the variable named "temp". Temp
'will seek the letter that is repeated the biggest number of times
'consecutively. From then i get the number of min. Chars to add as in the
'formula below which is
'the length of the text - 1 - counter-->(same letters from begin and end at
'respective positions) - temp, which gives an accurate result for most
'cases, except for the cases in which there are palindromes within the text
'itself, but not the whole text is a palindrome. I hope it will clear
'something out.



Msgbox("this text is not a palindrome, it needs " & (richtextbox1.text.length - 1 - counter - temp) & " chars to become one.")
end if
'msgbox(counter)

end sub

end class

[/highlight]

 

[snarfblam]

I'll start by saying you really want to avoid variable names such as counter, counter2, temp, test, and j. These names don't tell me anything about what the variable actually stores, and they won't help you much if you need to go back and look at your own code down the road. What is counter counting? What does test test? I would rather look at a variable name like "numOfCharactersThatMatchBetweenTheBeginningOfTheStringAndTheEnd" than "counter".

I spent some time sorting through your code I really just can't understand what it's trying to do. Like I said, I'm a little confused as to how you get from the input to the output. I don't understand the step-by-step process.

arben - arben-ebra

Okay, it looks like the concept is that we would need to reverse and append part of the beginning of the string to create the palindrome. But wait...

faslli - fas-i-lli-saf

Where did that extra "i" come from? And now I'm confused about what the hyphens mean.