title: Smallest Narcissistic Number

text:
# Question
Title: Smallest Narcissistic Number
Given a natural numbers `n>1`, find the smallest narcissistic number of `n` digit.

A narcissistic number is a number which is the sum of its own digits, each raised to the power of the number of digits.

For example, for `n=3` (3 digits) the out put should be `153`:

`1^3 + 5^3 + 3^3 = 1 + 125 + 27 = 153`

For `n=4` (4 digits) the out put should be `1634`:

`1^4 + 6^4 + 3^4 + 4^4 = 1 + 1296 + 81 + 256 = 1634`

For `n=5` (5 digits) the out put should be `54748`:

`5^5 + 4^5 + 7^5 + 4^5 + 8^5 = 54748`

If there is no such numbers, like for example `n = 2` or `n = 22` output any special output (a negative number, an exception, an error, empty,...).

**Winning Criteria**

This is , so shortest answer in bytes by language wins.

**OEIS A005188**

# Answer
> 2 votes
# 05AB1E, ~~16~~ 15 bytes

Very inefficient.
Empty output if there is no solution.

```
°LʒDSImOQ}ʒgQ}н

```

Try it online!

# Answer
> 1 votes
# JavaScript (ES7), ~~82~~ 79 bytes

*Saved 3 bytes thanks to @ThePirateBay*

Returns `undefined` when there's no solution. Reasonably fast up to `n = 7` and really slow beyond that.

```
n=>[...Array(10**n).keys()].find(x=>x==eval([...x+='0'].join(`**${n}+`))&&x[n])

```

### Demo

```
let f =

n=>[...Array(10**n).keys()].find(x=>x==eval([...x+='0'].join(`**${n}+`))&&x[n])

for(n = 2; n < 6; n++) {
  console.log(n, f(n))
}
```

---

# Recursive version, 72 bytes

Returns `"0"` (as a string) when there's no solution. For `n > 4`, it would require to either enable Tail-Call-Optimization (not tested) or extend the maximum size of the call stack.

```
f=(n,x=1)=>eval([...s=x+'0'].join(`**${n}+`))-x|!s[n]?s[n+1]||f(n,x+1):x

```

```
f=(n,x=1)=>eval([...s=x+'0'].join(`**${n}+`))-x|!s[n]?s[n+1]||f(n,x+1):x

for(n = 2; n < 5; n++) {
  console.log(n, f(n))
}
```

# Answer
> 1 votes
# Pyth, 20 bytes

```
hfqTsm^dQjT10r^TtQ^T

```

Try it online!

How it works...

```
hfqTsm^dQjT10r^TtQ^T    Implicit: Q=input()

                  ^T    10^Q (final Q is inferred)
              ^TtQ      10^(Q-1)
             r          Range over the above
                           (generates list of numbers of length Q)
 f                      Filter each element in the above (as T) over...
         jT10              Get digits in T
     m                     Map each digit in the above (as d) over...
      ^dQ                     d^Q
    s                      Sum these
  qT                       Is the above equal to the original number?
h                       Take the first element of this filtered list

```

Throws an error if no solutions exist.

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


title: HE COMETH NOT - a zalgo challenge

text:
# Question
Title: HE COMETH NOT - a zalgo challenge
Write a program or function that, given a string, will strip it of zalgo, if any exists.

## Zalgo

For this post, zalgo is defined as any character from the following Unicode ranges:

* Combining Diacritical Marks (0300–036F)
* Combining Diacritical Marks Extended (1AB0–1AFF)
* Combining Diacritical Marks Supplement (1DC0–1DFF)
* Combining Diacritical Marks for Symbols (20D0–20FF)
* Combining Half Marks (FE20–FE2F)

https://en.wikipedia.org/wiki/Combining\_character#Unicode\_ranges

## Input

* May be passed via command line arguments, STDIN, or any other standard method of input supported by your language
* Will be a string that may or may not contain zalgo or other non-ASCII characters

## Output

Output should be a string that does not contain any zalgo.

## Test Cases

```
Input -> Output

HE̸͚ͦ ̓C͉Õ̗͕M͙͌͆E̋̃ͥT̠͕͌H̤̯͛ -> HE COMETH
C͉̊od̓e͔͝ ̆G̀̑ͧo͜l͔̯͊f͉͍ -> Code Golf
aaaͧͩa͕̰ȃ̘͕aa̚͢͝aa͗̿͢ -> aaaaaaaaa
ññ        -> ñn
⚡⃤       -> ⚡

```

## Scoring

As this is , shortest answer in bytes wins.

# Answer
## Retina, 35 bytes

```
T`̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯

```

Try it online!

Simply removes all characters in the ranges given in the challenge from the input. The code is super unreadable of course, but the code is conceptually no different from something like `T`0-9A-Za-z` which would delete all alphanumeric characters.
> 13 votes

# Answer
# Python 3, ~~73~~ 69 bytes

*-4 bytes thanks to L3viathan.*

Not sure if participating in your own challenge is ok or not but... Stole the regex ~~and essentially the idea as well \>\<~~ straight from the JS and Retina answers.

```
lambda s:re.sub('[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯]','',s)
import re

```

Try it online!
> 7 votes

# Answer
## JavaScript (ES6), 55 bytes

```
f=
s=>s.replace(/[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯]/g,'')
```

```
<textarea oninput=o.textContent=f(this.value)></textarea><pre id=o>
```
> 4 votes

# Answer
# PHP, 67 Bytes

shorter as the write out

```
<?=preg_replace("#[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯]#u","",$argn);

```

Try it online!

# PHP, 115 Bytes

```
<?=preg_replace("#[\u{300}-\u{36f}\u{1ab0}-\u{1aff}\u{1dc0}-\u{1dff}\u{20d0}-\u{20ff}\u{fe20}-\u{fe2f}]#u","",$argn);

```

Try it online!

# PHP, 35 Bytes

Valid for the given Testcases it removes all Marks

```
<?=preg_replace("#\pM#u","",$argn);

```

Try it online!
> 4 votes

# Answer
# Japt, 37 bytes

```
r"[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯]

```

Try it online!
> 4 votes

# Answer
# Python 3, ~~127~~ 118 bytes

Just a straightforward answer for now, let's see how golfable it is.

```
lambda y:"".join(chr(x)for x in map(ord,y)if not(767<x<880or 6831<x<6912or 7615<x<7680or 8399<x<8448or 65055<x<65072))

```

Changelog:

* When will I ever learn that comprehensions are shorter than functional stuff (-9 bytes).
> 3 votes

# Answer
# Bash + coreutils, 41

```
tr -d '̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯'

```

Simply strips out characters in the given ranges.

Try it online.
> 3 votes

# Answer
# APL (Dyalog Unicode), 43 bytes

```
'[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯]'⎕R''

```

Try it online!

PCRE **R**eplace all those with nothing

---

44 byte version not using RegEx or strange character literals (and thus single byte per character):

```
⍞~⎕UCS∊65055 8399 7615 6831 767+⍳¨16×2 6~⍨⍳7

```

Try it online! `⍳7` 1…7 (1 2 3 4 5 6 7)

`2 6~⍨` except 2 and 6 (1 3 4 5 7)

`16×` multiply by 16 (16 48 64 80 112)

`⍳¨` 1… each (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16, 1 2 3…, …110 111 112)

`+` add offset to each list (65056 65057 65058…, …877 878 879)

enlist (flatten)

`⎕UCS` convert to corresponding Unicode character

`⍞~` get text input and remove all such characters
> 2 votes

# Answer
# Jelly, 32 bytes

```
“Żȷ'⁺¦60ƭṖ_WTɦ7Ụ|ṫYɠF’bȷ5r2/FỌḟ@

```

Try it online!

# Explanation

```
“Żȷ'⁺¦60ƭṖ_WTɦ7Ụ|ṫYɠF’bȷ5r2/FỌḟ@  Main link
“Żȷ'⁺¦60ƭṖ_WTɦ7Ụ|ṫYɠF’            Base 250 compressed integer; 768008790683206911076160767908400084476505665071
                      bȷ5         Convert into base 100000; [768, 879, 6832, 6911, 7616, 7679, 8400, 8447, 65056, 65071]
                         r2/      Inclusive range on non-overlapping slices of length 2
                            F     Flatten
                             Ọ    chr; cast to character from codepoints
                              ḟ@  Filter; remove all characters from input that are in the characters generated before

```
> 2 votes

# Answer
# Java 8, 57 bytes

```
s->s.replaceAll("[̀-ͯ᪰-᫿᷀-᷿⃐-⃿︠-︯]","")

```

Try it here.
> 1 votes

# Answer
# 05AB1E, 32 bytes

```
•3xIαEλ¤’ä₆Ćkмм`0Â9"´•žHв2ôvyŸçK

```

Try it online!
> 1 votes

---
Tags: code-golf, string, unicode
---


title: Draw my Contours

text:
# Question
Title: Draw my Contours
Given a rectangular matrix of elevations, draw its contours.

# Task

Two elements `x` and `y` are on the same contour level if `floor(x/10) == floor(y/10)`. For example, `52` and `58` are on the same contour level, but `58` and `64` are not.

The act of drawing contours is defined as follows: For every element `e`, replace it with a two-char string chosen as follows:

* the first character is `" "` if the element below `e` is on the same contour level as `e` or if there is no element to the below `e` and `"_"` otherwise
* the second character is `" "` if the element to the right of `e` is on the same contour level as `e` or there is no element to the right of `e` and `"|"` otherwise

The elements within rows are joined together, then the rows are joined together with newlines.

# Example

Let's say the input is `[[5,20],[3,6]]`, visualized as

```
5 20
3 6

```

We first look at `5`. Since `3` is on the same contour level as `5`, the first character is `" "`. Since `20` is not on the same contour level as `5`, the second character is `"|"`.

Now we look at `20`. Since `6` is not on the same contour level as `20`, the first character is `"_"`. Since there is no element to the right of `20`, the second character is `" "`.

Now we look at `3`. Since there is no element below `3`, the first character is `" "`. Since `6` is on the same contour level as `3`, the second character is `" "`.

Now we look at `6`. Since there is no element below `6`, the first character is `" "`. Since there is no element to the right of `6`, the second character is `" "`.

Based on these two-char strings, we make replacements to get `[[" |","_ "],[" "," "]]`. Joining these together, we get an output of

```
 |_

```

# Rules

* The input matrix will always be rectangular and composed of positive integers.
* Trailing spaces or newlines may be in any amount (including 0) and do not have to be consistent in any way.
* You do not have to follow the same algorithm as long as you produce the same results.
* Your program or function may output a newline-separated string, list of strings, or equivalent.
* This is , so shortest code in bytes wins.

# Test Cases

```
input
output

[[1,5,8,9],[3,11,13,8],[7,14,10,9],[4,8,7,6]]
  _ _
 |   |
 |_ _|

[[0,10,20,30,40,50,60,70,80,90],[0,0,10,10,20,20,30,30,40,40],[0,0,0,10,10,10,20,20,20,30],[0,0,0,0,10,10,10,10,20,20],[0,0,0,0,0,10,10,10,10,10],[0,0,0,0,0,0,10,10,10,10],[0,0,0,0,0,0,0,10,10,10],[0,0,0,0,0,0,0,0,10,10],[0,0,0,0,0,0,0,0,0,10],[0,0,0,0,0,0,0,0,0,0]]
 |_|_|_|_|_|_|_|_|_
   |_  |_ _|_ _|_ _
     |_    |_ _  |_
       |_      |_ _
         |_
           |_
             |_
               |_
                 |_

[[5,5,5,5,5,5,5,5,5,5,5],[5,10,10,10,10,10,10,10,10,10,5],[5,10,15,15,15,15,15,15,15,10,5],[5,10,15,20,20,20,20,20,15,10,5],[5,10,15,20,25,25,25,20,15,10,5],[5,10,15,20,25,30,25,20,15,10,5],[5,10,15,20,25,25,25,20,15,10,5],[5,10,15,20,20,20,20,20,15,10,5],[5,10,15,15,15,15,15,15,15,10,5],[5,10,10,10,10,10,10,10,10,10,5],[5,5,5,5,5,5,5,5,5,5,5]]
  _ _ _ _ _ _ _ _ _
 |                 |
 |    _ _ _ _ _    |
 |   |         |   |
 |   |    _    |   |
 |   |   |_|   |   |
 |   |         |   |
 |   |_ _ _ _ _|   |
 |                 |
 |_ _ _ _ _ _ _ _ _|

[[35,32,29,26,25,25,25,26,29,32,35],[32,28,25,22,20,20,20,22,25,28,32],[29,25,21,18,15,15,15,18,21,25,29],[26,22,18,14,11,10,11,14,18,22,26],[25,20,15,11,7,5,7,11,15,20,25],[25,20,15,10,5,0,5,10,15,20,25],[25,20,15,11,7,5,7,11,15,20,25],[26,22,18,14,11,10,11,14,18,22,26],[29,25,21,18,15,15,15,18,21,25,29],[32,28,25,22,20,20,20,22,25,28,32],[35,32,29,26,25,25,25,26,29,32,35]]
  _|             |_
_|    _ _ _ _ _    |_
    _|         |_
   |    _ _ _    |
   |   |     |   |
   |   |     |   |
   |   |_ _ _|   |
   |_           _|
_    |_ _ _ _ _|    _
 |_               _|
   |             |

```

# Answer
> 6 votes
# Perl 6, 135 bytes (131 chars)

```
{my$n="_";sub w{$^a.chop-$^b.chop??$n!!" "};my&q={|.[1..*],.tail};(($_ «[&w]».&q) ZZ~{$n="|";$_ «[&w]».map(*.&q)}()).map:{say |$_}}

```

Try it online!

Slightly ungolfed:

```
{
    my $n = "_";
    sub w { $^a.chop - $^b.chop ?? $n !! " "};
    my &q = {|.[1..*],.tail};
    (
        ($_ «[&w]».&q)
        ZZ~
        {$n="|";$_ «[&w]».map(*.&q)}()
    ).map:{say |$_}
}

```

**Explanation**: First, we define a variable `$n` (line 2) and a function `w` (line 3). This function returns a space if its two arguments are at the same "elevation", and the contents of variable `$n` otherwise. Instead of dividing by 10 and flooring, we abuse the fact that ints are `Cool` (can be treated like strings) and use `chop` to remove the last character (=digit). Then we calmly subtract them, forcing them into numbers again :—).

After that (line 4) we make up a function `q` that takes a list and returns that list with first element removed and the last element duplicated.

On the next 3 lines, we're going to make 2 more matrices from the input matrix: the first one has the first row missing and the last row duplicated (that's just `.&q` — using `.&`, you can call a function on anything as if it was a method — the thing in front of the dot is then the first argument), the other one has the first column missing and the last column duplicated (that's `.map(*.&q)`).

First (line 4) we take the original matrix `$_`, "overlay" it with the "shifted rows" matrix and use the function `w` as a binary operator (that's that `[&w]`) on the matching elements. That one puts a `_` wherever the matching elements are on the different elevations, and a  otherwise. So we get ½ of the result (only the "first characters").

At line 6, we do the same thing, but first we change `$n` to `|`, and we now "overlay" the original matrix with the matrix with shifted columns. Result has a `|` at different and  at the same elevations. These are the "second characters".

Now we just combine them together. We zip the arrays with a zip with a concat (yeah...), which results in a matrix of the original shape whose each element is the 2 matching elements of the "half-solutions" concatenated. Finally, we just map over this matrix (which is really a list of lists). Each of these lists is flattened and then `say`-ed (printed with a newline). Since `say` can take any number of arguments and it prints them all without separators, making the newline only at the end, we get the desired picture on stdout. (And the block returns a list of `True`s (each `say` returns one `True`), but who cares.)

# Answer
> 5 votes
# Jelly,  ~~25 23~~  22 bytes

-1 byte thanks to miles (`I` vectorises)

```
:⁵I;€0ao⁶
Zç”_Zż"ç”|$Y

```

A full program printing the result. As a monadic link it takes a list of lists of numbers, the elevations, and returns a list lists, however these "rows" consist of lists of two character "pairs" - if this is fine then 1 byte may be saved by removing `Y`.

**Try it online!**

### How?

```
:⁵I;€0ao⁶ - Link 1, assignCharacters (row-wise): list of lists of numbers; character, c
 ⁵        - literal 10
:         - integer division (vectorises)
  I       - incremental differences (vectorises) (zero if the same else non-zero)
     0    - literal 0
   ;€     - concatenate for €ach (rightmost edge of a row has no contour mark)
      a   - logical and (vectorises) with c (replace non-zeros with the contour character)
        ⁶ - literal space character
       o  - logical or (vectorises) (replace the zeros with spaces)

Zç”_Zż"ç”|$Y - Main link: list of lists of numbers, contours
Z            - transpose the input (get the columns)
  ”_         - literal underscore character, '_'
 ç           - call the last link (1) as a dyad with '_'
    Z        - transpose the result
          $  - last two links as a monad:
        ”|   -   literal pipe character, '|'
       ç     -   call the last link (1) as a dyad with '|'
      "      - zip with the dyadic operation:
     ż       -   zip (interleave the column-wise characters with the row-wise ones)
           Y - join with newlines
             - implicit print

```

# Answer
> 3 votes
# Jelly, 24 bytes

```
:⁵IṠ;€0
ZÇZị⁾_ +³Ç¤ị⁾| ¤

```

Try it online!

# Explanation

```
:⁵IṠ;€0           Helper Link; get contour data
:                 Floor division by
 ⁵                10
  I               Compute increments
   Ṡ              Sign; ±1 for different values and 0 for same values
    ;             Append
      0           Zero
     €            To each row
ZÇZị⁾_ +³Ç¤ị⁾| ¤  Main Link
Z                 Zip the input (for vertical contours _)
 Ç                Get the contour data
  Z               Zip the data (because it's zipped from the first Z)
   ị              Index into the string
    ⁾_            "_ "
       +          Add (vectorizing twice) to
        ³ ¤    ¤  Nilad starting from (input)
         Ç        Get contour data (horizontal contours |)
           ị      Index into the string
            ⁾|    "| "

```

-2 bytes thanks to Jonathan Allan

# Answer
> 3 votes
# Python 2, ~~199~~ ~~186~~ ~~157~~ 155 bytes

```
lambda a:(lambda x:'\n'.join(''.join('_ '[x==z]+'| '[x==y]for x,y,z in zip(r,r[1:]+r[-1:],q))for r,q in zip(x,x[1:]+x[-1:])))([[v/10for v in r]for r in a])

```

Try it online!

# Answer
> 2 votes
# Python 2, 226 bytes

```
l=[[j/10for j in i]for i in input()]
for i,j in enumerate(l[:-1]):print''.join('_ '[h==l[i+1][g]]+'| '[h==j[g+1]]for g,h in enumerate(j[:-1]))+'_ '[j[-1]==l[i+1][-1]]
print''.join(' '+'| '[i==j]for i,j in zip(l[-1],l[-1][1:]))

```

Try it online!

Whew, that was a doozy to work the logic out. I now see Hyper Neutrino ninja'd me with a shorter answer but I spent too much work on this *not* to post it. :P

Also, can I just say, this is an awesome way to make ASCII-art. Excuse me while I make a boatload more of these.

# Answer
> 2 votes
# J, 58 bytes

```
f=.{~0==/@]
[:(,/"2)2 2((' _'f{."1),' |'f{.);.3 1:+<.@%&10

```

Try it online!

An anonymous function which takes a matrix and outputs the contours.

Lotta room for improvement here. I didn't have time to try all the test cases so let me know if there are any issues. Will try to golf more and explain later.

# (Quick) Explanation

Helper function: indexes into a length 2 string based on whether the first element of a 2 length array is equal to the second. If it is equal, it indexes into the zeroth element, if it is unequal, it indexes into the first. A 1 length array always indexes into the zeroth element of the string.

```
f=.{~0==/@]

```

Main function

```
[:(,/"2)2 2((' _'f{."1),' |'f{.);.3 1:+<.@%&10

```

`1:+<.@%&10` floors each element divided by 10 and adds 1 (so we will never get 0 -- this is important for the helper function).

`2 2((' _'f{."1),' |'f{.);.3` cuts the matrix into 2 x 2 segments if it can (otherwise it'll give a 2 x 1, 1 x 2, or 1 x 1 segment near the edges) and applies the function that uses `f` to compare the top left element to the top right and the top left element to the bottom left.

`(,/"2)` flattens the result into the desired shape. I really feel like I should be able to avoid having to use this (and a lot of other things, but I digress).

# Answer
> 2 votes
# , ~~46~~ 45 bytes

```
' _|'({~];"1@(,&.>-@|:)&(0,~}.~:}:)|:)<.@%&10

```

Try it online!

# Answer
> 2 votes
## JavaScript (ES6), ~~120~~ 118 bytes

```
a=>a.map(b=>b.map(c=>c/10|0)).map((b,i,a)=>b.map((c,j)=>((a[i+1]||0)[j]-c?'_':' ')+(b[j+1]-c?'|':' ')).join``).join`\n`

```

Where `\n` represents the literal newline character. Edit: Saved 2 bytes thanks to @Bálint.

```
f=
a=>a.map(b=>b.map(c=>c/10|0)).map((b,i,a)=>b.map((c,j)=>((a[i+1]||0)[j]-c?'_':' ')+(b[j+1]-c?'|':' ')).join``).join`
`
;[
[[5,20],[3,6]]
,
[[1,5,8,9],[3,11,13,8],[7,14,10,9],[4,8,7,6]]
,
[[0,10,20,30,40,50,60,70,80,90],[0,0,10,10,20,20,30,30,40,40],[0,0,0,10,10,10,20,20,20,30],[0,0,0,0,10,10,10,10,20,20],[0,0,0,0,0,10,10,10,10,10],[0,0,0,0,0,0,10,10,10,10],[0,0,0,0,0,0,0,10,10,10],[0,0,0,0,0,0,0,0,10,10],[0,0,0,0,0,0,0,0,0,10],[0,0,0,0,0,0,0,0,0,0]]
,
[[5,5,5,5,5,5,5,5,5,5,5],[5,10,10,10,10,10,10,10,10,10,5],[5,10,15,15,15,15,15,15,15,10,5],[5,10,15,20,20,20,20,20,15,10,5],[5,10,15,20,25,25,25,20,15,10,5],[5,10,15,20,25,30,25,20,15,10,5],[5,10,15,20,25,25,25,20,15,10,5],[5,10,15,20,20,20,20,20,15,10,5],[5,10,15,15,15,15,15,15,15,10,5],[5,10,10,10,10,10,10,10,10,10,5],[5,5,5,5,5,5,5,5,5,5,5]]
,
[[35,32,29,26,25,25,25,26,29,32,35],[32,28,25,22,20,20,20,22,25,28,32],[29,25,21,18,15,15,15,18,21,25,29],[26,22,18,14,11,10,11,14,18,22,26],[25,20,15,11,7,5,7,11,15,20,25],[25,20,15,10,5,0,5,10,15,20,25],[25,20,15,11,7,5,7,11,15,20,25],[26,22,18,14,11,10,11,14,18,22,26],[29,25,21,18,15,15,15,18,21,25,29],[32,28,25,22,20,20,20,22,25,28,32],[35,32,29,26,25,25,25,26,29,32,35]]
].forEach(a=>document.write(['<pre>','</pre>'].join(f(a))));
```

# Answer
> 1 votes
# Proton, 202 bytes

```
R=(L=len)+range
k=[map((//)&10,r)for r:eval(input())]
d=(x,y,X,Y)=>X>=L(k)or Y>=L(k[X])or k[x][y]==k[X][Y]
print('\n'.join(map(''.join,[['_ '[d(x,y,x+1,y)]+'| '[d(x,y,x,y+1)]for y:R(k[x])]for x:R(k)])))

```

Try it online!

-2 bytes thanks to Jonathan Frech
-15 bytes by switching to Proton instead of Python 2

# Answer
> 1 votes
# Java 8, ~~200~~ ~~170~~ 169 bytes

```
a->{String r="";for(int l=a.length,i=0,j;i<l;i++,r+="\n")for(j=0;j<l;r+=(i>l-2||a[i][j]/10==a[i+1][j]/10?" ":"_")+(j++>l-2||a[i][j-1]/10==a[i][j]/10?" ":"|"));return r;}

```

**Explanation:**

Try it here.

Note that integer division in Java automatically floors.

```
a->{                   // Method with 2D int-array as parameter and String return-type
  String r="";         //  Result-String
  for(int l=a.length,  //  Length of the input array
      i=0,j;           //  Index integers
      i<l;i++,         //  Loop (1) over the rows of the input array
          r+="\n")     //  and append a new-line to the result after every iteration
    for(j=0;j<l;       //   Inner loop (2) over the columns of a row
      r+=              //    Append the String with:
         (i>l-2        //      If it's the last row,
         ||a[i][j]/10==a[i+1][j]/10?
                       //      or the current and next rows are equal floored/10:
          " "          //       Use a space
         :             //      Else:
          "_")         //       Use a "_"
        +              //     Plus
         (j++>l-2      //      If it's the last column in the row,
         ||a[i][j-1]/10==a[i][j]/10?
                       //      or the current and next columns are equal floored/10:
          " "          //       Use a space
         :             //      Else:
          "|")         //       Use "|"
    );                 //   End of column loop (2)
                       //  End of row-loop (1) (implicit / single-line body)
  return r;            //  Return the result-String
}                      // End of method

```

# Answer
> 1 votes
# R, 159 bytes

```
f=function(m){M=m%/%10;a=cbind(0,t(apply(M,1,diff)));b=rbind(apply(M,2,diff),0);a[!!a]="|";b[!!b]="_";M[]=gsub("0"," ",paste0(a,b));write(t(M),"",ncol(m),,"")}

```

With newlines and indentations:

```
f=function(m){
    M=m%/%10
    a=cbind(0,t(apply(M,1,diff))) #row-wise difference
    b=rbind(apply(M,2,diff),0) #column-wise difference
    a[!!a]="|"
    b[!!b]="_"
    M[]=gsub("0"," ",paste0(a,b)) # M[] is a trick to force the result to have the same structure as M
    write(t(M),"",ncol(m),,"")
    }

```

Does the integer division of the matrix, measures the row-wise and column-wise differences, and when not null replace by `|`and `_` respectively, then pastes both (painless, thanks to R's vectorization) and outputs.

Test cases:

```
> m=matrix(c(0,10,20,30,40,50,60,70,80,90,0,0,10,10,20,20,30,30,40,40,0,0,0,10,10,10,20,20,20,30,0,0,0,0,10,10,10,10,20,20,0,0,0,0,0,10,10,10,10,10,0,0,0,0,0,0,10,10,10,10,0,0,0,0,0,0,0,10,10,10,0,0,0,0,0,0,0,0,10,10,0,0,0,0,0,0,0,0,0,10,0,0,0,0,0,0,0,0,0,0),byrow=T,ncol=10)
> f(m)
  |_|_|_|_|_|_|_|_|_
    |_  |_ _|_ _|_ _
      |_    |_ _  |_
        |_      |_ _
          |_
            |_
              |_
                |_
                  |_

> m=matrix(c(5,5,5,5,5,5,5,5,5,5,5,5,10,10,10,10,10,10,10,10,10,5,5,10,15,15,15,15,15,15,15,10,5,5,10,15,20,20,20,20,20,15,10,5,5,10,15,20,25,25,25,20,15,10,5,5,10,15,20,25,30,25,20,15,10,5,5,10,15,20,25,25,25,20,15,10,5,5,10,15,20,20,20,20,20,15,10,5,5,10,15,15,15,15,15,15,15,10,5,5,10,10,10,10,10,10,10,10,10,5,5,5,5,5,5,5,5,5,5,5,5),byrow=T,ncol=11)
> f(m)
   _ _ _ _ _ _ _ _ _
  |                 |
  |    _ _ _ _ _    |
  |   |         |   |
  |   |    _    |   |
  |   |   |_|   |   |
  |   |         |   |
  |   |_ _ _ _ _|   |
  |                 |
  |_ _ _ _ _ _ _ _ _|

```

# Answer
> 0 votes
# Perl 5, ~~130~~ 126 bytes

124 bytes of code + 2 for `-ap` flags

```
push@a,[map 0|$_/10,@F]}{map{say map{($a[$r+1][$c]-$_&&$r<$#a?'_':$").($a[$r][++$c]-$_&&$c<@{$a[0]}?'|':$")}@$_;$c=0;$r++}@a

```

Try it online!

Input format is 2-D grid of space separated numbers.

**Explanation**

*This is from a previous iteration of the code.*

```
push@a,[map 0|$_/10,@F]     # read the input, divide it by 10, and store it in a 2-D array
}{                          # end the implicit while loop and start the final block
map{                        # repeat this for each line
  $_=($a[$r+1][$c]-$_&&$r<$#a?'_':$")       # set appropriate characters to output based
     .($a[$r][++$c]-$_&&$c<@{$a[0]}?'|':$") # on the given rules
  for@$_;                                   # repeat for each number on the line
  $c=0;$r++;                         # setup row and column counters for next iteration
  say@$_                             # output this line
}@a

```

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


title: Badugi, Who Wins?

text:
# Question
Title: Badugi, Who Wins?
#

Inspired by this challenge and related to this one.

### Background

Badugi \[bæduːɡiː\] is a low-ball draw-poker variant.

The Pokerstars World Cup Of Online Poker **$1K** event starts within **3** hours and I'll need to know how good my hands are!

The game uses a standard deck of **52** cards of four suits and thirteen ranks. The suits are unordered and shall be labelled `cdhs`; the ranks - ordered from highest `K` to lowest `A` \- are `KQJT98765432A`. As such the full deck may be represented as follows (space separated):

```
Kc Kd Kh Ks Qc Qd Qh Qs Jc Jd Jh Js Tc Td Th Ts 9c 9d 9h 9s 8c 8d 8h 8s 7c 7d 7h 7s 6c 6d 6h 6s 5c 5d 5h 5s 4c 4d 4h 4s 3c 3d 3h 3s 2c 2d 2h 2s Ac Ad Ah As

```

Each player is dealt **four** cards from the deck, there are four betting rounds with three drawing rounds in-between (a player always has four cards, they have the option of changing 0-4 of their cards with new ones from the dealer on each of the three drawing rounds).

If more than one player is still active after all these rounds there is a showdown, whereupon the strongest hand(s) win the wagered bets.

The game is played low-ball, so the lowest hand wins, and as mentioned above `A` (ace) is low. Furthermore the hand ranking is different from other forms of poker, and can be somewhat confusing for beginners.

The played "hand" is the lowest ranked combination made from the highest number of both "off-suit" (all-different-suits) and "off-rank" (all-different-ranks) cards possible (from the four held cards). That is: if one holds four cards of both distinct suits *and* distinct ranks one has a 4-card hand (called a "badugi"); if one does not have a 4-card hand but does have some set or sets of three cards of both distinct suits *and* distinct ranks one has a 3-card hand (one chooses their best); if one has neither a 4-card hand or a 3-card hand one probably has a 2-card hand, but if not one has a 1-card hand.

* As such the best possible hand is the 4-card hand `4-3-2-A` \- the lowest **off-rank** cards of **four different suits**, often termed a "number-1". The weakest possible hand would be the 1-card hand `K` and is only possible by holding exactly `Kc Kd Kh Ks`.
* Note that `4c 3h 2c As` is **not** a "number-1", since the `4c` and `2c` are of the same suit, but it *is* the strongest of the 3-card hands, `3-2-A`, it draws with other `3-2-1`s (like `Kh 3d 2s Ah`) and beats all other 3-card hands but loses to all 4-card hands (which could be as weak as `K-Q-J-T`).

+ The other possible 3-card hand that could be made from `4c 3h 2c As` is `4-3-A`, but that is weaker (higher) so not chosen.
* Similarly `8d 6h 3s 2h` is a 3-card hand played as `8-3-2` \- there are two off-rank off-suit combinations of size 3 and `8-3-2` is better (lower) than `8-6-3` since the three (or "trey") is lower than the six.

Comparing hands against one another follows the same logic - any 4-card beats any 3-card, any 3-card beats any 2-card and any 2-card beats any 1-card, while hands of the same number of used cards are compared from their highest rank down to their lowest (for example: `8-4-2` beats `8-5-A` but not any of `8-4-A`, `8-3-2` or `7-6-5`)

### The challenge:

Given two unordered-collections each of four cards, identify the one(s) which win a Badugi showdown (identify both if it is a draw).

The input may be anything reasonable:

* a single string of all eight cards as labelled above (with or without spaces) with the left four being one hand and the right the other (with an optional separator); or a list of characters in the same fashion
* a list of two strings - one per hand, or a list of lists of characters in the same fashion
* two separate strings or list inputs, one per hand
* the cards within the hands may be separated already too (so a list of lists of lists is fine)

Note, however:

* the cards may not be arranged into any order prior to input
* ...and the suits and ranks are fixed as the character labels specified here - If your language does not support such constructs just suggest something reasonable and ask if it is an acceptable alternative given your languages constraints.

The output should either be

* formatted the same as the input, or a printed representation thereof; or
* be one of three distinct and consistent results (e.g.: `"left"`, `"right"`, `"both"`; or `1`, `2`, `3`; etc.)

Really - so long as it is clear which of the two inputs are being identified it should be fine.

### Test cases

```
input                      ->  output
                                   (notes)
----------------------------------------------------------------------------
3c 2s 4d Ah - As 3h 2d 4h  ->  3c 2s 4d Ah
                                   (4-card 4-3-2-A beats 3-card 3-2-A)

3c 2s 4d Ah - As 2c 3d 4h  ->  3c 2s 4d Ah - As 2c 3d 4h
                                   (4-card 4-3-2-A draws with 4-card 4-3-2-A)

2d Ac 4h 3c - Kh Ad 9s 2c  ->  Kh Ad 9s 2c
                                   (3-card 4-2-A loses to 4-card K-9-2-A)

Kc Tc Qc Jc - Ac Ad Ah As  ->  Ac Ad Ah As
                                   (1-card T loses to 1-card A)

9c 9h Qc Qh - Qs Kh Jh Kd  ->  Qs Kh Jh Kd
                                   (2-card Q-9 loses to 3-card K-Q-J)

2d 5h 7c 5s - 2h 3c 8d 6c  ->  2d 5h 7c 5s
                                   (3-card 7-5-2 beats 3-card 8-3-2)

3s 6c 2d Js - 6h Jd 3c 2s  ->  6h Jd 3c 2s
                                   (3-card 6-3-2 loses to 4-card J-6-3-2)

Ah 6d 4d Ac - 3h 2c 3s 2s  ->  3h 2c 3s 2s
                                   (2-card 4-A loses to 2-card 3-2)

2h 8h 6h 4h - 6d 2d 5d 8d  ->  2h 8h 6h 4h - 6d 2d 5d 8d
                                   (1-card 2 = 1-card 2)

```

---

This is , so the shortest code in bytes wins per-language, and the shortest code overall wins. Don't let golfing languages put you off submitting in other languages, and ...have fun!

# Answer
> 2 votes
# Perl 6, 128 bytes

```
{.map({.combinations(1..4).grep({!.join.comb.repeated}).map({-$_,$_».trans('ATK'=>'1BZ')».ord.sort(-*)}).min}).minpairs».key}

```

Try it online!

Takes a list of hands (also more than two) which are lists of cards which are strings like `Kc`. Returns the indices of the hands with the lowest score. For two hands this is `(0)` if the first hand wins, `(1)` if the second hand wins, and `(0, 1)` for a draw.

Explained:

```
{
    # Map hands to best "played hand".
    .map({
        # Generate all combinations of length 1 to 4.
        .combinations(1..4)
        # Remove hands with repeated characters.
        .grep({!.join.comb.repeated})
        # Map to a cmp-arable representation. This works because
        # lists are compared element-wise. Translate some characters
        # so that ASCII order works. Sort in reverse order so that
        # element-wise comparison will go from highest to lowest.
        .map({ -$_, $_».trans('ATK'=>'1BZ')».ord.sort(-*) })
        # Find best hand.
        .min
    })
    # Return indices of lowest scoring hands. It's a shame that
    # `minpairs` doesn't support a filter like `min`.
    .minpairs».key
}

```

# Answer
> 2 votes
# JavaScript (ES6), ~~209~~ ~~202~~ ~~192~~ ~~182~~ 181 bytes

*Saved 7 bytes thanks to @Neil*

Takes input as an array of arrays of strings. Returns `true` if the first hand wins, `false` if the second hand wins, or `2` in the event of a tie.

```
a=>([a,b]=a.map(a=>a.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).map(a=>!/(\w).*\1/.test(a)*a.length+a.map(a=>'KQJT98765432A'.search(a[0])+10).sort()).sort().pop()),a==b?2:a>b)

```

### Test cases

```
let f =

a=>([a,b]=a.map(a=>a.reduce((a,x)=>[...a,...a.map(y=>[x,...y])],[[]]).map(a=>!/(\w).*\1/.test(a)*a.length+a.map(a=>'KQJT98765432A'.search(a[0])+10).sort()).sort().pop()),a==b?2:a>b)

console.log(f([["3c","2s","4d","Ah"], ["As","3h","2d","4h"]])) // true  (1st hand wins)
console.log(f([["3c","2s","4d","Ah"], ["As","2c","3d","4h"]])) // 2     (tie)
console.log(f([["2d","Ac","4h","3c"], ["Kh","Ad","9s","2c"]])) // false (2nd hand wins)
console.log(f([["Kc","Tc","Qc","Jc"], ["Ac","Ad","Ah","As"]])) // false (2nd hand wins)
console.log(f([["9c","9h","Qc","Qh"], ["Qs","Kh","Jh","Kd"]])) // false (2nd hand wins)
console.log(f([["2d","5h","7c","5s"], ["2h","3c","8d","6c"]])) // true  (1st hand wins)
console.log(f([["3s","6c","2d","Js"], ["6h","Jd","3c","2s"]])) // false (2nd hand wins)
console.log(f([["Ah","6d","4d","Ac"], ["3h","2c","3s","2s"]])) // false (2nd hand wins)
console.log(f([["2h","8h","6h","4h"], ["6d","2d","5d","8d"]])) // 2     (tie)
```

### How?

```
a => (
  // store the best combination for both hands in a and b respectively
  [a, b] = a.map(a =>
    // compute the powerset of the hand
    a.reduce((a, x) => [...a, ...a.map(y => [x, ...y])], [[]])
    // for each entry:
    .map(a =>
      // invalidate entries that have at least 2 cards of same rank or same value
      !/(\w).*\1/.test(a) *
      // the score of valid entries is based on their length ...
      a.length +
      // ... and their card values, from highest to lowest
      // (we map 'KQJT98765432A' to [10 - 22], so that the resulting
      // strings can be safely sorted in lexicographical order)
      a.map(a => 'KQJT98765432A'.search(a[0]) + 10).sort()
    )
    // keep the best one
    .sort().pop()
  ),
  // compare a with b
  a == b ? 2 : a > b
)

```

# Answer
> 1 votes
# Python 3, ~~207~~ 204 bytes

```
lambda i,j:L(h(i))-L(h(j))if L(h(i))!=L(h(j))else(h(i)<h(j))-(h(i)>h(j))
L=len
def h(l):s=set();return[x[0]for x in sorted(y.translate({65:49,75:90,84:65})for y in l)if not(s&set(x)or s.update(*x))][::-1]

```

Try it online!

*Saved 3 bytes thanks to Jonathan Frech*

Returns `1` if the first hand wins, `-1` if the second hand wins and `0` in case of a draw.

The function `h` computes a list that represents the hand.

The lambda compares two representations of hand. I think it might be shortened, but I wanted to return only three values and didn't find a simpler way to do comparison.

# Answer
> 1 votes
# Jelly, 36 bytes

```
ẎŒQȦ;L;Ṗ€Ṣ$
“A+KYTE”yḲONŒPÇ€ṢṪµ€⁼€Ṁ$

```

A monadic link taking a list of two lists of characters
\- each being a space separated representation of the hand (e.g. `"Ac 2d 4s 3h"`)
returning a list of two numbers identifying the winner(s) with `1` and any loser with `0`
\- i.e. `[1, 0]` = left wins; `[0, 1]` = right wins; `[1, 1]` = draw.

**Try it online!** or see the test-suite.

### How?

```
ẎŒQȦ;L;Ṗ€Ṣ$ - Link 1, sortKey: list of lists of numbers representing some cards (see Main)
Ẏ           - flatten into a single list of numbers
 ŒQ         - distinct sieve (1 at first occurrence of anything, 0 at the rest)
   Ȧ        - Any & All? zero if any are 0 or if empty; 1 otherwise (i.e. playable hand?)
     L      - length of input (number of cards in the hand)
    ;       - concatenate
          $ - last two links as a monad:
       Ṗ€   -   pop each (get just the rank portions)
         Ṣ  -   sort (Main's translation & negation of ordinals ensures A>2>3>...>Q>K)
      ;     - concatenate (now we have [isPlayable; nCards; [lowToHighCards]])

“A+KYTE”yḲONŒPÇ€ṢṪµ€⁼€Ṁ$ - Main link: list of lists of characters, hands
                  µ€     - for €ach of the two hands:
“A+KYTE”                 -   literal list of characters "A+KYTE" (compressing doesn't help - lower case would be “£Ḅṁ⁽>» though -- I'll stick with kyte though it's kind of nice.)
        y                -   translate - change As to +s, Ks to Ys and Ts to Es
                         -               note the ranks are now in ordinal order:
                         -               +<2<3<4<5<6<7<8<9<E<J<Q<Y
         Ḳ               -   split at spaces - split the four cards up
          O              -   to ordinals '+'->43, '2'->50, ...
           N             -   negate - effectively reverse the ordering
            ŒP           -   power-set - get all combinations of 0 to 4 cards inclusive
              Ç€         -   call the last link (1) as a monad for €ach such selection
                Ṣ        -   sort these keys
                 Ṫ       -   tail - get (one of) the maximal keys
                         -                       (the key of a best, playable selection)
                       $ - last two links as a monad:
                      Ṁ  -   maximum (the better of the two best, playable selection keys)
                    ⁼€   -   equals? for €ach (1 if the hand is a winner, 0 if not)

```

---
Tags: code-golf, string, decision-problem, game, card-games
---


title: Dwarves and Coins

text:
# Question
Title: Dwarves and Coins
**The Situation:**

Several (`M`) dwarves have found a goblin's chest with `N` gold coins and have to divide them. Due to ancient rules governing the allocation of loot to pirates in order of seniority, the oldest dwarf should get one coin more than the next oldest dwarf, and so on, so that the youngest dwarf gets `M-1` fewer coins than the oldest dwarf. Additionally, no dwarf has to pitch in any coins (ie no negative coins to any dwarfs)

Help the dwarves to divide the coins in this way, or tell them that this is impossible.

Winner's code must always answer correctly (this challenge is deterministic) and follow the general rules.

**Input**

You are given an integer N (3 ≤ N ≤ 1000) for number of coins and an integer M (3 ≤ M ≤ N) for number of dwarves, space-separated.

**Output**

If it is impossible to divide the coins in the way that dwarves want, print -1 (minus one). Otherwise, print the numbers of coins that each dwarf will receive, from oldest to youngest. Separate the numbers with spaces.

**Samples**:

**input**

```
3 3

```

**output**

```
2 1 0

```

**input**

```
9 3

```

**output**

```
4 3 2

```

**input**

```
7 3

```

**output**

```
-1

```

**input**

```
6 4

```

**output**

```
3 2 1 0

```

# Answer
# J - ~~32~~ ~~29~~ ~~28~~ 25

~~Not~~ shorter than other J solution, ~~but~~ and uses a different idea

```
(]{.[:i:-:@-.@]-%)/ ::_1:

```

The answer for the number of coins the highest rank gnome is getting is simply `N/M+(M-1)/2` (if it's an integer), we construct the negative of this `-:@-.@]-%`. Then `i:` makes an array like that `2 1 0 _1 _2` for argument `_2` and we take M elements from it.
> 18 votes

# Answer
# J - 30 char

Very fun to golf. A lot of things worked out neatly.

```
((+/@s~i.[){ ::_1:s=.+/&i.&-)/

```

Explanation:

* `/` \- Take the space-separated integers as argument, and slip the function between them. That is to say, consider N the left argument to the function in the brackets `(...)` and M the right argument.
* `i.&-` \- Negate (`-`) and then take integers (`i.`). Normally, when you do something like `i.5` you get `0 1 2 3 4`. Whenever `i.` receives a negative number, however, it reverses that output list. So e.g. `i._5` will give `4 3 2 1 0`.
* `s=.+/&` \- Perform the above action on each argument (`&`) and then make an addition table (`+/`) out of these arrays. We now have a table where each row is a possible coin distribution to M dwarves, though maybe not when there's N coins. Finally, this table-making verb is so useful we're going to call it `s` and use it again later.
* `+/@s~` \- Now, we use `s` again, but we swap (`~`) the order of the arguments, so that we transpose the table. This is a golfy way of taking the sum of each row after creating the table (`+/@`), having to do with the way J sums multidimensional lists.
* `i.[` \- In this list of sums, we search for the left argument to the verb, i.e. N. If N is an item, we get that index: else we get the length of the list, which notably is an invalid index.
* `{ ::_1:` \- Now we try to use the index to pull out a row from table in `s`. `{` will throw a domain error if the index was invalid, so in that case we catch the error (`::`) and return -1 (`_1:`). This handles everything. Since we use `i.&-` previously, the coin distribution will be in descending order, as was required.

Usage:

```
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 9 3
4 3 2
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 7 3
_1
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 6 4
3 2 1 0
   ((+/@s~i.[){ ::_1:s=.+/&i.&-)/ 204 17
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4

```
> 11 votes

# Answer
# R - ~~71~~ ~~70~~ ~~67~~ ~~66~~ 65 chars

```
s=scan();m=s[2];x=s[1]-sum(1:m);cat(if(x%%m|-m>x)-1 else x/m+m:1)

```

Ungolfed:

```
s = scan()    # Reads N and M by stdin.
m = s[2]
x = s[1] - m*(m-1)/2
cat(if (x %% m | x < -m) -1 else x/m + m:1)

```

Solution:

If *M* the number of dwarfs, then the sequence of paid gold can be decomposed to two singular series. First a series ending in zero: M-1, ..., 2, 1, 0 and a constant series of c, c, ..., c. The sum of the first series is always M\*(M-1)/2. So if the remainder (x = N - M\*(M-1)/2) could be divided without remainder (modulo equal 0), each dwarf gets x/M plus the part of the decreasing series.

Usage:

```
> s=scan()
1: 10 4
3:
Read 2 items
> m=s[2]
> x = s[1] - m*(m-1)/2
> cat(if (x %% m || x<0) -1 else x/m + (m-1):0)
4 3 2 1

```
> 7 votes

# Answer
## Python 3 (100)

Using the same idea as @Geobits but conforming to the input and output requirements.

```
n,m=map(int,input().split())
κ,ρ=divmod(n-m*(m-1)//2,m)
x=[-1]if ρ else range(κ,κ+m)[::-1]
print(*x)

```
> 4 votes

# Answer
# Python 3 - 109 107 103 102 90 93

Using the same idea as Evpok, but with a number of improvements.

```
n,m=map(int,input().split())
k=n/m+m/2
a=int(k)
print(*(range(a,a-m,-1),[-1])[k-a-.5or~a>-m])

```

The improvements are:

1. Eliminating the space after else and before ' '. 1 character
2. Eliminating the ' ' inside split(), because splitting on spaces is a default. 3 characters
3. Lowering x by 1 changing the -1 to +1 inside divmod, and then changing the range function to use the range's reversed order option. 3 characters.
4. EDIT: ... if ... else ... changed to ... and ... or ... 2 characters.
5. EDIT: Divmod made explicit, r removed. 4 characters.
6. EDIT: x removed, m//n used explicitly. 1 character
7. EDIT: used starred expressions instead of ' '.join(map(str,...)), added x to avoid repeating print(). 12 characters.
8. EDIT: I realized that I was allowing negative numbers of coins to be given to the Dwarves. I changed the code to avoid this.
> 4 votes

# Answer
## PHP (187)

It's my first attempt at golfing, and I know it could be better, but still :)

**Golfed:**

```
<?php
$b=fgets(STDIN);list($c,$d)=explode(' ',$b);if((($d&1)AND($c%$d==0))OR($c%$d==$d/2)){for($e=floor($c/$d)+floor($d/2);$e>floor($c/$d)-round($d/2);$e--){echo"$e ";}}else{die('-1');}?>

```

**Ungolfed:**

```
<?php
$a = fgets(STDIN);
list($coins, $dwarves) = explode(' ', $a);
if ((($dwarves & 1) AND ($coins % $dwarves == 0)) OR ($coins % $dwarves == $dwarves / 2)) {
    for (
        $i = floor($coins / $dwarves) + floor($dwarves / 2);
        $i > floor($coins / $dwarves) - round($dwarves / 2);
        $i--
    ) {
        echo "$i ";
    }
}
else {
  die('-1');
}
?>

```

Execute in a shell

**Basic idea:**

Coins can be separated by these rules, if one of these is true:

1. The dwarves are odd number, and the coins are divisible by the dwarves with no remains
2. The dwarves are even number, and the coins remaining after dividing coins / dwarves is equal to half of the dwarves number

If so, we take for base the average coins per dwarf (ACPD). But we have to start from the highest and output until we reach the lowest. So we make a loop with counter starting from ACPD + the count of the rest of the dwarves towards the higher end, and go on until we reach the ACPD - the count of the rest of the dwarves towards the lower end.

It's basically the same if the dwarves are odd (i.e. 5 dwarves - the middle one is 3, and in both ends there remain 2), but not if they are even - which is why we rely on floor AND round.

**Problems so far:** Works with too low coins number, which means some dwarves will be smacked down and robbed of their precious earnings. And this is sad. Or at least if you like dwarves.

**Solution**:

1. Think of a way to calculate the lowest amount of coins so the calculation doesn't end up with dwarves in the dust.
2. Design not-so-greedy dwarves.

**Smarter solution**:

Coins are metal. Make the dwarves melt them all, and then cast them in smaller/larger amount of coins, so they are divisible in any case.

**Smartest solution**:

Steal their mountain, rename yourself to Smaug and keep it all for yourself. After all, why do you have to bother with grumpy dwarves?
> 4 votes

# Answer
## Python 3 - 114

```
n,m=map(int,input().split(' '))
r=range(m);n-=sum(r)
if n%m<1:
 for x in r:print(m-x+n//m-1,end=' ')
else:print -1

```

Works by checking if `N-(M*(M-1)/2)` is evenly divisible by `M`. New to python, so any tips appreciated.

Ideone.com example

```
Input:
735 30
Output:
39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10

```
> 3 votes

# Answer
## C# - 322

```
using System;using System.Linq;namespace D{class P{static void Main(string[]args){int n=Convert.ToInt16(args[0]);int m=Convert.ToInt16(args[1]);bool b=false;int q=n/2+1;g:b=!b;int[]z=new int[m];for(int i=0;i<m;i++){z[i]=q-i;}if(z.Sum()==n)foreach(int p in z)Console.Write(p+" ");else{q--;if(b)goto g;Console.Write(-1);}}}}

```

Horrible score but I took a different approach and got to use `goto` :)

I will shorten it later.
> 3 votes

# Answer
### R: ~~77~~ ~~73~~ 70 chars

```
a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))

```

Create a vector going from (M-1) to 0 and adds 1 to each number until the sum is no longer inferior to N. If it is superior, output -1 else output the vector.

Indented and slightly ungolfed:

```
a=scan()   #Reads in stdin (by default numeric, space-separated)
r=a[2]:1-1 #Creates vector (M-1) to 0
while(sum(r)<a[1])r=r+1 #Increments all member of vector by 1 until sum is not inferior to N
cat( #Outputs to stdout
    `if`(sum(r)>a[1], -1, r) #If superior to N: impossible, returns -1
    )

```

Example usage:

```
> a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))
1: 9 3
3:
Read 2 items
4 3 2
> a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))
1: 7 3
3:
Read 2 items
-1
> a=scan();r=a[2]:1-1;while((n=sum(r))<a[1])r=r+1;cat(`if`(n>a[1],-1,r))
1: 204 17
3:
Read 2 items
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4

```
> 3 votes

# Answer
# Java 210

```
class A { public static void main(String[] a){int d=Integer.parseInt(a[0]),c=Integer.parseInt(a[1]);if (2*c%d==0) for (int i=0;i<d;i++) System.out.print((((1+(2*c/d)-d)/2)+i)+" "); else System.out.print(-1);}}

```
> 3 votes

# Answer
# Golfscript, 35

```
~:M.(*2/-.M%{;-1}{M/M+,-1%M<' '*}if

```

### How it works

In the following example, the input is `9 3`.

```
          # STACK: "9 3"
~         # Interpret the input string.
          # STACK: 9 3
:M        # Store the top of the stack (number of dwarves) in variable `M'.
.         # Duplicate the top of the stack.
          # STACK: 9 3 3
(         # Decrement the top of the stack.
          # STACK: 9 3 2
*         # Multiply the topmost elements of the stack.
          # STACK: 9 6
2/        # Divide the top of the stack by `2'.
          # STACK: 9 3
          # So far, we've transformed `M' into `M*(M-1)/2', which is the minimum amount of
          # coins all dwarves together will get. This number comes from the fact that the
          # youngest dwarf will get at least 0 coins, the next at least 1 coin, etc., and
          # 0 + 1 + ... + (M - 1) = M*(M-1)/2.
-         # Subtract the topmost elements of the stack.
          # STACK: 6
          # The remaining coins have to get reparted evenly to all dwarves.
.         # Duplicate the top of the stack.
          # STACK: 6 6
M%        # Calculate the top of the stack modulus `M'.
          # STACK: 6 0
{         # If the modulus is positive, the remaining coins cannot get reparted evenly.
    ;-1   # Replace the top of the stack by `-1'.
}
{         # If the modulus is zero, the remaining coins can get reparted evenly.
    M/    # Divide the top of the stack by `M'.
          # STACK: 2
          # This is the number of coins all dwarves will get after giving 1 to the second
          # youngest, etc.
    M+    # Add `M' to the top of the stack.
          # STACK: 5
    ,     # Replace the top of the stack by an array of that many elements.
          # STACK: [ 0 1 2 3 4 ]
          # The rightmost element is the number of coins the oldest dwarf will get.
    -1%   # Reverse the array.
          # STACK: [ 4 3 2 1 0 ]
    M<    # Keep the leftmost `M' elements.
          # STACK: [ 4 3 2 ]
          # There are only `M' dwarves.
    ' '*  # Join the array, separating by spaces.
          # STACK: "4 3 2"
}if

```
> 2 votes

# Answer
# JavaScript - 76

> Observe that k + (k - 1) + ... + (k - (M - 1)) = M(k - (M - 1)/2) Setting this equal to N gives k = N/M + (M-1)/2 for the highest amount. If this is integer, then k % 1 == 0 and the amounts we are looking for are k, k - 1, ..., k - (M - 1).

I could probably have written this shorter in another language, but there was no JS solution yet so here it is:

```
N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

```

Run in the console.

Example input:

```
N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

```

Output:

```
3
2
1

```

Input:

```
N=6;M=4;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

```

Output:

```
3
2
1
0

```

Input:

```
N=7;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)

```

Output: -1

Too bad console.log is so long to spell :) Unfortunately declaring `l=console.log.bind(console)` does not make it any shorter, and just `l=console.log` does not work.

Input:

```
"N=3;M=3;if((r=N/M+(M-1)/2)%1)console.log(-1);else while(M--)console.log(r--)".length

```

Output:

```
76

```
> 2 votes

# Answer
# Julia, 45

```
f(n,m)=(x=n/m-m/2+1/2;x%1==0?[x+m-1:-1:x]:-1)
julia> f(6,4)'
1x4 Array{Float64,2}:
 3.0  2.0  1.0  0.0

```

Just a bit of algebra, took me way longer than it should have.
> 2 votes

# Answer
# Delphi XE3 (176)

```
uses SysUtils;var d,c,i:integer;begin read(c,d);for I:=1to d-1do c:=c-i;if c mod d>0then writeln(-1)else begin c:=c div d;for I:=d-1downto 0do write(IntToStr(i+c)+' ');end;end.

```

### How it works.

Reads 2 integers, coins and dwarves.
Substracts the difference per dwarf.
If the remainder mod dwarves\>0 its impossible.
Else get equal share per dwarf in a loop of dwarves-1 to 0 and prints dwarfIndex+equal share

### Ungolfed

```
uses SysUtils;
var
  d,c,i:integer;
begin
  read(c,d);
  for I:=1to d-1do
    c:=c-i;
  if c mod d>0then
    writeln(-1)
  else
  begin
    c:=c div d;
    for I:=d-1downto 0do
      write(IntToStr(i+c)+' ');
  end;
end.

```
> 1 votes

# Answer
# Mathematica 65

The function, `g`, generates all the increasing-by-one sequences, of length m, from 0 to n and checks whether any of them sum to m. If successful, the sequence is returned; otherwise, -1 is returned.

The sequences are made by `Partition`ing the list {0,1,2,3… m} into all possible sublists of n contiguous integers.

There are, of course, more efficient ways to achieve the same effect, but those that I have found require more code.

```
n_~g~m_:=If[(s=Select[Partition[0~Range~n,m,1],Tr@#==n&])=={},-1,s]

```

Examples

```
g[9, 3]

```

> {{2, 3, 4}}

---

```
g[3, 3]

```

> {{0, 1, 2}}

---

```
g[7, 3]

```

> -1

---

```
g[705, 3]

```

> {{234, 235, 236}}

---

```
g[840, 16]

```

> {{45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60}}

---

```
g[839, 16]

```

> -1
> 1 votes

# Answer
# Cobra - 198

Cobra Website

```
class P
    def main
        x,y=Console.readLine.split
        a,b=x to int,y to int
        l=[]
        t=n=0
        for i in b,t+=i
        while (t+=b)<=a,n+=1
        for i in b,l.insert(0,i+n)
        print if(t-b<>a,-1,l.join(" "))

```

**Explained:**

```
class P
    def main

```

Required for the code to run

```
        x,y=Console.readLine.split
        a,b=x to int,y to int

```

Takes input and stores it as `a` and `b`

```
        l=[]
        t=n=0

```

Initializes the output list `l`, and initializes the total required money `t` and number of coins to add to each dwarves pile `n`

```
        for i in b,t+=i

```

Finds the lowest possible money value that will result in all dwarves having an allowable number of coins in their pile

```
        while (t+=b)<=a,n+=1

```

Determines how many coins to add to each pile so that the total required money is \>= to the total available money

```
        for i in b,l.insert(0,i+n)

```

Fills the list with the different sized piles of money

```
        print if(t-b<>a,-1,l.join(" "))

```

Outputs either `-1` or `l` depending whether the total required money is equal to the total available money
> 1 votes

# Answer
**C 131**

```
#include <edk.h>
main(int a,char **v){int j=atoi(*++v),k=atoi(*++v)-j*(j-1)/2;k<0||k%j?j=1,k=-1:k/=j;while(j--)printf("%d ",k+j);}

```

Ungolfed

```
#include <edk.h> //Shortest standard header including stdio.h and stdlib.h
main(int a,char **v)
{
    int j=atoi(*++v),k=atoi(*++v)-j*(j-1)/2;

    k<0||k%j?j=1,k=-1:k/=j;  // If youngest dwarf gets < 0 or amount not equally divisible then set values such that ...

    while(j--)printf("%d ",k+j); // ... loop prints out correct values
}

```

This compiles with a warning because main has no type. If this is not valid in the rules of golf, I would have to add five characters.
> 1 votes

# Answer
# Perl 5, 78 + 1 (-n) = 79 bytes

```
($d)=/ (.*)/;$,=$";say(($b=$_-($d**2-$d)/2)%$d?-1:map$_+$b/$d,reverse 0..$d-1)

```

Try it online!
> 0 votes

# Answer
# Python (~~100~~ ~~96~~ 94):

~~A nice, round-scoring answer.~~ Not any more, but it IS shorter now.

```
def f(n,m):a=range(m)[::-1];b=n-sum(a);c=b/m;d=[i+c for i in a];return(d,-1)[-1in d or c*m!=b]

```

Ungolfed:

```
def f(n,m):
 a = range(m)[::-1]
 b = sum(a)
 c = (n-b)/m
 if c * m != n-b: return -1
 d = [i+c for i in a]
 return (d,-1)[-1 in d or c!=n-b]
 if -d in d or c*m!=n-b:
  return -1
 return d

```

Output:

```
def f(n,m):a=range(m)[::-1];b=sum(a);c=(n-b)/m;d=[i+c for i in a];return (d,-1)[-1 in d or c*m!=n-b]

f(3,3)
Out[2]: [2, 1, 0]

f(9,3)
Out[3]: [4, 3, 2]

f(7,3)
Out[4]: -1

f(6,4)
Out[5]: [3, 2, 1, 0]

```
> -1 votes

---
Tags: code-golf
---


title: All Armstrong numbers

text:
# Question
Title: All Armstrong numbers
An Armstrong number (AKA Plus Perfect number, or narcissistic number) is a number which is equal to its sum of `n`-th power of the digits, where `n` is the number of digits of the number.

For example, `153` has `3` digits, and `153 = 1^3 + 5^3 + 3^3`, so `153` is an Armstrong number.

For example, `8208` has `4` digits, and `8208 = 8^4 + 2^4 + 0^4 + 8^4`, so `8208` is an Armstrong number.

On 14th Nov 2013, we tested if a number is an Armstrong number.

Now, we would like to list all Armstrong numbers. There are exactly `88` Armstrong numbers:

```
1
2
3
4
5
6
7
8
9
153
370
371
407
1634
8208
9474
54748
92727
93084
548834
1741725
4210818
9800817
9926315
24678050
24678051
88593477
146511208
472335975
534494836
912985153
4679307774
32164049650
32164049651
40028394225
42678290603
44708635679
49388550606
82693916578
94204591914
28116440335967
4338281769391370
4338281769391371
21897142587612075
35641594208964132
35875699062250035
1517841543307505039
3289582984443187032
4498128791164624869
4929273885928088826
63105425988599693916
128468643043731391252
449177399146038697307
21887696841122916288858
27879694893054074471405
27907865009977052567814
28361281321319229463398
35452590104031691935943
174088005938065293023722
188451485447897896036875
239313664430041569350093
1550475334214501539088894
1553242162893771850669378
3706907995955475988644380
3706907995955475988644381
4422095118095899619457938
121204998563613372405438066
121270696006801314328439376
128851796696487777842012787
174650464499531377631639254
177265453171792792366489765
14607640612971980372614873089
19008174136254279995012734740
19008174136254279995012734741
23866716435523975980390369295
1145037275765491025924292050346
1927890457142960697580636236639
2309092682616190307509695338915
17333509997782249308725103962772
186709961001538790100634132976990
186709961001538790100634132976991
1122763285329372541592822900204593
12639369517103790328947807201478392
12679937780272278566303885594196922
1219167219625434121569735803609966019
12815792078366059955099770545296129367
115132219018763992565095597973971522400
115132219018763992565095597973971522401

```

Your task is to output exactly the list above.

# Flexibility

The separator **does not have to be** be a line-break, but the separator must not contain any digit.

A trailing separator at the end of the output is optional.

Also, your code must terminate ~~before the heat death of the universe~~ in a reasonable amount of time (say, less than a **day**).

You **may** hard-code the result or any part thereof.

# References

# Answer
> 13 votes
# CJam, ~~626~~ ~~397~~ ~~325~~ ~~218~~ ~~168~~ ~~134~~ ~~93~~ ~~55~~ ~~54~~ 53 bytes

```
8A#{[_8b3394241224Ab?A0e[A,]ze~__,f#:+s_$@s=*~}%$1>N*

```

Execution takes roughly four and a half hours on my machine. One Armstrong number is hardcoded, the remaining ones are computed.

Computing all Armstrong numbers is theoretically possible in 24 hours, but the approach

```
9A#{_9b8 9erA0e[A,]ze~__,f#:+s_$@s=*~}%$1>N*

```

drives the garbage collector nuts. So far, all settings I've tried resulting either in a GC error message or too much memory consumption.

### How it works

```
8A#              e# Compute 8¹⁰ = 1,073,741,824.
{                e# Map the following block over all I in [0 ... 1,073,741,824].
  [              e#   Begin an array.
    _8b          e#     Copy I and convert the copy to base 8.
    3394241224Ab e#     Push [3 3 9 4 2 4 1 2 2 4], the representation of the
                 e#     Armstrong number 1122763285329372541592822900204593.
    ?            e#     If I is non-zero, select the array of base 8 digits.
                 e#     Otherwise, select the hardcoded representation.
    A0e[         e#     Left-pad the digit array with 0's to length 10.
    A,           e#     Push [0 1 2 3 4 5 6 7 8 9].
  ]              e#   End the array.
  ze~            e#   Transpose and perform run-length decoding, repeating the
                 e#   digit n k times, where k in the n-th entry of the repr.
                 e#   This is a potential Armstrong number, with sorted digits.
  _              e#   Push a copy.
  _,             e#   Compute the length of yet another copy.
  f#             e#   Elevate all digits to that power.
  :+s            e#   Add the results and cast to string.
  _$             e#   Push a sorted copy.
  @s             e#   Stringify the sorted digits.
  =*             e#   Compare for equality and repeat the string that many times.
                 e#   This pushes either the representation of an Armstong number
                 e#   or an empty string.
  ~              e#   Evaluate, pushing the number or doing nothing.
}%               e#
$1>              e# Sort and remove the lowest number (0).
N*               e# Join, separating by linefeeds.

```

# Answer
> 1 votes
# Pyth, 330 bytes

```
0000000: 6a 6d 73 2e 65 2a 73 62 5e 6b 73 73 4d 64 64 63 jms.e*sb^kssMddc
0000010: 2e 5a 22 78 da ad 50 51 76 03 30 08 ba 52 04 4d .Z"x..PQv.0..R.M
0000020: de ee 7f b1 81 26 dd f6 bf f6 35 35 28 08 59 b1 .....&....55(.Y.
0000030: 3e 9f 7f 2e e7 3b 68 ac f7 8b 3f c0 c5 e2 57 73 >....;h...?...Ws
0000040: 2d bc f3 02 e8 89 8b a3 eb be cf a1 ae 3b 33 84 -............;3.
0000050: 01 66 1a 23 d7 40 8c 06 d0 eb e6 fa aa 96 12 17 .f.#.@..........
0000060: 11 bc f8 d0 e0 6d 96 e2 d0 f1 b3 41 c7 8a 74 19 .....m.....A..t.
0000070: 3d b8 fc 77 2b 2c ce 88 05 86 d6 9e d5 f5 4c 37 =..w+,........L7
0000080: b0 9e ab 46 75 a1 37 f1 5d 5b 36 dd 86 e5 6e 15 ...Fu.7.][6...n.
0000090: a4 09 b4 0c 40 a7 01 1d 2a 8d a8 49 e4 ac 23 1d ....@...*..I..#.
00000a0: 25 c5 55 53 02 be 66 c7 dd bd c3 4a 28 9d 39 57 %.US..f....J(.9W
00000b0: 6f 11 92 ca 94 8a a5 87 38 4e 1d 25 17 60 3a 2d o.......8N.%.`:-
00000c0: 51 5a 96 55 7e 04 7a 41 aa b1 84 c4 88 10 fd 28 QZ.U~.zA.......(
00000d0: 04 37 64 68 ab 58 1e 0c 66 99 de a6 4c 34 2e 51 .7dh.X..f...L4.Q
00000e0: 19 96 fc a7 ea 01 6d de b4 2b 59 01 52 1b 1c 6e ......m..+Y.R..n
00000f0: 92 eb 38 5c 22 68 6f 69 60 e9 ab 17 60 6e e9 6b ..8\"hoi`...`n.k
0000100: 44 d6 52 44 33 fd 72 c9 7a 95 28 b2 a8 91 12 88 D.RD3.r.z.(.....
0000110: 74 0a 7b 10 59 16 ab 44 5a 4e d8 17 e5 d8 a8 a3 t.{.Y..DZN......
0000120: 97 09 27 d9 7b bf 8a fc ca 6b 2a a5 11 28 89 09 ..'.{....k*..(..
0000130: 76 3a 19 3a 93 3b b6 2d eb 2c 9c dc 45 a9 65 1c v:.:.;.-.,..E.e.
0000140: f9 be d5 37 27 6e aa cf 22 54                   ...7'n.."T

```

Encodes the count of the number of 0-9 in each number.

Try it online!

# Answer
> 0 votes
# Python 2, ~~358~~ 204 bytes

-6 bytes thanks to @JonathanFrech

```
from itertools import*
R=range
S=sorted
A=[]
for i in R(40):
 B=(i>31)*10
 for c in combinations_with_replacement(R(10),i-B):t=sum(d**i for d in c);A+=[t]*(S(map(int,str(t)))==S(S(c)+R(B)))
print S(A)[1:]

```

In my computer, it ran in 11 and a half hours.

## How it works?

Only one thing is hardcoded, the fact that from 32 digits onwards, all armstrong numbers have the digits 0 to 9. This is handled by the uses of the variable `B` in the code. It's speed goes down significantly as the number of combinations reduces a lot.

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


title: Fast Topswops calculation

text:
# Question
Title: Fast Topswops calculation
From AZSPCS:

*Suppose you have a deck containing n cards. Each card contains a number from 1 to n, and each number appears on exactly one card. You look at the number on the top card -- let's says it's k -- and then reverse the order of the top k cards. You continue this procedure -- reading the top number and then reversing the corresponding number of cards -- until the top card is 1.*

Write the fastest program to compute the number of reversals for a given deck. Note that if you are participating in the contest you are not allowed to post your code (and thus I will not post my code yet).

# Answer
## JavaScript

```
function(d){for(t=0;x=(n=d[0])-1;t++)for(i=0;i<n/2;i++){m=d[x-i];d[x-i]=d[i];d[i]=m}return t}

```

You pass it the deck, like so:

```
f([3, 2, 1]) // 1
f([2, 3, 1]) // 2
f([1, 2, 3]) // 0

```
> 5 votes

# Answer
### Scala: (This isn't a golf - is it?)

```
def transform (l: List[Int], sofar: Int = 0) : Int =
  if (l(0) == 1) sofar else transform (l.take (l(0)).reverse ::: l.drop (l(0)), sofar + 1)

```

Complete application with testcase and stopwatch, including the shuffling of the Deck:

```
object DeckReverse extends Application {

  def transform (l: List[Int], sofar: Int = 0) : Int =
    if (l(0) == 1) sofar else transform (l.take (l(0)).reverse ::: l.drop (l(0)), sofar + 1)

  def stopwatch (count: Int, size: Int) = {
    val li = (1 until size).toList
    val r = util.Random

    val start = System.currentTimeMillis ()
    (0 until count).foreach (_ => transform (r.shuffle (li)))
    val stop = System.currentTimeMillis ()

    println ("count: " + count + "\tsize: " + size + "\tduration: " + (stop - start) + " msecs")
  }

  stopwatch (1000, 100)
}

```

count: 1000 size: 100 duration: 1614 msecs machine: Single Pentium M 2Ghz
> 3 votes

# Answer
# Python, 84 Chars

Golfing anyway... I'm using the numbers 0 through n-1. Assuming the array is stored in a variable x, it takes me 84 chars of Python.

```
while x[0]:x[:x[0]+1]=x[x[0]::-1]

```

However, performance is pretty bad due to memory abuse.
> 3 votes

# Answer
# Perl 5, 58 + 2 (-ap) = 60 bytes

```
++$\&&(@F[0..$F[0]-1]=reverse@F[0..$F[0]-1])while$F[0]-1}{

```

Try it online!
> 1 votes

# Answer
### C

```
int revno(int* deck, int n) {
  int k,j,r=0;
  for(;;) {
    k=*deck;
    if (k==1) {
      return r;
    }
    for (j=0; j<k/2; j++) {
      int tmp=deck[j];
      deck[j]=deck[k-j];
      deck[k-j]=tmp;
    }
    r++;
  }
}

```

`deck` is a pointer to an integer array representing the decks. `n` is the number of the cards. Obviously memory safety is the task of the caller.

It is probably nearing the fastest algorithm on recent computers and on a high-level language. Only with asm-level tricks could it be made faster, but not heavily even with them.
> 0 votes

---
Tags: fastest-code
---


title: Solve this Alcazar for me

text:
# Question
Title: Solve this Alcazar for me
Recently I've been playing a game called Alcazar. It is a board puzzle game where your goal is to enter from one door, pass through all squares, and exit through another door. The only rules are:

* Enter once, leave once;
* Pass through all squares;
* Do not pass through a square more than once

The image below shows an example of an Alcazar board and, at its right, the solved puzzle (of course this is an easy one):

You can find more puzzles at http://www.theincrediblecompany.com/try-alcazar and download the game at PlayStore (P.S.: Not an advertisement).

My problem is that I almost finished the game, except for one level. I simply cannot find a way to solve it. So the challenge I propose is: create an algorithm that solves any normal1 solvable2 Alcazar level.

Of course, I'm not asking for anyone to build an image interpreter to read the image and solve the puzzle (or am I?). So I redrew the above puzzle using box drawing characters. The puzzle and its solution would be like this:

```
╔═══════╗         ╔═══════╗
║▒ ▒ ▒ ▒║         ║┌─┐ ┌─┐║
║     ║ ║         ║│ │ │║│║
╣▒ ▒ ▒║▒╠         ╣│ └─┘║└╠
║ ══╦═╩═╣         ║│══╦═╩═╣
║▒ ▒║▒ ▒║         ║└─┐║┌─┐║
║   ║   ║   ==>   ║  │║│ │║
╣▒ ▒║▒ ▒║         ╣┐ │║│ │║
║ ║ ║   ║         ║│║│║│ │║
╣▒║▒ ▒ ▒║         ╣│║└─┘ │║
║ ║     ║         ║│║    │║
║▒ ▒ ▒ ▒║         ║└─────┘║
╚═══════╝         ╚═══════╝

```

In the board above,  are the cells to be filled.

One can observe that there is a vertical and horizontal gab between the cells. This is because I had to insert a space between cells to add the walls. This means that the only important cells are the ones above, below, to the left, and to the right of each cell. The diagonals could be removed without information loss. For example, in the board below, both represent the same puzzle:

```
╔════╩╗         ═ ═ ╩
║▒ ▒ ▒║        ║▒ ▒ ▒║
║ ═══ ║           ═
║▒ ▒ ▒║   ==   ║▒ ▒ ▒║
║     ║
║▒ ▒ ▒║        ║▒ ▒ ▒║
╚╦════╝         ╦═ ══

```

This is also valid for the solutions. That is, it is not required to connect the cells:

```
╔════╩╗        ╔════╩╗        ╔════╩╗
║▒ ▒ ▒║        ║┌───┘║        ║┌ ─ ┘║
║ ═══ ║        ║│═══ ║        ║ ═══ ║
║▒ ▒ ▒║   ==   ║└───┐║   =>   ║└ ─ ┐║
║     ║        ║    │║        ║     ║
║▒ ▒ ▒║        ║┌───┘║        ║┌ ─ ┘║
╚╦════╝        ╚╦════╝        ╚╦════╝

```

In the example above, both solutions mean the same.

Yes, the test cases. Here they are:

### Puzzle 1

```
╔════╩╗        ╔════╩╗
║▒ ▒ ▒║        ║┌ ─ ┘║
║ ═══ ║        ║ ═══ ║
║▒ ▒ ▒║   =>   ║└ ─ ┐║
║     ║        ║     ║
║▒ ▒ ▒║        ║┌ ─ ┘║
╚╦════╝        ╚╦════╝

```

### Puzzle 2

```
╔═════╗        ╔═════╗
║▒ ▒ ▒║        ║┌ ─ ┐║
║   ║ ║        ║   ║ ║
╣▒ ▒║▒║        ╣└ ┐║│║
║ ║ ║ ║   =>   ║ ║ ║ ║
╣▒║▒ ▒╠        ╣┐║│ │╠
║ ║   ║        ║ ║   ║
║▒ ▒ ▒║        ║└ ┘ │║
╚════╦╝        ╚════╦╝

```

### Puzzle 3

```
╔════╩══╗        ╔════╩══╗
║▒ ▒ ▒ ▒║        ║┌ ┐ └ ┐║
║ ║   ║ ║        ║ ║   ║ ║
╣▒║▒ ▒║▒╠        ╣┘║└ ┐║│╠
║ ╚══ ║ ║        ║ ╚══ ║ ║
║▒ ▒ ▒ ▒╠   =>   ║┌ ─ ┘ │╠
║   ═══ ║        ║   ═══ ║
║▒ ▒ ▒ ▒║        ║│ ┌ ┐ │║
║   ║   ║        ║   ║   ║
║▒ ▒║▒ ▒║        ║└ ┘║└ ┘║
╚═══╩═══╝        ╚═══╩═══╝

```

### puzzle 4

```
╔═══════╗        ╔═══════╗
║▒ ▒ ▒ ▒║        ║┌ ┐ ┌ ┐║
║     ║ ║        ║     ║ ║
╣▒ ▒ ▒║▒╠        ╣│ └ ┘║└╠
║ ══╦═╩═╣        ║ ══╦═╩═╣
║▒ ▒║▒ ▒║        ║└ ┐║┌ ┐║
║   ║   ║   =>   ║   ║   ║
╣▒ ▒║▒ ▒║        ╣┐ │║│ │║
║ ║ ║   ║        ║ ║ ║   ║
╣▒║▒ ▒ ▒║        ╣│║└ ┘ │║
║ ║     ║        ║ ║     ║
║▒ ▒ ▒ ▒║        ║└ ─ ─ ┘║
╚═══════╝        ╚═══════╝

```

### Puzzle 5

```
╔══╩══════╗        ╔══╩══════╗
║▒ ▒ ▒ ▒ ▒║        ║┌ ─ ┐ ┌ ┐║
║   ║     ║        ║   ║     ║
║▒ ▒║▒ ▒ ▒╠        ║└ ┐║└ ┘ │╠
║   ╠════ ║        ║   ╠════ ║
║▒ ▒║▒ ▒ ▒║   =>   ║┌ ┘║┌ ─ ┘║
║   ║     ║        ║   ║     ║
║▒ ▒║▒ ▒ ▒╠        ║└ ┐║└ ─ ─╠
║   ╠═════╣        ║   ╠═════╣
║▒ ▒║▒ ▒ ▒║        ║┌ ┘║┌ ─ ┐║
║   ║     ║        ║   ║     ║
║▒ ▒ ▒ ▒ ▒║        ║└ ─ ┘ ┌ ┘║
╚══╦═══╦══╝        ╚══╦═══╦══╝

```

### Puzzle 6

```
╔═══════════╗        ╔═══════════╗
║▒ ▒ ▒ ▒ ▒ ▒║        ║┌ ┐ ┌ ┐ ┌ ┐║
║           ║        ║           ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║│ └ ┘ └ ┘ │║
║       ═══ ║        ║       ═══ ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║└ ┐ ┌ ─ ─ ┘║
║     ═══   ║        ║     ═══   ║
╣▒ ▒ ▒ ▒ ▒ ▒╠   =>   ╣┐ │ │ ┌ ┐ ┌╠
║           ║        ║           ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║│ │ │ │ │ │║
║   ║   ║   ║        ║   ║   ║   ║
║▒ ▒║▒ ▒║▒ ▒║        ║│ │║│ │║│ │║
║   ║   ║   ║        ║   ║   ║   ║
║▒ ▒ ▒ ▒ ▒ ▒║        ║└ ┘ └ ┘ └ ┘║
╚═══════════╝        ╚═══════════╝

```

### Puzzle 7

```
╔════╩════════╦╩╗        ╔════╩════════╦╩╗
║▒ ▒ ▒ ▒ ▒ ▒ ▒║▒║        ║┌ ─ ─ ─ ─ ─ ┐║│║
║ ║       ║   ║ ║        ║ ║       ║   ║ ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║        ║│║┌ ─ ─ ┐║┌ ┘ │║
║ ║ ║ ═══ ║     ║        ║ ║ ║ ═══ ║     ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠        ║│ │║┌ ─ ┘ └ ┐ │╠
║   ║           ║        ║   ║           ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║│ │ └ ┐ ┌ ┐ └ ┘║
║     ║ ║     ══╣        ║     ║ ║     ══╣
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║        ║│ └ ┐║│║│ └ ─ ┐║
║     ║ ║       ║        ║     ║ ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║│ ┌ ┘ │ └ ┐ ┌ ┘║
║           ║ ══╣   =>   ║           ║ ══╣
║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║        ║└ ┘ ┌ ┘ ┌ ┘║└ ┐║
╠══       ║ ╚══ ║        ╠══       ║ ╚══ ║
║▒ ▒ ▒ ▒ ▒║▒ ▒ ▒║        ║┌ ┐ └ ┐ │║┌ ─ ┘║
║     ║ ║ ║     ║        ║     ║ ║ ║     ║
║▒ ▒ ▒║▒║▒ ▒ ▒ ▒║        ║│ └ ┐║│║│ └ ─ ┐║
║ ║   ║ ║ ╔══   ║        ║ ║   ║ ║ ╔══   ║
║▒║▒ ▒ ▒ ▒║▒ ▒ ▒║        ║│║┌ ┘ │ │║┌ ┐ │║
║ ║     ║ ║     ║        ║ ║     ║ ║     ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║        ║│ └ ─ ┘║└ ┘ │ │║
║       ╚══     ║        ║       ╚══     ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║        ║└ ─ ─ ─ ─ ─ ┘ │║
╚════╦═╦═╦═════╦╝        ╚════╦═╦═╦═════╦╝

```

### Puzzle 8 (Sorry, I really don't have the solution to this one)

```
╔══╩╦══╩═══╩═╩═╩═══╩╗
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║   ║               ║
╣▒ ▒║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
║   ╚══ ╔══     ╔═══╣
╣▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒╠
║       ║   ╔══ ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║           ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒╠
║           ║       ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
║   ╔═══╗   ╚══     ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║
║   ║   ║           ║
╣▒ ▒║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒╠
║ ══╝   ║       ╔══ ║
║▒ ▒ ▒ ▒║▒ ▒ ▒ ▒║▒ ▒║
║   ══╗ ╚══ ╔══ ║   ║
╣▒ ▒ ▒║▒ ▒ ▒║▒ ▒ ▒ ▒╠
║     ║     ║   ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║▒ ▒║
║   ═══   ══╗   ║   ║
╣▒ ▒ ▒ ▒ ▒ ▒║▒ ▒ ▒ ▒╠
╠══ ║       ║   ╔══ ║
║▒ ▒║▒ ▒ ▒ ▒ ▒ ▒║▒ ▒╠
║   ╚══ ║   ║   ║   ║
╣▒ ▒ ▒ ▒║▒ ▒║▒ ▒ ▒ ▒╠
║       ║   ║       ║
║▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒ ▒║
╚══╦═══╦═══╦═╦═╦═╦═╦╝

```

### Input

The input of your code can have any representation as long as it follow these rules:

1. It must be a graphical input. So it is not possible to read a coordinate list, for example.
2. Horizontal walls, vertical walls, and doors must be distinct, and they must be made of a visible character (no blank characters).
3. The  can be replaced by blanks. I just used a different character to highlight them.

### Output

The output can also have any representation as long as it follows these rules:

1. It must be a graphical output. That is, one can see the path by looking at it.
2. Rule number one implies that the path characters be different. That is, there are going to be at least 6 path characters; horizontal, vertical, and corners.
3. For the answer to be valid, the output must be the same board as the input (obviously) with all the cells (in my representation, the ) filled. Filling the gaps between the cells is optional.

## Scoring

This is , so the shortest code in bytes wins.

1 There are some Alcazar levels that have optional cells and tunnels. These will not be considered.

2 There are some Alcazar boards that are impossible.

# Answer
# Python 3, 809 728 723 714 693 688 684 663 657 641 639 627 610 571 569 bytes

**Edit:** Saved 55 bytes thanks to @Felipe Nardi Batista

Does not run the last test case in 60 seconds on TIO, but should work correctly nonetheless. Returns a list of coordinates for the path. Some 400 of the bytes are used to get the data lists from the I/O.

```
A=enumerate
I,J="═║"
B=range
L=len
K=-1
Z=1,0
X=0,1
C=K,0
V=0,K
E=lambda a,b,p:(((a,b)in d)*L(p)==H*h)*p or max([E(q+a,w+b,p+[(q+a,w+b)])for q,w in y[a][b]if~-((q+a,w+b)in p)*-h>w+b>K<q+a<H]+[[]])
x=input().split("\n")
h=L(x[0])//2
H=L(x)//2
y=[[{C,Z,V,X}for i in B(h)]for j in B(H)]
d=[]
exec('d+=[(%s,i)for i,a in A(x[%s][1::2])if I<a]\nfor i,u in A(x[%s:%s:2]):\n d+=[(i,0)]*(J<u[0])+[(i,h-1)]*(J<u[K])\n for j,w in A(u[%s:%s:2]):\n  if"%s"==w:y[i][j]-={%s};y[i+%s][j+%s]-={%s}\n'*2%(0,*X,"",2,K,J,X,*X,V,H-1,K,2,K,1,"",I,Z,*Z,C))
print(max(E(*D,[D])for D in d))

```

Try it online!
> 5 votes

# Answer
# APL (Dyalog Classic), 319 bytes

```
i←N⍴j←⍳1+n←×/N←⌊2÷⍨⍴a←⎕⋄e←↑⊃,/{(,~'#='∊⍨a[(⍵⌽⍳2)∘+¨2×⍳N+⍵=⍳2])/,2,/[⍵]⊃,[⍵]/n i n}¨⍳2
r←{e g c←⍵⋄d←+/j∘.=∊g⋄e⌿⍨←(≠/c[e])∧2>⌈/d[e]⋄n≡≢g:g⍪j/⍨d=1⋄0≡≢e:0⋄2>⌊/d+D←+/j∘.=,e:0⋄u←,¯1↑e←e[⍒⌊/D[e];]⋄e↓⍨←¯1⋄0≢r←∇e(g⍪u)(c-(-/c[u])×c=c[⊃u]):r⋄∇e g c}e(0↑e)j
a[1+2×⍳N]←' ??┌?─┐┬?└│├┘┴┤┼'[2⊥(↑(⊂i),¨¨{⊖∘⍉⍣⍵⊢n⍪¯1↓⌽∘⍉⍣⍵⊢i}¨⍳4)∊↓r⍪⌽r]
a

```

Try it online!

Input uses `=#F7LJ<>^v.` instead of `═║╔╗╚╝╣╠╩╦▒` in order to fit in the classic charset.

All test cases except for the last one pass in a few seconds.

The last test takes 47 min on my computer and yields no solution.

When the resulting path uses a door near a corner it may be rendered incorrectly (it's as if the trail forks and passes through an extra imaginary door), but it's still discernable and unambiguous.
> 5 votes

# Answer
# JavaScript (ES6), 274 bytes

Input as a multiline string, each line terminated with a newline character. The doors are marked with character '2'

Output as a multiline string with the path marked by character '1', very easily discernable.

This is a *Depth First Search*, trying all paths and backtraking when stuck. It's not efficient at all, but can solve puzzles 1 .. 6 in a less than 1 minute.

```
z=>(w=z.search`
`+1,t=(w-2)*(z.length/w-1)/4,z=[...z],R=(p,l,q)=>[1,-1,w,-w].some(d=>l<t?z[q=p+d]<1&z[q+d]<1&&(R(q+d,++z[q]+l)||--z[q]):z[p+d]>1&&--z[p+d],++z[p])||--z[p],z.some((c,i)=>-c&&(x=i%w,R(i<w?i+w:x?x>w-3?i-1:i-w:i+1,--z[i])||++z[i]*0))&&z.join``.replace(/0/g,' '))

```

*Less golfed*

```
z => (
  w = z.search`\n`+1, // board width and offset to next row
  t = (w-2)*(z.length/w-1)/4, // total size of board, number of cells that must be filled
  z = [...z], // convert string to array
  d = [1, -1, w, -w], // delta to next position in all directions
  // recursive search
  // given a current position, try to move in all directions
  // if the board is not full, look for an emoty cell
  // if the board is full, look for a door
  R = (p, // current position
       l, // fill level
       q  // parameter used as a local variable
      ) => (
        ++z[p], // mark current position
        // .some will terminate early if the called function returns true
        // in case of return true the recursive function returns all way up leaving the path marked
        // in case of return false we need to unmark path and backtrack
        d.some( d => // for each direction, offset in d
          l < t // check if board is full
          ? z[q=p+d] < 1 & z[q+d] < 1 // not full, try to advance
            && (++z[q], // mark intermediate cell
                R(q+d, 1+l) // recursive call incrementing fill level
                || --z[q] // if R return false, backtrack: unmark intermediate cell
               )
          : z[p+d] > 1 && --z[p+d]
        ) // full, ok only if I find a door nearby
        || --z[p], // if some returns false, unmark and backtrak
  // look for doors and for each door call R
  // when R returns true, stop and return the marked board
  // if R returns false for each door, no solution, return false
  z.some((c,i) =>
   -c && // if numeric and != 0
    (x = i%w,
     z[i]=1, // marking starting position (door)
     R(i<w ? i+w : x ? x > w-3 ? i-1 : i-w : i+1, 1)
     || (z[i] = 2, false) // if R returned false, unmark a return false
    )
  ) && z.join``.replace(/0/g,' ')
)

```

Inside the test snippet there is a solution using a DFS with some constraint that solves puzzle 7 in less than a minute (on my PC). Puzzle 8 has no solution. Constraints:

* All empty cells must be reachable from the current cell - the empty space must not be split in two parts
* There must be a reachable door
* A configuration of cells cannot be explored more than one time
* Cannot skip a cell that has only one empty adjacent cell

**Test**

Beware, puzzle 7 is well beyond the timeout for javascript execution in any browser (using the Short and Slow solver)

```
var Short=
z=>(w=z.search`
`+1,t=(w-2)*(z.length/w-1)/4,z=[...z],R=(p,l,q)=>[1,-1,w,-w].some(d=>l<t?z[q=p+d]<1&z[q+d]<1&&(R(q+d,++z[q]+l)||--z[q]):z[p+d]>1&&--z[p+d],++z[p])||--z[p],z.some((c,i)=>-c&&(x=i%w,R(i<w?i+w:x?x>w-3?i-1:i-w:i+1,--z[i])||++z[i]*0))&&z.join``.replace(/0/g,' '))

var Fast=
b=>{
N=0
console.clear()
    F=(b,p,n) => D.reduce((n,d) => b[p+d] < 1 && b[p+d+d] < 1? F(b, p+d+d, n) : n, n+1, b[p]=1)
    A=(s, f, o, q, k)=>{
        D.map(d => b[s[1] + d] == 2 && (++o, q = s[1] + d));

        ++b[s[0]];
        if (++f < t)
        {
            if (o < m && !K[k=b.reduce((k,c,i)=>c>3?k+' '+i:k,s[1])] && F(b.slice(), s[K[k] = 1], f) >= t
                && R(D.reduce((n,d) =>(b[s[1] + d] == 0 && b[s[1] + d + d ] == 0 && n.push([s[1] + d, s[1] + d + d ]),n),[]),f,o,b[s[1]]=4))
                return 1;
        }
        else
        {
            b[s[1]] = 4;
            if (q) return b[q]++;
        }
        --b[s[0]]
        b[s[1]]=0
    }

    R=(s, f, o)=>{
        if (!s[1]) return A(s[0], f, o);
        var e, n, z=[];
        if (s.some(s =>(
                n = D.reduce( (n,d) => b[s[1]+d]>1 || (b[s[1]+d]<1 && b[s[1]+d+d]<1) ? n+1 : n, 0),
                n>2 ? !z.push(s)
                : n>1 ? !z.unshift(s)
                : n>0 && (e||(e=s,0))
        ))) return 0
        if (e) return A(e, f, o);
        return z.some(s => A(s, f, o))
    }

    w = b.search`\n` + 1;
    h = b.length / w;
    t = (w - 2) * (h - 1) / 4;
    D = [ 1, -1, w, -w ];
    b = [...b];
    K = {};
    s = [];
    b.forEach( (c,i) => -c ?
        m = s.push( [i,i < w ? i + w : (x = i % w) > w - 3 ? i - 1 : x ? i - w : i + 1]):0
    )
    R(s, 0, 0);
    return b.join``.replace(/\d/g, c => ' oXOo'[c])
}

Out=(e,s)=>e.textContent = s

function Test(num)
{
  var puzzle = document.getElementById('Z'+num).textContent;
  var solver = MF.checked ? Fast : Short
  Out(S,'...wait...')
  Out(T,'');

  var t0=performance.now()
  setTimeout(_=>(
    Out(S,solver(puzzle)),Out(T,((performance.now()-t0)/1000).toFixed(3)+' sec')
  ),10)
}
```

```
td { border: 1px solid #000; font-family: helvetica; font-size:12px; vertical-align: top; }
pre { line-height: 13px; }
```

```
Short and slow <input type='radio' value='S' name='M' id='MS'>
Long and faster <input type='radio' checked value='F'name ='M' id='MF'>
<table >
<tr>
<td id=T>Solution</td>
<td>Puzzle 1<input type='radio' name='T' onclick="Test(1)"></td>
<td>Puzzle 2<input type='radio' name='T' onclick="Test(2)"></td>
<td>Puzzle 3<input type='radio' name='T' onclick="Test(3)"></td>
<td>Puzzle 4<input type='radio' name='T' onclick="Test(4)"></td>
<td>Puzzle 5<input type='radio' name='T' onclick="Test(5)"></td>
<td>Puzzle 6<input type='radio' name='T' onclick="Test(6)"></td>
<td>Puzzle 7<input type='radio' name='T' onclick="Test(7)"></td>
</tr>
<tr>
<td><pre id=S></pre></td>
<td><pre id='Z1'>╔════2╗
║     ║
║ ═══ ║
║     ║
║     ║
║     ║
╚2════╝
</pre></td>
<td><pre id='Z2'>╔═════╗
║     ║
║   ║ ║
2   ║ ║
║ ║ ║ ║
2 ║   2
║ ║   ║
║     ║
╚════2╝
</pre></td>
<td><pre id='Z3'>╔════2══╗
║       ║
║ ║   ║ ║
2 ║   ║ 2
║ ╚══ ║ ║
║       2
║   ═══ ║
║       ║
║   ║   ║
║   ║   ║
╚═══╩═══╝
</pre></td>
<td><pre id='Z4'>╔═══════╗
║       ║
║     ║ ║
2     ║ 2
║ ══╦═╩═╣
║   ║   ║
║   ║   ║
2   ║   ║
║ ║ ║   ║
2 ║     ║
║ ║     ║
║       ║
╚═══════╝
</pre></td>
<td><pre id='Z5'>╔══2══════╗
║         ║
║   ║     ║
║   ║     2
║   ╠════ ║
║   ║     ║
║   ║     ║
║   ║     2
║   ╠═════╣
║   ║     ║
║   ║     ║
║         ║
╚══2═══2══╝
</pre></td>
<td><pre id='Z6'>╔═══════════╗
║           ║
║           ║
║           ║
║       ═══ ║
║           ║
║     ═══   ║
2           2
║           ║
║           ║
║   ║   ║   ║
║   ║   ║   ║
║   ║   ║   ║
║           ║
╚═══════════╝
</pre></td>
<td><pre id='Z7'>╔════2════════╦2╗
║             ║ ║
║ ║       ║   ║ ║
║ ║       ║     ║
║ ║ ║ ═══ ║     ║
║   ║           2
║   ║           ║
║               ║
║     ║ ║     ══╣
║     ║ ║       ║
║     ║ ║       ║
║               ║
║           ║ ══╣
║           ║   ║
╠══       ║ ╚══ ║
║         ║     ║
║     ║ ║ ║     ║
║     ║ ║       ║
║ ║   ║ ║ ╔══   ║
║ ║       ║     ║
║ ║     ║ ║     ║
║       ║       ║
║       ╚══     ║
║               ║
╚════2═2═2═════2╝
</pre></td>
</tr>
</table>
```
> 3 votes

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


title: Sort band names

text:
# Question
Title: Sort band names
# Challenge description

You have a music library with many tracks recorded by many bands, each of which has a name, like `Queen`, `Aerosmith`, `Sunny Day Real Estate`, `The Strokes` . When an audio player displays your library alphabetically by band name, it usually skips the `The` part, as many band names start with `The`, making it easier to navigate through your media collection. In this challenge, given a list (array) of strings, you need to sort it that way (that is, omitting the `The` word at the beginning of the name). You can either write a method or a full working program.

# Sample inputs / outputs

```
[Queen, Aerosmith, Sunny Day Real Estate, The Strokes] -> [Aerosmith, Queen, The Strokes, Sunny Day Real Estate]
[The Ramones, The Cure, The Pixies, The Roots, The Animals, Enrique Iglesias] -> [The Animals, The Cure, Enrique Iglesias, The Pixies, The Ramones, The Roots]
[The The, The They, Thermodynamics] -> [The The, Thermodynamics, The They]

```

# Notes / Edge cases

* Sorting lexicographically is case insensitive, so `The Police`, `The police` and `the police` are all equivalent,
* Your algorithm should only omit the first `the` word, so bands named `The The` or `The The Band` are sorted normally by the second `the`,
* A band named `The` (a three letter word) is sorted normally (no skipping),
* Order of two bands having the same name, one of which starts with `the` (like `The Police` and `Police`) is undefined,
* You can assume that if a band's name consists of more than one word, they are separated by a single space character. You don't need to handle leading or trailing whitespaces,
* All input strings match `[A-Za-z0-9 ]*`, that is they will consist only of lower- and uppercase letters of English alphabet, digits and space characters,
* Remember that this is a challenge, so make your code as short as possible!

# Answer
> 7 votes
## Python, ~~56~~ ~~62~~ 64 bytes

```
lambda b:sorted(b,key=lambda x:(x,x[4:])[x.lower()[:4]=='the '])

```

Try it

Thanks to @Chris H for pointing out that `lstrip()` was not handling `The The` correctly, since the strip was blasting all matching characters and sorting it as a blank string, and @manatwork for finding the flaw in using `replace()`. The new version should work.

Old version:

```
lambda b:sorted(b,key=lambda x:x.lower().lstrip('the '))

```

# Answer
> 5 votes
# , ~~32~~ 28 bytes

```
ç^The /dwA_
:sort
ç_/$xIThe

```

Try it online!

*Note to self: Make an abbreviation for `:sort` so that I don't need 6 whole bytes for a single command!*

Explanation:

```
ç^The /     "On every line starting with 'The ',
       dw   "Delete a word
         A_ "And (A)ppend an underscore '_'

:sort       "Sort all lines alphabetically

ç_/         "On every line containing an underscore,
   $x       "Delete the last character
     IThe   "And prepened 'The '

```

# Answer
> 4 votes
## Retina, 34 bytes

The trailing linefeed is significant.

```
%`^
$';
T`L`l`.+;
m`^the

O`
.+;

```

I/O is one band per line.

Try it online!

### Explanation

```
%`^
$';

```

Duplicate each line, using `;` as a separator.

```
T`L`l`.+;

```

Turn everything in front of a `;` to lower case.

```
m`^the

```

Remove any `the`s that appear at the beginning of a line.

```
O`

```

Sort the lines.

```
.+;

```

Remove the beginnings of the lines which we used for sorting.

# Answer
> 4 votes
## Pyke, 16 bytes

```
.#l1D"the ".^4*>

```

Try it here!

```
.#                - sort_by(V, input)
  l1              -  i = i.lower()
      "the ".^    -   i.startswith("the ")
              I   -  if ^:
               4> -   i[4:]

```

# Answer
> 3 votes
# Perl, 52 bytes

*-13 byte thanks to @manatwork*
*-1 byte thanks to @msh210*

```
sub f{lc pop=~s/^the //ri}print sort{f($a)cmp f$b}<>

```

One band per line as input, and so is the output.

The implementation is quite straight forward : the program prints the list of bands, sorted with the help of a custom function (`f`) which returns the lower case band name without the eventual leading `the` .

# Answer
> 2 votes
# Python, ~~66~~ ~~72~~ 69 bytes

```
lambda x:sorted(x,key=lambda a:a[4*(a.lower()[:4]=='the '):].lower())

```

Uses Python's `sorted` method with the `key` keyword argument to sort by the name minus "The". This is a lambda; to call it, give it a name by putting `f=` in front.

Now with extra case insensitivity!

# Answer
> 2 votes
## PowerShell v2+, ~~33~~ ~~32~~ 29 bytes

```
$args|sort{$_-replace'^the '}

```

*Saved 3 bytes thanks to @MathiasRJessen*

Input is via command-line arguments. Sorts the original names based on the results of the script block `{...}` that performs a regex `-replace` to strip out the leading (case-insensitive) `"the "`.

### Examples

```
PS C:\Tools\Scripts\golfing> .\sort-band-names.ps1 'the Ramones' 'The cure' 'The Pixies' 'The Roots' 'the Animals' 'Enrique Iglesias'
the Animals
The cure
Enrique Iglesias
The Pixies
the Ramones
The Roots

PS C:\Tools\Scripts\golfing> .\sort-band-names.ps1 'The The' 'The They' 'Thermodynamics'
The The
Thermodynamics
The They

PS C:\Tools\Scripts\golfing> .\sort-band-names.ps1 'THE STOOGES' 'The Strokes' 'The The' 'the they' 'the band' 'STP'
the band
THE STOOGES
STP
The Strokes
The The
the they

```

# Answer
> 2 votes
# JavaScript/ECMAScript 6 ~~93~~ 70 bytes

**70** *Thanks to Neil and Downgoat for advice*

```
B=>B.sort((a,b)=>R(a).localeCompare(R(b)),R=s=>s.replace(/^the /i,''))

```

*Readable Version for the 70-byte variant*

```
let sortBandNames = (bandNames) => {
    let stripThe = (name) => name.replace(/^the /i, '');
    let compareFunc = (a, b) => stripThe(a).localeCompare(stripThe(b));
    return bandNames.sort(compareFunc)
};

```

**93**

```
f=B=>{R=s=>s.toLowerCase().replace(/the /,'');return B.sort((a,b)=>R(a).localeCompare(R(b)))}

```

*Readable Version for the 93-byte variant*

```
let sortBandNames = (bandNames) => {
    let stripThe = (name) => name.toLowerCase().replace(/the /, '');
    let compareFunc = (a, b) => stripThe(a).localeCompare(stripThe(b));
    return bandNames.sort(compareFunc)
};

```

# Answer
> 2 votes
# Ruby, 42 bytes

```
->a{a.sort_by{|s|s.upcase.sub /^THE /,''}}

```

Try it online!

# Answer
> 2 votes
# Perl 6, 26 bytes

```
*.sort({fc S:i/^'the '//})

```

### Explanation:

```
# ｢*｣ is the input to this Whatever lambda
*.sort(

  # sort based on the return value of this Block lambda
  {
    fc # foldcase the following

    # string replace but not in-place
    S
      :ignorecase
      /
        # at the start of the string
        ^

        # match ｢the ｣
        'the '

      # replace with nothing
      //
  }
)

```

### Test:

```
use v6.c;
use Test;

my @tests = (
  « Queen Aerosmith 'Sunny Day Real Estate' 'The Strokes' »
    => « Aerosmith Queen 'The Strokes' 'Sunny Day Real Estate' »,
  « 'The Ramones' 'The Cure' 'The Pixies' 'The Roots' 'The Animals' 'Enrique Iglesias' »
    => « 'The Animals' 'The Cure' 'Enrique Iglesias' 'The Pixies' 'The Ramones' 'The Roots' »,
  « 'The The' 'The They' Thermodynamics »
    => « 'The The' Thermodynamics 'The They' »,
);

# give it a lexical name for clarity
my &band-sort = *.sort({fc S:i/^'the '//});

plan +@tests;

for @tests -> ( :key(@input), :value(@expected) ) {
  is-deeply band-sort(@input), @expected, @expected.perl;
}

```

```
1..3
ok 1 - ("Aerosmith", "Queen", "The Strokes", "Sunny Day Real Estate")
ok 2 - ("The Animals", "The Cure", "Enrique Iglesias", "The Pixies", "The Ramones", "The Roots")
ok 3 - ("The The", "Thermodynamics", "The They")

```

# Answer
> 1 votes
## Java 8, 178 bytes

```
void q(String[]s){java.util.Arrays.sort(s,(a,b)->(a.toLowerCase().startsWith("the ")?a.substring(4):a).compareToIgnoreCase(b.toLowerCase().startsWith("the ")?b.substring(4):b));}

```

Ungolfed version:

```
void sort(String[] bands) {
    java.util.Arrays.sort(bands, (a, b) ->
        (a.toLowerCase().startsWith("the ") ? a.substring(4) : a).compareToIgnoreCase(
            b.toLowerCase().startsWith("the ") ? b.substring(4) : b
        )
    );
}

```

Call as such:

```
public static void main(String[] args) {
    String[] bands = {"The Strokes", "Queen", "AC/DC", "The Band", "Cage the Elephant", "cage the elephant"};
    sort(bands); // or q(bands) in the golfed version
    System.out.println(java.util.Arrays.toString(bands));
}

```

# Answer
> 1 votes
## Bash + coreutils, 44 bytes

```
sed '/^the /I!s,^,@ ,'|sort -dk2|sed s,@\ ,,

```

**Explanation:** the input and output format is one band per line

```
sed '/^the /I!s,^,@ ,'   # prepend '@ ' to each line not starting with 'the ', case
                         #insensitive. This adds a temporary field needed by sort.
sort -dk2                # sort in ascending dictionary order by 2nd field onward
sed s,@\ ,,              # remove the temporary field

```

**Test run (using a here-document with EOF as the end marker):**

```
./sort_bands.sh << EOF
> Queen
> Aerosmith
> Sunny Day Real Estate
> The Strokes
> EOF

```

**Output:**

```
Aerosmith
Queen
The Strokes
Sunny Day Real Estate

```

# Answer
> 1 votes
# Vim, 18 bytes

Well now that I realized this is possible, I'm kinda embarrassed by my 26 byte V answer, especially since V is supposed to be shorter than vim. But this is pretty much a builtin.

```
:sor i/\(The \)*/<CR>

```

Explanation (straight from vim help):

```
                            *:sor* *:sort*
:[range]sor[t][!] [b][f][i][n][o][r][u][x] [/{pattern}/]
            Sort lines in [range].  When no range is given all
            lines are sorted.

            With [i] case is ignored.

            When /{pattern}/ is specified and there is no [r] flag
            the text matched with {pattern} is skipped, so that
            you sort on what comes after the match.
            Instead of the slash any non-letter can be used.

```

# Answer
> 1 votes
# C, ~~216~~ ~~212~~ 135 + 5 (`qsort`) = ~~221~~ ~~217~~ 140 bytes

```
M(void*a,void*b){char*A,*B;A=*(char**)a;B=*(char**)b;A=strcasestr(A,"The ")?A+4:A;B=strcasestr(B,"The ")?B+4:B;return strcasecmp(A,B);}

```

Well, I finally got around to finishing this in `C`. Golfing tips are very much appreciated.

In this submission, `M` is the comparison function to be supplied to `qsort`. Therefore, to invoke this, you must use `qsort` in the format `qsort(argv++,argc--,8,M)` where `argv` contains the command-line arguments and `argc` is the number of arguments provided.

Try It Online!

# Answer
> 0 votes
# Nim, 96 bytes

```
import algorithm,strutils,future
x=>x.sortedByIt toLower it[4*int(it.toLower[0..3]=="the ")..^0]

```

<sup>Those `import`s take up so many bytes `:|`</sup>

A translation of my Python answer.

This is an anonymous procedure; to use it, it must be passed into a testing procedure. Here's a full program you can use for testing:

```
import algorithm,strutils,future
proc test(x: seq[string] -> seq[string]) =
 echo x(@["The The", "The They", "Thermodynamics"]) # Substitute your input here
test(x=>x.sortedByIt toLower it[4*int(it.toLower[0..3]=="the ")..^0])

```

# Answer
> 0 votes
# MATL, 16 bytes

```
tk'^the '[]YX2$S

```

Input format is (each line corresponds to a test case)

```
{'Queen', 'Aerosmith', 'Sunny Day Real Estate', 'The Strokes'}
{'The Ramones', 'The Cure', 'The Pixies', 'The Roots', 'The Animals', 'Enrique Iglesias'}
{'The The', 'The They', 'Thermodynamics'}

```

**Try it online!**

### Explanation

```
t        % Implicitly input cell array of strings. Push another copy
k        % Convert to lowercase
'^the '  % String to be used as regex pattern: matches initial 'the '
[]       % Empty array
YX       % Regex replacement: replace initial 'the ' in each string by empty array
2$S      % Sort input according to the modified cell array. Implicitly display

```

# Answer
> 0 votes
# Haskell, 84 bytes

```
import Data.List
p(t:'h':'e':' ':s)|elem t"Tt"=s
p s=s
sortBy(\a b->p a`compare`p b)

```

Call with

```
sortBy(\a b->p a`compare`p b)["The The", "The They", "Thermodynamics"]

```

Testcase:

```
let s = sortBy(\a b->p a`compare`p b)
and[s["Queen", "Aerosmith", "Sunny Day Real Estate", "The Strokes"]==["Aerosmith", "Queen", "The Strokes", "Sunny Day Real Estate"],s["The Ramones", "The Cure", "The Pixies", "The Roots", "The Animals", "Enrique Iglesias"]==["The Animals", "The Cure", "Enrique Iglesias", "The Pixies", "The Ramones", "The Roots"],s["The The", "The They", "Thermodynamics"]==["The The", "Thermodynamics", "The They"]]

```

# Answer
> 0 votes
# C#, 139 Bytes

```
using System.Linq;System.Collections.IEnumerable S(string[] l)=> l.OrderBy(b=>(b.ToLower().StartsWith("the ")?b.Substring(4):b).ToLower());

```

Try online!

Without counting the usings the answer would be 102 bytes.

# Answer
> 0 votes
**BASH, 64 Bytes**

```
sed 's/^the / /;s/^The /    /'|sort -fb|sed 's/^ /the /;s/^ /The /'

```

Input: stdin, one band per line. Output: stdout

Note: The second replacements (s/^The/ / and s/^ /The /) use the tab character, so they don't always copy/paste correctly.

# Answer
> 0 votes
# q/kdb+, ~~36~~ 33 bytes

**Solution:**

```
{x(<)@[x;(&)x like"[Tt]he *";4_]}

```

**Example:**

```
q){x(<)@[x;(&)x like"[Tt]he *";4_]}("Queen";"Aerosmith";"Sunny Day Real Estate";"The Strokes";"the Eagles")
"Aerosmith"
"the Eagles"
"Queen"
"The Strokes"
"Sunny Day Real Estate"

```

**Explanation:**

Strip out any "\[Tt\]he " from each input string, sort this list, then sort the original list based on the indexing of the sorted list.

```
{x iasc @[x;where x like "[Tt]he *";4_]} / ungolfed solution
{                                      } / lambda function
        @[x;                       ;  ]  / apply function to x at indices
                                    4_   / 4 drop, remove first 4 items
            where x like "[Tt]he *"      / where the input matches 'The ...' or 'the ...'
   iasc                                  / returns sorted indices
 x                                       / index into original list at these indices

```

# Answer
> 0 votes
# 05AB1E, 27 bytes

```
vyð¡RD¤…TheQsgα£Rðý})‚øí{ø¤

```

Try it online!

### Explanation

```
vyð¡RD¤…TheQsgα£Rðý})‚øí{ø¤   Argument l
v                 }           For each y in l, do:
 yð¡                            Split y on space
    RD                          Reverse and duplicate
      ¤…TheQ                    Last element equals "The" (true = 1, false = 0)
            sgα                 Absolute difference with length of array
               £                Get elements from index 0 to calculated difference
                R               Reverse
                 ðý             Join on space
                    )‚øí      Pair each element with original
                        {ø¤   Sort and get the original band name

```

# Answer
> 0 votes
# Groovy, 34 bytes

```
{it.sort{it.toLowerCase()-'the '}}

```

41% my answer is `.toLowerCase()`, kill me now.

---

# Output

When running...

```
({it.sort{it.toLowerCase()-'the '}})(['The ramones','The Cure','The Pixies','The Roots','The Animals','Enrique Iglesias'])

```

The result is...

`[The Animals, The Cure, Enrique Iglesias, The Pixies, The ramones, The Roots]`

With no debug or error output.

# Answer
> 0 votes
# Japt, ~~11~~ 10 bytes

```
ñ_v r`^e

```

Try it

# Answer
> -2 votes
# Java ~~176~~ 158 bytes

```
public String[]sort(String[]names){
  for(int i=-1;++i<names.length;)
    if(names[i].startsWith("(The |the )"))
      names[i]=names[i].substring(4);
  return Arrays.sort(names,String.CASE_INSENSITIVE_ORDER);
  }

```

Main Function

```
public static void main(String[]args){
  Scanner s = new Scanner(System.in);
  List<String> list= new ArrayList<>();
  while(!(String h = s.nextLine).equalsIgnoreCase("~")){
    list.add(h);
  }
System.out.println(sort(list.toArray(newString[0]))

```

); }

Golfed sort function:

```
String[]s(String[]n){for(int i=-1;++i<n.length;)if(n[i].startsWith("(The |the )"))n[i]=n[i].substring(4);return Arrays.sort(n,String.CASE_INSENSITIVE_ORDER);}

```

> Thanks to @raznagul for saving 18 bytes

---
Tags: code-golf, string, sorting
---