21

Re: Порівняння матриць

Мій розв'язок на Rust:

use itertools::Itertools;

fn default_form(matrix: &[i16; 4]) -> (i16, i16, i16, i16) {
    [0,1,3,2,0,1,3]
            .windows(4)
            .map(|r|r.iter()
                     .map(|&i|matrix[i])
                     .collect_tuple()
                     .unwrap()
            )
            .min()
            .unwrap()
}

fn count_different_matrices(matrices: &[[i16; 4]]) -> usize {
    matrices.iter()
            .map(default_form)
            .unique()
            .count()
}

Загалом десь схоже, але я використовую тьюпл з 4 i16, і замість 4 перевірок по геш-таблиці спершу знаходжу мінімальну з чотирьох комбінацій, а потім заношу тільки її. Ну агресивно використовую стандартні/напівстандартні функції на кшталт .unique() (там унутрі нєонка геш-таблиця)

Подякували: leofun01, lucas-kane2

22

Re: Порівняння матриць

Чим я керувався .. чи то мені чого було ..

Чистий C++, навіть читабельний, O(n)
#include <array>
#include <unordered_set>
#include <vector>

using vec_t = std::vector<std::array<int, 4>>;
int count_different_matrices(vec_t const &matrices) {
    std::unordered_set<int> s;
    for(auto a : matrices)
        #define A (a = { a[1], a[3], a[0], a[2] }) \
            [0] | a[1] << 8 | a[2] << 16 | a[3] << 24
        s.insert(std::min({ A, A, A, A }));
        #undef A
    return s.size();
}
Подякували: lucas-kane1

23

Re: Порівняння матриць

Наступна ідея: якщо числа там лише від 1 до 9, то нам не треба unordered_set. Навіть з найпростішою геш-функцією (по типу збираємо всі числа в одне 4-значне) там вийде 10000 можливих варіантів, це vector<bool> на трохи більш ніж кілобайт.

Подякували: leofun011

24 Востаннє редагувалося steamwater (31.08.2024 23:15:22)

Re: Порівняння матриць

Отакий ровнокодище вийшов)

#include <iostream>
#include <vector>
#include <array>
#include <utility>
#include<algorithm>

using val_t=char;
using super_vec=std::vector< std::pair<val_t*, std::array<val_t,4>>>;
using super_it=super_vec::iterator;
using super_pair=std::pair<val_t*, std::array<val_t,4>>;

super_vec
make_chains(val_t *arr, size_t N)
{
    super_vec vec;
    int size = N/4;
    val_t *p=arr;

    for(int i=0; i<size; ++i)
    {
        std::array<val_t,4> v;
        val_t *pp=p;

        for(int j=0; j<4; ++j)
        {
            v[j]=(*p);
            ++p;
        }

        std::sort(v.begin(), v.end());
        vec.push_back( {pp, v} );
    }
    return vec;
}

void my_summ_sort(super_it left, super_it right)
{
    std::sort(left, right,

        [](const super_pair &a, const super_pair &b)
              {
                return a.second < b.second;
              }
              );
}

val_t* max4(val_t *begin, int size=4)
{
    auto end=begin+size;
    auto pmax=begin;
    val_t max_val=*begin;
    ++begin;
    for( ;begin!=end; ++begin )
    {
       if(*begin>max_val)
        {
            max_val=*begin;
            pmax=begin;
        }

    }
    return pmax;
}

bool rotor_equal(val_t *begin1, val_t *begin2,  int size=4)
{
    auto max1=max4(begin1, size);
    auto max2=max4(begin2, size);
    auto last_ind=size-1;

    for(int i=0; i<size; ++i)
    {
        if( *max1 != *max2 ) return false;
        max1 = max1-begin1 == last_ind? begin1: ++max1 ;
        max2 = max2-begin2 == last_ind? begin2: ++max2 ;
    }

    return true;
}

int main()
{
    val_t set_of_matrixes[]={
         2,3,4,5//
        ,3,4,5,2//
        ,1,2,3,4///
        ,1,2,4,5
        ,2,3,5,4
        ,2,3,4,1///
        ,3,4,5,1
        ,2,3,4,1///
        };

        const int sz=sizeof(set_of_matrixes)/sizeof(val_t);

    auto chains=make_chains(set_of_matrixes, sz);

    my_summ_sort(chains.begin(), chains.end());

    //chains of equal value set:
    using has_twin = int;
    std::vector<std::vector<std::pair<val_t*, has_twin>>> eqv_set_chains;
    super_it sup_it=chains.begin();
    super_it sup_it_end=chains.end();
    for ( ; sup_it!=sup_it_end; )
    {
        auto upb_it = std::upper_bound(sup_it, sup_it_end, *sup_it,
              [](const super_pair &a, const super_pair &b)
              {
                return a.second < b.second;
              }
              );
              std::vector<std::pair<val_t*, has_twin>> eqv_range;
              for( ; sup_it!=upb_it; ++sup_it)
              {
                 eqv_range.push_back({sup_it->first,-1});
              }
              eqv_set_chains.push_back(eqv_range);
    }

    int twin_count(0);

    for(auto & v:eqv_set_chains)
    {
        auto it_end=v.end();

            for(auto iter=v.begin(); iter!=it_end; ++iter)
            {
                bool once_for_leader=true;
                for(auto it=iter; it!=it_end; ++it)
                {
                    if(it==iter || it->second!=-1)continue;
                    auto twin_bool=rotor_equal(iter->first, it->first);
                    if(twin_bool)
                    {
                       auto index_leader=iter-v.begin();
                       iter->second=index_leader;
                       it->second=index_leader;
                       ++twin_count;
                       if(once_for_leader)
                       {
                           ++twin_count;
                           once_for_leader=false;
                       }
                    }
                }
            }
    }
    std::cout<<"the number of twined matrixes is "<<(twin_count)<<'\n';

    std::cout<<"the number of different matrixes is "<<(sz/4-twin_count)<<'\n';
    //ще можна вивести вiдповiднi набори матриць, але в завдання воно не входить)
    return 0;
}
//наче працює, але не тестував. Можна, звiсно трохи оптiмiзувати. Не дивлячись на те, що стайл не спортивний, - є видiлення додаткової, пам'ятi, загальна швiдкiсть може бути не погана.

25

Re: Порівняння матриць

Розв'язок на C за O(n)

Мабуть, з іменами недопрацював, а з константами перестарався, але хай вже буде як є

#include <stddef.h>
#include <stdbool.h>
#include <limits.h>

#define MIN_VALUE 1
#define MAX_VALUE 9
const unsigned SIZE = 4;

static const unsigned order[] = {0,1,3,2,0,1,3};
#define VALUE_COUNT (MAX_VALUE-MIN_VALUE+1)
typedef unsigned BitTableValue;
const unsigned VALUE_SHIFT = 5; //log2(sizeof(BitTableValue)*CHAR_BIT)
const unsigned VALUE_MASK = (1<<VALUE_SHIFT)-1;

//ceil(VALUE_COUNT**SIZE/sizeof(TableValue))
#define TABLE_SIZE ((VALUE_COUNT*VALUE_COUNT*VALUE_COUNT*VALUE_COUNT+sizeof(BitTableValue)-1)/sizeof(BitTableValue))

unsigned hash(const short matrix[4])
{
    unsigned result = INT_MAX;
    
    for(const unsigned *rot_order = order, *end = order+4; rot_order<end; ++rot_order) {
        unsigned v = 0;
        for(unsigned i=0; i<SIZE; ++i) {
            v = v * 9 + (matrix[rot_order[i]] - 1);
        }
        if(result>v)
            result = v;
    }
    return result;
}


bool table_get(BitTableValue table[], unsigned index)
{
    return (table[index >> VALUE_SHIFT]>>(index&VALUE_MASK)) & 1;
}

void table_set(BitTableValue table[], unsigned index)
{
    table[index >> VALUE_SHIFT] |= (1<<(index&VALUE_MASK));
}

unsigned count_unique_matrices (size_t n, const short matrices[n][SIZE])
{
    BitTableValue table[TABLE_SIZE] = {};
    unsigned result = 0;
    for(size_t i=0; i<n; ++i) {
        unsigned h = hash(matrices[i]);
        if(!table_get(table, h)) {
            ++result;
            table_set(table, h);
        }
    }
    return result;
}
Подякували: steamwater, leofun012

26 Востаннє редагувалося steamwater (02.09.2024 20:16:08)

Re: Порівняння матриць

Так, koala, я зробив бiльше нiж вимагає задача. Але, якщо треба тiльки пiдрахувати кiлькiсть унiкальних матриць з урахуванням обертань, то можно отак, мабуть:

#include <iostream>
#include <unordered_set>
#include<algorithm>

using val_t=char;

int min_ind(val_t *begin, int size=4)
{
    int ind_min=0;
    val_t min_val=*begin;

    int i=1;
    for(  ;i<size; ++i )
    {
       if(begin[i]<min_val)
        {
            min_val=begin[i];
            ind_min=i;
        }
    }
    
    return ind_min;
}

int hash_4(val_t *begin)
{
    int rot_table[][4]={
       {0,1,2,3}
      ,{1,2,3,0}
      ,{2,3,0,1}
      ,{3,0,1,2}
    };

    int min_index=min_ind(begin);
    int(&row)[4]=rot_table[min_index];

    int hash_sum=0;

    for(int i=0; i<4; ++i)
    {
        hash_sum+=begin[row[i]]<<8*(3-i);
    }
    
    return hash_sum;
}

int main()
{
     val_t set_of_matrixes[][4]={
         {2,3,4,5}//
        ,{3,4,5,2}//
        ,{1,2,3,4}///
        ,{1,2,4,5}
        ,{2,3,5,4}
        ,{2,3,4,1}///
        ,{3,4,5,1}
        ,{2,3,4,1}///
        };

        int size=sizeof(set_of_matrixes)/sizeof(*set_of_matrixes);

        std::unordered_set<int> uset;

        for(int i=0; i<size; ++i) uset.insert(hash_4(set_of_matrixes[i]));

        std::cout<<(size-uset.size());

    return 0;
}

Складнiсть, теж не має перевищити 0(n).

27

Re: Порівняння матриць

steamwater, там є посилання на початку. Зайдіть і перевірте, ваш "розв'язок" не працює.

Подякували: leofun011

28

Re: Порівняння матриць

C, майже читабельний, O(n), коротка версія
#include <stddef.h>

#define A (a = (short[4]){ a[1], a[3], a[0], a[2] })
#define H(X) (X * 9 + A[0])
#define HASH (hash = H(H(H(a[0]))))
#define BIT(X) HASH & 0 | (bits[hash >> 5] X (1 << (hash & 0x1F)))
#define GET BIT(&)
#define SET BIT(|=)

unsigned count_unique_matrices(size_t n, short const matrices[n][4]) {
    unsigned count = 0, hash, bits[230] = { 0 };
    for(int i = 0; i < n; ++i) {
        short *a = matrices[i];
        if(GET == 0) SET, SET, SET, SET, ++count;
    }
    return count;
}
C, майже читабельний, O(n), розширена версія
#include <stddef.h>
#include <stdint.h>

#define SHIFT 5
#define MASK ~(-1 << SHIFT)
#define MIN 1
#define MAX 9
#define DIST (MAX - MIN + 1)
#define BITS_COUNT DIST * DIST * DIST * DIST
#define ARRAY_SIZE (BITS_COUNT >> SHIFT) + 24

#define A (a = (short[4]){ a[1], a[3], a[0], a[2] })
#define H(X) (X * 9 + A[0])
#define HASH (hash = H(H(H(a[0]))))
#define BIT(X) HASH & 0 | (bits[hash >> SHIFT] X (1 << (hash & MASK)))
#define GET BIT(&)
#define SET BIT(|=)

unsigned count_unique_matrices(size_t n, short const matrices[n][4]) {
    unsigned count = 0, hash;
    uint32_t bits[ARRAY_SIZE] = { 0 };
    for(int16_t i = 0; i < n; ++i) {
        short *a = matrices[i];
        if(GET == 0) SET, SET, SET, SET, ++count;
    }
    return count;
}

Надихався дописом koala.

29 Востаннє редагувалося steamwater (05.09.2024 18:17:32)

Re: Порівняння матриць

Так. Iсторiя з поворотом матриць виявилась не такою очевидною. Тодi може отак:

Прихований текст
#include <iostream>
#include <unordered_map>
#include<algorithm>

using val_t=char;
int min_ind(val_t *begin, int size=4)
{
    int ind_min=0;
    val_t min_val=*begin;

    int i=1;
    for(  ;i<size; ++i )
    {
       if(begin[i]<min_val)
        {
            min_val=begin[i];
            ind_min=i;
        }
    }

    return ind_min;
}

unsigned hash_4(val_t *begin)
{
    constexpr int rot_table[][4]={
       {0,1,3,2}
      ,{1,3,2,0}
      ,{2,0,1,3}
      ,{3,2,0,1}
    };

    int min_index=min_ind(begin);
    const int(&row)[4]=rot_table[min_index];

    int hash_sum=0;
    int cnt(0);

    for(int i=0; ;)
    {
        hash_sum+=begin[row[i]]<<8*(3-i);

        ++cnt;
        ++i;
        if(i==4)i=0;
        if(cnt==4)break;
    }

    return hash_sum;
}

int main()
{
     val_t set_of_matrixes[][4]={

          {1,2,4,3}
         ,{3,1,2,4}
         ,{4,3,1,2}
         ,{2,4,3,1}

         ,{1,2,3,4}

         ,{2,3,4,5}
         ,{3,4,5,2}

         ,{2,4,3,5}

        };

        int size=sizeof(set_of_matrixes)/sizeof(*set_of_matrixes);

        std::unordered_map<unsigned, unsigned> umap;


        for(int i=0; i<size; ++i){
             auto h= hash_4(set_of_matrixes[i]) ;
             umap[h]++;
        }

        int diff_conter=std::count_if(umap.begin(), umap.end(),
                                      [](const std::pair<unsigned, unsigned> &pr){return pr.second==1;} );
                                      std::cout<<"the different matrixes number is:"<<diff_conter<<'\n';

        return 0;
}

Доречi. Я вважаю умову завдання некоректною. Якщо вони вважають, що в наборi

// Same as the above example.
count_different_matrices([
                          [1, 2, 3, 4],
                          [3, 1, 4, 2],
                          [4, 3, 2, 1],
                          [2, 4, 1, 3]]);
                          
//should return '1'

присутня одна хоч матриця яка вiдрiзняється вiд iнших, то це не є коректно. У цьому наборi жодної такої немає.
The task of this kata is to count how many different matrices you have.
тобто:
Завдання цього ката полягає в тому, щоб порахувати, скільки у вас різних матриць.
А тут їх нема зовсiм. Усi однаковi. Тому я й не люблю математикiв, якiм байдуже на будь яку логiку.
Вони б мали скласти завдання якось так:
The task of this kata is to count how many different kinds of matrices you have.
тобто:
Завдання цього ката полягає в тому, щоб порахувати, скільки у вас матриць, що належать до різних ризновидiв, де рiзновидом вважається группа с чотирьох матриць кожна з которих є продуктом описаного обертання.
  У цьому випадку достатньо unordered_set для мого алгоритму:

std::unordered_set<unsigned> uset;

        for(int i=0; i<size; ++i){
             auto h= hash_4(set_of_matrixes[i]) ;
             uset.insert(h);
        }

        std::cout<<uset.size();