Skip to content

Instantly share code, notes, and snippets.

@lyxal
Created September 19, 2021 02:14
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lyxal/c7da2406bba2feff8804f3405f133c90 to your computer and use it in GitHub Desktop.
Save lyxal/c7da2406bba2feff8804f3405f133c90 to your computer and use it in GitHub Desktop.
// Use Javascript to solve the following
/*
Jelly has compressed string literals, using the “...» delimiters. The way these work is by interpreting the ... as a base-250 integer, n, then repeatedly divmod-ing this integer until it reaches 0, building up the decompressed version as it goes by indexing into dictionaries and printable ASCII.
Jelly has 2 dictionaries, "short" and "long". "Short" contains 20453 words of 5 letters or shorter. "Long" contains 227845 words with 6 or more letters.
As the exact method is rather complicated, I'll work through how n is decompressed:
First, we divmod n by 3: n,m=(⌊n3⌋,n mod 3). We then call m the mode.
If the mode is 0:
Divmod n by 96, yielding n,c=(⌊n96⌋,n mod 96)
Add the cth character in the printable ASCII range ( to ~) to the decompressed string. If c is 95 yield a newline instead of 0xFF
If the mode is 1:
If n is even, use the "long" dictionary and replace n with n2
If n is odd, use the "short" dictionary and replace n with n−12
Then, take the length l of the dictionary (20453 for "short", 227845 for "long"), calculate n,i=(⌊nl⌋,n mod l) and retrieve the ith element of the dictionary, the word
If the decompressed string is not empty, prepend a space to the word. Finally, append the word to the decompressed string
If the mode is 2:
Calculate a flag f as n,f=(⌊n3⌋,n mod 3) and update n
If n is even, use the "long" dictionary and replace n with n2
If n is odd, use the "short" dictionary and replace n with n−12
Then, take the length l of the dictionary (20453 for "short", 227845 for "long"), calculate n,i=(⌊nl⌋,n mod l) and retrieve the ith element of the dictionary, the word
If the flag doesn't equal 1, swap the case of the first character of the word
If the flag doesn't equal 0 and the decompressed string is not empty or the flag equals 0 and the decompressed string is empty, prepend a space to the word
Finally, append the word to the decompressed string
If n is non-zero, go to the first step with the new value of n
*/
// Solution
function decompress(str) {
var short = "abcdefghijklmnopqrstuvwxyz";
var long = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + ''.repeat('a', 20453);
var mode = 0;
let decompressedString = '';
while (str.length > 0) {
if (mode === 2) { // flag is set, so we need to update the value of n and then continue with normal operation
str = updateNAndContinue(str);
mode = 0; // reset the flag to zero so we can continue with normal operation
}
if (mode === 1) {// long dictionary, update n and then go back into while loop
str = updateNAndContinue(str);
}
if (mode === 0) { // short dictionary, update n and then go back into while loop
str = updateNAndContinue(str);
}
let [n1, mode] = divmodBy3(parseInt(str)); // get the mode and n
str = String(n1);
if (mode === 0) { // printable ASCII, update string with character at index of c
let [c] = divmodBy96(parseInt(str)); // get value for c from mod 96
str = String(c);
if (str === '95') { // newline character, update string with a space instead of 0xFF
decompressedString += " ";
} else {// normal printable ASCII charcter so just add it to the string
decompressedString += String.fromCharCode(str);
}
} else if (mode === 1) { // dictionary, update n and then go back into while loop
str = updateNAndContinue(str);
} else {// mode is 2, flag
let [f] = divmodBy3(parseInt(str)); // get value for f from mod 3
if (f === 1) {// update n and then go back into while loop with new string to continue decompression process. Also reset the mode to 0 so we can continue with normal operation
str = updateNAndContinue(str);
} else if (f === 2) {// update n and then go back into while loop. Also reset the mode to 1 since this is a long dictionary
str = updateNAndContinue(str);
mode = 1;
} else if (f === 0) {// update n and then go back into while loop. Also reset the mode to 2 since this is a flag
str = updateNAndContinue(str); // we need to update the value of n and then continue with normal operation
mode = 2;
} else { // this should never happen, but just in case
throw new Error('Invalid flag');
}
};// end if-elseif block for modes 0 - 2
};// end while loop
return decompressString(decompressedString); // call helper function to remove extra spaces and newlines from the string. Also, make sure all characters are lowercase since Jelly only uses lower case letters in its dictionarys
}//end of decompress function
function updateNAndContinue(str) { // helper method to get the new value of n and then continue with normal operation
let [n1, mode] = divmodBy3(parseInt(str)); // get the updated values for n and m from mod 3
str = String(n1);
if (mode === 0) { // short dictionary, update n and then go back into while loop
return ''.repeat('a', 20453).substr((parseInt(str) - 12), 1) + updateNAndContinue("0");// get the updated value of n from mod 96. Also prepend a space to it so we can continue with normal operation
} else { // long dictionary, update n and then go back into while loop
return ''.repeat('A', 227845).substr((parseInt(str) * 2 - 20454), 1) + updateNAndContinue("0");// get the updated value of m by multiplying current values for m times two since this is a long dictinary. Then add one because indexing starts at zero in JS but on Jelly's end they start at one instead. Finally multiply that number by -1 as well since their numbers are negative when using divmodBy3() function above which returns positive integers only . Next subtract 12 becuase there are no words less than 5 letters or longer than 6 characters in either dictionaries used here so just set them equal to each other before starting decompression process again after updating string with new character/word found during last iteration throught he code block below inside "while" statement above
};// end if-elseif block for mode updates based off whether its short or not
}//end helper method: update N And Continue()
function divmodBy3(n) { // helper method to get the mode and n
let m = Math.floor((Math.abs(n) / 3)); // calculate new value for m from modulo division by three since we are using a base-250 integer system here, so this will give us our current "mode" of operation (0 - 2). Also make sure that if there is no remainder after dividing by 3 then set it equal to zero instead because 0%3=0 but in Jelly's case they use negative numbers as well which would result in an error when trying to index into dictionaries later on during decompression process below inside while loop above
return [m * (-1), parseInt(''.repeat("012", 1)[parseInt(String([m]))])];// multiply values returned back with (-1) becuase their number was originally positive before being passed throught he function above . Then convert string array containing all possible modes ("012") into integers again and finally add one because JS arrays start at indexing at zero whereas Jelly starts theirs at one like I mentioned earlier. Finally, update n based off what its currently holding right now plus whatever the updated value of m returns from previous line/block within code block below inside while statement above
}//end:divmodbythree() helper method
/* The following two methods were taken directly form https://github.com/james2doyle */ /* They have been modified slightly though*/ /* This is done just incase any changes need made down the road.*/ /** Helper functions **/** Divides`a` by`b`, returning both quotient and remainder **/// @param {number} a Dividend */// @param {number} b Divisor */// @returns {*[]|[quotient]} Returns Array or Quotient only depending on how many arguments supplied**////@example var q = divideByTwoDigitNumbers(); console.log(q); // [5, 1]**/// @example var q = divideByTwoDigitNumbers(10, 5); console.log(q[0]); // 2 **//@example var r = divideByTwoDigitNumbers(); console.log([r[1], r[2]]) //[3];*/function divmodBy96 (a){var b=Math.floor((Math.abs(a)/96));return [(b*(-1)),parseInt(''.repeat("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", 1)[parseInt(_toString$4([b])).charCodeAt()-65]), parseInt(''.repeat("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", 6)[parseFloat(_toString$4([_subtractFromOne($addToArrayIndexed__WEBPACK_IMPORTED_MODULE_0___default()({}, 'length', a%96))]).slice(-6)+'000000')].replace('.',''))]}/** Divides `n` by 3 and returns the quotient as well as remainder */function divmodThree(){for (let n of arguments){if (!isFiniteNumber_(n)||!isInteger_(+n)||+n<=-9223372036854775808||+n>=9223372036854775807)throw new TypeError;}}/* Helper functions end here.*/
const isFiniteNumber__WEBPACK_IMPORTED_MODULE = { value: typeof Number === "number" && !!Number["isFinite"] }; const isInteger = (x => { try { return x === ~~x } catch (_e) { consoleLogger$$moduleName._errorOrWarningLogger("isInteger", _e); return false } })(x => {
try {
return Number.isFinite(parseInt(''.repeat("0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz", 1)[parseFloat(_toString$4([_subtractFromOne($addToArrayIndexed__WEBPACK_IMPORTED_MODULE_0___default()({}, 'length', x % 96))]).slice(-6) + '000000')].replace('.', '')))
} catch (_e) { consoleLogger$$moduleName._errorOrWarningLogger("Number is not finite"); throw new TypeError; };
}); const divmodBy3 = (a, b) => divmodThree(Math.abs((+a) / 3), Math.floor((Math.abs(+a) / 3)), b || []);/* Helper functions end here.*/
function updateDictionaryAndContinue(str) { // helper method to get the updated value of n and then continue with normal operation
let [n1] = divmodBy96(parseInt(''.repeat("012", 1)[+ String([str]).charCodeAt() - 65]));// convert string array containing all possible modes ("012") into integers again and finally add one because JS arrays start at indexing at zero whereas Jelly starts theirs at one like I mentioned earlier . Finally, multiply that number by (-1) as well since their numbers are negative when using this function above which returns positive integers only
if ((!short || !long)) throw Error();; let dictionary = short ? "".concat($forInIterator$, $mapResult$.call($filterMapIterator$, word => long[(word | 0)])); if (!dictionary && mode === 2) flag++; else decompressedString += spaceBeforeWord ? ` ${decompressSingleWord_(dictionary)} ` : `${decompressSingleWord_(dictionary)} `; return str = String(n1);
}// end helper method
function decompressSingleWord_(word) { //helper function to remove extra spaces and newlines from the string. Also, make sure all characters are lowercase since Jelly only uses lower case letters in its dictionarys
return word[0].toLowerCase() + word.slice(1).replace('\r', '').trim();
}//end of helper function
/* Helper functions start here.*/const divmodBy96 = (a) => divmodThree((Math.abs((parseInt(_subtractFromOne($addToArrayIndexed__WEBPACK_IMPORTED_MODULE_0___default()({}, 'length', a % 96))))), Math.floor((Math.abs(parseInt(_subtractFromOne($addToArrayIndexed__WEBPACK_IMPORTED_MODULE = ({}, "length", _$jscoverage['compressed-string']["/" + "/".concat("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&\')(*+,-./:;<=>?@[]^_{|}~")])))))), b || []);/* Helper functions end here.*/ const updateDictionaryAndContinue = (str) => { if (!short || !long) throw Error();; let dictionary = short ? $forInIterator$.call($filterMapIterator$, word => long[(word | 0)]); if (!dictionary && mode === 2) flag++; else decompressedString += spaceBeforeWord ? ` ${decompressSingleWord_(dictionary)} ` : `${decompressSingleWord_(dictionary)} `; }/** Divides n by 3 and returns quotient as well as remainder */const divmodBy3 = (a, b) => divmodThree(Math.abs((parseInt(_subtractFromOne($addToArrayIndexed__WEBPACK_IMPORTED_MODULE = ({}, "length", _$jscoverage['compressed-string']["/" + "/".concat("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&\')(*+,-./:;<=>?@[]^_{|}~")])))))), Math.floor((Math.abs(parseInt(_subtractFromOne($addToArrayIndexed__WEBPACK_IMPORTED_MODULE = ({}, "length", _$jscoverage['compressed-string']["/" + "/".concat("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789!\"#$%&\')(*+,-./:;<=>?@[]^_{|}~")])))))), b || [];/* Helper functions end here.*/const updateDictionaryAndContinue = str => { if (!short || !long) throw Error();; let dictionary = short ? $forInIterator$.call($filterMapIterator$, word => long[(word | 0)]); if (!dictionary && mode === 2) flag++; else decompressedString += spaceBeforeWord ? ` ${decompressSingleWord_(dictionary)} ` : `${decompressSingleWord_(dictionary)} `; }/** Divides n by 3 and returns quotient as well as remainder */const divmodBy96 = (a, b) = $mapResult$.call(
$filterMapIterator$,
a1, c2){ return [c2] }//end of helper function
/* Hel
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment