Effiziente Methode, um zu überprüfen, ob eine Menge symmetrisch ist

Question

Ich muss einen Validator schreiben, der nach Räumen sucht, die von einem JSON mit Gson analysiert wurden, das für jedes Zimmerpaar A und B, wenn Sie von A nach B gelangen können Sie können hier das Format für die JSON von B nach A.

erhalten: https://jsfiddle.net/tgtbqzky/

{ 
    "initialRoom": "MatthewsStreet", 
    "rooms": [ 
    { 
     "name": "MatthewsStreet", 
     "description": "You are on Matthews, outside the Siebel Center", 
     "directions": [ 
     { 
      "direction": "East", 
      "room": "SiebelEntry" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelEntry", 
     "description": "You are in the west entry of Siebel Center. You can see the elevator, the ACM office, and hallways to the north and east.", 
     "directions": [ 
     { 
      "direction": "West", 
      "room": "MatthewsStreet" 
     }, 
     { 
      "direction": "Northeast", 
      "room": "AcmOffice" 
     }, 
     { 
      "direction": "North", 
      "room": "SiebelNorthHallway" 
     }, 
     { 
      "direction": "East", 
      "room": "SiebelEastHallway" 
     } 
     ] 
    }, 
    { 
     "name": "AcmOffice", 
     "description": "You are in the ACM office. There are lots of friendly ACM people.", 
     "directions": [ 
     { 
      "direction": "South", 
      "room": "SiebelEntry" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelNorthHallway", 
     "description": "You are in the north hallway. You can see Siebel 1112 and the door toward NCSA.", 
     "directions": [ 
     { 
      "direction": "South", 
      "room": "SiebelEntry" 
     }, 
     { 
      "direction": "NorthEast", 
      "room": "Siebel1112" 
     } 
     ] 
    }, 
    { 
     "name": "Siebel1112", 
     "description": "You are in Siebel 1112. There is space for two code reviews in this room.", 
     "directions": [ 
     { 
      "direction": "West", 
      "room": "SiebelNorthHallway" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelEastHallway", 
     "description": "You are in the east hallway. You can see Einstein Bros' Bagels and a stairway.", 
     "directions": [ 
     { 
      "direction": "West", 
      "room": "SiebelEntry" 
     }, 
     { 
      "direction": "South", 
      "room": "Siebel1314" 
     }, 
     { 
      "direction": "Down", 
      "room": "SiebelBasement" 
     } 
     ] 
    }, 
    { 
     "name": "Siebel1314", 
     "description": "You are in Siebel 1314. There are happy CS 126 students doing a code review.", 
     "directions": [ 
     { 
      "direction": "North", 
      "room": "SiebelEastHallway" 
     } 
     ] 
    }, 
    { 
     "name": "SiebelBasement", 
     "description": "You are in the basement of Siebel. You see tables with students working and door to computer labs.", 
     "directions": [ 
     { 
      "direction": "Up", 
      "room": "SiebelEastHallway" 
     } 
     ] 
    } 
    ] 
} 

ich mich gefragt, ob die Art und Weise zwei verschachtelte for-Schleifen zu gehen wäre, wobei die äußere for-Schleife würde Schleife durch alle Räume würde der innere durch jede mögliche Richtung in jedem Loop schleifen, und dann würde ich jedes Paar hinzufügen, das ich in einen Arr bekomme aylist.

Wenn ich auf etwas stoße, das bereits vorhanden ist, würde ich es aus der ArrayList entfernen, und wenn am Ende meiner for-Schleifen die ArrayList immer noch ein Element enthält, ist das entsprechende Paar nicht vorhanden, und Daher ist der JSON ungültig. Wenn die Größe der ArrayList Null ist, sind die Daten gültig.

Hat jemand eine effizientere Methode, dieses Problem zu lösen? Ich habe das Gefühl, da es im Wesentlichen beweist, ob eine gegebene Menge symmetrisch ist, muss es eine optimierte Methode geben.

Answer 1

Sie sollten in der Lage sein, die Symmetrie Ihres Sets zu validieren, indem Sie einen "kanonischen Namen" eines Raumpaares definieren, indem Sie beispielsweise Raumnamen alphabetisch sortieren und alle Raumpaare ihren kanonischen Namen zuordnen:

static String canonicalName(String roomA, String roomB) { 
    if (roomA.compareTo(roomB) < 0) { 
     return roomA + "|" + roomB; 
    } else { 
     return roomB + "|" + roomA; 
    } 
} 

Dies wird den gleichen Schlüssel "AcmOffice|MatthewsStreet" für ein Paar von Räumen, in denen einer von ihnen produzieren "AcmOffice" ist, und das andere ist "MatthewsStreet", unabhängig von der Reihenfolge.

Jetzt können Sie sie auf Listen, wie diese Karte:

Map<String,List<String>> mp = new HashMap<>(); 
for (PairOfRooms pair : allRoomPairs) { 
    String key = canonicalName(pair.roomA, pair.roomB); 
    List<String> list = mp.get(key); 
    if (list == null) { 
     list = new ArrayList<>(); 
     mp.put(key, list); 
    } 
    list.add(pair.roomA + "|" + pair.roomB); 
} 

Nachdem durch alle Paare gehen, untersuchen Sie die Listen innerhalb der Karte:

• Wenn eine Liste zwei verschiedene Elemente hat, alles ist in Ordnung
• Wenn die Liste ein Element enthält, fehlt das symmetrische Element
• Wenn die Liste mehr als zwei Elemente enthält, gibt es doppelte

Answer 2

1. Bauen Sie ein Proxy-Objekt für ein Paar Raum A, B, Richtung
2. implementieren ein equals und compareTo
3. ein Verfahren implementieren das entgegengesetzte Zimmer zu bekommen
4. die Elemente, die Sie in einem deserialisiert Put Array.
5. Verwenden Sie eine Karte, um zu überprüfen, ob die entgegengesetzten Wege gefunden wurden.

Es läuft in O (n)

Welche

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class RoomPath implements Comparable<RoomPath> 
{ 
    String from; 
    String to; 
    String direction; 

    public RoomPath(String A, String B, String dir) 
    { 
     from = A; 
     to = B; 
     direction = dir; 
    } 

    public RoomPath opposite() 
    { 
     String oppDirection =""; 
     switch(direction) 
     { 
      case "North" : oppDirection = "South"; break; 
      case "South" : oppDirection = "North"; break; 
      case "West" : oppDirection = "East"; break; 
      case "East" : oppDirection = "West"; break; 
     } 
     return new RoomPath(to, from, oppDirection); 
    } 

    public int compareTo(RoomPath other) 
    { 
     int v1 = from.compareTo(other.from); 
     if(v1 == 0) 
     { 
      v1 = to.compareTo(other.to); 
      if(v1 == 0) 
      { 
       return direction.compareTo(other.direction); 
      } 
      return v1; 
     } 
     return v1; 
    } 

    public bool equals(Object e) 
    { 
     if (!(e instanceof RoomPath)) return false; 
     RoomPath path = (RoomPath)e; 
     return compareTo(e) == 0; 
    } 

    public int hashCode() { 
     int dirnumber = 0; 
     switch(dirnumber) 
     { 
      case "North" : dirnumber = 0; break; 
      case "South" : dirnumber = 1; break; 
      case "West" : dirnumber = 2; break; 
      case "East" : dirnumber = 3; break; 
     } 

     return (from.hashCode() + 31 * b.hashCode()) << 2 | dirnumber; 
     //left as exercise 
     return 0; 
    } 


} 


/* Name of the class has to be "Main" only if the class is public. */ 
class Ideone 
{ 
    public static void main (String[] args) throws java.lang.Exception 
    { 
     List<RoomPath > roompaths = ... ; //the parsing function 
     List<RoomPath > symetrics = new ArrayList<RoomPath>(); 
     Map<RoomPath, bool> syms = new HashMap<>(); 
     for (RoomPath path : roompaths) 
     { 
      if(!syms.containsKey(path)) 
      { 
       syms.put(path, false); 
      } 

      if(syms.containsKey(path.opposite())) 
      { 
       symetrics.insert(path); 
      } 
     } 
     bool allok = symetrics.size()*2 = roompaths.size(); 
    } 
} 

Answer 3

i die JSON in eine 2D-Matrix wie diese transfrom würde es vorziehen, gibt:

Welche : W für West, E für Est, N für Nord, S für Sud und X bedeutet Abwesenheit des Pfades

So wäre es sehr einfach zu wissen, ob Sie von einem Raum zum anderen Raum gelangen können. Sie müssen nur einige einfache Schleifen implementieren, um über die Matrix zu iterieren.