La guida o il codice passo-passo che troverai in questo post è la soluzione più veloce e valida che abbiamo trovato a questa preoccupazione o dilemma.
Soluzione:
C++, Punteggio 23/1225/1327/1428/14 31/15
Finalmente un risultato con rapporto > 2:
rows=15,cols=31
1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1 0
1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1 1
1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0 1
1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1 0
1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1 1
0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1 1
0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1 1
1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0 0
0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0 0
0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1 0
1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0 1
0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0 0
0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1 0
1 0 0 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 1 1 1 0 1 0 1 1
Ho esplorato completamente da 1 a 14 righe. 15 richiederebbe troppo tempo per essere esplorato completamente. I risultati sono:
1/1 = 1
2/2 = 1
4/3 = 1.333
5/4 = 1.25
7/5 = 1.4
9/6 = 1.5
12/7 = 1.714
14/8 = 1.75
16/9 = 1.778
18/10 = 1.8
20/11 = 1.818
23/12 = 1.917
25/13 = 1.923
28/14 = 2
Il codice riportato di seguito è una versione precedente del programma. La versione più recente si trova su https://github.com/thospel/personal-propertyX.
/*
Compile using something like:
g++ -Wall -O3 -march=native -fstrict-aliasing -std=c++11 -g propertyX.cpp -lpthread -o propertyX
*/
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int ELEMENTS = 2;
using uint = unsigned int;
using Element = uint64_t;
using Column = array;
using Set = vector;
using Sum = uint8_t;
using Index = uint32_t;
using sec = chrono::seconds;
int const PERIOD = 5*60;
int const MAX_ROWS = 54;
int const COL_FACTOR = (MAX_ROWS+1) | 1; // 55
int const ROW_ZERO = COL_FACTOR/2; // 27
int const ROWS_PER_ELEMENT = CHAR_BIT * sizeof(Element) / log2(COL_FACTOR); //11
Element constexpr ELEMENT_FILL(Element v = ROW_ZERO, int n = ROWS_PER_ELEMENT) {
return n ? ELEMENT_FILL(v, n-1) * COL_FACTOR + v : 0;
}
Element constexpr POWN(Element v, int n) {
return n ? POWN(v, n-1)*v : 1;
}
Element const ELEMENT_TOP = POWN(COL_FACTOR, ROWS_PER_ELEMENT -1);
int const MAX_COLS = ROWS_PER_ELEMENT * ELEMENTS; // 22
atomic col_next;
atomic period;
chrono::steady_clock::time_point start;
mutex period_mutex;
uint ratio_row;
uint ratio_col;
mutex ratio_mutex;
auto const nr_threads = thread::hardware_concurrency();
// auto const nr_threads = 1;
struct State {
State(uint cols);
void process(Index i);
void extend(uint row);
void print(uint rows);
Index nr_columns() const { return static_cast(1) << cols_; }
Column last_;
Element top_;
int top_offset_;
uint ratio_row_ = 0;
uint ratio_col_ = 1;
uint cols_;
array side;
vector sets;
};
ostream& operator<<(ostream& os, Column const& column) {
for (int i=0; i(-1) - ELEMENT_FILL(1);
}
}
top_ = POWN(COL_FACTOR, (cols_-1) % ROWS_PER_ELEMENT);
top_offset_ = ELEMENTS - 1 - (cols_-1) / ROWS_PER_ELEMENT;
}
void State::print(uint rows) {
for (auto c=0U; c(side[cols_-c+r-1]) << " ";
}
cout << "n";
}
cout << "----------" << endl;
}
void check(uint cols, uint t) {
State state(cols);
Index nr_columns = state.nr_columns();
while (1) {
Index col = col_next++;
if (col >= nr_columns) break;
state.process(col);
auto now = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast(now-start).count();
if (elapsed >= period) {
lock_guard lock{period_mutex};
if (elapsed >= period) {
cout << "col=" << col << "/" << nr_columns << " (" << 100.*col/nr_columns << "% " << elapsed << " s)" << endl;
period = (elapsed/PERIOD+1)*PERIOD;
}
}
}
}
void State::process(Index col) {
last_.fill(0);
for (uint i=0; i> i & 1;
side[i] = bit;
Element carry = 0;
for (int j=0; j(side[cols_+row-1]) << "n";
if (row >= MAX_ROWS) throw(range_error("row out of range"));
// Execute subset sum. The new column is added to set {from} giving {to}
// {sum} is the other set.
auto const& set_from = sets[row];
auto const& set_sum = sets[row + 1];
auto & set_to = sets[row + 2];
if (set_to.size() == 0) {
auto size = 3 * set_from.size() - 2;
set_to.resize(size);
for (int j=0; j(-1) - ELEMENT_FILL(1);
}
// Merge sort {set_from - last_} , {set_from} and {set_from + last_}
auto ptr_sum = &set_sum[1][0];
auto ptr_low = &set_from[0][0];
auto ptr_middle = &set_from[0][0];
auto ptr_high = &set_from[0][0];
Column col_low, col_high;
for (int j=0; j ptr_middle[j]) goto MIDDLE;
}
// low == middle
// cout << "low == middlen";
return;
LOW:
// cout << "LOWn";
for (int j=0; j col_high[j]) goto HIGH0;
}
// low == high
// cout << "low == highn";
return;
MIDDLE:
// cout << "MIDDLEn";
for (int j=0; j col_high[j]) goto HIGH0;
}
// middle == high
// cout << "middle == highn";
return;
LOW0:
// cout << "LOW0n";
for (int j=0; j ptr_sum[j]) {
ptr_sum += ELEMENTS;
goto SUM;
}
if (ptr_to[j] < ptr_sum[j]) goto DONE;
}
// sum == to
for (int j=-ELEMENTS; j<0; ++j)
if (ptr_to[j] != ELEMENT_FILL()) {
// sum == to and to != 0
// cout << "sum == ton";
// cout << set_sum[(ptr_sum - &set_sum[0][0])/ELEMENTS-1] << "n";
return;
}
DONE:;
}
// cout << "Ween";
auto row1 = row+1;
if (0)
for (uint i=0; i ratio_row_ * cols_) {
ratio_row_ = row1;
ratio_col_ = cols_;
lock_guard lock{ratio_mutex};
if (ratio_row_ * ratio_col > ratio_row * ratio_col_) {
auto now = chrono::steady_clock::now();
auto elapsed = chrono::duration_cast(now-start).count();
cout << "cols=" << cols_ << ",rows=" << row1 << " (" << elapsed << " s)n";
print(row1);
ratio_row = ratio_row_;
ratio_col = ratio_col_;
}
}
auto last = last_;
Element carry = 0;
for (int j=0; j 1) {
min_col = atoi(argv[1]);
if (min_col < 2)
throw(range_error("Column must be >= 2"));
if (min_col > MAX_COLS)
throw(range_error("Column must be <= " + to_string(MAX_COLS)));
}
if (argc > 2) {
max_col = atoi(argv[2]);
if (max_col < min_col)
throw(range_error("Column must be >= " + to_string(min_col)));
if (max_col > MAX_COLS)
throw(range_error("Column must be <= " + to_string(MAX_COLS)));
}
for (int cols = min_col; cols <= max_col; ++cols) {
cout << "Trying " << cols << " columns" << endl;
ratio_row = 0;
ratio_col = 1;
col_next = 0;
period = PERIOD;
start = chrono::steady_clock::now();
vector threads;
for (auto t = 1U; t < nr_threads; t++)
threads.emplace_back(check, cols, t);
check(cols, 0);
for (auto& thread: threads)
thread.join();
}
}
int main(int argc, char** argv) {
try {
my_main(argc, argv);
} catch(exception& e) {
cerr << "Error: " << e.what() << endl;
exit(EXIT_FAILURE);
}
exit(EXIT_SUCCESS);
}
Haskell 14/8 = 1,75
1 1 0 0 0 1 0 1 1 0 1 1 0 0
1 1 1 0 0 0 1 0 1 1 0 1 1 0
0 1 1 1 0 0 0 1 0 1 1 0 1 1
1 0 1 1 1 0 0 0 1 0 1 1 0 1
0 1 0 1 1 1 0 0 0 1 0 1 1 0
0 0 1 0 1 1 1 0 0 0 1 0 1 1
0 0 0 1 0 1 1 1 0 0 0 1 0 1
0 0 0 0 1 0 1 1 1 0 0 0 1 0
Precedentemente 9/6 = 1,5
1 0 1 0 1 1 0 0 1
1 1 0 1 0 1 1 0 0
1 1 1 0 1 0 1 1 0
1 1 1 1 0 1 0 1 1
1 1 1 1 1 0 1 0 1
1 1 1 1 1 1 0 1 0
Ho scritto questo, poi ho guardato le risposte all'altra domanda ed ero... scoraggiato.
import Data.List
import Data.Hashable
import Control.Monad
import Control.Parallel.Strategies
import Control.Parallel
import qualified Data.HashSet as S
matrix§indices = [ matrix!!i | i<-indices ]
powerset :: [a] -> [[a]]
powerset = filterM (const [True, False])
hashNub :: (Hashable a, Eq a) => [a] -> [a]
hashNub l = go S.empty l
where
go _ [] = []
go s (x:xs) = if x `S.member` s
then go s xs
else x : go (S.insert x s) xs
getMatrix :: Int -> Int -> [Int] -> [[Int]]
getMatrix width height vector = [ vector § [x..x+width-1] | x<-[0..height-1] ]
hasDuplicate :: (Hashable a, Eq a) => [a] -> Bool
hasDuplicate m = go S.empty m
where
go _ [] = False
go s (x:xs) = if x `S.member` s
then True
else go (S.insert x s) xs
hasProperty :: [[Int]] -> Bool
hasProperty matrix =
let
base = replicate (length (matrix !! 0)) 0::[Int]
in
if elem base matrix then
False
else
if hasDuplicate matrix then
False
else
if hasDuplicate (map (foldl (zipWith (+)) base) (powerset matrix)) then
False
else
True
pmap = parMap rseq
matricesWithProperty :: Int -> Int -> [[[Int]]]
matricesWithProperty n m =
let
base = replicate n 0::[Int]
in
filter (hasProperty) $
map (getMatrix n m) $
sequence [ [0,1] | x<-[0..n+m-1] ]
firstMatrixWithProperty :: Int -> Int -> [[Int]]
firstMatrixWithProperty n m = head $ matricesWithProperty n m
main = mapM (putStrLn. show) $ map (firstMatrixWithProperty 8) [1..]
Ricorda che puoi dare visibilità a questa notizia se ti è stata di aiuto.