title: Determine if Strings are equal

text:
# Question
Title: Determine if Strings are equal
Your task is **simple**. Determine if one string equals the other (not address, the value) without the use of equality operators (such as `==`, `===`, or `.equal()`) or inequality (`!=`, `!==`) anything similar for other languages. This means anywhere! You may not use these operators anywhere in the code. You may however, you use toggles such as `!exp` as you're not directly comparing the `exp != with something else`.

In addition, you may not use any functions such as strcmp, strcasecmp, etc.

As for comparison operators (`>=`, `<=`, `>`, `<`), they are also **disallowed**. I realize that some answers include this, but I'd really like to see more answers that don't borderline the equality operator.

An example using PHP is shown:

```
<?php

$a = 'string';
$b = 'string';

$tmp = array_unique(array($a, $b));

return -count($tmp) + 2;

```

Simply return true or false (or something that evaluates in the language to true or false like 0 or 1) to indicate if the strings match. The strings should be hardcoded seen in the above example. The strings should not be counted in the golf, so if you declare the variable before hand, don't count the declaration.

# Answer
# Python 49 45 18 22 15 14

## ( + 3 if string variables are considered)

```
print{a:0,b:1}[a]

```

The string should be hard coded at the two occurrences of `a` and one occurrence of `b` surrounded by quotes.

`a` and `b` should be pre-initialized to the strings.

---

# Python shell, 9

## ( + 3 if string variables are considered)

```
{a:0,b:1}[a]

```

Output in shell

```
>>> a = 'string'
>>> b = 'string'
>>> {a:0,b:1}[a]
1
>>> a = 'string'
>>> b = 'stringgg'
>>> {a:0,b:1}[a]
0
>>> {'string':0,'string':1}['string']
1
>>> {'stringggg':0,'string':1}['stringggg']
0
>>>

```

---

Explanation

Creates a dict(hash table) with the key of first and second string. If second string is the same, the value of first is replaced by that of second. Finally, we print the value of first key.

EDIT: OP allowed 0/1 instead of False/True as well as using pre-initialized variables.
> 34 votes

# Answer
# Python (~~17~~ 11):

```
b in a in b

```

(Checks if b is contained in a and a is contained in b, if that wasn't clear from the code.)

## Alternative python: (~~8~~ 7)

derived from Tom Verelst's Go solution:

```
b in[a]

```

Bonus: this works for any type.

EDIT:

Wait a second, just read that you can also directly program in the strings, and don't have to count quotes... (or at least, that what golfscript does). So... Python on par with golfscript? Oh my!

## Alternative alternative Python (~~5~~ 4):

(thanks Claudiu)

```
"string"in["string"]

```

original:

```
"string" in["string"]

```

## Alternative Alternative Alternative Bendy-ruly Python (2):

```
"string"is"string"

```

Nothing was said about comparison **keywords** (This is not a serious submission, just something that occurred to me...)
> 21 votes

# Answer
# JavaScript, 11 10

Strings have to be stored in a and b.

```
!(a>b|a<b)

```

Edit: thanks Danny for pointing out, `|` is enough instead of `||`
> 14 votes

# Answer
# Ruby, 11

```
s = 'string'
t = 'string'
!!s[t]&t[s]

```

Checks if each string is contained within the other.
> 8 votes

# Answer
# Python - 11 (without the strings)

```
>>> a = 'ss'
>>> b = 's'
>>> a in b in a
False

```
> 8 votes

# Answer
## GolfScript (5 chars)

```
'string1''string1'].&,(

```

Fairly straightforward port of the PHP reference implementation. Leaves `0` (=false) on the stack if the strings are the same, or `1` (=true) if they're different.
> 6 votes

# Answer
# C++, ~~63~~ ~~58~~ 56

```
const char* a = "string";
const char* b = "string";
int main(){while(*a**b*!(*a^*b))++a,++b;return!(*a^*b);}

```
> 5 votes

# Answer
# Javascript (45 bytes):

Here is another solution in Javascript.

```
var a='string',b='string',c=!a.replace(b,'');

```

The space is important.

`c` should be `true`.
> 5 votes

# Answer
# coreutils: uniq -d

Just enter your two strings as the standard input of a pipe and `uniq -d | grep -q .` will print nothing but will have a return value of success or error. If you want to print the boolean, just replace with `uniq -d | grep -c .`

How many characters? I let you count; `uniq -d|grep -q .` with no extra spaces has 17 characters in it, but since the whole job is performed by uniq, I would say this solution is a 0-character one in... `uniq` own language!

Actually, `uniq -d` will print one line if the two strings are identical, and nothing if the are different.
> 3 votes

# Answer
## APL (~~8~~ 9)

Update: the old one does not work for strings of different lengths.

```
{∧/∊⌿↑⍺⍵}

```
* `↑⍺⍵`: make a matrix with  on the first line and  on the second line, filling blanks with spaces.
* `∊⌿`: For each column, see if the upper row contains the lower row (as in the old version).
* `∧/`: Take the logical `and` of all the values.

Old one:

```
{∧/⍺∊¨⍵}

```
* `⍺∊¨⍵`: for each combination of elements in  and , see if the element from  contains the element from . Since in a string these will all be single characters, and a string contains itself, this is basically comparing each pair of characters.
* `∧/`: take the logical and of all the values (if all the characters match, the strings are equal)
> 3 votes

# Answer
Strings have to be stored in a and b. Will not work if either is `null`.

# C#, 53

```
string.IsNullOrEmpty(a.Replace(b,"")+b.Replace(a,""))

```

---

# C#, 28

```
a.Contains(b)&&b.Contains(a)

```
> 3 votes

# Answer
### PHP - 49 characters

```
!(strlen($a)^strlen($b)|strlen(trim($a^$b,"\0")))

```
> 3 votes

# Answer
# Python - 12

```
not({a}-{b})

```

This solution uses sets. Subtracting equal sets will result in an empty set, which has a boolean value of False. Negating that will result in a True value for a and b being equal strings.

```
>>> a="string1"
>>> b="string2"
>>> not({a}-{b})
False

>>> a="string"
>>> b="string"
>>> not({a}-{b})
True

```

Edit: Thanks to Peter Taylor for pointing out the unnecessary whitespace.
> 3 votes

# Answer
## C — 62

```
e(char*p,char*q){for(;*p&*q&&!(*p^*q);q++,p++);return!(*p^*q);}

```

Tested. Call as `e(str1, str2)`

Come to think of it, if you don't count the `char*p,char*q`, which seems only fair, it's only 49 bytes :)
> 3 votes

# Answer
## Mathematica / Wolfram Language, 15 bytes

```
2 - Length[{a} ∪ {b}]

```

Pretty self explanatory, sets each string as a set, then checks the length of the union of the two sets. If the strings are the same, returns 1, otherwise returns 0. If I'm allowed to return '2' for "different" and '1' for "same", subtract two bytes.
> 2 votes

# Answer
## Java - 162 147 characters

The idea is to compare the difference of each byte, same bytes will have difference 0. The program will throw `java.lang.ArrayIndexOutOfBoundsException` for when bytes are different (try to access a negative index) or when strings are of different length. It will catch the exception and return 0 (strings not equal), or return 1 otherwise (strings equal).

**Compressed:**

```
String a = "12345";
String b = "12345";
byte[]x=a.getBytes(),y=b.getBytes();int z,i=a.length()-b.length();try{for(byte d:x){z=d-y[i];z=x[-z*z];i++;}}catch(Exception e){return 0;}return 1;

```

**Normal:**

```
String a = "12345";
String b = "12345";
byte[] byteArrA = a.getBytes();
byte[] byteArrB = b.getBytes();

int byteDifference = 0;
int i = a.length() - b.length();

try {
    for (byte aByte : byteArrA) {
        byteDifference = aByte - byteArrB[i];
        byteDifference = byteArrA[-byteDifference*byteDifference];
        i++;
    }
} catch (Exception e){
    return 0;
}

return 1;

```
> 2 votes

# Answer
# Haskell -- 9

```
elem a[b]

```

Note that this, just like many entries here, is just an expression. This is not a Haskell program.
> 2 votes

# Answer
# Prolog 7

```
e(A,A).

```

This makes use of the pattern matching feature in Prolog to unify the 2 arguments to the predicate, which effectively tests for equals equivalence *when there is no unbound variable*.

Sample usage:

```
?- e("abcd", "Abcd").
false.

?- e("abcd", "abcd").
true.

```

Technically speaking, the behavior of this solution is that of unification operator `=/2`, rather than that of `==/2`, which checks for term equivalence. The difference shows when unbound variables are involved. In this solution, when unbound variable is supplied, the predicate will return `true` when unification is successful. In comparison, `==/2` will compare order of term without unification.
> 2 votes

# Answer
## PHP, 68 Bytes

I assume you're prohibited to use **any** comparison operators. So `<` or `>` are included.

The idea is to use bitwise XOR. In different languages this operator has different syntax - I'll show an example for PHP. There it's available with `^`. Unfortunately, its behavior with strings isn't as good as it could be, so you'll need to check string length before. That is because in PHP, xor will strip the longer string down to the length of the shorter string.

Next thing is to work with strings properly, because a single `xor` will not produce a result, available for further operations in PHP. That's why `unpack()` was used. So, the code would be:

```
return !(strlen($a)^strlen($b)) & !array_filter(unpack('c*', $a^$b))

```

It's longer than option with `<` / `>` but it won't use them. Also, the important thing is about PHP type juggling (so empty array will be cast to `false`). Or maybe there's a simpler way to check if an array contain non-zero members (*Edit*: while I've been typing this, there's a good catch with `trim()` in another answer, so we can get rid of array operations)

But I believe there are languages, where we can do just `a ^ b` \- literally, getting the result. If it's `0` (treated from all resulted bytes) - then our strings *are equal*. It's very easy and even more simple than `<` or `>` stuff.
> 2 votes

# Answer
# PHP

```
    $string = 'string';
    isset( ${'string'} );

```

This script may not have any utility, but atleast this provides a way to compare strings.

# PHP

Aother one:

```
    $string = 'something';
    $text   = 'something';
    return count( array( $string => 1 , $text => 1 ) ) % 2;

```
> 2 votes

# Answer
## PHP, 21

This one is doing the job using variable indirection.

```
$$a=$b;!!$$b;

```

Or, if you don't need it to be bool

```
$$a=$b;$$b;

```

**EDIT** : I forgot to handle the case where you try to compare two empty strings, so the code now is

```
$$a=$b;!($a.$b)||$$b;

```

which is 21 chars.
> 2 votes

# Answer
## CPython: 6

```
a is b

```

---

```
>>> a = 'string'
>>> b = 'string'
>>> c = 'STRING'
>>> a is b
True
>>> a is c
False

```

The use of `is` is obviously pretty suspect, but since the task specifically calls out that we're to determine value equality rather than reference equality, and `is` only compares object identity, I feel like it *may* not fall under the list of banned operators.

Of course there's also some question as to whether this is even valid; it works on all of my systems, but it's implementation-specific and probably won't always work if the strings aren't defined by hand in the interactive interpreter.
> 2 votes

# Answer
**C 342 golfed**

```
#include <stdio.h>
#define N 100
#define P(x) printf("%s\n",x)
#define G(x) gets(x)
void e(int x){x?P("y"):P("n");}
int main(){
char s[N],t[N];char *p,*q;int r=0; int n=0,m=0;int i=1;p=s,q=t;
if((p=G(s))&&(q=G(t))){while (*p){n+=i*(int)*p;m+=i*(int)*q;i++;p++;q++;if(!(*q)){break;}}
if(!*p&!*q){if(!(m-n)){r=1;}}e(r);}
return 0;
}

```

Note: Visual Studio complains if you don't use their safe methods eg gets\_s. CodeBlocks with mingw compiles without warnings.

**C 655 not golfed**

Code creates weighted sum of chars for each string. If the difference is zero then they are equal, including 2 empty strings:

```
    #include <stdio.h>
#define N 100
#define P(x) printf(x)
#define G(x) gets_s(x)

void e(int x){ x ? P("equal\n") : P("not equal\n"); }
int main()
{
    char s[N], t[N];//words
    char *p = 0, *q = 0;
    int r = 0; //result 0=false
    int n=0, m=0; //weighted sums
    int i = 1; //char pos start at 1
    if ((p=gets_s(s)) &&
        (q=gets_s(t)))
    {
        while (*p)
        {
            n += i*(int)*p;
            m += i*(int)*q;
            i++;
            p++;
            q++;
            if (!(*q)){
                break;
            }
        }

        if (!*p && !*q){ //both same length strings
            if (!(m - n)){ r = 1; } //weighted sums are equal
        }//else r=0, false=>not equal

        e(r);
    }
    else{
        P("error\n");
    }
    getchar();
}

```
> 2 votes

# Answer
# Python

It's long and it's not beautiful, but this is my first entry!

```
def is_equal(a,b):
    i=0
    a,b=list(a),list(b)
    if len(a)>len(b):
        c=a
        lst=b
    else:
        c=b
        lst=a
    try:
        while i<len(c):
            for j in c:
                if j not in lst[i]:
                    return False
                i+=1
    except IndexError:
        return False
    return True

```
> 2 votes

# Answer
# R (4 chars)

```
'string1'%in%'string2'

```

Or, for an actual function,

## (6 chars)

```
`%in%`

```

which is called with

```
`%in%`(x,y)

```

As R is a vector-based language, is treated as a string and b is treated as a vector of one string, so this is similar to the `elem a[b]`/`a in b in a`/`a in[b]` solutions in spirit.
> 2 votes

# Answer
# grep 14 characters

Of course, I only count the grep code; the two strings are on two consecutive lines in the input (either a pipe or a file or even an interactive session).

```
$ echo -e 'string\nstring' | grep -cPzo "(?s)^(\N*).\1$"
1
$ echo -e 'string\nstring1' | grep -cPzo "(?s)^(\N*).\1$"
0
$ echo -e 'string1\nstring' | grep -cPzo "(?s)^(\N*).\1$"
0

```
> 1 votes

# Answer
# Matlab: 12 chars (after the strings are in variables)

```
~(x*x'-y*y')

```

The code including assignments would be:

```
x='string1'
y='string2'
~(x*x'-y*y')

```
> 1 votes

# Answer
# The very crazy way

Just for the fun, but many ways for making it fail if one thinks about it. More over, don't forget the strings will be EXECUTED by the shell.

```
$ echo -e 'string\nstring1' | sed -e '1s/^/#define /' | cpp | sh 2>/dev/null && echo true
$ echo -e 'string\nstring' | sed -e '1s/^/#define /' | cpp | sh 2>/dev/null && echo true
true
$ echo -e 'string1\nstring' | sed -e '1s/^/#define /' | cpp | sh 2>/dev/null && echo true

```

A good counter-example is comparing "string" as first string and "rm -Rf /" as a second string; just check as root and see: it will say "true" though both strings obviously aren't the same.
> 1 votes

# Answer
# JavaScript \[18 bytes\]

```
(_={})[a]=1,!!_[b]

```

**OR**

```
!!((_={})[a]=_)[b]

```

This will return `true` if `a == b` and `false` if `a =/= b`. The logic behind is creating an object with a value of `a` as a property and returning `1` or `undefined` in case if a property of `b` value exists or doesn't exist in that object.
> 1 votes

# Answer
# JavaScript \[15 bytes\]

```
![a].indexOf(b)

```

This will return `true` if `a == b` and `false` if `a =/= b`. The script is looking for the value of `b` in the array that holds a single element of value of `a`.
> 1 votes

# Answer
## C - ~~86~~ 83

```
main(int i,char**v){return*v[1]&!(*v[1]++^*v[2]++)?main(3,v):!(*--v[1]^*--v[2]);}

```

Obvioulsy not the shortest, but this doesn't work with string variables and instead takes the strings as input from the console. Also, I sort of like the recursive main, even if it's obviously not the shortest version. But certainly the least advisable.
> 1 votes

# Answer
**Python, 7 chars.**

```
b in[a]

```

Where `b` and `a` are strings.
> 1 votes

# Answer
## C++: 104 ~~105~~ characters

```
#include<string>
#include<set>
template<typename T>
int f(T a,T b){std::set<T>S={a};return S.count(b);}

```

EDIT: Saved a character by making it a template function.

Function itself is 51 characters. Other C++ answers already posted are shorter, but I wanted to try one that wasn't also pure C. In fact, this requires C++11. For earlier versions of C++ you can replace `std::set<T>S={a};` with `std::set<T>S(&a,&a+1);` at the expense of an extra 5 characters.
> 1 votes

# Answer
**Excel VBA**

```
Function stringmatch()
a = ""
b = ""
For i = 1 To Len(a)
If Asc(Right(Left(a, i), 1)) - Asc(Right(Left(b, i), 1)) Or Len(a) - Len(b) Then
debug.print "string unnmatch"
Exit Function
End If
Next
debug.print  "string match"
End Function

```
> 1 votes

# Answer
## Java (235 characters for golfed version at bottom).

Strings are not hardcoded, but this is a trivial change.

```
   public boolean areEqual(String a, String b) {
    int[] q = new int[1];
    int i = 0;
    try {
        while (true) {
            noOp(q[(int) a.charAt(i) - (int) b.charAt(i)]);
            i++;
        }
    } catch (Error e) {
        try {
            a.charAt(i);
        } catch (Error e2) {
            try {
                b.charAt(i) {catch(Error e3){
                    return true;
                }
                }
            }

            return false;
        }
        return true;
    }
}

public void noOp(int i) {
}

```

Traverses both strings, using the difference in `char`s to select an array index (which is 0-based). No in-loop comparisons or Math.max used. Using `Error` as a throwable instead.

Golfed for use under certain circumstances (instantiated class, used from same package):

```
boolean a(String a,String b){boolean t=true,f=!t;int[]q={1};int i=0;try{while(t){q[(int)a.charAt(i)-(int)b.charAt(i)];i++;}}catch(Error e){try{a.charAt(i);}catch(Error z){try{b.charAt(i){catch(Error g){return t;}}}return f;}return t;}}

```
> 1 votes

# Answer
## Groovy 347

```
def compare(str1,str2){
    def str1val = 0
    def str2val = 0

    MessageDigest md5 = MessageDigest.getInstance("MD5")
    md5.digest(str1.getBytes("UTF-8")).each{ str1val += it*2 }
    md5.digest(str2.getBytes("UTF-8")).each{ str2val += it*2 }

    if(!(str1val-str2val)) {
        return true
    } else {
        return false
    }
}

```
> 1 votes

# Answer
# Perl - 10

```
/^\Q$w\E$/

```

The input is in `$_` and `$w`. The output is stored in `$&`.
> 1 votes

# Answer
# APL (Dyalog Extended), 4 bytesSBCS

Anonymous tacit infix function. Requires `⎕IO←0`

```
~⍳⍥⍮

```

Try it online!

`⍥⍮` put each argument into a list

index of right list's elements in left list (0 if match, 1 if not)

`~` logical NOT
> 1 votes

# Answer
# PowerShell, 30 bytes

```
param($a,$b)$a-in$b-and$b-in$a

```

Try it online!

Takes two string inputs as command line parameters, `-a` and `-b`.

# PowerShell, ~~20~~ 16 bytes

-4 bytes thanks to @mazzy!

```
!($args|gu).Rank

```

Try it online!

Alternate answer, takes two strings as commandline arguments.
> 1 votes

# Answer
# Python, 79

```
a=list(a)
b=list(b)
for i in range(len(a)):
 if ord(a[i])-ord(b[i])<0:
  print 'n'

```
> 0 votes

# Answer
## Perl, 24 bytes

```
$r=!(-1+keys{$a,1,$b,1})

```

The two strings are given in `$a` and `$b`. The result is stored in `$r`.

The trick is using a hash array. If the strings are equal, then only one hash entry is created.

---

A standalone variant that gets the string from STDIN and returns 0, if the strings match and 1 otherwise:

```
$h{<>}=$h{<>}=1;exit -1+keys%h

```
> 0 votes

# Answer
## Python - 52 chars without strings (76 with strings)

The `in` operator might be skirting the edges, but the rules disallow strict equality comparison, not similarity comparison.

```
a="string"
b="string"
x=a in b and not(len(a)-len(b)>0 or len(a)-len(b)<0)

```
> 0 votes

# Answer
### Python 2 - ~~50~~ 54 (including strings)

Thanks to Ace for way around the "==" issue

```
a='string'
b='string'
not(len(''.join(set(a+b)))-len(a))

```

Output

```
True

```

Non-equal strings

```
a='string'
b='String'
not(len(''.join(set(a+b)))-len(a))

```

Output

```
False

```
> 0 votes

# Answer
# Ruby, 21

Online version

Strings have to be stored in `a` and `b`:

```
!!(a+b=~/^(#{a})\1$/)

```

Checks if the concatenation of `a` and `b` contains `a` twice.
> 0 votes

# Answer
## D 30

```
string a="somestring";
string b="somestring";

return !reduce!"a|b"(a[]^b[]);

```
> 0 votes

# Answer
## Python 15 - 2( if you hard code the string in the solution) = 13

```
>>> s = 'string'
>>> t = 'string'
>>> 1 is len({s,t})
True
>>> s = 'string1'
>>> t = 'string2'
>>> 1 is len({s,t})
False

```

## Python 17

```
>>> s = 'string'
>>> t = 'string'
>>> s in t and t in s
True
>>> s = 'string1'
>>> t = 'string2'
>>> s in t and t in s
False

```
> 0 votes

# Answer
## Perl, 25 bytes

```
$r="$a$b"=~/^(\Q$a\E)\1$/

```

The input is expected in variables `$a` and `$b`. The result is stored in `$r`. It uses a regular expression to check, whether the concatenation `"$a$b"` is a duplicate of `$a`.
> 0 votes

# Answer
# Python (7)

Assuming strings are stored in variables `a` and `b`:

```
a<=b<=a

```
> 0 votes

# Answer
## Emacs Lisp

```
(split-string-and-unquote a b)

```

returns nil when a == b, something else when a != b

```
(print (if (split-string-and-unquote a b) "not equal..." "equal!"))

```

If I'm doing string work in elisp I use the popular package s.el in which it could be written a little shorter and without a negated output

```
(not (s-split a b t))

```
> 0 votes

# Answer
## Java - 193

```
new int[]{0,1,0}[new BigInteger(a.getBytes()).subtract(new BigInteger(b.getBytes())).signum()+1]

```

No comparison operators at all, not even a `<` or `>`.
> 0 votes

# Answer
# C - 45 characters

```
r;main(){ // 9 chars here
    char *a = "str2";
    char *b = "str1";
while(r+=*a^*b,*a++**b++);return!r;} // 36 more here

```
> 0 votes

# Answer
# C++ - ~~66~~ ~~57~~ 53

```
int c(char*a,char*b){return *a-*b?0:*a?c(++a,++b):1;}

```

with the ungolfed version:

```
int mystrcmp( char* a, char* b )
{
  // If the characters don't match, we're done
  if( *a - *b )
  {
      return 0;
  }

  // If they do match, and both were nulls, we are done
  if( !*a )
  {
      return 1;
  }

  return mystrcmp( ++a, ++b );
}

```

Driver program in original post below.

---

*Old version:* The golfed version:

```
int c(char*a, char*b){while(*a|*b)if(*a++-*b++)return 0;return 1;}

```

Here is a full driver program with comments:

```
#include <iostream>

using std::cout;
using std::endl;

int mystrcmp( char* a, char* b ) {
   // The comparison will continue as long as both *a and *b are not '\0'.
   // If one of them goes '\0' but the other does not, the strings are not
   // of equal length and at that point we will return 0.
   while( *a | *b ) {
     // Compare the current character and return 0 if they are not equal.
     // *a++ will return the value of *a and then increment the pointer -
     // see http://stackoverflow.com/questions/9255147/does-p-increment-after-dereferencing
     if(*a++ - *b++) {
       return 0;
     }
   }

   // If we got here, both strings are equal up to and including the last '\0'.
   return 1;
}

int main()
{
   // Prints 1
   cout << mystrcmp("Hello.", "Hello.") << endl;

   // Prints 1
   cout << mystrcmp("Hello, world!", "Hello, world!") << endl;

   // Prints 0
   cout << mystrcmp("Hello", "Hello.") << endl;

   // Prints 0
   cout << mystrcmp("Hello.", "Zello.") << endl;

   // Prints 0
   cout << mystrcmp("Hello", "Hallo") << endl;

   // Prints 0
   cout << "Hello World" << endl;

   return 0;
}

```
> 0 votes

# Answer
## C++ 30

```
#include<string>
std::string a = "test", b = a;
int main(){return!(a<b||a>b);}

```

---

I'm not counting the first two lines because:

> The strings should not be counted in the golf.

And here are some tests.
> 0 votes

# Answer
# Delphi (412 83 75)

Can probably be done shorter but was fun to do, going to see if i can get some off.
**412 -\> 83** Cant believe I missed this... Checks if s1 is in s2 and if s2 is in s1. Saved 329 chars *Cheers*
**83 -\> 75** Thanks to Manatwork. Changed check if s1 is in s2 and other way around. Saved 8 characters

```
const s1='string12';s2='string12';begin Write(Pos(s1,s2)*Pos(s2,s1)>0);end.

```

### Ungolfed

```
const
  s1='string12';
  s2='string22';
begin
  Write(Pos(s1,s2)*Pos(s2,s1)>0);
end.

```
> 0 votes

# Answer
## Dart - 15

Strings are stored in `a` en `b`.

```
[a].contains(b)

```

`[a]` creates a `List` with `a`.
> 0 votes

# Answer
## Q - \[3 bytes\]

```
a:"string"
b:"string"

a~b

```

I think this is a valid answer as ~ isn't an equals operator. From a Q tutorial:

> ~ asks whether two entities have the same contents.
>
> http://kx.com/q/d/primer.htm
> 0 votes

# Answer
# C#

I know there's already a C# answer, I just wanted to show other options. :)

## boolean:

* 51

```
!Convert.ToBoolean(new[]{a,b}.Distinct().Count()-1)

```

## 1 or 0:

* 32

```
-new[]{a,b}.Distinct().Count()+2

```
> 0 votes

# Answer
**C#**

```
void Main()
{
    Console.WriteLine(StringEqual("pie","pie")); // true
}

bool Equals(int a,int b)
{
    var aBytes = BitConverter.GetBytes(a);
    var bBytes = BitConverter.GetBytes(b);

    return aBytes.SequenceEqual(bBytes);
}

bool StringEqual(string a,string b)
{
    int i = 0;
    return a.All((c) => Equals((int)c,(int)b[i++]));
}

```
> 0 votes

# Answer
**C#**

I already posted the answer But just found a number of ways in C#

```
 var b = "abcdef";
 var a = "abcdef";
 // the best one is this.
 bool repace = a.Replace(b, "").Length < 1 && b.Replace(a, "").Length < 1;
 bool contsins = ("a" + a).Contains(b) && ("b" + b).Contains(a);

```
> 0 votes

# Answer
## Javascrpt: 38 chars (without a-b declarations) || 31 without alert()

```
a="string";
b="string";

o={};o[a]=0;alert(o.hasOwnProperty(b))

```

sets an object key named the value of *a* -- checks for a key named the value of *b* in that object.

without alert:

```
o={};o[a]=0;o.hasOwnProperty(b)

```
> 0 votes

# Answer
# J - 6 char

A J expression which tests for string equality without testing for string equality? Here's one:

```
e./a;b        NB. is a boxed in b boxed?

```

Not good enough? Want some more options? Go ahead, have some more, J has plenty.

```
<:#~.a;b      NB. (the number of the unique items among the two) - 1
1-{:~:a;b     NB. 1 - (whether the second item is unique, given the first)
2-#]/.~a;b    NB. 2 - (the number of piles the strings will sort themselves into)
+/(/:*\:)a;b  NB. is sorting them forwards the same as sorting them backwards?
A.|./:\:~a;b  NB. will sorting them forwards after sorting them backwards do anything?

```

The common subexpression here, `a;b`, is `a` linked to `b`. It puts `a` and `b` into boxes before appending them into a list. This is J's closest approximation to non-rectangular arrays: if you just tried to put the two strings in a 2-item list, the shorter would be padded with spaces on the right, which could result in you comparing `'a'` and `'a '` as equal.
> 0 votes

# Answer
C#, pretty straightforward.

```
static bool equal(string s1, string s2)
{
    int i = 0;
    try { while (true) if (!isZero((int)s1[i] - (int)s2[i++])) return false; }
    catch { }
    return isEnd(s1, i) && isEnd(s2, i);
}

static bool isEnd(string s, int i)
{
    try { char c = s[i]; return false; }
    catch { }
    return true;
}

static bool isZero(int x)
{
    try { int y = 1 / x; return false; }
    catch { }
    return true;
}

```
> 0 votes

# Answer
Bash, 14

Assuming strings are in A and B, then

```
[ -z ${A/$B} ]

```

will return a true (0) or false (1) value in $?.

How do I use it?

```
A="string";B="string";[ -z ${A/$B} ]&&echo same

```

How does it work?

${A/$B} replaces $B in $A with nothing. Only if $A=$B then result will be an empty string. \[ -zn X \] tests for empty or null string and sets $? to 0 if empty.

Update: should be -z not -n in test.
> 0 votes

# Answer
## C, 48 chars

```
c(char*a,char*b){return*a++-*b?0:!*b++||c(a,b);}

```

Recursion is often shorter than a loop.
Subtraction easily replaces a comparison.
> 0 votes

# Answer
**Lua, 147**

```
a="string" b="string" y=string.byte s=string.sub m=math.abs c=1 for i=1,math.max(#a,#b) do d=y(s(a,i)) e=y(s(b,i))if not((d and e)and(m(d) - m(e)))then c=0 break end end

```

Assumes *a* and *b* are the strings. *c* should be 1 (true)
> 0 votes

# Answer
## Python 56

```
a = "string"
b = "string"

not any(ord(x)*len(a)-ord(y)*len(b) for x,y in zip(a,b))

```

A bit longer than the shortest Python examples, but probably about the best I can do without using in or set notation (the former should probably be excluded, the latter has already been employed as succinctly as possible).
> 0 votes

# Answer
# Rebol, 22

```
all[find a b find b a]

```

This will return `none` if strings are different.

Example usage in Rebol console:

```
>> a: "string"
== "string"

>> b: "string"
== "string"

>> c: "stringstring"
== "stringstring"

>> all [find a b find b a]
== "string"

>> all [find a c find c a]
== none

```

By default Rebol is case insensitive. So use `find/case` to enforce stricter test:

```
>> b: "STRING"
== "STRING"

>> all [find a b find b a]
== "STRING"

>> all [find/case a b find/case b a]
== none

```
> 0 votes

# Answer
# Javascript

Where `x = z` and `x != y`:

```
if( x.match(RegExp(z)) ) // Evaluates to True

if( x.match(RegExp(y)) ) // Evaluates to False

```
> 0 votes

# Answer
## Windows Batch (47)

```
@echo.>%1
@if exist %2 (exit /b 0)
@exit /b 1

```

This should be run in an empty directory each time ;)

It types a blank line into a file named with the first argument, and then checks if the second argument exists. For hardcoded strings, either replace the %1 and %2 or add `@if "%1"=="" %0 string1 string2` to the top of the file.
> 0 votes

# Answer
# Java

```
import java.util.HashSet;
public class Equals {
    public static boolean equals(String s1, String s2){
        HashSet<String> sSet = new HashSet<>();
        sSet.add(s1);
        return !sSet.add(s2);
    }
    public static void main(String[] args) {
        System.out.println(equals("Apple","Tpple"));
    }
}

```
> 0 votes

# Answer
# perl, 20 bytes

Today I'm serving up perl two ways, saving a byte or two off the other perl solutions seen here. First, with hash slices, for 20 bytes:

```
@x{$a,$b}=();$_=%x%2

```

and then a port of the clever python solution above (also 20 bytes)

```
$_={$a,0,$b,1}->{$a}

```
> 0 votes

# Answer
# C - 59

```
e(char*l,char*r){for(;*l&*r&&!(*l++^*r++););return!*l&!*r;}

```
> 0 votes

# Answer
# Ruby (18)

This one is a script using the exit status instead of a function's return value: 0 is success, 1+ is failure.

```
exit$*.uniq.size-1

```

Usage:

```
$ ruby equality.rb a b
$ echo $?
1
$ ruby equality.rb a a
$ echo $?
0

```
> 0 votes

# Answer
# R, 4

`"string1"%in%"string2"` equivalent to `is.element("string1", c("string2"))`
> 0 votes

# Answer
## D - ~~34~~ 27 bytes

```
!any!"a.length"(split(a,b))

```

Example use:

```
import std.stdio,std.string,std.algorithm;

void main() {
    auto a = "abcd";
    auto b = "abcd";

    writeln(!any!"a.length"(split(a,b)));
}

```

Output:

```
true

```
> 0 votes

# Answer
# ~-~! (No Comment) - 1

### (might not be legal)

```
|string|-|string|

```

`%` if they're equal, anything else if they're not. There's an issue though; ~-~! only accepts `%` or `~` (0 or 1) for conditionals; if it's neither, it throws an error. So you'd have to use `==~` to actually be able to use it properly. I don't think there /is/ a way to do this in ~-~! without the equality operator if this isn't allowed.
> 0 votes

# Answer
# Excel VBA, 124 Bytes

Subroutine that takes variant input `a` and `b` of the assumed type `variant\string` and outputs as a boolean variable to the VBE immediates window

```
Sub m(a,b)
c=1
For i=1To Len(a)
If Asc(Right(Left(a,i),1))-Asc(Right(Left(b,i),1)) Or Len(a)-Len(b) Then:c=0:Exit For
Next
Debug.?CBool(c)
End Sub

```
> 0 votes

# Answer
# Operation Flashpoint scripting language, 7 bytes

```
a in[b]

```

Strings are stored in variables `a` and `b` (as allowed by the question).

Interestingly, even if direct comparison would be allowed, this would be the only valid solution, because `a==b` performs a case-insensitive comparison, whereas the built-in `in` uses case-sensitive comparison for strings internally.
> 0 votes

# Answer
# \[shell\], 22 bytes (almost any shell (sh,bash,ksh,zsh, etc), certainly POSIX ones)

```
a=string
b=string

c=${a#"$b"}
echo ${#c}

```

Try it online!

Will output 0 if strings are equal, 1 if different. The less robust solution that doesn't deal with (`*`, `?` and `[` in `$b`) is two bytes shorter:

```
c=${a#$b}
echo ${#c}

```
> 0 votes

# Answer
# PYTHON, 25

```
not bool(a.replace(b,''))

```

Explanation

An empty string is false in Python, so if we replace b with '' and check if it is empty that gives use true/false.
> 0 votes

# Answer
## C#

```
var b="string";
var a="string";
return  Regex.IsMatch(b, "^.{" + a.Length + "}$") && Regex.IsMatch(b,"^" + a + "$");

```
> -1 votes

# Answer
# Java - 54

First Golf: Since all string's HashCode is the same with the same content, it can be useful.

```
(int)Math.abs(Math.signum(s.hashCode()-b.hashCode()));

```
> -1 votes

---
Tags: code-golf
---


# Question
Title: Determine if a number is less than another
# Introduction

Your job is to write a function or program that detects if a number `a` is less than a number `b`.

**But...** You are not allowed to use built-in alternatives for equals, less than, greater than, less than or equal to, greater than or equal to, or not equal to operators. (Writing your own implementation is allowed.) Similar alternative methods/alternatives in other languages that are designed to replace those operations are also restricted.

You **are** allowed to use operators that are not banned, e.g. bitwise operators and the not operator (but it would be better if your answer did not have the not operator).

# Challenge

Simply return a truthy or falsy value (or something that evaluates in the language to true or false like 0 or 1) to indicate whether `a` is less than `b`. The winner of the challenge can be determined by the shortest code. External sources are not allowed, but anonymous functions are. Explaining your answer is not mandatory, but encouraged.

# Example using Javascript:

```
(a,b)=>!!Math.max(0,b-a) //remove the !! for truthy and falsy numbers
/*Explanation
(a,b)                    Parameters a and b
     =>                  Function is
       !!                returns true if truthy and false if falsy
         Math.max(0,b-a) returns the greater number, 0 or b-a
*/

```

# Examples of Input and Output

```
Input | Output
------|-------
1, 3  | true
2, 2  | false
3, 2  | false

```

# Answer
> 3 votes
# APL (Dyalog Unicode), 2 bytesSBCS

Anonymous tacit prefix function. Requires `⎕IO←0`

```
⊃⍒

```

Try it online!

gives the "grade". The indices into the argument that would stably sort it in descending order

* If the first element is less than the second, it gives `[1,0]`
* If the the elements are equal, it gives `[0,1]`
* If the second element is less than the second, it gives `[0,1]`

picks the first element of that

* If the first element is less than the second, it gives `1`
* If the the elements are equal, it gives `0`
* If the second element is less than the second, it gives `0`

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


title: Maximal 2-distance Sets

text:
# Question
Title: Maximal 2-distance Sets
In the plane (\\$\mathbb R^2\\$) we can have at most five distinct points such that the distances from each point to every other point (except itself) can assume at most two distinct values.

An example of such an arrangement is a regular pentagon - the two different distances are marked with red and blue:

### Challenge

Given a number \\$n = 1,2,3,\ldots\\$ find the size \\$s\_n\\$ of the largest 2-distance set in \\$\mathbb R^n\\$.

### Definitions

* We measure the *Euclidean distance* \\$d(a, b) = \sqrt{\sum\_{i=1}^n (a\_i - b\_i)^2}\\$.
* A set \\$S \subseteq R^n\\$ is a 2-distance set if the number of distinct distances \\$| \\{ d(a,b) \mid a,b \in S, a \neq b\\}| = 2\\$.

### Details

Any output format defined in is allowed.

### Examples

```
  n =  1, 2, 3,  4,  5,  6,  7,  8
s_n =  3, 5, 6, 10, 16, 27, 29, 45

```

This is OEIS A027627, and these are all the terms that we know so far. Answers to this challenge are expected to be able to find *any* term of this sequence - given enough ressources - not just the first eight.

# Answer
# Mathematica, ~~220~~ 218 bytes

```
For[n=1,1>0,n++,For[m=1,1>0,m++,x=Array[a,{m,n}];d=Table[(Norm[x[[i]]-x[[j]]]^2-1)*(Norm[x[[i]]-x[[j]]]^2-y)==0,{i,1,m-1},{j,i+1,m}];If[Not[CylindricalDecomposition[Flatten@{d,y>0},Flatten@{y,x}]],Break[]]];Print[m-1]]

```

Try it online! Un-golfed version:

```
For[ n = 1, 1>0, n++,
  For[ m = 1, 1>0, m++,
   x = Array[a, {m, n}];
   d = Table[(Norm[x[[i]] - x[[j]]]^2 - 1)*(Norm[x[[i]] - x[[j]]]^2 -
         y) == 0, {i, 1, m - 1}, {j, i + 1, m}];
   If[Not[
      CylindricalDecomposition[Flatten@{d, y > 0}, Flatten@{y, x}]],
      Break[]]
  ];
  Print[m - 1]
]

```

In this code, we apply a key tool from real algebraic geometry. A semialgebraic set is a subset of \\$\mathbb{R}^d\\$ defined by polynomial equalities and inequalities. We may identify the set of 2-distance subsets of \\$\mathbb{R}^n\\$ of cardinality \\$m\\$ with a semialgebraic subset of \\$\mathbb{R}^{mn+2}\\$. We force one of the distances to equal 1 without loss of generality, which means our semialgebraic set is a subset of \\$\mathbb{R}^{mn+1}\\$. We denote the other distance (squared) by \\$y\\$.

For which values \\$Y\subseteq\mathbb{R}\\$ of \\$y\\$ does there exists a size-\\$m\\$ subset of \\$\mathbb{R}^n\\$ with squared distances \\$\\{1,y\\}\\$? This can be answered with the help of Tarski--Seidenberg, which says that the projection of any semialgebraic set is semialgebraic. In our case, this means there is some univariate polynomial \\$p\\$ and relation \\$\*\in\\{=,\<,\leq\\}\\$ such that \\$Y=\\{y\in\mathbb{R}:p(y)\*0\\}\\$. This projection may be accomplished using cylindrical algebraic decomposition (CAD), which enjoys an implementation in Mathematica.

Given a set of polynomial equalities and inequalities, as well as an ordered list of variables, Mathematica's implementation returns either an explicit description of every point in the corresponding semialgebraic set, or `False` if the set is empty. In the above code, we run CAD for increasingly larger values of \\$m\\$ until we get `False`, at which point we know that \\$s\_n=m-1\\$. Sadly, the runtime of CAD is doubly exponential in the number of variables, and so we shouldn't expect this approach to determine \\$s\_9\\$ any time soon. In fact, a minute of runtime only gives \\$s\_1=3\\$.
> 5 votes

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


title: Shorten String as Much as Possible

text:
# Question
Title: Shorten String as Much as Possible
# Introduction

In a list of strings, there is a certain length you can shorten strings to before they become indistinguishable. This is a pretty bad explanation, so here is an example.

1. `['hello', 'help', 'helmet']`
2. `['hell', 'help', 'helme']`
3. `['hell', 'help', 'helm']`
4. `['hel', 'hel', 'hel'] <- At this point the strings are indistinguishable`

# Challenge

Given a list of strings, you program must shorten them until just before any of them become indistinguishable. Shorting is defined as removing one character from the end of a string. To shorten a list of strings by one remove the last character from all of the longest strings in the list, or, if all strings are the same length, every string in the list. For example, given the above input, your program would output `['hell', 'help', 'helm']`. If the strings cannot be shortened, or are already indistinguishable, your program should just output the list unchanged. If, at any point, shortening the strings in the list would make some, but not all, of the strings indistinguishable, you program should still output the list as is, instead of shortening it more.

*Note for those who are wondering: If multiple strings can be shortened in the list, they should all be shortened.*

* Your program may take input in any format you like, as long as it is one of the default I/O methods. Input can be of any encoding, but must be a valid UTF-8 string, or your language's equivalent, as can the list of strings. The strings will never be empty, but they might be of different lengths. They will always have at least one common character or be all the same length. There are no restrictions on string content, other than this. The list can also be of any length.
* The same goes for output: you may use any of the default I/O methods. Output can be of any encoding and type, just like the input. All strings in the output should be the same length.

# Example I/O

* `['hello', 'help', 'helmet']`
`['hell', 'help', 'helm']`
* `['like', 'likable', 'lick']`
`['like', 'lika', 'lick']`
* `['hello', 'hello', 'hello']`
`['hello', 'hello', 'hello']`
* `['a1', 'a2', 'bb']`
`['a1', 'a2', 'bb']`
* `['farm', 'farms', 'farmer']`
`['farm', 'farms', 'farmer']`
* `['ape', 'bison', 'caterpillar']`
`['a', 'b', 'c']`
* `['', '', '']`
`['', '', '']`

# Scoring

This is , so the shortest answer in bytes wins!

# Answer
> 1 votes
# Charcoal, 54 bytes

```
≔⌊ＥθＬιζ≔⌈ＥθＬιδ≔ＥδＥθ…λ⎇‹ιζι⌈⟦ζ⁻⁺ιＬλδ⟧η≔Φη⬤ι⁼№ιλ¹η⎇η§η⁰θ

```

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

```
≔⌊ＥθＬιζ≔⌈ＥθＬιδ≔Ｅδ

```

Get the length of the shortest and longest strings, and loop over the latter.

```
Ｅθ…λ⎇‹ιζι⌈⟦ζ⁻⁺ιＬλδ⟧η

```

Trim each string appropriately; the longest string simply trims a character each time but shorter strings stop when they reach the length of the shortest string, until finally the longest string joins them and all the strings can be trimmed again.

```
≔Φη⬤ι⁼№ιλ¹η

```

Filter out the results with indistinguishable prefixes.

```
⎇η§η⁰θ

```

Print the shortest distinguishable prefixes, or failing that, the original strings.

# Answer
> 0 votes
# Jelly, (11?) 18 bytes

This follows the example given in the question rather than "To shorten a list of strings by one remove the last character from all of *the longest strings* in the list, or, if all strings are the same length, every string in the list."

```
Ṗ€µẈnṂ$TȯJµ¦ƬQƑƇṪȯ

```

**Try it online!** Or see the test-suite.
(Both use the footer to format the resulting list of strings).

### How?

```
Ṗ€µẈnṂ$TȯJµ¦ƬQƑƇṪȯ - Link: list, S
            Ƭ      - collect up until a fixed point applying:
           ¦       -   sparse application...
  µ       µ        -   ...to indices: this monadic chain:
   Ẉ               -       length of each
      $            -       last two links as a monad:
     Ṃ             -         minimum
    n              -         not equal (vectorises)
       T           -       truthy indices
         J         -       range of length (of current list) - i.e. all indices
        ȯ          -       logical OR
Ṗ€                 -   ...action: pop each
               Ƈ   - filter keep those for which:
              Ƒ    -   is invariant under:
             Q     -     deduplicate
                Ṫ  - tail (0 if none remain)
                 ȯ - logical OR with S (for the 0 case)

```

---

If the text is correct rather than the example then this works for **11 bytes**:

```
ḣ€ⱮẈṀ$QƑƇḢȯ

```

A monadic Link accepting a list which yields a list.

Try it online! Or see the test-suite.
(Both use the footer to format the resulting list of strings).

### How?

```
ḣ€ⱮẈṀ$QƑƇḢȯ - Link: list, S
     $      - last two links as a monad - f(S):
   Ẉ        -   length of each
    Ṁ       -   maximum
  Ɱ         - map across (implicit range [1..m]) applying:
ḣ€          -   head each to index
        Ƈ   - filter keep those for which:
       Ƒ    -   is invariant under:
      Q     -     deduplicate
         Ḣ  - head (0 if none remain)
          ȯ - logical OR with S (for the 0 case)

```

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


# Question
Title: Decode ascii and reversed words sentence
In a challenge of CodingGame, there is a challenge that ask you to decode a string composed by reversed words ('Hello world' \> 'olleH dlrow') then each characters converted into ascii value separeted by space:

```
>>> decode('111 108 108 101 72 32 100 108 114 111 119 32 41 58')
Hello world :)

```

The challenge is to be the fastest to write the `decode` function, but I later tried to write it with the fewest character possible.

Here is my result (104 characters):

```
def decode(m,s=' '):return s.join([w[::-1]for w in(''.join([chr(int(c))for c in m.split(s)]).split(s))])

```

The name of the function doesn't matter, it can be shorter, but only rename variable isn't good enough for an answer.

Is it possible to improve this result ?

# Answer
> 2 votes
# Python 3, 75 bytes

```
lambda a:' '.join(''.join(map(chr,map(int,a.split())))[::-1].split()[::-1])

```

Try it online!

# Python 3, 70 bytes

If taking input from STDIN and outputing to STDOUT is fine then it takes only 70 bytes this is mostly because the spread operator (`*`) is shorter than `' '.join()`

```
print(*''.join(map(chr,map(int,input().split())))[::-1].split()[::-1])

```

Try it online!

# Answer
> 6 votes
### Use lambdas

```
def f(a,b):return c

```

can be shortened to

```
f=lambda a,b:c

```

(the `f=` can also be removed per CGCC site standards)

### Remove excess `[]`s

```
x.join([a for b in c])

```

can be

```
x.join(a for b in c)

```

since join can take a generator instead of a list

### Split is on spaces by default

*Thanks ElPedro for reminding me about this*

So the `split(' ')`s can be shortened, which in turn means the `s=' '` doesn't help (and it only broke even in the first place).

### Take input from STDIN and output to STDOUT

`print` will automatically print arguments with space as a separator if you use `*` to unpacks the sequence/collection into positional arguments, and taking input via `input()` is shorter. Also, setting `s` to space doesn't actually save any bytes.

Altogether, this is 79 bytes:

```
print(*[w[::-1]for w in(''.join(chr(int(c))for c in input().split()).split())])

```

Try it online!

or, if you're dedicated to having a function, 82 bytes:

```
lambda m:' '.join(w[::-1]for w in(''.join(chr(int(c))for c in m.split()).split()))

```

Try it online!

plus seven or so characters if you really need the function to be called `decode`

# Answer
> 5 votes
# Python 2, 78 bytes

```
lambda m:' '.join(x[::-1]for x in''.join(map(chr,map(int,m.split()))).split())

```

Try it online!

**Edit** changed to a Python 2 answer as the `lambda` is shorter than the `print`/`input` version in Python 2.

This uses a couple of `map`s to get the list of characters which we then `join` on "", `split` again on space, reverse each element then re`join` again on space for 78. Also works in Python 3.

Just a pity that it needs so many brackets :-(

---
Tags: code-golf, tips, python
---


# Question
Title: Summation under Zeckendorf Representation
Zeckendorf's theorem shows that every positive integer can be uniquely represented as a sum of non-adjacent Fibonacci numbers. In this challenge, you have to compute the sum of two numbers in Zeckendorf representation.

---

Let Fn be the *n*-th Fibonacci number where

> F1 = 1,
> F2 = 2 and
> for all *k* \> 2, F*k* = F*k* \- 1 \+ F*k* \- 2.

The *Zeckendorf representation* Z(*n*) of a non-negative integer *n* is a set of positive integers such that

> *n* = Σ*i* ∈ Z(*n*) F*i* and
> *i* ∈ Z(*n*) *i* \+ 1 ∉ Z(*n*).

(in prosa: the Zeckendorf representation of a number *n* is a set of positive integers such that the Fibonacci numbers for these indices sum up to *n* and no two adjacent integers are part of that set)

Notably, the Zeckendorf representation is unique. Here are some examples for Zeckendorf representations:

> Z(0) = ∅ (the empty set)
> Z(1) = {1}
> Z(2) = {2}
> Z(3) = {3} ({1, 2} is not the Zeckendorf representation of 3)
> Z(10) = {5, 2}
> Z(100) = {3, 5, 10}

In this challenge, Zeckendorf representations are encoded as bit sets where the least significant bit represents if `1` is part of the set, etc. You may assume that the Zeckendorf representations of both input and output fit into 31 bits.

Your task is to compute Z(*n* \+ *m*) given Z(*n*) and Z(*m*). The solution with the shortest length in octets wins.

You can find a reference implementation written in ANSI C here. It can also be used to generate Zeckendorf representations or compute a number from its Zeckendorf representation.

Here are some pairs of sample input and output, where the first two columns contain the input and the third column contains the output:

```
73865           9077257         9478805
139808          287648018       287965250
34              279004309       279004425
139940          68437025        69241105
272794768       1051152         273846948
16405           78284865        83888256
9576577         4718601         19013770
269128740       591914          270574722
8410276         2768969         11184785
16384           340             16724

```

# Answer
# K (ngn/k), ~~45 43 42~~ 41 bytes

```
{2/<':(+/F@&+/'|2\x){y!x}\|F:64(+':1,)/0}

```

Try it online!

@Bubbler's algorithm

`{` `}` function with argument `x`

`64(` `)/0` do 64 times, using 0 as initial value:

* `1,` prepend 1
* `+':` add each prior (leave the first element intact)

`F:` assign to `F` for "fibonacci sequence"

`|` reverse

`(`..`){y!x}\`.. starting with the value on the left, compute cumulative remainders (left-to-right) for the list on the right. the value on the left is the plain sum of the inputs without zeckendorf representation:

* `2\x` binary encode the inputs. this will be an nbits-by-2 matrix
* `|` reverse
* `+/'` sum each
* `&` where are the 1s? - list of indices. if there are any 2s, the corresponding index is repeated twice.
* `F@` array indexing into `F`
* `+/` sum

`<':` less than each prior (the first of the result will always be falsey)

`2/` binary decode
> 5 votes

# Answer
# APL (Dyalog Extended), 39 bytes

```
⊥1↓⍧|/⌽(+/g[⍸⌽+/⊤⎕]),↑,\⌽g←(2+/,)⍣38⍨⍳2

```

Try it online!

Changed into a full program taking one argument of length 2, and also changed the Fibonacci generator. Thanks to @ngn for lots of ideas.

Uses `⎕IO←0` so that `⍳2` evaluates to `0 1`.

### Fibonacci generator (new)

Note that the last two numbers are inaccurate, but it doesn't change the output of the program.

```
(2+/,)⍣38⍨⍳2
→ 0 1 ((2+/,)⍣38) 0 1

Step 1
0 1 (2+/,) 0 1
→ 2+/ 0 1 0 1
→ (0+1) (1+0) (0+1) ⍝ 2+/ evaluates sums for moving window of length 2
→ 1 1 1

Step 2
0 1 (2+/,) 1 1 1
→ 2+/ 0 1 1 1 1
→ 1 2 2 2

Step 3
0 1 (2+/,) 1 2 2 2
→ 2+/ 0 1 1 2 2 2
→ 1 2 3 4 4

```

### Zeckendorf to plain (partial)

```
⍸⌽+/⊤⎕
     ⎕  ⍝ Take input from stdin, must be an array of 2 numbers
    ⊤   ⍝ Convert each number to base 2; each number is mapped to a column
  +/    ⍝ Sum in row direction; add up the counts at each digit position
 ⌽      ⍝ Reverse
⍸       ⍝ Convert each number n at index i to n copies of i

```

---

# APL (Dyalog Extended), 47 bytes

```
g←1↓(1,+\⍤,)⍣20⍨1
{⊥1↓⍧|/⌽⍵,↑,\⌽g}+⍥{+/g[⍸⌽⊤⍵]}

```

Try it online!

Changed Part 1 of the previous answer to reuse the Fibonacci numbers. Also, drop the duplicate 1 to save some bytes in other places.

### Part 1 (new)

```
{+/g[⍸⌽⊤⍵]}
       ⊤⍵    ⍝ Argument to binary digits
     ⍸⌽      ⍝ Reverse and convert to indices of ones
   g[    ]   ⍝ Index into the Fibonacci array of 1,2,3,5,...
 +/          ⍝ Sum

```

---

# APL (Dyalog Extended), 52 bytes

```
{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}+⍥({+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤)

```

Try it online!

### How it works

No fancy algorithm to do addition in Zeckendorf because APL isn't known for operation on individual elements in an array. Instead, I went ahead to convert the two inputs from Zeckendorf to plain integers, add them, and convert it back.

### Part 1: Zeckendorf to plain integer

```
{+∘÷⍣(⌽⍳≢⊤⍵)⍨1}⊥⊤  ⍝ Zeckendorf to plain integer
                ⊤  ⍝ Convert the input to array of binary digits (X)
{    (  ≢⊤⍵)  }    ⍝ Take the length L of the binary digits and
      ⌽⍳           ⍝   generate 1,2..L backwards, so L..2,1
{+∘÷⍣(     )⍨1}    ⍝ Apply "Inverse and add 1" L..2,1 times to 1
                   ⍝ The result looks like ..8÷5 5÷3 3÷2 2 (Y)
               ⊥   ⍝ Mixed base conversion of X into base Y

Base |             Digit value
-------------------------------
13÷8 | (8÷5)×(5÷3)×(3÷2)×2 = 8
 8÷5 |       (5÷3)×(3÷2)×2 = 5
 5÷3 |             (3÷2)×2 = 3
 3÷2 |                   2 = 2
 2÷1 |                   1 = 1

```

### Part 2: Add two plain integers

```
+⍥z2i  ⍝ Given left and right arguments,
       ⍝   apply z2i to each of them and add the two

```

### Part 3: Convert the sum back to Zeckendorf

"You may assume that the Zeckendorf representations of both input and output fit into 31 bits" was pretty handy.

```
{⊥1↓¯1↓⍧|/⌽⍵,↑,\⌽(1,+\⍤,)⍣20⍨1}  ⍝ Convert plain integer N to Zeckendorf
                 (1,+\⍤,)⍣20⍨1   ⍝ First 41 Fibonacci numbers starting with two 1's
                ⌽                ⍝ Reverse
             ↑,\                 ⍝ Matrix of prefixes, filling empty spaces with 0's
          ⌽⍵,                    ⍝ Prepend N to each row and reverse horizontally
        |/                       ⍝ Reduce by | (residue) on each row (see below)
       ⍧                         ⍝ Nub sieve; 1 at first appearance of each number, 0 otherwise
  1↓¯1↓                          ⍝ Remove first and last item
 ⊥                               ⍝ Convert from binary digits to integer

```

### The Fibonacci generator

```
(1,+\⍤,)⍣20⍨1
→ 1 ((1,+\⍤,)⍣20) 1  ⍝ Expand ⍨
→ Apply 1 (1,+\⍤,) x 20 times to 1

First iteration
1(1,+\⍤,)1
→ 1,+\1,1  ⍝ Expand the train
→ 1,1 2    ⍝ +\ is cumulative sum
→ 1 1 2    ⍝ First three Fibonacci numbers

Second iteration
1(1,+\⍤,)1 1 2
→ 1,+\1,1 1 2  ⍝ Expand the train
→ 1 1 2 3 5    ⍝ First five Fibonacci numbers

⍣20  ⍝ ... Repeat 20 times

```

This follows from the property of Fibonacci numbers: if Fibonacci is defined as

$$ F\_0 = F\_1 = 1; \forall n \ge 0, F\_{n+2} = F\_{n+1} + F\_n $$

then

$$ \forall n \ge 0, \sum\_{i=0}^{n} F\_i = F\_{n+2} - 1 $$

So cumulative sum of \\$ 1,F\_0, \cdots, F\_n \\$ (Fibonacci array prepended with a 1) becomes \\$ F\_1, \cdots, F\_{n+2} \\$. Then I prepend a 1 again to get the usual Fibonacci array starting with index 0.

### Fibonacci to Zeckendorf digits

```
Input: 7, Fibonacci: 1 1 2 3 5 8 13

Matrix
0 0 0 0 0 0 13 7
0 0 0 0 0 8 13 7
0 0 0 0 5 8 13 7
0 0 0 3 5 8 13 7
0 0 2 3 5 8 13 7
0 1 2 3 5 8 13 7
1 1 2 3 5 8 13 7

Reduction by residue (|/)
- Right side always binds first.
- x|y is equivalent to y%x in other languages.
- 0|y is defined as y, so leading zeros are ignored.
- So we're effectively doing cumulative scan from the right.
0 0 0 0 0 0 13 7 → 13|7 = 7
0 0 0 0 0 8 13 7 →  8|7 = 7
0 0 0 0 5 8 13 7 →  5|7 = 2
0 0 0 3 5 8 13 7 →  3|2 = 2
0 0 2 3 5 8 13 7 →  2|2 = 0
0 1 2 3 5 8 13 7 →  1|0 = 0
1 1 2 3 5 8 13 7 →  1|0 = 0
Result: 7 7 2 2 0 0 0

Nub sieve (⍧): 1 0 1 0 1 0 0
1's in the middle are produced when divisor ≤ dividend
(so it contributes to a Zeckendorf digit).
But the first 1 and last 0 are meaningless.

Drop first and last (1↓¯1↓): 0 1 0 1 0
Finally, we apply base 2 to integer (⊥) to match the output format.

```
> 10 votes

# Answer
# CJam, ~~76~~ ~~74~~ ~~70~~ ~~63~~ 59 bytes

```
2q~{32{2\#I&},}fI+32_,*{WUer$Kf-[UU]/[-2X]*2,/2a*Kf+}fKf#1b

```

Try it online in the CJam interpreter or verify all test cases at once.

### Idea

We start by defining a minor variation of the sequence in the question:

> **G-2 = 0**
> **G-1 = 1**
> **Gk = Gk-1 \+ Gk-2** whenever **k** is a non-negative integer

This way, the bit **0** (LSB) of the bit arrays input or output corresponds to the Fibonacci number **G0** and, in general, the bit **k** to **Gk**.

Now, we replace each set bit in **Z(n)** and **Z(m)** by the index it encodes.

For example, the input **53210 = 10000101002** gets transformed into **\[2 4 9\]**.

This yields two arrays of integers, which we can concatenate to form a single one.

For example, if **n = m = 100**, the result is **A := \[2 4 9 2 4 9\]**.

If we replace each **k** in **A** by **Gk** and add the results, we obtain **n + m = 200**, so **A** is *a* way to decompose **200** into Fibonacci numbers, but certainly not the one from Zeckendorf's theorem.

Keeping in mind that **Gk \+ Gk+1 = Gk+2** and **Gk \+ Gk = Gk \+ Gk-1 \+ Gk-2 = Gk+1 \+ Gk-2**, we can substitute consecutive and duplicated indexes by others (namely, **(k, k + 1)** by **k + 2** and **(k, k)** by **(k + 1, k - 2)**), repeating those substitutions over and over until the Zeckendorf representation is reached.1

Special case has to be taken for resulting negative indexes. Since **G-2 = 0**, index **-2** can simply be ignored. Also, **G-1 = 0 = G0**, so any resulting **-1** has to be replaced by **0**.

For our example **A**, we obtain the following (sorted) representations, the last being the Zeckendorf representation.

**\[2 2 4 4 9 9\] → \[0 3 4 4 9 9\] → \[0 5 4 9 9\] → \[0 6 9 9\] → \[0 6 7 10\] → \[0 8 10\]**

Finally, we convert back from array of integers to bit array.

### Code

```
2             e# Push a 2 we'll need later.
q~            e# Read and evaluate the input.
{             e# For each integer I in the input:
  32{         e#   Filter [0 ... 31]; for each J:
    2\#       e#     Compute 2**J.
    I&        e#     Compute its logical AND with I.
  },          e#   Keep J if the result in truthy (non-zero).
}fI           e#
+             e# Concatenate the resulting arrays.
32_,*         e# Repeat [0 ... 31] 32 times.
{             e# For each K:
  WUer        e#   Replace -1's with 0's.
  $           e#   Sort.
  Kf-         e#   Subtract K from each element.
  [UU]/[-2X]* e#   Replace subarrays [0 0] with [-2 1].
  2,/2a*      e#   Replace subarrays [0 1] with [2].
  Kf+         e#   Add K to each element.
}fK           e#
f#            e# Replace each K with 2**K.
1b            e# Cast all to integer (discards 2**-2) and sum.

```

---

1 The implementation attempts substituting 32 times and does not check if the Zeckendorf representation has in fact been reached. I do not have a formal proof that this is sufficient, but I've tested all possible sums of 15-bit representations (whose sums' representations require up to 17 bits) and 6 repetitions was enough for all of them. In any case, augmenting the number of repetitions to 99 is possible without incrementing the byte count, but it would cripple performance.
> 9 votes

# Answer
# Haskell, 325 ~~396~~ bytes

EDIT: new version:

```
s f[]=[]
s f l=f l
x((a:b):(c:d):(e:r))=x(b:d:(a:e):r)
x(a:b:((c:d:e):r))=x((c:a):b:e:((d:s head r):s tail r))
x[]=[]
x(a:r)=a:x r
w l|x l/=l=w.x$l|True=l
l=length
t n x=take n$repeat x
j 0=[]
j n=t(mod(n)2)1:j(div(n)2)
i n=[[],[]]++j n++t(32-(l$j n))[]
u[]=0
u(a:r)=2*u r+l a
o(_:a:r)=u r+l a
z a b=o$w$zipWith(++)(i a)(i b)

```

`z` does the job.
> 6 votes

# Answer
## ES6, 130 bytes

```
(n,m)=>{for(a={},s=0,i=x=y=1;i<<1;i+=i,z=y,y=x,x+=z)s+=((n&i)+(m&i))/i*(a[i]=x);for(r=0;i;i>>>=1)s>=a[i]?(s-=a[i],r|=i):0;return r}

```

I originally tried to compute the sum in-place (effectively along the lines of the CJam implementation) but I kept running out of temporaries, so I just converted the numbers to and back from real integers.

(Yes, I can probably save a byte by using eval.)
> 4 votes

# Answer
# Ruby, ~~85 73~~ 65 bytes

```
->*a{r=(0..2*a.sum).select{|r|r^r*2==r*3};r[a.sum{|w|r.index w}]}

```

Try it online!

### How?

First get an upper bound for the encoded sum: (a+b)\*2 is ok.

Now filter out all non-zeckendorf numbers from (0..limit).

We have a lookup table, it's downhill from here.
> 1 votes

# Answer
# Python 3, 207 bytes

```
def s(n):
 p=1
 while n>=2*p:
  p*=2
 return n if n<=p else s(n+p//2)if n>=3*p/2 else s(m)if (m:=s(n-p)+p)!= n else n
a=lambda n,m:(b:=n&m)>-1 and s(a(a(a(s((n|m)-b%4),b//4*2),b//4),b%4*2+b%4//2))if m else n

```

Try it Online! (Verify all test cases)

## Explanation

This program directly manipulates the binary translations of the Zeckendorf representations. The function `a(n,m)` performs the main calculations, and `s(n)` is a helper function that gets rid of adjacent numbers contained in the Zeckendorf representation.

Let's start with the function `s(n)` (expanded for clarity):

```
def s(n):
    p=1                  #This finds the highest digit of the binary form of n.
    while n>=2*p:
        p*=2
    if n<=p:             #If n is a power of two (i.e, our number is already a Fibonnaci number)...
        return n         #Then return it normally.  This also works for zero. (A)
    if n>=3*p/2:         #If n's first digit is followed by a 1 (i.e, it starts with 11X)
        return s(n+p//2) #Then replace that with 100X (B)
    m = s(n-p)+p         #Otherwise, apply s to the rest of the number (C)
    if m==n:             #If this is out final result, we're done! (D)
        return n
    return s(m)          #Otherwise, reapply it. (E)

```

For example, the number 107 (`1101011` in binary, representing 1+2+5+13+21=42), undergoes the following process:

```
1+2+5+13+21 [1101011] -> 1+2+5+34 [10001011] (B)
1+2+5+34 [10001011] (C)
 1+2+5 [1011] (C)
  1+2 [11] -> 3 [100] (B)
 ->3+5 [1100] (A/E)
 (E):  3+5 [1100] -> 8 [10000] (B)
->8+34 [10010000] (A/E)
(E): 8+34 [10010000] (C)
->8+34 [10010000] (A/E)

```

Try it Online! (s with detailed output)

Here is an expanded version of `a(n,m)`:

```
def a(n,m):
    if m==0:
        return n
    b=n&m
    t=s((n|m)-b%4)              #(A)
    t=a(t,b//4*2)               #(B)
    t=a(t,b//4)                 #(C)
    return s(a(t,b%4*2+b%4//2)) #(D)

```

This function converts the two Zeckendorf representations into four binary numbers which are easier to combine. Line (A) is the bitwise OR of the two binary Zeckendorf representations--these correspond to one copy of each Fibonacci number in either group. (B) and (C) are the bitwise AND of the two numbers right-shifted 1 and 2 times, respectively. We know that when the corresponding Fibonacci numbers for (B) and (C) are added together, they will be equivalent to the bitwise AND of our `n` and `m` because F(n)=F(n-1)+F(n-2).

For example, let's say that we have the binary numbers n=101001 (corresponding to 1+5+13) and m=110110 (2+3+8+13). Then we will have (A)=111111 (1+2+3+5+8+13), which is converted to 1010100 (3+8+21) by our function `s`, (B)=10000 (8), and (C)=1000 (5). We can check that (1+5+13)+(2+3+8+13)=(3+8+21)+(8)+(5)=45. This process repeats with ((3+8+21)+(8))+(5)=((3+8+21)+(5)+(3))+(5), etc.

The one difficulty with this system is that it doesn't work for the Fibonacci numbers 1 and 2, since they don't obey the property `F(n)=F(n-1)+F(n-2)` (they're the lowest two numbers)! Because of that, whenever 1 or 2 is contained in both `n` and `m`, they are removed from A, B, and C, then their sum placed in D under the property that 1+1=2 and 2+2=1+3. For example, if we add 1+3 (101) + 1+3+5 (1101), we get:

(A): 3+5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 2 (10)

Notice that the 3 and 5 were placed into A, the duplicate 3 was split into 2+1 in B and C, and duplicate 1s were removed from A, B, and C, added together, and put into D. Similarly, if we add 2+3 (110) + 2+3+5 (1110), we get:

(A): 3+5 (1100) = 8 (10000)

(B): 2 (10)

(C): 1 (1)

(D): 1+3 (101)

Try it online! (a with detailed output)
> 1 votes

# Answer
# Wolfram Language (Mathematica), 218 bytes

```
Fold[#+##&,Total@PadLeft@IntegerDigits[#,2]//.{{p=n_/;n>1,r=y___}:>{0,n,y},{q=x___,i_,p,j_,k_,r}:>{x,i+1,n-2,j,k+1,y},{q,i_,p,j_}:>{x,i+1,n-2,j+1},{q,i_,p}:>{x,i+1,n-2},{1,1,r}:>{1,0,0,y},{q,i_,1,1,r}:>{x,i+1,0,0,y}}]&

```

Try it online!

Simply pattern matching.

Ungolfed:

```
FromDigits[Total@PadLeft@IntegerDigits[#, 2] //.
   {{n_ /; n > 1, y___} :> {0, n, y},
    {x___, i_, n_ /; n > 1, j_, k_, y___} :> {x, i + 1, n - 2, j, k + 1, y},
    {x___, i_, n_ /; n > 1, j_} :> {x, i + 1, n - 2, j + 1},
    {x___, i_, n_ /; n > 1} :> {x, i + 1, n - 2},
    {1, 1, y___} :> {1, 0, 0, y},
    {x___, i_, 1, 1, y___} :> {x, i + 1, 0, 0, y}}, 2] &

```
> 0 votes

---
Tags: code-golf, fibonacci, bitwise, integer
---


# Question
Title: Find all unambiguous prefixes of a set of strings
For this challenge, you must implement Ruby's `Abbrev` module in as little code as possible.

## Challenge

* The input will be whatever your language has as an array (array, list, sequence, etc.) of strings. You may write a function, or you may accept comma-separated words on STDIN.
* You must then calculate the set of unambiguous prefixes for those strings. This means you must return a hash (or map, object, etc.) of abbreviations to their original strings.

+ A "prefix" is a substring of the original string starting at the beginning of the string. For example, "pref" is an prefix of the word "prefix."
    + An *unambiguous* prefix is one that can only mean one word. For example, if your input is `car,cat`, then `ca` is not an unambiguous prefix because it could mean either "car" or "cat."
    + The exception to this rule is that a word is always a prefix of itself. For example, if you have input such as `car,carpet`, `car:car` must be in your output.
* You can then return the hash/map/object/etc. from your function (or do the equivalent in your language), or print it out to STDOUT in `key:value` pairs in the form of `f:foo,fo:foo,...`. (The key-value pairs may also be separated by whitespace if it makes your code shorter.)

## Test cases

```
Input  code,golf,going
Output c:code,co:code,cod:code,code:code,gol:golf,golf:golf,goi:going,goin:going,going:going

Input  pie
Output p:pie,pi:pie,pie:pie

Input  pie,pier,pierre
Output pie:pie,pier:pier,pierr:pierre,pierre:pierre

Input  a,dog
Output a:a,d:dog,do:dog,dog:dog

```

## Rules

* The input will not contain duplicate elements.
* Your output may be in any order; you don't have to sort it.
* You may not use a built-in `Abbrev` module/function/thing like Ruby's.
* This is , so the shortest code in bytes will win!

# Answer
## APL (46)

(Yes, the APL charset does fit in a byte, with room to spare.)

```
{↑{∆/⍨2=⍴∆←(⊂⍵),∆/⍨⊃¨⍵∘⍷¨∆}¨∪⊃,/{↑∘⍵¨⍳⍴⍵}¨∆←⍵}

```

This is a function that takes a list of strings, and returns a 2-by-N matrix, where each row contains an unambigous prefix and the word it belongs to:

```
{↑{∆/⍨2=⍴∆←(⊂⍵),∆/⍨⊃¨⍵∘⍷¨∆}¨∪⊃,/{↑∘⍵¨⍳⍴⍵}¨∆←⍵}'code' 'golf' 'going'
 c      code
 co     code
 cod    code
 code   code
 gol    golf
 golf   golf
 goi    going
 goin   going
 going  going

```

Explanation:

* `∆←⍵`: store the right argument in .
* `{↑∘⍵¨⍳⍴⍵}¨∆`: for each element of , get the possible prefixes of that element:
    + `⍳⍴⍵`: get a list from `1` to the length of
    + `↑∘⍵¨`: for each of those numbers, get that many elements from .
* `∪⊃,/`: concatenate the lists together and take the unique values.
* `{`...: for each of the unique prefixes:
    + `∆/⍨⊃¨⍵∘⍷¨∆`: select the words that start with that prefix
    + `(⊂⍵),`: also enclose the prefix, and concatenate
    + `∆/⍨2=⍴∆←`: only return the list if there are two elements (the prefix and one matching word)
* : turn the list of tuples into a matrix
> 1 votes

# Answer
# Python 2.7 - 146 141 bytes

```
l=raw_input().split(',')
for w in l:
 for a in range(len(w)):
    e=w[:a+1]
    if e==w or len(filter(lambda b:b.startswith(e),l))==1:print e+':'+w

```

Note that the indentation on lines 4 and 5 is not 4 spaces, that's a side effect of SE's markdown interpreter. That's a literal tab character, so only one byte.

This is not technically up to spec, but I'll change it if Doorknob clarifies. It uses newlines instead of commas to separate the output. For example:

```
$ python2 abbreviations.py <<< code,golf,golfing
c:code
co:code
cod:code
code:code
golf:golf
golfi:golfing
golfin:golfing
golfing:golfing

```

**New:** I was able to get rid of 5 characters by assigning the string that I'm checking to a variable `e`. This means that I only have to type `e` instead of `w[:a]` three times. It also means I save characters by doing `e=w[:a+1]` and changing `...range(1,len(w)+1)` to `range(len(w))`.

---

Explanation:

```
l=raw_input().split(',') # Gets a line of input from stdin and splits it at every ',' to make a list
for w in l: # For each word in that list...

 for a in range(1,len(w)+1): # For each number a from 1 to the length of that word...

    if (w[:a]==w # w[:a] gets the string w up to the ath index. For example, 'aeiou'[:3] == 'aei'.
                 # We're testing every possible w[:a] to see if it's a unique abbreviation.
                 # However, a word is always its own abbreviation, so we hardcode that in by testing
                 # if w[:a] is the same as w.

or len(filter( # filter takes a function and an iterable as an argument, and returns a list of every
               # element of that iterable where that_function(that_element) returns a True-y value

lambda b:b.startswith(w[:a]),l) # We define an anonymous function that returns True for any string
                                # that begins with our current w[:a]. We filter for words that return
                                # True.

)==1): # If exactly one word returns True for this, it's a unique abbreviation!

     print w[:a]+':'+w # Print the abbreviation, a colon, and the full word.

```
> 4 votes

# Answer
# J - 47 char

```
(,.~~.@,~[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>)

```

J sees strings as just vectors of characters, which means that when it tries to make a list of strings it actually ends up making a table of characters, so the ends get padded with spaces. J's solution to this is called the *box*, so this function takes as argument a boxed list of strings, so as to preserve length.

```
   'code';'golf';'going'
+----+----+-----+
|code|golf|going|
+----+----+-----+

```

Also, J lacks a hash type, so the closest it has to that is a two-column table of items, say boxed strings, for instance. If that is unacceptable and I have to default to the key-value form, I can reformat the output to this form in **67 characters** total:

```
;@|.@,@((<&>',:'),."1,.~~.@,[:(#~1-1({.\e."_1]\.){:"1)@;(<,.<\)&.>)

```

Explanation by explosion:

```
(,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) NB. unambiguous prefixes
                                    (     )&.>  NB. for each string:
                                     <\         NB.   take all prefixes
                                       ,.<      NB.   pair each with string
        [:                         ;            NB. gather up "partial" hashes
          (#~1-                  )@             NB. remove those rows where:
               1({.\        ){."1               NB.   each key
                    e."_1                       NB.   is an element of
               1(        ]\.){."1               NB.   the rest of the keys
 ,.~                                            NB. hash each word to itself
       ,                                        NB. add these rows to hash
    ~.@                                         NB. remove duplicate rows

```

Examples:

```
   (,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) 'pie';'pier';'pierre'
+------+------+
|pie   |pie   |
+------+------+
|pier  |pier  |
+------+------+
|pierre|pierre|
+------+------+
|pierr |pierre|
+------+------+
   NB. 1-char words have to be made into lists with ,
   (,.~~.@,[:(#~1-1({.\e."_1]\.){."1)@;(<\,.<)&.>) (,'a');'dog'
+---+---+
|a  |a  |
+---+---+
|dog|dog|
+---+---+
|d  |dog|
+---+---+
|do |dog|
+---+---+
   NB. "key:value," format, reversed order to save chars
   ;@|.@,@((<&>',:'),."1,.~~.@,[:(#~1-1({.\e."_1]\.){:"1)@;(<,.<\)&.>) 'code';'golf';'going'
goin:going,goi:going,gol:golf,cod:code,co:code,c:code,going:going,golf:golf,code:code,

```
> 3 votes

# Answer
# Haskell ~~96~~ 87

```
import Data.List
i=inits
f a=a>>= \x->[(y,x)|y<-i x,y/="",y`notElem`(a>>=i)\\i x||y==x]

```

Ungolfed version:

```
 import Data.List
 f a = concatMap (\x ->
     [(y, x) |
      y <- inits x,
      y /= "",
      y `notElem` concatMap inits a \\ inits x || y == x]
     ) a

```

Example:

```
> f ["pi","pier","pierre"]
[("pi","pi"),("pier","pier"),("pierr","pierre"),("pierre","pierre")]

```

I used the `inits` function, which finds all prefixes of a list/string. Does it count as cheating?
> 2 votes

# Answer
# Python 3 (97)

```
c=','
S=c+input()
for w in S.split(c):
 e=w
 while e:e<w<w*S.count(c+e)or print(e+':'+w);e=e[:-1]

```

We iterate over prefixes of each word in the input, printing the corresponding prefix/word pair if it either appears exactly once or is to whole word. We take advantage of the short-circuiting behavior of `or` (and `print` being a function) to print only if one of these conditions is met.

The `while` loop repeatedly cuts off the last character to create shorter and shorter prefixes, terminating when the empty string remains. This is the only time we index or slice into anything.

We count the occurrences of the prefix `e` in the input by searching the original comma-separated input string `S` for substrings `','+e`. We prepend a comma to the input string beaforehand. This addition causes an extra empty string element when we `split`, but this has no effect because it has no nonempty substrings.

To check for the case when the substring `e` is the whole word `w`, we compare them using the string comparison operator. This compares lexicographically, so shorter prefixes are smaller. The double comparison fails if either `e==w` or `S.count(c+e)<2`.

If printing outputs in the form `e,w` were allowed, I'd save a character by writing `e+c+w` instead.

Credit to undergroundmonorail from whose answer I based my overall code structure.
> 2 votes

# Answer
## Ruby, 114

```
def f(l);h={};l.each{|w|w.size.times{|i|k=w[0..i];h[k]=h[k]&&0||w}};h.delete_if{|k,v|v==0};l.each{|w|h[w]=w};h end

```

Ungolfed:

```
def f(list)
  hash = {}
  list.each do |word|
    word.size.times do |i|
      key = word[0..i]
      h[key] = (hash[key] && 0) || word
    end
  end
  hash.delete_if{|key, value| v==0}
  list.each{|word| hash[word] = word}
  hash
end

```
> 1 votes

# Answer
## k4 (70)

not particularly golfed; i'm sure it could be shorter

pretty similar to the J impl. above, i think -- basically just collects all the (proper) prefixes, removes the words from the prefixes again (to handle the `"car"`/`"carpet"` case), groups them into equivalence classes, picks the classes with only one element, reduces them from lists to strings, and adds in the map from strings to themselves.

```
f:{(x!x),*:'{(&1=#:'x)#x}{x@=y@:&~y in x}.,/'+{1_'(c#,x;(!c:#x)#\:x)}'x}

```

some test cases

note that in `k`/`q`, a string is list of characters, so a string containing only a single character needs to be marked as such using the unary `,` function; & m.m. w.r.t a list of strings containing only a single string

these use `q`'s `show` function, which has built-in formatting for some data structures, to make the results more readable:

```
  .q.show f("code";"golf";"going")
"code" | "code"
"golf" | "golf"
"going"| "going"
,"c"   | "code"
"co"   | "code"
"cod"  | "code"
"gol"  | "golf"
"goi"  | "going"
"goin" | "going"
  .q.show f@,"pie"
"pie"| "pie"
,"p" | "pie"
"pi" | "pie"
  .q.show f("pie";"pier";"pierre")
"pie"   | "pie"
"pier"  | "pier"
"pierre"| "pierre"
"pierr" | "pierre"
  .q.show f(,"a";"dog")
,"a" | ,"a"
"dog"| "dog"
,"d" | "dog"
"do" | "dog"
  .q.show f("car";"carpet")
"car"   | "car"
"carpet"| "carpet"
"carp"  | "carpet"
"carpe" | "carpet"

```
> 1 votes

# Answer
# JavaScript - 212

```
w=prompt(o=[]).split(",");w.map(function(k,l){for(i=0;++i<k.length;){p=k.slice(0,i);if(w.filter(function(r,t){return t!=l}).every(function(r){return r.indexOf(p)}))o.push(p+":"+k)}o.push(k+":"+k)});console.log(o)

```

Initial golf.

Input:

`code,golf,going`

Output:

`["c:code", "co:code", "cod:code", "code:code", "gol:golf", "golf:golf", "goi:going", "goin:going", "going:going"]`
> 1 votes

# Answer
## Perl, ~~93~~ 77

With newlines and indentation for readability:

```
sub f{
    (map{
        $h{$x}=[($x=$`.$&,$_)x!$h{$x}]while/./g;
        $_,$_
    }@_),map@$_,values%h
}

```

A bit too late and too long, but I'm glad it's finally got below 100. Function returns a list which can be assigned to hash variable:

```
%h = f(qw/code golf going pie pier pierre/);
print "$_ $h{$_}\n" for sort keys %h;

```

and

```
perl prefix.pl
c code
co code
cod code
code code
goi going
goin going
going going
gol golf
golf golf
pie pie
pier pier
pierr pierre
pierre pierre

```

Actually, returned list is not filtered yet - hash construction is completed at the moment of its assignment i.e. outside function. **IF** it's not clean/fair enough, add 3 to count and put function contents into curly braces, prepending `+` \- then function returns 'true' hash reference.
> 1 votes

# Answer
## Q: 44 Bytes

```
{x!p@'(?0,&:)'p in\:&1=#:'=,/p:`$(-1_)\'$x}

```

**NOTES**

* Q language has an inner core named internally K4 (used in this answer and another previously answer to this question)
* To test code, download interpreter (kx.com, free for non-commertial use, support for Windows, Linux, Mac)

Interpreter admits two syntaxes:

* verbose (more readable names, distinct names for moands and diads, more libraries, ...). Load source file with q extension, or interactive interpreter
* compact (functional inner core, one letter operators, same letter for both uses monad/diad, ...). Load source file with k extension, or interactive interpreter **in k mode** (write \ at prompt). Code must be tested in this mode

The code defines a lambda (anonymous function). To give name to the function we need prefix name: (ex f:{..}), so requires 46 Bytes

**TEST**

(assumming named function: otherwise substitute f for the code)

```
f `code`golf`going

`code`golf`going!(`code`cod`co`c;`golf`gol;`going`goin`goi)

```

returns a dictionary (syntax keys!values). Keys are a list of symbols (\`symb\`symb..), and values a list of list of symbols. If we execute the sentente at the interactive interpreter, we have a more convenient presentation (each key and associate values at a different line)

```
code | `code`cod`co`c
golf | `golf`gol
going| `going`goin`goi

```

**EXPLANATION**

`x` is the implicit argument to the lambda

`$x` convert symbol list to string list

`(-1_)\` iterates over each elem of the symbol list

(reads as for each string calculates prefixes (at eat iteration drops last char of the string (-1\_), until empty string)

`$` transforms to a symbol list again (list of all prefixes)

`p:` and assigns to p

`,/` raze all (concatenates and creates a one-level structure)

`=` classify -\> for each unique prefix, associates the corresponding words

`#:'` calculates length (number of words associated to each prefix)

`1=` true if length=1 (unambiguous), false otherwise

`&` where -\> index of true elements

`p in\:` determines for all prefix if they are in unambiguous prefix

`(..)'` applies (..) to each value at right (unambiguous prefix)

`?0,&:` -\> distinct 0 concatenated where (to cope words as prefix of itself)

`p@` transform indexes to symbols

`x!..` construct a dictionary with x (words) as keys, and .. as values

Read as:

* Construct and returns a dictionary with the words as keys, and values ..
* ... values of indexes at distinct positions 0 (all word) and where unambiguous prefix
* ... unambiguous calculated as prefixes that appear only at one word (wordlist associates to each symbols has length one)
* ... lists resulting of classifying all unique symbols with corresponding words
* ... prefixes calculated by repeating drop last char of each word
> 1 votes

# Answer
**PHP 7.0, 67 bytes** (postdates the challenge)

```
for(;a&$c=$s[++$k]??($s=$argv[++$i])[$k=+$t=!1];)echo$t.=$c,":$s,";

```

takes input from command line arguments; prints a trailing comma; run with `-nr`.

for **newer PHP**, add one byte: Replace `&a` with `""<`.

for older PHP, use these 70 bytes:

# PHP, 70 bytes

```
for(;a&$s=$argv[++$i];)for($k=+$t="";a&$c=$s[$k++];)echo$t.=$c,":$s,";

```
> 1 votes

# Answer
# Brachylog, 23 bytes

```
∋Xa₀Y;?↔⟨∋a₀⟩ᶜ1∧Y;X|∋gj

```

Try it online!

Takes input as a list through the input variable, and generates a list of `[key, value]` pairs through the output variable. Any input string which is not a prefix of another input string will be generated as a prefix of itself twice, although the header on TIO hides this by using  to obtain the full list instead of .

```
 X                         X
∋                          is an element of
                           the input variable
    Y                      and Y
  a₀                       is a prefix of
 X                         X.
             ᶜ             The number of ways in which
        ⟨∋  ⟩              an element can be selected from
     ;?↔⟨   ⟩              the input variable
    Y; ↔⟨ a₀⟩              such that it has Y as a prefix
              1            is equal to 1.
               ∧Y          Y is not necessarily 1,
                   |       and the output variable
                Y;X        is the list [Y, X].
                   |       If every choice from the first rule has been taken already,
                           the output variable is
                    ∋      an element of
                   |       the input variable
                     gj    paired with itself.

```
> 1 votes

# Answer
# APL (Dyalog Classic), 38 bytes

thanks Erik the Outgolfer for reminding me to use a single-byte character encoding

```
{⊃,/⍵{b,¨⍨(⊂¨⍵~⊃,/a~⊂⍵)∪b←⊂⊂⍺}¨a←,\¨⍵}

```

Try it online!
> 1 votes

# Answer
# Perl 5 `-a`, 76 bytes

```
map{say"$, $a"if($,=substr$a,0,$_)eq$a||2>grep/^$,/,@F}1..length($a=$_)for@F

```

Try it online!
> 1 votes

# Answer
# Python (127)

So I couldn't comment @undergroundmonorail, but I thought that taking a dictionary approach would be better? I'm sure with some list/dictionary comprehension it could be cut down tremendously too, but can't get it to work with popping from the dict.

```
i=raw_input().split(",")
d = {}
for x in i:
    for c in range(1,len(x)+1):
        if x[:c] in d:
            del d[x[:c]]
        else:
            d[x[:c]]=x
print d

```

The print will output the dictionary, unordered.

EDIT: Ahh I missed the car:car / car:carpet criteria. Maybe a length check?
> 0 votes

# Answer
## Groovy - 212 chars

Golfed:

```
c="collectEntries";f="findAll";def g={def h=[:].withDefault{[]};it.each{def w->w.size().times{ h[w[0..it]] << w}};(h."$f"{k,v->v.size()==1}."$c"{k,v->[k,v[0]]}).plus(h."$f"{k,v->v.contains(k)}."$c"{k,v->[k,k]})}

```

example output:

```
println g(["code","golf","going"])

[c:code, co:code, cod:code, code:code, gol:golf, golf:golf, goi:going, goin:going, going:going]

```

Ungolfed:

```
def g = { def list ->
    def hash = [:].withDefault{[]}
    list.each {
        def word -> word.size().times{ hash[word[0..it]] << word }
    }

    def map = hash.findAll{ k,v -> v.size() == 1 }.collectEntries{ k,v -> [k,v[0]] }
    map.plus(hash.findAll{ k,v -> v.contains(k) }.collectEntries{ k,v -> [k,k] }
    map
}

```
> 0 votes

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

```
L=>L.map(s=>[...s].map(c=>L.filter(t=>t>S&t<S+'~',S+=c)[1]&&s>S||(R[S]=s),S=''),R={})&&R

```

Try it online!
> 0 votes

# Answer
# Zsh, 95 bytes

```
local -A m
for w;{m[$w]=$w;x=
for c (${(s::)w})x+=$c&&[ ${(M)@:#$x*} = $w ]&&m[$x]=$w
}
local m

```

Try it online!

The only way to "return" an associative array in Bash/Zsh is by declaring it without the `local` keyword and then accessing it in the parent scope. This would save one byte. However, I/O via variables is generally frowned upon, so we print the array definition instead.

```
local -A m                          # declare m as associative
                                    # "local" is shorter than "typeset"/"declare"
for w;{                             # for each word
    m[$w]=$w                        # the word is a prefix of itself
    x=                              # ensure x is empty
    for c (${(s::)w})               # for each character in the word
        x+=$c &&                    # append to x (building a prefix
          [ ${(M)@:#$x*} = $w ] &&  # if the only match is the word itself:
          m[$x]=$w                  # ... then x is a prefix of w
}
local m                             # print m

```
> 0 votes

# Answer
# Ruby, 84 bytes

Just noticed there's already an existing Ruby solution, oh well. This basically improves on the old solution by picking prefixes in a smarter way (eliminating the need to add each word as a "prefix" at the end) and counting prefixes to check uniqueness before adding them to the hash, instead of overwriting the value with a dummy if there is a duplicate and then erasing the entry.

```
->w{h={};w.map{|e|(1..e.size).map{|i|w.count{|d|d[0,i]==e[0,i]}<2?h[e[0,i]]=e:0}};h}

```

Try it online!
> 0 votes

---
Tags: code-golf
---


title: Knight's tour game (7x7)

text:
# Question
Title: Knight's tour game (7x7)
Your job is to solve this chess-related game.

The setup of the game is a 7x7 tile grid, you start on a random tile and you have to hop on each tile, until you hopped on all 49 tiles.

Top left corner is (0,0)

**Rules:**

* you can hop on each tile once.
* the only move allowed in the game is to hop two tiles horizontally and one tiles vertically, or two tiles vertically and one tiles horizontally, like a knight in a chess game.
* your input should be a tuple representing the coordinates of the starting tile (stdin, file, what you prefer).
* your output a list of tuples, representing the coordinates of each hop. If there's no valid combinations, return an empty list (same as above, any output is ok).

This is , so shortest code wins!

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

```
7 7{3::0⋄(⍋,(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)¯1⌂kt⍺)⊇,⍳⍺}⊂

```

Try it online!

A version provided by @Adám.

Dyalog Extended has a shortcut to the `dfns` library , and a few convenience functions e.g. monadic `=` which is equivalent to `0∘=`, and dyadic  for multiple indexing. Unfortunately an inner assignment is buggy, so we use a tacit inner function to reference the value of `¯1⌂kt⍺` twice. Otherwise we'd have a **38 byte** solution:

```
7 7{3::0⋄(⍋,w⊃⍨⍵⍳⍨⊃∘⍸¨=w←¯1⌂kt⍺)⊇,⍳⍺}⊂

```

### How the inner tacit function `(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)` works

```
This tacit function has 5 terms: `⊢`  `⊃⍨`  `⍵`  `⍳⍨`  `⊃∘⍸¨∘=`
A tacit function is grouped by 3 terms from the right:
  ⊢ ⊃⍨ (⍵ ⍳⍨ ⊃∘⍸¨∘=)
A group of 3 terms is interpreted as follows:
  (f g h)w → (f w) g (h w)     ⍝ f, g, h are functions
  (A g h)w → (A  ) g (h w)     ⍝ A is an array
Then we can interpret the above tacit function as
  (⊢ ⊃⍨ (⍵ ⍳⍨ ⊃∘⍸¨∘=))w
  → (⊢ w) ⊃⍨ (⍵ ⍳⍨ (⊃∘⍸¨∘= w))   ⍝ Expand tacit function
  → w ⊃⍨ ⍵ ⍳⍨ ⊃∘⍸¨∘= w           ⍝ ⊢ is identity function; simplify parens
  → w ⊃⍨ ⍵ ⍳⍨ ⊃∘⍸¨ = w           ⍝ (f∘g)w simply expands to f g w
So the code `(⊢⊃⍨⍵⍳⍨⊃∘⍸¨∘=)w` is equivalent to `w⊃⍨⍵⍳⍨⊃∘⍸¨=w`.

```

---

# APL (Dyalog Unicode), <sup>~~53~~</sup> 49 bytes

```
⎕CY'dfns'
7 7{3::0⋄(,⍳⍺)[⍋,w⊃⍨⍵⍳⍨⊃∘⍸¨0=w←¯1kt⍺]}⊂

```

Try it online!

Golfed 4 bytes by extracting some terms out of the dfn using a tacit form.

---

## Original submission: APL (Dyalog Unicode), 53 bytes

```
⎕CY'dfns'
{3::0⋄(,⍳7 7)[⍋,w⊃⍨(⊃∘⍸¨0=w←¯1 kt 7 7)⍳⊂⍵]}

```

Try it online!

Because we've got a language that has a Knight's tour solver built in.

Since `¯1 kt 7 7` tries to find all solutions, it's infeasible to actually run the code as-is. For demonstration purposes, the TIO link uses 3x4 board instead.

### How it works

The function `dfns.kt` finds a (possibly open) Knight's tour, where the right argument is the board's dimensions, and the optional left argument is the number of solutions to find. Giving `-1` on the left causes the function to search all possible solutions.

```
⎕CY'dfns'  ⍝ Import the 'dfns' workspace

{3::0⋄(,⍳7 7)[⍋,w⊃⍨(⊃∘⍸¨0=w←¯1 kt 7 7)⍳⊂⍵]}  ⍝ ⍵←starting coordinates
                          w←¯1 kt 7 7        ⍝ Find ALL solutions of 7x7 knight's tour
                   (⊃∘⍸¨0=           )       ⍝ Extract the starting coordinates from each solution
                                      ⍳⊂⍵    ⍝ Find the index of the solution that starts at ⍵
               ,w⊃⍨                          ⍝ Fetch the solution and flatten it
      (,⍳7 7)                                ⍝ Take the flattened list of coordinates on 7x7 board
             [⍋                          ]   ⍝ Sort the coordinates by flattened solution
 3::0⋄                                       ⍝ If there's no solution starting with ⍵,
                                             ⍝ catch the Index Error and return 0 instead

```

---

## Every black square on 7x7 board can be the starting location of a Knight's tour.

The following isn't directly related to the code above, but nevertheless here is a proof by example.

### Starting at (0,0), Ending at (5,1)

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

```

### Starting at (1,3), Ending at (6,4)

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

```

### Starting at (2,2), Ending at (3,3)

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

```

By swapping heads and tails, reflection, and rotation, all black squares can be the starting point of some Knight's tour.

I found these three tours by splitting the board into four groups that can form a continuous loop:

```
O O O . O O O  |  . . . O . . .  |  . . . . . . .  |  . . . . . . .
O . O O O . O  |  . O . . . O .  |  . . . . . . .  |  . . . . . . .
O O . . . O O  |  . . . . . . .  |  . . O O O . .  |  . . . . . . .
. O . . . O .  |  O . . . . . O  |  . . O . O . .  |  . . . O . . .
O O . . . O O  |  . . . . . . .  |  . . O O O . .  |  . . . . . . .
O . O O O . O  |  . O . . . O .  |  . . . . . . .  |  . . . . . . .
O O O . O O O  |  . . . O . . .  |  . . . . . . .  |  . . . . . . .

```

and breaking and gluing the chains whenever needed. It's kind of a heuristic, so it would be usually shorter to hardcode the three boards or just run naive DFS.

# Answer
> 1 votes
# Python 3 - 241 chars

This will work most of the time, if you live long enough to see the result...

It works by randomly reordering a list of all coordinates until it gets the right answer. If it takes more than **9\*10^99** loops, it assumes that there is no answer. (It will be right the vast majority of the time, since the probability of getting the right order is roughly **1 in 6\*10^63**).

N.B. Yes, I know that this is not really a valid answer.

```
import random
l=[(x%7,x//7)for x in range(49)]
s=eval(input())
v=lambda x:all(abs((x[i][0]-x[i+1][0])*(x[i][1]-x[i+1][1]))==2 for i in range(len(x)-1))
t=0
while not all(v(l),l[0]==s,t<9e99):
 random.shuffle(l);t+=1
print(l if t<9e99 else[])

```

# Answer
> 1 votes
# Python 3 - ~~272~~ 263

Since this is a code-golf, this is built to be shorter in code, as opposed to faster in execution. Note that if you want solutions that will run in practical amounts of time, that almost requires some kind of dynamic programming, using a hash in addition to a list, and probably even some kind of heuristic. Otherwise, an exhaustive backtracking search may potentially take a very long time. It would be interesting to see a separate contest for the *fastest* knight's tour finder for all mxn boards for m0\<=m\<=M, n0\<=n\<=N

Anyway, here is the code. It expects an input as a tuple, i.e. (0,0)

```
p=[eval(input())]
def k():
 if 49==len(p):return 1
 n=[(p[-1][0]+x,p[-1][1]+y) for x in range(-2,3)for y in range(-2,3)if(abs(x)+abs(y)==3)]
 for z in n:
  if(min(z)<0 or max(z)>6 or z in p):continue
  p.append(z)
  if(k()):return 1
  p.remove(z)
if(k()):print(p)

```

Thanks to Fry for the golfing tips!

---
Tags: code-golf, chess
---


title: How Shuffled is this Sequence?

text:
# Question
Title: How Shuffled is this Sequence?
Given a sequence \\$S\\$ with length \\$n\\$ of exactly one each of whole numbers from \\$1\\$ to \\$n\\$, your task is to return a number \\$\sigma\\$ indicating how shuffled it is.

# Definition of shuffledness

Humans perceive shuffling randomness locally \[Citation Needed\], so the shuffledness of a sequence is based on the ability to find various patterns within each sliding window \\$W\\$ of 5 consecutive elements of the sequence (\\$W = \\{S\_x, S\_{x+1}, S\_{x+2}, S\_{x+3}, S\_{x+4}\\}\\$ for some \\$x\\$\- these will overlap, as each \\$x\\$ that is at least \\$4\\$ less than \\$n\\$ is considered). For each window of 5 elements, add a point for each test of the following that fails: (Note the 1-indexing due to the use of mathematical notation)

* Apply the following tests to the whole window:
    1. \\$W\\$ is monotonic
    2. \\$W\\$ is in ascending order
    3. Some permutation of \\$W\\$ is a run of sequential integers (e.g. 1, 2, 3, 4, 5)
    4. For all \\$W\_i\\$ where \\$i\>1\\$, \\$W\_i = W\_{i-1}+k\\$ for some integer \\$k\\$.
        + This corresponds to regular linear intervals
    5. For all \\$W\_i\\$ where \\$i\>1\\$, \\$W\_i = W\_{i-1}+ax+k\\$ for some integers \\$k, a\\$, where \\$x=i\\$.
        + This corresponds to regular quadratic intervals (which could also be linear)
* Apply the same tests for subwindows where 1 or 2 elements have been removed (if any one of those reduced windows passes a particular test, this step passes. Only count one failure when a test fails for all reduced windows.
* Apply the same tests for windows with some pair of adjacent elements optionally swapped (this step will pass if all tests passed for the whole unmodified window) Replace test 3 with the following:
    + \\$W\\$ is an ascending or descending sequence of sequential integers (e.g. 5, 4, 3, 2, 1)

### Notes

* Ascending sequential sequences will pass every test for all windows and therefore be scored as \\$0\\$
* Descending sequential sequences will pass all tests except the "ascending" one for all windows and will therefore be scored as \\$3(n-4)\\$
* The naive maximum shuffledness is \\$15(n-4)\\$

# Examples

* \[1, 5, 3, 2, 4\]
    + All elements:
        - Passes test 3
        - Fails all other tests (+4)
    + Elements removed:
        - Passes tests 1, 2, 5 with \[1, 2, 4\] (remove 5 and 3)
        - Passes test 3 with \[5, 3, 2, 4\] (remove 1)
        - Fails test 4 (+1)
    + Elements swapped:
        - Fails all tests (+5)
            * Test 3 fails because it requires the elements to be in order for this case only
    + \\$\therefore \sigma = 10\\$
* \[1, 2, 4, 3, 5\]
    + All elements:
        - Passes test 3
        - Fails all other tests (+4)
    + Elements removed:
        - All tests pass with \[1, 2, 3\] (remove 4, 5)
    + Elements swapped:
        - Passes all tests (swap 4, 3)
    + \\$\therefore \sigma = 4\\$
* \[3, 6, 9, 12, 15\] (a sliding window)
    + All elements:
        - Passes tests 1, 2, 4, 5
        - Fails test 3 (+1)
    + Elements removed: same (+1)
    + Elements swapped: same (+1) (no swap)
    + \\$\therefore \sigma = 3\\$
* \[8, 12, 13, 11, 6\] (a sliding window)
    + All elements:
        - Passes test 5 (\\$a=-3, k=4\\$)
        - Fails all other tests (+4)
    + Elements removed:
        - Passes tests 1, 2, 5 with \[8, 12, 13\] (remove 11, 6)
        - Passes test 3 with \[12, 13, 11\] (remove 8, 6)
        - Fails test 4 (+1)
    + Elements swapped: same as all elements (+4) (no swap)
    + \\$\therefore \sigma = 9\\$
* \[2, 4, 6, 1, 3, 5\] (whole sequence)
    + First window: (\[2, 4, 6, 1, 3\])
        - All elements: Fails all tests (+5)
        - Elements removed:
            * Passes tests 1, 2, 4, 5 with \[2, 4, 6\]
            * Passes test 3 with \[2, 1, 3\]
        - Elements swapped: Fails all tests (+5)
    + Second window: (\[4, 6, 1, 3, 5\])
        - All elements: Fails all tests (+5)
        - Elements removed:
            * Passes tests 1, 2, 4, 5 with \[1, 3, 5\]
            * Passes test 3 with \[4, 6, 5\]
        - Elements swapped: Fails all tests (+5)
    + \\$\therefore \sigma = 20\\$

# Rules and such

* Standard IO rules, loopholes, etc
* You must handle sequences of up to 1000 elements long
* You may assume \\$S\\$ is at least 5 elements long
* No validation necessary. You may assume that all inputs contain exactly one each of every whole number from \\$1\\$ to \\$n\\$
* Shortest code wins!

# Answer
# Jelly, ~~71~~ 65 bytes

```
J4Ṭ;-+ʋ€ịṭ@Wẋ¥€3ṭœcJ;2/Ṣṭ,`Ɗ€€ƲḊ,UṢƑ€o\ƲI,I$E€ƊIỊẠƊ3ƭ€€€»/€¬µ5ƤFS

```

Try it online!

A monadic link taking a list if integers and returning an integer. I’m sure this can be shortened further.

## Explanation

```
...µ5Ƥ   | Run the main chain (below) for each 5-integer-long infix of the list
      F  | Flatten list
       S | Sum

```

### Main chain

This generates the lists for the each set of tests. To deal with the variation in test 3, there are 3 copies made of each innermost list. For the first and second sets of tests, the last copy of each innermost list is sorted, while for the third set of tests it is not.

### Main chain part 1 (generates swapped lists for third set of tests)

```
J                | Sequence along list [1,2,3,4,5]
 4    ʋ€         | Do the following as a dyad for each of 1,2,3,4 with 1,2,3,4,5 as the right argument:
  Ṭ              | - Convert to logical list with 1 at the relevant index [[1],[0,1],[0,0,1],[0,0,0,1]]
   ;-            | - Concatenate -1 to this
     +           | - Add (to [1,2,3,4,5])
        ị        | Index into original list
         ṭ@      | Tack onto end the original list
           Wẋ¥€3 | Repeat each inner list 3 times

```

### Main chain part 2 (generates lists for first and second sets of tests)

```
ṭ             Ʋ  | Tack output of part 1 onto the following:
 œcJ             | - Combinations of lengths 1,2,3,4,5
    ;2/          | - Pairwise reduce using concatenation
           Ɗ€€   | - Following as a monad for each innermost list:
       Ṣ         |   - Sort
        ṭ,`      |   - Tacked onto the list paired with itself
               Ḋ | - Remove first (i.e. the combinations of lengths 1 and 2)

```

### Main chain part 3 (runs the tests)

```
                   3ƭ€€€     | For each innermost list, do one of the following three in turn:
       Ʋ                     | - Tests 1 and 2
,U                           |   - Pair with reversed list
  ṢƑ€                        |   - Check whether each invariant if sorted
     o\                      |   - Cumulative or
              Ɗ              | - Tests 4 and 5
        I                    |   - Increments (test 4)
         ,I$                 |   - Paired with increments of increments (test 5)
            E€               |   - Check if all equal for each of these
                  Ɗ          | - Test 3
               I             |   - Increments
                Ị            |   - Absolute value <= 1
                 Ạ           |   - All
                        »/€  | Reduce each using max - picks the best results for each test for each set of tests
                           ¬ | Not (vectorises)

```
> 2 votes

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