Developer @Observable
Public
Edited
Jan 29, 2023
charmsRando = d3
.csvParse(
`name,notchCost
Wayward Compass,2
Gathering Swarm,3
Stalwart Shell,4
Soul Catcher,4
Shaman Stone,1
Soul Eater,1
Dashmaster,3
Sprintmaster,1
Grubsong,2
Grubberfly's Elegy,4
Fragile Heart,3
Unbreakable Greed,3
Unbreakable Strength,1
Spell Twister,1
Steady Body,1
Heavy Blow,2
Quick Slash,3
Longnail,4
Mark of Pride,1
Fury of the Fallen,2
Thorns of Agony,6
Baldur Shell,5
Flukenest,6
Glowing Womb,4
Quick Focus,4
Deep Focus,2
Lifeblood Heart,1
Lifeblood Core,1
Joni's Blessing,0
Hiveblood,6
Spore Shroom,2
Sharp Shadow,3
Shape of Unn,3
Nailmaster's Glory,6
Weaver Song,2
Dream Wielder,1
Dreamshield,3
Grimmchild,3
`,
(d) => ({ ...d, notchCost: +d.notchCost })
)
.filter((d) => d.name.length > 0)
filteredCombos = {
yield notchCombos;
let combos = notchCombos
// only include combos that have "must have" charms
.filter((cs) =>
mustHaveCharms.every((must) => cs.charms.find((c) => c.name === must))
)
// only include combos that use only allowed charms
.filter((cs) => cs.charms.every((c) => availableCharms.includes(c.name)));
yield combos;
// remove combos that are a prefix of another combo
let trie = new Trie();
for (const combo of combos) {
trie.insert(combo.charms.map((c) => c.name));
}
combos = combos.filter((combo) => {
const trieEntry = trie.get(combo.charms.map((c) => c.name));
return Object.entries(trieEntry.children).length == 0;
});
yield combos;
// heavy lifting, remove all combos that are a subset of another
combos = combos.map((combo) => ({
...combo,
charmNames: new Set(combo.charms.map((c) => c.name))
}));
const notSubset = [];
for (let i = 0; i < combos.length; i++) {
let shouldKeep = true;
for (let j = 0; j < combos.length; j++) {
if (i === j) continue;
if (isSubset(combos[i].charmNames, combos[j].charmNames)) {
shouldKeep = false;
break;
}
}
if (shouldKeep) {
notSubset.push(combos[i]);
}
}
combos = notSubset;
yield combos;
const freeCharms = availableCharms.filter((c) => c.notchCost === 0);
combos = combos.map((combo) => ({
...combo,
charms: [...freeCharms, ...combo.charms]
}));
yield combos;
}
function isSubset(a, b) {
return Array.from(a).every((ax) => b.has(ax));
}
class Trie {
constructor() {
this.nodes = this._newNode();
}
_newNode() {
return { children: {} };
}
insert(keys) {
let cursor = this.nodes;
for (const key of keys) {
if (!Object.hasOwn(cursor.children, key)) {
cursor.children[key] = this._newNode();
}
cursor = cursor.children[key];
}
}
get(keys) {
let cursor = this.nodes;
for (const key of keys) {
if (!Object.hasOwn(cursor.children, key)) {
return undefined;
}
cursor = cursor.children[key];
}
return cursor;
}
}
notchCombos = {
let queue = Immutable.List();
queue = queue.push({ chosen: Immutable.List(), notchesUsed: 0, cursor: 0 });
let options = Immutable.List();
const charmsWithCost = charms.filter((c) => c.notchCost > 0);
while (queue.size > 0) {
const inProgress = queue.first();
queue = queue.shift();
const consideredCharm = charmsWithCost[inProgress.cursor];
if (consideredCharm) {
const nextChosen = inProgress.chosen.push(consideredCharm);
if (inProgress.notchesUsed + consideredCharm.notchCost <= maxNotches) {
options = options.push(nextChosen);
queue = queue.push({
chosen: nextChosen,
notchesUsed: inProgress.notchesUsed + consideredCharm.notchCost,
cursor: inProgress.cursor + 1
});
}
queue = queue.push({
chosen: inProgress.chosen,
notchesUsed: inProgress.notchesUsed,
cursor: inProgress.cursor + 1
});
}
}
return options.toJS().map((charms) => ({
charms,
totalNotchCost: charms.reduce((s, c) => s + c.notchCost, 0)
}));
}
charmsZip = FileAttachment("charms.zip").zip()
charmsZip.filenames.find((c) => c.includes("Eater"))
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
