title: Seven's Cycle Sum Sequence

text:
# Question
Title: Seven's Cycle Sum Sequence
Take a look at the sevens multiplication table from 7×0 to 7×9:

```
0, 7, 14, 21, 28, 35, 42, 49, 56, 63

```

If we just look at the digits in the one's place we get a permutation of the digits 0 through 9:

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

```

Consider taking some positive decimal integer N and replacing each digit D in N with the the digit in the one's place of 7×D.

For example, `15209` becomes `75403` because `1` maps to `7`, `5` maps to `5`, `2` maps to `4`, `0` maps to `0`, and `9` maps to `3`.

Now lets repeat this process with this new decimal integer until we see a cycle, i.e. until an integer we've already seen comes up.

For example, with `15209` we get the cycle

```
15209 -> 75403 -> 95801 -> 35607 -> 15209 -> repeats...
                                      ^
                                      |
                             cycle restarts here

```

As another example, `505` has the short cycle

```
505 -> 505 -> repeats...
        ^
        |
cycle restarts here

```

It turns out that for any N these cycles will always contain exactly 1 or 4 distinct integers. (I'll leave it to you to figure out why that is.) What's interesting is that if you sum all the distinct integer in a cycle, you almost always get a decimal integer that only consists of `2`'s and `0`'s.

For example, 15209 + 75403 + 95801 + 35607 = 222020.

N = 505 is one of the exceptions. The only integer in the cycle is 505 so the total sum is 505 itself.

Here are the sums of the cycles for N = 1 to 60:

```
N sum
1 20
2 20
3 20
4 20
5 5
6 20
7 20
8 20
9 20
10 200
11 220
12 220
13 220
14 220
15 220
16 220
17 220
18 220
19 220
20 200
21 220
22 220
23 220
24 220
25 220
26 220
27 220
28 220
29 220
30 200
31 220
32 220
33 220
34 220
35 220
36 220
37 220
38 220
39 220
40 200
41 220
42 220
43 220
44 220
45 220
46 220
47 220
48 220
49 220
50 50
51 220
52 220
53 220
54 220
55 55
56 220
57 220
58 220
59 220
60 200
```

We'll call this the Seven's Cycle Sum Sequence.

# Challenge

Write a program or function that takes in a positive decimal integer N and prints or returns, in decimal, the corresponding term of the Seven's Cycle Sum Sequence.

For example, if the input is `95801`, the output should be `222020`. If the input is `505`, the output should be `505`. If the input is `54`, the output should be `220`.

The shortest code in bytes wins.

# Answer
# Pyth, 14 bytes

```
s.uieM*R7jNTTQ

```

Not sure, why everybody determines the result by looking at patterns in the numbers. Simply doing the process, calculating all numbers of the circle and summing them up is shorter. At least in Pyth ;-)

Try it online: Demonstration or Test Suite

Btw, this is my 200th code-golf answer. So this post earns me the Gold code-golf badge.

### Explanation:

```
s.uieM*R7jNTTQ   implicit: Q = input number
 .u          Q   apply the following expression to N=Q until it reaches a circle
         jNT        convert N to base 10
      *R7           multiply each digit with 7
    eM              and perform modulo 10 for each number
   i        T       convert digits from base 10 to a number
                    update N
                 .u returns the list of all intermediate results of N,
                 so we have now all numbers of the circle
s                sum them up

```
> 1 votes

# Answer
## Python 2, 69 bytes

```
lambda n:[''.join('02'[x>'0']for x in`n`)+'0',n][set(`n`)<=set('05')]

```

The function is simple to describe:

* If n consists of only 0's and 5's, output it unchanged.
* Otherwise, replace each digit of n with 2, except 0 stays 0, and tack on a 0 to the end.

The golfing can be improved, I'm mostly posting to share the method. A language with native regex should allow a short solution.

An alternative statement of the function is

* In n, replace each digit with a 5, except 0 stays as 0
* If this changed n (it had a digit other than 0 or 5), multiply the result by 4
> 5 votes

# Answer
# Python 2, 63 bytes

```
lambda s:s.strip('05')and''.join(`(c>'0')*2`for c in s)+'0'or s

```

Input argument is expected to be a string.
> 4 votes

# Answer
## CJam, 16 bytes

Using the same algorithm as everyone else:

```
r_50s-{:~2fe&0}&

```

Test suite. (Generates all results from 1 to the input.)

### Explanation

```
r_      e# Read input and duplicate
50s     e# Push the string "50".
-       e# Remove all '5' and '0' characters from the input.
{       e# If any characters remained in the input...
  :~    e#   Evaluate each digit character to turn it into an integer.
  2fe&  e#   Map (&& 2) over the list. Due to short-circuiting, zeros remain zeros and
        e#   everything else becomes 2.
  0     e#   Push a trailing zero.
}&

```
> 4 votes

# Answer
# JavaScript (ES6), ~~54~~ 51 bytes

Using xnor's method:

```
n=>/[^05]/.test(n)?`${n}0`.replace(/./g,d=>+d&&2):n

```

*Saved 3 bytes thanks to @charlie!*

## Explanation

```
n=>
  (s=n+"").match`[^05]`          // if there are any digits which aren't 5 or 0
    ?s.replace(/\d/g,d=>+d&&2)+0 //     replace every digit except 0 with 2 then add a 0
  :s                             // else return the input unchanged

```

## Test

```
<input type="number" id="input" value="0" oninput='result.textContent=(

n=>(s=n+"").match`[^05]`?s.replace(/\d/g,d=>+d&&2)+0:s

)(+input.value)' />
<pre id="result"></pre>
```

## Naive method, 102 bytes

```
n=>(c=x=>~r.indexOf(x+=m="")?eval(r.join`+`):[...r[++i]=x].map(d=>m+="0741852963"[d])&&c(m))(n,i=r=[])

```

```
n=>
  (c=x=>                  // c = recursive function
    ~r.indexOf(           // if we have calculated this number before
      x+=m="")?           // cast x to a string, m = calculated result
        eval(r.join`+`):  //     return the sum of all the calculated numbers
    [...r[++i]=x].map(d=> // else add x to the list of calculated numbers
      m+="0741852963"[d]  // map each digit of x to the "seven" digits
    )&&c(m)               // calculate the value of the result
  )(n,i=r=[])             // r = array of previously calculated values

```

```
<input type="number" id="input" value="0" oninput='result.textContent=(

n=>(c=x=>~r.indexOf(x+=m="")?eval(r.join`+`):[...r[++i]=x].map(d=>m+="0741852963"[d])&&c(m))(n,i=r=[])

)(+input.value)' />
<pre id="result"></pre>
```
> 3 votes

# Answer
## Mathematica, ~~83~~ ~~77~~ 60 characters

```
Tr@Union@NestList[FromDigits@Mod[7IntegerDigits@#,10]&,#,4]&

```

**Ungolfed**

```
Tr@
  Union@
   NestList[
    FromDigits@Mod[7 IntegerDigits@#, 10] &,
    #,
    4
   ] &

```
> 2 votes

# Answer
# JavaScript (ES5), 40 bytes

```
n=>(s=`${n}`.replace(/[^0]/g,5))^n?s*4:n

```

It's an evolution of the user81655's solution, using the alternative approach described by xnor.

### Explanation

Sum of a non-zero digit in the 4-cycle is always 20, since the digit cycles either through 1→7→9→3, or 2→4→8→6, or 5→5→5→5. So replacing every such a digit with 5 doesn't change the sum.

That replacement action is reused to distinguish the 4-cycle from 1-cycle — if the replacement result is different from the input, then it's a 4-cycle, otherwise it's a 1-cycle.

*N.B.: The template string ``${n}`` is just for readability, `(n+'')` has the same length.*
> 2 votes

# Answer
# sed, 26 bytes

`/[^05]/{s/[^0]/2/g;s/$/0/}`

*(Another take on the "replace by 2's" approach.)*

### Examples

`echo '500' | sed '/[^05]/{s/[^0]/2/g;s/$/0/}'``500`

`echo '501' | sed '/[^05]/{s/[^0]/2/g;s/$/0/}'``2020`
> 0 votes

# Answer
# Perl 6,  ~~68 55 53 36~~  33 bytes

~~```
{[+] $^a,{[~] $^b.comb.map: {'0741852963'.comb[$_]}}...^{$++*?/$a/}} # 68

```

```
{$_=@=$_.comb;[~] (@$_,(|.map(2*?+*),0))[$_⊈qw<0 5>]} # 55

```

```
{[~] ($_=@=$_.comb)⊆qw<0 5>??@$_!!(|.map(2*?+*),0)} # 53

```

```
{/^<[05]>+$/??$_!!S:g/./{2*?+$/}/~0} # 36

```~~
```
{m/^<[05]>+$/||S:g/./{2*?+$/}/~0} # 33

```

This is definitely the wrong way to do this, if the number is consists only of `5`s and `0`s it will return a Match object, otherwise it replaces everything but `0` with a `2`, and append a `0` to the end.
( The Match object will behave like a number if you use it as one )

Though since it is doing it wrong, it makes it easy to point out the rare numbers by calling the `gist` method.

usage:

```
# give it a name
my &code = {...}

.say for (0..60,505,15209).flat.map({ code($_).gist.fmt: '%4s' }).rotor(1,10 xx 6,:partial)

( ｢0｣)
(  20   20   20   20  ｢5｣   20   20   20   20  200)
( 220  220  220  220  220  220  220  220  220  200)
( 220  220  220  220  220  220  220  220  220  200)
( 220  220  220  220  220  220  220  220  220  200)
( 220  220  220  220  220  220  220  220  220 ｢50｣)
( 220  220  220  220 ｢55｣  220  220  220  220  200)
(｢505｣)
(222020)

```
> 0 votes

# Answer
# Jelly, 9 bytes

```
D×7%⁵ƊƬḌS

```

Try it online!

## How it works

```
D×7%⁵ƊƬḌS - Main link. Takes an integer n on the left
D         - Convert to digits
     ƊƬ   - Repeat the following until a value is repeated and collect all intermediate values:
 ×7       -   Multiply each digit by 7
   %⁵     -   Take the ones digit
       Ḍ  - Convert each list of digits back to a number
        S - Take the sum

```
> 0 votes

---
Tags: code-golf, number, arithmetic, sequence
---


title: Power-Ending Patterns

text:
# Question
Title: Power-Ending Patterns
When you look at the last decimal digit of each power of a non-negative integer a repeating pattern forms. For example, 3:

```
3^1 =     3
3^2 =     9
3^3 =    27
3^4 =    81
3^5 =   243
3^6 =   729
3^7 =  2187
3^8 =  6561
3^9 = 19683

```

The last digits go `3971` which repeats indefinitely. In fact any number we choose that ends in 3 has that same pattern because none of the other digits can have an effect on the ones place during repeated multiplication.

What's curious is that some numbers have a much shorter cycle of power-ending digits. For example with 5 the powers all end in 5 so the pattern, written as short as possible, is simply `5`.

Looking at the minimal power-ending digits patterns for 0 through 9 we get:

```
0 -> 0
1 -> 1
2 -> 2486
3 -> 3971
4 -> 46
5 -> 5
6 -> 6
7 -> 7931
8 -> 8426
9 -> 91

```

(The lengths of these being `11442` repeated is a curious tidbit itself.)

Remember, any numbers above 9 will have the same pattern as their last digit as was explained above with 3.

# Challenge

Your challenge here is to write a program that takes in any non-negative integer and outputs its minimal power-ending digit pattern.

The exact output formatting, whether string or list, doesn't matter. For example, here are some potential inputs followed by valid potential outputs:

```
900 -> [0]
11 -> 1
2 -> 2486
303 -> 3, 9, 7, 1
44 -> 4 6
45 -> 5
666 -> "6"
3857 -> [7 9 3 1]
118 -> '8426'
129 -> [9, 1]

```

**The shortest code in bytes wins.**

# Answer
> 6 votes
# Python 3, ~~44~~ ~~43~~ 40 bytes

Based off of mabel's answer but using dictionary comprehensions:

```
lambda n:[*{n**i%10:0for i in[1,2,3,4]}]

```

Saved 1 byte thanks to mabel.

Saved 3 bytes thanks to xnor.

You can try it online

# Answer
> 5 votes
# Jelly, 6 bytes

```
*Ɱ4%⁵Q

```

A monadic link which accepts an integer and yield a list of integers.

**Try it online!**

### How?

```
*Ɱ4%⁵Q - Link: integer, n
  4    - four
 Ɱ     - map across (implicit range of [1..4]) with:
*      -    exponentiate
    ⁵  - ten
   %   - (powers) mod (ten)
     Q - de-duplicate

```

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

```
n=>[n%=10]+[[,,486,971,6,,,931,426,1][n]]

```

Try it online!

---

# JavaScript (ES6), 42 bytes

A recursive version.

```
n=>(g=k=>(d=(k*n)%10)-n?[k]+g(d):k)(n%=10)

```

Try it online!

# Answer
> 4 votes
# Python 3, 54 bytes

```
lambda n:list(dict.fromkeys(n**i%10for i in(1,2,3,4)))

```

Try it online!

Could have been 38 bytes if `set()` was ordered.

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~10~~ 8 bytes

Jo King suggested a shorter function than what I originally had, `∪10⊤*∘⍳∘4` (a train at 9 bytes) vs my 10-byter dfn, and ngn pointed out a tradfn would be shorter than both altogether

```
∪10⊤⎕*⍳4

```

Try it online!

`⍳4` the vector 1 2 3 4

`⎕*` the input raised to the power of, i.e. `(⍵*1)(⍵*2)(⍵*3)(⍵*4)` (using  to represent the value of the input)

`10⊤` mod 10

unique

# Answer
> 3 votes
# 05AB1E, 7 6 bytes

-1 byte thanks to Kevin Cruijssen

```
4LmT%Ù

```

Try it online!

Just a port of Jonathan Allan's Jelly answer.

# Answer
> 3 votes
# MATL, 7 bytes

```
4:^10\u

```

Try it online!

### Explanation

```
4:    % Push [1 2 3 4]
^     % Implicit input, n. Element-wise power: gives [n n^2 n^3 n^4]
10\   % Modulo 10
u     % Unique (remove duplicates). Implicit display

```

# Answer
> 3 votes
# Haskell, ~~48~~ 46 bytes

`import Data.List;f n=nub[n^i`mod`10|i<-[1..4]]`

-2 bytes thanks to @Laikoni

Having to import `nub` is really annoying... Any suggestions to remove it?

You can Try it online!

# Answer
> 2 votes
# JavaScript (Node.js), 42 bytes

```
n=>new Set([1,2,3,4].map(v=>(n%10)**v%10))

```

Try it online!

# JavaScript (Node.js), 37 bytes

This solution is suggested by @Expired Data, it is shorter, elegant but it will have problems when working with large number.

```
n=>new Set([1,2,3,4].map(v=>n**v%10))

```

Try it online!

# Answer
> 2 votes
# x86-16 machine code, IBM PC DOS, 26 bytes

**Binary:**

```
00000000: b380 8a07 d72c 308a d850 0430 b40e cd10  .....,0..P.0....
00000010: 58f6 e3d4 0a3a c375 f0c3                 X....:.u..

```

**Unassembled:**

```
B3 80       MOV  BL, 80H            ; BX to command line input tail
8A 07       MOV  AL, BYTE PTR[BX]   ; input length into AL
D7          XLAT                    ; AL = [BX+AL] (get the last char of input)
2C 30       SUB  AL, '0'            ; convert from ASCII
8A D8       MOV  BL, AL             ; save N to BL for compare/multiply
        POW_LOOP:
50          PUSH AX                 ; save AX
04 30       ADD  AL, '0'            ; convert to ASCII
B4 0E       MOV  AH, 0EH            ; BIOS tty function
CD 10       INT  10H                ; call BIOS, write char to console
58          POP  AX                 ; restore AX
F6 E3       MUL  BL                 ; AX = AL * BL
D4 0A       AAM                     ; AL = AL % 10
3A C3       CMP  AL, BL             ; is sequence repeating?
75 F0       JNE  POW_LOOP           ; if not, keep looping
C3          RET                     ; return to DOS

```

A standalone PC DOS executable program. Input via command line args.

**I/O:**

# Answer
> 1 votes
# PHP, ~~54~~ 50 bytes

```
for($n=$o=$argn%10;print$n;$n-$o||die)$n=$n*$o%10;

```

Try it online!

---

Alternate Solution:

# PHP, ~~50~~ 45 bytes

```
for(;$i<'11442'[$argn%5];)echo$argn**++$i%10;

```

Try it online!

# Answer
> 1 votes
# x86\_64 machine code, ~~63~~ 61 bytes

```
B8 BF 84 7B 09 B9 0A 00 00 00 31 D2 C7 44 24 FC
A4 10 0A 00 48 C1 E0 22 48 89 44 24 EC 48 B8 3C
00 00 00 00 00 5E 24 48 89 44 24 F4 89 F8 66 F7
F1 48 89 D0 83 E0 0F 66 03 54 44 EC C3

```

Disassembly:

```
00000000  B8BF847B09        mov eax,0x97b84bf
00000005  B90A000000        mov ecx,0xa
0000000A  31D2              xor edx,edx
0000000C  C74424FCA4100A00  mov dword [rsp-0x4],0xa10a4
00000014  48C1E022          shl rax,byte 0x22
00000018  48894424EC        mov [rsp-0x14],rax
0000001D  48B83C0000000000  mov rax,0x245e00000000003c
         -5E24
00000027  48894424F4        mov [rsp-0xc],rax
0000002C  89F8              mov eax,edi
0000002E  66F7F1            div cx
00000031  4889D0            mov rax,rdx
00000034  83E00F            and eax,byte +0xf
00000037  66035444EC        add dx,[rsp+rax*2-0x14]
0000003C  C3                ret

```

Input: `edi`, Output: `dx`, requires `rsp` to be set to a correct value.

Example call:

```
main:
  mov edi, 1337
  call f
  movzx eax, dx
  ret

```

# Answer
> 1 votes
# Retina 0.8.2, ~~58~~ 50 bytes

```
.*(.)
$1$1$*_,,486,971,6,,,931,426,1
+`_\d*,

,.*

```

Try it online! Link includes test cases. Edit: Saved 8 bytes by not including the input digit in the digit patterns. Explanation:

```
.*(.)
$1$1$*_,,486,971,6,,,931,426,1

```

Create a unary copy of the last digit and append the list of power-ending digit pattern suffixes.

```
+`_\d+,

```

Delete the appropriate number of entries from the start of the list.

```
,.*

```

Delete unneeded entries from the end of the list.

Actually calculating the digits takes 69 bytes:

```
M!`.$
{`(.).*
$&;$1$*_,$&$*
_(?=.*,(1*))|,1*
$1
;(1{10})*(1*)
$.2
D`.

```

Try it online! Link includes test cases. Explanation:

```
M!`.$

```

Modulo the input by 10.

```
{`

```

Repeat while new digits can be added.

```
(.).*
$&;$1$*_,$&$*

```

Create unary copies of the first digit and power-ending digits so far.

```
_(?=.*,(1*))|,1*
$1

```

Multiply them together.

```
;(1{10})*(1*)
$.2

```

Take the remainder modulo 10 and convert it to decimal.

```
D`.

```

Deduplicate the digits.

Of course it only takes 34 bytes in Retina 1:

```
L`.$
{`(.).*
$&_$.(*$1*
_.*\B

D`.

```

Try it online! Link includes test cases. Explanation:

```
L`.$

```

Modulo the input by 10.

```
{`

```

Repeat while new digits can be added.

```
(.).*
$&_$.(*$1*

```

Multiply the power-ending pattern so far by its first digit. (`*` has higher precedence than `$^`, so multiplying by its reverse ends up costing a byte more than it saves.)

```
_.*\B

```

Modulo the result by 10.

```
D`.

```

Deduplicate the digits.

# Answer
> 1 votes
# Perl 6, 23 bytes

```
((*X**1..4)X%10).unique

```

Try it online!

Returns the unique values of the input to the power of 1 through 4 modulo 10.

# Answer
> 1 votes
# Excel, 53 bytes

```
=CHOOSE(RIGHT(A1)+1,,1,2486,3971,46,5,6,7931,8426,91)

```

`RIGHT(A1)` defaults to `RIGHT(A1,1)`, making it more efficient than `MOD(A1,10)`

# Answer
> 1 votes
# MathGolf, 6 bytes

```
4╒#♂%▀

```

port of *@JonathanAllan*'s Jelly answer, so make sure to upvote him as well!

Try it online.

**Explanation:**

```
4╒      # Push the list [1,2,3,4]
  #     # Take the (implicit) input-integer to each of this power
   ♂%   # Take modulo-10 for each of these
     ▀  # Uniquify the list
        # (after which the entire stack is output implicitly)

```

# Answer
> 1 votes
# C (gcc), <sup>~~56~~</sup> 51 bytes

Saved 5 bytes thanks to S.S. Anne!!!

```
i;f(n){for(i=n%10;putchar(i+48),i=n*i%10,i-n%10;);}

```

Try it online!

# Answer
> 1 votes
# Ruby, 30 bytes

```
->n{(1..4).map{|g|n**g%10}|[]}

```

Try it online!

# Answer
> 1 votes
# Pyth, 9 bytes

```
{m%^QdTS4

```

Try it online!

# Answer
> 0 votes
# Jelly, 7 bytes

```
4R*@%⁵Q

```

You can try it online. \[It doesn't beat Jonathan's answer nor was it posted first. I just got to this answer by myself and I like posting Jelly answers while I'm learning\]

# Answer
> 0 votes
# Charcoal, 24 bytes

```
⭆⁺0§⪪”←‴Ki⦃k‽” Ｉθ﹪⁺ＩθＩιχ

```

Try it online! Link is to verbose version of code. Uses the repetition between the first and second halves of the table. Explanation:

```
     ”←‴Ki⦃k‽”              Compressed string `  264 648 2`
    ⪪                       Split on literal space
   §           Ｉθ           Cyclically index by the input as a number
 ⁺0                         Prefix a literal `0`
⭆                           Map over characters and join
                 ﹪⁺ＩθＩιχ    Add to the input and reduce modulo 10

```

# Answer
> 0 votes
# C (gcc), 116 bytes

```
x,c,a[4];f(n){n%=10;for(c=0,x=n;c<4;x*=n)a[c++]=x%10;n=*a*10+a[1];n=a[2]*10+a[3]-n?n*100+a[2]*10+a[3]:*a-a[1]?n:*a;}

```

Can almost certainly be golfed more but I haven't figured it out yet.

Try it online!

# Answer
> 0 votes
# , 15 bytes

```
[:~.10|]^1+i.@4

```

Try it online!

# K (Kona), 14 bytes

```
{?(x^1+!4)!10}

```

Try it online!

# Answer
> 0 votes
# Burlesque, 12 bytes

```
ri4ro?^)[~NB

```

Try it online!

```
ri   # Read input to int
4ro  # Range [1,4]
?^   # Raise input to powers [1,4]
)[~  # Take last digit of each
NB   # Remove duplicates

```

# Answer
> 0 votes
# Pip, 12 bytes

```
UQ(a**\,4)%t

```

takes range from 1 to 4, takes powers, mod 10, uniquify.

Try it online!

---
Tags: code-golf, number, arithmetic, integer
---


title: Draw the Hilbert Curve

text:
# Question
Title: Draw the Hilbert Curve
A Hilbert Curve is a type of space-filling curve, and it basically maps a line to a plane. Each point in the line corresponds to just one point in the plane, and each point in the plane corresponds to just one point on the line. Shown are iterations 0 through 4 of the Hilbert Curve:

Iterations 0 up to 4:

The objective of this task: Write code that draws the fourth iteration of the Hilbert Curve, as defined above. Your code should be complete - in other words, if you create a function to draw the Hilbert Curve, your code must call that function. The output can either be displayed directly on the screen, or you can write the output to an image file. The curve may be rotated or flipped, but lines must intersect at right angles and the output cannot be stretched. ASCII art is appreciated but will not be accepted. Shortest code in bytes wins!

# Answer
> 8 votes
# MATL, ~~39~~ 38 bytes

```
O5:"tZjJ*JQ-wJq+t2+&y2j+_v2/]XG25Y01ZG

```

This takes the number of iterations as input. If you want to hard-code it, replace `i` by the number.

The program is a port of the Matlab code by Jonas Lundgren shown here.

The result is shown below. You can also try it at MATL Online! It takes a couple of seconds to produce the output. This compiler is experimental; you may need to refresh the page and press "Run" again if it doesn't initially work.

### Explanation

```
O          % Push 0. This is the initial value of "z" in the original code
5:"        % Do 5 times
  t        %   Duplicate
  Zj       %   Complex conjugate
  J*       %   Multiply by 1j (imaginary unit). This is "w" in the original code
  JQ-      %   Subtract 1+1j
  w        %   Swap: brings copy of "z" to top
  Jq+      %   Add 1-1j
  t        %   Duplicate
  2+       %   Add 2
  &y       %   Duplicate the third element from top
  2j+_     %   Add 2j and negate
  v        %   Concatenate the three matrices vertically
  2/       %   Divide by 2
]          % End
XG         % Plot (in complex plane). The numbers are joined by straight lines
25Y0       % Push string 'square'
1ZG        % Make axis square

```

# Answer
> 7 votes
# MATLAB, ~~264~~ ~~262~~ 161 bytes

This works still very much the same, except that we basically calculate the "derivative" of the hilbert curve, that we then "integrate" via `cumsum`. This reduces the code size by quite a bunch of bytes.

```
function c;plot(cumsum([0,h(1,1+i,4)]));axis equal;end function v=h(f,d,l);v=d*[i*f,1,-i*f];if l;l=l-1;D=i*d*f;w=h(f,d,l);x=h(-f,D,l);v=[x,D,w,d,w,-D,-x];end;end

```

### Old version

This is just a plain recursive approach. I used complex numbers to store vectorial information for simplicity. You can change the curve at the part `h(0,1,1+i,4)`. The first argument `p=0` is the initial position, the second argument `f` is a flag for the orientation (`+1` or `-1`), the third argument `d` is the direction/rotation in which the curve should be drawn and the fourth one `l` is the recursion depth.

```
function c;hold on;h(0,1,1+i,4);axis equal;end function p=h(p,f,d,l);q=@plot;if l;l=l-1;d=i*d*f;p=h(p,-f,d,l);q(p+[0,d]);p=p+d;d=-i*d*f;p=h(p,f,d,l);q(p+[0,d]);p=p+d;p=h(p,f,d,l);d=-i*d*f;q(p+[0,d]);p=p+d;p=h(p,-f,d,l);else;q(p + d*[0,i*f,1+i*f,1]);p=p+d;end;end

```

This is what it looks like in older versions:

This is what it looks like in 2015b:

--\>

# Answer
> 7 votes
## R, 90 bytes

```
n=scan();a=1+1i;b=1-1i;z=0;for(k in 1:n)z=c((w<-1i*Conj(z))-a,z-b,z+a,b-w)/2;plot(z,t="s")

```

Shameless R-port of the the algorithm used in the link posted by @Luis Mendo.

For `n=5` we get:

# Answer
> 4 votes
## JavaScript (ES6), ~~266~~ ... ~~233~~ 232 bytes

A SVG rendering of the Hilbert Curve.

```
document.write('<svg><path fill=none stroke=red d="M8 8'+(f=(i,s='2',d=x=y=8)=>i?f(i-1,s.replace(/./g,c=>[32410401423,,10432423401][+c]||c)):s.replace(/./g,c=>c-4?(d+=c&1&&c-2,''):`L${x+=4-'4840'[d&=3]} ${y+=4-'0484'[d]}`))(5)+'">')
```

*Saved 1 byte thanks to Neil*

# Answer
> 3 votes
# MATLAB/Octave, 202 bytes

I noticed the version @LuisMendo linked ~~is~~ was way shorter than previous "handmade" solution but uses an entirely different approach. I'm posting a golfed version here now as a CW:

This version is based on the Lindenmayer system approach:

```
A=zeros(0,2);B=A;C=A;D=A;n=[0,1];e=[1,0];for k=1:4;a=[B;n;A;e;A;-n;C];b=[A;e;B;n;B;-e;D];c=[D;-e;C;-n;C;e;A];D=[C;-n;D;-e;D;n;B];A=a;B=b;C=c;end;A=[0,0;cumsum(A)];plot(A(:,1),A(:,2));axis off;axis equal

```

# Answer
> 3 votes
# Python 3, ~~177~~ ~~175~~ 171 bytes

A simple implementation of the Lindenmayer system for the Hilbert curve. Golfing suggestions welcome!

**Edit:** -2 bytes thanks to Kade. -3 bytes from restructuring how the Hilbert curve is built. -1 byte with thanks to ETHproductions.

```
from turtle import*;s="a";exec('t=""\nfor c in s:t+=c>"F"and"+-abFF-+baFFba-+FFab+-"[c<"b"::2]or c\ns=t;'*5)
for c in s:
 if"-">c:rt(90)
 elif"F">c:lt(90)
 elif"a">c:fd(9)

```

**Ungolfing**

```
import turtle

hilbert_seq = "a"

for _ in range(5):
    new_seq = ""
    for char in hilbert_seq:
        if char == "a":
            new_seq += "-bF+aFa+Fb-"
        elif char == "b":
            new_seq += "+aF-bFb-Fa+"
        else:
            new_seq += char
    hilbert_seq = new_seq

for char in hilbert_seq:
    if char == "F":
        turtle.forward(9)
    elif char == "+":
        turtle.right(90)
    elif char == "-":
        turtle.left(90)

```

# Answer
> 2 votes
# Mathematica (Wolfram Language) 76 bytes

After Mathematica 11.1, there is a HilbertCurve function, but i don't want to use it

```
Region@Line@ReIm@Nest[Join[w=I Conjugate@#-1-I,t=#+I-1,t+2,-2I-w]/2&,{0},#]&

```

# Answer
> 1 votes
# MSWLogo (Version 6.5b), 136 bytes

Based on the final Hilbert curve program here.

```
to h :n :a :l
if :n=0[stop]
rt :a
h :n-1(-:a):l
fd :l
lt :a
h :n-1 :a :l
fd :l
h :n-1 :a :l
lt :a
fd :l
h :n-1(-:a):l
rt :a
end
h 5 90 9

```

A function `h` is defined, which takes number of iterations `:n` (1-based), angle `:a`, length `:l`. It is recursive, calling a lower iteration of itself with the angle `:a` negated in two instances to get the orientation correct.

* `rt :a`, `lt :a` rotate the turtle (triangle thingy whose path is traced) right, left by `:a` degrees.
* `fd :l` moves the turtle forward by `:l` steps.

Finally, the function is called: `h 5 90 9`. The turtle can be hidden for an extra 2 bytes, `ht`.

# Answer
> 1 votes
## Mathematica 128 Bytes

```
Graphics[Line@AnglePath[Total/@Split[Cases[Nest[#/.{-2->(s=##&@@#&)[l={-1,2,0,1,-2,0,-2,1,0,2,-1}],2->s@-l}&,{-2},4],-1|1|0],#!=0&][[;;-2,;;-2]]*Pi/2]]

```

Replace the 4 above with a different number of iterations if you like.

Done as a Lindenmayer system with integer sequences rather than string sequences so the second production rule is just the negative of the first rule. This version is 151 bytes.

The port of Jonas Lundgren's MATLAB code is only 128 bytes.

```
z=0;Graphics[Line[{Re[#],Im[#]}&/@Flatten[Table[w=I*Conjugate[z];z={w-(a=1+I),z-(b=1-I),z+a,b-w}/2,{k,5}][[5]]]],AspectRatio->1]

```

I see that in a future version of Mathematica, this may become really short, something like:

```
Graphics@HilbertCurve[n]

```

http://mathworld.wolfram.com/HilbertCurve.html

# Answer
> 1 votes
# LindenMASM, 63 Bytes

Another question with a LindenMASM answer? Awesome!

```
STT
AXI A
INC 5
SET F 0
RPL A -BF+AFA+FB-
RPL B +AF-BFB-FA+
END

```

Once again, due to some drawing bugs with Python's `turtle`, sometimes when you run this the whole drawing isn't there. However you can see it does actually work:

---
Tags: code-golf, kolmogorov-complexity, graphical-output, fractal
---


title: Illustrate music beats

text:
# Question
Title: Illustrate music beats
You know—they look like this:

source

The goal is to draw a music beats illustration like the following:

```
=     =      =
=  =  =      =          =
== = ==   =  ==     = ====
== ====  == ===   = = =======
======== == ====  = ========= =
=================================

```

The rules are:

* The width of the illustration is 33 symbols, but if you need—any trailing spaces exceeding this width are allowed.
* Each column is made of equals signs (`=`).
* Each column has a **random height** (the height of the next column shouldn’t depend in any way on the height of the previous column), varying from 1 to 6. It’s also fine if it’s at least *possible* to get some input with no strict math probability (i.e. some inputs could appear more rarely than others).
* A column *can’t* float above the bottom and have gaps in it.
* Since every column has the minimal height of 1, the last row can’t have any gaps either—it always consists of 33 equals signs.
* Since it’s possible to have no columns with the height of 6 (it’s all random after all): in this case you don’t need to have a top line made of spaces. Applies to any edge cases of this nature: if suddenly your code provided no columns with the height greater than 1, you don’t need to have additional lines made of spaces above the bottom line.
* **You don’t take any input**.

# Answer
> 12 votes
# Pyth, 13 bytes

And I outgolfed Jelly.

```
j_.tm*hO6\=33

```

Try it online!

```
j_.tm*hO6\=33
    m      33  for 33 times:
       O6          yield a random number in [0,1,2,3,4,5].
      h            add one.
     *   \=        repeat "=" that number of times.
  .t           transpose, filling with whitespace
 _             reverse
j              join by newlines.

```

# Answer
> 14 votes
# Dyalog APL, 14 bytes

```
⊖⍉↑'='⍴¨⍨?33⍴6

```

### Explanation

`33⍴6` 33 repetitions of 6

`?` random integer in range \[1,*n*\] for each of the 33 6s

`'='⍴¨⍨` equality symbol repeated each of those number of times

convert list of lists to table of rows

transpose rows into columns, columns into rows

flip upside down

### Example runs

Input is indented six spaces:

```
      ⊖⍉↑'='⍴¨⍨?33⍴6
=          ==        =      ==
= =    =   ==      ====     ==
= = = ===  ==  === ==== =  ===  =
= = ===== ==== === ==== = ====  =
=== ============== ==== ====== ==
=================================
      ⊖⍉↑'='⍴¨⍨?33⍴6
         =  =  =    =    =
  =      =  =  ==  == == =  =
 === == ==  =  === =======  =
==== == ==  ====== ==========   =
==== ============= ========== = =
=================================
      ⊖⍉↑'='⍴¨⍨?33⍴6
             =    =   =  =
         =   =    =   = == =
=      = =   =    ==  = ==== ===
= = =  = =   =    ==  = ==== ====
=====  = == ==  ============ ====
=================================

```

# Answer
> 10 votes
# JavaScript (ES6), 116 bytes

```
(a=Array(33).fill``.map(_=>[,,,,,,].fill` `.fill('=',Math.random()*6)))[0].map((x,i)=>a.map(x=>x[i]).join``).join`
`

```

Check it out in the animated snippet below:

```
F = () => (a=Array(33).fill``.map(_=>[,,,,,,].fill` `.fill('=',Math.random()*6)))[0].map((x,i)=>a.map(x=>x[i]).join``).join`
`

var interval;
G = () => output.innerHTML = F().split('\n').map((r, i) => `<span id="row-${6-i}">${r}</span>`).join('\n');
A = () => {
  clearInterval(interval);
  if (auto.checked) {
    speed.disabled = false;
    interval = setInterval(G, speed.value);
  } else {
    speed.disabled = true;
  }
}
S = () => {
  if (stylized.checked) {
    output.classList.add('stylized');
  } else {
    output.classList.remove('stylized');
  }
}

generate.onclick = G;
auto.onchange = speed.onchange = A;
stylized.onchange = S;

G();
A();
S();
```

```
#output {
  background: #000;
  color: #9fff8a;
  overflow: hidden;
  padding: 1em;
  line-height: 1;
}

#output.stylized {
  line-height: 0.25;
  font-size: 2em;
  margin: 0.5em 0 0 0;
  padding: 0.5em;
}

.stylized #row-1 { color: #9fff8a; }
.stylized #row-2 { color: #c5ff8a; }
.stylized #row-3 { color: #e0ff8a; }
.stylized #row-4 { color: #ffe88a; }
.stylized #row-5 { color: #ffc28a; }
.stylized #row-6 { color: #ff8a8a; }
```

```
<button id="generate">Generate</button>
<label>Auto: <input id="auto" type="checkbox" checked/></label>
<label>Speed: <select id="speed">
  <option value="25">25</option>
  <option value="50">50</option>
  <option value="100" selected>100</option>
  <option value="200">200</option>
  <option value="400">400</option>
  <option value="600">600</option>
  <option value="800">800</option>
  <option value="1000">1000</option>
</select></label>
<label>Stylized: <input id="stylized" type="checkbox" checked/></label>
<pre id="output"></pre>
```

# Answer
> 9 votes
# Jelly, 14 bytes

```
6x33X€”=ẋz⁶Ṛj⁷

```

Try it here.

# Answer
> 8 votes
# C, 87 bytes

```
f(x,y){for(y=6;y--;){srand(time(0));for(x=33;x--;)putchar("= "[rand()%6<y]);puts("");}}

```

Call as `f();`. This answer relies on the fact that six consecutive calls to `time(0)` return the same result (in seconds). This is virtually always true, but probably worth mentioning.

# Answer
> 8 votes
## Cheddar, ~~68~~ 65 bytes (non-competing)

```
->(1:33).map(->IO.sprintf("%6s","="*Math.rand(1,7))).turn().vfuse

```

O\_O Cheddar is actually doing good! Uses `sprintf` and `turn` to do a bulk of the work. `vfuse` is vertical-fuse meaning it joins the array but vertically. This is very golfy but also rather fast. Version is prerelease v1.0.0-beta.10, which post-dates the challenge.

## Explanation

```
->           // Anonymous function
  (1:33)     // Range 1-33 inclusive
  .map(->    // Loop through the above range
    IO.sprintf("%6s",       // `sprintf` from C/C++
      "="*Math.rand(1,7)    // Repeat `=` a random time from [1,7)
    )
  ).turn().vfuse     // Turn it 90deg, and fuse it vertically

```

Some example runs:

# Answer
> 6 votes
# 05AB1E, 22 bytes

No auto joining, no automatic filling while transposing, osabie is doomed on this one. Code:

```
33F6ð×6L.R'=×ðñ})ø€J¶ý

```

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

# Answer
> 5 votes
# Python 2, 95 bytes

```
from random import*
x=map(randrange,[6]*33)
for y in range(6):print''.join('= '[z>y]for z in x)

```

# Answer
> 4 votes
# MATL, ~~20~~ ~~19~~ ~~18~~ 17 bytes

*1 byte saved thanks to @Luis*

```
33l2$r6*6:>!~61*c

```

**Try it Online**

# Answer
> 4 votes
# Python 3, 115 bytes

Python never even had a chance...

```
from random import*
for k in zip(*[[' ']*(6-len(j))+j for j in[randint(1,6)*['=']for i in[0]*33]]):print(*k,sep='')

```

**How it works**

```
from random import*    Import everything in the random module
randint(1,6)*['=']     Create a list containing a random number in [1,6] of '='...
...for i in[0]*33      ...33 times...
[...]                  ...and store in a list X
for j in...            For all lists j in X...
[' ']*(6-len(j))+j     ...create a list containing j padded with the correct number of
                       spaces to give a height of 6...
[...]                  ...and store in a list Y

Y now contains a list for each output line, but transposed.

for k in zip(*...):...  For all lists k in the transpose of Y...
print(*k,sep='')        Print all elements in k with no separating space

```

Try it on Ideone

# Answer
> 3 votes
# SpecaBAS - 76 bytes

```
1 FOR x=1 TO 33: r=1+INT(RND*6): FOR y=7-r TO 6: ?AT y,x;"=": NEXT y: NEXT x

```

Prints an equal sign at the relevant screen coordinate.

with a spot of colour and a `GOTO` loop it becomes

# Answer
> 2 votes
# K4, 18 bytes

Essentially a port of the APL solution (unsurprisingly).

```
+-6$(33?1+!6)#'"="

```

# Answer
> 2 votes
# C#, ~~200~~ 117 bytes

```
()=>{var s="";int x,y=6;for(;y-->0;){var r=new Random();for(x=33;x-->0;)s+="= "[r.Next(6)<y?1:0];s+='\n';}return s;};

```

I move to @Lynn algorithm and save 83 bytes!

C# lambda without input and where output is a string. Try it online.

Code:

```
()=>{
    var s="";int x,y=6;
    for(;y-->0;){
        var r=new Random();
        for(x=33;x-->0;)
            s+="= "[r.Next(6)<y?1:0];
        s+='\n';
    }return s;
};

```

# Answer
> 2 votes
## Haskell, 164 Bytes

Being a purely functional language, Haskell was doomed from the start. I did it anyway and it turns out, that the necessary overhead is actually not that large.

```
import System.Random
import Data.List
f r n|r>n=' '|0<1='='
s=do
g<-newStdGen
mapM_ putStrLn$transpose$map(\n->map(f$mod n 6)[0..5])(take 33(randoms g)::[Int])

```

**Usage:**

```
s

```

**Explanation:**

```
import System.Random

```

to be able to use `newStdGen` and `randoms`

```
import Data.List

```

to be able to use `transpose`

```
f r n|r>n=' '|0<1='='

```

defines a function that prints a space if its first argument is larger than the second and a `=` otherwise. It is called with `map (f m) [0..5]` on a given number `m` and the list `[0,1,2,3,4,5]`. (See below)

```
s=do
g<-newStdGen

```

Creates a new standard random number generator

```
(take 33(randoms g)::[Int])

```

takes 33 random integers.

```
map(\n->map(f$mod n 6)[0..5])

```

Calculates `m = n % 6` and maps `(f m)` to the list `[0,1,2,3,4,5]`, which results in one of `"======", " =====", ..., " ="`. These lines are mapped to the list of the 33 random integers resulting in a table. (A table in Haskell is a list of lists)

```
transpose$

```

switches columns and rows of the table

```
mapM_ putStrLn$

```

prints every line in the table

# Answer
> 1 votes
## CJam, 19 bytes

```
{5mrS*6'=e]}33*]zN*

```

Try it online!

### Explanation

```
{       e# 33 times...
  5mr   e#   Push a random number in [0 1 2 3 4 5].
  S*    e#   Create a string with that many spaces.
  6'=e] e#   Pad to length 6 with =.
}33*
]       e# Wrap all 33 strings in a list.
z       e# Transpose that list.
N*      e# Join the lines with linefeeds.

```

# Answer
> 1 votes
# Mathematica, 78 bytes

```
StringRiffle[(PadLeft[Array["="&,#+1],6," "]&/@5~RandomInteger~33),"
",""]&

```

Anonymous function. Takes no input and returns a string as output. The Unicode character is U+F3C7, representing `\[Transpose]`.

# Answer
> 1 votes
# J, 18 bytes

```
|.|:'='#~"0>:?33#6

```

Very simple stuff. With a bugfix from miles!

# Answer
> 1 votes
# PHP, ~~95~~ ~~92~~ 89 bytes

```
<?php for(;++$i<34;)for($j=6,$e=' ';$j--;)$a[$j].=$e=rand(0,$j)?$e:'=';echo join("
",$a);

```

Pretty happy with this one actually. For a while I had a version that in theory could generate any input but in practise would generate only solid blocks of = but this is both shorter and equally distributed!
Generates 7 undefined something notices whenever you run it but that's fine.

edit: well I just learned that join is an alias of implode, so that's nice.

# Answer
> 1 votes
# R, 102 bytes

```
m=rep(" ",33);for(i in 1:6){n=ifelse(m=="=",m,sample(c(" ","="),33,T,c(6-i,i)));m=n;cat(n,"\n",sep="")}

```

### Explanation

`m=rep(" ",33)` init an empty vector for the upcoming loop

`n=ifelse(m=="=",m,sample(c(" ","="),33,T,c(6-i,i)))` If there's an `=` in the row above, then make sure the spot below also has an `=`; otherwise randomly pick. Random picks are weighted to make sure that a) the bottom row is all `=` and b) you get a neat shape to the whole thing.

`cat(n,"\n",sep="")` output that row to the console with a newline at the end and no spaces between elements!

# Answer
> 1 votes
## Perl, 64 bytes

```
@f=$_="="x33;s/=/rand>.4?$&:$"/ge,@f=($_.$/,@f)while@f<6;print@f

```

### Usage

```
perl -e '@f=$_="="x33;s/=/rand>.3?$&:$"/ge,@f=($_.$/,@f)while@f<6;print@f'
  = =           =  ==      =    =
  = =         ===  ==      =    =
= = =         ===  ==      =    =
= = =   = =   ===  ===   = =    =
= = == =====  === ====   ===  = =
=================================

```

---

## Perl, 68 bytes

Alternative version that relies on ANSI escape codes to move the cursor around, first dropping down 6 lines, then writing the original line (all the `=`s), moving up a line and printing the replaced string (`s/=/rand>.4?$&:$"/ge`) repeatedly until it makes no more substitutions. This can end up writing more than six lines, but it is eventually replaced with an empty line.

**Note: `\x1b`s are actually the ASCII `Esc` character.**

```
print"\x1bc\x1b[6B",$_="="x33;print"\x1b[1A\x1b[33D$_"while s/=/rand>.4?$&:$"/ge

```

# Answer
> 1 votes
# Ruby, ~~102~~ ~~99~~ ~~84~~ 83 bytes

```
s='
'*203;33.times{|j|a=(' '*rand(6)).ljust 6,'=';6.times{|i|s[i*34+j]=a[i]}};$><<s

```

New and significantly shorter approach, where I start with string full of newlines.

Older version...

```
s='';204.times do|i|s+=->i{i%34==0?"\n":i>170?'=':s[i-34]=='='?'=':rand(2)==1?'=':' '}[i]end;puts s

```

...gave output with leading new line. My first submission in Ruby, using similar approach to @Barbarossa's one, but in single loop.

What I liked in Ruby while working on this program:

* `.times` loop
* `rand()` which is pretty short
* stacking ternary operators without parentheses

I didn't like (mainly in terms of golfing):

* ~~mandatory `$` for global variables~~ not so mandatory in `.times` loop
* ~~`do` and `end` keywords~~ which can be replaced with single-line block
* `0` is not falsy

# Answer
> 1 votes
# Charcoal, 12 bytes

```
Ｆ³³⁺×=⁺¹‽⁶¶⟲

```

Beats Pyth by 1 byte!

Link is to verbose version of code.

Try it online!

# Answer
> 0 votes
# JavaScript, 179 bytes

Still working on golfing this a bit. I like this since it's straightforward.

```
n=>{a=Array(33).fill(0).map(n=>Math.floor(Math.random()*6)+1);r=Array(6).fill("");r.map((e,m)=>{a.map(n=>{if (n<=m+1){r[m]+="="}else r[m]+=" "})});return r.join('\n');}

```

Usage:

```
>q=n=>{a=Array(33).fill(0).map(n=>{return Math.floor(Math.random() * 6)+1});
r=Array(6).fill("");r.map((e,m)=>{a.map(n=>{if (n<=m+1){r[m]+="="}else r[m]+=" "})});return r.join('\n');}
>q();
           = =  =   =    = =
=   =    = = =  =  == =  = =  =
= = =  = === ====  ====  = = ===
= = =  = === ==========  =======
= === ===========================
=================================

```

# Answer
> 0 votes
# Forth, 190 bytes

I had to create my own PRNG, an xor-shift taken from here. The word `f` is the word you would call multiple times to see the output.

```
variable S utime S !
: L lshift xor ;
: R S @ dup 13 L dup 17 rshift xor dup 5 L dup S ! 6 mod ;
: f
33 0 DO R LOOP
1 -5 DO
33 0 DO
I PICK J + 0< 1+ IF ." =" ELSE SPACE THEN
LOOP CR
LOOP
; f

```

**Try it online** \- Note that the system time is one of two values based on which server (or something) is running the code. Other than that, they don't change in the online IDE for some reason. So you'll only see two possible outputs. You can manually set the seed by changing `utime` to an integer.

### Ungolfed

```
variable seed                   \ seed with time
utime seed !

: RNG                           \ xor-shift PRNG
seed @
dup 13 lshift xor
dup 17 rshift xor
dup 5 lshift xor
dup seed !
6 mod                           \ between 0 and 6, exclusive
;

: f 33 0 DO RNG LOOP            \ push 33 randoms
    1 -5 DO                     \ for (J = -6; J <  0; J++)
        33 0 DO                 \ for (I =  0; I < 33; I++)
            I PICK J + 0< 1+ IF \ if  (stack[I] < J)
                61 EMIT         \ print "="
            ELSE
                32 EMIT         \ print " "
            THEN
        LOOP
        CR                      \ print "\n"
    LOOP
; f

```

**Ungolfed online**

# Answer
> 0 votes
# JavaScript, 165 Bytes

```
// function that fills a column with a specified number of = signs
m=l=>Array(6).fill``.map((e,i)=>i<l?"=":" ");
// fill an array of 33 length with columns of random number of = signs
a=Array(33).fill``.map(e=>m(Math.ceil(Math.random()*6)));
// transponse the rows and columns and print to console
a[0].map((c,i)=>a.map(r=>r[5-i])).map(r=>console.log(r.join``))

```

The newlines are unnecessary but they make it easier to see what's going on. Not the most optimal solution, but it makes sense to me at least.

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


title: Decimal concatenation of squares

text:
# Question
Title: Decimal concatenation of squares
**Premise**

One night, I was just contemplating on numbers. I found out about something unique about numbers like 7, 10, 12, 13, and more. They are squares of squares! Meaning, that when squared, are comprised of squares themselves. The OEIS calls them Squares which are a decimal concatenation of two or more squares.

Examples of such numbers include 7 (49 has 22 and 32) 13 (169 has 42 and 32) and 20 (400 has 22 and 02). Other examples include 37, as 1369 is a term as it can be partitioned as 1, 36 and 9. 1444 (382) is a term as it can be partitioned as 1, 4, 4, 4. I asked about this on Math.SE, and it was named after me!

**Challenge**

Design a program that prints TanMath numbers. Given the number n (starting at 1), print the nth TanMath number, T(n).

As a code example:

```
>> 1
>> 7

```

or

```
>> 4
>> 13

```

Reference Python implementation(thanks @MartinBüttner and @Sp3000!):

```
from math import sqrt

n = input()

def r(digits, depth):
    z = len(digits)
    if z < 1:
        return (depth > 1)
    else:
        for i in range(1, z+1):
            t = int(digits[:i])
            if sqrt(t).is_integer() and r(digits[i:], depth+1):
                return True
        return False

i=0
t=0
while t < n:
    i += 1

    if r(str(i**2), 0):
        t += 1

print i

```

Here is a list of the first 100 numbers:

> 7 10 12 13 19 20 21 30 35 37 38 40 41 44 50 57 60 65 70 80 90 95 97 100 102 105 107 108 110 112 119 120 121 125 129 130 138 140 150 160 170 180 190 191 200 201 204 205 209 210 212 220 223 230 240 250 253 260 270 280 285 290 300 305 306 310 315 320 325 330 340 342 343 345 348 350 360 369 370 375 379 380 390 397 400 402 405 408 410 413 420 430 440 441 450 460 470 475 480 487

This is a code golf, so the shortest code wins!

Good luck!

# Answer
> 7 votes
# Pyth, ~~23~~ ~~21~~ 20 bytes

```
e.ff!-sMT^R2Z./`^Z2Q

```

*Thanks to @isaacg for golfing off 1 byte!*

Try it online.

### How it works

```
                      (implicit) Store the evaluated input in Q.
 .f                Q  Filter; find the first Q positive integers Z such that:
                ^Z2     Compute the square of Z.
               `        Cast to string.
             ./         Compute all partitions of the string.
   f                    Filter; find all partitions T such that:
      sMT                 Cast all elements of T to integer.
         ^R2Z             Compute the squares of all integers in [0, ..., Z-1].
     -                    Remove the squares from the integers in T.
    !                     Compute the logical NOT of the result. This returns True
                          iff all integers in T are squares of numbers less than Z.
                        Keep T if `!' returned True.
                      Keep Z if `!' returned True for at least one T.
e                     Retrieve the last of the Q matches.

```

# Answer
> 5 votes
# Julia, ~~189~~ 145 bytes

```
n->(c=m=0;while c<n m+=1;d=["$(m^2)"...];for p=partitions(d) d==[p...;]&&!any(√map(parse,map(join,p))%1.>0)&&endof(p)>1&&(c+=1;break)end;end;m)

```

This creates an unnamed function that accepts an integer and returns an integer. To call it, give it a name, e.g. `f=n->...`.

Ungolfed:

```
function tanmath(n::Integer)
    # Initialize the number to check (c) and the nth TanMath
    # number (m) both to 0
    c = m = 0

    # While we've generated fewer than n TanMath numbers...
    while c < n
        # Increment the TanMath number
        m += 1

        # Get the digits of m^2 as characters
        d = ["$(m^2)"...]

        # Loop over the unordered partitions of the digits
        for p in partitions(d)
            # Convert the partition of digits to parsed numbers
            x = map(parse, map(join, p))

            # If the partition is in the correct order, none of the
            # square roots of the digits are non-integral, and p is
            # of length > 1...
            if d == [p...;] && !any(sqrt(x) % 1 .> 0) && endof(p) > 1
                # Increment the check
                c += 1

                # Leave the loop
                break
            end
        end
    end

    # Return the nth TanMath number
    return m
end

```

Thanks to Dennis for some help and ideas and thanks to Glen O for saving 44 bytes!

# Answer
> 4 votes
# JavaScript ES6, 126 ~~127~~

The reference implementation, converted to Javascript with some golf trick.

Using eval to avoid explicit return.

Test running the snippet below in an EcmaScript 6 compliant browser, with spread operator, default parameters and arrow functions (I use Firefox)

```
F=n=>eval('for(i=t=0;t<n;t+=k([...i*i+""]))++i',k=(s,l=1,n="")=>s[0]?s.some((d,i)=>Math.sqrt(n+=d)%1?0:k(s.slice(i+1),l-1)):l)

// Less golfed

U=n=>{
  k = (s,l=1,n="") =>
    s[0]
    ? s.some((d,i) =>
             Math.sqrt(n+=d)%1 ? 0 : k(s.slice(i+1),l-1)
            )
    : l;
  for(i=t=0; t<n; ) {
    ++i;
    t += k([...i*i+""])
  }
  return i
}

function test() { R.innerHTML=F(+I.value) }

test()
```

```
<input id=I value=100><button onclick='test()'>-></button>
<span id=R></span>
```

# Answer
> 3 votes
# JavaScript (ES6), 143 bytes

```
f=n=>{for(i=c=0;c<n;c+=1<g(++i*i+""))g=s=>{for(var l=0;s[l++];)if(!(Math.sqrt(s.slice(0,l))%1)&&!s[l]|(r=!!g(s.slice(l))))return 1+r};return i}

```

## Usage

```
f(100)
=> 487

```

## Explanation

```
f=n=>{
  for(
    i=                     // i = current number to check
      c=0;                 // c = number of TanMath numbers found so far
    c<n;                   // keep looping until we have found the required TanMath number
    c+=1<                  // increment the count if it has multiple squares in the digits
      g(++i*i+"")          // check if the current number is a TanMath number
  )
    g=s=>{                 // this function is passed a number as a string and returns the
                           //     number of squares found (max 2) or undefined if 0
      for(var l=0;s[l++];) // loop through each digit
                           // ('var' is necessary because the function is recursive)
        if(
          !(Math.sqrt(     // check if the square root of the digits is a whole number
            s.slice(0,l)   // get the digits to check
          )%1)&&
          !s[l]|           // finish if there are no more digits left to check
          (r=!!            // r = true if number of squares in remaining digits > 0
            g(s.slice(l))  // get number of squares in remaining digits
          )
        )
          return 1+r       // return number of squares found
    };
  return i                 // return the number that the loop finished at
}

```

# Answer
> 2 votes
# Jelly, ~~14~~ 12 bytes

```
²ŒṖḌṖÆ²PƇµ#Ṫ

```

Try it online!

## How it works

```
²ŒṖḌṖÆ²PƇµ#Ṫ - Main link. Takes no arguments
         µ#  - Read n from STDIN and run the following over k = 1, 2, 3, ... until n integers return True:
²            -   Yield k²
 ŒṖ          -   Yield all partitions of k²'s digits
   Ḍ         -   Convert each list of digits back into a number
    Æ²       -   Yield 1 for perfect squares and 0 otherwise
      PƇ     -   Remove all lists with any zeros
                This returns an empty list (falsy) for non-TanMath numbers
                 and a non-empty list (truthy) for TanMath numbers
           Ṫ - Return the last element i.e. the nth number for which the above is true

```

# Answer
> 2 votes
# Raku, 44 bytes

```
{grep({$^a²~~/^<{(^$a)>>²}>+$/},1..*)[$_]}

```

Try it online!

The runtime of this inflates fast, due to bruteforcing the combination of powers in the regex. If this were a instead, then the submission could just be that central codeblock instead.

# Answer
> 0 votes
# Lua, 148 bytes

```
c=...r=load"a=a or...==''for p=0,...and n-1or-1 do p='^'..p*p..'(.*)'r(p.match(...,p))end"n=-1repeat
n=n+1r(n*n)c,a=c-(a and 1or 0)until c<1print(n)

```

Lua 5.3 is required

```
$ lua program.lua 1
7
$ lua program.lua 10
37
$ lua program.lua 100
487

```

# Answer
> 0 votes
# Python 3, ~~283~~ 243 bytes

This is a brute-force implementation. Golfing suggestions welcome.

```
from itertools import*
def t(n):
 a=m=0
 while a<n:m+=1;d=str(m*m);r=range(1,len(d));c=[i*i for i in range(m)];a+=any(all(p in c for p in q)for q in[[int(d[x:y])for x,y in zip((0,)+j,j+(None,))]for i in r for j in combinations(r,i)])
 return m

```

**Ungolfed:**

```
import itertools
def tanmath(n):
    a = 0
    m = 0
    while a < n:
        m += 1
        d = str(m*m)
        squares = [i*i for i in range(m)]
        z = []
        # partitions code
        for i in range(1, len(d)):
            for j in itertools.combinations(range(1, len(d)), i):
                partition_indices = zip((0,)+j, j+(None,))
                z.append([int(d[x:y]) for x, y in partition_indices]
        # end partitions code
        if any(all(p in squares for p in q) for q in z):
            a += 1
    return m

```

---
Tags: code-golf, number, sequence, number-theory, set-partitions
---


title: Highly composite numbers

text:
# Question
Title: Highly composite numbers
A highly composite number is a positive integer that has more divisors than any smaller positive integer has. This is OEIS sequence A002182. Its first 20 terms are

```
1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, 720, 840, 1260, 1680, 2520, 5040, 7560

```

For example, `4` is in the sequence because it has 3 divisors (namely 1, 2, 4), whereas 3 only has 2 divisors, 2 also has 2 divisors, and 1 has 1 divisors.

### Challenge

Given a positive integer input *n*, output either the *n*-th highly composite number or the first *n* highly composite numbers, at your choice (but the choice must be the same for every input *n*).

### Rules

The program or function should theoretically work for arbitrarily large inputs given infinite time and memory, and without considering data type limitations. Essentially, this means no hardcoding a finite number of values.

In practice, the program or function should run in a reasonable amount of time, say less than 1 minute, for *n* up to 20. Maximum input or output may be limited by your language standard data type (but again, the algorithm should theoretically work for arbitrarily large numbers).

Any reasonable input and output format is allowed, including unary.

Code golf. Fewest bytes wins.

# Answer
# 05AB1E, ~~15~~ 14 bytes

The input in zero-indexed. That means that `n = 0` gives `1`, `n = 1` gives `2`, etc. Code:

```
$µ>DÑgD®›i©¼}\

```

Explanation:

```
$               # Pushes 1 and input
 µ              # Counting loop, executes until the counting variable is equal to input
  >             # Increment (n + 1)
   DÑ           # Duplicate and calculate all divisors
     gD         # Get the length of the array and duplicate
       ®        # Retrieve element, standardized to zero
        ›i  }   # If greater than, do...
          ©     #   Copy value into the register
           ¼    #   Increment on the counting variable
             \  # Pop the last element in the stack

```

Calculates *n = 19*, which should give `7560` in about 10 seconds.

Try it online!

Uses **CP-1252** encoding.
> 4 votes

# Answer
# Jelly, 15 bytes

```
,®ÆDL€ṛ©0>/?µƓ#

```

For input **n**, this prints the first **n** highly composite numbers.

For **n = 20**, it takes less than two seconds on Try it online!

### How it works

```
,®ÆDL€ṛ©0>/?µƓ#  Main link. No implicit input.

            µ    Push the chain to the left on the local link stack.
             Ɠ   Read an integer n from STDIN.
              #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
                 value n times. Return the list of matches.

,®               Pair k with the value in the register (initially 0).
  ÆD             Compute the divisors of k and the register value.
    L€           Count both lists of divisors.
           ?     If
         >/        k has more divisors than the register value:
      ṛ©             Save k in the register and return k.
        0          Else: Return 0.

```

## Alternate version, 13 bytes (non-competing)

While the below code worked in the latest version of Jelly that precedes this challenge, the implementation of `M` was very slow, and it did not comply with the time limit. This has been fixed.

```
ÆDL®;©MḢ’>µƓ#

```

Try it online!

### How it works

```
ÆDL®;©MḢ’>µƓ#  Main link. No implicit input.

          µ    Push the chain to the left on the local link stack.
           Ɠ   Read an integer n from STDIN.
            #  Execute the chain for k = 0, 1, 2, ..., until it returned a truthy
               value n times. Return the list of matches.

ÆD             Compute the divisors of k.
  L            Count them.
   ®;          Append the count to the list in the register (initially 0 / [0]).
     ©         Save the updated list in the register.
      M        Obtain all indices the correspond to maximal elements.
       Ḣ       Retrieve the first result.
        ’>     Subtract 1 and compare with k.
               This essentially checks if the first maximal index is k + 2, where
               the "plus 2" accounts for two leading zeroes (initial value of the
               register and result for k = 0).

```
> 5 votes

# Answer
# MATL, ~~26~~ 24 bytes

```
~XKx`K@@:\~s<?@5MXKx]NG<

```

**Try it online!**

The current largest number of divisors found is kept in clipboard K. Highly composite numbers (HCN) are kept directly on the stack. A loop keeps testing candidates to HCN. When one is found it is left on the stack, and clipboard K is updated. The loop exits when the desired number of HCN have been found.

```
~         % take input implicitly (gets stored in clipboard G). Transform into a 0
          % by means of logical negation
XKx       % copy that 0 into clipboard K, and delete
`         % do...while
  K       %   push largest number of divisors found up to now
  @       %   push iteration index, i: current candidate to HCN
  @:      %   range [1,...,i]
  \       %   modulo operation
  ~s      %   number of zeros. This is the number of divisors of current candidate
  <       %   is it larger than previous largest number of divisors?
  ?       %   if so: a new HCN has been found
    @     %     push that number
    5M    %     push the number of divisors that was found
    XKx   %     update clipboard K, and delete
  ]       %   end if
  N       %   number of elements in stack
  G<      %   is it less than input? This the loop condition: exit when false
          % end do...while implicitly
          % display all numbers implicitly

```
> 3 votes

# Answer
## Perl, ~~60~~ 57 + 1 = 58 bytes

```
$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,

```

Requires `-n` and the free `-M5.010`|`-E`:

```
$ perl -nE'$,++;$==grep$,%$_<1,1..$,;$_--,$m=$=if$=>$m;$_?redo:say$,' <<< 10
120

```

How it works:

```
$,++;
     $==grep$,%$_<1,1..$,;                                # Calculate total numbers of divisors for `$,`
                          $_--,$m=$=if$=>$m;              # Set `$m`ax divisors to `$=`ivisors if `$m>$=`
                                            $_?redo:say$, # Repeat or print

```
> 3 votes

# Answer
# Pyth, ~~17~~ 16 bytes

*1 byte thanks to Jakube*

```
uf<Fml{yPd,GTGQ1

```

Test suite

Takes a 0-indexed **n**, and returns the **nth** highly composite number.

Explanation:

```
uf<Fml{yPd,GThGQ1
                     Input: Q = eval(input())
u              Q1    Apply the following function Q times, starting with 1.
                     Then output the result. lambda G.
 f           hG      Count up from G+1 until the following is truthy, lambda T.
          ,GT        Start with [G, T] (current highly comp., next number).
    m                Map over those two, lambda d.
        Pd           Take the prime factorization of d, with multiplicity.
       y             Take all subsets of those primes.
      {              Deduplicate. At this point, we have a list of lists of primes.
                     Each list is the prime factorization of a different factor.
     l               Take the length, the number of factors.
  <F                 Check whether the number of factors of the previous highly
                     composite number is smaller than that of the current number.

```
> 2 votes

# Answer
# JavaScript (ES6) 72

Straightforward implementation. Time near 20 sec for input 20

```
x=>{for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;return n}

```

The eval trick could save a byte doubling the run time

```
x=>eval("for(i=e=n=0;i<x;d>e&&(++i,e=d))for(d=1,j=++n;--j;)n%j||++d;n")

```

**Less golfed**

```
x=>{
  for(i = e = 0, n = 1; i < x; n++)
  {
    for(d = 1, j = n; --j; )
    {
      if (n%j == 0)
        ++d;
    }
    if (d > e)
      ++i,
      e = d;
  }
  return n;
}

```
> 2 votes

# Answer
# Jelly, 10 bytes

```
1Æd€<Ṫ$PƊ#

```

Try it online!

Returns the first \\$n\\$ highly composite numbers.

My guess is that this uses features unavailable when Dennis first posted a Jelly answer, but this uses a sufficiently different algorithm that I thought it was ok to post as a separate answer

## How it works

```
1Æd€<Ṫ$PƊ# - Main link. Takes no arguments
1       Ɗ# - Read an integer n from STDIN and run the following over k = 1, 2, 3, ... until n return true:
   €       -   Generate the range [1, 2, ..., k] and do the following over each:
 Æd        -     Calculate the divisor count of each, yielding [σ₀(1), σ₀(2), ..., σ₀(k)]
      $    -   Group the previous two commands together:
     Ṫ     -     Remove σ₀(k) from the list and return it
    <      -     Generate [σ₀(1)<σ₀(k), σ₀(2)<σ₀(k), ..., σ₀(k-1)<σ₀(k)]
       P   -   Are all values true?

```
> 2 votes

# Answer
# Ruby, ~~70~~ ~~69~~ ~~67~~ ~~66~~ ~~64~~ 62

```
->n{r=k=0
0until(r<t=(1..k+=1).count{|d|k%d<1})&&1>n-=t/r=t
k}

```

Straightforward implementation.
> 1 votes

# Answer
# C, 98 bytes

```
f,i,n,j;main(m){for(scanf("%d",&n);n--;printf("%d ",i))for(m=f;f<=m;)for(j=++i,f=0;j;)i%j--||f++;}

```

Try it here.

## Ungolfed

```
f,i,n,j;

main(m)
{
    for(scanf("%d",&n); /* Get input */
            n--; /* Loop while still HCN's to calculate... */
            printf("%d ",i)) /* Print out the last calculated HCN */
        for(m=f;f<=m;) /* Loop until an HCN is found... */
            for(j=++i,f=0;j;) /* Count the number of factors */
                i%j--||f++;
}

```
> 1 votes

# Answer
# Python 3, 97 bytes

```
i=p=q=0;n=int(input())
while q<n:
 c=j=0;i+=1
 while j<i:j+=1;c+=i%j==0
 if c>p:p=c;q+=1
print(i)

```

A full program that takes input from STDIN and prints the output to STDOUT. This returns the `n`th 1-indexed highly composite number.

**How it works**

This is a straightforward implementation. The input `n` is the highly composite number index.

The program iterates over the integers `i`. For each integer `j` less than `i`, `i mod j` is taken; if this is `0`, `j` must be a factor of `i` and the counter `c` is incremented, giving the number of divisors of `i` after looping. `p` is the previous highest number of divisors, so if `c > p`, a new highly composite number has been found and the counter `q` is incremented. Once `q = n`, `i` must be the `n`th highly composite number, and this is printed.

Try it on Ideone

(This takes ~15 seconds for `n = 20`, which exceeds the time limit for Ideone. Hence, the example given is for `n = 18`.)
> 1 votes

# Answer
# Python 2, 207 bytes

```
n,i,r,o=input(),1,[],[]
while len(o)<n:
 r+=[(lambda n:len(set(reduce(list.__add__,([i,n//i]for i in range(1,int(n**0.5)+1)if n%i==0)))))(i)];h=max(r)
 if r.index(h)>i-2 and r.count(h)<2:o+=[i]
 i+=1
print o

```

Uses the same method as Dennis' Jelly answer. Calculates the first 20 terms in `<2` seconds.
> 0 votes

---
Tags: code-golf, number, sequence, arithmetic, number-theory
---


title: Connect the Three Kingdoms

text:
# Question
Title: Connect the Three Kingdoms
You are a medieval overlord tasked with designing a road network between three kingdoms placed on a \\$9 \times 9\\$ grid. A sample placement of kingdoms might look like this:

Non-commercial use of tileset by douteigami. Thanks!

The kingdoms make the following three demands:

1. The *road network must be connected*: for any tile on the road network, you must be able to reach any other tile on the road network by just moving horizontally or vertically only along road tiles.
2. The *kingdoms must be connected*: Every kingdom has at least one road tile immediately adjacent horizontally or vertically.
3. The *road network must be thin*: No block of \\$2\times2\\$ squares can all be road tiles.

Both of the following road networks satisfy all three criteria:

The following setups fail to satisfy one of the three criteria:

## Challenge

Take input of a \\$9\times9\\$ grid with three kingdoms in any format. This may be a multiline string with spaces and characters, a list of single-line strings, a list of zeros and ones, a matrix, or any other reasonable format for your language.

As output, add a road network to the input (indicated in any suitable way) that satisfies the above three criteria. Note that:

* The kingdoms will never be horizontally or vertically adjacent.
* There is no requirement that your road network be minimal in any sense, just that it follows the three rules.
* You may not place roads on top of kingdoms.
* A \\$2\times2\\$ block where three tiles are road and a single tile is a kingdom is OK; the third restriction only concerns four road tiles.

## Test Cases

The test cases use `.` for an empty space, `k` for a kingdom and `#` for a road, but you may take inputs in other formats/use any three distinct characters or integers as described in the previous section.

```
Input     -> Possible output

.........    .........
....k....    ....k....
.........    ....#....
.........    ....#....
.k....... -> .k####...
.........    .....#...
.....k...    .....k...
.........    .........
.........    .........

k.k......    k#k......
.........    .#.......
k........    k#.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.k.......    .k.......
k........    k#.......
.k.......    .k.......
.........    .........
......... -> .........
.........    .........
.........    .........
.........    .........
.........    .........

.........    .........
.........    .........
k........    k#.......
.........    .#.......
k........ -> k#.......
.........    .#.......
k........    k#.......
.........    .........
.........    .........

........k    ...#####k
....k....    ...#k....
.........    ...#.....
.........    ...#.....
......... -> ...#.....
.........    ####.....
.........    ...#.....
....k....    ...#k....
.........    ...#.....

.........    .........
.........    .........
.........    .........
.........    .........
......... -> .........
.........    .........
k........    k........
.k.......    #k.......
..k......    ##k......

```

Here's the inputs as a list of list of lists, should you prefer that:

```
[[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 1, 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, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 1, 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, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [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, 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, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 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], [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], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [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, 1], [0, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 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, 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, 0, 0, 0, 0, 0, 0, 0], [0, 1, 0, 0, 0, 0, 0, 0, 0], [0, 0, 1, 0, 0, 0, 0, 0, 0]]]

```

## Scoring

Shortest code in bytes wins.

# Answer
> 12 votes
# JavaScript (ES7),  ~~166 153 149~~  137 bytes

Slower and even less subtle than my first answer, but also shorter. This simply looks for a path touching all kingdoms without generating any \\$2\times 2\\$ road blocks.

Takes input as a flat list of 81 entries, with \\$0\\$ for an empty cell and \\$2\\$ for a kingdom. Returns another list with \\$0\\$ for an empty cell, \\$1\\$ for a road and \\$3\\$ for a kingdom.

```
f=(a,X)=>+(z=/.*1,1.{15}1,1|2/.exec(a))?a.some((v,x)=>(a[x]++,(d=(x-X)**2)-1|x/9^X/9&&d-81?0:v?1/X&&v==2?f(a,X):0:f(a,x))||!a[x]--)&&a:!z

```

Try it online!

### How?

We use the regular expression `/.*1,1.{15}1,1|2/` to detect either a \\$2\times 2\\$ block of roads or a remaining kingdom. We get `null` if nothing is matched, a string that is coerced to *NaN* by the unary `+` if a block is matched, or a string that is coerced to \\$2\\$ if a kingdom is matched.

Because the left and right boundaries are ignored, the condition on the road block is a little more restrictive than it really should, as it will also match something like that:

```
.........
........X
X.......X
X........
.........

```

However, we have plenty of room to find a path that will work even without including that kind of pattern.

---

# JavaScript (ES7),  ~~243 236~~  226 bytes

*I'm not very happy with this method, as it heavily relies on a brute-force search. There must exist more elegant and more straightforwards ways of solving this. But it does work!*

Expects a matrix with \\$0\\$ for an empty cell and \\$3\\$ for a kingdom. Returns another matrix with \\$0\\$ for an empty cell, \\$2\\$ for a kingdom and \\$4\\$ for a road.

```
f=(m,k)=>(M=m.map((r,y)=>r.map((v,x)=>x^k%8&&x^k%8+2+k/8%8&&y^(q=k/64&7)&&y^q+2+k/512?v:v?3:(X=x,Y=y,1))),g=(X,Y)=>M.map((r,y)=>r.map((v,x)=>(x-X)**2+(y-Y)**2-1?0:v-1?v-3?0:r[x]=2:g(x,y,r[x]=4))))(X,Y)|/1|3/.test(M)?f(m,-~k):M

```

Try it online!

### How?

All puzzles can be solved1 by putting at most 2 horizontal roads and at most 2 vertical roads across the entire grid, either next to or 'over' the kingdoms.

1: this was empirically verified

*Example:*

Given \\$k\ge 0\\$, we compute:

$$x\_0=k\bmod 8$$ $$x\_1=x\_0+2+(\lfloor k/8\rfloor \bmod 8)$$ $$y\_0=\lfloor k/64\rfloor \bmod 8$$ $$y\_1=y\_0+2+\lfloor k/512\rfloor$$

We put vertical roads at \\$x\_0\\$ and \\$x\_1\\$ and horizontal roads at \\$y\_0\\$ and \\$y\_1\\$. If any value is greater than \\$8\\$, it's simply ignored.

Because \\$x\_1\ge x\_0+2\\$ and \\$y\_1\ge y\_0+2\\$, we will never end up we a \\$2\times 2\\$ block of roads.

Starting from a road cell, we flood-fill the grid to make sure that the two other criteria are fulfilled.

# Answer
> 8 votes
# Perl 5, ~~251~~ ~~317~~ ~~298~~ 258 bytes

```
sub f{eval'forP(0..80){forT(0,1){my@r;forK(@_){X=intP/9;Y=P%9;I=intK/9;J=K%9;push@r,X*9+Y andT&&Y-J?Y-=Y<=>J:X-I?X-=X<=>I:Y-J?Y-=Y<=>J:0 whileX.Y neI.J}D="."x81;substrD,$_,1,1for@_;substrD,$_,1,0for@r;3==D=~y/1/1/&&D!~/00.{7}00/&&returnD}}'=~s/[A-Z]/\$$&/gr}

```

Try it online!

Somewhat ungolfed:

```
sub f {
  for$p(0..80){              #loop through all possible starting points p,
                             #... the crossroads in the 9x9 board
                             #... from which each road to each kingdom starts
   for$t(0,1){               #for each starting point, try two strategies
                             #...of movement: vertical first or horizontal first
    my @r;                   #init list of road tiles to empty
    for(@_){                 #loop through all the three kingdoms from input
      $x=int$p/9; $y=$p%9;   #x,y = start roads at current starting point p
      $X=int$_/9; $Y=$_%9;   #X,Y = current kingdom

      push @r, $x*9+$y       #register road tile while x,y not yet reached X,Y
      and                          # move x,y towards X,Y
      $t && $y-$Y ? $y-=$y<=>$Y :
            $x-$X ? $x-=$x<=>$X :
            $y-$Y ? $y-=$y<=>$Y :0 # move horizontally or vertically first
                                   # ...depending on current strategy t=0 or 1
        while $x.$y ne $X.$Y   # continue towards current kingdom unless there
    }
    $d='.'x81;                 # init current board string of 81 dots
    substr $d,$_,1,1 for @_;   # put 1's at kingdoms
    substr $d,$_,1,0 for @r;   # put 0's at road tiles
    3==$d=~s/1/1/g             # if board has 3 kingdoms (none overrun by road)
      && $d!~/00.{7}00/        # and current board has no 2x2 road tiles
      && return $d             # then the board is valid and is returned
                               # otherwise try the next of the 81 starting points
  }
 }
}

```

Can run like this:

```
@test=( [[1,4], [4,1], [6,5]],
        [[0,0], [0,2], [2,0]],
        [[0,1], [1,0], [2,1]],
        [[2,0], [4,0], [6,0]],
        [[0,8], [1,4], [7,4]],
        [[6,0], [7,1], [8,2]] );
for(@test){
    my @kingdom = map $$_[0]*9+$$_[1], @$_;
    print display( f(@kingdom) );
}
sub display{join('',map join(' ',split//)."\n",pop=~y/10/k#/r=~/.{9}/g).('-'x17)."\n"}

```

First lines of output: (see '*Try it online*' link above for more)

```
# . . . . . . . .
# # # # k . . . .
# . . . . . . . .
# . . . . . . . .
# k . . . . . . .
# . . . . . . . .
# # # # # k . . .
. . . . . . . . .
. . . . . . . . .

```

# Answer
> 7 votes
# Brachylog, 97 93 bytes

This actually is fast – brute force in Brachylog! You can't believe how surprised I was when I kept upping the board size. However, this assumes that a road doesn't need to fork. If anyone finds a counterexample – be warned, the other version will not run in time on TIO! :-)

Takes castles as 2, and returns roads as 1.

```
∧ċ{Ċℕᵐ≤ᵛ⁹}ᵐ{s₂{;.\-ᵐȧᵐ+1∧}ᵈ}ᵇP{,1↻₁}ᵐX&{iiʰgᵗc}ᶠT{ṗʰb}ˢ{,.≠&↰₃ᵐ∈ᵛ}P∧T,X≜bᵍtᵐhᵐḍ₉.¬{s₂\s₂c=₁}∧

```

Try it online! or Try all testcases!

### How the original version works

Many bytes got lost for getting the output into a matrix form, as I didn't find a neat way to go from list of coordinates to its matrix representation. The rough story is:

```
ċ{l₂ℕᵐ≤ᵛ⁹}ᵐ

```

We are looking for a path: a list of coordinates, each 0 ≤ X ≤ 9.

```
s₂ᵇ{\-ᵐȧᵐ+}ᵛ¹hᵐ

```

And every pair of consecutive coordinates has a distance of 1.

```
P{,1↻₁}ᵐX

```

We'll store the path as `P`, and a version with a 1 before every coordinate as `X`.

```
&{iiʰgᵗc}ᶠT

```

Transform the matrix to a list of `[Type, Y, X]` and store it as `T`.

```
{ṗʰb}ˢ

```

However, we are only interested in cities for now, so the `Type` must be prime (that's why they are marked with 2).

```
C,P≠

```

The city and path coordinates must all be different to each other.

```
∧C{;.↰₂1∧}ᵐ∈ᵛP≜

```

Every city coordinate, shifted by a distance of 1, must be in the path.

```
∧T,Xbᵍtᵐhᵐḍ₉

```

To the tiles `T` append `X` (the path with `Type = 1` prepended), group the tiles by their coordinates and take the last one – so roads will overwrite empty tiles. Reduce the list to the `Type` and split it into a 9x9 matrix.

```
.¬{s₂\\s₂c=₁}∧

```

This is already the output, but make sure there is no 2x2 submatrix of roads.

# Answer
> 6 votes
# , ~~248~~ ~~257~~ ~~251~~ ~~264~~ ~~250~~ 245 bytes

*Edit: +9 bytes to fix corner-case (literally; see #1 below), then some golfing, then +13 bytes to fix another corner-case (#2, below), then some more golfing...*

```
function(g,s=setdiff,S=0:8%/%3-1,`^`=`%in%`){k=which(g>0,T);v=k[,1];w=k[,2]
g[r<-max(s(v+S,v)%%9),]=g[,c<-max(s(w+S,w)%%9)]=1
for(i in 1:3){x=v[i];y=w[i]
if(!(x^(r+S)|y^(c+S)))`if`(F|x^v[-i],g[x:r,y--y^w[-i]**(y<2)]<-1,g[x,y:c]<-F<-1)}
g[k]=2;g}

```

Try it online!

This is a 'constructive' rather than 'brute-force' solution: we build a single set of roads in such a way that the conditions will be satisfied, rather than trying-out various possibilities and checking whether-or-not we've violated one or more of the conditions.

Input is a matrix with non-zero elements representing the three kingdoms. Output is a matrix with roads represented by 1, and the kingdoms by 2.

**How?**

First we construct 'main' roads in the form of a '+' from north-to-south and from east-to-west across empty elements of the grid, and touching at least one of the 3 kingdoms (*take care: corner-case 2 was when all kingdoms are in edge rows/columns, so we need to make sure that our 'adjacent' roads are still in the grid*).
Now there at most 2 kingdoms left that still need to be connected.
For each kingdom that isn't already connected to the 'main' roads, we construct an 'access road' from the kingdom to one of the 'main' roads.
We need to be careful that the 'access road' won't be split by one of the kingdoms: therefore, we check whether the unconnected kingdom is on the same row as another kingdom, and, if it isn't, we construct an east-west access road. If the unconnected kingdom shares its row with another kingdom, we check if it also shares its column: if not, we build a north-south access road. If it does (and it also shared a row), then we can be sure that the adjacent columns are empty, so we build a north-south access road in a column adjacent to the kingdom (*corner case 1: for this, we need to check if the kingdom is in column 1: if it is, we build the access road in column 2, otherwise in column y-1*).

Here are the roads (orange) built for each of the 6 test cases (kingdoms indicated in whiteish):

**Commented code:**

```
function(g,                     # g=input grid with kingdoms
 s=setdiff,                     # s=alias to 'setdiff()' function
 S=0:8%/%3-1,                   # S=defines adjacent indices
 `^`=`%in%`){                   # ^=alias to '%in%' function
 k=which(g>0,T)                 # k=get indices of the kingdoms
 v=k[,1];w=k[,2]                # v=x-coordinates, w=y-coordinates of kingdoms
 r<-max(s(v+S,v)%%9)            # r=empty row next-to a kingdom
                                # (elements of v±1 that are different to v, avoiding zero and >8)
 c<-max(s(w+S,w)%%9)            # c=first empty column next-to a kingdom
 g[r,]=g[,c]=1                  # build the 'main' roads
 for(i in 1:3){                 # loop through each of the 3 kingdoms:
  x=v[i];y=w[i]                 #  (x,y=x- and y-coordinates of current kingdom)
  if(!(xin%(r+S)|y%in%(c+S)))   #  if x or y are not adjacent to r or s
                                #  (so this kingdom isn't connected to the 'main' roads)
   `if`(F|x%in%v[-i],           #  if x is shared with the row of another kingdom, or
                                #  'F' indicates that we've already built an east-west 'access road':
    g[x:r,y                     #   build an north-south 'access road' from x to r
    -                           #   (either on the same row, y, or on an adjacent row
    (-(y%in%w[-i]))**(y<2)<-1,  #   if y is shared with the col of another kingdom);
    g[x,y:c]<-F<-1)             #  otherwise build an east-west 'access road' from y to c
  }
 g[k]=2;                        # mark the kingdoms on the grid
 g                              # and return the grid
}

```

# Answer
> 4 votes
# Charcoal, 196 bytes

```
≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧ＦυＦ⁴Ｆ⁴«θＪ§ι¹§ι⁰Ｍ✳⊗λ≔⁰ζＷ⁼ＫＫ.«✳⊗κ#≦⊕ζ»≔ωηＦ⁻υ⟦ι⟧Ｆ⁴Ｆ⁴«Ｊ§μ¹§μ⁰Ｍ✳⊗ξ≔ＫＤ⁹✳⊗νδＭ⌕δ#✳⊗ν¿∧№δ#¬№…δ⌕δ#¦k¿⁼⌕υμ¬⌕υι≔⟦μⅈⅉν⌕δ#ξ⟧η¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε»⎚»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι

```

Try it online! Link is to verbose version of code. Works by drawing a line from a square adjacent to one kingdom to the edge of the grid, then drawing lines from squares adjacent to each of the other kingdoms to intersect the first line, except not allowing the two lines to be exactly one row apart. Explanation:

```
≔Ｅ⁹Ｓθ

```

Input the grid.

```
Ｆ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧

```

Locate all of the kingdoms.

```
ＦυＦ⁴Ｆ⁴«

```

Loop through each direction from each square adjacent to each kingdom.

```
θ

```

Print the grid.

```
Ｊ§ι¹§ι⁰Ｍ✳⊗λ

```

Jump to the selected kingdom and move to the selected adjacent square.

```
≔⁰ζ

```

Count the number of empty squares.

```
Ｗ⁼ＫＫ.«

```

Repeat while the current square is empty...

```
✳⊗κ#

```

... mark it with a `#`...

```
≦⊕ζ

```

... and increment the count.

```
»≔ωη

```

Start with no line for the second kingdom.

```
Ｆ⁻υ⟦ι⟧

```

Loop through the remaining kingdoms.

```
Ｆ⁴Ｆ⁴«

```

Loop through each direction from each square adjacent to this kingdom.

```
Ｊ§μ¹§μ⁰Ｍ✳⊗ξ

```

Jump to this kingdom and move to the selected adjacent square.

```
≔ＫＤ⁹✳⊗νδ

```

Grab the line in the selected direction.

```
Ｍ⌕δ#✳⊗ν

```

Move to where the line would intersect if it was valid.

```
¿∧№δ#¬№…δ⌕δ#¦k

```

Does this line cross the first kingdom's line? If so:

```
¿⁼⌕υμ¬⌕υι

```

If this is the second kingdom's line...

```
≔⟦μⅈⅉν⌕δ#ξ⟧η

```

... then save this as its line.

```
¿∧η⊖ΣＥ⟦ⅈⅉ⟧↔⁻π§η⊕ρ

```

Otherwise if the second kingdom's line does not intersect exactly one square away...

```
≔⟦⟦ικζλ⟧η⟦μν⌕δ#ξ⟧⟧ε

```

... then save this as a solution.

```
»⎚

```

Clear the canvas ready for the first kingdom's next adjacent square or the final output.

```
»θ

```

Print the grid.

```
Ｆε«

```

Loop over the kingdoms in the last solution found.

```
Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι

```

Jump to the position of the kingdom and move to the found adjacent square.

```
✳⊗⊟ι×#⊟ι

```

Print the found line.

Note that this code tries all combinations of kingdoms and directions. It's probably unnecessary to try them all, for instance I think it's likely that you can always draw a line up from one of three sides of the bottommost kingdom and connecting the other two kingdoms to that line. If this is true then the code can be simplified, currently saving ~~10~~ 24 bytes: Try it online! Link is to verbose version of code. Explanation:

```
≔Ｅ⁹ＳθＦ⁹Ｆ⌕Ａ§θιk⊞υ⟦ικ⟧

```

Input the grid and locate all of the kingdoms.

```
≔⊟υτ

```

Get the bottommost kingdom.

```
Ｆ³«

```

Check the squares to its right, above and left.

```
θＪ§τ¹§τ⁰Ｍ✳⊗ι

```

Print the grid and jump to the selected adjacent square.

```
≔⁰ζＷ⁼ＫＫ.«↑#≦⊕ζ»

```

Draw a line up as far as possible.

```
≔ωη

```

Start with no line for the second kingdom.

```
ＦυＦ⁴Ｆ⁴«

```

Loop over the other two kingdoms, considering all lines for all four adjacent squares. (I could just do left and right lines but it turns out that all lines is golfier.)

```
Ｊ§κ¹§κ⁰Ｍ✳⊗μ

```

Jump to this kingdom's adjacent square.

```
≔ＫＤ⁹✳⊗λδ

```

Grab the line in the selected direction.

```
¿∧№δ#¬№…δ⌕δ#¦k

```

Does this line cross the first kingdom's line? If so:

```
¿⌕υκ«

```

If this is the third kingdom's line, then...

```
¿∧η⊖↔⁻ⅉ§η¹

```

... if the second kingdom's line isn't exactly one row away, then...

```
≔⟦⟦τ¹ζι⟧η⟦κλ⌕δ#μ⟧⟧ε

```

... save this as a solution.

```
»≔⟦κⅉλ⌕δ#μ⟧η

```

Otherwise for the second kingdom save this as its line.

```
»⎚

```

Clear the canvas ready for the first kingdom's next adjacent square or the final output.

```
»θＦε«Ｊ⊟§ι⁰⊟§ι⁰Ｍ✳⊗⊟ι✳⊗⊟ι×#⊟ι

```

Print the solution.

# Answer
> 3 votes
# Perl 5 `-00ap`, ~~114~~, 109 bytes

```
$_|=substr'iiiiiiiii
iaiaiaiai
'x5,10*!(grep/k/,@F[1,7]),90;1while s/(?<!i.{9})(?<!ii)i(?!iii|.{9}i.{9}i)/a/s

```

6 bytes saved thanks to @DomHastings, but 1 lost to fix a case.

Try it online!

Another perl answer, with a different approach, I've also upvoted the other perl answer.

I had to fix several times because of some cases (in addition to those of the question) for which it didn't work.

# Solution

The idea is to start from the grid of roads which almost works and fix for the different cases. If there's a kingdom in the square region of `o`s rows: 1 or 7 (after golfing), the grid is aligned on (0,0), otherwise on (0,1)

```
.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #
.........      # # # # #      #########
.........  ?   #########  :   # # # # #
.........      # # # # #      #########
.........      #########      # # # # #
ooooooooo      # # # # #      #########
.........      #########      # # # # #

```

Then the remaining roads can be fixed by removing squares when all the squares in the four directions, empirically (haven't a proof yet), at a distance of 3 (right), 2 (left, bottom) or 1 (up), are not a road (or are out of the map).

```
  ?
??#???
  ?
  ?

```

# Justification

Looking for a counter-example. Starting from a grid of roads and putting kingdoms so that road a kingdom could be disconnected.

Because of the symmetries only the first corner is shown. For grid 1, the only case which causes a problem:

```
k.k###
. # #
k#####
# # #

```

and as there is no kingdom in the region described in solution it can't occur.

For grid 2, one example but other configurations exist:

```
k # #
..k###
k # #
######

```

One of the 2 kingdoms that cut the roads must be in the region described in solution, so this can't occur.

# Answer
> 2 votes
# , 139 127 bytes

Starting from `[0,1]` or `[0,2]` forming two grids

```
#XX#… and .X.#…
#.#.…     ####…
####…     .#.#…
#.#.…     ####…

```

at least one of the 3 attempts will succeed (based on a hacked together J script.) For some byte saving, this tries some more grids:

```
+u({.@\:#@~.@,"3)0|:(d|.!.0]*1+i.@$)*"2/u=:(}:"2}:"{d|.10$#:1023 682)(2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)(9 9$!.1]1 2 2)*1=+)"2]

```

Try it online!

### How it roughly works

There should still be some bytes golfable. But for now:

```
(}:"2}:"{d|.10$#:1023 682)

```

The grid – first as a 10x10 matrix so we can easily shift via the 4 `d`irections, we'll define later. Drawback: we have to cut it down to 9x9. Now, for every grid:

```
(9 9$!.1]1 2 2)*1=+

```

Whenever a castle is on a road, set the tile to empty. Also, give the roads at `[0,1]` and `[0,2]` value 2 (if they exist). From there we'll find the biggest connected road network now:

```
 2=_(d=:(,-)#:i.3)&(*@]*[:>./|.!.0)

```

Until the map does not change: shift it around and give each road a new road number: the maximum of the current number and the ones of the connected roads (but keep 0 as 0). Finally, keep the roads marked with 2 – those are connected to the starting nodes

```
(d|.!.0]*1+i.@$)*"2/

```

Now to check that all castles are connected: Take the original input, and shift it into the 4 directions. Give each castle a unique number.

```
 +u({.@\:#@~.@,"3)0|:

```

Sort the grids by the number of connected castle (the unique numbers after the shifted castle numbers are multiplied with the 1's of the road network.) Take the best one, add the castles back in – et voilà, a kingdom for you!

# Answer
> 2 votes
# Charcoal, 67 bytes

```
Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧Ｂ⁹ψＦ⁹Ｆ⁹«Ｊκι¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »Ｆυ«Ｊ⊟ι⊟ιk»Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#

```

Try it online! Link is to verbose version of code. Outputs using spaces for empty tiles, but anything except `k` serves as empty on input. This is an entirely different approach to my previous answer, so I thought it deserved a separate answer. It relies on the observation that the grid with 16 holes solves all problems except those with three kingdoms near the corners. The one thing those problems have in common is that all three kingdoms lie on even rows and columns. In such cases the grid is offset diagonally resulting in a grid with 25 holes. Explanation:

```
Ｆ⁹Ｆ⌕ＡＳk⊞υ⟦ικ⟧

```

Read in the grid and save the coordinates of the kingdoms.

```
Ｂ⁹ψ

```

Prepare an empty area for the grid.

```
Ｆ⁹Ｆ⁹

```

Loop through each square on the grid.

```
«Ｊκι

```

Jump to that position.

```
¿¬№﹪⟦ικ⟧²﹪ΠＥυΠ⊕λ² »

```

If both the row and column have the same parity as the bitwise OR of all of the coordinates, then place an explicit space at that position, preventing it from being flood filled. Since I don't have a good way of taking the bitwise OR of a list, I use De Morgan's laws to check whether neither row nor column contain have the parity of the bitwise AND of the complement of the list, noting that for the purposes of parity, product is equivalent to bitwise AND and increment is equivalent to complement.

```
Ｆυ«Ｊ⊟ι⊟ιk»

```

Place the kingdoms on the grid.

```
Ｆ³Ｆ³«Ｊ⁺³κ⁺³ι¤#

```

Try to flood fill starting at each of the nine centre squares. This guarantees that the result is a single connected road. It's not possible for only three kingdoms to disconnect the centre of the grid, so this is always safe.

---
Tags: code-golf, grid, connected-figure
---