A nonnegative integer n, and a nonempty string s containing only alphanumeric characters and underscores _. The first character of s is not _. The underscores of s are interpreted as blank spaces that can be filled with other characters.

We define an infinite sequence of "infinite strings" as follows. The string s1 = s s s... is just s repeated infinitely many times. For all k > 1, the string sk+1 is obtained from sk by filling its blank spaces with the characters of s1, so that the first _ of sk is replaced with s1[0], the second with s1[1], and so on. Since the first letter of s is not _, every blank space gets filled eventually, and we denote by s the infinite string where every _ has been replaced by its eventual value.


The first n characters of s as a string.


Consider the inputs n = 30 and s = ab_c_. We have

s1 = ab_c_ab_c_ab_c_ab_c_ab_c_ab_c_ab_c_...

Substituting s1 to the blanks of s1, we have

s2 = abacbab_ccab_caabbc_abcc_abacbab_cc...

We again substitute s1 to the blanks, which results in

s3 = abacbabaccabbcaabbc_abcccabacbab_cc...

One more substitution:

s4 = abacbabaccabbcaabbcaabcccabacbabbcc...

From this we can already deduce the first 30 characters of s, which are


This is the correct output.


You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Crashing on incorrect input is acceptable.

Test Cases

0  "ab__"    -> ""
1  "ab__"    -> "a"
3  "ab__"    -> "aba"
20 "ab"      -> "abababababababababab"
20 "ab__"    -> "abababababababababab"
20 "ab_"     -> "abaabbabaabaabbabbab"
30 "ab_c_"   -> "abacbabaccabbcaabbcaabcccabacb"
50 "ab_a_cc" -> "abaabccabaaaccabbacccabcaaccabbaaccabaaaccabcaccca"
50 "abc____" -> "abcabcaabcbcaaabcbcbcabcaaababccbcbabccabcabcaaaba"
  • \$\begingroup\$ Can we take input in the opposite order (in languages where the order matters)? \$\endgroup\$ Feb 2, 2015 at 14:41
  • \$\begingroup\$ @MartinBüttner Sure, I'll allow that. \$\endgroup\$
    – Zgarb
    Feb 2, 2015 at 14:41

15 Answers 15


APL 29 28


it's used like this:

20 fun 'ab_c_'


a←⍺⍴⍵           makes vector long as left argument using repeated chars in right argument
a↑⍨+/b←'_'=a   takes a string from the beginning of string a (a↑⍨), long as the number of _'s in a (+/b←'_'=a)
(b/a)←          puts those chars in place of the _'s in the original vector
a⊣             and returns a
{}⍣≡            repeats function ( {} ) until results doesn't change anymore


  • \$\begingroup\$ ⍣≡ is a nifty idea. Maybe I should try to port this to J... \$\endgroup\$
    – FUZxxl
    Feb 2, 2015 at 18:01

CJam, 26 24 20 bytes

4 bytes saved thanks to Peter.


Test it here. Takes the string first and n second on STDIN.

You can run all test cases by pasting them into the input as they are (include the -> output if you want), and using the following test harness (which reverses the order for the code):





l~                       "Read the input and evaluate.";
  :I                     "Store n in I for future use.";
    *                    "Repeat s n times to ensure it's long enough for the output.";
     {           }I*     "Repeat this block n times. This will always be enough passes.";
      _                  "Duplicate the string.";
       '_/               "Split the string on underscores.";
          [\]            "Swap with the other copy, putting both in an array.";
             z           "Zip the two arrays together, interleaving substrings from the split
                          copy with characters from the unsplit copy. Extraneous
                          characters from the unsplit copy just go at the end and
                          can be ignored.";
              s          "Convert the result into a string, flattening the array in the
                          process. This basically joins the two interleaved strings together.";
               I<        "Truncate to n characters.";

The result is printed automatically at the end of the program.

A note on [\]: In principle, [ remembers the current size of the stack and ] collects everything down to the last remembered size in an array. However, if the array size falls below the remembered size in between, then the start of the array gets adjusted accordingly. Now you might think that swapping the top two array elements doesn't affect the array size at all, but \ actually pops two value and then pushes them in reverse order. This is what pushes the start of the array down by two. Therefore, [\] is the shortest way to wrap the top two stack elements in an array. Sometimes, the side effect of collecting them in reverse order is quite annoying, but in this case, it's exactly what I need.

  • \$\begingroup\$ I think you could replace _'_#) g with I*. Works for me in GolfScript. \$\endgroup\$ Feb 2, 2015 at 17:51
  • \$\begingroup\$ @PeterTaylor oh, very good idea, thanks! \$\endgroup\$ Feb 2, 2015 at 19:23

Python 3, 110 bytes

while"_"in a:b,a=b[:],[x*(x!="_")or b.pop(0)for x in a]

Needs a fair bit more golfing, but here is some sheer insanity. Reads in n then s from STDIN.

The fun part is, in the loop's assignment we copy b, then start popping from b during a list comprehension. If the assignment was the other way around, it wouldn't work!


Pyth, 17


Input should be given with the string on the first line, and the length on the second, on STDIN. For example:


Try it here.


                             z = input()              z is the string.
                             Q = eval(input())        Q is the length.

<               Q            First Q characters of
 u         UQ*zQ             Reduce, with an initial value of z repeated Q times, 
                             on the list range(len(Q)).
                             Since the reduce function doesn't use the sequence variable H
                             this function amounts to applying the inner code Q times to
                             the initial value, where the working variable is G.
  ss                         Sum from list of tuples of strings, to tuple of strings,
                             to string.
    C,                       Zip together
      cG\_                   G split on underscores
          G                  with G.
                             This inserts a character of G between every underscore
                             separated group of G, which amounts to replacing the
                             underscores with characters of G, after summation.

k, 30


Java - 162 174

It's not every day I get to use a do/while loop when golfing in Java :D

This just iterates and fills in blanks as they come. It just keeps going until there are no more _ in the result.

char[]a(int n,char[]s){char[]o=new char[n];if(n>0)do for(int i=0,j=0;i<n;i++)if(o[i]==95|o[i]<1)o[i]=s[j++%s.length];while(new String(o).contains("_"));return o;}

With line breaks:

char[]a(int n,char[]s){
    char[]o=new char[n];
            for(int i=0,j=0;i<n;i++)
        while(new String(o).contains("_"));
    return o;
  • \$\begingroup\$ I wasn't going to answer this, but the other Java answer was too long to let stand ;) \$\endgroup\$
    – Geobits
    Feb 2, 2015 at 17:34

Java 8, 238

(n,s)->{int i=0,j=0;for(s=String.join("",java.util.Collections.nCopies(n,new String(s))).toCharArray();j<1;){for(i=0;i<n;i++){for(;s[++j]!=95&j<n;);if(j<n)s[j]=s[i];}for(j=1,i=0;i<n;)j=s[++i]==95?0:1;}return java.util.Arrays.copyOf(s,n);}

Less golfed:

(Integer n, char[] s) -> {
    int i = 0, j = 0;
    for (s = String.join("", java.util.Collections.nCopies(n, new String(s))).toCharArray(); j < 1;) {
        for (i = 0; i < n; i++) {
            for (; s[j] != 95 & j < n; j++);
            if (j < n) {
                s[j] = s[i];
        for (j = 1, i = 0; i < n;) {
            j = s[++i] == 95 ? 0 : 1;
    return java.util.Arrays.copyOf(s, n);

Ruby, 60


Concatenates s to itself n times, then generates n copies of code that replaces underscores with s, evaluates those copies, and returns the first n characters of the result. Since at least one underscore is removed in each loop, this is guaranteed to give us n underscore-free characters.

  • \$\begingroup\$ What is the right syntax to run this? When I call it f and run puts f[10,"ab_"], I get the following error: in 'eval': undefined method 'next' for #<Array:.... It does seem to work when there are no underscores in the string, though. \$\endgroup\$
    – Théophile
    Feb 3, 2015 at 4:51
  • \$\begingroup\$ Oh, interesting, it looks like the behavior of String#chars changed between Ruby 1.9.3 and Ruby 2.0; in Ruby 1 it returns an enumerator when there's no block, in Ruby 2 an array. It can be made version-insensitive by changing chars to each_char, at the cost of 4 more net bytes of code. \$\endgroup\$
    – histocrat
    Feb 3, 2015 at 13:48

Python 2, 75

for x in s*n:b=x=='_';S+=S[c:c+b]or x;c+=b
print S[:n]

This expects input like (30,"ab_c_").

In Python, strings don't allow assignment. So, replacing the blanks with the desired character is hard. One can get around this by converting to a list and back, but I found it shorter to just generate the output string from scratch, adding on the desired characters one at a time.

The output being constructed is S, which starts empty. We loop through the characters of the input s copied many times to simulate a circle. We check if it's a blank via the Boolean b. We check equality x=='_' rather than comparison because the underscore lies between capital and lowercase letters.

If the character is not a blank, we just add it onto S. If it is blank, we add the next unused letter of the output-so-far S. We track used letters by an index pointer c that starts at 0 and is incremented each time we encounter a blank.

At the end, we print the first n characters of the resulting string S.

We have to use S[c:c+b] in place of the shorter b*S[c] because the latter gives an out-of-bounds error when S starts empty and c is 0. It never matters because we're guaranteed the first character of s is non-blank, so this S[c] is never needed, but the code doesn't know it. Flipping the or to short-circuit could also solve this, but costs more characters.

Python 2, 83

A Pyth-to-Python port of isaacg's solution, which uses split and zip to perform the replacement:

exec"s=''.join(a+b for a,b in zip(s.split('_'),s));"*n
print s[:n]

It turned out longer because, suprise, named methods are long in python. But it can perhaps be improved by riffling s and s.split('_') together in a shorter way.

  • \$\begingroup\$ Nice! Didn't expect reconstructing the string to be so much shorter! \$\endgroup\$
    – Sp3000
    Feb 3, 2015 at 8:51

Haskell (93) 67

I haven't written any Haskell in a while, so this can probably be shortened by a lot. but it was so good, we had to shorten it and make it better!

f n s=take n$q where q=cycle s&q


*Main> f 50 "ab_a_cc"

Batch - 425

Do I lose?

@echo off&setLocal enableDelayedExpansion&set s=%2
if "%3"=="" (for /l %%a in (1,1,%1)do set o=!o!%s%)else set o=%3
set o=!o:~0,%1!&set l=0
if defined s set/al+=1&set "s=%s:~1%"&goto c
set s=%2&set/ap=%1-1
set y=&set c=0&for /l %%a in (0,1,%p%)do set x=!o:~%%a,1!&if !x!==_ (for %%b in (!c!)do set y=!y!!s:~%%b,1!&set/ac+=1)else (set y=!y!!x!)&if !c!==%l% set c=0
if "!y:_=!"=="!y!" echo !y!&goto :EOF
%0 %1 %2 !y!

Batch has limitations - I accept this. For example; I had to use a for loop to get a single variable in a usable format due to limitations of variable parsing syntax. for %%b in (!c!)do... just exists so I can use %%b instead of !c! so I can actually do the string manipulation !s:~%%b,1! and have the variables expand at the correct time.

There are a couple of pretty basic things I could do to golf this further, but probably not below 400 bytes. I'll have another crack soon.

  • 3
    \$\begingroup\$ Unless someone else posts a better Batch answer, I wouldn't call this losing :) \$\endgroup\$
    – Sp3000
    Feb 3, 2015 at 7:35
  • \$\begingroup\$ @Sp3000 If only someone would. \$\endgroup\$
    – unclemeat
    Feb 16, 2015 at 22:10

ECMAScript 6, 78


Starts off with an empty string and for every occurrence of underscore, replaces it with the character at the next index of the current string.


Python 2 - 99 97 bytes

Because 4 python-based submissions aren't enough...

while"_"in S:x=iter(s);S="".join(j>"_"and j or next(x)for j in S)
print S[:n]


$ python2 t.py 
(50, "ab_a_cc")

ECMAScript 6, 93 91

(n,s)=>{for(x="_".repeat(n);n=0,/_/.test(x);)x=x.replace(/_/g,a=>s[n++%s.length]);return x}

Shaved off 2 characters from the first version.

(n,s)=>{x="_".repeat(n);while(/_/.test(x)){n=0,x=x.replace(/_/g,a=>s[n++%s.length])}return x}

C# - 162

I stole Geobits solution and changed it to C#

char[]p(int n,string s){var r=new char[n];if(n>0)do for(int i=0,j=0;i<n;i++)if(r[i]=='_'||r[i]<1)r[i]=s[j++%s.Length];while(r.ToList().IndexOf('_')>=0);return r;}

1 char better, so you can improve Geobits ;)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.