Solved Sudoku Compactor P81->p20

sudoku_p20.js

(()=>{
const p20 = (()=>{
const F=[1,1,2,6,24,120,720,5040,40320,362880];
const chrLUT = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_~', encNum = n=>chrLUT[n], decNum = c=>chrLUT.indexOf(c);
const sizeMap = [9,6,6,6,6,6,6,6,6,6,3,3,3], bitMap = [19,10,10,10,10,10,10,10,10,10,3,3,3], reBitMap = new RegExp(bitMap.map(n=>`(.{${n}})`).join(''));
const N9 = [...Array(9).keys()], boxLUT = N9.map(b=>N9.map(n=>(~~(b/3)*27+b*3%9)+~~(n/3)*9+n%3)), rowLUT = N9.map(r=>N9.map(c=>r*9+c)), colLUT = N9.map(c=>N9.map(r=>r*9+c));
const getLc = (perm,s=[...perm.keys()])=>perm.map((n,_,a,i=s.indexOf(n))=>(s.splice(i,1),i));
const fromLc = (code,s=[...code.keys()])=>code.map((i,_,a,e=s[i])=>(s.splice(i, 1),e));
const lcToInt = (lc,l=lc.length)=>lc.reduce((int,n,i)=>int+n*F[l-i-1],0);
const intToLc = (int,z=9)=>[...Array(z)].map((_,i,a,c=F[z-i-1],n=Math.floor(int/c))=>(int%=c,n));
const getP = (p,m)=>m.map(i=>p[i]), getB = (p,b)=>getP(p,boxLUT[b]), getR = (p,r)=>getP(p,rowLUT[r]), getC = (p,c)=>getP(p,colLUT[c]);
const deflate = (perm,def)=>perm.map(n=>def.reduce((o,d)=>o-(n>d?1:0),n));
const inflate = (perm,inf)=>perm.map(n=>inf.sort().reduce((o,i)=>o+(o>=i?1:0),n));
const solEnc = (puz,p=puz.split('').map(c=>c-1))=>[
		getB(p,0),
		...[0,1,2].map(i=>getR(p,i)).map(r=>deflate(r.slice(3,9),r.slice(0,3))),
		...[0,1,2,3,4,5].map(i=>getC(p,i)).map(r=>deflate(r.slice(3,9),r.slice(0,3))),
		...[3,4,5].map(i=>getR(p,i)).map(r=>deflate(r.slice(6,9),r.slice(0,6))),
	]
	.map(p=>lcToInt(getLc(p)))
	.map((n,i)=>n.toString(2).padStart(bitMap[i],'0')).join('').padEnd(120,'0')
	.match(/.{6}/g).map(b=>encNum(parseInt(b, 2))).join('');
const solDec = data => {
	let perms = data
		.split('').map(decNum).map(n=>n.toString(2).padStart(6,'0'))
		.join('').match(reBitMap).slice(1).map((b,i)=>fromLc(intToLc(parseInt(b,2),sizeMap[i])));
	let p = [...Array(81)].map(_=>0);
	boxLUT[0].forEach((i,n)=>p[i]=perms[0][n]);
	[0,1,2].forEach(r=>inflate(perms[r+1],getR(p,r).slice(0,3)).forEach((n,i)=>p[rowLUT[r][i+3]]=n));
	[0,1,2,3,4,5].forEach(c=>inflate(perms[c+4],getC(p,c).slice(0,3)).forEach((n,i)=>p[colLUT[c][i+3]]=n));
	[3,4,5].forEach(r=>inflate(perms[r+7],getR(p,r).slice(0,6)).forEach((n,i)=>p[rowLUT[r][i+6]]=n));
	N9.forEach(i=>p[[6,7,8].find(r=>getR(p,r).slice(0,6).indexOf(i)===-1)*9+[6,7,8].find(c=>getC(p,c).slice(0,6).indexOf(i)===-1)]=i);
	return p.map(n =>n+1).join('');
};
const puzEnc = p=>p.replace(/[^0]/g,1).padEnd(84,0).match(/.{6}/g).map(b=>encNum(parseInt(b,2))).join('');
const puzDec = d=>[...d].map(decNum).map(n=>n.toString(2).padStart(6,0)).join('').slice(0,81);
const enc = (s,p)=>solEnc(s)+puzEnc(p);
const dec = (d,s=solDec(d.slice(0,20)))=>[s,puzDec(d.slice(20,34)).split('').map((c,i)=>c^1?0:s[i]).join('')];
return {solEnc,solDec,puzEnc,puzDec,enc,dec};
})();

/*
Encoding order:
111|222|222
111|333|333
111|444|444
---+---+---
567|89a|bbb
567|89a|ccc
567|89a|ddd
---+---+---
567|89a|
567|89a|
567|89a|

In order above:
1. Calculate Lehmer Code for each set of sizes 1x9,9x6,3x3
2. Convert to integer and align to bit sizes 19,10,10,10,10,10,10,10,10,10,3,3,3
3. Join and pad to 120 bits
4. Split into groups of 6 and convert a "safe" character

Reverse to decode

Only "tricky" detail is converting a permutation of 9 elements to a subset of 6 or 3 (inflate/ deflate)
*/

const printP81 = p81 => p81.match(/.{9}/g).map((r,i)=>r.match(/.../g).join(' ')+(i==2||i==5?'\n':'')).join('\n');
const printP = p => printP81(p.map(n =>String(n+1)).join(''));
let p81 = '200000090000000080060053000030060008000070060070000020000000015800020000000001030';
let s81 = '281647593345219687967853142439162758152378469678495321726934815813526974594781236';
console.log('Solution:');
console.log(printP81(s81));
console.log('p20.solEnc:', p20.solEnc(s81));
console.log(printP81(p20.solDec(p20.solEnc(s81))));

console.log('Puzzle:');
console.log(printP81(p81));
console.log('p20.puzEnc:', p20.puzEnc(p81));
console.log(printP81(p20.puzDec(p20.puzEnc(p81)).split('').map((c,i)=>c^1?0:s81[i]).join('')));
console.log('s81:', s81);
console.log('p81:', p81);
console.log('p20.enc(s81,p81):', p20.enc(s81,p81));
console.log('p20.dec(p20.enc(s81,p81)):', ...p20.dec(p20.enc(s81,p81)));
})();

sudoku_p32_a.js

(()=>{
const
F=[1,1,2,6,24,120,720,5040,40320,362880],
N9 = [...Array(9).keys()],
m1=[9,6,6,6,6,6,6,6,6,6,3,3,3],
m2=m1.map(s=>BigInt(F[s])),
m3='0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_~',
m4 = [N9.map(b=>N9.map(n=>(~~(b/3)*27+b*3%9)+~~(n/3)*9+n%3)),N9.map(r=>N9.map(c=>r*9+c)),N9.map(c=>N9.map(r=>r*9+c))],
m5 = [[[0],0,0,0],[[0,1,2],1,3,1],[[0,1,2,3,4,5],2,3,4],[[3,4,5],1,6,7]],
encN=n=>m3[n],decN=c=>m3.indexOf(c),ce=(p,t,i)=>m4[t][i].map(i=>p[i]),
def = (perm,def)=>perm.map(n=>def.reduce((o,d)=>o-(n>d?1:0),n)), inf = (perm,inf)=>perm.map(n=>inf.sort().reduce((o,i)=>o+(o>=i?1:0),n)),
getLc = (p,i,a,s=[...p.keys()],l=s.length)=>p.map((n,_,a,i=s.indexOf(n))=>(s.splice(i,1),i)).reduce((r,n,i)=>r+n*F[l-i-1],0),
fromLc = (l,z=9,s=[...Array(z).keys()])=>[...s].map((_,i,a,c=F[z-i-1],n=Math.floor(l/c))=>(l%=c,n)).map((i,_,a,e=s[i])=>(s.splice(i, 1),e)),
smoo = (n,s)=>n.reduce((t,n,i)=>(t+BigInt(n))*BigInt(s[i+1]||1),BigInt(0)),
unsmoo = (n,s,l=s.length,r=[])=>{for(let i=l-1;i>=0;i--)r[i]=Number(n%s[i]),n/=s[i];return r;},
pack = (s81,p81) => {
let s=s81.split('').map(c=>c-1);
return (
smoo(m5.map(([n,t,z])=>n.map(i=>ce(s,t,i)).map(r=>def(r.slice(z,9),r.slice(0,z)))).flat().map(getLc),m2).toString(2)+
p81.replace(/[^0]/g,1)
).padEnd(192,0).match(/.{6}/g).map(b=>encN(parseInt(b,2))).join('');
},
unpack = code => {
let [_,decS,decP] = code.split('').map(c=>decN(c).toString(2).padStart(6,0)).join('').match(/(.{110})(.{81})/);
let perms = unsmoo(BigInt('0b'+decS),m2).map((n,i)=>fromLc(n,m1[i]));
let s = [...Array(81)].map(_=>0);
m5.map(([n,t,z,d])=>n.forEach(r=>inf(perms[r+d],ce(s,t,r).slice(0,z)).forEach((n,i)=>s[m4[t][r][i+z]]=n)));
N9.forEach(i=>s[[6,7,8].find(r=>ce(s,1,r).slice(0,6).indexOf(i)===-1)*9+[6,7,8].find(c=>ce(s,2,c).slice(0,6).indexOf(i)===-1)]=i);
let s81 = s.map(n =>n+1).join(''), p81 = decP.split('').map((c,i)=>c^1?0:s81[i]).join('');
return [s81,p81];
};

[
	['281647593345219687967853142439162758152378469678495321726934815813526974594781236',
	 '200000090000000080060053000030060008000070060070000020000000015800020000000001030'],
	['379281654164975283285643719937452168658317492412896375723568941546139827891724536',
	 '000001000064000280080003010907400000000010000000006305020500040046000820000700000'],
].forEach(([solIn,puzIn])=>{
	let packed = pack(solIn,puzIn);
	console.log('packed:', packed);
	let [solOut,puzOut] = unpack(pack(solIn,puzIn));
	console.log('  solIn: ', solIn);
	console.log('  solOut:', solOut);
	console.log('  solIn === solOut:', solIn === solOut);
	console.log('  puzIn: ', puzIn);
	console.log('  puzOut:', puzOut);
	console.log('  puzIn === puzOut:', puzIn === puzOut);
});

})();

sudoku_p32_humanable.js

(() => {
	// Helpers
		const factorial = n => (n <= 0) ? 1 : n * factorial(n - 1);
		const removeSymbs = (perm, symbs) => {
			// Reduce a permutation by a subset of its symbols
			return perm.map(n => symbs.reduce((o, d) => o - (n > d ? 1 : 0), n));
		};
		const insertSymbs = (perm, symbs) => {
			// Inject symbols into permutation at correct positions
			return perm.map(n => [...symbs].sort().reduce((o, i) => o + (o >= i ? 1 : 0), n));
		};
	// Lehmer Code
		const createLehmerCode = arr => {
			const lc = [], len = arr.length, symbs = [...arr.values()].sort();
			for(let i = 0; i < len; i++) {
				let idx = symbs.indexOf(arr[i]);
				lc.push(idx);
				symbs.splice(idx, 1);
			}
			let int = 0;
			for(let i = 0; i < len; i++) int += lc[i] * factorial(len - i - 1);
			return int;
		};
		const integerToLehmerCode = (int, permSize) => {
			if(permSize <= 1) return [0];
			let multiplier = factorial(permSize - 1);
			let digit = Math.floor(int / multiplier);
			return [digit].concat(integerToLehmerCode(int % multiplier, permSize - 1));
		};
		const parseLehmerCode = (int, size) => {
			let lc = integerToLehmerCode(int, size);
			const res = [], len = lc.length, symbs = [...lc.keys()];
			for(let i = 0; i < len; i++) {
				let idx = lc[i];
				res.push(symbs[idx]);
				symbs.splice(idx, 1);
			}
			return res;
		};
	// B64 encoding
		const Char64Map = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_~';
		const encodeChar64 = num => Char64Map[num], decodeChar64 = char => Char64Map.indexOf(char);
		const bitsToChar64 = bits => bits.match(/.{6}/g).map(bits => encodeChar64(parseInt(bits, 2))).join('');
		const char64ToBits = chars => [...chars].map(char => decodeChar64(char).toString(2).padStart(6, 0)).join('');
	// BigInt packing
		const joinBigInts = (bis, biScales) => bis.reduce((acc, cur, i)=>(acc + cur) * (biScales[i + 1] || 1n), 0n);
		const splitBigInt = (bi, biScales) => {
			let len = biScales.length, res = [];
			for(let i = len - 1; i >= 0; i--) {
				res[i] = Number(bi % biScales[i]);
				bi /= biScales[i];
			}
			return res;
		};
	// Sudoku packing details
		const N9 = [0, 1, 2, 3, 4, 5, 6, 7, 8];
		const Regions = {
			box: N9.map(b => N9.map(n => (Math.floor(b / 3) * 27 + b * 3 % 9) + Math.floor(n / 3) * 9 + n % 3)),
			row: N9.map(r => N9.map(c => r * 9 + c)),
			col: N9.map(c => N9.map(r => r * 9 + c))
		};
		const PackOrder = [
			{type: 'box', parts: [0], size: 9},
			{type: 'row', parts: [0, 1, 2], size: 6},
			{type: 'col', parts: [0, 1, 2, 3, 4, 5], size: 6},
			{type: 'row', parts: [3, 4, 5], size: 3}
		];
		const PackScales = PackOrder.flatMap(({type, parts, size}) => parts.map(i => BigInt(factorial(size))));
		const getReg = (sol, type, idx) => Regions[type][idx].map(i => sol[i]);
		const setReg = (sol, type, idx, vals) => Regions[type][idx].map((idx, i) => sol[idx] = vals[i]);
	// Packing Functions
		const fillBox9 = sol => {
			const rows = [6, 7, 8].map(r => getReg(sol, 'row', r).slice(0, 6)),
						cols = [6, 7, 8].map(c => getReg(sol, 'col', c).slice(0, 6));
			N9.map(i => [
				6 + rows.findIndex(r => r.indexOf(i) === -1),
				6 + cols.findIndex(c => c.indexOf(i) === -1),
				i
			])
			.forEach(([row, col, i]) => sol[row * 9 + col] = i);
		};
		const pack = (s81, p81) => {
			let vals = [...s81].map(n => n - 1);
			let codes = PackOrder.flatMap(({type, parts, size}) => parts
				.map(idx => getReg(vals, type, idx))
				.map(perm => removeSymbs(perm.slice(9 - size, 9), perm.slice(0, 9 - size)))
				.map(createLehmerCode)
				.map(BigInt)
			);
			let solBits = joinBigInts(codes, PackScales).toString(2);
			let puzBits = p81.replace(/[^0]/g, 1);
			let jointBits = (solBits + puzBits).padEnd(192,0);
			return bitsToChar64(jointBits);
		};
		const unpack = (packed) => {
			let jointBits = char64ToBits(packed),
					solBits = jointBits.slice(0, 110),
					puzBits = jointBits.slice(110, 191),
					sol = [],
					codes = splitBigInt(BigInt('0b' + solBits), PackScales);
			PackOrder.forEach(({type, parts, size}) => parts.forEach(idx => {
				let perm = parseLehmerCode(codes.shift(), size),
						symbs = getReg(sol, type, idx).slice(0, 9 - size);
				setReg(sol, type, idx, symbs.concat(insertSymbs(perm, symbs)));
			}));
			fillBox9(sol);
			let s81 = sol.map(n => n + 1).join(''),
					p81 = [...puzBits].map((b, i) => b === '0' ? b : s81[i]).join('');
			return {s81, p81};
		};
		
	let s81 = '379281654164975283285643719937452168658317492412896375723568941546139827891724536';
	let p81 = '000001000064000280080003010907400000000010000000006305020500040046000820000700000';
	console.log('s81:', s81);
	console.log('p81:', p81);
	let packed = pack(s81, p81);
	console.log('packed:', packed);
	let unpacked = unpack(packed);
	console.log('unpacked:', unpacked);
	console.log('unpacked.s81 === s81:', unpacked.s81 === s81);
	console.log('unpacked.p81 === p81:', unpacked.p81 === p81);
})();