Historia

Moja firma wysyła cotygodniowy biuletyn do wszystkich osób w firmie. W tych biuletynach znajduje się zagadka wraz z okrzykiem do kogokolwiek w firmie, który jako pierwszy wysłał e-maila / zapewnił rozwiązanie zagadki z zeszłego tygodnia. Większość z tych zagadek jest dość trywialna i naprawdę dość nudna dla firmy technologicznej, ale był jeden, kilka miesięcy temu, który przykuł moją uwagę.

Oryginalna zagadka:

Biorąc pod uwagę poniższy kształt:

Masz liczby naturalne od 1 do 16. Dopasuj je wszystkie do tego kształtu, tak aby wszystkie ciągłe rzędy i ciągłe kolumny sumowały się do 29.

Na przykład jedno takie rozwiązanie tej układanki (które było rozwiązaniem „kanonicznym”, które przesłałem do newslettera) było następujące:

Jednak w trakcie jego rozwiązywania znalazłem dość interesujące informacje:

• Istnieje znacznie więcej rozwiązań niż tylko jedno; w rzeczywistości istnieje 9 368 rozwiązań.
• Jeśli rozszerzysz zestaw reguł, aby wymagać tylko, aby wiersze i kolumny były sobie równe, niekoniecznie 29, otrzymasz 33 608 rozwiązań:
  • 4440 rozwiązań za sumę 27.
  • 7400 rozwiązań za sumę 28.
  • 9 368 Rozwiązania za sumę 29.
  • 6 096 Rozwiązania za sumę 30.
  • 5 104 Rozwiązania za sumę 31.
  • 1200 rozwiązań za sumę 32.

Więc ja i moi współpracownicy (choć głównie tylko mój menedżer, ponieważ był jedyną osobą poza mną z umiejętnościami programowania „ogólnego przeznaczenia”) podjąłem wyzwanie, które trwało przez większą część miesiąca - mieliśmy inną, faktyczną pracę - powiązane obowiązki, które musieliśmy wykonać - aby spróbować napisać program, który znalazłby każde rozwiązanie w najszybszy możliwy sposób.

Oryginalne statystyki

Pierwszy program, który napisałem w celu rozwiązania problemu, po prostu sprawdzał losowe rozwiązania w kółko i zatrzymywał się, gdy znalazł rozwiązanie. Jeśli przeprowadziłeś analizę matematyczną tego problemu, prawdopodobnie już wiesz, że to nie powinno działać; ale jakoś miałem szczęście i zajęło programowi tylko minutę, aby znaleźć jedno rozwiązanie (to, które zamieściłem powyżej). Powtarzanie uruchomień programu często trwało nawet 10 lub 20 minut, więc oczywiście nie było to rygorystyczne rozwiązanie problemu.

Przeszedłem na rozwiązanie rekurencyjne, które powtarzało się przez każdą możliwą permutację układanki i odrzuciłem wiele rozwiązań na raz, eliminując sumy, które się nie sumowały. IE, jeśli pierwszy wiersz / kolumna, którą porównywałem, nie były już równe, mógłbym natychmiast przestać sprawdzać tę gałąź, wiedząc, że nic innego permutowanego w układankę by tego nie zmieniło.

Korzystając z tego algorytmu, osiągnąłem pierwszy „właściwy” sukces: program mógł wygenerować i wypluć wszystkie 33 608 rozwiązań w około 5 minut.

Mój kierownik miał inne podejście: wiedząc na podstawie mojej pracy, że jedyne możliwe rozwiązania miały sumy 27, 28, 29, 30, 31 lub 32, napisał rozwiązanie wielowątkowe, które sprawdzało możliwe sumy tylko dla tych konkretnych wartości. Udało mu się uruchomić program w zaledwie 2 minuty. Więc powtórzyłem ponownie; Hashowałem wszystkie możliwe sumy 3/4 cyfr (na początku programu; jest to liczone w całkowitym czasie wykonywania) i użyłem „częściowej sumy” wiersza do wyszukania pozostałej wartości na podstawie wcześniej ukończonego wiersza, a nie testowanie wszystkich pozostałych wartości i skrócenie czasu do 72 sekund. Potem z pewną logiką wielowątkowości zredukowałem ją do 40 sekund. Mój menedżer zabrał program do domu, przeprowadził optymalizację jego działania i obniżył go do 12 sekund. Zmieniłem kolejność oceny wierszy i kolumn,

Najszybsze którekolwiek z nas dostało nasze programy po miesiącu wynosiło 0,15 sekundy dla mojego menedżera i 0,33 sekundy dla mnie. Skończyło się jednak twierdzeniem, że mój program był szybszy, odkąd program mojego menedżera, podczas gdy go znalazł wszystkie rozwiązania, nie drukował ich w pliku tekstowym. Jeśli dodał tę logikę do swojego kodu, często zajmowało to 0,4-0,5 sekundy.

Od tamtej pory pozwoliliśmy sobie na przetrwanie w naszym osobistym wyzwaniu, ale oczywiście pozostaje pytanie: może ten program można przyspieszyć?

To wyzwanie, które zamierzam wam postawić.

Twoje wyzwanie

Parametry, nad którymi pracowaliśmy, złagodziły zasadę „suma 29”, aby zamiast tego były „równe sumom wszystkich wierszy / kolumn”, i dla was również ustawię tę regułę. Wyzwanie jest zatem następujące: Napisz program, który znajdzie (i drukuje!) Wszystkie rozwiązania tej zagadki w najkrótszym możliwym czasie. Zamierzam wyznaczyć pułap zgłaszanych rozwiązań: jeśli program zajmuje więcej niż 10 sekund na stosunkowo przyzwoitym komputerze (<8 lat), prawdopodobnie jest zbyt wolny, aby go policzyć.

Mam też kilka bonusów za układankę:

• Czy możesz uogólnić rozwiązanie tak, aby działało ono dla dowolnego zestawu 16 liczb, nie tylko int[1,16] ? Wynik pomiaru czasu byłby oceniany na podstawie oryginalnego zestawu numerów podpowiedzi, ale przekazywany przez tę ścieżkę kodową. (-10%)
• Czy potrafisz napisać kod w sposób, który z wdziękiem obsługuje i rozwiązuje za pomocą zduplikowanych liczb? To nie jest tak proste, jak mogłoby się wydawać! Rozwiązania „wizualnie identyczne” powinny być unikalne w zestawie wyników. (-5%)
• Czy potrafisz obsłużyć liczby ujemne? (-5%)

Możesz także spróbować wygenerować rozwiązanie, które obsługuje liczby zmiennoprzecinkowe, ale oczywiście nie wstrząśnij, jeśli zawiedzie całkowicie. Jeśli znajdziesz solidne rozwiązanie, może być warta dużej premii!

Pod każdym względem „Obroty” są uważane za unikalne rozwiązania. Tak więc rozwiązanie będące tylko rotacją innego rozwiązania liczy się jako rozwiązanie własne.

IDE, które mam na komputerze, to Java i C ++. Mogę przyjmować odpowiedzi z innych języków, ale może być konieczne podanie linku do strony, w której mogę uzyskać łatwe do skonfigurowania środowisko wykonawcze dla Twojego kodu.

C - blisko 0,5 sek

Ten bardzo naiwny program daje wszystkie rozwiązania w pół sekundy na moim 4-letnim laptopie. Bez wielowątkowości, bez mieszania.

Windows 10, Visual Studio 2010, rdzeń procesora I7 64 bit

Wypróbuj online na ideone

#include <stdio.h>
#include <time.h>

int inuse[16];
int results[16+15+14];

FILE *fout;

int check(int number)
{
    if (number > 0 && number < 17 && !inuse[number-1])
    {
        return inuse[number-1]=1;
    }
    return 0;
}

void free(int number)
{
    inuse[number-1]=0;
}

void out(int t, int* p)
{
    int i;
    fprintf(fout, "\n%d",t);
    for(i=0; i< 16; i++) fprintf(fout, " %d",*p++);
}

void scan() 
{
    int p[16];
    int t,i;
    for (p[0]=0; p[0]++<16;) if (check(p[0]))
    {
        for (p[1]=0; p[1]++<16;) if (check(p[1]))
        {
            for (p[2]=0; p[2]++<16;) if (check(p[2]))
            {
                t = p[0]+p[1]+p[2]; // top horiz: 0,1,2
                for (p[7]=0; p[7]++<16;) if (check(p[7]))
                {
                    if (check(p[11] = t-p[7]-p[2])) // right vert: 2,7,11
                    {
                        for(p[9]=0; p[9]++<16;) if (check(p[9]))
                        {
                            for (p[10]=0; p[10]++<16;) if (check(p[10]))
                            {
                                if (check(p[12] = t-p[9]-p[10]-p[11])) // right horiz: 9,10,11,12
                                {
                                    for(p[6]=0; p[6]++<16;) if (check(p[6]))
                                    {
                                        if (check(p[15] = t-p[0]-p[6]-p[9])) // middle vert: 0,6,9,15
                                        {
                                            for(p[13]=0; p[13]++<16;) if (check(p[13]))
                                            {
                                                if (check(p[14] = t-p[13]-p[15])) // bottom horiz:  13,14,15
                                                {
                                                    for(p[4]=0; p[4]++<16;) if (check(p[4]))
                                                    {
                                                        if (check(p[8] = t-p[4]-p[13])) // left vert: 4,8,13
                                                        {
                                                            for(p[3]=0; p[3]++<16;) if (check(p[3]))
                                                            {
                                                                if (check(p[5] = t-p[3]-p[4]-p[6])) // left horiz: 3,4,5,6
                                                                {
                                                                    ++results[t];
                                                                    out(t,p);
                                                                    free(p[5]);
                                                                }
                                                                free(p[3]);
                                                            }
                                                            free(p[8]);
                                                        }
                                                        free(p[4]);
                                                    }
                                                    free(p[14]);
                                                }
                                                free(p[13]);
                                            }
                                            free(p[15]);
                                        }
                                        free(p[6]);
                                    }
                                    free(p[12]);
                                }
                                free(p[10]);
                            }
                            free(p[9]);
                        }
                        free(p[11]);
                    }
                    free(p[7]);
                }    
                free(p[2]);
            } 
            free(p[1]);
        }
        free(p[0]);
    }
    for(i=0;i<15+16+14;i++)
    {
        if(results[i]) printf("%d %d\n", i, results[i]);
    }
}

void main()
{
    clock_t begin, end;
    double time_spent;
    begin = clock();

    fout = fopen("c:\\temp\\puzzle29.txt", "w");
    scan();
    fclose(fout);

    end = clock();
    time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    printf("Time %g sec\n", time_spent);
}

C ++ - 300 milisekund

Na żądanie dodałem własny kod, aby rozwiązać tę zagadkę. Na moim komputerze trwa on średnio 0,310 sekundy (310 milisekund), ale w zależności od wariancji może działać tak szybko, jak 287 milisekund. Bardzo rzadko widzę, jak wzrasta powyżej 350 milisekund, zwykle tylko wtedy, gdy mój system jest obciążony innym zadaniem.

Czasy te oparte są na autoreportowaniu zastosowanym w programie, ale przetestowałem również przy użyciu zewnętrznego timera i otrzymałem podobne wyniki. Narzut w programie wydaje się dodawać około 10 milisekund.

Również mój kod nie dość obsługiwać duplikaty poprawnie. Może rozwiązać je, ale nie eliminuje „wizualnie identycznych” rozwiązań z zestawu rozwiązań.

#include<iostream>
#include<vector>
#include<random>
#include<functional>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<thread>
#include<chrono>
#include<fstream>
#include<iomanip>
#include<string>
#include<mutex>
#include<queue>
#include<sstream>
#include<utility>
#include<atomic>
#include<algorithm>

//#define REDUCE_MEMORY_USE

typedef std::pair<int, std::vector<std::pair<int, int>>> sumlist;
typedef std::unordered_map<int, std::vector<std::pair<int, int>>> summap;
typedef std::array<int, 16> solution_space;

class static_solution_state {
public:
    std::array<int, 16> validNumbers;
    summap twosums;
    size_t padding;
    std::string spacing;

    static_solution_state(const std::array<int, 16> & _valid);

    summap gettwovaluesums();
    std::vector<sumlist> gettwovaluesumsvector();
};

static_solution_state::static_solution_state(const std::array<int, 16> & _valid) 
    : validNumbers(_valid) {
    twosums = gettwovaluesums();
    padding = 0;
    for (int i = 0; i < 16; i++) {
        size_t count = std::to_string(validNumbers[i]).size();
        if (padding <= count) padding = count + 1;
    }
    spacing.resize(padding, ' ');
}

class solution_state {
private:
    const static_solution_state * static_state;
public:
    std::array<int, 16> currentSolution;
    std::array<bool, 16> used;
    std::array<int, 7> sums;
    size_t solutions_found;
    size_t permutations_found;
    size_t level;
    std::ostream * log;

    solution_state(const static_solution_state & _sstate);
    solution_state(static_solution_state & _sstate) = delete;
    void setLog(std::ostream & out);
    const int & operator[](size_t index) const;

};

solution_state::solution_state(const static_solution_state & _sstate) {
    static_state = &_sstate;
    sums = { 0 };
    used = { false };
    currentSolution = { -1 };
    solutions_found = 0;
    permutations_found = 0;
    level = 0;
}

void solution_state::setLog(std::ostream & out) {
    log = &out;
}

const int & solution_state::operator[](size_t index) const {
    return static_state->validNumbers[currentSolution[index]];
}

int getincompletetwosum(const static_solution_state & static_state, const solution_state & state);
void permute(const static_solution_state & static_state, solution_state & state, volatile bool & reportProgress, const volatile size_t & total_tests, volatile bool & done);
void setupOutput(std::fstream & out);
void printSolution(const static_solution_state & static_state, const solution_state & state);
constexpr size_t factorial(const size_t iter);

const bool findnext2digits[16]{
    false, false, false,
    true, false,
    false, true, false,
    true, false,
    true, false,
    true, false,
    true, false
};

const int currentsum[16]{
    0, 0, 0,
    1, 1,
    2, 2, 2,
    3, 3,
    4, 4,
    5, 5,
    6, 6
};

const int twosumindexes[7][2]{
    { 0, -1},
    { 2, -1},
    { 5, -1},
    { 5, -1},
    { 0,  7},
    { 11, 4},
    { 10, 9}
};

const std::array<size_t, 17> facttable = [] {
    std::array<size_t, 17> table;
    for (int i = 0; i < 17; i++) table[i] = factorial(i);
    return table;
}();

const int adj = 1;

std::thread::id t1id;

int main(int argc, char** argv) {
    //std::ios_base::sync_with_stdio(false);
    std::array<int, 16> values = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16 };
    if (argc == 17) {
        for (int i = 0; i < 16; i++) {
            values[i] = atoi(argv[i + 1]);
        }
    }
    auto start = std::chrono::high_resolution_clock::now();
    const static_solution_state static_state(values);
#if defined(REDUCE_MEMORY_USE)
    const int num_of_threads = max(1u, min(thread::hardware_concurrency(), 16u));
#else
    const int num_of_threads = 16;
#endif
    std::vector<solution_state> states(num_of_threads, static_state);
    for (int i = 0; i < num_of_threads; i++) {
        int start = i * 16 / num_of_threads;
        states[i].permutations_found += start * factorial(16) / 16;
    }
    std::fstream out;
    setupOutput(out);
    std::locale loc("");
    std::cout.imbue(loc);
    volatile bool report = false;
    volatile bool done = false;
    volatile size_t tests = 0;

    std::thread progress([&]() {
        auto now = std::chrono::steady_clock::now();
        while (!done) {
            if (std::chrono::steady_clock::now() - now > std::chrono::seconds(1)) {
                now += std::chrono::seconds(1);

                size_t t_tests = 0;
                for (int i = 0; i < num_of_threads; i++) t_tests += states[i].permutations_found - i * factorial(16) / num_of_threads;
                tests = t_tests;
                report = true;
            }
            std::this_thread::yield();
        }
    });

    if (num_of_threads <= 1) {


        states[0].setLog(out);
        permute(static_state, states[0], report, tests, done);


    } 
    else {
        std::vector<std::thread> threads;
#if defined(REDUCE_MEMORY_USE)
        std::vector<std::fstream> logs(num_of_threads);
#else
        std::vector<std::stringstream> logs(num_of_threads);
#endif
        for (int i = 0; i < num_of_threads; i++) {
            threads.emplace_back([&, i]() {
                if (i == 0) t1id = std::this_thread::get_id();
                int start = i * 16 / num_of_threads;
                int end = (i + 1) * 16 / num_of_threads;
#if defined(REDUCE_MEMORY_USE)
                logs[i].open("T"s + to_string(i) + "log.tmp", ios::out);
#endif
                logs[i].imbue(loc);
                states[i].setLog(logs[i]);

                for (int j = start; j < end; j++) {


                    states[i].currentSolution = { j };
                    states[i].level = 1;
                    states[i].used[j] = true;
                    permute(static_state, states[i], report, tests, done);


                }
            });
        }

        std::string buffer;
        for (int i = 0; i < num_of_threads; i++) {
            threads[i].join();
#if defined(REDUCE_MEMORY_USE)
            logs[i].close();
            logs[i].open("T"s + to_string(i) + "log.tmp", ios::in);
            logs[i].seekg(0, ios::end);
            auto length = logs[i].tellg();
            logs[i].seekg(0, ios::beg);
            buffer.resize(length);
            logs[i].read(&buffer[0], length);
            logs[i].close();
            remove(("T"s + to_string(i) + "log.tmp").c_str());
            out << buffer;
#else
            out << logs[i].str();
#endif
        }
    }
    done = true;
    out.close();

    if (num_of_threads > 1) {
        size_t t_tests = 0;
        for (int i = 0; i < num_of_threads; i++) t_tests += states[i].permutations_found - i * factorial(16) / num_of_threads;
        tests = t_tests;
    }

    size_t solutions = 0;
    for (const auto & state : states) {
        solutions += state.solutions_found;
    }

    auto end = std::chrono::high_resolution_clock::now();

    progress.join();

    auto duration = end - start;
    auto secondsDuration = std::chrono::duration_cast<std::chrono::milliseconds>(duration);
    std::cout << "Total time to process all " << tests << " results: " << std::setprecision(3) << std::setiosflags(std::ostream::fixed) << (secondsDuration.count()/1000.0) << "s" << "\n";
    std::cout << "Solutions found: " << solutions << std::endl;
    //system("pause");
    return 0;
}

void permute(const static_solution_state & static_state, solution_state & state, volatile bool & reportProgress, const volatile size_t & total_tests, volatile bool & done) {
    if (done) return;
    if (state.level >= 16) {
        if (reportProgress) {
            reportProgress = false;
            std::cout << "Current Status:" << "\n";
            std::cout << "Test " << total_tests << "\n";
            std::cout << "Contents: {";
            for (int i = 0; i < 15; i++) std::cout << std::setw(static_state.padding - 1) << state[i] << ",";
            std::cout << std::setw(static_state.padding - 1) << state[15] << "}" << "(Partial Sum: " << state.sums[0] << ")" << "\n";
            std::cout << "=====================" << "\n";
        }
        printSolution(static_state,state);
        state.solutions_found++;
        state.permutations_found++;
    }
    else {
        if (state.level == 3) state.sums[0] = state[0] + state[1] + state[2];

        if (!findnext2digits[state.level]) {
            for (int i = 0; i < 16; i++) {
                if (!state.used[i]) {
                    state.currentSolution[state.level] = i;
                    state.used[i] = true;
                    state.level++;
                    permute(static_state, state, reportProgress, total_tests, done);
                    state.level--;
                    state.used[i] = false;
                }
            }
        }
        else {
            int incompletetwosum = getincompletetwosum(static_state, state);
            if (static_state.twosums.find(incompletetwosum) == static_state.twosums.end()) {
                state.permutations_found += facttable[16 - state.level];
            }
            else {
                size_t successes = 0;
                const std::vector<std::pair<int, int>> & potentialpairs = static_state.twosums.at(incompletetwosum);
                for (const std::pair<int, int> & values : potentialpairs) {
                    if (!state.used[values.first] && !state.used[values.second]) {
                        state.currentSolution[state.level] = values.first;
                        state.currentSolution[state.level + 1] = values.second;
                        state.used[values.first] = true;
                        state.used[values.second] = true;
                        state.level += 2;
                        permute(static_state, state, reportProgress, total_tests, done);
                        state.level -= 2;
                        state.used[values.first] = false;
                        state.used[values.second] = false;

                        successes++;
                    }
                }
                state.permutations_found += facttable[16 - state.level - 2] * ((16 - state.level) * (15 - state.level) - successes); 
            }
        }
    }
}

int getincompletetwosum(const static_solution_state & static_state, const solution_state & state) {
    int retvalue = state.sums[0];
    int thissum = currentsum[state.level];
    for (int i = 0; i < 2 && twosumindexes[thissum][i] >= 0; i++) {
        retvalue -= state[twosumindexes[thissum][i]];
    }
    return retvalue;
}

constexpr size_t factorial(size_t iter) {
    return (iter <= 0) ? 1 : iter * factorial(iter - 1);
}

void setupOutput(std::fstream & out) {
    out.open("puzzle.txt", std::ios::out | std::ios::trunc);
    std::locale loc("");
    out.imbue(loc);
}

void printSolution(const static_solution_state & static_state, const solution_state & state) {
    std::ostream & out = *state.log;
    out << "Test " << state.permutations_found << "\n";
    static const auto format = [](std::ostream & out, const static_solution_state & static_state, const solution_state & state, const std::vector<int> & inputs) {
        for (const int & index : inputs) {
            if (index < 0 || index >= 16) out << static_state.spacing;
            else out
                << std::setw(static_state.padding)
                << state[index];
        }
        out << "\n";
    };
    format(out, static_state, state, { -1, -1, -1,  0,  1,  2 });
    format(out, static_state, state, { 15,  9, 14, 10, -1,  3 });
    format(out, static_state, state, { -1,  8, -1, 11, 12,  4, 13 });
    format(out, static_state, state, { -1,  5,  6,  7});

    out << "Partial Sum: " << (state.sums[0]) << "\n";
    out << "=============================" << "\n";
}

summap static_solution_state::gettwovaluesums() {
    summap sums;
    for (int i = 0; i < 16; i++) {
        for (int j = 0; j < 16; j++) {
            if (i == j) continue;
            std::pair<int,int> values( i, j );
            int sum = validNumbers[values.first] + validNumbers[values.second];
            sums[sum].push_back(values);
        }
    }
    return sums;
}

std::vector<sumlist> static_solution_state::gettwovaluesumsvector() {
    std::vector<sumlist> sums;
    for (auto & key : twosums) {
        sums.push_back(key);
    }

    std::sort(sums.begin(), sums.end(), [](sumlist a, sumlist b) {
        return a.first < b.first;
    });
    return sums;
}

Prolog - 3 minuty

Ten rodzaj układanki wydaje się idealnym przykładem użycia dla Prologa. Więc stworzyłem rozwiązanie w Prologu! Oto on:

:- use_module(library(clpfd)).

puzzle(P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15) :-
    Vars = [P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15],
    Vars ins 1..16,
    all_different(Vars),
    29 #= P0 + P1 + P2,
    29 #= P3 + P4 + P5 + P6,
    29 #= P9 + P10 + P11 + P12,
    29 #= P13 + P14 + P15,
    29 #= P0 + P6 + P9 + P15,
    29 #= P2 + P7 + P11,
    29 #= P4 + P8 + P13.

Niestety nie jest tak szybki, jak się spodziewałem. Może ktoś bardziej obeznany z programowaniem deklaratywnym (lub konkretnie Prologiem) może zaoferować kilka wskazówek dotyczących optymalizacji. Możesz wywołać regułę puzzleza pomocą następującego polecenia:

time(aggregate_all(count, (puzzle(P0, P1, P2, P3, P4, P5, P6, P7, P8, P9, P10, P11, P12, P13, P14, P15), labeling([leftmost, up, enum], [P9, P15, P13, P0, P4, P2, P6, P11, P1, P5, P3, P7, P14, P12, P10, P8])), Count)).

Wypróbuj online tutaj . Możesz podstawić dowolną liczbę zamiast 29s w kodzie, aby wygenerować wszystkie rozwiązania. Na obecnym etapie wszystkie 29 rozwiązań znajduje się w około 30 sekund, więc znalezienie wszystkich możliwych rozwiązań powinno zająć około 3 minut.