recursively checking data containing other data in Javascript

user_17317011 0
Viewed 74

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);

recursion javascript
2 Answers

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; }

user_14476750

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.

user_36627480
Related