title: Draw the lambda blazon

text:
# Question
Title: Draw the lambda blazon
To celebrate the 2497th anniversary of the Greek victory at Salamis in 480 BC. Draw the lambda blazon.

The lambda blazon was the lambda painted on greek shields like so:

**Puzzle:** Given a positive odd integer n, produce an ascii art image of the above shield.

**Specifications:**

**n=1:**

```
( /\ )

```

**n=3:**

```
(   /\   )
|  /  \  |
( /    \ )

```

**n=5**

```
(     /\     )
|    /  \    |
|   /    \   |
|  /      \  |
( /        \ )

```

**Graph:** **n=3**

```
          2|   (   /\   )
y-axis    1|   |  /  \  |
          0|   ( /    \ )
               ___________
               0123456789

                 x-axis

```

**Description:**

There should be exactly *n* `\` characters and *n* `/` characters. The `/`s and `\`s should not touch the edge of the shield. The bottom and top corners of the shield will be denoted with a `(` or `)` unless *n*=1 where there will be one `)` and one `(`. There will always be one space between the bottom corners and the lambda, increasing by 1 with the y axis until `y + 1 == n`. Non corners of the shield side will be denoted with `|`. There is no shield top.

# Answer
> 8 votes
# Charcoal,  ~~17~~  13 bytes

*Thanks to @Neil for saving 4 bytes!*

```
(↙↓⊖θＭ↑(→↗Ｎ‖Ｍ

```

Try it online!

**Explanation:**

```
(↙                // Print '(' and move one step down and to the left.
  ↓⊖θ             // Print n-1 '|'s downwards.
     Ｍ↑          // Move one step up.
        (→        // Print '(' and move one step to the right.
          ↗Ｎ      // Print n '/'s towards the upper right corner.
            ‖Ｍ    // Mirror the left half to produce the right half.

```

# Answer
> 6 votes
# SOGL V0.12, ~~17~~ 14 bytes

```
┐*ƨ(Κm«@.╚┼┼╬³

```

Try it Here!

Explanation:

```
example input: 3
┐*              push a string of input amount of "|"                      "|||"
  ƨ(            push "("                                                  "|||", "(("
    Κ           prepend that to the vertical bar string                   "((|||"
     m          mold that string as the input (remove excess characters)  "((|"
      «         put the first character at the end                        "(|("
       @        push a space                                              "(|(", " "
        .╚      create a diagonal of input length                         "(|(", " ", ["  /", " / ", "/  "]
          ┼┼    append those three horizontally together                  ["(   /", "|  / ", "( /  "]
            ╬³  palindromize that all

```

# Answer
> 4 votes
# C (gcc), ~~103~~ 96 bytes

```
f(n,j,b){for(j=n;j--;printf("%c%*c%*c%*c\n","|("[b],j+2,47,n+n-j+~j,92,j+2,"|)"[b=j<1|n-2<j]));}

```

Try it online!

# Answer
> 3 votes
# Retina, 41 bytes

```
.+
$*

( $'/$`$`\$' )¶
G`.
sT`()`|`¶.*¶

```

Try it online! Explanation:

```
.+
$*

```

Convert to unary, but using spaces.

```

( $'/$`$`\$' )¶

```

Use the match prefix and suffix operators to generate a series of lines with increasing amounts of centre space on each line.

```
G`.

```

However, there's an extra blank line, which throws off the final transliteration, so delete it here.

```
sT`()`|`¶.*¶

```

On all lines except the first and last, change the `()`s to `|`s.

# Answer
> 2 votes
# Perl 5, 91 + 1 (`-p`) = 92 bytes

```
$_='('.($s=$"x($q=$_))."/\\$s)";while(--$q){say;y/()/|/;s| /|/ |;s|\\ | \\|}s/\|/(/;s/\|/)/

```

Try it online!

# Answer
> 2 votes
# Java (OpenJDK 8), ~~200~~ ~~190~~ 170 bytes

```
n->{for(char i=0,s[];i<n;s[-~n-i]=47,s[2+n+i]=92,s[0]=i<1|i>n-2?40:'|',s[3+n+n]=i<1|i++>n-2?41:'|',System.out.println("".valueOf(s).replace('\0',' ')))s=new char[4+n+n];}

```

Try it online!

# Answer
> 2 votes
# Pyth, 43 bytes

This is quite gigantic given that it's been done on mobile :-/

```
j_m++++++@"(|"J!/,1QdK*;d\/*;y-Qd\\K@")|"JS

```

**Try it online!**

# Answer
> 2 votes
# Python 2, 85 bytes

```
n=a=input()
while a:print'(|'[1<a<n]+a*' '+'/'+(n-a)*'  '+'\\'+a*' '+')|'[1<a<n];a-=1

```

Try it online!

# Answer
> 2 votes
# , 153 bytes

```
function(n){s=2*n+4
m=matrix('|',s,n)
m[3:s-1,]=' '
m[cbind(5:s-2,c(n:1,1:n))]=1
m[1,c(1,n)]='('
m[s,c(1,n)]=')'
m[m>0]=rep(c('/','\\'),n)
rbind(m,'\n')}

```

Try it online!

# Answer
> 2 votes
## Batch, 218 bytes

```
@echo off
set s=
for /l %%i in (1,1,%1)do call set s= %%s%%
set s=%s%/\%s%
echo (%s%)
for /l %%i in (2,1,%1)do call:l %1 %%i
exit/b
:l
set s=%s: /=/ %
set s=%s:\ = \%
if %1==%2 (echo ^(%s%^))else echo ^|%s%^|

```

As if `|`s weren't bad enough, `()`s don't work well with `if`...`else`.

# Answer
> 2 votes
# 05ab1e (27 bytes)

```
F"|("0NQ¹<NQ~èð¹N-×'/ðN×J∞,

```

try it online

explanation

```
F                                                #Loop n times
 |("0NQ¹<NQ~è                                    #Use ( or |
             ð¹N-×                               #put spaces (1)
                  '/                             #put /
                    ðN×                          #put more space
                       J∞,                       #reverse image

```

# Answer
> 2 votes
# Funky, 101 bytes

```
n=>for(i=0;i<n;i++)print(((c=(i==n-1)or!i)?"(":"|")..(s=" "*n-i).."/"..(" "*i*2).."\\"..s..c?")":"|")

```

Try it online!

# Answer
> 1 votes
# Python 2, 90 bytes

```
n=input()
for i in range(n):m=-~i%n<2;s=' '*(n-i);print'|('[m]+s+'/'+'  '*i+'\\'+s+'|)'[m]

```

Try it online!

-1 thanks to ovs.

# Answer
> 1 votes
# Python 3, 110 bytes 93 bytes

```
b=c=int(input())*2
d,e='/\\'
while b:print('(|%%ss)|'[2<b<c::2]%f' {d+e:^{c}} ');d+='  ';b-=2

```

# Answer
> 1 votes
# C# (.NET Core), 188 bytes

```
n=>{int y=0,i=-1;var s="";while(y<n){var r=new char[n*2+4];r[n+1-y]='/';r[n+2+y]='\\';if(y<2|y++>n-2)i++;r[0]="(|("[i];r[n*2+3]=")|)"[i];s+=new string(r)+"\n";}return s.Replace("\0"," ");}

```

Try it online!

### Degolfed

```
n=>{
    int y=0,i=-1;
    var s="";

    while(y<n){
        var r=new char[n*2+4];
        r[n+1-y]='/';
        r[n+2+y]='\\';

        if(y<2 | y++>n-2)
            i++;

        r[0] = "(|("[i];
        r[n*2+3] = ")|)"[i];

        s += new string(r)+"\n";
    }

    return s.Replace("\0"," ");
}

```

# Answer
> 1 votes
# PowerShell, ~~93~~ ~~91~~ ~~90~~ 89 bytes

-2 Thanks to ASCII-only for pointing out extra parens
-1 Thanks to Mazzy for tweaking swap logic

```
param($n)0..--$n|%{"|("[!($x=($n-$_)*$_)]+($y=" "*($n-$_+1))+"/"+"  "*$_+"\$y"+"|)"[!$x]}

```

Try it online!

~~Trying to tweak that `$x=` bit. There's probably a smarter way to get the 1st and last line out in a few less bytes.~~ There is a better `$x=` but it isn't much cheaper.

# Answer
> 0 votes
# Canvas, 12 bytes

```
┤|×(ｅ⟳ ＋╴／＋║

```

Try it here!

Explanation:

```
┤             decrease the input by 2
 |×           repeat "|" vertically - if the amount is -1 (for input of 1), ir just removes the item currently
   (          push "("
    ｅ        encase in that parentheis - if that first string isn't there, currently it just fails doing anything and leaves the parenthesis on the stack
     ⟳       rotate clockwise
       ＋     append horizontally a space
        ╴／   get a diagonal the length of the input
          ＋  append it horizontally to the current result
           ║  and palindromize horizontally with 0 overlap

```

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


title: Count the Closed Polygons

text:
# Question
Title: Count the Closed Polygons
## Input:

An `NxM` grid or multi-line string (or other reasonable input-format), containing only printable ASCII (unicode range `[32,126]`).

## Output:

The amount of closed polygons of the same character that can be found, with two special rules:

* Spaces are wildcards and can be used (multiple times) for any character
* `o`, `O`, and `0` are counted as closed polygons themselves

## Challenge rules:

* (Anti-)Diagonal connections between the same characters (or spaces) are included to form closed polygons.
* You cannot go over other characters (except for the wild-card spaces). (I.e. in the first test case/example below, you cannot form two triangles with the `A`'s by going over the `x`.) So all characters used for a closed polygon should be connected (horizontally, vertically, and/or (anti-)diagonally).
* Polygons are at least three characters (excluding the single characters `o`, `O`, `0`).
* Lines of adjacent characters are not closed polygons.
* The same characters cannot be used for multiple polygons, excluding wildcard spaces.
* Wildcard spaces cannot be counted as `o`, `O`, or `0`.
* Three or more spaces alone cannot form a closed polygon. It should always have at least one non-space (and non `o`/`O`/`0`) character.
* Input can be in any reasonable format. Can be a character-matrix, new-line delimiter string, string-array, character-array with added integer width, etc.
* The inputs will always be an N by M rectangle (or square), so no weird input-shapes
* Since the same characters cannot be used more than once and we want to have as many closed polygons, using multiple characters to form two (or more) closed polygons instead of one larger polygon is of course the intended goal in the counting (which is also why closed polygons formed by `o`, `O`, or `0` will never be counted, since they are already closed polygons individually).
* Uppercase and lowercase letters are of course counted as individual characters.

## General rules:

* This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
* Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
* Default Loopholes are forbidden.
* If possible, please add a link with a test for your code (i.e. TIO).
* Also, adding an explanation for your answer is highly recommended.

## Examples / Test Cases:

Input:

```
AAAw
AxA4
'AoQ

```

Output: `2`, because these polygons can be formed:

---

Input:

```
1822uaslkoo
12*2sl ljoo
a* 0a91)j$*
()*#J9dddj*
*Q#ID dJj!"
*UJD SO&*93

```

Output: `12`, because these polygons can be formed:

Note that:
\- The yellow one below is not a polygon, because the `o`'s are already counted as separated polygons
\- The purple and brown ones aren't closed
\- The red, grey, green, and light-blue use one or more non-space characters that were already used for other closed polygons

---

Input (dimensions are `2x4`):

```
3  3
  2

```

Output: `3`, because these polygons can be formed:

---

Input:

```
AAAA
AAAA
AAxA

```

Output: `3`, because these polygons can be formed:

Of course other polygons are possible here, but no more than 3. Here another valid example with `3` polygons:

---

Input:

```
0QoO

```

Output: `3`, because these polygons can be formed:

---

Input:

```
W w
 Ww

```

Output: `3`, because these polygons can be formed:

Note that the top layer space is used for all three polygons. Here are the three polygons individually highlighted:

---

Input:

```
W W
 WW

```

Output: `3`, because the same three polygons as in the previous test can be formed. **So no, it's not `2` with these two polygons:**

---

Input:

```
abcdQefg
hQiQjQQk
QlQmnopQ
QqrstQQu
QvQQQwxy
QQz0QQQQ

```

Output: `3`, because these polygons can be formed:

# Answer
# Python 2, 714 ~~737~~ ~~821~~ bytes

* -23 bytes thanks to Kevin Cruijssen

```
M=input()
m=''.join(M)
def P(L):
 if len(L)<2:yield[L];return
 for p in P(L[1:]):
	for n,s in enumerate(p):yield p[:n]+[[L[0]]+s]+p[n+1:]
	yield[[L[0]]]+p
h,w,R,C=len(M),len(M[0]),0,[-1,0,1]
K=[(i,j)for i in range(h)for j in range(w)]
Z=[(i,j)for i,j in K if' '==M[i][j]]
from networkx import*
for l in set(m):
 G,S=[],[]
 if l in'oO0':R+=m.count(l);continue
 for I in K:
  i,j=I
  for p in C:
	for q in C:
	 X=x,y=i+p,j+q
	 if X in K and X!=I and set(M[i][j]+M[x][y])<=set(' '+l):G+=[(I,X)];S+=[I,X]
 B=0
 for L in P(list(set(S))):
  b=0
  for p in L:
	for i,j in p:
	 if' '!=M[i][j]:
		try:find_cycle(from_edgelist([(I,X)for I,X in G if I in p+Z and X in p+Z]));b+=1
		except:1
		break
	if b>B:B=b
 R+=B
print R

```

Try it online!

1. For each letter `A` (except `o`, `O`, and `0`) the code build a graph representing the adjacency of the different occurrences of letter `A` and space in the initial given matrix. Then it computes the set of semi-separated cycles covering the graph when maximizing the number of cycles (separation is based only on the letter `A`, the same space can be used for several cycles).
2. The code passes all tests.
3. Input: the list of lines of the matrix.
4. More explanation and golfing coming soon.
> 4 votes

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


title: Mid-Autumn Festival gambling game

text:
# Question
Title: Mid-Autumn Festival gambling game
Tomorrow is the Mid-Autumn festival, and in the spirit of that holiday, I will introduce a gambling game that we (people from Xiamen) play during the holiday!

# Rules

The game is played with six 6-sided dice. Different combinations of numbers have different ranks, with a special emphasis on fours and ones. Your job is to write a program/function that will rank the hand, given a roll of 6 dice. Here are the ranks (I've modified/simplified the rules a bit):

~~I guess only Chinese people can do this challenge!~~  Okay, fine, here are some English explanations.

* 0: 4 fours and 2 ones.
* 1: 6 fours.
* 2: 6 ones.
* 3: 6 of any kind except fours and ones.
* 4: 5 fours.
* 5: 5 of any kind except for fours.
* 6: 4 fours.
* 7: Straight. (1-6)
* 8: 3 fours.
* 9: 4 of any kind except 4.
* 10: 2 fours.
* 11: 1 four.
* 12: Nothing.

# Input

6 numbers, an array of 6 numbers, or a string of 6 numbers that represent the values of the 6 dice rolls from 1-6

# Output

Your program/function may return/output anything to indicate the rank, as long as each rank is indicated by one output and vice versa. Ex. Using the numbers 0-12, 1-13, etc.

# Examples(Using 0-12 as the outputs)

```
[1,1,1,1,1,1]->2
[1,4,4,4,1,4]->0
[3,6,5,1,4,2]->7
[1,2,3,5,6,6]->12
[3,6,3,3,3,3]->5
[4,5,5,5,5,5]->5

```

This is code-golf, so shortest byte count wins!

# Answer
# Charcoal, 55 bytes

```
≡⌈Ｅθ№θι⁶Ｉ⁻²⌕14§θχ⁵Ｉ⁻⁵⁼⁵№θ4⁴⎇⁼№θ4⁴§60⁼№θ1²9¹7Ｉ⁻¹²⌊⊘Ｘ²№θ4

```

Try it online! Link is to verbose version of code. Does not skip 10. Explanation:

```
≡⌈Ｅθ№θι

```

Calculate the highest frequency of any digit.

```
⁶Ｉ⁻²⌕14§θχ

```

If there is a 6 of a kind, then subtract the position of the digit in the string `14` from 2. This results in 1 for 6 4s, 2 for 6 1s, and 3 for 6 of anything else.

```
⁵Ｉ⁻⁵⁼⁵№θ4

```

If there is a 5 of a kind, then the result is 5 unless there are 5 4s, in which case 1 is subtracted.

```
⁴⎇⁼№θ4⁴§60⁼№θ1²9

```

If there is a 4 of a kind, then if there are 4 4s then the result is 6 unless there are 2 1s in which case the result is 0, otherwise the result is 9.

```
¹7

```

If all the digits are different then the result is 7.

```
Ｉ⁻¹²⌊⊘Ｘ²№θ4

```

Otherwise the result is 12 - (4 \>\> (3 - # of 4s)).
> 2 votes

# Answer
# JavaScript (ES6), 88 bytes

```
a=>a.map(o=n=>[x=o[n]=-~o[n],6,,,21,9,8^o[1]][a=x<a?a:x])[5]|[,1,4,5,o[1]&2|8,2,4][o[4]]

```

Try it online! or Test all possible rolls!

Outputs an integer according to the following mapping:

```
 Rank | Output       Rank | Output
------+--------     ------+--------
   0  |  31            7  |   7
   1  |  12            8  |   5
   2  |  14            9  |  21
   3  |   8           10  |   4
   4  |  11           11  |   1
   5  |   9           12  |   0
   6  |  29

```

## How?

### Method

The output is computed by performing a bitwise OR between:

* a bitmask based on \\$F\\$: the number of 4's
* a bitmask based on \\$M\\$: the maximum number of occurrences of the same dice

Exceptions:

* When \\$F=4\\$: we use a special bitmask \\$4b\\$ when the two other dice are 1's, or a default bitmask \\$4a\\$ otherwise.
* When \\$M=6\\$: we use a special bitmask \\$6b\\$ when we have a six-of-a-kind of 1's, or a default bitmask \\$6a\\$ otherwise.

### Table

Valid combinations of \\$F\\$ and \\$M\\$ are highlighted in bold and blue in the following table.

$$\begin{array}{c|c|cccccccc} &F&0&1&2&3&4a&4b&5&6\\ \hline M&\text{OR}&0&1&4&5&8&10&2&4\\ \hline 1&6&\color{grey}{6}&\color{blue}{\textbf{7}}&\color{grey}{6}&\color{grey}{7}&\color{grey}{14}&\color{grey}{14}&\color{grey}{6}&\color{grey}{6}\\ 2&0&\color{blue}{\textbf{0}}&\color{blue}{\textbf{1}}&\color{blue}{\textbf{4}}&\color{grey}{5}&\color{grey}{8}&\color{grey}{10}&\color{grey}{2}&\color{grey}{4}\\ 3&0&\color{blue}{\textbf{0}}&\color{blue}{\textbf{1}}&\color{blue}{\textbf{4}}&\color{blue}{\textbf{5}}&\color{grey}{8}&\color{grey}{10}&\color{grey}{2}&\color{grey}{4}\\ 4&21&\color{blue}{\textbf{21}}&\color{blue}{\textbf{21}}&\color{blue}{\textbf{21}}&\color{grey}{21}&\color{blue}{\textbf{29}}&\color{blue}{\textbf{31}}&\color{grey}{23}&\color{grey}{21}\\ 5&9&\color{blue}{\textbf{9}}&\color{blue}{\textbf{9}}&\color{grey}{13}&\color{grey}{13}&\color{grey}{9}&\color{grey}{11}&\color{blue}{\textbf{11}}&\color{grey}{13}\\ 6a&8&\color{blue}{\textbf{8}}&\color{grey}{9}&\color{grey}{12}&\color{grey}{13}&\color{grey}{8}&\color{grey}{10}&\color{grey}{10}&\color{blue}{\textbf{12}}\\ 6b&14&\color{blue}{\textbf{14}}&\color{grey}{15}&\color{grey}{14}&\color{grey}{15}&\color{grey}{14}&\color{grey}{14}&\color{grey}{14}&\color{grey}{14}\\ \end{array}$$

All other combinations (in gray) can't possibly happen. For instance, if we have three 4's, we must have \\$M\ge3\\$. But because there are only 3 other remaining dice in such a roll, we also have \\$M\le3\\$. So, there's only one possible value of \\$M\\$ for \\$F=3\\$.

### Example

If we have a straight, each dice appears exactly once. So we have \\$M=1\\$ and \\$F=1\\$. Using the bitmasks described in the above table, this leads to:

$$6 \text{ OR } 1 = 7$$

There is another \\$7\\$ in the table, but it's invalid. Therefore, a straight is uniquely identified by \\$7\\$.

## Commented

```
a =>                   // a[] = input array, reused as an integer to keep track of the
  a.map(               //       maximum number of occurrences of the same dice (M)
    o =                // o = object used to count the number of occurrences of each dice
    n =>               // for each dice n in a[]:
    [                  //   this is the lookup array for M-bitmasks:
      x =              //     x = o[n] = number of occurrences of the current dice
        o[n] = -~o[n], //     increment o[n] (we can't have M = 0, so this slot is not used)
      6,               //     M = 1 -> bitmask = 6
      ,                //     M = 2 -> bitmask = 0
      ,                //     M = 3 -> bitmask = 0
      21,              //     M = 4 -> bitmask = 21
      9,               //     M = 5 -> bitmask = 9
      8 ^ o[1]         //     M = 6 -> bitmask = 14 for six 1's, or 8 otherwise
    ][a =              //   take the entry corresponding to M (stored in a)
        x < a ? a : x] //   update a to max(a, x)
  )[5]                 // end of map(); keep the last value
  |                    // do a bitwise OR with the second bitmask
  [                    // this is the lookup array for F-bitmasks:
    ,                  //   F = 0 -> bitmask = 0
    1,                 //   F = 1 -> bitmask = 1
    4,                 //   F = 2 -> bitmask = 4
    5,                 //   F = 3 -> bitmask = 5
    o[1] & 2 | 8,      //   F = 4 -> bitmask = 10 if we also have two 1's, 8 otherwise
    2,                 //   F = 5 -> bitmask = 2
    4                  //   F = 6 -> bitmask = 4
  ][o[4]]              // take the entry corresponding to F (the number of 4's)

```
> 10 votes

# Answer
# , 100 bytes

Encode the score as a bunch of indexed conditionals. Simpler than my first stringy-regex approach.

Edit- fixed bug and now rank all rolls.

```
function(d,s=sum(d<2))min(2[s>5],c(11,10,8,6-6*!s-2,4,1)[sum(d==4)],c(7,12,12,9,5,3)[max(table(d))])

```

Try it online!
> 5 votes

# Answer
# JavaScript (Node.js), 169 bytes

```
a=>-~"114444|123456".search(w=a.sort().join``,[l,t]=/(.)\1{3,}/.exec(w)||[0],l=l.length)||(l>5?3-"14".search(t):l>3?4+(5.5-l)*(t-4?4:2):[,13,12,11,9][w.split`4`.length])

```

Try it online!

Returns `1..13`
> 2 votes

# Answer
# Python 2,  ~~148~~  119 bytes

-27 bytes thanks to ovs's (1. use of `.count` allowing a `map` to be used; 2. removal of redundant `0` in slice; 3. use of an `in` rather than a `max`; 4. shortened `(F==4)*O==2` to `F==4>O==2` \[since golfed to `F>3>O>1`\])

```
C=map(input().count,range(1,7))
O,F=C[::3]
print[F>3>O>1,F>5,O>5,6in C,F>4,5in C,F>3,all(C),F>2,4in C,F>1,F,1].index(1)

```

**Try it online!**
> 2 votes

# Answer
# Pyth, 60 bytes

```
eS[@[ZhZ2 4*6hq2hJuXtHG1Qm0Q8hT)@J3*5hSJ*Tq6hJ*<3KeSJ@j937TK

```

Maps to reversed rank, 0-12. Try it online here, or verify all the test cases at once here.

The full mapping used is as follows:

```
12: 4 fours and 2 ones.
11: 6 fours.
10: 6 ones.
 9: 6 of any kind except fours and ones.
 8: 5 fours.
 7: 5 of any kind except for fours.
 6: 4 fours.
 5: Straight. (1-6)
 4: 3 fours.
 3: 4 of any kind except 4.
 2: 2 fours.
 1: 1 four.
 0: Nothing.

```

This works by mapping the dice values to frequencies, then calculating the value of several rules, and taking the maximum of the set.

```
Implicit: Q=eval(input()), Z=0, T=10

JuXtHG1Qm0Q   Input mapping
 u     Q      Reduce each element of the input, as H, ...
        m0Q   ...with initial value, G, as an array of 6 zeroes (map each roll to 0)
   tH           Decrement the dice roll
  X  G1         Add 1 to the frequency at that point
J             Store the result in J

@[ZhZ2 4*6hq2hJuXtHG1Qm0Q8hT)@J3   Rule 1 - Values for sets including 4
  Z                               *0
   hZ                             *1 (increment 0)
     2                            *2
       4                          *4
              JuXtHG1Qm0Q          Input mapping (as above)
             h                     First value of the above - i.e. number of 1's
           q2                      1 if the above is equal to 2, 0 otherwise
        *6h                       *Increment and multiply by 6
                                   Maps to 12 if there are 2 1's, 6 otherwise
                         8        *8
                          hT      *11 (increment 10)
 [                          )      Wrap the 7 starred results in an array
                             @J3   Get the 4th value of the input mapping - i.e. number of 4's
@                                  Get the value at that position in the array

*5hSJ   Rule 2 - Straight
  hSJ   Smallest frequency in input mapping (first, sort, J)
        For a straight, smallest value will be 1, 0 otherwise
*5      Multiply by 5

*Tq6hJ   Rule 3 - 6 1's
    hJ   Frequency of 1's (first value from input mapping)
  q6     1 if the above == 6, 0 otherwise
*T       Multiply by 10

*<3KeSJ@j937TK   Rule 4 - 4,5,6 of a kind, other than 4's
   KeSJ          Get the max frequency from input mapping, store in K
        j937T    [9,3,7]
       @     K   Get the element at K'th position in the above (modular indexing)
 <3K             1 if 3<K, 0 otherwise
*                Multiply the previous 2 results

eS[   Wrapping it all up!
  [   Wrap all the above rules in an array
eS    Take the max value of the above, implicit print

```
> 1 votes

# Answer
# Retina, ~~137~~ 126 bytes

```
4
A
O`.
^11A+
0
1+$
2
^A+
1
(.)\1{5}
3
^.A+
4
.?(.)\1{4}.?
5
^..A+
6
12356A
7
.+AAA$
8
.*(.)\1{3}.*
9
.+AA$
10
.+A$
11
.{6}
12

```

-11 bytes thanks to *@Neil*.

Output is 0-indexed (`0..12`).

Try it online or verify all test cases.

**Explanation:**

Replace every 4 with an 'A':

```
4
A

```

Sort all the input-digits (the A's will be at the back):

```
O`.

```

Every other two lines replaces the input with the expected output:

```
Regex         Replacement  Explanation

^11A+         0            starts with "11", followed by any amount of A's
1+$           2            ends with any amount of 1s
^A+           1            starts with any amount of A's
(.)\1{5}      3            six of the same characters
^.A+          4            starts with any character, followed by any amount of A's
.?(.)\1{4}.?  5            five of the same characters,
                           with optionally a leading or trailing character
^..A+         6            starts with any two characters, followed by any amount of A's
12356A        7            literal "12356A" match
.+AAA$        8            any amount of leading characters, ending with three A's
.*(.)\1{3}.*  9            four of the same characters,
                           with optionally any amount of leading/trailing chars
.+AA$         10           any amount of leading characters, ending with two A's
.+A$          11           any amount of leading characters, ending with a A
.{6}          12           any six characters

```
> 1 votes

# Answer
# 05AB1E, ~~57~~ 55 bytes

```
4¢4@U.M¢©5-Di14¹нk2αë>Di5X-ë>i9X3*-¹1¢2Ê*ë®i7ë¹4¢o;ï12α

```

Port of *@Neil*'s Charcoal answer, because my initial approach was already at 60 bytes and I wasn't done yet. My current answer can probably be golfed some more, though.

Input as a list of digits.

Try it online or verify all test cases.

**Explanation:**

```
4¢              # Count the amount of 4s in the (implicit) input-list
  4@            # Check if it's larger than or equal to 4
                # (results in 1 for truthy; 0 for falsey)
    U           # Pop and store that result in variable `X`
.M              # Push the most frequent number in the (implicit) input-list
  ¢             # Pop and push the count of that number in the (implicit) input-list
   ©            # Store it in the register (without popping)
5-Di            # If the maximum count - 5 is exactly 1 (so the maximum count is 6):
    14          #  Push 14
      ¹н        #  Push the first digit of the input-list
        k       #  Get its index in 14, resulting in -1, 0, or 1
         2α     #  Take the absolute difference with 2
                #  (This covers cases 1, 2, and 3)
ë>Di            # Else-if the maximum count - 5 + 1 is exactly 1 (so the maximum count is 5):
    5           #  Push 5
     X-         #  And subtract variable `X`
                #  (This covers cases 4 and 5)
ë>i             # Else-if the maximum count - 5 + 2 is exactly 1 (so the maximum count is 4):
   9            #  Push 9
    X3*         #  Multiply variable `X` by 3
       -        #  And subtract it from the 9
        ¹1¢     #  Count the amount of 1s in the input-list
           2Ê   #  Check if it's NOT equal to 2 (1 if truthy; 0 if falsey)
             *  #  Multiply it with the 9 or 6
                #  (This covers cases 0, 6, and 9)
ë®i             # Else-if the maximum count is 1:
   7            #  Push a 7
                #  (This covers case 7)
ë               # Else (maximum count is 2 or 3):
 ¹4¢            #  Count the amount of 4s in the input-list
    o           #  Take 2 to the power this count
     ;ï         #  Halve and floor it
       12α      #  And take the absolute difference with 12
                #  (This covers cases 8, 10, 11, and 12)
                # (Output the top of the stack implicitly as result)

```
> 1 votes

# Answer
# Ruby, 100 bytes

```
->a{%w(^2.*4$ 6$ ^6 6 5$ 5 4$ ^1*$ 3$ 4 2$ 1$ .).index{|b|/#{b}/=~([1,*a,4].map{|c|a.count(c)}*'')}}

```

Try it online!

### How it works:

Count occurrences of every number in the array, prepend number of 1s and append number of 4s.

After that, try to match with different regex patterns.
> 0 votes

---
Tags: code-golf, game
---


title: KOTH: TNT Run Challenge

text:
# Question
Title: KOTH: TNT Run Challenge
This was inspired by a Minecraft mini-game. The rules are pretty simple: you run and jump around, and every block you step on disappears once you've stepped on it. The goal is to be the last one left.

Your bot should be a complete program. It should accept input as a command line argument. The input will be a map of the "world"; here is an example:

```
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxx xxxxxxxxxxxxxxxxxxxxxxxxxxx
xxx xxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxx x xxxxxxxxxxxxx@xxxxxxxxxxx
xxxxxx1xxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxx           xxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxx
xxxxxxxxxxxxxxxxx x x xxxxxxxxxx
xxxxxxxxxxxxxxxxxxxx xxxxxxxxxxx
xxxxxxxxxxxxxx xxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxx xxx xx3xxxxxxxxxx
xxxxxxxxxxxxxxxxxxx xxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
xxxxxxxxxxxxxxxxxxxxxxxxxxxxx  x
xxxxxxxxxxxxxxxxxxxxxxxxxxx   xx
xxxxxxxxxxxxxxxxxxxxxxxxx      2
xxxxxxxxxxxxxxxxxxxxxxx

```

The legend is as follows:

`x: solid block`

`: empty air`

`@: your bot`

`1,2,3,4,5,6,7,8,9,0: other bots`

Your bot should output your move as a pair of integers. Example: `-1, 2` will move 1 block to the left and 2 blocks down (coordinates origin is in the top left corner).

You may move up to four blocks, manhattan distance, from your current location. If you try to move further than that, the move is invalid. Any move that would move you past the edge will put you on the edge instead. Invalid moves will be ignored.

Once you land on a block it is removed; if you remain on the same block next turn you will fall. Two bots may land on the same block on the same turn and both survive; if this happens, both bots will only see themselves and not the other bot.

If you need to store files for persistence, please do so in a folder with the name of your bot. You may not read other bots' persistent data if any exists.

The match controller is available at https://paste.ee/p/Xf65d.

Please use languages that can be run on a standard Linux or OSX install.

Current results (100 rounds):

```
JumpBot                   31
LookBot                   27
ShyBot                    26
Slow Bot                  15
KnightBot                 2
Moat Builder              0
UpBot                     0
Random Bot                0

```

# Answer
> 9 votes
# Slow Bot (Python)

He moves in a line pattern and checks his moves before making them (also suicides when he's the last one alive to prevent long runtimes) He won 195/200 Battels in my test tournament.

```
import sys
import re

class vec2(object):
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, other):
        return vec2(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return vec2(self.x - other.x, self.y - other.y)

    def __iadd__(self, other):
        return self + other

    def __isub__(self, other):
        return self - other

    def __neg__(self):
        return vec2(-self.x, -self.y)

def xy_to_i(vec=vec2(0, 0)):
    vec -= vec2(1, 1)
    vec.y += (vec.x - vec.x % 32) / 32
    return vec.x + vec.y * 33

def i_to_xy(i=0):
    vec = vec2(0, 0)
    vec.x = i % 33
    vec.y = (i - vec.x) / 32 + 1
    vec.x += 1
    return vec

class World(object):
    def __init__(self, map=''):
        self.map = map

    def getPlayerPosition(self):
        return i_to_xy(re.search('@', self.map).start())

    def getNumOtherBots(self):
        return len(re.findall('([0123456789])', ' ' + self.map + ' '))

    def get_tile(self, vec=vec2(0, 0)):
        i = xy_to_i(vec)
        return self.map[i:i + 1]

world = World(sys.argv[1])
pos = world.getPlayerPosition()

def check_moveV(vecd=vec2(0, 0)):
    try:
        vecn = pos + vecd

        if vecn.x > 32 or vecn.x < 1 or vecn.y > 32 or vecn.y < 1 \
            or abs(vecd.x) + abs(vecd.y) > 4:
            return False

        # Note: this will also avoid positions other bots are on (will disappear in the next step).

        return world.get_tile(vecn) == 'x'
    except:
        raise
        return False

def check_move(x=0, y=0):
    return check_moveV(vec2(x, y))

def run():
    if world.getNumOtherBots() == 0:
        return '0 0'  # Suicide if we are the only one left.

    # this creates the "line" pattern

    if check_move(0, -1):
        return '0 -1'

    if check_move(0, 1):
        return '0 1'

    if check_move(1, 0):
        return '1 0'

    if check_move(1, -1):
        return '1 -1'

    # If we get here, we are desperate and need to find a safe place to jump.

    for dx in range(-2, 2):
        for dy in range(-2, 2):
            if check_move(dx, dy):
                return '%i %i' % (dx, dy)

    # If we can't find a place to jump in close range, try long range.

    for dx in range(-4, 4):
        for dy in range(-4, 4):
            if check_move(dx, dy):
                return '%i %i' % (dx, dy)

    # If we get here, we are dead no matter what; accept our fate.

    return '0 0'

print(run())

```

*I'm not an expert in python and there are probably 100 ways of doing it shorter/better*

# Answer
> 6 votes
# JumpBot (C)

Try to jump to field with most possible moves in next round.

```
#include <stdio.h>
#include <stdlib.h>

typedef struct map {
     char *raw_map;
     int size;
     int lines;
     char *pos;
} *MAP;

typedef struct cdata {
     int result;
     MAP m;
     int x;
     int y;
} *CDATA;

typedef struct mdata {
     int x;
     int y;
     int moves;
     int bx;
     int by;
     MAP m;
} *MDATA;

int numberOfMoves(MAP, int, int);
char getAt(MAP, int, int);

int abs(int x)
{
    return x < 0 ? x*-1 : x;
}

void count(void *data, int x, int y)
{
    CDATA d = (CDATA)data;
    char c = getAt(d->m, d->x + x, d->y + y);
    if(c != 'x') return;
    d->result++;
}

void choose(void *data, int x, int y)
{
    MDATA m = (MDATA)data;
    char c = getAt(m->m, m->x + x, m->y + y);
    if(c != 'x') return;
    int moves = numberOfMoves(m->m, m->x+x, m->y+y);
    if(moves > m->moves || (!m->bx && !m->by)) {
        m->moves = moves;
        m->bx = x;
        m->by = y;
    }
}

MAP parse_input(char *input)
{
    MAP m = malloc(sizeof *m);
    if(!m) {
        fprintf(stderr, "failed to alloc map\n");
        return NULL;
    }

    m->size=0;
    m->lines=1;
    m->pos=0;

    char *temp;
    for(temp = input;*temp;temp++) {
        switch(*temp) {
            case '\n': m->lines++; break;
            default: break;
        }
    }
    m->size = (temp + 1) - (input + m->lines);
    m->raw_map = malloc(m->size);
    if(!m->raw_map) {
        fprintf(stderr, "failed to alloc raw_map\n");
        return NULL;
    }

    int index = 0;
    for(temp = input; *temp; temp++) {
        if(*temp == '@') m->pos = m->raw_map + index;
        if(*temp != '\n') m->raw_map[index++] = *temp;
    }

    return m;
}

char getAt(MAP m, int x, int y)
{
    return m->raw_map[x + y*(m->size / m->lines)];
}

void posToXY(MAP m, int *x, int *y)
{
    int index = m->pos - m->raw_map;
    int length = m->size / m->lines;
    *x = index % length;
    *y = index / length;
}

typedef void (*DOFUNC)(void *, int, int);
void processMoves(MAP m, int x, int y, DOFUNC proc, void *data)
{
    int length = m->size / m->lines;
    int left = x>=4 ? 4 : x;
    int right = x + 4 <= length ? 4 : length - (x + 1);
    int up = y >= 4 ? 4 : y;
    int down = y + 4 <= m->lines ? 4 : m->lines - (y + 1);

    for(int i=-left; i<=right; i++) {
        for(int j=-up; j<=down; j++) {
            if((abs(i) + abs(j) <= 4) && (i || j)) (*proc)(data, i, j);
        }
    }
}

int numberOfMoves(MAP m, int x, int y)
{
    struct cdata d;
    d.result = 0;
    d.x = x;
    d.y = y;
    d.m = m;
    processMoves(m, x, y, &count, &d);
    return d.result;
}

void getMove(MAP m, int *x, int *y)
{
    struct mdata d;
    posToXY(m, &d.x, &d.y);
    d.moves = 0;
    d.bx = 0;
    d.by = 0;
    d.m = m;
    processMoves(m, d.x, d.y, &choose, &d);
    *x = d.bx;
    *y = d.by;
}

int main(int argc, char *argv[])
{
    if(argc != 2) {
        fprintf(stderr, "bad number of arguments %d\n", argc);
        return -1;
    }

    MAP m = parse_input(argv[1]);
    int x=0, y=0;
    getMove(m, &x, &y);
    printf("%d %d\n", x, y);
    return 0;
}

```

# Answer
> 5 votes
# LookBot (C)

Simple bot that is similar in performance to Slow Bot, except that this one makes random possible moves. Plan to improve this to PredictBot.

```
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <sys/time.h>

#define WORLDSZ (32)
#define WORLDSZ_2 (WORLDSZ*WORLDSZ)

int max(int a,int b){return a>b?a:b;}
int min(int a,int b){return a<b?a:b;}

struct Position{
    int x,y;
};
typedef struct Position Position;

struct World{
    Position me;
    double enemymap[WORLDSZ][WORLDSZ]; //chance of enemy present
    bool open[WORLDSZ][WORLDSZ];
};
typedef struct World World;

void world_read(World *world,const char *arg){
    int x,y,i=0;
    for(y=0;y<WORLDSZ;y++,i++){
        for(x=0;x<WORLDSZ;x++,i++){
            if(arg[i]=='@'){world->me.x=x; world->me.y=y;}
            world->enemymap[y][x]=arg[i]>='0'&&arg[i]<='9';
            world->open[y][x]=arg[i]=='x';
        }
    }
}

//returns relative position
Position world_calcmove(World *world){
    const int mex=world->me.x,mey=world->me.y;
    int dx,dy;
    Position poss[40];
    int nposs=0;
    for(dy=max(-mey,-4);dy<=min(WORLDSZ-1-mey,4);dy++){
        const int absdy=abs(dy);
        for(dx=max(-mex,absdy-4);dx<=min(WORLDSZ-1-mex,4-absdy);dx++){
            if(!world->open[mey+dy][mex+dx])continue;
            poss[nposs].x=dx;
            poss[nposs++].y=dy;
        }
    }
    if(nposs==0){
        poss[0].x=poss[0].y=0;
        return poss[0];
    }
    return poss[rand()%nposs];
}

int main(int argc,char **argv){
    if(argc!=2){
        fprintf(stderr,"Call with world!\n");
        return 1;
    }
    struct timeval tv;
    gettimeofday(&tv,NULL);
    srand(tv.tv_sec*1000000ULL+tv.tv_usec);

    World world;
    world_read(&world,argv[1]);
    Position move=world_calcmove(&world);
    printf("%d %d\n",move.x,move.y);
}

```

# Answer
> 5 votes
# Moat Builder (Python)

If I dig a moat around myself, nobody outside it can screw me over.

...also known as "Paint yourself into a corner simulator 2016".

```
import numpy
import sys
import math
import os

if not os.path.exists('./moatbuilder'):
    os.mkdir('./moatbuilder')

raw_field = sys.argv[1]
field = numpy.array([numpy.array(list(i)) for i in raw_field.splitlines()])
field_size = len(field)
x, y = raw_field.replace('\n','').index('@')%field_size, int(raw_field.replace('\n','').index('@')/field_size)
# If there are no holes, it's the first round - reset persistence
if raw_field.count(' ')==0:
    open('./moatbuilder/persistent','w').write('')

def bigmove(target):
    if x < target[0]:
        return min(4, target[0] - x), 0
    elif x > target[0]:
        return max(-4, target[0] - x), 0
    elif y < target[1]:
        return 0, min(4, target[1] - y)
    else:
        return 0, max(-4, target[1] - y)

def smallmove(target):
        if x < target[0]:
        try:
            return min(max(1, list(field[y][x:x+4]).index('x')), target[0] - x), 0
        except:
            return 0, 0
        elif x > target[0]:
        try:
            return max(min(-1, 0-list(reversed(field[y][x-4:x])).index('x')), target[0] - x), 0
        except:
            return 0, 0
        elif y < target[1]:
        try:
                    return 0, min(max(1, list(field[:,x][y:y+4]).index('x')), target[1] - y)
        except:
            return 0, 0
        else:
        try:
            return 0, max(min(-1, 0-list(reversed(field[:,x][y-4:y])).index('x')), target[1] - y)
        except:
            return 0, 0

try:
    mode = int(open('./moatbuilder/persistent').read())
except:
    mode = 1

# Modes:
# 1 - go to the center
# 2 - go to an outside edge
# 3 - dig moat
if mode==1:
    dx, dy = bigmove((int(field_size/2), int(field_size/2)))
    if dx==0 and dy==0:
        open('./moatbuilder/persistent', 'w').write('2')
        mode = 2
if mode==2:
    dx, dy = bigmove((int(field_size-1), int(field_size/2)))
    if dx==0 and dy==0:
        dy = 1
        open('./moatbuilder/persistent', 'w').write('3')
        mode = 3
elif mode==3:
    direction = max(field_size-x, field_size-y)%2
    if direction == 1:
        if x > y:
            dx, dy = smallmove((y, y))
        else:
            dx, dy = smallmove((x, field_size - 1))
        if dx==0 and dy==0:
            dx = 1
    else:
        if y > x:
            dx, dy = smallmove((x, x))
        else:
            dx, dy = smallmove((field_size - 1, y))
        if dx==0 and dy==0:
            dy = 1

print "%i %i" % (dx, dy)

```

# Answer
> 5 votes
# Monte (Python)

Sorry, that pun just had to be made.

Anyway, this bot works by doing a Monte Carlo Tree Search on all of the possible move sets. Think of JumpBot, only more in-depth.

To run, it needs an extra command line argument (can be specified in the controller). It controls how much time the bot should search for (in ms); I used 750-1500 in testing.

Code:

```
import sys
import math
import copy
#from profilestats import profile
pmap = sys.argv[2].split("\n")
pmap = [list(r) for r in pmap]

#find a player
#@profile
def find(tmap,bot):
   r,c=-1,-1
   for row in range(len(tmap)):
      for col in range(len(tmap[row])):
         if tmap[row][col]==bot:
            r,c=row,col
   return r,c

mer,mec=find(pmap,'@')
bots=[(mer,mec)]

#find all the other players
for b in range(10):
   r,c=find(pmap,str(b))
   if r != -1:
      bots.append((r,c))

#getter function, treats oob as spaces
def get(tmap,r,c):
   if r<0 or r>=len(tmap) or c<0 or c>=len(tmap[r]):
      return ' '
   return tmap[r][c]

#returns manhattan distance between 2 positions
def dist(r1,c1,r2,c2):
   return abs(r1-r2)+abs(c1-c2)

#gets all possible moves from a map
#@profile
def moves(tmap,ther=-1,thec=-1):
   if ther==-1: ther,thec = find(tmap,'@')
   pos=[]
   for r in range(-4,5):
      for c in range(-4,5):
         if abs(r)+abs(c)<=4 and get(tmap,ther+r,thec+c)=='x':
            pos.append((r,c))
   return pos

ttlmoves = 40
#monte-carlo tree node
class MCNode:
   def __init__(self):
      self.wins=0
      self.simu=0
      self.chld=[]
      self.cmap=[[]]
      self.prnt=None
      self.r=-1
      self.c=-1
   def add(self, cnode):
      self.chld.append(cnode)
      cnode.prnt = self
   #used to balance exploitation and exploration
   #@profile
   def param(self,cin):
      return self.chld[cin].wins/self.chld[cin].simu\
             + 1.414 * math.sqrt( math.log(self.simu) / \
             self.chld[cin].simu )
   #finds the child with the highest param
   #@profile
   def best(self):
      vals = [self.param(x) for x in range(len(self.chld))]
      binx = 0
      bval = vals[0]
      for x in range(len(vals)):
         if vals[x]>bval:
            binx=x
            bval=vals[x]
      return self.chld[binx]

#update all the parents
#@profile
def backprog(leaf):
   par = leaf.prnt
   if not (par is None):
      par.wins+=leaf.wins
      par.simu+=leaf.simu
      backprog(par)

#expand all the moves from a position
#@profile
def expand(rootn):
   ther,thec = rootn.r,rootn.c
   for r,c in moves(rootn.cmap,rootn.r,rootn.c):
      nmap = copy.deepcopy(rootn.cmap)
      nmap[ther+r][thec+c] = '@'
      nmap[ther][thec]=' '
      nnode = MCNode()
      nm = moves(nmap,ther+r,ther+c)
      nnode.wins = len(nm)
      nnode.simu = ttlmoves
      nnode.r=ther+r
      nnode.c=thec+c
      nnode.cmap = nmap
      rootn.add(nnode)
      backprog(nnode)

root = MCNode()
m = moves(pmap,mer,mec)
root.wins = len(m)
root.simu = ttlmoves
root.cmap=copy.deepcopy(pmap)
root.r=mer
root.c=mec
expand(root)

#simulate a bunch of outcomes
import time
curt  = lambda: int(round(time.time() * 1000))
strt = curt()
ttme = int(sys.argv[1])
while curt()-strt < ttme:
   tnode=root
   while tnode.chld:
      tnode=tnode.best()
   expand(tnode)

#choose the most explored one
bnode = max(root.chld,key=lambda n:n.simu)

#output
print("{} {}".format((bnode.c-mec),(bnode.r-mer)))

```

# Trials

25 rounds:

```
MonteBot            14
JumpBot             6
ShyBot              5
LookBot             1
KnightBot           0
SlowBot             0

```

100 rounds:

```
JumpBot             38
MonteBot            36
ShyBot              15
LookBot             14
SlowBot             2
KnightBot           0

```

200 rounds:

```
MonteBot            87
JumpBot             64
LookBot             33
ShyBot              21
SlowBot             5
KnightBot           0

```

All of the simulations above used search time 750. This bot would probably be even better with a longer search time (I don't know what the max allowed is).

## Improvements

This bot still needs improvements in:

1. Performance: it needs the entire time to search.
2. Prediction: it won't account for other bot's moves.
3. Balance: I'm not sure if the UCT formula I am using to calculate which node I should explore is optimal.

# Answer
> 4 votes
# ShyBot (Python)

This bot really doesn't like other bots and will try to keep itself away if possible. ShyBot is also really careful about where it steps; it won't even step on other bots. However, ShyBot still looses often which makes insecure.

```
import sys
map = sys.argv[1]
map = map.split("\n")
map = [list(r) for r in map]

def find(map,bot):
   r,c=-1,-1
   for row in range(len(map)):
      for col in range(len(map[row])):
         if map[row][col]==bot:
            r,c=row,col
   return r,c

mer,mec=find(map,'@')
bots=[(mer,mec)]

for b in range(10):
   r,c=find(map,str(b))
   if r != -1:
      bots.append((r,c))

avg=[0,0]

for b in bots:
   avg[0]+=b[0]
   avg[1]+=b[1]

avg[0] = avg[0]/len(bots)
avg[1] = avg[1]/len(bots)

def get(map,r,c):
   if r<0 or r>=len(map) or c<0 or c>=len(map[r]):
      return ' '
   return map[r][c]

def dist(r1,c1,r2,c2):
   return abs(r1-r2)+abs(c1-c2)

pos=[]
for r in range(-4,5):
   for c in range(-4,5):
      if abs(r)+abs(c)<=4 and get(map,mer+r,mec+c)=='x':
         pos.append((r,c))

if len(pos)==0:
   bestr,bestc=0,0
else:
   bestr,bestc=pos[0]

for r,c in pos:
   if dist(mer+r,mec+c,avg[0],avg[1])>dist(mer+bestr,mec+bestc,avg[0],avg[1]):
      bestr,bestc=r,c

print(str(bestc)+" "+str(bestr))

```

# Answer
> 4 votes
# KnightBot (Java)

It's works like chess, and is named like Twitch...

...

.........

............................sorry...

```
public class KnightBot{
   private static String[] map;
   private static int myx;
   private static int myy;
   public static void main(String[] args){
      map=args[0].split("\n");
      for(int y=0;y<map.length;y++){
         if(map[y].indexOf("@")!=-1){
            myy = y;
            myx = map[y].indexOf("@");
            break;
         }
      }
      System.out.println(move((int)(Math.random()*4),4));
   }
   public static String move(int dir,int tries){
      if(tries==0)return "0 0";
      int x=dir<2?1:-1;
      int y=dir%2==0?2:-2;
      if((myx+x<0||myx+x>=map[0].length()||myy+y<0||myy+y>=map.length)||map[y+myy].charAt(myx+x)!='x'){
         x=dir<2?2:-2;
         y=dir%2==0?1:-1;
      }
      if((myx+x<0||myx+x>=map[0].length()||myy+y<0||myy+y>=map.length)||map[y+myy].charAt(myx+x)!='x')
         return move(++dir>3?0:dir,tries-1);
      return x+" "+y;
   }
}

```

# SwirlyBot (Java)

These are clearly not the optimal solutions, but I hope will be useful for midlevel testing.

```
public class SwirlyBot{
   private static String[] map;
   private static int myx;
   private static int myy;
   public static void main(String[] args){
      map=args[0].split("\n");
      for(int y=0;y<map.length;y++){
         if(map[y].indexOf("@")!=-1){
            myy = y;
            myx = map[y].indexOf("@");
            break;
         }
      }
      System.out.println(move(0));
   }
   public static String move(int dir){
      switch(dir){
         case 0:
            if(!safe(0,1)){
               if(safe(1,1)){
                  return "1 1";//Down-Right
               }else{
                  if(safe(1,0)){
                     return "1 0";//Right
                  }
               }
            }
            break;
         case 1:
            if(!safe(1,0)){
               if(safe(1,-1)){
                  return "1 -1";//Up-Right
               }else{
                  if(safe(0,-1)){
                     return "0 -1";//Up
                  }
               }
            }
            break;
         case 2:
            if(!safe(0,-1)){
               if(safe(-1,-1)){
                  return "-1 -1";//Up-Left
               }else{
                  if(safe(-1,0)){
                     return "-1 0";//Left
                  }
               }
            }
            break;
         case 3:
            if(!safe(-1,0)){
               if(safe(-1,1)){
                  return "-1 1";//Down-Left
               }else{
                  if(safe(0,1)){
                     return "0 1";//Down
                  }
               }
            }
            break;
         case 4:
            if(safe(0,-1))return "0 -1";
            break;
         case 5:
            if(!safe(0,2)){
               if(safe(1,2)){
                  return "1 2";//Down-Right
               }else{
                  if(safe(2,2)){
                     return "2 2";
                  }else{
                     if(safe(2,1)){
                        return "2 1";
                     }else{
                        if(safe(2,0)){
                           return "2 0";//Right
                        }
                     }
                  }
               }
            }
            break;
         case 6:
            if(!safe(2,0)){
               if(safe(2,-1)){
                  return "2 -1";//Up-Right
               }else{
                  if(safe(2,-2)){
                     return "2 -2";
                  }else{
                     if(safe(1,-2)){
                        return "1 -2";
                     }else{
                        if(safe(0,-2)){
                           return "0 -2";//Up
                        }
                     }
                  }
               }
            }
            break;
         case 7:
            if(!safe(0,-2)){
               if(safe(-1,-2)){
                  return "-1 -2";//Up-Left
               }else{
                  if(safe(-2,-2)){
                     return "-2 -2";
                  }else{
                     if(safe(-2,-1)){
                        return "-2 -1";
                     }else{
                        if(safe(-2,0)){
                           return "-2 0";//Left
                        }
                     }
                  }
               }
            }
            break;
         case 8:
            if(!safe(-2,0)){
               if(safe(-2,1)){
                  return "-2 1";//Down-Left
               }else{
                  if(safe(-2,2)){
                     return "-2 2";
                  }else{
                     if(safe(-1,2)){
                        return "-1 2";
                     }else{
                        if(safe(0,2)){
                           return "0 2";//Down
                        }
                     }
                  }
               }
            }
            break;
      }
      if(dir<8)return move(dir+1);
      return "0 -1";
   }
   public static boolean safe(int x, int y){
      return !((myx+x<0||myx+x>=map[0].length()||myy+y<0||myy+y>=map.length)||map[y+myy].charAt(myx+x)!='x');
   }
}

```

# Answer
> 2 votes
# Random Bot, UpBot

Two starting bots to compete against:

**Random Bot:** An example bot that moves randomly.

```
import random

x = random.randint(-4, 4)
y = random.randint(max(-4, -4 + abs(x)), min(4, 4 - abs(x)))
print x, y

```

**UpBot:** An example bot that moves up.

```
print '0 -1'

```

# Answer
> 1 votes
# StalkerBot (Python)

Will get as close as possible to the closest bot it sees. Targets Slow Bot's (pointless) automatic suicide. (If I'm on the same square as it and there are no other players, it won't see me and will suicide.)

```
#!/usr/bin/python3
from math import inf
from sys import argv

class Vector:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    def __neg__(self):
        return Vector(-self.x, -self.y)

    def __abs__(self):
        return self.x ** 2 + self.y ** 2  # Technically the square of the magnitude, but we only need it for comparison.

    def __iter__(self):
        yield self.x
        yield self.y

def get_location(grid, target='@'):
    for i, line in enumerate(grid):
        for j, char in enumerate(line):
            if char == target:
                return Vector(i, j)

def main(grid):
    my_location = get_location()

    min_distance = inf
    min_distance_direction = None

    for i in range(10):
        enemy_location = get_location(str(i))

        if enemy_location is not None:
            direction = enemy_location - my_location
            distance = abs(direction)

            if distance < current_min:
                min_distance = distance
                min_distance_direction = direction

            if distance == 1:
                break

    if min_distance_direction is not None:
        return min_distance_direction

    for d in range(1, 5):
        for x in range(-d, d):
            for y in (d - abs(x), abs(x) - d):
                if grid[x][y] == ' ':
                    return x, y

    return 0, 0

if __name__ == '__main__':
    print(*main(argv[1].splitlines()))

```

---
Tags: king-of-the-hill
---


# Question
Title: I give you Nth permutation, you give me N
**Input:** a sequence of uppercase letters (ASCII \[65;90\]) which is the ***N**th** lexicographical permutation of the multiset of its characters

\*permutations are numbered from 0 or 1 upwards

**Output:** base-10 integer ***N***

---

### Rulez

* **There might be duplicates** *(that's how this challenge differs from this one)*
* The characters are ordered by their ASCII value
* In case of an input of length less than or equal to 1, the input is the first permutation and the result is `0` or `1` respectively
* First permutation is that in which the leftmost character has the lowest value, the rightmost character has the highest value, and the sequence of characters between the first and the last character is the first permutation of the multiset of its characters *(recursive definition!)*
* Shortest entry wins

---

### Example

* Input `AAB` produces output `0`
* Input `ABA` produces output `1`
* Input `BAA` produces output `2`

* Input `ZZZ` produces output `0`
* Input `DCBA` produces output `23`

---

### EDIT

Extra kudos to the one who can come up with a solution which doesn't produce all permutations and then search for the input. That's some challenge.

# Answer
# Jelly, 5 bytes

```
Œ!QṢi

```

Try it online!

1-indexed output.
> 1 votes

# Answer
## Python 2, 69 bytes

Try it online

```
from itertools import*
lambda S:sorted(set(permutations(S))).index(S)

```
> 5 votes

# Answer
## Python, ~~302~~ 287 bytes

Dead Possum has already posted a short Pythonic solution, so I decided to go for the extra kudos. This solution does *not* generate all of the permutations. It can rapidly calculate the permutation index of a rather large string; it also handles an empty string correctly.

```
from math import factorial as f
from itertools import groupby as g
def p(t,b=''):
 if len(t)<2:return 0
 z,b=0,b or sorted(t)
 for i,c in enumerate(b):
  w=b[:i]+b[i+1:]
  if c==t[0]:return z+p(t[1:],w)
  if i<1 or c!=b[i-1]:
   n=f(len(w))
   for _,v in g(w):n//=f(len(list(v)))
   z+=n

```

Testing code:

```
def lexico_permute_string(s):
    ''' Generate all permutations of `s` in lexicographic order '''
    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break
        a[j], a[k] = a[k], a[j]
        a[j+1:] = a[j+1:][::-1]

def test_all(base):
    for i, s in enumerate(lexico_permute_string(base)):
        rank = p(s)
        assert rank == i, (i, s, rank)
        print('{:2} {} {:2}'.format(i, s, rank))
    print(repr(base), 'ok\n')

for base in ('AAB', 'abbbbc'):
    test_all(base)

def test(s):
    print('{!r}\n{}\n'.format(s, p(s)))

for s in ('ZZZ', 'DCBA', 'a quick brown fox jumps over the lazy dog'):
    test(s)

```

**output**

```
 0 AAB  0
 1 ABA  1
 2 BAA  2
'AAB' ok

 0 abbbbc  0
 1 abbbcb  1
 2 abbcbb  2
 3 abcbbb  3
 4 acbbbb  4
 5 babbbc  5
 6 babbcb  6
 7 babcbb  7
 8 bacbbb  8
 9 bbabbc  9
10 bbabcb 10
11 bbacbb 11
12 bbbabc 12
13 bbbacb 13
14 bbbbac 14
15 bbbbca 15
16 bbbcab 16
17 bbbcba 17
18 bbcabb 18
19 bbcbab 19
20 bbcbba 20
21 bcabbb 21
22 bcbabb 22
23 bcbbab 23
24 bcbbba 24
25 cabbbb 25
26 cbabbb 26
27 cbbabb 27
28 cbbbab 28
29 cbbbba 29
'abbbbc' ok

'ZZZ'
0

'DCBA'
23

'a quick brown fox jumps over the lazy dog'
436629906477779191275460617121351796379337

```

---

Non-golfed version:

```
''' Determine the rank (lexicographic index) of a permutation
    The permutation may contain repeated items

    Written by PM 2Ring 2017.04.03
'''

from math import factorial as fac
from itertools import groupby

def lexico_permute_string(s):
    ''' Generate all permutations of `s` in lexicographic order '''
    a = sorted(s)
    n = len(a) - 1
    while True:
        yield ''.join(a)
        for j in range(n-1, -1, -1):
            if a[j] < a[j + 1]:
                break
        else:
            return
        v = a[j]
        for k in range(n, j, -1):
            if v < a[k]:
                break
        a[j], a[k] = a[k], a[j]
        a[j+1:] = a[j+1:][::-1]

def perm_count(s):
    ''' Count the total number of permutations of sorted sequence `s` '''
    n = fac(len(s))
    for _, g in groupby(s):
        n //= fac(sum(1 for u in g))
    return n

def perm_rank(target, base):
    ''' Determine the permutation rank of string `target`
        given the rank zero permutation string `base`,
        i.e., the chars in `base` are in lexicographic order.
    '''
    if len(target) < 2:
        return 0
    total = 0
    head, newtarget = target[0], target[1:]
    for i, c in enumerate(base):
        newbase = base[:i] + base[i+1:]
        if c == head:
            return total + perm_rank(newtarget, newbase)
        elif i and c == base[i-1]:
            continue
        total += perm_count(newbase)

base = 'abcccdde'
print('total number', perm_count(base))

for i, s in enumerate(lexico_permute_string(base)):
    rank = perm_rank(s, base)
    assert rank == i, (i, s, rank)
    #print('{:2} {} {:2}'.format(i, s, rank))
print('ok')

```

**About `lexico_permute_string`**

This algorithm, due to Narayana Pandita, is from https://en.wikipedia.org/wiki/Permutation#Generation\_in\_lexicographic\_order

To produce the next permutation in lexicographic order of sequence `a`

1. Find the largest index j such that a\[j\] \< a\[j + 1\]. If no such index exists, the permutation is the last permutation.
2. Find the largest index k greater than j such that a\[j\] \< a\[k\].
3. Swap the value of a\[j\] with that of a\[k\].
4. Reverse the sequence from a\[j + 1\] up to and including the final element a\[n\].

FWIW, you can see an annotated version of that function here.

---

FWIW, here's the inverse function.

```
def perm_unrank(rank, base, head=''):
    ''' Determine the permutation with given rank of the
        rank zero permutation string `base`.
    '''
    if len(base) < 2:
        return head + ''.join(base)

    total = 0
    for i, c in enumerate(base):
        if i < 1 or c != base[i-1]:
            newbase = base[:i] + base[i+1:]
            newtotal = total + perm_count(newbase)
            if newtotal > rank:
                return perm_unrank(rank - total, newbase, head + c)
            total = newtotal
# Test

target = 'a quick brown fox jumps over the lazy dog'
base = ''.join(sorted(target))
rank = perm_rank(target, base)
print(target)
print(base)
print(rank)
print(perm_unrank(rank, base))

```

**output**

```
a quick brown fox jumps over the lazy dog
        aabcdeefghijklmnoooopqrrstuuvwxyz
436629906477779191275460617121351796379337
a quick brown fox jumps over the lazy dog

```

And here's a function that I wrote while developing `perm_unrank` which shows the breakdown of the subcounts.

```
def counts(base):
    for i, c in enumerate(base):
        newbase = base[:i] + base[i+1:]
        if newbase and (i < 1 or c != base[i-1]):
            yield c, perm_count(newbase)
            for h, k in counts(newbase):
                yield c + h, k

def show_counts(base):
    TAB = ' ' * 4
    for s, t in counts(base):
        d = len(s) - 1
        print('{}{} {}'.format(TAB * d, s, t))

# Test
base = 'abccc'
print('total number', perm_count(base))
show_counts(base)

```

**output**

```
a 4
    ab 1
        abc 1
            abcc 1
    ac 3
        acb 1
            acbc 1
        acc 2
            accb 1
            accc 1
b 4
    ba 1
        bac 1
            bacc 1
    bc 3
        bca 1
            bcac 1
        bcc 2
            bcca 1
            bccc 1
c 12
    ca 3
        cab 1
            cabc 1
        cac 2
            cacb 1
            cacc 1
    cb 3
        cba 1
            cbac 1
        cbc 2
            cbca 1
            cbcc 1
    cc 6
        cca 2
            ccab 1
            ccac 1
        ccb 2
            ccba 1
            ccbc 1
        ccc 2
            ccca 1
            cccb 1

```
> 5 votes

# Answer
# MATL, ~~13~~ ~~12~~ 11 bytes

*1 byte saved thanks to G B!*

```
tY@Xu=!Af1)

```

Output is 1-based.

Try it online! Or verify all test cases.

### Explanation

```
t      % Input string implicitly. Duplicate
Y@     % All permutations, sorted; each in a different row
Xu     % Unique rows
=      % Compare for equality, with broadcast
!      % Transpose
A      % All: true for columns that contain all entries true
f      % Find: indices of nonzero elements
1)     % Get first of those indices. Implicitly display

```
> 3 votes

# Answer
# Julia, ~~121~~ 125 bytes

Noncompeting, as it does not deal with duplicate letters correctly. I ported this from another language, from part of a solution to a Project Euler problem I did several years ago, and the first, 121-byte version had a bug because I had transposed the use of the permuted string and the sorted, canonical reference string.

```
f(p)=(n=0;z=length(p)-1;s=join(sort(collect(p)));for c in p z-=(n+=factorial(z)*(search(s, c)-1);p=replace(s,c,"",1);1)end;n)

```

For large inputs, this version uses bignums at the cost of 8 extra bytes:

```
f(p)=(n=0;z=BigInt(length(p)-1);s=join(sort(collect(p)));for c in p z-=(n+=factorial(z)*(search(s, c)-1);p=replace(s,c,"",1);1)end;n)

```

Ungolfed:

```
function f(perm)
    nth = 0
    size = length(perm) - 1
    sorted = join(sort(collect(p)))
    for ch in sorted
        index = search(perm, ch) - 1
        nth += factorial(size) * index
        perm = replace(perm, ch, "" , 1) # replace at most one copy
        size -= 1
    end
    return nth
end

```

Uses a factoriadic number system, q.v. Thus, it does not produce all the permutations and for large inputs will run enormously faster than those that do.

For example, the alphabet can be permuted into the rather contrived sentence "Quartz glyph job vex'd cwm finks." That sentence is the 259,985,607,122,410,643,097,474,123rd lexicographic permutation of the letters of the alphabet. (Approximately 260 septillionth permutation.) This program finds that in about 65 µs on my machine.

```
julia> @time f("quartzglyphjobvexdcwmfinks")
  0.000065 seconds (570 allocations: 19.234 KB)
259985607122410643097474122

```

Note that the number ends in ...122 rather than ...123 because OP requested that the permutations be numbered from 0 rather than from 1.

# Julia, 375 bytes

I've left the indentation in for readability, but the byte count is without it.

```
p(t,b="")=begin
    l=length
    if l(t)<2 return 0 end
    f=factorial
    g(w)=(a=[];
        while w!=""
            s=""
            for c in w if c==w[1] s="$s$c" end end
            w=replace(w,s,"")
            push!(a,s)
        end;a)
    b=b>""?b:join(sort(collect(t)))
    z=0
    for(i,c) in enumerate(b)
        w=b[1:i-1]*b[i+1:end]
        if c==t[1] return z+p(t[2:end],w)
        elseif i>1&&c==b[i-1] continue end
        n=f(l(w))
        for v in g(w) n=div(n,f(l(v))) end
        z+=n
    end
    z
end

```

This one is just a straight Julia port of PM 2Ring's brilliant Python solution. I got hungry, so I decided I wanted the cookie after all. It's interesting to see the similarities and the differences between the two languages. I implemented `itertools.groupby` (in a limited form) as `g(w)`.

But the logic isn't mine, so go and upvote PM 2Ring's answer.

Replace `f=factorial` with `f(x)=factorial(BigInt(x))` if you want to be able to handle large inputs like p("QUARTZGLYPHJOBVEXDCWMFINKS").
> 3 votes

# Answer
# 05AB1E, 5 bytes

```
œêJ¹k

```

Uses the **CP-1252** encoding. Try it online!
> 3 votes

# Answer
# 05AB1E, 5 bytes

```
œê¹Sk

```

Try it online!

Independently discovered from Adnan's answer.
> 3 votes

# Answer
# PHP, 124 Bytes

```
$a=str_split($argn);sort($a);for($i=$j=join($a);$i<=strrev($j);$i++)$i==$argn?print+$n:(($c=count_chars)($i)!=$c($j)?:$n++);

```

## PHP, 136 Bytes

```
foreach($t=($c=count_chars)($argn)as$k=>$v)$i=$s.=str_repeat(chr($k),$v);for(;$i<=strrev($s);$i++)$i==$argn?print+$n:($c($i)!=$t?:$n++);

```

Online Version

Run with

```
echo '<string>' | php -nR '<code>'

```

## Calculate with factorial

Expanded Version

```
function f($i){return array_product(range(1,$i));} #factorial
function p($s){
return f(strlen($s))/array_product(array_map("f",count_chars($s,1)));
} # factorial / divide through product of factorials for each char
$a=$argn;
$b="";
$r=[];
for($d=0;$a;$d++) # loop range before used chars in string
{
    for($i=0;$i<strlen($a);$i++){ # loop for every char in the rest string
        if($a[$i]<$a[0]) # if char is before first char order by ascii
        $r[$d.$a[$i]]=p(substr_replace($a,"",$i,1)); # add range before
    }
    $a=substr($a,1); # remove first char
}
echo array_sum($r); # Output the range before the used permutation

```

Output for the string PPCG

```
Array
(
    [0C] => 3    # in first run C is before P startposition = 3
    [0G] => 3    # in first run G is before P startposition = 3+3
    [1C] => 2    # in second run PC is before PP startposition = 3+3+2
    [1G] => 2    # in second run PG is before PP startposition = 3+3+2+2=8
)

```

Online Version
> 3 votes

# Answer
# Mathematica, ~~33~~ 31 bytes

*Changing the problem spec allowed for a 2-byte savings.*

```
Permutations@Sort@#~Position~#&

```

Pure function taking a list as input and returning a nonnegative integer `N` in the form `{{N}}`.
> 2 votes

# Answer
# JavaScript (ES6), 130 bytes

```
s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))[0]||o.add(q.join``))([...s],[])&&[...o].sort().indexOf(s)

```

*Less golfed*

```
s=>{
  o = new Set; // use a set to avoid duplicates

  // recursive function to build all permutations (no cookie for me)
  p = (s, q) =>
  {
    y = s.map( (t,i) => // execute for each char at position i
          (
             t = [...s], // using t as local variable, store a copy of s
             x = t.splice(i,1), // remove char from t in position i, and store in array x
             p(t, q.concat(x)) // recursive call
          ));
    if (!y[0]) // if s was empty, I have a new permutation in q
      o.add( q.join('')) // convert to string and add to output set
  }
  // call p to enumerate all permutations
  p( [...s], [] ) // convert string s to array, q starts empty

  o = [...o].sort() // get elements of o and sort lexicographically
  return o.indexOf(s) // return the position of the input in o
}

```

**Test**

```
F=
s=>(o=new Set,p=(s,q)=>s.map((t,i)=>p(t=[...s],q.concat(t.splice(i,1))))[0]||o.add(q.join``))([...s],[])&&[...o].sort().indexOf(s)

function update() {
  O.textContent = F(I.value)
}

update()
```

```
<input id=I value='DCBA' oninput='update()'>
<pre id=O></pre>
```
> 2 votes

# Answer
# CJam, 7 bytes

```
q_e!\a#

```

Try it online!
> 1 votes

# Answer
# Pyth, 5 bytes

```
xS{.p

```

Online interpreter

Takes quoted input.
> 1 votes

# Answer
# Scala, 40 bytes

```
s=>s.permutations.toSeq.sorted indexOf s

```

To use it, assign this function to a variable:

```
val f:(String=>Int)=s=>s.permutations.toSeq.sorted indexOf s
println(f("BAA"))

```

Try it online at ideone

Unfortunately, `permutations` returns an iterator, which doesn't have a `sorted` method, so it has to be converted to a `Seq`
> 1 votes

# Answer
# C++, 96 bytes

We can make full use of the standard library here. The list of letters is passed as start/end iterators in standard C++ style.

```
#include<algorithm>
int f(char*a,char*z){int i=0;while(std::prev_permutation(a,z))++i;return i;}

```

We don't need to generate all permutations - since we have a transformation from one permutation to its predecessor, we simply count how many iterations it takes to reach the zeroth value.

### Test program:

```
#include<cstring>
#include<iostream>
int main(int argc, char **argv)
{
    while (*++argv)
        std::cout << *argv << ": "
                  << f(*argv, *argv+std::strlen(*argv)) << std::endl;
}

```

### Test results:

```
BAA: 0
BAA: 1
BAA: 2
ZZZ: 0
DCBA: 23
: 0

```
> 1 votes

# Answer
# Ruby, 50 bytes

I expected this to be shorter. I wouldn't have added the `sort` if the docs didn't say "the implementation makes no guarantees about the order in which the permutations are yielded."

```
->x{x.chars.permutation.map{|v|v*""}.sort.index x}

```
> 1 votes

# Answer
# Japt, 6 bytes

0-indexed

```
ñ á bU

```

Try it
> 1 votes

---
Tags: code-golf, permutations
---


title: Same number letters

text:
# Question
Title: Same number letters
Letters of the words want fairness.

They decided to appear same number of times in a sentence equally.

Example:

```
Priorities

```

Will become:

```
Ppprrioooritttieeesss

```

Each letter appears 3 times, as the most common letter was `i`, appearing 3 times.

It does not matter where you put the repeated letters, as long as they are next to a similar letter.

I.e.:

`Pppriooorritttieeesss` is OK (the 'r' letter)

`Ppprioororitttieeesss` is not OK (the 'r' letter)

Another example:

```
invoice

```

Will become:

```
innvvooiccee

```

Another example:

```
Remittance Advice

```

Will become:

```
Rrremmmiitttaannncce Adddvvvice

```

Space, comma, question mark, quotation, etc. are not considered letters for this challenge. Only need to consider \[a-zA-Z\]. Just once space is enough, and the order of the letters should remain the same.

The capitalization of letters does not matter, upper and lower case are countes as the same letter. That is: `Pip` has 2 'P's and 1 'I', so it will become `Piip`.

It is case insensitive letters can be in any form, `Piip=piip=piiP=PiiP`

This is

# Answer
> 5 votes
# 05AB1E, 16 bytes

```
lDáÙSÐ¹ls¢Zα>×.;

```

Try it online!

**Explanation**

```
l                  # convert input to lowercase
 D                 # duplicate
  á                # keep only letters
   Ù               # remove duplicates
    S              # split to list of chars
     Ð             # triplicate
      ¹ls¢         # count the occurrences of each letter in lowercase input
          Zα       # absolute valuue with max occurrence
            >      # increment
             ×     # repeat each unique char that many times
              .;   # replace the first occurrence of the char in lowercase input with this

```

# Answer
> 7 votes
# , 106 bytes

```
function(s){for(A in L<-LETTERS)s=sub(A,strrep(A,max(x<-+s-+Map(gsub,L,'',s,T))-x[A]--1),s,T);s}
"+"=nchar

```

Try it online!

Base R approach :

* stealing some ideas from @J.Doe R+stringr approach, I saved 26 bytes !
* another 5 bytes saved using @J.Doe suggestion to abuse R `+` operator

# Answer
> 5 votes
# Perl 6, 82 bytes

*-3 bytes thanks to nwellnhof*

```
->\a{a.=lc.=subst($_,$_ x a.comb(/<:L>/).Bag.values.max+1-a.comb($_))for 'a'..'z'}

```

Try it online!

Takes a mutable string and modifies it in place.

### Explanation:

```
->\a{        # Anonymous code block that takes a mutable string            }
 a.=lc;  # Lowercase
                                                               for 'a'..'z'  # For each letter
 .=subst(                                                    )  # Substitute
          $_,   #The first occurrence of the letter with
             $_ x  #The letter repeated
                  a.comb(/<:L>/).Bag.values.max    # The count of the most common letter
                                                 +1  # Plus 1
                                                   -a.comb($_)  # Minus the count of that letter already in the string

```

# Answer
> 5 votes
# , ~~33~~ ~~56~~ 46 bytes

```
t=:~:tolower
(#~1+t*~:(*>./-])t*1#.e.)@toupper

```

Try it online!

Couldn't find a way to avoid using `~:tolower` twice.

### How it works

```
t=:~:tolower    Auxiliary function: isupper
     tolower    Is lowercase version of itself...
   ~:           different from itself?

(#~1+t*~:(*>./-])t*1#.e.)@toupper    Main function
                          toupper    Convert to uppercase
                      e.     Build 2D array by comparing to itself
                   1#.       Row-wise sum; Count occurrences
                 t*     A) Filter by isupper (needed for finding max count)
           >./-]        Compute max of A) minus each element of A)
       ~:          Nub sieve; 1 if first occurrence, 0 otherwise
          *        Filter first occurrences only
     t*       Filter by isupper again, to ban non-alphabets from duplicating
   1+         Add one to preserve given chars
 #~           Duplicate

```

# Answer
> 5 votes
# \+ stringr, 108 bytes

I am not very good at `stringr`. Returns a mixture of lower and upper case since the question says it doesn't matter.

```
function(x){for(l in L<-letters)x=sub(l,strrep(l,max(s<-stringr::str_count(tolower(x),L))-s[L==l]+1),x,T);x}

```

Try it online!

## Explanation

```
function(x){
for(l in letters){ # Iterate through builtin vector "a", "b", "c"...
   # Generate a 26-long integer vector for how many a's, b's, c's in lower case string
  s = stringr::str_count(tolower(x),letters)
    # Take the max of this
  m = max(s)
    # Repeat the letter in the iteration enough times to make the word 'fair'
  new.l = strrep(l,m-s[letters==l]+1)
    # Substitute the first instance only of the letter in the string for the repeated letter
    # This is case insensitive (the T at the end)
    # Notice we calculate the max letter frequency each loop
    # This is inefficient but doesn't change the answer and avoids bytes
  x=sub(l,new.l,x,T);
  }
x # Return the substituted string
}

```

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

```
s=>(m=g=F=>s.replace(/[a-z]/gi,c=>F(c.toLowerCase())))(c=>g[c]=c+c.repeat(m-g[c]),g(c=>m=(n=g[c]=-~g[c])<m?m:n))

```

Try it online!

### Commented

```
s => (                       // s = input string
  m =                        // m = max. number of occurrences of the same letter
  g = F =>                   // g = helper function taking a callback function F
    s.replace(               //     (also used to store the # of occurrences of each letter)
      /[a-z]/gi,             //   for each letter c in s:
      c => F(                //     invoke F():
        c.toLowerCase()      //       with c.toLowerCase()
      )                      //     end of call to F()
    )                        //   end of replace()
)(c =>                       // invoke g() (second pass):
  g[c] =                     //   update g[c] to a non-numeric value
    c +                      //   append c once, unconditionally
    c.repeat(m - g[c]),      //   and append c as many times as required to reach m
                             //   (any subsequent iteration with the same letter will
                             //   lead to c.repeat(m - g[c]) --> c.repeat(NaN) --> '')
  g(c =>                     //   invoke g() (first pass):
    m = (n = g[c] = -~g[c])  //     increment g[c], save the result in n
      < m ? m : n            //     and update m to max(m, n)
  )                          //   end of first pass
)                            // end of second pass

```

# Answer
> 3 votes
# Java 11, ~~190~~ ~~176~~ 162 bytes

```
s->{s=s.toUpperCase();char m=2,i=64,a[]=new char[127];for(int c:s.getBytes())m-=m+~++a[c]>>-1;for(;++i<91;)s=s.replaceFirst(i+"",repeat((i+""),m-a[i]));return s;}

```

-14 bytes thanks to *@Nevay*.

Output is in full uppercase.

Try it online. (NOTE: `String.repeat(int)` is emulated as `repeat(String,int)` for the same byte-count, because Java 11 isn't on TIO yet.)

**Explanation:**

```
s->{                      // Method with String as both parameter and return-type
  s=s.toUpperCase();      //  Convert the input-String to full uppercase
  char m=2,               //  Max occurrence (+1), starting at 2
       i=64,              //  Index integer, starting at 64 ('A'-1)
       a[]=new char[127]; //  Create a count-array of size 127 (printable ASCII chars)
  for(int c:s.getBytes()) //  Loop over the characters of the String as integers
    m-=m+~++a[c]>>-1;     //   Increase the occurrence-counter of the char by 1 first
                          //   And if it's larger than the max-2, increase the max by 1
  for(;++i<91;)           //  Loop `i` in the range ['A', 'Z']
    s=s.replaceFirst(i+"",//   Replace the first char `i` in the string with:
       (i+"").repeat(     //   That same character repeated
        m-a[i]));         //   The max(+1) minus its array-occurrence amount of times
  return s;}              //  Then return the now modified String as result

```

# Answer
> 3 votes
# K4, 35 bytes

**Solution:**

```
{x@o@<o:(&^x),/(|/#:'g)#'g:" "_=_x}

```

**Examples:**

```
q)k){x@o@<o:(&^x),/(|/#:'g)#'g:" "_=_x}"Priorities"
"PPPrrioooritttieeesss"
q)k){x@o@<o:(&^x),/(|/#:'g)#'g:" "_=_x}"invoice"
"innvvooiccee"
q)k){x@o@<o:(&^x),/(|/#:'g)#'g:" "_=_x}"Remittance Notice"
"RRRemmmiittaaanncce Noootice"

```

**Explanation:**

Might be golfable with a different approach, will keep thinking

```
{x@o@<o:(&^x),/(|/#:'g)#'g:" "_=_x} / the solution
{                                 } / lambda taking implicit argument x
                                _x  / lowercase input
                               =    / group
                           " "_     / drop space from keys
                         g:         / save as g
                       #'           / take each
               (      )             / do this together
                  #:'g              / count occurances in each group
                |/                  / take the maximum
             ,/                     / flatten with
        (&^x)                       / indices where input is null (ie " ")
      o:                            / save as o
     <                              / indices to sort o ascending
   o@                               / apply these to o
 x@                                 / apply these indices to original input

```

# Answer
> 3 votes
# Charcoal, ~~33~~ 32 bytes

```
⭆↧θ⁺§θκ×ι∧№βι∧⁼κ⌕↧θι⁻⌈Ｅβ№↧θλ№↧θι

```

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

```
  θ                                 Input string
 ↧                                  Lower case
⭆                                   Map over characters and join
      κ                             Current index
     θ                              Input string
    §                               Original character
   ⁺                                Concatenate with
        ι                           Lowercased character
       ×                            Repeated
            ι                       Lowercased character
           β                        Lowercase alphabet
          №                         Count
         ∧                          Logical And
                   ι                Lowercased character
                  θ                 Input string
                 ↧                  Lower case
                ⌕                   Find
               κ                    Current index
              ⁼                     Equals
             ∧                      Logical And
                       β            Lowercase alphabet
                      Ｅ             Map over characters
                           λ        Current character
                          θ         Input string
                         ↧          Lower case
                        №           Count
                     ⌈              Maximum
                    ⁻               Minus
                               ι    Lowercased character
                              θ     Input string
                             ↧      Lower case
                            №       Count
                                    Implicitly print

```

# Answer
> 3 votes
# Japt `-h`, 27 bytes

*-3 bytes from @ETHproductions*

```
;v
ñ oC ó¥ ú £=iXÎpXèS)UbXg

```

---

**Trying to explain**

```
;v                          Convert implicit input to lowercase
ñ oC ó¥ ú £=iXÎpXèS)UbXg      Main function. Implicit lowercase input => "priorities"
ñ                           Sort => "eiiioprrst"
 oC                         Remove non alphabetical chars
   ó¥                       Split on different letters => ["e","iii","o","p","rr","s","t"]
     ú                      Right-pad each to the length of the longest with space => ["e  ","iii","o  ","p  ","rr ","s  ","t  "]
       £                    For each X in this array:
             XèS              Count the number of spaces in X
          XÎ                  Get the first character in X
            p   )             Repeat it (number of spaces) times
                              example the mapped value "e  " will become "ee"
         i                    Insert this into U at
                 UbXg           the first index of (first character in X) in U
        =                     Set U to the result

```

Try it online!

# Answer
> 3 votes
# Husk, 15 bytes

```
ḟ§Ë#f√MṘO´πL¹m_

```

Try it online!

Brute force, so very slow.

## Explanation

```
ḟ§Ë#f√MṘO´πL¹m_  Implicit input, say s = "To do"
             m_  Convert to lowercase: t = "to do"
           L¹    Length of s: 5
         ´π      All length-5 combinations of [1..5]:
                   [[1,1,1,1,1], [1,1,1,1,2], [2,1,1,1,1], ..., [5,5,5,5,5]]
        O        Sort them lexicographically:
                   [[1,1,1,1,1], [1,1,1,1,2], [1,1,1,1,3], ..., [5,5,5,5,5]]
      MṘ         For each, replicate letters of t that many times:
                   ["to do", "to doo", "to dooo", ..., "tttttooooo     dddddooooo"]
ḟ                Find the first string that satisfies this:
                   Example argument: x = "tto ddo"
    f√             Letters of x: "ttoddo"
  Ë                They have equal
 § #               number of occurrences in x: true (all have 2).

```

# Answer
> 2 votes
# JavaScript (Node.js), ~~140~~ 137 bytes

```
x=>[...x=x.toLowerCase()].map(F=c=>(F[c]=-~F[c],F[c]>w?w=F[c]:w,c),w=0).map(c=>x=x.replace(c,c.repeat(c>'`'&c<'{'?w-F[c]+1:1),F[c]=w))&&x

```

Try it online!

+33 bytes from my first solution for those never-ending additional constraints. JS sucks at case-insensitive string manipulations you know.

-3 bytes back Thanks @Arnauld.

## Explanation

```
x =>                                     // The function.
  [...x = x.toLowerCase()].map(f = c => (// - Iterate among each character...
                                         // - Additional constraint 2
    f[c] = -~f[c],                       //   - Add one to the character counter
    f[c] > w ? w = f[c] : w,             //   - Update the maximum count if necessary
    c                                    //   - Return back the character for the use in
                                         //     the next map function
  ), w = 0)                              // - The counters
  .map(c =>                              // - Iterate again...
    x = x.replace(                       //   - Repeat the first appearance of
      c,                                 //   - Each character
      c.repeat(                          //   - Needed number times
        c > '`' & c < '{'                //   - Additional constraint 1
        ? w - f[c] + 1                   //   - If this is letter, repeat
        : 1                              //   - If not, stay as is
      ),                                 //   - That should've been clearly stated
      f[c] = w                           //   - And set the counter so that no further
                                         //     replacements are done on this character
    )                                    //   - (w - f[c] + 1 = 1 in further iterations)
  ) && x                                 // - Return the result

```

# Answer
> 2 votes
# Ruby, 89 bytes

```
->s{1while(a=s.scan /\w/).map(&g=->x{s.scan(/#{x}/i).size}).uniq[1]&&s[a.min_by &g]*=2;s}

```

Try it online!

I tried different approaches, but what really saves a lot of bytes is adding one character at a time.

### How:

```
->s{
    1while                             # 1 is a nop to the while
    (a=s.scan /\w/)                    # For all the letters in the string
    .map(&g=->x{s.scan(/#{x}/i).size}) # Count occurrences ignoring case.
    .uniq[1]                           # Break out of loop if all equals
    &&s[a.min_by &g]*=2                # Otherwise duplicate the letter
                                       #  with the lowest count
    ;s}                                # Return the string

```

# Answer
> 2 votes
# Powershell 6, 123 bytes

*It uses a char range `'a'..'z'`. See script for previous Powershell below.*

```
param($s)for(;'a'..'z'|%{
if($d=($s-replace"[^$_]").Length-$n){if($d-gt0){1}else{$s=$s-replace"^(.*$_)","`$1$_"}}}){$n++}$s

```

Explained test script:

```
$f = {

param($s)                               # a parameter string
for(;                                   # loop while exists at least one letter...
'a'..'z'|%{                             # for each letter
    $d=($s-replace"[^$_]").Length-$n    # let $d is a difference between a number of current letter and current $n
    if($d-gt0){                         # if the difference > 0
        1                               # then return a object to increase $n on next iteration
    }
    if($d-lt0){                         # if the differenct < 0
        $s=$s-replace"^(.*$_)","`$1$_"  # append the current letter after a last instance of the letter. Use "^(.*?$_)" regexp to append it after a first instance of the letter.
    }
}){
    $n++                                # increment $n if exists at least one letter number of witch greather then $n
}                                       # and make next iteration of the 'for'.

$s                                      # return modified string if all letters in the string occur the same number of times

}

@(
    ,('Priorities', 'Ppprrioooritttieeesss', 'PPPriooorritttieeesss')
    ,('invoice', 'innvvooiccee')
    ,('Remittance Advice', 'Rrremmmiitttaannncce Adddvvvice', 'RRRemmmitttannnce Aadddvvviicce')
) | % {
    $s,$e = $_
    $r = &$f $s
    "$($r-in$e): $r"
}

```

Output:

```
True: Pppriooorritttieeesss
True: innvvooiccee
True: Rrremmmitttannnce Aadddvvviicce

```

# Powershell 5.1-, 133 bytes

```
param($s)for(;97..122|%{$_=[char]$_
if($d=($s-replace"[^$_]").Length-$n){if($d-gt0){1}else{$s=$s-replace"^(.*$_)","`$1$_"}}}){$n++}$s

```

# Answer
> 2 votes
# Red, 252 bytes

```
func[s][a: charset[#"a"-#"z"#"A"-#"Z"]t: parse s[collect[any[keep a | skip]]]m: copy
#()foreach c t[c: form c either n: m/:c[m/:c: n + 1][m/:c: 1]]d: last sort extract next
to-block m 2 foreach c s[prin c: form c if n: m/:c[loop d - n[prin c]m/:c: d]]]

```

Try it online!

Ridiculously long solution...

## Explanation:

```
f: func [ s ] [
    a: charset [ #"a" - #"z" #"A" - #"Z" ]   ; letters
    t: parse s [                             ; parse the string
        collect [ any [ keep a | skip ] ]    ; and keep only the letters
    ]
    m: copy #()                              ; initialize a map
    foreach c t [                            ; for each character in t
        c: form c                            ; the character as a string
        either n: select m c [ m/:c: n + 1 ] ; increase the count if already in map
                             [ m/:c: 1 ]     ; otherwise create a map entry with count 1
    ]
    d: last sort extract next to-block m 2   ; convert the map to a block; extract only the
                                             ; numbers and take the last of the sorted block
    foreach c s [                            ; for each character in the input
        c: form c                            ; the character as a string
        prin c                               ; print it (with no space nor newline)
        if n: select m c [                   ; if c is a key in the map
            loop d - n [ prin c ]            ; print the character again up to d times
            m/:c: d                          ; set the count to max (flag it as used)
        ]
    ]
]

```

# Answer
> 2 votes
# Perl 6, ~~77~~ 70 bytes

```
{s:i|$($!.min(*{*}).key)|$/$/|until [==] ($!=.lc.comb(/<:L>/).Bag){*}}

```

Try it online!

Taking G B's approach of inserting a character until all characters appear the same number of times. Receives a string that is modified in-place.

If underscores can be treated like letters, the regex can become `/\w/`, saving two bytes.

### Explanation

```
{
                    .lc.comb(/<:L>/).Bag          # Create Bag of letter/count pairs
                ($!=                    )         # Store temporarily in $!
 ... until [==]                          .values  # Until all counts are equal
 s:i|                      |    |                 # Replace (ignoring case)
     $($!.min(*.value).key)                       # letter with minimum count
                            $/$/                  # with itself doubled
}

```

# Answer
> 1 votes
# Python 2, ~~97~~ 117 bytes

```
s=input().upper()
S=''
for c in s:S+=c+c*(max(map(s.count,map(chr,range(65,91))))-(S+s).count(c))*('@'<c<'[')
print S

```

Try it online!

# Answer
> 1 votes
# C (clang), ~~246~~ ~~223~~ ~~220~~ ~~210~~ ~~208~~ ~~193~~ 188 bytes

Compiler flag `-DF=;for(i=0;b[i];i++` `-DB=b[i]` (29 bytes)

Added mixed case support.

```
f(char*c){char m,i,s,*b,a[255]={0};s=asprintf(&b,c)F)B=tolower(B),a[B]++F,a[B]>a[m]?m=B:0)F)a[B]^a[m]?b=realloc(b,s+i),bcopy(&B,b+i+1,s),a[B]++:(m=B);puts(b);}

```

Try it online!

# Answer
> 1 votes
# Pyth, ~~31~~ 30 bytes

```
JeSm/Qd=r0QVQ=tQ=+k*N-J/+kQN)k

```

Try it here

### Explanation

```
JeSm/Qd=r0QVQ=tQ=+k*N-J/+kQN)k
       =r0Q                        Convert input to lowercase.
JeSm/Qd                            Find the count of the most common character.
           VQ               )      For each character in the input...
             =tQ                   ... remove that character from the input...
                =+k*N-J/+kQN       ... append copies to k until we have enough.
                             k     Output.

```

# Answer
> 1 votes
# C (GCC) \- 175 Bytes

```
f(char*s){int c[999]={0},i=0,m=0,k,L;while((L=s[i++])&&(k=++c[L<97?L+32:L]))m=k>m?k:m;i=0;while(L=s[i++])for(L=L<97&&L>64?L+32:L,putchar(L);isalpha(L)&&++c[L]<=m;)putchar(L);}

```

**Ungolfed**

```
f(char *s) {
  int c[999]={0},i=0,m=0,k,L;                      // Array used like a dictionary, temp vars
  while((L=s[i++])&&(k=++c[L<97?L+32:L]))          // store letter counts
    m=k>m?k:m;                                     // calculate max occurance
  i=0;                                             // reset string index
  while(L=s[i++])                                  // iterate string
    for(L=L<97&&L>64?L+32:L,putchar(L);isalpha(L)&&++c[L]<=m;) // set character L to lowercase if in alphabet, print always once, repeat if in alphabet
      putchar(L);                                  // print character
}

```

Try it online!

# Answer
> 0 votes
**Kotlin Android, 413 bytes**

```
var l: List<Char> = w.toList().distinct();val h = HashMap<Char, Int>();var x='m';var n=0;for(z in l.indices){var c=0;for (i in 0.rangeTo(w.length-1)){if(l[z]==(w[i]))c++};h.put(l[z],c);if(n<c){n=c}};for(entry in h){h.replace(entry.key,n-entry.value)};var v=ArrayList<Char>();for(i  in 0.rangeTo(w.length-1)){if(h.containsKey(w[i])){for(p in 0.rangeTo(h.get(w[i])!!)){v.add(w[i])};h.remove(w[i])}else{v.add(w[i])}}

```

Try online

Explanation step 1 --\> Select list of distinct chars. step 2 --\> Get count of every char in string and select max char frequency. step 3 --\> get difference in frequency of chars with respect to max char frequency step 4 --\> place chars with respect to positions in string. Happy Solving !

# Answer
> 0 votes
# C# (Visual C# Interactive Compiler), 145 bytes

```
x=>x.ToLower().Select((a,b)=>x.IndexOf(a)==b&char.IsLetter(a)?a+new String(a,x.GroupBy(d=>x.Count(e=>e==d)).Max(d=>d.Key)-x.Count(d=>d==a)):a+"")

```

Try it online!

# Answer
> 0 votes
# PHP, ~~185~~ ~~173~~ 170 bytes

```
function($s){$m=max($a=count_chars($s=strtolower($s),1));foreach(str_split($s)as$c)$o.=str_repeat($c,($b=$a[$d=ord($c)])!=($a[$d]=$m)&&$d>96&&$d<123?$m-$b+1:1);return$o;}

```

Try it online!

Ungolfed (and un-ternaried and un-optimized).

```
function f($s) {
    $s = strtolower( $s );
    $a = count_chars( $s, 1 );
    $m = max( $a );
    foreach( str_split( $s ) as $c ) {
        if ( $c < 'a' or $c > 'z') {           // is non a-z
            $n = 1;
        } elseif ( $a[ord($c)] == $m ) {    // already has max number
            $n = 1;
        } else {
            $n = $m - $a[ord($c)] + 1;       // add this many chars
        }
        $o .= str_repeat( $c, $n );
        $a[ord($c)] = $m;                   // has reached the max
    }
    return $o;
}

```

---
Tags: code-golf, word-puzzle
---


title: Check if the 15 puzzle is solvable

text:
# Question
Title: Check if the 15 puzzle is solvable
The fifteen puzzle is peculiar in that only half the possible states of arrangement are solvable. If you flip the 14 and 15 tiles, there is no way you can slide the blocks so that they are flipped back.

Your task is to build a program that accepts a list of integers in the format of your choice (containing exactly one instance of each of the numbers from 0 to 15, with 0 being the blank space) representing the state of an arrangement of tiles in a 4x4 grid, and outputs a single boolean value determining whether the grid is solvable or not.

The shortest code to do this in any language wins.

# Answer
# Jelly, 9 bytes

```
Œc>/€;TSḂ

```

A monadic Link accepting a list of the integers reading in row-major order alternating between left-right and right-left which yields `0` if solvable and `1` if not (to invert this add `¬` to the right of the code).

**Try it online!** (this example is a board where 12 just needs to slide into place)

### How?

Similar to John Dvorak's answer we calculate parities and utilise a snake-like input order to simplify checker-board parity, although instead of checking equality of parity we sum the out-of-order count with the non-zero indices and test whether that is odd:

```
Œc>/€;TSḂ - Link: list of integers
Œc        - unordered pairs
    €     - for each:
   /      -   reduce with:
  >       -     greater than?
      T   - truthy indices (i.e. [1..16] without 1-indexed index of 0)
     ;    - concatenate
       S  - sum
        Ḃ - is odd?

```
> 0 votes

# Answer
# J, 28 characters

```
((C.!.2=_1^i.&0)&.".&.stdin''

```

The input order is row-major with rows read alternatingly left to right and right to left in a single path across the table. Assumes the zero belongs to the top left corner.

Usage on Windows:

```
<nul set /p="0 1 2 3 7 6 5 4 8 9 10 11 15 14 13 12" | jconsole c:\...\15.jhs

```

Explanation:

* `<nul set /p=` is used to prevent a newline in the input, that `echo` produces that `".` doesn't like. Of course, Unix supports `echo /n`.
* `v&.".&.stdin''` reads "v under parse under stdin" meaning "input, then parse the input, then do v, then undo parse (= format), then undo input (=output)". `1!:1]3` is one character shorter, but it does not have a defined inverse.
* `C.!.2` means "permutation parity". It returns either `1` (even parity) or `_1` (odd parity). That is, `_1^inversions`
* `_1^i.&0` means "-1 to the power of index of 0".
* thus, `C.!.2=_1^i.&0` means "does the permutation parity equal the hole position parity?"

This works for a 4x4 board, but if the desired end position is row-major left-to-right, then the permutation for the solved position has an odd number of inversions, and thus odd parity. Also, the parity is reversed (for any input order) when the desired hole position moves from upper left to bottom right. In both cases, the fix is one character: add `-` after `=` to reverse the expected parity.

Proof of correctness:

After each move, the zero exchanges a position with some number, flipping the permutation parity. The zero also alternates between white and black checkerboard positions, indicated by odd and even positions in the input ordering. Thus, this condition is neccessary. It is also sufficient by the counting argument: it is common knowledge that exactly half of the positions is solvable. This condition filters out exactly half of the possible positions.
> 5 votes

---
Tags: code-golf, decision-problem, sliding-puzzle
---