Created
January 19, 2022 17:20
-
-
Save ethan-gallant/dbad6a716a5e433ed7b5063b60ab6842 to your computer and use it in GitHub Desktop.
Quest Sorting
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import lombok.extern.slf4j.Slf4j; | |
import java.util.Arrays; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Set; | |
import java.util.stream.Collectors; | |
public class Test { | |
public static void main(String[] args) { | |
Set<Quest> quests = new HashSet<>(); | |
// Quest A has no dependencies | |
quests.add(new Quest("quest_a", "")); | |
quests.add(new Quest("quest_a1", "quest_a")); | |
quests.add(new Quest("quest_a11", "quest_a1")); | |
quests.add(new Quest("quest_a111", "quest_a11")); | |
quests.add(new Quest("quest_a2", "quest_a")); | |
quests.add(new Quest("quest_a22", "quest_a2")); | |
quests.add(new Quest("quest_b", "")); | |
quests.add(new Quest("quest_b1", "quest_b")); | |
Set<String> existingQuests = new java.util.HashSet<>(); | |
Set<Quest> questsToSort = new java.util.HashSet<>(quests); | |
// Sort the quests based on insert order | |
int lastInsertedCount = 1; | |
List<Set<Quest>> sortedQuests = new java.util.ArrayList<>(); | |
// no pre requisites | |
// First line prerequisites | |
// SEcond line prerequisites | |
while (!questsToSort.isEmpty()) { | |
if (lastInsertedCount <= 0) { | |
System.out.println("Infinite recrsion, last inserted quests were: "); | |
for (Quest q : sortedQuests.get(sortedQuests.size() - 1)) { | |
System.out.println(q.id); | |
} | |
throw new RuntimeException("Infinite recursion on quest dependencies"); | |
} | |
lastInsertedCount = 0; | |
Set<Quest> questsToInsert = new java.util.HashSet<>(); | |
for (Quest quest : questsToSort) { | |
if (quest.prerequisites == null || quest.prerequisites.isEmpty() || existingQuests.containsAll(quest.prerequisites)) { | |
questsToInsert.add(quest); | |
lastInsertedCount++; | |
} | |
} | |
// Insert quests to rocket | |
existingQuests.addAll(questsToInsert.stream().map(quest -> quest.id).collect(Collectors.toSet())); | |
// Remove quests from todo list | |
questsToSort.removeAll(questsToInsert); | |
// Add them to the sorted list | |
sortedQuests.add(questsToInsert); | |
} | |
int round = 1; | |
for (Set<Quest> questsToInsert : sortedQuests) { | |
System.out.println("======= Round " + round++ + " ======="); | |
for (Quest quest : questsToInsert) { | |
System.out.println(quest.id); | |
} | |
} | |
} | |
static class Quest { | |
String id; | |
Set<String> prerequisites; | |
public Quest(String id, String... prerequisites) { | |
this.id = id; | |
this.prerequisites = new HashSet<>(); | |
if (prerequisites != null) { | |
Arrays.stream(prerequisites).filter(p -> p != null && !p.isEmpty()).forEach(this.prerequisites::add); | |
} | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment