Fill In the Blanks

Question

Input

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.

Output

The first n characters of s∞ as a string.

Example

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

abacbabaccabbcaabbcaabcccabacb

This is the correct output.

Rules

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"

Answer 1

Pyth, 17

<ussC,cG\_GUQ*zQQ

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

abc____
50

Try it here.

Explanation:

                             Implicit:
                             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.

Answer 2

CJam, 26 24 20 bytes

4 bytes saved thanks to Peter.

l~:I*{_'_/[\]zsI<}I*

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):

qN/{"->"/0=S/W%S*

~:I*{_'_/[\]zsI<}I*

]oNo}/

Explanation

l~:I*{_'_/[\]zsI<}I*
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.

Answer 3

APL 29 28

{a⊣(b/a)←a↑⍨+/b←'_'=a←⍺⍴⍵}⍣≡

it's used like this:

fun←{a⊣(b/a)←a↑⍨+/b←'_'=a←⍺⍴⍵}⍣≡
20 fun 'ab_c_'
abacbabaccabbcaabbca

Explanation:

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

Tryapl.org

Answer 4

Python 3, 110 bytes

n=int(input())
*b,=input()*n
a=b[:n]
while"_"in a:b,a=b[:],[x*(x!="_")or b.pop(0)for x in a]
print("".join(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!

Answer 5

k, 30

{{@[x;i;:;(#i:&"_"=x)#x]}/x#y}

Answer 6

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];
    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;
}

Answer 7

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);
}

Answer 8

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!

('_':b)&(d:e)=d:b&e;(a:b)&c=a:b&c
f n s=take n$q where q=cycle s&q

Usage:

*Main> f 50 "ab_a_cc"
"abaabccabaaaccabbacccabcaaccabbaaccabaaaccabcaccca"

Answer 9

Ruby, 60

->n,s{eval"r=%1$p.chars;s.gsub!(?_){r.next};"*n%s*=n;s[0,n]}

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.

Answer 10

Python 2, 75

n,s=input()
S='';c=0
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:

n,s=input()
s*=n
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.

Answer 11

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
:c
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.

Answer 12

ECMAScript 6, 78

f=(s,n,i=0)=>[...s.repeat(n)].reduce((s,x)=>s+(x=='_'?s[i++]:x),'').slice(0,n)

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.

Answer 13

Python 2 - 99 97 bytes

---

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

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

Example:

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

Answer 14

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}

Answer 15

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 ;)