title: Coat of Many Colours

text:
# Question
Title: Coat of Many Colours
## Challenge

Given a list of **unique** colour names as input, sort them in the order that they first appear in Joseph's Amazing Technicolour Dreamcoat.

---

## Example

```
Input:  green, blue, red, brown
Output: red, green, brown, blue

```

The full list of colours, in order, is:

```
 1. red
 2. yellow
 3. green
 4. brown
 5. scarlet
 6. black
 7. ochre
 8. peach
 9. ruby
10. olive
11. violet
12. fawn
13. lilac
14. gold
15. chocolate
16. mauve
17. cream
18. crimson
19. silver
20. rose
21. azure
22. lemon
23. russet
24. grey
25. purple
26. white
27. pink
28. orange
29. blue

```

Or as an array of strings:

```
["red","yellow","green","brown","scarlet","black","ochre","peach","ruby","olive","violet","fawn","lilac","gold","chocolate","mauve","cream","crimson","silver","rose","azure","lemon","russet","grey","purple","white","pink","orange","blue"]

```

---

## Rules

* You may take input by any reasonable, convenient means (e.g., an array of strings, a delimited string, individual strings) as long as it's permitted by our standard I/O rules, but please specify your input method in your answer.
* You may do the same for your output.
* The input will only ever contain colours from the above list.
* Your solution should be able to handle empty inputs.
* You may choose whether all words in the input are consistently uppercase, lowercase or title case but your output's casing *must* match your input's.
* This is so lowest byte count in each language wins.
* As always, standard loopholes are forbidden.

---

## Test cases

```
Input:  []
Output: []

Input:  ["green", "blue", "red", "brown"]
Output: ["red", "green", "brown", "blue"]

Input:  ["gold", "grey", "green"]
Output: ["green", "gold", "grey"]

Input:  ["ruby","yellow","red","grey"]
Output: ["red", "yellow", "ruby", "grey"]

Input:  ["gold", "green", "fawn", "white", "azure", "rose", "black", "purple", "orange", "silver", "ruby", "blue", "lilac", "crimson", "pink", "cream", "lemon", "russet", "grey", "olive", "violet", "mauve", "chocolate", "yellow", "peach", "brown", "ochre", "scarlet", "red"]
Output: ["red", "yellow", "green", "brown", "scarlet", "black", "ochre", "peach", "ruby", "olive", "violet", "fawn", "lilac", "gold", "chocolate", "mauve", "cream", "crimson", "silver", "rose", "azure", "lemon", "russet", "grey", "purple", "white", "pink", "orange", "blue"]

```

# Answer
> 13 votes
# PowerShell, ~~262~~ ~~155~~ ~~151~~ ~~127~~ ~~125~~ 95 bytes

```
$args|sort{"rlyegwbrscbrocpyrvo lvnfaldgccvmacmcvseraolsrygpptwkpnoeb".indexof((-join$_[3,0]))}

```

Try it online!

~~Naive approach.~~ PowerShell `sort-object` can sort based on a script block that gets executed for every object. Here we're simply getting the `.IndexOf()` the color from a string, which will assign a numerical value to each color, and then sorts based on those numbers. The string is constructed from the fourth and first letters of each color to ensure uniqueness. Output is implicit.

*-4 bytes thanks to Shaggy.*
*-2 bytes thanks to mazzy.*
*A whopping -30 bytes thanks to KGlasier.*

# Answer
> 10 votes
# JavaScript (SpiderMonkey),  ~~104~~  101 bytes

*"When in doubt, just hash the bloody input."*

```
a=>a.sort((a,b)=>(g=s=>'mgo0dakbrfs0h0000j9c412603e870500p0l0niq'[parseInt(s,36)%657%53%42])(a)>g(b))

```

Try it online!

# Answer
> 7 votes
# Jelly, 28 bytes

```
“½Ṗ©cƘʂẒẹMMỤẓHP’Œ?“ðÑþQ’,ḥµÞ

```

Try it online!

### How it works

`µ` turns everything to its left into a monadic chain, which `Þ` maps over the input array and sorts the input according to the generated values.

`“½Ṗ©cƘʂẒẹMMỤẓHP’` sets the return value to 176073885534954276199526358143331.

`Œ?` generates the 176073885534954276199526358143331th permutation of the positive integers (without the sorted tail), yielding \\$\small\[20,28,15,3,5,26,18,16,8,30,4,25,2,21,22,11,24,1,23,10,29,12,17,27,14,9,6,13,7,19\]\\$.

`“ðÑþQ’` yields 391695582; `,` prepends it to the permutation. Then, c ompute Jelly's 391695582th hash function, mapping the resulting buckets to the integers of the permutation.

The magic constant 391695582 was found by Jelly's utils.

```
dennis-home:utils$ time ./findhash 30 29 <<< '["red","yellow","green","brown","scarlet","black","ochre","peach","ruby","olive","violet","fawn","lilac","gold","chocolate","mauve","cream","crimson","silver","rose","azure","lemon","russet","grey","purple","white","pink","orange","blue"]'
391695582

real    0m2.058s
user    0m15.077s
sys     0m0.023s

```

# Answer
> 6 votes
# Python 3, 93 bytes

```
lambda r:sorted(r,key=lambda s:'iV^ZzwnFM@pYuOobXGAKyf[tUR]E'.find(chr(int(s,36)%127%60+64)))

```

Try it online!

Reads each color as a base-36 `int`. Brute-forced the moduli and chose an arbitrary offset among the 19 that didn't require escapes.

# Answer
> 5 votes
# Powershell, ~~124~~ ~~120~~ ~~124~~ ~~119~~ ~~118~~ 102 bytes

```
$args|sort{$c=$_
'bluOrPiWPuG*yRusLeARoSiCriCrMCGoLFVOlRuPOBlSBGYR'-csplit'(?=[A-Z])'|%{$c-like"$_*"}}

```

Try It Online!

Explanation:

1. The data string contains the first significant letters of the color labels in descending order. Except for the `Grey` label - `G*y` is shorter.
2. `-csplit'(?=[A-Z])'` splits the data string to the array `(blu,Or,Pi,W,Pu,G*y,Rus,Le,A,Ro,Si,Cri,Cr,M,C,Go,L,F,V,Ol,Ru,P,O,Bl,S,B,G,Y,R)`
3. `|%{$c-like"$_*"}` maps the string array to the array of boolean. Where `True` means "a color label starts from this string" (like is case-insensitive operator, csplit - case-sensitive. see doc).
4. `sort{}` sorts a color lables by the arrays of boolean in ascending order.

The sorting by array is a very interesting feature in the Powershell. In this script all arrays have the same length and contain Boolean values only. This sorting is performed in the lexographic order of boolean arrays.

Therefore, the string can contain one-letter abbreviations for the last labels. If there is a match at the beginning of the array, the matches at the end have no effect.

```
       blu Or Pi W Pu G*y Rus Le A Ro Si Cri Cr M C Go L F V Ol Ru P O Bl S B G Y R
green: -   -  -  - -  -   -   -  - -  -  -   -  - - -  - - - -  -  - - -  - - T - -
gold : -   -  -  - -  -   -   -  - -  -  -   -  - - T  - - - -  -  - - -  - - T - -
grey : -   -  -  - -  T   -   -  - -  -  -   -  - - -  - - - -  -  - - -  - - T - -

     : green < gold < grey

```

Where `T` is `true` and `-` is `false`.

---

Test script:

```
$f = {

$args|sort{$c=$_
'bluOrPiWPuG*yRusLeARoSiCriCrMCGoLFVOlRuPOBlSBGYR'-csplit'(?=[A-Z])'|%{$c-like"$_*"}}

}

@(
    ,( @(), @() )
    ,( ('green', 'blue', 'red', 'brown'), ('red', 'green', 'brown', 'blue') )
    ,( ("gold", "grey", "green"), ("green", "gold", "grey") )
    ,( ("ruby","yellow","red","grey"), ("red", "yellow", "ruby", "grey") )
    ,( ("gold", "green", "fawn", "white", "azure", "rose", "black", "purple", "orange", "silver", "ruby", "blue", "lilac", "crimson", "pink", "cream", "lemon", "russet", "grey", "olive", "violet", "mauve", "chocolate", "yellow", "peach", "brown", "ochre", "scarlet", "red"),
       ("red", "yellow", "green", "brown", "scarlet", "black", "ochre", "peach", "ruby", "olive", "violet", "fawn", "lilac", "gold", "chocolate", "mauve", "cream", "crimson", "silver", "rose", "azure", "lemon", "russet", "grey", "purple", "white", "pink", "orange", "blue") )
) | % {
    $inp,$expected = $_
    $result = &$f @inp  # splatting
    "$("$result"-eq"$expected"): $result"
}

```

Output:

```
True:
True: red green brown blue
True: green gold grey
True: red yellow ruby grey
True: red yellow green brown scarlet black ochre peach ruby olive violet fawn lilac gold chocolate mauve cream crimson silver rose azure lemon
russet grey purple white pink orange blue

```

# Answer
> 4 votes
# C (clang), ~~121~~ 119 bytes

```
#define j(i)index(".MH^>SALcD8Z!)3TF(RNe*aQU<,'",(**i^377)%75+30)
s(**a,**b){return j(a)-j(b);}f(*t,n){qsort(t,n,8,s);}

```

Try it online!

-2 bytes thanks ceilingcat!

# Answer
> 3 votes
# Wolfram Language ~~255 213~~ 199 bytes

Fourteen bytes saved by Dennis, who avoided the " marks, using symbols instead of strings.

```
SortBy[#,{yellow,green,brown,scarlet,black,ochre,peach,ruby,olive,violet,fawn,lilac,gold,chocolate,mauve,cream,crimson,silver,rose,azure,lemon,russet,grey,purple,white,pink,orange,blue}~Position~#&]&

```

Try It Online!

# Answer
> 3 votes
*I will improve the string compression in a while*

# Japt, ~~88~~ ~~78~~ 71 bytes

```
ñ@`äŠâwrÒ.cÖ¨acru½ivo¤faØngoÒqauvœamsolv€osz¨e¶s gœrpl–tpˆ„g½u`bXé4 ¯3

```

Try it online!

# Answer
> 3 votes
# Python 2, 186 bytes

```
lambda a:[y for x,y in sorted((max(" y gree br sc bla oc pe rub ol v f li go ch m cre cri si ro a le rus grey pu w pi or blu ".find(" %s "%c[:i+1])for i,j in enumerate(c)),c)for c in a)]

```

Try it online!

Finds all matches for progressive character substrings (Ex: "green" will check for "g", "gr", "gre", "gree", and "green") in the identifier string, and keeps the maximum index. "red" is always first, anf find() returns -1 for missing matches, so there is no identifier for red specifically.

Once the colors are turned into (index, color) pairs, sorts array on first item of pair and then discards first item of each pair.

# Answer
> 2 votes
# Python 3, 130 bytes

```
lambda*a:sorted(a,key=lambda c:("r,ylgebwsrtbcorpcryovvlfnlagdccamvca cmnsvrearlorsgyppwtpkonbe".find(c[::3]+" "*(c=="cream")),c))

```

Try it online!

# Answer
> 2 votes
# Charcoal, ~~69~~ ~~68~~ ~~63~~ ~~56~~ 52 bytes

```
Ｆ⪪”&⌊Oτe¿k⟲ⅈζLbψ#>φuＣ№ς…Ｘ◧9gF→G⌈Ｈ≡M*e{-”²Φθ⁼ι⁺§κ⁰§κ³

```

Try it online! Link is to verbose version of code. Explanation: Now a port of @Sok's Pyth answer.

```
Ｆ⪪”&⌊Oτe¿k⟲ⅈζLbψ#>φuＣ№ς…Ｘ◧9gF→G⌈Ｈ≡M*e{-”²

```

Take the compressed string `rrylgebwsrbcorpcryovvlfnlagdccmvcacmsvrearlorsgyppwtpkonbe` and loop over each substring of length 2.

```
Φθ⁼ι⁺§κ⁰§κ³

```

For each substring print those input strings whose first and fourth (cyclically) characters equal the substring.

# Answer
> 2 votes
# C# (Visual C# Interactive Compiler), ~~321~~ ~~219~~ ~~210~~ ~~161~~ ~~159~~ 138 bytes

```
n=>n.OrderBy(a=>a!="grey"?"yelgrebroscablaochperuboliviofawlilgolchomaucrecrisilrosazulemruspurwhipinorablu".IndexOf(a.Substring(0,3)):65)

```

Try it online!

*-3 bytes thanks to Shaggy, -18 thanks to TheLethalCoder*

Takes input as a `List<string>`, returns an `IOrderedEnumerable<string>`

How this works is that it orders the list by each string's index in the original string. The original string has every color except for grey turned to it's first three letters. Grey is not there, since green and grey would cause ambiguity. Red isn't there either, since `IndexOf` returns -1 if the string doesn't appear.

# Shorter version taking IOrderedEnumerable as input, 137 bytes

```
n=>n.ThenBy(a=>a!="grey"?"yelgrebroscablaochperuboliviofawlilgolchomaucrecrisilrosazulemruspurwhipinorablu".IndexOf(a.Substring(0,3)):65)

```

Takes advantage of the fact that `ThenBy` is 1 byte shorter than `OrderBy`, but `ThenBy` only operates on `IOrderedEnumerable`s though.

Try it online!

# Answer
> 1 votes
# Pyth, 66 bytes

```
oxc."ayÇæ£ðÐ¥~@iF[2BÍÐ:Yë)^ksTTã"2s@LN,03

```

Try it online here, or verify all the test cases at once here.

The colours in the list can be uniquely identified by taking the characters at index `0` and `3`, assuming modular indexing. This results in the following mapping:

```
rr -> red
yl -> yellow
ge -> green
bw -> brown
sr -> scarlet
bc -> black
or -> ochre
pc -> peach
ry -> ruby
ov -> olive
vl -> violet
fn -> fawn
la -> lilac
gd -> gold
cc -> chocolate
mv -> mauve
ca -> cream
cm -> crimson
sv -> silver
re -> rose
ar -> azure
lo -> lemon
rs -> russet
gy -> grey
pp -> purple
wt -> white
pk -> pink
on -> orange
be -> blue

```

Full explanation:

```
oxc."..."2s@LN,03Q   Implicit: Q=eval(input())
                     Trailing Q inferred, dictionary string replaced with ... for brevity
o                Q   Order the elements of Q, as N, using:
              ,03      [0,3]
           @LN         Get the characters at the above indices in N
          s            Concatenate into a string
                         The above is result {1}
   ."..."              The compressed dictionary string
  c      2             Split into chunks of length 2
 x                     Get the index of {1} in the above
                       Implicit print of sorted list

```

# Answer
> 1 votes
# 05AB1E, 48 bytes

```
Σ.•Aå₂мÕh∊þèmvƶ\kΛ1YŠíJ>J#θ₁2©€,Ù{η¦ù-•2ôy¬s3è«k

```

Same solution as most other answers. Will try to golf it down from here later.

Try it online or verify all test cases.

**Explanation:**

```
Σ          # Sort the (implicit) input-list by:
 .•Aå₂мÕh∊þèmvƶ\kΛ1YŠíJ>J#θ₁2©€,Ù{η¦ù-•
           #  Push compressed string "rrylgebwsrbcorpcryovvlfnlagdccmvcacmsvrearlorsgyppwtpkonbe"
  2ô       #  Split into parts of size 2
 y         #  Push the current string of the list we're sorting
  ¬        #  Push its head (without popping)
   s       #  Swap so the string is at the top of the stack again
    3è     #  Get the character at index 3 (with automatic wraparound)
      «    #  Merge both characters together
       k   #  And get the index in the compressed string to sort on

```

See this 05AB1E tip (section *How to compress strings not part of the dictionary?*) to understand how `.•Aå₂мÕh∊þèmvƶ\kΛ1YŠíJ>J#θ₁2©€,Ù{η¦ù-•` is `"rrylgebwsrbcorpcryovvlfnlagdccmvcacmsvrearlorsgyppwtpkonbe"`.

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


title: Find sum of odd numbers

text:
# Question
Title: Find sum of odd numbers
Write a program to find the sum of all odd numbers between a given range \[a,b\]. Input consists of a single line containing two integers a and b separated by a space. 0 ≤ a,b ≤ 1,000,000,000,000. Your program should not take more than 10 secs.

```
Sample Inputs
1 5
4 8
1 8
0 5

Sample Outputs
9
12
16
9

```

# Answer
## Ruby, 43 characters

```
p eval"-(%d/2)**2+((%d+1)/2)**2"%gets.split

```

Example for largest input:

```
$ time echo "1 10000000000000000" | ruby oddsum.rb
25000000000000000000000000000000

real    0m0.006s
user    0m0.000s
sys     0m0.000s

```
> 10 votes

# Answer
## Funciton

Not a language particularly suitable for golfing, but I gave it my best shot to cram everything together in best code-golf tradition. Near the end I was making rearrangements that gave net savings of a single character until I could find no more ways to improve it :)

This is **398 characters** (or 786 bytes in UTF-16). I challenge anyone to find a way to make it smaller :)

```
 ┌───┐    ┌──────────┐
╔╧╗┌─┴╖┌─╖│╔═╗┌──╖┌─╖│
║ ║│>>╟┤_╟┘║1╟┤>>╟┤♯╟┘
╚═╝╘╤═╝╘═╝ ╚═╝╘═╤╝╘═╝
    └┐ ┌─┐ ╔══╗┌┴───┐
╔══╗┌┴╖│┌┴╖║32║│ ┌─╖│
║21╟┤×╟┘│♯║╚╤═╝└─┤×╟┘
╚══╝╘═╝ ╘╤╝┌┘ ┌─┐╘╤╝
┌──────┬─┘┌┘ ┌┴╖└─┘
│╔═╗  ┌┴╖┌┘  │−╟┐┌───────╖
│║0║ ┌┤ʘ╟┘┌─┐╘╤╝└┤int→str╟
│╚╤╝ │╘═╝┌┴╖└─┘  ╘═══════╝
│┌┴╖╔╧╗┌─┤×╟┐
└┤ʃ╟╢ ║│ ╘═╝│
 ╘╤╝╚═╝└┬───┘
  │┌─╖┌─┴╖╔═╗╓─╖┌───────╖
  └┤_╟┤>>╟╢1║║_╟┤str→int╟
   ╘═╝╘══╝╚═╝╙─╜╘═══════╝

```
> 14 votes

# Answer
## Windows PowerShell, ~~84~~ ~~61~~ 55

```
$a,$b=-split"$input+1"|iex|%{($_-band-2)/2}
$b*$b-$a*$a

```

O(1) runtime.
> 4 votes

# Answer
## Golfscript - 12 chars

```
~)2/2?\2/2?-

```

can be done in 11 chars if the order of the inputs is reversed

```
~)]{2/2?}/-

```
> 3 votes

# Answer
# Python, 32 bytes

As unnamed lambda function:

```
lambda a,b:((b+1)/2)**2-(a/2)**2

```

Did some math to get a direct formula. Proof will follow.
> 1 votes

# Answer
# Vyxal `s`, 7 bytes

```
›"2ḭ²Ḃ¯

```

Try it Online!

```
STACK = [4,8]
›               Increment, [5, 8]
"               Pair  [[5, 8]]
2              Push 2 [[5, 8], 2]
ḭ               Integer Division [[2, 4]]
²               Square [[4, 16]]
Ḃ              Reverse [[16, 4]]
¯               Deltas    [[12]]
                 Implicit Sum [12]

```
> 1 votes

---
Tags: code-golf, restricted-time
---


title: Remove r-th powers

text:
# Question
Title: Remove r-th powers
Given two numbers r and n on separate lines, write a program to print n natural numbers starting from 1 onwards, excluding the r-th powers. For example,

If `r=2` and `n=10`, the results would be `2,3,5,6,7,8,10,11,12,13`

4 and 9 were excluded because 4 is `2^2` and 9 is `3^2`

```
Sample Input
2
10
Sample Output
2 3 5 6 7 8 10 11 12 13

Sample Input
3
30
Sample Output
2 3 4 5 6 7 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 28 29 30 31 32 33

```
1. `1 < r < 10`
2. `0 < n < 1,000,000`

> Since nobody came up with this, here's a hint to reduce your solution sizes:
>
> The `i`th term of the output is given by `floor(i+pow(i+pow(i,1/r), 1/r))`.

# Answer
> 4 votes
## Golfscript, 18 characters

```
~.3*,.{3$?}%-@;<n*

```

Basically a direct port of my Ruby solution. Also probably not completely golfed yet, I'll take a look at it later today again.

# Answer
> 4 votes
## Ruby, 56 characters

```
r,n=$<.map &:to_i;puts ([*l=1..2*n]-l.map{|i|i**r})[0,n]

```

Pretty straightforward (and similar to Lars' solution). Takes about 5 seconds to complete for `r = 2, n = 1000000` and 8 seconds for `r = 10, n = 1000000` here.

# Answer
> 2 votes
### Golfscript (18 17 chars)

```
~.3*,@{?}+1$%-<n*

```

This turns out to be similar to Ventero's solution, but slightly shorter (at time of writing!)

For a more efficient solution, 26 chars gives

```
~2.@{.2$4$?={)\)\}*.p)}*];

```

which uses the obvious algorithm:

```
int k = 2, x = 2;
for (i = 0; i < n; i++) {
    if (pow(k,r) == x) {k++; x++;}
    println(x++);
}

```

# Answer
> 2 votes
## Python 2, 84 83  80 chars

```
r,n=input()
r+=.0
i=c=1
while c<=n:
    p=i**(1/r)
    if p!=int(p):print i;c+=1
    i+=1

```

Runs in about 3 seconds for r=2, n=1000000

# Answer
> 2 votes
**Python 68 Chars**

```
r=input();i=0;exec'i+=1;print int(i+(i+i**(1./r))**(1./r));'*input()

```

# Answer
> 1 votes
## Windows PowerShell, 88

```
for($x,$r,[int]$n=,1+@($input);$n--){if((1..$n|%{[Math]::Pow($_,$r)})-eq$x){$x++}($x++)}

```

Fairly straightforward, but probably way too long.

# Answer
> 1 votes
## Ruby (~~79~~ 77 chars)

```
n,r=$<.map &:to_i
a=(0..n*2).map{|x|[x,x**r]}.transpose
p (a[0]-a[1])[0,n]*?,

```

Yes, this does a lot of wasted effort, but it completes in about 8 secs for n=1E6,r=10 on my laptop.

# Answer
> 1 votes
# J, 32

```
(4 :'y{.I.(~:<.)x%:i.1001000')/,

```

This assumes the input has the shape `2 1`, i.e., a vertical list of two rows with one atom per row, e.g.,

```
 2
10

```

This solution is instantaneous for r = 9, n = 999999, which (unless I've misread the question) are the upper bounds for the input parameters.

# Answer
> 1 votes
## Qwerty RPN (52)

```
@=r@=n>L$i)=i$i 1$r/^:\=<S$n(=n$i#32.>S 0$n=<B 1<L>B

```

Ungolfed

```
@ =r  ; input number r
@ =n  ; input number n, counter variable

0 =i  ; the next number to be printed (pre-assigning variable is optional)
>loop ; label loop
  $i ) =i ; pre-increase i

  $i 1 $r / ^ : \ = <skipped ; skip printing and increasing counter n if i^(1 / r) == round(i^(1 / r))
    $n ( =n ; decrease n
    $i #    ; print number i
    32 .    ; print space
  >skipped

  0 $n = <break ; if n == 0: break loop
  1 ; TRUE
<loop  ; go back to beginning of loop
>break ; this is where the loop ends

```

# Answer
> 1 votes
## JavaScript, ~~118~~ 111 bytes

```
function d(r,n){for(var a=[],i=m=0,p=1;i<n;p++,m=Math.pow(p,1/r))if((m|0)!=m){a.push(p);i++}return a.join(" ")}

```

# Answer
> 1 votes
# Perl - 51

```
map{print$_.$/if($_**(1/$ARGV[0])!~/^\d+$/)}1..pop;

```

Not quite up to spec, as it takes ~12/13s for r=10/n=1000000, and takes r/n as command line args instead of on separate lines -- but other than that it works.

# Answer
> 1 votes
# Vyxal, 11 bytes

```
+¹$r'¹Ėe:I≠

```

Try it Online!

```
+¹$r        # Input range
'¹Ėe         # r-th root of each item in range
:I≠           # Filter roots with no fractional part

```

# Answer
> 0 votes
**C++, ~~97~~ ~~95~~ 90**

```
int main(){int r,s,n,m=0;cin>>r;cin>>n;s=r;while(m++!=n)r!=m?cout<<m<<' ',r*=r<m?s:1:++n;}

```

**(eventually +20)**

```
using namespace std;

```

# Answer
> 0 votes
**Scala 172**

```
def p(r:Int,n:Int)={def f(n:Int):Stream[Int]=n#::f(n+1);lazy val i=f(0);lazy val o=i.filter(a => math.pow(a,1.0/r)!=math.pow(a,1.0/r).toInt);print(o.take(n).mkString(","))}

```

# Answer
> 0 votes
# Python 2, 60 bytes

```
r,n=input();i=0
while n:
 i+=1
 if i**r**-1%1:
	print i;n-=1

```

Try it online!

---
Tags: code-golf
---


title: Golf bit weaving

text:
# Question
Title: Golf bit weaving
**Note: the first half of this challenge comes from Martin Ender's previous challenge, Visualize Bit Weaving.**

The esoteric programming language evil has an interesting operation on byte values which it calls "weaving".

It is essentially a permutation of the eight bits of the byte (it doesn't matter which end we start counting from, as the pattern is symmetric):

* Bit 0 is moved to bit 2
* Bit 1 is moved to bit 0
* Bit 2 is moved to bit 4
* Bit 3 is moved to bit 1
* Bit 4 is moved to bit 6
* Bit 5 is moved to bit 3
* Bit 6 is moved to bit 7
* Bit 7 is moved to bit 5

For convenience, here are three other representations of the permutation. As a cycle:

```
(02467531)

```

As a mapping:

```
57361402 -> 76543210 -> 64725031

```

And as a list of pairs of the mapping:

```
[[0,2], [1,0], [2,4], [3,1], [4,6], [5,3], [6,7], [7,5]]

```

After `8` weavings, the byte is essentially reset.

For example, weaving the number `10011101` (which is `157` in base 10) will produce `01110110` (which is `118` in base 10).

# Input

There are only `256` valid inputs, namely all the integers between `0` and `255` inclusive. That may be taken in any base, but it must be consistent and you must specify it if the base you choose is not base ten.

You may **not** zero-pad your inputs.

# Output

You should output the result of the bit weaving, in any base, which must also be consistent and specified if not base ten.

You **may** zero-pad your outputs.

---

Related: Visualize Bit Weaving

# Answer
> 33 votes
# Python 2.7, 44 -\> 36 bytes

```
lambda x:x/4&42|x*2&128|x*4&84|x/2&1

```

# Answer
> 15 votes
# Evil, 3 characters

```
rew

```

Try it online!

Input is in base 256, (e.g. ASCII), e.g. to enter the digit 63, enter ASCII 63 which is `?`.

Explanation:

```
r          #Read a character
 e         #Weave it
  w        #Display it

```

This *so* feels like cheating.

# Answer
> 11 votes
## CJam, ~~15~~ 12 bytes

*Thanks to FryAmTheEggman for saving 3 bytes.*

```
l8Te[m!6532=

```

Input in base 2. Output also in base 2, padded to 8 bits with zeros.

Test it here.

### Explanation

```
l      e# Read the input.
8Te[   e# Left-pad it to 8 elements with zeros.
m!     e# Generate all permutations (with duplicates, i.e. treating equal elements
       e# in different positions distinctly).
6532=  e# Select the 6533rd, which happens to permute the elements like [1 3 0 5 2 7 4 6].

```

# Answer
> 7 votes
# MATL, 14 bytes

```
&8B[2K1B3D5C])

```

Input is in decimal. Output is zero-padded binary.

**Try it online!**

### Explanation

```
&8B         % Take input number implicitly. Convert to binary array with 8 digits
[2K1B3D5C]  % Push array [2 4 1 6 3 8 5 7]
)           % Index first array with second array. Implicitly display

```

# Answer
> 7 votes
# Jelly, 11 bytes

```
+⁹BḊŒ!6533ị

```

Translation of Martin’s CJam answer. Try it here.

```
+⁹BḊ          Translate (x+256) to binary and chop off the MSB.
              This essentially zero-pads the list to 8 bits.
    Œ!        Generate all permutations of this list.
      6533ị   Index the 6533rd one.

```

# Answer
> 7 votes
## JavaScript (ES6), 30 bytes

```
f=n=>n*4&84|n*2&128|n/2&1|n/4&42

```

# Answer
> 7 votes
# x86 machine code, 20 bytes

In hex:

```
89C22455C1E002D0E0D1E880E2AAC0EA0211D0C3

```

It's a procedure taking input and returning result via AL register

## Disassembly

```
89 c2                   mov    edx,eax
24 55                   and    al,0x55  ;Clear odd bits
c1 e0 02                shl    eax,0x2  ;Shift left, bit 6 goes to AH...
d0 e0                   shl    al,1     ;...and doesn't affected by this shift
d1 e8                   shr    eax,1    ;Shift bits to their's target positions
80 e2 aa                and    dl,0xaa  ;Clear even bits
c0 ea 02                shr    dl,0x2   ;Shift right, bit 1 goes to CF
11 d0                   adc    eax,edx  ;EAX=EAX+EDX+CF
c3                      ret

```

# Answer
> 7 votes
# C (unsafe macro), 39 bytes

```
#define w(v)v*4&84|v*2&128|v/2&1|v/4&42

```

# C (function), 41 bytes

```
w(v){return v*4&84|v*2&128|v/2&1|v/4&42;}

```

# C (full program), 59 bytes

```
main(v){scanf("%d",&v);return v*4&84|v*2&128|v/2&1|v/4&42;}

```

(returns via exit code, so invoke with `echo "157" | ./weave;echo $?`)

# C (standards-compliant full program), 86 bytes

```
#include<stdio.h>
int main(){int v;scanf("%d",&v);return v*4&84|v*2&128|v/2&1|v/4&42;}

```

# C (standards-compliant full program with no compiler warnings), 95 bytes

```
#include<stdio.h>
int main(){int v;scanf("%d",&v);return (v*4&84)|(v*2&128)|(v/2&1)|(v/4&42);}

```

# C (standards-compliant full program with no compiler warnings which can read from arguments or stdin and includes error/range checking), 262 bytes

```
#include<stdio.h>
#include<stdlib.h>
#include<unistd.h>
int main(int v,char**p){v=v<2?isatty(0)&&puts("Value?"),scanf("%d",&v)?v:-1:strtol(p[1],p,10);exit(*p==p[1]||v&255^v?fprintf(stderr,"Invalid value\n"):!printf("%d\n",(v*4&84)|(v*2&128)|(v/2&1)|(v/4&42)));}

```

### Breakdown

Pretty much the same as a lot of existing answers: bit-shift all the bits into place by using `<<2` (`*4`), `<<1` (`*2`), `>>1` (`/2`) and `>>2` (`/4`), then `|` it all together.

The rest is nothing but different flavours of boiler-plate.

# Answer
> 6 votes
# J, 12 bytes

```
6532 A._8&{.

```

Uses the permute builtin `A.` with permutation index `6532` which corresponds to the bit-weaving operation.

## Usage

Input is a list of binary digits. Output is a zero-padded list of 8 binary digits.

```
   f =: 6532 A._8&{.
   f 1 0 0 1 1 1 0 1
0 1 1 1 0 1 1 0
   f 1 1 1 0 1 1 0
1 1 0 1 1 0 0 1

```

## Explanation

```
6532 A._8&{.  Input: s
       _8&{.  Takes the list 8 values from the list, filling with zeros at the front
              if the length(s) is less than 8
6532          The permutation index for bit-weaving
     A.       permute the list of digits by that index and return

```

# Answer
> 6 votes
## Retina, 39 bytes

```
+`^(?!.{8})
0
(.)(.)
$2$1
\B(.)(.)
$2$1

```

Input and output in base 2, output is left-padded.

Try it online!

## Explanation

```
+`^(?!.{8})
0

```

This just left-pads the input with zeros. The `+` indicates that this stage is repeated until the string stops changing. It matches the beginning of the string as long as there are less than 8 characters in it, and inserts a `0` in that position.

Now for the actual permutation. The straight-forward solution is this:

```
(.)(.)(.)(.)(.)(.)(.)(.)
$2$4$1$6$3$8$5$7

```

However that's painfully long and redundant. I found a different formulation of the permutation that is much easier to implement in Retina (`X` represents a swap of adjacent bits):

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

```

Now that's much easier to implement:

```
(.)(.)
$2$1

```

This simply matches two characters and swaps them. Since matches don't overlap, this swaps all four pairs.

```
\B(.)(.)
$2$1

```

Now we want to do the same thing again, but we want to skip the first character. The easiest way to do so is to require that the match *doesn't* start at a word boundary with `\B`.

# Answer
> 4 votes
# Mathematica, 34 bytes

```
PadLeft[#,8][[{2,4,1,6,3,8,5,7}]]&

```

Anonymous function. Takes a list of binary digits, and outputs a padded list of 8 binary digits.

# Answer
> 3 votes
## Matlab, ~~49~~ ~~48~~ 44 bytes

```
s=sprintf('%08s',input(''));s('24163857'-48)

```

Takes input as string of binary values. Output padded. 4 bytes saved thanks to @Luis Mendo.

**Explanation:**

```
input('')             -- takes input
s=sprintf('%08s',...) -- pads with zeros to obtain 8 digits
s('24163857'-48)      -- takes positions [2 4 1 6 3 8 5 7] from s (48 is code for '0')

```

# Answer
> 3 votes
## 05AB1E, ~~14~~ 12 bytes

```
žz+b¦œ6532èJ

```

**Explanation**

```
žz+b¦           # convert to binary padded with 0's to 8 digits
     œ6532è     # get the 6532th permutation of the binary number
           J    # join and implicitly print

```

Input is in base 10.
Output is in base 2.

Borrows the permutation trick from MartinEnder's CJam answer

Try it online

# Answer
> 3 votes
## PowerShell v2+, 34 bytes

```
("{0:D8}"-f$args)[1,3,0,5,2,7,4,6]

```

Translation of @LegionMammal978's answer. Full program. Takes input via command-line argument as a binary number, outputs as a binary array, zero-padded.

The `"{0:D8}"-f` portion uses standard numeric format strings to prepend `0` to the input `$args`. Since the `-f` operator supports taking an array as input, and we've explicitly said to use the first element `{0:`, we don't need to do the usual `$args[0]`. We encapsulate that string in parens, then index into it `[1,3,0,5,2,7,4,6]` with the weaving. The resultant array is left on the pipeline and output is implicit.

### Examples

*(the default `.ToString()` for an array has the separator as ``n`, so that's why the output is newline separated here)*

```
PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 10011101
0
1
1
1
0
1
1
0

PS C:\Tools\Scripts\golfing> .\golf-bit-weaving.ps1 1111
0
0
0
1
0
1
1
1

```

# Answer
> 3 votes
# , 17 bytes

```
8é0$7hd|òxplò2|@q

```

Try it online!

This takes input and output in binary. Most of the byte count comes from padding it with 0's. If padding the input was allowed, we could just do:

```
òxplò2|@q

```

Thanks to Martin's solution for the method of swapping characters, e.g:

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

```

Explanation:

```
8é0                 "Insert 8 '0' characters
   $                "Move to the end of the current line
    7h              "Move 7 characters back
      d|            "Delete until the first character
        ò   ò       "Recursively:
         xp         "Swap 2 characters
           l        "And move to the right
             2|     "Move to the second column
               @q   "And repeat our last recursive command.

```

# Answer
> 2 votes
## Labyrinth, ~~27~~ 26 bytes

```
_1@
&,)}}}=}}=}}=}!{!!{{!"

```

Input and output in base 2. Output is padded.

Try it online!

# Answer
> 2 votes
# Pyth, 19 characters

```
s[@z1.it%2tzP%2z@z6

```

Input and output are base 2.

Far from a Pyth expert, but since no one else has answered with it yet I gave it a shot.

Explanation:

```
s[                # combine the 3 parts to a collection and then join them
  @z1             # bit 1 goes to bit 0
  .i              # interleave the next two collections
    t%2tz         # bits 3,5,7; t is used before z to offset the index by 1
    P%2z          # bits 0,2,4
  @z6             # bit 6 goes to bit 7

```

# Answer
> 2 votes
## vi, 27 bytes

```
8I0<ESC>$7hc0lxp<ESC>l"qd0xp3@q03@q

```

Where `<ESC>` represents the Escape character. I/O is in binary, output is padded. 24 bytes in vim:

```
8I0<ESC>$7hd0xpqqlxpq2@q03@q

```

# Answer
> 2 votes
# UGL, 50 bytes

```
cuuRir/r/r/r/r/r/r/%@@%@@%@@%@@@%@@%@@%@@@oooooooo

```

Try it online!

Repeatedly div-mod by 2, and then `%` swap and `@` roll to get them in the right order.

Input in base-ten, output in base-two.

# Answer
> 1 votes
## Actually, 27 bytes

```
'08*+7~@tñiWi┐W13052746k♂└Σ

```

Try it online!

This program does input and output as a binary string (output is zero-padded to 8 bits).

Explanation:

```
'08*+7~@tñiWi┐W13052746k♂└Σ
'08*+                        prepend 8 zeroes
     7~@t                    last 8 characters (a[:~7])
         ñi                  enumerate, flatten
           Wi┐W              for each (i, v) pair: push v to register i
               13052746k     push [1,3,0,5,2,7,4,6] (the permutation order, zero-indexed)
                        ♂└   for each value: push the value in that register
                          Σ  concatenate the strings

```

# Answer
> 0 votes
# JavaScript, 98 Bytes

Input is taken in base-2 as a string, output is also base-2 as a string

```
n=>(n.length<8?n="0".repeat(8-n.length)+n:0,a="13052746",t=n,n.split``.map((e,i)=>t[a[i]]).join``)

```

# Answer
> 0 votes
# Japt, 11 bytes

I/O as binary strings

```
ùT8 á g6532

```

Try it \- header & footer convert from and to decimal.

---
Tags: code-golf, permutations, bitwise
---


title: Enlarge ASCII art, Mark II

text:
# Question
Title: Enlarge ASCII art, Mark II
Related

Given a piece of ascii art and a factor to enlarge it by, which will always be an odd number \>1, replace each character with the corresponding ascii-art, resized to fit on a grid the size of the input number:

| Character | What to do |
| --- | --- |
| `\` | ``` \  <br> \ <br>  \ ``` A line of `\` to the length of the enlarging factor, padded to form a line. |
| `/` | ```   /<br> / <br>/   ``` A line of `/` to the length of the enlarging factor, padded to form a line. |
| `|` | ```  | <br> | <br> |  ``` A line of `|` to the length of the enlarging factor, centred horizontally. |
| `-` | ```    <br>---<br>    ``` A line of `-` to the length of the enlarging factor, centered vertically. |
| `_` | ```    <br>   <br>___ ``` A line of `_` to the length of the enlarging factor, at the bottom of the square it's in. |

And of course, a space should be resized to a n-by-n grid of spaces. The input will only contain these six characters, plus newlines.

You may take input as a list of lines, a matrix of characters, whatever.

This is a bit confusing, so here's an example:

```
-\
 /, 3 =>
   \
--- \
     \
     /
    /
   /

```

Because each character is enlarged to size 3.

Any trailing whitespace is allowed.

# Scoring

This is , shortest wins!

# Testcases

```
\, 3 =>
\
 \
  \

---, 3 =>

---------

|
|
|, 3 =>
 |
 |
 |
 |
 |
 |
 |
 |
 |

|\_/|
|   |
 \_/ , 3 =>
 | \       / |
 |  \     /  |
 |   \___/   |
 |           |
 |           |
 |           |
   \       /
    \     /
     \___/

_____
\   /
/   \
\___/, 3 =>

_______________
\             /
 \           /
  \         /
  /         \
 /           \
/             \
\             /
 \           /
  \_________/

  /\
 /  \
/____\
  ||
  ||
_/__\_, 3 =>
        /\
       /  \
      /    \
     /      \
    /        \
   /          \
  /            \
 /              \
/  ____________  \
       |  |
       |  |
       |  |
       |  |
       |  |
       |  |
     /      \
    /        \
___/  ______  \___

\/
\/, 5 =>
\        /
 \      /
  \    /
   \  /
    \/
\        /
 \      /
  \    /
   \  /
    \/

/-/
\-\, 7 =>
      /             /
     /             /
    /             /
   /   -------   /
  /             /
 /             /
/             /
\             \
 \             \
  \             \
   \   -------   \
    \             \
     \             \
      \             \

 _   _
/ \_/ \
| | | |
|_| |_|, 11 =>

           ___________                                 ___________
          /           \                               /           \
         /             \                             /             \
        /               \                           /               \
       /                 \                         /                 \
      /                   \                       /                   \
     /                     \                     /                     \
    /                       \                   /                       \
   /                         \                 /                         \
  /                           \               /                           \
 /                             \             /                             \
/                               \___________/                               \
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |                     |                     |                     |
     |     ___________     |                     |     ___________     |

                       __    __   __             __  ___
  /\  /\    |  |\  |  |     /    |  |     /\    |     |
 /  \/  \   |  | \ |  |--  |     |--\    /__\   |--   |
/        \  |  |  \|  |__   \__  |   \  /    \  |     | , 5 =>

                                                                                __________                    __________               __________                                                                 __________          _______________
              /\                  /\                          |              |  \                |              |                               /                      |              |                               /\                          |                             |
             /  \                /  \                         |              |   \               |              |                              /                       |              |                              /  \                         |                             |
            /    \              /    \                        |              |    \              |              |                             /                        |              |                             /    \                        |                             |
           /      \            /      \                       |              |     \             |              |                            /                         |              |                            /      \                       |                             |
          /        \          /        \                      |              |      \            |              |                           /                          |              |                           /        \                      |                             |
         /          \        /          \                     |              |       \           |              |                        |                             |            \                            /          \                     |                             |
        /            \      /            \                    |              |        \          |              |                        |                             |             \                          /            \                    |                             |
       /              \    /              \                   |              |         \         |              |  ----------            |                             |  ----------  \                        /              \                   |  ----------                 |
      /                \  /                \                  |              |          \        |              |                        |                             |               \                      /                \                  |                             |
     /                  \/                  \                 |              |           \       |              |                        |                             |                \                    /    __________    \                 |                             |
    /                                        \                |              |            \      |              |                           \                          |                 \                  /                    \                |                             |
   /                                          \               |              |             \     |              |                            \                         |                  \                /                      \               |                             |
  /                                            \              |              |              \    |              |                             \                        |                   \              /                        \              |                             |
 /                                              \             |              |               \   |              |                              \                       |                    \            /                          \             |                             |
/                                                \            |              |                \  |              |  __________                   \__________            |                     \          /                            \            |                             |

```

Reference implementation

# Answer
> 9 votes
# APL(Dyalog Unicode), ~~118 114 90 88 83~~ 80 bytes SBCS

```
{⊃,/⍪⌿⍵{' '⍺[⍵]}¨1+(⍺ ⍺∘⍴¨o(⌽o←∘.=⍨⍳⍺)i(⌽⍺/⍺↑1)(⍉⍺ ⍺⍴i←(⌈⍺÷2)=⍳⍺)0)['\/|_- '⍳⍵]}

```

Try it on APLgolf!

A dfn submission which takes a char matrix on the right and a scale factor on the left.

Indexes each character into its specific pattern, and then uses the original matrix to index back into it.

More byte saves can be done by figuring out a formula for getting the boolean arrays.

# Answer
> 8 votes
# C (clang), ~~170 147 143~~  137 bytes

```
a,j,i;f(*m,x,z){for(;*m;m+=x)for(j=z;j--;puts(""))for(i=-1;++i<x*z;putchar((a-92?a-47?a-45?a-95|j:j-~j-z:i%z-j:~j+z-i%z)?32:a))a=m[i/z];}

```

Try it online!

* thanks to @ceilingcat suggestion !
* added for loop instead of recursion
* thanks to @Johan du Toit for suggesting using int\*array as input!

`f(*m,x,z){` function taking:

* m : ~~char~~ int array without newlines
* x : width
* z : scale

~~`m+=x;*m&&f(m,x,z);`~~ =\> `for(;*m;m+=x)`
for every row of input, loop actually better than recursion.

`for(j=z;j--;puts(""))`
we iterate z times every row of input and put \n each time.

`for(i=-1;++i<x*z;putchar(..) )`
we put x\*z characters.

`a=m[i/z]`
we use `a` to save on m\[i/z\] repetitions which is current input being enlarged.

`putchar(( ... )?32:a`
... =\> many nested ternary operators to select proper character based on a and i / j relations which evaluates to 1 or 0 , we then puts a space or `a`.

# Answer
> 8 votes
# V (vim), 311 bytes

```
"aDj:%s:\([ \-_]\):=repeat("\\1",a)
:g
:%s:\\:\\=repeat(" ",a-1)
:g
:%s:/:=repeat(" ",a-1)
/:g
:%s:|:=repeat(" ",a/2)
|=repeat(" ",a/2)
:g
{qqYp:s:\\ : \\:ge
:s: /:/ :ge
qdkG{Go
ggqtjjkk@a@qdd@tq@tggqb@ajk:s:_:Y:ge
j@bq@bi=a/2+1
D@"kkqc:s:-:X:ge
@ak@cq@c:%s:[-_]: :g
:%s:X:-:g
:%s:Y:_:g
gg:s:-: :g

```

Try it online!

Thanks to PyGamer for the idea of solving this in Vim. It's not extremely well golfed, can change some substitutions and bad hacks around the many macros that are in use.

Outputs the required art with two trailing newlines.

# Answer
> 6 votes
# , 89 bytes

```
[(a{~[:,/[:,./"3[*({0:0}(,:|.)@=@i.,/@,~(1,>.@-:)(,:~|:)@|."{1:0},~$0:))~(a=.' _|-\/')i.]

```

Try it online!

# Answer
> 6 votes
# K (oK), ~~261~~ ~~184~~ ~~165~~ ~~163~~ 159 bytes

```
{k:y;v:" ";a:{[g]{(x#v),g,(k-x+1)#v}'!k};h:{[s]{k#s@x=_k%2}'!k};,/{,/'+{$[92=x;a x;47=x;|:'a x;45=x;h v,x;95=x;{k#" _"@x=k-1}'!k;v=x;(k;k)#v;+h v,x]}'x}'";"\x}

```

Try it online!

I lost my sanity several times while creating this. Thanks to ngn and Razetime for helping me with this.

Thanks to Razetime for helping me to golf off a lot.

The basic approach is to split by newlines, replace each character with a list of subrows, take the transpose of that, join each line, and flatten.

# Answer
> 6 votes
# K (ngn/k), 51 bytes

```
{,/,'/'`c$32|x*(a@<a;+a;|=y;=y;a=:|a:y#'!y)8!19!-x}

```

Try it online!

# Answer
> 3 votes
# Python 2, 135 bytes

Takes input as a list of lines.

```
s,f=input()
R=range(f)
for r in s:
 for w in R:print''.join([i-w,i-~w-f,w-f/2,f+~w,i-f/2][ord(c)%23%5]and' 'or c for c in r for i in R)

```

Try it online!

# Answer
> 2 votes
# Charcoal, 55 bytes

```
Ｎθ≔⊘⊕θη↑ＷＳ«Ｊ⁰⁺θⅉＦι¿⁼κ_×θκ«Ｍ⊖η↗≡κ-Ｐ-η/Ｐ/η|Ｐ|η\Ｐ\ηＰκＭ⊖η↘→

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｎθ≔⊘⊕θη

```

Input the scale factor `n` and calculate half, rounded up.

```
↑ＷＳ«Ｊ⁰⁺θⅉ

```

Output each transformed row on its own set of `n` lines.

```
Ｆι

```

Loop through the characters on each line.

```
¿⁼κ_×θκ«

```

If the next character is a `_` then print `n` of them, otherwise...

```
Ｍ⊖η↗

```

Move to the centre of the square.

```
≡κ-Ｐ-η/Ｐ/η|Ｐ|η\Ｐ\ηＰκ

```

Print a line in the desired direction. (TIO's version of Charcoal doesn't support computed multidirectionals, so I'm not sure whether that would beat a switch statement.)

```
Ｍ⊖η↘→

```

Move to the bottom left of the next square.

# Answer
> 2 votes
# JavaScript (ES2020), ~~157~~ ~~151~~ ~~148~~ 147 bytes

Takes a 2D character array `A` and a size `n` as `f(A)(n)`.

```
A=>n=>A.flatMap(L=>(N=[...Array(n)]).map((_,y)=>L.flatMap(c=>N.map((_,x)=>[a=y-n+1,a+y,a+=x,a+x-y]['_-/|'.indexOf(c)]??x-y?' ':c)).join``)).join`
`

```

Try it online!

---

# JavaScript (ES2020), ~~157~~ ~~151~~ ~~148~~ 147 bytes

```
A=>n=>A.flatMap(L=>(N=[...Array(n)]).map((_,y)=>L.flatMap(c=>N.map((_,x)=>({_:a=y-n+1,'-':a+y,'/':a+=x,'|':a+x-y})[c]??x-y?' ':c)).join``)).join`
`

```

Try it online!

---

# JavaScript (ES2019), ~~161~~ ~~158~~ ~~152~~ ~~149~~ 148 bytes

```
A=>n=>A.flatMap(L=>(N=[...Array(n)]).map((_,y)=>L.flatMap(c=>N.map((_,x)=>[a=y-n+1,x-y,a+y,a+=x,a+x-y]['_\\-/|'.indexOf(c)]?' ':c)).join``)).join`
`

```

Try it online!

# Answer
> 2 votes
# Haskell, 97 bytes

```
n%a|z<-[1-n,3-n..n]=[do c<-r;x<-z;max" "[c|(l,0)<-zip"|_/\\-"[x,y-n+1,y+x,y-x,y],c==l]|r<-a,y<-z]

```

Try it online!

I/O: `size%listOfLines` is a new list of lines.

# Answer
> 1 votes
# PowerShell, ~~162~~ ~~152~~ ~~149~~ ~~143~~ 138 bytes

```
param($k,$o)$o|%{$l=$_;1..$k|%{$y=$_
-join($l|% t*y|%{$c=$_;1..$k|%{" $c"[@{1=$y-$_+$k+1
8=$_+$y
7=2*$_
6=2*$y
4=$y+1}[$c%13]-eq$k+1]}})}}

```

Try it online!

Less golfed:

```
param($k,$origLines)
$origLines|%{                           $line = $_
    1..$k|%{                            $y = $_
        -join($line|% toCharArray|%{    $char = $_
            1..$k|%{                    $x = $_
                $rasterFont = @{
                    1 = $y-$x+$k+1                      # \
                    8 = $x+$y                           # /
                    7 = 2*$x                            # |
                    6 = 2*$y                            # -
                    4 = $y+1                            # _
                }
                " $char"[$rasterFont[$char%13]-eq$k+1]  # space or $char
            }
        })
    }
}

```

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


title: How many dominoes can you fit here?

text:
# Question
Title: How many dominoes can you fit here?
Much harder than Can this pattern be made with dominoes?

## Challenge

A grid of width \\$w\\$ and height \\$h\\$ is given, filled with 1s and 0s. You can place a domino somewhere on the grid only if both cells are 1. You cannot overlap dominoes. What is the maximum number of dominoes you can fit in the given grid?

**The worst-case time complexity should be \\$\mathcal{O}(w^2h^2)\\$ or lower.** Please include an explanation of how your answer meets this time complexity requirement. If you use a built-in to solve the problem, you should provide an evidence that the built-in meets the time complexity bound. (Note that "being polynomial-time" is not sufficient.)

At least two well-known algorithms can be used to meet the bound: Ford-Fulkerson and Hopcroft-Karp. More specialized algorithms with even better runtimes also exist.

You may use any two consistent values in place of 1 and 0 in the input. You may assume that \\$w\\$ and \\$h\\$ are positive, and the input grid is rectangular.

Standard rules apply. The shortest code in bytes wins.

## Test cases

The test cases use `O` for 1s and `.` for 0s for easier visualization. The last two cases are of sizes 50×50 and 70×70 respectively; as an empirical measure, your solution should not take more than a few seconds to compute the result for these inputs (on a typical desktop machine, less than a second for fast languages; 70^4 ~ 24 million). But note that being able to solve these inputs is NOT a guarantee of being a valid answer here; as mentioned above, you need to explain how your answer meets the time complexity bound.

```
O..
OO.
OOO  => 2

..OOOO..
.OOOOOO.
OOO..OOO
OO....OO  => 9

OOOOOOOOOOOOOOOO
O.OOO.OOO.OOO.OO
O..OOO.OOO.OOO.O
OO..OOO.OOO.OOOO
OOO..OOO.OOO.OOO
OOOO..OOO.OOO.OO
O.OOO..OOO.OOO.O
OO.OOO..OOO.OOOO
OOO.OOO..OOO.OOO
OOOO.OOO..OOO.OO
O.OOO.OOO..OOO.O
OO.OOO.OOO..OOOO
OOO.OOO.OOO..OOO
OOOO.OOO.OOO..OO
O.OOO.OOO.OOO..O
OO.OOO.OOO.OOO.O
OOOOOOOOOOOOOOOO  => 80

....OOO..O.OOOOO..OOO.OOO
OO.OOOOOOOO..OOO.O.OO.OOO
OOO.OO.O.O.OOOOO...OO.OO.
.O..OO.OO.OO.OO.O..OOOOOO
O.O.O..OOO..OOO.OOO.O.OOO
O.OOOOOOOOOOOOOO.OO..OOO.
OOOOOO.O.O.OOOOOOOOOOOOOO
O.O.O.OO.OO.O..OO..OOOOOO
O.OOOO.O.OOO.OOOOO.OOOOOO
..OOO..OO...OOOOOOOOOOOOO
.O..OO.OOOO.OO.O..OOOOOOO
O.OOOOOO..OO...OOO.OOOOOO
.OO....OO.OOOOO.OO.OOOOOO
OOOO.OOO.O..OOO.OOOOO...O
...OOOOOO.OOOOOOO.OOOOO.O
O..O.OOOOOOOOOOOOOOOOOOO.
OOOO.O.OOOOOOO..O..OO.O.O
..OOOOOOOOO.OOOOO.OOOO.O.
O.OOOOOOO...OO..O.OOOO.O.
OOO.O.O..OOOOO.OOO.OOO..O
.OOO.OOO.OO.OOO.O.OOOOO..
O.OO..OO..O.....OOOOOOOO.
..OO.O.O.OO.OOO.O.OOOO.O.
OOOOO.OO..OO...O...O.O.OO
O..OOOOOO.O..OOOOO.OOOOO.  => 197

O.O..O.OOOO.OOO..OO.OOOOOOOO.OO...OO.O.O.OOOOOOO.O
OOOO...OOOO..O..OOO.....O..OO.....OOO..OO..OOO.OOO
.OOO..OOOOOOO....O.OOOOO..OO.O..OO.OOO.OO.O.O.OOOO
OOOOO..O...OOOOOOO.O.O....O..O.OOOOOOOO.O..OOOOO.O
OOOOOOO.O.OOOO.OOO.O.O.OO..OOOOOOOOOOOOO.OOOOOOOO.
OO.OO.OOOOO.OO..O.OO.OOO...O.OO.OOOO.OO.OO.....OOO
OOO.OOO.OO.OO...O.OOOOO..O.OOOOOOO.O..O..OO.OOOO..
OOO.O.OOO.OOOOOO.OOOO.OO.OOO..OOO..O.OOO.OO.OOOO..
OO..OOOO.OOOOO.OO..O.OOOOOOOOOOOO.O..O.O.OOO.O.OOO
.OOOO.O.O.O.OOOO.OO.O..OOO..O.O.OOO..OOOOOOOOO..O.
O..O.OOOO.OOOOOOOOO..O..O.O.OOOOOOO...O.OO...O....
OOO...O..OOOO.O.O..OO.O..O.OO..O.OOOOOOOOO..OOOOO.
OOO.OOOO.OO.OO.O..O..OOO..OOOOO.OOO..OOO..OO.OOOOO
O....O.OOOOOO.OOO..OOOOOOOOOOO.O.OOOOOOO.OOO.OOO..
..OOOO..OOOOO..O..O.OOOOOOOOO.OOOOO..OOOOO.OO..O.O
O.OOOO..OO..OOO.OO...OO.OO.OO.OO..O.OO.O.OOOOOO.OO
.OO.O....O..OOOOOOOO.O......O.OO.OO..OOOOO.OOOO.O.
OOOOO.O.OOOOOOO......OOO.O.O.OOOO.OOO.OO.OOOOO.O.O
..O.OO..O.O...OOO.OOOO..OO.OOOO.OOOO.OOO.OOOOOOO.O
OO.OOOOOO...OOO.OOOOOOOOOOOOOOOOOOOO.O...O.O..OO.O
O...O.O.O.OOOO.O.O.O.OO.O...OO..O.O.OOO.O..O.O.O..
OO.O.O.O..OO.O....OOOOO..O.O..OOOO.OOO.OOOO.OOOO..
OOOOOO.OOO.O..OOO..OOOO...OOO.OO.OOOOO.OOO.OO.OOO.
.O..O.O..OOO..O.OO.O.OOOO.O..O..OOOOOO.O..O..O...O
.OOOO.O..O.O..O.OOO.OOO.OO.OOO.O.O.OO.OOO.O..OOO.O
OO.OO...O.OOOOOOOO.OOOO..O.OOOOOO.OOO.OO..OOO.OOOO
OO.O.O..OO..O...O.O.O.OOOO..OO.OOOO.OOO.OO.O..OOO.
OOO....OO.OO..OO.O.OOOO..O.O..OO..O.O.OOOO..O.O..O
..O.OOO.OOOO...OO.OOO..O.O.OO.OO...OOOO.OO.OOO.OOO
O.OOOOOO.O.OO.OOOOOO..OOO.O.OOO.OO..O.O.OOOOOO.O.O
O.OO....O..OOOOO..OOO.O.OOOOOOOOO..O.O..OOOOOO.OOO
.OOOO..OOOO..OOOOO.OOOOO.OOOOOOOOOO..O..OO.OO..O.O
OO.OOOOOO..O.OOOOO..O....OO.OOO.OOO.O.O.OO..OO....
OO.OOO.OOOOOOOOO.O.OO..O.OOOO.OOO.OO.OOOOO...O.O.O
OOOO..OO.O.O.OO.OOOO..O....OOOOOOO.O..O.O.OOO.O.O.
OOO.O.OOO.O.OO..OOOO...OOOOOO.O....OOOOOO.....O..O
OOOO.OOOO.O..OOO...O...OOO.OO.OOOOO..OOOOOOOOOO.O.
..OOOOO..OOO.O..O..OOOO.O.O.OOOOOOOO...O..OO.O..OO
OOOOOO.OOO.O..O.O.OOO...O.O.O..O.O..O.O..OO.OOOOOO
O.OOOOOOOO.O...O..O.O.OOOOOO.O.OO.OOOOOOOOOOOO..OO
O.O.OOOO...OOO.OO.OOOO.OO.O...OO..OOOOOOO.OOO.O.O.
.OO.O..OO.O.OOO.OOO.OO.OOO..OOOOO...O.O..OO...O...
..OOO..O.OOO.OOOO...OOO..OO.OO..O.OO.OOOOOO.O.O.O.
.OOOOO.O..OO.O.OO...O.OOOOOOOOO.OOOOOOO.O.OO.OOOOO
OOO..OO.OOO.OO.OO....OO.O.O.OOOO..O..OO.O..OOOOOO.
..O.OOO...O.OOO.OOOOOOOOOOO...OO.O.OOO.O..OOOOO.OO
..O..OOOO..O...OOOO.OO...O..OO.OO.OOOOO..O.O.OO...
.OOOOO.OOOO.O..OOO.OOOOOOOO....OO.OO.O....O.O..O.O
O.OOOO.O.O.O.O.OOOOOOOO.OOO.OOO.O....OOOOOOO..OOOO
OOOOO.OOOOOOO..OOO.OO.OOOOO.OOOOOO.O.O.O.OOOOO.O.O  => 721

..O.O.OOOO..O.OOOOOO.O.OOOO.O.OO.O.O..OOOOOOOOO.OO.O.OO..O.OOOOOO.O..O
O.OOOOO.OOOOOOO.O.O.OOOOOO..OO.O.OO.....OO.OOOOOOOO.OOOOOOOOO.O..OOO..
OOOOO.OOO.OOO.OO.OOOO..OO.O.OO.OOO.OOOO..OOOOOOOOOO...OO.O..OOOOO.OO.O
.O...OOO...OOO.OO..OO.OOOOOOOOO.OOOOOOOOOOO.O..OOOOOOOOOOOOOOOOO.OO.OO
OO.OO.O.OOOOOOOO.OOO.OO.OOOO.O.OOO.OOO.OOOOO.OOO..OOOOO....O.O.OOO..O.
OO..O.OOOOOO..OO..O..OOO..OO.OO.OOO...OO..O.OOO.O....O..O.OO..OOO.OO.O
OO..OOO..OOOOO.OOOO.O..OO.O.OOO..OOO..O.OOO...OO.OOO..OOOO.OOO.OO.OOO.
OOOOO.OOOOOOOO.O...OOO..OOOO.OOO.O.O.OOO..OOOOO..O.OO.OOOOO......O.OOO
OOOOOO.OOOOO.O.O.OOOOOO.OOOOOO.OOOO.OOOOO.O...OOO.OO..OOOOOOOOOOOOOO.O
OOOO.OOOO...OOO..OOOO.OOOOOOOOOOO.O..OOOOOOOO.OOOOOOO.OOOOOOOOOOOOO.OO
OOOO.OOOOO.OOO.OOO..OOOO..OOO..O..OO.OOOOO.OOOOOOO..OO.OOO...OOO.OOOOO
.OO..O.O.O.O.OOOOOOO.O.OOOOOOOO....O.OOOOO.OOOO.O..OOOOOO..OO.O.O.O.OO
OO..OO.OOOOOO.OOOOOO..OOOOOOOO..OOOOOOOOO.O.OOOO....OOOOO.OOO..O.O...O
O.O.OOOO.O..OOOO.OOOOOO..OOO...OO.O.OOOO.OOOOOO.OO.O..OOO.OOOOO...OOOO
O..OOO.O.OO...O..O..O.OOOO.OOOOOOOO...OOOO...OOO..OOOOOO..OOOOO..OOOOO
OOOO.OOOOO.OOOOO.OOOOO.O..O.OO..O.O.O..O..OOO...O.O.OO.O.O..OOOO.OO..O
OO..OOO.OO...OO..OO.O.OOOOO.O..OOOOOOO..O..OOO.OOO.O..OOO..OOOOO...O.O
.OOOOOOOOO.OOOOO...OOOO..OOOOOOO.OO..OOOOOOOO..OOOO..OOOOOOO...O.OO.OO
.OOOOO.O..O.O.O.O.O...OO..OO.OOO.OOO.OO.OOO...O.O..OOOO.OOOOOOOOOOO.OO
O.OOO.O...OOOO..OOOOOOOO.OOO.OOO.O.OOOO.OOOOOO.O.OO.OO...O.OO.OO..O..O
.OO.O..OOOOO..OOOOOOOO.O.OO.OOO.OO.O...O..OOO.O.OOOO...OO..OOOOOOOOO.O
..OO.OOOO.OO.OO..OO.OOOO..OOOO.OOOOO.OOO.O.O.OO..OO.O.O.OOO.OOOO..OO.O
OOO..O.OOO.O.OOOOOOOOO.OOO.OOO.OOO.OOO.OOO..OO.O.OOOO.OO.OOOOOOOOOO.OO
O...OOOOOOO..O.OO.OO...OOO.O...OO.OOO.OOO..OO..OO..OO.OO..OO..OOOOOOOO
..OOO.O..OO...OOOOO...OOO.OO...OOOO.OOO.OO...O...O.OOOO..OOOOOOOO.OOOO
O..OO..OO.OOO.OOOOOOOO.OOOOOOOOOOOOO..OOOO.O.O.OO.....O..OOO..OO.OOOO.
..OO.OOO.OO.O.O.OO.OOOOOOO.O...OOOOOO.OOO.OOO.O.OO.OOO.OOO.OOO..OOOOOO
OO.O..OO.....OOOOO..OO.OOOO.OOOOOO.O.O.O.O..OOO.OOO.O....OOO.OO..OOOOO
O.OO.O.O.OO.OOOO..OOOO..OO.O.OOOO.OOOO.O..O.OOOO.OO.O....OO..OO.O.OOOO
O..OOO.O...O.OO.OOOOO.....OOOOOOOOO..O.OOO.O.O.OOOOO..O.OOOO....OO..OO
.OOOOO...OOOO..O.OOO.OO.OO.OOOO.OOO.OOOOO.OOO...OOOOO.OOOOOOOO.OOOO..O
O...OOOOO..OOO.......O.OO...O.OOO...OOOOO..OOO..OOOO.OO.OO.O...OOO..OO
O.OOO..OO..OO..OOOOOOOOOOOO.OO.OO.O.OOOO...OO.O.OO..OOO..O...OOO..OOO.
..O.OOOO.O...OOOOO.OOOO.OOOOOO..OOO..OOOO.OO...O.OOO..OO.O..OO.O.OOOOO
..OOO..OOOOO.OOOOOO.OO.O..OO.O..OO.OO.OOOO.O.OOO.OO.OOOOO.O.OO.OOO.OOO
OOO.O.O.OOO.OO.OOOOO.OOO.OOO.O..OO.OO..OOOOOO.OOOOO.OO.OOOOOO....O.OOO
O..O.O.O.OOOO.O.O..O.OOOOO.O.OOOO.OO.OOO..O.OOOO.O.O..OOO.OO..OO..OOOO
OOOO.OOOOO...O..OO...OO.OO.OOO...OOOOOOOO...OO..O...OOOO..O.O...OO.OOO
OOOOOOOOOO.O.O.OO.OOOOOO.OO.OO.OO.O.O.O.O.OOO..OO.OOO.OOO.O..O.OOO..OO
.O.OOO.O.OOOOOOOO.O.O..OOOOOOOOOO.OO..OOOOOO.O.OOO..OOO.OOO.OOO..OOOOO
.O.O.O.OOOO.OOOO.OOOOO.OOOO..OO..OO.O.O..OOO.O..OO.OOOOOOO.....O.OOO.O
OO..O.O..OOOO.OO.OOO.OOOOOO...OOOOO.OOOOO..O.O.OOOO..O.OOOOOOO.O....O.
O.OO.O.....OOOOOOO.OOOOOOO.OO.O.OOOOOO.OOOOOO.OOOO..OOOOOO.OOOOOO..OOO
OOOO.OO.O.O.OO..OO.O..OOO.OOOOO.OOO..OOO...OO.OO..O.OO.OO.OO.OOOOO.O..
..OOOO.O..OOOOOOOO..OOO..O.OO.O.OOO.O.OOO.OO..OOOO.O.OOOO.O.OOOOOOOO.O
OOOOOOOOOOOO.OOO..OOOO.O.OOOO..OOOOOOO.OO.OOOOOOO.OOOOO...OOOOOO.OOO.O
OOO.O.OO....O...OOOO.OO..OOO..O.O.O...O.O.OO.O..OOOO.OOOOOOOOOOOO.OOO.
.OO.OOOOOO..OOOOOO.OOOOO..OO.OOOOOOOO.O.OO..OO.OOOOO.OOOOOOOO.OOOOOO.O
OO.OO..OO.OO.O.OOO..O...O..OO.O...O.O.O.O.OO..OO.OO.O...OOOO.OOO.O..O.
OO..O........OOO...OO.OOOOOOOO..OOO..O..OOO.OO.O.OO.OOO.OOOOOOO..OOOOO
.O..OOO...O.O.OO..O..OOOOOOOOOOOOOOO.OO....O.OOOOO...OOOOO.OOOOOO.OO..
OOO.O..OO.OOO.OOO.OOOO.OOO..OOO.O.OOOO..OOOOO.OOO.O.O...OOOOOOOOO.O...
.OOO.O..OOO.OO...OO.OOOOOOOOOO.O.OOOOOOO..OOO.O..OO.OOOO.O...OOOO....O
OO.OOOOO.OO.O.OO.OOOOO.OOOOOOOOOOOO...O.O.O...O.OOO.OOO.O..OO..OOOOO.O
OOO.O..OO..OOOO..OOOO...OO.O.OOOOOO..O..OO.OOOOO.OOOOOO.O.OOO..OOOO.OO
OOO.O.OOO....O.....O...OOOO..O.O.O.OOO.O.O.OO.OO.OO.O.O..O.OO...OO.OO.
OOO.OOO.OO.O.OO.O.O.O.O..O..OO..O..OOOO.OOOOO.OO.OOOO..OOO.O....OOOOO.
.OOOOOOO..OOO.OOOO.OO..O.O..OOOOOOOO.OO.OO.O...OOO..O.OO.OOOO.OOO.....
OOOO.OO.OOO.O.OOO...O.O..O.OOOOOOO.OOOOO.O.OO.O.OOOOO...OOOOO.OOOOOO.O
OOOO.OO..O..OO..OO.OOOOOOO.OOOOOOOOOO.OO....OOOOOOOOO.OOOO..OO..OOOOOO
O.OO.OO.OOO.O.OOO.OO...OOO.O.OOO.O.O.OOOO.O.OOO.O.O.OOO.OOOO.OO.OO.O.O
O..O.OOOOOOO..OO.OOO.OO..OOOO..O...O.OOOOO.OO......O..OOOO..OOOO..OOO.
.OOO.O.OOO.O...OO.OOOOO..O..OO.O.OO..OOOO.OOOO.OOO..OOOO..O...O...OOOO
O.OO.OOOO.O.OOOO.OO.OO..O..OO.OOOO.O.OOO.OOOOO.O.O.O.O.O.O.OO.OO.....O
.OO.OOO.O.OOOOOOOOOO.OOO..OO.O..OOOO...OOO.O.O.OOOO..O.OOOOOO..OOOOOO.
OO.OOOO.OOOOOO.OOOOOOOOO.OOO..OOOOOO.OOOO...OOOO.O..O..OOOOO.OOO.O.O..
O.OOO.O.OOO.O..OOOOOOOO.OOO..OO..OO..O...O....O.OOO.OO...OOOOO...OO..O
...OOOOOOOOO.O....OOOO.OOOOOO.OO.OO.OO...OO.OO..OO.O.OO.O.OOO.OOO.O...
.O..OOOOOOO..OO.OO..O.OOOOO.OOOOOOOOOOOOO.O.O.OOO.OO.OOOOO..OOOOOO..OO
O.OO....O....OOO.O.O..OO.O..OO...OOOOOOO.OOOOO.OOOO.O.O.OOOO.OOOOOOOO.
=> 1487

```

# Answer
> 10 votes
# Python 3.8 (pre-release), 544 bytes

```
I=float('inf')
def f(g,e=enumerate):
 a={(x,y):[(X,Y)for X,Y in[(x-1,y),(x+1,y),(x,y-1),(x,y+1)]if len(l)>X>-1<Y<len(g)!='O'==g[Y][X]]for y,l in e(g)for x,c in e(l)if'O'[:x+y&1]==c};R={};S={};D={};Q=[];m=0
 def F(u):
  if not u:return 1
  for v in a.get(u):
   if D[(p:=S.get(v))]==D[u]+1and F(p):S[v]=u;R[u]=v;return 1
 while D.get(N:=None)!=I:
  for u in a:k=u in R;D[u]=[0,I][k];Q+=[u]*-~-k
  D[N]=I
  for u in Q:
   if D[u]<D[N]:
    for v in a[u]:
     if D[(p:=S.get(v))]==I:D[p]=D[u]+1;Q+=p,
  for u in a:m+=u not in R!=N!=F(u)
 return m

```

Try it online!

Picture a checkerboard pattern on the grid. I apply a poorly-golfed Hopcroft–Karp to the bipartite graph obtained by connecting `O`s on "light squares" with those on "dark squares". A domino placement is a matching of this graph; the "maximum cardinality matching" found by the algorithm is the amount of dominos that can be placed.

In the worst case, there are \\$O(wh)\\$ edges and \\$O(wh)\\$ vertices, and Hopcroft–Karp promises to be \\$O(E\sqrt{V})=O(w^{1.5}h^{1.5})\\$.

# Answer
> 6 votes
# Jelly, ~~216~~ 199 bytes

```
ñ4ñ3ñ1Ɗ=¥Ƈñ1‘$⁸;ⱮḢ;U$3ịḢ}⁺¦⁹$2¡Wʋ3¦ɼ$02ịñ3ß1Ẹ?Ʋ?ȯƊẸaŒḊ2ƑƲ¿Ẹ
ịị®$}
FJṁ×⁸Z,$ṖŻż"ḊƲ€Z,¥/Ẏ€;"/×¹Ƈ¥"ŒJ§ḂƊaFƊ0€,$ṫ-;1aL$,¬ȧ"Tɗʋ/;©$2ịḢç4ç3ç1=®ẈḢ¤ƊƇW;¹ƇƊƲ;ç1‘$Ṫ}Ḣ}¦;¹¹4ƭ€ɼƲ®0;ç1$>/Ʋ?ƲẠ¿ƊT€ṪçÐḟ3Ñ€Ʋṛ®ƲÐL3ịTLH

```

Try it online!

A full program that takes a binary matrix and prints an integer. This generates a bipartite graph and then uses the Hopcroft-Karp method; it’s loosely based on the pseudo code on the Wikipedia page, but obviously has to stick within what’s possible in Jelly. I think it should meet the complexity requirement since the underlying method does, and manages to complete all challenges within about 28 seconds total on TIO.

# Answer
> 2 votes
# Charcoal, 140 bytes

```
ＷＳ⊞υιυＦＬυＦＬ§υι«Ｊκι¿⁼ＫＫO«≔⟦ω⟧θＷθ«≔Φurdl№⪪α¹⊟ＫＤ²✳μλ¿λ«≔§λ⁰λ✳λλ≔ＫＫηＰ§dlur⌕urdlλ¿⁼ηO≔⟦⟧θ«Ｍ✳η⊞θη⊞θＫＫ»»«≔⊟θλ¿λ«✳λ↧λ✳ＫＫ↧⊟θ»O»»ＵＭＫＡ↥λ»»≔ΣＥRD№ＫＡιθ⎚Ｉθ

```

Try it online! Link is to verbose version of code. Counts the 197 dominoes in 5 seconds and the 721 in 30 seconds which means that the 1421 is just too slow for TIO. Explanation: Most of this is simply my answer to Can this pattern be made with dominoes? but the two changes are that the code doesn't crash when it fails to place a domino and it counts the number of dominoes and outputs that as the final result.

---
Tags: code-golf, grid, restricted-complexity, binary-matrix, dominoes
---


title: Reverse cadaddadadaddddaddddddr

text:
# Question
Title: Reverse cadaddadadaddddaddddddr
The Lisp language has a family of functions `car`, `cdr`, `cadr`, etc for accessing arrays. For each one, an `a` defines taking the first item of an array, and a `d` defines taking the rest.

For example, running `cadr` on `[[1,3,4],5,7]` will return `[3,4]` as the `a` gets the first item (`[1,3,4]`) and the `d` removes the first item.

We've already had a challenge regarding running a `cadaddadadaddddaddddddr` on a list, but what about the reverse?

Your challenge is to, given a string of the type above (starting with a `c`, ending with a `r`, with only `ad` in the middle), and a single value, create an array such that running the string as a `cadaddadadaddddaddddddr` on the array returns said value.

For example, given the input `cadar, 1` a possible output could be `[[0,[1]]]` since running `cadar` on that gives 1.

# Scoring

This is , shortest wins!

# Testcases

These are possible outputs, all that matters is that your program returns an array which works for the condition.

```
car, 3 => [3]
cdddar, 5 => [0,0,0,5]
cadadadadar, 4 => [[0,[0,[0,[0,[4]]]]]]
caaaaaaaaar, 2 => [[[[[[[[[[2]]]]]]]]]]

```

# Answer
> 14 votes
# Python 2, 40 bytes

```
f=lambda s,*l:s[3:]and f(s[1:],l,*l)or l

```

Try it online!

Doesn't bother telling car from cdr. Instead, makes a big nested tuple where every path ends at the right value, assuming it has the right length and ends in `a`. For example,

```
f("cdddar", 5) = ((((5,), 5), (5,), 5), ((5,), 5), (5,), 5)

```

is the same as `f("caaaar", 5)` or `f("cdadar", 5)`. So, only the length of the input string matters.

This is done by repeating the transformation `l -> (l,*l)`, which puts `l` as both the car and cdr of the new tuple. This happens once for each character in `s` except the first three, starting from a singleton of the input value.

# Answer
> 6 votes
# 05AB1E, 11 bytes

```
RA"¸  Ć"‡.V

```

Try it online!

```
R             # reverse the input
 A            # push the lower case alphabet
  "¸  Ć"‡     # transliterate, replace:
              #  - "a" with "¸" (wrap)
              #  - "c" with " " (noop)
              #  - "d" with "Ć" (enclose, append the first value)
         .V   # evaluate as 05AB1E code, the leading r reverses the empty stack

```

---

Porting xnor's construction comes in at 5 bytes:

```
g<GDš

```

Try it online!

# Answer
> 5 votes
# Vyxal, ~~10~~ 9 bytes

```
(nH₂[w|⁰J

```

Try it Online!

Wow, using hexadecimal conversion actually helped save a byte. Exits with an error, but outputs the required list wrapped in a list.

## Explained

```
(nH₂[w|⁰J
(          # for each character `n` in the remnants:
 nH        #     convert to hexadecimal
   ₂       #     is that divisible by 2?
    [      #     if so:
     w     #         wrap the TOS in a list ([TOS])
      |    #     else:
       ⁰J  #         join the TOS and the next input

```

# Answer
> 4 votes
# , 47 41 bytes

```
4 :0
".'y',~(}.}:x)rplc a`,:`d,<'(,{.)'
)

```

Try it online!

* `(}.}:x)` Kill the c and r
* `rplc a`,:`d,<'(,{.)'` In what remains, replace `a` with enlist `,:` (another nesting level) and replace `d` with `(,{.)` (append first element)
* `".'y',~` Evaluate the resulting verb on the right arg `y`

# Answer
> 4 votes
# Ruby, 48 bytes

```
f=->s,n{s[0]='';s<?r?s>?b?[0]+f[s,n]:[f[s,n]]:n}

```

Try it online!

# Answer
> 2 votes
# Charcoal, 23 bytes

```
Ｆ⮌η≡ιd≔⁺⟦⁰⟧θθa≔⟦θ⟧θＰ⭆¹θ

```

Try it online! Link is to verbose version of code. Explanation:

```
Ｆ⮌η≡ι

```

Loop over the `cdadadr` string in reverse and switch on each character.

```
d≔⁺⟦⁰⟧θθ

```

If it's a `d` then prepend a `0`.

```
a≔⟦θ⟧θ

```

If it's an `a` then wrap the value in a list.

```
Ｐ⭆¹θ

```

Stringify the final result. (For some reason, outputting using Charcoal's default output format produces a meaningless result.)

# Answer
> 2 votes
# Jelly, ~~9~~ 8 bytes

```
W;$L}¡ḢḢ

```

Try it online!

Based on xnor's idea.

*-1 byte thanks to Jonathan Allan*

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


# Question
Title: Calculate the integer square root of a matrix
Let \\$A\\$ be a square matrix that is at least \\$2 \times 2\\$ where each element is an integer. \\$A^2 = A \times A\\$ will then have the same dimensions as \\$A\\$, and will have integer elements. For example, let

$$A = \left\[ \begin{matrix} -3 & 2 \\ 0 & -1 \end{matrix} \right\]$$

Therefore,

$$\begin{align} A^2 & = \left\[ \begin{matrix} -3 & 2 \\ 0 & -1 \end{matrix} \right\]^2 \\ & = \left\[ \begin{matrix} -3 & 2 \\ 0 & -1 \end{matrix} \right\] \times \left\[ \begin{matrix} -3 & 2 \\ 0 & -1 \end{matrix} \right\] \\ & = \left\[ \begin{matrix} -3 \times -3 + 2 \times 0 & -3 \times 2 + 2 \times -1 \\ 0 \times -3 + -1 \times 0 & 0 \times 2 + -1 \times -1 \\ \end{matrix} \right\] \\ & = \left\[ \begin{matrix} 9 & -8 \\ 0 & 1 \end{matrix} \right\] \end{align}$$

---

Given an \\$n \times n\\$ matrix \\$B\\$ consisting only of integer elements, output any \\$n \times n\\$ integer matrix \\$A\\$ such that \\$A^2 = B\\$. You may optionally take \\$n\\$ as an input, and you may assume that you'll only have to handle matrices for which there exists such an \\$A\\$.

You may take input and output in any convenient format and method. This is so the shortest code in bytes wins.

## Test cases

The outputs given below are not necessarily the only valid outputs

```
[[8, 96], [-84, -40]] -> [[-8, -8], [7, -4]]
[[18, 63], [14, 67]] -> [[0, 9], [2, 7]]
[[9, 0], [-10, 25]] -> [[3, 0], [5, -5]]
[[25, -58, 57], [0, 7, -4], [0, -24, 31]] -> [[5, -7, 5], [0, -1, -1], [0, -6, 5]]
[[12, -33, 42], [16, 19, 20], [-90, 18, 63]] -> [[6, -3, 3], [2, 5, 1], [-6, 0, 9]]
[[33, -80, 86], [72, 57, -13], [-88, 40, 44]] -> [[-8, 7, -3], [-1, 0, 8], [8, 8, -2]]
[[88, 8, -72, 65], [-12, 45, 17, 33], [-27, 21, 36, 31], [5, 40, -53, 119]] -> [[-5, -4, 3, -9], [-6, 0, 0, 7], [-5, 5, -4, 7], [-6, 3, 5, -3]]
[[45, 39, -25, -17, 61], [29, 69, -15, 2, 45], [42, 51, 7, -28, 67], [27, 65, -25, 7, 25], [-66, -61, 9, 63, 1]] -> [[9, 7, -3, -9, 3], [3, -3, 5, -8, -2], [5, 3, 5, -9, 2], [3, -2, 2, -8, -4], [-5, -4, 0, 7, 6]]
[[150, -73, -37, -40, -43, 119], [-62, 191, 95, -87, -10, -88], [-31, -32, -64, 137, 82, -54], [22, -81, 32, 24, 46, -149], [-5, -16, -6, 42, 63, -23], [106, -160, -115, 25, 20, -5]] -> [[8, -8, -3, 5, 6, 3], [-7, 6, 8, 5, 6, -4], [5, 1, -1, -7, 1, -9], [0, 9, 6, -8, -2, 9], [4, 3, 2, -1, -3, -2], [7, -7, 2, -5, -4, 1]]
[[146, -37, -60, -38, 30, -8], [71, -42, -33, -26, -15, -55], [-39, -74, 2, -46, -19, 31], [42, -136, -46, 19, -41, -3], [61, 23, 12, -8, 37, -59], [-73, -13, 88, 90, -71, -11]] -> [[4, 7, -2, -4, 4, -1], [8, -1, -3, -6, 2, 4], [-9, 5, -2, 6, 1, 3], [-7, 6, 1, -5, 4, 3], [5, -8, -8, 2, 3, -4], [-8, -8, -1, -4, -6, -2]]

```

# Answer
# Haskell, ~~98~~ 96 bytes

```
s a=[x|m<-[1..],x<-q(q[-m..m]a)a,a==[foldr1(z(+))$z(map.(*))r x|r<-x]]!!0
q=mapM.const
z=zipWith

```

Try it online!

The relevant function is `s`, which takes as input a matrix `a` as a list of lists of integers and returns a square root of `a` in the same form.

The matrix multiplication part is taken almost verbatim from xnor's answer to this challenge.
> 8 votes

# Answer
# WolframLanguage (Mathematica), ~~54~~ ~~52~~ 45 bytes

```
Last@Solve[(q=s~Array~{#,#}).q==#2,Integers]&

```

–2 bytes from ovs.

–7 bytes due to reading the directions and realizing I can take *n* as an input.

Try it online! \[The request exceeded the 60 sec time limit, so it could only solve the first eight of the ten test cases.\]

How it works:

```
q=s~Array~{#,#} //creates a dummy-indexed matrix with dimensions equal to *n* , calls it "q"
Solve[(q=s~Array~{#,#}).q==#2,Integers] //Solves q.q=#2 for q, where #2 is the input matrix, restricting the solutions to matrices with integer elements
Last@... //since there can be multiple solutions, this selects  the last one (the first ones contain conditionals)

```

Here I leaned heavily on the OP's allowance that output could be in "any convenient format", since the above code specifies the solution matrix in terms of its indexed elements, i.e., s\[*row*, *column*\]. For example:

For 3 additional bytes (48 total), a nicer output can be obtained with a small modification of the code offered by att in the comments:

```
(q=s~Array~{#,#})/.Last@Solve[q.q==#2,Integers]&

```
> 7 votes

# Answer
# Jelly, 17 bytes

```
FAṀŒRṗLƲṁ€ðæ*2iị⁸

```

Try it online!

It's been over a week, so I figured I'd reveal my brute-force Jelly approach. This makes the following assumption, which I haven't managed to prove, but can't find a counter example:

> Let \\$B\\$ be the input \\$n \times n\\$ matrix, and \\$A\\$ be an \\$n \times n\\$ matrix such that \\$A^2 = B\\$
>
> Let \\$b = \max\\{|B\_{ij}|, 1 \le i,j \le n\\}\\$ i.e. the largest absolute element of \\$B\\$. This answer assumes that, assuming \\$A\\$ exists, there is at least one matrix \\$A\\$ such that all its elements are in the inclusive range \\$\[-b, b\]\\$
>
> For example, for $$B = \left\[ \begin{matrix} 9 & -8 \\ 0 & 1 \end{matrix} \right\]$$, \\$b = 9\\$ and there exists at least one \\$A\\$ such that all elements are between \\$-9\\$ and \\$9\\$ (the example in the question, for example)

## How it works

```
FAṀŒRṗLƲṁ€ðæ*2iị⁸ - Main link. Takes B on the left
F                 - Flatten B
 A                - Absolute values of each.
       Ʋ          - Last 4 links as a monad f(abs(flat(B)):
  Ṁ               -   Maximum
   ŒR             -   Bounced range; [-max, +max]
      L           -   Length i.e. number of elements of B
     ṗ            -   Powerset
         €        - Over each list:
        ṁ         -   Mold it like B
                    Call this list of matrices M
          ð       - Begin a new dyadic chain with M on the left and B on the right
           æ*2    - Matrix square of each matrix in M
              i   - Index of B in M
                ⁸ - Yield M
               ị  - Index back into M

```

One byte longer is a slightly more conventional way of extracting the root:

```
FAṀŒRṗLƲṁ€æ*2⁼ɗƇ⁸Ḣ

```

Try it online!

Here, the dyadic filter `æ*2⁼ɗƇ` means that it would save a byte over the dyadic chaining with the indexing. However, as we should only output one solution, and the  would chain to the filter without either  or `¹`, the indexing here actually saves a byte.
> 4 votes

# Answer
# Julia 1.0, ~~109~~ 100 bytes

```
I=Iterators
m%n=for i=I.countfrom(),j=I.product(fill(-i:i,n^2)...)
r=+m;r[:].=j;r^2==m&&return r end

```

Try it online!

9 bytes golfed by MarcMush.

Boring bruteforce solution. Takes input as matrix `m` and its size `n`. But here's also a bonus:

# Julia 0.7, ~~214~~ 194 bytes

```
~=round
m%n=.~filter(j->j≈.~j,1-2digits.(0:2^n-1,2,n).|>h->((t,z)=schur(m+0im);u=√t.*h;for i=n:-1:1,j=i+1:n a&k=a-u[i,k]*u[k,j];u[i,j]=reduce(&,t[i,j],i+1:j-1)/(u[i,i]+u[j,j])end;z)*u*z')[1]

```

Try it online!

This is an attempt at an algebraic solution making use of Julia's rich linear algebra library. In fact, Julia's `sqrt` or  already works on matrices, but obviously only returns the principal root which may not be the one we need. Therefore, we resort to Schur decomposition, and our task boils down to finding the square roots of the upper triangular matrix \\$T\\$ (notation is different from Wiki, but corresponds to Julia's):

\\$M^\frac{1}{2}=ZT^\frac{1}{2}Z^{-1}\\$

The square roots \\$U\\$ of matrix \\$T\\$ can be found by Björck-Hammarling method, which is what Julia itself uses in the implementation of `sqrt`:

\\$U\_{ii}=T\_{ii}^\frac{1}{2}\\$

\\$U\_{ij}=\frac{T\_{ij} - \sum\_{k=i+1}^{j-1} U\_{ik}U\_{kj}}{U\_{ii}+U\_{jj}}, j\>i\\$

In order to find all solutions, we also need to apply all possible permutations of the signs of the roots in the first equation. The upper triangle can then be fixed according to the second equation.

All these computations introduce some roundoff errors, but when checking for integers, we can resolve this by using inexact comparison operator . ~~There is a problem with zero, for which it behaves the same as exact equality and comparisons fail.~~ *(It works just fine when applied to entire matrix that has both zeros and non-zeros).*

The results are composed of complex numbers with zero imaginary part, so in TIO footer, we extract the real part for nicer display. It would be -2 bytes if it's acceptable to output the values without cleaning the roundoff errors, and further -3, if we can actually output all found integer solutions instead of just one.
> 4 votes

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


title: Composite Number Sequences

text:
# Question
Title: Composite Number Sequences
Inspired by this question

Given a positive integer \\$n\\$, your code must output the first \\$n\\$ composite numbers.

**Input / Output**

You may write a program or a function. Input is through STDIN or function argument and output is to STDOUT, or function return value.

Output can be a List, Array, or String.

**Examples**

```
 0 ->
 1 -> 4
 2 -> 4, 6
 3 -> 4, 6, 8
13 -> 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22

```

---

## Rules

* As always standard loopholes are disallowed.
* Built-ins that generate prime or composite numbers are not allowed.
* Built-ins relating to prime or composite numbers are not allowed.

# Answer
# Pyth - 10 bytes

A valid answer. Uses Wilson's Theorem.

```
.f%h.!tZZQ

```

Try it online here.

## Old answer

## Pyth - 6 chars

Uses builtin for *prime factorization*, not prime checking.

```
.ftPZQ

```

Try it online here.

```
.f  Q         First n that passes filter of lambda Z, uses input for how many
 t            Tail. This makes all that have len-one prime factorization become empty list, and thus falsey.
  P           Prime factorization - primes have a len-one factorization.
   Z          Lambda var

```
> 11 votes

# Answer
# Pyth, 11 bytes

```
<S{*M^tSQ2Q

```

Generates overly large list of products of all combinations of \[2, n\] and truncates.
> 8 votes

# Answer
# TeX, 382 bytes

Because you can.

```
\newcount\a\newcount\b\newcount\c\newcount\n\newcount\p\newcount\q\let\v\advance\let\e\else\let\z\ifnum
\def\d#1:#2:#3:{\z#1>#2\v#1 by-#2\d#1:#2:#3:\e\z#1=#2#3=1\e#3=0\fi\fi}
\def\i#1:#2:#3:{#3=0\z#1>#2\a=#1\d\a:#2:\c:
\z\c=0\b=#2\v\b by 1\i#1:\the\b:#3:\e#1\par\fi\e#3=1\fi}
\def\l#1:#2:#3:#4:{\i\the#1:2:#4:
\z#4=0\v#2 by 1\fi\z#2<#3\v#1 by 1\l#1:#2:#3:#4:\fi}
\l\p:\n:10:\q:\end

```

The number in the last line is the number of composite numbers you want to have.

This is a simple divisor tester. `\d` checks if `#2` divides `#1`. `\i` calls `\d` for all possible dividers (i.e. \< `#1`). `\l` lists the first `#2` numbers for which `\i` returns 0.

Ungolfed (well, half-golfed) version:

```
\newcount\a
\newcount\b
\newcount\c
\newcount\n
\newcount\p
\newcount\q

\def\div#1:#2:#3:{%
  \ifnum#1>#2 %
    \advance#1 by-#2 %
    \div#1:#2:#3:%
  \else%
    \ifnum#1=#2 %
      #3=1%
    \else%
      #3=0%
    \fi%
  \fi%
}

\long\def\isprime#1:#2:#3:{%
  #3=0%
  \ifnum#1>#2 %
    \a=#1 %
    \div\a:#2:\c: %
    \ifnum\c=0 %
      \b=#2 %
      \advance\b by 1 %
      \isprime#1:\the\b:#3:%
    \else
      #1\par%
    \fi%
  \else%
    #3=1%
  \fi%
}

\def\listprimes#1:#2:#3:#4:{%
  \isprime\the#1:2:#4: %
  \ifnum#4=0 %
    \advance#2 by 1 %
  \fi
  \ifnum#2<#3 %
    \advance#1 by 1 %
    \listprimes#1:#2:#3:#4: %
  \fi
}

\listprimes\p:\n:11:\q:

\end

```
> 7 votes

# Answer
## Python, 57

```
lambda n:sorted({(k/n+2)*(k%n+2)for k in range(n*n)})[:n]

```

Less golfed:

```
def f(n):
 R=range(n)
 return sorted({(a+2)*(b+2)for a in R for b in R})[:n]

```

The idea is to generate the set of composite numbers by multiplying all pairs of natural numbers except 0 and 1. Then, sort this set, and take the first `n` elements. It suffices to take the Cartesian product of the set `{2, 3, ..., n+2}` with itself, which we can get by shifting `range(n)` up by 2.

To golf this, we do a classic golfing trick of storing two values `(a,b)` in `range(n)` as a single value `k` in `range(n*n)`, and extract them as `a=k/n, b=k%n`.
> 6 votes

# Answer
# Java 8, ~~98~~ 97 bytes

```
i->{int a[]=new int[i],c=3,k=0,d;for(;k<i;c++)for(d=c;d-->2;)if(c%d<1){a[k++]=c;break;}return a;}

```

Expanded, with boilerplate:

```
public class C {
    public static void main(String[] args) {
        Function<Integer, int[]> f = i -> {
            int a[] = new int[i], c = 3;
            for (int k = 0; k < i; c++) {
                for (int d = c; d --> 2;) {
                    if (c % d < 1) {
                        a[k++] = c;
                        break;
                    }
                }
            }
            return a;
        };
        System.out.println(Arrays.toString(f.apply(5)));
    }
}

```
> 4 votes

# Answer
# R, 53 bytes

```
n=scan();t=1:(n*n+3);t[factorial(t-1)%%t!=(t-1)][1:n]

```

**How it works**

This is also based on Wilson's theorem and all it does is to run over a range of `1:n*n` and extract the composite numbers according to the above mentioned theorem. I've added `+3` because `n*n` isn't big enough range for `n < 3` integers

---

The only problem with this solution is that (sadly) R loses precision for a big enough factorial, thus, this won't work properly for `n > 19`
> 4 votes

# Answer
# CJam, ~~20~~ 18 bytes

```
li_5*{_,2>f%0&},<`

```

Try it online

Does not use any built in prime or factorization operators. Fairly brute force check for numbers being composite.

One observation that is used here is that we can easily calculate a safe upper bound for the numbers we have to test. Since every second number larger than 4 is composite, `4 + n * 2` is an upper bound for the n-th composite number.

Based on a suggestion by @Dennis, the latest implementation actually uses `n * 5` as the upper limit, which is much less efficient, but 2 bytes shorter.

Explanation:

```
li    Get and convert input.
_     Copy, will need the value to trim the list at the end.
5*    Calculate upper bound.
{     Start of filter.
  _     Copy value.
  ,     Create list [0 .. value-1].
  2>    Slice off the first two, leaving candidate factors [2 .. value-1].
  f%    Apply modulo with all candidate factors to value.
  0&    Check if one of the modulo results is 0.
},    End of filter.
<     Trim output to n values.
`     Convert list to string.

```
> 3 votes

# Answer
# Javascript ES6, 88 chars

```
n=>{r=[];for(q=2;r.length!=n;++q)if(/^(..+)\1+$/.test("-".repeat(q)))r.push(q);return r}

```
> 3 votes

# Answer
# Haskell, ~~49~~ 46 bytes

```
(`take`[x|x<-[4..],or[mod x y<1|y<-[2..x-1]]])

```

Usage example:

```
*Main> (`take`[x|x<-[4..],or[mod x y<1|y<-[2..x-1]]]) 13
[4,6,8,9,10,12,14,15,16,18,20,21,22]

```

How it works

```
  [x|x<-[4..]    ]           -- keep all x from the integers starting with 4 where
      ,or                    -- where at least one element of the following list is "True"
    [mod x y<1|y<-[2..x-1]]  -- "x mod y < 1" for all y from [2,3,...x-1]
(`take`[   ])                -- take the first n elements from the xes
                             -- where n is the parameter supplied when calling the function

```
> 2 votes

# Answer
## F#, 78 bytes

```
fun n->(Array.filter(fun i->Seq.exists((%)i>>(=)0)[2..i-1])[|2..n*n|]).[..n-1]

```

Explained:

```
fun n->
                                                           [|2..n*n|]          // Generate an array of integers from 2 to n * n
        Array.filter(fun i->                              )                    // Filter it using the following function on each element
                                                  [2..i-1]                        // Generate a list of possible divisors (from 2 to i-1)
                            Seq.exists(          )                                // Check if at least one of the divisors is valid, that is
                                       (%)i>>(=)0                                    // That i % it is equal to 0. This is equivalent to (fun d -> i % d = 0)
       (                                                             ).[..n-1] // Take the n first elements of the resulting, filtered array

```
> 2 votes

# Answer
## C++ 109

```
int main(){int n,i,x=4;cin>>n;while(n){for(i=2;i<x-1;i++){if(x%i==0){cout<<x<<' ';n--;break;}}x++;}return 0;}

```

**Ungolfed**

```
int main(){
int n,i,x=4;cin>>n;
while(n)
{
for(i=2;i<x-1;i++)
{
if(x%i==0){cout<<x<<' ';n--;break;}
}
x++;
}
return 0;
}

```
> 1 votes

# Answer
# Julia, 103 bytes

```
n->(n>0&&println(4);n>1&&(i=0;c=big(6);while i<n-1 mod(factorial(c-1),c)<1&&(i+=1;println(c));c+=1end))

```

This uses Wilson's Theorem.

Ungolfed:

```
function f(n::Int)
    # Always start with 4
    n > 0 && println(4)

    # Loop until we encounter n composites
    if n > 1
        i = 0
        c = big(6)
        while i < n-1
            if mod(factorial(c-1), c) == 0
                i += 1
                println(c)
            end
            c += 1
        end
    end
end

```
> 1 votes

# Answer
# ECMAScript 6 – ~~107~~ ~~91~~ 84 bytes

```
n=>eval('for(a=[],x=4;n&&!a[~-n];x++)for(y=2;y*2<=x;)if(x%y++<1){a.push(x);break}a')

```

The function returns an array of the first `n` composite numbers.

> `~-n` is a fancy way of writing `n-1`; same length, but much more fun, right?
> The only reason I use `eval` is that the template `n=>eval('...returnValue')` is 1 character shorter than `n=>{...return returnValue}`.

## Old versions

```
n=>eval('for(a=[],x=4;n&&!a[~-n];x++){for(z=0,y=2;y*2<=x;)if(x%y++<1)z=1;if(z)a.push(x)}a')

```

---

```
n=>eval('for(a=[],i=4;a.length<n;i++)if((x=>{for(y=2,z=1;y*2<=x;)if(x%y++<1)z=0;return!z})(i))a.push(i);a')

```

## Output

```
 0 -> []
 1 -> [4]
 2 -> [4, 6]
 3 -> [4, 6, 8]
13 -> [4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22]

```
> 1 votes

# Answer
# Haskell, 44 bytes

Heavily inspired by Nimi's earlier answer, replacing the predicate with a 2-byte shorter one based on `any` with a pointfree lambda instead of a nested list comprehension.

```
(`take`[x|x<-[4..],any((<)1.gcd x)[2..x-1]])

```

Try it online!
(thanks to Laikoni for the accurate TIO link)

**Explanation:**

```
[x|x<-[4..],       -- consider all integers x >=4
[2..x-1]           -- consider all integers smaller than x
any((<)1.gcd x)    -- if for any of them
    (<)1           -- 1 is smaller than
        .gcd x     -- the gcd of x and the lambda input
                   -- then we found a non-trivial factor and thus the number is composite
(`take`[  ])       -- take the first <argument> entries

```
> 1 votes

# Answer
# Husk, ~~14~~ 12 bytes

```
↑fṠöV¬thM%ḣN

```

Try it online!

-2 bytes from Jo King.

# Husk, 8 bytes

```
↑fȯ≠2LḊN

```

Try it online!

Uses the ivisors function, if that is okay.
> 1 votes

# Answer
# Japt, 9 bytes

```
Èâ Ê¨3}jU

```

Try it
> 0 votes

# Answer
# Vyxal, 7 bytes

```
∞'KḢḢ;Ẏ

```

Try it Online!

```
∞       # The set of all positive integers
 '   ;  # Filtered by...
  K     # The list of factors of n
   ḢḢ   # Has length > 2
      Ẏ # Get first n

```

Using a isprime builtin doesn't actually save any bytes as 1 and 0 are considered nonprime.
> 0 votes

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


title: Hilbert's Grand Hotel

text:
# Question
Title: Hilbert's Grand Hotel
## Introduction

Some of you may have heard of Hilbert's Grand Hotel. The manager there has lost his list of where the guests are staying but he still has the order in which they checked in. Each guest can not stay in a room with a room number less than their value and if a guest is added to a lower room, all guests in higher rooms with no empty space between them and the new guest are shifted up one room. Can you help him find where each of the guests are staying?

## Requirements

Write a program which receives an ordered list of natural numbers as input and places them at their index. If there is already a value in that index, it is shifted up to the next entry in the list. This process repeats until the first empty (0 or undefined) space is found. Any undefined spaces between the current highest index and any new input will be filled by adding 0s. As this is Hilbert's Grand Hotel, rooms higher than the current highest occupied index do not exist.

## Input and Output

Input will be an ordered list of natural numbers (allowed to be read through any accepted form of input)
Each number in the input is considered one guest arriving at the hotel and is in order of arrival

Output will be the final arrangement of guests (numbers)

## Examples

> **Input:** 1 3 1
> **Output:** 1 1 3
> **Step by step:**
> 1
> Create room at index 1 and place 1 in it
> 1 0 3
> Create rooms up to index 3 and place 3 in room 3
> 1 1 3
> Shift the contents of room 1 up one room and place 1 in room 1
>
> **Input:** 1 4 3 1 2 1
> **Output**: 1 1 2 1 3 4
> **Step by step:**
> 1
> Create room at index 1 and place 1 in it
> 1 0 0 4
> Create rooms up to index 4 and place 4 in room 4
> 1 0 3 4
> Place 3 in room 3
> 1 1 3 4
> Shift contents of room 1 up one room and place 1 in room 1
> 1 2 1 3 4
> Shift contents of rooms 2 to 4 up one room and place 2 in room 2
> 1 1 2 1 3 4
> Shift contents of rooms 1 to 5 up one room and place 1 in room 1
>
> **Input:** 10
> **Output:** 0 0 0 0 0 0 0 0 0 0 10
> **Step by step:**
> 0 0 0 0 0 0 0 0 0 10
> Create rooms up to room 10 and place 10 in room 10
>
> Notes:
> Working with 0 indexed is fine and you may insert a 0 at the front of the output in that case

Standard loopholes are forbidden, shortest code in bytes wins

# Answer
# Jelly, 28 bytes

```
ṫœṡ0F
’⁹ḣ;⁸;ç@ð0ẋ;@
0;ç@/œr0

```

Try it online!
> 3 votes

# Answer
# PHP 93 bytes

```
for(;$r=$g?$r+1:$g=$argv[++$i];[$g,$h[$r]]=[$h[$r],$g])$h=array_pad($h?:[],$g,0);print_r($h);

```

0 indexed. Uses a 2 in 1 loop that looks up the next guest after it gets a 0 (or a null form going beyond the current final room). Use like:

```
php -r "for(;$r=$g?$r+1:$g=$argv[++$i];[$g,$h[$r]]=[$h[$r],$g])$h=array_pad($h?:[],$g,0);print_r($h);" 1 4 3 1 2 1

```

Ungolfed:

```
for( $hotel = []; $room = $guest = $argv[ ++$i ]; )
{
    for( $hotel = array_pad( $hotel, $guest, 0 ); $guest; $room++ )
    {
        $last = $hotel[ $room ];
        $hotel[ $room ] = $guest;
        $guest = $last;
    }
}
print_r( $hotel );

```
> 5 votes

# Answer
# Haskell, 107 bytes

```
h=foldl(\h n->let{(b,a)=splitAt n h;(c,d)=span(>0)a;e=0:e;f=take n$b++e;g(0:m)=m;g m=m}in f++[n]++c++g d)[]

```

Try it online!
> 4 votes

# Answer
# Jelly, ~~24~~ 22 bytes

```
aŻƤSƇḢßoɓ@ooƑ?
Ṭ×)ç@ƒ0

```

Try it online!

I still have the strangest feeling that something closer to Dennis's answer should beat this, but I haven't had any luck with that so far. I have twisted the first line into something that sounds like some kind of exploding can (from my original recursive solution; I thought it saved a byte but I didn't look at the output too carefully so it actually ties but it does look funnier).

```
aŻƤSƇḢßoɓ@ooƑ?    Helper link: add a pre-positioned guest to the hotel

        ɓ         With reversed arguments (hotel left, guest right):
           oƑ?    Unless both arrays have a nonzero at the same location,
          o       return with the guest placed in its empty room;
        ɓ         if they do:
         @        (guest left, hotel right)
a                 Overlay the guest's zeroes on the hotel.
 ŻƤ               Prepend another zero to each prefix,
   SƇḢ            and take the first with a nonzero sum.
      ß           Call this link again with that as the new guest
       o          and with the hotel having the previous guest replace the new one.

Ṭ×)ç@ƒ0    Main link

  )        For each guest value,
Ṭ          obtain a list of all zeroes then a one at that index,
 ×         and multiply that by the same guest value.
     ƒ0    Starting with 0, reduce that by
   ç@      the helper with reversed arguments.

```

Essentially just boots occupants out of their rooms in sequence until there's no collision, considering a new guest as equivalent to someone evicted from the last room they can't start in.

Dennis's answer with some simple golfs for fair comparison, and an explanation for those still wondering:

# Jelly, 26 bytes

```
’⁹ḣ;⁸;ṫ@œṡ0Fɗð0ẋ;@
ç@ƒ0œr0

```

Try it online!

```
’⁹ḣ;⁸;ṫ@œṡ0Fɗð0ẋ;@    Helper link: add a guest on the left to the hotel on the right

             ð        Let the right argument to the rest of the link be
              0ẋ      zero repeated by the value of the guest
                ;@    concatenated to the end of the hotel.
 ⁹ḣ                   Take elements from that right argument numbering
’                     one less than the guest,
   ;⁸                 concatenate the guest,
     ;      ɗ         and concatenate:
      ṫ@              remove elements from that right argument numbering the guest value,
        œṡ0           split those remaining around the first zero,
           F          and flatten them back together.

ç@ƒ0œr0    Main link

ç@ƒ0       With the hotel starting as 0, add each guest to the hotel in sequence.
    œr0    Trim trailing zeroes.

```
> 4 votes

# Answer
# JavaScript (ES6), ~~144~~ 120 bytes

*Saved 20B thanks to Arnauld and 11B thanks to Neil*

```
a=>a.map((d,c)=>b[d]?(b.splice(d,0,d),b.splice([...b,0].findIndex((e,g)=>g&&!e),1)):b[d]=d,b=[])&&[...b].map(c=>c|0)

```

## Usage

You can assign the function to the variable `f` and the list should be given as an array. Example:

```
f=a=>a.map((d,c)=>b[d]?(b.splice(d,0,d),b.splice([...b,0].findIndex((e,g)=>g&&!e),1)):b[d]=d,b=[])&&[...b].map(c=>c|0)
f([1,4,3,1,2,1])

```

## Output

The output is in an array as well. Since Javascript works zero-indexed, there is an extra 0 up front.

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

```
> 2 votes

# Answer
## JavaScript (ES6), 86 bytes

```
f=([n,...a],r=[],p=n,m=r[p],_=r[p]=n)=>n?m?f([m,...a],r,p+1):f(a,r):[...r].map(n=>n|0)

```

Leading zero in the result because JavaScript is 0-indexed.
> 1 votes

# Answer
# Mathematica, 98 bytes

```
Fold[If[Length@#<#2,PadRight@##~Append~#2,Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]&,{0},#]&

```

Unnamed function taking a list of positive integers and returning a 0-indexed list of integers. The whole `If` function takes a partially completed list and the next integer to insert as arguments. If the next integer exceeds the length of the partial list, `PadRight@##~Append~#2` increases the partial list accordingly; otherwise, `Join[Take@##,{#2},Drop@##/.{a___,0,b__}->{a,b}]]` inserts the next integer into its position, then throws away the first `0` found after it. `Fold[...,{0},#]` applies this function repeatedly to the original list, starting with the empty hotel `{0}`, and outputs the final hotel list.
> 1 votes

# Answer
# JavaScript (ES6), 81

Using 0 indexing

```
l=>l.map(v=>(s=(p,v,w=r[p])=>(w&&s(p+1,w),r[p]=v))(v,v),r=[])&&[...r].map(x=>~~x)

```

*Less golfed*

```
l => {
  s = ( // recursively insert a value, shifting present values up until it finds an empty spot
       p, // insert position
       v, // value to insert
       w = r[p] // value a current position
      ) => (
         w && s(p+1,w), // if there is a value, put it in the next position
         r[p] = v // now the current place is empty
      );
  r = []; // initialize the result array
  l.map( // execute the following for each value in input
     v => s(v,v) // insert value
  );
  return [...r].map(x=>~~x) // fill the missing places with 0
}

```

**Test**

```
F=
l=>l.map(v=>(s=(p,v,w=r[p])=>(w&&s(p+1,w),r[p]=v))(v,v),r=[])&&[...r].map(x=>~~x)

out=x=>O.textContent+=x+'\n'

out([1,3,1]+' -> '+F([1,3,1]))
out([10]+' -> '+F([10]))

function go() {
   var v = I.value.match(/\d+/g).map(x=>+x)
   out(v +' -> ' + F(v))
}
go()
```

```
<input id=I value='1 4 3 1 2 1'><button onclick='go()'>go</button>
<pre id=O></pre>
```
> 1 votes

# Answer
# R, 133 bytes

```
a=scan()
z=rep(0,max(a))
for(i in a){b=match(0,z[-1:-i])+i
if(z[i])z[i:b]=c(i,z[i:(b-1)])else(z[i]=i)
z=c(z,0)}
z[1:max(which(z!=0))]

```

To avoid problems with bad indexing, I pad with some zeros, and then strip them at the end. This is maybe not the best solution, but it works.
> 1 votes

# Answer
## Python, ~~134~~ ~~125~~ 116 bytes

```
def a(b):
 r=[]
 i=0
 for n in b:
    d=n
    while n:
     if i<d:r.extend([0]*(d-i));i=d
     n,r[d-1]=r[d-1],n;d+=1
 return r

```

Valid for both Python 2.7.13 and 3.6.0. This code functions by means of a swapping the held value with the value contained at each index until the held value is 0. If it reaches an index not yet in the array, it adds zeros to the end of the array until the array contains that index. Thanks to Wheat Wizard and xnor for golfing off 9 bytes each
> 0 votes

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