# Question
Title: Unscramble those case-(very)-sensitive strings
## Goal

This is a simple challenge. Your goal is to unscramble a string by swapping each letter with the next letter of the same case, while leaving non-letter characters unchanged.

## Step by step explanation

1. The first character is a `E`. We look for the next letter in upper case: it's a `C`. We swap these characters, which leads to `CdoE!`.
2. We advance to the next character: this is a `d`. We look for the next letter in lower case: it's a `o`. We swap these characters, which leads to `CodE!`.
3. We advance to the next character: this is the `d` that we've just moved here. We ignore it, because it has already been processed.
4. We advance to the next character: this is the `E` that was moved here at step #1. We ignore it, because it has already been processed.
5. We advance to the next character: this is a `!`. We ignore it, because it's not a letter.

## Rules

* You can assume that the input string is made exclusively of printable ASCII characters, in the range 32 - 126.
* You may write either a full program or a function, which either prints or returns the result.
* If the input string contains an odd number of letters, the last remaining letter can't be swapped with another one and should remain in place, no matter its case. The same logic applies if the string contains an even number of letters, but an odd number of uppercase letters and an odd number of lowercase letters.
* This is code-golf, so the shortest answer in bytes wins. Standard loopholes are forbidden.

## Test cases

```
Input : lLEhW OroLd!
Output: hELlO WorLd!

Input : rpGOZmaimgn uplRzse naC DEoO LdGf
Output: prOGRamming puzZles anD COdE GoLf

Input : eIt uqHKC RBWOO xNf ujPMO SzRE HTL EOvd yAg
Output: tHe quICK BROWN fOx juMPS OvER THE LAzy dOg

Input : NraWgCi: Nsas-eNEiTIsev rNsiTG!!
Output: WarNiNg: Case-sENsITive sTriNG!!

```

Not-so-random test cases:

```
Input : (^_^)
Output: (^_^)

Input : AWCTY HUOS RETP
Output: WATCH YOUR STEP

Input : hwn oeesd acsp nawyya
Output: who needs caps anyway

Input : SpMycaeIesKyBorekn
Output: MySpaceKeyIsBroken

Input : D's mroyr, Ivam. I'e faardi I act'n od htta.
Output: I'm sorry, Dave. I'm afraid I can't do that.

```

# Answer
> 6 votes
# Jelly, ~~21~~ ~~20~~ ~~19~~ 18 bytes

```
s2UF,
nŒlTÇyJịŒsµ⁺

```

Try it online!

### How it works

```
nŒlTÇyJịŒsµ⁺  Main link. Argument: s (string)

 Œl           Convert to lowercase.
n             Test for inequality.
   T          Truth; yield all indices of 1's.
    Ç         Call the helper link. Yields [A, B] (pair of lists).
      J       Indices; yield I := [1, ..., len(s)].
     y        Translate; replace the integers of I that occur in A with the
              corresponding integers in B.
        Œs    Swapcase; yield s with swapped case.
       ị      Use the translated index list to index into s with swapped case.
          µ   Combine all links to the left into a chain.
           ⁺   Duplicate the chain, executing it twice.

s2UF,         Helper link. Argument: J (list of indices)

s2            Split J into pairs. If the length is odd, the last list will be
              a singleton list.
  U           Upend; reverse each pair. This is a no-op for singletons lists.
   F          Flatten, concatenating the pairs.
    ,          Pair the previous result with J.

```

# Answer
> 18 votes
# Retina, 53 bytes

Not really clever, but a clean and quite readable solution

```
([a-z])(.*?)([a-z])
$3$2$1
([A-Z])(.*?)([A-Z])
$3$2$1

```

Try it online!

# Answer
> 10 votes
# MATL, 22 bytes

```
2:"tttk<f2etAZ))P5M(Yo

```

Try it online! Or verify all test cases.

### How it works

```
2:"       % Do the following twice
  ttt     %   Input string (implicit). Push three more copies
  k       %   Convert to lowercase
  <f      %   Indices of characters that had their code point increased by
          %   the lowercase conversion, i.e. that were uppercase letters
  2e      %   Convert to 2-row matrix. This pads a zero in the lower-right
          %   corner if necessary
  tAZ)    %   Keep only columns that don't contain zeros. Thus if there
          %   was a character that can't be swapped it will be ignored
  )       %   Get 2-row matrix of characters at those positions
  P       %   Flip vertically. This does the swapping
  5M      %   Push matrix of original indices again
  (       %   Write the swapped characters onto their original positions
  Yo      %   Change case. In the first iteration, this prepares the
          %   string so the second iteration will process the letters that
          %   were originally lowercase. In the second iteration, it
          %   undoes the change of case
          % End (implicit)
          % Display (implicit)

```

# Answer
> 6 votes
## ES6, ~~185~~ 95 bytes

```
i=>(o=[...i]).map((c,j)=>/[a-z]/i.test(c)?o[e=c>"Z"]=1/(b=o[e])?o[o[j]=o[b],b]=c:j:0)&&o.join``

```

Solution severely shortened with the help of @Neil, @Arnauld and @edc65

Explanation

```
f = i =>
  // Get array of characters from input string
  (o = [...i])
    .map((c, j) =>
      // Check if it's a text character, otherwise skip it
      /[a-z]/i.test(c) ?
        // Get last character position for case
        // merged with setting a variable for if the character is lowercase
        // merged with storing the current case character position,
        // under properties on the array (with keys "true" or "false")
        o[e = c>"Z"] =
          // Check if there exists a character position to switch with
          // merged with storing the current position for quick access
          1/(b=o[e]) ?
            // This statement will end up returning the Array subset,
            // which will be falsy in the above conditional since (1/[])==false
            o[
              // Switch left character to the right
              o[j]=o[b]
            // Switch right character to the left
            ,b]=c :
            // No character exists for case, so return current character position
            j
         // It was not a text character, so do nothing
         :0
      )
  // Join array and return as result
  && o.join``;

`lLEhW OroLd!
NraWgCi: Nsas-eNEiTIsev rNsiTG!!
rpGOZmaimgn uplRzse naC DEoO LdGf
eIt uqHKC RBWOO xNf ujPMO SzRE HTL EOvd yAg
(^_^)
AWCTY HUOS RETP
hwn oeesd acsp nawyya
SpMycaeIesKyBorekn
D's mroyr, Ivam. I'e faardi I act'n od htta`
  .split`\n`
  .map(testCase => console.log(f(testCase)));
```

# Answer
> 6 votes
# Bash + Unix utilities, ~~77~~ ~~62~~ ~~57~~ ~~56~~ 54 bytes

```
sed -r "s/([$1)([^$1*)([$1)/\3\2\1/g"||$0 a-z]|$0 A-Z]

```

Input in stdin. Output in stdout.

(In this last version, stderr happens to be written to also, but PPCG consensus seems to be that that's OK -- stderr is simply ignored.)

Edit 1: Thanks to @Dennis for 15 bytes! Improvements: (a) Taking input via stdin; (b) combining 2 sed scripts into one; and (c) replacing tr with substitution via bash parameter expansion; (b) and (c) disappeared in Edit 2.

Edit 2: Shorter by 5 additional bytes. Used a function call to replace both (b) and (c) in Edit 1.

Edit 3: One more byte -- passed \] as part of the function arguments.

Edit 4: Replaced the two function calls with calls to the program itself when it has no arguments.

Testbed and sample output:

```
for x in 'lLEhW OroLd!' 'rpGOZmaimgn uplRzse naC DEoO LdGf' 'eIt uqHKC RBWOO xNf ujPMO SzRE HTL EOvd yAg' 'NraWgCi: Nsas-eNEiTIsev rNsiTG!!' '(^_^)' 'AWCTY HUOS RETP' 'hwn oeesd acsp nawyya' 'SpMycaeIesKyBorekn' "D's mroyr, Ivam. I'e faardi I act'n od htta."; do ./swapping <<<"$x" 2>/dev/null; done

hELlO WorLd!
prOGRamming puzZles anD COdE GoLf
tHe quICK BROWN fOx juMPS OvER THE LAzy dOg
WarNiNg: Case-sENsITive sTriNG!!
(^_^)
WATCH YOUR STEP
who needs caps anyway
MySpaceKeyIsBroken
I'm sorry, Dave. I'm afraid I can't do that.

```

# Answer
> 3 votes
# Python, 82 bytes

```
lambda s:S(r.lower(),t,S(r,t,s))
import re
S=re.sub
r='([A-Z])(.*?)'*2
t=r'\3\2\1'

```

Try it online!

# Answer
> 3 votes
# QBasic, 229 bytes

```
LINE INPUT s$
FOR i=1TO LEN(s$)
c$=MID$(s$,i,1)
IF"@"<c$AND"[">c$THEN
IF u THEN MID$(s$,u,1)=c$:MID$(s$,i,1)=u$
u=-i*(u=0)
u$=c$
ELSEIF"`"<c$AND"{">c$THEN
IF l THEN MID$(s$,l,1)=c$:MID$(s$,i,1)=l$
l=-i*(l=0)
l$=c$
END IF
NEXT
?s$

```

### Strategy

We loop through the input string. When we encounter an uppercase letter, we store it and its position. The second time we encounter an uppercase letter, we use those stored values to swap it with the previous one. Same for lowercase.

(I was about to post a rather longer version that used an array, because I thought that QBasic strings were immutable. Then I stumbled across the fact that `MID$(strng$, index, length) = replacement$` works just fine. Live and learn.)

### Ungolfed + commented

```
LINE INPUT text$

FOR i = 1 TO LEN(text$)
  char$ = MID$(text$, i, 1)
  IF "A" <= char$ AND "Z" >= char$ THEN
    ' Uppercase
    IF upperIndex = 0 THEN
      ' This is the first of a pair of uppercase letters
      ' Store the letter and its index for later
      upperLetter$ = char$
      upperIndex = i
    ELSE
      ' This is the second of a pair of uppercase letters
      ' Put it at the position of the previous uppercase letter
      ' and put that letter at this letter's position
      MID$(text$, upperIndex, 1) = char$
      MID$(text$, i, 1) = upperLetter$
      upperIndex = 0
    END IF
  ELSEIF "a" <= char$ AND "z" >= char$ THEN
    ' Lowercase
    IF lowerIndex = 0 THEN
      ' This is the first of a pair of lowercase letters
      ' Store the letter and its index for later
      lowerLetter$ = char$
      lowerIndex = i
    ELSE
      ' This is the second of a pair of lowercase letters
      ' Put it at the position of the previous lowercase letter
      ' and put that letter at this letter's position
      MID$(text$, lowerIndex, 1) = char$
      MID$(text$, i, 1) = lowerLetter$
      lowerIndex = 0
    END IF
  END IF
NEXT i

PRINT text$

```

# Answer
> 2 votes
## C++11 (GCC), ~~154~~ 149 bytes

```
#include<algorithm>
[](std::string s){int*p,u,l=u=-1;for(auto&c:s)(c|32)-97<26U?p=&(c&32?u:l),~*p?(std::swap(c,s[*p]),*p=-1):*p=&c-&s[0]:0;return s;}

```

# Answer
> 2 votes
# PHP, ~~108~~ ~~93~~ 83 bytes

```
<?=preg_replace([$a="/([a-z])([^a-z]*)([a-z])/",strtoupper($a)],"$3$2$1",$argv[1]);

```

---

### Previous version (93 bytes)

```
<?=preg_replace(["/([a-z])([^a-z]*)([a-z])/","/([A-Z])([^A-Z]*)([A-Z])/"],"$3$2$1",$argv[1]);

```

Thanks to @user59178 for reminding me that `preg_replace()` can take arrays of strings as arguments.

---

### The original answer (108 bytes)

```
$f=preg_replace;echo$f("/([a-z])([^a-z]*)([a-z])/",$r="$3$2$1",
$f("/([A-Z])([^A-Z]*)([A-Z])/",$r,$argv[1]));

```

The code is wrapped here to fit the available space.
It can be executed from the command line:

```
$ php -d error_reporting=0 -r '$f=preg_replace;echo$f("/([a-z])([^a-z]*)([a-z])/",$r="$3$2$1",$f("/([A-Z])([^A-Z]*)([A-Z])/",$r,$argv[1]));' 'lLEhW OroLd!'

```

A 1-byte shorter version is possible on PHP 7 by squeezing the assignment of `$f` inside its first call:

```
echo($f=preg_replace)("/([a-z])([^a-z]*)([a-z])/",$r="$3$2$1",
$f("/([A-Z])([^A-Z]*)([A-Z])/",$r,$argv[1]));

```

---

Both solutions, with test cases and ungolfed versions can be found on Github.

# Answer
> 2 votes
## Qbasic, ~~436~~ 408 bytes

```
LINE INPUT a$:b=len(a$):FOR a=1TO b:t$=MID$(a$,a,1)
IF"@"<t$AND"[">t$THEN
b$=b$+"U":u$=u$+t$
ELSEIF"`"<t$AND"{">t$THEN
b$=b$+"L":l$=l$+t$
ELSE b$=b$+t$
END IF:NEXT
FOR x=1TO b STEP 2:g$=g$+MID$(u$,x+1,1)+MID$(u$,x,1):h$=h$+MID$(l$,x+1,1)+MID$(l$,x,1):NEXT
FOR x=1TO b:t$=MID$(b$,x,1)
IF"U"=t$THEN
u=u+1:z$=z$+MID$(g$,u,1)
ELSEIF"L"=t$THEN l=l+1:z$=z$+MID$(h$,l,1)
ELSE z$=z$+t$
END IF:NEXT:?z$

```

*Saved one byte thanks to DLosc. Saved several more by changing handling of non-letter chars.*

This basically consists of three parts:

* Splitting the input into 3 strings (Uppercase, Lowercase, and a map (also holding the other chars))
* Flipping the uppercase and lowercase letters
* Using the map to (re)construct the output.

A more detailed explanation (note that this is of an earlier version of the code, but the principle still applies):

```
' --- Part I: Reading the input
LINE INPUT a$
'This FOR loop takes one character at a time
b=len(a$):FOR a=1TO b
' And checks in what category the character belongs
t$=MID$(a$,a,1):SELECT CASE t$
' For each group, char t$ is added to that group (u$ for uppercase,
' l$ for lowercase. The map in b$ is updated with a U or L on this index,
' or with the non-letter char t$.
CASE"A"TO"Z":b$=b$+"U":u$=u$+t$
CASE"a"TO"z":b$=b$+"L":l$=l$+t$
CASE ELSE:b$=b$+t$
END SELECT:NEXT

' --- Part II: Swapping within case-groups
' Loop through u$ and l$ twp chars at a time, and add those chunks in reverse order
' to g$ and h$. Because mid$ doesn't fail past the end of a string (but returns ""),
' this automatically compensates for odd-length groups.
FOR x=1TO b STEP 2:g$=g$+MID$(u$,x+1,1)+MID$(u$,x,1):h$=h$+MID$(l$,x+1,1)+MID$(l$,x,1):NEXT

' --- Part III: Read the map to put it all back together
FOR x=1TO b:t$=MID$(b$,x,1)
' See what group was in this spot, then read the next char from the flipped string.
' This keeps an index on those strings for the next lookup.
IF t$="U"THEN
u=u+1:z$=z$+MID$(g$,u,1)
ELSEIF t$="L"THEN l=l+1:z$=z$+MID$(h$,l,1)
' The map contains a non-letter char, just drop that in
ELSE z$=z$+t$
' And finally,display the end result.
END IF:NEXT:?z$

```

# Answer
> 2 votes
# Perl 5, 48 + 1 (-p) = 49 bytes

```
for$p(qw/([a-z]) ([A-Z])/){s/$p(.*?)$p/$3$2$1/g}

```

Try it online!

# Answer
> 1 votes
# Mathematica, 96 bytes

```
s[#,r="([a-z])(.*?)([a-z])"]~(s=StringReplace[#,RegularExpression@#2->"$3$2$1"]&)~ToUpperCase@r&

```

A port of Leo's Retina answer, which uses regular expressions.

# Answer
> 1 votes
# Python 2, 124 bytes

```
s=input();u=str.isupper
exec"r='';i=0\nfor c in s:r+=c[u(c):]or filter(u,s+s[::-1])[i^1];i+=u(c)\ns=r.swapcase();"*2
print s

```

Not as short as my regex-based solution, but I think it's still interesting.

Try it online!

# Answer
> 1 votes
## Python 2, 181 bytes

Much longer than it should be but anyway:

```
def F(s):
 for l in[i for i,c in enumerate(s)if c.isupper()],[i for i,c in enumerate(s)if c.islower()]:
  for a,b in zip(l[0::2],l[1::2]):s=s[:a]+s[b]+s[a+1:b]+s[a]+s[b+1:]
 print s

```

This first creates two lists: one of the indices of the uppercase characters and one for the lowercase characters. Each of these lists is looped through in pairs of indices, and the characters at those indices are switched.

I'll golf this down tomorrow, but for now it's time to sleep.

# Answer
> 1 votes
# Bean, 83 bytes

Hexdump:

```
00000000 26 53 d0 80 d3 d0 80 a0 5d 20 80 0a a1 81 81 00  &SÐ.ÓÐ. ] ..¡...
00000010 23 81 01 20 80 0a a1 81 81 02 23 81 01 a8 db c1  #.. ..¡...#..¨ÛÁ
00000020 ad da dd a9 a8 db de c1 ad da dd aa bf a9 a8 db  .ÚÝ©¨ÛÞÁ.ÚÝª¿©¨Û
00000030 c1 ad da dd 29 a4 b3 a4 b2 a4 31 a8 db e1 ad fa  Á.ÚÝ)¤³¤²¤1¨Ûá.ú
00000040 dd a9 a8 db de e1 ad fa dd aa bf a9 a8 db e1 ad  Ý©¨ÛÞá.úÝª¿©¨Ûá.
00000050 fa dd 29                                         úÝ)
00000053

```

Equivalent JavaScript:

```
a.replace(/([A-Z])([^A-Z]*?)([A-Z])/g,'$3$2$1').replace(/([a-z])([^a-z]*?)([a-z])/g,'$3$2$1')

```

Explanation:

Implicitly taking the first line of input unformatted as `a` (since newlines can't be part of scrambled string), and implicitly outputs unscrambled string by sequentially replacing uppercase, then lowercase pairs.

### Try demo here.

### Try test suite here.

# Answer
> 1 votes
# Ruby, 81 bytes

```
puts f=->(i,s){i.gsub /([#{s})([^#{s}*)([#{s})/,'\3\2\1'}[f[$*[0],'a-z]'],'A-Z]']

```

# Answer
> 1 votes
## JavaScript (ES6), 80 bytes

Based on **Leo's Retina answer**.

```
s=>eval("s"+(r=".replace(/([A-Z])([^A-Z]*)([A-Z])/g,'$3$2$1')")+r.toLowerCase())

```

This works because the only uppercase characters in the code `.replace(/([A-Z])([^A-Z]*)([A-Z])/g,'$3$2$1')` are `A` and `Z`, which are used to describe the character ranges. This is precisely what we need to transform into lowercase in order to process the second pass.

### Test cases

```
let f =

s=>eval("s"+(r=".replace(/([A-Z])([^A-Z]*)([A-Z])/g,'$3$2$1')")+r.toLowerCase())

console.log(f("lLEhW OroLd!"));
console.log(f("rpGOZmaimgn uplRzse naC DEoO LdGf"));
console.log(f("eIt uqHKC RBWOO xNf ujPMO SzRE HTL EOvd yAg"));
console.log(f("NraWgCi: Nsas-eNEiTIsev rNsiTG!!"));
console.log(f("(^_^)"));
console.log(f("AWCTY HUOS RETP"));
console.log(f("hwn oeesd acsp nawyya"));
console.log(f("SpMycaeIesKyBorekn"));
console.log(f("D's mroyr, Ivam. I'e faardi I act'n od htta."));
```

# Answer
> 1 votes
# ES6 155 - 195 bytes

I know there's already a better answer, but I wanted to try without regex. This one works on punctuation too, but that seems to violate the `(^_^)` test. In that case I have another `c()` function, given below.

```
f=(s)=>{d={};s=[...s];for(i in s){b=s[i];for(j in s)if(i<j&!d[i]&c(s[j])==c(b)){d[j]=1;s[i]=s[j];s[j]=b;break}}return s.join('')}
c=c=>~(c.charCodeAt()/32)

f("M I'o DaG") //> I'M a GoD
f("(^_^)")     //> )_^^(

c=c=>((c!=c.toUpperCase())<<1|c!=c.toLowerCase())||c.charCodeAt()

f("M I'o DaG") //> I'M a GoD
f("(^_^)")     //> (^_^)

```

### Explanation

```
f=(s)=>{
    d={};        //list of indexes already swapped
    s=[...s];        //string to array, stolen from above ES6 answer
    for(i in s){
        b=s[i];        //keep a note of what we are swapping
        for(j in s)        //iterate over the array again
            if( i<j & !d[i] & c(s[j])==c(b) ){
                        //only pay attention after we pass i'th
                        //only swap if this char hasn't been swapped
                        //only swap if both chars in same 'category'
                d[j]=1;        //note that the latter char has been swapped
                s[i]=s[j];
                s[j]=b;
                break        //avoid swapping on the same 'i' twice
            }
    }
    return s.join('')        //return as string
}

```

# Answer
> 1 votes
# Perl 6, 56 bytes

```
{for "A".."Z","a".."z" ->@c {s:g/(@c)(.*?)(@c)/$2$1$0/}}

```

Takes a string variable as an argument, and modifies it in-place so that after calling the lambda the variable contains the result.

Longer than it would be in Perl, because:

* The new regex syntax is more verbose, e.g. writing out the character classes would look like `<[A..Z]>` instead of `[A-Z]`.
* Regexes are first-class source code parsed at compile time, and a string can only be interpolated into them at run-time if it consists of a self-contained subregex (i.e. you can't interpolate a string into a character class).
* Explict `EVAL`, which would allow more flexibility, requires the golf-unfriendly `use MONKEY-SEE-NO-EVAL;` pragma.

On the plus side, an array in a `@` variable can be referenced directly in a regex, and is treated as an alternation.

---

# Perl 6, 65 bytes

```
{reduce ->$_,@c {S:g/(@c)(.*?)(@c)/$2$1$0/},$_,"A".."Z","a".."z"}

```

Functional version (outputs the result as the return value of the lambda).

# Answer
> 1 votes
# R, 343 Bytes

Terribly clumsy R solution:

```
f <- function(x) {
        y=unlist(strsplit(x,""))
        z=data.frame(l=ifelse(y %in% letters,0,ifelse(y %in% LETTERS,1,2)),s=y)
        l <- list(which(z$l==0),which(z$l==1))
        v <- unlist(l)
        for(j in 1:2) for (i in seq(1,ifelse(length(l[[j]])%%2==1,length(l[[j]])-2,length(l[[j]])-1),2)) l[[j]][i:(i+1)] <- rev(l[[j]][i:(i+1)])
        z[v,] <- z[unlist(l),]
        return(z$s)
    }

f("D's mroyr, Ivam. I'e faardi I act'n od htta.")

# [1] I ' m   s o r r y ,   D a v e .   I ' m   a f r a i d   I   c a n ' t   d o   t h a t .

```

# Answer
> 1 votes
# AWK, ~~121~~ 129 bytes

```
BEGIN{FS=OFS=""}{for(a=1;a<=NF;a++){if($a~/[A-Z]/?U>0?p=U+(U=0):0*(U=a):$a~/[a-z]/?L>0?p=L+(L=0):0*(L=a):0>0){t=$a;$a=$p;$p=t}}}1

```

Try it online! Note: Link has 8 extra bytes to allow multiline input

Usage is fairly typical, but does require a version of `AWK` that accepts an empty string as the field separator (most versions of `gawk` but I'm pretty sure the original `AWK` would fail :( )

It's very straightforward as it simply iterates over each character and checks if it's found one of that case before. If so, it swaps the characters and resets the checked index. On the learning side of things, I'd never used an assignment statement within an assignment statement in `AWK` before. For some reason it had never come up. :)

I might be able to shave a couple of bytes by saying to assign OFS and FS outside a `BEGIN` block via command-line assignment or similar, but it's "cleaner" this way.

*Adding the TIO link showed me that I had a transcription error that required 8 bytes to fix :( (I left out `0*(U=a):`)*

# Answer
> 1 votes
# Pip, 28 bytes

```
Y[XLXU]aRy.`.*?`.y{Sa@0a@va}

```

Takes input as a command-line argument. Try it online!

### Explanation

This is a regex solution, using the builtin regex variables `XL` (lowercase letters, ``[a-z]``) and `XU` (uppercase letters, ``[A-Z]``).

```
                              a is 1st cmdline arg; v is -1 (implicit)
Y[XLXU]                       Yank a list containing XL and XU into y
         y.`.*?`.y            Concatenate y, `.*?`, and y itemwise, giving this list:
                              [`[a-z].*?[a-z]`; `[A-Z].*?[A-Z]`]
       aR                     In a, replace matches of each regex in that list...
                  {        }  ... using this callback function:
                   Sa@0a@v     Swap the 0th and -1st characters of the match
                          a    and return the resulting string
                              Print (implicit)

```

When the second argument to `R` is a list, the replacements are performed in series; thus, the lowercase replacement and the uppercase replacement don't interfere with each other.

# Answer
> 1 votes
# C (gcc), ~~212~~ ~~206~~ ~~205~~ 203 bytes

* Thanks to ceilingcat for golfing ~~six~~ ~~seven~~ nine bytes.

```
#define I(a,b)if(S[j=i]/a&b/S[i]){for(;S[++j]<a|S[j]>b;);j<l?s[i]=S[j],s[j]=S[i]:0;}
i,j,l;f(char*S){char*s=calloc(l=-~strlen(S),1);for(i=~0;++i<strlen(S);)if(!s[i]){s[i]=S[i];I(65,90)I(97,'z')}puts(s);}

```

Try it online!

# Answer
> 1 votes
# Stax, 18 bytes

```
âß:}\]ó☺æ■jφ╛jz/Φi

```

Run and debug it

The general approach is regex-based.

* Two times do:
* Find all matches for `[a-z].*?[a-z]`.
* Swap the first and last character in matches.
* Invert case.

# Answer
> 1 votes
# , ~~223~~ ~~163 bytes~~ 148 bytes

EDIT: -60 bytes by implementing a for loop

EDIT: -15 bytes from Giuseppe

```
u=utf8ToInt(scan(,''));for(i in c(65,97)){l=which(u%in%i:(i+25));x=sum(l|1)%/%2;u[l[1:(x*2)]]=u[c(matrix(l,2)[2:1,1:x])]};cat(intToUtf8(u,T),sep="")

```

Try it online!

Works by testing if character is a lowercase or uppercase, places them in a matrix, inverts the matrix to extract the values in a swapped format. Then output with `cat`. Try it online struggles with `scan(,'')` if the code is more than one line, hence the semicolons throughout the single line of code.

# Answer
> 1 votes
# 05AB1E, ~~26~~ 23 bytes

```
2FÐlø€Ë≠āsƶ0KD2ôí˜‡<è.š

```

I/O as a list of characters.

Try it online or verify all test cases.

**Explanation:**

```
2F                # Loop 2 times:
  Ð               #  Triplicate the current character-list
                  #  (which will use the implicit input-list in the first iteration)
   l              #  Lowercase all letters of the top copy
    ø             #  Zip/transpose the top two lists; pairing them together, and swapping
                  #  rows/columns
     €Ë≠          #  Check for each pair whether they're NOT the same
                  #  (so uppercase characters that have now become lowercase)
  ā               #  Push a list in the range [1, length] (without popping)
   s              #  Swap so the mapped list is at the top again
    ƶ             #  Multiply each 1/0 by its 1-based index
     0K           #  Remove all 0s
       D          #  Duplicate this list of 1-based indices
        2ô        #  Split it into parts of size 2
          í       #  Reverse each part
           ˜      #  Flatten the list of swapped indices
            ‡     #  Transliterate the indices with the swapped indices in [1, length]
             <    #  Decrease each by 1 (because 05AB1E uses 0-based indexing)
              è   #  Index them into the current character-list
               .š #  And swap all cases (lowercase to uppercase, and vice-versa)
                  # (after the loop, the resulting character-list is output implicitly)

```

# Answer
> 0 votes
# Java 7, 117 bytes

```
String c(String s){String x="([a-z])(.*?)([a-z])",y="$3$2$1";return s.replaceAll(x,y).replaceAll(x.toUpperCase(),y);}

```

EDIT: Just noticed I have a similar answer as *@Leo*'s Retina answer, even though I've thought about it independently..

**Ungolfed:**

```
String c(final String s) {
  String x = "([a-z])(.*?)([a-z])",
         y = "$3$2$1";
  return s.replaceAll(x, y).replaceAll(x.toUpperCase(), y);
}

```

**Test code:**

Try it here.

```
class M{
  static String c(String s){String x="([a-z])(.*?)([a-z])",y="$3$2$1";return s.replaceAll(x,y).replaceAll(x.toUpperCase(),y);}

  public static void main(String[] a){
    System.out.println(c("lLEhW OroLd!"));
    System.out.println(c("rpGOZmaimgn uplRzse naC DEoO LdGf"));
    System.out.println(c("eIt uqHKC RBWOO xNf ujPMO SzRE HTL EOvd yAg"));
    System.out.println(c("NraWgCi: Nsas-eNEiTIsev rNsiTG!!"));
    System.out.println(c("(^_^)"));
    System.out.println(c("AWCTY HUOS RETP"));
    System.out.println(c("hwn oeesd acsp nawyya"));
    System.out.println(c("SpMycaeIesKyBorekn"));
    System.out.println(c("D's mroyr, Ivam. I'e faardi I act'n od htta."));
  }
}

```

**Output:**

```
hELlO WorLd!
prOGRamming puzZles anD COdE GoLf
tHe quICK BROWN fOx juMPS OvER THE LAzy dOg
WarNiNg: Case-sENsITive sTriNG!!
(^_^)
WATCH YOUR STEP
who needs caps anyway
MySpaceKeyIsBroken
I'm sorry, Dave. I'm afraid I can't do that.

```

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


# Question
Title: More fun with case-(very)-sensitive strings
Inspired by this challenge (or, more specifically, by misreading it), I've come up with the following challenge:

Given an input string S, reverse the order of all uppercase characters, and all lowercase characters. Leave all non-letter characters in place. For instance:

Note that the uppercase `W` (the first uppercase letter) was replaced with `H` (the last). Same goes for the lowercase letters: 'd' (the first) is swapped with `e` (the last), `l` (second) gets replaced with `l` (pen-ultimate) ... All the non-letter characters are left in place.

## Input

* Input is a string with only ASCII characters in the range 32-126.
* Input is guaranteed to be at least 1 character long, and won't exceed your language's limit.

## Output

* That same string, with the characters swapped as described.

## Additional rules

* Standard loopholes are forbidden
* Answer must be a full program or a function, not a snippet or a REPL-entry.
* , shortest answer in bytes wins.

## Test cases

```
A
A

Ok
Ok

OK
KO

Hello, World!
Wdlro, Holle!

0123456789
0123456789

The quick brown Fox jumps over the lazy doge
Feg odyza lehtr Tev ospmu jxon wor bkci uqeh

odd
ddo

racecar
racecar

EtOn Em OsN R AaToNsIsIhT!!1!
ThIs Is NoT A RaNsOmEnOtE!!1!

```

# Answer
# MATL, 14 bytes

```
2:"t@Y2myy)Pw(

```

**Try it at MATL Online**

**Explanation**

```
        % Impicitly grab input as a string
2:      % Push the array [1, 2] to the stack
"       % For each value in this array
  t     % Duplicate the top element of the stack (S)
  @     % Get the current loop index
  Y2    % Load the predefined literal 1Y2 ('ABC...Z') on the first loop
        % and the predefined literal 2Y2 ('abc...z') on the second loop (M)
  m     % Create a logical array the length of S that is TRUE when a character is in the
        % array M and FALSE otherwise (B)
  yy    % Make a copy of both S and B
  )     % Grab just the letters of S that were in M using B as an index
  P     % Reverse this array
  w     % Flip the top two stack elements
  (     % Assign them back into the string
        % Implicit end of for loop and implicit display

```
> 6 votes

# Answer
# Retina, 19 bytes

Retina doesn't have a direct way to reverse a string, but we can do it by exploiting the sorting stage:

```
O^#`[a-z]
O^#`[A-Z]

```

Sort (`O`), reading them as numbers (`#`), and then reverse the ordering (`^`), of all the strings matching the given regex (lowercase letters for the first line, and uppercase letters for the second).

This works because when we try to read strings without numeric characters as numbers they get treated as `0`, so all the characters have the same value for sorting. Since sorting is stable they are left in the same order, and reversing them returns the original string reversed.

Try it online!
> 12 votes

# Answer
# Perl, 45 bytes

44 bytes of code + `-p` flag.

```
for$c(u,l){@T=/\p{L$c}/g;s/\p{L$c}/pop@T/ge}

```

Try it online!

Unicode characters classes `\p{Lu}` and `\p{Ll}` matches respectively uppercase and lowercase letters.
So `/\p{L$c}/` will return the list of all upper (or lower) case letters (and store it inside `@T`).
And then, the regex `s/\p{$c}/pop@T/ge` will replace each (upper, then lower case) letter by the last letter of `@T` while removing it from `@T`.
> 10 votes

# Answer
## JavaScript (ES6), ~~74~~ ~~73~~ ~~71~~ 70 bytes

```
f=
s=>(g=r=>s=s.replace(r,_=>a.pop(),a=s.match(r)))(/[A-Z]/g,g(/[a-z]/g))
```

```
<input oninput=o.textContent=f(this.value)><pre id=o>
```

Edit: Saved 1 byte thanks to @Arnauld.
> 7 votes

# Answer
## JavaScript (ES6), 92 bytes

```
s=>(F=(r,s)=>s.replace(r,([x],a,y)=>y+F(r,a)+x))(/[a-z](.*)([a-z])/,F(/[A-Z](.*)([A-Z])/,s))

```

There has *got* to be a way to take advantage of the similarity between the regexes...

### Test snippet

```
let f =
s=>(F=(r,s)=>s.replace(r,([x],a,y)=>y+F(r,a)+x))(/[a-z](.*)([a-z])/,F(/[A-Z](.*)([A-Z])/,s))
```

```
<input style="width:500px" value="Wdlro, Holle!" oninput="O.value=f(this.value)"><br>
<input style="width:500px" value="Hello, World!" id=O disabled>
```
> 5 votes

# Answer
# Perl 6, ~~75~~ 69 bytes

```
{my @a=.comb;@(grep $_,@a).&{@$_=[R,] $_} for /<:Lu>/,/<:Ll>/;[~] @a}

```

### How it works

1. `my @a=.comb;`
Split the string into characters, and store them in an array.
2. `for /<:Lu>/,/<:Ll>/`
For two regexes matching upper and lower-case letters, respectively...

* `@(grep $_,@a)`
    Get a slice of all array entries matching the regex.
    * `.&{@$_=[R,] $_}`
    Assign the reverse of the slice to itself.
3. `[~] @a`
Concatenate the modified array to form a string again, and return it.

---

*-6 bytes by stealing the idea to use Unicode classes instead of character ranges, from @Dada's solution.*
> 4 votes

# Answer
# Jelly, 14 bytes

```
nŒlT,Ṛ$yJịŒsµ⁺

```

Try it online!

### How it works

```
nŒlT,Ṛ$yJịŒsµ⁺  Main link. Argument: s (string)

 Œl             Convert to lowercase.
n               Test for inequality.
   T            Truth; yield all indices of 1's.
    ,Ṛ$         Pair with its reverse. Yields [A, B] (pair of lists).
        J       Indices; yield I := [1, ..., len(s)].
       y        Translate; replace the integers of I that occur in A with the
                corresponding integers in B.
          Œs    Swapcase; yield s with swapped case.
         ị      Use the translated index list to index into s with swapped case.
            µ   Combine all links to the left into a chain.
             ⁺   Duplicate the chain, executing it twice.

```
> 3 votes

# Answer
# Bash \+ Unix utilities, ~~122~~ 121 bytes

```
f()(p=[^$1*
v="\)\([$1\)\("
for((n=99;n;n--)){
q="$q;s/^\($p$v.*$v$p\)$/\1\4\3\2\5/"
p=[^$1*[$1$p
}
sed $q)
f a-z]|f A-Z]

```

Try it online!

Not really very short; maybe someone can golf it further.

Input on stdin, output on stdout.

This will work correctly on inputs of less than 200 characters.

(Actually it correctly handles any string with fewer than 200 lower-case letters and fewer than 200 upper-case letters.)

If you increase the 99 in the code to 102 (at the cost of one additional byte), it will handle strings up to 205 characters.

However, you can't increase the 99 in the code beyond 102 since you'll then exceed sed's maximum argument length.

Here's a version without any particular input size limitation, but the count is a little longer, 137 bytes. (This longer version writes to an auxiliary file named t.)

```
f()(p=[^$1*
v="\)\([$1\)\("
for((n=`wc -c<t`;n;n--)){
sed -i "s/^\($p$v.*$v$p\)$/\1\4\3\2\5/" t
p=[^$1*[$1$p
})
cat>t
f a-z]
f A-Z]
cat t

```

Test runs:

```
for x in A Ok OK 'Hello, World!' 0123456789 'The quick brown Fox jumps over the lazy doge' odd racecar 'EtOn Em OsN R AaToNsIsIhT!!1!'
  do
    echo "$x"
    ./swapping3 <<<"$x"
    echo
  done

A
A

Ok
Ok

OK
KO

Hello, World!
Wdlro, Holle!

0123456789
0123456789

The quick brown Fox jumps over the lazy doge
Feg odyza lehtr Tev ospmu jxon wor bkci uqeh

odd
ddo

racecar
racecar

EtOn Em OsN R AaToNsIsIhT!!1!
ThIs Is NoT A RaNsOmEnOtE!!1!

```
> 3 votes

# Answer
# Python 2, 115 bytes

```
s=input();u=str.isupper
exec"r='';i=0\nfor c in s:r+=c[u(c):]or filter(u,s)[~i];i+=u(c)\ns=r.swapcase();"*2
print s

```

Try it online!
> 2 votes

# Answer
# Java (OpenJDK 8), 271 bytes

```
s->new String(new Error(){char[]o=s.toCharArray();char c;int b;{while(b++<2)for(int l=0,r=o.length;l<r;l++){for(--r;r>l&&f(r);r--);for(;l<r&&f(l);l++);if(l<r){o[l]=o[r];o[r]=c;}}}boolean f(int i){c=o[i];return b>1?!Character.isUpperCase(c):!Character.isLowerCase(c);}}.o)

```

Try it online!
> 2 votes

# Answer
# , 107 bytes

```
u=utf8ToInt(scan(,''));for(i in c(65,97)){l=which(u%in%i:(i+25));u[l]=u[rev(l)]};cat(intToUtf8(u,T),sep="")

```

Adapted from my response to the linked challenge. This is considerably easier than just swapping pairs. I wonder if I could get sub 100 with some golfs...

Try it online!
> 1 votes

# Answer
# 05AB1E, 19 bytes

```
2FÐlø€Ë≠āsƶ0KÂ‡<è.š

```

I/O as a list of characters.
Based on my 05AB1E answer in the related challenge.

Try it online or verify all test cases.

**Explanation:**

```
2F            # Loop 2 times:
  Ð           #  Triplicate the current character-list
              #  (which will use the implicit input-list in the first iteration)
   l          #  Lowercase all letters of the top copy
    ø         #  Zip/transpose the top two lists; pairing them together, and swapping
              #  rows/columns
     €Ë≠      #  Check for each pair whether they're NOT the same
              #  (so uppercase characters that have now become lowercase)
  ā           #  Push a list in the range [1, length] (without popping)
   s          #  Swap so the mapped list is at the top again
    ƶ         #  Multiply each 1/0 by its 1-based index
     0K       #  Remove all 0s
       Â      #  Bifurcate it (short for Duplicate & Reverse copy)
        ‡     #  Transliterate the indices with the reversed indices in [1, length]
         <    #  Decrease each by 1 (because 05AB1E uses 0-based indexing)
          è   #  Index them into the current character-list
           .š #  And swap all cases (lowercase to uppercase, and vice-versa)
              # (after the loop, the resulting character-list is output implicitly)

```
> 1 votes

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


title: Fast inverse square root

text:
# Question
Title: Fast inverse square root
Inspired by http://meta.codegolf.stackexchange.com/questions/547/write-a-code-golf-problem-in-which-script-languages-are-at-a-major-disadvantage question on meta, I've decided to make a question which could be problematic for scripting languages.

The goal is to calculate fast inverse square root, just like it was done in Quake III Arena. You will get the floating point number as first argument after program name and you should implement it. Simply doing `** -0.5` is disallowed as it doesn't implement the algorithm.

Your program will be called like this. The `12.34` could be other value.

```
$ interpreter program 12.34 # for interpreted languages
$ ./a.out 12.34 # for compiled languages

```

For comparison, this is original Quake III Arena implementation.

```
float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y = number;
        i = * ( long * ) &y;                       // evil floating point bit level hacking
        i = 0x5f3759df - ( i >> 1 );               // what the heck?
        y = * ( float * ) &i;
        y = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//      y = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

```

You have to do just one iteration because the second was commented out.

Winning condition: Shortest code.

# Answer
> 5 votes
## Perl, 89 85 chars

includes the necessary symbols for declaring and implementing a function

**edit:** standalone program. receives input parameter as command line argument

```
$_=unpack'f',pack'i',0x5f3759df-unpack('i',pack'f',$n=shift)/2;
print$_*1.5-$n/2*$_**3

```

# Answer
> 10 votes
# Jelly, 41 bytes

```
l2Ḟ©.*×+®µ23 .*×“9®ġ’_Hµ‘_Ḟ×Ḟ2*$$µ²×³3_×H

```

Try it online!

I know this challenge was designed in the hope that golfing languages would have a hard time. In a way, they do; Jelly doesn't have any primitives for looking at the representation of a floating point number in memory. However, it's still possible to solve the challenge via working out "manually" what the representation would look like using the basic definitions of floating point arithmetic, and in fact there's some amount of mathematical interest in doing things "the hard way". Jelly's so much terser than (say) C, that the fact it has to do more work doesn't prevent the program being considerably shorter.

## Explanation

The input is a floating-point number, as a number. In order to run the fast inverse square root algorithm, we need to find how it would be represented in memory. Jelly doesn't have a way to do that by looking at the bit pattern, but we can do it arithmetically.

First, note that the input must be positive (or its inverse square root would be undefined). As such, it's laid out in memory as follows, from most to least significant:

* A zero bit (the sign bit, zero means nonnegative so this will always be zero);
* The exponent (dividing the number by 2 to the power of the exponent scales it into the range 1 to 2), represented in 8 bits as its value minus 127;
* The mantissa (the result of the above division), represented in 23 bits via subtracting 1, then multiplying by 223.

The results of each of these calculations can be represented directly in Jelly. As such, we could generate the same output as C's convert-`float`-to-`int` memory hack does like this:

* Calculate the exponent
* Calculate the mantissa
* Take ((exponent + 127) × 223) + (mantissa × 223 \- 1)

However, the last expression shown here simplifies to the following rather simpler form:

* 223 × (exponent + mantissa + 126)
* alternatively, 8388608 × (exponent + mantissa) + 1056964608 (the result of multiplying the above out)

Let's call the exponent + mantissa of the input floating point number *em* for short. (The exponent + mantissa of a floating point number uniquely defines it.) In other words, after the `// evil floating point bit level hacking` comment, the C program is currently working with `i` = 8388608 × *em* \+ 1056964608.

The next steps in the C program are to halve *i*, and subtract it from `0x5f3759df` (which, in decimal, is 1597463007). *i* is (8388608 × *em* \+ 1056964608); halving it gives (4194304 × *em* \+ 528482304); the subtraction gives (1068980703 - 4194304 × *em*).

Then, C convert this number back to a floating point number `y`. Let's call the exponent + mantissa of `y` *em'*. What the C program is therefore effectively doing in the floating point representational hacking is solving the following equation:

* (1068980703 - 4194304 × *em*) = (8388608 × *em'* \+ 1056964608), which simplifies to:
* 12016095 = 4194304 × *em* \+ 8388608 × *em'*
* *em'* = (12016095 - 4194304 × *em*) ÷ 8388608 = (12016095 × 2-23) - *em* / 2

Now, to convert this into Jelly. We have a nice arithmetic definition of *em* and of *em'*, so we can translate it directly. First, here's how to calculate *em*:

```
l2Ḟ©.*×+®
l2                 Logarithm of the input, base 2
  Ḟ                Round down to the integer below (produces the exponent)
   ©               Store the exponent in a variable
    .*             Take (½ to the power of the exponent)
      ×            Multiply by {the original value, by default}
       +®          Add the value of the variable (i.e. the exponent)

```

The original value multiplied by ½ to the power of the exponent is equal to the original value divided by 2 to the power of the exponent, i.e. the mantissa, so this is *em*.

Getting *em'* is very straightforward from here, if we want it. However, we're going to need to convert the exponent+mantissa format back into a floating point number. This can be done unambiguously (the exponent's always an integer, the mantissa runs from 1 inclusive to 2 exclusive). However, to extract the exponent, we're going to want to floor and subtract 1. As such, it's actually shorter to generate *em'* -1.

* *em'* = (12016095 × 2-23) - *em* / 2, so
* *em'*-1 = (3627487 × 2-23) - *em* / 2

We can encode this formula in Jelly directly:

```
µ23 .*×“9®ġ’_H
µ                  set this point as the new default for missing arguments
 23                restart with 23
    .*             ½ to the power of that (i.e. 2 to the power -23)
      ×            times
       “9®ġ’       3627487 (compressed representation)
            _H     minus half {the value as of the last µ command}

```

Incidentally, we need the space because `23.` is a single token in Jelly (which evaluates to 23½).

The next step is to convert from *em'-1* to an actual floating point number `y`. We can extract the exponent using ; then the mantissa is *em'-1* \+ 1 - the exponent. To produce the floating point number, we want to calculate mantissa × 2exponent:

```
µ‘_Ḟ×Ḟ2*$$
µ                  set this point as the new default for missing arguments
 ‘                 increment (producing em'-1 + 1)
  _Ḟ               subtract the exponent (producing the mantissa)
    ×              multiply by
     Ḟ2*           2 to the power of the exponent
        $$         parse the previous three links as a group

```

Finally, we just need to handle the line marked `// 1st iteration`. This is just regular arithmetic, so encodes into Jelly really easily. The formula is:

* `y` × (1.5 - (`x2` × `y`²)), where `x2` is half the original input; this is shorter to express as
* `y` ÷ 2 × (3 - (`x` × `y`²)), where `x` is the original input.

And here's how it looks in Jelly:

```
µ²×³3_×H
µ                  set this point as the new default for missing arguments
 ²                 square
  ×³               multiply (×) by the original input (³)
    3_             subtract (_) from 3
      ×H           multiply by half {the value as of the last µ command}

```

## Verification

Running this program on the input `2` produces the output `0.7069300386983334`. This is the same value (allowing for differences in the float-to-string conversion) as produced by this VBA answer, and not equal to the mathematically correct value for 2-0.5.

# Answer
> 8 votes
# FORTRAN, ~~124~~ 113 Chars

saved 11 Bytes thanks to rafa11111

I know that this question is rather old, but it deserves a FORTRAN answer. It cannot outgolf Perl or Jelly, but it is at least not the worst.

```
character*9 c
equivalence(r,i)
call getarg(1,c)
read(c,*)y
r=y
i=Z'5f3759df'-ishft(i,-1)
print*,r/2*(3-y*r*r)
end

```

The hardest thing is to get command line arguments into FORTAN. Fortunately there is `getarg()` as alias for `get_command_argument()`. Note the use of an equivalence statement to avoid type casting. `r` and `i` are simply the same bytes but can be addressed as different datatypes. Since FORTRAN pointers cannot be casted into another datatypes like in C this is the way to go in FORTRAN.

# Answer
> 4 votes
## vba, 171

```
Type x
q As Long
End Type
Type z
w As Single
End Type
Function q(n)
Dim i As x,y As z
x=n/2
y.w=n
LSet i=y
i.q=&H5F3759DF-i.q/2
LSet y=i
q=y.w*(1.5-x*y.w*y.w)
End Function

```

finding a way to do the pointer cast was the hardest part. unfortunately, as there is no real direct way, I had to define my own type, which added to the length of the program

call from the immediate window with ?q(number)

result:

> ?2^-0.5
> 0.707106781186548
> ?q(2)
> 0.706930038698333

# Answer
> 4 votes
# Portable C99, 114 bytes

```
float g(f,t,e)float f,t;{t=1.93243-frexp(f,&e);t-=.5*(e&1);t=ldexp(t+(t<1),-(e>>1)-(t<1));return(1.5-.5*f*t*t)*t;}

```

Try it online!

A solution in a more portable subset of C99. Uses `frexp` and `ldexp` from `math.h` instead of bit twiddling. Has very slight rounding errors. Here's a documented version that should be exact:

```
float my_rsqrt(float f) {
    int e;
    float r = frexp(f, &e);

    // Subtract from magic mantissa.
    int prev_mode = fegetround();
    fesetround(FE_UPWARD);
    r = (0x0.3759dfp1f + 1.5f) - r;
    fesetround(prev_mode);

    // Handle LSB of exponent that spills into mantissa.
    if (e & 1) r -= 0.5f;

    // Handle overflow.
    if (r < 1.0f) {
        r += 1.0f;
        e += 2;
    }

    // Scale with adjusted exponent.
    r = ldexp(r, -(e>>1));

    return r * (1.5f - 0.5f * f * r * r);
}

```

# Answer
> 2 votes
## C#, 157 chars

Horrible for golfing, but why not...

```
class C{unsafe static void Main(string[]a){var n=float.Parse(a[0]);var i=*(int*)&n/-2+0x5f3759df;var y=*(float*)&i;System.Console.Write(y*1.5f-y*n/2f*y*y);}}

```

Readable version:

```
class C
{
    unsafe static void Main( string[] a )
    {
        var n = float.Parse( a[0] );
        var i = *(int*) &n / -2 + 0x5f3759df;
        var y = *(float*) &i;
        System.Console.Write( y * 1.5f - y * n / 2f * y * y );
    }
}

```

# Answer
> 1 votes
# C, 173 chars

Might as well put code golfed version of example above. Could be less if I would ignore portability.

```
#include<stdio.h>
#include<stdint.h>
main(int _,char**a){float n,g;sscanf(a[1],"%f",&n);int32_t o=0x5f3759df-(*(long*)&n>>1);g=*(float*)&o;printf("%g\n",g*(1.5-(n/2*g*g)));}

```

# Answer
> 1 votes
## Java, 175 bytes

I decided to give this question a Java answer since it didn't have one, and then it got tweeted and bumped while I was golfing... weird.

As a lambda, `101 bytes`:

```
f=n->{float y=Float.intBitsToFloat(0x5f3759df-(Float.floatToIntBits(n)>>1));return y*(1.5f-n/2*y*y);}

```

As a full program, `175 bytes`:

```
class Q{public static void main(String[]a){float n=Float.parseFloat(a[0]),y=Float.intBitsToFloat(0x5f3759df-(Float.floatToIntBits(n)>>1));System.out.print(y*(1.5f-n/2*y*y));}}

```

Darn it, two bytes more than portable C. It's the darn `Float.floatToIntBits()`&`Float.intBitsToFloat()`, for Java doesn't like it when you try to say `"You know this float that I just defined? Make it an int. You know that int I just defined? Make it a float."`

# Answer
> 1 votes
# Julia, 96 characters

```
F=Float32;\ =reinterpret;n=parse(F,ARGS[]);y=F\(0x5f3759df-UInt\n>>1);print(y*(1.5f0-(n/2*y*y)))

```

# Julia (function), 73 characters

```
n->(\ =reinterpret;y=Float32\(0x5f3759df-UInt\n>>1);y*=(1.5f0-(n/2*y*y)))

```

Needs to be run on a 32-bit system for `UInt` to mean `UInt32`. Unfortunately, there isn't a similar alias for `Float32`, and if I tried to just `parse(ARGS[])`, it would be `Float64`.

# Answer
> 1 votes
# X86-64 Machine Code, Microsoft Calling Convention - ~~65~~ 61 bytes

```
48 8B 4A 08          mov         rcx,qword ptr [rdx+8]
48 83 EC 28          sub         rsp,28h
E8 C5 FD FF FF       call        strtof (07FF62D2A1642h)
48 83 C4 28          add         rsp,28h
66 0F 7E C0          movd        eax,xmm0
D9 E8                fld1
D9 E8                fld1
D8 C0                fadd        st,st(0)
D8 F9                fdivr       st,st(1)
DC C1                fadd        st(1),st
50                   push        rax
D8 0C 24             fmul        dword ptr [rsp]
5A                   pop         rdx
D1 F8                sar         eax,1
B9 DF 59 37 5F       mov         ecx,5F3759DFh
2B C8                sub         ecx,eax
51                   push        rcx
D9 04 24             fld         dword ptr [rsp]
D9 C0                fld         st(0)
DE C9                fmulp       st(1),st
DE C9                fmulp       st(1),st
DE E9                fsubp       st(1),st
D8 0C 24             fmul        dword ptr [rsp]
D9 14 24             fst         dword ptr [rsp]
58                   pop         rax
C3                   ret

```

Might be a little shorter in 32 bit. About 20 bytes used in string conversion.

-4 bytes by using `strtof`

# Answer
> 0 votes
# Tcl, 110 bytes

```
rename binary B
proc R n {B s [B f f $n] i i
B s [B f i [expr 0x5f3759df-($i>>1)]] f y
expr $y*1.5-$n/2*$y**3}

```

Try it online!

---

~~Tcl, 112 bytes
```
rename binary B
proc R n {B s [B f f $n] i i
B s [B f i [expr 0x5f3759df-($i>>1)]] f y
expr $y*(1.5-$n/2*$y*$y)}

```
Try it online!
~~

---

~~Tcl, 113 bytes
```
rename binary B
proc R n {B s [B f f $n] i i
B s [B f i [expr 0x5f3759df-($i>>1)]] f y
expr $y*(1.5-$n*.5*$y*$y)}

```
Try it online!
~~

---

~~Tcl, 129 bytes
```
rename binary B
proc R n {B scan [B format f $n] i i
B scan [B format i [expr 0x5f3759df-($i>>1)]] f y
expr $y*(1.5-$n*.5*$y*$y)}

```
Try it online!
Tcl, 133 bytes
```
proc R n {binary scan [binary format f $n] i i
binary scan [binary format i [expr 0x5f3759df-($i>>1)]] f y
expr $y*(1.5-$n*.5*$y*$y)}

```
Try it online!
Tcl, 142 bytes
```
proc R n {binary scan [binary format f $n] i i
set i [expr 0x5f3759df-($i>>1)]
binary scan [binary format i $i] f y
expr $y*(1.5-$n*.5*$y*$y)}

```
Try it online!
~~

---
Tags: code-golf, math, floating-point
---


title: Get to the Zone!

text:
# Question
Title: Get to the Zone!
You are playing a famous game called \\$1\text{D Array BattleGround}\\$. In the game, the player can be stationed in any position from \\$0\\$ to \\$10^5\\$.

You are a *Paratrooper* in the game and have the ability to do *two types of operation* \\$-\\$

* ***Advance***, which would **multiply** your position by \\$2\\$
* ***Fall-back***, which would **decrease** your current position by \\$1\\$

Each type of operation requires \\$1\\$ second.

You are stationed in \\$N\\$ and want to go to \\$M\\$ in the minimum time possible, (\\$1≤ N, M ≤10^4\\$).

Find out the minimum time you need to ***Get to \\$M\\$***.

*Note: After each operation, you must remain in the zone from \\$0\\$ to \\$10^5\\$.*

### Sample

```
Input : 4 6
Output: 2

Input : 10 1
Output: 9

Input : 1 3
Output: 3

Input : 2 10
Output: 5

Input : 666 6666
Output: 255

Input : 9999 10000
Output: 5000

```

This is a code-golf challenge so code with lowest bytes wins!

# Answer
> 23 votes
# JavaScript (ES6), 30 bytes

Takes input as `(N)(M)`.

```
N=>g=M=>M>N?M%2-~g(M+1>>1):N-M

```

Try it online!

### How?

Instead of going from \\$N\\$ to \\$M\\$, we go from \\$M\\$ to \\$N\\$.

While \\$M\\$ is greater than \\$N\\$:

* if \\$M\\$ is odd, increment it and divide it by \\$2\\$ (2 operations)
* if \\$M\\$ is even, just divide it by \\$2\\$ (1 operation)

When \\$M\\$ is less than or equal to \\$N\\$, the remaining number of operations is \\$N-M\\$.

*Example for \\$N=666\\$, \\$M=6666\\$:*

```
  M   | transformation     | operations | total
------+--------------------+------------+-------
 6666 | M / 2       = 3333 |      1     |   1
 3333 | (M + 1) / 2 = 1667 |      2     |   3
 1667 | (M + 1) / 2 = 834  |      2     |   5
 834  | M / 2       = 417  |      1     |   6
 417  | M + 249     = 666  |     249    |  255

```

With inverse operations in reverse order, this gives:

$$((((666-249)\times 2)\times 2-1)\times 2-1)\times 2=6666$$

The idea behind that is that it's always cheaper to process the greatest number of *fall-back* operations at the beginning of the process (i.e. when \\$N\\$ is still small) rather than exceeding \\$M\\$ by too large a margin with hasty *advance* operations and doing *fall-backs* afterwards.

# Answer
> 6 votes
# C (gcc), ~~53~~ 34 bytes

Saved a whopping 19 bytes thanks to the man himself Arnauld!!!

```
f(N,M){M=M>N?M%2-~f(N,-~M/2):N-M;}

```

Try it online!

A port of Arnauld's JavaScript answer.

# Answer
> 6 votes
# APL (Dyalog Unicode), 24 bytes SBCS

Recursive dfn as per Arnauld's answer.

```
{⍵≤⍺:⍺-⍵⋄(2|⍵)+1+⍺∇⌈⍵÷2}

```

Try it online! We take Arnauld's approach but we use APL's nice builtins to make a single recursive call instead of having to choose the recursive call that we want to make (which would depend on the parity of M):

```
{⍵≤⍺:⍺-⍵⋄(2|⍵)+1+⍺∇⌈⍵÷2} ⍝ dfn taking N on the left and M on the right
{⍵≤⍺:                    } ⍝ if N is less than or equal to M
      ⍺-⍵                  ⍝ just return N - M
          ⋄                 ⍝ otherwise
                   ⍺∇⌈⍵÷2  ⍝ divide M by 2, round up and call this function recursively
                 1+         ⍝ to which we add 1 unconditionally
          (2|⍵)+            ⍝ and to which we add the parity of M, i.e. add one more iff M is odd.

```

# Answer
> 6 votes
# Husk, 11 bytes

```
←V€⁰¡ṁ§eD←;

```

Try it online! Arguments are in reversed order (first target, then initial position).

# Explanation

Brute force turned out shorter than more efficient methods.

```
←V€⁰¡ṁ§eD←;  Inputs: M (stored in ⁰) and N (implicit).
          ;  Wrap in list: [N]
    ¡        Iterate, returning an infinite list:
     ṁ         Map and concatenate:
         ←       Decrement and
        D        double,
      §e         put the results in a two-element list.
 V           1-based index of first list that
  €⁰         Contains M.
←            Decrement.

```

# Answer
> 4 votes
# Japt, ~~15~~ 14 bytes

Heading tag now includes the completely unnecessary space SE are forcing on us for no good reason

Well, seeing as everyone else is taking Arnauld's approach ...! Be sure to `+1` him if you're `+1`ing this.

Takes input in reverse order.

```
>V?¢ÌÒß°Uz:UnV

```

Try it

```
>V?¢ÌÒß°Uz:UnV     :Implicit input of integers U=M and V=N
>V                 :Is U greater than V
  ?                :If so
   ¢               :  Convert U to base-2 string
    Ì              :  Get last character
     Ò             :  Subtract the bitwise negation of
      ß            :  A recursive run of the programme with argument U (V remains unchanged)
       °U          :    Increment U
         z         :    Floor divide by 2
          :        :Else
           UnV     :  U subtracted from V

```

# Answer
> 4 votes
# Jelly, 13 bytes

Took quite a while to find an approach which could be implemented in under 16 bytes.

```
‘:Ḃȯ⁹>$Ɗ?Ƭ2i’

```

A dyadic Link accepting `M` on the left and `N` on the right which yields the time you need to manoeuvre.

**Try it online!**

### How?

```
‘:Ḃȯ⁹>$Ɗ?Ƭ2i’ - Link: M, N
          2   - use two as the right argument (R) of:
         Ƭ    -   collect up, starting at M, while results are distinct:
        ?     -     if...
       Ɗ      -     ...condition: last three links as a monad - i.e. f(current_value):
  Ḃ           -       LSB (i.e. is current_value odd?)
      $       -       last two links as a monad:
     ⁹        -         chain's right argument, N
    >         -         greater than? (i.e. is current_value less than N?)
   ȯ          -       logical OR (i.e. is current_value either odd or less than N?)
‘             -     ...then: increment
 :            -     ...else: integer divide by R (2)
          i  - 1-based index of first occurrence of N in that
           ’ - decrement

```

# Answer
> 3 votes
# 05AB1E, 18 bytes

```
[ÐÆd#`DÉD½+;‚¼}Æ¾+

```

Inspired by *@Arnauld*'s JavaScript answer, so make sure to upvote him!

Try it online or verify all test cases.

**Explanation:**

```
[         # Start an infinite loop:
 Ð        #  Triplicate the pair at the top
          #  (which will use the implicit input in the first iteration)
  Æ       #  Reduce it by subtracting (N-M)
   d      #  If this is non-negative (>=0):
    #     #   Stop the infinite loop
  `       #  Pop and push both values separated to the stack
   D      #  Duplicate the top value `M`
    É     #  Check if it's odd (1 if odd; 0 if even)
      ½   #  If it's 1: increase the counter_variable by 1
     D    #  (without popping by duplicating first)
     +    #  Add this 1/0 to `M`
      ;   #  And halve it
       ‚  #  Then pair it back together with the `N`
 ¼        #  At the end of each iteration, increase the counter_variable by 1
}Æ        # After the infinite loop: reduce by subtracting again (N-M)
  ¾+      # And add the counter_variable to this
          # (after which the result is output implicitly)

```

# Answer
> 2 votes
# perl -alp, 62 bytes

```
$;=pop@F;{$_<$;||last;$"+=1+$;%2;$;+=$;%2;$;/=2;redo}$_+=$"-$;

```

Try it online!

This uses the same logic as most other solutions.

# Answer
> 1 votes
# Befunge-98, 75 bytes

The program keeps a running total of moves at `(0, 0)` and remembers `N` at `(1, 0)`. It definitely could be golfed some more.

```
p&01p&>:01g-0\`|>:2%|
2/1  v  >0g+.@ >^   >
1+2/2v  ^0-\g10<    >
0+g00<^p0

```

Try it online! Edit: I had to add some extra arrows for it to run on TIO for some reason. See comments.

I used the logic from Arnauld's JavaScript answer.

# Answer
> 1 votes
# Charcoal, 24 bytes

```
Ｎθ⊞υＮＷ¬№υθ≔⁺⊖υ⊗υυＩ⊖Ｌ↨Ｌυ²

```

Try it online! Link is to verbose version of code. Takes inputs in the order `M`, `N`. Horribly inefficient breadth-first search, so don't bother putting in large numbers. Explanation:

```
Ｎθ

```

Input `M`.

```
⊞υＮ

```

Push `N` to the predefined empty list.

```
Ｗ¬№υθ

```

Repeat until `M` is present in the list...

```
≔⁺⊖υ⊗υυ

```

... concatenate the decremented list with the doubled list.

```
Ｉ⊖Ｌ↨Ｌυ²

```

Calculate the number of concatenations.

# Answer
> 1 votes
## Batch, 153 bytes

```
@echo off
@set/an=%1,c=0
:l
@if %n%==%2 echo %c%&exit/b
@set/a"c+=1,p=~-%2/n+1,q=p&p-1,r=n*p-%2,n-=1
@if %q%==0 if %r% lss %p% set/an=n*2+2
@goto l

```

Explanation:

```
set /a n=%1, c=0

```

Initialise `n` from the first parameter and clear the loop count.

```
if %n% == %2 echo %c% & exit /b

```

Output the count once the target in the second parameter is reached.

```
set /a " c += 1, p = ~-%2 / n + 1, q = p & p - 1, r = n * p - %2, n -= 1

```
* Increment the loop count
* Calculate the number of advances needed
* Calculate how near to the target advances would get
* Assume that we'll fall back

```
if %q% == 0 if %r% lss %p% set /a n = n * 2 + 2

```

If the advances would get near to the target then undo the fall back and advance instead.

# Answer
> 1 votes
# bc, 61 bytes

```
define f(n,m){if(n>=m)return n-m;return 1+m%2+f(n,(m+m%2)/2)}

```

Try it online!

Given `n`, and `m`, return `n - m` if `n` is greater than or equal to `m`. Else, it returns `1` plus `1` (if `m` is odd), plus the result of (`n`, `m / 2`), with the division rounded upwards. The latter is done with a recursive call.

# Answer
> 1 votes
# Erlang (escript), 65 bytes

Port of Arnauld's answer.

```
f(X,Y)->if X>Y->X-Y;true->1+(Y rem 2)+f(X,(Y+(Y rem 2))div 2)end.

```

Try it online!

# Answer
> 1 votes
# , 22 bytes

A port of RGS' APL answer with J's hooks and forks.

```
-`(($:>.@-:)+1+2|])@.<

```

Try it online!

---
Tags: code-golf, graph-theory
---


title: Give me the first day of next month

text:
# Question
Title: Give me the first day of next month
Simple question!

Given a string that contains a date in ISO8601 format, print the first of the next month in ISO8601 format.

Example inputs:

`2018-05-06`

`2019-12-20`

Their respective outputs:

`2018-06-01`

`2020-01-01`

The rules:

* Imports are free and don't count towards your score.
* The date will be stored in a string called `s`.
* The solution with the least characters, wins

# Answer
> 5 votes
# JavaScript (V8), ~~67~~, ~~57~~, 56 bytes

-10 thanks to Arnauld,
-1 joining template string and ternary

```
s=>([a,b]=s.split`-`,+a+!(b%=12))+`-${b++<9?'0'+b:b}-01`

```

Test cases:

```
f=s=>([a,b]=s.split`-`,+a+!(b%=12))+`-${b++<9?'0'+b:b}-01`

console.log(f('2018-12-20'))
console.log(f('2019-05-06'))
```

# Answer
> 4 votes
# Bash, ~~31~~, 24 bytes

7 bytes saved thanks to @manatwork and @nwellnhof

```
date -d${1%??}1month +%F

```

Try it online!

# Answer
> 2 votes
# Ruby 49 bytes

```
d=Date.parse(s);print Date.new(d.year,d.mon,1)>>1

```

Online repl

# Answer
> 1 votes
# PHP, 57 bytes

```
[$y,$m]=explode('-', $s);$m=++$m%13?:!!++$y;$d="$y-$m-1";

```

Test cases:

```
<?php
function next_month($s) {
    [$y,$m]=explode('-', $s);
    $m=++$m%13?:!!++$y;
    return "$y-$m-1";
}

$s = "2018-05-06";
echo next_month($s); // Gives 2018-6-1

$s = "2019-12-20";
echo next_month($s); // Gives 2020-1-1

```

# Answer
> 1 votes
# Retina 0.8.2, 33 bytes

```
T`9d`d`.9*(-12)?-..$
-23|-..$
-01

```

Try it online! Link includes test cases. Explanation:

```
T`9d`d`

```

Increment with wrap-around...

```
.9*(-12)?-..$

```

... the last non-`9` digit, plus trailing `9`s, in either the year or the month, depending on whether the month is `12`. (Digits in the following date parts also get incremented.)

```
-23|-..$
-01

```

Replace the day with `01`. Also, if the month was `12` before, it will be `23` now, and also needs to be reset to `01`.

# Answer
> 0 votes
# Red, 39 bytes

```
t: load s
t/month: t/month + t/day: 1
t

```

# Answer
> 0 votes
# Python 3.6.9, 73 characters

```
from datetime import *; from dateutil.relativedelta import relativedelta as r;
(datetime(*map(int, s.split('-')), 1) + r(months=1)).strftime('%Y-%m-01')

```

Your rules say that imports don't count, so I didn't count them.

---
Tags: code-golf, date
---


# Question
Title: Represent n as an expression containing all the digits
Related Challenge: Single Digit Representations of Natural Numbers

# Task

Write a program/function that when given a non-negative integer \\$n \le 100000\\$ outputs an expression which uses all the digits from \\$0\\$ to \\$9\\$ exactly once and evaluates to \\$n\\$

The expression outputted by your program may only use the operations listed below:

* addition
* subtraction and unary minus (both must have the same symbol)
* multiplication
* division (fractional, i.e. 1/2 = 0.5)
* exponentiation
* parentheses

**Note:** Concatenation is **not** allowed

# Output Format

* Output can be a string, list of operations and numbers or a list of lists in place of brackets.
* You may choose the precedence of the operators but it must be consistent for all outputs produced by your program/function
* Output may be in polish, reverse polish or infix notation but it must be consistent for all outputs produced by your program/function.
* You can use custom symbols for representing the digits and operations but the symbols used for representing the digits and operations should be distinct.

# Scoring

This is so shortest bytes wins

# Sample Testcases

```
0 -> 0 ^ (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)
4 -> (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8) / 9
7 -> 0 * (1 + 2 + 3 + 4 + 5 + 6 + 8 + 9) + 7
45 -> 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
29 -> 1 + 2 + 7 + 6 + 5 + 4 + 3 + 0 + (9 - 8)
29 -> (((9 + 8 + 7 + 6) * 0) + 5 + 4) * 3 + 2 * 1
100 -> (9 * 8) + 7 + 4 + 5 + 6 + 3 + 2 + 1 + 0

```

---

A proof by exhaustion (also contains program used to generate the proof) that shows that all number less than or equal to \\$100000\\$ have an expression that uses all the digits.

# Answer
> 8 votes
# 05AB1E, ~~25~~ 24 bytes

```
9Ýœ"+-*m"9ãðδšδ.ιJ˜.Δ.VQ

```

Brute-force approach, so obviously extremely slow.
Outputs in reverse Polish notation, with the characters `+-*m` for addition, subtraction, multiplication, and exponentiation respectively. Division isn't necessary for the \\$\[0,100000\]\\$ range we have to support.

Try it online with additional (first) input to specify the digit-range \\$\[0,n\]\\$ instead of \\$\[0,9\]\\$, for which I've used `4` right now as example.

**Explanation:**

```
9Ý           # Push a list in the range [0,9]
  œ          # Get all possible permutations of this list
"+-*m"       # Push string "+-*m"
      9ã     # Get all possible combinations of size 9 with the cartesian product
         δ   # Map over each string of operations:
        ð š  #  Convert it to a list of characters, and prepend a space
δ            # Apply double-vectorized with both lists of lists:
 .ι          #  Interleave the lists
J            # Then join each inner list together to a string
.Δ           # Find the first string which is truthy for:
  .V         #  Evaluate/execute the string as 05AB1E code
    Q        #  And check if the result is equal to the (implicit) input-integer
             # (after which the found result is output implicitly)

```

If we are allowed to output all possible results instead of just one, the  (find first) could be `ʒ` (filter) for -1 byte. Although in that case it would become even slower than it already is..

# Answer
> 5 votes
# , ~~249~~ ~~244~~ ~~234~~ ~~224~~ ~~220~~ 200 bytes

Or +arrangements library, ~~237~~ ~~232~~ ~~222~~ ~~212~~ ~~208~~ 188 bytes (and somewhat faster)

*Multiple edits: -15 bytes thanks to Mukundan314 (no division needed), -4 bytes thanks to 'my pronoun is monicareinstate', -10 bytes by outputting in Polish (prefix) notation, and (latest) -20 bytes by outputting as error message*

```
function(n){apply(gtools::permutations(10,10)-1,1,function(k)apply(expand.grid(rep(list(1:4),9)),1,function(l){for(m in 10:1)F=c(`+`,`-`,`*`,`^`)[[c(l,1)[m]]](F,k[11-m])
if(F==n)stop(letters[l],k)}))}

```

Try it online!

Outputs **as error message**, in Polish notation using 'a' to denote plus, 'b' to denote minus, 'c' to denote multiply, and 'd' to denote exponentiation.

Commented version before golfing (with more-readable output that can be copy-pasted to directly check):

```
make_number=function(n,with=0:9) {
    i=arrangements::permutations(with)          # all the permutations of the digits 0..9
    j=as.matrix(expand.grid(rep(list(1:5),length(with)-1)))
                                                # all the combinations of 1..5 (for the 5 operators)
    o=c("+"=`+`,"-"=`-`,"*"=`*`,"/"=`/`,"^"=`^`)
                                                # the 5 operators that we can use
    for(k in 1:nrow(i)){for(l in 1:nrow(j)){    # cycle through the permutations of digits & operators
        t=i[k,1]                                # total starts as first digit
        for(m in 2:length(with)-1){t=o[[j[l,m]]](t,i[k,m+1])}
                                                # apply all the operators using each next digit
        if(!is.na(t)&&(t==n)){                  # if we get the answer we're looking for...
                                                # return a string with the calculation
            return( paste0( paste0(rep("(",ncol(j)),collapse=""),paste0(c("",names(o)[j[l,]]),i[k,],collapse=")")))
        }
    }}
}

> make_number(1)
[1] "(((((((((0)-1)-2)-3)*4)-5)+6)+7)+8)+9"
> make_number(99)
[1] "(((((((((0)+1)/2)+3)+4)+5)*6)+7)+8)+9"
> make_number(1234)
[1] "(((((((((0)*1)+2)+3)^4)/5)+6)+7)*9)-8"

```

Note that this algorithm will always find first (and stop at) a solution with the smallest rearrangment of the digits from the starting order of 0..9.

# Answer
> 3 votes
# Charcoal, 84 bytes

```
Ｎθ≔”y⁰¹²³⁴⁵⁶⁷⁸⁹”ε≔ＶεηＷ¬ω«≔⭆◧Ｉηχ§εΣκζ≦⊕η¿⬤ε№ζκＦＸ⁴¦⁹«≔⭆⁹§”y⁺×⁻Ｘ”÷κＸ⁴λδ¿⁼Ｖ⁺δ⪫ζ´¦θ≔δω»»ωζ

```

Don't try it online! Link is to verbose version of code. Outputs prefix notation using Charcoal operators and digits (note that it's not valid Charcoal code due to the omission of `¦` separators between the digits, and it still wouldn't be useful without the  cast operator). Explantion:

```
Ｎθ

```

Input `n`.

```
≔”y⁰¹²³⁴⁵⁶⁷⁸⁹”ε

```

Assign the list of Charcoal's digits.

```
≔⁰η

```

Start checking starting at `0000000000` and working up.

```
Ｗ¬ω«

```

Repeat until we have an answer.

```
≔⭆◧Ｉηχ§εΣκζ

```

Convert the current trial index to a 10-digit number in Charcoal digits.

```
≦⊕η

```

Increment the trial index.

```
¿⬤ε№ζκ

```

If this is a permutation of the 10 digits, then...

```
ＦＸ⁴¦⁹«

```

Loop over all operator combinations,

```
≔⭆⁹§”y⁺×⁻Ｘ”÷κＸ⁴λδ

```

convert each into a string of operators,

```
¿⁼Ｖ⁺δ⪫ζ´¦θ

```

compare the value with `n`,

```
≔δω

```

and set the result if it matches.

```
»»ωζ

```

Output the resulting operator string and digits.

96-byte version that can actually finish in under a minute on very simple examples:

```
Ｎθ≔”y⁰¹²³⁴⁵⁶⁷⁸⁹”ε≔ＶεηＷ¬ω«≔⭆◧Ｉηχ§εΣκζ≦⊖ι≦⊕η¿⬤ε№ζκＷ∧¬ω‹ιＸ⁴¦⁹«≔⭆⁹§”y⁺×⁻Ｘ”÷ιＸ⁴λδ¿⁼Ｖ⁺δ⪫ζ´¦θ≔δω≦⊕ι»»ωζ

```

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

# Answer
> 3 votes
# Python 3, ~~200~~ ~~194~~ ~~186~~ 178 bytes

*-6, -2, -6, -8 bytes, and a test runner thanks to @Mukundan314.*

```
lambda n:next(s for o in product(*[[*"+-*","**"]]*9)for l in permutations("0123456789")if eval(s:="("*8+l[9]+')'.join(o[i]+str(l[i])for i in range(9)))==n)
from itertools import*

```

Try it online! (5 digits case)

Outputs in infix notation with parentheses, using `+-*` respectively for addition, subtraction, and multiplication; uses `**` and exponentiation. The program generates Python code that gets eval'd to check for equivalence to `n`.

Slightly more-readable version with a variable for the number of digits:

```
L=9
import itertools as i
def g(n):
    for l in i.permutations(map(str,range(1,L+1))):
        for o in i.product("+-*m",repeat=L-1):
            s=l[L-1]
            for j in range(L-1):
                s='('+s+o[j]+l[j]+')'
            s=s.replace("m","**")
            if eval(s)==n:
                return s

```

# Answer
> 3 votes
# Jelly, ~~21~~ 26 bytes

*+5 bytes for a fix based on Kevin Cruijssen*

```
“+×*_”ṗ9
⁵ḶŒ!p¢ż/€Ẏ€V=¥ƇḢḢ

```

Brute force, like the 05AB1E answer, so it is also extremely slow.

Outputs in infix notation with `+×*_` to represent addition, multiplication, exponentiation, and subtraction respectively. All operators have equal precedence. Similarly to my Python answer, this generates an expression and evals it to find what it evaluates to.

Try it online (in a version that allows you to enter the number of digits) The value for `n` should be provided as the first argument, while the input should consist of two lines: the first equal to the number of digits; the second less by one.

### Explanation (going to update soon, I should be able to golf a bit off):

```
“+×*_”ṗ9           # literal string "+×*_" (Jelly arithmetic symbols) Cartesian power 9

⁵ḶŒ!p¢ż/€Ẏ€V=¥ƇḢḢ
⁵Ḷ                 # lowered_range(10): [0,1,2,3,...,9]
  Œ!               # all permutations of these digits
    p              # Cartesian product with
     ¢             # the list of all permutations of 9 arithmetic symbols
      ż/€Ẏ€        # zip and tighten each to squeeze together (golfportunity?)
           V=¥Ƈ    # Filter for those that evaluate to
               Ḣ   # n (surely there is a way around this)
                Ḣ  # get the first one

```

If no string works (which could occur if `n` is too large or the number of digits is decreased), then it outputs `0`.

# Answer
> 0 votes
# Pyth, 23 bytes

```
hfqQ.vjdsT*^"+-*^"9.pUT

```

Try it online! (5 digit case)

### Explanation

```
hfqQ.vjdsT*^"+-*^"9.pUT
h                        : first element of
 f                       : filter on
          *              : cartesian product of
           ^"+-*^"9      : all 9 length string that can be formed with the chars +, -, * and ^
                   .pUT  : and all permutations of [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
  qQ                     : for equality of input and
    .vjdsT               : evaluated result of operators and permutation joined with spaces

```

---
Tags: code-golf, expression-building
---


title: Write a crochet pattern generator

text:
# Question
Title: Write a crochet pattern generator
# Introduction

I crochet a lot, and lately I've started writing crochet patterns. However, while I work very well from notes such as *rnds 2-6 (round number = x, original number of stitches = y): \*dc x-2 stitches, 2 dc in next stitch\* around (xy stitches)*, most published patterns spell out each row in more detail. I don't like writing out each individual row/round myself though, so I want to have a program do it for me.

# Challenge

The challenge is to write a program or function that takes three mandatory inputs (r, s, and y) and returns a string of the pattern.

## Inputs

The inputs can go in any appropriate order or format, just please point that out so others can run your code.

R is an integer corresponding to the number of rounds/rows (use whichever designation you want) to generate. S is a string corresponding to the type of stitch. This can be guaranteed to be one of the following strings: "tc", "dc", "hdc", "sc", or "ch". Y is the number of stitches in row/round 1, and the number of increases in each following row (for instance, if y=6, row 1 has 6 stitches, row 2 has 12 stitches, row 3 has 18 stitches, etc). In the general case: row x has xy stitches.

## Outputs

The output is a list of strings with length r, in the following pattern.

`O N: \*s in next N-2 stitches, 2 s in next stitch\* y times (NY stitches).`

To clarify: it should return r strings, in order from least row/rnd number to greatest row/rnd number. The first row/rnd should be row 1, and the last row should be row r. In the template, replace s and y with the matching inputs, and N is the row number of the current row (N isn’t an input, just an integer that represents the current row). O is used to denote one of the following strings, your choice: “Row”, “Round”, or “Rnd”.

Each line of output should be separated by a newline. The period is necessary and should follow the parentheses.

## Edge Cases

You can assume s is one of the listed strings. R will always be a positive integer, as will y.

You don’t have to do anything fancy for row 1, it can be `Row 1: \*s in next -1 stitches, 2 s in next stitch\* y times (y stitches).` Row 2 can also be outputted in the default format, as `Row 2: \*s in next 0 stitches, 2 s in next stitch\* y times (2y stitches).` Thusly, it can be outputted with a for loop. But, if you output rows 1 and 2 as `Row 1: s in next y stitches (y stitches).\nRow 2: 2 s in next y stitches (2y stitches).`, you can have -10% or -10 bytes, whichever is smaller, removed from your score.

## Scoring

This is code golf, so fewest bytes wins. If you output rows 1 and 2 as shown in the Output section above, your score is lowered by -10% or -10 bytes, whichever is smaller.

# Example Input and Output

Input \[the format doesn’t matter so much as the answer, so it could be any format the language supports\]: (r,s,y)

> 1. (5, “dc”, 6)
> 2. (3, “sc”, 1)
> 3. (6, “hdc”, 100)
> 4. (0, “ch”, 1)
> 5. (5, “tc”, 0)

Output \[this format must be fairly exact, hyphens are used to show negative numbers\]:

> 1. `Row 1: \*dc in next -1 stitches, 2 dc in next stitch\* 6 times (6 stitches).\nRow 2: \*dc in next 0 stitches, 2 dc in next stitch\* 6 times (12 stitches).\nRow 3: \*dc in next 1 stitches, 2 dc in next stitch\* 6 times (18 stitches).\nRow 4: \*dc in next 2 stitches, 2 dc in next stitch\* 6 times (24 stitches).\nRow 5: \*dc in next 3 stitches, 2 dc in next stitch\* 6 times (30 stitches).`
> 2. `Rnd 1: \*sc in next -1 stitches, 2 sc in next stitch\* 1 times (1 stitches).\nRnd 2: \*sc in next 0 stitches, 2 sc in next stitch\* 1 times (2 stitches).\nRnd 3: \*sc in next 1 stitches, 2 sc in next stitch\* 1 times (3 stitches).\n`
> 3. `Rnd 1: \*hdc in next -1 stitches, 2 hdc in next stitch\* 100 times (100 stitches).\nRnd 2: \*hdc in next 0 stitches, 2 hdc in next stitch\* 100 times (200 stitches).\nRnd 3: \*hdc in next 1 stitches, 2 hdc in next stitch\* 100 times (300 stitches).\nRnd 4: \*hdc in next 2 stitches, 2 hdc in next stitch\* 100 times (400 stitches).\nRnd 5: \*hdc in next 3 stitches, 2 hdc in next stitch\* 100 times (500 stitches).\nRnd 6: \*hdc in next 4 stitches, 2 hdc in next stitch\* 100 times (600 stitches).\n`
> 4. This can error, or not produce any output, or anything. R will always be positive and nonzero.
> 5. This can either error OR produce `Rnd 1: \*tc in next -1 stitches, 2 tc in next stitch\* 0 times (0 stitches).\nRnd 2: \*tc in next 0 stitches, 2 tc in next stitch\* 0 times (0 stitches).\nRnd 3: \*tc in next 1 stitches, 2 tc in next stitch\* 0 times (0 stitches).\nRnd 4: \*tc in next 2 stitches, 2 tc in next stitch\* 0 times (0 stitches).\nRnd 5: \*tc in next 3 stitches, 2 tc in next stitch\* 0 times (0 stitches).`

Suggestions for more test cases welcomed! Please let me know how to improve it. If you have an input/output that produces a pattern you like, add it to your answer and maybe I’ll crochet it when I have time.

Ungolfed solution in Python 2: Try it online

# Answer
> 1 votes
# perl -M5.010 -a, 124 bytes

```
say"Row $_: \\*$F[1] in next ${\($_-2)} stitches, 2 $F[1] in next stitch\\* $F[2] times (${\($_*$F[2])} stitches)."for 1..$_

```

Try it online!

Pretty trivial. The bulk of the program consists of the line which needs to be printed, with some variable interpolation.

# Answer
> 1 votes
# 05AB1E, 62 bytes

```
EN³*³²NÍ²N“ ÿ: \*ÿ€†‚š ÿÀŠ, 2 ÿ€†‚šïŠ\* ÿ„Æ (ÿÀŠ).“'w't:'¢ã™ì,

```

Input in the same order as the challenge description, as three loose inputs \\$r,s,y\\$.

I've used `Row` for the optional first word, although `Round` and `Rnd` could both also be used for the same byte-count, by replacing `'¢ã™` with `'í‰™` or `…Rnd` respectively.

Try it online or verify all test cases.

**Explanation:**

```
E        # Loop `N` in the range [1, (implicit) first input `r`]:
 N³*     #  Push `N` multiplied by the third input `y`
 ³       #  Push the third input `y`
 ²       #  Push the second input `s`
 NÍ      #  Push `N-2`
 ²       #  Push the second input `s` again
 N       #  Push `N`
 “ ÿ: \*ÿ€†‚š ÿÀŠ, 2 ÿ€†‚šïŠ\* ÿÀŠ (ÿ„Æ).“
         #  Push dictionary string " ÿ: \*ÿ in next ÿ switches, 2 ÿ in next switch\* ÿ times (ÿ switches).",
         #  where the `ÿ` are automatically replaced with the values on the stack
  'w't:  #  Replace all "w" with "t" ("switch" to "stitch")
  '¢ã   '#  Push dictionary string "row"
     ™   #  Titlecase it to "Row"
      ì  #  Prepend it in front of the string
       , #  And output it with trailing newline

```

See this 05AB1E tip of mine (section *How to use the dictionary?*) to understand why `“ ÿ: \*ÿ€†‚š ÿÀŠ, 2 ÿ€†‚šïŠ\* ÿ„Æ (ÿÀŠ).“` is `" ÿ: \*ÿ in next ÿ switches, 2 ÿ in next switch\* ÿ times (ÿ switches)."` and `'¢ã` is `"row"`.

# Answer
> 1 votes
# Retina, 132 bytes

```
^\d+
*
Lv^$`(_+) (.+) (.+)
Row $.1: \$*$2 in next $1 stitches, 2 $2 in next stitch\$* $3 times ($.($3*$1) stitches).
__(_*)
$.1
_
-1

```

Try it online! Takes input in the order `r`, `s`, `y`. Explanation:

```
^\d+
*

```

Convert `r` to unary.

```
Lv^$`(_+) (.+) (.+)

```

Count down from `r` to `1`, then reverse the results, and substitute in the output pattern:

```
Row $.1: \$*$2 in next $1 stitches, 2 $2 in next stitch\$* $3 times ($.($3*$1) stitches).

```

`$.1` is the row, `$*` is a literal `*`, `$2` is `s`, `$1` is the row in unary, `$3` is `y`, and `$.($3*$1)` is the product of the row with `y` (in decimal).

```
__(_*)
$.1

```

Subtract 2 from the row for the final substitution.

```
_
-1

```

Fix up the first row.

---
Tags: code-golf
---


title: Scoring Quantum Tic-Tac-Toe

text:
# Question
Title: Scoring Quantum Tic-Tac-Toe
In the description of this challenge, the following board will be used as a reference for positions:

```
ABC
DEF
GHI

```

For instance, in a game of ordinary tic-tac-toe, `B E A C G D F H I` describes the following:

```
-X-   -X-   XX-   XXO   XXO   XXO   XXO   XXO   XXO
---   -O-   -O-   -O-   -O-   OO-   OOX   OOX   OOX
---   ---   ---   ---   X--   X--   X--   XO-   XOX

```

---

# Quantum Tic-Tac-Toe Gameplay

In quantum tic-tac-toe, players' moves are superpositions of moves in classical tic-tac-toe. Players mark two cells per move instead of just one, and those cells become *entangled*. Each quantum mark is given a subscript telling the number of the turn in which it was placed.

In the above board, `A` and `B` are entangled, and so it is said that X made the move `AB`: `X1` is either in `A` or `B` but the true position cannot be known with certainty until later in the game.

Consider the following board, made with the sequence `AB BE DE AE` (X makes the move `AB`, O makes the move `BE`, X makes the move `DE`, O makes the move `AE`; note that the relative positions of quantum marks in a cell in the image do not actually matter):

Here, there has arisen a *cyclic entanglement* between cells `A`, `B` and `E`. Consider the following image, in which a line represents an entanglement:

After a cyclic entanglement (which does not necessarily have length 3) is formed, *measurement* takes place, in which every quantum mark involved in the cycle collapses into a known state and becomes a *classical mark*. This includes entanglements like the red one above that are merely accessories to the cyclic entanglement, and don't actually complete the cycle. After one player forms a cyclic entanglement, the other player chooses which state the board assumes. Since X formed the cyclic entanglement, it is up to O to choose between these two states:

There are only ever two possible states to choose from, because all individual entanglements only involve two cells. To record which state was chosen, the following methodology will be used:

* Find the first cell (i.e. `A` takes precedence over `B`, etc) in the cyclic entanglement which cannot be removed without breaking the cycle (meaning entanglements like the red one above are excluded). In this case this is `A`.
* Write the number of the mark that fills that cell.

Since either `X1` or `O4` will occupy `A`, either `1` or `4` will be written. This would mean the above boards would be described by the sequences `AB BE DE AE 1` and `AB BE DE AE 4`, respectively. After measurement occurs, no more moves can be made in `A`, `B`, `D` or `E` because it is now known what lies in those cells.

A single-cell entanglement, e.g. `AA 1`, is not allowed under ordinary circumstances, as that would mimic the behavior of a classical mark. This sort of move is only allowed when just one cell not occupied by a classical mark remains.

A game continues until at least one tic-tac-toe is formed or until the board is filled with classical marks. Multiple tic-tac-toes can be made only if they appear simultaneously after a measurement; this is because the presence of one or multiple tic-tac-toes disallows the placement of any additional quantum marks.

---

# Scoring

The first number corresponds to X's score and the second to O's.

* If neither player has a tic-tac-toe, then both players get zero points.
* If there is only one tic-tac-toe present, then the player with the tic-tac-toe gets one point and the other player gets zero points.
* If one player gets two tic-tac-toes after a measurement, then they get two points and the other player gets zero. It is not possible for one player to get one tic-tac-toe while the other gets two, nor is it possible for both players to get two, nor one player to get three.
* If both players get a tic-tac-toe after a measurement, then the player with the least maximum subscript in their tic-tac-toe will get one point and the other player will get one half-point.

For clarification on that last point, consider the board made by the sequence `AI EG BE EH DG AI 1 BC CE 3`:

The maximum subscript in X's tic-tac-toe is seven, while the maximum subscript in O's tic-tac-toe is six. Because of this, O has the least maximum subscript and gets one point while X gets one half-point.

---

# The Challenge

Given a series of moves from a game of quantum tic-tac-toe, determine the score of each player.

# Rules

* Input and output may be given in whatever form is most convenient, but it must be explained if it differs from what is described above. Changes can be slight, like describing locations or scores differently, or more drastic. For instance, writing the number of the classical mark that fills the cell of the last quantum mark placed can be done instead of writing the number of the mark that fills the first cell alphabetically.
* One must always be able to tell which score corresponds to which player. For instance, always putting the winner's score first is not acceptable unless the output also tells which player won or lost. If a specific player's score is always given first, that does not have to be included in the output (as seen in the test cases).
* Assume only valid input is given.
* Spaces are not necessary; they were added for the purpose of legibility.
* This is so the smallest program in bytes wins.

---

# Test Cases

```
In: AB
Out: 0 0

In: AI EG BE EH DG AI 1 BC CE 3
Out: 0.5 1

In: IA EG EB EH GD AI 1 CB CE 3
Out: 0.5 1

In: DE AB DE 1 AH CF CH CG BC 2
Out: 1 0.5

In: AE BF EI DH AI 1
Out: 1 0

In: CE BD EG FH CG 1
Out: 1 0

In: AB AD BC CF AC 5
Out: 1 0

In: AB BE BC CE 2 DG HI DF HI 6
Out: 0 1

In: BC BE CF EF 1 AD AG GH DG 6 II 9
Out: 0 0

In: DI AE AB BF EH AH 2 DI 7 CG CG 8
Out: 0 0

In: AD BH EF CI EF 3 HI DG BI 2 AG 1
Out: 2 0

```

# Answer
> 8 votes
# Python 3.8 (pre-release), ~~419~~ ~~371~~ 351 bytes

*-48 bytes following suggestions from @ovs*

*-16 bytes thanks to @JBernardo*

```
def s(C,l=[]):
 l=l+[p:=C.pop(0)]
 if 0==p*0:
  del l[~1];r=[p]
  while r:c=r.pop();l=[r.append(t:=sum(e)-c)or t if e*0!=0and c in e else e for e in l]
 if C:s(C,l)
 else:w=[a:=[sum(z.count(j)>2for z in[*zip(*[[k//3,k%3,k%4,6559>>2*k&3]for k in l[i:f+1:2]if 0==k*0])]for j in set(z))for i in[0,1]]for f in range(9)];a[[1,0]in w]/=1+([1,1]==a);print(a)

```

Try it online!

Takes input with `A-I` translated to `0-8` in tuples. The collapse choice is represented by the cell the last entanglement collapses to.

### Massive Explanation

```
# Take input C
# I(k) <==> move k is a collapse, not entanglement <==> 'imag'in dir(k) <==> isinstance(k,int) <==> hasattr(k,'imag')
# I have a feeling that collapses vs entanglements can be encoded in a much more byte-efficient manner
I=lambda k:'imag'in dir(k)
# C: list of moves, where a pair entry (e.g. [0,1]) is entanglement (e.g 0-1).
# and an int entry (e.g 1) states collapse of the last entry, (e.g. [0,1] collapsed to 1)
# l: be the list of entangled/collapsed states, built up with recursion
# pair (e.g. [0,1]) represents an existing entanglement, and int (e.g. 1) represents collapsed state
# the owners alternate XOXOXO in the list
def s(C,l=[]):
 l=l[:] # clone l for array operations
 if C:  # deal with end condition: only recurse if C has any mvoes
  l+=[  # append the first move in C to l
    p:=C[0] # assign p to be the first move
  ]
  if I(p):  # if that move is an int, collapse:
   del l[~1];   # delete the entangled move before
   r=[p]        # r will be the list of location to remove
                # start by adding p to r: no entanglement can have the location p anymore
   # I have a feeling this whole while loop can be replaced with a recursive method
   while r:     # while there is still a location to remove:
    c=r.pop()   # take c to be the first location, so we will collapse all states that contain c
    for i,e in enumerate(l):    # for each state e of l:
     if (1-I(e)  # If it is not a collapsed state
        and c in e): # and it contains c
         r+=[       # add to r:
            sum(l[i])-c     # the location besides e of c
         ];
         l[i]=r[~0] # replace e with that collapsed location
  s(C[1:],l) # recurse without the first move and with the modified l
 else:  # end condition: all moves have been processed
       # for case 5 (begins [[0, 1], [1, 4]...),
       # l=[0, 1, 2, 4, [3, 6], 7, [3, 5], 8] (most states are collapsed, except for [3,6] and [3,5])
  w=[  # w will be a list, supposing everything is collapsed as soon as it is intered,
       # of how many 3-in-a-rows each player has after each move
    a:=     # this is a for loop, so `a` gets set to the *last* 3-in-a-row count (the final win state)
        [
            sum(    # take the sum of:
                z.count(j)>2    # the number of directions that have exactly 3 (more than 2) identical entries
                    for z in    # for each of the 3 directions (rows, cols, diags) in
                        [*zip(*[    # the transpose:
                                [
                                    k//3, # floor divide maps items on each row to the same value
                                    k%3, # mod 3 maps items in the same column to the same value
                                    k%4 # mod 4 maps items on the main diagonal to 0
                                    6559>>2*k&3 # k on antidiagonal to 0; 0,1,7,8 to negative; 3,5 to 1
                                                    # (k in[2,4,6] doesn't work because it also maps all of 0,1,3,5,7,8 to False)
                                ]
                                for k in l[i:f+1:2] # i=0: every even state; i=1: every odd state
                                                    # states limited to from the first f moves
                                if I(k) # only consider the state if it is collapsed
                            ]
                        )]
                    for j in set(z) # take the count for each unique value in the direction
                )
            for i in[0,1] # do this for both player i=0=X and player i=1=O)
        ]
    for f in range(9)   # for each count f of moves from 0 moves to 8 moves, calculate the 3-in-a-row count
  ]
  # now a should be [0,0],[1,0],[2,0],[1,1] or the opposite order
  if[1,1]==a:   # [1,1] is the only case we have to special handle
    a[[1,0]in w]*=.5    # subtract .5 from the second element (O's score) if X got the point first, otherwise subtract from X's score
  print(a)  # finally

```

---
Tags: code-golf, graph-theory, tic-tac-toe
---


# Question
Title: What's the missing column/row? (GCJ 2016-1A rankfile)
There is an `N x N` square of numbers.

* All columns increase strictly monotonically from top to down
* All rows increase strictly monotonically from left to right
* There is exactly one valid answer for each input.

You are given `2N-1` rows of `N` numbers representing rows or columns in this square. The task is to find the row that isn't in the input.

**Your Task**
Write a program or function that outputs the row or column that isn't in the input.

**Input**

First, you get the number `N`.
Then follow `2N-1` lines of `N` space-separated numbers, representing rows or columns of this `N x N` square. The lines are given in left-to-right or top-down order. There may be multiple equal lines. It is ok to omit the initial `N` from the input, or modify the input format as you like.

```
3
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3

```

**Output**

Your program or function should output a single line of `N` numbers; the row or column from the square that was not present in the input. You may change the output format as you please.

```
3 4 6

```

This would correspond to one of two squares:

```
1 2 3     1 2 3
2 3 4     2 3 5
3 5 6     3 4 6

```

Either way, the output is the same.

**Bonus**

Your solution should be able to calculate `2 ≤ N ≤ 10` within a minute on a normal computer. If your solution handles the big input, `2 ≤ N ≤ 50`, within a minute, you get `-10%` byte count.

**Test cases**

```
2
22 222
2 22
22 222
-> 2 22

3
1 2 3
2 3 5
3 5 6
2 3 4
1 2 3
-> 3 4 6

4
11 14 16 22
3 6 9 11
6 7 11 14
9 11 15 19
10 11 19 22
6 7 10 11
3 6 8 10
-> 8 10 15 16

```

Note that you can simply change what line in these inputs that is omitted, and reorder them in any way you want, to generate new test cases.

This is a simplified version of Google Code Jam 2016 round 1A problem B: Rank and File. The original Google Code Jam problem, where you can get more test cases (but without answers), is available here: https://code.google.com/codejam/contest/4304486/dashboard#s=p1

# Answer
> 6 votes
# CJam, 5 - 10% = 4.5

This is an unnamed function (block) that takes an array of arrays and returns an array:

```
{:^$}

```

(With some inspiration from Dennis)

Try it online

And here is the code I actually submitted at GCJ (24 bytes):

```
li2*({l~}*]$e`{(2%*~}%S*

```

Try it online

**Explanation:**

This basically lists the values that appear an odd number of times.

```
:^    reduce by symmetric difference; pairs of duplicate values "cancel" each other
$     sort the resulting array

```

# Answer
> 5 votes
# Jelly, 3.6 bytes

```
œ^/Ṣ

```

The source code is **4 bytes** long and qualifies for the **-10% bonus**. Try it online!

### How it works

Since there are **2N** rows/columns in total, each number must appear **2N** times. Therefore, it suffices to take the numbers that appear in an odd number of the **2N - 1** rows/columns from input.

```
œ^/Ṣ  Main link. Argument: A (2D list of integers)

  /   Reduce the rows by...
œ^    symmetric multiset difference.
   Ṣ  Sort the result.

```

# Answer
> 1 votes
# JavaScript (ES6), 179 bytes

```
f=(n,a,p=[],o)=>(p[n-1]?p.every((_,j)=>~(a.map(v=>v+"").indexOf((m=p.map((_,k)=>p.map(r=>r[k]))[j])+""))?1:o=!o&&m):a.map((c,i)=>o=o||f(n,x=a.slice(),p.concat(x.splice(i,1)))))&&o

```

## Explanation

Whew! That took quite a bit of effort to do without any combinatorics built-ins...

Possibly qualifies for the bonus. I haven't tested with `n = 50`.

The entire function is a recursive permutation function. It takes the size `n` and input array `a`, then moves each item individually from `a` to the current permutation array `p`. `p` becomes every permutation of *rows*.

Once the length of `p` becomes `n`, it transposes `p` to get an array of the columns. It searches these columns for each item in `a`.

Because `a` should contain all these columns except one if this is the correct result, output the column in the transposed `p` which is missing from `a` if there is only one column missing.

```
f=(n,a,p=[],o)=>(
  p[n-1]?                                        // once p is a square
    p.every((_,j)=>                              // find each column in the transposed square a,
                                                 //     a is missing a column so one should fail
      ~(a.map(v=>v+"")                           // convert column arrays to strings so we can use indexOf
        .indexOf(                                // search for current column
          (m=p.map((_,k)=>p.map(r=>r[k]))[j])+"" // transpose p to match a
        )
      )?1:o=!o&&m                                // if there is only one column missing from a, o = missing column
    )
  :a.map((c,i)=>                                 // add each row to the permutation
    o=o||                                        // set o to first found result
    f(n,x=a.slice(),p.concat(x.splice(i,1)))     // get next permutation
  )
)&&o                                             // return o

// Test
var testCases = [[
    2, [
      [22,222],
      [2,22],
      [22,222]
    ]
  ], [
    3, [
      [1,2,3],
      [2,3,5],
      [3,5,6],
      [2,3,4],
      [1,2,3]
    ]
  ], [
    4, [
      [11,14,16,22],
      [3,6,9,11],
      [6,7,11,14],
      [9,11,15,19],
      [10,11,19,22],
      [6,7,10,11],
      [3,6,8,10]
    ]
]];
document.write("<pre>"+testCases.map(c=>f(c[0],c[1])).join`\n`);
```

# Answer
> 1 votes
# Pyth, ~~13~~ ~~12~~ ~~11~~ 9 x 0.9 = 8.1 bytes

```
S{f%/QT2Q

```

Flattened list as input.

Try it online!

### previous 11-byte solution

```
M-+GH@GHSgF

```

Uses Dennis' algorithm.

### previous 12-byte solution:

```
S{f%/.nQT2.n

```

Try it online!

## alternative 13 byte solution:

```
eCf%hT2rS.nQ8

```

Try it online!

# Answer
> 1 votes
# Julia, 19.8 bytes

```
x->sort(symdiff(x...))

```

The source code is **22 bytes** long and qualifies for the **-10% bonus**. Try it online!

# Answer
> 1 votes
## JavaScript (Firefox 30-57), 62 bytes

```
(a,s=[])=>[for(b of a)for(c of b)s[c]^=c]&&[for(c of s)if(c)c]

```

Only works for positive integers. 64 bytes to work with zero too:

```
(a,s=[])=>[for(b of a)for(c of b)s[c]^=~c]&&[for(c of s)if(c)~c]

```

101 bytes to work with arbitrary floating-point numbers:

```
(a,m=new Map)=>[for(b of a)for(c of b)m.set(c,!m.get(c))]&&[for(b of m)if(b[1])b[0]].sort((a,b)=>a-b)

```

109 bytes to work with strings instead:

```
(a,m=new Map)=>[for(b of a)for(c of b)m.set(c,!m.get(c))]&&[for(b of m)if(b[1])b[0]].sort((a,b)=>(a>b)-(a<b))

```

# Answer
> 0 votes
# GolfScript, 5 - 10% = 4.5 bytes

Port of the CJam answer - reduce by symdiff, sort.

```
{^}*$

```

Try it online!

---
Tags: code-golf
---