title: Is my name official?

text:
# Question
Title: Is my name official?
### Introduction

As ToonAlfrink says: "Me thinks there aren't enough easy questions on here that beginners can attempt!". So the task is very simple. Given a string, output a truthy or falsy value whether the name is official or not.

**A name is "official" if it is a single title-case word, that is:**

* If the *first* letter is capitalized (not official: `adnan`)
* If the other letters are *not* capitalized (not official: `AdNaN`)
* If the name *doesn't* contain any non-alphabetic characters (not official: `Adnan123`, `Adnan!`)
* If the name consists of just one word (not official: `Adn an`, `Adn An`)
* If the name has more than one character (not official: `A`)

### Rules

* You may provide a function or a program
* This is , so the submission with the least amount of bytes wins!
* **Note:** To simplify things, names like Mary-Ann are in this challenge *not official.*
* Assume that there are no leading whitespaces in the name.
* Assume that only the printable ASCII characters (`32-126`) are used in the names

### Test cases

```
Input: Adnan
Output: True

Input: adnan
Output: False

Input: AdnaN
Output: False

Input: Adnan123
Output: False

Input: Adnan Adnan
Output: False

Input: A
Output: False

Input: Mary-Ann
Output: False

```

### Leaderboard

```
/* Configuration */

var QUESTION_ID = 67554; // Obtain this from the url
// It will be like http://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 34388; // This should be the user ID of the challenge author.

/* App */

var answers = [], answers_hash, answer_ids, answer_page = 1, more_answers = true, comment_page;

function answersUrl(index) {
  return "http://api.stackexchange.com/2.2/questions/" +  QUESTION_ID + "/answers?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + ANSWER_FILTER;
}

function commentUrl(index, answers) {
  return "http://api.stackexchange.com/2.2/answers/" + answers.join(';') + "/comments?page=" + index + "&pagesize=100&order=desc&sort=creation&site=codegolf&filter=" + COMMENT_FILTER;
}

function getAnswers() {
  jQuery.ajax({
    url: answersUrl(answer_page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      answers_hash = [];
      answer_ids = [];
      data.items.forEach(function(a) {
        a.comments = [];
        var id = +a.share_link.match(/\d+/);
        answer_ids.push(id);
        answers_hash[id] = a;
      });
      if (!data.has_more) more_answers = false;
      comment_page = 1;
      getComments();
    }
  });
}

function getComments() {
  jQuery.ajax({
    url: commentUrl(comment_page++, answer_ids),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      data.items.forEach(function(c) {
        if (c.owner.user_id === OVERRIDE_USER)
          answers_hash[c.post_id].comments.push(c);
      });
      if (data.has_more) getComments();
      else if (more_answers) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SCORE_REG = /<h\d>\s*([^\n,<]*(?:<(?:[^\n>]*>[^\n<]*<\/[^\n>]*>)[^\n,<]*)*),.*?(\d+)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/;

var OVERRIDE_REG = /^Override\s*header:\s*/i;

function getAuthorName(a) {
  return a.owner.display_name;
}

function process() {
  var valid = [];

  answers.forEach(function(a) {
    var body = a.body;
    a.comments.forEach(function(c) {
      if(OVERRIDE_REG.test(c.body))
        body = '<h1>' + c.body.replace(OVERRIDE_REG, '') + '</h1>';
    });

    var match = body.match(SCORE_REG);
    if (match)
      valid.push({
        user: getAuthorName(a),
        size: +match[2],
        language: match[1],
        link: a.share_link,
      });
    else console.log(body);
  });

  valid.sort(function (a, b) {
    var aB = a.size,
        bB = b.size;
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  valid.forEach(function (a) {
    if (a.size != lastSize)
      lastPlace = place;
    lastSize = a.size;
    ++place;

    var answer = jQuery("#answer-template").html();
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", a.user)
                   .replace("{{LANGUAGE}}", a.language)
                   .replace("{{SIZE}}", a.size)
                   .replace("{{LINK}}", a.link);
    answer = jQuery(answer);
    jQuery("#answers").append(answer);

    var lang = a.language;
    lang = jQuery('<a>'+lang+'</a>').text();

    languages[lang] = languages[lang] || {lang: a.language, lang_raw: lang, user: a.user, size: a.size, link: a.link};
  });

  var langs = [];
  for (var lang in languages)
    if (languages.hasOwnProperty(lang))
      langs.push(languages[lang]);

  langs.sort(function (a, b) {
    if (a.lang_raw.toLowerCase() > b.lang_raw.toLowerCase()) return 1;
    if (a.lang_raw.toLowerCase() < b.lang_raw.toLowerCase()) return -1;
    return 0;
  });

  for (var i = 0; i < langs.length; ++i)
  {
    var language = jQuery("#language-template").html();
    var lang = langs[i];
    language = language.replace("{{LANGUAGE}}", lang.lang)
                       .replace("{{NAME}}", lang.user)
                       .replace("{{SIZE}}", lang.size)
                       .replace("{{LINK}}", lang.link);
    language = jQuery(language);
    jQuery("#languages").append(language);
  }

}
```

```
body { text-align: left !important}

#answer-list {
  padding: 10px;
  width: 290px;
  float: left;
}

#language-list {
  padding: 10px;
  width: 290px;
  float: left;
}

table thead {
  font-weight: bold;
}

table td {
  padding: 5px;
}
```

```
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b">
<div id="language-list">
  <h2>Shortest Solution by Language</h2>
  <table class="language-list">
    <thead>
      <tr><td>Language</td><td>User</td><td>Score</td></tr>
    </thead>
    <tbody id="languages">

    </tbody>
  </table>
</div>
<div id="answer-list">
  <h2>Leaderboard</h2>
  <table class="answer-list">
    <thead>
      <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr>
    </thead>
    <tbody id="answers">

    </tbody>
  </table>
</div>
<table style="display: none">
  <tbody id="answer-template">
    <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
<table style="display: none">
  <tbody id="language-template">
    <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr>
  </tbody>
</table>
```

# Answer
> 6 votes
# Pyth, ~~16~~ ~~13~~ 12 bytes

*Thanks to @Thomas Kwa for reminding me about titlecase.*

```
&qzr@GrzZ3tz

```

Test Suite.

```
&              Boolean and operator
 qz            Equality test on input
  r    3       Titlecase operator
   @G          Setwise intersection with the alphabet
    rzZ        Input to lowercase
 tz            All but the first character of the input

```

# Answer
> 21 votes
# Retina, 13 bytes

```
^[A-Z][a-z]+$

```

Try it online | Test suite (The output `0` means none of the strings matched, which is expected.)

When Retina is only provided with a single line of code, it outputs the number of times the expression matched the input string, so it will output `1` (truthy) if it matches and therefore is an official name and `0` (falsy) if it's not.

### Breakdown

```
^       The beginning of the string
[A-Z]   One uppercase letter
[a-z]+  One or more lowercase letters
$       The end of the string

```

# Answer
> 9 votes
# TeaScript, 12 bytes

```
xO`A-Z][a-z`

```

Abuses the `O` function.

Try this online

Test Suite

## Explanation

The `O` function makes this:

```
x O   `A-Z][a-z`
x.O(/^[A-Z][a-z]+$/)

```

Then, the O function checks if the regex matches `x`.

---

Alternatively, a TeaScript 3 answer at **7 bytes**:

```
xO/\A\a

```

# Answer
> 7 votes
# JavaScript (ES6), 26

```
n=>/^[A-Z][a-z]+$/.test(n)

```

By: Edcsixtyfive

```
f=n=>/^[A-Z][a-z]+$/.test(n)

console.log=x=>O.textContent+=x+'\n'

;['Adnan','adnan','AdnaN','Adnan123','Adnan Adnan','A','Mary-Ann']
.forEach(t=>console.log(t+' '+f(t)))
```

```
<pre id=O></pre>
```

# Answer
> 7 votes
# Python, ~~59~~ 58 bytes

I'm sure there's no real way to beat the Retina version, since this is basically just that within Python. But I think this is my first submission ;)

```
import re,sys;print(re.match('[A-Z][a-z]+$',sys.argv[1]))

```

It's a very *odd* truthy value:

```
(test2)wayne@arglefraster ~/programming/inactive/golf/67554
⚘ python golf.py AdNan                                                                                $? 148  %# 3  10:06:36
None
(test2)wayne@arglefraster ~/programming/inactive/golf/67554
⚘ python golf.py Adnan                                                                                %# 3  10:06:40
<_sre.SRE_Match object at 0x7feefea7f440>
(test2)wayne@arglefraster ~/programming/inactive/golf/67554
⚘ python golf.py "Adnan Banana"                                                                                %# 3  10:06:47
None

```

(And it does require `""` around strings with spaces in it, if passed via the shell)

# Answer
> 4 votes
# Java, 53 bytes

```
boolean b(String a){return a.matches("[A-Z][a-z]+");}

```

# Answer
> 4 votes
# Python, ~~50~~ ~~45~~ ~~43~~ 41 bytes

```
lambda s:s.isalpha()*s.istitle()*len(s)>1

```

Returns `True` if it's an official name or `False` if it's not.

# Answer
> 3 votes
# VB6, 48 bytes

```
Function f(i):f=i Like"[A-Z][a-z]+":End Function

```

# Answer
> 3 votes
# BotEngine, ~~203~~ ~~180~~ 29x6=174

```
v ABCDEFGHIJKLMNOPQRSTUVWXYZ
>ISSSSSSSSSSSSSSSSSSSSSSSSSSF
v <<<<<<<<<<<<<<<<<<<<<<<<<<
 Tabcdefghijklmnopqrstuvwxyz
> SSSSSSSSSSSSSSSSSSSSSSSSSSF
^E<<<<<<<<<<<<<<<<<<<<<<<<<<

```

I should really add builtins for identifying uppercase and lowercase letters. That would be much more concise than checking each letter individually.

Rough translation:

```
for a of input enqueue a
if ABCDEFGHIJKLMNOPQRSTUVWXYZ contains first
 remove first
 while abcdefghijklmnopqrstuvwxyz contains first
  remove first
 if empty
  yield TRUE exit
 else
  yield FALSE exit
else
 yield FALSE exit

```

# Answer
> 3 votes
# C, 129 122 121 111 bytes

```
main(c,b,d){b=d=0;while((c=getchar())>13)b|=b|=!b&&c>90|c<65?1:2&&d++&&c<97|c>122?4:2;printf("%d\n",b<3&&d>1);}

```

Try It Online

```
main(c,b,d)
{
    b=d=0;
    while((c=getchar())>13)
    {
        // Twiddle bits, 1<<0 for first character and 1<<3 for subsequent
        b|=!b&&c>90|c<65?1:2; // check first character is valid
        b|=d++&&c<97|c>122?4:2; // check later characters are valid
    }
    // If all OK b == 2, if either of above are wrong, b >= 3 due to
    // extra bits. Also, d should be > 1 for name length to be valid.
    printf("%d\n",b<3&&d>1);
}

```

# Answer
> 3 votes
# Ruby, 28 bytes

```
p (gets=~/^[A-Z][a-z]+$/)!=p

```

-2 bytes( thanks to manatwork )

# Answer
> 3 votes
# 05AB1E, ~~11~~ ~~7~~ 6 bytes

```
á™Q×¦Ā

```

-4 bytes thanks to *@Grimy*.

Try it online or verify all test cases.

**Explanation:**

```
á       # Only leave the letters of the (implicit) input
        #  i.e. "Adnan" → "Adnan"
        #  i.e. "A" → "A"
        #  i.e. "aDNAN" → "aDNAN"
        #  i.e. "Adnan123" → "Adnan"
 ™      # Titlecase it
        #  i.e. "Adnan" → "Adnan"
        #  i.e. "Adnan" → "A"
        #  i.e. "aDNAN" → "Adnan"
  Q     # Check if it's still equal to the (implicit) input
        #  i.e. "Adnan" and "Adnan" → 1 (truthy)
        #  i.e. "A" and "A" → 1 (truthy)
        #  i.e. "aDNAN" and "Adnan" → 0 (falsey)
        #  i.e. "Adnan123" and "Adnan" → 0 (falsey)
   ×    # Repeat the (implicit) input that many times
        #  i.e. "Adnan" and 1 → "Adnan"
        #  i.e. "A" and 1  → "A"
        #  i.e. "aDNAN" and 0 → ""
        #  i.e. "Adnan123" and 0 → ""
    ¦Ā  # Remove the first character, and check that it's non-empty
        #  i.e. "Adnan" → "dnan" → 1 (truthy)
        #  i.e. "A" → "" → 0 (falsey)
        #  i.e. "" → "" → 0 (falsey)
        # (which is output implicitly as result)

```

# Answer
> 2 votes
## Mathematica 10.1, 46 bytes

```
LetterQ@#&&#==ToCamelCase@#&&StringLength@#>1&

```

Uses one less byte than the standard regex solution. It does three checks. `LetterQ@#` ensures that the string is entirely composed of letters, and `StringLength@#>1` invalidates single-letter strings. `#==ToCamelCase@#` makes less sense, however. `ToCamelCase` is an undocumented function I found that takes an input string AndOutputsItLikeThis. Since there is only one word, it will capitalize the first letter, so we check if the string is equal to that.

# Answer
> 2 votes
## bash/zsh/ksh, 25 bytes

```
[[ $1 =~ ^[A-Z][a-z]+$ ]]

```

To actually use this, make a file with it as the only line and make the file executable; executable files not recognized as a known binary type are treated as shell scripts (for `/bin/sh` specifically).

```
$ printf '[[ $1 =~ ^[A-Z][a-z]+$ ]]' >f
$ chmod +x f
$ wc -c f
25 f
$ for x in 'Adnan' 'adnan' 'AdnaN' 'Adnan123' 'Adnan Adnan' 'A' 'Mary-Ann'; do f "$x" && echo 1 || echo 0; done
1
0
0
0
0
0
0
$

```

# Answer
> 2 votes
# MATL, 18 bytes

The current version (4.0.0) of the language is used.

This applies the same regular expression as NinjaBearMonkey's answer:

```
j'^[A-Z][a-z]+$'XX

```

The output is the string (which is truthy) if it's an official name, and nothing (which is falsy) if it's not.

### Examples

```
>> matl
 > j'^[A-Z][a-z]+$'XX
 >
> December
December
>>

>> matl
 > j'^[A-Z][a-z]+$'XX
 >
> ASCII
>>

```

# Answer
> 2 votes
# Haskell, 61 bytes

```
f(h:t@(_:_))=elem h['A'..'Z']&&all(`elem`['a'..'z'])t
f _=1<0

```

# Answer
> 2 votes
# Gema, 17 characters

```
\B<K1><J>\E=1
*=0

```

Sample run:

```
bash-4.3$ echo -n 'Adnan' | gema '\B<K1><J>\E=1;*=0'
1

bash-4.3$ echo -n 'adnan' | gema '\B<K1><J>\E=1;*=0'
0

bash-4.3$ echo -n 'Adnan123' | gema '\B<K1><J>\E=1;*=0'
0

```

# Answer
> 2 votes
# IA-32 machine code, 19 bytes

A function that receives the pointer to a null-terminating string in `ecx` and returns 0 or 1 in `eax` (according to the `fastcall` convention).

Hexdump of the code:

```
6a 20 58 32 01 74 0a 41 2c 61 3c 1a b0 00 72 f3 c3 40 c3

```

In assembly language:

```
    push 32;
    pop eax;

myloop:
    xor al, [ecx];
    jz yes;
    inc ecx;
    sub al, 'a';
    cmp al, 26;
    mov al, 0;
    jb myloop;
    ret;

yes:
    inc eax;
    ret;

```

The first byte of the input name has its 5th bit flipped (`xor` with `32`) to convert it from capital case to small case. This loads 32 into `eax`, using 3 bytes of code:

```
    push 32;
    pop eax;

```

To check whether the byte is a small letter:

```
    sub al, 'a';
    cmp al, 26;
    jb myloop;

```

If not, this code falls through. To return 0 in this case, it puts 0 in `al` before doing the conditional jump:

```
    sub al, 'a';
    cmp al, 26;
    mov al, 0;
    jb myloop;

```

The 0 in `al` also serves as a xor-mask (or absence of it) for the following bytes of the input name.

A successful exit is when it encounters a zero byte, which stays zero after the `xor`:

```
    xor al, [ecx];
    jz yes;

```

It assumes that the input name is not empty. I guess it's a reasonable assumption about a name (not an arbitrary string)!

# Answer
> 2 votes
### `grep`, 16 bytes

This is the pattern:

```
[A-Z][a-z]+

```

If you use the `-E` and `-x` and `-c` switches `grep` will print a count of matching input lines. So if you give it one line you get a 1 or a 0. I think that's how this place works.

The pattern is 11 chars, the whole command line is 23. I've seen people use `sed` scripts without the command so I don't know what is what. But, it reads stdin, and so you can just type at it. Here's `echo`:

```
for a in Adnan adnan Ad\ nan
do  echo "$a" | grep -cxE \[A-Z]\[a-z]+
done

```

---

```
1
0
0

```

# Answer
> 2 votes
## C# 4, 89 bytes

My first attempt at Code Golf. Here it comes:

```
bool o(string i){return System.Text.RegularExpressions.Regex.IsMatch(i,"^[A-Z][a-z]+$");}

```

See it in action at Dot Net Fiddle.

# Answer
> 2 votes
# Java, 28 bytes

```
n->n.matches("[A-Z][a-z]+")

```

Uses regex to make sure the string consists of an uppercase character followed by at least one lowercase character.

-1 bytes thanks to Benjamin Urquhart

# Answer
> 2 votes
# Vyxal, 8 bytes

```
Lċ?₍ǐǍ≈∧

```

Try it Online (with test cases)!

Potentially golfable. I swear there was a builtin for `len(a)>1`...

Assumes input is nonempty.

```
L        # Length of input
 ċ       # is not 1
  ?      # Push the input,
   ₍     # parallel apply...
    ǐ    # title case and
     Ǎ   # keep only alphabetic chars
      ≈  # is equal?
       ∧ # bitwise AND the length and ^

```

# Answer
> 2 votes
# Thunno 2 `b`, 5 bytes

```
Ịḟ=×ḣ

```

Port of Kevin Cruijssen's 05AB1E answer.

#### Explanation

```
Ịḟ=×ḣ  # Implicit input
Ị      # Remove non-alphabets from the input
 ḟ     # Convert this string to title case
  =    # Check whether it's still equal to the input
   ×   # Repeat the input this many times
       # (i.e. input if true, empty string otherwise)
    ḣ  # Remove the first character from this string
       # The b flag boolifies the resulting string,
       # checking that it is not empty
       # Implicit output

```

#### Screenshots

(click to enlarge)

# Answer
> 1 votes
## k4, 39 bytes

```
{((*x)in .Q.A)&(&/(1_,/x)in .Q.a)&1<#x}

```

First char is upper, all others are lower, count greater than one.

E.g.:

```
  {((*x)in .Q.A)&(&/(1_,/x)in .Q.a)&1<#x}'("Adnan";"adnan";"AdnaN";"Adnan123";"Adnan Adnan";"A";"Mary-Ann")
1000000b

```

# Answer
> 1 votes
## Seriously, 16 bytes

```
ú4,nÿ=)l1<)ù-Y&&

```

Hex Dump:

```
a3342c6e983d296c313c29972d592626

```

Try It Online

Seriously does not have regex support yet, so the best we can do is:

```
 4,n                               Push 4 copies of input
    ÿ=                             Check that it's equal to itself converted to titlecase
      )                            Put the boolean on the bottom
       l1<                         Check that it's longer than 1 character
          )                        Put the boolean on the bottom
           ù                       Convert it to lowercase.
ú           -Y                     Check that removing the lowercase alphabet empties it
              &&                   And all the booleans together

```

# Answer
> 1 votes
# Ocaml, 231 216 197 166 bytes

```
let f n=let l=String.length n in if l=1 then 0 else let rec e=function 0->1|i->match n.[i] with('a'..'z')->e(i - 1)|_->0 in match n.[0]with('A'..'Z')->e(l - 1)|_->0;;

```

Example usage:

```
# f "Adnan";;
- : int = 1

# f "adnan";;
- : int = 0

# f "AdnaN";;
- : int = 0

# f "Adnan123";;
- : int = 0

# f "Adnan Adnan";;
- : int = 0

# f "A";;
- : int = 0

# f "Mary-Ann";;
- : int = 0

```

Ungolfed (with real function names):

```
let is_name name =
  let len = String.length name
  in if len = 1 then 0 else
  let rec explode_lower = function
    | 0 -> 1
    | i ->
      match name.[i] with
      | ('a'..'z') -> explode_lower (i - 1)
      | _ -> 0
  in match name.[0] with
  | ('A'..'Z') -> explode_lower (len - 1)
  | _ -> 0;;

```

# Answer
> 1 votes
## Swift 2, 116 bytes

Regex is so verbose in Swift that doing this is much shorter

```
func e(s:String)->Int{var c=0;for k in s.utf8{if(c==0 ?k<65||k>90:k<97||k>122){return 0};c++};return s.utf8.count-1}

```

This will return `0` or `-1` (in the case of no input) for non-official names, and a number `> 0` (which is equal to the length of the string - 1) if the name is official

### Ungolfed

```
func e(s: String) -> Int{
    var c = 0
    for k in s.utf8{
        if(c == 0 ? k < 65 || k > 90 : k < 97 || k > 122){
            return 0
        }
        c++
    }
    return s.utf8.count - 1
}

```

# Answer
> 1 votes
# SpecBAS - 39 bytes

SpecBAS handles regular expressions through the `MATCH` command. Output is 0 for false and 1 if true.

```
1 input n$:  ?MATCH("^[A-Z][a-z]+$",n$)

```

# Answer
> 1 votes
## C#, 188 bytes

Regular expressions would have been the right way to tackle this, but here's an attempt without it.

```
bool O(string s){for(int i=1;i<s.Length;i++){if(char.IsUpper(s[i])){return false;}}if(char.IsUpper(s[0])&&s.All(Char.IsLetter)&&!s.Contains(" ")&& s.Length > 1){return true;}return false;}

```

Longhand

```
static bool O(string s)
{
    for (int i = 1; i < s.Length; i++)
    {
        if (char.IsUpper(s[i]) )
        {
            return false;
        }
    }
    if (char.IsUpper(s[0]) && s.All(Char.IsLetter) && !s.Contains(" ") && s.Length > 1)
    {
        return true;
    }
    return false;
}

```

Would love advice on how to make the lowercase check shorter, perhaps without the loop. I just started learning the language, and used this as practice, figured I'd share my result anyway.

# Answer
> 1 votes
# Perl 5 `-p`, 18 bytes

```
$_=/^[A-Z][a-z]+$/

```

Try it online!

# Answer
> 1 votes
# PowerShell, 29 bytes

```
"$args"-cmatch'^[A-Z][a-z]+$'

```

Try it online!

Does the same regex trick everyone else is using. Has to use `c`ase-sensitive `match` to properly do it at the cost of a byte.

# Answer
> 1 votes
# Perl 6, 17 bytes

```
{/^<:Lu><:Ll>+$/}

```

Returns a `Match` object if this is an official name and `Nil` otherwise.

Try it online!

# Answer
> 1 votes
# Japt, 9 bytes

Returns `1` or `0`.

```
è"^%A%a+$

```

Try it

# Answer
> 1 votes
# , 18 bytes

```
'[A-Z][a-z]+'&rxeq

```

Attempt This Online!

```
'[A-Z][a-z]+'&rxeq
              rxeq  NB. does the regex fully describe the string
             &      NB. bind the left argument to
'[A-Z][a-z]+'       NB. the Official™ regex

```

# Answer
> 0 votes
# AWK, 15 bytes or 37 bytes (rule dependent)

## Flexibly truthy

If you're allowed to define "truthy" as "non-empty string", then:

```
/^[A-Z][a-z]+$/

```

Try it online!

## Strict truthy

If it needs to be something more consistent like 1 and 0, then:

```
{print match($0,/^[A-Z][a-z]+$/)?1:0}

```

Try it online!

# Answer
> 0 votes
## C++, 73 bytes

Good old `#define`

```
#include<regex>
#define F(s)std::regex_match(s,std::regex("[A-Z][a-z]+"))

```

Code to test :

```
std::cout << F("Adnan") << '\n';
std::cout << F("adnan") << '\n';
std::cout << F("AdnaN") << '\n';
std::cout << F("Adnan123") << '\n';
std::cout << F("Adnan Adnan") << '\n';
std::cout << F("A") << '\n';
std::cout << F("Mary-Ann") << '\n';

```

# Answer
> 0 votes
# JavaScript(ES6), 83 bytes

```
s=>s[0].match(/[A-Z]/)&&s.substr(1).match(/[a-z]/)&&!s.match(/[^A-Z]/i)&&s.length>1

```

# Answer
> 0 votes
# Stax, 9 bytes

```
ü╡♫╒┤á╕◘▓

```

Run and debug it

Tests for complete match with regex `"[A-Z][a-z]+"`.

# Answer
> 0 votes
# Kotlin 98 bytes

```
x.length>1 && x.mapIndexed{i,c->if(i>0)c in 'a'..'z' else c in 'A'..'Z'}.sumBy{if(it) 0 else 1}==0

```

Way less boring than shorter:

```
x.matches(Regex("[A-Z][a-z]+"))

```

Try it online!

# Answer
> 0 votes
# PHP, 51 bytes

```
<?=ucfirst($s=$argn)==$s&ctype_lower(substr($s,1));

```

Try it online!

No regex. Input is `STDIN`, output to `STDOUT` is `'1'` for truthy and `'0'` for falsy.

```
$ echo Adnan|php -F p.php
1
$ echo adnan|php -F p.php
0
$ echo AdnaN|php -F p.php
0
$ echo Adnan123|php -F p.php
0
$ echo Adnan Adnan|php -F p.php
0
$ echo A|php -F p.php
0
$ echo Mary-Ann|php -F p.php
0
$ echo Mary-ann|php -F p.php
0

```

# Answer
> 0 votes
# Python 2, 43 bytes

```
lambda s:len(s)>1==s.isalpha()<s==s.title()

```

Try it online!

# Answer
> 0 votes
# Arturo, 28 bytes

```
$=>[match?&{/^[A-Z][a-z]+$}]

```

Try it

# Answer
> 0 votes
# Lua, 29 bytes

```
s=...print(s==s:match'%u%l+')

```

Try it online!

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


title: Calculate the Ultraradical

text:
# Question
Title: Calculate the Ultraradical
## What is the Ultraradical?

The ultraradical, or the Bring radical, of a real number \\$a\\$ is defined as the only real root of the quintic equation \\$x^5+x+a=0\\$.

Here we use \\$\text{UR}(\cdot)\\$ to denote the ultraradical function. For example, \\$\text{UR}(-100010)=10\\$, since \\$10^5+10-100010=0\\$.

## Challenge

Write a full program or a function, that takes a real number as input, and returns or outputs its ultraradical.

## Requirements

No standard loopholes are allowed. The results for the test cases below must be accurate to at least 6 significant digits, but in general the program should calculate the corresponding values for any valid real number inputs.

## Test Cases

9 decimal places rounded towards 0 are given for reference. Explanation is added for some of the test cases.

```
 a                         | UR(a)
---------------------------+---------------------
             0             |   0.000 000 000        # 0
             1             |  -0.754 877 (666)      # UR(a) < 0 when a > 0
            -1             |   0.754 877 (666)      # UR(a) > 0 when a < 0
             1.414 213 562 |  -0.881 616 (566)      # UR(sqrt(2))
            -2.718 281 828 |   1.100 93(2 665)      # UR(-e)
             3.141 592 653 |  -1.147 96(5 385)      # UR(pi)
            -9.515 716 566 |   1.515 71(6 566)      # 5th root of 8, fractional parts should match
            10             |  -1.533 01(2 798)
          -100             |   2.499 20(3 570)
         1 000             |  -3.977 89(9 393)
      -100 010             |  10.000 0(00 000)      # a = (-10)^5 + (-10)
 1 073 741 888             | -64.000 0(00 000)      # a = 64^5 + 64

```

## Winning Criteria

The shortest valid submission in every language wins.

# Answer
# Wolfram Language (Mathematica), 20 bytes

```
Root[xx^5+x+#,1]&

```

Try it online!

Still a built-in, but at least it isn't `UltraRadical`.

(the character  is displayed like `|->` in Mathematica, similar to `=>` in JS)
> 12 votes

# Answer
# Python 3.8 (pre-release), 60 bytes

```
f=lambda n,x=0:x!=(a:=x-(x**5+x+n)/(5*x**4+1))and f(n,a)or a

```

Try it online!

Newton iteration method. \\$ x' = x - \frac {f(x)} {f'(x)} = x - \frac {x^5+x+n} {5x^4+1}\\$

While using \\$ \frac {4x^5-n} {5x^4+1} \\$ is mathematically equivalent, it makes the program loop forever.

---

Other approach:

# Python 3.8 (pre-release), 102 bytes

```
lambda x:a(x,-x*x-1,x*x+1)
a=lambda x,l,r:r<l+1e-9and l or(m:=(l+r)/2)**5+m+x>0and a(x,l,m)or a(x,m,r)

```

Try it online!

Binary search, given that the function `x^5+x+a` is increasing. Set the bounds to `-abs(x)` and `abs(x)` is enough but `-x*x-1` and `x*x+1` is shorter.

BTW Python's recursion limit is a bit too low so it's necessary to have 1e-9, and the `:=` is called the walrus operator.
> 8 votes

# Answer
# Jelly, 8 bytes

```
;17B¤ÆrḢ

```

Try it online!

**How it works:**

* Constructs the list `[a, 1, 0, 0, 0, 1]` by prepending `a` to the binary representation of `17`. Why this list? Because it corresponds to the coefficients we are looking for:

```
[a, 1, 0, 0, 0, 1] -> P(x) := a + 1*x^1 + 0*x^2 + 0*x^3 + 0*x^4 + 1*x^5 = a + x + x^5

```
* Then, `Ær` is a built-in that solves the polynomial equation `P(x) = 0`, given a list of coefficients (what we constructed earlier).
* We are only interested in the real solution, so we take the first entry in the list of solutions with .
> 8 votes

# Answer
# JavaScript (ES7), 44 bytes

A safer version using the same formula as below but with a fixed number of iterations.

```
n=>(i=1e3,g=x=>i--?g(.8*x-n/(5*x**4+5)):x)``

```

Try it online!

---

# JavaScript (ES7),  ~~43~~  42 bytes

Newton's method, using \\$5x^4+5\\$ as an approximation of \\$f'(x)=5x^4+1\\$.

```
n=>(g=x=>x-(x-=(x+n/(x**4+1))/5)?g(x):x)``

```

Try it online!

### How?

We start with \\$x\_0=0\\$ and recursively compute:

$$x\_{k+1}=x\_k-\frac{{x\_k}^5+x\_k+n}{5{x\_k}^4+5}=x\_k-\frac{x\_k+\frac{n}{{x\_k}^4+1}}{5}$$

until \\$x\_k-x\_{k+1}\\$ is insignificant.
> 8 votes

# Answer
# APL (Dyalog Unicode), ~~11~~ 10 bytesSBCS

-1 thanks to dzaima

Anonymous tacit prefix function.

```
(--*∘5)⍣¯1

```

Try it online!

`(``)⍣¯1` apply the following tacit function negative one time:

`-` the negated argument

`-` minus

`*∘5` the argument raised to the power of 5

In essence, this asks: *Which \\$x\\$ do I need to feed to \\$f(x)=-x-x^5\\$ such that the result becomes \\$y\\$.*
> 6 votes

# Answer
# , 43 bytes

```
function(a)nlm(function(x)abs(x^5+x+a),a)$e

```

Try it online!

`nlm` is an optimization function, so this searches for the minimum of the function \\$x\mapsto |x^5+x+a|\\$, i.e. the only zero. The second parameter of `nlm` is the initialization point. Interestingly, initializing at 0 fails for the last test case (presumably because of numerical precision), but initializing at `a` (which isn't even the right sign) succeeds.
> 5 votes

# Answer
# , 56 bytes

```
function(x)(y=polyroot(c(x,1,0,0,0,1)))[abs(Im(y))<1e-9]

```

Try it online!

Thanks to @Roland for pointing out `polyroot`. I have also realised my previous answer picked a complex root for zero or negative \\$a\\$ so now rewritten using `polyroot` and filtering complex roots.
> 4 votes

# Answer
# , 14 bytes

```
{:@;@p.@,#:@17

```

Try it online!

J has a built in for solving polynomials... `p.`

The final 4 test cases timeout on TIO, but in theory are still correct.

## how

The polynomial coefficients for J's builtin are taken as a numeric list, with the coefficient for `x^0` first. This means the list is:

```
a 1 0 0 0 1

```

`1 0 0 0 1` is 17 in binary, so we represent it as `#:@17`, then append the input `,`, then apply `p.`, then unbox the results with raze `;`, then take the last element `{:`
> 3 votes

# Answer
# Ruby, ~~53~~ 41 bytes

```
->a{x=a/=5;99.times{x-=a/(x**4+1)+x/5};x}

```

Try it online!

Using Newton-Raphson with a fixed number of iterations, and the same approximation trick as Arnauld
> 3 votes

# Answer
# Pari/GP, ~~34~~ ~~32~~ ~~26~~ 24 bytes

```
a->-solve(X=0,a,a-X-X^5)

```

Try it online!
> 2 votes

# Answer
# k4, ~~33~~ 31 bytes

```
{{y-(x+y+*/5#y)%5+5*/4#y}[x]/x}

```

newton-raphson computed iteratively until a number is converged on

edit: -2 thanks to ngn!

---

whoops, got this all wrong...

# ~~K (oK), 10 bytes~~

```
{-x+*/5#x}

```
> 2 votes

# Answer
# 05AB1E, 12 bytes

```
ΔyIy4m>/+5/-

```

Try it online!

Newton's method.
> 2 votes

# Answer
# Pari/GP, 24 bytes

```
a->polrootsreal(x^5+x+a)

```

Try it online!
> 1 votes

# Answer
# Octave, 25 bytes

```
@(a)fzero(@(x)x^5+x+a,-a)

```

Try it online!
> 1 votes

# Answer
# Maplesoft Maple, 23 bytes

```
f:=a->fsolve(x^5+x+a=0)

```

Unfortunately, there is no online Maple compiler/calculator out there AFAIK. But the code is pretty straightforward.
> 1 votes

# Answer
**C,118b/96b**

```
#include<math.h>
double ur(double a){double x=a,t=1;while(fabs(t)>1e-6){t=x*x*x*x;t=(x*t+x+a)/(5*t+1);x-=t;}return x;}

```

118 bytes with original function name and with some extra accuracy (double). With bit hacks may be better, but unportable.

96 bytes with fixed iterations.

```
double ur(double a){double x=a,t;for(int k=0;k<99;k++){t=x*x*x*x;x=(4*x*t-a)/(5*t+1);}return x;}

```

Actually, our function is so good we can use better adaptations of Newton's method. Much faster and practical implementation (150 bytes) would be

```
#include<math.h>
double ur(double a){double x=a/5,f=1,t;while(fabs(f)>1e-6){t=x*x*x*x;f=(t*(5*t*x+5*a+6*x)+a+x)/(15*t*t-10*a*x*x*x+1);x-=f;}return x;}

```

I checked it works, but I'm too lazy to find out how much more fast it would be. Should be at least one more order faster as Newton's.
> 1 votes

# Answer
# MMIX, 68 bytes (17 instrs)

(jelly-style xxd -g4)

```
00000000: e0043ff0 e0034014 79010001 3b01013f  ṭ¥?ṅṭ¤@Þy¢¡¢;¢¢?
00000010: e8013ff0 c1020100 10ff0202 10ffffff  ċ¢?ṅḊ£¢¡Ñ”££Ñ”””
00000020: 1001ff02 10ffff03 e4010020 04ffff04  Ñ¢”£Ñ””¤ỵ¢¡ ¥””¥
00000030: 06010100 140101ff 11020102 5b02fff6  ©¢¢¡Þ¢¢”×£¢£[£”ẇ
00000040: f8020000                             ẏ£¡¡

```

**Disassembly**

```
bringr  SETH  $4,#3FF0          // one = 1.
        SETH  $3,#4014          // five = 5.
        ZSNN  $1,$0,1           // x = (a neg? 0 : 1)
        SLU   $1,$1,63          // x <<= 63
        ORH   $1,#3FF0          // x |= 1. [now x = a neg? 1. : -1.]
0H      SET   $2,$1             // loop: px = x
        FMUL  $255,$2,$2        // t = px *. px
        FMUL  $255,$255,$255    // t = t *. t
        FMUL  $1,$255,$2        // x = t *. px
        FMUL  $255,$255,$3      // px = px *. five
        INCH  $1,#20            // x *.= 4. (bit trick: add two to exponent)
        FADD  $255,$255,$4      // t = t +. one
        FSUB  $1,$1,$0          // x = x -. a
        FDIV  $1,$1,$255        // x = x /. t
        FCMPE $2,$1,$2          // px = epsilon_comp(x, px)
        PBNZ  $2,0B             // iflikely(px) goto loop
        POP   2,0               // return x

```

I used WolframAlpha to simplify Newton's method for this. It said that \\$\def\d{{\rm d}}x-{x^5+x+a\over{\d\over \d x}x^5+x+a}\\$ simplified down to \\$4x^5-a\over5x^4+1\\$. The convergence test here is a builtin epsilon-convergence, so `rE` must be set by the calling function.

For faster convergence, change `ORH $1,#3FF0` to

```
        SLU  $255,$0,1      // 3BFF0001 ;”¡¢ shift left to erase sign
        INCH $255,#8020     // E4FF8020 ỵ”⁰  unbias exponent
        PUT  rD,0           // F7010000 ẋ¢¡¡ prep dividend
        DIVU $2,$255,5      // 1F02FF05 þ£”¦ take approximate fifth root
        CSN  $2,$255,$255   // 6002FFFF `£”” and use that if we are >1
        INCH $2,#7FE0       // E4027FE0 ỵ£¶ṭ rebias exponent
        SRU  $255,$2,1      // 3FFF0201 ?”£¢ shift right again
        OR   $1,$1,$255     // C00101FF Ċ¢¢” or sign and guess

```
> 1 votes

# Answer
# Excel (Insider Beta), 59 bytes

```
=h(a1,1)
h =LAMBDA(a,x,IF(a=x^5+x,x,h(a,(a/(x^5+x))^0.2*x))) in name manager

```

1 byte for name h in name manager, 49 bytes for formula for h, 9 bytes for calling h. Uses successive approximations using the 5th root of a/(x^0.5+x) times x. Initial call uses 1 for x.
> 1 votes

# Answer
# Clean, ~~61~~ 60 bytes

```
import StdEnv
$a=iter 99(\x=(3.0*x^5.0-a)/inc(4.0*x^4.0))0.0

```

Try it online!

Newton's method, first implemented in user202729's answer.

# Clean, 124 bytes

```
import StdEnv
$a= ?a(~a)with@x=abs(x^5.0+x+a);?u v|u-d==u=u|v+d==v=v= ?(u+if(@u< @v)0.0d)(v-if(@u> @v)0.0d)where d=(v-u)/3E1

```

Try it online!

A "binary" search, narrowing the search area to the upper or lower 99.6% of the range between the high and low bounds at each iteration instead of 50%.
> 0 votes

# Answer
# Python 3 \+ sympy, 72 bytes

```
lambda y:float(sympy.poly("x**5+x+"+str(y)).all_roots()[0])
import sympy

```

Try it online!
> 0 votes

# Answer
# TI-Basic (TI-83), 12 bytes

```
solve(X^5+X+Ans,X,0

```

# TI-Basic (TI-89), 13* bytes

```
solve(x^5+x=-a,x)→f(a)

```

\*Not completely sure how to score ti-89 programs/functions
> 0 votes

# Answer
# Scala, 74 bytes

Using Newton-Raphson with a fixed number of iterations, and the same approximation trick as @Arnauld

Golfed version. Try it online!

```
def f(a:Double)={var x=a/5;(1 to 99).foreach{_=>x-=(a/(x*x*x*x+1)+x)/5};x}

```

Ungolfed version. Try it online!

```
import scala.math._

object Main {
  def main(args: Array[String]): Unit = {
    val f: Double => Double = a => {
      var x = a / 5
      (1 to 99).foreach { _ =>
        x -= (a / (x * x * x * x + 1) + x) / 5
      }
      x
    }

    val inputs = List(-100010.0, 0.0, 1.0, -1.0, exp(1), pow(2, 0.5), 1073741888.0)
    inputs.foreach { x =>
      println(s"%.9f --> %.9f".format(x, f(x)))
    }
  }
}

```
> -1 votes

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


# Question
Title: Find The Average String Between Two Strings
> Inspired by this

Your task today: given two strings, find the string with the lowest maximum Levenshtein distance to the input strings. For example, using `Steffan` and `Seggan`, the average string will be `Steggan`. It is distance 2 from `Steffan` (replace the `gg` with `ff`), and 1 from `Seggan` (add a `t`). That gives it a maximum distance of 2.

Other constraints:

* If there are multiple possibilities, output any of them or all of them (duplicates are OK)
* The inputs are distinct
* The input will be given in uppercase or lowercase ASCII, you choose
* There will always be common letters in the inputs
* The outputs will only have letters from the inputs
* There will always be a solution satisfying the above constraints

As this is , shortest code in bytes wins.

## Testcases

```
seggan, steffan -> ['seffan', 'sefgan', 'segfan', 'stefgan', 'stegfan', 'steggan'] (2)
hello, ho -> ['hllo', 'hlo', 'helo', 'heo'] (2)
string, ring -> ['tring', 'sring'] (1),
aaa, aaaa -> ['aaa', 'aaaa'] (1)
abc, abcd -> ['abc', 'abcd', 'abd', 'abca', 'abcb', 'abcc'] (1)

```

# Answer
> 7 votes
# Vyxal, 14 bytes

```
Þ∪Þx:ƛ□꘍GN;ÞMİ

```

Try it Online!

I think `Þ∪` can be `J`, but that makes it so slow that it's practically impossible to run.

This is already really, really, really slow.

```
Þ∪Þx:ƛ□꘍GN;ÞMİ
Þ∪             # Get the multiset union of the two strings
  Þx           # Get all combinations without replacement of all lengths and of all orders
    :          # Duplicate (call this X)
     ƛ         # Over each:
      □꘍       #  For each of the inputs, get the Levenshthein distance between that input and this string
        G      #  Get the maximum of that
         N     #  Negate that
          ;    # Close map
           ÞM  # Get the indices of maximal elements. (If Vyxal had an "indices of minimal elements" builtin, then negate could be removed.)
             İ # Index this into X

```

# Answer
> 6 votes
# 05AB1E, 9 bytes

```
JæΣ.L{R}н

```

Outputs one possible result.

Try it online or verify all test cases.

**Explanation:**

```
J        # Join the (implicit) input-pair together to a single string
 æ       # Pop and get the powerset of this string
  Σ      # Sort it by:
   .L    #  Get the Levenshtein distance of the two strings with the (implicit) input
     {   #  Sort the pair from lowest to highest
      R  #  Reverse it from highest to lowest
  }н     # After the sort-by: leave the first result
         # (which is output implicitly as result)

```

Note: if we'd use `à` (max) instead of `{R`, it would also give results where the Levensthein distance is `[2,2]` even if `[1,2]` are available. If we'd use just `{`, it would give results where the Levensthein distance is `[0,3]` over `[1,2]`. So using the `{R` ensures the minimum pair while prioritizing the maximum of the pair.

---

Although it works for the test cases, I'm not 100% sure if  is *always* correct. Using an additional group-by (and uniquify) to get all results shows that `Stegfan` and `Segfan` aren't among them for example, since the powerset builtin uses characters of the joined string in order. This could be fixed by changing it to `Jœ€æ˜` \[+3 bytes\] (powerset of each permutation of the joined string), but it becomes extremely slow and it'll timeout.

# Answer
> 5 votes
# Factor \+ `lcs math.combinatorics`, ~~123~~ ~~120~~ 78 bytes

```
[ 2dup append all-subsets [ tuck [ levenshtein ] 2bi@ max ] 2with infimum-by ]

```

Attempt This Online!

-42 bytes(!) using the idea behind @KevinCruijssen's 05AB1E answer.

# Answer
> 4 votes
# Vyxal, 9 bytes

```
∑ṗµ?꘍sṘ;h

```

Try it Online!

Port of Kevin Cruijssen's answer, go upvote that!

# Answer
> 3 votes
# Pyth, ~~95~~ 93 bytes

```
J._+k._KwFGUz=ZJ=J]+_._<zhGkVlK aJh.mlb[+<zhG@ZhN+eJ<KhN+m+d@zG@ZN?q@zG@KNY]+e@ZN@KN;@eJ/leJ2

```

Try it online!

I know what you're thinking: "That seems long." In my defense, it's been a while since I've touched Pyth. Furthermore, this runs in Ο(m·n·max(m,n)) time, where m, n are the lengths of the two input strings. This is wicked fast and can handle pretty long strings with ease. I used this algorithm from Wikipedia, but instead of keeping track of the distance, I keep track of the optimal path throughout. Then at the end we can simply output the middle element of the optimal path. This must satisfy the requirements, as if there were some string with a lower max distance, there would then exist a shorter path.

# Answer
> 2 votes
# Python, 150 bytes

```
n=lambda A,B:{a[:x]+y+a[z:]for a in A for x in range(len(a)+1)for z in[x,x+1]for b in B for y in[*b,""]}
f=lambda A,B:(N:=n(A,B))&(M:=n(B,A))or f(N,M)
```

Attempt This Online!

# Answer
> 1 votes
# Wolfram Language (Mathematica), ~~92~~ 88 bytes

```
(c=Characters/@#;""<>#&/@MinimalBy[Subsets@*Join@@c,Max[EditDistance[x,#]&/@c]/.x->#&])&

```

Try it online!

---
Tags: code-golf, string, edit-distance
---


# Question
Title: What dice do I need to display every integer up to X?
You may have seen something called a "perpetual dice calendar":

Two 6-sided dice can be rearranged and rotated. One die has the numbers 0, 1, 2, 3, 4, and 5. The second die has the numbers 0, 1, 2, 6, 7, and 8. With this, any day of the month—from 1 to 31—can be displayed on the front of the calendar. *The `6` can be rotated to be used as a `9`.*

However, what if I wanted to display any number up to... 100? 365? 50287? How many 6-sided dice would I need then, and what numbers would be printed on their sides?

The challenge:

* Given a whole number input X, output the fewest possible 6-sided dice that are required to display all integers from 1 up to and including X.
* Each side of a die must contain exactly one integer, from 0 to 8 inclusive.
* `6`'s may be used as `9`'s.
* If not every side of every die needs to have a number on it, then those side(s) must have `0`.
* Each line of the output should represent a die, e.g.:

```
Input: 4
Output:
0 0 1 2 3 4

Input: 6
Output:
1 2 3 4 5 6

Input: 9
Output:
0 1 2 3 4 5
0 0 0 6 7 8

Input: 31
Output:
0 1 2 3 4 5
0 1 2 6 7 8

Input: 35
Output:
0 1 2 3 4 5
0 1 2 3 6 7
0 0 0 0 0 8

```
* The output lines can be in any format, e.g.:

```
123456
1 2 3 4 5 6
1,2,3,4,5,6
[1, 2, 3, 4, 5, 6]

```
* Assume that all the dice are used for every number, using leading 0's if necessary. For instance, if X is 35, then `2` would be displayed as `002`, because 3 dice are necessary.
* The outputted numbers do not need to be in any particular order.
* There may be multiple solutions for X. You need only output one.
* Standard golfing rules apply.

# Answer
> 7 votes
# Vyxal, ~~29~~ 17 bytes

```
~≈∩h9F5?6=+ẇṅ6∆Z⁋

```

Try it Online!

*-12 bytes by taking some ideas from @Jonathan Allan's Jelly answer*

I believe this is correct but I'm not completely sure.

```
~≈                # keep only those numbers where all digits are equal from the implicit range [1, input]
  ∩               # transpose
   h              # first element
    9F            # remove nines
      5?6=+       # 6 if input is 6 otherwise 5
           ẇ      # split into chunks of that length
            ṅ     # join
             6∆Z  # pad with zeros to length 6
                ⁋ # join by newlines

```

# Answer
> 12 votes
# Jelly,  ~~22~~  20 bytes

```
D€EƇZḢḟ9s<7+5Ɗo0x6¤Y

```

A full program that accepts a positive integer and prints a set of dice as lines each having six digits from \\$\[0,8\]\\$.

**Try it online!**

### How?

For small inputs (\\$\le 6\\$) we should fill a single die with the numbers we need and then zeros.

For larger numbers, we:

* need multiple dice since one dice only has six sides, and
* only place up to five non-zero digits on the first dice (since we will need at least one leading zero to represent small numbers like \\$7\\$ or \\$8\\$)

When we reach a rep-digit that is not repeated nines (e.g. \\$444\\$) we need to ensure that enough of the dice have that digit (in this case three of them), and that any others contain a zero (since we will need them in front to represent the rep-digit).

Thus an optimal output for numbers greater than six is to set the first face of every die to \\$0\\$ and fill the remaining faces with the digits \\$1\\$ to \\$8\\$ in order as required by either the number itself (excluding \\$9\\$) or the digit of the rep-digit we have reached that we cannot yet make.

Thus for inputs greater than six we:

* fill the first dice with \\$\[1,2,3,4,5,0\]\\$
* fill the second dice with \\$\[6,7,a,b,c,0\]\\$ where \\$a\\$, \\$b\\$ and \\$c\\$ are \\$0\\$ until we encounter \\$8\\$ (a non-nines rep-digit), \\$11\\$ and \\$22\\$ whereupon they should be filled with \\$8\\$, \\$1\\$ and \\$2\\$ respectively.
* at \\$33\\$ create a new dice \\$\[3,d,e,f,g,0\]\\$ where \\$d\\$, \\$e\\$, \\$f\\$, and \\$g\\$ are \\$0\\$ until we encounter \\$44\\$, \\$55\\$, \\$66\\$, and \\$77\\$ whereupon they should be filled with \\$4\\$, \\$5\\$, \\$6\\$, and \\$7\\$ respectively.
* etc.

```
D€EƇZḢḟ9s<7+5Ɗo0x6¤Y - Main Link: positive integer, N
 €                   - for each i in [1,N]:
D                    -   decimal digits
   Ƈ                 - keep those for which:
  E                  -   all equal -> [[1],[2],...,[9],[1,1],[2,2],...,[9,9],...,[1,1,1],...]
    Z                - transpose
     Ḣ               - head -> [1,2,...,9,1,2,...,9,1,...]
      ḟ9             - filter out nines
             Ɗ       - last three links as a monad - f(N):
         <7          -   less than seven?
            5        -   five
           +         -   add -> 6 if N < 7 else 5
        s            - (filtered list of digits) split into chunks of length (that)
                          e.g.:  N=3 -> [[1,2,3]]
                                N=44 -> [[1,2,3,4,5],[6,7,8,1,2],[3,4]]
                  ¤  - nilad followed by link(s) as a nilad:
               0     -   zero
                 6   -   six
                x    -   repeat -> [0,0,0,0,0,0]
              o      - logical OR (vectorises)
                          e.g.:  N=3 -> [[1,2,3,0,0,0]]
                                N=44 -> [[1,2,3,4,5,0],[6,7,8,1,2,0],[3,4,0,0,0,0]]
                   Y - join with newline characters

```

# Answer
> 5 votes
# Excel, ~~161 122 120~~ 122 bytes

*saved 39 bytes after looking at AndrovT's solution and fixing error for n=6*

*saved 2 more bytes after realizing the die for N=6 didn't need to have a 1*

*added 2 bytes because the previous statement was false*

```
=LET(x,ROW(1:8),y,LEN(A1),z,A1=6,IFERROR(HSTACK(z*1,MOD(SEQUENCE(INT((y*8+MAX(x*(REPT(x,y)*1<=A1))-4-z)/5),5)+z-1,8)+1),))

```

The formula above determines how many faces are needed to cover all numbers less than or equal to N then generates dice from the list below so there at least that many faces.

```
0 1 2 3 4 5
0 6 7 8 1 2
0 3 4 5 6 7
0 8 1 2 3 4
0 5 6 7 8 1
0 2 3 4 5 6
0 7 8 1 2 3
0 4 5 6 7 8

```

If N = 6 it uses `1 2 3 4 5 6`.

**Explanation:**

```
=LET(x,ROW(1:8),           # x = array 1..8
y,LEN(A1),                 # y = number of digits in N
z,A1=6,                    # z = (N=6)
IFERROR(~,)                # Pads errors with 0
HSTACK(z*1,~)                # Concatenates 0 to other 5 faces
MOD(SEQUENCE(~,5)+z-1,8)+1 # array of last 5 faces for each die
INT((~)/5)                 # number of dice needed
y*8+MAX(x*(~))-4-z         # 4 + number of faces needed to cover all numbers up to ~
REPT(x,y)*1<=A1            # calculates the largest number the same length as N with repeated digits

```

# Answer
> 5 votes
# Python3, 475 bytes:

```
from itertools import*
R=range
N=lambda k:k+[6,9]*(6 in k or 9 in k)
P=permutations
def f(n):
 q=[({*R(1,n+1)},[[]]if n<7 else[[0]])]
 while q:
  a,b=q.pop()
  if not a:return[[0]*(6-len(i))+i for i in b]
  t=str(min(a))
  for i in P(b,min(len(b),len(t))):
   for j,k in zip_longest(t,i):
    j=int(j)
    if not k or j not in N(k):
     D=[*b,[0,j]]if len(b[-1])==6 else[*b[:-1],b[-1]+[j]];q+=[(a-{int(''.join(map(str,K)))for d in P(D,len(D))for K in product(*map(N,d))},D)]

```

Try it online!

# Answer
> 5 votes
# JavaScript (ES8), 111 bytes

Algorithm shamelessly borrowed from @AndrovT's latest version, which itself uses ideas from @JonathanAllan.

Returns an array of digit strings.

```
n=>n-6?(g=n=>n?g(n-1)+(/^([1-8])\1*$/.test(n)?n%10:''):'')(n).match(/.{1,5}/g).map(s=>s.padEnd(6,0)):["123456"]

```

Try it online!

# Answer
> 5 votes
# Charcoal, 29 bytes

```
Ｅ⪪⁻⭆ΦＩ…·¹Ｎ⁼⌊ι⌈ι⌊ι9⁺⁵⁼θ6⭆◨ι⁶Σλ

```

Try it online! Link is to verbose version of code. Explanation: Once I'd figured out what the problem actually was, this is an implementation of @Axuary's observation, although comparing the other answers I see I ended up with the same basic algorithm as @AndrovT and @JonathanAllan but only by coincidence.

```
      …·                        Inclusive range from
        ¹                       Literal integer `1` to
         Ｎ                      First input as a number
     Ｉ                          Vectorised cast to string
    Φ                           Filtered where
           ⌊ι                   Minimum digit
          ⁼                     Is equal to
             ⌈ι                 Maximum digit
   ⭆           ⌊ι               Extract one digit from each repdigit
  ⁻              9              Remove `9`s
 ⪪                              Split into groups of
                   ⁵            Literal integer `5`
                  ⁺             Plus
                     θ          First input
                    ⁼           Equals
                      6         Literal string `6`
Ｅ                              Map over groups
                        ◨ι⁶     Pad to 6 characters
                       ⭆   Σλ   Replace spaces with `0`s
                                Implicitly print

```

The above code is sublinear in `X`, so here's more efficient 35-byte version:

```
Ｅ⪪⁻⭆⁺÷×⁹⊕ＮＸχＬθ×⁹⊖Ｌθ﹪⊕ι⁹0⁺⁵⁼θ6⭆◨ι⁶Σλ

```

Try it online! Link is to verbose version of code. Explanation: Calculates the number of repdigits up to `X` as equal to the first digit of `(X+1)*9` plus `9` times the length of `X` as a string plus a correction factor, then takes the sequence modulo `9` omitting the zeros and wraps into rows as above.

The problem would have been much more interesting if each number only needed to be formed from `1+floor(log10(X))` dice. In that case, my best patterns so far are as follows:

* 6: 123456
* 9: 123456, 78
* 10: 012345, 0678
* 21: 012345, 06781
* 32: 123450, 678012
* 54: 123456, 781234, 0
* 65: 123456, 781234, 05
* 76: 123456, 781234, 056
* 87: 123456, 781234, 0567
* 99: 123456, 781234, 05678
* 221: 123456, 781234, 056781, 0
* 332: 123456, 781234, 056781, 02
* 443: 123456, 781234, 056781, 023
* 554: 123456, 781234, 056781, 0234
* 665: 123456, 781234, 056781, 02345
* 776: 123456, 781234, 056781, 023456
* 887: 123456, 781234, 056781, 023456, 7
* 999: 123456, 781234, 056781, 023456, 78
* 1110: 123456, 781234, 056781, 023456, 780
* 2221: 123456, 781234, 056781, 023456, 7801
* 3332: 123456, 781234, 056781, 023456, 78012
* 4443: 123456, 781234, 056781, 023456, 780123

I believe that the dice will then continue cyclically though the digits after that point.

# Answer
> 4 votes
# 05AB1E, 44 (or 42†) bytes

```
[8Ý6ãNã.ΔULε§Xgj„9 60‡œεXsøε`å}P}à}P}D¸àd#}»

```

Extremely slow brute-force, so it'll time out for \\$n\geq7\\$ on TIO..
Not too happy with how long `§Igj„9 60‡œεXsøε`å}P}à` is. Will see if I can find something shorter (and hopefully faster) later on.

Try it online or verify some of the smaller test cases.

† With looser output-format of a list of lists of digits, the trailing  can be removed for -2 bytes.

**Explanation:**

```
[               # Start an infinite loop:
 8Ý             #  Push a list in the range [0,8]
   6ã           #  Cartesian power of 6 to create all sextets using these digits
     Nã         #  Cartesian power with the 0-based loop-index
 .Δ             #  Find the first one that's truthy for,
                #  or -1 if none are truthy:
   U            #   Pop and store the current list in variable `X`
   Ý            #   Push a list in the range [0, (implicit) input-integer]
    ε           #   Map over each value:
      Xg        #    Push the length of list `X`
     §  j       #    Pad leading spaces to make the current integer that length
         „9 60‡ #    Transliterate 9s to 6s and spaces to 0s
     œ          #    Get all permutations of this integer
      ε         #    Map over each permutation:
       Xs       #     Push list of lists `X` and swap
         ø      #     Create pairs of the two lists
          ε     #     Map over each pair of [list,digit]
           `    #      Pop and push the list and digit separately to the stack
            å   #      Check if the digit is in the list
          }P    #     After the map: check whether it's truthy for all [list,digit]-pairs
      }à        #    After the map: check whether it's truthy for any permutation
    }P          #   After the map: check whether it's truthy for all values in the range
  }D            #  After the find_first: Duplicate the resulting -1 or list
    ¸           #  Wrap it into a list
     à          #  Pop and push the flattened maximum
      d         #  If this maximum is non-negative (thus not -1):
       #        #   Stop the infinite loop
}»              # After the infinite loop: join each inner list of the valid find_first
                # by spaces, and then all strings by newlines
                # (after which it is output implicitly as result)

```

# Answer
> 4 votes
# Nibbles, 18 bytes (36 nibbles)

```
&"0"6`/ ?-$6 5 $ |+|.,$`$`@~$~<<$- 9

```

Same approach as Androv T's answer: upvote that one!

```
|+|.,$`$`@~$~<<$- 9 # part 1: get the nonzero digits needed:
   .                # map over
    ,               # range from 1..
     $              # input
        `@ $        #   convert to digits in base
          ~         #   10
      `$            #   and remove duplicates
  |                 # now filter to keep only
            ~       # falsy elements when
             <<$    #   dropping the first element of each list
 +                  # flatten the list of (1-element) lists
|                   # and filter again to keep only
                    # elements that are truthy (positive) when
                - 9 #   subtracted from 9
&"0"6`/ ?-$6 5 $    # part 2: split them into dice:
     `/             # split into chunks of
        ?           #   if
         -$6        #     input minus 6 is truthy
             5      #   then 5
               $    #   else input
&                   # now justify each chunk
    6               # to a width of 6
 "0"                # using "0" as a filler

```

---

Frustratingly, if we were allowed to use `9`s instead of `6`s (rather than `6`s instead of `9`s), which would correspond to identical physical dice, we could have:

# Nibbles, 16.5 bytes (33 nibbles; but not permitted output)

```
&"0";6`/ +`$- $@ $ +`%+|.,@`$`@~$~<<

```

# Answer
> 3 votes
# Python 2, 120 bytes

```
n=input()
m=n>6
for v in zip(*[(i%10for i in range(n>1,n+1)+4*[0]if len(set(`i`))<2-i%10/9)]*(6-m)):print'0'*m+`v`[1::3]

```

A full program that accepts a positive integer from STDIN and prints the dice.

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

This employs the same method I used in my Jelly answer.

---
Tags: code-golf
---


# Question
Title: Number of ways to make an amount with coins
**This is not a duplicate of Sum of combinations with repetition. This question considers `1+2` to be the same as `2+1`. The other question doesn't.**

---

OEIS link - A000008

---

## Background

If you have 4 types of coins (1, 2, 5 and 10 cents), in how many ways can you make an amount?

There are 4 ways of making 5 cents:

* 1 + 1 + 1 + 1 + 1
* 1 + 1 + 1 + 2
* 1 + 2 + 2
* 5

Note: 1 + 2 + 2 and 2 + 2 + 1 are considered to be the same in this challenge.

## Your task

* Take an input. It will be a positive integer. This is the amount (in cents).
* Work out the number of ways to make that number from 1, 2, 5 and 10 cent coins.
* This is a challenge, so any form of output is allowed.
* This is , so shortest answer in bytes wins.

# Answer
# Vyxal, ~~12~~ ~~8~~ 7 bytes

```
Ṅ₀$ḊvΠ∑

```

Try it Online! 6 bytes with s flag

## Explained

```
Ṅ₀$ḊvΠ∑
Ṅ       # Integer partitions of the input
 ₀$Ḋ    # Does each item in each partition divide 10?
    vΠ  # Product of each partition
      ∑ # Sum that

```
> 5 votes

# Answer
# JavaScript (ES6), 41 bytes

*Saved 3 bytes thanks to @ovs*

```
f=(n,k=10)=>n?k*n>0&&f(n,k>>1)+f(n-k,k):1

```

Try it online!

### 40 bytes

*Suggested by @tsh*

Returns *true* for \\$f(0)\\$.

```
f=(n,k=10)=>n>0?k&&f(n,k>>1)+f(n-k,k):!n

```

Try it online!

### Commented

```
f = (              // f is a recursive function taking:
  n,               //   n = input
  k = 10           //   k = current coin value
) =>               //
n ?                // if n is not equal to 0:
  k * n > 0 &&     //   if k is not equal to 0 and n is positive:
    f(n, k >> 1) + //     do a recursive call where k is updated to the
                   //     next coin value
    f(n - k, k)    //     do a recursive call where k is subtracted from n
:                  // else:
  1                //   increment the number of solutions

```
> 6 votes

# Answer
# HOPS, 20 bytes

```
mset(x+x^2+x^5+x^10)

```

Attempt This Online!
> 4 votes

# Answer
# Wolfram Language (Mathematica), 36 bytes

```
Length[{1,2,5,10}~FrobeniusSolve~#]&

```

Try it online!
> 4 votes

# Answer
# Regex  (RME / Perl / PCRE / Raku<sup>`:P5`</sup>), 24 bytes

```
^x*(xx)*(x{5})*(x{10})*$

```

Takes its input in unary, as the length of a string of `x`s. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

Try it on replit.com! \- RegexMathEngine
Try it online! \- Perl
Try it online! \- PCRE
Try it online! \- Raku

---

It's also possible to use Arnauld's algorithm, but only for inputs \\$≥ 10\\$ (because captures are the only kind of variable available, and can only be taken from the input). Even using lookinto, this is pretty long at **42 bytes** (and would be longer using variable-length lookbehind):

```
^(?|(?^1=(x+)\1){0,3}\1|^(?=(x{10}))){2,}$

```

Try it on replit.com! \- RegexMathEngine

```
^                      # tail = input number
(?|
    (?^1=(x+)\1)       # Assert \1 is set; \1 = floor(\1 / 2);
                       # assert the resulting \1 ≥ 1
                {0,3}  # Iterate the above 0 to 3 times
    \1                 # tail -= \1
|                  # or
    ^(?=(x{10}))       # If on the first iteration, \1 = 10. This can be
                       # matched multiple times in a row, as long as nothing
                       # has been subtracted from tail yet, but that would
                       # result in a non-match when exiting this loop.
){2,}                  # Iterate the above at least 2 times, with no maximum.
                       # This allows the first alternative to get a chance to
                       # match after the second alternative, which is zero-
                       # width, has matched.
$                      # Assert tail == 0

```

That can be made to work with all inputs by extending it to 49 bytes: `^(?|(?^1=(x+)\1){0,3}\1|^(?=((x{5}|x)\2?)|)){2,}$` \- but this defeats the purpose of the 42 byte version in the first place, because if \\$10\\$ is not the only constant specified, you might as well go with the 24 byte version.

But it is possible to use this algorithm in its pure form (with no constants specified other than \\$10\\$ and \\$\lfloor\log\_2{10}\rfloor\\$) in such a way that works for all inputs, by capturing \\$10\\$ in binary (**89 bytes**):

`^(?|(?=(?=(\2))(?=(\3))(\4)()){0,3}(\1\2\2\3{4}\4{8})(?!.*$\5)|^(?=(?=()(x))()(x)|)){2,}$`

Attempt This Online! \- PCRE2 v10.40+
Try it on replit.com \- RegexMathEngine in PCRE mode

```
^                   # tail = N = input number
(?|                 # Branch reset group - capture group numbering of each
                    # alternative starts at the same number, in this case \1.
    (?=
        # coinValue /= 2, where coinValue is defined as \1 + \2*2 + \3*4 + \4*8
        (?=(\2))    # \1 = \2
        (?=(\3))    # \2 = \3
        (\4)()      # \3 = \4; \4 = 0
    ){0,3}          # maximum number of iterations is floor(log(10) / log(2))
    (               # \5 = coinValue; tail -= \5
        \1
        \2\2
        \3{4}
        \4{8}
    )
    (?!.*$\5)       # Assert \5 != 0
|
    ^               # Only take this alternative on the first iteration (or, as
                    # explained below, also the 2nd iteration, if N==0)
    # coinValue = 10
    (?=             # Atomic lookahead
        # This can only match if tail ≥ 1
        (?=()(x))   # \1 = 0; \2 = 1
           ()(x)    # \3 = 0; \4 = 1
    |           # or...
        # Do nothing, if tail == 0; in this case, the 2nd iteration of the
        # outer loop will also end up taking this alternative, and there will
        # be exactly one way N==0 can result in a match.
    )
){2,}               # An enforced minimum of 2 iterations is necessary, because
                    # the first iteration always has zero width, and would cause
                    # the loop to end otherwise. (In Perl, not even this trick
                    # can force a loop to take more than one zero-width
                    # iteration.)
$                   # Assert that tail == 0

```

For compatibility with old versions of PCRE2, it is necessary to use a 93 byte version of this:
Try it online! \- PCRE2 v10.33
> 4 votes

# Answer
# Python, <sup>~~111~~ ~~106~~</sup> 65 bytes

```
f=lambda s,n=4:s==0 or s>=0<n and f(s,n-1)+f(s-(1,2,5,10)[n-1],n)

```

Try it online!

-5 thanks to Jo King -41 thanks to Kevin Cruijssen
> 3 votes

# Answer
# Jelly, 7 bytes

```
Œṗḍ⁵ẠƇL

```

A monadic Link that accepts a positive integer and yields a positive integer.

**Try it online!**

### How?

```
Œṗḍ⁵ẠƇL - Link: integer, Cents        e.g. 4
Œṗ      - integer partitions of Cents      [[1,1,1,1],[1,1,2],[1,3],[2,2],[4]]
   ⁵    - ten                              10
  ḍ     - divides? (vectorises)            [[1,1,1,1],[1,1,1],[1,0],[1,1],[0]]
     Ƈ  - keep those for which:
    Ạ   -   all?                           [[1,1,1,1],[1,1,1],      [1,1]    ]
      L - length                           3

```
> 3 votes

# Answer
# Python 2, 49 bytes

```
f=lambda n,k=10:k*n>0and f(n-k,k)+f(n,k/2)or n==0

```

Try it online!

Conveniently, we can iterate through the count value by starting at 10 and floor-dividing by 2 to get `10->5->2->1` and terminating at 0.
> 2 votes

# Answer
# 05AB1E, ~~13~~ 10 bytes

```
ÅœʒTÑsåP}g

```

Try it online.

A modification of Mr.Xcoder's 05AB1E answer in the related challenge would be 1 byte longer (and way slower):

```
TÑIиæ€{ÙOI¢

```

Try it online. (Too slow for TIO for \\$n\ge4\\$.)

**Explanation:**

```
Åœ           # Get all lists of positive integers that sum to the (implicit) input
  ʒ          # Filter this list of lists by:
             #  (implicitly push the current list)
   TÑ        #  Push the divisors of 10: [1,2,5,10]
     s       #  Swap so the current list is at the top of the stack
      å      #  Check for each value whether it's in list [1,2,5,10]
       P     #  Check if it's truthy for all of them by taking the product
  }g         # After the filter: pop and push the length
             # (which is output implicitly as result)

TÑ           # Push list [1,2,5,10]
  Iи         # Repeat it the input amount of times: [1,2,5,10,1,2,5,10,...]
    æ        # Get the powerset of this list
     €{      # Sort each inner list
       Ù     # Uniquify the list of lists
        O    # Sum each inner list
         I¢  # Count how many times the input occurs in the list
             # (which is output implicitly as result)

```
> 1 votes

# Answer
# Charcoal, 26 bytes

```
Ｎθ⊞υ⁰Ｆ9410ＦυＦ‹κθ⊞υ⁺κ⊕ιＩ№υθ

```

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

```
Ｎθ

```

Input `n`.

```
⊞υ⁰

```

Start with `0` as a possible amount.

```
Ｆ9410

```

Loop over the digits `9`, `4`, `1`, and `0`, which will later be incremented to represent the coins `10`, `5`, `2` and `1`.

```
Ｆυ

```

Loop over each possible amount discovered so far.

```
Ｆ‹κθ

```

If this amount is less than `n`, then...

```
⊞υ⁺κ⊕ι

```

... add the current coin to the amount, and record this as a new possible amount. This then allows it to be considered again as a possible amount for the current coin, until the value reaches or exceeds `n`.

```
Ｉ№υθ

```

Count the number of times `n` was reached.

Example for `n=5`:

* Start with `0` as an amount.
* Add `10` to that, resulting in a new amount of `10`. This amount is now more than `5`, so it is ignored.
* Add `5` to the `0` amount, resulting in a new amount of `5`. This amount is also ignored for now.
* Add `2` to the `0` amount, resulting in a new amount of `2`.
* Add `2` to the `2` amount, resulting in a new amount of `4`.
* Add `2` to the `4` amount, resulting in a new amount of `6`. This amount is now more than `5`, so it is ignored.
* Add `1` to the `0`, `2` and `4` amounts, resulting in new amounts of `1`, `3` and `5`. The `5` amount is ignored for now.
* Add `1` to the `1` and `3` amounts, resulting in new amounts of `2` and `4`.
* Add `1` to the `2` and `4` amounts, resulting in new amounts of `3` and `5`.
* Add `1` to the `3` amount, resulting in a new amount of `4`.
* Add `1` to the `4` amount, resulting in a new amount of `5`.
* There are no more coins, so the final count of `5`s is `4` as desired.
* The `4` `5`s correspond to the sums `5`, `2+2+1`, `2+1+1+1` and `1+1+1+1+1` respectively.

The coins are considered in descending order for efficiency but the algorithm would work with the coins in any order.
> 1 votes

# Answer
# Ruby, 46 bytes

```
f=->n,k=10{n<0||k<1?0:n<1?1:f[n-k,k]+f[n,k/2]}

```

Try it online!

Shamelessly inspired by Arnauld's Javascript answer.
> 1 votes

# Answer
# Desmos, 76 bytes

```
f(n)=1+∑_{k=1}^{n^4}0^{(n-∑_{j=1}^4[1,2,5,10][j]mod(floor(nk/n^j),n))^2}

```

Inspired by @fireflame's Desmos answer to How many partitions do I have?

Try It On Desmos!

Try It On Desmos! - Prettified
> 1 votes

# Answer
# Prolog (SWI), 66 bytes

```
N+K+M:-K*N>0,N-K+K+Q,N+K//2+W,M is Q+W;N=:=0,M=1;M=0.
N+M:-N+10+M.

```

Try it online!

Port of xnor's Python answer.
> 1 votes

# Answer
# Scala, 131 bytes

Golfed version. Try it online!

```
def f(n:Int,p:Seq[Int]=Seq(1,2,5,10)):Int=(n,p)match{case(0,_)=>1;case(_,Nil)=>0;case(_,k::ks)=>if(n<k)0 else f(n-k,k::ks)+f(n,ks)}

```

Ungolfed version. Try it online!

```
object Main {
  def a000008(n: Int): Int = {
    val coins = List(1, 2, 5, 10)

    def p(ks: List[Int], m: Int): Int = (ks, m) match {
      case (_, 0)         => 1
      case (Nil, _)       => 0
      case (k :: ksTail, _) if m < k => 0
      case (ksHead :: ksTail, _)     => p(ksHead :: ksTail, m - ksHead) + p(ksTail, m)
    }

    p(coins, n)
  }

  def main(args: Array[String]): Unit = {
    for (n <- 1 to 20) {
      println(s"p($n) = ${a000008(n)}")
    }
  }
}

```
> 1 votes

---
Tags: code-golf, number, sequence, integer-partitions
---


title: Sum of partition numbers

text:
# Question
Title: Sum of partition numbers
**The partition function:**

> In number theory, the partition function *p(n)* represents the number of possible partitions of a positive integer *n* into positive integers

For instance, *p(4)* = 5 because the integer 4 has five possible partitions:

* 1 + 1 + 1 + 1
* 1 + 1 + 2
* 1 + 3
* 2 + 2
* 4

**Your task:**

* Accept an input (let's call it *n*). It will be a positive integer.
* Find the sum of the partitions of the numbers from 1 to n and output it.

**Example:**

Given the input 5:

* p(1) = 1
* p(2) = 2
* p(3) = 3
* p(4) = 5
* p(5) = 7

Sum = 18

**As this is , the shortest answer in bytes wins.**

I'll add my attempt as an answer, but it can probably be golfed down a bit.

# Answer
# Vyxal `l`, 4 bytes

```
vṄÞf

```

Try it Online!

Partitions of each number in the range 1...input, flatten one layer, l flag takes length of that.

Alternatively,

## 5 bytes

```
ƛṄL;∑

```

Try it Online!

3 bytes with `s` flag

## Explained

```
ƛṄL;∑
ƛ  ;   # Over each number in the range [1, input]:
 ṄL    #   Get the number of partitions of that number
    ∑  # Take the sum of that list.

```
> 2 votes

# Answer
# Prolog (SWI), 56 bytes

```
N+I+R:-I>N,R=0;N-I+I+Q,N+(I+1)+W,R is Q+W+1.
X+R:-X+1+R.

```

Try it online!

Using Arnauld's formula again.

-1 thanks to Jo King
> 6 votes

# Answer
# JavaScript (ES6), 35 bytes

```
f=(n,i=1)=>i<=n&&f(n-i,i)-~f(n,i+1)

```

Try it online!

### Recursive formula

The sum of the partitions of the numbers from \\$1\\$ to \\$n\\$ is given by \\$f(n,1)\\$ where:

$$f(n,i)=\begin{cases} 0&\text{if }i\>n\\ f(n-i,i)+f(n,i+1)+1&\text{if }i\le n \end{cases}$$
> 4 votes

# Answer
# Desmos, 75 bytes

```
f(N)=N+∑_{n=1}^N∑_{k=1}^{n^n}0^{(n-∑_{j=1}^njmod(floor(nk/n^j),n))^2}

```

It's times like this when I really wish Desmos supported recursion... a majority of the other answers are just using some super golfy recursive formula...

Try It On Desmos!

Try It On Desmos! - Prettified

---

Me when no Desmos Recursion
> 4 votes

# Answer
# Python, 97 88 bytes

```
lambda n:sum(map(f,range(1,n+1)))
f=lambda n,k=1:1+sum(f(n-j,j)for j in range(k,n//2+1))

```

(-9 thanks to 97.100.91.109)

Try it online!
> 3 votes

# Answer
# Wolfram Language (Mathematica), 22 bytes

```
Tr@*PartitionsP@*Range

```

Try it online!
> 3 votes

# Answer
# Python,  ~~58 48~~  42 bytes

-6 thanks to Steffan!

```
f=lambda n,b=1:b<=n and f(n-b,b)-~f(n,b+1)

```

**Try it online!**
> 3 votes

# Answer
# Charcoal, ~~43~~ ~~42~~ ~~41~~ ~~40~~ ~~39~~ 20 bytes

```
Ｆ⊕Ｎ⊞υＥ⮌υ⊕↨¹✂κλι¹ＩΣ⊟υ

```

Try it online! Link is to verbose version of code. Explanation: Vaguely based on @Arnauld's formula, but there's not much of it left.

```
Ｆ⊕Ｎ

```

Loop from `0` to `n`. (This part of the algorithm actually works for `n=0`, but it costs 1 byte to output the final result correctly.)

```
⊞υＥ⮌υ⊕↨¹✂κλι¹

```

Calculate the incremented sums of the upper right triangle of the reversed matrix so far and add that as the next row.

```
ＩΣ⊟υ

```

Output the sum of the last row.

Example:

For `n=0` we don't have any thing so far so we just create an empty row. The final matrix conceptually looks like this:

```
 0 ...

```

For `n=1` there is only one empty row so far so its sum is zero. This results in a row of `[1]`, with the matrix now like this:

```
 0 0 ...
 1 0 ...

```

For `n=2` there are two rows. For the second row we take the sum of all of the elements but for the first row we omit the first element. Incrementing results in `[2, 1]`, with the matrix now like this:

```
 0 0 0 ...
 1 0 0 ...
 2 1 0 ...

```

For `n=3` the triangle's rows are `[2, 1, 0]`, `[0, 0]` and `[0]`, giving incremented sums of `[4, 1, 1]`, with the matrix now like this:

```
 0 0 0 0 ...
 1 0 0 0 ...
 2 1 0 0 ...
 4 1 1 0 ...

```

For `n=4` the triangle's rows are `[4, 1, 1, 0]`, `[1, 0, 0]`, `[0, 0]` and `[0]`, giving incremented sums of `[7, 2, 1, 1]`, with the matrix now like this:

```
 0 0 0 0 0 ...
 1 0 0 0 0 ...
 2 1 0 0 0 ...
 4 1 1 0 0 ...
 7 2 1 1 0 ...

```

For `n=5` the triangle's rows are `[7, 2, 1, 1, 0]`, `[1, 1, 0, 0]`, `[0, 0, 0]`, `[0, 0]` and `[0]` with incremented sums of `[12, 3, 1, 1, 1]`, with the matrix now like this:

```
 0 0 0 0 0 0 ...
 1 0 0 0 0 0 ...
 2 1 0 0 0 0 ...
 4 1 1 0 0 0 ...
 7 2 1 1 0 0 ...
12 3 1 1 1 0 ...

```

For `n=6` the triangle's rows are `[12, 3, 1, 1, 1, 0]`, `[2, 1, 1, 0, 0]`, `[1, 0, 0, 0]`, `[0, 0, 0]`, `[0, 0]` and `[0]` with incremented sums of `[19, 5, 2, 1, 1, 1]`, with the matrix now like this:

```
 0 0 0 0 0 0 0 ...
 1 0 0 0 0 0 0 ...
 2 1 0 0 0 0 0 ...
 4 1 1 0 0 0 0 ...
 7 2 1 1 0 0 0 ...
12 3 1 1 1 0 0 ...
19 5 2 1 1 1 0 ...

```

The full row sums are the partition sums are desired. The first column is also `A000070`.
> 3 votes

# Answer
# Haskell,  ~~31~~  30 bytes

```
n!i|i>n=0|z<-n-i=1+z!i+n!(i+1)

```

Try it online!

Thanks to Arnauld for the formula from their answer.

-1 thanks to xnor.
> 3 votes

# Answer
# PARI/GP, 25 bytes

```
n->sum(i=1,n,numbpart(i))

```

Attempt This Online!
> 2 votes

# Answer
# Jelly, 5 bytes

```
ŒṗL)S

```

**Try it online!**

---

Or

```
Œṗ€ẎL

```
> 2 votes

# Answer
# C (gcc), ~~49~~ ~~48~~ 35 bytes

```
i;f(n){n=i<n?i++,f(n)-~f(n-i--):0;}

```

Try it online!

*Uses Arnauld's formula from his JavaScript answer.*
*Saved a byte thanks to Steffan!!!*
*Saved a whopping 13 bytes thanks to tsh!!!*

Inputs positive integer \\$n\\$.
Returns the sum of partitions \\$\displaystyle\sum\limits\_{i=1}^n p(i)\\$.
> 2 votes

# Answer
# Regex  (RME / Perl / PCRE2 v10.35+ / Raku`:P5`), ~~16~~ 11 bytes

```
(\1x*|^x+)+

```

Try it on replit.com \- RegexMathEngine
Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
Attempt This Online! \- PCRE2 v10.40+
Try it online! \- Raku

Takes its input in unary, as the length of a string of `x`s. Returns its output as the number of ways the regex can match. (The rabbit emoji indicates this output method.)

This simply enumerates all the partitions that add up to less than or equal to the input number. In order to count unordered partitions, it enforces that partitions occur in strictly nondecreasing order. This is accomplished by starting with an arbitrary positive-sized partition on the first iteration, and adding an arbitrary nonnegative integer to the partition size on each iteration.

This differs conceptually from How many partitions do I have? in that the first iteration is forced to have positive size (to prevent p(0)=1 from being added to the total) and that there is no ending `$` anchor.

```
                # tail = N = input number; no need to anchor, because the
                # following loop is forced to do at least one iteration,
                # and its first iteration has an anchor.
(               # \1 = the following:
    \1x*        # Previous value of \1, plus any arbitrary nonnegative integer,
                # if this is not the first iteration.
|           # or
    ^x+         # Any arbitrary positive integer, if this is the first iteration.
)+              # Iterate the above any positive number of times.

```

A more natural way for this function to work would be to sum p(0)...p(n), rather than p(1)...p(n). This would result in the 11 byte regex `((\1|^)x*)+`, which returns a number 1 greater than the function asked for by this challenge.

# Regex  (RME / Perl / PCRE), 20 bytes

```
((?=(\3|^x))(\2x*))+

```

Try it on replit.com \- RegexMathEngine
Try it online! \- Perl v5.28.2 / Attempt This Online! \- Perl v5.36+
**Try it online! \- PCRE1
Try it online! \- PCRE2 v10.33** / Attempt This Online! \- PCRE2 v10.40+

PCRE1, and PCRE2 up to v10.34, automatically makes any capture group atomic if it contains a nested backreference. To work around this, the capture is copied between `\2` and `\3` using only forward-declared backreferences.

This would also make the regex compatible with Python`regex` and Ruby, but they have no way of doing  output without source code modifications.

```
                      # tail = N = input number; no need to anchor, because the
                      # following loop is forced to do at least one iteration,
                      # and its first iteration has an anchor.
(
    (?=
        (             # \2 = the following:
            \3        # Previous value of \3, if \3 is set
        |         # or
            ^x        # 1, if on the first iteration
        )
    )
    (                 # \3 = the following, which is also subtracted from tail:
        \2x*          # \2 plus any arbitrary nonnegative integer
    )
)+                    # Iterate the above as many times as possible, minimum 1

```

# Perl, ~~41~~ 36 bytes (full program)

```
1x<>~~/(\1.*|^.+)+(??{-++$i})/;say$i

```

Try it online!

Unlike all of my other Perl answers of this type so far, the regex in this one is not `$`-anchored at the end, so `(??{++$i))` so no longer guaranteed not to match. It can in fact match if the regex hasn't reached the end of the string and `$i` is `1`, `11`, or any other number whose digits are all `1` in decimal. So a negative sign is added to the return value to guarantee that this "postponed" regular subexpression embedded code block will not match.

Alternative 36 bytes:

```
1x<>~~/(\1.*|^.+)+(??{-++$\})/;print

```

Try it online!

# Perl `-p`, ~~37~~ 32 bytes (full program)

```
1x$_~~/(\1.*|^.+)+(??{-++$\})/}{

```

Try it online!

Can only take one input (followed by EOF) per run. See Fibonacci function or sequence for an explanation.

# Raku, 27 bytesSBCS (anonymous function)

```
{+m:ex:P5/(\1.*|^.+)+/}o¹x*

```

Try it online!
> 2 votes

# Answer
# Scala, 58 bytes

Use the recursive formula proposed in @Arnauld's answer.

---

Try it online!

```
def f(n:Int,i:Int=1):Int=if(i>n)0 else f(n-i,i)+f(n,i+1)+1

```
> 2 votes

# Answer
# PowerShell Core, 61 bytes

```
filter f{param($i=1)if($i-le$_){($_-$i|f $i)+($_|f($i+1))+1}}

```

Try it online!

A recursive filter, this is an implementation of Arnauld's javascript answer
> 1 votes

# Answer
# 05AB1E, 6 bytes

```
LÅœ€gO

```

Try it online.

**Explanation:**

```
L       # Push a list in the range [1, (implicit) input-integer]
 Åœ     # Map each to a list of list of positive integers that sum to that value
   €g   # Get the length of each inner list
     O  # Sum those together
        # (after which the result is output implicitly)

```
> 1 votes

# Answer
# Pyt, 3 bytes

```
řᵱƩ

```

Try it online!

```
ř           implicit input; řangify
 ᵱ          ᵱartition number of each element in the array
  Ʃ         Ʃum; implicit print

```
> 1 votes

# Answer
# x86-64 machine code, 24 bytes

```
31 C0 89 F9 51 57 29 CF 76 06 E8 F5 FF FF FF F8 83 D8 FF 5F 59 E2 ED C3

```

Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes n in EDI and returns a value in EAX.

In assembly:

```
f:
    xor eax, eax    # Set EAX to 0.
    mov ecx, edi    # Set ECX to n.
recursion:
            # Starting here will add to EAX the number of partitions of 1,...,n,
            #  but with the numbers within the partitions limited to ECX.
    push rcx        # Save RCX and RDI (the 64-bit registers containing ECX and EDI)
    push rdi        #  onto the stack.
    sub edi, ecx    # Subtract the limit value from n,
                    #  to try including that value in a partition.
    jbe skip        # Jump if the result is 0 or negative.
    call recursion  # Make a recursive call (if it is positive).
    clc             # Set CF to 0.
skip:
    sbb eax, -1     # Subtract -1+CF from EAX. This increases it by 1 if CF=0:
                    #  if the result of the earlier 'sub' was not negative,
                    #  which means the limit value on its own is a valid partition.
    pop rdi         # Restore RCX and RDI
    pop rcx         #  from the stack.
    loop recursion  # Subtract 1 from ECX, and jump back to repeat if it's nonzero.
    ret             # Return.

```
> 0 votes

---
Tags: code-golf, number-theory, integer-partitions
---


# Question
Title: Find Index of Rational Number in Calkin-Wilf Sequence
*Related*

From Wikipedia:

> In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond one-to-one to the positive rational numbers. The tree is rooted at the number \\$1\\$, and any rational number expressed in simplest terms as the fraction \\$\frac{a}{b}\\$ has as its two children the numbers \\$\frac{a}{a+b}\\$ and \\$\frac{a+b}{b}\\$.
>
> The Calkin–Wilf sequence is the sequence of rational numbers generated by a breadth-first traversal of the Calkin–Wilf tree, $$\frac11, \frac12, \frac21, \frac13, \frac32, \frac23, \frac31, \frac14, \frac43, \frac35, \frac52, \ldots$$

For this challenge, you are given a fraction found in the \\$i\\$th position of the Calkin-Wilf sequence, and must output \\$i\\$. You can start from either 0 or 1.

## Test cases

(Starting from 1.)

| \\$a\_i\\$ | \\$i\\$ |
| --- | --- |
| \\$\frac11\\$ | \\$1\\$ |
| \\$\frac13\\$ | \\$4\\$ |
| \\$\frac43\\$ | \\$9\\$ |
| \\$\frac34\\$ | \\$14\\$ |
| \\$\frac{53}{37}\\$ | \\$1081\\$ |
| \\$\frac{37}{53}\\$ | \\$1990\\$ |

Standard loopholes are forbidden. Since this is , the shortest code wins.

# Answer
> 15 votes
# JavaScript (ES6), 33 bytes

Expects a pair of integers `(p,q)` representing the fraction \\$p/q\\$.

```
f=(p,q)=>p&&1+f(q+p-(q%p||p)*2,p)

```

Try it online!

### How?

This version is based on the nice recurrence formula found by alephalpha:

$$\begin{align}f(0)&=0\\f(x)&=1+f(2\lceil1/x\rceil-1-1/x)\end{align}$$

It was modified to work with two integers \\$p/q=x\\$ instead of a native fraction and without an explicit ceiling function:

$$\lceil q/p\rceil=\begin{cases} q/p,&q\equiv 0\pmod p\\ (q+p-(q \bmod p))/p,&q\not\equiv 0\pmod p\end{cases}$$

We have:

$$f(2\lceil1/x\rceil-1-1/x)=f(2\lceil q/p\rceil-p/p-q/p)$$

which is turned into the following JS code:

```
f(q % p ? q + p - q % p * 2 : q - p, p)

```

which can be further simplified to:

```
f(q + p - (q % p || p) * 2, p)

```

---

# JavaScript (ES6), 40 bytes

Expects a pair of integers `(p,q)` representing the fraction \\$p/q\\$.

```
f=(p,q)=>p-q?p>q?f(p-q,p)+1:2*f(p,q-p):1

```

Try it online!

### Commented

```
f = (p, q) =>   // (p, q) = input pair
p - q ?         // if p is not equal to q:
  p > q ?       //   if p is greater than q:
                //     we're located on the right branch
    f(p - q, p) //     turn it into the corresponding left branch
    + 1         //     and add 1
  :             //   else:
                //     we're located on the left branch
    2 *         //     double the result of
    f(p, q - p) //     a recursive call with the parent fraction
:               // else:
                //   we've reached the root
  1             //   stop and return 1

```

# Answer
> 13 votes
# PARI/GP, 29 bytes

```
f(x)=if(x,1+f(-1\-x*2-1-1/x))

```

Attempt This Online!

\\$\begin{align}f(0)&=0\\f(x)&=1+f(2\lceil1/x\rceil-1-1/x)\end{align}\\$

# Answer
> 10 votes
# Vyxal, 12 bytes

```
g-¨£∨)↔vÞṘṘB

```

Try it Online!

Takes input as a pair of numbers.

```
g-¨£∨)↔vÞṘṘB

             # function taking a pair and returning its parent:
g-           #   subtract minimum
  ¨£∨        #   zip and return the last truthy element from each pair
     )       # end function
      ↔      # apply until fixed point and collect intermediate results
       vÞṘ   # vectorizing is sorted in reverse?
          Ṙ  # reverse
           B # convert from binary

```

# Answer
> 9 votes
# Python, 34 bytes (@Neil)

```
f=lambda Q:Q and 1+f(1/Q-1-2/Q%-2)

```

Attempt This Online!

Port of @Arnauld's latest and greatest which ports @alephalpha's.

Expects a Python Fraction object.

#### Previous Python, 44 bytes (@xnor)

```
f=lambda Q:Q==1or(Q>1)+2*f(max(Q/(1-Q),Q-1))

```

Attempt This Online!

#### Original Python, 46 bytes

```
f=lambda Q:Q==1or(Q>1)+2*f([Q/(1-Q),Q-1][Q>1])

```

Attempt This Online!

Expects a Python Fraction object.

Similar but as far as I can tell not identical to @Arnauld's approach.

# Answer
> 6 votes
# , 24 bytes

```
*`(1+%$:@-~_1+2*>.@%)@.*

```

-4, port of @Jo King's answer, which is a port of @loopy walt's, which is a port of @Arnauld's, which is a port of @alephalpha's.

Attempt This Online!

```
*`(1+%$:@-~_1+2*>.@%)@.*
                       *  NB. signum, 0 for 0, 1 for everything else
                     @.   NB. index into the gerund list and execute
*                         NB. if 0, use signum again to return 0
  (                 )     NB. if 1, execute the recursive function
                          NB. uses the formula in alephalpha's PARI/GP answer
      $:@                 NB. recurse here

```

### Original 28 bytes

```
[:#[(1%1+]-~2*<.@])^:~:^:a:*

```

In short, returns the length of the sequence up to the input. Expects a rational number.

Attempt This Online!

```
[:#[(1%1+]-~2*<.@])^:~:^:a:*
                           *  NB. signum, returns 1 for all inputs to give initial value
   [                          NB. input unchanged
    (             )^:~:^:a:   NB. form for a do-while that uses a: to collect results into an array
                              NB. u^:v^:_ v is a boolean function and u modifies the initial value
                         a:   NB. empty box
                     ~:       NB. continue if input is not equal to current value
              <.@]            NB. floor the right arg (qᵢ)
            2*                NB. double
         ]-~                  NB. subtract by qᵢ
       1+                     NB. increment
     1%                       NB. reciprocal
[:                            NB. then
  #                           NB. take the length

```

# Answer
> 6 votes
# Raku, 25 bytes

```
+*o{{1/$_-1-2/$_%-2}...0}

```

Try it online!

Port of @loopy walt's answer, which is a port of @Arnauld's, which is a port of @alephalpha's.

# Answer
> 5 votes
# Arturo, 49 bytes

```
f:$[p q][(p=q)?->1->(p>q)?->1+f p-q p->2*f p q-p]

```

Try it

Port of Arnauld's JavaScript answer.

# Answer
> 5 votes
# Rust, ~~91~~ ~~84~~ ~~81~~ 77 bytes

Based on the recursive relation:

$$ a\_n = b\_{n-1} $$ $$ b\_n = 2\cdot b\_{n-1} \cdot \left \lfloor \frac{a\_{n-1}}{b\_{n-1}} \right \rfloor - a\_{n-1} + b\_{n-1}$$

0-indexed. Recursion is very verbose in rust so I hope this is shorter than the recursive version most other answers use.

```
|m|{let mut d=(1,1,1);while(d.0,d.1)!=m{d=(d.1,d.0+d.1-d.0%d.1*2,d.2+1)};d.2}

```

Attempt This Online!

# Answer
> 5 votes
# Jelly, 11 bytes

Uses AndrovT's method from their Vyxal answer, go upvote!

```
_ṂoƊƬ</€¬ṚḄ

```

A monadic Link that accepts a pair of co-prime positive integers, `[numerator, denominator]` and yields the 1-indexed index of that fraction in

**Try it online!**

### How?

```
_ṂoƊƬ</€¬ṚḄ - Link: pair of positive, coprime integers, [N,D]
    Ƭ       - start with C=[N,D] and collect until a fixed-point applying:
   Ɗ        -   last three links as a monad - f([N,D]):
 Ṃ          -     minimum ([N,D])
_           -     ([N,D]) subtract (that) (vectorises)   -> [0,D-N] or [N-D,0]
  o         -     (that) logical OR ([N,D]) (vectorises) -> [N,D-N] or [N-D,D]
       €    - for each ([numerator, denominator] pair in the collected results):
      /     -   reduce by:
     <      -     is (the numerator) less than (the denominator)?
        ¬   - logical NOT (vectorises)
         Ṛ  - reverse
          Ḅ - convert from binary

```

---

Loads of \\$11\\$s, is there a \\$10\\$?

e.g.:

```
_ṂoƊƬṚUṢƑ€Ḅ
_ṂoƊƬṚZ</¬Ḅ
_ṂoƊƬIF<1ṚḄ

```

# Answer
> 4 votes
# Prolog (SWI), ~~59~~ 53 bytes

*Thanks @Jo King for -6 bytes and fixing the floating point issue*

```
0+0.
N+X:-A is 2*ceiling(1/N)-1-1rdiv N,A+B,X is B+1.

```

Took the recursive formula from @alephalpha's answer, so make sure to upvote his answer as well!

Try it online!

# Answer
> 3 votes
# Charcoal, ~~34~~ 24 bytes

```
ＮθＮηＷθ«≦⁻⁻η⊗﹪η±θθ≔ιη→»Ｉⅈ

```

Try it online! Link is to verbose version of code. 1-indexed. Takes input as two integers. Explanation: Port of @Arnauld's port of @alephalpha's answer.

```
ＮθＮη

```

Input the numerator and denominator.

```
Ｗθ«

```

Repeat until the numerator is zero.

```
≦⁻⁻η⊗﹪η±θθ

```

Calculate the next numerator. This uses true modulus, so instead of writing `q + p - (q % p || p)` I can write `q - q % -p`; the final expression is then `q - q % -p * 2 - p`.

```
≔ιη

```

Save the copy of the numerator that conveniently happens to be in the loop variable to the denominator.

Increment the count.

```
»Ｉⅈ

```

Output the final count.

Previous 34-byte version based on @AndrovT's answer:

```
≔Ｅ²ＮθＷ↨θ±¹«⊞υ‹ι⁰ＵＭθ∨⁻κ⌊θκ»⊞υ¹Ｉ↨⮌υ²

```

Try it online! Link is to verbose version of code. 1-indexed. Takes input as two integers. Explanation:

```
≔Ｅ²Ｎθ

```

Input the fraction.

```
Ｗ↨θ±¹«

```

Repeat until the numerator and denominator are equal.

```
⊞υ‹ι⁰

```

If the numerator was larger than push a `1` bit otherwise push a `0` bit.

```
ＵＭθ∨⁻κ⌊θκ»

```

Subtract the smaller element from the larger.

```
⊞υ¹

```

Push a final `1` bit.

```
Ｉ↨⮌υ²

```

Convert from base `2`.

I could have done better by generating the sequence (~~36~~ 33 bytes):

```
≔⮌Ｅ²ＮθＦ²⊞υ¹Ｗ¬⁼θυ«≔⁺⁻Συ⊗﹪⊟υυυυ→»Ｉⅈ

```

Try it online! Link is to verbose version of code. 0-indexed. Takes input as two integers. Explanation:

```
≔⮌Ｅ²Ｎθ

```

Input the fraction in reverse.

```
Ｆ²⊞υ¹

```

Start with `1` as the fraction.

```
Ｗ¬⁼θυ«

```

Repeat until the fraction is found.

```
≔⁺⁻Συ⊗﹪⊟υυυυ

```

Find the next fraction. (And yes, that is legitimately `4` `υ`s in a row.)

Increment the loop count.

```
»Ｉⅈ

```

Output the final count.

# Answer
> 3 votes
# Scala, 72 bytes

Golfed version. Try it online!

```
def f(p:Int,q:Int):Int=if(p-q!=0)if(p>q)f(p-q,p)+1 else 2*f(p,q-p)else 1

```

Ungolfed version. Try it online!

```
object Main {
  def main(args: Array[String]): Unit = {
    def f(p: Int, q: Int): Int = {
      if (p - q != 0) {
        if (p > q) {
          f(p - q, p) + 1
        } else {
          2 * f(p, q - p)
        }
      } else {
        1
      }
    }

    println(f(1,1))
    println(f(1,3))
    println(f(4,3))
    println(f(3,4))
    println(f(53,37))
    println(f(37,53))
  }
}

```

# Answer
> 3 votes
# Ruby, ~~38~~ 28 bytes

```
->m{m>0?1+f[1/m-1-2/m%-2]:0}

```

Try it online!

Using @alephalpha/@Arnauld formula like most of the answers.

# Answer
> 3 votes
# \>\<\>, 36 bytes

```
ii$\l2-nao;
:?!\$&:::&+:@$:@%:?$~2*-

```

Try it online!

Port of Arnauld's answer. Takes input as codepoints, e.g. 53/37 is `5%`

# Answer
> 2 votes
# \>\<\> (Fish), 59 bytes

```
1ii11$4[:{:{:{:\
@=r@={+2(?v]{n;\
*-+{1+}40.\r{]$:@$:@$:@%2

```

Try it

Despite not having a easy way to check tuple equality still shorter than rust. Uses the formula Neil suggested under my Rust answer.

## Explanation

`1ii11` pushes the initial state.

`$4[:{:{:{:@=r@={+2(?vr{]` Checks if the 2 tuples are equal

`$:@$:@$:@$2*-+` Performs the basic calculation of the next value for `B`

`{1+}` Adds one to the counter

`]{n;` Prints the result and exits, if the tuples are equal.

---
Tags: code-golf, math, rational-numbers
---


title: String Array to JSON String

text:
# Question
Title: String Array to JSON String
# Introduction

I've seen throughout the code-golf challenges several simple tasks involving JSON, such as interpreting JSON strings with RegExs, and almost every other manipulation I could think of.

In a binding for AppleScript that I was using for a Node project, I noticed that objects would be returned in a strange way: there would be an array of properties in string form, instead of a JSON object being returned as expected. This is where the challenge comes in...

# Algorithm

1. Add `{` to beginning of the output string
2. Iterate over all entries, adding them to the output string, delimited by `,`
3. Add `}` to the end of the output string
4. Print out the output string

# Challenge

Make this strange return format usable. Convert an array of JSON `'key:value'`s (in string form) to a full JSON object string.

# Rules

* Any language that can do string manipulations allowed
* Must print out JSON string with surrounding curly braces `{}`, and double quotes `""` around string values **AND** all properties (`"property":"value"` or `"property":3.14`, etc.)
* Must return a valid, parseable JSON string
* Lowest byte count wins per language

# Example Input and Output

Input:

> \['prop1:"val1"', 'prop2:12', 'prop3:3.14', 'prop4:false'\]

Output:

> '{"prop1":"val1", "prop2":12, "prop3":3.14, "prop4":false}'

# Answer
> 1 votes
# Retina, 23 bytes

```
%0`\w+
"$&"
¶
,
.+
{$&}

```

Try it online! Explanation:

```
%0`\w+
"$&"

```

Quote all of the keys.

```
¶
,

```

Join the array elements together.

```
.+
{$&}

```

Wrap the result in brackets. This can also be done using the following code for the same byte count:

```
^
{
$
}

```

# Answer
> 2 votes
# JavaScript (Node.js), 35 bytes

```
a=>JSON.stringify(eval(`({${a}})`))

```

Try it online! 43 bytes without builtins:

```
a=>`{${a.map(s=>s.replace(/\w+/,`"$&"`))}}`

```

Try it online!

# Answer
> 1 votes
# C 108

**Thanks to Jonathan Frech this answer is now incredibly shorter**
**Thanks to @ceilingcat for some very nice pieces of golfing - now even shorter**

```
i;main(c,v)char**v;{for(;++i<c;printf("%c\"%s\":%s",!~-i*79+44,v[i],++*v))*(*v=index(i[v],58))=0;puts("}");}

```

Try it online!

# Answer
> 1 votes
# Scala, 79 bytes

Essentially Neil's JS solve.

---

Try it online!

```
def f(a:Seq[String])="{"+a.map(_.replaceAll("\\w+","\"$0\"")).mkString(",")+"}"

```

# Answer
> 0 votes
# Python 3, 59 bytes

```
lambda x:"{%s}"%",".join('"'+a.replace(":",'":')for a in x)

```

Try it online!

-6 bytes thanks to ovs

# Answer
> 0 votes
# Lua, 122 bytes

```
loadstring[[s="{"for i,v in ipairs(...)do x,y=v:match("(.-):(.+)")s=s.."\""..x.."\":"..y..","end return s:sub(1,-2).."}"]]

```

Try it online!

---

This is an anonymous function. It technically doesn't "print out JSON string \[...\]", but instead it returns this string, so that when calling it you could print. I did that because **I needed to first convert the input from string to an actual list**, and I did that on the argument of the function call.

**If this makes my answer invalid** I'll move the string to table (list) "parser" from the footer to the actual code. **But I don't think it should**, because the input shown as a table, so the code that takes a string and transforms it into a table shouldn't count.

# Answer
> 0 votes
# POSIX sh (sed + ShellShoccar-jpn/Parsrs makrj.sh), 33 bytes

Assumes values may have colons but properties shall never have colons, spaces, tabs, or periods.

```
sed 's/\([^:]*\):/.\1 /'|makrj.sh

```

## Usage

Input via standard input. Each line represents each item of an array.

## Commented

```
# "prop:item"
sed 's/\([^:]*\):/.\1 /'|
# ".prop item" is JSONPath-value format
makrj.sh
# JSON object

```

## Example run on Termux

```
~ $ sh makrj.sh -h
Usage : makrj.sh [JSON_value_textfile]
Wed Sep 14 22:19:55 JST 2016
~ $ cat jsss;echo;cat jsss | sed 's/\([^:]*\):/.\1 /'|sh makrj.sh
prop1:"val1"
prop2:12
prop3:3.14
prop4:false

{
"prop1":"val1",
"prop2":12,
"prop3":3.14,
"prop4":false
}
~$

```

# Answer
> 0 votes
# Go, 116 bytes

```
import."strings"
func f(s[]string)string{for i,l:=range s{s[i]=`"`+Replace(l,`:`,`":`,1)}
return"{"+Join(s,",")+"}"}

```

Attempt This Online!

# Answer
> 0 votes
# Ruby, ~~41~~ 40 bytes

```
->a{?{+a.map{_1.sub /\w+/,'"\&"'}*?,+?}}

```

Essentially Neil's JS solve.

Attempt This Online!

---
Tags: code-golf, string, array, json
---