14
\$\begingroup\$

Fannkuch is a classic benchmark program. The name comes from the German "Pfannkuchen"- pancakes- for the algorithm's resemblance to flipping stacks of pancakes. A Fannkuch sequence of numbers is formed as follows:

Take a permutation of {1.....n}, for example: {4,2,1,5,3}. Take the first element, here 4, and reverse the order of the first 4 elements: {5,1,2,4,3}. Repeat this until the first element is a 1, so flipping won't change anything more: {3,4,2,1,5}, {2,4,3,1,5}, {4,2,3,1,5}, {1,3,2,4,5}

You are to write a program or function which calculates a Fannkuch-like sequence for strings of alphabetic characters. Instead of using numbers to indicate how many elements of the list should be flipped each time, the position of a letter in the alphabet should be used. For example, a leading c would indicate that you should reverse the order of the first 3 elements, while a leading a indicates that the sequence is complete.

Input

Input will be provided as a string via stdin or as a function argument. The string will contain between 1 and 26 distinct lowercase letters. Strings will not contain letters whose equivalent index would cause the Fannkuch algorithm to flip more elements than exist.

Output

Programs or functions should return or print to stdout the sequence of terms produced by applying the Fannkuch algorithm until a leading a is encountered, including the initial string. For example, if the input is bca, you might print:

bca
cba
abc

Printed results can use any reasonable separator- commas, newlines, etc. Any choice of whitespace is acceptable.

As another example, if your input is eabdc you might return:

("eabdc"
 "cdbae"
 "bdcae"
 "dbcae"
 "acbde")

Rules and Scoring

This is - the shortest program wins. Standard Loopholes are disallowed.

\$\endgroup\$
11
\$\begingroup\$

Pyth, 16 bytes

.u+_<NJhxGhN>NJz

Demonstration.

The "repeat until it stops changing" feature of Pyth's reduce functions is really handy here. This is used with .u, the cumulative reduce function, to output all results. The body of the reduce is as naive as can be, but I couldn't find anything better.

| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

T-SQL, 213 bytes

Of course being SQL it's really large, but it was interesting to do. Created as an inline table function using a recursive CTE query.

CREATE FUNCTION F(@ CHAR(26))RETURNS TABLE RETURN WITH R AS(SELECT @ S UNION ALL SELECT CAST(STUFF(S,1,ASCII(LEFT(S,1))-96,REVERSE(LEFT(S,ASCII(LEFT(S,1))-96)))AS CHAR(26))FROM R WHERE LEFT(S,1)<>'a')SELECT*FROM R

Expanded

CREATE FUNCTION F(@ CHAR(26))
RETURNS TABLE 
RETURN WITH R AS(
    SELECT @ S            -- Initial string as an anchor for the recursion
    UNION ALL 
    SELECT CAST(
        STUFF(                                    -- Stuff into 
            S,                                    -- string S
            1,                                    -- from position 1
            ASCII(LEFT(S,1))-96,                  -- to index value of first char
            REVERSE(LEFT(S,ASCII(LEFT(S,1))-96))  -- the reverse of the index first chars
            )
        AS CHAR(26))
    FROM R 
    WHERE LEFT(S,1)<>'a'  -- recurse until first char is a
)SELECT*FROM R

Used as follows

SELECT * FROM F('eabdc')
S
--------------------------
eabdc                     
cdbae                     
bdcae                     
dbcae                     
acbde                     

(5 row(s) affected)
| improve this answer | |
\$\endgroup\$
4
\$\begingroup\$

CJam, 22 bytes

This is an anonymous function which takes a string on stack and returns a list of string on the stack.

{_,{_0='`-/(W%\+s_}*]}

Try it online here

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Python 2, 59 bytes

def p(l):
 print l;o=ord(l[0])-97
 if o:p(l[o::-1]+l[o+1:])

I guess this is a rather straightforward answer. Uses recursion and Python's slice syntax. Call as: p('eabdc').

| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

SAS, 131 bytes

sub a(s$);outargs s;put s;do while(b ne 1);b=rank(char(s,1))-96;substr(s,1,b)=reverse(substr(s,1,b));if b>1 then put s;end;endsub;

An FCMP call routine. Nongolfed below (with an extra check I highly recommend as SAS crashes if an FCMP routine enters an infinite loop).


options cmplib=work.funcs;
proc fcmp outlib=work.funcs.funcs;
  sub a(s$);
    outargs s;
    put s=;
    do while (b ne 1 and z<1e5);
        b=rank(char(s,1))-96;
        substr(s,1,b) = reverse(substr(s,1,b));
        if b>1 then put s=;
        z+1;
    end;
  endsub;
quit;
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Nice work. We don't get much proc fcmp around here. \$\endgroup\$ – Alex A. Jul 27 '15 at 20:24
2
\$\begingroup\$

Haskell, 78 bytes

f l@(h:_)|h=='a'=[l]|1<2=l:f(reverse(take d l)++drop d l)where d=fromEnum h-96

Usage: f "eabdc" -> ["eabdc","cdbae","bdcae","dbcae","acbde"].

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ consider using splitAt -- you can get it down to 71 bytes! \$\endgroup\$ – MtnViewMark Jul 27 '15 at 5:58
  • \$\begingroup\$ @MtnViewMark well i seem to have the exact same algorithm, down to 68 bytes \$\endgroup\$ – proud haskeller Jul 27 '15 at 8:48
2
\$\begingroup\$

K5, 21 bytes

{(|v#x),(v:*x-96)_x}\

Saved 5 bytes thanks to @JohnE and another byte by rearranging an expression.

For the first time on earth, I think K has beaten CJam!

27-byte version

(~97=*){(|v#x),(v:-96+*x)_x}\
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ You can make this quite a bit shorter if you use the fixed-point form of "scan". \$\endgroup\$ – JohnE Jul 27 '15 at 20:32
  • \$\begingroup\$ @JohnE Thanks! I didn't realize that, when the first letter is an a, the string won't change. \$\endgroup\$ – kirbyfan64sos Jul 27 '15 at 20:52
0
\$\begingroup\$

Haskell, 68

f l@(x:_)|x<'b'=[l]|(x,y)<-splitAt(fromEnum x-96)l=l:f(reverse x++y)

Any more complicated tactic I thought of took more bytes.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.