title: Stretching Words

text:
# Question
Title: Stretching Words
Write a program or function that duplicates letters in a word, so that all the duplicated letters arranged from left to right in the word would form the input array.

For example:

```
input: chameleon, [c,a,l,n]
output: cchaamelleonn

```

## Input

* The starting word (e.g. `chameleon`)
* An array of characters (`[c,a,l,n]`) or a string to represent an array (`caln`), or something similar
* Input can be through function parameters, STDIN or language equivalents
* All inputs will be lower-case letters (a-z)

## Output

* The changed word
* If there are multiple solutions, any can be printed

```
input: banana [n,a]
possible outputs: bannaana, banannaa
                     |-|---------|-|--->[n,a]

```
* You may assume that the input word (not necessarily the array) will have the letters in the array (in order)
* You may also assume that the inputs have no consecutive letters which are the same (NOT apple, geek, green, glass, door...)

## Examples

```
input: abcdefghij, [a,b,c]
output: aabbccdefghij

input: lizard, [i,a,r,d]
output: liizaarrdd

input: coconut, [c,o]
ouput: ccooconut or coccoonut or ccocoonut

input: onomatopoeia, [o,o,a,o,o]
output: oonoomaatoopooeia

input: onomatopoeia, [o,a,o]
output: oonomaatoopoeia or onoomaatoopoeia or oonomaatopooeia etc.

```

Shortest program wins!

Leaderboard (thanks to Martin Büttner for the snippet)

```
/* Configuration */

var QUESTION_ID = 51984; // 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";

/* App */

var answers = [], page = 1;

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 getAnswers() {
  jQuery.ajax({
    url: answersUrl(page++),
    method: "get",
    dataType: "jsonp",
    crossDomain: true,
    success: function (data) {
      answers.push.apply(answers, data.items);
      if (data.has_more) getAnswers();
      else process();
    }
  });
}

getAnswers();

var SIZE_REG = /\d+(?=[^\d&]*(?:<(?:s>[^&]*<\/s>|[^&]+>)[^\d&]*)*$)/;
var NUMBER_REG = /\d+/;
var LANGUAGE_REG = /^#*\s*([^,]+)/;

function shouldHaveHeading(a) {
  var pass = false;
  var lines = a.body_markdown.split("\n");
  try {
    pass |= /^#/.test(a.body_markdown);
    pass |= ["-", "="]
              .indexOf(lines[1][0]) > -1;
    pass &= LANGUAGE_REG.test(a.body_markdown);
  } catch (ex) {}
  return pass;
}

function shouldHaveScore(a) {
  var pass = false;
  try {
    pass |= SIZE_REG.test(a.body_markdown.split("\n")[0]);
  } catch (ex) {}
  return pass;
}

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

function process() {
  answers = answers.filter(shouldHaveScore)
                   .filter(shouldHaveHeading);
  answers.sort(function (a, b) {
    var aB = +(a.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0],
        bB = +(b.body_markdown.split("\n")[0].match(SIZE_REG) || [Infinity])[0];
    return aB - bB
  });

  var languages = {};
  var place = 1;
  var lastSize = null;
  var lastPlace = 1;
  answers.forEach(function (a) {
    var headline = a.body_markdown.split("\n")[0];
    //console.log(a);
    var answer = jQuery("#answer-template").html();
    var num = headline.match(NUMBER_REG)[0];
    var size = (headline.match(SIZE_REG)||[0])[0];
    var language = headline.match(LANGUAGE_REG)[1];
    var user = getAuthorName(a);
    if (size != lastSize)
      lastPlace = place;
    lastSize = size;
    ++place;
    answer = answer.replace("{{PLACE}}", lastPlace + ".")
                   .replace("{{NAME}}", user)
                   .replace("{{LANGUAGE}}", language)
                   .replace("{{SIZE}}", size)
                   .replace("{{LINK}}", a.share_link);
    answer = jQuery(answer)
    jQuery("#answers").append(answer);

    languages[language] = languages[language] || {lang: language, user: user, size: size, link: a.share_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: 50%;
  float: left;
}

#language-list {
  padding: 10px;
  width: 50%px;
  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>
```

# Answer
> 5 votes
# Pyth, 14 bytes

```
s+L&@d<Q1.(QZz

```

Demonstration.

Input style:

```
banana
["b","a","n","a"]

```

Explanation:

```
s+L&@d<Q1.(Q0z
                  Implicit: z = input(); Q = eval(input())
 +L          z    Map (lambda d) over z, adding the result to each character.
    @d<Q1         Intersection of d with Q[:1], up to the first element of Q.
   &              Logical and - if the first arg is truthy, evaluate and
                  return the second arg, otherwise return first arg.
         .(Q0     Q.pop(0)
                  The addition will either be the empty string, for the empty
                  intersection, or the character that was Q[0] otherwise.

s                 Concatenate and print.

```

# Answer
> 44 votes
# Brainfuck, ~~46~~ 45 (63 with printable characters in input)

Compatible with Alex Pankratov's bff (brainfuck interpreter used on SPOJ and ideone) and Thomas Cort's BFI (used on Anarchy Golf).

The printable version takes the array first as a string, followed by a tab, followed by the starting string with no trailing newline.

Demonstration on ideone.

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

```

We can save some bytes by using `\x00` as a separator instead of tab:

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

```

# Answer
> 14 votes
# CJam, 15 bytes

```
rr{_C#)/(C@s}fC

```

Try it online.

### How it works

```
rr              e# Read two whitespace-separated tokens from STDIN.
  {         }fC e# For each character C in the second string.
   _            e#   Duplicate the first string.
    C#          e#   Compute the index of the character in the string.
      )/        e#   Add 1 and split the string in slice of that size.
        (       e#   Shift out the first slice.
         C      e#   Push the character.
          @     e#   Rotate the remainder of the string in top of the stack.
           s    e#   Stringify (concatenate the slices).

```

# Answer
> 12 votes
# C, 62 bytes

```
f(char*s,char*c){while(*s-*c||putchar(*c++),*s)putchar(*s++);}

```

Well, this is surprisingly competetive.

We define a function `f(char*, char*)` that takes the string as its first input and the array of characters to duplicate as its second input.

Some testing code:

```
int main (int argc, char** argv) {
    f("onomatopeia", "oao");
    return 0;
}

```

Which prints:

```
oonomaatoopeia

```

Try it online!

If it is acceptable to submit a macro rather than a function, the following `#define g(s,c)` is just **58 bytes**, but requires `s` and `c` to be actual pointers:

```
#define g(s,c)while(*s-*c||putchar(*c++),*s)putchar(*s++);

```

# Answer
> 11 votes
# CJam, 15 bytes

```
rr{:X/(XX+@X*}/

```

An alternative CJam approach. Try it online

## Explanation

For each character in the second string, we do two things.

1. Split the current suffix of the string by the character, e.g. `"beeper" "e" -> ["b" "" "p" "r"]`
2. Uncons the first string in the array, insert two of the character, then rejoin the rest of the array with the character, e.g. `"b" "ee" "eper"`. The last string is the new suffix.

# Answer
> 9 votes
# Retina, 33 bytes

More information about Retina.

```
+`(?=(.))(((.)(?<!\4.))+\n)\1
$1$2

```

This expects the two strings on STDIN, separated by a newline.

For counting purposes, each line goes into a separate file, `\n` should be replaced with an actual newline character (0x0A). If you actually want to test this, it's more convenient to put this in a single file where `\n` remains as it is and then invoke Retina with the `-s` option before passing the file.

## Explanation

*(Outdated... I managed to get rid of the marker... I'll update this later.)*

Each pair of lines is a regex substitution (first line the pattern, second line the substitution).

```
^
#

```

This puts a `#` as a marker at the start of the input string.

```
+`#(.*?(.))(.*\n)\2
$1$2#$3

```

This finds the first letter in the input (after the marker) corresponding to the next letter to be duplicated, duplicates that letter, moves the marker behind it, and drops the first character of the second string. The `+`` at the front tells Retina to do this repeatedly until the string stops changing (in this case, because the second string is empty and all required letters have been duplicated).

```
#
<empty>

```

Finally, we clean up the string by dropping the marker.

# Answer
> 9 votes
## Python, 61

```
def f(s,l):b=s[:1]==l[:1];return s and-~b*s[0]+f(s[1:],l[b:])

```

A greedy recursive solution. Saves to `b` whether the first letter of the string `s` is the first letter of the string `l` of letters to double. If so, take one of that letter and prepend it to the recursive call with the rest of `s`, removing the first element from `l`. If not `b`, do the same but don't double the letter and don't remove from `l`.

The code checks `s[:1]==l[:1]` rather than `s[0]==l[0]` to avoid an index-out-of-bounds error when `s` or `l` is empty.

# Answer
> 7 votes
# Prolog, ~~95~~ ~~83~~ ~~79~~ 56 bytes

```
d([A|S],H):-put(A),H=[A|T],put(A),d(S,T);d(S,H).
d(_,_).

```

Example:

```
d(`chameleon`,`caln`).

```

returns

```
cchaamelleonn

```

Edit: Saved 4 bytes thanks to Oliphaunt

Edit2: Saved 20 bytes using the deprecated `put/1` SWI-Prolog predicate instead of `writef`. Saved one byte replacing the recursion end predicate `d([],_).` to `d(_,_).`. Won't work if the ordering of the two definitions of `d` is swapped though, but we don't care about that in golfed code. Saved another 2 bytes removing the parenthesis around `H=[A|T],put(A),d(S,T)`

# Answer
> 6 votes
# Python 2, ~~83~~ ~~74~~ ~~72~~ 65 Bytes

No real special tricks here. `x` is the string, `y` is the array of characters that are duplicated. ~~To clarify if this doesn't copy properly, the first indentation level is a space, the next is a tab.~~

*Edit 1: Saved 9 bytes by using string manipulation instead of pop().*

*Edit 2: Saved 2 bytes by using `-~` to increment `g` by 1.*

*Edit 3: Saved 7 bytes by using `y[:1]` trick, thanks to xnor for this!*

```
def f(x,y,s=''):
 for c in x:g=y[:1]==c;s+=c*-~g;y=y[g:]
 print s

```

Check it out here.

Properly formatted and explained:

```
def f(x,y,s=''):           # Defining a function that takes our input,
                           # plus holds a variable we'll append to.
  for c in x:              # For every character in 'x', do the following:
    g = y[:1] == c         # Get the first element from the second string, will
                           # return an empty string if there's nothing left.
                           # Thanks to xnor for this trick!
    s += c * -~g           # Since int(g) would either evaluate to 0 or 1, we
                           # use the -~ method of incrementing g to multiply
                           # the character by 1 or 2 and append it to 's'
    y = y[g:]              # Again, since int(g) would either evaluate to 0
                           # or 1, use that to cut the first value off y, or
                           # keep it if the characters didn't match.
  print s                  # Print the string 's' we've been appending to.

```

# Answer
> 5 votes
### Excel VBA, 110 bytes

This is my first entry to CodeGolf so I hope this is ok.

You enter the input word in A1 and then the letters to be replaced in B1 and the resulting word is displayed in a message box.

```
w = Cells(1, 1)
l = Cells(2, 1)
For i = 1 To Len(w)
x = Left(w, 1)
R = R + x
If InStr(l, x) > 0 Then
R = R + x
End If
w = Right(w, Len(w) - 1)
Next
MsgBox R

```

# Answer
> 4 votes
# Javascript, 47 bytes

```
(a,b)=>a.replace(/./g,d=>b[0]!=d?d:d+b.shift())

```

Taking advantage of some ES6 features.

# Answer
> 4 votes
# Pyth, ~~18~~ 17 bytes

```
sm?+d.(QZqd&QhQdz

```

Live demo.

Saved 1 byte thanks to @Jakube.

## Explanation:

```
                z  Read the first line of input.
 m                 For each character in that line
  ?      qd&QhQ    If (?) the first char of the stretch list (`&QhQ`)
                   and the current character are equal,
   +d.(QZ          Then double the current character and pop an element off
                   the stretch list.
               d   Otherwise, just return the same character.
s                  Join all the characters together.

```

## Original version:

```
jkm?+d.(QZqd&QhQdz

```

Live demo for original.

# Answer
> 4 votes
# Haskell, 42 bytes

```
(a:b)#e@(c:d)|a==c=a:a:b#d|1<2=a:b#e
a#_=a

```

Usage example:

```
*Main> "coconut" # "co"
"ccooconut"
*Main> "lizard" # "iard"
"liizaarrdd"
*Main> "onomatopoeia" # "ooaoo"
"oonoomaatoopooeia"

```

How it works:

If one string is empty, the result is the first string. Else: if the first characters of the strings match, take it two times and append a recursive call with the tails of the strings. If the characters don't match, take the first character of the first string and append a recursive call with the tail of the first string and the same second string.

# Answer
> 3 votes
# Pyth, 16 bytes

```
u|pH<GJxGH>GJwz

```

Try it online: Demonstration

This is quite hacky. Stack-based languages might have an advantage here.

### Explanation

```
                   implicit: z = 1st input line, w = 2nd
u             wz   reduce, start with G = z
                   for each H in w, update G to:
        xGH          index of H in G
       h             +1
      J              store in J
    <GJ              substring: G[:J] (everything before index J)
  pH                 print substring then H (without newlines)
 |                   afterwards (actually or, but p always returns 0)
           >GJ       substring: G[J:] (everything from index J to end)
                     update G with ^
                   afterwards implicitly print the remainder G

```

# Answer
> 3 votes
# JavaScript ES6, 47 bytes

```
(w,s)=>w.replace(/./g,c=>c==s[0]?c+s.shift():c)

```

Assumes `s` is an array `["c","a","l","n"]`

# Answer
> 3 votes
## \>\<\> (Fish), 68 34 Bytes

```
ri&:o&:&=\
l&io& /!?/
?!;20.\l!\

```

You can run it at http://fishlanguage.com/playground inputting the string as the initial stack (with " marks, i.e. "chameleon") and the array of extra letters as the input stack (no " marks i.e. caln).

Don't forget to press the Give button to seed the input stack.

```
r       reverses the stack
i&      reads in the first input, and stores it in the register
:o      copies the top of the stack, and outputs the top of the stack
&:&     puts register value on stack, copies it, then puts top stack into register
=       checks if the top two values are equal, if yes push 1, else push 0
?       if top value is non-zero, execute next instruction
!       skips the following instruction (unless it was skipped by the previous ?)

If yes, then we proceed on the same line
&o      puts register value on stack, and outputs it
i&      reads in the first input, and stores it in the register
l       puts length of stack on stack, then proceed to lowest line

If no, we go directly to the last line
l       As above.
?!;     If zero value (from length), then end execution
20.     Push 2 and 0 onto stack, then pop top two values, and go to that position (2,0) (i.e. next instruction is at (3,0))

```

EDIT: Halved it! :)

# Answer
> 3 votes
# REGXY, 24 bytes

Uses REGXY, a regex substitution based language. Input is assumed to be the starting word and the array, space separated (e.g. "chameleon caln").

```
/(.)(.* )\1| /\1\1\2/
//

```

The program works by matching a character in the first string with the first character after a space. If this matches, the character is repeated in the substitution and the character in the array is removed (well, not appended back into the string). Processing moves on to the second line, which is just a pointer back to the first line, which causes processing to repeat on the result of the previous substitution. Eventually, there will be no characters after the space, at which point the second branch of the alternation will match, removing the trailing space from the result. The regex will then fail to match, processing is completed and the result is returned.

If it helps, the iterative steps of execution are as follows:

```
chameleon caln
cchameleon aln
cchaameleon ln
cchaameleonn n
cchaameleonn  (with trailing space)
cchaameleonn

```

The program compiles and executes correctly with the sample interpreter in the link above, but the solution is perhaps a bit cheeky as it relies on an assumption in the vagueness of the language specification. The spec states that the first token on each line (before the /) acts as a label, but the assumption is that a null label-pointer will point back to the first command in the file with a null label (or in other words, that 'null' is a valid label). A less cheeky solution would be:

```
a/(.)(.* )\1| /\1\1\2/
b//a

```

Which amounts to 27 bytes

# Answer
> 3 votes
# Japt `-m`, ~~10~~ 7 bytes

```
iVvUèVÎ

```

Try it

```
iVvUèVÎ     :Implicit map of each character U in the first input (the string)
i           :Prepend
 V          :  The second input (the array)
  v         :  Remove this many elements from the start ...
   Uè       :    Count the occurrences in U of
     VÎ     :    The first element of V

```

# Answer
> 2 votes
## Ruby, ~~52~~ 47 bytes

**Solution:**

`f=->(s,a){s.chars.map{|c|c==a[0]?a.shift*2:c}.join}`

**Example:**

`p f.call('banana', ['n','a']) # => "bannaana"`

**Explanation:**

Proc form of a method which takes a string as the first argument, and an array of characters as the second argument. Maps a block onto an array of the characters in the string argument, which checks each character against first element of the comparison array, and if there is a match, removes the first element of the comparison array, and doubles it.

---

*update*

`f=->s,a{s.chars.map{|c|c==a[0]?a.shift*2:c}*''}`

# Answer
> 2 votes
# R, 119

Based on @Alex's answer, this one is a couple of bytes shorter:

```
function(s,a){message(unlist(lapply(strsplit(s,"")[[1]],function(x){if(length(a)&x==a[1]){a<<-a[-1];c(x,x)}else x})))}

```

Ungolfed:

```
function(s, a) {
  message(                             # Prints to output
    unlist(                            # Flattens list to vector
      lapply(                          # R's version of map
        strsplit(s,"")[[1]],           # Split vector to characters
        function (x) {
          if (length(a) & x == a[1]) { # If there are still elements in a
                                       # and there's a match
            a <<- a[-1]                # Modify a
            c(x, x)                    # And return the repeated character
          } else x                     # Otherwise just return it
        }
      )
    )
  )
}

```

# Answer
> 2 votes
# Perl, ~~73~~ ~~62~~ ~~59~~ 56

Entirely new approach yields much better results. Still, I bet it can be shorter.

Call as `f('coconut', ['c','o'])`.

```
sub f{($s,$a)=@_;$s=~s/(.*?)($_)/\U$1$2$2/ for@$a;lc$s}

```

For each character in the array, find the first occurrence and duplicate it, and turn everything up to it to uppercase. Then return the entire string, converted to lowercase.

EDIT: shaved a couple of more characters by getting rid of `shift` and `pop`.

---

The previous version:

```
sub f{join '',map{shift @{$_[0]}if s/($_[0][0])/$1$1/;$_}split //,shift}

```

# Answer
> 1 votes
# rs, 39 bytes

More information about rs.

There's already a Retina answer, but I think this one uses a slightly different approach. They were also created separately: when I began working on this one, that answer hadn't been posted.

Besides, this one is 6 bytes longer anyway. :)

```
#
+#(\S)(\S*) ((\1)|(\S))/\1\4#\2 \5
#/

```

Live demo and test suite.

# Answer
> 1 votes
# Python 2, 77

```
def f(x,y,b=''):
 for i in x:
    try:
     if i==y[0]:i=y.pop(0)*2
    except:0
    b+=i
 print b

```

Call as:

```
f('onomatopoeia',['o','a','o'])

```

I may have got the byte count horribly wrong... Uses a mixture of spaces and tabs.

# Answer
> 1 votes
# JavaScript ES6, 72 bytes

```
(s,a,i=0,b=[...s])=>a.map(l=>b.splice(i=b.indexOf(l,i+2),0,l))&&b.join``

```

This is an anonymous function that takes 2 parameters: the starting word as a string and the characters to stretch as an array. Ungolfed code that uses ES5 and test UI below.

```
f=function(s,a){
  i=0
  b=s.split('')
  a.map(function(l){
    i=b.indexOf(l,i+2)
    b.splice(i,0,l)
  })
  return b.join('')
}

run=function(){document.getElementById('output').innerHTML=f(document.getElementById('s').value,document.getElementById('a').value.split(''))};document.getElementById('run').onclick=run;run()
```

```
<label>Starting word: <input type="text" id="s" value="onomatopoeia" /></label><br />
<label>Leters to duplicate: <input type="text" id="a" value="oao"/></label><br />
<button id="run">Run</button><br />Output: <output id="output"></output>
```

# Answer
> 1 votes
# R, ~~136~~ ~~128~~ 122 bytes

```
function(s,a){p=strsplit(s,"")[[1]];for(i in 1:nchar(s))if(length(a)&&(x=p[i])==a[1]){p[i]=paste0(x,x);a=a[-1]};message(p)}

```

This creates an unnamed function that accepts a string and a character vector as input and prints a string to STDOUT. To call it, give it a name.

Ungolfed + explanation:

```
f <- function(s, a) {
    # Split s into letters
    p <- strsplit(s, "")[[1]]

    # Loop over the letters of s
    for (i in 1:nchar(s)) {

        # If a isn't empty and the current letter is the first in a
        if (length(a) > 0 && p[i] == a[1]) {

            # Replace the letter with itself duplicated
            p[i] <- paste0(p[i], p[i])

            # Remove the first element from a
            a <- a[-1]
        }
    }

    # Combine p back into a string and print it
    message(p)
}

```

Examples:

```
> f("coconut", c("c","o"))
ccooconut

> f("onomatopoeia", c("o","a","o"))
oonomaatoopoeia

```

Saved 8 bytes thanks to MickeyT and another 3 thanks to jja!

# Answer
> 1 votes
# Bash+sed, 51

```
sed "`sed 's/./s!^[^&]*&!\U\&&!;/g'<<<$1`s/.*/\L&/"

```

Input from stdin; characters to be doubled as a single argument:

```
$ echo chameleon | strtech caln
cchaamelleonn

```

This works by constructing a sed program from `$2` and then executing it against `$1`. The sed program replaces the first occurrence of each replacement letter with two copies of its uppercase version, and downcases the whole lot at the end. For the example above, the generated sed program is

```
s!^[^c]*c!\U&C!;s!^[^a]*a!\U&A!;s!^[^l]*l!\U&L!;s!^[^n]*n!\U&N!;s/.*/\L&/

```

pretty-printed:

```
# if only sed had non-greedy matching...
s!^[^c]*c!\U&C!
s!^[^a]*a!\U&A!
s!^[^l]*l!\U&L!
s!^[^n]*n!\U&N!
s/.*/\L&/

```

I use the uppercase to mark characters processed so far; this avoids re-doubling characters that have already been doubled, or applying a doubling earlier than the previous one.

Earlier version, before clarification that order of replacement list is significant (44 chars):

```
sed "`sed 's/./s!&!\U&&!;/g'<<<$1`s/.*/\L&/"

```

# Answer
> 1 votes
# JavaScript, 92 characters

```
function f(s,c){r="";for(i=0;i<s.length;i++){r+=s[i];if(c.indexOf(s[i])>-1)r+=s[i]}return r}

```

Unobfuscated version:

```
function stretch(str, chars) {
    var ret = "";
    for(var i = 0; i < str.length; i++) {
        ret += str[i];
        if(chars.indexOf(str[i]) > -1) {
            ret += str[i];
        }
    }
    return ret;
}

```

# Answer
> 1 votes
## Perl, 51 bytes

```
$s=<>;$s=~s=^.*$_=$_=,$,.=$&for split"",<>;print$,;

```

Input is provided via STDIN. First input is the starting word (e.g. `chameleon`), second input is the letters as a single string (e.g. `caln`).

The above is just an obfuscated (read "prettier") way of doing the following:

```
$word = <>;
for $letter(split "", <>) {
   $word =~ s/^.*$letter/$letter/;
   $result .= $&;
}
print $result;

```

As we go through each letter, we replace from the start of the word up to the letter in the source word with just the new letter, and append the match (stored in `$&`) to our result. Since the match includes the letter and then gets replaced with the letter, each letter ends up appearing twice.

Because STDIN appends a new line character to both of our inputs, we're guaranteed to capture the remnants of the full word on the last match, i.e. the new line character.

# Answer
> 1 votes
# Perl 5 \+ `-0p`, 26 bytes

```
1while s;(.)(.+
)\1;$1$1$2
```

Try it online!

# Answer
> 1 votes
# K (ngn/k), ~~41~~ 21 bytes

-20 bytes by adapting my answer here

```
{x@&y{y_x,1+y~:*x}/x}

```

Try it online!

* `y{...}/x` set up a reduction seeded with `y` (the characters to repeat), run over the characters in `x` (the full string). confusingly, within the function itself, `x` and `y` are flipped. this ends up returning a boolean array with `2`s in the positions containing the desired matches and `1`s everywhere else
    + `1+y~:*x` compare the first character to search for (`*x`) to the current character being iterated over (`y`), updating `y` with the result of `0` or `1`. then add one to this; this represents the number of copies of the current character to end up returning. note that as soon as we have matched all the search characters, no more matches will be identified (since a character will never `~` (match) a `1` or `2`)
    + `x,` append this result to the list of characters to search for (essentially overloading the reduction to end up returning the desired output)
    + `y_` if there was a match, drop the first character (if there wasn't a match, this is a no-op). this allows us to search for the next search character in the next iteration of the reduction
* `x@&` return the correct number of copies of each character

# Answer
> 1 votes
# Vyxal `s`, 9 bytes

```
£ƛ¥h=[&Ḣd

```

Try it Online!

```
£ƛ¥h=[&Ḣd
£         # Put the first input in the register
 ƛ        # Map over the second input:
  ¥h=[    #  Is the current character equal to the first character of the register?
      &Ḣd #  If so, remove the first character of the register and double the current character
          #  (implicit) else, return the current character unchanged
          # s flag smashes this list into a string

```

# Answer
> 0 votes
# Python, ~~53~~ 92 bytes

Found my solution to be the same length in both Python 2 and 3.

EDIT: Man, fixing that case when doing multiple replaces of the same letter (while still using the same method) took a bit of work.

### Python 2:

**Try it here**

```
def f(s,t):
 for c in t:s=s.replace(c,'%',1)
 print s.replace('%','%s')%tuple(x*2for x in t)

```

### Python 3:

```
s,*t=input()
for c in t:s=s.replace(c,'%',1)
print(s.replace('%','%s')%tuple(x*2for x in t))

```

# Answer
> 0 votes
# Lua, ~~76~~ ~~78~~ ~~76~~ ~~75~~ ~~58~~ 53 bytes

New, completely reworked solution with help from wieselkatze and SquidDev! come on guys, we can beat brainfuck :P

```
function f(a,b)print((a:gsub("["..b.."]","%1%1")))end

```

Explanation coming tommorow. Try it here.

---

Original solution: Saved 2 bytes thanks to @kirbyfan64sos!

Lua is a pretty terrible language to golf in, so I think I did pretty good for this one.

```
function f(x,y)for i=1,#x do g=y:sub(i,i)x=x:gsub(g,g..g,1)end print(x)end

```

Code explanation, along with ungolfed version:

```
function f(x,y) --Define a function that takes the arguements x and y (x is the string to stretch, y is how to stretch it)
  for i=1,#x do --A basic for loop going up to the length of x
    g=y:sub(i,i) -- Define g as y's "i"th letter
    x=x:gsub(g,g..g,1) --Redefine x as x with all letter "g"s having an appended g after them, with a replace limit of 1.
  end
  print(x)
end

```

Try it here. (Outdated code but same concept, just less golfed, will update tommorow)

# Answer
> 0 votes
# Mathematica, 66 bytes

```
""<>Fold[Most@#~Join~StringSplit[Last@#,#2->#2<>#2,2]&,{"",#},#2]&

```

Example:

```
In[1]:= f = ""<>Fold[Most@#~Join~StringSplit[Last@#,#2->#2<>#2,2]&,{"",#},#2]&

In[2]:= f["banana", {"n", "a"}]

Out[2]= "bannaana"

```

# Answer
> 0 votes
# Ruby, 46 bytes

```
f=->s,a{a.map{|c|y,s=s.split(c,2);y+c*2}*''+s}

```

For each character `c` in the array `a`, divide the string `s` in two halves on the first occurrence of `c`. Add two copies of the `c` to the first half, and continue with the other half of `s`. Join it all together and add the remainder of `s` :)

Examples:

```
f["coconut", %w(c o)]
=> "ccooconut"
f["banana", %w(b a a)]
=> "bbaanaana"

```

# Answer
> 0 votes
# C, 57

Inspired by BrainSteel's answer:

```
f(char*s,char*c){while(*c-putchar(*s++)||putchar(*c++));}

```

This uses the result of `putchar` to determine whether we've hit one of the replacement list, and if so, advance one through the replacement list, outputting as we go.

If we don't consume all the replacements, we'll go off the end of the input string, but luckily the rules guarantee we wont. :-)

### Test harness:

```
int main(int argc, char* argv[]) {
    f(argv[1], argv[2]);
    return 0;
}

```

# Answer
> 0 votes
## C#, 116 bytes

Indented for clarity:

```
string F(string s,string c){
    int i;
    return c==""
        ?s
        :s.Remove(i=s.IndexOf(c[0]))+c[0]+F(s.Substring(i),c.Substring(1));
}

```

# Answer
> 0 votes
# SM83/Z80 machine language, 14 bytes

Takes input 1 in `de`, input 2 in `hl`, output to `bc`.

```
1A 13 02 03 B7 C8 BE 20
F7 02 03 23 18 F2

```

```
stretch:
 ld a,(de)                  // 1A       load input 1 char
 inc de                     // 13       and increment
 ld (bc),a                  // 02       store it
 inc bc                     // 03       and increment
 or a                       // B7       test for 0
 ret z                      // C8       return if so
 cp (hl)                    // BE       test against input 2 char
 jr nz,stretch              // 20 F7    if not same, continue
 ld (bc),a                  // 02       if same, store again
 inc bc                     // 03       and increment again
 inc hl                     // 23       also increment input 2 char
 jr stretch                 // 18 F2    loop back

```

The register pressure is extreme on this one. There's just enough room for three pointers and a character without pushing things to memory. It's impossible to do it this efficiently without putting the second input into `hl`.

# Answer
> 0 votes
## PHP, 145 Bytes

```
  <?php
$a=str_split($argv[1]);
$b=str_split($argv[2]);
foreach($a as $x){
if($x==$b[0])
{
    $w[] = $x . $x;
    array_shift($b);
}
else $w[] = $x;
}
echo implode($w);

```

Link to compact version

Definitely not the shortest answer, but no one else has done PHP yet so why not! Takes the word as the first argument, and a string representing the characters to be duplicated for the second argument.

I'm still new to golfing, so let me know if you see anything I could improve. Thanks!

# Answer
> 0 votes
# 05AB1E, 9 bytes

```
vy?¬yQić?

```

Pretty similar to my 05AB1E answer for two related challenges: Speed of Lobsters and Backronymiser.

Try it online or verify all test cases.

**Explanation:**

```
v        # Loop over the characters `y` of the first (implicit) input-string:
 y?      #  Print this character
 ¬       #  Push the first letter of the list
         #  (which will be the second implicit input-list in the first iteration)
  yQi    #  If it's equal to the current character `y`:
     ć   #   Extract the head of the list
      ?  #   Pop and print it as well

```

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


title: Yo boy, must it sum

text:
# Question
Title: Yo boy, must it sum
> Every positive integer can be expressed as the sum of at most three palindromic positive integers in any base *b*≥5. Cilleruelo et al., 2017

A positive integer is *palindromic* in a given base if its representation in that base, without leading zeros, reads the same backwards. In the following, *only* base *b*=10 will be considered.

The decomposition as a sum of palindromic numbers is *not unique*. For example, `5` can be expressed directly as `5`, or as the sum of `2, 3`. Similarly, `132` can be decomposed as `44, 44, 44` or as `121, 11`.

## The challenge

Given a positive integer, produce its sum decomposition into three or fewer positive integers that are palindromic in base 10.

## Additional rules

* The algorithm used should work for arbitrarily large inputs. However, it is acceptable if the program is limited by memory, time or data type restrictions.
* Input and output can be taken by any reasonable means. Input and output format is flexible as usual.
* You can choose to produce one or more valid decompositions for each input, as long as the output format is unambiguous.
* Programs or functions are allowed, in any programming language. Standard loopholes are forbidden.
* Shortest code in bytes wins.

## Examples

Since an input can have many decompositions, these are examples rather than test cases. Each decomposition is shown on a different line.

```
Input  ->  Output

5     ->   5
           2, 3

15    ->   1, 3, 11
           9, 6

21    ->   11, 9, 1
           7, 7, 7

42    ->   22, 11, 9
           2, 7, 33

132   ->   44, 44, 44
           121, 11

345   ->   202, 44, 99
           2, 343

1022  ->   989, 33
           999, 22, 1

9265  ->   9229, 33, 3
           8338, 828, 99

```

# Answer
> 19 votes
# Brachylog, 7 bytes

```
~+ℕᵐ.↔ᵐ

```

Try it online!

Surprisingly not that slow.

### Explanation

```
(?)~+  .          Output is equal to the Input when summed
     ℕᵐ.          Each element of the Output is a positive integer
       .↔ᵐ(.)     When reversing each element of the Output, we get the Output

```

# Answer
> 11 votes
# Python 2, ~~82~~ 79 bytes

```
f=lambda n:min([f(n-k)+[k]for k in range(1,n+1)if`k`==`k`[::-1]]or[[]],key=len)

```

Try it online!

# Answer
> 9 votes
# Jelly, ~~12~~ ~~10~~ ~~9~~ 8 bytes

```
ŒṗDfU$ṪḌ

```

Try it online!

### How it works

```
ŒṗDfU$ṪḌ  Main link. Argument: n (integer)

Œṗ        Find all integer partitions of n.
  D       Convert each integer in each partition to base 10.
     $    Combine the two links to the left into a chain.
    U     Upend; reverse all arrays of decimal digits.
   f      Filter the original array by the upended one.
      Ṫ   Take the last element of the filtered array.
          This selects  the lexicographically smallest decomposition of those with
          the minimal amount of palindromes.
       Ḍ  Undecimal; convert all arrays of decimal digits to integers.

```

# Answer
> 8 votes
# Python 2, 117 bytes

```
def f(n):p=[x for x in range(n+1)if`x`==`x`[::-1]];print[filter(None,[a,b,n-a-b])for a in p for b in p if n-a-b in p]

```

Try it online!

Prints a list of lists, each of which is a solution. Rod saved 9 bytes.

# Answer
> 7 votes
# JavaScript (ES6), ~~115~~ ... ~~84~~ 83 bytes

Always returns a three-element array, where unused entries are padded with zeros.

```
f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join``)?f(n,b+!a++):r

```

### Test cases

```
f=(n,b=a=0)=>(r=[b,a%=n,n-a-b]).some(a=>a-[...a+''].reverse().join``)?f(n,b+!a++):r

console.log(JSON.stringify(f(5)))
console.log(JSON.stringify(f(15)))
console.log(JSON.stringify(f(21)))
console.log(JSON.stringify(f(42)))
console.log(JSON.stringify(f(132)))
console.log(JSON.stringify(f(345)))
console.log(JSON.stringify(f(1022)))
console.log(JSON.stringify(f(9265)))
```

# Answer
> 6 votes
# R, 126 bytes ~~145 bytes~~

Thanks to Giuseppe for golfing off 19 bytes

```
function(n){a=paste(y<-0:n)
x=combn(c(0,y[a==Map(paste,Map(rev,strsplit(a,"")),collapse="")]),3)
unique(x[,colSums(x)==n],,2)}

```

Try it online!

Explanation

R does not have a native way to reverse strings and many default string operations don't work on numbers. So first we convert the series of positive integers (plus 0) to characters.

Next we produce a vector of 0 and all palindromes. The string reversal requires splitting each number up by characters, reversing the order of the vector and pasting them back together with no gap.

Next I want to check all groups of three (here's where the 0s are important), luckily R has a built in combination function which returns a matrix, each column in a combination.

I apply the `colSums` function to the matrix and keep only the elements which equal the supplied target.

Finally, because there are two 0s, any set of two positive integers will be duplicated so I use a unique function on the columns.

The output is a matrix where each column is a set of positive, pallindromic integers that sum to the target value. It is lazy and returns 0's when fewer than 3 elements are used.

# Answer
> 5 votes
# Mathematica, 49 bytes

```
#~IntegerPartitions~3~Select~AllTrue@PalindromeQ&

```

Try it online!

returns all solutions

-2~MartinEnder~bytes

# Answer
> 4 votes
# Jelly, 17 bytes

```
RŒḂÐfṗ3R¤YS⁼³$$Ðf

```

Try it online!

-6 bytes thanks to HyperNeutrino.

Outputs all ways. However the output consists of some duplicates.

# Answer
> 4 votes
# Jelly, 14 bytes

```
L<4aŒḂ€Ạ
ŒṗÇÐf

```

Try it online!

Very, *very* inefficient.

# Answer
> 4 votes
# Ohm v2, ~~13~~ ~~12~~ 10 bytes

```
#Dð*3ç⁇Σ³E

```

Try it online!

# Answer
> 3 votes
# Haskell, ~~90~~ ~~86~~ 79 bytes

-7 bytes thanks to Laikoni!

```
f=filter
h n=[f(>0)t|t<-mapM(\_->f(((==)<*>reverse).show)[0..n])"123",sum t==n]

```

Try it online!

Returns a list of all solutions with some duplication.

# Answer
> 3 votes
# Java (OpenJDK 8), 185 bytes

```
n->{for(int i=0,j=n,k;++i<=--j;)if(p(i))for(k=0;k<=j-k;k++)if(p(k)&p(j-k))return new int[]{j-k,k,i};return n;}
boolean p(int n){return(""+n).equals(""+new StringBuffer(""+n).reverse());}

```

Try it online!

Remove 1 byte from TIO to get the correct amount because the submission doesn't contain the `;` after the lambda.

# Answer
> 3 votes
# Husk, 11 bytes

```
ḟo=⁰Σm↑3Ṗİ↔

```

Try it online!

-2 from DLosc.

# Answer
> 2 votes
# Proton, 117 bytes

```
a=>filter(l=>all(p==p[by-1]for p:map(str,l)),(k=[[i,a-i]for i:1..a-1])+sum([[[i,q,j-q]for q:1..j-1]for i,j:k],[]))[0]

```

Try it online!

Outputs a solution

# Answer
> 2 votes
# Pyth,  ~~16 12~~  10 bytes

```
ef_I#`MT./

```

**Try it here!**

## How it works

```
ef_I#`MT./  ~ Full program.

        ./  ~ Integer Partitions.
 f          ~ Filter with a variable T.
     `MT    ~ Map each element of T to a string representation.
    #       ~ Filter.
  _I        ~ Is palindrome? (i.e Invariant over reverse?)
e           ~ Get last element.

```

# Answer
> 2 votes
# 05AB1E, 17 bytes

```
LʒÂQ}U4GXNãDO¹QÏ=

```

Try it online!

---

Outputs the result in three lists as follows:

* Palindromic lists of length 1 (the original number IFF it's palindromic).
* Palindromic lists of length 2.
* Palindromic lists of length 3.

# Answer
> 2 votes
# Axiom, 900 bytes

```
R(x)==>return x;p(r,a)==(n:=#(a::String);if r<0 then(a=0=>R a;n=1 or a=10^(n-1)=>R(a-1);a=10^(n-1)+1=>R(a-2));if r>0 then(n=1 and a<9=>R(a+1);a=10^n-1=>R(a+2));r=0 and n=1=>1;v:=a quo 10^(n quo 2);repeat(c:=v;w:=(n rem 2>0=>v quo 10;v);repeat(c:=10*c+w rem 10;w:=w quo 10;w=0=>break);r<0=>(c<a=>R c;v:=v-1);r>0=>(c>a=>R c;v:=v+1);R(c=a=>1;0));c)
b:List INT:=[];o:INT:=0
f(a:NNI):List INT==(free b,o;o:=p(-1,o);w:=0;c:=#b;if c>0 then w:=b.1;e:=a-o;e>10000000=>R[];if w<e then repeat(w:=p(1,w);w>e=>break;b:=cons(w,b));g:List INT:=[];for i in #b..1 by-1 repeat(b.i>e=>break;g:=cons(b.i,g));if o>e then g:=cons(o,g);n:=#g;for i in 1..n repeat(x:=g.i;x=a=>R[x];3*x<a=>break;for j in i..n repeat(y:=g.j;t:=x+y;t>a=>iterate;t=a=>R[x,y];t+y<a=>break;for k in j..n repeat(z:=t+g.k;z=a=>R[x,y,g.k];z<a=>break)));[])
D(a:NNI):List INT==(free o;p(0,a)=1=>[a];o:=a;for j in 1..10 repeat(t:=f(a);#t>0=>R t);[])

```

test code

```
--Lista random di n elmenti, casuali compresi tra "a" e "b"
randList(n:PI,a:INT,b:INT):List INT==
    r:List INT:=[]
    a>b =>r
    d:=1+b-a
    for i in 1..n repeat
          r:=concat(r,a+random(d)$INT)
    r

test()==
   a:=randList(20,1,12345678901234)
   [[i,D(i)] for i in a]

```

If this code has to decompose the number X in 1,2,3 palindrome, what this code does, it is try near palindrome N \< X and decompose X-N in 2 palindrome; if this decomposition of X-N has success return 3 palindrome found; if it fail, it try the prev palindrome G \< N \< X and try decompose X-G in 2 palindrome etc. Ungolf code (but it is possible some bug)

```
 R(x)==>return x

-- se 'r'=0 ritorna 1 se 'a' e' palindrome altrimenti ritorna 0
-- se 'r'>0 ritorna la prossima palindrome >'a'
-- se 'r'<0 ritorna la prossima palindrome <'a'
p(r,a)==(n:=#(a::String);if r<0 then(a=0=>R a;n=1 or a=10^(n-1)=>R(a-1);a=10^(n-1)+1=>R(a-2));if r>0 then(n=1 and a<9=>R(a+1);a=10^n-1=>R(a+2));r=0 and n=1=>1;v:=a quo 10^(n quo 2);repeat(c:=v;w:=(n rem 2>0=>v quo 10;v);repeat(c:=10*c+w rem 10;w:=w quo 10;w=0=>break);r<0=>(c<a=>R c;v:=v-1);r>0=>(c>a=>R c;v:=v+1);R(c=a=>1;0));c)

b:List INT:=[]   -- the list of palindrome
o:INT:=0         -- the start value for search the first is a

--Decompose 'a' in 1 or 2 or 3 palindrome beginning with prev palindrome of o
--if error or fail return []
f(a:NNI):List INT==
    free b,o
    -- aggiustamento di o, come palindrome piu' piccola di o
    o:=p(-1,o)
    -- aggiustamento di b come l'insieme delle palindromi tra 1..a-o compresa
    w:=0;c:=#b
    if c>0 then w:=b.1 --in w la massima palindrome presente in b
    e:=a-o
    output["e=",e,"w=",w,"o=",o,"#b=",#b]
    e>10000000=>R[]   --impongo che la palindrome massima e' 10000000-1
    if w<e then       --se w<a-o aggiungere a b tutte le palindromi tra w+1..a-o
          repeat(w:=p(1,w);w>e=>break;b:=cons(w,b))
                      -- g e' l'insieme dei b palindromi tra 1..a-o,o
    g:List INT:=[];for i in #b..1 by-1 repeat(b.i>e=>break;g:=cons(b.i,g))
    if o>e then g:=cons(o,g)
    --output["g=",g,b]
    n:=#g
    for i in 1..n repeat
        x:=g.i
        x=a  =>R[x]
        3*x<a=>break
        for j in i..n repeat
           y:=g.j;t:=x+y
           t>a   =>iterate
           t=a   =>R[x,y]
           t+y<a =>break
           for k in j..n repeat
                z:=t+g.k
                z=a =>R[x,y,g.k]
                z<a =>break
    []

--Decompose 'a' in 1 or 2 or 3 palindrome
--if error or fail return []
dPal(a:NNI):List INT==
   free o
   p(0,a)=1=>[a]
   o:=a                  -- at start it is o=a
   for j in 1..10 repeat -- try 10 start values only
        t:=f(a)
        #t>0=>R t
   []

```

results:

```
(7) -> [[i,D(i)] for i in [5,15,21,42,132,345,1022,9265] ]
   (7)
   [[5,[5]], [15,[11,4]], [21,[11,9,1]], [42,[33,9]], [132,[131,1]],
    [345,[343,2]], [1022,[999,22,1]], [9265,[9229,33,3]]]
                                                      Type: List List Any
                                   Time: 0.02 (IN) + 0.02 (OT) = 0.03 sec
(8) -> test()
   (8)
   [[7497277417019,[7497276727947,624426,64646]],
    [11535896626131,[11535888853511,7738377,34243]],
    [2001104243257,[2001104011002,184481,47774]],
    [3218562606454,[3218561658123,927729,20602]],
    [6849377785598,[6849377739486,45254,858]],
    [375391595873,[375391193573,324423,77877]],
    [5358975936064,[5358975798535,136631,898]],
    [7167932760123,[7167932397617,324423,38083]],
    [11779002607051,[11779000097711,2420242,89098]],
    [320101573620,[320101101023,472274,323]],
    [5022244189542,[5022242422205,1766671,666]],
    [5182865851215,[5182864682815,1158511,9889]],
    [346627181013,[346626626643,485584,68786]],
    [9697093443342,[9697092907969,443344,92029]],
    [1885502599457,[1885502055881,542245,1331]], [10995589034484,[]],
    [1089930852241,[1089930399801,375573,76867]],
    [7614518487477,[7614518154167,246642,86668]],
    [11859876865045,[11859866895811,9968699,535]],
    [2309879870924,[2309879789032,81418,474]]]
                                                      Type: List List Any
      Time: 0.25 (IN) + 115.17 (EV) + 0.13 (OT) + 28.83 (GC) = 144.38 sec

```

# Answer
> 2 votes
# 05AB1E, 8 bytes

```
ÅœR.ΔDíQ

```

Try it online!

Explanation:

```
Åœ          # integer partitions of the input
  R         # reversed (puts the shortest ones first)
   .Δ       # find the first one that...
     D Q    # is equal to...
      í     # itself with each element reversed

```

# Answer
> 2 votes
# Vyxal, 6 bytes

```
ṄṘ‡R⁼c

```

Try it Online!

```
ṄṘ‡R⁼c
Ṅ      # Integer partitions (from longest to shortest)
 Ṙ     # Reverse to make the shortest partitions be at the beginning
  ‡  c # Find the first element that satisfies:
   R   #  Reverse each
    ⁼  #  Equal to the original item?

```

# Answer
> 1 votes
# Java (OpenJDK 8), 605 bytes

Prints dupes but they aren't banned afaik

```
a->{int i=0,j,k,r[]=new int[a-1];for(;i<a-1;r[i]=++i);for(i=0;i<a-1;i++){if(r[i]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse()))System.out.println(r[i]);for(j=0;j<a-1;j++){if(r[i]+r[j]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse())&(""+r[j]).equals(""+new StringBuffer(""+r[j]).reverse()))System.out.println(r[i]+" "+r[j]);for(k=0;k<a-1;k++)if(r[i]+r[j]+r[k]==a&(""+r[i]).equals(""+new StringBuffer(""+r[i]).reverse())&(""+r[j]).equals(""+new StringBuffer(""+r[j]).reverse())&(""+r[k]).equals(""+new StringBuffer(""+r[k]).reverse()))System.out.println(r[i]+" "+r[j]+" "+r[k]);}}}

```

Try it online!

# Answer
> 1 votes
# APL (Dyalog), 51 bytes

```
{w/⍨⍵=+/¨w←(,y∘.,z),,(z←,∘.,⍨y),y←,x/⍨(⌽≡⊢)¨⍕¨x←⍳⍵}

```

Try it online!

# Answer
> 1 votes
# Ruby, 84 bytes

Builds a list of all possible combinations of 3 palindromes from 0 to n, finds the first one whose sum matches, then prunes the zeroes.

```
->n{a=(0..n).select{|x|x.to_s==x.to_s.reverse};a.product(a,a).find{|x|x.sum==n}-[0]}

```

Try it online!

# Answer
> 1 votes
# Perl 6, 51 bytes

```
{first *.sum==$_,[X] 3 Rxx grep {$_ eq.flip},1..$_}

```

Try it online!

* `grep { $_ eq .flip }, 1 .. $_` produces a list of all palindromic numbers from 1 to the input number.
* `3 Rxx` replicates that list three times.
* `[X]` reduces that list-of-lists with the cross-product operator `X`, resulting in a list of all 3-tuples of palindrominc numbers from 1 to the input number.
* `first *.sum == $_` finds the first such 3-tuple that sums to the input number.

# Answer
> 1 votes
# Add++, 62 bytes

```
D,g,@,BDdbR=
D,l,@@,$b+=
D,k,@@*,
L,RÞgdVBcB]Gd‽kdG‽k€bF++A$Þl

```

Try it online!

~50 bytes golfed while writing up an explanation. Defines a lambda function which returns a list of lists containing the solutions.

## How it works

The last line contains the main function and works by generating all sublists of lengths \\$1, 2\\$ and \\$3\\$ containing only palindromic numbers between \\$1\\$ and \\$n\\$, then discarding those whose sum does not match \\$n\\$.

The first section, and helper function, generates the range \\$1, 2, ..., n\\$, and filters out any number that isn't a palindrome. The helper function `g` is a palindrome checker and `RÞg` filters the range on `g`. We then save this filtered list as \\$A\\$ for later.

The next section can be split into three further parts:

```
BcB]
Gd‽k
dG‽k€bF

```

The first part takes the array \\$A\\$ (`[1 2 3 4 ...]`) and wraps each element in an array, yielding `[[1] [2] [3] [4] ... ]`. We then push \\$A\\$ twice and run the table quick over the function `k`:

```
D,k,@@*,

```

This function does basically nothing. It receives two arguments and wraps them in an array. However, the table quick,  is the magic trick here. It takes two lists and generates every pair of elements between those two lists. So `[1 2 3]` and `[4 5 6]` generates `[[1 4] [1 5] [1 6] [2 4] [2 5] [2 6] [3 4] [3 5] [3 6]]`. It then takes its functional argument (in this case `k`) and runs that function over each pair, which, in this case, simply returns the pairs as is.

After the first two parts are completed, the stack contains a list of wrapped palindromic integers (all palindromic numbers of list length 1), and a list of pairs of numbers that pair each palindromic number with every other palindromic number. The third section pushes the second array again, then pushes \\$A\\$, and runs the table function over the two arrays. This almost generates the list of triples we need, but annoyingly, each triple has a nested pair. To remove this, we run `€bF` over the list which flattens each sublist. Finally, we concatenate the three lists to form a list of all required sublists.

We've generated all sublists of length \\$1, 2\\$ and \\$3\\$ containing palindromic numbers, so all we need to do now is filter those whose sum is not the input. So, we push \\$n\\$ again and filter each sublist of `l`, which returns whether the sum of the array is equal to \\$n\\$. Finally, we return the list of lists.

# Answer
> 1 votes
# Python 3, 106 bytes

```
lambda n:[(a,b,n-a-b)for a in range(n)for b in range(n)if all(f'{x}'==f'{x}'[::-1]for x in(a,b,n-a-b))][0]

```

Try it online!

In the TIO link I used a faster (but 1 byte longer version) that takes the first valid result as a generator, rather than building the entire list of possible combinations and taking the first.

# Answer
> 1 votes
# Lua, 334 bytes

```
m=math.floor function p(a)a=tostring(a)return a:reverse()==a end
s=io.read()function g(s) for i=s,1,-1 do if(p(m(i)))then
t=i for j=s-i,1,-1 do if (p(m(j)))then u=j for k=t-j,0,-1 do
if(p(m(k))and(k~=0)and((t+u+k)==tonumber(s)))then
print(m(t))print(m(u))print(m(k))return end end end end end end end
if(p(s))then print(s)else g(s)end

```

Try it online!

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


# Question
Title: Cartesian product of a list with itself n times
When given a a list of values and a positive integer `n`, your code should output the cartesian product of the list with itself `n` times.

For example, in pseudocode your function could be similar to:

```
for x1 in list:
    for x2 in list:
        for x3 in list:
            ...
            for xn in list:
                print x1, x2, x3, ... , xn

```

Example:

```
repeated_cart([1,2,3], 3)

1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

```

Built in functions (or functions from imported libraries) that compute the Cartesian product or Cartesian power are not allowed due to the resulting code being somewhat boring.

Inputs and outputs should be delimited but can be taken in any reasonable method. The order the output is given does not matter but duplicates are not allowed.

This is so shortest code wins

# Answer
# Haskell, 21 bytes

```
l#n=mapM(\_->l)[1..n]

```

Try it online!
> 10 votes

# Answer
# , 41 bytes

```
function(l,n)unique(t(combn(rep(l,n),n)))

```

Try it online!

`combn` is definitely not a cartesian product built-in, as it computes all `n`-combinations of its input.

# , 40 bytes

```
function(l,n)expand.grid(rep(list(l),n))

```

Try it online!

`expand.grid` is probably a cartesian product built-in.
> 7 votes

# Answer
# Common Lisp, 146 bytes

```
(defun f(l n)(if(< n 2)(loop for x in l collect(list x))(loop for a in l nconc(loop for b in(f l(1- n))collect(cons a b)))))(princ(f(read)(read)))

```

Try it online!

ungolfed

```
(defun nloops (lst n)
  (if (< n 1)
      '(())
      (if (< n 2)
          (loop for x in lst collect (list x))
          (loop for a in lst
                nconc (loop for b in (nloops lst (1- n))
                            collect (cons a b))))))

```
> 6 votes

# Answer
# Perl 6, 16 bytes

```
{[X,] $^a xx$^b}

```

Try it

## Expnded:

```
{  # bare block lambda with placeholder parameters $a and $b

  [X,]         #reduce using Cross meta op combined with comma op

    $^a xx $^b # list repeat $a, by $b times
}

```
> 4 votes

# Answer
# APL (Dyalog Classic), ~~18~~ 12 bytes

```
{⍺[↑,⍳⍵⍴≢⍺]}

```

Try it online!

-6 bytes thanks to @ngn !
> 3 votes

# Answer
# K (ngn/k), 10 bytes

```
{x@+!y##x}

```

Try it online!

`{` `}` is a function with arguments `x` and `y`

`#x` the length of `x`

`y##x` the length of `x` repeated `y` times

`!y##x` all length-y tuples over 0,1,...,length(x)-1 as a transposed matrix

`+` transpose

`x@` elements of `x` at those indices
> 3 votes

# Answer
# Python 2, ~~69~~ 58 bytes

```
f=lambda a,n:n and[v+[i]for v in f(a,n-1)for i in a]or[[]]

```

Try it online!

Takes a list `a` and an integer `n`; returns a list of lists.
> 3 votes

# Answer
# Perl 5, 33 bytes

```
say for glob(join',',("{$_}")x<>)

```

Try it online!
> 3 votes

# Answer
# Prolog (SWI), 72 bytes

```
R-1-R.
L-N-R:-O is N-1,L-O-M,findall([H|T],(member(H,L),member(T,M)),R).

```

Try it online!
> 3 votes

# Answer
# Ruby, 53 bytes

```
f=->l,n{n<2?l:l.flat_map{|i|f[l,n-1].map{|j|[i,*j]}}}

```

Try it online!

Recursive approach, not so short, but guaranteed to be free of any built-ins.

It's tempting to use permutation methods, but this probably doesn't count, and the docs actually state no guarantees of the order correctness, although seems to work in practice:

# Ruby, 35 bytes

```
->l,n{[*l.repeated_permutation(n)]}

```

Try it online!
> 3 votes

# Answer
# Jelly, ~~11~~ ~~9~~ 7 bytes

```
³;þẎƊ’¡

```

Try it online!

## Explanation

```
³;þẎƊ’¡
³;þẎ    **Implements** the cartesian product of a value with the input
    Ɗ   Groups those together
     ’¡ Repeat (n-1) times

```
> 2 votes

# Answer
# Java 10, 19 + 135 = 154 bytes

```
import java.util.*;

```

```
List<List>f(Set l,int n){var o=new Stack();if(n<1)o.add(new Stack());else for(var t:l)for(var i:f(l,n-1)){i.add(t);o.add(i);}return o;}

```

Try It Online

## Ungolfed

```
List<List> f(Set l, int n) {
    var o = new Stack();
    if (n < 1)
        o.add(new Stack());
    else
        for (var t : l)
            for (var i : f(l, n - 1)) {
                i.add(t);
                o.add(i);
            }
    return o;
}

```

## Acknowledgments

* port to Java 10 thanks to Kevin Cruijssen
> 2 votes

# Answer
# Racket, 92 bytes

```
(define(f l n)(if(> n 0)(apply append(map(λ(r)(map(λ(e)(cons e r))l))(f l(- n 1))))'(())))

```

Try It Online

## Ungolfed

```
(define (f l n)
    (if (> n 0)
        (apply append
            (map
                (λ (r)
                    (map (λ (e) (cons e r)) l)
                )
                (f l (- n 1))
            )
        )
        '(())
    )
)

```
> 2 votes

# Answer
# Pure Bash (no external utilities), 57

```
printf -vn %0$1d
a=${n//0/{$2\}}
eval echo ${a//\}{/\},{}

```

Input is given as command-line parameters; 1st is `n`, 2nd is a comma-separated list.

```
printf -vn %0$1d         ;# Create a string of n "0"s in the variable v
a=${n//0/{$2\}}          ;# Replace each "0" with "{a,b,...m}"
eval echo ${a//\}{/\},{} ;# Replace each "}{" with "},{" and evaluate the resulting brace expansion

```

Try it online!
> 2 votes

# Answer
# , ~~17~~ 10 bytes

-7 bytes thanks to Jonah!

```
>@,@{@(#<)

```

Try it online!

## Original soluton:

# , 17 bytes

```
]{~(##)#:#@]i.@^[

```

## How it works?

I enumerate all the `n`-digit numbers in a number system with base the length of the list.

```
            i.         - creates a list from zero to (not including)
         #@]           - the length of the list
              @^       - to the power of
                [      - n (left argument)
   (##)                - creates a list of n times the length of the list (for the bases)
       #:              - converts all the numbers into lists of digits in the new base
]{~                    - use the digits as indices into the list

```

Try it online!
> 2 votes

# Answer
# Oracle SQL, 177 bytes

Create a collection type (31 bytes):

```
CREATE TYPE t IS TABLE OF INT;

```

Then use the query (146 bytes):

```
WITH n(a,b,c)AS(SELECT a,b,t()FROM i UNION ALL SELECT a,b-1,c MULTISET UNION t(COLUMN_VALUE)FROM n,TABLE(n.a)WHERE b>=0)SELECT c FROM n WHERE b=0

```

Assuming that the input parameters are in the table `i` with columns `a` and `b`:

```
CREATE TABLE i (a t,b INT) NESTED TABLE a STORE AS t_a;
INSERT INTO i VALUES ( t(1,2,3), 3 );

```

SQL Fiddle

**Results**:

```
|     C |
|-------|
| 1,1,1 |
| 1,1,2 |
| 1,1,3 |
| 1,2,1 |
| 1,2,2 |
| 1,2,3 |
| 1,3,1 |
| 1,3,2 |
| 1,3,3 |
| 2,1,1 |
| 2,1,2 |
| 2,1,3 |
| 2,2,1 |
| 2,2,2 |
| 2,2,3 |
| 2,3,1 |
| 2,3,2 |
| 2,3,3 |
| 3,1,1 |
| 3,1,2 |
| 3,1,3 |
| 3,2,1 |
| 3,2,2 |
| 3,2,3 |
| 3,3,1 |
| 3,3,2 |
| 3,3,3 |

```
> 2 votes

# Answer
# Jelly, 5 bytes

```
ẋœ!ṛQ

```

Try it online!

Completely different method to Adalynn's existing answer, plus two bytes shorter, so I thought I'd post a separate answer.

The Footer in the TIO link simply runs the above link then checks to see if the result is the same as the Cartesian power builtin. Remove it to see the full output

Same as the old version is length, but more tacit.

## How it works

```
ẋœ!ṛQ - Main link. Takes a list l on the left and n on the right
ẋ     - Repeat l n times; Call this m
   ṛ  - Right; Yield the right argument n
 œ!   - Yield all permutations of m of length n
    Q - Remove duplicates

```

The previous answer, `ẋ⁹œ!Q` used a `2-0, 2, 1` chain, where the  was necessary to prevent the `œ!` chaining to the . In this version, we have a `2, 2, 2, 1` chain. As it is at the start of the chain, the special `2,2,2` pattern is matched, meaning we execute the first three dyads, then deduplicate whatever that results in.

For three dyads `x (f g h) y`, we calculate `(x f y) g (x h y)` with this `2,2,2` pattern. `f` here is , meaning we repeat the list in `x` `y` times. `h` is , which takes two arguments and returns the right one `y`. Therefore, we're passing the repeated list to `œ!` on the left and `y` on the right, thus getting the permutations of length `y`.
> 2 votes

# Answer
# Octave, 38 bytes

```
@(x,n)x(dec2base(0:n^numel(x)-1,n)-47)

```

Anonymous function that takes a row vector of values and an integer.

**Try it online!**
> 1 votes

# Answer
# Bash, 61 bytes

```
N=$1
shift
IFS=,
printf echo\\t%${N}s ""|sed "s/ /{$*},/g"|sh

```

Try it online! I found repeating strings and joining lists with commas surprisingly hard to do in bash.
> 1 votes

# Answer
# Javascript (Node), 75 bytes

```
c=(m,n,a,i)=>a.length-n?m.map((_,j)=>c(m,n,[...a,m[j]],i+1)):console.log(a)

```

Recursive function which outputs the list to the console. Where `a` is an empty array and `i` is 0 (not sure if this still qualifies):

```
c([1,2,3], 3, [], 0);

```

Try it online!
> 1 votes

# Answer
# JavaScript (SpiderMonkey), 52 bytes

```
c=>g=(n,...l)=>n?c.map(w=>g(n-1,...l,w)):print(...l)

```

Try it online!
> 1 votes

# Answer
# CJam, 26 bytes

```
q~(_"m*:e_"*\'_*@\~W$~:p];

```

Try it online!

If only CJam had one character commands for cartesian product and flattening.
> 1 votes

# Answer
# Pyth, 5 bytes

```
.nM**

```

Try it online!
> 1 votes

# Answer
# Vyxal, 5 bytes

```
ẋf⁰↔U

```

Try it Online!
> 1 votes

# Answer
# Pari/GP, 46 bytes

```
(l,n)->matrix(#l^n,n,i,j,l[i--\#l^(n-j)%#l+1])

```

Try it online!
> 0 votes

---
Tags: code-golf, math, array, combinatorics
---


# Question
Title: Plot Slope Fields Given Differential Equation
Slope fields or direction fields, are a graphical representation of the solutions to a first-order differential equation of a scalar function. A slope field shows the slope of a differential equation at certain vertical and horizontal intervals on the cartesian plane, and can be used to determine the approximate tangent slope at a point on a curve, where the curve is some solution to the differential equation. For example consider the differential equation:

$$ \frac{dy}{dx} = \frac{y-4x}{x-y} $$

The corresponding slope field will look like:

Another example with this differential equation:

$$ \frac{dy}{dx} = \frac{x-y}{x-2y} $$

Your task is to generate such slope fields in the console with characters of text. You are to print the following for each coordinate pair:

* `/` If the differential equation evaluated at the point \\$(x, y)\\$ is positive.
* `\` If the differential equation evaluated at the point \\$(x, y)\\$ is negative.
* `-` If the differential equation evaluated at the point \\$(x, y) = 0\\$.
* `|` If the differential equation evaluated at the point \\$(x, y)\\$ is undefined.

The inputs are a string and a number consisting of:

* Expression string that can be evaluated (or parsed if you have to).
* A number that outlines the radius of the plot from \\$(0, 0)\\$.

The expression string can use any built-in mathematical function and will only either \\$x\\$ or \\$y\\$ as variables. Any combination of logarithms, (inverse and/or hyperbolic) trigonometric functions, or functions like `sqrt(), pow(), exp(), abs()` may be used in the expression. The plot radius may also be 0, which means only print one character containing the slope at the origin. A sample input may look something like:

```
plotRadius = 10
expression = "(x - y) / (x - 2 * y)"

```

Notice how both the boundaries of the plot follow: \\$ -\text{plotRadius} \leq x, y \leq \text{plotRadius}\\$. This results in the following slope field being displayed:

```
/ / / / / / / / / / / / / / / / / / / / —
/ / / / / / / / / / / / / / / / / / / — \
/ / / / / / / / / / / / / / / / / / — \ \
/ / / / / / / / / / / / / / / / / — \ \ \
/ / / / / / / / / / / / / / / / — \ \ \ \
/ / / / / / / / / / / / / / / — \ \ \ \ |
/ / / / / / / / / / / / / / — \ \ \ | / /
/ / / / / / / / / / / / / — \ \ | / / / /
/ / / / / / / / / / / / — \ | / / / / / /
/ / / / / / / / / / / — | / / / / / / / /
/ / / / / / / / / / | / / / / / / / / / /
/ / / / / / / / | — / / / / / / / / / / /
/ / / / / / | \ — / / / / / / / / / / / /
/ / / / | \ \ — / / / / / / / / / / / / /
/ / | \ \ \ — / / / / / / / / / / / / / /
| \ \ \ \ — / / / / / / / / / / / / / / /
\ \ \ \ — / / / / / / / / / / / / / / / /
\ \ \ — / / / / / / / / / / / / / / / / /
\ \ — / / / / / / / / / / / / / / / / / /
\ — / / / / / / / / / / / / / / / / / / /
— / / / / / / / / / / / / / / / / / / / /

```

Please separate each point with a space.

# Answer
> 1 votes
# Julia 1.0, 90 bytes

```
N\~=-(r=-N:N).|>y->println(join(r.|>x->abs(x~y)<Inf ? "\\-/"[Int(sign(x~y))+2] : "|"," "))

```

Try it online!

takes `plotRadius\df`, where `df` is a black-box function and prints the plot

# Answer
> 1 votes
# Burlesque, ~~71~~ 62 bytes

```
pes1Jngjr@sajJ<>cpm{%1!{{@0.<}'\{@0.>}'/{@0==}'-{1}'|}cn}jcosp

```

Try it online!

First stab, still some optimisation to be done

```
pes1       # Parse function and save
J          # Dup
ng         # Negate
jr@        # Range -n..n
sa         # Get length for chunking later
jJ<>cp     # Transform to -n..n x -n..n
m{         # Map
 %1!       # Call function
 {
  {@0.<}'\ # If <0  \
  {@0.>}'/ # If >0  /
  {@0==}'- # If ==0 -
  {1}'|    # else   |
 }cn       # Condition
}
jco        # Chunks of len
sp         # Pretty output

```

# Answer
> 0 votes
# Python 2, 122 bytes

```
def g(r,e):
 q=range(-r,r+1)
 for x in q:
    l=""
    for y in q:
     try:l+="-/\\"[cmp(e(-x,y),0)]+" "
     except:l+="| "
    print l

```

Try it online!

Takes an integer and a function as input, prints the result.

---
Tags: code-golf, ascii-art, calculus
---


title: Simplify Rubik's Cube Moves

text:
# Question
Title: Simplify Rubik's Cube Moves
## Background

On a Rubik's cube there are 54 moves that you can execute, for example, turn the right face anti-clockwise, or rotate the top face and the horizontal slice twice. To notate any move, each face (or slice) has a letter assigned to it. To move that face clockwise once, you just write the letter on its own, so for the top face it would be `U` (for "up"). You can put a `'` (pronounced "prime") after the letter to notate moving the face anti-clockwise, or a `2` to turn the face twice. You can see more details on this here.

## The Challenge

Your challenge is to take a list of moves which all rotate the same face, and simplify it into one move. For example if the input was `R R2`, you'd be turning the right face clockwise once, then twice, which results in the equivalent of `R'` — turning the right face anti-clockwise once.

## Rules

* If the result doesn't modify the cube, the output should be nothing or a falsey value.
* Input must be taken in the proper notation described above, otherwise, it's up to you.
* You can assume that no move will have a `2` *and* a `'` in it.

## Test Cases

```
R R2 -> R'
L2 L L' L -> L'
u' u2 u2 -> u'
y y' ->
F F' F F F' -> F
E' E2 E E E' -> E2

```

# Answer
# Python 2, 49 bytes (inspired by @math junkie)

```
lambda s:(s[0]+"2'"[len(``s``)%2])[:len(``s``)%4]
```

Attempt This Online!

Python 3 version is 51 bytes.

This takes the input sequence as a string without delimiters.

### How?

By applying the backtick operator twice we gain two pairs of quotation marks which is neutral modulo 4 and we get all apostrophes escaped, a cheap way of replacing them with two characters each. Now, we can simply count characters because "A","A2","A\\'" have the right lengths in terms of quarter turns. It remains to format the residue modulo 4 as required.

### Python, 56 bytes

```
lambda s:(s[0]+"**2'"[i:=-sum(map(" *'".find,s))%4])[:i]
```

Attempt This Online!

This version can handle a proper delimiter (single space).

### Old Python, 60 bytes

```
lambda s:(s[0]+"2'")[:(i:=-sum(map("  '2".find,s)))%4:1+i%2]
```

Attempt This Online!
> 9 votes

# Answer
# K (ngn/k), 26 bytes

```
{|(0," 2'",'*x)4!+/1+39=x}

```

Try it online!

-4 bytes thanks to @ovs!

Inspired by @Neil's Retina answer for a bunch of bytes saved.

## Explanation

* `1+39=` 1 for *A*, 2 for *A*2, 3 for *A*'
* `4+/` sum mod 4
* `|(0," 2'",'*x)` convert back to move or 0
> 4 votes

# Answer
# Retina 0.8.2, 24 bytes

```
'
22
\B.
2
+`....$

22
'

```

Try it online! Takes input as a smashed string of moves but link is to test suite that removes spaces for convenience. Explanation:

```
'
22

```

Change anti-clockwise rotations to three rotations (`2` means "repeat last rotation").

```
\B.
2

```

Change face rotations after the first to `2`s too.

```
+`....$

```

Reduce modulo `4`, making sure to keep the first face.

```
22
'

```

Change three rotations back to an anti-clockwise rotation.
> 4 votes

# Answer
# 05AB1E, ~~18~~ ~~17~~ 15 bytes

```
''T:g4%ø`¤£3'':

```

-1 byte being inspired by *@mathJunkie*'s Pyth answer
-2 bytes thanks to *@CommandMaster*

Input as a string without delimiter.

Try it online or verify all test cases.

**Explanation:**

```
''T:      # Replace all "'" with "10" in the (implicit) input-string
    g     # Pop and push the length
     4%   # Modulo-4
ø         # Create pairs with the (implicit) input-string, implicitly only using
          # the first character since we zip it with a single digit
 `        # Pop this single-item list and push the string-pair to the stack
  ¤       # Push its last character, the digit (without popping the string)
   £      # Pop both, and leave just that many leading characters
    3'':  # Replace a potential "3" with "'"
          # (after which the result is output implicitly)

```
> 4 votes

# Answer
# Cubestack, 166 bytes

I think this language is quite fitting.

```
b' S S' y S S' y2 M R' M' M R2 M' l2 M2 M R2 M' D x U' M R2 M' x2 l x M r M' x2 M R' M' x' x' R y' M r' M' U M2 x S R' r R B2 R' U2 S' l' r b' M M' r M R M' r l' R x'

```

Try it Online!

Formatted nicely:

```
b' S S' y
  S S' y2 M R' M' M R2 M' l2 M2
  M R2 M' D x
    U' M R2 M' x2
    l x
      M r M' x2
      M R' M'
    x'
  x' R
y' M r' M' U M2 x
  S R' r R B2 R' U2 S' l' r
  b' M M' r M R M' r
  l' R
x'

```

Goes through each move, if the move ending is `2`, then 2 is added to the total, if it's `'` 3 is added, otherwise 1 is added. The total mod 4 is then used to index into the string `' 2` and the appropriate letter is prepended.
> 4 votes

# Answer
# Charcoal, ~~23~~ 21 bytes

```
≔﹪⁺Ｌθ№θ'⁴η✂⁺§θ⁰§2'η⁰η

```

Try it online! Link is to verbose version of code. Takes a smashed list as input. Explanation:

```
≔﹪⁺Ｌθ№θ'⁴η

```

Add the length to the count of `'`s and reduce modulo `4`.

```
✂⁺§θ⁰§2'η⁰η

```

Concatenate `2` or `'` to the face depending on whether the total is even, but then truncate the string to the reduced length.
> 2 votes

# Answer
# Pyth, ~~22~~ ~~20~~ 17 bytes

*-3 bytes using @loopy wait's idea*

```
<X+hQJ%l``Q4\3\'J

```

Try it online! -- Try all test cases

```
<X+hQJ%l``Q4\3\'J
        ``Q            Surround the input with two pairs of quotes
                       (Which also escapes `'` characters as `\'`)
      %l   4           Take the length mod 4
     J                 (Set J to the result)
  +hQ                  Prepend the first letter of the input
 X           \3\'      Translate `3`s to `'`s
<                J     Keep the first J elements

```
> 2 votes

# Answer
# JavaScript (Node.js), 60 bytes

```
a=>['',p=a[s=0][0],p+2,p+"'",a.map(([,v])=>s+=!v|v||3)][s%4]

```

Try it online!

* -1 bytes by Arnauld
> 1 votes

# Answer
# Jelly, 19 bytes

```
ḢɓḟḲOȯ€1S%4ị⁾'2⁹;ḣƲ

```

**Try it online!**

There's probably shorter! Calculates the rotation, R, using the sum of the ordinals of the characters trailing each letter or `1` if none exists modulo 4. Concatenates `'` or `2` to the leading letter depending on R mod two and then heads this to the first (up to) R characters.
> 0 votes

---
Tags: code-golf, rubiks-cube
---


title: Flood fill by distance

text:
# Question
Title: Flood fill by distance
Say I have a grid with some obstacles:

```
 ----
|  X |
|    |
|XX  |
|    |
 ----

```

I can fill this with numbers, as distance from the top left corner. But, because there are obstacles in the way some cells will take further to reach than a straight line:

```
 ----
|01X5|
|1234|
|XX45|
|7656|
 ----

```

This can be done through flood filling:

```
 ----   ----   ----   ----   ----   ----   ----   ----
|0 X | |01X | |01X | |01X | |01X | |01X5| |01X5| |01X5|
|    | |1   | |12  | |123 | |1234| |1234| |1234| |1234|
|XX  | |XX  | |XX  | |XX  | |XX4 | |XX45| |XX45| |XX45|
|    | |    | |    | |    | |    | |  5 | | 656| |7656|
 ----   ----   ----   ----   ----   ----   ----   ----

```

Your challenge is to, given a binary matrix containing obstacles, flood fill it like so from the top left hand corner and output a corresponding matrix.

The first example of a grid is equivalent to the following matrix:

```
[ [0, 0, 1, 0],
  [0, 0, 0, 0],
  [1, 1, 0, 0],
  [0, 0, 0, 0] ]

```

And the corresponding output would be:

```
[ [0, 1, X, 5],
  [1, 2, 3, 4],
  [X, X, 4, 5],
  [7, 6, 5, 6] ]

```

Where X is any value that isn't a positive integer.

You may take any two consistent values in the matrix instead of 1 and 0, and you may choose any value to represent obstacles. Distances may be 0 or 1-indexed. You may assume the whole matrix can be flood filled from the top left corner, which cannot be an obstacle.

You must be able to support numbers with multiple digits.

This is , shortest wins!

## Testcases

These use -1 as X.

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

```

# Answer
> 6 votes
# , 54 46 bytes

```
[:(#-+/)](+[:+./(0,(,-)=0 1)|.!.0=&1)^:a:${.1:

```

Try it online!

# Answer
> 4 votes
# BQN, ~~36~~ 34 bytesSBCS

Uses  for obstacles in input and output.

```
{(⌈⊢⌊1+(«˘⌈«⌈»⌈»˘)⌾÷)⍟(≠⥊)0⌾⊑∞¨}

```

Run online!

`0⌾⊑∞¨` Generate a matrix of the same shape as the input, with a 0 in the top left corner and ∞ anywhere else.
`( ... )⍟(≠⥊)` Iterate the function on the left as many times as there are values in the matrix. (You could get away with less iterations, but this is golfy)

`(⌈⊢⌊1+(«˘⌈«⌈»⌈»˘)⌾÷)` Tacit function that performs one step of flood filling:

`( ... )⌾÷` Take the reciprocal of each value, do some transformations on that, then take the reciprocal (its own inverse) again.
The idea is that we want to shift in ∞ from each side, then take the element-wise minimum between the four matrices. BQN shift builtins `»` and `«` push in 0 instead, which is why do the shifting in "reciprocal space".
`«˘⌈«⌈»⌈»˘` pushes in 0s from all four directions, and takes the element-wise maximum.

Now we increment each value (`1+`), take the minimum with the previous step (`⊢⌊`) and the maximum with the input () to make sure the obstacles stay at ∞.

---

An adjacency matrix based approach is much longer at 52 bytes:

```
↕∘≢{⌈+˝¬⊏˘>(=⌜˜⊸≥(+´|∘-)⌜˜)∨˝∘∧⎉1‿∞⍟(↕≠)≡⌜˜}⌾⥊⊢

```

Run online!

# Answer
> 4 votes
# Jelly, ~~20~~ 19 bytes

```
ẸŻạ§ỊẸʋƇ@ƬŒMŒṬ+C¬S:

```

Try it online!

Inspired by @Jonathan Allan's answer (it started as a golf of that answer, but portions were rewritten, and it changed so extensively that it makes more sense to post a new answer); this answer uses a similar algorithm (although not exactly the same).

Output is 1-based, using NaN for walls.

## Explanation

```
ẸŻạ§ỊẸʋƇ@ƬŒMŒṬ+C¬S:
Ẹ                     1 if the input contains any nonzeros (it does)
 Ż                    prepend 0 (thus creating [0,1])
         Ƭ            Loop until we reach a steady state:
       Ƈ                {Set the loop variable to} a filtered subset of
        @ ŒM              the multidimensional indexes of {the input}
       Ƈ                keeping only those elements for which
      ʋ                   the following four-step procedure {returns true}:
  ạ                         absolute difference of {the index} from
                              {the loop variable, or each of its elements}
   §                        add the x-difference to the y-difference
     Ẹ                      at least one of those difference sums
    Ị                       has a magnitude of at most 1
            ŒṬ        {For each iteration}, create an array with 1s at
                         the indexes {in that iteration's loop variable}
              +       {For each iteration's array}, add, and reshape to,
               C        {the input} with each element subtracted from 1
                ¬     Replace 0s with 1s, other values with 0s
                 S    Sum {the arrays from each iteration}
                  :   Integer divide by {the input grid}

```

The basic idea is that we maintain a list of coordinates that our flood fill has reached, and repeatedly filter the list of non-wall coordinates to find those coordinates which are close to those in the previous iteration.

The initial coordinate, used on the first iteration, is \[0,1\]. Jelly uses 1-based indexing, so this is actually outside the array (but still at a distance of 1 from the top-left corner, allowing the loop to get started). The loop is written as a data-type polyglot; it works both on a single coordinate pair (such as \[0,1\]), and on a list of coordinate pairs (which is what it gets on every subsequent iteration). After the loop, the `ŒṬ` can treat the \[0,1\] the same way as all the coordinate lists (basically producing an array with no coordinates), so it doesn't matter that the loop variable is a coordinate pair on the first iteration and a list of coordinate pairs on subsequent iterations.

The `+C` doesn't have any effect on the array values (other than setting the value of walls to 1); its purpose is to pad out all the arrays generated by `ŒṬ` so that they're the same size as the input, making it possible to use `¬` to place 1s in all the squares that the flood-fill hadn't reached by that iteration. Then we can just sum the arrays to learn how long it took to reach each square, as in the other two Jelly answers.

Although Jelly has a constant `Ø.` to produce the list \[0,1\], writing it at the start of the program would trigger a special case in the parser, which would subsequently cause the `ŒM` later in the program to parse incorrectly. As a consequence, we need to generate the \[0,1\] as a function of the input, rather than using a constant, but fortunately this is possible in two bytes and thus the special case in question ends up not costing. (Because the input has a 1 in the top-left corner, there's guaranteed to be at least one nonzero value in the input.)

# Answer
> 3 votes
# Retina, 121 bytes

```
^.
0

{P^` +\S+
(?<=(.)*) +_(?=(.*¶(?<-1>.)*(?(1)^))? +(\d+)|(?<=(?<3>\d+)((?(5)$)(?<-5>.)*¶.*)? +_(?=(.)*)))
 $.($3*__

```

Try it online! Uses `_` for `0` and `X` for `1`. Explanation:

```
^.
0

```

Start flood filling at the top left.

```

```

Space everything apart.

```
{`

```

Repeat until everything has been filled.

```
P^` +\S+

```

Align all of the columns to the largest value found so far.

```
(?<=(.)*) +_(?=(.*¶(?<-1>.)*(?(1)^))? +(\d+)|(?<=(?<3>\d+)((?(5)$)(?<-5>.)*¶.*)? +_(?=(.)*)))

```

Match underscores that are either to the left ( `+_(?= +(\d+))`), above (`(?<=(.)*) +_(?=.*¶(?<-1>.)*(?(1)^) +(\d+)`), to the right ( `+_(?<=(?<3>\d+) +_)`) or below ( `+_(?<=(?<3>\d+)(?(5)$)(?<-5>.)*¶.* +_(?=(.)*))`) an integer, ensuring to capture the integer in capture group `3`.

```
 $.($3*__

```

Replace the underscore with the incremented integer.

# Answer
> 3 votes
# Jelly, 27 bytes

```
ŒM_Ø.ŒṬ»ḤZUµ4¡«³
FJỊṁ³ÇƬ¬S:

```

Try it online!

Input format: 0 for wall, 1 for passable cell.

Output format: 0-based, walls are represented as floating-point infinity.

This only works as a full program, because it assumes that the first command-line argument and the input to the main function are the same as each other (which they will be for a full program, but not for a function run as part of a larger program).

## Explanation

### Helper function `1Ŀ`

The helper function takes a matrix of 1s and 0s as its input; everywhere that's a 0 in the program input must be a 0 in the helper function input, but otherwise the helper function can have 1s and 0s anywhere. The output from the helper function is the same matrix with every non-wall space (based on the input to the program as a whole) filled with a 1 if it was or was adjacent to a 1 in the helper function input, or 0 otherwise.

The basic algorithm is to double the value of every cell of the helper function input, and place a 1 to the left of every maximal-valued cell unless there was already a higher value there. Then we rotate our working value 90 degrees, and repeat a further three times. The values that were 1 in the helper function input will always be the maximal-valued cells (having been doubled more often than the cells we set to 1 during the helper function), so the four iterations set the cells to the left, beneath, to the right, and above them to positive values respectively (and then we're rotated back to the array's original orientation). Once we've done our placing of 1s to the left four times, we simply just maximum with the input to the program as a whole; this sets all the 1s, 2s, 4s, 8s, and 16s to 1, except for cells which were 0 in the program input which are set to 0, implementing the desired behaviour of the helper function.

```
ŒM_Ø.ŒṬ»ḤZUµ4¡«³
ŒM                 Indexes of maximal elements
  _Ø.              Subtract [0, 1] (i.e. the indexes to their left)
     ŒṬ            Create an array with 1s at only those indexes
       »           Take the maximum of that array and
        Ḥ            twice {the working value as of the start of this iteration}
         ZU        Transpose and flip (i.e. rotate 90°)
             ¡     Repeat
           µ         everything in this function so far
            4        4 times
              «    Take the {element-wise} minimum of that and
               ³     the first command-line argument to this program

```

Jelly helpfully handles the edge of the array for us – if `ŒṬ` sees a coordinate before the left edge of the array, it won't add it to the array it's creating. (However, it will nonetheless make use of the coordinate to know how many dimensions the array it's creating is meant to have, avoiding a crash if there are no indexes in range.)

### Main program

Half the code in this is to create an array that's the same shape as the input array, but has a 1 in the top-left corner and 0s everywhere else (i.e. the location we're flood-filling from). Then, we run the helper function repeatedly to flood-fill, and convert the output to the desired format.

```
FJỊṁ³ÇƬ¬S:
F            Flatten the input array
 J           Create a list from 1 to the length {of the flattened array}
  Ị          Map 1 to 1, larger values to 0
   ṁ         Reshape back to the shape of the input
    ³        {no-op, fixes a parsing ambiguity by breaking up ṁÇ}
     Ç       Call the function 1Ŀ
      Ƭ        in a loop, until nothing changes, remember all results
       ¬     Swap 0s and 1s {in the list of outputs of 1Ŀ}
        S    Sum {for each cell, the number of iterations it was 0}
         :   Divide {cells by the corresponding input cell}

```

The basic idea is that a cell that should be 0 in the output has been 0 for no iterations of `1Ŀ` calls; a cell that should be 1 in the output has been 0 for one iteration; a cell that should be 2 in the output has been 0 for two iterations, and so on (i.e. we can use the length of time the one-step floodfills took to reach a particular square to discover its distance from the starting point). So we can just count the number of iterations for which each cell was 0. In order to place non-integers in the cells which are walls in the input (these cells would "naturally" hold the largest value in the output plus 1), it's possible to use division with the input; for non-wall cells, this divides by 1 (a no-op), and for wall cells, this divides by 0 (returning floating-point infinity, which is not a positive integer). (`:` is normally integer division, so it returns an integer in most cases, but it returns floating-point infinity when dividing by 0.)

# Answer
> 3 votes
# JavaScript (Node.js), 114 bytes

Expects a matrix filled with \\$0\\$ and \\$-1\\$.

Outputs by updating the input matrix with 1-indexed distances.

```
f=(m,n=m[0][0]=1)=>m.map(q=(r,y)=>r.map((v,x)=>(h=d=>d+2?v|m[y+d--%2]?.[x+d%2]^n?h(d):r[x]=q=n+1:0)(2)))|q&&f(m,q)

```

Attempt This Online!

### Commented

```
f = (                  // f is a recursive function taking:
  m,                   //   m[] = input matrix
  n =                  //   n = distance counter
  m[0][0] = 1          //   set m[0][0] to 1
) =>                   //
m.map(q =              // initialize q to a zero'ish value
(r, y) =>              // for each row r[] at position y in m[]:
  r.map((v, x) =>      //   for each value v at position x in r[]:
    ( h =              //     h is a recursive function taking
      d =>             //     a direction d
      d + 2 ?          //     if d is not equal to -2:
        v |            //       if v is already set
        m[y + d-- % 2] //       or the neighbor cell
        ?.[x + d % 2]  //       in direction d
        ^ n ?          //       is not equal to n:
          h(d)         //         try again with the next direction
        :              //       else:
          r[x] =       //         update the cell to n + 1
          q = n + 1    //         and set q to a non-zero value
      :                //     else:
        0              //       stop the recursion
    )(2)               //     initial call to h with d = 2
  )                    //   end of inner map()
)                      // end of outer map()
| q && f(m, q)         // if q was set, do a recursive call

```

# Answer
> 3 votes
# Julia

## 97 bytes

```
h(X,r=1,c=1,d=0)=try d<X[r][c]&&(X[r][c]=d
for i=[5,7,1,3] h(X,r+i÷3-1,c+i%3-1,d+1)end)catch;end
```

Attempt This Online!

## 81 bytes

A greatly improved version provided by @MarcMush.

```
h(X,r=1,c=1,d=0)=d<get(X,(r,c),0)&&1:2:7 .|>i->h(X,r+i÷3-1,c+i%3-1,(X[r,c]=d)+1)

```

Attempt This Online!

### representation:

* free slots -\> Inf
* forbidden slots -\> -Inf
* 0-based distance

# Answer
> 3 votes
# Vyxal, 32 bytes

```
k₁w≬ƛ£?ÞT›'¥ε∑ṅ}ÞfU↔‹vÞǔ∑:fGε›*‹

```

Try it Online!

Port of Jonathan Allan's Jelly answer, byte count can certainly be way less.

# Answer
> 2 votes
# Python3, 194 bytes:

```
def f(b):
 q=[(0,0,0)]
 while q:
  (x,y,v),*q=q
  for X,Y in[(0,1),(0,-1),(1,0),(-1,0)]:
   X+=x;Y+=y
   if-1<X<len(b)and-1<Y<len(b[0])and(X|Y)and 0==b[X][Y]:b[X][Y]=v+1;q+=[(X,Y,v+1)]
 return b

```

Try it online!

# Answer
> 1 votes
# Jelly,  ~~25~~  24 bytes

-1 using ais523's trick of using integer division to place `inf` as walls.

```
Ø1Wạ§ỊɗƇⱮẎQɗ@ƬŒMŒṬSFṀ_Ɗ:

```

A monadic Link that accepts the grid with `1` as space and `0` as wall and yields another grid containing the fill distances at spaces and `inf` at walls.

**Try it online!**

### How?

```
Ø1Wạ§ỊɗƇⱮẎQɗ@ƬŒMŒṬSFṀ_Ɗ: - Link: Grid
Ø1                       - literal [1, 1]
  W                      - wrap -> [[1, 1]]
              ŒM         - maximal multidimensional indices of Grid -> space coordinates
             Ƭ           - start with A=[[1, 1]] and collect up while distinct applying:
            @            -   with swapped arguments:
           ɗ             -     last three links as a dyad - f(space coordinates, A):
        Ɱ                -       map (for a in A) with:
       Ƈ                 -         keep those (s in space-cordinates) for which:
      ɗ                  -           last three links as a dyad - f(s, a):
   ạ                     -             absolute difference
    §                    -             sums
     Ị                   -             insignificant? -> is s a neighbour of, or equal to, a?
         Ẏ               -       tighten -> flat list of neighbours
          Q              -       deduplicate
                ŒṬ       - multidimensional grids with 1s at those indices
                  S      - sum -> 0 at walls, 1 at furthest, 2 at next nearest, etc.
                      Ɗ  - last three links as a monad - f(X=that):
                   F     -   flatten
                    Ṁ    -   maximum -> value at top-left
                     _   -   subtract X (vectorises)
                       : - integer divide by the grid -> keeps space values, replaces wall with inf

```

# Answer
> 1 votes
# JavaScript (Node.js), 110 bytes

```
a=>[,...0+a].map((_,i)=>a=a.map((r,y)=>r.map((c,x)=>x+y?c||i*[2,1,0,-1].some(k=>a[y+k%2]?.[x+--k%2]>0):1)))&&a
```

Attempt This Online!

---
Tags: code-golf, array, matrix, path-finding
---