# Question
Title: Detect what programming language a snippet is
Your challenge is to take some source code as input, and output which programming language it is written in.

For example, you could have the input

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

```

And output

```
Java

```

Your two main goals are **diversity** (how many programming languages you can detect) and **accuracy** (how good you are at detecting these languages).

For polyglots (programs valid in more than one language), you can decide what to do. You could just output the language that your program thinks is more likely, or you could output an error, or you could output an array of possible choices (which would probably get more upvotes than just an error!).

This is a , because it would be very difficult to specify a different objective winning criterion. Voters, please vote on how many languages it can detect and how accurate it is.

# Answer
# 234 text formats - Unix Shell

(not all of them languages - I need to count them carefully)

```
file $1

```

I hesitate to post this somewhat smart-a$$ answer, but I don't see anything in the rules banning it and the `file` shell utility really does do a good job of this. e.g:

```
$ file golfscript.rb
golfscript.rb: Ruby module source, ASCII text
$ file template.c
template.c: ASCII C program text
$ file adams.sh
adams.sh: Bourne-Again shell script, ASCII text executable
$

```

Furthermore you can use the `-k` option to "keep going" when testing a polyglot:

```
 -k, --keep-going
         Don't stop at the first match, keep going.  Subsequent matches
         will be have the string ‘\012- ’ prepended.  (If you want a new‐
         line, see the -r option.)

```

Also, the `-l` option will give you an idea of how good the algorithm is for differing languages:

```
$ file -l | grep shell
unknown, 0: Warning: using regular magic file `/etc/magic'
Strength = 280 : shell archive text [application/octet-stream]
Strength = 250 : Tenex C shell script text executable [text/x-shellscript]
Strength = 250 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 240 : Paul Falstad's zsh script text executable [text/x-shellscript]
Strength = 240 : Neil Brown's ash script text executable [text/x-shellscript]
Strength = 230 : Neil Brown's ae script text executable [text/x-shellscript]
Strength = 210 : Tenex C shell script text executable [text/x-shellscript]
Strength = 210 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 190 : Tenex C shell script text executable [text/x-shellscript]
Strength = 190 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 180 : Paul Falstad's zsh script text executable [text/x-shellscript]
Strength = 150 : Tenex C shell script text executable [text/x-shellscript]
Strength = 150 : Bourne-Again shell script text executable [text/x-shellscript]
Strength = 140 : C shell script text executable [text/x-shellscript]
Strength = 140 : Korn shell script text executable [text/x-shellscript]
Strength = 140 : Paul Falstad's zsh script text executable [text/x-shellscript]
Strength = 130 : POSIX shell script text executable [text/x-shellscript]
Strength = 130 : Plan 9 rc shell script text executable []
$

```

This is `file-5.09` (on Ubuntu 12.04)
> 21 votes

# Answer
# 18 programming languages, 1002 bytes, accuracy: test for yourself :)

(yep I know this is not code golf, but for the fun of it)

The program searches for iconic code snippets, the checks are ordered in a way that the most clear checks are at the top and programming languages embedded in other programming languages are below (e.g. HTML in PHP).

This obviously fails for programs like `System.out.println('<?php');`

```
t = (p) ->
    h = (x) -> -1 != p.indexOf x
    s = (x) -> 0 == p.indexOf x

    if h "⍵" then "APL"
    else if h "<?php" then "PHP"
    else if h("<?xml") and h "<html" then "XHTML"
    else if h "<html" then "HTML"
    else if h "<?xml" then "XML"
    else if h("jQuery") or h "document.get" then "JavaScript"
    else if h "def __init__(self" then "Python"
    else if h "\\documentclass" then "TeX"
    else if h("java.") or h "public class" then "Java"
    else if s("SELE") or s("UPDATE") or s "DELE" then "SQL"
    else if /[-\+\.,\[\]\>\<]{9}/.test p then "Brainfuck"
    else if h "NSString" then "Objective-C"
    else if h "do |" then "Ruby"
    else if h("prototype") or h "$(" then "JavaScript"
    else if h "(defun" then "Common Lisp"
    else if /::\s*[a-z]+\s*->/i.test p then "Haskell"
    else if h "using System" then "C#"
    else if h "#include"
        if h("iostream") or h "using namespace" then "C++"
        else "C"
    else "???"

program = ""
process.stdin.on 'data', (chunk) -> program += chunk
process.stdin.on 'end', -> console.log t program

```

Usage on node: `coffee timwolla.coffee < Example.java`

Demo (Online-Demo on JSFiddle):

```
[timwolla@~/workspace/js]coffee puzzle.coffee < ../c/nginx/src/core/nginx.c
C
[timwolla@~/workspace/js]coffee puzzle.coffee < ../ruby/github-services/lib/service.rb
Ruby
[timwolla@~/workspace/js]coffee puzzle.coffee < ../python/seafile/python/seaserv/api.py
Python

```
> 10 votes

# Answer
# Bash — about ~~50~~ 35 bytes per compilable language

Trick is to just compile, then you don't have to worry about linking errors from missing libraries, and it's more forgiving if you just have code snippets.

Thanks to Shahbaz for shorter forms!

```
gcc -c $1 && (echo C; exit 0)
g++ -c $1 && (echo C++; exit 0)
gpc -c $1 && (echo Pascal; exit 0)
gfortran -c $1 && (echo Fortran; exit 0)

```

etc...
> 10 votes

# Answer
# Just a few broad generalizations.

I think it's fairly accurate.

This is Ruby btw. Takes (multiline) input from stdin.

```
puts case $<.read
when /\)\)\)\)\)/
  "Lisp"
when /}\s+}\s+}\s+}/
  "Java"
when /<>/
  "Perl"
when /|\w+|/
  "Ruby"
when /\w+ :- \w+ \./
  "Prolog"
when /^[+-<>\[\],.]+$/
  "brainfuck"
when /\[\[.*\]\]/
  "Bash"
when /~]\.{,/
  "golfscript"
end

```
> 6 votes

# Answer
This answer is a proof of concept, that will not likely receive any more work from myself.

It falls short in several ways:

* The output is not exactly as the question requests, but close enough and could easily be modified to produce the exact output required.
* There are several ways to make the code perform better and/or better ways to represent the data structures.
* and more

The idea is to set a list of keywords/characters/phrases that can identify a specific language and assign a score to that keyword for each language. Then check the source file(s) for these keywords, and tally up the scores for each language that you find keywords for. In the end the language with the highest score is the likely winner. This also caters for polyglot programs as both (or all) the relevant languages will score high.

The only thing to add more languages is to identify their "signatures" and add them to the mapping.

You can also assign different scores to different keywords per language. For example, if you feel `volatile` is used more in Java than in C, set the score for `volatile` keyword to 2 for Java and 1 for C.

```
public class SourceTest {

  public static void main(String[] args) {
    if (args.length < 1) {
      System.out.println("No file provided.");
      System.exit(0);
    }
    SourceTest sourceTest = new SourceTest();
    for (String fileName : args) {
      try {
        sourceTest.checkFile(fileName);
      } catch (FileNotFoundException e) {
        System.out.println(fileName + " : not found.");
      } catch (IOException e) {
        System.out.println(fileName + " : could not read");
      }
    }
    System.exit(0);
  }

  private Map<String, LanguagePoints> keyWordPoints;
  private Map<LANGUAGES, Integer> scores;

  private enum LANGUAGES {
    C, HTML, JAVA;
  }

  public SourceTest() {
    init();
  }

  public void checkFile(String fileName) throws FileNotFoundException, IOException {
    String fileContent = getFileContent(fileName);
    testFile(fileContent);
    printResults(fileName);
  }

  private void printResults(String fileName) {
    System.out.println(fileName);
    for (LANGUAGES lang : scores.keySet()) {
      System.out.println("\t" + lang + "\t" + scores.get(lang));
    }
  }

  private void testFile(String fileContent) {
    for (String key : keyWordPoints.keySet()) {
      if (fileContent.indexOf(key) != -1) {
        for (LANGUAGES lang : keyWordPoints.get(key).keySet()) {
          scores.put(lang, scores.get(lang) == null ? new Integer(1) : scores.get(lang) + 1);
        }
      }
    }
  }

  private String getFileContent(String fileName) throws FileNotFoundException, IOException {
    File file = new File(fileName);
    FileReader fr = new FileReader(file);// Using 1.6 so no Files
    BufferedReader br = new BufferedReader(fr);
    StringBuilder fileContent = new StringBuilder();
    String line = br.readLine();
    while (line != null) {
      fileContent.append(line);
      line = br.readLine();
    }
    return fileContent.toString();
  }

  private void init() {
    scores = new HashMap<LANGUAGES, Integer>();

    keyWordPoints = new HashMap<String, LanguagePoints>();
    keyWordPoints.put("public class", new LanguagePoints().add(LANGUAGES.JAVA, 1));
    keyWordPoints.put("public static void main", new LanguagePoints().add(LANGUAGES.JAVA, 1));
    keyWordPoints.put("<html", new LanguagePoints().add(LANGUAGES.HTML, 1));
    keyWordPoints.put("<body", new LanguagePoints().add(LANGUAGES.HTML, 1));
    keyWordPoints.put("cout", new LanguagePoints().add(LANGUAGES.C, 1));
    keyWordPoints.put("#include", new LanguagePoints().add(LANGUAGES.C, 1));
    keyWordPoints.put("volatile", new LanguagePoints().add(LANGUAGES.JAVA, 1).add(LANGUAGES.C, 1));
  }

  private class LanguagePoints extends HashMap<LANGUAGES, Integer> {
    public LanguagePoints add(LANGUAGES l, Integer i) {
      this.put(l, i);
      return this;
    }
  }
}

```
> 6 votes

# Answer
# Javascript - 6 languages - high accuracy

Current Languages: Java, C, HTML, PHP, CSS, Javascript

I work on the principle that whenever an input satisfies a criteria, it is given a score, and based on that score results are given.

### Features:

* No built-in functions that determine language type used.
* Does not straightaway declare the input text is `x` language on seeing a keyword.
* Suggests other probable languages also.

Should you feel that any of your inputs of the programs (that I have done till now) are not caught or get invalid results, then please report and I'd be happy to fix them.

### Sample Input 1:

```
class A{public static void main(String[]a){System.out.println("<?php");}}

```

### Sample Output 1:

```
My program thinks you have :
Java with a chance of 100%
Php with a chance of 25%
----------------

```

### Explanation:

This should have failed the program and I would have printed `PHP`, but since my program works on the basis of scores, nothing fails and it easily identifies Java in the first place, followed by other possible results.

### Sample Input 2:

```
class A{public static void main(String[]a){System.out.println("HelloWorld!");}}

```

### Sample Output 2:

```
Java
----------------

```

### Sample Input 3:

```
ABCDEFGHIJKLMNOPQRSTUVWXYZ

```

### Sample Output 3:

```
Language not catched! Sorry.
----------------

```

### The code:

```
// Helper functions

String.prototype.m = function(condition){
  return this.match(condition);
};

String.prototype.capitalize = function(){
  return this[0].toUpperCase() + this.substr(1);
};

function getFuncName(func){
  var temp =  func.toString();
  temp = temp.substr( "function ".length);
  temp = temp.substr( 0, temp.indexOf("("));
  return temp.capitalize();
}

// Get input
var lang_input = prompt("Enter programming language");

// Max score of 4 per lang

function java(input){
  var score = 0;
  score += input.m(/class[\s\n]+[\w$]+[\s\n]*\{/) ? 1 : 0;
  score += input.m(/public[\s\n]+static[\s\n]+void[\s\n]+main[\s\n]*/) ? 1 : 0;
  score += input.m(/\}[\s\n]*\}[\s\n]*$/) ? 1 : 0;
  score += input.m(/System[\s\n]*[.][\s\n]*out/) ? 1 : 0;
  return score;
}

function c(input){
  var score = 0;
  // if java has passsed
  if(checks[0][1] >= 3)return 0;

  score += input.m(/^#include\s+<[\w.]+>\s*\n/) ? 1 : 0;
  score += input.m(/main[\s\n]*\([\s\n]*(void)?[\s\n]*\)[\s\n]*\{/) ? 1 : 0;
  score += input.m(/printf[\s\n]+\(/) || input.m(/%d/) ? 1 : 0;
  score += input.m(/#include\s+<[\w.]+>\s*\n/) || input.m(/(%c|%f|%s)/) ? 1 : 0;
  return score;
}

function PHP(input){
  var score = 0;
  score += input.m(/<\?php/) ? 1 : 0;
  score += input.m(/\?>/) ? 1 : 0;
  score += input.m(/echo/) ? 1 : 0;
  score += input.m(/$[\w]+\s*=\s*/) ? 1 : 0;
  return score;
}

function HTML(input){
  var score = 0;
  // if php has passed
  if(checks[2][1] >= 2) return 0;

  score += input.m(/<!DOCTYPE ["' \w:\/\/]*>/) ? 1 : 0;
  score += input.m(/<html>/) && input.m(/<\/html>/) ? 1 : 0;
  score += input.m(/<body>/) && input.m(/<\/body/) ? 1 :  0;
  score += input.m(/<head>/) && input.m(/<\/head>/) ? 1 : 0;
  return score;
}

function javascript(input){
  var score = 0;
  score += input.m(/console[\s\n]*[.][\s\n]*log[\s\n*]\(/) ? 1 : 0;
  score += input.m(/[\s\n]*var[\s\n]+/) ? 1 : 0;
  score += input.m(/[\s\n]*function[\s\n]+[\w]+[\s\n]+\(/) ? 1 : 0;
  score += input.m(/document[\s\n]*[.]/) ||
           ( input.m(/\/\*/) && input.m(/\*\//) ) ||
           ( input.m(/\/\/.*\n/) )? 1 : 0;
  return score;
}

function CSS(input){
  var score = 0;
  score += input.m(/[a-zA-Z]+[\s\n]*\{[\w\n]*[a-zA-Z\-]+[\s\n]*:/) ? 1 : 0;
  // since color is more common, I give it a separate place
  score += input.m(/color/) ? 1 : 0;
  score += input.m(/height/) || input.m(/width/) ? 1 : 0;
  score += input.m(/#[a-zA-Z]+[\s\n]*\{[\w\n]*[a-zA-Z\-]+[\s\n]*:/) ||
           input.m(/[.][a-zA-Z]+[\s\n]*\{[\w\n]*[a-zA-Z\-]+[\s\n]*:/) ||
           ( input.m(/\/\*/) && input.m(/\*\//) ) ? 1 : 0;
  return score;
}

// [Langs to check, scores]
var checks = [[java, 0], [c, 0], [PHP, 0], [HTML, 0], [javascript, 0], [CSS, 0]];
//Their scores

// Assign scores
for(var i = 0; i < checks.length; i++){
  var func = checks[i][0];
  checks[i][1] = func(lang_input);
}

// Sort the scores
checks.sort(function(a,b){ return b[1] - a[1]; });

var all_zero = true;

function check_all_zero(index){
  if(checks[index][1] > 0){ all_zero = false; return 0; } // someone is above zero

  // check next index only if it defined, else return zero
  if(checks[index + 1])
    check_all_zero(index + 1);
}

check_all_zero(0);

if(all_zero){
  console.log("Language not catched! Sorry.");
}else {
  var new_arr = [];                   // temp

  checks.map(function(value, index){
    if(value[1] > 0){
      var temp = [getFuncName(value[0]), value[1]];
      new_arr.push(temp);
    }
  });

  checks = new_arr.slice(0);          // array copy, because of mutation

  if(checks.length === 1){
    console.log(checks[0][0]);
  }else{
    console.log("My program thinks you have :");
    checks.map(function(value){
      var prob = (value[1]/4 * 100);
      console.log(value[0] + " with a chance of " + prob + "%");
    });
  }

} // Main else block finish

console.log("----------------");

```
> 3 votes

# Answer
# Python, 4 languages, can you test how accurate this is?

Sorry, but you need to put the source code in a file.

```
import sys

file = sys.argv[1]

def detect(code: str):

    python_keys = {"#": 1, "print": 2, "def": 5, "with": 5, "in": 2, "tuple": 5, ":": 1.5, "except":5, "str": 1.5, "complex": 4, "_": 2, "match": 3}
    javascript_keys = {"{": 3, "function": 4, "=>": 5, "catch": 2.5, "switch": 2, "var": 5, "let": 5, "const": 5, "//": 2}
    c_keys = {"#include": 5, "#pragma once": 5, "#ifdef": 4.5, "#ifndef": 4.5, "*": 2, "size_t": 3, "{": 4, "struct": 5, "switch": 2, "//": 2}
    html_keys = {"<!--": 5, "<!DOCTYPE":5, "html": 5, "href": 5, ".css": 4, "</": 3, "http": 3}

    langs = ["Python", "JavaScript", "C", "HTML"]
    scores = {lang: 0 for lang in langs}

    for lang in langs:
        score = 0

        for key, value in eval(f"{lang.lower()}_keys").items():
            score += value * code.count(key)

        scores[lang] = score

    return scores

with open(file) as file:
    results = detect(file.read())

if "-l" in sys.argv:
    summed = sum(results.values())
    for lang, score in results.items():
        print(f"{lang}: {100 * score / summed}% likely")
else:
    max_score = max(results.values())
    print(*filter(lambda lang: results[lang] == max_score, results.keys()), sep=", ")

```

This can also receive the `-l` flag to list how likely each language is.

Here is it checking itself with the `-l` flag enabled (on powershell, current directory hidden for obvious reasons):

```
>py langdetect.py langdetect.py -l
Python: 49.022346368715084% likely
JavaScript: 18.01675977653631% likely
C: 23.18435754189944% likely
HTML: 9.776536312849162% likely

```
> 1 votes

---
Tags: popularity-contest
---


title: Is it a Mersenne Prime?

text:
# Question
Title: Is it a Mersenne Prime?
> A number is a *Mersenne Prime* if it is both prime and can be written in the form **2n-1**, where **n** is a positive integer.

Your task is to, given any positive integer, determine whether or not it is a Mersenne prime. You may submit either a function which returns a truthy/falsy value, or a full program which performs IO.

### Rules:

* As this is , you should aim to do this in the **shortest byte count possible.** Builtins are allowed.
* Standard golfing loopholes apply - you cannot read the Mersenne primes from external files, or hardcode them into your program.
* Your program should work for values within your language's standard integer size.

---

### Test Cases

For reference, a list of (known) Mersenne Primes can be found **here**. Some handy test cases are:

```
2  -> False
1  -> False
20 -> False
51 -> False
63 -> False

3    -> True
31   -> True
8191 -> True

```

---

*Merry Christmas, everybody! Have a great holiday, whatever you celebrate :)*

# Answer
> 20 votes
# Jelly, 5 bytes

```
&‘<ÆP

```

Try it online!

### How it works

```
&‘<ÆP  Main link. Argument: x

 ‘     Yield x+1.
&      Take the bitwise AND of x and x+1.
       This yields 0 iff x is a Mersenne number, i.e., iff x+1 is a power of 2.
   ÆP  Yield 1 if x is a prime, 0 if not.
  <    Compare the results to both sides,
       This yields 1 iff x is both a Mersenne number and a prime.

```

# Answer
> 25 votes
# 05AB1E, 5 bytes

A positive number in the form **2n \- 1** in binary only consists of **1's**.

Code:

```
b`¹pP

```

Explanation:

```
b`      # Push each digit of the binary representation of the number onto the stack
  ¹p    # Check if the input is prime
    P   # Take the product of all these digits

```

Uses the **CP-1252** encoding. Try it online! or Verify all test cases.

# Answer
> 11 votes
# Python, 45 bytes

```
lambda n:-~n&n<all(n%i for i in range(2,n))<n

```

Try it online!

### How it works

The three terms of the chained comparison

```
-~n&n<all(n%i for i in range(2,n))<n

```

do the following:

* `-~n&n` computes the bitwise AND of **n + 1** and **n**. Since **n** consists solely of **1** bits if it is a Mersenne number, the bitwise AND will return **0** if (and only if) this is the case.
* `all(n%i for i in range(2,n))` returns *True* if and only if **n mod i** is non-zero for all values of **i** in **\[2, …, n - 1\]**, i.e., if and only if **n** has no positive divisors apart from **1** and **n**.

In other words, *all* returns *True* if and only if **n** is a composite number, i.e., **n** is either **1** or a prime.
* `n` is self-explanatory.

The chained comparison returns *True* if and only if the individual comparisons do the same.

* Since *all* returns either *True*/**1** or *False*/**0**, `-~n&n<all(n%i for i in range(2,n))` can only return *True* if `-~n&n` yields **0** (i.e., if **n** is a Mersenne number) and *all* returns *True* (i.e., if **n** either **1** or a prime).
* The comparison `all(n%i for i in range(2,n))<n` holds whenever **n \> 1**, but since *all* returns *True* if **n = 1**, it does not hold in this case.

# Answer
> 8 votes
# Brachylog, 7 bytes

```
#p+~^h2

```

Try it online!

A Brachylog program is basically a sequence of constraints which form a chain: the first constraint is between the input and an anonymous unknown (let's call it *A* for the purpose of this discussion), the second constraint is between that anonymous unknown and a second anonymous unknown (which we'll call *B*), and so on. As such, the program breaks down like this:

```
#p      Input = A, and is prime
+       B = A + 1
~^      B = X to the power Y, C = the list [X, Y]
h       D = the head of list C (= X)
2       D = 2

```

The only way all these constraints can be satisfied simultaneously is if B is a power of 2, i.e. the input is a power of 2 minus 1, and the input is also prime. (Brachylog uses a constraint solver internally, so the program won't be as inefficient as the evaluation order looks; it'll be aware that `C` is of the form `[2, Y]` before it tries to express `B` as the exponentiation of two numbers.)

Interestingly, `#p+~^` *almost* works, because Mersenne-like primes can only use 2 as the base in non-degenerate cases (proof), but a) it fails for non-Mersenne primes *B*-1 as they can be expressed as *B*¹, and b) the existing Brachylog interpreter seems to be confused (going into an infinite, or at least long-duration, loop) by a program that's that poorly constrained. So 7 bytes seems unlikely to be beaten in Brachylog.

# Answer
> 7 votes
## Mathematica, 29 26 bytes

*Edit: Saved 3 bytes thanks to Martin Ender*

`PrimeQ@#&&IntegerQ@Log2[#+1]&`

```
PrimeQ@#&&1>BitAnd[#,#+1]&

```

I suspect this would be faster since the first 42 exponents are hard-coded:

```
MersennePrimeExponentQ@Log2[#+1]&

```

# Answer
> 7 votes
## Mathematica 26 Bytes

```
PerfectNumberQ[# (#+1)/2]&

```

See this proof

Works so long as there are no odd perfect numbers, and none are known to exist.

# Answer
> 5 votes
# Perl 6, 29 bytes

```
{.base(2)~~/^1*$/&&.is-prime}

```

Try it

## Expanded:

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

  .base(2)    # is its binary representation ( implicit method call on ｢$_｣ )
   ~~
  /^ 1* $/    # made entirely of ｢1｣s

  &&          # and

  .is-prime   # is it prime

}

```

since Perl 6 has arbitrarily large Ints, it doesn't pad the front of `.base(2)` with `0`s.

# Answer
> 5 votes
## Python, ~~83~~ ~~82~~ ~~79~~ ~~76~~ 73 bytes

```
def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

```

## Python 2, 71 bytes

```
def f(m):
 s,n=(m!=3)*4,m/4
 while-~m&m<n:s,n=(s*s-2)%m,n/2
 return s<1

```

This function implements the Lucas–Lehmer primality test, so while it isn't as short as some of the other Python offerings it's *much* faster at handling huge inputs.

---

Here's some test code that runs on Python 2 or Python 3.

```
from __future__ import print_function

def primes(n):
    """ Return a list of primes < n """
    # From http://stackoverflow.com/a/3035188/4014959
    sieve = [True] * (n//2)
    for i in range(3, int(n**0.5) + 1, 2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n - i*i - 1) // (2*i) + 1)
    return [2] + [2*i + 1 for i in range(1, n//2) if sieve[i]]

def lucas_lehmer_old(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = (s * s - 2) % m
    return s == 0 and m or 0

# much faster
def lucas_lehmer(p):
    m = (1 << p) - 1
    s = 4
    for i in range(p - 2):
        s = s * s - 2
        while s > m:
            s = (s & m) + (s >> p)
    return s == 0 or s == m and m or 0

def f(m):
 s,n=(m!=3)*4,m>>2
 while-~m&m<n:s,n=(s*s-2)%m,n>>1
 return s<1

# Make a list of some Mersenne primes
a = [3]
for p in primes(608):
    m = lucas_lehmer(p)
    if m:
        print(p, m)
        a.append(m)
print()

# Test that `f` works on all the numbers in `a`
print(all(map(f, a)))

# Test `f` on numbers that may not be Mersenne primes
for i in range(1, 525000):
    u = f(i)
    v = i in a
    if u or v:
        print(i, u, v)
    if u != v:
        print('Error:', i, u, v)

```

**output**

```
3 7
5 31
7 127
13 8191
17 131071
19 524287
31 2147483647
61 2305843009213693951
89 618970019642690137449562111
107 162259276829213363391578010288127
127 170141183460469231731687303715884105727
521 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
607 531137992816767098689588206552468627329593117727031923199444138200403559860852242739162502265229285668889329486246501015346579337652707239409519978766587351943831270835393219031728127

True
3 True True
7 True True
31 True True
127 True True
8191 True True
131071 True True
524287 True True

```

FWIW, here's a slightly more efficient version of `f` that doesn't re-test `m` on every loop:

```
def f(m):
 s,n=m!=3and 4,m>>2
 if-~m&m<1:
  while n:
   s=(s*s-2)%m
   n>>=1
 return s<1

```

# Answer
> 4 votes
# R, ~~41~~ 40 bytes

```
matlab::isprime(x<-scan())&!log2(x+1)%%1

```

Oddly enough the builtin in R `mersenne` takes `n` as argument, not `2^n-1`.

This takes `x` from STDIN, checks if it is prime using the `matlab` package and checks if the 2-log of `x+1` is a whole number by taking mod 1 and checking for 'not zero-ness'.

Also, if you use the `mersenne` builtin, it ends up being slightly shorter, but feels like cheating:

```
numbers::mersenne(log2(scan()+1))

```

Saved 1 byte thanks to @Billywob

# Answer
> 2 votes
## Pyke, 10 bytes

```
_PQb2+}\1q

```

Try it here!

```
_P         -    is_prime(input)
     +     -   ^ + V
  Qb2      -    base_2(input)
      }    -  uniquify(^)
       \1q - ^ == "1"

```

# Answer
> 2 votes
# Actually, 9 bytes

```
;├╔'1=@p*

```

Try it online!

Explanation:

Since every number of the form 2n-1 has all 1's in its binary representation, a Mersenne prime can be identified as a prime number with that quality.

```
;├╔'1=@p*
 ├╔'1=     only unique binary digit is 1
        *  and
;     @p   is prime

```

# Answer
> 2 votes
## Jelly, 5 bytes

Alternate approach to @Dennis' existing 5-byte Jelly answer:

```
B;ÆPP

```

Try it online!

How it works:

```
B      Returns the binary representation of the input as a list [1, 0, 1, 1, ...]
 ;     And attach to this list
  ÆP   a 1 if the input is a prime, 0 otherwise
    P  Calculates the product of this list of 1's and 0's

```

Since a Mersenne Prime is one less than a power of 2, its binary representation is excusively 1's. The output therefor is 1 for Mersenne primes, and 0 in all other cases .

# Answer
> 2 votes
# Ceylon, 66 bytes

```
Boolean m(Integer c)=>c>2&&c.and(c+1)<1&&!(2:c-2).any((d)=>c%d<1);

```

Formatted (and commented):

```
// Check whether a (positive integer) number is a mersenne prime number.
//
// Question:  http://codegolf.stackexchange.com/q/104508/2338
// My Answer: http://codegolf.stackexchange.com/a/104805/2338

Boolean m(Integer c) =>
        // check whether c+1 is a power of two
        c.and(c+1)<1 &&
        // the standard primality check by trial division
         !(2 : c-2).any((d) => c%d < 1) &&
        // we need to exclude 1, which is unfortunately
        // matched by both criteria above, but is no prime.
        c>1;

```

---

With cheating (hardcoding the results in the range of Ceylon's Integer), we can get a byte shorter (65):

```
Boolean h(Integer c) =>
        c.and(c+1)<1 && #20000000800a20ac.and(c+1)>0;

```

(It looks like the syntax highlighter misunderstands Ceylon's hex numerals as start-of-comment.)

If an anonymous function is okay, this one is 49 bytes:

```
[2,3,5,7,13,17,19,31,61].map((p)=>2^p-1).contains

```

# Answer
> 2 votes
# Regex (ECMAScript), ~~42~~ 31 bytes

`^(?!(xx+)\1+$)(x(x*)(?=\3$))+x$`

```
^
(?!(xx+)\1+$)      # Assert that N is prime or 0 or 1.
(x(x*)(?=\3$))+x$  # Assert that N is a power of 2 minus 1 and is >= 3.
                   # The >=3 part of this prevents the match of 0 and 1.

```

Try it online!

Edit: Down to 31 bytes thanks to Neil.

The basic "is a power of 2 minus 1" test is `^(x(x*)(?=\2$))*$`. This works by looping the operation "subtract 1, then divide evenly by 2" until it can be done no further, then asserting that the result is zero. This can be modified to match only numbers ≥1 by changing the last `*` to a `+`, forcing the loop to iterate at least once. Inserting an `x` before the last `$` further modifies it to match only numbers ≥3 by asserting that the final result after looping at least once is 1.

The related "is a power of 2" test is `^((x+)(?=\2$))*x$`. There is also a shorthand for matching powers of 2 minus 2, discovered by Grimmy: `^((x+)(?=\2$)x)*$`. All three of these regexes are of the same length.

Alternative 31 byte version, by Grimmy:

`^(?!(xx+)\1+$|((xx)+)(\2x)*$)xx`

Try it online!

```
# Match Mersenne primes in the domain ^x*$
^                   # N = input number
(?!                 # "(?!p|q)" is equivalent to "(?!p)(?!q)"; evaluate the
                    # logical AND of the following negative lookaheads:
    (xx+)\1+$       # Assert that N is prime or 0 or 1
|
    ((xx)+)(\2x)*$  # Assert that N is a power of 2 minus 1; this is based
                    # on "(?!(x(xx)+)\1*$)" which matches powers of 2.
)
xx                  # Assert that N >= 2, to prevent the unwanted match of
                    # 0 and 1 by both of the negative lookahead statements.

```

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

```
PrimeQ[BitAnd[#,#+2]#]&

```

Try it online!

1 is handled correctly because `PrimeQ[BitAnd[1,1+2]*1] == PrimeQ@1 == False`. Otherwise, for `BitAnd[#,#+2]#` to be prime, we need that `#` is prime and `BitAnd[#,#+2] == 1`, which happens when `#` is a Mersenne number.

# Answer
> 2 votes
# Regex (ECMAScript), 29 bytes

```
^(?!(xx+|(x(x))+)(\1\3)+$)xxx

```

Try it online!

Inspired by Grimy in chat

The regex asserts that the input is greater than 3, and that it is neither of the form: `(xx+)\1+` or `((xx)+)(\1x)+`.

The first matches composite numbers.
The second matches a number that is 1 less than a multiple of some odd number greater than 2.

The first will **not** match prime numbers, or `0` or `1`.
The second will **not** match numbers of the form \\$2^n-1\\$, or numbers that are 1 less than an odd prime.

Since 2 is the only prime that is 1 less than an odd prime, the negative lookahead, together with the assertion that the input is greater than 3, will match only mersenne primes.

# Answer
> 1 votes
## Ruby, 47 bytes

```
->b{!("%b"%(b/2)=~/0/||(2...b).find{|a|b%a<1})}

```

# Answer
> 1 votes
# Python 3, 68 bytes

```
a=int(input());print(a&-~a<1and a>1and all(a%b for b in range(2,a)))

```

Try it here

# Python 2, 63 bytes

```
a=input();print(a&-~a<1)and a>1and all(a%b for b in range(2,a))

```

Try it here

---

Thanks for suggestion Jonathan

---

Open to any suggestions for reducing the bytecount.

# Answer
> 1 votes
# Julia, 26 bytes

```
n->isprime(n)&&ispow2(n+1)

```

# Answer
> 1 votes
# Python, 65 bytes

```
f=lambda n,i=3:(n^i)-all(n%i for i in range(2,n))<0 or f(n,-~i|i)

```

Outputs via Exit Code. Recursion Error for False. No error for True.

**How it works**

Since `2^n-1` in binary is made entirely from 1's, the next `2^n-1` number can be generated by `number|number+1`.

This function uses this by recursively going through each `2^n-1`number checking to see if it's a prime number and eqaul to the input. If the number is not a mersenne prime, python will eventually throw an error as the maximum recursion depth would have been exceeded.

# Answer
> 1 votes
# Pushy, 7 bytes

```
oBoIpP#

```

**Try it online!**

This takes advantage of the fact that mersenne numbers have only ones in their binary representation:

```
oB      \ Pop input, push its binary digits.
  oI    \ Re-push the input
    p   \ Test its primality (0/1)
     P# \ Print the product of the stack

```

The stack product will only be `1` if the number has no zeroes in its binary representation, and its primality is `True`.

# Answer
> 1 votes
# Pyth, 8 bytes

```
&.AjQ2P_

```

**Verify all the test cases.**

# Pyth, 8 bytes

```
<.&QhQP_

```

**Verify all the test cases.**

---

# How?

### Code Breakdown #1

```
&.AjQ2P_    Full program with implicit input.

      P_    Is Prime?
   jQ2      Convert the input to binary as a list of digits.
 .A         All the elements are truthy (i.e. all are 1).
&           Logical AND.
            Output implicitly.

```

### How does that work?

A number of the form ***2n \- 1*** always contains ***1*** only when written in binary. Hence, we test if all its binary digits are ***1*** and if it is prime.

### Code Breakdown #2

```
<.&QhQP_    Full program with implicit input.

      P_    Is Prime?
    hQ      Input + 1.
 .&Q        Bitwise AND between the input and ^.
<           Is smaller than? I.e. The bitwise AND results in 0 and the primality test results in 1.
            Output implicitly.

```

### How does that work?

This tests if the ***input + 1*** is a power of two (i.e. if it is a Mersenne number), and then performs the primality test. In Python, `bool` is a subclass of `int`, so truthy is treated as ***1*** and falsy is treated as ***0***. To avoid checking explicitly that one is ***0*** and the other is ***1***, we compare their values using `<` (since we only have 1 such case).

# Answer
> 1 votes
# Java 8, ~~53~~ ~~52~~ 49 bytes

```
n->{int i=1;for(;n%++i>0;);return(n&n+1|i^n)==0;}

```

Bug-fixed and golfed by 4 bytes thanks to *@Nevay*.

**Explanation:**

Try it here.

```
n->{                // Method with integer parameter and boolean return-type
  int i=1;          //  Temp integer `i`, starting at 1
  for(;n%++i>0;);   //  Loop and increase `i` as long as `n` is divisible by `i`
  return(n&n+1|i^n) //  Then return if `n` bitwise-AND `n+1` bitwise-OR `i` bitwise-XOR `n`
          ==0;      //  is exactly 0
}                   // End of method

```

# Answer
> 1 votes
# Japt, 6 bytes

```
¢¬×&Uj

```

Run it or Run all test cases

# Answer
> 1 votes
# Prolog (SWI), 48 bytes

```
Y+X:-X=<Y;X mod Y>0,Y+1+X.
\X:-X>1,2+X,X+1/\X<1.

```

Try it online!

-7 thanks to Jo King

# Answer
> 1 votes
# Vyxal, 6 bytes

```
æ[›¨²c

```

Try it Online!

If N is prime, check if `n+1` is a power of 2.

# Vyxal, 5 bytes

```
æ⁰bJΠ

```

Try it Online!

Port of the Jelly 5 byte answer.

# Answer
> 0 votes
# Python, 93 Bytes

```
def f(a):
 for b in range(a):
  if(a+1==2**b and not[i for i in range(2,a)if a%i<1]):return 1

```

This code would work in both Python 2 and Python 3 so I have not specified a version.

# Answer
> 0 votes
## Racket 76 bytes

```
(define(g m)(for/or((i m))(= m(-(expt 2 i)1))))(if(and(prime? n)(g n))#t #f)

```

Ungolfed:

```
(require math)
(define(f n)
  (define (ispowerminus1 m)
    (for/or ((i m))
      (= m (-(expt 2 i)1))))
  (if (and (prime? n)
           (ispowerminus1 n))
      #t #f))

```

Testing:

```
(f 1)
(f 2)
(f 20)
(f 51)
(f 63)
(f 3)
(f 31)
(f 8191)

```

Output:

```
#f
#f
#f
#f
#f
#t
#t
#t

```

# Answer
> 0 votes
# PHP, 53 bytes

```
for($i=$n=$argv[1];--$i&&$n%$i;);echo!($i-1|$n+1&$n);

```

takes command line argument; prints `1` for Mersenne prime, empty string else. Run with `-r`.

**breakdown**

```
for($i=$n=$argv[1];--$i&&$n%$i;);   // loop $i down from $n-1 until $i divides $n
                        // If $n is prime, loop ends with $i=1. ($n=1 -> $i=0)
echo!($i-1|$n+1&$n);    // If $i!=1, $n is not prime. If ($n+1&$n)>0, $n is not Mersenne.
                        // If either $i-1 or $n+1&$n is truthy, the negation will be false.

```

# Answer
> 0 votes
# C, 94 bytes

```
g(n,i){return--i?g(2*n,i):n;}n,r;f(x){for(n=r=1;++n<x;)r=x%n?x^g(2,n)-1?r:r|2:r&2;return r>2;}

```

Returns 1 if the number is a Mersenne Prime, 0 otherwise.

# Answer
> 0 votes
## Scala, 59 Bytes

```
def f(t:BigInt)=t.isProbablePrime(t.bitLength*9)&(1+t)%2==0

```

This function requires the input to be a `BigInt`. You can easily convert a string "162259276829213363391578010288127" (2\**107-1 is a Mersenne prime) into `BigInt` by doing `BigInt("162259276829213363391578010288127")`. It might go wrong as the name of `isProbablePrime()` method suggests. But the probability is not more than `0.5^(t.bigLength)*9`.

Standalone script version is 72 bytes long.

```
val t=BigInt(args(0));print(t.isProbablePrime(t.bitLength*9)&(1+t)%2==0)

```

Assume we save it as "t.scala", then then program can be run as

```
>scala t.scala 162259276829213363391578010288127
>true

```

# Answer
> 0 votes
# Perl 5, 53 bytes

52 bytes of code + 1 for `-p`

```
$f=0|sqrt;1while$_%$f--;$_=!$f*(sprintf'%b',$_)!~/0/

```

Try it online!

# Answer
> 0 votes
# J, 16 bytes

`*./(#:,1&=@#@q:)`

This solution consists of a fork and then a reduce, returns a 1 if true and 0 if false.

The left side of the fork `#:` returns the binary expansion of the input; the right side `1&=@#@q:` produces the prime factors, then tests whether the resulting array contains only a single item (so, whether or not the input is prime). Finally, the middle part of the fork `,` contains the two results. The result of the fork is reduced with the and operator (`*.`). Since the 1 less a power of two's binary expansion will only contain ones, we can pretend the binary expansion is actually an array of booleans.

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

```
n=>!(n&n+1||(g=(m,q)=>m>3?g(m>>1,(q*q-2)%n):n-3&&q)(n,4))

```

Try it online! Implements Lucas-Lehmer primality test. Works for `n<2**26.5`

(FINALLY NATIVE BIGINT SUPPORT IN JS IN 2018. HAIL V8)

For arbitrarily sized integers, try `n=>!(n&n+1n||(g=(m,q)=>m>3n?g(m/2n,(q*q-2n)%n):n-3n&&q)(n,4n))` for 62 bytes. Only works in Chrome 67+ and Node.js 10.4.1+ because of BigInt support. Have a try on 2\**4423-1!

# Answer
> 0 votes
# APL (Dyalog Classic), 21 bytes

```
1∧.=1∘≠,2∘⊥⍣¯1,¯1↓⊢∨⍳

```

Verify test cases

### Explanation:

Similar method to others here. Prime test + binary representation of Mersenne number being all 1s.

* `¯1↓⊢∨⍳` is a prime test. The length of the result depends on the size of the number but if the number is prime every element of the result list will be 1. (the exception is 1 which annoyingly returns empty list) Catenated with `,` to....
* `2∘⊥⍣¯1` is the easiest way to encode into binary in Dyalog, by inverting the decode-from-binary operation (yeah i know right), catenated to.....
* `1∘≠` which is there to catch the corner case that the above tests can't tell that 1 isn't a Mersenne prime. (Prime test returns empty list, binary encode results in 1, so result of concatenations contains only 1s)
* If the list resulting from the above operations contains only 1s, the result is a Mersenne prime. `1∧.=` checks that all elements are 1.

# Answer
> 0 votes
# APL(NARS), chars 20, bytes 40

```
{0π⍵×∧/⍵⊤⍨2⍴⍨1+⌊2⍟⍵}

```

0π return true \[1\] if its argument is prime else return false \[0\], test:

```
  f←{0π⍵×∧/⍵⊤⍨2⍴⍨1+⌊2⍟⍵}
  f¨2 1 20 51 63
0 0 0 0 0
  f¨3 31 8191
1 1 1

```

# Answer
> 0 votes
# Husk, 8 bytes

```
§&o£İ2→ṗ

```

Try it online!

# Answer
> 0 votes
# Thunno 2 `M`, 3 bytes

```
P×ḃ

```

Try it online!

#### Explanation

```
     # Implicit input

P    # Is the input prime?
     #   i.e.  1 if it's prime,
     #         0 otherwise

 ×   # Multiply by the input
     #   i.e.  (input) if it's prime,
     #         0 otherwise

  ḃ  # Convert to binary
     #   i.e.  a string of 1s if it's a Mersenne prime,
     #         a string including 0s if it's prime but not a Mersenne prime
     #         0 if it's not prime

     #   i.e   a string of 1s if it's a Mersenne prime,
     #         a string including 0s if it's not a Mersenne prime

     # M flag - take the minimum
     #   i.e.  1 if it's a Mersenne prime
     #         0 otherwise

     # Implicit output

```

---
Tags: code-golf, number-theory, primes, decision-problem, integer
---


title: Making a coin fair

text:
# Question
Title: Making a coin fair
You have a coin that produces `0` or `1`. But you suspect the coin may be *biased*, meaning that the probability of `0` (or `1`) is not necessarily 1/2.

A well known procedure to "transform" a biased coin into a *fair coin* (i.e. to obtain equally likely results), as proposed by von Neumann, is as follows. Produce (non-overlapping) blocks of two coin tosses until the two values of a block differ; and output the first value in that block (the second value would also do, but for the purposes of this challenge we choose the first). Intuitively, `1` may be more likely than `0`, but `01` and `10` will be equally likely.

For example, the input `1110...` would discard the first block, then produce a `1` from the second block, ...

This procedure is *expensive*, because several coin tosses are consumed to generate a single result.

### The challenge

Take a finite sequence of zeros and ones, representing tosses of the original coin, and produce the *maximum number of results* according to the above procedure, until all the input is consumed.

The last block may be incomplete, if the number of input values is odd. For example, the input sequence `11111` would produce no result (the first two blocks have equal values, and the third block is incomplete).

### Rules

The input can have any non-negative number of values, not necessarily positive or even.

The input format may be:

* an array of zeros and ones;
* a string of zeros and ones with an optional separator.

Output format may be:

* a string of zeros and ones, with or without separators;
* an array of zeros and ones;
* strings containing a single zero or one, separated by newlines;
* any similar, reasonable format that suits your language.

Code golf. Fewest bytes wins.

### Test cases

Input and output are here assumed to be strings.

```
Input         -->  Output

'1110'        -->  '1'
'11000110'    -->  '01'
'1100011'     -->  '0'
'00'          -->  ''
'1'           -->  ''
''            -->  ''
'1101001'     -->  '0'
'1011101010'  -->  '1111'

```

# Answer
# Jelly, 6 bytes

```
s2Q€Ṗ€

```

Try it online!

### How it works

```
s2Q€Ṗ€  Main link. Argument: S (string)

s2      Split the string into pairs of characters.
  Q€    Deduplicate each pair.
        This removes the second character iff it is equal to the first.
    Ṗ€  Pop each; remove the last character of each pair/singleton.

```
> 7 votes

# Answer
## Retina, ~~16~~ 14 bytes

```
(.)\1|(.)?.
$2

```

Try it online!

### Explanation

This is fairly simple. The code defines a single regex substitution replacing all (non-overlapping) matches of `(.)\1|(.)?.` with whatever the second group captured. This combines three different cases into one:

```
(.)\1 --> <empty>

```

If two repeated digits are equal, we remove them from the string (because group 2 is unused).

```
(.).  --> $2

```

Otherwise, if we can match two characters, remove the second one, by replacing both of them with the first. If that's not the case the `?` will omit the group:

```
.     --> <empty>

```

This only happens if there is an unpaired trailing character, which is also removed.
> 14 votes

# Answer
## Labyrinth, ~~21~~ 12 bytes

```
"(. :
""*$,@

```

~~A rare example of a compact Labyrinth program that also has no no-ops.~~ The `|` in the previous version was completely unnecessary, and removing it massively reduced the size of the program. In fact, Lab's beating Retina!

Try it online!

The bottom-left `"` can also be a space, but having it there greatly simplifies the explanation.

## Explanation

This one's a little trickier, so it's accompanied by images. But first, a quick primer:

* Labyrinth is a stack-based 2D language. Memory consists of a main stack and an auxiliary stack.
* Labyrinth's stacks are bottomless and filled with zeroes, so performing operations on an empty stack is not an error.
* At each junction, where there are two or more paths for the instruction pointer to go, the top of the main stack is checked to figure out where to go next. Negative is turn left, zero is straight ahead and positive is turn right. If a turn fails, the pointer tries to turn in the other direction.

### Setup

The program starts at the top-left `"`, which is a no-op. Then we perform:

```
(        Decrement a bottom zero to -1. Since -1 is negative we try to turn
         left at this junction, fail, and turn right instead.
"        No-op junction, turn left
*        Multiply top of stack (-1) with a 0 at bottom of stack, giving 0.
         This makes us go straight ahead at this junction.
$        Bitwise xor (of 0 and 0)

```

This leaves the stack with a single 0 on it, which is as good as empty for the purposes of Labyrinth.

### Reading input and termination

`,` reads a char from input, returning 48 or 49 for `0` or `1` respectively, and -1 on EOF. Since this is nonzero, either way we turn into the `:`, which duplicates the top of the stack.

The `:` is at a dead-end, so we turn around and execute `,` once more. Now if the last input was EOF, then we turn left and terminate with `@`, else we turn right, with the stack looking like `[a a b]` (where `a`, `b` are the two chars).

### Interpreting the coin toss

If we didn't terminate, our next move is to execute `$` (bitwise xor) again. This yields 0 if the input chars were the same, 1 otherwise. We then multiply `a` with this result, giving either 0 or `a`. Since the `*` is at a junction, this top stack value determines what happens next.

In the 0 case, we go straight ahead and execute three `"` no-ops, before perform a `(` decrement. Like the setup, this makes us turn and execute `"*$`, leaving us ready to read more chars.

Otherwise, in the `a` case, we turn right at the junction since `a` is positive (48 or 49). `.` outputs the char, leaving the stack empty, and `(` decrements the top of the stack, turning a 0 to -1. Once again, this makes us turn left, executing `"*$` like in the setup, also leaving us ready to read more input.
> 11 votes

# Answer
## CJam, ~~10~~ 8 bytes

```
l2/{)-}%

```

Test it here.

### Explanation

This is a very simple solution: in each pair, remove all instances of the last character. Repeated digits and unpaired trailing digits will be removed, as will be the second digit in any pair of unequal digits:

```
"0"  --> ""
"1"  --> ""
"00" --> ""
"01" --> "0"
"10" --> "1"
"11" --> ""

```

This leaves only the digits we're looking for. Here's how the code computes this:

```
l     e# Read input.
2/    e# Split into pairs. Odd inputs will yield a single-character string at the end.
{     e# Map this block over the pairs...
  )   e#   Pull the last character off the string.
  -   e#   Remove all occurrences of that character from the remainder (which is either
      e#   an empty string to begin with or a single-digit string).
}%

```

When the list is auto-printed at the end of the program, the empty strings are simply omitted.
> 8 votes

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

@Martin Büttner Retina solution inspired a 2 byte gain

Includes +1 for `-p`

Run with the input on STDIN, e.g. `perl -p fair.pl <<< 11000110`

`fair.pl`:

```
s/(.)\1|.?\K.//g

```

Not much to explain here since it is an (indirect) translation of the specification:

* `(.)\1` If the first 2 digits are the same, drop them
* `.\K.` Otherwise the first two digits are different. Keep (`\K`) the first one
* `.?\K.` Except that the first `.` is optional. This allows for a single match at the end of the string which then gets discarded since the kept part is empty
> 7 votes

# Answer
## Haskell, ~~71~~ ~~44~~ 29 bytes

```
p(a:b:r)=[a|a/=b]++p r
p _=[]

```

Extreme golfing by nimi.
> 5 votes

# Answer
# Mathematica, 36  ~~38~~  bytes

-2 after stealing @LegionMammal978's function for determining if a 2-element list is {0,1} or {1,0}

```
#&@@@Select[#~Partition~2,Tr@#==1&]&

```

Argument is expected to be a list of integers.
> 5 votes

# Answer
## Hexagony, ~~23~~ 21 bytes

```
,){,/;(_\/'%<\{)/>~$>

```

Unfolded:

```
    , ) { ,
   / ; ( _ \
  / ' % < \ {
 ) / > ~ $ > .
  . . . . . .
   . . . . .
    . . . .

```

This terminates with an error, but the error message goes to STDERR.

Try it online!

Judging by the number of mirrors it might be just about possible to fit it into side-length 3 but I've had no luck so far.

### Explanation

Here's the usual diagram, generated with Timwi's HexagonyColorer:

The program uses only three memory edges, labelled **A**, **B**, and **C** here (diagram courtesy of Timwi's EsotericIDE):

Execution starts on blue path. The `/` are just mirrors that redirect the instruction pointer (IP), the actual code is:

```
,   Read character from STDIN into memory edge A.
)   Increment.
{   Move to memory edge B.
,   Read character from STDIN into memory edge B.
)   Increment.
'   Move to memory edge C.
%   Compute A mod B in memory edge C.

```

The `,` will set the edge to `-1` instead of the character code if we've hit EOF. Since we're incrementing both inputs that doesn't change whether they are equal or not, but it turns EOF into `0`.

We use modulo to check for equality, because it's either `1` or `49` (positive) for unequal characters and `0` for equal characters. It also serves as the end of the program, because when we have the `0` from EOF, the attempted division by zero will cause an error.

Now the `<` distinguishes zeroes from positive results. The simple one first: if the characters are equal, the IP takes the red path. `_` is a mirror, `\` is also a mirror but gets ignored, and `>` deflects the IP such that it wraps around the edges and starts from the top again. However, on this iteration, the roles of **A**, **B** and **C** are swapped cyclically (**C** now takes the role of **A** and so on).

If the characters are different, the green path is taken instead. This one's a bit messier. It first jumps over a no-op with `$`, then wraps around to the `/` on the left edge, then traverses the second-to-last row from right to left and finally re-enters the interesting part of the source code at the `{`. There's an essentially linear bit of code, that I'll explain in a second, before the `$` makes the IP jump over the `>` to merge the two paths again.

Here is that linear piece of code:

```
{    Move to memory edge A.
(    Decrement to recover the actual character we read.
;    Print the character back to STDOUT.
'    Move to memory edge B.
~    Multiply the value there by -1, making it negative. This is
     necessary to ensure that the path correctly wraps back to the top.

```

Note that in this case, the roles of the edges for the next iteration are also swapped cyclically, but with **B** taking the role of **A** and so on.
> 5 votes

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

```
i:i:0(?;-?o

```

\>\<\> is pretty well suited to read-a-char-at-a-time challenges like this :) Try it online!

```
i:            Read char and duplicate
i             Read char
:0(?;         Halt if last char was EOF
-             Subtract
?o            Output first char if the subtraction was non-zero (i.e. not equal)

```

This all happens in a loop since the instruction pointer wraps around once it reaches the end of a line.
> 4 votes

# Answer
# JavaScript (ES6), 33 bytes

```
s=>s.filter((c,i)=>++i%2&c!=s[i])

```

### How it works

```
s=>s                // Take the input array.
.filter((c,i)=>   ) // Filter to only the chars that are both:
++i%2&              //  on an even index, and
c!=s[i]             //  not equal to the one after them.

```
> 3 votes

# Answer
## Perl, ~~27~~ 21 bytes

```
say grep$_-chop,/../g

```

Byte added for the `-n` flag.

```
                /../g  match groups of two chars
    grep       ,       select/filter on...
           chop        remove the last character, mutating the string
        $_-            is it different than the remaining char?
                         (subtract it, empty string is falsy)
say                    output if so

```

Test:

```
llama@llama:~$ perl -nE 'say grep$_-chop,/../g'
1110
1
11000110
01
1100011
0
00

1

1101001
0
1011101010
1111

```

Thanks to @TonHospel for 6 bytes!
> 3 votes

# Answer
## Python, 42 bytes

```
f=lambda L:L[1:]and L[:L[0]^L[1]]+f(L[2:])

```

Fun with recursion and bitwise xor. Takes a list of 1s and 0s as input.
> 3 votes

# Answer
## Prelude, 12 bytes

```
11(-(#!)?^?)

```

This assumes an interpreter that reads and prints characters. You can sort of try it online. But that interpreter prints integers, so for each `0` you'll get `48` and for each `1` you'll get `49` instead (and a linefeed).

### Explanation

It's very rare that you can write a non-trivial program on a single line in Prelude (because Prelude needs more than one line to be Turing-complete).

```
11      Push two 1s. We need something non-zero on the stack to enter the loop, and by
        pushing the same value twice, we make sure that the loop doesn't print anything
        on the first iteration.
(       Main loop...
  -       Subtract the last two values. This will be zero for equal values, and non-zero
          otherwise...
  (       This "loop" is simply used as a conditional: if the last two values were
          were equal, skip the code inside...
    #       Discard the conditional.
    !       Print the value below.
  )       The loop is exited because the value below is always zero.
  ?       Read the first character of the next pair from STDIN.
  ^       Duplicate it, so the lower copy can be printed.
  ?       Read the second character of the pair. This returns 0 at EOF, which
          terminates the loop.
)

```
> 3 votes

# Answer
## Befunge 93, 16 bytes

```
~:~:0`!#@_->#,_$

```

A one-liner for compactness. Tested using this online interpreter.

```
~:                     Read input char a and dup
  ~                    Read input char b (-1 on EOF)
   :0`!                Push 1 if b <= 0, 0 otherwise
       #@_             Halt if b <= 0 (i.e. EOF)
          -            Subtract to check whether a != b
           >#,_$       Output a if so

```

The last part makes use of the fact that popping from an empty Befunge-93 stack yields 0.

If `a != b`, we perform

```
>                      Move rightward
#                      Bridge: skip next
_                      Horizontal if - go right if 0, else left. But a != b, so we go left
,                      Output a
#                      Bridge: skip next
-                      Subtract (0 - 0 = 0)
_                      If: go right since 0 is popped
>#                     Go right and skip next
_                      If: go right since 0 is popped
$                      Pop top of stack, stack is now empty

```

Otherwise, if `a == b`, we perform:

```
>                      Move rightward
#                      Bridge: skip next
_                      If: go right since a == b (i.e. a-b is 0)
$                      Pop top of stack and discard, keeping stack empty

```
> 3 votes

# Answer
# brainfuck, 33 bytes

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

```

Compared to Java, this is very compact, however, I'm afraid of brainfuck-golfer answerer. And feel free to mention if there's a bug. Assuming EOF is 0, input doesn't contain invalid input, the cell is initially zero, and the cell value range is finite and cyclic. No other assumption is present.

Explanation:

Memory Cell Map

```
+---------+---------+-----------------+
|1st input|2nd input|copy of 1st input|
+---------+---------+-----------------+

```

Instruction

```
,>,                               read two instruction at once | first to first cell |
                                  second to second cell
   [                              Until the input is EOF
    <                             look at first cell
     [->->+<<]                    move the first cell to additional cells while
                                  subtracting the second cell with this at same
                                  time
              >[                  if the second cell is nonzero (it means that first cell and
                                  the second cell is the same)
                [-]>.<            Print the copied first input
                      ]
                       >[-]       clear the first input to prevent it polluting next input
                           <<,>,  continue with next two input
                                ]

```
> 3 votes

# Answer
# Jelly, 4 bytes

```
ḟ2/ḟ

```

Try it online!

Full program, but the link still runs all test cases, since they still get the smash-print treatment.

```
 2/     Split the input into slices of length 2, then reduce each slice by
ḟ       remove elements of right from left.
        This produces a list of empty lists and singleton lists,
        except if the length of the input is odd the last element is entirely unaffected.
   ḟ    Remove elements of the input from that result.
        This removes the odd element if there is one, and nothing else,
        since it is necessarily an element of the input, and everything else is a list.

```
> 3 votes

# Answer
# MATL, ~~11~~ ~~9~~ 8 bytes

```
`-?6MD]T

```

Input and output are numbers separated by newlines. Ends with an error (allowed by default) when all inputs have been consumed.

**Try it online!**

```
`         % do...while loop
  -       %   take two inputs implicitly. Compute difference
  ?       %   if nonzero
    6M    %     push first of the two most recent inputs again
    D     %     display (and remove from stack)
  ]       %   end if
  T       %   true. Used as loop condition, so the loop is infinite
          % end loop implicitly

```

## Old approach, 11 bytes

```
2YCd9L)Xz0<

```

Input is a string. Output is numbers separated by newlines.

Try it online!

```
2YC      % implicitly take input as a string. Generate 2D array of length-2
         % overlapping blocks as columns, padding with a zero if needed.
d        % difference of the two values in each column of that array
9L       % predefined literal [1 2 0]. This corresponds to "1:2:end" indexing
)        % keep only values at indices 1, 3, 5, ... This reduces the set of blocks
         % to non-overlapping, and discards the last (padded) block if the input had
         % odd length
Xz       % keep only nonzero entries, corresponding to blocks that had different values
0<       % 1 if negative, 0 if possitive. Implicitly display

```
> 2 votes

# Answer
## Pyth, ~~10~~ 9 bytes

```
jkPM{Mcz2

```

Algorithm shamelessly stolen from Dennis's Jelly answer.

```
       z    input
      c 2   chunks of 2
    {M      dedup each chunk
  PM        all-but-last element of each chunk
jk          join on empty string; can't use `s' because that gives `0' for []

```
> 2 votes

# Answer
## Python 2, 48 bytes

```
lambda n:[s for s,t in zip(*[iter(n)]*2)if s!=t]

```

Try it online

Thanks to Dennis and vaultah for pointing out stuff that I missed
> 2 votes

# Answer
## sed, ~~34~~ 33 bytes

```
s/../& /g;s/00\|11//g;s/.\b\| //g

```

Test:

```
llama@llama:~$ sed 's/../& /g;s/00\|11//g;s/.\b\| //g'
1110
1
11000110
01
1100011
0
00

1

1101001
0
1011101010
1111

```
> 2 votes

# Answer
# Mathematica, ~~41~~ 39 bytes

```
Select[#~Partition~2,Tr@#==1&][[1]]&

```

Less complicated and shorter than the other answer. The box is a transpose character.
> 2 votes

# Answer
## Labyrinth, 31 bytes

Not as short and neat as Sp3000's solution, but I thought I'd post this anyway as a different approach:

```
"" @
,, :{"
)  { $;
*"})";.
 ""

```

### Explanation

The first loop is simply

```
""
,,

```

which reads in two characters at a time (the `"` are no-ops). After EOF, `,` will return `-1`, but only check for EOF at every second character. That means in any case the top of the stack will then be `-1` and the value below is either `-1` or some character code that we don't care about, because it's an unpaired coin toss.

Then `)*` turns the `-1` and the value below into a single `0` which we need a) to get rid of those two values and b) to enter the next loop correctly. That next loop is simply

```
"}
""

```

Which shifts all the values over to the auxiliary stack. This is necessary because we want to start processing the pairs that we read first. Now the final loop:

```
:{"
{ $;
)";.

```

The `)` just increments some dummy value to ensure that it's positive and the instruction pointer turns north. `{` pulls over the first digit of the next pair and `:` duplicates it. Now when we're done processing, this will have been a `0` from the bottom of the auxiliary stack. Otherwise it's either `48` or `49`. In case of a zero, we exit the loop and terminate on `@`, otherwise, the IP turns east.

`{` pulls over the other digit of the current pair. `$` takes the XOR between them. If that is 0, i.e. the two are equal, the IP just continues moving south, `;` discards the zero, and the IP turns west into the next iteration. If the XOR was `1`, i.e. they were different, the IP turns west, discards the `1` with `;` and prints the first digit with `.`.
> 2 votes

# Answer
## JavaScript (ES6), 33 bytes

```
s=>s.replace(/(.)\1|(.)?./g,"$2")

```

Boring port of the Retina answer.
> 2 votes

# Answer
# str, 11 bytes

```
gd0H=N~e>*x

```

Try it online!

Alternative 11 byte solution: `dgdb=Nue>*x`

If we didn't have to handle the edge case of an unpaired toss (i.e., the input was always even), then the solution would be 5 bytes: `dg=Nx`.

## Explanation

str iterates implicitly over each character of the input. However, since it does not consume all the input at once, we can iterate over *pairs* of characters by manually taking the second character as input with `g`. Let `c1` be the first character and `c2` be the second.

```
gd0H=N~e>*x      stack: [c1]
g                stack: [c1, c2]
 d               stack: [c1, c2, c2] - duplicate
  0H             stack: [c1, c2, c2, c1] - get the first member of the stack
    =            stack: [c1, c2, (c2==c1)] - equality
     N           stack: [c1, c2, (c2!=c1)] - negate (inequality)
      ~          stack: [c1, (c2!=c1), c2] - swap top 2
       e         stack: [c1, (c2!=c1), c2, ``] - push empty string
        >        stack: [c1, (c2!=c1), c2>``] - test for end of input
         *       stack: [c1, Q] - Q is, if the two characters don't match
                                  AND we didn't read past the input
          x      stack: [c1 x Q] - c1 repeated once if Q, zero times if not

```
> 2 votes

# Answer
# Mathematica, 41 bytes

```
Cases[#~Partition~2,a_/;Tr@a==1:>a[[1]]]&

```

Anonymous function that inputs and outputs lists of zeros and ones.
> 1 votes

# Answer
# Pyth, 10 bytes

```
hMf!qFTcz2

```

Test suite
> 1 votes

# Answer
# C, 66 bytes

```
main(char*p,char**x){for(p=x[1];*p&p[1];p+=2)write(1,p,*p^p[1]);}

```

Assuming `sizeof(int) == sizeof(char *)`

# "clever" solution - ~~84~~ 81 bytes

```
main(int c,short**x){while(!((c=*x[1]++-12336)&~511))c>>8^c&1&&putchar(48|c&1);}

```

Works on little-endian machine assuming `short` is 2 bytes. Input is passed as argument. The program iterates over pairs of characters and prints 0 for 0x3130 and 1 for 0x3031. On big-endian the result will be reversed (replace `48|c&1` with `49^c&1` to fix this).
> 1 votes

# Answer
# DOS/Windows Batch, ~~201~~ 162 bytes

```
@echo off
set/pi=
:a
for /f "tokens=2" %%a in ("%i%") do goto l
exit/b
:l
for /f "tokens=1,2" %%a in ("%i:~0,4%") do if %%a neq %%b echo %%a
set "i=%i:~4%"
goto a

```

Input is a space seperated string, for example `1 0 0 1 1`. Start from cmd, otherwise the screen exits immediately
> 1 votes

# Answer
# C, 57 bytes

```
f(char*p,char*r){for(;*p*p[1];)*r=*p++,r+=*r!=*p++;*r=0;}

```

We tentatively copy a character from input `p` to result `r`, but only advance the `r` pointer if it differs from the next character. If not, then we'll overwrite it at the next unmatched pair, or with `NUL` at the end.

## Test program:

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int argc, char **argv) {
    while (*++argv) {
        char *result = malloc(1+strlen(*argv));
        f(*argv, result);
        printf("%s => %s\n", *argv, result);
        free(result);
    }
    return EXIT_SUCCESS;
}

```

## Test output:

```
$ ./74864 1110 11000110 1100011 00 1 "" 1101001 1011101010
1110 => 1
11000110 => 01
1100011 => 0
00 =>
1 =>
 =>
1101001 => 0
1011101010 => 1111

```
> 1 votes

# Answer
# Befunge-93, 40 bytes

```
v  ,-1<
      | -<
>~1+:~1+:|
^     <  @

```

You can try it here. Paste code in the space under the "show" button, press "show", define input, press "run". Our use the "step" button to see how the program works.
> 1 votes

# Answer
# Ruby, 46 bytes

This separates `l[0]`, `l[1]` and `l[2..{end}]` as `a`, `b` and `c`. Then it creates a string with `a` if `a!=b` or `''` otherwise and `f[c]` if `c[0]` exists or `''` otherwise.

```
f=->l{a,b,*c=l;"#{a!=b ?a:''}#{c[0]?f[c]:''}"}

```

**Ungolfed:**

```
def f(l)
  a = l[0]
  b = l[1]
  c = l[2..l.length]
  s = ''
  if a!=b
    s += a.to_s
  end
  if c[0]       # equivalent to !c.empty?
    s += f[c]   # no .to_s because the output will be a string
  end
  puts s
end

```
> 1 votes

# Answer
# beeswax, ~~45~~ 35 bytes

I could golf it down by 10 bytes—not too bad.

```
pgy~1z;L?gAF1<<?V_
>&?@yg&?~@ KQd{b

```

I took the *reading a full string of coin tosses approach*, which makes the program pretty large. Just reading single integers one by one would make the program smaller—maybe around 22 bytes or so—but also very inconvenient to use.

Examples:

```
julia> beeswax("FairCoin.bswx")
s1110
1
Program finished!

julia> beeswax("FairCoin.bswx")
s11000110
01
Program finished!

julia> beeswax("FairCoin.bswx")
s1100011
0
Program finished!

julia> beeswax("FairCoin.bswx")
s00

Program finished!

julia> beeswax("FairCoin.bswx")
s10101001010111111100000010011001110100010110101110100001011
1110001010000111100
Program finished!

```

My beeswax GitHub repository.

My beeswax examples on Rosetta Code.
> 1 votes

# Answer
# Thunno 2, 4 bytes

```
²ıUṫ

```

Try it online!

Port of Dennis's Jelly answer.

#### Explanation

```
²ıUṫ  # Implicit input
²     # Split into pairs
 ı    # Map over this list:
  U   #  Uniquify the pair
   ṫ  #  Remove the last character
      # Implicit output

```
> 1 votes

# Answer
# Java 117 bytes

(or 10 if we consider numerical system with base 117)

```
String z(char[]s){String r="";for(int i=0,x=-1;++x<s.length/2;i+=2)r+=(s[i]==s[i+1]?"":s[i]=='0'?"0":"1");return r;}

```
> 0 votes

# Answer
# GNU sed, 19 bytes

```
#!/bin/sed -rf
s/11|00|(.?)./\1/g

```

Simple and boring translation of Martin Büttner♦'s Retina solution. Except that I used `11|00` in place of `.(\1)` (for the same score). 18 bytes of code, plus one for the `-r`.
> 0 votes

# Answer
# C#, 83 bytes

```
int[]M(int[]x)=>x.Select((v,i)=>i%2>0&&x[i-1]!=v?x[i-1]:2).Where(v=>v<2).ToArray();

```

First, replace odd-numbered items which are not equal to their predecessors with the predecessor, while setting all the rest to 2, then drop all items equal to 2.
> 0 votes

# Answer
# Ruby, 66 bytes

initial attempt; likely room for improvement. Run with "ruby -n" and then enter input followed by enter key.

```
$_.chomp!;i,s=0,'';(s<<$_[i] if $_[i]!=$_[i+1];i+=2)until !$_[i+1];p s

```
> 0 votes

# Answer
# Python, 72 bytes

This definitely won't be the shortest, but hopefully it'll at least give someone a headache.

```
lambda s:hex(int('110'+s[::-1],4))[:3:-1].translate({48:'',53:'',52:48})

```
> 0 votes

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


title: Capitalize String

text:
# Question
Title: Capitalize String
Given a string, capitalize it. By capitalization I mean `conTeNT-lENgth` changes to `Content-Length`. In the example I showed the string with 2 words with `-` as the word boundary. However I expect you to write the code for the string containing any number of words separated by a **single** character as the boundary. This boundary may change across the string.

**Conditions**

1. using `regular expressions` is **not allowed**.
2. there could be any number of words in a sentence(string).
3. each word will consist of `English` letters`[a-zA-Z]` of any case.
4. different words in the sentence will be separated by a single character. This character will **only** be any one of `-`, `.`, , `/`, `&`, `#`. You can safely assume that sentence will **not** contain any other character except the mentioned ones.
5. word boundaries should be preserved in the output.
6. shortest code wins.

For example your program should output `Begin/With.Type&Content` for `BeGin/wITH.tyPE&conTeNt`.

```
Some test cases:
 "aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe"
 "type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe"
 "cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc"
 "lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT"
 "contENT/ACcEpT"
 "BeGin/wITH.tyPE&conTeNt"
 "Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with"
 "RaNgE&COnTeNT WITh CoNTENT-TypE tyPe"
 "BEgin COdE#uSeR#aGeNt.USeR"
 "TypE LENGth"

```

# Answer
> 7 votes
### GolfScript, 36 27 19 characters

```
0\{95&+.47>32*\}%\;

```

A quite basic GolfScript approach which works for all input according to the specification. The examples can be tested online.

# Answer
> 26 votes
**Python 3,22**

```
print(input().title())

```

This code will take a string as input from stdin and gives a capitalized output to stdout.

for example:

input:

```
BEGIN/wITH.tyPe&cOnTENt

```

ouput:

```
Begin/With.Type&Content

```

The following code is for multi-line inputs (if necessary)

**Python 3, 46**

```
import sys
for i in sys.stdin:print(i.title())

```

# Answer
> 8 votes
# 05AB1E, 1 byte

Code:

Explanation:

```
™   # Implicit input which is converted to title case.

```

Try it online!

# Answer
> 7 votes
## JavaScript (94)

```
prompt().split(l='').map(function(a){return l='A'>l?a.toUpperCase():a.toLowerCase()}).join('')

```

# Answer
> 6 votes
# Mathematica 62

**Data**

```
tests={"aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe","type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe","cc/rEspoNCe.lEngtH#tYpEwitH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc","lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT","contENT/ACcEpT","BeGin/wITH.tyPE&conTeNt","Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with","RaNgE&COnTeNT WITh CoNTENT-TypE tyPe","BEgin COdE#uSeR#aGeNt.USeR","TypE LENGth"}

```

---

**Code**

```
StringReplace[ToLowerCase@#,WordBoundary~~x_:>ToUpperCase@x]&

```

---

**Usage**

```
f["aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe"]

```

> "Agent Accept/Length-Type User Range.Type"

```
f /@ tests

```

> {"Agent Accept/Length-Type User Range.Type",
> "Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code", "Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc", "Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content", "Content/Accept",
> "Begin/With.Type&Content",
> "Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With",
> "Range&Content With Content-Type Type",
> "Begin Code#User#Agent.User",
> "Type Length"}

# Answer
> 5 votes
**PHP : 78 73 65 64 characters**

```
$b=ucfirst;foreach(str_split($s)as$c)echo$b($c),!$b[0]=$c<A?u:l;

```

Input is passed in `$s`. It operates on the string as an array of characters.

It is a simple 2 state machine. It relies on lexical ordering of strings, and that the parser automatically assumes you meant to type a string in some cases.

The state is being stored in `$b` and is being represented as the name of the function that needs to be called on the next character. `ucfirst` and `lcfirst` are shorter to type and have identical behaviour to `strtolower`/`strtoupper` on single character strings. Also, since they only differ by one letter, we can use them efficiently to store the state. The original version needed to store the state explicitly in a boolean.

Since echo doesn't print anything for boolean false, I used a comma and the `!` operator to "hide" the assignment(which in this case is truthy) in the echo statement. This allowed me to save a character by removing the `{}`.

# Answer
> 4 votes
# Powershell: 37 - 43

Depending on how you want to take the input...

**Prompt the user for input: 43**

```
(Culture).TextInfo.ToTitleCase((read-host))

```

**Take input from pipeline: 38**

```
(Culture).TextInfo.ToTitleCase($input)

```

**Provide input as an argument when running the script: 37**

```
(Culture).TextInfo.ToTitleCase($args)

```

---

**NOTE:** The above scripts will ignore all-caps words, leaving them as-is. If this needs to be accounted for, the input should be forced to lower-case before the Title Case conversion. This adds 10 characters to the first method, and 12 to the other two.

```
(Culture).TextInfo.ToTitleCase((read-host).ToLower())
(Culture).TextInfo.ToTitleCase("$input".ToLower())
(Culture).TextInfo.ToTitleCase("$args".ToLower())

```

# Answer
> 4 votes
## C, 83

```
n;main(c){c=getchar();putchar(c>96?n?c:(n=c-32):c&64?n?c+32:(n=c):(n=0,c));main();}

```

Takes lines on `stdin`, translates them to `stdout`. (Prefers `SIGINT` to `EOF`.)

# Answer
> 4 votes
## Java - 209 characters

```
class C{
public static void main(String[]a){
for(String b:a){
char[]k=b.toLowerCase().toCharArray();
for(int i=-1;i<k.length;i++){if(i<0||"-. /&#".indexOf(k[i])>=0)k[++i]=(char)(k[i]-32);}
System.out.println(k);}}}

```

I added newlines only for readability.

# Answer
> 3 votes
# Ruby: ~~60~~ ~~51~~ ~~50~~ 47 characters

```
$_.downcase.chars{|c|$><<$/=$/<?0?c.upcase: c}

```

Sample run:

```
bash-4.1$ for line in "${test[@]}"; do printf '%-75s | %s\n' "$line" "$( ruby -ne '$_.downcase.chars{|c|$><<$/=$/<?0?c.upcase: c}' <<< "$line" )"; done
aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe                                    | Agent Accept/Length-Type User Range.Type
type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe             | Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code
cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc          | Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc
lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT     | Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content
contENT/ACcEpT                                                              | Content/Accept
BeGin/wITH.tyPE&conTeNt                                                     | Begin/With.Type&Content
Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with           | Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With
RaNgE&COnTeNT WITh CoNTENT-TypE tyPe                                        | Range&Content With Content-Type Type
BEgin COdE#uSeR#aGeNt.USeR                                                  | Begin Code#User#Agent.User
TypE LENGth                                                                 | Type Length

```

# Answer
> 3 votes
# Befunge 98 - ~~24~~ 45

```
~\j:'``!3*j' -;:'``b*j:'/`!3*j' +#;:,'/`!jc#@

```

Writing this hurt my brain.

This takes input through `~` and if the previous character was one of the separators (or if there was no previous character), it executes

```
:'``!3*j' -;

```

This snippet takes the character, and if its ascii value is greater than or equal to `a`, it subtracts 32 from it, thus changing it to upper case. If it is less than `a`, `3*j` skips the adjustment. Afterwards, it skips the next part. This part handles changing from upper case to lower case (I'm sure it can be merged with the next part; I'm just not sure how):

```
:'``b*j:'/`!3*j' +#;

```

The character is printed (`,`), then this checks if the character is one of the boundaries:

```
'/`!

```

It basically compares the character to the ascii value of `/`. If the character is not a boundary, the code pushes `12` so that it will skip the capitalization adjustment the next time around. `#` skips over the end program: `@`, and if the end of the input is reached, `~` sends the code execution back to the `@`, ending the program.

# Answer
> 3 votes
### R, ~~143~~ 116

A solution a bit long maybe but here we go:

```
f=function(x){a=sapply(1:nchar(x),function(y)substr(tolower(x),y,y));d=c(1,which(!a%in%letters)+1);a[d]=toupper(a[d]);cat(a,sep="")}

```

Slightly ungolfed and explained:

```
f <- function(x){
    #Split the string in characters and "lower-case" everything
    a <- sapply(1:nchar(x),function(y)substr(tolower(x),y,y))
    #Select the first character and each character following a
    #character that doesn't belong to lower case alphabet
    d <- c(1,which(!a%in%letters)+1)
    #Make those ones uppercase.
    a[d] <- toupper(a[d])
    #Output (stdout) while pasting them back together.
    cat(a,sep="")
    }

```

**Edit**: 116 characters

The main challenge here is to vectorize `substr`. Here's another less verbose way.

```
f=function(x){n=1:nchar(x);a=mapply(substr,tolower(x),n,n);d=c(T,!a%in%letters);a[d]=toupper(a[d]);cat(a[n],sep="")}

```

Indented:

```
f <- function(x){
    n <- 1:nchar(x)
    a <- mapply(substr,tolower(x),n,n)
    d <- c(T,!a%in%letters) #This has been simplified as well
    a[d] <- toupper(a[d])
    cat(a[n],sep="") #Because a is now 1 char longer than x, need to subset a
    }

```

Usage:

```
> f("aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe")
Agent Accept/Length-Type User Range.Type

```

# Answer
> 3 votes
# JavaScript (string-\>string), 67 bytes

```
s=>[...s].map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='').join``

```

Try it:

```
f=s=>[...s].map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='').join``

console.log(f('aGeNT aCcEpT/LEngTh-tYPe USeR raNgE.TyPe'));
console.log(f('type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe'));
console.log(f('cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc'));
console.log(f('lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT'));
console.log(f('contENT/ACcEpT'));
console.log(f('BeGin/wITH.tyPE&conTeNt'));
console.log(f('Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with'));
console.log(f('RaNgE&COnTeNT WITh CoNTENT-TypE tyPe'));
console.log(f('BEgin COdE#uSeR#aGeNt.USeR'));
console.log(f('TypE LENGth'));
```

# Jacob's variant - JavaScript (char\[\]-\>char\[\]), 55 bytes

```
s=>s.map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='')

```

Try it:

```
f=s=>s.map(a=>l=a[`to${'A'>l?'Upp':'Low'}erCase`](),l='')

g = s => f([...s]).join``

console.log(g('aGeNT aCcEpT/LEngTh-tYPe USeR raNgE.TyPe'));
console.log(g('type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe'));
console.log(g('cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc'));
console.log(g('lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT'));
console.log(g('contENT/ACcEpT'));
console.log(g('BeGin/wITH.tyPE&conTeNt'));
console.log(g('Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with'));
console.log(g('RaNgE&COnTeNT WITh CoNTENT-TypE tyPe'));
console.log(g('BEgin COdE#uSeR#aGeNt.USeR'));
console.log(g('TypE LENGth'));
```

# Answer
> 2 votes
## C# – 110

A simple finite-state-machine-based processing:

```
x.Aggregate(new{b=1>0,r=""},(s,c)=>new{b="-. /&#".Contains(c),r=s.r+(s.b?Char.ToUpper(c):Char.ToLower(c))}).r

```

(where `x` is the `string` to capitalize)

and of course, if you want to be boring (after the specification was updated), you can use

```
new CultureInfo(9).TextInfo.ToTitleCase(x)

```

or, with all the boring boilerplate:

```
class C{static void Main(string[]a){System.Console.WriteLine(new System.Globalization.CultureInfo(9).TextInfo.ToTitleCase(a[0]));}}

```

# Answer
> 2 votes
## Forth, 135

```
: s swap ;
: c 1 begin key dup 96 > if s if 32 - then 0 s
else dup 64 > if s 0= if 32 + then 0 s then else 1 s then then emit again ; c

```

Translated output is written to `stdout` as it reads from `stdin`.

# Answer
> 2 votes
## Javascript 102

```
prompt().split(o=q='').map(function(c){o+=(q)?c.toLowerCase():c.toUpperCase(),q=('A'>c)?0:1})
alert(o)

```

# Answer
> 2 votes
## Befunge-98 (29), C (65)

Since the method/algorithm is pretty much the same, I include both versions in the same post. Both rely on keeping track of whether the last character was a symbol or letter, in order to know whether to lowercase a letter or not.

**Befunge-98 (29)**
```
#@~:'0` #v_,0>
',++@'% '<   ^

```
**C (65)**
```
c,d;main(){for(;~(c=getchar());d=c>48)putchar(c<48?c:c&95|32*d);}

```

# Answer
> 2 votes
## AWK, ~~113~~ ~~103~~ 98 bytes

```
{OFS=""
for(n=split($0,a,"");i<=n;s=a[++i]){$i=(L?tolower(s):toupper(s))
L=!(index("-. /&#",s))}}1

```

Try it online!

This works fine for single line content, but for multi-line input a few more inits need to be added

## AWK, 104 bytes

```
{OFS=i=s=L=""
for(n=split($0,a,"");i<=n;s=a[++i]){$i=(L?tolower(s):toupper(s))
L=!(index("-. /&#",s))}}1

```

Try it online!

It would have been nice to take advantage of AWK's automatic splitting of a record into fields and modifying said fields, but that throws away the field separators. :(

This update throws away the idea of tacking characters onto a string and then printing the string. Instead, each character becomes its own field. Without the `OFS=""` bit, each character/field would be separated by a space when printed, which isn't what was requested.

Realizing that "" is essentially the same thing as 0 in AWK shortens the byte-count for the multi-line version a little bit. (I know it's different... I said 'essentially' :p )

# Answer
> 2 votes
# Python 3, 122 bytes

```
lambda s:''.join(chr(ord(c)+[[0,0],[0,32],[-32,0]][('@'<c<'[')-('`'<c<'{')]['@'<p<'['or'`'<p<'{'])for c,p in zip(s,'-'+s))

```

Try it online!

Not a great score, but I wanted to try it without builtin string operations for case changing.

# Answer
> 1 votes
# Excel VBA, 13 characters

In the Immediate window

```
?[Proper(A1)]

```

Function takes input from cell `A1`

## VBScript

```
Set xlapp = CreateObject("excel.application")
wscript.echo xlapp.Evaluate("Proper(""BeGin/wITH.tyPE&conTeNt"")"

```

# Answer
> 1 votes
# QBasic, 74 bytes

```
1c$=LCASE$(INPUT$(1))
IF f=0THEN c$=UCASE$(c$)
f=c$>"@
?c$;
IF""<c$GOTO 1

```

Bytes are counted in CP-437;  is a single byte (character code 20).

The input method here is a bit strange: characters are typed one at a time, and their capitalization is converted before they are displayed. So when you type in `aGeNT`, it appears on screen as `Agent`. Hitting `Enter` ends the program.

# Answer
> 1 votes
# Python 3, 9 bytes

```
str.title

```

Try it online!

# Answer
> 1 votes
# Perl 5 \+ `-pF`, 42 bytes

```
$\.=~$=?uc:lc,$==index'?/.- &#',$_ for@F}{

```

Try it online!

# Answer
> 1 votes
# Vyxal, ~~20~~ 15 bytes

```
f:ʀĠ•ƛḣv⇩$⇧p;f∑

```

Try it Online!

Or, if that's too long:

## 1 byte

```
ǐ

```

Try it Online!

## Explained

```
f:ʀĠ•ƛḣv⇩$⇧p;f∑
f:               # Push two copies of the letters of the input
  ʀ              # is each letter in the first copy in the alphabet?
   Ġ             # group that on consecutive elements - this has the effect of grouping words.
    •            # reshape the other copy of the letters to have the same shape as that
     ƛ           # to each sublist L:
      ḣv⇩        #     push L[0] and [lower(x) for x in L[1:]] - on single length strings this just leaves L[0] on the stack.
         $⇧p     #     uppercase L[0] and prepend it to the other list
            ;    # close map
             f∑  # deep flatten and summate to get a single string - the `d` flag would save 3 bytes here by removing this pair and allowing structure autocompletion to save a byte.

```

# Answer
> 1 votes
# Go, 153 bytes

```
import."strings"
func f(s string)(o string){c:=0<1
for i:=range s{x:=s[i:i+1]
if c{o+=ToUpper(x);c=!c}else{o+=ToLower(x)}
c=Contains("-. /&#",x)}
return}

```

Attempt This Online!

# Answer
> 1 votes
# Julia 1.0, 9 bytes

```
titlecase

```

Try it online!

# Answer
> 1 votes
# Thunno, \\$2\log\_{256}(96)\approx\\$ 1.65 bytes

```
zV

```

Attempt This Online!

Just a built-in solution.

# Answer
> 1 votes
# JavaScript (Node.js), ~~54~~ 53 bytes

Exact same score as the RegEx approach would have been!

```
s=>Buffer(s.toLowerCase()).map(x=c=>x=x>64?c:c^32)+``

```

Try it online! (includes all test cases)

# Answer
> 1 votes
# K (ngn/k), 36 bytes

```
{,/{`c$x-32*~!#x}'_(&1,~~"a{"'_x)_x}

```

Try it online!

* `_(&1,~~"a{"'_x)_x` split input after each non-letter and lowecase it, e.g. `"Begin/With.Type&Content"` to `("begin/";"with.";"type&";"content")`
* `{`c$x-32*~!#x}'` subtract 32 from the first character in each word and 0 from the rest (in effect capitalizing the first letter and leaving the others unchanged)
* `,/` flatten back into a single string and (implicitly) return

# Answer
> 0 votes
## T-SQL, 179

```
DECLARE @T VARCHAR(MAX)='foo',@X VARCHAR(2),@ INT=0WHILE @<LEN(@T)SELECT @X=SUBSTRING(@T,@,2),@+=1,@T=STUFF(@T,@,1,IIF(@X LIKE'[a-Z]_',LOWER(RIGHT(@X,1)),UPPER(RIGHT(@X,1))))PRINT @T

```

Try the SELECT version in SQL Server 2012 here.

Replace "foo" with the input string. The char count is for a zero-length string. This code traverses the string using an index, uppercasing or lowercasing the character at that position based on the previous character.

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

```
c=>a=>c.split``.map(b=>a="A">a?b.toUpperCase():b.toLowerCase()).join``

```

Try it online!

I am sure this can be golfed further.

# Note :

Takes input via `f(string)()` , the last are required but perform nothing.

# Answer
> 0 votes
# Powershell, ~~77~~ 75 bytes

This solution fully meets the task rules (even ambiguous example `foo:bar`).

```
-join($args|% t*y|%{"$_"|%('ToU*r','ToL*r')[+$l];$l=!('# -./&'|% Co*s $_)})

```

*See also the Powershell solution with builtin function ToTitleCase from @Iszi.*

Explained test script:

```
$f = {

-join(
$args|% t*y|%{                   # for each char from input string
    "$_"|%('ToU*r','ToL*r')[+$l] # evaluate ToUpper or ToLower method depend on $l (lower) value
                                 # Note the variable $l is not defined for a first char
                                 # so it evaluates toUpper for the first char
    $l=!('# -./&'|% Co*s $_)     # golfed form for $l=!'# -./&'.Contains($_) expression
                                 # =0 if the current char is specified separator (toUpper for next char)
}                                # =1 otherwise (toLower for next char)
)                                # finally, join all chars to a result string

}

@(
    ,('foo:bar'                                                                 ,'Foo:bar')
    ,('aGeNT ACcEpT/LEngTh-tYPe USeR raNgE.TyPe'                                ,'Agent Accept/Length-Type User Range.Type')
    ,('type&AgeNt/CC/COnteNt lEnGth#acCePT/AgeNt.RAnGe-Cc/contEnt/cODe'         ,'Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code')
    ,('cc/rEspoNCe.lEngtH#tYpE-witH&UsEr/bEgIN&uSer.AGEnT&begIn/aCCEPt/Cc'      ,'Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc')
    ,('lENgTH#USeR.tYpE/BeGiN&LENGth tYpe/ACCEpt#rANge/codE&AnD-ACCepT/ConTenT' ,'Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content')
    ,('contENT/ACcEpT'                                                          ,'Content/Accept')
    ,('BeGin/wITH.tyPE&conTeNt'                                                 ,'Begin/With.Type&Content')
    ,('Code.cc#User.lenGTh-USer-AND&tyPE TypE&leNgtH.tYPe usER.UseR&with'       ,'Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With')
    ,('RaNgE&COnTeNT WITh CoNTENT-TypE tyPe'                                    ,'Range&Content With Content-Type Type')
    ,('BEgin COdE#uSeR#aGeNt.USeR'                                              ,'Begin Code#User#Agent.User')
    ,('TypE LENGth'                                                             ,'Type Length')
) | % {
    $s,$e = $_
    $r = &$f $s
    "$($r-ceq$e): $r"
}

```

Output:

```
True: Foo:bar
True: Agent Accept/Length-Type User Range.Type
True: Type&Agent/Cc/Content Length#Accept/Agent.Range-Cc/Content/Code
True: Cc/Responce.Length#Type-With&User/Begin&User.Agent&Begin/Accept/Cc
True: Length#User.Type/Begin&Length Type/Accept#Range/Code&And-Accept/Content
True: Content/Accept
True: Begin/With.Type&Content
True: Code.Cc#User.Length-User-And&Type Type&Length.Type User.User&With
True: Range&Content With Content-Type Type
True: Begin Code#User#Agent.User
True: Type Length

```

# Answer
> 0 votes
# Zsh, 10 bytes

```
<<<${(C)1}

```

Try it online!

# Answer
> 0 votes
# PHP, 28 bytes

Use of a dedicated function around since v4 makes a shorter and easier answer than elder

```
echo ucwords(strtolower($s));

```

# Answer
> 0 votes
# Swift 5.6, ~~52~~ 51 bytes

```
import Foundation
let f=\.capitalized as(String)->_

```

Try it on SwiftFiddle! For some reason, this has to be typed using `as`; `let f:(String)->_=\.capitalized` doesn't work.

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

```
s=>Buffer(s).map(x=c=>x=x>64?c|32&c/2:c&~32)+``

```

Try it online!

From Shaggy's

# Answer
> 0 votes
# Thunno 2, 1 byte

Try it online!

lol

Same as the Python answer - Thunno 2 is written in Python and that's exactly what the interpreter is doing behind the scenes.

(Built-in for title case)

# Answer
> -1 votes
# Javascript 72 bytes

```
prompt().toLowerCase().split``.map((p,e)=>0==e?p.toUpperCase():p).join``

```

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