title: Deal an ASCII Deck

text:
# Question
Title: Deal an ASCII Deck
There's never really been a definitive ASCII-cards challenge AFAIK. So, using the following deck of ASCII cards:

```
.------..------..------..------..------..------..------..------..------..------..------..------..------.
|2.--. ||3.--. ||4.--. ||5.--. ||6.--. ||7.--. ||8.--. ||9.--. ||T.--. ||J.--. ||Q.--. ||K.--. ||A.--. |
| (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) || (\/) |
| :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: |
| '--'2|| '--'3|| '--'4|| '--'5|| '--'6|| '--'7|| '--'8|| '--'9|| '--'T|| '--'J|| '--'Q|| '--'K|| '--'A|
'------''------''------''------''------''------''------''------''------''------''------''------''------'
.------..------..------..------..------..------..------..------..------..------..------..------..------.
|2.--. ||3.--. ||4.--. ||5.--. ||6.--. ||7.--. ||8.--. ||9.--. ||T.--. ||J.--. ||Q.--. ||K.--. ||A.--. |
| :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: |
| :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: || :\/: |
| '--'2|| '--'3|| '--'4|| '--'5|| '--'6|| '--'7|| '--'8|| '--'9|| '--'T|| '--'J|| '--'Q|| '--'K|| '--'A|
'------''------''------''------''------''------''------''------''------''------''------''------'
.------..------..------..------..------..------..------..------..------..------..------..------..------.
|2.--. ||3.--. ||4.--. ||5.--. ||6.--. ||7.--. ||8.--. ||9.--. ||T.--. ||J.--. ||Q.--. ||K.--. ||A.--. |
| :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: || :/\: |
| (__) || (__) || (__) || (__) || (__) || (__) || (__) || (__) || (__) || (__) || (__) || (__) || (__) |
| '--'2|| '--'3|| '--'4|| '--'5|| '--'6|| '--'7|| '--'8|| '--'9|| '--'T|| '--'J|| '--'Q|| '--'K|| '--'A|
'------''------''------''------''------''------''------''------''------''------''------''------''------'
.------..------..------..------..------..------..------..------..------..------..------..------..------.
|2.--. ||3.--. ||4.--. ||5.--. ||6.--. ||7.--. ||8.--. ||9.--. ||T.--. ||J.--. ||Q.--. ||K.--. ||A.--. |
| :(): || :(): || :(): || :(): || :(): || :(): || :(): || :(): || :(): || :(): || :(): || :(): || :(): |
| ()() || ()() || ()() || ()() || ()() || ()() || ()() || ()() || ()() || ()() || ()() || ()() || ()() |
| '--'2|| '--'3|| '--'4|| '--'5|| '--'6|| '--'7|| '--'8|| '--'9|| '--'T|| '--'J|| '--'Q|| '--'K|| '--'A|
'------''------''------''------''------''------''------''------''------''------''------''------''------'

```

---

Take two integers, `p` and `q` as input; where `p` is the number of players and `q` is the number of cards each player gets.

* Randomly shuffle the deck of cards (this is ambiguous, but means that all cards must be equally likely to appear anywhere once).
* Deal 1 round of cards per player, outputting `q` rows of `p` cards each row.

# Rules:

* The results should be uniformly random, each card should be equally likely to appear anywhere.
* It is guaranteed that `0 < p*q <= 52 and p < 10`, you may have undefined behavior for scenarios where this is not met.
* You should output `q` rows of cards with `p` cards per row.
* Each column should be separated by  `|`  (a pipe char surrounded by spaces); if you choose a different char than this, explain why. Surrounding spaces here are NOT optional.
* Each row must have 1 or more newlines inbetween them, more than one is acceptable, 0 is not (1 newline meaning the newline there by default).
* Each row should be labeled with the player who owns it in the format "Player N" (0 or 1-indexed is fine).
* No one card may appear more than once.
* `T` is for Ten.

---

# Examples:

**Function(`p=1,q=1`):**

```
Player 1 # Can also be 0.
.------.
|2.--. |
| (\/) |
| :\/: |
| '--'2|
'------'

```

**Function(`p=2,q=1`):**

```
Player 1 | Player 2 # Can also be "Player 0 | Player 1"
.------. | .------.
|2.--. | | |T.--. |
| (\/) | | | (\/) |
| :\/: | | | :\/: |
| '--'2| | | '--'T|
'------' | '------'

```

**Function(`p=2,q=2`):**

```
Player 1 | Player 2 # Can also be "Player 0 | Player 1"
.------. | .------.
|J.--. | | |3.--. |
| (\/) | | | :/\: |
| :\/: | | | :\/: |
| '--'J| | | '--'3|
'------' | '------'
.------. | .------.
|8.--. | | |6.--. |
| :(): | | | :/\: |
| ()() | | | (__) |
| '--'8| | | '--'6|
'------' | '------'

```

---

# Artistic credit to a font on: http://patorjk.com/software/taag

# Answer
# Charcoal, ~~142~~ ~~133~~ 125 bytes

```
ＮθＦＮ«Ｆ¬¬ι«→↑×⁶θ| »Player ＩιＦθ«↙↓.↓⁴←'←⁶↑'↑⁴.Ｐ⁶↓≔‽⁵²εＷ№υε≔‽⁵²ε⊞υε≔§”w↘τ[⁵ＰkxτG”εδδ.--.¶✂”{➙aＥTê；s∨Hμ⁼⎚↑Ｚ～ＳÀd～⌀Ｔê”﹪ε⁴φ⁴'--'δ↘

```

Try it online! Link is to verbose version of code. Edit: Saved 9 bytes by improving my random sampling code. Saved a further 8 bytes by improving my suit printing code. Explanation:

```
Ｎθ

```

Read the number of cards into `q`.

```
ＦＮ«

```

Loop over each player.

```
Ｆ¬¬ι«→↑×⁶θ| »

```

If this is not the first player, print the vertical line between the previous and this player.

```
Player Ｉι

```

Print the player number.

```
Ｆθ«

```

Loop over each card.

```
↙↓.↓⁴←'←⁶↑'↑⁴.Ｐ⁶↓

```

Print the card's edge.

```
≔‽⁵²εＷ№υε≔‽⁵²ε⊞υε

```

Pick a card index that hasn't already been picked, and add it to the list of picked card indices.

```
≔§”w↘τ[⁵ＰkxτG”εδδ

```

Choose and print the card's rank by cyclically indexing into a string of valid card ranks (`2-9, T, J, Q, K, A`).

```
.--.¶

```

Print the top of the suit.

```
✂”{➙aＥTê；s∨Hμ⁼⎚↑Ｚ～ＳÀd～⌀Ｔê”﹪ε⁴φ⁴

```

Print the middle of the suit by slicing into a string. The slice begins at the card index modulo 4 and takes every 4th character until the string runs out (or the `f`=1000th character is reached). Since 4 and 13 are coprime this ensures that all 52 cards are possible.

```
'--'δ↘

```

Print the bottom of the suit and a copy of the rank, and then move to a point that conveniently is not too far away from either the copy of the rank, the start of the next card, or the start of the dividing line for the next player.
> 6 votes

# Answer
# Python 2, 357 bytes

```
from random import*
p,q=input()
A,V=':/\:',':\/:'
c=sample([(""".------.
|%s.--. |
| %s |
| %s |
| '--'%s|
'------'"""%(n,s,t,n)).split('\n')for s,t in('(\/)',V),(A,V),(A,'(__)'),(':():','()()')for n in'123456789TJQKA'],p*q)
print' | '.join('Player '+`i`for i in range(p))
for i in range(0,p*q,p):print'\n'.join(map(' | '.join,zip(c[i:i+p][0],c[i:i+p][1])))

```

Try it online!

I have no friggin' idea.
> 3 votes

# Answer
# Jelly, 126 bytes

```
³‘Ḷj“×ṁẹHY»;⁶¤ṫ5W;
2r9;“TJQKA”
“¡ẏ%TZ=ẹaɦAY’ṃ“(\/)_:”s4s2
“E¬ƭḊHẈḢ“ðİ“|e*Ḳ?BḤ’ṃ“. -|1¶'”żÐ€¢FỴ$€p2£j/€Ẋ
¢ssḢµṣ€”1Zj€“ | ”Yµ€ÑY

```

Try it online!
> 3 votes

# Answer
# JavaScript (ES6), ~~328~~ ... 312 bytes

Takes input in currying syntax `(p)(q)`. Players are 0-indexed.

```
p=>g=(q,i=p*q*6,d=[...Array(52).keys(a=`:\\/:,(__),()(),(\\/),:/\\:,:():, | ,
,.3.,|0.--. |,| 1 |,| 2 |,| '--'0|,'3',Player 4`.split`,`)].sort(_=>Math.random()-.5))=>i--+p?g(q,i,d)+a[i%p?6:7]+a[i<0?14:i/p%6|8].replace(/\d/,c=>['TJQKA'[j=x>>2]||j-3,a['3454'[x&=3]],a[x%3],'------',p+i][c],x=d[i%p+p*(i/p/6|0)]):''

```

### Demo

```
let f =

p=>g=(q,i=p*q*6,d=[...Array(52).keys(a=`:\\/:,(__),()(),(\\/),:/\\:,:():, | ,
,.3.,|0.--. |,| 1 |,| 2 |,| '--'0|,'3',Player 4`.split`,`)].sort(_=>Math.random()-.5))=>i--+p?g(q,i,d)+a[i%p?6:7]+a[i<0?14:i/p%6|8].replace(/\d/,c=>['TJQKA'[j=x>>2]||j-3,a['3454'[x&=3]],a[x%3],'------',p+i][c],x=d[i%p+p*(i/p/6|0)]):''

;(update = _ => O.innerText = f(+P.value)(+Q.value))()
```

```
<label>Players <input id=P type=number value=1 onchange="update()"/></label> <label>Cards <input id=Q type=number value=1 onchange="update()"/></label> <button onclick="update()">Deal</button><pre id=O style="font-size:10px"></pre>
```

### How?

This is a recursive function, building the output from bottom to top. During the main part in which the cards are drawn, `i` is initialized to `p*q*6` and decremented until it reaches `0`. We then draw the header by further decrementing `i` until it reaches `-p`.

The ASCII art is split into small pieces stored into the array `a[]`. The table below describes the content of `a[]`, which makes the rest of the code easier to understand.

```
 Index | Content    | Description
-------+------------+------------------------------------------------
    0  | ":\\/:"    | bottom of 'diamonds' and 'hearts'
    1  | "(__)"     | bottom of 'spades'
    2  | "()()"     | bottom of 'clubs'
    3  | "(\\/)"    | top of 'hearts'
    4  | ":/\\:"    | top of 'diamonds' and 'spades'
    5  | ":():"     | top of 'clubs'
    6  | " | "      | player separator
    7  | "\n"       | line-feed
    8  | ".3."      | card row #1, "3" --> "------"
    9  | "|0.--. |" | card row #2, "0" --> symbol of card value
   10  | "| 1 |"    | card row #3, "1" --> top of color ASCII art
   11  | "| 2 |"    | card row #4, "2" --> bottom of color ASCII art
   12  | "| '--'0|" | card row #5, "0" --> symbol of card value
   13  | "'3'"      | card row #6, "3" --> "------"
   14  | "Player 4" | header, "4" --> player ID

```

### Formatted and commented

```
p => g = (                                // p = number of players
  q,                                      // q = number of cards
  i = p * q * 6,                          // i = counter
  d = [...Array(52).keys(                 // d = deck
    a = `:\\/:,(__),...`.split`,`         // a = ASCII art pieces (truncated, see above)
  )].sort(_ => Math.random() - .5)        // shuffle the deck
) =>                                      //
  i-- + p ?                               // if i is greater than -p:
    g(q, i, d) +                          //   do a recursive call and append ...
    a[i % p ? 6 : 7] +                    //   separator or line-feed
    a[i < 0 ? 14 : i / p % 6 | 8]         //   header or card row
    .replace(/\d/, c => [                 //   where digits are replaced with:
        'TJQKA'[j = x >> 2] || j - 3,     //     0: symbol of card value
        a['3454'[x &= 3]],                //     1: top of color ASCII art
        a[x % 3],                         //     2: bottom of color ASCII art
        '------',                         //     3: horizontal border
        p + i                             //     4: player ID
      ][c],                               //
      x = d[i % p + p * (i / p / 6 | 0)]  //   x = current card with: bits 0-1 = color
    )                                     //                          bits 2-5 = value
  :                                       // else:
    ''                                    //   stop recursion

```
> 3 votes

# Answer
# Python 2, ~~382~~ ~~358~~ ~~346~~ ~~338~~ 332 bytes

```
from random import*
p,n=input()
d=zip([0,1,2,3]*13,'23456789TJQKA'*4)
shuffle(d)
C=""".------.
|%s.--. |
| %s |
| %s |
| '--'%s|
'------'"""
print' | '.join('Player '+`i`for i in range(p))
exec"for l in zip(*[(C%(v,'(:::\/(//\)\):::'[s::4],':((:\_)\/_(/:)):'[s::4],v)).split('\\n')for s,v in d[:p]]):print' | '.join(l)\nd=d[p:]\n"*n

```

Try it online!
> 2 votes

# Answer
# SOGL V0.12, 106 bytes

```
E⁽⁰⅜║(Ηe─t¦4»\$²‘8n{"1<ω⅛┘‘4n╬¡;4n33žASUjk"TJQKA”+{a;22žF75ž}}'#δ№{ψ⌡≤οc+C}c_.∫:"▓⅛▲ŗ‘Κ⁽e{≤+};H?;lƧ |Γ∙┼;┼

```

Try it Here!

Card generating:

```
...‘                     push "(\/):\/::/\::\/::/\:(__):():()()" - the suits
    8n                   split to line lengths of 8 - individual suits
      {                  for each suit
       "...‘               push ".---| .-|   " - a quarter of a suit
            4n             split to line lengths of 4 - [".---", "| .-", "|   "]
              ╬¡           quad palindromize - empty card
                ;          get the suit on top
                 4n        split to line lengths of 4
                   33ž     insert in the card at [3; 3]
                      A    save on variable A - card template
SU                         push "1234567890"
  jk                       remove the first and last digits
    "TJQKA”+               append "TJQKA"
            {         }    for each number - "23456789TJQKA"
             a               load the template
              ;22ž           at [2; 2] insert the current number
                  F75ž       at [7; 5] insert the current number

```

Shuffling:

```
'#             push 52
  δ            lower range - [0, 1, ..., 50, 51]
   №           reverse - [51, 50, ..., 1, 0]
    {       }  for each, pushing the current item
     ψ           get a random number from 0 to ToS (inclusive)
      ⌡          that many times
       ≤           put the first item of the stack on the top
        οc+C     prepend that to the variable C, predefined with an empty array

```

Dealing:

```
c_              push Cs contents on the stack - the stack is now a mess of cards
  .∫            repeat input times - each player - pushing the current player number
    :             duplicate the number
     "..‘         push "player "
         Κ        prepend "player " to the number
          ⁽       uppercase the 1st letter
           e{  }  repeat 2nd input times
             ≤      put the first stack item on the top
              +     append it to "Player X" vertically (making an array)
;                 get the other copy of the player number
 H?               if POP-1 (aka if it's not 1)
   ;                swap the top 2 items - the current collumn and all the previous ones (by then they've been joined together)
    l               get its (vertical) length
     Ƨ |            push " |"
        Γ           palindromize - [" | "]
         ∙          multiply " | " vertically that length times
          ┼         append it horizontally (to the previous collumns)
           ;┼       append the current collumn

```
> 2 votes

# Answer
# Ruby, 262 bytes

```
->p,q{a=[*0..51].shuffle
puts ["Player %d"]*p*(d=" | ")%[*1..p],(1..q*6).map{|i|(["'------'
.------.
|%X.--. |
| %s |
| %s |
| '--'%X|".split($/)[i%6]]*p*d%a[i/6*p,p].map{|j|["(\\/):()::/\\:"[u=j%4*4-4,4],":\\/:()():\\/:(__)"[u,4],j/4][i%3]}).tr("01BC","TJQK")}}

```

Harder to follow, but shorter!

# Ruby, 279 bytes

```
->p,q{puts [*1..p].map{|k|"Player #{k}"}*" | "
a=[*0..51].shuffle
(q*6).times{|i|puts [".------.
|%s.--. |
| %s |
| %s |
| '--'%s|
'------'".split($/)[i%6]]*p*" | "%a[i/6*p,p].map{|j|[":\\/:()():\\/:(__)"[u=j%4*4-4,4],("%X"%(j/4)).tr("01BC","TJQK"),"(\\/):()::/\\:"[u,4]][i%3]}}}

```

Builds a format for each row, then uses the `%` operator like `sprintf` to populate it.

The fact that the card value appears on every 3rd row is handy. Card values are presented in hexadecimal with the digits `01BC` substituted to `TJQK`.

Saved 4 bytes from the suit symbols by considering that the top of diamonds and spades are the same but added 2 back on for the `-4` at the end of `j%4*4-4` Suit codes are -4 0 4 or 8 where `[-4,4]` means 4 characters starting the 4th last character in the string.

Could probably save a few more bytes. Having to repeat code for the player identifications is ugly.
> 2 votes

# Answer
## PHP, 509 bytes

```
<?$hu='(\/}';$hv=$dv=':\/:';$du=$su=':/\:';$sv='(__)';$cu=':():';$cv='()()';$q="------";$t=$argv[1];foreach([h,d,s,c]as$a)foreach([2,3,4,5,6,7,8,9,T,J,Q,K,A]as$b)$c[]=[$b,$a];shuffle($c);$h=$a=0;for(;$a<$t;$a++)$e[]="Player $a";$f[]=join(" | ",$e);for($g=$argv[2];$g--;){$p=$i=$k=$l=$m=$r=[];$j=$h+$t;for(;$h<$j;$h++){$n=$c[$h][0];$o=$c[$h][1];$p[]=".$q.";$i[]="|$n.--. |";$k[]="| ${$o.u} |";$l[]="| ${$o.v} |";$m[]="| '--'$n|";$r[]="'$q'";}foreach([p,i,k,l,m,r]as$b)$f[]=join(" | ",${$b});}echo join('
',$f);

```

Try it online!

This is my first attempt at code golf, so it can probably be improved a lot. I figured I had to start somewhere. :)
> 2 votes

# Answer
# Java (OpenJDK 8), ~~784~~ ~~835~~ ~~843~~ ~~826~~ ~~815~~ ~~781~~ 775 bytes

```
String k(String s){return s.replaceAll("...$","\n");}
p->q->{int c=0,l=0,s[]=new int[p*q],i=0,j,t,b;java.util.List e=new java.util.Stack();String v="TJQK",o="",n[]=new String[p*q],x=o;for(;i<p;o+="Player "+i+++" | ",x+=v);o=k(o);for(i=0;i<q;i++){o=k(o+x.replace(v,".------. | "));for(j=0;j<p;j++){do{t=(int)(Math.random()*13)+1;b=(int)(Math.random()*4);}while(e.contains(t+""+v.charAt(b)));e.add(t+""+v.charAt(b));s[c]=b;n[c]=t<2?"A":t<10?""+t:""+v.charAt(t-10);o+="|2.--. | | ".replace("2",n[c++]);}o=k(o);for(j=0;j<p;j++,l++)o+="| "+(s[l]<1?"(\\/)":s[l]<3?":/\\:":":():")+" | | ";o=k(o);for(j=0;j<p;j++)o+="| "+(s[i*p+j]<2?":\\/:":s[i*p+j]<3?"(__)":"()()")+" | | ";o=k(o);for(j=0;j<p;)o+="| '--'2| | ".replace("2",n[i*p+j++]);o=k(k(o)+x.replace(v,"'------' | "));}return o;}

```

Try it online!

Why the downvote, it complies with the spec
> 1 votes

# Answer
Python 3, 332 Bytes

```
from random import*
P=lambda x:print(*x,sep=' | ')
R=range
def f(p,c):
 P(f"Player {i}"for i in R(p))
 d=[f".------.,|{n}.--. |,| {a[:4]} |,| {a[4:]} |,| '--'{n}|,'------'".split(",")for a,n in sample([*zip(r':/\:(__) (\/):\/: :/\::\/: :():()()'.split()*13,'A23456789TJQK'*4)],p*c)]
 for i in R(c):
  for t in zip(*d[i::c]):
   P(t)

```
> 1 votes

---
Tags: code-golf, ascii-art, random, card-games
---


# Question
Title: How many squares are guarded by chess queens?
Today marks the 15th anniversary of Garry Kasparov's defeat against Deep Blue. Speaking of chess...

Input is a string that represents an 8x8 chess board containing only empty squares (`.`) and queens (`Q`). Output the number of squares that any queen can move to the next move. Queens can move any number of squares vertically, horizontally or diagonally.

Write either a program or a function. Shortest code wins, but most inventive solution gets the most upvotes.

## Examples

Input:

```
Q.......
........
.Q......
........
........
........
........
........

```

Output:

```
37

```

Input:

```
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQ.QQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ

```

Output:

```
1

```

# Answer
## Python - 125 chars

```
import os
s=os.read(0,99)
print sum(any('*'<s[i]!='Q'in s[i::j].split()[0]for j in(-10,-9,-8,-1,1,8,9,10))for i in range(71))

```
> 5 votes

# Answer
## APL, 40 characters

```
≢⍸a<∨/(⍳8 8)∘.{∨/⊃=/(⊢,+/,-/)¨⍺⍵}⍸a←'Q'=

```

⍸a←'Q'= transforms the matrix in a nested vector whose elements are the coordinates of the given queens.

(⊢,+/,-/) returns for every cell: the coordinates, their sum, their difference.

{∨/⊃=/(⊢,+/,-/)¨⍺ ⍵} returns 1 if cells ⍺ & ⍵ share one coordinate, the coordinates sum or the coordinates difference; that is gives 1 if a queen can move orizontally, vertically or diagonally from ⍺ to ⍵.

⍵∘.{∨/⊃=/(⊢,+/,-/)¨⍺⍵}⍳8 8 applies the previous function to each queen and each cell in the chessboard.

∨⌿ returns the boolean matrix of cell reachable from some queens ≢⍸a\< counts the cell reachable by the queens and not already occupied by queens.
> 7 votes

# Answer
## APL, 37 chars

```
{≢t~⍨⍸∨/(=/∘|∨0∘∊)¨(⍳8 8)∘.-t←⍸'Q'=⍵}

```
* `'Q'=⍵` gives boolean mask of queens
* gives vector of coordinates (row, column) of queens
* `t←` stores the result in var t
* `(⍳8 8)∘.-` outer product: gives "distances" (∆row, ∆column) between all grid cells and queen cells
* `0∘∊` checks if either ∆row or ∆column is 0
* `=/∘|` checks if ∆row = +/- ∆column
* `(=/∘|∨0∘∊)¨` checks both conditions for all "distances"
* `∨/` checks if at least one of those checks return true
* gives vector of coordinates (row, column) of reachable cells
* `t~⍨` removes original queens' positions
* count
> 5 votes

# Answer
**Java Solution**

```
public class NewQueenProblem {
        public static int countMoves(String input){
            int moves=0;
            class Board{
                char data;
                boolean visited;
            }
            Board[][] board=new Board[8][8];
            int x=0;
            for (int i=0; i< 64; i++){
                board[x%8][i%8] = new Board();
                board[x%8][i%8].data=input.charAt(i);
                if ((i+1)%8==0)
                    x++;
            }
            for (int i=0; i< 8; i++){
                for (int j=0; j< 8; j++){
                    if (board[i][j].data == 'Q'){
                        for (int row=0; row<8; row++)
                            if (board[i][row].data != 'Q' && !board[i][row].visited)
                                { moves++; board[i][row].visited=true;}
                        for (int col=0; col<8; col++)
                            if (board[col][j].data != 'Q' && !board[col][j].visited)
                                { moves++; board[col][j].visited=true;}
                        int posX=i, posY=j;
                        while (posX < 8 && posY < 8){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX++; posY++;
                        }
                        posX=i; posY=j;
                        while (posX > 0 && posY > 0){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX--; posY--;
                        }
                        posX=i; posY=j;
                        while (posX > 0 && posY < 8){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX--; posY++;
                        }
                        posX=i; posY=j;
                        while (posX < 8 && posY > 0){
                            if (board[posX][posY].data != 'Q' && !board[posX][posY].visited)
                            { moves++; board[posX][posY].visited=true;}
                            posX++; posY--;
                        }
                    }
                }
            }
            return moves;
        }
public static void main(String[] args) {
        int moves = countMoves("Q................Q..............................................");
        //int moves = countMoves("QQQQQQQQQQQQQQQQQQQQQQQQQQQQ.QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ");
        System.out.println(moves);
    }
}

```
> 3 votes

# Answer
## APL, 50 chars

```
{≢(b~x)∩,(x←(,'Q'=⍵)/b←,⍳8 8)∘.+(⍳8)∘.×∘.,⍨1 0 ¯1}

```

In English:

* `∘.,⍨1 0 ¯1`: computes all the pairs composed by -1, 0 or 1, i.e.: (0 0)(0 1)(0 -1)(1 0) and so on;
* `(⍳8)∘.×∘.,⍨1 0 ¯1`: multiply all the pairs computed by all the number from 1 to 8, obtaining all the possible offsets of movement of the queen;
* `(x←(,'Q'=⍵)/b←,⍳8 8)`: puts is `x` the coordinates of the given queens;
* `∘.+`: compute yet another outer sum, combining the position of the given queens with all the possible displacement offsets. This gives a multidimensional array of coordinate pairs of all the possible place where each of the queens might end up, including outside the board (whose valid coordinate pairs is in `b`)
* `(b~x)∩,`: removes from the list `b` all the coordinates taken by the queens in the given (`x`) and intersects it with flattened array of pairs of all the possible positions of the queens
* : count the remaining pairs

Try online sample 1.

Try online sample 2
> 3 votes

# Answer
# JavaScript 140 bytes

```
f=a=>a.split`
`.map((r,y,G)=>[...r].map((c,x)=>A+=c<"Q"&&G.some((R,Y)=>[...R].some((C,X)=>C>"."&&((d=X-x)*(D=Y-y)==0||d**2==D**2)))),A=0)&&A

console.log(f(`Q.......
........
.Q......
........
........
........
........
........`)==37)

console.log(f(`QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQ.QQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ
QQQQQQQQ`)==1)
```
> 0 votes

# Answer
# Perl 5, 172 + 3 (`-pF`) bytes

```
push@a,[@F]}{for$i(0..7){O:for$j(0..7){for$x(-1..1){for$y(-1..1){if($x|$y){$r=$i;$c=$j;$a[$i][$j]ne Q&&$a[$r][$c]eq Q&&++$\&&next O while(($r+=$x)^7)<8&&(($c+=$y)^7)<8}}}}}

```

Try it online!

There's got to be a better way to do it, but this at least works.
> 0 votes

---
Tags: code-golf, chess
---


title: Matching Adjacent Words

text:
# Question
Title: Matching Adjacent Words
In this challenge, you are passed two words: Your job is to determine if they are *adjacent*.

Two letters are adjacent if:

1. They are the same letter, or
2. They are lexicographically adjacent.

*For example, **J** is adjacent to **I**,**J**, and **K** only. **Z** is not adjacent to **A***

Two words are adjacent if:

1. They are the same length, and
2. Each letter is adjacent to a unique letter in the other word.

*For example, **CAT** is adjacent to **SAD**, as **C\>D, A\>A, T\>S**.
**FREE** is not adjacent to **GRRD** (each **E** needs a letter to pair with)*.

## Input/Output

You are passed two strings, and you need to return a truthy value if they are adjacent, otherwise a falsy value. You should return within a minute for all test cases below.

You can assume that the strings will only contain uppercase, alphabetic letters.

The two strings can be passed as a list, or concatenated, with or without quotes.

## Test Cases

Truthy:

```
A A
A B
C B
DD CE
DE FC
ABCD BCDE
AACC DBBB
DJENSKE FDJCLMT
DEFGHIJKL HJLEHMCHE
IKLIJJLIJKKL LJLJLJLJLJHI
ACEGIKMOQSUWY BLNPRDFTVHXJZ
QQSQQRRQSTTUQQRRRS PQTTPPTTQTPQPPQRTP
ELKNSDUUUELSKJFESD DKJELKNSUELSDUFEUS

```

Falsy:

```
A C
A Z
B J
JK J
CC BA
CE D
DJENSKE GDJCLMT
DEFGHIJKL HJLHMCHE
IJKLIJKLKIJL LIJLLHJLJLLL
AWSUKMEGICOQY RSHXBLJLNQDFZ
QQSQQRRQSTTUQQQRRS PQTTPPTTQTPQPPQRTT
ELKNSDUVWELSKJFESD DKJELKNSUELSDUFEUS

```

This is , so the shortest valid answer wins!

# Answer
> 11 votes
# CJam, ~~14~~ ~~13~~ 12 bytes

```
r$r$.-:)3,-!

```

Try it online! or verify all test cases at once.

### Algorithm

Let **s** and **t** be two sorted words of the same length. For **s** and **t** to be lexicographically adjacent (LA), it is necessary and sufficient that all pairs of its corresponding characters are also LA.

The condition is clearly sufficient for all words, and necessary for words of length **1**.

Now, assume **s** and **t** have length **n \> 1**, and let **a** and **b** be the first characters, resp., of **s** and **t**.

Since **s** and **t** are LA, there is some bijective mapping **φ** between the characters of **s** and the characters of **t** such that **x** and **φ(x)** are LA for all **x** in **s**, meaning that **|x - φ(x)| ≤ 1** for all **x** in **s**.

Let **c = φ(a)** and **d = φ-1(b)**. Because of **a**'s and **b**'s minimality, **a ≤ d (1)** and **b ≤ c (2)**.

Furthermore, since **b** and **d**, and **a** and **c**, and LA, **d ≤ b + 1 (3)** and **c ≤ a + 1 (4)**.

By combining **(1)** and **(3)**, and **(2)** and **(4)**, we get that **a ≤ d ≤ b + 1** and **b ≤ c ≤ a + 1**, from which we deduce that **a - 1 ≤ b ≤ a + 1** and, therefore, that **a** and **b** are LA.

Now, by combining **(1)** and **(4)**, and **(2)** and **(3)**, we get that **c - 1 ≤ a ≤ d** and **d - 1 ≤ b ≤ c**, from which we deduce that **c - 1 ≤ d ≤ c + 1** and, therefore that **c** and **d** are LA.

Thus, if we redefine **φ** by **φ(a) = b** and **φ(d) = c**, **|x - φ(x)| ≤ 1** will still hold for all **x** in **s** and, in particular, for all **x** in **s\[1:\]**.

This way, **s\[0\] = a** and **t\[0\] = b**, and **s\[1:\]** and **t\[1:\]**, are LA.

Since **s\[1:\]** has length **n - 1**, this proves the necessity by induction.

### Code

```
r               e# Read the first word from STDIN.
 $              e# Sort its characters.
  r             e# Read the second word from STDIN.
   $            e# Sort its characters.
    .-          e# Perform vectorized subtraction.
                e# This pushes either the difference of char codes of two
                e# corresponding characters or a character that has no does not
                e# correspond to a character in the other, shorter word.
      :)        e# Increment all results.
                e# In particular, this maps [-1 0 1] to [0 1 2].
        3,      e# Push the range [0 1 2].
          -     e# Perform set difference, i.e., remove all occurrences of 0, 1 and
                e# 2 from the array of incremented differences.
           !    e# Apply logical NOT. This gives 1 iff the array was empty iff
                e# all differences gave -1, 0 or 1.

```

# Answer
> 4 votes
# MATL, 10 ~~12~~ ~~17~~ bytes

```
c!S!odXl2<

```

This uses Dennis' approach: sort first and compare characters in matching positions.

Input is an array of strings, with the format `{'CAT 'SAD'}`.

Output is an array of zeros and ones. A result is truthy iff it contains all ones (this is agreed to be truthy).

Uses current release (10.2.1), which is earlier than this challenge.

*EDIT:* Function `Xl` has been renamed to `|` in newer versions of the language (and `o` is no longer necessary). The link below includes those modifications.

**Try it online!**

**Explanation**:

```
c         % implicitly cell array of strings and convert to 2D char array.
          % This pads with spaces if needed
!S!       % sort each row
o         % convert array from char to double
d         % difference between elements in the same column
Xl        % absolute value of each entry
2         % number literal
<         % each entry becomes 1 if smaller than 2 (adjacent letters), and 0 otherwise

```

---

Old approach, which accepts the strings as separate inputs: **12 bytes**:

```
SiSXhcodXl2<

```

*EDIT*: the code in the link has been modified acording the changes in the language; see comment above.

**Try it online**!

**Explanation**:

```
S         % implicitly input first string and sort
iS        % input second string and sort
Xh        % build cell array with these two strings
c         % convert to 2D char array. This pads with spaces if needed
o         % convert array from char to double
d         % difference between elements in the same column
Xl        % absolute value of each entry
2         % number literal
<         % each entry becomes 1 if smaller than 2 (adjacent letters), and 0 otherwise

```

# Answer
> 2 votes
# C, 233 bytes

```
#include <stdlib.h>
#include <string.h>
#define h char
#define r return
int c(void*a,void*b){r*(h*)a-*(h*)b;}int a(h*s,h*t){int l=strlen(s),m=strlen(t);if(l!=m)r 0;qsort(s,l,1,c);qsort(t,m,1,c);while(l--)if(abs(s[l]-t[l])>1)r 0;r 1;}

```

You can test it by saving that as `adj.h` and then using this `adj.c` file:

```
#include <stdio.h>
#include "adj.h"

int main() {
  char aa[] = "A", A[] = "A";
  char b[] = "A", B[] = "B";
  char cc[] = "C", C[] = "B";
  char d[] = "DD", D[] = "CE";
  char e[] = "DE", E[] = "FC";
  char f[] = "ABCD", F[] = "BCDE";
  char g[] = "AACC", G[] = "DBBB";
  char hh[] = "DJENSKE", H[] = "FDJCLMT";
  char i[] = "DEFGHIJKL", I[] = "HJLEHMCHE";
  char j[] = "IKLIJJLIJKKL", J[] = "LJLJLJLJLJHI";
  char k[] = "ACEGIKMOQSUWY", K[] = "BLNPRDFTVHXJZ";
  char l[] = "QQSQQRRQSTTUQQRRRS", L[] = "PQTTPPTTQTPQPPQRTP";
  char m[] = "ELKNSDUUUELSKJFESD", M[] = "DKJELKNSUELSDUFEUS";
  char n[] = "A", N[] = "C";
  char o[] = "A", O[] = "Z";
  char p[] = "B", P[] = "J";
  char q[] = "JK", Q[] = "J";
  char rr[] = "CC", R[] = "BA";
  char s[] = "CE", S[] = "D";
  char t[] = "DJENSKE", T[] = "GDJCLMT";
  char u[] = "DEFGHIJKL", U[] = "HJLHMCHE";
  char v[] = "IJKLIJKLKIJL", V[] = "LIJLLHJLJLLL";
  char w[] = "AWSUKMEGICOQY", W[] = "RSHXBLJLNQDFZ";
  char x[] = "QQSQQRRQSTTUQQQRRS", X[] = "PQTTPPTTQTPQPPQRTT";
  char y[] = "ELKNSDUVWELSKJFESD", Y[] = "DKJELKNSUELSDUFEUS";
  char *z[] = {aa,b,cc,d,e,f,g,hh,i,j,k,l,m,n,o,p,q,rr,s,t,u,v,w,x,y};
  char *Z[] = {A ,B,C ,D,E,F,G,H ,I,J,K,L,M,N,O,P,Q,R ,S,T,U,V,W,X,Y};

  for(int _=0;_<25;_++) {
    printf("%s %s: %s\r\n", z[_], Z[_], a(z[_], Z[_]) ? "true" : "false");
  }

  return 0;
}

```

Then compile using `gcc adj.c -o adj`. The output is:

```
A A: true
A B: true
C B: true
DD CE: true
DE CF: true
ABCD BCDE: true
AACC BBBD: true
DEEJKNS CDFJLMT: true
DEFGHIJKL CEEHHHJLM: true
IIIJJJKKKLLL HIJJJJJLLLLL: true
ACEGIKMOQSUWY BDFHJLNPRTVXZ: true
QQQQQQQRRRRRSSSTTU PPPPPPPQQQQRTTTTTT: true
DDEEEFJKKLLNSSSUUU DDEEEFJKKLLNSSSUUU: true
A C: false
A Z: false
B J: false
JK J: false
CC AB: false
CE D: false
DEEJKNS CDGJLMT: false
DEFGHIJKL HJLHMCHE: false
IIIJJJKKKLLL HIJJJLLLLLLL: false
ACEGIKMOQSUWY BDFHJLLNQRSXZ: false
QQQQQQQQRRRRSSSTTU PPPPPPQQQQRTTTTTTT: false
DDEEEFJKKLLNSSSUVW DDEEEFJKKLLNSSSUUU: false

```

# Answer
> 2 votes
# JavaScript (ES6), 86 ~~90 94~~

**Edit** 4 bytes saved thx @Neil
**Edit 2** 4 bytes save thx @Mwr247

```
(a,b)=>[...[...a].sort(),0].every((x,i)=>parseInt(x+([...b].sort()[i]||0),36)%37%36<2)

```

Note: adjacency check on a pair of letters. Take the pair as a base 36 number *n*, if the letters are equal, then `n = a*36+a = a*37`. If there is a difference of 1 then `n = a*36+a+1 = a*37+1` or `n = a*36+a-1 = a*37-1`. So `n % 37` must be 0, 1 or 36. And `n%37%36` must be 0 or 1.

Note 2: the added '0' is used to ensure that a and b are the same length. It's shorter then `a.length==b.length`

```
F=(a,b)=>[...[...a].sort(),0].every((x,i)=>parseInt(x+([...b].sort()[i]||0),36)%37%36<2)

console.log=x=>O.textContent+=x+'\n';

testOK=[['A','A'],['A','B'],['C','B'],['DD','CE'],['DE','FC'],
['ABCD','BCDE'],['AACC','DBBB'],['DJENSKE','FDJCLMT'],
['DEFGHIJKL','HJLEHMCHE'],['IKLIJJLIJKKL','LJLJLJLJLJHI'],
['ACEGIKMOQSUWY','BLNPRDFTVHXJZ'],
['QQSQQRRQSTTUQQRRRS','PQTTPPTTQTPQPPQRTP'],
['ELKNSDUUUELSKJFESD','DKJELKNSUELSDUFEUS']];
testFail=[['A','C'],['A','Z'],['B','J'],['JK','J'],['CC','BA'],['CE','D'],
['DJENSKE','GDJCLMT'],['DEFGHIJKL','HJLHMCHE'],
['IJKLIJKLKIJL','LIJLLHJLJLLL',''],
['AWSUKMEGICOQY','RSHXBLJLNQDFZ'],
['QQSQQRRQSTTUQQQRRS','PQTTPPTTQTPQPPQRTT'],
['ELKNSDUVWELSKJFESD','DKJELKNSUELSDUFEUS']];

console.log('TRUE')
testOK.forEach(t=>{
  var a=t[0],b=t[1],r=F(a,b)
  console.log(r+' '+a+' '+b)
})
console.log('FALSE')
testFail.forEach(t=>{
  var a=t[0],b=t[1],r=F(a,b)
  console.log(r+' '+a+' '+b)
})
```

```
<pre id=O></pre>
```

# Answer
> 2 votes
# Python 2, 90 bytes

```
lambda A,B:all(ord(b)-2<ord(a)<ord(b)+2for a,b in zip(sorted(A),sorted(B)))*len(A)==len(B)

```

Simple anonymous function, I have to have a separate check for length because `zip` will just contatenate. Theres a similar function in `itertools` (`zip_longest`) which would pad empty strings, but that would be quite costly.

Testing with

```
f=lambda A,B:all(ord(b)-2<ord(a)<ord(b)+2for a,b in zip(sorted(A),sorted(B)))*len(A)==len(B)

for case in testCases.split('\n'):
    print case, f(*case.split())

```

produces:

```
A A True
A B True
C B True
DD CE True
DE FC True
ABCD BCDE True
AACC DBBB True
DJENSKE FDJCLMT True
DEFGHIJKL HJLEHMCHE True
IKLIJJLIJKKL LJLJLJLJLJHI True
ACEGIKMOQSUWY BLNPRDFTVHXJZ True
QQSQQRRQSTTUQQRRRS PQTTPPTTQTPQPPQRTP True
ELKNSDUUUELSKJFESD DKJELKNSUELSDUFEUS True
A C False
A Z False
B J False
JK J False
CC BA False
CE D False
DJENSKE GDJCLMT False
DEFGHIJKL HJLHMCHE False
IJKLIJKLKIJL LIJLLHJLJLLL  False
AWSUKMEGICOQY RSHXBLJLNQDFZ False
QQSQQRRQSTTUQQQRRS PQTTPPTTQTPQPPQRTT False
ELKNSDUVWELSKJFESD DKJELKNSUELSDUFEUS False

```

# Answer
> 1 votes
# JavaScript ES6, ~~117 bytes~~ ~~116 bytes~~ ~~111 bytes~~ 109 bytes

```
(j,k)=>j.length==k.length&&(f=s=>[...s].sort())(j).every((c,i)=>Math.abs(c[h='charCodeAt']()-f(k)[i][h]())<2)

```

## Test Cases

```
a=(j,k)=>j.length==k.length&&(f=s=>[...s].sort())(j).every((c,i)=>Math.abs(c[h='charCodeAt']()-f(k)[i][h]())<2);
// true
console.log('A A:', a('A', 'A'));
console.log('A B:', a('A', 'B'));
console.log('C B:', a('C', 'B'));
console.log('DD CE:', a('DD', 'CE'));
console.log('DE FC:', a('DE', 'FC'));
console.log('ABCD BCDE:', a('ABCD', 'BCDE'));
console.log('AACC DBBB:', a('AACC', 'DBBB'));
console.log('DJENSKE FDJCLMT:', a('DJENSKE', 'FDJCLMT'));
console.log('DEFGHIJKL HJLEHMCHE:', a('DEFGHIJKL', 'HJLEHMCHE'));
console.log('IKLIJJLIJKKL LJLJLJLJLJHI:', a('IKLIJJLIJKKL', 'LJLJLJLJLJHI'));
console.log('ACEGIKMOQSUWY BLNPRDFTVHXJZ:', a('ACEGIKMOQSUWY', 'BLNPRDFTVHXJZ'));
console.log('QQSQQRRQSTTUQQRRRS PQTTPPTTQTPQPPQRTP:', a('QQSQQRRQSTTUQQRRRS', 'PQTTPPTTQTPQPPQRTP'));
console.log('ELKNSDUUUELSKJFESD DKJELKNSUELSDUFEUS:', a('ELKNSDUUUELSKJFESD', 'DKJELKNSUELSDUFEUS'));

// false
console.log('A C:', a('A', 'C'));
console.log('A Z:', a('A', 'Z'));
console.log('B J:', a('B', 'J'));
console.log('JK J:', a('JK', 'J'));
console.log('CC BA:', a('CC', 'BA'));
console.log('CE D:', a('CE', 'D'));
console.log('DJENSKE GDJCLMT:', a('DJENSKE', 'GDJCLMT'));
console.log('DEFGHIJKL HJLHMCHE:', a('DEFGHIJKL', 'HJLHMCHE'));
console.log('IJKLIJKLKIJL LIJLLHJLJLLL:', a('IJKLIJKLKIJL', 'LIJLLHJLJLLL'));
console.log('AWSUKMEGICOQY RSHXBLJLNQDFZ:', a('AWSUKMEGICOQY', 'RSHXBLJLNQDFZ'));
console.log('QQSQQRRQSTTUQQQRRS PQTTPPTTQTPQPPQRTT:', a('QQSQQRRQSTTUQQQRRS', 'PQTTPPTTQTPQPPQRTT'));
console.log('ELKNSDUVWELSKJFESD DKJELKNSUELSDUFEUS:', a('ELKNSDUVWELSKJFESD', 'DKJELKNSUELSDUFEUS'));
```

```
<!-- results pane console output; see http://meta.stackexchange.com/a/242491 -->
<script src="http://gh-canon.github.io/stack-snippet-console/console.min.js"></script>
```

## Credit

* @rink.attendant.6 shaved off 5 bytes
* @user81655 shaved off 2 bytes

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

```
(a,b)=>![...a].sort().some((d,i)=>(d[c='charCodeAt']()-([...b].sort()[i]||c)[c]())/2|0)

```

Uses a zero-centric symmetrical range check by dividing by the max value, then truncating with a bitwise "or" (`|`). Shorter than having to do two checks, or one with `Math.abs()`.

# Answer
> 1 votes
## Haskell, ~~67~~ 63 bytes

```
import Data.List
f a=any(null.(a\\)).mapM(\x->[pred x..succ x])

```

Usage example: `f "FREE" "GRRD"` -\> `False`.

How it works (note: `f` is partially point-free and the second parameter `b` does not appear in the definition):

```
mapM(\x->[pred x..succ x])      -- for each letter of b make a list of the
                                -- predecessor, the letter itself and the successor.
                                -- Make a list of every possible combination
                                -- thereof, e.g "dr" ->
                                -- ["cq","cr","cs","dq","dr","ds","eq","er","es"]
any(null.(a\\))                 -- see if the difference between any of the
                                -- combinations and the other parameter a is
                                -- empty, i.e. they have the same elements

```

Edit: @xnor found 4 bytes to save. Thanks!

# Answer
> 1 votes
# K (oK), 27 bytes

**Solution:**

```
2>|/x*x:-/(|/#:'x)$x@'<:'x:

```

Try it online!

**Examples:**

```
2>|/x*x:-/(|/#:'x)$x@'<:'x:("QQSQQRRQSTTUQQRRRS";"PQTTPPTTQTPQPPQRTP")
1
2>|/x*x:-/(|/#:'x)$x@'<:'x:("DEFGHIJKL";"HJLHMCHE")
0
2>|/x*x:-/(|/#:'x)$x@'<:'x:("AAA";"AAA")
1
2>|/x*x:-/(|/#:'x)$x@'<:'x:("AAA";"AA")
0

```

**Explanation:**

First sort each string, then pad to be the same length, then take one from the other (ASCII values of chars), square result as there is no built-in `abs`, take the maximum difference and check whether that is less than 2.

```
2>|/x*x:-/(|/#:'x)$x@'<:'x: / the solution
                         x: / save input to variable x
                      <:'   / ascending sorted indices (<:) for each (') list
                   x@'      / apply (@) each (') of these indices to the input (x)
          (      )$         / pad
             #:'x           / count (#:) each (') list (x)
           |/               / max (|) over (/) to get maximum
        -/                  / subtract (-) over (/) to take 2nd list from 1st
      x:                    / save in variable x
    x*                      / multiply by x (so square)
  |/                        / max over to get maximum distance
2>                          / is 2 greater than (>) to this maximum? returns 1 (true) or 0 (false)

```

# Answer
> 0 votes
# Pyth, ~~37~~ 31 bytes

```
&qZ-FmldK.zqY-m.a-FdCmmCkSdK[Z1

```

Try it online with all test cases!

Shaved off 6 bytes by using the shortened reduce notation (`-F` instead of `.U-bZ`)

Solution inspired by Dennis

First submission to codegolf!

## Explanation

We can split the expression in two parts, which are compared with `&` to output the result. I'll try to explain by writing some pseudo-Python

First we check that the length of the two words are the same

```
mldK.z         lengths = map(lambda d: len(d), K=all_input())
.U-bZmldK.z    diff = reduce(lambda b, Z: b - Z, lengths)
qZ.U-bZmldK.z  diff == 0

```

Then, we apply Dennis' method:

```
       K                                                      # ['CAT', 'SAD']
 m   SdK           sort = map(lambda d: sorted(d), K)         # ['ACT', 'ADS']
 mmCkSdK           ascii = map(lambda d: sorted(d), map(lambda k: ord(k), K))
                                                              # [[65, 67, 84], [65, 68, 83]]
CmmCkSdK           zipped = zip(*ascii)                       # [[65, 65], [67, 68], [84, 83]]
m.U-bZd CmmCkSdK   map(lambda d: d[0] - d[1], zipped)         # [0, -1, 1]
m.a.U-bZd CmmCkSdK map(lambda d: abs(d[0] - d[1]), zipped)    # [0, 1, 1]

```

We then use the `-` operator to filter all elements of that list that are not in `[Z1` (`[0, 1]`), and check that the result is an empty list with `qY`

# Answer
> 0 votes
# C, 172 bytes

```
#define q(x)qsort(x,strlen(x),1,c)
c(x,y)char*x,*y;{return*x-*y;}main(a,v,w)char**v,*w,*a;{for(q(w=v[1]),q(a=v[2]);*w&&*a&&abs(*w-*a)<2;w++,a++);printf("%d",abs(*w-*a)<2);}

```

## Test Cases

```
$ bash -x test.sh
+ bash -x test.sh
+ ./a.out A A
1+ ./a.out A B
1+ ./a.out C B
1+ ./a.out DD CE
1+ ./a.out DE FC
1+ ./a.out ABCD BCDE
1+ ./a.out AACC DBBB
1+ ./a.out DJENSKE FDJCLMT
1+ ./a.out DEFGHIJKL HJLEHMCHE
1+ ./a.out IKLIJJLIJKKL LJLJLJLJLJHI
1+ ./a.out ACEGIKMOQSUWY BLNPRDFTVHXJZ
1+ ./a.out QQSQQRRQSTTUQQRRRS PQTTPPTTQTPQPPQRTP
1+ ./a.out ELKNSDUUUELSKJFESD DKJELKNSUELSDUFEUS
1+ ./a.out A C
0+ ./a.out A Z
0+ ./a.out B J
0+ ./a.out JK J
0+ ./a.out CC BA
0+ ./a.out CE D
0+ ./a.out DJENSKE GDJCLMT
0+ ./a.out DEFGHIJKL HJLHMCHE
0+ ./a.out IJKLIJKLKIJL LIJLLHJLJLLL
0+ ./a.out AWSUKMEGICOQY RSHXBLJLNQDFZ
0+ ./a.out QQSQQRRQSTTUQQQRRS PQTTPPTTQTPQPPQRTT
0+ ./a.out ELKNSDUVWELSKJFESD DKJELKNSUELSDUFEUS
0++

```

# Answer
> 0 votes
## PowerShell, 140 bytes

```
param($a,$b)(($a=[char[]]$a|sort).Count-eq($b=[char[]]$b|sort).Count)-and(($c=0..($a.Count-1)|%{+$a[$_]-$b[$_]}|sort)[0]-ge-1-and$c[-1]-le1)

```

Might be possible to get this shorter. It's not currently competitive with Python or JavaScript, but it uses a slightly different approach, so I figured I'd post it.

### Explanation

This code is really confusing for someone not fluent in PowerShell, so I'll try to break it down into English as best I can...

We start with taking input `param($a,$b)` as normal.

The whole rest of the code is actually one statement, and can be broken as `(...)-and(...)` to test two Boolean statements with the `-and` operator.

The left-hand parens can be broken as `(... -eq ...)` to test equality of two objects. In this instance, the objects are the `.Count`s (that is, the length) of two new char-arrays. Each inner paren `($a=[char[]]$a|sort)` takes the original input word, re-casts it as a char-array, then sorts it and re-saves back into the same variable. We do that for both `$a` and `$b`. The left-hand side thus verifies that the input words are the same length. If they are not the same length, this half of the outer Boolean statement will fail and `False` will be output.

Moving to the right-hand side, we're again testing two Boolean statements with `(... -and ...)`. The left-hand side tests whether *something* is greater-than-or-equal-to negative 1 with `-ge-1`. The *something* is the zeroth-element of a constructed array `$c`, which is created by:

* taking a range of the allowed indices `0..($a.count-1)`
* piped into a loop `|%{...}`
* each iteration of the loop, we take the ASCII values of the indexed character in `$a` and subtract the ASCII value of the indexed character in `$b`
* which is then `|sort`ed by numerical value

The other side of the statement takes the maximal value `$c[-1]` of the array and ensures it's less-than-or-equal to 1 with `-le1`.

Thus, if the two input strings are indeed adjacent, the `$c` array will be something like `@(-1,-1,-1...0,0,0...1,1,1)`. So the first element will be `-1` and the last element will be `1`. If they are not adjacent, the difference in ASCII values for a particular pair will either be `< -1` or `> 1`, so this half of the outer Boolean test will fail, and `False` will be output.

Only if both sides pass will `True` be output, and the strings are therefore LA.

# Answer
> 0 votes
**Rust, ~~269~~ 264 bytes**

```
fn a(w:&str,x:&str)->bool{if w.len()==x.len(){return{let mut c:Vec<char>=w.chars().collect();let mut d:Vec<char>=x.chars().collect();c.sort();d.sort();for(e,f)in c.iter().zip(d.iter()){if(((*e as u8)as f64)-((*f as u8)as f64)).abs()>1f64{return false}}true}}false}

```

Expanded:

```
fn are_adjacent(w: &str, x: &str)->bool{

    if w.len() == x.len(){

        return {

            let mut c : Vec<char> = w.chars().collect();
            let mut d : Vec<char> = x.chars().collect();

            c.sort();
            d.sort();

            for (e,f) in c.iter().zip(d.iter()){
                if (((*e as u8) as f64) - ((*f as u8) as f64)).abs() > 1f64{
                    return false
                }
            }

            true
        }
    }

    false
}

```

Test Cases:

```
fn main(){
    assert_eq!(true,are_adjacent("A","B"));
    assert_eq!(true,are_adjacent("A","B"));
    assert_eq!(true,are_adjacent("C","B"));
    assert_eq!(true,are_adjacent("DD","CE"));
    assert_eq!(true,are_adjacent("DE","FC"));
    assert_eq!(true,are_adjacent("ABCD","BCDE"));
    assert_eq!(true,are_adjacent("AACC","DBBB"));
    assert_eq!(true,are_adjacent("DJENSKE","FDJCLMT"));
    assert_eq!(true,are_adjacent("DEFGHIJKL","HJLEHMCHE"));
    assert_eq!(true,are_adjacent("IKLIJJLIJKKL","LJLJLJLJLJHI"));
    assert_eq!(true,are_adjacent("ACEGIKMOQSUWY","BLNPRDFTVHXJZ"));
    assert_eq!(true,are_adjacent("QQSQQRRQSTTUQQRRRS","PQTTPPTTQTPQPPQRTP"));
    assert_eq!(true,are_adjacent("ELKNSDUUUELSKJFESD","DKJELKNSUELSDUFEUS"));

    assert_eq!(false,are_adjacent("A","C"));
    assert_eq!(false,are_adjacent("A","Z"));
    assert_eq!(false,are_adjacent("B","J"));
    assert_eq!(false,are_adjacent("JK","J"));
    assert_eq!(false,are_adjacent("CC","BA"));
    assert_eq!(false,are_adjacent("CE","D"));
    assert_eq!(false,are_adjacent("DJENSKE","GDJCLMT"));
    assert_eq!(false,are_adjacent("DEFGHIJKL","HJLHMCHE"));
    assert_eq!(false,are_adjacent("IJKLIJKLKIJL","LIJLLHJLJLLL"));
    assert_eq!(false,are_adjacent("AWSUKMEGICOQY","RSHXBLJLNQDFZ"));
    assert_eq!(false,are_adjacent("QQSQQRRQSTTUQQQRRS","PQTTPPTTQTPQPPQRTT"));
    assert_eq!(false,are_adjacent("QQSQQRRQSTTUQQQRRS","PQTTPPTTQTPQPPQRTT"));
    assert_eq!(false,are_adjacent("ELKNSDUVWELSKJFESD","DKJELKNSUELSDUFEUS"));
}

```

# Answer
> 0 votes
# APL, 59 bytes (characters)

(61 if we have to supply the { and }, 63 with f←)

I'm not the greatest APLer, but it's just too much fun.

`(0=+/2≤|¨∊-/{⎕av⍳⍵}¨(⍺{⌈/⍴¨⍺⍵}⍵)⍴¨⍺[⍋⍺]⍵[⍋⍵])∧=/⍴¨∊¨⍺⍵`

`=/⍴¨∊¨⍺⍵` are the inputs equally long?

and all of the below

`(⍺{⌈/⍴¨⍺⍵}⍵)⍴¨⍺[⍋⍺]⍵[⍋⍵]` sort both inputs and shape them to be as long as the longest of the two (they wrap around if you make them longer than they are)

`|¨∊-/{⎕av⍳⍵}` convert both char vectors to int vectors of their ascii values, do a vector subtraction and absolute all values

`0=+/2≤` sum up values larger than or equal to two and check if the result is equal to 0

# Answer
> 0 votes
# J, 27 bytes

```
[:*/@(2>|)[:-/,:&(3&u:@/:~)

```

## ungolfed

```
[: */@(2 > |) [: -/ ,:&(3&u:@/:~)

```

## explained

* `&(3&u:@/:~)` sorts both arguments, and converts to them to ascii numbers
* `,:` creates a 2 x n matrix, where n is the number of chars of the args
* `-/` subtracts one row from the other, giving a list of length n representing the distance of corresponding chars
* `(2>|)` returns 1 if the absolute value of the distance is less than 2, 0 otherwise
* `*/` multiplies all those `0`s and `1`s together: hence, the final result is 1 iff all pairs of corresponding chars are adjacent.

Try it online!

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


title: Fuzzy distances to coordinates

text:
# Question
Title: Fuzzy distances to coordinates
This challenge is similar to my previous one, but has a twist that makes it significantly more difficult.

There are *n* people on a 2D plane. Using distances between them we're going to find their positions. You may make four assumptions:

1. There are at least 3 people.
2. The first person is at position (0, 0).
3. The second person is at position (x, 0) for some x \> 0.
4. The third person is at position (x, y) for some y \> 0.

However, **all distances are floored to integers**! For example, if the actual distance between two people is 4.7 units, your program will see the distance 4 as input instead.

So your challenge is to write a program or function that given a 2D array of **floored** distances (where `D[i][j]` gives the distance between person `i` and `j`) returns a list of their coordinates.

The challenge here is that you have incomplete information, and must try to extract as much precision as possible. Therefore this challenge is not a code golf, instead it's a code challenge, and the winner is the answer that returns the most accurate results.

---

# Scoring

I will provide a series of arrays of coordinates. It is up to you to turn these arrays into 2D distance matrices **and flooring each element in these matrices** (if I were to do that here this question would get way too large).

For a certain input use your answer to predict the coordinates of each person. Then, for each person calculate the squared distance between the prediction and actual position. Sum all these and divide by the number of people in the input. That is your score for this input.

The total score of your answer is the average score you get for all of the following inputs:

```
[(0, 0), (0.046884, 0), (-4.063964, 0.922728), (-3.44831, -6.726776), (-0.284375, -0.971985)]
[(0, 0), (0.357352, 0), (-1.109721, 1.796241), (-7.894467, -3.086608), (-3.74066, -1.528463)]
[(0, 0), (6.817717, 0), (-6.465707, 0.705209), (-2.120166, 3.220972), (-2.510131, 8.401557)]
[(0, 0), (0.394603, 0), (-4.097489, 0.957254), (-5.992811, 1.485941), (-2.724543, -3.925886)]
[(0, 0), (6.686748, 0), (6.088099, 0.22948), (8.211626, -4.577765), (-1.98268, -4.764555)]
[(0, 0), (2.054625, 0), (0.75308, 0.497376), (6.987932, -5.184446), (0.727676, -5.065224)]
[(0, 0), (6.283741, 0), (-1.70798, 5.929428), (2.520053, 6.841456), (-2.694771, -1.816297)]
[(0, 0), (1.458847, 0), (5.565238, 7.756939), (-4.500271, 4.443), (-0.906575, 3.654772)]
[(0, 0), (0.638051, 0), (-2.37332, 0.436265), (-8.169133, -0.758258), (-7.202891, -2.804207)]
[(0, 0), (1.101044, 0), (-1.575317, 6.717197), (-2.411958, -7.856072), (-4.395595, 2.884473)]
[(0, 0), (7.87312, 0), (-0.320791, 2.746919), (-1.4003, 0.709397), (-0.530837, -0.220055), (-3.492505, -7.278485), (2.401834, 2.493873), (0.911075, -5.916763), (4.086665, -5.915226), (2.801287, 5.409761)]
[(0, 0), (0.304707, 0), (-1.709252, 0.767977), (-0.00985, -0.356194), (-2.119593, 3.353015), (1.283703, 9.272182), (6.239, -0.455217), (7.462604, 1.819545), (0.080977, -0.026535), (-0.282707, 6.55089)]
[(0, 0), (3.767785, 0), (0.133478, 0.19855), (-0.185253, -5.208567), (-6.03274, 6.938198), (5.142727, -1.586088), (0.384785, 0.532957), (3.479238, -1.472018), (3.569602, 8.153945), (-0.172081, 2.282675)]
[(0, 0), (0.445479, 0), (-3.3118, 8.585734), (0.071695, -0.079365), (2.418543, 6.537769), (1.953448, 0.511852), (-1.662483, -5.669063), (0.01342, 0.097704), (0.919935, 1.697316), (2.740839, -0.041325)]
[(0, 0), (3.281082, 0), (-6.796642, 5.883912), (-3.579981, -2.851333), (-1.478553, 6.720389), (3.434607, -9.042404), (7.107112, 2.763575), (-4.571583, 1.100622), (-1.629668, 1.235487), (-3.199134, 0.813572)]
[(0, 0), (5.278497, 0), (-4.995894, 3.517335), (-0.012135, 3.444023), (0.364605, -0.49414), (1.73539, 1.265443), (-7.289383, -3.305504), (-7.921606, 5.089785), (-1.002743, -0.554163), (-8.99757, -3.572637)]
[(0, 0), (2.331494, 0), (1.83036, 2.947165), (-5.520626, 1.519332), (5.021139, -4.880601), (-0.318216, -0.063634), (-5.204892, -5.395327), (-0.92475, -0.090911), (-0.19149, -2.188813), (-0.035878, 0.614552)]
[(0, 0), (2.981835, 0), (-3.909667, 2.656816), (-0.261224, -2.507234), (-7.35511, -3.65201), (1.198829, 5.328221), (-5.139482, -4.320811), (-3.253523, 2.367497), (6.254513, 1.565134), (3.13451, 4.595651)]
[(0, 0), (1.059838, 0), (-0.849461, 7.87286), (2.108681, 0.717389), (-0.065587, -0.007163), (2.818824, 5.529878), (2.413443, 4.102863), (-3.050506, -2.541446), (-1.215169, -4.818011), (-1.671743, 2.539397)]
[(0, 0), (5.036602, 0), (-1.627921, 1.813918), (-9.285855, 1.277063), (2.271804, -0.51118), (-7.070704, 2.252381), (6.125956, -4.278879), (1.000949, -1.38177), (-0.67657, -2.747887), (2.820677, -5.718695)]
[(0, 0), (0.733516, 0), (6.619559, 1.368964), (-0.047351, 0.545139), (-4.518243, -7.506885), (3.31011, -4.329671), (3.885474, -1.535834), (-3.952488, -1.94899), (1.402441, 7.538954), (2.385809, 4.042365), (-6.403547, 3.623895), (3.742502, 0.025475), (1.944868, -2.972475), (-0.514566, -1.015531), (-0.08634, 5.140751)]
[(0, 0), (2.374024, 0), (-1.016305, 1.31073), (2.176473, -1.357629), (0.181825, 2.107476), (-0.978214, -3.436398), (0.828254, -0.39516), (2.981311, -6.761157), (1.517599, 5.009197), (8.063442, 0.930487), (4.628231, 7.749696), (3.810604, 4.671208), (1.158015, 2.914197), (-9.230353, -0.473591), (-9.031469, -4.206725)]
[(0, 0), (5.733822, 0), (1.394054, 1.432354), (1.556614, 5.691443), (3.665168, 7.199478), (-0.670337, 0.396217), (4.144468, 2.959243), (-6.129783, -7.048069), (-3.230162, 3.116924), (-6.365913, 3.727042), (-0.174385, 0.253418), (-0.454495, -4.415929), (5.815488, 1.443031), (-4.288448, 0.619174), (1.957015, 0.784202)]
[(0, 0), (6.550779, 0), (-8.592692, 1.728506), (-6.460692, 2.344509), (8.359129, 4.578714), (3.593451, -4.172634), (8.697976, -2.379752), (4.27242, 5.296418), (2.920394, -4.520174), (0.662004, 2.171769), (1.879771, -1.873537), (0.769374, 3.570321), (-3.438699, -3.255416), (3.23342, -3.220256), (-0.002136, -5.646753)]
[(0, 0), (5.013665, 0), (-0.543516, 9.981648), (8.378266, 5.33164), (4.759961, -2.007708), (2.88554, 1.069445), (-6.110542, -6.253516), (0.292062, -0.052982), (-4.869896, -1.251445), (1.61841, 7.980471), (-0.313257, 0.515709), (8.673848, -2.269644), (-0.446207, -0.568228), (3.015721, -2.819861), (1.160386, -5.897356)]
[(0, 0), (0.437257, 0), (-3.127834, 8.941175), (0.785858, 1.99155), (2.005894, -6.723433), (1.332636, -6.214795), (3.149412, 7.17296), (-5.350834, -5.106189), (1.447561, 0.910621), (3.032259, -7.977927), (1.520669, 5.121877), (-1.075969, 0.098313), (1.015673, -5.244922), (3.575391, 5.270148), (-9.160492, 2.943283)]
[(0, 0), (3.63663, 0), (5.448045, 8.287277), (1.314494, -0.164441), (-1.941398, 4.223086), (5.025181, 0.495811), (-8.466786, -2.933392), (-0.139755, 0.730451), (-0.098497, -0.587856), (-3.337111, -1.238969), (2.142947, 2.521078), (0.352537, 5.4194), (-4.49191, 5.261929), (2.198984, -3.781113), (3.525393, 1.150581)]
[(0, 0), (4.540155, 0), (-7.248917, 2.368607), (2.434071, 1.763899), (3.990914, 1.135211), (-5.422214, -5.785259), (0.526037, -0.888364), (-0.370255, 8.515669), (0.77125, 4.48859), (3.9838, -2.3101), (-2.993973, -0.775446), (-1.731491, -1.028441), (-0.184254, 0.281876), (0.048732, 0.222435), (0.108646, -0.344878)]
[(0, 0), (4.934251, 0), (7.472259, 4.693888), (0.057108, -0.038881), (-0.276457, -0.157808), (-6.745232, -0.357168), (5.979037, -0.653591), (-3.969328, -6.050715), (4.19821, -1.883165), (-4.294607, -0.407446), (-6.11544, 0.480539), (1.193587, -1.028919), (-0.387421, 2.036394), (5.78394, 1.333821), (4.178077, 4.286095)]
[(0, 0), (7.547164, 0), (0.989783, 1.074185), (0.192979, 0.210046), (6.528904, 0.400088), (5.602168, 5.791553), (4.058506, 3.995028), (-1.033977, -5.44405), (5.767663, -6.702417), (4.401684, -3.097193), (-0.821263, 4.624133), (6.031465, 6.544092), (7.188866, 1.599597), (5.327328, 3.51571), (1.305662, 7.488827)]
[(0, 0), (0.638053, 0), (7.279348, 5.416438), (-6.495944, -1.385692), (5.348119, 6.89312), (-5.145817, -5.640294), (2.909321, -3.139983), (7.052144, 3.902919), (2.467506, 1.362787), (3.469895, -7.977336), (7.598683, -5.947955), (-0.679492, 9.140908), (-3.310304, 3.134427), (-0.83399, 5.797306), (4.08935, 0.830119), (-7.764758, -4.403114), (5.183087, -8.528744), (-0.75072, 6.163092), (-0.692329, -0.225665), (2.0628, -2.008365)]
[(0, 0), (9.468635, 0), (2.005581, 2.669352), (3.416536, 6.9941), (-3.293394, 0.864229), (-1.044833, 2.243219), (6.011018, 4.014313), (-0.959567, 9.620265), (-1.855409, 1.890371), (-0.629015, -1.383614), (4.087875, -2.203917), (3.286183, -7.748879), (-7.781181, -5.295325), (3.28653, -0.930535), (3.973893, -1.784441), (-7.7541, 4.355823), (1.522453, -1.960952), (5.085025, -1.511887), (8.401342, -2.139507), (-1.727888, 0.7952)]
[(0, 0), (8.617779, 0), (-7.012573, 5.883927), (-3.508725, -6.838323), (6.676063, 6.884947), (8.297052, -0.134775), (7.416737, 5.915766), (-5.10108, -7.183776), (-4.651823, 5.434926), (-1.099239, -0.238062), (-0.313045, 0.354853), (-7.592061, 5.408053), (0.566482, 0.652099), (-3.551817, -3.365006), (8.514655, 4.653756), (-4.249357, -2.130864), (1.181348, -1.22839), (2.469081, 1.110794), (1.831897, -1.552467), (-5.892299, -1.919411)]
[(0, 0), (2.407206, 0), (-6.771008, 0.810524), (-3.840048, -0.152269), (7.109171, -5.609477), (-7.391481, 5.639112), (-8.670299, 2.742321), (0.586435, 4.542551), (-0.442438, 0.107817), (4.31145, -1.409808), (-4.534678, -1.504437), (4.680038, -3.080315), (-4.973063, 5.638478), (6.127056, -7.491446), (2.291953, -2.357609), (3.510856, -9.171005), (3.971143, -8.515823), (0.049413, -5.842664), (1.058161, -0.21883), (7.093364, -3.604422)]
[(0, 0), (6.969461, 0), (4.338403, 5.197497), (0.369553, -0.770371), (8.882643, 1.450294), (2.124852, -1.210185), (-3.046623, -4.395661), (7.716904, 4.60951), (-0.83271, -0.854575), (-2.333383, -0.308884), (-6.347966, 3.124373), (0.832848, -1.892136), (1.446553, 1.613845), (-2.241092, -6.53878), (5.004282, 5.401177), (3.31202, 0.432188), (0.164548, 1.23087), (9.860844, -0.125136), (0.133559, -0.202543), (2.686551, 1.013555)]
[(0, 0), (9.107655, 0), (5.455882, 3.54979), (-0.681513, 2.950275), (7.369848, 4.050426), (5.320211, -8.288623), (-5.315311, 4.632769), (-2.801207, -3.00623), (2.502035, -2.085464), (-0.645319, -4.854856), (3.639806, -8.669185), (-0.732853, 2.379454), (-8.722855, 2.483643), (-0.03048, 1.845021), (-6.904949, -2.596416), (0.685437, 1.042775), (-5.182001, -2.617796), (1.595501, 0.885512), (-8.567463, -0.607195), (-5.456613, 5.81163)]
[(0, 0), (1.669656, 0), (-3.385149, 6.655961), (-1.501983, -0.746686), (1.962876, -0.780073), (0.51437, -4.130592), (1.825567, 0.531272), (-4.188001, 0.514048), (-5.894689, 1.726502), (-1.429067, -3.558197), (4.605078, 2.060605), (1.670708, -8.99749), (5.44004, -5.315796), (-0.619392, 1.785159), (-2.854087, 1.696694), (4.974886, 6.291052), (-0.699939, -5.930564), (-2.35508, -0.057436), (-0.804635, -0.687497), (2.289458, 1.946817)]
[(0, 0), (3.626795, 0), (5.048495, 1.581758), (0.154465, 3.132534), (-4.862419, 7.051311), (3.927243, -0.408956), (-7.41798, -0.313768), (1.987639, -7.957834), (-1.100923, -1.442563), (1.949075, -0.382901), (5.696638, 3.400352), (-1.121574, 1.315934), (-4.37434, 4.937007), (-1.244524, -7.36647), (9.138938, 4.035956), (-0.207342, -4.257523), (-1.298235, 5.950812), (2.17008, 1.116468), (-1.410162, 4.861598), (4.69532, 2.076335)]
[(0, 0), (9.787264, 0), (-4.65872, 0.957699), (-2.813155, -1.174551), (-0.445703, 0.362518), (2.920405, 0.914672), (-1.63431, 0.048213), (-0.534393, -2.389697), (-0.105639, -1.589822), (-0.100723, 8.648806), (-6.894891, 4.8257), (7.417014, 2.868825), (-0.84031, -0.322606), (-0.802219, 1.209803), (7.808668, 1.700949), (-3.270161, -3.463587), (-1.118415, 0.713057), (4.130249, 0.824635), (4.664258, 5.993324), (2.575522, -1.031243)]
[(0, 0), (6.514721, 0), (-2.2931, 3.6007), (3.388059, 1.102576), (-1.777694, -2.809783), (3.431761, 6.534511), (-8.13158, -2.940151), (-4.856169, 2.834183), (-0.706068, -0.93294), (-0.393184, -4.989653), (4.480243, -4.107001), (1.681165, 0.611419), (4.442544, -0.536704), (4.90654, -7.356498), (-8.722645, 1.203365), (-2.067292, -4.134382), (-3.002458, 7.891842), (1.398419, -1.279873), (0.237866, 0.010691), (6.879955, -2.882286)]
[(0, 0), (1.421587, 0), (-0.615169, 0.286873), (0.848122, -2.730297), (0.220832, 0.89274), (4.588547, 8.497067), (-5.079677, -8.428552), (-3.170092, 2.418608), (1.309388, -3.658275), (1.639533, -2.364448), (-1.327656, 1.006565), (-0.475542, 0.298309), (5.430131, -8.343581), (8.430933, 4.118178), (-2.090712, -0.470172), (1.146227, -6.664852), (-0.542811, 1.909997), (0.439509, 6.112737), (0.343281, 0.630898), (-3.673348, 5.101854), (-0.072445, 5.784645), (4.895027, -7.960275), (-9.633185, -1.688371), (8.059592, -5.178718), (-2.334299, 1.217686)]
[(0, 0), (5.456611, 0), (0.181969, 2.084064), (0.89351, -2.507042), (1.570701, 1.202458), (0.814632, 1.883803), (2.790854, 5.8582), (0.699228, 2.377369), (-0.463356, 5.162464), (1.166769, 4.739348), (-4.652182, 5.553297), (-1.123396, 4.186443), (-0.327375, 0.45977), (-0.395646, -4.122381), (0.652084, -0.696313), (0.716396, 2.005553), (0.73846, -7.361414), (-1.912492, 3.937217), (-0.162445, -2.681668), (-0.133005, -0.910646), (2.194447, -4.169833), (-3.132339, -3.079166), (-3.078943, -1.410719), (-1.365236, -4.103878), (2.044671, -0.831881)]
[(0, 0), (1.382529, 0), (5.031547, 7.747151), (-0.49526, 0.019819), (-7.918566, -1.919355), (1.046601, -4.397131), (3.113731, 8.325339), (-1.700401, 1.511139), (-2.699135, -5.052298), (3.434862, -2.609676), (-4.506703, -0.424842), (0.154899, 3.782215), (1.373067, 4.412563), (4.548762, 2.096691), (-0.0275, -2.604761), (4.462809, 1.533662), (-2.016089, -3.481723), (7.024583, 6.980284), (0.254207, -7.964855), (-2.055224, -1.374547), (-3.185323, -3.753214), (-0.479636, -7.476727), (2.208698, -6.374003), (0.24381, -0.620774), (-0.551312, -3.796487)]
[(0, 0), (3.442359, 0), (-5.045461, 1.685484), (0.072923, 1.158112), (-1.347292, 2.626515), (1.982477, 4.374474), (-3.188879, -4.020849), (-0.430788, 0.118491), (0.725544, 1.992762), (-2.893352, -4.311321), (-6.871016, -2.359638), (1.406456, 1.734539), (2.029903, 6.151807), (7.565244, 1.948656), (-6.420158, 0.698035), (-4.873019, 3.593625), (9.548917, -0.45405), (-8.701737, -1.872887), (-7.941202, -1.4121), (-5.995713, 0.555241), (-5.704163, -2.868896), (-2.677936, -1.924243), (-3.460593, -8.679839), (0.631064, -0.433745), (1.18902, -1.496815)]
[(0, 0), (6.537782, 0), (-6.75348, 0.404049), (-5.348818, 5.082766), (-3.738518, -7.824984), (4.513721, -7.740162), (-7.707575, 3.393118), (-0.11626, 0.439479), (0.12586, -2.885467), (4.952966, 5.673672), (2.56597, -0.333544), (-4.60141, 2.716012), (-1.865207, 1.826155), (3.234169, -0.966176), (-5.977172, 1.660029), (-7.968728, 0.889721), (-0.028198, 0.153274), (-5.427989, 8.150441), (-3.708225, -0.777001), (3.513778, 0.529579), (6.309027, 0.399666), (0.542878, 1.900558), (-0.633748, -4.971474), (5.340487, -2.474143), (-0.805431, -8.633636)]
[(0, 0), (0.211756, 0), (3.03609, 1.381372), (1.472087, 3.505701), (-0.198393, -0.284868), (4.290257, -7.630449), (-0.120326, -0.047739), (3.167345, -1.144179), (7.791272, 6.043579), (6.125765, -6.3722), (-0.178091, 9.313027), (-4.177894, -0.704969), (-2.950708, 1.716094), (-0.016133, -0.105582), (-5.962467, 6.088385), (0.901462, 0.58075), (2.063274, -0.221478), (-0.430464, 0.9548), (4.824813, -4.037669), (0.863528, 8.321907), (2.693996, -0.380075), (0.879924, 4.243756), (-7.759599, -2.81635), (2.58409, -2.225758), (5.515442, -7.445861)]
[(0, 0), (0.958126, 0), (-0.566246, 3.074569), (2.666409, -4.784584), (-5.490386, 1.820646), (0.505378, 0.261745), (-0.122648, -9.791207), (0.569961, 1.044212), (-8.917451, -1.667965), (-7.374214, -1.193314), (-4.559765, -2.486695), (2.367622, 1.707526), (0.762113, -5.553413), (-9.62438, -2.077561), (-0.072526, -0.072188), (-2.051266, -5.410767), (-6.656983, -1.824092), (1.170361, 2.019313), (2.689391, -3.998207), (1.814094, 1.782214), (0.498034, -9.437937), (0.87507, 0.670687), (-8.114628, 4.823256), (2.693849, 6.952855), (-0.005543, -0.01139)]
[(0, 0), (1.703854, 0), (1.091391, 2.171906), (5.559313, -0.310439), (-0.396107, -0.771272), (-5.136147, 7.769235), (8.969736, 0.885092), (3.541436, -6.530927), (-0.461503, -5.877802), (-6.108795, -5.163834), (3.698654, 3.749293), (8.049228, 2.056624), (-6.022241, -0.657227), (-8.701763, 4.803845), (1.225822, -2.070325), (2.099514, 5.191076), (0.500653, -0.104261), (-0.581698, -5.755634), (-5.150133, -8.269633), (2.559925, 6.839805), (-0.149545, 4.456742), (1.43855, 1.865402), (3.439778, -4.954683), (-4.18711, 7.244959), (0.640683, 0.907557)]
[(0, 0), (6.577004, 0), (0.042196, 0.025522), (8.61361, -0.689878), (5.407545, 1.709241), (-4.724503, 3.123675), (4.329227, -5.283993), (-1.238506, -1.104368), (-0.758244, 1.882281), (3.851691, -0.571509), (-0.229269, 7.452942), (2.833834, -6.742377), (-8.49992, 1.912219), (3.102788, -9.456966), (-0.420271, 2.449342), (4.123196, -0.512152), (5.893872, -3.689055), (-3.801056, -3.486555), (-3.576364, 3.448325), (-0.397213, -0.010559), (-4.519186, 4.525627), (2.720825, 6.0414), (0.918962, -0.430301), (2.217531, -3.056907), (0.912148, -1.487924)]
[(0, 0), (0.170063, 0), (1.088807, 2.795493), (5.884358, -1.914274), (9.333625, -0.111168), (7.168328, 4.042127), (2.558513, -0.146732), (-8.011882, -2.358709), (-0.374469, -6.591334), (2.495474, 1.011467), (0.094949, -0.351228), (7.0753, 1.26426), (6.614842, 4.664073), (-2.777323, 7.287667), (3.280189, -6.811248), (-7.254853, -1.472779), (7.147915, 1.932636), (-3.431701, 3.030416), (-0.863222, -1.177363), (0.512901, -0.258635), (-5.614965, 0.462802), (3.452843, -6.869839), (7.475845, -0.353582), (0.067355, 0.298013), (4.39831, -8.5387)]

```

**It's not allowed to optimize specifically for this set of inputs. I may change these inputs to any others at my discretion.**

Lowest score wins.

# Answer
> 2 votes
# , score = 4.708859

```
require(vegan)
solve_mmds<-function(dpf,noise=0,wgs=rep(1,nrow(dpf))){
  #MMDS
  v = wcmdscale(dpf+noise,2,add=TRUE,w=wgs)

  #center on first point
  v = sweep(v,2,v[1,])

  #rotate to adjust second point
  alpha = atan2(v[,2],v[,1])
  alpha_rot = alpha - alpha[2]
  radius = sqrt(apply(v^2,1,sum))
  v = cbind(cos(alpha_rot), sin(alpha_rot))*radius

  #flip to adjust third point
  if(v[3,2]<0){
    v[,2]=-v[,2]
  }

  #return
  v
}

N_input = length(input_data)
err_runs = rep(0,N_input)

for(i_input in c(1:N_input)){

  p = matrix(input_data[[i_input]],ncol=2,byrow=TRUE)
  n = nrow(p)

  dp = as.matrix(dist(p,upper=TRUE,diag=TRUE))
  dpf = floor(dp)

  v = solve_mmds(dpf)
  err_runs[i_input] = mean(apply( (p-v)^2, 1, sum))

  cat("test #", i_input," MSE:", err_runs[i_input],"\n")
}

cat("Average error: ", mean(err_runs)," \n")

```

Try it online

The core of the program is based on the Metric Multi-Dimensional Scaling (MDS) approach, which solves precisely the problem described by the OP. The idea is to start from a collection of dissimilarities between entities and infer the coordinates of the system. Some post-processing is required to rotate, translate and flip the solution.

There are at least three functions available in R to perform MDS. There is also one in sklearn in Python, in case. In the code above I settled for the weighted mds variant (function wcmdscale), mostly due to the possibility to add weights and to a slightly better performing correction for negative eigenvalues. There is a core function in R, called cmdscale, which could be used instead, and would result in a score of 5.77.

The code provided is predisposed to accept weights, as well as noise in the floored distance matrix. After testing, it seemed best to not use any of these options.

~~Sadly, the package "vegan" is not available on TIO. So, no live demonstration: my apologies for this inconvenience.~~ Works on TIO like a charm.

Interestingly, the program significantly underperforms on the last two examples. Adding noise can help, but it worsens the performance on every other test case. It would be interesting to find out what makes these two test cases particularly difficult.

# Answer
> 1 votes
# C++ (gcc), score = 5.94258

```
#ifndef _GLIBCXX_DEBUG
#define NDEBUG
#endif // _GLIBCXX_DEBUG

#include <iostream> //{ and more includes
#include <vector>
#include <string>
#include <sstream>
#include <array>
#include <cstdio>
#include <cmath>
#include <random>
#include <cassert>
#include <limits>
//}

template <typename T>
struct point { //{
    T x, y;
    point () {};
    point (T x1, T y1) : x (x1), y (y1) {};
    point operator+(point p) const { return point(x+p.x, y+p.y); }
    void operator+=(point p)       { x+=p.x; y+=p.y; }
    point operator-(point p) const { return point(x-p.x, y-p.y); }
    void operator-=(point p)       { x-=p.x; y-=p.y; }
    point operator*(T a)     const { return point(x*a, y*a);}
    void operator*=(T a)           { x *= a; y *= a; }
    T norm()                 const { return x * x + y * y; }
    T dot  (point p)         const { return x*p.x + y*p.y; }
    T cross(point p)         const { return x*p.y - y*p.x; }
    bool operator==(point<T> p1) const { return x==p1.x && y==p1.y;}
    bool operator!=(point<T> p1) const { return ! (*this == p1);}
    bool operator<(point<T> p1)  const {
        if (x != p1.x) return x < p1.x;
        return y < p1.y;
    }
    template <typename T1>
    operator point<T1> () const {
        return point<T1>(x, y);
    }
};

template <typename T>
std::istream& operator>> (std::istream& str, point<T>& pt) {
    str >> pt.x >> pt.y;
    return str;
}

template <typename T>
std::ostream& operator<< (std::ostream& str, point<T> pt) {
    str << "(" << pt.x << ", " << pt.y << ")";
    return str;
}//}

typedef point<double> pt;

//{ Additional functions, for point<real_type> only (specialize for double here)
double angle(pt p) {
	return std::atan2(p.y, p.x);
}

pt rotate(pt p, double angle) {
	double sin = std::sin(angle), cos = std::cos(angle);
	return pt(p.x * cos - p.y * sin, p.x * sin + p.y * cos);
}

pt normalize(pt p) {
	return p * (1/std::sqrt(p.norm()));
}
//}

std::array<bool, 0x80> const valid_double_start = [](){
	std::array<bool, 0x80> valid_double_start;
	for (size_t i = 0; i < valid_double_start.size(); ++i)
		valid_double_start[i] = false;
	for (char c = '0'; c <= '9'; ++c)
		valid_double_start[c] = true;
	valid_double_start['-'] = valid_double_start['.'] = true;
	// there are also 'e' and probably 'p' but they are not at
	// the begin of a double value string representation
	return valid_double_start;
}();

double score(std::vector<pt>const& pts1, std::vector<pt>const& pts2) {
	double result = 0;
	for (size_t i = 0; i < pts1.size(); ++i)
		result += (pts1[i] - pts2[i]).norm();
	return (result / pts1.size());
}

std::vector<std::vector<double>> distmatrix (std::vector<pt>const& pts) {
	std::vector<std::vector<double>> result (pts.size(), std::vector<double>(pts.size()));
	for (size_t i = 0; i < pts.size(); ++i) {
		for (size_t j = 0; j < i; ++j)
			result[i][j] = result[j][i] =
			std::floor(std::sqrt((pts[i] - pts[j]).norm()));
//		result[i][i] = 0; // implicit when initialize 'result' vector
	}
	return result;
}

std::vector<pt> normalize (std::vector<pt> pts) {
	for (size_t i = 1; i < pts.size(); ++i) pts[i] -= pts[0];
	pts[0] = {0, 0};
	double angle = - ::angle(pts[1]);
	for (size_t i = 1; i < pts.size(); ++i) pts[i] = rotate(pts[i], angle);
	pts[1].y = 0;
	if (pts[2].y < 0)
		for (size_t i = 2; i < pts.size(); ++i) pts[i].y = -pts[i].y;
	return pts;
}

unsigned nDiff (std::vector<std::vector<double>> mat1, std::vector<std::vector<double>> mat2, double eps = 1e-10) {
	unsigned result = 0;
	assert(mat1.size() == mat2.size());
	for (size_t i = 1; i < mat1.size(); ++i)
		for (size_t j = 0; j < i; ++j)
			result += std::abs(mat1[i][j] - mat2[i][j]) > eps;
	return result;
}

std::vector<pt> pts; // use global variable to print progress

int constexpr n_iteration = 200;
std::vector<pt> solve_with_seed (
	std::vector<std::vector<double>>const& distmatrix, int seed
) {

	std::mt19937 engine (seed);
	std::vector<pt> result; result.reserve(distmatrix.size());
	std::uniform_real_distribution<double> dist (-100, 100);
	for (size_t i = 0; i < distmatrix.size(); ++i)
		result.emplace_back(dist(engine), dist(engine));

	for (int iteration = 0; iteration < n_iteration; ++iteration) {
		#ifndef NDEBUG
		if (iteration % 10 == 0) {
			auto norm_result = normalize(result);
			std::clog << "Iteration " << iteration << "; "
			<< "score = " << score(norm_result, pts) << '\n';
			std::clog << "[";
			for (pt p : norm_result) std::clog << p << ", ";
			std::clog << "\b\b]";

			std::clog << " (nDiff = " << nDiff(distmatrix, ::distmatrix(norm_result)) << ")\n";
		}
		#endif
		for (size_t i = 1; i < pts.size(); ++i)
			for (size_t j = 0; j < i; ++j) {
				pt vec_IJ = result[j] - result[i];
				double dist = std::sqrt(vec_IJ.norm()),
				floor_expected = distmatrix[i][j];
				double ndist = (dist + (floor_expected + .5)) / 2;
				ndist = std::max(floor_expected, ndist);
				ndist = std::min(floor_expected + 1, ndist);

				double delta_dist = (dist - ndist) / 2;
				vec_IJ = normalize(vec_IJ) * delta_dist;
				result[i] += vec_IJ;
				result[j] -= vec_IJ;

//				std::clog << "Numerical error = " << std::sqrt((result[i] - result[j]).norm()) - ndist << '\n';
			}
	}
	return normalize(result);
}

std::vector<pt> solve (
	std::vector<std::vector<double>>const& distmatrix
) {
	// just going to try some random values of seed.
	std::vector<pt> result; int minDiff = std::numeric_limits<int>::max();
	for (int seed : {123456789,987654321,69850,68942,4162,12012}) {
		std::vector<pt> r = solve_with_seed(distmatrix, seed);
		int d = nDiff(distmatrix, ::distmatrix(r));
		if (d < minDiff) {
			minDiff = d;
			result = r;
		}
	}
	return result;
}

int main() {
	std::string str;
	double sumscore = 0; unsigned ntest = 0;
	while (std::getline(std::cin, str)) {
		if (str.empty()) break;
		std::stringstream sst (str);
		std::vector<double> values;
		while (true) {
			int c = sst.peek();
			while (c != EOF && !valid_double_start[c]) {
				sst.get();
				c = sst.peek();
			}
			if (c == EOF ) break;
			double val;
			if (!(sst >> val)) {
				std::clog << "Invalid input. Stop reading.\n";
				break;
			}
			values.push_back(val);
		}
		if (values.size() % 2 != 0) {
			std::clog << "Number of double values is odd: " << values.size()
			<< ". Assuming the last value (" << values.back() << ") is redundant.\n";
			values.pop_back();
		}

		pts.resize(values.size() / 2);
		for (size_t i = 0; i < pts.size(); ++i) {
			pts[i].x = values[2*i];
			pts[i].y = values[2*i+1];
		}

		if (pts.size() < 3) {
			std::clog << "Need at least 3 points. Ignore input.\n";
			continue;
		}

		auto distmatrix = ::distmatrix(pts);

		std::vector<pt> result_pts = solve(distmatrix);

		double score = ::score(pts, result_pts);
		std::cout << "Test #" << ++ntest << " score: " << score << ", "
		<< "number of difference in distance matrix: " << nDiff(distmatrix, ::distmatrix(result_pts)) << '\n';
		sumscore += score;
	}

	std::cout << "Final score = " << (sumscore / ntest) << '\n';
}

```

Try it online!

The main part of the code is the `solve` function, which is given a floored distance matrix (as a 2D vector of `double`) and output a vector of `point<double>`. The rest of the code are score-calculator.

Idea: Start with a (seeded) random set of points, loop `n_iteration = 200` times the operation: For each pairs of point, get their current distance and expected distance (which is estimated to be equal to the distance in the floored input matrix `+ 0.5`), and then change the position of those two points to an appropriate position nearer to the expected distance.

For this program, the new length is calculated as `min(max((old_length + expected_length) / 2, expected_length + 0.5), expected_length - 0.5`, which is twice closer to the `expected_length` if the `old_length` is sufficiently close, and force it to change such that the absolute difference between new length and `expected_length` is no more than `1` if `old_length` is more than `2` units apart from the `expected_length`.

It also tries multiple seeds, and then pick the seed which gives least error in the resulting distance matrix.

---
Tags: code-challenge, geometry, optimization
---


# Question
Title: Generate an ascii-art non-intersecting path
Given 2 integer inputs representing the size of the field, `x` and `y`, output a path through the field.

Example output for `5, 4`:

```
#
#
# ###
### #

```

The whole field is 5 by 4, and there is a path made of hashmarks crossing the field.

The path should always start in the top left corner, and go to the bottom right. The whole path should be randomized every time the program is run. Every valid path should be a possible output.

The rules for paths are:

* Made of hashmarks
* Every hash is only connected to 2 other hashes (i.e. the path does not intersect or run alongside itself)

The non-hash spaces can be filled it with any other character, but it must be consistent (i.e. all spaces, all periods, etc.)

Examples:

```
2, 2

##
 #

3, 4

##
 ##
  #
  #

5, 5

#####
    #
    #
    #
    #

6, 5

## ###
 # # #
## # #
# ## #
###  #

7, 9

#######
      #
####  #
#  #  #
#  #  #
#  #  #
#  ####
#
#######

```

This kind of path is similar to a self-avoiding random walk, however it can't be adjacent to itself unlike a true SAW.

Path continuity and path touching are both defined without diagonals.

# Answer
> 11 votes
# MATLAB, ~~316 305 300~~ 293 bytes

```
function P=f(a,b);z(a,b)=0;P=z;c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');B=1;while B;P=z;P(1)=1;for K=1:a*b;S=z;S(a,b)=1;for L=2:a*b;S(~S&c(S)&~P)=L;end;[i,j]=find(S&c(P==K));if i;r=randi(nnz(i));else;break;end;P(i(r),j(r))=K+1;if P(a,b);break;end;end;B=any(any(c(P>0)>3));end;P(P>0)=35;P=[P,'']

```

Thanks @LuisMendo for various suggestions and a bunch of bytes=)

Try it online! (Without warranty: Note that a few adjustments were needed to get it to run on Octave: First of all I needed to remove the `function` keyword and hardcode the values, secondly: The spaces do not get printed correctly as in Matlab. Also I did not check the convolution commands of Octave, which might act differently.)

Example output for input `(7,10)` (can already take quite a while):

```
#
#
##
 ##
  #   ###
  #   # ##
  #####  #

```

### Explanation

This generates paths sequentially from the top left to the bottom right with the desired 4-connectivity, and then uses rejection sampling to reject paths that do violate the criterion that you cannot have adjecent parts.

```
function P=f(a,b);
z(a,b)=0;                                 % a matrix of zeros of the size of th efield
P=z;
c=@(X)conv2(+X,[0,1,0;1,1,1;0,1,0],'s');  % our convolution function, we always convolute with the same 4-neighbourhood kernel
B=1;
while B;                                  % while we reject, we generate paths:
    P=z;
    P(1)=1;                               % P is our path, we place the first seed
    for K=1:a*b;                          % in this loop we generate the all shortest paths (flood fill) from the bottom right, withot crossing the path to see what fiels are reachable from the bottom left
        S=z;
        S(a,b)=1;                         % seed on the bottom left
        for L=2:a*b;
            S(~S&c(S)&~P)=L;              % update flood front
        end;
        [i,j]=find(S&c(P==K));            % find a neighbour of the current end of the path, that is also reachable from the bottom left
        if i;                             % if we found some choose a random one
            r=randi(nnz(i));
        else;
            break;                        % otherwise restart (might not be necessary, but I'm too tired to think about it properly=)
        end;
        P(i(r),j(r))=K+1;                 % update the end of the current path
        if P(a,b);                        % if we finished, stop continuing this path
            break;
        end;
    end;
    B=any(any(c(P>0)>3));                 % check if we actually have a valid path
end;
P(P>0)=35;                                % format the path nicely
P=[P,''];

```

Oh and as always:

> Convolution is the key to success.

# Answer
> 20 votes
# Befunge, 344 bytes

```
&v>>>#p_:63p:43g`\!+v>/*53g+\01g:2%2*1-\2/!*63g+\0\:v
 40$ v++!\`g14:p35:\<^2\-1*2%2p10::%4+g00:\g36\g35-1_v
#11^$_83p73v >1+:41g`!#v_$,1+:43g`!#v_@>->2>+00p+141^_
<p1^     vp< ^,g+7g36:<<<<1+55p36:<<<< ^1?0^#7g36g35*
8&p|!++!%9#2g+7g10\*!-g38g10!-g37:g00!!*<>3^
443>:!#v_>>1-::3%1-:53g+00p\3/1-:63g+01p^
^>^>>$#<"#"53g63g7+p41g53g-43g63g-+!#^_

```

Try it online!

As @flawr mentioned in their MATLAB answer, this may take some time if the field size is of any non-trivial size. In fact it's quite easy to get into a situation where it's really not worth trying to wait for it to finish, because you're quite likely to be waiting until the end of time.

To understand why this happens, it helpful to view the program as it's executing in one of Befunge's many "visual debuggers". Since data and code are the same thing in Befunge, you'll get to view the path as it changes over time. For example, here is a short animation showing what a part of a run on a slow path might look like.

Once the algorithm decides to make that fateful turn to the left at the bottom of the field boundary, it has essentially condemned itself to a lifetime of aimless wandering. From that point on it has to follow every single possible path in that fenced off area before it can back out and try the turn to the right. And the number of potential paths in these cases can easily become astronomical.

Bottom line: If it seems to be taking a long time, it's probably a good idea to just abort the execution and start again.

**Explanation**

This is basically a recursive algorithm, trying every possible path through the field, and then unwinding steps that have already been followed whenever it gets stuck. Since Befunge doesn't have the concept of functions, a recursive function is out of the question, but we can emulate the process by tracking the state on the stack.

This works by populating the stack with potential coordinates that we may want to follow. Then we pull one set from the stack and check whether it is suitable (i.e. in range and not overlapping with an existing path). Once we've got a good spot, we write a `#` into the playfield at that location, and add those details to the stack in case we need to backtrack later.

We then push an additional four sets of coordinates onto the stack (in random order) indicating the potential paths we can take from this new location, and jump back to the start of the loop. If none of the potential paths are feasible, we'll get to the point on the stack where we saved the location of the `#` we wrote out, so we'll undo that step and continue trying potential coordinates from one step prior.

This is what the code looks like with the various component parts highlighted:

Read the width and height of the field, and push the start coordinates along with a `0` type marker to indicate a potential path rather than a backtracking location.
Check for backtracking locations (indicated by a `1` type marker) which are reverted with a simple `p` command, since they're stored in the exact format needed to write a space back into the playfield.
Check if the coordinates are still inside the playfield. If they're out of range, drop them from the stack and loop back to try the next potential coordinates.
If they are in range, get the next two values from the stack, which is the location of the previous step (required in the test that follows this).
Check if the coordinates are going to come into contact with an existing segment of the path. The location of the previous step is obviously ignored from this check.
If all test are successful, write a `#` into the playfield, and check if we've reached the destination location.
If we have, write out the final path, and exit.
Otherwise save the coordinates onto the stack with a `1` type marker for later backtracking.
This is interrupted with a random number calculation which we're going to need soon.
Push four potential destinations that can be reached from the current location. The random number determines the order in which they're pushed and thus the order that they will be followed.
Wrap back to the start of the main loop and process the next values on the stack.

# Answer
> 2 votes
# QBasic, 259 bytes

I sure love `GOTO`s.

```
RANDOMIZE TIMER
INPUT w,h
DO
CLS
x=1
y=1
REDIM a(w+3,h+3)
2a(x+1,y+1)=1
LOCATE y,x
?"#"
d=INT(RND*4)
m=1AND d
x=x+m*(d-2)
y=y-d*m+m+d-1
c=a(x,y+1)+a(x+2,y+1)+a(x+1,y)+a(x+1,y+2)=1
IF(x=w)*c*(y=h)GOTO 9
IF(x*y-1)*x*y*c*(x<=w)*(y<=h)GOTO 2
LOOP
9LOCATE y,x
?"#"

```

Basic strategy: at each step, print a `#` to the current location and move in a random direction. An array `a` of 0s and 1s keeps track of where we've been. If the move is legal and takes us to the endpoint, `GOTO 9` to exit the loop and print the final `#`. Else, if the move is legal, take another step. Else, clear the screen and start over (much golfier than coding a backtracking algorithm!).

Tested on my laptop in QB64, this generally produces a result for `9, 9` in five seconds or less. Runs of `10, 10` have taken anywhere between three and 45 seconds. Theoretically, all legal paths have non-zero probability, but the probability of a path with large curves is vanishingly small. I have occasionally seen paths with one or two small curves, though:

Ungolfed version and/or in-depth explanation available on request.

# Answer
> 2 votes
# R, 225 bytes

```
function(x,y){library(igraph);a=matrix(rep(" ",x*y),c(y,x));g=make_lattice(c(y,x));w=runif(ecount(g));for (i in 1:2){v=shortest_paths(g,1,x*y,weights=w)$vpath[[1]];w[]=1;w[E(g)[v%--%v]]=0;};a[v]="#";cat(rbind(a,"\n"),sep="")}

```

Explanation:

We generate a regular (lattice) \[x * y\] undirected graph with random weigths on edges then we find the shortest path from the start to the end. However in the generated path there may be cells that have more than two neigbors for example:

```
#
#
####
  ##
  #
  ###

```

So we should apply the shortest path algorithm two times. In the second time we set all weights to 1 except those that are in the current found path that set to 0;

result

```
#
#
###
  #
  #
  ###

```

Ungolfed:

```
function(x,y){
    library(igraph);#igraph library should be installed
    a=matrix(rep(" ",x*y),c(y,x));#ASCII representation of the graph
    g=make_lattice(c(y,x));# regular graph
    w=runif(ecount(g));#weights
    for (i in 1:2){
        #find vertices that are in the path
        v=shortest_paths(g,1,x*y,weights=w)$vpath[[1]];
        #set all weights to 1 except those that are in the current found path that set to 0
        w[]=1;
        w[E(g)[v%--%v]]=0;
    }
    a[v]="#";
    cat(rbind(a,"\n"),sep="")
}

```

# Answer
> 1 votes
## JavaScript (ES7), ~~333~~ ~~331~~ ~~330~~ ~~329~~ ~~324~~ ~~318~~ 312 bytes

```
f=
(h,w,c=[...Array(h)].map(_=>Array(w).fill` `),g=a=>{for(z of b=[[[h-1,w-1]]])a.map(([x,y])=>b.every(([[i,j]])=>i-x|j-y)&(z[0][0]-x)**2+(z[0][1]-y)**2<2&&b.push([[x,y],...z]));return b.find(([[x,y]])=>!x&!y)||g([...a,[h,w].map(n=>Math.random()*n|0)])})=>g([]).map(([x,y])=>c[x][y]=`#`)&&c.map(a=>a.join``).join`
`
```

```
Height: <input type=number min=1 id=h>Width: <input type=number min=1 id=w><input type=button value="Generate!" onclick=o.textContent=f(+h.value,+w.value)><pre id=o>
```

Expanation: `#`s are randomly placed in the array until a path is found through the field using a breadth-first search; the first, and therefore shortest, such path is then output; this guarantees that the path does not intersect itself. Note that particularly for larger fields it's possible to exceed the JS engine's stack before a path is found. Ungolfed:

```
function r(n) {
    return Math.floor(Math.random() * n);
}
function f(h, w) {
    var a = []; // array of placed #s
    var b; // breadth-first search results
    var c;
    do {
        a.push([r(h), r(w)]); // place a # randomly
        b = [[[h - 1, w - 1]]]; // start from bottom right corner
        for (z of b) // breadth-first search
            for ([x, y] of a) // find possible next steps
                if (!b.some(([[i, j]]) => i == x && j == y))
                    if ((z[0][0] - x) ** 2 + (z[0][1] - y) ** 2 < 2)
                        if (x || y)
                            b.push([[x, y], ...z]); // add to search
                        else if (!c)
                            c = [[x, y], ...z]; // found path
    } while (!c);
    a = [...Array(h)].map(() => Array(w).fill(' '));
    for ([x, y] of c) // convert path to output
        a[x][y] = '#';
    return a.map(b => b.join('')).join('\n');
}

```

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


title: Find the greatest line

text:
# Question
Title: Find the greatest line
You will be given a 2-D array A of integers, and a length N. Your task is to find within the array the straight line (horizontal, vertical or diagonal) of N elements that yields the highest total sum, and return that sum.

### Example

```
 N = 3, A =
 3    3    7    9    3
 2    2   10    4    1
 7    7    2    5    0
 2    1    4    1    3

```

This array has 34 valid lines, including

```
 Vertical
 [3]   3    7    9    3
 [2]   2   10    4    1
 [7]   7    2    5    0
  2    1    4    1    3       [3,2,7] = 12
 Horizontal
  3    3    7    9    3
  2    2   10    4    1
  7    7   [2]  [5]  [0]
  2    1    4    1    3       [2,5,0] = 7
 Diagonal
  3    3   [7]   9    3
  2    2   10   [4]   1
  7    7    2    5   [0]
  2    1    4    1    3       [7,4,0] = 11

```

The maximum line is

```
 3    3    7   [9]   3
 2    2  [10]   4    1
 7   [7]   2    5    0
 2    1    4    1    3        [7,10,9] = 26

```

Note: lines may not wrap around the edges of the array.

### Inputs

* A X by Y 2-D array A, with X,Y \> 0. Each element of the array contains an integer value which may be positive, zero or negative. You may accept this array in an alternative format (e.g. list of 1-D arrays) if you wish.
* A single, positive integer N, no greater than max(X,Y).

### Output

* A single value representing the maximal line sum that can be found in the array. Note that you do **not** need to provide the individual elements of that line or where it is located.

### Test cases

```
N = 4, A =
-88    4  -26   14  -90
-48   17  -45  -70   85
 22  -52   87  -23   22
-20  -68  -51  -61   41
Output = 58

N = 4, A =
 9    4   14    7
 6   15    1   12
 3   10    8   13
16    5   11    2
Output = 34

N = 1, A =
 -2
Output = -2

N = 3, A =
1    2    3    4    5
Output = 12

N = 3, A =
-10   -5    4
 -3    0   -7
-11   -3   -2
Output = -5

```

# Answer
# Jelly, 15 bytes

```
,ZṚ¥;ŒD$+⁹\€€FṀ

```

Try it online!

### How it works

```
,ZṚ¥;ŒD$+⁹\€€FṀ  Main link. Left argument: M (matrix). Right argument: n (integer)

 ZṚ¥             Zip/transpose and reverse M. This is equivalent to rotating M 90°
                 counterclockwise.
,                Pair M and the result to the right.
    ;ŒD$         Append the diagonals of both matrices to the pair.
        +⁹\€€    Take the sums of length n of each flat array.
             FṀ  Flatten and take the maximum.

```
> 10 votes

# Answer
# Wolfram Language (Mathematica), 73 bytes

```
Max[Tr/@Join[#,#,{#,Reverse@#}]&/@Join@@Partition[#2,{#,#},1,1,-∞]]&

```

Try it online!

## How it works

Takes first `N` and then the matrix `A` as input.

`Join@@Partition[#2,{#,#},1,1,-∞]` finds every `N` by `N` submatrix of the matrix `A`, padded with `-∞` where necessary to ensure that lines running out of the grid will be out of the running.

For each of those blocks we compute `Tr/@Join[#,#,{#,Reverse@#}]`: the trace (i.e. sum) of each row, the trace (i.e. sum) of each column, the trace (*actually* the trace, for the first time in the history of Mathematica code golfing) of the block, and the trace of the block reversed. `#` is `Transpose@#`.

Then we find the `Max` of all of these.
> 6 votes

# Answer
# Mathematica, ~~135~~ 123 bytes

```
Max[(s=#;r=#2;Max[Tr/@Partition[#,r,1]&/@Join[s,s~Diagonal~#&/@Range[-(t=Tr[1^#&@@s])+2,t-1]]])&@@@{#|#2,Reverse@#|#2}]&

```

Try it online!
> 4 votes

# Answer
# Jelly, 16 bytes

```
µ;Z;Uµ;ŒDðṡ€ẎS€Ṁ

```

Try it online!
> 3 votes

# Answer
# JavaScript, ~~151~~ 129 bytes

```
a=>n=>a.map((l,x)=>l.map((v,y)=>[...'01235678'].map(d=>m=(g=i=>i--&&g(i)+(a[x+d%3*i-i]||[])[y+i*~-(d/3)])(n)>m?g(n):m)),m=-1/0)|m

```

Curry function takes two arguments, first one is an array of array of numbers, second one is a number.

Thanks to Arnauld, save 20+ bytes.

```
f=

a=>n=>a.map((l,x)=>l.map((v,y)=>[...'01235678'].map(d=>m=(g=i=>i--&&g(i)+(a[x+d%3*i-i]||[])[y+i*~-(d/3)])(n)>m?g(n):m)),m=-1/0)|m
```

```
<p><label>N = <input id="N" type="number" min="1" value="3" /></label></p>
<p><label>A = <textarea id="A" style="width: 400px; height: 200px;"> 3    3    7    9    3
 2    2   10    4    1
 7    7    2    5    0
 2    1    4    1    3
</textarea></label></p>
<input value="Run" type="button" onclick="O.value=f(A.value.split('\n').filter(x=>x.trim()).map(x=>x.trim().split(/\s+/).map(Number)))(+N.value)" />
<p>Result = <output id="O"></output></p>
```
> 3 votes

# Answer
# Jq 1.5, 211 bytes

```
def R:reverse;def U:[range(length)as$j|.[$j][$j:]]|transpose|map(map(select(.))|select(length>=N));def D:U+([R[]|R]|U|map(R)[1:]);[A|.,transpose,D,(map(R)|D)|.[]|range(length-N+1)as$i|.[$i:$i+N]]|max_by(add)|add

```

Expects input in `N` and `A`, e.g:

```
def N: 3;
def A: [
  [ 3, 3,  7, 9, 3 ],
  [ 2, 2, 10, 4, 1 ],
  [ 7, 7,  2, 5, 0 ],
  [ 2, 1,  4, 1, 3 ]
];

```

Expanded

```
def chunks:      .[] | range(length-N+1) as $i | .[$i:$i+N] ;
def flip:        [ reverse[] | reverse ] ;
def upperdiag:   [ range(length) as $j | .[$j][$j:] ] | transpose | map(map(select(.))|select(length>=N)) ;
def lowerdiag:   flip | upperdiag | map(reverse)[1:] ;
def diag:        upperdiag + lowerdiag ;
def allchunks:   A | ., transpose, diag, (map(reverse)|diag) | chunks ;

[allchunks]|max_by(add)|add

```

Note this challenge is basically the same as Project Euler problem 11

Try it online!
> 2 votes

# Answer
# Python 2, ~~208~~ ~~184~~ ~~183~~ 176 bytes

* Saved 24 bytes by using `-float("inf")` to represent that the checked line reached outside the matrix instead of computing the negative sum of all matrix elements.
* Saved a byte by defining `R,L=range,len` to shorten built-in functions and using `y in R(L(A))...R(L(A[y]))` instead of `y,Y in e(A)...x,_ in e(Y)`.
* Saved seven bytes by golfing `float("inf")` to `9e999`.

```
lambda N,A:max(sum(A[y+q*j][x+p*j]if-1<x+p*j<L(A[y])>-1<y+q*j<L(A)else-9e999for j in R(N))for y in R(L(A))for x in R(L(A[y]))for p,q in[(1,0),(0,1),(1,1),(1,-1)]);R,L=range,len

```

Try it online!

# Explanation

```
lambda N,A:                                                                                ;R,L=range,len # lambda function, golfed built-ins
           max(                                                                                )               # return the maximum line sum
                                                                                for y in R(L(A))                                                                       # loop through matrix rows
                                                                                for x in R(L(A[y]))                                                    # loop through matrix columns
                                                                                for p,q in[(1,0),(0,1),(1,1),(1,-1)]                # loop through four directions; east, south, south-east, north-east
               sum(                                                                      )                                                                                # matrix line sum
                                                                            for j in R(N)                                                                                # loop through line indices
                                  if-1<x+p*j<L(A[y])>-1<y+q*j<L(A)                                                                                # coordinates inside the matrix?
                   A[y+q*j][x+p*j]                                                                                # true; look at the matrix element
                                                                  else-9e999                                                                                # false; this line cannot be counted, max(...) will not return this line

```
> 1 votes

# Answer
# , 199 bytes

```
function(m,n,i=1,j=1){y=1:n-1
x=j-y;x[x<1]=NA
y=i-y;y[y<1]=NA
'if'(i>nrow(m)|j>ncol(m),NA,max(c(v(m[i,x]),v(m[y,j]),v(m[b(y,x)]),v(m[b(y,rev(x))]),f(m,n,i+1,j),f(m,n,i,j+1)), na.rm=T))}
v=sum
b=cbind

```

Try it online!

A recursive solution. For each element (i,j) of the matrix it returns the max between the sum along the row, the sum along the column, the sum along either diagonal, and the result of the function applied to (i+1,j) and (i,j+1). Results for the test cases are shown in the TIO.
> 1 votes

# Answer
# Husk, 14 bytes

```
▲mΣṁX⁰ṁëIT∂(∂↔

```

Try it online!

Thanks to the new anti∂iagonals builtin this is a quite short answer :)
> 1 votes

# Answer
# JavaScript 170 bytes

still wip on the golf part added 4 more chars because i didnt managed a case where the max is negative and N is bigger than 1

```
M=-1e9
G=(A,N)=>eval(`for(y in m=M,A)
for(x in R=A[y])
{for(a=b=c=d=j=0;j<N;d+=Y[x-j++])
{a+=R[X=+x+j]
b+=(Y=A[+y+j]||[])[x]
c+=Y[X]}
m=Math.max(m,a||M,b||M,c||M,d||M)}`)

console.log(G([ [3,3,7,9,3],
 [2,2,10,4,1],
 [7,7,2,5,0],
 [2,1,4,1,3]],3)==26)

 console.log(G([[-88,4,-26,14,-90],
[-48,17,-45,-70,85],
[22,-52,87,-23,22],
[-20,-68,-51,-61,41]],4)==58)

console.log(G([[9,4,14,7],[6,15,1,12],[3,10,8,13],[16,5,11,2]],4)==34)

console.log(G([[-2]],1)==-2)
console.log(G([[1,2,3,4,5]],3) ==12)
```
> 0 votes

# Answer
# Python 2, ~~222~~ 218 bytes

```
n,a=input()
W=len(a[0]);Q=['']*W;R=range;a+=[Q]*n
for l in a:l+=Q
print max(sum(x)for y in[zip(*[(a[j][i+k],a[j+k][i],a[j+k][i+k],a[j+k][i+n+~k])for k in R(n)])for j in R(len(a)-n)for i in R(W)]for x in y if''not in x)

```

Try it online!
> 0 votes

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