title: Watson-Crick palindromes

text:
# Question
Title: Watson-Crick palindromes
# Problem

Create a function that can determine whether or not an arbitrary DNA string is a Watson-Crick palindrome. The function will take a DNA string and output a true value if the string is a Watson-Crick palindrome and a false value if it is not. (True and False can also be represented as 1 and 0, respectively.)

The DNA string may either be in all uppercase or all lowercase depending on your preference.

Also, the DNA string will not be empty.

# Explanation

A DNA string is a Watson-Crick palindrome when the complement of its reverse is equal to itself.

Given a DNA string, first reverse it, and then complement each character according to the DNA bases (A ↔ T and C ↔ G). If the original string is equal to the complemented-reverse string, it is a Watson-Crick palindrome.

For more, see this question. It is a different challenge where you must find the longest substring of a DNA string where that substring is a Watson-Crick palindrome.

# Goal

This is code-golf and the shortest code wins.

# Test Cases

The format is `<input> = <output>`.

```
ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false
ACTG = false

```

# Answer
> 32 votes
# 05AB1E, ~~10~~ 7 bytes

### Code:

```
Â'š×Â‡Q

```

### Explanation:

To check if a string is a palindrome, we just need to check the input with the input, with `at` swapped and `cg` swapped and then reverse it. So that is what we are going to do. We push the input and the input reversed using `Â` (bifurcate). Now comes a tricky part. `'š×` is the compressed version for `creating`. If we reverse it, you can see why it's in the code:

```
CreATinG
|  ||  |
GniTAerC

```

This will be used to transliterate the reversed input. Transliteration is done with . After that, we just check if the input and the transliterated input are e`Q`ual and print that value. So this is how the stack looks like for input `actg` :

```
Â          # ["actg", "gtca"]
 'š×       # ["actg", "gtca", "creating"]
    Â      # ["actg", "gtca", "creating", "gnitaerc"]
     ‡     # ["actg", "cagt"]
      Q    # [0]

```

Which can also be seen with the debug flag (Try it here).

Uses **CP-1252** encoding. Try it online!.

# Answer
> 19 votes
# Jelly, 9 bytes

```
O%8µ+U5ḍP

```

Try it online! or verify all test cases.

### How it works

```
O%8µ+U5ḍP  Main link. Argument: S (string)

O          Compute the code points of all characters.
 %8        Compute the residues of division by 8.
           This maps 'ACGT' to [1, 3, 7, 4].
   µ       Begin a new, monadic link. Argument: A (array of residues)
    +U     Add A and A reversed.
      5ḍ   Test the sums for divisibility by 5.
           Of the sums of all pairs of integers in [1, 3, 7, 4], only 1 + 4 = 5
           and 3 + 7 = 10 are divisible by 5, thus identifying the proper pairings.
        P  Take the product of the resulting Booleans.

```

# Answer
> 12 votes
# Python 2, 56 45 44 bytes

```
lambda s:s==s[::-1].translate("_T_GA__C"*32)

```

# Answer
> 8 votes
# Perl, 27 bytes

Includes +2 for `-lp`

Give input on STDIN, prints 1 or nothing:

```
dnapalin.pl <<< ATCGCGAT

```

`dnapalin.pl`:

```
#!/usr/bin/perl -lp
$_=y/ATCG/TAGC/r=~reverse

```

Replace `$_=` by `$_+=` to get `0` instead of empty for the false case

# Answer
> 7 votes
# Pyth - 10 bytes

```
qQ_XQ"ACGT

```

Try it online here.

A 9 byte version: Try it online here.

# Answer
> 7 votes
## Retina, ~~34~~ 33 bytes

```
$
;$_
T`ACGT`Ro`;.+
+`(.);\1
;
^;

```

Try it online! (Slightly modified to run all test cases at once.)

### Explanation

```
$
;$_

```

Duplicate the input by matching the end of the string and inserting a `;` followed by the entire input.

```
T`ACGT`Ro`;.+

```

Match only the second half of the input with `;.+` and perform the substitution of pairs with a transliteration. As for the target set `Ro`: `o` references the *other* set, that is `o` is replaced with `ACGT`. But `R` reverses this set, so the two sets are actually:

```
ACGT
TGCA

```

If the input is a DNA palindrome, we will now have the input followed by its reverse (separated by `;`).

```
+`(.);\1
;

```

Repeatedly (`+`) remove a pair of identical characters around the `;`. This will either continue until only the `;` is left or until the two characters around the `;` are no longer identical, which would mean that the strings aren't the reverse of each other.

```
^;

```

Check whether the first character is `;` and print `0` or `1` accordingly.

# Answer
> 6 votes
## JavaScript (ES6), 59 bytes

```
f=s=>!s||/^(A.*T|C.*G|G.*C|T.*A)$/.test(s)&f(s.slice(1,-1))

```

Best I could do without using Regexp was 62 bytes:

```
f=s=>!s||parseInt(s[0]+s.slice(-1),33)%32%7<1&f(s.slice(1,-1))

```

# Answer
> 6 votes
# Ruby, 35

I tried other ways, but the obvious way was the shortest:

```
->s{s.tr('ACGT','TGCA').reverse==s}

```

**in test program**

```
f=->s{s.tr('ACGT','TGCA').reverse==s}

puts f['ATCGCGAT']
puts f['AGT']
puts f['GTGACGTCAC']
puts f['GCAGTGA']
puts f['GCGC']
puts f['AACTGCGTTTAC']

```

# Answer
> 5 votes
## Haskell, ~~48~~ 45 bytes

```
(==)=<<reverse.map((cycle"TCG_A"!!).fromEnum)

```

Usage example: `(==)=<<reverse.map((cycle"_T_GA__C"!!).fromEnum) $ "ATCGCGAT"`-\> `True`.

A non-pointfree version is

```
f x = reverse (map h x) == x           -- map h to x, reverse and compare to x
h c = cycle "TCG_A" !! fromEnum c      -- take the ascii-value of c and take the
                                       -- char at this position of string
                                       -- "TCG_ATCG_ATCG_ATCG_A..."

```

Edit: @Mathias Dolidon saved 3 bytes. Thanks!

# Answer
> 4 votes
# Retina, 52 bytes

```
^G(.*)C$
$1
^A(.*)T$
$1
^T(.*)A$
$1
}`^C(.*)G$
$1
^$

```

# Answer
> 4 votes
# Julia, ~~47~~ 38 bytes

```
s->((x=map(Int,s)%8)+reverse(x))%5⊆0

```

This is an anonymous function that accepts a `Char` array and returns a boolean. To call it, assign it to a variable.

This uses Dennis' algorithm, which is shorter than the naïve solution. We get the remainder of each code point divided by 8, add that to itself reversed, get the remainders from division by 5, and check whether all are 0. The last step is accomplished using , the infix version of `issubset`, which casts both arguments to `Set` before checking. This means that `[0,0,0]` is declared a subset of `0`, since `Set([0,0,0]) == Set(0)`. This is shorter than an explicit check against 0.

Try it online!

Saved 9 bytes thanks to Dennis!

# Answer
> 4 votes
# Bash + coreutils, ~~43~~ 32 bytes

```
[ `tr ATCG TAGC<<<$1|rev` = $1 ]

```

### Tests:

```
for i in ATCGCGAT AGT GTGACGTCAC GCAGTGA GCGC AACTGCGTTTAC; do ./78410.sh $i && echo $i = true || echo $i = false; done
ATCGCGAT = true
AGT = false
GTGACGTCAC = true
GCAGTGA = false
GCGC = true
AACTGCGTTTAC = false

```

# Answer
> 4 votes
# Jolf, 15 Bytes

Try it!

```
=~A_iγ"AGCT"_γi

```

Explanation:

```
   _i            Reverse the input
 ~A_iγ"AGCT"_γ   DNA swap the reversed input
=~A_iγ"AGCT"_γi  Check if the new string is the same as the original input

```

# Answer
> 3 votes
# Jolf, 16 bytes

Try it here!

```
pe+i~Aiγ"GATC"_γ

```

## Explanation

```
pe+i~Aiγ"GATC"_γ
    ~Aiγ"GATC"_γ  perform DNA transformation
  +i              i + (^)
pe                is a palindrome

```

# Answer
> 3 votes
# Factor, 72 bytes

Unfortunately regex can't help me here.

```
[ dup reverse [ { { 67 71 } { 65 84 } { 71 67 } { 84 65 } } at ] map = ]

```

Reverse, lookup table, compare equal.

# Answer
> 3 votes
## Actually, 19 bytes

```
O`8@%`M;RZ`5@Σ%Y`Mπ

```

This uses Dennis's algorithm.

Try it online!

Explanation:

```
O`8@%`M;RZ`5@Σ%Y`Mπ
O                    push an array containing the Unicode code points of the input
 `8@%`M              modulo each code point by 8
       ;RZ           zip with reverse
          `5@Σ%Y`M   test sum for divisibility by 5
                  π  product

```

# Answer
> 3 votes
# C,71

```
r,e;f(char*s){for(r=0,e=strlen(s)+1;*s;s++)r|=*s*s[e-=2]%5^2;return!r;}

```

2 bytes saved by Dennis. Additional 2 bytes saved by adapting for lowercase input: constants `37` and `21` are revised to `5` and `2`.

# C,75

```
i,j;f(char*s){for(i=j=0;s[i];i++)j|=s[i]*s[strlen(s)-i-1]%37!=21;return!j;}

```

Saved one byte: Eliminated parenthesis by taking the product of the two ASCII codes mod 37. The valid pairs evaluate to 21. Assumes uppercase input.

# C,76

```
i,j;f(char*s){for(i=j=0;s[i];i++)j|=(s[i]+s[strlen(s)-i-1])%11!=6;return!j;}

```

Uses the fact that ASCII codes of the valid pairs sum to 138 or 149. When taken mod 11, these are the only pairs that sum to 6. Assumes uppercase input.

**ungolfed in test program**

```
i,j;

f(char *s){
   for(i=j=0;s[i];i++)                  //initialize i and j to 0; iterate i through the string
     j|=(s[i]+s[strlen(s)-i-1])%11!=6;  //add characters at i from each end of string, take result mod 11. If not 6, set j to 1
return!j;}                              //return not j (true if mismatch NOT detected.)

main(){
  printf("%d\n", f("ATCGCGAT"));
  printf("%d\n", f("AGT"));
  printf("%d\n", f("GTGACGTCAC"));
  printf("%d\n", f("GCAGTGA"));
  printf("%d\n", f("GCGC"));
  printf("%d\n", f("AACTGCGTTTAC"));
}

```

# Answer
> 3 votes
# Oracle SQL 11.2, 68 bytes

```
SELECT DECODE(TRANSLATE(REVERSE(:1),'ATCG','TAGC'),:1,1,0)FROM DUAL;

```

# Answer
> 3 votes
# J - 21 bytes

```
0=[:+/5|[:(+|.)8|3&u:

```

Based on Dennis' method

## Usage

```
   f =: 0=[:+/5|[:(+|.)8|3&u:
   f 'ATCGCGAT'
1
   f 'AGT'
0
   f 'GTGACGTCAC'
1
   f 'GCAGTGA'
0
   f 'GCGC'
1
   f 'AACTGCGTTTAC'
0
   f 'ACTG'
0

```

## Explanation

```
0=[:+/5|[:(+|.)8|3&u:
                 3&u:    - Convert from char to int
               8|        - Residues from division by 8 for each
            |.           - Reverse the list
           +             - Add from the list and its reverse element-wise
        [:               - Cap, compose function
      5|                 - Residues from division by 5 for each
    +/                   - Fold right using addition to create a sum
  [:                     - Cap, compose function
0=                       - Test the sum for equality to zero

```

# Answer
> 3 votes
# R, 101 bytes

```
g=function(x){y=unlist(strsplit(x,""));all(sapply(rev(y),switch,"C"="G","G"="C","A"="T","T"="A")==y)}

```

### Test Cases

```
g("ATCGCGAT")
[1] TRUE
g("AGT")
[1] FALSE
g("GTGACGTCAC")
[1] TRUE
g("GCAGTGA")
[1] FALSE
g("GCGC")
[1] TRUE
g("AACTGCGTTTAC")
[1] FALSE
g("ACTG")
[1] FALSE

```

# Answer
> 3 votes
# Julia 0.4, 22 bytes

```
s->s$reverse(s)⊆""

```

The string contains the control characters EOT (4) and NAK (21). Input must be in form of a character array.

This approach XORs the characters of the input with the corresponding characters in the reversed input. For valid pairings, this results in the characters EOT or NAK. Testing for inclusion in the string of those characters produces the desired Boolean.

Try it online!

# Answer
> 3 votes
## Labyrinth, 42 bytes

```
_8
,%
;
"}{{+_5
"=    %_!
 = """{
 ;"{" )!

```

Terminates with a division-by-zero error (error message on STDERR).

Try it online!

The layout feels really inefficient but I'm just not seeing a way to golf it right now.

### Explanation

This solution is based on Dennis's arithmetic trick: take all character codes modulo `8`, add a pair from both ends and make sure it's divisible by `5`.

Labyrinth primer:

* Labyrinth has two stacks of arbitrary-precision integers, *main* and *aux*(iliary), which are initially filled with an (implicit) infinite amount of zeros.
* The source code resembles a maze, where the instruction pointer (IP) follows corridors when it can (even around corners). The code starts at the first valid character in reading order, i.e. in the top left corner in this case. When the IP comes to any form of junction (i.e. several adjacent cells in addition to the one it came from), it will pick a direction based on the top of the main stack. The basic rules are: turn left when negative, keep going ahead when zero, turn right when positive. And when one of these is not possible because there's a wall, then the IP will take the opposite direction. The IP also turns around when hitting dead ends.
* Digits are processed by multiplying the top of the main stack by 10 and then adding the digit.

The code starts with a small 2x2, clockwise loop, which reads all input modulo 8:

```
_   Push a 0.
8   Turn into 8.
%   Modulo. The last three commands do nothing on the first iteration
    and will take the last character code modulo 8 on further iterations.
,   Read a character from STDIN or -1 at EOF. At EOF we will leave loop.

```

Now `;` discards the `-1`. We enter another clockwise loop which moves the top of the main stack (i.e. the last character) down to the bottom:

```
"   No-op, does nothing.
}   Move top of the stack over to aux. If it was at the bottom of the stack
    this will expose a zero underneath and we leave the loop.
=   Swap top of main with top of aux. The effect of the last two commands
    together is to move the second-to-top stack element from main to aux.
"   No-op.

```

Now there's a short linear bit:

```
{{  Pull two characters from aux to main, i.e. the first and last (remaining)
    characters of the input (mod 8).
+   Add them.
_5  Push 5.
%   Modulo.

```

The IP is now at a junction which acts as a branch to test divisibility by 5. If the result of the modulo is non-zero, we know that the input is not a Watson-Crick palindrome and we turn east:

```
_   Push 0.
!   Print it. The IP hits a dead end and turns around.
_   Push 0.
%   Try to take modulo, but division by zero fails and the program terminates.

```

Otherwise, we need to keep checking the rest of the input, so the IP keeps going south. The `{` pulls over the bottom of the remaining input. If we've exhausted the input, then this will be a `0` (from the bottom of *aux*), and the IP continues moving south:

```
)   Increment 0 to 1.
!   Print it. The IP hits a dead end and turns around.
)   Increment 0 to 1.
{   Pull a zero over from aux, IP keeps moving north.
%   Try to take modulo, but division by zero fails and the program terminates.

```

Otherwise, there are more characters in the string to be checked. The IP turns west and moves into the next (clockwise) 2x2 loop which consists largely of no-ops:

```
"   No-op.
"   No-op.
{   Pull one value over from aux. If it's the bottom of aux, this will be
    zero and the IP will leave the loop eastward.
"   No-op.

```

After this loop, we've got the input on the main stack again, except for its first and last character and with a zero on top. The `;` discards the `0` and then `=` swaps the tops of the stacks, but this is just to cancel the first `=` in the loop, because we're now entering the loop in a different location. Rinse and repeat.

# Answer
> 3 votes
# C#, 65 bytes

```
bool F(string s)=>s.SequenceEqual(s.Reverse().Select(x=>"GACT"[("GACT".IndexOf(x)+2)%4]));

```

.NET has some fairly long framework method names at times, which doesn't necessarily make for the best code golf framework. In this case, framework method names make up 33 characters out of 90. :)

Based on the modulus trick from elsewhere in the thread:

```
bool F(string s)=>s.Zip(s.Reverse(),(a,b)=>a%8+b%8).All(x=>x%5==0);

```

Now weighs in at 67 characters whereof 13 are method names.

Another minor optimization to shave off a whopping 2 characters:

```
bool F(string s)=>s.Zip(s.Reverse(),(a,b)=>(a%8+b%8)%5).Sum()<1;

```

So, 65 of which 13 are framework names.

Edit: Omitting some of the limited "boilerplate" from the solution and adding a couple of conditions leaves us with the expression

```
s.Zip(s.Reverse(),(a,b)=>(a%8+b%8)%5).Sum()

```

Which gives 0 if and only if the string s is a valid answer. As cat points out, "bool F(string s)=\>" is actually replacable with "s=\>" *if* it's otherwise clear in the code that the expression is a `Func<string,bool>`, ie. maps a string to a boolean.

# Answer
> 3 votes
# sed, ~~67~~ 61 bytes

```
G;H;:1;s/\(.\)\(.*\n\)/\2\1/;t1;y/ACGT/TGCA/;G;s/^\(.*\)\1$/1/;t;c0

```

(67 bytes)

### Test

```
for line in ATCGCGAT AGT GTGACGTCAC GCAGTGA GCGC AACTGCGTTTAC ACTG
do echo -n "$line "
    sed 'G;H;:1;s/\(.\)\(.*\n\)/\2\1/;t1;y/ACGT/TGCA/;G;s/^\(.*\)\1$/1/;t;c0' <<<"$line"
done

```

### Output

```
ATCGCGAT 1
AGT 0
GTGACGTCAC 1
GCAGTGA 0
GCGC 1
AACTGCGTTTAC 0
ACTG 0

```

---

By using extended regular expressions, the byte count can be reduced to 61.

```
sed -r 'G;H;:1;s/(.)(.*\n)/\2\1/;t1;y/ACGT/TGCA/;G;s/^(.*)\1$/1/;t;c0'

```

# Answer
> 2 votes
**REXX** 37

```
s='ATCGCGAT';say s=translate(reverse(s),'ATCG','TAGC')

```

# Answer
> 2 votes
# Octave, 52 bytes

```
f=@(s) prod(mod((i=mod(toascii(s),8))+flip(i),5)==0)

```

Following Denis's trick ... take the ASCII values mod 8, flip and add together; if every sum is a multiple of five, you're golden.

# Answer
> 2 votes
# Vyxal, ~~17~~ ~~11~~ ~~10~~ 8 bytes

```
Ṙ«Wṁ«ḂĿ=

```

Try it Online!

### Explained

```
Ṙ«Wṁ«ḂĿ=
Ṙ        # Input reverse
 «Wṁ«ḂĿ  # Changes DNA and translate with string compression
       = # If original input is equal to the result output 1/0

```

# Answer
> 1 votes
# Clojure/ClojureScript, 49 chars

```
#(=(list* %)(map(zipmap"ATCG""TAGC")(reverse %)))

```

Works on strings. If the requirements are loosened to allow lists, I can take off the `(list* )` and save 7 chars.

# Answer
> 1 votes
# R, 70 bytes

```
f=function(x)all(chartr("GCTA","CGAT",y<-strsplit(x,"")[[1]])==rev(y))

```

Usage:

```
> f=function(x)all(chartr("GCTA","CGAT",y<-strsplit(x,"")[[1]])==rev(y))
> f("GTGACGTCAC")
[1] TRUE
> f("AACTGCGTTTAC")
[1] FALSE
> f("AGT")
[1] FALSE
> f("ATCGCGAT")
[1] TRUE

```

# Answer
> 1 votes
# C, 71 bytes

Requires ASCII codes for the relevant characters, but accepts uppercase, lowercase or mixed-case input.

```
f(char*s){char*p=s+strlen(s),b=0;for(;*s;b&=6)b|=*--p^*s++^4;return!b;}

```

This code maintains two pointers, `s` and `p`, traversing the string in opposite directions. At each step, we compare the corresponding characters, setting `b` true if they don't match. The matching is based on XOR of the character values:

```
'A' ^ 'T' = 10101
'C' ^ 'G' = 00100

'C' ^ 'T' = 10111
'G' ^ 'A' = 00110
'A' ^ 'C' = 00010
'T' ^ 'G' = 10011
 x  ^  x  = 00000

```

We can see in the above table that we want to record success for `xx10x` and failure for anything else, so we XOR with `00100` (four) and mask with `00110` (six) to get zero for `AT` or `CG` and non-zero otherwise. Finally, we return true if all the pairs accumulated a zero result in `b`, false otherwise.

## Test program:

```
#include <stdio.h>
int main(int argc, char **argv)
{
    while (*++argv)
        printf("%s = %s\n", *argv, f(*argv)?"true":"false");
}

```

# Answer
> 1 votes
# , 13 chars / 17 bytes

```
⟮ïĪ`ACGT”⟯ᴙ≔Ⅰ

```

`Try it here (Firefox only).`

# Explanation

Transliterate input from `ACGT` to `TGCA` and check if the resulting string is a palindrome.

# Answer
> 1 votes
# , 19 bytes

```
|.-:-&.('+AGCT'i.])

```

Try it online!

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

```
17-#==Reverse@#&@Mod[ToCharacterCode@#,11,2]&

```

Try it online!

Converts `A` to `10`, `T` to `7`, `C` to `12`, and `G` to `5`, by taking the ASCII codes mod 11 with offset 2. Then checks if the resulting list and its reverse add to 17 in each coordinate.

# Answer
> 1 votes
# J-uby, ~~50~~ ~~33~~ 27 bytes

Based on Level River St’s Ruby answer.

```
:=~&(~:tr&'ACGT'&'TGCA'|:~)

```

Attempt This Online!

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

```
min(seq(inString("ATA CGC",sub(Ans,I,1)+sub(Ans,length(Ans)-I+1,1)),I,1,length(Ans

```

Takes input in `Ans` as an uppercase string.

# Answer
> 0 votes
# Wolfram Language (Mathematica), 41 bytes

```
BioSequenceComplement@StringReverse@#==#&

```

Don't Try it online!

Takes input as a BioSequence.

Doesn't work on TIO due to it not supporting StringReverse on a BioSequence. Figured it was worth its own post intead of as a comment on the other Mathematica answer because it's significantly simpler and requires new-ish functionality.

# Answer
> 0 votes
# Raku, 24 bytes

```
{TR/ATCG/TAGC/ eq .flip}

```

Try it online!

Straightforward solution. Translates the characters in the input string to the complementary ones, then compares that to the reverse of the input string.

# Answer
> 0 votes
# Swift 5.9, 87 bytes

```
let f={zip($0+"",$0.reversed()).allSatisfy{($0.0.asciiValue!+$0.1.asciiValue!)%16%5<1}}

```

Dennis' algorithm, slightly golfed down.

---
Tags: code-golf, string, palindrome, bioinformatics
---


# Question
Title: Magical BF: BF code that works in two ways
## Challenge

In this challenge, we will use a language that is very similar to Brainfuck but slightly different.

* This variant of BF does not have any input and output commands; instead, it simply takes a tape as input and modifies it until it halts. The final state of the tape is considered the output of the program.
* The tape is infinitely long to the right, and each cell of the tape can store nonnegative integers of arbitrary size. Each cell is referred to as `tape[0]`, `tape[1]`, ... from the leftmost cell.
* If the data pointer tries to go left from the leftmost cell, it is a no-op. Similarly, if a zero cell is decremented, it is a no-op. Overflow never happens.

| Command | Behavior |
| --- | --- |
| `+` | Increment the current cell. |
| `-` | Decrement the current cell. No-op if the current cell is zero. |
| `>` | Move the data pointer by one cell to the right. |
| `<` | Move the data pointer by one cell to the left. No-op if the current cell is the leftmost cell. |
| `[` | Jump to the right of the matched `]` if the current cell is zero. |
| `]` | Jump to the right of the matched `[` if the current cell is nonzero. |

At the start of the program, the data pointer is at the leftmost cell, as in regular BF.

No characters other than the six commands may appear in the source code. The brackets must be balanced.

For each of the five tasks below, create a square-shaped program that solves the task when interpreted both horizontally and vertically. For example, if a submission is

```
+[-
>+<
-+]

```

the two programs would be

* horizontally: `+[->+<-+]`
* vertically: `+>-[++-<]`

The two code can be the same or different. The score is the side length of the square. The lowest score wins *for each task*. You may choose to solve just one or several of the tasks in one answer.

### Task 1

* Input: `tape[0]` contains an integer \\$x\\$, and `tape[1]` contains an integer \\$y\\$, such that \\$x \ge y\\$. All the other cells are zero.
* Output: `tape[0]` must contain the value of \\$x - y\\$. The other cells may contain any value.

### Task 2

* Input: `tape[0]` contains an integer \\$x\\$. All the other cells are zero.
* Output: `tape[0]` must contain the value of \\$x \operatorname{mod} 7\\$. The other cells may contain any value.

### Task 3

* Input: The tape contains some random values. It is guaranteed that at least one cell is zero.
* Output: `tape[0]` must contain the smallest index `i` such that `tape[i]` in the input is zero. The other cells may contain any value.

### Task 4

* Input: `tape[0]`, `tape[1]`, `tape[2]` contain integers \\$m\\$, \\$a\_1\\$, \\$a\_2\\$ respectively. \\$m \ge 3\\$, \\$a\_1, a\_2 \ge 1\\$. All the other cells are zero.
* Output: `tape[0]` must contain the value of \\$a\_m\\$, which is the \\$m\\$th value in the sequence defined by the first two terms \\$a\_1\\$ and \\$a\_2\\$, and the recurrence equation \\$a\_{n+2} = a\_{n+1} + a\_{n}\\$. The other cells may contain any value.

### Task 5

* Input: `tape[0]` is zero. For some positive integer \\$n\\$, `tape[1]` through `tape[n]` contain positive integers. All the other cells are zero.
* Output: `tape[0]` must contain the maximum of \\$n\\$ positive integers in the input. The other cells may contain any value.

A tester program is provided for you. Insert your BF program and change the `task` variable to test it.

My best scores:

> - Task 1: 3
> - Task 2: 10
> - Task 3: 7
> - Task 4: 10
> - Task 5: 9
>
> In the original problem, you get 100% credit at 3/11/7/11/9 score respectively. I was able to outgolf it by 1 in tasks 2 and 4.

---

Source: Estonian Informatics Olympiad 2020-2021 Open Competition, Problem 6 "Magical BF"

---

If you think this is off-topic, please read the meta section of the sandbox post and leave comments.

# Answer
# Task 2, Score: 9

```
[>>+<+<-]
>-<->-><<
><>----[>
+------<>
<>--<--<>
+----+-++
<>----]>>
-<[<<+>>-
]<>>>+>--

```

Attempt This Online!

I wouldn't be too surprised if 8 was possible. I basically just solved the task in a few different ways, picked the one which seemed like it would square the best, chucked it into a 9x9 and tweaked things until it all lined up nicely. You'll note that the square is symmetric along the diagonal, so horizontal and vertical both result in the same code.

The original code is

```
[>>+<+<-]>------[>-------<-------]>[<<+>>-]

```

We can see how the square code is built from the original:

```
[>>+<+<-]>-<->-><<><>----[>+------<><>--<--<>+----+-++<>----]>>-<[<<+>>-]<>>>+>--
[>>+<+<-]>-   -      ----[>  -----    --<--    ---        --]>   [<<+>>-]

```
> 6 votes

# Answer
# Task 1, score = 3

```
><>
[-<
->]

```

Attempt This Online!
> 5 votes

# Answer
I will share my own solutions that are matched or outgolfed.

# Task 1, score 3

```
>[-
<->
><]

```

Attempt This Online!

This can be easily shown optimal: the shortest flattened BF program that solves the challenge is `>[-<->]` (7 instructions).

# Task 2, score 10

> ```
> >+++++++<[
> +->->+<<[-
> +>][]>><<-
> +-[><]>[-<
> +>]<<<<-][
> ++>]<>>[<<
> +<>><>-][>
> +<<[-[]>]>
> <[<-]<[]>]
> [--<[<>>]]
> ```

Attempt This Online!

I had to solve tasks 3 and 5 before I could finish this one. The approach I used: (spoilered for those who want to figure out themselves)

> When I failed to complete the square for Task 2, I thought this is mainly because of the parity of the number of instructions inside each loop. As I solved tasks 3 and 5, I found a trick that solves the problem: loop as comments. Specifically, if you put `[` right after a `]`, the latter loop is automatically a bulk no-op. For this trick to work better, I needed a base solution that has many short loops.

> So I rewrote the base solution for Task 2 several times to finally get
>
> ```
> >+++++++<[>->+<<[>]>[-<+>]<<<<-]>>[<<+>>-]
> ```
>
> which also happens to be pretty short on its own (even shorter than CursorCoercer's by 1 byte).
> 2 votes

---
Tags: code-challenge, source-layout, brainfuck
---


title: Strings without twin letters

text:
# Question
Title: Strings without twin letters
Consider an arbitrary set of letters \\$L\\$. It may either be \\$\\{A, B, C\\}\\$, \\$\\{M, N, O, P\\}\\$, \\$\\{N, F, K, D\\}\\$, or even contain all the 26 letters. Given an instance of \\$L\\$ and a positive integer \\$n\\$, how many \\$n\\$-letter words can we build from \\$L\\$ such that no adjacent letters are the same (so for example A*BB*C is not allowed from \\$\\{A, B, C\\}\\$)?

This can be solved using combinatorics, but what those words are?

## Input

A non-empty string \\$L\\$ and a positive integer \\$n \> 0\\$.

You choose to accept only lowercase letters, only uppercase letters, or both, as input for \\$L\\$.

Also, note that a valid \\$L\\$ won't contain any duplicate letters, so `ABCA` is an invalid input and should not be handled.

## Output

A list of all strings of length \\$n\\$ that can be formed from \\$L\\$ such that no adjacent letters are the same.

You can repeat letters, so a valid solution for \\$L=\\{A, B, C\\}\\$ and \\$n=3\\$ is ABA, ABC, ACB, ACA, BAC, BCA, BAB, BCB, CAB, CBA, CAC and CBC.

Also note that \\$|L| \< n\\$ is possible, so a valid solution for \\$L=\\{A, B\\}\\$ and \\$n=3\\$ is only ABA and BAB.

And yes, \\$|L| \> n\\$ is also possible, so a valid solution for \\$L=\\{A, B, C, D\\}\\$ and \\$n=3\\$ is ABA, ABC, ABD, ACA, ACB, ACD, ADA, ADB, ADC, BAB, BAC, BAD, BCA, BCB, BCD, BDA, BDB, BDC, CAB, CAC, CAD, CBA, CBC, CBD, CDA, CDB, CDC, DAB, DAC, DAD, DBA, DBC, DBD, DCA, DCB and DCD.

The output doesn't have to be in a particular order.

### Test samples

```
ABC, 3 -> ABA, ABC, ACA, ACB, BAB, BAC, BCA, BCB, CAB, CAC, CBA, CBC
AB, 3 -> ABA, BAB
ABCD, 3 -> ABA, ABC, ABD, ACA, ACB, ACD, ADA, ADB, ADC, BAB, BAC, BAD, BCA, BCB, BCD, BDA, BDB, BDC, CAB, CAC, CAD, CBA, CBC, CBD, CDA, CDB, CDC, DAB, DAC, DAD, DBA, DBC, DBD, DCA, DCB, DCD
OKAY, 2 -> OK, OA, OY, KO, KA, KY, AO, AK, AY, YO, YK, YA
CODEGLF, 3 -> COC, COD, COE, COG, COL, COF, CDC, CDO, CDE, CDG, CDL, CDF, CEC, CEO, CED, CEG, CEL, CEF, CGC, CGO, CGD, CGE, CGL, CGF, CLC, CLO, CLD, CLE, CLG, CLF, CFC, CFO, CFD, CFE, CFG, CFL, OCO, OCD, OCE, OCG, OCL, OCF, ODC, ODO, ODE, ODG, ODL, ODF, OEC, OEO, OED, OEG, OEL, OEF, OGC, OGO, OGD, OGE, OGL, OGF, OLC, OLO, OLD, OLE, OLG, OLF, OFC, OFO, OFD, OFE, OFG, OFL, DCO, DCD, DCE, DCG, DCL, DCF, DOC, DOD, DOE, DOG, DOL, DOF, DEC, DEO, DED, DEG, DEL, DEF, DGC, DGO, DGD, DGE, DGL, DGF, DLC, DLO, DLD, DLE, DLG, DLF, DFC, DFO, DFD, DFE, DFG, DFL, ECO, ECD, ECE, ECG, ECL, ECF, EOC, EOD, EOE, EOG, EOL, EOF, EDC, EDO, EDE, EDG, EDL, EDF, EGC, EGO, EGD, EGE, EGL, EGF, ELC, ELO, ELD, ELE, ELG, ELF, EFC, EFO, EFD, EFE, EFG, EFL, GCO, GCD, GCE, GCG, GCL, GCF, GOC, GOD, GOE, GOG, GOL, GOF, GDC, GDO, GDE, GDG, GDL, GDF, GEC, GEO, GED, GEG, GEL, GEF, GLC, GLO, GLD, GLE, GLG, GLF, GFC, GFO, GFD, GFE, GFG, GFL, LCO, LCD, LCE, LCG, LCL, LCF, LOC, LOD, LOE, LOG, LOL, LOF, LDC, LDO, LDE, LDG, LDL, LDF, LEC, LEO, LED, LEG, LEL, LEF, LGC, LGO, LGD, LGE, LGL, LGF, LFC, LFO, LFD, LFE, LFG, LFL, FCO, FCD, FCE, FCG, FCL, FCF, FOC, FOD, FOE, FOG, FOL, FOF, FDC, FDO, FDE, FDG, FDL, FDF, FEC, FEO, FED, FEG, FEL, FEF, FGC, FGO, FGD, FGE, FGL, FGF, FLC, FLO, FLD, FLE, FLG, FLF
NFKD, 4 -> NFNF, NFNK, NFND, NFKN, NFKF, NFKD, NFDN, NFDF, NFDK, NKNF, NKNK, NKND, NKFN, NKFK, NKFD, NKDN, NKDF, NKDK, NDNF, NDNK, NDND, NDFN, NDFK, NDFD, NDKN, NDKF, NDKD, FNFN, FNFK, FNFD, FNKN, FNKF, FNKD, FNDN, FNDF, FNDK, FKNF, FKNK, FKND, FKFN, FKFK, FKFD, FKDN, FKDF, FKDK, FDNF, FDNK, FDND, FDFN, FDFK, FDFD, FDKN, FDKF, FDKD, KNFN, KNFK, KNFD, KNKN, KNKF, KNKD, KNDN, KNDF, KNDK, KFNF, KFNK, KFND, KFKN, KFKF, KFKD, KFDN, KFDF, KFDK, KDNF, KDNK, KDND, KDFN, KDFK, KDFD, KDKN, KDKF, KDKD, DNFN, DNFK, DNFD, DNKN, DNKF, DNKD, DNDN, DNDF, DNDK, DFNF, DFNK, DFND, DFKN, DFKF, DFKD, DFDN, DFDF, DFDK, DKNF, DKNK, DKND, DKFN, DKFK, DKFD, DKDN, DKDF, DKDK
JOHN, 5 -> JOJOJ, JOJOH, JOJON, JOJHJ, JOJHO, JOJHN, JOJNJ, JOJNO, JOJNH, JOHJO, JOHJH, JOHJN, JOHOJ, JOHOH, JOHON, JOHNJ, JOHNO, JOHNH, JONJO, JONJH, JONJN, JONOJ, JONOH, JONON, JONHJ, JONHO, JONHN, JHJOJ, JHJOH, JHJON, JHJHJ, JHJHO, JHJHN, JHJNJ, JHJNO, JHJNH, JHOJO, JHOJH, JHOJN, JHOHJ, JHOHO, JHOHN, JHONJ, JHONO, JHONH, JHNJO, JHNJH, JHNJN, JHNOJ, JHNOH, JHNON, JHNHJ, JHNHO, JHNHN, JNJOJ, JNJOH, JNJON, JNJHJ, JNJHO, JNJHN, JNJNJ, JNJNO, JNJNH, JNOJO, JNOJH, JNOJN, JNOHJ, JNOHO, JNOHN, JNONJ, JNONO, JNONH, JNHJO, JNHJH, JNHJN, JNHOJ, JNHOH, JNHON, JNHNJ, JNHNO, JNHNH, OJOJO, OJOJH, OJOJN, OJOHJ, OJOHO, OJOHN, OJONJ, OJONO, OJONH, OJHJO, OJHJH, OJHJN, OJHOJ, OJHOH, OJHON, OJHNJ, OJHNO, OJHNH, OJNJO, OJNJH, OJNJN, OJNOJ, OJNOH, OJNON, OJNHJ, OJNHO, OJNHN, OHJOJ, OHJOH, OHJON, OHJHJ, OHJHO, OHJHN, OHJNJ, OHJNO, OHJNH, OHOJO, OHOJH, OHOJN, OHOHJ, OHOHO, OHOHN, OHONJ, OHONO, OHONH, OHNJO, OHNJH, OHNJN, OHNOJ, OHNOH, OHNON, OHNHJ, OHNHO, OHNHN, ONJOJ, ONJOH, ONJON, ONJHJ, ONJHO, ONJHN, ONJNJ, ONJNO, ONJNH, ONOJO, ONOJH, ONOJN, ONOHJ, ONOHO, ONOHN, ONONJ, ONONO, ONONH, ONHJO, ONHJH, ONHJN, ONHOJ, ONHOH, ONHON, ONHNJ, ONHNO, ONHNH, HJOJO, HJOJH, HJOJN, HJOHJ, HJOHO, HJOHN, HJONJ, HJONO, HJONH, HJHJO, HJHJH, HJHJN, HJHOJ, HJHOH, HJHON, HJHNJ, HJHNO, HJHNH, HJNJO, HJNJH, HJNJN, HJNOJ, HJNOH, HJNON, HJNHJ, HJNHO, HJNHN, HOJOJ, HOJOH, HOJON, HOJHJ, HOJHO, HOJHN, HOJNJ, HOJNO, HOJNH, HOHJO, HOHJH, HOHJN, HOHOJ, HOHOH, HOHON, HOHNJ, HOHNO, HOHNH, HONJO, HONJH, HONJN, HONOJ, HONOH, HONON, HONHJ, HONHO, HONHN, HNJOJ, HNJOH, HNJON, HNJHJ, HNJHO, HNJHN, HNJNJ, HNJNO, HNJNH, HNOJO, HNOJH, HNOJN, HNOHJ, HNOHO, HNOHN, HNONJ, HNONO, HNONH, HNHJO, HNHJH, HNHJN, HNHOJ, HNHOH, HNHON, HNHNJ, HNHNO, HNHNH, NJOJO, NJOJH, NJOJN, NJOHJ, NJOHO, NJOHN, NJONJ, NJONO, NJONH, NJHJO, NJHJH, NJHJN, NJHOJ, NJHOH, NJHON, NJHNJ, NJHNO, NJHNH, NJNJO, NJNJH, NJNJN, NJNOJ, NJNOH, NJNON, NJNHJ, NJNHO, NJNHN, NOJOJ, NOJOH, NOJON, NOJHJ, NOJHO, NOJHN, NOJNJ, NOJNO, NOJNH, NOHJO, NOHJH, NOHJN, NOHOJ, NOHOH, NOHON, NOHNJ, NOHNO, NOHNH, NONJO, NONJH, NONJN, NONOJ, NONOH, NONON, NONHJ, NONHO, NONHN, NHJOJ, NHJOH, NHJON, NHJHJ, NHJHO, NHJHN, NHJNJ, NHJNO, NHJNH, NHOJO, NHOJH, NHOJN, NHOHJ, NHOHO, NHOHN, NHONJ, NHONO, NHONH, NHNJO, NHNJH, NHNJN, NHNOJ, NHNOH, NHNON, NHNHJ, NHNHO, NHNHN

```

# Answer
# Husk, 4 bytes

```
fΛ≠π

```

Try it online!

Short and straightforward solution, the MVP here is `Λ`, thanks to its overload that can take a binary function and use it to check pairs of adjacent elements.

### Explanation

```
fΛ≠π
   π    Cartesian power of L and n (generates all possible words)
f       Filter those
 Λ        for which all adjacent letters
  ≠           are different

```
> 12 votes

# Answer
# Google Sheets, 88 bytes

```
=let(L,torow(A:A,1),reduce(,sequence(B1),lambda(a,_,sort(tocol(if(left(a)=L,,L&a),1)))))

```

Put letters \\$L\\$ in column `A:A`, the target length \\$n\\$ in cell `B1`, and the formula in cell `D1`.

The formula generates all possible strings of length \\$n\\$ from the alphabet \\$L\\$ with repeats, and while building a string, refuses it if its first character is the same as the one currently being prepended.

Ungolfed:

```
=let(
  letters, torow(A1:A, 1),
  n, B1,
  blank, iferror(ø),
  reduce(blank, sequence(n), lambda(acc, curr,
    sort(
      tocol(if(left(acc) = letters, blank, letters & acc), 1)
    )
  ))
)

```

`acc` is a vertical array, and `letters` is a horizontal array. The `sort()` function is array enabled, which means that the inner comparison and concatenation produce `acc` × `letters` results each round. `tocol()` then flattens the result, weeding out blanks generated by the `if()`.

Hat tip to JvdV for the `left(acc) = letters` pattern.
> 8 votes

# Answer
# Haskell, ~~49~~ 47 bytes

```
l#1=pure<$>l
l#n=[c:a:r|a:r<-l#(n-1),c<-l,a/=c]

```

Try it online!

Edit: Thanks to @xnor for taking off two bytes! I didn't know you could remove the parentheses in that context
> 7 votes

# Answer
# Ruby, 42 bytes

```
->l,n{(?A*n..?Z*n).grep_v /[^#{l}]|(.)\1/}

```

Attempt This Online!

Input in uppercase. Start with a list of all \\$n\\$-letter strings, then remove those containing letters not in \\$L\\$ or double letters.
> 7 votes

# Answer
# JavaScript (ES10), 54 bytes

Expects `(a)(n)`, where `a` is an array of characters. Returns an array of strings.

```
a=>g=(n,o,p)=>n--?a.flatMap(c=>p!=c?g(n,[o]+c,c):[]):o

```

Try it online!

### Commented

```
a =>             // outer function taking a[]
g = (            // inner recursive function taking:
  n,             //   n = expected length
  o,             //   o = output string, initially undefined
  p              //   p = previous character in the output,
) =>             //       initially undefined
n-- ?            // if we don't have enough characters:
  a.flatMap(c => //   for each character c in a[]:
    p != c ?     //     if the previous char. is not equal to c:
      g(         //       do a recursive call:
        n,       //         pass the updated value of n
        [o] + c, //         coerce o to a string and append c to o
        c        //         set p = c
      )          //       end of recursive call
    :            //     else:
      []         //       abort
  )              //   end of flatMap()
:                // else:
  o              //   return the output

```
> 5 votes

# Answer
# Vyxal, 5 bytes

```
↔'ÞǓ⁼

```

Try it Online!

generates all combinations of length n using the characters in the input string, then filters by those which are equal to the string with all adjacent duplicates removed.
> 5 votes

# Answer
# C (gcc), ~~168~~ ~~160~~ ~~119~~ 114 bytes

*-8 Thanks to @corvus\_192 for pointing out newline separation between values was allowed, and a massive -41 thanks to @tsh, a further -5 thanks to @ceilingcat*

```
char*l,*c;f(n,i){n?(c[n-1]=l[i])&&(l[i]-c[n]&&f(n-1,0),f(n,i+1)):puts(c);}g(e,n)char*e;{c=calloc(n,2);l=e;f(n,0);}

```

Try it online!

Prints the newline separated output to STDOUT.
> 5 votes

# Answer
# K (ngn/k), 22 21 18 bytes:

-1 byte due to @ovs. -3 bytes thanks to @ngn.

```
{(|/'=':')_+!y#,x}

```

Try it online
> 5 votes

# Answer
# Python 3, ~~74~~ ~~67~~ 64 bytes

*-7 thanks to @Albert.Lang, -3 thanks to @Mukundan314*

```
f=lambda l,n:[""][n:]or[c+w for w in f(l,n-1)for c in{*l}-{*w[:1]}]

```

Try it online!
> 4 votes

# Answer
# MATL, 9 bytes

```
Z^t!dXAY)

```

Try it online!

### Explanation

```
Z^    % Implicit inputs. Cartesian product. Gives a character matrix where
      % each row is a Cartesian tuple (*)
t!    % Duplicate, transpose
d     % Consecutive differences, computed along vertical dimension
XA    % Vertical-all: gives true for columns that only contain nonzeros
Y)    % Use as logical index into the rows of (*). Implicit display

```
> 4 votes

# Answer
# , 70 bytes

```
\(L,n,x=combn(rep(L,n+1),n))unique(x[,apply(x,2,\(a)all(diff(a)))],,2)

```

Attempt This Online!

Uses a rather loose definition of string \- a vector of character codes. Outputs a matrix with unique words in columns.
> 4 votes

# Answer
# Perl 5 `-nl`, 30 bytes

```
map!/(.)\1/&&say,glob"{$_}"x<>

```

Try it online!
> 4 votes

# Answer
# APL+WIN, 42 bytes

Prompts for string followed by n:

```
n←m←⎕⋄⍎∊(⎕-1)⍴⊂'n←n∘.,m⋄'⋄(0=+/¨2=/¨,n)/,n

```

Try it online! Thanks to Dyalog Classic
> 3 votes

# Answer
# Uiua SBCS, ~~23~~ ~~21~~ 20 bytes

```
▽≡(/×≡/≠◫2).⊏☇1⇡▽:⧻,

```

Try it!

```
▽≡(/×≡/≠◫2).⊏☇1⇡▽:⧻,
                  ⧻,  # length of the set, call it L
               ⇡▽:    # permutations w/ repetition of [0..n) with length L
             ☇1       # change to rank 2
            ⊏         # index into set
           .          # duplicate
 ≡(       )           # map each row
        ◫2            # windows of length 2
     ≡/≠              # reduce each row by inequality
   /×                 # product
▽                     # keep

```
> 3 votes

# Answer
# Excel ms365, ~~85~~ 84 bytes

* -1 thanks to doubleunary's tip to apply `LEFT()` instead of `RIGHT()`.

Assuming:

* \\$L\\$ \- Given input in the first row `1:1` starting from `A1` onwards;
* \\$n\\$ \- Given integer in `A2`.

Formula, thus output, in `A4` spilled down:

```
=LET(L,TOROW(1:1,1),REDUCE("",TAKE(L,,A2),LAMBDA(x,n,TOCOL(IFS(LEFT(x)<>L,L&x),3))))

```
> 3 votes

# Answer
# Jelly, 6 bytes

```
ṗnƝẠ$Ƈ

```

A dyadic Link that accepts the alphabet on the left and the word length on the right and yields a list of valid words.

**Try it online!**

### How?

```
ṗnƝẠ$Ƈ - Link: Alphabet, WordLength
ṗ      - {Alphabet} Cartesian power {WordLength} -> all words
     Ƈ - keep those for which:
    $  -   last two links as a monad - f(Word):
  Ɲ    -     for neighbouring pairs:
 n     -       not equal?
   Ạ   -     all?

```

...if one didn't need to handle an alphabet of length one, then five bytes would do - `ṗnƝÐṀ` (keep those words which are maximal under neighbourwise not-equal).
> 3 votes

# Answer
# Charcoal, 20 bytes

```
⊞υωＦＮ≔ΣＥηＥΦυ⌕μκ⁺κμυυ

```

Attempt This Online! Link is to verbose version of code. Explanation:

```
⊞υω

```

Start with the empty string.

```
ＦＮ

```

Loop `n` times.

```
≔ΣＥηＥΦυ⌕μκ⁺κμυ

```

For each letter of `L`, prefix it to each string so far that does not begin with that letter, then concatenate all of the results together. (Prefixing each letter of `L` that the string does not begin with fails when there are no strings in the list.)

```
υ

```

Output the final list.
> 2 votes

# Answer
# Brachylog, ~~13~~ 10 bytes

*-3 bytes inspired by a suggestion from Fatalize*

```
gʰj₎∋ᵐ.ẹ~ḅ

```

Generator solution. Takes input as a list containing a string and an integer. Returns solutions as lists of single-character strings. Try it online!

### Explanation

This feels like it should be shorter. Part of the problem is that Brachylog starts getting verbose when you have to deal with anything past one input and one output.

```
gʰj₎∋ᵐ.ẹ~ḅ
             Input: list containing string and number
gʰ           Wrap the first element in a singleton list
  j₎         Concatenate that list with itself (second element) times
    ∋ᵐ       Select one character from each of those strings
      .      This will be the output
       ẹ     Convert each character to a list of its characters (i.e.
              wrap it in a singleton list)
        ~ḅ   Assert that this is the same as the result of partitioning
              some list into runs of identical elements
             ... and that that list is the output

```

To help clarify the ending bit: The predicate  converts each string in its input into a list of its characters. The predicate  finds all runs of consecutive identical values in its input. The `.ẹ~ḅ` structure applies  to the list, then *unapplies*  to that result, then requires *that* result to be the same list we started with. This is the same as saying that  and  must give the same result when applied to the list. So:

* Given the list `["a","b","b"]`,  outputs `[["a"],["b"],["b"]]` and  outputs `[["a"],["b","b"]]`. Those don't match, so the predicate fails.
* Given the list `["a","b","a"]`,  outputs `[["a"],["b"],["a"]]` and  outputs `[["a"],["b"],["a"]]`. Those do match, so the predicate succeeds.
> 2 votes

# Answer
# Retina, 41 bytes

```
"$&"+%Lw$`,.*(.)
$`$1$&$'
\d|,.+

A`(.)\1

```

Try it online! Link includes test cases. Takes comma-separated input. Explanation:

```
"$&"+`

```

Repeat `n` times...

```
%Lw$`,.*(.)
$`$1$&$'

```

Replicate each line for each letter of `L` but inserting a copy of the letter before the comma.

```
\d|,.+

```

Remove the copies of `n` and `L`.

```
A`(.)\1

```

Remove all lines with duplicate adjacent letters.
> 2 votes

# Answer
# 05AB1E, 5 bytes

```
ãʒüÊP

```

Inputs in the order \\$n,L\\$.

Try it online or verify all test cases.

Or alternatively:

```
ãʒDÔQ

```

Try it online or verify all test cases.

**Explanation:**

```
ã      # Cartesian product on both (implicit) inputs to get all n-sized strings using
       # characters from L
 ʒ     # Filter it by:
  ü    #  Map over each overlapping pair:
   Ê   #   Check that they're NOT equal
    P  #  Check that all of them are truthy
       # (after which the filtered list is output implicitly)

  D    #  Duplicate the current string
   Ô   #  Connected uniquify it, collapsing all equal adjacent characters
    Q  #  Check if the connected uniquified string is still the same

```
> 2 votes

# Answer
# Perl 5 \+ `-lF -M5.10.0`, 40 bytes

```
!/[^@F]|(.)\1/&&say for A x($;=<>)..Z x$
```

Try it online!
> 2 votes

# Answer
# Nekomata, 4 bytes

```
ŧĉᵐz

```

Attempt This Online!

```
ŧĉᵐz    Take input L and n
ŧ       Find an n-tuple of elements of L
 ĉ      Split into runs of equal elements
  ᵐ     For each run:
   z        Check that it contains exactly one element, and take that element

```
> 2 votes

# Answer
# **, ~~65~~ 64 bytes**

```
\(L,n,A=expand.grid(rep(list(L),n)))A[!rowSums(A[,-n]==A[,-1]),]

```

Assuming `L` is a vector of characters.

**-1 byte thanks to @pajonk!**

Try it online here!
> 2 votes

# Answer
# Scala 3, 128 bytes

A Port of @Arnold Palmer's Python answer in Scala.

---

Golfed version. Attempt This Online!

```
type Q=String;
def g(l:Q,n:Int,c:Q=""):Seq[Q]={if(n==0)Seq("");else{for{a<-l if a.toString!=c;b<-g(l,n-1,a.toString)}yield a+b}}

```

Ungolfed version. Attempt This Online!

```
def generateCombinations(l: String, n: Int, c: String = ""): Seq[String] = {
    if (n == 0) Seq("")
    else {
      for {
        a <- l
        if a.toString != c
        b <- generateCombinations(l, n - 1, a.toString)
      } yield a + b
    }
  }

```
> 1 votes

# Answer
# jq, 67 bytes

```
def f($n):combinations($n)|join("")|select(test("(.)\\1";"x")|not);

```

Try it online!

Defines a function `f` which takes \\$L\\$ as input and \\$n\\$ as an argument.
> 1 votes

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


title: Randomly capitalize half of a string

text:
# Question
Title: Randomly capitalize half of a string
Given string `s` of even length as input, randomly capitalize exactly half of the letters.

* You can assume the input will always be a non-zero, even length
* You can assume the input will consist of only lowercase letters (`[a-z]`)
* Exactly half of the letters should be capitalized in the output
* Every permutation that has exactly half of the characters capitalized should have an equal probability of being output

## Scoring

This is so fewest bytes **in each language** wins!

# Answer
> 11 votes
# 05AB1E, 7 bytes

### Code

Uses the 05AB1E codepage.

```
ā.rÈÅÏu

```

Try it online!

### Explanation

```
             # *example input: "**abcdefgh**"*
ā            # Indices of the input                   -> ex. [1, 2, 3, 4, 5, 6, 7, 8]
 .r          # Randomly shuffle this list             -> ex. [5, 4, 6, 3, 2, 8, 1, 7]
   È         # Map (x % 2 == 0) on each element       -> ex. [0, 1, 1, 0, 1, 1, 0, 0]
    ÅÏ       # Apply the following on truthy indices:
      u      #   Convert to uppercase                 -> ex. "aBCdEFgh"

```

# Answer
> 7 votes
# Python, 86 bytes

```
lambda s:bytes(map(int.__xor__,s,sample(len(s)//2*[0,32],len(s))))
from random import*
```

Attempt This Online!

Uses Rɪᴋᴇʀ's idea to toggle case using `^32`, but taken a bit further.

-1 byte thanks to @ovs.

# Answer
> 6 votes
# Jelly, 8 bytes

```
ŒuJḂẊTƲ¦
```

Attempt This Online!

Using the mod-2 trick from Adnan's 05AB1E answer.

Explanation:

```
ŒuJḂẊTƲ¦

Œu   TƲ¦   uppercase at truthy indices:
  J          range [1..length(input()]
   Ḃ         each modulo 2
    Ẋ        random permutation

```

`JḂ` essentially creates `[0, 1, 0, 1, ..., 0, 1]` up to the length of the input.

# Jelly, 9 bytes

```
ŒuJẊŒHḢƲ¦
```

Attempt This Online!

Explanation:

```
ŒuJẊŒHḢƲ¦

Œu     Ʋ¦   uppercase at indices:
  JẊ          random permutation of [1..length(input)]
    ŒH        split that list into two halves
      Ḣ       take the first of those two halves

```

I think there ought to be a shorter way of doing the `JẊŒHḢ`, ~~perhaps by picking a random combination~~nope. Or, at least, a shorter version of `ŒHḢ`.

# Answer
> 6 votes
# , ~~52~~ ~~51~~ 33 bytes

Or **\>=4.1, 25 bytes** by replacing the word `function` with `\`.

```
function(s)s-sample(seq(s))%%2*32

```

Try it online!

Inputs and outputs through vector of character codes.

Inspired by @Adnan's solution.

# Answer
> 6 votes
# APL (Dyalog Extended), ~~14~~ 9 bytes

−5 bytes thanks to ovs.

Anonymous tacit prefix function

```
⌈@(2|≢?≢)

```

Try it online!

uppercase

`@(``)` at the positions indicated by the following mask:

`≢?≢` shuffle the indices 1 through the tally of elements in the argument (lit. take n random elements from 1…n, without replacement)

`2|` division remainders when divided by 2

# Answer
> 6 votes
# C (clang), ~~57~~ 56 bytes

```
i,r;f(*s,z){for(i=z;s[r=rand()%z]>96?s[r]-=32,i-=2:i;);}

```

Try it online!

* takes a pointer to a widechar string and modifies it.

# Answer
> 5 votes
# JavaScript (Node.js), 76 bytes

```
f=s=>(S=Buffer(s).map(c=>c^=Math.random(n++)<.5?32:--n-n--,n=0),n?f(s):S)+''

```

Try it online!

### Commented

```
f = s =>               // s = input string
( S =                  // S = output
  Buffer(s)            // turn s into a buffer
  .map(c =>            // for each ASCII code c in s:
    c ^=               //   update c:
      Math.random(n++) //     increment n
      < .5 ?           //     with 1/2 probability:
        32             //       turn c into uppercase
      :                //     or:
        --n - n--,     //       leave c unchanged and decrement n twice
    n = 0              //   start with n = 0
  ),                   // end of map()
  n ? f(s)             // try again if we haven't capitalized exactly
                       // half of the letters
    : S                // otherwise, stop and return S
)                      //
+ ''                   // coerce the output buffer back to a string

```

# Answer
> 3 votes
# JavaScript (ES6), 154 bytes

*-1 thanks to emanresu A, with their `v<{}` trick*

```
s=>(t=(f=x=>x?f(x.slice(1)).flatMap(y=>[x[0]+y,x[0].toUpperCase()+y]):[""])(s).filter(w=>![...w].reduce((u,v)=>u+(v<{})*2-1,0)))[Math.random()*t.length|0]

```

**Explanation:**

* `(f=x=>x?f(x.slice(1)).flatMap(y=>[x[0]+y,x[0].toUpperCase()+y]):[""])(s)`: Recursively finds all ways to capitalize the string
* `.filter(w=>![...w].reduce((u,v)=>u+(v<{})*2-1,0))`: Filters out items which don't have the correct number of capitalized letters, by checking if the sum of `-1` (for capitalized) and `1` (for lowercase) is `0`
* `[Math.random()*t.length|0]`: Choose a random item

# Answer
> 3 votes
# , 21 bytes

```
toupper@{~`]`[}-:@#?#

```

Try it online!

* `-:@#?#` Randomly "Deal" `?` half-the-length `-:@#` number of indices from all possible indices.
* `toupper@{~`\]`[}` And Amend `}` just those indices with their uppercased versions `toupper@{~`.

# Answer
> 3 votes
# Jelly, 8 bytes

```
JẊị"żŒu$

```

Try It Online!

-2 bytes thanks to a clever trick from Adnan using cyclical indexing, thus tying pxeger's answer

```
JẊị"żŒu$    Main Link
J           [1, 2, ..., len(input)]
 Ẋ          random permutation of that
  ị"        vectorize - index (half of them are even, half are odd, and it wraps)
    żŒu$    the input zipped with itself capitalized

```

# Answer
> 3 votes
# Factor \+ `sequences.repeating`, ~~43~~ 39 bytes

```
[ "\0 "over length cycle randomize v- ]

```

Try it online!

```
            ! "hamburgers"
"\0 "       ! "hamburgers" "\0 "
over        ! "hamburgers" "\0 " "hamburgers"
length      ! "hamburgers" "\0 " 10
cycle       ! "hamburgers" "\0 \0 \0 \0 \0 "
randomize   ! "hamburgers" "\0\0\0    \0 \0"
v-          ! "hamBURGeRs"

```

# Answer
> 3 votes
# C (clang), ~~58~~ 51 bytes

-1 thanks to AZTECCO
-6 with wide string and clang

```
i;f(*s,l){for(i=l/2;rand()%l--<i?s[l]^=32,--i:i;);}

```

Try it online!

Outputs by modifying the input string.

Each letter has a \\$\frac in\\$ chance of being capitalized, where \\$i\\$ is the number of remaining capital letters and \\$n\\$ is the number of remaining letters (including this one).

# Answer
> 3 votes
# Ruby, 59 bytes

```
->s{[*0...q=s.size].sample(q/2).map{|w|s[w]=s[w].upcase};s}

```

Try it online!

# Answer
> 3 votes
# Julia 1.0, 73 bytes

```
!s=(E=length(s);v=rand(E);prod(i->s[i]-32*(i∈sortperm(v)[1:E÷2]),1:E))

```

Try it online!

# Answer
> 3 votes
# Uiua, ~~12~~ 10 bytes

```
⍜▽⌵◿2⍏≡⋅⚂.

```

Try it

-2 thanks to chunes’s nice idea to use gap.

Explanation:

```
≡⋅⚂.

```

To each of the input’s rows, drop the item with gap and give a random value between 0 and 1.

rise gives the index of each number if you had sorted the list in ascending order.

```
◿2

```

Take each number modulus2.

```
⍜▽⌵

```

under keep basically takes a list of 1’s and 0’s and a list of the same length, and applies a function to every item in the second list corresponding with a 1 in the first. absolute value, if given a character, uppercases it.

# Answer
> 2 votes
# Retina, 81 bytes

```
/^((?<-2>[a-z])|(?<-3>[A-Z])|([A-Z])|([a-z]))*(?(2)^)(?(3)^)$/^+/./_?(T`l`L
T`L`l

```

Try it online! Explanation:

```
/^((?<-2>[a-z])|(?<-3>[A-Z])|([A-Z])|([a-z]))*(?(2)^)(?(3)^)$/

```

Check whether the input contains equal numbers of lower and upper case letters. Groups `2` and `3` contain any excess upper and lower case letters respectively; if they are non-empty then the letter of the opposite case decrements the group, otherwise the letter increments the group appropriately. At the end both groups are required to be empty.

```
^+

```

Repeat while it does not.

```
/./_

```

Loop over each letter.

```
?(

```

Random choice between one of the following.

```
T`l`L

```

Uppercase.

```
T`L`l

```

Lowercase.

# Answer
> 2 votes
# Python 2,127 119 bytes

Not super happy with this, I'll probably come back to it after class (or not, we'll see). Takes input from stdin using Python 2 `input()` rules - aka `"test"` rather than `test`.

Requires Python 2 for `range` returning a list, since that would require `*x,` instead of `x` otherwise, and would lose a byte on the print statement and I don't think you can gain more than 2 from inline variable assignments.

Using `chr`/`ord` is shorter than `[s[i],s[i].upper()][i in x[::2]]`, I think that's optimal as well.

Thanks to enzo for -8, from switching from using a while loop to just `str.join`.

```
from random import*
s=input()
n=len(s)
r=range(n)
x=sample(r,n)
print''.join(chr(ord(s[i])-32*(i in x[::2]))for i in r)

```

Try it online!

# Answer
> 2 votes
# Wolfram Language (Mathematica), 52 bytes

```
MapAt[Capitalize,#,RandomSample[i=0;{++i}&/@#,i/2]]&

```

Try it online!

-16 bytes thanks to @att

# Answer
> 2 votes
### In true Perl spirit, TMTOWTDI:

# Perl 5 `-MList::Util=shuffle -F`, 35 bytes

```
map$_=uc,(shuffle@F)[1..@F/2];say@F

```

Try it online!

# Perl 5 `-F`, 49 bytes

```
@k{0..$#F}=1;map$_=uc,@F[(keys%k)[1..@F/2]];say@F

```

Try it online!

# Answer
> 2 votes
# C#, 145 bytes

Hey! I'm completely new to this and my answer will make that apparent. I thought I'd post so that I can refer back to later to see my progress. Let me know if I anything is incorrect involving my answer.

didn't include logging, output is the t string

```
string t="";int p=0;while(p!=s.Length/2){t="";p=0;foreach(char c in s){char l=c;if(new Random().Next(2)==0){l=char.ToUpper(l);p++;}t=$"{t}{l}";}}

```

Try it online!

# Answer
> 2 votes
# ayr, 13 bytes

```
(];-){:2|#?.#

```

Try it!

# Explained

```
       #?.# Roll N-sided die N times, where N is len of y
     2|     Convert this to a length-N boolean vector (half 1s, half 0s)
   {:       Use this to catalogue..
];-         A matrix of the string and the string with inverted caps

```

# Answer
> 1 votes
# Vyxal, 9 bytes

```
ẏṖ℅Ih⁽N¨M

```

Try it Online!

Explanation:

```
ẏ         # List of [0..len(input))
 Ṗ℅       # Random permutation
   Ih     # First half of the list
     ⁽N¨M # Toggle case of the indexes in the list

```

There is actually a dedicated builtin for `Random Permutation`, which is faster, but there is a bug in it, so we have to get every permutation and choose a random one.

# Answer
> 1 votes
# Python 3, 105 bytes

```
lambda s:''.join([x,x.upper()][y%2]for x,y in zip(s,sample([*range(len(s))],len(s))))
from random import*

```

Try it online!

# Answer
> 1 votes
# Perl 5 `-pF`, 43 bytes

1 byte saved thanks to @Kjetil S!

```
$F[rand@F]&=_,$_=join"",@F
while@F/2>y;A-Z;

```

Try it online!

---

# Perl 5 \+ `-pa`, 38 bytes

-5 bytes using a space separates string (Thanks @Kjetil S!)

```
$F[rand@F]&=_,$_="@F"
while@F/2>y;A-Z;

```

Try it online!

# Answer
> 1 votes
# Excel, 89 bytes

```
=LET(x,LEN(A1),y,RANDARRAY(x),CONCAT(CHAR(CODE(MID(A1,SEQUENCE(x),1))-(y>MEDIAN(y))*32)))

```

This breaks the string into an array of characters. Then generates an array of random numbers of the same length. For each number in the random array that is greater that the median of the array, the corresponding letter is changed to upper case (ASCII value reduced by 32). Then all of the characters are concatenated.

# Answer
> 1 votes
# Raku, 41 bytes

```
{[~] {@_[pick @_/2,^@_]».=uc;@_}(.comb)}

```

Try it online!

* `.comb` splits the input string into a list of characters, which is then fed to the brace-delimited anonymous function, which takes the list in the `@_` array. This is just a short way to get an array with writeable elements without having to declare one explicitly.
* `pick @_ / 2, ^@_` randomly selects half of the indices in the character array.
* `@_[...]».=uc` slices into the array of characters with the random selection of indices, and uppercases the characters at those indices. The original array is then returned.
* `[~]` concatenates the characters into a single string.

# Answer
> 1 votes
# YASEPL, 100 bytes

```
=1'±""=a®1=b$a/=i`1=r¢1,a-=c¥r,1=u$32`2!t$u»}3,c,3!u+|2`3!u}2,91-32»!¤r,u!i+}2,b=i`4=c¥i,1~!i+}2,a,4

```

explanation:

```
=1'±""=a®1=b$a/=i`1=r¢1,a-=c¥r,1=u$32`2!t$u»}3,c,3!u+|2`3!u}2,91-32»!¤r,u!i+}2,b=i`4=c¥i,1~!i+}2,a,4             packed
=1'                                                                                get user input and set it to var1
   ±""                                                                                split it every character (to bypass a bug in the yasepl code)
      =a®1                                                                                A = length of var1
          =b$a/                                                                                B = length of var1 divided by 2
               =i                                                                                increment variable
                 `1                                                      !i }2,b                                 do while I < B...
                   =r¢1,a-=c¥r,1                                                                                C = character from var1 at random position
                                =u$32`2!t$u»}3,c,3!u+|2`3!u}2,91                                                 if C is uppercase then continue loop, do not increment. if not, continue
                                                                -32»!¤r,u                                        make character at the position lowercase in list
                                                                           +                                     increment I
                                                                                =i`4=c¥i,1~!i+}2,a,4             join list together once done and print it

```

# Answer
> 0 votes
# Charcoal, 20 bytes

```
Ｗ⁻⊗ＬΦＫＡ№ακＬθＰ⭆θ‽⁺κ↥κ

```

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

```
Ｗ⁻⊗ＬΦＫＡ№ακＬθ

```

Repeat until uppercase letters make up exactly half of the canvas...

```
Ｐ⭆θ‽⁺κ↥κ

```

... output the input string but randomly uppercase each letter.

# Answer
> 0 votes
# APL+WIN, 37 bytes

Prompts for string

```
s[i]←s[i←(.5×⍴s)?⍴s←⎕av⍳⎕]+48⋄⎕av[s]

```

Try it online!Thanks to Dyalog Classic

# Answer
> 0 votes
# Python 3, 124 bytes:

```
import random as r
j=range
f=lambda s:(lambda v:''.join(chr(ord(s[i])-32*(i in v))for i in j(l)))(r.sample(j(l:=len(s)),l//2))

```

# Answer
> 0 votes
`(new Array(s.length)).fill(0).map((i,j)=> j % 2).sort(() => Math.random() - 0.5).map((i, j) => (i ? s[j].toUpperCase() : s[j])).join("")`

# Answer
> 0 votes
# Ly, 44 bytes

```
irysp>l[0f1f,,]p<[>sprl0y?[,sprl]psp<l' *-o]

```

Try it online!

This one works by generating a list of `0 1` pairs on a list the size of the input string. Then for each input character it reverses the list of `0 1` pairs a random number of times, then pops the top off the resulting stack. That value is used to decide whether or not to capitalize the character before printing it out.

1. Prep the input strings

```
ir      - read input codepoints into the stack, reverse the stack
  ysp   - save the number of char, delete that from the stack
     >  - switch to an empty stack

```
2. Generate a list of `0 1` pairs

```
      l[0f1f,,]p
      l[    ,,]p  - loop "n/2" times adding "0,1" pairs to the stack
        0f        - add a "0" to the stack, pull the iterating var forward
          1f      - add a "1" to the stack and pull the iterator forward again

```
3. Process each of the input chars on the input stack

```
<[                         ] - loop until the input stack is empty
  *3.1*                      - get a random 0/1 from the boolean stack
                    <l       - back to input stack, load boolean 0/1 capitalization choice
                      ' *    - multiple " " by the boolean
                         -   - subtract to capitalize (of boolean was true)
                          o  - print the current input char

```

3.1 Pull a random boolean off the list

```
>                   - switch to the boolean stack
 sprl               - disrupt pattern on list, move top entry to the bottom
     0y?            - pick a random number between 0 and the stack size
        [,sp l]p    - loop that number of time, using backup cell for iterator val
            r       - reverse the stack
                sp  - save the random boolean to the backup cell

```

# Answer
> 0 votes
# MathGolf, 14 bytes

```
δ^hr¥áÅ;v^mÅ~§

```

I/O as a list of characters.

Try it online.

**Explanation:**

```
δ              # Capitalize each character in the (implicit) input-list
               #  e.g. ['a','b','c','d','e'] → ['A','B','C','D','E']
 ^             # Zip it with the (implicit) input-list
               #  → [['a','A'],['b','B'],['c','C'],['d','D'],['e','E']]
  h            # Push the length (without popping)
               #  → 5
   r           # Pop and push a list in the range [0,length)
               #  → [0,1,2,3,4]
    ¥          # Mod-2 on each
               #  → [0,1,0,1,0]
     á         # Sort it by,
      Å        # using the following 2 characters as inner code-block:
       ;       #  Discard the value
        v      #  Push a random integer in the range [-2147483648,2147483647]
               #  e.g. [0,1,0,0,1]
         ^     # Zip these shuffled 0s/1s with the earlier pair of characters
               #  → [[['a','A'],0],[['b','B'],1],[['c','C'],0],[['d','D'],0],[['e','E'],1]]
          m    # Map over each,
           Å   # using 2 characters as inner code-block again:
            ~  #  Dump the pair and integer separated to the stack
             § #  Index the integer into the pair
               #  → ['a','B','c','d','E']
               # (after which the entire stack is output implicitly as result)

```

# Answer
> 0 votes
# TI-Basic, 160 bytes

```
Input Str1
length(Str1
Ans/2≥randIntNoRep(1,Ans→S
"abcdefhijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ→Str2
".
For(I,1,dim(ʟS
Ans+sub(Str2,inString(Str2,sub(Str1,I,1))+26ʟS(I),1
End
sub(Ans,2,dim(ʟS

```

Output is stored in `Ans` and displayed. Only works on calculators that support `randIntNoRep(`.

# Answer
> 0 votes
# T-SQL, 142 bytes

```
SELECT top(len(@)/2)@=stuff(@,number+1,1,upper(substring(@,number+1,1)))FROM
spt_values WHERE number<len(@)and'P'=type
ORDER BY newid()PRINT @

```

**Try it online**

This will always give return the same result. In Microsoft SQL Server Management Studio, the result is randomized. The reason could be the explanation below by Fmbalbuena

# Answer
> 0 votes
# JavaScript (V8), ~~88~~ 86 bytes

```
f=s=>(r=s.replace(/./g,c=>Math.random()>.5?c:c.toUpperCase(a+=2),a=0)).length-a?f(s):r

```

Try it online!

This was my first submission on the site! I got my second Yearling badge today so I thought I'd come back and golf some of my earliest submissions.

Explanation:

```
f=s=>                     // function f taking string argument s
  (r=                     //   assign variable r to
    s.replace(/./g,c=>    //     s with each character c mapped to:
      Math.random()>.5    //       random true/false
        ?c                //       if true, leave c unchanged
        :c.toUpperCase(a+=2), //   else, uppercase c, and add 2 to a
      a=0                 //     a defaults to 0
    ))                    //   end assignment
  .length-a               //   (length of r) - a
    ?f(s)                 //   if nonzero, start over
    :r                    //   else, return r

```

# Answer
> 0 votes
# Clojure, 142 bytes

```
(defn r[s](let[l(count s)z(apply str(update(vec s)(rand-int l)clojure.string/upper-case))](if(<(count(re-seq #"[A-Z]" z))(/ l 2))(recur z)z)))

```

Un-golfed version:

```
(defn randomly-capitalize-half-of [s]
  (let [v  (vec s)                                 ; convert string s to a vector of characters - e.g. "abcd" becomes [\a \b \c \d]
        l  (count s)                               ; length of string s
        i  (rand-int l)                            ; choose a random index from 0 to (length of s)-1
        v2 (update v i clojure.string/upper-case)  ; convert character at index i in v to upper case
        s2 (apply str v2)                          ; collapse vector-of-characters to a single string
        c  (count (re-seq #"[A-Z]" s2)) ]          ; count number of upper-case letters in s2
    (if (< c (/ l 2))                              ; if count of upper-case letters < 1/2 of length of s
      (recur s2)                                   ;   then recursively invoke randomly-capitalize with partially-upcased string as input
      s2)))                                        ;   else return half-uppercased string

```

# Answer
> 0 votes
# x86\_64 machine code, 33 bytes

```
\x89\xf1\x0f\xc7\xf0\x73\xfb\x31\xd2\xf7\xf6\xf6\x04\x17
\x20\x74\xf1\x80\x24\x17\xdf\x83\xe9\x02\x75\xe8\xc3

```

Try it online!

It uses the hardware random generator `rdrand`, which is very slow BTW.

original assembly (nasm)

```
f: ; rdi = string, rsi = number of characters, SysV calling convention
    mov ecx, esi
.loop:
    rdrand eax
    jnc .loop
    xor edx, edx
    div esi
    test byte [rdi + rdx], 0x20
    jz .loop
    and byte [rdi + rdx], 0xdf
    sub ecx, 2
    jnz .loop
    ret

```

# Answer
> 0 votes
# Swift, 103 bytes

```
let f={zip($0+"",(0..<$0.count).shuffled().map{$0%2<1}).map{(x,y)in y ?x.uppercased():"\(x)"}.joined()}

```

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


# Question
Title: Select the word around the given index in a given string
In the most common contemporary graphical desktop interfaces, when you perform double-click in a text, the word around your cursor in the text will be selected.

For example, let `|` be your cursor in `abc de|f ghi`. Then, when you double click, the substring `def` will be selected.

## Input/Output

You receive two inputs:

* a string and
* an integer. Your task is to return the word‐substring of the string around the index specified by the integer.

Your cursor can be right *before* or right *after* the character in the string at the index specified. If you use right *before*, please specify in your answer.

## Specifications

* The index is *guaranteed* to be inside a word, so no edge cases like `abc |def ghi` or `abc def| ghi`.
* The string will *only* contain printable ASCII characters (from U+0020 to U+007E).
* The word `word` is defined by the regex `(?<!\w)\w+(?!\w)`, where `\w` is defined by `[abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_]`, or “alphanumeric characters in ASCII including underscore”.
* The index can be *either* 1‑based *or* 0‑based. If you use are 0‑based index, please specify it in your answer.

## Test cases

The cursor position visualization is for demonstration purpose only; it is not a required output. The cursor is indicated right *after* the index specified. Here, the `sample` string indices are 1‑based.

| sample | index | visualization | output |
| --- | --- | --- | --- |
| `abc def` | `2` | `ab|c def` | `abc` |
| `abc def` | `5` | `abc d|ef` | `def` |
| `abc abc` | `2` | `ab|c abc` | `abc` |
| `ab cd ef` | `4` | `ab c|d ef` | `cd` |
| `ab cd` | `6` | `ab c|d` | `cd` |
| `ab!cd` | `1` | `a|b!cd` | `ab` |

<sub>) This feature has more complicated properties, but they are not required to be implemented for this challenge.</sub>

# Answer
# , ~~10, 9~~ 7 bytes

```
À|diwVp

```

Try it online!

This answer uses 1-based indexing.

This could be shorter if we do exactly what the title says: "*Select* the word around the given index in a string". We could do

```
À|viw

```

Which literally selects the word, but unfortunately doesn't change the output at all. So we need a little workaround to make it work by cutting it into a register, deleting the rest of the text, then pasting the register back in.

Explanation:

```
À|          " Jump the position of argument 1
  diw       " (d)elete (i)nside this (w)ord.
     V      " Select this line
      p     " And replace it with the word we just deleted

```
> 9 votes

# Answer
# C, 104 bytes

```
p[99];i,d;main(l){for(scanf("%d",&i);scanf("%[^a-zA-Z0-9_]%[a-zA-Z0-9_]%n",&d,&p,&l),i>l;i-=l);puts(p);}

```

Expects the input on stdin to be the 0-based index followed by one space or newline, followed by the string. Maximal length for a word is 99 characters. E.g.:

```
2 abc def

```
> 5 votes

# Answer
# C (gcc), 94 bytes

```
f(n,p)char*p;{for(p+=n-1;isalnum(*p)|*p==95&&n--;--p);for(;isalnum(*++p)|*p==95;putchar(*p));}

```

Zero-indexed, defines a function taking the index, then the string.
> 4 votes

# Answer
## Retina, 22

```
(1)+¶(?<-1>.)*\b|\W.+

```

Try it online! or verify all test cases. The regular program takes the cursor position in unary followed by a newline and then the string. The test suite has additional code to run in per line mode, and uses a `\` as a delimiter, and it uses decimal, for convenience.

Uses balancing groups to find the cursor position, then backtracks up to a word boundary. Deletes the text up to the word, and then after the word.
> 3 votes

# Answer
# Python 2, ~~70~~ 66 bytes

```
import re
f=lambda x,y,r=re.split:r('\W',x[:y])[-1]+r('\W',x[y:])[0]

```

Splits the string by non-word separators, once on the original string up to the cursor index, then on the string beginning at the cursor index. Returns the last element of the left split plus the first element of the right split. Thanks to Leaky Nun for saving 4 bytes!
> 3 votes

# Answer
# Pyth, 16 bytes

```
+e=:.<+QbE"\W"3h

       Q            first input (string)
      + b           plus newline
    .<   E          rotate left by second input (number)
   :      "\W"3     split on regex \W, non-word characters
  =                 assign to Q
 e                  last element
+              hQ   plus first element

```

Try it online
> 3 votes

# Answer
# Ruby, ~~41~~ 31 bytes

Try it online!

*-10 bytes from @MartinEnder*

```
->s,i{s[/\w*(?<=^.{#{i}})\w*/]}

```
> 3 votes

# Answer
# JavaScript (V8), 44 bytes

```
(i,x)=>RegExp(`\\w*(?<=.{${i}})`).exec(x)[0]

```

Try it online!

This is longer than an existing JS solution, but I don't actually understand the approach it uses, and I wrote this prior to seeing that solution. Hopefully this is different enough to be interesting :P

Code explanation, so the same fate is not befallen upon ye

```
(i,x)=>                                 take i (number) and x (string)
       RegExp(`...${i}...`)             construct a regex with i in it
                           .exec(x)[0]  return the first result of that regex on the string

\w*(?<=.{i}) constructed regex
\w*          match an entire word
   (?<=    ) if the end of the word comes after
       .{i}  at least i characters

```
> 3 votes

# Answer
# C, 115 bytes

Function `f()` requires the string and index (1-indexed) as parameters and prints the result to stdout. Cursor should be after the specified character.

```
f(char*p,int n){char*s=p+n;for(;s>=p&&isalnum(*s)+(*s==95);--s);for(p=s+1;*p&&isalnum(*p)+(*p==95);putchar(*p++));}

```
> 2 votes

# Answer
## JavaScript (ES6), 57 bytes

```
f=(s,n)=>s.slice(0,n).match(/\w*$/)+s.slice(n).match(/\w*/)

```

Simply slices the string at the cursor point (which is before the 0-indexed character, which works out the same as after the 1-indexed character), then extracts and concatenates the adjacent word fragments. Even returns a sensible result when the cursor is at the start, end, or nowhere near a word.
> 2 votes

# Answer
## Pyke, 19 bytes

```
#Q;cjmli<i+s)lttjR@

```

Try it here!

Uses `Q;` as a no-op to make sure the first input is placed correctly

```
#          )   -  first where
   c           -       input.split()
    ml         -      map(len, ^)
      i<       -     ^[:i]
        i+     -    ^+[i]
          s    -   sum(^)
            lt - len(^)-2

```
> 2 votes

# Answer
# Java 8, ~~86~~ 78 bytes

```
(s,p)->{for(String t:s.split("\\W"))if((p-=t.length()+1)<0)return t;return"";}

```

Ungolfed with test cases:

```
class Indexer {
    public static String f(String s, int p) {
        for(String t : s.split("\\W"))
            if((p -= t.length()+1) < 0)
                return t;
        return "";
    }

    public static void main(String[] args) {
        System.out.println(f("abc def",2));
        System.out.println(f("abc def",5));
        System.out.println(f("abc abc",2));
        System.out.println(f("ab cd ef",4));
        System.out.println(f("ab   cd",6));
        System.out.println(f("ab!cd",1));
    }
}

```

Splits the string by non-alphanumeric characters, then keeps subtracting the length of each substring, plus 1, from the specified position, until it becomes negative. Since any repeating non-alphanumerics get represented as empty string, the subtraction logic is significantly easier.

This code isn't extensively tested, so I'd like to see if someone can break this. Also, considering that this is Java code, how is this not the longest answer here? :P
> 2 votes

# Answer
# Ruby, 30 bytes

```
->s,n{s[/.{#{n}}\w+/][/\w+$/]}

```

Try it online!

A different approach, only 1 byte shorter and 3 years later. Why not?
> 2 votes

# Answer
# Clojure, 92 bytes

```
(fn[x k](let[[u i](map #(re-seq #"\w+"(apply str %))(split-at k x))](str(last u)(nth i 0))))

```

First, splits input string at position `k` into two strings. Then for these strings find occurrences of `"\w+"` and return them as list. Then concatenate the last element of first list and the first element of second list.

See it online: https://ideone.com/Dk2FIs
> 1 votes

# Answer
# JavaScript (ES6), 52 bytes

```
(s,n)=>RegExp(`^.{0,${n}}(\\W+|^)(\\w+)`).exec(s)[2]

```

```
const F = (s,n) => RegExp(`^.{0,${n}}(\\W+|^)(\\w+)`).exec(s)[2]

class Test extends React.Component {
    constructor(props) {
        super(props);
        const input = props.input || '';
        const index = props.index || 0;
        this.state = {
            input,
            index,
            valid: /\w/.test(input),
        };
    }
    onInput = () => {
        const input = this.refs.input.value;
        const index = Math.min(+this.refs.index.value, input.length);
        this.setState({
            input,
            index,
            valid: /\w/.test(input),
        });
    }
    render() {
        const {input, index, valid} = this.state;
        return (
            <tr>
                <td>{ this.props.children }</td>
                <td>
                    <input ref="input" type="text" onInput={this.onInput} value={input} />
                    <input ref="index" type="number" onInput={this.onInput} min="1" max={input.length} value={index} />
                </td>
                {valid && [
                    <td>{F(input, index)}</td>,
                    <td><pre>{input.slice(0, index)}|{input.slice(index)}</pre></td>,
                ]}
            </tr>
        );
    }
}

class TestList extends React.Component {
    constructor(props) {
        super(props);
        this.tid = 0;
        this.state = {
            tests: (props.tests || []).map(test => Object.assign({
                key: this.tid++
            }, test)),
        };
    }
    addTest = () => {
        this.setState({
            tests: [...this.state.tests, { key: this.tid++ }],
        });
    }
    removeTest = key => {
        this.setState({
            tests: this.state.tests.filter(test => test.key !== key),
        });
    }

    render() {
        return (
            <div>
                <table>
                    <thead>
                        <th/>
                        <th>Test</th>
                        <th>Output</th>
                        <th>Diagram</th>
                    </thead>
                    <tbody>
                        {
                            this.state.tests.map(test => (
                                <Test key={test.key} input={test.input} index={test.index}>
                                    <button onClick={() => this.removeTest(test.key)} style={{
                                        verticalAlign: 'middle',
                                    }}>-</button>
                                </Test>
                            ))
                        }
                    </tbody>
                    <tfoot>
                        <td/>
                        <td>
                            <button onClick={this.addTest} style={{
                                width: '100%',
                            }}>Add test case</button>
                        </td>
                    </tfoot>
                </table>
            </div>
        );
    }
}

ReactDOM.render(<TestList tests={[
    { input: 'abc def', index: 2 },
    { input: 'abc def', index: 5 },
    { input: 'abc abc', index: 2 },
    { input: 'ab cd ef', index: 4 },
    { input: 'ab   cd', index: 6 },
    { input: 'ab!cd', index: 1 },
]} />, document.body);
```

```
input[type="number"] {
  width: 3em;
}
table {
  border-spacing: 0.5em 0;
  border-collapse: separate;
  margin: 0 -0.5em ;
}
td, input {
    font-family: monospace;
}
th {
  text-align: left;
}
tbody {
  padding: 1em 0;
}
pre {
  margin: 0;
}
```

```
<script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react.min.js"></script>
<script src="https://cdnjs.cloudflare.com/ajax/libs/react/15.1.0/react-dom.min.js"></script>
```
> 1 votes

# Answer
## Lua, ~~71~~ 67 Bytes

Woohoo, Lua isn't the longest solution! Still one byte behind python, but don't know how to golf this down. Indexes are 1-based.

**Thanks to @LeakyNun reminding me the existence of `string.match`, saved 4 bytes**

```
g,h=...print(g:sub(1,h):match"[%a_]*$"..g:sub(h+1):match("[%a_]+"))

```

### Old 71

**Note: the explanations are still based on this one, because it also applies to the new one, but contains some extra informations on `gmatch`**

```
g,h=...print(g:sub(1,h):gmatch"[%a_]*$"()..g:sub(h+1):gmatch"[%a_]*"())

```

### Explanation

First, we unpack the arguments into `g` and `h` because they are shorter than `arg[x]`

```
g,h=...

```

Then, we construct our output, which is the concatanation of the part before the cursor and after it.

The first part of the string is

```
g:sub(1,h)

```

We want to find the word at the end of this one, so we use the function `string.gmatch`

```
:gmatch"[%a_]*$"

```

This pattern match `0..n` times the character set of alphabet+underscore at the end of the string. `gmatch` returns an iterator on its list of match in the form of a function (using the principle of closure), so we execute it once to get the first part of our word

```
g:sub(1,h):gmatch"[%a_]*$"()

```

We get the second part of our word by the same way

```
g:sub(h+1):gmatch"[%a_]*"())

```

The only difference being we don't have to specify we want to match at the start of the string (using `[^%a_]*`), as it will be the match returned by the iterator when it's called the first time.
> 1 votes

# Answer
# JavaScript (ES 6), ~~43~~42 Bytes

```
s=>n=>s.replace(/\w*/g,(x,y)=>y<n?s=x:0)&&s

```

# JavaScript (ES 3), 65 Bytes

```
function(s,n){s.replace(/\w*/g,function(x,y){y<n?s=x:0});alert(s)}

```
> 1 votes

# Answer
# 05AB1E, 14 bytes

```
ð«._DžjмS¡Á2£J

```

Port of *@AndersKaseorg*'s Pyth answer.

1-indexed like the challenge test cases.

Try it online or verify all test cases.

**Explanation:**

```
ð«              # Append a space to the (implicit) input-String
  ._            # Rotate this string the (implicit) input-integer amount of times
                #  towards the left
     D          # Duplicate this string
      žjм       # Remove [a-zA-Z0-9_] from the string
         S¡     # Split the rotated string by each of the remaining characters
           Á    # Rotate the resulting list once towards the right
            2£J # And only leave the first two items, joined together
                # (which is output implicitly)

```
> 1 votes

# Answer
# Perl 6, 34 bytes

```
->\b{&{first *.to>b,m:g/<<\w+>>/}}

```

Try it online!

Anonymous codeblock that takes input curried, like `f(n)(string)`.

### Explanation:

```
->\b{                            }   # Anonymous code block that takes a number
     &{                         }    # And returns another code block that
       first       ,m:g/<<\w+>>/     # Finds the first word in the input
             *.to>b                  # Where the start is after the number

```
> 1 votes

# Answer
# APL(NARS), 58 chars, 116 bytes

```
{m←⎕A,⎕a,⎕D,'_'⋄↑v⊂⍨m∊⍨v←⍵↓⍨¯1+⍵{⍵≤1:⍵⋄m∊⍨⍵⊃⍺:⍺∇⍵-1⋄⍵+1}⍺}

```

⍵{⍵≤1:⍵⋄m∊⍨⍵⊃⍺:⍺∇⍵-1⋄⍵+1}⍺ find where start the string...How to use and test:

```
  f←{m←⎕A,⎕a,⎕D,'_'⋄↑v⊂⍨m∊⍨v←⍵↓⍨¯1+⍵{⍵≤1:⍵⋄m∊⍨⍵⊃⍺:⍺∇⍵-1⋄⍵+1}⍺}
  2 f 'abc def'
abc
  5 f 'abc def'
def
  2 f 'abc abc'
abc
  4 f 'ab cd ef'
cd
  1 f 'ab!cd'
ab
  6 f 'ab   cd'
cd

```
> 1 votes

# Answer
# Jelly, 12 bytes

```
Żṙe€ØW¬œpƊ.ị

```

Try it online!

Port of Anders Kaseorg's Pyth answer.

```
Ż               Prepend a zero as a buffer between the first and last words,
 ṙ              then rotate left by the index.
       œpƊ      Partition that result around
   €  ¬         elements which are not
  e ØW          word characters,
          .ị    then take the last and first slices
                and smash-print them together.

```

Original:

# Jelly, 14 bytes

```
xðe€ØW¬Ä÷Ɗ=ị@¥

```

Try it online!

```
  e€ØW            For each element, is it a word character?
       Ä          Take the cumulative sum
      ¬           of the negations
        ÷Ɗ        and divide by the original Booleans.
          =       For each value in the result, is it equal to
           ị@¥    the one at the index?
xð                Filter the string to truthy positions.

```
> 1 votes

# Answer
# MATL, ~~16~~ 15 bytes

```
'\w+'5B#XXi>)1)

```

Cursor is 1-indexed and after the character (as in the test cases).

Try it online! Or verify all test cases.

```
'\w+'    % Push string to be used as regex pattern
5B#XX    % Take input string implicitly. Apply regex. Push matches and ending indices
i>       % Take input number. Compare with obtained ending indices. Gives true for
         % ending indices that exceed the input number
)        % Use as logical index to select the corresponding matches
1)       % Select the first match. Implicitly display

```
> 0 votes

# Answer
## PowerShell v3+, ~~103~~ 101 bytes

```
param($a,$n)for(;$n[++$a]-match'\w'){}$i=$a--;for(;$n[--$a]-match'\w'-and$a-ge0){}-join$n[++$a..--$i]

```

Kind of a goofy solution, but a different approach than others.

Takes input `$a` as the 0-based index of the string `$n`. Then, we find the boundaries of our word. While we've not reached the end of the string and/or we're still matching word-characters, we `++$a`. Then, because of fenceposting, we set `$i=$a--`. Next, we crawl backwards, decrementing `$a` until it's either `0` or we hit a non-word-character. We then slice the input string based on those two demarcations (with some increment/decrements to account for OBOE), and `-join` it together to produce the result.

### Examples

```
PS C:\Tools\Scripts\golfing> .\select-the-word-around-the-index.ps1 2 'This!test'
This

PS C:\Tools\Scripts\golfing> .\select-the-word-around-the-index.ps1 5 'This!test'
test

```
> 0 votes

# Answer
# PHP, 98 bytes

```
function f($s,$p){foreach(preg_split('#\W+#',$s,-1,4)as$m)if($m[1]+strlen($m[0])>=$p)return$m[0];}

```
* splits the string by non-word-characters, remembering their position (`4` == `PREG_SPLIT_OFFSET_CAPTURE`), loops through the words until position is reached.
* PHP strings are 0-indexed, cursor before character, but may be before or after the word
> 0 votes

# Answer
## Python 3, ~~112~~ 140 bytes

```
from string import*
p='_'+printable[:62]
def f(s,h,r=''):
 while s[h]in p and h>-1:h-=1
 while h+1<len(s)and s[h]in p:h+=1;r+=s[h]
 return r

```

0-indexed.

Seeks backward to the first alphanumeric character from the index, then goes forward to the last alphanumeric character after the index. There's probably a smarter way to do this.

Try it
> 0 votes

# Answer
## Javascript (using external library) (168 bytes)

```
(n,w)=> _.From(w).Select((x,i)=>({i:i,x:x})).Split((i,v)=>v.x==" ").Where(a=>a.Min(i=>i.i)<=n-1&&a.Max(i=>i.i)>=n-2).First().Select(i=>i.x).Write("").match(/^\w*^\w*/)[0]

```

Link to lib:https://github.com/mvegh1/Enumerable/blob/master/linq.js

Explanation of code: Library accepts a string, which gets parsed into a char array. It gets mapped to an object storing the index and the char. The sequence is split into subsequences at every occurrence of " ". The subsequences are filtered by checking if the cursor index is contained within the min and max index of the subsequence. Then we take the first subsequence. Then we transform back to just a char array. Then we concatenate all characters with "" as the delimiter. Then we validate against word regex. Then we take the first match.
> 0 votes

# Answer
# Perl 5 `-p`, 35 bytes

```
$b=<>;($_)=/.{$b}\w+/g;($_)=/\w+$/g

```

Try it online!
> 0 votes

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