W zeszłym tygodniu pracowaliśmy nad stworzeniem najkrótszego ciągu 1-D przy użyciu 10 000 najlepszych słów w języku angielskim . Teraz spróbujmy tego samego wyzwania w 2D!

Wszystko, co musisz zrobić, to wziąć wszystkie powyższe słowa i umieścić je w możliwie jak najmniejszym prostokącie, umożliwiając nakładanie się. Na przykład, jeśli twoje słowa były ["ape","pen","ab","be","pa"], to możliwy prostokąt to:

.b..
apen

Powyższy prostokąt dałby wynik 5.

Zasady:

• Dozwolone jest nakładanie wielu liter na słowo
• Słowa mogą iść w dowolnym z 8 kierunków
• Słowa nie mogą się zawijać
• W pustych lokalizacjach możesz użyć dowolnej postaci

Musisz utworzyć wyszukiwanie słów zawierające te 10 000 najlepszych słów w języku angielskim (według Google). Twój wynik jest równy liczbie znaków w wyszukiwaniu słów (z wyłączeniem nieużywanych znaków). Jeśli istnieje remis lub jeśli przesłanie okaże się optymalne, zgłoszenie, które zostanie opublikowane jako pierwsze, wygrywa.

Rust, 31430 30081 używanych znaków

Jest to pewien rodzaj chciwego algorytmu: zaczynamy od pustej siatki i wielokrotnie dodajemy słowo, które można dodać z jak najmniejszą liczbą nowych liter, z przerwanymi więzami przez preferowanie dłuższych słów. Aby to działało szybko, utrzymujemy priorytetową kolejkę umieszczania słów kandydujących (zaimplementowaną jako wektor wektorów deques, z wektorem dla każdej liczby nowych liter, zawierającym deque dla każdej długości słowa). Dla każdego nowo dodanego listu kolejkujemy wszystkie miejsca docelowe kandydatów, które przebiegają przez ten list.

Skompiluj i uruchom z rustc -O wordsearch.rs; ./wordsearch < google-10000-english.txt. Na moim laptopie działa to w 70 sekund, przy użyciu 531 MiB RAM.

Dane wyjściowe mieszczą się w prostokącie z 248 kolumnami i 253 wierszami.

Kod

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 ++, siatka znaków 27243 (248 x 219, wypełnienie 50,2%)

^{(Publikuję to jako nową odpowiedź, ponieważ chciałbym zachować granicę 1D, którą pierwotnie opublikowałem jako odniesienie)}

To rażące zerwanie jest mocno zainspirowane odpowiedzią @ AndersKaseorg w głównej strukturze, ale ma kilka drobnych poprawek. Po pierwsze, używam mojego oryginalnego programu do scalania ciągów, aż najlepsze dostępne nakładanie się będzie mieć tylko 3 znaki. Następnie używam metody opisanej przez AndersKaseorg do stopniowego wypełniania siatki 2D za pomocą wygenerowanych ciągów. Ograniczenia też są trochę inne: wciąż próbuje dodawać najmniej znaków za każdym razem, ale więzi są zrywane, preferując najpierw kwadratowe siatki, potem małe siatki, a na końcu dodając najdłuższe słowo.

Zachowanie, które wyświetla, polega na naprzemiennym wypełnianiu przestrzeni i szybkim rozszerzaniu siatki (niestety zabrakło słów tuż po etapie szybkiego rozszerzania, więc wokół krawędzi jest dużo pustej przestrzeni). Podejrzewam, że z pewnym dopracowaniem funkcji kosztu, którą można by uzyskać, aby uzyskać więcej niż 50% wypełnienia przestrzeni.

Są tutaj 2 pliki wykonywalne (aby uniknąć konieczności ponownego uruchomienia całego procesu podczas iteracyjnej poprawy algorytmu). Dane wyjściowe jednego można przesyłać bezpośrednio do drugiego:

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

I wreszcie wynik:

Alternatywny wynik (po naprawieniu kilku błędów w programie, które odchylały pewne kierunki i poprawiał funkcję kosztów, otrzymałem bardziej kompaktowe, ale mniej optymalne rozwiązanie): 29275 znaków, 198 x 195 (wypełnione 75,8%):

Znów nie zrobiłem wiele, aby zoptymalizować te programy, więc zajmuje to trochę czasu. Ale możesz obserwować, jak wypełnia siatkę, co jest dość hipnotyczne.

C ++, 34191 „siatka” znaków (przy minimalnej interwencji człowieka można łatwo zapisać 6 lub 7)

Powinno to być traktowane bardziej jako ograniczenie dla przypadku 2D, ponieważ odpowiedź jest wciąż ciągiem 1D. To tylko mój kod z poprzedniego wyzwania, ale z nową możliwością odwrócenia dowolnego łańcucha. Daje nam to znacznie więcej możliwości łączenia słów (szczególnie dlatego, że ogranicza najgorszy przypadek nie nakładających się superstrun do 26; po jednej na każdą literę alfabetu).

W przypadku niewielkiej atrakcyjności wizualnej 2D umieszcza w wyniku przełamania linii, jeśli może to zrobić za darmo (tj. Między wyrazami 0-nakładającymi się).

Dość powolny (wciąż bez buforowania). Oto kod:

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

Wynik: http://pastebin.com/UTe2WMcz (4081 znaków mniej niż poprzednie wyzwanie)

Jest całkiem jasne, że można uzyskać trywialne oszczędności, ustawiając linie xdi wvpionowo, przecinając linię potwora. Następnie hhidetautisbneuduimoże przecinać się z d, i lxwwwowaxocnnaesddaz w. To oszczędza 4 znaki. nbcllilhnmożna zastąpić istniejącym szakładkiem (jeśli można go znaleźć), aby zapisać kolejne 2 (lub tylko 1, jeśli takie nakładanie nie istnieje i należy je zamiast tego dodać pionowo). Wreszcie mjjrajaytqmożna dodać gdzieś pionowo, aby zapisać 1. Oznacza to, że przy minimalnej interwencji człowieka można zapisać 6–7 znaków z wyniku.

Chciałbym wprowadzić to do 2D za pomocą następującej metody, ale staram się znaleźć sposób na wdrożenie tego bez tworzenia algorytmu O (n ^ 4), co jest dość niepraktyczne!

1. Uruchom algorytm jak wyżej, ale zatrzymaj się na krótko, gdy nakładki osiągną 1 znak
2. Wielokrotnie:
   1. Znajdź grupę 4 słów, które można ułożyć w prostokąt
   2. Dodaj jak najwięcej słów na górze tego prostokąta, w którym każde słowo nakłada się na co najmniej 2 znaki bieżącego kształtu (sprawdź wszystkie 8 kierunków) - jest to jedyny etap, w którym możemy faktycznie uzyskać przewagę nad bieżącym kodem
3. Połącz wynikowe siatki i pojedyncze słowa, szukając nakładających się na siebie liter za każdym razem

PHP

ten wykonuje pracę termicznie; ale 10000 to prawdopodobnie zbyt wiele słów do rekurencji. Skrypt działa teraz. (nadal
działa 24 godziny później) działa dobrze w małych katalogach, ale w przyszłym tygodniu mogę utworzyć wersję iteracyjną.

$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: otwórz .ra .oa dcba`

Nie jest też bardzo szybki; usuwa tylko podciągi i sortuje resztki według długości,
reszta to brutalna siła: spróbuj dopasować słowa do prostokąta, spróbuj na większym prostokącie, jeśli się nie powiedzie.

btw: Część podciągu potrzebuje 4,5 minuty na mojej maszynie dla dużego katalogu
i skraca ją do 6190 słów; sortowanie na nich zajmuje 11 sekund.

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