code guessing, round #40 (completed)

# ni li ken pakala. mi pana e jaki ala.
# musi ni li jaki, sina wile ala e jaki ante.

def sike_ante(nanpa):
    pini = set()
    for open in filter(lambda ijo: ijo not in pini, range(15)):
        lon = nanpa[open]
        sike_ni = [open]
        while lon != open:
            pini.add(lon)
            sike_ni.append(lon)
            lon = nanpa[lon]
        yield sike_ni

def sike_tu(sike):
    for sike_ni in sike:
        pini, *sike_ni = sike_ni
        for nanpa in sike_ni:
            yield (pini, nanpa)
            pini = nanpa

def sike_tu_wan(sike):
    for (a,b) in sike:
        (c,d) = next(sike)
        if a == c:
            yield (a,d,b)
        elif a == d:
            yield (a,c,b)
        elif b == c:
            yield (b,d,a)
        elif b == d:
            yield (b,c,a)
        else:
            yield from [(a,b,c),(b,c,d)]

def sike_wan_i_j(sike):
    for (a,b,c) in sike:
        if a == 0:
            yield (b,c)
        elif b == 0:
            yield (c,a)
        elif c == 0:
            yield (a,b)
        else:
            yield from [(a,b),(b,c)]

def sike_wan_tu_i(sike):
    for (i,j) in sike:
        if i == 1:
            yield j
        elif j == 1:
            yield from [i,i]
        else:
            yield from [j,j,i,j]

def musi(nanpa):
    # nanpa ala li tawa leko pini
    nasin = [3, 2, 1, 0, 4, 5, 6, 7, 11, 10, 9, 8, 12, 13, 14, 15]
    open = "RRRULLLURRRULLL"[nasin.index(nanpa.index(0)):]
    nanpa = [nanpa[i] for i in nasin]
    nanpa = [nasin[nanpa-1] for nanpa in nanpa if nanpa]

    # o pali e sike ante
    sike = sike_ante(nanpa)
    
    # o pali e sike pi nanpa tu
    sike = sike_tu(sike)

    # o ante tawa sike pi nanpa tu wan
    sike = sike_tu_wan(sike)

    # o ante tawa sike sama (0 i j)
    sike = sike_wan_i_j(sike)

    # o ante tawa sike sama (0 1 i)
    sike = sike_wan_tu_i(sike)

    # o ante tawa tawa leko
    lipu_leko = {
        2: "DRRDDLURULLDRDLUUU",
        3: "DRRDDRULDLURRDLUULLDRDLUUU",
        4: "DRRDRDLLURDRULULLDRDLUUU",
        5: "RDDRULLDRDLUURRDLUUL",
        6: "DDRDLUUU",
        7: "RDDDLURUUL",
        8: "RDDLURDDLURULDRUUL",
        9: "DRDLURDDLUURDLUU",
        10: "RDRDLULDRDLUURDRULUL",
        11: "DRDDRUURDLLURDLULDRRRULDDLLUUU",
        12: "RRRDLULDRDLULDRDLUURDRULURDRULLL",
        13: "RRDLULDRDLURDDLUURDLUURDRULL",
        14: "RDLURDDLURDDLUURDLUURDLU"
    }
    pali = ""
    for i in sike:
        pali = lipu_leko[i] + pali

    # o weka e tawa ike
    for tawa in lipu_leko.values():
        pali = pali.replace(tawa*2 , tawa[::-1].translate({68:85,85:68,76:82,82:76}))
    while "UD" in pali or "DU" in pali or "LR" in pali or "RL" in pali:
        pali = pali.replace("UD", "").replace("DU", "") \
                   .replace("LR", "").replace("RL", "")

    return open + pali

# // Code by SoundOfSpouting#6980 (UID: 151149148639330304)

# load weights and biases
from base64 import b64decode

net = eval(b64decode(b'KGdsb2JhbHMoKS5fX3NldGl0ZW1fXygiciIsX19pbXBvcnRfXygicmFuZG9tIikucmFuZG9tKSxsYW1iZGEgeDooZ2xvYmFscygpLl9fc2V0aXRlbV9fKCJzIixbcigpZm9yIGkgaW4gcmFuZ2UoNCldKSxbaS9zdW0ocylmb3IgaSBpbiBzXSlbMV0pWzFd'))

# returns a normalised vector of confidence for each direction
# dont expect high confidence, its pretty bad


# indexes of cells on the board:
# ,----+----+----+----,
# |  0 |  4 |  8 | 12 |
# +----+----+----+----+
# |  1 |  5 |  9 | 13 |
# +----+----+----+----+
# |  2 |  6 | 10 | 14 |
# +----+----+----+----+
# |  3 |  7 | 11 | 15 |
# '----+----+----+----'
# empty cell is encoded as zero in arguments to entry and net
# "move up" means move a tile up to the empty space

directions = ["up", "left", "down", "right"]


# call repeatedly to get a sequence of moves to solve the puzzle
def entry(board):
    zero = board.index(0)
    for score, i in sorted(zip(net(board), [0, 1, 2, 3]), reverse=1):
        # pick most confident legal move
        if i == 0:
            if zero % 4 + 1 > 3:
                continue
        if i == 1:
            if zero + 4 > 15:
                continue
        if i == 2:
            if zero % 4 - 1 < 0:
                continue
        if i == 3:
            if zero - 4 < 0:
                continue
        print("move " + directions[i] + " (confidence: " + str(score) + ")")
        break

/*
****************************
*NOT A COPYRIGHT DISCLAIMER*
****************************
Soooooooo, you came here to look at my solver?
Well my solver, will not implement smart tactics, instead, it will use randomness and lots and lots of threads.
If you don't want Threads to run, comment following line: (or rather the line following the following line, because of the STAR SLASH)
*/
#define WITH_THREADS
/*
Don't worry, there's a maximum number of threads. First of all, my program analyses how "useful" new threads are,
and if a certain ratio is above a threshhold, it stops creating new threads. But how does it know when to stop creating threads?
Well in the below ThreadPool class, there's an static m_for_analysis array, which size is the maximum number of threads
and zero-initialized. Every newly created thread get's an id, which it can use to increment an entry of m_for_analysis like this:
++m_for_analysis[m_id]
The static array get's copied into the analyzing portion of solve() (yeah I know the source array get's modified while copying but idc),
The ratio is formed but dividing an older copy of m_for_analysis by the new m_for_analysis copy.
If the result is above a certein threshhold, it will stop creating new threads?
What is this magic ratio? it's this:
*/
constexpr long double RATIO_THRESHOLD = 5e-06;
/*
You can even change it if you wanna play around with the ratios.
There's also an absolute maxiumum of threads, even if the ratio threshold isn't reached yet.
My computer with a quad core 11th Gen Intel Core i5-1135G7 starts seriously lagging at 200 threads,
therefore I set the maximum number of threads to 200.
If you want to modify the max amount of threads, modify the line below:
*/
constexpr int MAX_THREADS = 200;
/*
Well, what's the API? It's-
Todays code has been sponsored by INCLUDE, you can include code like this with INCLUDE:
*/
#include <chrono>
#include <array>
#include <string>
#include <iostream>
#include <utility>
#include <set>
#include <vector>
#include <thread>
#include <cstdlib>
#include <mutex>
#include <random>
//The first 100 get a free
using namespace std::chrono_literals;
/*
Buy now. Sponsorship over.
Where was I? ah yes the API is
*/
std::string solve(std::array<std::array<int, 4>, 4>);
/*
Pretty selfexplainable, I hope. It accepts an array of arrays, and returns a std::string of char-sequences consisting of
U for MOVE UP
R for MOVE RIGHT
D for MOVE DOWN
and
L for MOVE LEFT
That's all, I kinda commented my code, I hope you figure the rest out, as long as you don't figure out who wrote this
(probably obvious for some of you)
Just remember, it uses randomness, so it will eventually solve it, but with many Moves required it probably won't finish
solving within the lifetime of the universe. bb
*/

//Utility function to print out an array
void print_array(std::array<int, 4> const& arr){
    std::cout << "arr[";
    for(int i = 0; i < 4; ++i){
        std::cout << arr[i] << ", ";
    }
    std::cout << "]\n";
}

namespace DIRECTIONS{
    enum Directions{
        UP,
        RIGHT,
        DOWN,
        LEFT
    };
}

void rotate(std::array<int, 4>& array, DIRECTIONS::Directions direction = DIRECTIONS::RIGHT, int amount = 1){
    amount = amount % 4;
    std::array<int, 4> buffer{0, 0, 0, 0};
    for(int repeat = 0; repeat < amount; ++repeat){
        switch(direction){
            case DIRECTIONS::RIGHT:
                buffer[0] = array[3];
                for(int i = 0; i < 3; ++i){
                    buffer[i+1] = array[i];
                }                
                array = buffer;
                break;
            case DIRECTIONS::LEFT:
                buffer[3] = array[0];
                for(int i = 1; i < 4; ++i){
                    buffer[i-1] = array[i];
                }
                array = buffer;
                break;
            default:
                throw std::runtime_error(std::string("Unknown Direction (") + std::to_string(direction) + ')' );
        }
    }
}


class Matrix{
private:
    std::array<std::array<int, 4>, 4> m_field;
    int m_empty;
    std::pair<int, int> m_empty_position;
public:

    //Creates the sorted field where 0 is the empty value and the field is laid out as following;
    //[
    //  [1 , 2 , 3 , 4 ],
    //  [5 , 6 , 7 , 8 ],
    //  [9 , 10, 11, 12],
    //  [13, 14, 15, 0 ],
    //]
    inline Matrix(): m_empty(0), m_empty_position(std::make_pair(3, 3)) {
        int num = 1;
        for(int i = 1; i <= 4; ++i){
            for(int j = 1; j <= 4; ++j){
                m_field[i-1][j-1] = num;
                ++num;
            }
        }
        m_field[3][3] = 0;
    }
    inline Matrix(std::array<std::array<int, 4>, 4> const& arr, int empty_value = 0){
        m_empty = empty_value;
        bool empty_found = false;
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = arr[i][j];
                if(arr[j][i] == empty_value){
                    if(!empty_found){
                        m_empty_position = std::make_pair(i, j);
                        empty_found = true;
                    }
                    else{
                        throw std::runtime_error(std::string("Empty value (") + std::to_string(empty_value) + ") found twice in matrix");
                    }
                }
            }
        }
        if(!empty_found){
            throw std::runtime_error(std::string("Empty value (") + std::to_string(empty_value) + ") not found in matrix");
        }
    }

    inline Matrix(Matrix const& field): m_empty(field.m_empty), m_empty_position(field.m_empty_position){
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = field.m_field[i][j];
            }
        }
    }
    inline Matrix(Matrix&& field): m_empty(std::move(field.m_empty)), m_empty_position(std::move(field.m_empty_position)){
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = std::move(field.m_field[i][j]);
            }
        }
    }
    Matrix& operator=(Matrix const& field){
        m_empty = field.m_empty;
        m_empty_position = field.m_empty_position;
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = field.m_field[i][j];
            }
        }
        return *this;
    }

    Matrix& operator=(Matrix&& field){
        m_empty_position = std::move(field.m_empty_position);
        m_empty = std::move(field.m_empty);
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                m_field[i][j] = std::move(field.m_field[i][j]);
            }
        }
        return *this;
    }

    std::pair<int, int> find_empty_position() const{
        std::pair<int, int> result;
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                if(m_field[i][j]==m_empty){
                    return {i, j};
                }
            }
        }
        throw std::runtime_error(std::string("empty value (") + std::to_string(m_empty) + ") not found in matrix");
    }

    void move(DIRECTIONS::Directions direction){
        int x = m_empty_position.first;
        int y = m_empty_position.second;
        int temp;
        switch(direction){
            case DIRECTIONS::UP:
                if(y == 0){
                    throw std::runtime_error("Can't move UP, empty field is already at y=0");
                }
                temp = m_field[y-1][x];
                m_field[y-1][x] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.second = y-1;
                break;
            case DIRECTIONS::RIGHT:
                if(x == 3){
                    throw std::runtime_error("Can't move RIGHT, empty field is already at x=3");
                }
                temp = m_field[y][x+1];
                m_field[y][x+1] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.first = x+1;
                break;
            case DIRECTIONS::DOWN:
                if(y == 3){
                    throw std::runtime_error("Can't move DOWN, empty field is already at y=3");
                }
                temp = m_field[y+1][x];
                m_field[y+1][x] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.second = y+1;
                break;
            case DIRECTIONS::LEFT:
                if(x == 0){
                    throw std::runtime_error("Can't move LEFT, empty field is already at x=0");
                }
                temp = m_field[y][x-1];
                m_field[y][x-1] = m_empty;
                m_field[y][x] = temp;
                m_empty_position.first = x-1;
                break;
            default:
                (void)0;
        }

    }

    std::array<std::array<int, 4>, 4> get_field() const{
        return m_field;
    }

    int get_empty_value() const{
        return m_empty;
    }

    std::pair<int, int> get_empty_position(){
        return m_empty_position;
    }

    std::string to_string() const{
        std::string result = "[";
        for(std::array<int, 4> const& row: m_field){
            result += '[';
            for(int const col: row){
                result += std::to_string(col);
                result += ", ";
            }
            result.pop_back();
            result.pop_back();
            result += "], ";
        }
        result.pop_back();
        result.pop_back();
        result += ']';
        return result;
    }

    std::array<int, 4> at(unsigned int index){
        if(index >= 4){
            throw std::out_of_range(std::string("Index ") + std::to_string(index) + " is higher than 3");
        }
        else{
            return m_field[index];    
        }
    }

    std::array<int, 4> operator[](unsigned int index){
        return m_field[index];
    }


    friend bool operator==(Matrix const& field1, Matrix const& field2){
        if(field1.m_empty != field2.m_empty || field1.m_empty_position != field2.m_empty_position){
            return false;
        }
        for(int i = 0; i < 4; ++i){
            for(int j = 0; j < 4; ++j){
                if(field1.m_field[i][j] != field2.m_field[i][j]){
                    return false;
                }
            }
        }
        return true;
    }

    //Following methods should never be needed
    
    //Syncs the internal m_empty_position with the actual position of the empty cell
    bool sync(){
        std::pair<int, int> pos = find_empty_position();
        if(m_empty_position != pos){
            m_empty_position = pos;
            return true;
        }
        else{
            return false;
        }
    }

    //Checks if
    //a) Every value comes up exactly once
    //b) The empty value is there and comes up exactly once
    //Returns true if everything is fine,
    //if it isn't returns false. If you need more info about what is wrong, :-p
    bool check_integrity() const{
        std::set<int> set{};
        for(std::array<int, 4> const& row: m_field){
            for(int const col: row){
                if(set.count(col) != 0){
                    return false;
                }
                else{
                    set.insert(col);
                }
            }
        }
        if(set.count(m_empty) != 1 || find_empty_position() != m_empty_position){
            return false;
        }
        return true;
    }

};

Matrix const SOLVED_MATRIX = Matrix();

bool is_solved(Matrix const& field){
    return field == SOLVED_MATRIX;
}


class ThreadPool{
    static inline std::vector<std::thread> m_threads;                       //Place for the threads
    static inline int m_counter = 0;                                        //Counts how many threads there are, also used to assign ids
    static inline std::mutex m_lock{};                                      //For m_result access
    static inline bool m_running = true;                                    //If the threads should continue searching for solution, also an indicator for if a solution has been found
    static inline bool m_close_all_threads_registered = false;              //If the program gets ^C, makes sure ThreadPool::close_all_threads get's called exactly once
    static inline std::string m_result;                                     //Result
    static inline unsigned long long m_for_analysis[MAX_THREADS] = {0};     //For analysis if new threads are actually useful

    int m_id;
    std::thread m_thread;
public:
    inline ThreadPool(){
        m_id = m_counter;
        ++m_counter;
        if(!m_close_all_threads_registered){
            std::atexit(&close_all_threads);
            m_close_all_threads_registered = true;
        }
    }

    void start(Matrix field){
        m_threads.emplace_back(std::thread(&ThreadPool::solve_matrix, this, field));

    }

    void solve_matrix(Matrix field){
        std::random_device rd;
        std::mt19937 gen(rd());
        std::uniform_int_distribution<int> random_int(0, 3);
        std::string result;

        int random;

        while(m_running){
            if(is_solved(field)){
                std::lock_guard<std::mutex> guard(m_lock);
                m_running = false;
                m_result = result;
            }
            else{
                ++m_for_analysis[m_id];
                //creates a random move, starts over if the move is impossible
                start:
                random = random_int(gen);
                switch(random){
                    case 0: 
                        if(field.get_empty_position().second == 0){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::UP);
                            result += "U";
                        }
                        break;
                    case 1:
                        if(field.get_empty_position().first == 3){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::RIGHT);
                            result += "R";
                        }
                        break;
                    case 2:
                        if(field.get_empty_position().second == 3){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::DOWN);
                            result += "D";
                        }
                        break;
                    case 3:
                        if(field.get_empty_position().first == 0){
                            goto start;
                        }
                        else{
                            field.move(DIRECTIONS::LEFT);
                            result += "L";
                        }
                        break;
                    default:
                        (void)0;
                }
            }
        }
    }

    static void close_all_threads(){
        std::lock_guard<std::mutex> guard(m_lock);
        m_running = false;
        for(std::thread& thread: m_threads){
            thread.join();
        }
        m_threads.clear();
    }

    static std::string get_result(){
        return m_result;
    }

    static bool is_running(){
        return m_running;
    }

    static int get_counter(){
        return m_counter;
    }

    static unsigned long long* get_analysis(){
        return m_for_analysis;
    }

    static std::mutex& get_lock(){
        return m_lock;
    }
};


std::string solve(std::array<std::array<int, 4>, 4> input){
    Matrix field(input);
    ThreadPool first_thread;
    first_thread.start(field);
    #ifdef WITH_THREADS
    bool limit_reached = false;

    unsigned long long analysis_array1[MAX_THREADS] = {0};
    unsigned long long analysis_array2[MAX_THREADS] = {0};
    while(ThreadPool::is_running() && ThreadPool::get_counter() < MAX_THREADS && !limit_reached){
        std::this_thread::sleep_for(10ms);
        unsigned long long* temp = ThreadPool::get_analysis();
        for(int i = 0; i < MAX_THREADS; ++i){
            analysis_array1[i] = temp[i];
        }
        unsigned long long sum1;
        unsigned long long sum2;
        for(int i = 0; i < MAX_THREADS; ++i){
            sum1 += analysis_array1[i];
            sum2 += analysis_array2[i];
        }
        long double ratio = static_cast<long double>(sum2)/sum1;
        if(ratio > RATIO_THRESHOLD){
            limit_reached = true;
            break;
        }
        for(int i = 0; i < MAX_THREADS; ++i){
            analysis_array2[i] = analysis_array1[i];
        }
        ThreadPool thread = ThreadPool();
        thread.start(field);
    }
    std::cout << "STOPPED CREATING MORE THREADS OR SOLUTION FOUND; TOTAL THREADS (with main): " << ThreadPool::get_counter()+1 << '\n';
    #endif
    while(ThreadPool::is_running()){}
    ThreadPool::close_all_threads();
    return ThreadPool::get_result();
}