title: Generate a Walsh Matrix

text:
# Question
Title: Generate a Walsh Matrix
A **Walsh matrix** is a special kind of square matrix with applications in quantum computing (and probably elsewhere, but I only care about quantum computing).

### Properties of Walsh matrices

The dimensions are the same power of 2. Therefore, we can refer to these matrices by two's exponent here, calling them`W(0)`, `W(1)`, `W(2)`...

`W(0)` is defined as `[[1]]`.

For `n>0`, `W(n)` looks like:

```
[[W(n-1)  W(n-1)]
 [W(n-1) -W(n-1)]]

```

So `W(1)` is:

```
[[1  1]
 [1 -1]]

```

And `W(2)` is:

```
[[1  1  1  1]
 [1 -1  1 -1]
 [1  1 -1 -1]
 [1 -1 -1  1]]

```

The pattern continues...

### Your task

Write a program or function that takes as input an integer `n` and prints/returns `W(n)` in any convenient format. This can be an array of arrays, a flattened array of booleans, a `.svg` image, you name it, as long as it's correct.

Standard loopholes are forbidden.

### A couple things:

For `W(0)`, the `1` need not be wrapped even once. It can be a mere integer.

You are allowed to 1-index results—`W(1)` would then be `[[1]]`.

### Test cases

```
0 -> [[1]]
1 -> [[1  1]
      [1 -1]]
2 -> [[1  1  1  1]
      [1 -1  1 -1]
      [1  1 -1 -1]
      [1 -1 -1  1]]
3 -> [[1  1  1  1  1  1  1  1]
      [1 -1  1 -1  1 -1  1 -1]
      [1  1 -1 -1  1  1 -1 -1]
      [1 -1 -1  1  1 -1 -1  1]
      [1  1  1  1 -1 -1 -1 -1]
      [1 -1  1 -1 -1  1 -1  1]
      [1  1 -1 -1 -1 -1  1  1]
      [1 -1 -1  1 -1  1  1 -1]]

```

`8 ->` Pastebin

This is , so the shortest solution in each language wins! Happy golfing!

# Answer
> 7 votes
# Perl 6, ~~63~~ ~~44~~ 40 bytes

```
{map {:3(.base(2))%2},[X+&] ^2**$_ xx 2}

```

Try it online!

Non-recursive approach, exploiting the fact that the value at coordinates x,y is `(-1)**popcount(x&y)`. Returns a flattened array of Booleans.

-4 bytes thanks to xnor's bit parity trick.

# Answer
> 11 votes
# MATL, 4 bytes

```
W4YL

```

Try it online!

**How it works:**

```
W       % Push 2 raised to (implicit) input
4YL     % (Walsh-)Hadamard matrix of that size. Display (implicit)

```

---

Without the built-in: **11 bytes**

```
1i:"th1M_hv

```

Try it online!

**How it works**:

For each Walsh matrix **W**, the next matrix is computed as \[**W** **W**; **W****W**\], as is described in the challenge. The code does that `n` times, starting from the 1×1 matrix \[1\].

```
1       % Push 1. This is equivalent to the 1×1 matrix [1]
i:"     % Input n. Do the following n times
  t     %   Duplicate
  h     %   Concatenate horizontally
  1M    %   Push the inputs of the latest function call
  _     %   Negate
  h     %   Concatenate horizontally
  v     %   Concatenate vertically
        % End (implicit). Display (implicit)

```

# Answer
> 7 votes
# Haskell, ~~57~~ 56 bytes

```
(iterate(\m->zipWith(++)(m++m)$m++(map(0-)<$>m))[[1]]!!)

```

Try it online! This implements the given recursive construction.

*-1 byte thanks to Ørjan Johansen!*

# Answer
> 5 votes
# Octave with builtin, ~~18~~ 17 bytes

```
@(x)hadamard(2^x)

```

Try it online!

# Octave without builtin, ~~56 51~~ 47 bytes

```
function r=f(x)r=1;if x,r=[x=f(x-1) x;x -x];end

```

Try it online! Thanks to @Luis Mendo for -4.

# Octave with recursive lambda, ~~54 53 52~~ 48 bytes

```
f(f=@(f)@(x){@()[x=f(f)(x-1) x;x -x],1}{1+~x}())

```

Try it online! Thanks to this answer and this question for inspiration.

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

```
(⍪⍨,⊢⍪-)⍣⎕⍪1

```

Try it online!

Output is a 2-dimensional array.

# Answer
> 4 votes
# Python 2, ~~75~~ 71 bytes

```
r=range(2**input())
print[[int(bin(x&y),13)%2or-1for x in r]for y in r]

```

Try it online!

The Walsh Matrix seems to be related to the evil numbers. If `x&y` (bitwise and, 0-based coordinates) is an evil number, the value in the matrix is `1`, `-1` for odious numbers. The bit parity calculation `int(bin(n),13)%2` is taken from Noodle9's comment on this answer.

# Answer
> 4 votes
# , ~~61~~ ~~56~~ ~~53~~ 50 bytes

```
w=function(n)"if"(n,w(n-1)%x%matrix(1-2*!3:0,2),1)

```

Try it online!

Recursively calculates the matrix by Kronecker product, and returns 1 for `n=0` case (thanks to Giuseppe for pointing this out, and also to JAD for helping to golf the initial version).

Additional -3 bytes again thanks to Giuseppe.

# Answer
> 3 votes
# Haskell, 41 bytes

```
(iterate([id<>id,id<>map(0-)]<*>)[[1]]!!)

```

Try it online!

The version of Haskell on TIO doesn't yet have `(<>)` in Prelude so I import it in the header.

# Answer
> 2 votes
# Jelly, 14 bytes

```
1WW;"Ð€,N$ẎƊ⁸¡

```

Try it online!

Change the `G` to `ŒṘ` in the footer to see the actual output.

# Answer
> 2 votes
## JavaScript (ES6), 77 bytes

```
n=>[...Array(1<<n)].map((_,i,a)=>a.map((_,j)=>1|-f(i&j)),f=n=>n&&n%2^f(n>>1))

```

The naive calculation starts by taking `0 <= X, Y <= 2**N` in `W[N]`. The simple case is when either `X` or `Y` is less than `2**(N-1)`, in which case we recurse on `X%2**(N-1)` and `Y%2**(N-1)`. In the case of both `X` and `Y` being at least `2**(N-1)` the recursive call needs to be negated.

If rather than comparing `X` or `Y` less than `2**(N-1)` a bitmask `X&Y&2**(N-1)` is taken then this is non-zero when the recursive call needs to be negated and zero when it does not. This also avoids having to reduce modulo `2**(N-1)`.

The bits can of course be tested in reverse order for the same result. Then rather than doubling the bitmask each time we he coordinates can be halved instead, allowing the results to be XORed, whereby a final result of `0` means no negation and `1` means negation.

# Answer
> 2 votes
# Pari/GP, 41 bytes

```
f(n)=if(n,matconcat([m=f(n-1),m;m,-m]),1)

```

Try it online!

# Answer
> 2 votes
# K (ngn/k), 18 bytes

```
{x{(x,x),'x,-x}/1}

```

Try it online!

# Answer
> 2 votes
# Husk, 13 bytes

```
!¡§z+DS+†_;;1

```

Try it online!

1-indexed.

### Explanation

```
!¡§z+DS+†_;;1
 ¡        ;;1    Iterate the following function starting from the matrix [[1]]
  §z+              Concatenate horizontally
     D               The matrix with its lines doubled
      S+†_           and the matrix concatenated vertically with its negation
!                Finally, return the result after as many iterations as specified
                 by the input (where the original matrix [[1]] is at index 1)

```

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

```
Nest[ArrayFlatten@{{#,#},{#,-#}}&,1,#]&

```

Try it online!

Almost directly copied from this answer of mine.

# Answer
> 2 votes
# Jelly, 8 bytes

```
Ø+ṗ&P¥þ`

```

Try it online!

```
Ø+ṗ         Take the Cartesian product of [1, -1] with itself n times.
      þ`    Table that with itself by:
   &        vectorizing bitwise AND (i.e. logical AND of sign bits!)
    P¥      then multiply the results.

```

A cell is -1 iff it has an odd number of 1 bits in the bitwise AND of its 0-indices. This effectively computes `[0 .. 2^n)`, tables that with itself by bitwise-AND-then-popcount, and raises -1 to each resulting power, but shortcuts all of those steps by representing 0 bits as 1 and 1 bits as -1 to begin with:  provides the desired range without having to explicitly compute `2^n`, and the product is -1 iff there are an odd number of -1s, while thanks to the magic of zipwith-vectorization and two's complement representation the bitwise AND of two sign-list integers is still their bitwise AND as sign-list integers.

# Answer
> 2 votes
# Nibbles, 10 bytes

```
.;`,^2$.@^-1+``@`&

```

Attempt This Online!

Uses the formula \\$W\_{i,j} = \left(-1\right)^{\operatorname{popcount}(\operatorname{bitand}(i,j))}\\$.

# Answer
> 1 votes
# JavaScript (Node.js),100 89 79 bytes

```
f=n=>n?[...(m=F=>r.map(x=>[...x,...x.map(y=>y*F)]))(1,r=f(n-1)),...m(-1)]:[[1]]

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 16 bytes

```
oFoL<N&b0м€g®smˆ

```

Try it online!

**Explanation**

```
oF                 # for N in 2**input do:
  oL<              # push range [1..2**input]-1
     N&            # bitwise AND with N
       b           # convert to binary
        0м         # remove zeroes
          €g       # length of each
            ®sm    # raise -1 to the power of each
               ˆ   # add to global array

```

I wish I knew a shorter way to compute the Hamming Weight.
`1δ¢˜` is the same length as `0м€g`.

# Answer
> 1 votes
# Stax, 20 bytes

```
àΩ2┤â#╣_ê|ª⌐╦è│╞►═∞H

```

Run and debug it at staxlang.xyz!

Thought I'd give my own challenge a try after some time. Non-recursive approach. Not too competitive against other golfing languages...

### Unpacked (24 bytes) and explanation

```
|2c{ci{ci|&:B|+|1p}a*d}*
|2                          Power of 2
  c                         Copy on the stack.
   {                  }     Block:
    c                         Copy on stack.
     i                        Push iteration index (starts at 0).
      {           }           Block:
       ci                       Copy top of stack. Push iteration index.
         |&                     Bitwise and
           :B                   To binary digits
             |+                 Sum
               |1               Power of -1
                 p              Pop and print
                   a          Move third element (2^n) to top...
                    *         And execute block that many times.
                     d        Pop and discard
                       *    Execute block (2^n) times

```

# Answer
> 0 votes
# Python 2, ~~80~~ 79 bytes

```
f=lambda n:n<1and[[1]]or[r*2for r in f(n-1)]+[r+[-x for x in r]for r in f(n-1)]

```

Try it online!

# Answer
> 0 votes
# Python 2, 49 bytes

Showcasing a couple of approaches using additional libraries. This one relies on a built-in in Scipy:

```
lambda n:hadamard(2**n)
from scipy.linalg import*

```

Try it online!

# Python 2, 65 bytes

And this one only uses Numpy, and solves by Kronecker product, analogously to my R answer:

```
from numpy import*
w=lambda n:0**n or kron(w(n-1),[[1,1],[1,-1]])

```

Try it online!

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


# Question
Title: Check if my input was 'hi whats up' without using any of those letters in your code
Write a script, program or function which takes one input of type string and outputs or returns some sort of indication wether the input string was 'hi whats up' (without the apostrophes) or not.

You can for example return true if it was and false if it wasn't. Or print something to the screen, like 1 or 0.

It just has to be consistent: whenever you run the function with parameter/input 'hi whats up' the same output/return should emerge (so don't make it random) and whenever the input is something else, the other possible outcome is expected (it has to be always the same, whatever the input was!). In conclusion, your function/script can only have in total 2 different possible outcomes.

The catch is, your entire code must not contain any of these characters: h, i, w, a, t, s, u, p

Code golf: shortest code in bytes wins.

# Answer
> 4 votes
# Python 3, 29 bytes

```
"HI WHATS UP".loʷer().__eq__

```

Try it online!

An anonymous function taking a string as input. See Using object methods as answer.

# Answer
> 3 votes
# APL (Dyalog Extended), 16 bytes

Full program. Prints 1 for a match, 0 otherwise.

```
⍞≡⌊'HI WHATS UP'

```

Try it online!

Does the input  match  the lowercased  string `'HI WHATS UP'`?

# Answer
> 3 votes
# Excel, 31 bytes

```
=EXACT(A1,LOWER("HI WHATS UP"))

```

# Answer
> 2 votes
# Ruby, 62 bytes

```
->b{b==""<<104<<105<<32<<119<<104<<97<<116<<115<<32<<117<<112}

```

Try it online!

# Answer
> 2 votes
# 05AB1E, 8 bytes

```
…ŒÞÝà€¾Q

```

Outputs `1` if the input is `hi whats up`, `0` otherwise.

Try it online or verify some more test cases.

**Explanation:**

Pretty straight-forward.

```
…ŒÞÝà€¾   # Push dictionary string "hi whats up"
       Q  # Check if it's equal to the (implicit) input
          # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `…ŒÞÝà€¾` is `"hi whats up"`.

# Answer
> 2 votes
# C (clang), ~~68~~ ~~62~~ 57 bytes

```
f(*x,n,*r){for(*r=0;~n;)*r|="()`7(!43`50@"[n]^x[n--]^64;}

```

Try it online!

# Answer
> 1 votes
# Vyxal, 10 bytes

```
«⟇>βX⋏⋏ƈ«=

```

Try it Online!

Base 255 compressed string for the phrase `"hi whats up"` compared against the input.

# Answer
> 1 votes
# Retina 0.8.2, 21 bytes

```
T`Ll`lL
^HI WHATS UP$

```

Try it online! Link includes test cases. Explanation:

```
T`Ll`lL

```

Toggle the case of the input.

```
^HI WHATS UP$

```

Compare it against the uppercased phrase.

# Answer
> 1 votes
# Python 3, ~~89 101~~ 85 bytes

Hey, hey hey.... nobody said you couldn't use code points! Doesn't use object methods or superscript ASCIIs unlike the other answer

Thanks to Dingus and Arnauld for pointing out 2 mistakes. Apparently I'm bad at detecting stuff. Also thanks to Arnauld for letting me forget about 1s and 0s

```
exec("\x70r\x69n\x74(\x69n\x70\x75\x74()=='\x68\x69 \x77\x68\x61\x74\x73 \x75\x70')")

```

# Answer
> 1 votes
# Charcoal, 12 bytes

```
⁼Ｓ”↶⌊＆νξ←₂Yδ

```

Try it online! No verbose link because the deverbosifier doesn't realise it can save a byte by omitting the closing quote. Explanation: Simply compares the input string to the compressed form of the phrase.

# Answer
> 1 votes
# Factor, 24 bytes

```
[ "no&}ngzy&{v"6 v-n = ]

```

Attempt This Online!

Subtracting 6 from each code point in the string `"no&}ngzy&{v"` results in `"hi whats up"`, then check for equality.

# Answer
> 1 votes
# JavaScript (Node.js), 52 bytes

```
x=>x=='\x68\x69\x20\x77\x68\x61\x74\x73\x20\x75\x70'

```

Try it online!

Boring, but you can't really do much else.

# Answer
> 0 votes
# Jelly, 11 bytes

```
“¥_Ż⁺ḄḂȮ§»⁼

```

Try it online!

Same as the other golflang answers: uses a compressed string and then compares with the input.

---
Tags: code-golf, string, restricted-source
---


# Question
Title: Substitute numbers by their respective letter
Create a function or program that takes a number as input, and outputs a string where ASCII-code points for the lower and upper case alphabet are substituted by their character equivalents.

* The upper case alphabet use the code points: `65-90`
* The lower case alphabet use the code points: `97-122`

If any adjacent digits in the input equals the code point of a letter, then that letter shall replace the digits in the output string.

**Rules:**

* The input will be a positive integer with between 1 and 99 digits
* You can assume only valid input is given
* You start substituting at the beginning of the integer (`976` -\> `a6`, not `9L`)
* The input can be on any suitable format (string representation is OK)
* The output can be on any suitable format
* Standard rules apply

**Examples:**

```
1234567
12345C

3456789
345CY

9865432
bA432

6566676869707172737475767778798081828384858687888990
ABCDEFGHIJKLMNOPQRSTUVWXYZ

6711110010100071111108102
Code000Golf

```

**Shortest code in bytes win!**

---

## Leaderboard

The Stack Snippet at the bottom of this post generates the catalog from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where `N` is the size of your submission. If you improve your score, you *can* keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

```
var QUESTION_ID=71735,OVERRIDE_USER=31516;function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"https://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
```

```
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>
```

# Answer
> 3 votes
# Jolf, ~~18~~ 16 bytes

Try it here! I knew that upperLower function would be useful someday! Replace `ó` with `΢`, or just use the interpreter link. This is encoded in ISO 8859-7.

```
ρiLaΜGpwpuEdóH΅A
      pw           upper and lower
        pu         of the uppercase alphabet
     G    E        split by nothing (E = "")
    Μ      dóH     map each char to its numeric counterpart
  La               regex alternate array (e.g. La[1,2,3] => "1|2|3")
ρi            ΅A   replace input with the character code of the match (΅ is string lambda)

```

# Answer
> 19 votes
## Perl, ~~39~~ 38 bytes

(1 byte added for the `-p` flag.)

```
$"="|";s/@{[65..90,97..122]}/chr$&/ge

```

```
s/                           /          replace...
  @{[                      ]}           this string, treated as a regex:
     join"|",65..90,97..122             65|66|67|68|...|121|122
                                   /ge  ...with this string, eval()'d:
                                 $&     the entirety of the last match
                              chr       convert to char from ASCII code

```

Right Tool for the Job™.

The explanation is outdated after one small optimization (thanks dev-null!) that makes it a single byte shorter (but a bit less elegant): the `$"` variable represents what to `join` on when interpolating an arrray into a string, so setting `$"="|"` removes the need for `join`.

Demo:

```
llama@llama:~$ perl -pe '$"="|";s/@{[65..90,97..122]}/chr$&/ge'
1234567
12345C
3456789
345CY
9865432
bA432
6566676869707172737475767778798081828384858687888990
ABCDEFGHIJKLMNOPQRSTUVWXYZ
6711110010100071111108102
Code000Golf

```

# Answer
> 11 votes
# Javascript, 80 bytes

```
s=>s.replace(/6[5-9]|[78]\d|9[0789]|1[01]\d|12[012]/g,x=>String.fromCharCode(x))

```

See regex in action here: https://regex101.com/r/iX8bJ2/1

```
f=
s=>s.replace(/6[5-9]|[78]\d|9[0789]|1[01]\d|12[012]/g,x=>String.fromCharCode(x))

document.body.innerHTML = '<pre>' +
    "f('1234567')\n" + f('1234567') + '\n\n' +
    "f('3456789')\n" + f('3456789') + '\n\n' +
    "f('9865432')\n" + f('9865432') + '\n\n' +
    "f('6566676869707172737475767778798081828384858687888990')\n" + f('6566676869707172737475767778798081828384858687888990') + '\n\n' +
    "f('6711110010100071111108102')\n" + f('6711110010100071111108102') +
'</pre>'
```

Just for curiosity, one thing I learned here:

I can't change `x=>String.fromCharCode(x)` to `String.fromCharCode` because ...

# Answer
> 6 votes
# CJam, 22 bytes

```
q{+'[,_el^{_is@\/*}/}*

```

Try it online!

### Background

Simply replacing all occurrences of digit groups with the corresponding letters (in whatever order we may choose) will fail to comply with the left-to-right rule.

Instead, we can generate all prefixes of the input string, and attempt to make all possible substitutions while we're generating them. Since no code point is contained in another code point, the order of these attempts is not important.

For example:

```
67466

6     -> 6
67    -> C
 C4   -> C4
 C46  -> C46
 C467 -> C4B

C4B

```

### How it works

```
q                       Read all input from STDIN.
 {                  }*  Fold; push the first character, and for each subsequent
                        character, push it and do the following:
  +                       Append the character to the string on the stack.
   '[,_el^                Push the string of all ASCII letters.
                          See: http://codegolf.stackexchange.com/a/54348
          {       }/      For each ASCII letter:
           _                Push a copy of the letter.
            i               Convert to integer, i.e., compute its code point.
             s              Cast to string.
              @\            Rotate and swap.
                /           Split the modified input characters at occurrences (at
                            most one) of the string repr. of the code point.
                 *          Join, separating by the corresponding letter.

```

# Answer
> 4 votes
# PHP, ~~110~~ ~~102~~ ~~101~~ ~~68~~ 67 bytes

Pretty hard challenge. ~~This is the best I could come up with.~~ This is a completely new version.

```
for($i=64;123>$i+=$i-90?1:7;)$t[$i]=chr($i)?><?=strtr($argv[1],$t);

```

Run like this:

```
php -r 'for($i=64;123>$i+=$i-90?1:7;)$t[$i]=chr($i)?><?=strtr($argv[1],$t);' 6711110010100071111108102;echo
> Code000Golf

```
* Saved 8 bytes by using `ctype_alpha` instead of `preg_match`, thx to manatwork
* Saved 1 byte by prepending `0` to the string instead of checking non-empty string: when the last character of the input is a 0, the substring I'm taking would be "0", which is falsy, whereas "00" is truthy, so it won't skip printing the last 0.
* Saved a massive 33 bytes by using `strtr` after building an array with conversion pairs
* Saved a byte by using short print tag

# Answer
> 3 votes
## Python 3, ~~211~~ ~~189~~ 188 bytes

```
def f(c,i=0,n=""):
 while i<len(c):a=1;x=int(c[i:i+2]);a=2 if 64<x<91 or 96<x<100 else a;x=int(c[i:i+3]) if a<2 else x;a=3 if 99<x<123 else a;x=chr(x) if a>1 else c[i];n+=x;i+=a
 return n

```
* ### Saved 23 bytes by replacing \n with ; thanks to Dennis

## Test

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

```
JkBC:CV)R

```

Try it Online! Link includes test cases.

Port of @KevinCruijssen's 05AB1E answer.
*-1 thanks to @KevinCruijssen*

#### Explanation

```
JkBC:CV)R  # Implicit input
       )R  # Reduce by:
J          #  Append to the string
 kB        #  Push constant [A-Za-z]
   C       #  Convert to codepoints
    :C     #  Duplicate and convert back
      V    #  Replace codepoints with characters
           # Implicit output

```

# Answer
> 2 votes
## Pyth, ~~20~~ 18 bytes

```
.Uu:G`CHHsrBG1+bZz

```

Same algorithm as @Dennis. It's a lot easier to code in Pyth on my phone than in Jelly.

```
                implicit: z=input
.U              Reduce the following lambda b, Z over z
                b is the string being built; z is the next char
   u                Reduce the following lambda G,H over +bZ
                    G is the string, H is the next letter to match
     :                  Replace
       G                in G
       ` C H            the char code of H
       H                with H
     s rB            where H takes on values:
          G              the lowercase alphabet (that's the global value of G)
          1              concatenated to its uppercased self.
     +
       b
       Z
   z

```

*Thanks @isaacg*

Try it here.

# Answer
> 2 votes
# 05AB1E, ~~12~~ 11 bytes

```
Å»«žnÇDç:}θ

```

Try it online or verify all test cases or see a step-by-step reduction with just the first 9 bytes.

**Explanation:**

```
Å»         # Cumulative left reduce the (implicit) input-string by:
  «        #  Append the current character to the string
   žn      #  Push the builtin "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
     Ç     #  Convert it to a list of integer codepoints
      D    #  Duplicate this list
       ç   #  Convert each integer to its character again
           #  (so it's a list of the characters, instead of a string)
        :  #  Replace all integers with these characters (at the same indices)
           #  (would only replace 0 or 1 time)
}          # After the cumulative reduce-by is done:
 θ         # Pop the list, and only leave the last string
           # (after which it is output implicitly as result)

```

# Answer
> 1 votes
# Ruby `-p`, ~~50~~ 45 bytes

-5 bytes thanks to manatwork

```
gsub(/#{[*65..90,*97..122]*?|}/){$&.to_i.chr}

```

Attempt This Online!

# Answer
> 1 votes
# Java (JDK), 164 <sup>~~169~~</sup> bytes

> -5 bytes thanks to @KevinCruijssen !

I tried without regexp, and it was surprisingly tricky to handle all the possibilities :')
I'm seven years late to the party, but nice challenge anyway!

```
s->{var r="";for(int i=0,j,a,m=s.length();i<m;r+=a>64&a<91|a>96&a<123?(char)(a+0*(i=j)):s.charAt(i++))for(j=i,a=0;j<m&&(a=a*10+s.charAt(j++)-48)>0&a<13;);return r;}

```

Try it online!

# Answer
> 1 votes
# Python 3, 95 bytes

```
lambda x:re.sub("6[5-9]|[7-8]\d|90|9[7-9]|1[01]\d|12[0-2]",lambda r:chr(int(r[0])),x)
import re

```

Assuming we can take in strings, otherwise this would be 100 bytes.

Try it online!

# Answer
> 0 votes
# Io, 228 bytes

As for these warnings... let's just ignore them.

```
s :=method(H,r(H slice(0,1),H slice(1)))
r :=method(H,T,"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"foreach(i,H=H asMutable replaceSeq(i asString,i asCharacter))if(T=="",return H)r(list(H,T slice(0,1))join,T slice(1)))

```

Try it online!

# Answer
> 0 votes
# PowerShell, 51 bytes

```
$args-replace(65..90+97..122-join'|'),{[char]+"$_"}

```

Try it online!

Explanation:

* replace by RegExp `65|66|67|68|...|121|122`
* replace to result of `{[char]+"$_"}`:

```
    $_   object with matched string
   "$_"  matched string
  +"$_"  convert the string to int

```

\[char\]+"$\_" convert the int to char

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


title: How many unique one sided polyominos

text:
# Question
Title: How many unique one sided polyominos
# Context

From Wikipedia: A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge.

one-sided polyominoes are distinct when none is a translation or rotation of another (pieces that cannot be flipped over). Translating or rotating a one-sided polyomino does not change its shape.

In other words, a one sided polyomino reflected across its x or y axis is not the same as the original polyomino, but a one sided polyomino that is rotated is still considered the same polyomino

# Task

Given a number n, find how many different unique one sided polyominos can be created using n number of blocks

# Input

Take integer n as input for the number of blocks that exist in the polyomino

# Output

An integer of the amount of unique one sided polyominos that can be generated

# Examples

in -\> out

4 -\> 7

5 -\> 18

6 -\> 60

7 -\> 196

More test cases can be found on the Wikipedia page and OEIS

# Answer
# Jelly,  ~~39~~  37 bytes

Soon to be crushed by MATL and, quite possibly, APL

```
p`œc⁸ḣ1ạ§ỊẸʋƇ@;QɗƬƊṪṢƊƑƇŒṬZṚŒṪƲƬṂ$€QL

```

**Try it online!** (It's pretty slow - a(6) took ~30 minutes locally!)

To see them instead try this (`L` -\> `ŒṬ€G€j⁾¶¶`).

### How?

Builds all index lists, where each represents the locations of `1`s on a grid of `1`s and `0`s, up to those for a square of side `n`, filters for those that have their `1`s fully connected, then selects the "minimal" of each after any amount of rotation + vertical translation, and finally de-duplicates and yields the length.

```
   p`œc⁸ḣ1ạ§ỊẸʋƇ@;QɗƬƊṪṢƊƑƇŒṬZṚŒṪƲƬṂ$€QL - Link: integer, n
   A....B..................C............ - break down below

A: p`œc⁸ - Get all ways to have n 1s on an n*n grid as multidimensional indices
    `    - use n as both arguments of:
   p     -   Cartesian product -> all pairs of [1..n] - these are in sorted order
       ⁸ - chain's left argument, n
  œc     - combinations (no replacement) - ...and so each of these are in sorted order

B: ḣ1ạ§ỊẸʋƇ@;QɗƬƊṪṢƊƑƇ - Keep only the fully-connected ones (call input "All")
                     Ƈ - filter keep those for which:
                    Ƒ  -   is invariant under:
                   Ɗ   -     last three links as a monad:
                Ɗ      -       last three links as a monad:
    1                  -         one
   ḣ                   -         head to index - i.e. [firstPair] (initial "Current")
               Ƭ       -         collect up while distinct, applying:
              ɗ        -           last three links as a dyad - i.e. f(Current, All):
           @           -             with swapped arguments - i.e. f(All, Current):
          Ƈ            -               filter keep those (of All) for which:
         ʋ             -                 last four links as a dyad - i.e. f(All, Current):
     ạ                 -                   absolute difference (vectorises)
      §                -                   sum each
       Ị               -                   insignificant? (effectively "in (0,1)?")
        Ẹ              -                   any? - i.e. any are neighbours/same?
            ;          -             concatenate (the result with Current)
             Q         -             deduplicate (-> Current for the next Ƭ-loop)
                 Ṫ     -       tail
                  Ṣ    -       sort

C: ŒṬZṚŒṪƲƬṂ$€QL - Count the distinct results
             €   - for each:
            $    - last two links as a monad:
          Ƭ      -   collect up while distinct, applying:
         Ʋ       -     last four links as a monad:
   ŒṬ            -       2d array from multidimensional indices
     Z           -       transpose
      Ṛ          -       reverse (transpose + reverse = rotate 1/4 anti-clockwise)
       ŒṪ        -       truthy multidimensional indices
           Ṃ     -   minimum
              Q  - de-duplicate
               L - length

```
> 9 votes

# Answer
# JavaScript (Node.js),  ~~269 ... 243~~  239 bytes

Rather slow for \\$n\ge7\\$, but it does find \\$a(8)=704\\$ in a bit more than 2 minutes on my laptop.

```
f=(n,m=[...o=Array(w=n)],i=c=0)=>n?m.map((r,y)=>m.map((_,x,[...m])=>!i|1<<x&~r&(m[y+1]|r/2|r*2)&&f(n-1,m,m[y]|=1<<x)))|c:[0,0,0,0].some(_=>o[M=(m=m.map(a=(_,y)=>m.map(b=(v,x)=>a|=b|=(v>>y&1)<<w+~x)|b)).flatMap(v=>v/(a&-a)||[])])?0:o[M]=++c

```

Try it online!

## How?

### Building the \\$n\\$-polyominos

We store the polyomino in an array \\$m\[\\:\]\\$ of \\$n\\$ bitmasks and build all possible shapes recursively. At each iteration, a new cell adjacent to an existing cell is added.

```
m.map((r, y) =>            // for each bitmask r at position y:
  m.map((_, x, [...m]) =>  //   for each position x, using a copy of m[]:
    !i |                   //     always set this cell if this is the 1st iteration
    1 << x &               //     otherwise, the x-th bit
    ~r &                   //     must not be already set in the current row
    (                      //     and one of the following conditions must be met:
      m[y + 1] |           //       - the x-th bit is set in the next row
      r / 2 |              //       - the (x+1)-th bit is set in the current row
      r * 2                //       - the (x-1)-th bit is set in the current row
    ) &&                   //     if truthy:
      f(                   //       do a recursive call:
        n - 1,             //         decrement n
        m,                 //         pass the copy of m[]
        m[y] |= 1 << x     //         set the bit at (x, y)
      )                    //       end of recursive call
  )                        //   end of inner map()
)                          // end of outer map()

```

### Applying the rotations and translations

When we have enough cells, we apply all 4 possible rotations to \\$m\[\\:\]\\$, discard the empty rows and translate it horizontally so that it's 'right-justified'. We store the encountered shapes in the object \\$o\\$ and the number of distinct shapes in \\$c\\$.

```
[0, 0, 0, 0].some(_ =>     // repeat 4 times:
  o[                       //   we will ultimately test this entry in o
    M = (                  //     save the final matrix in M[]
                           //     1) rotate
      m = m.map(a =        //       starting with a zero'ish,
      (_, y) =>            //       for 0 <= y < w:
        m.map(b =          //         starting with b zero'ish,
        (v, x) =>          //         for each bitmask v at position x in m[]:
          a |=             //           update the global bitmask:
            b |=           //             update the row bitmask:
              (v >> y & 1) //               extract the y-th bit from v
              << w + ~x    //               and set the (w-x-1)-th bit in b accordingly
        ) | b              //         end of inner map(); yield b
      )                    //       end of outer map()
    )                      //     2) translate and crop
    .flatMap(v =>          //       for each bitmask v in m[]:
      v / (a & -a)         //         right-shift v by the position of the LSB of a
      || []                //         discard this row if it's empty
    )                      //       end of flatMap()
  ]                        //   end of lookup
) ?                        // if at least one shape was already encountered:
  0                        //   do nothing
:                          // else:
  o[M] = ++c               //   save the new shape in o and increment c

```
> 5 votes

# Answer
# , ~~180~~ 168 bytes

```
f=\(n,o={},v=0,u=0,`:`=c,`~`=sort,`?`=diff){for(j in u)F=F+`if`(length(p<-~j:o)<n,f(n,p,v,setdiff(c(u=u[-1],j+-1:1i:1:-1i),v<-j:v)),2^(-any(?p-~-p)-any(?p-~p*1i))/n);F}

```

Attempt This Online!

How about a golfy implementation of a more or less real world algorithm of counting polyominoes?

This code is a variation of Redelmeier's method published back in 1981 (link). Obviously, here lots of speed optimizations have been sacrificed in favor of golf, but it still manages to calculate all \\$n\\$ up to 9 in about 17 s on TIO (and even finishes \\$n = 10\\$ when run alone), yet allowing for a quite nice byte count.

### Explanation

The method works by performing a recursive depth-first search up to the indicated length \\$n\\$. The key point is that we never store the list of found polyominoes. Instead, we check for symmetries, and if the current polyomino is symmetric, add only a fraction of the score, so that the total of all polyominoes having the same unique shape would add up to 1.

The algorithm starts by initializing the parent polyomino \\$o\\$ as empty (`NULL`), the set of visited cells \\$v\\$, and untried cells \\$u\\$ containing only the origin. The coordinates of the cells are represented by complex numbers.

`for(j in u)` \- Iterate through the untried set. At each iteration, the current cell is \\$j\\$.

`u<-u[-1]` \- Remove the current cell from the untried set.

`v<-c(j, v)` \- Add it to the visited set.

`p<-sort(c(j, o))` \- Grow the current polyomino \\$p\\$ by adding \\$j\\$ to the parent \\$o\\$. Sort for later use.

`if(length(p)<n)` \- If the polyomino has not yet reached the maximum length,

`f(n,p,v,...)` \- Invoke the recursive call with modified arguments. The new untried set (`...`) is constructed as follows.

Add new neighbors to the untried set. When we are at the origin, the next iteration will involve the cells labeled `1-4` in the scheme below. However, the new neighbors exclude already visited cells, therefore when enumerating neighbors for cell `1`, only the cells `5-7` will be added, as the origin had already been visited.

```
. . . . . . .
. . 6 2 . . .
. 5 1 0 3 . .
. . 7 4 . . .
. . . . . . .

```

So, the new untried set is defined as \\$u \cup\ \\{j-1,j+i,j+1,j-i\\} \setminus v\\$.

If the length \\$n\\$ has already been reached, count the polyomino and return.

`2^(-any(diff(p-sort(-p)))-any(diff(p-sort(p*1i))))/n` \- This is our symmetry evaluation.

As we are interested in one-sided polyominoes, luckily, only two checks corresponding to 90 and 180 degree rotations are needed, no reflections involved. The rotations with complex numbers are very simple (\\$ \times i\\$ for 90 degrees, and \\$ \times -1\\$ for 180 degrees), but then we need to align the shapes to compare them. For this purpose, we sort the polyomino cells, and subtract one from another. If both represent the same shape under different translations from the origin, the resulting vector will consist of identical entries, so that all `diff` will be zero.

Now, if a polyomino is invariant under 180 degree rotation, we will encounter this shape twice, so that gains a multipler of \\$1/2\\$. If it is also invariant under 90 degree rotation, we will find it 4 times, and the multiplier becomes \\$1/4\\$.

In Redelmeier's work, there are additional restrictions disallowing inclusion of certain cells, in order to guarantee that each different rotation ("fixed" polyomino) we be counted exactly once. But these checks take precious bytes, so we skip them. In our case, each fixed polyomino is counted \\$n\\$ times - once for every possible starting point. So, we can handle this simply by dividing the result by \\$n\\$.

Finally, we make use of heavy operator overloading to turn the code into a lunatic mess for some rather modest byte savings.
> 4 votes

# Answer
# Ruby, ~~216 214~~ 204 bytes

```
->n{*h=1,1i,-1,-1i;z=[[0i]];(r,*z=z;r.map{|c|h.map{|v|(r!=k=r|[c+v])&&(w=h.map{|y|(x=k.map{|v|v*y}).map{|g|g-x.map(&:real).min-1i*x.map(&:imag).min}.sort_by &:rect})-z==w&&z<<w[0]}})until z[0][-n];z.size}

```

Try it online!

~~5.5 seconds for n=8 on TIO.~~

~~**Update:** 41 seconds for n=9 on TIO~~

**Harder Better Faster Shorter:** 36 seconds for n=9 on TIO

Still golf-in-progress, the explanation refers to a previous version, the concept is still the same.

### How (more or less):

```
->n{z=[[0+0i]]

```

This initializes the list of polyominos. Instead of a matrix, I will use a list of complex numbers (with integer real and imaginary part). The first entry is the monomino (0,0)

```
(r,*z=z;

```

The main loop: get a single n-omino from the list and build all possible (n+1)ominos from there:

```
4.times{|v|r.map{|c|

```

We need to iterate on all squares of `r` 4 times (add a new square on all sides)

```
(k=[*r,e=c+1i**v])==k|[]&&

```

First check: if we have duplicate squares, we can discard this piece. Otherwise, continue.

```
(w=4.times.map{|y|

```

Check all possible rotations

```
(x=k.map{|v|v*1i**y})

```

To rotate a piece 90 degrees, multiply all squares by `i`

```
.map{|g|g-x.map(&:real).min-1i*x.map(&:imag).min}

```

Then translate it so that it starts from (0,0).

```
.sort_by(&:rect)})-z==w&&

```

Sort the squares inside all 4 rotations, check if at least one is already contained in `z`

```
z<<w[0]}})

```

If not, add the first rotation to `z`

```
until z[0][-n]

```

Repeat until the first piece in the list has size `n`

```
;z.size}

```

The size of `z` is the final result.
> 3 votes

# Answer
# Wolfram Language (Mathematica), 632 bytes

*Finds a(9)=2500 in 30 seconds*

```
J=Length;Q=First;s@n_:=(p=m@{{0,0}};Do[p=S[Flatten[m@#&/@p,1]],n-2];If[n<3,1,J@p]);m@b_:=(A=B={};Do[(A=If[(X=MemberQ)[b,b[[i]]+#],A,(H=Append)[A,b[[i]]+#]])&/@{{0,1},{1,0},{-1,0},{0,-1}},{i,J@b}];A=Complement@A;Table[B=H[B,H[b,A[[j]]]],{j,J@A}];B);S@q_:=Module[{s,b,u,L,V,U,f},f={};Do[s=q[[j]];b=g[q[[j]]];u=Sort[(#-Q@b)&/@q[[j]]];{L,V,U}=v@u;f=If[Or@@(X[f,#]&/@{u,Sort[(#-Q@g@L)&/@L],Sort[(#-Q@g@V)&/@V],Sort[(#-Q@g@U)&/@U]}),f,H[f,u]],{j,J@q-1}];f];g@h_:=(o=(W=Select)[h,Last@#==(Min[Last@#&/@h])&];W[o,Q@#==(Min[Q@#1&/@o])&]);v@p_:=(x=y=z={};Do[x=H[x,{T=Last[p[[i]]],-(R=Q[p[[i]]])}];y=H[y,-{R,T}];z=H[z,{-T,R}],{i,J@p}];{x,y,z})

```

Try it online!
> 2 votes

# Answer
# 05AB1E, ~~75~~ 72 bytes

Should have been 1 byte less by replacing `})}€ê` with `}){}`, but the many nested maps/loops cause a bug in 05AB1E here (`})ê}` and `})}€{` also doesn't work strangely enough..)

```
1ÝInãʒOQiyƶIô©Δ2Fø0δ.ø}2Fø€ü3}®Ā*εεÅsyøÅsM}}}˜Ùg<]εIô2Føʒà}}4FDíø})}€êÙg

```

Extremely slow brute-force, so is only able to output up to \\$a(4)\\$ on TIO.

Try it online or verify the first few results.

**Explanation:**

Step 1: Create all possible \\$n^2\\$-sized list using `0`s and `1`s, consisting of \\$n\\$ amount of `1`s:

```
1Ý          # Push pair [0,1]
  In        # Push the squared input
    ã       # Cartesian power
ʒ           # Filter this list of lists by:
   i        #  If
 O          #  the sum of the current list
  Q         #  is equal to the (implicit) input-integer:
            #   Continue with the check in step 2 below
            #  (implicit else: implicitly use the implicit input for the filter;
            #   this is only truthy for edge case n=1, which fails step 2 due to the `ü3`)

```

Try just this first step online (without trailing `i`).

Step 2: Filter it further to only keep single polynominos, using a flood-fill approach:

```
 y          #   Push the current list again
  ƶ         #   Multiply each value by its 1-based index
   Iô       #   Convert the list to an input-by-input block
     ©      #   Store this block in variable `®` (without popping)
 Δ          #   Loop until the result no longer changes to flood-fill the matrix:
  2Fø0δ.ø}  #    Add a border of 0s around the matrix:
  2F     }  #     Loop 2 times:
    ø       #      Zip/transpose; swapping rows/columns
      δ     #      Map over each row:
     0 .ø   #       Add a leading/trailing 0
  2Fø€ü3}   #    Convert it into overlapping 3x3 blocks:
  2F    }   #     Loop 2 times again:
    ø       #      Zip/transpose; swapping rows/columns
     €      #      Map over each inner list:
      ü3    #       Convert it to a list of overlapping triplets
  ®Ā        #    Push matrix `®` and convert all its positive values back to 1s
    *       #    Multiply each 3x3 block by this matrix of 0s/1s (so 0s will remain 0s)
  εεÅsyøÅsM #    Get the largest value from the horizontal/vertical cross of each 3x3 block:
  εε        #     Nested map over each 3x3 block:
    Ås      #       Pop and push its middle row
      y     #       Push the 3x3 block again
       ø    #       Zip/transpose; swapping rows/columns
        Ås  #       Pop and push its middle rows as well (the middle column)
          M #       Push the flattened maximum of the entire (scoped) stack,
            #       which is the flattened maximum of the cross of the current 3x3 block
  }}        #     Close the nested map
 }˜         #   After the flood-fill loop: flatten the block to a list
   Ù        #   Uniquify its values
    g       #   Pop and push its length
     <      #   Decrease it by 1 to account for the 0s
            #   (only 1 is truthy in 05AB1E, so only single islands remain)
]           # Close both the if-statement and filter

```

Try just the first two steps online.

Step 3: Convert each valid lists to matrices, and slash of any rows/columns of 0s to have the actual polynominos:

```
ε           # Map over each inner list
 Iô         #  Convert it to an n-by-n block
   2F       #  Inner loop 2 times:
     ø      #   Zip/transpose; swapping rows/columns
      ʒ     #   Filter this list of rows by:
       à    #    Get the maximum of the row (so if it only contains 0s, it'll be removed)
      }     #   Close the filter
    }       #  Close the inner loop

```

Try just the first three steps online.

Step 4: Remove all duplicated rotations, by converting each polynomino to a quartet of its four sorted rotations, and then uniquify that list of quartets.

```
 4F         #  Inner loop 4 times:
   D        #   Duplicate the current polynomino-matrix
    íø      #   Rotate it 90 degrees counterclockwise:
    í       #    Reverse each inner row
     ø      #    Zip/transpose the matrix; swapping rows/columns
  })        #  After the loop: wrap the four rotations on the stack into a list

            # Explanation if the 05AB1E bug mentioned at the top wasn't present:
    {       #  Sort the quartet of rotations
}Ù          # After the map: uniquify the list of polynomino-rotations

            # Actual explanation with bug:
}€          # After the map: open a new map:
  ê         #  Sort and uniquify each quartet
   Ù        # After the map: uniquify the list of distinct polynomino-orientations

```

Try just the first four steps online.

Step 5: Get the amount of unique polynominos left, and output it as result:

```
g           # Pop and push the length
            # (which is output implicitly as result)

```
> 1 votes

# Answer
# Python, ~~396~~ 319 bytes

saved 77 bytes thanks to @Deadcode

Modified from @Kirill L.'s answer.

The golfed version, Try it online!

```
import numpy as np
def f(n,o=[],v=[0],u=[0]):
    F=0
    for j in u:
        p=sorted(o+[j])
        if len(p)<n:u=u[1:];v=[j]+v;F+=f(n,p,v,list(set(u).union(set(np.array(j)+np.array([-1,1j,1,-1j]))-set(v))))
        else:F+=(2**(-any(np.diff(np.array(p)-np.sort(-np.array(p))))-any(np.diff(np.array(p)-np.sort(np.array(p)*1j))))/n)
    return F

```

The ungolfed version:

```
import numpy as np

def f(n, o=None, v=None, u=None):
    if o is None:
        o = []
    if v is None:
        v = [0]
    if u is None:
        u = [0]
    F = 0
    for j in u:
        p = sorted(o + [j])
        if len(p) < n:
            u = u[1:]
            v = [j] + v
            F += f(
                n,
                p,
                v,
                list(set(u).union(set(np.array(j) + np.array([-1, 1j, 1, -1j])) - set(v)))
            )
        else:
            var1 = any(np.diff(np.array(p) - np.sort(-np.array(p))))
            var2 = any(np.diff(np.array(p) - np.sort(np.array(p) * 1j)))
            F += (2 ** (-var1 - var2) / n)
    return F

expected = []
for n in range(1, 10):
    expected.append(round(f(n)))
print(expected)

```
> 0 votes

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


title: Let's go on a hyperjumping trip!

text:
# Question
Title: Let's go on a hyperjumping trip!
The idea is based on this interactive game. Given a set of eight decimal digits which are not necessarily distinct, your task is to find a hyperjump trip with the specified length.

### But what is a hyperjump? I ain't got time to click on HOW TO PLAY

Ok, you have a set of eight digits where none is `0` or `9`. Let's say `[1, 3, 6, 7, 8, 7, 7, 4]`. The hyperjump is basically a sub-list of this list. A valid sequence can start at the left with any two numbers, e.g. `7, 7`.

The next number must be the rightmost digit of a simple arithmetic operation (`+ - * /`) between the previous numbers of that sequence. For example:

```
7 + 7 = 14
7 / 7 = 1
7 - 7 = 0
7 * 7 = 49

```

So the next number can either be `4` or `1` because `0, 9` are not on the list. Let's choose `1`:

```
7 - 1 = 6
7 + 1 = 8
7 / 1 = 7

```

By choosing `8` as the next number (`7, 7, 1, 8`) we have:

```
1 * 8 = 8
1 + 8 = 9
71 - 8 = 63

```

As you see, one can also combine the previous digits in the specified order to form a new number. Since there was just one `8` on the list, we can't choose it again. So the only option is `3`. The resulting sequence can be expanded again by adding `4` (because `8 * 3 = 24`) to get `[7, 7, 1, 8, 3, 4]`. The ultimate goal is to reach a `9` after n-steps, where `n ∈ {5, 6, 7, 8}`. Thus if `n = 6` we have reached the desired *hyperjumps trip* since `83 - 4 = 79`.

## Challenge

You are given a list of eight digits in the range of `1..8` along with the number of steps `n`. Find a sub-list with length `n` that can form a hyperjump to `9`.

* The given set can have repeating elements.
* The number of steps is either of `5, 6, 7, 8`.
* The sub-list can only use the elements of the main list (obviously!) and the number of repeating elements cannot exceed those in the main list. For example if the given list has three `7`s, the hyperjump can have at most three `7`s.
* The inputs and output can be in any format that you are comfortable with. But the ordering of the output must be preserved.
* Math operations must apply from left to right and negative results are not accepted. Hence a sequence cannot start with `6, 7, 1`.
* If no hyperjump exists, any kind of error message or an empty output is acceptable.
* Standard rules apply.

## Bonus point

You are a God if your program can find all possible hyperjumps with the specified length.

## Examples:

```
list = [1, 3, 6, 7, 2, 7, 7, 4]; n = 5:
hyperjump = [7, 4, 3, 1, 2]

list = [1, 1, 8, 2, 2, 3, 4, 6]; n = 6:
hyperjump = [6, 2, 2, 1, 3, 4]

list = [5, 5, 5, 5, 5, 5, 5, 5]; n = 7:
hyperjump = []

```

# Answer
> 2 votes
# Jelly, 36 bytes

```
ṖṪṭḌƊÐƤṖjþ“+_×÷”ẎVDṪ€
œ!;9e"ÇƤ$ṫ3ẠƲƇ

```

A dyadic Link that accepts the list of positive digits as integers on the left and the proposed length on the right and yields a list of all possible hyperjump solutions, including the duplicates available when there are repeated digits that may be used.

**Try it online!**

### How?

Brute force checking.

```
ṖṪṭḌƊÐƤṖjþ“+_×÷”ẎVDṪ€ - Helper Link, get possibles for last digit: list, X
Ṗ                     - pop off the last digit (since it's the one we're aiming for)
     ÐƤ               - for each suffix:
    Ɗ                 -   last three links as a monad - f(S=suffix=[..., r]):
 Ṫ                    -     tail (S) and yield -> right operand = r (and S=[...])
   Ḍ                  -     convert (S) from base ten -> left operand = int([...])
                                                         (or 0 when nothing remains)
  ṭ                   -     tack -> [left operand, right operand]
       Ṗ              -   pop off the last result (removing the [0, r] which would
                                                   become e.g. "0+r", allowing any
                                                   repeated digit)
          “+_×÷”      -   list of characters = "+_×÷"
         þ            -   (operands list) table (characters) applying:
        j             -     (operands) join with (character)
                Ẏ     -   tighten to a list of equations
                 V    -   evaluate as jelly code -> list of results of the equations
                  D   -   convert the results to decimal
                   Ṫ€ -   tail each - note that this will be a negative digit if
                                      the equation result was negative
                                      (hence `DṪ€` rather than `%⁵`)

œ!;9e"ÇƤ$ṫ3ẠƲƇ - Main Link: list, L; integer N
œ!             - all permutations choosing N elements
             Ƈ - filter keep those of these "potentials" for which:
            Ʋ  -   last four links as a monad - f(potential):
  ;9           -     concatenate a nine
        $      -     last two links as a monad - f(potential):
       Ƥ       -       for each prefix:
      Ç        -         call the helper Link, above
     "         -       (potential) zip (that) applying:
    e          -         exists in?
         ṫ3    -     tail from index 3 on (remove the first two exists in checks)
           Ạ   -     all truthy?

```

# Answer
> 4 votes
# JavaScript (ES6), 159 bytes

A version always using a single digit for the right operand, which apparently is the correct rule of the game.

```
a=>g=(n,o='',p,m)=>(n?a:[9]).some((v,i)=>m>>i&v<9|o>9&!a.some((_,i)=>[...'+-*/'].some(c=>(s=o.slice(i,-1))&&eval(s+c+p)%10==v))?0:n?g(n-1,o+v,v,m|1<<i):O=o)&&O

```

Try it online!

---

# JavaScript (ES6), 175 bytes

Expects `(list)(n)`. Returns either a string of digits, or *false* if there's no solution.

```
a=>g=(n,o='',m)=>(n?a:[9]).some((v,i)=>m>>i&v<9|o>9&!a.some((_,i)=>(h=j=>(s=o.slice(j))&&eval(o.slice(i,j)+'+-*/'[j*4&3]+s)%10==v|h(j+1/4))(i+1))?0:n?g(n-1,o+v,m|1<<i):O=o)&&O

```

Try it online!

### Commented

```
a =>                   // a[] = input list of digits
g = (                  // g is a recursive function taking:
  n,                   //   n = counter
  o = '',              //   o = output string
  m                    //   m = bit mask of already used digits
) =>                   //
(n ? a : [9])          // using [9] for the last iteration or a[] otherwise,
.some((v, i) =>        // for each value v at index i:
  m >> i & v < 9 |     //   is the i-th bit of m set with v not equal to 9?
  o > 9 &              //   does o have at least 2 digits?
  !a.some((_, i) =>    //   for each entry in a[] at index i:
    ( h = j =>         //     h is a recursive function taking a pointer j
      (s = o.slice(j)) //     using j, extract the right operand s from o
      && eval(         //     unless s is empty, evaluate as JS code:
        o.slice(i, j)  //       the left operand (from i to j-1)
        + '+-*/'       //       followed by an operator
          [j * 4 & 3]  //       chosen according to the decimal part of j
        + s            //       followed by the right operand
      ) % 10 == v |    //     and test whether the result modulo 10 is v
      h(j + 1 / 4)     //     do a recursive call with j + 1/4
    )(i + 1)           //     initial call to h with j = i + 1
  ) ?                  //   end of some(); if the test fails:
    0                  //     do nothing
  :                    //   else:
    n ?                //     if there are more digits to add:
      g(               //       do a recursive call:
        n - 1,         //         decrement n
        o + v,         //         append v to o
        m | 1 << i     //         set the i-th bit of m
      )                //       end of recursive call
    :                  //     else:
      O = o            //       success: save o in O
) && O                 // end of some(); return either false or O

```

# Answer
> 3 votes
# 05AB1E, 40 bytes

```
.ÆʒV"+-*/"¹<ãεUYćsvyXNè.VDïθ}9Ê;)Ðd*ïQ}à

```

Slow brute-force. Inputs in the order \\$n,list\\$, and will output a list of all possible results (including duplicates); not because it's mentioned as *Bonus point* in the challenge description, but simply because it's 1 byte shorter.

Try it online or verify all test cases with only the first valid result instead of all.

**Explanation:**

```
.Æ                      # Get all n-sized lists using items of the list, where `n` and
                        # the list are the first/second (implicit) inputs respectively
  ʒ                     # Filter this list of lists by:
   V                    #  Pop and store the current list in variable `Y`
                        #  (since we're gonna use it within an inner iterator)
   "+-*/"               #  Push the string of the four operands
         ¹<             #  Push the first input - 1
           ã            #  Get all input-1 sized combinations of operands
            ε           #  Map over each list of operands:
             U          #   Pop and store the current list of operands in variable `X`
             Y          #   Push digit-list `Y`
              ć         #   Extract head; push remainder-list and first item separately
               s        #   Swap so the remainder-list is at the top
                v       #   Loop over each digit of the remainder-list:
                 y      #    Push the current digit
                  XNè   #    Push the loop-index'th operand of list `X`
                     .V #    Evaluate and execute this operand as 05AB1E code
                 D      #    Duplicate the result
                  ï     #    Cast the copy to an integer to remove decimal values
                   θ    #    Pop and leave just its last digit
                }       #   After the loop:
                 9Ê     #   Check that the final digit is NOT 9 (0 if 9; 1 if [0-8])
                   ;    #   Halve this 0 or 1 to 0 or 0.5 respectively
             )          #   Wrap all values on the stack into a list
              Ð         #   Triplicate this list
               d        #   Check for each value whether it's non-negative (>=0)
                *       #   Multiply so all negative values in the list become 0s
                 ï      #   Cast all values to integers to remove decimal values
                  Q     #   Equals-check to verify the list is still the same
            }à          #  After the map: check whether any is truthy by taking the max
                        # (after which the filtered list is output implicitly as result)

```

# Answer
> 1 votes
# Charcoal, ~~125~~ ~~114~~ 113 bytes

```
⊞υ⟦⟦⟧θ⟧Ｆ⊕η«≔υθ≔⟦⟧υＦθ«≔⊟κε≔⌊κδ≔↨δ⁰ζＦ⎇⁼ηι⟦⁹⟧Φχ№ελ¿∨‹ι²⊙Ｅδ↨✂δν⊖ι¹χ№﹪⟦∧μ⁺μζ∧›μζ⁻μζ×μζ∧¬﹪μζ÷μζ⟧χλ¿⁼ηιＩκ⊞υ⟦⁺δ⟦λ⟧Φε⁻⌕ελν

```

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

```
⊞υ⟦⟦⟧θ⟧

```

Start a breadth-first search with a position of no digits in the list yet and the starting set.

```
Ｆ⊕η«

```

Loop over each step in the trip plus one for the last hyperjump to `9`.

```
≔υθ

```

Save the list of previously found positions.

```
≔⟦⟧υ

```

Start recording a list of new positions.

```
Ｆθ«

```

Loop over the previous list of positions.

```
≔⊟κε

```

Get the set of remaining digits.

```
≔⌊κδ

```

Get the list of jumps so far.

```
≔↨δ⁰ζ

```

Get the last jump made, if any.

```
Ｆ⎇⁼ηι⟦⁹⟧Φχ№ελ

```

Loop over the remaining digits, or just `9` if this is the final hyperjump.

```
¿∨‹ι²

```

If this is one of the first two steps, or...

```
⊙Ｅδ↨✂δν⊖ι¹χ

```

... for any suffix of the previous jumps ...

```
№﹪⟦∧μ⁺μζ∧›μζ⁻μζ×μζ∧¬﹪μζ÷μζ⟧χλ

```

... any of the arithmetic operations results in a positive integer that ends with the desired digit, then:

```
¿⁼ηι

```

If this is the final hyperjump, then...

```
Ｉκ

```

... output the list, otherwise...

```
⊞υ⟦⁺δ⟦λ⟧Φε⁻⌕ελν

```

... save the position of the extended list and reduced set.

---
Tags: code-golf, puzzle-solver
---


title: Counting polystrips

text:
# Question
Title: Counting polystrips
Polystrips are a subset of polyominoes conforming to the following rules:

* each piece consist of 1 or more cells
* no cell can have more than two neighbours
* the cells should not enclose a hole

Free polyominoes are distinct when none is a rigid transformation (translation, rotation, reflection or glide reflection) of another (pieces that can be picked up and flipped over). Translating, rotating, reflecting, or glide reflecting a free polyomino does not change its shape (Wikipedia)

For example, there are 30 free heptastrips (polystrips with length 7). Here are all of them, packed into a 14x15 grid.

Image credit: Miroslav Vicher

## Goal

Write a program / function that takes a positive integer `n` as input and enumerates the distinct free `n`-polystrips.

* n=1 --\> 1 (A single square)
* n=2 --\> 1 (There is only one possible 2-polystrip made of 2 squares)
* n=3 --\> 2 (One is composed of 3 squares joined in a line and the other one is L-shaped)
* n=4 --\> 3 (One straight, one L-shaped and one Z-shaped)
* . . .

## Test cases:

```
n   polystrips

1   1
2   1
3   2
4   3
5   7
6   13
7   30
8   64
9   150
10  338
11  794
12  1836
13  4313
14  10067
15  23621

```

## Scoring

This is , so the shorter code is better. I would highly appreciate detailed explanations of the algorithm and the code.

## Partial reference implementation in

I decided to describe each piece in "vector" format and I only need n-2 blocks to describe an n-polystrip piece (there is only 1 2-polystrip and it's returned explicitly). The blocks describe the relative direction: 0 - no change; 1 - turn left; 2 - turn right. It doesn't matter which direction one will start but only to indicate where the next cell is to be put. There can be any number of consecutive 0s, but 1s and 2s are always single. This implementation is partial, because it doesn't account for the holes - solutions for n\>6 count the pieces with holes too.

Try it online!

# Answer
# Python 3, 480 433 406 364 309 299 295 bytes

Looked like a good point to start my PPCG career (or not?).

```
def C(s):
 S,*a={''},0,1;n=d=r=1
 for c in s:d=c*d*1jor d;n+=d;a+=n,;r*=not{n}&S;x,*a=a;S|={x+t+u*1jfor t in A for u in A}
 return r
from itertools import*;A=-1,0,1;n,y=int(input())-2,0;x={*filter(C,product(*[A]*n))}
while x:s=x.pop();S=*(-u for u in s),;x-={s[::-1],S,S[::-1]}-{s};y+=1
print(y)

```

Try it online!

**Edits:**

* Inlined `D` and `X`, and tweaked a little bit on some golfable spots.
* Applied more tricks, mainly set-related ones.
* Changed into program form, and changed to using complex numbers instead of arbitrary number `m`. (Complex numbers are really a strong but often ignored golfy feature; adapted from xnor's solution for another challenge)
* Changed the `LFR` string representation to `-1,0,1` tuples and sacrificed execution time for crazy amount of byte reduction(!). Now the solution is theoretically correct but timeouts before outputting the result for 15.
* One-lined the loop thanks to Jonathan Frech, then I found the much better alternative for calculating `r`. FINALLY UNDER 300 BYTES!!!
* Surprisingly `1j` can stick to anything else without confusing the parser (-2B), and `not` has insanely low precedence (-2B).

Obsolete version (480 bytes):

```
def C(s):
 m=999;a=[0,1];n=d=1
 D={'F':{},'L':{1:m,m:-1,-1:-m,-m:1},'R':{1:-m,-m:-1,-1:m,m:1}}
 X=lambda x:{x+~m,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x-~m}
 for c in s:
  d=D[c].get(d,d);n+=d;a+=n,
  if n in set().union(*map(X,a[:-3])):return 0
 return 1
def f(n):
 if n<3:return 1
 x={*'LF'}
 for _ in range(3,n):x={s+c for s in x for c in({*'LRF'}-{s[-1]})|{'F'}}
 y={*x}
 for s in x:
  if s in y:S=s.translate(str.maketrans('LR','RL'));y-={s[::-1],S,S[::-1]}-{s}
 return sum(map(C,y))

```

Try it online!

Ungolfed solution with comments:

```
t = str.maketrans('LR','RL')

# hole checking function
def check(s):
    m = 999   # (imaginary) board size enough to fit all generated polyominoes
    a = [0,1] # previous path
    n = 1     # current cell
    d = 1     # current direction
    # dict for direction change
    D = {'F':{}, 'L':{1:m, m:-1, -1:-m, -m:1}, 'R':{1:-m, -m:-1, -1:m, m:1}}
    # used to 'blur' all cells in path into 3x3
    X = lambda x: {x-m-1,x-m,x-m+1,x-1,x,x+1,x+m-1,x+m,x+m+1}
    for c in s:
        d = D[c].get(d,d) # change direction
        n += d            # move current cell
        # the polyomino has a hole if the current cell touches previous cells (including diagonally; thus the blurring function)
        if n in set().union(*map(X,a[:-2])): return False
        a.append(n)       # add current cell to the path
    return True

# main function
def f(n):
    if n < 3: return 1
    x = {*'LF'}
    # generate all polystrips using the notation similar to the reference
    for _ in range(3, n): x = {s+c for s in x for c in ({*'LRF'}-{s[-1]})|{'F'}}
    y = {*x}
    # remove duplicates (mirror, head-to-tail, mirror of head-to-tail) but retain self
    for s in x:
        if s in y:
            S = s.translate(t)
            y -= {s[::-1], S, S[::-1]} - {s}
    # finally filter out holey ones
    return sum(map(check,y))

```

Try it online!

`m = 999` is chosen because it takes exponential time to count everything, and it's already taking ~8s to calculate `n = 1..15`. Maybe it's fine to save 1 byte by using 99 instead. We don't need this anymore, and now it's guaranteed to be correct for arbitrary input size, thanks to complex number built-in.
> 13 votes

# Answer
# APL (Dyalog Unicode), <sup>~~70~~</sup> 65 bytes

```
+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳2↓⎕⍴3

```

Try it online!

Full program version of the code below, thanks to Adám.

---

# APL (Dyalog Unicode), 70 bytes

```
{+/{∧/∊2≤|(⊢-¯3↓¨,\)+\0 1,×\0j1*⍵}¨∪{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}¨2-,⍳3⍴⍨0⌈⍵-2}

```

Try it online!

### How it works

The code above is equivalent to the following definition:

```
gen←{2-,⍳3⍴⍨0⌈⍵-2}
canonicalize←{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
test←{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{+/test¨∪canonicalize¨gen⍵}

```

This works like the Python solution, but in a different order. It `gen`erates `LFR`-strips of length `n-2`, `canonicalize`s each strip, takes nique strips, `test`s each strip if it touches itself (1 if not touching, 0 otherwise), and sums `+/` the boolean result.

### `gen`

```
{2-,⍳3⍴⍨0⌈⍵-2}
{            }  ⍝ ⍵←input number n
        0⌈⍵-2   ⍝ x←max(0, n-2)
     3⍴⍨        ⍝ x copies of 3
   ,⍳           ⍝ multi-dimensional indexes; x-th cartesian power of [1,2,3]
                ⍝ (`⍳` gives x-dimensional hypercube; `,` flattens it)
 2-             ⍝ compute 2-k for each k in the array

⍝ in each strip, ¯1, 0, 1 corresponds to R, F, L respectively

```

### `canonicalize`

```
{(⊃∘⍋⊃⊢)(⊢,⌽¨)⍵(-⍵)}
{                  }  ⍝ ⍵←single strip
              ⍵(-⍵)   ⍝ nested array of ⍵ and its LR-flip
        (⊢,⌽¨)        ⍝ concatenate their head-to-tail flips to the above
 (⊃∘⍋  )              ⍝ find the index of the lexicographically smallest item
     ⊃⊢               ⍝ take that item

```

### `test`

```
{(∧/⊢{∧/2≤|⍺-¯3↓⍵}¨,\)+\0 1,×\0j1*⍵}
{                                  }  ⍝ ⍵←single strip
                              0j1*⍵   ⍝ power of i; direction changes
                            ×\        ⍝ cumulative product; directions
                        0 1,    ⍝ initial position(0) and direction(1)
                      +\        ⍝ cumulative sum; tile locations
 (  ⊢{           }¨,\)   ⍝ test with current tile(⍺) and all tiles up to ⍺(⍵):
             ¯3↓⍵        ⍝ x←⍵ with last 3 tiles removed
           ⍺-            ⍝ relative position of each tile of x from ⍺
        2≤|              ⍝ test if each tile of x is at least 2 units away
      ∧/                 ⍝ all(...for each tile in x)
  ∧/        ⍝ all(...for each position in the strip)

```
> 6 votes

# Answer
# Scala, ~~2277~~ 1710 bytes\*:

Modified from @Bubbler's answer.

### Golfed version

Try it online!

```
import scala.collection.mutable.Set

object Main {
  def checkSeq(s: String): Boolean = {
    val max = BigInt(9).pow(9)
    var a = Seq(BigInt(0), BigInt(1))
    var n = BigInt(1)
    var d = BigInt(1)
    val dirs = Map(
      'F' -> Map[BigInt, BigInt](),
      'L' -> Map(BigInt(1) -> max, max -> BigInt(-1), BigInt(-1) -> -max, -max -> BigInt(1)),
      'R' -> Map(BigInt(1) -> -max, -max -> BigInt(-1), BigInt(-1) -> max, max -> BigInt(1))
    )
    val adj = (x: BigInt) => Set(x - max - 1, x - max, x - max + 1, x - 1, x, x + 1, x + max - 1, x + max, x + max + 1)

    s.foreach { c =>
      d = dirs(c).getOrElse(d, d)
      n += d
      val v1 = if (a.length > 2) a.slice(0, a.length - 2).map(adj) else Seq()
      val s1 = if (v1.isEmpty) Set[BigInt]() else v1.reduce(_ ++ _)
      if (s1.contains(n)) return false
      a = a :+ n
    }
    true
  }

  def f(n: Int): Int = {
    if (n < 3) return 1

    var x = Set("L", "F")
    (3 until n).foreach { _ =>
      x = x.flatMap { seq =>
        val chars = Set('L', 'R', 'F') - seq.last + 'F'
        chars.map(c => seq + c)
      }
    }

    var y = x.clone()
    x.foreach { seq =>
      if (y.contains(seq)) {
        val trSeq = seq.replace("L", "#").replace("R", "L").replace("#", "R")
        val s1 = Set(seq.reverse, trSeq, trSeq.reverse)
        y --= s1.diff(Set(seq))
      }
    }

    y.count(checkSeq)
  }

  def main(args: Array[String]): Unit = {
    val t1 = System.nanoTime()
    (1 to 15).foreach { i =>
      val t2 = System.nanoTime()
      val res = f(i)
      val t3 = System.nanoTime()
      println(s"$i $res ${t3 - t2}ns")
    }
    val t4 = System.nanoTime()
    println(s"Total time: ${(t4 - t1) / 1000000.0}ms")
  }
}

```

### Ungolfed version

Try it online!

```
import scala.collection.mutable.Set

object Main {
  def checkSequence(s: String): Boolean = {
    val maxValue = BigInt(9).pow(9)
    var a = Seq(BigInt(0), BigInt(1))
    var n = BigInt(1)
    var d = BigInt(1)
    val directions = Map(
      'F' -> Map[BigInt, BigInt](),
      'L' -> Map[BigInt, BigInt](BigInt(1) -> maxValue, maxValue -> BigInt(-1), BigInt(-1) -> -maxValue, -maxValue -> BigInt(1)),
      'R' -> Map[BigInt, BigInt](BigInt(1) -> -maxValue, -maxValue -> BigInt(-1), BigInt(-1) -> maxValue, maxValue -> BigInt(1))
    )
    val calculateAdjacent = (x: BigInt) => Set(x - maxValue - 1, x - maxValue, x - maxValue + 1, x - 1, x, x + 1, x + maxValue - 1, x + maxValue, x + maxValue + 1)   // return a set

    for (c <- s) {
      d = directions(c).getOrElse(d, d)
      n += d
      val var1 = if (a.length > 2) a.slice(0, a.length - 2).map(calculateAdjacent) else Seq()
      val set1 = if (var1.isEmpty) Set[BigInt]() else var1.reduce(_ ++ _)
      if (set1.contains(n)) {
        return false
      }
      a = a :+ n
    }
    true
  }

  def f(n: Int): Int = {
    if (n < 3) {
      return 1
    }

    var x = Set("L", "F")
    for (i <- 3 until n) {
      val newSet = Set[String]()
      for (sequence <- x) {
        var characters = Set('L', 'R', 'F') - sequence.last
        characters += 'F'
        for (character <- characters) {
          newSet += sequence + character
        }
      }
      x = newSet
    }

    var y = x.clone()
    for (sequence <- x) {
      if (y.contains(sequence)) {
        val translatedSequence = sequence.replace("L", "#").replace("R", "L").replace("#", "R") //exchange 'L' and 'R' in sequence
        val set1 = Set(sequence.reverse, translatedSequence, translatedSequence.reverse)
        val set2 = Set(sequence)
        val setDifference = set1.diff(set2)
        y --= setDifference
      }
    }

    y.count(checkSequence)
  }

  def main(args: Array[String]): Unit = {
    val t1 = System.nanoTime()
    for (i <- 1 to 15) {
      val t2 = System.nanoTime()
      val result = f(i)
      val t3 = System.nanoTime()
      println(i + " " + result + " " + (t3 - t2) + "ns")
    }
    val t4 = System.nanoTime()
    val elapsedMs = (t4 - t1) / 1000000.0
    println("Total time: " + elapsedMs + "ms")
  }
}

```

* Rather long in bytes, but computes solutions up to and including \\$n=15\\$ around 15 seconds on TIO.
> 2 votes

---
Tags: code-golf, combinatorics, polyomino
---


# Question
Title: Find the largest contiguous prime in a string
In fairness, this is based on a StackExchange question - but its a good question.

The challenge is fairly simple:

1. Take a string of numerals
2. Find and print the largest contiguous prime number in the string

Scoring:

* Lowest number of characters wins.
* Victor will likely be a golfscript entry but we won't hold that against them, cause we all have fun and learn things, right.
* Winner we be awarded when I notice that I haven't actually ticked the green button.

Assumptions:

* The string is only numbers
    + If the string contains letters, you may have undefined behaviour
* The string contains at least 1 prime
    + If the string does not contains 1 valid prime number, you may have undefined behaviour
* Speed is not a constraint
    + Use a shorter prime algorithm over a faster one.
    + If your entry eventually finishes, thats ok, just make sure it will provable happen before the heat death of the universe.
* *The length of the string can be assumed less than 15 characters long*

For example:

```
>> Input:  3571
<< Output: 3571

>> Input:  123
<< Output: 23

>> Input:  1236503
<< Output: 236503

>> Input:  46462
<< Output:  2

>> Input:  4684
<< Output: ValueError: max() arg is an empty sequence

>> Input:  460
<< Output: 0   # Note, zero is not a prime, but the above string has no valid prime

>> Input:  4601
<< Output: 601

>> Input:  "12 monkeys is a pretty good movie, but not as good as se7en"
<< Output: ValueError: Fight Club was also good, I find Brad Pitt to be a consistantly good actor.

```

## Possible implementations:

1. Find all substrings of the input, check if they are prime. - Legostormtroopr (original)
2. Find all integers less than input, check if they are in the input then check if it is prime - Ben Reich
3. Take a list of all primes less than the input, check if it is in the input - daniero

# Answer
> 6 votes
## GolfScript ~~40~~ 37

```
.{`\`?)}+\~),\,{.,(;\{\%!}+,,1=},)\;

```

This looks at all numbers less than or equal to the the input, filters down to the ones that are substrings of the input, and then filters further down to the primes. Then, it takes the largest such element (which is obviously guaranteed to have the most digits).

Let's break it down into two main sections:

```
.{`\`?)}+\~,\,

```

This part of the code filters down to all integers string contained in the input. It uses grave accent to turn numbers into strings, and then `?` to determine the index of the substring. Since `?` returns `-1` in the case of no containment, increment using `)` so that the output is `0` for non-substrings, which will behave nicely with the `,` filtering.

```
{.,(;\{\%!}+,,1=},

```

This part of the code filters down to the primes by counting the number of factors less than the given number (an integer is a factor only if `number factor %!` is 1. A prime number will have exactly 1 factor strictly less than itself, so do `1=`.

Since the numbers are in order, take the last one and clear the stack using `)\;`

This obviously isn't as efficient as possible (since it somewhat unnecessarily iterates over all integers less than the input), but it still terminates with big input like `1236503` relatively quickly on my computer (1 minute).

# Answer
> 4 votes
## Python 2.7 - 84

Here is a reference implementation to beat, I used it for the example output in the question, so its gauranteed to work * Not an actual guarantee

**Shameless improvement** based on Ben Reich's much better solution than my original one. With major assistance from **Volatility**

```
N=input()
print max(x for x in range(N+1)if(`x`in`N`)&all(x%i for i in range(2,x)))

```

Prior incantations of the second line include:

```
print max(x for x in range(N+1)if`x`in`N`and 0 not in(x%i for i in range(2,x)))
print max(x for x in range(N+1)if`x`in`N`and sum(x%i<1 for i in range(2,x))<1)

```

---

**The original version - 143**

```
N=`input()`
p=lambda n:[n%i for i in range(2,n)if n%i==0]
print max(int(N[j:i])for i in range(len(N)+1)for j in range(i)if not p(int(N[j:i])))

```

# Answer
> 2 votes
# Vyxal `G`, 4 bytes

```
ǎ⌊~æ

```

Try it Online! Link includes test cases.

Input as a string. Add the  flag if you want input as a number.

#### Explanation

```
ǎ⌊~æ  # Implicit input
ǎ     # Substrings
 ⌊    # Cast to integer
  ~   # Filtered by
   æ  # Is prime
      # G flag gets maximum
      # Implicit output

```

# Answer
> 1 votes
# Ruby 61

Take all primes up to N and see if they are in the string

```
require'prime'
p Prime.each(gets.to_i).select{|i|~/#{i}/}.max

```

I think this only works on Ruby 1.9 and newer, but I'm not sure.

# Answer
> 1 votes
# Haskell, 94

`main=getLine>>=print.maximum.filter(\x->and$map((0/=).mod x)[2..x-1]).map read.init.scanr(:)[]`

# Answer
> 1 votes
# Scala (83 chars)

I wasn't sure how to provide inputs to the program so I considered `n` is the input. Here's the actual solution (based on which the solution length is evaluated). Below that is an executable form of the solution (which isn't golfed yet) for execution along with the output (for the samples give OP has).

**Solution:**

```
n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max

```

**Executable solution:**

```
object A {
  def main(x:Array[String])=List("3571","123","23","1236503","46462","4684","460","4601","12 monkeys..").foreach(e=>println(e+" => "+q(e)))

  private def p(n: String)=n.inits.flatMap(_.tails.toList.init.map(BigInt(_))).filter(_ isProbablePrime 1).max
  private def q(n: String)=try p(n)catch{case e=>e.toString}
}

```

**Sample output:**

```
3571 => 3571
123 => 23
23 => 23
1236503 => 236503
46462 => 2
4684 => java.lang.UnsupportedOperationException: empty.max
460 => java.lang.UnsupportedOperationException: empty.max
4601 => 601
12 monkeys.. => java.lang.NumberFormatException: For input string: "12 "

```

**Explanation:**

Steps are pretty straight forward.

input -\> Find all substrings -\> filter non primes -\> find longest value

* `main(Array[String])`: Method provides sample input and executes method `q(String)` for each input
* `q(String)`: Wraps actual program logic from `p(String)` so any exceptions are appropriately reported. Helps in formatting the output better because invalid inputs are going to get `NumberFormatException`s where as the lack of a prime will throw an `UnsupportedOperationException`
* `p(String)`: Actual logic of the program. Let's split the explanation for this into parts
    + `n.inits`: Creates an `Iterator` to iterate over the String input (`n`)
    + `flatMap(f)`: Applies an operation on the `Iterator` and pushes the result into a `List`
        - `_.tails.toList.init.map(BigInt(_))`: Splits the `String` and removes empty `String`s from the resultant `List`. Finally converts the `String` to a `BigInt` which is an equivalent of `java.math.BigInteger`. For golfing reasons, `BigInt` is selected (shorter name).
    + `filter(f)`: if `f` returns `false`, the value is removed from the resultant `List`
        - `_ isProbablePrime 1`: This line could have been written as `_.isProbablePrime(1)` but the representation used saves 1 byte. This line actually checks if the value is a prime (probabilistically; since `certainty` is set to `1`, execution time goes up but the system makes certain (more or less) that the number is a prime.
    + `max`: Finds the maximum value (not `String` based length. Actual max value)

# Answer
> 1 votes
## J (~~24~~ 22)

Reading from the keyboard is actually shorter than defining a function.

```
>./(*1&p:);".\.\1!:1[1

```

Test:

```
   >./(*1&p:);".\.\1!:1[1
3571
3571
   >./(*1&p:);".\.\1!:1[1
46462
2
   >./(*1&p:);".\.\1!:1[1
1236503
236503
   >./(*1&p:);".\.\1!:1[1
4684
0
   >./(*1&p:);".\.\1!:1[1
4680
0
   >./(*1&p:);".\.\1!:1[1
twelve monkeys is a pretty good movie
__

```

Explanation:

* `1!:1[1`: read a line of text from the keyboard
* `".\.\`: the evaluation (`".`) of each suffix (`\.`) of each prefix (`\`) of the string.
* `;`: flatten the matrix
* `*1&p:`: multiply each value by whether it is a prime or not (so all nonprimes will be zero)
* `>./`: get the largest value in the list

# Answer
> 1 votes
## Perl 6 (40 characters, 41 bytes)

```
$_=get;say max grep &is-prime,+«m:ex/.+/

```

First `get` input into `$_`, this makes the regex match call shorter. `:ex` gives exhaustive matching for regex, it will give all possibilities. The hyper op  (or `+<<` works too) will make numbers out of the Match objects, those are passed to `grep` with `&is-prime` sub as selector. Finally take the maximum of the remaining list and output it.

# Answer
> 1 votes
# Jelly, 6 bytes

```
DẆḌẒƇṀ

```

Try it online!

Takes input as an integer. If input must be a string, then 7 bytes. Returns `0` for numbers with no primes in them.

## How it works

```
DẆḌẒƇṀ - Main link. Takes n on the left
    Ƈ  - Find...
     Ṁ - ...the largest...
 Ẇ     - ...contiguous...
  ḌẒ   - ...prime...
D      - ...in a string

```

or, alternatively,

```
DẆḌẒƇṀ - Main link. Takes n on the left
D      - Convert n to digits
 Ẇ     - Get all contiguous sublists
  Ḍ    - Convert each back from digits
    Ƈ  - Filter keep:
   Ẓ   -   Primes
     Ṁ - Yield the maximum

```

# Answer
> 1 votes
# 05AB1E, 5 bytes

```
Œʒp}Z

```

Try it online!

#### Explanation

```
Œʒp}Z  # Implicit input
Œ      # Substrings
 ʒ }   # Filtered by
  p    # Is prime
    Z  # Maximum
       # Implicit output

```

# Answer
> 1 votes
# PowerShell, 170 bytes

I'm sure there is a better way of doing this...

```
$v.count..1|%{
	$d=$_
	0..(-$d+$v.count)|%{
		$n=$v[$_..($_+$d-1)]-join""
		$a=@()
		1..[math]::sqrt($n)|%{$a+=$_,($n/$_)*!($n%$_)}
		if($a.count-eq2){$b+=$n}
	}
}

$b[0]

```

Try it online!

# Answer
> 0 votes
# Mathematica ~~67~~ 47

```
StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&

```

**Explanation**

The code is a pure function. It has no name. In it, `#` represents the full input string.

`StringCases` takes the input, #, and checks for substrings, `a`, of one character or more (that's why \__ was used instead of \_) that are primes; PrimeQ must return True for the substring.

All the favorable cases, i.e. the substrings that are primes, are by default returned in a list. `〚1〛`, or `[[1]]` takes the first part, that is, the first element of that list of primes. `element[[1]]` is shorthand for `Part[element, 1]`. If there is more than one prime, the first one will be the longest prime (`StringCases` checks the longest substrings first).

**Examples**

```
StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&["1236503"]

```

> "236503"

```
StringCases[#,a__/;PrimeQ@ToExpression@a]〚1〛&/@
{"1236503", "123", "46462", "4684", "460", "4601",
"12 monkeys is a pretty good movie, but not as good as se7en"}

```

> {"236503", "23", "2", {}\[\[1\]\], {}\[\[1\]\], "601", "2"}

# Answer
> 0 votes
# Perl 6 (50 characters, 51 bytes)

```
say max +«get.match(/(.+)<?{(+$0).is-prime}>/,:ex)

```

maps strings to numbers, `max` gets the biggest number, `get` receives a line. `/(.+)<?{(+$0).is-prime}>/` is a regular expression that gets all primes `<?{}>` is a code assertion. `is-prime` is `Int` class method which checks if number is a prime. I need to cast value to number by using `+`, because it's `Str` by default. `:ex` means that it tries to find **ALL** matches (including those where overlap others). Because of Rakudo Perl bug, it's currently impossible to use `m//` here.

This works for any number, and if you remove `max` (or replace it with `sort`) you will get list of all primes in the number, for extra bonus (not that this gives points, or anything). For example (with `sort` in this case):

```
1234567890
2 3 5 7 23 67 89 4567 23456789

```

# Answer
> 0 votes
# Japt `-h`, 6 bytes

```
ã f_°j

```

Try it

# Answer
> 0 votes
# Husk, 6 bytes

```
→fṗmrQ

```

Try it online!

# Answer
> 0 votes
# Arturo, 50 bytes

```
$[s][last select..1do s'x->∧prime? x in?~"|x|"s]

```

Try it

# Answer
> 0 votes
# PARI/GP, 212 bytes

Try it online!

```
ss(s,n,m)=concat(Vec(s)[n..n+m-1])
ivn(s)={my(v=Vecsmall(s));for(i=1,#s,if(v[i]<48||v[i]>57,return(0)));1}
ips(s)={my(l=#s);for(i=1,l,for(j=1,i,my(st=ss(s,j,l+1-i));if(ivn(st)&&isprime(eval(st)),return(st))));""}

```

Ungolfed version

```
substring(s,n,m)=concat(Vec(s)[n..n+m-1])
is_valid_number(s) = {
  my(vec_s = Vecsmall(s));
  for (i = 1, #s, if (vec_s[i] < 48 || vec_s[i] > 57, return(0)));
  return(1);
}
is_prime_string(s) = {
  my(len = #s);
  for (i = 1, len,
    for (j = 1, i,
      my(substr = substring(s, j, len+1-i));
      if (is_valid_number(substr) && isprime(eval(substr)), return(substr));
    )
  );
  return("");
}
strings = ["1236503", "123", "46462", "4684", "460", "4601","12 monkeys is a pretty good movie, but not as good as se7en"];
ans = vector(#strings, i, is_prime_string(strings[i]))
print(ans)

```

---
Tags: code-golf, string, primes, subsequence
---


title: Translate English to English

text:
# Question
Title: Translate English to English
You have been hired by the American embassy in the UK to act as a translator. Being a programmer, you decide to write a program to do a bit of the work for you.

You've found out that often just doing the following things can satisfy Word's spellcheck, which has been set to "English (United States)", somewhat, so you don't have to do as much work later when translating written documents:

* All occurrences of "our" can be replaced with "or", e.g. "favourite" -\> "favorite", "our" -\> "or".
* All occurrences of "ise" and "yse" can be replaced with "ize" and "yze", respectively.
* All occurrences of "ae" and "oe" can be replaced with "e".
* All occurrences of "ll" that have a vowel before them can be replaced with "l".
* The ending "re" can re replaced with "er", as long as it is not preceded by a vowel, e.g. "ore" will not be replaced, but "centre" becomes "center".
* The ending "xion" can be replaced with "ction", e.g. "connexion" -\> "connection" (this is archaic, but whatever).

Write a program or function that takes a string or list of characters as input, performs the replacements mentioned above, and outputs the modified string or list of characters using the standard IO methods.

# Rules

* A sequence of alphabetical characters is considered a word (`[A-Za-z]`). Words may be delimited by spaces, hyphens, commas, periods, or other punctuation characters (`[^A-Za-z]`).
* A vowel is one of a, e, i, o, or u.
* This is , so shortest code wins.
* Inputs with conflicts are undefined behavior, e.g. if a word ends with "oure", your program can make it "ouer" or "ore".
* Your program need only take one pass over the input - it's fine if you replaced something like "rae" and end up with "re" instead of further turning that into "er".
* Substitutions may be done on uppercase and/or lowercase letters (you can choose). You may also output the letters in any case you want.

## Test cases

Note that not all words have been translated correctly, since the rules described above are not always right. Also note that the text here has mixed case to try to look like normal English, but you can use all lowercase for your input and all uppercase for your output or whatever you want.

```
Substitutions are **bolded** or *italicized* if they are side by side.

Input
---
Output
______
We would like you to anal**yse** something **our** agencies have discovered.
---
We would like you to anal**yze** something **or** agencies have discovered.
______
There have been reports of American t**our**ists trave**ll**ing here in knight's arm**our**.
---
There have been reports of American t**or**ists trave**l**ing here in knight's arm**o**r.
______
An **ae**rosol may be the cause of their transfi**xion**. Their **oe**sophagi must be studied.
---
An **e**rosol may be the cause of their transfi**ction**. Their **e**sophagi must be studied.
______
**OUR**o**ull**is**ae*****ise***re
---
**OR**o**ul**is**e*****ize***re
______
Pardon me, I just f**ell** on my keyboard while dodging a knight with a met**re**-long sword.
---
Pardon me, I just f**el** on my keyboard while dodging a knight with a met**er**-long sword.
______
My ke**yse**re n'tw**our**kingnowneith**re** r myhands h**ell**llpme
---
My ke**yze**re n'tw**or**kingnowneith**er** r myhands h**ell**lpme
______
Haha, I'm just messing with you. No knights here with 3.28-foot-long swords. That's tot**all**y ridiculous.
---
Haha, I'm just messing with you. No knights here with 3.28-foot-long swords. That's tot**al**y ridiculous.

```

# Answer
# QuadR, ~~77~~ 75 bytes

-2 thanks to Neil.

```
our
(i|y)se
ae|oe
([aeiou]l)l
([^aeiou])re\b
xion\b
or
\1ze
e
\1
\1er
ction

```

Try it online!

The first half of the strings are PCRE patterns while the latter half are their substitutions.
> 9 votes

# Answer
# Perl 5, `-p` ~~100~~ 94 bytes

*Saves 6 bytes since we can require all input to be lowercase, as pointed out by @NahuelFouilleul*

```
s/our/or/g;s/[iy]\Kse/ze/g;s/ae|oe/e/g;s/[aeiou]l\Kl//g;s/[^aeiou]\Kre\b/er/g;s/xion\b/ction/g

```

Try it online!
> 7 votes

# Answer
# JavaScript (ES9), 126 bytes

Operates on lowercase patterns.

```
s=>s.replace(/(?<=o)u(?=r)|(a|o|(?<=i|y)s)(?=e)|(?<=[aeiou])l(?=l)|(?<![aeiou])re\b|x(?=ion)/g,s=>[{x:'ct',re:'er',s:'z'}[s]])

```

Try it online!

### How?

All operations are processed within a single `replace()` with a callback function.

We use lookbehind and lookahead assertions so that the sub-strings that actually need to be modified are as small as possible and the replacement is just an implicit empty string whenever possible.

The non-empty replacement strings are stored in an object.

```
 pattern              | replacement
----------------------+------------------------------
 (?<=o)**u**(?=r)         | "u" -> ""
 (**a**|**o**|(?<=i|y)**s**)(?=e) | "a" or "o" -> "", "s" -> "z"
 (?<=[aeiou])**l**(?=l)   | "l" -> ""
 (?<![aeiou])**re**\b     | "re" -> "er"
 **x**(?=ion)             | "x" -> "ct"
```
> 7 votes

# Answer
# Charcoal, ~~130~~ 125 bytes

```
≔aeiouζ≔⁺ θηＦiy≔⪫⪪θ⁺ιse⁺ιzeθＦ⌕ＡθreＦ¬∨№ζ§ηι№β§η⁺³ι≔⭆Φθ⁻μι⎇⁻μιλerθ⭆θ⎇∨№⁺⊕⌕Ａθour⁺⌕Ａθae⌕Ａθoeκ∧№⌕Ａθllκ№ζ§ηκω⎇∧№⌕Ａθxionκ¬№β§η⁺⁵κctι

```

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

```
≔aeiouζ

```

Get the vowels in a variable, as they're long enough for this to save a byte.

```
≔⁺ θη

```

Make a copy of the input with a space prepended. This is used for cyclic indexing, plus conveniently offsets the indices by one.

```
Ｆiy≔⪫⪪θ⁺ιse⁺ιzeθ

```

Replace `ise` and `yse` with `ize` and `yze` respectively.

```
Ｆ⌕Ａθre

```

Find all occurrences of `re`...

```
Ｆ¬∨№ζ§ηι№β§η⁺³ι

```

... that are at the end of a word and do not follow a vowel...

```
≔⭆Φθ⁻μι⎇⁻μιλerθ

```

... and replace them with `er`.

```
⭆θ⎇∨№⁺⊕⌕Ａθour⁺⌕Ａθae⌕Ａθoeκ∧№⌕Ａθllκ№ζ§ηκω⎇∧№⌕Ａθxionκ¬№β§η⁺⁵κctι

```

If the current character is:

* the `u` of `our`
* the `a` of `ae`
* the `o` of `oe`
* or the first `l` of `ll` and it follows a vowel

... then delete it, otherwise if it is the `x` that begins `xion` at the end of a word then replace it with `ct`, and output the final result.
> 6 votes

# Answer
# Ruby `-p`, ~~110~~ ~~101~~ 100 bytes

*A port of Arnauld's answer in Ruby.*
*Saved a whooping 9+1 bytes using* `\K`, *thanks to Dingus!!*

```
gsub /o\Ku(?=r)|(a|o|[iy]\Ks)(?=e)|[aeiou]\Kl(?=l)|[^aeiou]\Kre\b|x(?=ion)/,?s=>?z,'re'=>:er,?x=>:ct

```

Try it online!
> 6 votes

# Answer
# Lexurgy, 106 bytes

Sound changes are what Lexurgy is made for!

Works in all lowercase only.

```
Class v {a,e,i,o,u}
o:
our=>or
{i,y} se=>{i,y} ze
{a,o}=>*/_ e
l=>*/@v _ l
re=>er/!@v _
x=>ct/_ ion

```

Ungolfed explanation:

```
# define vowels
Class vowel {a,e,i,o,u}

or:
our=>or

ize:
{i,y} se=>{i,y} ze

e:
{a,o}=>*/_ e

l:
l=>*/@vowel _ l

er:
re=>er/!@vowel _

ction:
x=>ct/_ ion

```
> 5 votes

# Answer
# 05AB1E, 94 bytes

```
.•´iÈQ<¾Ÿ7ø₂2>“UcтλHZ•#2ä`.:žMS„ll«D€¨.:DžQAKS¡DεD"xion"Å¿i¨¨¨¨.•U®$•«}žNvDy„re«Å¿i¨¨¨y„erJ].;

```

Input in lowercase. Assumes the input will only contains printable ASCII characters.

Try it online or verify all test cases.

**Explanation:**

```
.•´iÈQ<¾Ÿ7ø₂2>“UcтλHZ• # Push compressed string "our ise yse ae oe or ize yze e e"
 #                     # Split it on spaces: ["our","ise","yse","ae","oe","or","ize","yze","e","e"]
  2ä                   # Split into 2 equal-sized blocks: [["our","ise","yse","ae","oe"],["or","ize","yze","e","e"]]
    `                  # Pop and push both lists separated to the stack
     .:                # Replace all
žM                     # Push builtin "aeiou"
  S                    # Convert it to a list of characters: ["a","e","i","o","u"]
   „ll«                # Append "ll" to each: ["all","ell","ill","oll","ull"]
       D€¨             # Duplicate it, and remove the last character of each: ["al","el","il","ol","ul"]
          .:           # Replace all
D                      # Duplicate the current string
 žQ                    # Push a builtin with all printable ASCII characters
   AK                  # Remove the lowercase alphabet from it
     S                 # Split it to a list of characters
      ¡                # And split the duplicated string on these non-letter characters
D                      # Duplicate the list of words
 ε                     # Map over each word:
  D                    #  Duplicate the current word
   "xion"Å¿i       }   #  Pop, and if it ends with "xion":
            ¨¨¨¨       #   Remove the final four characters from the word
            .•U®$•«    #   And append (compressed) "ction"
  žN                   #  Push buitin "bcdfghjklmnpqrstvwxyz"
    v                  #  Loop `y` over each of its characters:
     D                 #   Duplicate the current word
      y„re«            #   Push the current consonant, and append "re"
           Å¿i         #   If it ends with "Cre" (where `C` is the consonant)
              ¨¨¨      #    Remove the final three characters from the word
              y„erJ    #    Push the consonant and "er" and join all three together
]                      # Close the open if-statement, loop, and map
 .:                    # And replace all
                       # (after which the result is output implicitly)

```

See this 05AB1E tip of mine (section *How to compress strings not part of the dictionary?*) to understand why `.•´iÈQ<¾Ÿ7ø₂2>“UcтλHZ•` is `"our ise yse ae oe or ize yze e e"` and `.•U®$•` is `"ction"`.
> 4 votes

# Answer
# Wolfram Language (Mathematica), ~~227~~ 181 bytes

saved 46 bytes thanks to comment.

Try it online!

```
R:=RegularExpression
f[s_]:=StringReplace[s,{"our"->"or","ise"->"ize","yse"->"yze","ae"->"e","oe"->"e",R["(?<=[aeiou])ll"]->"l",R["(?<=[^aeiou])re\\b"]->"er",R["xion\\b"]->"ction"}]

```

Ungolfed version:

```
f[s_String] := Module[
  {replacements, result},
  replacements = {
    "our" -> "or",
    "ise" -> "ize",
    "yse" -> "yze",
    "ae" -> "e",
    "oe" -> "e",
    RegularExpression["(?<=[aeiou])ll"] -> "l",
    RegularExpression["(?<=[^aeiou])re\\b"] -> "er",
    RegularExpression["xion\\b"] -> "ction"
  };
  result = StringReplace[s, replacements];
  result
]

```
> 3 votes

# Answer
# Python 3.8, ~~158~~ 154 bytes

Saved 4 bytes thanks to user!!!

```
lambda s:[(s:=re.sub(*x.split(),s))for x in r'our or|ise ize|yse yze|[ao]e e|(?<=[aeiou])ll l|(?<=[^aeiou])re\b er|xion\b ction'.split('|')][-1]
import re

```

Try it online!

Inputs a string in lower-case and returns its translation in lower-case.
> 2 votes

---
Tags: code-golf, string, natural-language
---