Input data:
HashMap filled with objects.
Each Aspect object consists of a key ( String , object name) and two objects of the same class (that is, each object consists of two objects, except for 6 basic objects, in which the sub-object fields are null ).

The task: to build an algorithm that, when two objects are introduced, will output the shortest chain of objects combining these two objects.

Class Content:

 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collections; import java.util.HashMap; import java.util.Map; /** * Created by Vampirenostra on 16.01.2017. */ public class Aspect { private String name; private Aspect con1; private Aspect con2; public static ArrayList<Aspect> list = new ArrayList<>(); public static HashMap<String,Aspect> aspects = new HashMap<>(); Aspect (String name, Aspect con1,Aspect con2){this.name=name;this.con1=con1;this.con2=con2;} Aspect(String name){this.name=name;} public String toString() { if (java.util.Objects.equals(con1, null))return name; else return name+" "+con1+" "+con2+" "; } public static void addAspects() { aspects.put("Aer", new Aspect("Aer")); aspects.put("Terra", new Aspect("Terra")); aspects.put("Aqua", new Aspect("Aqua")); aspects.put("Ignis", new Aspect("Ignis")); aspects.put("Ordo", new Aspect("Ordo")); aspects.put("Perditio", new Aspect("Perditio")); aspects.put("Lux", new Aspect("Lux", aspects.get("Aer"), aspects.get("Ignis"))); aspects.put("Motus", new Aspect("Motus", aspects.get("Aer"), aspects.get("Ordo"))); aspects.put("Gelum", new Aspect("Gelum", aspects.get("Ignis"), aspects.get("Perditio"))); aspects.put("Victus", new Aspect("Victus", aspects.get("Terra"), aspects.get("Aqua"))); aspects.put("Tempestas", new Aspect("Tempestas", aspects.get("Aer"), aspects.get("Aqua"))); aspects.put("Vacuos", new Aspect("Vacuos", aspects.get("Perditio"),aspects.get("Aer"))); aspects.put("Potentia", new Aspect("Potentia", aspects.get("Ignis"), aspects.get("Ordo"))); aspects.put("Viterus", new Aspect("Viterus", aspects.get("Ordo"), aspects.get("Terra"))); aspects.put("Permutatio", new Aspect("Permutatio",aspects.get("Perditio"),aspects.get("Ordo"))); aspects.put("Venenum", new Aspect("Venenum", aspects.get("Aqua"), aspects.get("Perditio"))); aspects.put("Fames", new Aspect("Fames", aspects.get("Vacuos"), aspects.get("Victus"))); aspects.put("Bestia", new Aspect("Bestia", aspects.get("Victus"), aspects.get("Motus"))); aspects.put("Metallum", new Aspect("Metallum", aspects.get("Terra"), aspects.get("Viterus"))); aspects.put("Herba", new Aspect("Herba", aspects.get("Terra"), aspects.get("Victus"))); aspects.put("Sano", new Aspect("Sano", aspects.get("Victus"), aspects.get("Ordo"))); aspects.put("Mortuus", new Aspect("Mortuus", aspects.get("Victus"), aspects.get("Perditio"))); aspects.put("Praecantatio", new Aspect("Praecantatio",aspects.get("Vacuos"),aspects.get("Potentia"))); aspects.put("Limus", new Aspect("Limus", aspects.get("Aqua"), aspects.get("Victus"))); aspects.put("Iter", new Aspect("Iter", aspects.get("Terra"), aspects.get("Motus"))); aspects.put("Tenebrae", new Aspect("Tenebrae", aspects.get("Lux"), aspects.get("Vacuos"))); aspects.put("Volatus", new Aspect("Volatus", aspects.get("Aer"), aspects.get("Motus"))); aspects.put("Vinculum", new Aspect("Vinculum", aspects.get("Perditio"),aspects.get("Motus"))); aspects.put("Spiritus", new Aspect("Spiritus", aspects.get("Victus"), aspects.get("Mortuus"))); aspects.put("Auram", new Aspect("Auram", aspects.get("Aer"), aspects.get("Praecantatio"))); aspects.put("Exanimis", new Aspect("Exanimis", aspects.get("Mortuus"), aspects.get("Motus"))); aspects.put("Vitium", new Aspect("Vitium", aspects.get("Perditio"),aspects.get("Praecantatio"))); aspects.put("Corpus", new Aspect("Corpus", aspects.get("Bestia"), aspects.get("Mortuus"))); aspects.put("Alienis", new Aspect("Alienis", aspects.get("Tenebrae"),aspects.get("Vacuos"))); aspects.put("Sensus", new Aspect("Sensus", aspects.get("Aer"), aspects.get("Spiritus"))); aspects.put("Cognitio", new Aspect("Cognitio", aspects.get("Ignis"), aspects.get("Spiritus"))); aspects.put("Arbor", new Aspect("Arbor", aspects.get("Aer"), aspects.get("Herba"))); aspects.put("Humanus", new Aspect("Humanus", aspects.get("Cognitio"),aspects.get("Bestia"))); aspects.put("Messis", new Aspect("Messis", aspects.get("Humanus"), aspects.get("Herba"))); aspects.put("Lucrum", new Aspect("Lucrum", aspects.get("Humanus"), aspects.get("Fames"))); aspects.put("Instrumentum", new Aspect("Instrumentum",aspects.get("Humanus"),aspects.get("Ordo"))); aspects.put("Perfodio", new Aspect("Perfodio", aspects.get("Humaus"), aspects.get("Terra"))); aspects.put("Fabrico", new Aspect("Fabrico", aspects.get("Humanus"), aspects.get("Instrumentum"))); aspects.put("Machina", new Aspect("Machina", aspects.get("Motus"), aspects.get("Instrumentum"))); aspects.put("Pannus", new Aspect("Pannus", aspects.get("Bestia"), aspects.get("Instrumentum"))); aspects.put("Tutamen", new Aspect("Tutamen", aspects.get("Terra"), aspects.get("Instrumentum"))); aspects.put("Telum", new Aspect("Telum", aspects.get("Ignis"), aspects.get("Instrumentum"))); aspects.put("Meto", new Aspect("Meto", aspects.get("Messis"), aspects.get("Instrumentum"))); } public static String input() throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); return br.readLine(); } public static boolean check(String x){return aspects.containsKey(x);} public static ArrayList<Aspect> upList (String asp) { ArrayList<Aspect> upList = new ArrayList<>(); for(Aspect aspect : aspects.values()) {if (aspect.con1!=null&&(aspect.con1.name.equals(asp)||aspect.con2.name.equals(asp))) {upList.add(aspect);}} return upList; } public static ArrayList<Aspect> downList(String asp) { ArrayList<Aspect> downList = new ArrayList<>(); downList.add(aspects.get(asp).con1); downList.add(aspects.get(asp).con2); return downList; } public static ArrayList<String> same() { ArrayList<String> same = new ArrayList<>(); ArrayList<Aspect> list = upList(Main.asp1); String tmp = list.toString(); tmp=tmp.replaceAll(",","");tmp=tmp.replaceAll("]","");tmp=tmp.replaceAll("\\[" ,""); while (tmp.contains(" ")){tmp=tmp.replaceAll(" "," ");} if(tmp.endsWith(" ")){tmp=tmp.trim();} String[] tmp1 = tmp.split(" "); ArrayList<String> one = new ArrayList<>(); Collections.addAll(one, tmp1); list = upList(Main.asp2); tmp = list.toString(); tmp=tmp.replaceAll(",","");tmp=tmp.replaceAll("]","");tmp=tmp.replaceAll("\\[" ,""); while (tmp.contains(" ")){tmp=tmp.replaceAll(" "," ");} if(tmp.endsWith(" ")){tmp=tmp.trim();} tmp1 = tmp.split(" "); ArrayList<String> two = new ArrayList<>(); Collections.addAll(two, tmp1); System.out.println(one.size()+" "+two.size()); Map<String,String> map = new HashMap<>(); for (String text:one) {map.put(text,null);} one=new ArrayList<>(); for (String text:map.keySet()) {one.add(text);} map = new HashMap<>(); for (String text:two) {map.put(text,null);} two=new ArrayList<>(); for (String text:map.keySet()) {two.add(text);same.add(text);} same.retainAll(one); return same; } public static void listPrint (ArrayList <Aspect> list) { for (Aspect aspect : list) {System.out.println(aspect);} } }
  • Specify what should be the help? - Kromster
  • 1. We need an algorithm for finding a chain of interrelated objects. 2. Save these chains in a valid List for later rejection on size (). - Vampirenostra
  • You should not push a few commands and curly brackets in one line. This makes the code unreadable. The for (String text:map.keySet()) {two.add(text);same.add(text);} code for (String text:map.keySet()) {two.add(text);same.add(text);} should occupy 5 (4, if put { on the same line) lines, and not one. - Regent

1 answer 1

You can make a list of connections between objects (the graph whose vertices are Aspect s, and the edges are the connections between them), and then use the search in width:

 public static ArrayList<Aspect> findShortestWay(Aspect first, Aspect second) { //построение связей HashMap<String, ArrayList<Aspect>> aspectNameToRelatedAspects = new HashMap<>(); for (Aspect aspect : aspects.values()) { ArrayList<Aspect> relatedAspects = new ArrayList<>(); if (aspect.con1 != null) { relatedAspects.add(aspect.con1); } if (aspect.con2 != null) { relatedAspects.add(aspect.con2); } for (Aspect otherAspect : aspects.values()) { if (aspect.equals(otherAspect) || otherAspect.equals(aspect.con1) || otherAspect.equals(aspect.con2)) { continue; } if (aspect.equals(otherAspect.con1) || aspect.equals(otherAspect.con2)) { relatedAspects.add(otherAspect); } } aspectNameToRelatedAspects.put(aspect.name, relatedAspects); } //поиск в ширину HashMap<String, Aspect> aspectNameToPreviousAspect = new HashMap<>(); aspectNameToPreviousAspect.put(first.name, first); ArrayList<Aspect> queue = new ArrayList<>(); queue.add(first); while (!queue.isEmpty()) { Aspect aspect = queue.remove(0); if (aspect.equals(second)) { break; } ArrayList<Aspect> relatedAspects = aspectNameToRelatedAspects.get(aspect.name); for (Aspect relatedAspect : relatedAspects) { if (!aspectNameToPreviousAspect.containsKey(relatedAspect.name)) { queue.add(relatedAspect); aspectNameToPreviousAspect.put(relatedAspect.name, aspect); } } } //построение цепочки связей ArrayList<Aspect> way = null; if (aspectNameToPreviousAspect.containsKey(second.name)) { way = new ArrayList<>(); Aspect previousAspect = second; do { way.add(previousAspect); previousAspect = aspectNameToPreviousAspect.get(previousAspect.name); } while (!previousAspect.equals(first)); way.add(first); Collections.reverse(way); } return way; } private boolean equals(Aspect aspect) { return aspect != null && name.equals(aspect.name); } @Override public String toString() { String con1Name = (con1 != null) ? con1.name : "null"; String con2Name = (con2 != null) ? con2.name : "null"; return name + " -> " + con1Name + " " + con2Name; }

And use:

 public static void main(String[] args) { Aspect.addAspects(); ArrayList<Aspect> way = Aspect.findShortestWay(Aspect.aspects.get("Aer"), Aspect.aspects.get("Aqua")); if (way == null) { System.out.println("Связи нет"); } else { for (Aspect aspect : way) { System.out.println(aspect); } } }