Ein zusammengesetztes Wort ist ein Wort, das zwei oder mehr Wörter enthält. Aber wir können es besser machen. Sie müssen ein (unsinniges) Wort erstellen, das jedes Wort enthält .

Wir möchten jedoch, dass dieses Wort so kurz wie möglich ist. Wir können überlappende Buchstaben verwenden, um dies zu erreichen.

Wenn Ihre Wortliste beispielsweise lautete ["cat", "atom", "a"], möchten Sie zurückkehren "catom".

Input-Output

Ihr Programm muss eine Liste von Wörtern als Eingabe und ein zusammengesetztes Wort als Ausgabe zurückgeben.

Die Wortliste, die Sie verwenden werden, ist laut Google die Liste der 10000 wichtigsten Wörter in Englisch (Wenn sich diese Liste als zu einfach herausstellt, kann ich sie durch eine längere Liste ersetzen). Wenn Sie als Referenz einfach jedes Wort anhängen, erhalten Sie eine Punktzahl von 65888.

Ihre Punktzahl ist die Anzahl der Buchstaben in Ihrem letzten Wort, niedriger ist besser. Der Krawattenbrecher geht zum ersten Plakat.

C ++, endgültige Wortlänge: 38272

(optimierte Version dauerte ca. 20 Minuten)

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

Verification Bash One-Liner:

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

Es hat auch einige ziemlich coole In-Progress-Wörter produziert. Hier sind einige meiner Favoriten:

• Gestern (synthetische Nostalgie)
• afghanistanbul (etwas [Politiker einfügen, das Sie nicht mögen] würde sagen)
• zusammen (das freundliche Internet)
• Elefantom (ein großer Geist)
• thundergroundwaterproof (wie in "Ich weiß nicht, warum sie das Bedürfnis verspürten, es thundergroundwaterproof zu machen, aber es macht mich nervös")

Und:

• codescribingo (möglicherweise eine bevorstehende Herausforderung auf dieser Site?)

Die endgültige Ausgabe ist auf Pastebin hier: http://pastebin.com/j3qYb65b

C ++ 11, 38272 Buchstaben, als optimal erwiesen

Dieser Algorithmus garantiert eine niedrigere Grenze für die Lösung. In diesem Fall ist es möglich, die Untergrenze zu erreichen und eine optimale Lösung mit 38272 Buchstaben auszugeben. (Dies entspricht der Lösung, die von Daves gierigem Algorithmus gefunden wurde. Ich war überrascht und ein wenig enttäuscht, als ich herausfand, dass es optimal ist, aber da sind wir.)

Es funktioniert durch Lösen des Minimalkostenflusses in dem Netzwerk, das wie folgt aufgebaut ist.

• Erstens sind alle Wörter, die in anderen Wörtern enthalten sind, überflüssig; wirf sie weg.
• Für jedes Wort w , ziehen zwei Knoten w _0 und w _1, wo w _0 ist eine Quelle mit einer Kapazität von 1 und w _1 ist eine Wanne mit Kapazität 1.
• Zeichnen Sie für jedes (strenge) Präfix oder Suffix eines Wortes einen Knoten a .
• Zeichnen Sie für jedes Suffix a von w einen Bogen von w _0 bis a mit der Kapazität 1 und kosten Sie 0.
• Zeichnen Sie für jedes Präfix a von w einen Bogen von a bis w _1 mit Kapazität 1 und Kostenlänge ( w ) - Länge ( a ).

Jede Zeichenfolge mit der Länge n , die jedes Wort enthält, kann in diesem Netzwerk zu höchstens n Kosten in einen Datenfluss umgewandelt werden . Daher ist der minimale Kostenfluss in diesem Netzwerk eine Untergrenze für die Länge des kürzesten solchen Strings.

Wenn wir Glück haben - und in diesem Fall auch -, dann, nachdem wir den eingehenden Fluss umgeleitet haben w_1 eintritt, zurück aus w eingehenden _0 einen optimalen Fluss mit nur einer verbundenen Komponente, der den Knoten für den leeren durchläuft Zeichenfolge. In diesem Fall enthält es einen Eulerschen Kreis, der dort beginnt und endet. Eine solche Eulersche Schaltung kann als eine Kette optimaler Länge ausgelesen werden.

Wenn wir kein Glück hatten, fügen Sie einige zusätzliche Bögen zwischen der leeren Zeichenfolge und den kürzesten Zeichenfolgen in den anderen verbundenen Komponenten hinzu, um sicherzustellen, dass eine Euler-Schaltung vorhanden ist. Die Zeichenfolge wäre in diesem Fall nicht mehr unbedingt optimal.

Ich benutze die LEMON- Bibliothek für ihre Min-Cost-Flow- und Euler-Schaltungsalgorithmen. (Ich habe diese Bibliothek zum ersten Mal verwendet und war beeindruckt - ich werde sie auf jeden Fall wieder für zukünftige Anforderungen an Grafikalgorithmen verwenden.) LEMON wird mit vier verschiedenen Minimum-Cost-Flow-Algorithmen geliefert. Sie können sie hier mit versuchen --net, --cost, --cap, und --cycle(Standard).

Das Programm läuft in 0,5 Sekunden ab und erzeugt diese Ausgabezeichenfolge .

#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 Minuten, Länge 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);
        }
    }

}

Eingang:

• Eine Datei mit dem Namen "words.txt" im Arbeitsverzeichnis im exakt gleichen Format wie die Datei im Hauptbeitrag

Ausgabe:

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

Python 2, 39254 Zeichen

Die Ausführung auf meinem Computer dauert 1 bis 2 Minuten. Dabei wird das längste Wort verwendet und das Wort immer der Ergebniszeichenfolge hinzugefügt, die die meisten gemeinsamen Zeichenfolgen enthält. (Vorher werden alle Wörter, die Teilzeichenfolgen anderer Wörter sind, entfernt, um unnötiges Hinzufügen zur Zeichenfolge zu vermeiden.)

Update: Versucht in beide Richtungen zu schauen, aber das geht nicht besser. (Vielleicht verwendet es Wörter, die später besser verwendet werden können?)

Link zum Wort auf Pastebin.

erste 100 Zeichen:

telecommunicationsawayneillegallynnbabyenbcjrxltdxmlbsrcwvtxxxboxespnycdsriconsentencessexyrsslipodc

Code:

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 Zeichen

Verwendet einen ähnlichen Ansatz wie @KarlKastor in seiner Python-Antwort, aber die Startzeichenfolge ist eines der kleinsten statt der größten Wörter. Eine weitere Optimierung (ich weiß nicht, wie viel es hilft) besteht darin, dass zwischen den einzelnen Hinzufügungen alle Wörter entfernt werden, die möglicherweise aufgrund überlappender Wörter bereits in der Zeichenfolge enthalten sind.

Läuft in etwas mehr als 4 Minuten auf meinem Computer, ohne die Webanforderung zum Abrufen der Wortliste zu zählen, aber nicht ganz 4:20.

Das Wort zum 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 Zeichen

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

Nimmt die Eingabe als Liste und wandelt sie in eine ArrayList um (damit wir sie bearbeiten können). Wir sortes durch lengthin -desaufsteigender reihenfolge. Dann haben whilewir immer noch Wörter in unserem Eingabearray, machen Sie eine Schleife. Stellen Sie den Helfer $xbei jeder Iteration so ein, dass er der Anzahl der verbleibenden Helfer entspricht, markieren Sie das nächste Element in der Liste für unsere Ausgabe $ound durchsuchen Sie dann alles, was noch in unserer Liste enthalten ist. Wenn das .IndexOfnicht gleich ist -1(dh das Wort wurde irgendwo in gefunden $o), entfernen wir dieses Wort aus unserer Liste der verbleibenden Wörter. Schließlich am Ende Ausgabe$o .

Ich habe keinen Zugang zu einem Pastebin oder ähnlichem, also hier ist der Anfang und das Ende des Wortes für temporär - telecommunicationscharacterizationresponsibilitiessublimedirectory...fcmxvtwvfxwujmjsuhjjrxjdbkdxqc. Was ich denke, hat ungefähr 20.000 Zeichen von der Eingabe entfernt, also nicht so schlimm, nehme ich an.

Ich arbeite an Verbesserungen.

PHP 46612 Zeichen

Dies ist nur ein Anfang. Ich hoffe es zu verbessern. Alles, was ich bisher getan habe, ist, jedes Wort zu entfernen, das eine Unterzeichenfolge eines anderen Wortes ist. Ich arbeite an 3 Kopien des Arrays, aber der Speicher scheint kein Problem zu sein.

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