title: Name the Aztec year

text:
# Question
Title: Name the Aztec year
It's time for another Mesoamerican calendar! The Xiuhnelpilli was used by the Aztecs (more properly, the Mexica) to name their years. Each year has a number and a sign. Here's part of the cycle:

```
Input; Output
1089; 13 Calli
1090; 1 Tochtli
1091; 2 Acatl
1092; 3 Tecpatl
1093; 4 Calli
1094; 5 Tochtli
1095; 6 Acatl
1096; 7 Tecpatl
1097; 8 Calli
1098; 9 Tochtli
1099; 10 Acatl
1100; 11 Tecpatl
1101; 12 Calli
1102; 13 Tochtli
1103; 1 Acatl
1104; 2 Tecpatl
1105; 3 Calli
1106; 4 Tochtli
1107; 5 Acatl
1108; 6 Tecpatl
1109; 7 Calli
1110; 8 Tochtli
1111; 9 Acatl
1112; 10 Tecpatl
1113; 11 Calli
1114; 12 Tochtli
1115; 13 Acatl
1116; 1 Tecpatl
1117; 2 Calli
1118; 3 Tochtli
1119; 4 Acatl
1120; 5 Tecpatl
1121; 6 Calli
1122; 7 Tochtli
1123; 8 Acatl
1124; 9 Tecpatl
1125; 10 Calli
1126; 11 Tochtli
1127; 12 Acatl
1128; 13 Tecpatl
1129; 1 Calli
1130; 2 Tochtli
1131; 3 Acatl
1132; 4 Tecpatl
1133; 5 Calli
1134; 6 Tochtli
1135; 7 Acatl
1136; 8 Tecpatl
1137; 9 Calli
1138; 10 Tochtli
1139; 11 Acatl
1140; 12 Tecpatl
1141; 13 Calli
1142; 1 Tochtli

```

The pattern should be clear enough: the number is counting up to 13, and the sign goes Tochtli, Acatl, Tecpatl, Calli. After 52 years the pattern repeats itself.

**The program** will take as input an integer between 1064 (the year the Mexica left their mythological homeland of Aztlan) and 1521 (fall of Tenochtitlan to the Spaniards), inclusive, and output the corresponding year name. It can be a single string (in which case there needs to be a space between number and sign), or a tuple (e.g. `["2", "Calli"]`) of your preferred format. The sign name is always capitalised.

Handling years outside the specified range is not necessary. It's , so the shortest code wins!

**Test cases**

The entire example list above, plus:

```
Input; Output
1064; 1 Tecpatl
1521; 3 Calli

```

# Answer
# 05AB1E, 30 bytes

```
Ì13%>.•19ŠSBÿ®Ï¿¾Ñλ1Ï7qι•#™Iè‚

```

Try it online or verify all test cases.

**Explanation:**

```
Ì       # Increase the (implicit) input by 2
 13%    # Take modulo-13 on that
    >   # And increase it by 1
.•19ŠSBÿ®Ï¿¾Ñλ1Ï7qι•
        # Push compressed string "tecpatl calli tochtli acatl"
  #     # Split it on spaces: ["tecpatl","calli","tochtli","acatl"]
   ™    # Titlecase each: ["Tecpatl","Calli","Tochtli","Acatl"]
    Iè  # Index the input into it (0-based and with automatic wraparound)
‚       # Pair the two together
        # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•19ŠSBÿ®Ï¿¾Ñλ1Ï7qι•` is `"tecpatl calli tochtli acatl"`.
> 2 votes

# Answer
# Python 3, ~~68~~ ~~62~~ 59 bytes

Saved ~~6~~ 9 bytes thanks to my pronoun is monicareinstate!!!

```
lambda n:((n+2)%13+1,"TCTAeaocclcaplhtaitlt l l i"[n%4::4])

```

Try it online!
> 5 votes

# Answer
# dc, ~~63~~ 62 characters

```
[Tecpatl]0:y[Calli]1:y[Tochtli]2:y[Acatl]3:y?d2+13%1+n32P4%;yp

```

Explained:

```
[Tecpatl] 0 :y    # store the string "Tecpatl" in array y at index 0
[Calli]   1 :y    # store the string "Calli" in array y at index 1
[Tochtli] 2 :y    # store the string "Tochtli" in array y at index 2
[Acatl]   3 :y    # store the string "Acatl" in array y at index 3
?                 # read input input
d                 # duplicate it to keep a copy for later
2+ 13% 1+ n       # the usual formula: (year + 2) % 13 + 1, then print it
32 P              # print a space
4 %               # use the left copy of input for formula: year % 4
;y p              # get the value from array y at the given index, then print it

```

Sample run:

```
bash-5.0$ dc -e '[Tecpatl]0:y[Calli]1:y[Tochtli]2:y[Acatl]3:y?d2+13%1+n[ ]n4%;yp' <<< 1111
9 Acatl

```

Try it online! / Try all test cases online!
> 4 votes

# Answer
# perl -pl, 61 bytes

```
$_=(($_+3)%13||13).$".(qw[Tecpatl Calli Tochtli Acatl])[$_%4]

```

Try it online!

Nothing special going on, modding the year twice, with some aligning. `$"` is a variable which by default holds a space.
> 3 votes

# Answer
# Java 8, ~~63~~ 62 bytes

```
y->1-~-~y%13+" "+"Tecpatl Calli Tochtli Acatl".split(" ")[y%4]

```

-1 byte thanks to *@ceilingcat*.

Try it online.

**Explanation:**

```
y->          // Method with integer parameter and String return-type
  1-         //  Decrease 1 by:
    ~-~y     //   (-y-2)
        %13  //   Modulo-13
  +" "       //  Append a space
  +"Tecpatl Calli Tochtli Acatl".split(" ")
             //  Split these four words as array
    [y%4]    //  And take the (0-based) year-modulo-4'th value

```
> 3 votes

# Answer
# Whitespace, 344 bytes

```
[S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve][S N
S _Duplicate_input][S S S T S N
_Push_2][T  S S S _Add][S S S T T   S T N
_Push_13][T S T T   _Modulo][S S S T    N
_Push_1][T  S S S _Add][T   N
S T _Print_as_integer][S S S T  S S T   N
_Push_9_tab][T  N
S S _Print_as_character][S S S T    S S N
_Push_4][T  S T T   _Modulo][S N
S _Duplicate][N
T   S S N
_If_0_Jump_to_Label_0][S S S T  N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate][N
T   S T N
_If_0_Jump_to_Label_1][S S S T  N
_Push_1][T  S S T   _Subtract][N
T   s S S N
_If_0_Jump_to_Label_2][S S S T  T   N
_Push_3_l][S S S T  S T T   N
_Push_11_t][S S T   T   S S S N
_Push_-8_a][S S T   T   T   S N
_Push_-6_c][S S T   T   S T S S S N
_Push_-40_A][N
S S N
_Create_Label_PRINT_LOOP][S S S T   T   S T S S T   N
_Push_105][T    S S S _Add][T   N
S S _Print_as_character][N
S N
N
_Jump_to_Label_PRINT_LOOP][N
S S S N
_Create_Label_0][S N
N
_Discard][S S S T   T   N
_Push_3_l][S S S T  S T T   N
_Push_11_t][S S T   T   S S S N
_Push_-8_a][S S S T T   T   N
_Push_7_p][S S T    T   T   S N
_Push_-6_c][S S T   T   S S N
_Push_-4_e][S S T   T   S T S T N
_Push_-21_T][N
S N
N
_Jump_to_Label_PRINT_LOOP][N
S S T   N
_Create_Label_1][S N
N
_Discard][S S S N
_Push_0_i][S S S T  T   N
_Push_3_l][S N
S _Duplicate_3_l][S S T T   S S S N
_Push_-8_a][S S T   T   S S T   T   S N
_Push_-38_C][N
S N
N
_Jump_to_Label_PRINT_LOOP][N
S S S S N
_Create_Label_2][S S S N
_Push_0_i][S S S T  T   N
_Push_3_l][S S S T  S T T   N
_Push_11_t][S S T   T   N
_Push_-1_h][S S T   T   T   S N
_Push_-6_c][S S S T T   S N
_Push_6_o][S S T    T   S T S T N
_Push_-21_T][N
S N
N
_Jump_to_Label_PRINT_LOOP]

```

Letters `S` (space), `T` (tab), and `N` (new-line) added as highlighting only.
`[..._some_action]` added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

**Explanation in pseudo-code:**

```
Integer year = STDIN as integer
Print (year+2) modulo-13 + 1 as integer to STDOUT
Print '\t' as character to STDOUT
Integer temp = year modulo-4
If(temp == 0):
  Push the codepoints of "ltapceT" minus 105 to the stack
If(temp-1 == 0):
  Push the codepoints of "illaC" minus 105 to the stack
If(temp-2 == 0):
  Push the codepoints of "ilthcoT" minus 105 to the stack
Else:
  Push the codepoints of "ltacA" minus 105 to the stack
Start PRINT_LOOP:
  Add 105 to the top integer on the stack
  Print this integer as character with this codepoint to STDOUT
  Go to the next iteration of PRINT_LOOP

```

Uses this Whitespace tip of mine to print the output, which will exit the program with an error as soon as we're done with printing and the stack is empty. The optimal constant `105` is generated by this Java program.
> 3 votes

# Answer
# jq (with `-r` switch), 57 characters

```
"\((.+2)%13+1) "+("Tecpatl Calli Tochtli Acatl"/" ")[.%4]

```

Sample run:

```
bash-5.0$ jq -r '"\((.+2)%13+1) "+("Tecpatl Calli Tochtli Acatl"/" ")[.%4]' <<< 1111
9 Acatl

```

Try it online! / Try all test cases online!
> 3 votes

# Answer
# APL (Dyalog Unicode), ~~55~~ 54 bytesSBCS

```
{((4 7⍴'TecpatlCalli  TochtliAcatl  ')⌷⍨4|⍵),1+13|2+⍵}

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~87~~ \\$\cdots\\$ ~~70~~ 69 bytes

Saved 2 bytes thanks to my pronoun is monicareinstate!!!
Saved a byte thanks to ceilingcat!!!

```
f(n){printf("%d %.7s",1-~-~n%13,"TecpatlCalli  TochtliAcatl"+n%4*7);}

```

Try it online!
> 2 votes

# Answer
# Jelly, 36 bytes

```
+3ịⱮ13R,“©ȥƒị Œñ⁾<ŻĠ)?ỵ%uxÐZỵȯẏ1»Ḳ¤¤

```

**Try it online!**

### How?

```
+3ịⱮ13R,“...»Ḳ¤¤ - Link: integer, Y
+3               - add three (to Y)
               ¤ - nilad followed by link(s) as a nilad:
    13R          -   range(13) = [1,2,3,4,5,6,7,8,9,10,11,12,13]
              ¤  -   nilad followed by link(s) as a nilad:
        “...»    -     compressed string = "Tochtli Acatl Tecpatl Calli"
             Ḳ   -     split at spaces = ["Tochtli","Acatl","Tecpatl","Calli"]
       ,         -   pair these together = [[1,2,3,4,5,6,7,8,9,10,11,12,13],["Tochtli","Acatl","Tecpatl","Calli"]]
   Ɱ             - map accross (these two lists) with:
  ị              -   index into (1-based & modular)

```
> 2 votes

# Answer
# Befunge-93, 100 bytes

```
&:2+67+%1+.4%:#v_"ltapceT",,v
<"Calli"_v#!-1:<@,,,,, <    <
         >2`!#v_"ltacA"^
^  ,,"Tochtli"<

```

Try it online!

Reads the year from input, and duplicates it. Adds 2, mods it with 13, adds 1 to the result and prints it. Then mods the year with 4, and using a series if if statements, selects the right name to print.
> 2 votes

# Answer
# , 43 bytes

Straightforward implementation. Takes a number like 1090, returns boxed tuple \[1|Tochtli\].

```
(1+13|2+]);Tecpatl`Calli`Tochtli`Acatl{~4|]

```

Try it online!

### How it works

```
(1+13|2+]);Tecpatl`Calli`Tochtli`Acatl{~4|]
                                        4|] x mod 4
           Tecpatl`Calli`Tochtli`Acatl{~    select from boxes
(1+13|2+])                                  ((x + 2) mod 4) + 1
          ;                                 join left & right side

```
> 2 votes

# Answer
# Charcoal, 38 bytes

```
ＮθＩ⊕﹪⁺²θ¹³ §⪪”(0«βxo%↔W^⊘Ｓ≧L≔Z⮌⍘｜Nº” θ

```

Try it online! Link is to verbose version of code. Explanation:

```
ＮθＩ⊕﹪⁺²θ¹³

```

Input the year, add 2, reduce modulo 13, add 1, and print as a string, followed by a space.

```
§⪪”(0«βxo%↔W^⊘Ｓ≧L≔Z⮌⍘｜Nº” θ

```

Split the compressed string `Tecpatl Calli Tochtli Acatl` on spaces and print the entry cyclically indexed using the year.
> 1 votes

# Answer
# Ruby, 54 bytes

```
->y{[(y+2)%13+1,%w[Tecpatl Calli Tochtli Acatl][y%4]]}

```

Try it online!
> 1 votes

# Answer
# Pyth, 41 bytes

```
(h%+2Q13@c." t£>Ì<ëWÈ¶Adh|Å],%œ¯s")%Q4

```

Try it online!

The number is calculated with `1+((x+2)%13))`, x being the input.
The sign is retrieved by indexing into a packed string, split on whitespace.

Oddly enough, using repeated indexing for the string (like in other answers) yielded the same bytecount for me.
> 1 votes

# Answer
# JavaScript, ~~58~~ 57 bytes

-1 byte using the numerical method from @ceilingcat used in Kevin Cruijssen's Java answer

```
n=>[1-~-~n%13,["Tecpatl","Calli","Tochtli","Acatl"][n%4]]

```

Try it online!

It's been a long time since I got to a question fast enough to post a Javascript answer. (July 15, 2017 appears to have been my last for one that wasn't a king of the hill challenge.)

Pretty straightforward, get the right number with some ~~basic~~ modular arithmetic and get the sign with some array indexing mod 4.
> 1 votes

# Answer
# PHP, 69 bytes

```
fn($n)=>(($n+2)%13+1).' '.['Tecpatl','Calli','Tochtli','Acatl'][$n%4]

```

Try it online!

Just a port of Abigail's perl answer using Arnauld's edit suggestion, i fear.. but I had to, it's a 69
> 1 votes

# Answer
# Kotlin, 72 bytes

```
fun f(x:Int)=(x+2)%13+1 to "Tecpatl Calli Tochtli Acatl".split(" ")[x%4]

```

Try it online!
> 1 votes

---
Tags: code-golf, number
---


title: Validate Blokus Board

text:
# Question
Title: Validate Blokus Board
*Blokus* is a board game in which players take turns placing pieces on a \\$ n \times n \\$ square grid. In this version of the game, there will be just one person playing. The person is given \\$ 21 \\$ unique polyominoes, ranging from \\$ 1 \\$ to \\$ 5 \\$ tiles each. They then proceed to place down a subset of the pieces onto the board. After the pieces have been placed, it is your job to determine whether it could be a valid *Blokus* board.

There are \\$ 3 \\$ key rules for placing down pieces, which must be followed:

\\$ 1. \\$ The first piece being placed must touch one of the four corners of the board
\\$ 2. \\$ After the first piece, each subsequent piece must *not* contain a tile that is adjacent to another piece in any of the four cardinal directions *(not including diagonals)*
\\$ 3. \\$ After the first piece, each subsequent piece must contain at least one tile that is diagonally adjacent to another piece, *(that is, all pieces should form a single connected component which are connected only by corners touching)*

## Task

The task is to determine, given an \\$ n \times n \\$ square grid, whether it could be a valid *Blokus* board. A *Blokus* board is considered valid if it obeys the \\$ 3 \\$ rules given above.

In addition, you can assume that the board will consist only of the \\$ 21 \\$ valid *Blokus* pieces. However, you may *not* assume that there are no duplicates. A board which contains a duplicate is automatically considered invalid.

### Very Important

You may notice that sometimes a single board can have multiple orientations of the pieces. For example,

```
...
.XX
XXX

```

might be a single `P` piece, but it could also be a `V3` piece directly adjacent to a `2` piece, among other things. If this is ever the case, you should output a Truthy value if *any* of these orientations match. So in the above example, it would return *true*, because while it could be a `V3` and a `2` piece, which breaks Rule 2, it could also be a single `P` piece, making it a valid board.

## Clarifications

* The board will be inputted as a grid of two distinct values, denoting whether a given tile is occupied by a polyomino
* The input can be taken in any reasonable format *(e.g. 2D array, flattened string, list of coordinates + dimensions)*
* The pieces can be rotated or reflected before placing on to the board
* Not all the pieces are required to be placed down to be considered a valid position

## Test Cases

### Truthy

```
('X' for occupied, '.' for unoccupied)

.X.
.XX
X..

XX.X
XXX.
...X
..XX

.....
.....
.....
.....
.....

......
......
......
......
......
X.....

X....XXX.
X..XX.X..
X..XX..X.
X.....XXX
X.XX.X.X.
.X.XX....
.X..X.XXX
.X.X.X...
.X.XXX...

```

### Falsey

```
('X' for occupied, '.' for unoccupied)

Invalid configuration, there is no such piece, unless two pieces are joined to
look as one (e.g. 'L4' piece is directly adjacent to '2' piece), which would
break Rule 2.
XXX
X.X
X..

Invalid, since a valid board can contain no duplicates.
X....
X....
X....
X....
.XXXX

Invalid configuration. Even though the pieces are all valid, it doesn't start in
one of the four corners, which breaks Rule 1.
.....
..X..
.XXX.
.X...
..X..

Invalid configuration. All pieces are valid and are not adjacent horizontally
or vertically, however they are disjoint (they do not form a single chain, which
breaks Rule 3).
X...XX
X.X.XX
X.X..X
..XXX.
.....X
X..XXX

Invalid configuration. The two components are disjoint.
.XX..
X....
X.X..
X..XX
X..XX

Invalid configuration. It breaks Rule 1, 2, and 3 (board may be portrayed as an
'L4' piece at the bottom, and an 'O' and a '2' piece at the top).
.....
.XXXX
...XX
.X...
.XXX.

```

This is , so the shortest code in bytes wins!

# Answer
> 4 votes
# Python 2, ~~446~~ ~~422~~ ~~385~~ 384 bytes

-1 byte thanks to @ovs

```
l=len
A=abs
s="""def v(O,N):
 def c():
 qp:
    qp:
        if(i!=j)*any(A(t-T)==1qiqj):i+=j;p.remove(j);c();return
 p=[[a]qO];c();r=C=p[:1];i=[sum(A(b-a)*A(c-b)qPqPqP)qp];N-=1
qC:
  if l(o)>5:r=0
 qp:C+=[P]*(1-all(A(a-b)-2**0.5qoqP)-(P in C))
 print(l(p)-l(C)+l(i)-l(set(i))==0)*any(k in Oq[0,N*1j,N+N*1j,N])*r,p>[]"""
exec eval("s"+".replace('q',' for %s in ',1)"*14%tuple("ijtTaabcPoPabk"))

```

The output format is a bit strange: it prints more than 7 characters for truthy output, and 7 or fewer characters for falsey output (7 characters is the length of `"[] True"`. This may be stretching it, so the `p>[]` can be replaced by `if p!=[] else 1` for +11 characters to give more traditional truthy/falsey output.

The input is a list of coordinates given as complex numbers, along with the dimension `n`.

Try it online!

All testcases

The invariant may be the most interesting part. Since it must be conserved on rotations and reflections, distance between corresponding tiles is just about the only thing that stays constant. Also, I could not rely on the order that the tiles are listed in the piece. Using the product/sum of distances between every tile led to collisions, but using triples of tiles worked well.

I used `for _ in` fourteen times (wow), so the `exec`/`eval` saves 37 bytes.

Ungolfed:

```
def invariant(piece):
    inv=1
    for a in piece:
        for b in piece:
            for c in piece:
                inv+=abs((b-a)*(c-b))
    return inv

def valid(occupied,n):
    # convert list of rows into coordinates of Xs
    if not len(occupied):
        return True
    # generate list of pieces (this takes care of rule #2)
    pieces = [[a] for a in occupied]
    def consolidate():
        for i in pieces:
            for j in pieces:
                # merge two pieces if they share an edge
                if i!=j and any(abs(tile1-tile2)==1 for tile1 in i for tile2 in j):
                    i += j
                    pieces.remove(j)
                    # this repeats consolidate until no change (nothing left to combine)
                    consolidate()
                    return
    consolidate()
    # get a connected component of pieces (for rule #3)
    connected = [pieces[0]]
    for connected_piece in connected:
        # eventually every piece should be connected if the board is otherwise valid, so
        # we can check for valid-size pieces in this outer loop
        # all polyominoes with at most 5 tiles are valid
        if len(connected_piece) > 5:
            return False
        for piece in pieces:
            if any(abs(a-b)==abs(1+1j) for a in connected_piece for b in piece) and piece not in connected:
                connected += [piece]
    # check that all pieces are only used once
    ids = [invariant(piece) for piece in pieces]
    used_once = len(ids) == len(set(ids))
    nm = n-1
    rule_1_met = any(k in occupied for k in [0, nm*1j, nm+nm*1j, nm])
    return used_once and rule_1_met and len(pieces) == len(connected)

```

# Answer
> 4 votes
# JavaScript (ES7),  ~~344 330 328~~  326 bytes

Takes a binary matrix as input. Returns **0** or **1**.

```
m=>[-1,C=E=I=0,1,2,1,4].map(Z=t=>(m=m.sort(_=>t-3).map((r,y)=>r.map((_,x)=>m[x][y])),C|=!!m[0][0],g=(X,Y)=>m.map((r,y)=>r.map((v,x)=>(q=(x-X)**2+(y-Y)**2,t&1?v>0:v<0)?~t?1/X?q-1||g(x,y,S.push(x-H,y-V),r[x]=t?-v:I,n++):E|=Z[g(H=x,V=y,K=r[x]=t?-v:++I,S=[d=n=1]),S]-(Z[S]=K*K)|n>5|v==1:q<3|!I&&g(x,y,r[x]=-1,I=1):0)))())|I<2|C&!E

```

Try it online!

## How?

### About the 2nd rule

The 2nd rule is implicitly enforced if we:

1. Assume that adjacent tiles always belong to the same piece.
2. Make sure that all pieces are made of at most 5 tiles.
3. Make sure that there are no duplicate pieces (either rotated or reflected).

### Main algorithm

Our algorithm works with 6 iterations.

The pieces are identified by flood-filling the occupied tiles of the grid.

During the first iteration, we look for the first occupied tile as a starting point and flood-fill in all directions (including diagonals) with \\$-1\\$. If a piece is not connected to the other ones, it will still be filled with \\$1\\$'s after this process, as the secluded red tile in the example below.

During the second iteration, each piece is renumbered with a distinct ID, starting at \\$2\\$.

*Example:*

*(ignoring the transformations that are described in the next paragraph)*

$$\begin{pmatrix} 1&1&0&1\\ 1&1&1&0\\ 0&0&0&1\\ \color{red}1&0&1&1 \end{pmatrix}\rightarrow \begin{pmatrix} -1&-1&0&-1\\ -1&-1&-1&0\\ 0&0&0&-1\\ \color{red}1&0&-1&-1 \end{pmatrix}\rightarrow \begin{pmatrix} 2&2&0&3\\ 2&2&2&0\\ 0&0&0&4\\ \color{red}1&0&4&4 \end{pmatrix} $$

During the next iterations, only the sign of the IDs is changed.

### Transformations

At each iteration, the matrix is either rotated or reflected in such a way that 2 duplicate pieces are guaranteed to eventually appear with the same shape at some point.

For each piece, we build a shape key consisting of a flatten list \\$S\\$ of \\$(dx,dy)\\$ values. It describes the positions of the tiles, using the top-left one as the origin. The keys are stored in the object \\$Z\\$.

There is a duplicate if we encounter the same key at any iteration for two distinct piece IDs.

### Flags and final result

The flag \\$E\\$ (for error) is set if:

* a duplicate is found
* or a piece is made of more than 5 tiles
* or there's at least one tile which is still marked as \\$1\\$, meaning that a piece is not connected to the other ones

At each iteration, we test whether the tile at \\$(0,0)\\$ is occupied and set the flag \\$C\\$ (for corner) if it is. Because all rotations are tried, it is guaranteed to be set if there's at least one piece in any corner.

Because an empty board is valid although it has no corner, we also need the variable \\$I\\$, which is the number of pieces + 1.

The final result is given by:

$$(I\<2)\text{ or }\big(C\text{ and }(\operatorname{not} E)\big)$$

# Answer
> 3 votes
# , ~~134~~ 130 bytes

Takes the dimensions and a list of points. I'm not sure if this is the best approach, but it is shorter then a quick matrix attempt.

```
(((140*/@:>#"1)*[-:~.)@((5 2$0 0,i:1)&n)*2>[:#(,/,"0/~i:1)&n=.]/:~@,@:(-/~)/.~[:+./"2@#~^:_]e./"2+"1/~)@[*(+/@e.~0,3 2$0,<:)+0=#@[

```

Try it online!

### How it works

We check five things:

1. empty list OR all of …
2. corner is in the points
3. all points are connected to each other via 8 directions
4. all groups that are connected to each other via 4 directions have max length of 5
5. the groups of 4 are unique

Most components and the combination of them can probably be golfed further. The most interesting part will be the uniqueness check: it calculates all differences between points and sorts them, flattened down. So `1 2, 2 2 -> 1 0, _1 0 -> _1 0 0 1`. Not sure if this would be enough for all polyominoes, but for up to length 5 it seems to work.

A rough ungolfed version looks like this:

```
points=. 4 2 $ 0 1 , 1 1 , 1 2 , 2 0    NB. input
dims=. 3 3                              NB. input
empty=. 0=# points                      NB. 1
corner=. points (+/@e.~0,3 2$0,<:) dims NB. 2
dir8=. ,/,"0/~i:1                       NB. the 4 directions
dir4=. 5 2$0 0,i:1                      NB. the 8 directions
borders=. ]e./"2+"1/~                   NB. connection matrix: 1 iff. a borders b
expand=. +./"2@#~^:_                    NB. repeat in the matrix:
                                            if a<->b and b<->c then a<->c
group=. ] <./~ expand@borders           NB. partitions points to groups
                                            based on connection matrix
con8=. (2>[:#dir8&group) points             NB. 3
con4=. ([:*/6>#&>) (dir4 group points)      NB. 4
forms=. (/:~@,@:(-/~)&>) (dir4 group points)
unique=. (-:~.) forms                       NB. 5
f=. empty + corner * con4 * con8 * unique

```

# Answer
> 1 votes
# Charcoal, ~~231~~ 213 bytes

```
ＷＳ⊞υιυ≔⟦⟧ζ≔⟦⟧θ≔⟦⁰⊖Ｌυ⟧ηＦηＦηＦ⁼X§§υικ⊞θ⟦ικ⟧Ｗθ«≔…θ¹θＦθ«Ｊ⊟κ⊟κ¿⁼XＫＫ«↓#Ｆ⁴«Ｍ✳⊕⊗λ⊞θ⟦ⅉⅈ⟧»»»≔Φ⪪⭆ＫＡ⁼#κＬυΣκθＵＭθ✂κ⌊Ｅθ⌕μ1⊕⌈Ｅθ⊟⌕Ａμ1≔⟦⟧ηＦ⁴«⊞ηθ≔⮌θθ⊞ηθ≔Ｅ§θ⁰⭆θ§νμθ»⊞ζ⌊ηＵＭＫＡ⎇⁼#κ*κ≔⟦⟧θＦ⌕ＡＫＡX«Ｊ﹪κＬυ÷κＬυ¿№ＫＭ*⊞θ⟦ⅉⅈ⟧»»¿№ＫＡX⎚«⎚¬⊙ζ∨⊖№ζι‹⁵Σ⪫ιω

```

Try it online! Link is to verbose version of code. Outputs a Charcoal boolean, i.e. `-` for valid, nothing if invalid. Explanation:

```
ＷＳ⊞υιυ

```

Copy the board to the canvas.

```
≔⟦⟧ζ

```

Start with no pieces discovered.

```
≔⟦⟧θ

```

Start with no connected squares to check.

```
≔⟦⁰⊖Ｌυ⟧ηＦηＦη

```

Check the corners.

```
Ｆ⁼X§§υικ

```

If there is a piece in this corner, then...

```
⊞θ⟦ικ⟧

```

add that to the list of connected squares.

```
Ｗθ«

```

Repeat while there is at least one connected square.

```
≔…θ¹θ

```

Take the first square.

```
Ｆθ«Ｊ⊟κ⊟κ¿⁼XＫＫ«↓#Ｆ⁴«Ｍ✳⊕⊗λ⊞θ⟦ⅉⅈ⟧»»»

```

Perform a flood fill to complete this piece.

```
≔Φ⪪⭆ＫＡ⁼#κＬυΣκθＵＭθ✂κ⌊Ｅθ⌕μ1⊕⌈Ｅθ⊟⌕Ａμ1

```

Represent the piece as a binary matrix (using strings of `0`s and `1`s originally because Charcoal apparently can't reverse a binary array but it turns out that strings allow me to save another byte anyway) and extract the minimum enclosing rectangle.

```
≔⟦⟧ηＦ⁴«⊞ηθ≔⮌θθ⊞ηθ≔Ｅ§θ⁰⭆θ§νμθ»

```

Generate all the rotations and reflections of the piece.

```
⊞ζ⌊η

```

Add the minimum to the list of discovered pieces.

```
ＵＭＫＡ⎇⁼#κ*κ

```

Change the piece character from `#` to `*`.

```
Ｆ⌕ＡＫＡX«Ｊ﹪κＬυ÷κＬυ¿№ＫＭ*⊞θ⟦ⅉⅈ⟧»

```

Find all `X`s that are adjacent to a `*`.

```
»¿№ＫＡX⎚

```

If there are any `X`s left then they were disconnected so just clear the canvas.

```
«⎚¬⊙ζ∨⊖№ζι‹⁵Σ⪫ιω

```

Output a `-` only if all the discovered pieces are unique and have no more than 5 tiles.

---
Tags: code-golf, decision-problem, grid
---


# Question
Title: Check if three letters can form a "Godel-Escher-Bach cube"
This question is inspired by the cover of the book "Godel, Escher, Bach":

The challenge here is to write a function that tells if three given letters can produce a 3D sculpture that can be read from three sides.

For this exercise, the only letters you can use are 26 5px * 5px bitmaps:

Or in binary (A to Z):

```
01110  11110  01111  11110  11111  11111  11111  10001  11111  11111  10001  10000  10001  10001  01110  11110  01110  11110  01111  11111  10001  10001  10001  10001  10001  11111
10001  10001  10000  10001  10000  10000  10000  10001  00100  00100  10010  10000  11011  11001  10001  10001  10001  10001  10000  00100  10001  10001  10001  01010  01010  00010
10001  11110  10000  10001  11100  11110  10011  11111  00100  00100  11100  10000  10101  10101  10001  10001  10001  11111  01110  00100  10001  01010  10001  00100  00100  00100
11111  10001  10000  10001  10000  10000  10001  10001  00100  10100  10010  10000  10001  10011  10001  11110  10011  10010  00001  00100  10001  01010  10101  01010  00100  01000
10001  11110  01111  11110  11111  10000  11111  10001  11111  11100  10001  11111  10001  10001  01110  10000  01111  10001  11110  00100  01110  00100  01010  10001  00100  11111

```

The sculpture is formed by three letters in the following order:

* letter one on top,
* letter two on the left
* letter three on the right
* the bottom of letter one is bound to the top of the letter two.

Example:

Your function may accept as input three uppercase letters (three chars or three strings of one letter), and output a boolean (true/false or 0/1) telling if the corresponding sculpture can exist.

Example:

```
f("B","E","G") // true  (because if you "sculpt out" B on top + E on the left + G on the right, and watch the three sides of the sculpture, you'll see exactly B, E and G as they are defined)
f("B","G","E") // false (because if you "sculpt out" B on top + G on the left + E on the right, and watch the three sides of the sculpture, you won't see a complete G and a complete E. Their shapes bother each other)

```

NB: you may return true even if the sculpture contains "flying pixels" (cubes or group of cubes that are attached to nothing).

Standard loopholes apply.

More precisely, you can't use external input besides the three letters, and you can't hardcode the 17576 possible answers in your source code

Shortest answer in characters in any language wins!

Have fun :)

# Answer
> 16 votes
# Mathematica 423

I added a section called "How blocking works".

## Ungolfed

(\*The binary data of the alphabet are stored as a single string in `s`. `vars` imports it and converts it into an array.)

```
vars=IntegerDigits[#,10,5]&/@Transpose[ImportString[s,"Table"]];
get[char_]:=(ToCharacterCode[char]-64)[[1]];
cube=Flatten[Table[{i,j,k},{i,5},{j,5},{k,5}],2];

(* character slice along axis *)
slice[char_,layer_,axis_,bit_]:=Insert[(Reverse@#),layer,axis]&/@Position[Reverse@vars[[get[char]]],bit]

(* cuboid assembly  *)
charBlocks[{char_,axis_,bit_}]:=Flatten[Table[slice[char,k,axis,bit],{k,5}],1]

(* letters are those whose HOLES should be sculped out of the full cube *)
sculpturePoints[letters_(*{char_,axis_,bit_}*)]:=Complement[cube,Union[Join@@(charBlocks/@letters(*{char,axis,bit}*))]];

collapse[letters_(*{char_,axis_,bit_}*),axis_]:=Union[Reverse/@(Delete[#,axis]&/@sculpturePoints[letters(*{char,axis,bit}*)])](*/.{x_,y_}\[RuleDelayed] {6-x,y}*)

vQ[l_]:=collapse[l,3]==collapse[{l[[1]]},3]\[And]collapse[l,2]==collapse[{l[[2]]},2]\[And]collapse[l,1]==collapse[{l[[3]]},1]

validQ@l_:= vQ[{{l[[1]],3,0},{l[[2]],2,0},{l[[3]],1,0}}]

perspective[letts_,view_:1]:=
Graphics3D[{AbsolutePointSize[10],Cuboid/@sculpturePoints[letts]},
ImageSize-> 120,
ViewPoint-> Switch[view,1,{0,0,\[Infinity]},2,{0,-\[Infinity],0},3,{\[Infinity],0,0},4,Top,5,Front,6,Right,True,{0,0,\[Infinity]}],
PlotLabel-> Switch[view,1,"top orthogonal view",2,"front orthogonal view",3,"right orthogonal view",4,"top close-up view",5,"front close-up view",6,"right close-up view"],
ImagePadding->10]

```

---

## Example

Is the cube `{"B", "G", "E"}` valid? (i.e. Will the three letters project correctly onto the walls?)

```
validQ[{"B", "G", "E"}]

```

> False

**Illustrations**

The figures below show how BGE is rendered. The upper row of figures takes orthogonal perspectives, as if the viewer were positioned at infinite distances from the cube. The lower row shows how the blocks would look from close up. The 3D figures can be manually rotated to inspect precisely where the individual unit cubes are positioned.

A problem occurs with the letter "G". There is nothing connecting the serif to the rest of the letter.

```
pts = {{"B", 3, 0}, {"G", 2, 0}, {"E", 1, 0}}
GraphicsGrid@Partition[Table[perspective[pts, view], {view, 1, 6}], 3]

```

---

BEG, however, should work fine.

```
 validQ[{"B", "E", "G"}]

```

> True

```
pts2 = {{"B", 3, 0}, {"E", 2, 0}, {"G", 1, 0}}
GraphicsGrid@Partition[Table[perspective[pts2, view], {view, 1, 6}], 3]

```

---

## How Does Blocking Work?

Please excuse me if this seems obvious, but perhaps some folks will want to visualize how how letters interfere with each other, canceling their 3D pixels.

Let's follow what happens to the letter G, in the BGE cube rendering.

We'll be paying special attention to the voxel (3D pixel or unit cube) below. That is the pixel that disappears in the BGE cube. It is the pixel corresponding to Row 4, Column 5 in the bit array and in the corresponding array plot.

---

In the x y plane, the pixel corresponds to the gray disk at point (5,2). But because we're going to work in 3D, we need to consider the 5 positions in the *shaft* from (5,1,2) to (5,5,2). If any of those pixels survives sculpting by the letters B and E, we'll be able to see the pixel of interest in the 3D projection on the wall.

---

Letters interfere when pixels are removed from the solid block. In the left, the black arrow represents the carving out of pixels, corresponding to the bit at the bottom right; it has the value 0 for the letter B. Carving out removes the pixel at (5,1,2), along with those directly above and below it. Four pixels remain to be accounted for.

But as the right pane shows, the letter E sculpts out the remaining pixels of interest, (5,2,2) (5,3,2), (5,4,2) and (5,5,2). (This is due to the fact that the letter E has bits equal to 0 in the fourth row, from column 2 through column 5.) As a result, not a single pixel remains among those that were needed to ensure shade at point (5,2) on the far wall (for the letter G). Instead, there will be a bright spot corresponding to a hole in the letter G! The cube BGE is no good because it incorrectly renders G.

## Golfed 423 chars

The function `h` served the same role as `validQ` in the unGolfed code. The rendering function, `perspective`, is not included because it does not contribute to, and is not required by, the challenge.

```
x=Reverse;q=Flatten;
g@c_:=(ToCharacterCode[c]-64)[[1]];
r[{c_,a_,b_}]:=q[Table[Insert[(x@#),k,a]&/@Position[x@(IntegerDigits[#,10,5]&/@
Transpose[ImportString[s,"Table"]])[[g[c]]],b],{k,5}],1]
p@l_:=Complement[q[Table[{i,j,k},{i,5},{j,5},{k,5}],2],Union[Join@@(r/@l)]];
w[l_,a_]:=Union[x/@(Delete[#,a]&/@p[l])]
v@l_:=w[l,3]==w[{l[[1]]},3]\[And]w[l,2]==w[{l[[2]]},2]\[And]w[l,1]==w[{l[[3]]},1]

h@l_:= v[{{l[[1]],3,0},{l[[2]],2,0},{l[[3]],1,0}}]

```

# Answer
> 13 votes
# Prolog, ~~440~~, 414

```
:- encoding(utf8).
i(I) :- between(0,4,I).
h(T,L,R,X,Y,Z) :- i(X),i(Y),i(Z),I is 4-X,c(T,Z,I),c(L,Z,Y),c(R,X,Y).
f(T,L,R) :- forall((i(U),i(V),I is 4-V),((\+c(T,U,V);h(T,L,R,I,Y,U)),(\+c(L,U,V);h(T,L,R,X,V,U)),(\+c(R,U,V);h(T,L,R,U,V,Z)))).
c(C,X,Y) :- char_code(C,N),i(X),i(Y),Z is X+5*Y+25*(N-65),I is floor(Z/15),O is (Z mod 15),string_code(I,"䙎㹟䘑߯硁䙏縑ԁࠟя摟䠑䠑ᐑ粤Ⴟ䔅┉ё籁垑䙑曓䗱㩑䙏㡏晑䘞䕟㡞縐Ⴄ䙄㩑⩑䒪噑⩊䕤ᅱ粤ࢨ?",V),1 is (V-32)>>O/\1.

```

The program is called like this:

```
?- f('B','E','G').
true.
?- f('B','G','E').
false.

```

`Prolog` seemed to be a good choice, since it's easy to represent the problem in first order logic. Also `Prolog` provides potent functionality for solving this kind of problem.

**However, since the code is golfed, I guess I should add some explanation.**

### Mildly golfed version

```
:- encoding(utf8).
i(I) :- between(0,4,I).
t(C,X,Z) :- I is 4-X,c(C,Z,I).
l(C,Y,Z) :- c(C,Z,Y).
r(C,X,Y) :- c(C,X,Y).
h(T,L,R,X,Y,Z) :- i(X),i(Y),i(Z),t(T,X,Z),l(L,Y,Z),r(R,X,Y).
u(T,L,R) :- forall((i(U),i(V),I is 4-V,c(T,U,V)),h(T,L,R,I,Y,U)).
v(T,L,R) :- forall((i(U),i(V),c(L,U,V)),h(T,L,R,X,V,U)).
w(T,L,R) :- forall((i(U),i(V),c(R,U,V)),h(T,L,R,U,V,Z)).
f(T,L,R) :- u(T,L,R),v(T,L,R),w(T,L,R).
c(C,X,Y) :- char_code(C,N),i(X),i(Y),Z is X+5*Y+25*(N-65),I is floor(Z/15),O is (Z mod 15),string_code(I,"䙎㹟䘑߯硁䙏縑ԁࠟя摟䠑䠑ᐑ粤Ⴟ䔅┉ё籁垑䙑曓䗱㩑䙏㡏晑䘞䕟㡞縐Ⴄ䙄㩑⩑䒪噑⩊䕤ᅱ粤ࢨ?",V),1 is (V-32)>>O/\1.

```

The coordinates corresponding to the pixels on each side of the dice can be easily converted to a 3D coordinate system. I use `T`,`L` and `R` for top(1), left(2) and right(3) side. `u` and `v` are used for the coordinates in the images:

* **T**: `(u,v) -> (4-v, ?, u)`
* **L**: `(u,v) -> (?, v, u)`
* **R**: `(u,v) -> (u, v, ?)`

The results for each active (i.e. black) pixel are combined to a set of "3D-pixels" that can be acitvated without changing the look of the object from this side. The intersection of the sets for each side are all 3D-pixels, that can be activated without adding pixels, that would obstruct the view (i.e. looking from at least one side there would be a pixel that shouldn't be there).

All that remains is to check for each side, if there is a pixel in the intersection that blocks the view, where it's necessary.

This leads to the predicates in the program:

* **f**: does the final check; takes the letters at the top, the left side and the right side
* **u**, **v** and **w**: do the checks, if for every pixel active on the side there is a 3D-pixel in the intersection, that blocks the view
* **h**: checks, for the existence of a pixel in the intersection
* **t**,**l**,**r**: checks, if a 3D-pixel can be blocked from top, left and right side.
* **c**: checks for the pixel in the image of a letter. The string in there may look a bit strange, but it's only a compact way to store the image data. It's simply a character sequence with the following values(hex notation):

```
[464e,3e5f,4611,7ef,7841,464f,7e11,501,81f,44f,645f,4811,4811,1411,7ca4,10bf,4505,2509,451,7c41,5791,4651,66d3,45f1,3a51,464f,384f,6651,461e,455f,385e,7e10,10a4,4644,3a51,2a51,44aa,5651,2a4a,4564,1171,7ca4,8a8,3f]

```

Each of these characters stores the data for 3 pixel rows in letter image(s) (=15 pixel). The pixels are also reordered so that the data is stored at one location and not divided across multiple rows, like the data of the OP.

## Mathematic formulation

### Input data

### Conversion from pixel in one char to set of 3D-pixels that obstruct the view for this pixel

### Pixels that can be added safely(without obstructing the view in the wrong place)

### Checks for each side, that the pixels that need to be obstructed can be obstructed safely

### Combinatin of checks for each side

# Answer
> 10 votes
# J - ~~223~~ ~~197~~ 191 char

A function taking a three char list as argument.

```
(_5#:\".'1b',"#:'fiiifalllvhhhheehhhvhhllvgkkkvnlhhvv444vhhvhhggvhjha44v1111vv848vv248vehhheciiivfjhhedmkkvilll9ggvggu111uo616ou121uha4ahg878ghpljh')((-:0<+/"1,+/"2,:+/)*`(*"1/)/)@:{~_65+3&u:

```

This golf relies heavily on a powerful feature of J called *rank*, which gives us the "sculpt out" and "watch side of" operations almost for free. To oversimplify it a bit, rank refers to the dimensionality of a noun or of a verb's natural arguments.

J has multidimensional arrays, and it is obvious that, say, a 3D array can be interpreted as a single 3D array, or as a list of matrices, or a 2D array of vectors, or a 3D array of scalars. So every operation in J can have its application controlled w.r.t. how to be spread over the argument. Rank 0 means apply on the scalars, rank 1 means apply on the vectors, and so on.

```
   1 + 2 + 3 + 4  NB. add these things together
10
   +/ 1 2 3 4     NB. sum the list by adding its items together
10
   i. 3 4         NB. 2D array, with shape 3-by-4
0 1  2  3
4 5  6  7
8 9 10 11
   +/"2 i. 3 4    NB. add the items of the matrix together
12 15 18 21
   0 1 2 3 + 4 5 6 7 + 8 9 10 11    NB. equivalent
12 15 18 21
   +/"1 i. 3 4    NB. now sum each vector!
6 22 38
   +/"0 i. 3 4    NB. now sum each scalar!
0 1  2  3
4 5  6  7
8 9 10 11

```

This becomes very powerful when you introduce dyadic (two-argument) functions, because if the shapes of the two arguments (after accounting for rank) are agreeable, J will do some implicit looping:

```
   10 + 1             NB. scalar addition
11
   10 20 30 + 4 5 6   NB. vector addition, pointwise
14 25 36
   10 + 4 5 6         NB. looping!
14 15 16
   10 20 + 4 5 6      NB. shapes do not agree...
|length error
|   10 20    +4 5 6

```

When all your shapes are agreeable and you can specify the rank yourself, there are many ways to combine arguments. Here we show off some of the ways that you can multiply a 2D matrix and a 3D array.

```
   n =: i. 5 5
   n
 0  1  2  3  4
 5  6  7  8  9
10 11 12 13 14
15 16 17 18 19
20 21 22 23 24
   <"2 n *"2 (5 5 5 $ 1)  NB. multiply by 2-cells
+--------------+--------------+--------------+--------------+--------------+
| 0  1  2  3  4| 0  1  2  3  4| 0  1  2  3  4| 0  1  2  3  4| 0  1  2  3  4|
| 5  6  7  8  9| 5  6  7  8  9| 5  6  7  8  9| 5  6  7  8  9| 5  6  7  8  9|
|10 11 12 13 14|10 11 12 13 14|10 11 12 13 14|10 11 12 13 14|10 11 12 13 14|
|15 16 17 18 19|15 16 17 18 19|15 16 17 18 19|15 16 17 18 19|15 16 17 18 19|
|20 21 22 23 24|20 21 22 23 24|20 21 22 23 24|20 21 22 23 24|20 21 22 23 24|
+--------------+--------------+--------------+--------------+--------------+
   <"2 n *"1 (5 5 5 $ 1)  NB. multiply by vectors
+---------+---------+--------------+--------------+--------------+
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
|0 1 2 3 4|5 6 7 8 9|10 11 12 13 14|15 16 17 18 19|20 21 22 23 24|
+---------+---------+--------------+--------------+--------------+
   <"2 n *"0 (5 5 5 $ 1)  NB. multiply by scalars
+---------+---------+--------------+--------------+--------------+
|0 0 0 0 0|5 5 5 5 5|10 10 10 10 10|15 15 15 15 15|20 20 20 20 20|
|1 1 1 1 1|6 6 6 6 6|11 11 11 11 11|16 16 16 16 16|21 21 21 21 21|
|2 2 2 2 2|7 7 7 7 7|12 12 12 12 12|17 17 17 17 17|22 22 22 22 22|
|3 3 3 3 3|8 8 8 8 8|13 13 13 13 13|18 18 18 18 18|23 23 23 23 23|
|4 4 4 4 4|9 9 9 9 9|14 14 14 14 14|19 19 19 19 19|24 24 24 24 24|
+---------+---------+--------------+--------------+--------------+

```

You'll notice that this doesn't actually carve in the letters in the orientation the question asks for, it just writes them in however is convenient for rank logic. Unless we reverse or rotate the letters before we apply them, it won't work right. But correcting things like that would take up precious characters, so instead we'll encode the letters such that, when J carves them in naturally, *some* triple of faces will be in the correct orientations and relative positions. It turns out the shortest solution is to rotate all the letterforms a quarter-turn counterclockwise. Considering J's third dimension to represent the front-to-back axis, the crude diagram below shows why this scheme works.

Figure A: The three sides of the cube that J carves into. Figure B: The three sides which have the letters oriented like the question asks.

This choice in encoding saves 12 characters over the previous method, and makes the whole thing neater. The actual golf creates the cube out of the `"1` and `"2` carves with some funky logic, due to an unrelated optimization.

Then we have to check the faces. Since we encode the block as 1s and 0s, we can just sum along each axis in the way we want (these are the `+/"1`, `+/"2`, and `+/` bits), adjust to booleans (`0<`), and then compare them all directly to the original 90°-turned-letters.

The compression scheme encodes each 5px row of each letter as the base 32 representation of a binary number. By exploiting a number of syntactic sugars and operator overloadings, `".'1b',"#:` is the shortest way to turn the list of characters into base 36 numbers. Well, technically, base 32, but J thinks it's unary, so who's counting?

Usage is below. Note that strings are character arrays in J, so a three item list `'A','B','C'` can be written `'ABC'` for short. Also, booleans are 1/0.

```
   NB. can be used inline...
   (_5#:\".'1b',"#:'fiiifalllvhhhheehhhvhhllvgkkkvnlhhvv444vhhvhhggvhjha44v1111vv848vv248vehhheciiivfjhhedmkkvilll9ggvggu111uo616ou121uha4ahg878ghpljh')((-:0<+/"1,+/"2,:+/)*`(*"1/)/)@:{~_65+3&u:'BEG'
1
   NB. or assigned to a name
   geb=:(_5#:\".'1b',"#:'fiiifalllvhhhheehhhvhhllvgkkkvnlhhvv444vhhvhhggvhjha44v1111vv848vv248vehhheciiivfjhhedmkkvilll9ggvggu111uo616ou121uha4ahg878ghpljh')((-:0<+/"1,+/"2,:+/)*`(*"1/)/)@:{~_65+3&u:
   geb 'BGE'
0

```

# Answer
> 5 votes
# Python, ~~687~~ ~~682~~ 671

```
import itertools as t,bz2
s=range(5)
c=dict([(i,1)for i in t.product(*3*[s])])
z=dict([(chr(i+65),[map(int,bz2.decompress('QlpoOTFBWSZTWXndUmsAATjYAGAQQABgADABGkAlPJU0GACEkjwP0TQlK9lxsG7aomrsbpyyosGdpR6HFVZM8bntihQctsSiOLrWKHHuO7ueAyiR6zRgxbMOLU2IQyhAEAdIJYB0ITlZwUqUlAzEylBsw41g9JyLx6RdFFDQEVJMBTQUcoH0DEPQ8hBhXBIYkXDmCF6E/F3JFOFCQed1Saw='.decode('base64')).split('\n')[j].split()[i])for j in s])for i in range(26)])
def m(a,g):
 for e in c:c[e]&=g[e[a]][e[a-2]]
def f(a):
 g=map(list,[[0]*5]*5)
 for e in c:g[e[a]][e[a-2]]|=c[e]
 return g
r=lambda g:map(list,zip(*g)[::-1])
def v(T,L,R):T,L,R=r(r(z[T])),r(z[L]),z[R];m(1,T);m(2,L);m(0,R);return(T,L,R)==(f(1),f(2),f(0))

```

Call with `v`:

```
v('B','E','G') => True
v('B','G','E') => False

```

Everything below is from my previous ungolfed version which includes helpful drawing functions. Feel free to use it as a jumping off point.

```
import string as s
import itertools as t

az = """01110  11110  01111  11110  11111  11111  11111  10001  11111  11111  10001  10000  10001  10001  01110  11110  01110  11110  01111  11111  10001  10001  10001  10001  10001  11111
10001  10001  10000  10001  10000  10000  10000  10001  00100  00100  10010  10000  11011  11001  10001  10001  10001  10001  10000  00100  10001  10001  10001  01010  01010  00010
10001  11110  10000  10001  11100  11110  10011  11111  00100  00100  11100  10000  10101  10101  10001  10001  10001  11111  01110  00100  10001  01010  10001  00100  00100  00100
11111  10001  10000  10001  10000  10000  10001  10001  00100  10100  10010  10000  10001  10011  10001  11110  10011  10010  00001  00100  10001  01010  10101  01010  00100  01000
10001  11110  01111  11110  11111  10000  11111  10001  11111  11100  10001  11111  10001  10001  01110  10000  01111  10001  11110  00100  01110  00100  01010  10001  00100  11111""".split('\n')

dim = range(len(az))
az = dict([(c, [map(int, az[j].split()[i]) for j in dim]) for i, c in enumerate(s.uppercase)])
cube = dict([(i, 1) for i in t.product(*3*[dim])])

def mask(axis, grid):
    for c in cube:
        if not grid[c[axis]][c[axis - 2]]:
            cube[c] = 0

def face(axis):
    grid = [[0 for j in dim] for i in dim]
    for c in cube:
        if cube[c]:
            grid[c[axis]][c[axis - 2]] = 1
    return grid

def rot(grid):
    return map(list, zip(*grid)[::-1])

def draw(grid, filled='X', empty=' '):
    s = ''
    for y in dim:
        for x in dim:
            s += filled if grid[y][x] else empty
        s += '\n'
    print s

def drawAll():
    print 'TOP:\n'
    draw(rot(rot(face(1))))
    print 'LEFT:\n'
    draw(rot(rot(rot(face(2)))))
    print 'RIGHT:\n'
    draw(face(0))

def valid(top, left, right):
    top, left, right = rot(rot(az[top])), rot(az[left]), az[right]
    mask(1, top)
    mask(2, left)
    mask(0, right)
    return top == face(1)and left == face(2) and right == face(0)

letters = 'BEG'

if valid(*letters):
    print letters, 'is valid.\n'
else:
    print letters, 'is not valid!\n'

drawAll()

```

Call `valid` to run it:

```
valid('B', 'E', 'G') #returns True
valid('B', 'G', 'E') #returns False

```

Right now the code is setup to test the validity of `B E G` and print out the resulting faces:

```
BEG is valid.

TOP:

XXXX
X   X
XXXX
X   X
XXXX

LEFT:

XXXXX
X
XXX
X
XXXXX

RIGHT:

XXXXX
X
X  XX
X   X
XXXXX

```

Running it on `B G E` we can see that the G is incorrect:

```
BGE is not valid!

TOP:

XXXX
X   X
XXXX
X   X
XXXX

LEFT:

XXXXX
X
X  XX
X
XXXXX

RIGHT:

XXXXX
X
XXX
X
XXXXX

```

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

```
x y z←(⎕A⍳⍞)⌷¨⊂26 5 5⍴(8⍴2)⊤⎕AV⍳'5∘⍉⍉c∨wÌþ∩⍀ýFó  â⍒⍪┤ÌÙÍ⊃?>áóU│yEå≥∧+├Û└KEÐ┐⌹;⍉ùigë/⋄⍪,ËwÙ4○$⊣7×c⍺þS¢|⍋îÜ⍀â:b⌷Î'
(x,y,z)≡(∨⌿,∨⌿⍤2,∨/)x×⍤2⊢z∘.×⍤1⊢y

```

Try it online!

A full program that takes three uppercase letters from stdin and prints 0 (false) or 1 (true) to stdout.

We already have an answer in J which has an excellent primer on multi-dimensional arrays and function rank. This answer uses the same concept. (Plus an obvious advantage that we can efficiently encode the binary arrays using the single-byte character encoding.)

### How it works

```
⍝ Extract the three bit matrices
x y z←(⎕A⍳⍞)⌷¨⊂26 5 5⍴(8⍴2)⊤⎕AV⍳'5∘⍉⍉c∨wÌþ∩⍀ýFó  â⍒⍪┤ÌÙÍ⊃?>áóU│yEå≥∧+├Û└KEÐ┐⌹;⍉ùigë/⋄⍪,ËwÙ4○$⊣7×c⍺þS¢|⍋îÜ⍀â:b⌷Î'
                            ⎕AV⍳'...'  ⍝ Char value of each char w.r.t. the code page
                      (8⍴2)⊤  ⍝ Convert each number to 8 bits, making 8-row matrix
               26 5 5⍴  ⍝ Take the bits and form 26×5×5 brick
      (⎕A⍳⍞)⌷¨⊂  ⍝ Take 3-char input and extract the corresponding 5×5 matrices
x y z←  ⍝ Assign to three variables

(x,y,z)≡(∨⌿,∨⌿⍤2,∨/)x×⍤2⊢z∘.×⍤1⊢y
                         z∘.×⍤1⊢y  ⍝ Combine front and right faces
                                   ⍝ so that three dimensions are oriented naturally
                    x×⍤2⊢  ⍝ Combine the top face
        (∨⌿,∨⌿⍤2,∨/)  ⍝ Compute the top, front, and right views of the pixels
(x,y,z)≡  ⍝ Check if they all match the original faces

```

# Answer
> 1 votes
# Python 3 + numpy, 327C

```
from numpy import*
B=hstack([ord(x)>>i&1for x in'옮弟ჹ羂옱쏷）ជ࿂︹缘龌ℿ쓥剴ℌᾄ起츱ꎚㆋឺ௣옮忬⧼ﯠႄ挒⺌ꕆ豈ꪱ袨冊䈑∾Ϣ'for i in range(16)])[:-6].reshape(26,5,5)
T=transpose
def f(*X):
 A=ones((5,5,5));F=list(zip([A,T(A,(1,0,2)),T(fliplr(A),(2,0,1))],[B[ord(x)-65]for x in X]))
 for r,f in F:r[array([f]*5)==0]=0
 return all([all(r.sum(0)>=f)for r,f in F])

```

This golf solution need an external library, numpy, which is quite popular so I think it's fine to use it.

The unicode string is in 41 chars, while the same thing in @fabian's prolog answer is 44.

The most interesting here is that the indexing of numpy array. In `a[ix]`, `ix` can be an boolean array with the same shape as `a`. It's the same as saying `a[i, j, k] where ix[i, j, k] == True`.

## Ungolfed Version

```
import numpy as np
table = '옮弟ჹ羂옱쏷）ជ࿂︹缘龌ℿ쓥剴ℌᾄ起츱ꎚㆋឺ௣옮忬⧼ﯠႄ挒⺌ꕆ豈ꪱ袨冊䈑∾Ϣ'

def expand_bits(x):
    return [ord(x) >> i & 1 for i in range(16)]

# B.shape = (26, 5, 5), B[i] is the letter image matrix of the i(th) char
B = np.hstack([expand_bits(x) for x in table])[:-6].reshape(26, 5, 5)

def f(*chars):
    """
    cube:    ----------   axis:
            /         /|      --------->2
           /   1     / |     /|
          /         /  |    / |
         /         /   |   /  |
        |---------|  3 |  v   |
        |         |    /  1   |
        |    2    |   /       v
        |         |  /        0
        |         | /
        -----------
    """
    cube = np.ones((5, 5, 5))
    cube_views = [
        cube,
        cube.transpose((1, 0, 2)),  # rotate to make face 2 as face 1
        np.fliplr(cube).transpose(2, 0, 1),  # rotate to make face 3 as face 1
    ]
    faces = [B[ord(char) - ord('A')] for char in chars]
    # mark all white pixels as 0 in cube
    for cube_view, face in zip(cube_views, faces):
        # extrude face to create extractor
        extractor = np.array([face] * 5)
        cube_view[extractor == 0] = 0

    return np.all([
        # cube_view.sum(0): sum along the first axis
        np.all(cube_view.sum(0) >= face)
        for cube_view, face in zip(cube_views, faces)
    ])

```

## Script to compress table

```
import numpy as np

def make_chars():
    s = """
01110  11110  01111  11110  11111  11111  11111  10001  11111  11111  10001  10000  10001  10001  01110  11110  01110  11110  01111  11111  10001  10001  10001  10001  10001  11111
10001  10001  10000  10001  10000  10000  10000  10001  00100  00100  10010  10000  11011  11001  10001  10001  10001  10001  10000  00100  10001  10001  10001  01010  01010  00010
10001  11110  10000  10001  11100  11110  10011  11111  00100  00100  11100  10000  10101  10101  10001  10001  10001  11111  01110  00100  10001  01010  10001  00100  00100  00100
11111  10001  10000  10001  10000  10000  10001  10001  00100  10100  10010  10000  10001  10011  10001  11110  10011  10010  00001  00100  10001  01010  10101  01010  00100  01000
10001  11110  01111  11110  11111  10000  11111  10001  11111  11100  10001  11111  10001  10001  01110  10000  01111  10001  11110  00100  01110  00100  01010  10001  00100  11111
""".strip().split('\n')
    bits = np.zeros((26, 5, 5), dtype=np.bool)
    for c_id in range(26):
        for i in range(5):
            for j in range(5):
                bits[c_id, i, j] = s[i][j + c_id * 7] == '1'
    bits = np.hstack([bits.flat, [0] * 7])
    bytes_ = bytearray()
    for i in range(0, len(bits) - 8, 8):
        x = 0
        for j in range(8):
            x |= bits[i + j] << j
        bytes_.append(x)
    chars = bytes_.decode('utf16')
    return chars

```

---
Tags: code-golf, 3d
---


# Question
Title: Determine if a substructure is present in a chemical structure using SMILES string (substructure fingerprint)
A SMILES (Simplified molecular-input line-entry system) string is a string that represents a chemical structure using ASCII characters. For example, water (\\$H\_2O\\$) can be written in SMILES as `H-O-H`.

However, for simplicity, the single bonds (`-`) and hydrogen atoms (`H`) are frequently omitted. Thus, a molecules with only single bonds like *n*-pentane (\\$CH\_3CH\_2CH\_2CH\_2CH\_3\\$) can be represented as simply `CCCCC`, and ethanol (\\$CH\_3CH\_2OH\\$) as `CCO` or `OCC` (which atom you start from does not matter).

n-pentane:

ethanol:

In SMILES, double bonds are represented with `=` and triple bonds with `#`. So ethene:

can be represented as `C=C`, and hydrogen cyanide:

can be represented as `C#N` or `N#C`.

SMILES uses parentheses when representing branching:

Bromochlorodifluoromethane can be represented as `FC(Br)(Cl)F`, `BrC(F)(F)Cl`, `C(F)(Cl)(F)Br`, etc.

For rings, atoms that close rings are numbered:

First strip the `H` and start from any `C`. Going round the ring, we get `CCCCCC`. Since the first and last `C` are bonded, we write `C1CCCCC1`.

Use this tool: https://pubchem.ncbi.nlm.nih.gov/edit3/index.html to try drawing your own structures and convert them to SMILES, or vice versa.

**Task**

Your program shall receive two SMILES string. The first one is a molecule, the second is a substructure (portion of a molecule). The program should return `true` if the substructure is found in the molecule and `false` if not. For simplicity, only above explanation of SMILES will be used (no need to consider stereochemistry like cis-trans, or aromaticity) and the only atoms will be:

* `O`
* `C`
* `N`
* `F`

Also, the substructure do not contain `H`.

**Examples**

```
CCCC C
true

CCCC CC
true

CCCC F
false

C1CCCCC1 CC
true

C1CCCCC1 C=C
false

COC(C1)CCCC1C#N C(C)(C)C // substructure is a C connected to 3 other Cs
true

COC(C1)CCCCC1#N COC1CC(CCC1)C#N // SMILES strings representing the same molecule
true

OC(CC1)CCC1CC(N)C(O)=O CCCCO
true

OC(CC1)CCC1CC(N)C(O)=O NCCO
true

OC(CC1)CCC1CC(N)C(O)=O COC
false

```

Shortest code wins. Refrain from using external libraries.

# Answer
> 3 votes
# Mathematica, 31 bytes

```
MoleculeContainsQ@@Molecule/@#&

```

Takes input as a list of 2 strings (the source and the pattern molecules).

As you could guess, this checks if the first molecule (parsed via `Molecule`) contains the second one by using the `MoleculeContainsQ` function.

This doesn't seem to work in the online interpreter on TIO; I'm not sure what I am doing wrong. It works on my local machine, though. Of course, this is not using an external library: it's completely built-in functionality!

---
Tags: code-golf, string, chemistry
---


title: Calculate the vector component

text:
# Question
Title: Calculate the vector component
## Challenge

Assume two vectors \\$\mathbf{a} = (a\_1,a\_2,\cdots,a\_n)\\$ and \\$\mathbf{b} = (b\_1,b\_2,\cdots,b\_n)\\$ are given in an \\$n\\$-dimensional space, where at least one of \\$b\_1,\cdots,b\_n\\$ is nonzero. Then \\$\mathbf{a}\\$ can be uniquely decomposed into two vectors, one being a scalar multiple of \\$\mathbf{b}\\$ and one perpendicular to \\$\mathbf{b}\\$:

$$ \mathbf{a} = \mathbf{b}x + \mathbf{b^\perp}\text{, where }\mathbf{b^\perp} \cdot \mathbf{b}=0. $$

Given \\$\mathbf{a}\\$ and \\$\mathbf{b}\\$ as input, find the value of \\$x\\$.

This can be also thought of as the following: Imagine a line passing through the origin and the point \\$\mathbf{b}\\$. Then draw a perpendicular line on it that passes through the point \\$\mathbf{a}\\$, and denote the intersection \\$\mathbf{c}\\$. Finally, find the value of \\$x\\$ that satisfies \\$\mathbf{c}=\mathbf{b}x\\$.

You can use an explicit formula too (thanks to @xnor), which arises when calculating the projection:

$$ x=\frac{\mathbf{a} \cdot \mathbf{b}}{\mathbf{b} \cdot \mathbf{b}} $$

Standard rules apply. The shortest code in bytes wins.

## Example

Here is an example in 2D space, where `a=(2,7)` and `b=(3,1)`. Observe that `(2,7) = (3.9,1.3) + (-1.9,5.7)` where `(3.9,1.3)` is equal to `1.3b` and `(-1.9,5.7)` is perpendicular to `b`. Therefore, the expected answer is `1.3`.

## Test cases

```
a         b          answer
(2,7)     (3,1)      1.3
(2,7)     (-1,3)     1.9
(3,4,5)   (0,0,1)    5
(3,4,5)   (1,1,1)    4
(3,4,5)   (1,-1,-1)  -2
(3,4,5,6) (1,-2,1,2) 1.2

```

# Answer
# APL (Dyalog Unicode), 1 byteSBCS

Check all test cases! When used dyadically, `X ⌹ Y` solves the least squares* system \\$Ya = X\\$ for a result \\$a\\$ of the appropriate shape, e.g.:

* if \\$Y\\$ is a matrix and \\$X\\$ is a vector, we try to solve a linear system of equations.
* if \\$Y\\$ and \\$X\\$ are matrices, we compute \\$Y\\$'s (pseudo-)inverse and multiply it on the left of \\$X\\$.
* when both \\$X\\$ and \\$Y\\$ are vectors, the least squares formulation reduces to what we want, namely

$$\frac{X \cdot Y}{||Y||^2}$$

**the least squares system \\$Ya = X\\$* can be understood as "what should \\$a\\$ be such that \\$Ya\\$ is as close as can be to \\$X\\$?", where closeness is measured with the usual L2 distance.
> 25 votes

# Answer
# Haskell, ~~33~~ 32 bytes

-1 byte thanks to @xnor!

```
(!)b=sum.zipWith(*)b
a#b=a!b/b!b

```

Try it online!

---

# Coconut, 35 bytes

```
(a,b)->p(a,b)/p(b,b)
p=sum..map$(*)

```

Try it online!
> 8 votes

# Answer
# , 24 bytes

```
function(a,b)a%*%b/b%*%b

```

Try it online!
> 4 votes

# Answer
# Python 3 \+ `numpy`, 20 bytes

```
lambda a,b:a@b/(b@b)

```

Try it online!
> 4 votes

# Answer
# MATL, 2 bytes

```
Y\

```

Try it online!

Least squares approach such as used in the APL answer.
> 4 votes

# Answer
# Jelly, ~~6~~ 5 bytes

```
ḋ`÷@ḋ

```

Try it online!

Simple translation of the given formula. Takes \\$\mathbf{b}\\$ as the left argument and \\$\mathbf{a}\\$ as the right argument.

```
ḋ        The dot product of b and
 `       itself,
  ÷@     dividing
    ḋ    the dot product of b and a.

```
> 2 votes

# Answer
# Charcoal, ~~21~~ 18 bytes

```
Ｆ²⊞υΣＥＡ×κ§θλＩ∕⊟υ⊟υ

```

Try it online! Link is to verbose version of code. Takes inputs in the order `b`, `a`. Explanation:

```
Ｆ²

```

Repeat twice...

```
⊞υΣＥＡ×κ§θλ

```

Input a vector, take its dot product with `b` and push the result to the predefined empty list.

```
Ｉ∕⊟υ⊟υ

```

Retrieve the dot products and take their quotient.
> 2 votes

# Answer
# C (gcc), ~~84~~ ~~74~~ 73 bytes

Saved 10 bytes thanks to dingledooper!!!

Saved a byte thanks to ceilingcat!!!

```
float f(a,b,n)float*a,*b;{float x,y;for(;n--;y+=*b**b++)x+=*a++**b;x/=y;}

```

Try it online!

Inputs two pointers to vectors \\$a,b\\$ and their dimension \\$n\\$ and returns their component..

Uses given formula:

$$x = \frac{a\_0\cdot b\_0 + a\_1\cdot b\_1 + \dots + a\_{n-1}\cdot b\_{n-1}}{b\_0^2 + b\_1^2 + \dots + b\_{n-1}^2}$$
> 2 votes

# Answer
# 05AB1E, 6 bytes

```
*OInO/

```

Try it online or verify all test cases.

Implements the given formula:

$$x = \frac{a\_1\times b\_1 + a\_2\times b\_2 + \dots + a\_n\times b\_n}{b\_1^2 + b\_2^2 + \dots + b\_n^2}$$

**Explanation:**

```
*       # Multiply the values at the same indices in the two (implicit) input-lists
 O      # Sum this list
  I     # Push the second input-list again
   n    # Square each value
    O   # Take the sum of that
     /  # And divide the two values
        # (after which the result is output implicitly)

```
> 2 votes

# Answer
# Wolfram Language (Mathematica), 9 bytes

```
#.#2/#.#&

```

Try it online! Pure function. Takes **b** followed by **a** as input and returns a rational number as output. It just directly uses Mathematica's notation for the dot product.
> 2 votes

# Answer
# Fortran \>= 95, 66 bytes

Taking advantage of implicit typing for the return type.

```
function x(a,b)
real a(:),b(:)
x=dot_product(a,b)/norm2(b)**2
end

```
> 2 votes

# Answer
# \[R\], 22 bytes

Taking advantage of a resident regression function, `lm`

```
function(a,b)lm(a~b-1)

```

Try it online!
> 1 votes

# Answer
# Java 10, ~~84~~ 74 bytes

```
a->b->{float A=0,B=0;int i=0;for(var t:b){A+=a[i++]*t;B+=t*t;}return A/B;}

```

Try it online.
> 0 votes

# Answer
# Japt v2.0a0, 9 bytes

```
í*V x÷Vx²

```

Try it
> 0 votes

---
Tags: code-golf, math, geometry
---


# Question
Title: Remove each integer from a string and multiply them all!
# Goal:

* Get every integer from the string (not a number, but integer)
* Multiply them
* Output the result

# Input:

*5 kilograms of food eaten, 10 liters of water drank, 20 plates dirty, 40 mugs dirty, and only 3 people acted!*

# Output:

*120000*

# How:

*Result was 5 * 10 * 20 * 40 * 3*

# What do we count as an integer:

# General:

* If integer has a symbol BEFORE of AFTER the int, only take the number without symbols. `-335 or 335+` are 335 anyways.
* If integer has a symbol like this: `35:3`, don't take it. `35 : 3` is available though, and considered as 2 integers.

# Detailed:
* 35/3 aren't two integers, skip this
* 35.3 is not an integer, skip this
* 35:3, 35\*3, 3e3, etc. aren't ints, skip them as well
* 353 is an integer
* 35 3 are two integers
* 353. is an integer
* 353?, 353!, etc. are integers
* -353 is an integer, but you only claim 353 and skip "-".
* +353 is the same case as upper

# Requirements:
* Select any language you want
* The program should contain as little bytes as possible
* You should tell us the language (if it's, like, exotic, link it like this)
* Please, upload the code to Try It Online services like this
* Count the bytes using special services like this
* It would be fine if you'd explain your code!

# Scoring:

Less bytes program wins! The end is 20th of June, you guys have a week

# Answer
# perl -pl, 64 bytes

```
s!\D+|\d+(?:[.:^e/]\d+)+|(\d+)!$1?"*".(0+$1):""!aeg;$_=eval"1$_"

```

Try it online!

Ignores anything which isn't a digit, or multiple sequences of digits separated by `/`, `.`, `e`, `:`, or `^`. Sequences of digits are replaced by themselves, prepended with \*. The result, we eval, after predending 1. There's a tiny bit of hackery going to deal with numbers starting with 0s -- we don't want them be interpreted as octal numbers.

Reads lines from `STDIN`, writes the result to `STDOUT`.
> 1 votes

# Answer
# Red, 109 bytes

```
func[s][p: 1 d: charset"0123456789"parse s[any[to d copy t[any d ahead[" "|"!"|"?"]](p: p * to p t)| skip]]p]

```

Try it online!
> 4 votes

---
Tags: code-golf, string, integer
---


# Question
Title: Generate self-avoiding loops of a specific length
This question is a sequel to this one, working in the opposite direction.

For a reminder of terminology, the letters `L`, `R`, `U`, and `D` represent one-unit movement of a robot on the coordinate plane in the directions left, right, up, and down respectively. Given a positive even integer `n`, generate and print *all* sequences of `L`, `R`, `U`, and `D` of length `n` that result in a closed loop that does not intersect itself. In other words, when the robot follows the instructions in the sequence of letters, it must visit a new cell with every movement until it completes the loop and returns to the original cell.

Any of the generally accepted output formats for arrays and strings are allowed. The elements printed must be in alphabetical order. It can be assumed that the input is always a positive even integer.

```
Test cases

2 -> {"DU", "LR", "RL", "UD"}
4 -> {"DLUR", "DRUL", "LDRU", "LURD", "RDLU", "RULD", "ULDR", "URDL"}
6 -> {"DDLUUR", "DDRUUL", "DLLURR", "DLUURD", "DRRULL", "DRUULD", "LDDRUU", "LDRRUL", "LLDRRU", "LLURRD", "LURRDL", "LUURDD", "RDDLUU", "RDLLUR", "RRDLLU", "RRULLD", "RULLDR", "RUULDD", "ULDDRU", "ULLDRR", "URDDLU", "URRDLL", "UULDDR", "UURDDL"}

```

This is a standard code golf challenge, where the shortest answer wins. Standard rules apply.

# Answer
# Jelly, 19 bytes

```
“ḅḍʂ»ðṗẆċⱮṚƑ¥ƇḢɗƑƇ⁸

```

A monadic Link accepting a non negative integer which yields a list of lists of characters.

**Try it online!**

### How?

Much the same as Zgarb's Husk answer...

```
“ḅḍʂ»ðṗẆċⱮṚƑ¥ƇḢɗƑƇ⁸ - Link: integer, L
“ḅḍʂ»               - compressed string "URLD"
     ð              - start a new dyadic chain, f("URLD", L)
      ṗ             - ("URLD") Cartesian power (L) -> all length L strings using "URLD"
                 Ƈ  - keep those (s in those strings) for which:
                Ƒ   -   is invariant under?:
                  ⁸ -     use chain's left argument, "URLD", as the right argument of:
               ɗ    -       last three links as a dyad, f(s, "URLD"):
       Ẇ            -         all sublists (s)
             Ƈ      -         keep those (b in sublists(s)) for which:
            ¥       -           last two links as a dyad, f(b, "URLD"):
         Ɱ          -             map across (for c in "URLD") with f(b, c):
        ċ           -               count
           Ƒ        -             is invariant under?:
          Ṛ         -               reverse - i.e. count('U')=count('D')
                                               and count('R')=count('L')
              Ḣ     -         head (iff the only sublist with equal counts is the string
                                    itself then this will be that same string)

```
> 1 votes

# Answer
# APL (Dyalog Extended), 39 bytes

```
{∧'LURD'⊇⍨m⌿⍨(⍲∘⍧=⊢/)⍤1+\0J1*m←⍉4⊤⍳4*⍵}

```

Try it online!

The output is a matrix of characters, one path on a line.

### How it works

```
{∧'LURD'⊇⍨m⌿⍨(⍲∘⍧=⊢/)⍤1+\0J1*m←⍉4⊤⍳4*⍵}  ⍝ Input ⍵←n

m←⍉4⊤⍳4*⍵  ⍝ A matrix of all length-n combinations of 0..3
     ⍳4*⍵  ⍝ 0..4^n-1
   4⊤      ⍝ Convert each to base 4 (each goes to a column)
m←⍉        ⍝ Transpose and assign to m

∧'LURD'⊇⍨m⌿⍨(⍲∘⍧=⊢/)⍤1+\0J1*m
                        0J1*m  ⍝ Power of i (directions on complex plane)
                      +\       ⍝ Cumulative sum; the path of the robot
            (      )⍤1  ⍝ Test each row:
                 ⊢/     ⍝   the last number (real+imag is always even)
                =       ⍝   equals
             ⍲∘⍧        ⍝   NAND of the nub-sieve
                        ⍝   (0 if all numbers are unique, 1 otherwise)
                        ⍝ The condition is satisfied only if both are 0
         m⌿⍨  ⍝  Extract the rows that satisfy the above
 'LURD'⊇⍨     ⍝  Index each number into the string 'LURD'
∧             ⍝  Ascending sort

```
> 8 votes

# Answer
# Python 2, ~~119 106~~ 104 bytes

```
def f(n,s="",p=0,*v):
 if p==n<1:print s
 for d in"DLRU":p in v or 0<n<f(n-1,s+d,p+1j**(ord(d)%15),p,*v)

```

Try it online!

---

Same idea in Python 3:

# Python 3, ~~102~~ 100 bytes

*-2 bytes thanks to @ovs!*

```
def f(n,s="",p=0,*v):p==n<1==print(s);p in v or[f(n-1,s+d,p+1j**(ord(d)%15),p,*v)for d in"DLRU"if n]

```

Try it online!

---

A recursive function that prints the results to `STDOUT`. Keep track of `s, p, v` which are the current sequence, the current position (as a complex number), and the list of visited positions respectively.

The sequence is printed when `n == 0` and the position is back to `0`, aka `p==n<1`.

Otherwise, if there is still moves and no self-intersection (`n > 0 and p not in v`), the function tries to move the current position in 4 directions, and recurs. Given the character `d` that is one of the 4 character `D, L, R, U`, the direction is determined as

```
1j ** (ord(d) % 15)

```

since

```
d  ord(d)  ord(d)%15  1j**...
D   68        8         1
L   76        1         1j
R   82        7        -1j
U   85        10       -1

```
> 7 votes

# Answer
# Husk, 21 bytes

```
fS=oḟȯE½M#₁Q`π₁
"RULD

```

Try it online!

# Explanation

A string over `RULD` encodes a self-avoiding loop if and only if the only contiguous substring with an equal number of R and L, and of U and D, is the entire string. I loop over all strings of the given length and check this condition by brute force.

```
fS=oḟȯE½M#₁Q`π₁  Implicit input n
            `π₁  Length-n words over string "RULD" (from second line).
f                Keep those that satisfy this:
           Q       List of substrings
   oḟ              Get the first one that satisfies this:
        M#₁          Counts of each letter in "RULD"
       ½             Split in half
     ȯE              The halves (counts of R,U vs counts of L,D) are equal
 S=                That equals the string, which is the last substring in the list

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), ~~99~~ 96 bytes

<sup>*-3 bytes thanks to my pronoun is monicareinstate!*</sup>

```
Sort["ULDR"~StringPart~#&/@Select[Range@4~Tuples~#,Tr[a=I^#]==0&&DuplicateFreeQ@Accumulate@a&]]&

```

Try it online! Pure function. Takes a number as input and returns a list of character lists as output. (I believe such a format is acceptable.) The logic is pretty simple: It takes all *n*-tuples of 1, 2, 3, 4, interprets them as powers of *i*, checks that the sequences end at 0 and contain no duplicates, and converts them to the `ULDR` format.
> 2 votes

# Answer
# Python 2, ~~155~~ 139 bytes

```
r=input()
for y in range(4**r):
 n=0;s=[];k='';exec'c=y%4;y/=4;s+=n,;n+=1j**(6>>c);k="DLRU"[c]+k;'*r
 if n==0<2>max(map(s.count,s)):print k

```

Try it online!
> 1 votes

# Answer
# perl -M5.010 -n, 189 bytes

```
$k=2*$_;@m=(D,L,R,U);y=D====y=U==&&y=R====y=L==&&!/.+(??{!($&=~y=D====$&=~y=U==&&$&=~y=R====$&=~y=L==&&y===c-length$&)})/&&say for map{sprintf("%0$k".b,$_)=~s/../'$m['."0b$&]"/geer}0..4**$_

```

Try it online!

This iterates over the numbers from `0` to `4^$_`, where `$_` is the input number. Each number is turned into a binary format (padded out with zeros so they're all the same length (twice the size of the input)), and then `00` is replaced with `D`, `01` with `L`, `10` with `R`, and `11` with `U`. This enforces the correct order. Note that we include the number `4^$_` which will lead to a string that is "too long" (`RDDD..D0`), but will not pass the tests later on.

We then print the string if 1) they are a loop (contains the same number of `U`s and `D`s, and the same number of `R`s and `L`s), and 2) no proper substring does contain a loop.

Expanding the program gives us:

```
#!/opt/perl/bin/perl

use 5.026;

use strict;
use warnings;
no  warnings 'syntax';

use experimental 'signatures';

my $k = 2 * $_;
my @m = ("D", "L", "R", "U");

y/D// == y/U//  &&   # Does $_ contain as many D's as U's ?
y/R// == y/L//  &&   # Does $_ contain as many R's as L's ?
!/.+                 # Grab a substring
  (??{               # Code block, result is seen as a pattern
       !(            # Negate what follows, if true, the result is ""
                     #     and "" will always match
                     #                      if false, the result is 1,
                     #     and since the string does not contain a 1,
                     #     the match will fail
         $& =~ y!D!! == $& =~ y!U!!  && # Does the substring contain as many
                                        # D's as U's?
         $& =~ y!R!! == $& =~ y!L!!  && # Does the substring contain as many
                                        # R's as L's?
         y!!!c - length ($&)            # Is this a proper substring?
                                        # y!!!c is a funny way getting the
                                        # length of $_, saving 1 byte over
                                        # using length, and if the lengths
                                        # are unequal, subtracting them is
                                        # a true value
       )})/x    &&   # if all conditions are met
say                  # print the results
for                  # do this for each
map {
    sprintf ("%0$k" . "b", $_)          # Get the binary representation
    =~ s/../'$m[' . "0b$&]"/geer        # And replace pairs of digits
                                        # with directions; we're using a
                                        # double eval -- first to turn the
                                        # replacement part into '$m[0bXX]',
                                        # with XX the two binary digits from
                                        # match, then we eval that result to
                                        # get the right direction.
} 0 .. 4 ** $_;      # Range of numbers

__END__

```
> 1 votes

# Answer
# Python 3, 232 bytes

```
from itertools import*
x,y,z={"D":1,"U":-1},{"L":-1,"R":1},()
for j in product(*("DLRU",)*int(input())):
 n,m,s=0,0,()
 for c in j:
  if (n,m)in s:n=1e999
  s+=(n,m),;n+=x.get(c,0);m+=y.get(c,0);
 z+=("".join(j),)*(n==m==0)
print(z)

```

Brute-force approach (checks every possible string of the given length, with no optimization for performance).

Can probably be golfed a lot more, but still includes several non-obvious tricks to it. The most notable is setting `n` to `1e999` (a short form for infinity) when a self-crossing path is detected, ensuring that it never goes back to zero and saving 3 bytes over the more obvious approach of `break` in the loop and moving the assignment to `z` into a `else`.

Try it online!
> 0 votes

# Answer
# JavaScript (V8), 106 bytes

Prints the paths to STDOUT.

```
f=(n,s='',p=0,o=[])=>s[n-1]?p||print(s):(o[n*n+p]^=1)&&[n,-1,1,-n].map((d,i)=>f(n,s+'DLRU'[i],p+d,[...o]))

```

Try it online!

### Commented

```
f = (                   // a recursive function taking:
  n,                    //   n = input
  s = '',               //   s = output string
  p = 0,                //   p = position
  o = []                //   o[] = array holding all visited positions
) =>                    //
  s[n - 1] ?            // if s has the requested length:
    p || print(s)       //   print it only if we're back to our starting point
  :                     // else:
    (o[n * n + p] ^= 1) //   toggle the item in o[] at n² + p
                        //   NB: we need n² to make sure it's positive
    &&                  //   abort if it's now set to 0 (meaning that this
                        //   position was already visited)
    [n, -1, 1, -n]      //   list of directions (down, left, right, up)
    .map((d, i) =>      //   for each direction d at position i:
      f(                //     do a recursive call:
        n,              //       pass n unchanged
        s + 'DLRU'[i],  //       append the direction character to s
        p + d,          //       add the direction to the position
        [...o]          //       pass a copy of o[]
      )                 //     end of recursive call
    )                   //   end of map()

```
> 0 votes

# Answer
# Charcoal, ~~60~~ 59 bytes

```
Ｎθ⊞υωＦυ«≔Ｅι§⟦¹θ±¹±θ⟧⌕LURDκζ¿¬№ＥζΣ…ζλΣζ¿‹ＬιθＦLURD⊞υ⁺ικ¿¬Σζ⟦ι

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ

```

Input `n`.

```
⊞υω

```

Start the list of sequences off with an empty sequence.

```
Ｆυ«

```

Perform a breadth-first search of sequences.

```
≔Ｅι§⟦¹θ±¹±θ⟧⌕LURDκζ

```

Convert the sequence into a list of directions `1`, `i`, `-1` and `-i`. As Charcoal doesn't have complex numbers, I'm simulating them using `n` instead of `i`. It's not possible for `n` of these numbers to overflow to zero (I need `n` `1`s and an `n+1`th `-n` to do that) so I'm safe.

```
¿¬№ＥζΣ…ζλΣζ

```

Take the sums of the proper prefixes and check that the sum of the directions does not appear. Note that due to a Charcoal quirk the sum of `[]` is not zero, so we can allow a single zero to appear as a sum of the sequence.

```
¿‹Ｌιθ

```

Is this sequence of the desired length? If not...

```
ＦLURD

```

Loop over each direction.

```
⊞υ⁺ικ

```

Append the direction and push this candidate sequence to the list of sequences.

```
¿¬Σζ

```

Did this sequence of the desired length finish back at the origin?

```
⟦ι

```

If so then print it on its own line.
> 0 votes

# Answer
# Swift 5/Xcode 10.3, ~~434~~ ~~433~~ ~~417~~ ~~399~~ ~~366~~ ~~360~~ 273 bytes

```
func g(_ a:[(Int,Int)],_ b:String)->[String]{let l=a.last!;if b.count==n{return l==(0,0) ?[b]:[]};return[(l.0,l.1-1,"D"),(l.0-1,l.1,"L"),(l.0+1,l.1,"R"),(l.0,l.1+1,"U")].flatMap{m in a[1...].contains{$0.0==m.0 && $0.1==m.1} ?[]:g(a+[(m.0,m.1)],b+m.2)}};return g([(0,0)],"")

```

Try it online!
> 0 votes

---
Tags: code-golf, path-finding
---


# Question
Title: Insert parens into a free-form SKI calculus expression
Imagine a simple SKI calculus expression - for example, `(((S α) β) γ)`. As you can see, each node of the rooted tree has exactly two children. Sometimes though, the parentheses are omitted and the tree is unrooted (just to make the notation clear, I believe). The challenge is to put the parentheses back, so that the tree is binary and rooted again.

The preferable way of I/O is mostly up to you; although the input and output has to at least look like the SKI calculus, and it obviously has to represent a tree.

The rule on adding parentheses is simple: `α β γ` becomes `((α β) γ)` (bind to the left), `α β γ δ` becomes `(((α β) γ) δ)`, and so on.

You may assume that the input is a correct SKI-calculus expression.

If it wasn't clear enough, you may NOT add more braces than necessary. And if it helps you in any way, you can assume that the input contains no redundant parens (like, for example, `(((SK)))`).

### Examples

```
S(KS)K => ((S(KS))K)
SS(SK) => ((SS)(SK))

```

# Answer
# Perl 5 `-p`, 37 bytes

```
s/(\w|\((?1)*\)){2}(?!\))/($&)/&&redo

```

Try it online!
> 5 votes

# Answer
# Charcoal, 52 bytes

```
≔⟦⟧ηＦθ¿⁼)ι≔⊟υη«Ｆ⁼Ｌη²⊞η⮌Ｅ²⊟η¿⁼(ι«⊞υη⊞η⟦⟧≔§η¹η»⊞ηι»⭆¹η

```

Try it online! Link is to verbose version of code. Outputs a stringified tree-like nest of lists. Explanation:

```
≔⟦⟧η

```

Start with an empty tree.

```
Ｆθ

```

Loop over the input characters.

```
¿⁼)ι

```

If this is a `)`, then...

```
≔⊟υη

```

... restore the parent node saved below, otherwise:

```
«Ｆ⁼Ｌη²

```

If the current node already has two children, then...

```
⊞η⮌Ｅ²⊟η

```

... remove them and put them in a first child node. (I can't wrap them in a node, since its parent is still pointing to it.)

```
¿⁼(ι«

```

If this is a `(`, then...

```
⊞υη

```

... save the current node, ...

```
⊞η⟦⟧

```

... push an empty node, ...

```
≔§η¹η»

```

... and set that as the current node.

```
⊞ηι»

```

Otherwise push the letter to the current node.

```
⭆¹η

```

Stringify and output the tree.

56 bytes for pretty output:

```
≔⟦⟧ηＦ⁺θI«≔⪫()⪫ηωζＦ⁼Ｌη²≔⟦ζ⟧η≡ι(«⊞υη≔⟦⟧η»)«≔⊟υη⊞ηζ»⊞ηι»§η⁰

```

Try it online! Link is to verbose version of code. Explanation:

```
≔⟦⟧η

```

Start with an empty tree.

```
Ｆ⁺θI«

```

Loop over the input characters, but add an extra `I` to ensure that the final result is wrapped in `()` if necessary. (If the result can always be wrapped in `()`, then this can be `Ｆ⪫()θ«` and the last part can be `»ζ` for an overall saving of 1 byte.)

```
≔⪫()⪫ηωζ

```

Get what the bracketed expression would be.

```
Ｆ⁼Ｌη²≔⟦ζ⟧η

```

If the current node already has two children then replace it with a node with the bracketed expression.

```
≡ι

```

Switch on the current character.

```
(«⊞υη≔⟦⟧η»

```

If it's a `(` then save the current node and start a new node.

```
)«≔⊟υη⊞ηζ»

```

If it's a `)` then retrieve the saved node and push the bracketed expression to it.

```
⊞ηι

```

Otherwise push the letter to the current node.

```
»§η⁰

```

Output the desired expression.
> 2 votes

---
Tags: code-golf, combinatory-logic
---


title: Determine the area enclosed by slashes

text:
# Question
Title: Determine the area enclosed by slashes
For example, let's look at the following ASCII art:

```
/\    - encloses a total of 2 cells - half a cell per slash
\/
 /\   - encloses 4 cells fully and half of 8 cells, for a total of 8
/  \
\  /
 \/

```

Your challenge is to write a program that determines (and outputs) the total area enclosed by ASCII art composed only of spaces, slashes and newlines. Slashes won't necessarily be a part of a shape with non-zero area. A point is defined as enclosed *iff* it is unreachable from any point outside the art's bounding box, if slashes are impassable.

Slashes have zero area and cells are assumed to be \\$1\times1\\$ squares. `/`s represent lines that connect the lower left corner with the upper right corner, and `\`s represent lines the connect the upper left corner with the lower right corner of the corresponding cells. Spaces represent empty space.

## Test cases

```
/\/\
\   \
 \/\/

```

Encloses 3 cells fully and 10 partially, for a total of 8.

```
///\\\
//  \\
/ /\ \
\ \/ /
\\  //
\\\///

```

Encloses 12 cells fully (the four innermost slashes have both corresponding half-cells enclosed) and half of 12 cells, for a total of 18.

```
/\/\
/\/\
/\/\

```

Encloses 0 cells.

```
 /\
/  \
\/\/
/\/\
\  /
 \/

```

Encloses 8 cells fully and 12 cells partially, for a total of 14.

```
   /\
  /  \
 /  \ \
/   /  \
\ \/  \/
 \ \  /
  \   \
   \/\/

```

Encloses 25 cells fully and half of 18 cells, for an area of 34.

This is tagged , so the shortest answer wins.

# Answer
> 17 votes
# JavaScript (ES6),  ~~228 195 192~~  185 bytes

Expects a matrix of characters as input.

This can be quite slow on some inputs, such as the last test case.

```
m=>m.map((r,Y)=>r.map((_,X)=>n+=(g=(x,y,z,q=z&2,r=m[y],v=r&&r[x])=>v?(v|=64+(v>{})+!++v)^(r[x]|=v|4<<z)?g(x+--q*~z%2,y-q*z%2,z^2)&g(x,y,v&3?z^=v&2|1:z+1&3)|!(r[x]=v):1:0)(X,Y,0)),n=0)|n

```

Try it online!

## How?

### Grid encoding

We divide each cell into 4 areas as follows:

The current position is encoded as \\$(x,y,z)\\$, where \\$(x,y)\\$ is the position in the matrix and \\$z\\$ is the ID of the area.

The characters in the original matrix are converted on the fly to 7-bit integers as they are visited:

```
+---------> a marker to tell that this tile has been converted (always 1)
|      +--> 4 bits to tell whether a given area has been visited
|      |
|      |      +-----> set to 1 if the cell contains an anti-slash
|  ____|____  |  +--> set to 1 of the cell contains a slash
| /         \ |  |
1 z3 z2 z1 z0 AS S

```

The conversion is done with:

```
v |= 64 + (v > {}) + !++v

```

The expression `(v > {})` is only *true* for `'\'` and `!++v` is *true* for either `'/'` or `'\'`. If `v` is already an integer, it is left unchanged.

### Algorithm

Evaluating the area enclosed by slashes is equivalent to counting the number of cells from which we can't escape from the grid, starting from a given area ID. We arbitrary start from area #0, but that would work with any of them as long as it is consistent.

We iterate on all possible starting points and process some kind of flood-filling that takes the area IDs into account.

For each visited cell, we try to move to an adjacent cell (left figure) and to another area within the same cell (right figure).

The recursion stops either when we escape the grid or when we get trapped.

# Answer
> 13 votes
# , <sup>~~108~~ ~~95~~ ~~93~~ ~~91~~ ~~83~~ ~~80~~</sup> 77 bytes

*-13 due using 4x4 instead of 3x3 masks*

*-7 thanks to Jonah*

*-~~2~~ 5 thanks to Bubbler*

This expands the ASCII to a 4 times as big bit map that gets searched in for enclosed spaces. Maybe you can do the calculations on the original map, but at least this approach works for now. :-)

```
[:+/@,12%~1=2|.@|:@(2(>.*])/\,)^:4^:_[:,"_1/^:2((+./~#:9),-.(,:|.)=i.4){~' \'i.]

```

Try it online!

### How it works

Ungolfed:

```
12 +/@,@:%~
1=
((,-)=i.2) (] * >./@:(|.!.2))^:_
((+./~#:9) , -. (,:|.)=i.4) ,"_1/^:2@:{~ ' \/'i. ]

```

Build up 3x4x4 masks, where `0` is a wall:

```
((+./~#:9) , -. (,:|.)=i.4)

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

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

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

```

That expands each character ' \\/'. So from a 3x4 drawing we get a 12x16 bit mask. The empty space has 12 1's (while still allowing traversal) and each side of a slash has 6.

```
,"_1/^:2@:{~' \/'i.]

```

Then shift the matrix in the four directions by rotating the matrix. At the borders `2` gets shifted in. The resulting matrices are added up together by taking the highest value (so 2 expands), while `0` in the matrix deletes (so borders blocks expansions). We do this until the result does not change `(…)^:_`.

```
2|.@|:@(2(>.*])/\,)^:4^:_

```

We are interested in the 1's that still stand. And because of our bit masks, we can simply divide by 12 of the total sum of all 1's to get the result.

```
12 +/@,@:%~

```

# Answer
> 8 votes
# Charcoal, ~~114~~ ~~100~~ ~~96~~ 91 bytes

```
ＷＳ⊞υιＦυ«Ｊ⁰⁺³ⅉＦι«Ｍ³→≡κ/Ｐ/²\Ｐ\²»»≔⁺²Ｌθθ≔⁺²ＬυυＪ±¹±¹Ｂ×³θ×³υψ¤#ＦυＦθ«Ｊ×³κ×³ιＰX²»≔Ｉ÷⁻×⊗υ⊗θ№ＫＡ#⁴θ⎚θ

```

Try it online! Link is to verbose version of code. Assumes rectangular input. Explanation:

```
ＷＳ⊞υι

```

Input the art.

```
Ｆυ«Ｊ⁰⁺³ⅉ

```

Loop over each row of the art.

```
Ｆι«Ｍ³→

```

Loop over each cell of the art.

```
≡κ/Ｐ/²\Ｐ\²»»

```

Output it at three times its original size.

```
≔⁺²Ｌθθ≔⁺²Ｌυυ

```

Adjust the size of the art for a notional 1-square border on each side.

```
Ｊ±¹±¹Ｂ×³θ×³υψ

```

Draw a notional box around the notional border. This allows the border to be filled without actually having drawn anything.

```
¤#

```

Fill the exterior of the art with `#`. Sadly Charcoal doesn't support multiline fill patterns. (Its fill was designed for the challenge, Bake a slice of Pi.)

```
ＦυＦθ«Ｊ×³κ×³ιＰX²»

```

Draw `X`s at every position (including the notional border), overwriting all the existing spaces and slashes. This means that each square now has only four `#`s (or fewer if it didn't get completely filled in).

```
≔Ｉ÷⁻×⊗υ⊗θ№ＫＡ#⁴θ

```

Calculate the number of `#`s that there would have been had the art originally been empty (including the border), subtract the number of `#`s actually filled, then divide by 4.

```
⎚θ

```

Clear the canvas and output the result.

Alternative solution, based on @xash's idea of 4×4 masks, also 91 bytes:

```
≔⪫  ⭆θ θ⊞υθＷＳ⊞υ⪫  ι⊞υθＢ×⁴Ｌθ×⁴ＬυψＦＬυＦＬθ«Ｊ×⁴κ×⁴ι≡§§υικ «↘ＵＲ²»/«↓↓↓↗⁴»↘⁴»↖¤#≔Ｉ⁻×ＬυＬθ÷№ＫＡ#¹²θ⎚θ

```

Try it online! Link is to verbose version of code. Assumes rectangular input. Explanation:

```
≔⪫  ⭆θ θ⊞υθ

```

Generate a padding row.

```
ＷＳ⊞υ⪫  ι

```

Input the art padded on both sides.

```
⊞υθ

```

Add padding to the bottom of the art.

```
Ｂ×⁴Ｌθ×⁴Ｌυψ

```

Draw a notional box around the padded art. This allows the padding to be filled without actually having drawn anything.

```
ＦＬυＦＬθ«

```

Loop over each cell of the art.

```
Ｊ×⁴κ×⁴ι

```

Jump to the cell.

```
≡§§υικ «↘ＵＲ²»/«↓↓↓↗⁴»↘⁴

```

Draw the cell at four times size, except that space becomes a dot. This means that it takes up the same amount of space as a `/` or `\` but without impeding the flood fill.

```
»↖¤#

```

Move the cursor off the last dot so that the exterior of the art can be flood filled with `#`.

```
≔Ｉ⁻×ＬυＬθ÷№ＫＡ#¹²θ

```

Divide the number of `#`s by 12, and subtract that from the padded size of the art.

```
⎚θ

```

Clear the canvas and output the result.

# Answer
> 5 votes
# APL (Dyalog Unicode), 67 bytes

```
12÷⍨≢⍸1=(⍉∘⌽2(⌈∧⊢)/2,⊢)⍣4⍣≡⊃⍪/,/({(∘.∨⍨1=3|⍳4)(⌽⍵)⍵}∘.≠⍨⍳4)[' /'⍳⎕]

```

Try it online!

A port of xash's excellent J answer.

### How it works

```
12÷⍨≢⍸1=(⍉∘⌽2(⌈∧⊢)/2,⊢)⍣4⍣≡⊃⍪/,/({(∘.∨⍨1=3|⍳4)(⌽⍵)⍵}∘.≠⍨⍳4)[' /'⍳⎕]

⊃⍪/,/({(∘.∨⍨1=3|⍳4)(⌽⍵)⍵}∘.≠⍨⍳4)[' /'⍳⎕]  ⍝ Preprocessing
     (                         )          ⍝ Create 3 bitmasks
                         ∘.≠⍨⍳4           ⍝ Negated identity matrix of size 4
      {            (⌽⍵)⍵}                 ⍝ Strand with its reflection, and
       (∘.∨⍨1=3|⍳4)                       ⍝ Self OR outer product of 1 0 0 1
                                [' /'⍳⎕]  ⍝ Convert three chars ' /\' to respective bitmasks
   ,/  ⍝ Join horizontally adjacent arrays horizontally
 ⍪/    ⍝ and vertically adjacent ones vertically
⊃      ⍝ Remove nesting

12÷⍨≢⍸1=(⍉∘⌽2(⌈∧⊢)/2,⊢)⍣4⍣≡  ⍝ Flood fill from the outside, and find the answer
        (          2,⊢)      ⍝ Prepend 2 on each row
            2(⌈∧⊢)/          ⍝ Pairwise reduce: (x,y)→lcm(max(x,y),y)
                             ⍝ Effectively, if left is 2 and right is nonzero, make it 2;
                             ⍝ keep the right one otherwise
         ⍉∘⌽                 ⍝ Rotate the matrix 90 degrees
                       ⍣4⍣≡  ⍝ Repeat on the four sides, until the flood fill is complete
12÷⍨≢⍸1=  ⍝  Count ones, and divide by 12

```

# Answer
> 4 votes
# MATL, ~~51~~ ~~50~~ 49 bytes

```
Ji^G8\*TTYa3XytPJ*-X*Xj~4&1ZIt1)0hm3thZCS6:Y)~Yms

```

Input is a char matrix, with `;` as row separator.

Try it online! Or verify all test cases

### Explanation

The approach is similar to that used in my answer to this other challenge.

```
J        % Push imaginary unit, j
i        % Take input: char matrix
^        % Element-wise power of j raised to the code points of the input.
         % This gives -j, 1, 1 for '/', '\' and ' ' respectively
G        % Push input again
8\       % Modulo 8, element-wise. This gives 7, 4 0 for '/', '\' and ' '
         % respectively. The specific values do not matter; it only matters
         % that ' ' gives 0 and the other chars give nonzero
*        % Multiply. Now we have a matrix that contains -7, 4 and 0 for
         % '/', '\' and ' ' (*)
TTYa     % Pad array with a 2D frame of zeros of length 1
3Xy      % Push 3×3 identity matrix
tP       % Duplicate, flip vertically
J*-      % Multiply by imaginary unit and subtract. This gives the matrix
         % [1 0 -j; 0 1-j 0; -j 0 1] (**)
X*       % Kronecker product. This replaces each entry of (*) by its
         % product with (**)
Xj       % Real part. We now have a matrix where '/', '\' and ' ' have been
         % transformed into [0 0 -7; 0 -7 0; -7 0 0], [4 0 0; 0 4 0; 0 0 4]
         % and [0 0 0; 0 0 0; 0 0 0] respectively
~        % Negate. We now have a matrix with "pixelated" versions of the
         % input chars at 3 times greater resolution, with an empty frame.
         % Pixels equal to 1 are empty space, and pixels equal to 0 are
         % borders corresponding to the original slash chars
4&1ZI    % Label connected components based on 4-neighbourhood. This
         % transformes the pixels which contained 1 into different numbers
         % We are interested in the area not occupied by the outer
         % connected component and the borders
t1)      % Duplicate. Value of the upper-left corner. This gives the label
         % of the outer component
0h       % Append 0. This is the value of the borders
m        % Ismember: this gives true for pixels that are outer component
         % or border. Each original cell corresponds to a 3×3 block of
         % pixels. Each of those blocks will contain 9 zeros for cells
         % that were fully enclosed; 6 zeros for cells with its two halves
         % enclodes but with a border in between; 3 zeros for cells with
         % one of its halves enclosed, and 0 zeros for cells not enclosed
3thZC    % Matrix where each distinct 3×3 block has been arranged into
         % a column of length 9
S        % Sort. This sends 1 to the bottom and 0 to the top
6:Y)     % Keep the first 6 rows. This effectively transforms columns with
         % 9 zeros into columns of 6 zeros. So now we have 0, 3 or 6 zeros
         % for not covered, partically covered or fully covered cells
~        % Logical negation
Ym       % Mean of each column. This transforms the 0, 3, and 6 numbers
         % referred to above into 0, 0.5 or 1
s        % Sum. Implicit display

```

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


title: Quines that print what their index is

text:
# Question
Title: Quines that print what their index is
We all know what a quine is. A quine is a program which prints its own source code. And we also know about the printable ASCII characters. Well... this challenge mixes both.

Your mission, should you accept it, is to create an *index quine*. An index quine is a non-empty program, composed only of the printable ASCII characters, which prints its own *index*.

The index of a string is its position within an infinite dictionary where all strings composed of exactly the printable ASCII characters appear, sorted by size then ASCII code.

The index is a non-negative whole number, assigning 0 to the empty string then continuing with the space, !, " onward.

For example, `*!` precedes `**` as the ending `!` in the first string has lower ASCII code than the ending `*` in the second, but both are preceded by `{`, which has a higher ASCII code than the characters of the last two examples, but is shorter.

The printed index should be in base 10, outputted through STDOUT or closest equivalent, with no other output unless your language requires trailing newlines/other characters. Also, a bit like actual quines, do not access your source code directly (as a file, etc.)

Your program should be non-empty, as a reminder to those reading these rules.

If there are multiple programs of shortest length, the tiebreaker is the program with the lower index.

The shortest program following these very rules wins. Have fun.

# Answer
> 11 votes
## Deorst, 1 byte

```

```

Try it online!

## Commentator, 1 byte

```

```

Try it online!

## Snails, 1 byte

```

```

Try it online!

---

So far, I have found three one-byte solutions, all of which print 1 with a space in the source code.

The first two languages were created by @cairdcoinheringaahing, and the last one by @feersum.

# Answer
> 5 votes
# , 52 bytes

```
echo-95x#.31-3 u:(,quote)'echo-95x#.31-3 u:(,quote)'

```

Try it online!

### How it works

```
echo-95x#.31-3 u:(,quote)'echo-95x#.31-3 u:(,quote)'
                         '...'  NB. a string literal
                 (,quote)       NB. concatenate self with single-quoted self
             3 u:  NB. convert to Unicode codepoints
          31-      NB. subtract from 31 (negation of 1-based index)
     95x#.         NB. convert from base 95 to integer (using extended integer)
    -              NB. negate
echo               NB. print with newline

```

# Answer
> 4 votes
# Pyth, ~~39~~ ~~37~~ 33 bytes

-2 bytes thanks to @Mukundan

```
hiR95]m-Cd31jN B"hiR95]m-Cd31jN B

```

Try it online!

```
hiR95]m-Cd31jN B"...
                "...   ( String literal
               B       ( Wrap in an array and duplicate
            jN         ( Join using `"` (this gives us the full source code)
      m-Cd31           ( For each character, take its codepoint minus 31
     ]                 ( Wrap in an array
 iR95                  ( Map base 95-conversion to that array
h                      ( Take the first (only) element

```

# Answer
> 4 votes
# Python 3.8 (pre-release), <sup>~~82~~ ~~66~~</sup> 63 bytes

-3 bytes thanks to @dingledooper

```
exec(a:='g=0\nfor i in b"exec(a:=%r)"%a:g=g*95+i-31\nprint(g)')

```

Try it online!

# Answer
> 3 votes
# C# (.NET Core), 471 bytes

```
using System.Numerics;class A{static void Main(){var s="using System.Numerics;Class A{{static void Main(){{var s={0}{1}{0};System.Console.Write(V(string.Format(s,(char)34,s)));}}static BigInteger V(string s){{BigInteger r=0;for(int i=0;i<s.Length;++i)r+=(s[i]-31)*BigInteger.Pow(95,i);return r;}}}}";System.Console.Write(V(string.Format(s,(char)34,s)));}static BigInteger V(string s){BigInteger r=0;for(int i=0;i<s.Length;++i)r+=(s[i]-31)*BigInteger.Pow(95,i);return r;}}

```

Try it online!

This is the basic C# quine with the scoring function built in. Is my scoring function a little off? It doesn't quite agree with the Python one linked in the comments.

# Answer
> 3 votes
# Gol\>\<\>, 15 bytes

```
"r3lMF`_*+fs-|h

```

Try it online!

An extension from my own 6-byte quine.

### How it works

```
"r3lMF`_*+fs-|h
"...             Start string ("), push all characters, and end string(")
 r3              Reverse the stack and push 3 (= 34 - 31)
   lMF       |   Loop (stack length - 1) times...
      `_*+         [... n2 n1] -> [... n2+n1*95]
          fs-      Subtract 31
                 equivalent to "-31 from each except top and base 95 convert"
              h  Print the top number and halt

```

# Answer
> 3 votes
# Python 2, ~~68~~ 65 bytes

*-3 bytes thanks to @Mukundan*

```
x="g=0\nfor i in'x=%r;exec x'%x:g=95*g+ord(i)-31\nprint g";exec x

```

Try it online!

# Answer
> 1 votes
# \+ GMP, ~~156~~ 116 bytes

or 126 bytes in R

```
"->a;t=utf8ToInt(a)-31;sum(as.bigz(95)^(115:0)*c(3,t,3,t))"->a;t=utf8ToInt(a)-31;sum(as.bigz(95)^(115:0)*c(3,t,3,t))

```

Try it online!

*Edit: Big improvement by re-arranging to start immedidately with quoted string, which really simplifies the re-construction of the full program text.*

~~This seems horribly uncompetitive, but I don't seem to be able to do any better, I'm afraid.~~ The enormously-verbose `utf8ToInt()` function name isn't really helping much.

# Answer
> 1 votes
# Java (OpenJDK 8), 724 bytes

```
import java.math.*;class D{public static void main(String[]a0){char q=34;String s="import java.math.*;class D{public static void main(String[]a0){char q=34;String s=;String u=s.substring(0,82)+q+s+q+s.substring(82);BigInteger n=new BigInteger(s.substring(60,61));for(int i=0;i<u.length();)n=n.add(new BigInteger(new Long(95).toString()).pow(i).multiply(new BigInteger(new Long(u.charAt(u.length()-i++-1)-31).toString())));System.out.print(n);}}";String u=s.substring(0,82)+q+s+q+s.substring(82);BigInteger n=new BigInteger(s.substring(60,61));for(int i=0;i<u.length();)n=n.add(new BigInteger(new Long(95).toString()).pow(i).multiply(new BigInteger(new Long(u.charAt(u.length()-i++-1)-31).toString())));System.out.print(n);}}

```

Try it online!

# Answer
> 0 votes
# Stax, 34 bytes

1-byte difference with Pyth, since I can't get rid of the prepending quote in Stax.

```
"c34|Ss+{31-m95|E"c34|Ss+{31-m95|E

```

Try it online!

## Explanation

```
"..."                 The second half of the program
     c                Copy this operand
      34|S            Surround it with quotes
          s+          Prepend the quoted string with the original string
            {   m     Map: (Since direct - removes items)
             31-      Codepoint - 31 (Stax strings consist of codepoints)
                 95|E Convert from base 95

```

# Answer
> 0 votes
# Stax, 12 bytes

```
0|?F31-s94*+

```

Run and debug it

Note that this uses the `|?` program source operand, which may be cheating

```
0   # Push a zero to the stack
|?  # Return program's source as a string
F   # for each character (as an ascii value)...
31- # subtract 31 from the character's value
s   # get the running total
94* # multiply it by 94
+   # add the character's value

```

# Answer
> 0 votes
# Perl 5 \+ `-Mbigint -M5.10.0`, 71 bytes

```
$_=q($n+=(95**(70-$-++))*(-31+ord)for"\$_=q($_);eval"=~/./g;say$n);eval

```

Try it online!

---
Tags: code-golf, printable-ascii, self-referential
---