I was playing a game called Alchemy Merge, where you have to combine different elements to create a new one. It starts with 4 basic elements i.e., Air, Fire, Soil and Water and combining this we get new elements. Now, I have completed the game and simultaneously noted each entry as following
Air
Fire
Soil
Water
Heat = Air Fire
Plant = Soil Water
Tree = Plant Plant
Forest = Tree Tree
... and the list continues for roughly 400 elements. Now, I have two questions regarding this.
- What is the fastest algorithm to complete the game with minimum steps?
- What is the best approach to determine the depth of an element in minimum time? By the term "depth", I am referring to the number of combinations required to get the element...
depth(Water) = 0 #primary element
depth(Plant) = 1 #(soil water)
#calculation for depth is stopped as it reaches the primary elements
As @trincot points out, here are a few more examples to clarify the "depth"
Algae = Plant Water.
Now, to get Algae, we need 2 combinations,
1. Plant = Soil Water
2. Algae = Plant Water
So the depth(Algae) will be 2.
Taking another example, consider the following combinations...
Stone = Soil Soil
Sand = Stone Water
Glass = Sand Fire
Time = Glass Sand
Now, calculating depth(Time), but in reverse order...
1. Time = Sand Glass
2. = (Stone Water) Glass
3. = ((Soil Soil) Water) Glass
4. = ((Soil Soil) Water) (Sand Fire)
5. = ((Soil Soil) Water) ((Stone Water) Fire)
6. = ((Soil Soil) Water) (((Soil Soil) Water) Fire)
So, depth(Time) = 6
Thank you.
CodePudding user response：
This is a graph problem, more specifically the graph is a directed, acyclic graph (DAG), where each node is an element, and outgoing edges go to the element(s) that are needed to build that element. If the same element is needed multiple times, that just means there are two edges connecting the two nodes. The "initial" four elements are represented by leaf-nodes, as they don't have outgoing edges.
Once you have this DAG available in a practical data structure, the problem of creating a target element comes down to traversing the dependent nodes in bottom-up fashion.
The notion of "depth" you present is actually not the term that would be used in the graph problem. You want to actually count the number of edges in a traversal that can be executed from the target node to reach the leaves.
To implement an algorithm, first choose a graph data structure that is convenient to quickly find a node, so a hash table (hash map, dictionary) would be a good choice. For each entry you could then have an array of references to child nodes, that reference the components that are needed.
We can represent such a structure in JSON format:
{
"Air": [],
"Fire": [],
"Soil": [],
"Water": [],
"Heat": ["Air", "Fire"],
"Plant": ["Soil", "Water"],
"Tree": ["Plant", "Plant"],
"Forest": ["Tree", "Tree"],
"Algae": ["Plant", "Water"],
"Stone": ["Soil", "Soil"],
"Sand": ["Stone", "Water"],
"Glass": ["Sand", "Fire"],
"Time": ["Glass", "Sand"]
}
The traversal of all paths that lead to the leaves can be done with a depth-first traversal, more specifically, with a post-order traversal. That way the traversal will list the edges (i.e. the actions to take) in a chronological (topological) order.
Here is an implementation in JavaScript, with a run for the "Time" element:
const graph = {
"Air": [],
"Fire": [],
"Soil": [],
"Water": [],
"Heat": ["Air", "Fire"],
"Plant": ["Soil", "Water"],
"Tree": ["Plant", "Plant"],
"Forest": ["Tree", "Tree"],
"Algae": ["Plant", "Water"],
"Stone": ["Soil", "Soil"],
"Sand": ["Stone", "Water"],
"Glass": ["Sand", "Fire"],
"Time": ["Glass", "Sand"]
};
function build(target) {
if (graph[target].length == 0) { // It is a leaf
return []; // No action needed
}
let actions = [];
for (let child of graph[target]) {
actions.push(...build(child));
}
actions.push("Use " graph[target] " to create " target);
return actions;
}
let actions = build("Time");
console.log(actions);The size of the returned array of steps is what you called "depth" (6 in the example of "Time").
If you're only interested in the size and not the steps themselves, it is easy to simplify the above code to just return a step counter.
It would also be appropriate to use memoization, i.e. store calculated "depths" with each node so you would not do the calculation a second time.
Here is a version that only returns the step-count and uses memoization:
const graph = {
"Air": [],
"Fire": [],
"Soil": [],
"Water": [],
"Heat": ["Air", "Fire"],
"Plant": ["Soil", "Water"],
"Tree": ["Plant", "Plant"],
"Forest": ["Tree", "Tree"],
"Algae": ["Plant", "Water"],
"Stone": ["Soil", "Soil"],
"Sand": ["Stone", "Water"],
"Glass": ["Sand", "Fire"],
"Time": ["Glass", "Sand"]
};
const steps = {}; // Memoization of the number of steps needed for a component
function build(target) {
if (graph[target].length == 0) { // It is a leaf
return 0; // No action needed
}
if (target in steps) { // We have calculated this before
return steps[target];
}
let actionCount = 1;
for (let child of graph[target]) {
actionCount = build(child);
}
// Store for later reuse
steps[target] = actionCount;
return actionCount;
}
let actionCount = build("Time");
console.log(actionCount);For "discovering" (i.e. building) all nodes, and to minimise the number of steps for it, we should find the "roots" of the graph, the nodes that have no parent (i.e. elements which are not used as component for another). When we have built those, we know we will have built all.
As we need to know the children, the build count, the parents for each node, it is time to create a Node class, and have these as instance properties.
Here it is an implementation and run on the larger JSON you provided:
class Node {
constructor(element) {
this.element = element;
this.children = [];
this.parents = [];
this.buildCount = 0; // Default
}
build() {
if (this.children.length > 0 && this.buildCount == 0) { // Not yet calculated
this.buildCount = 1; // Count the last step of combining the children
for (let child of this.children) {
this.buildCount = child.build();
}
}
return this.buildCount;
}
}
function solve(adjacency) {
const graph = {};
// Create a node instance for each element
for (const element in adjacency) {
graph[element] = new Node(element);
}
// Populate children & parents lists of each node
for (const element in adjacency) {
for (const child of adjacency[element]) {
graph[element].children.push(graph[child]);
graph[child].parents.push(graph[element]);
}
}
let buildCount = 0;
// Explicitly build all nodes that have no parent (are not used for another element)
for (const node of Object.values(graph)) {
if (node.parents.length == 0) {
buildCount = node.build();
}
}
return buildCount;
}
// Run on the larger JSON:
const adjacency = {"Air": [],"Fire": [],"Soil": [],"Water": [],"Acorn" : ["Time" , "Tree"],"Adhesive tape" : ["Glue" , "Ribbon"],"Aircraft" : ["Air" , "Metal"],"Airship" : ["Balloon" , "Metal" , "Rope"],"Algae" : ["Plant" , "Water"],"Anchor" : ["Chain" , "Metal" , "Water"],"Angel" : ["Bird" , "Human"],"Anvil" : ["Hammer" , "Human"],"Apple" : ["Gravity" , "Tree"],"Aquarium" : ["Fish" , "Glass" , "Water"],"Armor" : ["Clothes" , "Metal"],"Arrow" : ["Blade" , "Feather" , "Stick"],"Ash" : ["Bonfire" , "Water"],"Asteroid" : ["Space" , "Stone"],"Atom" : ["Electron" , "Neutron" , "Proton"],"Axe" : ["Blade" , "Stick" , "Wood"],"Baby" : ["Human" , "Human" , "Love"],"Bacteria" : ["Life" , "Ocean"],"Ball" : ["Air" , "Rubber"],"Balloon" : ["Air" , "Rope" , "Rubber"],"Bandage" : ["Cloth" , "Ribbon"],"Bank" : ["House" , "Money"],"Baobab" : ["Savannah" , "Tree"],"Barrel" : ["Board" , "Circle" , "Metal"],"Bat" : ["Air" , "Blood"],"Battery" : ["Electricity" , "Energy" , "Metal"],"Beach" : ["Ocean" , "Sand"],"Bear" : ["Cave" , "Claw"],"Bed" : ["Pillow" , "Wood"],"Bee" : ["Flower" , "Insect"],"Beer" : ["Water" , "Wheat"],"Binoculars" : ["Telescope" , "Telescope"],"Bird" : ["Air" , "Life"],"Birdhouse" : ["Bird" , "House"],"Bitcoin" : ["Coin" , "Electricity"],"Black hole" : ["Gravity" , "Gravity" , "Gravity"],"Blade" : ["Metal" , "Tool"],"Blood" : ["Blade" , "Human"],"Boar" : ["Forest" , "Pig"],"Board" : ["Tool" , "Wood" , "Wood"],"Boat" : ["Paddle" , "Raft"],"Bone" : ["Sword" , "Zombie"],"Bonfire" : ["Fire" , "Stick" , "Stick"],"Book" : ["Cardboard" , "Ink" , "Paper"],"Bottle" : ["Plastic" , "Water"],"Bow" : ["Rope" , "Stick"],"Box" : ["Cardboard" , "Cardboard"],"Brain" : ["Neuron" , "Neuron" , "Neuron"],"Bread" : ["Dough" , "Fire"],"Brick" : ["Clay" , "Fire"],"Brush" : ["Paper" , "Tool"],"Bubble" : ["Air" , "Soap"],"Bucket" : ["Metal" , "Plastic" , "Water"],"Bug" : ["Insect" , "Tree"],"Bulb" : ["Electricity" , "Glass"],"Butterfly" : ["Caterpillar" , "Time"],"Cacao" : ["Sun" , "Tree"],"Cactus" : ["Needle" , "Plant"],"Cake" : ["Dough" , "Ice cream"],"Calendar" : ["Paper" , "Time"],"Camel" : ["Desert" , "Horse"],"Camouflage" : ["Chameleon" , "Cloth"],"Candle" : ["Fire" , "Wax"],"Candy" : ["Chocolate" , "Paper"],"Canon" : ["Gunpowder" , "Pipe"],"Car" : ["Road" , "Wheel"],"Cardboard" : ["Paper" , "Paper"],"Castle" : ["Tower" , "Wall"],"Cat" : ["Human" , "Tiger"],"Caterpillar" : ["Earthworm" , "Plant"],"Cave" : ["Mountain" , "Time"],"Centaur" : ["Horse" , "Human"],"Ceramic" : ["Clay" , "Heat"],"Cerberus" : ["Dog" , "Dog" , "Dog"],"Chain" : ["Metal" , "Rope"],"Chalk" : ["Limestone" , "Pencil"],"Chameleon" : ["Lizard" , "Rainbow"],"Cheese" : ["Milk" , "Time"],"Cheetah" : ["Cat" , "Savannah" , "Wind"],"Chest" : ["Box" , "Wood"],"Chocolate" : ["Cacao" , "Sugar"],"Christmas tree" : ["Garland" , "Spruce" , "Star"],"Circle" : ["Dividers" , "Paper"],"Circus" : ["Clown" , "House"],"Claw" : ["Blade" , "Bone"],"Clay" : ["River" , "Shovel"],"Clock" : ["Battery" , "Time"],"Cloth" : ["Thread" , "Thread"],"Clothes" : ["Cloth" , "Needle"],"Cloud" : ["Air" , "Water"],"Clown" : ["Holiday" , "Human"],"Coal" : ["Fire" , "Plant"],"Cobweb" : ["Fly" , "Spider"],"Coffee" : ["Cacao" , "Heat" , "Water"],"Coin" : ["Circle" , "Gold"],"Comb" : ["Hair" , "Plastic"],"Compass" : ["Electricity" , "Magnet"],"Concrete" : ["Sand" , "Water"],"Cookie" : ["Cacao" , "Dough" , "Milk"],"Cotton" : ["Cloud" , "Grass"],"Cow" : ["Life" , "Meadow"],"Crab" : ["Fish" , "Scissors"],"Crocodile" : ["Lizard" , "Swamp"],"Crossbow" : ["Bow" , "Metal"],"Crown" : ["Gem" , "Gold"],"Death" : ["Life" , "Time"],"Deer" : ["Forest" , "Horse"],"Desert" : ["Sand" , "Sun"],"Diamond" : ["Coal" , "Pressure"],"Dinosaur" : ["Fossil" , "Life"],"Dirt" : ["Ash" , "Water"],"Dividers" : ["Needle" , "Pencil"],"Doctor" : ["Human" , "Medicine"],"Dog" : ["Human" , "Wolf"],"Door" : ["Board" , "Wall"],"Dough" : ["Flour" , "Water"],"Dragon" : ["Fire" , "Lizard"],"Drum" : ["Barrel" , "Leather"],"Duck" : ["Bird" , "Lake"],"Dynamite" : ["Gunpowder" , "Rope"],"Eagle" : ["Bird" , "Mountain"],"Earthworm" : ["Life" , "Soil"],"Eclipse" : ["Moon" , "Sun"],"Eel" : ["Earthworm" , "Electricity"],"Egg" : ["Bird" , "Bird"],"Electricity" : ["Metal" , "Thunderbolt"],"Electron" : ["Electricity" , "Electricity"],"Energy" : ["Thunderbolt" , "Thunderbolt"],"Engine" : ["Metal" , "Steam"],"Explosion" : ["Fire" , "Gunpowder"],"Eye" : ["Lens" , "Life"],"Fangs" : ["Blade" , "Tooth"],"Fat" : ["Blade" , "Pig"],"Feather" : ["Bird" , "Hammer"],"Firefly" : ["Bulb" , "Insect"],"Fireworks" : ["Explosion" , "Rocket"],"Fish" : ["Life" , "Water"],"Fishing rod" : ["Earthworm" , "Rope" , "Stick"],"Flag" : ["Cloth" , "Stick"],"Flashlight" : ["Battery" , "Light"],"Flask" : ["Glass" , "Water"],"Flour" : ["Wheat" , "Windmill"],"Flower" : ["Life" , "Plant"],"Flute" : ["Pipe" , "Wind"],"Fly" : ["Air" , "Insect"],"Footwear" : ["Cloth" , "Soil"],"Forest" : ["Tree" , "Tree"],"Fork" : ["Pitchfork" , "Steak"],"Fossil" : ["Brush" , "Shovel" , "Soil"],"Fountain" : ["Pressure" , "Water"],"Fridge" : ["Electricity" , "Frost"],"Fried egg" : ["Egg" , "Fire"],"Frog" : ["Life" , "Swamp"],"Frost" : ["Air" , "Wind"],"Furnace" : ["Coal" , "Fire" , "Stone"],"Garland" : ["Bulb" , "Bulb" , "Bulb"],"Gasoline" : ["Petroleum" , "Steam"],"Gear" : ["Metal" , "Wheel"],"Gem" : ["Mountain" , "Pickaxe"],"Ghost" : ["Death" , "Human"],"Gift" : ["Box" , "Ribbon"],"Glass" : ["Fire" , "Sand"],"Glasses" : ["Eye" , "Lens" , "Plastic"],"Glue" : ["Flour" , "Heat" , "Water"],"Gold" : ["Gem" , "Metal"],"Golem" : ["Life" , "Stone"],"Grapes" : ["Plant" , "Stick" , "Sun"],"Grass" : ["Plant" , "Soil"],"Grasshopper" : ["Grass" , "Insect"],"Gravity" : ["Soil" , "Soil" , "Soil"],"Greenhouse" : ["Glass" , "Plant"],"Guitar" : ["String" , "String" , "Wood"],"Gunpowder" : ["Coal" , "Saltpeter"],"Hair" : ["Human" , "Wax"],"Hammer" : ["Stick" , "Stone"],"Hammerhead shark" : ["Fish" , "Hammer"],"Hamster" : ["Mouse" , "Wheat"],"Hand fan" : ["Paper" , "Wind"],"Harp" : ["Bow" , "String"],"Hay" : ["Grass" , "Heat"],"Healing potion" : ["Flask" , "Life"],"Health" : ["Apple" , "Human"],"Heart" : ["Blood" , "Engine"],"Heat" : ["Air" , "Fire"],"Hedgehog" : ["Mouse" , "Needle"],"Hen" : ["Bird" , "Wheat"],"Hippo" : ["Cow" , "River"],"Holiday" : ["Balloon" , "Cake" , "Fireworks"],"Honey" : ["Bee" , "Flower"],"Hookah" : ["Flask" , "Steam" , "Tobacco"],"Horns" : ["Blade" , "Bone" , "Bone"],"Horse" : ["Hay" , "Life"],"Hospital" : ["Health" , "House"],"House" : ["Concrete" , "Glass" , "Wood"],"Human" : ["Cave" , "Life"],"Hydrogen" : ["Sun" , "Time"],"Hyena" : ["Dog" , "Savannah"],"Ice" : ["Frost" , "Water"],"Ice cream" : ["Ice" , "Sugar"],"Iceberg" : ["Ice" , "Water"],"Ink" : ["Octopus" , "Pressure"],"Insect" : ["Earthworm" , "Soil"],"Island" : ["Ocean" , "Soil"],"Jungle" : ["Forest" , "Rain"],"Kettlebell" : ["Gravity" , "Metal"],"Key" : ["Lock" , "Tool"],"King" : ["Crown" , "Human"],"Kite" : ["Air" , "Cloth" , "Rope"],"Knight" : ["Armor" , "Human" , "Sword"],"Lake" : ["Water" , "Water"],"Lava" : ["Fire" , "Soil"],"Leaf" : ["Tree" , "Wind"],"Leather" : ["Hammer" , "Pig"],"Leech" : ["Blood" , "Earthworm"],"Lens" : ["Glass" , "Light"],"Lever" : ["Gear" , "Stick"],"Life" : ["Energy" , "Water"],"Light" : ["Sky" , "Sun"],"Lighthouse" : ["Light" , "Tower"],"Limestone" : ["River" , "Stone"],"Lion" : ["Cat" , "Savannah"],"Lizard" : ["Grass" , "Life"],"Lock" : ["Chest" , "Gear"],"Locomotive" : ["Car" , "Railway"],"Lollipop" : ["Candy" , "Stick"],"Love" : ["Human" , "Human"],"Magic wand" : ["Star" , "Stick"],"Magnet" : ["Electricity" , "Metal"],"Mana potion" : ["Flask" , "Star"],"Mantis" : ["Insect" , "Leaf"],"Map" : ["Compass" , "Paper"],"Mask" : ["Cloth" , "Rope"],"Match" : ["Coal" , "Stick"],"Meadow" : ["Grass" , "Soil"],"Meat" : ["Blade" , "Cow"],"Medicine" : ["Bacteria" , "Health"],"Mercury" : ["Silver" , "Water"],"Mermaid" : ["Fish" , "Human"],"Metal" : ["Fire" , "Stone"],"Meteor" : ["Asteroid" , "Fire"],"Microphone" : ["Sound" , "Stick"],"Milk" : ["Bucket" , "Cow"],"Mine" : ["Cave" , "Pickaxe"],"Minotaur" : ["Cow" , "Human"],"Mirror" : ["Glass" , "Light" , "Water"],"Moat" : ["Castle" , "River"],"Mole" : ["Mouse" , "Soil"],"Molecule" : ["Atom" , "Atom"],"Money" : ["Gold" , "Paper"],"Monkey" : ["Life" , "Tree"],"Moon" : ["Sky" , "Stone"],"Mosquito" : ["Blood" , "Fly"],"Mountain" : ["Soil" , "Stone"],"Mouse" : ["Life" , "Wheat"],"Mummy" : ["Bandage" , "Human"],"Mushroom" : ["Grass" , "Rain"],"Music" : ["Needle" , "Vinyl disk"],"Nail" : ["Hammer" , "Metal" , "Stick"],"Needle" : ["Metal" , "Thread"],"Nest" : ["Bird" , "Egg" , "Tree"],"Net" : ["Cobweb" , "Water"],"Neuron" : ["Electricity" , "Life"],"Neutron" : ["Electron" , "Proton"],"Nunchaku" : ["Chain" , "Stick" , "Stick"],"Obsidian" : ["Lava" , "Water"],"Ocean" : ["Water" , "Water" , "Water"],"Octopus" : ["Fish" , "Vacuum"],"Orca" : ["Ice" , "Whale"],"Ore" : ["Mine" , "Pickaxe"],"Ostrich" : ["Bird" , "Sand"],"Owl" : ["Bird" , "Claw"],"Oxygen" : ["Plant" , "Sun"],"Ozone" : ["Oxygen" , "Sun"],"Paddle" : ["Stick" , "Water"],"Paints" : ["Board" , "Rainbow"],"Panda" : ["Bear" , "Jungle"],"Paper" : ["Tool" , "Wood"],"Parrot" : ["Bird" , "Jungle"],"Pearl" : ["Gem" , "Water"],"Pegasus" : ["Bird" , "Horse"],"Pen" : ["Ink" , "Plastic"],"Pencil" : ["Coal" , "Wood"],"Penguin" : ["Bird" , "Frost"],"Petroleum" : ["Fossil" , "Plant" , "Soil"],"Phoenix" : ["Bird" , "Fire"],"Photo camera" : ["Light" , "Metal" , "Paper"],"Pickaxe" : ["Mountain" , "Tool"],"Picture" : ["Brush" , "Paints" , "Paper"],"Pie" : ["Apple" , "Flour"],"Pig" : ["Dirt" , "Life"],"Pigeon" : ["Bird" , "Bread"],"Pillow" : ["Cloth" , "Feather"],"Pipe" : ["Air" , "Metal" , "Stick"],"Pitchfork" : ["Hay" , "Tool"],"Plant" : ["Soil" , "Water"],"Plastic" : ["Coal" , "Petroleum"],"Plunger" : ["Rubber" , "Stick" , "Vacuum"],"Poison" : ["Flask" , "Snake"],"Polar bear" : ["Bear" , "Snow"],"Potion of Speed" : ["Flask" , "Wind"],"Potion of Strength" : ["Flask" , "Mountain"],"Potion of Wisdom" : ["Flask" , "Owl"],"Pressure" : ["Air" , "Heat"],"Propane" : ["Fire" , "Petroleum"],"Proton" : ["Electron" , "Gravity"],"Puddle" : ["Road" , "Water"],"Pyramid" : ["Mountain" , "Sand"],"Radio" : ["Metal" , "Sound"],"Raft" : ["Water" , "Wood"],"Railway" : ["Metal" , "Road"],"Rain" : ["Cloud" , "Water"],"Rainbow" : ["Rain" , "Sun"],"Raincoat" : ["Clothes" , "Rain"],"Rake" : ["Comb" , "Stick"],"Rhinoceros" : ["Horns" , "Savannah"],"Ribbon" : ["Cloth" , "Scissors"],"Ring" : ["Circle" , "Metal"],"River" : ["Soil" , "Water" , "Water"],"Road" : ["Concrete" , "Soil"],"Robot" : ["Battery" , "Human"],"Rocket" : ["Fire" , "Pipe"],"Rope" : ["Thread" , "Thread" , "Thread"],"Rose" : ["Flower" , "Love"],"Rubber" : ["Petroleum" , "Water"],"Ruler" : ["Board" , "Pencil"],"Safe" : ["Lock" , "Money"],"Salt" : ["Heat" , "Ocean"],"Saltpeter" : ["Limestone" , "Plant"],"Sand" : ["Stone" , "Water"],"Savannah" : ["Grass" , "Soil" , "Sun"],"Scalpel" : ["Blade" , "Health"],"Scissors" : ["Blade" , "Blade"],"Scoop-net" : ["Net" , "Stick"],"Scooter" : ["Wheel" , "Wheel"],"Scorpion" : ["Crab" , "Desert"],"Sculpture" : ["Human" , "Stone"],"Sea cow" : ["Cow" , "Water"],"Seagull" : ["Bird" , "Ocean"],"Seahorse" : ["Fish" , "Horse"],"Sewing machine" : ["Electricity" , "Needle"],"Shark" : ["Fish" , "Tooth"],"Sheep" : ["Cloud" , "Life"],"Shield" : ["Board" , "Metal"],"Ship" : ["Cloth" , "Water" , "Wood"],"Shovel" : ["Soil" , "Tool"],"Silver" : ["Coin" , "Furnace"],"Skateboard" : ["Board" , "Wheel"],"Skates" : ["Blade" , "Footwear" , "Ice"],"Skull" : ["Bone" , "Brain"],"Sky" : ["Air" , "Air" , "Air"],"Slingshot" : ["Rubber" , "Stick"],"Smartphone" : ["Microphone" , "Radio"],"Snail" : ["Caterpillar" , "Glue"],"Snake" : ["Earthworm" , "Fangs"],"Snow" : ["Frost" , "Rain"],"Snowman" : ["Human" , "Snow"],"Soap" : ["Ash" , "Fat"],"Soda" : ["Air" , "Sugar" , "Water"],"Solar panel" : ["Energy" , "Sun"],"Sound" : ["Air" , "Explosion"],"Space" : ["Sky" , "Star"],"Spear" : ["Blade" , "Stick" , "Stick"],"Sphinx" : ["Human" , "Lion"],"Spider" : ["Insect" , "Insect"],"Spine" : ["Bone" , "Neuron"],"Sport" : ["Human" , "Kettlebell"],"Spruce" : ["Needle" , "Tree"],"Spyglass" : ["Lens" , "Pipe"],"Squirrel" : ["Acorn" , "Mouse"],"Star" : ["Sky" , "Telescope"],"Starfish" : ["Ocean" , "Star"],"Steak" : ["Fire" , "Meat"],"Steam" : ["Fire" , "Water"],"Stick" : ["Blade" , "Plant"],"Stone" : ["Soil" , "Soil"],"Stopwatch" : ["Ruler" , "Time"],"String" : ["Sound" , "Thread"],"Stump" : ["Axe" , "Tree"],"Sugar" : ["Sugar cane" , "Windmill"],"Sugar cane" : ["Plant" , "Stick" , "Water"],"Sulfur" : ["Ash" , "Lava"],"Sulfuric acid" : ["Hydrogen" , "Oxygen" , "Sulfur"],"Sun" : ["Fire" , "Sky"],"Sunflower" : ["Flower" , "Sun"],"Surfboard" : ["Board" , "Wave"],"Sushi" : ["Algae" , "Fish"],"Swamp" : ["Grass" , "Lake"],"Sword" : ["Blade" , "Stick"],"Swordfish" : ["Fish" , "Sword"],"Syringe" : ["Health" , "Needle"],"Tank" : ["Metal" , "Turtle"],"Tape measure" : ["Ribbon" , "Ruler"],"Tea" : ["Heat" , "Plant" , "Water"],"Tear" : ["Eye" , "Water"],"Telescope" : ["Lens" , "Sky"],"Tent" : ["Cloth" , "House" , "Stick"],"Thermometer" : ["Heat" , "Mercury"],"Thread" : ["Cobweb" , "Cobweb"],"Thunderbolt" : ["Cloud" , "Cloud" , "Cloud"],"Tide" : ["Moon" , "Ocean"],"Tiger" : ["Jungle" , "Life"],"Time" : ["Glass" , "Sand"],"Tobacco" : ["Plant" , "Steam"],"Tool" : ["Human" , "Metal" , "Wood"],"Tooth" : ["Bone" , "Pressure"],"Toothbrush" : ["Tool" , "Tooth"],"Toothpaste" : ["Health" , "Tooth"],"Toothpick" : ["Stick" , "Tooth"],"Torch" : ["Fire" , "Stick"],"Tornado" : ["Energy" , "Wind"],"Tower" : ["House" , "House"],"Traffic light" : ["Garland" , "Road"],"Treasure" : ["Chest" , "Island"],"Tree" : ["Plant" , "Plant"],"Trojan horse" : ["Horse" , "Wood"],"Turtle" : ["Egg" , "Sand"],"Umbrella" : ["Cloth" , "Rain"],"Unicorn" : ["Horse" , "Magic wand"],"Vacuum" : ["Glass" , "Space"],"Vampire" : ["Blood" , "Human"],"Vinyl disk" : ["Plastic" , "Wax"],"Violin" : ["String" , "Wood"],"Volcano" : ["Lava" , "Mountain"],"Wall" : ["Brick" , "Concrete"],"Wallpaper" : ["Glue" , "Paper" , "Wall"],"Walrus" : ["Fangs" , "Sea cow"],"Waterfall" : ["Mountain" , "Water"],"Wave" : ["Energy" , "Ocean"],"Wax" : ["Bee" , "Bee"],"Well" : ["Bucket" , "Shovel" , "Soil"],"Werewolf" : ["Human" , "Moon" , "Wolf"],"Whale" : ["Fish" , "Fountain"],"Wheat" : ["Shovel" , "Soil" , "Water"],"Wheel" : ["Air" , "Pressure" , "Rubber"],"Wig" : ["Hair" , "Hair"],"Wind" : ["Air" , "Air"],"Windmill" : ["Stone" , "Wind"],"Window" : ["Glass" , "Wood"],"Wine" : ["Grapes" , "Water"],"Wire" : ["Electricity" , "Metal" , "Plastic"],"Wolf" : ["Forest" , "Life"],"Wood" : ["Forest" , "Human"],"Woodpecker" : ["Bird" , "Wood"],"Wool" : ["Scissors" , "Sheep"],"Zebra" : ["Horse" , "Savannah"],"Zombie" :["Death", "Life"]};
const buildCount = solve(adjacency);
console.log("Total number of steps to discover all elements:", buildCount);The output is 27435.
CodePudding user response：
As the previous answer pointed out, this is a directed acyclic graph problem. The nodes are composed elements, the leafs are basic elements. In order to calculate the depth, you just traverse the tree to find out.
In Haskell, this looks rather neat (while at first thought I considered Prolog for that, I settled with Haskell as it is really pretty in this case).
-- The base elements are simply numbers
-- (could be strings as well - but that would just be eye candy).
data Element =
Basic(Integer)
| Composed(Element,Element)
deriving (Show,Eq)
depth:: Element -> Integer
depth (Basic _) = 0
depth (Composed(a, b)) =
1 max (depth a) (depth b)
air = Basic 1
fire = Basic 2
soil = Basic 3
water = Basic 4
heat = Composed(air,fire)
plant = Composed(soil,water)
algae = Composed(plant,water)
If loaded into the REPL and executing the function, we get the correct result.
*Main> depth algae
2
For just 400 elements, at this point you would be done as it is still a "small" problem and the run time should be below noticeable. In order to speed it up, one idea could be to add data automatically to Composed elements (such as the depth) so you can prune the tree. The same idea at search time could be a form of memoization.