title: Longest Common Prefix of 2 Strings

text:
# Question
Title: Longest Common Prefix of 2 Strings
Write a program that takes 2 strings as input, and returns the longest common prefix. This is , so the answer with the shortest amount of bytes wins.

```
Test Case 1:

"global" , "glossary"
"glo"

Test Case 2:

"department" , "depart"
"depart"

Test Case 3:

"glove", "dove"
""

```

# Answer
# Python 3, 54 bytes

Thanks Python for having a built-in function for this task! :D

```
import os;print(os.path.commonprefix(input().split()))

```

Takes input as two words separated by a space such as `glossary global`.
> 24 votes

# Answer
## Haskell, 29 bytes

```
(c:x)%(d:y)|c==d=c:x%y;_%_=""

```

Usage:

```
>> "global"%"glossary"
"glo"

```

Recursively defines the binary function `%` by pattern matching. On two strings with equal first letters, takes that first letters, and prepends it to the function of the remainder of the strings. On anything else, gives the empty string.
> 23 votes

# Answer
# Pyth, ~~8~~ 7 bytes

```
e@F._MQ

```

Thanks @isaacg for 1 byte off

Takes input quoted and comma separated, like `"abc", "acc"`. This exits on an error (but leaves stdout empty) when the result is the empty string. If that is unacceptable, add 2 bytes for `#e@F._MQq`

Test Suite

### Explanation

```
e@F._MQ        : implicit Q = eval(input)
   ._MQ        : Map the prefix operator onto both inputs
 @F            : Fold the setwise intersection operator over those lists
e              : Take the last such element, the prefixes are always made from shortest
               : to longest, so this always gives the longest matching prefix

```
> 12 votes

# Answer
## C++, ~~101~~ ~~100~~ 99 bytes

```
#include<iostream>
int i;main(){std::string s,t;std::cin>>s>>t;for(;s[i]==t[i];std::cout<<s[i++]);}

```

Reads two strings from `stdin`, prints the character at the current position from one of the strings while the character at the current position is equal to the character at the same position in the other string.

Thanks to Zereges for saving one byte.
> 10 votes

# Answer
# CJam, ~~12~~ ~~11~~ 9 bytes

```
l_q.-{}#<

```

This reads the strings on two separate lines with Unix-style line ending, i.e., `<string>\n<string>\n`.

*Thanks to @MartinBüttner for -1 byte, and to @jimmy23013 for -2 bytes!*

Try it online in the CJam interpreter.

### How it works

```
l_         e# Read a line (w/o trailing LF) from STDIN and push a copy.
  q        e# Read another line from STDIN (with trailing LF).
           e# The trailing linefeed makes sure that the lines are not equal.
   .-      e# Perform vectorized character subtraction. This yields 0 for equal
           e# characters, a non-zero value for two different characters, and the
           e# characters themselves (truthy) for the tail of the longer string.
     {}#   e# Find the index of the first truthy element.
        <  e# Keep that many characters from the first string.

```
> 9 votes

# Answer
## Haskell, 38 bytes

```
((map fst.fst.span(uncurry(==))).).zip

```

Usage example: `( ((map fst.fst.span(uncurry(==))).).zip ) "global" "glossary"` -\> `"glo"`.

Zip both input string into a list of pairs of characters. Make two lists out of it: the first one with all pairs from the beginning as long as both characters are equal, the second one with all the rests. Drop the second list and extract all characters from the first list.
> 9 votes

# Answer
# APL, 13

```
{⊃↓K/⍨=⌿K←↑⍵}

```

This is a function that takes an array of two strings, and returns the prefix:

```
      {⊃↓K/⍨=⌿K←↑⍵}'glossary' 'global'
glo
      {⊃↓K/⍨=⌿K←↑⍵}'department' 'depart'
depart

```
> 8 votes

# Answer
# AppleScript, 215 Bytes

And I tried so hard... ;(

```
set x to(display dialog""default answer"")'s text returned
set a to(display dialog""default answer"")'s text returned
set n to 1
set o to""
repeat while x's item n=a's item n
set o to o&x's item n
set n to n+1
end
o
```

I wanted to see how well AppleScript could pull this off, and *man* is it not built for string comparisons.
> 8 votes

# Answer
# sed, 18

I had something much longer and more complicated in mind, so credit for this idea goes to @kirbyfan64sos.

```
s/(.*).* \1.*/\1/

```

Includes +1 for the `-r` option to sed.
> 7 votes

# Answer
## C#, ~~201~~ 147 bytes

```
using System.Linq;class a{static void Main(string[]a){a[0].Take(a[1].Length).TakeWhile((t,i)=>a[1][i]==t).ToList().ForEach(System.Console.Write);}}

```

I know it isn't terribly competitive. I just wanted to see what it would look like.

EDIT: Thanks Ash Burlakzenko, Berend, and Dennis\_E
> 7 votes

# Answer
# CJam, 12 8 26

```
r:AAr:B.=0#_W={;;ABe<}{<}?

```

Try it Online.

(Got idea to use .= instead of .- after looking at Dennis's answer.)

With all the edge cases, it became to hard for a CJam beginner like me to keep it short. Hopefully, this at least works for all cases.
> 6 votes

# Answer
# rs, 14 bytes

```
(.*).* \1.*/\1

```

Live demo and test cases.

This is pretty simple. It just matches the...longest common prefix and removes the rest of the string. If there is no longest common prefix, it just clears everything.
> 6 votes

# Answer
## Common Lisp, 39

```
(lambda(a b)(subseq a 0(mismatch a b)))

```

Takes two string arguments, determines the index *i* where they differ, and returns a substring from 0 to *i*.
> 5 votes

# Answer
# Javascript ES6, 52 bytes

```
f=(a,b)=>[...a].filter((e,i)=>e==b[i]?1:b='').join``

```

Usage:

```
>> f("global","glossary")
"glo"

```
> 5 votes

# Answer
## Perl 5, ~~20~~ ~~19~~ 18 bytes

19 bytes, plus 1 for the `-E` flag instead of `-e`:

```
say<>=~/^(.*).* \1/

```

This is copied shamelessly from Digital Trauma's sed answer. It assumes the input is a couple of words without spaces in them (or before the first) and with one space between them.

---

Update:

ThisSuitIsBlackNot suggested using `-pe` as follows, to save a byte (thanks!):

```
($_)=/^(.*).* \1/

```

And then Luk Storms suggested using `-nE` as follows to save another byte (thanks!):

```
say/^(.*).* \1/

```

(I'm counting `-E` as one byte instead of the standard `-e`, but `-n` or `-p` as two. My impression is that that's SOP around here.)
> 5 votes

# Answer
# Python 3, 72

31 bytes saved thanks to FryAmTheEggman. 8 saved thanks to DSM.

```
r=''
for x,y in zip(input(),input()):
 if x==y:r+=x
 else:break
print(r)

```
> 4 votes

# Answer
## Python 3, 47

```
def f(w):[print(end=c[c!=d])for c,d in zip(*w)]

```

A function that takes a list `w` of two words, and prints the common prefix before terminating with an error.

Python 3's `print` function lets you prints strings flush against each other with `print(end=c)` (thanks to Sp3000 for saving 3 bytes with this shorter syntax). This repeatedly take two letters from the words, and prints the first of the letters. The indexing `c[c!=d]` gives an out-of-bounds error where `c!=d`, terminating the execution when two unequal letters are encountered.

An explicit for loop is one char longer than the list comprehension:

```
def f(w):
 for c,d in zip(*w):print(end=c[c!=d])

```
> 4 votes

# Answer
# MATL, ~~11~~ 9 bytes

```
y!=XdYpf)

```

Try it online!

*(-2 bytes thanks to Giuseppe)*

```
 y  % implicitly input the two strings, then duplicate the
    %  first one into the stack again
    %  stack: ['department' 'deported' 'department']
 !  % transpose the last string into a column vector
 =  % broadcast equality check - gives back a matrix comparing
    %  every letter in first input with the letters in the second
 Xd % diagonal of the matrix - comparison result of each letter with
    %  only corresponding letter in the other string
    %  stack: ['department' [1; 1; 1; 0; 1; 1; 0; 0;]]
 Yp % cumulative product (so only initial sequence of 1s remains
    %  1s, others become 0)
    %  stack: ['department' [1; 1; 1; 0; 0; 0; 0; 0;]]
 f  %  find the indices of the 1s
 )  % index at those elements so we get those letters out
    % (implicit) convert to string and display

```
> 3 votes

# Answer
# Retina, 14 bytes

Uses the same idea as kirbyfan64sos. Unfortunately, despite Martin's claim that eventually Match mode will feature a way to print capturing groups, it hasn't been implemented yet. Otherwise, `(.*).* \1` could be used along with 2 bytes or so for some not-yet-existing configuration string option.

```
(.*).* \1.*
$1

```

Each line would go in its own file, with 1 byte added per additional file. Alternatively, run in a single file with the `-s` flag.
> 2 votes

# Answer
# Japt, 27 bytes

**Japt** is a shortened version of **Ja**vaScri**pt**. Interpreter

```
Um$(X,Y)=>$A&&X==VgY ?X:A=P

```

(The strings go into the Input box like so: `"global" "glossary"`)

This code is exactly equivalent to the following JS:

```
A=10;(U,V)=>U.split``.map((X,Y)=>A&&X==V[Y]?X:A="").join``

```

I have not yet implemented anonymous functions, which is what the `$...$` is for: anything between the dollar signs is left untouched in the switch to JS. After I add functions, this 21-byte code will suffice:

```
UmXY{A&&X==VgY ?X:A=P

```

And after I implement a few more features, it will ideally be 18 bytes:

```
UmXY{AxX=VgY ?X:AP

```

Suggestions welcome!

---

So it turns out that this program is only 15 bytes in modern Japt:

```
¡A©X¥VgY ?X:A=P

```

Try it online!
> 2 votes

# Answer
# Julia, 62 bytes

```
f(a,b)=(c="";for(i,j)=zip(a,b) i!=j?break:(c*=string(i))end;c)

```

Ungolfed:

```
function f(a::AbstractString, b::AbstractString)
    # Initialize an output string
    c = ""

    # Iterate over the pairs of characters in a and b,
    # truncated to the shorter of the two lengths
    for (i, j) in zip(a, b)
        if i == j
            # If they match, append to the output string
            c *= string(i)
        else
            # Otherwise stop everything!
            break
        end
    end

    return c
end

```

Fixed an issue (at the hefty cost of 14 bytes) thanks to xnor!
> 2 votes

# Answer
# K, 24 bytes

```
{(+/&\=/(&/#:'x)#'x)#*x}

```

Find the minimum of the length of each string. (`(&/#:'x)`). Trim each string to that length (`#'x`). Then compare, smear and sum the resulting sequence:

```
  =/("globaa";"glossa")
1 1 1 0 0 1
  &\=/("globaa";"glossa")
1 1 1 0 0 0
  +/&\=/("globaa";"glossa")
3

```

Finally, take that many characters from the first of the strings provided (`#*x`).

In action:

```
 f: {(+/&\=/(&/#:'x)#'x)#*x};
 f'(("global";"glossary")
    ("department";"depart")
    ("glove";"dove")
    ("aaa";"aaaaa")
    ("identical";"identical")
    ("aca";"aba"))
("glo"
 "depart"
 ()
 "aaa"
 "identical"
 ,"a")

```
> 2 votes

# Answer
## Powershell, 65 bytes

Compare the strings, shrinking the first until it either matches (print and exit) or the string is null and the loop terminates.

```
param($a,$b)while($a){if($b-like"$a*"){$a;exit}$a=$a-replace".$"}

```
> 2 votes

# Answer
## MATLAB, ~~50~~ 40 bytes

Defines a function that accepts 2 strings as input, outputs to command window

```
function t(a,b);a(1:find([diff(char(a,b)) 1],1)-1)

```

This solution will work for any string, outputs

```
ans =

   Empty string: 1-by-0

```

if no match is given.

Can be golfed by using a script instead of a function (using local variables a, b) (-16 bytes).

so getting 34 Bytes

```
a(1:find([diff(char(a,b)) 1],1)-1)

```

The function style (which seems to be the accepted style), yields

```
@(a,b)a(1:find([diff(char(a,b)) 1],1)-1)

```

(Thanks @Stewie Griffin)
> 2 votes

# Answer
## C99, 73 bytes

```
main(int c,char *a[]){for(char *x=a[1],*y=a[2];*x==*y++;putchar(*x++));}

```

Similar to this answer, but shorter and meets spec (takes input from stdin).
> 2 votes

# Answer
# Perl 6, 28 bytes

I came up with two that take their values from STDIN which are based on the Perl 5 answer.

```
lines~~/(.*).*' '$0/;say ~$0

```

```
lines~~/:s(.*).* $0/;say ~$0

```

The first requires exactly one space between the inputs, while the other requires at least one whitespace character between the inputs.

---

That is quite a bit shorter than the first thing I tried which takes the values from the command line.

```
say [~] map ->($a,$b){$a eq$b&&$a||last},[Z] @*ARGS».comb # 58 bytes

```

or even the lambda version of it:

```
{[~] map ->($a,$b){$a eq$b&&$a||last},[Z] @_».comb} # 52 bytes

```

Though this is much easier to adjust so that it accepts any number of input strings, at the cost of only one stroke.

```
{[~] map ->@b {([eq] @b)&&@b[0]||last},[Z] @_».comb} # 53 bytes
#          ┗━┛ ┗━━━━━━━┛  ┗━━━┛

```

```
my &common-prefix = {[~] map ->@b {([eq] @b)&&@b[0]||last},[Z] @_».comb}

say common-prefix <department depart>; # "depart"
say common-prefix; # ""
say common-prefix <department depart depot deprecated dependant>; # "dep"

# This code does not work directly with a single argument, so you have
# to give it an itemized List or Array, containing a single element.

say common-prefix $('department',); # "department"

# another option would be to replace `@_` with `(@_,)`

```
> 2 votes

# Answer
# 05AB1E, 6 bytes

```
ø€ËγнÏ

```

Try it online or verify all test cases.

Or alternatively:

```
ηR.ΔÅ?

```

Might be invalid, since it outputs `-1` instead of an empty string if the strings have no common prefix.

Try it online or verify all test cases.

**Explanation:**

```
ø      # Zip the two (implicit) inputs together, creating pairs
       #  i.e. "abc1de98f" and "abc2de87f"
       #   → ["aa","bb","cc","12","dd","ee","98","87","ff"]
 €Ë    # Check for each if all inner items (the two characters in this case) are the same
       #  → [1,1,1,0,1,1,1,0,0,1]
   γ   # Split it into parts, grouping the same subsequent values together
       #  → [[1,1,1],[0],[1,1],[0,0],[1]]
    н  # Pop and only leave the first item
       #  → [1,1,1]
     Ï # Only leave the characters at the truthy indices in the (implicit second) input
       #  i.e. "abc2de87f" and [1,1,1] → "abc"
       # (after which the result is output implicitly)

η      # Get the prefixes of the first (implicit) input
       #  i.e. "abc1de98f"
       #   → ["a","ab","abc","abc1","abc1d","abc1de","abc1de9","abc1de98","abc1de98f"]
 R     # Reverse this list
       #  → ["abc1de98f","abc1de98","abc1de9","abc1de","abc1d","abc1","abc","ab","a"]
  .Δ   # Then find the first item in this list which is truthy for:
       # (which will result in -1 if none are found)
    Å? #  Check if the second (implicit) input starts with the current prefix
       #   i.e. "abc2de87f" and "abc1d" → 0 (falsey)
       #   i.e. "abc2de87f" and "abc" → 1 (truthy)
       # (after which the result is output implicitly)

```
> 2 votes

# Answer
# Husk, <sup>~~6~~</sup> 4 bytes

```
→¤nḣ

```

Try it online!

-2 bytes from Dominic Van essen.
> 2 votes

# Answer
## Clojure/ClojureScript, 51

```
(defn f[[a & b][c & d]](if(= a c)(str a(f b d))""))

```

Pretty straightforward. Unfortunately the spaces around the parameter destructuring are necessary (that's the `[a & b]` stuff). Not the shortest but I beat some other answers in languages that like to brag about their terseness so I'll post it.
> 1 votes

# Answer
# Python 2, 50 bytes

```
for a,b in zip(*input()):print(1/0if a!=b else a),

```

---

### Input

The input is taken as two strings:

```
"global", "glossary"

```

---

### Output

The output is each character followed by a space; which, hopefully, isn't a problem. However, if it is, I'll edit my answer.

```
g l o

```
> 1 votes

# Answer
# TeaScript, 16 bytes ~~20~~

```
xf»l¦y[i]?1:b=0)

```

Takes each input separated by a space.
> 1 votes

# Answer
# , 25 chars / 39 bytes

```
ô⟦ï0]Ă⇀$≔ï1[_]?1:ï1=0)ø⬯)

```

`Try it here (Firefox only).`

It barely looks like ES6.
> 1 votes

# Answer
# Scala, 90 bytes

```
object S extends App{print(args(0)zip args(1)takeWhile{case(a,b)=>a==b}map(_._1)mkString)}

```

It takes to Strings as arguments and outputs to stdout.
> 1 votes

# Answer
## ed, sed, 19 bytes

## ex, 18 bytes

## vim, 20 bytes

```
s/\(.*\).* \1.*/\1/

```

This also works with ex/vi (heirloom ex 050325), and the trailing slash is not required.

Oddly, this *should* work in vim, but mysteriously fails. It works if I add another unused capture group, something which should not change the semantics of the regex at all:

```
s/\v(.*)(.* \1.*)/\1

```

It fails and gives garbage answers in nvi and the results are downright mysterious:

```
:1
global glossary
:s/\(.*\)\(.*\) \1\(.*\)/\1{\2,\3}/
global{,ry}

```

NOTE: This expects the words on the current \[last in the file\] line \[or every line for the sed script\] separated by a space, and containing no space. To operate on every line in ex/vim, add % to the beginning. I don't think I'm the only program here to have constraints like these.
> 1 votes

# Answer
# PHP, 52 bytes

Not spectacular but does the job:

```
$a=$argv;while($a[1][$i]==$a[2][$i])echo$a[1][$i++];

```

Takes two command line arguments:

```
php prefix.php department depart

```
> 1 votes

# Answer
## MATLAB, 63 bytes

Defines a function that accepts 2 strings as input.

```
function f(a,b),c=1;try,while a(c)==b(c),c=c+1;end,end,a(1:c-1)

```

Had to include a try-statement for those cases where a would be **a** is a longer string than **b**.

* If we have the freedom to always supply the shorter string to **a**, then **8 bytes** can be removed.
* If it is allowed to define **a** and **b** in the workspace, then another **16 bytes** can be removed.
> 1 votes

# Answer
# Scala, 85 83 77 bytes

```
def f(a:String,b:String)=a zip b takeWhile(a=>a._1==a._2) map(_._1) mkString

```

for example,

```
f("global" , "glossary")

```

returns

```
glo

```
> 1 votes

# Answer
## C# 147 146

```
string l(string a,string b){var s="";for(int i=0;i<Math.Min(a.Length,b.Length);i++){if(a[i]==b[i])s+=a[i];else return a.Substring(0,i);}return s;}

```

Readable and ungolfed version

```
    string longestPrefix(string a, string b)
    {
        var s = "";
        for (int i = 0; i < Math.Min(a.Length, b.Length); i++)
        {
            if (a[i] == b[i]) s+=a[i];
            else return a.Substring(0, i);
        }

        return s;
    }

```

## How it works:

It loops until characters on the same index do not match. Every character that matches is added to **s** string, otherwise return a new string from zero index to current iteration.
> 1 votes

# Answer
# R, 130 bytes

```
substr(x[1],1,which.max(apply(do.call(rbind,lapply(strsplit(x,''),`length<-`,nchar(x[1]))),2,function(i)!length(unique(i))==1))-1)

```

Usage:

```
x <- c('bubblegum','bubbafish')

```
> 1 votes

# Answer
# brainfuck, 91 bytes

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

```

Requires an interpreter that either allows negative positions on the tape or wraps if you `<` from 0. Also requires `,` to return 0 every time you use it after input runs out. (In my experience these are both the most common behaviour.) Takes input as two words separated by a space.

This was a lot easier than I expected it to be! Usually I decide to write a brainfuck program and end up devoting quite a bit of time to it, but this one played nice. My first idea ended up working well and being rather short, especially for brainfuck.

This works by getting the entire first word and storing the characters in every second cell, then weaving in the second word (e.g. `gglloosbsaalr y`). Then, for each pair of characters `a` and `b`, it copies `a` a cell to the left and simultaneously replaces `b` with `b-a`. The cell `a` used to be in becomes `NOT (b-a)`. If that's true, `a` is printed and the loop continues to the next set of characters. Otherwise, nothing is printed and the loop terminates.

I only used two real golfing tricks in this program. The first was combining two unrelated loops while gathering input. The first word is initially stored with each of its bytes subtracted by 32, so that space becomes 0 and the loop can end. Rather than adding 32 to each of those bytes and then getting the second word, the program does both at the same time. The second trick I used was abuse of `,` when I know the input is empty. The idiomatic way of setting a cell to 0 is `[-]`. However, if you know that the program has already read the entire input, most interpreters will let you try to get a byte of input anyway and set the current cell to `NUL`, or 0. I use this twice in my program, saving 4 bytes.

**Ungolfed:**

```
+[>>,>++++[<-------->-]<]          get first word (minus 32 at each byte)

<<[<<]>                            go back to start

+[>>++++[>++++++++<-],]            get second word and add 32 to each byte of
                                   first word

<[<]>>-<                           go back to start and clean up a little bit

[                                  main loop

  >>[<+>>-<-]                        subtract letter from second word from
                                     letter of first word

  +>[<->,]<                          logical NOT the result

  [<.,]>                             if the result is 1: print the letter
                                     else: the loop dies and execution is
                                     terminated

]

```
> 1 votes

# Answer
# Javascript: 67 Bytes

```
(a,b)=>{for(i=0;i<a.length;i++){if(a[i]!=b[i])return a.slice(0,i)}}

```
> 1 votes

# Answer
# MUMPS, 54 bytes

```
t(a,b) f i=$L(a):-1:0 s p=$E(a,1,i) q:p=$E(b,1,i)
    q p

```

Typically primitive stuff - it just compares successively-shorter prefixes of the strings until it hits a match.
> 1 votes

# Answer
# \>\<\>, 37 bytes

```
i:0( ?\
4*=?\$>1+{:8
+[r]\$1
?!;o>:{=

```

Try it online!

Input is via STDIN, and is expected without quotes, separated by a space. For example, `global glossary`.

After the input is read, the characters up to and including the space are reversed and pushed back onto the stack. For example, if the input were `global glossary`, the stack would be `glossary labolg`. The stack is then rotated to the left one step at a time. If the top two chars are the same, output. Otherwise, end.
> 1 votes

# Answer
## Brainfuck, 61 bytes

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

```

Expects two words separated by a space.

Try it online.
> 1 votes

# Answer
# Java 8, 76 bytes

```
(a,b)->{String m="";for(int i=0;i<a.length&&a[i]==b[i];)m+=a[i++];return m;}

```

Lambda that takes 2 `char[]` arguments. Loops through until the letters stop matching or we match them all, appending them to a blank string as it goes.
> 1 votes

# Answer
# Jelly, 6 bytes

```
¹Ƥ€f/Ṫ

```

Try it online!
> 1 votes

# Answer
# Rust, 75 bytes

```
|a,b|a.chars().zip(b.chars()).take_while(|(a,b)|a==b).map(|v|v.0).collect()

```

Try it online!

Does unnecessary heap allocation for the result (idiomatic Rust code would return `&str` here as opposed to `String`), but it works so whatever. It's not like it matters.

This iterates over string characters as long as characters match and then collects matched characters into a `String`.
> 1 votes

# Answer
# K (oK) / K4, ~~21~~ 19 bytes

**Solution:**

```
(*x)@&&\=/(#,/x)$x:

```

Try it online!

**Explanation:**

Pad strings to combined length of the strings, check for equality, find matching indices, take minimum over resulting list, and index into first element of original input at these indices.

```
(*x)@&&\=/(#,/x)$x: / the solution
                 x: / save input as x
                $   / pad
          (    )    / do together
            ,/x     / flatten (,/) x
           #        / count (returns length)
        =/          / compare, equals (=) over (/)
      &\            / mins, min (&) scan (\)
     &              / indices where true
    @               / index into
(  )                / do this together
 *x                 / first (*) x

```
> 1 votes

# Answer
# Kotlin, 55 bytes

Not-Lame Edition! (no builtin)

```
{zip(it).takeWhile{(a,b)->a==b}.fold(""){a,(f,_)->a+f}}

{zip(it)                                                 // zip first string with second
        .takeWhile{(a,b)->a==b}                          // take pairs while chars are equal
                               .fold(""){a,(f,_)->a+f}}  // fold into string

```

Try it online!
> 1 votes

# Answer
# Japt `-h`, 6 bytes

```
®å+Ãrf

```

Try it
> 1 votes

# Answer
## x86-16 machine code, 6 bytes

```
00000000  56 A6 74 FD 4E C3                                 V.t.N.

```

Callable function.

Expects `[SI]` = address of first string, `[DI]` = address of second string.

Outputs as: `Top of stack` = start of memory slice, `SI` = end of memory slice (like the slice in Python).

Disassembly:

```
56            PUSH    SI    ; Store original SI onto stack
A6      LOOP: CMPSB         ; Compare [SI++] with [DI++]
74 FD         JZ      LOOP  ; If they're equal, jump to tag 'LOOP'
4E            DEC     SI    ; -- SI
C3            RET           ; Return to caller

```

## Example run

```
-d 0100
0B4A:0100  56 A6 74 FD 4E C3 00 00-00 00 00 00 00 00 00 00   V.t.N...........
0B4A:0110  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0120  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0130  67 6C 6F 62 61 6C 00 00-00 00 00 00 00 00 00 00   global..........
0B4A:0140  67 6C 6F 73 73 61 72 79-00 00 00 00 00 00 00 00   glossary........
0B4A:0150  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0160  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
0B4A:0170  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-r
AX=0000  BX=0000  CX=0000  DX=0000  SP=FFEA  BP=0000  SI=0130  DI=0140
DS=0B4A  ES=0B4A  SS=0B4A  CS=0B4A  IP=0100   NV UP EI PL NZ NA PO NC
0B4A:0100 56            PUSH    SI
-t

AX=0000  BX=0000  CX=0000  DX=0000  SP=FFE8  BP=0000  SI=0130  DI=0140
DS=0B4A  ES=0B4A  SS=0B4A  CS=0B4A  IP=0101   NV UP EI PL NZ NA PO NC
0B4A:0101 A6            CMPSB
...
-t

AX=0000  BX=0000  CX=0000  DX=0000  SP=FFE8  BP=0000  SI=0133  DI=0144
DS=0B4A  ES=0B4A  SS=0B4A  CS=0B4A  IP=0105   NV UP EI PL NZ NA PE CY
0B4A:0105 C3            RET
-d ss:ffe0
0B4A:FFE0  00 00 00 00 30 01 4A 0B-AE 05 30 01 30 01 00 00   ....0.J...0.0...
0B4A:FFF0  00 00 00 00 00 00 00 00-00 00 00 00 00 00 00 00   ................
-rsp
SP FFEA
:
-

```
> 1 votes

# Answer
# Nekomata, 5 bytes

```
ᵃp=al

```

Attempt This Online!

```
ᵃp=al
ᵃp      Non-deterministically choose a prefix of both inputs
  =     Check if the two prefixes are equal
   al   Find the last possible solution, which is the longest

```
> 1 votes

# Answer
# K, 45 bytes

```
{*|(*v)@{&y~'x}.#[&/#:'v;]'v:{#[;x]'1+!#x}'x}

```

Takes input as a 2-element list.
> 0 votes

# Answer
# Ruby, 44 characters

```
->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}

```

Sample run:

```
2.1.5 :001 > ->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}["global , "glossary"]
 => "glo"

2.1.5 :002 > ->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}["department", "depart"]
 => "depart"

2.1.5 :003 > ->a,b{i=0;i+=1while a[i]&&a[i]==b[i];a[0,i]}["glove", "dove"]
 => ""

```
> 0 votes

# Answer
**Swift, 34 bytes**

`import UIKit
"global".commonPrefixWith("glossary")`

But with Swift 2 it is actually more like: `"global".commonPrefixWithString("glossary",options:.CaseInsensitiveSearch)`
> 0 votes

# Answer
# C#, 112 bytes

```
class P{static void Main(string[]a){try{for(int i=0;a[0][i]==a[1][i];)System.Console.Write(a[0][i++]);}catch{}}}

```

Newlines and indentation for clarity:

```
class P{
    static void Main(string[]a){
        try{
            for(int i=0;a[0][i]==a[1][i];)
                System.Console.Write(a[0][i++]);
        }
        catch{}
    }
}

```
> 0 votes

# Answer
## Minkolang 0.10, 21 bytes

```
(od" "=,)x(0gdo=?.O1)

```

Expects input as two words, space-separated, like so: `department depart`. Try it here.

### Explanation

```
(od" "=,)      Loops through input until a space is encountered
x              Dumps extraneous space
(0gdo=   1)    Loops through second word and compares letters
      ?.O      Halts if two letters are not equal, outputs them otherwise

```
> 0 votes

# Answer
# pb, 105 bytes

```
^w[B!32]{>}>w[B!0]{t[B]vb[1]<[X]w[B!0]{>}b[T]w[B!1]{>}b[0]^>}v<[X]<t[0]w[T=0]{>t[B]^t[T-B]v}w[B!0]{b[0]>}

```

Takes two words separated by a single space. (I can save a byte by using a tab instead but that feels like cheating.)

In pb, the area that can be written to is thought of as a 2D space, with (0, 0) in the upper left. Additionally, input is initially kept at Y=-1. This program copies the second word of the input to Y=0 (starting at (0, 0)). Then, each letter is compared to the letter immediately above it until one is found that doesn't match. The rest of the word is erased and the desired output is already on the canvas so it's printed when execution halts.

**Ungolfed:**

```
^w[B!32]{>}>       # Go to the first letter of the second word
w[B!0]{            # For each letter in the second word:
    t[B]             # Save the letter to T
    vb[1]            # Put a flag below that letter so it can be found later
    <[X]w[B!0]{>}    # Go to the first empty space on Y=0
    b[T]             # Write the contents of T
    w[B!1]{>}b[0]    # Go back to the flag and erase it
    ^>               # Restart loop from next letter
}

v<[X]<             # Go to (-1, 0)
t[0]               # Set T to 0
w[T=0]{            # While T is 0:
    >t[B]            # Save the next letter of the second word to T
    ^t[T-B]v         # Subtract the equivalent letter of the first word from T

    # If they were the same, T is 0 and the loop continues.
}

w[B!0]{b[0]>}      # Erase the rest of the second word

```
> 0 votes

# Answer
# Dyalog APL, 12 bytes

```
{⊥⍨⌽=⌿↑⍵}↑∊

```

That's two bytes less than the previous APL solution!

The overall function is , which takes *n* elements (characters) from the flattened () argument, where *n* is the result of applying the function `{⊥⍨⌽=⌿↑⍵}` to the argument:

`↑⍵` convert list of strings to table (padding with spaces to form rectangle)
`=⌿` compare down (columns) giving boolean list
reverse
`⊥⍨` count trailing trues\*

---

\*Literally it is a mixed-base to base-10 conversion, using the boolean list as both number and base:

`⊥⍨0 1 0 1 1` is the same as `0 1 0 1 1⊥⍨0 1 0 1 1` which is `0×(0×1×0×1×1) 1×(1×0×1×1) 0×(0×1×1) 1×(1×1) + 1×(1)` which again is two (the number of trailing 1s).
> 0 votes

# Answer
# PHP, 49 bytes

```
<?=substr($t=$argv[1],0,strspn($t^$argv[2],"\0"));

```

Replace `\0` with the actual byte.
> 0 votes

# Answer
# Java 7, 145 bytes

```
class M{public static void main(String[]a){for(char i=0,c;i<a[0].length();){c=a[0].charAt(i);if(c!=a[1].charAt(i++))break;System.out.print(c);}}}

```

Those pesky program-requirements instead of function..

**Ungolfed:**

```
class M{
  public static void main(String[] a){
    for(char i = 0, c; i < a[0].length(); ){
      c = a[0].charAt(i);
      if(c != a[1].charAt(i++)){
        break;
      }
      System.out.print(c);
    }
  }
}

```

Try it here.
> 0 votes

# Answer
# 05AB1E, 10 bytes

```
.ps.p©å®Ï¤

```

Try it online!
> 0 votes

# Answer
# Powershell + Regex, 48 bytes

```
$m=$args-join"`n"-match"(^.*).*`n\1";$Matches[1]

```

one line input strings only.

# Powershell pure, ~~58~~ 56 bytes

```
param($a,$b)for($i=0;$a[$i]-eq$b[$i]){$c+=$a[$i++]};"$c"

```

Test script:

```
$f = {
param($a,$b)for($i=0;$a[$i]-eq$b[$i]){$c+=$a[$i++]};"$c"
}

"glo" -eq (&$f "global" "glossary")
"depart" -eq (&$f "department"  "depart")
"" -eq (&$f "glove" "dove")

```

Output:

```
True
True
True

```
> 0 votes

# Answer
# Regex, 12 bytes

```
(^.*).*$\n\1

```

each input string is separate line. https://regex101.com/r/bTf1ud/1
> 0 votes

# Answer
# C# (Visual C# Compiler), 62 bytes

```
(a,b)=>Concat(a.Zip(b,(x,y)=>x==y?x:'$').TakeWhile(x=>x!='$'))

```

Try it online!

`Zip`! This byte count includes only the lambda expression, and some necessary `using static` directives are not counted.

It is assumed that no word will contain the magical `char` value `$` (otherwise program may fail). Can use `\0` instead (but that is longer to type).
> 0 votes

# Answer
# C, 59 bytes

```
main(int c,char**a){while(*a[1]==*a[2]++)putchar(*a[1]++);}

```

Input from the command-line arguments.

Note - will overrun after printing the final null character if the input strings are identical.
> 0 votes

# Answer
# Zsh, 46 bytes

```
until [[ $1 = ${2%$~s}* ]] {s+=?;}
<<<${2%$~s}

```

Try it online!
> 0 votes

# Answer
# Vyxal, `a`, ~~5~~ 4 bytes

```
R÷ġṘ

```

Try it Online!

## Explained

```
R÷ġṘ
R÷   # vectorise reverse over the input (wrapped in an array by the -a flag) and push contents onto the stack
  ġ  # Push the greatest common suffix
   Ṙ # and reverse it to get the prefix

```
> 0 votes

# Answer
# V (vim), <sup>~~41~~</sup> 40 bytes

```
qqhYp$x@qq@qo<esc>j$@qo<esc>:%!awk 'a[$0]++'
jdG

```

Try it online!

No regex.

Takes the strings on two separate lines. The awk command is from here.

Once the matching prefixes are found, we delete everything except the first line.
> 0 votes

# Answer
# Thunno 2, 6 bytes

```
Z€ạġhị

```

Attempt This Online!

#### Explanation

```
Z€ạġhị  # Implicit input
Z       # Zip them together
 €      # To each inner pair:
  ạ     #  Check if they're equal
   ġ    # Group consecutive items
    h   # Get the first group
     ị  # Corresponding filter
        # Implicit output

```
> 0 votes

# Answer
# Java, 152 bytes

```
String a="aa",b="ab";char[]c=a.toCharArray(),d=b.toCharArray();int e=0,f=Math.min(c.length,d.length);for(;e<f&&c[e]==d[e];e++);return new String(c,0,e);

```
> -1 votes

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


title: Lossy Sorting (Implement Dropsort)

text:
# Question
Title: Lossy Sorting (Implement Dropsort)
Dropsort, designed by David Morgan-Mar, is an example of a linear-time "sorting algorithm" that produces a list that is, in fact, sorted, but contains only *some* of the original elements. Any element that is not at least as large as the maximum of the elements preceding it is simply removed from the list and discarded.

In this task, you will be given a list of integers as input (STDIN or function argument, you are required to support at least the range of 8-bit signed integers.) Your task is to dropsort them and then output the remaining elements in order.

You may assume that the list is non-empty.

This is code-golf, so the shortest program wins.

**Test Cases**

```
Input             Output
1 2 5 4 3 7       1 2 5 7
10 -1 12          10 12
-7 -8 -5 0 -1 1   -7 -5 0 1
9 8 7 6 5         9
10 13 17 21       10 13 17 21
10 10 10 9 10     10 10 10 10

```

**Leaderboard**

```
var QUESTION_ID=61808,OVERRIDE_USER=39022;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
# APL, 9 bytes

```
⊢(/⍨)⊢=⌈\

```

This is a monadic function train with diagram:

```
┌─┼───┐
⊢ ⍨ ┌─┼─┐
┌─┘ ⊢ = \
/     ┌─┘
      ⌈

```

The non-train version is

```
{⍵/⍨⍵=⌈\⍵}

```

This basically checks if each element is equal to the running maximum.

*Note that **Martin Büttner's J solution** is the same length as this and was posted first.*
> 43 votes

# Answer
# J, ~~10~~ 9 bytes

```
#~(=>./\)

```

Working version of my CJam idea (in fewer bytes). E.g.:

```
   f =: #~(=>./\)
   f 10 10 10 9 10
10 10 10 10
   f 1 2 5 4 3 7
1 2 5 7

```

## Explanation

First, we get the maximum of each prefix, with:

```
    >./\

```

(Here, `>.` is the maximum operator, `/` folds that operator onto a list, and `\` gets all the prefixes of the input.)

Then we compare the initial list with those maxima for equality:

```
  (=>./\)

```

And finally, we select all elements where this list of boolean results gave a `1`:

```
#~(=>./\)

```
> 22 votes

# Answer
## Haskell, 28

```
foldr(\x l->x:filter(x<)l)[]

```

An anonymous function. Call it like

```
foldr(\x l->x:filter(x<)l)[] [-7, -8, -5, 0, -1, 1]
[-7,-5,0,1]

```

Equivalent to the recursion

```
f[]=[]
f(x:l)=x:filter(x<)(f l)

```

Translated iteratively, we iterate over the elements, and for each one we see, we remove the ones smaller than it from the remainder of the list that we're iterating over. Thanks to Antisthenes for a byte saved with `(x<)`.
> 16 votes

# Answer
# Brachylog, 5 bytes

```
⊇ᶠ↔ᵒt

```

Try it online!

# Jelly, 5 bytes

```
ŒPUÞṪ

```

Try it online!

## Explanation

```
⊇ᶠ↔ᵒt    ŒPUÞṪ
⊇ᶠ       ŒP       On all subsequences of {the input}
   ᵒ        Þ     sort by
  ↔        U      their reverse
    t        Ṫ    then take the last element (i.e. the maximum as given by the sort)

```

This is a rare situation: I get to use an algorithm which (as far as I could tell with a quick skim) nobody is using so far, and it somehow ends up the same length in two very different golfing languages with very different syntax and builtin sets, with a 1-to-1 correspondence between the programs (the commands are even in the same order!). So it seemed to make more sense to combine them – in a way, these are the same program, and I wrote it in both languages to see which was shorter – than to submit them separately.

The basic idea here is that the dropsort of a list is its subsequence with the lexicographically maximum reverse. Oddly, neither Brachylog nor Jelly has a builtin to find the maximum by a particular function (Jelly has a builtin to return *all the maxima* by a particular function, but that'd return a singleton list containing the result rather than the result itself, and also isn't even shorter than doing it this way). So instead, we generate all possible subsequences, sort by reverse, take the last.

The reason why "lexicographically maximum reverse" works is that the chosen output must end (thus its reverse must start) with the highest number in the input list (it's easy to see that the dropsort output will always end with that), and thus can't contain anything after that (because taking subsequences preserves order). Repeat inductively and we end up with the definition of dropsort.
> 11 votes

# Answer
# Octave, ~~27~~ 19 bytes

```
@(a)a(cummax(a)==a)

```
> 10 votes

# Answer
# JavaScript (ES6), 29

Abusing of the standard type conversion in javascript, array to number:

* array of just 1 number =\> that number
* any other array =\> NaN

```
d=l=>l.filter(v=>l>v?0:[l=v])

// TEST
console.log=x=>O.innerHTML+=x+'\n'

;[
  [[1,2,5,4,3,7], [1,2,5,7]]
, [[10,-1,12], [10,12]]
, [[-7,-8,-5,0,-1,1], [-7,-5,0,1]]
, [[9,8,7,6,5], [9]]
, [[10,13,17,21], [10,13,17,21]]
, [[10,10,10,9,10], [10,10,10,10]]
].forEach(t=>( i=t[0],r=d(i),x=t[1],
  console.log('Test '+i+' -> '+r+(r+''==x+''?' OK':' Fail (expected '+x+')')))
)
```

```
<pre id=O></pre>
```
> 10 votes

# Answer
# Python 2, 49

```
f=lambda a:a and f(a[:-1])+a[-1:]*(a[-1]==max(a))

```
> 9 votes

# Answer
# Pyth, 12 bytes

```
eMfqeTeST._Q

```

Verify all test cases at once.

### How it works

```
         ._Q  Compute all prefixes of the input.
  f           Filter; for each T in the prefixes:
    eT          Retrieve the last element of T.
      eST       Sort T and retrieve its last element.
   q            Check for equality.
              Keep T if q returned True.
eM            Select the last element of each kept T.

```
> 8 votes

# Answer
# Mathematica, 26 Bytes

```
DeleteDuplicates[#,#>#2&]&

```
> 6 votes

# Answer
# R, ~~29~~ 26 bytes

```
function(x)x[x>=cummax(x)]

```

This creates a function object that accepts a vector `x` and returns `x` after removing all elements not at least as large as the cumulative maximum of `x`.

Saved 3 bytes thanks to flodel!
> 5 votes

# Answer
# K, 11 bytes

```
{x@&~x<|\x}

```

In action:

```
  f: {x@&~x<|\x}
  f'(1 2 5 4 3 7
     10 -1 12
     -7 -8 -5 0 -1 1
     9 8 7 6 5
     10 13 17 21
     10 10 10 9 10)

(1 2 5 7
 10 12
 -7 -5 0 1
 ,9
 10 13 17 21
 10 10 10 10)

```
> 4 votes

# Answer
# Python 3, 67

Pretty brute force. Changed it to a function, because I missed that it was a valid answer.

```
def f(i):
 s=[i[0]]
 for n in i[1:]:
  if s[-1]<=n:s+=[n]
 return s

```

Ungolfed version:

```
input_numbers = input().split()
sorted_numbers = []
previous_number = int(input_numbers[0])
for number in map(int, input_numbers):
    if previous_number <= number:
        sorted_numbers.append(number)
        previous_number = number
print(sorted_numbers)

```
> 3 votes

# Answer
# Java, 82 bytes

```
void f(int[]a){int m=a[0];for(int n:a){System.out.print(m>n?"":n+" ");m=n>m?n:m;}}

```

Here's a simple output loop. It just keeps the max in `m` and compares each element.
> 3 votes

# Answer
# \>\<\> with -v flag, ~~36~~ 31 + 2 = 33 bytes

```
:&\o " "&n:~& <
~ >l?!;:&:&(?!^

```

Input the list on the stack with -v so that the first element of the list is at the top of the stack. It will print the dropsorted list with a trailing space.

Test run :

```
$ for input in "1 2 5 4 3 7" "10 -1 12" "-7 -8 -5 0 -1 1" "9 8 7 6 5" "10 13 17 21" "10 10 10 9 10"; do echo $input '-> ' $(python fish.py dropsort.fsh -v $(echo $input | tac -s ' ')); done

1 2 5 4 3 7 ->  1 2 5 7

10 -1 12 ->  10 12

-7 -8 -5 0 -1 1 ->  -7 -5 0 1

9 8 7 6 5 ->  9

10 13 17 21 ->  10 13 17 21

10 10 10 9 10 ->  10 10 10 10

```

Edit : saved 5 bytes thanks to Fongoid
> 3 votes

# Answer
## Perl, 33 bytes

**32 bytes code + `-p`**

```
$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge

```

If additional spaces are acceptable in the output, can be 31 bytes by removing  and `?`. Accepts a string (or number of newline separated) strings via `STDIN`:

```
perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '-7 -8 -5 0 -1 1'
-7 -5 0 1

```

```
perl -pe'$p=$_;s/\S+ ?/$&>=$p&&($p=$&)/ge' <<< '10 10 10 9 10'
10 10 10 10

```
> 3 votes

# Answer
# Haskell, ~~38~~ 37 bytes

Saved 1 byte thanks to JArkinstall.

```
f(x:y:s)|x>y=f$x:s|1>0=x:f(y:s)
f s=s

```
> 3 votes

# Answer
# C# - ~~68~~64 or ~~132~~127 Characters

```
int[]f(int[]b){return b.Where((v,i)=>i<1||b[i-1]<=v).ToArray();}

```

`Where` in this case is iterating through the list, and for each element `v` at index `i` in the list, evaluates the boolean expression. If the expression evaluates to true, then the item is added to the result. The only real trick to the boolean expression is that C# short circuits or evaluation as soon as a condition evaluates to true. This prevents the `IndexOutOfRangeException` exception, and keeps the first element in the list.

If the input and output have to be strings (I couldn't tell for sure, so I'll leave it to the OP and the rest of you to decide.)

```
string t(string b){var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();return String.Join(" ",c.Where((v,i)=>i<1||c[i-1]<=v));}

```

Decompressing that a bit gives:

```
string t(string b)
{
    var c=b.Split(' ').Select(d=>int.Parse(d)).ToList();
    return String.Join(" ",c.Where((v, i)=>i<1||c[i-1]<=v));
}

```

In this case the second line of the function is using the exact same logic as above. The `Select` grabs the elements of the list and converts them to `int`. The call to `ToList`1 forces the select to be evaluated, and turns the `var` into a `List<int>` at compile time, so that the `Where` is operating on a collection of integers.

Try it on C# Pad

**Thanks to VisualMelon for helping trim 4 bytes and 5 bytes respectively. :)**

1 tutu list?
> 3 votes

# Answer
# CJam, 15 bytes

```
q~{_2$<{;}&}*]p

```

Try it online in the CJam interpreter.

### How it works

```
q~               Read an evaluate all input.
  {        }*    Reduce; push the first element; or each remaining element:
   _2$           Copy the topmost and second topmost element from the stack.
      <          Check if the topmost is smaller than the second topmost.
       {;}&      If it is, remove it from the stack.
             ]   Wrap the stack i an array.
              p  Print.

```
> 3 votes

# Answer
# PowerShell, 32 bytes

```
$args|?{$e-eq$p-or$_-ge$p;$p=$_}

```

Try it online!

Less golfed:

```
$args|?{
    $empty -eq $previous -or $_ -ge $previous
    $previous = $_
}

```
> 3 votes

# Answer
# Husk, 2 bytes

```
ü<

```

Try it online!

nub sieve using lesser than.
> 3 votes

# Answer
## Burlesque, 13 bytes

11 byte solution that passes test-cases:

```
-.2CO:so)[~

```

Try online here.

Explanation:

```
-. -- prepend head of list to list
2CO -- n-grams (sliding window) of size 2
:so -- filter sorted lists
)[~ -- map last

```

However, this version only works by using the fact, that no two smaller numbers are in between two numbers. Otherwise use the version below (which is 13B):

**Older versions:**

```
J-]{cm-1.>}LO

```

Try online here. Explanation:

```
J -- duplicate
-] -- head
{
  cm -- compare (returning -1,0 or 1)
  -1.> -- greater than -1
}LO -- Loop

```

If you'd drop equal numbers as well you could go with just `.>` instead of using `cm`. Also, if lists only contain positive numbers you can use either `0` or `-1` instead of `J-]`.
> 2 votes

# Answer
# C: 73 bytes

```
int i,j;i=j=INT_MIN;while(scanf("%d",&j)!=EOF)if(j>=i)printf("%d",j),i=j;

```

or

# C: 49 bytes

**(If customs header made for codegolf competitions is allowed)**

```
I z,y;z=y=INT_MIN;w(s(D,&y)!=E)i(y>z)p(D,y),z=y;}

```

Still can't beat CJam, but at least this allow to beat few other languages.
> 2 votes

# Answer
# Ruby, 32 characters

```
->a{m,=a;a.select{|n|m<=n&&m=n}}

```

Thanks to:

* Value Ink for reminding that in Ruby all numbers are truthy, so `&&` number assignment does not change the preceding boolean expression.

Try it online!

### Ruby, ~~41~~ 37 characters

```
->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}

```

(My old attempt.)

Sample run:

```
2.1.5 :001 > [
2.1.5 :002 >     [1, 2, 5, 4, 3, 7],
2.1.5 :003 >     [10, -1, 12],
2.1.5 :004 >     [-7, -8, -5, 0, -1, 1],
2.1.5 :005 >     [9, 8, 7, 6, 5],
2.1.5 :006 >     [10, 13, 17, 21],
2.1.5 :007 >     [10, 10, 10, 9, 10],
2.1.5 :008 > ].each{ |test| p ->a{m=a[0];a.map{|n|m>n ?p: m=n}-[p]}[test] }
[1, 2, 5, 7]
[10, 12]
[-7, -5, 0, 1]
[9]
[10, 13, 17, 21]
[10, 10, 10, 10]

```
> 2 votes

# Answer
## Minkolang 0.9, 18 bytes

```
ndN(nd1R`2&dN$I$).

```

Try it here.

### Explanation

```
ndN                Take first integer from input
(         $I$).    Repeat until the input is empty and then stop.
 nd1R`             Is the next integer less than the previous one?
      2&dN         If not (i.e., it's greater than or equal to), print it.

```
> 2 votes

# Answer
# Python, 102 99 94 + 5 6 non-file-final newlines = 107 105 100 bytes

(I used tabs for indentation)

```
def d(l):
    j=b=0;m=l[j];r=[]
    for i in l:
        (m,b)=[(m,0),(i,1)][i>=m]
        if b>0:r+=[i]
        j+=1
    l[:]=r

```

Not the best out there, but this is my first shot at code golf. Couldn't figure out a way to sort the list inline without running into removal-related bugs, so I moved the ordered elements to a temporary list.

EDIT: list.append() is shorter than doing it the ugly way

r+=\[i\] was shorter than list.append(); thanks njzk2!
> 2 votes

# Answer
# Scala: 232 126 120 bytes

```
def f(x:Int*)=(Seq[Int]()/:x)((r,y)=>r.headOption.filter(y>=).map(_=>y+:r).getOrElse(if(r.isEmpty) y+:r else r)).reverse

```
> 2 votes

# Answer
# NARS2000 APL, 13 bytes

NARS2000 is a free APL interpreter for Windows; it includes multiset features accessed with the  operator.

```
(+⍦∩⌈\)

```

This is a monadic fork that takes the multiset intersection (`⍦∩`) of the input (`+`)\* and the list of running maximums (`⌈\`).

Since  is not a standard APL character in the one-byte APL legacy encodings, we must use UTF-8, making the `⍦∩⌈` characters three bytes each. I chose `+` instead of  to save two bytes.

NARS2000 supports forks, which can be built into trains without parentheses, but unlike Dyalog it doesn't allow assignment to a function without wrapping the function in parentheses.

*`+` is technically complex conjugate, but the input is real.
> 2 votes

# Answer
# Scala, 54 bytes

```
def f(x:Int*)=(x:\Seq[Int]())((y,r)=>y+:r.filter(y<=))

```

Ungolfed:

```
def dropSort(xs: Seq[Int]): Seq[Int] =
  xs.foldRight(Seq.empty[Int]) { (x, result) =>
    x +: result.filter(r => r >= x)
  }

```
> 2 votes

# Answer
## Tiny Lisp, 107 bytes

(This language was only published after this question, so this answer runs out of competition. Not that it had any chance to win. *The language later evolved further to have more buildins than the ones I used here, but I'm staying with the version I originally implemented in 2015. This answer still works with the newer official interpreter, though it gives some warnings because I define a parameter `a` which shadows the new buildin `a` (for adding).*Thanks to DLosc for the TIO link.)

`(d r(q((m a)(i a(i(l(h a)m)(r m(t a))(c(h a)(r(h a)(t a))))()))))(d ds(q((b)(i b(c(h b)(r(h b)(t b)))()))))`

This defines a function `ds` (and its recursive helper function `r`) which sorts its argument, which must be a list of integers.

`r` is not a tail-recursive function, so for very long lists this might run into a stack overflow.

Ungolfed:

```
(d r
   (q((m a)
      (i a
         (i (l (h a) m)
            (r m (t a))
            (c (h a)
               (r (h a) (t a))
             )
          )
         ()
       )
   ) )
 )
(d ds
  (q(
      (b)
      (i b
        (c (h b)
           (r (h b) (t b))
         )
        ()
       )
   ) )
 )

```

Here are some examples how to use this (with the test cases from the question):

```
(d list (q (args args)))
(d -
   (q( (n)
       (s 0 n)
    ) )
 )

(ds (list 1 2 5 4 3 7))
(ds (list 10 (- 1) 12))
(ds (list (- 7) (- 8) (- 5) 0 (- 1) 1))
(ds (list 9 8 7 6 5))
(ds (list 10 13 17 21))
(ds (list 10 10 10 9 10))

```

(Yeah, `-7` is not an integer literal, so we have to define a function to represent them.) Output:

```
list
-
(1 2 5 7)
(10 12)
(-7 -5 0 1)
(9)
(10 13 17 21)
(10 10 10 10)

```
> 2 votes

# Answer
# Jelly, 5 bytes

```
=»\Tị

```

Note that the challenge predates the creation of Jelly.

Try it online!

### How it works

```
=»\Tị  Main link. Argument: A (list)

 »\    Yield the cumulative maxima of A.
=      Perform element-by-element comparison.
       Yields 1 iff A[n] = max(A[1], ..., A[n]).
   T   Get all indices of truthy elements.
    ị  Retrieve the items of A at those indices.

```
> 2 votes

# Answer
# SWI-Prolog, 55 bytes

```
A/B:-append(C,[D,E|F],A),E<D,append(C,[D|F],G),G/B;A=B.

```

Usage: Call "*List*/X" where *List* is a bracket-enclosed, comma-separated list e.g. \[1,4,5,1,11,6,7\].
> 2 votes

# Answer
# Python 2, 41 bytes

```
for n in input():
 if-n<=id:print n;id=-n

```

Try it online!

A nice to trick is to use `id` as the initial running maximum, since it's already initialized. Python 2 allows this weird comparison, but unfortunately functions are smaller than numbers, we instead store the running max negated.

---

# Python 3.8 (pre-release), 41 bytes

```
lambda l,m=-128:[m:=n for n in l if n>=m]

```

Try it online!

A nice solution using the Python 3.8+ walrus operator. We use `-128` as the initial minimum since the challenge specifies the code needs to work for signed 8-bit integers.
> 2 votes

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

```
lambda l:[l:=[n]for n in l if n>=l[0]]

```

Try it online!

This outputs in the format

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

```

e.g. a list of lists containing one element each. According to this default for output, it is allowed to use a singleton list in place of a single value, so arguably this should be allowed as well.
> 2 votes

# Answer
# Mathematica, 27 bytes

```
Pick[#,#-Max~FoldList~#,0]&

```
> 1 votes

# Answer
# Haskell, 52 bytes

```
d(x:l)=x:e l x
e(x:l)m|x<m=e l m|0<1=x:e l x
e[]_=[]

```

`d` expects a list.
> 1 votes

# Answer
# OCaml, 62

```
let rec f=function a::b::c when a>b->f(a::c)|a::t->a::f t|t->t

```

The idea is that if the second element is less than the first element, then we should discard the second element. Otherwise, the first element is kept and we move on to the rest of the list.
> 1 votes

# Answer
# Ruby, 45 bytes

```
->a{o=[];a.map{|n|o<<n if !o[0]||n>=o.max};o}

```
> 1 votes

# Answer
# Simplex v.0.7, 32 bytes

That was long. Sorry for the vague explanation.

```
u{viRux}ly^nR@^m^_R&>n?[L@o' s]]
u{viRux}                         ~~ take pseudo-tuple input
        ly                       ~~ converts to tuple
          ^nR@                   ~~ takes minimum and puts it into register
              ^m               ] ~~ map the tuple using inner function
                ^_               ~~ the current value
                  R&>n           ~~ checks if current value is not greater
                      ?[      ]  ~~ does inner if so
                        L@o' s   ~~ outputs the number and a space; stores as current min

```
> 1 votes

# Answer
# Perl 5, (33 Bytes+2) = 35

A regex-less solution.

```
map{print$p=$_.$"if$_>=$p||!$p}@F

```

### Test

*Note that the @F array is populated because of the -a switch.*

```
$ echo -7 -8 -5 0 -1 4 4 3 5|perl -na -e 'map{print$p=$_.$"if$_>=$p||!$p}@F'
-7 -5 0 4 4 5

```
> 1 votes

# Answer
# MATL, 6 bytes

```
ttY>=)

```

Try it online!
> 1 votes

# Answer
# Japt, 8 bytes

```
f@¯Y e§X

```

Try it here
> 1 votes

# Answer
# 05AB1E, ~~8~~ 6 bytes

```
vyMyQ—

```

Try it online!

```
v          # for each item of the input list
 y         # push it on the stack
  M        # push the maximum of the stack
   yQ      # is it equal to the maximum?
     —     # if yes, print it

```
> 1 votes

# Answer
## Python 3, ~~58~~ 56 bytes

```
f=lambda x:[e for i,e in enumerate(x)if max(x[:i+1])==e]

```

Not sure if the input would be a string or a list, my code only would work in the second case.
> 1 votes

# Answer
# VBA, ~~173~~ 133 bytes

```
Sub s(c)
d=UBound(c)
ReDim r(d)
r(i)=c(i)
For i=1To d
If r(j)<=c(i)Then j=j+1:r(j)=c(i)
Next
ReDim Preserve r(j)
c=r
End Sub

```

(after edits) The above code is shorter and expects the parameter `c` to be passed as a variant array of numbers. My original Test\_Cases sub below uses the `Split()` function which returns an array of strings. You won't be able to use Test\_Cases to test the above code. If you want to see the algorithm working you need to test with the function below.

### 148 bytes (as a function expecting a string array)

```
Function s(c)
d=UBound(c)
ReDim r(d)
r(i)=c(i)
For i=1To d
If Val(r(j))<=c(i)Then j=j+1:r(j)=c(i)
Next
ReDim Preserve r(j)
s=r
End Function

```

The following code use the function s() and sends all the test cases and shows the result.

```
Public Sub Test_Cases()

    Dim cases(5, 1) As String
    Dim i As Integer
    Dim match As Boolean

    ' Define space-delimited strings of numbers.
    ' The second array column shows the expected response.
    cases(0, 0) = "1 2 5 4 3 7":     cases(0, 1) = "1 2 5 7"
    cases(1, 0) = "10 -1 12":        cases(1, 1) = "10 12"
    cases(2, 0) = "-7 -8 -5 0 -1 1": cases(2, 1) = "-7 -5 0 1"
    cases(3, 0) = "9 8 7 6 5":       cases(3, 1) = "9"
    cases(4, 0) = "10 13 17 21":     cases(4, 1) = "10 13 17 21"
    cases(5, 0) = "10 10 10 9 10":   cases(5, 1) = "10 10 10 10"

    Debug.Print "Case Input"; Tab(25); "Output"; Tab(38); "Do they match?"
    For i = 0 To UBound(cases())
        Debug.Print i; Tab(6); cases(i, 0); Tab(25); cases(i, 1); Tab(42);
        ' When calling the sorting function, use Split() to convert the string to
        ' a character array and then use Join() to convert the sorted array back
        ' into a string.  Compare that to the expected response in the second column.
        match = cases(i, 1) = Join(s(Split(cases(i, 0), " ")), " ")
        Debug.Print match
    Next i
    Debug.Print

End Sub

```

Output should look like this in the Immediate window:

```
Case Input              Output       Do they match?
 0   1 2 5 4 3 7        1 2 5 7          True
 1   10 -1 12           10 12            True
 2   -7 -8 -5 0 -1 1    -7 -5 0 1        True
 3   9 8 7 6 5          9                True
 4   10 13 17 21        10 13 17 21      True
 5   10 10 10 9 10      10 10 10 10      True

```

This was a fun challenge. If you know of an online interpreter like TIO for VB6/VBScript/VBA please leave a comment.

*If you want to test this code and have Microsoft Excel, Word, Access, or Outlook installed (Windows only), press Alt+F11 to open the VBA IDE. Insert a new code module (Alt+I,M) and clear out `Option Explicit`. Then paste in the code and press F5 to run it. The results should appear in the Immediate Window (press Ctrl+G if you don't see it).*
> 1 votes

# Answer
# Oracle SQL, 115 bytes (Version 12c+)

```
select x from t match_recognize(order by i all rows per match pattern((p|{-y-})+)define p as x>=nvl(last(p.x,1),x))

```

It works with an assumption that input data is stored in a table t(i,x) (i for order), e.g.

```
with t(i,x) as (select rownum,value(v) from table(sys.odcinumberlist(1,2,5,4,3,7))v)

```

Test in SQL\*Plus.

```
SQL> with t(i,x) as (select rownum,value(v) from table(sys.odcinumberlist(1,2,5,4,3,7))v)
  2  select x from t match_recognize(order by i all rows per match pattern((p|{-y-})+)define p as x>=nvl(last(p.x,1),x))
  3  /

         X
----------
         1
         2
         5
         7

```
> 1 votes

# Answer
# Maple (48 and 50 bytes)

48 byte solution using a `for` loop:

```
m:=L[1];(for v in L do if v>=m then m:=v fi od);

```

50 byte solution using `seq`:

```
seq(if L[i]>=max(L[..i])then L[i]fi,i=1..nops(L));

```

Both examples expect their input to be in a list, L, and produce their output as a sequence.
> 1 votes

# Answer
# Vyxal, ~~9~~ 5 bytes

```
ɖ∴=Tİ

```

Try it Online!

### Explanation

```
ɖ∴=Tİ
ɖ     # Cumulatively reduce by an element
 ∴    # Dyadic Maximum
  =   # equal
   T  # Get indices of truthy elements
    İ # Index into list at indices

```
> 1 votes

# Answer
# Thunno, \\$ 13 \log\_{256}(96) \approx \\$ 10.7 bytes

```
eDM=E1zIz0sAI

```

Attempt This Online!

#### Explanation

```
eDM=E1zIz0sAI  # Implicit input
e   E          # Map over the input:
 D             #  Duplicate it
  M=           #  Is it the largest number on the stack?
     1zI       # Truthy indices of this list
        z0     # Push the input list again
          sAI  # Index into the input list
               # Implicit output

```
> 1 votes

# Answer
# Thunno 2, 6 bytes

```
Ʋ§;=Vi

```

Attempt This Online!

#### Explanation

```
Ʋ§;=Vi  # Implicit input
Ʋ ;     # Cumulative reduce (scanl) by:
 §      # Dyadic maximum
   =    # Equals the input list?
    V   # Truthy indices
     i  # Index in
        # Implicit output

```
> 1 votes

# Answer
# rs, ~~121~~ 109 bytes

```
(\d+)/(_)^^(\1)
-/n
+\b((_+) n_+|(n_+) \3_+|(_+)(_+) \4|(_+ ) |( ) n_+)\b/\2\3\4\5\6\7
n/-
(_+)/(^^\1)
  / 0

```

The magic line is 3, which basically continuously deletes elements that aren't sorted.

Live demo and test cases.

## 121-byte version

```
(\d+)/(_)^^(\1)
-/n
+\b(((_+) n_+)|((n_+) \5_+)|((_+)(_+) \7)|((_+ ) )|(( ) n_+))\b/\3\5\7\8\10\12
n/-
(_+)/(^^\1)
  / 0

```

Dang...12 groups...

Live demo and test cases.
> 0 votes

# Answer
# Ceylon, 73

```
Integer[]d(Integer[]l)=>[for(i->x in l.indexed)if(x==max{x,*l[0:i]})x];

```

Formatted and commented:

```
// dropsort: "sorts" a sequence of integers by dropping all elements which don't fit.
// input and output are (possible empty) sequences of integers.
Integer[] d(Integer[] l) =>
// construct a sequence with a comprehension
        [
    // iterate over the input sequence, with indexes.
    for (i->x in l.indexed)
        // only if x it is the maximum of ...
        if (x == max
            // .. an iterable made from x and the part of the input sequence just before the current index ...
                { x, *l[0:i] })
            // ... include x in the iteration.
            x];

```

This features an sequence comprehension (with `for` and `if` clause) for the return value, the `=>` function defintion, the shortcut syntax `X[]` for `Sequential<X>` (i.e. a possibly empty sequence), a named argument list for `max`, in which we have actually no named arguments, but the contents for an iterable argument, given by a single entry and a spread argument made from a measured subsequence, to make it (the argument) non-empty (otherwise `max` could possibly return `null`, which can't be compared to `x`).
> 0 votes

# Answer
# Python 2 59 bytes

```
f=lambda a: reduce(lambda x,y:x+([],[y])[y>x[-1]],a,[a[0]])

```

Assumes the list is not empty, as stated in the description. Simple.
> 0 votes

# Answer
# RETURN, 29 bytes (noncompetitive)

```
[␃$a:␌[$¥][$a;-<[%][$a:␌]?]#]

```

`Try it here.`

Anonymous lambda that leaves result on Stack2. Usage:

```
1 2 5 4 3 7[␃$a:␌[$¥][$a;-<[%][$a:␌]?]#]!

```

NOTE: Make sure to paste this string using the `Insert String` button, which will transform the control pictures into their respective unprintables.

# Explanation

```
[                            ]  lambda
 ␃$a:␌                         reverse stack, set TOS to a and push to Stack2
       [  ][               ]#   while loop
        $¥                        check if TOS is integer
            $a;-<                 if so, check if TOS < a
                 [ ][    ]?       conditional
                  %                 if so, drop TOS
                     $a:␌           otherwise, set TOS to a and push to Stack2

```
> 0 votes

# Answer
# PHP, 63 bytes

```
function d($l){$m=$l[0];foreach($l as$n)echo$n<$m?"":$m="$n ";}

```

Try it online!
> 0 votes

# Answer
# SmileBASIC, 57 bytes

```
DEF D A
WHILE LEN(A)N=SHIFT(A)IF N>=M THEN M=N?N
WEND
END

```
> 0 votes

# Answer
# Perl 5, ~~24~~ 22 bytes

Includes `+2` for `-la`

```
#!/usr/bin/perl -la
$_<"$o $_"||say$o=$_

```

Try it online!
> 0 votes

# Answer
# Bash, 63 bytes

```
echo $1;a=$1;while test $a -gt ${2:?};do shift;done;shift;$0 $@

```

Try it online! (+3 bytes since "$0 $@" doesn't work in TIO)
> 0 votes

# Answer
# Perl 5.10.0 `-n`, ~~17~~ ~~16~~ 15 bytes

```
$m>$_||say$m=$_

```

Try it online!

-1 byte thanks to Xcali
> 0 votes

# Answer
# K (oK), 11 bytes

**Solution:**

```
{x@&~<':x}/

```

Try it online!

**Examples:**

```
{x@&~<':x}/1 2 5 4 3 7
1 2 5 7
{x@&~<':x}/10 -1 12
10 12
{x@&~<':x}/-7 -8 -5 0 -1 1
-7 -5 0 1
{x@&~<':x}/9 8 7 6 5
,9
{x@&~<':x}/10 13 17 21
10 13 17 21
{x@&~<':x}/10 10 10 9 10
10 10 10 10

```

**Explanation:**

```
{x@&~<':x}/ / the solution
{        }/ / perform function {} until results converge
     <':x   / less-than (<) each-previous (':) input
    ~       / not
   &        / where, indices where true
 x@         / index back into input at these indices

```
> 0 votes

# Answer
# PowerShell, 59 bytes

```
param($a)$a[0];(1..$a.Count|?{$a[$_]-ge$a[$_-1]})|%{$a[$_]}

```

Try it online!

I will golf this further as soon as possible.
> 0 votes

# Answer
# Perl 6, 35 bytes

```
{(grep {.[0]==.max},[\R,] $_)[*;0]}

```

Try it online!
> 0 votes

# Answer
## Clojure, 55 bytes

```
#(for[[i j](map list(reductions max %)%):when(= i j)]j)

```

One day I'm gonna do a "Golfure" or something of that short which will have one-symbol names for most handy functions, and even more generic macros.
> 0 votes

# Answer
# Python 3, ~~68~~ ~~64~~ 62 bytes

```
lambda L:[L[i]for i in range(len(L))if L[i]>=max(L[:1]+L[:i])]

```

Try it online!
> 0 votes

# Answer
# C++ (gcc), ~~122~~ 119 bytes

*-3 bytes thanx to ceilingcat*

```
#include<list>
auto f(std::list<int>l){auto i=l.begin();for(int m=*i;i!=l.end();)i=*i>=m?m=*i,++i:l.erase(i);return l;}

```

Try it online!
> 0 votes

# Answer
# JavaScript, ~~72~~70 bytes

```
a=>{for(b=[a[l=i=0]];i<a.length;b[l]>=a[++i]?b[++l]=a[i]:0);return a}

```

72B-\>70B - -2B for removing assignment of the function.
> 0 votes

# Answer
# MathGolf, 10 bytes

```
╓\ô`╙┼=╛o╘

```

Try it online!

This solution relies on stack manipulation. It could have been 2 bytes shorter if negative numbers are not included (skip the first two bytes). Basically a port of the 05AB1E answer, except there is more of a hassle to get the stack right.

## Explanation

```
╓            minimum of two elements, min of list, minimum by filter
 \           swap top elements, pushing list to top
  ô          start block of length 6
   `         duplicate the top two items
    ╙        maximum of two elements, max of list, maximum by filter
     ┼       duplicate second item from top and push to top
      =      is equal (is the current element equal to the total maximum so far)
       ╛o    print without popping if equal
             loop ends here
         ╘   discard everything in stack

```
> 0 votes

# Answer
# Pushy, 14 bytes

```
@vL:Ov2d>?.;;_

```

Try it online!

```
                     \ Implicit: input on main stack.
@                    \ Reverse stack.
 v                   \ Move top item to auxiliary stack.
  L:        ;        \ length(main stack) times do:
    Ov               \   Move top item from main stack to auxiliary stack.
      2d>? ;         \   If top element > second element:
          .          \       Pop the main stack element.
             _       \ Output stack.

```
> 0 votes

# Answer
# Factor, 41 bytes

```
[ -1/0. swap [ 2dup max -rot > ] reject ]

```

Attempt This Online!
> 0 votes

# Answer
# Nekomata, 4 bytes

```
pƆᵖ≤

```

Attempt This Online!

```
pƆᵖ≤
p       For all prefixes of the input
 Ɔ      Split it into the last element and the rest
  ᵖ≤    Check if the last element is greater than or equal to the rest
        If so, the last element is returned

```
> 0 votes

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


title: Generate Fibonacci Primes Quickly

text:
# Question
Title: Generate Fibonacci Primes Quickly
Unsurprisingly, fibonacci primes are primes that are also Fibonacci numbers. There are currently 34 known Fibonacci primes and an additional 15 probable Fibonacci primes. For the purpose of this challenge, the Fibonacci numbers are the sequence \\$F\_n\\$ defined as \\$F\_1 = 1\\$, \\$F\_2 = 1\\$, and \\$F\_n = F\_{n-1} + F\_{n-2}\\$, and a number is considered prime if it passes a probabilistic prime test with a probability of being incorrect of less than \\$2^{-32}\\$. For example, since a \\$k\\$ round Miller-Rabin test has an error probability of \\$4^{-k}\\$, a 16 round Miller-Rabin test is sufficient to prove primality for the purpose of this challenge.

## Submissions:

The goal of this challenge is to write a full program that calculates every Fibonacci prime and its index in the Fibonacci series as fast as possible.

Submissions shall be a full program, complete with instructions for building and running it. Submissions must be in a language freely available for noncommercial use and capable of running on Windows 10, and users must be prepared to provide installation instructions for that language. External libraries are permitted, with the same caveats that apply to languages.

Primes will be output by writing them as base 10 integers to stdout in ascending order in the format

```
index,prime\n

```

where `\n` is the newline character. The numbers can have extraneous leading/trailing whitespace other than the newline character.

## Scoring

The programs will be run on an Intel(R) Core(TM) i5-8365U CPU with 8 threads, avx-2 support, and 24 Gigabytes of ram. The largest prime that can be correctly reached in one minute wins. Tiebreaker is the time taken to reach the largest value. Programs that tamper with my computer or the testing program will be disqualified. Programs that error or otherwise fail to produce the correct output will be judged based on the furthest Fibonacci prime reached before they failed.

## Results

Sorry for the delay, getting Anders Kaseorg's entry to build properly wound up being way harder than it needed to be.

```
Results:
  anders_kaseorg:
    num: 27
    time: 44.6317962s
  aleph_alpha:
    num: 24
    time: 22.6188601s
  example:
    num: 12
    time: 23.2418081s

```

see also: A005478, A001605

The test program can be found here. Additionally, there is an example program here.

# Answer
> 6 votes
# Rust, \\$F\_{14431}\\$ in ≈ 58 s

(Unofficial estimate based on the expected CPU performance ratio.)

After special-casing \\$F\_3, F\_4\\$, this tests every prime-indexed Fibonacci number with the GMP `mpz_probab_prime_p` function, which performs a Baillie–PSW test and `rep - 24` Miller–Rabin iterations. Since Baillie-PSW has no proven error bound, I pass `24 + 16` to ensure 16 Miller–Rabin iterations.

Build with `cargo build --release` and run `target/release/fibprimes`.

**`Cargo.toml`**

```
[package]
name = "fibprimes"
version = "0.1.0"
edition = "2021"

[dependencies]
pariter = "0.5.1"
rug = { version = "1.16.0", features = ["integer"], default-features = false }

```

**`src/main.rs`**

```
use pariter::IteratorExt;
use rug::{integer::IsPrime, Integer};
use std::iter;

fn main() {
    println!("3,2");
    println!("4,3");

    let mut fib0 = Integer::from(1);
    let mut fib1 = Integer::from(2);
    let mut n = Integer::from(3);

    for (n, fib) in iter::from_fn(move || {
        let n1 = Integer::from(n.next_prime_ref());
        while n != n1 {
            fib0 += &fib1;
            fib1 += &fib0;
            n += 2;
        }
        Some((n.clone(), fib1.clone()))
    })
    .parallel_filter(|(_, fib)| fib.is_probably_prime(24 + 16) != IsPrime::No)
    {
        println!("{n},{fib}");
    }
}

```

# Answer
> 3 votes
# C + PARI/GP's C library, \\$F\_{9677}\\$ in 25s on my computer

```
#include <pari/pari.h>

void f(long n)
{
    GEN a = fibo(n);
    if (ispseudoprime(a, 16))
        pari_printf("%d,%Ps\n", n, a);
    return;
}

int main()
{
    pari_init(8000000, 500000);

    f(3);
    f(4);

    long n;
    forprime_t iter;
    u_forprime_init(&iter, 5, ULONG_MAX);

    while (n = u_forprime_next(&iter))
        f(n);

    return 0;
}

```

If you are using Ubuntu or Debian, you need to install the package `libpari-dev`. For Arch Linux, `pari-gp` is enough.

Compiles with `gcc -O3 filename.c -lpari`.

# Answer
> 0 votes
# Python, gmpy2, \\$F\_{9677}\\$ in 27s on my computer.

Same trick as @Anders Kaseorg's Rust answer.

```
import time

import gmpy2
from gmpy2 import mpz
# from itertools import count
import time

# set the precision for probable prime test
gmpy2.get_context().precision = 24 + 16

def next_prime(n):
    candidate = n + 1 if n % 2 == 0 else n + 2
    while not gmpy2.is_prime(candidate):
        candidate += 2
    return candidate

def fib_prime_gen():
    fib0, fib1 = mpz(3), mpz(5)
    n = mpz(5)
    yield n, fib1

    while True:
        fib0, fib1 = fib0 + fib1, (fib1 << 1) + fib0
        n += 2
        # print(f"{n=} {fib1=}")
        if gmpy2.is_prime(fib1):
            yield n, fib1

print("3,2")
print("4,3")

start_time=time.time()
for n, fib in fib_prime_gen():
    print(f"{n},{fib}")
    if n>=9677:
        break

print(f"F9677 in {time.time()-start_time} seconds.")

```

---
Tags: primes, fastest-code, fibonacci
---


# Question
Title: Print the power set of the power set ... of an empty set
Given a non-negative integer `n`, print the result of `P(P(...P({})))`, where the number of `P`'s is `n` (`P` is the power set function).

```
0 => {}
1 => P({})
2 => P(P({}))
3 => P(P(P({})))
n => P(f(n-1))

```

```
input   result
0       {}
1       {{}}
2       {{},{{}}}
3       {{},{{}},{{{}}},{{},{{}}}}
...

```

The result should only contain parentheses/brackets/braces and commas, spaces and newlines are allowed.

# Answer
# Jelly, 3 bytes

```
ŒP¡
```

Attempt This Online!

Using standard I/O rules; takes input from STDIN

Explanation:

```
  ¡         repeatedly apply
ŒP           the power set
             to nothing
              which defaults to 0
               which is turned into the range [1..0]
                which is []

```

---

If you insist on the `{{},{{}}}` formatting:

## Jelly, 12 bytes

```
ŒP¡ŒṘ“[{]}”y
```

Attempt This Online!

This could probably be shorter, but I'm not too interested in golfing boring formatting code.

Explanation:

```
ŒP¡ŒṘ“[{]}”y
  ¡                 repeatedly apply
ŒP                   the power set
   ŒṘ               convert to string representation
            y       translate
     “[{]}”          square brackets to curly braces

```
> 9 votes

# Answer
# Burlesque, 8 bytes

```
{}1qR@C~

```

Try it online!

```
{}   # Empty block
1    # Continuation takes top 1 elements of stack
qR@  # Quoted powerset
C~   # Continuation forever, printing all powersets

```

If you insist on getting a particular N

# Burlesque, 11 bytes

```
{}1qR@C~j!!

```

Try it online!

```
j!! # Reorder stack, get from block

```

And if you insist on comma-separated formatting add 8 bytes for

```
up' ',r~

```
> 8 votes

# Answer
# Wolfram Language (Mathematica), 19 bytes

```
Nest[Subsets,{},#]&

```

Try it online!

In the notebook interface, the results are printed without spaces. But in TIO or the text-based interface, spaces are automatically added.
> 7 votes

# Answer
# Vyxal, 4 bytes

or 12

```
¾?(ṗ

```

## Explanation

```
¾?(ṗ
¾     Global array, empty at the start
 ?    Get input n
  (   Start loop n times
   ṗ  Powerset

```

Try it Online!

## 12 bytes with the curly braces formatting:

(thanks to @lyxal)

```
¾?(ṗ)S¾S‛{}Ŀ

```

```
¾?(ṗ)S¾S‛{}Ŀ
¾?(ṗ)          The boring stuff
     S         Stringify the power-setted list
      ¾        Empty list -> `[]`
       ‛{}     Curly braces
          Ŀ    Transliterate, replace `[]` with the curly braces

```

The `P` prints the list with its python representation. Try it online!
> 7 votes

# Answer
# Python, 96 bytes

```
from itertools import*
f=lambda n:n and(chain(*(combinations(f(n-1),r)for r in range(n+1))))or()
```

Attempt This Online!
> 6 votes

# Answer
# Haskell, 53 bytes

```
f=(!!)$iterate(\l->init l++[','|l/="{}"]++l++"}")"{}"

```

Try it online!

My first golf. Nothing particularly clever, uses the Fokker trick to deal with the base case.
> 5 votes

# Answer
# Pyth, 3 or ~~17~~ 11 bytes

```
yFY

```

Try it online!

`F` \- Repeat *Q* times, where *Q* is the implicit input:

`y` \- powerset of

`Y` \- empty list

### With formatting

```
X`yFYQ"[]}{

```

Try it online!

`X..."[]}{` \- convert each occurrence of `[` to `{` and each occurrence of `]` to `}`
> 4 votes

# Answer
# 05AB1E (legacy), 4 or 17 bytes

Regular I/O using `[]` instead of `{}` and spaces after the commas would be 4 bytes:

```
¯IFæ

```

Try it online or verify the first few test cases.

Strict I/O format is 17 bytes:

```
¯IFæ}"ÿ"„[]„{}‡ðK

```

Try it online or verify the first few test cases.

**Explanation:**

`"ÿ"` on lists only works in the legacy version of 05AB1E (built in Python), and unfortunately not in the new 05AB1E version (built in Elixir). I'm not sure how to do this challenge in the new version of 05AB1E, which lacks any form of `toString` builtin on lists..

```
¯        # Push an empty list: []
 IF      # Loop the input amount of times:
   æ     #  Pop the current list, and push its powerset
         # (after the loop, the result is output implicitly)

¯IFæ     # Same as above
  }      # Close the loop
   "ÿ"   # Convert the (nested) list to a string
„[]„{}‡  # Transliterate all "[" to "{" and "]" to "}"
ðK       # Remove all spaces
         # (after which the result is output implicitly)

```
> 3 votes

# Answer
# Python 3, 71 bytes

```
f=lambda n,k=1:n and f(n-1,1<<k)or[f(0,i+1)for i in range(k)if~-k>>i&1]

```

Try it online!

Adapts pxeger's Python answer to Enumerate all pure sets.

Computes the pure set corresponding to \\$^n2-1\\$ in the binary-encoding enumeration, which consists of the \\$^{n-1}2\\$ distinct sets with rank less than \\$n\\$.
> 3 votes

# Answer
# JavaScript (ES10), 95 bytes

Assuming a strict output format:

```
f=(n,a=[])=>n?f(n-1,a.reduce((a,x)=>a.flatMap(y=>[y,[...y,x]]),[[]])):(g=a=>`{${a.map(g)}}`)(a)

```

Try it online!

---

# JavaScript (ES10), 71 bytes

Returning an array of arrays:

```
f=(n,a=[])=>n?f(n-1,a.reduce((a,x)=>a.flatMap(y=>[y,[...y,x]]),[[]])):a

```

Try it online!
> 2 votes

# Answer
# Factor \+ `math.combinatorics`, 72 bytes

```
[ { } [ all-subsets ] repeat unparse " "without "}{""},{"replace write ]

```

Try it online!

As written.

---

# Factor \+ `math.combinatorics`, 30 bytes

```
[ { } [ all-subsets ] repeat ]

```

Try it online!

With standard I/O rules.
> 2 votes

# Answer
# C (gcc), 206 bytes

```
#define P putchar
f(i,s,c){P(123);for(s=0;i;++s,i>>=1)if(i&1){f(s);if(i>1)P(44);}P(125);}s,i;main(c,v)char**v;{sscanf(v[1],"%d",&c);for(s=!!c--;c>0;--c)s=1<<s;P(123);for(;i<s;){f(i++);if(s>i)P(44);}P(125);}

```

Try it online!
> 2 votes

# Answer
# 05AB1E, 3 bytes

*Ties pxeger's Jelly answer and math junkie's Pyth answer for #1.*

```
ćFæ

```

Try it online! Takes input as a singleton list, and outputs with square brackets.
> 2 votes

# Answer
# Nekomata, 5 bytes

```
Øᶦ{Sa

```

Attempt This Online!

```
Øᶦ{Sa
Ø       Empty list
 ᶦ{     Iterate
   Sa   All subsets

```

Since Nekomata is a non-deterministic language, the built-in `S` (`\subset`) returns any subset non-deterministically instead of all subsets in a list. This is helpful for many other challenges, but not this one. We have to add an `a` (`\allValues`) to get the power set.
> 2 votes

# Answer
# Charcoal, 26 bytes

```
Ｆ⊕Ｎ≔ＥＸ²Ｌυ⪫{}⪫Φυ﹪÷κＸ²ν²,υ⊟υ

```

Try it online! Link is to verbose version of code. Extremely inefficient; do not try `n=4` unless you have a lot of patience (will time out on TIO). Explanation:

```
Ｆ⊕Ｎ

```

Repeat `n+1` times...

```
≔ＥＸ²Ｌυ⪫{}⪫Φυ﹪÷κＸ²ν²,υ

```

... replace the predefined empty list with its formatted powerset.

```
⊟υ

```

Output the last element.

21 bytes using Python list formatting:

```
ＦＮ≔ＥＸ²ＬυΦυ﹪÷κＸ²ν²υ⭆¹υ

```

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

```
ＦＮ

```

Repeat `n` times...

```
≔ＥＸ²ＬυΦυ﹪÷κＸ²ν²υ

```

... replace the predefined empty list with its powerset.

```
⭆¹υ

```

Pretty-print the list.
> 0 votes

# Answer
# , 205 bytes

```
\(n,z=paste0,b=\(x)z('{',x,'}'),p=\(x,e=el(strsplit(x,',')),l=lapply(e,\(i)c(i,NA)),g=do.call(expand.grid,l),d=\(v)z(na.omit(v),collapse=','),a=apply(g,1,d))d(b(a))){s='';for(i in seq_len(n)){s=p(s)};b(s)}
```

Attempt This Online!

A naive implementation of powerset for comma-delimited strings in R, using `seq_len` instead of `1:n` to handle the n = 0 case correctly.
> 0 votes

# Answer
# APL(Dyalog Unicode), 34 bytes SBCS

```
{⎕json{⌿∘⍵¨↓⌽⍉2⊥⍣¯1⊢¯1+⍳2*≢⍵}⍣⍵⊢⍬}

```

Try it on APLgolf!

Marked as community wiki because the power set function has been taken from APLCart.
> 0 votes

# Answer
# BQN, 17 bytes

```
{(⥊(↕2˘)/¨<)⍟⟨⟩}

```

Try it here!

Powerset composed x times on empty set.

---

# BQN, 42 bytes

```
{{'⟨':'{';'⟩':'}';}¨•Repr(⥊(↕2˘)/¨<)⍟⟨⟩}

```

Try it here!

Strictly formatted variant.

If `⟨⟩` count as valid brackets, then simply remove `{'⟨':'{';'⟩':'}';}¨` for a 22-byte solution.
> 0 votes

---
Tags: code-golf, math, set-theory
---