title: Turn a string into a windmill

text:
# Question
Title: Turn a string into a windmill
The code on this site is rapidly being depleted. We need to invest in renewable strings. So you must write a program that takes a string and converts it into a windmill.

# The Challenge

Let's take a simple wind-mill string as an example. Take the string `abc`. The *pivot* is the center character, in this case `b`. Since the string is 3 chars long, every output will be *exactly* three lines tall and three characters wide. Here is your output on step 1. (Note the whitespace)

```

abc

```

To get the next step, rotate each character around the pivot clockwise. Here is step 2:

```
a
 b
  c

```

Here are steps 3-8:

```
 a
 b
 c

```

```
  a
 b
c

```

```

cba

```

```
c
 b
  a

```

```
 c
 b
 a

```

```
  c
 b
a

```

And on the ninth step, it comes around full circle to the original string:

```

abc

```

Note that the `b` stayed in the same spot the whole time. This is because `b` is the pivot character. You must write a program or function that takes a string as input and repeatedly prints out this sequence until the program is closed.

# Clarifications

* All input strings will have an odd number of characters. (So that every windmill will have a pivot)
* To keep the challenge simple, all strings will only contain upper and lowercase alphabet characters.
* The output must be `len(input_string)` characters wide and tall.
* It doesn't matter which step of the sequence you start on, just as long as you continue rotating and looping forever.

# More Test IO:

Since the post is already pretty long, here is a link to the output for "windmill":

# Sidenote:

Since this is supposed to be a windmill, it would be awesome if you include some boilerplate code to animate it with a small time delay or a user input between each step. However, since some languages don't have time builtins, this is not mandatory. The competing part of your submission can just print the sequence as fast as possible.

# Answer
> 7 votes
# MATL, ~~35~~ ~~33~~ 21 bytes

```
jtn2/kYaG1$Xd`wtD3X!T

```

The following will animate the windmill (**26 bytes**)

```
jtn2/kYaG1$Xd`wtXxDlY.3X!T

```

**Online Demo**

In this version , the `Xx` specifies to clear the display and the `1Y.` is a 1-second pause.

**Explanation**

The basic idea is that we want to create two versions of the input. An "orthogonal" version

```
+-----+
|     |
|     |
|abcde|
|     |
|     |
+-----+

```

And a "diagonal" version

```
+-----+
|a    |
| b   |
|  c  |
|   d |
|    e|
+-----+

```

We push these two versions onto the stack. Each time through the loop, we switch the order of stack and rotate the top one clockwise.

```
j       % Grab the input as a string
t       % Duplicate the input

%--- Create the "orthogonal" version ---%

n2/     % Determine numel(input) / 2
k       % Round down to nearest integer
Ya      % Pad the input string with floor(numel(input)/2) rows above and below

%--- Create the "diagonal" version ---%

G       % Grab the input again
1$Xd    % Place the input along the diagonal of a matrix

`       % do...while loop
  w     % Flip the order of the first two elements on the stack
  t     % Duplicate the top of the stack

  %--- OCTAVE ONLY (converts NULL to space chars) ---%

  O       % Create a scalar zero
  32      % Number literal (ASCII code for ' ')
  XE      % Replaces 0 elements in our 3D array with 32 (' ')

  %--- END OCTAVE ONLY ---%

  D     % Display the element
  3X!   % Rotate this element 90 degrees counter-clockwise 3 times (clockwise)
  T     % Explicit TRUE to create an infinite loop
        % Implicit end of while loop

```

# Answer
> 8 votes
## JavaScript (ES6), 291 bytes

```
r=a=>{w.textContent=a.map(a=>a.join``).join`
`;for(i=j=h=a.length>>1;j++,i--;){t=a[i][i];a[i][i]=a[h][i];a[h][i]=a[j][i];a[j][i]=a[j][h];a[j][h]=a[j][j];a[j][j]=a[h][j];a[h][j]=a[i][j];a[i][j]=a[i][h];a[i][h]=t}}
s=w=>{a=[...w=[...w]].map(_=>w.map(_=>' '));a[w.length>>1]=w;setInterval(r,1000,a)}
s("windmills")
```

```
<pre id=w>
```

# Answer
> 5 votes
# 05AB1E, ~~88~~ 53 bytes

Code:

```
¹VYg;ïU[2FX¶×DYsJ,YvNð×y¶J?}YvðX×yJ,}Yv¹gN>-ð×yJ,}YRV

```

Try it online!. Make sure to hit the kill button right after you run it, because it goes into an infinite loop.

# Answer
> 5 votes
# Ruby, ~~122~~119 bytes

```
->n{c=0
loop{i=[l=n.size,m=l+1,m+1,1][3-c=c+1&7]*(3.5<=>c)
s=(' '*l+$/)*l
l.times{|j|s[m*l/2-1+(j-l/2)*i]=n[j]}
$><<s}}

```

**Ungolfed version with sleep, in test program**

The rotation isn't very convincing at full console height. But if you reduce the height to the the length of the input string, the rotation is a lot more convincing.

```
f=->n{
  c=0                                     #loop counter
  m=1+l=n.size                            #l=string length. m=l+1
  loop{                                   #start infinite loop
    s=(' '*l+$/)*l                        #make a string of l newline-terminated lines of l spaces. Total m characters per line.
    i=[m-1,m,m+1,1][3-c=c+1&7]*(3.5<=>c)  #array contains positive distance between characters in string 1=horizontal, m=vertical, etc.
                                          #c=c+1&7 cycles through 0..7. Array index 3..-4 (negative indices count from end of array, so 3=-1, 0=-4 etc)
                                          #(3.5<=>c) = 1 or -1. We use to flip the sign. This is shorter than simply using 8 element array [m-1,m,m+1,1,1-m,-m,-m+1,-1]
    l.times{|j|s[m*l/2-1+i*(j-l/2)]=n[j]} #for each character in n, write the appropriate space character in s to the character in n
    puts s                                #print s
    sleep 1                               #sleep for 1 second
  }
}

f[gets.chomp]                             #get input, remove newline, call function

```

# Answer
> 3 votes
# MATL, ~~47~~ 44 bytes

```
' 'jntX"tGtnXyg(wGtnQ2/Y(XJDXKD`J@_X!DK3X!DT

```

Try it online! (but kill it immediately, infinite loop)

With 1-second pause: **56 bytes**

```
' 'jntX"tGtnXyg(wGtnQ2/Y(XJD1Y.XKD1Y.`J@_X!D1Y.K3X!D1Y.T

```

Try it online! (again, infinite loop)

# Answer
> 3 votes
# **Python 3**, 193 bytes

```
def c(a):e=' ';s=len(a);l=int(s/2);b=range(s);m='\n'*l;print(m,a,m);for x in b:print(e*x,a[x]);for x in b:print(e*l,a[x]);for x in b:print(e*(s-1-x),a[x]); a=input();while True:c(a);c(a[::-1]);

```

**Ungolfed**

```
def c(a):
    e=' ';s=len(a);l=int(s/2);b=range(s);m='\n'*l;
    print(m,a,m);
    for x in b:print(e*x,a[x]);
    for x in b:print(e*l,a[x]);
    for x in b:print(e*(s-1-x),a[x]);
a=input();
while True:
    c(a);
    c(a[::-1]);

```

## Recursive, 177 bytes

(crash after a few seconds)

```
def c(a):e=' ';s=len(a);l=int(s/2);b=range(s);m='\n'*l;print(m,a,m);for x in b:print(e*x,a[x]);for x in b:print(e*l,a[x]);for x in b:print(e*(s-1-x),a[x]);c(a[::-1]);c(input());

```

**Ungolfed**

```
def c(a):
    e=' ';s=len(a);l=int(s/2);b=range(s);m='\n'*l;
    print(m,a,m);
    for x in b:print(e*x,a[x]);
    for x in b:print(e*l,a[x]);
    for x in b:print(e*(s-1-x),a[x]);
    c(a[::-1])
c(input());

```

## Another solution, 268 bytes

```
import itertools as i;def w(a):e=' ';s=len(a);l=int(s/2);t='\n';m=(l-1)*t;h=list(i.chain.from_iterable((e*x+a[x],e*l+a[x],e*(s-1-x)+a[x]) for x in range(s)));print(m,a,m,t.join(h[::3]),t.join(h[1::3]),t.join(h[2::3]),sep=t,end='');a=input();while True:w(a);w(a[::-1]);

```

**Ungolfed**

```
import itertools as i;
def w(a):
    e=' ';s=len(a);l=int(s/2);t='\n';m=(l-1)*t;
    h=list(i.chain.from_iterable((e*x+a[x],e*l+a[x],e*(s-1-x)+a[x]) for x in range(s)))
    print(m,a,m,t.join(h[::3]),t.join(h[1::3]),t.join(h[2::3]),sep=t,end='');
a=input();
while True:
    w(a);
    w(a[::-1]);

```

# Answer
> 2 votes
# Pyth, 48 bytes

```
JlzK/J2#*btKz*btKM+*dG@zHVJgNN)VJgKN)VJg-JNN)=_z

```

Try it online! (Note: this is a version that does not forever loop, because it would crash the interpreter.)

Shamelessly translated from the Python 3 solution by @ByHH.

How it works:

```
JlzK/J2#*btKz*btKM+*dG@zHVJgNN)VJgKN)VJg-JNN)=_z
                                                 assign('z',input())
Jlz                                              assign("J",Plen(z))
   K/J2                                          assign("K",div(J,2))
       #                                         loop-until-error:
        *btK                                      imp_print(times(b,tail(K)))
            z                                     imp_print(z)
             *btK                                 imp_print(times(b,tail(K)))
                                                  @memoized
                 M                                def gte(G,H):
                  +*dG@zH                          return plus(times(d,G),lookup(z,H))
                         VJ   )                   for N in num_to_range(J):
                           gNN                     imp_print(gte(N,N))
                               VJ   )             for N in num_to_range(J):
                                 gKN               imp_print(gte(K,N))
                                     VJ     )     for N in num_to_range(J):
                                       g-JNN       imp_print(gte(minus(J,N),N))
                                             =_z  assign('z',neg(z))

```

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


title: Validate a Wikipedia page name

text:
# Question
Title: Validate a Wikipedia page name
Wikipedia has several restrictions on an article's title. I summarize them here:

* It may not be empty.
* It may not begin with a lowercase letter. A character is considered lowercase if it has an `Ll` after its name in UnicodeData.txt.
* It may not contain any of the characters: `# < > [ ] | { } _`
* It may not be `.` or `..`
* It may not begin with `./` or `../`.
* It may not contain `/./` or `/../`.
* It may not end with `/.` or `/..`.
* It may not contain any space character (a character is considered a space if it has `Zs` after its name in UnicodeData.txt) except for `U+0020 SPACE`.
* It may not contain more than one consecutive space.
* It may not consist entirely of spaces.
* It may not begin with a colon.
* It may not begin with the language prefix of any of the 292 language editions of Wikipedia followed by a colon. This includes `en:` for English.
* It may not begin with the prefix of another Wikimedia Foundation project or its shortcut followed by a colon.
* It may not contain the character `%` followed by two hexadecimal digits.
* It may not contain a named HTML character entity. Numbered entities are already forbidden through `#`.
* It must contain no more than 256 bytes when encoded in UTF-8.

Write a function that takes in a string (or whatever data type your language normally uses to manipulate text) and outputs a boolean indicating whether the string is a valid Wikipedia article title. You are permitted to use networking libraries to download and read from any page that I linked in this question.

# Answer
> 4 votes
# Retina, 1221 bytes

```
^(?=...:|\w|(^|.*/)\.\.?(/.*|$)|.*([#<>\[\]|{}]|  |__|%[0-9a-fA-F]{2}|&#(\d{4}|[0-9a-fA-F]{4}|a(mp|pos)|(l|g|quo)t);|~~~)|[ _]*$|.{257,}).*
no
^(?!no$).+
yes

```

where `...` is:

```
(w(ik(i(s(pecies|ource)|v(ersity|oyage)|([mp]edi|dat)a|(book|new)s|quote|tech)|t(ionary)?)|m(i[dlnt]|c[ahz]|a[ru]|b[de]|d[ek]|h[ku]|n[lo]|r[su]|u[ak]|fi?|mk|pl|se|tw)|ar?|uu|o)?|m(e(dia(wikiwiki|zilla)|t(awikipedi)?a)|a(p-bms|i)|[klnr]|[ghi]|[iz]n|[st]|yv?|df|hr|rj|us|wl)|s([degh]|t(rategy|q)|i(mple)?|[klmnoqr]|c(n?|o)|pecies|[uvw]|[st]|ah?|rn|zl)|b(a(t-smg|r?)|ug(zilla)?|e-tarask|[eghi]|[mno]|[rs]|cl|jn|py|xr)|t([aghw]|e(stwiki|t)?|[iklno]|oollabs|[rst]|yv?|pi|um)|c(o(mmons)?|h[ory]?|[es]b?|bk-zam|[uvy]|rh?|do|kb|a)|p(habricator|a[gmp]?|n[bt]|[st]|f?l|ih?|cd|dc|ms)|n(ds(-nl)?|[glno]|a[hp]?|[vy]|ew?|ov|rm|so)|a([afkm]|r[cz]?|[vyz]|ng?|st?|z?b|ce|dy|ls)|k([gijklmnor]|[uvwy]|a[ab]?|sh?|bd|oi|rc)|z(h(-(classical|min-nan|yue))?|e?a|u)|f([afijory]|oundation|iu-vro|r[pr]|ur)|l([gi]|[no]|ad?|be?|tg?|ez|ij|mo|rc|v)|r([nw]|o(a-(tara|rup))?|my?|ue?)|g(a[gn]?|[dln]|o[mt]|[uv]|lk)|h([eiortu]|a[kw]?|[yz]|if|sb)|i([adegikostu]|ncubator|lo)|v(e(c?|p)|oy?|ls|i)|d([vz]|[ae]|iq|sb)|e([elnostu]|ml|xt)|u([gz]|[kr]|dm)|j([av]|bo)|x(al|mf|h)|[nbqsvcdm]|o[cmrs]|y[io]|qu|)

```

(I used this regex optimizer and manutally typed in all the data)

Try it online without the `...`!

---
Tags: code-golf
---


# Question
Title: Optimal solution to go to opposite corner of a rectangle
Your job is to write a program that finds the optimal number of moves it takes to get from the lower-left corner of a rectangle to the upper-right corner directly opposite.

Your program will accept input as an ordered pair `(width, height)`. These will be the dimensions of the rectangle you will work with. Your program will create an ASCII-art of the solution (use `.` for empty square and `#` for part of the solution, `X` for starting square) and count the number of moves it takes to reach the endpoint. Diagonal moves are not allowed. If there are multiple solutions, choose one to output.

The shortest program in bytes wins.

**Example**

Input: `(4, 5)`

Output:

```
..##
..#.
.##.
.#..
X#..

```

Move count: 7

# Answer
> 0 votes
# 05AB1E, ~~27~~ 24 bytes

Code:

```
+Í,¹<'.×'#¶J²<×'X'#¹<×J,

```

Explanation:

```
+                         # Add the length and the height.
 Í                        # Decrease by two.
  ,                       # Print this value with a newline.
   ¹<'.×                  # Take the first input, decrease by 1 and multiply with ".".
        '#¶               # Push a "#"-character and a newline character.
           J              # Join the string.
            ²<            # Take the second input and decrease by 1.
              ×           # Multiply the joined string with this value.
               'X         # Push the "X"-character.
                 '#¹<×J   # Multiply the "#"-character with (first input - 1).
                       ,  # Pop and print with a newline.

```

Try it online!. Uses **CP-1252** encoding.

# Answer
> 3 votes
## Retina, ~~54~~ 53 bytes

```
\d+
$*.
S_`(?<=(.+)¶.*).|\D
T`.`#`.¶|.*$
:m-1=`^#
X
#

```

Takes input separated by a linefeed and outputs the solution grid followed by the move count.

Try it online!

### Explanation

```
\d+
$*.

```

Turn both integers into that many `.`s, i.e. convert them to unary.

```
S_`(?<=(.+)¶.*).|\D

```

This builds a grid of `.`s, by matching each `.` in the unary height and capturing the unary representation of the width. The `S` activates split mode which returns the captured strings, and the `|\D` and `_` together ensure that everything else is removed from the string.

```
T`.`#`.¶|.*$

```

This turns the last character of each line as well as the entire last line into `#`s.

```
:m-1=`^#
X

```

This uses a ton of options to convert only the first `#` on the last row to `X` (we need to make sure that only the last row is affected because of width-1 inputs). `m` activates multi-line mode which makes `^` match the beginning of lines. `-1=` tells Retina to perform the substitution only on the last match. Finally, `:` switches off the default silent mode such that the grid is printed to STDOUT as an intermediate result.

```
#

```

Finally, we simply count the number `#` in the string, which corresponds to the number of moves.

# Answer
> 3 votes
## Pyke, 26 bytes

```
DtQ+RtF; Q\.*t\#+)\X\#Qt*+

```

Try it here

---

Or a noncompetitive 34 bytes, add apply node with an ast)

```
jUa]Dm!X|RZjht]q+".#X"R@)Fs
);jmts

```

Try it here!

Or 30 bytes if allowed spaces as padding

```
jUa]Dm!X|RZjht]q+".#X"R@)Pjmts

```

# Answer
> 2 votes
# Pyth, ~~32~~ ~~29~~ 24 bytes

```
AtMQVH+*\.G\#;+\X*\#G+GH

```

Try it online!

Sample input:

```
(4, 5)

```

Sample output:

```
...#
...#
...#
...#
X###
7

```

How it works:

```
AtMQVH+*\.G\#;+\X*\#G+GH
                           assign('Q',eval_input())
AtMQ                       assign('[G,H]',Pmap(lambda d:tail(d),Q))
    VH       ;             for N in range(H):
      +*\.G\#                  implicit_print(plus(times(".",G),"#"))
              +\X*\#G      implicit_print(plus("X",times("#",G)))
                     +GH   implicit_print(plus(G,H))

```

---

Previous attempt:

```
JthQK@Q1+*++*\.J\#btK+\X*\#Jt+JK

```

Try it online!

Sample input:

```
(4, 5)

```

Sample output:

```
...#
...#
...#
...#
X###
7

```

How it works:

```
JthQK@Q1+*++*\.J\#btK+\X*\#Jt+JK
                                 assign('Q',eval_input())        --Q is now an official pair of numbers (4, 5)
JthQ                             assign("J",decrement(first(Q))) --gets the first element, and then take 1 from it, and assign it to J
    K@Q1                         assign("K",lookup(Q,1))         --K is now the second element (count from 0) of the pair.
        +            +\X*\#J     concat(-----------------------------------------------------------,concat("X",times("#",J)))
         *         tK                   repeat(--------------------------------------,decrement(K))
          +       b                            concat(-------------------------,"\n")
           +    \#                                    concat(-------------,"#")
            *\.J                                             repeat(".",J)
                            t+JK decrement(add(J,K)) <--- auto-print

```

# Answer
> 1 votes
## CJam, ~~35~~ 33 bytes

```
q~\(_2$(+p'.*a*'#f+)W%_"X#"era+N*

```

Takes input in the form `width height` and outputs the move count on the first line, followed by the solution grid.

Test it here.

This also works for the same byte count:

```
q~\('.*a*'#f+)W%_"X#"era+N*_'#e=p

```

# Answer
> 1 votes
# Ruby, 48 bytes

This is an anonymous function, which according to this meta post is acceptable unless the question states "full program." I wouldn't normally be pedantic about this but the problem is very simple and doing a program would be a significant % increase to the score.

Input is two arguments. Return value is an array containing the ASCII art string and the number of `#` in the path.

```
->w,h{[(?.*(w-=1)+'#
')*(h-=1)+?X+?#*w,w+h]}

```

**In test program**

```
f=->w,h{[(?.*(w-=1)+'#
')*(h-=1)+?X+?#*w,w+h]}

puts f[4,5]

```

**Output**

```
...#
...#
...#
...#
X###
7

```

It's just a string of h-1 rows of w-1 dots, followed by a `#` and newline. I put the `#` at the end in order to use a single `#\n` literal for both `#` and newline (the code contains an actual newline rather than an escape sequence.) The final row is then an `X` followed by w-1 `#`'s.

It was shorter to decrement the values of w and h during the ASCII art generation, so that the final calculation is simply `w+h`.

# Answer
> 1 votes
# MATL, ~~28~~ ~~26~~ 25 bytes

```
+qq35IMwX"46 5Lt4$(88HG(c

```

*EDIT (June 10, 2016): the link below includes a modification ( `5L` is replaced by `IL`) to adapt to changes in the language*

**Try it online!**

### Explanation

```
+       % take two inputs. Add them
qq      % subtract 2
35      % push ASCII for '#'
IMw     % push the two inputs again. Swap them
X"      % 2D char array of '#'  repeated as indicated by inputs
46      % push ASCII for '.'
5Lt4$(  % fill all but last and row columns with that
88HG(   % fill 88 (ASCII for 'X') at linear index given by second input
c       % convert to char

```

# Answer
> 1 votes
# JavaScript (ES6), 60 bytes

```
w=>h=>--w+--h+`
${"."[r="repeat"](w)}#`[r](h)+`
X`+"#"[r](w)

```

## Usage

```
f(4)(5)

7
...#
...#
...#
...#
X###

```

# Answer
> 0 votes
# Java, ~~137~~ 132 bytes

```
w->h->{String s="";int i=0,j;for(;i<h;i++){for(j=1;j<w;j++)s+=".";s+="#\n";}s+="X";for(j=1;j<w;j++)s+=".";s+="\n"+(w+h-2);return s;}

```

# Answer
> 0 votes
# Scala, 118 bytes

```
(w:Int,h:Int)=>{print(Array.fill(h-1,w-1)('.')map(new String(_))mkString("","#\n","#\nX"));Seq.fill(w-1)(print("#"))}

(w:Int,h:Int)=>{...}           //define a function with 2 Ints as parameters
print(                        //print ...
  Array.fill(h-1,w-1)('.')    //an array of arrays with dimensions (h-1,w-1)
                              //and fill it with a dot
  map(new String(_))          //map each inner array of chars to a string
  mkString("","#\n","#\nX")   //create a string from the array, with
                              //an empty string before the array,
                              //"#\n" as a seperator between the elements
                              //and "#\nX" at the end
);
Seq.fill(w-1)(print("#"))     //w-1 times print "#"

```

# Answer
> 0 votes
## Haskell, 64 bytes

```
c!n=c<$[2..n]
w#h=unlines$('.'!w++"#")!h++['X':'#'!w,show$w+h-2]

```

Usage example:

```
*Main> putStr $ 4 # 5
...#
...#
...#
...#
X###
7

```

How it works:

```
c!n = c <$ [2..n]                       -- helper function: make (n-1) copies of c

                                        -- main function
                     !h                 -- (h-1) times
       ('.'!w ++ "#")                   --    (w-1) dots and a hash sign
                       ++[      ,     ] -- followed by
                          'X' : '#'!w   --    an 'X' and (w-1) hash signs
                            show$w+h-2  --    and the number of steps
unlines                                 -- join everything with newlines in-between

```

# Answer
> 0 votes
# Lua, 81 bytes

Try it online!

Golfed:

```
w,h=(...)print((("."):rep(w-1).."#\n"):rep(h-1).."X"..("#"):rep(w-1))print(w+h-2)

```

Ungolfed:

```
w,h=4,5
print((("."):rep(w-1).."#\n"):rep(h-1).."X"..("#"):rep(w-1))
print(w+h-2)

```

# Answer
> 0 votes
## Python, 48.

```
lambda w,h:('.'*(w-1)+'#\n')*(h-1)+'X'+'#'*(w-1)

```

To use it, add `f=` before the line above and call it like this:

```
f(4, 5)

```

Result:

```
...#
...#
...#
...#
X###

```

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


# Question
Title: Find the shortest way to advance a counter to a certain number
I have a counter. It's a small device that looks like this:

The display goes from `0000` to `9999`. It has a little push-button at the top that increases the count by 1, and a little knob at the right whose purpose is to reset the counter back to 0.

Now, the thing about the little knob is that if you turn it backwards, you can make it increase any digit that you want once you turn it forwards again. So if I push the counter button 10 times so that the counter shows `0010`, I can then turn the knob backwards until i hear a tiny click, then turn it forwards again and make it go straight to `0090`.

But, the knob will always increase all occurrences of the same digit by 1 every time it pushes numbers forward. So if the counter shows `6060`, you can only make it increase to `7070`, not to `6070` or `7060`. Also, the knob will roll `9`s over to `0` without carrying, so `0990` will advance to `0000` instead of `1000` or `1100`.

---

I want to know the most efficient way to set the counter to a certain number. Your task is to write a program or function that will determine the shortest sequence of button pushes and knob advancements required to do so.

Your program will take as input a 4-digit number from `0000` to `9999`, and return a series of steps in the following format:

```
> 0001
C
> 0093
C12345678C12345678CCC
> 1000
C12345678C12345678C12345678C12345678C12345678C12345678C12345678C
> 9999
012345678

```

Where `C` stands for "push the counter button" and any digit `D` from 0 to 9 stands for "use the knob to advance all occurrences of `D` by 1".

Your program must produce a valid sequence of steps for all possible four-digit combinations, and will be scored by the total number of steps required for all 10,000 cases. In the case of a tie (most likely when the optimal algorithm is found), the shorter code will win.

# Answer
# Pyth, 327763 steps (optimum, 130 bytes)

Since the online compiler is inept at dealing with such enormous task, I have given it less work, so that it only generates `0`, `1`, and `1111`. However, it can theoretically solve the problem, because it uses the same algorithm as the Lua at the top.

Try it online!

```
=Y.d((0k;V53=ZYFGY XZG=k@YG=N%"%04d"GV4=b@NH=di:Nb%"%d"ehibTT XZd.x?>l@Ydlk+kb@Yd+kb)=bhGI<G9999 XZb.x?>l@Yblk+k\C@Yb+k\C))=YZ;@YQ

```

---

How it works:

```
=Y.d((0k;V53=ZYFGY XZG=k@YG=N%"%04d"GV4=b@NH=di:Nb%"%d"ehibTT XZd.x?>l@Ydlk+kb@Yd+kb)=bhGI<G9999 XZb.x?>l@Yblk+k\C@Yb+k\C))=YZ)@YQ
                  assign_copy('Q',eval_input())
=Y.d((0k;         assign_copy('Y',dict(0=k))
V53               for N in range(0,53):
=ZY                   assign_copy('Z',Y)
FGY                   for G in num_to_range(Y):
 XZG=k@YG                 no_print(Z[G] = assign_copy('k',lookup(Y,G)))
=N%"%04d"G                assign_copy('N',format("%04d",G))
V4                        for H in range(0,4):
=b@NH                         assign_copy('b',lookup(N,H))
=di:Nb%"%d"ehibTT             assign_copy('d',base(replace(N,b,format("%d",mod10(increment(base(b,10))))),10))
 XZd.x?>l@Ydlk+kb@Yd+kb       no_print(Z[d]=try_and_catch(greater_than(Plen(lookup(Y,d)),Plen(k)) ? concat(k,b) : lookup(Y,d)), lambda:plus(k,b))
)                         <anti-indent>
=bhG                      assign_copy('b',head(G))
I<G9999                   if less_than(G,9999):
 XZb.x?>l@Yblk+k\C@Yb+k\C     no_print(Z[b]=try_and_catch(greater_than(Plen(lookup(Y,b)),Plen(k)) ? concat(k,"C") : lookup(Y,b)), lambda:plus(k,"C"))
)                         <anti-indent>
)                     <anti-indent>
=YZ                   assign('Y',Z)
)                 <anti-indent>
@YQ               print(lookup(Y,Q))

```
> 1 votes

# Answer
# Lua, 327763 steps (optimum, 276 bytes)

Golfed version:

```
a={[0]=""}t=tonumber for i=0,52 do A={}for k,v in pairs(a)do A[k]=v L=("%04d"):format(k)for i=1,4 do c=L:sub(i,i)d=L:gsub(c,(t(c)+1)%10)e=a[t(d)]A[d]=(not e or #e>#v)and v..c or e end b=k+1 if k<9999then e=a[b]A[b]=(not e or #e>#v)and v.."C"or e end end a=A endprint(a[(...)])

```

Improved version of the examples in question (only `1000` is improved):

```
0001:C
0093:CCCCCCCCCC12345678CCC
1000:0CCCCCCCCCCC2345678C23456789
     (0000>1111>1122>1199>1200>1000)
9999:012345678

```

Ungolfed version:

```
a = {[0]=""}
for i=0,52 do
    A = {}
    for k,v in pairs(a) do
        A[k] = v
        L=("%04d"):format(k)
        for i=1,4 do
           c=L:sub(i,i)
           d=L:gsub(c,(tonumber(c)+1)%10)
           e=a[tonumber(d)]
           A[d] = (not e or #e > #v) and v..c or e
        end
        b=k+1
        if k < 9999 then
            e=a[b]
            A[b] = (not e or #e > #v) and v.."C" or e
        end
    end
    a=A
end
print(a[93],a[1000],a[9999])

```
> 5 votes

# Answer
# Mathematica, score 512710

```
Unprotect[StringRepeat]
StringRepeat[x_String, 0]:=""
Protect[StringRepeat]
#<>StringRepeat["C",#3-#2*1111]&[Array[ToString@#&,#,0],##]&[If[#<10^3,0,Quotient[#,1111]],#]&

```

Fixes a bug with `StringRepeat` (behaves incorrectly for `StringRepeat[x_String,0]`)
> 1 votes

# Answer
# JavaScript (ES6), 327763 steps (optimum, 184 bytes)

A Breadth First Search, not so smart and not so fast.

```
t=>eval("for(k=[],s=[['0000',i='']];[u,p]=s[i++],u-t;k[v=(1+u-~0+'').slice(-4)]=k[v]||s.push([v,p+'C']))[...u].map(x=>k[v=[...u].map(y=>x-y?y:-~x%10).join``]=k[v]||s.push([v,p+x]));p")

```

**Less golfed**

```
t=>{
  k=[]; // mark values already found to reduce search
  for( i=0, s=[['0000','']];
       [u,p]=s[i++], // u: current code, p:current steps
       u != t; // exit if target found
     )
  {
     // try all digits present in current code
     [...u].map(x=> {
       v=[...u].map(y=>x-y?y:-~x%10).join`` // apply digit x to u
       if (!k[v]) // check if value v not found already
          k[v] = s.push([v,p+x]));
     })
     v=(1+u-~0+'').slice(-4); // try operator C
     if (!k[v]) // check if value v not found already
       k[v] = s.push([v,p+'C']))
  }
  return p
}

```

**Test**

```
f=t=>eval("for(k=[],s=[['0000',i='']];[u,p]=s[i++],u-t;k[v=(1+u-~0+'').slice(-4)]=k[v]||s.push([v,p+'C']))[...u].map(x=>k[v=[...u].map(y=>x-y?y:-~x%10).join``]=k[v]||s.push([v,p+x]));p")

function SingleTest()
{
  var i=S.value
  if (/^\d{4}$/.test(i)) X.value=f(i)
  else X.value='invalid input'
}

SingleTest()

function LongTest()
{
  var i=0,v,r,t=0

  var step=_=>{
    v = ('000'+i).slice(-4);
    r = f(v);
    t+= r.length
    V.value = v;
    R.value = r;
    T.value = t;
    ++i;
    if(i<10000) setTimeout(step, 0)
  }

  step()
}
```

```
#V,#T,#S { width:5em }
#R,#X { width: 25em }
```

```
Single Test <input id=S value='0093'><button onclick="SingleTest()">-></button><input readonly id=X><hr>
Long test (0000 ... 9999) <button onclick="LongTest()">Go</button>(i mean <i>long</i>, runtime 1 hour)<br>
<input readonly id=V>
<input readonly id=R>
Total steps:<input readonly id=T>
```
> 1 votes

---
Tags: code-challenge, test-battery
---


title: How many sides does this polygon have?

text:
# Question
Title: How many sides does this polygon have?
So in 1st grade math, you learn the names of polygons. Three sides is a triangle, 4 is a square, and 5 is a pentagon. However, in 1st grade honors, you go a bit further.

## Your challenge

There is a naming system for polygons above a few sides, so arbitrarily large polygons have a name.

Your task is to write a program or a function that **accepts the name of a polygon as input** and **outputs the number of sides** it has.

The names of polygons are defined as in the left column of this wikipedia article with a few exceptions.

Three sided polygons will be called a triangle instead of a trigon and 4 sided polygons will be a square instead of a tetragon (assume that all the polygons are regular). Otherwise, the names in the article will be used.

## Rules

* Input will be a string value.
* The program should print the result to STDOUT (or it should return an integer).
* Only polygons between 3 and 99 will be inputted.
* Your program must satisfy all test cases.
* No standard loopholes.
* The program doesn't need to do anything for invalid/out of range inputs.
* Scoring is in bytes. Since this is , shortest program wins.

## Test cases

```
3   triangle
4   square
5   pentagon
10  decagon
11  hendecagon
12  dodecagon
13  triskaidecagon
20  icosagon
21  icosikaihenagon
22  icosikaidigon
34  triacontakaitetragon
35  triacontakaipentagon
36  triacontakaihexagon
47  tetracontakaiheptagon
48  tetracontakaioctagon
49  tetracontakaienneagon
64  hexacontakaitetragon
80  octacontagon
81  octacontakaihenagon
99  enneacontakaienneagon

```

## Leaderboards

Here is a Stack Snippet to generate both a regular leaderboard and an overview of winners by language.

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

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

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

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
# Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
# Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the *last* number in the header:

```
# Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the leaderboard snippet:

```
# [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

# Answer
> 7 votes
# Ruby, ~~405~~ 207 bytes

207 bytes

```
->a{i,n=0,"#{a}";[/ontag|sa/,/(he|mo)n/,/di|do|ic/,/tri/,/tet|q/,/pe/,/hex/,/hep/,/oc/,/enn/,/^d/,/1d/,/2d/].each{|r|n.gsub!(r,i.to_s);i+=1;};n=n.gsub(/ide/,'!').gsub(/[a-z]/,'');n='1'+n[0] if /!/=~n;n.to_i}

```

Ungolfed 207

```
    sides = ->a{
          i,n=0,"#{a}";
          # Match patterns for zero, one, two, etc.
          # Each regex corresponds to a digit.
          # Special patterns for 10, 11 and 12.
          [/ontag|sa/,/(he|mo)n/,/di|do|ic/,/tri/,
             /tet|q/,/pe/,/hex/,/hep/,/oc/,/enn/,
             /^d/,/1d/,/2d/].each {|r| n.gsub!(r, i.to_s);i+=1;};
          n=n.gsub(/ide/,'!').  # Change part of the teens to exclamation
              gsub(/[a-z]/,''); # Remove remaining unmatched letters
          n='1'+n[0] if /!/=~n; # Fixup the teens
          n.to_i
      }

```

405 bytes:

```
->a{d=%w(on hen d tr te p hex hep oc e);case a when/de/ then %w(de hen do tr te p hex hep o e ).index(a[/^(he|t|d)?./]||:de)+10;when/^([mdtspoe]|he[xp]).{,7}$/ then %w(z m d t s p hex hep o e).index($1);when/^i.*[ks]a.([dep]|on|oc|tr|te|hen|hex|hep)/ then d.index($1)+20;when/^((he|t)?[^ht]).*nta(kai)?([gdpoe]|tr|te|hen|hex|hep)/ then (3+%w(tr te p hex hep o e).index($1))*10+(d.index($4)||0)else 0;end}

```

Ungolfed 405

```
def sides(a)
  d=%w(on hen d tr te p hex hep oc e);
  case a
    when /de/ then %w(de hen do tr te p hex hep o e ).index(a[/^(he|t|d)?./]||:de)+10;
    when /^([mdtspoe]|he[xp]).{,7}$/ then %w(z m d t s p hex hep o e).index($1);when/^i.*[ks]a.([dep]|on|oc|tr|te|hen|hex|hep)/ then d.index($1)+20;
    when /^((he|t)?[^ht]).*nta(kai)?([gdpoe]|tr|te|hen|hex|hep)/ then (3+%w(tr te p hex hep o e).index($1))*10+(d.index($4)||0)
    else 0;
  end
end

```

Maybe not the best golf submission, but it might win an obfuscated code contest!

Test

```
polygons = %w(
  gone
  monogon digon
  triangle square
  pentagon hexagon
  heptagon octagon
  enneagon decagon
  hendecagon dodecagon
  triskaidecagon tetrakaidecagon
  pentakaidecagon hexakaidecagon
  heptakaidecagon octakaidecagon
  enneakaidecagon icosagon
  icosikaihenagon icosikaidigon
  icosikaitrigon icosikaitetragon
  icosikaipentagon icosikaihexagon
  icosikaiheptagon icosikaioctagon
  icosikaienneagon triacontagon
  triacontakaihenagon triacontakaidigon
  triacontakaitrigon triacontakaitetragon
  triacontakaipentagon triacontakaihexagon
  triacontakaiheptagon triacontakaioctagon
  triacontakaienneagon tetracontagon
  tetracontakaihenagon tetracontakaidigon
  tetracontakaitrigon tetracontakaitetragon
  tetracontakaipentagon tetracontakaihexagon
  tetracontakaiheptagon tetracontakaioctagon
  tetracontakaienneagon pentacontagon
  pentacontakaihenagon pentacontakaidigon
  pentacontakaitrigon pentacontakaitetragon
  pentacontakaipentagon pentacontakaihexagon
  pentacontakaiheptagon pentacontakaioctagon
  pentacontakaienneagon hexacontagon
  hexacontakaihenagon hexacontakaidigon
  hexacontakaitrigon hexacontakaitetragon
  hexacontakaipentagon hexacontakaihexagon
  hexacontakaiheptagon hexacontakaioctagon
  hexacontakaienneagon heptacontagon
  heptacontakaihenagon heptacontakaidigon
  heptacontakaitrigon heptacontakaitetragon
  heptacontakaipentagon heptacontakaihexagon
  heptacontakaiheptagon heptacontakaioctagon
  heptacontakaienneagon octacontagon
  octacontakaihenagon octacontakaidigon
  octacontakaitrigon octacontakaitetragon
  octacontakaipentagon octacontakaihexagon
  octacontakaiheptagon octacontakaioctagon
  octacontakaienneagon enneacontagon
  enneacontakaihenagon enneacontakaidigon
  enneacontakaitrigon enneacontakaitetragon
  enneacontakaipentagon enneacontakaihexagon
  enneacontakaiheptagon enneacontakaioctagon
  enneacontakaienneagon
  )

sides =  ->a{i,n=0,"#{a}";[/ontag|sa/,/(he|mo)n/,/di|do|ic/,/tri/,/tet|q/,/pe/,/hex/,/hep/,/oc/,/enn/,/^d/,/1d/,/2d/].each{|r|n.gsub!(r,i.to_s);i+=1;};n=n.gsub(/ide/,'!').gsub(/[a-z]/,'');n='1'+n[0] if /!/=~n;n.to_i}

polygons.each {|p| puts "#{p} -> #{sides.call(p)}"; }

```

# Answer
> 4 votes
## Python2 - ~~357~~ 368 byte

Since the only real exceptions to the system are "square", "hendecagon" and "dodecagon", all other numbers follow the same pattern of having "kai" for second digits and "conta"/"deca" for their first digit.

```
import sys;s=input();e=eval;x='y(str(10*i(b)+i(a)))';y=sys.exit;a=b='0';l=['0','hen','di','tri','tet','pen','hex','hep','oct','enn'];i=l.index
if'kai'in s:
 a=[f for f in l if f in s[-8:]][0]
if'ca'in s:
 if l[1]in s:y("11")
 if'do'in s:y("12")
 b=l[1];e(x)
elif'co'in s:
 l[2]='ico';b=[f for f in l if f in s[:5]][0];e(x)
if'sq'in s:y("4")
y(str(i(s[:3])))

```

Explanation:

```
import sys;s=input();e=eval;x='y(str(10*i(b)+i(a)))';y=sys.exit;a=b='0'
l=['0','hen','di','tri','tet','pen','hex','hep','oct','enn']
# List of all defining numerals, index equals the number.
i=l.index

if'kai'in s:                       # check if the input is a two-digit number
                                   # with a second digit greater than 0
 a=[f for f in l if f in s[-8:]][0] # get the second digit, and store it.

if'ca'in s:                        # Special case for 10-19
 if l[1]in s:y("11")               # Exceptions 11 & 12
 if'do'in s:y("12")                #
 b=l[1];e(x)
elif'co'in s:                      # All other two digit numbers
 l[2]='ico'
 b=[f for f in l if f in s[:5]][0] # Get the first digit, and store it
 e(x)
if'sq'in s:y("4")                  # Exception "square"
y(str(i(s[:3])))                   # All other single digit numbers

```

This works for all inputs between 3-99, and prints the result to the console.

Might be more golfable, but this is as far as I can go right now.

\**Edit: I just realized, this printed to STDERR, not STDOUT. Fixed code is a little longer:

```
import sys;s=input();e=eval;x="10*i(b)+i(a)";y=sys.exit;a=b='0';l=['0','hen','di','tri','tet','pen','hex','hep','oct','enn'];i=l.index
if'kai'in s:a=[f for f in l if f in s[-8:]][0]
if'ca'in s:
 if l[1]in s:print"11"
 if'do'in s:print"12"
 b=l[1];print e(x);y()
elif'co'in s:l[2]='ic';b=[f for f in l if f in s[:5]][0];print e(x);y()
if'q'in s:print"4"
print(i(s[:3]))

```

# Answer
> 2 votes
# Cinnamon Gum, 430 bytes

```
0000000: 6c4c ce85 0d04 4108 05d0 6e36 9e5b 379a  lL....A...n6.[7.
0000010: 5977 f7f2 6f02 8410 fdbc 11fe 75f4 f9d2  Yw..o.......u...
0000020: 4eb5 e5c1 b9df f951 5b3e 6cf5 72e5 edba  N......Q[>l.r...
0000030: 5801 74f5 8729 3469 238c 602d 29c5 502f  X.t..)4i#.`-).P/
0000040: 4b8d 3181 aa2e 3139 b6b9 bac8 e440 b5ca  K.1...19.....@..
0000050: e082 5977 8e79 2fe2 c155 5f47 ae89 f76b  ..Yw.y/..U_G...k
0000060: a21e 5ab8 8f26 eaa5 85fb 694a a02f d713  ..Z..&....iJ./..
0000070: b36b 63ee cdb1 294c e408 553d 822b 701d  .kc...)L..U=.+p.
0000080: 249e 0836 47f3 c5b0 3a5a a07e ff88 4245  $..6G...:Z.~..BE
0000090: 1b5f 8bc4 d692 2916 c2fa 6809 98fd 79b9  ._....)...h...y.
00000a0: f2ef 9e0d 32ff 9baa 8b43 3982 288a a121  ....2....C9.(..!
00000b0: 35d4 c3fc 03b3 3f4b cbd2 1d3a 43ad d77f  5.....?K...:C...
00000c0: 1ef2 9fe1 bc44 1ce7 b862 39e1 8ee7 a43a  .....D...b9....:
00000d0: a653 ceb8 4eab 633b e38c efec d7f7 0060  .S..N.c;.......`
00000e0: dc04 0be3 a143 8c57 1563 1c67 2123 3c48  .....C.W.c.g!#<H
00000f0: 19c9 6066 94bb 9cd1 0c86 c6b8 4b1a fbf5  ..`f........K...
0000100: f546 9a37 c1d2 7ce8 48f3 a54a 9ac7 59d2  .F.7..|.H..J..Y.
0000110: 0c0f 9266 7a40 9ae5 2e69 b607 a439 ee92  ...fz@...i...9..
0000120: e67e fe6a 81d6 cd59 ce7a c87f cc7a 8928  .~.j...Y.z...z.(
0000130: eb50 8dac a0db 5849 17b1 8a6c 6135 5dc0  .P....XI...la5].
0000140: 1ab2 7db5 5fff 4100 fb26 58d8 0f1d 62bf  ..}._.A..&X...b.
0000150: 5419 fb28 1bd9 a1c1 ca4e 0633 bbd4 edec  T..(.....N.3....
0000160: 6630 b447 ddd2 decf bf56 a073 7396 739e  f0.G.....V.ss.s.
0000170: bf0c 735e 22ca 3954 2327 e836 4ed2 459c  ..s^".9T#'.6N.E.
0000180: 225b 384d 1770 866c dfec d785 02e0 de04  "[8M.p.l........
0000190: 0bf7 a143 dc97 2ae3 1e65 2337 3458 b9c9  ...C..*..e#74X..
00001a0: 60e6 96ba 9ddb 0c86 eea8 5bba fb1f       `.........[...

```

This is a hexdump of the source code; you can reverse it using `xxd -r`.

Try it online.

---
Tags: code-golf, string, number, kolmogorov-complexity
---


title: Shortest code for key-logger

text:
# Question
Title: Shortest code for key-logger
Okay, I propose a shortest-key-logger challenge. As explained by the gentleman at "Are key-logger questions allowed?", strict rules have to be imposed in order to make this challenge valid for PPCG.

1. The key-logger has to run on Windows, Linux or Mac OSX (any programming language is welcome).
2. Upon execution, it has to show the message: "I'm gonna log you" (either in a console or using GUI).
3. The keys that are relevant for logging in this challenge are letters (case is not important) and numbers, all others such as symbols, control keys and whitespace are optional and can be ignored.
4. All relevant key presses that occur during runtime (even when the application is not in focus) have to be saved in a log file that can be read and verified using any text editor (even an esoteric one, as long as I can verify it using that text editor).

Anyone up for it? Whatdayatink?

# Answer
# Bash, 90 bytes

This works on Ubuntu, and requires `evtest`. It picks a device that is a keyboard, and saves `evtest`'s output to the file `l`. If you want a more formatted output, I can do that with more bytes.

```
echo I\'m gonna log you
sudo evtest /dev/input/by-path/`ls /dev/input/by-path/|grep kbd`>l

```
> 9 votes

---
Tags: code-golf
---


title: Clean the muddy quartata-fish

text:
# Question
Title: Clean the muddy quartata-fish
This challenge is in honor of the Rookie of the Year category winners of Best of PPCG 2015: muddyfish (for I'm not the language you're looking for!) and quartata (for Implement a Truth-Machine). Congratulations!

## Background

In the deepest trenches of the ocean, there lives a rare and elusive square-shaped fish called the *quartata-fish*. It looks like the glider from the Game of Life cellular automaton. Here are two quartata-fish of different sizes:

```
-o-
--o
ooo

--oo--
--oo--
----oo
----oo
oooooo
oooooo

```

You have managed to snap a photo of the quartata-fish, but the fish is rather hard to see since it's covered in mud. Now you'll have to write a program to clean up the photo.

## Input

Your input is a rectangular 2D grid of the characters `.-o#`, given as a newline-separated string. If you want, you can use pipes `|` instead of newlines as the separators, and you may assume one trailing and/or preceding separator.

The input will contain exactly one quartata-fish of some side-length `3*n`, where `n ≥ 1` is a positive integer, surrounded by periods `.` that represent the ocean floor. The fish will always be in the orientation depicted above. Overlaid on this grid, there will be exactly one non-empty rectangular region of hashes `#`, which represents a blob of mud. The blob may cover the quartata-fish partially or entirely. An example input would be

```
............
..--oo--....
..--oo--....
..---#####..
..---#####..
..ooo#####..
..oooooo....

```

## Output

Your output shall be generated from the input by replacing all the hashes with the characters `.-o`, so that the grid contains exactly one quartata-fish. There will always be a unique way to perform this replacement properly; in particular, the blob of mud will cover the fish entirely only if its size is 3×3. The output shall use the same separator as the input. For the above input, the correct output would be

```
............
..--oo--....
..--oo--....
..----oo....
..----oo....
..oooooo....
..oooooo....

```

## Rules and scoring

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. There are no time bounds: if your submission would eventually halt given unlimited time and resources, you're fine.

## Test cases

```
Input:
.......
...-o-.
...--o.
##.ooo.
##.....
Output:
.......
...-o-.
...--o.
...ooo.
.......

Input:
...-o-.
...-#o.
...ooo.
.......
Output:
...-o-.
...--o.
...ooo.
.......

Input:
.........
.###.....
.###.....
.ooo.....
Output:
.........
.-o-.....
.--o.....
.ooo.....

Input:
.....
.###.
.###.
.###.
Output:
.....
.-o-.
.--o.
.ooo.

Input:
......
......
......
...###
...###
...###
Output:
......
......
......
...-o-
...--o
...ooo

Input:
###o--....
###o--....
###-oo....
###-oo....
###ooo....
###ooo....
###.......
Output:
--oo--....
--oo--....
----oo....
----oo....
oooooo....
oooooo....
..........

Input:
............
..--oo--....
..--oo--....
..---#####..
..---#####..
..ooo#####..
..oooooo....
Output:
............
..--oo--....
..--oo--....
..----oo....
..----oo....
..oooooo....
..oooooo....

Input:
...--oo--....
.#########...
.#########...
.#########...
...oooooo....
...oooooo....
.............
.............
Output:
...--oo--....
...--oo--....
...----oo....
...----oo....
...oooooo....
...oooooo....
.............
.............

Input:
..............
..............
.########.....
.########.....
.########-....
.########-....
.########o....
.########o....
.########o....
.########o....
.########.....
..............
Output:
..............
..............
..............
..............
....--oo--....
....--oo--....
....----oo....
....----oo....
....oooooo....
....oooooo....
..............
..............

Input:
.................
.................
..---ooo---......
..--#########....
..--#########....
..--#########....
..--#########....
..--#########....
..oo#########....
..oo#########....
..oo#########....
....#########....
Output:
.................
.................
..---ooo---......
..---ooo---......
..---ooo---......
..------ooo......
..------ooo......
..------ooo......
..ooooooooo......
..ooooooooo......
..ooooooooo......
.................

Input:
.........................
.........................
....----oooo----.........
....----########.........
....----########.........
....----########.........
....----########.........
....----########.........
....----########.........
....----########.........
....oooo########.........
....oooo########.........
....oooooooooooo.........
....oooooooooooo.........
.........................
Output:
.........................
.........................
....----oooo----.........
....----oooo----.........
....----oooo----.........
....----oooo----.........
....--------oooo.........
....--------oooo.........
....--------oooo.........
....--------oooo.........
....oooooooooooo.........
....oooooooooooo.........
....oooooooooooo.........
....oooooooooooo.........
.........................

```

# Answer
> 9 votes
## Python 2, ~~433~~ 411 bytes

```
import re;i,o,l,j=input(),range,lambda s,r:s.replace(*r),"".join;i=l(l(l(i,".1"),"#."),"| ");s=o(len(i))
for x in s:
 for y in s:
    for q in s:
     r=map(list,l(l(i,"o."),"-.").split(" "))
     try:
        for v in o(q):r[x+v][y:y+q]=["".join(c*(q/3)for c in b)for b in["-o-","--o","ooo"]][3*v/q]
        m=re.match(i," ".join(j(i)for i in r))
     except:0
     if sum("-"in p for p in r)and m:print"|".join(l(j(i),"1.")for i in r);_

```

Exits with a `NameError`. Takes input pipe separated.

I'm mixing tabs and spaces here. SE doesn't render tabs properly.

```
'###o--....|###o--....|###-oo....|###-oo....|###ooo....|###ooo....|###.......'
 --oo--....|--oo--....|----oo....|----oo....|oooooo....|oooooo....|..........

'.....|.###.|.###.|.###.'
 .....|.-o-.|.--o.|.ooo.

'...-o-.|...-#o.|...ooo.|.......'
 ...-o-.|...--o.|...ooo.|.......

```

(Note extra spaces at the start are for prettiness only and aren't actually printed)

# Answer
> 4 votes
# JavaScript (ES6), 291 bytes

```
g=>eval('w=g.search`\n`;h=g.length/w|0;for(n=(w<h?w:h)/3|0;s=n*3;n--)for(x=w+1-s;x--;)for(y=h+1-s;y--;[...g].every((c,i)=>c==o[i]|c=="#")?z=p:0)for(p="",i=h;i--;)p=(l=[,"-o-","--o","ooo"][(i-y)/n+1|0],l?"."[t="repeat"](x)+l.replace(/./g,c=>c[t](n))+"."[t](w-x-s):"."[t](w))+(p?`\n`:"")+p;z')

```

## Explanation

Takes input grid as a newline separated string. Not completely golfed, will do more when I get time.

It works by:

* Getting every possible position and size of a fish in the bounds of the input grid.
* For each position/size, it builds a grid string with a fish in that position.
* Checks if this is the correct output by iterating over every character. If each character either matches or is a hash, it outputs the built string.

```
var solution =

g=>
  eval(`

    // Get size of input grid
    w=g.search\`\n\`;
    h=g.length/w|0;

    // Check every possible size (n) and position (x and y) of fish
    for(n=(w<h?w:h)/3|0;s=n*3;n--)
      for(x=w+1-s;x--;)
        for(y=h+1-s;y--;

          // Check if possible solution matches input grid
          [...g].every((c,i)=>c==p[i]|c=="#")?z=p:0
        )

          // Create possible solution grid
          for(p="",i=h;i--;)
            p=(
              l=[,"-o-","--o","ooo"][(i-y)/n+1|0],
              l?
                "."[t="repeat"](x)+
                l.replace(/./g,c=>c[t](n))+
                "."[t](w-x-s)
              :"."[t](w)
            )+(p?\`\n\`:"")+p;
    z
  `)
```

```
<textarea id="input" rows="6" cols="40">..............
..............
.########.....
.########.....
.########-....
.########-....
.########o....
.########o....
.########o....
.########o....
.########.....
..............</textarea><br />
<button onclick="result.textContent=solution(input.value)">Go</button>
<pre id="result"></pre>
```

# Answer
> 4 votes
## Python 2, 325 bytes

```
def f(s):
 s=map(list,s.split());R=range;L=len(s);M=len(s[0])
 for h in R(L/3*3,0,-3):
  for x in R(M-h+1):
   for y in R(L-h+1):
    if all(s[v%L][v/L]in".-#o #"[0<=v%L-y<h>v/L-x>=0::2]for v in R(L*M)):
     for k in R(h*h):s[y+k/h][x+k%h]="-o"[482>>k/h*3/h*3+k%h*3/h&1]
     return'\n'.join(map(''.join,s)).replace('#','.')

```

A badly golfed solution for now – the `for .. in range(...)`s are an utter train wreck. Inputs/outputs newline separated strings.

The byte count currently assumes space indents only – I'll switch to mixed tabs/spaces later when I'm done golfing, if necessary.

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


title: Find the treasure in a 2D dungeon

text:
# Question
Title: Find the treasure in a 2D dungeon
You are in a one-floor dungeon. There is a treasure which is protected by locked doors. Doors can be opened by finding the corresponding keys. Your goal is to find the shortest path to the treasure.

## Input

Input will be a two-dimensional grid representing the initial layout of the dungeon.

```
###########
#$   #   g#
#    # ####
###G##    #
#    ####C#
#c  @     #
###########

```

This is you: `@`
These are walls: `#`
This is the treasure: `$`
Locked doors are capital letters: `A`...`Z`
Each door has a corresponding lower-case key: `a`...`z`

* There will always be one `@` and one `$`.
* The dungeon will always be rectangular.
* It is not guaranteed that the outside edge of the dungeon is a wall. This is a valid dungeon:

```
  $
A##
@ a

```
* It is not guaranteed that the treasure is reachable. Some dungeons may not be solvable.
* There may be doors without a key, and there may be keys that do not open any doors.
* There will never be duplicate doors or keys.

## Output

Your program should print a sequence of `R`, `L`, `U`, `D` (or 4 other distinct symbols) to represent the *shortest* possible path to the treasure. Here, `RLUD` stands for right, left, up, and down, respectively. If there are multiple shortest paths, your program only needs to print one of them.

* You cannot move onto a wall.
* You cannot move outside of the dungeon boundaries.
* You cannot move onto a door without picking up it's key.
* Move onto a key to pick it up.
* It is not necessary to open every single door.

If it is not possible to reach the treasure through a valid sequence of moves, then your program must terminate without printing anything. (A trailing newline is allowed.)

## Scoring

This is so the answer with the lowest byte count wins.

## Test Cases

Each test case will have the height and width of the dungeon on the first line, and one possible path, with the optimal number of moves, on the last line.

```
1 2
@$
R (1)

3 3
  $
#Z#
@ z
RRLUUR (6)

3 5
c#d#$
 #C#D
@
UUDDRRUUDDRRUU (14)

7 16
c   # b #  ###@
###     #
  A #####  ####
d #           e
  B    ## #####
###    C   ##
       # a DE $
RDDDDDDL (8)

16 37
#####################################
#    #ijk #a M   ##m##   #    #  R  #
#    #    #  #           #       ####
###J#### ############# ###    #  P b#
#e                       N  h #  ####
##########  ###########  ######     #
#        #  #    $    #  #    #  ####
#  D     H  #         #  #       Q f#
# EcF    #  #####A#####  ######  ####
#  G     #  #####B#####  #          #
#        K  #####C#####  ############
#        #                          #
########### #         #### ##### ####
#     # p   #         # n    #      #
# d         #    @    #     o#   r  #
#################Z###################
UUULLLLLLDDLLLDLLLLLLRRRRRRRRRUUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLLLDDLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU (172)

```

It is not possible to reach the treasure in the following dungeons. For these test cases, there should be no output.

```
1 3
@#$

7 11
#a#j#$#i#f#
# #E#F#c#H#
# #K#D#A#G#
#         #
#C#J# #I#B#
#h#d# #L#g#
#l#e#@#b#k#

10 25
#########################
   # fgh  #  # c B b #  #
 $ #      #  #   #   #  #
   ###### #  ##H###E##  #
   #                    #
   #     #########  ##e##
   Z @   D     y #  #   #
   #     #########  F  C#
   #     G          # Ad#
#########################

```

The following snippet can be used to validate answers.

```
function run() {var dungeonText = document.getElementById("dungeon").value;var dungeonLines = dungeonText.split("\n");var height = dungeonLines.length;var width = dungeonLines[0].length;var dungeon = new Array(height);for (i = 0; i < dungeon.length; i++) {var dungeonLine = dungeonLines[i];if (dungeonLine.length != width) {return error("The dungeon is not rectangular");} dungeon[i] = dungeonLines[i].split("");} var movesText = document.getElementById("moves").value;var moves = movesText.trim().split("");var moveCount = moves.length;var rowAt, colAt;for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == '@') {rowAt = r;colAt = c;}}} var treasure = false;while (moves.length > 0) {var move = moves[0];var row = rowAt,col = colAt;switch (move) {case 'R':col++;break;case 'L':col--;break;case 'U':row--;break;case 'D':row++;break;default:return print(dungeon, moves, "Invalid move");} if (row < 0 || col < 0 || row >= height || col >= width) {return print(dungeon, moves, "Out of bounds");} var target = dungeon[row][col];if (target.match(/[A-Z#]/)) {return print(dungeon, moves, "Path blocked");} if (target.match(/[a-z]/)) {var door = target.toUpperCase();for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {if (dungeon[r][c] == door) {dungeon[r][c] = ' ';}}}} if (target == '$') {treasure = true;} dungeon[row][col] = '@';dungeon[rowAt][colAt] = '.';rowAt = row;colAt = col;moves.shift();} if (treasure) {print(dungeon, moves, "Got the treasure in " + moveCount + " moves!");} else {print(dungeon, moves, "Failed to reach treasure");}} function error(message) {var result = document.getElementById("result");result.innerHTML = message;} function print(dungeon, moves, message) {var output = message + "\n";for (r = 0; r < dungeon.length; r++) {for (c = 0; c < dungeon[r].length; c++) {output += dungeon[r][c];} output += "\n";} for (i = 0; i < moves.length; i++) {output += moves[i];} var result = document.getElementById("result");result.innerHTML = output;}
```

```
Dungeon:<br/><textarea id="dungeon" name="dungeon" rows="20" cols="40"></textarea><br/>Moves:<br/><textarea id="moves" name="moves" cols="40"></textarea><br/><button id="run" name="run" onclick="run();">Start</button><br/><br/>Result:<br/><textarea id="result" name="result" rows="20" cols="40" disabled></textarea><br/>
```

# Answer
> 5 votes
# Perl, ~~157~~ ~~152~~ 151 bytes

Includes +4 for `-p0` (cannot be counted as just an extension of `-e` because it uses `'` in several places)

Run with the maze on STDIN:

```
./keymaze.pl < maze.txt

```

`keymaze.pl`:

```
#!/usr/bin/perl -p0
1until$n{map/\n/&&"L1R-1U@+D-@+"=~s%\pL%$t=$1{$_}.$&;pos=$^H=-$'+s'@' '*"@-",s/\G[a-z\$ ]/\@/+s/$&/ /i?/\$/?$1{$_}:$\||=$t:0for"$_"%reg,$_,%1}++.$\}{

```

Replace `\n` and `^H` by their literal versions for the claimed score. Needs about 1 hour and a bit less than 2 Gigabytes on my machine to solve the big maze.

# Answer
> 4 votes
# Java 8 - ~~1282~~ ~~1277~~ ~~1268~~ ~~1259~~ 1257 bytes

This passes all the tests. However, for some of them it gives some slightly different results (when there is more than one optimal way, which isn't a problem).

For the 4th test, it gives this:

```
RDDDDDLD

```

Instead of this:

```
RDDDDDDL

```

For the 5th test, it gives this:

```
LLLLUUULLDDLLLLDLLLLLRRRRRRURRRUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLDDLLLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU

```

Instead of this:

```
UUULLLLLLDDLLLDLLLLLLRRRRRRRRRUUURRRRRRRRRRRRRRRDDLLRRUULLUUUUUUURRRRRUURRRDRRRLLLLULLLLLDDLLLLUULLLUDLLLLLULLLRRRRRDRRRRRRDDLLLLLLLLLLLLDDDLLLLLLLDURRRRRRRRDDDDRRRRRRUUUUU

```

# Golfed version:

```
import java.util.*;class G{int y,w,h,p;String C="",S,o,v;Map m=new HashMap();String q(int a){return a<1?"":"#"+q(a-1);}public static void main(String[]a)throws Exception{new G(new String(java.nio.file.Files.readAllBytes(new java.io.File(a[0]).toPath())));}G(String a){w=(a+"\n").indexOf(10)+3;String t=q(w)+a.replace("\n","##")+q(w);for(char j=65,k=97;j<91;j++,k++){if(t.indexOf(j)*t.indexOf(k)<0)t=t.replace(j,'#').replace(k,' ');}h=t.length()/--w;S=v=q(w*h);t=g(t);if(t!=v)System.out.print(t);}String g(String t){o=(String)m.get(t);if(o!=null)return o;if(t.indexOf(36)<0){if(S.length()>C.length())S=C;return"";}String d="";int f=t.indexOf(64),M[]=new int[w*h],N[]=new int[w*h];Queue<Integer>s=new ArrayDeque();s.add(f);while(!s.isEmpty()){y=s.poll();int[]P={y+1,y-1,y+w,y-w};for(int v:P){char j=t.replaceAll("[A-Z]","#").charAt(v);if(v!=f&j!=35&(N[v]<1|M[y]+1<M[v])){M[v]=M[y]+1;N[v]=y;s.add(v);if(j>32)d+=j;}}}o=d.chars().distinct().mapToObj(e->{String z="",c=C;for(y=t.indexOf(e);y!=f;y=N[y]){p=y-N[y];z=(p==w?"D":p==-w?"U":p==1?"R":"L")+z;}if(S.length()<=(C+z).length())return v;C+=z;String u=g(t.replace('@',' ').replace((char)e,'@').replace((char)(e-32),' '));C=c;return u==v?v:z+u;}).reduce(v,(a,b)->a.length()<b.length()?a:b);m.put(t,o);return o;}}

```

# Ungolfed version

Features:

* Informative variable names;
* Explicative and detailed comments;
* Proper identation.

```
import java.util.*;

/**
 * @author Victor Stafusa
 */
class TreasureHunt {

    // Note: on normal (non-golfing programming) those variables should have been scoped properly.
    // They are instance variables just for golfing purposes.
    // On the golfed version, nextCellIndex and waypointCellIndex are the same variable. The same also happens to cachedValue and result. This happens is for golfing purposes.

    int nextCellIndex,
            width,
            height,
            waypointCellIndex,
            cellIndexDifference;

    String previousPath = "",
            bestSolutionSoFar,
            cachedValue,
            result,
            failureFlag;

    // This should be Map<String, String>, but the generics were omitted for golfing.
    // It is needed to avoid recomputing long partial dungeons (i.e. dynamic programming).
    Map cachedResults = new HashMap();

    // Returns a lot of hashes. Like aLotOfHashes(7) will return "#######".
    String aLotOfHashes(int howMany) {
        return howMany < 1 ? "" : "#" + aLotOfHashes(howMany - 1);
    }

    // Here is where our program starts.
    public static void main(String[] args) throws Exception {
        // Read all the content of the file from args[0] and put it into a string.
        // Pass that string as a parameter to the constructor.
        // The instance itself is useless - it is just a golfing trick.
        new TreasureHunt(new String(java.nio.file.Files.readAllBytes(new java.io.File(args[0]).toPath())));
    }

    // Pre-processs the source in order to format it in the way that we want:
    // * No separators between rows. It uses the (row * width + column) formula, so no separators are needed.
    // * An extra layer of wall is added in all sides. This naturally fix up problems about walking out of the edges of the board, wrapping-around or acessing invalid array indexes.
    // This is a constructor just for golfing purposes. Its instances are worthless.
    TreasureHunt(String originalSource) {

        // Finds the width by searching the first line-feed.
        // If there is just one line and no line-feed, the [+ "\n"] will ensure that it will not break.
        // The [+ 3] is because we will add a layer of walls around, so it will be widen by one cell in the left and one in the right (which is +2).
        // We still get one more in the width that will be decremented later to use that in the aLotOfHashes method below.
        // 10 == '\n'.
        width = (originalSource + "\n").indexOf(10) + 3;

        // Add a layer of walls in the top and in the bottom (using a lot of hashes for that).
        // Replaces the line-feed by a pair of walls, representing the rightmost wall of a row and the leftmost row of the following row.
        // Since there is no line-feed before the first line nor after the last line, we add more two walls to fill those.
        String newSource = aLotOfHashes(width) + originalSource.replace("\n", "##") + aLotOfHashes(width);

        // Remove the keys without door (replaces them as blank spaces) and the doors without keys (replaces them with walls.
        // This way, the resulting dungeon will always have matching keys and doors.
        // 65 == 'A', 97 == 'a', 91 == 'z'+1
        for (char door = 65, key = 97; door < 91; door++, key++) {

            // Now a little math trick. For each key or door, we find an index. If the key or door exist, it will be a positive number. Otherwise it will be negative.
            // The result will never be zero, because the zeroey position is filled with part of the layer of wall that we added.
            // If only one of the key and the door exist, the multiplication will be the product of two numbers with opposite signals, i.e. a negative number.
            // Otherwise (both exists or both don't), then the product will be positive.
            // So, if the product is negative, we just remove the key and the door (only one of them will be removed of course, but we don't need to care about which one).
            if (newSource.indexOf(door) * newSource.indexOf(key) < 0) {
                newSource = newSource.replace(door, '#').replace(key, ' ');
            }
        }

        // Knowing the source length and the width (which we fix now), we can easily find out the height.
        height = newSource.length() / --width;

        // Creates a special value for signaling a non-existence of a path. Since they are sorted by length, this must be a sufficiently large string to always be unfavoured.
        bestSolutionSoFar = failureFlag = aLotOfHashes(width * height);

        // Now, do the hard work to solve the dungeon...
        // Note: On the golfed version, newSource and solution are the same variable.
        String solution = solvingRound(newSource);

        // If a solution is found, then show it. Otherwise, we just finish without printing anything.
        // Note: It is unsafe and a bad practice to compare strings in java using == or != instead of the equals method. However, this code manages the trickery.
        if (solution != failureFlag) System.out.print(solution);
    }

    // This does the hard work, finding a solution for a specific dungeon. This is recursive, so the solution of a dungeon involves the partial solution of the dungeon partially solved.
    String solvingRound(String dungeon) {
        // To avoid many redundant computations, check if this particular dungeon was already solved before. If it was, return its cached solution.
        cachedValue = (String) cachedResults.get(dungeon);
        if (cachedValue != null) return cachedValue;

        // If there is no treasure in the dungeon (36 == '$'), this should be because the adventurer reached it, so there is no further moves.
        if (dungeon.indexOf(36) < 0) {
            if (bestSolutionSoFar.length() > previousPath.length()) bestSolutionSoFar = previousPath;
            return "";
        }

        String keysOrTreasureFound = ""; // Initially, we didn't found anything useful.
        int adventurerSpot = dungeon.indexOf(64), // 64 == '@', find the cell index of the adventurer.
                cellDistance[] = new int[width * height],
                previousWaypoint[] = new int[width * height];

        // Use a queue to enqueue cell indexes in order to floodfill all the reachable area starting from the adventurer. Again, screw up the proper user of generics.
        Queue<Integer> floodFillQueue = new ArrayDeque();
        floodFillQueue.add(adventurerSpot); // Seed the queue with the adventurer himself.

        // Each cell thies to populate its neighbours to the queue. However no cell will enter the queue more than once if it is not featuring a better path than before.
        // This way, all the reachable cells will be reached eventually.
        while (!floodFillQueue.isEmpty()) {
            nextCellIndex = floodFillQueue.poll();

            // Locate the four neighbours of this cell.
            // We don't need to bother of checking for wrapping-around or walking into an invalid cell indexes because we added a layer of walls in the beggining,
            // and this layer of wall will ensure that there is always something in each direction from any reachable cell.
            int[] neighbourCells = {nextCellIndex + 1, nextCellIndex - 1, nextCellIndex + width, nextCellIndex - width};

            // For each neighbouring cell...
            for (int neighbourCellIndex : neighbourCells) {
                // Find the cell content. Considers doors as walls.
                char neighbourCellContent = dungeon.replaceAll("[A-Z]", "#").charAt(neighbourCellIndex);

                if (neighbourCellIndex != adventurerSpot // If we are not going back to the start ...
                        & neighbourCellContent != 35 // ... nor walking into a wall or a door that can't be opened (35 == '#') ...
                        & (previousWaypoint[neighbourCellIndex] < 1 // ... and the neighbour cell is either unvisited ...
                            | cellDistance[nextCellIndex] + 1 < cellDistance[neighbourCellIndex])) //  ... or it was visited before but now we found a better path ...
                { // ... then:
                    cellDistance[neighbourCellIndex] = cellDistance[nextCellIndex] + 1; // Update the cell distance.
                    previousWaypoint[neighbourCellIndex] = nextCellIndex; // Update the waypoint so we can track the way from this cell back to the adventurer.
                    floodFillQueue.add(neighbourCellIndex); // Enqueue the cell once again.
                    if (neighbourCellContent > 32) keysOrTreasureFound += neighbourCellContent; // If we found something in this cell (32 == space), take a note about that.
                }
            }
        }

        // Brute force solutions chosing each one of the interesting things that we found and recursively solving the problem as going to that interesting thing.
        // Warning: This has an exponential complexity. Also, if we found something interesting by more than one path, it will compute that redundantly.
        result = keysOrTreasureFound.chars().distinct().mapToObj(keyOrTreasure -> {
            String tracingWay = "", savedPreviousPath = previousPath;

            // From our keyOrTreasure, trace back the path until the adventurer is reached, adding (in reverse order) the steps needed to reach it.
            for (waypointCellIndex = dungeon.indexOf(keyOrTreasure); waypointCellIndex != adventurerSpot; waypointCellIndex = previousWaypoint[waypointCellIndex]) {

                // Use the difference in cell indexes to see if it is going up, down, right or left.
                cellIndexDifference = waypointCellIndex - previousWaypoint[waypointCellIndex];
                tracingWay = (cellIndexDifference == width ? "D" : cellIndexDifference == -width ? "U" : cellIndexDifference == 1 ? "R" : "L") + tracingWay;
            }

            // If this path is going to surely be longer than some other path already found before, prune the search and fail this path.
            if (bestSolutionSoFar.length() <= (previousPath + tracingWay).length()) return failureFlag;

            // Prepare for recursion, recording the current path as part of the next level recursion's previous path.
            previousPath += tracingWay;

            // Now that we traced our way from the adventurer to something interesting, we need to continue our jorney through the remaining items.
            // For that, create a copy of the dungeon, delete the door of the key that we found (if it was a key),
            // move the adventurer to the thing that we just found and recursively solve the resulting simpler problem.
            String nextRoundPartialSolution = solvingRound(dungeon
                        .replace('@', ' ') // Remove the adventurer from where he was...
                        .replace((char) keyOrTreasure, '@') // ... and put him in the spot of the key or treasure.
                        .replace((char) (keyOrTreasure - 32), ' ')); // ... and if it was a key, delete the corresponding door ([- 32] converts lowercase to uppercase, won't do anything in the case of the treasure).

            // Recursion finished. Now, get back the previous path of the previous recursion level.
            previousPath = savedPreviousPath;

            // If the subproblem resulted in a failure, then it is unsolvable. Otherwise, concatenates the subproblem solution to the steps that we took.
            return nextRoundPartialSolution == failureFlag ? failureFlag : tracingWay + nextRoundPartialSolution;

        // From all the paths we took, choose the shorter one.
        }).reduce(failureFlag, (a, b) -> a.length() < b.length() ? a : b);

        // Now that we have the result of this recursion level and solved this particular dungeon instance,
        // cache it to avoid recomputing it all again if the same instance of the dungeon is produced again.
        cachedResults.put(dungeon, result);
        return result;
    }
}

```

# Taking input

To run it, try this:

```
javac G.java
java G ./path/to/file/with/dungeon.txt

```

Or if you are running the ungolfed version, replace the `G`'s with `TreasureHunt`.

The file should contain the dungeon. The input should **not** end with a line-feed. Further, it only accepts line-ends in the `\n` format. It won't work with `\r\n` or with `\r`.

Also, it does not validates or sanitizes the input. If the input is malformed, then the behaviour is undefined (likely to throw an exception). If the file can't be found, then an exception will be thrown.

# Remarks

My first implementation somewhere near 1100 bytes could not solve the 5th test case in reasonable time. The reason for that is because my implementation it brute-forces all the possible permutations of collectible items (i.e. the keys and the treasure) that are acessible (i.e. not locked in an inacessible room).

In the worst case, with all the 26 keys and the treasure, this would be 27! = 10,888,869,450,418,352,160,768,000,000 different permutations.

The OP did not specified that the answer should be something that runned in reasonable time. However, I consider that this is a loophole that I would not like to exploit. So, I decided to make it run in acceptable time for all the test cases. In order to achieve that, my revised program features pruning in search paths that are proved to be worse than some already know solution. Further, it also caches subsolutions (i.e. dynamic programming) to avoid recomputing many identical dungeons that might arise. With that, it is able to solve the 5th test case in just over one minute in my computer.

The solution is recursive. The idea is first to get the adventurer to some item (a key or the treasure). In case of a key, after the adventurer reaches it, a new similar dungeon is generated with both the key and the door deleted and the adventurer moved to where the key was. With that, the generated simpler dungeon is solved recursively until the point when the treasure is reached or the algorithm concludes that there isn't any reachable item. The order of the items to be visited is brute-forced with pruning and caching as explained above.

The path-finding between the adventurer and the items is made with an algorithm that resembles both floodfill and Dijkstra.

Finally, I suspect that this problem is NP-complete (well, the generalized version of it without a limitation on the number of doors/keys). If this is true, don't expect solutions that optimally solve very large dungeons with miryads of doors and keys in reasonable time. If sub-optimal paths were allowed, then it would be easily tractable with some heuristics (just go to the treasure if possible, otherwise go to the nearest key).

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


title: Number of pieces on a checkers board

text:
# Question
Title: Number of pieces on a checkers board
### Introduction

A normal checkers board contains 8 x 8 = 64 squares:

You can see that in total, there are **12 white pieces**. Black and white always have the same amount of pieces. If there are any more pieces on the board, the pieces would neighbouring, which is not allowed for this challenge. To clarify things, here are some examples:

The smallest board possible for this challenge is **3 x 3**:

You can see that the maximum amount of pieces is equal to **2**. So, when given **N = 3**, you need to output **2**. If the input is **N = 4**, we get the following:

You can see that the maximum amount is also 2. So for **N = 4**, the output should be **2**. For **N = 5**, the output should be equal to **5**:

### Examples

```
STDIN:  3
STDOUT: 2

STDIN:  4
STDOUT: 2

STDIN:  5
STDOUT: 5

STDIN:  6
STDOUT: 6

STDIN:  8
STDOUT: 12

```

### Rules

* Your submission must be a program, or function etc. that takes one integer and outputs or returns the number of pieces on the board
* You can safely assume that the input is an non-negative integer \> 2
* This is , so the program with the least amount of bytes wins!
* *Note that the square in the lower left of the board is always dark. Pieces are only placed on dark squares*
* You have to occupy a full row with pieces

# Answer
# Par, 8 bytes

```
✶″½↓┐*½┐

```

One byte is used per character.

## Explanation

```
               ## [implicit: read line]      Example
✶              ## Convert to number           7
″              ## Duplicate                   7 7
½              ## Divide by two               7 3.5    half the board
↓              ## Minus one                   7 2.5    leave one row empty
┐              ## Ceiling                     7 3      a whole number of rows
*              ## Multiply                    21       total number of spaces
½              ## Divide by two               10.5     only the blue squares
┐              ## Ceiling                     11       starts with blue, so round up

```
> 5 votes

# Answer
## Hexagony, 19 bytes

```
?({{&2'2':{):!/)'*/

```

Try it online.

### Explanation

This is still the same computation as I've used in my CJam and Labyrinth answers, but due to Hexagony's... special... memory model, it's a bit trickier to squeeze the computation into 19 bytes (so that it fits inside a side-length 3 hexagon).

Like my Labyrinth answer, this terminates with a division-by-0 error.

Here is the unfolded code:

As I said the code is entirely linear. You can piece the executed path together in order grey-purple-green-red-blue. The path actually continues a bit further until it hits the `:` on the left. Removing the `/` (which only redirect control flow), the entire program unrolled linearly is:

```
?({2':{)'*){&2':!:&?':

```

So the question is how does it work. Hexagony's memory is the line graph of a hex grid, where each edge of the grid contains an integer value (initially zero). The memory pointer (MP) is always on one edge and points in a certain direction along that edge. Arithmetic operations are generally applied to the two edges pointed *at* and stored in the edge the MP is on.

For this program, we'll be using the three edges labelled **A**, **B**, **C**, with the MP starting as shown here:

So here is how this works:

```
?  Read an integer N from STDIN into edge A.
(  Decrement to get N-1.
{  Move the MP forwards onto edge B.
2  Set the edge to 2.
'  Move the MP backwards onto edge C.
:  Divide edge A by edge B (rounding down) to compute (N-1)/2.
{  Move the MP forwards onto edge A.
)  Increment to restore value of N.
'  Move the MP backwards onto edge B.
*  Multiply edges A and C to compute N*(N-1)/2.
)  Increment to compute N*(N-1)/2 + 1.
{  Move the MP forwards onto edge C.
&  This actually a copy operation, but we use it to reset the edge to zero.
2  Set the edge to 2.
'  Move the MP backwards onto edge A.
:  Divide edge B by edge C to compute (N*(N-1)/2 + 1)/2.
!  Output the result as an integer. We're basically done now.
:  no-op (we already have this value)
&  Copy either B or C into A (doesn't matter).
?  Read a zero (EOF) into A.
'  Move the MP backwards onto an unused cell.
:  Divide some unused cell by A (which is zero), terminating with an error.

```
> 13 votes

# Answer
# LabVIEW, ~~28~~ 20 LabVIEW Primitives
> 11 votes

# Answer
## CJam, 10 bytes

```
ri_(2/*)2/

```

Test it here.

### Explanation

```
ri   e# Read input and convert to integer N.
_    e# Duplicate N.
(2/  e# Decrement, integer divide by two, to determine the number of rows that can be used.
*    e# Multiply by the input to determine the number of cells that can be used.
)2/  e# Increment, integer divide by two, which essentially ceil()s the result of the
     e# division.

```
> 8 votes

# Answer
## Labyrinth, 11 bytes

Woohoo, only one byte behind CJam.

```
?:(#/*)_2/!

```

Try it online.

It's essentially the same thing:

```
? reads an integer value.
: duplicates the result.
( decrements it.
# pushes the stack depth which happens to be 2.
/ is integer division.
* is multiplication.
) increments the result.
_ pushes a 0.
2 turns it into a 2.
/ is once again integer division.
! prints the result as an integer.

```

However, at this point the program doesn't terminate yet. Instead, the instruction pointer has hit a dead end and turns around. But now `/` tries to compute `0/0` which terminates with an error.
> 8 votes

# Answer
## Seriously, 8 bytes

```
,;D½L*½K

```

Seriously has the handy `½` (float divide by 2), and `K` (ceiling), so we don't need to add one before division.

Try it here with explanation.
> 5 votes

# Answer
# Python 2, 22 21 bytes

```
lambda n:~-n/2*n+1>>1

```

I first separate in two cases, odd N and even N.

With odd N we can fill (N - 1)/2 rows, containing on average N/2 pieces. Since the first row always has more pieces we should ceil this result. So when N is odd we have ceil((N-1)/2 * N/2) pieces.

With even N we can fill N/2 - 1, or floor((N - 1)/2) rows, each row containing N/2 pieces.

We can combine these two expressions by ceil(floor((N-1)/2) * N/2). Since ceil(x/2) = floor((x+1)/2) we can use flooring division: `((N - 1) // 2 * N + 1) // 2`.
> 5 votes

# Answer
# JavaScript, ~~37~~ 35 bytes

```
alert(((n=prompt()/2)-.5|0)*n+.5|0)

```

## Explanation

Uses a similar technique to the rest of the answers. This is the ungolfed algorithm:

```
var n = parseInt(prompt());
var result = Math.ceil(Math.floor((n - 1) / 2) * n / 2);
alert(result);

```
> 3 votes

# Answer
# dc, 12

```
?d1-2/*1+2/p

```

### Test output:

```
$ for t in 3 4 5 6 8; do echo $t | dc -e?d1-2/*1+2/p; done
2
2
5
6
12
$

```
> 3 votes

# Answer
# Pyth, 9 bytes

```
/h*/tQ2Q2

```

Same algorithm as my Python 2 answer.
> 3 votes

# Answer
# Java, ~~230~~ ~~155~~ 52

Golfed:

```
int f(int s){return(int)Math.ceil(s*((s-1)/2)/2.0);}

```

Ungolfed:

```
public class NumberOfPiecesOnACheckersBoard {

  public static void main(String[] args) {
    // @formatter:off
    int[][] testData = new int[][] {
      {3, 2},
      {4, 2},
      {5, 5},
      {6, 6},
      {8, 12}
    };
    // @formatter:on

    for (int[] data : testData) {
      System.out.println("Input: " + data[0]);
      System.out.println("Expected: " + data[1]);
      System.out.print("Actual:   ");
      System.out.println(new NumberOfPiecesOnACheckersBoard().f(data[0]));
      System.out.println();
    }
  }

  // Begin golf
  int f(int s) {
    return (int) Math.ceil(s * ((s - 1) / 2) / 2.0);
  }
  // End golf

}

```

Program output:

```
Input: 3
Expected: 2
Actual:   2

Input: 4
Expected: 2
Actual:   2

Input: 5
Expected: 5
Actual:   5

Input: 6
Expected: 6
Actual:   6

Input: 8
Expected: 12
Actual:   12

```
> 3 votes

# Answer
# Japt, ~~16~~ 14 bytes

```
U-1>>1 *U+1>>1

```

Try it online!

### How it works

Pretty simple:

```
         // Implicit: U = input number
U-1>>1   // Subtract 1 from U and integer divide by 2.
*U+1>>1  // Multiply the result by U, add 1, and integer divide by 2.
         // Implicit: output last expression

```

I wish there were some way to take into account that the two halves of the code are so similar. Suggestions welcome!

Old version (16 bytes):

```
U*½-½|0 *U*½+½|0

```
> 3 votes

# Answer
# MATLAB, ~~37~~ 25 bytes

```
@(a)ceil(fix(a/2-.5)*a/2)

```

I believe this should work, does for all test cases.

It also works on **Octave**. You can try online here.

---

For the old code I added the program to that workspace in a file named `checkerboard.m`. You can run it by simply entering `checkerboard` at the prompt, then when it starts, enter the required size at the prompt. The result will be printed.

For the new code, simply enter the code posted here into the prompt, then call the anonymous function as `ans(n)`.
> 2 votes

# Answer
## Pyth, 17 14 13 bytes

-3 bytes thanks to Ypnypn! Rearranged the numbers of the * operator to save 1 byte.

```
/+*Q-/Q2-1%Q2 1 2 (original)
/h*Q-/Q2!%Q2 2
/h*-/Q2!%Q2Q2

```

Explanation:

When n is even, we can occupy n/2-1 rows with n/2 pieces, making a total of n\*(n/2-1)/2 pieces. This expression is equivalent to (n\*(n/2-1)+1)/2

When n is odd, we can find how twice the number of pieces would look like, twice the number of pieces will span n-1 rows, and if I take away one piece, we can divide the n-1 rows into (n-1)/2 groups of 2 rows such that each group has n pieces, so the expression for this case is (n\*(n/2)+1)/2

Now that both expressions are quite similar, we can write the code.

```
/h*-/Q2!%Q2Q2
        %Q2   Check if the number is odd
       !      Logical not to make 1 if even and 0 if odd
    /Q2       n/2
   -          n/2-1 if even, and n/2 if odd
  *        Q  n*(n/2-1) if even, n*(n/2) if odd
 h            Add one
/           2 Divide the result by two.

```

My first time using a golfing language.
> 2 votes

# Answer
## Zilog ez80 machine code, 9 bytes

In hex:

```
6C 2D CB3D ED6C 2C CB3D

```

In assembly:

```
ld l,h
dec l
srl l
mlt hl
inc l
srl l

```

Input is in register `h`, and output is in `l`.

The Zilog ez80 is an 8-bit processor with an 8 bit accumulator and 24-bit registers. Unlike the z80, it has a `mlt` (8-bit multiply) instruction, which, in 16-bit mode, multiplies the high and low bytes of a register pair, here `hl`, and stores back in `hl`.

This only works for values for which twice the result fits in 8 bits; that is, n≤23.
> 2 votes

# Answer
## TI-BASIC, 13 bytes

```
⁻int(⁻.5Ansint(Ans/2-.5

```

TI-BASIC's implicit multiplication helps, but it doesn't have integer division. `⁻int(⁻X` is a shorter form of ceil(x).
> 2 votes

# Answer
# vba, 46

```
Function f(x)
f=(((x-1)\2)*x+1)\2
End Function

```

Call with ?f(x), or =f(A1) in a formula
> 2 votes

# Answer
## Javascript, 33 bytes

```
a=prompt();alert(a*(a-1>>1)+1>>1)

```

If an ES6 function is allowed then 18 bytes:

```
a=>a*(a-1>>1)+1>>1

```
> 2 votes

# Answer
## Retina, 18 bytes

```
11(..?$)?
$_
11?
1

```

Input and output is in unary.

Try it online!

The latest version of Retina (newer than this challenge) could handle decimal I/O for four additional bytes:

```
.+
$*
11(..?$)?
$_
11?

```

Try it online!

With unary input and decimal output, we can do 16 bytes, but that seems like a bit of a stretch:

```
11(..?$)?
$_
11?

```

### Explanation

Still the same approach as anyone elses, but using regex replacement on a unary representation of the number.

```
11(..?$)?
$_

```

This computes `n*((n-1)/2)`. We do this by matching two characters at a time (division by two) and replacing them with the entire string (multiplication by `n`). The decrement of `n` is done by skipping the remainder of the string, if only one or two characters are left.

```
11?
1

```

This is integer division by 2, rounded up. We simply replace two characters with one (division by 2), but allow the last match to consist of only one character (rounding up).
> 2 votes

# Answer
# Prolog, ~~39~~ 38 bytes

**Code:**

```
p(N):-X is ((N-1)//2*N+1)//2,write(X).

```

**Explanation:**

```
Subtract 1 from input and integer divide by 2 to get number of rows available.
Multiply that number by input to get number of squares available.
Add one and integer divide by 2 to round up, since at at least half the rows
will have a checker at the first square.
Print.

```

**Example:**

```
p(8).
12

```

Try it online here

**Edit:** Saved 1 byte by replacing ceil/2 with +1//2
> 1 votes

# Answer
# Python 3, 39 bytes

This is a little bloated, but I'm not sure I could golf much further than this. A link for testing.

```
n=int(input());print(((n-1)//2*n+1)//2)

```
> 1 votes

# Answer
# Mumps, 17 bytes

```
R I W I-1\2*I+1\2

```

Thanks to Emigna for the simple algorithm explanation. This exploits Mumps' mathematics "deficiency" that operations are executed strictly left-to-right (not PEMDAS) so parenthesis are not required. :-)

Output does look a tad odd, however, as Cache's Ensemble (the Mumps environment that I have access to) does not automatically output carriage returns even when pressed on input. If you want it prettier, add 4 characters for pre/post carriage returns:

```
R I W !,I-1\2*I+1\2,!

```

Thanks!
> 1 votes

# Answer
## Bash, 32 bytes

```
read a;echo $((a*(a-1>>1)+1>>1))

```
> 1 votes

# Answer
## Batch, 30 bytes

```
@cmd/cset/a(%1*((%1-1)/2)+1)/2

```

38 bytes if input on stdin is required:

```
@set/pa=
@cmd/cset/a(a*((a-1)/2)+1)/2

```
> 1 votes

# Answer
## Pyke, 8 bytes, noncompeting

```
Dt2f*h2f

```

dup,dec,half,mult,inc,half

Try it here!
> 1 votes

---
Tags: code-golf, game, grid, board-game
---