Conversion to palindrome with minimal points used

Question

Input: a word (2-100 characters)

Convert this word to a palindrome:

• delete character - 13 points
• add character - 12 points
• increase character - 5 points ('d' > 'e')
• decrease character - 4 points ('n' > 'm')
• switch 2 characters - 7 points

What is the minimal points needed to make the word palindrome? (C++/C#)

Output: Minimal points needed to convert the word

Winning criteria: fastest algorithm

Answer 1

Spent about an hour and got a working solution that I believe should give an optimal result:

public class PalindromeFinder : IComparer<Tuple<int,string>>
    {
        public PalindromeFinder()
        {
            heap = new IntervalHeap<Tuple<int, string>>(this);
            handles = new Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>();
        }

        private readonly IntervalHeap<Tuple<int, string>> heap;
        private readonly Dictionary<string, IPriorityQueueHandle<Tuple<int, string>>>  handles; 

        public int FindMinValue(string startingWord)
        {
            AddWord(startingWord,0);
            while(!heap.IsEmpty)
            {

                var item = heap.DeleteMin();
                var word = item.Item2;
                var value = item.Item1;
                handles.Remove(word);
                if(IsPalindrome(word))
                {
                    return value;
                }
                for(int i = 0; i<word.Length; i++)
                {
                    //decrease
                    var decreased = word.ToCharArray();
                    if (decreased[i] > 'a')
                    {
                        decreased[i]--;
                        AddWord(new string(decreased), value + 4);
                    }
                    //switch
                    for(int j = i+1; j<word.Length; j++)
                    {
                        if (word.Count(x => x == word[i]) >= 2 || word.Count(x => x == word[j]) >= 2)
                        {
                            var swap = word.ToCharArray();
                            var tmp = swap[i];
                            swap[i] = swap[j];
                            swap[j] = tmp;
                            AddWord(new string(swap), value + 7);
                        }
                    }
                    //add character before (only add characters already present)
                    foreach (char c in word.Distinct())
                    {
                        var added = word.Insert(i, c.ToString());
                        AddWord(added, value+12);
                    }
                }
                //add character at end of word
                foreach (char c in word.Distinct())
                {
                    var added = word + c.ToString();
                    AddWord(added, value + 12);
                }
            }
            return int.MaxValue;
        }

        private void AddWord(string word, int value)
        {
            var min = int.MaxValue;
            if(handles.ContainsKey(word))
            {
                var tuple = heap.Delete(handles[word]);
                min = tuple.Item1;
                handles.Remove(word);
            }
            IPriorityQueueHandle<Tuple<int, string>> handle = null;
            heap.Add(ref handle,new Tuple<int, string>(Math.Min(min, value), word));
            handles[word] = handle;
        }

        private bool IsPalindrome(string word)
        {
            int left = 0;
            int right = word.Length - 1;
            while(left<right)
            {
                if (word[left] != word[right]) return false;
                left++;
                right--;
            }
            return true;
        }

        public int Compare(Tuple<int, string> x, Tuple<int, string> y)
        {
            return x.Item1 - y.Item1;
        }
    }

Uses priority queue implementation from C5 collections. This is basically the brute force best-first search solution to the problem. It runs out of memory pretty fast, and is less efficient than is probably possible. I could fix that by implementing a better data structure like a DAWG, but out of time for now. Maybe later.It does work well for short words, and even for long ones that are within a few steps of a palindrome already.

Edit:

Made some improvements on Peter's suggestion, but the complexity is still too high. On input: "superman", runs for about a minute until it runs out of memory with over 11 million items in heap and a max value of 42 reached. Still a bit off from being a viable general solution.

Answer 2

C++

Made this under the assumption that simply changing the character costs the same as switching two characters(7 points) & that comparing costs 0 points. A pretty basic & dumb solution, but it works.

int main(int argc, char *argv[]) {
    int c, l, p;
    p = 0;
    if(argc != 2) { 
        cout<<"Incorrect arguments\n";
        return 1;
    }
    else if(strlen(argv[1])<2 || strlen(argv[1])>100) {
        cout<<"Not a valid string(between 2 & 100 characters)\n";
        return 1;
    }
    l = strlen(argv[1]);
    c = l/2;
    for(int i=0;i<c;i++) {
        if(argv[1][i] != argv[1][l-i-1]) {
            argv[1][i] = argv[1][l-i-1];
            p+=7;
        }
    }
    cout<<argv[1]<<endl<<p<<endl;
    return 0;
}