# Question
Title: Create a list of snaking numbers under 50,000
### Snaking Number Challenge

I wonder how many snaking numbers there are between 1 and 50,000?

Snaking Numbers, in this game, are numbers which can be typed out on a traditional numberpad (format below) by moving one key up, down, left, or right.

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

```

For example, if you start with the number 5, you could select 4, 6, 8, or 2 as your next valid move - however 7, 3, 9, and 1 are off-limits as they are positioned diagonally to the current key. So, if you have 5, then 2, your next viable key choices are 0, 1, 3, or 5 again.

In this Code Golf exercise, you are to output a list of all the positive snaking numbers between 1 and 50k, along with a final count of all the numbers that meet the criterion.

### Rules

1. Numbers cannot start with a Zero.
2. Numbers must be whole positive integers.
3. Each consecutive number, read from left to right, must "snake" around the numberpad.
4. The snake cannot travel diagonally across keys
5. The number 0 can be accessed from both numbers 1 and 2
6. Numbers cannot be paired (eg: 22)

### Examples of valid Snaking Numbers:

```
12369
45201
1254
10102
1
12
987

```

### Examples of invalid numbers

```
1238 - 8 is not connected
0001 - multiple leading 0s
0101 - leading 0
159  - snake cannot travel diagonally
4556 - duplicate 5

```

As per normal Code Golfs, the aim is fewest bytes!

According to my maths and rules, you should have 670 valid snaking numbers in your list, plus 670 itself printed as the last number.

# Answer
> 14 votes
# K (ngn/k), ~~60 57~~ 60 bytes

```
(x;#x:({*/1=3!5&+/x*x:+1_-':(+0 1,'2*!3 3)@10\x}')#1+!50000)

```

Try it online!

`!50000` list of `0` .. `49999`

`1+` add 1 to all

`({` `}')#` filter with the function in `{` `}`

`10\x` decimal digits of the argument

`(` `)@` use as indices in ...

* `!3 3` a pair of lists: `(0 0 0 1 1 1 2 2 2;0 1 2 0 1 2 0 1 2)`
* `2*` multiply all by 2
* `0 1,'` prepend `0` to the first list and `1` to the second
* `+` transpose (pair of lists -\> list of pairs). this gives us the approx button coords.

`-':` subtract from each pair the previous pair. use `0 0` as an imaginary element before the first.

`1_` drop the first

`+` transpose

`x*x:` square (assign to `x` and multiply by `x`). here `x` is a pair of lists - ∆x-s and ∆y-s

`+/` sum the two lists (element by element)

`5&` min with 5

`3!` mod 3

`1=` boolean list of where it's equal to 1

`*/` product (boolean "and")

`(x;#x:` `)` make a pair of the result and the length (`#`) of the result

# Answer
> 9 votes
# Jelly,  ~~24~~  23 bytes

```
5ȷ4µDo1.’d3ZIASĊ’ẸµÐḟṄL

```

A full program which prints a list of all the results and then the number of results.

**Try it online!**

### How?

```
5ȷ4µDo1.’d3ZIASĊ’ẸµÐḟṄL - Main Link: no arguments
5ȷ4                     - 5*10^4 = 50000
   µ              µÐḟ   - filter discard those for which this is truthy:
                        -                  e.g.: 8520        ... or           4559
    D                   -   decimal digits       [8,5,2,0]                    [4,5,5,9]
      1.                -   literal 1.5
     o                  -   logical OR           [8,5,2,1.5]                  [4,5,5,9]
        ’               -   decrement            [7,4,1,0.5]                  [3,4,4,8]
         d3             -   div-mod by 3         [[2,1],[1,1],[0,1],[0,0.5]]  [[1,0],[1,1],[1,1],[2,2]]
           Z            -   transpose            [[2,1,0,0],[1,1,1,0.5]]      [[1,1,1,2],[0,1,1,2]]
            I           -   deltas               [[-1,-1,0],[0,0,-0.5]]       [[0,0,1],[1,0,1]]
             A          -   absolute value       [[1,1,0],[0,0,0.5]]          [[0,0,1],[1,0,1]]
              S         -   sum (vectorises)     [1,1,0.5]                    [1,0,2]
               Ċ        -   ceiling              [1,1,1]                      [1,0,2]
                ’       -   decrement            [0,0,0]                      [0,-1,1]
                 Ẹ      -   any?                 0 (i.e. keep)                1 (i.e. discard)
                     Ṅ  - print and yield
                      L - length
                        - implicit print

```

# Answer
> 7 votes
# Python 3, 140 bytes

```
f=lambda s:''==s[1:]or s[1]in'10021234562216565878 43 749 9   5  8'[int(s[0])::10]and f(s[1:])
print(*filter(f,map(str,range(1,50000))),670)

```

Try it online!

I'm positive someone will be able to do this with an expression instead of a lookup string.

# Answer
> 7 votes
# Python 2, 101 bytes

```
print[n for n in range(1,50000)if all(`n`[i:i+2]in`0x20b33ec8bc49a10589e76b15`for i in range(4))],670

```

Try it online!

The hex number is decimal `10120214525632365878969854741`, which encodes every ordered pair of digits that can appear adjacent to one another.

# Answer
> 5 votes
# JavaScript (V8),  ~~112 106~~  104 bytes

*Saved 2 bytes thanks to @NahuelFouilleul*

A full program.

```
for(n=0;++n<5e4;)[...n+''].every(x=>'6589632145201478'.match(x+p+'|'+p+(p=x)),p='')&&print(n)
print(670)

```

Try it online!

Or **96 bytes** if we can output the numbers in reverse order:

```
for(n=5e4;n--;)[...n+''].every(x=>'6589632145201478'.match(x+p+'|'+p+(p=x)),p='')&&print(n||670)

```

Try it online!

# Answer
> 4 votes
# Stax, ~~37~~ 35 bytes

```
ü╞╡~▄ⁿ♪eµïê◙ü╔ï▼ΔJr¥æ≤PH╟♀I♣Δz8─¶Γ╞Ç▓

```

Run and debug it at staxlang.xyz!

It was so nice and short, until it wasn't.

### Unpacked (42 bytes) and explanation

```
49999{E2B{{om"#qYY>!(AFI"%A|E2B{{om-C_Qf%p
49999{                                 f      Filter range [1..49999]:
      E2B                                       All adjacent pairs of digits
         {{om                                   Each sorted
             "#qYY>!(AFI"%A|                    Literal 2012365478963258741
                            E2B{{om             Pairs of digits, each sorted
                                   -            Set difference
                                    C           Cancel block execution if any remain
                                     _Q         Print current value
                                        %p    Print length

```

2012365478963258741 encodes the keypad. Look at pairs of adjacent digits. Perhaps if I could get a decently short alternative that goes in both directions for each pair, I could cut the eight bytes of `{{om`.

Without that trailing 670, a simple filter would suffice: `f..!` instead of `{..C_Qf%p`. There might be a better way to go about handling this irregularity. In either case, this filter-range behavior is undocumented.

# Answer
> 3 votes
# Perl 5 (`-M5.01`), ~~96~~, 92 bytes

-4 bytes thanks to @Xcali

```
$r=join"|",map$t++."[^$_]",12,240,1350,26,157,2648,359,48,579,68;map/$r/||say,1..5e4;say 670

```

TIO

# Answer
> 3 votes
# PHP, 145 bytes

```
for(;$i++<5e4;$f&&print$i._)for($f=1,$l=b;''<$d=("$i")[$$i++];$l=$d)$f&=$l>a||strstr([12,240,1053,26,157,2468,359,48,579,68][$l],$d)>'';echo 670;

```

Try it online!

For every number from 1 to 50,000, checks every digit of that number from left to right. If all digits are in the list of valid digits of the previous digit, that number is printed. At the end prints a hard coded 670 since it takes less bytes than actually counting it.

# Answer
> 3 votes
# 05AB1E, 23 bytes

```
ŽÅKLʒSÌYX;:3‰üαï€OP}=g=

```

Try it online!

Port of Jonathan Allan's Jelly answer.

# Answer
> 3 votes
# JavaScript (SpiderMonkey), ~~179~~ ~~173~~ ~~151~~ 129 bytes

```
[12,240,1350,26,157,2468,359,48,579,68].map((_,i,l)=>i&&(f=(v,t)=>print(v)|v<5e3&&[...l[t]+''].map(k=>f(v+k,k)))(i,i)),print(670)

```

Try it online!

-22 bytes thank to Arnauld -22 bytes thank to dana

# explanation:

```
[12,240,1350,26,157,2468,359,48,579,68]
// an array where keys are current position and values, the possible destinations
.map((_,i,l)=>                    // loop over it
    i&&(                          // if key is not 0
        f=(v,t)=>                 // create a function
                 print(v)|        // which print the value
                          v<5e3&& // and if the limit is not attained
                                 [...l[t]+''].map(k=>f(v+k,k))
                    // recurcively call itself with for each destinations
                                                              )(i,i)),
                    // make the first call with each digit
print(670) // finally print 670

```

---

@dana also gave a 123 bytes solution if we can print 670 first

```
[21,420,5310,62,751,8642,953,84,975,86].map((_,i,a)=>(f=(v,t)=>print(i?v:640)|i&v<5e3&&[...a[t]+''].map(k=>f(v+k,k)))(i,i))

```

# Answer
> 2 votes
# Ruby, 99 bytes

```
1.upto(5e4){|n|w,*x=n.digits;x.all?{|d|[6,21,43,68,162,340,552,272,672,320][w][w=d]>0}&&p(n)}
p 670

```

Try it online!

# Answer
> 2 votes
# Stax, ~~28~~ 26 bytes

```
Δh┤♣É╦&·é╝n$K»à¶▲v═NÆ;↨m≥8

```

Run and debug it

Unpacked, ungolfed, and commented, it looks like this.

```
G               Call to unbalanced trailing '}', then resume here
670P            Print 670
}               Call target
219J            219 squared (47961)
f               Filter 1-based range by the rest of the program; implicitly output
  $2B           Convert to string and get adjacent pairs; e.g. 213 -> ["21", "13"]
  O             Push 1 under list of pairs
  F             Iterate over pairs, using the rest of the program
    o           Order each pair; e.g. "21" -> "12"
    "{<f:[/T8Z" string literal with code points [123 60 102 58 91 47 84 56 90]
    $           concate as string i.e. "12360102589147845690"
    s#          How many times does the current pair appear in the constant string?
    *           Multiply this by running total.  Any zero will cause the result to be zero.

```

Run this one

The secret sauce is in the string literal `"{<f:[/T8Z"`. After jamming all the codepoints together, you get `12360102589147845690`. The ascending pairs in this string are the valid snake moves.

# Answer
> 2 votes
# Haskell, 118 bytes

```
(filter(and.(zipWith elem.tail<*>map f).show)[1..50000],670)
f c=words"12 024 0135 26 157 2468 359 48 579 68"!!read[c]

```

Try it online!

A first pass; I'm not good at compression.

The `s=` doesn't count, since we don't actually need to bind the result.

Ungolfed code.

# Answer
> 1 votes
# Pyth, ~~68~~ ~~65~~ 45 bytes

```
l
f.Am}dCtB+J`65874589632012541_PJCtB`TS50000

```

Try it online!

Inspiration for the revised lookup process came from Khuldraeseth na'Barya's Stax answer, go give them an upvote!

---

Edit 2: Rewrote to save a bunch of bytes, previous version:

```
l
f.Am}ed@c"12 024 0135 26 157 2468 359 48 579 68";shdCtB`TS50000

```

---

Edit: Golfed 3 bytes by using string lookups, previous version:

```
l
f.Am}ed@sMMc"12 024 0135 26 157 2468 359 48 579 68";hdCtBjT;S50000

```

# Answer
> 1 votes
# Charcoal, 42 bytes

```
≔ΦＩ…·¹×⁵⁰φ⬤ι№”)¶∧XRτ_ΠＧêＲ⁵m⎇λ”✂ιμ⁺²μ¹θθＩＬθ

```

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

```
≔ΦＩ…·¹×⁵⁰φ

```

Process the inclusive range from `1` to `50,000` cast to string.

```
⬤ι№”)¶∧XRτ_ΠＧêＲ⁵m⎇λ”✂ιμ⁺²μ¹θ

```

Filter out those that have pairs of digits not contained in the compressed string `01478963202125458565236987410`.

```
θＩＬθ

```

Output the remaining array and its length.

# Answer
> 1 votes
# Japt, 34 bytes

```
5e4õs f_ä@"-Pì[/Z8"mc øZñÃe
pUl

```

Try it

# Answer
> 1 votes
# Perl 6, 64 bytes

```
{670,grep {[+&](:36<12HGX91H8VCL3MG0FDVQ>X+>m:ov/../)%2},1..5e4}

```

Try it online!

### Explanation

```
{670,grep {...},1..5e4}  # Meet questionable output requirements

# Actual decision problem

     :36<12HGX91H8VCL3MG0FDVQ>  # Bit field of allowed transitions
                                # encoded in base 36
                                 m:ov/../  # All 2-digit substrings
                              X+>  # Right shift by each substring
                                   # (implicitly converted to an integer)
[+&](                                    )  # Binary and
                                          %2  # Modulo 2

```

---
Tags: code-golf
---


title: What my dog really hears

text:
# Question
Title: What my dog really hears
My dog is called Rex. Every time I scold him, he seems not very impressed and the only times I see him react is when I pronounce his name. If I say

`Rex, I told you not to do this! You're making me angry Rex!`

all he hears is

`Rex, * **** *** *** ** ** ****! ***'** ****** ** ***** Rex!`

**The challenge** : given an input string, your program must output the same string where all alphabetic characters have been turned to stars, except the characters in the appearances of the word `Rex`, who must be left untouched. The non-alphabetic characters are also left untouched.

**Details** : The challenge is case-insensitive, thus `rex` must be left untouched also. The word `Rex` can be part of another word, so for example `anorexic` must be rendered as `***rex**`.

**Update** : as the initial text of this challenge did not clarify how underscores or numbers or accentuated characters should be treated, I do not make any special requirement on those characters. Thus, a solution is valid as long as characters in `a-zA-Z` (and also the one mentioned in the examples, `,!".`) are handled correctly.

Test cases :

Input : `Rex lives in Rexland.`

Output : `Rex ***** ** Rex****.`

Input : `To call Rex, just say "Rex".`

Output : `** **** Rex, **** *** "Rex".`

Input : `My cat is getting anorexic.`

Output : `** *** ** ******* ***rex**.`

# Answer
> 26 votes
## Retina, ~~24~~ 21 bytes

```
i`(rex)|(\w)
$1$#2$**

```

Try it online!

### Explanation

Skipping `rex`s is easiest by matching them as well, because matches can't overlap. So if we give priority to `rex` over other letters, those will be covered in a single match and not touched by the individual-letter matches.

But how do we do different things depending on the alternative that was used for the match? Unfortunately, Retina doesn't (yet) have any conditional substitution syntax like the Boost regex flavour. But we can fake it by including both substitutions in a single replacement and making sure that only one of them is non-empty:

* `$1` is the first capturing group, i.e. the `(rex)`. If we did match `rex` this simply writes it back (so it does nothing), but if we didn't match `rex` then `$1` is an empty string and vanishes.
* `$#2$**` should be read as `($#2)$*(*)`. `$#2` is the number of times group `2` was used, i.e. the `(\w)`. If we matched `rex` this is `0`, but if we matched any other individual letter, this is `1`. `$*` repeats the next character as many times as its left-hand operand. So this part inserts a single `*` for individual-letter matches and nothing at all for `rex`.

# Answer
> 164 votes
## \**REXX ~~151~~ ~~148~~ 141 bytes \**

(Kinda seemed appropriate)

```
i=arg(1)
m=i
o=translate(m,'',xrange('A','z'),'*')
p=0
do forever
   p=pos('REX',m,p+1)
   if p=0 then leave
   o=overlay(substr(i,p,3),o,p)
end
say o

```

Try it here

Notes for non-REXXers:

1. translate is a character replacement function (name comes from an assembler instruction on IBM MF). It searches string1 for the characters in string3. Every time it finds one it replaces it with the same positioned one in string2. If string2 is too short it is padded with the pad character.

See here for translate function

2. overlay simply overlays the string1 on top of string2 at the specified position.

See here for overlay function

# Answer
> 24 votes
# JavaScript (ES6), ~~42~~ ~~41~~ 38 bytes

```
s=>s.replace(/rex|\w/gi,m=>m[1]?m:"*")

```

---

## Try It

```
o.innerText=(f=

s=>s.replace(/rex|\w/gi,m=>m[1]?m:"*")

)(i.value="Rex, I told you not to do this! You're making me angry Rex!")
oninput=_=>o.innerText=f(i.value)
```

```
<input id=i><pre id=o>
```

---

## Explanation

```
s=>            :Anonymous function that takes the string as an argument via parameter s.
s.replace(x,y) :Replace x in s with y.
/rex|\w/gi     :Case-insenstive regular expression that globally matches all occurrences
                of "rex" or any single letter, number or underscore.
                (numbers & underscores will never be included in the input.)
m=>            :Anonymous function that takes each match as an argument via parameter m.
m[1]?          :If string m has a second character, ...
                (Equivalent to m.charAt(1))
m              :Return m, ...
:"*"           :Otherwise return "*".

```

# Answer
> 13 votes
# APL (Dyalog Unicode), 22 bytesSBCS

```
'rex' '\w'⎕R'\0' '*'⍠1

```

Try it online!

Simple PCRE **R**eplace.

`⍠1` sets case insensitivity. Simply replaces `rex` with itself and all other word characters with asterisks.

# Answer
> 11 votes
# Perl 5, 24 bytes

23 bytes of code + `-p` flag.

I used Martin Ender's regex from his Retina answer (which happens to be shorter in Perl, thanks to `\pl`), and only had to adapt the right side of the s///.

```
s%(rex)|\pl%$1//"*"%gie

```

Try it online!

# Answer
> 8 votes
# Retina, ~~32~~ 31 bytes

```
iS`(rex)
%iT`Ll`*`^(?!rex).*
¶

```

Try it online! Explanation: Splits the string into occurrences of the word `rex` and everything else, but keeps the matches. Then, on lines that don't begin `rex` (i.e. the "everything else"), change letters to `*`s. Finally, join everything back together.

# Answer
> 8 votes
## C, ~~99~~ ~~97~~ ~~92~~ ~~86~~ ~~74~~ ~~73~~ ~~72~~ 65 bytes

```
f(char*s){*s&&f(s+=strnicmp("Rex",s,3)?!isalpha(*s)||(*s=42):3);}

```

Pelles IDE environment provides (compile with /Go) the function strnicmp. This function is identical to strncasecmp. See it work here (with the replacement function).

The output is stored in the first parameter which is an in/out parameter.

Thanks to Johan du Toit for letting me know that recursion is slightly shorter.

# Answer
> 7 votes
# Ruby, ~~36~~ ~~35~~ 32 bytes

```
->s{s.gsub(/(rex)|\w/i){$1||?*}}

```

As a test:

```
f=->s{s.gsub(/(rex)|\w/i){$1||?*}}

tests = [
  ["Rex, I told you not to do this! You're making me angry Rex!", "Rex, * **** *** *** ** ** ****! ***'** ****** ** ***** Rex!"],
  ["Rex lives in Rexland.", "Rex ***** ** Rex****."],
  ["To call Rex, just say \"Rex\".", %q(** **** Rex, **** *** "Rex".)],
  ["My cat is getting anorexic.", "** *** ** ******* ***rex**."]
]

tests.each do |input, output|
  if f.call(input) == output
    puts "Fine for #{input.inspect}"
  else
    puts "Problem with :\n#{input.inspect}"
    puts f.call(input)
    puts output
  end
  puts
end

```

It outputs:

```
Fine for "Rex, I told you not to do this! You're making me angry Rex!"

Fine for "Rex lives in Rexland."

Fine for "To call Rex, just say \"Rex\"."

Fine for "My cat is getting anorexic."

```

# Answer
> 6 votes
# PHP, 78 Bytes

```
<?=preg_replace("#[a-df-qs-wyz]|r(?!ex)|(?<!r)e|e(?!x)|(?<!re)x#i","*",$argn);

```

Try it online!

# PHP, 84 Bytes

```
<?=preg_replace_callback("#(rex)|\pL#i",function($t){return$t[1]?$t[1]:"*";},$argn);

```

-1 Byte `\w` instead `\pl` in this case underscore and numbers are replaced too

`\pL` is shorter as `[a-z]` or `[[:alpha:]]`

Try it online!

# Answer
> 5 votes
# C (GCC on POSIX), ~~167~~ ~~118~~ ~~93~~ 87 bytes

```
i,j;f(char*s){for(i=0;j=s[i];i++)strncasecmp("Rex",s+i,3)?s[i]=isalpha(j)?42:j:(i+=2);}

```

Try it online!

# Answer
> 5 votes
# Java 8, ~~187~~ ~~192~~ ~~168~~ ~~164~~ ~~159~~ 138 bytes

```
s->{for(int i=0;i<s.length();System.out.print(s.regionMatches(0<1,i,"rex",0,3)?s.substring(i,i+=3):s.replaceAll("\\w","*").charAt(i++)));}

```

-28 bytes thanks to @OlivierGrégoire.

**Explanation:**

Try it online.

```
s->{                         // Method with String parameter and no return-type
  for(int i=0;i<s.length();  //  Loop over the characters of the input-String
    System.out.print         //   Print:
     s.regionMatches(1>0,i,"rex",0,3)?
                             //    If we've found "rex" (case-insensitive):
      s.substring(i,i+=3)    //     Print this REX-word (case-sensitive)
     :                       //    Else:
      s.replaceAll("\\w","*").charAt(i++));
                             //     Print the current character,
                             //     or '*' if it's an alpha-numeric character

```

# Answer
> 5 votes
# Python 2 or 3, ~~75~~ ~~73~~ 70 bytes

```
import re;f=lambda s:re.sub('(?i)(rex)|\w',lambda x:x.group(1)or'*',s)

```

Basically the same as my Ruby's answer.

-2 bytes thanks to @Wondercricket.

As a test:

```
tests = [
  ["Rex, I told you not to do this! You're making me angry Rex!", "Rex, * **** *** *** ** ** ****! ***'** ****** ** ***** Rex!"],
  ["Rex lives in Rexland.", "Rex ***** ** Rex****."],
  ["To call Rex, just say \"Rex\".", "** **** Rex, **** *** \"Rex\"."],
  ["My cat is getting anorexic.", "** *** ** ******* ***rex**."]
]

for test_in, test_out in tests:
    print(test_in)
    print(f(test_in))
    print(f(test_in) == test_out)

```

# Answer
> 4 votes
## Python 2, 87 Bytes

```
import re
print re.sub(r'(?i)[a-df-qs-wyz]|r(?!ex)|(?<!r)e|e(?!x)|(?<!re)x','*',input())

```

I guess that can be shortened? :)

# Answer
> 4 votes
# sed, 37 33 bytes

36 bytes sourcecode + 1 byte for -r flag.

```
s:(rex)|\w:\1*:Ig
s:(rex)\*:\1:Ig

```

Try it online!

# Answer
> 4 votes
# QuadR, ~~11~~ 10 + 1 = 11 bytes

+1 byte for the `i` flag.

```
rex
\w
&
*

```

Try it online!

Explanation: Case-insensitively replace `rex` and word-chars with itself and asterisks, respectively.

# Answer
> 3 votes
# Retina, ~~54~~ ~~50~~ 49 bytes

*Golfed 5 bytes thanks to @MartinEnder*

```
i(`[\w-[rex]]
*
(?<!r)e|e(?!x)|r(?!ex)|(?<!re)x
*

```

Try it online!

# Answer
> 3 votes
# Gema, 25 characters

```
/[rR][eE][xX]/=$0
<L1>=\*

```

Sample run:

```
bash-4.3$ gema '/[rR][eE][xX]/=$0;<L1>=\*' <<< "Rex, I told you not to do this! You're making me angry Rex!
Rex lives in Rexland.
To call Rex, just say \"Rex\".
My cat is getting anorexic."
Rex, * **** *** *** ** ** ****! ***'** ****** ** ***** Rex!
Rex ***** ** Rex****.
** **** Rex, **** *** "Rex".
** *** ** ******* ***rex**.

```

Painful fact that could be `\CRex=$0;<L1>=\*`, but unfortunately `$0` contains the template, not the match. ☹

# Answer
> 3 votes
## PowerShell, 60 bytes

```
{$args|%{$_-replace'(rex)|\p{L}','$1*'-replace'(x)\*','$1'}}

```

Try it online

# Answer
> 2 votes
# Python 2, ~~93~~ 92 bytes

```
f=lambda s:s and("rex"==s[:3].lower()and s[:3]+f(s[3:])or("*"+s)[s[0].isalpha()<1]+f(s[1:]))

```

Try it online!

# Answer
> 2 votes
# MATL, 24 bytes

```
42y3Y2mFGk'rex'Xf!3:q+((

```

The input is a string enclosed in single quotes.

Try it online!

### Explanation

Consider input `'Rex lives in Rexland.'`

```
42    % Push 42 (ASCII for '*')
      % STACK: 42
y     % Implicit input. Duplicate from below
      % STACK: 'Rex lives in Rexland.', 42, 'Rex lives in Rexland.'
3Y2   % Push string 'ABC...YZabc...yz'
      % STACK: 'Rex lives in Rexland.', 42, 'Rex lives in Rexland.', 'ABC...YZabc...yz'
m     % Ismember
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0]
F     % Push false
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0], 0
Gk    % Push input lower-cased
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0], 0, 'rex lives in rexland'
'rex' % Push this string
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0], 0, 'rex lives in rexland', 'rex'
Xf!   % Strfind and transpose: gives indices of matchings as a column vector
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0], 0, [1; 14]
3:q   % Push [0 1 2]
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0], 0, [1; 14], [0 1 2]
+     % Addition, element-wise with broadcast
      % STACK: 'Rex lives in Rexland.', 42, [1 1 1 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 0], 0, [1 2 3; 14 15 16]
(     % Assignment indexing: sets indicated entries to 0
      % STACK: 'Rex lives in Rexland.', 42, [0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0]
(     % Assignment indexing: sets indicated entries to 42 (that is, '*'). Implicit display
      % 'Rex ***** ** Rex****.'

```

# Answer
> 2 votes
# Bash, 128 bytes

```
r=REXrex;a=`tr -c $r'",. !
' l<<<$1`;for i in {r,R}{e,E}{x,X};{
a=`echo ${a[@]//$i/$(tr $r f-k<<<$i)}`;}
tr $r l<<<$a|tr f-l $r*

```

Try it online!

I'm sticking to tr on my previous answer, non-functional bash array string replace and no preg replace!

Less golfed:

```
    a=`echo $1 |tr -c 'REXrex.,\"! ' 'z'`;        -> a replaces with z chars in input not matching REXrex or punctuation
    for i in {r,R}{e,E}{x,X}; {                   -> iterates over rex .. rEx .. REX
      j=$(tr 'REXrex' 'ABCabc' <<<$i)}            -> holds a for r, A for R, ando so on
      a=`echo ${a[@]//$i/$j`;                     -> replace each combination of rex .. rEx .. REX with abc ... aBc.. ABC
    }
    tr 'REXrex' 'z' <<<$a |tr 'ABCabcz' 'REXrex*' -> replaces each remainig r,e,x,R,E,X with z and finally each ABC with REX and z with *

```

Had to use z instead of * because of expansion

# Answer
> 2 votes
## C#, ~~93~~ 90 bytes

```
s=>System.Text.RegularExpressions.Regex.Replace(s,"(?i)rex|\w",m=>m.Length>1?m.Value:"*");

```

Believe this is the first time I've used a regex in a C# answer here because of the long namespace `System.Text.RegularExpressions`.

---

Didn't realise it when I wrote my answer but this seems to be the C# version of @Shaggy's JavaScript answer.

# Answer
> 2 votes
# Perl, 31 bytes

```
s/(rex)|[a-z]/$1||"*"/ieg;print

```

Invoke perl with `-n` option. For example:

```
echo 'To call rex, just say "Rex".'| perl -ne 's/(rex)|[a-z]/$1||"*"/ieg;print'
** **** rex, **** *** "Rex".

```

# Answer
> 1 votes
# CJam, 39 bytes

```
q{_3<_el"rex"=3{elc_'{,97>&'*@?1}?\o>}h

```

Try it online!

**How it works**

```
q           e# Read the input.
{           e# Do:
 _3<        e#  Copy the string and get its first three characters.
 _el"rex"=  e#  Check case-insensitively if they equal "rex".
  3         e#   If they do, push 3.
  {         e#   If they don't:
   elc_     e#    Take the first character of the three, and make it lowercase.
   '{,97>&  e#    Take its set intersection with the lowercase alphabet. Returns a non-empty
            e#      string (truthy) if it's a letter or an empty string (falsy) if not.
   '*@?     e#    Push a * if the char is a letter, or itself if it's not.
   1        e#    Push 1.
  }?        e#  (end if)
 \o         e#  Print the second-from-the-top stack item.
 >          e#  Slice the string after the first 3 or 1 characters, depending on previous outcome.
}h          e# Repeat the above until the string is empty.

```

# Answer
> 1 votes
# Java 7, ~~96~~ ~~98~~ ~~97~~ 96 bytes

+2 bytes for missing e's preceded by r or followed by x but not both

-1 byte for changing `[a-z&&[^rex]]` to `(?![rex])\\w`

```
String a(String s){return s.replaceAll("(?i)r(?!ex)|(?<!r)e|e(?!x)|(?<!re)x|(?![rex])\\w","*");}

```

Try it online!

A regex version for replacing using Java

Replaces everything in this regex with a * (note in Java \w has to be escaped as \\w)

```
(?i)r(?!ex)|(?<!r)e|e(?!x)|(?<!re)x|(?![rex])\w

(?i)                                                   // Case Insensitive
    r(?!ex)                                            // Any r not followed by ex
           |(?<!r)e                                    // Or any e not preceded by r
                   |e(?!x)                             // Or any e not followed by x
                          |(?<!re)x                    // Or any x not preceded by re
                                   |(?![rex])\w        // Or any other word character

```

# Answer
> 1 votes
# VimScript, 34 bytes

```
s/\v(rex|r@<=ex|(re)@<=x)@!\w/*/gi

```

And here's an interesting substitution that almost works:

```
s/\vr(ex)@!|<e|<x|[rex]@!\w/*/gi

```

Imagine running this repeatedly on the string `Rex, dex, I told you not to do this! You're making me angry Rex!` After the first line, the string is `Rex, *ex, * **** *** *** ** ** ****! ***'*e ****** *e ***** Rex!` The second pass will result in `Rex, **x, * **** *** *** ** ** ****! ***'** ****** ** ***** Rex!`, and the third pass will finish it. Any subsequent passes will not change the string. However, it could take more than 3 substitutions to get there, for example on string `xxxxxxxx`. So, if there were an easy way to run the above substitution until it stopped changing things, or as many times as the length of the input, that would be another solution. I bet it could be done in V, but it would still probably be longer than 34 bytes.

# Answer
> 1 votes
# Jelly, 23 bytes

*No response in over 24 hours to my question regarding case, so I'll post this tentative 23 byter.*

```
“rex”
Œlœṣ¢µØaW;”*yµ€j¢

```

See the test cases at **Try it online!**

### How?

```
“rex” - Link 1, get "rex": no arguments
“rex” - literal "rex"

Œlœṣ¢µØaW;”*yµ€j¢ - Main link: string s (or list of characters)
Œl                - convert s to lowercase
    ¢             - call the last link (1) as a nilad (get "rex")
  œṣ              - split left (s) at sublists equal to right ("rex")
     µ            - call the result t
             µ€   - for each word, w, in t:
      Øa          -   literal: lowercase alphabet
        W         -   wrap it in a list
          ”*      -   literal: '*'
         ;        -   concatenate the wrapped alphabet with the asterisk
            y     -   translate: replace all lowercase letters with asterisks.
                ¢ - call the last link (1) as a nilad (get "rex")
               j  - join left (translated, split text) with copies of right ("rex")

```

# Answer
> 1 votes
# CJam, 26 bytes (uppercase output) / 36 bytes (case-preserving)

```
qeu"REX":R/{__el-'*@?}f%R*

```

Try it online!

If letter case needs to be preserved (since that's still a little bit unclear), that can be accomplished with 10 extra bytes:

```
q_32f&:i\eu"REX":R/{__el-'*@?}f%R*.|

```

Try it online!

By the way, while writing this answer, I found what I would consider to be a design bug in CJam: the bitwise operators `&` and `|` are not defined between two char values, so I can't use `.|` to take the bitwise OR of two strings. The solution, which ended up costing me two extra bytes, is to first convert one of the strings with `:i` into an array of integers, which then can be ORed with the other string. (Actually it cost me *three* bytes, because if `&` worked between two chars, I could've also used `Sf&` instead of `32f&` to save the letter case information.)

On the positive side, I did discover that `{...}f%` indeed works as expected for iterating over the characters in an array of strings. Nice.

Anyway, here's a (lightly) commented version of the 36-byte code:

```
q                                       "read input";
 _32f&:i\                               "save the case bit of each input char";
         eu"REX":R/                     "uppercase input and split it on 'REX'";
                   {                    "start code block:"
                    __el-'*@?           "c = (c != lowercase(c) ? '*' : c)";
                             }f%        "apply block to chars in each substring";
                                R*      "join the substrings with 'REX' again";
                                  .|    "bitwise OR the case bits back in";

```

The case-saving trick works because the case of ASCII letters is solely determined by the fifth bit of the ASCII code: this bit is 0 for uppercase and 1 for lowercase letters. Thus, taking the bitwise AND of the character code with 32 = 25 extracts the case bit, and bitwise ORing this bit with the uppercased letters restores their original case.

Of course, non-alphabetic characters may have arbitrary values for the fifth bit (although, due to the way ASCII characters are organized, most punctuation characters have the fifth bit set to 1) but this doesn't matter, since those characters are left untouched by uppercasing and the letter censoring loop anyway, and ORing a character with its own fifth bit does't change it. Also, conveniently, the `*` character already has the fifth bit set, so it is also left unchanged by the final `.|`.

# Answer
> 1 votes
# Japt, ~~21~~ ~~20~~ ~~19~~ 17 bytes

A port of my JavaScript solution, with a little help from Oliver. Would be 16 in Japt v2 but RegEx is very bugged right now.

```
r`(x)|%l`Ïª'*}'i

```

Try it

## Japt v2.0a0, 12 bytes

If, as some other solutions assume, output case is irrelevant.

```
v Ër\l'*}`x

```

Try it

# Answer
> 1 votes
# Pip, ~~21~~ 19 bytes

```
qR-`(rex)|\w`{b|'*}

```

Takes input from stdin, outputs to stdout. Try it online!

### Explanation

```
q                    Read a line of stdin
 R                   and replace
   `(rex)|\w`          a regex matching `rex` or any single alphanumeric character,
  -                    case-insensitive
             {    }  with this callback function:
              b|'*     If the 1st capture group (rex) matched, return it, else asterisk
                       The result of the replacement is auto-printed

```

# Answer
> 1 votes
# SNOBOL4 (CSNOBOL4), 147 bytes

```
	L =INPUT
	K =ANY(&UCASE &LCASE)
B	L ARB . X (('R' | 'r') 'ex') . Y REM . L	:F(O)
R	X K ='*'	:S(R)
	O =O X Y :(B)
O	L K ='*'	:S(O)
	OUTPUT =O L
END

```

Try it online!

Previous version did not properly handle non-alphabetic characters.

# Answer
> 1 votes
# , ~~27~~, 24 bytes

I'm leaving both answers up, because I think they're equally interesting.

# 27 bytes

```
òÓãr¨ex©À!ü¼eü¼xü[rex]À!÷/*

```

Try it online!

Thanks to Brian McCutchon for his idea to do this in V

Hexdump:

```
00000000: f2d3 e372 a865 78a9 c021 fcbc 65fc bc78  ...r.ex..!..e..x
00000010: fc5b 7265 785d c021 f72f 2a              .[rex].!./*

```

Explanation:

```
ò                           " Until the output stops changing...
 Óãr¨ex©À!ü¼eü¼xü[rex]À!÷/* " Run the compressed vim regex:

:s/\vr(ex)@!|<e|<x|[rex]@!\w/*/gi

```

# 24 bytes

```
Óãrex/ò&ò
HòÓ÷/*/e
jjòÍî

```

Try it online!

```
Ó           " Substitute
 ã          "   (case-insensitive)
  rex       "   'rex'
     /      " with
       &    "   'rex'
      ò ò   "   Surrounded in new lines
ò           " Recursively...
 Ó          "   Substitute...
  ÷         "     A word character
   /        "   with
    *       "     An asterisk
     /e     "     (don't break if there are 0 matches)
jj          "   Move down 2 lines
  ò         " end the recursive loop
   Íî       " Remove all newlines

```

# Answer
> 1 votes
# 05AB1E, 21 bytes

```
l…rex©₄ç:AS'*:₄ç®:s.Ï

```

I've assumed the input can contain any ASCII character and only upper and lowercase letters are replaced with asterisks. It could be 2 bytes less if we assume the input will never contain substring `1000`, in which case both `ç` can be removed.

Try it online.

**Explanation:**

```
l           # Convert the (implicit) input to lowercase
 …rex       # Push string "rex"
     ©      # Store it in the register (without popping)
      ₄ç    # Push 1000 and convert it to a character: "Ϩ"
        :   # Replace all "rex" with "Ϩ"
AS          # Push the lowercase alphabet, and convert it to a list of characters
  '*       '# Push "*"
    :       # Replace every letter in the alphabet with "*"
₄ç          # Push "Ϩ" again
  ®         # Push "rex" from the register
   :        # Replace all "Ϩ" with "rex"
s           # Swap to take the (implicit) input again at the top of the stack
 .Ï         # Match the case of the lowercase "rex" with that of the input
            # (and output implicitly)

```

# Answer
> 0 votes
# PegJS \+ ES6, 50 bytes

```
C=a:("rex"i/[a-z]i{return'*'}/.)*{return a.join``}

```

Online interpreter

The lack of lambda syntax for the expression returns hurts the size.

# Answer
> 0 votes
# Julia, ~~69~~ 50 bytes.

```
f(x)=replace(x,r"rex|[a-z]"i,a->length(a)>1?a:"*")

```

Took some ideas from more concise entries, now it works like them.

# Answer
> 0 votes
# Japt 2.0a0, 17 bytes

```
r/(Rex)|\l/i@Yª'*

```

Try it online!

### Unpacked & How it works

```
Ur/(Rex)|\l/iXYZ{Y||'*

Ur  Replace on input...
/(Rex)|\l/i  Match this regex globally...
             (`\l` stands for [A-Za-z], and Japt regexes have `g` by default)
XYZ{Y||'*    and replace anything that isn't Rex into '*'.

```

`S.r` uses JS's `String.replace` which can accept a function as 2nd input, but unfortunately, the Japt doc doesn't mention it.

Idea adapted from Martin Ender's Retina answer.

# Answer
> 0 votes
# K4, 56 bytes

**Solution:**

```
{@[;r;:;x@r:,/ss[_x;"rex"]+\:!3]@[x;&(_x)in .Q.a;:;"*"]}

```

**Examples:**

```
q)k){@[;r;:;x@r:,/ss[_x;"rex"]+\:!3]@[x;&(_x)in .Q.a;:;"*"]}"Rex lives in Rexland."
"Rex ***** ** Rex****."
q)k){@[;r;:;x@r:,/ss[_x;"rex"]+\:!3]@[x;&(_x)in .Q.a;:;"*"]}"To call Rex, just say \"Rex\"."
"** **** Rex, **** *** \"Rex\"."
q)k){@[;r;:;x@r:,/ss[_x;"rex"]+\:!3]@[x;&(_x)in .Q.a;:;"*"]}"My cat is getting anorexic."
"** *** ** ******* ***rex**."

```

**Explanation:**

No regular expressions here... Change everything non-alphabetic into stars, put back any occurences of Rex:

```
{@[;r;:;x@r:,/ss[_x;"rex"]+\:!3]@[x;&(_x)in .Q.a;:;"*"]} / the solution
{                                                      } / lambda taking implicit x
                                @[x;            ;:;"*"]  / apply (@) assignment (:) of "*" at indices...
                                         in .Q.a         / in lowercase alphabet?
                                     (_x)                / lowercase (_) x
                                    &                    / indices where true
 @[; ;:;                       ]                         / another application of assignment
                             !3                          / range til 3 -> 0 1 2
                          +\:                            / add (+) to each left (\:)
              ss[_x;"rex"]                               / string-search for "rex" in lowercase (_) x
            ,/                                           / flatten
          r:                                             / assign to r
        x@                                               / index into x
    r                                                    / indices to modify

```

# Answer
> 0 votes
# Dart, 99 bytes

```
f(s)=>s.replaceAllMapped(RegExp(r'(rex)|(\w)',caseSensitive:false),(Match m)=>m[1]!=null?m[1]:'*');

```

Try it online!

# Answer
> 0 votes
# Stax, 18 bytes

```
ùV:┬KsS•u┤8α╞"T-┤☼

```

Run and debug it

# Answer
> -1 votes
# JS (ES5), 75 bytes

```
function r(l){return l.replace(/rex|\w/gi,function(c){return c[1]?c:"*"})}

```

Based on this

---
Tags: code-golf, string, substitution
---


title: Heavy Box Stacking

text:
# Question
Title: Heavy Box Stacking
You have a bunch of heavy boxes and you want to stack them in the fewest number of stacks possible. The issue is that you can't stack more boxes on a box than it can support, so heavier boxes must go on the bottom of a stack.

## The Challenge

**Input**: A list of weights of boxes, in whole kg.

**Output**: A list of lists describing the stacks of boxes. This must use the fewest number of stacks possible for the input. To be a valid stack, the weight of each box in the stack must be greater than or equal to the sum of the weight of all boxes above it.

### Examples of Valid stacks

(In bottom to top order)

* \[3\]
* \[1, 1\]
* \[3, 2, 1\]
* \[4, 2, 1, 1\]
* \[27, 17, 6, 3, 1\]
* \[33, 32, 1\]
* \[999, 888, 99, 11, 1\]

### Examples of Invalid stacks

(In order from bottom to top)

* \[1, 2\]
* \[3, 3, 3\]
* \[5, 5, 1\]
* \[999, 888, 777\]
* \[4, 3, 2\]
* \[4321, 3000, 1234, 321\]

## Example Test Cases

### 1

```
IN: [1, 2, 3, 4, 5, 6, 9, 12]
OUT: [[12, 6, 3, 2, 1], [9, 5, 4]]

```

### 2

```
IN: [87, 432, 9999, 1234, 3030]
OUT: [[9999, 3030, 1234, 432, 87]]

```

### 3

```
IN: [1, 5, 3, 1, 4, 2, 1, 6, 1, 7, 2, 3]
OUT: [[6, 3, 2, 1], [7, 4, 2, 1], [5, 3, 1, 1]]

```

### 4

```
IN: [8, 5, 8, 8, 1, 2]
OUT: [[8, 8], [8, 5, 2, 1]]

```

## Rules and Assumptions

* Standard I/O rules and banned loopholes apply
* Use any convenient format for I/O
    + Stacks may be described top to bottom or bottom to top, as long as you are consistent.
    + The order of stacks (rather than boxes within those stacks) does not matter.
    + You may also take input boxes as a presorted list. Order is not particularly important for the input, so long as the general problem isn't being solved by the sorting itself.
* If there is more than one optimal configuration of stacks, you may output any one of them
* You may assume that there is at least one box and that all boxes weigh at least 1 kg
* You must support weights up to 9,999 kg, at minimum.
* You must support up to 9,999 total boxes, at minimum.
* Boxes with the same weight are indistinguishable, so there is no need to annotate which box was used where.

Happy golfing! Good luck!

# Answer
# Jelly, 19 bytes

```
Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ

```

Try it online!

Obvious -3 thanks to Nick Kennedy...

Top to bottom.

Explanation:

```
Œ!ŒṖ€ẎṖÄ>ḊƲ€¬ȦƊƇLÞḢ  Arguments: S (e.g. [1, 2, 3, 4, 5])
Œ!                   Permutations (e.g. [..., [4, 1, 5, 2, 3], ...])
    €                Map link over left argument (e.g. [..., [..., [[4, 1], [5], [2, 3]], ...], ...])
  ŒṖ                  Partitions (e.g. [..., [[4, 1], [5], [2, 3]], ...])
     Ẏ               Concatenate elements (e.g. [..., ..., [[4, 1], [5], [2, 3]], ..., ...])
               Ƈ     Filter by link (e.g. [..., [[1, 3], [2], [4], [5]], ...])
              Ɗ       Create >=3-link monadic chain (e.g. [[1], [], [0]])
           €           Map link over left argument (e.g. [[1], [], [0]])
          Ʋ             Create >=4-link monadic chain (e.g. [1])
      Ṗ                  Remove last element (e.g. [4])
       Ä                 Cumulative sum (e.g. [4])
         Ḋ               [Get original argument] Remove first element (e.g. [1])
        >                Greater than (vectorizes) (e.g. [1])
            ¬          Logical NOT (vectorizes) (e.g. [[0], [], [1]])
             Ȧ         Check if non-empty and not containing zeroes after flattening (e.g. 0)
                 Þ   Sort by link (e.g. [[[1, 2, 3], [4, 5]], ..., [[5], [4], [3], [2], [1]]])
                L     Length (e.g. 4)
                  Ḣ  Pop first element (e.g. [[1, 2, 3], [4, 5]])

```
> 5 votes

# Answer
# JavaScript (Node.js),  ~~139 122~~  116 bytes

Expects the input sorted in ascending order.

```
f=(A,s=[],[n,...a]=A,r)=>n?s.some((b,i,[...c])=>n<eval(b.join`+`)?0:f(A,c,a,c[i]=[n,...b]))?S:r?0:f(A,[...s,[]]):S=s

```

Try it online!

### Commented

```
f = (                        // f is a recursive function taking:
  A,                         //   A[] = input array
  s = [],                    //   s[] = list of stacks, initially empty
  [n,                        //   n   = next weight to process
      ...a] = A,             //   a[] = array of remaining weights
  r                          //   r   = recursion flag
) =>                         //
  n ?                        // if n is defined:
    s.some((b, i,            //   for each stack b[] at position i in s[],
                  [...c]) => //   using c[] as a copy of s[]:
      n < eval(b.join`+`) ?  //     if n is not heavy enough to support all values in b[]:
        0                    //       abort
      :                      //     else:
        f(                   //       do a recursive call:
          A, c, a,           //         using A[], c[] and a[]
          c[i] = [n, ...b]   //         with n prepended to c[i]
        )                    //       end of recursive call
    ) ?                      //   end of some(); if successful:
      S                      //     return S[]
    :                        //   else:
      r ?                    //     if this is a recursive call:
        0                    //       do nothing
      :                      //     else:
        f(A, [...s, []])     //       try again with an additional stack
  :                          // else:
    S = s                    //   success: save the solution in S[]

```
> 5 votes

# Answer
# Python 3.8 (pre-release), 178 bytes

```
f=lambda b,s=[[]]:(a for i in range(len(s))if b[0]>=sum(s[i])for a in f(b[1:],s[:i]+[[b[0]]+s[i]]+s[i+1:]+[[]]))if b else[s]
g=lambda a:(c:=sorted(f(a),key=len)[0])[:c.index([])]

```

Try it online!

Now works on all possible inputs. *(It times out on TIO with more than ten or so boxes, but it calculates a correct answer)*
> 2 votes

---
Tags: code-golf, optimization
---


title: Plane Blowup

text:
# Question
Title: Plane Blowup
The Blow-up is a powerful tool in algebraic geometry. It allows the removal of *singularities* from *algebraic sets* while preserving the rest of their structure.

If you're not familiar with any of that don't worry, the actual computation is not difficult to understand (see below).

In the following we are considering the *blow-up* of the point \\$(0,0)\\$ of an algebraic curve in 2D. An algebraic curve in 2D is given by the zero-locus of a polynomial in two variables (e.g. \\$p(x,y) = x^2 + y^2 - 1\\$ for the unit circle, or \\$p(x,y) = y-x^2\\$ for a parabola). The *blowup* of that curve (in \\$(0,0)\\$) is given by two polynomials \\$r,s\\$ as defined below. Both \\$r\\$ and \\$s\\$ do describe \\$p\\$ with the (possible) singularity at \\$(0,0)\\$ removed.

### Challenge

Given some polynomial \\$p\\$, find \\$r\\$ and \\$s\\$ as defined below.

### Definition

First of all note that everything I say here is simplified, and does not completely correspond to the actual definitions.

Given a polynomial \\$p\\$ in two variables \\$x,y\\$ the *blowup* is given by two polynomials \\$r,s\\$ again each in two variables.

To get \\$r\\$ we first define \\$R(x,v) := p(x,vx)\\$. Then \\$R(x,v)\\$ is probably a multiple of \\$x\\$, i.e. \\$R(x,v) = x^n \cdot r(x,v)\\$ for some \\$n\\$ where \\$x\\$ does not divide \\$r(x,v)\\$. Then \\$r(x,v)\\$ is basically what remains after the division.

The other polynomial is defined exactly the same, but we switch the variables: First write \\$S(u,y) := p(uy,y)\\$. Then \\$s\\$ is defined such that \\$S(u,y) = y^m \cdot s(u,y)\\$ for some \\$m\\$ where \\$y\\$ does not divide \\$s(u,y)\\$.

In order to make it clearer consider following

### Example

Consider the curve given by the zero locus of \\$p(x,y) = y^2 - (1+x) x^2\\$. (It has a singularity at \\$(0,0)\\$ because there is no well defined tangent at that point. )

Then we find

$$R(x,v) = p(x,vx) = v^2x^2-(1+x)x^2 = x^2 (v^2-1-x)$$

Then \\$r(x,v) = v^2 -1 -x\\$ is the first polynomial.

Similarly

$$S(u,y) = p(uy,y) = y^2 - (1+ uy) u^2 y^2 = y^2 (1 - (1 + uy)u^2)$$

Then \\$s(u,y) = 1 - (1 + uy)u^2 = 1 - u^2 + u^3y\\$.

### Input/Output Format

(Same as here.) The polynomials are represented given as`(m+1) x (n+1)` matrices/lists of lists of integer coefficients, in the example below the terms of the coefficients are given in their position:

```
[   1 * 1,   1 * x,   1 * x^2,   1 * x^3,  ... , 1 * x^n ]
[   y * 1,   y * x,   y * x^2,   y * x^4,  ... , y * x^n ]
[   ...  ,   ...   ,   ...   ,    ...   ,  ... ,   ...   ]
[ y^m * 1, y^m * x, y^m * x^2, y^m * x^3 , ..., y^m * x^n]

```

So an ellipse `0 = x^2 + 2y^2 -1` would be represented as

```
[[-1, 0, 1],
 [ 0, 0, 0],
 [ 2, 0, 0]]

```

If you prefer you can also swap `x` and `y`. In each direction you are allowed to have trailing zeros (i.e. coefficients of higher degrees that are just zero). If it is more convenient you can also have staggered arrays (instead of a rectangular one) such that all sub sub-arrays contain no trailing zeros.

* The output format is the same as the input format.

### Examples

More to be added (source for more)

```
Trifolium
p(x,y) = (x^2 + y^2)^2 - (x^3 - 3xy^2)
r(x,v) = v^4  x + 2  v^2  x + x + 3  v^2 - 1
s(u,y) = u^4  y + 2  u^2  y + y - u^3 + 3  u

```

```
Descartes Folium
p(x,y) = y^3 - 3xy + x^3
r(x,v) = v^3  x + x - 3v
s(u,y) = u^3  y + y - 3u

```

### Examples w/o pictures

```
Trifolium:
p:
[[0,0,0,-1,1],
 [0,0,0, 0,0],
 [0,3,2, 0,0],
 [0,0,0, 0,0],
 [1,0,0, 0,0]]
r: (using the "down" dimension for v instead of y)
[[-1,1],
 [ 0,0],
 [ 3,2],
 [ 0,0],
 [ 0,1]]
s: (using the "right" dimension for u instead of x)
[[0,3,0,-1,0],
 [1,0,2, 0,1]]

Descartes Folium:
p:
[[0, 0,0,1],
 [0,-3,0,0],
 [0, 0,0,0],
 [1, 0,0,0]]
r:
[[ 0,1],
 [-3,0],
 [ 0,0],
 [ 0,1]]
s:
[[0,-3,0,0],
 [1, 0,0,1]]

Lemniscate:
p:
[[0,0,-1,0,1],
 [0,0, 0,0,0],
 [1,0, 0,0,0]]
r:
[[-1,0,1],
 [ 0,0,0],
 [ 1,0,0]]
s:
[[1,0,-1,0,0],
 [0,0, 0,0,0],
 [0,0, 0,0,1]]

Powers:
p:
[[0,1,1,1,1]]

r:
[[1,1,1,1]]

s:
[[0,1,0,0,0],
 [0,0,1,0,0],
 [0,0,0,1,0],
 [0,0,0,0,1]]

```

# Answer
> 5 votes
# Python 3 \+ numpy, ~~165~~ 134 bytes

```
lambda p:(r(p),r(p.T).T)
from numpy import*
def r(p):w,l=where(p);s=w+l;n=min(s);o=zeros((len(p),max(s)-n+1));o[w,s-n]=p[w,l];return o

```

Try it online!

The function takes one `numpy` 2D array `p` as input and returns a tuple of `(r,s)` of two `numpy` 2D arrays.

The breakdown of the solution is as follows. In order to compute the polynomial \\$r\\$, we rewrite each term \\$x^jy^i\\$ of \\$p\\$ into \\$x^{j+i}(\frac{y}{x})^i\\$, and it becomes \\$x^{j+i}u^i\\$ in \\$p(x,ux)\\$. So we can rearrange the input \\$(m+1)\times (n+1)\\$ matrix \\$P\\$ into a \\$(m+1)\times (m+n-1)\\$ matrix \\$D\\$ corresponding to \\$p(x,ux)\\$ by setting \\$D\[i,j+i\]=P\[i,j\]\\$. Then we eliminate all-zero columns at the beginning and end of \\$D\\$ to perform a reduction and get the output matrix \\$R\\$ for \\$r\\$.

To compute \\$s\\$, we simply swap \\$x\\$ and \\$y\\$, repeat the same process, and then swap them back. This corresponds to computing \\$R\\$ for \\$P^T\\$ and then transposes the outcome.

The following ungolfed code shows the above computation process.

# Ungolfed (Basic)

```
import numpy as np

def r(p):
    num_rows, num_cols = p.shape
    deg_mat = np.zeros((num_rows, num_rows + num_cols - 1))
    for i, row in enumerate(p):
        deg_mat[i, i:i+num_cols] = row
    non_zero_col_idx, = np.where(deg_mat.any(axis=0))
    return deg_mat[:,non_zero_col_idx.min():non_zero_col_idx.max()+1]

def rs(p):
    return r(p), r(p.T).T

```

Try it online!

A further improvement of the solution computes the matrix \\$R\\$ in one single pass based on \\$R\[i,j+i-c\]=P\[i,j\]\\$, where \\$c=\min\_{P\[i,j\]\neq 0}i+j\\$.

# Ungolfed (Improved)

```
import numpy as np

def r(p):
    y_deg, x_deg = np.where(p)  # Retrieve degrees of y and x for non-zero elements in p
    total_deg = y_deg + x_deg
    min_total_deg = total_deg.min()
    max_total_deg = total_deg.max()
    out = np.zeros((p.shape[0], max_total_deg - min_total_deg + 1))
    out[y_deg, y_deg + x_deg - min_total_deg] = p[y_deg, x_deg]
    return out

def rs(p):
    return r(p), r(p.T).T

```

Try it online!

# Answer
> 3 votes
# APL (Dyalog Unicode), ~~38~~ 37 bytes

1 byte saved thanks to ngn by using `+/∘⍴` in place of the dummy literal `0`

```
⊢∘⍉\+/∘⍴{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍺↑⍵}¨⊂,⊂∘⍉

```

Try it online!

(a train with `⎕io` (index origin) set as 0)

enclosed right argument

`,` concatenated with

* `⊂∘` enclosed
* transposed right argument

\\$s\\$ is computed from the former, \\$r\\$ from the latter

`¨` on each

`+/∘⍴{ ... }` perform the following function with left argument

* `+/` sum

+ - the shape of the right argument, i.e. get rows+columns

and the right argument will be each of the enclosed matrices.

`⍺↑⍵` and take left argument  many rows from the right argument , if  is deficient in rows (which it will be because rows+columns \> rows), it is padded with enough 0s

The computation of substituting \\$vx\\$ or \\$uy\\$ in place of \\$y\\$ or \\$x\\$ is done by rotating the columns of  by their index, and since  is padded with 0s, columns of  are effectively prepended by the desired amount of 0s.

rotate columns by

* `⍉⍵` transposed
* count rows, all together, `≢⍉⍵` gets the number of columns in
* range 0 .. count-1
* `-` negated, to rotate in the other direction and the default for , to ultimately yield 0 ¯1 ¯2 ... -(count-1), this automatically vectorises across each column such that the 0-th column is rotated by 0, the 1-st by 1, ...

`q←` assign this to variable `q`

Now to divide the polynomial by the largest power of \\$x\\$ or \\$y\\$, the leading all-0 rows have to be removed.

`∨/` reduce by LCM across each row, if the row is all-0s, this yields 0, otherwise it gives a positive number

`×` get its sign, `0``0` and positive number → `1`

indices of truthies, i.e. indices of 1s

pick the first element, `⊃⍸` simply gets the index of the first 1

`q↓⍨` drops that many rows from `q`, again `⎕io←0` helps in  returning the correct value for dropping the leading all-0 rows

(exit function)

\\$s\\$ is already achieved, to get \\$r\\$ the second value has to be transposed via `⊢∘⍉\`

---

Other approaches are listed below.

```
⍝(⊢∘⍉\+/∘⍴{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍺↑⍵}¨⊂,⊂∘⍉)¨a
⍝(⊢∘⍉\∘⌽⍴{q↓⍨⊃⍸×∨/q←(-⍳⍺)⊖⍵↑⍨+/⍴⍵}¨⊂∘⍉,⊂)¨a
⍝(⊢∘⍉\⌽∘⍴{q↓⍨⊃⍸×∨/q←(-⍳⍺)⊖⍵↑⍨+/⍴⍵}¨⊂,⊂∘⍉)¨a
⍝(⊢∘⍉\0{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⊂,⊂∘⍉)¨a
⍝(⊢∘⍉\+/∘⍴({⍵↓⍨⊃⍸×∨/⍵}(-∘⍳1⊃⊢∘⍴)⊖↑)¨⊂,⊂∘⍉)¨a
⍝(⊂∘⍉∘⊃@0⍴{q↓⍨⊃⍸×∨/q←(-⍳⍺)⊖⍵↑⍨+/⍴⍵}¨⊂∘⍉,⊂)¨a
⍝{⊢∘⍉\{q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝(⊢∘⍉\(({⍵↓⍨⊃⍸×∨/⍵}(-∘⍳1⊃⍴)⊖⊢↑⍨1⊥⍴)¨⊂,⊂∘⍉))¨a
⍝(0 1{⍉⍣⍺⊢q↓⍨⊃⍸×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⊂,⊂∘⍉)¨a
⍝{⊢∘⍉\{q[;⍸×∨\∨⌿q←↑(,\0⍴⍨≢⍵),¨↓⍵]}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{q↓⍨1⍳⍨×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝(⊢∘⍉\(((⊢↓⍨1⍳⍨0≠∨/)(-∘⍳1⊃⍴)⊖⊢↑⍨1⊥⍴)¨⊂,⊂∘⍉))¨a
⍝{⊢∘⍉\{q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{q↓⍨+/0=∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{q↓⍨⌊/+⌿∧⍀0=q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝(⌽∘⍉¨1↓({⊖⍉q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}\3/⊂))¨a
⍝{⊢∘⍉\{↑(↓q)/⍨∨\×∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝f←⊢∘⍉\⋄{f{q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}¨f⍵⍵}¨a
⍝{1↓⌽∘⍉¨{⊖⍉q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}\3/⊂⍵}¨a
⍝{f←{q[⍸×∨\∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵;]}⋄(f⍵)(⍉f⍉⍵)}¨a
⍝{⊢∘⍉\{↑(↓q)/⍨∨\0≠∨/q←(-⍳≢⍉⍵)⊖⍵↑⍨+/⍴⍵}¨⍵(⍉⍵)}¨a
⍝{⊢∘⍉\{(0~⍨∊⍵)@(↓⍉(⊢-⌊/)@1+⍀⍉↑⍸0≠⍵)⊢0⍴⍨,⍨⌈/⍴⍵}¨⍵(⍉⍵)}¨a

```

---
Tags: code-golf, math, geometry, abstract-algebra, polynomials
---


title: Free a Binary Tree

text:
# Question
Title: Free a Binary Tree
So before you read some basic computer science concepts.

1. A binary tree is a dynamically allocated structure (usually used for ordered storage).
2. Because of its nature traversal of binary trees is usually recursive;
This is because linear traversal (via a loop) is not natural when there are two avenues of looping.
    * Recursive: This means a function that calls itself.
3. In old fashioned languages, memory management requires manual memory management.
    * Manual: Means you have to do it yourself.
4. When you do manual memory management you need to actual ask the underlying system to free each member of the tree.
    * Free: recover the memory in to the global poos so it can be re-used and you don't run out of memory.
    * Freeing: this is done by calling the function `free()` and passing it the pointer you want to recover.
    * Pointer: Its like a virtual stick. At the end is memory. When you ask for memory you are given a pointer (virtual stick) that has memory. When you are done you give back the pointer (virtual stick).

### The recursive solution:

```
freeTree(Node* node)
{
    freeTree(node->left);
    freeTree(node->right);
    free(node);
}

```

The problem then is that recursion means you are repeatedly calling the same function. This grows the stack. Growing the stack uses more memory. The reason you are freeing the tree is you want memory back using more memory is counterproductive (even if you do get both bits of memory back).

### At last the question:

SO the problem centers around converting the recursive version above into a linear solution (so that you don't have to use memory).

Give the node type

```
typedef struct Node Node;
struct Node
{
    Node* left;
    Node* right;
};

```

Write a function to free a tree of these nodes.

Restrictions:

* Cannot use recursion (not even indirectly)
* Cannot allocate any dynamic space for tracking.
* Note there is an O(n) solution

Winner:

1. Best Complexity.
2. Tie Break 1: First Submitted
3. Tie Break 2: Least amount of characters.

# Answer
Seems very close to O(n) to me:

This does a depth-first walk on the tree, and uses the `->left` pointer of traversed nodes to keep track of the parent.

```
struct Node * node = root;
struct Node * up = NULL;

while (node != NULL) {
    if (node->left != NULL) {
        struct Node * left = node->left;
        node->left = up;
        up = node;
        node = left;
    } else if (node->right != NULL) {
        struct Node * right = node->right;
        node->left = up;
        node->right = NULL;
        up = node;
        node = right;
    } else {
        if (up == NULL) {
            free(node);
            node = NULL;
        }
        while (up != NULL) {
            free(node);
            if (up->right != NULL) {
                node = up->right;
                up->right = NULL;
                break;
            } else {
                node = up;
                up = up->left;
            }
        }
    }
}

```
> 8 votes

# Answer
# C99, 94, O(n)

**Edit:** everyone seems to refer to `struct Node` just as `Node` as if the `typedef`ed it, so I did too.

this is actually my first C golf. lots of segfaults.

anyways, this requires C99 because it uses a declaration inside a for loop's first statement.

```
void f(Node*n){for(Node*q;n;n=q)(q=n->left)?n->left=q->right,q->right=n:(q=n->right,free(n));}

```

not even using `#define`!

this algorithm works by transforming the tree so that the top node has no left child, and then deleting it and moving on to it's right child.

for example, if we start with the tree

```
 1
/ \
2 3
 \
 4

```

the algorithm will mutate the pointers so that the tree will be

```
2
 \
 1
/ \
4 3

```

now we can delete the topmost node easily.
> 4 votes

# Answer
# c++ 99 O(n)

The thing here loops are great for chaining along a list but not going up and down hierarchies. user300 managed it (I am impressed) but the code is hard to read.

The solution is to convert the tree into a list.
The trick is to do it at the same time your deleting the nodes.

```
void freeNode(Node* t)
{
    if (t == NULL)
    {   return;
    }

    // Points at the bottom left node.
    // Any right nodes are added to the bottom left as we go down
    // this progressively flattens the tree into a list as we go.
    Node* bottomLeft    = findBottomLeft(t);

    while(t != NULL)
    {
        // Technically we don't need the if (it works fine without)
        // But it makes the code easier to reason about with it here.
        if (t->right != NULL)
        {
            bottomLeft->left = t->right;
            bottomLeft = findBottomLeft(bottomLeft);
        }
        // Now just free the curent node
        Node*   old = t;
        t = t->left;
        free(old);
    }
}

Node* findBottomLeft(Node* t)
{
    while(t->left != NULL)
    {
        t = t->left;
    }
    return t;
}

```

# Golf Version

```
void f(Node*t){Node*o,*l=t;for(;t;free(o)){for(;l->left;l=l->left);l->left=t->right;o=t;t=t->left;}}

```

## Golf Expanded

```
void f(Node* t)
{
        Node*o,*l    = t;

        for(;t;free(o))
        {
            for(;l->left;l = l->left);
            l->left = t->right;
            o = t;
            t = t->left;
        }
}

```
> 2 votes

# Answer
## C/C++/Objective-C 126 characters (includes required trailing newline)

```
#define b(t)(t->left||t->right)
void f(Node*r){while(r&&b(r)){Node**p=&r,*c=b(r);while(c)p=&c,c=b(c);free(*p);*p=0;}free(r);}

```

Does not run in O(n) time. But the OP does not require it, so here's my O(n2) solution.

Algorithm: Walk down to a leaf from the root. Release it. Repeat until there are no leaves. Release the root.

Ungolfed:

```
void freeTree (Node * root) {
    while (root && (root->left || root->right)) {
        Node ** prev = &root;
        Node * curr = root->left || root->right;
        while (curr != 0) {
            prev = &curr;
            curr = curr->left || curr->right;
        }
        free(*prev);
        *prev = 0;
    }
    free(root);
}

```
> 1 votes

# Answer
## C, 150 bytes

```
f(T*r,int s){T*t[s];t[0]=r;T**f=&t[0],**e=&t[0];while(f<=e){if(*f){if((*f)->left){*++e=(*f)->left;}if((*f)->right){*++e=(*f)->right;}}free(*f);f++;}}

```

Try It On JDoodle
> 0 votes

---
Tags: code-challenge, fastest-algorithm, binary-tree
---


# Question
Title: ABAA/ABBB: Generate this recursive 2D pattern
I was messing around with infinite resistor networks (long story) when I came across the following interesting recursive pattern:

```
|-||
|---

```

Each instance of this pattern is twice as wide as it is tall. To go from one level of the pattern to the next, you break up this rectangle into two sub-blocks (each of which is a NxN square):

```
AB =
|-||
|---

so A =
|-
|-

and B =
||
--

```

These halves are then duplicated and rearranged according to the following pattern:

```
ABAA
ABBB

giving

|-|||-|-
|---|-|-
|-||||||
|-------

```

**Challenge**

Write a program/function which, given a number `N`, outputs the `N`th iteration of this recursive design. This is golf.

I/O format is relatively lenient: you may return a single string, a list of strings, a 2D array of characters, etc. Arbitrary trailing whitespace is allowed. You may also use either 0 or 1 indexing.

**Examples**

The first several iterations of the pattern are as follows:

```
N = 0
|-

N = 1
|-||
|---

N = 2
|-|||-|-
|---|-|-
|-||||||
|-------

N = 3
|-|||-|-|-|||-||
|---|-|-|---|---
|-|||||||-|||-||
|-------|---|---
|-|||-|-|-|-|-|-
|---|-|-|-|-|-|-
|-||||||||||||||
|---------------

N = 4
|-|||-|-|-|||-|||-|||-|-|-|||-|-
|---|-|-|---|---|---|-|-|---|-|-
|-|||||||-|||-|||-|||||||-||||||
|-------|---|---|-------|-------
|-|||-|-|-|-|-|-|-|||-|-|-|||-|-
|---|-|-|-|-|-|-|---|-|-|---|-|-
|-|||||||||||||||-|||||||-||||||
|---------------|-------|-------
|-|||-|-|-|||-|||-|||-|||-|||-||
|---|-|-|---|---|---|---|---|---
|-|||||||-|||-|||-|||-|||-|||-||
|-------|---|---|---|---|---|---
|-|||-|-|-|-|-|-|-|-|-|-|-|-|-|-
|---|-|-|-|-|-|-|-|-|-|-|-|-|-|-
|-||||||||||||||||||||||||||||||
|-------------------------------

```

I wonder if there is some short algebraic way to compute this structure.

# Answer
> 13 votes
# APL (Dyalog Classic), ~~29~~ 25 bytes

```
'|-'[{a,⊖⌽⍉~a←⍪⍨⍵}⍣⎕⍉⍪⍳2]

```

Try it online!

`⍳2` is the vector `0 1`

turns it into a 2x1 matrix

transposes it, so it becomes 1x2

evaluated input

`{` `}⍣⎕` apply a function that many times

`⍪⍨⍵` concatenate the argument on top of itself - a 2x2 matrix

`a←` remember as `a`

`~` negate

transpose

reverse horizontally

reverse vertically

`a,` concatenate with `a` on the left

`'|-'[` `]` use the matrix as indices in the string `'|-'`, i.e. turn 0 into `|` and 1 into `-`

# Answer
> 10 votes
# JavaScript (Node.js), ~~130~~ ... ~~106~~ ~~94~~ 92 bytes

Golfed from my alternative method and fixing the characters, -14 bytes Thanks @Shaggy

```
f=n=>n?f(n-1).replace(/.+/g,x=>(g=i=>x.replace(/./g,p=>p<i?s[i]+s[i]:s))`0`+`
`+g`1`):s="|-"

```

Try it online!

**My original approach (~~106~~ 102 bytes)**

~~```
f=n=>n?[0,1].map(j=>f(n-1).split`
`.map(x=>x+x.substr((i=x.length/2)*j,i).repeat(2)).join`
`).join`
`:"|-"

```~~

-4 bytes Thanks @Shaggy

```
f=n=>n?[0,1].map(j=>f(n-1).split`
`.map(x=>x+(y=x.substr((i=x.length/2)*j,i))+y).join`
`).join`
`:"|-"

```

Try it online!

Explanation & Ungolfed:

```
function f(n) {                     // Main Function
 if (n != 0) {                      //  If n != 0: (i.e. not the base case)
  return [0, 1].map(                //   Separate the pattern into 2 parts
  function(j) {                     //   For each part:
   return f(n - 1).split("\n")      //    Split the next depth into lines
    .map(function(x) {              //    For each line in the result:
    return x                        //     The common part: "AB"
     + x.substr(
      (i = x.length / 2) * j        //     Take A if j == 0, B if j == 1
      , i                           //     Take half the original length
     ).repeat(2);                   //     Double this part
   }).join("\n");                   //    Join all lines together
  }).join("\n");                    //   Join the two parts together
 }
 else return "|-";                  //  If not (base case): return "|-";
}

```

**My original alternative method, if `"|"->"2", "-"->"1"` is allowed, ~~105~~ 104 bytes:**

```
f=n=>n?f(n-1).replace(/[12]+/g,x=>(g=(y,i)=>y.replace(/1|2/g,p=>[,i?11:22,21][p]))(x,0)+`
`+g(x,1)):"21"

```

Try it online!

**Just figured out some algebraic method towards this problem.**

```
x=>y=>"|-||--"[(f=(x,y,t=0,m=2**30,i=!(y&m)*2+!(x&m)<<1)=>m?f(x^m,y^m,([18,0,90][t]&3<<i)>>i,m>>1):t)(x>>1,y)*2+x%2]

```

Try it online!

(finally a function which length's comparable to my original answer)

`f(n, x, y)` calculates the block type at (x, y) block at `n`th iteration of the following substitution:

```
0 => 0 1      1 => 0 0      2 => 1 1
     0 2           0 0           2 2

```

where `0 = "|-", 1 = "||", 2 = "--"`, starting from `f(0, 0, 0) = 0`.

Then, `g(x)(y)` calculates the symbol at (x, y) of the original pattern.

# Answer
> 9 votes
# Stax, 24 ~~17~~ 15 bytes

```
╛ä├¼àz[{╧↑;ε╖>╠

```

Run and debug it

Here's the ascii representation of the same program.

```
'|'-{b\2*aa+c\}N\m

```

The basic idea is start with the 0-generation grid, and then repeat a block that expands the grid.

```
'|'-                    Push "|" and "-"
     {         }N       Get input and repeat block that many times.
      b                 Copy two top stack values
       \2*              Zip two parts, and double the height
          aa            Roll the top of the stack down to 3rd position.
            +           Concatenate two grids vertically
             c\         Copy result and zip horizontally
                  \     Zip the two parts horizontally
                   m    Output each row

```

# Answer
> 8 votes
# Canvas, ~~17~~ 16 bytes

```
|∙-╶［∔αω＋：∔；：＋｝＋

```

Try it here!

Explanation, showing the stack for the input of 1:

```
|∙-               push "|" and "-" - the initial halves  "|", "-"
   ╶[         }   repeat input times
     ∔              add the two parts vertically         "|¶-"
      αω            get the original arguments to that   "|¶-", "|", "-"
        +           and add those horizontally           "|¶-", "|-"
         :∔         and add to itself vertically         "|¶-", "|-¶|-"
           ;        get the vertically added parts       "|-¶|-", "|¶-"
            :+      and add to itself horizontally       "|-¶|-", "||¶--"
               +  finally, add the halves together       "|-||¶|---"

```

Updated to 16 bytes by fixing a bug where the values set for `α`/`ω` to work weren't copied properly (Canvas is supposed to be fully immutable, but, alas, it wasn't).

# Answer
> 6 votes
# Python 2, ~~88~~ 77 bytes

<sup>-11 bytes thansk to Lynn</sup>

```
f=lambda x:x<1and['|-']or[n+2*n[i:i+2**x/2]for i in(0,2**x/2)for n in f(x-1)]

```

Try it online!

# Answer
> 4 votes
# Perl 5, 72 bytes

```
@1='|-';$l=@1,map{/.{$l}/;push@1,$_.$' x2;$_.=$&x2}@1for 1..<>;say for@1

```

Try it online!

# Answer
> 4 votes
# Husk, 17 bytes

```
!¡§z+DȯṁmDTm½;"|-

```

1-indexed. Try it online!

## Explanation

```
!¡§z+DȯṁmDTm½;"|-  Implicit input: a number n.
              "|-  The string "|-".
             ;     Wrap in a list: ["|-"]
 ¡                 Iterate this function on it:
                    Argument is a list of lines, e.g. L = ["|-||","|---"]
           m½       Break each line into two: [["|-","||"],["|-","--"]]
          T         Transpose: [["|-","|-"],["||","--"]]
      ȯṁ            Map and concatenate:
        mD           Map self-concatenation.
                    Result: ["|-|-","|-|-","||||","----"]
   z+               Zip using concatenation
  §  D              with L concatenated to itself: ["|-|||-|-","|---|-|-","|-||||||","|-------"]
                   Result is the infinite list [["|-"],["|-||","|---"],["|-|||-|-","|---|-|-","|-||||||","|-------"],...
!                  Take n'th element, implicitly display separated by newlines.

```

# Answer
> 3 votes
# Jelly, ~~21~~ 19 bytes

```
;"/;`,Ẏ;`€$
⁾|-Ç¡ZY

```

Try it online!

---

Explanation:

Initially, the value is `⁾|-`, that is `["|","-"]`.

The last link (`Ç`), given `[A, B]`, will return

```
   AB     AA
[  AB  ,  BB  ]

```

. The `¡` repeatedly apply the last link (input) number of times, and `ZY` formats it.

Explanation for last link:

```
-----------------
;"/;`,Ẏ;`€$  Monadic link. Value = [A, B]
;"/          Accumulate vectorized concatenate. Calculates (A ;" B).
             Represented as a matrix, it's |AB| (concatenated horizontally)
   ;`        Concatenate with self.      |AB|
                                Value =  |AB|  (concatenate vertically)
     ,    $  Pair with ...
      Ẏ        Tighten.  |A|    (concatenate vertically)
                 Value = |B|
       ;`€     Concatenate each with self.    |AA|
                                      Value = |BB|  (duplicate horizontally)

```

# Answer
> 2 votes
# Clean, ~~121~~ 106 bytes

```
import StdEnv
$0=[['|-']]
$n#z=map(splitAt(2^n/2))($(n-1))
=[u++v++u++u\\(u,v)<-z]++[u++v++v++v\\(u,v)<-z]

```

Try it online!

# Answer
> 2 votes
# Haskell, 86 bytes

```
(%)=zipWith(++)
f 0=["|-"]
f n|(a,b)<-unzip$splitAt(2^(n-1))<$>f(n-1)=a%b%a%a++a%b%b%b

```

Try it online!

Pretty simple. Output is a list of strings. We take the previous version and split each line in half then collect those into two new lists using `unzip`. Then it's simply a matter of combining the arrays together the right way

# Answer
> 1 votes
# Charcoal, ~~47~~ 46 bytes

```
Ｍ²↖|-¶¶ＦＥＮＸ²ι«Ｆ²Ｃ±ι⁰Ｃ⁰ιＣ⊗ι±ιＣ×³ι±ι≦⊗ιＭ±ι±ιＴ⊗ιι

```

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

```
Ｍ²↖|-¶¶

```

In order to get a consistent cursor position for the following loop, I have to print step 0 at position (-2, -2) and leave the cursor at (-2, 0). (This might be due to a bug in Charcoal.)

```
ＦＥＮＸ²ι«

```

Loop over the first `N` powers of 2.

```
Ｆ²Ｃ±ι⁰Ｃ⁰ιＣ⊗ι±ιＣ×³ι±ι

```

Make copies of the previous output with various offsets resulting in a canvas that contains the desired next step in a rectangle within it.

```
≦⊗ιＭ±ι±ιＴ⊗ιι

```

Move to the position of that rectangle and trim the canvas.

Alternative solution, also 46 bytes:

```
Ｍ²→|-ＦＥＮＸ²ι«Ｆ432Ｃ×Ｉκι×³ιＦ245Ｃ×Ｉκι⊗ι≦⊗ιＪ⊗ιιＴ⊗ιι

```

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

```
Ｍ²→|-

```

This time step 0 has to be printed at position (2, 0), but at least the cursor position doesn't matter.

```
ＦＥＮＸ²ι«

```

Loop over the first `N` powers of 2.

```
Ｆ432Ｃ×Ｉκι×³ιＦ245Ｃ×Ｉκι⊗ι

```

Make copies of the previous output with various offsets resulting in a canvas that contains the desired next step in a rectangle within it.

```
≦⊗ιＪ⊗ιιＴ⊗ιι

```

Move to the position of that rectangle and trim the canvas.

# Answer
> 1 votes
# , 49 bytes

```
f=.3 :'''|-''{~((,.[:|.[:|."1[:|:-.)@,~)^:y,:0 1'

```

A clumsy translation of ngn's APL solution. I had problems making it tacit - I'll apreciate any advice.

Try it online!

# Answer
> 1 votes
# , 126 bytes

```
function(n,k=cbind){o=matrix(c("|","-"),1,2)
if(n>0)for(i in 1:n)o=rbind(k(a<-o[,x<-1:(2^(i-1))],b<-o[,-x],a,a),k(a,b,b,b))
o}

```

Try it online!

Returns a `matrix`. There's a bit of code in the TIO link to get it to print nicely for ease of verification.

# Answer
> 1 votes
# K (ngn/k), 25 bytes

```
{"|-"x{x,'|+|~x:x,x}/,!2}

```

Try it online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~67~~ 65 bytes

```
SubstitutionSystem[{"|"->{i={"|","-"},i},"-"->{i,i}},{i},{#}]&

```

Try it online!

Straightforward implementation of the recursion. Returns an array of characters wrapped in a list.

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


title: Is it checkmate?

text:
# Question
Title: Is it checkmate?
Wholly surprised this hasn't been posted already, given the large number of chess puzzles on the site. While I thought of this myself, credit to Anush for posting it to the sandbox back in March. But I figured it's been long enough that I could go ahead and do so myself.

A checkmate in chess is a position in which the king is attacked and there is no move that can defend it. If you aren't familiar with how chess pieces move, you can familiarize yourself on Wikipedia.

# The challenge

For this challenge, your input will be the position of a chess board in whatever notation you like. To clarify, your input will describe the pieces on a chess board, with their colors and positions, along with the possible en passant capture square, if any. (Ability to castle is irrelevant as you cannot castle out of check.) You may find FEN notation useful, but any convenient format is fine. For simplicity, **you can assume it's Black to play** \- this means Black will always be the checkmated player. A position where White is in check, checkmate, or stalemate will be considered invalid for this challenge.

You must output a truthy value if the position is checkmate, and a falsey value if it is not. Note that **stalemate is not checkmate** \- the king must be attacked!

# Truthy test cases

> 1k5R/6R1/8/8/8/8/8/6K1 b - -
>
> rn2r1k1/pp1p1pQp/3p4/1b1n4/1P2P3/2B5/P5PP/R3K2R b - -
>
> kr5R/rB6/8/8/8/5Q2/6K1/R7 b - -
>
> 2K5/1B6/8/8/8/7N/R7/R3r2k b - - 0 1
>
> 8/4Q1R1/R7/5k2/3pP3/5K2/8/8 b - -
>
> 2K5/1B6/8/8/8/4b2N/R7/4r2k b - -

# Falsey test cases

> rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq -
>
> 8/8/8/8/8/1KQ5/4N3/1k6 b - -
>
> 2K5/1B6/8/8/8/7N/R7/4r2k b - -
>
> 8/8/2Q5/3k4/3Q5/8/8/7K b - -
>
> 8/4Q1R1/R7/5k2/3pP3/5K2/8/8 b - e3 (Watch that en passant!)

Code golf - shortest code in bytes wins. Good luck!

# Answer
> 12 votes
# JavaScript (Node.js),  ~~499 ... 374~~  370 bytes

Takes input as `(b)(X)`, where \\$b\\$ is an array of 64 integers describing the squares (from left to right and from top to bottom) and \\$X\\$ is the 0-based index of the en-passant target square, or \\$-1\\$ if there's none.

Below are the expected values for each square:

```
 0: empty square

 5: white pawn      6: black pawn
 9: white king     10: black king
17: white bishop   18: black bishop
33: white rook     34: black rook
49: white queen    50: black queen
65: white knight   66: black knight

```

Returns \\$64\\$ for checkmate, or \\$0\\$ for not-checkmate.

```
b=>e=>(g=(c,k)=>b.map((v,p,h,s=p+(p&~7),M=t=>v&-~c?c?(B=[...b],K&=g(b[t?b[T]=b[p]:b[b[e-8]=0,e]=6,p]=0),b=B):k|=V&8:0,m=([a],[x,t,...d]=Buffer(a))=>d.map(c=>(h=n=>(V=(a+=c-66)&136?3:b[T=a+a%8>>1])&v&3||t>>!V&v>>x&n>31&&h(n-4/!V,M``))(t,a=s)))=>(v=b[p],m`##123ACQRS`,m`$?13QS`,m`%?2ACR`,m`&#!#04PTac`,c?(p-e+8.5&~1||M(),m`"!QS`,p<16?m`"&R`:m`""R`):m`"!13`))|k)(1,K=g())*K

```

Try it online!

## How?

### Board representation

We use the classic 0x88 board representation, so that out-of-bounds target squares can be easily detected.

```
   |  a    b    c    d    e    f    g    h
---+----------------------------------------
 8 | 0x00 0x01 0x02 0x03 0x04 0x05 0x06 0x07
 7 | 0x10 0x11 0x12 0x13 0x14 0x15 0x16 0x17
 6 | 0x20 0x21 0x22 0x23 0x24 0x25 0x26 0x27
 5 | 0x30 0x31 0x32 0x33 0x34 0x35 0x36 0x37
 4 | 0x40 0x41 0x42 0x43 0x44 0x45 0x46 0x47
 3 | 0x50 0x51 0x52 0x53 0x54 0x55 0x56 0x57
 2 | 0x60 0x61 0x62 0x63 0x64 0x65 0x66 0x67
 1 | 0x70 0x71 0x72 0x73 0x74 0x75 0x76 0x77

```

### Move encoding

Each set of moves is encoded with 5 parameters:

* the type of piece
* the maximum number of squares that can be visited in each direction
* a flag telling if captures are allowed
* a flag telling if non-captures are allowed
* a list of directions

All these parameters are packed into a single string. For instance, knight moves are encoded as follows:

```
`&#!#04PTac`
 ||\______/
 ||    |                            +------> 0 + 1 = 1 square in each direction
 ||    |                            | +----> standard moves allowed
 ||    +---> 8 directions           | |+---> captures allowed
 ||                                / \||
 |+--------> ASCII code = 35 = 0b0100011
 |
 +---------> 1 << (ASCII code MOD 32) = 1 << 6 = 64

```

To decode a direction, we subtract \\$66\\$ from its ASCII code:

```
 char. | ASCII code | -66
-------+------------+-----
  '!'  |     33     | -33
  '#'  |     35     | -31
  '0'  |     48     | -18
  '4'  |     52     | -14
  'P'  |     80     | +14
  'T'  |     84     | +18
  'a'  |     97     | +31
  'c'  |     99     | +33

```

which gives:

```
 [ - ] [-33] [ - ] [-31] [ - ]
 [-18] [ - ] [ - ] [ - ] [-14]
 [ - ] [ - ] [ N ] [ - ] [ - ]
 [+14] [ - ] [ - ] [ - ] [+18]
 [ - ] [+31] [ - ] [+33] [ - ]

```

All sets of moves are summarized in the following table, except en-passant captures which are processed separately.

```
  string    | description             | N | S | C | directions
------------+-------------------------+---+---+---+----------------------------------------
 &#!#04PTac | knight                  | 1 | Y | Y | -33, -31, -18, -14, +14, +18, +31, +33
 ##123ACQRS | king                    | 1 | Y | Y | -17, -16, -15, -1, +1, +15, +16, +17
 "!13       | white pawn / captures   | 1 | N | Y | -17, -15
 "!QS       | black pawn / captures   | 1 | N | Y | +15, +17
 "&R        | black pawn / advance x2 | 2 | Y | N | +16
 ""R        | black pawn / advance x1 | 1 | Y | N | +16
 $?13QS     | bishop or queen         | 8 | Y | Y | -17, -15, +15, +17
 %?2ACR     | rook or queen           | 8 | Y | Y | -16, -1, +1, +16

```

### Commented

```
b => e => (
  // generate all moves for a given side
  g = (c, k) =>
    b.map((
      v, p, h,
      // s = square index in 0x88 format
      s = p + (p & ~7),
      // process a move
      M = t =>
        // make sure that the current piece is of the expected color
        v & -~c ?
          c ?
            // Black's turn: play the move
            ( // board backup
              B = [...b],
              // generate all White moves ...
              K &= g(
                // ... after the board has been updated
                b[
                  t ?
                    // standard move
                    b[T] = b[p]
                  :
                    // en-passant capture
                    b[b[e - 8] = 0, e] = 6,
                  p
                ] = 0
              ),
              // restore the board
              b = B
            )
          :
            // White's turn: just update the king's capture flag
            k |= V & 8
        :
          0,
      // generate all moves of a given type for a given piece
      m = ([a], [x, t, ...d] = Buffer(a)) =>
        d.map(c =>
          ( h = n =>
            ( // advance to the next target square
              V = (a += c - 66) & 136 ? 3 : b[T = a + a % 8 >> 1]
            )
            // abort if it's a border or a friendly piece
            & v & 3 ||
            // otherwise: if this kind of move is allowed
            t >> !V &
            // and the current piece is of the expected type
            v >> x &
            // and we haven't reached the maximum number of squares,
            n > 31 &&
            // process this move (if it's a capture, force n to
            // -Infinity so that the recursion stops)
            h(n - 4 / !V, M``)
          )(t, a = s)
        )
    ) =>
      (
        v = b[p],
        // king
        m`##123ACQRS`,
        // bishop or queen
        m`$?13QS`,
        // rook or queen
        m`%?2ACR`,
        // knight
        m`&#!#04PTac`,
        c ?
          // black pawn
          ( // en-passant capture
            p - e + 8.5 & ~1 || M(),
            // standard captures
            m`"!QS`,
            // standard moves
            p < 16 ? m`"&R` : m`""R`
          )
        :
          // white pawn (standard captures only)
          m`"!13`
      )
    ) | k
// is the black king in check if the Black don't move?
// is it still in check after each possible move?
)(1, K = g()) * K

```

# Answer
> 6 votes
# Haskell, ~~1165~~ ~~1065~~ 1053 bytes

*Bytes saved thanks to Leo Tenenbaum*

```
n=Nothing
x?y=Just(x,y)
o(x,y)=x<0||y<0||x>7||y>7
m#k@(x,y)|o k=n|1>0=m!!x!!y
z(x,y)m p(a,b)|o(x+a,y+b)=1<0|Just g<-m#(x+a,y+b)=elem g[(p,0),(5,0)]|1>0=z(x+a,y+b)m p(a,b)
t(x,y)p(a,b)m|o(x+a,y+b)=[]|g<-(x+a,y+b)=(g%p)m++do[0|m#g==n];t g p(a,b)m
c m|(x,y):_<-[(a,b)|a<-u,b<-u,m#(a,b)==6?1],k<-z(x,y)m=or$[m#(x+a,y+b)==6?0|a<-0:s,b<-0:s]++do a<-s;[k 3(a,b)|b<-s]++(k 2<$>[(a,0),(0,a)])++[m#l==4?0|b<-[2,-2],l<-[(x+a,y+b),(x+b,y+a)]]++[m#(x-1,y+a)==p?0|p<-[0,1]]
c m=1>0
(k%p)m=[[[([p|a==k]++[m#a])!!0|a<-(,)b<$>u]|b<-u]|not$o k]
w(Just(_,1))=1<0
w x=1>0
m!u@(x,y)|g<-m#u,Just(q,1)<-g,v<-((u%n)m>>=),r<-v.t u g,k<-(do[0|n==m#(x+1,y)];(u%n)m>>=(x+1,y)%g)++(do a<-s;[0|n<m#(x+1,y+a)];v$(x+1,y+a)%g)++(do[0|(x,n,n)==(1,m#(x+1,y),m#(x+2,y))];v$(x+2,y)%g)++(do a<-s;[0|1?0==m#(x,y+a)];v((x,y+a)%n)>>=(x+1,y+a)%g)=[k,k,do a<-s;[(a,0),(0,a)]>>=r,do a<-s;b<-s;r(a,b),do a<-s;b<-[2,-2];l<-[(x+a,y+b),(x+b,y+a)];v$l%g,do a<-0:s;b<-[0|a/=0]++s;r(a,b),do a<-[x-1..x+1];b<-[y-1..y+1];[0|w$m#(a,b)];v$(a,b)%g]!!q
m!u=[]
u=[0..7]
s=[1,-1]
q m=all c$m:do a<-u;b<-u;m!(a,b)

```

Try it online!

~~This is not exactly well golfed as of now, but it is a start.~~ With some help along the way I've now golfed this down pretty aggressively (and fixed an error along the way).

The one perhaps questionable thing this does is that it assumes that, other than by a king or a pawn en passant, you can never get out of check by capturing one of your own pieces. In chess you are not allowed to make this move but my program considers these moves to save bytes under the assumption that if you are in check this can never get you out of it.

This assumption is valid because such moves

1. Cannot capture the piece that is attacking the king, since the piece they capture is black.
2. Cannot block the path of the piece that is attacking the king, since the captured black piece would have already been doing that.

We also add the additional stipulation that if you have no king you are in check.

This program also makes the assumption that if there is a pawn that can be captured en passant, then the pawn was the last piece to move and that move was a legal move. This is because the program does not check if the square it moves the black pawn to is empty so if there is a piece there things can get a little screwy. However this cannot be obtained if the last move was a legal move and furthermore cannot be represented in FEN. So this assumption seems rather solid.

Here is my "ungolfed" version for reference:

```
import Control.Monad
out(x,y)=x<0||y<0||x>7||y>7
at b (x,y)
  |out(x,y)=Nothing
  |otherwise=(b!!x)!!y
inLine (x,y) ps m (a,b)
  | out (x+a,y+b) = False
  | elem (m `at` (x+a,y+b)) $ Just <$> ps = True
  | m `at` (x+a,y+b) == Nothing = inLine (x+a,y+b) ps m (a,b)
  | otherwise = False
goLine (x,y) p (a,b)m
  | out (x+a,y+b) = []
  | otherwise = case m `at` (x+a,y+b) of
--    Just (n,1) -> []
    Just (n,_) -> set(x+a,y+b)p m
    Nothing    -> set(x+a,y+b)p m ++ goLine(x+a,y+b)p(a,b)m
checkBishop (x,y) m=or[inLine(x,y)[(3,0),(5,0)]m(a,b)|a<-[1,-1],b<-[1,-1]]
checkRook   (x,y) m=or$do
  a<-[1,-1]
  inLine(x,y)[(2,0),(5,0)]m<$>[(a,0),(0,a)]
checkKnight (x,y) m=any((==Just(4,0)).(at m))$do
  a<-[1,-1]
  b<-[2,-2]
  [(x+a,y+b),(x+b,y+a)]
checkPawn (x,y) m=or[at m a==Just(p,0)|a<-[(x-1,y+1),(x-1,y-1)],p<-[0,1]]
checkKing (x,y) m=or[at m(a,b)==Just(6,0)|a<-[x-1..x+1],b<-[y-1..y+1]]
check m
  | u:_<-[(a,b)|a<-[0..7],b<-[0..7],(m!!a)!!b==Just(6,1)] =
    checkBishop u m ||
    checkRook   u m ||
    checkKnight u m ||
    checkPawn   u m ||
    checkKing   u m
  | otherwise = True
set (x,y) p m=[[[head$[p|(a,b)==(y,x)]++[(m!!b)!!a]|a<-[0..7]]|b<-[0..7]]|not$out(x,y)]
white(Just(n,0))=True
white x=False
moves m (x,y)
 |g<-m `at` (x,y)=case g of
  Just(2,1) -> do
    a<-[1,-1]
    b<-[(a,0),(0,a)]
    set(x,y)Nothing m>>=goLine (x,y) g b
  Just(3,1) -> do
    a<-[1,-1]
    b<-[1,-1]
    set(x,y)Nothing m>>=goLine (x,y) g(a,b)
  Just(4,1) -> do
    n<-set(x,y)Nothing m
    a<-[1,-1]
    b<-[2,-2]
    l<-[(x+a,y+b),(x+b,y+a)]
    -- guard$white$n `at` l
    set l g n
  Just(5,1) -> do
    a<-[1,-1]
    c<-[(a,0),(0,a),(a,1),(a,-1)]
    set(x,y)Nothing m>>=goLine (x,y) g c
  Just(6,1) -> do
    a<-[x-1..y+1]
    b<-[x-1..y+1]
    guard$white(m `at`(a,b))||Nothing==m`at`(a,b)
    set(x,y)Nothing m>>=set(a,b)g
  Just(n,1) -> (do
    guard$Nothing==m `at` (x+1,y)
    set(x,y)Nothing m>>=set(x+1,y)g) ++ (do
      a<-[1,-1]
      guard$white$m`at`(x+1,y+a)
      set(x,y)Nothing m>>=set(x+1,y+a)g) ++ (do
        guard$(x,Nothing,Nothing)==(1,m`at`(x+1,y),m`at`(x+1,y))
        set(x,y)Nothing m>>=set(x+2,y)g) ++ (do
          a<-[1,-1]
          guard$Just(1,0)==m`at`(x,y+a)
          set(x,y)Nothing m>>=set(x,y+a)Nothing>>=set(x+1,y+a)g)
  _ -> []
checkmate m=all check$m:do
  a<-[0..7]
  b<-[0..7]
  moves m(a,b)

```

Try it online!

# Answer
> 1 votes
# Python 3 (PyPy), 729 bytes

```
F=lambda a,b:a<'^'<=b or a>'^'>=b
def m(b,P,A=0):
 yield b
 for(r,f),p in b.items():
  if F(P,p):continue
  *d,n,k={'R':[(0,1),8,4],'N':[(1,2),(2,1),2,4],'B':[(1,1),8,4],'Q':[(0,1),(1,1),8,4],'K':[(0,1),(1,1),2,4],'P':[(2,0),(1,0),(1,1),(1,-1),2,1],'p':[(-2,0),(-1,0),(-1,1),(-1,-1),2,1]}[p if p=='p'else p.upper()]
  if p in'pP':d=d[d!=[2,7][p=='p']+A:]
  for u,v in d:
   for j in range(k):
    for i in range(1,n):
     U=r+u*i;V=f+v*i;t=b.get((U,V),'^')
     if U<1or U>8or V<1 or V>8:break
     if F(p,t):
      B=dict(b);B[(U,V)]=B.pop((r,f))
      if t in'eE':B.pop(([U+1,U-1][t=='e'],V))
      yield B
     if t not in'^eE':break
    u,v=v,-u
M=lambda b:all(any('k'not in C.values()for C in m(B,'W',1))for B in m(b,'b'))

```

Try it online!

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


title: Calculate Landau's function

text:
# Question
Title: Calculate Landau's function
Landau's function \\$g(n)\\$ (OEIS A000793) gives the maximum order of an element of the symmetric group \\$S\_n\\$. Here, the order of a permutation \\$\pi\\$ is the smallest positive integer \\$k\\$ such that \\$\pi^k\\$ is the identity - which is equal to the least common multiple of the lengths of the cycles in the permutation's cycle decomposition. For example, \\$g(14) = 84\\$ which is achieved for example by (1,2,3)(4,5,6,7)(8,9,10,11,12,13,14).

Therefore, \\$g(n)\\$ is also equal to the maximum value of \\$\operatorname{lcm}(a\_1, \ldots, a\_k)\\$ where \\$a\_1 + \cdots + a\_k = n\\$ with \\$a\_1, \ldots, a\_k\\$ positive integers.

## Problem

Write a function or program that calculates Landau's function.

## Input

A positive integer \\$n\\$.

## Output

\\$g(n)\\$, the maximum order of an element of the symmetric group \\$S\_n\\$.

## Examples

```
n    g(n)
1    1
2    2
3    3
4    4
5    6
6    6
7    12
8    15
9    20
10   30
11   30
12   60
13   60
14   84
15   105
16   140
17   210
18   210
19   420
20   420

```

## Score

This is : Shortest program in bytes wins. (Nevertheless, shortest implementations in multiple languages are welcome.)

Note that there are no requirements imposed on run-time; therefore, your implementation does not necessarily need to be able to generate all the above example results in any reasonable time.

Standard loopholes are forbidden.

# Answer
> 10 votes
# 05AB1E, 6 bytes

```
Åœ€.¿Z

```

Try it online!

```
    Åœ       # integer partitions of the input
      €.¿    # lcm of each
         Z   # maximum

```

# Answer
> 10 votes
# Wolfram Language (Mathematica), 44 bytes

```
Max[PermutationOrder/@Permutations@Range@#]&

```

Try it online!

# Wolfram Language (Mathematica), 31 bytes

@DanielSchepler has a better solution:

```
Max[LCM@@@IntegerPartitions@#]&

```

Try it online!

# Answer
> 4 votes
# Haskell, 44 bytes

```
(%1)
n%t=maximum$t:[(n-d)%lcm t d|d<-[1..n]]

```

Try it online!

# Answer
> 4 votes
# Python, 87 bytes

```
f=lambda n,d=1:max([f(m,min(range(d,d<<n,d),key=(n-m).__rmod__))for m in range(n)]+[d])

```

Try it online!

A recursive function that tracks the remaining `n` to partition and the running LCM `d`. Note that this means we don't need to track the actual numbers in the partition or how many of them we've used. We try each possible next part, `n-m`, replacing `n` with what's left `m`, and `d` with `lcm(d,n-m)`. We take the maximum of those recursive results and `d` itself. When nothing remains `n=0`, the result ist just `d`.

The tricky thing is that Python doesn't have any built-ins for LCM, GCD, or prime factorization. To do `lcm(d,m-n)`, we generate a list of multiples of `d`, and take the value attaining the minimum modulo `n-m`, that is with `key=(n-m).__rmod__`. Since `min` will give the earlier value in case of a tie, this is always the first nonzero multiple of `d` that's divisible by `n-m`, so their LCM. We only multiples of `d` up to `d*(n-m)` to be guaranteed to hit the LCM, but it's shorter to write `d<<n` (which is `d*2**n`) which suffices with Python's upper bounds being exclusive.

Python 3's `math` library has `gcd` (but not `lcm`) after 3.5, which is a few bytes shorter. Thanks to @Joel for shortening the import.

**Python 3.5+, 84 bytes**

```
import math
f=lambda n,d=1:max([f(m,d*(n-m)//math.gcd(n-m,d))for m in range(n)]+[d])

```

Try it online!

Using `numpy`'s `lcm` is yet shorter.

**Python with numpy, 77 bytes**

```
from numpy import*
f=lambda n,d=1:max([f(m,lcm(d,n-m))for m in range(n)]+[d])

```

Try it online!

# Answer
> 3 votes
# Jelly, 7 bytes

```
Œṗæl/€Ṁ

```

Try it online!

A monadic link taking an integer as its argument and returning an integer.

## Explanation

```
Œṗ      | Integer partitions
  æl/€  | Reduce each using LCM
      Ṁ | Maximum

```

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

Computes the maximum value of \\$\operatorname{lcm}(a\_1,\ldots,a\_k)\\$ where \\$a\_1+\ldots+a\_k\\$ is a partition of \\$n\\$.

```
f=(n,i=1,l=m=0)=>n?i>n?m:f(n-i,i,l*i/(G=(a,b)=>b?G(b,a%b):a)(l,i)||i)&f(n,i+1,l)|m:m=l>m?l:m

```

Try it online!

---

# JavaScript (ES6), 95 bytes

```
f=(n,i=1,m)=>i>>n?m:f(n,i+1,i<m|(g=(n,k=2,p=0)=>k>n?p:n%k?p+g(n,k+1):g(n/k,k,p*k||k))(i)>n?m:i)

```

Try it online!

### How?

We define:

$$\cases{ g(1)=0\\ g(n)=\sum\_{j=1}^{N}{p\_j}^{k\_j}\quad\text{for}\enspace n\>1\enspace\text{and}\enspace n=\prod\_{j=1}^{N}{p\_j}^{k\_j} }$$

(this is A008475)

Then we use the formula (from A000793):

$$f(n)=\max\_{g(k)\le n}k$$

# Answer
> 3 votes
# Perl 6, 50 bytes

```
{max .map:{+(.[$_],{.[@^a]}...$_,)}}o&permutations

```

Try it online!

Checks all permutations directly, like @histocrat's Ruby solution.

### Explanation

```
                                     &permutations  # Permutations of [0;n)
{                                  }o  # Feed into block
     .map:{                       }  # Map permutations
                           ...  # Construct sequence
             .[$_]  # Start with permutation applied to itself [1]
                  ,{.[@^a]}  # Generate next item by applying permutation again
                              $_,  # Until it matches original permutation [2]
           +(                    )  # Length of sequence
 max  # Find maximum

```

1 We can use any sequence of n distinct items for the check, so we simply take the permutation itself.

2 If the endpoint is a container, the `...` sequence operator smartmatches against the first item. So we have to pass a single-element list.

# Answer
> 2 votes
# Gaia, ~~25~~ ~~23~~ 22 bytes

```
,:Π¤d¦&⊢⌉/
1w&ḍΣ¦¦⇈⊢¦⌉

```

Try it online!

Not having LCM or integer partitions makes this approach rather long.

```
,:Π¤d¦&⊢⌉/		;* helper function: LCM of 2 inputs

1w&ḍΣ¦¦			;* push integer partitions
         ¦		;* for each
       ⇈⊢		;* Reduce by helper function
	  ⌉		;* and take the max

```

# Answer
> 2 votes
# Ruby, 77 bytes

```
f=->n{a=*0...n;a.permutation.map{|p|(1..).find{a.map!{|i|p[i]}==a.sort}}.max}

```

Try it online!

`(1..)` infinite range syntax is too new for TIO, so the link sets an arbitrary upper bound.

This uses the direct definition--enumerate all possible permutations, then test each one by mutating `a` until it gets back to its original position (which also conveniently means I can just mutate the original array in each loop).

# Answer
> 2 votes
## Haskell, ~~70~~ 67 bytes

```
f n=maximum[foldl1 lcm a|k<-[1..n],a<-mapM id$[1..n]<$[1..k],sum a==n]

```

Try it online!

Edit: -3 bytes thanks to @xnor.

# Answer
> 1 votes
# Python 3 \+ numpy, 115 102 99 bytes

*-13 bytes thanks to @Daniel Shepler*

*-3 more bytes from @Daniel Shepler*

```
import numpy
c=lambda n:[n]+[numpy.lcm(i,j)for i in range(1,n)for j in c(n-i)]
l=lambda n:max(c(n))

```

Try it online!

Brute force method: find all possible sequences a,b,c,... where a+b+c+...=n, then pick the one with the highest lcm.

# Answer
> 0 votes
# Pyth, ~~24~~ 15 bytes

```
eSm.U/*bZibZd./

```

Try it online!

```
             ./Q  # List of partitions of the input
  m               # map that over lambda d:
   .U       d     # reduce d (with starting value first element of the list) on lambda b,Z:
     /*bZgbZ      # (b * Z) / GCD(b, Z)
 S                # this gives the list of lcms of all partitions. Sort this
e                 # and take the last element (maximum)

```

-9 bytes: paid attention and noticed that Pyth actually has a GCD builtin (`i`).

---
Tags: code-golf, math, arithmetic, permutations, integer-partitions
---