title: Is it a sum-free set?

text:
# Question
Title: Is it a sum-free set?
A set is sum-free if no two (not necessarily distinct) elements when added together are part of the set itself.

For example, `{1, 5, 7}` is sum-free, because all members are odd, and two odd numbers when added together are always even. On the other hand, `{2, 4, 9, 13}` is not sum-free, as either `2 + 2 = 4` or `4 + 9 = 13` add together to a member of the set.

Write a program or function that takes a set as input, and outputs a Truthy value if the set is sum-free, and Falsy otherwise.

Examples:

```
Sum-free:
{}
{4}
{1, 5, 7}
{16, 1, 4, 9}

Not sum-free:
{0}
{1, 4, 5, 7}
{3, 0}
{16, 1, 4, 8}

```

# Answer
# Pyth - ~~8~~ 5 bytes

*Thanks to @FryAmTheEggman for saving me 3 bytes.*

```
!@sM*

```

Test Suite.

```
!             Logical not. This makes the empty intersection true and vice versa.
 @    Q       Setwise intersection with input (implictly).
  sM          Map sum to all the pairs.
   *QQ        Get all pairs by doing cartesian product with input*input (implicit).

```
> 14 votes

# Answer
# Python 2, 41 bytes

```
lambda s:s==s-{a+b for a in s for b in s}

```

`s` should be a Python set.

Fun fact: `sum-free` is an anagram of my name.
> 42 votes

# Answer
# Jelly, 5 bytes

```
ṗ3ḅ-P

```

Try it online!

### How it works

```
ṗ3ḅ-P  Main link. Argument: A (array)

ṗ3     Take the third Cartesian power of A, i.e., generate all triplets that
       consist of elements of A.
  ḅ-   Convert each triplet from base -1 to integer.
       This maps [a, b, c] to a - b + c = (a + c) - b.
       If (a + c) belong to A, this will yield 0 for some b.
    P  Take the product of all resulting integers.

```
> 28 votes

# Answer
# JavaScript, ~~86~~ ~~42~~ 41 bytes

```
n=>!n.some(m=>n.some(o=>n.includes(m+o)))

```

Thanks Cᴏɴᴏʀ O'Bʀɪᴇɴ for saving me a ton of bytes off parentheses/curly brackets. Also thanks Neil for pointing out that the function was returning the opposite boolean value than it should have.

I tried to cut down on bytes by redefining `n.some` but that doesn't work because it's a prototype function unfortunately. There might be a better solution with `Array.prototype.map` in JS but the some function is really fun.

I'm now wondering if there's a shorter way than `.includes` using something such as .indexOf and adding 1 (which would give it a truthy value if it contains the number).

---

Testing:

```
> (n=>!n.some(m=>n.some(o=>n.includes(m+o))))([1,5,7]);
true
> (n=>!n.some(m=>n.some(o=>n.includes(m+o))))([1,5,7,12]);
false

```
> 14 votes

# Answer
# MATL, 5 bytes

```
t&+m~

```

This outputs an array which is truthy if all entries are `1` and falsey otherwise. Here is a demo to show various truthy/falsey values in MATL.

**Try it Online**

**Explanation**

```
        % Implicitly grab input
t       % Duplicate
&+      % Compute sum of each element with every other element (2D Matrix)
m       % Check which members of the input are present in this matrix of sums
~       % Negate the result to yield a truthy value for sum-free sets
        % Implicitly display truthy/falsey value

```
> 12 votes

# Answer
# Mathematica, 23 Bytes

```
{}==#⋂Tr/@#~Tuples~2&

```
> 12 votes

# Answer
# Haskell, ~~32~~, 30 bytes

Simple solution:

```
f x=and[a+b/=c|a<-x,b<-x,c<-x]

```

Two bytes saved by @Lynn
> 11 votes

# Answer
# J, ~~18~~ ~~10~~ 8 bytes

8 bytes saved thanks to miles, and 2 thanks to FrownyFrog!

```
-:]-.+/~

```

Matches the original list with the set difference of tabulated sums. This is equivalent to:

```
(-: (] -. +/~)) y

```

for input `y`. This translates to:

```
y -: (] -. +/~) y
y -: (y -. +/~ y)

```

`+/~` returns a table of sums using `y`. For `y =: 16 1 4 9`, this gives:

```
   +/~ 16 1 4 9
32 17 20 25
17  2  5 10
20  5  8 13
25 10 13 18

```

Then, we use `-.`, which produces a list consisting of all elements in `y` not in this table. If the list is sum-free, this will produce the same list. Then, `-:` checks for equality of lists, which produces the desired output.

## Old, 18 bytes

```
[:-.[:>./^:_+/~e.]

```

`+/~` creates a table of the values of the set added to itself, and `e.` checks if those members are in the original set. The rest of that is negating the maximal element.
> 8 votes

# Answer
# Julia, 18 bytes

```
!x=x∩(x'.+x)==[]

```

Try it online!
> 7 votes

# Answer
## Retina, ~~45~~ 44 bytes

```
\d+
<$&$*1>
$
$`$`
M`(<1*)>.*<(1*>).*\1\2
^0

```

Input is a decimal list of comma-separated numbers. Output is `0` (falsy) or `1` (truthy).

Try it online! (The first line enables a linefeed-separated test suite.)

### Explanation

**Stage 1: Substitution**

```
\d+
<$&$*1>

```

This converts all elements of the input to unary and wraps them in `<...>`. The purpose of the angle brackets is to distinguish a list containing only `0` from an empty list (since the unary representation of `0` is empty itself).

**Stage 2: Substitution**

```
$
$`$`

```

We repeat the string 3 times by append it twice at the end.

**Stage 3: Match**

```
M`(<1*)>.*<(1*>).*\1\2

```

We now try to find three numbers in the result such that the first two add up to the third. Those matches are counted (this doesn't actually count all such tuples, because matches cannot overlap, but if such a tuple exists it will be found). Hence, we get `0` for sum-free sets and something positive otherwise.

**Stage 4: Match**

```
^0

```

Since the previous stage gave the opposite of what we want, we negate the result by counting the matches of `^0` which is `1` for input `0` and `0` for everything else.
> 5 votes

# Answer
# Clojure, ~~47~~ 37 bytes

```
#(=(for[a % b % :when(%(+ a b))]a)[])

```

quite plain solution. uses list comprehension to find all elements which sum is equal to another element.

38 bytes variant:

```
#(every? nil?(for[a % b %](%(+ a b))))

```
> 5 votes

# Answer
# Octave, ~~29~~ ~~21~~ 25 bytes

```
@(s)~[ismember(s,s+s') 0]

```

Thanks to Suever! It returns an array. I added `0` at the end to make `[]` become sum-free. To verify truthy and falsey in Octave, you can do this:

```
> f=@(s)~[ismember(s,s+s') 0]

> if f([]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([0]) "sum-free" else "not sum-free" end
ans = not sum-free

> if f([4]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([1 3]) "sum-free" else "not sum-free" end
ans = sum-free

> if f([2 4]) "sum-free" else "not sum-free" end
ans = not sum-free

```

An alternative that returns 0 or 1 is:

```
@(s)~numel(intersect(s+s',s))

```
> 5 votes

# Answer
# Ruby, 36 bytes

Constructs a cartesian product of the set against itself and finds the sum of all elements, then checks for intersection with the original set. Input is arrays, but in Ruby they have enough set operations to make it work out nicely anyways.

-1 byte over my original solution (used `&` instead of `-` and compared with `[]`) because of inspiration from @feersum

Try it here!

```
->s{s-s.product(s).map{|x,y|x+y}==s}

```
> 4 votes

# Answer
# Mathematica ~~63 62~~ 42 bytes

This shorter version benefitted from A Simmons' submission. No element needs to be removed from the list before `IntegerPartitions` is applied.

If an element cannot be partitioned into two integers (each from the list), then `IntegerPartitions[#,{2},#]=={}` holds. `And` checks whether this holds for every element in the list. If so, the list is sum-free.

```
And@@(IntegerPartitions[#,{2},#]=={}&/@#)&

```

---

## Examples

```
 And@@(IntegerPartitions[#,{2},#]=={}&/@ #)&@{2, 4, 9, 13}

```

False

---

```
 And@@(IntegerPartitions[#,{2},#]=={}&/@ #)&@{1, 5, 7}

```

True

---

There is a 2, but no odd numbers that differ by 2.

```
 And@@(IntegerPartitions[#,{2},#]=={}&/@#)&@{2, 3, 7, 11, 17, 23, 29, 37, 41, 47, 53, 59, 67, 71}

```

True
> 4 votes

# Answer
# R, ~~39~~ 36 bytes

```
w<-function(s)!any(outer(s,s,'+')%in%s)

```

Call as `w(s)`, where `s` is the set (actually vector) of values. Here is the output for some test cases:

```
> w(numeric(0)) # The empty set
[1] TRUE
> w(0)
[1] FALSE
> w(1)
[1] TRUE
> w(c(1, 5, 7))
[1] TRUE
> w(c(2, 4, 9, 13))
[1] FALSE

```

Where `c()` is the concatenation function that takes a bunch of values and makes it a vector.

EDIT: Making it an anonymous function to save 3 bytes, thanks to @MickyT.

```
function(s)!any(outer(s,s,'+')%in%s)

```
> 4 votes

# Answer
# Perl 6,  ~~24 21 20~~  19 bytes

```
~~{not any (@_ X+@_)X==@_}
{so all (@_ X+@_)X!==@_}
{not @_ (&)(@_ X+@_)}
{not @_∩(@_ X+@_)}~~

{!(@_∩(@_ X+@_))}
```

Input is any Positional value like a List.
( a Set is an Associative so you would have to call `.keys` on it. )

### Test:

```
#! /usr/bin/env perl6
use v6.c;
use Test;

my @sum-free = (
  (),
  (4,),
  (1, 5, 7),
  (16, 1, 4, 9),
);

my @not-sum-free = (
  (0,),
  (1, 4, 5, 7),
  (3, 0),
  (16, 1, 4, 8),
);

my @tests = ( |(@sum-free X=> True), |(@not-sum-free X=> False) );

plan +@tests;

# store the lambda in lexical namespace for clarity
my &sum-free-set = {!(@_∩(@_ X+@_))}

for @tests -> $_ ( :key(@list), :value($expected) ) {
  is sum-free-set(@list), $expected, .gist
}

```

```
1..8
ok 1 - () => True
ok 2 - (4) => True
ok 3 - (1 5 7) => True
ok 4 - (16 1 4 9) => True
ok 5 - (0) => False
ok 6 - (1 4 5 7) => False
ok 7 - (3 0) => False
ok 8 - (16 1 4 8) => False

```
> 4 votes

# Answer
# Racket, 58 bytes

```
(λ(l)(andmap(λ(m)(andmap(λ(n)(not(memq(+ n m)l)))l))l))

```

Explanation:

```
(λ(l)(andmap(λ(m)(andmap(λ(n)(not(memq(+ n m)l)))l))l))
(λ(l)                                                 ) # Define a lambda function that takes in one parameter
     (andmap(λ(m)                                  )l)  # If for all m in l
                 (andmap(λ(n)                   )l)     # If for all n in l
                             (not(memq(+ n m)l))        # n + m is not in l

```
> 3 votes

# Answer
# 05AB1E, ~~9~~ 5 bytes

Saved 4 bytes thanks to *Magic Octopus Urn*

```
ãOå_P

```

Try it online!

**Explanation**

```
ã       # cartesian product
 O      # sum
  å     # check each if it exists in input
   _    # logical negation
    P   # product

```
> 3 votes

# Answer
# Brachylog, 13 bytes

```
'(p:?+L:?x'L)

```

### Explanation

```
'(          )  True if what's in the parentheses is impossible, false otherwise
  p            Get a permutation of Input
   :?+L        L is the list of element-wise sums of the permutation with Input
       :?x'L   There is at least one element of Input in L

```
> 3 votes

# Answer
# Python, 40 bytes

```
lambda s:s^{a+b for a in s for b in s}>s

```

`^` = symmetric difference, new set with elements in either sets but not both

`>` True if the left set is a superset of the right set.
> 3 votes

# Answer
# APL, 8 bytes

```
⊢≡⊢~∘.+⍨

```

Explanation:

```
⊢         argument
 ≡        equals
  ⊢       argument
   ~      without
    ∘.+⍨  sums of its elements

```

Test:

```
      ( ⊢≡⊢~∘.+⍨ ) ¨ (1 5 7)(2 4 9 13)
1 0

```
> 2 votes

# Answer
## Haskell, 30 bytes

```
f s=and[x+y/=z|x<-s,y<-s,z<-s]

```

I think there exists a shorter solution that's more interesting, but I haven't found it.

These are 33 and 34 bytes:

```
f s=and$((/=)<$>s<*>)$(+)<$>s<*>s
f s|q<-((-)<$>s<*>)=all(/=0)$q$q$s

```
> 2 votes

# Answer
# Actually, 7 bytes

```
;;∙♂Σ∩Y

```

Try it online!

```
;;∙♂Σ∩Y              Stack: [1,5,7]
;         duplicate         [1,5,7] [1,5,7]
 ;        duplicate         [1,5,7] [1,5,7] [1,5,7]
  ∙       cartesian product [1,5,7] [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]]
   ♂Σ     sum each          [1,5,7] [2,6,8,6,10,12,8,12,14]
     ∩    intersect         []
      Y   negate            1

```
> 2 votes

# Answer
## Java, 67 bytes

```
s->!s.stream().anyMatch(p->s.stream().anyMatch(q->s.contains(p+q)))

```

Input is a `Set<Integer>`. Tests:

```
import java.util.Arrays;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;

public class SumFree {
    public static void main(String[] args) {
        sumFree(s->!s.stream()
            .anyMatch(p->s.stream()
                .anyMatch(q->s.contains(p+q)))); // formatted to avoid wrapping
    }

    public static void sumFree(Function<Set<Integer>, Boolean> func) {
        test(func);
        test(func, 4);
        test(func, 1, 5, 7);
        test(func, 16, 1, 4, 9);
        test(func, 1, 4, 5, 7);
        test(func, 0);
        test(func, 3, 0);
        test(func, 16, 1, 4, 8);
    }

    public static void test(Function<Set<Integer>, Boolean> func, Integer... vals) {
        Set<Integer> set = Arrays.stream(vals).collect(Collectors.toSet());
        System.out.format("%b %s%n", func.apply(set), set);
    }
}

```

Output:

```
true []
true [4]
true [1, 5, 7]
true [16, 1, 4, 9]
false [0]
false [1, 4, 5, 7]
false [0, 3]
false [16, 1, 4, 8]

```
> 2 votes

# Answer
# Vyxal, 30 bits1, 3.75 bytes

```
ẊṠ↔¬

```

Try it Online!

```
Ẋ    # cartesian product with itself
 Ṡ   # vectorized sums
  ↔  # intersection of this with the input
   ¬ # logical NOT

```

If inverted truthiness is allowed, the `¬` can be removed for 2.875 bytes, but the challenge specifically states "*outputs a Truthy value if the set is sum-free, and Falsy otherwise.*"
> 2 votes

# Answer
# PHP, 73 bytes

+8 to turn the snippet into a program, -8 on obsolete variables thanks to insertusernamehere

```
<?foreach($argv as$p)foreach($argv as$q)if(in_array($p+$q,$argv))die;echo 1;

```

prints `1` for `true`, empty output for `false`
usage: `php <filename> <value1> <value2> ...`

qualified function for testing (~~94~~ 86): returns `1` or nothing

```
function f($a){foreach($a as$p)foreach($a as$q)if(in_array($p+$q,$a))return;return 1;}

```

**tests**

```
function out($a){if(!is_array($a))return$a;$r=[];foreach($a as$v)$r[]=out($v);return'['.join(',',$r).']';}
function cmp($a,$b){if(is_numeric($a)&&is_numeric($b))return 1e-2<abs($a-$b);if(is_array($a)&&is_array($b)&&count($a)==count($b)){foreach($a as $v){$w = array_shift($b);if(cmp($v,$w))return true;}return false;}return strcmp($a,$b);}
function test($x,$e,$y){static $h='<table border=1><tr><th>input</th><th>output</th><th>expected</th><th>ok?</th></tr>';echo"$h<tr><td>",out($x),'</td><td>',out($y),'</td><td>',out($e),'</td><td>',cmp($e,$y)?'N':'Y',"</td></tr>";$h='';}
$samples = [
    [], 1,
    [0], false,
    [1], 1,
    [0,1], false,
    [2, 4, 9, 13], false,
    [1,5,7], 1
];
while($samples)
{
    $a=array_shift($samples);
    $e=array_shift($samples);
    test($a,$e,f($a));
}

```
> 1 votes

# Answer
# TSQL, 47 bytes

```
CREATE table T(a int)
INSERT T values(1),(5),(7),(12)

SELECT min(iif(a.a+b.a<>T.a,1,0))FROM T a,T b,T

```

Note: This will only run once, then the table needs to be deleted or dropped to run again. The fiddle editor doesn't allow creation of tables. Therefore the fiddle included in my answer uses 2 extra bytes to compensate for this - the fiddle version doesn't require cleanup.

**Fiddle**
> 1 votes

# Answer
# Perl, 46 bytes

45 bytes code + 1 byte command line (-p)

```
$_="$_ $_ $_"!~/(\b\d++.*)((?1))(??{$1+$2})/

```

Uses a single regex match with Perl's support for 'code expressions' inside the regex to allow for evaluation within a match.

To get around the requirement that the input is unsorted, we repeat the input string three times. This guarantees that the result is after the two operands, and allows the same digit to be matched again (e.g. in the case of input `2 4`).

Usage example:

```
echo "3 5 6 8" | perl -p entry.pl

```
> 1 votes

# Answer
# Factor, 47 bytes

```
[ dup dup 2array [ Σ ] product-map ∩ { } = ]

```
* `∩ { } =` is equivalent to but shorter than `intersects?`.
* `Σ` is shorter than but equivalent to `sum`.

Thanks, math.unicode!

testing code:

```
USING: arrays kernel math.unicode sequences sequences.product ;
IN: sum-free

: sum-free? ( seq -- ? )
  dup dup 2array [ Σ ] product-map ∩ { } = ;

USING: tools.test sum-free ;
IN: sum-free.tests

{ t } [ { 5 7 9 } sum-free? ] unit-test
{ f } [ { 2 4 9 13 } sum-free? ] unit-test
{ t } [ { } sum-free? ] unit-test
{ f } [ { 0 } sum-free? ] unit-test
{ t } [ { 1 } sum-free? ] unit-test
{ f } [ { 0 1 } sum-free? ] unit-test

```

I'm only confident the first two are correct. It's unclear from the question what the rest should be, so I think it's fine for now.
> 1 votes

# Answer
## Clojure, 34 bytes

```
#(not-any? %(for[i % j %](+ i j)))

```

I wrote this before noticing the earlier Clojure solution. Anyway, this one is more compact as it uses the input set as a `pred` function for `not-any?`.
> 1 votes

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

```
âOмQ

```

Try it online or verify all test cases.

**Explanation:**

```
â       # Take all pairs of the input-list
        #  i.e. [1,5,7] → [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]]
        #  i.e. [1,4,5] → [[1,1],[1,4],[1,5],[4,1],[4,4],[4,5],[5,1],[5,4],[5,5]]
 O      # Sum all pairs
        #  i.e. [[1,1],[1,5],[1,7],[5,1],[5,5],[5,7],[7,1],[7,5],[7,7]]
        #    → [2,6,8,6,10,12,8,12,14]
        #  i.e. [[1,1],[1,4],[1,5],[4,1],[4,4],[4,5],[5,1],[5,4],[5,5]]
        #    → [2,5,6,5,8,9,6,9,10]
  м     # Remove all values in the input-list that are also in the list above
        #  i.e. [1,5,7] and [2,6,8,6,10,12,8,12,14] → ['1','5','7']
        #  i.e. [1,4,5] and [2,5,6,5,8,9,6,9,10] → ['1','4','']
   Q    # Is the current list still equal to the input-list?
        #  i.e. [1,5,7] and ['1','5','7'] → 1
        #  i.e. [1,4,5] and ['1','4',''] → 0

```
> 1 votes

# Answer
# Prolog (SWI), ~~66~~ ~~56~~ 49 bytes

```
A/B:-member(A,B).
-L:- \+ (E/L,F/L,G is E+F,G/L).

```

Try it online!
> 1 votes

# Answer
# Husk, ~~8 7~~ 6 bytes

```
¬Sn´×+

```

Try it online!

-1 byte from Zgarb.

Same method as the Pyth solution.

## Explanation

```
¬Sn´×+ implicit input
   ´   double: ´ f x = f x x
    ×+ map sum to all pairs
 S     hook: S f g x = f x (g x)
  n    intersection of sums with input
¬      negate

```
> 1 votes

# Answer
# Scala 3, ~~52~~ 37 bytes

Saved 15 bytes using lambda function.

---

```
s=>s==s.diff(for{a<-s;b<-s}yield a+b)

```

Attempt This Online!
> 1 votes

# Answer
# Thunno 2 `!`, 3 bytes

```
Ṗʂȯ

```

Try it online!

#### Explanation

```
Ṗʂȯ  # Implicit input
Ṗ    # Cartesian product
 ʂ   # Sum each
  ȯ  # Set intersection
     # Logical NOT
     # Implicit output

```
> 1 votes

# Answer
# PowerShell 50 bytes

```
param($a)$a|%{$b=$_;$a|%{if($b+$_-in$a){1;break}}}

```

Where 1 is true and no output is false.

Though, if outputting multiple truthy values is allowed, then I could save 6 bytes:

```
param($a)$a|%{$b=$_;$a|%{if($b+$_-in$a){1}}}

```

But I will wordsmith myself and agree that the OP asked for '**a** Truthy value'

Explanation:

```
param($a)$a|%{$b=$_;$a|%{if($b+$_-in$a){1;break}}}
param($a)                                          # assigns first passed parameter to variable $a
         $a|${                                   } # foreach $_ in $a
              $b=$_;                               # assign $_ to $b for access from further down the pipe
                    $a|%{                       }  # foreach $_ in $a
                         if($b+$_-in$a){       }   # if $a contains the value $b+$_
                                        1;         # implicit output of 1 (true)
                                          break    # exit the loops

```
> 0 votes

# Answer
# Japt `-!`, 9 bytes

```
ø¡UË+XÃÃc

```

Try it online!

### Unpacked & How it works

```
UøUmX{UmD{D+X} } c

Uø  Does the input array have any common element with...
UmX{  the input array mapped with...
UmD{    the input array mapped with...
D+X       sum of the two elements
}
}
c     ... flattened

```

The result is the opposite of what is requested, so `-!` flag is used to flip `true` and `false`.
> 0 votes

# Answer
# Cjam, 10 bytes

```
__m*::+&!!

```

Not very golfed. If someone can help me shave off more bytes, please help!

Explanation:

```
__         Duplicate the list twice
  m*       Take the Cartesian Product of the two
    ::+    For every item in the list (which is a list in this case), sum the elements
       &   Take the intersection with the original list
        !! Logical-not twice; take the "truthness" of the value

```
> 0 votes

# Answer
# Japt `-!`, 4 bytes

```
øUï+

```

Try it here
> 0 votes

# Answer
# Arturo, 37 bytes

```
$->a->¬some? a'x->some? a=>[in?+x&a]

```

Try it
> 0 votes

# Answer
# \[Matlab\] 38 bytes

assuming a is the input array (in form of a=\[1 3 5\]

```
sum(sum(ismember(diff(perms(a)),a)))>0

```
> 0 votes

# Answer
# Nekomata \+ `-e`, 5 bytes

```
ᵒ+j∕=

```

Attempt This Online!

```
ᵒ+       Addition table
  j      Flatten
   ∕     Set minus
    =    Check equality

```
> 0 votes

# Answer
# JavaScript (V8), 41 bytes

```
f=(x,p,q)=>x.every(t=>1/q?p+q-t:f(x,t,p))

```

Try it online!
> 0 votes

# Answer
# C (clang), 66 bytes

```
i;f(*a,n,*r){*r=1;for(i=n*n*n;i--;)*r&=a[i/n%n]+a[i%n]!=a[i/n/n];}

```

Try it online!
> 0 votes

---
Tags: code-golf, decision-problem, arithmetic, set-theory
---


title: Output a string's cumulative slope

text:
# Question
Title: Output a string's cumulative slope
## Challenge

Given a string such as `Hello World!`, break it down into its character values: `72, 101, 108, 108, 111, 32, 87, 111, 114, 108, 100, 33`.

Then calculate the difference between each consecutive pair of characters: `29, 7, 0, 3, -79, 55, 24, 3, -6, -8, -67`.

Finally, sum them and print the final result: `-39`.

## Rules

* Standard loopholes apply
* No using pre-made functions that perform this exact task
* Creative solutions encouraged
* Have fun
* This is marked as , the shortest answer in bytes wins but will not be selected.

# Answer
# Python, 29 bytes

```
lambda s:ord(s[-1])-ord(s[0])

```

The sum of the differences forms a telescopic series, so most summands cancel out and
**(s1 \- s0) + (s2 \- s1) + … + (sn-1 \- sn-2) + (sn \- sn-1) = sn \- s0**.

If taking a byte string as input is allowed

```
lambda s:s[-1]-s[0]

```

will work as well for **19 bytes**.

Test both on Ideone.
> 40 votes

# Answer
# MATL, 2 bytes

```
ds

```

Try it online!

Explanation:

`d` gets the difference between consecutive characters and `s` sums the resulting array. Then, the value on top of the stack is implicitly printed. Not much else to say about that.

Interestingly enough, even though Dennis discovered an awesome shortcut, using it would be significantly longer in MATL.
> 21 votes

# Answer
# Jelly, 3 bytes

```
OIS

```

Try it online!

Take the `O`rdinals of the input string’s characters, then the `I`ncrements of that list, then the `S`um of *that* list.
> 9 votes

# Answer
# MATLAB, 16 bytes

```
@(x)sum(diff(x))

```

This creates an anonymous function named `ans` which can be called like: `ans('Hello world!')`.

Here is an online demo in Octave which requires an additional byte `+` to explicitly convert the input string to a numeric array prior to computing the element-to-element difference
> 6 votes

# Answer
# Python, 63 bytes

```
x=map(ord,input())
print sum(map(lambda(a,b):b-a,zip(x,x[1:])))

```

Ideone it!
> 4 votes

# Answer
# Cubix, 13 bytes

Cubix is a 2-dimensional language wrapped around a cube.

```
i?u//O-t#;/.@

```

**Test it online!** This maps to the following cube net:

```
    i ?
    u /
/ O - t # ; / .
@ . . . . . . .
    . .
    . .

```

Where the IP (instruction pointer) starts at the top-left of the far-left face.

### How it works

First, the IP hits the mirror `/` which redirects it onto the `i` on the top face. The top face is a loop which continually inputs charcodes until EOF is reached. When the input is empty, the result of `i` is -1; the IP turns left from the `?`, hitting the `/` on the far right face and going through the following commands:

* `;` \- Pop the top item (-1).
* `#` \- Push the length of the stack.
* `t` \- Pop the top item and get the item at that index in the stack. This pulls up the bottom item.
* `-` \- Subtract.
* `O` \- Output as an integer.
* `/` \- Deflects the IP to the `@`, which ends the program.
> 4 votes

# Answer
## Ruby, 23 bytes

```
->s{s[-1].ord-s[0].ord}

```

Assign to a variable like `f=->s{s[-1].ord-s[0].ord}` and call like `f["Hello World!"]`

Uses Dennis's observation about telescopic series.
> 3 votes

# Answer
# C#, 22 bytes

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

```

Full source code with test case:

```
using System;

namespace StringCumulativeSlope
{
    class Program
    {
        static void Main(string[] args)
        {
            Func<string,int>f= s=>s[s.Length-1]-s[0];
            Console.WriteLine(f("Hello World!"));
        }
    }
}

```

# C# with LINQ, 17 bytes

A shorter version, using LINQ, thanks to hstde:

```
s=>s.Last()-s[0];

```

However, an extra import is necessary:

```
using System.Linq;

```
> 3 votes

# Answer
## JavaScript ES6, ~~42~~ 39 Bytes

```
f=
     s=>s[x='charCodeAt'](s.length-1)-s[x]();
;

console.log(f.toString().length);      // 39
console.log(f('Hello World!'))         // -39
```

Using @Dennis observation about telescope sums.

~~I think in this case the trivial solution is the shortest.~~

Saved 3 bytes by getting rid of th the `charCodeAt` repetition as suggested by @Neil.
> 3 votes

# Answer
# reticular, 12 bytes

```
idVc~@qVc-o;

```

Try it online!

Using Dennis's observation, we can shorten an iterative process into a simpler one.

```
idVc~@qVc-o;
i             take input
 d            duplicate
  V           pop input copy, push last character
   c          get its char code
    ~         put it under the input in the stack
     @q       reverse the item at the top of the stack
       V      get the last item of that (first item of input)
        c     convert to char
         -    subtract
          o   output
           ;  and terminate

```
> 2 votes

# Answer
# Brain-Flak, 51 bytes

48 bytes of code plus three bytes for the `-a` flag, which enables ASCII input (but decimal output. How convenient. :D)

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

```

Try it online!

This ones a *little* bit harder than my other answer, haha. Lets walk through it.

```
{           While the top of the stack is nonzero:
 (            Push:
  [{}]          The top of the stack times negative one. Pop this off.
  ({})          Plus the value on top of the stack, which is duplicated to save for later.
  <>          On to the other stack
 )
 <>         Move back to the first stack
}
<>          After the loop, move back again.
{}          We have one extra element on the stack, so pop it
([]<>)      Push the height of the alternate stack back onto the first stack
{           While the top of the stack is nonzero:
 ({}[()])     Decrement this stack
 <>           Move back to the alternate stack
 ({}{})       Sum the top two elements
 <>           Move back tothe first stack
}
<>          Switch back to the stack holding the sum

```
> 2 votes

# Answer
# 05AB1E, 3 bytes

```
Ç¥O

```

**Try it Online!**

Uses CP-1252 encoding.

**Explanation**

```
Ç       Converts input string to ASCII
¥       Compute difference between successive elements
O       Sum the result

```
> 2 votes

# Answer
# NodeJS, 82 bytes

```
x=process.argv[2],a=[],t=0;for(y in x)a[y]=x.charCodeAt(y),t+=y!=0?a[y]-a[y-1]:0

```

Explanation:

```
x = process.argv[2] // Get the input
a=[], // Initializes an array to store the differences' values.
t=0;  // Initializes a variable to store the total of the differences
for(y in x) // Iterates over the string as an array of characters
    a[y]=x.charCodeAt(y) // Transforms the input into an array of integers
    t+=y!=0?a[y]-a[y-1]:0 // Add the difference of the last two characters, except at the first iteration

```

# JavaScript, 79 bytes

```
f=x=>{a=[],t=0;for(y in x)a[y]=x.charCodeAt(y),t+=y!=0?a[y]-a[y-1]:0;return t}

```

Same idea as above with a function input instead of an argument.
> 2 votes

# Answer
# Brachylog, 7 bytes

```
@c$)@[-

```

Try it online!

### Explanation

```
@c        Convert "Hello World!" to [72,101,108,108,111,32,87,111,114,108,100,33]
  $)      Circular permute right: [33,72,101,108,108,111,32,87,111,114,108,100]
    @[    Take a prefix of the list
      -   Subtract

```

Since subtract only works for an input of two integers, it will succeed once the selected prefix is `[33, 72]`.
> 2 votes

# Answer
## R, 69 43 32 bytes

A very non-competing answer although I thought it'd be fun to showcase a possible solution in R.

```
sum(diff(strtoi(sapply(strsplit(readline(),"")[[1]],charToRaw),16L)))

```

The only interesting aspect of this answer is the use of `sapply`and `charToRaw`. First I split the string into a vector of characters that I want to convert into its ASCII integer representations. The `charToRaw` function is not vectorized in R and instead of looping over each value in aforementioned vector I use `sapply` which effectively vectorizes the function. Subsequently take 1st difference and then sum.

---

Edit: Turns out `charToRaw` transform a string into a vector where each element is the raw representation of each character, hence no need to use `strsplit` and `sapply`

```
sum(diff(strtoi(charToRaw(readline()),16)))

```

Edit2: Turns out there is an even better way, the function `utf8ToInt(x)` does exactly what `strtoi(charToRaw(x),16)` which means we can save a few more bytes (Idea taken from @rturnbull's answer to another question):

```
sum(diff(utf8ToInt(readline())))

```
> 2 votes

# Answer
# Haskell, 32 bytes

```
g=fromEnum
f t=g(last t)-g(t!!0)

```
> 2 votes

# Answer
# PHP 7.1, ~~33~~ 31 bytes

Uses negative string offsets implemented in PHP 7.1.

```
echo ord($argn[-1])-ord($argn);

```

Run like this:

```
echo 'Hello World!' | php -nR 'echo ord($argn[-1])-ord($argn);';echo

```

# Tweaks

* Saved 2 bytes by using `$argn`
> 2 votes

# Answer
# Perl, 19 bytes

Includes +1 for `-p`

Give input on STDIN ***without final newline***

```
echo -n "Hello World!" | slope.pl; echo

```

`slope.pl`:

```
#!/usr/bin/perl -p
$_=-ord()+ord chop

```

If you are sure the input string has at least 2 characters this 17 byte version works too:

```
#!/usr/bin/perl -p
$_=ord(chop)-ord

```
> 2 votes

# Answer
# Forth, 28 bytes

```
: f depth 1- roll swap - . ;

```

Takes a list of characters on the stack (Forth's standard method of taking parameters.) The characters are taken such that the top of the stack is the first character of the string. I move the bottom of the stack to the top, swap, then subtract and print. Garbage is left on the stack, and output is printed to stdout.

If each character were pushed to the stack in order instead of reverse order, the program would be 2 bytes shorter. Not sure if that's allowed, though, because normally you push arguments in reverse order.

**Try it online**

Called like this:

```
33 100 108 114 111 87 32 111 108 108 101 72 f

```
> 2 votes

# Answer
# Java, 42

```
int f(char[]c){return c[c.length-1]-c[0];}

```

Ungolfed:

```
  int f(char[] c) {
    return c[c.length - 1] - c[0];
  }

```

Explanation:

This uses the same principle as telescoping:

```
sum =
  c[4] - c[3]
+        c[3] - c[2]
+               c[2] - c[1]
+                      c[1] - c[0]
= c[4]                      - c[0]

```

Generalized for any sequence of characters of length `n`, the answer is `c[n-1] - c[0]` because all the stuff in the middle cancels out.
> 2 votes

# Answer
# RProgN, 142 Bytes, Non-competing

```
function tostack 'b' asoc stack 'a' asoc 0 'v' asoc b pop byte 'o' asoc b len while [ v o b pop byte ] 'o' asoc - + 'v' asoc b len end [ v end

```

Non-competing, as the 'tostack' command was added after the discovery of this challenge (even though it has a terrible byte count)

# Test Cases

```
Hello, World!
-39

Cool, huh?
-4

```

# Explanation

```
function                        # Push the function between this and end to the stack
    tostack 'b' asoc            # Convert the implicit input to a stack, associate it with 'b'
    0 'v' asoc                  # Push 0 to the stack, associate it with 'v'
    b pop byte 'o' asoc         # Pop the top value of b (The end of the input), get the byte value, associate it with 'o'.
    b len                       # Push the size of b to the stack
    while [                     # While the top of the stack is truthy, pop the top of the stack
        v                       # Push v to the stack
            o                   # Push o to the stack
            b pop byte          # Pop the top value of b, push the byte value of that to the stack
            ] 'o' asoc          # Push a copy of the top of the stack, associate it with 'o'
            -                   # Subtract the top of the stack from one underneith that, In this case, the old value of o and the byte.
        +                       # Sum the top of the stack and underneith that, that is, the difference of the old value and new, and the total value
        'v' asoc                # Associate it with 'v'
        b len                   # Push the size of b to the stack (which acts as the conditional for the next itteration)
    end [                       # Pop the top of the stack, which will likely be the left over size of b
    v                           # Push the value of v to the top of the stack
end                             # Implicitely returned / printed

```

RProgN is an esoteric language I've been working on with Reverse Polish Notation in mind. It's currently pretty verbose, with it's variable assignment being 4 characters, and such, however I plan to in future add a bit of syntatic sugar.

Also, RProgN implicitly accesses arguments from the stack, and returns them the same way. Any string data left in the stack after the program has finished, is implicitly printed.
> 1 votes

# Answer
# Haskell, 36 bytes

```
sum.(tail>>=zipWith(-)).map fromEnum

```

usage:

```
Prelude> (sum.(tail>>=zipWith(-)).map fromEnum)"Hello World!"
-39

```

# Haskell (Lambdabot), 31 bytes

```
sum.(tail>>=zipWith(-)).map ord

```
> 1 votes

# Answer
# PHP, 36 bytes

```
<?=ord(strrev($s=$argv[1]))-ord($s);

```
* Every character but the first and the last are added and substracted once each.
→ sum of differences == difference between first and last character
* `ord()` in PHP operates on the first character of a string
→ no need to explicitly reduce it to a single character
> 1 votes

# Answer
# Brain-Flak, ~~34~~ 32 + 3 = 35 bytes

+3 because of the `-a` flag required for ascii mode.

Try it online

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

```

Strangely it is more efficient to actually use the definition used in the specs rather than the "trick" of subtracting first from last.

This works by doing exactly that.

```
(                           )  Push
 ([][()]){[{}]...([][()])}     While the stack has more than one item
  [{}]({})                     Subtract the top from a copy of the second
                          <>   Switch

```
> 1 votes

# Answer
# CJam, ~~8~~ 5 bytes

*Big thanks to Dennis for two suggestions that removed 3 bytes*

```
l)\c-

```

Try it online!

### Explanation

Computes last value minus first value.

```
l        e# Read line as a string
 )       e# Push original string except last char, then last char
  \      e# Swap
   c     e# Convert to char: gives the first element of the string
    -    e# Subtract. Implicitly display

```
> 1 votes

# Answer
# Zsh, 22 bytes

```
c=${1[-1]}
<<<$[#1-#c]

```

Try it online!

In arithmetic mode, `#name` gets the character code of the first character in `name`. We set `c` to the last character, and take the difference between the first and last codes.
> 1 votes

# Answer
# Seed, 4039 bytes

Doesn't seem to work on TIO, but it works when coupled with FBBI.

```
14 8414852681982816833433372790810698364813132893898716362540459584022688625798264387975418828592568753770315758610479370948681922136495546332842108359182479433966535765905179459065388440010157609978582001324769124099052737381611149373840917627724397208407089028643895012022628742573222012294052825237085324348444982290123104121122461666554733775475271788467486276475996175601885295303147702452726755226593471202120020410091199743017659208335573154423152801819978230729474715612051171341032334263365083856632777830962888838362419197925323841920453373876672857133617794914410360730116004434899654147180698957725800385129472017678272345459812820971385979547803648176092646145140068284050765640658811309016564056046407942182022651820035228362009982528504039804533767866420627382353719046483891910293375462106828387996245797761671261225013254207748981048605554765186147388853719963818083208243777244635745476307692488230092953697945832727395511335923455041158708566455516940361128710445734129517551071425980383868245384850414606859858328386070419359939079803074746512275418226197202836571384766956166619631171689844438573861785835116965466345655300077072895442275382922411155969198031415738356480027632734767683173461182290664943587642194391696717872166867654883153215102039820352237331385538370736495673578435286268786644516575547497324796824104315134626042330000705635177425450889072765711268672415205890660238315815153396544582388726425393852710118827047025185722269256146833775842006903080438150231695467021895363092529052520574194449676863598714517983262264357148485564703497878252076796987453939376614487678998151538038216932183036887648867146010916400020167219699363649810398529289241805610816901261682694481335373706251300527833925871180538483186233363575543039834652936143724765476480508305310882619200753413549214001157046401271519191156669194718305689324989237259136640434177325764364988116134945176126598820243998840443809752937520515344100617592630708925293861813249878688056870983944233809329996471811576900931997780578487934118491491633897231317094843722600453017152923803380210221974284736694358834261070630538144378201331181295164165912573101108878664104307565822507660429342648076645023021168927208404041863975881061432156693032967007545907712594685762148986214769140105389660472663019317931289961882347209090166368043206503779209112395539888113389407785335974662862517349671898791744588250308875572231759349870386015999899867730850506155358755663748614960022707399194198125201119524711715917827843321904976384404399309909866117302648386221353990707105795689319200425475186294089244622996442050731852097029817043141662937032584233928974737956370762054769055740438112740398572042024506348722650458410985546474473013737717240921600206923559721606463255613663371594880700597771926022187507689847687858240678832570285874435337075457716552831708888345356267662827783367565953777183820536859644451652595212270478985957060226344344006615328799484309837681549308387846900027966717655132797273586137694817492623636158543337389070780557382062590460928510862319381296648463287607060777913950944590945611345871683722732511843519102329506670894902511012732849359818448234315652916582556004294329878892425996281732479821424288647852769164824964729074599862314905063617436396577181901208863286669417671633028568895553965730176671535168886849416991134495839198428309058778632557423424054558897220151969306175456749531391645847260474651558039451142732356612220356880561099668248940964860594234916534549758712951241624081205523001565783316244873255420507329913573024484261568206576447347928383571365849256478051564364025715977517184173481323212119208578654500149740498811223293108994963782665818483798181705998628126622874671206108670316343107440206697310762264893261199201322114098489434319045842881613392743422024262546473060171303072727645787087619741180752610519691334159796822881314093039453830533166310770923481605656257998247400453809665413874039582375952009490304856930435790676573549004040517995168920956454944956745597460627149165715

```
> 1 votes

# Answer
# Haskell, 30 bytes

```
(-).x.last<*>x.head
x=fromEnum

```

Try it online!

Subtracts the ordinal value of the last character from the first one.
> 1 votes

# Answer
# Vyxal `s`, 3 bytes

```
C¯N

```

Try it Online!

Charcodes, deltas, negate.
> 1 votes

# Answer
# APL (Dyalog Extended), 9 bytes

```
⊢/-⍥⎕UCS⊃

```

Try it online!

*-13 thanks to @Adám*

#### Explanation

```
    ⎕UCS     Codepoints of input
        ⊃    Last item
  -⍥         Minus
⊢/           First item

```

Old:

```
{                    }    Define a function
  (⍴⍵)                    Length of argument
       ⎕UCS⍵              Codepoints of input
 (    ⌷     )             Index in (1-indexed)
                          i.e. get the last item
             -            Minus
              1⌷          First item of
                ⎕UCS⍵     Codepoints of input

```
> 1 votes

# Answer
# Trilangle, 19 bytes

```
i2|<_!..>iL.,<@-\S/

```

Try it in the online interpreter!

Unfolds to this:

```
     i
    2 |
   < _ !
  . . > i
 L . , < @
- \ S / . .

```

Roughly equivalent to this C code:

```
#include <stdio.h>

int main() {
    // RED PATH
    int a, b;
    a = b = getchar();
    while (1) {
        int c = getchar();
        if (c == EOF) {
            // BLUE PATH
            printf("%d\n", b - a);
            return 0;
        } else {
            // GREEN PATH
            b = c;
        }
    }
}

```
> 1 votes

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

```
Oz[S

```

Attempt This Online!

Takes the challenge literally, as that's the shortest way.

```
Oz[S # Implicit input
O    # Ordinals
 z[  # Deltas
   S # Sum
     # Implicit output

```
> 1 votes

# Answer
# Thunno 2 `SB`, 1 byte

Try it online!

#### Explanation

```
   # Implicit input
   # Convert to ordinals
Ṣ  # Take the deltas
   # Sum the list
   # Implicit output

```
> 1 votes

# Answer
# Raku, 18 bytes

```
{[-] .ords[*-1,0]}

```

Try it online!

`.ords` returns a list of the ordinal values of the characters in the input string, `[* - 1, 0]` slices into it to return the last and first values, and `[-]` reduces that two-element list using subtraction.
> 1 votes

# Answer
# Haskell, 61 bytes

```
import Data.Char
f s=sum$g$ord<$>s
g(a:b:r)=b-a:g(b:r)
g _=[]

```
> 0 votes

# Answer
# Java 7, ~~100~~ 96 bytes

```
int c(String s){char[]a=s.toCharArray();int r=0,i=a.length-1;for(;i>0;r+=a[i]-a[--i]);return r;}

```

**Ungolfed & test code:**

Try it here.

```
class M{
  static int c(String s){
    char[] a = s.toCharArray();
    int r = 0,
        i = a.length-1;
    for(; i > 0; r += a[i] - a[--i]);
    return r;
  }

  public static void main(String[] a){
    System.out.println(c("Hello World!"));
  }
}

```

**Output:** `-39`
> 0 votes

# Answer
# PHP, 39 Bytes

```
<?=ord(substr($s=$argv[1],-1))-ord($s);

```
> 0 votes

# Answer
# Clojure, 31 bytes

```
#(-(int(last %))(int(first %)))

```

Someone reduced the task already to a single operation.
> 0 votes

# Answer
## Mathematica, 30 bytes

```
Tr@Differences@ToCharacterCode

```
> 0 votes

# Answer
# Befunge-93, 16 bytes

```
~:v_$-.@
~\<^`0:

```

# Befunge-98, 14 bytes

```
~v >-.@
\>#^~

```

Reads (`~`) the first character, and then loops reading (`~`) a character and swaping (`\`) the top 2 items in the stack (so the first character keeps being raised to the top of the stack) until EOF, then substracts (`-`) the top 2 items, outputs (`.`) the result and ends (`@`).
> 0 votes

# Answer
# C, 69 bytes

```
main(i,e,z){while(EOF!=(i =getc(stdin))){z+=e-i;e=i;}putc(z,stdout);}

```
> 0 votes

# Answer
# Pyth (fork), 5 bytes

```
s.+CM

```

Does not work on the online interpreter, as current online interpreters are based only on the main repo.

Explanation:

```
   CM  Map ordinals over input
 .+    Deltas, calculates differences between consecutive numbers
s      Sums the result

```
> 0 votes

# Answer
## Haskell, 27 bytes

```
\x->(ord.last)x-(ord.head)x

```

Unfortunately, Haskell has no knowledge of character codes until you `import Data.Char`. Fortunately, Haskell already treats strings as character arrays.

```
\x->                             --Syntax for anonymous function of 'x'
    (ord                         --Character code of...
        .last)                     --last element in the array
              x                  --Apply to argument
               -
                (ord             --Character code of...
                    .head)         --first element in the array
                          x      --Apply to argument

```
> 0 votes

# Answer
## Pyke, 5 bytes

```
m.o$s

```

Try it here!

```
m.o   -   map(ord, input)
   $  -  delta(^)
    s - sum(^)

```
> 0 votes

# Answer
## Racket 121 bytes

```
(λ(s)(let((l(map char->integer(string->list s))))(for/sum((i(range 1(length l))))(-(list-ref l i)(list-ref l(- i 1))))))

```

Ungolfed version

```
(define f
  (λ(s)
    (let ((l (map char->integer
                   (string->list s))))
      (for/sum ((i (range 1 (length l))))
        (- (list-ref l i)
           (list-ref l (- i 1)))))))

```

Testing

```
(f "Hello World!")

-39

```
> 0 votes

# Answer
# Groovy (80 Bytes)

```
f={n->s=[];n.eachWithIndex{x,i->s<<(i+1<n.size()?(int)n[i+1]-(int)x:0)};s.sum()}

```
> 0 votes

# Answer
# brainfuck, 31 bytes

Probably easy to outgolf, any ideas about this code will be appreciated.

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

```

Try it online!
> 0 votes

# Answer
# C# .NET, 156 bytes

```
public class P{public static void Main(string[]a){int q=0;for(int i=0;i<a[0].Length;i++){q+=i!=a[0].Length-1?a[0][i+1]-a[0][i]:0;}System.Console.Write(q);}}

```

Try online
> 0 votes

# Answer
# Jelly, 3 bytes

```
OIS

```

Try it online!

A monadic link, I think.

Charcodes, deltas, sum.
> 0 votes

# Answer
# Factor, 25 bytes

```
[ dup last swap first - ]

```

Try it online!
> 0 votes

# Answer
# C (gcc), 64 bytes

Takes input from command line: `./a.out "<input>"`

```
main(c,v)char**v;{for(v++;1[*v];)c-=**v-*++*v;printf("%d",c-2);}

```

Try it online!
> 0 votes

# Answer
# JavaScript, 36 bytes

```
s=>s.at(-1)[x='charCodeAt']()-s[x]()

```

Try it:

```
f=s=>s.at(-1)[x='charCodeAt']()-s[x]()

input.addEventListener('input', e => result.innerHTML = f(input.value))
result.innerHTML = f(input.value)
```

```
<input id="input" value="Hello world!"/>
<div id="result"></div>
```
> 0 votes

# Answer
# , 12 bytes

```
1#.2-~/\3&u:

```

Attempt This Online!

```
1#.2-~/\3&u:
        3&u:  NB. convert to codepoints
   2   \      NB. for each consecutive pair
    -~/       NB. minus reduce the first from the second
1#.           NB. sum reduce

```

# Alternative 12 bytes

```
3({:-{.)@u:]

```

Attempt This Online!

```
3({:-{.)@u:]
3        u:]   NB. convert input to codepoints
        @      NB. then
 ({:-{.)       NB. monadic fork
     {.        NB. head
  {:           NB. tail
    -          NB. subtract

```
> 0 votes

---
Tags: code-golf, string, number, arithmetic, array
---


title: Unsort an array

text:
# Question
Title: Unsort an array
Inspired by this StackOverflow post

Given a list where each element appears a maximum of 2 times, we can define it's "sortedness" as the sum of the distances between equal elements. For example, consider

```
[1,1,2,3,3] (array)
 0 1 2 3 4  (indices)

```

The sortedness of this array is \\$2\\$. The distance between the `1`s is \\$1 - 0 = 1\\$, the distance between the `2`s is \\$2 - 2 = 0\\$ (as there's only one `2`) and this distance between the `3`s is \\$4 - 3 = 1\\$. Summing these distances, we get the sortedness as \\$1 + 0 + 1 = 2\\$.

Now, consider

```
[1,3,2,1,3] (array)
 0 1 2 3 4  (indices)

```

The sortedness of this array is \\$6\\$:

* `1`s: \\$3 - 0 = 3\\$
* `2`s: \\$2 - 2 = 0\\$
* `3`s: \\$4 - 1 = 3\\$
* \\$3 + 0 + 3 = 6\\$

In fact, \\$6\\$ is the maximal sortedness of the permutations of this particular array, and there are 16 permutations of `[1,1,2,3,3]` with a sortedness of \\$6\\$.

```
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[1, 3, 2, 1, 3]
[1, 3, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]
[3, 1, 2, 1, 3]
[3, 1, 2, 3, 1]

```

---

Given a list of positive integers, where each integer appears either once or twice, output a permutation of this list where the sortedness is maximal. You may input and output in any convenient manner, and you may output any number of the permutations with maximal sortedness.

This is , so the shortest code in bytes wins.

## Test cases

```
input -> output
[1] -> [1]
[8, 7] -> [8, 7]
[1, 1, 2] -> [1, 2, 1]
[9, 7, 4] -> [9, 7, 4]
[2, 9, 3, 10] -> [2, 9, 3, 10]
[4, 4, 10, 10] -> [4, 10, 4, 10]
[1, 1, 2, 3, 3] -> [1, 3, 2, 1, 3]
[2, 8, 5, 6, 5] -> [5, 2, 8, 6, 5]
[5, 2, 6, 1, 9] -> [5, 2, 6, 1, 9]
[7, 1, 1, 4, 5, 5, 8] -> [1, 5, 7, 4, 8, 1, 5]
[3, 1, 2, 8, 3, 10, 8] -> [3, 8, 1, 2, 10, 3, 8]
[1, 1, 2, 2, 3, 3, 4, 4] -> [1, 2, 3, 4, 1, 2, 3, 4]
[4, 4, 3, 3, 2, 2, 1, 1] -> [4, 3, 2, 1, 4, 3, 2, 1]

```

# Answer
# Python 3, 47 bytes

```
lambda l:(sorted({*l},key=l.count)*2)[-len(l):]

```

Try it online!
> 15 votes

# Answer
# Python 2, 57 bytes

```
lambda l:[x for c in 1,2,1for x in set(l)if l.count(x)-c]

```

Try it online!

Iterates through the distinct elements of `l` 3 times, first outputting those that appear twice in `l`, then those that appear once, then twice again.

*-1 byte by att*

# Python 3.8, 47 bytes

```
def f(l):*map(l.remove,s:={*l}),;l+=[*s-{*l}]+l

```

Try it online!

*-3 bytes by pxeger with modifying the list in place*
> 13 votes

# Answer
# , 10 bytes

```
/:~:*1#.e.

```

Try it online!

I had this first, hoping J might tie caird's Jelly, but I couldn't find any actual 9-byter.

### How it works

```
/:~:*1#.e.    Monadic train, input: X, a numeric vector
     1#.e.    Count occurrences of each number of X in X
  ~:*         Multiply with nub sieve (1 if a number appears first, 0 otherwise)
              First occurrence of a double becomes 2, second becomes 0
              A single becomes 1
/:            Sort X by the above

```
> 10 votes

# Answer
# Wolfram Language (Mathematica), 35 bytes

```
ReverseSort@Gather@#~Flatten~{2,1}&

```

Try it online!

```
                   #                    {1,1,2,3,3}
            Gather@                     {{1,1},{2},{3,3}}
ReverseSort@                            {{3,3},{1,1},{2}}
                    ~Flatten~{2  }      {{3,1,2},{3,1}}
                               ,1       {3,1,2,3,1}

```
> 8 votes

# Answer
# Jelly, 7 bytes

```
ẹⱮ_"JỤị

```

Try it online!

### How it works

```
ẹⱮ_"JỤị    Monadic link. Input: X, a numeric vector
ẹⱮ         For each element n of X, get all indices of n in X
  _"J      For each list of indices, subtract the original index
           If n appears twice, the first becomes [0, positive],
           and the second becomes [negative, 0].
           If n appears only once, it becomes [0].
     Ụị    Sort X by the above
           All [negative, 0]s come first, then [0]s, then [0, positive]s

```

I really hope Jelly were a proper derivative of J/K, in which case we wouldn't need the `"`.
> 7 votes

# Answer
# Factor, ~~94~~ 62 bytes

```
[ [ ] collect-by values [ length ] inv-sort-with round-robin ]

```

Have a screenshot of running this in Factor's REPL because `collect-by` postdates the build on TIO.

## Explanation

I finally found a use for `round-robin`! It's sort of like if `flip` (matrix transposition) worked for non-rectangular matrices and it also flattens the results.

```
                          ! { 1 1 2 3 3 }
[ ] collect-by            ! H{ { 1 V{ 1 1 } } { 2 V{ 2 } } { 3 V{ 3 3 } } }
values                    ! { V{ 1 1 } V{ 2 } V{ 3 3 } }
[ length ] inv-sort-with  ! { V{ 1 1 } V{ 3 3 } V{ 2 } }
round-robin               ! { 1 3 2 1 3 }

```
> 7 votes

# Answer
# Jelly, 6 bytes

```
ĠEÞZFị

```

A monadic Link accepting and returning a list of positive integers as specified.

**Try it online!**

### How?

Produces a list of the form `a+b+a` where `a` is a list of the elements that are present twice and `b` is a list of the elements that only appear once. (`a` and `b` are also each sorted by value as a side effect of the method employed.)

```
ĠEÞZFị - Link: list of integers with at most two of each, A
                                             e.g. [3, 3, 1, 1, 2]
Ġ      - group indices of A by their values       [[3, 4], [5], [1, 2]]
  Þ    - sort the result using:                    v       v    v
 E     -   all equal?                              0       1    0
                                              ->  [[3, 4], [1, 2], [5]]
   Z   - transpose                                [[3, 1, 5], [4, 2]]
    F  - flatten                                  [3, 1, 5, 4, 2]
     ị - index back into A                        [1, 3, 2, 1, 3]

```
> 7 votes

# Answer
# Jelly, 8 bytes

```
Œ!ĠISƊÐṀ

```

Try It Online!
> 6 votes

# Answer
# Haskell + hgl, 17 bytes

```
cx<tx<rsB l<gr<sr

```

## Explanation

This one is pretty simple, it composes 5 functions:

* `sr` sorts a list.
* `gr` groups a list into contiguous sublists of equal elements.
* `rsB l` sorts a list of lists in descending order of length.
* `tx` transposes a list of lists.
* `cx` concats a list of lists.

## Worked example

We take the original list:

```
1 2 9 9 3 1

```

... sort it

```
1 1 2 3 9 9

```

... group it

```
1 1
2
3
9 9

```

... sort by length

```
1 1
9 9
2
3

```

... transpose it

```
1 9 2 3
1 9

```

.. and concat it

```
1 9 2 3 1 9

```

## Reflections

This score seems pretty weak despite how straightforward the answer is. However I think there could be some improvements.

* `rsB l` and `sB l` could probably be their own functions. Sorting lists by length is likely to come up again so it would be nice to have these.
* `gr<sr` could probably be rolled into one function. It's not uncommon to want to get all the groups irrespective of the initial order and 5 bytes is a big price for that. Since the final order is arbitrary why not sort the output by size. It's the order we want here so that shows it's at least useful once.

As of e7ce5325 these changes have been implemented saving 9 bytes:

```
cx<tx<bg

```

Obviously this is non-competing, but these changes should be helpful in the future.
> 6 votes

# Answer
# MATL, ~~14~~ ~~12~~ 9 bytes

```
9B#u1>&)y

```

The input is a column vector. The output contains each entry on a line (not necessarily right-aligned). Try it online! Or verify all test cases.

### Explanation

This outputs the duplicated numbers in their original order, then the non-duplicated numbers, then the duplicated numbers in their original order again.

```
9B   % Push 9, convert to binary. Gives [1 0 0 1]
#    % Use as output specification for the next function
u    % Implicit input. "Unique" function, first and fourth outputs. This
     % pushes the unique numbers in their orignal order, and their count
1>   % Greater than 1? (element-wise). Gives a mask for duplicated numbers
&    % Use alternative output specification for the next function
)    % Indexing, two outputs. This pushes the duplicated numbers, then the
     % non-duplicated numbers
y    % Duplicate from below. Implicit display

```
> 5 votes

# Answer
# 05AB1E, 7 bytes

```
ÙΣ¢}RI∍

```

Try it online!

-4 thanks to @ovs
> 5 votes

# Answer
# Python3, ~~139~~ ~~131~~ ~~116~~ 106 bytes

```
def f(x):
 l,m=[],[]
 while x:
  i=x.pop()
  if x.count(i):l+=[i];x.remove(i)
  else:m+=[i]
 return l+m+l

```

Try it online

## Alternative with lambda, 103 bytes

With non-deterministic ordering of elements. I'm not sure, whether that counts:

```
lambda x:(l:=[e for e in set(x)if x.count(e)>1])+[e for e in set(x)if x.count(e)<2]+l

```

Try it online
> 4 votes

# Answer
# Python 3, 69 bytes

```
def f(l):x={z for z in l if l.count(z)<2};y=[*{*l}-x];return y+[*x]+y

```

Try it online!

No, @xnor has better version of this idea, heck @tsh has even better
> 4 votes

# Answer
# , 19 bytes

```
/:~:]`(I.@[)`[}1#.=

```

Try it online!

The idea is to create a mask for sorting, such that unique elements are pushed into the middle, and the first and second instances of repeat elements are pushed right and left, like a solution of water, oil, and mercury.

Consider `2 1 1 3 3`:

* `=` Creates boolean masks for each unique element:

```
1 0 0 0 0
0 1 1 0 0
0 0 0 1 1

```
* `1#.` Sums the rows:

```
1 2 2

```
* `~:` Nub sieve of input: ones at the first occurrence of each element:

```
1 1 0 1 0

```
* `]`(I.@[)`[}` Update the nub sieve `[` at the indices of those ones `(I.@[)` using the row-sum values `]` (ie, `1 2 2`):

```
1 2 0 2 0

```
* `/:` Sort the original input according to that:

```
1 3 2 1 3

```
> 4 votes

# Answer
# Vyxal, 13 bytes

```
ĠvḢf?Ġ'₃;fȮJJ

```

Try it Online! Wow this is a mess.

```
Ṗµ          ;t # Maximal permutation by...
  Uv=∩         # For each unique element, indices of equal elements?
      ƛ   ;∑   # Apply to each, taking the sum
       T       # Truthy indices
        ¯h     # Cumulative differences

```
> 3 votes

# Answer
# Charcoal, 21 bytes

```
Ｗ⁻θυ⊞υ⊟ιＦ³ＩΦυ¬﹪⁻ι№θκ²

```

Try it online! Link is to verbose version of code. Explanation: Since each element is guaranteed to occur no more than twice, the exercise reduces to printing the elements that are duplicated, then the ones that only appear once, then the ones that are duplicated again.

```
Ｗ⁻θυ⊞υ⊟ι

```

Create a (reversed) deduplicated list of elements.

```
Ｆ³ＩΦυ¬﹪⁻ι№θκ²

```

Output the elements three times, but alternately filtered on whether the element was originally duplicated or not.
> 3 votes

# Answer
# Husk, 7 bytes

```
ΣT↔ÖLk=

```

Try it online!

Output is concatenation of:

1. List of all elements present, with those appearing twice coming first
2. List of elements that appear twice, in the same order as 1

```
     k=  # group list elements by equality
   ÖL    # and sort the groups by length
  ↔      # and reverse this order
         # (so now 2-element groups are first,
         # then 1-element groups),
 T       # now transpose
Σ        # and flatten the resulting list of 2 lists

```
> 3 votes

# Answer
# , ~~55~~ 54 bytes

*Edit: -1 byte thanks to Giuseppe*

```
function(x)names(y<-table(x))[c(order(-y),which(y>1))]

```

Try it online!

Output as strings of the original elements. Add +3 bytes to output as the original elements themselves (see TIO link).

Output is: one of each element that appears twice, then elements that appear once, and finally one more of each element that appears twice.
> 3 votes

# Answer
# BQN, 13 bytes

```
(⍷⍒∘⊒⊸⊏˜)∾⊒⊸/

```

Try it at BQN online REPL

```
         ∾      # join together:
(⍷⍒∘⊒⊸⊏˜)       # L: unique set of elements, with those present twice first
    ⊒           #    occurrence count of each element
  ⍒∘            #    reverse order (so those twice first)
      ⊸⊏˜       #    use this to index original elements
 ⍷              #    and deduplicate them;
          ⊒⊸/   # R: just the elements that are present twice
          ⊒     #    occurrence count of each element
           ⊸/   #    use this to select original elements

```
> 3 votes

# Answer
# Vyxal, 13 bytes

```
Ṗµv=UvTv¯f∑;h

```

Try It Online!

Vyxal's deltas is negative for whatever reason, but no worries, we just get the minimum value then.
> 2 votes

# Answer
# Retina 0.8.2, ~~53~~ 44 bytes

```
O$`(\d+)((?<=\b\1,.*))?((?!.*,\1\b))?
$#2$#3

```

Try it online! Link includes test cases. Explanation: Saved 9 bytes by using @Bubbler's idea of encoding both whether the elements need to be sorted to the start or the end in the same sort key.

```
(\d+)

```

Matching each entry...

```
((?<=\b\1,.*))?

```

... check whether this is the second entry of a duplicate, and...

```
((?!.*,\1\b))?

```

... check whether this is a unique entry or the second entry of a duplicate.

```
O$`
$#2$#3

```

Sort by a combination of the two checks. The first entry of a duplicate has a sort key of `00`. Unique elements have a sort key of `01`. The second entry of a duplicate has a sort key of `11`. This means that the unique elements sort between the two sets of duplicate elements.
> 2 votes

# Answer
# Jelly, 7 bytes

A port of tsh's Python answer.

```
Qċ@Þ¹Uṁ

```

Try it online!

```
Q        -- the unique elements of the list
   Þ     -- sort by ...
 ċ@ ¹    --   the number of occurences in the full list
     U   -- reverse
      ṁ  -- mold; reshape the list to the length of input by reusing from the front

```
> 2 votes

# Answer
# python3, ~~121~~ 101 bytes

```
def u(l):
 x=[]
 y=set()
 for i in l:x.append(i)if l.count(i)%2else y.add(i)
 y=list(y)
 return y+x+y

```

Try it online!

Thanks to caird coinheringaahing
> 2 votes

# Answer
# Perl 5, 67 bytes

```
sub f{pop=~s/(.*)(\b\d+ )(.*)(\2)(.*)/my$x=$2;$x.f("$1$3$5").$x/er}

```

Try it online!
> 2 votes

# Answer
# , 48 bytes

```
function(x)c(d<-x[duplicated(x)],setdiff(x,d),d)

```

Try it online!
> 2 votes

# Answer
# Ruby, 43 bytes

```
->l{(l&l-z=l.select{|x|l.count(x)<2})+z|=l}

```

Try it online!
> 2 votes

# Answer
# Julia 1.0, 46 bytes

```
~a=(!x=a∩a[a.|>i->sum(i.==a)==x];[!2;!1;!2])

```

Try it online!
> 2 votes

# Answer
# C (gcc), ~~119~~ \\$\cdots\\$ ~~103~~ 97 bytes

```
*b;*p;f(a,e)int*a,*e;{for(b=a;a<e;++a)for(p=a;++p<e;)*a==*p?*p^=*--e^(*e=*p),*a^=*b^(*b++=*a):0;}

```

Try it online!

*Saved 3 bytes thanks to ceilingcat!!!*

Inputs a pointer to an array of integers and a pointer one past the end of the array (because pointers in C carry no length info).
Unsorts the array in place.

### Commented

```
*b;*p;f(a,e)int*a,*e;{             // declare pointers and f
    for(   ;a<e;++a)               // main loop a to the end
        b=a                        // init b to the beginning
        for(p=a;++p<e;)            // inner loop of p from
                                   //   a + 1 to the end
            *a==*p?                // is current int equal to
                                   //   another int in a?
                *p^=*  e^(*e=*p),  // then swap second int with
                                   //   one before the end
                     --            // move end back one
                *a^=*b^(*b  =*a)   // and swap current int with
                                   //   the beginning which
                                   //   has already been seen
                                   //   so is single or is the
                                   //   same as what a points to
                          ++       // bump up the beginning one
            :0;                    // or do nothing
}                                  //

```
> 2 votes

# Answer
# JavaScript (Node.js), 60 bytes by tsh

```
a=>(p=a.filter(y=c=>!(y[c]^=1))).concat(a.filter(c=>y[c]),p)

```

Try it online!

# JavaScript (Node.js), 61 bytes

```
x=>x.map(r=t=>r[t]=[r[t]?~++r[t][0]:4,t]).sort().map(t=>t[1])

```

Try it online!
> 1 votes

# Answer
# Vyxal, 56 bitsv2, 7 bytes

```
Þzµ≈;∩fİ

```

Try it Online!

Jelly porting ftw
> 1 votes

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


title: Adjacent Items Sorting

text:
# Question
Title: Adjacent Items Sorting
Given a list, `L`, of sets of numbers like this:

```
[[1], [0,2,3], [3,1], [1,2,3]]

```

Output a single list of numbers such that 2 numbers A and B appear next to each other at least once if and only if `B in L[A]`.

That is all such pairs *must* exist in the output, and *only* such pairs *may* exist in the output, where the order of any pair in the output may be read in either direction.

If `A` is in `L[B]` then `B` is guaranteed to be in `L[A]`, in other words, the relationship is symmetric.

In this case, one possible output would be this:

```
[0, 1, 2, 3, 3, 1, 3]

```

In this case, you can see `0` is only ever next to `1`, which matches our adjacency list. `1` appears next to `0` and `2` in the first instance and `3` in the second instance. It appears next to `3` again but that doesn't matter. Numbers are adjacent if they appear together at least once, but more doesn't matter. `2` appears next to `1` and `3`, and finally `3` appears next to `2`, `1`, and itself (necessary since `L[3]` contains a `3`).

For any given adjacency list there are many possible solutions. You may choose to output any valid solution. Your solution does not need to be the shortest one, but it does need to have a finite length.

## Test Cases

| Input | Possible Solution |
| --- | --- |
| `[[0]]` | `[0, 0]` |
| `[[1],[0]]` | `[0, 1]` |
| `[[0,1,2], [0], [0]]` | `[1, 0, 0, 2]` |
| `[[0,1,2], [0,1,2], [0,1,2]]` | `[0, 1, 1, 2, 2,0, 0]` |
| `[[1,2,3,4], [0], [0], [0], [0]]` | `[1, 0, 2, 0, 3, 0, 4]` |
| `[[1, 2], [0, 2], [0, 1]]` | `[0, 1, 2, 0]` |
| `[[], [2], [1]]` | `[1,2]` |

## IO

Any of list of sets, dict of sets, list of lists, list of dicts, adjacency matrix, are valid input formats. You don't have to use numbers if you use a mapping, any primitive data type with a potentially infinite number of elements is valid.

For the input `[[0,1,2], [0], [0]]` the following would all be possible input formats from you to choose from. You only need to handle one of these of your choice.

* `[[0,1,2], [0], [0]]`
* `{0: {0,1,2}, 1: {0}, 2: {0}}`
* `{'a': "abc", 'b': "a", 'c': "a"}` (Strings and arrays of characters are considered equivalent.
* `[[1,1,1],[1,0,0],[1,0,0]]` (Adjacency matrix)

# Answer
# 05AB1E, ~~14~~ ~~13~~ ~~11~~ 12 bytes

```
Wsvεèyδ‚yš}˜

```

Try it online!

If it shouldn't output "0" for 0 it can be fixed with +1 byte by appending `ï`.

## Explanation

Suppose `i` is adjacent to `[a1, ..., a2, ..., an]`. If we start with some path, we can replace all instances of `i` with `i, a1, i, a2, i, a3, i, ..., i, an, i` and remain with a valid path.

If we do it N times, we will necessarily traverse all edges, since N-1 is the maximal distance in a connected graph, after N-1 times all vertices will appear, and the N-th iteration will add all edges.

```
W       push the minimum number in the input
s       and swap it, so the input is back on top
v       for each element in the input (we do this to repeat N times)
 ε       replace each value in our list (which starts with "0") with
  è       index it into the implicit input
  y       push the index
  δ       and for each element in the adjacency list
  ‚       pair it with the index
  y       push the index again
  š       and prepend it to the list
 }       (the list isn't flat, but we flatten it later)
 ˜       and flatten

```
> 13 votes

# Answer
# Python, 131 bytes

```
f=lambda l,h=[],*t:h*({*zip(h,[r:=range(len(l))]+h)}>{(a,b)for a in r for b in l[a]})or f(l,*t,*(h+[i]for i in[*l,r][[-1,*h][-1]]))

```

Attempt This Online!

Since it's a bit less readable than a typical python submission, here's the explanation:

The code does a BFS, keeping track of the queue using varargs. `h` is the entry to be explored this iteration.

We first check if `h` is a solution using `{*zip(h,[r:=range(len(l))]+h)}>{(a,b)for a in r for b in l[a]}`. This checks if the left set is a strict superset of the right one.

The left set is the set of all ordered adjacencies present in `h` plus an extra element `(h[0],r)`.

For the purposes of this part of the code, the exact value of `r` does not matter, only that it's distinct from integers.

The right set is the set of all possible adjacencies.

The comparison is a bit more strict than necessary, but due to the symmetry of `l` it doesn't matter.

If the comparison succeeds this means that `h` gets multiplied by 1 and the `or` short circuits and `h` is returned, otherwise we explore `h`.

We recurse, adding new paths at the end of the queue (varargs). There is also code that handles the special case of `h=[]` which happens at the start
> 7 votes

# Answer
# Wolfram Language (Mathematica), ~~83~~ 72 bytes

```
(c=1;FindPostmanTour[Reap[(Sow[#<->c]&/@#;c++)&/@#][[2,1]]][[1,All,1]])&

```

Try it online!

Start from `1` notation!
Much shorter, but still has problem with `[[1]]`...
> 5 votes

# Answer
# ATOM 70 chars, 74 bytes

```
{i=*;p=[];g={p+*;i.*∀{*p:*g;p+$1}};0g;(p{a=[*];i.*∀{a+*+$1};a})}

```

Edit: Decided to add integer for-loops to the language as an alternative to arrays, and with that plus changing the algorithm to the top one used by 05AB1E, I got this down to 38 char/43 bytes. The change happened after the question was posted, and it feels like cheating to steal someone else's algorithm, so I'll keep the label on this answer as 70 char/74 bytes.

```
{r=[0];*∀r=(r[*,$2.*[*,$1]]);r}

```

## Usage

```
input=[[1], [0,2,3], [3,1], [1,2,3]];
input INTO {i=*;p=[];g={p+*;i.*∀{*p:*g;p+$1}};0g;(p{a=[*];i.*∀{a+*+$1};a})}

```

### Try it online

## Explanation Using Commented Non-Golfed Code

```
input=[[1], [0,2,3], [3,1], [1,2,3]];
visited=[];
path=[];
# Create a path of indices that hits each at least once
# Depth first traversal
visit = {
  visited+*; # Add the index to the list of visited indices
  path+*; # Add the index to the path
  # Look at each connected index and check if its already visited
  input.* FOREACH {
    * NOTIN visited:
      * INTO visit;
      path+$1; # Return to the original index at the end
  }
};
0 INTO visit;
"Path";
path;

# Create a function that takes an index and generates a proper neighbor sequence
neighbors = {
  arr = [*];
  input.* FOREACH {
    arr + *;
    arr + $1;
  };
  arr
};

# Map the path into neighbor sequences
result = (path MAP neighbors);
"Preflattened Result";
result;

# Flatten it and return
 result

```

Essentially it builds a path of indices that is guaranteed to hit each of them at least once. Then, it takes that path, and turns each point on the path into a sequence of numbers that hits every pair from the input. The solution it finds is very brute forced and longer than what is optimal.

Between the time of the question being posted and this solution, I implemented the flatten operator (the foot). Hopefully that function is considered standard enough to not be considered breaking a loophole.
> 5 votes

# Answer
# Python3, 244 bytes

```
def F(r,k=[],s=[]):
 if not r-{*s}:yield k
 for x,y in r:
  if(x,y)not in s and([]==k or k[-1]==x):yield from F(r,k+[x,y][k!=[]:],s+[(x,y)])
def f(l):
 v={i for j in l for i in j if i<len(l)}
 return F({(x,y)for x in v for y in v if x in l[y]})

```

Try it online!
> 4 votes

# Answer
# Charcoal, 42 bytes

```
≔Ｅθ⟦κ⟧ηＦη¿¬ⅉ¿⊙θ⁻κＥ⌕ＡΦινλ§ιμＦ§θ↨ι⁰⊞η⁺ι⟦κ⟧Ｉι

```

Try it online! Link is to verbose version of code. Actually outputs the shortest list of numbers such that both pairs `A, B` and `B, A` appear in the list. Explanation:

```
≔Ｅθ⟦κ⟧η

```

Start with the trivial lists of just one item. (This is needed so that we know which next item(s) are valid.)

```
Ｆη¿¬ⅉ

```

Start a breadth first search of lists but stopping once a solution is found.

```
¿⊙θ⁻κＥ⌕ＡΦινλ§ιμ

```

Check whether all the pairs exist in this list.

```
Ｆ§θ↨ι⁰⊞η⁺ι⟦κ⟧

```

If not then try all the lists obtained by appending one of the legal neighbours of the last element.

```
Ｉι

```

If they do then output this solution.

30 bytes for a port of @CursorCoercer's nondeterministic but fast Pyth answer:

```
⊞υ⌈⌈θＷ⊙θ⁻κＥ⌕ＡΦυνλ§υμ⊞υ‽§θ↨υ⁰Ｉυ

```

Try it online! Link is to verbose version of code. Outputs a random list containing all the pairs and their reversals. Explanation:

```
⊞υ⌈⌈θ

```

Push the maximum number from the lexicographically maximum list.

```
Ｗ⊙θ⁻κＥ⌕ＡΦυνλ§υμ

```

Repeat while the list does not contain all of the pairs...

```
⊞υ‽§θ↨υ⁰

```

... push a random hop from the last number.

```
Ｉυ

```

Output the final list.
> 3 votes

# Answer
# Scala, 336 bytes.

\\$ \color{red}{\text{It failed on some cases. Any help would be appreciated.}} \\$

Modified from @Ajax1234's answer.

---

Golfed version. Try it online!

```
type Q=Int
def f(l:Seq[Seq[Q]])={def g(v:Set[Q],l:Seq[Seq[Q]],k:Seq[Q]=Seq(),s:Seq[(Q,Q)]=Seq()):Seq[Q]={for(x<-v;y<-v){val X=Seq(x,y).min;val Y=Seq(x,y).max;if(!s.contains((X,Y))&&l(Y).contains(X))return g(v,l,k++Seq(X,Y).drop(if(k.nonEmpty&&k.last==X)1 else 0),s:+(X,Y))};k};g((l.indices.flatMap(i=>l(i).filter(_<l.length)).toSet),l)}

```

Ungolfed version. Try it online!

```
object Main extends App {
  def f(l: Array[Array[Int]]): List[Int] = {
    func((l.indices.flatMap(i => l(i).filter(_ < l.length)).toSet), l)
  }

  def func(v: Set[Int], l: Array[Array[Int]], k: List[Int] = List(), s: List[(Int, Int)] = List()): List[Int] = {
    for (x <- v; y <- v) {
      val sortedPair = List(x, y).sorted
      val X = sortedPair(0)
      val Y = sortedPair(1)
      if (!s.contains((X, Y)) && l(Y).contains(X))
        return func(v, l, k ++ List(X, Y).drop(if (k.nonEmpty && k.last == X) 1 else 0), s :+ (X, Y))
    }
    k
  }

  println(f(Array(Array(1), Array(0,2,3), Array(3,1), Array(1,2,3))))
  println(f(Array(Array(0))))
  println(f(Array(Array(1),Array(0))))
  println(f(Array(Array(0,1,2), Array(0), Array(0))))
  println(f(Array(Array(0,1,2), Array(0,1,2), Array(0,1,2))))
  println(f(Array(Array(1,2,3,4,5), Array(0), Array(0), Array(0), Array(0))))
  println(f(Array(Array(1, 2), Array(0, 2), Array(0, 1))))
  println(f(Array(Array[Int](), Array(2), Array(1))))
}

```
> 2 votes

# Answer
# , ~~89~~ 82 bytes

*Edit: -7 bytes thanks to pajonk*

```
f=\(l,p=max(?l),n=p,`?`=unlist)`if`(n,f(l,?Map(\(x)c(x,rbind(l[[x]],x)),p),n-1),p)

```

Attempt This Online!

Same approach as Command Master's answer: upvote that one!
(uses 1-based indexing)

**Ungolfed:**

```
f=function(l,p=unlist(l)[1],n=1){
    if(n==length(l))return(c(unlist(p)))
    else{
        f(l,unlist(sapply(p,function(x)c(x,rbind(l[[x+1]],x)))),n+1)
    }
}

```
> 2 votes

# Answer
# JavaScript (Node.js), 73 bytes

```
x=>g=(i=x.findIndex(x=>x+x))=>[i,...x[i].flatMap(j=>[...g(j),i],x[i]=[])]

```

Try it online!

Each appearance of edge runs twice
> 2 votes

# Answer
# Pyth, 19 bytes

```

KOQWnQXKH.{
=KO@QK

```

Try it online!

Takes input as a dictionary of sets. Starts at a random node and randomly traverses the graph until all edges have been hit.

### Explanation

```
                         # implicitly set H to an empty dict
                         # implicitly set Q = eval(input())
  KOQ                    # set K to a random key in Q
\n                       # print(K)
     WnQ                 # while Q != H:
        XKH              #   add to H[K] (or assign to if H has no key K)
           .{            #   set containing
               =K        #   K assigned to
                 O@QK    #   a random element of Q[K]
             \n          #   print(K)

```
> 1 votes

---
Tags: code-golf, array, open-ended-function
---


title: Enumerate all pure sets

text:
# Question
Title: Enumerate all pure sets
In set theory, a set is an unordered group of unique elements. A pure set is either the empty set \\$\\{\\}\\$ or a set containing only pure sets, like \\$\\{\\{\\},\\{\\{\\}\\}\\}\\$.

Your challenge is to write a program that enumerates all pure sets, in some order of your choice. Standard rules apply - you may:

* Output all pure sets
* Take an integer \\$n\\$ and output the nth set by your definition
* Take an integer \\$n\\$ and output the first n sets.

(\\$n\\$ may be 0 or 1-indexed)

Pure sets may be represented in any reasonable format.

This is , shortest wins.

# Answer
# Python, 43 bytes

```
f=lambda x:[f(i)for i in range(x)if x>>i&1]
```

Attempt This Online!

Outputs the \\$ n \\$th set, starting at \\$ 0 \\$.

One way of creating a sequence of all pure sets is to encode them as binary numbers, with bits set according to which indices of pure sets they do and do not contain.

For example, the empty set contains no sets, so it has no 1 bits, and its index is \\$ 0 \\$.

For the set `{{}}`, it contains only one item, the empty set, which has index 0, so we set a 1 bit in the 0th position: \\$ 1 \\$.

For the set `{{}, {{}}}`, it contains two items: the empty set with index 0, and the previous `{{}}` which has index 1. Therefore, we set the 0th and 1st bits: \\$ 11\_2 = 3\_{10} \\$

My program does the reverse of this process.

This is essentially the same as my answer to Output every sublist ... eventually but operating recursively on itself.
> 18 votes

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

Port of pxeger's answer.

```
{o'&|2\x}

```

Try it online!

`|2\x` The argument converted to binary, reversed.
`&` Where, indices of 1s.
`o'` For each of those indices, call the function recursively.
> 7 votes

# Answer
# Python 2, 45 bytes

-1 thanks to pxeger

```
f=lambda x,n=0:x*[1]and x%2*[f(n)]+f(x/2,n+1)

```

Try it online!

A worse version of pxeger's answer. The input's binary digits encode which sets are included.
> 5 votes

# Answer
# Rust, ~~113~~ 79 bytes

*-34 bytes thanks to @alephalpha*

```
struct K(Vec<K>);fn f(x:u64)->K{K((0..x).filter(|v|x>>v&1>0).map(f).collect())}

```

Could save 2 bytes by using `u8` instead but then it generates only 5 numbers before overlow. You could also use 128 bit integers to get more numbers. Algorithm copied from @pxeger.

Try it yourself: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=1dbb90a9b8347a6cd554723dedbb93e1
> 4 votes

# Answer
# 05AB1E, 8 bytes

```
ÝæΔDè}Iè

```

Outputs the 0-based \\$n^{th}\\$ value.

Try it online or verify the first few test cases.

Outputting the first \\$n\\$ values would be 8 bytes as well by replacing the `è` with `£`:
Try it online or verify the first few test cases.

**Explanation:**

```
Ý         # Push a list in the range [0, (implicit) input]
 æ        # Get the powerset of this list
  Δ  }    # Loop until the result no longer changes:
   D      #  Duplicate the list
    è     #  And index each inner-most integers into itself
      I   # After the loop: push the input-integer again
       è  # And index it into the list
       £  # Or alternatively leave that meany leading items from the list
          # (after which the result is output implicitly)

```

Try `∞<æ` online to see (the infinite version of) the list it uses to reduce all inner integers down to `[]`.
> 4 votes

# Answer
# BQN, 20 bytes

```
{¨(2|·⌊÷2⊸⋆)¨⊸/↕}

```

Try it here!

Based on pxeger's answer.

## Explanation

* range from 0 to input `x`
* `(...)¨⊸/` filter range over predicate...
* `2|·⌊÷2⊸⋆` equivalent to `floor(x / 2^i) mod 2`
* recurse on each filtered index.
> 4 votes

# Answer
# x86-64 machine code, 28 bytes

```
B0 7B AA EB 0B 0F B3 C6 56 96 E8 F1 FF FF FF 5E 0F BC C6 75 F0 B0 7D AA C6 07 00 C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes in RDI an address at which to place the result, as a null-terminated byte string, and takes the input number in ESI.

This uses the same method as most other answers, with a set's number having 1s in binary positions corresponding to its elements' numbers.

In assembly:

```
f:  mov al, '{'
    stosb
    jmp b
a:  btr esi, eax
    push rsi
    xchg eax, esi
    call f
    pop rsi
b:  bsf eax, esi
    jnz a
    mov al, '}'
    stosb
    mov BYTE PTR [rdi], 0
    ret

```
> 3 votes

# Answer
# Jelly, 6 bytes

```
BṚT’ß€

```

A recursive mondaic Link that accepts `n` (0-indexed) and yields the `n`-th pure set using the empty list as the empty set.

**Try it online!**

### How?

```
BṚT’ß€ - Link: non-negative integer, n
B      - convert to binary
 Ṛ     - reverse
  T    - truthy indices (1-indexed)
   ’   - decrement (vectorises)
     € - for each:
    ß  -   call this Link

```
> 2 votes

# Answer
# Haskell, 49 bytes

Outputs as a lazily evaluated infinite list. Each entry is encoded as a nested list.

```
import Data.List
data P=P[P]
p=P<$>subsequences p

```
> 2 votes

# Answer
# Vyxal, 6 bytes

```
λbṘTvx

```

Try it Online!

Port of Jelly.

```
λbṘTvx
λ      # Open a lambda for recursion, f(x)
 b     # Get the binary representation of x (as a list)
  Ṙ    # Reverse
   T   # Get truthy indices of that (zero-indexed)
    vx # For each, recurse

```
> 2 votes

# Answer
# Charcoal, 15 bytes

```
ＦＮ⊞υΦυ＆ιＸ²λ⭆¹⊟υ

```

Try it online! Link is to verbose version of code. Outputs the 1-indexed `n`th set using `[]`s. Explanation:

```
ＦＮ

```

Repeat `n` times.

```
⊞υΦυ＆ιＸ²λ

```

Extract the existing lists given by the binary decomposition of the current index and push the resulting list to the predefine empty list.

```
⭆¹⊟υ

```

Pretty-print the last list.
> 1 votes

# Answer
# Retina, 53 bytes

```
{`\d+
{$&*_}
+`(_+)\1
$1@
_(?=((@)|(_))*)
$#2$.3*,
@

```

Try it online! Link includes test cases. Output's the 0-indexed `n`th set. Explanation:

```
{`

```

Repeat until all subsets have been constructed.

```
\d+
{$&*_}

```

Convert all integers to unary, and wrap them in `{}`s. Note that if the integer was `0`, there were no `_`s, so processing stops for this integer here.

```
+`(_+)\1
$1@

```

Partially convert them to binary, but using the "digits" `@_` and `@`. Normally for binary conversion you would then remove the `@`s before `_`s, but we only need the count of "digits", which here is simply the count of `@`s.

```
_(?=((@)|(_))*)

```

For each `1` in the binary representation, calculate its bit position and whether it's the last `1` bit...

```
$#2$.3*,

```

... and replace it with the position and append a `,` if this is not the last `1` bit.

```
@

```

Delete the remaining `@`s.
> 1 votes

# Answer
# Ruby, 39 bytes

```
f=->n{(0...n).select{|x|n[x]>0}.map &f}

```

Try it online!

Based on pxeger's python answer.
> 1 votes

# Answer
# Julia 1.0, 28 bytes

```
!k=[!i for i=0:k if k&2^i>0]

```

Try it online!

Port of pxeger's answer
> 1 votes

# Answer
# JavaScript (Node.js), 49 bytes

```
f=(x,i=0)=>x?[...x&1?[f(i)]:[],...f(x>>1,i+1)]:[]

```

Try it online!
> 1 votes

---
Tags: code-golf, sequence, combinatorics, open-ended-function, set-theory
---


# Question
Title: Generate a permutation from the high-water marks
Given a permutation, we can define its high-water marks as the indices in which its cumulative maximum increases, or, equivalently, indices with values bigger than all previous values.

For example, the permutation \\$ 4, 2, 3, 7, 8, 5, 6, 1 \\$, with a cumulative maximum of \\$ 4, 4, 4, 7, 8, 8, 8, 8 \\$ has \\$1, 4, 5\\$ as (1-indexed) high-water marks, corresponding to the values \\$4, 7, 8\\$.

Given a list of indices and a number \\$n\\$, generate some permutation of size \\$n\\$ with the list as its high-water marks **in time polynomial in \\$n\\$**.

This is code golf, so the shortest solution in each language wins.

# Test Cases

In all of those except the first, more than one valid permutation exist, and you may output any one of them.

```
1-based high-water mark indices, n -> a valid permutation

[1, 2, 3], 3 -> [1, 2, 3]
[1, 2, 3], 5 -> [2, 3, 5, 4, 1]
[1, 4, 5], 8 -> [4, 2, 3, 7, 8, 5, 6, 1]
[1], 5 -> [5, 4, 3, 2, 1]
[1, 5], 6 -> [4, 1, 3, 2, 6, 5]

```

# Rules

* You can use any reasonable I/O format. In particular, you can choose:
    + To take the input list as a bitmask of size \\$n\\$, and if you do that whether to take the size at all.
    + Whether the input is 0-indexed or 1-indexed.
    + Whether to have the first index (which is always a high-water mark) in the input. When taking a bitmask, you may take a bitmask of size \\$n-1\\$ without the first value. When taking a list of indices, you can have it indexed ignoring the first value.
    + Whether the output is a permutation of the values \\$0,1,...,n-1\\$ or \\$1,2,...,n\\$.
    + To output any non-empty set of the permutations, as long as the first permutation is outputted in polynomial time.
    + To have the cumulative minimum decrease in the given points instead.
    + To have the cumulative operation work right-to-left, instead of left-to-right.
* It is allowed for your algorithm to be non-deterministic, as long as it outputs a valid permutation with probability 1 and there's a polynomial \\$p(n)\\$ such that the probability it takes more than \\$p(n)\\$ time to run is negligible. The particular distribution doesn't matter.
* Standard loopholes are disallowed.

# Answer
> 9 votes
# Nibbles, 5 bytes

```
.,@?:-,_@@

```

Attempt This Online!

Puts the \\$k\\$ highest numbers at the specified indices in ascending order and the remaining numbers at the remaining indices, where \\$k\\$ is the number of marks.

```
[1, 4, 5], 8 -> [6, 1, 2, 7, 8, 3, 4, 5]

```

## Explanation

```
.,@?:-,_@@
.          Map
 ,          range
  @          second input
   ?        find index in
    :        join
     -        list difference
      ,        range
       _        second input
        @      first input
         @    first input

```

If I'm reasoning correctly, the time complexity should be \\$\mathcal O\left(n^2\right)\\$.

# Answer
> 6 votes
# , 23 bytes

*Edit: -9 bytes thanks to Command Master by switching to use a bitmask as input*

```
function(h)rank(h,,"f")

```

Try it online!

Input is simply a bitmask `h`, no need to provide `n` as this is implicitly the length of the bitmask.
The `"f"` (short for `ties="first"`) argument to `rank()` indicates that ties with the same rank should be broken using "increasing values at each index set of ties".

# , 32 bytes

```
function(h,n)rank(1:n%in%h,,"f")

```

Try it online!

Same approach as above, except inputting `h` as the indices of high-water marks, together with `n`. `1:n %in% h` returns a vector of mainly zeros, with ones where the high-water marks should be (in other words, converting the indices to a bitmask).

# Answer
> 6 votes
# Jelly,  ~~4~~  2 bytes

```
ỤỤ

```

A monadic Link that accepts a bitmask identifying the high watermarks and yields a permutation.

**Try it online!** Or see the test-suite.

#### How?

```
ỤỤ - Link: bitmask                        e.g. [1,0,0,1,0,0]
Ụ  - grade-up (indices of sorted values)       [2,3,5,6,1,4]
 Ụ - grade-up (indices of sorted values)       [5,1,2,6,3,4]

```

---

### Previous at 4 bytes (not using a bitmask):

```
ReÞỤ

```

A dyadic Link that accepts the number on the left and the high watermark indices on the right and yields a permutation.

**Try it online!** Or see the test-suite.

#### How?

```
ReÞỤ - Link: n; I                       e.g. n=6; I=[1,4]
R    - range (n)                             [1,2,3,4,5,6]
  Þ  - sort by:
 e   -   exists in (I)?                      [2,3,5,6,1,4]
   Ụ - grade-up (indices of sorted values)   [5,1,2,6,3,4]

```

# Answer
> 4 votes
# Vyxal, 6 bytes

```
ɾ$ÞṖRf

```

Try it Online!

Takes `n` and then a list of indices.

```
ɾ      # range
 $     # swap top two items on the stack
  ÞṖ   # split before indices
    R  # reverse each
     f # flatten

```

# Answer
> 3 votes
# 05AB1E, 8 bytes

```
LDŠåÅ¡í˜

```

Port of @AndrovT's Vyxal answer.

Try it online or verify all test cases.

**Explanation:**

```
L         # Push a list in the range [1, first (implicit) input n]
 D        # Duplicate this list
  Š       # Triple-swap it with the second (implicit) input: [1,n], input-list, [1,n]
   å      # Check for each value of [1,n] whether it's in the input-list
    Å¡    # Split the second [1,n]-list before the truthy indices
      í   # Reverse each inner list
       ˜  # Flatten it to a single list
          # (after which the result is output implicitly)

```

# Answer
> 2 votes
# Pyth, 10 bytes

```
XKSE+-KQQK

```

Try it online!

Takes the indices then the length, runs in \\$\mathcal{O}(n^2)\\$. Uses the same general strategy as most others, putting the \\$n\\$ highest values at the given indices.

### Explanation

```
              # implicitly assign Q = eval(input()) to the indices
 KSE          # assign K = [1, 2, ..., eval(input())]
     -KQ      # elements of K not in Q
    +   Q     # concatenated to Q
XK       K    # translate K from this to K

```

# Answer
> 2 votes
# , 16 bytes

Not enough reputation to comment on Dominic's answer, but using the new anonymous function syntax in R, a few bytes can be shaved off:

`\(h)rank(h,,"f")`

# Answer
> 1 votes
# Python 3, 64 bytes

Uses zero-based indexing

```
f=lambda m,n:sum(([*range(*t)][::-1]for t in zip(m,m[1:]+[n])),[])

```

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

```
m=>n=>m.map(i=>i?++n-eval(m.join`+`):++x,x=0)

```

Attempt This Online!

Takes a bit mask and length. Runs in \\$\mathcal O(n)\\$.

This is probably my first time golfing in JavaScript, please leave suggestions how to improve the code.

*-7 thanks to Kevin Cruijssen, Shaggy and Arnauld*

# Answer
> 1 votes
# Retina, 38 bytes

```
^.+
*
_
$.`¶
^D`
G`.
.+
$&,$:&
N`
.+,

```

Try it online! Takes `n` as the first input and then the element of the 0-indexed list. Explanation: Inspired by @DominicVanEssen's R answer.

```
^.+
*

```

Convert `n` to unary.

```
_
$.`¶

```

Get a range from `0` to `n`.

```
^D`

```

Remove all but the last instance of all duplicates.

```
G`.

```

Remove all blank lines.

```
.+
$&,$:&

```

Append the line index to each value.

```
N`

```

Sort by value.

```
.+,

```

Delete the values, leaving their original indices.

# Answer
> 0 votes
# Python NumPy, 56 bytes

```
def f(m,n):x=m[:1]*range(n);_,*x[m-1]=*x[m-1],n;return x

```

Attempt This Online!

1-based. Expects a numpy array and an integer.

## How?

Populates the output with a 0-based (!) range. Then shifts the values at the marked indices one position to the left ignoring non marked indices and filling the right most position with n. As the left most marked index always is 0, a 0 was lost and an n gained, generating a 1-based permutation.

# Answer
> 0 votes
# Charcoal, 12 bytes

```
ＩＥη⌕⁺⁻…⁰ηθθι

```

Try it online! Link is to verbose version of code. 0-indexed. Explanation: Port of @xigoi's Nibbles answer.

```
  η             Input `n`
 Ｅ              Map over implicit range
   ⌕            Find index of
           ι    Current value in
      …         Range from
       ⁰        Literal integer `0`
        η       To input `n`
     ⁻          Remove elements from
         θ      Input list
    ⁺           Concatenated with
          θ     Input list
Ｉ               Cast to string
                Implicitly print

```

# Answer
> 0 votes
# Japt, ~~11~~ 10 bytes

```
õ ò@VøYÃcÔ

```

Try it

-1 by Shaggy (crossed out 11 is still regular 11)

```
õ ò@VøYÃcÔ
õ          # range [1, input integer]
  ò@   Ã   # partitioned between pairs X, Y where
    VøY    #   Y is contained in input array
        cÔ # reverse each and flatten

```

# Answer
> 0 votes
# JavaScript (Node.js), 39 bytes

```
x=>x.map(t=>!t&&++i,i=0).map(t=>t||++i)

```

Try it online!

Take marks

---
Tags: code-golf, permutations, open-ended-function, restricted-complexity
---