Fixing an Anagram
Back to General discussions forum
Hi Rodion, thanks for the new problem.
Question regarding the 3rd example:
Position 0 is only involved in a single swap - the first one: 0:5.
That moves an E to the start of the string, but that doesn't match the second string.
Am I misunderstanding something?
Mathias, thanks for quick reaction!
this example contained wrong anagram (source string) - seemingly picked from the wrong test run in my console :( I think I identified the correct one and replaced it, please have a look.
Hey Rodion,
Thank you for new interesting puzzle!
I have tried it as you suggested in another topic and got the following error: Too many steps for CIRCULARIZED
This is for the following test case:
CURRAIZLDICE CIRCULARIZED
Well, this should mean that your suggested chain of swaps is longer than one found by checker. Perhaps this phrase needs to be emphasized in the problem statement, sorry. If you can give specific chain proposed by your solution, we can try checking manually, if better option exists.
A chain proposed by my solution is:
1:4,1:5,3:7,3:5,3:6,3:9,3:8,3:10,10:11
This leads to following transformations:
CURRAIZLDICE =>
CARRUIZLDICE =>
CIRRUAZLDICE =>
CIRLUAZRDICE =>
CIRAULZRDICE =>
CIRZULARDICE =>
CIRIULARDZCE =>
CIRDULARIZCE =>
CIRCULARIZDE =>
CIRCULARIZED
I noticed that on first step you chose to put second I in place instead of first. There must be some trick when choosing between same letters...
I was able to solve CURRAIZLDICE CIRCULARIZED by considering all ways with which same letters could be swapped, but now my program works too slow.
Before that improvement, program worked for any string in blink of eye, but now...
MSHFEAIERENTCNSNID DISENFRANCHISEMENT
...was solved in around 5 minutes, and...
SNADAAERIGINANSATTDVTTNPOALD. TRANSPLANTATION.DISADVANTAGED
...was solved in more than hour.
Are there any way to speed things up?
Are there any way to speed things up?
That sounds a bit queer. The matter is I don't know a fair solution myself so che checker searches for "reference" sequence of steps in somewhat straightforward manner. It may take 1-2 second when data are prepared (on page loading).
Supposing you also implemented some brute-force like approach, I guess there should be a great potential to improve it. Probably there is some dramatic inefficiency in data manipulation etc.
Standard recursion.
My solution is highly optimized and uses recursion only when it really have to (it uses recursion as a tiebreaker in case of several same letters).
You want to say that solution that uses recursion on every step can solve this problem so fast? I hardly can believe that...
The number of possible letter swaps in anagram of length n is:
(n - 1) + (n - 2) + ... + 1 = n * (n - 1) / 2
The number of possible variants to consider in case of standard recursion is:
m * (m - 1) * ... * 1 = m!
Where:
m = n * (n - 1) / 2
Isn't it a bit too much?
My solution is O(2^n) instead of yours O((n^2)!), but it is still too much. I need to improve.
Of course there is a bit more than just recursion to it, but recursion is key.
Without giving too much away: imagine a function make_anagram(s, t, i)
that works out the swaps required if everything up to position i is the same in strings s and t and you only
look from position i onwards - what are the cases, and how could you break this down into a mix of recursion and brute force?
The number of possible letter swaps in anagram of length n is:
should the solution try swaps which do not increase amount of letters in proper places?
Hi, gardengnome and Rodion.
I did it as you suggested. Wrote an recursive function and followed your advices:
Following gardengnome's advice, I added a parameter k to recursive function which means that everything up to position k is the same in strings s and t. I called this parameter k because variable i already used in loop as starting index of swap.
Following Rodion's advice, I added conditional expressions which restricts swaps and recursion. Swaps are only made if they increase number of letters at proper places at least by one.
Unfortunately, the new code again works more than a hour for some testcases. I feels so down :(
Submitted my code to the site as failed attempt in case I return someday to this task to investigate further.
qwerty: since you are using recursion, perhaps there is no need to check all pairs of swappable letters in the remaining portion of the string? Perhaps one of the letters could be fixed, in the way that would allow you to call your recursive function with a different value of k?
To add to zelevin's comment: if everything in s and t is the same up to position k, let's not worry about fixing
the entire string s from k onwards but break it down into two smaller steps: i) how to fix position k itself
(you know which letter you need there) and ii) recursively fix positions from k+1.
Textbook recursion.
I'll leave the case work for part i) to you. ;)
Finally solved this puzzle thanks to your advices.
The only change I made in code is replacement of:
for i in range(k, n - 1):
to
for i in [k]:
and it was enough to speed program execution time from hours of work to less than second :)
it looks a bit like overengineering :)
but it's truly - the puzzle is bit easier to solve than to understand / prove the solution
Hi Rodion, in very (un)lucky circumstances the two strings can be identical (just had that).
It is not clear what the expected output should be in such a case, and how the checker would identify it correctly
(the empty string wasn't recognised).
I suggest to add a litlle check s!=t to the problem generator.
My output for this special case was 0:0. It is ok or a wrong answer?
Sorry Friends, I wanted to quickly address the issue mentioned by Mathias, but got distracted.
Now the code is updated and such things shouldn't happen, hm, hopefully :)
As for 0:0 it doesn't look as good answer as it suggest at least one dummy swap is made. In other words it looks
like output format simply won't allow specifying empty sequence.
I agree that dummy swap is not a good answer, but it is a possible workaround which allows to meet output format. I'm happy to hear there is no need in such workaround now.