title: Area enclosed by perimeter loop

text:
# Question
Title: Area enclosed by perimeter loop
Find the area of a region of unit cells given its perimeter loop as a sequence of 90-degree turns.

For example, take the three-cell region

```
XX
X

```

whose perimeter loop we draw

```
L<S<L
v   ^
S R>L
v ^
L>L

```

Each turn is marked as left (L), straight (S), or right (R). Starting from the R, the turns are `RLLSLSLL`. So, given input `RLLSLSLL`, we should output 3 for the area.

The input sequence is guaranteed to trace out a loop enclosing a single region on its left.

* The path ends back at the start point, facing the initial direction, forming a loop.
* The loop does not cross or touch itself.
* The loop goes counterclockwise around a region.

**I/O**

You can take input as a list or string of characters `LSR`, or as numbers `-1, 0, 1` for left, straight, right. Output is a positive integer. Floats are OK.

**Test cases**

The inputs are given in both formats followed by their respective outputs.

```
RLLSLSLL
LLLL
SLLSLL
LSRRSLLSSLSSLSSL
SSSSSLSSSSSLSSSSSLSSSSSL

[1, -1, -1, 0, -1, 0, -1, -1]
[-1, -1, -1, -1]
[0, -1, -1, 0, -1, -1]
[-1, 0, 1, 1, 0, -1, -1, 0, 0, -1, 0, 0, -1, 0, 0, -1]
[0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0, -1]

3
1
2
7
36

```

# Answer
> 10 votes
# Brain-Flak, 112 bytes

```
(([]){[{}]<{({}()){{}<>([{}]<([{}])>)(<>)}<>(({}[({})])[({}{})])<>}{}<>>({}<({}())>)<>([])}{})({()<({}()())>}{})

```

Try it online!

This program uses Green's theorem to compute the area

The current location is stored on the right stack, in a format that depends on the direction faced.

```
Direction  top  second
north       -x       y
west        -y      -x
south        x      -y
east         y       x

```

In all instances, the second value on the stack will increase by 1, and the line integral for the area decreases by half the value on the top of the stack. To compensate, the end of the program divides the running total by -2.

```
# For each number in input
(([]){[{}]

  # Evaluate turn-handling to zero
  <

    # If turn:
    {

      # If right turn:
      ({}()){{}

        # Negate both values on other stack (reverse direction)
        <>([{}]<([{}])>)

      (<>)}

      # Swap the two stack elements and negate the new top of stack
      # This performs a left turn.
      <>(({}[({})])[({}{})])<>

    }{}

  <>>

  # Evaluate as top of stack and...
  ({}<

    # increment the number below it
    ({}())

  >)<>

([])}{})

# Divide total by -2
({()<({}()())>}{})

```

# Answer
> 7 votes
# APL (Dyalog Classic), ~~30~~ ~~28~~ 19 bytes

-2 thanks to @Adám

```
(+/9∘○×11○+\)0j1*+\

```

Try it online!

uses tricks with complex numbers to compute the coordinates

the area is ½Σ(xi-xi+1)(yi+yi+1) or equivalently Σ(xi-xi+1)yi as the lines are only horizontal or vertical

# Answer
> 6 votes
# JavaScript (ES6), ~~52~~ 50 bytes

*Saved 2 bytes thanks to @Neil*

Expects the second input format.

```
a=>a.map(k=>r+=(2-(a=a+k&3))%2*(y+=~-a%2),r=y=0)|r

```

Try it online!

### How?

*This description applies to the previous version: **x** and **y** have since been inverted.*

This is based on the formula already mentioned by @ngn: **A = Σ(xi \- xi+1)yi**, which can also be written as **Σdxiyi** where **dxi** is either -1, 0 or 1.

We start with **r = y = 0**.

We keep track of the current direction in **a**:

```
          | a = 0 | a = 1 | a = 2 | a = 3
----------+-------+-------+-------+-------
direction | East  | South | West  | North
       dx |  +1   |   0   |  -1   |   0     <--  -(~-a % 2)
       dy |   0   |  +1   |   0   |  -1     <--  (2 - a) % 2

```

It is updated with `a = a + k & 3`, where **k** is the current element of the input array.

Because **a** initially contains the input array, **a + k** is coerced to **NaN** on the first iteration and then to **0** when the bitwise AND is applied. This means that the first direction change is actually ignored and we always start heading to East. It doesn't matter because the area remains the same, no matter the orientation of the final shape.

Then, we update **y** with `y += (2 - a) % 2`.

Finally, we compute **-dx** with `~-a % 2` and subtract **y * -dx** from **r**, which -- at the end of the process -- is our final result.

# Answer
> 4 votes
# Python 2, 64 bytes

```
f=lambda c,d=1,x=0:c>[]and f(c[1:],d*1j**c[0],x+d.real)-x*d.imag

```

Try it online!

Computes ∑xΔy using complex numbers.

# Answer
> 3 votes
# Haskell, ~~71~~ ~~70~~ 69 bytes

```
a 0 0
a x d(t:r)|k<-t+d=x*g k+a(x+g(k-1))k r
a _ _ _=0
g a=sin$a*pi/2

```

Explanation: Green's Theorem gives the formula for the area : A = ½∑(xk+1+xk)(yk+1-yk), which simplifies to A = ½∑Δx=02xkΔy + ½∑Δy=0(xk+1+xk)\*0 = ∑xΔy when turns are 90 degrees along the axes. We have the following pseudocode for a recursive turn-globbing function that keeps track of the x position and direction:

```
A x dir (turn:turns) = ΔA + A (x+Δx) (dir+turn) turns

```

where the new direction, ΔA and Δx can be seen from the following tables. We can see a sinusoidal periodicity of length four in both ΔA and Δx along the diagonal axis, `dir+turn`, which is implemented using `sin` instead of modular arithmetic.

```
  ↔|L S R ΔA| L  S  R  Δx| L  S  R
←   ↓ ← ↑    -x  0  x      0 -1  0
↑   ← ↑ →     0  x  0     -1  0  1
→   ↑ → ↓     x  0 -x      0  1  0
↓   → ↓ ←     0 -x  0      1  0 -1

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), ~~36~~ 30 bytes

```
Area@Polygon@AnglePath[.5Pi#]&

```

If you have an older version of Mathematica (~v10) you'll need `Most@` in front of `AnglePath` to avoid closing the polygon. (Thanks to @user202729 for the tips).

original: Try it online!

updated: Try it online!

# Answer
> 2 votes
# Jelly, ~~15~~ 11 bytes

*Thanks to @xnor for pointing out a useless step, saving 2 bytes*
*Thanks to @dylnan for saving another byte*

Expects the second input format. Returns a float.

```
+\ı*Ḟ_\×ƊĊS

```

Try it online! or run all test cases

### Commented

```
+\ı*Ḟ_\×ƊĊS  - main link, taking the input list   e.g. [1, -1, -1, 0, -1, 0, -1, -1]
+\           - cumulative sum                     -->  [1, 0, -1, -1, -2, -2, -3, -4]
  ı*         - compute 1j ** d,                   -->  [(0+1j), (1+0j), (0-1j), (0-1j),
               which gives a list of (-dy + dx*j)       (-1+0j), (-1+0j), (0+1j), (1+0j)]
         Ċ   - isolate the imaginary part (dx)    -->  [1, 0, -1, -1, 0, 0, 1, 0] (floats)
        Ɗ    - invoke the last 3 links as a monad
    Ḟ        - isolate the real part (-dy)        -->  [0, 1, 0, 0, -1, -1, 0, 1] (floats)
     _\      - negated cumulative sum (gives y)   -->  [0, -1, -1, -1, 0, 1, 1, 0]
       ×     - compute dx * y                     -->  [0, 0, 1, 1, 0, 0, 1, 0]
          S  - sum                                -->  3

```

# Answer
> 2 votes
# Python 2, 62 bytes

```
f=lambda l,p=0,s=1:l>[]and(p/s).imag/2+f(l[1:],p+s,s*1j**l[0])

```

Try it online!

Similar to Lynn's solution, but using some complex arithmetic to extract the right component of the complex number in one go.

# Answer
> 1 votes
# Pyth, 25 bytes

Uses the `-1, 0, 1` input format.

```
s*Vm_sd._sMKm^.j)sd._QeMK

```

Try it here!

# Answer
> 0 votes
# Pyth, 14 bytes

```
_smec^.j)sd2.:

```

Test suite

```
_smec^.j)sd2.:
              Q     implicit input
            .:      take all non-empty contiguous sublists
  m                map this operation onto each one:
   ec^.j)sd2
         s           the sum of the sublist
     ^.j)            raise it to the complex unit 1j to that power
    c      2         halve it
   e                take the imaginary part
_s                take the negated sum of the result

```

This expresses the area as the sum of `-1/2 * g(sum(l))` over all contiguous sublists `l` over the input, where `g` does modular indexing into `[0,1,0,-1]`. The code implements `g` as `g(x)=imag(1j**x)`. There may be a shorter method with direct modular indexing, using `sin`, or an arithmetic function on `x%4`.

---
Tags: code-golf, geometry, grid
---


title: Word Search Puzzle

text:
# Question
Title: Word Search Puzzle
Given a rectangular text as a word search puzzle and a search string, determine if the text contains the search string. The search string may appear:

* horizontally, vertically or diagonally
* forwards or backwards

You may write a function or a program and take two strings as input via function argument, ARGV or STDIN. The output should be a truthy or falsy result which can either be returned from the function or written to STDOUT.

Assume that the text will contain arbitrary printable ASCII characters (hex codes 20 to 7E) and line break characters. Letters are case sensitive. You may assume that the input text is rectangular, i.e. all lines have the same length. You may whether the input ends with a trailing newline or not (if it matters for your submission).

This is code golf, the shortest answer (in bytes) wins.

## Examples

Using this grid from Wikipedia's article on word searches as the first input:

```
WVERTICALL
ROOAFFLSAB
ACRILIATOA
NDODKONWDC
DRKESOODDK
OEEPZEGLIW
MSIIHOAERA
ALRKRRIRER
KODIDEDRCD
HELWSLEUTH

```

the following search strings should yield truthy or falsy results respectively:

```
Truthy: RANDOM, VERTICAL, HORIZONTAL, WORDSEARCH, WIKIPEDIA, TAIL
Falsy:  WordSearch, CODEGOLF, UNICORN

```

Alternatively, using this input text

```
Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur.

```

We get the following search results (using quotes now, because there are spaces in some search strings):

```
Truthy: "Lorem", "mine", "uma bop", "tuetdod", "snol,a", "texas", "pii.d  v", "vexta"
Falsy:  "lorem", "wordsearch", "pii.d v", "mute"

```

# Answer
# CJam, ~~46~~ 37 bytes

```
qN%{_zW%__,N**2$2$+,)/z\}4*]:+N*eas#)

```

Reads the grid from STDIN and the word as a command-line argument. Prints positive integers for matches and 0 for non-matches.

At the cost of two extra bytes, both strings (word, linefeed, grid) can be read from STDIN:

```
qN%(\{_zW%__,N**2$2$+,)/z\}4*](\:+N*\#)

```

You can try this version online with the CJam interpreter.

### Example run

```
$ for W in Lorem mine uma\ bop tuetdod snol,a texas pii.d\ \ v vexta WordSearch CODEGOLF UNICORN; do echo -e "$(cjam wordsearch.cjam "$W" < grid)\t$W"; done
1       Lorem
3085    mine
2055    uma bop
5142    tuetdod
3878    snol,a
1426    texas
5371    pii.d  v
2536    vexta
0       WordSearch
0       CODEGOLF
0       UNICORN

```

### Background

Assume the input was the following grid:

```
ABCD
EFGH
IJKL

```

Splitting at linefeeds, we obtain the following array:

```
A := [
         "ABCD"
         "EFGH"
         "IJKL"
     ]

```

That covers East words (words going from left to right).

Now, we join the elements of `A` using a string of `len(A)` linefeeds as separator:

```
"ABCD⏎⏎⏎EFGH⏎⏎⏎IJKL"

```

Then, we chop the resulting string in chunks of length `len(A) + len(A[0]) + 1`:

```
[
    "ABCD⏎⏎⏎E"
    "FGH⏎⏎⏎IJ"
    "KL"
]

```

If we "zip" the array (transpose rows and columns), we obtain:

```
[
    "AFK"
    "BGL"
    "CH"
    "D⏎"
    "⏎⏎"
    "⏎⏎"
    "I⏎"
    "EJ"
]

```

That covers South East words.

If we zip A and reverse the order of the result's rows, we obtain:

```
[
    "DHL"
    "CGK"
    "BFJ"
    "AEI"
]

```

That covers South and – after repeating the process for diagonals – South West words.

Zipping and reversing again, we obtain:

```
[
    "LKJI"
    "HGFE"
    "DCBA"
]

```

That covers West and – after repeating the process for diagonals – North West words.

Zipping and reversing once more, we obtain:

```
[
    "IEA"
    "JFB"
    "KGC"
    "LHD"
]

```

That covers North and – after repeating the process for diagonals – North East words.

### How it works

The code does as explained in the previous section, with two minor differences:

* It zips and reverses once at the very beginning.
* It computes `len(A) + len(A[0])` as `len(A + zip(A))`.

Finally, it joins all rows of all generated arrays using linefeeds as separators and searches for the word in the resulting string.

```
qN%                                   " A := split(input(),'\n')                          ";
   {                    }4*           " Do 4 times:                                       ";
    _zW%                              "   B := reverse(zip(A))                            ";
        __,N**                        "   C := B.join(len(B) * '\n')                      ";
              2$2$+,)/z               "   D := zip(C.chunks(len(A + B) + 1))              ";
                       \              "   A := B                                          ";
                           ]          " Collect all values of A and D in an array R.      ";
                            :+        " R := flatten(R)                                   ";
                              N*      " R := R.join('\n')                                 ";
                                eas   " I := flatten(ARGV)                                ";
                                   #) " print R.index(I) + 1                              ";

```
> 8 votes

# Answer
# Java : 183 ~~211~~ ~~321~~

```
boolean s(char[]w,char[]s){int j,z,a=s.length,i=a*9,f=1,q=0;for(;s[q++]>10;);for(;i-->0;)for(j=w.length,z=i/9;i%9!=4&j-->0&z>=0&z<a&&s[z]==w[j];z+=q*(i/3%3)+i%3-q-1)f*=j;return f==0;}

```

A basic brute force. There's not much else to say, I guess. Input is needle first and haystack second. Assumes grid is newline-terminated.

A slightly more readable version with test case shown:

```
public class WordSearch {
    static String grid = "WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH";
    static String search = "RANDOM";

    public static void main(String[] args) {
        System.out.println(new WordSearch().s(search.toCharArray(),grid.toCharArray()));
    }

    boolean s(char[]w,char[]s){
        int j,z,a=s.length,i=a*9,f=1,q=0;
        for(;s[q++]>10;);
        for(;i-->0;)
            for(j=w.length,z=i/9;
                i%9!=4&j-->0&z>=0&z<a&&s[z]==w[j];
                z+=q*(i/3%3)+i%3-q-1)
                f*=j;
        return f==0;
    }
}

```
> 7 votes

# Answer
# JavaScript (E6) 111 ~~116~~

Brute force search for every character in every direction - as golfed as I can

```
F=(b,w)=>
  [1,-1,r=b.search('\n'),-r,++r,-r,++r,-r].some(d=>
    [...b].some((_,p)=>
      [...w].every(c=>c==b[p+=d],p-=d)
    )
  )

```

**Test** In FireFox/Firebug console

```
;["RANDOM", "VERTICAL", "HORIZONTAL", "WORDSEARCH", "WIKIPEDIA", "TAIL",
"WordSearch", "CODEGOLF", "UNICORN"]
.forEach(w=>console.log('\n'+ w +' -> '+
  F("WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH",w)))

```

*Output*

```
RANDOM -> true
VERTICAL -> true
HORIZONTAL -> true
WORDSEARCH -> true
WIKIPEDIA -> true
TAIL -> true
WordSearch -> false
CODEGOLF -> false
UNICORN -> false

```
> 6 votes

# Answer
## Python, 175

Not very inspired, but here goes:

```
def s(h,n):
 l=h.find('\n')+2;h+='\n'*l;L=i=len(h)
 while i>0:
  i-=1
  for d in[-l,1-l,2-l,-1,1,l-2,l-1,l]:
    j=i;m=len(n)
    for c in n:m-=c==h[j%L];j+=d
    if m<1:i=-1
 return-i

```

First argument is haystack, second is needle.
> 5 votes

# Answer
# C# - ~~218~~ ~~197~~ 186 bytes

C# function that takes 2 strings, the first the word to search for, the later the grid with line feeds (`\n`) between lines. Things are getting desperate now... *so desperate* in-fact that my previous edit *didn't work!*

Golfed code:

```
bool F(string D,string S){int l=S.Length,i=l*13,r,p;for(S+="\n";i-->l*5;i=r<0?r:i)for(r=D.Length,p=i%l;p>-1&p<l&r-->0&&D[r]==S[p];p+=(S.IndexOf('\n')+1)*(i/l%9/3-1)+i/l%3-1);return i<0;}

```

Less golfed with test code:

```
class P
{
    static void Main()
    {
        System.Console.WriteLine(new P().F(System.Console.ReadLine(),System.Console.In.ReadToEnd())?"Truthy":"Falsy"); // because why not
    }

    bool F(string D,string S)
    {
        int l=S.Length,i=l*13,r,p;

        for(S+="\n";i-->l*5;i=r<0?r:i) // for each cell/direction
            for(r=D.Length,p=i%l;p>-1&p<l&r-->0&&D[r]==S[p];p+=(S.IndexOf('\n')+1)*(i/l%9/3-1)+i/l%3-1); // test against string (backwards)

        return i<0;
    }
}

```
> 5 votes

# Answer
# Bash+coreutils, 214 169 bytes

```
r()(tee >(rev) $@)
t()(eval paste -d'"\0"' `sed 's/.*/<(fold -1<<<"&")/'`)
d()(while IFS= read l;do echo "$a$l";a+=_;done|t)
r<<<"$2"|r >(d) >(r|t) >(r|d)|r|grep -q "$1"

```

Uses 3 transform functions `r`, `t` and `d` to reverse, transpose and diagonal shift, in all the necessary combinations.

*Update - the `r` function now produces reversed and non-reversed output for extra golfiness*

Input via commandline arguments - search string, followed by (newline separated) rectangular wordsearch block.

Output is an idiomatically correct shell exit status code - 0 meaning TRUE and 1 meaning FALSE.

### Output:

```
$ for w in "Lorem" "mine" "uma bop" "tuetdod" "snol,a" "texas" "pii.d  v" "vexta" ; do ./ws.sh "$w" "Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur."; echo $?; done
0
0
0
0
0
0
0
0
$ for w in WordSearch CODEGOLF UNICORN ; do ./ws.sh "$w" "Lorem ipsum dolor sit amet consectetu
r adipisicing elit sed do eiusmod tem
por incididunt ut labore et dolore ma
gna aliqua. Ut enim ad minim veniam,
quis nostrud exercitation ullamco lab
oris nisi ut aliquip ex ea commodo co
nsequat. Duis aute irure dolor in rep
rehenderit in voluptate velit esse ci
llum dolore eu fugiat nulla pariatur."; echo $?; done
1
1
1
$

```
> 5 votes

# Answer
# C,163

```
f(char*h,char*n){int i,j,d,p,y=0,l=strlen(h),w=strchr(h,10)-h+1;for(i=l*9;i--;y+=d&&!n[j]){p=i/9;d=i%9/3*w-w+i%3-1;for(j=0;p>=0&p<l&h[p]==n[j];j++)p+=d;}return y;}

```

No rearrangement of the grid, I simply try every starting letter in every direction, and walk along until I run off the grid or find a mismatch.

I take advantage of the fact that a C string terminates in a zero byte. As there are no zero bytes in the grid, there will ALWAYS be a mismatch. But if the mismatch occurs at the zero byte we know we have found the end of the string to be searched for, and record it as a match.

**Ungolfed in a test program**

```
char h[]="WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH\n";

f(char*h,char*n){                                   //haystack,needle
  int i,j,d,p,y=0,l=strlen(h),w=strchr(h,10)-h+1;   //l=length of whole grid. w=width of row, including terminal newline ASCII 10
  for(i=l*9;i--;){                                  //for each start letter and direction
    p=i/9;                                          //pointer to start letter
    d=i%9/3*w-w+i%3-1;                              //9 possible values of direction vector {-w,0,w}+{-1,0,1}
    for(j=0;p>=0&p<l&h[p]==n[j];j++)p+=d;           //walk p in the direction defined by d until we walk off the top or bottom of the grid or a mismatch is fount
    y+=d&&!n[j];                                    //if we got all the way to the terminal 0, record it as a hit. If d=0, don't record as this is an invalid direction.
  }
  return y;
}

main(int c, char**v){
  printf("%d",f(h,v[1]));
}

```

**Output**

Note that the function will return the total number of incidences of the string searched for in the grid. Thus for `OD` it returns 6. If no incidences are found it returns 0 which is the only falsy value in C. Changing to `y|=d*!n[j]` would save one character but lose this functionality.

```
$ ./a UNICORN
0

$ ./a CODEGOLF
0

$ ./a WordSearch
0

$ ./a RANDOM
1

$ ./a WORDSEARCH
1

$ ./a VERTICAL
1

$ ./a HORIZONTAL
1

$ ./a WIKIPEDIA
1

$ ./a TAIL
1

$ ./a OD
6

```
> 5 votes

# Answer
## Python 2 - 246 ~~259~~ ~~275~~ ~~308~~ ~~298~~ ~~297~~ ~~294~~ ~~313~~ ~~322~~

```
w,s=input()
r=range
d='\n'
I=''.join
w=w.split(d)
t,u=len(w),len(w[0])
v=d.join([I(x)for x in zip(*w)]+[d]+[I([w[i+j][i]for i in r(min(u,t-j))])+d+I([w[i][i+j]for i in r(min(t,u-j))])for j in r(max(t,u))]+[d]+w)
print s in v or s[::-1]in v

```

Thanks to Will for some help with dealing with the print and defining join.

Thanks to underground railroad for reminding me to golf spaces properly ;p

Fixed for bad matches thanks to using ',' as delimiter.

Apparently the best way to golf is to add tons of horizontal scrolling.

Input as ~~whitespace~~ ~~bang~~ newline delimited lines in quotes: "WVERTICALL\nROOAFFLSAB\nACRILIATOA\nNDODKONWDC\nDRKESOODDK\nOEEPZEGLIW\nMSIIHOAERA\nALRKRRIRER\nKODIDEDRCD\nHELWSLEUTH","RANDOM"
> 4 votes

# Answer
## Haskell - 173

Instead of searching directly on the grid, I transform the grid in different ways and match the word with each row of the new grid.

For example,

```
G1    G2    G3       G4   G5

abcd  aA1   abcd     a..  ..1
ABCD  bB2   .ABCD    bA.  .A2
1234  cC3   ..1234   cB1  aB3
      dD4            dC2  bC4
                      D3  cD
                       4  d

```

Search the word in each row of G1, G2, G4 and G5, then we're done. Note that G3 is not used, I post it here just for illustration.

A similar idea is applied to search forward and backward: just search the original word and reversed word.

So now we have searched 8 directions. Here's the code, whose correctness was verified by another script.

```
import Data.List
v=reverse
t=transpose
y=any
d r=zipWith(++)(scanr(\_->('\n':))[]r)r
g r w=y(y$y((==w).take(length w)).tails)[r,t r,t.d$r,t.d.v$r]
f r w=y(g(lines r))[w,v w]

```

The function `f` is what we want and its argument `r` is the rectangle string, `w` is the word to search.
> 4 votes

# Answer
# APL (Dyalog Classic), 44 bytes

```
1∊⍞⍷↑{⍉0,⍵,↑(0,⊢)\↓0,⍵}¨{⍉⌽⍵}\4⍴⊂↑a⊆⍨a≠⊃⌽a←⎕

```

Try it online!
> 2 votes

# Answer
# , ~~60~~ 53 bytes

```
<@[e.[:,[:(;|.)@>[:<\\.@>[:(<"1,</.)@>@(;|.@|:)[;.2@]

```

Try it online!

Requires the first input to contain no newlines.

Explanation:

```
linkrotate=: ;|.@|:     NB. link with itself rotated 90° ccw
infixes   =: <\\.       NB. list of boxes containing the infixes
lines     =: <"1 , </.  NB. horizontal and diagonal lines, boxed
linkrev   =: ;|.        NB. link with itself reversed
appearin  =: <@[ e. [: , [: linkrev@> [: infixes@> [: lines@>@linkrotate [;.2@]

```

Try it online!

Hooks are useful.
> 0 votes

# Answer
# Jelly, 16 bytes

Solved a related (possibly a duplicate) challenge with 15 of these 16 bytes as the core of the code...

```
ỴZU$3Ð¡;ŒD$€Ẏw€Ẹ

```

A dyadic link accepting a list of characters on the left and a list of characters on the right which returns 1 if found and 0 if not.

**Try it online!**

### How?

```
ZU$3Ð¡;ŒD$€Ẏw€Ẹ - Link: words, grid
   3Ð¡          - repeat three times and collect the results (inc input):
  $             -   last two links as a monad:
Z               -     transpose
 U              -     upend     (together these rotate by a quarter)
          €     - for €ach:
         $      -   last two links as a monad:
       ŒD       -     get forward-diagonals
      ;         -     concatenate
           Ẏ    - tighten (to get all the runs across the grid)
             €  - for €ach run:
            w   -   sublist-index (0 if not found)
              Ẹ - any truthy? (i.e. was the word found?)

```
> 0 votes

---
Tags: code-golf, string, decision-problem, word-search
---


title: Mutually Attacking Queens

text:
# Question
Title: Mutually Attacking Queens
Let an 8x8 chessboard be represented by any two distinct values, with one value being an empty square and the other being a queen. In the following examples, I use 0s as the empty squares and 1s as queens. For example:

is given by

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

```

Consider the number of pairs of queens that are attacking each that are at least one square away (as a reminder, queens attack orthogonally and diagonally). In the above example, the following incredible ugly diagram shows all these pairs as arrows.

There are 43 pairs found above giving the following test case:

```
Input:
1 0 1 1 1 0 0 0
1 0 1 0 1 0 1 1
1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 0
0 1 1 0 0 1 0 1
1 0 0 0 1 0 0 0
0 1 0 0 0 1 1 1
0 1 1 1 0 1 0 1
Output: 43

```

## Challenge

Write a program that, given a board state represented by two distinct values, outputs the number of pairs of queens that attack each other with at least one square in between them.

* You may input in whatever format is most convenient that uses two values to represent the empty squares and queens, e.g., a string of 64 "."s for empty squares and "Q"s for queens by rows from bottom to top, an 8x8 matrix of booleans, a list of list of integers 0 and 1 etc, as long as it is explained in your solution
* Output is an integer
* Standard I/O methods apply and standard loopholes forbidden
* This is code golf so shortest answer in bytes wins

## Test cases:

Using the 0 and 1 format, with 0 being empty squares and 1 being queens:

```
Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 0

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 0

Input:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
Output: 1

Input:
0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 1 0 0 0 0 1 0
0 0 0 0 1 0 1 0
0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0
0 0 0 0 0 0 0 0
Output: 10

Input:
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 4

Input:
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 0 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
Output: 11

```

# Answer
# Python 2, 105 bytes

```
lambda b:sum(b[i+d::d][:(8,7-i%8,i%8)[d%8%5]].find('1')*int(c)>0for i,c in enumerate(b)for d in[1,7,8,9])

```

Try it online!

# Explanation

We take the input as a string of 64 characters `'0'` or `'1'`. Using step slices, we cast four "lines of sight" from every queen we encounter. For example, when **i = 10** and **d = 7**, marking the queen as ♥ and the tiles selected by `b[i+d::d]` as █:

```
1 0 1 1 1 0 0 0
1 0 ♥ 0 1 0 1 1
1 █ 1 0 1 1 0 1
█ 1 0 1 0 1 0 █
0 1 1 0 0 1 █ 1
1 0 0 0 1 █ 0 0
0 1 0 0 █ 1 1 1
0 1 1 █ 0 1 0 1

```

Clearly, we don't actually want vision to wrap around the board like this. So we compute how far away the edge of the board is in each direction, and view the tiles at `b[i+d::d][:…]`.

For each tile-direction pair we count:

```
ray.find('1')*int(c)>0

```

This will fail whenever

* `c` is not a queen; or
* the queen this ray sees is too close (`find` returns 0); or
* this ray sees no queen (`find` returns −1).

Each pair of queens is only checked once, since rays are always casted *forward* in reading order, from an "earlier" queen to a "later" one.
> 14 votes

# Answer
# JavaScript (ES7), 86 bytes

Takes input as an array of 64 integers with **254** for a queen and **0** for an empty square.

```
a=>[s=0,6,7,8].map(d=>a.map(g=(n,p)=>(p%8-(p+=~d)%8)**2<n%4?a[p]?s+=n&1:g(n/2,p):0))|s

```

Try it online!

This version abuses arithmetic underflow to get a stop condition in the recursive part.

---

# JavaScript (ES7), 89 bytes

Takes input as an array of 64 bits.

```
a=>[s=0,6,7,8].map(d=>a.map(g=(n,p,x)=>(p%8-(p+=~d)%8)**2>1|p<0?0:a[p]?s+=!x&n:g(n,p)))|s

```

Try it online!

### How?

We recursively call a named callback function of `map()` to walk through the squares in a given direction. Although we don't really need the content of the third parameter of the callback (the array `map()` was called upon), we indirectly use it nonetheless to know whether it is the first iteration or not.

> *arr.map(function callback(currentValue\[, index\[, array\]\])*

This is the **x** variable in the code.

```
a =>                        // given the input array a[]
  [ s = 0,                  // initialize the sum s to 0
    6, 7, 8 ].map(d =>      // for each direction d in [0, 6, 7, 8]:
    a.map(g = (n, p, x) =>  //   for each square n at position p in a[]:
      (                     //     we are out of the board if:
        p % 8 -             //       - abs(p % 8 - p' % 8) is greater than 1
        (p += ~d) % 8       //         where p' = p - (d + 1)
      ) ** 2 > 1 |          //         (squaring is shorter than using Math.abs)
      p < 0 ?               //       - or p' is less than 0
        0                   //       if so, stop recursion
      :                     //     else:
        a[p] ?              //       if there's a queen on the target square:
          s +=              //         increment s if:
            !x &            //           x is undefined (this is not the 1st iteration)
            n               //           and n = 1 (there's a queen on the source square)
        :                   //       else:
          g(n, p)           //         do a recursive call to g(), with x undefined
    )                       //   end of inner map()
  ) | s                     // end of outer map(); return s

```
> 10 votes

# Answer
# Snails, 14 bytes

```
A
rdaa7\1\0+\1

```

Try it online!

Input is the 0/1 format, without spaces within lines.

Snails was created for a 2D pattern matching language design PPCG challenge. Most importantly, it by default outputs the number of matches found, which is perfect for this challenge.

---

`A` sets the "all paths" option, so that if a queen is in multiple pairs, each of those pairs would generate a match.

`rdaa7` sets the match direction to S, SE, E, and NE. Setting to all directions (`z`) would cause double counting.

`\1\0+\1` matches a `1`, then one or more `0`s, then another `1`.
> 9 votes

# Answer
# APL (Dyalog Classic), ~~41~~ ~~39~~ 32 bytes

```
(+/+⌿-⌈⌿)2<⌿0⍪⊢,⍉,8 31⍴⊢,≠⍨,⌽,≠⍨

```

Try it online!

`≠⍨` is "not equal to itself" - an 8x8 all-zero matrix

`⊢,≠⍨,⌽,≠⍨` \- if the original matrix is `ABC...`, this expression returns:

```
A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0 0
I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0 0 0
Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0 0 0 0
Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0 0 0 0 0
G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0 0 0 0 0 0
O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0 0 0 0 0 0 0
W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0 0 0 0 0 0 0 0
E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E 0 0 0 0 0 0 0 0

```

`8 31⍴` reshapes it from 8x32 to 8x31, reusing the elements in row-major order:

```
A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

```

`⊢,⍉,` prepends the original matrix and its transpose (extra spaces for clarity):

```
A B C D E F G H  A I Q Y G O W E  A B C D E F G H 0 0 0 0 0 0 0 0 H G F E D C B A 0 0 0 0 0 0 0
I J K L M N O P  B J R Z H P X F  0 I J K L M N O P 0 0 0 0 0 0 0 0 P O N M L K J I 0 0 0 0 0 0
Q R S T U V W X  C K S A I Q Y G  0 0 Q R S T U V W X 0 0 0 0 0 0 0 0 X W V U T S R Q 0 0 0 0 0
Y Z A B C D E F  D L T B J R Z H  0 0 0 Y Z A B C D E F 0 0 0 0 0 0 0 0 F E D C B A Z Y 0 0 0 0
G H I J K L M N  E M U C K S A I  0 0 0 0 G H I J K L M N 0 0 0 0 0 0 0 0 N M L K J I H G 0 0 0
O P Q R S T U V  F N V D L T B J  0 0 0 0 0 O P Q R S T U V 0 0 0 0 0 0 0 0 V U T S R Q P O 0 0
W X Y Z A B C D  G O W E M U C K  0 0 0 0 0 0 W X Y Z A B C D 0 0 0 0 0 0 0 0 D C B A Z Y X W 0
E F G H I J K L  H P X F N V D L  0 0 0 0 0 0 0 E F G H I J K L 0 0 0 0 0 0 0 0 L K J I H G F E

```

`2<⌿0⍪` adds 0s on top and compares using `<` every element against the element below it, so we get a 1 for the leading 1 in every vertical group of 1s, and we get 0s everywhere else

`+⌿-⌈⌿` the sums by column minus the maxima by column - we compute the number of gaps between the 1-groups in every column, 0 if there are none

`+/` sum
> 7 votes

# Answer
# Jelly, ~~22~~ 20 bytes

```
t0ŒgL:2
Z,U;ŒD$€ẎÇ€S

```

Try it online!
> 5 votes

# Answer
# K (ngn/k), ~~45~~ 43 bytes

-2 bytes thanks to @coltim

```
{+/0|-1+/0|-':x,'+x,+8 31#,/+x,a,(|x),a:^x}

```

Try it online!
> 4 votes

# Answer
# Retina 0.8.2, ~~60~~ 58 bytes

```
1
¶1$';___¶
_
$n$%`7$*_
(.)(?=.*;(_)*)(?<-2>.)*
$1
m`^10+1

```

Try it online! Takes input as 8 comma-separated 8-character binary strings, but the header converts the provided format for you. Explanation:

```
1
¶1$';___¶

```

Create all of the substrings of the board starting at a queen. Suffix a marker value to each substring. Edit: Saved 2 bytes by leaving some garbage strings behind; these are effectively ignored.

```
_
$n$%`7$*_

```

Split each marker up into an inclusive range, and add 7 to the non-zero elements.

```
(.)(?=.*;(_)*)(?<-2>.)*
$1

```

Delete every run of characters that equals the length of the marker. This is equivalent to finding each east, southwest, south or southeast ray from each queen.

```
m`^10+1

```

Count all the rays that pass through at least one empty square before meeting another queen.
> 3 votes

# Answer
# JavaScript (ES6) + SnakeEx, 38 bytes

```
s=>snakeEx.run('m:<*>10+1',s).length/2

```

Takes input in the form `'10111000\n10101011\n10101101\n01010100\n01100101\n10001000\n01000111\n01110101'`. Turns out, SnakeEx can still be used outside of its original challenge!
> 3 votes

---
Tags: code-golf, chess, binary-matrix
---


title: The biggest square

text:
# Question
Title: The biggest square
This question is similar to Biggest Square in a grid.

**Challenge**

Given a matrix of `1` and `0` in a string format `"xxxx,xxxxx,xxxx,xx.."` or array format `["xxxx","xxxx","xxxx",...]`, You will create a function that determines the area of the largest square submatrix that contains all `1`.

A square submatrix is one of equal width and height, and your function should return the area of the largest submatrix that contains only `1`.

**For Example:**

Given `"10100,10111,11111,10010"`, this looks like the following matrix:

1 0 1 0 0

1 0 1 **1 1**

1 1 1 **1 1**

1 0 0 1 0

You can see the bolded `1` create the largest square submatrix of size 2x2, so your program should return the area which is 4.

**Rules**

* Submatrix must be one of equal width and height
* Submatrix must contains only values `1`
* Your function must return the area of the largest submatrix
* In case no submatrix is found, return `1`
* You can calculate the area of the submatrix by counting the number of `1` in the submatrix

**Test cases**

**Input:** `"10100,10111,11111,10010"` **Output:** `4`

**Input:** `"0111,1111,1111,1111"` **Output:** `9`

**Input** `"0111,1101,0111"` **Output:** `1`

---

This is , so the shortest answer in bytes win.

# Answer
# Jelly, 18 bytes

+2 to handle no-all-1 sublist present output

```
ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1

```

**Try it online!** Or see the test-suite

### How?

```
ẆZṡ¥"L€$ẎȦÐfL€Ṁ²»1 - Link: list of lists of 1s and 0s
Ẇ                  - all slices (lists of "rows") call these S = [s1,s2,...]
       $           - last two links as a monad:
     L€            -   length of each (number of rows in each slice) call these X = [x1, x2, ...]
    "              -   zip with (i.e. [f(s1,x1),f(s2,x2),...]):
   ¥               -     last two links as a dyad:
 Z                 -       transpose (get the columns of the current slice)
  ṡ                -       all slices of length xi (i.e. squares of he slice)
        Ẏ          - tighten (to get a list of the square sub-matrices)
          Ðf       - filter keep if:
         Ȧ         -   any & all (all non-zero when flattened?)
            L€     - length of €ach (the side length)
              Ṁ    - maximum
               ²   - square (the maximal area)
                »1 - maximum of that and 1 (to coerce a 0 found area to 1)

```
> 2 votes

# Answer
# Haskell, ~~113 121 118~~ 117 bytes

```
x!s=[0..length x-s]
t#d=take t.drop d
f x=last$1:[s*s|s<-min(x!0)$x!!0!0,i<-x!!0!s,j<-x!s,all(>'0')$s#i=<<(s#j)x,s>0]

```

Try it online!

-3 bytes thanks to Laikoni!

-1 byte thanks to Lynn!

+8 bytes for the ridiculous requirement of returning 1 for no all-1s sub-matrix..

### Explanation/Ungolfed

The following helper function just creates offsets for `x` allowing to decrement them by `s`:

```
x!s=[0..length x-s]

```

`x#y` will drop `y` elements from a list and then take `x`:

```
t#d=take t.drop d

```

The function `f` loops over all possible sizes for sub-matrices in order, generates each sub-matrix of the corresponding size, tests whether it contains only `'1'`s and stores the size. Thus the solution will be the last entry in the list:

```
--          v prepend a 1 for no all-1s submatrices
f x= last $ 1 : [ s*s
                -- all possible sizes are given by the minimum side-length
                | s <- min(x!0)$x!!0!0
                -- the horizontal offsets are [0..length(x!!0) - s]
                , i <- x!!0!s
                -- the vertical offsets are [0..length x - s]
                , j <- x!s
                -- test whether all are '1's
                , all(>'0') $
                -- from each row: drop first i elements and take s (concatenates them to a single string)
                              s#i =<<
                -- drop the first j rows and take s from the remaining
                                      (s#j) x
                -- exclude size 0...........................................
                , s>0
                ]

```
> 5 votes

# Answer
# APL (Dyalog Unicode), ~~35~~ ~~34~~ 32 bytes

```
{⌈/{×⍨⍵×1∊{∧/∊⍵}⌺⍵ ⍵⊢X}¨⍳⌊/⍴X←⍵}

```

Try it online!

Adám's SBCS has all of the characters in the code

Explanation coming eventually!
> 4 votes

# Answer
# Haskell, ~~99~~ 97 bytes

```
b s@((_:_):_)=maximum$sum[length s^2|s==('1'<$s<$s)]:map b[init s,tail s,init<$>s,tail<$>s]
b _=1

```

Checks if input is a square matrix of just ones with `s==('1'<$s<$s)`, if it is, answer is length^2, else 0. Then recursively chops first/last column/row and takes the maximum value it finds anywhere.

Try it online!
> 4 votes

# Answer
# , 33 27 bytes

-6 bytes thanks to FrownyFrog!

```
[:>./@,,~@#\(#**/)@,;._3"$]

```

Try it online!

## Explanation:

I'll use the first test case in my explanation:

```
    ] a =. 3 5$1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

```

I generate all the possible square submatrices with size from 1 to the number of rows of the input.

`,~@#\` creates a list of pairs for the sizes of the submatrices by stitching `,.` togehter the length of the successive prefixes `#\` of the input:

```
   ,~@#\ a
1 1
2 2
3 3

```

Then I use them to cut `x u ;. _3 y` the input into submatrices. I already have `x` (the list of sizes); `y` is the right argument `]` (the input).

```
 ((,~@#\)<;._3"$]) a
┌─────┬─────┬─────┬───┬─┐
│1    │0    │1    │0  │0│
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │0    │1    │1  │1│
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1    │1    │1    │1  │1│
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0  │0 1  │1 0  │0 0│ │
│1 0  │0 1  │1 1  │1 1│ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│1 0  │0 1  │1 1  │1 1│ │
│1 1  │1 1  │1 1  │1 1│ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

┌─────┬─────┬─────┬───┬─┐
│1 0 1│0 1 0│1 0 0│   │ │
│1 0 1│0 1 1│1 1 1│   │ │
│1 1 1│1 1 1│1 1 1│   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
│     │     │     │   │ │
├─────┼─────┼─────┼───┼─┤
│     │     │     │   │ │
└─────┴─────┴─────┴───┴─┘

```

For each submatrix I check if it consist entirely of 1s: `(#**/)@,` \- flatten the matrix, and mutiply the number of items by their product. If all items are 1s, the result will be their sum, otherwise - 0:

```
   (#**/)@, 3 3$1 0 0 1 1 1 1 1 1
0
   (#**/)@, 2 2$1 1 1 1
4

   ((,~@#\)(+/**/)@,;._3"$]) a
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1

0 0 0 0 0
0 0 4 4 0
0 0 0 0 0

0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

```

Finally I flatten the list of results for each submatrix and find the maximum:

`>./@,`

```
   ([:>./@,,~@#\(+/**/)@,;._3"$]) a
4

```
> 3 votes

# Answer
# K (ngn/k), ~~33~~ 28 bytes

```
{*/2#+/|/',/'{0&':'0&':x}\x}

```

Try it online!
> 3 votes

# Answer
# Ruby `-n`, 63 bytes

```
p (1..l=$_=~/,|$/).map{|i|/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max

```

Try it online!

Ruby version of my Python answer. Golfier as a full program. Alternatively, an anonymous lambda:

# Ruby, ~~70~~ 68 bytes

```
->s{(1..l=s=~/,|$/).map{|i|s=~/#{[?1*i]*i*(?.*(l-i+1))}/?i*i:1}.max}

```

Try it online!
> 3 votes

# Answer
# Retina, 143 bytes

```
%`$
,;#
+%(`(\d\d.+;#)#*
$1¶$&¶$&#
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2
)r`((11)|\d\d)(\d*,;?#*)\G
$#2$3
1,
#
Lv$`(#+).*;\1
$.($.1*$1
N`
-1G`
^$
1

```

Try it online! Link includes test cases. Takes input as comma-separated strings. Explanation:

```
%`$
,;#

```

Add a `,` to terminate the last string, a `;` to separate the strings from the `#`s and a `#` as a counter.

```
+%(`
)

```

Repeat the block until no more subsitutions happen (because each string is now only one digit long).

```
(\d\d.+;#)#*
$1¶$&¶$&#

```

Triplicate the line, setting the counter to 1 on the first line and incrementing it on the last line.

```
\G\d(\d+,)|\G((;#+¶|,)\d)\d+
$1$2

```

On the first line, delete the first digit of each string, while on the second line, delete all the digits but the first.

```
r`((11)|\d\d)(\d*,;?#*)\G
$#2$3

```

On the third line, bitwise and the first two digits together.

```
1,
#

```

At this point, each line consists of two values, a) a horizontal width counter and b) the bitwise and of that many bits taken from each string. Convert any remaining `1`s to `#`s so that they can be compared against the counter.

```
Lv$`(#+).*;\1
$.($.1*$1

```

Find any runs of bits (vertically) that match the counter (horizontally), corresponding to squares of `1`s in the original input, and square the length.

```
N`

```

Sort numerically.

```
-1G`

```

Take the largest.

```
^$
1

```

Special-case the zero matrix.
> 2 votes

# Answer
# JavaScript, 92 bytes

```
a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1

```

```
f=
a=>(g=w=>a.match(Array(w).fill(`1{${w}}`).join(`..{${W-w}}`))?w*w:g(w-1))(W=a.indexOf`,`)||1
console.log(f('0111,1111,1111,1111'));
console.log(f('10100,10111,11111,10010'));
console.log(f('0111,1101,0111'));
```
> 2 votes

# Answer
# APL (Dyalog Classic), ~~21~~ 20 bytes

```
×⍨{1∊⍵:1+∇2×/2×⌿⍵⋄0}

```

Try it online!
> 2 votes

# Answer
# Python 2, ~~117~~ 109 bytes

Credit to @etene for pointing out an inefficiency that cost me an additional byte.

```
lambda s:max(i*i for i in range(len(s))if re.search(("."*(s.find(',')-i+1)).join(["1"*i]*i),s))or 1
import re

```

Try it online!

Takes input as a comma-separated string. This is a regex-based approach that tries matching the input string against patterns of the form `111.....111.....111` for all possible sizes of the square.

In my calculations, doing this with an anonymous lambda is just a tad shorter than defined function or a full program. The `or 1` part in the end is only necessary to handle the strange edge case, where we must output `1` if there are no ones in the input.
> 2 votes

# Answer
# Python 2, 116 115 117 109 bytes

*Credits to @Kirill for helping me golf it even more and for his clever & early solution*

*Edit*: Golfed 1 byte by using a lambda, I didn't know assigning it to a variable didn't count towards the byte count.

*Edit 2*: Kirill pointed out my solution didn't work for cases where the input only contains `1`s, I had to fix it and lost two precious bytes...

*Edit 3*: more golfing thanks to Kirill

Takes a comma separated string, returns an integer.

```
lambda g:max(i*i for i in range(len(g))if re.search(("."*(g.find(",")+1-i)).join(["1"*i]*i),g))or 1
import re

```

Try it online!

I independently found an answer that is close to Kiril's one, i.e regex based, except that I use `re.search` and a `def`.

It uses a regex built during each loop to match an incrementally larger square and returns the largest one, or 1.
> 2 votes

# Answer
# Python 2, ~~138~~ 128 bytes

```
def f(m):j=''.join;L=j(m);k=map(j,zip(*m));return len(L)and max(len(L)*(len(m)**2*'1'==L),f(k[1:]),f(k[:-1]),f(m[1:]),f(m[:-1]))

```

Try it online!

---

Saved

* -10 bytes thanks to ovs
> 1 votes

# Answer
# Perl 6, ~~61~~ ~~60~~ 58 bytes

```
{(^$_ X.. ^$_).max({[~&](.[|$^r||*])~~/$(1 x$r)/&&+$r})²}

```

Try it online!
> 1 votes

# Answer
## Clojure, 193 bytes

```
#(apply max(for [f[(fn[a b](take-while seq(iterate a b)))]R(f next %)R(f butlast R)n[(count R)]c(for[i(range(-(count(first R))n -1)):when(apply = 1(for[r R c(subvec r i(+ i n))]c))](* n n))]c))

```

Wow, things escalated :o

Less golfed:

```
(def f #(for [rows (->> %    (iterate next)    (take-while seq)) ; row-postfixes
              rows (->> rows (iterate butlast) (take-while seq)) ; row-suffixes
              n    [(count rows)]
              c    (for[i(range(-(count(first rows))n -1)):when(every? pos?(for [row rows col(subvec row i(+ i n))]col))](* n n))] ; rectangular subsections
          c))

```
> 1 votes

---
Tags: code-golf, matrix
---


title: Autogram programs

text:
# Question
Title: Autogram programs
This sentence employs two a’s, two c’s, two d’s, twenty-eight e’s, five f’s, three g’s, eight h’s, eleven i’s, three l’s, two m’s, thirteen n’s, nine o’s, two p’s, five r’s, twenty-five s’s, twenty-three t’s, six v’s, ten w’s, two x’s, five y’s, and one z.

Such sentences are called autograms. Your task is to write a program or function that has a similar property: it takes as input a byte, and outputs an integer representing the number of times that byte appears in the program's source code. It should output 0 if its input doesn't appear in its source.

**Your program must not read its own source code**, directly or indirectly, but instead all the data it needs to give its output must be hard-coded, quine style. Your program must be at least one byte in length.

This is , so the shortest entry (in bytes) wins. I won't accept an answer, so feel free to compete for the shortest solution in your favourite language.

You are strongly encouraged to include an explanation in your post.

## Leaderboards

Below are leaderboards both for overall score and per language:

```
var QUESTION_ID=162408,OVERRIDE_USER=21034;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 15 votes
# Octave, 44 bytes

```
@(x)sum([[39,'(())*,239==@[[]]msuxx']]==x)*2

```

Try it online!

The result of the function, when using each of the characters in the function as input:

```
'  (  )  *  ,  2  3  9  =  @  [  ]  m  s  u  x
2  4  4  2  2  2  2  2  4  2  4  4  2  2  2  4

```

All other input characters returns a zero.

The fact that I had to escape `'` made this a whole lot longer. In order to account for the 4 parentheses, I just had a duplicate in the string. However, duplicating apostrophes takes apostrophes, so this just takes us further from the correct result. Therefore, I had to count the number of apostrophes with its ASCII-value, `39`. This of course meant I had to check for the characters `3` and `9` too, making it all a lot longer.

# Answer
> 7 votes
# Excel, 84 bytes

```
=IFERROR(MID("65496331125442343343233",FIND(A1,"""123456789,()=MINORFADEOMEN"),1),0)

```

`Find()` will look for the value in cell `A1` within the string `"123456789,()=MINORFADEOMEN` (the `"""` at the beginning is to escape the character and will evaluate to just `"`).

Based on the result of `Find()`, the `Mid()` function will return the corresponding character from the string of numbers. This string was created through iteration until it stopped changing.

If the character in `A1` is not found, `Find()` returns an error so the `IfError()` function escapes that to return `0` instead.

The `OMEN` at the end of the string being searched in the `Find()` function are duplicate letters so their position will never be returned but they were needed to adjust the character counts. Without them, there was an endless loop of changing counts. The letter arrangement is stylistic choice.

# Answer
> 5 votes
# Retina, 1 byte

This wouldn't be valid if following strictly the quine rules, but the OP explicitely allowed it in a comment.

```
x

```

Try it online!

In retina a single-line program counts the occurrences of that regex in the input. This challenge is solved by any single ASCII character except ```, `.`, `+`, `*`, `?`, `[`, `(`, `)`, `^`, `$`, `\` and newline.

# Answer
> 5 votes
# JavaScript (ES6), 70 bytes

Doesn't read the source of the function, but this is quite long. Takes input as a 1-character string.

```
i=>~(n='\\34=\'in(|)0257?:.>[]Odefx~'.indexOf(i))?'3733544333'[n]||2:0

```

Try it online!

# Answer
> 5 votes
# C# (Visual C# Compiler), ~~88~~ 57 bytes

```
x=>"\\\"(())==>>??..::3300CCaaiinoossttx".Contains(x)?3:0

```

Try it online!

Returns **3** if the string contains the passed char, otherwise returns 0. The string contains each character of the code atleast once and exactly the amount required to have the char **3** times in the code.

-31 bytes thanks to Kevin Cruijssen

# Answer
> 4 votes
# Haskell, 66 bytes

The first two versions are essentially a quine which filters the required characters and then takes the length:

```
q c=length.filter(==c)$id<>show$"q c=length.filter(==c)$id<>show$"

```

Try it online or test with all characters!<sup>*</sup>

---

### Alternative without `(<>)`, 72 bytes

```
q c=length.filter(==c)$(++)<*>show$"q c=length.filter(==c)$(++)<*>show$"

```

Try it online or test with all characters!

---

### Non-quine alternative, ~~87~~ 86 bytes

Might still be improved, but I'm happy that I got it down to only three different groups.

I like this one the best, even though it counts the most bytes. It's computes the character/byte count by as a sum of *2,3* and *7* (note how some characters are in multiple groups):

```
u t=sum[fst e|e<-[(2," ()-237<=dflnst|"),(3," ()[\\]`mstu"),(7,"\",ee")],t`elem`snd e]

```

Try it online or test with all characters!

---

<sup>* imports `(<>)` because TIO's GHC version is 8.0.2</sup>

# Answer
> 3 votes
# Java 10, ~~164~~ ~~81~~ 57 bytes

```
q->"q-->>\\\"..ccoonttaaiiss(())??33::00".contains(q)?3:0

```

Port of *@Hyarus*' C# answer, so make sure to upvote him!

**Explanation:**

Try it online.

```
q->      // Method with String parameter and integer return-type
  "q->\\\"..ccoonttaaiiss(())??33::00".contains(q)?
         //  If the string above contains the input character
   3     //   Return 3
  :      //  Else:
   0     //   Return 0

```

---

**Old 164-bytes answer:**

```
c->{var s="c->{var s=%c%s%1$c;return s.format(s,34,s).replaceAll(%1$c[^%1$c+c+']',%1$c%1$c).length();}";return s.format(s,34,s).replaceAll("[^"+c+']',"").length();}

```

**Explanation:**

Try it online.

```
c->{                                  // Method with char parameter and integer return-type
  var s="c->{var s=%c%s%1$c;return s.format(s,34,s).replaceAll(%1$c[^%1$c+c+']',%1$c%1$c).length();}";
                                      //  Unformatted source code
  return s.format(s,34,s)             //  Create the formatted source code (the quine),
          .replaceAll("[^"+c+']',"")  //  remove all characters not equal to the input,
          .length();}                 //  and return the length

```

-part:

* The String `s` contains the unformatted source code.
* `%s` is used to input this String into itself with the `s.format(...)`.
* `%c`, `%1$c` and the `34` are used to format the double-quotes.
* `s.format(s,34,s)` puts it all together

Challenge part:

* `.replaceAll("[^"+c+']',"")` removes all characters except those equal to the input.
* `.length()` then takes the length of this String.

---

NOTE: `.split(c).length` (with `String` input instead of `char`) may seem shorter, but has two problems:

1. The first character gives an incorrectly result, so if `c` (with `c->` as leading part) is input, it will incorrectly return one character too few. This can be fixed by adding `+(c==99?1:0)` in both the source code and unformatted source code String (and changing `.split(c)` to `.split(c+"")`, but then we still have the following problem:
2. If a regex character (i.e. `$`) is input, the `.split` will interpret it as a regex, giving an incorrect result.

# Answer
> 3 votes
# Husk, ~~11 10~~ 8 bytes

Thanks Leo for -2 bytes!

```
#sD"#sD"

```

Try it online!

### Explanation

This makes sure that it only uses ASCII (because `show` would mess it up) and that each character is contained twice:

```
#sD"#sD"  -- character as input, eg. '"'
   "#sD"  -- string literal (note the redundant '"'): "#sD"
  D       -- double: "#sD#sD"
 s        -- show: "\"#sD#sD\""
#         -- number of occurences: 2

```

## Standard quine extension, 11 bytes

```
#hS+s"#hS+s

```

Try it online!

### Explanation

```
#hS+s"#hS+s  -- character as input, eg. '"'
     "#hS+s  -- string literal: "#hS+s"
  S+         -- join with itself: ("#hS+s"++)
    s        -- | and itself shown: "\"#hS+s\""
             -- : "#hS+s\"#hS+s\""
 h           -- init: "#hS+s\"#hS+s"
#            -- number of occurences in string: 1

```

# Answer
> 3 votes
# Python 2, ~~54~~ ~~52~~ 32 bytes

<sup>-20 bytes thanks to ovs</sup>

```
("''+.23cnotu()"*2+'"*'*3).count

```

Try it online!

# Answer
> 3 votes
# Haskell, 58 bytes

```
f c=sum[2|x<-succ '!':"f c=sum[2|x<-succ '!':,x==c]",x==c]

```

Try it online! or verify the solution.

Same byte count alternatives:

```
f c=sum[2|x<-tail$show"f c=sum[2|x<-tail$show,x==c]",x==c]
f c=sum[1|x<-id<>show$"f c=sum[1|x<-id<>show$,x==c]",x==c]

```

---

### Haskell, 90 bytes

```
sum.($zip"1234\"$,.[\\]opu+()iklmsz652"$[4,4,11,3,3,3,16,5,3,3,3,3,3,3,3]++[2,2..]).lookup

```

Try it online! or verify the solution. Uses the fact that `sum Nothing = 0` and e.g. `sum (Just 4) = 4`.

# Answer
> 3 votes
# Smalltalk, 112 ~~132~~ bytes

Smalltalk isn't exactly known for its golfing suitability :-)

Method defined in class Character (tested in VA Smalltalk and Squeak, should work in other dialects such as VisualWorks and Pharo as well):

```
a^(0to:6),#(10 18)at:(#('' ',[]^|+68cForu' '#0adefln' '1it' '()' ':s' ' ' '''')findFirst:[:s|s includes:self])+1

```

Characters occurring in the source are grouped by occurrence count. The groups are tested for the first one which contains the receiver, and the matching occurrence count is returned.

### Old method:

```
a^('''''((((())))):::[[[[]]]]^^^^^0000066666aaaacccccdddddeefffFFFFFiiilllnnnnnrrrrrsssTTTTTuuuu'includes:self)ifTrue:[6]ifFalse:[0]

```

Every character that does appear in the method appears exactly 6 times (by being repeated in the string constant), so the method just checks whether the receiver is contained in the string and returns 6 if it is, 0 otherwise.

After defining the method as above, you can validate it using

```
| code |
code := Character sourceCodeAt: #a.
((0 to: 255) collect: [:b | b asCharacter]) reject: [:c | c a = (code occurrencesOf: c)]

```

The result should be empty.

# Answer
> 2 votes
# JavaScript, 31 bytes

```
f=c=>~-`f=${f}`.split(c).length

```

Try it online

# Answer
> 2 votes
# Python 2, 57 bytes

```
lambda c,s='lambda c,s=%r:(s%%s).count(c)':(s%s).count(c)

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 17 bytes

```
2"D34çýs¢"D34çýs¢

```

Try it online!

# Answer
> 2 votes
# x86 .COM, 17 bytes, controversial

```
0120 BF2001        MOV     DI,0120 (120 be the current address)
0123 B91100        MOV     CX,0011
0126 AE            SCASB
0127 7502          JNZ     012B
0129 FEC4          INC     AH
012B E2F9          LOOP    0126
012D C1E808        SHR     AX,8
0130 C3            RET

```

# 36 bytes

```
0100 BF????        MOV     DI,(an copy of this code)
0103 B91200        MOV     CX,0012
0106 AE            SCASB
0107 7503          JNZ     010C
0109 80C402        ADD     AH,02
010C E2F8          LOOP    0106
010E C1E808        SHR     AX,8
0111 C3            RET

```

# Answer
> 2 votes
# Haskell, 96 bytes

```
n"n"=15;n"="=14;n" "=2;n";"=13;n"\\"=3;n"\""=25;n"0"=2;n"1"=4;n"2"=4;n"3"=4;n"4"=5;n"5"=5;n n3=0

```

Try it online!

# Haskell, 109 bytes

```
n 'n'=15;n '='=14;n ' '=14;n ';'=13;n '\\'=3;n '\''=25;n '0'=2;n '1'=5;n '2'=4;n '3'=4;n '4'=5;n '5'=5;n n3=0

```

Try it online!

# Haskell, 122 bytes

```
n 'n'=21
n '='=14
n ' '=14
n '\n'=12
n '\\'=4
n '\''=32
n '0'=2
n '1'=5
n '2'=5
n '3'=3
n '4'=5
n '5'=5
n nnnnnn4'''''''=0

```

Try it online!

# Explanations

These answers are not terribly sophisticated. It is a series of declarations, one for each character present in the program. At the end we have a catch all that returns 0 for characters not present in the program.

I use a couple of tricks to minimize the number of characters necessary in the program and from there I fiddled with things until the numbers turned out just right. You can see that I've padded the variable name in the last declaration, in all 3 of them. The difference between the 3 programs is whether I chose to use a new line or `;` for line breaks and whether I chose to take Chars as input or Strings. The `;` approach doesn't seem inherently superior to the others it just gets luck and ends up shorter, however it does seem that using Strings is a better idea than Chars because Chars require spaces after the function name an Strings do not.

# Answer
> 2 votes
# Whitespace, 140 bytes

```
[S S S N
_Push_0][S N
S _Duplicate][S N
S _Duplicate][T N
T   S _Read_STDIN_as_character][T   T   T   _Retrieve][S S S T  S S T   N
_Push_9][T  S S T   _Subtract][S N
S _Duplicate][N
T   S S T   N
_If_0_Jump_to_Label_TAB][S S S T    N
_Push_1][T  S S T   _Subtract][S N
S _Duplicate][N
T   S S N
_If_0_Jump_to_Label_NEWLINE][S S S T    S T T   S N
_Push_22][T S S T   _Subtract][N
T   S T N
_If_0_Jump_to_Label_SPACE][N
S T N
_Jump_to_Label_PRINT][N
S S S T N
_Create_Label_TAB][S S S T  S S T   S T N
_Push_37][N
S T N
_Jump_to_Label_PRINT][N
S S S N
_Create_Label_NEWLINE][S S S T  S S S S T   N
_Push_33][N
S T N
_Jump_to_Label_PRINT][N
S S T   N
_Create_Label_SPACE][S S S T    S S S T T   S N
_Push_70][N
S S N
_Create_Label_PRINT][T  N
S T _Print_as_integer]

```

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

70 spaces, 37 tabs, and 33 new-lines used.

Usually I use the Create Labels in the order `NSSN`, `NSSSN`, `NSSTN`, `NSSSSN`, `NSSSTN`, `NSSTSN`, `NSSTTN`, etc. But because printing a number where the binary `S=0`/`T=1` is used affects the number I need to output, I used the labels `NSSN`, `NSSSN`, `NSSTN`, and `NSSSTN` instead, which gave the perfect amount of spaces/tabs to be printed with the binary numbers `SSSTSSSSTN` (33; amount of new-lines), `SSSTSSTSTN` (37; amount of tabs), and `SSSTSSSTTSN` (70; amount of spaces).

### Explanation in pseudo-code:

```
Character c = STDIN-input as character
If c is a tab:
  Print 37
Else if c is a new-line:
  Print 33
Else if c is a space:
  Print 70
Else
  Print 0

```

### Example runs:

**Input: space**

```
Command       Explanation                   Stack       Heap     STDIN   STDOUT   STDERR

SSSN          Push 0                        [0]
SNS           Duplicate top (0)             [0,0]
SNS           Duplicate top (0)             [0,0,0]
TNTS          Read STDIN as character       [0,0]       {0:32}   \n
TTT           Retrieve                      [0,32]      {0:32}
SSSTSSTN      Push 9                        [0,32,9]    {0:32}
TSST          Subtract top two (32-9)       [0,23]      {0:32}
SNS           Duplicate top (23)            [0,23,23]   {0:32}
NTSSTN        If 0: Jump to Label_TAB       [0,23]      {0:32}
SSSTN         Push 1                        [0,23,1]    {0:32}
TSST          Subtract top two (23-1)       [0,22]      {0:32}
SNS           Duplicate top (22)            [0,22,22]   {0:32}
NTSSN         If 0: Jump to Label_NEWLINE   [0,22]      {0:32}
SSSTSTTSN     Push 22                       [0,22,22]   {0:32}
TSST          Subtract top two (22-22)      [0,0]       {0:32}
NTSTN         If 0: Jump to Label_SPACE     [0]         {0:32}
NSSTN         Create Label_SPACE            [0]         {0:32}
SSSTSSSTTSN   Push 70                       [0,70]      {0:32}
NSTN          Jump to Label_PRINT           [0,70]      {0:32}
NSSN          Create Label_PRINT            [0,70]      {0:32}
TNST          Print as integer              [0]         {0:32}            70
                                                                                error

```

Program stops with an error: No exit defined.
Try it online (with raw spaces, tabs, and new-lines only).

**Input: tab**

STDIN will be `\t` (`9`) instead, in which case it will be `0` at the first `If 0` check, goes to `LABEL_TAB`/`NSSSTN`, and will push and print `37` instead.

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

**Input: new-line**

STDIN will be `\n` (`10`) instead, in which case it will be `0` at the second `If 0` check, goes to `Label_NEWLINE`/`NSSSN`, and will push and print `33` instead.

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

**Input: anything else**

Any other input-character will do `NSTN` (Jump to Label\_PRINT) after the third `If 0` check, printing the `0` that was still on the stack (which we've duplicated at the very beginning).

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

# Answer
> 2 votes
# Japt, 27 bytes

```
\Ua"" a a a " ÄU\\\"a "aU Ä
            " ÄU\\\"a "     // Given this string literal,
                       aU   // find the last index of the input
                          Ä // and add +1.
\Ua"" a a a                 // Do nothing useful, but make the results match.

```

Longer than the existing Japt answer, but uses a different approach.
Has the inherent limitation that all chars need to occur a unique number of times.

Takes input as a string.

Try it online!

# Answer
> 2 votes
## Perl, 130 bytes

```
+print+0+((0)x40,6,6,0,3,43,0,0,0,22,12,6,3,5,2,4,0,1,0,0,0,1,0,1,(0)x28,1,0,1,(0)x6,1,(0)x4,1,(0)x4,1,1,1,0,2,0,1,0,0,0,5)[ord<>]

```

Has no newline or other whitespace. Reads a line from the standard output, but only cares about its first bytes, then prints the number of times that byte occurs in its own source code in decimal, without a newline.

The program is straightforward. Most of the source code is occupied by a literal table that gives the answer for the each possible byte. Trailing zeros are omitted, and adjacent zeros are run-time compressed, but there's no special trick other than that. The rest of the program simply reads the input and looks up the answer in the table.

For example, the part `22, 12, 6, 3, 5, 2, 4, 0, 1, 0` in the source code gives the frequency of digits, so there are 22 zeroes, 12 ones, 6 twos etc in the source code. As a result, if you enter `0` to the standard input of the program, the program will print `22`.

# Answer
> 2 votes
# C (gcc), 1033 bytes

```
#include <stdio.h>
int main(int argc,char *argv[]){int r=0*14811;switch((int)argv[1][0]){case' ':r=6;break;case'"':r=3;break;case'#':r=2;break;case'%':r=2;break;case'\'':r=101;break;case'(':r=5;break;case')':r=5;break;case'*':r=5*1*1;break;case'.':r=2;break;case':':r=51;break;case';':r=103;break;case'<':r=2;break;case'=':r=52;break;case'>':r=2;break;case'[':r=4;break;case'\\':r=3;break;case']':r=4;break;case'0':r=11;break;case'1':r=20;break;case'2':r=20;break;case'3':r=9;break;case'4':r=7;break;case'5':r=12;break;case'6':r=3;break;case'7':r=2;break;case'8':r=5;break;case'9':r=2;break;case'a':r=106;break;case'b':r=51;break;case'c':r=55;break;case'd':r=4;break;case'e':r=102;break;case'f':r=2;break;case'g':r=4;break;case'h':r=4;break;case'i':r=10;break;case'k':r=51;break;case'l':r=2;break;case'm':r=2;break;case'n':r=8;break;case'o':r=2;break;case'p':r=2;break;case'r':r=108;break;case's':r=53;break;case't':r=8;break;case'u':r=2;break;case'v':r=3;break;case'w':r=2;break;case'{':r=3;break;case'}':r=3;break;}printf("%d",r);}

```

Try it online!

This is by NO means a golfed answer, but it was fun to try to accomplish this challenge in a language which I am not familiar with. It wasn't a particularly difficult challenge until it came time to find the occurrences of the digits, now THAT was a challenge. Had to do a little creative balancing :)

# Answer
> 2 votes
# C (gcc), 192 bytes

```
F(J){J=J-70?J-40?J-41?J-74?J-'{'?J-'}'?J-39?J-48?J-49?J-50?J-51?J-52?J-53?J-54?J-55?J-56?J-57?J-47?J-61?J-63?J-45?J-58?J-59?0:1:23:23:23:1:2:3:3:4:4:14:14:10:10:15:6:4:2:2:25:1:1:1;}//84332211

```

Try it online!

Probably possible to golf down further. Uses a comment at the end as a 'scratch space' to add extra digits. When I have to change a digit from X to Y, I change one of the Y's in the scratch to an X to compensate. Other than that this is just a function that takes an integer, using the assignment trick to return a value based on a large ternary conditional.

# Answer
> 2 votes
# APL (Dyalog Classic), 30 bytes

```
⊢⊢⊢11-11-11-'''''''1''⊢-⍳⍳0'⍳⊢

```

Try it online!

## Explanation

In APL, single quotes within strings are escaped by doubling, so `'''''''1''⊢-⍳⍳0'` is the string `'''1'⊢-⍳⍳0`, which contain every character used in the program.

APL arrays are by default 1-indexed, and the index-of function, interestingly, returns `1 + max index` if the element is not found.

So, by using index-of on the string and the input returns

```
Input    Index    Count
'        1        10
1        4        7
⊢        6        5
-        7        4
⍳        8        3
0        10       1
<other>  11       0

```

As one can see, `11 - index` gives the count of the character in the program. So, the basic algorithm is

```
11-'''''''1''⊢-⍳⍳0'⍳⊢

```

The rest is bloating the character counts to allow them to fit nicely into the slots.

# Answer
> 1 votes
# Japt, 14 bytes

```
Qi"QiUè² " ²èU

```

Try it

---

## Explanation

```
                   :Implicit input of character string U
  "QiUè² "         :String literal
Qi                 :Append a quotation mark
           ²       :Repeat twice
            èU     :Count the occurrences of U

```

# Answer
> 1 votes
# , 12 bytes

```
ñéÑ~"qpxøÖa

```

Try it online!

Hexdump:

```
00000000: f1e9 d17e 2271 7078 f8d6 1261            ...~"qpx...a

```

# Answer
> 1 votes
# x86, ~~42~~ 40 bytes

Here I use the same strategy as others: Create a string copy of the program with unique bytes, then return 2 in `al` if the input `al` is in the string. If we allow ourselves to read code that is actually run, we get l4m2's solution.

I got to make use of a cool string instruction `scasb`. To the best of my knowledge, there are no duplicate bytes, but this is something I'd easily screw up. Loading the string address takes 5 bytes but I'm not aware of any shorter solution (64-bit `lea` of `rip` with offset takes 6 bytes).

-2 by jumping backwards to avoid using `02` twice.

```
.section .text
.globl main
main:
        mov     $0xff, %eax

start:
        push    $20             # program length
        pop     %ecx            # counter
        mov     $str, %edi      # load string

loop:
        scasb                   # if (al == *(edi++))
        jne     loop1
        mov     $2, %al         # ret 2
end:    ret
loop1:
        loop    loop            # do while (--counter)
        xor     %eax, %eax      # ret 0
        jmp     end

str:    .byte 0x6a,0x14,0x59,0xbf,0xf4,0x83,0x04,0x08
        .byte 0xae,0x75,0x03,0xb0,0x02,0xc3,0xe2,0xf8
        .byte 0x31,0xc0,0xeb,0xf9

```

Hexdump (of binary file format elf32-i386, as obj file unfortunately has `00` bytes for `str` address):

```
000003e0  6a 14 59 bf f4 83 04 08  ae 75 03 b0 02 c3 e2 f8  |j.Y......u......|
000003f0  31 c0 eb f9 6a 14 59 bf  f4 83 04 08 ae 75 03 b0  |1...j.Y......u..|
00000400  02 c3 e2 f8 31 c0 eb f9                           |....1...|

```

---

# x86, 256 bytes

Boring answer that is the equivalent of a giant comment. Input in `cl`, immediately returns 1 in `al`. I'll make an actual answer when I have the free time.

```
00000039  b0 01 c3 00 02 03 04 05  06 07 08 09 0a 0b 0c 0d  |................|
00000049  0e 0f 10 11 12 13 14 15  16 17 18 19 1a 1b 1c 1d  |................|
00000059  1e 1f 20 21 22 23 24 25  26 27 28 29 2a 2b 2c 2d  |.. !"#$%&'()*+,-|
00000069  2e 2f 30 31 32 33 34 35  36 37 38 39 3a 3b 3c 3d  |./0123456789:;<=|
00000079  3e 3f 40 41 42 43 44 45  46 47 48 49 4a 4b 4c 4d  |>?@ABCDEFGHIJKLM|
00000089  4e 4f 50 51 52 53 54 55  56 57 58 59 5a 5b 5c 5d  |NOPQRSTUVWXYZ[\]|
00000099  5e 5f 60 61 62 63 64 65  66 67 68 69 6a 6b 6c 6d  |^_`abcdefghijklm|
000000a9  6e 6f 70 71 72 73 74 75  76 77 78 79 7a 7b 7c 7d  |nopqrstuvwxyz{|}|
000000b9  7e 7f 80 81 82 83 84 85  86 87 88 89 8a 8b 8c 8d  |~...............|
000000c9  8e 8f 90 91 92 93 94 95  96 97 98 99 9a 9b 9c 9d  |................|
000000d9  9e 9f a0 a1 a2 a3 a4 a5  a6 a7 a8 a9 aa ab ac ad  |................|
000000e9  ae af b1 b2 b3 b4 b5 b6  b7 b8 b9 ba bb bc bd be  |................|
000000f9  bf c0 c1 c2 c4 c5 c6 c7  c8 c9 ca cb cc cd ce cf  |................|
00000109  d0 d1 d2 d3 d4 d5 d6 d7  d8 d9 da db dc dd de df  |................|
00000119  e0 e1 e2 e3 e4 e5 e6 e7  e8 e9 ea eb ec ed ee ef  |................|
00000129  f0 f1 f2 f3 f4 f5 f6 f7  f8 f9 fa fb fc fd fe ff  |................|

```

# Answer
> 1 votes
# Jelly, 16 bytes

```
“;⁾w⁸a2”;⁾“”w⁸a2

```

Try it online!

Every character appears exactly twice.

```
“;⁾w⁸a2”;⁾“”w⁸a2
“;⁾w⁸a2”;⁾“”     the string ;⁾w⁸a2“”
            w⁸a2 return 2 if input in string

```

# Answer
> 1 votes
# , 135 bytes

Inspired by this Python answer.

Previous versions were broken. Thanks to @Giuseppe for pointing out that `paste` was not required it saved 18 bytes or so. `lengths(regmatches(z,gregexpr(x,z)))`is from this answer.

```
function(x,z=rep(c("afilo2679=:","hmpu15'","nstxz","cgr","e","()",'"',","),c(2:5,7,9,15,16)))sum(lengths(regmatches(z,gregexpr(x,z))))

```

Try it online!

# Answer
> 0 votes
# Pari/GP, 36 bytes

```
f=(x)->#[x|c<-Vec(Str("f=",f)),x==c]

```

Try it online!

# Answer
> 0 votes
# Ruby, 48 bytes

```
->x{%q[->x{%q[].count(x.chr)*2}].count(x.chr)*2}

```

`%q[str]` is a more convenient way to write a string literal than `"str"` because it can be nested inside itself without any escaping. So I just put the entire code except for the copy inside it, then double the count.

# Answer
> 0 votes
# Jelly, ~~12~~ 10 bytes

```
“;Ṿċƈ”;Ṿċƈ

```

Try it online!

Reads a character from STDIN.

**12 bytes**

```
Ḣ“Ḣċ;Ṿ¤”;Ṿ¤ċ

```

Try it online!

Using input from command line argument.

Also 12 bytes:

```
ẇ“Ṿẇ¤Ḥ”Ṿ¤Ḥ“”

```

Try it online!

# Answer
> 0 votes
# \>\<\>, 19 bytes

```
'0d3*{:}=+l2=?n$40.

```

Try it online!

Takes input via the `-s` flag. Uses the standard \>\<\> quine format, counting how many occurrences of the character are present in the program.

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


title: Word Search on a Torus

text:
# Question
Title: Word Search on a Torus
# The Challenge

Given a list of words and a grid of letters, your job is to determine which of the given words can be found on the grid in all 8 directions (forward, backward, up, down, and the 4 diagonal directions), much like a word search. The grid is toroidal, so the grid wraps around on the edges. Letters can be reused with this wrap-around property.

Wrapping around for diagonals behaves as you might expect. On a 4x6 grid going diagonally down and right, you would expect movement to look like this:

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

```

For an example of a wrap-around reuse word:

```
S E A H O R

```

Would be able to make SEAHORSE

# Example Test Cases

Given this grid and the word list \[ANT, COW, PIG\]:

```
A N T
W C O
P G I

```

The result would be \[ANT, COW, PIG\]

---

Given this grid and the word list \[CAT, DOG, DUCK, GOOSE, PUMPKIN\]:

```
N O O D M E
O I O C U U
P G K O T C
K A U P S K

```

The result would be \[DOG, DUCK, PUMPKIN\]

---

Given this grid and the word list \[TACO, BEEF, PORK\]:

```
T A C B
A P O R
K E E F
B F C P

```

The result would be an empty list

---

Given this grid and the word list \[ACHE, ASK, BAD, BOOK, COOK, CROW, GAS, GOOD, LESS, MARK, MASK, MEAL, SAME, SEAHORSE, SELL, SHOW, SLACK, WOOD\]:

```
G S L A C K
H A E S R O
C M S K O O
A K S D W B

```

The result would be \[ASK, BOOK, COOK, CROW, GAS, GOOD, LESS, MASK, SEAHORSE, SHOW, SLACK\]

---

Given this grid and a list of all English words that are at least 3 letters long:

```
A R T U P
N T U B O
E S R O H
Q E T I U
E A T D P

```

The result would be \[AEQ, AES, ANE, ART, ARTS, ATRIP, BOID, BON, BREE, BUD, BUT, DUB, DUE, DUET, EAN, EAR, EAT, EER, EST, HES, HIT, HOP, HOR, HORS, HORSE, HUP, NAE, NOB, NOBUT, ONT, OOT, OPP, ORS, OUR, OUT, PAR, PART, PAT, PEA, PEAT, PEE, PEER, PIR, POH, PUT, QAT, QUI, QUIT, QUITE, RAP, REE, RIP, RIPA, RTI, RUT, SEA, SEAR, STD, STR, STRA, STRAE, SUU, TAA, TAE, TAP, TAPIR, TEE, TIU, TOO, TRA, TRAP, TRI, TRIP, TUB, TUP, TUR, UDI, UIT, URE, UTE\]

# Rules

* No exploiting standard loopholes
* This is , so shortest code wins
* Input and output may be in any convenient format
* You may assume that both the grid and the words list will use only capital letters
* The output order of the words does not matter
* You do not have to, but may, filter out duplicates

# Answer
> 3 votes
# Jelly, 25 bytes

```
Lẋ@Zɗ⁺ZU$3Ð¡;ŒD$€Ẏw€⁸ẸðÐf

```

A dyadic link accepting a list of lists of characters (the words) on the left and a list of lists of characters (the rows of the grid) on the right which returns a list of list of characters (the found words).

**Try it online!**

### How?

Filters the words by their existence in the grid tiled to be word-length times as wide and word-length times as high:

```
Lẋ@Zɗ⁺ZU$3Ð¡;ŒD$€Ẏw€⁸ẸðÐf - Link: words, grid
                       Ðf - filter (the words) keeping those for which
                      ð   - ...the dyadic link to the left ...is truthy:
     ⁺                    -   perform this twice:
    ɗ                     -     last three links as a dyad:
L                         -       length (of the current word)
 ẋ@                       -       repeat (the rows) by (that number)
   Z                      -       transpose (making the rows become the columns)
         3Ð¡              -   repeat three times and collect the results (inc input):
        $                 -     last two links as a monad:
      Z                   -       transpose
       U                  -       upend     (together these rotate by a quarter)
                €         -   for €ach:
               $          -     last two links as a monad:
             ŒD           -       get forward-diagonals
            ;             -       concatenate
                 Ẏ        -   tighten (to get all the runs across the grid)
                    ⁸     -   chain's left argument (the word)
                   €      -   for €ach run:
                  w       -     sublist-index (0 if not found)
                     Ẹ    -   any truthy? (i.e. was the word found?)

```

# Answer
> 1 votes
# JavaScript (Node.js), 269 214 164 163 bytes

-50 bytes with the golfing I learned since last year.
-1 byte thanks to Redwolf Programs

```
l=>g=>l.filter(w=>g.some((r,y)=>r.some((c,x,r,z=[-1,0,1],m=(a,b,c=b.length)=>(a%c+c)%c)=>z.some(l=>z.some(p=>[...w].every((h,i)=>h==g[m(l*i+y,g)][m(p*i+x,r)]))))))

```

Try it online!

old 214 bytes version:

```
(l,g)=>l.filter(w=>g.some((r,y)=>r.some((c,x,r,e=w.split``,m=(a,b)=>((a%b)+b)%b)=>[[0,1],[0,-1],[1,0],[-1,0],[1,1],[1,-1],[-1,1],[-1,-1]].some(v=>e.every((h,i)=>h==g[m(v[0]*i+y,g.length)][m(v[1]*i+x,r.length)])))))

```

Try it online!

Semi readable versoin:

```
(l, g) =>
    l.filter(w =>
        g.some((r, y) => //loop through rows
            r.some((c, x, r, e = w.split``, //loop through columns and split word in chars
                m = (a, b) => ((a % b) + b) % b) //modulo function which also works for negative
                =>
                [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]].some(v => //the different directions
                    e.every((h, i)
                        => h == g[m(v[0] * i + y, g.length)][m(v[1] * i + x, r.length)]
                    )
                )
            )
        )
    )

```

# Answer
> 1 votes
## Clojure, ~~203~~ 180 bytes

```
#(let[C count R range h(C %)w(C(% 0))](for[Q %2[y x][[1 0][0 1][-1 0][0 -1][1 1][1 -1][-1 -1][-1 1]]r(R h)c(R w):when(=(for[i(R(C Q))]((%(mod(+(* y i)r)h))(mod(+(* x i)c)w)))Q)]Q))

```

The grid must be a vector of vector of characters and the word list must be a sequence of sequence of characters. Sorry, no strings ;)

---
Tags: code-golf, string, grid
---


title: Nim Multiplication

text:
# Question
Title: Nim Multiplication
### Background

If you do much code golfing, you're likely aware of the bitwise XOR operation. Given two integers, it gives another integer with `1`s in the bits where the two inputs differ. So, for example, `1010 XOR 0011 = 1001`.

It turns out to be very useful in game theory, where it's better known as the "nim sum". If you have the sum of two games (that is, you're making moves in one game at a time), the value of the position is the nim sum of the values of the positions in each individual game.

But we can take this a step further. With nim addition and an appropriate definition of nim multiplication, we can form a field from the nonnegative integers. So the challenge is to golf nim multiplication.

### Definition

Nim multiplication obeys the following rules:
The nim product of a Fermat 2-power n = (2^(2^k)) with any smaller number is the ordinary product.
The nim product of a Fermat 2-power n with itself is 3n/2.
Nim multiplication distributes over nim addition.
Nim multiplication is commutative and associative (as is nim addition).
The multiplicative identity is 1 (and the additive identity is 0).

Any nonnegative integer can be written as the nim sum of distinct powers of two, and any power of two can be written as the product of distinct Fermat numbers, so this is sufficient to define nim multiplication for all nonnegative integers.

### Example

That was all pretty abstract, so let's work through an example. I'll use `+` to denote nim addition (XOR) and `*` for nim multiplication.

```
6 * 13
= (4 + 2) * (8 + 4 + 1)
= (4 + 2) * ((4 * 2) + 4 + 1)
= (4 * 4 * 2) + (4 * 2 * 2) + (4 * 4) + (4 * 2) + (4 * 1) + (2 * 1)
= (6 * 2) + (4 * 3) + 6 + 8 + 4 + 2
= ((4 + 2) * 2) + 12 + 6 + 8 + 4 + 2
= (4 * 2) + (2 * 2) + 12 + 6 + 8 + 4 + 2
= 8 + 3 + 12 + 6 + 8 + 4 + 2
= 15

```

### Additional Test Cases

```
4, 4 -> 6
4, 3 -> 12
4, 7 -> 10
2, 4 -> 8
2, 3 -> 1
1, 42 -> 42

```

### Challenge

Write a program or function which, given two nonnegative integers in any convenient form, computes their nim product.

This is , so shortest submission wins.

# Answer
# Nim, 120 bytes

```
proc f(a,b:int):int=
 var s={0..a*b}
 for i in 0..<a*b:s=s-{f(i%%a,i/%a)xor f(a,i/%a)xor f(i%%a,b)}
 for i in s:return i

```

Try it online!

OK, this might be crazy, but somebody had to do Nim multiplication in Nim...

This is standard algorithm from Wikipedia. The problem is that I don't know the language, so had to learn the basics on the fly. In particular, I was surprised that `-=` and `min` didn't work for sets, and the best way I managed to find for extracting the minimum was to use the iterator and return the first value. Hopefully, Nim experts will help me to improve this.
> 9 votes

# Answer
# Python 2, 85 bytes

```
f=lambda x,y:min(set(range(x*y+1))-{f(i%x,i/x)^f(x,i/x)^f(i%x,y)for i in range(x*y)})

```

Try it online!

Slow as heck. Computes mex({α′ β ⊕ α β′ ⊕ α' β′ : α′ \< α, β′ \< β}) recursively.
> 7 votes

# Answer
# Jelly, 16 bytes

```
p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ

```

Uses the recursive formula **xy = mex({ay ⊕ xb ⊕ ab : a \< x, b \< y})** for nimber multiplication.

Try it online!

### How it works

```
p’ß/;ß"^/ʋ€ṭ‘ḟ$Ṃ  Main link. Left argument: x. Right argument: y.

p                 Cartesian product; yield the array of all pairs [a, b] such that
                  0 < a ≤ x and 0 < b ≤ y.
 ’                Decrement, changing the conditions to 0 ≤ a < x and 0 ≤ b < y.
          ṭ       Tack; yield [y, x].
        ʋ€        Combine the four links to the left into a dyadic chain. Call it
                  with right argument [y, x] and each of the [a, b] as left one.
  ß/                  Reduce [a, b] by the main link, computing the product ab.
     ß"               Zip [a, b] with [y, x] using the main link, computing the
                      array of products [ay, xb].
    ;                 Concatenate, yielding [ab, ay, xb].
       ^/             Reduce by bitwise XOR, yielding ab ⊕ ay ⊕ xb.
                  All that's left is to compute the minimum excluded (mex) non-
                  negative integer.
             $    Combine the two links to the left into a monadic chain.
           ‘          Increment the XOR sums.
            ḟ         Filterfalse; remove all incremented sums that appear in the
                      original sums.
              Ṃ  Take the minimum if the resulting array is non-empty or yield 0.
                 If x = 0 or y = 0, the array of sums is empty and Ṃ yields 0.
                 If x > 0 and y > 0, since 0 is among the sums, this finds the
                 smallest non-sum n+1 such that n ≥ 0 is a sum.
                 In either case, Ṃ yields xy.

```
> 6 votes

# Answer
# CGSuite, ~~52~~ ~~39~~ 22 bytes

```
(a,b)->a.NimProduct(b)

```

Didn't realize it has this builtin, and anonymous "procedures".

Original version, 36 bytes:

```
(a,b)->*a.ConwayProduct(*b).NimValue

```

Or 25 bytes if the input/output could be nimbers:

```
(a,b)->a.ConwayProduct(b)

```

Well, I hoped `*a**b`/`a*b` to work, but it doesn't.
> 4 votes

# Answer
# Pyth, 21 bytes

```
Mf-TsmmxxgkdgkHgGdGH0

```

Demonstration

Uses the minimum excluded element formulation of nim multiplication, as given here.

Two nested maps are used to iterate over all smaller values (`mm ... GH`), then the results are flattened (`s`). The clever part comes with `f-T ... 0`, where we iterate over integers upward from 0 to find the first one not contained in the set mentioned above. By doing it this way, we don't need to calculate an iteration upper bound, saving a few bytes.

In the end, the function `g` computes the nim product.
> 3 votes

# Answer
## JavaScript (ES6), ~~142~~ 128 bytes

```
f=(x,y,z=Math.log2,v=x&-x,t=z(x),u=z(y),s=t&u,r=s&-s)=>x<2|y<2?x*y:x>v?f(v,y)^f(x^v,y):y&y-1?f(y,x):r?f(f(x>>r,y>>r),3<<r-1):x*y
```

```
<div oninput=o.textContent=f(x.value,y.value)><input id=x><input id=y><pre id=o>
```

The first step is to split both `x` and `y` into an XOR of powers of `2`, take their pairwise nim products, and then XOR the results (because nim product distributes over XOR). Once we have recursed to the case of `x` and `y` both powers of 2, we note that Fermat powers multiply with each other using ordinary arithmetic, so we can therefore factorise `x` and `y` into Fermat powers. If `x` and `y` don't share a Fermat power we can reverse the process and simply return `x * y`. However if they share a Fermat power, then we divide both `x` and `y` by that power, calculate the nim product, then take the nim product with the nim square of that Fermat power. Ungolfed:

```
function nimprod(x, y) {
    if (x < 2 || y < 2) return x * y;
    var v = x & -x;
    if (x > v) return nimprod(v, y) ^ nimprod(x ^ v, y); // nimprod distributes over ^
    if (y & (y - 1)) return nimprod(y, x); // x is a power of 2 but y is not
    var t = Math.log2(x);
    var u = Math.log2(y);
    var s = t & u;
    if (!s) return x * y; // x and y do not share a Fermat power
    var r = s & -s;
    return nimprod(nimprod(x >> r, y >> r), 3 << r - 1); // square the Fermat power
}

```
> 3 votes

# Answer
# Wolfram Language (Mathematica), 81 bytes

```
x_±y_:=Min@Complement[Range[0,x*y],##&@@Array[BitXor[x±#2,#±y,±##]&,{x,y},0]]

```

Try it online!

Using the formula:

\\$\alpha \beta = \operatorname{mex}(\\{\\,\alpha' \beta + \alpha \beta' + \alpha' \beta' : \alpha' \< \alpha , \beta' \< \beta \\,\\}).\\$
> 1 votes

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


# Question
Title: Generate all combinations of given list of elements, sorted
Make a code that takes a list and a number as input, and generates all possible combinations with the length of the number. For example, with the list **{0,1}** and the number **2**:

```
00
01
10
11

```

**Your program doesn't have to expect characters twice or more often in the list, such as** *{0,0,0,0,0,1,1,5,5}*

**Make sure you print the combinations out sorted, in the order of the list:**

With the list **{0,1}** and the number **5** (generated by some of my code, which is a way too long to win):

```
00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111

```

**But with the list *{1,0}* and the number *2*:**

```
11
10
01
00

```

As you can see, reversed list means reversed order.

Take a look at the structure, it's like a tree.

This is code-golf, so the shortest code in bytes wins!

# Answer
> 17 votes
# Jelly, 1 byte

**TryItOnline**

Cartesian power built-in atom, as a dyadic link with left argument the items and right argument the count, or as a full program with first argument the items and second argument the count.

# Answer
> 9 votes
## Haskell, 20 bytes

```
(mapM id.).replicate

```

Usage exaple:

```
*Main> ( (mapM id.).replicate )  2 "01"
["00","01","10","11"]
*Main> ( (mapM id.).replicate )  2 "10"
["11","10","01","00"]

```

`replicate` makes `n` copies of the 2nd parameter and `mapM id` builds the combinations. Btw, `mapM id` is the same as `sequence`, but 1 byte less.

# Answer
> 8 votes
# MATL, 2 bytes

```
Z^

```

Cartesian power builtin...

Try it online!

# Answer
> 6 votes
# Pyth, 2 bytes

```
^F

```

A program that takes input in the form `list,number` and prints a list of lists.

Test suite

**How it works**

```
^F   Program. Input: Q
^FQ  Implicit input fill
 F   Fold
^    repeated Cartesian power
  Q  over Q
     Implicitly print

```

# Answer
> 6 votes
# Perl 6, 15 bytes

```
{[X] @^a xx$^b}

```

## Explanation:

```
{[X] @^a xx$^b}

{             } # bare block lambda

     @^a        # declare first parameter as Positional
           $^b  # declare second parameter
         xx     # list repeat ｢@a｣, ｢$b｣ times

# at this point given ｢ (0,1), 5 ｣
# ((0 1) (0 1) (0 1) (0 1) (0 1))

 [ ]            # list reduce
  X             #    using cross meta-operator

# results in a list of lists
# ((0 0 0 0 0)
#  (0 0 0 0 1)
#  (0 0 0 1 0)
#  (0 0 0 1 1)
#  (0 0 1 0 0)
#  (0 0 1 0 1)
#  ...
#  (1 1 1 1 1))

```

```
say {[X] $^a xx$^b}( (0,1), 2 ); # ((0 0) (0 1) (1 0) (1 1))
say {[X] $^a xx$^b}( (1,0), 2 ); # ((1 1) (1 0) (0 1) (0 0))
say {[X] $^a xx$^b}( (0,1,2), 2 );
# ((0 0) (0 1) (0 2) (1 0) (1 1) (1 2) (2 0) (2 1) (2 2))

put {[X] $^a xx$^b}( (0,1), 5 )».join;
# 00000 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 11011 11100 11101 11110 11111

```

# Answer
> 5 votes
# JavaScript (Firefox 30+), 55 bytes

```
f=(a,n)=>n?[for(b of a)for(c of f(a,n-1))[b,...c]]:[[]]

```

I'm 99% certain recursion is the best way to go about this in JavaScript.

# Answer
> 5 votes
# Mathematica, 6 bytes

```
Tuples

```

Still worse than Jelly :(

# Usage

```
Tuples[{0, 1}, 5]

```

> `{{0, 0, 0, 0, 0}, {0, 0, 0, 0, 1}, {0, 0, 0, 1, 0}, {0, 0, 0, 1, 1}, {0, 0, 1, 0, 0}, {0, 0, 1, 0, 1}, {0, 0, 1, 1, 0}, {0, 0, 1, 1, 1}, {0, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 1, 0}, {0, 1, 0, 1, 1}, {0, 1, 1, 0, 0}, {0, 1, 1, 0, 1}, {0, 1, 1, 1, 0}, {0, 1, 1, 1, 1}, {1, 0, 0, 0, 0}, {1, 0, 0, 0, 1}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 1}, {1, 0, 1, 0, 0}, {1, 0, 1, 0, 1}, {1, 0, 1, 1, 0}, {1, 0, 1, 1, 1}, {1, 1, 0, 0, 0}, {1, 1, 0, 0, 1}, {1, 1, 0, 1, 0}, {1, 1, 0, 1, 1}, {1, 1, 1, 0, 0}, {1, 1, 1, 0, 1}, {1, 1, 1, 1, 0}, {1, 1, 1, 1, 1}}`

# Answer
> 4 votes
## Perl, 30 bytes

28 bytes of code + `-nl` flag.

```
$"=",";say for glob"{@F}"x<>

```

To run it:

```
perl -alE '$"=",";say for glob"{@F}"x<>' <<< "1 0
2"

```

I think that taking the input as a list of numbers is logical for Perl. However, if we allow some fantasy, and take the input with the brackets and comma (as shown in the question), we can go down to **20 bytes**:

```
perl -nlE 'say for glob$_ x<>' <<< "{1,0}
2"

```

**Explanations:** `glob` initial purpose in Perl is list and iterate through filenames, but when its argument contains curly brackets, it generates combinations formed of one element of each bracket group.
`-a` autosplit on spaces the input, and put the result inside `@F` array.
`$"` is the list separator: it's the separator inserted between the elements of a list inside a string. We set it to `,`, so `"{@F"}` produces `{.,.}` (if `@F` contains 0 and 1).
Then `x` is the string repetition operator (and `<>` gets one line of input).
And finally, `say for` iterates through the list generated by `glob` and prints the elements.

# Answer
> 3 votes
# Python, 57 bytes

```
from itertools import*
lambda o,n:list(product(*([o]*n)))

```

**repl.it**

Unnamed function taking a list of objects, `o` and a count, `n` and returning a list of the combinations.

# Answer
> 3 votes
# Pure Bash, 36

```
printf -vv %$2s
eval echo ${v// /$1}

```

Input by command-line params - The list is a comma-separated list in braces, e.g.:

```
./elemcombo.sh "{0,1}" 2

```

Note the input list needs to be quoted so the calling shell does not expand it too early.

Ideone.

# Answer
> 3 votes
# , ~~53~~ 45 bytes

```
function(x,n)rev(expand.grid(rep(list(x),n)))

```

Try it online!

`rev` is there to the conform with the precise sort order requested (which doesn't really seem essential to the problem) and adds 5 bytes.

# Answer
> 2 votes
# 05AB1E, ~~2~~ 1 byte~~s~~

```
ã

```

-1 byte thanks to *@Emigna*.

Try it online.

Input as `number\nlist`, output as list of lists.

**Explanation:**

```
     # Implicit input `a`, `b`
ã    # Take the Cartesian product of list `b` repeated `a` times

```

# Answer
> 1 votes
## Racket 123 bytes

```
(let p((s "")(l(map number->string(sort l <))))
(if(= n(string-length s))(displayln s)(for((i l))(p(string-append s i)l))))

```

Ungolfed:

```
(define(f l n)
  (let loop ((s "")
             (l (map number->string (sort l <))))
    (if (= n (string-length s))
        (displayln s)
        (for ((i l))
          (loop (string-append s i) l)))))

```

Testing:

```
(f '(0 1) 2)
(f '(0 1) 3)
(f '(0 1) 5)

```

Output:

```
00
01
10
11

000
001
010
011
100
101
110
111

00000
00001
00010
00011
00100
00101
00110
00111
01000
01001
01010
01011
01100
01101
01110
01111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111

```

# Answer
> 1 votes
# PHP, 109 bytes

```
for($o=$a=array_slice($argv,2);--$argv[1];$o=$c,$c=[])foreach($a as$n)foreach($o as$s)$c[]=$n.$s;print_r($o);

```

Takes the length as the first argument and the list as any further arguments.
Use like:

```
php -r "for($o=$a=array_slice($argv,2);--$argv[1];$o=$c,$c=[])foreach($a as$n)foreach($o as$s)$c[]=$n.$s;print_r($o);" 5 0 1

```

Will run into an "out of memory" fatal error if asked for length 0.

---
Tags: code-golf, combinatorics
---