Discrete Baker's Map

Question

Introduction

The Baker's map is an important dynamical system that exhibits chaotic behavior. It is a function from the unit square to itself defined intuitively as follows.

• Cut the square vertically in half, resulting in two rectangles of size 0.5×1.
• Stack the right half on top of the left, resulting in one rectangle of size 0.5×2
• Compress the rectangle back into a 1×1 square.

In this challenge, you'll implement a discrete version of this transformation.

Input and Output

Your input is a 2D array of printable ASCII characters and whitespace of size 2m×2n for some m, n > 0. Your output is a similar array obtained as follows, using the 6×4 array

ABCDEF
GHIJKL
MNOPQR
STUVWX

as an example. First, stack the right half of the array on top of the left half:

DEF
JKL
PQR
VWX
ABC
GHI
MNO
STU

Then, split the columns into pairs of characters, and independently turn each pair 90 degrees clockwise, "compressing" the tall rectangle back to the original shape:

JDKELF
VPWQXR
GAHBIC
SMTNUO

This is the correct output for the above array.

Rules

The input and output formats are flexible. You can use newline-delimited strings, lists of strings, or 2D arrays of characters. However, the input and output must have the exact same format: you must be able to iterate your submission an arbitrary number of times on any valid input.

You can write either a full program or a function. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

Input:
12
34

Output:
42
31

Input:
Hell
!  o
d  -
lroW

Output:
 lol
o W-
!H e
ldr 

Input:
ABCDEF
GHIJKL
MNOPQR
STUVWX

Output:
JDKELF
VPWQXR
GAHBIC
SMTNUO

Input:
*___  ___  o
o|__) |__) *
*|    |    o
o __   __  *
*|    | _  o
o|__  |__| *

Output:
|_____)   *o
 |_ _     *o
||_ __|   *o
o*|_____)   
o* |_ _     
o*||_ _     

Answer 1

Pyth, 25 19 18 bytes

msC_dcs_Cmck/lk2Q2

Online demonstration. It uses an 2D-array of chars.

Array of strings is one char longer (19 bytes). Online demonstration

Explanation:

         m      Q    map each string k in input:
            /lk2        calculate half the line-length: len(k)/2
          ck/lk2        chop k into pieces of length len(k)/2
                        results in two pieces
        C            zip the resulting list
                     results in a tuple ([first half of strings], [second half of strings])
       _             invert the order ([second half of strings], [first half of strings])
      s              sum (combine the two lists to a big one
     c           2   chop them into tuples
m                          for each tuple of strings: 
 sC_d                        invert, zip, and sum

The last part is a bit confusing at first. Let's assume we have the tuple ['DEF', 'JKL'] (I use the example from the OP).

    d  (('D', 'E', 'F'), ('J', 'K', 'L'))   just the pair of strings
   _d  (('J', 'K', 'L'), ('D', 'E', 'F'))   invert the order
  C_d  [('J', 'D'), ('K', 'E'), ('L', 'F')] zipped
 sC_d  ('J', 'D', 'K', 'E', 'L', 'F')       sum (combine tuples)

Answer 2

Julia, 136 bytes

A very straightforward implementation. Not a particularly competitive entry, but it was fun!

A->(s=size(A);w=s[2];u=w÷2;C=vcat(A[:,u+1:w],A[:,1:u]);D=cell(s);j=1;for i=1:2:size(C,1) D[j,:]=vec(flipdim(C[i:i+1,:],1));j+=1end;D)

This creates a lambda function that accepts a 2-dimensional array as input and returns a transformed 2-dimensional array.

Ungolfed + explanation:

function f(A)

    # Determine bounds
    s = size(A)          # Store the array dimensions
    w = s[2]             # Get the number of columns
    u = w ÷ 2            # Integer division, equivalent to div(w, 2)

    # Stack the right half of A atop the left
    C = vcat(A[:, u+1:w], A[:, 1:u])

    # Initialize the output array with the appropriate dimensions
    D = cell(s)

    # Initialize a row counter for D
    j = 1

    # Loop through all pairs of rows in C
    for i = 1:2:size(C, 1)

        # Flip the rows so that each column is a flipped pair
        # Collapse columns into a vector and store in D
        D[j, :] = vec(flipdim(C[i:i+1, :], 1))

        j += 1
    end

    return D
end

To call it, give the function a name, e.g. f=A->(...).

Example output:

julia> A = ["A" "B" "C" "D" "E" "F";
            "G" "H" "I" "J" "K" "L";
            "M" "N" "O" "P" "Q" "R";
            "S" "T" "U" "V" "W" "X"]
julia> f(A)

4x6 Array{Any,2}:
 "J"  "D"  "K"  "E"  "L"  "F"
 "V"  "P"  "W"  "Q"  "X"  "R"
 "G"  "A"  "H"  "B"  "I"  "C"
 "S"  "M"  "T"  "N"  "U"  "O"

julia> B = ["H" "e" "l" "l";
            "!" " " " " "o";
            "d" " " " " "-";
            "l" "r" "o" "W"]
julia> f(B)

4x4 Array{Any,2}:
 " "  "l"  "o"  "l"
 "o"  " "  "W"  "-"
 "!"  "H"  " "  "e"
 "l"  "d"  "r"  " "

And proof that it can be arbitrarily chained:

julia> f(f(B))

4x4 Array{Any,2}:
 "W"  "o"  "-"  "l"
 "r"  " "  " "  "e"
 "o"  " "  " "  "l"
 "l"  "!"  "d"  "H"

Suggestions are welcome as always, and I'll happy provide any further explanation.

Answer 3

CJam, 25 24 bytes

qN/_0=,2/f/z~\+2/Wf%:zN*

Straight forward spec implementation. Explanation:

qN/                       "Split input by rows";
   _0=,2/                 "Get half of length of each row";
         f/               "Divide each row into two parts";
           z              "Convert array of row parts to array of half columns parts";
            ~\+           "Put the second half of columns before the first half and join";
               2/         "Group adjacent rows";
                 Wf%      "Flip the row pairs to help in CW rotation";
                    :z    "Rotate pairwise column elements CW";
                      N*  "Join by new line";

Try it online here

Answer 4

JavaScript (ES6), 104 141

Edit Reviewing the spec, I found that the number of rows must be even (I missed this before). So it's not too complicated find the correct source position for each char in output in a single step.

F=a=>a.map((r,i)=>
  [...r].map((c,k)=>
     a[l=i+i]?a[(j=l+1)-k%2][(k+r.length)>>1]:a[l-j-k%2][k>>1]
  ).join('')
)

Test In Firefox/FireBug console

;[["ABCDEF","GHIJKL","MNOPQR","STUVWX"]
 ,["12","34"], ["Hell","!  o","d  -","lroW"]
 ,["*___  ___  o","o|__) |__) *","*|    |    o","o __   __  *","*|    | _  o","o|__  |__| *"]
].forEach(v=>console.log(v.join('\n')+'\n\n'+F(v).join('\n')))

Output

ABCDEF
GHIJKL
MNOPQR
STUVWX

JDKELF
VPWQXR
GAHBIC
SMTNUO

12
34

42
31

Hell
!  o
d  -
lroW

 lol
o W-
!H e
ldr 

*___  ___  o
o|__) |__) *
*|    |    o
o __   __  *
*|    | _  o
o|__  |__| *

|_____)   *o
 |_ _     *o
||_ __|   *o
o*|_____)   
o* |_ _     
o*||_ _     

Answer 5

J, 45 39 bytes

   $$[:,@;@|.@|:([:,:~2,2%~1{$)<@|:@|.;.3]

J has a tessellation function (cut ;.) which helps a lot.

   ]input=.4 6$97}.a.
abcdef
ghijkl
mnopqr
stuvwx

   ($$[:,@;@|.@|:([:,:~2,2%~1{$)<@|:@|.;.3]) input
jdkelf
vpwqxr
gahbic
smtnuo

Answer 6

Haskell, 128 127 bytes

import Control.Monad
f=g.ap((++).map snd)(map fst).map(splitAt=<<(`div`2).length)
g(a:b:c)=(h=<<zip b a):g c
g x=x
h(a,b)=[a,b]

Usage: f ["12", "34"] -> ["42","31"]

How it works:

                                 input list:
                                   ["abcdef", "ghijkl", "mnopqr", "stuvwx"]
==========================================================================

map(splitAt=<<(`div`2).length)   split every line into pairs of halves:
                                   -> [("abc","def"),("ghi","jkl"),("mno","pqr"),("stu","vwx")]
ap((++).map snd)(map fst)        take all 2nd elements of the pairs and
                                 put it in front of the 1st elements:
                                   -> ["def","jkl","pqr","vwx","abc","ghi","mno","stu"]
(    zip b a) : g c              via g: take 2 elements from the list and
                                 zip it into pairs (reverse order), 
                                 recur until the end of the list:
                                   -> [[('j','d'),('k','e'),('l','f')],[('v','p'),('w','q'),('x','r')],[('g','a'),('h','b'),('i','c')],[('s','m'),('t','n'),('u','o')]]
h=<<                             convert all pairs into a two element list
                                 and concatenate:
                                   -> ["jdkelf","vpwqxr","gahbic","smtnuo"]  

Edit: @Zgarb found a byte to save.

Answer 7

J, 33 32 characters

A monadic verb.

0 2,.@|:_2|.\"1-:@#@{.(}.,.{.)|:

Explanation

Let's begin by defining Y to be our sample input.

   ] Y =. a. {~ 65 + i. 4 6          NB. sample input
ABCDEF
GHIJKL
MNOPQR
STUVWX

The first part (-:@#@{. (}. ,. {.) |:) splits Y in half and appends then ends:

   # {. Y                            NB. number of columns in Y
6
   -: # {. Y                         NB. half of that
3
   |: Y                              NB. Y transposed
AGMS
BHNT
CIOU
DJPV
EKQW
FLRX
   3 {. |: Y                         NB. take three rows
AGMS
BHNT
CIOU
   3 }. |: Y                         NB. drop three rows
DJPV
EKQW
FLRX
   3 (}. ,. {.) |: Y                 NB. stitch take to drop
DJPVAGMS
EKQWBHNT
FLRXCIOU

In the second part (_2 |.\"1) we split this into pairs of two and reverse them:

   R =. (-:@#@{. (}. ,. {.) |:) Y    NB. previous result
   _2 <\"1 R                         NB. pairs put into boxes
┌──┬──┬──┬──┐
│DJ│PV│AG│MS│
├──┼──┼──┼──┤
│EK│QW│BH│NT│
├──┼──┼──┼──┤
│FL│RX│CI│OU│
└──┴──┴──┴──┘
   _2 <@|.\"1 R                      NB. reversed pairs
┌──┬──┬──┬──┐
│JD│VP│GA│SM│
├──┼──┼──┼──┤
│KE│WQ│HB│TN│
├──┼──┼──┼──┤
│LF│XR│IC│UO│
└──┴──┴──┴──┘

Finally (0 2 ,.@|:), we transpose the matrix as needed and discard the trailing axis:

   ] RR =. _2 |.\"1 R                NB. previous result
JD
VP
GA
SM

KE
WQ
HB
TN

LF
XR
IC
UO
   0 2 |: RR                         NB. transpose axes
JD
KE
LF

VP
WQ
XR

GA
HB
IC

SM
TN
UO
   ($ RR) ; ($ 0 2 |: RR)            NB. comparison of shapes
┌─────┬─────┐
│3 4 2│4 3 2│
└─────┴─────┘
   ,. 0 2 |: RR                      NB. discard trailing axis
JDKELF
VPWQXR
GAHBIC
SMTNUO

The whole expression with whitespace inserted:

0 2 ,.@|: _2 |.\"1 -:@#@{. (}. ,. {.) |:

And as an explicit verb:

3 : ',. 0 2 |: _2 |.\"1 (-: # {. y) (}. ,. {.) |: y'

Answer 8

GNU sed -r, 179 bytes

Score includes +1 for the -r arg to sed.

It took me a while to figure out how to do this in sed, but I think I have it now:

# Insert : markers at start and end of each row
s/  /:  :/g
s/(^|$)/:/g
# Loop to find middle of each row
:a
# Move row start and end markers in, one char at a time
s/:([^  :])([^  :]*)([^ :]):/\1:\2:\3/g
ta
# Loop to move left half of each row to end of pattern buffer
:b
s/([^   :]+)::(.*)/\2   \1/
tb
# remove end marker
s/$/:/
# double loop to merge odd and even rows
:c
# move 1st char of rows 2 and 1 to end of pattern buffer
s/^([^  :])([^  ]*) ([^ ])(.*)/\2   \4\3\1/
tc
# end of row; remove leading tab and add trailing tab 
s/^ +(.*)/\1    /
tc
# remove markers and trailing tab
s/(:|   $)//g

Note all the whitespace above should be single tab characters. Comments are not included in the golf score.

Note also that this makes extensive use of : marker characters. If the input stream contains :, then undefined behaviour will ensue. This can be mitigated by replacing all : with some non-printing character (e.g. BEL) at no cost to the golf score.

Input and output is a tab-separated list of strings:

$ echo 'Hell
!  o
d  -
lroW' | paste -s - | sed -rf baker.sed | tr '\t' '\n'
 lol
o W-
!H e
ldr 
$