summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--c++/.nix/derivation.nix (renamed from .nix/derivation.nix)8
-rw-r--r--c++/lights_out.cpp128
-rw-r--r--default.nix14
-rw-r--r--html/.nix/derivation.nix16
-rw-r--r--html/lights_out.html1
5 files changed, 133 insertions, 34 deletions
diff --git a/.nix/derivation.nix b/c++/.nix/derivation.nix
index c3f76a3..a47b023 100644
--- a/.nix/derivation.nix
+++ b/c++/.nix/derivation.nix
@@ -1,17 +1,19 @@
{ lib
, stdenv
+, pname
+, version
}:
stdenv.mkDerivation {
- pname = "kel_lights_out";
- version = "0.0.0";
+ inherit pname version;
src = ./..;
dontConfigure = true;
buildPhase = ''
HOME=$(pwd)
- emcc c++/lights_out.cpp \
+ EM_CACHE=$TMPDIR/emscripten_cache
+ emcc lights_out.cpp \
-s WASM=1 \
-s EXPORTED_FUNCTIONS='["_fake_main"]' \
-s EXPORTED_RUNTIME_METHODS='["ccall", "cwrap"]' \
diff --git a/c++/lights_out.cpp b/c++/lights_out.cpp
index a5a277c..a1052bb 100644
--- a/c++/lights_out.cpp
+++ b/c++/lights_out.cpp
@@ -12,6 +12,7 @@ using Mat = std::array<std::array<int8_t,MM*NN>,MM*NN>;
template<size_t MM, size_t NN>
using Vec = std::array<int8_t,MM*NN>;
+template<size_t MM, size_t NN>
struct point {
point():x{0},y{0}{}
point(size_t x_, size_t y_):x{x_},y{y_}{}
@@ -22,16 +23,16 @@ struct point {
point& ret = *this;
++y;
- if(y >= N){
+ if(y >= NN){
++x;
- y -= N;
+ y -= NN;
}
return *this;
}
size_t stride() const {
- return x + y*N;
+ return x + y*NN;
}
bool equal(const point& rhs) const {
@@ -39,10 +40,11 @@ struct point {
}
};
-void print_vec(const Vec& x){
- for(size_t j = 0; j < N; ++j){
- for(size_t i = 0; i < M; ++i){
- point ind{i,j};
+template<size_t MM, size_t NN>
+void print_vec(const Vec<MM,NN>& x){
+ for(size_t j = 0; j < NN; ++j){
+ for(size_t i = 0; i < MM; ++i){
+ point<MM,NN> ind{i,j};
std::cout<<x[ind.stride()]<<" ";
}
std::cout<<"\n";
@@ -50,16 +52,18 @@ void print_vec(const Vec& x){
std::cout<<std::endl;
}
-void print_perm(const std::array<size_t,MN>& x){
- for(size_t j = 0; j < MN; ++j){
+template<size_t MM, size_t NN>
+void print_perm(const std::array<size_t,MM*NN>& x){
+ for(size_t j = 0; j < MM*NN; ++j){
std::cout<<x[j]<<"\n";
}
std::cout<<std::endl;
}
-void print_mat(const Mat& x, const std::array<size_t,MN>& P){
- for(size_t j = 0; j < MN; ++j){
- for(size_t i = 0; i < MN; ++i){
+template<size_t MM, size_t NN>
+void print_mat(const Mat<MM,NN>& x, const std::array<size_t,MM*NN>& P){
+ for(size_t j = 0; j < MM*NN; ++j){
+ for(size_t i = 0; i < MM*NN; ++i){
std::cout<<x[P[j]][i]<<" ";
}
std::cout<<"\n";
@@ -67,11 +71,12 @@ void print_mat(const Mat& x, const std::array<size_t,MN>& P){
std::cout<<std::endl;
}
-bool lu_decompose_gf2(Mat& R, std::array<size_t,MN>& P){
- for(size_t i = 0; i < MN; ++i){
+template<size_t MM, size_t NN>
+bool lu_decompose_gf2(Mat<MM,NN>& R, std::array<size_t,MM*NN>& P){
+ for(size_t i = 0; i < MM*NN; ++i){
bool found_pivot = false;
size_t pivot_row = i;
- for(size_t k = i; k < MN && (not found_pivot); ++k){
+ for(size_t k = i; k < MM*NN && (not found_pivot); ++k){
if(R[P[k]][i]){
found_pivot = true;
pivot_row = k;
@@ -82,10 +87,10 @@ bool lu_decompose_gf2(Mat& R, std::array<size_t,MN>& P){
}else if ( i != pivot_row ){
std::swap(P[i],P[pivot_row]);
}
- for(size_t k = i+1u; k < MN; ++k){
+ for(size_t k = i+1u; k < MM*NN; ++k){
if(R[P[k]][i]){
- for(size_t j = i+1u; j < MN; ++j){
+ for(size_t j = i+1u; j < MM*NN; ++j){
R[P[k]][j] ^= (R[P[i]][j]);
}
}
@@ -96,17 +101,82 @@ bool lu_decompose_gf2(Mat& R, std::array<size_t,MN>& P){
}
template<uint64_t MM, uint64_t NN>
-int solve_lights_out(const std::array<MM*NN,int8_t>& b){
+int solve_lights_out(std::array<int8_t,MM*NN>& b_raw){
+ Mat<M,N> A;
+ constexpr size_t MN = M*N;
+
+ Vec<M,N> b{
+ 1,0,1,
+ 1,0,1,
+ 0,0,0
+ };
+ // Works best if we use odd N's
+ // even N might not be solvable in roughly half of the cases
+ // Init
+ std::cout<<"Init"<<std::endl;
+ for(point<M,N> i{}; i.x < M && i.y < N; i.inc()){
+ for(point<M,N> j{}; j.x < M && j.y < N; j.inc()){
+ if(
+ (i.equal(j)) ||
+ (i.x == j.x && (i.y+1) == j.y) ||
+ (i.x == j.x && (j.y+1) == i.y) ||
+ (i.y == j.y && (i.x+1) == j.x) ||
+ (i.y == j.y && (j.x+1) == i.x)
+ ){
+ A[i.stride()][j.stride()] = true;
+ }else{
+ A[i.stride()][j.stride()] = false;
+ }
+ // std::cout<<A[i.stride()][j.stride()]<<std::endl;
+ }
+ // Populate how you like it.
+ //b[i.stride()] = false;
+ }
+ std::array<size_t, MN> P_ident;
+ std::iota(P_ident.begin(),P_ident.end(),0);
+ print_mat<M,N>(A,P_ident);
+
+ std::array<size_t, MN> P;
+ std::iota(P.begin(),P.end(),0);
+ // Solve it :)
+ std::cout<<"Solve"<<std::endl;
+ if(!lu_decompose_gf2<M,N>(A,P)){
+ return -1;
+ }
+ std::array<size_t,MN> P_inv{};
+ for(size_t i = 0; i < MN; ++i){
+ P_inv[P[i]] = i;
+ }
+ Vec<M,N> y;
+ for(size_t i = 0; i < MN; ++i){
+ y[i] = b[P[i]];
+ for(size_t j = 0; j < i; ++j){
+ y[i] ^= A[P[i]][j] & y[j];
+ }
+ }
- return 0;
+ Vec<M,N> x;
+ for(size_t i = MN; i > 0; --i){
+ x[i-1] = y[i-1];
+ for(size_t j = i; j < MN; ++j){
+ x[i-1] ^= (A[P[i-1]][j] and x[j]);
+ }
+ }
+
+ return 0;
}
extern "C"{
+int solve_lights_out_3_x_3(std::array<int8_t, 3u*3u>& inp){
+ int rc = solve_lights_out<3u,3u>(inp);
+ return rc;
+}
int fake_main(){
Mat<M,N> A;
+ constexpr size_t MN = M*N;
Vec<M,N> b{
1,0,1,
@@ -118,8 +188,8 @@ int fake_main(){
// even N might not be solvable in roughly half of the cases
// Init
std::cout<<"Init"<<std::endl;
- for(point i{}; i.x < M && i.y < N; i.inc()){
- for(point j{}; j.x < M && j.y < N; j.inc()){
+ for(point<M,N> i{}; i.x < M && i.y < N; i.inc()){
+ for(point<M,N> j{}; j.x < M && j.y < N; j.inc()){
if(
(i.equal(j)) ||
(i.x == j.x && (i.y+1) == j.y) ||
@@ -138,13 +208,13 @@ int fake_main(){
}
std::array<size_t, MN> P_ident;
std::iota(P_ident.begin(),P_ident.end(),0);
- print_mat(A,P_ident);
+ print_mat<M,N>(A,P_ident);
std::array<size_t, MN> P;
std::iota(P.begin(),P.end(),0);
// Solve it :)
std::cout<<"Solve"<<std::endl;
- if(!lu_decompose_gf2(A,P)){
+ if(!lu_decompose_gf2<M,N>(A,P)){
return -1;
}
std::array<size_t,MN> P_inv{};
@@ -153,15 +223,15 @@ int fake_main(){
}
std::cout<<"LR"<<std::endl;
- print_mat(A,P);
+ print_mat<M,N>(A,P);
std::cout<<"P"<<std::endl;
- print_perm(P);
+ print_perm<M,N>(P);
std::cout<<"Lights-Off puzzle"<<std::endl;
- print_vec(b);
+ print_vec<M,N>(b);
- Vec y;
+ Vec<M,N> y;
for(size_t i = 0; i < MN; ++i){
y[i] = b[P[i]];
for(size_t j = 0; j < i; ++j){
@@ -169,7 +239,7 @@ int fake_main(){
}
}
- Vec x;
+ Vec<M,N> x;
for(size_t i = MN; i > 0; --i){
x[i-1] = y[i-1];
for(size_t j = i; j < MN; ++j){
@@ -178,7 +248,7 @@ int fake_main(){
}
std::cout<<"Solution"<<std::endl;
- print_vec(x);
+ print_vec<M,N>(x);
return 0;
}
diff --git a/default.nix b/default.nix
index c2bb53f..acf40f7 100644
--- a/default.nix
+++ b/default.nix
@@ -3,6 +3,16 @@
, ...
}:
-pkgs.callPackage .nix/derivation.nix {
- inherit stdenv;
+let
+ pname = "lights_out";
+ version = "0.0.0";
+in rec {
+ lights_out_wasm = pkgs.callPackage c++/.nix/derivation.nix {
+ inherit stdenv pname version;
+ };
+
+ html = pkgs.callPackage html/.nix/derivation.nix {
+ inherit lights_out_wasm pname version;
+ stdenv = pkgs.stdenvNoCC;
+ };
}
diff --git a/html/.nix/derivation.nix b/html/.nix/derivation.nix
new file mode 100644
index 0000000..607c595
--- /dev/null
+++ b/html/.nix/derivation.nix
@@ -0,0 +1,16 @@
+{ stdenv
+, lights_out_wasm
+, pname
+, version
+}:
+
+stdenv.mkDerivation {
+ inherit pname version;
+
+ src = ./..;
+
+ installPhase = ''
+ mkdir $out
+ touch $out/side
+ '';
+}
diff --git a/html/lights_out.html b/html/lights_out.html
new file mode 100644
index 0000000..8b13789
--- /dev/null
+++ b/html/lights_out.html
@@ -0,0 +1 @@
+