title: Sort this, quick!

text:
# Question
Title: Sort this, quick!
Well... there are 59 (now 60) questions tagged , but no simple quicksorts.

That must be fixed.

For those unfamiliar with quicksort, here is a breakdown, courtesy of Wikipedia-

1. Pick an element, called a **pivot**, from the array.
2. Reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

# Rules

The rules are simple:

* Implement a numerical quicksort in the programming language of your choice.
* The pivot should be chosen at random *or* with median of three (1st, last, and middle element).
* Your program can be a complete program or function.
* You can get the input using STDIN, command line args, or function parameters. If using a string input, the input is space separated.
* The input may contain decimal and negative values. However, there will be no duplicates.
* You may output to STDOUT or by returning from the function.
* No built-in sorting (or sorting related) functions or standard loopholes.
* The list may be an arbitrary length.

Bonus #1: On lists or sub-lists of length \<= 5, use insertion sort to speed things up a bit. Reward: -15%.

Bonus #2: If your language supports concurrency, sort the list in parallel. If you are using an insertion sort on sub-lists, the final insertion sort doesn't need to be in parallel. Built in thread pools/ thread scheduling are allowed. Reward: -15%.

Note: Median of three was confusing some people, so here is an explanation, courtesy of (again) Wikipedia:

> choosing the median of the first, middle and last element of the partition for the pivot

# Scoring

This is . Base score is in bytes. If you got one bonus, take 15% off that number. If you got both, take 30% off. That really sounds like a sales pitch.

This isn't about finding the shortest answer overall, but rather the shortest in each language.

And now, a shameless copy of the leaderboard snippet.

# The Leaderboard

The Stack Snippet at the bottom of this post generates the catalogue from the answers a) as a list of shortest solution per language and b) as an overall leaderboard.

To make sure that your answer shows up, please start your answer with a headline, using the following Markdown template:

```
## Language Name, N bytes

```

where N is the size of your submission. If you improve your score, you can keep old scores in the headline, by striking them through. For instance:

```
## Ruby, <s>104</s> <s>101</s> 96 bytes

```

If there you want to include multiple numbers in your header (e.g. because your score is the sum of two files or you want to list interpreter flag penalties separately), make sure that the actual score is the last number in the header:

```
## Perl, 43 + 2 (-p flag) = 45 bytes

```

You can also make the language name a link which will then show up in the snippet:

```
## [><>](http://esolangs.org/wiki/Fish), 121 bytes

```

```
/* Configuration */

var QUESTION_ID = 62476; // 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 = 41505; // 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+(?:.\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
## C++, 440.3 ~~405~~ 388 bytes

518 bytes - 15% bonus for insertion sort = 440.3 bytes

~~477 bytes - 15% bonus for insertion sort = 405.45 bytes~~

~~474 bytes - 15% bonus for insertion sort = 402.9 bytes~~

```
456 bytes - 15% bonus for insertion sort = 387.6 bytes

```

Thanks to @Luke for saving 3 bytes (2 really).

Thanks to @Dúthomhas for saving 18 (15 really) bytes.

Note that I am new here and this is my first post.

This is a `.h` (header) file.

Compressed Code:

```
#include<iostream>
#include<ctime>
#include<cstdlib>
void s(int a[],int i,int j){int t=a[i];a[i]=a[j];a[j]=t;}int z(int a[],int b,int e){int p=a[(rand()%(e-b+1))+b];b--;while(b<e){do{b++;}while(a[b]<p);do{e--;}while(a[e]>p);if(b<e){s(a, b, e)}}return b;}void q(int a[],int b,int e){if(e-b<=5){for(int i=b;i<e;i++){for(int j=i;j>0;j--){if(a[j]<a[j-1]){s(a,j,j-1);}else{break;}}}return;}int x=z(a,b,e);q(a,b,x);q(a,x,e);}void q(int a[],int l){q(a,0,l);}

```

Full Code:

```
#include <iostream>
#include <ctime>
#include <cstdlib>

void swapElements(int toSort[], int i, int j) {
    int temp = toSort[i];
    toSort[i] = toSort[j];
    toSort[j] = temp;
}

int partitionElements(int toSort[], int beginPtr, int endPtr)
{
    int pivot = toSort[(rand() % endPtr - beginPtr + 1) + beginPtr];
    beginPtr--;
    while (beginPtr < endPtr) {
        do {
            beginPtr++;
        } while (toSort[beginPtr] < pivot);
        do {
            endPtr--;
        } while (toSort[endPtr] > pivot);
        if (beginPtr < endPtr) {
            // Make sure they haven't crossed yet
            swapElements(toSort, beginPtr, endPtr);
        }
    }
    return beginPtr;
}

void quickSort(int toSort[], int beginPtr, int endPtr)
{
    if (endPtr - beginPtr <= 5) { // Less than 5: insertion sort
        for (int i = beginPtr; i < endPtr; i++) {
            for (int j = i; j > 0; j--) {
                if (toSort[j] < toSort[j - 1]) {
                    swapElements(toSort, j, j - 1);
                } else {
                    break;
                }
            }
        }
        return;
    }
    int splitIndex = partitionElements(toSort, beginPtr, endPtr);
    quickSort(toSort, beginPtr, splitIndex );
    quickSort(toSort, splitIndex, endPtr);
}

void quickSort(int toSort[], int length)
{
    quickSort(toSort, 0, length);
}

```
> 10 votes

# Answer
# APL, ~~49~~ 42 bytes

```
{1≥⍴⍵:⍵⋄(∇⍵/⍨⍵<p),(⍵/⍨⍵=p),∇⍵/⍨⍵>p←⍵[?⍴⍵]}

```

This creates an unnamed recursive monadic function that accepts an array on the right. It does not qualify for the bonus.

Explanation:

```
{1≥⍴⍵:⍵⋄                                     ⍝ If length(⍵) ≤ 1, return ⍵
                                  p←⍵[?⍴⍵]}  ⍝ Choose a random pivot
                           ∇⍵/⍨⍵>            ⍝ Recurse on >p
                  (⍵/⍨⍵=p),                  ⍝ Concatenate with =p
        (∇⍵/⍨⍵<p),                           ⍝ Recurse on <p

```

Try it online

Fixed an issue (at the cost of 8 bytes) thanks to marinus and saved 7 bytes thanks to Thomas Kwa!
> 9 votes

# Answer
# C++17, ~~254~~ ~~199~~ 195 bytes

```
#include<vector>
#include<cstdlib>
#define P push_back(y)
using V=std::vector<int>;V q(V a){int p=a.size();if(p<2)return a;p=rand()%p;V l,r;for(y:a)(y<a[p]?l:r).P;l=q(l);for(y:q(r))l.P;return l;}

```

With whitespace:

```
V q(V a) {
    int p = a.size();

    if (p < 2)
        return a;

    p = rand() % p;
    V l,r;

    for (y : a)
        (y < a[p] ? l : r).P;

    l=q(l);

    for (y : q(r))
        l.P;

    return l;
}

```
> 5 votes

# Answer
# Pyth, 25 bytes

```
L?tbsyMa_,]JObf<TJbf>TJbb

```

This defines a function `y`, that takes a list of numbers as input.

Try it online: Demonstration

### Explanation

```
L?tbsyMa_,]JObf<TJbf>TJbb
L                          define function y(b), that returns:
 ?tb                         if t[1:] (if the list has more than one element):
            Ob                 choose a random element of b
           J                   save it in J
          ]                    put J in a list
         ,    f<TJb            create a pair, that contains ^ and a list of
                               all numbers smaller than J: [[J], [smaller than J]]
        _                      reverse this list: [[smaller than J], [J]]
       a           f>TJb       append a list with all elements bigger than J:
                               [[smaller than J], [J], [bigger than J]]
     yM                        call y recursively for each sublist
    s                          combine the results and return it
                        b    else: simply return b

```

# Pyth, 21 bytes (probably invalid)

I use the "group-by" method, which internally uses a sort. I use it to split the original list into three sublists (all element smaller than the pivot, the pivot, and all elements bigger than the pivot). Without the sort in "group-by", it could return these 3 lists in a different order.

As said, this is probably invalid. Nevertheless I'll keep it here, because it's an interesting solution.

```
L?tb&]JObsyM.g._-kJbb

```

Try it online: Demonstration

### Explanation

```
L?tb&]JObsyM.g._-kJbb
L                      def y(b): return
 ?tb                     if t[1:] (if the list has more than one element):
       Ob                  choose a random element of b
      J                    save it in J
    &]                     put it in an array and call "and"
                           (hack which allows to call 2 functions in one statement)

            .g     b       group the elements in b by:
              ._-kJ           the sign of (k - J)
                           this generates three lists
                             - all the elements smaller than J
                             - J
                             - all the elements bigger than J
          yM               call y recursively for all three lists
         s                 and combine them
                    b    else: return b

```
> 4 votes

# Answer
# \>\<\> (Fish), ~~313~~ 309 bytes

```
!;00l[l2-[b1.
>:0)?v~$:@&vl2,$:&${:}$
^-1@{< ]]. >055[3[5b.
?v~~@~ v:}@:}@:}:}@:}@}}}(}(}({{:@=
.>=$~?$>~]]
.001-}}d6.{$}1+}d6
?v:{:}@{(?v08.}:01-=
 >{$~~{09.>95.v-1@{<   v-1}$<
.:@}:@{=${::&@>:0)?^~}&>:0)?^~+}d6
 1-:0a.{{$&l&1+-: >:0)?v~:1)?!v62fb.
>:0)?v~:}:1)?v~69.^@{-1<>.!]]~<
^@{-1<:}@@73.>69@@:3+[{[b1.

```

This took me very long to write. You can try it here, just put the list that has to be sorted into the initial stack, seperated with commas, before running the program.

## How it works

The program grabs the first, middle and last element in the initial stack and calculates the median of these three.
It then changes the stack to:

\[list 1\] element \[list 2\]

where everything in list 1 is smaller or equal to the element and everything in list 2 is bigger.
It recursively repeats this process on list 1 and list 2 untill the whole list is sorted.
> 3 votes

# Answer
# CJam, 40 bytes

```
{_1>{_mR:P-PaL@{_P<{+}{@\+\}?}/J\J+}&}:J

```

This is a named function that expects an array on the stack and pushes one in return.

Try it online in the CJam interpreter.

The above code follows the spec as closely as possible. If that's not required, 12 bytes can be saved:

```
{_1>{_mR:P;_{P<},J_@^J+}&}:J

```
> 2 votes

# Answer
# Python 3, ~~123~~, 122.

Saved 1 byte thanks to Aaron.

This is the first time I've actually bothered to write a sorting algorithm. It's actually a little easier than I thought it would be.

```
from random import*
def q(s):
 if len(s)<2:return s
 p=choice(s);return q([d for d in s if d<=p])+q([d for d in s if d>p])

```

Ungolfed:

```
from random import choice
def quick_sort(seq):
    if len(seq) < 2:
        return seq
    low = []
    high = []
    pivot = choice(seq)
    for digit in seq:
        if digit > pivot:
            high += [digit]
        else:
            low += [digit]
    return quick_sort(low) + quick_sort(high)

```
> 2 votes

# Answer
# Javascript (ES2015), 112

```
q=l=>{let p=l[(Math.random()*l.length)|0];return l.length<2?l:q(l.filter(x=>x<=p)).concat(q(l.filter(x=>x>p)));}

```

### Explanation

```
//Define lambda function q for quicksort
q=l=>{

    //Evaluate the pivot
    let p=l[(Math.random()*l.length)|0];

    //return the list if the length is less than 2
    return l.length < 2 ? l:

    //else return the sorted list of the elements less or equal than
      the pivot concatenated with the sorted list of the elements
      greater than the pivot
    q(l.filter(x=>x<=p)).concat(q(l.filter(x=>x>p)));
}

```
> 2 votes

# Answer
# Ceylon (JVM only), ~~183~~ 170

No bonuses apply.

```
import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];

```

It seems there is no cross-platform way to produce a random number in Ceylon, so this is JVM-only. (At the end I have a non-random version which works in JS too, and is smaller.)

This defines a function which takes an iterable of floats, and returns a sorted version thereof.

```
import ceylon.math.float {
    r=random
}

{Float*} q({Float*} l) {
    if (exists p = l.getFromFirst((r() * l.size).integer)) {
        return q(l.filter((e) => e < p)).chain { p, *q(l.filter((e) => p < e)) };
    } else {
        return [];
    }
}

```

If (against the specification) duplicate entries are passed, those will be filtered out.

This are 183 bytes: `import ceylon.math.float{r=random}{Float*}q({Float*}l){if(exists p=l.getFromFirst((r()*l.size).integer)){return q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))};}else{return[];}}`

We can improve a bit by using the new (Ceylon 1.2) `if` expression:

```
import ceylon.math.float {
    r=random
}

{Float*} q({Float*} l) =>
        if (exists p = l.getFromFirst((r() * l.size).integer))
        then q(l.filter((e) => e < p)).chain { p, *q(l.filter((e) => p < e)) }
        else [];

```

This is 170 bytes: `import ceylon.math.float{r=random}{Float*}q({Float*}l)=>if(exists p=l.getFromFirst((r()*l.size).integer))then q(l.filter((e)=>e<p)).chain{p,*q(l.filter((e)=>p<e))}else[];`

---

Here is a non-random version:

```
{Float*} r({Float*} l) =>
        if (exists p = l.first)
        then r(l.filter((e) => e < p)).chain { p, *r(l.filter((e) => p < e)) }
        else [];

```

Without spaces this would be 107 bytes: `{Float*}r({Float*}l)=>if(exists p=l.first)then r(l.filter((e)=>e<p)).chain{p,*r(l.filter((e)=>p<e))}else[];`
> 1 votes

# Answer
# Ruby, ~~87~~ 60 bytes

```
q=->a,p=a.sample{a[1]?(l,r=a.partition{|e|e<p};q[l]+q[r]):a}

```

Ungolfed:

```
def quicksort(a, pivot=a.sample)
  if a.size > 1
    l,r = a.partition { |e| e < pivot}
    quicksort(l) + quicksort(r)
  else
    a
  end
end

```

Test:

```
q[[9, 18, 8, 5, 13, 20, 7, 14, 16, 15, 10, 11, 2, 4, 3, 1, 12, 17, 6, 19]]
=> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

```
> 1 votes

# Answer
# R, 78 bytes

```
Q=function(x)if(length(x)>1)c(Q(x[x<(p=sample(x,1))]),x[x==p],Q(x[x>p]))else x

```

This creates a recursive function `Q` that accepts a vector and returns a vector. It does not conditionally apply insertion sort, so no bonus.

Ungolfed:

```
Q <- function(x) {
    # Check length
    if (length(x) > 1) {
        # Select a random pivot
        p <- sample(x, 1)

        # Recurse on the subarrays consisting of
        # elements greater than and less than p,
        # concatenate with those equal to p
        c(Q(x[x < p]), x[x == p], Q(x[x > p]))
    } else {
        x
    }
}

```

Try it online

Saved 4 bytes thanks to flodel!
> 1 votes

# Answer
# Julia, 83 bytes

```
Q(x)=endof(x)<2?x:(p=rand(x);[Q((f=filter)(i->i<p,x));f(i->i==p,x);Q(f(i->i>p,x))])

```

This creates a recursive function `Q` that accepts an array and returns an array. It does not conditionally use insertion sort, so no bonus applies.

Ungolfed:

```
function Q(x::AbstractArray)
    if endof(x) ≤ 1
        # Return on empty or 1-element arrays
        x
    else
        # Select a random pivot
        p = rand(x)

        # Return the function applied to the elements less than
        # the pivot concatenated with those equal to the pivot
        # and the function applied to those greater than the pivot
        [Q(filter(i -> i < p, x));
         filter(i -> i == p, x);
         Q(filter(i -> i > p, x))]
    end
end

```

Fixed an issue and saved some bytes thanks to Glen O!
> 1 votes

# Answer
# JavaScript (ES6), 191

```
Q=(a,l=0,h=a.length-1)=>l<h&&(p=((a,i,j,p=a[i+(0|Math.random()*(j-i))])=>{for(--i,++j;;[a[i],a[j]]=[a[j],a[i]]){while(a[--j]>p);while(a[++i]<p);if(i>=j)return j}})(a,l,h),Q(a,l,p),Q(a,p+1,h))

```

```
// More readable
U=(a,l=0,h=a.length-1)=>l<h &&
  (p=( // start of partition function
    (a,i,j,p=a[i+(0|Math.random()*(j-i))])=>
    {
      for(--i,++j;;[a[i],a[j]]=[a[j],a[i]])
      {
        while(a[--j]>p);
        while(a[++i]<p);
        if(i>=j)return j
      }
    } // end of partition function
  )(a,l,h),U(a,l,p),U(a,p+1,h))

// This is the shortest insertion sort that I could code, it's 72 bytes
// The bonus is worth  ~30 bytes - so no bonus
I=a=>{for(i=0;++i<a.length;a[j]=x)for(x=a[j=i];j&&a[j-1]>x;)a[j]=a[--j]}

// TEST
z=Array(10000).fill().map(_=>Math.random()*10000|0)

Q(z)

O.innerHTML=z.join(' ')
```

```
<div id=O></div>
```
> 1 votes

# Answer
# Octave, ~~76~~ 75 bytes

```
function u=q(u)n=numel(u);if n>1 k=u(randi(n));u=[q(u(u<k)),q(u(u>=k))];end

```

Multi-line version:

```
function u=q(u)
   n=numel(u);
   if n>1
      k=u(randi(n));
      u=[q(u(u<k)),q(u(u>=k))];
   end

```
> 1 votes

# Answer
# K, 41 bytes

```
s:{$[#x;(s@x@&x<p),p,s@x@&x>p:x@*1?#x;x]}

```

TAKE THAT, APL!!! Doesn't do any of the bonuses.
> 1 votes

# Answer
# Haskell, ~~137~~136 bytes

```
f=filter
m a b c=max(min a b)(min(max a b)c)
q[]=[]
q l=let{n=m(head l)(head$drop(length l`div`2)l)(last l)}in(q$f(<n)l)++(n:(q$f(>n)l))

```

The ungolfed version is hereunder, with expanded variable and function names and some intermediate results added:

```
median a b c = max (min a b) (min (max a b) c)
quicksort [] = []
quicksort l = let mid = median (head l) (middle l) (last l)
                  lesser = filter (< mid) l
                  greater = filter (> mid) l
                  middle l = head $ drop (length l `div` 2) l
              in (quicksort lesser) ++ (mid : (quicksort greater))

```

I'm taking advantage of the fact that there's no duplicates to use two strict comparisons. I'll have to check if `Data.List.partition` doesn't makes things shorter though, even considering I would have to add an import statement. I'm not taking the insertion sort bonus because I consider `Data.List.insert` as a sorting-related function — thus forbidden — and if not using it, adding the insertion sort pushes the code to 246 bytes, 209.1 with the bonus, so it's not worth it.

*Edit :* Thanks to RobAu for their suggestion to create an alias to use `f=filter`. It may save only one byte but everything helps.
> 1 votes

# Answer
## Tcl, 138 bytes

```
proc q v {if {$v eq {}} return
lassign {} a b
foreach x [lassign $v p] {if {$x<$p} {lappend a $x} {lappend b $x}}
concat [q $a] $p [q $b]}

```

This is an exceedingly standard quicksort.

The pivot is simply the first element of each subarray (I contend that this is a random number. https://xkcd.com/221/)

It isn't particularly efficient in terms of memory usage, though it could be improved some with `tailcall` on the second recursion and a base case of n\<1 elements.

Here's the readable version:

```
proc quicksort xs {
  if {![llength $xs]} return
  set lhs [list]
  set rhs [list]
  foreach x [lassign $xs pivot] {
    if {$x < $pivot} \
      then {lappend lhs $x} \
      else {lappend rhs $x}
  }
  concat [quicksort $lhs] $pivot [quicksort $rhs]
}

```

Works on all input and permits duplicates. Oh, it's also *stable*. You can test it with something simple, like:

```
while 1 {
  puts -nonewline {xs? }
  flush stdout
  gets stdin xs
  if {$xs eq {}} exit
  puts [q $xs]    ;# or [quicksort $xs]
  puts {}
}

```

Enjoy! :O)
> 1 votes

# Answer
## AutoIt, ~~320.45~~ 304.3 bytes

This is plenty fast (for AutoIt anyway). Qualifies for insertion sort bonus. Will add explanation after final golfing occurred.

Input is `q(Array, StartingElement, EndingElement)`.

```
Func q(ByRef $1,$2,$3)
$5=$3
$L=$2
$6=$1[($2+$3)/2]
If $3-$2<6 Then
For $i=$2+1 To $3
$4=$1[$i]
For $j=$i-1 To $2 Step -1
$5=$1[$j]
ExitLoop $4>=$5
$1[$j+1]=$5
Next
$1[$j+1]=$4
Next
Else
Do
While $1[$L]<$6
$L+=1
WEnd
While $1[$5]>$6
$5-=1
WEnd
ContinueLoop $L>$5
$4=$1[$L]
$1[$L]=$1[$5]
$1[$5]=$4
$L+=1
$5-=1
Until $L>$5
q($1,$2,$5)
q($1,$L,$3)
EndIf
EndFunc

```

Random test input + output:

```
862, 543, 765, 577, 325, 664, 503, 524, 192, 904, 143, 483, 146, 794, 201, 511, 199, 876, 918, 416
143, 146, 192, 199, 201, 325, 416, 483, 503, 511, 524, 543, 577, 664, 765, 794, 862, 876, 904, 918

```
> 0 votes

# Answer
## Java, 346 bytes

```
407 bytes - 15% bonus for insertion sort = 345.95 bytes

```

Compressed Code:

```
class z{Random r=new Random();void q(int[] a){q(a,0,a.length);}void q(int[] a,int b,int e){if(e-b<6){for(int i=b;i<e;i++){for(int j=i;j>0&a[j]<a[j-1];j--){s(a,j,j-1);}}return;}int s=p(a,b,e);q(a,b,s);q(a,s,e);}int p(int[] a,int b,int e){int p=a[r.nextInt(e-b)+b--];while(b<e){do{b++;}while(a[b]<p);do{e--;}while(a[e]>p);if(b<e){s(a,b,e);}}return b;}void s(int[] a,int b,int e){int t=a[b];a[b]=a[e];a[e]=t;}}

```

Full Code:

```
public class QuickSort {

    private static final Random RANDOM = new Random();

    public static void quickSort(int[] array) {
        quickSort(array, 0, array.length);
    }

    private static void quickSort(int[] array, int begin, int end) {
        if (end - begin <= 5) {
            for (int i = begin; i < end; i++) {
                for (int j = i; j > 0 && array[j] < array[j - 1]; j--) {
                    swap(array, j, j - 1);
                }
            }
            return;
        }
        int splitIndex = partition(array, begin, end);
        quickSort(array, begin, splitIndex);
        quickSort(array, splitIndex, end);
    }

    private static int partition(int[] array, int begin, int end) {
        int pivot = array[RANDOM.nextInt(end - begin) + begin];
        begin--;
        while (begin < end) {
            do {
                begin++;
            } while (array[begin] < pivot);
            do {
                end--;
            } while (array[end] > pivot);
            if (begin < end) {
                // Make sure they haven't crossed yet
                swap(array, begin, end);
            }
        }
        return begin;
    }

    private static void swap(int[] array, int begin, int end) {
        int temp = array[begin];
        array[begin] = array[end];
        array[end] = temp;
    }

}

```
> 0 votes

# Answer
## Mathematica, ~~93~~ 90 bytes

```
If[Length@#>1,pv=RandomChoice@#;Join[qs2[#~Select~(#<pv&)],{pv},qs2[#~Select~(#>pv&)]],#]&

```

No bonus, haven't got a minimal way to do insertion sort yet. When I was learning C++ recently, I did a comparison of various sorting algorithms here.
> 0 votes

# Answer
## Python2, 120 bytes

```
def p(a):
 if[]==a[1:]:return a
 b,c,m=[],[],__import__("random").choice(a)
 for x in a:[b,c][x>m]+=[x];return p(b)+p(c)

```

`if[]==a[1:]` is exactly as long as `if len(a)>2` but looks more golfed.
> 0 votes

# Answer
# Lua, 242 Bytes

```
function f(t,p)if(#t>0)then local P,l,r,i=math.random(#t),{},{},table.insert p=t[P]for k,v in ipairs(t)do if(k~=P)then i(v<p and l or r,v)end end t={}for k,v in pairs(f(l))do i(t,v)end i(t,p)for k,v in pairs(f(r))do i(t,v)end end return t end

```

## Ungolfed & Explination

```
function f(t,p)                                             # Assign 'p' here, which saves two bytes, because we can't assign it to t[P] IN the local group.
    if(#t>0)then                                            # Just return 0 length lists...
        local P,l,r,i=math.random(#t),{},{},table.insert    # Using local here actually makes the a,b=1,2 method more efficient here. Which is unnormal for Lua
        p = t[P]                                            # P is the index of the pivot, p is the value of the pivot, l and r are the sub-lists around the pivot, and i is table.insert to save bytes.
        for k,v in ipairs(t) do                             # We use a completely random pivot, because it's cheaper on the bytes.
            if(k~=P)then                                    # Avoid 'sorting' the pivot.
                i(v<p and l or r,v)                         # If the value is less than the pivot value, push it to the left list, otherwise, push it to the right list.
            end                                             #
        end                                                 #
        t = {}                                              # We can re-use t here, because we don't need it anymore, and it's already a local value. Saving bytes!
        for k,v in pairs(f(l)) do                           # Quick sort the left list, then append it to the new output list.
            i(t,v)                                          #
        end                                                 #
        i(t,p)                                              # Append the pivot value.
        for k,v in pairs(f(r)) do                           # Ditto the right list.
            i(t,v)                                          #
        end                                                 #
    end                                                     #
    return t                                                # Return...
end                                                         #

```
> 0 votes

# Answer
## Racket 121 bytes

```
(λ(l)(if(null? l)l(let((h(car l))(t(cdr l)))(append(qs (filter(λ(x)(< x h))t))(list h)(qs (filter(λ(x)(>= x h))t))))))

```

Ungolfed (l=list, h=head (first element), t=tail (rest or remaining elements)):

```
(define qs
  (λ(l)
    (if (null? l) l
        (let ((h (first l))
              (t (rest  l)))
          (append (qs (filter (λ(x) (< x h) ) t))
                  (list h)
                  (qs (filter (λ(x) (>= x h)) t))  )))))

```

Testing:

```
(qs (list 5 8 6 8 9 1 2 4 9 3 5 7 2 5))

```

Output:

```
'(1 2 2 3 4 5 5 5 6 7 8 8 9 9)

```
> 0 votes

# Answer
# Japt, 23 bytes

Each bonus would need to be three bytes or less to pay off in the total score, so I didn't take any bonuses.

```
Z=Uö;Ê<2?U:ßUf<Z)cßUf¨Z
Z=Uö;                   // Take a random element from the input for partitioning.
     Ê<2                // If the input is shorter than two elements,
        ?U              // return it.
          :             // Otherwise
           ß      ß     // recursively run again
            Uf<Z        // with both items that are smaller than the partition
                   Uf¨Z // and those that are larger or equal,
                )c      // returning the combined result.

```

Try it online!
> 0 votes

---
Tags: code-golf, sorting
---


title: Ascending Pea Pattern generator

text:
# Question
Title: Ascending Pea Pattern generator
For those who are not familiarized with the Pea Pattern, it is a simple mathematical pattern.

**There are multiple variations of this pattern, but we will focus in one:**

> Ascending Pea Pattern

It looks like this:

```
1
11
21
1112
3112
211213
...

```

It seems really hard to get the following line, but it is really easy. The way to get the next line is by counting the number of times a digit have repeated on the previous line (start counting with the lowest, to largest):

```
one
one one
two ones
one one, one two
three ones, one two
two ones, one two, one three
...

```

**Requirements/Rules:**

* We will start at `1`
* It will be a snippet
* There must be a way to specify the number of lines generates (e.g `5` will give the first 5 lines)
* The code should be as *short* as possible
* It must start counting from lowest to largest (the Ascending variation)

# Answer
> 4 votes
# APL, 32 characters

```
⍪⌽({⍵,⍨,/{⌽⍵,+/⍵⍷d}¨⍳⌈/d←⊃⍵}⍣⎕)1

```

This generates lines starting from 0 (i.e. `0` generates `1`, `1` generates `1` followed by `1 1`, etc.), as specified by user input. I used Dyalog APL for this, and `⎕IO` should be set to its default of 1.

Example:

```
      ⍪⌽({⍵,⍨,/{⌽⍵,+/⍵⍷d}¨⍳⌈/d←⊃⍵}⍣⎕)1
⎕:
      0
1

      ⍪⌽({⍵,⍨,/{⌽⍵,+/⍵⍷d}¨⍳⌈/d←⊃⍵}⍣⎕)1
⎕:
      13
               1
             1 1
             2 1
         1 1 1 2
         3 1 1 2
     2 1 1 2 1 3
     3 1 2 2 1 3
     2 1 2 2 2 3
     1 1 4 2 1 3
 3 1 1 2 1 3 1 4
 4 1 1 2 2 3 1 4
 3 1 2 2 1 3 2 4
 2 1 3 2 2 3 1 4
 2 1 3 2 2 3 1 4

```

Once I get some more time, I'll write up an explanation. ⍨

# Answer
> 3 votes
## Python (2.x), 81 80 characters

```
l='1'
exec"print l;l=''.join(`l.count(k)`+k for k in sorted(set(l)))\n"*input()

```

All tips or comments welcome!

```
usage: python peapattern.py
15 # enter the number of iterations
1
11
21
1112
3112
211213
312213
212223
114213
31121314
41122314
31221324
21322314
21322314
21322314
```

# Answer
> 2 votes
## J, 60 46 39 26 characters

```
1([:,(#,{.)/.~@/:~)@[&0~i.

```

**Edit 3**: Came up with a much nicer way of expressing this.

```
1([:;[:|."1[:/:~~.,.[:+/"1[:~.=)@[&0~i.

```

**Edit 2**: Finally found a way to move the argument to the end of the sequence and get rid of the unnecessary assignment stuff.

Previously:

```
p=.3 :'([:,[:|."1[:/:~~.,.[:+/"1[:~.=)^:(i.y)1

```

**Edit 1**: Fixes the output which should be `y` rows rather than the `y`th row. Also shortens things a bit. Shame about the `0`s, can't seem to get rid of the damn things.

Usage:

```
   1([:,(#,{.)/.~@/:~)@[&0~i. 1
1

   1([:,(#,{.)/.~@/:~)@[&0~i. 6
1 0 0 0 0 0
1 1 0 0 0 0
2 1 0 0 0 0
1 1 1 2 0 0
3 1 1 2 0 0
2 1 1 2 1 3

   1([:,(#,{.)/.~@/:~)@[&0~i. 10
1 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0
2 1 0 0 0 0 0 0
1 1 1 2 0 0 0 0
3 1 1 2 0 0 0 0
2 1 1 2 1 3 0 0
3 1 2 2 1 3 0 0
2 1 2 2 2 3 0 0
1 1 4 2 1 3 0 0
3 1 1 2 1 3 1 4

```

Admittedly the usage is uglier now, but prettiness isn't the name of the game here...

# Answer
> 2 votes
## Perl, 83

I'm pretty sure some Perl guru could outdo this, but here goes:

```
$_++;$n=<>;for(;$n--;){print$_.$/;$r='';$r.=length($&).$1 while(s/(.)\1*//);$_=$r;}

```

Expanded:

```
$_++;$n=<>;

for(;$n--;)
{
    print $_.$/;

    $r='';$r .= length($&).$1 while (s/(.)\1*//);  # The magic
    $_=$r;
}

```

Number of rows is passed in via STDIN.

# Answer
> 1 votes
## Haskell, 116

```
import Data.List
main=interact(unlines.map(show=<<).($iterate((>>=
 \x->[length x,head x]).group.sort)[1]).take.read)

```

Usage:

```
$ runhaskell pea.hs <<< 15
1
11
21
1112
3112
211213
312213
212223
114213
31121314
41122314
31221324
21322314
21322314
21322314

```

# Answer
> 1 votes
## Common Lisp, 140 characters

```
(defun m(x)
  (labels((p(l n)
    (if(= 0 n)
       nil
       (cons l
             (p(loop for d in(sort(remove-duplicates l)#'<)
                  append(list(count d l)d))
               (1- n))))))
    (p'(1) x)))

```

This is Lisp, so the function returns a list of lists. (m x) generates X sublists.

# Answer
> 1 votes
### Mathematica, 70

```
NestList[FromDigits@TakeWhile[DigitCount@#~Riffle~Range@9,#>0&]&,1,#]&

```

# Answer
> 1 votes
# Jelly, 13 11 bytes (Feedback appreciated)

```
1ṢŒrUFƲÐ¡ṖY

```

Try it online!

```
1ṢŒrUFƲÐ¡ṖY
1     Ʋ         starting with 1, run these 4 links...
 ṢŒr            Ṣort the list and get the Œrun-length encoding of it,
    U           reverse each member of the RLE list (so it goes [repetitions, digit] instead of [digit, repetitions]),
     F          and Flatten the RLE list-of-lists to just a list of digits, which is the next number.
       Ð¡       do that (input) number of times,
         ṖY     Ṗop the last line off the output (an extra line is always calculated) and then print the numbers, separated by newlines.

```

---
Tags: code-golf, math
---


title: What's in my pasta sauce?

text:
# Question
Title: What's in my pasta sauce?
## Background

In France, and probably in the rest of the European Union, any food available for sale must list the ingredients that compose it on its packaging, in **weight percentage descending order**. However, the **exact percentage** doesn't have to be indicated, unless the ingredient is highlighted by the text or an image on the covering.

For example, my basil tomato sauce, showing only some big red tomatoes and beautiful basil leaves on its packaging, has the following indications:

> *Ingredients:* Tomatoes 80%, onions in pieces, basil 1.4%, sea salt, mashed garlic, raw cane sugar, extra virgin olive oil, black pepper.

It sounds savoury, but… **how much onions will I eat**, exactly?

## Challenge

Given a list of weight percentages in descending order, eventually incomplete, output a **complete** list of the **minimal** and **maximal** weight percentages that can possibly be found in the recipe.

* You can write either a function, or a full program.
* The *input* can be in any reasonable form (array of numbers or list of strings, for instance). Fractional values should be supported at least to one decimal place. A missing weight percentage can be represented in any consistent and unambiguous way (`0`, `'?'` or `null`, for instance). You can assume that the input will always be associated to a valid recipe (`[70]` and `[∅, ∅, 50]` are invalid, for instance).
* The *output* can be in any reasonable form (one array for both of the minimal and maximal weight percentages, or a single list of doublets, for instance). The minimal and maximal percentages can be in any order (`[min, max]` and `[max, min]` are both acceptable). Exact weight percentages don't need to be processed differently than other percentages and may be represented by equal minimal and maximal values.

Standard rules for apply: while you're typing your code, my pasta dish is cooling down, so the shortest submission wins.

## Examples

Since this problem is harder than it may look at first glance, here is a step-by-step resolution of a few cases.

### `[40, ∅, ∅]`

Let's call respectively `x` and `y` the two missing percentages.

* Because it comes after the first ingredient at 40%, `x` can't be higher than 40 % itself.
`[40, [?, 40], [?, ?]]`
* The sum of the two missing percentages is always 60%. Consequently :
    + If `x` takes its *maximal* value, then `y` takes its *minimal* value, which is therefore 60% - 40% = 20%.
    `[40, [?, 40], [20, ?]]`
    + If `x` takes its *minimal* value, then `y` takes its *maximal* value. But `x` can't be lower than `y`, so in this case, `x` = `y` = 60% / 2 = 30%.
    `[40, [30, 40], [20, 30]]`

### `[70, ∅, ∅, 5, ∅]`

Let's call respectively `x`, `y` and `z` the three missing percentages.

* The minimal and maximal percentages for `z` are necessarily between 0% and 5%. Let's assume `z` = 0% for a moment. The sum of the two missing percentages is always 25%. Consequently :
`[70, [?, ?], [?, ?], 5, [0, 5]]`
    + If `y` takes its *minimal* value, 5%, then `x` takes its *maximal* value, which is therefore 25% - 5% = 20%.
    `[70, [?, 20], [5, ?], 5, [0, 5]]`
    + If `y` takes its *maximal* value, then `x` takes its *minimal* value. But `x` can't be lower than `y`, so in this case, `x` = `y` = 25% / 2 = 12.5%.
    `[70, [12.5, 20], [5, 12.5], 5, [0, 5]]`
* Let's verify that everything is fine if we assume now that `z` = 5%. The sum of the two missing percentages is always 20%. Consequently :
    + If `y` takes its *minimal* value, 5%, then `x` takes its *maximal* value, which is therefore 20% - 5% = 15%. This case is already included in the previously calculated ranges.
    + If `y` takes its *maximal* value, then `x` takes its *minimal* value. But `x` can't be lower than `y`, so in this case, `x` = `y` = 20% / 2 = 10%. This case is already included in the previously calculated range for `y`, but not for `x`.
    `[70, [10, 20], [5, 12.5], 5, [0, 5]]`

## Test cases

```
Input:  [∅]
Output: [100]

Input:  [70, 30]
Output: [70, 30]

Input:  [70, ∅, ∅]
Output: [70, [15, 30], [0, 15]]

Input:  [40, ∅, ∅]
Output: [40, [30, 40], [20, 30]]

Input:  [∅, ∅, 10]
Output: [[45, 80], [10, 45], 10]

Input:  [70, ∅, ∅, ∅]
Output: [70, [10, 30], [0, 15], [0, 10]]

Input:  [70, ∅, ∅, 5, ∅]
Output: [70, [10, 20], [5, 12.5], 5, [0, 5]]

Input:  [30, ∅, ∅, ∅, 10, ∅, ∅, 5, ∅, ∅]
Output: [30, [10, 25], [10, 17.5], [10, 15], 10, [5, 10], [5, 10], 5, [0, 5], [0, 5]]

```

# Answer
# JavaScript (ES6), 252 bytes

Expects `0` for missing percentages. Returns a pair of minimum and maximum values for all entries.

```
a=>(g=a=>(h=(M,I,J=I^1)=>a.some((x,i)=>a.map((y,j)=>s-=j-i?M(j,i)-i?y[I]:M(w=y[I],z=x[J])-z||w==z?w:++k&&z:y[J],s=100,k=1,X=x)&&(I?-s:s)<0)?X[J]=M(X[I],X[J]+s/k):0)(Math.max,0)+h(Math.min,1)?g(a):a)(a.map((n,i)=>[n?p=n:a.find(n=>i--<0&&n)||0,p],p=100))

```

Try it online!

## How?

### Initialization

We first replace each value in the input array **a\[ \]** with the largest possible range.

```
a.map((n, i) =>       // for each value n at position i in a[]:
  [                   //   generate a [min, max] array:
    n ?               //     if n is not 0:
      p = n           //       use n as the minimum and save it in p
    :                 //     else:
      a.find(n =>     //       find the first value n
        i-- < 0 &&    //         which is beyond the current value
        n             //         and is not equal to 0
      ) || 0,         //       or use 0 as a default value
    p                 //     use p as the maximum
  ],                  //   end of array declaration
  p = 100             //   start with p = 100
)                     // end of map()

```

Examples:

```
[ 0 ] --> [ [ 0, 100 ] ]
[ 30, 0, 5, 0 ] --> [ [ 30, 30 ], [ 5, 30 ], [ 5, 5 ], [ 0, 5 ] ]

```

### Main function

The main function is **h()**. It looks for the first entry that appears to be inconsistent when we try to either minimize or maximize it. If it finds one, it updates it to a value which is at least temporarily acceptable, given the other ranges.

It takes as input either **M = Math.max** / **I = 0** or **M = Math.min** / **I = 1** and defines **J** as **I XOR 1**.

Because **h()** was written to support both the minimizing and maximizing passes, the code is a bit tricky to comment. That's why we will focus on the maximizing pass only, for which we have **M = Math.max**, **I = 0** and **J = 1**. With these parameters, the code reads as follows:

```
a.some((x, i) =>              // for each range x at position i in a[] (tested range):
  a.map((y, j) =>             //   for each range y at position j in a[] (reference range):
    s -=                      //     update s:
      j - i ?                 //       if i is not equal to j:
        Math.max(j, i) - i ?  //         if j > i:
          y[0]                //           the reference range is beyond the tested range
                              //           so we just use the minimum value of the y range
        :                     //         else:
          Math.max(           //           take the maximum of:
            w = y[0],         //             w = minimum value of the y range
            z = x[1]          //             z = maximum value of the x range
          ) - z ||            //           if it's not equal to z
          w == z ?            //           or they are equal (i.e. if w <= z):
            w                 //             use w
          :                   //           else:
            ++k && z          //             increment the counter k and use z
      :                       //       else:
        y[1],                 //         use the maximum value of the y range
    s = 100,                  //     start with s = 100
    k = 1,                    //     start with k = 1
    X = x                     //     save the range x in X
  ) &&                        //   end of map()
  (0 ? -s : s) < 0            //   abort if s < 0 (i.e. if we've subtracted more than 100)
) ?                           // end of some(); if truthy:
  X[1] = Math.max(            //   update the maximum value of the faulty range to:
    X[0],                     //     either the minimum value
    X[1] + s / k              //     or the maximum value, less the correction
  )                           //   whichever is greater
:                             // else:
  0                           //   do nothing

```

### Recursion

The recursive function **g()** keeps calling **h()** until neither the minimizing or the maximizing pass leads to a new correction, and eventually returns the final result.

```
g = a => h(Math.max, 0) + h(Math.min, 1) ? g(a) : a

```
> 11 votes

---
Tags: code-golf, math
---


title: Bringing a pair of integers to equality

text:
# Question
Title: Bringing a pair of integers to equality
This was inspired by a math problem I saw somewhere on the internet but do not remember where (UPDATE: The original problem was found on the math riddles subreddit with a proof provided that it is possible, also see this Math SE post), asking for a proof if the following process is possible for any arbitrary pair of integers (from what I remember, it was possible for any given pair):

Given a pair of integers, j and k, double one of them and add one to the other, resulting in a pair of new integers, i.e., (j, k) -\> (j+1, k\*2) or (j\*2, k+1). Then repeat this process with those integers, with the objective of having the pair of integers be equal.

These given examples are not necessarily optimal but show how this process can be done on any integers, positive, negative or zero:

```
(2, 5) -> (3, 10) -> (6, 11) -> (12, 12)

(5, 6) -> (6, 12) -> (7, 24) -> (14, 25) -> (28, 26) -> (56, 27) -> (112, 28) -> (113, 56) -> (226, 57) -> (227, 114) -> (228, 228)

(0, 2) -> (1, 4) -> (2, 5) -> (3, 10) -> (6, 11) -> (12, 12)

(-4, 0) -> (-3, 0) -> (-2, 0) -> (-1, 0) -> (0, 0)

(3, -1) -> (6, 0) -> (12, 1) -> (13, 2) -> (14, 4) -> (15, 8) -> (16, 16)

(-4, -3) -> (-8, -2) -> (-16, -1) -> (-32, 0) -> (-31, 0) -> ... -> (0, 0)

```

## Challenge

Create a program that given two integers, outputs the list of steps required to make those integers equal by repeatedly incrementing one and doubling the other

## Specifications

* The solution does not have to be optimal but it must solve in a finite number of steps for any arbitrary pair
* Input must be two integers
* Output may be any reasonable output that clearly denotes the resulting integers of each step, for example:

+ a string with two distinct delimiters (any symbol, whitespace, etc), one for each integer in a pair and one for each pair
        - e.g., input j, k: 2, 5 -\> output: 3,10;6,11;12,12
    + a list of lists of integers
        - e.g. input j, k: 2, 5 -\> output: \[\[3, 10\], \[6, 11\], \[12, 12\]\]
* If the input is a pair of equal numbers, you may output anything as long as it's consistent with other nontrivial answers

+ for example
        - if input \[2, 5\] has output \[\[3, 10\], \[6, 11\], \[12, 12\]\], which does not include the input pair, then input \[4, 4\] should output nothing.
        - if input \[2, 5\] has output \[\[2, 5\], \[3, 10\], \[6, 11\], \[12, 12\]\], which does include the input pair, then input \[4, 4\] should output \[\[4, 4\]\].
* Standard IO methods apply and standard loopholes banned
* This is code golf so shortest answer in bytes wins

# Answer
> 10 votes
# JavaScript (ES6), ~~111~~ ~~90~~ 83 bytes

```
f=(a,b,p=q=[],u=[...p,[a,b]])=>a-b?f(...(q=[[a*2,b+1,u],[a+1,b*2,u],...q]).pop()):u

```

Try it online!

### Commented

```
f = (                       // f = recursive function taking:
  a, b,                     //   (a, b) = input integers
  p =                       //   p[] = current path
  q = [],                   //   q[] = queue
  u = [...p, [a, b]]        //   u[] = updated path with [a, b] appended to it
) =>                        //
  a - b ?                   // if a is not yet equal to b:
    f(...                   //   recursive call, using spread syntax:
      (q = [                //     prepend the next 2 possible moves in the queue:
        [a * 2, b + 1, u],  //       a * 2, b + 1
        [a + 1, b * 2, u],  //       a + 1, b * 2
        ...q                //
      ]).pop()              //     use the move on the top of the queue
    )                       //   end of recursive call
  :                         // else:
    u                       //   success: return the (updated) path

```

# Answer
> 9 votes
## Haskell, ~~70~~ 69 bytes

```
f(w@((i,j):_):r)|i==j=w|1<2=f$r++[(i+1,j*2):w,(i*2,j+1):w]
g x=f[[x]]

```

Try it online!

A simple BFS. Keeps track of the steps in a list of list of pairs.

```
g x=f[[x]]                -- start with a single list where the only
                          -- step is the starting pair
f (w@((i,j):_):r) =       -- let w be the first list of steps
                          --     (i,j) the last pair of the first list of steps
                                       ('last' as in last operated on. As we store
                                        the steps in reverse order it's the
                                        first element in the list)
                          --     r all other lists of steps
   i==j=w                 -- if i==j stop and return the first list
   1<2= f                 -- else make a recursive call
          r++             -- where the new input list is r followed by
                          -- the first list extended one time by
          [(i+1,j*2):w,         (i+1,j*2) and one time by
             (i*2,j+1):w]       (i*2,j+1)

```

# Answer
> 7 votes
# Python 3, ~~90~~ ~~74~~ 72 bytes

-2 bytes thanks to Dennis.

```
def f(a,*x):j,k=a[0];return(j==k)*a or f(*x,[(2*j,k+1)]+a,[(j+1,2*k)]+a)

```

Try it online!

Takes input as a singleton list.

---

## Ungolfed

```
def f(a,*x):              # function taking at least one argument
                          # a is the first argument, all other are stored in x
  j, k = a[0]             # get the newest values of the current path
  return (j==k)*a         # if j is equal to k return the current path
                  or      # else ...
   f(                     # continue ...
     *x,                  # with the remaining paths ...
     [(2*j,k+1)]+a        # and split the current path ...
     [(j+1,2*k)]+a        # in two new ones
    )

```

# Answer
> 4 votes
# Pyth, 41 bytes

```
J]]QL,hhb*2ebWt{KehJ=J+tJm+hJ]d,yK_y_K)hJ

```

Try it here

### Explanation

This is pretty straightforward breadth-first search. Keep a queue of possible sequences (`J`), and until we get a matching pair, take the next sequence, stick on each of the possible moves, and put them at the end of the queue.
For the sake of brevity, we define a function `y` (using the lambda expression `L`) to perform one of the moves, and apply it both forward and in reverse.

# Answer
> 4 votes
# MATL, 24 bytes

```
`vxG1r/q:"tt1rEk(+]td0=~

```

Running time is random, but it is finite with probability 1.

The code is very inefficient. Inputs requiring more than 4 or 5 steps have a large probability of timing out in the online interpreter.

**Try it online!**

### Explanation

```
`         % Do...while
  vx      %   Concatenate stack and delete. This clears the stack from contents
          %   of previous iterations
  G       %   Push input
  1       %   Push 1
  r       %   Push random number uniformly distributed on (0,1)
  /       %   Divide
  q       %   Subtract 1. The result is a random number, t, that has nonzero
          %   probability of being arbitrarily large. Specifically, t is in
          %   the interval (0,1) with probability 1/2; in (1,2) with probability
          %   1/6; ... in (k,k+1) with probability 1/((k+1)*(k+2).
  :       %   Range [1 2 ... floor(t)]
  "       %   For each (that is: do thw following floor(t) times)
    tt    %     Duplicate twice
    1     %     Push 1
    rEk   %     Random number in (0,1), times 2, round down. This produces a
          %     number i that equals 0 or 1 with probability 1/2
    (     %     Write 1 at entry i. So if the top of the stack is [a b], this
          %     transforms it into either [1 b] or [a 1]
    +     %     Add, element-wise. This gives either [a+1 2*b] or [2*a b+1]
  ]       %   End for each
  td      %   Duplicate, consecutive difference between the two entries
  0=~     %   Is it not zero? If so, the do...while loop continues with a new
          %   iteration. Normally the code 0=~ could be omitted, because a
          %   nonzero consecutive difference is truthy. But for large t the
          %   numbers a, b may have gone to infinity, and then the consecutive
          %   difference gives NaN
          % End do...while (implicit). Display (implicit)

```

# Answer
> 4 votes
# Retina, 72 bytes

```
\d+
*
/\b(_+),\1\b/^+%`(_+),(_+)$
$&;_$&$2¶$=;$1$&_
G`\b(_+),\1\b
_+
$.&

```

Try it online! Only two test cases due to the limitations of unary arithmetic. Explanation:

```
\d+
*

```

Convert to unary.

```
/\b(_+),\1\b/^+

```

While the input does not contain a pair of identical numbers...

```
%`(_+),(_+)%

```

...match the last pair on each line...

```
$&;_$&$2¶$=;$1$&_

```

...and turn the line into two lines, one suffixed with the first number incremented and second doubled, the other suffixed with the first number doubled and second incremented.

```
G`\b(_+),\1\b

```

Keep the line with the matching pair.

```
_+
$.&

```

Convert back to decimal. ~~89~~ 88-byte unsigned decimal arithmetic version (works with 0 as well):

```
/\b(\d+),\1\b/^+%`(\d+),(\d+)$
$&;$.(_$1*),$.(2*$2*)¶$=;$.(2*$1*),$.(_$2*
G`\b(\d+),\1\b

```

Try it online!

# Answer
> 4 votes
# Jelly, 20 bytes

```
ḃ2d2;@+*¥\
0çṪEɗ1#Ḣç

```

Try it online!

# Answer
> 4 votes
# 05AB1E, ~~25~~ ~~22~~ 20 bytes

Takes a doubly nested list as input and outputs a jagged list with each step at one nest-depth.

```
[ć¤Ë#¤xs>R‚ø`R‚s¸sâ«

```

Try it online!

**Explanation**

```
[                      # start a loop
 ć                     # extract the first element of the current list (current path)
  ¤Ë#                  # break if all elements in the head are equal
     ¤xs>              # duplicate one copy of the head and increment another
         R             # reverse the incremented copy
          ‚ø           # zip them together
            `R‚        # reverse the tail of the zipped list
               s¸sâ    # cartesian product with the rest of the current path
                   «   # append to the list of all current paths

```

# Answer
> 3 votes
# Stax, ~~29~~ 26 bytes

```
ä⌠|Tô&cm♂NV↓↔╗╣¢♠╜╒█¡Φ≈ñY@

```

Run and debug it

It's a breadth first search. It seems reasonably fast.

It takes a doubly-array-wrapped pair of integers. The output is a space separated list of values. Every two values represents one pair in the path to the solution.

# Answer
> 2 votes
# Haskell, 95 bytes

```
g s|a:_<-[a|a@((x,y):_)<-s,x==y]=a
g s=g$do a@((x,y):_)<-s;[(x*2,y+1):a,(x+1,y*2):a]
h t=g[[t]]

```

Try it online! Outputs in reverse order, e.g. `h(2,5)` yields `[(12,12),(6,11),(3,10),(2,5)]`.

# Answer
> 2 votes
# Red, 142 bytes

Takes the input as a doubly nested block of the pair of integers in Red's format `(2, 5)` -\> `2x5`

Returns the result as a list ot Red pairs, for example `2x5 3x10 6x11 12x12`. Includes the initial pair.

```
func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]do replace/all{%+ 1x0 * 1x2
%* 2x1 + 0x1}"%""append/only a append copy d l "]f a]

```

Try it online!

## Strict input:

The input is two numbers, for example `2 5`

# Red, 214 bytes

```
func[a b][g: func[c][a: copy[]foreach d c[l: last d if l/1 = l/2[return d]append/only a append copy d l + 1x0 * 1x2
append/only a append copy d l * 2x1 + 0x1]g a]c: copy[]insert/only c reduce[do rejoin[a 'x b]]g c]

```

Try it online!

## Explanation:

```
f: func[a b][
g: func[c][                                   ; recursive helper function
  a: copy[]                                   ; an empty block
  foreach d c[                                ; for each block of the input
    l: last d                                 ; take the last pair
    if l/1 = l/2[return d]                    ; if the numbers are equal, return the block
    append/only a append copy d l + 1x0 * 1x2 ; in place of each block append two blocks
    append/only a append copy d l * 2x1 + 0x1 ; (j+1, k*2) and (j*2, k+1)
  ]                                           ; using Red's arithmetic on pairs
  g a                                         ; calls the function anew
]
c: copy[]insert/only c reduce[do rejoin[a 'x b]]; prepares a nested block from the input
g c                                           ; calls the recursive function
]

```

---
Tags: code-golf, math, number, number-theory
---


# Question
Title: Selective character count (only non-alphanumeric)?
## Challenge (Easy)

> Write a function which takes an argument and returns the number of non-alphanumeric characters found.

## Challenge (Hard)

> Write a function which takes an argument and returns the number of bytes used to store the number of non-alphanumeric characters found. (ie: include calculation for multi-byte characters.)

## Rules / Notes

* Alphanumeric in this case is defined as:

`abcdefghijklmnopqrstuvwxyz` `ABCDEFGHIJKLMNOPQRSTUVWXYZ` `0123456789`
* A null character should count as 0 characters, but as 1 byte when stored.

`NUL`
* Showing multi-byte support (if too complicated) only has to demonstrate one character set or language reference / codepage (if this actually matters. I don't know, so just putting it out there.)

## Winner

Since this is code golf, the shortest code that correctly matches the challege wins.

# Answer
> 5 votes
# Perl, 14 characters

```
y/A-Za-z0-9//c

```

# Answer
> 2 votes
# Jelly, 7 6 4 bytes

```
ḟØBL

```

Try it online!

```
ḟØBL
ḟ         reverse ḟilter: remove all of the input characters that are also in...
 ØB       alphanumeric characters...
   L      and get the Length of the resulting string!

```

**6-byte solution:**

```
ḟØWṖ¤L

```

Try it online!

```
ḟØWṖ¤L
ḟ         reverse ḟilter: remove all of the input characters that are also in...
 ØWṖ¤     the "word" character class with the underscore popped from it, taken as a nilad...
     L    ...and take the length of the resulting string

```

# Answer
> 2 votes
# Stax, 3 bytes (Easy)

```
├Dr

```

Run and debug it

**Explanation**

```
VL-%        # Full program, unpacked
VL          # Push "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
  -         # Remove all elements in b from a.
    %       # Length and implicitly print result

```

# Answer
> 1 votes
# Groovy

## Easy: 26 25 30 characters

```
c={(it=~/[[^\00\w]_]/).size()}

assert c("abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789")== 2
assert c("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")==0
assert c("a-b-7*NNuah ~#77%")==7
assert c('_|') == 2
assert c('\0') == 0

```

## Hard: 47 characters

```
s={it.replaceAll(/[\w&&[^_]]/,'').bytes.size()}

assert s("abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ 0123456789")== 2
assert s("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")==0
assert s("a-b-7*NNuah ~#77%")==7
assert s('_') == 1

```

# Answer
> 1 votes
# D

## easy (29 chars)

```
count!"!isAlphaNum(b)&&b"(s);

```

## hard (35 chars)

`s` needs to be a `char[]`

```
s.length-count!"!isAlphaNum(b)"(s);

```

# Answer
> 1 votes
# , ~~68~~ 42 bytes

-26 bytes thanks to Giuseppe.

```
function(x)nchar(gsub('[[:alnum:]]',"",x))

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 4 bytes (easy)

```
žKмg

```

Try it online.

**Explanation:**

```
žK      # Push "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
  м     # Remove all occurrences of this second string from the input string
   g    # Push and implicitly output the length of the result

```

---

# 05AB1E, 19 bytes (hard)

```
žKмÇεDžy‹i1ë.²<5÷>н]O

```

Thanks to *@Mr.Xcoder* for helping me put two sub-solutions together with `D`, and explaining how `]` closes both the if-statement and foreach-loop. (I accidentally placed the `D` before the `ε` and used one `}` instead of two..)

Try it online.

**Explanation:**

```
žK                     # "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
  м                    # Remove all occurrences of this second string from the input string
   Ç                   # Convert each character to its unicode value
    εD                 # Foreach over this list
         i             #  If the current item
        ‹              #  is maller than
      žy               #  128
          1            #   Use 1
           ë           #  Else
            .²         #   Use log_2
              <        #   minus 1
               5÷      #   integer-divided by 5
                 >     #   plus 1
                  н    #  Take the head of the sublists
                   ]   # Close both the if-else and for-each (shorter version of `}}`)
                    O  # Sum everything together

```

05AB1E doesn't have any builtins for knowing the amount of bytes a character costs, so I'm converting them to unicode values with `Ç` and use the following pseudo-code to determine their bytes:

```
if(unicodeValue < 128)
  return 1
else
  return log_2(unicodeValue-1)//5+1    # (where // is integer-division)

```

Pseudo-code inspired by *@TheBikingViking*'s Python 3 answer for the *Bytes/Characters* challenge.

# Answer
> 1 votes
# Husk, 4 bytes (easy)

```
#(¬□

```

Try it online!

### Explanation

Pretty simple usage of `isanum` ():

```
#(¬□)  -- example: "Input!"
#(  )  -- count number of
 ( □)  -- | is alphanumeric: [73,110,112,117,116,0]
 (¬ )  -- | not: [0,0,0,0,0,1]
       -- : 1

```

# Answer
> 1 votes
# MS-SQL, 85 bytes (easy)

```
SELECT SUM(1)FROM spt_values,t
WHERE type='P'AND SUBSTRING(v,number,1)LIKE'[^a-z0-9]'

```

Handles strings up to 2047 characters. Per our IO standards, input is taken via a pre-existing table **t** with `varchar` field **v**.

This must be run in the `master` database (which exists on every SQL server). This database has a system table `dbo.spt_values`, which, if we filter by `type='P'`, contains counting numbers from 0 to 2047. Join that to our input table to split each character into its own row, then count up those that match the `LIKE` filter (which supports character ranges).

# MS-SQL, 85 bytes (hard)

```
SELECT SUM(2)FROM spt_values,t
WHERE type='P'AND SUBSTRING(v,number,1)LIKE'[^a-z0-9]'

```

You also need to change the input table to an `nvarchar` field **v** instead of `varchar`.

So yeah, this is kind of cheaty, because the nvarchar data type uses 2 bytes for *every* character, even for normal ASCII characters. That means I don't have to distinguish between characters that *could* be stuffed into a single byte and those that can't. But it does strictly satisfy the challenge, since it reflects the number of bytes that SQL is actually using to store `nvarchar` strings.

# Answer
> 0 votes
# Javascript 1.8

## easy (48 chars)

`function f(s)(s.match(/[^a-z0-9]/gi)||[]).length`

# Answer
> 0 votes
## PowerShell, easy, 44

```
filter e{($args-replace"[a-z0-9]").Length}

```

If we stretch the definition of »arguments«, we can shorten it a bit more (**41**):

```
filter e{($_-replace"[`0a-z0-9]").Length}

```

but it then requires input to be sent via the pipeline.

## PowerShell, hard, 71

```
function x{[text.encoding]::utf8.GetByteCount($args-replace'[a-z0-9]')}

```

Again, if we allow the pipeline we get it to **68**:

```
function x{[text.encoding]::utf8.GetByteCount($_-replace'[a-z0-9]')}

```

# Answer
> 0 votes
# Scala

## Easy (43 chars)

```
def c(s:String)=s.count(!_.isLetterOrDigit)

```

## Hard (58 chars)

```
def c(s:String)=s.filter(!_.isLetterOrDigit).getBytes.size

```

# Answer
> 0 votes
# Python

## easy (39 chars)

```
f=lambda s:sum(1-i.isalpha()for i in s)

```

# Answer
> 0 votes
# Brainfuck

## Easy (1397 chars)

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

```

All hand coded. It takes input until it gets a 0xA character signifying end of input (not counted). Only handles up to 255 nonalphanumeric input characters.

# Answer
> 0 votes
**Perl (easy) 27 characters**

```
sub _{$_=shift;(s/\W|_//g)}

```

**usage:**

```
say _('@abc_123ABC -("~ abc')
---> 8

```

# Answer
> 0 votes
**Ruby, easy, 32**

```
f=->s{s.scan(/[^a-z0-9]/i).size}

```

# Answer
> 0 votes
# Gol\>\<\>, Easy, 26 bytes

```
iEh$"0:A[a{"{16F@2k)S^|}~+

```

Try it online!

### How it works

```
iEh$"0:A[a{"{16F@2k)S^|}~+

iEh                         Take input as char; if EOF, print the top as int and halt
   $                        Move the input under the char counter
    "0:A[a{"                Push six boundary chars
            {1              Pull the input to the top, and push 1 (XOR counter)
                            (Stack: [char counter, ...boundary, input, XOR counter])
              6F      |     Repeat 6 times...
                @             Pull a boundary char to the top
                 2k)          Copy the input char and compare (boundary > input)
                    S^        XOR with the XOR counter
                            (Stack: [char counter, input, XOR counter])
                       }~+  Move XOR counter to bottom, discard input, and
                              add to the char counter
                            Repeat indefinitely

```

# Answer
> 0 votes
# Pyth

## Easy, 17 bytes

```
l:z"[a-zA-Z0-9]"k

```

Try it online!

## Hard, 30 bytes

```
/lsm.[\08.BCd:z"[a-zA-Z0-9]"k8

```

Try it online!

# Answer
> 0 votes
# Java 10, 42 bytes (easy)

```
s->s.replaceAll("[A-Za-z0-9]","").length()

```

Try it online.

**Explanation:**

```
s->                               // Method with String parameter and integer return-type
  s.replaceAll("[A-Za-z0-9]","")  //  Remove all digits and letters
   .length()                      //  And return the length

```

---

# Java 10, 102 bytes (hard)

```
s->{int r=0;for(var c:s.replaceAll("[A-Za-z0-9]","").split(""))r+=c.getBytes("utf8").length;return r;}

```

Try it online.

**Explanation:**

```
s->{                              // Method with String parameter and integer return-type
  int r=0;                        //  Result-integer, starting at 0
  for(var c:s.replaceAll("[A-Za-z0-9]","")
                                  //  Remove all digits and letters
             .split(""))          //  And loop over the remaining characters
    r+=                           //   Add to the result-sum:
      c.getBytes("utf8").length;  //    The UTF-8 bytes of the current character
  return r;}                      //  Return the result-sum

```

# Answer
> 0 votes
# Haskell, ~~58~~ 52 bytes (easy)

<sub>-6 bytes, thanks to Laikoni (inverting the test, using `elem` instead)!</sub>

```
f s=sum[1|c<-s,elem c":;<=>?@[\\]^_`"||c>'z'||c<'0']

```

Try it online!

---
Tags: code-golf
---


# Question
Title: Sorting a list of strings without using any built-in sort method
The goal of this Code Golf is to create a program that sorts a list of strings (in ascending order), **without using any built-in sort method** (such as `Array.Sort()` in .NET, `sort()` in PHP, ...). Note that this restriction excludes using a built-in method that sorts an array descending, and then reversing the array.

Some details:

* Your program should prompt for input, and this input is a list of strings containing only ASCII lower-case alphabetic characters `a-z`, comma-separated without spaces. For example:

```
code,sorting,hello,golf

```
* The output should be the given list of strings, but sorted in ascending order, still comma-separated without spaces. For example:

```
code,golf,hello,sorting

```

# Answer
> 3 votes
# GolfScript, ~~26~~ 25 bytes

```
","/.,{{.2$<{\}*}*]}*","*

```

Straightfoward implementation of Bubble Sort.

Try it online in Web GolfScript.

### How it works

```
","/     # Split the input string at commas.
.,       # Get the number of chunks.
{        # Do that many times:
  {      #   Reduce; for each element but the first:
    .2$< #     Push 1 if the last two strings are in descending order, 0 if not.
    {\}* #     Swap these strings that many times.
  }*]    #   Collect the strings dumped by reduce in an array.
}*       #
","*     # Join, separating by commas.

```

# Answer
> 10 votes
## Ruby ~~76~~ ~~54~~ 51 chars

```
x=gets.scan /\w+/;$><<x.dup.map{x.delete(x.min)}*?,

```

# Answer
> 7 votes
# k (16 chars)

Probably doesn't really live up to the spirit of the problem. In k, there is no built in *sort* operator. `<x` returns a list of indices of items in x in sorted order.

```
{x@<x}[","\:0:0]

```

# Answer
> 4 votes
## SED, 135

```
s/.*/,&,!,abcdefghijklmnopqrstuvwxyz/;:;s/\(,\([^,]*\)\(.\)[^,]*\)\(.*\)\(,\2\(.\)[^,]*\)\(.*!.*\6.*\3\)/\5\1\4\7/;t;s/^,\(.*\),!.*/\1/

```

Based on my previous sorting entry

# Answer
> 3 votes
## Ruby, 99 chars (Gnome sort)

```
a=gets.scan /\w+/
p=1
while a[p]
a[p]>a[p-1]?p+=2:(a[p],a[p-1]=a[p-1],a[p])
p-=1if p>1
end
$><<a*?,

```

This just barely beats my bubble sort implementation:

## Ruby, ~~110~~ ~~104~~ 101 chars (Bubble sort)

```
s=gets.scan /\w+/
(z=s.size).times{(0..(z-2)).map{|i|s[i],s[i+1]=s[i+1],s[i]if s[i]>s[i+1]}}
$><<s*?,

```

This does `list.length` iterations, because worst-case scenario takes `list.length - 1` iterations and one more really doesn't matter, and saves 2 chars.

Just for fun, a Quicksort version:

## Ruby, 113 chars (Quicksort)

```
q=->a{if a[1]
p=a.shift
l=[]
g=[]
a.map{|x|(x>p ?g:l).push x}
q[l]+[p]+q[g]
else
a
end}
$><<q[gets.scan /\w+/]*?,

```

# Answer
> 3 votes
## Haskell, 141

```
import Data.List
m=minimum
s[]=[]
s l=m l:s(l\\[m l])
t[]=[]
t s=let(a,b)=span(/=',')s in a:t(drop 1 b)
main=interact$intercalate",".s.t.init

```

At least it’s… **sort** of efficient.

# Answer
> 2 votes
## vba, 165

```
Sub q()
c=","
s=InputBox("?")
Z=Split(s, c)
t=UBound(Z)
For i=1 To t-1
For j=i To t
If Z(i)>Z(j) Then a=Z(i):Z(i)=Z(j):Z(j)=a
Next
Next
Debug.Print Join(Z,c)
End Sub

```

# Answer
> 2 votes
## PHP 83 bytes

```
<?for($x=fgetcsv(STDIN);$x;)${$x[0]>min($x)?x:a}[]=array_shift($x)?><?=join(~Ó,$a);

```

An *O(n3)* implementation of a selection sort. The `Ó` is character 211; a bit-inverted comma.

Sample usage:

```
$ more in.dat
code,sorting,hello,golf

$ php list-sort.php < in.dat
code,golf,hello,sorting

```

# Answer
> 2 votes
# Scala, 122 bytes

## As a one-liner (88 bytes):

```
.permutations.filter(_.sliding(2).map(w=>w(0)<w.last).fold(true)((a,b)=>a&&b)).toSeq(0)

```

(it will sort a list by just doing `list.permutations.fil...` )

## As a program (122 bytes):

```
println(readLine.split(",").toSeq.permutations.filter(_.sliding(2).map(w=>w(0)<w.last).fold(true)((a,b)=>a&&b)).toSeq(0))

```

A longer version if you want it to read from stdin.

This iterate over all the permutations of the given list until it stumble on a sorted one. It's not fast as it takes about 12 seconds to sort a 10 elements list and well over a minute for a 11 elements one.

**\[Edit\]** items need to be unique or `<` can be replaced by `<=`. Also, sorry for necro.

# Answer
> 1 votes
# Python 3 (80 chars)

```
l=input().split(',')
m=[]
while l:m+=[l.pop(l.index(min(l)))]
print(','.join(m))

```

Here is a variation of the while-statement that is of equal length:

```
while l:x=min(l);m+=[x];l.remove(x)

```

# Answer
> 1 votes
# Mathematica ~~66~~ 56

```
Row[#[[Ordering@#]]&[InputString[]~StringSplit~","],","]

```

Some other solutions without the build-in symbol `Ordering`:

## Bogosort: ~~84~~ 74

```
NestWhile[RandomSample,InputString[]~StringSplit~",",!OrderedQ@#&]~Row~","

```

## Bubble Sort: ~~93~~ 83

```
Row[InputString[]~StringSplit~","//.{x___,i_,j_,y___}/;j~Order~i==1:>{x,j,i,y},","]

```

## Another solution as inefficient as bogosort: ~~82~~ 72

```
#~Row~","&/@Permutations[InputString[]~StringSplit~","]~Select~OrderedQ;

```

# Answer
> 1 votes
# Python 3.5+, 73 bytes

This takes inspiration from Steven Rumbalski's answer but uses list comprehension instead of a while loop; the number of iterations comes from the copied list `l` which is the reason this requires additional unpacking generalizations and Python 3.5

```
l=input().split(',');print(*[l.pop(l.index(min(l)))for _ in[*l]],sep=',')

```

# Answer
> 0 votes
## javascript 128

```
a=prompt().split(',');b=[];for(i in a){b.push(a[i]);k=0;for(j in b){j=k;b[j]>a[i]?[c=b[j],b.splice(j,1),b.push(c)]:k++}}alert(b)

```

DEMO fiddle.

i am looking for a way to eliminate `b`.

# Answer
> 0 votes
# R

### Bubble Sort: ~~122~~ 118 characters

```
a=scan(,"",sep=",");h=T;while(h){h=F;for(i in 1:(length(a)-1)){j=i+1;if(a[i]>a[j]){a[j:i]=a[i:j];h=T}}};cat(a,sep=",")

```

### Bogosort: 100 characters

```
a=scan(,"",sep=",");while(any(apply(embed(a,2),1,function(x)x[1]<x[2]))){a=sample(a)};cat(a,sep=",")

```

# Answer
> 0 votes
## Perl, 159

```
perl -F"," -lape "$m=$m<length()?length():$m for@F;$_{10**(2*$m)*sprintf'0.'.'%02d'x$m,map-96+ord,split//}=$_ for@F;$_=join',',map$_{$_+0},grep exists$_{$_+0},'0'.1..'0'.10**100"

```

This never stood a chance to win, but decided to share it because I liked the logic even if it's a mess :) The idea behind it, is to convert each word into an integer (done using the ord function), we save the number as a key in a hash and the string as a value, and then we iterate increasingly through all integers (1..10\**100 in this case) and that way we get our strings sorted.

**WARNING**: Don't run this code on your computer, since it loops through trillions+ of integers. If you want to test it, you can lower the upper range limit and input non-lengthy strings. If for any reason this is against the rules, please let me know and I'll delete the entry!

# Answer
> 0 votes
## JS: 107 chars - Bubble Sort

```
a=prompt().split(/,/);for(i=a.length;i--;)for(j=0;j<i;)a[j]>a[j+1]?[b=a[j],a[j]=a[++j],a[j]=b]:j++;alert(a)

```

I looked at @tryingToGetProgrammingStraight's answer and tried to improve it, but ended up implementing it slightly differently.

# Answer
> 0 votes
# Java, 134 bytes

A method that implements Gnome Sort.

```
void s(String[]a){int m=a.length-1,i=0;while(i<m){while(i>=0&&a[i].compareTo(a[i+1])>0){String t=a[i];a[i]=a[i+1];a[i+1]=t;i--;}i++;}}

```

# Answer
> 0 votes
# Swift, 101 bytes

```
func s(a:[String])->[String]{return a.count<2 ? a:(s(a.filter{$0<a[0]})+[a[0]]+s(a.filter{$0>a[0]}))}

```

Ungolfed:

```
//quicksort
func sort(a:[String]) -> [String]
{
    //return the array if its length is less than or equal to 1
    if a.count <= 1
    {
        return a
    }
    //choose the first element as pivot
    let pivot = a[0]
    //retrieve all elements less than the pivot
    let left = a.filter{ $0 < pivot }
    //retrieve all elements greater than the pivot
    let right = a.filter{ $0 > pivot }
    //sort the left partition, append a new array containing the pivot,
    //append the sorted right partition
    return sort(left) + Array<String>(arrayLiteral: pivot) + sort(right)
}

```

# Answer
> 0 votes
# , 24 chars / 30 bytes (noncompetitive)

```
ï⇔Ĕ⍪;↻ïꝈ)ΞÿѨŗ ï,⇀$≔МƵï;Ξ

```

`Try it here (Firefox only).`

Using selection sort!

# Explanation

```
ï⇔Ĕ⍪;↻ïꝈ)ΞÿѨŗ ï,⇀$≔МƵï;Ξ // implicit: ï=input, Ξ=[]
ï⇔Ĕ⍪;                    // split ï along commas and set it to ï
     ↻ïꝈ)                // while ï's length > 0
         Ξÿ              // push to Ξ:
           Ѩŗ ï,⇀$≔МƵï;  // removed minimum item(s) from ï using builtin
                       Ξ // get sorted array

```

Basically recursively removes and pushes the minimum from the input to another array.

# Answer
> 0 votes
# Ceylon (Bogosort), 119

```
String s(String i)=>",".join([*i.split(','.equals)].permutations.select((p)=>!any{for([x,y]in p.paired)y<x})[0]else[]);

```

Try it online!

I found the `permutations` method and thus ended up with Bogosort (a non-random variant).

Formatted and commented:

```
// a function `s` mapping a String `i` to a String
String s(String i) =>
    // the end result is created by joining the iterable in (...).
    ",".join(
        // take the input, split it on commas, make the result a sequence.
        [*
            i.split(','.equals)   // → {String+}
           ]                      // → [String+]
        // get the iterable of all permutations of this sequence.
        // Yes, this is an iterable of O(n!) sequences (though likely
        // lazily computed, we don't need all in memory at once).
        .permutations              // → {[String+]*}
        // filter this iterable for ordered sequences.
        // Using select instead of filter makes this
        // eager instead of lazy, so we are actually iterating
        // through all n! sequences, and storing the ordered
        // ones. (All of those are equal.)
        .select(
            // this is our function to check whether this sequence
            // is ordered in ascending order.
            (p)=>
               // return if none of the following iterable of booleans is true.
                !any {
                   // This is a for-comprehension. Inside an named argument list
                   // (what we have here, although there is no name) for a
                   // function which wants an iterable, this becomes an iterable,
                   // lazily built from the existing iterable p.paired,
                   // which is just an iterable with all pairs of subsequent
                   // elements.
                      for([x,y] in p.paired)
                        // for each such pair, we evaluate this expression, which
                        // is true when the sequence is not ordered correctly.
                           y < x         // → Boolean
                        // → {Boolean*}
                    }  //   → Boolean
                 //  → Boolean([String+])
               ) // → [[String+]*]
         // we now have a sequence of (correctly sorted) sequences.
         // just take the first one.
         // If we had used `.filter` before, this would have to be `.first`.
               [0]    // → [String+]|Null
         // in case this is null, which can only happen if the original array was
         // empty, so there were no permutations, just use the empty sequence
         //  again. (Actually, split never returns an empty array, so this can't
         //  happen, but the type checker can't know that.)
               else []    // → [String*]
    // so that is what we pass to the join method.
        )   // → String
    ;

```

Without the formatting and parsing it becomes just 90 bytes:

```
String[]s(String[]i)=>i.permutations.select((p)=>!any{for([x,y]in p.paired)y<x})[0]else[];

```

Try it online!

# Answer
> 0 votes
# Perl 5, 77 bytes

```
map{$F[$_]gt$F[$_+1]&&(@F[$_,$_+1]=@F[$_+1,$_])for 0..@F-2}@F;$_=join',',"@F"

```

Try it online!

Simple bubble sort.

# Answer
> 0 votes
# `ruby -plaF,` , 70 bytes

```
o=[]
$F.map{|s|i=o;s.bytes{|b|i=i[b]=[*i[b]]};i[0]=s<<?,}
$_=o*''
chop

```

O(n), if you pretend that resizing and compacting an array is free (it is very not free).

We create a deeply and unevenly nested array `o` by putting a string with bytes b1,b2...bn into the array at position o\[b1\]\[b2\]...\[bn\]. The result looks like `[,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,["a,",,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, [,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,, ["abc,"], ["abd,"], ["abe,"]], ["ac,"], ["ad,"]],, ["c,"]]`

Then we flatten and output it.

# Answer
> 0 votes
> Reusing my own answer on Sort an Integer List

# Tcl, 211 bytes

```
set L [split [gets stdin] ,]
set i 0
time {incr j;set x 0;while \$x<$i {if \"[lindex $L $i]"<"[lindex $L $x]" {set L [lreplace [linsert $L $x [lindex $L $i]] $j $j]};incr x};incr i} [llength $L]
puts [join $L ,]

```

Try it online!

---
Tags: code-golf, sorting
---


# Question
Title: Rotate matrix rows according to the row above
# Specifications

For this challenge, you will be given a matrix of some sort in any reasonable format for a 2-D array. For each row except the last, in order from top (first) to bottom (last), rotate the row below it by `x` to either direction (you choose a consistent direction to use) where `x` is the first element in the current row.

# Reference

A reference implementation in Python can be found here

# Example

Let's walk through an example. Take the following matrix for example:

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

```

Let's say we're rotating right. First we rotate `[4 7 2]` to the right by 1 because the first element of `[1 5 8]` is 1. Thus, we get `[2 4 7]` as the second row. The matrix is now like this:

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

```

Then, we rotate `[3 9 6]` to the right by 2 because the first element of the second row is 2. Thus we get:

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

```

# Challenge

Implement the above

# Test Cases

Test cases are given as a list of lists in Python style.

```
Input -> Output
[[6, 7, 10, 1, 10, 7], [7, 3, 7, 8, 9, 2], [6, 8, 3, 9, 3, 1], [6, 3, 8, 6, 4, 1], [7, 5, 2, 9, 7, 2], [2, 10, 9, 9, 7, 9], [8, 8, 10, 10, 8, 4]] -> [[6, 7, 10, 1, 10, 7], [7, 3, 7, 8, 9, 2], [1, 6, 8, 3, 9, 3], [1, 6, 3, 8, 6, 4], [2, 7, 5, 2, 9, 7], [7, 9, 2, 10, 9, 9], [4, 8, 8, 10, 10, 8]]
[[8, 10, 4, 3, 9, 4, 6], [8, 8, 8, 8, 6, 7, 5], [6, 2, 2, 4, 8, 9, 6], [1, 7, 9, 9, 10, 7, 8]] -> [[8, 10, 4, 3, 9, 4, 6], [5, 8, 8, 8, 8, 6, 7], [2, 4, 8, 9, 6, 6, 2], [7, 8, 1, 7, 9, 9, 10]]
[[6, 2, 4, 4, 4], [5, 9, 10, 5, 4], [3, 5, 7, 2, 2], [1, 5, 5, 10, 10], [8, 2, 3, 2, 1], [3, 3, 9, 5, 10], [9, 5, 9, 7, 2]] -> [[6, 2, 4, 4, 4], [4, 5, 9, 10, 5], [5, 7, 2, 2, 3], [1, 5, 5, 10, 10], [1, 8, 2, 3, 2], [10, 3, 3, 9, 5], [9, 5, 9, 7, 2]]
[[3, 6, 3, 7, 4], [8, 8, 1, 5, 8], [7, 5, 1, 9, 4], [3, 9, 10, 8, 6]] -> [[3, 6, 3, 7, 4], [1, 5, 8, 8, 8], [4, 7, 5, 1, 9], [9, 10, 8, 6, 3]]
[[5, 6, 1, 2, 6], [1, 10, 10, 1, 4], [6, 2, 7, 1, 7], [9, 5, 8, 6, 3], [4, 5, 1, 2, 1], [8, 6, 1, 1, 3]] -> [[5, 6, 1, 2, 6], [1, 10, 10, 1, 4], [7, 6, 2, 7, 1], [6, 3, 9, 5, 8], [1, 4, 5, 1, 2], [3, 8, 6, 1, 1]]
[[10, 1, 2], [9, 9, 10], [2, 4, 7]] -> [[10, 1, 2], [10, 9, 9], [7, 2, 4]]
[[4, 5, 6], [6, 9, 4], [9, 3, 2], [3, 5, 9], [5, 5, 3], [9, 1, 4]] -> [[4, 5, 6], [4, 6, 9], [2, 9, 3], [5, 9, 3], [5, 3, 5], [1, 4, 9]]
[[8, 7, 6, 5], [9, 8, 6, 6], [7, 9, 7, 10]] -> [[8, 7, 6, 5], [9, 8, 6, 6], [10, 7, 9, 7]]
[[10, 2, 8, 8, 1], [2, 10, 1, 4, 10], [3, 2, 5, 3, 8], [5, 1, 8, 1, 8], [6, 1, 3, 1, 2], [7, 9, 1, 1, 2]] -> [[10, 2, 8, 8, 1], [2, 10, 1, 4, 10], [3, 8, 3, 2, 5], [8, 1, 8, 5, 1], [3, 1, 2, 6, 1], [1, 1, 2, 7, 9]]
[[9, 1, 3, 2, 7], [3, 8, 10, 3, 3], [8, 10, 7, 9, 5], [8, 1, 4, 9, 9], [6, 8, 4, 10, 10], [4, 7, 6, 2, 2], [8, 5, 3, 7, 6]] -> [[9, 1, 3, 2, 7], [8, 10, 3, 3, 3], [7, 9, 5, 8, 10], [9, 9, 8, 1, 4], [8, 4, 10, 10, 6], [6, 2, 2, 4, 7], [6, 8, 5, 3, 7]]

```

Generate more testcases here

# Answer
> 6 votes
# Husk, 4 bytes

```
G(ṙ←

```

Try it online!

Rotates rows to the left.

### Explanation

`G` in Husk is `scanl` (or cumulative reduce from left, as some languages call it). When given a function of type `x->x->x` (like in this case) it can use as starting value the first element of the list.

`(` is needed here to combine the following two functions into a single one.

is "rotate to the left" and takes a number and a list as arguments.

returns the first element of a list.

# Answer
> 3 votes
# Jelly, ~~6~~ 5 bytes

```
ṙ@Ḣð\

```

Try it online!

Rotates to the left.

Saved a byte thanks to @Jonathan Allan.

## Explanation

```
ṙ@Ḣð\  Input: array of arrays M
   ð\  Cumulative reduce over each array using
ṙ@       Rotate the RHS array using each in the LHS array
  Ḣ      Head

```

# Answer
> 3 votes
## C++, ~~187~~ 149 bytes

* 38 bytes thanks to Karl Napf

Output is done by the reference type parameter The parameter's type have to be a `std::vector<std::vector<int>>` type

```
auto r=[](auto&a){for(int i=1,j,v;i<a.size();++i){v=a[i-1][0]%a[i].size();for(j=0;j<v;++j){a[i].insert(a[i].begin(),a[i].back());a[i].pop_back();}}};

```

Trying to do as `#define A a[i]` and replacing all occurences of `a[i]` by `A` will result with same byte count code

Code to help for the test :

```
//Shift operator overload
std::ostream& operator<<(std::ostream& os, std::vector<std::vector<int>>& v) {
    os << "{\n";
    for (auto&a : v) {
        os << "\t{ ";
        for (auto&b : a) {
            os << b << ' ';
        }
        os << "},\n";
    }
    return os << "}\n";
}

```

And in the `main` function

```
std::vector<std::vector<int>> t{
    {1,5,8},
    {4,7,2},
    {3,9,6}
};

std::cout << t;

r(t);

std::cout << t;

```

# Answer
> 2 votes
# Haskell, ~~84 59~~ 45 bytes

Shifts to the left (now using Leo's approach):

```
scanl1(\a r->(drop<>take$a!!0`mod`length r)r)

```

Try it online!

# Answer
> 1 votes
# Python 2, 65 bytes

```
l=input();K=0
for i in l:g=-K%len(i);e=i[g:]+i[:g];print e;K=e[0]

```

Try it online!

# Python 2, 55 bytes (possibly broken)

If this version is found to fail for some test cases, I can assure you the above works. I am currently half-asleep, so feel free to remove this version in case it is invalid by editing.

```
l=input();K=0
for i in l:e=i[-K:]+i[:-K];print e;K=e[0]

```

Try it online!

# Answer
> 1 votes
# 05AB1E, 9 bytes

```
vyNFÁ}=нƒ

```

Try it online!

```
vy        # For each row:
  NFÁ}    #   Rotate this row N times (initially 0)
      =   #   Print without popping
       н  #   Get the head
        ƒ #   Assign that to N

```

# Answer
> 0 votes
# Perl 5, 41 + 1 (`-a`) = 42 bytes

```
push@F,shift@F for 1..$r;say"@F";$r=$F[0]

```

Try it online!

Rotates to the left. Takes the input as lines of space separated integers.

**How?**

Remove an element from the left end of the list, put it on the right end as many times as we should rotate (`$r`). Since `$r` starts at `undef` (equivaltent to 0 in this usage), nothing happens to the first line. Output the list. Save the first element of the list in `$r` so we can rotate that many times on the next line.

# Answer
> 0 votes
# Pyth, 11 bytes

```
VQ=ZhJ.>NZJ

```

**Try it here!**

# Explanation

* `VQ` \- For each list in the matrix input:

+ `=Z` \- Assign `Z` to the value of the below statement. Its initial value is `0`, so that helps us with the first row.
    + `h` \- The first element of ...
    + `J.>NZ` \- ... The current list, cyclically rotated by `Z` places, and assigned to a variable `J`.
    + `J` \- Print `J`.

# Answer
> 0 votes
# , 77 bytes

```
function(B){for(i in 2:nrow(B))B[i,]=rep(B[i,],sum(B))[1:ncol(B)+B[i-1,1]]
B}

```

Try it online!

Rotates rows to the right.

Replicates each row of `B` `sum(B)` times (creating a huge vector), then grabs the appropriate values from that replicated vector to put into the correct row.

I also wrote a function in the header that converts from the python matrix format to R matrices.

# Answer
> 0 votes
# APL (Dyalog), 14 bytes

Anonymous tacit prefix function. Takes list of lists as argument and prints rows on separate lines with the numbers in each row separated by single spaces. Rotates left (although the explanation mentions how rotate right).

```
{⎕←⍺⌽⍨⊃⍵}/0,⍨⌽

```

Try it online!

reverse the argument (because reduction is right-to-left)

`0,⍨` append a zero (for initial rotation of zero steps)

`{``}/` reduce by the following anonymous lambda, where  is the element on the left and  on the right (the reduction goes right-to-left

pick the first of the right argument

`⍺⌽⍨` rotate the left argument to the left\* that many steps

`⎕←` output to STDOUT with a trailing line-break

---

* To rotate right, insert a `-` to the right of . This will negate the rotation amount.

---
Tags: code-golf, matrix
---


title: Auto cycler quine

text:
# Question
Title: Auto cycler quine
Make a quine but with a twist.

**Statement**

The quine prints its code but puts its first character at the end.
(You can do it in reverse but include that note in your answer)
The output must then be a program which is also an solution.

Example: Assume your code was `foobar`, running it will return `oobarf` which will be another valid program.

```
foobar -> oobarf
oobarf -> obarfo
obarfo -> barfoo
barfoo -> arfoob
arfoob -> rfooba
rfooba -> foobar
```

**Rules**

* Your code **must not** be an output of some generation of someone else's code that's quite obviously stealing
* Your code must be more than 2 characters long (so short code is no fun)
* Your code must contain at least two different characters (ex: `+++` is not valid)

**Scoring**

As a challenge the shortest code wins.

# Answer
> 20 votes
# Befunge-98 (PyFunge), 2600 bytes

```
ab*1'3:*2+*0pnd3*:::::::::::::::1'3:*3+*0p1'3:*5+*0p1'3:*d+*0p1'3:*f+*0p1'3:*fa++*0p1'3:*fd++*0p1'4'3*f-*0p1'4'3*7-*0p1'4'3*5-*0p6:*:*4-1p6:*:*4+1p6:*:*8+1p6:*:*a+1p6:*:*8+2p6:*:*f1++2p6:*:*f3++2pn75*1-:1'3:*4+*0p6:*:*f2++2pnaa*:::::::::::::::::1'3:*6+*0p1'3:*7+*0p1'3:*f1++*0p1'3:*f2++*0p1'3:*fe++*0p1'3:*ff++*0p1'4'3*e-*0p1'4'3*d-*0p1'4'3*4-*0p1'4'3*3-*0p6:*:*3-1p6:*:*2-1p6:*:*b+1p6:*:*c+1p6:*:*9+2p6:*:*a+2p6:*:*f4++2p6:*:*f5++2pn67*::::::::::1'3:*8+*0p1'3:*a+*0p1'3:*f4++*0p1'3:*f5++*0p1'4'3*f-5-*0p1'4'3*c-*0p1'4'3*2-*0p6:*:*1-1p6:*:*d+1p6:*:*b+2p6:*:*f6++2pna5*::1'3:*9+*0p1'3:*f3++*0p6:*:*1pn68*:::::1'3:*b+*0p1'3:*f8++*0p1'4'3*f-2-*0p1'4'3*9-*0p1'4'3*1+*0p6:*:*f7++2pne8*:::::::1'3:*c+*0p1'3:*f9++*0p1'4'3*f-1-*0p1'4'3*8-*0p1'4'3*2+*0p6:*:*f2++1p6:*:*f+2p6:*:*f8++2pnf4*:1'3:*e+*0p1'4'3*3+*2pn77*::::1'3:*f6++*0p1'4'3*f-4-*0p6:*:*f1++1p6:*:*c+2p6:*:*e+2pnb4*1-::1'3:*f7++*0p6:*:*f+1p6:*:*d+2pnf4*1-::1'3:*fb++*0p6:*:*7+2p1'3:*1+*2pnf4*2-1'3:*fc++*0pn95*:::1'4'3*f-3-*0p1'4'3*a-*0p1'4'3**0p6:*:*1+1pn87*1'4'3*b-*0pnac*2-:1'4'3*6-*0p1'4'3*3+*0pnf4*3-1'4'3*1-*0pn88*2-6:*:*5-1pnc9*1-6:*:*2+1pnb4*:6:*:*3+1p6:*:*6+1pn88*6:*:*9+1pnd4*1-6:*:*e+1pnc8*2-:1'3:**1p1'3:**2pnd7*2+6:*:*4+2pn75*6:*:*6+2pn>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>ab*1'3:*2+*0pnd3*:::::::::::::::1'3:*3+*0p1'3:*5+*0p1'3:*d+*0p1'3:*f+*0p1'3:*fa++*0p1'3:*fd++*0p1'4'3*f-*0p1'4'3*7-*0p1'4'3*5-*0p6:*:*4-1p6:*:*4+1p6:*:*8+1p6:*:*a+1p6:*:*8+2p6:*:*f1++2p6:*:*f3++2pn75*1-:1'3:*4+*0p6:*:*f2++2pnaa*:::::::::::::::::1'3:*6+*0p1'3:*7+*0p1'3:*f1++*0p1'3:*f2++*0p1'3:*fe++*0p1'3:*ff++*0p1'4'3*e-*0p1'4'3*d-*0p1'4'3*4-*0p1'4'3*3-*0p6:*:*3-1p6:*:*2-1p6:*:*b+1p6:*:*c+1p6:*:*9+2p6:*:*a+2p6:*:*f4++2p6:*:*f5++2pn67*::::::::::1'3:*8+*0p1'3:*a+*0p1'3:*f4++*0p1'3:*f5++*0p1'4'3*f-5-*0p1'4'3*c-*0p1'4'3*2-*0p6:*:*1-1p6:*:*d+1p6:*:*b+2p6:*:*f6++2pna5*::1'3:*9+*0p1'3:*f3++*0p6:*:*1pn68*:::::1'3:*b+*0p1'3:*f8++*0p1'4'3*f-2-*0p1'4'3*9-*0p1'4'3*1+*0p6:*:*f7++2pne8*:::::::1'3:*c+*0p1'3:*f9++*0p1'4'3*f-1-*0p1'4'3*8-*0p1'4'3*2+*0p6:*:*f2++1p6:*:*f+2p6:*:*f8++2pnf4*:1'3:*e+*0p1'4'3*3+*2pn77*::::1'3:*f6++*0p1'4'3*f-4-*0p6:*:*f1++1p6:*:*c+2p6:*:*e+2pnb4*1-::1'3:*f7++*0p6:*:*f+1p6:*:*d+2pnf4*1-::1'3:*fb++*0p6:*:*7+2p1'3:*1+*2pnf4*2-1'3:*fc++*0pn95*:::1'4'3*f-3-*0p1'4'3*a-*0p1'4'3**0p6:*:*1+1pn87*1'4'3*b-*0pnac*2-:1'4'3*6-*0p1'4'3*3+*0pnf4*3-1'4'3*1-*0pn88*2-6:*:*5-1pnc9*1-6:*:*2+1pnb4*:6:*:*3+1p6:*:*6+1pn88*6:*:*9+1pnd4*1-6:*:*e+1pnc8*2-:1'3:**1p1'3:**2pnd7*2+6:*:*4+2pn75*6:*:*6+2pn>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>

```

Try it online!

This making this was a hellfest.

How this works:
The program is a bunch of put statements that assembles a Program B around itself which then prints half of the source byte shifted twice.
The program is actually 2 copies of a 1300 byte program, this is so it's ensured that the whole 1300 byte program always gets ran as a whole.

Better explanation:
Every Befunge-98 quine needs to contain symbols such a `@` or `q` and `,`
**Problem**: None of those symbols are a good starting point especialy since `@` and `q` terminate the program instantly.
**Solution**: Get rid of those characters in the source code

**Problem**: How?
**Solution**: Use `p` (put) commands to modify the source code to include the required characters which will print the contains of the source code shifted by one byte and **not** use the `g` command which is cheating.

**Problem**: (sigh when will these end)
A put command pops 3 values `n x y` which determine character, x-coord, y-coord however when the initialization of these values is split in half it can write bad characters in the beginning source code making it useless for quining.
**Solution**: (last one I promise)
Use 2 copies of the source code, the latter one being the "correct one" this accidentally fixes another problem which is that a put statement (p command + the constant initializers) which is split in half will not get executed, this is fixed by having 2 copies of each statement. Last thing this needs to work is how do we make the whole source code out of a half?

**Answer**:

This is visual proof of why two copies of a string byte shifted == Two copies of a byte shifted string. That means we can take a half of the code, byte shift it, then print it twice (OR take half of the code, byte shift it, print, repeat \[That's what actually happens\])

**How this is implemented**: Assume 0123456789abcdef is the source

Befunge Pseudocode:

```
0123456789abcv;;"123456789abcdef" < go this way <--
             >PS'0,   repeat 2x   ^

```

PS means Print Stack (not a real instruction). We push half of the source code in reverse onto the stack using `""` then we print the stack and then we fetch (`'` command) the first character `0` which we move in front of the `'` and print it last which causes the byte shift, then we repeat the cycle once more to print the second copy. One technicality to deal with are the symbols inside the source, this can cause trouble if we write it while executing the source code, I circumvented this by adding more put statements which take care of it externally.

This makes the code look something like this:

**Explanation**:
Green Highlight: Code that takes care of adding characters into the source
Grey Letters (probs poor visibility sorry): Code that gets added by green code
Red Highlight: Code that moves first character of the second half of source code into the Blue area.
Blue Highlight: See Red Highlight
Orange Highlight: Code that makes sure we terminate after we wrote 2 byte shifted copies by putting a `@` (terminate) command into the Yellow Area.

Arrows should hopefully make it clearer how the code flow goes.

Here comes the last tough part:
**Where do ~~babies~~ source code come from?**

Short answer: C# Magic
Long answer: 100+ Befunge code snippets made by hand compiled by C# code. I manually wrote about 100 constant initializers (a piece of befunge code that pushes a certain number to stack) by hand and then used a custom C# program to compile it into the 1300 byte Befunge output, which I then copy pasted twice and made the final program.

Are you still here? Great thank you for reading! (or at least scrolling to the end)
I hope my bad jokes were fun and not annoying.

Note: No put statement in this code creates a g command which would be cheating.

EDIT: I have verified the code using the following Javascript code in TIO using developer tools

```
setInterval(()=>{document.getElementById("code").value =
document.getElementById("output").value;
document.getElementById("run").click();}, 2000);

```

---
Tags: code-golf, quine
---