Letzte Woche haben wir daran gearbeitet, die kürzeste 1-D-Zeichenfolge unter Verwendung der 10.000 häufigsten Wörter in englischer Sprache zu erstellen . Versuchen wir jetzt die gleiche Herausforderung in 2D!

Was Sie tun müssen, ist, alle obigen Wörter zu nehmen und sie in ein Rechteck so klein wie möglich zu setzen, um Überlappungen zuzulassen. Wenn Ihre Wörter zum Beispiel wären, wäre ["ape","pen","ab","be","pa"]ein mögliches Rechteck:

.b..
apen

Das obige Rechteck würde eine Punktzahl von 5 ergeben.

Regeln:

• Das Überlappen mehrerer Buchstaben in einem Wort ist zulässig
• Wörter können in jede der 8 Richtungen gehen
• Wörter können nicht umbrochen werden
• Sie können ein beliebiges Zeichen für die leeren Stellen verwenden

Sie müssen eine Wortsuche erstellen, die diese 10.000 Wörter in Englisch enthält (laut Google). Ihre Punktzahl entspricht der Anzahl der Zeichen in Ihrer Wortsuche (ohne nicht verwendete Zeichen). Wenn es ein Unentschieden gibt oder sich eine Einsendung als optimal herausstellt, gewinnt die Einsendung, die zuerst veröffentlicht wird.

Rust, 31430 30081 verwendeten Zeichen

Dies ist eine Art gieriger Algorithmus: Wir beginnen mit einem leeren Gitter und fügen wiederholt das Wort hinzu, das mit den wenigsten neuen Buchstaben hinzugefügt werden kann, wobei die Bindung unterbrochen wird, indem längere Wörter bevorzugt werden. Damit dies schnell ausgeführt werden kann, wird eine Prioritätswarteschlange mit Wortplatzierungskandidaten eingerichtet (implementiert als Vektor von Deques-Vektoren mit einem Vektor für jede Anzahl neuer Buchstaben, der ein Deque für jede Wortlänge enthält). Für jeden neu hinzugefügten Brief werden alle Kandidaten-Placements in die Warteschlange gestellt, die diesen Brief durchlaufen.

Kompilieren und ausführen mit rustc -O wordsearch.rs; ./wordsearch < google-10000-english.txt. Auf meinem Laptop dauert dies mit 531 MiB RAM 70 Sekunden.

Die Ausgabe passt in ein Rechteck mit 248 Spalten und 253 Zeilen.

Code

use std::collections::{HashMap, HashSet, VecDeque};
use std::io::prelude::*;
use std::iter::once;
use std::vec::Vec;

type Coord = i16;
type Pos = (Coord, Coord);
type Dir = u8;
type Word = u16;

struct Placement { word: Word, dir: Dir, pos: Pos }

static DIRS: [Pos; 8] =
    [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)];

fn fit(grid: &HashMap<Pos, u8>, (x, y): Pos, d: Dir, word: &String) -> Option<usize> {
    let (dx, dy) = DIRS[d as usize];
    let mut n = 0;
    for (i, c) in word.bytes().enumerate() {
        if let Some(c1) = grid.get(&(x + (i as Coord)*dx, y + (i as Coord)*dy)) {
            if c != *c1 {
                return None;
            }
        } else {
            n += 1;
        }
    }
    return Some(n)
}

struct PlacementQueue { queue: Vec<Vec<VecDeque<Placement>>>, extra: usize }

impl PlacementQueue {
    fn new() -> PlacementQueue {
        return PlacementQueue { queue: Vec::new(), extra: std::usize::MAX }
    }

    fn enqueue(self: &mut PlacementQueue, extra: usize, total: usize, placement: Placement) {
        while self.queue.len() <= extra {
            self.queue.push(Vec::new());
        }
        while self.queue[extra].len() <= total {
            self.queue[extra].push(VecDeque::new());
        }
        self.queue[extra][total].push_back(placement);
        if self.extra > extra {
            self.extra = extra;
        }
    }

    fn dequeue(self: &mut PlacementQueue) -> Option<Placement> {
        while self.extra < self.queue.len() {
            let mut subqueue = &mut self.queue[self.extra];
            while !subqueue.is_empty() {
                let total = subqueue.len() - 1;
                if let Some(placement) = subqueue[total].pop_front() {
                    return Some(placement);
                }
                subqueue.pop();
            }
            self.extra += 1;
        }
        return None
    }
}

fn main() {
    let stdin = std::io::stdin();
    let all_words: Vec<String> =
        stdin.lock().lines().map(|l| l.unwrap()).collect();
    let words: Vec<&String> = {
        let subwords: HashSet<&str> =
            all_words.iter().flat_map(|word| {
                (0..word.len() - 1).flat_map(move |i| {
                    (i + 1..word.len() - (i == 0) as usize).map(move |j| {
                        &word[i..j]
                    })
                })
            }).collect();
        all_words.iter().filter(|word| !subwords.contains(&word[..])).collect()
    };
    let letters: Vec<Vec<(usize, usize)>> =
        (0..128).map(|c| {
            words.iter().enumerate().flat_map(|(w, word)| {
                word.bytes().enumerate().filter(|&(_, c1)| c == c1).map(move |(i, _)| (w, i))
            }).collect()
        }).collect();

    let mut used = vec![false; words.len()];
    let mut remaining = words.len();
    let mut grids: Vec<HashMap<Pos, u8>> = Vec::new();

    while remaining != 0 {
        let mut grid: HashMap<Pos, u8> = HashMap::new();
        let mut queue = PlacementQueue::new();
        for (w, word) in words.iter().enumerate() {
            if used[w] {
                continue;
            }
            queue.enqueue(0, word.len(), Placement {
                pos: (0, 0),
                dir: 0,
                word: w as Word
            });
        }

        while let Some(placement) = queue.dequeue() {
            if used[placement.word as usize] {
                continue;
            }
            let word = words[placement.word as usize];
            if let None = fit(&grid, placement.pos, placement.dir, word) {
                continue;
            }
            let (x, y) = placement.pos;
            let (dx, dy) = DIRS[placement.dir as usize];
            let new_letters: Vec<(usize, u8)> = word.bytes().enumerate().filter(|&(i, _)| {
                !grid.contains_key(&(x + (i as Coord)*dx, y + (i as Coord)*dy))
            }).collect();
            for (i, c) in word.bytes().enumerate() {
                grid.insert((x + (i as Coord)*dx, y + (i as Coord)*dy), c);
            }
            used[placement.word as usize] = true;
            remaining -= 1;

            for (i, c) in new_letters {
                for &(w1, j) in &letters[c as usize] {
                    if used[w1] {
                        continue;
                    }
                    let word1 = words[w1];
                    for (d1, &(dx1, dy1)) in DIRS.iter().enumerate() {
                        let pos1 = (
                            x + (i as Coord)*dx - (j as Coord)*dx1,
                            y + (i as Coord) - (j as Coord)*dy1);
                        if let Some(extra1) = fit(&grid, pos1, d1 as Dir, word1) {
                            queue.enqueue(extra1, word1.len(), Placement {
                                pos: pos1,
                                dir: d1 as Dir,
                                word: w1 as Word
                            });
                        }
                    }
                }
            }
        }
        grids.push(grid);
    }

    let width = grids.iter().map(|grid| {
        grid.iter().map(|(&(x, _), _)| x).max().unwrap() -
            grid.iter().map(|(&(x, _), _)| x).min().unwrap() + 1
    }).max().unwrap();
    print!(
        "{}",
        grids.iter().flat_map(|grid| {
            let x0 = grid.iter().map(|(&(x, _), _)| x).min().unwrap();
            let y0 = grid.iter().map(|(&(_, y), _)| y).min().unwrap();
            let y1 = grid.iter().map(|(&(_, y), _)| y).max().unwrap();
            (y0..y1 + 1).flat_map(move |y| {
                (x0..x0 + width).map(move |x| {
                    *grid.get(&(x, y)).unwrap_or(&('.' as u8)) as char
                }).chain(once('\n').take(1))
            })
        }).collect::<String>()
    );
}

C ++, 27243-Zeichenraster (248 x 219, 50,2% gefüllt)

^{(Dies als neue Antwort posten, da ich die 1D-Bindung beibehalten möchte, die ich ursprünglich als Referenz gepostet habe.)}

Dieser reißt eklatant off durch ist stark inspiriert @ AndersKaseorg Antwort in seiner Hauptstruktur, hat aber ein paar Verbesserungen. Zuerst verwende ich mein ursprüngliches Programm, um Zeichenfolgen zusammenzuführen, bis die beste verfügbare Überlappung nur noch 3 Zeichen beträgt. Dann benutze ich die von AndersKaseorg beschriebene Methode, um ein 2D-Gitter mit diesen generierten Zeichenfolgen fortlaufend zu füllen. Die Einschränkungen sind auch ein wenig anders: Es wird immer noch versucht, jedes Mal die wenigsten Zeichen einzufügen, aber Bindungen werden unterbrochen, indem zuerst quadratische Gitter, dann kleine Gitter und schließlich das längste Wort hinzugefügt werden.

Das Verhalten, das angezeigt wird, besteht darin, abwechselnd Leerstellen auszufüllen und das Raster schnell zu erweitern (leider waren kurz nach einer schnellen Ausbaustufe keine Worte mehr zu finden, sodass an den Rändern eine Menge Leerstellen vorhanden sind). Ich vermute, dass mit einigen Optimierungen der Kostenfunktion eine Raumausfüllung von mehr als 50% erzielt werden könnte.

Hier gibt es 2 ausführbare Dateien (um zu vermeiden, dass der gesamte Prozess erneut ausgeführt werden muss, wenn der Algorithmus iterativ verbessert wird). Der Ausgang von einem kann direkt in den anderen geleitet werden:

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>

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

bool isSameReversed(const std::string &a, const std::string &b) {
    std::size_t l = a.size();
    if(b.size() != l) {
        return false;
    }
    for(std::size_t i = 0; i < l; ++ i) {
        if(a[i] != b[l-i-1]) {
            return false;
        }
    }
    return true;
}

int main(int argc, const char *const *argv) {
    // Usage: prog [<stop_threshold>]

    std::size_t stopThreshold = 3;

    if(argc >= 2) {
        char *check;
        long v = std::strtol(argv[1], &check, 10);
        if(check == argv[1] || v < 0) {
            std::cerr
                << "Invalid stop threshold. Should be an integer >= 0"
                << std::endl;
            return 1;
        }
        stopThreshold = v;
    }

    std::vector<std::string> words;

    // Load all words from input and their reverses (words can be backwards now)
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
        std::reverse(word.begin(), word.end());
        words.push_back(std::move(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 we reach the threshold
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 2) {
        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 && !isSameReversed(*p, *q)) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap && !isSameReversed(*p, *q)) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        if(bestOverlap <= stopThreshold) {
            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 (forward or reverse)
        // (would not be necessary if we didn't have the reversed forms too)
        std::string newRev = newStr;
        std::reverse(newRev.begin(), newRev.end());
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos || newRev.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));
        words.push_back(std::move(newRev));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

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

    // Remove all fully subsumed words (i.e. reversed words)

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

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

    // Sort words longest-to-shortest for display
    std::sort(words.begin(), words.end(), [](const std::string &a, const std::string &b) {
        return a.size() > b.size();
    });

    std::size_t len = 0;
    for(const auto &word : words) {
        std::cout
            << word
            << std::endl;
        len += word.size();
    }
    std::cerr
        << "Total size: " << len
        << std::endl;
    return 0;
}

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <limits>

class vec2 {
public:
    int x;
    int y;

    vec2(void) : x(0), y(0) {};
    vec2(int x, int y) : x(x), y(y) {}

    bool operator ==(const vec2 &b) const {
        return x == b.x && y == b.y;
    }

    vec2 &operator +=(const vec2 &b) {
        x += b.x;
        y += b.y;
        return *this;
    }

    vec2 &operator -=(const vec2 &b) {
        x -= b.x;
        y -= b.y;
        return *this;
    }

    vec2 operator +(const vec2 b) const {
        return vec2(x + b.x, y + b.y);
    }

    vec2 operator *(const int b) const {
        return vec2(x * b, y * b);
    }
};

class box2 {
public:
    vec2 tl;
    vec2 br;

    box2(void) : tl(), br() {};
    box2(vec2 a, vec2 b)
        : tl(std::min(a.x, b.x), std::min(a.y, b.y))
        , br(std::max(a.x, b.x) + 1, std::max(a.y, b.y) + 1)
    {}

    void grow(const box2 &b) {
        if(b.tl.x < tl.x) {
            tl.x = b.tl.x;
        }
        if(b.br.x > br.x) {
            br.x = b.br.x;
        }
        if(b.tl.y < tl.y) {
            tl.y = b.tl.y;
        }
        if(b.br.y > br.y) {
            br.y = b.br.y;
        }
    }

    bool intersects(const box2 &b) const {
        return (
            ((tl.x >= b.br.x) != (br.x > b.tl.x)) &&
            ((tl.y >= b.br.y) != (br.y > b.tl.y))
        );
    }

    box2 &operator +=(const vec2 b) {
        tl += b;
        br += b;
        return *this;
    }

    int width(void) const {
        return br.x - tl.x;
    }

    int height(void) const {
        return br.y - tl.y;
    }

    int maxdim(void) const {
        return std::max(width(), height());
    }
};

template <> struct std::hash<vec2> {
    std::size_t operator ()(const vec2 &o) const {
        return std::hash<int>()(o.x) + std::hash<int>()(o.y) * 997;
    }
};

template <class A,class B> struct std::hash<std::pair<A,B>> {
    std::size_t operator ()(const std::pair<A,B> &o) const {
        return std::hash<A>()(o.first) + std::hash<B>()(o.second) * 31;
    }
};

class word_placement {
public:
    vec2 start;
    vec2 dir;
    box2 bounds;
    const std::string *word;

    word_placement(vec2 start, vec2 dir, const std::string *word)
        : start(start)
        , dir(dir)
        , bounds(start, start + dir * (word->size() - 1))
        , word(word)
    {}

    word_placement(vec2 start, const word_placement &copy)
        : start(copy.start + start)
        , dir(copy.dir)
        , bounds(copy.bounds)
        , word(copy.word)
    {
        bounds += start;
    }

    word_placement(const word_placement &copy)
        : start(copy.start)
        , dir(copy.dir)
        , bounds(copy.bounds)
        , word(copy.word)
    {}
};

class word_placement_links {
public:
    std::unordered_set<word_placement*> placements;
    std::unordered_set<std::pair<char,word_placement*>> relativePlacements;
};

class grid {
public:
    std::vector<std::string> wordCache; // Just a block of memory for our pointers to reference
    std::unordered_map<vec2,char> state;
    std::unordered_set<word_placement*> placements;
    std::unordered_map<const std::string*,word_placement_links> wordPlacements;
    std::unordered_map<char,std::unordered_set<word_placement*>> relativeWordPlacements;
    box2 bound;

    grid(const std::vector<std::string> &words) {
        wordCache = words;
        std::vector<vec2> directions;
        directions.emplace_back(+1,  0);
        directions.emplace_back(+1, +1);
        directions.emplace_back( 0, +1);
        directions.emplace_back(-1, +1);
        directions.emplace_back(-1,  0);
        directions.emplace_back(-1, -1);
        directions.emplace_back( 0, -1);
        directions.emplace_back(+1, -1);

        wordPlacements.reserve(wordCache.size());
        placements.reserve(wordCache.size());
        relativeWordPlacements.reserve(64);

        std::size_t total = 0;
        for(const std::string &word : wordCache) {
            word_placement_links &p = wordPlacements[&word];
            p.placements.reserve(8);
            auto &rp = p.relativePlacements;
            std::size_t l = word.size();
            rp.reserve(l * directions.size());
            for(int i = 0; i < l; ++ i) {
                for(const vec2 &d : directions) {
                    word_placement *rwp = new word_placement(d * -i, d, &word);
                    rp.emplace(word[i], rwp);
                    relativeWordPlacements[word[i]].insert(rwp);
                }
            }
            total += l;
        }
        state.reserve(total);
    }

    const std::string *find_word(const std::string &word) const {
        for(const std::string &w : wordCache) {
            if(w == word) {
                return &w;
            }
        }
        throw std::string("Failed to find word in cache");
    }

    void remove_word(const std::string *word) {
        const word_placement_links &links = wordPlacements[word];
        for(word_placement *p : links.placements) {
            placements.erase(p);
            delete p;
        }
        for(auto &p : links.relativePlacements) {
            relativeWordPlacements[p.first].erase(p.second);
            delete p.second;
        }
        wordPlacements.erase(word);
    }

    void remove_placement(word_placement *placement) {
        wordPlacements[placement->word].placements.erase(placement);
        placements.erase(placement);
        delete placement;
    }

    bool check_placement(const word_placement &placement) const {
        vec2 p = placement.start;
        for(const char c : *placement.word) {
            auto i = state.find(p);
            if(i != state.end() && i->second != c) {
                return false;
            }
            p += placement.dir;
        }
        return true;
    }

    int check_new(const word_placement &placement) const {
        int n = 0;
        vec2 p = placement.start;
        for(const char c : *placement.word) {
            n += !state.count(p);
            p += placement.dir;
        }
        return n;
    }

    void check_placements(const box2 &b) {
        for(auto i = placements.begin(); i != placements.end(); ) {
            if(!b.intersects((*i)->bounds) || check_placement(**i)) {
                ++ i;
            } else {
                i = placements.erase(i);
            }
        }
    }

    void add_placement(const vec2 p, const word_placement &relative) {
        word_placement check(p, relative);
        if(check_placement(check)) {
            word_placement *wp = new word_placement(check);
            placements.insert(wp);
            wordPlacements[relative.word].placements.insert(wp);
        }
    }

    void place(word_placement placement) {
        remove_word(placement.word);
        int overlap = 0;
        for(const char c : *placement.word) {
            char &g = state[placement.start];
            if(g == '\0') {
                g = c;
                for(const word_placement *rp : relativeWordPlacements[c]) {
                    add_placement(placement.start, *rp);
                }
            } else if(g != c) {
                throw std::string("New word changes an existing character!");
            } else {
                ++ overlap;
            }
            placement.start += placement.dir;
        }
        bound.grow(placement.bounds);
        check_placements(placement.bounds);

        std::cerr
            << draw('.', "\n")
            << "Added " << *placement.word << " (overlap: " << overlap << ")"
            << ", Grid: " << bound.width() << "x" << bound.height() << " of " << state.size() << " chars"
            << ", Words remaining: " << wordPlacements.size()
            << std::endl;
    }

    int check_cost(box2 b) const {
        b.grow(bound);
        return (
            ((b.maxdim() - bound.maxdim()) << 16) |
            (b.width() + b.height() - bound.width() - bound.height())
        );
    }

    void add_next(void) {
        int bestNew = std::numeric_limits<int>::max();
        int bestCost = std::numeric_limits<int>::max();
        int bestLen = 0;
        word_placement *best = nullptr;
        for(word_placement *p : placements) {
            int n = check_new(*p);
            if(n <= bestNew) {
                int l = p->word->size();
                int cost = check_cost(box2(p->start, p->start + p->dir * l));
                if(n < bestNew || cost < bestCost || (cost == bestCost && l < bestLen)) {
                    bestNew = n;
                    bestCost = cost;
                    bestLen = l;
                    best = p;
                }
            }
        }
        if(best == nullptr) {
            throw std::string("Failed to find join to existing blob");
        }
        place(*best);
    }

    void fill(void) {
        while(!placements.empty()) {
            add_next();
        }
    }

    std::string draw(char blank, const std::string &linesep) const {
        std::string result;
        result.reserve((bound.width() + linesep.size()) * bound.height());
        for(int y = bound.tl.y; y < bound.br.y; ++ y) {
            for(int x = bound.tl.x; x < bound.br.x; ++ x) {
                auto c = state.find(vec2(x, y));
                result.push_back((c == state.end()) ? blank : c->second);
            }
            result.append(linesep);
        }
        return result;
    }

    box2 bounds(void) const {
        return bound;
    }

    int chars(void) const {
        return state.size();
    }
};

int main(int argc, const char *const *argv) {
    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(std::move(word));
    }

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

    // initialise grid
    grid g(words);

    // add first word (order of input file means this is longest word)
    g.place(word_placement(vec2(0, 0), vec2(1, 0), g.find_word(words.front())));

    // add all other words
    g.fill();

    std::cout << g.draw('.', "\n");

    int w = g.bounds().width();
    int h = g.bounds().height();
    int n = g.chars();
    std::cerr
        << "Final grid: " << w << "x" << h
        << " with " << n << " characters"
        << " (" << (n * 100.0 / (w * h)) << "% filled)"
        << std::endl;
    return 0;
}

Und zum Schluss das Ergebnis:

Alternatives Ergebnis (nachdem einige Fehler im Programm behoben wurden, die bestimmte Richtungen beeinflussten und die Kostenfunktion optimierten, erhielt ich eine kompaktere, aber weniger optimale Lösung): 29275 Zeichen, 198x195 (75,8% gefüllt):

Ich habe wieder nicht viel getan, um diese Programme zu optimieren, also dauert es eine Weile. Aber Sie können zusehen, wie es das Gitter ausfüllt, was ziemlich hypnotisch ist.

C ++, 34191 Zeichen "Gitter" (mit minimalem menschlichem Eingriff können 6 oder 7 leicht gespeichert werden)

Dies sollte eher als Grenze für den 2D-Fall verstanden werden, da die Antwort immer noch eine 1D-Zeichenfolge ist. Es ist nur mein Code aus der vorherigen Herausforderung, aber mit der neuen Möglichkeit, beliebige Zeichenfolgen umzukehren. Dies gibt uns viel mehr Spielraum für das Kombinieren von Wörtern (insbesondere, weil es den schlimmsten Fall nicht überlappender Superstrings auf 26 begrenzt; einen für jeden Buchstaben des Alphabets).

Für eine leichte 2D-Darstellung werden Zeilenumbrüche in das Ergebnis eingefügt, wenn dies kostenlos möglich ist (dh zwischen Wörtern mit 0 Überlappungen).

Ziemlich langsam (immer noch kein Caching). Hier ist der Code:

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

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

bool isSameReversed(const std::string &a, const std::string &b) {
    std::size_t l = a.size();
    if(b.size() != l) {
        return false;
    }
    for(std::size_t i = 0; i < l; ++ i) {
        if(a[i] != b[l-i-1]) {
            return false;
        }
    }
    return true;
}

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

    // Load all words from input and their reverses (words can be backwards now)
    while(true) {
        std::string word;
        std::getline(std::cin, word);
        if(word.empty()) {
            break;
        }
        words.push_back(word);
        std::reverse(word.begin(), word.end());
        words.push_back(std::move(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 we have only 1 word left (+ its reverse)
    std::size_t bestPossible = maxlen - 1;
    while(words.size() > 2) {
        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 && !isSameReversed(*p, *q)) {
                    bestA = p;
                    bestB = q;
                    bestOverlap = overlap;
                }
                overlap = calcOverlap(*q, *p, bestPossible, bestOverlap);
                if(overlap > bestOverlap && !isSameReversed(*p, *q)) {
                    bestA = q;
                    bestB = p;
                    bestOverlap = overlap;
                }
            }
            if(bestOverlap == bestPossible) {
                break;
            }
        }
        std::string newStr = std::move(*bestA);
        if(bestOverlap == 0) {
            newStr.push_back('\n');
        }
        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 (forward or reverse)
        // (would not be necessary if we didn't have the reversed forms too)
        std::string newRev = newStr;
        std::reverse(newRev.begin(), newRev.end());
        for(auto p = words.begin(); p != words.end(); ) {
            if(newStr.find(*p) != std::string::npos || newRev.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));
        words.push_back(std::move(newRev));
        bestPossible = bestOverlap; // Merging existing words will never make longer merges possible
    }

    std::cerr
        << "After non-trivial merging: " << words.size()
        << std::endl;

    if(words.size() == 2 && !isSameReversed(words.front(), words.back())) {
        // must be 2 palindromes, so just join them
        words.front().append(words.back());
    }

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

    std::cout
        << result
        << std::endl;
    std::cerr
        << "Word size: " << result.size() // Note this number includes newlines, so to get the grid size according to the rules, subtract newlines manually
        << std::endl;
    return 0;
}

Ergebnis: http://pastebin.com/UTe2WMcz (4081 Zeichen weniger als die vorherige Herausforderung)

Es ist ziemlich klar, dass einige geringfügige Einsparungen erzielt werden können, wenn die Linien xdund wvvertikal angeordnet werden und die Monsterlinie schneiden. Dann hhidetautisbneuduikann schneiden mit dem dund lxwwwowaxocnnaesddamit w. Das spart 4 Zeichen. nbcllilhnkann in eine vorhandene sÜberlappung eingesetzt werden (wenn eine vorhanden ist), um weitere 2 zu speichern (oder nur 1, wenn keine solche Überlappung vorhanden ist und diese stattdessen vertikal hinzugefügt werden muss). Zum mjjrajaytqSpeichern kann der Wert schließlich irgendwo vertikal hinzugefügt werden 1. Dies bedeutet, dass mit minimalem menschlichem Eingriff 6 bis 7 Zeichen aus dem Ergebnis gespeichert werden können.

Ich würde dies gerne mit der folgenden Methode in 2D umsetzen, aber ich habe Mühe, einen Weg zu finden, um es zu implementieren, ohne den Algorithmus O (n ^ 4) zu erstellen, der recht unpraktisch zu berechnen ist!

1. Führen Sie den Algorithmus wie oben beschrieben aus, hören Sie jedoch auf, wenn die Überlappungen 1 Zeichen erreichen
2. Wiederholt:
   1. Suchen Sie eine Gruppe von 4 Wörtern, die in einem Rechteck angeordnet werden können
   2. Fügen Sie so viele Wörter wie möglich über dieses Rechteck, wobei jedes Wort mindestens 2 Zeichen der aktuellen Form überlappt (überprüfen Sie alle 8 Richtungen). Dies ist die einzige Phase, in der wir tatsächlich einen Vorteil gegenüber dem aktuellen Code erzielen können
3. Kombinieren Sie die resultierenden Gitter und Einzelwörter und suchen Sie jedes Mal nach Ein-Buchstaben-Überlappungen

PHP

dieser macht den Job theroratisch; aber 10000 sind wahrscheinlich zu viele Wörter für eine Rekursion. Das Skript wird jetzt ausgeführt. (lief noch 24 Stunden später)
funktioniert gut auf kleinen Verzeichnissen, aber ich kann eine iterative Version nächste Woche machen.

$f=array("pen","op","po","ne","pro","aaa","abcd","dcba"); will output abcd apen arop ao .. although this is not an optimal result (scoring was changed ... I´m working on a generator). One optimal result is this: open .ra .oa dcba`

Es ist auch nicht sehr schnell; Entfernt nur Teilzeichenfolgen und sortiert die Überreste nach Länge,
der Rest ist Brute Force: Versuchen Sie, die Wörter in ein Rechteck einzufügen, versuchen Sie es mit einem größeren Rechteck, wenn dies fehlschlägt.

Übrigens: Der Teil des Teilstrings benötigt auf meinem Computer 4,5 Minuten für das große Verzeichnis
und reduziert es auf 6.190 Wörter. Die Sortierung dauert 11 Sekunden.

$f=file('https://raw.githubusercontent.com/first20hours/google-10000-english/master/google-10000-english.txt');
// A: remove substrings - forward or reversed
$s=join(' ',$f);
$haystack="$s ".strrev($s);
foreach($f as$w)
{
    $r=strrev($w=trim($w)); // remove trailing line break and create reverse word
    if(!preg_match("%$w\w|\w$w%",$haystack)
        // no substr match ... now: is the reverse word in the list?
        // if so, keep only the lower one (ascii values)
        &!($w>$r&&strstr($s,$r))
        // strstr does NOT render the reverse substr regex obsolete:
        // this is only executed for $w=abc, not for $w=bca!
    )
        $g[]=$w
    ;
}

// B: sort the words by length
usort($g,function($a,$b){return strlen($a)-strlen($b);});

// C1: function to fit $words into $map
function gomap($words,$map)
{
    $h=count($map);$w=strlen($map[0]);
    $len=strlen($word=array_pop($words));
    // $x,$y=position; $d=0:horizontal, $d=1:vertical; $r=0: word, $r=1: reverse word
    for($x=$w-$len;$x>=0;$x--)for($y=$h-$len;$y>=0;$y--)for($d=0;$d<2;$d++)for($r=0;$r<2;$r++)
    {
        // does the word fit there?
        $drow=$r?strrev($word):$word;
        for($ok=1,$i=0;$ok&$i<$len;$i++)
            $ok=in_array($map[$y+$d*$i][$x+$i-$d*$i], [' ',$drow[$i]])
        ;
        // it does, paint it
        if($ok)
        {
            for($i=0;$i<$len;$i++)
                $map[$y+$d*$i][$x+$i-$d*$i]=$drow[$i];
            if(!count($words))      // this was the last word: return map
                return $map;
            else                    // there are more words: recurse
                if ($ok=gomap($words,$map))
                    return $ok;
            // no fit, try next position
        }
    }
    return 0;
}

// C2: rectangle loop
for($h=0;++$h;)for($w=0;$w++<$h;)   // define a rectangle
{
    // and try to fit the words in there
    if($map=gomap($g,
        array_fill(0,$h,str_repeat(' ',$w))
    ))
    {
        // words fit; output and break loops
        echo '<pre>',implode("\n",$map),'</pre>';
        break 2;
    }
}