Uma palavra composta é uma palavra que contém 2 ou mais palavras. Podemos fazer melhor que isso, no entanto. Precisamos que você crie 1 palavra (sem sentido) que contenha todas as palavras .

No entanto, queremos que essa palavra seja o mais curta possível. Podemos usar letras sobrepostas para conseguir isso.

Por exemplo, se sua lista de palavras fosse ["cat", "atom", "a"], você desejaria retornar "catom".

Entrada / Saída

Seu programa precisará pegar uma lista de palavras como entrada e retornar uma palavra composta como saída.

A lista de palavras que você usará são as 10000 palavras mais importantes em inglês, de acordo com o Google (se essa lista for muito fácil, posso alterá-la para uma mais longa). Para referência, basta adicionar cada palavra para obter uma pontuação de 65888.

Sua pontuação é o número de letras em sua palavra final, quanto menor, melhor. O desempatador vai para o primeiro pôster.

C ++, comprimento da palavra final: 38272

(a versão otimizada levou cerca de 20 minutos)

#include <iostream>
#include <string>
#include <vector>

std::size_t calcOverlap(const std::string &a, const std::string &b, std::size_t limit, std::size_t minimal) {
    std::size_t la = a.size();
    for(std::size_t p = std::min(std::min(la, b.size()), limit + 1); -- p > minimal; ) {
        if(a.compare(la - p, p, b, 0, p) == 0) {
            return p;
        }
    }
    return 0;
}

int main() {
    std::vector<std::string> words;

    // Load all words from input
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
    }

    std::cerr
        << "Input word count: " << words.size() << std::endl;

    // Remove all fully subsumed words

    for(auto p = words.begin(); p != words.end(); ) {
        bool subsumed = false;
        for(auto i = words.begin(); i != words.end(); ++ i) {
            if(i == p) {
                continue;
            }
            if(i->find(*p) != std::string::npos) {
                subsumed = true;
                break;
            }
        }
        if(subsumed) {
            p = words.erase(p);
        } else {
            ++ p;
        }
    }

    std::cerr
        << "After subsuming checks: " << words.size()
        << std::endl;

    // Sort words longest-to-shortest (not necessary but doesn't hurt. Makes finding maxlen a tiny bit easier)
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t maxlen = words.front().size();

    // Repeatedly combine most-compatible words until there is only one left
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 1) {
        auto bestA = words.begin();
        auto bestB = -- words.end();
        std::size_t bestOverlap = 0;
        for(auto p = ++ words.begin(), e = words.end(); p != e; ++ p) {
            if(p->size() - 1 <= bestOverlap) {
                continue;
            }
            for(auto q = words.begin(); q != p; ++ q) {
                std::size_t overlap = calcOverlap(*p, *q, bestPossible, bestOverlap);
                if(overlap > bestOverlap) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        std::string newStr = std::move(*bestA);
        newStr.append(*bestB, bestOverlap, std::string::npos);

        if(bestA == -- words.end()) {
            words.pop_back();
            *bestB = std::move(words.back());
            words.pop_back();
        } else {
            *bestB = std::move(words.back());
            words.pop_back();
            *bestA = std::move(words.back());
            words.pop_back();
        }

        // Remove any words which are now in the result
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos) {
                std::cerr << "Now subsumes: " << *p << std::endl;
                p = words.erase(p);
            } else {
                ++ p;
            }
        }

        std::cerr
            << "Words remaining: " << (words.size() + 1)
            << " Latest combination: (" << bestOverlap << ") " << newStr
            << std::endl;

        words.push_back(std::move(newStr));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

    std::string result = words.front();

    std::cout
        << result
        << std::endl;
    std::cerr
        << "Word size: " << result.size()
        << std::endl;
    return 0;
}

Base única de verificação:

cat commonwords.txt | while read p; do grep "$p" merged.txt >/dev/null || echo "Not found: $p"; done

Também produziu algumas palavras muito legais em andamento. Aqui estão alguns dos meus favoritos:

• ontem (nostalgia sintética)
• afghanistanbul (algo [insira um político que você não gosta] diria)
• togethernet (a internet amigável)
• elephantom (um grande fantasma)
• thundergroundwaterproofproof (como em "Não sei por que eles sentiram a necessidade de torná-lo thundergroundwaterproof, mas isso está me deixando nervoso")

E:

• codescribingo (talvez um próximo desafio neste site?)

A saída final está em pastebin aqui: http://pastebin.com/j3qYb65b

C ++ 11, 38272 letras, comprovadamente ideal

Esse algoritmo é garantido para fornecer um limite inferior à solução. Nesse caso, ele é capaz de atingir o limite inferior e gerar uma solução ótima de 38272 letras. (Isso corresponde à solução encontrada pelo algoritmo ganancioso de Dave. Fiquei surpreso e um pouco decepcionado ao descobrir que é o ideal, mas aqui estamos.)

Ele funciona resolvendo o problema de fluxo de custo mínimo na rede criada da seguinte maneira.

• Primeiro, quaisquer palavras contidas em outras palavras são redundantes; descarte-os.
• Para cada palavra w , desenhe dois nós w _0 e w _1, onde w _0 é uma fonte com capacidade 1 e w _1 é um coletor com capacidade 1.
• Para cada prefixo (estrito) ou sufixo a de qualquer palavra, desenhe um nó a .
• Para cada sufixo a de w , desenhe um arco de w _0 a a com capacidade 1 e custo 0.
• Para cada prefixo a de w , desenhe um arco de a a w _1 com capacidade 1 e custo de comprimento ( w ) - comprimento ( a ).

Qualquer cadeia de comprimento n que contenha cada palavra pode ser convertida em um fluxo nessa rede com custo no máximo n . Portanto, o fluxo de custo mínimo nessa rede é um limite mais baixo no comprimento da string mais curta.

Se tivermos sorte - e, neste caso, tivermos -, depois de redirecionarmos o fluxo que entra em w _1 de w _0, encontraremos um fluxo ideal que tem apenas um componente conectado e que passa pelo nó para o vazio corda. Nesse caso, ele conterá um circuito euleriano que começa e termina aí. Esse circuito euleriano pode ser lido de volta como uma sequência de comprimento ideal.

Se não tivermos sorte, adicione alguns arcos extras entre a cadeia vazia e as cadeias mais curtas nos outros componentes conectados para garantir a existência de um circuito euleriano. A cadeia de caracteres não seria mais necessariamente ideal nesse caso.

Eu uso a biblioteca LEMON para seus algoritmos de fluxo de custo mínimo e de circuito euleriano. (Esta foi a primeira vez que eu usei essa biblioteca e fiquei impressionado - eu definitivamente a utilizarei novamente para futuras necessidades de algoritmos gráficos.) O LEMON vem com quatro algoritmos diferentes de fluxo de custo mínimo; você pode experimentá-los aqui com --net, --cost, --cap, e --cycle(default).

O programa é executado em 0,5 segundos , produzindo essa sequência de saída .

#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <lemon/core.h>
#include <lemon/connectivity.h>
#include <lemon/euler.h>
#include <lemon/maps.h>
#include <lemon/list_graph.h>
#include <lemon/network_simplex.h>
#include <lemon/cost_scaling.h>
#include <lemon/capacity_scaling.h>
#include <lemon/cycle_canceling.h>

using namespace std;

typedef lemon::ListDigraph G;

struct Word {
    G::Node suffix, prefix;
    G::Node tour_node;
};

struct Edge {
    unordered_map<string, Word>::iterator w;
    G::Arc arc;
};

struct Affix {
    vector<Edge> suffix, prefix;
    G::Node node;
    G::Node tour_node;
};

template<class MCF>
bool solve(const G &net, const G::ArcMap<int> &lowerMap, const G::ArcMap<int> &upperMap, const G::ArcMap<int> &costMap, const G::NodeMap<int> &supplyMap, int &totalCost, G::ArcMap<int> &flowMap)
{
    MCF mcf(net);
    if (mcf.lowerMap(lowerMap).upperMap(upperMap).costMap(costMap).supplyMap(supplyMap).run() != mcf.OPTIMAL)
        return false;
    totalCost = mcf.totalCost();
    mcf.flowMap(flowMap);
    return true;
}

int main(int argc, char **argv)
{
    clog << "Reading dictionary from stdin" << endl;
    unordered_map<string, Affix> affixes;
    unordered_map<string, Word> words;
    unordered_set<string> subwords;
    G net, tour;
    G::ArcMap<int> lowerMap(net), upperMap(net), costMap(net);
    G::NodeMap<int> supplyMap(net);
    string new_word;
    while (getline(cin, new_word)) {
        if (subwords.find(new_word) != subwords.end())
            continue;
        for (auto i = new_word.begin(); i != new_word.end(); ++i) {
            for (auto j = new_word.end(); j != i; --j) {
                string s(i, j);
                words.erase(s);
                subwords.insert(s);
            }
        }
        words.emplace(new_word, Word());
    }
    for (auto w = words.begin(); w != words.end(); ++w) {
        w->second.suffix = net.addNode();
        supplyMap.set(w->second.suffix, 1);
        w->second.prefix = net.addNode();
        supplyMap.set(w->second.prefix, -1);
        for (auto i = w->first.begin(); ; ++i) {
            affixes.emplace(string(w->first.begin(), i), Affix()).first->second.prefix.push_back(Edge {w});
            affixes.emplace(string(i, w->first.end()), Affix()).first->second.suffix.push_back(Edge {w});
            if (i == w->first.end())
                break;
        }
        w->second.tour_node = tour.addNode();
    }
    for (auto a = affixes.begin(); a != affixes.end();) {
        if (a->second.suffix.empty() || a->second.prefix.empty() ||
            (a->second.suffix.size() == 1 && a->second.prefix.size() == 1 &&
             a->second.suffix.begin()->w == a->second.prefix.begin()->w)) {
            affixes.erase(a++);
        } else {
            a->second.node = net.addNode();
            supplyMap.set(a->second.node, 0);
            for (auto &e : a->second.suffix) {
                e.arc = net.addArc(e.w->second.suffix, a->second.node);
                lowerMap.set(e.arc, 0);
                upperMap.set(e.arc, 1);
                costMap.set(e.arc, 0);
            }
            for (auto &e : a->second.prefix) {
                e.arc = net.addArc(a->second.node, e.w->second.prefix);
                lowerMap.set(e.arc, 0);
                upperMap.set(e.arc, 1);
                costMap.set(e.arc, e.w->first.length() - a->first.length());
            }
            a->second.tour_node = lemon::INVALID;
            ++a;
        }
    }

    clog << "Read " << words.size() << " words and found " << affixes.size() << " affixes; ";
    clog << "created network with " << countNodes(net) << " nodes and " << countArcs(net) << " arcs" << endl;

    int totalCost;
    G::ArcMap<int> flowMap(net);
    bool solved;
    if (argc > 1 && string(argv[1]) == "--net") {
        clog << "Using network simplex algorithm" << endl;
        solved = solve<lemon::NetworkSimplex<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if (argc > 1 && string(argv[1]) == "--cost") {
        clog << "Using cost scaling algorithm" << endl;
        solved = solve<lemon::CostScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if (argc > 1 && string(argv[1]) == "--cap") {
        clog << "Using capacity scaling algorithm" << endl;
        solved = solve<lemon::CapacityScaling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    } else if ((argc > 1 && string(argv[1]) == "--cycle") || true) {
        clog << "Using cycle canceling algorithm" << endl;
        solved = solve<lemon::CycleCanceling<G>>(net, lowerMap, upperMap, costMap, supplyMap, totalCost, flowMap);
    }

    if (!solved) {
        clog << "error: no solution found" << endl;
        return 1;
    }
    clog << "Lower bound: " << totalCost << endl;

    G::ArcMap<string> arcLabel(tour);
    G::Node empty = tour.addNode();
    affixes.find("")->second.tour_node = empty;
    for (auto &a : affixes) {
        for (auto &e : a.second.suffix) {
            if (flowMap[e.arc]) {
                if (a.second.tour_node == lemon::INVALID)
                    a.second.tour_node = tour.addNode();
                arcLabel.set(tour.addArc(e.w->second.tour_node, a.second.tour_node), "");
            }
        }
        for (auto &e : a.second.prefix) {
            if (flowMap[e.arc]) {
                if (a.second.tour_node == lemon::INVALID)
                    a.second.tour_node = tour.addNode();
                arcLabel.set(tour.addArc(a.second.tour_node, e.w->second.tour_node), e.w->first.substr(a.first.length()));
            }
        }
    }

    clog << "Created tour graph with " << countNodes(tour) << " nodes and " << countArcs(tour) << " arcs" << endl;

    G::NodeMap<int> compMap(tour);
    int components = lemon::stronglyConnectedComponents(tour, compMap);
    if (components != 1) {
        vector<unordered_map<string, Affix>::iterator> breaks(components, affixes.end());
        for (auto a = affixes.begin(); a != affixes.end(); ++a) {
            if (a->second.tour_node == lemon::INVALID)
                continue;
            int c = compMap[a->second.tour_node];
            if (c == compMap[empty])
                continue;
            auto &b = breaks[compMap[a->second.tour_node]];
            if (b == affixes.end() || b->first.length() > a->first.length())
                b = a;
        }
        int offset = 0;
        for (auto &b : breaks) {
            if (b != affixes.end()) {
                arcLabel.set(tour.addArc(empty, b->second.tour_node), b->first);
                arcLabel.set(tour.addArc(b->second.tour_node, empty), "");
                offset += b->first.length();
            }
        }
        clog << "warning: Found " << components << " components; solution may be suboptimal by up to " << offset << " letters" << endl;
    }

    if (!lemon::eulerian(tour)) {
        clog << "error: failed to make tour graph Eulerian" << endl;
        return 1;
    }

    for (lemon::DiEulerIt<G> e(tour, empty); e != lemon::INVALID; ++e)
        cout << arcLabel[e];
    cout << endl;

    return 0;
}

Java 8, ~ 5 minutos, comprimento de 39.279

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;

public class Words {

    public static void main(String[] args) throws Throwable {
        File file = new File("words.txt");
        List<String> wordsList = new ArrayList<>();
        BufferedReader reader = new BufferedReader(new FileReader(file));
        String line;
        while ((line = reader.readLine()) != null) {
            wordsList.add(line);
        }
        reader.close();

        Set<String> words = new HashSet<>();

        System.out.println("Finished I/O");

        for (int i = 0; i < wordsList.size(); i++) { //Step 1: remove any words that occur in other words
            boolean in = false;
            for (int j = 0; j < wordsList.size(); j++) {
                if (i != j && wordsList.get(j).contains(wordsList.get(i))) {
                    in = true;
                    break;
                }
            }
            if (!in) {
                words.add(wordsList.get(i));
            }
        }

        System.out.println("Removed direct containers");

        List<String> working = words.stream().sorted((c, b) -> Integer.compare(c.length(), b.length())).collect(Collectors.toList()); //Sort by length, shortest first
        StringBuilder result = new StringBuilder();
        result.append(working.get(0));
        while (!working.isEmpty()) {
            Optional<String> target = working.stream().sorted((c, b) -> Integer.compare(firstLastCommonality(result.toString(), b), firstLastCommonality(result.toString(), c))).findFirst(); //Find the string that has the greatest in common with the end of 'result'
            if(target.isPresent()) { //It really should be present, but just in case
                String s = target.get();
                working.remove(s);
                int commonality = firstLastCommonality(result.toString(), s);
                s = s.substring(commonality);
                result.append(s);
            }
        }

        System.out.println("Finished algorithm");

        String r = result.toString();
        System.out.println("The string: \n" + r);
        System.out.println("Length: \n" + r.length());
        System.out.println("Verified: \n" + !wordsList.stream().filter(s -> !r.contains(s)).findFirst().isPresent());
    }

    private static int firstLastCommonality(String a, String b) {
        int count = 0;
        int len = b.length();
        while (!a.endsWith(b) && !b.equals("")) {
            b = cutLastChar(b);
            count++;
        }
        return len - count;
    }

    private static String cutLastChar(String string) {
        if (string.length() - 1 < 0) {
            return string;
        } else {
            return string.substring(0, string.length() - 1);
        }
    }

}

Entrada:

• um arquivo chamado 'words.txt' no diretório de trabalho, exatamente no mesmo formato do arquivo na postagem principal

Saída:

Finished I/O
Removed direct containers
Finished algorithm
The string: 
[Moved to pastebin](http://pastebin.com/iygyR3zL)
Length: 
39279
Verified: 
true

Python 2, 39254 caracteres

Leva de 1 a 2 minutos para rodar na minha máquina, funciona usando a palavra mais longa e sempre adicionando a palavra à sequência de resultados que possui mais sequências em comum. (Antes disso, todas as palavras que são substrings de outras palavras são removidas para evitar a adição desnecessária à string.)

Atualização: tentei olhar nas duas direções, mas isso não melhora. (talvez esteja usando palavras que possam ser usadas melhor mais tarde?)

Link para a palavra em pastebin.

100 primeiros caracteres:

telecommunicationsawayneillegallynnbabyenbcjrxltdxmlbsrcwvtxxxboxespnycdsriconsentencessexyrsslipodc

Código:

import re
import urllib

def suffix_dist(w1,w2):
    for i in range(min(map(len,[w1,w2])))[::-1]:
        if w1[-i:]==w2[:i]:
            return i
    return 0

url="https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt"
s=urllib.urlopen(url).read()
words=s.split()
words.sort(key=len,reverse=True)

## remove words that are substrings of other words anyway
for i in range(len(words))[::-1]:
    if any(words[i] in w for w in words[:i]):
        words.pop(i)

print len(words)

words.sort(key=len)
w1=words.pop(-1)
result=w1
while words:
    ## get the word with longest shared suffix/prefix
    w2=max(words,key=lambda x:suffix_dist(w1,x))
    print w2
    words.pop(words.index(w2))
    if w2 in result:
        break
    result+=w2[suffix_dist(w1,w2):]
    w1=w2


print result[:100]
print len(result)
print "Test:", all(w in result for w in s.split())

Ruby, 39222 caracteres

Usa uma abordagem semelhante ao @KarlKastor em sua resposta em Python, mas a string inicial é uma das menores palavras em vez das maiores. Outra otimização (não sei o quanto isso ajuda) é que, entre cada adição, remove todas as palavras que já possam ter sido incluídas na string devido a sobreposição de palavras.

É executado em pouco mais de 4 minutos na minha máquina, sem contar a solicitação da Web para recuperar a lista de palavras, mas não com as 4:20.

A palavra em Pastebin.

require 'net/http'

puts "Obtaining word list..."
data = Net::HTTP.get(URI'https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt')
puts "Word list obtained!"

puts "Starting calculation..."
time = Time.now

words = data.split.sort_by(&:size)
words.reject!{|w| words.find{|x| w!=x && x.include?(w)}}

string = words.shift

def merge_dist(prefix, suffix)
    [prefix.size,suffix.size].min.downto(0).find{|i| prefix.end_with?(suffix[0,i])}
end

while words.length > 0
    suffix = words.max_by{|w| merge_dist string, w}
    string += suffix[merge_dist(string, suffix)..-1]
    words.reject!{|w| string.include? w}
end

delta = Time.now - time

puts "Calculation completed in #{delta} seconds!"
puts "Word is #{string.size} chars long."

open("word.txt", 'w') << string

puts "Word saved to word.txt"

PowerShell v2 +, 46152 caracteres

param([System.Collections.ArrayList]$n)$n=$n|sort length -des;while($n){$x=$n.Count;$o+=$n[0];0..$x|%{if($o.IndexOf($n[$_])-ge0){$n.RemoveAt($_)}}}$o

Pega a entrada como uma lista e a lança em um ArrayList (para que possamos manipulá-la). Nós sortque por lengthem -desordem cending. Então, whileainda temos palavras em nossa matriz de entrada, faça um loop. Cada iteração, define o auxiliar $xcomo igual ao número que resta, adere no próximo item da lista à nossa saída $oe, em seguida, vasculha tudo o que ainda está em nossa lista. Se .IndexOfnão for igual a -1(ou seja, a palavra foi encontrada em algum lugar $o), removemos essa palavra da nossa lista de palavras restantes. Finalmente, no final, saída $o.

Eu não tenho acesso a um Pastebin ou similar, então aqui está o começo e o fim da palavra para temporário - telecommunicationscharacterizationresponsibilitiessublimedirectory...fcmxvtwvfxwujmjsuhjjrxjdbkdxqc. Acho que isso eliminou cerca de 20.000 caracteres da entrada, então não é tão ruim assim, suponho.

Estou trabalhando em refinamentos.

PHP 46612 caracteres

Isto é só o começo. Espero melhorá-lo. Tudo o que fiz até agora foi remover qualquer palavra que seja uma sub-string de outra palavra. Estou trabalhando em 3 cópias da matriz, mas a memória não parece ser um problema.

<?php
set_time_limit(3000);

$words=file('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt');
$words = array_map('trim', $words);

usort($words, function ($a, $b)
{
    if (strlen($a) == strlen($b) ){
        return 0;
    }
    return ( strlen($a) < strlen($b) )? -1 : 1;
});

$final_array=$words;
$comparison_array=$words;


  foreach($words as $key => $word){
    echo $word."<br>\n";
      foreach($comparison_array as $nestedKey => $nestedWord){
          if (strlen($nestedWord) <= strlen($word)) {
            unset($comparison_array[$nestedKey]);
            continue;
          }
          if( strpos($nestedWord,$word) !== FALSE ){
              unset($final_array[$key]);
              $restart=true;
              break;
          } 
      }    
  }


sort($final_array);
$compound='';
$compound = implode($final_array);
echo $compound;
echo "  <br><br>\n\n". strlen($compound);