Fixing an Anagram

Back to General discussions forum

ThereAreNoUsernamesLeftForMe     2024-06-12 23:44:17

Hi there, I was trying this question and I keep getting issue 'Steps do not lead to original word "blah"' when I try to submit my solution. I have checked the word that flags up on a few submisions in my code and my code rearanges the anagram fine. Could this be due to that my program has a part that checks the word in reverse order as well, to see if this is a more efficiant way of rearanging than looking front to back?

My program consists of two functions:

def fix(anagram, original):

    """ Takes in an anagram and returns the series of swaps done to transform it back to the
        original word.The series of swaps will be the minimum requried swaps"""

    ann_lst = list(anagram)
    swapps = []

    for index,let in enumerate(original):

        # Do nothing if letter is in correct place
        if ann_lst[index] == original[index]:
            continue
        else:
            want_to_swap = ann_lst[index]
            swap_with_letter = original[index]
            i = 1

            # Since we are sorting the word as we are going through it we only need to look at future indexes, not the previous ones
            while index + i <= len(original) - 1:
                # Checks for the letter we want to swap with in the annagram
                if swap_with_letter == ann_lst[index + i]:
                    # Check if a future letter is already in the correct position
                    if ann_lst[index + i] == original[index+i]:
                        i += 1
                        continue
                    else:
                        swapps.append([index,index+i])
                        ann_lst[index],ann_lst[index + i] = ann_lst[index + i],ann_lst[index]
                        break

                i += 1


    # Each list in swapps is the index shift
    return swapps

def rfix(anagram, original):

    """Checks anagram back to front"""

    ann_lst = list(anagram[::-1])
    swapps = []

    for index,let in enumerate(original):

        # Do nothing if letter is in correct place
        if ann_lst[index] == original[index]:
            continue
        else:
            want_to_swap = ann_lst[index]
            swap_with_letter = original[index]
            i = 1

            #Looking through rest of list
            while index + i <= len(original) - 1:
                # Checks for the letter we want to swap with in the annagram 
                if swap_with_letter == ann_lst[index + i]:
                    # Check if a future letter is already in the correct position
                    if ann_lst[index + i] == original[index+i]:
                        i += 1
                        continue
                    else:
                        swapps.append([index,index+i])
                        ann_lst[index],ann_lst[index + i] = ann_lst[index + i],ann_lst[index]
                        break

                i += 1


    return swapps

The last issue text was : 'SENJRIO REJOINS'.

zelevin     2024-06-13 00:06:19

As an extremely basic point: the two functions are not an entire program. There should be something else that accepts and parses the input, and also produces the output in the required format. Without entering into the discussion of the algorithm above (also, please, do not post code in the forum; those who solved the problem can see your unsuccessful attempt), perhaps you can check that the output is formatted correctly?

I have verified that the first function produces the correct swaps for the input you mention. I don't understand the point of the second function, so I cannot comment on that.

ThereAreNoUsernamesLeftForMe     2024-06-14 14:38:29

Ok, thank you for letting me know about posting code and how others can see my unsuccessful attemp.

The reason for the second function is to see if going backwards through the inputted anagram results in less total swaps needed than going front to back. So for instance, if we take the second example input "'NRAAAMG','ANAGRAM'", my second function will give (after changing it to match the desired output format): 0:3,1:6,4,5 , which is less swaps than sorting front to back.

I think my issue may actually be that I am ouptutting the index swaps for the reversed string and the problem checker might check each string front to back with the swaps given in the ' Your answer' box. I will see if I can adjust the indexes accordingly.

zelevin     2024-06-14 16:03:30
 the problem checker might check each string front to back with the swaps given

I would be rather surprized if the problem checker applied the swaps to the string other than what's given as input.

Generally speaking, I am suspicious of the approach of "let's try a couple of permutations of the input and then pick the better result". Why only two, and not, say, all n factorial?

Please login and solve 5 problems to be able to post at forum