title: Backhanded^H^H^H^H^H^Hspaces

text:
# Question
Title: Backhanded^H^H^H^H^H^Hspaces
On some terminals, pressing backspace generates the control code `^H` to delete the previous character. This gave rise to a snarky idiom where edits are feigned for comedic effect:

> Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ.

Given a string with one or more `^H`'s, output the result of backspacing on each `^H`. The input will use only printable characters (ASCII 32-126), and `^` will only appear as `^H`. Backspaces will never happen on empty text.

You may not assume that the output environment supports control codes, in particular the backspace code `\x08`.

```
>> Horse^H^H^H^H^HCow
Cow

>> Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ.
Be nice to this gentleman, he's visiting from corporate HQ.

>> 123^H45^H^H^H78^H
17

>> Digital Trauma^H^H^H^H^H^H^H^H^H^H^H^H^H^HMaria Tidal Tug^H^H^H^H^H^H^H^H^H^H^H^H^H^H^HDigital Trauma
Digital Trauma

```

## Leaderboard

Here's a by-language leaderboard, courtesy of Martin Büttner.

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

```

```
function answersUrl(e){return"https://api.stackexchange.com/2.2/questions/52946/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function getAnswers(){$.ajax({url:answersUrl(page++),method:"get",dataType:"jsonp",crossDomain:true,success:function(e){answers.push.apply(answers,e.items);if(e.has_more)getAnswers();else process()}})}function shouldHaveHeading(e){var t=false;var n=e.body_markdown.split("\n");try{t|=/^#/.test(e.body_markdown);t|=["-","="].indexOf(n[1][0])>-1;t&=LANGUAGE_REG.test(e.body_markdown)}catch(r){}return t}function shouldHaveScore(e){var t=false;try{t|=SIZE_REG.test(e.body_markdown.split("\n")[0])}catch(n){}return t}function getAuthorName(e){return e.owner.display_name}function process(){answers=answers.filter(shouldHaveScore).filter(shouldHaveHeading);answers.sort(function(e,t){var n=+(e.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0],r=+(t.body_markdown.split("\n")[0].match(SIZE_REG)||[Infinity])[0];return n-r});var e={};var t=1;answers.forEach(function(n){var r=n.body_markdown.split("\n")[0];var i=$("#answer-template").html();var s=r.match(NUMBER_REG)[0];var o=(r.match(SIZE_REG)||[0])[0];var u=r.match(LANGUAGE_REG)[1];var a=getAuthorName(n);i=i.replace("{{PLACE}}",t++ +".").replace("{{NAME}}",a).replace("{{LANGUAGE}}",u).replace("{{SIZE}}",o).replace("{{LINK}}",n.share_link);i=$(i);$("#answers").append(i);e[u]=e[u]||{lang:u,user:a,size:o,link:n.share_link}});var n=[];for(var r in e)if(e.hasOwnProperty(r))n.push(e[r]);n.sort(function(e,t){if(e.lang>t.lang)return 1;if(e.lang<t.lang)return-1;return 0});for(var i=0;i<n.length;++i){var s=$("#language-template").html();var r=n[i];s=s.replace("{{LANGUAGE}}",r.lang).replace("{{NAME}}",r.user).replace("{{SIZE}}",r.size).replace("{{LINK}}",r.link);s=$(s);$("#languages").append(s)}}var QUESTION_ID=45497;var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";var answers=[],page=1;getAnswers();var SIZE_REG=/\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;var NUMBER_REG=/\d+/;var LANGUAGE_REG=/^#*\s*((?:[^,\s]|\s+[^-,\s])*)/
```

```
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>Language<td>Size<tbody id=answers></table></div><div id=language-list><h2>Winners by Language</h2><table class=language-list><thead><tr><td>Language<td>User<td>Score<tbody id=languages></table></div><table style=display:none><tbody id=answer-template><tr><td>{{PLACE}}</td><td>{{NAME}}<td>{{LANGUAGE}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table><table style=display:none><tbody id=language-template><tr><td>{{LANGUAGE}}<td>{{NAME}}<td>{{SIZE}}<td><a href={{LINK}}>Link</a></table>
```

# Answer
> 69 votes
# GNU sed, 11 bytes

```
:;s/.^H//;t

```

### Test output:

```
$ echo "Horse^H^H^H^H^HCow
Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ.
123^H45^H^H^H78^H
Digital Trauma^H^H^H^H^H^H^H^H^H^H^H^H^H^HMaria Tidal Tug^H^H^H^H^H^H^H^H^H^H^H^H^H^H^HDigital Trauma" | sed ':;s/.^H//;t'
Cow
Be nice to this gentleman, he's visiting from corporate HQ.
17
Digital Trauma
$

```

# Answer
> 19 votes
# Pyth, 11 bytes

```
.U+PbZcz"^H

```

Demonstration.

```
.U+PbZcz"^H
               Implicit: z = input()
      cz"^H    z.split("^H")
.U             reduce, with the first element of the list as the initial value.
   Pb          Remove the last character of what we have so far.
  +  Z         And add on the next segment.
               Print implicitly.

```

# Answer
> 17 votes
# Gema, 6 bytes

```
?#\^H=

```

Sample run:

```
bash-4.3$ gema -p '?#\^H=' <<< 'pizza is alright^H^H^H^H^H^Hwesome'
pizza is awesome

```

CW, because the fool vs. gentleman example takes far too long. (Killed after a day. Maybe a glitch in the interpreter? All other examples here are processed in fractions of seconds.) Gema's recursive pattern not seems to be affected by the recursion level, but the amount of non-matching text increases processing time exponentially.

# Answer
> 15 votes
# C, 52 bytes

```
j;f(char*s){for(j=0;*s=s[j];s[j]==94?s--,j+=3:s++);}

```

We define a function `f` that takes a pointer to the string as input. After the function call, that pointer will contain a modified string.

A simple test:

```
int main(int argc, char** argv) {
    char buf[300] = "Digital Trauma^H^H^H^H^H^H^H^H^H^H^H^H^H^HMaria Tidal Tug^H^H^H^H^H^H^H^H^H^H^H^H^H^H^HDigital Trauma";
    f(buf);
    printf(buf);
    return 0;
}

```

The above prints:

```
Digital Trauma

```

# Answer
> 14 votes
# Haskell, 47 bytes

```
h(a,_:_:b)=f$init a++b;h(x,_)=x
f=h.span(/='^')

```

Defines a function `f :: String -> String`. How it works:

```
    f "ab^Hc^Hd"
=== h ("ab", "^Hc^Hd")   (find ^H)
=== f ("a" ++ "c^Hd")    (backspace)
=== f "ac^Hd"            (join)
=== h ("ac", "^Hd")      (find ^H)
=== f ("a", "d")         (backspace)
=== f "ad"               (join)
=== h ("ad", "")         (find ^H)
=== "ad"                 (no ^H: base case)

```

# Answer
> 12 votes
# CJam, ~~14~~ 13 bytes

```
q"^H"/{W\ts}*

```

**How it works**

```
q                   e# Read the entire input
 "^H"/              e# Split it on occurrences of string "^H"
      {    }*       e# Reduce on the split array
       W\t          e# This is the tricky part. We know that if there are two parts that we
                    e# are reducing on, they must be separated by "^H". Which in turn means
                    e# that from the first part, last characters needs to be deleted
                    e# So we simply put the second part in place of the last character of the
                    e# first part.
          s         e# Doing the above makes it a mixed array of character and string.
                    e# So we convert it to a single string, ready to be served as first part
                    e# in next reduce iteration

```

*UPDATE: 1 byte saved thanks to jimmy23013*

Try it online here

# Answer
> 11 votes
# Retina, 13 bytes

Retina

```
+`.\^H(.*)
$1

```

The two lines should go to their own files but you can run the code as one file with the `-s` flag.

At each step we delete the first match for `.\^H` in the string. We repeat this (with the `+` modifier) until no deletion happens.

# Answer
> 10 votes
# JavaScript (*ES6*), 39 bytes

```
f=s=>(t=s.replace(/.\^H/,''))!=s?f(t):t

// TEST

Out=x=>O.innerHTML+=x+'\n'

Test=_=>(Out(I.value + "\n-> " + f(I.value)),I.value='')

;["Horse^H^H^H^H^HCow"
,"Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ."
,"123^H45^H^H^H78^H"
,"Digital Trauma^H^H^H^H^H^H^H^H^H^H^H^H^H^HMaria Tidal Tug^H^H^H^H^H^H^H^H^H^H^H^H^H^H^HDigital Trauma"]
.forEach(t => Out(t + "\n-> " + f(t)))
```

```
#I { width:400px }
```

```
<pre id=O></pre>
<input id=I><button onclick='Test()'>-></button>
```

# Answer
> 10 votes
# Perl, ~~20~~ ~~16~~ 15 bytes

(14 characters code + 1 character command line option.)

```
s/.\^H//&&redo

```

Sample run:

```
bash-4.3$ perl -pe 's/.\^H//&&redo' <<< "Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ."
Be nice to this gentleman, he's visiting from corporate HQ.

```

# Answer
> 9 votes
# Julia, ~~58~~ ~~42~~ 41 bytes

Saved 16 bytes thanks to manatwork and 1 thanks to Glen O!

```
f(s)='^'∈s?f(replace(s,r".\^H","",1)):s

```

This creates a recursive function that accepts a string and returns a string.

This replaces one occurrence of `^H` at a time with an empty string while the input contains `^`.

Examples:

```
julia> f("123^H45^H^H^H78^H")
"17"

julia> f("pizza is alright^H^H^H^H^H^Hwesome")
"pizza is awesome"

```

# Answer
> 8 votes
# REGXY, 10 bytes

Uses REGXY, a regex substitution based language. Replaces any character followed by ^H with nothing. The second line then executes which is just a pointer to the previous line, repeating the substitution until it fails to match.

```
/.\^H//
//

```

This compiles and executes correctly with the sample interpreter in the link above, but the solution is perhaps a bit cheeky as it relies on an assumption in the vagueness of the language specification. The spec states that the first token on each line (before the /) acts as a label, but the assumption is that a null label-pointer will point back to the first command in the file with a null label (or in other words, that 'null' is a valid label). A less cheeky solution would be:

```
a/.\^H//
b//a

```

Which amounts to 13 bytes.

# Answer
> 7 votes
# Python 3, 53 bytes

```
o=""
for x in input().split("^H"):o=o[:-1]+x
print(o)

```

But personally I like this wordier version better:

```
H=input().split("^H")
print(eval("("*~-len(H)+")[:-1]+".join(map(repr,H))))

```

The interesting thing is that

```
'B''a''c''k''h''a''n''d''e''d'[:-1][:-1][:-1][:-1][:-1][:-1]

```

actually works and gives `'Back'`, so I tried to map `^H -> [:-1]` and any other char `c -> 'c'` then `eval`, but unfortunately you can't have any strings afterwards without a `+`, so this fails:

```
'B''a''c''k''h''a''n''d''e''d'[:-1][:-1][:-1][:-1][:-1][:-1]'s''p''a''c''e''s'

```

# Answer
> 7 votes
# Haskell, ~~52~~ 47 bytes

```
import Data.Lists
foldl1((++).init).splitOn"^H"

```

Usage example:

```
> map (foldl1((++).init).splitOn"^H") ["Horse^H^H^H^H^HCow", "123^H45^H^H^H78^H", "Digital Trauma^H^H^H^H^H^H^H^H^H^H^H^H^H^HMaria Tidal Tug^H^H^H^H^H^H^H^H^H^H^H^H^H^H^HDigital Trauma"]
["Cow","17","Digital Trauma"]

```

How it works:

```
                  splitOn"^H"     -- split on substring "^H", e.g "Horse^H^H^H^H^HCow" -> ["Horse","","","","","Cow"]
                 .                -- then
foldl1(         )                 -- fold from left by
            init                  --   first dropping the last char from the left argument
       (++).                      --   second concatenating left and right argument

```

# Answer
> 6 votes
# Ruby, ~~27~~ ~~24~~ 20 bytes

(19 characters code + 1 character command line option.)

```
$_=$`+$'while/.\^H/

```

Thanks to:

* Ventero for suggesting to use the global variables (-4 characters)

Sample run:

```
bash-4.3$ ruby -pe '$_=$`+$'"'"'while/.\^H/' <<< "Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ."
Be nice to this gentleman, he's visiting from corporate HQ.

```

# Answer
> 4 votes
# Vim, 12 bytes

```
qqt^3xh@qq@q

```

Try it online!

Makes use of the fact that "`^` will only appear as `^H`".

### Explanation

```
qqt^3xh@qq@q
qq     @qq@q    Define an indefinitely looping recursive macro and immediately call it
  t^            Move to just before the next ^ character in the line
    3x          Delete 3 characters (the one to be deleted, ^, and H)
      h         Move left 1 step (to be in position for the next search)

```

# Answer
> 4 votes
# V (vim), ~~16~~ 14 bytes

```
qq:s/.^H
@qq@q

```

Try it online!

similar to sed, but uses Vim's recursion.

# Answer
> 3 votes
# Pyth - 19 bytes

Reduce works really, really well with this but it only does one char at a time so I had to spend almost as many chars as the actual algo to do a replace `^H` with linebreak. Looking for a better way to do that.

```
u?+GHnHbPGjbcz"^H"k

```

Try it online here.

# Answer
> 3 votes
# Python 2, 50

It's a bit odd having a second `lambda` in there, but seems to be the best Python so far.

```
lambda s:reduce(lambda a,b:a[:-1]+b,s.split('^H'))

```

# Answer
> 3 votes
# Julia, ~~41~~ 39 bytes

```
s->foldl((t,v)->chop(t)v,split(s,"^H"))

```

What it's doing is using ^H as a delimiter, and then removing the last character on each string then concatenating the next string before removing the last character again. Unlike the other Julia answer, this is not a recursive function.

Note: I've removed the function name from the definition. Originally, it said `f(s)=` rather than `s->`, and you used it as `f("AAA^HB^H^H")`... but I'm saving two bytes by letting it be "anonymous", and use itself as its name. You use it like this:

```
(s->foldl((t,v)->chop(t)v,split(s,"^H")))("AAA^HB^H^H")

```

(you can also assign a variable to it as `f=s->foldl((t,v)->chop(t)v,split(s,"^H"))`, then `f("AAA^HB^H^H")` will work)

# Answer
> 3 votes
# TeaScript, 7 bytes \[Not competing\]

**Not competing** as TeaScript was made after this challenge was posted. This is here as reference.

```
xW/.\^H

```

This uses the new TeaScript 3, and recursive replaces to remove the characters

# Answer
> 3 votes
# Japt, 8 bytes

```
Ue/.\^H/

```

Try it online!

### How it works

```
U        // Take the input,
e/.\^H/  // and recursively replace any char followed by "^H" with
         // (nothing, defaults to an empty string).
         // Implicit: output last expression

```

# Answer
> 3 votes
# brainfuck, 81 bytes

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

```

Try it online!

# Answer
> 2 votes
# ECMAScript 6, 57 bytes

```
s=>{while(~s.indexOf`^H`)s=s.replace(/.\^H/,'');return s}

```

This is ~~probably golfable, just gotta think of a way~~ probably not

# Answer
> 2 votes
# R, ~~54~~ 52 bytes

```
f=function(s)ifelse(s==(r=sub(".\\^H","",s)),r,f(r))

```

Same basic idea as my Julia answer. This creates a recursive function that accepts a string and returns a string. If the input is equal to itself with a single occurrence of `^H` removed, return it, otherwise call the function again.

You can try it online!

# Answer
> 2 votes
# K5, 64 bytes

K isn't really designed for this kind of work...

```
{[s]$[2>#s;s;`=t:*&{"^H"~2#x_s}'1+!-2+#s;s;,/2#2!|(0,t,3+t)_s]}/

```

# Answer
> 2 votes
# golflua, 36 bytes

```
\f(s)@o!=s o=s;s=s:g(".^H","",1)$~s$

```

Sample run:

```
Lua 5.2.2  Copyright (C) 1994-2013 Lua.org, PUC-Rio
> \f(s)@o!=s o=s;s=s:g(".^H","",1)$~s$
> w(f("Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ."))
Be nice to this gentleman, he's visiting from corporate HQ.

```

# Answer
> 2 votes
# Javascript, 62 bytes

Not the shortest one, but works fine.

```
t=prompt();while(t.match(R=/.\^H/))t=t.replace(R,'');alert(t);
```

This probably can be shortened a lot!

# Answer
> 2 votes
# Java, ~~78~~ 77 bytes

```
String f(String a){while(!a.equals(a=a.replaceFirst(".\\^H","")));return a;}

```

# Answer
> 2 votes
# (Visual)FoxPro any version 80 bytes

```
PARA t
DO WHILE AT('^H',t)>0
t = STRT(t,SUBS(t,AT('^H',t)-1,3))
ENDDO
RETU t

```

Repeating string translation to empty by finding ^H and backing up one character.

# Answer
> 2 votes
# rs, 8 bytes

Technically, this doesn't count, as it depends on a feature I added after this question was posted. However, I think it's pretty neat.

```
+?1.\^H/

```

Live demo and test cases.

# Answer
> 2 votes
# Jelly, 9 bytes

```
œṣ⁾^HṖ;¥/

```

Try it online!

Not a new approach, but the question was missing a Jelly answer

## How it works

```
œṣ⁾^HṖ;¥/ - Main link. Takes a string S on the left
  ⁾^H     - Yield "^H"
œṣ        - Split on "^H"
       ¥/ - Reduce by the following:
     Ṗ    -   Remove the last character
      ;   -   And append the right argument

```

# Answer
> 2 votes
# Vim, ~~38~~ 35 bytes

Saved 3 bytes thanks to Leo!

```
qa:%s/\([^H]\|\^\@<!.\)\^H//g
@aq@a

```

Try it online!

See Razetime's answer for a shorter and smarter version of this.

qa:%s/\([^H]\|\^\@<!.\)\^H//g
@aq@a

qa                                     Start recording a macro a
  :%s/                                 Substitute in entire file
      \([^H]\|\^\@<!H\)                Regex for the character to be deleted
        [^H]                           A character that isn't H
            \|                         or
                    H                  an H
              \^\@<!                   that doesn't have a ^ before it
                       \^H             All of that followed by ^H
                          //           Replace with empty string
                            g          Global flag so it replaces multiple times
                                       Enter the command
@a                                     Recursively call macro a
  q                                    Stop recording
   @a                                  Run the macro
```
</code></pre>

# Answer
> 1 votes
# Java - 123 bytes

I personally like the `g---1` part the best.

```
String f(char[] a){String b="";for(int g=-1;++g<a.length;b=(a[g++]=='^'?b.substring(0,b.length()-1):b+a[g---1]));return b;}

```

expanded (slightly):

```
  String f(char[] a) {
      String b = "";
      for (int g = -1;
           ++g < a.length;
           b = (a[g++]=='^'
                ? b.substring(0, b.length() - 1)
                : b + a[g---1])
      );
      return b;
  }

```

# Answer
> 1 votes
# Python 2, 74 + 2 = 76 Bytes

I've tried a few approaches so far, this is the best I've been able to come up with so far.

```
n=input();o='';c=0
for l in n:d=l=='^';o=[o+l*(1-c),o[:-1]][d];c=d
print o

```

# Answer
> 1 votes
## Batch - 138 bytes

```
@!! 2>nul||cmd/q/v/c%0 %1&&exit/b
set s=%1&for /F %%a in ('"prompt $H&echo on&for %%b in (1)do rem"')do set D=%%a
echo %s:^H=!D! !D!%

```

The first line is a way of saving a few bytes over the lengthy `@echo off&setLocal enableDelayedExpansion` (which turns echo off and enables the delayed expansion of variables, in case you were wondering). I explained it in Tips for Golfing in Batch.

The second line is a neat little trick to save the a backspace control character into a variable. It's pretty hacky, and I can't pretend to take credit for it. It's sort of explained here. Basically uses the prompt command to generate a backspace character and captures it in a variable - in this case `!D!`.

The final line then performs the simple string manipulation of - replace `^H` with `!D!<SPACE>!D!`.

```
C:\>bsp.bat "testing^H^H^H test"
"test test"

```

Unfortunately it breaks with cases like `"AAA^HB^H^H"` \- where it should produce `"A"`, it instead produces `"A"B`. Which is somewhat confusing. I'll have to look into how Batch string manipulation works in some more depth.

```
C:\>bsp.bat "AAA^HB^H^H"
"A"B

```

Thanks to to some helpful people over here \- I now realize that I was only saving the backspace character (0x08), and so was only overwriting the characters. It now works with examples like the following:

```
C:\>bsp.bat "AAA^HB^H^H"
"A"

```

# Answer
> 1 votes
## Mumps, 84 Bytes

```
R Z S T="",Y=$L(Z,"^H") F I=1:1:Y{S T=T_$P(Z,"^H",I) S:I<Y T=$E(T,1,$L(T)-1)} W !,T

```

This could probably be made shorter as a function (1 byte I was able to save in quick testing) but I kinda like the one-liner aspect... :-)

The braces come from the Intersystems Cache flavour of Mumps which is what I'm most versed in.

# Answer
> 1 votes
# jq 1.5, ~~41~~ 37 bytes

(34 characters code + 3 characters command line option.)

```
reduce(./"^H")[]as$t("";.[:-1]+$t)

```

Sample run:

```
bash-4.3$ bin/jq -R -r 'reduce(./"^H")[]as$t("";.[:-1]+$t)' <<< "Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ."
Be nice to this gentleman, he's visiting from corporate HQ.

```

On-line test (Passing `-R` through URL is not supported – so input passed as JSON string literal. Passing `-r` through URL is not supported – check Raw Output yourself.)

# Answer
> 1 votes
# \>\<\>, ~~39~~ ~~38~~ 36 bytes

There was no \>\<\> answer so I thought I'd add one.

```
i:0(?v:'^'=?\
     ~   ~~i/
;!?lr<ro

```

# Answer
> 1 votes
# JavaScript, 60 bytes

```
b=n=>(v=n.search('^H'))>0?b(n.replace(n.slice(v-1,v+2),'')):n

```

Not as good as edc65's answer, but I wanted to try something that didn't use Regex.

# Answer
> 1 votes
# bash, 50 bytes

```
while [ "$a" != "${a/?^H/}" ];do a=${a/?^H/};done

```

Sample:

```
a=$'Horse^H^H^H^H^HCow'
while [ "$a" != "${a/?^H/}" ];do a=${a/?^H/};done
echo $a
Cow

a="Be nice to this fool^H^H^H^Hgentleman, he's visiting from corporate HQ."
while [ "$a" != "${a/?^H/}" ];do a=${a/?^H/};done
echo $a
Be nice to this gentleman, he's visiting from corporate HQ.

```

This could work with real (binaries) backspaces as well:

```
a=$'Be nice to this fool\b\b\b\bgentleman, he'\'$'s visiting from corporate HQ.'
echo $a.. but:
Be nice to this gentleman, he's visiting from corporate HQ... but:
printf %q\\n "$a"
$'Be nice to this fool\b\b\b\bgentleman, he\'s visiting from corporate HQ.'

while [ "$a" != "${a/?$'\b'/}" ];do a=${a/?$'\b'/};done
printf %q\\n "$a"
Be\ nice\ to\ this\ gentleman\,\ he\'s\ visiting\ from\ corporate\ HQ.

```

# Answer
> 1 votes
# JavaScript, 60 Bytes

I know there is already a JS answer here, but wanted to do it without regexes, because regex is really almost a language by itself. I'm sorry if you feel I shouldn't post this, this is my first post.
`X` is the string to be operated upon.

```
while((z=x.indexOf('^D'))>0){x=x.slice(0,z-1)+x.slice(z+2);}

```

### Test

Put this into your browser's address bar.

```
javascript:x=prompt('Enter the sentence to be erased');while((z=x.indexOf('^D'))>0){x=x.slice(0,z-1)+x.slice(z+2);}alert(x);

```

I love JS because it will let you do things like saying `(z=x.indexOf('^D))>0`, and it will both assign `z.indexOf('^D');` to `x` and evaluate `z.indexOf('^D')` in the condition, which saves me precious bytes in this problem. It's not very useful otherwise, but it's fun!

# Answer
> 1 votes
# Emacs Lisp, ~~45~~ 73 bytes

```
(lambda(s)(while(string-match".^H"s)(set's(replace-match"" nil nil s)))s)

```

Searches for the first occurence of anything else and `^H` as long as it exists and replaces it with an empty string.

~~Old, incorrect version~~

```
(lambda(s)(replace-regexp-in-string".^H"""s))

```

# Answer
> 1 votes
# Oracle SQL 11.2, 172 bytes

```
WITH v(s,i)AS(SELECT:1,INSTR(:1,'^')FROM DUAL UNION ALL SELECT LPAD(s,i-2)||SUBSTR(s,i+2),INSTR(s,'^',1,2)-3 FROM v WHERE i>0AND'^'<>s)SELECT s FROM v WHERE INSTR(s,'^')=0;

```

Un-golfed

```
WITH v(s,i) AS                        -- Recursive view, s-> string, i->pos of first ^
(
  SELECT :1,INSTR(:1,'^')             -- Initialisation view
  FROM   DUAL
  UNION ALL
  SELECT LPAD(s,i-2)||SUBSTR(s,i+2),  -- Remove the ^ at pos i and the characters before and after
         INSTR(s,'^',1,2)-3           -- Compute the pos of the next ^ (the 2nd of s as before the remove just above)
  FROM   v
  WHERE  i>0                          -- Exit clause : no more ^
    AND  s<>'^'                       -- Needed to circumvent oracle's cycle detection, without it 123^H45^H^H^H78^H will fail
)
SELECT s FROM v WHERE INSTR(s,'^')=0; -- Keep only the row without any ^

```

# Answer
> 1 votes
# K (ngn/k), ~~23~~ 16 bytes

-7 bytes by rereading question (specifically, "`^` will only appear as `^H`")

```
{x_/3#-1+x?"^"}/

```

Try it online!

Removes one instance of `?^H` on each invocation, and is run until convergence (i.e. no more `^`'s are present).

* `{...}/` run function on (implicit) input until it converges
* `-1+x?"^"` get the index of the character immediately prior to the first `^` in `x`
* `x_/3#` drop the value occurring at that index three times

# Answer
> 1 votes
# Vyxal, 9 bytes

```
‛^H/ƒλ$Ṫp

```

Try it Online! Port of caird coinheringaahing's Jelly answer.

```
   /      # Split on
‛^H       # "^H"
    ƒλ--- # Reduce by
        p # Prepend to the first item
      $Ṫ  # The second with its last item removed

```

# Answer
> 0 votes
# Javascript ES6, ~~41~~ 39 bytes

```
f=s=>s==(s=s.replace(/.\^H/,""))?s:f(s)

```

# Answer
> 0 votes
# , 8 chars / 10 bytes (noncompetitive)

```
ïė/.\^H/

```

`Try it here (Firefox only).`

Works like all of the other JSGL's.

# Answer
> 0 votes
# APL (Dyalog Unicode), 18 bytes

```
'.\^H'⎕R''⍠'ML'1⍣≡

```

Try it online!

# Answer
> 0 votes
# Swift, 81 bytes

```
let f={(s:inout _)in while(s+"").contains("^"){s={s.replacing}()(#/.\^H/#,"",1)}}

```

Call it like this:

```
var s = "Horse^H^H^H^H^HCow"
f(&s)
print(s) // "Cow"

```

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


title: Is this a Permutation of 1..n

text:
# Question
Title: Is this a Permutation of 1..n
Input a non-empty array with \\$n\\$ positive integers. Test if the input array contains every integer in \\$1\cdots n\\$.

In case you prefer 0-indexed numbers, you may choose to input an array of non-negative integers, and test if the input array contains every integer in \\$0\cdots (n-1)\\$ instead. All testcases and formula listed below use 1-index. You may need to adjust them if you choose this option.

## Input / Output

Input is an array \\$A\\$ with \\$n\\$ positive integers:

$$ A = \left\[A\_1,\dots,A\_n\right\] $$ $$ \forall i \in \left\[1,\dots,n\right\]: A\_i\>0 $$

Output if input \\$A\\$ satisfies:

$$ \forall i \in \left\[1,\dots,n\right\]: i \in A $$

Output would be two distinct values, or truthy vs falsy values (swap meaning of truthy / falsy is allowed).

## Rules

* This is , shortest code wins. And since this is code-golf, don't worry about time / memory complexity of your code. You may even timeout on TIO as long as your program works when giving it more time to run.

## Testcases

### Truthy

```
1
1,2
2,1
1,3,2
3,1,2
1,2,3,4,5,6,7,8,9,10,11,12
12,11,10,9,8,7,6,5,4,3,2,1
6,3,8,12,1,10,4,2,7,9,5,11
16,37,14,15,23,8,29,35,21,6,5,34,38,9,36,26,24,32,28,7,20,33,39,12,30,27,40,22,11,41,42,1,10,19,2,25,17,13,3,18,31,4

```

### Falsy

```
2
12
1,1
1,3
2,3
3,3
2,1,3,2
1,4,3,1
4,1,2,4
1,2,2,5,5
1,3,3,3,5
8,7,5,3,4,1,6
5,7,1,4,6,1,8,3
6,3,5,4,7,1,8,1,2
6,5,3,8,2,7,9,4
1,1,1,1,1,1,1,1
1,5,9,13,11,7,3
14,6,12,4,10,8,16,2
34,33,38,17,35,11,36,31,28,14,6,15,18,2,19,40,29,41,9,1,27,23,20,32,26,25,37,8,13,30,39,7,5,3,21,4,11,16,10,22,12,24
38,27,20,23,31,6,2,24,21,31,33,7,26,12,14,17,3,2,28,31,5,23,28,27,37,32,7,39,22,6,35,42,19,3,35,17,35,40,22,13,27,7

```

# Answer
> 16 votes
# Risky, ~~7 bytes~~ 7 bytes and a palindrome

```
1_??!0:0!??_1

```

Try it online!

## Explanation

```
1   sort
_
?         input
?     filter by
!       factorial
0         0
: =
0   range
!       length
?         input
?     find first number such that
_
1         1

```

# Answer
> 15 votes
# , 7 bytes

```
-:/:@/:

```

Try it online!

Ninja'd by hyper-neutrino :(

Takes zero-based input. Applying Grade Up twice to a vector gives a "ranking" of each element, so that 0 is the smallest, 1 is the next smallest, ... up to n-1, breaking ties by giving a smaller number to the one appearing first. A vector is a permutation if and only if the ranking is identical to itself.

# , 7 bytes

```
2|C.!.2

```

Try it online!

Takes zero-based input. `C.!.2` is a built-in for "cycle parity". It gives 1 if a permutation has even number of swaps, -1 if odd, and 0 if not a valid permutation. I take it modulo 2 to convert all nonzero results to 1 (the only truthy value in J).

~~Even if error/non-error output were allowed, it is too bad that permutation-related built-ins `A.` and `C.` don't error on all possible non-permutations.~~

# , 7 bytes

```
#\-:/:~

```

Try it online!

Takes one-based input. `#\` is a golfing trick for getting 1..n, which is compared to the sorted array `/:~` of the original.

---

If output by erroring/non-erroring is allowed:

# , 3 bytes

```
C.~

```

Try it online!

Takes zero-based input. Abuses dyadic form of `C.`, whose left argument must strictly be a permutation. It throws an `index error` otherwise.

# Answer
> 13 votes
# APL (Dyalog Unicode), 5 bytes

```
⊢≡⍋∘⍋

```

Try it online!

-4 bytes thanks to Bubbler by turning this into a train and via using `⍵≡` to match the whole array instead of `∧/⍵=` to match element-wise and then reduce by AND.

```
⊢≡⍋∘⍋    Train
 ≡         Check equality between
⊢         (Right argument ⍵) and
  ⍋∘⍋    Composed function {⍋⍋⍵}; grade up twice

```

Grading up twice gives the minimum permutation of length X that has the same (non-strict) ordering as the original - so, if the permutation of the right order is the same as the original, then the original was that permutation and thus a permutation.

# Answer
> 12 votes
# Python 3, 31 bytes

Input is \\$ 0 \\$-indexed.

```
lambda a:{*a}=={*range(len(a))}

```

Try it online!

This is the most obvious implementation I could think of. It compares the set of \\$ a \\$ to the set of numbers from `0` to `len(a)-1`.

# Python 3, 30 bytes

As @ovs suggested, we can save a byte by switching the definition of truthy and falsey. A valid permutation returns a falsey value, and truthy otherwise.

```
lambda a:{*a}^{*range(len(a))}

```

Try it online!

# Answer
> 12 votes
# Haskell (1 indexed), 29 bytes

*Courtesy of AZTECCO*

```
g l=all(`elem`l)[1..length l]

```

Try it online!

# Haskell (0 indexed), ~~42~~ ~~32~~ 31 bytes

*Lynn saved one byte with the pointfree solution.*

```
all.(.fst).flip elem<*>zip[0..]

```

Try it online!

I tried a bunch of creative stuff with scans, folds and zips, but the boring solution ended up being the shortest.

Both of these check that every integer in the available range is in the list. The first is `1` to the length of the list, the second is `0` to 1 less than the length of the list.

# Answer
> 10 votes
# Zsh, ~~18~~ ~~12~~ 11 bytes

```
>$@<{1..$#}
```

Attempt This Online!

Outputs via exit code: 0 for a permutation and 1 for not a permutation

Explanation:

* `>`: create files called
    + `$@`: each command-line argument
* `{1..$#}`: range from 1 to the number of command-line arguments
* `<`: try to read from each of those numbers as a file

If any command fails, then that means one of the files in the range didn't exist, so it's not a valid permutation, and zsh will exit with status 1.

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

Expects 0-indexed values. Returns a Boolean value.

```
a=>a.every(x=>(a[~x]^=1)/a[x])

```

Try it online!

### Commented

We test whether all values are less than the length \\$N\\$ of the input array and make sure that there is no duplicate. Both conditions are satisfied iff the array consists of all values from \\$0\\$ to \\$N-1\\$.

```
a =>             // a[] = input array
  a.every(x =>   // For each value x in a[]:
    (a[~x] ^= 1) //   ~x is -x - 1, which is guaranteed to be negative
                 //   Therefore, a[~x] is a property (such as '-1') of
                 //   the underlying object of a[], which can be safely
                 //   used to store values that were already encountered
                 //   If a[~x] XOR 1 is not equal to 1, we have a
                 //   duplicate value
    / a[x]       //   We also make sure that a[x] is defined, which
                 //   means that x < a.length
                 //   The possible cases are:
                 //     1 / n, n > 0 is a truthy number  \__ success
                 //     1 / 0 is +Infinity (also truthy) /
                 //     1 / undefined is NaN (falsy)     \
                 //     0 / n, n > 0 is 0 (falsy)         |_ failed
                 //     0 / 0 is NaN (falsy)              |
                 //     0 / undefined is NaN (falsy)     /
  )              // End of every()

```

# Answer
> 10 votes
# Julia 1.5, 6 bytes

This is a built-in, so it's quite easy for Julia

```
isperm

```

Use it like this: `isperm([6,3,8,12,1,10,4,2,7,9,5,11])`

# Answer
> 9 votes
# , ~~26~~ 24 bytes

-2 bytes thanks to pajonk.

```
all(seq(x<-scan())%in%x)

```

Try it online!

If input is of length at least 2, `seq(x)` outputs the integers from 1 to `length(x)`; if input is of length 1, it outputs the integers from 1 to `x`. Return `TRUE` iff all those integers are elements of `x`.

# Answer
> 7 votes
# Ruby, 21 bytes

```
->a{a|[*1..a.max]==a}

```

Try it online!

-1 byte thanks to ovs!

-3 bytes thanks to Razetime!

# Answer
> 7 votes
# Factor \+ `math.unicode`, ~~24~~ 23 bytes

```
[ dup length iota ⊃ ]

```

Try it online!

0-indexed to save a byte. Is the input a superset of \\$\[0..|input|)\\$?

# Answer
> 7 votes
# Python 3, 33 bytes

```
lambda x:max(*x,len(x))^len({*x})

```
1. Check uniqueness: len(x) = len(set(x))
2. For unique set: max(x) == len(x) iff x = 1...n

Try it online!

# Answer
> 6 votes
# Zsh, 13 bytes

```
: >$@<{1..$#}

```

Try it online!

```
:              noop command to prevent hanging while waiting for input
  >$@          create a file for every argument
     <{1..$#}  read every file between 1 and the number of arguments

```

Since the redirects are handled left-to-right, we create the files before trying to read them. If we encounter a number for which no file exists (for example on `zsh x.zsh 4 1 2`), we get the following error:

`no such file or directory: 3`

and receive exit code 1. If it was indeed a permutation, we exit cleanly with code 0.

# Answer
> 6 votes
# BitCycle `-u`, 91 bytes

```
v 0< <  <
ABv
^/=^?^
v<
Hvv <<
/<CDv
!v /=^
v  =\\\v
 ~~< >+
    <@>G^
 >E\^
>~> \/
 > F//@

```

Outputs `1` for truthy, `0` for falsey. Try it here!

## Explanation

The algorithm is as follows:

* Loop until the list is empty:
    1. Decrement every number in the list
    2. If there is not exactly one zero in the list, halt and output 0
    3. Otherwise, remove the zero from the list and continue
* If the loop ran to completion, output 1

The program contains two main sections, one that accomplishes step 1 and one that accomplishes steps 2 and 3. Here they are as separate programs:

### Step 1

```
?0 v
v  <
ABv
^/=^
  C\!

```

Subtracts 1 from every number in the list. Try it!

We prefix a `0` bit to the input so every unary number has a leading `0`. Each time through the `A`-`B` loop, we use the first bit to set the switch (`=`) and then send it into the `C` collector.

* If the first bit was `0`, the rest of the bits go west. We use the splitter `/` to discard the second bit and sent the rest of the bits back into `A`. The second bit is guaranteed to be `1`, since all the numbers in the list are positive.
* If the first bit was `1`, the rest of the bits go east, right back into `A`.

The upshot is that one bit from each of the unary numbers gets discarded, subtracting 1 from each of them.

### Steps 2-3

```
?0v  <
  CDv
 v /=^
v  =\\\v
 ~~< >+
    < >G\!
 >E\^@
>~> \/
 > F//@

```

Halts if there are no zeros or multiple zeros in the list, otherwise filters the zero(s) out of the list. Try it!

We once again prefix a `0` bit to the input. (In the actual program, this only needs to be done once.) Each time through the `C`-`D` loop, we use the first bit to set the northeast switch (`=`).

* If the first bit was `1`, the rest of the bits go east, right back into `C`.
* If the first bit was `0`, the rest of the bits go west. We peel off the second bit and use it to set the southwest switch. Then we send it through the eastern dupneg (`~`), from which a negated copy goes into the `E` collector and the original copy goes back into `C`. The rest of the bits go through both dupnegs; a negated copy goes into `E`, and a doubly negated copy goes back into `C`.

The upshot is that all the bits after the first go back into `C` unchanged, but if the first bit was `0`, the second bit sets the southwest switch and some bits go into `E`.

Meanwhile, the first bit goes through this structure:

```
 =
=\\\v
  >+
   >G

```

Starting from the northeast switch moving south, it bounces off the westernmost two splitters (`\`) and is sent to the branch (`+`). If it is `1`, it turns right and goes into the `G` collector. If it is `0`, it turns left, bounces off the easternmost splitter, passes back through the other two splitters, and reaches the southwestern switch.

* If the second bit was `1`, the switch sends the first bit back eastward, through all the splitters, and into the `G` collector.
* If the second bit was `0`, the switch sends the first bit westward; it eventually reaches a dupneg, from which one copy goes into the `E` collector and one into `F`.
* If there was no second bit, the inactive switch passes the first bit straight through, which behaves the same as the `0` case.

The upshot is that `G` gets the same list but without any `0` bit that is followed by another `0` bit or the end of the string. Also, `F` gets a bit for each of the `0` bits that didn't go into `G`, and `E` is guaranteed to have at least one bit in it.

Next, the `E` collector opens, dumps its first bit into `F`, and discards the rest. `F` now contains one bit if there were no zeros in the list, two bits if there was exactly one zero, and more than two if there were multiple zeros.

The bits from the `F` collector then go through this structure:

```
   @
> \/
 F//@

```
* If there are more than two bits, the first two bounce off the splitters on the bottom row, allowing the third one to pass through both splitters and hit the southeastern halt instruction (`@`).
* If there are two bits, the first one bounces off the westernmost two splitters and goes west. Meanwhile, the second one bounces off the easternmost two splitters and goes east off the playfield. The first bit is sent back east, goes through the two northernmost splitters, and off the playfield.
* If there is one bit, it bounces off the westernmost splitters, turns around, bounces off the northeastern splitter, and hits the northern halt instruction (`@`).

The upshot is that if there was not exactly one zero in the list, the program halts. No bits have been output yet, which with the `-u` flag means the output is `0`. If there was exactly one zero, the program does not halt; the `G` collector opens and the program continues.

### Tying it together

In the full program, the output from the `G` collector is sent back into `A`, starting the loop over again.

Meanwhile, the discarded `1` bits from step 1 have been collected in `H`. Once there are no bits left in the main loop, `H` opens. The splitter (`/`) sends its first bit into the sink (`!`), outputting `1`. The rest of the bits go through the splitter and off the playfield.

# Answer
> 5 votes
# Jelly, 3 bytes

```
Ṣ⁼J

```

Try it online!

```
Ṣ⁼J   Monadic Link
Ṣ     1-chain: sort the input
 ⁼J   2,1-chain: is (the input sorted) equal to (range on the length of the input)?

```

# Answer
> 5 votes
# , 27 bytes

```
any(rank(x<-scan(),,'f')-x)

```

Try it online!

Returns FALSE for Truthy, TRUE for FALSY (just to shave one byte)

**Explanation:**

If the array containing the rank of each value is equal to the input array, then it's a permutation of `1..n`

**Note:**
5 bytes are wasted because in `rank` function the default handling strategy in case of ties is "average their ranks" instead of any of the other possibilities... argh!

# Answer
> 5 votes
# Brachylog, 3 bytes

```
o~⟦

```

Try it online!

0-indexed. Succeeds or fails.

```
o      The input sorted
 ~⟦    is the range from 0 to something inclusive.

```

Note that this can not be golfed to `⟦p` with reversed input, as it fails to terminate for cases it should reject:

```
⟦     Choose an integer. Is the range from 0 to it inclusive
 p    a permutation of the input?

```

# Answer
> 5 votes
# Pyth, 3 bytes

```
UIS

```

Try it online!

# Answer
> 4 votes
# Red, 46 bytes

```
func[a][i: 0 until[alter a i: 1 + i]single? a]

```

Try it online!

increments a counter as long as the counter is found in the list, and then checks it against the length.

`1 = length?` is used as a polyfill for `single?` in the latest Red version.

-5 bytes from tsh.

-5 bytes from Galen Ivanov.

# Answer
> 4 votes
# Perl 5, 38 bytes

```
sub{!grep!{map+($_,1),@_}->{$_},1..@_}

```

Try it online!

# Answer
> 4 votes
# Java (JDK), 43 bytes

```
a->a.sorted().reduce(1,(x,y)->y==x?x+1:0)>0

```

Try it online!

## Explanations

This answer is a `Predicate<IntStream>` and requires that the input contains no `0`.

First this code sorts the input stream. The reduce method then makes sure that each consecutive number is encountered, and return the last encountered number. `x` always contains the next expected number, or `0` if we got an unexpected number. `1` is the first parameter of the `reduce` method as it's the first expected number. Given that `0`, or any negative number, is not allowed in the `IntStream`, when `0` is returned for the first time, it will always be returned for the remaining of the process.

# Answer
> 4 votes
# TypeScript's Type System, 450 442 bytes

```
type A<T extends any[]>=T extends{length:infer L}?(L extends number?L:never):never
type B<L extends number,T extends 0[]=[]>=T extends{length:L}?T:B<L,[...T,0]>
type C<N extends number,T extends number=1,R extends any[] = []> = R['length']extends N?R:C<N,A<[...B<T>,0]>,[...R,T]>
type D<T extends any[],U extends any[]>=T extends[]?true:T extends[infer H,...infer R]?H extends U[number]?D<R,U>:false:never
type F<T extends any[]>=D<T,C<A<T>>>

```

TypeScript Playground Link

## Explanation

```
// This allows getting the Length of any tuple via inferring its L property
type A<T extends any[]>=T extends{length:infer L}?(L extends number?L:never):never

// This creates a tuple of arbitrary length L (we need to use this later for arithmetic)
type B<L extends number,T extends 0[]=[]>=T extends{length:L}?T:B<L,[...T,0]>

// We can use this to generate an incrementing tuple of length L (e.g. [1, 2, 3, 4]). We use this to compare against the final array.
type C<N extends number,T extends number=1,R extends any[] = []> = R['length']extends N?R:C<N,A<[...B<T>,0]>,[...R,T]>

// This checks if two arrays have the same elements inside them
type D<T extends unknown[],U extends unknown[]>=T extends[]?true:T extends[infer H,...infer R]?H extends U[number]?D<R,U>:false:never

// Finally, we can use this to compare the chosen array T vs the increasing tuple N
type F<T extends any[]>=D<T,C<A<T>>>

```

# Answer
> 3 votes
# Wolfram Language (Mathematica), ~~22~~ 20 bytes

```
Sort@#==Range@Max@#&

```

-2 bytes, thanks to @ZaMoC:

Try it online!

# Answer
> 3 votes
# Stax, 5 bytes

```
c%R|}

```

Run and debug it

Explanation:

```
     ; Implicit input onto top of stack
c    ; Copy top of stack
%    ; Length of top of stack
R    ; Make range [1 .. n]
|}   ; Compare top two elements of stack. Arrays are different orderings of same elements?
     ; Implicit output of truthy/falsy

```

Could probably save a byte somewhere.

# Answer
> 3 votes
# jq, 20 bytes

```
[range(max)+1]==sort

```

Try it online!

## Explanation

```
       max            # Get the maximum of the input
 range(   )           # Generate the non-negative integers below that
           +1         # Add 1 to each of them
[            ]        # Collect as list
                sort  # Sort the input list
              ==      # Compare the two lists

```

# Answer
> 3 votes
# Nibbles, 1.5 bytes (3 nibbles)

```
-,,

```

Returns an empty list (falsy) if input is a permutation of 1..n, or a non-empty list (truthy) if it is not.

```
-       # remove
 ,      #   sequence of 1..
  ,     #   length of
        #   (implicitly) input
        # from
        #   (implicitly) input

```

# Answer
> 3 votes
# Python, ~~43~~ 39 Bytes

```
lambda x:sorted(x)==list(range(len(x)))

```

0-indexed. Uses `sorted()`, `range()` and `list()`. Surprisingly gives correct answer for empty list.

Test on TIO.

# Answer
> 2 votes
# JavaScript (Node.js), ~~40~~ 38 bytes

```
s=>s.sort((a,b)=>a-b).some((x,i)=>x^i)

```

Try it online!

Returns true for invalid and false for valid. Put a `!` before the `s.sort` for the otherway round. Takes input 0-indexed.

# Answer
> 2 votes
# Charcoal, 6 bytes

```
¬⁻Ｅθκθ

```

Try it online! Link is to verbose version of code. 0-indexed. Outputs a Charcoal boolean, i.e. `-` for permutation, nothing if not. Explanation:

```
   θ    Input array
  Ｅ     Map over elements
    κ   Current index
 ⁻      Remove values found in
     θ  Input array
¬       Check that nothing is left
        Implicitly print

```

(Mapping over the input indices is golfier than creating a range.)

# Answer
> 2 votes
# Japt, ~~4~~ 3 bytes

0-based

```
Íe¶

```

Try it or run all test cases

Saved a byte thanks to Etheryte pointing out one of my own favourite tricks that I somehow forgot!

```
Íe¶     :Implicit input of array
Í       :Sort
 e      :Every?
  ¶     :  Equal to its 0-based index

```

# Answer
> 2 votes
# jq, ~~20~~ ~~49~~ 36 bytes

```
length==max and max==(unique|length)

```

Try it online!

*Thanks to `tsh` and `xigoi` for catching mistakes in the previous attempts...*

Third time is the charm perhaps?

Since the rules limit the numbers to "positive integers", there's no need to test the minimum. Making sure the largest number in the list, the size of the original list and the size of a de-dup'd list are all the same is sufficient. So that's what this version does.

# Answer
> 2 votes
# C (gcc), ~~95~~ ~~73~~ 72 bytes

```
r,t,i,j;f(a,n)int*a;{for(r=i=n;i--;r*=!t)for(t=j=n;j--;)t*=i!=a[j];n=r;}

```

Try it online!

Inputs a pointer to an array \\$a\\$ of zero-based integers and its length \\$n\\$ (since C pointers to arrays carry no length information).
Returns a truthy value if all \\$0\dots (n-1)\\$ integers are present or a falsey value otherwise.

### Explanation

Goes through all the numbers \\$0\dots (n-1)\\$ (in reverse order) and tests to see if they're in \\$a\\$.

Saved a whopping 19 bytes thanks to AZTECCO!!!

# Answer
> 2 votes
# Raku, 14 bytes

```
{$_∖bag ^$_}

```

0-based.

Try it online!

* `$_` is the list argument to the function.
* `^$_` is a list of numbers from 0 to one less than the size of the input list.
* `bag ^$_` is a bag (a set with multiplicity) of that list of those sequential numbers.
* is the set difference operator. The left argument, the input list, is coerced to a bag because the right argument is a bag, from which one instance of each of the sequential numbers is removed. The result will be an empty bag only if the input list contained exactly one number from zero up to one less than its size. An empty bag is falsey in a boolean context, and a non-empty bag is truthy.

# Answer
> 2 votes
# 05AB1E, 3 bytes

```
{āQ

```

Try it online!

```
{āQ  # full program
  Q  # is...
 ā   # implicit input...
{    # sorted...
  Q  # equal to...
 ā   # [1, 2, 3, ..., length of...
     # implicit input...
{    # sorted...
 ā   # ]...
  Q  # ?
     # implicit output

```

# Answer
> 2 votes
# Husk, 3 bytes

```
-ŀ¹

```

Try it online!

What's left after removing (`-`) 1..length\_of\_input (`ŀ¹`) from the input?
Empty list = falsy (so input is permutation of 1..n); Non-empty list = truthy (input is not permutation of 1..n).

# Answer
> 2 votes
# Pyt, 6 bytes

```
şĐŁř=Π

```

Try it online!

```
ş              implicit input; sort in ascending order
 Đ             duplicate
  Ł            get length
   ř           push [1,2,... length]
    =          element-wise equal with sorted array?
     Π         product of booleans; implicit print

```

returns 1 if permutation of \[1,2,...\]; 0 otherwise

# Answer
> 2 votes
# Regex (ECMAScript+`(?^=)`RME), ~~37~~ ~~30~~ 28 bytes

```
(:x*)x\b(.*\1x:|(?^!.*\1\b))

```

Takes its input in unary, as a concatenation of strings of `x` characters whose lengths represent the numbers, separated and enclosed on both sides by `:` characters. Example: `:xxx:x:xx:` represents `3,1,2`.

Try it on replit.com \- **ECMAScript+`(?^=)`** (RegexMathEngine `-xli`)

Asserts that there exists no element \\$n\\$ for which there either is a subsequent duplicate element \\$n\\$, or for which there doesn't exist any element \\$n-1\\$ anywhere in the list if \\$n\ne 1\\$.

Returns "match" for falsy and "no match" for truthy **(inverted logic)**.

```
              # No anchor - can match starting at any point in the string
(:x*)x\b      # Start at any list element; \1 = {that element} - 1, including
              # the bounding character on its left side, consuming it without
              # consuming the bounding character following it.
(
    .*\1x:    # Match any subsequent list element whose value equals \1 + 1
|         # or...
    (?^!      # Negative lookinto - assert that the following pattern cannot
              # match the entire input string:
        .*    # Skip to any list element, putting it in tail (Works in concert
              # with the following expression's matching of the left-side
              # bounding character contained in \1)
        \1\b  # Assert that tail==\1, or if \1==0 this can match at the edge
              # of any element in the list (if we didn't need \1==0 to be able
              # to match, we could have used "\1:" instead)
    )
)

```

Using comma delimiting (e.g. `xxx,x,xx`) instead of this input method, would take +5 bytes:

```
\b(x*)x\b(.*,\1x\b|(?^!.*\b\1\b))

```

# Regex (PCRE+`(?^=)`RME), 29 bytes

```
^:(x*:(?^=.*:((?(2)\2)x):))*$

```

Try it on replit.com \- PCRE+`(?^=)` (RegexMathEngine `--pcre -xli`)

Golfwise, this is obsoleted by the 28 byte version above, but is kept here due to still being close in length, and using a different algorithm.

Iterate once for each list element: Find a list element whose value is the index of the current loop iteration. (Uses a nested backreference to accomplish this.)

Returns "match" for truthy and "no match" for falsy.

```
^                     # Anchor to start
:                     # Consume initial bounding character
(                     # Loop the following:
    x*:               # Consume one list element
    (?^=              # Lookinto - is matched against the entire string
        .*:           # Skip to any list element, putting it in tail
        (             # \2 = the  following:
            (?(2)\2)  # If \2 is set (i.e., if we're not on the first iteration)
                      # then include the previous value of \2 in its new value
            x         # Append one more "x" (if this is the first iteration,
                      # captures just one)
        )
        :             # Consume one bounding character
    )
)*                    # Iterate the above as many times as possible, minimum 0
$                     # Assert we've reached the end of the string

```

Using comma delimiting (e.g. `xxx,x,xx`) instead of this input method, would take +2 bytes:

```
^(x+,?(?^=.*\b((?(2)\2)x)\b))*$

```

But that regex is incredibly slow, and it takes another +1 byte to give it reasonable speed:

```
^(x++,?(?^=.*\b((?(2)\2)x)\b))*$

```

# Regex (ECMAScript 2018 / Python`regex` / .NET), ~~38~~ ~~31~~ 29 bytes

```
(:x*)x\b.*(\1x:|$(?<!\1\b.*))

```

Try it online! \- **ECMAScript 2018**
Try it online! / Attempt This Online! \- **Python (with `regex`)**
Try it online! \- **.NET**

A port of the ~~37~~ ~~30~~ 28 byte version, using variable-length right-to-left evaluated lookbehind instead of lookinto. Like it, returns "match" for falsy and "no match" for truthy **(inverted logic)**.

```
               # No anchor - can match starting at any point in the string
(:x*)x\b       # Start at any list element; \1 = {that element} - 1, including
               # the bounding character on its left side, consuming it without
               # consuming the bounding character following it.
.*             # Skip to any subsequent position in the string
(
    \1x:       # Match any subsequent list element whose value equals \1 + 1
|          # or...
    $          # Assert that we're at the end of the string
    (?<!       # Negative lookbehind - using right-to-left evaluation starting
               # from the current position (so read this from bottom to top),
               # assert that the following cannot match:
        \1\b   # Assert that head==\1, or if \1==0 this can match at the edge
               # of any element in the list (if we didn't need \1==0 to be able
               # to match, we could have used "\1:" instead)
        .*     # Skip to anywhere in the string, putting it in head
    )
)

```

Using comma delimiting (e.g. `xxx,x,xx`) instead of this input method, would take +5 bytes:

```
\b(x*)x\b.*(,\1x\b|$(?<!\b\1\b.*))

```

Try it online! \- ECMAScript 2018

# Regex (.NET), ~~36~~ 35 bytes

```
^:(x*:(?=.*(?<=:(x(?(2)\2)):.*)))*$

```

Try it online!

Golfwise, this is obsoleted by the 29 byte version directly above, but is kept here due to still being close in length, and using a different algorithm.

A port of the 29 byte PCRE+`(?^=)`RME version, using variable-length right-to-left evaluated lookbehind instead of lookinto. Like it, returns "match" for truthy and "no match" for falsy.

```
^                     # Anchor to start
:                     # Consume initial bounding character
(                     # Loop the following:
    x*:               # Consume one list element
    (?=               # Lookahead
        .*            # Skip to later in the string (".*$" would be faster)
        (?<=          # Lookbehind - evaluated right-to-left (so read this
                      # from bottom to top)
            :             # Consume one bounding character
            # Assert head==1 (on the first iteration) or head==\2+1 (on
            # subsequent iterations), capturing this as the new value of \2
            (
                x         # Append one more "x" (if this is the first iteration,
                          # captures just one)
                (?(2)\2)  # If \2 is set (i.e., if we're not on the first
                          # iteration) then include the previous value of
                          # \2 in its new value
            )
            :.*           # Skip to any list element, putting it in head
        )
    )
)*                    # Iterate the above as many times as possible, minimum 0
$                     # Assert we've reached the end of the string

```

Using comma delimiting (e.g. `xxx,x,xx`) instead of this input method, would take +2 bytes:

```
^(x+,?(?=.*(?<=\b(x(?(2)\2))\b.*)))*$

```

But that regex is incredibly slow, and it takes another +2 bytes to give it reasonable speed:

```
^(x+\b,?(?=.*(?<=\b(x(?(2)\2))\b.*)))*$

```

Try it online!

# Regex (ECMAScript 2018 / Java / Python`regex` / .NET), ~~44~~ ~~37~~ 35 bytes

```
(:x*)x\b(.*\1x:|(?<!(?=.*\1\b)^.*))

```

Try it online! \- ECMAScript 2018
Try it online! \- **Java**
Try it online! / Attempt This Online! \- Python (with `regex`)
Try it online! \- .NET

Based on the ~~37~~ ~~30~~ 28 byte version **(inverted logic)**.

Java needs to be "hinted" as to how far the lookbehind should go, thus necessitating the use of a lookahead inside the lookbehind.

# Regex (ECMAScript+`(?*)`RME / PCRE2 v10.35+), ~~41~~ 39 bytes

```
^(?*.*(:x*)x:)((.*\1x\b){2}|(?!.*\1\b))

```

Try it on replit.com \- **ECMAScript+`(?*)`** (RegexMathEngine `-xml`)
Attempt This Online! \- **PCRE2 v10.40+**

A port of the ~~38~~ ~~31~~ 29 byte version, using molecular lookahead instead of variable-length right-to-left evaluated lookbehind. Like it, returns "match" for falsy and "no match" for truthy **(inverted logic)**.

```
^                # Anchor to start
(?*              # Molecular (non-atomic) lookahead - try all possible matches
    .*(:x*)x:    # Skip to any list element; \1 = {the element} - 1, including
                 # the bounding character on its left side
)
(
    (
        .*\1x\b  # Match and consume any subsequent list element whose value
                 # equals \1 + 1, without consuming the bounding character on
                 # its right side (to allow this group to be repeated)
    ){2}         # Iterate the above 2 times
|          # or...
    (?!          # Negative lookahead - assert that the following cannot match:
        .*       # Skip to any list element, putting it in tail (Works in
                 # concert with the following expression's matching of the
                 # left-side bounding character contained in \1)
        \1\b     # Assert that tail==\1, or if \1==0 this can match at the edge
                 # of any element in the list (if we didn't need \1==0 to be
                 # able to match, we could have used "\1:" instead)
    )
)

```

# Regex (ECMAScript+`(?*)`RME / PCRE2 v10.35+), ~~44~~ 42 bytes

```
^(?!.*(:x*)\b.*\1:|(?*.*(:x+)x:)(?!.*\2:))

```

Try it on replit.com \- ECMAScript+`(?*)` (RegexMathEngine `-xml`)
Attempt This Online! \- PCRE2 v10.40+

Asserts that there exists no element \\$n\\$ for which there is a subsequent duplicate element \\$n\\$, and that there exists no element \\$n≥2\\$ for which there is no element \\$n-1\\$ anywhere in the list.

Returns "match" for truthy and "no match" for falsy.

This non-inverted logic version is being kept up, despite losing in golf to the inverted logic ~~41~~ 39 byte version above, to show how close it comes in length. This is because the second half of the logic, that asserts there are no non-consecutive elements, cannot be golfed by inverted logic, since the `.*:` must be inside the molecular lookahead.

```
^                  # Anchor to start
(?!                # Negative lookahead - assert that the following cannot match:
    .*(:x*)\b      # Skip to any list element; \1 = the element, including the
                   # bounding character on its left side
    .*             # Skip to any list element, putting it in tail (Works in
                   # concert with the following expression's matching of the
                   # left-side bounding character contained in \1)
    \1:            # Assert tail == \1
|              # or...
    (?*            # Molecular (non-atomic) lookahead - try all possible matches
        .*(:x+)x:  # Skip to any list element that's ≥ 2; \2 = {the element} - 1,
                   # including the bounding character on its left side
    )
    (?!            # Negative lookahead - only matches outside if the pattern
                   # inside fails to match.
        .*         # Skip to any list element, putting it in tail (Works in
                   # concert with the following expression's matching of the
                   # left-side bounding character contained in \2)
        \2:        # Assert tail == \2
    )
)

```

# Answer
> 2 votes
# Vyxal, 2 bytes

```
ż⊍

```

Try it Online!

Uses inverted truthiness (non-empty array for falsy, empty array for truthy)

This follows Vyxal's truthiness conventions, which can be checked using a boolify: Verify all test cases online! (boolified and logical NOT applied).

```
ż  # length range
 ⊍ # setwise difference

```

# Answer
> 2 votes
# Thunno 2, 2 bytes

```
ėṗ

```

Output with inverted booleans (allowed by community consensus). Add the `!` flag if you want `1` for truthy and `0` for falsy.

#### Explanation

```
ė   # Length range
 ṗ  # Set difference

```

#### Screenshot

# Answer
> 2 votes
# Nekomata \+ `-e`, 3 bytes

```
x↕=

```

Attempt This Online!

Inputs are 0-indexed.

```
x↕=
 ↕    Find a permutation of
x     the range from 0 to the length of the input minus 1
  =   that is equal to the input

```

The `-e` flag prints `True` if there is a solution, and `False` otherwise.

# Answer
> 2 votes
# Python, 39 Bytes

```
lambda x:sorted(x)==list(range(len(x)))

```

I am an account owned by PlaceReporter99. I am trying to get 20 rep so that I can access the chat rooms.

# Answer
> 2 votes
# Swift 5.9, ~~50~~ ~~48~~ ~~42~~ 37 bytes

```
let p={Set($0+[])==Set(1...$0.count)}

```

Play the fiddle!

# Answer
> 1 votes
# Vyxal `rR`, ~~5~~ 3 bytes

```
GṖc

```

Try it Online!

-2 thanks to lyxal

# Answer
> 1 votes
# C# (Visual C# Interactive Compiler), 46 bytes

```
a=>{a.Sort();int i=1;return a.All(x=>x==i++);}

```

Try it online!

# Answer
> 1 votes
# Retina 0.8.2, 26 bytes

```
\d+
$*_
O`
^
¶
(^¶_|\1_)+$

```

Try it online! Takes input on separate lines but link is to test suite that splits on commas for convenience. 1-indexed. Explanation:

```
\d+
$*_

```

Convert to unary, but using a non-digit character.

```
O`

```

Sort.

```
^
¶

```

Prefix a newline, so that each number is now preceded by a newline.

```
(^¶_|\1_)+$

```

If at the beginning of the buffer, match a newline followed by `1` (in unary), otherwise match one more than the previous match (still with preceding newlines). If the input was a permutation then the buffer will contain an ascending sequence and the match will reach the end of the buffer.

# Answer
> 1 votes
# Desmos, ~~54~~ 39 bytes

```
f(l)=0^{(l.sort-[1...l.total])^2.total}

```

Test on function `f`. Returns `1` if truthy, `0` if falsey.

~~To be honest, I thought that the solution would be shorter than this :|. Could most likely be golfed though, with a different strategy than mines.~~

Ok well I got much better at golfing in Desmos since 2021 and all I can say is that there are some pretty glaring byte saves in my previous version.

Try It On Desmos!

Try It On Desmos! - Prettified

# Answer
> 1 votes
# APL(Dyalog Unicode), ~~11~~7 bytes SBCS

```
∧/⍳∘⍴∊⊢

```

Try it on APLgolf!

* thanks to @ovs for saving 4bytes by using a train!

Old explanation

```
∧/     all
(⍳⍴⍵)  [1..length]
∊⍵     belongs to input?

```

# Answer
> 1 votes
# Wolfram Language (Mathematica), 16 bytes

```
PermutationListQ

```

Try it online!

# Answer
> 1 votes
# Pari/GP, 31 bytes

```
f(v)=vecsort(v)==vector(#v,i,i)

```

Try it online!

# Answer
> 1 votes
# GolfScript, 6 bytes

```
~.,,-!
~      # parse the input string as an array
 .,,   # create an array [0 1 2...] of the same length as the input
    -  # get the set difference of this array and the original
     ! # convert the empty/non-empty array into a 1 or 0

```

Try It Online!

# Answer
> 1 votes
# C (gcc), 64 bytes

```
f(a,n,i)int*a;{for(i=n;i--&&a[i]-n;);n=~i?f(a,n,a[i]=a[--n]):n;}

```

Try it online!

# Answer
> 1 votes
# BQN, 4 bytesSBCS

```
∧≡⊒˜

```

Run online!

Uses this tip.

# Answer
> 1 votes
# GAP, 24 bytes

```
p:=l->PermList(l)<>fail;

```

Try it online!

This is a little trick since `PermList` fails if `l` is not a permutation of `1...length(l)`. However, due to technical reasons this is actually a boolean value. From the GAP documentation:

> fail is simply an object that is different from every other object than itself.
>
> For technical reasons, fail is a boolean value. But note that fail cannot be used to form boolean expressions with and, or, and not

The operator `<>` tests for inequality.

# Answer
> 1 votes
# TI-Basic, 17 bytes

```
Prompt A
SortA(ʟA
min(ʟA=cumSum(1 or ʟA

```

# Answer
> 1 votes
# Thunno `-`, \\$ 8 \log\_{256}(96)\approx \\$ 6.58 bytes

```
Iz:DLRA=

```

Attempt This Online!

Input as each number on its own line.

#### Explanation

```
Iz:DLRA= # Implicit input. - flag subtracts one.
Iz:      # All inputs, sorted
   DLR   # Duplicate and push the length range
      A= # Are equal?
         # Implicit output

```

# Answer
> 1 votes
# vemf, 8 bytes

```
{α~↨≡│α≤

```

## Explained

```
{α~↨≡│α≤
{        # Monadic function that checks if
      α≤ # the sorted input
    ≡    # equals
 α~↨     # range(1, len(input) + 1)

```

# Answer
> 1 votes
# Stax, 4 bytes

```
àæ↓Δ

```

Run and debug it

This is Packed Stax which unpacks to the following 5 bytes:

```
%Rx-!

```

Run and debug it

```
 R    # range 1..
%     # input length
  x-  # setwise difference with register x (which is set to the input by default)
    ! # logical NOT

```

# Answer
> 1 votes
# PARI/GP, 66 bytes

Try it online!

```
f(a)={for(i=1,#a,if(setsearch(Set(a),i)==0,return(0)));return(1);}

```

# Answer
> 1 votes
# Vyxal, 12 bytes

```
?£(|)1¥G›r¥⁼

```

Try it Online!

# Answer
> 1 votes
# APL(Dyalog Unicode), 5 bytes SBCS

```
^/⍋∊⊢

```

Try it on APLgolf!

A tacit function that returns if every number from `1..n` is in the array.

## Explanation

```
^/⍋∊⊢
^/    all
  ⍋   (a permutation of) numbers from 1..n
   ∊  are members of
    ⊢ the array

```

# Answer
> 1 votes
# Lua, 64 bytes

```
load't=...table.sort(t)for i=1,#t do b=b or i~=t[i]end return b'

```

Try it online!

Truthy and falsy values are swapped.

# Answer
> 1 votes
## Pascal, 134 Bytes

This `function` requires a processor supporting Extended Pascal as defined by ISO standard 10206 (level 1).

```
type Z=integer;function f(A:array[p..q:Z]of Z):Boolean;var S:set of Z;i:Z;begin S:=[];for i:=p to q do S:=S+[A[i]];f:=S=[1..q-p+1]end;

```

Ungolfed:

```
function f(A: array[minimum..maximum: integer] of integer): Boolean;
var
    members: set of integer value [];
    i: integer;
begin
    { transform an ordered `array` into an unordered `set` }
    for i := minimum to maximum do
    begin
        { form the union of two sets }
        members := members + [A[i]]
    end;
    { analyze: compare `members` to a set of `[1..n]` }
    f := members = [1..(maximum - minimum + 1)]
end;

```

Evidently, the implementation is index-insensitive.

# Answer
> 1 votes
# Kamilalisp, 28 bytes

```
[≡ $(+ 1)∘⍳∘⍴ ⊼]

```

Determines whether the sorted vector is equal to the range \[1, length(input)\].

Attempt This Online!

# Kamilalisp, 24 bytes

```
[≡ #0 ⍋@⍋]@$(^- 1)

```

A port of the APL answer.

Attempt This Online!

# Answer
> 1 votes
# C (clang), 47 bytes

*Input is a null-terminated array of positive integers*

```
i;f(*a){return!a[i++]?i=0,1:!wcschr(a,i)<f(a);}

```

Try it online!

---

# C (gcc) `-m32`, 35 bytes

*Requires that you also pass the length*

```
f(a,n){n=!n||wcschr(a,n)*f(a,n-1);}

```

Try it online!

# Answer
> 1 votes
# Scala 3, ~~36~~ 30 bytes

```
l=>l.toSet==(1to l.size).toSet

```

Attempt This Online!

# Answer
> 0 votes
# RAD, 5 bytes

```
<≡⍳∘⍴

```

Try it online!

```
 ≡       - Check equality between ...
<        - ... the input vector ...
  ⍳∘     - ... and 1 through ...
   ⍴     - ... the length of the input vector.

```

# Answer
> 0 votes
# Arturo, 22 bytes

```
$[a][=sort a 1..max a]

```

Try it

Checks whether the input sorted is equal to \\$\[1..\mathrm{max}(input)\]\\$.

---
Tags: code-golf, array, decision-problem, integer, permutations
---


title: Find the Maximal Prime Powers

text:
# Question
Title: Find the Maximal Prime Powers
A prime power is a positive integer *n* that can be written in the form *n* = *pk* where *p* is a prime and *k* is a positive integer. For example, some prime powers are `[2, 3, 5, 4, 9, 25, 8, 27, 125]`.

Next, consider prime powers of 2. These are `[2, 4, 8, 16, ...]` and can be written in the form 2*k*. They would all be included when considering prime powers beneath 20. However, 16 is the *maximal* prime power with a base prime of 2 in that range. A prime power *pk* is *maximal* in a range if it is the highest power of *p* in that range. We are only interested in the *maximal* prime power in each range so all lower prime powers must be excluded.

Your goal is to write a function or program that takes a positive integer *n* and outputs the *maximal* prime powers in the range `[2, 3, 4, ..., n]`.

Thanks to @Peter Taylor for clarifying the definition of *maximal* prime power and more.

## Rules

* This is so make your code as short as possible.
* The *maximal* prime powers may be output in any order but there must be no duplicates.

## Test cases

```
n      result
1      []
2      [2]
3      [2, 3]
4      [3, 4]
5      [3, 4, 5]
6      [3, 4, 5]
7      [3, 4, 5, 7]
20     [5, 7, 9, 11, 13, 16, 17, 19]
50     [11, 13, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49]
100    [11, 13, 17, 19, 23, 25, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, 89, 97]
10000  <1229 results>
       [101, 103, 107, 109, 113, 127, 131, 137, 139, 149, ..., 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973]

```

The full list of maximal prime powers for 10000 can be found here.

# Answer
> 17 votes
# Jelly, ~~7~~ 4 bytes

```
æḟÆR

```

Try it online!

### How it works

```
æḟÆR  Main link. Argument: n

  ÆR  Prime range; yield all primes in [1, ..., n].
æḟ    Power floor; round n down to the nearest power of each prime in the range.

```

# Answer
> 10 votes
## Mathematica, 44 43 40 bytes

*Saved 4 bytes thanks to miles and Martin Ender*

`n#^⌊#~Log~n⌋&/@Select[Range@n,PrimeQ]`

```
(x=Prime@Range@PrimePi@#)^⌊x~Log~#⌋&

```

and  are the `3` byte characters `U+230A` and `U+230B` representing `\[LeftFloor]` and `\[RightFloor]`, respectively.

## Explanation:

Pure function. `#` is short for `Slot[1]` which represents the first argument to the `Function`. `PrimePi@#` counts the number of primes less or equal to `#`, `Range@PrimePi@#` is the list of the first `PrimePi[#]` positive integers, and so `Prime@Range@PrimePi@#` is the list of primes less than or equal to `#` (this is one byte shorter than `Select[Range@#,PrimeQ]`). The symbol `x` is `Set` equal to this list, then raised to the `Power` `⌊x~Log~#⌋`, which is the list of `Floor[Log[n,#]]` for each `n` in `x`. In Mathematica, raising a list to the `Power` of another list of the same length results in the list of the powers of their corresponding elements.

# Answer
> 7 votes
# MATL, 13 bytes

```
ZqG:!^tG>~*X>

```

**Try it Online!**

**Explanation**

```
        % Implicitly grab the input as a number (N)
Zq      % Get an array of all primes below N
G:!     % Create an array from [1...N]
^       % Raise each prime to each power in this array which creates a 2D matrix
        % where the powers of each prime are down the columns
tG>~    % Create a logical matrix that is TRUE where the values are less than N
*       % Perform element-wise multiplication to force values > N to zero
X>      % Compute the maximum value of each column
        % Implicitly display the resulting array

```

# Answer
> 7 votes
# Jelly, ~~12~~ 9 bytes

```
RÆEz0iṀ$€

```

**Try it online!** (method is too slow for the 10000 case).

### How?

Builds the list of **pk** in order of **p**.

```
RÆEz0iṀ$€ - Main link: n                      e.g. 7
R         - range(n)                          [1 ,2  ,3    ,4  ,5      ,6    ,7]
 ÆE       - prime factor vector (vectorises)  [[],[1],[0,1],[2],[0,0,1],[1,1],[0,0,0,1]]
   z0     - transpose with filler 0           [[0,1,0,2,0,1,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]]
       $€ - la$t two links as a monad, for €ach       ^             ^                   ^                   ^
     i    -     first index of                        4             3                   5                   7
      Ṁ   -     maximum                       [4,3,5,7]

```

# Answer
> 7 votes
# Jelly, 8 bytes

```
ÆR*ÆE€»/

```

Try it online!

### How it works

```
ÆR*ÆE€»/  Main link. Argument: n

ÆR        Prime range; yield all primes in [1, ..., n].
   ÆE€    Prime exponents each; yield the exponents of 2, 3, 5, ... of the prime
          factorization of each k in [1, ..., n].
          For example, 28 = 2² × 3⁰ × 5⁰ × 7¹ yields [2, 0, 0, 1].
  *       Exponentiation; raise the elements of the prime range to the powers
          of each of the exponents arrays.
      »/  Reduce the columns by maximum.

```

# Answer
> 5 votes
## Pyth, 13 bytes

```
m^ds.lQdfP_TS

```

Try it here!

```
        f   S -  filter(v, range(1, input))
         P_T  -   is_prime(T)
m             - map(v, ^)
    .lQd      -    log(input, d)
   s          -   int(^)
 ^d           -  d ** ^

```

I haven't played with Pyth in a while so any golfing tips are appreciated.

# Answer
> 5 votes
I couldn't get a shorter Mathematica solution than ngenisis's solution, but I thought I'd offer a couple of (hopefully interesting) alternative approaches.

## Mathematica, 65 bytes

```
#/#2&@@@({#,#}&/@Range@#~Select~PrimeQ//.{a_,b_}/;a<=#:>{b a,b})&

```

First we use `{#,#}&/@Range@#~Select~PrimeQ` to build a list of all primes in the appropriate range, but with ordered pairs of each prime, like `{ {2,2}, {3,3}, ...}`. Then we operate on that list repeatedly with the replacement rule `{a_,b_}/;a<=#:>{b a,b}`, which multiplies the first element of the ordered pair by the second until the first element exceeds the input. Then we apply `#/#2&@@@` to output, for each ordered pair, the first element divided by the second. (They end up sorted by the underlying prime: an example output is `{16, 9, 5, 7, 11, 13, 17, 19}`.)

## Mathematica, 44 bytes

```
Values@Rest@<|MangoldtLambda@#->#&~Array~#|>&

```

The von Mangoldt function `Λ(n)` is an interesting number theory function: it equals 0 unless `n` is a prime power pk, in which case it equals `log p` (not `log n`). (These are natural logs, but it won't matter.) Thus `MangoldtLambda@#->#&~Array~#` creates an array of rules `{ 0->1, Log[2]->2, Log[3]->3, Log[2]->4, Log[5]->5, 0->6, ... }` whose length is the input integer.

We then turn this list of rules into an "association" using `<|...|>`. This has the effect of retaining only the last rule with any given left-hand value. In other words, it will throw away `Log[2]->2` and `Log[2]->4` and `Log[2]->8` and keep only `Log[2]->16` (assuming that the input is between 16 and 31 for this example). Therefore the only remaining right-hand sides are the maximal prime powers—except for the one remaining rule `0->n`, where `n` is the largest non-prime-power up to the input integer. But `Rest` throws that undesired rule away, and `Values` extracts the right-hand sides from the rules in the association. (They end up sorted as above.)

A slightly longer (46 bytes) version, which counts the number of appearances of each `log p` and then exponentiates to convert to the maximal prime powers:

```
E^(1##)&@@@Rest@Tally[MangoldtLambda~Array~#]&

```

# Answer
> 4 votes
# CJam, ~~21~~ 20 bytes

*Saved 1 byte thanks to Martin Ender*

```
ri_){mp},f{\1$mLi#}p

```

Try it online!

**Explanation**

```
ri                    e# Read an integer from input (let's call it n)
  _                   e# Duplicate it
   ){mp},             e# Push the array of all prime numbers up to and including n
         f{           e# Map the following block to each prime p:
           \          e#   Swap the top two elements of the stack
            1$        e#   Copy the second element down in the stack. Stack is now [p n p]
              mL      e#   Take the base-p logatithm of n
                i     e#   Cast to int (floor)
                 #    e#   Raise p to that power
                  }   e# (end of map block)
                   p  e# Print

```

# Answer
> 4 votes
# 05AB1E, ~~15~~ 12 bytes

```
ƒNpiN¹N.nïm,

```

Try it online!

**Explanation**

```
ƒ             # for N in [0 ... input]
 Npi          # if N is prime
    N         # push N
     ¹N.n     # push log_N(input)
         ï    # convert to int
          m   # raise N to this power
           ,  # print

```

# Answer
> 4 votes
# Brachylog, 24 21 19 bytes

*3+2 bytes saved thanks to Fatalize!*

This is my first time using Brachylog, and I know some things could have been done in shorter ways, but I'm happy that it even works :D

```
{≥.~^ℕ₁ᵐhṗ:.≜×>?∧}ᶠ

```

Try it online! (Return values are ordered by their base primes)

### Explanation:

```
{................}ᶠ           #Find all possible results of what's inside.
 ≥.                           #Input is >= than the output.
  .~^ℕ₁ᵐ                      #Output can be calculated as A^B, where A and B are
                              #Natural numbers >=1.
        hṗ                    #The first of those numbers (A) is prime
          :.≜×>?              #That same element (A), multiplied by the output
                              #is greater than the input - This means
                              #that B is the maximal exponent for A.
                ∧             #No more restrictions on the output.

```

# Answer
> 4 votes
# Brachylog, 15 bytes

```
⟧{ḋ=}ˢ⊇Xhᵐ≠∧X×ᵐ

```

Try it online!

This outputs the powers from biggest to smallest.

This is very inefficient.

### Explanation

```
⟧                   The Range [Input, Input - 1, ..., 1, 0]
 {  }ˢ              Select:
  ḋ=                  The elements of that range whose prime decompositions are lists of the
                      same element (e.g. [3,3,3]); output is those prime decompositions
      ⊇X            X is an ordered subset of that list of prime decompositions
       Xhᵐ≠         All first elements of the prime decompositions are different (that is,
                      X contains prime decompositions with different primes each times)
           ∧
            X×ᵐ     Output is the result of mapping multiplication to each element of X

```

This will find the biggest prime decompositions for each prime first because of the way  works: from left to right and from biggest to smallest subsets.

# Answer
> 3 votes
# Jelly, 9 bytes

```
Ræl/ÆF*/€

```

One byte longer than my other answer, but finishes for input **10,000** is a couple of seconds.

Try it online!

### How it works

```
Ræl/ÆF*/€  Main link. Argument: n

R          Range; yield [1, ..., n].
 æl/       Reduce by least common multiple.
    ÆF     Factor the LCM into [prime, exponent] pairs.
      */€  Reduce each pair by exponentiation.

```

# Answer
> 3 votes
# Bash \+ GNU utilities, 74 bytes

```
seq $1|factor|sed "s@.*: \(\w*\)\$@\1;l($1);l(\1);print \"/^p\"@"|bc -l|dc

```

Try it online!

The input number is passed as an argument. The output is printed to stdout. (As is customary, stderr is ignored.)

Sample output:

```
./maximalprimepowers 100 2>/dev/null
64
81
25
49
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97

./maximalprimepowers 10000 2>/dev/null | wc -l
1229

```

Here's how it works:

Call the argument N.

`seq` generates all the numbers from 1 to N, and `factor` factors them all.

The regex in the call to sed identifies those lines where the number is a prime P, and replaces those lines with lines that are of the form \`

```
P;l(N);l(P);print "/^p"

```

(where P and N are replaced by their actual numerical values, and everything else is copied literally, even the quotes and semicolons, and the string `print`).

These lines are fed as input to `bc -l`; bc prints the values of the three indicated numbers, each followed by a newline, and then prints the characters `/^p` . (In bc, l(x) denotes the natural logarithm of x.) JK K

The strings that bc prints are then fed as input to dc; dc prints the value of each P^(log(N)/log(P)) using integer arithmetic (truncating); that's the greatest power of P that is \<= N.

One thing that's glossed over above is what happens to lines that are produced by factors that don't correspond to primes. Those lines don't match the regex in the call to sed, so no replacement is done on those. As a result, those lines start with a number followed by a colon, which generates an error when fed as input to `bc`. But bc just prints to stderr then, which we ignore; it doesn't print anything to stdout. By default, stderr is ignored on PPCG.

# Answer
> 3 votes
# Haskell, ~~73 67~~ 66 bytes

```
p n=[last[x^i|i<-[1..n],x^i<=n]|x<-[2..n],all((>0).mod x)[2..x-1]]

```

Try it online! Usage:

```
Prelude> p 50
[32,27,25,49,11,13,17,19,23,29,31,37,41,43,47]

```

**Edit:** 6 bytes off thanks to Zgarb!

**Explanation:**

```
p n=[... x|x<-[2..n]                         ] -- list of all x in the range 2 to n
p n=[... x|x<-[2..n],        mod x<$>[2..x-1]] -- where the remainders of x mod the numbers 2 to x-1
p n=[... x|x<-[2..n],all(>0)$mod x<$>[2..x-1]] -- are all greater 0. This yields all primes in the range.

p n=[    [x^i|i<-[1..n]       ]|...] -- for each of those x generate the list of all x^i with i in the range 1 to n
p n=[last[x^i|i<-[1..n],x^i<=n]|...] -- where x^i is smaller or equal to n
p n=[last[x^i|i<-[1..n],x^i<=n]|...] -- and take the last (that is the largest) element

```

# Answer
> 3 votes
# Regex (ECMAScript 2018 / Python`regex` / .NET), 97 bytes

```
(?=(?=(xx+?)\1*$)(((?=(x+)(\4+$))\5)*\1$))(?<!(?=(?=(xx+?)(\6*$))(?=\7\1$)(?=(x+)\8+$)\8\9$)(x+))

```

Try it online! \- ECMAScript 2018
Try it online! \- Python (with `regex`)
Try it online! \- .NET

Like Pseudofactorial, this uses Neil's prime powers test instead of mine, because when capturing the smallest prime factor is also needed, it results in a shorter total length.

```
                              # tail = N ≤ M = input number
# Assert tail is a prime power ≥ 2
(?=                           # Atomic lookahead
    (?=(xx+?)\1*$)            # \1 = smallest prime factor of tail,
                              #      asserting that tail ≥ 2
    (                         # \2 = tail = N
        (
            (?=(x+)(\4+$))\5  # tail = {largest proper divisor of tail}
                              #      = tail / {smallest prime factor of tail}
        )*                    # Iterate the above as many times necessary
                              # (minimum zero) to make the following match:
        \1$                   # Assert that tail == \1; if N is a prime power,
                              # the end result of the above loop will always
                              # be this. Otherwise it will be a larger prime,
                              # and this will fail to match.
    )
)
# Assert there is no prime power (of the same base prime \1)
# that is greater than N but less than or equal to M.
(?<!              # Negative Lookbehind - evaluated right-to-left, so read it
                  # from bottom to top, but once entering the lookahead, go
                  # back to left-to-right (top to bottom); assert that the
                  # following cannot match:
    (?=                       # Lookahead
        (?=(xx+?)(\6*$))      # \6 = smallest prime factor of tail; \7 = tail-\6
        (?=                   # Lookahead
            \7                # tail = tail - (tail - \6) = \6
            \1$               # Assert tail == \1
        )
        (?=(x+)\8+$)          # \8 = {largest proper divisor of tail}
                              #    = tail / {smallest prime factor of tail}
        \8\9$                 # Assert tail == \8 + \9, meaning \8 == N
    )
    (x+)          # tail += \9 = any positive value, in which all possibilities
                  # are tried, until a match is found, or all have been tried
                  # and no matches were found) as long as the resulting tail ≤ M
)

```

# Answer
> 2 votes
## JavaScript (ES6), ~~118~~ ~~120~~ ~~119~~ ~~114~~ ~~112~~ 105 bytes

```
(n,r)=>(r=k=>[...Array(k-1)].map((_,i)=>i+2),r(n).filter(q=>r(q).every(d=>q%d|!(d%(q/d)*(q/d)%d)&q*d>n)))

```

Suggestions welcome. This is kind of long, but it seemed worth posting because it does all the divisibility testing explicitly rather than using built-ins related to primes.

Notes:

* A natural number q is a prime power \<=\> all of q's divisors are powers of the same prime \<=\> for any d which divides q, one of d and q/d is a divisor of the other.
* If q is a power of p, q is maximal \<=\> q * p \> n \<=\> q * d \> n for every nontrivial divisor d of q.

# Answer
> 2 votes
# Sage, 43 bytes

```
lambda i:[x^int(ln(i,x))for x in primes(i)]

```

Maps each prime in the range `primes(i)` to its maximal prime power. `ln` is just an alias of `log` so it accepts alternate bases although its name suggests it can only use base `e`.

# Answer
> 2 votes
# Haskell, ~~110~~ 90 bytes

```
s[]=[];s(x:t)=x:s[y|y<-t,y`rem`x>0];f n=[last.fst.span(<=n).scanl1(*)$repeat x|x<-s[2..n]]

```

--updated per Laikoni's feedback

# Answer
> 2 votes
## Haskell, 70 bytes

```
f n=[k|k<-[2..n],p:q<-[[d|d<-[2..k],mod k d<1]],k==p*p^length q,p*k>n]

```

Defines a function `f`. Try it online!

## Explanation

The idea is to filter the range `[2..n]` for those numbers `k` that satisfy `k == p^length(divisors k)` and `p*k > n`, where `p` is the smallest prime divisor of `k`.

```
f n=                -- Define f n as
 [k|                -- the list of numbers k, where
  k<-[2..n],        -- k is drawn from [2..n],
  p:q<-[            -- the list p:q is drawn from
   [d|              -- those lists of numbers d where
    d<-[2..k],      -- d is drawn from [2..k] and
    mod k d<1]      -- d divides k
   ],               -- (so p:q are the divisors of k except 1, and p is the smallest one),
  k==p*p^length q,  -- k equals p to the power of the divisor list's length
                    -- (so it's in particular a prime power), and
  p*k>n]            -- p*k, the next power of p, is not in the range [2..n].

```

# Answer
> 2 votes
# Vyxal, 6 bytes

```
~æ~•⌊e

```

Try it Online!

```
~      # Filter (implicit) range from 1 to n by
 æ     # Is prime?
  ~    # Without popping
   •   # Take the log of the input with base each of the primes
    ⌊  # Floor
     e # Raise the primes to those powers

```

# Answer
> 1 votes
# PHP, ~~101~~ ~~93~~ ~~91~~ 88 bytes

just a little bit of real maths ...

```
for($n=$argv[$i=1];$n>$j=$i++;$j?:$r[$p=$i**~~log($n,$i)]=$p)for(;$i%$j--;);print_r($r);

```

**breakdown**

```
for($n=$argv[$i=1];     // loop $i from 2 to $n
    $n>$j=$i++;             // 0.: init $j to $i-1
    $j?:                    // 2. if $i is prime
        $r[$p=$i**~~log($n,$i)]=$p) // 3. add maximum power to results
    for(;$i%$j--;);         // 1. prime check (if $i is prime, $j will be 0)
print_r($r);            // print results

```

# Answer
> 1 votes
# JavaScript ES7, 93 bytes

Recursively iterate `i` from 0 up to and including `n`. If `i` is prime raise it to the highest floored exponent that makes it `<= n` (`i ^ floor(log(n) / log(i))`)

```
F=(n,i=n)=>i?[...((P=j=>i%--j?P(j):1==j)(i)?[i**((l=Math.log)(n)/l(i)|0)]:[]),...F(n,--i)]:[]

```

# Answer
> 0 votes
# J-uby `-rprime`, 34 bytes

Port of Dennis' 9-byte Jelly solution; give him an upvote.

```
:+|:/&:lcm|:prime_division|:*&+:**

```

Attempt This Online!

## Explanation

```
:+ | :/ & :lcm | :prime_division | :* & +:**
:+ |                                          # Range 1..n, then
     :/ & :lcm |                              # reduce by LCM, then
                 :prime_division |            # get prime factors as [factor, exponent] pairs, then
                                   :* & +:**  # map each pair as exponentiation

```

Created with the help of Luminespire.

# Answer
> 0 votes
# 05AB1E, 8 bytes

```
LÓ0ζεZk>

```

Port of *@JonathanAllan*'s Jelly answer.

Try it online or verify (almost) all test cases.

Or alternatively (and faster):

```
ÅPIL.¿Óm

```

Port of *@Dennis*' (9-bytes) Jelly answer.

Try it online or verify all test cases.

**Explanation:**

```
L         # Push a list in the range [1, (implicit) input]
 Ó        # Map each value to a list of its prime exponents
   ζ      # Zip/transpose, swapping rows/columns,
  0       # using a 0 as filler-item for unequal length rows
    ε     # Map over each inner list:
     Z    #  Push the maximum (without popping the list)
      k   #  Get the (0-based) index of this maximum in the list
       >  #  Increase it by 1 to make it a 1-based index
          # (after which the resulting list is output implicitly)

ÅP        # Push a list of all primes smaller than or equal to the (implicit) input
  IL      # Push a list in the range [1,input]
    .¿    # Pop and get its Least Common Multiple (lcm)
      Ó   # Get the prime exponents of this lcm
       m  # Take each prime to each prime exponent at the same positions
          # (after which the resulting list is output implicitly)

```

# Answer
> 0 votes
# APL(NARS), 19 chars

```
{a*⌊⍵⍟⍨a←k/⍨0πk←⍳⍵}

```

It use the fact if p is a number \>1 r=floor(log\_p(InputNumber)) is the max number with p^r\<InputNumber. test:

```
  f←{a*⌊⍵⍟⍨a←k/⍨0πk←⍳⍵}
  ≢f 10000
1229
  f 20
16 9 5 7 11 13 17 19

```

---
Tags: code-golf, math, primes
---