# Question
Title: Convert from base 10 to base 2 without built-in base conversions
**Background**:

> You have been given an assignment to convert base 10 numbers to base 2 without using any premade base conversion functions. You can't use any imported libraries either.

**Problem**:

Convert an input string from base 10 (decimal) to base 2 (binary). You may not use any premade base conversion code/functions/methods, or imported libraries. Since this is , the shortest answer in bytes will win.

Input will be anything from -32768 to 32767 (include sign byte handling in your code)

# Answer
> 4 votes
## GolfScript - 17 bytes

```
~{.1&\2/}16*;]-1%

```

Not too much more verbose than the built-in `~2base`.

# Answer
> 12 votes
# JavaScript, 46

```
for(x=prompt(o='');x;x>>>=1)o=(x&1)+o;alert(o)

```

# Answer
> 5 votes
# Brainf\*ck, 98 77

Obviously this isn't for the purpose of winning but what would a competition be if it didnt have a brainfk solution

```
++++[>++++<-]>>,<[->>++<[->-[>+>>]>[+[-<+>]>+>>]<<<<<]>[-]++++++[->++++++++<]>.[-]>[-<<<+>>>]<<<<]

```

Since brainfk can only handle 8bit integers and no negatives I guess it doesn't fully abide by the rules but hey I was never in it to win it.

This actually does work for 16-bit input if your interpreter supports

I even got it to output in ascii values

Here is the annotated code:

```
++[>++++<-]                       preload 8 onto cell 1
>>,<                                input into cell 2
[-                                  iterate over cell 1
    >>++<                               put 2 in cell 3
    [->-[>+>>]>[+[-<+>]>+>>]<<<<<]      division algorithm: converts {n d} into {0 d_minus_n%d n%d n/d}
    >[-]++++++[->++++++++<]>           clears cell 4 and puts 48(ascii of 0) into cell 5
    .[-]                                output n%2 and clear it (the bit)
    >[-<<<+>>>]                         bring n/2 into cell 2 (to be used for division in next iteration)
<<<<]                               end iterate

```

Shorter algorithm (77):

```
+>,>-<[>>[->]++[-<+]-<-]++++++++[->++++++<]>+[->+>+>+>+>+>+>+>+<<<<<<<<]>[.>]

```

This one can only handle 8bit integers.

The algorithm works by using a binary counter which is actually very short (one increment is `>[->]++[-<+]-<-` which then lays out the bits. The issue is that it is difficult to print out all of the bits

That last algorithm can be adapted to fit any number of bits at the expense of bytes. To be able to deal with N bit integers, it requires 53+3\*N bytes to encode.

examples:

```
(1 bit) +>,>-<[>>[->]++[-<+]-<-]++++++++[->++++++<]>+[->+<]>[.>]
(2 bit) +>,>-<[>>[->]++[-<+]-<-]++++++++[->++++++<]>+[->+>+<<]>[.>]
(3 bit) +>,>-<[>>[->]++[-<+]-<-]++++++++[->++++++<]>+[->+>+>+<<<]>[.>]
etc

```

# Answer
> 3 votes
## Mandatory APL answer - 21 ~~22~~

```
"01"[1+2|⌊⎕÷2⋆⊖0,⍳15]

```

Examples:

```
      "01"[1+2|⌊⎕÷2⋆⊖0,⍳15]
⎕: 0
0000000000000000
      "01"[1+2|⌊⎕÷2⋆⊖0,⍳15]
⎕: 13
0000000000001101
      "01"[1+2|⌊⎕÷2⋆⊖0,⍳15]
⎕: 9999
0010011100001111
      "01"[1+2|⌊⎕÷2⋆⊖0,⍳15]
⎕: -3
1111111111111101
      "01"[1+2|⌊⎕÷2⋆⊖0,⍳15]
⎕: 32767
0111111111111111

```

# Answer
> 3 votes
# Turing Machine Code, 272 bytes

As usual, I'm using the rule table syntax defined here. You can test it on that site or, alternatively, using this java implementation.

A lot of the code is copied from my decimal-to-hex converter here.

```
0 * * l B
B * * l C
C * 0 r D
D * * r E
E * * r A
A _ * l 1
A * * r *
1 0 9 l 1
1 1 0 l 2
1 2 1 l 2
1 3 2 l 2
1 4 3 l 2
1 5 4 l 2
1 6 5 l 2
1 7 6 l 2
1 8 7 l 2
1 9 8 l 2
1 _ * r Y
Y * * * X
X * _ r X
X _ _ * halt
2 * * l 2
2 _ _ l 3
3 * 1 r 4
3 1 0 l 3
4 * * r 4
4 _ _ r A

```

Counts down from the input in base 10 while counting up from 0 in base 2. On decrementing zero, it erases the input block and terminates.

# Answer
> 3 votes
# Dyalog APL, 11 bytes

```
2|⌊⎕÷2*⌽⍳16

```

`2|` The division remainder when halved of
the rounded down value of
the input
`÷` divided by each of
`2*` two to the power of each of
`⍳16` {0, 1, 2, ..., 15}

Requires `⎕IO←0` which is default on many systems.

TryAPL online!

# Answer
> 2 votes
## Javascript 59

```
o='';i=parseInt(prompt());do{o=(i&1)+o}while(i>>=1)alert(o)

```

# Answer
> 2 votes
## Perl, 44

This is my first Perl program ever, so please forgive me if this can be easily golfed down further. Edit: Thank you @primo for taking 7 chars away from my answer.

```
$x=<>;do{@s=($x&1,@s)}while($x>>=1);print@s

```
~~```
$x=<>;do{push@s,$x&1}while($x>>=1);print reverse@s

```~~

The logic is essentially the same as my previous C solution.

Also, uses 64 bits.

# Answer
> 2 votes
# Javascript - ~~56~~ 48 and ~~36~~ 28 characters

* Does not works with negative numbers.

Thanks to @Blender for shaving 8 characters.

This form takes input and shows output, 48 characters:

```
x=prompt();for(a="";x;x=~~(x/2))a=x%2+a;alert(a)

```

If just an instruction that puts in a variable `a` the binary form of a variable `x` is needed (and you don't bother in destroying the `x` value as a side-effect), here it is with 28 characters:

```
for(a="";x;x=~~(x/2))a=x%2+a

```

# Answer
> 2 votes
## C, 55 chars

Prints an extra leading zero (for the sake of 2 bytes).
Recursion within `printf` reverses the print order, so the algorithm extracts bits right-to-left but prints left-to-right.

*EDIT*: Saved a char by using `putchar` instead of `printf`.

```
f(x){(x*=x<0?-printf("-"):1)&&f(x/2);putchar(48+x%2);}

```

# Answer
> 2 votes
# Python - ~~61~~ 60 characters

```
x=input();print"".join("01"[x>>i&1]for i in range(15,-1,-1))

```

# Answer
> 2 votes
# Excel, ~~91 90 81~~ 74

Trailing parens already discounted.

Compatibility note: `CONCAT()` was available only after later versions of 2016. It replaced `CONCATENATE()`. Tested in Excel online.

## Formulae

* `A1` \- Input
* `B1` \- `=A1+4^8*(A1<0)` (13) - Convert to 16-bit unsigned equivalent.
* `B2` \- `=1+INT(LOG(B1,2))` (15) - Number of binary digits + 1

## Code (46):

Convert `B1` to binary.

```
=IF(A1=0,0,CONCAT(--ISODD(B1/2^(B2-SEQUENCE(B2)))))

```

Works in the full 16-bit range.

# Answer
> 1 votes
## C, 81

```
char b[17];i=15;main(x){scanf("%d",&x);while(i+1)b[i--]=(x&1)+48,x>>=1;puts(b);}

```

The output has strictly 16 bits (including padding zeros)

# Answer
> 1 votes
# Bash, 44

```
f=b+=n/2**e%2*10**e,2**e++/n?f=b:f;echo $[f]

```

Pass an input value to the script through the environment variable `n`. The decimal representation of the binary result cannot exceed `LONG_MAX`.

This should also be compatible with `ksh93` and `zsh` if `b` and `e` are initialized to `0` and proper arithmetic expansion is used.

# Answer
> 1 votes
# Apps Script + Google Sheets, ~~147~~ ~~144~~ 121 bytes

### Script

```
function j(decNumb){var str='';do{str=String(decNumb%2)+str;decNumb=decNumb/2|0;}while(decNumb>=1);return parseInt(str);}

```

### Sheet

```
=j(b1)

```

Modified version of this script by ZygD.

# Answer
> 1 votes
# Haskell, 66 bytes

```
c 0=0
c n=c(div n 2)*10+mod n 2
b('-':r)='-':b r
b r=show.c.read$r

```

Call with `b "-1023"`, add `main=interact b` for a complete program or try it on Ideon.

`c` performs the conversion for positive integers.
`b r=show.c.read$r` converts a string to a number, applies `c` and converts back to string.
`b('-':r)='-':b r` strips a possible leading `-` and re-appends it to the result.

# Answer
> 1 votes
# PowerShell, ~~59~~ ~~87~~ ~~82~~ 70 bytes

+28 bytes for supporting negative numbers.
-12 bytes thanks to @ASCII-only

```
param($d)$m=$d-lt0;while($d){$n="01"[$d%2]+$n;$d=($d-$d%2)/2}'-'*$m+$n

```

Try it online!

Adapted from this code. Takes input through a commandline parameter `-d`.

# Answer
> 1 votes
# APL(NARS), 17 chars, 34 bytes

```
{2∣⌊⍵÷2*(⍺-1)..0}

```

It is a copy and modify of Adam answer https://codegolf.stackexchange.com/a/90107 in the way one can add the parameter for the bits lenght, and ⎕IO for this function (here is ⎕IO=1) should have no importance...

```
  f←{2∣⌊⍵÷2*(⍺-1)..0}
  16 f 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
  32 f 2
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
  32 f ¯1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  16 f ¯1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
  64 f ¯12345678
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0

```

it seeme easy handle the number of bits in this way (I cheked that last result should be right)

# Answer
> 0 votes
# Smalltalk (Smalltalk/X), 63/78

the first version creates an intermediate string (78):

```
t:=Number readFrom:Stdin.
((15to:1by:-1)collect:[:i|$0+(t>>i&1)]as:String)print

```

actually, there is no need to create the string; just output the chars (63):

```
t:=Number readFrom:Stdin.
15to:1by:-1 do:[:i|($0+(t>>i&1))print]

```

mhmh - is there a shorter way to read to a number?

# Answer
> 0 votes
# Python 3.x: 65 characters

```
b=lambda n:n<2 and'01'[n]or b(n//2)+b(n%2);print(b(int(input())))

```

# Answer
> 0 votes
# C# - 104

```
string p(int d){var r="";long i=1;while(r.Length<=64){var g=d&i;r=(g!=0)? "1"+r:"0"+r;i=i<<1;}return r;}

```

This method will convert decimal to binary up to `64` bits.

When executed the above method in Linqpad - rr = p(-32768); rr.Dump();

Output: `01111111111111111111111111111111111111111111111111000000000000000`

# Answer
> 0 votes
# Java 10, ~~80~~ ~~71~~ 57 bytes

```
n->{var r="";for(n=n<0?-n:n;n>1;n/=2)r=n%2+r;return n+r;}

```

-9 bytes due to a rule in the comments.. Negative base-10 inputs may return the positive/absolute base-2 value as output apparently.

**Explanation:**

Try it online.

```
n->{                   // Method with integer parameter and String return-type
  var r="";            //  Result-String, starting empty
  for(n=n<0?-n:n;      //  Transform the input to its absolute value
      n>1;             //  Loop as long as `n` is still >= 2:
      n/=2)            //    After every iteration: integer-divide `n` by 2
    r=n%2+r;           //   Prepend `n` modulo-2 to the result
  return n             //  Return the last `n`
         +r;           //  appended with the result

```

# Answer
> 0 votes
# Small Basic, 133 bytes

A script that inputs from and outputs to the `TextWindow` console.

```
n=TextWindow.Read()
While n>0
c=c+1
x[c]=Math.Remainder(n,2)
n=Math.Floor(n/2)
EndWhile
For i=0To c-1
TextWindow.Write(x[c-i])
EndFor

```

Try it at SmallBasic.com *Requires Silverlight and thus must be run in IE.*

I/O is taken/given from the black console.

-22 bytes thanks to @Neil

# Answer
> 0 votes
# C (gcc), ~~50~~ 43 bytes

-7 bytes thanks to ceilingcat.

```
f(n){printf("-%d"+(~n?n&&f(n/2),1:0),n&1);}

```

Try it online!

# Answer
> 0 votes
# Kotlin, 82 bytes

```
{s:String->{var i=s.toInt()
var r=""
(0..15).map{r="${i and 1}$r"
i=i shr 1}
r}()}

```

Try it online!

# Answer
> 0 votes
# MATL, ~~15~~ 17 bytes

```
t0<?16Ww+]`2&\t]x

```

Try it on MATL Online

TIO

*(+2 bytes removing leading 0 for negative numbers, sign bit should be the first bit.)*

Output on MATL Online should be read bottom-up (MSB is at the bottom).

The main part is pretty simple: ``2&\t` = while the value is greater than 0, divide by 2 and accumulate the remainders.

Handling negative numbers and giving them 2's complement representation was the tricky part. In the end I went with the "subtract from \\$ 2^N \\$" method of getting a number's two's complement. Since we're only required to handle values upto -32768, for negative numbers the code creates \\$ 2^{16} = 65536 \\$ with `16W`, adds the input to that (eg. 65536 + (-42)), which gives something MATLAB sees as a positive number but represents the input's signed binary representation in 16-bit form.

# Answer
> 0 votes
# PowerShell, 43 bytes

```
param($n)15..0|%{$r+='01'[($n-shr$_)%2]}
$r

```

Try it online!

# Answer
> 0 votes
# \>\<\>,  ~~34~~  33 bytes

```
|!/?=0:,2-}:%2:+***"  @"(0:
n{\~{

```

Try it online!

# Answer
> 0 votes
# ///, 124 bytes

```
/~/\/\///9/8*~8/7*~7/6*~6/5*~5/4*~4/3*~3/2*~2/1*~1/0*~*0/9*~0~/*/>Oⅼ~ⅼ>/ⅼ~ⅼO/Oⅼ~Oⅼⅼ/ⅼ\O~Oⅼ/_ⅼ~_~/>O/>~>~

```

Try it online!

Could be considered cheating, Outputs  and `O` instead of `1` and `0`, due to the mechanics of `///`.

Uses examples from the wiki.

# Answer
> 0 votes
# Perl 5, 26 bytes

Produces an additional leading `0` which can be avoided with two additional bytes (appending `}{`)

```
$\=($_&1).$\;redo if$_>>=1

```

Try it online!

# Answer
> 0 votes
# Clojure 129 bytes#

Golfed version:

```
(defn p[n](loop[m 32768](if(> m 0)(do(if(= 0(bit-and m n))(print"0")(print"1"))(recur(unsigned-bit-shift-right m 1)))(println))))

```

Ungolfed:

```
(defn print-as-binary [n]
  (loop [mask  32768]
    (if (> mask 0)
      (do
        (if (= 0 (bit-and mask n))
          (print "0")
          (print "1"))
        (recur (unsigned-bit-shift-right mask 1)))
      (println))))

```

# Answer
> 0 votes
# PostgreSQL, 184 bytes

```
WITH RECURSIVE t(a,b,c)AS(SELECT abs($1),0,0 UNION ALL SELECT a/2,a%2,1from t where a>0)select case when $1<0then '-'else ''end||string_agg(b::text,''order by a)from t where c>0OR $1=0

```

137 bytes if only handling positive numbers

```
WITH RECURSIVE t(a,b,c)AS(SELECT $1,0,0 UNION ALL SELECT a/2,a%2,1from t where a>0)select string_agg(b::text,''order by a)from t where c>0

```

Input is given as an integer query parameter (using the extended query protocol or by wrapping in a function) and output is given as a string.

---
Tags: code-golf, number
---


title: Find acronym-like words in a sentence

text:
# Question
Title: Find acronym-like words in a sentence
Let's say you have a sentence like:

```
this is a very long sentence with several words of no significance

```

It contains only the 26 lowercase letters of the alphabet and spaces.

And you have a dictionary, where each word contains any number of the 26 lowercase letters and nothing else:

```
henge
renton

```

Then the output should contain, among others:

* t**H**is is a v**E**ry long se**N**tence with several words of no si**G**nificanc**E**
* t**H**is is a v**E**ry long sente**N**ce with several words of no si**G**nificanc**E**
* this is a ve**R**y long s**ENT**ence with several w**O**rds of no significa**N**ce

So, every line of the output is the original sentence, but if only the uppercase letters of a line are taken, they should form a dictionary word. The program should find all possible such lines.

# Answer
# JavaScript, 474 bytes

```
k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

```

**Live example:**

```
k=((e,r)=>{for(o=[],e=[...e],r=[...r],w=r.reduce((r,h,n)=>!(r[n]=e.map((e,r)=>h==e?r:"").filter(Number))||r,[]),[z]=w,h=[],x=0;x<w.reduce((e,r)=>e*=r.length||e,1);x++)z.forEach((e,r)=>{for(g=[z[r]],j=1;j<w.length;j++)for(n=w[j],y=0;y<n.length;y++)if(g.slice(-1)[0]<n[y]&&!h.some(e=>e.toString()==[...g,n[y]].toString())){g.push(n[y]);break}h.push(g)});return h.filter(e=>e.length==w.length).forEach(r=>{d=[...e],r.forEach(e=>d[e]=d[e].toUpperCase()),o.push(d.join(""))}),o})

console.log(k('this is a very long sentence with several words of no significance', 'henge'));
```

**Explanation:**

For each letter in the word, an array of indices is constructed corresponding to every position of that letter in the sentence.

Then inside a nest of 4 `for` loops, every possible path from the first array to the last array is computed, where each step is into an element with greater numeric value in the next array.

This produces an array of paths whose length is equal to the maximum possible paths, which is the product of multiplying the length of each letter indices array (this number gets big real quick as the length of the word increases).

Then all paths whose length is smaller than the word are excluded, since they failed to find a valid step between each array.

You can see the unminified logic at this stackoverflow answer.

I am confused by this line (even though it's my code), whose intent is to check the existing paths before adding a step to the current path to make sure its constructing a unique path:

```
if (!paths.some(p => p.toString() == [...path, arrays[j][y]].toString())) {
  path.push(arrays[j][y]);
  break;
}

```

It seems to me like this should erroneously prevent construction of multiple paths who share any beginning steps. But it actually works as intended. So I am stumped.
> 2 votes

# Answer
# Python 3, 169 bytes

```
a=lambda c,w:(([c[0]+k for k in a(c[1:],w)]+([c[0].upper()+k for k in a(c[1:],w[1:])]if c[0]==w[0]else[]))if c else[])if w else[c]
lambda c,d:sum((a(c,w)for w in d),[])

```

Takes as input the sentence as a string and the dictionary as a list of strings. Uses a recursive helper function `a(c,w)` to compute the output for each word in the dictionary at a time, then sums the lists together to get the final output. The helper function works through the sentence/word one character at a time, and has several cases:

1. No more characters in the word, return what's left of the sentence
2. No more characters in the sentence, return empty list
3. Characters left in both, return same results as `a(c[1:],w)`, with `c[0]` prepended to each result.
4. Characters left in both, **and** beginning characters match, return (3.) in addition to `a(c[1:],w[1:])`, with `c[0].upper()` prepended to each result.

There's definitely a few bytes of savings to be had in the helper method; I wasn't being super careful with my parentheses around the inline `if`-expressions (and the precedence is slightly confusing) -- I might take a closer look tomorrow to see if I can shave off a few bytes.
> 1 votes

# Answer
# Perl 5 `-pF`, 96 bytes

Takes the sentence as the first input and all subsequent inputs are treated as the dictionary. Could produce the strings in the reverse order for +1 byte. I still feel there's room to golf this...

```
$"=").*(";m#(@{[<>=~/./g]})(?{$a=%h=();$h{$_}++for@-;map$\.=$h{$a++}?uc:lc,@F})(?!)# while!eof}{

```

Try it online!

## Explanation

This script uses Perl's regex engine to perform the matching.

First `$"` is set to `).*(`, this is the separator that's used when lists are interpolated. A `m//`atch is then started (with `#` as the delimiter) which contains the current input dictionary word (`<>`), interpolated (`@{[...]}`) into the match as as a list (`=~/./g`). Example.

The next part of the `m//` operation is a zero-length code block. In here there is access to all the magic variables associated with regex (`$&`, `$1`, etc). `$a` and `%h` are initialised as empty (`()` \- technically `$a` is set to the length, which is `0`) and `@-`, which contains the start of each matched group, is used to populate the indices of `%h` with `1` (`++`) for the position of all the matches.

Finally, `@F` (which is automatically filled with the chars from the input via `-F`) is looped over `while` there's still input (`!eof`), checking `%h`'s key `$a` (incremented for each char in `@F`) to see if it's truthy (`1`) or not (`undef` for missing key). If it's truthy `uc` returns (its operand, or `$_` if none passed, which is set for each item in `@F` via `map{...}@F`) the item uppercased, otherwise `lc` returns it lowercased. This is appended to `$\` which is implicitly output after anything is `print`ed, which because `-p` is specified, will happen after the (implicit - from `-p`) input loop exits. Due to this, it's also necessary to break out of the surrounding loops with `}{` so that we don't get an unmodified copy of the input `print`ed too.
> 1 votes

---
Tags: code-golf
---


title: Connect the pixels

text:
# Question
Title: Connect the pixels
Given a text like this:

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

```

Output the same text but by connecting the pixels with the characters `─│┌┐└┘├┤┬┴┼`. If a pixel doesn't have any neighbours, don't change it.

So the output of the last text is:

```
│ ─┬── ┌─ │
└─ │  ┌┘  │
   └──┘  ─┘

```
* You can take input as a boolean array.
* The input will always contain at least 1 pixel.
* You can count box-drawing chars as 1 byte.
* You can assume the input is padded with spaces.

## Test cases

```
## #
=>
── #

```

```
###
 #
=>
─┬─
 │

```

```
##### ##
 # #  #
########
=>
─┬─┬─ ┌─
 │ │  │
─┴─┴──┴─

```

```
 # #
#####
 # #
=>
 │ │
─┼─┼─
 │ │

```

```
# # # # #
 # # # #
# # # # #
 # # # #
# # # # #
=>
# # # # #
 # # # #
# # # # #
 # # # #
# # # # #

```

```
#####
#####
#####
#####
#####
=>
┌┬┬┬┐
├┼┼┼┤
├┼┼┼┤
├┼┼┼┤
└┴┴┴┘

```

Since this is , the shortest code wins.

# Answer
# Jelly, ~~60~~ ~~52~~ ~~51~~ ~~50~~ ~~49~~ 48 bytes

```
ṖḤ0;+Ḋ×
“µ³Q~E!G⁸ṗṫ\’ḃ61+9471Ọ⁾# j
ZÑ€4×Z++Ñ€ị¢Y

```

Saved a byte thanks to @Dennis.

The input is a boolean array of 1's and 0's. Iterates over each column and each row converting the head and tail of each infix of size 3 from a pair of binary digits to a decimal, and multiplies that with the center of each infix. Then it sums it with itself to find the index into `'#───│┌┐┬│└┘┴│├┤┼ '`.

Try it online! (case 2) (case 3) (case 4)

## Explanation

This relies on the same idea as my answer in J but instead of processing on each 3x3 subarray, I process over each row and each column while still obtaining the same table of indices.

Over half of the bytes are spent generating the list of box characters `'#───│┌┐┬│└┘┴│├┤┼ '`. String literals start with  in Jelly and have different meanings depending on their terminator. Here the terminator  means that the string will be parsed as the code points of each character according to the Jelly code page, and convert from a list of base 250 digits to a decimal.

```
“µ³Q~E!G⁸ṗṫ\’ => 10041542192416299030874093
(bijective base 61) => [1, 1, 1, 3, 13, 17, 45, 3, 21, 25, 53, 3, 29, 37, 61]
(add 9471 and convert to char) => '───│┌┐┬│└┘┴│├┤┼'

```

Then convert that decimal to a list of digits in bijective base 61 and increment each by 9471 to move it into the range of the box characters and convert each using Python's `chr`. Then prepend it with a character literal `”#` and append a space .

```
ṖḤ0;+Ḋ×  Helper link - Input: 1d list A
Ṗ        Get all of A except the last value
 Ḥ       Double each value in it
  0;     Prepend a 0
    +    Add elementwise with
     Ḋ     All of A except the first value
      ×  Multiply elementwise by A

“µ³Q~E!G⁸ṗṫ\’ḃ61+9471Ọ⁾# j  Nilad. Represents '#───│┌┐┬│└┘┴│├┤┼ '
“µ³Q~E!G⁸ṗṫ\’               Get the code points of each char in the string and
                            convert from a list of base 250 digits to decimal
             ḃ61            Convert that to a list of digits in bijective base 61
                +9471       Add 9400 to each
                     Ọ      Convert from ordinals to chars, gets '───│┌┐┬│└┘┴│├┤┼'
                      ⁾#    A pair of chars ['#', ' ']
                         j  Join the pair using the box characters

ZÑ€4×Z++Ñ€ị¢Y  Input: 2d list M
Z              Transpose
 Ñ€            Apply the helper link to each row of the transpose (each column of M)
   4×          Multiply each by 4
     Z         Transpose
      +        Add elementwise with M
       +       Add elementwise with
        Ñ€       The helper link applied to each row of M
          ị¢   Use each result as an index to select into the nilad
            Y  Join using newlines
               Return and print implicitly

```
> 8 votes

# Answer
## JavaScript (ES6), ~~155~~ ~~121~~ ~~103~~ 102 characters

```
let f =

s=>s.replace(/#/g,(c,p)=>'#│─┘─└─┴││┐┤┌├┬┼'[t=x=>s[p+x]==c,8*t(w=s.search`
`+1)+4*t(1)+2*t(-1)+t(-w)])

console.log(f(
  '# #### ## #\n' +
  '## #  ##  #\n' +
  '   ####  ##'
));
```

*Edit: saved 18 bytes with the help of ETHproductions*
*Edit: saved 1 byte by using the 1st parameter of replace() as `'#'`*

### How it works

We iterate on all `#` characters found in the input string. For each of them, we test whether its neighbors are also `#` characters using the `t()` function:

```
t = x => s[p + x] == c  // where c = '#'

```

The parameter `x` of the `t()` function is the offset of the neighbor with respect to the current position `p`. We use -1/+1 to test left/right neighbors and -w/+w for top/bottom neighbors (where `w` is the width of a row, i.e. the position of the first line-break + 1).

Each neighbor is assigned a different weight (1, 2, 4 or 8) according to the following compass:

```
  1
2 + 4
  8

```

Each weight combination leads to unique value in \[ 0 .. 15 \]. For instance, if both the neighbor at the top and the neighbor on the right are set, the sum will be 1 + 4 = 5, which is translated into  using this table:

```
00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15
#  │  ─  ┘  ─  └  ─  ┴  │  │  ┐  ┤  ┌  ├  ┬  ┼

```

Therefore, `'#│─┘─└─┴││┐┤┌├┬┼'[weight_sum]` leads to the expected character.
> 15 votes

# Answer
# , ~~82~~ ~~72~~ 66 bytes

```
(ucp' #───│┌┐┬│└┘┴│├┤┼'){~]+]*3 3((2#.1 7 3 5{,);._3)0,.~0,.0,~0,]

```

The input is a boolean table of 1's and 0's. The rules state that the box characters each count as one byte, not three, and that has been applied here.

## Usage

```
   f =: (ucp' #───│┌┐┬│└┘┴│├┤┼'){~]+]*3 3((2#.1 7 3 5{,);._3)0,.~0,.0,~0,]
   m =: 1 0 1 1 1 1 0 1 1 0 1 , 1 1 0 1 0 0 1 1 0 0 1 ,: 0 0 0 1 1 1 1 0 0 1 1
   m { ' #'
# #### ## #
## #  ##  #
   ####  ##
   f m
│ ─┬── ┌─ │
└─ │  ┌┘  │
   └──┘  ─┘
   ' #' {~ m =: 5 5 $ 1
   f m
┌┬┬┬┐
├┼┼┼┤
├┼┼┼┤
├┼┼┼┤
└┴┴┴┘
   ' #' {~ m =: 5 9 $ 1 0
# # # # #
 # # # #
# # # # #
 # # # #
# # # # #
   f m
# # # # #
 # # # #
# # # # #
 # # # #
# # # # #

```

## Explanation

First the input is padded with 0's on all sides.

```
   ] m =: 1 0 1 1 1 1 0 1 1 0 1 , 1 1 0 1 0 0 1 1 0 0 1 ,: 0 0 0 1 1 1 1 0 0 1 1
1 0 1 1 1 1 0 1 1 0 1
1 1 0 1 0 0 1 1 0 0 1
0 0 0 1 1 1 1 0 0 1 1
   (0,.~0,.0,~0,]) m
0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 1 1 1 1 0 1 1 0 1 0
0 1 1 0 1 0 0 1 1 0 0 1 0
0 0 0 0 1 1 1 1 0 0 1 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0

```

Then each subarray of size 3 is selected

```
   3 3 <;._3 (0,.~0,.0,~0,]) m
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│
│0 1 0│1 0 1│0 1 1│1 1 1│1 1 1│1 1 0│1 0 1│0 1 1│1 1 0│1 0 1│0 1 0│
│0 1 1│1 1 0│1 0 1│0 1 0│1 0 0│0 0 1│0 1 1│1 1 0│1 0 0│0 0 1│0 1 0│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│0 1 0│1 0 1│0 1 1│1 1 1│1 1 1│1 1 0│1 0 1│0 1 1│1 1 0│1 0 1│0 1 0│
│0 1 1│1 1 0│1 0 1│0 1 0│1 0 0│0 0 1│0 1 1│1 1 0│1 0 0│0 0 1│0 1 0│
│0 0 0│0 0 0│0 0 1│0 1 1│1 1 1│1 1 1│1 1 0│1 0 0│0 0 1│0 1 1│1 1 0│
├─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┼─────┤
│0 1 1│1 1 0│1 0 1│0 1 0│1 0 0│0 0 1│0 1 1│1 1 0│1 0 0│0 0 1│0 1 0│
│0 0 0│0 0 0│0 0 1│0 1 1│1 1 1│1 1 1│1 1 0│1 0 0│0 0 1│0 1 1│1 1 0│
│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│0 0 0│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

```

Then only 5 of the values in each subarray is considered

```
┌───┐
│xAx│
│CED│
│xBx│
└───┘

```

The values `ABCD` are selected by flattening each subarray and selecting at indices `1 7 3 5`. Those values are multiplied by `E` which is at index 4. It is then converted from a list of binary digits to a decimal, and incremented by `E`. The `x` values are not needed.

```
   3 3 (4&{([+2#.*)1 7 3 5&{)@,;._3 (0,.~0,.0,~0,]) m
 5 0 2  8 4 3  0  6 3 0  5
10 3 0 13 0 0  6 11 0 0 13
 0 0 0 10 4 4 11  0 0 2 11

```

This is used as an index to select which character to draw according to the table below (reordered a bit for golfing). The last column matches the output value of each subarray to a box character.

```
 0  (space)  0
 1  #        1
 2  ┌        6
 3  ┬        8
 4  ┐        7
 5  ├        14
 6  ┼        16
 7  ┤        15
 8  └        10
 9  ┴        12
10  ┘        11
11  │        5, 9, 13
12  ─        2, 3, 4

```

Also, in J, the string `' #───│┌┐┬│└┘┴│├┤┼'` uses 8-bit characters making it have a length of 47 (for each byte) for the 17 characters needed. The command `ucp` converts it to 16-bit characters which allows it to be length 17.
> 15 votes

# Answer
# Python 2.7, ~~318~~ 315 bytes (~~270~~ 267 chars)

I'm sure this can be golfed further (particularly I'd love to get rid of that annoying first-line comment) but here's my entry:

```
#encoding:utf-8
f=lambda t:(lambda l,s:'\n'.join(''.join((u'┼├┤│┬┌┐│┴└┘│───#'[(s==l[i][j-1])+2*(s==l[i][j+1])+4*(i<1 or s==l[i-1][j])+8*(i>len(l)-2 or s==l[i+1][j])],s)[s==l[i][j]]for j in range(len(l[i])-1))for i in range(len(l))))([l+' 'for l in t.split('\n')],' ')

```

Here's an explanation of how the whole thing works:

```
#encoding:utf-8 # Dammit, Python. This adds an extra 16 bytes!
f=lambda t:( # main lambda function
    lambda l,s: # inner lambda so we can pass it "local constants" (see last line)
        '\n'.join( # join each line
            ''.join( # join each char within the line
                (u'┼├┤│┬┌┐│┴└┘│───#'[ # string of all possible characters, indexed by binary 0-15 based on adjacent chars
                    (s==l[i][j-1])+ # left
                    2*(s==l[i][j+1])+ # right
                    4*(i<1 or s==l[i-1][j])+ # up ('i<1' just yields zero in case this is the first line, so that we don't get index problems)
                    8*(i>len(l)-2 or s==l[i+1][j])], # down ('i>len(l)-2' is same as above)
                s)[s==l[i][j]] # if original is space, choose space, else choose the previously chosen box-drawing char
                for j in range(len(l[i])-1)) # do this process for each char (excluding last, which is a space)
            for i in range(len(l))) # do this for each line
    )([l+' ' for l in t.split('\n')],' ') # call the inner lambda with two parameters: first, the text split into lines; second, a space char (actually makes code shorter)

```

EDIT: Removed some spaces before `for ... in ...`
> 8 votes

# Answer
# JavaScript (ES6), ~~150~~ ~~139~~ ~~133~~ 131 chars

```
a=>a.map((q,y)=>q.replace(/#/g,(c,x)=>"#│─┘─└─┴││┐┤┌├┬┼"[g=(X,Y=0)=>(a[Y+y]||[])[X+x]==c,g(0,1)*8+g(1)*4+g(-1)*2+g(0,-1)])).join`
`

```

Takes input as an array of strings, e.g. `f(["###", " # "])`.

### Test snippet

```
f=a=>a.map((q,y)=>q.replace(/#/g,(c,x)=>"#│─┘─└─┴││┐┤┌├┬┼"[g=(X,Y=0)=>(a[Y+y]||[])[X+x]==c,g(0,1)*8+g(1)*4+g(-1)*2+g(0,-1)])).join`
`
```

```
<textarea id=I rows=6># #### ## #
## #  ##  #
   ####  ##</textarea>
<br>
<button onclick="O.innerHTML=f(I.value.split('\n')).replace(/\n/g,'<br>')">Run</button>
<pre id=O></pre>
```
> 6 votes

# Answer
# Python 3, 149 bytes

```
def f(s):S=' ';w=s.find('\n')+1;t=lambda i:(s+w*S)[i]>S;return[[c,'#│─┘─└─┴││┐┤┌├┬┼'[t(p-w)+2*t(p-1)+4*t(p+1)+8*t(p+w)]][c>S]for p,c in enumerate(s)]

```

Takes input like `##\n #\n` and returns output like `['─', '┐', '\n', ' ', '│', '\n']`.
> 5 votes

# Answer
# ALPACA, 414 + 2 = 416 bytes

```
neighbourhoodV(^ v < >);states" ";statep"#"toA when4inV p,toB when3inV p andvs,toC when3inV p and^s,toD when3inV p and>s,toE when3inV p and<s,toF when2inV p and>s andvs,toG when2inV p andvs and<s,toH when2inV p and<s and^s,toI when2inV p and^s and>s,toJ when^p orvp,toK when<p or>p;stateA"┼";stateB"┴";stateC"┬";stateD"┤";stateE"├";stateF"┘";stateG"└";stateH"┌";stateI"┐";stateJ"│";stateK"─".

```

Requires the `-fI` flags.

This solution uses a very large number of bytes, but it is unique in that it uses a cellular automaton. ALPACA is usually used as a metalanguage, but here I'm using it as a programming language.

Ungolfed version:

```
neighbourhood V (^ v < >);
state s " ";
state p "#" to A when 4 in V p,
to B when 3 in V p and v s,
to C when 3 in V p and ^ s,
to D when 3 in V p and > s,
to E when 3 in V p and < s,
to F when 2 in V p and > s and v s,
to G when 2 in V p and v s and < s,
to H when 2 in V p and < s and ^ s,
to I when 2 in V p and ^ s and > s,
to J when ^ p or v p,
to K when < p or > p;
state A "┼";
state B "┴";
state C "┬";
state D "┤";
state E "├";
state F "┘";
state G "└";
state H "┌";
state I "┐";
state J "│";
state K "─".

```
> 5 votes

# Answer
# PHP, 203 bytes

This can probably be done in a shorter way.

```
while($s=fgets(STDIN))$f[]=$s;foreach($f as$y=>&$s)for($x=strlen($s);$x--;)if($s[$x]>$b=" ")$s[$x]="#───│┘└┴│┐┌┬│┤├┼"[($s[$x-1]>$b)+2*($s[$x+1]>$b)+4*($f[$y-1][$x]>$b)+8*($f[$y+1][$x]>$b)];echo join($f);

```

reads input from STDIN. run with `-r`.
> 4 votes

# Answer
# Perl, ~~89~~ 88 bytes

Includes +2 for `-0p`. The special characters are counted as 1 byte, but to make them actually display as single characters it's best to also add the -C option.

Give input on STDIN with the lines space padded so they all have the same length:

```
perl -C connect.pl
# #### ## #
## #  ##  #
   ####  ##
^D

```

`connect.pl`:

```
#!/usr/bin/perl -0p
/
/;$n=".{@-}";s%#%substr"#───│└┘┴│┌┐┬│├┤┼",/\G##/+2*/#\G/+4*/#$n\G/s+8*/\G#$n#/s,1%eg

```
> 4 votes

# Answer
# R, ~~199~~ 212 bytes

EDIT: It's now a function, rather than a code snippet.

The input is a matrix `m` of 1s and 0s. This is pretty ugly and hacky.

```
function(m){
v=strsplit(" #─│┘│┐│┤──└┴┌┬├┼","")[[1]]
d=dim(m)+1
n=array(0,dim=d+1)
n[2:d[1],2:d[2]]=m
for(i in 0:(d[1]-2)){for(j in 0:(d[2]-2))cat(v[1+(p<-n[2+i,2+j])*sum(2^(0:3)*n[1:3+i,1:3+j][1:4*2])+p]);cat("\n")}
}

```

A couple of tests:

```
> m = matrix(c(1, 1, 1, 0, 1, 0), nrow=2, byrow=TRUE)
> v=strsplit(" #─│┘│┐│┤──└┴┌┬├┼","")[[1]]
> d=dim(m)+1
> n=array(0,dim=d+1)
> n[2:d[1],2:d[2]]=m
> for(i in 0:(d[1]-2)){for(j in 0:(d[2]-2))cat(v[1+(p<-n[2+i,2+j])*sum(2^(0:3)*n[1:3+i,1:3+j][1:4*2])+p]);cat("\n")}
─┬─
 │
> m = matrix(rep(1, 16), ncol=4)
> v=strsplit(" #─│┘│┐│┤──└┴┌┬├┼","")[[1]]
> d=dim(m)+1
> n=array(0,dim=d+1)
> n[2:d[1],2:d[2]]=m
> for(i in 0:(d[1]-2)){for(j in 0:(d[2]-2))cat(v[1+(p<-n[2+i,2+j])*sum(2^(0:3)*n[1:3+i,1:3+j][1:4*2])+p]);cat("\n")}
┌┬┬┐
├┼┼┤
├┼┼┤
└┴┴┘

```
> 3 votes

# Answer
# MATL, 102 characters

I assign a neighbour a value (1, 2, 4 or 8); their sum will match a character in a string containing the drawing characters. I think there is still lots of room for improvements, but for a rough draft:

```
' #│││─┌└├─┐┘┤─┬┴┼' % String to be indexed
wt0J1+t4$(          % Get input, and append zeros at end of matrix (solely to avoid
                    %  indexing a non-existent second row/column for small inputs)
ttttt               % Get a whole load of duplicates to work on
3LXHY)              % Select rows 2:end from original matrix (one of the many dupes)
      w4LXIY)       % Select rows 1:end-1 from the 'destination' summing matrix)
             +HY(   % Add the neighbors below, store in 'destination' matrix
tIY)b3LY)2*+IY(     % +2* the neighbors above    +-------------------------------+
tHZ)b4LZ)4*+HZ(     % +4* the neighbors right    |(note: H and I contain 1:end-1 |
tIZ)b3LZ)8*+IZ(     % +8* the neighbors left     |  and 2:end respectively)      |
HH3$)               % Select the original matrix +-------------------------------+
*                % Make sure only cells that originally had a # get replaced
  1+)            % Add one because the original string is one-indexed. Index using ).

```

Improvements to be made:

* Possibly replace the whole summing part with some kind of loop working on rotated copies of the matrix
* Ditch the entire thing and make something based on a single loop working through the matrix
* *Use modular indexing to work on a flattened vector from the original array* **(?)**

Try it Online! (may not have box drawing characters support)
> 1 votes

# Answer
# APL (Dyalog Extended), 9 bytes

```
'#'⌂draw⊢

```

Try it online!

A built-in that solves the challenge (except that it accepts the `'*'` symbol as the default, so `'#'` needs to be supplied as an explicit argument). ¯\\\_(⍨)\_/¯

Documentation is here.

---

A non-built-in solution, because a built-in is boring:

# APL (Dyalog Extended), 43 bytes

```
' #│─┌─┐─┬││└├┘┤┴┼'⊇⍨⊢×0 0{1+⊥⊢/4 2⍴⍵}⌺3 3⊢

```

Try it online!

An anonymous function that takes the boolean matrix as its argument. Incidentally it wins over Jelly even without the built-in.

The approach is pretty similar to many other answers (base-2 conversion from the four neighbors and index into the target string).

One interesting thing to note is that the box-drawing characters are already part of the SBCS, so it is completely fine to use them in the code.

### How it works

```
' #│─┌─┐─┬││└├┘┤┴┼'⊇⍨⊢×0 0{1+⊥⊢/4 2⍴⍵}⌺3 3⊢
  0 0{          }⌺3 3⊢  ⍝ Map over 3×3 submatrices, with zero padding...
           4 2⍴⍵        ⍝ Reshape 3×3 to 4×2:
                        ⍝ . A .   . A
                        ⍝ B . C → . B
                        ⍝ . D .   . C
                        ⍝         . D
         ⊢/  ⍝ Take the last column
        ⊥    ⍝ Convert base 2 to integer
      1+     ⍝ Offset 1 to distinguish between ' ' and '#'
⊢×  ⍝ Mask the places for blanks
' #│─┌─┐─┬││└├┘┤┴┼'⊇⍨  ⍝ Convert each value in the matrix to the char at that index

```
> 1 votes

# Answer
# Charcoal, 45 bytes

```
ＷＳ⊞υιＰ⪫υ⸿Ｆ⪫υ⸿≡ι#§”y#─│┐──┌┬│┘│┤└┴├┼”↨ＥＫＶ›κ ²ι

```

Try it online! Link is to verbose version of code. Takes input as a newline-terminated list of strings. Scored using 15 1-byte box drawing characters (normally 3 bytes each). Explanation:

```
ＷＳ⊞υι

```

Read in the text.

```
Ｐ⪫υ⸿

```

Print it without moving the cursor.

```
Ｆ⪫υ⸿

```

Loop over the text again.

```
≡ι#

```

If the current character is a `#`...

```
§”y#─│┐──┌┬│┘│┤└┴├┼”↨ＥＫＶ›κ ²

```

... then look up the box drawing character based on the presence of neighbours.

```
ι

```

Otherwise just print the current character.
> 1 votes

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


title: Logo Pack LAPACK

text:
# Question
Title: Logo Pack LAPACK
This is the logo for LAPACK, a widely used software library for numerical linear algebra.

Your task is to print the logo (color and matrix brackets not required) as this exact string. Trailing newline is allowed.

```
L  A  P  A  C  K
L -A  P -A  C -K
L  A  P  A -C -K
L -A  P -A -C  K
L  A -P -A  C  K
L -A -P  A  C -K

```

# Answer
> 15 votes
# Python 2, 69 bytes

```
print"L %sA %sP %sA %sC %sK\n"*6%tuple('     - - -   --- -'+'-  -'*3)

```

Try it online!

Kind-of a boring solution. Makes a string template for the output with slots to put in minuses, then inserts in hardcoded string of minuses and spaces for those slots. I didn't find a way to compress or generate this length-30 binary sequence shorter than hardcoding it. The only optimization the code uses is that the sequence ends in 3 copies of `'- -'`. The output includes a trailing newline which the challenge allows.

The template could also use `%2s` in place of  `%s` which would allow also putting in empty string for the spaces, but I don't see how to use this.

# Answer
> 13 votes
# Python 2, 91 bytes

```
i=0
for c in'LAPACK'*6:print' -'[chr(i+33)in'(*,12467;<@AD']*(c!='L')+c+'\n'*(c=='K'),;i+=1

```

Try it online!

I know most previous answers already beat this, but it's my first golf and I quite enjoyed the result :-)!

Edit: Thanks very much to @xnor for ~~the tip with `'\n'*(c=='K')`~~ all the tips!

# Answer
> 12 votes
# x86-16 machine code, IBM PC DOS, ~~54~~ ~~48~~ 49 bytes

**Binary:**

```
00000000: b106 be25 01ad cd29 84e4 740e b020 cd29  ...%...)..t.. .)
00000010: d2ec 7302 b02d cd29 ebeb b00d cd29 b00a  ..s..-.).....)..
00000020: cd29 e2de c34c 1541 0350 1641 0c43 194b  .)...L.A.P.A.C.K
00000030: 00                                       .

```

Build and test using `xxd -r` on your favorite DOS VM.

**Listing:**

```
B1 06       MOV  CL, 6              ; loop 6 rows
        ROWLOOP:
BE 0121     MOV  SI, OFFSET LS      ; letter string into SI
        COLLOOP:
AD          LODSW                   ; letter into AL, dash pattern into AH
CD 29       INT  29H                ; write to screen
84 E4       TEST AH, AH             ; is AH = 0?
74 0E       JZ   END_NL             ; if so break loop, write NL
B0 20       MOV  AL, ' '            ; space char into AL
CD 29       INT  29H                ; write to screen
D2 EC       SHR  AH, CL             ; shift dash bit into CF
73 02       JNC  NO_DASH            ; is a dash?
B0 2D       MOV  AL, '-'            ; dash char in AL
        NO_DASH:
CD 29       INT  29H                ; write to screen
EB EB       JMP  COLLOOP            ; loop until end of string
        END_NL:
B0 0D       MOV  AL, 0DH            ; CR char
CD 29       INT  29H                ; write to screen
B0 0A       MOV  AL, 0AH            ; LF char
CD 29       INT  29H                ; write to screen
E2 DE       LOOP ROWLOOP            ; loop until end of rows
C3          RET                     ; return to DOS

        LS  DB  'L',15H,'A',3H,'P',16H,'A',0CH,'C',19H,'K',0

```

**How?**

The "letter string" data contains two bytes for each letter - the high byte is the letter and the low byte is a bitmap describing if that letter should be followed by a dash for each row. The rows are indexed 6 to 1 starting from the top, where the bit in the corresponding order represents whether or not there's a dash.

*Examples:*

Row 5, Col 0: Data `'L'`, `0x15` (0**1**0101)

The fifth bit is a `1` indicating that for the fifth row after the `L` there is a dash after.

Row 2, Col 3: Data `'A'`, `0xC` (0011**0**0)

The second bit is a `0` indicating that for the fifth row after the `A` there is not a dash after.

Or looking at it a different way, the odd bytes `[ 0x15, 0x3, 0x16, 0xC, 0x19, 0x0 ]` form the bitmap of the dashes (only rotated and flipped):

```
0x15    010101
0x3     000011
0x16    010110
0xC     001100
0x19    011001
0x0     000000

```

**Runtime:**

A standalone IBM PC DOS COM executable. Output to console.

# Answer
> 10 votes
# JavaScript (ES6),  ~~74 72~~  71 bytes

```
_=>`L A P A C K
`.repeat(i=6).replace(/ /g,c=>c+' -'[863064083>>++i&1])

```

Try it online!

### How?

We build a string consisting of the pattern `"L A P A C K\n"` repeated 6 times and match all spaces. We replace each of them with either `" "` or `" -"` depending on the result of a test on a bit mask.

In binary, the constant **863064083** is:

```
  bit 31                  bit 7  bit 0
    v                       v      v
    00110011011100010101000000010011
    \___/\___/\___/\___/\___/  \___/
row:  4    3    2    1    0      5

```

Because we start with `i=6` and pre-increment `i` at each iteration, the first row is encoded by the bits 7 to 11 (0-indexed).

As stated in the ECMAScript specification, bitwise shifts are processed modulo 32. So there's a wrap-around when `i` exceeds 31 and the last row can safely be encoded by the bits 0 to 4.

---

### Alternate version

For **69 bytes**, we could do:

```
_=>`LAPACK
`.repeat(i=6).replace(/\B/g,c=>' '+' -'[863064083>>++i&1])

```

Try it online!

But the corresponding output includes 2 trailing spaces on the last row1. Because the challenge looks very strict about leading and trailing whitespace, this is probably invalid. ¯\\\_(ツ)\_/¯

*1: Now, would you have noticed them if I didn't tell ya?! :-p*

# Answer
> 8 votes
# Charcoal, ~~29~~ 27 bytes

```
Ｅ?*<)3&✂⭆⍘℅ι- ⁺ ⁺λ§LAPACKμ²

```

Try it online! Link is to verbose version of code. Edit: Saved 2 bytes by appropriating @KevinCruijssen's custom base conversion idea. Explanation:

```
 ?*<)3&                     Literal string of code points
Ｅ                           Map over characters
           ι                Current character
          ℅                 Take the ordinal
         ⍘  -               Convert to custom base `- `
        ⭆                   Map over characters and join
                 λ          Current character
                ⁺           Concatenated with
                   LAPACK   Literal string `LAPACK`
                  §         Indexed by
                         μ  Inner index
              ⁺             Prefixed with a space
       ✂                   ² Slice off the leading spaces

```

# Answer
> 4 votes
# APL+WIN, 58 bytes

```
n←96⍴¯2↓∊'LAPACK',¨⊂'  '⋄n[⎕av⍳'ì↑⍋+.28;EHRU^']←'-'⋄6 16⍴n

```

Explanation:

```
'LAPACK',¨⊂'  ' concatenate 2 spaces to each letter in LAPACK

96⍴¯2↓∊ convert to a vector, drop last 2 spaces and replicate to form a 96 element vector

⎕av⍳'ì↑⍋+.28;EHRU^' convert characters to ascii code point integers

n[.....]←'-' use integers as index positions to assign - character

6 16⍴n reshape vector as a 6 16 matrix

```

# Answer
> 3 votes
# Ruby, 63 bytes

```
puts"L%sA%sP%sA%sC%sK
"*6%(0..29).map{|i|'  -'[644276896[i],2]}

```

Try it online!

Builds the output string by successive substitution from an array of prefixes. For each letter other than `L`, the appropriate two-character prefix (either  or  `-`) is selected by using the binary digits of `644276896` (`100110011001101110001010100000` in binary) to index into the three-character string  `-`.

# Answer
> 3 votes
# 05AB1E, 31 bytes

```
•x—o—Õ•₃вε„ -Åв’la•Î’u.ι2ôJðý¦,

```

Try it online.

**Explanation:**

```
•x—o—Õ•     # Push compressed integer 251957282837
       ₃в   # Convert it to base-95 as list: [32,53,35,54,44,57]
ε           # Foreach over the integers:
 „ -Åв      #  Convert it to custom base-" -",
            #  which basically means to convert it to base-2 and index it into " -"
 ’la•Î’     #  Push dictionary string "lapack"
       u    #  Uppercase it: "LAPACK"
 .ι         #  Interleave the characters in the two strings
   2ô       #  Split it into pairs of characters
     J      #  Join each pair together
      ðý    #  Join the list by spaces
        ¦   #  Remove the first character in front of the "L"
         ,  #  And output it with trailing newline

```

See this 05AB1E tip of mine (sections *How to use the dictionary?*, *How to compress large integers?*, and *How to compress integer lists?*) to understand why `’la•Î’` is `"lapack"`; `•x—o—Õ•` is `251957282837`; and `•x—o—Õ•₃в` is `[32,53,35,54,44,57]`.

(`[32,53,35,54,44,57]` is `[100000,110101,100011,110110,101100,111001]` in binary.)

# Answer
> 3 votes
# Perl 5, 57 bytes

```
$"=" { ,-}";say+(<"@{[L,A,P,A,C,K]}\n">)[0,21,3,22,12,25]

```

Try it online!

## Explanation

First `$"` (which is a magic variable that is used as a field separator when lists are interpolated into strings - default is `" "`) is set to  `{ ,-}`. Then `say` is called which is a newline-terminated `print` function, passing in the listed indexes (0, 21, 3, 22, 12, 25) from the result of the `glob` (`<...>` is shorthand for calling `glob`) `<"@{[L,A,P,A,C,K]}\n">`. This glob expands to:

```
L { ,-}A { ,-}P { ,-}A { ,-}C { ,-}K

```

Which, due to the `{ ,-}`s, will generate a list containing all permutations of the string with either  or `-` before every letter (except the leading `L`). The chosen indices are the ones we need for the logo.

# Answer
> 2 votes
# C (gcc), ~~92~~ ~~91~~ ~~84~~ 83 bytes

Saved 7 bytes thanks to the man himself Arnauld!!!

Saved a byte thanks to ceilingcat!!!

```
f(i){for(i=30;i--;i%5||puts("K"))printf("%c %c","CAPAL"[i%5]," -"[22141337>>i&1]);}

```

Try it online!

# Answer
> 2 votes
# Retina, 62 bytes

This is way too long. ~~The markdown parser breaks terribly if I use the TIO's post snippet generator, so there's an extra leading newline in the snippet below: there is actually only 1 leading newline!~~

```

bbcccbc-cc-b--b-- c
b

c
 -
L`.{6}
.
$0X
Y`X`\LAPACK
.L
L

```

The first 2 lines replace the empty string with `bbccc... c`, the next 4 lines decode it into spaces and dashes by simple substitutions (`b` -\> 3 spaces, `c` -\>  `-`), the next line splits it into 6 lines of length 6 (producing a 6x6 sign matrix), the next two lines replace each character `c` by `cX` , the next line cyclically transliterates all `X`s into `LAPACK`s, and the last 2 lines remove leading whitespace. Try it online!

# Answer
> 2 votes
# Python 3, 107 bytes

```
s='LAPACK';e=enumerate
for i,_ in e(s):print(*[' -'[(j%2+i%2==2)^(i//2+j//2==3)]*(j!=0)+k for j,k in e(s)])

```

Try it online!

How it works: blue squares are in the form \\$\begin{pmatrix}1&1\\1&-1\end{pmatrix}\\$ hence `j%2+i%2==2` and red squares (when `i//2+j//2==3`) are in the opposite form \\$\begin{pmatrix}-1&-1\\\-1&1\end{pmatrix}\\$ thus we simply xor the expressions with `^`. \\$\\$ \begin{array}{rr|rr|rr} \color{blue}{\mathrm{L}}& \color{blue}{\mathrm{A}}& \color{blue}{\mathrm{P}}& \color{blue}{\mathrm{A}}& \color{blue}{\mathrm{C}}& \color{blue}{\mathrm{K}}\\ \color{blue}{\mathrm{L}}& \color{blue}{\mathrm{-A}}& \color{blue}{\mathrm{P}}& \color{blue}{\mathrm{-A}}& \color{blue}{\mathrm{C}}& \color{blue}{\mathrm{-K}}\\ \hline \color{blue}{\mathrm{L}}& \color{blue}{\mathrm{A}}& \color{blue}{\mathrm{P}}& \color{blue}{\mathrm{A}}& \color{red}{\mathrm{-C}}& \color{red}{\mathrm{-K}}\\ \color{blue}{\mathrm{L}}& \color{blue}{\mathrm{-A}}& \color{blue}{\mathrm{P}}& \color{blue}{\mathrm{-A}}& \color{red}{\mathrm{-C}}& \color{red}{\mathrm{K}}\\ \hline \color{blue}{\mathrm{L}}& \color{blue}{\mathrm{A}}& \color{red}{\mathrm{-P}}& \color{red}{\mathrm{-A}}& \color{blue}{\mathrm{C}}& \color{blue}{\mathrm{K}}\\ \color{blue}{\mathrm{L}}& \color{blue}{\mathrm{-A}}& \color{red}{\mathrm{-P}}& \color{red}{\mathrm{A}}& \color{blue}{\mathrm{C}}& \color{blue}{\mathrm{-K}} \end{array} \\$\\$ Other techniques used:
`print(*[x])` instead of `print(' '.join(x))`,
`s*(j==0)` instead of `s if j else ''`,
`[falsy,truthy][expr]` instead of `truthy if expr else falsy`, where the former list is just a string `' -'`,
the rest is pretty straightforward.

# Answer
> 2 votes
# APL (Dyalog), 37 bytes

```
' -'[(6⍴2)⊤⎕A⍳'AVDWMZ'],¨6 6⍴'LAPACK'

```

Try it online!

* `⎕IO←0`.

We encode the dashes matrix by

* encoding dashes as `1`s (and spaces as `0`s)
* converting each column from binary to a decimal number (`0 21 3 22 12 25`)
* indexing into the alphabet (`AVDWMZ`).

We decode it the same way:

* `⎕A⍳` \- retrieves index into alphabet
* `(6⍴2)⊤` converts to binary columns
* `' -'[...]` \- `1` becomes dash.

Then we generate the `LAPACK` matrix with `6 6⍴'LAPACK'`, and concatenate each pair with .

# Answer
> 1 votes
# ///, 83 bytes

```
/$/ -//#/A@//!/
L //@/  /L@#P@#C@K!-#P$#C$K! #P@A$C$K!-#P$A$C@K! A$P$#C@K!-A$P@#C$K

```

Try it online!

# Answer
> 1 votes
# \+ magrittr, 312 bytes

```
library(magrittr)

A <- matrix(c(1,1,1,-1),nrow = 2)
B <- matrix(c(1,1,1,1,1,-1,1,-1,1),nrow = 3)
kronecker(B,A) %>%
  apply(1, function(x) {paste0(x,strsplit("LAPACK","")[[1]]) %>%
  gsub("-1","-",.) %>%  gsub("1"," ",.)})  %>%
  apply(2,function(x){paste0(x, collapse = " ")})  %>%
  cat(sep = "\n")

```

Try it online!

This gives on my console:

```
 L  A  P  A  C  K
 L -A  P -A  C -K
 L  A  P  A -C -K
 L -A  P -A -C  K
 L  A -P -A  C  K
 L -A -P  A  C -K

```

With the function kronecker() we construct a block matrix by replicating A by B coefficients.

A is a 2x2:

```
> A
     [,1] [,2]
[1,]    1    1
[2,]    1   -1

```

which are the signs that we want to replicate in 3x3 blocks multiplied by the coefficients in B:

```
> B
     [,1] [,2] [,3]
[1,]    1    1    1
[2,]    1    1   -1
[3,]    1   -1    1

```

Then we explode LAPACK with strsplit() and prepend 1 or -1. With gsub() we substitute 1 and -1. Then, we collapse the strings and print out to the console.

# Answer
> 1 votes
# Japt `-R`, 30 bytes

Happy to be beating 05AB1E after quite a bit of work on this but still feel I could do much better. Originally based on Neil's Charcoal solution.

```
"?*<)3&"¬®csSi-)í"LAPACK")ò ¸x

```

Test it

# Answer
> 1 votes
# PowerShell, ~~94~~ 77 bytes

-17 bytes thanks to mazzy

```
-join("L  A  P  A  C  K
"*6|% t*y|%{"$_-"[++$i+12-in' &,:=BHKYVdgp'[0..12]]})

```

Try it online!

Just checking for the indexes we need saves 9 bytes over just writing out the block. However, if we represent the indexes using their char values, we save loads more. We add 12 to the current iteration to get everything into the printable ASCII range. `' &,:=BHKYVdgp'[0..12]` converts our index string into an index array so we can use `-in`.

# Answer
> 1 votes
# PowerShell, ~~62~~ 57 bytes

Port of the Arnauld's alternative answer. Very nice! Delicious! Thanks.

We avoid the problem with `2 trailing spaces on the last row` because we use the array of strings, not the string with repeated `LAPACK\n`.

```
,'LAPACK'*6-replace'\B',{' '+' -'[(214811968-shr++$i)%2]}

```

Try it online!

---

# PowerShell, 71 bytes

port of C (gcc) answer. Thanks @Noodle9 and @Arnauld.

```
-join(29..0|%{'CAPAL'[$_%5];' ';' -'[(22141337-shr$_)%2];'K
'*!($_%5)})

```

Try it online!

# Answer
> 0 votes
# Io, 125 bytes

```
"      - - -    -- - --   --   --  - "foreach(x,i,("LAPACK"exSlice(x%6,x%6+1).." ".. i asCharacter .. if(x%6>4,"
",""))print)

```

Try it online!

# Answer
> 0 votes
# Python 2, 132 bytes

```
s,a,i="0"*19+bin(0x208200090824009002402)[2:],list("L  A  P  A  C  K\n"*6),0
for c in s:
	if(int(c)):a[i]="-"
	i+=1
print "".join(a)

```

Try it online!

Yes, I realise this is longer than a simple print statement, but I spent too long trying to get this to work and I liked the approach (for larger matrices, this method would become much more efficient). There must be at least a few ways to shave a couple bytes off this answer

# Answer
> 0 votes
# brainfuck, 356 bytes

```
++++++++[>+++++>++++++++>++++>+++++++++>+<<<<<-]>+++++>+>>++++>++<.<..<.>..>++++.<..<.>..<++.>..>-----.>.<+.<.<<.>--.>..>++++.<.<<.>.>..<++.>.<<.>>>-----.>.<+.<..<--.>..>++++.<..<.>.<<.>++.>.<<.>>>-----.>.<+.<.<<.>--.>..>++++.<.<<.>.>.<<.>++.>..>-----.>.<+.<..<--.>.<<.>>>++++.<.<<.>.>..<++.>..>-----.>.<+.<.<<.>--.>.<<.>>>++++.<..<.>..<++.>.<<.>>>-----.>.

```

Try it online!

There is the version, line by line (The 1st one is used to store the different chars)

```
++++++++[>+++++>++++++++>++++>+++++++++>+<<<<<-]>+++++>+>>++++>++
<.<..<.>..>++++.<..<.>..<++.>..>-----.>.
<+.<.<<.>--.>..>++++.<.<<.>.>..<++.>.<<.>>>-----.>.
<+.<..<--.>..>++++.<..<.>.<<.>++.>.<<.>>>-----.>.
<+.<.<<.>--.>..>++++.<.<<.>.>.<<.>++.>..>-----.>.
<+.<..<--.>.<<.>>>++++.<.<<.>.>..<++.>..>-----.>.
<+.<.<<.>--.>.<<.>>>++++.<..<.>..<++.>.<<.>>>-----.>.

```

---
Tags: code-golf, kolmogorov-complexity, matrix
---


title: Alignment on Triangular Grids

text:
# Question
Title: Alignment on Triangular Grids
Hexagonal grids have been become a fairly popular twist for challenges about 2-dimensional data recently. However, it seems that the equally interesting triangular grids have been largely neglected so far. I'd like to rectify that with a rather simple challenge.

First, how do we represent a triangular grid? Consider the following example (ignore the right diagram for now):

The cells neatly fall onto a regular grid (the difference to a regular grid being only which cells are considered adjacent):

```
1234567
89abcde
fghijkl
mnopqrs

```

Now, as the right diagram shows, a triangular grid has three main axes: a horizontal and two diagonal ones.

Highlighting these in the ASCII grid:

```
AVAVAVA
VAabcAV
fVAiAVl
mnVAVrs

```

### The Challenge

You're given a rectangular string representing a triangular grid (where the top left corner is an upwards-pointing triangle). Most of the cells with be `.`, but exactly two cells will be `#`, e.g.:

```
....#
.#...
.....

```

Determine whether the two `#` are aligned along any of the three axes of the grid (i.e. whether they lie on a single row in any of the three directions highlighted above). For this example, the answer is "no".

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Input may be a single string delimited by linefeeds or some other convenient character, or a list of strings. You may use any two (consistent) printable ASCII characters in place of `.` and `#`.

Output should be a truthy value if the highlighted cells are aligned and a falsy value otherwise.

Standard rules apply.

### Test Cases

Truthy grids:

```
.#..#.

#
#

...........
...#.......
...........
...........
...........
.......#...
...........

...........
.......#...
...........
...........
...........
...#.......
...........

.#.........
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.......#...

.........#.
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
...#.......

...........
.#.....#...
...........
...........
...........

```

Falsy grids:

```
#.....
.....#

.....#
#.....

...#.......
...........
...........
...........
...........
.......#...
...........

...........
...#.......
...........
...........
...........
...........
.........#.

.......#...
...........
...........
...........
...........
...#.......
...........

...........
.......#...
...........
...........
...........
...........
.#.........

```

# Answer
# Snails, ~~40~~ 39 bytes

```
\#{z|=(ul.ul.`,l~a~)(l.a3|.a|d.ea5}.,\#

```

```

\#    ,, match '#'
{
  z |  ,, Either turn in any octinilear direction, or do all the other stuff before the }
  =(   ,, If this assertion succeeds, the starting cell is an "upwards-pointing triangle"
    ul.ul.`,  ,, Go one cell up or left twice, any number of times.
              ,, This should have been one byte shorter with ul.`2 , or ul.`2+? but
              ,, the parsing of ` is buggy.
    l~a~   ,, Check that we are on the top-left cell by matching out-of-bounds to the left and then northeast
  )
  ( l.a3 |  ,, Move leftward once, then set direction to northwest; or
    .a   |  ,, Move right (the initial direction) once, then set direction to northeast; or
    d.ea5   ,, Move down once, then set direction to either northwest or northeast
}
.,    ,, Match any number of arbitrary chars (moving in the current direction)
\#    ,, match '#'

```
> 3 votes

# Answer
## CJam, 47 bytes

Well, now that there is a shorter solution I no longer feel bad sharing my own. :) (Mostly to show that this isn't particularly difficult, even if you don't have a 2D pattern matching language...)

```
qN%:eeee::f+:~{S&},2f<:P0f=P::+Xf|P::-Xf|]::=:|

```

This uses spaces in place of `#` and really anything else for `.`.

Run all test cases online.

I really hate the duplication in `P::+Xf|P::-Xf|` but so far I haven't come up with anything to get rid of it.

### Explanation

Don't read on if you want to figure out a solution for yourself.

First, the boring part: getting the two coordinate pairs of the two spaces in the input grid:

```
qN%   e# Read input and split into lines.
:ee   e# Enumerate the characters in each line. I.e. turn each character 'x into a pair
      e# [N 'x] where N is its horizontal 0-based index.
ee    e# Enumerate the lines themselves, turning each line [...] into [M [...]] where M
      e# is its vertical 0-based index.
::f+  e# This distributes the vertical index over the individual lines, by prepending it
      e# to each pair in that line. So now we've got a 2-D array, where each character 'x
      e# has been turned into [M N 'x].
:~    e# Flatten the outermost dimension, so that we have a flat list of characters with
      e# their coordinates.
{S&}, e# Filter only those lists that contain a space.
2f<   e# Truncate the two results to only their first two elements.
:P    e# Store the result in P.

```

Now the interesting part is how to determine whether those coordinates are aligned or not. My code computes all three axes separately:

* The horizontal axis is trivial. Check whether the vertical coordinates match.
* Let's look at the north-east diagonal. In the ASCII grid, there are always two antidiagonals that belong to each tri-grid diagonal:

```
....AV..
...AV...
..AV....

```

We can identify the current antidiagonal by adding up the `x` and `y` coordinates:

```
01234567
12345678
23456789

```

So we'd want `0` and `1` to belong to the same diagonal, as well as `2` and `3`, and `4` and `5` and so on. That means, once we have our anti-diagonal index we want to round up to the next odd number. In other words, we take the bitwise OR with `1`. (We could also round down to the next even number by bitwise AND with `-2` but that's more expensive in code.)
* Now the south-east diagonals:

```
.VA.....
..VA....
...VA...

```

In order to give diagonals an index, we *subtract* the `x` from the `y` coordinate (representing negative numbers as letters):

```
0abcdefg
10abcdef
210abcde

```

In this case, we'd want `0` and `1` to belong to the same diagonal, as well as `-1` and `-2`, or `2` and `3`. So once again, we want to round up to the next odd number.

Here is the code for that:

```
0f=  e# The coordinates are still on the stack. Replace each with its vertical coordinate
     e# to check for the horizontal axis.
P    e# Push the coordinates again.
::+  e# Sum each pair to get an anti-diagonal index.
Xf|  e# OR each index with 1 to round up to the next odd number.
P    e# Push the coordinates again.
::-  e# In each pair, subtract the horizontal coordinate from the vertical, to
     e# get a diagonal index.
Xf|  e# OR each index with 1.
]    e# Wrap all three index pairs in an array.
::=  e# Check equality for each pair.
:|   e# Fold bitwise OR over the results to check if at least one pair of indices
     e# was equal.

```
> 2 votes

# Answer
# APL (Dyalog Unicode), ~~36~~ 27 bytes

```
1∊=/¯1 0 1∘.(⊥-2|⊣×⊥)⍸⍉⍎¨↑⎕

```

Try it online!

*-9 bytes mostly from @Bubbler*

Full program that returns `0` or `1`. Takes input as an array of strings, where each character is `0` for `.` or `1` for `#`.

### How?

Uses the same general strategy as Martin Ender's CJam Answer. The two diagonals are indexed as `y+(-1)*x` and `y+1*x`, both rounded up to the nearest odd number. The horizontal axis is indexed as `y+0*x` with no rounding.

```
1∊=/¯1 0 1∘.(⊥-2|⊣×⊥)⍸⍉⍎¨↑⎕
                         ↑⎕  ⍝ The input array of strings, converted to a matrix
                       ⍎¨    ⍝ Evaluate each character to obtain either 0 or 1
                     ⍸       ⍝ Find the (y,x) positions of both 1s
          ∘.                 ⍝ Outer product:
    ¯1 0 1                     ⍝ For each ⍺ in 1, 0, -1:
                               ⍝ And for each (y,x) position
            (⊥     )           ⍝ Compute (⍺×x)+y (convert to base ⍺)
                                 ⍝ (⍉-Transposed earlier to get x left of y)
             -2|⊣×⊥            ⍝ If odd and ⍺ is not 0: subtract 1
1∊=/                         ⍝ Check if the two positions have equal indices on any axis

```
> 2 votes

---
Tags: code-golf, decision-problem, hexagonal-grid
---


title: K-Means Clustered Golf

text:
# Question
Title: K-Means Clustered Golf
# K-Means Clustering (Wikipedia)

The task here is rather simple, perform a single iteration of a k-means clustering algorithm on a binary matrix. This is essentially the setup task for the main k-means algorithm, I felt the setup might be easier and entice golfing languages to give it a shot as well. The matrix passed to you will have the following format:

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

```

1 represents a point, while 0 represents a lack of points. Your job will be to randomly generate `k-1` centroids and perform the initial clustering of the data around the centroids you've generated. `k` is defined as `min(grid#Width, grid#Height)-1`. The labeling of each centroid should go from `2` until `k`. For instance, in this scenarios you could generate the following centroids:

```
Centroid 2 was generated at: (1.0, 4.0)
Centroid 3 was generated at: (1.0, 5.0)
Centroid 4 was generated at: (5.0, 1.0)
Centroid 5 was generated at: (3.0, 3.0)
Centroid 6 was generated at: (0.0, 2.0)
Centroid 7 was generated at: (6.0, 6.0)
Centroid 8 was generated at: (2.0, 6.0)

```

After generating the centroids, you must loop through each and every point that is marked with a `1`, as we can treat the ones marked with `0` as empty space. For each centroid, you must decide which centroid is the closest to the point in question. Here's the distances for the example:

```
(0,8) distance from centroid 2 is 4.123105625617661
(0,8) distance from centroid 3 is 3.1622776601683795
(0,8) distance from centroid 4 is 8.602325267042627
(0,8) distance from centroid 5 is 5.830951894845301
(0,8) distance from centroid 6 is 6.0
(0,8) distance from centroid 7 is 6.324555320336759
(0,8) distance from centroid 8 is 2.8284271247461903
(1,1) distance from centroid 2 is 3.0
(1,1) distance from centroid 3 is 4.0
(1,1) distance from centroid 4 is 4.0
(1,1) distance from centroid 5 is 2.8284271247461903
(1,1) distance from centroid 6 is 1.4142135623730951
(1,1) distance from centroid 7 is 7.0710678118654755
(1,1) distance from centroid 8 is 5.0990195135927845
(2,8) distance from centroid 2 is 4.123105625617661
(2,8) distance from centroid 3 is 3.1622776601683795
(2,8) distance from centroid 4 is 7.615773105863909
(2,8) distance from centroid 5 is 5.0990195135927845
(2,8) distance from centroid 6 is 6.324555320336759
(2,8) distance from centroid 7 is 4.47213595499958
(2,8) distance from centroid 8 is 2.0
(3,2) distance from centroid 2 is 2.8284271247461903
(3,2) distance from centroid 3 is 3.605551275463989
(3,2) distance from centroid 4 is 2.23606797749979
(3,2) distance from centroid 5 is 1.0
(3,2) distance from centroid 6 is 3.0
(3,2) distance from centroid 7 is 5.0
(3,2) distance from centroid 8 is 4.123105625617661
(4,5) distance from centroid 2 is 3.1622776601683795
(4,5) distance from centroid 3 is 3.0
(4,5) distance from centroid 4 is 4.123105625617661
(4,5) distance from centroid 5 is 2.23606797749979
(4,5) distance from centroid 6 is 5.0
(4,5) distance from centroid 7 is 2.23606797749979
(4,5) distance from centroid 8 is 2.23606797749979
(4,8) distance from centroid 2 is 5.0
(4,8) distance from centroid 3 is 4.242640687119285
(4,8) distance from centroid 4 is 7.0710678118654755
(4,8) distance from centroid 5 is 5.0990195135927845
(4,8) distance from centroid 6 is 7.211102550927978
(4,8) distance from centroid 7 is 2.8284271247461903
(4,8) distance from centroid 8 is 2.8284271247461903
(6,1) distance from centroid 2 is 5.830951894845301
(6,1) distance from centroid 3 is 6.4031242374328485
(6,1) distance from centroid 4 is 1.0
(6,1) distance from centroid 5 is 3.605551275463989
(6,1) distance from centroid 6 is 6.082762530298219
(6,1) distance from centroid 7 is 5.0
(6,1) distance from centroid 8 is 6.4031242374328485
(7,1) distance from centroid 2 is 6.708203932499369
(7,1) distance from centroid 3 is 7.211102550927978
(7,1) distance from centroid 4 is 2.0
(7,1) distance from centroid 5 is 4.47213595499958
(7,1) distance from centroid 6 is 7.0710678118654755
(7,1) distance from centroid 7 is 5.0990195135927845
(7,1) distance from centroid 8 is 7.0710678118654755
(7,5) distance from centroid 2 is 6.082762530298219
(7,5) distance from centroid 3 is 6.0
(7,5) distance from centroid 4 is 4.47213595499958
(7,5) distance from centroid 5 is 4.47213595499958
(7,5) distance from centroid 6 is 7.615773105863909
(7,5) distance from centroid 7 is 1.4142135623730951
(7,5) distance from centroid 8 is 5.0990195135927845
(8,1) distance from centroid 2 is 7.615773105863909
(8,1) distance from centroid 3 is 8.06225774829855
(8,1) distance from centroid 4 is 3.0
(8,1) distance from centroid 5 is 5.385164807134504
(8,1) distance from centroid 6 is 8.06225774829855
(8,1) distance from centroid 7 is 5.385164807134504
(8,1) distance from centroid 8 is 7.810249675906654
(8,8) distance from centroid 2 is 8.06225774829855
(8,8) distance from centroid 3 is 7.615773105863909
(8,8) distance from centroid 4 is 7.615773105863909
(8,8) distance from centroid 5 is 7.0710678118654755
(8,8) distance from centroid 6 is 10.0
(8,8) distance from centroid 7 is 2.8284271247461903
(8,8) distance from centroid 8 is 6.324555320336759

```

The final result of the clustering algorithm is that there should be no 1s remaining in the matrix, only centroid numbers. This is why it was important to label the centroids from `2-k+1`, allowing us to replace them, as follows:

```
 0 0 0 0 0 0 0 0 8
 0 6 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 8
 0 0 5 0 0 0 0 0 0
 0 0 0 0 0 5 0 0 7
 0 0 0 0 0 0 0 0 0
 0 4 0 0 0 0 0 0 0
 0 4 0 0 0 7 0 0 0
 0 4 0 0 0 0 0 0 7
 0 0 0 0 0 0 0 0 0

```

This is the initial clustering layout for 7 centroids on the provided grid, given randomly generated centroids. Your job is to output the clustered version of the binary input grid.

# Rules

* The `k-1` centroids must be randomly generated and should be anywhere from `(0,0)` to `(grid#Width, grid#Height)`.
    + The value of `k` is `min(grid#Width, grid#Height)-1`.
    + The centroids generated MUST be numbered from `2` to `k`.
* The input format MUST be a grid of 0s and 1s, where 0s represent empty space and 1s represent points.
    + A grid is either a string using 1-char per cell and `\n` as row delimiters or a 2D array.
    + The grid passed is not guaranteed to be square, but it is guaranteed to not be empty.
* The final output can either use arrays or a delimited string.
* Shortest code wins, this is .

# Answer
# APL (Dyalog Unicode), ~~61~~ 50 bytes

```
⍴⍴,{⍺\1+{⊃⍸⍵=⌊/⍵}¨↓⍵}⍸∘.(+.×⍨-)⌊/∘⍴{⍵[1↓⍺?⍴⍵]}∘⍸=⍨

```

Try it online!

*-11 bytes thanks to Bubbler*

### How it Works

```
          ⍝ Implicitly take binary matrix G as input
⍸=⍨       ⍝ Yield all (1-indexed) coordinates from (1,1) to (w,h)
⌊/∘⍴      ⍝ k+1=min(w,h)
{...}     ⍝ Choose k centroids:
 ?          ⍝ Randomly choose
 ⍺          ⍝ k+1 distinct indices
 ⍴⍵         ⍝ from the array of w×h possible indices
 1↓         ⍝ Drop the first so there are only k indices
 ⍵[...]     ⍝ index into the array of w×h coordinates
∘.        ⍝ Outer product of
            ⍝ the k centroids with
 ⍳          ⍝ the coordinates of all of the "1"s in G
 (+.×⍨-)    ⍝ with operator: distance squared
{...}¨↓   ⍝ For each row (point)
 ⊃⍸⍵=⌊/⍵    ⍝ Find the index of the centroid with smallest distance
            ⍝ (breaks ties by choosing lower numbers → small bias toward lower centroid numbers)
1+        ⍝ Add 1 to shift centroid numbers to [2,k]
          ⍝ Now we have a list of the centroid numbers for the "1"s, in reading order
⍺\         ⍝ Expand to prototype array:
,         ⍝ Prototype array is flattened G (Expand \ throws RANK ERROR for non-vector left argument)
⍴     ⍝ Reshape back to
⍴     the shape of G

```
> 4 votes

# Answer
## Mathematica 109 Bytes

If I understand the question correctly, something like this ought to work. "KMeans" is one of the built in methods to FindClusters and ClusteringComponents.

```
SparseArray[Thread[(p=Position[#,1])->1+ClusteringComponents[p,Min[d=Dimensions@#]-1,1,Method->"KMeans"]],d]&

```

Usage: `%@in//MatrixForm` to get visualization, `in` is an integer array.
> 1 votes

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


title: Complete the Magic Square

text:
# Question
Title: Complete the Magic Square
## Background

A magic square is an `n×n` matrix consisting of one of each of the integers from \\$1\\$ to \\$n^2\\$ where every row, column, and diagonal sum to the same value. For example, a 3×3 magic square is as follows:

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

```

Here, each row, column, and diagonal sum to the magic sum of 15, which can be calculated with the following formula:

$$ n × \frac{n^2 + 1}{2} $$

Even if you didn't have the full `n×n` magic square, you could reproduce it without guessing. For example, given just the 4, 9, 2, and 3 of the prior magic square, you could fill

```
4 9 2    4 9 2    4 9 2    4 9 2    4 9 2    4 9 2
3 _ _ => 3 _ _ => 3 5 _ => 3 5 7 => 3 5 7 => 3 5 7
_ _ _    8 _ _    8 _ _    8 _ _    8 1 _    8 1 6

```

## Task

Given a partially-filled magic square, your program or function should output the full magic square.

The input is guaranteed to be part of of a magic square, such that the only deduction necessary to solve it is taking a row, column, or diagonal in which `n-1` values are determined and filling in the final entry (**without** this rule, `4 9 _ / _ _ _ / _ _ _` would be a valid input since only one magic square starts `4 9`, but that would require a more complicated approach or a brute-force of all possibilities).

Input and output may be any reasonable format for a square matrix (`n`×`n` matrix datatype; string representations; length-`n×n` flat array; etc.). In all formats, you may optionally take `n` as another input.

You may use any character or value other than `_` in the input to represent blanks as long as that value is unmistakable for a possible entry.

Related variant: Is Magic Possible?

## Sample Testcases

(one newline between input and output; three between cases)

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

4 9 2
3 5 7
8 1 6

4 9 2
3 _ _
_ _ _

4 9 2
3 5 7
8 1 6

4 9 _
_ 5 _
_ _ _

4 9 2
3 5 7
8 1 6

_ _ _
_ 5 7
_ 1 6

4 9 2
3 5 7
8 1 6

_   16  13  _
11  5   _   _
7   9   12  6
_   _   _   15

2   16  13  3
11  5   8   10
7   9   12  6
14  4   1   15

1   23  _   4   21
15  14  _   18  11
_   _   _   _   _
20  8   _   12  6
5   3   _   22  25

1   23  16  4   21
15  14  7   18  11
24  17  13  9   2
20  8   19  12  6
5   3   10  22  25

```

# Answer
> 9 votes
# MATL, 36 bytes

```
`nZ@[]etGg)GXz-yt!hs&ytXdwPXdhsh&-ha

```

The input is an \\$ n \times n\\$ matrix, with \\$0\\$ for the unknown numbers.

The code keeps generating random \\$ n \times n\\$ matrices formed by the numbers \\$1, \dots, n^2\\$ until one such matrix meets the required conditions. This procedure is guaranteed to finish with probability one.

This is a terrible approach, in that:

* running time is random, and unbounded;
* average running time increases as \\$(n^2)!\\$ (that's more than exponentially);
* and so it very likely times out in the online interpreter.

... but hey, it's the shortest answer so far!

(Don't) try it online.

See below a sped-up animated GIF of an example run which happened to take about 2 minutes, here compressed to a few seconds.

## Explanation

```
`         % Do...while
  n       %   Number of elements. This implictly takes the input in the first
          %   iteration, or uses the candidate solution from the previous iteration.
          %   Let this number be denoted as N
  Z@      %   Random permutation of integers 1, 2, ..., N
  []e     %   Reshape as a square matrix. This yields a candidate solution
  t       %   Duplicate
  Gg)     %   Push input, convert to logical, index: this produces a column vector
          %   of the entries of the candidate solution that correspond to nonzero
          %   entries in the input matrix
  GXz     %   Push input, take its nonzero elements. Gives a column vector
  -       %   Element-wise difference (*). This will be all zeros for a valid
          %   solution
  y       %   Duplicate second-top object from the stack, that is, the candidate
          %   solution
  t!      %   Duplicate, transpose
  h       %   Concatenate horizontally
  s       %   Sum of columns. This also gives the sum of rows, thanks to the
          %   concatenated, transposed copy. The result is a two-element row
          %   vector (**)
  &y      %   Duplicate third-top object from the stack: the candidate solution
  tXd     %   Duplicate, extract diagonal as a column vector
  wPXd    %   Swap, flip vertically, extract diagonal. This gives the anti-diagonal
          %   as a column vector
  h       %   Concatenate horizontally
  s       %   Sum of each column. This gives the sum of the diagonal and that
          %   of the anti-diagonal
  h       %   Concatenate horizontally with (**)
  &-      %   Matrix of all element-wise differences. This will be a matrix of
          %   zeros for a valid solution (***)
  h       %   Concatenate (*) and (***) horizontally. Since sizes do not match,
          %   both (*) and (***) are first linearized to row vectors, and the
          %   result is a row vector
  a       %   Any. This gives true if any element is non-zero
          % End (implicit). A new iteration is run if the top of the stack is true
          % Display (implicit). The candidate solution from the last iteration is
          % the valid solution

```

# Answer
> 6 votes
# JavaScript, ~~559~~ 551 bytes

Fast and methodical.

```
B=Boolean,f=((e,r)=>(v=r*((r**2+1)/2),e.forEach(e=>e.filter(B).length==r-1?e[e.findIndex(e=>!e)]=v-e.reduce((e,f)=>!(e+=f)||e):0),e[0].reduce((f,l,n)=>!(f[0].push(e[n][n])+f[1].push(e[n][r-1-n]))||f,[[],[]]).forEach((f,l)=>{f.filter(B).length==r-1&&(z=f.findIndex(e=>!e),e[z][l?r-1-z:z]=v-f.reduce((e,f)=>!(e+=f)||e))}),e[0].reduce((f,r,l)=>f.forEach((f,r)=>f.push(e[l][r]))||f,new Array(r).fill().map(()=>[])).forEach((f,l)=>f.filter(B).length==r-1?e[f.findIndex(e=>!e)][l]=v-f.reduce((e,f)=>!(e+=f)||e):0),e.flat(2).filter(B).length==r*r?e:f(e,r)));

```

Live examples:

```
B=Boolean,f=((e,r)=>(v=r*((r**2+1)/2),e.forEach(e=>e.filter(B).length==r-1?e[e.findIndex(e=>!e)]=v-e.reduce((e,f)=>!(e+=f)||e):0),e[0].reduce((f,l,n)=>!(f[0].push(e[n][n])+f[1].push(e[n][r-1-n]))||f,[[],[]]).forEach((f,l)=>{f.filter(B).length==r-1&&(z=f.findIndex(e=>!e),e[z][l?r-1-z:z]=v-f.reduce((e,f)=>!(e+=f)||e))}),e[0].reduce((f,r,l)=>f.forEach((f,r)=>f.push(e[l][r]))||f,new Array(r).fill().map(()=>[])).forEach((f,l)=>f.filter(B).length==r-1?e[f.findIndex(e=>!e)][l]=v-f.reduce((e,f)=>!(e+=f)||e):0),e.flat(2).filter(B).length==r*r?e:f(e,r)));

console.log(JSON.stringify(f([
  [4, 9, 2],
  [0, 5, 0],
  [0, 0, 0]
], 3)));

console.log(JSON.stringify(f([
  [1, 23, 0, 4, 21],
  [15, 14, 0, 18, 11],
  [0, 0, 0, 0, 0],
  [20, 8, 0, 12, 6],
  [5, 3, 0, 22, 25]
], 5)));
```

The "un"-golfed version can be seen at this Github repository.

# Answer
> 4 votes
# APL (Dyalog Unicode), 60 bytes

```
{(⍵,m+.×1+⍺*2)⌹(∘.(×⊢×=)⍨⍵)⍪2×m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺}

```

Try it online!

Not likely the shortest approach, but anyway here is one with Matrix Divide , a.k.a. Solve Linear Equation. This works because all the cells are uniquely determined by the horizontal/vertical/diagonal sums when joined with the givens.  has no problem with over-determined systems, as long as there is a solution (otherwise, it finds the least-squares fit).

A dyadic inline function (dfn) where the left argument is the side length and the right argument is the flattened matrix.

In the case of `[4 9 2][3 0 0][0 0 0]`, the coefficient matrix and constant vector are given as follows:

```
Coefficients        Constants
-------------------------------
Part 1: Givens
1 0 0 0 0 0 0 0 0   4
0 1 0 0 0 0 0 0 0   9
0 0 1 0 0 0 0 0 0   2
0 0 0 1 0 0 0 0 0   3
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0
0 0 0 0 0 0 0 0 0   0

Part 2: Magic Square sums
2 0 0 0 2 0 0 0 2   30  # diagonals
0 0 2 0 2 0 2 0 0   30
2 2 2 0 0 0 0 0 0   30  # rows
0 0 0 2 2 2 0 0 0   30
0 0 0 0 0 0 2 2 2   30
2 0 0 2 0 0 2 0 0   30  # columns
0 2 0 0 2 0 0 2 0   30
0 0 2 0 0 2 0 0 2   30

```

which is a set of 17 equations for 9 unknowns.

```
{(⍵,m+.×1+⍺*2)⌹(∘.(×⊢×=)⍨⍵)⍪2×m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺}

m←(⍪↑c(⌽c))⍪(⊢⍪⍴⍴⍉)⍺/c←∘.=⍨⍳⍺  ⍝ Construct the sums part of the coef matrix
                     c←∘.=⍨⍳⍺  ⍝ ⍺ × ⍺ identity matrix
                   ⍺/  ⍝ ⍺ copies of each horizontally, giving the "rows" part
            (  ⍴⍴⍉)    ⍝ Reshape the transpose of above into the original,
                       ⍝ giving the "columns" part
             ⊢⍪        ⍝ Vertically concatenate two parts
m←(⍪↑c(⌽c))⍪  ⍝ Generate the "diagonals" part and vertically prepend to above

(∘.(×⊢×=)⍨⍵)⍪2×m  ⍝ Construct the entire coef matrix
             2×m  ⍝ Use twos so that we can avoid halving the constant
(          )⍪     ⍝ Vertically concatenate with...
 ∘.(×⊢×=)⍨⍵       ⍝ The square diagonal matrix where nonzero entries of ⍵ give
                  ⍝ a 1 at the corresponding position, 0 otherwise

(⍵,m+.×1+⍺*2)  ⍝ Construct the constant vector
       1+⍺*2   ⍝ Square of ⍺ plus 1
   m+.×        ⍝ Matmul with m, which has ⍺ ones on each row,
               ⍝ giving (# of rows of m) copies of ⍺ times above
 ⍵,            ⍝ Prepend ⍵ to above

⌹  ⍝ Solve the linear system of equations; no postprocessing necessary

```

# Answer
> 4 votes
# JavaScript (ES7),  ~~143 142~~  140 bytes

Expects `(n)(m)`, where unknown cells in `m` are filled with 0's.

```
n=>g=m=>[0,1,2,3].some(d=>m.some((r,i)=>m.map((R,j)=>t^(t-=(v=d?R:r)[x=[j,i,j,n+~j][d]])||(e--,X=x,V=v),e=1,t=n**3+n>>1)&&!e))?g(m,V[X]=t):m

```

Try it online!

### Commented

```
n =>                          // outer function taking n
  g = m =>                    // inner function taking the matrix m[]
    [0, 1, 2, 3]              // list of directions
    .some(d =>                // for each direction d:
      m.some((r, i) =>        //   for each row r[] at position i in m[]:
        m.map((R, j) =>       //     for each row R[] at position j in m[]:
          t ^ (               //       test whether t is modified:
            t -=              //         subtract from t:
              (v = d ? R : r) //           use v = r[] if d = 0 or v = R[] otherwise
              [x =            //           use:
                [ j,          //             r[j] if d = 0 (rows)
                  i,          //             R[i] if d = 1 (columns)
                  j,          //             R[j] if d = 2 (diagonal)
                  n + ~j      //             R[n - 1 - j] if d = 3 (anti-diagonal)
                ][d]          //
              ]               //
          ) || (              //       if t was not modified:
            e--,              //         decrement e
            X = x,            //         copy x to X
            V = v             //         copy v to V
          ),                  //
          e = 1,              //       start with e = 1
          t = n**3 + n >> 1   //       start with t = n(n²+1)/2
        )                     //     end of map()
        && !e                 //     e = 0 means that there's exactly one cell set
                              //     to zero in this vector
      )                       //   end of inner some()
    ) ?                       // end of outer some(); if truthy:
      g(m, V[X] = t)          //   update V[X] to t and do a recursive call
    :                         // else:
      m                       //   done: return m[]

```

# Answer
> 3 votes
# Brachylog, 47 44 bytes

```
{0∧|}ᵐ²{l⟦₅gj↔ʰc;?z∋₍ᵐġ,?;?\ᵗc+ᵐ=&c≠≤ᵛ√~l?≜}

```

Try it online!

### How it works

In classic Prolog style we replace zeros with uninitiated variables and based on the constraints let Brachylog figure out a solution. In Prolog you could just write `[1,_,_]` for unknown variables, in Brachylog you would have to write `[1,A,B]` and that seems too far away from the usual I/O restriction. So we use 0 for unknowns and convert them to uninitiated variables by:

```
{∧0|}ᵐ²

```

If a value is 0 try something else, otherwise use the value itself.

```
l⟦₅gj↔ʰc;?z∋₍ᵐ
l               length of array, N
 ⟦₅             0…N-1
   gj           [0…N-1],[0…N-1]
     ↔ʰc        0…N-1,N-1…0
        ;?z     [[0,first row], …, [N-1,last row],
                 [N-1,first row], …, [0,last row]]
           ∋₍ᵐġ [diagonal \, diagonal /]

```

This feels a bit long just to get the two diagonals. Basically calculate the indices, zip them with the rows, and get the elements.

```
,?;?\ᵗc

```

Append all rows and all transposed rows.

```
+ᵐ=

```

Sum every row. All sums (f.e. 15 in the 3x3 case) must be equal to each other. We don't have to calculate 15 explicitly, as this follows from the next constraint:

```
&c≠≤ᵛ√~l?
 c            the rows concatenated
  ≠           all elements are different
   ≤ᵛ         and are less-equal than X,
     √        and the root of X is
      ~l?     the length of the input
              which is implicitly the output

```

The numbers are distinct and between 1 and N^2.

# Answer
> 3 votes
# , ~~169~~ ~~180~~ ~~142~~ 135 bytes

*Edits: +11 bytes to rotate the magic square back to it's original orientation, -38 bytes by wrapping "replace-only-missing-element" into a function, -7 bytes by various golf obfuscations*

```
function(m,n){while(F%%4|sum(!m)){m[n:1,]=apply(m,1,f<-function(v){if(sum(!v)<2)v[!v]=(n^3+n)/2-sum(v);v})
m[d]=f(m[d<-!0:n])
F=F+1}
m}

```

Try it online!

Solves rows & the first diagonal, then rotates the matrix anticlockwise (so cols become rows in the opposite order) and repeats, until there are no empty elements left. ~~Outputs the completed magic-square matrix in one of 4 possible rotated forms.~~ Then rotates matrix back to its original orientation.

Commented readable version:

```
solve=function(m,n){
    t=(n^3+n)/2                         # t = desired total of each row/col/diag
    f=function(v){                      # f = function to check if a vector
        if(sum(!v)==1)v[!v]=t-sum(v);v  # has only 1 missing element, and if so
    }                                   # fill it with t-sum(elements).
    while(F%%4|sum(!m)){                # While rotations are not multiple-of-4, or
                                        # there are still some empty elements of m:
        m[n:1,]=                        # rotate the matrix anticlockwise, while
            apply(m,1,f)                # using f() to fix any rows; then
        d=1:(n+1)==1                    # define diagonal as every (n+1)th element,
        m[d]=f(m[d])                    # and use f() to fix diagonal.
        F=F+1                           # Count rotations so far,
    }                                   # and repeat.
    m                                   # Finally, output m.
}

```

# or awfully-slow , ~~124~~ ~~123~~ ~~109~~ 105 bytes

*Edit: -14 bytes thanks to Xi'an*

```
function(m,n){x=m;`?`=rowSums;while(any(sum(x[0:n<1])!=c(sum(diag(x)),?x,?t(x))))x[!m]=sample(n^2)[-m];x}

```

Try it online!

Generates random permutations of the missing elements until it finds one where all row, column and diagonal sums are all equal.

# Answer
> 2 votes
# 05AB1E, 43 41 30 bytes

*-2 bytes by replacing `Dgt` with `¹` to get first input back*

*-11 bytes thanks to Kevin Cruijssen!*

```
nLœʒ¹ôD©ø®Å\®Å/)O˜Ë}ʒøε¬_sË~}P

```

Try it online! Takes input as (n, flattened square), where zeros represent blanks, like

```
3
[4,9,2,3,0,0,0,0,0]

```

Works by generating all permutations of the numbers from 1 to n2, filtering to only keep those that are magic squares, and then iterating through and printing all that match the partial input (by input constraints, there will always only be one match). Because of this brute-force approach, it's already very slow for 3x3 magic squares and I doubt 5x5 would terminate. This is my first 05AB1E answer, so I'm sure there's savings to be had here.

The magic square checking is borrowed from Kevin Cruijssen.

**Explanation:**

```
n      # Square input (implicit) (3 → 9)
 L     # Generate list from 1 to n^2 ([1,2,...,9])
  œ    # All permutations
   ʒ   # Filter by:
¹       # Recover n by pushing first input again
        # Check if magic square, borrowed from Kevin Cruijssen
 ô      # Split permutation into parts of size n
  D     # Duplicate
   ©    # Store in register (without popping)
    ø   # Zip rows to get columns
®       # Push from register
 Å\     # Take main diagonal
®       # Push from register
 Å/     # Take anti diagonal
)       # Flatten stack into one list
 O      # Take sum (of each row/column/diagonal)
  Ë     # Check if all values are equal
     } # End filter (to get magic squares)
ʒ      # Filter magic squares by:
 ø      # Zip together magic square and input (implicit)
ε       # Map
 ¬       # Push the input again
  _      # Input equals 0 (to produce mask)
s        # Manage stack (swap mask and zipped args)
 Ë       # Partial equals potential match
  ~      # Bitwise OR to combine masks
    }   # End map
P      # Take product (effectively logical AND) to verify
       # that combined mask is all 1s
      # Implicit output

```

# Answer
> 2 votes
# Wolfram Language (Mathematica), 100 bytes

```
#/.Solve[Tr/@Flatten[{#,Thread@#,{(d=Diagonal)@#,d@Reverse@#}},1]==Table[(l^3+l)/2,2(l=Tr[1^#])+2]]&

```

Try it online!

# Answer
> 1 votes
# Jelly, 25 bytes

```
ZṚ,⁸;Jị"$€$§FE
²Œ!ṁ€ÇƇ=ÐṀ

```

A full program taking `n` and a list-of-lists-formatted representation of the incomplete square which prints the result in the same format.

Try it online! \- too slow for TIO's 60s limit
...so, **Try a limited space** one which only considers the first 150K permutations - three magic squares two of which match at two and three locations.

### How?

Unfortunately, even with the ability to deduce the missing numbers one at a time, I believe brute-forcing will be terser, so that is how this works.

```
ZṚ,⁸;Jị"$€$§FE - Link 1, Is this a magic-square?: list of lists, M
Z              - transpose (M)
 Ṛ             - reverse (together ZṚ rotate 1/4)
  ,⁸           - pair with chain's left argument (M)
          $    - last two links as a monad:
         €     -   for each (m in (MZṚ, M)):
        $      -     last two links as a monad:
     J         -       range of length = [1..n]
       "       -       zip with:
      ị        -         index into - i.e. get the leading diagonal
    ;          -   concatenate (m with it's diagonal)
           §   - sums
            F  - flatten
             E - all equal?

²Œ!ṁ€ÇƇ=ÐṀ - Main Link: integer, N; list of lists, P
²          - square (n)
 Œ!        - all permutations of (implicit range [1..n²])
   ṁ€      - mould each like (P)
      Ƈ    - filter keep those for which:
     Ç     -   call the last Link as a monad  - i.e. keep magic squares
        ÐṀ - keep those which are maximal under:
       =   -   equals (P) (vectorises) - i.e. keep the one which matches at all givens
           - implicit print, which when given a list containing only one item prints that item

```

# Answer
> 0 votes
# Charcoal, 81 bytes

```
ＦθＦι⊞υκＵＭθκ≔ＬθηＦυＦ⁺⁺⪪ＥυληＥθ⁺λ×θη⟦×θ⊕η×⊕θ⊖η⟧«≔Ｅκ§υλι¿⁼¹№ι⁰§≔υ§κ⌕ι⁰⁻÷×⊕×ηηη²Σι»Ｉ⪪υη

```

Try it online! Link is to verbose version of code. Uses zero as the "blank" marker. Explanation:

```
ＦθＦι⊞υκ

```

Flatten the input array.

```
ＵＭθκ

```

Replace the original array with a range from `0` to `n-1`.

```
≔Ｌθη

```

Also the length of the array is used a lot so capture it in a temporary to save 3 bytes.

```
Ｆυ

```

Loop  times, which is more than enough to track down all the solvable `0`s.

```
Ｆ⁺⁺

```

Loop over all of the following ranges:

```
⪪Ｅυλη

```

the range from `0` to `n²-1`, split into subranges of length `n`;

```
Ｅθ⁺λ×θη

```

the subranges obtained from the range from `0` to `n²-1`, but taking every `n`th element (so effectively the transpose of the above);

```
⟦×θ⊕η×⊕θ⊖η⟧«

```

the range from `0` to `n²-1` in steps of `n+1`, which is the main diagonal, and the range from `n-1` to `n²-n` in steps of `n-1`, which is the main antidiagonal.

```
≔Ｅκ§υλι

```

Get the values in the flattened array corresponding to the elements of the current range.

```
¿⁼¹№ι⁰

```

Count whether exactly one of them is zero.

```
§≔υ§κ⌕ι⁰

```

If so then overwrite that entry in the flattened array...

```
⁻÷×⊕×ηηη²Σι

```

... with `½n(n²+1)` minus the sum of the (other) elements.

```
»Ｉ⪪υη

```

Split the flattened array back into rows and convert the values to strings for implicit print.

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


title: Trilaterate your position

text:
# Question
Title: Trilaterate your position
# Introduction

Imagine you are on a two dimensional cartesian plane and want to determine your position on it. You know 3 points on that plane and your distance to each of them. While it is always possible to calculate your position from that, doing that in your head is pretty hard. So you decide to write a program for that.

# The Challenge

Given 3 points and your distance to them, output the cordinates of your position.

* Input and output may be in any convenient format, including using complex instead of real numbers. Please clarify in your answer which format you use.
* You will always get exactly 3 distinct points with their distance to you.
* The coordinates and distances will be floats with arbitrary precision. Your output has to be correct to 3 decimal places. Rounding is up to you. Please clarify in your answer.
* You may assume that the three points are not collinear, so there will be always an unique solution.
* You are not allowed to bruteforce the solution.
* You may not use any builtins that trivialize this particular problem. Builtins for vector norms, etc. are allowed though.

**Hint to get started:**

> Think about a circle around each of those 3 points with their distance to you as radius.

# Rules

# Test cases

Input format for one point here is `[[x,y],d]` with `x` and `y` being the coordinates and `d` being the distance to this point. The 3 of those points are arranged in a list. Output will be `x` and then `y` in a list.

```
[[[1, 2], 1.414], [[1, 1], 2.236], [[2, 2], 1.0]] -> [2, 3]
[[[24.234, -13.902], 31.46], [[12.3242, 234.12], 229.953], [[23.983, 0.321], 25.572]] -> [-1.234, 4.567]
[[[973.23, -123.221], 1398.016], [[-12.123, -98.001], 990.537], [[-176.92, 0], 912.087]] -> [12.345, 892.234]

```

You can generate additional test cases with this Pyth program. Location goes on the first line of the input and the 3 points are on the following 3 lines.

**Happy Coding!**

# Answer
# Desmos, 122 bytes

Online use. Copy+paste each equation into an equation box, click "add all" for each box, then click on the point of intersection, then enter in each value as appropriate. each of `A`, `B`, and `C` are the distances for the points `(a,b)`, `(c,d)`, and `(E,f)`, respectively. To get a square root in the value, type `sqrt` then the value in the box.

```
\left(x-a\right)^2+\left(y-b\right)^2=AA
\left(x-c\right)^2+\left(y-d\right)^2=BB
\left(x-E\right)^2+\left(y-f\right)^2=CC

```

Verify the first test case.

Or you can take a look here:
> 5 votes

# Answer
## C, ~~362~~ ~~348~~ 345 bytes

Input is given as a sequence of space-separated floats on stdin: `x1 y1 d1 x2 y2 d2 x3 y3 d3`. Output is similar on stdout: `x y`.

```
#define F"%f "
#define G float
#define T(x)(b.x*b.x-a.x*a.x)
typedef struct{G a;G b;G c;}C;G f(C a,C b,G*c){G x=b.b-a.b;*c=(T(a)+T(b)-T(c))/x/2;return(a.a-b.a)/x;}main(){C a,b,c;G x,y,z,t,m;scanf(F F F F F F F F F,&a.a,&a.b,&a.c,&b.a,&b.b,&b.c,&c.a,&c.b,&c.c);x=f(a,a.b==b.b?c:b,&y);z=f(b.b==c.b?a:b,c,&t);m=t-y;m/=x-z;printf(F F"\n",m,x*m+y);}

```

`C` is a structure type whose members are an x-coordinate `a`, a y-coordinate `b`, and a distance (radius) `c`. The function `f` takes two `C` structures and a pointer to a float, and determines the line at which the `C` (circles) intersect. The y-intercept of this line is placed into the pointed-to float, and the slope is returned.

The program calls `f` on two pairs of circles, then determines the intersection of the produced lines.
> 4 votes

# Answer
# APL (Dyalog Unicode) 18.0, 23 bytes

```
-∘(+/)⍥(×⍨)⌹⍥(2-⌿⊢)¯2×⊢

```

Try it online!

A tacit infix function that can be called like `dists f pts`, where `pts` contains three centers' coordinates as a 3-row 2-column matrix, and `dists` contains three distances to the respective centers.

Uses 18.0 feature . TIO's Dyalog Unicode is not updated yet from 17.1, so TIO link uses Dyalog Extended for demonstration purposes.

### How it works

Uses the same method as R.T.'s Python answer, i.e. constructing a linear system of equations and solving it.

The distance equations are necessarily quadratic. Then how did we get linear ones?

Let's consider just two circles, and denote the point we want to find as \\$P\\$, two circles' centers as \\$C, D\\$, and their radii as \\$r\_C, r\_D\\$. Also, let's use \\$A\_x, A\_y\\$ for the \\$x\\$\- and \\$y\\$-coordinates of a point \\$A\\$. Then the following equations hold:

$$ (P\_x-C\_x)^2+(P\_y-C\_y)^2 =r\_C^2 \\ (P\_x-D\_x)^2+(P\_y-D\_y)^2 =r\_D^2 \\ $$

Then we expand them and subtract the second from the first:

$$ P\_x^2-2P\_xC\_x+C\_x^2+P\_y^2-2P\_yC\_y+C\_y^2=r\_C^2\\ P\_x^2-2P\_xD\_x+D\_x^2+P\_y^2-2P\_yD\_y+D\_y^2=r\_D^2\\ -2P\_x(C\_x-D\_x)+(C\_x^2-D\_x^2)-2P\_y(C\_y-D\_y)+(C\_y^2-D\_y^2)=r\_C^2-r\_D^2\\ -2P\_x(C\_x-D\_x)-2P\_y(C\_y-D\_y)=(r\_C^2-C\_x^2-C\_y^2)-(r\_D^2-D\_x^2-D\_y^2) $$

We've just got one linear equation on \\$P\_x\\$ and \\$P\_y\\$. Since we have three circles given, we can take any two pairs and construct two equations, which then solving the system of equations gives the coordinates we want.

```
-∘(+/)⍥(×⍨)⌹⍥(2-⌿⊢)¯2×⊢  ⍝ Left: dists, Right: pts
-∘(+/)⍥(×⍨) ⍥(2-⌿⊢)      ⍝ Constants part
      ⍥(×⍨)              ⍝ Square each number in both dists and pts
 ∘(+/)                   ⍝ Row sums of squared pts
-                        ⍝ Subtract above from squared dists
            ⍥(2-⌿⊢)      ⍝ Take pairwise difference

            ⍥(2-⌿⊢)¯2×⊢  ⍝ Coefficients part
                   ¯2×⊢  ⍝ -2 times pts
            ⍥(2-⌿⊢)      ⍝ Take pairwise difference between rows
           ⌹             ⍝ Solve linear equations

```
> 4 votes

# Answer
# Python - 172

Takes input as a list of tuples of form (x,y,d). Let me know if you see a way to golf this further, I feel like there must be but I can't figure it out!

```
import numpy as N
def L(P):
    Z=[p[2]**2-p[0]**2-p[1]**2 for p in P];return N.linalg.solve([[P[i][0]-P[0][0],P[i][1]-P[0][1]]for i in[1,2]],[(Z[0]-Z[i])*0.5 for i in [1,2]])

```
> 3 votes

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