title: Is this an L-shape?

text:
# Question
Title: Is this an L-shape?
## Background

An **L-shape** is defined as a polyomino which can be made by extending two rectangular legs in orthogonal directions from a full square (called a pivot). The size of the square should be at least 1, and the lengths of the two legs should also be at least 1.

These are some examples of L-shapes:

```
Pivot size 1, two leg lengths 2 and 4
#
#
#####

Pivot size 2, two leg lengths 1 and 3
#####
#####
   ##

```

These are not:

```
Does not have two orthogonal nonempty legs
####

The pivot is not a square
##
####

One of the legs is not rectangular
#####
####
##
##

Has three legs instead of two
#####
#####
  ##

Has four legs instead of two
  #
#######
  #
  #

Cannot identify a pivot and two legs
##
 ##

Contains one or more holes
#####
# ###
#####
# #
###

Is not a polyomino (the shape is disconnected)
##  #
#  ##

```

## Challenge

Given a zero-one matrix, determine if the ones form a single L-shape.

You should handle inputs containing any amount of margins on all four sides (including no-margin cases), and detect L-shapes in any of the four orientations. For example, the output must be True if the input is any of these:

```
0 0 1 1 1 1 0
0 0 1 1 1 1 0
0 0 1 1 0 0 0

1 1 1
0 0 1
0 0 0

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 0 0 0 0
0 0 0 0 0 0

0 0 0 1 1 0
1 1 1 1 1 0
1 1 1 1 1 0
0 0 0 0 0 0
0 0 0 0 0 0

```

and False if given any of these:

```
1

0 0 0 0
0 1 1 0
0 1 1 0
0 0 0 0

1 0 1
0 0 0
1 0 0

0 0 0 1
0 1 1 1
0 0 1 0
0 0 0 0

0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 1 1 1 0 0

1 1 0 0
1 1 1 1

```

You can choose any reasonable representation of a matrix, and you can assume that the input is always rectangular. You can also choose the two values to represent 0 and 1 respectively.

For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Shortest code in bytes wins.

# Answer
> 8 votes
# 05AB1E, ~~31~~ ~~30~~ 17 bytes

```
ø‚O0δÚDWδåsεÔg<}Q

```

Try it online or verify all test cases.

**Explanation:**

```
ø            # Zip/transpose the (implicit) input-matrix, swapping rows/columns
 ‚           # Pair it together with the (implicit) input-matrix
  O          # Take the sum of each row of both matrices
             # Remove any leading/trailing rows/columns of 0s:
    δ        #  Map over both the inner lists of row-sums:
   0 Ú       #   And trim all leading/trailing 0s
      D      # Duplicate it
             # Check if the pivot is a square:
       W     #  Get the flattened minimum (without popping)
        δ    #  Map over both lists of row-sums:
         å   #   And check if this minimum is present in the row-sums
             #  (this will result in [1,1] if the minimum sum is present in both the
             #   row-sums and column-sums, which means the pivot is a square)
             # Check if the matrix forms an L-shape:
      s      #  Swap so the duplicated pair of row-sums is at the top again
       ε     #  Map over both inner lists:
        Ô    #   Connected uniquify the sums
         g   #   Pop and push the length
          <  #   And decrease this by 1
       }     #  Close the map
             #  (this will result in [1,1] if the matrix forms an L-shape, which means
             #   the lengths were 2 for both the row-sums and column-sums after the
             #   connected uniquify)
             # Check that all four values are truthy:
        Q    #  Check if both pairs are equal
             # (after which the result is output implicitly)

```

NOTE: the `Q` would also incorrectly result in truthy if both pairs are \\$\[1,0\]\\$ for example, but there isn't any test case where both pairs would be the same apart from the truthy \\$\[1,1\]\\$ test cases. (If there were, we could have used `«P` \- merge; check if all four are truthy - instead.) The reason why the pairs can never be the same except for the truthy test cases:

1. We check if the flattened minimum of the sums is present in both inner lists. Since we took the minimum from the lists, this can only ever result in \\$\[1,1\]\\$, \\$\[0,1\]\\$, or \\$\[1,0\]\\$ (this will also result in \\$\[1,1\]\\$ if the input-matrix is empty).
2. The `εÔg<}` will however not result in \\$\[1,1\]\\$ for empty matrices, nor will it ever result in \\$\[0,1\]\\$ or \\$\[1,0\]\\$. For either the sums of rows or columns to result in \\$0\\$, it would mean all values in those rows/columns are equal, but this implicitly means the same applies vice-versa and it's a rectangle matrix of the same values. The `εÔg<}` can only result in:
    * \\$\[-1,-1\]\\$: which meant the input was empty, or only contained \\$0\\$s (try it online);
    * \\$\[0,0\]\\$: which meant the input-matrix was a rectangle of \\$1\\$s, after we've trimmed all leading/trailing \\$0\\$s (try it online);
    * \\$\[1,1\]\\$: our expected truthy result for L-shaped matrices (try it online);
    * or larger than \\$\[1,1\]\\$ \- i.e. \\$\[1,3\]\\$, \\$\[2,4\]\\$, etc.: if the input-matrix contained gaps in one or multiple of the rows/columns (try it online).

# Answer
> 7 votes
# , 51 48 79 bytes

```
(1-'10+1'rxin'012'{~2,@,.],|:)*1&#.(,~&{:-:,&(0{#/.~)+0{,)&(|.^:({.>{:)@-.&0)+/

```

Try it online!

*+31 thanks to Bubbler for catching a bug not revealed by the original cases*

**NOTE: All test cases are passing again when I run locally on j902, but this now fails on TIO due to a J regex bug on linux/TIO.**

Consider the column and row sums of:

```
11111 = 5
11111 = 5
00011 = 2 (count of 2s is 1)
-----
22233
(count of 2s is 3)

```

as well as the count of the smallest number in each: 2 in this case.

The insight is:

```
2 + (column count of 2s) = 5
2 + (row    count of 2s) = 3

```

and this fact is basically all you need to solve it. The rest is mechanics and likely the J could be golfed a bit more. I'll try to do that and improve this explanation tomorrow.

# Answer
> 6 votes
# JavaScript (V8), 500 bytes

Lots of golfing possible.

```
M=>{R=M.map(m=>m.join``);if(R.find(r=>r.match(/10+1/)))return;o = [];for(i=n=0;i<R[L="length"];i++)if((r=R[i]).includes`1`){if(n)return;n=0;o.push([r.indexOf`1`,r.lastIndexOf`1`])}else{if(o[L])n=1;else continue}if(o.every(r=>r[0]==o[0][0])){}else if(o.every(r=>r[1]==o[0][1]))o=o.map(r=>[R[0][L]-r[1],R[1][L]-r[0]]);else return;d=[];for(i=0;i<o[L];i++){if(o[i][1]!=(d[0]||0)[0])d.unshift([o[i][1],1]);else d[0][1]++}return d[L]== 2&&(d[0][1]==o[0][1]-o[0][0]+1||d[1][1]==o[o[L]-1][1]-o[o[L]-1][0]+1)}

```

Try it online!

Outputs truthy/falsy. Inputs as a multidimensional array of `0` and `1`.

**Explanation:**

1. Join into rows, and do a regex to check for lines that have two vertical parts (`10+1`, which can't be `L` shapes)
2. Create a list of the first and last index of each `1` for every line containing a `1`, and return a falsy value immediately if there's a line with no `1`s between two that have ones (which can't be `L` shapes)
3. If the "stem" of the `L` is on the right, flip it horizontally
4. Make a list of each group of lines where the width of the `1`s is the same, and note its height
5. Check if there are two of these sections (i.e., ensure it's not a rectangle or an `E`/`F`/jagged thingy)
6. Check if the width of the stroke is the same horizontally and vertically

**Ungolfed:**

f = (matrix) => {
    var rows = matrix.map(m => m.join(""));

    if (rows.find(r => r.match(/10+1/)))
        return false;

    var o = [];
    var n;

    for (var r, i = 0; i < rows.length; i++) {
        r = rows[i];

        if (r.includes("1")) {
            if (n)
                return false;

            n = false;

            o.push([r.indexOf("1"), r.lastIndexOf("1")]);
        } else {
            if (o.length)
                n = true;
            else
                continue;
        }
    }

    if (o.every(r => r[0] == o[0][0])) {
    } else if (o.every(r => r[1] == o[0][1])) {
        o = o.map(r => [rows[0].length - r[1], rows[1].length - r[0]]);
    } else {
        return false;
    }

    var d = [];

    for (i = 0; i < o.length; i++) {
        if (o[i][1] != (d[0]||0)[0])
            d.unshift([o[i][1], 1]);
        else
            d[0][1]++;
    }

    return d.length == 2 && (d[0][1] == o[0][1] - o[0][0] + 1 || d[1][1] == o[o.length - 1][1] - o[o.length - 1][0] + 1);
}
```
</code></pre>

# Answer
> 6 votes
# APL (Dyalog Extended), 48 bytes (SBCS)

Anonymous tacit prefix function. Takes Boolean (0/1) matrix with 0s indicating the shape. Requires 0-based indexing.

```
{(=/⍵-⍥⍴e)∧i≡,e←(⊂∘⊃+∘⍳∘|1+⊃∘⌽-⊃)i←⍸⍵}1⍉⍤⌂deb⍣2⊢

```

Try it online!

`0` with 0 as left argument and the unmodified argument as right argument:

…`⍣2` repeat twice

…`⍤⌂deb`**d**elete **e**nding (leading and trailing) **b**lanks (1s), then:

transpose (so we end up deleting the top and bottom blank rows too)

`{``}` apply the following lambda, with  representing its argument:

`⍸⍵`**i**ndices where there are 1s

`i←` save as `i`

`(``)` apply the following tacit function to that:

the \[index of the\] first \[blank\]

…`-` subtract that from:

`⊃∘` the \[index of the\] first of the:

reversed \[indices of blanks, i.e. the index of the last blank\]

`1+` increment that \[to get inclusive range\]

`∘|` take the absolute value of that \[getting the absolute range\], then:

`∘⍳` get the indices of that range, then:

…`+` add that to:

`⊂∘` the whole of…

\[index of the\] first \[blank, giving a matrix of indices of the entire supposed blank area\]

`e←` save as `e`

`,` ravel into a list of indices

`i≡` identical to the actual list of indices of blanks?

`(``)∧` and…

`e` considering the argument and the matrix of supposed blanks…

`-⍥` are the differences in…

shapes \[between heights and widths\]

`=/` equal? \[i.e. does the height-difference match the width-difference?\]

# Answer
> 6 votes
# JavaScript (ES6),  ~~175~~  166 bytes

Expects a list of binary strings.

```
m=>m.map(M=r=>(M|=v='0b'+r|0,m&=v||~0,v),m=~0).map(v=>v?(b=v+(v&-v))&b-1?3:v^m?2^v<M:1:0).join``.match(`^0*(1+${s=(g=m=>m?2+g(m&m-1):'')(m)}|${s}1+)0*$`)&&M*2&M/2&m^m

```

Try it online!

## How?

### Step 1

We first convert the input matrix \\$m\[\\:\]\\$ into a list of integers. At the same time, we compute the bit mask \\$M\\$ of all rows OR'd together and the bit mask \\$m\\$ of all non-empty rows AND'd together.

```
m.map(M =                  // start with M zero'ish
  r =>                     // for each row r in m[]:
  ( M |= v = '0b' + r | 0, //   turn r into an integer v by parsing it as binary
                           //   and update M by doing M = M OR v
    m &= v || ~0,          //   if v is not equal to 0, update m by doing m = m AND v
    v                      //   yield v as the actual value for the map()
  ),                       //
  m = ~0                   //   start with all bits set in m
)                          // end of map()

```

If the shape is valid:

* \\$m\\$ is the pattern for the vertical leg
* \\$M\\$ is the pattern for the horizontal leg
* the list returned by `map()` contains only \\$m\\$, \\$M\\$ and optional \\$0\\$'s

**Example:**

```
 input     | bin -> dec |  M |  m
-----------+------------+----+-----
 "0000000" |      0     |  0 | ~0
 "0100000" |     32     | 32 | 32
 "0100000" |     32     | 32 | 32
 "0111110" |     62     | 62 | 32
 "0000000" |      0     | 62 | 32

```

### Step 2

We convert the list into a string of digits, using \\$0\\$ for empty rows, \\$1\\$ for rows equal to \\$m\\$, \\$2\\$ for rows equal to \\$M\\$, or \\$3\\$ for invalid rows.

```
.map(v =>                  // for each value v in the list:
  v ?                      //   if v is not equal to 0:
    (b = v + (v & -v))     //     if adding to v the least significant bit set in v
    & b - 1 ?              //     results in more than one bit set:
      3                    //       this is an invalid row where at least one 0
                           //       breaks a pattern of consecutive 1's
    :                      //     else:
      v ^ m ?              //       if v is not equal to m:
        2 ^                //         yield 2 if v = M
        v < M              //         or yield 3 if v != M (invalid)
      :                    //       else (v = m):
        1                  //         yield 1
  :                        //   else (empty row):
    0                      //     yield 0
)                          // end of map()
.join``                    // join all digits

```

### Step 3

We build a regular expression to test whether the string is valid.

```
.match(                    // test the resulting string:
  "^0*(" +                 //   optional leading 0's
                           //   followed by either:
  "1+" +                   //     one or several 1's
  ( s =                    //     followed by as many 2's as the number of bits set
    ( g = m =>             //     in m
        m ?                //
          2 + g(m & m - 1) //     this string of 2's is computed with the recursive
        :                  //     function g and saved in s
          ''               //
    )(m)                   //
  ) +                      //
  "|" +                    //   or:
  s + "1+" +               //     as many 2's as the number of bits set
                           //     in m, followed by one or several 1's
  ")0*$"                   //   followed by optional trailing 0's
)                          // end of match()

```

### Step 4

Finally, we make sure that \\$m\\$ and \\$M\\$ form a right angle.

Either \\$m\text{ AND }(M\times 2)\\$ or \\$m\text{ AND }\lfloor M/2\rfloor\\$ must be different from \\$m\\$:

```
M * 2 & M / 2 & m ^ m

```

# Answer
> 4 votes
# Julia, ~~175~~ 170 bytes

```
a->try
r=rotr90
for _=1:4
while sum(a[1,:])<1
a=a[2:end,:]end
a=r(a)end
for _=1:4
a=r(a,a[end])end
a[a[1]]
while sum(a)>0
a[a[a[:,1],:]]
a=a[2:end,2:end]end
a[1]catch
end

```

Try it online!

returns `0` if L-shaped and `nothing` otherwise

It's probably not the most efficient approch but I'm glad I could match the javascript answer

**Ungolfed version**

```
function f(a)
    try
        # remove margins
        for _=1:4
            while sum(a[1,:])<1
                a=a[2:end,:]
            end
            a=rotr90(a)
        end

        # rotate `a[end]` times, meaning until a[end]==0
        for _=1:4
            a=rotr90(a,a[end])
        end
        a[a[1]] # check that a[1]!=0, by erroring if a[1]==0

        while sum(a)>0
            a[a[1,:]] # check that first line and col are all ones
            a[a[:,1]]
            a=a[2:end,2:end] # remove first line an col
        end
        a[1] # check that a is not empty (errors if empty)
    catch
        nothing
    end
end

```

Try it online!

# Answer
> 4 votes
# APL (Dyalog Unicode), 44 bytes

thanks @Adám for the `⍸⍣¯1` trick

```
(⊂a)∊(⍉¨⊢,⌽¨)⍣2≥∘i¨⍳⌈/,i←⌊/↑⍳⍴a←⍸⍣¯1(⊢-⌊/)⍸⎕

```

Try it online!

`⍸⍣¯1(⊢-⌊/)⍸` trim surrounding 0s

`≥∘i¨⍳⌈/,i←⌊/↑⍳⍴a` generate L-shapes

`(⍉¨⊢,⌽¨)⍣2` add reflections

`(⊂a)∊` test if the (trimmed) input is among them

# Answer
> 3 votes
# APL (Dyalog Unicode), 104 bytes

```
{i←0⋄{(~×/1=,⍵)∧(⍴⍵)≡+/¨1⌷¨(⍉⍵)⍵}⌽∘⍉⍣{(~⊃⌽⊖⍺)∨i=4⊣i+←1}{×≢⍵:⍵⋄,0}p∧⌿⍵∧/⍨p←⌊/0~⍨+/⍵}{(¯1+⌊⌿c)↓⍵↑⍨⌈⌿c←↑⍸⍵}

```

Try it online!

A train of two dfns which takes a matrix of 0's and 1's as argument.

Can be simplified a lot using Jonah's idea.

It simplifies the matrix like so:

```
#####
##### →  ####
   ##       #

```

rotates it to put the corner at the top left:

```
##
#
#
#

```

and then checks if the first row and first column match its shape.

# Answer
> 3 votes
# Retina, 112 bytes

```
^\s+¶|¶\s+$

/^( .*¶)+ .*$/+m`^

/^(.* ¶)+.* $/+m` $

/^#* /&G^`
/(?m)^ /&V`
/^##+(¶#.*)+/+`^#+¶#|(¶)#
$1
^\s+$

```

Try it online! Link includes test suite with header that extracts the `#`-based test cases from the input and automatically right-pads them. Explanation:

```
^\s+¶|¶\s+$

/^( .*¶)+ .*$/+m`^

/^(.* ¶)+.* $/+m` $

```

Remove any margins. Annoyingly, this costs almost 50% of the code size.

```
/^#* /&G^`

```

If the first line contains a space then reverse the rows.

```
/(?m)^ /&V`

```

If the first column contains a space then reverse each line.

```
/^##+(¶#.*)+/+`

```

Repeat while the there are at least two rows and columns of which the first of each only contains `#`s...

```
^#+¶#|(¶)#
$1

```

... completely delete the first row and column.

```
^\s+$

```

Check that the entire `L` was deleted.

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~107~~ ~~105~~ ~~101~~ 100 bytes

```
FreeQ[#|r/@#,#|r@#&@{z={y=0...}...,d:{a:y,o=1..,b:o,y}..,{a:y,b:o,y}..,z}/;+b==Length@!d]&
r=Reverse

```

Try it online!

The pattern identifies a vertically reflected L shape. Reversing it checks for another vertical reflection (upright); `#|r/@#` checks for horizontal reflection.

```
{                               (* L pattern: *)
 z={y=0...}...,                 (*  zero or more leading zero-lines, followed by *)
 d:{a:y,o=1..,b:o,y}..,         (*  a column of 1s, wider than *)
 {a:y,b:o,y}..,                 (*  another column of 1s, left-aligned with the first column, *)
 z                              (*  and zero or more trailing zero-lines, *)
}/;+b==Length@!d                (* such that the width of the second column is equal to the height of the first. *)

```

# Answer
> 2 votes
# Python 3.9 \+ NumPy, 167 bytes

```
lambda a:min(c:=(a:=a[[slice(min(i),max(i)+1)for i in a.nonzero()]]).sum(0))-min(r:=a.sum(1))|len(c)-max(r)|sum((a[:-1]^a[1:]).any(1))*sum((a[:,:-1]^a[:,1:]).any(0))-1

```

Expected input is a 2D numpy array of 0/1 (or False/True) values.

Returns falsey for L shape, truthy for not L shape.

Explanation:

First remove the "margin" / 0 column and row vectors around the input if there is any.

Then for both axes:

* Check that the row/column vector only changes once when going along that axis (this ensures that there are only 2 unique ones (one for the leg parallel, and one for the leg perpendicular), and these are all next to each other)
* Take the sum along the axis. There should only be 2 unique values. The smaller one is the width of the leg perpendicular to the axis. Check that the two widths are the same

Then check that the width of both legs is the same

And then check that the length of one of the legs is the entire length of the array

Ungolfed + test runner (since TIO doesn't have numpy):

```
def is_L_shape(a):
    # Remove zero vectors surrounding a
    a = a[tuple(slice(min(i), max(i)+1) for i in a.nonzero())]

    # Check columns have L-like sums
    col_sums = a.sum(0)
    col_width = min(col_sums)
    cols_in_order = sum(~(a[:,:-1]==a[:,1:]).all(0)) == 1  # Only one column should be different from the next

    # Check rows have L-like sums
    row_sums = a.sum(1)
    row_width = min(row_sums)
    rows_in_order = sum(~(a[:-1]==a[1:]).all(1)) == 1  # Only one row should be different from the next

    # Check that the legs span the entire column/row
    col_correct_length = col_sums.max() == len(row_sums)
    # row_correct_length = row_sums.max() == len(col_sums)

    return col_width == row_width and col_correct_length and cols_in_order and rows_in_order

# Test runner
f = \
lambda a:...

def run_test(s):
    import numpy as np
    s = s.strip('\n')
    if s.endswith('!'): s = s[:-1]
    a = np.row_stack([np.array(list(map(ord, line))) for line in s.split('!\n')]) == ord('#')
    is_L = not f(a)
    print(np.array(a, dtype=int), 'is an L' if is_L else 'is not an L', 'as expected' if bool(is_L) == bool(expected) else '(failure)' + '!\n'*20, end='\n\n')

expected = True

run_test('''
#    !
#    !
#####!
''')

run_test('''
#####!
#####!
   ##!
''')

run_test('''
  #### !
  #### !
  ##   !
''')

run_test('''
###!
  #!
   !
''')

run_test('''
      !
      !
  #   !
  ##  !
      !
      !
''')

run_test('''
   ## !
##### !
##### !
      !
      !
''')

expected = False

run_test('''
####!
''')

run_test('''
##  !
####!
''')

run_test('''
#####!
#### !
##   !
##   !
''')

run_test('''
#####!
#####!
  ## !
''')

run_test('''
  #    !
#######!
  #    !
  #    !
''')

run_test('''
## !
 ##!
''')

run_test('''
#####!
# ###!
#####!
# #  !
###  !
''')

run_test('''
##  #!
#  ##!
''')

run_test('''
    !
 ## !
 ## !
    !
''')

run_test('''
# #!
   !
#  !
''')

run_test('''
       !
  #    !
 ####  !
''')

run_test('''
###!
# #!
## !
''')

run_test('''
###!
   !
###!
## !
## !
''')

run_test('''
### !
### !
### !
   #!
   #!
''')

run_test('''
## !
## !
  #!
''')

run_test('''
## !
## !
  #!
  #!
''')

run_test('''
#########!
#########!
''')
run_test('''
#!
''')
run_test('''
###!
''')

```

# Answer
> 2 votes
# Perl 5 (cperl), 338 bytes

```
sub L{($w,$h,$v,$m)=@_;join$/,map{$x=$_;join'',map$_<=$w|($m?$x>$h-$w:$x<=$w)|0,1..$v}1..$h}
sub r{my($i,@r);map/\n/?($i=0):$r[$i++]=~s/^/$_/,pop()=~/./gs;join$/,@r}
sub d{my$_=pop;/.*/;length$&,0+split$/}
sub f{$s=pop;map$s=r($s)=~s,^(0+\n)+,,r,1..4;@m=map{$m=$_;map$m=r($m),1..4}map{L(@L=($_,d($s))),L(@L,1)}1..min(d($s))-1;grep/$s/,@m}

```

Try it online!

Creates all possible L's with all possible rotations and mirrors up to the dimensions of the input (with all 0-margins shaved off). Sees if any of those L's is equal to the shaved input.

# Answer
> 2 votes
# Charcoal, 69 bytes

```
ＦＬθＦＬ§θ⁰Ｆ⌊⟦ικ⟧Ｆ⁻ιλＦ⁻κλＦ²Ｆ²⁼θＥθＥρ¬∨∨∨‹ςμ›ςι∨‹τν›τκ‹λ⌊⟦⎇π⁻ςμ⁻ις⎇ξ⁻τν⁻κτ

```

Try it online! Link is to verbose version of code. Works by enumerating all possible `L` shapes on the original grid looking for a match. So many nested loops, I've actually used the `t` variable for the first time ever. This is an important milestone, since there are no trivial loop variables left. Outputs a Charcoal boolean, i.e. `-` if the shape was an `L`, nothing if not. Explanation:

```
ＦＬθＦＬ§θ⁰

```

Loop over all potential bottom right corners of the rectangle enclosing the `L` shape. (Zero values will be trivially excluded as there won't be room for a pivot.)

```
Ｆ⌊⟦ικ⟧

```

Loop over all potential pivot sizes. (Obviously there must be room for the pivot in both dimensions as it is square.)

```
Ｆ⁻ιλＦ⁻κλ

```

Loop over all potential top left corners of the enclosing rectangle.

```
Ｆ²Ｆ²

```

Loop over all orientations of the `L` within the rectangle.

```
⁼θＥθＥρ¬∨∨∨‹ςμ›ςι∨‹τν›τκ‹λ⌊⟦⎇π⁻ςμ⁻ις⎇ξ⁻τν⁻κτ

```

Recreate the `L` based on the specification, eliminating all points `(v, t)` outside the rectangle `(m, n) - (i, k)` (inclusive) but also all points which are more than `l` away from at least one of the appropriate adjacent edges for the given orientation, and see if that equals the original input.

Here is an example of an enumerated `L` shape. In this figure, `i` is `5`, `k` is `11`, `l` is `3`, `m` is `2`, `n` is `5`, and `p` is `1` (for top) and `x` is `0` (for right) for the position of the pivot.

```
+-----n-----k
|
|
m     ----+++
|     ----+++
|     ----+++
i         |||

```

# Answer
> 1 votes
# Scala, ~~249~~ ~~185~~ 180 bytes

```
Seq.iterate(_,8)(_.transpose.map(_.reverse)dropWhile(!_.toSet(1)))drop 4 exists{m=>Set(m,m.transpose).flatMap(_.dropWhile(!_.toSet(0)).map(_.reverse.dropWhile(_<1)).toSet).size==1}

```

Try it online!

This is shamefully long. It takes a `List[List[Int]]` as input (even though the type is `Seq[Seq[Int]] => Boolean`). The result is a `Boolean`.

## Explanation

Then we make a `Seq` of length 8 by repeatedly rotating the matrix clockwise (`t(_)map(_.reverse)`) and then dropping empty rows at the beginning (`dropWhile(!_.toSet(1))`).

```
Seq.iterate(_, 8)(t(_)map(_.reverse)dropWhile(!_.toSet(1)))

```

Just applying it 4 times would be enough to trim on all sides, but we also want all orientations. We first `drop 4` so only trimmed matrices remain. Then we use `exists` to check if any of them meet a certain condition. However, this function won't work for all orientations, it'll only work for upside-down L's (that's why all 4 orientations were generated):

```
#####
#####
##

```

First, we make a `Set` out of `m` and its transpose, and for both of them, we drop the rows at the start that only contain `#`'s. For the rest of the rows in both, we reverse them and strip leading zeroes, then deduplicate them using `toSet`. The results for both `m` and its transpose are combined because we used `flatMap`, and then we make sure there is exactly one element. Thus, we eliminate legless shapes (less than one element) and shapes with extraneous `#`'s (more than one element).

---
Tags: code-golf, decision-problem, binary-matrix, polyomino
---


title: Simple predictive keyboard CG

text:
# Question
Title: Simple predictive keyboard CG
*In honor of recent news of Google developing a keyboard for iPhone...*

Your input (for simplicity, all input is case sensitive):

1. Location of standard dictionary file. File format is 1 valid word per line; in alphabetical order. Example file:

```
apple
banana
citrus
domino
durian
orange
tuna
zabc

```
2. Location of personal dictionary file (initially, may be empty or non-existant). Format is 1 word per line, comma separated by count of times that word was used. Example file:

```
Stackoverflow,15
StackExchange,11
Meta,13
TFGITW,2
VTC,10

```
3. A stream of words on standard input (for simplicity, newline separated), in the following format on each line: "Typed\_word,intended\_word".

You need to emulate a predictive keyboard, as follows. For every line in the stream of words:

1. Process the typed word character by character
2. After 3rd character, generate the 5 most-used words that start with the currently-seen substring

"5" is a hard-coded constant, but my example below uses "2" for simplicity. "most-used" are picked as first words when words are sorted in the order of counting; alphabetic order within same counts.

The rules for most-used words are: the word from the standard dictionary is assumed to have the used count of 20 (that's a hard-coded constant, but my example below uses "2" for simplicity). The word from personal dictionary has a used count of whatever number the dictionary file has.
3. If one of 5 words matches intended word, print the success: "MATCH:$substring,$intended\_word" and stop
4. If typed word is finished and matches intended\_word, print it: "FULLWORD:$typed\_word,$intended\_word" and stop
5. If typed word is finished, but none of teh matches or the word match intended\_word, print ERROR message including both typed and intended word: "MISMATCH:$typed\_word,$intended\_word"
6. Add the intended word to the personal dictionary if missing from it; or increment its usage count in personal dictionary if already present

Answers should be genuine working code - no gotchas/loopholes, no edge cases like super-small input.

# SAMPLE RUN

(I'm going to change the constants to 2 guesses (instead of 5) and main dictionary words weigh as 2 user-usages instead of 20)

## Standard Dictionary:

```
abacus
abacii
abandon
abandoned
abandonment

```

## User dictionary

EMPTY

## INPUT

```
abanana,abanana
abanana,abanana
abanana,abanana
abandonmint,abandonment
cat,cad

```

## OUTPUT

```
FULLWORD:abanana,abanana #after this, add "abanana,1" to custom dictionary
MATCH:abana,abanana
   # NOTE: your code should have matched "abandon,abandoned" till seeing "abana"
   # change custom dict count for abanana to 2
MATCH:aban,abanana #By now, aban matches "abanana,abandon"
MATCH:abandonm,abandonment
MISMATCH:cat,cad # Add cad to custom dictionary

```

---

**NOTE**: someone asked to be able to live with no files. I'm fine with that, the simplest spec seems to be to pass all 3 inputs on STDIN, separated by empty line between the inputs.

# Answer
> 1 votes
# Python 3.9, 350 bytes

```
import sys
[s,p,x]=sys.stdin.read().split("\n\n")
p,x=[[l.split(',')for l in d.split("\n")]for d in[p,x]]
s={k:20 for k in s.split("\n")}
p={k:int(v)for k,v in p}
for t,i in x:b=s|p;b={k:b[k]for k in b if k[:4]==t[:4]};b=sorted(b,key=b.get);p[i]=p.get(i,0)+1;print((f"MATCH:{t[:4]},"if i in b[:5]else f"FULLWORD:{t},"if t==i else f"MISMATCH:{t},")+i)

```

Try it online! (Uses `{**a,**b}` instead of `a|b` to merge dictionaries)

The I/O formats are restrictive, but this still makes for a simple and fun challenge.

```
import sys
#s is the standard dictionary, p is the personal dictionary, and x is the input
#They are separated by a blank line
[s,p,x]=sys.stdin.read().split("\n\n")
#Turn both p and x into lists (separated by \n) of 2-element lists (separated by commas)
p,x=[[l.split(',')for l in d.split("\n")]for d in[p,x]]
#Split s on \n to get list of words, then map to 20, the default no. of occurrences
s={k:20 for k in s.split("\n")}
#Turn p into a dictionary, and make the values ints
p={k:int(v)for k,v in p}
#Iterate over each typed word t and intended word i in the input
for t,i in x:
  #Merge the personal and standard dictionaries and store in b
  b=s|p
  #Filter the words who start with the first 4 characters of t (typed word)
  b={k:b[k]for k in b if k[:4]==t[:4]}
  #b now contains words from the dictionary, sorted by number of occurrences
  b=sorted(b,key=b.get)
  #Increment number of occurrences of i in personal dictionary, or set to 1 if it doesn't exist yet
  p[i]=p.get(i,0)+1
  #Print the corresponding message
  print((f"MATCH:{t[:4]},"if i in b[:5]else f"FULLWORD:{t},"if t==i else f"MISMATCH:{t},")+i)

```

---
Tags: code-golf
---


title: Simplificate an array

text:
# Question
Title: Simplificate an array
## Input

An array that can contain arrays or positive, consecutive, ascending integers. The arrays can have any number of arrays inside of them, and so on and so forth. No arrays will be empty.

## Output

This array simplificated

## How to simplificate an array

We will use the array, `[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]` as our example.

First, we check how deep the values are nested. Here are the depths and the numbers at those depths:

```
0  1
1  2 3 9
2  4 7
3  5 6
5  8

```

We construct the output array by taking the numbers in the original array, grouping them by how deep they are nested, and then nesting the groups at depths of the original depths of their elements. Arrange the numbers in ascending order and ascending depth.

So, our output is `[1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]`

## Examples

```
[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]] -> [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]
[[[1]], [2, [3]], 4, [5, [6, [7, [8], [9, [[10]]]]]]] -> [4, [2, 5], [[1, 3, 6]], [[[7]]], [[[[8, 9]]]], [[[[[[10]]]]]]]
[1] -> [1]
[1, [2], [[3]], [[[4]]], [[[[5]]]]] -> [1, [2], [[3]], [[[4]]], [[[[5]]]]]
[1, [[[[2], 3]]], [[4]]] -> [1, [[4]], [[[3]]], [[[[2]]]]]

```

# Answer
# Jelly, 8 bytes

```
fFṄḟ@;/ß

```

Output is one level per line, with empty lines for levels without elements. Try it online!

### How it works

```
fFṄḟ@;/ß  Main link. Argument: A (array)

 F        Flat; yield all integers (at any level) in A.
f         Filter; intersect A with the integers, yielding those at level 0.
  Ṅ       Print the filtered array and a linefeed. Yields the filtered array.
     ;/   Reduce by concatenation.
          This decreases the levels of all integers at positive levels by 1.
   ḟ@     Swapped filter-false; remove the integers at level 0 in A from the array
          with decreased levels.
       ß  Recursively call the main link on the result.
          The program stops once A is empty, since ;/ will result in an error.

```
> 2 votes

# Answer
## Perl, 52 bytes

Just a recursive subroutine. (unusual for a Perl answer, I know..)

```
sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}

```

Call it like that :

```
$ perl -E 'sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}f(1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9])'
1
2 3 9
4 7
5 6

8

```

Each line of the output corresponds to a depth level of the array (hence the empty line in the example above).

It can be turned into a full program for just a few more bytes : add `-n` flag and an `eval` (inside `@{ }` to transform the input into an array and not an arrayref) to transform the input into a Perl array :

```
perl -nE 'sub f{say"@{[grep!ref,@_]}";@_&&f(map/A/?@$_:(),@_)}f(@{+eval})' <<< "[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]"

```

---

My previous approach was slightly longer (65 bytes), but still interesting, so I'll let it here :

```
perl -nE '/\d/?push@{$;[$d-1]},$_:/]/?$d--:$d++for/\[|]|\d+/g;say"@$_"for@' <<< "[1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]"

```
> 3 votes

# Answer
## JavaScript (ES6), ~~139~~ 109 bytes

```
f=(a,v=b=>a.filter(a=>b^!a[0]))=>a[0]?v().concat((a=f([].concat(...v(1))),b=v())[0]?[b]:[],v(1).map(a=>[a])):[]

```

Explanation using the example input: `v` is a helper method which returns the arrays (with parameter `1`) or values (with no parameter). We start with `a = [1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]`, which is nonempty. We filter out the arrays, giving `[1]`. We then recursively call ourselves on the arrays concatenated together, which is `[2, 3, [4], [[5, 6], 7, [[[8]]]], 9]`, the result being `[2, 3, 9, [4, 7], [[5, 6]], [[[[8]]]]]`. We again filter out the arrays, which gives us the second term of our output, `[2, 3, 9]`, however we have to be careful not to insert an empty array here. It them remains to wrap the arrays `[4, 7], [[5, 6]], [[[[8]]]]` inside arrays and append them to the output, resulting in `[1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]`.
> 3 votes

# Answer
# JavaScript (ES6) 121 ~~144 152~~

**Edit** Revised a lot, 1 byte saved thx Patrick Roberts, and 21 more just reviewing the code

Recursive function working on arrays in input and output. I don't like the request of having elements at depth 1 as single elements in output array (while greater levels are grouped as one element): `[l1,l1, [l2...], [[l3...]] ]`. While this would be more direct: `[ [l1...], [[l2...]], [[[l3...]]] ]`

```
f=(l,d=0,r=[])=>l.map(v=>v[0]?f(v,d+1,r):r[d]=[...r[d]||[],v])
r.reduce((r,v,d)=>d?[...r,(n=d=>d-->1?[n(d)]:v)(d)]:v,[])

```

Newline added for readability.

Some notes: the line 2 is evaluated again and again at each recursive call, but only the last iteration at the end of recursion is useful.
The special handling when `d==0` in line 2 takes care of the anomaly for level 1 elements.
The `n` recursive function handles the array nesting in output

**Test**

```
f=(l,d=0,r=[])=>l.map(v=>v[0]?f(v,d+1,r):r[d]=[...r[d]||[],v])
&&r.reduce((r,v,d)=>d?[...r,(n=d=>d-->1?[n(d)]:v)(d)]:v,[])

console.log=x=>O.textContent+=x+'\n'

test=[
 [
   [1, [2,3], 4], /* -> */ [1, 4, [2,3]]
 ]
,[
   [1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]],
   // ->
   [1, [2, 3, 9], [[4, 7]], [[[5, 6]]], [[[[[8]]]]]]
 ]
,[
  [[[1]], [2, [3]], 4, [5, [6, [7, [8], [9, [[10]]]]]]],
  // ->
  [4, [2, 5], [[1, 3, 6]], [[[7]]], [[[[8, 9]]]], [[[[[[10]]]]]]]
 ]
,[
  [1], /* -> */ [1]
 ]
,[
  [1, [2], [[3]], [[[4]]], [[[[5]]]]],
  // ->
  [1, [2], [[3]], [[[4]]], [[[[5]]]]]
 ]
,[
  [1, [[[[2], 3]]], [[4]]],
  [1, [[4]], [[[3]]], [[[[2]]]]]
]]

test.forEach(t=>{
  var i=t[0], k=t[1], r=f(i),
      si=JSON.stringify(i),
      sr=JSON.stringify(r),
      sk=JSON.stringify(k)

  console.log((sr==sk?'OK ':'KO ')+si + " => " + sr)
})
```

```
<pre id=O></pre>
```
> 2 votes

# Answer
# 05AB1E, ~~27~~ ~~26~~ ~~25~~ 21 bytes

```
D˜gFvyydi„ÿ ?}}¶?.gG«

```

Try it online! (slightly modified as `.g` isn't on TIO yet)

**Explanation**

```
D˜gF                    # flattened input length times do
    vy                  # for each y current level of list
      ydi„ÿ ?}          # if y is a digit, print with space
              }         # end v-loop
               ¶?       # print newline
                 .g     # calculate length of stack (this should be .g but I can't test)
                   G«   # length stack times, concatenate items on stack

```

The main strategy is to loop over each possible level of the nested array and print any digits on one row, while keeping the non-digits (lists) in a list one level less nested.
> 2 votes

# Answer
# JavaScript (ES6) 168 bytes

```
f=a=>(s=[],b=-1,k=0,a.replace(/\d+|\[|\]/g,a=>a=='['?b++:a==']'?b--:(s[b]=s[b]||[]).push(a)),'['+s.map((a,b)=>k=a&&(k?',':'')+'['.repeat(b)+a+']'.repeat(b)).join``+']')

```

# Demo
> 1 votes

# Answer
# PHP, 145 Bytes

```
<?function c($r){$n=[];foreach($r as$k=>$v)if(is_array($v)){$n=array_merge($n,$v);unset($r[$k]);}if($n)$r[]=c($n);return$r;}print_r(c($_GET[a]));

```

Breakdown

```
function c($r){
  #usort($r,function($x,$y){return is_array($x)<=>is_array($y)?:$x<=>$y;});
#no need to sort and a simple sort($r); do it sort array after scalar
  $n=[];
  foreach($r as$k=>$v)if(is_array($v)){$n=array_merge($n,$v);unset($r[$k]);} # put arrays on the same depth together
  if($n)$r[]=c($n); # recursive if an array exists
  return$r; #return changes
}
print_r(c($_GET[a])); #Output and Input

```
> 1 votes

# Answer
## Haskell, ~~124~~ 123 bytes

```
data L=I Int|R[L]
d#R l=((d+1)#)=<<l
d#i=[(d::Int,i)]
[]!_=[]
l!1=l
l!d=[R$l!(d-1)]
h l=R$do d<-[1..];[i|(e,i)<-0#l,d==e]!d

```

As Haskell doesn't support mixed lists (integers and list of integers) by default, I define a custom list type `L`. Usage example:

```
*Main> h (R[I 1, R[I 2, I 3], R[ R[I 4]], R[ R[ R[I 5, I 6], I 7, R[R[R[I 8]]]], I 9]])
R [I 1,R [I 2,I 3,I 9],R [R [I 4,I 7]],R [R [R [I 5,I 6]]],R [R [R [R [R [I 8]]]]]]

```

Note: it takes some time to run, because it loops through all positive Ints (32 or 64bit) to look for a nest level that deep. Also: the custom list type cannot be printed by default, so if you want to see the result as in the example above, you need to add `deriving Show` to the `data` declaration (-\> `data L=I Int|R[L] deriving Show`). Because it's not needed for returning a L-list from a function, I don't count the bytes.

How it works:

```
data L=I Int|R[L]               -- custom list type L, which is either an Int
                                -- (-> I Int) or a list of some L (-> R [L])

d#R l=((d+1)#)=<<l              -- # makes a list of (depth, I-number) pairs from
d#i=[(d::Int,i)]                -- a given L-list, e.g.
                                -- 0 # (R[I 1,R[I 2,I 3],I 4]) -> [(1,I 4),(2,I 2),(2,I 3),(1,I 4)]
                                -- the type annotation ::Int makes sure that all
                                -- depths are bounded. Without it, Haskell
                                -- would use arbitrary large numbers of type
                                -- ::Integer and the program won't finish

[]!_=[]                         -- ! wraps a list of Is with (d-1) additional
l!1=l                           --  R constructors
l!d=[R$l!(d-1)]

h l=                            -- main function, takes a L-list
      do d<-[1..]               -- for each nest level d make
        [i|(e,i)<-0#l,d==e]     -- a list of all I where the depth is d
                           !!d  -- and wrap it again with d-1 Rs
     R$                         -- wrap with a final R

```

Edit @BlackCap saved a byte by switching from `>>=` to `do` notation. Thanks!
> 1 votes

# Answer
## JavaScript (ES6), ~~127~~ ~~137~~ 134 bytes

Takes an array as input and returns a string.

```
f=(a,l=[],d=0,o='')=>`[${a.map(x=>x[0]?f(x,l,d+1,o+'['):l[d]=(l[d]?l[d]+',':o)+x),l.map((s,d)=>x+s+']'.repeat(d,x=','),x='').join``}]`

```

### Test cases

```
f=(a,l=[],d=0,o='')=>`[${a.map(x=>x[0]?f(x,l,d+1,o+'['):l[d]=(l[d]?l[d]+',':o)+x),l.map((s,d)=>x+s+']'.repeat(d,x=','),x='').join``}]`

console.log(f([1, [2, 3], [[4]], [[[5, 6], 7, [[[8]]]], 9]]));
console.log(f([[[1]], [2, [3]], 4, [5, [6, [7, [8], [9, [[10]]]]]]]));
console.log(f([1]));
console.log(f([1, [2], [[3]], [[[4]]], [[[[5]]]]]));
console.log(f([1, [[[[2], 3]]], [[4]]]));
```
> 1 votes

# Answer
# Pyth, ~~19~~ 16 bytes

```
W=Qsf!&sITp+TdQk

```

Try it online. Test suite.

Note the leading space. Outputs levels on rows like the Perl answer.

### Explanation

* Implicit input in `Q`.
* `f`ilter items `T` of `Q` on:
    + Check if `s`um is `I`dentity on `T`.
    + If it was (it was a number), `p`rint `T` plus a space `+``d`.
    + If it wasn't (it was an array), keep it.
* `s`um the items. This removes a layer of arrays from each item. If none are left, yields `0`.
* Assign `=` the result to `Q`.
* `W`hile the result is nonempty, print the empty string `k` and a newline.
> 1 votes

# Answer
# APL (Dyalog Unicode), 22 bytes

```
{⍬≢⍵:∇⊃,/⍵~⎕←⍵/⍨0=≡¨⍵}

```

Try it online!

Similar to Dennis' answer, a test case per line.
> 1 votes

# Answer
# Red, 174 bytes

```
func[a][i: charset"0123456789"d: 0 m: copy #()parse mold a[any["["(d: d + 1)|"]"(d: d - 1)|" "|
copy t any i(either m/:d[append m/:d to 1 t][m/:d: to[]t])]]sort/skip to[]m 2]

```

Try it online!

A naive approach using the string representation of the array, keeping track of the depth by counting the `[`and `]`. The integers are stored into a map which keys are the depths.
> 1 votes

# Answer
# , 96 bytes

```
f=function(x,`+`=list,`-`=unlist,i=sapply(x,is.list))c(+sort(-x[!i]),if(length(x[i]))+f(x[i]-F))

```

Try it online!

Outputs a nested list.

**Ungolfed code**

```
simplificate=
f=function(x){                      # recursive function f with argument x;
 islist=sapply(x,is.list)           # first determine which elements of x are lists
 c(                                 # now make a list of two groups of elements:
  list(sort(unlist(x[!islist]))),   # the first is the non-list elements of x,
  if(length(x[islist])){            # then (but only if there were some)
   list(                            # the second is a list of
    f(                              # the results of a recursive call to f
     unlist(x[islist],              # with the list elements of x as an argument,
      recursive=FALSE)))            # after unlisting by one level.
  }
 )
}

```

---

Or, **88 bytes**

```
f=function(x,`-`=unlist,i=sapply(x,is.list))if(length(x)){print(sort(-x[!i]));f(x[i]-F)}

```

Try it online!

Outputs elements from each level on a different line. This meets the flexible output allowed in the comments, but feels a bit sneaky when  is happily able to output a nested list as originally asked for in the challenge...
> 0 votes

# Answer
# Python 3, 104 bytes

```
v=lambda l,m={},i=1:m if l==[]else v(l[1:],v(l[0],m,i+1)if str(l[0])>'A'else{**m,i:m.get(i,[])+l[:1]},i)

```

Try it online!
> 0 votes

---
Tags: code-golf, array
---


title: Non-overlapping Matrix Sum

text:
# Question
Title: Non-overlapping Matrix Sum
Given \\$k\\$ arrays of length \\$n\\$, output the maximum sum possible using one element from each array such that no two elements are from the same index. It is guaranteed that \\$k\le n\\$.

# Input

A nonempty list of nonempty arrays of integers.

# Output

An integer that represents the maximum sum.

# Examples

```
Input -> Output
[[1]] -> 1
[[1, 3], [1, 3]] -> 4
[[1, 4, 2], [5, 6, 1]] -> 9
[[-2, -21],[18, 2]] -> 0
[[1, 2, 3], [4, 5, 6], [7, 8, 9]] -> 15
[[1, 2, 3, 4], [5, 4, 3, 2], [6, 2, 7, 1]] -> 16
[[-2, -1], [-1, -2]] -> -2

```

# Answer
> 9 votes
# Jelly, ~~10~~ 6 bytes

```
ZŒ!ÆṭṀ

```

Try it online!

(4 bytes saved by @Dennis, who pointed out that Jelly had a "sum of main diagonal" builtin. I was *not* expecting it to have one of those; the previous solution implemented the operation without using the builtin. The operation in question, `Æṭ`, is defined as "trace", but the trace is only defined for square matrices; Jelly implements a generalisation to rectangular matrices too.)

The improvement over the other answers is mostly from a simpler (thus terser to express) algorithm; this program was originally written in Brachylog v2 (`{\p\iᶠ∋₎ᵐ+}ᶠot`), but Jelly has some builtins for parts of the program that have to be spelled out in Brachylog, so this came out shorter.

## Explanation

```
ZŒ!ÆṭṀ
Z            Swap rows and columns
 Œ!          Find all permutations of rows (thus columns of the original)
   Æṭ        {For each permutation}, take the sum of the main diagonal
     Ṁ       Take the maximum

```

It should be clear that for any solution to the problem, we can permute the columns of the original matrix to put that solution onto the main diagonal. So this solution simply reverses that, finding all possible main diagonals of permutations.

Note that the "permute the columns" operation is done as "transpose, permute the rows" without bothering to transpose back; the rest of the algorithm happens to be symmetrical about the main diagonal, so we don't need to undo the transpose and thus can save a byte.

# Answer
> 7 votes
# , 28 bytes

```
>./@({.+1$:@|:\.|:@}.)@[^:]#

```

Try it online!

```
 >./ @  (   {.   +         1 $:@|:\. |:@}.       )       @[^:] #
(max of (1st row + recursive call on each "minor")) or count of arg if 0

```

Here the recursive call is done by `$:` which represents the largest anonymous function containing it. We are lucky in J to have the primitive `x u\. y`, which applies `u` to successive "outfixes" of `y` obtained by suppressing successive infixes of length `x` of the items in `y`; here we want to surpress successive columns to get "minors", so we transpose `|:` the lower rows (or tail `}.`) of `y`, and then recurse on the transpose of their outfixes.

# Answer
> 6 votes
# Python 3, ~~94 90 89 84~~ 80 bytes

<sup>-4 bytes thanks to xnor (using sets instead of lists)!</sup>

```
f=lambda x,y={-1}:x>[]and max(e+f(x[1:],y|{i})for(i,e)in enumerate(x[0])if{i}-y)

```

Try it online!

# Answer
> 6 votes
# Husk, ~~12 11~~ 9 bytes

```
▲mȯΣ►L∂PT

```

Try it online!

Thanks to BMO for suggesting a port of ais523's answer and a 2-byte save, which I managed to improve on further, and in turn BMO shaved off 2 more bytes.

---

## Previous solution (14 bytes)

```
▲moΣz!¹fS=uΠmŀ

```

Try it online!

I wasn't able to make a test suite because this answer uses the *first command line argument* command explicitly. But Husk doesn't use STDIN at all so I included all the test cases there, so you can just copy paste in the argument field to check it out. Also note that arrays in Husk may not contain spaces between elements while being inputted.

### How it works?

**Code breakdown**

```
▲moΣz!¹fS=uΠmŀ     Full program. Takes a 2D list from CLA 1 and outputs to STDOUT.
            mŀ     Length range of each list.
           Π       Cartesian product.
       fS=u        Discard those combinations which have at least 1 non-unique element.
 mo                Map over the combinations with the following predicate:
    z!¹            Zip the 2D list input with the current combination and index accordingly.
   Σ               Sum the resulting elements.
▲                  Finally, pick the maximum.

```

**Example**

Let's pick an example: $$\left(\begin{matrix}1&4&2\\5&6&1\end{matrix}\right)$$

One must pick exactly one index from each such that no two indices correspond. So, we generate the length ranges of the rows and only keep those without duplicates, yielding the following combinations (each combination is a column instead of a row to save space):

$$\left(\begin{matrix}\color{red}{1}&\color{blue}{2}&\color{green}{1}&\color{orange}{3}&2&\color{pink}{3}\\\color{red}{2}&\color{blue}{1}&\color{green}{3}&\color{orange}{1}&3&\color{pink}{2}\end{matrix}\right)$$

Then, the program indexes in the input lists with each element of the combination, returning:

$$\left(\begin{matrix} \color{red}{1}&\color{blue}{4}&\color{green}{1}&\color{orange}{2}&4&\color{pink}{2}\\ \color{red}{6}&\color{blue}{5}&\color{green}{1}&\color{orange}{5}&1&\color{pink}{6} \end{matrix}\right)$$

Summing all those results (here, each column, for the aforementioned reason), one obtains all possible valid sums according to the criteria, in this case \\$9\\$.

# Answer
> 5 votes
# Jelly, ~~13~~ 12 bytes

```
ẈŒpQƑƇị"€¹§Ṁ

```

Try it online!

### Alternate version, 11 bytes

```
ZLœ!Lị"€¹§Ṁ

```

This uses the newly added `œ!` built-in, which generates all permutations of a given length.

Try it online!

### How it works

```
ẈŒpQƑƇị"€¹§Ṁ  Main link. Argument: M (matrix)

Ẉ             Widths; compute the length of each row.
              For an n×m matrix, this yields an array m copies of n.
 Œp           Cartesian product; promote each n to [1, ..., n], then form all arrays
              that pick one k out of all m copies of [1, ..., n].
   QƑƇ        Comb by fixed unique; keep only arrays that do not change by
              deduplicating their entries.
         ¹    Identity; yield M.
      ị"€     For each of the arrays of unique elements, use its m entries to index
              into the m rows of M.
          §   Take the sums of all resulting vectors.
           Ṁ  Take the maximum.

```

# Answer
> 4 votes
# JavaScript (ES6),  ~~74~~  71 bytes

*Thanks to @tsh for identifying 2 useless bytes that were used to fix a bug*
*Saved 3 bytes thanks to @tsh*

```
f=([a,...r],k,i=1)=>a?Math.max(...a.map(n=>k&(i+=i)?-1/0:n+f(r,k|i))):0

```

Try it online!

# Answer
> 4 votes
# Haskell, 65 bytes

```
f(u:v)=maximum[e+f(take i<>drop(i+1)<$>v)|(i,e)<-zip[0..]u]
f _=0

```

Try it online!

## Explanation & Ungolfed

The function `take i<>drop(i+1)` takes a list and removes the element at position `i`.

The function `f` gets each possible element `e` at position `i`, removes the elements at position `i` from the remaining elements and adds `e` to the recursively computed optimum:

```
f(u:v)=maximum[e+f(removeElementAt i<$>v)|(i,e)<-zip[0..]u]

```

And the base case for the empty list is just `0`:

```
f _=0

```

# Answer
> 3 votes
# Brachylog, 18 bytes

```
{hl⟦kp;?z₀∋₍ᵐ+}ᶠot

```

Try it online!

### Explanation

```
                ot      The output is the biggest result of…
{             }ᶠ        …finding all outputs to the following predicate:
 hl⟦k                     Construct the range [0, …, n-1]
     p                    Take a permutation of that range
      ;?z₀                Zip that permutation with the Input, stopping when all elements of
                            the input are used (important because the range is possibly
                            bigger than the length of the input)
          ∋₍ᵐ             In each element of the zip, take the head'th element of the tail
             +            Sum the result

```

# Answer
> 2 votes
# K (oK), 40, 32, 28, 19 bytes

-13 bytes thanks to ngn!

```
{|/+/(prm'x)@''!#x}

```

Try it online!

## Initial solution:

```
{|/+/'x./:/:(*t),'/:t:{x~?x}#+!(#x)##*x}

```

Try it online!

Note: Doesn't work for the first test case \[\[1\]\]

## Explanation:

`{ }` \- function with argument `x`

```
                                   #     - creata a list
                               (#x)      - with length number of rows of x
                                    #*x  - of the length of the first row
                              !          - odometer (ranged permutations)
                             +           - transpose
                            #            - filter out the rows
                      {x~?x}             - that have duplicates
                    t:                   - save it to t
                ,'/:                     - pair up each number in each row with
            (*t)                         - a number from the first row
      x./:/:                             - index x with each of the above
   +/'                                   - find the sum of each row
 |/                                      - reduce by max

```

# Answer
> 2 votes
# Haskell, 65 bytes

```
([]%)
p%(h:t)=maximum[x+(i:p)%t|(i,x)<-zip[0..]h,all(/=i)p]
p%_=0

```

Try it online!

---

**71 bytes**

```
f m=maximum[sum b|(a,b)<-unzip<$>mapM(zip[0..])m,[x|x<-a,y<-a,x==y]==a]

```

Try it online!

The `[x|x<-a,y<-a,x==y]==a` checks that the elements of `a` are distinct. This uses up a surprising number of characters, but I didn't see a shorter way.

# Answer
> 2 votes
# , 14 bytes

```
{:@$>./ .+@{.]

```

Try it online!

When I saw xnor's comment

> For square arrays, this is the matrix permanent over the tropical semiring which uses the operations (max, +) in place of (+, \*).

I immediately realized that it must be a job for J's generalized determinant/permanent built-in `f . g`. The permanent is `+/ .*`, so the modified permanent is `>./ .+` (6 bytes). Unfortunately this only works with square arrays (horizontally longer arrays give negative infinity `__` for some reason), so I needed to pad the input with zeros to make it square.

```
{:@$>./ .+@{.]    NB. Tacit function, input: a matrix
{:@$              NB. The horizontal length of the matrix
           {.]    NB. Pad the matrix with zeros at the bottom to make it square
    >./ .+@       NB. Compute the modified permanent over the square matrix

```

# Answer
> 1 votes
# Pyth, ~~15~~ 12 bytes

```
eSms@VQd.plh

```

Try it online here.

```
eSms@VQd.plhQ   Implicit: Q=eval(input())
                Trailing Q inferred
          lhQ   Length of first element of Q
        .p      Generate all permutaions of 0 to the above
  m             Map the elements of the above, as d, using:
    @VQd          Vectorised index into Q using d
                    For i in [0-length(Q)), yield Q[i][d[i]]
   s              Take the sum of the above
 S              Sort the result of the map
e               Take the last element of the above, implicit print

```

*Edit: saved 3 bytes courtesy of issacg*

# Answer
> 1 votes
# 05AB1E, ~~18~~ 13 bytes

```
нgLœε‚øε`è]OZ

```

~~I have the feeling it's overly long, but I'm not sure how to do vectorized indexing byte-efficiently in 05AB1E..~~ And I was indeed right that it was too long.. -5 bytes thanks to *@Emigna*.

Try it online or verify all test cases.

**Explanation:**

```
н                # Take the first inner list (of the implicit input list of lists)
 g               # Pop and take its length
  L              # Create a list in the range [1, inner-length]
   œ             # Create each possible permutation of this range-list
    ε            # Map each permutation to:
     ‚           #  Pair it with the (implicit) input
      ø          #  Transpose; swap rows/columns
       ε         #  Map each to:
        `        #   Push both to the stack
         è       #   Index the permutation-nr into the inner list of the input
    ]            # Close both maps
     O           # Take the sum of each inner list
      à          # Pop and push the maximum (and output implicitly)

```

**Example run:**

* Input: `[[1,4,2],[5,6,1]]`
* After step 1 (`нgL`): `[1,2,3]`
* After step 2 (`œ`): `[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]`
* After step 3 (`ε‚`): `[[[[1,4,2],[5,6,1]],[1,2,3]],[[[1,4,2],[5,6,1]],[1,3,2]],[[[1,4,2],[5,6,1]],[2,1,3]],[[[1,4,2],[5,6,1]],[2,3,1]],[[[1,4,2],[5,6,1]],[3,1,2]],[[[1,4,2],[5,6,1]],[3,2,1]]]`
* After step 4 (`ø`): `[[[[1,4,2],1],[[5,6,1],2]],[[[1,4,2],1],[[5,6,1],3]],[[[1,4,2],2],[[5,6,1],1]],[[[1,4,2],2],[[5,6,1],3]],[[[1,4,2],3],[[5,6,1],1]],[[[1,4,2],3],[[5,6,1],2]]]`
* After step 5 (`ε`è]`): `[[4,1],[4,5],[2,6],[2,5],[1,6],[1,1]]` (NOTE: 05AB1E is 0-indexed (with automatic wraparound), so indexing `3` into `[5,6,1]` results in `5`.)
* After step 6 (`O`): `[5,9,8,7,7,2]`
* Output / after step 7 (`à`): `9`

# Answer
> 1 votes
# Perl 6, ~~50~~ 49 bytes

```
{max map *.map({.[$++]}).sum,permutations [Z] $_}

```

Try it online!

Decently short, even despite the long `permutations` call. This is an anonymous code block that takes a list of lists and returns a number.

### Explanation:

```
{                                               } # Anonymous code block
 max                                              # Finds the maximum
                             permutations         # Of all permutations
                                          [Z] $_  # Of the transposed input
     map                                          # When mapped to
                        .sum # The sum of
         *.map({.[$++]})     # The diagonal of the matrix

```

# Answer
> 1 votes
# 05AB1E, 7 bytes

```
øœ€Å\Oà

```

Port of *@ais523*'s Jelly CW answer, so make sure to upvote it as well!

Try it online or verify all test cases.

**Explanation:**

```
ø          # Transpose the (implicit) input; swapping row/columns
 œ         # Get all permutations
  €Å\      # Take the main diagonal of each
     O     # Sum each
      à    # Pop and push the maximum (which is output implicitly)

```

# Answer
> 1 votes
## Haskell, 84 bytes

```
import Data.List
h l=maximum[sum$snd<$>r|r<-mapM id$zip[1..]<$>l,(==)=<<nub$fst<$>r]

```

Try it online!

# Answer
> 0 votes
# Ruby, ~~74~~ ~~72~~ 69 bytes

```
->a{[*0...a[0].size].permutation.map{|x|a.zip(x).sum{|y,z|y[z]}}.max}

```

Try it online!

---
Tags: code-golf, array
---


title: ASCII Train Golf

text:
# Question
Title: ASCII Train Golf
Consider these seven ASCII train cars.

**Engine (E)**

```
            __
======      \/
| [] |=========
|              )
================
 O-O-O   O-O-O \\

```

**Passenger car (P)**

```
===============
| [] [] [] [] |
===============
 O-O       O-O

```

**Boxcar (B)**

```
===============
|-|-|  |  |-|-|
===============
 O-O       O-O

```

**Tanker (T)**

```
 _____---_____
(             )
===============
 O-O       O-O

```

**Hopper (H)**

```
_______________
\ | | | | | | /
===============
 O-O       O-O

```

**Flatbed (F)**

```
===============
 O-O       O-O

```

**Caboose (C)**

```
    =====
====|   |====
| []     [] |
=============
 O-O     O-O

```

Write a program that when given a sequence of the characters `EPBTHFC`, outputs its ASCII train representation, using `--` for the car couplings. The leftmost input characters become the rightmost train cars. The train is always facing right.

For example, an input of `EEHTBPFC` should produce

```
                                                                                __                __
    =====                                                                                ======      \/    ======      \/
====|   |====                   ===============  ===============   _____---_____   _______________  | [] |=========   | [] |=========
| []     [] |                   | [] [] [] [] |  |-|-|  |  |-|-|  (             )  \ | | | | | | /  |              )  |              )
=============--===============--===============--===============--===============--===============--================--================
 O-O     O-O    O-O       O-O    O-O       O-O    O-O       O-O    O-O       O-O    O-O       O-O    O-O-O   O-O-O \\  O-O-O   O-O-O \\

```

## Details

* This is code golf; the shortest program in bytes wins.
* Any sequence of one or more of the letters `EPBTHFC` is valid input.
* Your program must be able to output all 7 car types exactly as they appear above.
* Take input from the command line or directly from the user (e.g. message box). Output to stdout. (Quotes around input are fine.)
* The height of the output should either be 6 or the maximum height needed for the train cars being drawn.
* Do not put couplings (`--`) at the front of the first car or the back of the last car.

# Answer
# Perl, 265 bytes

Since this entry contains bytes that do not correspond to printable ASCII characters, it cannot be copy-pasted here directly. Instead, I am providing it as a hex dump. Users on Unix-ish systems can reconstruct the script by feeding the following hex dump to the `xxd -r` command:

```
0000000: 7573 6520 436f 6d70 7265 7373 275a 6c69  use Compress'Zli
0000010: 623b 6576 616c 2075 6e63 6f6d 7072 6573  b;eval uncompres
0000020: 7320 2778 daad 9241 6b83 3014 c7ef f914  s 'x...Ak.0.....
0000030: ef10 6add f67c 5ed6 8b06 c646 476f dda1  ..j..|^....FGo..
0000040: 3723 c183 1d85 8212 c740 087e f625 a6a3  7#.......@.~.%..
0000050: b1f6 24fd 3de1 3d7f e8fb e790 b74a 74ed  ..$.=.=......Jt.
0000060: f9f4 c3e9 25cf a328 6310 a094 6b4c 8c78  ....%..(c...kL.x
0000070: 2569 5406 8a12 8cf8 c7ab 09b1 ff71 0222  %iT..........q."
0000080: 833d da02 b874 2981 c10d 3333 df74 39c1  .=...t)...33.t9.
0000090: f531 d6dc 0f03 8f9f 9666 a12d 7021 6e7a  .1.......f.-p!nz
00000a0: 6416 2807 228e dd99 3584 c40f cc52 53ac  d.(."...5....RS.
00000b0: 9160 82a2 4559 0bcd a22c ff2e 1cc1 0e63  .`..EY...,.....c
00000c0: 9d09 6f85 25b8 13b3 8470 3fe3 5c27 a1eb  ..o.%....p?.\'..
00000d0: df5a 7735 b44d 2b86 9eb6 5fef 87dd e707  .Zw5.M+..._.....
00000e0: a5b8 219d b1ae eaed 3743 4709 f1aa d83c  ..!.....7CG....<
00000f0: f1d5 3357 257d 6be7 1039 9186 63a3 214d  ..3W%}k..9..c.!M
0000100: 9257 f607 1251 a1e7 27                   .W...Q..'

```

The script uses the Perl 5.10 `say` feature, and so needs to be run with `perl -M5.010`. It takes a single command line argument consisting of the letters `EPBTHFC` and outputs the corresponding train car arrangement. For example, the input `FEH` produces the following output:

```
                             __
                 ======      \/
_______________  | [] |=========
\ | | | | | | /  |              )
===============--================--===============
 O-O       O-O    O-O-O   O-O-O \\  O-O       O-O

```

The readable code at the beginning of the script simply decompressed the zlib-compressed string containing the body of the script and evals it. The decompressed code, in turn, looks like this:

```
@a=split$/,<<'';
            __
======      \/
| [] |=========
|              )
================--
 O-O-O   O-O-O \\

===============
| [] [] [] [] |
===============--
 O-O       O-O

===============
|-|-|  |  |-|-|
===============--
 O-O       O-O

 _____---_____
(             )
===============--
 O-O       O-O

_______________
\ | | | | | | /
===============--
 O-O       O-O

===============--
 O-O       O-O

    =====
====|   |====
| []     [] |
=============--
 O-O     O-O

$i=reverse pop=~y/EPBTHFC/0-6/r;
say$i=~s/./$a[6*$&+$_]/gr=~s/--$//r for 0..5

```

Note that all the train cars have their lines padded with spaces to a uniform length, and include the coupling (which is stripped from the rightmost car by the output loop). The DEFLATE compression used by zlib is very good at compressing such repetitive data, so there's no need to try and compress it by hand.

Note that this is a quick first attempt. I'm sure it would be possible to shave several bytes off the length by playing with variations such as reordering the train cars in the source.
> 23 votes

# Answer
### Python, 464

```
from curses import*
E,P,B,T,H,F,C='eJyNkM0NgDAIhe9MwVEPpBN0AxMHsKaLdHgfpVr7E+NHUyCQR4C5EiP5jKXBUeLj5ORvkDes5DtEiHeBoWo+hI36NtN9XurrRaVMQTSTEBizPo3+SGBBICLZ0/K9y0whtlDA/Gruj8SwyaRJA9tSPz16qmdTxqO9VeAvC5VloQ=='.decode('base64').decode('zlib').split('L')
i=[s.split('\n')for s in map(eval,raw_input()[::-1])]
h=max(sum(map(bool,s))for s in i)
w=initscr()
x=0
for t in i:[w.addstr(y,x,t[y+6-h])for y in range(h)];x+=len(t[-2])
w.addstr(h-2,x-2,'  ')
w.getch()
endwin()

```

I went for an approach using curses. It can't really compete, but I had some fun with it (~630 bytes):

```
from curses import*
E,P,B,T,H,F,C='eJyFkMENwCAIRe9M8Y/tgTiBGzTpALVxEYcvSFqiNO2DCAb8BgCnVsodu5ZEDceJlm/kPrBSniDsLCY1i6VsNDeZ6uMt1GEKMJU3ARYD1DX7F5DRBGbukZbvKeL7OkJF/nZL/wJxhrlFE6vooYtuviwlrso1JF745GMr'.decode('base64').decode('zlib').split('L')
i=[s.split('\n')for s in map(eval,raw_input()[::-1])]
h=max(sum(map(bool,s))for s in i)
w=initscr()
m=w.getmaxyx()[1]
for o in range(-sum(2+len(t[-2])for t in i),m):
 x=o
 for t in i:
  if m>x>o:w.addnstr(h-2,max(x,0),'--'[max(0,-x):],m-x);x+=2
  [w.addnstr(y,max(x,0),t[y+6-h][max(0,-x):],m-x)for y in range(h)if x<m];x+=len(t[-2])
 w.move(h,0);w.refresh();w.clear();napms(90)
endwin()

```
> 65 votes

# Answer
## Python (~~582~~ ~~488~~ ~~476~~ 450 Chars)

```
import sys
A=sys.argv[1]
h=0
c='eJyVkrEKAzEIhnef4h97g9x+kOVKS7d2uK0peZE8fNXQS3NCpb+BREU/YnIhfKkUgJKpBfIsgYrnCzV9pIFBE6WDCHcWk1zbMy0PGovg/GMPw+6rujwaAY0CWtb/ESwG6NJTjNhChMxQxMy2g06/R+URtxBRRlGWC3SbY8Q1vkXgh4gz+Qb7v7Jy/US1P7TKP3NvbG3fy/V/Cw=='.decode('base64').decode('zlib').split(':')
C={}
for x in c:X=x.split('\n');C[X[0]]=X[1:-1]
for c in A:h=max(h,1+('F..CE'.find(c)+1or 3))
for y in range(6-h,6):print(' -'[y==4]*2).join(C[c][y]for c in A[::-1])

```

The ascii-salad is a base64 encoded zlib-compressed string containing the figures...
> 8 votes

# Answer
# Python, ~~402~~ 369

```
import sys
for n in range(6):
 l= sys.argv[1][::-1]
 for x,y in zip("EPBTHFC",range(0,42,6)):
  l=l.replace(x,'eJytktsNgCAMRVfpp340TMAHEziAGBZhePvgLYmGeGosXqQXSAEqIfDbWUElb0SKcF4QbUaljr0srCA6OJCC5jV7cDAyUYY6eQPlic9/kleqoKNVL6QANkmj37zohglElMzK9naJy16hhxRPR6ph/jzXB2XBS76bZpQa3Hex7Qpm1hOtg+Yb0a6PSA=='.decode('base64').decode('zlib').split('A')[y+n]).strip('-')
 print l

```

Thanks you for the improvements, ugoren!
> 7 votes

# Answer
## Java 10, ~~637~~ ~~617~~ ~~600~~ ~~595~~ ~~593~~ 592 chars

```
interface T{static void main(String[]u){String g=" ",n=g+g,m=n+g,s=m+m,h=s+s,q=h+m,o=" O-O",w=o+s+o+n,y="=",d=y+y+y,p="_____",b=d+d,e=b+b,f=n+n,t=e+d,c="|",l=g+c,z=l+l+l,v="|-|-|",k=" []",x=k+k,r=k+l,a[]={h+"__"+n,b+s+"\\/"+n,c+r+b+d+g,c+h+n+")",t+y,o+"-O"+n+o+"-O \\\\",q,q,t,c+x+x+l,t,w,q,q,t,v+g+l+n+v,t,w,q,q,g+p+"---"+p+g,"("+h+" )",t,w,q,q,p+p+p,"\\"+z+z+" /",t,w,q,q,q,q,t,w,h+g,f+d+y+y+f,d+y+c+m+c+d+y,c+k+f+r,e+y,o+f+o+n,n,n,n,n,"--",g};var O=System.out;for(int i=-1,j;i++<5;O.println())for(j=u[1].length();j-->0;O.print(a["EPBTHFC".indexOf(u[1].charAt(j))*6+i]+(j>0?a[42+i]:"")));}}

```

Try it online!

Readable:

```
interface T{
    static void main(String[]u){
        // constants - carriages' parts, a[] - array of carriages
        String g=" ",n=g+g,m=n+g,s=m+m,h=s+s,q=h+m,o=" O-O",w=o+s+o+n,y="=",d=
                y+y+y,p="_____",b=d+d,e=b+b,f=n+n,t=e+d,c="|",l=g+c,z=l+l+l,v=
                "|-|-|",k=" []",x=k+k,r=k+l,a[]={h+"__"+n,b+s+"\\/"+n,c+r+b+d+
                g,c+h+n+")",t+y,o+"-O"+n+o+"-O \\\\",q,q,t,c+x+x+l,t,w,q,q,t,v
                +g+l+n+v,t,w,q,q,g+p+"---"+p+g,"("+h+" )",t,w,q,q,p+p+p,"\\"+z
                +z+" /",t,w,q,q,q,q,t,w,h+g,f+d+y+y+f,d+y+c+m+c+d+y,c+k+f+r,e+
                y,o+f+o+n,n,n,n,n,"--",g};
        // output ASCII train
        var O=System.out;
        for(int i=-1,j;i++<5;O.println())
            for(j=u[1].length();j-->0;O.print(
                    a["EPBTHFC".indexOf(u[1].charAt(j))*6+i]+(j>0?a[42+i]:"")));
    }
}

```

---

Train carriages. The lower line of each carriage is one character longer because of engine but the lower line of couplings is one character shorter. Double backslashes are *escaped characters*, they are interpreted as a single backslash:

```
String a[] = {
        // Engine (E)
        "            __  ",
        "======      \\/  ",
        "| [] |========= ",
        "|              )",
        "================",
        " O-O-O   O-O-O \\\\",
        // Passenger car (P)
        "               ",
        "               ",
        "===============",
        "| [] [] [] [] |",
        "===============",
        " O-O       O-O  ",
        // Boxcar (B)
        "               ",
        "               ",
        "===============",
        "|-|-|  |  |-|-|",
        "===============",
        " O-O       O-O  ",
        // Tanker (T)
        "               ",
        "               ",
        " _____---_____ ",
        "(             )",
        "===============",
        " O-O       O-O  ",
        // Hopper (H)
        "               ",
        "               ",
        "_______________",
        "\\ | | | | | | /",
        "===============",
        " O-O       O-O  ",
        // Flatbed (F)
        "               ",
        "               ",
        "               ",
        "               ",
        "===============",
        " O-O       O-O  ",
        // Caboose (C)
        "             ",
        "    =====    ",
        "====|   |====",
        "| []     [] |",
        "=============",
        " O-O     O-O  ",
        // Car coupling
        "  ",
        "  ",
        "  ",
        "  ",
        "--",
        " "};

```

Train `EPBTHFC`:

```
                                                                                __
    =====                                                                                ======      \/
====|   |====                   _______________   _____---_____   ===============  ===============  | [] |=========
| []     [] |                   \ | | | | | | /  (             )  |-|-|  |  |-|-|  | [] [] [] [] |  |              )
=============--===============--===============--===============--===============--===============--================
 O-O     O-O    O-O       O-O    O-O       O-O    O-O       O-O    O-O       O-O    O-O       O-O    O-O-O   O-O-O \\

```
> 4 votes

# Answer
## Java (583 characters)

With basic homemade compression - not sure it's so efficient though :-) The train string (e.g. `EEHTBPFC`) must be passed as parameter.

```
class C{public static void main(String[]a){String s="",y="thAthA",x=" *!*h*!* A",q="vjA",r=q+x+y;String[]m=("hP78A^\\#$8A% &' %j.,A%hh) Ajj.A *!*!*8*!*!* /A"+y+q+"% &' &' &' &' %A"+r+q+"%!%!%,%,%!%!%A"+r+" [9[ A(tP)A"+r+"ss+A# % % % % % % $A"+r+y+q+x+"tPADRDAF%8%FA% &'P&' %AvRA *!*P*!* ").split("A");for(int l,z,i,j=0;j<6;j++){for(i=a[0].length()-1;i>=0;i--){z=a[0].charAt(i);r=m["EPBTHFC".indexOf(z)*6+j];for(int c:r.toCharArray()){c-=32;for(l=0;l<=c/12;l++)s+=" -=\\/|[]()O_".charAt(c%12);}if(i>0)for(l=0;l<(z=='E'&&j!=4?1:2);l++)s+=j==4?"-":" ";}s+="\n";}System.out.println(s);}}

```

Unfolded:

```
class C{
    public static void main(String[]a){
        String s="",y="thAthA",x=" *!*h*!* A",q="vjA",r=q+x+y;
        String[]m=("hP78A^\\#$8A% &' %j.,A%hh) Ajj.A *!*!*8*!*!* /A"+y+q+"% &' &' &' &' %A"+r+q+"%!%!%,%,%!%!%A"+r+" [9[ A(tP)A"+r+"ss+A# % % % % % % $A"+r+y+q+x+"tPADRDAF%8%FA% &'P&' %AvRA *!*P*!* ").split("A");
        for(int l,z,i,j=0;j<6;j++){
            for(i=a[0].length()-1;i>=0;i--){
                z=a[0].charAt(i);
                r=m["EPBTHFC".indexOf(z)*6+j];
                for(int c:r.toCharArray()) {
                    c-=32;
                    for(l=0;l<=c/12;l++)
                        s+=" -=\\/|[]()O_".charAt(c%12);
                }
                if(i>0)for(l=0;l<(z=='E'&&j!=4?1:2);l++)s+=j==4?"-":" ";
            }
            s+="\n";
        }
        System.out.println(s);
    }
}

```
> 3 votes

# Answer
### C#, ~~758~~ ~~664~~ ~~603~~ 562bytes

Not a great score, 200 or so bytes in the poorly encoded string, and about 80 bytes devoted to decoding it. Frustrating amount of code spent sorting out the coupling on the engine! It now leaves white-space trailing at the front of the train, which is untidy but within the rules, and it also has the dimensions of the data-string hard coded, something I was reluctant to do initially.

```
using c=System.Console;class P{static void Main(){string d=c.ReadLine(),a="",z=@"99 1_5 4=78 5=5 \/1 3=|2 |3=14 29= 4_2-4_ 14_| [] |8= | []4 [] |14 | [] [] [] [] 1|-|-|1 |1 |-|-|(12 )\ | | | | | | /|13 )103= O-O4 O-O1 O-O6 O-O1 O-O6 O-O1 O-O6 O-O1 O-O6 O-O1 O-O6 O-O1 O-O-O2 O-O-O c";int j=0,e;foreach(var h in z)if(h>47&&h<58)j=j*10+h-48;else for(j++;j>0;j--)a+=h;int[]x={0,13,28,43,58,73,88,104};for(;j<6;j++){z="";foreach(var h in d)z=a.Substring(j*104+x[e="CFPBTHE".IndexOf(h)],x[e+1]-x[e])+(j==4?"--":"  ")+z;c.WriteLine(z.Replace("c ",@"\\").Trim('-'));}}}

```

Formatted a bit:

```
using c=System.Console;
class P{static void Main(){
    string d=c.ReadLine(),a="",z=@"99 1_5 4=78 5=5 \/1 3=|2 |3=14 29= 4_2-4_ 14_| [] |8= | []4 [] |14 | [] [] [] [] 1|-|-|1 |1 |-|-|(12 )\ | | | | | | /|13 )103= O-O4 O-O1 O-O6 O-O1 O-O6 O-O1 O-O6 O-O1 O-O6 O-O1 O-O6 O-O1 O-O-O2 O-O-O c";

    int j=0,e;

    foreach(var h in z)
        if(h>47&&h<58)
            j=j*10+h-48;
        else
            for(j++;j>0;j--)
                a+=h;

    int[]x={0,13,28,43,58,73,88,104};

    for(;j<6;j++)
    {
        z="";
        foreach(var h in d)
            z=a.Substring(j*104+x[e="CFPBTHE".IndexOf(h)],x[e+1]-x[e])+(j==4?"--":"  ")+z;
        c.WriteLine(z.Replace("c ",@"\\").Trim('-'));
    }
}}

```

The string is compressed very simply by replacing repeated character with a string representation of the number of characters followed by the character (minus 1), or just the character if there is only one of them (I wanted to stick with ASCII and avoid doing anything at the sub-char level). Encoder (not included in score):

```
string compress(string str)
{
    str += (char)0; // too lazy to write a proper loop
    string res = "";

    char prev = str[0];
    int count = 1;

    for (int i = 1; i < str.Length; i++)
    {
        char cur = str[i];
        if (cur != prev)
        {
            if (count != 1)
                res += (count - 1).ToString();
            res += prev;

            prev = cur;
            count = 1;
        }
        else
        {
            count++;
        }
    }

    return res;
}

```
> 3 votes

# Answer
Here is my solution in PHP (v5.4 compatible), 512bytes. Could be shorter, but just made a quick build to try this out.

```
<?php $m=array_combine(str_split('EPBTHFC'),explode('$',gzinflate(base64_decode('jZDBDYAwCEXvfwoOHvRAnKAzOICYLtLhhVYlrY320RQI5BMgcmJEyJRUViTaD0rhRvOKBaEBtLGa1ooXmdA2FdXnJfQ0rgkW9RRYjcieRQMKupzCzNlj/t6jIxBrIDrdbR1QwH+PRaVkn107+cWM971cxPwJ'))));$t=['','','','','',''];$i=str_split(strrev(strtoupper($argv[1])));foreach($i as $w=>$n){$c=$m[$n];$c=explode("\n",$c);foreach($t as $j=>&$p){$p.=str_pad($c[$j],$n=='E'?18:($n=='C'?15:17),$j==4?'-':' ');if($w==count($i)-1)$p=rtrim($p,' -');}}echo implode("\n",$t)."\n";

```

This is a spread-out version for easy reading:

```
<?php
$m=array_combine(
  str_split('EPBTHFC'),
  explode('$',
    gzinflate(
      base64_decode(
        'jZDBDYAwCEXvfwoOHvRAnKAzOICYLtLhhVYlrY320RQI5BMgcmJEyJRUViTaD0rhRvOKBaEBtLGa1ooXmdA2FdXnJfQ0rgkW9RRYjcieRQMKupzCzNlj/t6jIxBrIDrdbR1QwH+PRaVkn107+cWM971cxPwJ'
      )
    )
  )
);
$t=['','','','','',''];
$i=str_split(strrev(strtoupper($argv[1])));
foreach($i as $w=>$n)
{
  $c=$m[$n];
  $c=explode("\n",$c);
  foreach($t as $j=>&$p)
  {
    $p.=str_pad($c[$j],$n=='E'?18:($n=='C'?15:17),$j==4?'-':' ');
    if($w==count($i)-1)$p=rtrim($p,' -');
  }
}
echo implode("\n",$t)."\n";

```
> 3 votes

# Answer
# Python, 491 bytes

```
import zlib as z,sys,base64 as d
y=eval(z.decompress(d.b64decode('eNqlksEOwiAMhl/lv1WTkd1NdtFovLmDt7HwIOK729LJmJDY6F8SyA/0g6YPOtNhIhQKAaCOhiS1fJ+siGlGHN5Sa6N9vriKLdwcB+/r7D3NHY2fYCRI7dT50kPyiM0zUCKUCiEe/yA6DkCGrKzEu5XIVWc559Iszu5bYdvEq5UYtmLH8/fW6K3Ei/mPP1W+QTxVxCVXbtklk3RnLHtG1OqYkqOU5wsfZZmx')))
w=sys.argv[1][::-1]
x=[""]*6
v=range
u=len(w)
for j in v(6):
 for i in v(u):
  if j==5 and w[i]=='E':k="\\ "
  elif j==4 and i!=u-1:k="--"
  else:k="  "
  x[j]+=y[w[i]][j]+k
for q in x:print q

```

I like how it came out, even though it won't be a winner.
> 2 votes

# Answer
# C (gcc), ~~501~~ ~~499~~ ~~490~~ ~~489~~ ~~484~~ ~~483~~ 481 bytes

-2 -9 -1 -5 -1 -2 bytes thanks to ceilingcat.

```
#define A": O-Og O-O:o=:"
char*p,*q,s[80];i=6,k,n;main(j,a)char**a;{for(;i--;puts(q))for(k=strlen(a[1]);k--;*q=0,printf("%-*s%s",j?j^6?15:13:16,s,k?i^1?!j*!i+"  ":"--":q)){j=index(p="EPBTHFC",a[1][k])-p;for(n=j*6+i,p=" O-O-Oc O-O-O \\\\:p=:|n ):| [] |i=:f=f \\/:l __"A"| [] [] [] [] |:o=::"A"|-|-|  |  |-|-|:o=::"A"(m ): e_c-e_::"A"\\ | | | | | | /:o_::"A":::: O-Oe O-O:m=:| []e [] |:d=|c |d=:d e=::";n--;)for(;*p++-58;);for(q=s;*p^58;q+=n)memset(q,*p++,n=islower(*p)?*p++-96:1);}}

```

Try it online!
> 2 votes

# Answer
# GNU sed, 491 bytes

```
s/./& #/g
s:E:0S__s%1esss\\/s%2|bpef %3|Ss)%4E=@5 o-Os o-O \\\\:g
s/P/zE%3|bbbbp%4E@5ut/g
s/B/zE%3|-|-|s|s|-|-|%4E@5ut/g
s/T/z l---l %3(S )%4E@5ut/g
s:H:zlll%3\\pppppp /%4E@5ut:g
s/F/zSs %3Ss %4E@5ut/g
s/C/0S %1ssf==ss%2f=|spf=%3|bssbp%4ee=@5 ts t/g
s/z/0Ss %1Ss %2/g
s/%/s%/g
s/@/--%/g
s/u/ tss /g
s/t/os/g
s/S/ssssss/g
s/s/  /g
s/E/eef/g
s/e/ff/g
s/f/===/g
s/b/ []/g
s/p/ |/g
s/o/O-O/g
s/l/_____/g
s/^/0123456;/
:
s/([0-6])(.*;)\1([^%#]+)[%#](.*)/\1\3!\2\4/
t
s/(--!)?[1-6]/\n/g
s/[0!;]//g

```

Try it online!

## Explanation

This is basically a super naïve custom compression scheme. The first line appends to each letter in the input a space and `#`, to mark the end of each part:

```
s/./& #/g

```

The next 7 lines replace each letter with a compressed representation of the corresponding ASCII image:

```
s:E:0S__s%1esss\\/s%2|bpef %3|Ss)%4E=@5 o-Os o-O \\\\:g
s/P/zE%3|bbbbp%4E@5ut/g
s/B/zE%3|-|-|s|s|-|-|%4E@5ut/g
s/T/z l---l %3(S )%4E@5ut/g
s:H:zlll%3\\pppppp /%4E@5ut:g
s/F/zSs %3Ss %4E@5ut/g
s/C/0S %1ssf==ss%2f=|spf=%3|bssbp%4ee=@5 ts t/g

```

The next 14 lines do the "decompression". For example, an `S` decompresses to six `s`es, and an `s` decompresses to two spaces, so `S` becomes 12 spaces.

```
s/z/0Ss %1Ss %2/g
s/%/s%/g
s/@/--%/g
s/u/ tss /g
s/t/os/g
s/S/ssssss/g
s/s/  /g
s/E/eef/g
s/e/ff/g
s/f/===/g
s/b/ []/g
s/p/ |/g
s/o/O-O/g
s/l/_____/g

```

Decompressed, the lines of each car are preceded by a line number, and each car is terminated by `#`. The rest of the code prepends `0123456;` (the line numbers and delimiter) to the pattern space and then, in a loop, replaces each digit with the corresponding line of each car.

```
s/^/0123456;/
:
  s/([0-6])(.*;)\1([^%#]+)[%#](.*)/\1\3!\2\4/
  t

```

Finally, it cuts the pattern space into lines by splitting on digits and cleans up extraneous characters:

```
s/(--!)?[1-6]/\n/g
s/[0!;]//g

```

There's a lot of room for improvement here. I wasn't rigorous at all about finding an optimal set of compressions, and using a lookup table instead of 14 separate `s///g`s would be an easy win. I may or may not noodle with this some more.
> 2 votes

# Answer
# Python 3, 529 bytes

```
a=['']*6
T,R="EPBTHFC",{'S':' '*3,'E':'='*3,'W':'[] ','U':'_'*5,'P':'| ','H':'O-O'}
A=('SSSS__  ',)+('S'*5,)*5+('SSSS ',),('EESS\/  ',)+('S'*5,)*5+('S E==S ',),('PW|EEE ','E'*5,'E'*5,' U---U ','U'*3,'S'*5,'E=|S|E='),('P SSSS)','PWWWW|','|-|-P P |-|-|','(SSSS )','\ PPPPPP/','S'*5,'PWS W|'),('E'*5+'=--',)+('E'*5+'--',)*5+('EEEE=--',),(' H-OSH-O \\\\ ',)+(' HSS HS',)*5+(' HS  HS',)
for C in input():
 for I in range(6):
  a[I]=A[I][T.index(C)]+'  '*(I<4)+a[I]
  for k in R:a[I]=a[I].replace(k,R[k])
a[4]=a[4][:-2]
[*map(print,a)]

```

Try it online!

Figured I would post it because it does not use any compression, unlike most of the other answers here.
> 1 votes

# Answer
# Javascript (Node.js), 1216 bytes

```
var c={E:['            __  ','======      \\/  ','| [] |========= ','|              )','================',' O-O-O   O-O-O \\',],P:['               ','               ','===============','| [] [] [] [] |','===============',' O-O       O-O'],B:['               ','               ','===============','|-|-|  |  |-|-|','===============',' O-O       O-O'],T:['               ','               ',' _____---_____ ','(             )','===============',' O-O       O-O '],H:['               ','               ','_______________','\\ | | | | | | /','===============',' O-O       O-O '],F:['               ','               ','               ','               ','===============',' O-O       O-O '],C:['             ','    =====    ','====|   |====','| []     [] |','=============',' O-O     O-O ']};var o=[];for(var w=0;w<process.argv[2].length;w++){o.push(process.argv[2].charAt(w));}var arg=o.reverse().join('');var s=['  ','  ','  ','  ','--','  '];for(var x=0;x<6;x++){var k=[];for(var y=0;y<arg.length;y++){if(!['B','C','E','F','H','P','T'].includes(arg.charAt(y))){y++;}k.push(c[arg.charAt(y)][x]);}var v='';for(var q in k){v+=k[q]; if(arg.charAt(q)=='E'&&x== 5){v+='\\ ';}else if(q<k.length-1){v+=s[x];}}console.log(v);}

```

Uncompressed

```
var c = { // define cars
    E: [
        '            __  ',
        '======      \\/  ',
        '| [] |========= ',
        '|              )',
        '================',
        ' O-O-O   O-O-O \\',
    ],
    P: [
        '               ',
        '               ',
        '===============',
        '| [] [] [] [] |',
        '===============',
        ' O-O       O-O'
    ],
    B: [
        '               ',
        '               ',
        '===============',
        '|-|-|  |  |-|-|',
        '===============',
        ' O-O       O-O'
    ],
    T: [
        '               ',
        '               ',
        ' _____---_____ ',
        '(             )',
        '===============',
        ' O-O       O-O '
    ],
    H: [
        '               ',
        '               ',
        '_______________',
        '\\ | | | | | | /',
        '===============',
        ' O-O       O-O '
    ],
    F: [
        '               ',
        '               ',
        '               ',
        '               ',
        '===============',
        ' O-O       O-O '
    ],
    C: [
        '             ',
        '    =====    ',
        '====|   |====',
        '| []     [] |',
        '=============',
        ' O-O     O-O '
    ]
};
//reverse string - why is there no builtin for this?
var o = [];
for(var w = 0; w < process.argv[2].length; w++){
    o.push(process.argv[2].charAt(w));
}
var arg = o.reverse().join('');
//train car seperators
var s = ['  ','  ','  ','  ','--','  '];
// for each row
for(var x = 0; x < 6; x++){
    var k = []; //empty array for each car string
    for(var y = 0; y < arg.length; y++){
        //ignore non-included characters
        if(!['B','C','E','F','H','P','T'].includes(arg.charAt(y))){
            y++;
        }
        // add car
        k.push(c[arg.charAt(y)][x]);
    }
    var v = '';
    for(var q in k){
        v += k[q]; // append car
        if(arg.charAt(q) == 'E' && x == 5){ // to deal with annoying engine thing, see below
            v += '\\ ';
        } else if(q < k.length - 1){ // if not last car
            v += s[x]; // append separator
        }
    }
    console.log(v); //output
}

```

The annoying thing about this challenge is the coupling near the engine. All the other cars are just one solid block, but the \ on the front takes up the same vertical space as the coupling. See here:

```
            __
======      \/
| [] |=========
|              )
================--
 O-O-O   O-O-O \\

```

Note: Enter via the CLI e.g. node asciitrain.js EBCEFH. This was badly golfed.
> 1 votes

---
Tags: code-golf, ascii-art, kolmogorov-complexity
---