/*
  Copyright (c) 2021 Corinne Diakhoumpa et Erwan Iev-Le Tac

  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:

  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.

  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/

const fs = require("fs");
const assert = require('assert').strict;
const utils = require('./utils');

// This program draws the schema associated to "Tatami".

let primes  = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
               61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
               131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
               197, 199, 211, 223, 227, 229];

let primesOneModFour = primes.filter(p => p % 4 == 1);

// Return 0 ≤ x < p such that x^2 = -1 mod p
function evenSquareRootOfMinusOne(p) {
    assert.strictEqual(p % 4, 1);
    // By the First Supplement to Quadratic Reciprocity we can find x such that
    // x^2 = -1 mod p iff p = 1 mod 4. Such an x satisfies x^{-1} = -x mod p and
    // (-x)^2 = -1 mod p. Conversely, if y is another solution, then p divides
    // (xy)^2 - 1 = (xy + 1)(xy - 1) and so y = ±x^{-1} = ±x mod p.
    // So there are exactly two solutions in [0, p): x and p - x, only one of
    // them being even.
    for (let x = 0; x < p; x += 2) {
        if (x * x % p == p - 1)
            return x;
    }
}

function getParameters(p) {
    assert.strictEqual(p % 4, 1);
    // p = 1 mod 4 ; r even implies so r^2 + 1 = 1 mod 4
    // So n = pn = q^2 + 1 = 1 mod 4
    //
    // pn = q^2 + 1 ≤ (p - 1)^2 + 1 = p^2 + 2(1 - p) < p^2 so n < p
    //
    let r = evenSquareRootOfMinusOne(p);
    let n = (r * r + 1) / p;
    return [r, n];
}

primesOneModFour.forEach(p => {
    let [r, n] = getParameters(p);
    console.log(`p = ${p}, n = ${n}, r = ${r}, (1 + 4 * ${(p-1)/4}) * (1 + 4 * ${(n-1)/4}) = ${r}^2 + 1, r mod 4 = ${r % 4}`);
});

const size = 10;
const p = 61;
const n = getParameters(p)[1];

function Rectangle(x, y, Nx, Ny) {
    return `<rect x="${x * size + 1}" y="${y * size + 1}" width="${size * Nx - 2}" height="${size * Ny - 2}" fill="#cccccc"/>`;
}

const filename = "tatami.svg";
console.log(`Generate ${filename}...`)
let stream = fs.createWriteStream(filename);
stream.write(utils.svgProlog('viewBox="0 0 415 615" width="7cm" height="10.37349397590361cm"'));
stream.write(utils.svgHeaderWithCopyLeft("Tatami", `L'image montre un pavage d'un rectangle de taille ${p}×${n} par des rectangles de taille 2×1, à l'exception d'un carré de coté 1 dans un des coins. En comparant le pavage d'un rectangle taille (4×3+1)×(4×1+1) dans ce coin et du carré de coté 2×4 dans le coin opposé, on constate que 8²+1 = 13×5. De même, en comparant le pavage d'un rectangle taille (4×3+1)×(4×4+1) dans ce coin et du carré de coté 2×15 dans le coin opposé, on constate que 30²+1 = 17×53. Les dimensions précédentes sont écrites en notation japonaise positionnelle.`));

stream.write(`<g style="font-size: ${size * 2}px; font-family: 'EB Garamond', 'AR PL UMing CN';" transform="translate(2.5,2.5)">`);

for (let i = 0; i < (n - 1) / 4; i++) {
    stream.write(Rectangle(1 + 4 * i, 0, 2, 1));
    stream.write(Rectangle(1 + 4 * i + 2, 0, 2, 1));
}
for (let j = 0; j < (p - 1) / 4; j++) {
    stream.write(Rectangle(0, 1 + 4 * j, 1, 2));
    stream.write(Rectangle(0, 1 + 4 * j + 2, 1, 2));
}
for (let j = 0; j < (p - 1) / 4; j++) {
    for (let i = 0; i < (n - 1) / 4; i++) {
        for (let k = 0; k < 4; k++) {
            if ((i + j) % 2) {
                stream.write(Rectangle(1 + 4 * i, 1 + 4 * j + k, 2, 1));
                stream.write(Rectangle(1 + 4 * i + 2, 1 + 4 * j + k, 2, 1));
            } else {
                stream.write(Rectangle(1 + 4 * i + k, 1 + 4 * j, 1, 2));
                stream.write(Rectangle(1 + 4 * i + k, 1 + 4 * j + 2, 1, 2));
            }
        }

    }
}

function toJapaneseNumeral(n, vertical) {
    let number = n.toLocaleString("ja-JP-u-nu-hanidec");
    if (!vertical)
        return number;

    let verticalNumber = "";
    for (let i = 0; i < number.length; i++)
        verticalNumber += `<tspan x="0" y="${2 * size * i}">${number[i]}</tspan>`;
    return verticalNumber;
}

[13, 53].forEach(q => {
    let [r, m] = getParameters(q);
    let thickness = size / (q == 13 ? 2 : 4);
    stream.write(`<rect width="${m * size}" height="${q * size}" stroke-width="${thickness}" stroke="black" fill="none"/>`);

    stream.write(`<text x="${size}" y="${q * size + size * 2}">${toJapaneseNumeral(m)}</text>`)

    stream.write(`<g transform="translate(${(m + 1) * size}, ${size * 3})">`)
    stream.write(`<text>${toJapaneseNumeral(q, true)}</text>`)
    stream.write("</g>")

    stream.write(`<g transform="translate(${(n - r) * size}, ${(p - r) * size})">`);
    stream.write(`<rect stroke="black" width="${r * size}" height="${r * size}" stroke-width="${thickness}" fill="none"/>`);
    let square = `${toJapaneseNumeral(r)}`;
    stream.write(`<g transform="rotate(45)"><text x="${-size * (square.length + 2)}">${square}</text></g>`)
    stream.write("</g>")

    // If (2A)^2 + 1 = 229 (4B+1) and (2C)^2 + 1 = 229 (4D+1) then
    // (2A)^2 - (2B)^2 = 4(A - B)(A + B) = 0 mod 229
    // A = B or A = -B mod 229
    //
    // So (2n)^2 + 1 = 229 (4m+1) implies n = ±61 mod 229.
    // Then we can write n = ±61 + 229k and
    // 4*(±61 + 229k)^2 + 1 = 229 * (4 * (229k^2 ± 122k + 16) + 1)
    // so m = (229k^2 ± 122k + 16)
    //
    // Conversely, for any k we have
    // 4(±61 + 229k)^2 + 1 = 229 * (4 * (229k^2 ± 122k + 16) + 1)
    //
    // The only solutions for n < 229 are n = 61, m = 16 and n = 168, m = 123.
    // stream.write(`<g transform="translate(229, 229) rotate(-45)"><text>(2n)² + 1 = (4m+1)×229 ?</text></g>`)
});
stream.write("</g>");

stream.write("</svg>")
stream.end();
console.log("done")