Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

This one is driving me nuts

  1. Aug 30, 2009 #1
    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.
     
  2. jcsd
  3. Aug 30, 2009 #2
    Yes.

    I thought about using numbers, but I didn't think it would work as well for me.
     
  4. Aug 30, 2009 #3

    DaveC426913

    User Avatar
    Gold Member

    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.
     
  5. Aug 30, 2009 #4
    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
     
  6. Aug 31, 2009 #5
    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.
     
    Last edited: Aug 31, 2009
  7. Aug 31, 2009 #6
    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.
     
  8. Aug 31, 2009 #7

    DaveC426913

    User Avatar
    Gold Member

    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.
     
  9. Aug 31, 2009 #8
    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
     
    Last edited: Aug 31, 2009
  10. Sep 1, 2009 #9

    DaveC426913

    User Avatar
    Gold Member

    Over my head. And I'm a programmer. :redface:
     
  11. Sep 1, 2009 #10
    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
     
  12. Sep 1, 2009 #11
    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:

    Code (Text):

    #!/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);
    }
     


    The output of the program is:
    Code (Text):
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: This one is driving me nuts
  1. Customers drive me nuts! (Replies: 40)

Loading...