From 5bb7a961480b15440f9d590214c799b19da9aaba Mon Sep 17 00:00:00 2001 From: "Claudius \"keldu\" Holeksa" Date: Sat, 20 Sep 2025 17:29:06 +0200 Subject: Reworking structure. Adding proper C exports. Fix needed emcc is annoying me with its caching. Tries to write into /nix/store locations, which is shouldn't do. Need the proper env variable to rewrite. Otherwise it'll be ignored. --- .nix/derivation.nix | 29 ----------- c++/.nix/derivation.nix | 31 ++++++++++++ c++/lights_out.cpp | 128 ++++++++++++++++++++++++++++++++++++----------- default.nix | 14 +++++- html/.nix/derivation.nix | 16 ++++++ html/lights_out.html | 1 + 6 files changed, 159 insertions(+), 60 deletions(-) delete mode 100644 .nix/derivation.nix create mode 100644 c++/.nix/derivation.nix create mode 100644 html/.nix/derivation.nix create mode 100644 html/lights_out.html diff --git a/.nix/derivation.nix b/.nix/derivation.nix deleted file mode 100644 index c3f76a3..0000000 --- a/.nix/derivation.nix +++ /dev/null @@ -1,29 +0,0 @@ -{ lib -, stdenv -}: - -stdenv.mkDerivation { - pname = "kel_lights_out"; - version = "0.0.0"; - - src = ./..; - - dontConfigure = true; - buildPhase = '' - HOME=$(pwd) - emcc c++/lights_out.cpp \ - -s WASM=1 \ - -s EXPORTED_FUNCTIONS='["_fake_main"]' \ - -s EXPORTED_RUNTIME_METHODS='["ccall", "cwrap"]' \ - -o lights_out.js - ''; - - # Silence the warnings for now - checkPhase = '' - ''; - - installPhase = '' - mkdir -p $out - cp lights_out.{wasm,js} $out/ - ''; -} diff --git a/c++/.nix/derivation.nix b/c++/.nix/derivation.nix new file mode 100644 index 0000000..a47b023 --- /dev/null +++ b/c++/.nix/derivation.nix @@ -0,0 +1,31 @@ +{ lib +, stdenv +, pname +, version +}: + +stdenv.mkDerivation { + inherit pname version; + + src = ./..; + + dontConfigure = true; + buildPhase = '' + HOME=$(pwd) + EM_CACHE=$TMPDIR/emscripten_cache + emcc lights_out.cpp \ + -s WASM=1 \ + -s EXPORTED_FUNCTIONS='["_fake_main"]' \ + -s EXPORTED_RUNTIME_METHODS='["ccall", "cwrap"]' \ + -o lights_out.js + ''; + + # Silence the warnings for now + checkPhase = '' + ''; + + installPhase = '' + mkdir -p $out + cp lights_out.{wasm,js} $out/ + ''; +} 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,MM*NN>; template using Vec = std::array; +template 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 +void print_vec(const Vec& x){ + for(size_t j = 0; j < NN; ++j){ + for(size_t i = 0; i < MM; ++i){ + point ind{i,j}; std::cout<& x){ - for(size_t j = 0; j < MN; ++j){ +template +void print_perm(const std::array& x){ + for(size_t j = 0; j < MM*NN; ++j){ std::cout<& P){ - for(size_t j = 0; j < MN; ++j){ - for(size_t i = 0; i < MN; ++i){ +template +void print_mat(const Mat& x, const std::array& P){ + for(size_t j = 0; j < MM*NN; ++j){ + for(size_t i = 0; i < MM*NN; ++i){ std::cout<& P){ std::cout<& P){ - for(size_t i = 0; i < MN; ++i){ +template +bool lu_decompose_gf2(Mat& R, std::array& 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& 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& P){ } template -int solve_lights_out(const std::array& b){ +int solve_lights_out(std::array& b_raw){ + Mat A; + constexpr size_t MN = M*N; + + Vec 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"< i{}; i.x < M && i.y < N; i.inc()){ + for(point 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< P_ident; + std::iota(P_ident.begin(),P_ident.end(),0); + print_mat(A,P_ident); + + std::array P; + std::iota(P.begin(),P.end(),0); + // Solve it :) + std::cout<<"Solve"<(A,P)){ + return -1; + } + std::array P_inv{}; + for(size_t i = 0; i < MN; ++i){ + P_inv[P[i]] = i; + } + Vec 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 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& inp){ + int rc = solve_lights_out<3u,3u>(inp); + return rc; +} int fake_main(){ Mat A; + constexpr size_t MN = M*N; Vec 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"< i{}; i.x < M && i.y < N; i.inc()){ + for(point 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 P_ident; std::iota(P_ident.begin(),P_ident.end(),0); - print_mat(A,P_ident); + print_mat(A,P_ident); std::array P; std::iota(P.begin(),P.end(),0); // Solve it :) std::cout<<"Solve"<(A,P)){ return -1; } std::array P_inv{}; @@ -153,15 +223,15 @@ int fake_main(){ } std::cout<<"LR"<(A,P); std::cout<<"P"<(P); std::cout<<"Lights-Off puzzle"<(b); - Vec y; + Vec 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 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"<(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 @@ + -- cgit v1.2.3