На прошлой неделе мы работали над созданием самой короткой 1-D строки, используя лучшие 10000 слов в английском языке . Теперь давайте попробуем ту же задачу в 2D!

Что вам нужно сделать, это взять все вышеперечисленные слова и поместить их в прямоугольник как можно меньшего размера, учитывая перекрытия. Например, если бы ваши слова были ["ape","pen","ab","be","pa"], то возможный прямоугольник был бы:

.b..
apen

Вышеуказанный прямоугольник даст оценку 5.

Правила:

• Допускается наложение нескольких букв в слове
• Слова могут идти в любом из 8 направлений
• Слова не могут обернуться
• Вы можете использовать любой символ для пустых мест

Вам нужно создать поиск слов, который содержит эти 10000 лучших слов на английском языке (по данным Google). Ваша оценка равна количеству символов в вашем поиске слов (исключая неиспользованные символы). Если есть связь, или если подача доказана, чтобы быть оптимальной, тогда выигрывает заявка, которая сначала отправлена.

Ржавчина, 31430 30081 используемые символы

Это своего рода жадный алгоритм: мы начинаем с пустой сетки и многократно добавляем слово, которое можно добавлять с наименьшим количеством новых букв, с разрывом связей, предпочитая более длинные слова. Чтобы сделать это быстро, мы поддерживаем приоритетную очередь размещения слов-кандидатов (реализованную в виде вектора векторов запросов, с вектором для каждого числа новых букв, содержащего раздел для каждой длины слова). Для каждого вновь добавленного письма мы ставим в очередь все места размещения кандидатов, которые проходят через это письмо.

Скомпилируйте и запустите rustc -O wordsearch.rs; ./wordsearch < google-10000-english.txt . На моем ноутбуке это работает за 70 секунд, используя 531 МБ ОЗУ.

Вывод помещается в прямоугольник с 248 столбцами и 253 строками.

Код

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 символов (248x219, заполнено на 50,2%)

^{(Публикация этого как нового ответа, потому что я хотел бы сохранить привязку к 1D, которую я изначально опубликовал в качестве ссылки)}

Это нагло срывает в большой степени многом ответом @ AndersKaseorg в его основной структуре, но имеет несколько настроек. Во-первых, я использую свою оригинальную программу для слияния строк, пока наилучшее доступное перекрытие не составит всего 3 символа. Затем я использую метод, описанный AndersKaseorg, для постепенного заполнения 2D-сетки с использованием этих сгенерированных строк. Ограничения тоже немного другие: он все еще пытается добавлять наименьшее количество символов каждый раз, но связи разрываются, отдавая предпочтение сначала квадратным сеткам, затем маленьким сеткам и, наконец, добавляя самое длинное слово.

Поведение, которое он отображает, заключается в чередовании периодов заполнения пространства и быстрого расширения сетки (к сожалению, в ней не хватает слов сразу после стадии быстрого расширения, поэтому вокруг краев много пустого пространства). Я подозреваю, что с некоторой настройкой функции стоимости это можно сделать, чтобы получить заполнение пространства лучше, чем 50%.

Здесь есть 2 исполняемых файла (чтобы избежать необходимости повторного запуска всего процесса при итеративном улучшении алгоритма). Вывод одного может быть передан непосредственно в другой:

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

И наконец, результат:

Альтернативный результат (после исправления нескольких ошибок в программе, которые смещали определенные направления и настраивали функцию стоимости, я получил более компактное, но менее оптимальное решение): 29275 символов, 198x195 (заполнено 75,8%):

Опять же, я мало что сделал для оптимизации этих программ, так что это занимает некоторое время. Но вы можете наблюдать, как он заполняет сетку, что довольно гипнотично.

C ++, 34191 символ «сетка» (при минимальном вмешательстве человека 6 или 7 могут быть легко сохранены)

Это следует рассматривать скорее как границу для 2D-случая, потому что ответ по-прежнему является 1D-строкой. Это просто мой код из предыдущего вызова, но с новой возможностью перевернуть любую строку. Это дает нам гораздо больше возможностей для объединения слов (особенно потому, что в худшем случае непересекающиеся суперструны составляют 26; по одной на каждую букву алфавита).

Для некоторой небольшой визуальной привлекательности в 2D он добавляет разрывы строк в результат, если он может сделать это бесплатно (то есть между словами с перекрытием 0).

Довольно медленно (до сих пор нет кэширования). Вот код:

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

Результат: http://pastebin.com/UTe2WMcz (на 4081 символ меньше, чем в предыдущем задании)

Совершенно очевидно, что можно добиться некоторой тривиальной экономии, если вертикальные линии xdи wvлинии пересекаются с линией монстра. Тогда hhidetautisbneuduiможно пересекать с d, и lxwwwowaxocnnaesddaс w. Это экономит 4 символа. nbcllilhnможет быть заменено на существующее sперекрытие (если оно может быть найдено), чтобы сохранить еще 2 (или просто 1, если такого перекрытия не существует, и оно должно быть добавлено по вертикали). Наконец, mjjrajaytqможно добавить куда-нибудь вертикально для сохранения 1. Это означает, что при минимальном вмешательстве человека можно сохранить 6–7 символов из результата.

Я хотел бы получить это в 2D с помощью следующего метода, но я изо всех сил пытаюсь найти способ реализовать его без создания алгоритма O (n ^ 4), который довольно непрактично вычислять!

1. Запустите алгоритм, как указано выше, но остановитесь на коротком, когда перекрытия достигают 1 символа
2. Несколько раз:
   1. Найдите группу из 4 слов, которые можно упорядочить в прямоугольник
   2. Добавьте как можно больше слов поверх этого прямоугольника, где каждое слово перекрывает как минимум 2 символа текущей фигуры (отметьте все 8 направлений) - это единственный этап, на котором мы действительно можем получить преимущество над текущим кодом
3. Объедините полученные сетки и одиночные слова, ища перекрытия из одной буквы каждый раз

PHP

этот выполняет работу теоретически; но 10000, вероятно, слишком много слов для рекурсии. Скрипт работает сейчас. (все еще работает 24 часа спустя)
отлично работает на небольших каталогах, но я могу сделать итерационную версию на следующей неделе.

$f=array("pen","op","po","ne","pro","aaa","abcd","dcba"); will output ABCD Apen arop ао .. although this is not an optimal result (scoring was changed ... I´m working on a generator). One optimal result is this: открытая .ra .oa dcba`

Это также не очень быстро; удаляет только подстроки и сортирует остатки по длине,
остальное - грубой силой: попробуйте вписать слова в прямоугольник, попробуйте на больший прямоугольник, если это не удастся.

Кстати: часть подстроки требует 4,5 минуты на моем компьютере для большого каталога
и сокращает его до 6 190 слов; сортировка по ним занимает 11 секунд.

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