Combine Palindromes

Computer Science Level 5

Given an array of positive integers ,we would like to convert it to a palindrome. To convert it to a palindrome we are only allowed to combine adjacent pairs (add them together). For example for the array [3, 5, 2, 1] we combine 2 and 1 to get [3, 5, 3] which is a palindrome.

For the array in the text file, what is the minimum number of combinations required to convert it to a palindrome?

Explicit examples :
[1, 2, 3, 2, 1] : 0 combination.
[1, 2, 5, 7] : 3 combinations.

The answer is 36.

2 solutions

Christopher Boo
May 23, 2016

1	`8 2 10 4 7 10 10 2 4 8 2 7 10 2 10 2 5 8 6 4 5 3 6 4 10 7 3 2 1 6 10 9 8 1 3 6 6 3 9 5 7 8 3 7 5 4 2 10 8`

We only need to concentrate on the head and tails of the list. If both numbers are the same, we move on. Else, the smaller one should combine with its neighbor, until we loop through the entire list.

int solve(deque<int> d) {    // push everything into the deque (double-ended queue)

    int cnt = 0;             // number of combines
    while (d.size() > 1) {
        if (d.front() == d.back()) {
            d.pop_front(); d.pop_back();
        }
        else if (d.front() < d.back()) {
            int x = d.front(); d.pop_front();
            d.front() += x;

            cnt++;
        }
        else if (d.front() > d.back()) {
            int x = d.back(); d.pop_back();
            d.back() += x;

            cnt++;
        }
    }

    return cnt;
}

This is a greedy algorithm. That is, there is always a optimal approach regardless of the situation. In this case, we always combine the smaller one to its neighbor, but not the larger one. If we do the latter, it would make it the gap even worse.

Why did you check for numbers at the front and back? Why not start merging from somewhere in the middle?

Siva Bathula - 5 years ago

Good question. First, noticed that any string of numbers can always be transformed into a palindrome after some merging (worst case just merge till one number left). Secondly, a palindrome $S$ is defined recursively such that after the removal of the first and last character, the substring remains a palindrome.

With this two properties, we can only consider the head and tails. After they match, we deal with the substring.

Christopher Boo - 5 years ago

On your second statement, if you start merging from somewhere in between the middle you get a palindrome as well? Example : 1,2,3, 1,2, 2,1?

Siva Bathula - 5 years ago

@Siva Bathula – Technically yes. For your example it will be merging the 4th and 5th number to achieve a palindrome.

1	`1 2 3 3 2 1`

However for larger cases, this is not a very good approach. This is because you don't know where is the "middle" / "core" of the palindrome should be. If your example changed to 1 2 3 1 2 5 1 1 4 1 then we should merge the 5th and 6th, 2nd and 3rd, 8th and 9th numbers. Of course, if you know that the middle of the transformed palindrome is the merged result of 5th and 6th number, then you can loop till the end (head and tails) of the string.

Christopher Boo - 5 years ago

@Christopher Boo – Yep, so the end solution will always be different? The end palindrome as well as the number of steps to reach that palindrome both are different. So the problem is not about the approach, but the least number of combinations needed to convert it to a palindrome?

Siva Bathula - 5 years ago

@Siva Bathula – Yup, you're right.

Christopher Boo - 5 years ago

@Christopher Boo – So although 36 is a possible solution, it may not be the least number of combinations? A better solution can be still be found?

Siva Bathula - 5 years ago

@Siva Bathula – No, $36$ is the least number of merging already.

Christopher Boo - 5 years ago

nice solution, +1

can you please add an example to your problem "Friends (Hard)"? :)

Mehdi K. - 5 years ago

Ahh, I am terribly sorry for that problem. I put the answer as $999$ just to preview the problem statement and forgot to change it back to the correct answer.

Will add an additional example for the problem. :)

Christopher Boo - 5 years ago

"too many things to do, too little time" as I remember XD

Mehdi K. - 5 years ago

Mehdi K.
May 23, 2016

Python3

>>> l = [8, 2, 10, 4, 7, 10, 10, 2, 4, 8, 2, 7, 10, 2, 10, 2, 5, 8, 6, 4, 5, 3, 6, 4, 10, 7, 3, 2, 1, 6, 10, 9, 8, 1, 3, 6, 6, 3, 9, 5, 7, 8, 3, 7, 5, 4, 2, 10, 8]
>>> i = 0
>>> j = len(l) - 1
>>> op = 0
>>> while i < j :
...     a = l[i]
...     b = l[j]
...     while a != b and i < j:
...         if a < b:
...             i += 1
...             a += l[i]
...             op += 1
...         elif a > b:
...             j -= 1
...             b += l[j]
...             op += 1
...     else :
...         i += 1
...         j -= 1
... 
>>> op
36

Nice iterative solution. Also, we have the recursive approach:

from urllib.request import urlopen
def convpal(n):
    if n[0]==n[-1] and len(n)<3: return 0
    elif n[0]==n[-1]: return convpal(n[1:-1])
    elif n[0]>n[-1]: return 1+convpal(n[0:-2]+[n[-1]+n[-2]])
    else: return 1+convpal([n[0]+n[1]]+n[2:])

file=eval(urlopen("http://pastebin.com/raw/UJgD491y").read().decode("utf-8"))
print(convpal(file))

... which gives the output as $36$ .

Prasun Biswas - 5 years ago

Bro this is genius!

Mehdi K. - 5 years ago

Combine Palindromes

The answer is 36.

2 solutions

0 pending reports