Lawful Evil #1 – kwadraty magiczne

krzaq Leave a comment

Rozpoczynam nową serię: Lawful Evil. Jest to znana kategoria postaci z DnD, charakteryzująca się działaniem zgodnym z obowiązującym porządkiem, jednak zaprzeczającym jego duchowi.

W moim wykonaniu jest to wykonywanie zadań (domowych czy innych) zgodnie z literą zadania, ale w sposób taki, aby było jasne, że to parodia/żart. Zadania będą maksymalnie przekombinowane, mogą zawierać celowo rażące błędy i, w ramach możliwości, ich stopień skomplikowania uczyni je niemożliwymi do wytłumaczenia nauczycielowi/wykładowcy.

Program C++ .Kwadrat magiczny jest to macierz kwadratowa o wymiarach n x n
zawierająca liczby całkowite takie, że suma elementów wszystkich wierszy, kolumn i przekątnych diagonalnych jest równa.
Napisz program, który wczytuje rozmiar kwadratu a następnie wypełnia go wartościami liczbowymi w taki sposób, by tworzyły one kwadrat magiczny. Wydrukuj ten kwadrat.
Załóż, że wymiar macierzy nie przekracza 10

Uwaga!!! zadanie należy wykonać używając techniki obiektowej (Klasy).
Klasa musi zawierać co najmniej: – 4 właściwości, 4 konstruktory (zwykły domyślny, kopiujący, destruktor przeładowanie operatorów <<,>>,+,=.

Po upewnieniu się, że mogą być kwadraty o wyłącznie nieparzystej długości boku, wybrałem łatwo googlowalną metodę De la Loubère’a. Niestety nie mogłem korzystać z dobrodziejstw C++11 (na pytanie o C++14 nie dostałem odpowiedzi), chociaż to pozytywnie (czyli negatywnie) wpłynęło na złożoność rozwiązania, które zastosowałem.

Kwadraty tworzone są za pomocą powyższej metody w czasie kompilacji, za pomocą średnio poprawnego metaprogramowania w szablonach, C++03 style:

template<int Base, int Exp>
class Power{
public:
	static const int value = Power<Base,Exp-1>::value * Base;
};
 
template<int Base>
class Power<Base,0>{
public:
	static const int value = 1;
};
 
template<template <int,int,int> class Func, template<int> class ArgGetter, int Times>
class Apply{
public:
	template<typename T>
	static void exec(T& t){
		typedef ArgGetter<Times> Arg;
		Func<Arg::type::x, Arg::type::y, Arg::type::value>::exec(t);
		Apply<Func,ArgGetter,Times-1>::exec(t);
	}
	template<typename T>
	static void exec(T const& t){
		typedef ArgGetter<Times> Arg;
		Func<Arg::type::x, Arg::type::y, Arg::type::value>::exec(t);
		Apply<Func,ArgGetter,Times-1>::exec(t);
	}
	template<typename T, typename U>
	static void exec(T& t, U& u){
		typedef ArgGetter<Times> Arg;
		Func<Arg::type::x, Arg::type::y, Arg::type::value>::exec(t, u);
		Apply<Func,ArgGetter,Times-1>::exec(t, u);
	}
	template<typename T, typename U>
	static void exec(T const& t, U& u){
		typedef ArgGetter<Times> Arg;
		Func<Arg::type::x, Arg::type::y, Arg::type::value>::exec(t, u);
		Apply<Func,ArgGetter,Times-1>::exec(t, u);
	}
	template<typename T, typename U>
	static void exec(T& t, U const& u){
		typedef ArgGetter<Times> Arg;
		Func<Arg::type::x, Arg::type::y, Arg::type::value>::exec(t, u);
		Apply<Func,ArgGetter,Times-1>::exec(t, u);
	}
	template<typename T, typename U>
	static void exec(T const& t, U const& u){
		typedef ArgGetter<Times> Arg;
		Func<Arg::type::x, Arg::type::y, Arg::type::value>::exec(t, u);
		Apply<Func,ArgGetter,Times-1>::exec(t, u);
	}
};
 
template<template <int,int,int> class Func, template<int> class ArgGetter>
class Apply<Func,ArgGetter,0>{
public:
	template<typename T>
	static void exec(T&){}
	template<typename T>
	static void exec(T const&){}
	template<typename T, typename U>
	static void exec(T&, U&){}
	template<typename T, typename U>
	static void exec(T const&, U&){}
	template<typename T, typename U>
	static void exec(T&, U const&){}
	template<typename T, typename U>
	static void exec(T const&, U const&){}
};
 
template<template<int,int> class Iterator, int Size, int X, int Y, int N>
class IfCellTraversed{
public:
	typedef Iterator<Size,N> Current;
	static const bool value = (Current::x == X && Current::y == Y) || IfCellTraversed<Iterator,Size,X,Y,N-1>::value;
};
 
template<template<int,int> class Iterator, int Size, int X, int Y>
class IfCellTraversed<Iterator,Size,X,Y,0>{
public:
	typedef Iterator<Size,1> Current;
	static const bool value = (Current::x == X && Current::y == Y);
};
 
template<int Size, int N>
class MagicSquareIterator{
public:
	typedef MagicSquareIterator<Size,N-1> Prev;
	typedef IfCellTraversed< ::MagicSquareIterator,Size, (Prev::x+1)%Size, (Prev::y-1+Size)%Size, N-1> SkipTest;
	static const int x = SkipTest::value ? Prev::x : (Prev::x+1)%Size;
	static const int y = SkipTest::value ? (Prev::y + 1)%Size : (Prev::y-1+Size)%Size;
	static const int value = Prev::value + 1;
};
 
template<int Size>
class MagicSquareIterator<Size,1>{
public:
	static const int x = Size/2;
	static const int y = 0;
	static const int value = 1;
};
 
template<int Size>
class IteratorForSize{
public:
	template<int N>
	class Template{
	public:
		typedef MagicSquareIterator<Size,N> type;
	};
};
 
template<int X, int Y, int Value>
class FillSquare{
public:
	template<typename T>
	static void exec(T& t){
		t(X,Y) = Value;
	}
};
 
 
 
template<int N>
class Copy{
public:
	template<int X, int Y, int>
	class Regular{
	public:
		template<typename T, typename U>
		static void exec(T const& from, U& to){
			to(X,Y) = from(X,Y);
		}
	};
 
	template<int X, int Y, int>
	class FromRawToSquare{
	public:
		template<typename T, typename U>
		static void exec(T const& from, U& to){
			to(X,Y) = from[Y*N + X];
		}
	};
};
 
 
 
 
 
template<int X, int Y, int>
class AddValue{
public:
	template<typename T, typename U>
	static void exec(T& to, U const& what){
		to(X,Y) += what;
	}
};
 
template<int X, int Y, int>
class AddValueFrom{
public:
	template<typename T, typename U>
	static void exec(T& to, U const& what){
		to(X,Y) += what(X,Y);
	}
};
 
 
template<int N>
class MagicSquare;
 
template<int N>
istream& operator>> (istream& s, MagicSquare<N> & sq);
 
template<int N>
class MagicSquare{
 
public:
 
	template<template <int,int,int> class Func>
	class SquareApply{
	public:
		typedef Apply<Func, IteratorForSize<N>::template Template,Power<N,2>::value> type;
	};
 
	MagicSquare(){
		SquareApply<FillSquare>::type::exec(*this);
	}
 
	MagicSquare(MagicSquare const& o){
		SquareApply<Copy<N>::template Regular>::type::exec(o, *this);
	}
 
	MagicSquare(istream& s){
		s >> *this;
	}
 
	MagicSquare(int added){
		SquareApply<FillSquare>::type::exec(*this);
		SquareApply<AddValue>::type::exec(*this,added);
 
	}
 
	~MagicSquare(){}
 
	MagicSquare& operator=(MagicSquare const& o){
		SquareApply<Copy<N>::template Regular>::type::exec(o, *this);
	}
 
	MagicSquare operator+(MagicSquare const& o){
		MagicSquare sq;
		SquareApply<Copy<N>::template Regular>::type::exec(o, sq);
		SquareApply<AddValueFrom>::type::exec(sq, *this);
		return sq;
	}
 
	int operator()(int x, int y) const {
		return data[y][x];
	}
 
	int& operator()(int x, int y){
		return data[y][x];
	}
 
 
private:
	int data[N][N];
	int property1, property2, property3;
};
 
template<int N>
ostream& operator<< (ostream& o, MagicSquare<N> const& sq){
	o << "Magic Square " << N << "x" << N << ":" << endl;
	for(int y = 0; y < N; y++){
		for(int x = 0; x < N; x++){
			o << setw(4) << right << sq(x,y);
		}
		o << endl;
	}
	return o;
}
 
template<int N>
istream& operator>> (istream& s, MagicSquare<N> & sq){
	std::vector<int> values(Power<N,2>::value);
	for(int i = 0; i < Power<N,2>::value; i++){
		s >> values[i];
	}
 
	MagicSquare<N>::template SquareApply<Copy<N>::template FromRawToSquare>::type::exec(values, sq);
	return s;
}

Przy powyższym kodzie, poniższa funkcja main

int main()
{
	MagicSquare<5> sq;
 
	stringstream str("17 23 4 10 11 24 5 6 12 18 1 7 13 19 25 8 14 20 21 2 15 16 22 3 9");
 
	MagicSquare<5> sq2(str);
 
	DBG(sq);
	DBG(sq2);
	DBG(sq+sq2);
 
	MagicSquare<1> m1;
	MagicSquare<3> m3;
	MagicSquare<5> m5;
	MagicSquare<7> m7;
	MagicSquare<9> m9;
	MagicSquare<11> m11;
 
	DBG(m1);
	DBG(m3);
	DBG(m5);
	DBG(m7);
	DBG(m9);
	DBG(m11);
}

Daje następujące rezultaty: [link]

sq                                      Magic Square 5x5:
  17  24   1   8  15
  23   5   7  14  16
   4   6  13  20  22
  10  12  19  21   3
  11  18  25   2   9
 
sq2                                     Magic Square 5x5:
  17  23   4  10  11
  24   5   6  12  18
   1   7  13  19  25
   8  14  20  21   2
  15  16  22   3   9
 
sq+sq2                                  Magic Square 5x5:
  34  47   5  18  26
  47  10  13  26  34
   5  13  26  39  47
  18  26  39  42   5
  26  34  47   5  18
 
m1                                      Magic Square 1x1:
   1
 
m3                                      Magic Square 3x3:
   8   1   6
   3   5   7
   4   9   2
 
m5                                      Magic Square 5x5:
  17  24   1   8  15
  23   5   7  14  16
   4   6  13  20  22
  10  12  19  21   3
  11  18  25   2   9
 
m7                                      Magic Square 7x7:
  30  39  48   1  10  19  28
  38  47   7   9  18  27  29
  46   6   8  17  26  35  37
   5  14  16  25  34  36  45
  13  15  24  33  42  44   4
  21  23  32  41  43   3  12
  22  31  40  49   2  11  20
 
m9                                      Magic Square 9x9:
  47  58  69  80   1  12  23  34  45
  57  68  79   9  11  22  33  44  46
  67  78   8  10  21  32  43  54  56
  77   7  18  20  31  42  53  55  66
   6  17  19  30  41  52  63  65  76
  16  27  29  40  51  62  64  75   5
  26  28  39  50  61  72  74   4  15
  36  38  49  60  71  73   3  14  25
  37  48  59  70  81   2  13  24  35
 
m11                                     Magic Square 11x11:
  68  81  94 107 120   1  14  27  40  53  66
  80  93 106 119  11  13  26  39  52  65  67
  92 105 118  10  12  25  38  51  64  77  79
 104 117   9  22  24  37  50  63  76  78  91
 116   8  21  23  36  49  62  75  88  90 103
   7  20  33  35  48  61  74  87  89 102 115
  19  32  34  47  60  73  86  99 101 114   6
  31  44  46  59  72  85  98 100 113   5  18
  43  45  58  71  84  97 110 112   4  17  30
  55  57  70  83  96 109 111   3  16  29  42
  56  69  82  95 108 121   2  15  28  41  54

Jednocześnie można udowodnić, że wszystko wykonuje się podczas kompilacji (tutaj wersja zmodyfikowana z większą ilością constexpr i static_assert):

void sink(MagicSquare<3> const&);
 
int main()
{
	MagicSquare<3> sq;
  sink(sq);
 
}
main:
        sub     rsp, 56
        mov     DWORD PTR [rsp+28], 9
        mov     DWORD PTR [rsp], 8
        mov     DWORD PTR [rsp+20], 7
        mov     DWORD PTR [rsp+8], 6
        mov     DWORD PTR [rsp+16], 5
        mov     DWORD PTR [rsp+24], 4
        mov     DWORD PTR [rsp+12], 3
        mov     DWORD PTR [rsp+32], 2
        mov     DWORD PTR [rsp+4], 1
        mov     rdi, rsp
        call    sink(MagicSquare<3> const&)
        mov     eax, 0
        add     rsp, 56
        ret

To by było na tyle. Link do zadania jest tutaj, swego czasu opisałem też tę sytuację na wykopie.

Leave a Reply

Your email address will not be published.