This one is driving me nuts

[MrJones]

Hello, Folks! This is my first post and I'm pretty excited about finding this web forum with so many forums dedicated to different fields of sciences, but I thought I'd start here first. I've had this riddle for approximately a week and a half, and it has completely befuddled me:

"Mr. McPita is playing a word game and he has received the letters that spell his name. There is only one word he can make (IMPACT), but first he will have to reorder the letters. To this end, he allows himself two types of moves:

1: Place the letters in the odd positions before the letters in the even positions: M C P I T A => M P T C I A

OR

2: Bring the letter in the first position to the end of the line: M C P I T A => C P I T A M

Using the fewest number of moves (using the above rules) create the word IMPACT."

I'm sure there's probably an easy program that could be written to figure this out, but I am completely at a loss here and I am dying to figure this out. Can someone show me the steps to the answer?? I feel like I've done this 100 different ways, and the closest I've come is IMTPAC.

[MrJones]

Yes.

I thought about using numbers, but I didn't think it would work as well for me.

[DaveC426913]

Sorry, didn't mean to make you look like you were talking to yourself. o:) I deleted my post when I realzied I had nothing of value to add.

[MrJones]

Oh, well I believe it would be valuable to someone who would rather solve the puzzle in a numerical manner, but I prefer to see the letters to solve the riddle.

I'm sure it's rather simple and I'm just not in the right frame of mind to solve it

[davee123]

I wrote a quick program that solved it in 10 steps, using 4 "type 2" moves and 6 "type 1" moves.
The 5th word (of all 11) is "CATIMP"
DaveE
The moves alternate from one to the other, except twice.

[MrJones]

That's fantastic... 10 moves!

I finally got it approximately 2 hours ago, but it took me 21 steps.

10 steps? I have to try this.

[DaveC426913]

I wrote a quick program that solved it in 10 steps, using 4 "type 2" moves and 6 "type 1" moves.


What did your program do? Did it use a brute force permutational approach and you simply waited for it to spit out a valid answer? Or did you use some algorithm?

It seems to me that, unless you used the brute force approach, you would first have to solve the problem - i.e. doing 80% of the heavy-lifting before even being able to write a program to finish it.

[davee123]

I just did a breadth-first search, which guarantees that the first solution it finds is the shortest-length path. There might be several solutions that are all 10 steps long-- It didn't check for those.

To be more explicit, it performed a loop on all known strings-- each of which has a "shortest path" to them. Then, for each one, it performs a "type 1" and a "type 2" modification. If the resultant string is not already in the list of known strings, it adds it to the list, along with the originating string and the modification type. Hence:

Round 1:
Known strings:
MCPITA, distance: 0, originating string: none, explored: no
MCPITA --- Type 1 ---> MPTCIA
MCPITA --- Type 2 ---> CPITAM

Round 2:
Known strings:
MCPITA, distance: 0, originating string: none, explored: yes
(skip)
MPTCIA, distance: 1, originating string: MCPITA, explored: no
MPTCIA --- Type 1 ---> MTIPCA
MPTCIA --- Type 2 ---> PTCIAM
CPITAM, distance: 1, originating string: MCPITA, explored: no
CPITAM --- Type 1 ---> CIAPTM
CPITAM --- Type 2 ---> PITAMC

Round 3:
Known strings:
MCPITA, distance: 0, originating string: none, explored: yes
(skip)
MPTCIA, distance: 1, originating string: MCPITA, explored: yes
(skip)
CPITAM, distance: 1, originating string: MCPITA, explored: yes
(skip)
MTIPCA, distance: 2, originating string: MPTCIA, explored: no
MTIPCA --- Type 1 ---> MICTPA
MTIPCA --- Type 2 ---> TIPCAM
PTCIAM, distance: 2, originating string: MPTCIA, explored: no
PTCIAM --- Type 1 ---> PCATIM
PTCIAM --- Type 2 ---> TCIAMP
CIAPTM, distance: 2, originating string: CPITAM, explored: no
CIAPTM --- Type 1 ---> CATIPM
CIAPTM --- Type 2 ---> IAPTMC
PITAMC, distance: 2, originating string: CPITAM, explored: no
PITAMC --- Type 1 ---> PTMIAC
PITAMC --- Type 2 ---> ITAMCP

Etc.

Anyway, it's probably unnecessarily efficient in this example, because there's only 1024 different permutations that are 10 long-- you could try all the permutations that were 1 long, then 2, then 3, etc, until you got a solution, which would yield the same result, but would do... 2046 actual calculations of the string? That's pretty trivial. The above solution is a tad more efficient in a case like this, but would be MUCH more efficient if (say) the solution were something like 100 permutations out rather than 10.

DaveE

[DaveC426913]

Over my head. And I'm a programmer. :redface:

[MrJones]

Wow... So apparently the program was not so simple. At least it doesn't appear that way...

So what did it find the combination to be (1,2,1,2,2?)

I'm having a hard time reading what it did

[davee123]

So apparently the program was not so simple.

I didn't think it was that complicated-- maybe I've been doing too many projecteuler problems or something. The entirety of the code is:


#!/usr/bin/perl

%strs = ('MCPITA' => { dist => 0, from => '', type => 0, exp => 0, });
MLOOP: for($i=0;$i<100;$i++) {
foreach my $str (keys %strs) {
next if($strs{$str}{exp});
$m1 = move1($str);
if(!exists($strs{$m1}) || $strs{$m1}{dist} > ($strs{$str}{dist}+1)) {
$strs{$m1} = { dist => ($strs{$str}{dist} + 1), from => $str, type => 1, };
last MLOOP if($m1 eq "IMPACT");
}
$m2 = move2($str);
if(!exists($strs{$m2}) || $strs{$m2}{dist} > ($strs{$str}{dist}+1)) {
$strs{$m2} = { dist => ($strs{$str}{dist} + 1), from => $str, type => 2, };
last MLOOP if($m2 eq "IMPACT");
}
$strs{$str}{exp} = 1;
}
}

$str = "IMPACT";
while($strs{$str}{dist} && !$strs{$str}{done}) {
$strs{$str}{done} = 1;
print "$str \<-- $strs{$str}{from} ($strs{$str}{type})\n";
$str = $strs{$str}{from};
}

sub move1 {
my($str) = @_;
my($odds,$evens);
for(my $i=0;$i<length($str);$i++) {
if($i % 2) { $odds .= substr($str,$i,1); }
else { $evens .= substr($str,$i,1); }
}
return "$evens$odds";
}

sub move2 {
my($str) = @_;
return substr($str,1).substr($str,0,1);
}




So what did it find the combination to be (1,2,1,2,2?)

The output of the program is:
IMPACT <-- TIMPAC (2)
TIMPAC <-- TPIAMC (1)
TPIAMC <-- TAPMIC (1)
TAPMIC <-- TMAIPC (1)
TMAIPC <-- CTMAIP (2)
CTMAIP <-- CATIMP (1)
CATIMP <-- PCATIM (2)
PCATIM <-- PTCIAM (1)
PTCIAM <-- MPTCIA (2)
MPTCIA <-- MCPITA (1)

(Which just shows the progression in reverse)

DaveE