I've recently been indulging myself in some nostalgia in the form of Bookworm Deluxe:

In case you haven't seen it before, it's a word game where the goal is to connect adjacent tiles to form words. In order to determine whether a string is a valid word, it checks it against its internal dictionary, which is stored in a compressed format that looks like this:


The rules for unpacking the dictionary are simple:

  1. Read the number at the start of the line, and copy that many characters from the beginning of the previous word. (If there is no number, copy as many characters as you did last time.)

  2. Append the following letters to the word.

So, our first word is aa, followed by 2h, which means "copy the first two letters of aa and append h," forming aah. Then 3ed becomes aahed, and since the next line doesn't have a number, we copy 3 characters again to form aahing. This process continues throughout the rest of the dictionary. The resulting words from the small sample input are:


Your challenge is to perform this unpacking in as few bytes as possible.

Each line of input will contain zero or more digits 0-9 followed by one or more lowercase letters a-z. You may take input and give output as either a list of strings, or as a single string with words separated by any character other than 0-9/a-z.

Here is another small test case with a few edge cases not covered in the example:

abc cba 1de fg hi 0jkl mno abcdefghijk 10l
=> abc cba cde cfg chi jkl mno abcdefghijk abcdefghijl

You may also test your code on the full dictionary: input, output.

  • \$\begingroup\$ Is there a possibility that there will not be a number in the second line? Also, can we assume that no number except 0 will have leading 0s? \$\endgroup\$ Dec 19, 2018 at 19:43
  • \$\begingroup\$ @EriktheOutgolfer Yes, that is possible; I've added that to the test case. And yes, you can assume that (as well as that the number won't be greater than the length of the previous word). \$\endgroup\$
    – Doorknob
    Dec 19, 2018 at 19:46
  • 11
    \$\begingroup\$ That's a cute compression format :] \$\endgroup\$
    – Poke
    Dec 19, 2018 at 20:19
  • 1
    \$\begingroup\$ The locate program uses this type of encoding on pathnames. \$\endgroup\$
    – Dan D.
    Dec 19, 2018 at 21:24
  • \$\begingroup\$ I wrote this program for my actual use, about 15 years ago. Unfortunately I don't think I have the source anymore... \$\endgroup\$
    – hobbs
    Dec 20, 2018 at 1:24

23 Answers 23


Vim, 57 bytes

:%s/\a/ &
:%norm +hkyiwjP
:g/\d/norm diw-@"yl+P
:%s/ //g

Try it online!


JavaScript (ES6),  66 62  61 bytes


Try it online!


a =>                  // a[] = input, re-used to store the previous word
  a.map(p =           // initialize p to a non-numeric value
  s =>                // for each string s in a[]:
    a =               //   update a:
      a.slice(        //     extract the correct prefix from the previous word:
        [, x, y] =    //       load into x and y:
          /(\d*)(.*)/ //         the result of a regular expression which splits the new
          .exec(s),   //         entry into x = leading digits and y = trailing letters
                      //       this array is interpreted as 0 by slice()
        p = x || p    //       update p to x if x is not an empty string; otherwise leave
                      //       it unchanged; use this as the 2nd parameter of slice()
      )               //     end of slice()
      + y             //     append the new suffix
  )                   // end of map()

brainfuck, 201 bytes


Try it online!

Requires a trailing newline at the end of the input. A version without this requirement is 6 bytes longer:

brainfuck, 207 bytes


Try it online!

Both versions assume all numbers are strictly less than 255.


The tape is laid out as follows:

tempinputcopy 85 0 inputcopy number 1 a 1 a 1 r 1 d 0 w 0 o 0 l 0 f 0 ...

The "number" cell is equal to 0 if no digits are input, and n+1 if the number n is input. Input is taken at the cell marked "85".

,[                     take input and start main loop
 [                     start number input loop
  [-<+>>>+<<]          copy input to tempinputcopy and inputcopy
  >-[---<+>]           put the number 85 in the cell where input was taken
  <[[-<]>>]            test whether input is less than 85; ending position depends on result of comparison
                       (note that digits are 48 through 57 while letters are 97 through 122)
  <[-]>                clean up by zeroing out the cell that didn't already become zero
  >[                   if input was a digit:
   <<,>>               get next input character
   >[-[-<++++++++++>]] multiply current value by 10 and add to current input
   ++++                set number cell to 4 (as part of subtracting 47)
   <[->+<]             add input plus 10*number back to number cell
   -[----->-<]         subtract 51
  <]                   move to cell we would be at if input were a letter
 <]                    move to input cell; this is occupied iff input was a digit

                       part 2: update/output word

 >>>                   move to number cell
 [                     if occupied (number was input):
  [>>]+[-<<]>>         remove existing marker 1s and decrement number cell to true value
  [[>>]+[<<]>>-]       create the correct amount of marker 1s
 +[>>]<[-]             zero out cell containing next letter from previous word
 <[<<]>                return to inputcopy
 [->[>>]<+<[<<]>]      move input copy to next letter cell
 >[>.>]                output word so far
 +[                    do until newline is read:
  >[-]<                zero out letter cell
  ,.                   input and output next letter or newline
  [->+>+<<]            copy to letter cell and following cell
  >>----------         subtract 10 to compare to newline
 <[<<]>-               zero out number cell (which was 1 to make copy loop shorter)
 <<<,                  return to input cell and take input
]                      repeat until end of input

Perl 6, 50 48 bytes

-2 bytes thanks to nwellnhof

{my$l;.map:{$!=S[\d*]=substr $!,0,$l [R||]=~$/}}

Try it online!

A port of Arnauld's solution. Man, that R|| trick was a rollercoaster from 'I think this could be possible', to 'nah, it's impossible', to 'kinda maybe possible' and finally 'aha!'


{my$l;.map:{$!=S[\d*]=substr $!,0,$l [R||]=~$/}}
{                                              }  # Anonymous code block
 my$l;    # Declare the variable $l, which is used for the previous number
      .map:{                                  }  # Map the input list to
            $!=              # $! is used to save the previous word
               S[\d*]=       # Substitute the number for
                      substr $!,0    # A substring of the previous word
                                 ,              # With the length of 
                                           ~$0     # The num if it exists
                                  $l [R||]=        # Otherwise the previous num

The $l [R||]=~$/ part roughly translates to $l= ~$/||+$l but... it has the same amount of bytes :(. Originally, it saved bytes using an anonymous variable so the my$l was gone but that doesn't work since the scope is now the substitution, not the map codeblock. Oh well. Anyways, R is the reverse metaoperator, so it reverses the arguments of ||, so the $l variable ends up being assigned the new number (~$/) if it exists, otherwise itself again.

It could be 47 bytes if Perl 6 didn't throw a kinda redundant compiler error for =~.


Ruby, 49 45 43 bytes


Try it online!


$0=                                         #Previous word, assign the value of
   $_=                                      #Current word, assign the value of
      $0[/.{0#{              }}/]           #Starting substring of $0 of length p which is
               p=$_[/\d+/]||p               #defined as a number in the start of $_ if any 
                                 +$_[/\D+/] #Plus any remaining non-digits in $_

C (gcc), 65 57 55 53 bytes


Try it online!


n;                  /* `n` stores the shared prefix length, implicitly 0 */

b[9];               /* int[] buffer we read into, we need 12+1 bytes for the
                       largest words, this buffer is 9*4=36 bytes */

c=b;                /* if we use `b` in pointer arithmetic it would be an int*,
                       but we want to address individual bytes, so we need to
                       store the address as an integer. */

f() {               /* the unpacking function */

    scanf("%d",&n); /* read the common prefix length, if scanf fails because no
                       new prefix length is given then `n`s value will remain
                       the same, which is exactly what we want!  :-) */

    gets(c+n)       /* read the suffix part, the first `n` characters are the
                       common prefix */

        &&          /* short-circuit, so if the gets fails the next part is not
                       executed */

    f(puts(c));     /* print the word that was extracted and call `f`
                       recursively to handle the next word */

Python 3.6+, 172 195 156 123 122 121 104 bytes

import re
def f(l,n=0,w=""):
 for s in l:t=re.match("\d*",s)[0];n=int(t or n);w=w[:n]+s[len(t):];yield w

Try it online!


I caved, and used Regular Expressions. This saved at least 17 bytes. :


When the string doesn't begin with a digit at all, the length of this string will be 0. This means that:

n=int(t or n)

will be n if t is empty, and int(t) otherwise.


removes the number that the regular expression found from s (if there's no number found, it'll remove 0 characters, leaving s untruncated) and replaces all but the first n characters of the previous word with the current word fragment; and:

yield w

outputs the current word.


Haskell, 82 81 bytes

tail.map concat.scanl p["",""]
p[n,l]a|[(i,r)]<-reads a=[take i$n++l,r]|1<2=[n,a]

Takes and returns a list of strings.

Try it online!

        scanl p["",""]        -- fold function 'p' into the input list starting with
                              -- a list of two empty strings and collect the
                              -- intermediate results in a list
  p [n,l] a                   -- 1st string of the list 'n' is the part taken form the last word
                              -- 2nd string of the list 'l' is the part from the current line
                              -- 'a' is the code from the next line
     |[(i,r)]<-reads a        -- if 'a' can be parsed as an integer 'i' and a string 'r'
       =[take i$n++l,r]       -- go on with the first 'i' chars from the last line (-> 'n' and 'l' concatenated) and the new ending 'r'
     |1<2                     -- if parsing is not possible
       =[n,a]                 -- go on with the previous beginning of the word 'n' and the new end 'a'
                              -- e.g. [         "aa",     "2h",      "3ed",       "ing"       ] 
                              -- ->   [["",""],["","aa"],["aa","h"],["aah","ed"],["aah","ing"]]
  map concat                  -- concatenate each sublist
tail                          -- drop first element. 'scanl' saves the initial value in the list of intermediate results. 

Edit: -1 byte thanks to @Nitrodon.

  • 1
    \$\begingroup\$ Contrary to usual Haskell golfing wisdom, you can actually save one byte here by not defining the helper function as an infix operator. \$\endgroup\$
    – Nitrodon
    Dec 23, 2018 at 4:46
  • \$\begingroup\$ @Nitrodon: well spotted! Thanks! \$\endgroup\$
    – nimi
    Dec 23, 2018 at 10:07

Japt, 19 18 17 bytes

Initially inspired by Arnauld's JS solution.

;£=¯V=XkB ªV +XoB

Try it

                      :Implicit input of string array U
 £                    :Map each X
   ¯                  :  Slice U to index
      Xk              :    Remove from X
;       B             :     The lowercase alphabet (leaving only the digits or an empty string, which is falsey)
          ªV          :    Logical OR with V (initially 0)
    V=                :    Assign the result to V for the next iteration
             +        :  Append
              Xo      :  Remove everything from X, except
;               B     :   The lowercase alphabet
  =                   :  Reassign the resulting string to U for the next iteration

Jelly, 16 bytes


Try it online!

How it works

⁹fØDVo©®⁸ḣ;ḟØDµ\  Main link. Argument: A (array of strings)

              µ\  Cumulatively reduce A by the link to the left.
⁹                     Yield the right argument.
  ØD                  Yield "0123456789".
 f                    Filter; keep only digits.
    V                 Eval the result. An empty string yields 0.
     o©               Perform logical OR and copy the result to the register.
       ®              Yield the value in the register (initially 0).
        ⁸ḣ            Head; keep that many character of the left argument.
          ;           Concatenate the result and the right argument.
            ØD        Yield "0123456789".
           ḟ          Filterfalse; keep only non-digits.

Groovy, 74 bytes

{w="";d=0;it.replaceAll(/(\d*)(.+)/){d=(it[1]?:d)as int;w=w[0..<d]+it[2]}}

Try it online!


{                                                                        }  Closure, sole argument = it
 w="";d=0;                                                                  Initialize variables
          it.replaceAll(/(\d*)(.+)/){                                   }   Replace every line (since this matches every line) and implicitly return. Loop variable is again it
                                     d=(it[1]?:d)as int;                    If a number is matched, set d to the number as an integer, else keep the value
                                                        w=w[0..<d]+it[2]    Set w to the first d characters of w, plus the matched string

Python 2, 118 bytes

import re
print o
for i in l:(N,x),=re.findall('(\d*)(.+)',i);n=int(N or n);o=o[:n]+x;print o

Try it online!


Retina 0.8.2, 69 bytes


Try it online! Link includes harder test cases. Explanation:


For all lines that begin with letters, copy the number from the previous line, looping until all lines begin with a number.


Convert the number to unary.


Use balancing groups to replace all 1s with the corresponding letter from the previous line. (This turns out to be slightly golfier than replacing all runs of 1s.)


Red, 143 bytes

func[b][a: charset[#"a"-#"z"]u: b/1 n: 0 foreach c b[parse c[copy m to a
p: copy s to end(if p<> c[n: do m]print u: rejoin[copy/part u n s])]]]

Try it online!


Perl 5 -p, 45 41 bytes


Try it online!


s:\d*:substr($p,0,$l=$&+$l*/^\D/):e;$p=$_ Full program, implicit input
s:   :                           :e;      Replace
  \d*                                       Any number of digits
      substr($p,0,              )           By a prefix of $p (previous result or "")
                  $l=  +                      With a length (assigned to $l) of the sum
                     $&                         of the matched digits
                          *                     and the product
                        $l                        of $l (previous length or 0)
                           /^\D/                  and whether there is no number in the beginning (1 or 0)
                                                (product is $l if no number)
                                    $p=$_ Assign output to $p
                                          Implicit output
  • \$\begingroup\$ This can be shorted by removing the parentheses in the substr clause. \$\endgroup\$
    – Xcali
    Jan 20, 2021 at 2:29

Java (JDK), 150 bytes

a->{String p="",s[];for(int n=0,i=0;i<a.length;a[i]=p=p.substring(0,n=s.length<1?n:new Short(s[0]))+a[i++].replaceAll("\\d",""))s=a[i].split("\\D+");}

Try it online!


Scala, 226 129 102 bytes

Thanks @ASCII-only for their work here (and for the Groovy answer).

s map(_ match{case r(a,b)=>{if(a>"")d=a.toInt

Try it online!

  • \$\begingroup\$ :| both links are the same \$\endgroup\$
    – ASCII-only
    Dec 31, 2018 at 6:17
  • \$\begingroup\$ yeah, editing. I didn't know how to turn it out and was in a hurry so I did not modify what I did. \$\endgroup\$ Dec 31, 2018 at 6:21
  • \$\begingroup\$ 130 \$\endgroup\$
    – ASCII-only
    Dec 31, 2018 at 8:27
  • \$\begingroup\$ 129 \$\endgroup\$
    – ASCII-only
    Dec 31, 2018 at 8:35
  • \$\begingroup\$ 127 \$\endgroup\$
    – ASCII-only
    Dec 31, 2018 at 23:34

05AB1E, 20 19 17 16 bytes


Try it online or verify all test cases.


õ               # Push an empty string ""
 U              # Pop and store it in variable `X`
v               # Loop `y` over the (implicit) input-list:
 yþ             #  Push `y`, and leave only the digits (let's call it `n`)
   Ddi  }       #  If it's a non-negative integer (thus NOT an empty string ""):
      £         #   Pop and push the first `n` characters of the string
       U        #   Pop and store it in variable `X`
         X      #  Push variable `X`
          yá    #  Push `y`, and leave only the letters
            «   #  Merge them together
             =  #  Print it with trailing newline (without popping)

Jelly, 27 bytes


Try it online!


Groovy, 103 99 bytes

{w=it[0];d=0;it.collect{m=it=~/(\d+)(.+)/;i=m.find()?{d=m[0][1] as int;m[0][2]}():it;w=w[0..<d]+i}}

Try it online!

  • \$\begingroup\$ 76? \$\endgroup\$
    – ASCII-only
    Dec 31, 2018 at 1:48
  • 1
    \$\begingroup\$ 74? \$\endgroup\$
    – ASCII-only
    Dec 31, 2018 at 1:48

Common Lisp, 181 bytes

(do(w(p 0))((not(setf g(read-line t()))))(multiple-value-bind(a b)(parse-integer g :junk-allowed t)(setf p(or a p)w(concatenate'string(subseq w 0 p)(subseq g b)))(format t"~a~%"w)))

Try it online!


(do (w (p 0))   ; w previous word, p previous integer prefix (initialized to 0)
    ((not (setf g (read-line t ()))))   ; read a line into new variable g
                                        ; and if null terminate: 
  (multiple-value-bind (a b)            ; let a, b the current integer prefix
      (parse-integer g :junk-allowed t) ; and the position after the prefix
    (setf p (or a p)                    ; set p to a (if nil (no numeric prefix) to 0)
          w (concatenate 'string        ; set w to the concatenation of prefix
             (subseq w 0 p)             ; characters from the previous word 
             (subseq g b)))             ; and the rest of the current line
    (format t"~a~%"w)))                 ; print the current word

As usual, the long identifers of Common Lisp make it non particularly suitable for PPCG.


Python 2, 101 100 99 bytes

import re
for t in input():(m,w),=re.findall('(\d*)(.+)',t);n=m or n;s=s[:int(n)]+w;print s

Try it online!


C# (Visual C# Interactive Compiler), 134 bytes

a=>{int l=0,m,n;var p="";return a.Select(s=>{for(m=n=0;s[m]<58;n=n*10+s[m++]-48);return p=p.Substring(0,l=m>0?n:l)+s.Substring(m);});}

Try it online!

-9 bytes thanks to @ASCIIOnly!

Less golfed...

// a is an input list of strings
  // l: last prefix length
  // m: current number of digits
  // n: current prefix length
  int l=0,m,n;
  // previous word
  var p="";
  // run a LINQ select against the input
  // s is the current word
  return a.Select(s=>{
    // nibble digits from start of the
    // current word to build up the
    // current prefix length
    // append the prefix from the
    // previous word to the current
    // word and capture values
    // for the next iteration
  • \$\begingroup\$ 134? \$\endgroup\$
    – ASCII-only
    Dec 30, 2018 at 10:55
  • \$\begingroup\$ That's pretty cool :) I changed l=n>0?n:l to l=m>0?n:l because it wasn't picking up the case when a line started with zero (0jkl). Thanks for the tip! \$\endgroup\$
    – dana
    Dec 30, 2018 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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