8
\$\begingroup\$

A common optimization to save space in binaries is to merge string literals where one literal is the suffix of another. For instance, a binary with the string literals

a: foobar
b: bar
c: barbaz
d: foobarbaz
e: baz

might contain the following string literal pool (# representing the \0-terminator):

foobar#foobarbaz#

with the symbols a, b, c, and d having the following values relative to the beginning of the string pool:

a:  0
b:  3
c: 10
d:  7
e: 13

In this task, you have to compute the minimal size of a string pool for a given set of input strings.

Input

The input is a series of up to 999 strings each comprising up to 80 ASCII characters (not including the newline) in the range from 32 to 127 inclusive and then a single newline character.

Output

Find the shortest string such that each of the input strings (including the terminating newlines) are substrings of that string. The output shall be the length of that shortest string. Do not output the string, only its length.

Scoring

This challenge is code golf, standard loopholes apply. The solution with the least length in octets wins.

Examples

  1. Input:

    foobar
    bar
    barbaz
    foobarbaz
    baz
    

    shortest string, # representing newline:

    foobar#foobarbaz#
    

    length: 17

  2. Input:

    foobar
    foobaz
    foobarbaz
    barbaz
    

    shortest string, # representing newline:

    foobar#foobaz#foobarbaz#
    

    length: 24

\$\endgroup\$
4
  • 1
    \$\begingroup\$ And 80-character test case would be good. Also, is there any difference between "octet" and "byte"? Otherwise I'm not sure what the benefit of using the obscurer term is. \$\endgroup\$ Commented Jun 9, 2015 at 22:44
  • 1
    \$\begingroup\$ @MartinBüttner On some machines, a byte has more or less than 8 bits (cf. Knuth's MIX). Octet is the standard word to refer to an 8 bit quantity, byte refers to the least addressable unit of the particular machine you're working on. The 80 character limit is just there so people can work with fixed arrays and so I can't say “this is invalid because it breaks with very long input.” \$\endgroup\$
    – FUZxxl
    Commented Jun 9, 2015 at 22:46
  • 1
    \$\begingroup\$ Are all input strings pairwise distinct? \$\endgroup\$ Commented Jun 10, 2015 at 2:25
  • \$\begingroup\$ @AlexeyBurdin No. \$\endgroup\$
    – FUZxxl
    Commented Jun 10, 2015 at 8:42

4 Answers 4

4
\$\begingroup\$

Pyth, 20 18 bytes

hljb-{.zsmteM./d.z

Demonstration.

{ can be removed if duplicates are not allowed.

Explanation:

hljb-{.zsmteM./d.z
                .z     The input, as a list of strings.
         m             Map each strings to
             ./d       all possible partitions of the string into separate strings.
           eM          take the last element of each, giving all suffixes.
          t            Remove the first suffix, giving all suffixes other than
                       the string itself.
        s              Sum, combining the list of lists into a single list.
    -{.z               From the set of input strings, remove all suffixes.
                       This is the list of strings in the minimal segment.
  jb                   Join the strings together on newlines.
 l                     Take the length of the resulting string.
h                      Add one and print.
\$\endgroup\$
3
\$\begingroup\$

CJam, 22 bytes

qN%_&Nf+:G{Gs\/,3<},s,

Try it online.

How it works

qN%   e# Split the input from STDIN at linefeeds, discarding the last, empty chunk.
_&    e# Intersect the array with itself to remove duplicates.
Nf+   e# Append a linefeed to each chunk.
:G    e# Save the result in G.
{     e# Filter; for each chunk in G:
  Gs  e#   Flatten the array of strings G.
  \/  e#   Split at occurrences of G.
  ,3< e#   Compare the resulting number of chunks with 3.
},    e#   Keep the chunk iff the comparision pushed 1 (true).
s,    e# Flatten the resulting array of strings and push the result's length.
\$\endgroup\$
1
\$\begingroup\$

python 2, 132

Just to start a race:

def f(s):
    l=set(s.split('\n'))
    for x in l:
        for y in l:
            if x!=y and x.endswith(y):l.remove(y)
    return sum(len(x)+1 for x in l)

It works:

>>> f(r'''foobar
foobaz
foobarbaz
barbaz''')
24
>>> f(r'''foobar
bar
barbaz
foobarbaz
baz
''')
17
\$\endgroup\$
1
\$\begingroup\$

Haskell, 101 85 bytes

import Data.List
length.unlines.(\l->[x|x<-nub l,x`notElem`((tails.tail)=<<l)]).lines

A function without a name. Usage example:

*Main>  length.unlines.(\l->[x|x<-nub l,x`notElem`((tails.tail)=<<l)]).lines $ "foobar\nbar\nfoobaz"
14

How it works: split input string at newlines. Remove duplicates from the word list l. Keep a word x from the remaining list if it's not in the list of all tails of the words of l. Join those x with newlines in-between (and at the end!) to a single string and count it's length.

\$\endgroup\$

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.