title: ADFGX Cipher Encryption

text:
# Question
Title: ADFGX Cipher Encryption
# ADFGX cipher encryption

The ADFGX cipher was used by the German army in WWI. Write a program to encipher with it!

It works as follows:

1. Create a 5x5 Polybius square with a mixed alphabet. The polybias square is labled `A D F G X` along the top and left.
2. Generate the pairs, so `A` in its non-mixed position is `AA`, `B` is `AD` and so on.
3. Perform columnar transposition using the columnar key.
4. Output the ciphertext.

# Rules

* Your program should either define a function that accepts the arguments of the mixed alphabet and the columnar transposition key, in that order, or accept the alphabet/key as command-line arguments. You can also get input from `STDIN`.
* Standard loopholes apply.
* You can't use a pre-written columnar transposition library (or, for that matter, ADFGX) - i.e. no running something like `import cipherpack`.

# Scoring

This is , so shortest code (in bytes) wins!

# Test cases

My example runs used a failed source. I'll do some more later.

# Leaderboard

Run the Stack Snippet to generate a leaderboard.

```
/* Configuration */

var QUESTION_ID = 71997; // Obtain this from the url
// It will be like https://XYZ.stackexchange.com/questions/QUESTION_ID/... on any question page
var ANSWER_FILTER = "!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe";
var COMMENT_FILTER = "!)Q2B_A2kjfAiU78X(md6BoYk";
var OVERRIDE_USER = 50171; // 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 "https://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 "https://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,]*[^\s,]),.*?(\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,
      });

  });

  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;
    if (/<a/.test(lang)) lang = jQuery(lang).text();

    languages[lang] = languages[lang] || {lang: a.language, 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 > b.lang) return 1;
    if (a.lang < b.lang) 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="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>
<div id="language-list">
  <h2>Winners 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>
<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>
```

**Note:**

It is not necessary to split the output into groups of five.

# Answer
## Pyth, 26 bytes

```
seMhDC,Q.TcsXwz^"ADFGX"2lQ

```

For this, the second line (columnar key) needs to be in quotes, which is acceptable by default.

Try it here.
> 3 votes

# Answer
## Pyth, ~~36~~ ~~34~~ ~~33~~ ~~32~~ 31 bytes

```
JwseMhDC,J.Tcsm@^"ADFGX"2xzdwlJ

```

```
Jw                                assign (z, J) to 2 lines of input
              m             w     map over each char of a 3rd input line...
                ^"ADFGX"2         generate ['AA', 'AD', 'AF', ...]
                         xzd      find the index of this char in z
               @                  index into ^^ with ^
             s                    join groups of 2 ch. into one string
            c                lJ   split ^ into groups of len(J) chars
          .T                      transpose
       C,J                        pair elems up with chars of J
     hD                           sort by chars of J (the key)
   eM                             get rid of the chars of J now
  s                               join

```

Thanks to Thomas Kwa for a byte!

Sample run, using the example from Wikipedia:

```
llama@llama:~$ pyth -c 'JwjdeMhDC,J.Tcsm@^"ADFGX"2xzdwlJ'
BTALPDHOZKQFVSNGJCUXMREWY
CARGO
ATTACKATONCE
FAXDF ADDDG DGFFF AFAX AFAFX

```
> 3 votes

---
Tags: code-golf, cryptography, cipher
---


title: How many words of power did I shout?

text:
# Question
Title: How many words of power did I shout?
In Skyrim, the player character can use powerful magic shouts (Thu'ums) to achieve their goals. Every shout consists of three words, however, the player can use the first one or two words to achieve the same effect with less power but at a shorter cooldown.

Given a lowercase ASCII Thu'um phrase **without punctuation or spaces**, return how many words of power it contains.

Example:

```
fusrodah   -> 3
dur        -> 1
kaandrem   -> 2
odah       -> 2
vengaarnos -> 3

```

The input will **always** be a lowercase ASCII string formed by taking one of the shouts below, choosing the first 1, 2, or 3 words from that shout, and concatenating the words in order.

```
dur neh viir
faas ru maar
feim zii gron
fo krah diin
fus ro dah
gaan lah haas
gol hah dov
hun kaal zoor
iiz slen nus
joor zah frul
kaan drem ov
krii lun aus
laas yah nir
lok vah koor
mid vur shaan
mul qah diiv
od ah viing
raan mir tah
rii vaaz zol
strun bah qo
su grah dun
tiid klo ul
ven gaar nos
wuld nah kest
yol toor shul
zul mey gut
zun haal viik

```

So `fus`, `fusro`, and `fusrodah` are all valid inputs, but `fusroviir` isn't because it uses words from mixed shouts, and `rodah` isn't because it's not a prefix of a shout. You also don't have to handle the empty string input.

---

Shortest code in bytes wins.

# Answer
> 17 votes
## Retina, ~~78~~ ~~42~~ ~~15~~ 14 bytes

```
ul
xo
[aeiou]+

```

Try it online

**tiidkloul** is the only word that doesn't have the same amount of vowel sequences as the number supposed to be printed. Therefore we need to match the word to give it an extra vowel sequence. `ou` will only match tiidkl**ou**l and we can then replace **ou** with **oxo** which creates the extra sequence.

My initial approach wasn't this simple, but was build around removing all consonants, then removing a few vowel sequences (`ai|ii|aa|...`) and then finally counting the numbers of letters. But thanks to @Martin Büttner for thinking of `[aeiou]+` instead.

# Answer
> 1 votes
## Retina, 313 bytes

```
ah|aus|bah|d(ah|ii[nv]|ov|rem|u[nr])|[fhl]aas|f(eim|o|rul|us)|g(aa[nr]|ol|rah|ron|ut)|haal|hah|hun|iiz|joor|k(aa[ln]|est|lo|oor|rah|rii)|lah|lok|lun|m(aar|ey|i[dr]|ul)|n[ae]h|nir|n[ou]s|od|ov|qah|qo|r(aan|ii|o|u)|s(haan|hul|len|trun|u)|tah|tiid|toor|ul|v(aaz|ah|en|iin?[gkr]|ur)|wuld|yah|yol|z(ah|ii|[ou][ln]|oor)

```

Try it online!

Based on a few simple observations:

* All words are unique, regardless of their position.
* No word is a prefix of another word.
* The input is guaranteed to be valid.

That means we can simply count how many of words appear in the string without overlap. That's exactly what a regex does. I've tried compressing the regex a little beyond just concatenating all the words with `|` (which would be 351 bytes), but I'm sure this is far from optimal. For a start, I've definitely not exploited all common parts optimally. But more importantly, it's possible to compress the string even further by making it match more strings than valid words, as long as those can't accidentally match part of a valid word (because then they'll just never be matched). I'm pretty sure one would have to automate the compressing to really be sure it's optimal.

# Answer
> 1 votes
# Perl 5, 28 bytes

Byte count includes one for `-p`.

```
s/ou/oxo/;$_=()=/[aeiou]+/g

```

Stolen straight from dev-null. (Thanks, dev-null!)

---
Tags: code-golf, string, kolmogorov-complexity
---


title: Maximise the squared difference

text:
# Question
Title: Maximise the squared difference
Consider a permutation of the integer values from `1` to `N`. E.g. this example for `N = 4`:

```
[1, 3, 4, 2]

```

We'll consider this list to be cyclic, such that `1` and `2` are treated as adjacent. One quantity we can compute for such a list is the total squared difference of adjacent values:

```
(1-3)² + (3-4)² + (4-2)² + (2-1)² = 10

```

Your task is to find a permutation which maximises this quantity, given a positive integer `N`. In the case of `N = 4` the above example is not optimal (in fact, it's minimal). We can achieve a total squared difference of `18` with the following permutation (as well as several others):

```
[1, 4, 2, 3]

```

Your algorithm must run in polynomial time (of `N`). In particular, you cannot simply compute the total squared difference of all permutations.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

Output may be in any convenient, unambiguous, flat list or string format. You may choose to return a list with values from `0` to `N-1` instead of `1` to `N`.

Standard rules apply.

## Test Data

There is a nice analytical solution for this problem. E.g. all valid solutions for `N = 10` are equivalent to the following list (up to cyclic shifts and reversal):

```
[7, 5, 6, 4, 8, 2, 10, 1, 9, 3]

```

I don't want to reveal too much beyond that (although it's probably enough to figure out the pattern), so instead of giving any more examples, you can check that your results have the following total squared differences for a given `N`:

```
N    Total squared difference

1                         0
2                         2
3                         6
4                        18
5                        36
6                        66
7                       106
8                       162
9                       232
10                      322
33                    11936
100                  333202
333                12308236
1000              333332002

```

This is OEIS entry A064842 (which also contains a reference to a paper with a solution to this challenge if you're stuck).

# Answer
> 7 votes
# Jelly, ~~24~~ ~~21~~ ~~15~~ ~~14~~ ~~10~~ 9 bytes

```
RUĖµ«/€ị"

```

To compute the total squared difference, append `µ_ṙ1$²S` to the code. Try it online!

### Background

One way to generate a permutation with maximized squared difference is to take the integers **1** to **n** in ascending order, and swap the second from the left with the second from the right, the fourth from the left with the fourth from the right, and so forth until we meet in the middle.

For example, for **n = 8, 9** we have

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

```

(carets mark integers to be swapped), which results in

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

```

after swapping.

One way to achieve these swaps, independently of the parity of **n**, is as follows.

Start by writing the integers in ascending order and in descending order, one below the other.

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

```

For each pair of integers, compute the minimum of the pair. This gives the distance to the nearest edge, i.e., the index from the left or the right (whichever is lower).

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

1 2 3 4 4 3 2 1        1 2 3 4 5 4 3 2 1

```

If the minimum is odd, the integer should stay in its place, so we select the one from the first row; if it is even, the integers should be swapped, so we select the one from the second row.

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

```

This is the desired output.

### How it works

```
RUĖµ«/€ị"    Main link. Input: n

R            Range. Yields [1, ..., n].
 U           Upend. Yields [n, ..., 1].
  Ė          Enumerate. Yields p := [[1, n], [2, n-1], ... [n-1, 2], [n, 1]].

   µ         Begin a new, monadic chain. Argument: p
     /       Reduce...
      €        each pair of p...
    «          by minimum.
        "    For each minimum and the corresponding pair of p:
       ị       Select the element at that index.
            Indices are modular and 1-based in Jelly, so this selects the first
            element if the minimum is odd, and the second one if it is even.

```

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

```
n=>[...Array(n)].map((_,i)=>(i<n/2|n%2)^i%2?i+1:n-i)

```

*9 bytes saved thanks to @Neil!*

## Explanation

This approach determines the number that should be at index `i` with a length of `n` rather than concatenating the results to an array. This is based on the following observation (using `n = 7` as an example):

* Start with the lowest number on the left and the highest on the right: `[ 1, 7 ]`
* Switch the order so the lowest is on the *right* and the highest is on the left, increment the lowest, decrement the highest, and place them in the middle of the array: `[ 1, 6, 2, 7 ]`
* Repeat until the highest and lowest converge: `[ 1, 6, 3, 4, 5, 2, 7 ]`

The higher and lower numbers can easily be expressed as `n-i` and `i+1` respectively.

```
var solution =

n=>
  [...Array(n)] // create an array of length n
  .map((_,i)=>  // set each value of the array at index i
    (i<n/2      // if we're on the left side,
    |n%2)       // or we're on the right and n is odd, even i => lower, odd i => higher
    ^i%2?       // else even i => higher, odd i => lower
    i+1:n-i
  )
```

```
N = <input type="number" id="input" oninput="result.textContent=solution(+this.value)" />
<pre id="result"></pre>
```

# Answer
> 5 votes
## Python2, ~~105~~ 98 bytes

*7 bytes saved thanks to the comment by @Dennis*

```
n=input()
r=([],[n/2+1])[n%2]
for i in range(n/2,0,-1):k=[n+1-i];r=([i]+r+k,k+r+[i])[i%2]
print r

```

### Edited version 58 bytes

```
lambda n:[(n-i-1,i)[(i+(n,1)[i<n/2])%2]for i in range(n)]

```

I already believed it should be possible to do it as a one-liner, but the logic was too complex for me. Seeing the JavaScript-answer by @user81655 and the lambda-notation in @Dennis Python-answer, I gave it new try.

The condition is equal to

```
if i < n/2:
    i%2 != n%2
else:
    (i+1)%2

```

Unfortunately all the transformation effort saves only ~~one~~ no byte compared to the direct translation `(i<n/2or n%2)!=i%2` of the JavaScript-logic.

# Answer
> 4 votes
# Python, ~~51~~ 49 bytes

```
lambda n:[(i^min(i,~i%n)%-2)%n for i in range(n)]

```

*Thanks to @xnor for golfing off 2 bytes!*

Try it on Ideone.

### How it works

If **i** is a number in **\[0, ..., n - 1\]**, then **~i % n = -(i + 1) % n = -(i + 1) + n = (n - 1) - i**, meaning that it maps **0** to **n - 1**, **1** to **n - 2** and, in general, the **j**th item from the left to the **j**th from the right.

As explained in my Jelly answer, we can construct the output by peeking at the lower value among **i** and **~i % n**, and pick **i** if it is even and **~i % n** if it is odd. We achieve this as follows.

* If the minimum is even, `min(i,~i%n)%-2` will yield **0**, so XORing the result with **i** will yield **i**, and computing its residue modulo **n** will return **i**.
* If the minimum is odd, `min(i,~i%n)%-2` will yield **-1**, so XORing the result with **i** will yield **~i**, so the entire expression evaluates to **~i % n** as desired.

# Answer
> 2 votes
# PHP, ~~77~~ ~~76~~ ~~51~~ ~~50~~ 49 bytes

Uses ISO 8859-1 encoding.

Assembling the first half of the array like this:

* Odd numbers have their index value (1, 3, 5..)
* Even numbers have the value of `N+1-index` (9, 7, 5)
* This results in `1, 9, 3, 7, 5`

As for the second half of the array, the outermost values add up to `N+1`, which means you can get the corresponding right value from `N-[left value]` where the left value is already known.

```
for(;$k=$argv[1]-$j++;)echo" ",min($j,$k)%2?$j:$k;

```

Run like this (this also shows the total squared difference) (`-d` added for aesthetics only):

```
php -d error_reporting=32757 -r 'for(;$k=$argv[1]-$j++;)echo~ß,$x[]=min($j,$k)%2?$j:$k;  for(;$c=$x[+$i++];)$b+=($c-($x[$i]?:$x[0]))**2;echo"\n$b\n";' 10

```
* Saved a byte by negating left/right condition so the second ternary can be nested without parentheses
* Saved 25 bytes by shamelessly implementing Dennis' algorithm
* Saved a byte by getting rid of the needed space after `echo`
* Saved a byte by using  to yield a space.

# Answer
> 1 votes
# Python 2, 100

I know there's already a python answer, but I think I may have done this differently.

```
n=input();a=n%2;b=n/2;x=[b+1,b+a][a:]
for i in range(b+a-1):f=1-i%2*2;x=[x[-1]-f]+x+[x[0]+f]
print x

```

And as an extra to test the total score:

```
def t(x,n):return sum((x[i]-x[(i+1)%n])**2for i in range(n))

```

# Answer
> 1 votes
# CJam, ~~17~~ ~~15~~ 14 bytes

```
{,W%ee_::e<.=}

```

This is a function that pops an integer **n** from the stack and pushes a permutation of **\[0 … n-1\]** in return. The code uses the same approach as my Jelly answer.

Try it online!

### How it works

```
,W%ee_::e<.=    Function body. Stack: N

,               Turn N into [0 ... N-1].
 W%             Reverse to push [N-1 ... 0].
   ee           Enumerate. This pushes [[0 N-1] [1 N-2] ... [N-2 1] [N-1 0]].
     _          Push a copy of the array of pairs.
      ::e<      Reduce each pair by minimum.
          .=    Vectorized selection.
                For the Ith minimum M, select the Mth element of the Ith pair.
                Indices are modular and 0-based in CJam, so this selects the first
                element if the minimum is even, and the second one if it is odd.

```

# Answer
> 1 votes
## LISP, 86 bytes

```
(defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))

```

The inputs of the function allow to choose the start (m) and the end (n) values of the sequence.

For testing the function according to the provided samples, n is fixed to N and m to 1.

Here the code to test the function:

```
    (defun g(n m)(if(= n m)(list n)(if(< m n)(cons m(reverse(cons n(g(- n 1)(+ m 1))))))))

(defun sq (c)
    (apply #'+ (mapcar #'(lambda(x y) (* (- x y) (- x y))) c (append (cdr c) (list (car c))))))

(format t "N~20TSequence~50TSquared Difference~%")
(mapcar #'(lambda (x)(format t "~S~20T~S~50T~S~%" x (g x 1) (sq (g x 1)))) '(1 2 3 4 5 6 7 8 9 10 33 100 333 1000))

```

Try it on Ideone!

# Answer
> 1 votes
# Julia, 39 bytes

```
n->map(i->min(i-1,n-i)%2>0?n-~-i:i,1:n)

```

This prints a permutation of **1:n**. A permutation of **0:n-1** does neither cost nor save bytes:

```
n->map(i->min(i,n+~i)%2>0?i:n+~i,0:n-1)

```

This last version is a direct port of my Python answer.

# Answer
> 0 votes
# R, ~~117~~ 86 bytes

```
z=1:(n<-scan());a=pmin(z,n:1);for(i in seq(2,,2,n%/%2))z[b]=z[rev(b<-which(a==i,T))];z

```

*edit* replaced buggy long version with an implementation of @Dennis' Jelly algorithm

# Answer
> 0 votes
## ES6, 77 bytes

```
n=>[...Array(n)].map(_=>r[++i&2?"push":"unshift"](i&1?n--:++j),i=j=0,r=[])&&r

```

The `i&1` samples the digits from the extremes to the middle. The `i&2` adds them to the beginning or end of the result in pairs.

---
Tags: code-golf, array, permutations, restricted-complexity
---


title: Print the input in hexadecimal

text:
# Question
Title: Print the input in hexadecimal
## Challenges

You need to do a program that outputs the input string to hexadecimal!

For each character in the input string, convert it's ascii value to hexadecimal and output it out.

## Example

```
Something = 536f6d657468696e67

```

Of course, this is code golf, so the shorter code wins!

# Answer
## Pyth, 3 bytes

```
.Hz

```

Pyth docs:

```
.H <str>
  Converts A to a hexadecimal string, treating the string as a base 256 integer.

```

`z` is a variable autoinitialized to `input()`.

Try it here.
> 2 votes

# Answer
## Bash, 6 bytes

```
xxd -p

```
> 1 votes

# Answer
# JavaScript ES6, 49 bytes

```
s=>s.replace(/./g,l=>l.charCodeAt().toString(16))

```

Try it online
> 1 votes

# Answer
## Python3 console, 21 bytes

```
input().encode("hex")

input() -- Gets the input in a string.
       .encode("hex") -- Encodes it to hexadecimal.

```

Doing this on the console saves the `print` argument.
> 0 votes

# Answer
# , 7 chars / 9 bytes

```
ïⓢ⒨⒞ⓧ)⨝

```

`Try it here (Firefox only).`

Explanation later.
> 0 votes

# Answer
# JavaScript ES6, 50 bytes

```
s=>[for(c of s)c.charCodeAt().toString(16)].join``

```

Using an array generator comprehension, it loops through each character of the string and generates an array of the transform, then call `.join()` with an empty string as an argument to prevent inclusion of commas in default array `toString()` method.

Try it Online

This currently only works in Firefox v ≥ 30
> 0 votes

# Answer
# TeaScript, 5 bytes

```
ΣcT16

```

I really need to add base conversion built-ins

Try it online

## Explanation

```
Σ    // Loop through input
 c   // Get char code
 T16 // To hexadecimal

```
> 0 votes

# Answer
# Perl 6, 25 bytes

```
{lc [~] .ords».base(16)}

```

### Usage:

```
my &code = {lc [~] .ords».base(16)}

say code 'Something';
# 536f6d657468696e67

```
> 0 votes

# Answer
## Python, 24 bytes

```
lambda x:x.encode("hex")

```

Test:

```
a=lambda x:x.encode("hex")
a("something")    # 736f6d657468696e67
a("Hello World!") # 48656c6c6f20576f726c6421

```
> 0 votes

---
Tags: code-golf, hexadecimal
---


title: Chocolate numbers

text:
# Question
Title: Chocolate numbers
Given an `m` by `n` chocolate bar, `m,n` positive, output the number of ways to break the bar into `mn` 1 by 1 pieces where each break occurs on a gridline.

Order is important. Pieces are also distinguishable, so the two pieces on either end of a 1 by 3 chocolate bar are not equivalent.

For instance, for a 2 by 2 block we have:

```
 _ _            _   _            _   _            _   _
|_‖_|    ->    |‗| |_|    ->    |_| |‗|    ->    |_| |_|
|_‖_|          |_| |_|           _  |_|           _   _
                                |_|              |_| |_|

 _ _            _   _            _   _            _   _
|_‖_|    ->    |_| |‗|    ->    |‗| |_|    ->    |_| |_|
|_‖_|          |_| |_|          |_|  _            _   _
                                    |_|          |_| |_|

 _ _            _ _              _   _            _   _
|‗|‗|    ->    |_‖_|      ->    |_| |_|    ->    |_| |_|
|_|_|           _ _               _ _             _   _
               |_|_|             |_‖_|           |_| |_|

 _ _            _ _               _ _             _   _
|‗|‗|    ->    |_|_|      ->     |_‖_|    ->     |_| |_|
|_|_|           _ _              _   _            _   _
               |_‖_|            |_| |_|          |_| |_|

```

Hence there are 4 ways to break up a 2 by 2 chocolate bar.

### Rules

* Input will be two integers via function input, STDIN, command line or similar. Output a single number, the number of ways to break up the chocolate bar.
* Since the numbers go up pretty quickly, don't worry if the output exceeds the integer limits of your language – your submission will be valid as long as the algorithm theoretically works for all possible inputs.

### Test cases

The output doesn't depend on the order of `m,n`, so the test cases are listed such that `m <= n`.

```
1 1 -> 1
1 2 -> 1
1 3 -> 2
1 4 -> 6
1 5 -> 24
1 10 -> 362880

2 2 -> 4
2 3 -> 56
2 4 -> 1712
2 5 -> 92800
2 10 -> 11106033743298560

3 3 -> 9408
3 4 -> 4948992
3 5 -> 6085088256
3 10 -> 76209753666310470268511846400

4 4 -> 63352393728

```

A261964 is the chocolate numbers arranged in a triangle such that each row corresponds to the sum `m+n`.

# Answer
> 7 votes
# Mathematica, 85 bytes

```
f=If[##==1,1,Tr[Sum[Binomial[1##-2,i#-1]f[i,#]f[#2-i,#],{i,#2-1}]&@@@{{##},{#2,#}}]]&

```

**Test case**

```
f[4,4]
(* 63352393728 *)

```

# Answer
> 3 votes
# Python 3, ~~168~~, ~~156~~, 147 bytes

Made improvements thanks to chat

```
f=lambda n:n<1or n*f(n-1);a=lambda m,n,c=lambda m,n:sum(f(m*n-2)/f(i*n-1)/f((m-i)*n-1)*a(i,n)*a(m-i,n)for i in range(1,m)):+(m+n<4)or c(m,n)+c(n,m)

```

Ungolfed:

```
f=lambda n:n<1or n*f(n-1) # Factorial
def a(m, n):
    if m+n < 4:
        return 1
    first = 0
    for i in range(1,m):
        first += f(m*n-2) * 1/f(i*n-1) * 1/f((m-i)*n-1) * a(i,n) * a(m-i,n)
    second = 0
    for i in range(1,n):
        second += f(m*n-2) * 1/f(i*m-1) * 1/f((n-i)*m-1) * a(i,m) * a(n-i,m)
    return first + second

```

Algorithm was based on this paper.

I could probably cut it down a lot more, I'm just not sure where

# Answer
> 3 votes
# R, ~~208~~ 198 bytes

```
f=function(m,n){g=function(i,j){a=0;if(j>1)for(x in 2:j-1)a=a+choose(j*i-2,x*i-1)*M[x,i]*M[j-x,i];a};s=max(m,n);M=matrix(1,s,s);for(i in 1:s)for(j in 1:s)if(i*j>2)M[i,j]=M[j,i]=g(i,j)+g(j,i);M[m,n]}

```

Indented, with newlines:

```
f = function(m,n){
    g=function(i,j){
        a = 0
        if(j>1) for(x in 2:j-1) a = a + choose(j*i-2,x*i-1) * M[x,i] * M[j-x,i]
        a
    }
    s = max(m,n)
    M = matrix(1,s,s)
    for(i in 1:s) for(j in 1:s) if(i*j>2) M[i,j] = M[j,i] = g(i,j) + g(j,i)
    M[m,n]
}

```

Usage:

```
> f(3,1)
[1] 2
> f(3,2)
[1] 56
> f(3,3)
[1] 9408
> f(4,3)
[1] 4948992
> f(5,3)
[1] 6085088256

```

# Answer
> 2 votes
# Python 2, 135 bytes

```
C=lambda A:sum(C(A[:i]+A[i+1:]+[(c,H),(W-c,H)])for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1
print C([input()])

```

Here's what I came up with. It's really slow, but here's a faster version (needs repoze.lru):

```
from repoze.lru import lru_cache
C=lru_cache(maxsize=9999)(lambda A:sum(C(tuple(sorted(A[:i]+A[i+1:]+((c,H),(W-c,H)))))for i,Q in enumerate(A)for W,H in(Q,Q[::-1])for c in range(1,W))or 1)
print C((input(),))

```

### Examples

```
$ time python2 chocolate.py <<< 2,5
92800

real    0m2.954s
user    0m0.000s
sys     0m0.015s

$ time python2 chocolate-fast.py <<< 3,5
6085088256

real    0m0.106s
user    0m0.000s
sys     0m0.015s

```

### Explanation

The code defines a function `C` that takes an array of pieces. The algorithm is as such:

1. `for i,Q in enumerate(A)`: loop through the array of pieces.
2. `for W,H in(Q,Q[::-1])`: calculate ways twice, rotating 90 degrees.
3. `for c in range(1,W)`: loop through possible positions to split at.
4. `A[:i]+A[i+1:]+[(c,H),(W-c,H)]`: get a list without the split piece and with the two new pieces.
5. `C(…)`: call the function again on that list.
6. `sum(…)`: sum the results for each possible split.
7. `or 1`: if no splits are possible, there is exactly one way to split the chocolate.

Finally, the code is called with an array containing the input.

# Answer
> 1 votes
## ES6, 141 bytes

```
c=(m,n)=>(f=n=>n<2||n*f(n-1),h=(m,n)=>[...Array(m-1)].reduce((t,_,i)=>t+f(m*n-2)/f(++i*n-1)/f((m-i)*n-1)*c(i,n)*c(m-i,n),0),h(m,n)+h(n,m))||1

```

Based on the formula found by @CameronAavik. Ungolfed:

```
function fact(n) {
    return n < 2 ? 1 : n * f(n - 1);
}
function half(m, n) {
    total = 0;
    for (i = 1; i < m; i++)
        total += fact(m * n - 2) / fact(i * n - 1) / fact((m - i) * n - 1) * choc(i, n) * choc(m - i, n)
    return total;
}
function choc(m, n) {
    total = half(m, n) + half(n, m);
    if (!total) total = 1;
    return total;
}

```

---
Tags: code-golf, sequence, combinatorics
---


title: Compute overall ranking

text:
# Question
Title: Compute overall ranking
You are given a table that represents the rankings of *S* subjects according to a number *C* of different criteria. The purpose is to

* compute an **overall** ranking according to a weighted sum of the *C* ranking criteria,
* using one of those criteria (i.e. columns), *T*, as **tie-breaker**.

The rankings are a *S*×*C* table of positive integers. The weights for computing the overall ranking are given as an array of non-negative numbers.

Entry (*s*,*c*) of the table contains the ranking of subject *s* according to criterion *c*; that is the **position** of subject *s* when all *S* subjects are sorted according to criterion *c*. (Another possible interpretation, **not** used here, would be: row *s* tells which user is ranked *s*-th according to criterion *c*).

### Example

Consider the following table with *S*=6 and *C*=2:

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

```

Weights are

```
1.5 2.5

```

and column *T*=2 is used as tie-breaker.

The overall ranking for the first subject (first row) is `1*1.5+4*2.5 = 11.5`. The overall ranking array is

```
11.5
18.5
11.5
12
12.5
18

```

The resulting ranking, which is the output, is then

```
2
6
1
3
4
5

```

Note that the first-ranked row is the third, not the first, according to the tie-breaking specification.

## Input and output

Use any reasonable format for input and output. The rankings may be a 2D array of any orientation, an array of arrays, or separate arrays. Inputs may be taken in any fixed order.

Input and output rankings should be 1-based (as in the example above), because that's the natural way to speak of rankings.

Output may be a string of numbers with a fixed separator character or an array.

You can write a function or a program.

## Test cases

Table, weights, tie-breaking column, output.

```
--- (Example above) ---

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

1.5 2.5

2

2
6
1
3
4
5

--- (Three columns) ---

4     4     1
2     3     5
5     1     3
3     5     2
1     2     4

0.5   1.4   0.9

1

3
4
1
5
2

--- (Only one weight is nonzero) ---

1     5
3     3
4     2
5     1
2     4

1     0

2

1
3
4
5
2

--- (Only one column) ---

2
4
1
3

1.25

1

2
4
1
3

--- (Only one row) ---

1 1 1

0.8 1.5 2

3

1

```

# Answer
## Jelly, ~~11~~ 10 bytes

*-1 byte by @Dennis*

```
×⁵S€żị@€ỤỤ

```

Uses the fact that lists are lexicographically ordered.

This is a dyadic link that takes two arguments plus one input. The left argument is x, the rankings. The right argument is y, the tiebreaker. The input is the weights.

```
×⁵S€żị@€ỤỤ         Dyadic function. Inputs: x, y
×⁵                 Vectorized multiply x by the weights.

  S                Sum the rows.
                   This is the weighted ordering.
   ż               Zip with
    ị@€             x indexed at y, mapped over x
       ỤỤ          and compute the inverse of the permutation vector that sorts that.
                   A list is sorted by its inverse permutation, so
                   this is the inverse of the inverse; i.e. the original permutation.

```

Try it here.
> 2 votes

# Answer
# MATL, ~~21~~ 20 bytes

```
2#2$XSwiY*4#S)tn:tb(

```

Takes input as a matrix for the table of rankings, then the tie breaking column as a number, then a column vector of weightings for each column. Attempted explanation:

```
2#2$XS        % specifies 2 inputs/2 outputs for sortrows, takes 2 implicit inputs,
              % and sorts the matrix of ranks based on the second column. This means
              % ties are automatically broken in the correct way
wiY*          % swap the top 2 elements in the stack, take an input, and matrix multiply
              % the (sorted) ranking table by the weighting vector to give ranking array
4#S)         % sort the ranking array, taking only the permutation vector, and use it to
              % reorder the original sortrows permutation vector
tn:           % make a vector 1:(number of rows in ranking table)
tb(           % index 1:n vector using permutation vector to give final ranking
% implicit display

```

Try it Online!

(Written using MATL version 11.0.3 from a few weeks ago)

The equivalent Matlab code may be easier to understand:

```
[f,g]=sortrows(A,c); % 2#2$XS          (A=matrix of ranks, c=tie-break column)
[~,l]=sort(f*B);     % wiY*4#S        (B=weighting vector)
t=1:numel(g);        %
t(g(l))=t            % )tn:tb(

```
> 1 votes

# Answer
# JavaScript (ES6), 114 bytes

```
(a,w,t)=>a.map(s=>s.reduce((p,v,c)=>p+v*w[c],0)).map((n,i,b)=>b.map((v,j)=>r+=n>v|v==n&a[j][t-1]<a[i][t-1],r=1)|r)

```

## Explanation

Fairly straight-forward. Expects an array of rows as arrays, an array of weights as numbers, and the tie-breaker column as a number. Returns an array.

```
var solution =

(a,w,t)=>
  a.map(s=>                        // for each row s in the criteria table
    s.reduce((p,v,c)=>p+v*w[c],0)  // create an array of the summed weights for each row
  )
  .map((n,i,b)=>                   // for each number n at i in the summed weights array b
    b.map((v,j)=>                  // compare it to each other summed weight
      r+=n>v                       // increment it's rank if n > v
        |v==n&a[j][t-1]<a[i][t-1], // or in case of tie, check the weights in column t
      r=1                          // initialise the rank to 1
    )|r                            // return the rank
  )
```

```
<textarea id="table" rows="5" cols="40">4     4     1
2     3     5
5     1     3
3     5     2
1     2     4</textarea><br />
Weights = <input type="text" id="weights" value="0.5   1.4   0.9" /><br />
Tie-Breaker = <input type="number" id="tie" value="1" /><br />
<button onclick="result.textContent=solution(table.value.split('\n').map(x=>x.split(/\s+/).map(n=>+n)),weights.value.split(/\s+/).map(n=>+n),+tie.value)">Go</button>
<pre id="result"></pre>
```
> 1 votes

# Answer
# MATL, 16 bytes

```
Y*2GiY)v!4#XS4#S

```

Input is of the form: weights; table with each ranking on a different row; tie-breaker. Foe example,

```
[1.5 2.5]
[1 4 6 3 5 2; 4 5 1 3 2 6]
2

```

Try it online! First test case, second, third, fourth, fifth.

```
Y*         % implicitly input ranking table and weights. Matrix multiply, to produce
           % combined ranking as a row vector
2G         % push ranking table again
i          % input tie-breaker
Y)         % get that ranking from the table (as a row)
v!         % join combined ranking and tie-breaker column. Produce 2-col matrix
4#XS       % sort rows by first column (combined ranking) and then second
           % column (tie-breaker). Produce not the sorted matrix, but the indices
           % of the sorting, as a column vector
4#S        % sort that vector and get the indices of the sorting. Implicitly display

```
> 1 votes

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


title: Enumerate rhyme schemes

text:
# Question
Title: Enumerate rhyme schemes
A "rhyme scheme" is a string of letters `a` to `z`, such that the first occurrences of the characters are in ascending order (without gaps), starting from `a`. For example (with first occurrences marked):

```
abccdbebdcfa
^^^ ^ ^   ^

```

The number of rhyme schemes of length `N` is given by the *Bell numbers* `B(N)`. (OEIS A000110)

## The Challenge

Your task is to implement an enumeration of these rhyme schemes, i.e. a bijective mapping from integers to rhyme schemes. You're given a positive integer `N <= 26`, as well as a non-negative integer `0 <= i < B(N)`. Alternatively, you can use the range `1 <= i <= B(N)`. You should output a rhyme scheme of length `N`, such that every `i` yields a different string.

You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument and outputting the result via STDOUT (or closest alternative), function return value or function (out) parameter.

You may use either lower or upper case letters (consistently).

Your code must be able to handle any valid input in reasonable amount of time (e.g. **not more than a few hours** for `N = 26`, worst case `i`). This should allow solutions that scale exponentially with `N` (for small bases), even in slow languages but prohibit solutions that scale linearly with `i` (i.e. `B(N)`). In particular, that means you cannot just iterate through all valid rhyme schemes of length `N` until you've discard `i` schemes.

Standard rules apply.

## Examples

The exact assignment of the `i` to schemes (i.e. the order of the schemes for a given `N`) is up to you. But say you chose lexicographical ordering, your solution should correspond to the following table (with `-` denoting invalid input):

```
N\i 1    2    3    4    5    6    7    8    9    10   11   12   13   14   15
1   a    -    -    -    -    -    -    -    -    -    -    -    -    -    -
2   aa   ab   -    -    -    -    -    -    -    -    -    -    -    -    -
3   aaa  aab  aba  abb  abc  -    -    -    -    -    -    -    -    -    -
4   aaaa aaab aaba aabb aabc abaa abab abac abba abbb abbc abca abcb abcc abcd

```

Here is a short CJam script which generates all valid rhyme schemes for any given length (but don't try more than 10 or you'll wait a while).

### Related Challenges

# Answer
## CJam, ~~68~~ 66 bytes

```
r~:W)1a*{__(;\);_,,.*.+}W(*r~{X@\=_2$\/:CX<!{X:C):X;}&C*-C'a+o}W*;

```

Try it online.

This is my first CJam program. It started life as a port of my Perl solution and was initially over 130 bytes long. Further golfing suggestions are welcome.

As with my Perl program, it is in two parts.

```
Part 1:
r~:W                                         | Read the first input (n) and store it in W
    )1a*                                     | Create an array of n+1 1s
        {              }W(*                  | Repeat n-1 times:
         __                                  | Duplicate array twice
           (;\);                             | Remove first element of 1st array. Swap
                                             | arrays. Remove last element of 2nd array
                _,,                          | Duplicate array. Count items. Create range
                   .*.+                      | Multiply arrays. Add 1st array to result

Part 2:
r~                                           | Read the second input (i)
   {                                  }W*    | Repeat n times:
    X@                                       | Push y (initially 1). Bring item 2 (last array) to top
     \=                                      | Swap top two items. Pop array[y] (v)
       _2$                                   | Duplicate v. Copy item 2 (i) to top
          \/:CX                              | Swap i & v. i/v. Store in C (c). Push y
               <!{       }&                  | If !(i/v < c):
                  X:C):X;                    | c = y. ++y (store in X)
                           C*-C'a+o          | i -= c * v. Push y. Push "a". Add c. Print
                                         ;   | Discard top item (integer 0)

```

To debug the arrays created by Part 1 add `]_`o~` between Parts 1 & 2. If n is `5`, the arrays will look like this: `[[1 1 1 1 1 1] [1 2 3 4 5] [2 5 10 17] [5 15 37] [15 52]]`. The 0 indices of each array aren't used, they just make it easier by not having to calculate offsets. The arrays are calculated like this:

```
[2 5 10 17] [2 5 10 17] [2 5 10 17]        | Duplicate twice
[2 5 10 17] [2 5 10 17] [5 10 17]          | Discard first item of array
[2 5 10 17] [5 10 17] [2 5 10 17]          | Swap last two arrays
[2 5 10 17] [5 10 17] [2 5 10]             | Discard last item of array
[2 5 10 17] [5 10 17] [2 5 10] [2 5 10]    | Duplicate array
[2 5 10 17] [5 10 17] [2 5 10] 3           | Count items in array
[2 5 10 17] [5 10 17] [2 5 10] [0 1 2]     | Integer to range 0 - n-1
[2 5 10 17] [5 10 17] [0 5 20]             | Multiply arrays [2*0 5*1 10*2]
[2 5 10 17] [5 15 37]                      | Add arrays [5+0 10+5 17+20]

```

It keeps a copy of the old array while calculating the next one. The arrays are read and discarded in reverse order by Part 2.
> 3 votes

# Answer
# Python 2, 153

```
u=[1]*999;i=60;exec"u[i]=i%30*u[i-30]+u[i-29];i+=1;"*900
def x(l,n,a=0):m=u[30*l+a];c=n>=a*m;return'.'*l and chr(65+min(n/m,a))+x(l-1,[n%m,n-m*a][c],a+c)

```

It uses alphabetical order and 0-based indexing.

Let `l` denote the length of a suffix of the letters and `a` denote the number of distinct letters that were used in the preceding part. Then a function `p(l,a)` that calculates the number of ways to select the remaining letters could be 40 bytes:

```
p=lambda l,a:l<1or a*p(l-1,a)+p(l-1,a+1)

```

However, this is too slow for the challenge, so instead the necessary values are precalculated and stored in the `u` array. At each stage of the calculation, if the next letter is the one of the `a` already used, the *n = k * p(l - 1, a) + n'* where *k* is the 0-indexed letter of the alphabet and *n'* is the value of `n` for the next function call, which contains the information about the remaining letters. If a new letter is used, then *n = a * p(l - 1, a) + n'*.
> 13 votes

# Answer
# Haskell (GHC 7.10), 150 bytes

```
s=(1,\_->[]):s
k!((y,b):l@((x,a):_))|let h i|i<x=k:a i|(p,q)<-divMod(i-x)y=p:b q=(x+k*y,h):(k+1)!l
n#i=(['a'..]!!).fromEnum<$>snd(iterate(0!)s!!n!!0)i

```

The operator `n # i` computes the `i`th (zero-indexed) rhyme scheme of length `n`. It runs in O(n²) (big-integer) operations, taking advantage of Haskell’s lazy infinite lists for automatic memoization. Sample runs:

```
*Main> 26 # 0
"abcdefghijklmnopqrstuvwxyz"
*Main> 26 # 1
"abcdefghijklmnopqrstuvwxya"
*Main> 26 # 2
"abcdefghijklmnopqrstuvwxyb"
*Main> 26 # 49631246523618756271
"aaaaaaaaaaaaaaaaaaaaaaaabb"
*Main> 26 # 49631246523618756272
"aaaaaaaaaaaaaaaaaaaaaaaaab"
*Main> 26 # 49631246523618756273
"aaaaaaaaaaaaaaaaaaaaaaaaaa"
*Main> [1 # i | i <- [0..0]]
["a"]
*Main> [2 # i | i <- [0..1]]
["ab","aa"]
*Main> [3 # i | i <- [0..4]]
["abc","aba","abb","aab","aaa"]
*Main> [4 # i | i <- [0..14]]
["abcd","abca","abcb","abcc","abac","abaa","abab","abbc","abba","abbb","aabc","aaba","aabb","aaab","aaaa"]

```

(If the maximum N were 25 instead of 26, the `.fromEnum` could be removed, because B(25) fits in a 64-bit `Int`.)
> 11 votes

# Answer
## ~~Perl 257 + 1 (-p flag) = 258~~

## Perl 182 + 10 (-pMbignum flags) = 192

```
($n,$i)=split;@m=[@a=(1)x($n+1)];while($a[2]){push@m,[@a=map{$a[$_]*$_+$a[$_+1]}0..$#a-1]}$_='';$y=1;while($w=pop@m){$c=int($i/($v=$$w[$y]));$c=$y++if($c>=$y);$i-=$c*$v;$_.=chr$c+65}

```

Thanks to dev-nul for saving many bytes! I've now rewritten it based on what I learnt from doing the CJam version.

Calculates the rhyme in ascending alphabetical order, 0 indexed.

Two parts: Part 1 is ~~128~~ 90 bytes and calculates a matrix for Part 2. Part 2 is ~~129~~ 92 bytes and does some simple maths to calculate each letter. ~~If I could get rid of the matrix and replace it with two simple numbers, I could calculate a single path through the matrix for each number and save a lot of bytes!~~ Apparently, that idea doesn't work!

~~Unfortunately, it doesn't output the right rhymes for values of `i` higher than 9007199254740992, but it works beautifully for low values!~~ ~~I've added the Bignum library at a cost of 11 bytes.~~ It's run from the command line with `perl -pMbignum bell-rhyme.pl`. `-pMbignum` = 10 bytes. It's also very fast for any input value.
> 4 votes

# Answer
# Oracle SQL 11.2, ~~412~~ ~~284~~ 283 bytes

```
WITH a AS(SELECT CHR(96+LEVEL)d,LEVEL b FROM DUAL CONNECT BY LEVEL<=:i),v(s,c,n)AS(SELECT d,1,1 FROM a WHERE b=1 UNION ALL SELECT s||d,b,LENGTH(REGEXP_REPLACE(s||d,'([a-z])\1+','\1'))FROM v,a WHERE(b<=n OR b=c+1)AND LENGTH(s)<:n)SELECT s FROM v WHERE:n=LENGTH(s)AND:i<=:n ORDER BY 1;

```

Unfortunately it only runs up to a length of 8. Any greater value results in : ORA-01489: result of string concatenation is too long

Un-golfed

```
WITH a AS(SELECT CHR(96+LEVEL)d,LEVEL b FROM DUAL CONNECT BY LEVEL<=:i),
v(s,c,n) AS
(
  SELECT d,1,1 FROM a WHERE b=1
  UNION ALL
  SELECT s||d,b,LENGTH(REGEXP_REPLACE(s||d,'([a-z])\1+','\1'))
  FROM v,a
  WHERE (b<=n OR b=c+1) AND LENGTH(s)<:n
)
SELECT s FROM v WHERE LENGTH(s)=:n AND :i<=:n ORDER BY 1;

```

The a view generate the :i letters in column a and their value in b.

The recursive view v takes the string being constructed as parameter v, the value of the last letter used in c and the value of the greatest letter used in n. The n parameter is equal to the length of the string without any duplicate letter, thats what the regex is for.

A letter is valid if its value is \<= the value of the greatest letter already used or it is the next letter to be used.

Somehow the query needs the LENGTH(s)\<:n part to run, I must be missing something in how the query works.

The main SELECT takes care of filtering out the invalid inputs and the shorter strings built before the length targeted is reached.

412 bytes version

```
WITH a AS(SELECT * FROM(SELECT d,b,ROW_NUMBER()OVER(PARTITION BY b ORDER BY d)l FROM(SELECT CHR(64+DECODE(MOD(LEVEL,:i),0,:i,MOD(LEVEL,:i)))d,CEIL(LEVEL/:i)b FROM DUAL CONNECT BY LEVEL<=:i*:n))WHERE l<=b),v(s,c,p)AS(SELECT d,1,l FROM a WHERE b=1 UNION ALL SELECT s||d,c+1,l FROM v,a WHERE c+1=b AND(l<=LENGTH(REGEXP_REPLACE(s,'([A-Z])\1+','\1'))OR l=p+1))SELECT s FROM v WHERE LENGTH(s)=:n AND :i<=:n ORDER BY 1;

```

Do not try the 412 bytes query with 26. It puts the database in restricted mode, at least on my xe version running in a docker container on a macbook. I could try on the exadata at work, but sadly I still need to work for a living.
> 2 votes

# Answer
## Mathematica, 136 bytes

```
(For[j=2^#-1;t=#2,c=1;m=0;x=t;r=If[#>0,++m,c*=m;d=x~Mod~m+1;x=⌊x/m⌋;d]&/@j~IntegerDigits~2;;c<=t,t-=c;--j];FromCharacterCode[r+64])&

```

For completeness, here is my golfed reference implementation. As opposed to the existing answers this does not run in polynomial time (it's exponential in `N` with base 2) but does meet the time constraint (the worst case would still run in under half an hour).

The idea is this:

* For each rhyme scheme we can identify the positions where the maximum character so far increases:

```
ABCDEFGHDIJDEKBBIJEIKHDFII
^^^^^^^^ ^^  ^

```

We can treat those markings as a binary number which makes it easy to iterate over all such structures. We need to iterate from 2n-1 to 2n (or the other way round) which is where the exponential time complexity comes from.
* For each such structure it's easy to determine how many such strings there are: only the gaps between the markings can be freely chosen, and the maximum in front of the gap tells us how many different characters are valid in each position. This is a simple product. If this number is smaller than `i`, we subtract it from `i`. Otherwise, we've found the structure of the requested rhyme scheme.
* To enumerate the schemes in the given structure, we simply represent `i` (or what remains of it) as a mixed-base number, where the weights of the digits are determined by the number of allowed characters in the remaining positions.

I wonder if this would allow for a shorter solution in some of the other languages that were submitted since it doesn't require any memoisation or precomputation.
> 0 votes

---
Tags: code-golf, combinatorics, set-partitions
---