Skip to content

Instantly share code, notes, and snippets.

@lastrafda
Created February 28, 2021 17:27
Show Gist options
  • Save lastrafda/a50d248d49115be431dc545b00fd0c7a to your computer and use it in GitHub Desktop.
Save lastrafda/a50d248d49115be431dc545b00fd0c7a to your computer and use it in GitHub Desktop.
/**
Eloquent Javascript CH003
Consider this puzzle: by starting from the number 1 and repeatedly either
adding 5 or multiplying by 3, an infinite set of numbers can be produced.
How would you write a function that, given a number, tries to find
a sequence of such additions and multiplications that produces that number?
*/
function findSolution(target) {
function find(current, history) {
if (current == target) {
return history;
} else if (current > target) {
return null;
} else {
return find(current + 5, `(${history} + 5)`) ||
find(current * 3, `(${history} * 3)`);
}
}
return find(1, "1");
}
console.log(findSolution(24));
// → (((1 * 3) + 5) * 3)
// VISUAL
/**
find(1, "1")
find(6, "(1 + 5)")
find(11, "((1 + 5) + 5)")
find(16, "(((1 + 5) + 5) + 5)")
too big
find(33, "(((1 + 5) + 5) * 3)")
too big
find(18, "((1 + 5) * 3)")
too big
find(3, "(1 * 3)")
find(8, "((1 * 3) + 5)")
find(13, "(((1 * 3) + 5) + 5)")
found!
*/
@lastrafda
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment