title: Does the start equal the end?

text:
# Question
Title: Does the start equal the end?
# The Task

In this challenge, your task is to write a program or function which takes in a String and outputs a truthy or falsey value based on whether the first character and the last character of the input String are equal.

## Input

You may take input in any way reasonable way. However, assuming that the input is present in a predefined variable is not allowed. Reading from a file, console, command line, input field etc., or taking input as a function argument is allowed.

## Output

You may output in any reasonable format, except for assigning the result to a variable. Writing to a file, console, command line, modal box, function `return` statements etc. is allowed.

## Additional Rules

* The input can be empty String as well, for which you should return a falsey value.
* Single-Char Input Strings should have a truthy result.
* Your program should be case-sensitive. `helloH` should output a falsey value.
* You can only have a single Truthy value and a single Falsey value. For example, outputting `false` for an Input String and `0` for another input String as Falsey values is not allowed.
* Standard loopholes are not allowed.

## Test Cases

```
Input    ->    Output

"10h01"        Truthy
"Nothing"      Falsey
"Acccca"       Falsey
"eraser"       Falsey
"erase"        Truthy
"wow!"         Falsey
"wow"          Truthy
"H"            Truthy
""             Falsey

```

This is , so the shortest code in bytes wins!

# Answer
# Jelly, 3 bytes

```
=ṚḢ

```

Try it online!
> 7 votes

# Answer
# Python 3, 23 bytes

```
s=input()
s[0]!=s[-1]<e

```

Output is via exit code, so **0** (success) is truthy and **1** (failure) is falsy. If this is acceptable, a byte can be saved.

Try it online!

### How it works

First of all, if **s** is an empty string, `s[0]` will raise an *IndexError*, causing the program to fail.

For non-empty **s**, if the first and last characters are equal, `s[0]!=s[-1]` will evaluate to *False*, so the program exits cleanly and immediately.

Finally, if the characters are different, `s[0]!=s[-1]` will evaluate to *True*, causing the compairson `s[-1]<e` to be performed. Since **e** is undefined, that raises a *NameError*.

If backwards compatibility with Python 2 is not desired,

```
s[0]!=s[-1]<3

```

works as well, since comparing a string with an integer raises a *TypeError*.
> 21 votes

# Answer
# JavaScript, 19 bytes

```
a=>a.endsWith(a[0])

```
> 15 votes

# Answer
# Brachylog, 4 bytes

```
h~t?

```

Try it online!

### Explanation

```
h       The head of the Input...
 ~t?    ...is the tail of the Input

```
> 8 votes

# Answer
# 05AB1E, 4 bytes

```
S¬Q¤

```

Try it online! or Try All Tests

```
S    # Split the input into individual characters
 ¬   # Get the first character
  Q  # Check all characters for equality to the first
   ¤ # Get the last value i.e. head == tail

```
> 8 votes

# Answer
# Retina, ~~13~~ 12 bytes

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

```

Try it online! Includes test suite. Edit: Saved 1 byte thanks to @Kobi.
> 7 votes

# Answer
# Mathematica, 15 bytes

```
#&@@#===Last@#&

```

Takes an array of chars. Throws errors when the input is empty but can be ignored.
> 7 votes

# Answer
# Haskell, 21 bytes

`c` takes a `String` and returns a `Bool`.

```
c s=take 1s==[last s]

```

Try it online!

* If not for empty strings, this could have been 16 bytes with `c s=s!!0==last s`.
* `take 1s` gives a list that is just the first element of `s` unless `s` is empty, in which case it's empty too.
* `last s` would error out on an empty string, but Haskell's laziness saves it: A string with a single element is always different from the empty string, without evaluating its element.
> 7 votes

# Answer
# C++ (gcc), 40 bytes

```
[](auto s){return s[0]&&s[0]==s.back();}

```

Try it online!
> 7 votes

# Answer
# Python 2, ~~26~~ ~~25~~ 24 bytes

Thanks to *@Dennis* for saving a byte!

```
lambda x:""<x[:1]==x[-1]

```

Try it online!
> 6 votes

# Answer
# Java, ~~81~~ 77 bytes

* -4 bytes, thanks @KevinCruijssen

**Try Online**

```
boolean f(String s){int l=s.length();return l>0&&s.charAt(l-1)==s.charAt(0);}

```
* Returns `true` if they're equal, otherwise `false`, `false` for empty string

**Array Version, 60 bytes**

```
boolean f(char[]s){int l=s.length;return l>0&&s[0]==s[l-1];}

```
> 6 votes

# Answer
# MATL, 5 bytes

```
&=PO)

```

Try it at MATL Online!

**Explanation**

```
       % Implicitly grab input as a string (of length N)
&=     % Perform an element-wise equality check yielding an N x N matrix
P      % Flip this matrix up-down
O)     % Get the last value in the matrix (column-major ordering)
       % Implicitly display the result

```

In the case, that an empty input string must be handled, then something like the following (8 bytes) would work

```
&=POwhO)

```

This solution simply prepends a `0` to the front of the N x N matrix such that for an empty input, when the matrix is `0 x 0`, there's still a `0` value that is then grabbed by `0)`

Try it at MATL Online
> 5 votes

# Answer
# brainfuck, 43 bytes

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

```

Try it online!

### Explanation

The main loop is `[>[->+<<->],]`. After each iteration, the cell to the right of the current position is the first byte of the string, and the cell to the left is the difference between the most recently handled character and the first. `<[[-]-<]` converts the final result to -1 if nonzero, and the rest converts -1 and 0 to 48 and 49 ("0" and "1") respectively.
> 5 votes

# Answer
# APL (Dyalog), 4 bytes

```
⊃⌽=⊃

```

Try it online!

### Explanation

```
  =                     Compare
   ⊃                    The first element of the right argument with
 ⌽                      The right argument reversed
                        This will return an array of the length of the reversed argument. Each element in the resulting array will be either 0 or 1 depending on whether the element at that position of the reversed argument equals the first element of the original right argument
                        So with argument 'abcda', we compare 'a' with each character in 'adcba' which results in the array 1 0 0 0 1
⊃                       From this result, pick the first element.

```

Here is the reason this works on empty strings. Applying  to an empty string returns a space . But reversing an empty string still returns an empty string, so comparing an empty string with a non-empty string (in this case ) gives an empty numerical vector. And applying  to an empty numerical vector returns `0`. Hence passing an empty string returns `0`.
> 5 votes

# Answer
# Japt, 6 bytes

```
tJ ¥Ug

```

Try it online!
> 4 votes

# Answer
# Java, ~~52~~ 43 bytes

```
s->!s.isEmpty()&&s.endsWith(""+s.charAt(0))

```

To make it work, feed this into a function such as the following that makes a lambda "go":

```
private static boolean f(Function<String, Boolean> func, String value) {
  return func.apply(value);
}

```
> 4 votes

# Answer
# Ruby, ~~26~~ 24 bytes

*Saved two bytes thanks to @philomory!*

```
->e{!!e[0]>0&&e[0]==e[-1]}

```

First post on codegolf -))
> 4 votes

# Answer
## JavaScript, 20 bytes

Add `f=` at the beginning and invoke like `f(arg)`.

```
_=>_[0]==_.slice(-1)

```

```
f=_=>_[0]==_.slice(-1)

i.oninput = e => o.innerHTML = f(i.value);
```

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

### Explanation

This function takes in an argument `_`. In the function body, `_[0]==_.slice(-1)` checks whether the first element of `_` (at `0`th index) equals the last element of it, and returns the appropriate `true` or `false` boolean.
> 3 votes

# Answer
# PHP\>=7.1, 23 Bytes

prints 1 for equal and nothing if the character is different

```
<?=$argn[0]==$argn[-1];

```
> 3 votes

# Answer
# GNU grep, 12 bytes

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

```

Run in extended or PCRE mode.

I don't know if this is considered cheating or not.
> 3 votes

# Answer
# shortC, ~~27~~ ~~26~~ ~~25~~ 24 bytes

```
f(C*s){T*s&&*s==s[Ss)-1]

```

How it works:

```
f(C*s){                     declare int-returning function that takes a string
       T                    return
        *s                  provided string has any length
          &&                and
            *s==s[Ss)-1]    the first character equals the last one

```

Try it online!
> 3 votes

# Answer
## C#, ~~38~~ 30 bytes

```
s=>s!=""&&s[0]==s[s.Length-1];

```

*Saved 8 bytes thanks to @raznagul.*
> 3 votes

# Answer
# Swift, 46 bytes

```
var s=readLine()!,a=Array(s);a[0]==a.last ?1:0

```
> 3 votes

# Answer
## R, 40 bytes

```
function(x)x>""&&rev(y<-charToRaw(x))==y

```

Thanks to Nitrodon for -2 bytes.

Thanks to MickyT for -8 bytes.

Test:

```
f=function(x)x>""&&rev(y<-charToRaw(x))==y
test <- c("10h01", "Nothing", "Acccca", "wow!", "wow", "H", "")
sapply(test, f)
all(sapply(test, f) == c(T, F, F, F, T, T, F))

```

Output:

```
> f=function(x)x>""&&rev(y<-charToRaw(x))==y
> test <- c("10h01", "Nothing", "Acccca", "wow!", "wow", "H", "")
> sapply(test, f)
  10h01 Nothing  Acccca    wow!     wow       H
   TRUE   FALSE   FALSE   FALSE    TRUE    TRUE   FALSE
> all(sapply(test, f) == c(T, F, F, F, T, T, F))
[1] TRUE

```
> 3 votes

# Answer
# \>\<\>, ~~39~~ 33 bytes

```
 2i&01. >~&-?v1v
  i:1+?!^01. >0>n;

```

This is my first time both using \>\<\> and playing code golf, so helpful suggestions would be appreciated.

The code is in three basic sections.

```
2i&01. Pushes an arbitrary number (2 in this case, this causes an empty string to print 0) onto the stack and puts the input's first character in the register.

>i:1+?!^01. Main loop. Pushes the next character onto the stack. If the string has been read completely, then go to the last section

>~&-?v1v
     >0>n;  Compare the first and last characters. Print 1 if they're the same, 0 if not

```
> 3 votes

# Answer
# Google Sheets, 33 Bytes

Takes input from cell `[A1]` and outputs `1` for truthy input and `0` for falsey input.

```
=(A1<>"")*Exact(Left(A1),Right(A1

```

It is noted that the parentheticals in `Exact(` and `Right(` are left unclosed as Google Sheets automatically corrects this as soon as the user has input the formula text and pressed enter to leave that cell.

### Output
> 3 votes

# Answer
# R, ~~50~~ ~~43~~ ~~41~~ ~~40~~ 64

Second solution with 41 bytes for a callable function - thanks to @niczky12 & @Giuseppe - amended for x=""

```
r=function(x,y=utf8ToInt(x))ifelse(x=="","FALSE",(y==rev(y))[1])

```

First with 50 bytes but not for the challenge

```
function(x){charToRaw(x)[1]==rev(charToRaw(x))[1]}

```
> 3 votes

# Answer
# Mornington Crescent, 2585 bytes

```
Take Northern Line to Bank
Take Circle Line to Hammersmith
Take District Line to Mile End
Take District Line to Bank
Take Northern Line to Charing Cross
Take Northern Line to Charing Cross
Take Northern Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Hammersmith
Take Circle Line to Victoria
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Hammersmith
Take District Line to Bow Road
Take District Line to Acton Town
Take Piccadilly Line to Heathrow Terminals 1, 2, 3
Take Piccadilly Line to Acton Town
Take District Line to Acton Town
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Barking
Take District Line to Hammersmith
Take District Line to Mile End
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Charing Cross
Take Northern Line to Charing Cross
Take Northern Line to Bank
Take Circle Line to Bank
Take Circle Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate
Take District Line to Upminster
Take District Line to Upminster
Take District Line to Temple
Take District Line to Barking
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Barking
Take District Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster
Take District Line to Bank
Take Circle Line to Bank
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Angel
Take Northern Line to Bank
Take Circle Line to Temple
Take District Line to Bow Road
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Bow Road
Take District Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Aldgate
Take Circle Line to Victoria
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Angel
Take Northern Line to Bank
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Mornington Crescent

```

Try it online!

I thougt, this was easier...

Outputs 0 for false and 1 for true

```
// Prepare input for right substring
Take Northern Line to Bank
Take Circle Line to Hammersmith
Take District Line to Mile End

// Get char code of first character
Take District Line to Bank
Take Northern Line to Charing Cross
Take Northern Line to Charing Cross

// Put it in Upminster for later calculation
Take Northern Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upminster

// Also save it for later check for null string # Victoria = char code of first
Take District Line to Hammersmith
Take Circle Line to Victoria

// Save 0 # Upney = 0, Bow Road = 0 (for second loop)
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Hammersmith
Take District Line to Bow Road

// Save 1 # Barking = 1
Take District Line to Acton Town
Take Piccadilly Line to Heathrow Terminals 1, 2, 3
Take Piccadilly Line to Acton Town
Take District Line to Acton Town
Take District Line to Parsons Green
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Barking

// Get char code of last letter of input
Take District Line to Hammersmith
Take District Line to Mile End
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Charing Cross
Take Northern Line to Charing Cross

// Bitwise NOT, so we get -(char count)-1
Take Northern Line to Bank
Take Circle Line to Bank
Take Circle Line to Notting Hill Gate
Take Circle Line to Notting Hill Gate

// Add it to the char code of first letter. If they match, the result is -1.
Take District Line to Upminster

// Save the result in Upminster
Take District Line to Upminster

// ********************************************************************************
// * Add some logic. This is quite puzzling because the only control structure    *
// * in Mornington Crescent is a post-test loop. You don't have something like    *
// * an if-else. You can't skip code. You can only define how often a loop should *
// * be repeated.                                                                 *
// * My solution to this is: When checking if the first and last character        *
// * are the same (first char code - last char code = 0), I swap the positions    *
// * of the 0 and 1 variables, then multiply the result of the equality check     *
// * with the new position of 1. If the characters are the same, the loop will    *
// * exit after the first run. If not, it will run another time, swapping the     *
// * 0 and 1 back and exiting after the second run, because it multiplies the     *
// * new equality check with 0.                                                   *
// ********************************************************************************

// Set starting line of loop
Take District Line to Temple

// Swap 0 and 1 # Upney = 1, Barking = 0 (on the first run)
Take District Line to Barking
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Upney
Take District Line to Barking

// Save 1 in Chalfont & Latimer for later multiplication
Take District Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer

// Add 1 to Upminster, to check for equality
Take Metropolitan Line to Aldgate
Take Circle Line to Hammersmith
Take District Line to Upminster

// Multiply the result with 1 in the first run, or 0 in the second run
Take District Line to Bank
Take Circle Line to Bank
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer

// If the result is not 0, run the loop again
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Angel

// **********************************************************************
// * Another control loop to check for empty string.                    *
// * The previous loop will return true if an empty string was entered. *
// **********************************************************************

// Set start of loop
Take Northern Line to Bank
Take Circle Line to Temple

// Swap 0 and 1 # Upney = 0, Bow Road = 1 (on the first run, if previous loop ran once)
//              # Upney = 0, Bow Road = 0 (if previous loop ran twice)
Take District Line to Bow Road
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Hammersmith
Take District Line to Bow Road

// store 1 in Chalfont & Latimer for later multiplication
Take District Line to Hammersmith
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer

// Multiply by char code of first char (0 if empty string)
Take Metropolitan Line to Aldgate
Take Circle Line to Victoria
Take Circle Line to Aldgate
Take Circle Line to Aldgate
Take Metropolitan Line to Chalfont & Latimer

// Loop again if input not empty
Take Metropolitan Line to Moorgate
Take Circle Line to Moorgate
Take Northern Line to Angel

// Fetch result and go home for output
Take Northern Line to Bank
Take District Line to Upney
Take District Line to Bank
Take Circle Line to Bank
Take Northern Line to Mornington Crescent

```
> 3 votes

# Answer
# BRASCA, 3 bytes

This looks like a job for `M`!

```
M=n

```

Try it online!

## Explanation

```
M        - Move the bottom of the stack to the top
 =       - Are they the same? Push 1 if it is, 0 if it isnt.
  n      - Output as number.

```
> 3 votes

# Answer
# Knight, 20 bytes

```
O<!=xP?AxA Gx-Lx 1 1

```

Try it online!

Takes a line from stdin and prints `true` if equal and `false` otherwise.

```
O                           Output the result of:
  < ! (= x P)                 x = input; x is not null and
    ? A x                       the first char's ord is equal to
      A (G x (- L x 1) 1)       the (length-1)th char's ord

```
> 3 votes

# Answer
# Fireball, 4 bytes

```
d1╡├

```

Explanation:

```
d      Duplicate implicit input
 1╡    Get the first character
   ├   Check whether the input ends with the first character

```

Alternative program:

```
d↔♥├

```
> 2 votes

# Answer
# JavaScript (ES6), 25 bytes

```
s=>/^(.)(.*\1)?$/.test(s)

```

21 bytes if we can return `true` for the empty string.

```
s=>s[0]==[...s].pop()

```

---

## Try it

```
f=
s=>/^(.)(.*\1)?$/.test(s)
o.innerText=f(i.value="10h01")
i.oninput=_=>o.innerText=f(i.value)
```

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

# Answer
# Octave, 16 bytes

```
@(s)s(1)==s(end)

```

It takes a string `s` as input, and compares the first `s(1)` element with the last `s(end)`.

This could be `@(s)s(1)-s(end)` if it was OK to swap `true/false` to `false/true`.
> 2 votes

# Answer
## Common Lisp, 83 74 61 58 bytes

### Original: 83 bytes

I've just started learning Common Lisp, so I feel like I'm bringing a putter to a driving range. There must be some kind of recursive macro wizardry or array manipulation possible here that I'm not seeing.

This is an anonymous function that accepts a string as its input:

```
(lambda (s) (let ((n (- (length s) 1))) (when (> n 0) (eq (char s 0) (char s n)))))

```

Prettified:

```
(lambda (s)
  (let ((n (- (length s) 1)))
    (when (> n 0)
      (eq (char s 0)
          (char s n)))))

```

Would love to see a slicker solution!

### Revision 1: 74 bytes

Gotta love those standard library functions!

Ugly:

```
(lambda (s) (when (> (length s) 0) (eq (elt s 0) (elt (reverse s) 0))))

```

Pretty:

```
(lambda (s)
  (when (> (length s) 0)
    (eq (elt s 0)
        (elt (reverse s) 0))))

```

### Revision 1.5: 61 bytes

Whitespace!

```
(lambda(s)(when(>(length s)0)(eq(elt s 0)(elt(reverse s)0))))

```

### Revision 2: 58 bytes

Ugly:

```
(lambda(s)(and(>(length s)0)(not(mismatch s(reverse s)))))

```

Pretty:

```
(lambda (s)
  (and (> (length s) 0)
       (not (mismatch s (reverse s)))))

```

That's all for now! I think I'm smarter already.
> 2 votes

# Answer
# S.I.L.O.S, 81 bytes

```
loadLine
a=256
c=get a
lblb
t=s
s=get a
a+1
if s b
t-c
if t d
i+1
lbld
printInt i

```

Try it online!
> 2 votes

# Answer
## AWK, 29 34 bytes

This one might be cheating slightly, because it requires invoking AWK with the option:

```
`-F ''`

```

In GNU Awk you can use the long-form synonyms:

```
`--field-separator=''`

```

So I added 5 bytes to the total to account for this.

Ugly:

```
NR==1{a=$1}END{print(a==$NF)}

```

Pretty:

```
NR == 1
{
    a = $1
}

END
{
    print(a == $NF)
}

```
> 2 votes

# Answer
# C, ~~50~~ ~~40~~ 36 bytes

Saved 10 bytes thanks to Dennis.

```
#define f(s)(*s&&*s==s[strlen(s)-1])

```

Equates to `0` if the first and last characters are different, or if the string is empty.

You could call `f` with something like:

```
int main(void)
{
    char s[100] = {0};
    gets(s);
    printf("%d\n",f(s));
}

```

Or, try it online!
> 2 votes

# Answer
# Python, 51 bytes

```
s=input()
if s:print(s[0]==s[-1])
else:print(False)

```

Try it online!
> 2 votes

# Answer
# Bash, 37 bytes

```
[ -n "$1" ]&&[ ${1:0:1} == ${1: -1} ]

```

Takes command line input and returns with exit status 0 (truthy) or 1 (falsy).

Test with:

```
bash test.sh "helloH" ; echo $?

```
> 2 votes

# Answer
# Pyth, 9 bytes

```
.xqhzez!1

```

Try it online!

Could make it 5 bytes if I didn't have to deal with `""`, probably even less if I was good at Pyth.
> 2 votes

# Answer
# Casio Basic, 46 bytes

```
StrLeft s,1,a
StrRight s,1,b
Print judge(a=b)

```

Strings aren't very nice to work with in this language. We need to take the first character from the left and right of the string, assign them to `a` and `b`, then print whether `a` is equal to `b`.

45 bytes for the code, 1 byte to enter `s` as parameter.
> 2 votes

# Answer
# Python 3, ~~31~~ 24 Bytes

```
lambda a:a[0]==a[-1]!=''

```

Old code:

```
def f(a):return a[0]==a[-1]!=''

```

This is pretty self explanatory; It takes a string `a` and checks if the first and last chars are equal, but I then had to add the `!=''` in order to satisfy the requirement "`The input can be empty String as well, for which you should return a falsey value`" because Python returns True for an empty string.

EDIT:

- -7 Bytes thanks to @numbermaniac
> 2 votes

# Answer
# Ruby, ~~16~~ 17 bytes

Outputs `true` or `false`. Now with fixed syntax error.

```
p !! ~/./&~/#$&$/

```

Try it online!
> 2 votes

# Answer
# PowerShell, 24 bytes

```
!("$args"[0,-1]|gu).Rank

```

Try it online!
> 2 votes

# Answer
# Labyrinth, <sup>~~27~~</sup> 20 bytes

```
,)!@
 : !
,} _
")=-:

```

Try it online!

-7 bytes thanks to Jo King.

Basic flow goes like this: start at the upper left corner, filter away the empty input at the first T-junction, take the rest of the string at the 2x2 loop, and test for equality at the last T-junction.

### How it works

`x` marks the alternative paths at junctions, which should make the explanation easier to follow.

```
,)!@   Take char input (possibly EOF == -1), increment
 x     If EOF, top is 0, so go straight, print 0 and halt

 x     Otherwise, the string is not empty
 :     Duplicate the first char and move to aux. stack
,}     Go around the 2x2 loop `,")}`:
")x    Take next char input, increment, move to aux. stack
       until it hits EOF, where the stack is [first 0 | last ... first]
  @
  !    `=`: Swap the top of two stacks, giving [first last | (ignored)]
  _    Then calculate first - last
x=-x   If nonzero, take the north branch `_!@`: Push 0, print, halt

x)!@
 :     If zero, go all the way back to the first branch
x} x   (Eventually print 1 and halt)
x)=-:

```
> 2 votes

# Answer
# Lexurgy, 27 bytes

```
a:
([]$1) []* !$1=>*
[]+=>a

```

Outputs an empty string for falsey, and `a` otherwise.

Explanation:

```
a:                # change...
([]$1)            # the first character
       []*        # then 0 or more any character, regex /.*/
           !$1    # then a character that's not the first
              =>* # change to an empty string
# equivalent regex: /(.).*\1/
[]+=>a            # replace the leftovers with "a"

```
> 2 votes

# Answer
# Julia, 22 bytes

```
!s=s>""&&s[1]==s[end]
```

Attempt This Online!
> 2 votes

# Answer
# MUMPS, 27 bytes

```
 w x]""&($e(x)=$e(x,$l(x)))

```

Try it online!

* There is a leading space character so `w` is interpreted as a command and not a label.
* `w` is short for the `write` command which prints the following expression to the console.
* `x]""` checks that `x` is not empty. `]` is the "follows" operator and everything non-empty follows the empty string.
* `$l` is short for `$length` which returns the length of a string.
* `$e` is short for `$extract` which gets characters from a string. `$e(x)` gets the first character of `x` and `$e(x,$l(x))` gets the last character of `x`.

It could be further reduced to 23 bytes in Intersystems Caché/IRIS by replacing `$l(x)` with `*`.

```
 w x]""&($e(x)=$e(x,*))

```
> 2 votes

# Answer
# C#, ~~25~~ 21 bytes

Uses the index operator `^` from C# 8 to get the last character in the string.

```
x=>x!=""&&x[0]==x[^1]

```

Try it online!

-4 bytes thanks to the default
> 2 votes

# Answer
# Python, 31 bytes

```
lambda x:bool(x)and x[0]==x[-1]

```
> 1 votes

# Answer
# , 8 bytes

1 byte thanks to Kritixi Lithos.

```
1{.{.=|.

```

Try it online!
> 1 votes

# Answer
# Python 2, ~~36~~ 35 bytes

*-1 byte thanks to Erik the Outgolfer*

```
lambda s:s[0]==s[-1]if s else False

```

Try it online!
> 1 votes

# Answer
# Standard ML \- ~~52~~ 54 bytes

```
open String
fn s=>s<>""andalso sub(s,0)=sub(s,size s-1)

```
> 1 votes

# Answer
## QBIC, ~~12~~ 11 bytes

```
?_s;|=_s_fA

```

Explanation:

```
?              PRINT
     =         -1 if equal, 0 if not, between
 _s;|          QBIC's Substring function takes a variable amount of parameters.
                 With only a string as argument it takes the leftmost char of it.
                 The ; takes a string from the cmd line and names it A$
                 | closes the call to Substring
      _s_fA    _f flips string A, _s without arguments takes the left 1 char again.

```

---

Original 12 byter, which takes a substring of 1 from the left and 1 from the right:

```
?_s;|=_sA,-1

```

Explanation of the second substring:

```
      _sA,-1   Another call to Substring
                 A$ is implicitly defined by the ; in the other substring
                 -1 sets the starting index at the last position
                 No argument for length = 1 char by default.
               No closing |, auto-added at EOF

```
> 1 votes

# Answer
# CJam, 6

```
q_W>#!

```

Try it online

**Explanation:**

```
q_     read and duplicate the input
W>     get the substring starting from the last position (W=-1)
        the result is empty if the input is empty
#      find the position of that substring within the initial string
        a bit surprising, position of empty string within itself is -1 (not found)
!      negate (0->1, non-zero->0)

```

Note: I consider the behavior of `#` with an empty substring to be a bug in CJam⩽0.6.5 and I will probably fix it in the next version. It's useful for this challenge though.
> 1 votes

# Answer
# Ruby, ~~22~~ 20 bytes

```
->x{x[0]===x[-1]||p}

```
> 1 votes

# Answer
## Excel, 38 bytes

```
=1*IFERROR(CODE(A1)=CODE(RIGHT(A1)),0)

```

Surprisingly longer than I expected, in order to get the *same* truthy/falsy for all cases. Text conditionals ignore case by default in excel, so `"A"="a"` is `TRUE`. Empty cells yield an error for `CODE()`. Multiplied by 1 to force everything to a number, rather than having `TRUE`, `FALSE`, or `0` cases.
> 1 votes

# Answer
## Batch, 52 bytes

```
@set s=!=
@set/ps=
@if "%s:~,1%"=="%s:~-1%" echo 1

```

Outputs `1` if equal, nothing if not. `set/p` doesn't change the variable if nothing is entered, so I can initialise it to a failure case, and `!=` seemed appropriate.
> 1 votes

# Answer
# Perl 6,  ~~18~~  17 bytes

```
{?m/^(.)[.*$0]?$/}

```

Test it

```
{?/^(.)[.*$0]?$/}

```

Test it

## Expanded:

```
{  # bare block lambda with implicit parameter ｢$_｣

  ?        # Boolify the following

  /        # match implicitly against ｢$_｣

    ^      # beginning of string

    (.)    # character ｢$0｣

    [

      .*   # followed by any number of characters
      $0   # and itself

    ]?     # optionally (Str with a single char)

    $  # end of string
  /
}

```
> 1 votes

# Answer
# C, 34 bytes

```
f(char*s){s=*s&&*s==s[puts(s)-2];}

```

Try it online

# C, 35 bytes

```
f(char*s){s=*s&&!strrchr(s,*s)[1];}

```

Try it online
> 1 votes

# Answer
# Java 8, 29 bytes

```
s->s.matches("^(.)(.*\\1)?$")

```

Port of *@Neil*'s Retina answer.

Try it here.
> 1 votes

# Answer
# Brain-Flak, 51 bytes

Includes +1 for `-a`

```
{(<([({})<{({}<>)<>}<>>]{})((){[()](<{}>)}{})>)}{}

```

Try it online!

Outputs 1 on top of the stack for truthy, and either nothing or 0 on top of the stack for falsy. These are consistent with Brain-Flak's "if" statement: `{...}`.

```
{(<                                          >)}{} # If there is input...
     ({})<            >                            #   Evaluate to the first char after...
          {({}<>)<>}<>                             #     reversing the entire stack
   ([                  ]{})((){[()](<{}>)}{})      # Check if the top 2 are equal
                                                   # I.e. first == last

```
> 1 votes

# Answer
# Perl 5: 28 bytes

```
exit$ARGV[0]=~/^(.)(.*\1)?$/

```

Similar to perl 6 but it seems to be shorter as a program.
> 1 votes

# Answer
# PowerShell, 42 bytes

```
$a=(read-host);$a-ne""-and$a[0]-ceq$a[-1]

```
> 1 votes

# Answer
# Brain-Flak, 55 bytes

```
(({})<(())>)({}[<{({}<>)<>}><>{}]<>)((){[()](<{}>)}{})

```

Try it online!
> 1 votes

# Answer
# Actually, 10 bytes

```
;;lb)F@N=*

```

Try it online!

Explanation:

```
;;lb)F@N=*
;;          copy input twice
  lb        length of input, cast to boolean
    )F      first character
      @N    last character
        =   compare equality
         *  multiply by boolean casted length (to make empty strings falsey)

```
> 1 votes

# Answer
# Excel VBA, <sub>~~52~~ ~~48~~ ~~40~~ ~~38~~ ~~37~~ 36</sub> 34 Bytes

Anonymous VBE immediate window function that takes input of type `variant` and expected type `variant\String` from cell `[A1]` on the `ActiveSheet` object and outputs boolean response to the VBE immediate window.

```
?[A1]<>""=([Left(A1)]=[Right(A1)])

```
> 1 votes

# Answer
# Perl 5, 22+1 (-p flag)=23 bytes

```
/^(.).*(.)/;$_=$1 eq$2

```

Outputs 1 for truthy and an empty string for falsey.
> 1 votes

# Answer
# REXX 32 Bytes

```
a=arg(1)
say abbrev(a,right(a,1))

```

Tests if the last character is a valid abbreviation of the whole string.
> 1 votes

# Answer
## Clojure: 21, 27 or 34 bytes

**depending on the handling of "" test case**

`true` for "aba" and "", `false` for "abc":

```
#(=(first %)(last %))

```

`true` for "aba", `nil` for "", `false` for "abc":

```
#(first(map =(reverse %)%))

```

`true` for "aba", `nil` for "" and "abc":

```
#(or(first(map =(reverse %)%))nil)

```
> 1 votes

# Answer
# Chip, 91+3 = 94 bytes

```
*Z~.
,-{mA
>{xmB
|BA|
|CD|AvB
>{xmC+G
>-{mD+H
>{-mE+~t
>x{mF^S
|EF|
|HG|
>x{mG
>{-mH
Z--)~a

```

+3 for `-z`

Outputs the byte `0x0` for falsey, and `0x1` for truthy. This is a lot bigger than I was hoping, sadly.

Try it online! (Note about the TIO: it includes an extra line `e*f` to map the output to ASCII digits. TIO also includes the verbose flag `-v`, which gives extra debug output via stderr.)

The first line produces a signal on only the first byte, allowing us to store that byte's bits, and to detect the empty string. (If we could give a truthy value for the empty string, -3 bytes.)

The last line deals with output, producing truthy only if the first and most recent bytes match, and if it isn't the first byte. Output is given one byte after the end of the input, with the help of `-z`. If not, we would be unable to detect the end of the string. (If we swapped truthy and falsey, -2 bytes, or if combined with empty string savings above, -4 for the both.)

The blob to the right, surrounding the `+`'s, is what triggers the end of input behavior. This actually looks for a zero byte, meaning that incorrect results may occur if one is given as input.

The remainder of the elements perform the actual comparison. This comparison performed is equivalent to, in C-ish: `!(input[0] xor input[n])`. In Chip, however, this must be performed for each bit individually, hence the eight sets of memory cells `m`, xor-gates `{`, and so on.

There is an interesting caveat to this implementation, in that it can handle 8 bits, but is unaware of unicode. So, effectively, this compares the first and last *bytes*, rather than *chars*.
> 1 votes

# Answer
# J, 12 bytes

```
'({.={:)*.*@#

```

`{.` means start, `=` means equals, and `{:` means end. `*.*@#` means "logical and with the length of the string", i.e., if the length is 0, it returns 0.
> 1 votes

# Answer
# Axiom, 30 bytes

```
f(a)==(#a=0=>false;a.1=a.(#a))

```

this below seems not to be ok

```
f(a)==(#a=0=>false;a.#a=a.1)

```
> 1 votes

# Answer
# TI-Basic (TI-84 Plus CE), 17 bytes

```
sub(Ans,1,1)=sub(Ans,length(Ans),1

```

Run with `"string":prgmNAME`. Returns 1 for true and 0 for false.
> 1 votes

# Answer
## Powershell, 30 bytes

```
"$args"|%{!($_[0]-$_[-1]+!$_)}

```

Try it online
> 1 votes

# Answer
# PowerShell, 25 Bytes

```
($a="$args")[0]-ceq$a[-1]

```

gets the first char and last char, performed a case-sensitive comparison of them.
> 1 votes

# Answer
# q/kdb+, ~~21~~ ~~20~~ 18 bytes

**Solution:**

```
{#:[x]&(1#x)~-1#x}

```

**Example:**

```
q){#:[x]&(1#x)~-1#x}"abc"
0
q){#:[x]&(1#x)~-1#x}"abca"
1
q){#:[x]&(1#x)~-1#x}""
0

```

**Explanation:**

Take the first and last elements of the list, check for equality (return boolean 1 or 0), then check length of string, return the minimum of these two results.

```
{                } / anonymous lambda function
             -1#x  / take (#) 1 item from end of list
       (1#x)       / take (#) 1 item from start of list
            ~      / are they equal
 #:[x]             / count (#:) length of list x
      &            / minimum

```
> 1 votes

# Answer
# Tcl, 34 bytes

```
proc C s {regexp ^(.)(.*\\1)?$ $s}

```

Try it online!
> 1 votes

# Answer
# Vim, 30 bytes

```
:s/\v^(.)(.*\1)?$/1
:s/^..\+/

```

Leaves you with `1`, if the string starts and ends with the same character, or nothing, if it doesn't.
> 1 votes

# Answer
# Julia 0.6, 29 bytes

```
f(x)=x==""?false:x[1]==x[end]

```

Try it online!
> 1 votes

# Answer
# Husk, 4 bytes

```
Γ·=→

```

Try it online!

Takes a string as an argument to the program, returns 0 for falsy cases and 1 for truthy cases.

# Explanation:

`Γ` is list deconstruction. The version I'm using (listN) takes a binary function and returns a function that takes a list. This new function returns the default type (0 in this case) for an empty string, and otherwise applies the given function to the head and tail of the string. The binary function I'm giving it is `=` (equality), composed on the second argument (`·`) with  (last element of a list).
> 1 votes

# Answer
# SmileBASIC 3, 36 bytes

In SmileBASIC, 0 is false and 1 (or nonzero) is true.

```
LINPUT S$L=LEN(S$)?L&&S$[0]==S$[L-1]

```

Explainer:

```
 LINPUT S$                'read line from console to string S$
 L=LEN(S$)                'store length of line in L
 ? L && S$[0] == S$[L-1]
'| |          |
'| |          \-----------first char equals last char
'| \----------------------length is false if zero, && shortcuts
'\------------------------print

```
> 1 votes

# Answer
# \>\<\>, 11 bytes

```
l?!<{:}=n;!

```

Try it online!

Takes input through the `-s` flag. You'll need to remove the flag for an empty input.

### How it works

```
l?!<  Go right if there is input, left is there is none
    {:  If there is input, rotate the stack and dupe the first element
        This creates two copies of a one character input
      }=n;  Print if the last character is equal to the first
l  If there is no input, push the length of the stack (0)
        n;!  Wrap around and print the 0

```
> 1 votes

# Answer
# Brachylog, 4 bytes

```
h.&t

```

Try it online!

and

# Brachylog, 4 bytes

```
h~t?

```

Try it online!

are both predicates which try to unify the first and last elements of the input, outputting through success or failure (which prints `true.` or `false.` when it's run as a program).
> 1 votes

# Answer
# GolfScript, 7 bytes

```
)\(@=\;

```

Try it online!

## Explanation

```
)       # The last character
 \(     # And the first character
   @=\; # Are they equal

```
> 1 votes

# Answer
# Burlesque, 6 bytes

```
l_-]==

```

Try it online!

```
l_ # Non-destructive tail, leaving the rest of the string on top of the stack
-] # Destructive head
== # Equal

```
> 1 votes

# Answer
# MAWP, <sup>~~21~~</sup> 29 bytes

```
|1A<1:.>1M\%_1A<1:.>\A{0:.}1:

```

Try it!

Fixed for empty input(and single character input, after Lyxal pointed out). If input is empty, it checks if the existing 1 on the stack is still at the top. then checks the length of the input.
> 1 votes

# Answer
# 05AB1E (legacy), 3 bytes

```
Ć`Q

```

Try it online or verify all test cases.

**Explanation:**

```
Ć    # Enclose the (implicit) input-string; append its own head
 `   # Pop and push all characters separated to the stack
  Q  # Check if the top/last two are the same
     # (after which the result is output implicitly)

```

The empty test case only works in the legacy version of 05AB1E, because `Q` on an empty stack and without input is apparently falsey. Whereas in the new version of 05AB1E an empty input is interpret as an empty string, in which case `""==""` is truthy.
> 1 votes

# Answer
# Vyxal, 3 bytes

```
Ṙ=h

```

Try it Online!

Input as a list of chars.
> 1 votes

# Answer
# Perl 5 \+ `-plF`, 15 bytes

This matches the char at the last index of `@F` (`$#F`) against the beginning of the string (`/^.../`) and sets `$_` to the result only if `$_` is truthy (non-empty).

```
$_&&=/^$F[$#F]/
```

Try it online!

---

# Perl 5 \+ `-plF/^.*(.)$/`, 11 bytes

If we abuse `-F` so that it will only include the final char, we can save four more bytes. The trailing `/x` is necessary as `@F` will contain two indices, empty string at `0` and the desired char at `1` which when interpolated results in a leading space.

```
$_&&=/^@F/x
```

Try it online!
> 1 votes

# Answer
# K (ngn/k), ~~16~~ ~~15~~ 10 bytes

```
{0^*|x=*x}

```

Try it online!

*-5 bytes thanks to ngn!*
> 1 votes

# Answer
# brev, 48 bytes

```
(as-list(fn(if(null? x)#f(eq?(car x)(last x)))))

```

Examples:

```
(map (as-list(fn(if(null? x)#f(eq?(car x)(last x)))))
     '("10h01"
       "Nothing"
       "Acccca"
       "eraser"
       "erase"
       "wow!"
       "wow"
       "H"
       ""))

```

The null check adds a lot!
> 1 votes

# Answer
# Go, ~~50~~ 49 bytes

```
func(s string)bool{return""<s&&s[0]==s[len(s)-1]}

```

Attempt This Online!

* -1 by @The Thonnu
> 1 votes

# Answer
# Japt , 5 bytes

```
©Î¶UÌ

```

Try it

```
©Î¶UÌ     :Implicit input of string U
©         :Logical AND with
 Î        :First character of U
  ¶       :Is equal to
   UÌ     :Last character of U
          :Implicit output as a Boolean

```
> 1 votes

# Answer
# Golang, 27 bytes

```
if n[0:1] == n[(len(n))-1:]

```

Full Program

```
package main
import (
    "fmt"
)
func f(x string) string {
    if x[0:1] == x[(len(x))-1:] {
        return "Truthy"
    } else {
        return "Falsey"
    }
}
func main() {
    var n string
    fmt.Scanf("%q", &n)
    fmt.Printf("%q", f(n))
}

```

Try it online!
> 0 votes

# Answer
# Cubix, 20 bytes

```
@O0UA?n\.\1.1\2ntc?U

```

Returns 0 for false and 1 for true.

Cubified:

```
    @ O
    0 U
A ? n \ . \ 1 .
1 \ 2 n t c ? U
    . .
    . .

```

explanation:

```
A - read in input as chars; so input of abc has the stack -1,99,98,97
? - turn left if negative (empty string), right if positive
if negative:
   0 - push 0
   U - left u-turn
   O - output as int
   @ - end program
if positive:
\ - reflect so we are moving to the right
2 - push 2
n - negate top of stack
t - pop top of stack, move that item from the bottom to the top; moves the last character to top of stack
c - xor
? - turn right if positive, go straight if negative
if 0:
   U - left U-turn
   1 - push 1
   \ - reflect so we point up
   O - output 1
   @ - end program
if positive
   n - negate
   \ - reflect
   n - negate
   ? - righthand turn
   0 - push 0
   U - lefthand U-turn
   O - output
   @ - end program

```

Try it online!

Watch it online
> 0 votes

# Answer
# Tcl, 59 bytes

```
proc C s {expr {[string in $s 0]==[string in $s e]&$s!=""}}

```

Try it online!
> 0 votes

# Answer
# C (gcc), 45 bytes

```
f(s,j)char*s;{for(j=*s;*s;s++);j=j&&j==*--s;}

```

Try it online!
> 0 votes

# Answer
# SmileBASIC, 29 bytes

```
DEF E S?S>""&&POP(S)==S[0]END

```

Pretty simple, but it's important that the `POP` is done *after* the first character is checked, so it will work on 1 character long strings.
> 0 votes

# Answer
# ActionScript 2.0, ~~49~~ 57bytes

```
function a(b){trace(b!=""?b.substr(0,1)==b.slice(-1):0);}

```

Old version (v) doesn't output false for "", but the new, longer version does.

```
function a(b){trace(b.substr(0,1)==b.slice(-1));}

```

I'm fairly sure this is the shortest way to do it, but...

The semicolon can be removed and it'll still compile in JPEXS.

This is a pretty simple function - if the argument is not "", output whether the (0, 1) substring of the argument (basically a way of getting the first character) is equal to the last character, obtained by slicing the string at its last character, otherwise 0. Tracing is shorter than returning.
> 0 votes

# Answer
# jq, 23 characters

(20 characters code + 3 characters command line option)

```
.>""and.[:1]==.[-1:]

```

Sample run:

```
bash-4.4$ jq -R '.>""and.[:1]==.[-1:]' <<< $'10h01\nNothing\nAcccca\nwow!\nwow\nH\n'
true
false
false
false
true
true
false

```

Try it online!

### jq, 25 characters

(22 characters code + 3 characters command line option)

```
endswith(.[:1])and.>""

```

Just to show that jq also has `endswith()` function. But unfortunately all strings are considered to end with empty string, so is not shorter. ☹
> 0 votes

# Answer
# MAWP 2.0, 28 bytes

```
=A|_!=W1-W0-*{`=M~M-{0=A}}A:

```

Try it!
> 0 votes

# Answer
# Ly, 6 bytes

```
i0I=u;

```

Try it online!

One caveat about this one... Ly can't detect null input, so it doesn't handle that use case.

```
i       - read STDIN onto the stack a codepoints
 0I     - copy the bottom of stack to the top
   =    - compare top two entries on the stack
    u   - print the result
     ;  - exit to avoid print the rest of the stack

```
> 0 votes

# Answer
# K (ngn/k), 12 bytes

```
{0^*(*x)=|x}

```

Try it online!

A port of @user41805's APL answer.

* `(*x)=|x` compare the first character of the input against each character of the reversed input
* `0^*` take the first value; `*emptyIntegerList` will return `0N`, which needs to be filled with `0` via `0^`
> 0 votes

# Answer
# Zsh, 13 bytes

```
>_$1<*${1[1]}
```

Attempt This Online!
> 0 votes

# Answer
## Regex `fullmatch` (Java / Boost / Python / PCRE2), ~~11~~ 9 bytes

```
(.).*\1|.

```

Try it online! / Attempt This Online! \- Java
Try it online! \- Boost
Try it online! / Attempt This Online! \- Python
Try it online! / Attempt This Online! \- PCRE2

Simple non-complicated regex. Would have been even less complicated if not for the fact that you had to match single char strings. Matches a string only if the first and last characters are equal.

```
(.).*\1|.  # The regex
     \1    # Does the last character equal...
(.)        # The first character?
   .*      # Allow anything in between
       |.  # Or match a string 1 character in length

```
> 0 votes

# Answer
# Jellyfish, 14 bytes

```
P
=<,1
v
, I
2

```

Try it online! (The input requires a trailing newline to handle the empty string case correctly.)

### Explanation

A straightforward solution would be 7 bytes if we didn't have to handle empty strings:

```
P
=<
vI

```

`I` inputs a string, which goes to both `<` (first element) and `v` (last element). The results of both of these functions go to `=`, and the comparison result gets printed by `P`.

However, `<` and `v` error when the string is empty, so we have to add some workarounds. Note that strings in Jellyfish are lists of characters, and lists can contain values with different data types.

```
<,1

 I

```

Append `1` to the input and take the first element: either a character, or `1` if the input was empty.

```
v
, I
2

```

Prepend `2` to the input and take the last element: either a character, or `2` if the input was empty.

```
P
=

```

Compare and print the result, as before.
> 0 votes

# Answer
# Dart, 38 bytes.

```
c(s)=>s.length>0&&s[0]==s[s.length-1];

```

Nothing amazing. Introducing a variable for `s.length` takes one character more. Splitting an empty string, or using `s.runes`/`s.charCodes`, gives an empty list, which needs special casing anyway.
> 0 votes

# Answer
# PHP, 46 bytes

```
$f=fn($x)=>fn($y)=>($x==$y&&($y!=""))?'T':'F';

```

Try it online!
> 0 votes

# Answer
# Stax, 6 bytes

```
¢₧/#HL

```

Run and debug it

This is a function which takes input as a string.

This is PackedStax which unpacks to the following 7 bytes:

```
%_:EE=I

```

Run and debug it

# Explanation

```
%     I # input length is > 0 and
 _:E    # input string first and last value
    E=  # are equal

```
> 0 votes

# Answer
# JavaScript, 30 bytes

```
i=>!!(i[0]===i[i.length-1]&&i);

```
> 0 votes

# Answer
# PowerShell, 32 bytes

```
if($a){return $a[0]-ceq$a[-1]}!1

```

Try it online!
> 0 votes

# Answer
# Regex (GNU ERE or better), 12 bytes

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

```

This regex was already used in the following answers, shown in chronological order:

1. eush77's 12 byte GNU grep answer (GNU ERE / PCRE)
2. Neil's edited 12 byte Retina answer (.NET)
3. Kevin Cruijssen's 29 byte Java 8 answer (Java)
4. Shaggy's edited 25 byte JavaScript answer (ECMAScript)
5. Tom Tanner's 28 byte Perl answer (Perl)
6. oktupol's 30 byte Vim answer (GNU ERE)
7. sergiol's edited 34 byte Tcl answer (Tcl ARE)

But here it is demonstrated in the form of a pure regex, in a wider variety of regex engines:

Try it online! / Attempt This Online! \- GNU ERE
Try it online! / Attempt This Online! \- Tcl ARE
Try it online! \- ECMAScript (SpiderMonkey)
Try it online! / Attempt This Online! \- ECMAScript 2018 (Node.js)
Try it online! / Attempt This Online! \- Perl
Try it online! / Attempt This Online! \- Java
Try it online! \- Boost
Try it online! / Attempt This Online! \- Python
Try it online! / Attempt This Online! \- Ruby
Try it online! / Attempt This Online! \- PCRE
Try it online! \- .NET

```
^       # Anchor to start of string
(.)     # \1 = Consume one character
(       # Begin grouped expression
    .*      # Skip any number of characters, minimum zero
    \1      # Consume a character if it matches the one captured in \1,
            # otherwise fail to match.
)?      # Evaluate the above group optionally; if it fails to match, it will
        # be skipped.
$       # Assert that we've reached the end of the string

```

See also Seggan's answer, in which a feature is used that is not present in all regex engines, allowing that regex to be just **9 bytes** (the regex is matched against only the entire string, and doesn't attempt substring matches).

# Regex (ECMAScript or better), 13 bytes

```
^(?=(.)).*\1$

```

Try it online! \- ECMAScript (SpiderMonkey)
Try it online! / Attempt This Online! \- ECMAScript 2018 (Node.js)
Try it online! / Attempt This Online! \- Perl
Try it online! / Attempt This Online! \- Java
Try it online! \- Boost
Try it online! / Attempt This Online! \- Python
Try it online! / Attempt This Online! \- Ruby
Try it online! / Attempt This Online! \- PCRE
Try it online! \- .NET

Doesn't beat the 12 byte version in golf or in range of compatibility (GNU ERE isn't supported due to lack of lookaheads, and Tcl ARE isn't supported due to lack of support for captures or backreferences inside lookaheads), but included anyway, to demonstrate another method that's rather elegant.

Already used in Neil's original 13 byte Retina answer before being edited down to 12 bytes.

```
^         # Anchor to start of string
(?=       # Lookahead
    (.)   # \1 = one character
)
.*        # Skip any number of characters, minimum zero (if more than zero
          # characters are skipped, the first of them will be the one captured
          # in the lookahead above)
\1        # Consume a character if it matches the one captured in \1,
          # otherwise fail to match.
$         # Assert that we've reached the end of the string

```
> 0 votes

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


title: We're gonna need a bigger podium!

text:
# Question
Title: We're gonna need a bigger podium!
If \\$R\\$ runners were to run a race, in how many orders could they finish such that exactly \\$T\\$ runners tie?

### Challenge

Given a positive integer \\$R\\$ and a non-negative integer \\$0\leq T\leq {R}\\$ produce the number of possible finishing orders of a race with \\$R\\$ runners of which \\$T\\$ tied.

Note, however, that runners that tie do not necessarily all tie with each other.

---

You may accept the number of runners that did not tie, \\$R-T\\$, in place of either \\$R\\$ or \\$T\\$ if you would prefer, just say so in your answer. You may also accept just \\$R\\$ and output a list of results for \\$0\leq T \leq R\\$.

This is , so try to make the shortest code in bytes in your language of choice.

---

### Examples

#### 1. \\$f(R=5, T=0)=120\\$

No runners tied and the five runners could have finished in any order, thus \\$f(R=5, T=0)=R!=5!=120\\$

#### 2. \\$f(R=5, T=1)=0\\$

There are zero ways for exactly one runner to have tied since ties involve at least two runners.

#### 3. \\$f(R=4, T=2)=36\\$

* The first two tied - `** * *` \- \\$\binom{4}{2}\binom{2}{1}\binom{1}{1}=6\times 2\times 1=12\\$ ways:
    + `AB C D` `AB D C`
    `AC B D` `AC D B`
    `AD B C` `AD C B`
    `BC A D` `BC D A`
    `BD A C` `BD C A`
    `CD A B` `CD B A`
* The middle two tied - `* ** *` \- \\$\binom{4}{1}\binom{3}{2}\binom{1}{1}=4\times 3\times 1=12\\$ ways:
    + `A BC D` `A BD C` `A CD B`
    `B AC D` `B AD C` `B CD A`
    `C AB D` `C AD B` `C BD A`
    `D AB C` `D AC B` `D BC A`
* The last two tied - `* * **` \- \\$\binom{4}{1}\binom{3}{1}\binom{2}{2}=4\times 3\times 1=12\\$ ways:
    + `A B CD` `A C BD` `A D BC`
    `B A CD` `B C AD` `B D AC`
    `C A BD` `C B AD` `C D AB`
    `D A BC` `D B AC` `D C AB`

#### 4. \\$f(R=5, T=5)=21\\$

* All five runners tied - `*****` \- \\$\binom{5}{5}=1\\$ way
* The first two and the last three tied - `** ***` \- \\$\binom{5}{2}\binom{3}{3}=10\times 1=10\\$ ways:
    + `AB CDE` `AC BDE` `AD BCE` `AE BCD` `BC ADE` `BD ACE` `BE ACD` `CD ABE` `CE ABD` `DE ABC`
* The first three and the last two tied - `*** **` \- \\$\binom{5}{3}\binom{2}{2}=10\times1=10\\$ ways:
    + `ABC DE` `ABD CE` `ABE CD` `ACD BE` `ACE BD` `ADE BC` `BCD AE` `BCE AD` `BDE AC` `CDE AB`

### Test cases

```
R,T => f(R,T)
1,0 => 1
1,1 => 0
2,0 => 2
2,1 => 0
2,2 => 1
3,0 => 6
3,1 => 0
3,2 => 6
3,3 => 1
4,0 => 24
4,1 => 0
4,2 => 36
4,3 => 8
4,4 => 7
5,0 => 120
5,1 => 0
5,2 => 240
5,3 => 60
5,4 => 100
5,5 => 21
7,5 => 5166

```

As a table, with `x` if the input does not need to be handled (all of them would be zero):

```
T R: 1     2     3     4     5     6     7
0    1     2     6    24   120   720  5040
1    0     0     0     0     0     0     0
2    x     1     6    36   240  1800 15120
3    x     x     1     8    60   480  4200
4    x     x     x     7   100  1170 13440
5    x     x     x     x    21   372  5166
6    x     x     x     x     x   141  3584
7    x     x     x     x     x     x   743

```

---

### Isomorphic problem

This is the same as \\$a(n=R,k=R-T)\\$ which is given in A187784 at the Online Encyclopedia of Integer Sequences as *the number of ordered set partitions of \\$\\{1,2,\dots,n\\}\\$ with exactly \\$k\\$ singletons*.

# Answer
> 7 votes
# MATL, ~~26~~ 24 bytes

```
xt:Z^!"@tufm?@&=sqz1G=vs

```

Inputs `T`, then `R`. The code takes a while for `R≥5`.

Try it online! You can also see the examples: , , , . Or verify test cases for `R≤4`.

### Explanation

The program consists of three major steps:

1. Generate all tuples of length `R` containing (possibly repeated) numbers from the set `[1, 2, ..., R]`.
2. Keep only those tuples such the tuple contains all numbers `[1, 2, ..., u]`, where `u` is the number of distinct elements in the tuple. So `[1 2 1]` would be kept, whereas `[1 3 1]` or `[2 3 2]` would be rejected.
3. For each tuple that survived the previous step, count how many of its `R` entries are equal to some other entry. Let this count be `e`. The output of the program is the amount of tuples for which `e` equals `T`.

# Answer
> 5 votes
# JavaScript (ES6), 88 bytes

Expects `(t)(r)`.

```
t=>F=(r,q=r-t,p=1,v=0)=>q|r?v+r&&F(r,q,p,--v)+F(r+v,q-!~v,(g=_=>v?(~r-v)/v++*g():p)()):p

```

Try it online!

### Algorithm

Starting with \\$q=r-t\\$ and \\$p=1\\$, we recursively look for all ordered integer partitions of \\$r\\$. Whenever a new term \\$v\\$ is added to a given partition \\$P\\$ of \\$r\\$:

* we multiply \\$p\\$ by the number of ways to choose \\$v\\$ racers among the remaining ones: $$p\gets p\times\binom{r}{v}$$
* we subtract \\$v\\$ from \\$r\\$
* we decrement \\$q\\$ if \\$v=1\\$

Once a valid partition \\$P\\$ is complete (ending with \\$r=0\\$), we test whether we also have \\$q=0\\$, meaning that there are \\$r-t\\$ singletons in the finishing order of the race, i.e. \\$t\\$ ties. If so, we add the product \\$p\\$ to the final result. Otherwise, we ignore this partition.

# Answer
> 4 votes
# PARI/GP, 46 bytes

```
f(r,t)=Vec(r!/(2-exp(x+O(x^t++))+x)^r-=t-2)[t]

```

Attempt This Online!

# Answer
> 4 votes
# , 105 bytes

(or 91 bytes in in R≥4.1 by exchanging `function` for `\`)

```
function(r,n)sum(apply(expand.grid(rep(list(1:r),r)),1,function(v)all(1:max(v)%in%v,sum(table(v)<2)==n)))

```

Attempt This Online!

Input is `r`=runners, `n`=non-tied finishers.

Port of Luis Mendo's answer: upvote that one!

---

# \+ `partitions`, 95 bytes

(or 81 bytes in R≥4.1 by exchanging `function` for `\`)

```
function(r,n)sum(apply(partitions::setparts(r),2,function(v)prod((sum(table(v)<2)==n):max(v))))

```

Try it at rdrr.io

Input is `r`=runners, `n`=non-tied finishers.

Lazily uses `partitions` library to gather all set partitions, selects those with `n` singleton sets, and sums the factorials of the number of sets in each partition to account for the number of possible orders.

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

```
LZãʒÐêāQi¢≠OQ]g

```

-6 bytes by porting *@LuisMendo*'s MATL answer, so make sure to upvote him as well!

Inputs in the order \\$R,T\\$.

Try it online or verify all test cases.

**Original 21 bytes answer:**

```
Lœ€.œ€`€€{Ùʒ€g1ÝKOQ}g

```

Inputs in the order \\$R,T\\$.

Brute-force, so pretty slow.

Try it online or verify all test cases.

**Explanation:**

```
L         # Push a list in the range [1, first (implicit) input-integer R]
 Zã       # Get the cartesian power of R, creating all possible lists of length R using
          # items of the [1,R]-ranged list, including duplicates
ʒ         # Filter this list of lists by:
 Ð        #  Triplicate the current list
  ê       #  Uniquify and sort the top list
   ā      #  Push a list in the range [1,length] (without popping the list)
    Q     #  Check if the top two lists are equal
 i        #  If this is truthy:
  ¢       #   Pop the remaining two lists, and get the count of each integer
   ≠      #   Check for each count whether it's NOT equal to 1
    O     #   Sum the amount of non-1 counts together
     Q    #   Check if this is equal to the second (implicit) input-integer T
          #  (implicit else: use the current list we've triplicated - which is falsey)
]         # Close both the if-statement and filter
 g        # Pop and push its length to get the amount of remaining valid lists
          # (which is output implicitly as result)

```

```
L         # Push a list in the range [1, first (implicit) input-integer R]
 œ        # Get all permutations of this list
  €       # Map over each permutation:
   .œ     #  Get all partitions of this permutation
     €`   # Flatten it one level down to a list of partitions
€         # Map over each partition:
 €        #  Inner map over each part in this partition:
  {       #   Sort the integers in the current part
   Ù      # After the nested map, uniquify the list of partitions with sorted parts
ʒ         # Filter the list of partitions by:
 €g       #  Get the length of each part
   1Ý     #  Push pair [0,1]
     K    #  Remove all 0s and 1s from the list of lengths
      O   #  Sum the remaining lengths (of >=2) together
       Q  #  Check whether this sum is equal to the second (implicit) input-integer `T`
}g        # After the filter: pop and push the length of the remaining partitions
          # (which is output implicitly as result)

```

# Answer
> 2 votes
# Charcoal, 55 bytes

```
⊞υＥ²¬ιＦＮ⊞υ⊞ＯＥ⁺²ιΣＥ∨κ¹×§§υ⁻ιμ⁻κ∧μ⊕μ÷Π⁻⊕ι…⁰⊕μΠ…·¹⊕μ⁰Ｉ§⊟υＮ

```

Try it online! Link is to verbose version of code. Takes \\$ R \\$ and \\$ T \\$ as parameters. Explanation: Using dynamic programming with a recurrence relation turned out to be a byte shorter than porting @DominicvanEssen's R + partitions answer.

```
⊞υＥ²¬ι

```

Start with \\$ f(0, 0) = 1 \\$ and \\$ f(0, 1) = 0 \\$.

```
ＦＮ

```

Loop \\$ R \\$ times.

```
⊞υ⊞ＯＥ⁺²ιΣＥ∨κ¹×§§υ⁻ιμ⁻κ∧μ⊕μ÷Π⁻⊕ι…⁰⊕μΠ…·¹⊕μ⁰

```

Calculate \\$ f(R, T) \\$ using the recurrence relation below and append an extra zero for \\$ f(R, R + 1) \\$.

$$ f(R, T) = R f(R - 1, T) + \sum _ { i = 2 } ^ T \binom R i f(R - i, T - i) $$

```
Ｉ§⊟υＮ

```

Output \\$ f(R, T) \\$.

# Answer
> 2 votes
# Nekomata \+ `-n`, 13 bytes

```
R↕J:ᵐo=ᵐ#←¬∑=

```

Attempt This Online!

Takes input as \\$R,R-T\\$.

Brute force. Very slow.

```
R↕J:ᵐo=ᵐ#←¬∑=
R                   Range from 1 to the first input (R)
 ↕                  Non-deterministically choose a permutation
  J                 Split the permutation into a list of lists
   :ᵐo=             Check if all the sublists are sorted
       ᵐ#←¬∑        Count the number of sublists with length 1
            =       Check if the number is equal to the second input (R-T)

```

`-n` counts the number of solutions.

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

```
SeriesCoefficient[1/(2-Exp@x+x-y*x),{x,0,R},{y,0,R-T}]*R!

```

Try it online!

Accroding to the question description, this is the same as \\$a(n=R,k=R-T)\\$ which is given in A187784 at the Online Encyclopedia of Integer Sequences as *the number of ordered set partitions of \\$\\{1,2,\dots,n\\}\\$ with exactly \\$k\\$ singletons*.

---
Tags: code-golf, math, combinatorics
---


title: Minimum Cut finder

text:
# Question
Title: Minimum Cut finder
Write a program that takes an undirected graph and finds the minimum cut, i.e., the set of edges that, if removed, would disconnect the graph into two or more connected components. The program should have a time complexity of \\$O(n^2m)\\$, where n is the number of vertices and m is the number of edges in the graph.

One algorithm to solve this problem is the Karger's algorithm, which is a randomized algorithm that finds the minimum cut with high probability. Here is a high-level overview of the algorithm:

1. Initialize a "contracted graph" that is a copy of the original graph.
2. While the contracted graph has more than 2 vertices:

1. Choose an edge at random from the contracted graph.
    2. Contract the two vertices connected by the chosen edge into a single vertex,
    3. removing the chosen edge.
    4. Repeat steps 1 and 2 until only 2 vertices remain.
3. The minimum cut is the set of edges that connect the two remaining vertices in the contracted graph.

This algorithm works by repeatedly contracting edges in the graph until only 2 vertices remain. The intuition behind the algorithm is that, as edges are contracted, the size of the cut decreases until there are only 2 vertices left, at which point the cut is the set of edges that connect those 2 vertices.

Karger's algorithm has a time complexity of \\$O(n^2m)\\$, which makes it relatively efficient for small to medium-sized graphs. However, it may not be practical for very large graphs.

# Answer
> 4 votes
# Python, 433 bytes,

```
import random

def karger_algorithm(graph):
    while len(graph) > 2:
        # Choose an edge at random
        u, v = random.choice(list(graph.items()))
        w = random.choice(v)

        # Contract the two vertices
        graph[u].extend(graph[w])
        for node in graph[w]:
            graph[node].remove(w)
            graph[node].append(u)
        del graph[w]

    # Return the size of the cut
    return len(list(graph.values())[0])

# Example usage
graph = {0: [1, 2], 1: [0, 2], 2: [0, 1, 3], 3: [2]}
min_cut = karger_algorithm(graph)
print(min_cut)

```

Attempt This Online!

---

This implementation uses a dictionary to represent the graph, where the keys are the vertices and the values are lists of adjacent vertices. The algorithm repeatedly chooses an edge at random, contracts the two vertices connected by the edge, and updates the adjacency lists accordingly. The function returns the size of the cut, which is the number of edges that were removed.

Note that this implementation is not optimized for performance and may be slow for large graphs. There are more efficient ways to implement Karger's algorithm, such as using Union-Find data structures to keep track of connected components.

# Answer
> 2 votes
A simple implementation of Karger's algorithm in Python using union-find.

```

import random

def min_cut(graph):
    edges = [(u, v) for u, l in graph.items() for v in l if v > u]
    parent = {u: u for u in graph}
    def find(u):
        v = parent[u]
        while v != u:
            w = parent[v]
            parent[u] = w
            u, v = v, w
        return u
    def union(u, v):
        if random.randrange(2):
            u, v = v, u
        parent[u] = v
    random.shuffle(edges)
    n_components = len(graph)
    if n_components < 2:
        return None
    if n_components > 2:
        for (u, v) in edges:
            fu, fv = find(u), find(v)
            if fu != fv:
               union(fu, fv)
               n_components -= 1
               if n_components == 2:
                    break
    return [(u, v) for (u, v) in edges if find(u) != find(v)]

```

# Answer
> 0 votes
# Rust

We can use Rust to implement Karger's algorithm, one example is:

run it on Rust Playground!

```
extern crate rand;
use rand::Rng;
use std::collections::HashMap;
use std::time::Instant;

fn karger_algorithm(graph: &mut HashMap<u32, Vec<u32>>) -> usize {
    while graph.len() > 2 {
        // 1. Randomly select an edge in a graph
        let keys: Vec<_> = graph.keys().cloned().collect();
        let u = rand::thread_rng().gen_range(0..keys.len());
        let u_key = keys[u];
        let v = rand::thread_rng().gen_range(0..graph[&u_key].len());
        let w_key = graph[&u_key][v];

        // 2. Contract the two vertices
        // Add all the neighbors of w to the Adjacency List of u,
        // Next, for all Adjacency Lists, w is replaced with u
        // Finally, delete the Adjacency List of w
        let w_key_values = graph[&w_key].clone();
        graph.get_mut(&u_key).unwrap().extend(w_key_values.clone());
        for node in w_key_values.iter() {
            let node_list = graph.get_mut(node).unwrap();
            node_list.retain(|x| *x != w_key);
            node_list.push(u_key);
        }
        graph.remove(&w_key);
    }

    // 3. Return the size of the cut
    // Finally, there are two remaining nodes, with some edges connected between them.
    // Returns the number of edges
    graph.values().next().unwrap().len()
}

fn karger_algorithm_montecarlo(graph: &mut HashMap<u32, Vec<u32>>, iterations: usize) -> usize {
    let mut min_cut = usize::max_value();
    for _ in 0..iterations {
        let mut graph_copy = graph.clone();
        let cut = karger_algorithm(&mut graph_copy);
        if cut < min_cut {
            min_cut = cut;
        }
    }
    min_cut
}

fn main() {
    let mut graph: HashMap<u32, Vec<u32>> = HashMap::new();
    graph.insert(0, vec![1, 2]);
    graph.insert(1, vec![0, 2]);
    graph.insert(2, vec![0, 1, 3]);
    graph.insert(3, vec![2]);

    let start = Instant::now();
    let min_cut = karger_algorithm_montecarlo(&mut graph, 500);
    let duration = start.elapsed();

    println!("Minimum cut: {}", min_cut);
    println!("Time elapsed: {:?}", duration);
}

```

Run the program with `iterations=500` and find that the minimum cut can be \\$1\\$

```
-----Standard Error-----
   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 0.88s
     Running `target/debug/playground`

-----Standard Output-----
Minimum cut: 1
Time elapsed: 8.640442ms

```

Its minimum cut is \\$1\\$, we can use Mathematica to verify that.

---
Tags: graph-theory, restricted-complexity, fastest-algorithm
---


# Question
Title: Count the number of cyclic words in an input
Cyclic Words

> Problem Statement
>
> We can think of a cyclic word as a word written in a circle. To represent a cyclic word, we choose an arbitrary starting position and read the characters in clockwise order. So, "picture" and "turepic" are representations for the same cyclic word.
>
> You are given a String\[\] words, each element of which is a representation of a cyclic word. Return the number of different cyclic words that are represented.

Fastest wins (Big O, where n = number of chars in a string)

# Answer
# Python

Here's my solution. I think it might still be O(n2), but I think the average case is much better than that.

Basically it works by normalizing each string so that any rotation will have the same form. For example:

```
'amazing' -> 'mazinga'
'mazinga' -> 'mazinga'
'azingam' -> 'mazinga'
'zingama' -> 'mazinga'
'ingamaz' -> 'mazinga'
'ngamazi' -> 'mazinga'
'gamazin' -> 'mazinga'

```

The normalization is done by looking for the minimum character (by char code), and rotating the string so that character is in the last position. If that character occurs more than once, then the characters after each occurrence are used. This gives each cyclic word a canonical representation, that can be used as a key in a map.

The normalization is n2 in the worst case (where every character in the string is the same, e.g. `aaaaaa`), but most of the time there's only going to be a few occurrences, and the running time will be closer to `n`.

On my laptop (dual core Intel Atom @ 1.66GHz and 1GB of ram), running this on `/usr/share/dict/words` (234,937 words with an average length of 9.5 characters) takes about 7.6 seconds.

```
#!/usr/bin/python

import sys

def normalize(string):
   # the minimum character in the string
   c = min(string) # O(n) operation
   indices = [] # here we will store all the indices where c occurs
   i = -1       # initialize the search index
   while True: # finding all indexes where c occurs is again O(n)
      i = string.find(c, i+1)
      if i == -1:
         break
      else:
         indices.append(i)
   if len(indices) == 1: # if it only occurs once, then we're done
      i = indices[0]
      return string[i:] + string[:i]
   else:
      i = map(lambda x:(x,x), indices)
      for _ in range(len(string)):                       # go over the whole string O(n)
         i = map(lambda x:((x[0]+1)%len(string), x[1]), i)  # increment the indexes that walk along  O(m)
         c = min(map(lambda x: string[x[0]], i))    # get min character from current indexes         O(m)
         i = filter(lambda x: string[x[0]] == c, i) # keep only the indexes that have that character O(m)
         # if there's only one index left after filtering, we're done
         if len(i) == 1:
            break
      # either there are multiple identical runs, or
      # we found the unique best run, in either case, we start the string from that
      # index
      i = i[0][0]
      return string[i:] + string[:i]

def main(filename):
   cyclic_words = set()
   with open(filename) as words:
      for word in words.readlines():
         cyclic_words.add(normalize(word[:-1])) # normalize without the trailing newline
   print len(cyclic_words)

if __name__ == '__main__':
   if len(sys.argv) > 1:
      main(sys.argv[1])
   else:
      main("/dev/stdin")

```
> 4 votes

# Answer
## Python (3) again

The method I used was to calculate a rolling hash of each word starting at each character in the string; since it's a rolling hash, it takes O(n) (where n is the word length) time to compute all the n hashes. The string is treated as a base-1114112 number, which ensures the hashes are unique. (This is similar to the Haskell solution, but more efficient since it only goes through the string twice.)

Then, for each input word, the algorithm checks its lowest hash to see if it's already in the set of hashes seen (a Python set, thus lookup is O(1) in the set's size); if it is, then the word or one of its rotations has already been seen. Otherwise, it adds that hash to the set.

The command-line argument should be the name of a file that contains one word per line (like `/usr/share/dict/words`).

```
import sys

def rollinghashes(string):
    base = 1114112
    curhash = 0
    for c in string:
        curhash = curhash * base + ord(c)
    yield curhash
    top = base ** len(string)
    for i in range(len(string) - 1):
        curhash = curhash * base % top + ord(string[i])
        yield curhash

def cycles(words, keepuniques=False):
    hashes = set()
    uniques = set()
    n = 0
    for word in words:
        h = min(rollinghashes(word))
        if h in hashes:
            continue
        else:
            n += 1
            if keepuniques:
                uniques.add(word)
            hashes.add(h)
    return n, uniques

if __name__ == "__main__":
    with open(sys.argv[1]) as words_file:
        print(cycles(line.strip() for line in words_file)[0])

```
> 3 votes

# Answer
# Mathematica

Decided to start again, now that I understand the rules of the game (I think).

A 10000 word dictionary of unique randomly composed "words" (lower case only) of length 3. In similar fashion other dictionaries were created consisting of strings of length 4, 5, 6, 7, and 8.

```
ClearAll[dictionary]
dictionary[chars_,nWords_]:=DeleteDuplicates[Table[FromCharacterCode@RandomInteger[{97,122},
chars],{nWords}]];
n=16000;
d3=Take[dictionary[3,n],10^4];
d4=Take[dictionary[4,n],10^4];
d5=Take[dictionary[5,n],10^4];
d6=Take[dictionary[6,n],10^4];
d7=Take[dictionary[7,n],10^4];
d8=Take[dictionary[8,n],10^4];

```

`g`takes the current version of dictionary to check. The top word is joined with cyclic variants (if any exist). The word and its matches are appended to the output list, `out`, of processed words. The output words are removed from the dictionary.

```
g[{wds_,out_}] :=
   If[wds=={},{wds,out},
   Module[{s=wds[[1]],t,c},
   t=Table[StringRotateLeft[s, k], {k, StringLength[s]}];
   c=Intersection[wds,t];
   {Complement[wds,t],Append[out,c]}]]

```

`f` runs through all words dictionary.

```
f[dict_]:=FixedPoint[g,{dict,{}}][[2]]

```

---

**Example 1**: actual words

```
r = f[{"teaks", "words", "spot", "pots", "sword", "steak", "hand"}]
Length[r]

```

> {{"steak", "teaks"}, {"hand"}, {"pots", "spot"}, {"sword", "words"}}
> 4

---

**Example 2**: Artificial words. Dictionary of strings of length 3. First, timing. Then the number of cycle words.

```
f[d3]//AbsoluteTiming
Length[%[[2]]]

```

> 5402

---

**Timings as a function of word length**. 10000 words in each dictionary.

I don't particularly know how to interpret the findings in terms of O. In simple terms, the timing roughly doubles from the three character dictionary to the four character dictionary. The timing increases almost negligibly from 4 through 8 characters.
> 1 votes

# Answer
## Haskell

Not sure about the efficiency of this, most likely rather bad. The idea is to first create all possible rotations of all the words, count the values that uniquely represent the strings and select the minimum. That way we get a number that is unique to a cyclic group.
We can group by this number and check the number of these groups.

If n is the number of words in the list and m is the length of a word then calculating the 'cyclic group number' for all the words is `O(n*m)`, sorting `O(n log n)` and grouping `O(n)`.

```
import Data.List
import Data.Char
import Data.Ord
import Data.Function

groupUnsortedOn f = groupBy ((==) `on` f) . sortBy(compare `on` f)
allCycles w = init $ zipWith (++) (tails w)(inits w)
wordval = foldl (\a b -> a*256 + (fromIntegral $ ord b)) 0
uniqcycle = minimumBy (comparing wordval) . allCycles
cyclicGroupCount = length . groupUnsortedOn uniqcycle

```
> 1 votes

# Answer
This can be done in O(n) avoiding quadratic time. The idea is to construct the full circle traversing the base string twice. So we construct "amazingamazin" as the full circle string to check all cyclic strings corresponding to "amazing".

Below is the Java solution:

```
public static void main(String[] args){
    //args[0] is the base string and following strings are assumed to be
    //cyclic strings to check
    int arrLen = args.length;
    int cyclicWordCount = 0;
    if(arrLen<1){
        System.out.println("Invalid usage. Supply argument strings...");
        return;
    }else if(arrLen==1){
        System.out.println("Cyclic word count=0");
        return;
    }//if

    String baseString = args[0];
    StringBuilder sb = new StringBuilder();
    // Traverse base string twice appending characters
    // Eg: construct 'amazingamazin' from 'amazing'
    for(int i=0;i<2*baseString.length()-1;i++)
        sb.append(args[0].charAt(i%baseString.length()));

    // All cyclic strings are now in the 'full circle' string
    String fullCircle = sb.toString();
    System.out.println("Constructed string= "+fullCircle);

    for(int i=1;i<arrLen;i++)
    //Do a length check in addition to contains
     if(baseString.length()==args[i].length()&&fullCircle.contains(args[i])){
        System.out.println("Found cyclic word: "+args[i]);
        cyclicWordCount++;
    }

    System.out.println("Cyclic word count= "+cyclicWordCount);
}//main

```
> 1 votes

# Answer
I don't know if this is very efficient, but this is my first crack.

```
private static int countCyclicWords(String[] input) {
    HashSet<String> hashSet = new HashSet<String>();
    String permutation;
    int count = 0;

    for (String s : input) {
        if (hashSet.contains(s)) {
            continue;
        } else {
            count++;
            for (int i = 0; i < s.length(); i++) {
                permutation = s.substring(1) + s.substring(0, 1);
                s = permutation;
                hashSet.add(s);
            }
        }
    }

    return count;
}

```
> 0 votes

# Answer
## Perl

not sure i understand the problem, but this matches the example @dude posted in the comments at least. please correct my surely incorrect analysis.

for each word W in the given N words of the string list, you have to step through all characters of W in the worst case. i have to assume the hash operations are done in constant time.

```
use strict;
use warnings;

my @words = ( "teaks", "words", "spot", "pots", "sword", "steak", "hand" );

sub count
{
  my %h = ();

  foreach my $w (@_)
  {
    my $n = length($w);

    # concatenate the word with itself. then all substrings the
    # same length as word are rotations of word.
    my $s = $w . $w;

    # examine each rotation of word. add word to the hash if
    # no rotation already exists in the hash
    $h{$w} = undef unless
      grep { exists $h{substr $s, $_, $n} } 0 .. $n - 1;
  }

  return keys %h;
}

print scalar count(@words), $/;

```
> 0 votes

# Answer
# Rust, brute force

run it on Rust Playground!

```
use std::collections::HashSet;
use std::time::Instant;

fn count_cyclic_words(input: &[&str]) -> usize {
    let mut hash_set = HashSet::new();
    let mut count = 0;

    for &s in input.iter() {
        if hash_set.contains(s) {
            continue;
        } else {
            count += 1;
            let mut permutation = String::from(s);
            for _ in 0..s.len() {
                permutation = format!("{}{}", &permutation[1..], &permutation[0..1]);
                hash_set.insert(permutation.clone());
            }
        }
    }

    count
}

fn main() {
    let test_cases = vec![
        vec!["abc", "cab", "bca"],
        vec!["aaa", "aaa", "aaa"],
        vec!["a", "b", "c"],
    ];

    for (i, input) in test_cases.iter().enumerate() {
        let start = Instant::now();
        let count = count_cyclic_words(input);
        let duration = start.elapsed();
        println!("Test case {}: count = {}", i + 1, count);
        println!("Time elapsed: {:?}", duration);
    }
}

```
> 0 votes

---
Tags: word-puzzle, counting, fastest-algorithm
---


# Question
Title: Edit distance where a substitution only costs the first time
This challenge is about the following variant of edit distance. Say we have a cost of 1 for inserts, deletes and substitutions as usual with one exception. A substitution for a given letter `x` for a letter `y` only costs `1` the first time. Any further substitutions of `x` for `y` cost 0.

As simple examples:

```
A = apppple
B = attttle

```

cost 1 (not 4) to transform A into B. This is because we change `p` for a `t` four times but we only charge for the first one.

```
A = apxpxple
B = atxyxtle

```

cost 2 (not 3) as the `p` to `t` substitution only costs 1 even though we do it twice.

```
A = apppple
B = altttte

```

cost 3. `p` -\> `l` costs 1. `p` -\> `t` costs 1 as does `l` -\> `t`.

If we assume the total length of the input is `n`, you must give the big O() of your algorithm. The best time complexity wins.

---

We should assume the alphabet size can be as large as `n`.

# Answer
> 2 votes
# Naive recursive algorithm \\$ O(\frac{(1+\sqrt2)^n}{\sqrt{n}}) \\$

The basic idea is try adding, removing and replacing one character and recursive.

```
def f(str1, str2):
  l1, l2 = len(str1), len(str2)
  mapping = set()
  def g(p1, p2):
    if l1 == p1 or l2 == p2:
      return l1 + l2 - p1 - p2
    cost1 = g(p1 + 1, p2) + 1
    cost2 = g(p1, p2 + 1) + 1
    if str1[p1] != str2[p2] and (str1[p1], str2[p2]) not in mapping:
      mapping.add((str1[p1], str2[p2]))
      cost3 = g(p1 + 1, p2 + 1) + 1
      mapping.discard((str1[p1], str2[p2]))
    else:
      cost3 = g(p1 + 1, p2 + 1)
    return min(cost1, cost2, cost3)
  return g(0, 0)

```

The function `g` will be invoked \\$ O(\frac{(1+\sqrt2)^n}{\sqrt{n}}) \\$ times<sup>\[1\]</sup>. While adding, discarding, or checking an element in the mapping cost \\$ O(1) \\$ on average.

\[1\]: Based on https://oeis.org/A027618 ; I don't know why actually...

# Answer
> 2 votes
Based on the Wagner–Fischer algorithm, each cell (here I just store a single row rather than the whole matrix) contains a list of tuples of edit distances and their associated transpositions. The matrix itself requires \\$ O(n^2) \\$ to traverse, but I don't know the cost of tracking the sets of transpositions, which varies across the grid roughly in line with Delannoy numbers. The code also merges distances with the same transpositions; I don't know whether that increases or reduces the complexity.

```
def dist(fr, to):
  costs = [[(i, frozenset())] for i in range(len(fr) + 1)]
  for j in range(len(to)):
    editcosts = costs[0]
    delcosts = costs[0] = [(costs[0][0][0] + 1, frozenset())]
    for i in range(len(fr)):
      inscosts = costs[i + 1]
      allcosts = [(c + 1, s) for c, s in delcosts + inscosts] + [(c, s) if fr[i] == to[j] or fr[i] + to[j] in s else (c + 1, s | {fr[i] + to[j]}) for c, s in editcosts]
      allcosts = [min((c, s) for c, s in allcosts if s == e) for e in {s for c, s in allcosts}]
      costs[i + 1] = allcosts
      editcosts = inscosts
      delcosts = allcosts
  return min(costs.pop())

print(dist("apxpxple", "atxyxtle"))

```

Try it online!

# Answer
> 2 votes
A\* Search, unknown complexity. Seems to at least achieve \\$o(2^{n})\\$ and is quite fast in practice. No reason to think it's optimal, but making it better seemed like too much work.

```
import collections
import heapq

def dist(s0, s1):
    l0, l1 = len(s0), len(s1)
    suffix_sets = tuple([frozenset(s[i:]) for i in range(len(s) + 1)] for s in (s0, s1))
    q = []
    def push_node(g, i, j, substs):
        suff0, suff1 = suffix_sets[0][i], suffix_sets[1][j]
        substs = frozenset(
            t for t in substs if t[0] in suff0 and t[1] in suff1
        )
        substs0, substs1 = {c0 for c0, _ in substs}, {c1 for _, c1 in substs}
        h0 = abs((l0 - i) - (l1 - j))
        h1 = max(len((suff0 - suff1) - substs0), len((suff1 - suff0) - substs1))
        h = max(h0, h1)
        heapq.heappush(q, (g + h, -g, -len(substs), i, j, substs))
    closed = collections.defaultdict(lambda: set())
    push_node(0, 0, 0, frozenset())
    while True:
        (f, neg_g, _, i, j, substs) = heapq.heappop(q)
        g = -neg_g
        if (i == l0) or (j == l1):
            return f
        closed_ij = closed[(i, j)]
        if (g, substs) in closed_ij:
            continue
        subsumed = False
        for (g1, substs1) in closed_ij:
            if g1 <= g and substs.issubset(substs1):
                subsumed = True
                break
        if subsumed:
            continue
        if substs:
            closed_ij.add((g, substs))
        c0, c1 = s0[i], s1[j]
        if (c0 == c1) or ((c0, c1) in substs):
            push_node(g, i + 1, j + 1, substs)
            continue
        push_node(g + 1, i + 1, j, substs)
        push_node(g + 1, i, j + 1, substs)
        push_node(g + 1, i + 1, j + 1, substs | frozenset([(c0, c1)]))

```

# Answer
> 1 votes
I worked a bit more on this, against my better judgement :). A\* search, more complicated than my other answer.

```
import collections
import heapq
import itertools

class SubsumptionTrie:
    def __init__(self):
        self.max_len = 0
        self.min_v = float('inf')
        self.children = {}
    def insert(self, k, v, i=0):
        self.max_len = max(self.max_len, len(k) - i)
        self.min_v = min(self.min_v, v)
        if i >= len(k):
            return
        c = k[i]
        if c not in self.children:
            self.children[c] = SubsumptionTrie()
        self.children[c].insert(k, v, i + 1)
    def subsumption_test(self, k, v, i=0):
        if i >= len(k):
            return self.min_v <= v
        if (self.min_v > v) or (self.max_len < (len(k) - i)):
            return False
        c = k[i]
        for b, child in self.children.items():
            if b < c and self.children[b].subsumption_test(k, v, i):
                return True
        if c in self.children:
            return self.children[c].subsumption_test(k, v, i + 1)
        return False

def heuristic(s0, s1, n0, n1, substs):
    substs0 = {a for a, _ in substs} | set(s1.keys())
    substs1 = {b for _, b in substs} | set(s0.keys())
    if n0 > n1:
        s0, s1 = s1, s0
        n0, n1 = n1, n0
        substs0, substs1 = substs1, substs0
    h0 = 0
    m1 = sum(n for c, n in s1.items() if c in substs1)
    for c, n in sorted(s0.items(), key=lambda t: t[1]):
        if (c not in substs0) or (m1 < 0):
            h0 += 1
        else:
            m1 -= n
    h1 = 0
    for c, n in sorted(s1.items(), key=lambda t: (t[0] in substs1, t[1]), reverse=True):
        n0 -= n
        if n0 < 0:
            excess = min(-n0, n)
            h1 += excess
            n -= excess
        if n and (c not in substs1):
            h1 += 1
    return max(h0, h1)

def dist(s0, s1):
    labels = itertools.count()
    relabel = collections.defaultdict(lambda: next(labels))
    s0, s1 = [relabel[c] for c in s0], [relabel[c] for c in s1]
    label_count = next(labels)
    l0, l1 = len(s0), len(s1)
    suffix_counts = tuple([collections.Counter(s[i:]) for i in range(len(s) + 1)] for s in (s0, s1))
    q = []
    def push_node(g, i, j, substs):
        suff0, suff1 = suffix_counts[0][i], suffix_counts[1][j]
        substs = frozenset(
            t for t in substs if t[0] in suff0 and t[1] in suff1
        )
        h = heuristic(suff0, suff1, l0 - i, l1 - j, substs)
        heapq.heappush(q, (g + h, -g, -len(substs), i, j, substs))
    push_node(0, 0, 0, frozenset())
    closed = collections.defaultdict(lambda: SubsumptionTrie())
    while True:
        (f, neg_g, _, i, j, substs) = heapq.heappop(q)
        g = -neg_g
        if (i == l0) or (j == l1):
            return f
        closed_ij = closed[(i, j)]
        k = sorted(a * label_count + b for a, b in substs)
        if closed_ij.subsumption_test(k, g):
            continue
        closed_ij.insert(k, g)
        c0, c1 = s0[i], s1[j]
        if (c0 == c1) or ((c0, c1) in substs):
            push_node(g, i + 1, j + 1, substs)
            continue
        push_node(g + 1, i + 1, j + 1, substs | frozenset(((c0, c1),)))
        push_node(g + 1, i + 1, j, substs)
        push_node(g + 1, i, j + 1, substs)

```

# Answer
> 1 votes
# Rust

Port of @tsh's answer

run it on Rust Playground!

```
use std::cmp;
use std::collections::HashSet;
use std::time::Instant;

fn f(str1: &str, str2: &str) -> usize {
    let mut mapping = HashSet::new();

    fn g(p1: usize, p2: usize, str1: &str, str2: &str, mapping: &mut HashSet<(char, char)>) -> usize {
        let l1 = str1.len();
        let l2 = str2.len();

        if l1 == p1 || l2 == p2 {
            return l1 + l2 - p1 - p2;
        }

        let cost1 = g(p1 + 1, p2, str1, str2, mapping) + 1;
        let cost2 = g(p1, p2 + 1, str1, str2, mapping) + 1;

        let c1 = str1.chars().nth(p1).unwrap();
        let c2 = str2.chars().nth(p2).unwrap();

        let cost3 = if c1 != c2 && !mapping.contains(&(c1, c2)) {
            mapping.insert((c1, c2));
            let cost = g(p1 + 1, p2 + 1, str1, str2, mapping) + 1;
            mapping.remove(&(c1, c2));
            cost
        } else {
            g(p1 + 1, p2 + 1, str1, str2, mapping)
        };

        cmp::min(cost1, cmp::min(cost2, cost3))
    }

    g(0, 0, str1, str2, &mut mapping)
}

fn main() {
    let test_cases = [
        ("apppple", "attttle", 1),
        ("apxpxple", "atxyxtle", 2),
        ("apppple", "altttte", 3),
    ];

    for (a, b, expected) in test_cases.iter() {
        let start = Instant::now();
        let result = f(a, b);
        let duration = start.elapsed();
        println!("A: {}, B: {}, Output: {}, Expected: {}", a, b, result, expected);
        println!("Time elapsed: {:?}", duration);
    }
}

```

---
Tags: fastest-algorithm, edit-distance
---


title: Heaviest increasing subsequence

text:
# Question
Title: Heaviest increasing subsequence
A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. A strictly increasing subsequence is a subsequence in which every element is bigger than the preceding one.

The heaviest increasing subsequence of a sequence is the strictly increasing subsequence that has the biggest element sum.

Implement a program or function in your language of choice that finds the element sum of the heaviest increasing subsequence of a given list of non-negative integers.

Examples:

```
                    [] ->  0 ([])
                   [3] ->  3 ([3])
             [3, 2, 1] ->  3 ([3])
          [3, 2, 5, 6] -> 14 ([3, 5, 6])
       [9, 3, 2, 1, 4] ->  9 ([9])
       [3, 4, 1, 4, 1] ->  7 ([3, 4])
       [9, 1, 2, 3, 4] -> 10 ([1, 2, 3, 4])
       [1, 2, 4, 3, 4] -> 10 ([1, 2, 3, 4])
[9, 1, 2, 3, 4, 5, 10] -> 25 ([1, 2, 3, 4, 5, 10])
       [3, 2, 1, 2, 3] ->  6 ([1, 2, 3])

```

Note that you only have to give the element sum of the heaviest increasing subsequence, not the subsequence itself.

---

The asymptotically fastest code wins, with smaller code size in bytes as a tiebreaker.

# Answer
> 3 votes
# javascript (ES6) `O(n log n)` 253 characters

```
function f(l){l=l.map((x,i)=>[x,i+1]).sort((a,b)=>a[0]-b[0]||1)
a=[0]
m=(x,y)=>x>a[y]?x:a[y]
for(t in l)a.push(0)
t|=0
for(j in l){for(i=(r=l[j])[1],x=0;i;i&=i-1)x=m(x,i)
x+=r[0]
for(i=r[1];i<t+2;i+=i&-i)a[i]=m(x,i)}for(i=t+1;i;i&=i-1)x=m(x,i)
return x}

```

this uses fenwick trees (a maximum fenwick tree) to find maxima of certain subsequences.

basically, in the underlying array of the datatype, each place is matched with an element from the input list, in the same order. the fenwick tree is initialized with 0 everywhere.

from the smallest to the biggest, we take an element from the input list, and look for the maximum of the elements to the left. they are the elements that may be before this one in the subsequence, because they are to the left in the input sequence, and are smaller, because they entered the tree earlier.

so the maximum we found is the heaviest sequence that can get to this element, and so we add to this the weight of this element, and set it in the tree.

then, we simply return the maximum of the whole tree is the result.

tested on firefox

# Answer
> 4 votes
# Python, O(n log n)

I didn't golf this, because I'm competing primarily on the fastest code side of things. My solution is the `heaviest_subseq` function, and a test harness is also included at the bottom.

```
import bisect
import blist

def heaviest_subseq(in_list):
    best_subseq = blist.blist([(0, 0)])
    for new_elem in in_list:

        insert_loc = bisect.bisect_left(best_subseq, (new_elem, 0))

        best_pred_subseq_val = best_subseq[insert_loc - 1][1]

        new_subseq_val = new_elem + best_pred_subseq_val

        list_len = len(best_subseq)
        num_deleted = 0

        while (num_deleted + insert_loc < list_len
               and best_subseq[insert_loc][1] <= new_subseq_val):
            del best_subseq[insert_loc]
            num_deleted += 1

        best_subseq.insert(insert_loc, (new_elem, new_subseq_val))

    return max(val for key, val in best_subseq)

tests = [eval(line) for line in """[]
[3]
[3, 2, 1]
[3, 2, 5, 6]
[9, 3, 2, 1, 4]
[3, 4, 1, 4, 1]
[9, 1, 2, 3, 4]
[1, 2, 4, 3, 4]
[9, 1, 2, 3, 4, 5, 10]
[3, 2, 1, 2, 3]""".split('\n')]

for test in tests:
    print(test, heaviest_subseq(test))

```

Runtime analysis:

Each element has its insertion position looked up once, is inserted once, and is possibly deleted once, in addition to a constant number of value lookups per loop. Since I am using the built-in bisect package and the blist package, each of those operations are `O(log n)`. Thus, the overall runtime is `O(n log n)`.

The program works by maintaining a sorted list of best possible increasing subsequences, represented as a tuple of ending value and sequence sum. An increasing subsequence is in that list if there are no other subsequences found so far whose ending value is smaller and sum is at least as large. These are maintained in increasing order of ending value, and necessarily also in increasing order of sum. This property is maintained by checking the successor of each newly found subsequence, and deleting it if its sum is not large enough, and repeating until a subsequence with a larger sum is reached, or the end of the list is reached.

# Answer
> 2 votes
# Python, O(n log n)

I used an index transform and a nifty data structure (binary indexed tree) to trivialize the problem.

```
def setmax(a, i, v):
    while i < len(a):
        a[i] = max(a[i], v)
        i |= i + 1

def getmax(a, i):
    r = 0
    while i > 0:
        r = max(r, a[i-1])
        i &= i - 1
    return r

def his(l):
    maxbit = [0] * len(l)
    rank = [0] * len(l)
    for i, j in enumerate(sorted(range(len(l)), key=lambda i: l[i])):
        rank[j] = i

    for i, x in enumerate(l):
        r = rank[i]
        s = getmax(maxbit, r)
        setmax(maxbit, r, x + s)

    return getmax(maxbit, len(l))

```

The binary indexed tree can do two operations in log(n): increase a value at index i and get the maximum value in \[0, i). We initialize every value in the tree to 0. We index the tree using the rank of elements, not their index. This means that if we index the tree at index i, all elements \[0, i) are the elements smaller than the one with rank i. This means that we get the maximum from \[0, i), add the current value to it, and update it at i. The only issue is that this will include values which are less than the current value, but come later in the sequence. But since we move through the sequence from left-to-right and we initialized all values in the tree to 0, those will have a value of 0 and thus not affect the maximum.

# Answer
> 1 votes
# Python 2 - `O(n^2)` \- 114 bytes

```
def h(l):
 w=0;e=[]
 for i in l:
    s=0
    for j,b in e:
     if i>j:s=max(s,b)
    e.append((i,s+i));w=max(w,s+i)
 return w

```

# Answer
> 1 votes
# C++ - `O(n log n)` \- 261 bytes

Should be fixed now:

```
#include <set>
#include <vector>
int h(std::vector<int>l){int W=0,y;std::set<std::pair<int,int>>S{{-1,0}};for(w:l){auto a=S.lower_bound({w,-1}),b=a;y=prev(a)->second+w;for(;b!=S.end()&&b->second<=y;b++){}a!=b?S.erase(a,b):a;W=y>W?y:W;S.insert({w,y});}return W;}

```

# Answer
> 0 votes
# Python, O(2n), 91 bytes

This is more for fun than to be competitive. An arcane recursive solution:

```
h=lambda l,m=0:l and(h(l[1:],m)if l[0]<=m else max(h(l[1:],m),l[0]+h(l[1:],l[0])))or 0

```

# Answer
> 0 votes
## Matlab, *O*(*n* 2*n*), 90 bytes

```
function m=f(x)
m=0;for k=dec2bin(1:2^numel(x)-1)'==49
m=max(m,all(diff(x(k))>0)*x*k);end

```

Examples:

```
>> f([])
ans =
     0
>> f([3])
ans =
     3
>> f([3, 2, 5, 6])
ans =
    14

```

# Answer
> 0 votes
# Rust ,\\$\mathcal{O}(n \log n)\\$

Port of @isaacg's answer

run it on Rust Playground!

```
use std::cmp::Ordering;

fn heaviest_subseq(in_list: &[i32]) -> i32 {
    let mut best_subseq = vec![(0, 0)];

    for new_elem in in_list {
        let insert_loc = match best_subseq
            .binary_search_by(|&(key, _)| if key < *new_elem { Ordering::Less } else { Ordering::Greater })
        {
            Ok(index) => index,
            Err(index) => index,
        };

        let best_pred_subseq_val = best_subseq[insert_loc - 1].1;

        let new_subseq_val = new_elem + best_pred_subseq_val;

        let mut num_deleted = 0;

        while num_deleted + insert_loc < best_subseq.len() && best_subseq[insert_loc].1 <= new_subseq_val {
            best_subseq.remove(insert_loc);
            num_deleted += 1;
        }

        best_subseq.insert(insert_loc, (*new_elem, new_subseq_val));
    }

    best_subseq.into_iter().map(|(_, val)| val).max().unwrap()
}

fn main() {
    let tests = [
        &[][..],
        &[3][..],
        &[3, 2, 1][..],
        &[3, 2, 5, 6][..],
        &[9, 3, 2, 1, 4][..],
        &[3, 4, 1, 4, 1][..],
        &[9, 1, 2, 3, 4][..],
        &[1, 2, 4, 3, 4][..],
        &[9, 1, 2, 3, 4, 5, 10][..],
        &[3, 2, 1, 2, 3][..],
    ];

    for test in &tests {
        println!("{:?} {:?}", test, heaviest_subseq(test));
    }
}

```

---
Tags: code-golf, fastest-algorithm, subsequence
---