I have to solve a problem. I have a set of data of the following structure, and have to create an array of all bags containing a shiny gold bag (including bags that contain bags containing the shiny gold bag)
I have implemented something like the following, that works for the above dataset but not for the larger one(almost 600 lines). My question is: -why the code is working for that small data set but not for the larger one -I know that mine is not the most elegant way to solve it, so is that any technique to solve it more efficiently?
this is my code
const input = `light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.`
.split("\n")
.map((row) => Array(row))
.map((row) => row[0].replace("contain", ",").split(","));
function checkColors(arr, str) {
for (let i = 1; i < arr.length; i++) {
if (arr[i].includes(str)) return arr[0];
}
}
let colors = input
.map((entry) => checkColors(entry, "shiny gold"))
.filter((entry) => entry != undefined)
.map((entry) => entry.replace("bags", "").trim());
let colorsMain = colors;
let tempCol = [];
do {
for (let j = 0; j < colors.length; j++) {
tempCol = input.map((entry) => checkColors(entry, colors[j]));
}
tempCol = tempCol
.filter((entry) => entry != undefined)
.map((entry) => entry.replace("bags", "").trim());
colorsMain = colorsMain.concat(tempCol);
colors = tempCol;
console.log(colorsMain);
} while (tempCol.length > 0);
console.log(colorsMain.length);You could build an object with all relations and then collect the wanted values.
const
addToSet = (s, v) => (relations[v] || []).reduce(addToSet, s.add(v)),
data = `light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.`,
relations = data
.split(/[\r\n]+/)
.reduce((r, s) => {
const
[value, key] = s.split(' bags contain '),
keys = key === 'no other bags.'
? []
: key
.split(/[,.]\s*/)
.filter(Boolean)
.map(s => s.match(/\d+\s(.*)\sbag/)[1]);
keys.forEach(k => (r[k] ??= []).push(value));
return r;
}, {}),
result = [...relations['shiny gold'].reduce(addToSet, new Set)];
console.log(result);
console.log(relations);.as-console-wrapper { max-height: 100% !important; top: 0; }How about this one?
const input = `light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.`
function buildColorDict(input) {
const colorDict = {}
input.split("\n").map((line) => {
return line.match(/([a-zA-Z]+\s+[a-zA-Z]+)+(?=\s+bags?)/g)
}).forEach((arr) => {
arr.slice(1).forEach((color) => {
colorDict[color] ? colorDict[color].push(arr[0]) : colorDict[color] = [arr[0]]
})
})
return colorDict
}
function lookUp(colorDict, color) {
const _lookUp = (_color) => {
if (colorDict[_color]) {
return colorDict[_color].concat(colorDict[_color].map((_color1)=> _lookUp(_color1)).flat())
} else {
return []
}
}
return new Set(_lookUp(color))
}
const colorDict = buildColorDict(input)
const result = lookUp(colorDict, "shiny gold")
console.log(Array.from(result))Basically, extract color from the input using regex, and build a reverse look up dictionary. Given a color, let's say shiny gold. It looks up which bag contains it, and using the colors found to look up which bags contain the found colored bags in a recursive way.