files: import os
  from collections import Counter, OrderedDict
  from enum import Enum
  from math import sqrt
  
  import yaml
  
  from logic.item_types import CONSUMABLE_ITEMS, DUNGEON_NONPROGRESS_ITEMS, DUNGEON_PROGRESS_ITEMS
  from logic.logic import Logic
  from wwrando_paths import DATA_PATH
  import tweaks
  
  ITEM_LOCATION_NAME_TO_EXIT_ZONE_NAME_OVERRIDES = {
    "Pawprint Isle - Wizzrobe Cave": "Pawprint Isle Side Isle",
  }
  
  
  class HintType(Enum):
    PATH = 0
    BARREN = 1
    ITEM = 2
    LOCATION = 3
  
  
  class Hint:
    def __init__(self, type: HintType, place, reward=None):
      self.type = type
      self.place = place
      self.reward = reward
    
    def __str__(self):
      return "<HINT: %s, (%s, %s)>" % (str(self.type), self.place, self.reward)
  
  
  class Hints:
    # A dictionary mapping dungeon name to the dungeon boss.
    # The boss name is used as the path goal in the hint text.
    DUNGEON_NAME_TO_BOSS_NAME = {
      "Dragon Roost Cavern": "Gohma",
      "Forbidden Woods": "Kalle Demos",
      "Tower of the Gods": "Gohdan",
      "Forsaken Fortress": "Helmaroc King",
      "Earth Temple": "Jalhalla",
      "Wind Temple": "Molgera",
      "Hyrule": "Hyrule",
      "Ganon's Tower": "Ganondorf",
    }
    
    # A dictionary mapping dungeon name to the requirement name.
    # This dictionary is used when determining which items are on the path to a goal.
    DUNGEON_NAME_TO_REQUIREMENT_NAME = {
      "Dragon Roost Cavern": "Can Access Other Location \"Dragon Roost Cavern - Gohma Heart Container\"",
      "Forbidden Woods": "Can Access Other Location \"Forbidden Woods - Kalle Demos Heart Container\"",
      "Tower of the Gods": "Can Access Other Location \"Tower of the Gods - Gohdan Heart Container\"",
      "Forsaken Fortress": "Can Access Other Location \"Forsaken Fortress - Helmaroc King Heart Container\"",
      "Earth Temple": "Can Access Other Location \"Earth Temple - Jalhalla Heart Container\"",
      "Wind Temple": "Can Access Other Location \"Wind Temple - Molgera Heart Container\"",
      "Hyrule": "Can Access Hyrule",
      "Ganon's Tower": "Can Reach and Defeat Ganondorf",
    }
    
    def __init__(self, rando):
      self.rando = rando
      self.logic = rando.logic
      self.options = rando.options
      
      self.path_logic = Logic(self.rando)
      self.path_logic_initial_state = self.path_logic.save_simulated_playthrough_state()
      
      # Define instance variable shortcuts for hint distribution options.
      self.max_path_hints = int(self.options.get("num_path_hints", 0))
      self.max_barren_hints = int(self.options.get("num_barren_hints", 0))
      self.max_location_hints = int(self.options.get("num_location_hints", 0))
      self.max_item_hints = int(self.options.get("num_item_hints", 0))
      self.total_num_hints = self.max_path_hints + self.max_barren_hints + self.max_location_hints + self.max_item_hints
      
      self.clearer_hints = self.options.get("clearer_hints")
      self.use_always_hints = self.options.get("use_always_hints")
      
      # Import dictionaries used to build hints from files.
      with open(os.path.join(DATA_PATH, "progress_item_hints.txt"), "r") as f:
        self.progress_item_hints = yaml.safe_load(f)
      with open(os.path.join(DATA_PATH, "island_name_hints.txt"), "r") as f:
        self.island_name_hints = yaml.safe_load(f)
      with open(os.path.join(DATA_PATH, "location_hints.txt"), "r") as f:
        self.location_hints = yaml.safe_load(f)
      
      # Validate location names in location hints file.
      for location_name in self.location_hints:
        assert location_name in rando.logic.item_locations
      
      # Define a dictionary mapping charts to their sunken treasure.
      # This will be used to check whether or not the chart leads to a junk item. If so, the chart itself can be
      # considered junk.
      self.chart_name_to_sunken_treasure = {}
    
    @staticmethod
    def get_hint_item_name(item_name):
      if item_name.startswith("Triforce Chart"):
        return "Triforce Chart"
      if item_name.startswith("Triforce Shard"):
        return "Triforce Shard"
      if item_name.startswith("Treasure Chart"):
        return "Treasure Chart"
      if item_name.endswith("Tingle Statue"):
        return "Tingle Statue"
      if item_name.endswith("Small Key"):
        return "Small Key"
      if item_name.endswith("Big Key"):
        return "Big Key"
      return item_name
    
    @staticmethod
    def get_formatted_hint_text(hint, prefix="They say that ", suffix=".", delay=30):
      if hint.type == HintType.PATH:
        hint_string = (
          "%san item found at \\{1A 06 FF 00 00 05}%s\\{1A 06 FF 00 00 00} is on the path to \\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00}%s"
          % (prefix, hint.place, hint.reward, suffix)
        )
      elif hint.type == HintType.BARREN:
        hint_string = (
          "%svisiting \\{1A 06 FF 00 00 03}%s\\{1A 06 FF 00 00 00} is a foolish choice%s"
          % (prefix, hint.place, suffix)
        )
      elif hint.type == HintType.LOCATION:
        hint_string = (
          "%s\\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00} rewards \\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00}%s"
          % (prefix, hint.place, hint.reward, suffix)
        )
      elif hint.type == HintType.ITEM:
        hint_string = (
          "%s\\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00} is located in \\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00}%s"
          % (prefix, hint.reward, hint.place, suffix)
        )
      else:
        hint_string = ""
      
      # Add a wait command (delay) to prevent the player from skipping over the hint accidentally.
      delay = max(0, min(0xFFFF, delay)) # Clamp within valid range.
      if delay > 0:
        hint_string += "\\{1A 07 00 00 07 %02X %02X}" % (delay >> 8, delay & 0xFF)
      
      return hint_string
    
    
    def get_entrance_zone(self, location_name):
      # Helper function to return the entrance zone name for the location.
      #
      # For non-dungeon and non-cave locations, the entrance zone name is simply the zone (island) name. However, when
      # entrances are randomized, the entrance zone name may differ from the zone name for dungeons and caves.
      # As a special case, if the entrance zone is Tower of the Gods or the location name is "Tower of the Gods - Sunken
      # Treasure", the entrance zone name is "Tower of the Gods Sector" to differentiate between the dungeon and the
      # entrance.
      
      zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
      
      if location_name in ITEM_LOCATION_NAME_TO_EXIT_ZONE_NAME_OVERRIDES:
        zone_name = ITEM_LOCATION_NAME_TO_EXIT_ZONE_NAME_OVERRIDES[location_name]
      
      if zone_name in self.rando.dungeon_and_cave_island_locations and self.logic.is_dungeon_or_cave(location_name):
        # If the location is in a dungeon or cave, use the hint for whatever island the dungeon/cave is located on.
        entrance_zone = self.rando.dungeon_and_cave_island_locations[zone_name]
        
        # Special case for Tower of the Gods to use Tower of the Gods Sector when refering to the entrance, not the dungeon
        if entrance_zone == "Tower of the Gods":
          entrance_zone = "Tower of the Gods Sector"
      else:
        # Otherwise, for non-dungeon and non-cave locations, just use the zone name.
        entrance_zone = zone_name
        
        # Special case for Tower of the Gods to use Tower of the Gods Sector when refering to the Sunken Treasure
        if location_name == "Tower of the Gods - Sunken Treasure":
          entrance_zone = "Tower of the Gods Sector"
        # Note that Forsaken Fortress - Sunken Treasure has a similar issue, but there are no randomized entrances on
        # Forsaken Fortress, so we won't make that distinction here.
      return entrance_zone
    
    def build_sunken_treasure_mapping(self):
      # Helper function to create a mapping of treasure charts to their respective sunken treasure.
      
      chart_name_to_island_number = {}
      for island_number in range(1, 49+1):
        chart_name = self.logic.macros["Chart for Island %d" % island_number][0]
        chart_name_to_island_number[chart_name] = island_number
      
      chart_name_to_sunken_treasure = {}
      for chart_number in range(1, 49+1):
        if chart_number <= 8:
          chart_name = "Triforce Chart %d" % chart_number
        else:
          chart_name = "Treasure Chart %d" % (chart_number-8)
        island_number = chart_name_to_island_number[chart_name]
        island_name = self.rando.island_number_to_name[island_number]
        chart_name_to_sunken_treasure[chart_name] = "%s - Sunken Treasure" % island_name
      
      return chart_name_to_sunken_treasure
    
    def check_location_required_for_paths(self, location_to_check, paths_to_check):
      # To check whether the location is required or not, we simulate a playthrough and remove the item the player would
      # receive at that location immediately after they receive it. If the player can still fulfill the requirement 
      # despite not having this item, the location is not required.
      
      # If the item is not a progress item, there's no way it's required.
      item_name = self.logic.done_item_locations[location_to_check]
      if item_name not in self.logic.all_progress_items:
        return False
      
      # Reuse a single Logic instance over multiple calls to this function for performance reasons.
      self.path_logic.load_simulated_playthrough_state(self.path_logic_initial_state)
      previously_accessible_locations = []
      
      while self.path_logic.unplaced_progress_items:
        progress_items_in_this_sphere = OrderedDict()
        
        accessible_locations = self.path_logic.get_accessible_remaining_locations()
        locations_in_this_sphere = [
          loc for loc in accessible_locations
          if loc not in previously_accessible_locations
        ]
        if not locations_in_this_sphere:
          break
        
        
        if not self.options.get("keylunacy"):
          # If the player gained access to any small keys, we need to give them the keys without counting that as a new sphere.
          newly_accessible_predetermined_item_locations = [
            loc for loc in locations_in_this_sphere
            if loc in self.logic.prerandomization_item_locations
          ]
          newly_accessible_small_key_locations = [
            loc for loc in newly_accessible_predetermined_item_locations
            if self.logic.prerandomization_item_locations[loc].endswith(" Small Key")
          ]
          if newly_accessible_small_key_locations:
            for small_key_location_name in newly_accessible_small_key_locations:
              item_name = self.logic.prerandomization_item_locations[small_key_location_name]
              assert item_name.endswith(" Small Key")
              
              self.path_logic.add_owned_item(item_name)
              # Remove small key from owned items if it was from the location we want to check
              if small_key_location_name == location_to_check:
                self.path_logic.currently_owned_items.remove(self.path_logic.clean_item_name(item_name))
            
            previously_accessible_locations += newly_accessible_small_key_locations
            continue # Redo this loop iteration with the small key locations no longer being considered 'remaining'.
        
        
        # Hide duplicated progression items (e.g. Empty Bottles) when they are placed in non-progression locations to avoid confusion and inconsistency.
        locations_in_this_sphere = self.path_logic.filter_locations_for_progression(locations_in_this_sphere)
        
        for location_name in locations_in_this_sphere:
          item_name = self.logic.done_item_locations[location_name]
          if item_name in self.path_logic.all_progress_items:
            progress_items_in_this_sphere[location_name] = item_name
        
        for location_name, item_name in progress_items_in_this_sphere.items():
          self.path_logic.add_owned_item(item_name)
          # Remove item from owned items if it was from the location we want to check.
          if location_name == location_to_check:
            self.path_logic.currently_owned_items.remove(self.path_logic.clean_item_name(item_name))
        for group_name, item_names in self.path_logic.progress_item_groups.items():
          entire_group_is_owned = all(item_name in self.path_logic.currently_owned_items for item_name in item_names)
          if entire_group_is_owned and group_name in self.path_logic.unplaced_progress_items:
            self.path_logic.unplaced_progress_items.remove(group_name)
        
        previously_accessible_locations = accessible_locations
      
      requirements_met = {
        path_name: not self.path_logic.check_requirement_met(self.DUNGEON_NAME_TO_REQUIREMENT_NAME[path_name])
        for path_name in paths_to_check
      }
      return requirements_met
    
    def get_required_locations_for_paths(self):
      # Add all race-mode dungeons as paths, in addition to Hyrule and Ganon's Tower.
      dungeon_paths = self.rando.race_mode_required_dungeons.copy()
      non_dungeon_paths = ["Hyrule", "Ganon's Tower"]
      path_goals = dungeon_paths + non_dungeon_paths
      required_locations_for_paths = {goal: [] for goal in path_goals}
      
      # Determine which locations are required to beat the seed.
      # Items are implicitly referred to by their location to handle duplicate item names (i.e., progressive items and
      # small keys). Basically, we remove the item from that location and see if the seed is still beatable. If not, then
      # we consider the item as required.
      progress_locations, non_progress_locations = self.logic.get_progress_and_non_progress_locations()
      for location_name in progress_locations:
        # Ignore race-mode-banned locations.
        if location_name in self.rando.race_mode_banned_locations:
          continue
        
        # Build a list of required locations, along with the item at that location.
        item_name = self.logic.done_item_locations[location_name]
        if (
          location_name not in self.rando.race_mode_required_locations          # Ignore boss Heart Containers in race mode, even if it's required.
          and (self.options.get("keylunacy") or not item_name.endswith(" Key")) # Keys are only considered in key-lunacy.
          and item_name in self.logic.all_progress_items                        # Required locations always contain progress items (by definition).
        ):
          # Determine the item name for the given location.
          zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
          entrance_zone = self.get_entrance_zone(location_name)
          item_tuple = (zone_name, entrance_zone, specific_location_name, item_name)
          
          # Check and record if the location is required for path goals.
          requirements_met = self.check_location_required_for_paths(location_name, path_goals)
          for goal_name, requirement_met in requirements_met.items():
            if requirement_met:
              required_locations_for_paths[goal_name].append(item_tuple)
          
          # Add items that are path to race mode dungeons to the Hyrule and Ganon's Tower paths
          for dungeon_path_name in dungeon_paths:
            for item_tuple in required_locations_for_paths[dungeon_path_name]:
              for non_dungeon_path_name in non_dungeon_paths:
                if item_tuple not in required_locations_for_paths[non_dungeon_path_name]:
                  required_locations_for_paths[non_dungeon_path_name].append(item_tuple)
      
      return required_locations_for_paths
    
    def get_path_hint(self, unhinted_locations, hinted_locations, path_name):
      valid_path_hint = False
      while not valid_path_hint:
        # If there are no hintable locations, return `None`.
        if len(unhinted_locations) == 0:
          return None, None
        
        # Pick a location uniformly at random from the list of hintable locations.
        zone_name, entrance_zone, specific_location_name, item_name = self.rando.rng.choice(unhinted_locations)
        hinted_location = "%s - %s" % (zone_name, specific_location_name)
        
        # Regardless of whether we use the location, remove that location from being hinted.
        unhinted_locations.remove((zone_name, entrance_zone, specific_location_name, item_name))
        
        # The location is a valid hint if it has not already been hinted at.
        if hinted_location not in hinted_locations:
          valid_path_hint = True
      
      # Record hinted zone, item, and path goal.
      # If it's a dungeon, use the dungeon name. If it's a cave, use the entrance zone name.
      if zone_name in self.logic.DUNGEON_NAMES.values():
        if zone_name == "Tower of the Gods" and specific_location_name == "Sunken Treasure":
          # Special case: if location is Tower of the Gods - Sunken Treasure, use "Tower of the Gods Sector" as the hint.
          return Hint(HintType.PATH, "Tower of the Gods Sector", self.DUNGEON_NAME_TO_BOSS_NAME[path_name]), hinted_location
        else:
          return Hint(HintType.PATH, zone_name, self.DUNGEON_NAME_TO_BOSS_NAME[path_name]), hinted_location
      else:
        return Hint(HintType.PATH, entrance_zone, self.DUNGEON_NAME_TO_BOSS_NAME[path_name]), hinted_location
    
    
    def determine_junk_items(self):
      # Helper method which returns a set of guaranteed unrequired items in the seed.
      
      junk_items = set(self.logic.all_nonprogress_items)  # Start with all non-progress items in the seed.
      junk_items |= set(CONSUMABLE_ITEMS)                 # Add consumables like Heart Containers and Rupees.
      junk_items |= set(DUNGEON_NONPROGRESS_ITEMS)        # Add dungeon items (Dungeon Maps and Compasses).
      if not self.options.get("keylunacy"):
        junk_items |= set(DUNGEON_PROGRESS_ITEMS)         # Consider Small and Big Keys junk when key-lunacy is off.
      
      # Consider Empty Bottles junk only if none are logical.
      if "Empty Bottle" in self.rando.logic.all_progress_items and "Empty Bottle" in junk_items:
        junk_items.remove("Empty Bottle")
      # Consider Progressive Quiver junk only if none are logical.
      if "Progressive Quiver" in self.rando.logic.all_progress_items and "Progressive Quiver" in junk_items:
        junk_items.remove("Progressive Quiver")
      # Consider Progressive Wallet junk only if none are logical.
      if "Progressive Wallet" in self.rando.logic.all_progress_items and "Progressive Wallet" in junk_items:
        junk_items.remove("Progressive Wallet")
      
      # Consider Small and Big Keys for non-required race mode dungeons as junk when key-lunacy is on.
      if self.options.get("race_mode") and self.options.get("keylunacy"):
        race_mode_banned_dungeons = set(self.logic.DUNGEON_NAMES.values()) - set(self.rando.race_mode_required_dungeons)
        if "Dragon Roost Cavern" in race_mode_banned_dungeons:
          junk_items.add("DRC Small Key")
          junk_items.add("DRC Big Key")
        if "Forbidden Woods" in race_mode_banned_dungeons:
          junk_items.add("FW Small Key")
          junk_items.add("FW Big Key")
        if "Tower of the Gods" in race_mode_banned_dungeons:
          junk_items.add("TotG Small Key")
          junk_items.add("TotG Big Key")
        if "Earth Temple" in race_mode_banned_dungeons:
          junk_items.add("ET Small Key")
          junk_items.add("ET Big Key")
        if "Wind Temple" in race_mode_banned_dungeons:
          junk_items.add("WT Small Key")
          junk_items.add("WT Big Key")
      
      # Special cases: Loop here until the list of junk items stops changing.
      junk_items_changed = True
      while junk_items_changed:
        junk_items_changed = False
        
        # Loop through charts when sunken treasure on and consider any charts that lead to immediately to junk as junk.
        if self.options.get("progression_triforce_charts") or self.options.get("progression_treasure_charts"):
          for chart_name, sunken_treasure in self.chart_name_to_sunken_treasure.items():
            if chart_name not in junk_items:
              item_name = self.logic.done_item_locations[sunken_treasure]
              if item_name in junk_items:
                junk_items.add(chart_name)
                junk_items_changed = True
        
        # Check Maggie's and Moblin's Letters and if they lead to junk, consider them junk as well.
        if self.options.get("progression_short_sidequests"):
          item_name = self.logic.done_item_locations["Windfall Island - Cafe Bar - Postman"]
          if "Maggie's Letter" not in junk_items and item_name in junk_items:
            junk_items.add("Maggie's Letter")
            junk_items_changed = True
          item_name = self.logic.done_item_locations["Windfall Island - Maggie - Delivery Reward"]
          if "Moblin's Letter" not in junk_items and item_name in junk_items:
            junk_items.add("Moblin's Letter")
            junk_items_changed = True
        
        # Check the two 12-eye octos and if both lead to junk, consider both quivers as junk.
        if self.options.get("progression_big_octos_gunboats"):
          octo1_item_name = self.logic.done_item_locations["Tingle Island - Big Octo"]
          octo2_item_name = self.logic.done_item_locations["Seven-Star Isles - Big Octo"]
          if "Progressive Quiver" not in junk_items and octo1_item_name in junk_items and octo2_item_name in junk_items:
            junk_items.add("Progressive Quiver")
            junk_items_changed = True
        
        if self.options.get("progression_misc"):
          # Check Tingle statues.
          item_name = self.logic.done_item_locations["Tingle Island - Ankle - Reward for All Tingle Statues"]
          if "Dragon Tingle Statue" not in junk_items and item_name in junk_items:
            junk_items.add("Dragon Tingle Statue")
            junk_items.add("Forbidden Tingle Statue")
            junk_items.add("Goddess Tingle Statue")
            junk_items.add("Earth Tingle Statue")
            junk_items.add("Wind Tingle Statue")
            junk_items_changed = True
          
          # Check Ghost Ship Chart.
          item_name = self.logic.done_item_locations["The Great Sea - Ghost Ship"]
          if "Ghost Ship Chart" not in junk_items and item_name in junk_items:
            junk_items.add("Ghost Ship Chart")
            junk_items_changed = True
          
      return junk_items
    
    def get_barren_zones(self, progress_locations):
      # Helper function to build a list of barren zones in this seed.
      # The list includes only zones which are allowed to be hinted at as barren.
      
      # To determine a list of candidate barren zones, we first construct a list of guaranteed junk items. The remaining
      # set of items may or may not be required, so the zones that contain them won't be hinted barren. We do this because
      # the player may have multiple paths to beat the seed. So if we only used non-path locations, we may hint at all
      # paths as barren (since one particular path is not strictly required).
      # Technically, this is an overestimate (a superset) of actual barren locations, but it should suffice.
      junk_items = self.determine_junk_items()
      
      # We don't want to have barren/always hints overlap if hints are on.
      # For instance, consider a Ganon's Tower always hint. If you get that hint and a barren hint for Ganon's Tower, it's
      # effectively the same hint. However, if there's a Blue Chu Jelly hint, a Windfall barren hint would still be
      # helpful since Green Chu Jelly is at least another check on Windfall.
      always_hint_locations = []
      if self.use_always_hints:
        always_hint_locations = list(filter(
          lambda location_name: location_name in self.location_hints
          and self.location_hints[location_name]["Type"] == "Always",
          progress_locations,
        ))
      
      # Initialize possibly-required zones to all logical zones in this seed.
      # `possibly_required_zones` contains a mapping of zones -> possibly-required items.
      # `possibly_required_zones_no_always` contains a mapping of zones with always locations ignored -> possibly-required items.
      possibly_required_zones = {}
      possibly_required_zones_no_always = {}
      for location_name in progress_locations:
        zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
        
        # Consider dungeons as a separate zone.
        key_name = ""
        if zone_name in self.logic.DUNGEON_NAMES.values():
          if location_name == "Tower of the Gods - Sunken Treasure":
            key_name = "Tower of the Gods Sector"
          else:
            key_name = zone_name
        else:
          entrance_zone = self.get_entrance_zone(location_name)
          key_name = entrance_zone
        
        possibly_required_zones[key_name] = set()
        if location_name not in always_hint_locations:
          possibly_required_zones_no_always[key_name] = set()
      
      # Loop through all progress locations, recording only possibly-required items in our dictionary.
      for location_name in progress_locations:
        item_name = self.logic.done_item_locations[location_name]
        if location_name not in self.rando.race_mode_required_locations and item_name not in junk_items:
          zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
          
          # Consider dungeons as a separate zone.
          if zone_name in self.logic.DUNGEON_NAMES.values():
            if location_name == "Tower of the Gods - Sunken Treasure":
              possibly_required_zones["Tower of the Gods Sector"].add(item_name)
            else:
              possibly_required_zones[zone_name].add(item_name)
          else:
            entrance_zone = self.get_entrance_zone(location_name)
            possibly_required_zones[entrance_zone].add(item_name)
          
          # Include dungeon-related mail with its dungeon, in addition to Mailbox.
          if location_name == "Mailbox - Letter from Baito":
            possibly_required_zones["Earth Temple"].add(item_name)
            entrance_zone = self.get_entrance_zone("Earth Temple - Jalhalla Heart Container")
            if entrance_zone in possibly_required_zones:
              possibly_required_zones[entrance_zone].add(item_name)
          if location_name == "Mailbox - Letter from Orca":
            possibly_required_zones["Forbidden Woods"].add(item_name)
            entrance_zone = self.get_entrance_zone("Forbidden Woods - Kalle Demos Heart Container")
            if entrance_zone in possibly_required_zones:
              possibly_required_zones[entrance_zone].add(item_name)
          if location_name == "Mailbox - Letter from Aryll" or location_name == "Mailbox - Letter from Tingle":
            possibly_required_zones["Forsaken Fortress"].add(item_name)
      
      # The zones with zero possibly-required items makes up our initial set of barren zones.
      # We also check whether there are any non-always hinted locations there. If not, then don't hint at that zone since
      # it'd be covered already by the always hint(s).
      barren_zones = list(filter(
        lambda x: x[0] in possibly_required_zones_no_always and len(x[1]) == 0,
        possibly_required_zones.items()
      ))
      barren_zones = set(zone_name for zone_name, empty_set in barren_zones)
      
      # Prevent the entrances of possibly-required dungeons from being hinted at as barren.
      possibly_required_dungeons = list(filter(
        lambda x: len(x[1]) != 0
        and x[0] in self.logic.DUNGEON_NAMES.values(),
        possibly_required_zones.items(),
      ))
      for dungeon_name, items_set in possibly_required_dungeons:
        if dungeon_name == "Dragon Roost Cavern":
          entrance_zone = self.get_entrance_zone("Dragon Roost Cavern - Gohma Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Forbidden Woods":
          entrance_zone = self.get_entrance_zone("Forbidden Woods - Kalle Demos Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Tower of the Gods":
          entrance_zone = self.get_entrance_zone("Tower of the Gods - Gohdan Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Earth Temple":
          entrance_zone = self.get_entrance_zone("Earth Temple - Jalhalla Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Wind Temple":
          entrance_zone = self.get_entrance_zone("Wind Temple - Molgera Heart Container")
          barren_zones.discard(entrance_zone)
      
      # Remove race-mode banned dungeons from being hinted at as barren.
      if self.options.get("race_mode"):
        race_mode_banned_dungeons = set(self.logic.DUNGEON_NAMES.values()) - set(self.rando.race_mode_required_dungeons)
        barren_zones = barren_zones - race_mode_banned_dungeons
      
      # Return the list of barren zones sorted to maintain consistent ordering.
      return list(sorted(barren_zones))
    
    def get_barren_hint(self, unhinted_zones, zone_weights):
      # If there are no hintable locations, return `None`.
      if len(unhinted_zones) == 0:
        return None
      
      # Remove a barren zone at random from the list, using the weights provided.
      zone_name = self.rando.rng.choices(unhinted_zones, weights=zone_weights)[0]
      unhinted_zones.remove(zone_name)
      
      return Hint(HintType.BARREN, zone_name)
    
    
    def filter_legal_item_hint(self, location_name, progress_locations, previously_hinted_locations):
      return (
        # Don't hint at non-progress items.
        self.logic.done_item_locations[location_name] in self.logic.all_progress_items and
        
        # Don't hint at item in non-progress locations.
        location_name in progress_locations and
        
        # Don't hint at dungeon maps and compasses, and don't hint at dungeon keys when key-lunacy is not enabled.
        (self.options.get("keylunacy") or not self.logic.is_dungeon_item(self.logic.done_item_locations[location_name])) and
        
        # You already know which boss locations have a required item and which don't in race mode by looking at the sea chart.
        location_name not in self.rando.race_mode_required_locations and
        
        # Remove locations that are included in always hints.
        not (location_name in self.location_hints and self.location_hints[location_name]["Type"] == "Always") and
        
        # Remove locations in race-mode banned dungeons.
        location_name not in self.rando.race_mode_banned_locations and
        
        # Remove locations for items that were previously hinted.
        location_name not in previously_hinted_locations
      )
    
    def get_legal_item_hints(self, progress_locations, hinted_barren_zones, previously_hinted_locations):
      # Helper function to build a list of locations which may be hinted as item hints in this seed.
      
      # Filter out locations which are invalid to be hinted at for item hints.
      hintable_locations = list(filter(lambda location_name: self.filter_legal_item_hint(
        location_name, progress_locations, previously_hinted_locations), self.logic.done_item_locations.keys()))
      
      # Remove locations in hinted barren areas.
      new_hintable_locations = []
      barrens = [hint.place for hint in hinted_barren_zones]
      for location_name in hintable_locations:
        # Catch Mailbox cases.
        if (
            (location_name == "Mailbox - Letter from Baito" and "Earth Temple" in barrens)
            or (location_name == "Mailbox - Letter from Orca" and "Forbidden Woods" in barrens)
            or (location_name == "Mailbox - Letter from Aryll" and "Forsaken Fortress" in barrens)
            or (location_name == "Mailbox - Letter from Tingle" and "Forsaken Fortress" in barrens)
        ):
          continue
        
        # Catch locations which are hinted at in barren dungeons.
        zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
        if zone_name in self.logic.DUNGEON_NAMES.values() and zone_name in barrens:
          continue
        
        # Catch locations which are hinted at in barren zones.
        entrance_zone = self.get_entrance_zone(location_name)
        if entrance_zone not in barrens:
          new_hintable_locations.append(location_name)
      
      return new_hintable_locations
    
    def get_item_hint(self, hintable_locations):
      # If there are no hintable locations, return `None`.
      if len(hintable_locations) == 0:
        return None
      
      # Pick a location at which to hint at random.
      location_name = self.rando.rng.choice(hintable_locations)
      hintable_locations.remove(location_name)
      
      item_name = self.logic.done_item_locations[location_name]
      entrance_zone = self.get_entrance_zone(location_name)
      
      # Simplify entrance zone name
      if entrance_zone == "Tower of the Gods Sector":
        entrance_zone = "Tower of the Gods"
      
      return Hint(HintType.ITEM, entrance_zone, item_name), location_name
    
    
    def get_legal_location_hints(self, progress_locations, hinted_barren_zones, previously_hinted_locations):
      # Helper function to build a list of locations which may be hinted as location hints in this seed.
      
      hintable_locations = list(filter(lambda loc: loc in self.location_hints.keys(), progress_locations))
      
      # Identify valid always hints for this seed.
      always_hintable_locations = list(filter(lambda loc: self.location_hints[loc]["Type"] == "Always", hintable_locations))
      # The remaining locations are potential sometimes hints.
      hintable_locations = list(filter(lambda loc: self.location_hints[loc]["Type"] == "Sometimes", hintable_locations))
      
      # If we're not using always hints, consider them as sometimes hints instead.
      if not self.use_always_hints:
        hintable_locations += always_hintable_locations
        always_hintable_locations = []
      
      # Remove locations in race-mode banned dungeons.
      hintable_locations = list(filter(lambda location_name: location_name not in self.rando.race_mode_banned_locations, hintable_locations))
      
      # Remove locations for items that were previously hinted.
      hintable_locations = list(filter(lambda loc: loc not in previously_hinted_locations, hintable_locations))
      
      # Remove locations in hinted barren areas.
      sometimes_hintable_locations = []
      barrens = [hint.place for hint in hinted_barren_zones]
      for location_name in hintable_locations:
        # Catch Mailbox cases.
        if (
            (location_name == "Mailbox - Letter from Baito" and "Earth Temple" in barrens)
            or (location_name == "Mailbox - Letter from Orca" and "Forbidden Woods" in barrens)
            or (location_name == "Mailbox - Letter from Aryll" and "Forsaken Fortress" in barrens)
            or (location_name == "Mailbox - Letter from Tingle" and "Forsaken Fortress" in barrens)
        ):
          continue
        
        # Catch locations which are hinted at in barren dungeons.
        zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
        if zone_name in self.logic.DUNGEON_NAMES.values() and zone_name in barrens:
          continue
        
        # Catch locations which are hinted at in barren zones.
        entrance_zone = self.get_entrance_zone(location_name)
        if entrance_zone not in barrens:
          sometimes_hintable_locations.append(location_name)
      
      return always_hintable_locations, sometimes_hintable_locations
    
    def get_location_hint(self, hintable_locations):
      # If there are no hintable locations, return `None`.
      if len(hintable_locations) == 0:
        return None
      
      # Pick a location at which to hint at random.
      location_name = self.rando.rng.choice(hintable_locations)
      hintable_locations.remove(location_name)
      
      # Apply cryptic text to the location name, unless the clearer hints option is selected.
      item_name = self.logic.done_item_locations[location_name]
      if self.clearer_hints:
        item_name = tweaks.add_article_before_item_name(item_name)
      else:
        location_name = self.location_hints[location_name]["Text"]
      
      return Hint(HintType.LOCATION, location_name, item_name)
    
    
    def generate_octo_fairy_hint(self):
      # Get an item hint for a random progress item.
      # Note that this hint is completely independant of all other hints.
      progress_locations, non_progress_locations = self.logic.get_progress_and_non_progress_locations()
      hintable_locations = self.get_legal_item_hints(progress_locations, [], [])
      if len(hintable_locations) == 0:
        raise Exception("No valid items to give hints for")
      
      item_hint, location_name = self.get_item_hint(hintable_locations)
      # We don't want this Great Fairy to hint at her own item.
      if location_name == "Two-Eye Reef - Big Octo Great Fairy":
        item_hint, location_name = self.get_item_hint(hintable_locations)
      
      # Always use cryptic text for the octo fairy hint
      item_hint.reward = self.progress_item_hints[Hints.get_hint_item_name(item_hint.reward)]
      item_hint.place = self.island_name_hints[item_hint.place]
      
      return item_hint
    
    def generate_savage_labyrinth_hints(self):
      # Get an item hint for the two checks in Savage Labyrinth.
      floor_30_item_name = self.logic.done_item_locations["Outset Island - Savage Labyrinth - Floor 30"]
      floor_50_item_name = self.logic.done_item_locations["Outset Island - Savage Labyrinth - Floor 50"]
      
      floor_30_is_progress = (floor_30_item_name in self.logic.all_progress_items)
      floor_50_is_progress = (floor_50_item_name in self.logic.all_progress_items)
      
      floor_30_item_name = Hints.get_hint_item_name(floor_30_item_name)
      floor_50_item_name = Hints.get_hint_item_name(floor_50_item_name)
      
      if floor_30_is_progress and not floor_30_item_name in self.progress_item_hints:
        raise Exception("Could not find progress item hint for item: %s" % floor_30_item_name)
      if floor_50_is_progress and not floor_50_item_name in self.progress_item_hints:
        raise Exception("Could not find progress item hint for item: %s" % floor_50_item_name)
      
      # Always use cryptic text for the Savage Labyrinth hints
      floor_30_hint = None
      if floor_30_is_progress:
        floor_30_hint = Hint(HintType.ITEM, None, self.progress_item_hints[floor_30_item_name])
      floor_50_hint = None
      if floor_50_is_progress:
        floor_50_hint = Hint(HintType.ITEM, None, self.progress_item_hints[floor_50_item_name])
      
      return floor_30_hint, floor_50_hint
    
    def generate_hints(self):
      # Create a mapping for chart name -> sunken treasure
      self.chart_name_to_sunken_treasure = self.build_sunken_treasure_mapping()
      
      # Build of list of progress locations for this seed.
      progress_locations, non_progress_locations = self.logic.get_progress_and_non_progress_locations()
      
      # Get all entrance zones for progress locations in this seed.
      all_world_areas = []
      for location_name in progress_locations:
        if self.logic.is_dungeon_location(location_name):
          zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
          all_world_areas.append(zone_name)
        else:
          all_world_areas.append(self.get_entrance_zone(location_name))
      
      # Get a counter for the number of locations associated with each zone, used for weighing.
      location_counter = Counter(all_world_areas)
      
      # Determine which locations are required for each path goal.
      # Items are implicitly referred to by their location to handle duplicate item names (i.e., progressive items and
      # small keys). Basically, we remove the item from that location and see if the path goal is still achievable. If
      # not, then we consider the item as required.
      required_locations_for_paths = {}
      if self.max_path_hints > 0:
        required_locations_for_paths = self.get_required_locations_for_paths()
      
      # Generate path hints.
      # We hint at max `self.max_path_hints` zones at random. We start by hinted each of the race mode dungeons once.
      # After that, we repeatedly select a path goal at random and use that to form another hint. Zones are weighted by
      # the number of required locations at that zone. The more required locations, the more likely that zone will be
      # chosen.
      dungeon_paths = self.rando.race_mode_required_dungeons.copy()
      self.rando.rng.shuffle(dungeon_paths)
      
      # If race mode is on, then remove items that are hinted on the path to a race mode dungeon from paths to Hyrule and
      # Ganondorf. This way, the path to the race mode dungeon takes hint priority for that item.
      if self.max_path_hints > 0:
        for dungeon_name in dungeon_paths:
          for item_tuple in required_locations_for_paths[dungeon_name]:
            if item_tuple in required_locations_for_paths["Hyrule"]:
              required_locations_for_paths["Hyrule"].remove(item_tuple)
            if item_tuple in required_locations_for_paths["Ganon's Tower"]:
              required_locations_for_paths["Ganon's Tower"].remove(item_tuple)
      
      # Likewise, remove items that are hinted on the path to Hyrule from the path to Ganondorf. This way, the path to
      # Hyrule takes hint priority over the path to Ganondorf for that item.
      if self.max_path_hints > 0:
        for item_tuple in required_locations_for_paths["Hyrule"]:
          if item_tuple in required_locations_for_paths["Ganon's Tower"]:
            required_locations_for_paths["Ganon's Tower"].remove(item_tuple)
      
      hinted_path_zones = []
      previously_hinted_locations = []
      
      # Generate a path hint for each race-mode dungeon.
      for dungeon_name in dungeon_paths:
        # If there are no hintable locations for path hints, skip to barren hints.
        if len(required_locations_for_paths) == 0:
          break
        
        if len(hinted_path_zones) < self.max_path_hints:
          path_hint, location_name = self.get_path_hint(required_locations_for_paths[dungeon_name], previously_hinted_locations, dungeon_name)
          
          # Unable to generate a path hint for the dungeon, so remove path goal and move on to the next.
          if path_hint is None:
            del required_locations_for_paths[dungeon_name]
            continue
          
          # Remove locations that are hinted in always hints from being hinted path.
          if not self.use_always_hints or (location_name not in self.location_hints or self.location_hints[location_name]["Type"] != "Always"):
            hinted_path_zones.append(path_hint)
            previously_hinted_locations.append(location_name)
      
      while len(required_locations_for_paths) > 0 and len(hinted_path_zones) < self.max_path_hints:
        path_name = self.rando.rng.choice(list(required_locations_for_paths.keys()))
        path_hint, location_name = self.get_path_hint(required_locations_for_paths[path_name], previously_hinted_locations, path_name)
        
        # Unable to generate a path hint for the dungeon, so remove path goal.
        if path_hint is None:
          del required_locations_for_paths[path_name]
        else:
          # Remove locations that are hinted in always hints from being hinted path.
          if not self.use_always_hints or (location_name not in self.location_hints or self.location_hints[location_name]["Type"] != "Always"):
            hinted_path_zones.append(path_hint)
            previously_hinted_locations.append(location_name)
      
      # Generate barren hints.
      # We select at most `self.max_barren_hints` zones at random to hint as barren. Barren zones are weighted by the
      # square root of the number of locations at that zone.
      unhinted_barren_zones = self.get_barren_zones(progress_locations)
      hinted_barren_zones = []
      while len(unhinted_barren_zones) > 0 and len(hinted_barren_zones) < self.max_barren_hints:
        # Weight each barren zone by the square root of the number of locations there.
        zone_weights = [sqrt(location_counter[zone]) for zone in unhinted_barren_zones]
        
        barren_hint = self.get_barren_hint(unhinted_barren_zones, zone_weights)
        if barren_hint is not None:
          hinted_barren_zones.append(barren_hint)
      
      # Generate item hints.
      # We select at most `self.max_item_hints` items at random to hint at. We do not want to hint at items already
      # covered by the path hints, nor do we want to hint at items in barren-hinted locations.
      hintable_locations = self.get_legal_item_hints(progress_locations, hinted_barren_zones, previously_hinted_locations)
      
      hinted_item_locations = []
      while len(hintable_locations) > 0 and len(hinted_item_locations) < self.max_item_hints:
        item_hint, location_name = self.get_item_hint(hintable_locations)
        
        # Apply cryptic text, unless the clearer hints option is selected.
        if self.clearer_hints:
          item_hint.reward = tweaks.add_article_before_item_name(item_hint.reward)
        else:
          item_hint.reward = self.progress_item_hints[Hints.get_hint_item_name(item_hint.reward)]
          item_hint.place = self.island_name_hints[item_hint.place]
        
        hinted_item_locations.append(item_hint)
        previously_hinted_locations.append(location_name)
      
      # Generate location hints.
      # We try to generate location hints until we get to `self.total_num_hints` total hints, but if there are not enough
      # valid hintable locations, then we have no choice but to return less than the desired amount of hints.
      always_hintable_locations, sometimes_hintable_locations = self.get_legal_location_hints(progress_locations, hinted_barren_zones, previously_hinted_locations)
      hinted_locations = []
      remaining_hints_desired = self.total_num_hints - len(hinted_path_zones) - len(hinted_barren_zones) - len(hinted_item_locations)
      
      # Start by exhausting the list of always hints.
      while len(always_hintable_locations) > 0 and remaining_hints_desired > 0:
        remaining_hints_desired -= 1
        location_hint = self.get_location_hint(always_hintable_locations)
        hinted_locations.append(location_hint)
      
      # Fill out the remaining hint slots with sometimes hints.
      while len(sometimes_hintable_locations) > 0 and remaining_hints_desired > 0:
        remaining_hints_desired -= 1
        location_hint = self.get_location_hint(sometimes_hintable_locations)
        hinted_locations.append(location_hint)
      
      return hinted_path_zones + hinted_barren_zones + hinted_item_locations + hinted_locations
  
files: hints.py
files: import os
  from collections import Counter, OrderedDict
  from enum import Enum
  from math import sqrt
  
  import yaml
  
  from logic.item_types import CONSUMABLE_ITEMS, DUNGEON_NONPROGRESS_ITEMS, DUNGEON_PROGRESS_ITEMS
  from logic.logic import Logic
  from wwrando_paths import DATA_PATH
  import tweaks
  
  ITEM_LOCATION_NAME_TO_EXIT_ZONE_NAME_OVERRIDES = {
    "Pawprint Isle - Wizzrobe Cave": "Pawprint Isle Side Isle",
  }
  
  
  class HintType(Enum):
    PATH = 0
    BARREN = 1
    ITEM = 2
    LOCATION = 3
  
  
  class Hint:
    def __init__(self, type: HintType, place, reward=None):
      self.type = type
      self.place = place
      self.reward = reward
    
    def __str__(self):
      return "<HINT: %s, (%s, %s)>" % (str(self.type), self.place, self.reward)
  
  
  class Hints:
    # A dictionary mapping dungeon name to the dungeon boss.
    # The boss name is used as the path goal in the hint text.
    DUNGEON_NAME_TO_BOSS_NAME = {
      "Dragon Roost Cavern": "Gohma",
      "Forbidden Woods": "Kalle Demos",
      "Tower of the Gods": "Gohdan",
      "Forsaken Fortress": "Helmaroc King",
      "Earth Temple": "Jalhalla",
      "Wind Temple": "Molgera",
      "Hyrule": "Hyrule",
      "Ganon's Tower": "Ganondorf",
    }
    
    # A dictionary mapping dungeon name to the requirement name.
    # This dictionary is used when determining which items are on the path to a goal.
    DUNGEON_NAME_TO_REQUIREMENT_NAME = {
      "Dragon Roost Cavern": "Can Access Other Location \"Dragon Roost Cavern - Gohma Heart Container\"",
      "Forbidden Woods": "Can Access Other Location \"Forbidden Woods - Kalle Demos Heart Container\"",
      "Tower of the Gods": "Can Access Other Location \"Tower of the Gods - Gohdan Heart Container\"",
      "Forsaken Fortress": "Can Access Other Location \"Forsaken Fortress - Helmaroc King Heart Container\"",
      "Earth Temple": "Can Access Other Location \"Earth Temple - Jalhalla Heart Container\"",
      "Wind Temple": "Can Access Other Location \"Wind Temple - Molgera Heart Container\"",
      "Hyrule": "Can Access Hyrule",
      "Ganon's Tower": "Can Reach and Defeat Ganondorf",
    }
    
    def __init__(self, rando):
      self.rando = rando
      self.logic = rando.logic
      self.options = rando.options
      
      # Define instance variable shortcuts for hint distribution options.
      self.max_path_hints = int(self.options.get("num_path_hints", 0))
      self.max_barren_hints = int(self.options.get("num_barren_hints", 0))
      self.max_location_hints = int(self.options.get("num_location_hints", 0))
      self.max_item_hints = int(self.options.get("num_item_hints", 0))
      self.total_num_hints = self.max_path_hints + self.max_barren_hints + self.max_location_hints + self.max_item_hints
      
      self.clearer_hints = self.options.get("clearer_hints")
      self.use_always_hints = self.options.get("use_always_hints")
      
      # Import dictionaries used to build hints from files.
      with open(os.path.join(DATA_PATH, "progress_item_hints.txt"), "r") as f:
        self.progress_item_hints = yaml.safe_load(f)
      with open(os.path.join(DATA_PATH, "island_name_hints.txt"), "r") as f:
        self.island_name_hints = yaml.safe_load(f)
      with open(os.path.join(DATA_PATH, "location_hints.txt"), "r") as f:
        self.location_hints = yaml.safe_load(f)
      
      # Validate location names in location hints file.
      for location_name in self.location_hints:
        assert location_name in rando.logic.item_locations
      
      # Define a dictionary mapping charts to their sunken treasure.
      # This will be used to check whether or not the chart leads to a junk item. If so, the chart itself can be
      # considered junk.
      self.chart_name_to_sunken_treasure = {}
    
    @staticmethod
    def get_hint_item_name(item_name):
      if item_name.startswith("Triforce Chart"):
        return "Triforce Chart"
      if item_name.startswith("Triforce Shard"):
        return "Triforce Shard"
      if item_name.startswith("Treasure Chart"):
        return "Treasure Chart"
      if item_name.endswith("Tingle Statue"):
        return "Tingle Statue"
      if item_name.endswith("Small Key"):
        return "Small Key"
      if item_name.endswith("Big Key"):
        return "Big Key"
      return item_name
    
    @staticmethod
    def get_formatted_hint_text(hint, prefix="They say that ", suffix=".", delay=30):
      if hint.type == HintType.PATH:
        hint_string = (
          "%san item found at \\{1A 06 FF 00 00 05}%s\\{1A 06 FF 00 00 00} is on the path to \\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00}%s"
          % (prefix, hint.place, hint.reward, suffix)
        )
      elif hint.type == HintType.BARREN:
        hint_string = (
          "%svisiting \\{1A 06 FF 00 00 03}%s\\{1A 06 FF 00 00 00} is a foolish choice%s"
          % (prefix, hint.place, suffix)
        )
      elif hint.type == HintType.LOCATION:
        hint_string = (
          "%s\\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00} rewards \\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00}%s"
          % (prefix, hint.place, hint.reward, suffix)
        )
      elif hint.type == HintType.ITEM:
        hint_string = (
          "%s\\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00} is located in \\{1A 06 FF 00 00 01}%s\\{1A 06 FF 00 00 00}%s"
          % (prefix, hint.reward, hint.place, suffix)
        )
      else:
        hint_string = ""
      
      # Add a wait command (delay) to prevent the player from skipping over the hint accidentally.
      delay = max(0, min(0xFFFF, delay)) # Clamp within valid range.
      if delay > 0:
        hint_string += "\\{1A 07 00 00 07 %02X %02X}" % (delay >> 8, delay & 0xFF)
      
      return hint_string
    
    
    def get_entrance_zone(self, location_name):
      # Helper function to return the entrance zone name for the location.
      #
      # For non-dungeon and non-cave locations, the entrance zone name is simply the zone (island) name. However, when
      # entrances are randomized, the entrance zone name may differ from the zone name for dungeons and caves.
      # As a special case, if the entrance zone is Tower of the Gods or the location name is "Tower of the Gods - Sunken
      # Treasure", the entrance zone name is "Tower of the Gods Sector" to differentiate between the dungeon and the
      # entrance.
      
      zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
      
      if location_name in ITEM_LOCATION_NAME_TO_EXIT_ZONE_NAME_OVERRIDES:
        zone_name = ITEM_LOCATION_NAME_TO_EXIT_ZONE_NAME_OVERRIDES[location_name]
      
      if zone_name in self.rando.dungeon_and_cave_island_locations and self.logic.is_dungeon_or_cave(location_name):
        # If the location is in a dungeon or cave, use the hint for whatever island the dungeon/cave is located on.
        entrance_zone = self.rando.dungeon_and_cave_island_locations[zone_name]
        
        # Special case for Tower of the Gods to use Tower of the Gods Sector when refering to the entrance, not the dungeon
        if entrance_zone == "Tower of the Gods":
          entrance_zone = "Tower of the Gods Sector"
      else:
        # Otherwise, for non-dungeon and non-cave locations, just use the zone name.
        entrance_zone = zone_name
        
        # Special case for Tower of the Gods to use Tower of the Gods Sector when refering to the Sunken Treasure
        if location_name == "Tower of the Gods - Sunken Treasure":
          entrance_zone = "Tower of the Gods Sector"
        # Note that Forsaken Fortress - Sunken Treasure has a similar issue, but there are no randomized entrances on
        # Forsaken Fortress, so we won't make that distinction here.
      return entrance_zone
    
    def build_sunken_treasure_mapping(self):
      # Helper function to create a mapping of treasure charts to their respective sunken treasure.
      
      chart_name_to_island_number = {}
      for island_number in range(1, 49+1):
        chart_name = self.logic.macros["Chart for Island %d" % island_number][0]
        chart_name_to_island_number[chart_name] = island_number
      
      chart_name_to_sunken_treasure = {}
      for chart_number in range(1, 49+1):
        if chart_number <= 8:
          chart_name = "Triforce Chart %d" % chart_number
        else:
          chart_name = "Treasure Chart %d" % (chart_number-8)
        island_number = chart_name_to_island_number[chart_name]
        island_name = self.rando.island_number_to_name[island_number]
        chart_name_to_sunken_treasure[chart_name] = "%s - Sunken Treasure" % island_name
      
      return chart_name_to_sunken_treasure
    
    def check_location_required_for_paths(self, location_to_check, paths_to_check):
      # If the item is not a progress item, there's no way it's required.
      item_name = self.logic.done_item_locations[location_to_check]
      if item_name not in self.logic.all_progress_items:
        return False
      
      # Effectively, to check whether the location is required or not, we simulate a playthrough and remove the item the
      # player would receive at that location immediately after they receive it. If the player can still fulfill the
      # requirement despite not having this item, the location is not required.
      logic = Logic(self.rando)
      previously_accessible_locations = []
      
      while logic.unplaced_progress_items:
        progress_items_in_this_sphere = OrderedDict()
        
        accessible_locations = logic.get_accessible_remaining_locations()
        locations_in_this_sphere = [
          loc for loc in accessible_locations
          if loc not in previously_accessible_locations
        ]
        if not locations_in_this_sphere:
          return {path_name: not logic.check_requirement_met(self.DUNGEON_NAME_TO_REQUIREMENT_NAME[path_name]) for path_name in paths_to_check}
        
        
        if not self.options.get("keylunacy"):
          # If the player gained access to any small keys, we need to give them the keys without counting that as a new sphere.
          newly_accessible_predetermined_item_locations = [
            loc for loc in locations_in_this_sphere
            if loc in self.logic.prerandomization_item_locations
          ]
          newly_accessible_small_key_locations = [
            loc for loc in newly_accessible_predetermined_item_locations
            if self.logic.prerandomization_item_locations[loc].endswith(" Small Key")
          ]
          if newly_accessible_small_key_locations:
            for small_key_location_name in newly_accessible_small_key_locations:
              item_name = self.logic.prerandomization_item_locations[small_key_location_name]
              assert item_name.endswith(" Small Key")
              
              logic.add_owned_item(item_name)
              # Remove small key from owned items if it was from the location we want to check
              if small_key_location_name == location_to_check:
                logic.currently_owned_items.remove(logic.clean_item_name(item_name))
            
            previously_accessible_locations += newly_accessible_small_key_locations
            continue # Redo this loop iteration with the small key locations no longer being considered 'remaining'.
        
        
        # Hide duplicated progression items (e.g. Empty Bottles) when they are placed in non-progression locations to avoid confusion and inconsistency.
        locations_in_this_sphere = logic.filter_locations_for_progression(locations_in_this_sphere)
        
        for location_name in locations_in_this_sphere:
          item_name = self.logic.done_item_locations[location_name]
          if item_name in logic.all_progress_items:
            progress_items_in_this_sphere[location_name] = item_name
        
        for location_name, item_name in progress_items_in_this_sphere.items():
          logic.add_owned_item(item_name)
          # Remove item from owned items if it was from the location we want to check.
          if location_name == location_to_check:
            logic.currently_owned_items.remove(logic.clean_item_name(item_name))
        for group_name, item_names in logic.progress_item_groups.items():
          entire_group_is_owned = all(item_name in logic.currently_owned_items for item_name in item_names)
          if entire_group_is_owned and group_name in logic.unplaced_progress_items:
            logic.unplaced_progress_items.remove(group_name)
        
        previously_accessible_locations = accessible_locations
      
      return {path_name: not logic.check_requirement_met(self.DUNGEON_NAME_TO_REQUIREMENT_NAME[path_name]) for path_name in paths_to_check}
    
    def get_required_locations_for_paths(self):
      # Add all race-mode dungeons as paths, in addition to Hyrule and Ganon's Tower.
      dungeon_paths = self.rando.race_mode_required_dungeons.copy()
      non_dungeon_paths = ["Hyrule", "Ganon's Tower"]
      path_goals = dungeon_paths + non_dungeon_paths
      required_locations_for_paths = {goal: [] for goal in path_goals}
      
      # Determine which locations are required to beat the seed.
      # Items are implicitly referred to by their location to handle duplicate item names (i.e., progressive items and
      # small keys). Basically, we remove the item from that location and see if the seed is still beatable. If not, then
      # we consider the item as required.
      progress_locations, non_progress_locations = self.logic.get_progress_and_non_progress_locations()
      for location_name in progress_locations:
        # Ignore race-mode-banned locations.
        if location_name in self.rando.race_mode_banned_locations:
          continue
        
        # Build a list of required locations, along with the item at that location.
        item_name = self.logic.done_item_locations[location_name]
        if (
          location_name not in self.rando.race_mode_required_locations          # Ignore boss Heart Containers in race mode, even if it's required.
          and (self.options.get("keylunacy") or not item_name.endswith(" Key")) # Keys are only considered in key-lunacy.
          and item_name in self.logic.all_progress_items                        # Required locations always contain progress items (by definition).
        ):
          # Determine the item name for the given location.
          zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
          entrance_zone = self.get_entrance_zone(location_name)
          item_tuple = (zone_name, entrance_zone, specific_location_name, item_name)
          
          # Check and record if the location is required for path goals.
          requirements_met = self.check_location_required_for_paths(location_name, path_goals)
          for goal_name, requirement_met in requirements_met.items():
            if requirement_met:
              required_locations_for_paths[goal_name].append(item_tuple)
          
          # Add items that are path to race mode dungeons to the Hyrule and Ganon's Tower paths
          for dungeon_path_name in dungeon_paths:
            for item_tuple in required_locations_for_paths[dungeon_path_name]:
              for non_dungeon_path_name in non_dungeon_paths:
                if item_tuple not in required_locations_for_paths[non_dungeon_path_name]:
                  required_locations_for_paths[non_dungeon_path_name].append(item_tuple)
      
      return required_locations_for_paths
    
    def get_path_hint(self, unhinted_locations, hinted_locations, path_name):
      valid_path_hint = False
      while not valid_path_hint:
        # If there are no hintable locations, return `None`.
        if len(unhinted_locations) == 0:
          return None, None
        
        # Pick a location uniformly at random from the list of hintable locations.
        zone_name, entrance_zone, specific_location_name, item_name = self.rando.rng.choice(unhinted_locations)
        hinted_location = "%s - %s" % (zone_name, specific_location_name)
        
        # Regardless of whether we use the location, remove that location from being hinted.
        unhinted_locations.remove((zone_name, entrance_zone, specific_location_name, item_name))
        
        # The location is a valid hint if it has not already been hinted at.
        if hinted_location not in hinted_locations:
          valid_path_hint = True
      
      # Record hinted zone, item, and path goal.
      # If it's a dungeon, use the dungeon name. If it's a cave, use the entrance zone name.
      if zone_name in self.logic.DUNGEON_NAMES.values():
        if zone_name == "Tower of the Gods" and specific_location_name == "Sunken Treasure":
          # Special case: if location is Tower of the Gods - Sunken Treasure, use "Tower of the Gods Sector" as the hint.
          return Hint(HintType.PATH, "Tower of the Gods Sector", self.DUNGEON_NAME_TO_BOSS_NAME[path_name]), hinted_location
        else:
          return Hint(HintType.PATH, zone_name, self.DUNGEON_NAME_TO_BOSS_NAME[path_name]), hinted_location
      else:
        return Hint(HintType.PATH, entrance_zone, self.DUNGEON_NAME_TO_BOSS_NAME[path_name]), hinted_location
    
    
    def determine_junk_items(self):
      # Helper method which returns a set of guaranteed unrequired items in the seed.
      
      junk_items = set(self.logic.all_nonprogress_items)  # Start with all non-progress items in the seed.
      junk_items |= set(CONSUMABLE_ITEMS)                 # Add consumables like Heart Containers and Rupees.
      junk_items |= set(DUNGEON_NONPROGRESS_ITEMS)        # Add dungeon items (Dungeon Maps and Compasses).
      if not self.options.get("keylunacy"):
        junk_items |= set(DUNGEON_PROGRESS_ITEMS)         # Consider Small and Big Keys junk when key-lunacy is off.
      
      # Consider Empty Bottles junk only if none are logical.
      if "Empty Bottle" in self.rando.logic.all_progress_items and "Empty Bottle" in junk_items:
        junk_items.remove("Empty Bottle")
      # Consider Progressive Quiver junk only if none are logical.
      if "Progressive Quiver" in self.rando.logic.all_progress_items and "Progressive Quiver" in junk_items:
        junk_items.remove("Progressive Quiver")
      # Consider Progressive Wallet junk only if none are logical.
      if "Progressive Wallet" in self.rando.logic.all_progress_items and "Progressive Wallet" in junk_items:
        junk_items.remove("Progressive Wallet")
      
      # Consider Small and Big Keys for non-required race mode dungeons as junk when key-lunacy is on.
      if self.options.get("race_mode") and self.options.get("keylunacy"):
        race_mode_banned_dungeons = set(self.logic.DUNGEON_NAMES.values()) - set(self.rando.race_mode_required_dungeons)
        if "Dragon Roost Cavern" in race_mode_banned_dungeons:
          junk_items.add("DRC Small Key")
          junk_items.add("DRC Big Key")
        if "Forbidden Woods" in race_mode_banned_dungeons:
          junk_items.add("FW Small Key")
          junk_items.add("FW Big Key")
        if "Tower of the Gods" in race_mode_banned_dungeons:
          junk_items.add("TotG Small Key")
          junk_items.add("TotG Big Key")
        if "Earth Temple" in race_mode_banned_dungeons:
          junk_items.add("ET Small Key")
          junk_items.add("ET Big Key")
        if "Wind Temple" in race_mode_banned_dungeons:
          junk_items.add("WT Small Key")
          junk_items.add("WT Big Key")
      
      # Special cases: Loop here until the list of junk items stops changing.
      junk_items_changed = True
      while junk_items_changed:
        junk_items_changed = False
        
        # Loop through charts when sunken treasure on and consider any charts that lead to immediately to junk as junk.
        if self.options.get("progression_triforce_charts") or self.options.get("progression_treasure_charts"):
          for chart_name, sunken_treasure in self.chart_name_to_sunken_treasure.items():
            if chart_name not in junk_items:
              item_name = self.logic.done_item_locations[sunken_treasure]
              if item_name in junk_items:
                junk_items.add(chart_name)
                junk_items_changed = True
        
        # Check Maggie's and Moblin's Letters and if they lead to junk, consider them junk as well.
        if self.options.get("progression_short_sidequests"):
          item_name = self.logic.done_item_locations["Windfall Island - Cafe Bar - Postman"]
          if "Maggie's Letter" not in junk_items and item_name in junk_items:
            junk_items.add("Maggie's Letter")
            junk_items_changed = True
          item_name = self.logic.done_item_locations["Windfall Island - Maggie - Delivery Reward"]
          if "Moblin's Letter" not in junk_items and item_name in junk_items:
            junk_items.add("Moblin's Letter")
            junk_items_changed = True
        
        # Check the two 12-eye octos and if both lead to junk, consider both quivers as junk.
        if self.options.get("progression_big_octos_gunboats"):
          octo1_item_name = self.logic.done_item_locations["Tingle Island - Big Octo"]
          octo2_item_name = self.logic.done_item_locations["Seven-Star Isles - Big Octo"]
          if "Progressive Quiver" not in junk_items and octo1_item_name in junk_items and octo2_item_name in junk_items:
            junk_items.add("Progressive Quiver")
            junk_items_changed = True
        
        if self.options.get("progression_misc"):
          # Check Tingle statues.
          item_name = self.logic.done_item_locations["Tingle Island - Ankle - Reward for All Tingle Statues"]
          if "Dragon Tingle Statue" not in junk_items and item_name in junk_items:
            junk_items.add("Dragon Tingle Statue")
            junk_items.add("Forbidden Tingle Statue")
            junk_items.add("Goddess Tingle Statue")
            junk_items.add("Earth Tingle Statue")
            junk_items.add("Wind Tingle Statue")
            junk_items_changed = True
          
          # Check Ghost Ship Chart.
          item_name = self.logic.done_item_locations["The Great Sea - Ghost Ship"]
          if "Ghost Ship Chart" not in junk_items and item_name in junk_items:
            junk_items.add("Ghost Ship Chart")
            junk_items_changed = True
          
      return junk_items
    
    def get_barren_zones(self, progress_locations):
      # Helper function to build a list of barren zones in this seed.
      # The list includes only zones which are allowed to be hinted at as barren.
      
      # To determine a list of candidate barren zones, we first construct a list of guaranteed junk items. The remaining
      # set of items may or may not be required, so the zones that contain them won't be hinted barren. We do this because
      # the player may have multiple paths to beat the seed. So if we only used non-path locations, we may hint at all
      # paths as barren (since one particular path is not strictly required).
      # Technically, this is an overestimate (a superset) of actual barren locations, but it should suffice.
      junk_items = self.determine_junk_items()
      
      # We don't want to have barren/always hints overlap if hints are on.
      # For instance, consider a Ganon's Tower always hint. If you get that hint and a barren hint for Ganon's Tower, it's
      # effectively the same hint. However, if there's a Blue Chu Jelly hint, a Windfall barren hint would still be
      # helpful since Green Chu Jelly is at least another check on Windfall.
      always_hint_locations = []
      if self.use_always_hints:
        always_hint_locations = list(filter(
          lambda location_name: location_name in self.location_hints
          and self.location_hints[location_name]["Type"] == "Always",
          progress_locations,
        ))
      
      # Initialize possibly-required zones to all logical zones in this seed.
      # `possibly_required_zones` contains a mapping of zones -> possibly-required items.
      # `possibly_required_zones_no_always` contains a mapping of zones with always locations ignored -> possibly-required items.
      possibly_required_zones = {}
      possibly_required_zones_no_always = {}
      for location_name in progress_locations:
        zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
        
        # Consider dungeons as a separate zone.
        key_name = ""
        if zone_name in self.logic.DUNGEON_NAMES.values():
          if location_name == "Tower of the Gods - Sunken Treasure":
            key_name = "Tower of the Gods Sector"
          else:
            key_name = zone_name
        else:
          entrance_zone = self.get_entrance_zone(location_name)
          key_name = entrance_zone
        
        possibly_required_zones[key_name] = set()
        if location_name not in always_hint_locations:
          possibly_required_zones_no_always[key_name] = set()
      
      # Loop through all progress locations, recording only possibly-required items in our dictionary.
      for location_name in progress_locations:
        item_name = self.logic.done_item_locations[location_name]
        if location_name not in self.rando.race_mode_required_locations and item_name not in junk_items:
          zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
          
          # Consider dungeons as a separate zone.
          if zone_name in self.logic.DUNGEON_NAMES.values():
            if location_name == "Tower of the Gods - Sunken Treasure":
              possibly_required_zones["Tower of the Gods Sector"].add(item_name)
            else:
              possibly_required_zones[zone_name].add(item_name)
          else:
            entrance_zone = self.get_entrance_zone(location_name)
            possibly_required_zones[entrance_zone].add(item_name)
          
          # Include dungeon-related mail with its dungeon, in addition to Mailbox.
          if location_name == "Mailbox - Letter from Baito":
            possibly_required_zones["Earth Temple"].add(item_name)
            entrance_zone = self.get_entrance_zone("Earth Temple - Jalhalla Heart Container")
            if entrance_zone in possibly_required_zones:
              possibly_required_zones[entrance_zone].add(item_name)
          if location_name == "Mailbox - Letter from Orca":
            possibly_required_zones["Forbidden Woods"].add(item_name)
            entrance_zone = self.get_entrance_zone("Forbidden Woods - Kalle Demos Heart Container")
            if entrance_zone in possibly_required_zones:
              possibly_required_zones[entrance_zone].add(item_name)
          if location_name == "Mailbox - Letter from Aryll" or location_name == "Mailbox - Letter from Tingle":
            possibly_required_zones["Forsaken Fortress"].add(item_name)
      
      # The zones with zero possibly-required items makes up our initial set of barren zones.
      # We also check whether there are any non-always hinted locations there. If not, then don't hint at that zone since
      # it'd be covered already by the always hint(s).
      barren_zones = list(filter(
        lambda x: x[0] in possibly_required_zones_no_always and len(x[1]) == 0,
        possibly_required_zones.items()
      ))
      barren_zones = set(zone_name for zone_name, empty_set in barren_zones)
      
      # Prevent the entrances of possibly-required dungeons from being hinted at as barren.
      possibly_required_dungeons = list(filter(
        lambda x: len(x[1]) != 0
        and x[0] in self.logic.DUNGEON_NAMES.values(),
        possibly_required_zones.items(),
      ))
      for dungeon_name, items_set in possibly_required_dungeons:
        if dungeon_name == "Dragon Roost Cavern":
          entrance_zone = self.get_entrance_zone("Dragon Roost Cavern - Gohma Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Forbidden Woods":
          entrance_zone = self.get_entrance_zone("Forbidden Woods - Kalle Demos Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Tower of the Gods":
          entrance_zone = self.get_entrance_zone("Tower of the Gods - Gohdan Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Earth Temple":
          entrance_zone = self.get_entrance_zone("Earth Temple - Jalhalla Heart Container")
          barren_zones.discard(entrance_zone)
        if dungeon_name == "Wind Temple":
          entrance_zone = self.get_entrance_zone("Wind Temple - Molgera Heart Container")
          barren_zones.discard(entrance_zone)
      
      # Remove race-mode banned dungeons from being hinted at as barren.
      if self.options.get("race_mode"):
        race_mode_banned_dungeons = set(self.logic.DUNGEON_NAMES.values()) - set(self.rando.race_mode_required_dungeons)
        barren_zones = barren_zones - race_mode_banned_dungeons
      
      # Return the list of barren zones sorted to maintain consistent ordering.
      return list(sorted(barren_zones))
    
    def get_barren_hint(self, unhinted_zones, zone_weights):
      # If there are no hintable locations, return `None`.
      if len(unhinted_zones) == 0:
        return None
      
      # Remove a barren zone at random from the list, using the weights provided.
      zone_name = self.rando.rng.choices(unhinted_zones, weights=zone_weights)[0]
      unhinted_zones.remove(zone_name)
      
      return Hint(HintType.BARREN, zone_name)
    
    
    def filter_legal_item_hint(self, location_name, progress_locations, previously_hinted_locations):
      return (
        # Don't hint at non-progress items.
        self.logic.done_item_locations[location_name] in self.logic.all_progress_items and
        
        # Don't hint at item in non-progress locations.
        location_name in progress_locations and
        
        # Don't hint at dungeon maps and compasses, and don't hint at dungeon keys when key-lunacy is not enabled.
        (self.options.get("keylunacy") or not self.logic.is_dungeon_item(self.logic.done_item_locations[location_name])) and
        
        # You already know which boss locations have a required item and which don't in race mode by looking at the sea chart.
        location_name not in self.rando.race_mode_required_locations and
        
        # Remove locations that are included in always hints.
        not (location_name in self.location_hints and self.location_hints[location_name]["Type"] == "Always") and
        
        # Remove locations in race-mode banned dungeons.
        location_name not in self.rando.race_mode_banned_locations and
        
        # Remove locations for items that were previously hinted.
        location_name not in previously_hinted_locations
      )
    
    def get_legal_item_hints(self, progress_locations, hinted_barren_zones, previously_hinted_locations):
      # Helper function to build a list of locations which may be hinted as item hints in this seed.
      
      # Filter out locations which are invalid to be hinted at for item hints.
      hintable_locations = list(filter(lambda location_name: self.filter_legal_item_hint(
        location_name, progress_locations, previously_hinted_locations), self.logic.done_item_locations.keys()))
      
      # Remove locations in hinted barren areas.
      new_hintable_locations = []
      barrens = [hint.place for hint in hinted_barren_zones]
      for location_name in hintable_locations:
        # Catch Mailbox cases.
        if (
            (location_name == "Mailbox - Letter from Baito" and "Earth Temple" in barrens)
            or (location_name == "Mailbox - Letter from Orca" and "Forbidden Woods" in barrens)
            or (location_name == "Mailbox - Letter from Aryll" and "Forsaken Fortress" in barrens)
            or (location_name == "Mailbox - Letter from Tingle" and "Forsaken Fortress" in barrens)
        ):
          continue
        
        # Catch locations which are hinted at in barren dungeons.
        zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
        if zone_name in self.logic.DUNGEON_NAMES.values() and zone_name in barrens:
          continue
        
        # Catch locations which are hinted at in barren zones.
        entrance_zone = self.get_entrance_zone(location_name)
        if entrance_zone not in barrens:
          new_hintable_locations.append(location_name)
      
      return new_hintable_locations
    
    def get_item_hint(self, hintable_locations):
      # If there are no hintable locations, return `None`.
      if len(hintable_locations) == 0:
        return None
      
      # Pick a location at which to hint at random.
      location_name = self.rando.rng.choice(hintable_locations)
      hintable_locations.remove(location_name)
      
      item_name = self.logic.done_item_locations[location_name]
      entrance_zone = self.get_entrance_zone(location_name)
      
      # Simplify entrance zone name
      if entrance_zone == "Tower of the Gods Sector":
        entrance_zone = "Tower of the Gods"
      
      return Hint(HintType.ITEM, entrance_zone, item_name), location_name
    
    
    def get_legal_location_hints(self, progress_locations, hinted_barren_zones, previously_hinted_locations):
      # Helper function to build a list of locations which may be hinted as location hints in this seed.
      
      hintable_locations = list(filter(lambda loc: loc in self.location_hints.keys(), progress_locations))
      
      # Identify valid always hints for this seed.
      always_hintable_locations = list(filter(lambda loc: self.location_hints[loc]["Type"] == "Always", hintable_locations))
      # The remaining locations are potential sometimes hints.
      hintable_locations = list(filter(lambda loc: self.location_hints[loc]["Type"] == "Sometimes", hintable_locations))
      
      # If we're not using always hints, consider them as sometimes hints instead.
      if not self.use_always_hints:
        hintable_locations += always_hintable_locations
        always_hintable_locations = []
      
      # Remove locations in race-mode banned dungeons.
      hintable_locations = list(filter(lambda location_name: location_name not in self.rando.race_mode_banned_locations, hintable_locations))
      
      # Remove locations for items that were previously hinted.
      hintable_locations = list(filter(lambda loc: loc not in previously_hinted_locations, hintable_locations))
      
      # Remove locations in hinted barren areas.
      sometimes_hintable_locations = []
      barrens = [hint.place for hint in hinted_barren_zones]
      for location_name in hintable_locations:
        # Catch Mailbox cases.
        if (
            (location_name == "Mailbox - Letter from Baito" and "Earth Temple" in barrens)
            or (location_name == "Mailbox - Letter from Orca" and "Forbidden Woods" in barrens)
            or (location_name == "Mailbox - Letter from Aryll" and "Forsaken Fortress" in barrens)
            or (location_name == "Mailbox - Letter from Tingle" and "Forsaken Fortress" in barrens)
        ):
          continue
        
        # Catch locations which are hinted at in barren dungeons.
        zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
        if zone_name in self.logic.DUNGEON_NAMES.values() and zone_name in barrens:
          continue
        
        # Catch locations which are hinted at in barren zones.
        entrance_zone = self.get_entrance_zone(location_name)
        if entrance_zone not in barrens:
          sometimes_hintable_locations.append(location_name)
      
      return always_hintable_locations, sometimes_hintable_locations
    
    def get_location_hint(self, hintable_locations):
      # If there are no hintable locations, return `None`.
      if len(hintable_locations) == 0:
        return None
      
      # Pick a location at which to hint at random.
      location_name = self.rando.rng.choice(hintable_locations)
      hintable_locations.remove(location_name)
      
      # Apply cryptic text to the location name, unless the clearer hints option is selected.
      item_name = self.logic.done_item_locations[location_name]
      if self.clearer_hints:
        item_name = tweaks.add_article_before_item_name(item_name)
      else:
        location_name = self.location_hints[location_name]["Text"]
      
      return Hint(HintType.LOCATION, location_name, item_name)
    
    
    def generate_octo_fairy_hint(self):
      # Get an item hint for a random progress item.
      # Note that this hint is completely independant of all other hints.
      progress_locations, non_progress_locations = self.logic.get_progress_and_non_progress_locations()
      hintable_locations = self.get_legal_item_hints(progress_locations, [], [])
      if len(hintable_locations) == 0:
        raise Exception("No valid items to give hints for")
      
      item_hint, location_name = self.get_item_hint(hintable_locations)
      # We don't want this Great Fairy to hint at her own item.
      if location_name == "Two-Eye Reef - Big Octo Great Fairy":
        item_hint, location_name = self.get_item_hint(hintable_locations)
      
      # Always use cryptic text for the octo fairy hint
      item_hint.reward = self.progress_item_hints[Hints.get_hint_item_name(item_hint.reward)]
      item_hint.place = self.island_name_hints[item_hint.place]
      
      return item_hint
    
    def generate_savage_labyrinth_hints(self):
      # Get an item hint for the two checks in Savage Labyrinth.
      floor_30_item_name = self.logic.done_item_locations["Outset Island - Savage Labyrinth - Floor 30"]
      floor_50_item_name = self.logic.done_item_locations["Outset Island - Savage Labyrinth - Floor 50"]
      
      floor_30_is_progress = (floor_30_item_name in self.logic.all_progress_items)
      floor_50_is_progress = (floor_50_item_name in self.logic.all_progress_items)
      
      floor_30_item_name = Hints.get_hint_item_name(floor_30_item_name)
      floor_50_item_name = Hints.get_hint_item_name(floor_50_item_name)
      
      if floor_30_is_progress and not floor_30_item_name in self.progress_item_hints:
        raise Exception("Could not find progress item hint for item: %s" % floor_30_item_name)
      if floor_50_is_progress and not floor_50_item_name in self.progress_item_hints:
        raise Exception("Could not find progress item hint for item: %s" % floor_50_item_name)
      
      # Always use cryptic text for the Savage Labyrinth hints
      floor_30_hint = None
      if floor_30_is_progress:
        floor_30_hint = Hint(HintType.ITEM, None, self.progress_item_hints[floor_30_item_name])
      floor_50_hint = None
      if floor_50_is_progress:
        floor_50_hint = Hint(HintType.ITEM, None, self.progress_item_hints[floor_50_item_name])
      
      return floor_30_hint, floor_50_hint
    
    def generate_hints(self):
      # Create a mapping for chart name -> sunken treasure
      self.chart_name_to_sunken_treasure = self.build_sunken_treasure_mapping()
      
      # Build of list of progress locations for this seed.
      progress_locations, non_progress_locations = self.logic.get_progress_and_non_progress_locations()
      
      # Get all entrance zones for progress locations in this seed.
      all_world_areas = []
      for location_name in progress_locations:
        if self.logic.is_dungeon_location(location_name):
          zone_name, specific_location_name = self.logic.split_location_name_by_zone(location_name)
          all_world_areas.append(zone_name)
        else:
          all_world_areas.append(self.get_entrance_zone(location_name))
      
      # Get a counter for the number of locations associated with each zone, used for weighing.
      location_counter = Counter(all_world_areas)
      
      # Determine which locations are required for each path goal.
      # Items are implicitly referred to by their location to handle duplicate item names (i.e., progressive items and
      # small keys). Basically, we remove the item from that location and see if the path goal is still achievable. If
      # not, then we consider the item as required.
      required_locations_for_paths = {}
      if self.max_path_hints > 0:
        required_locations_for_paths = self.get_required_locations_for_paths()
      
      # Generate path hints.
      # We hint at max `self.max_path_hints` zones at random. We start by hinted each of the race mode dungeons once.
      # After that, we repeatedly select a path goal at random and use that to form another hint. Zones are weighted by
      # the number of required locations at that zone. The more required locations, the more likely that zone will be
      # chosen.
      dungeon_paths = self.rando.race_mode_required_dungeons.copy()
      self.rando.rng.shuffle(dungeon_paths)
      
      # If race mode is on, then remove items that are hinted on the path to a race mode dungeon from paths to Hyrule and
      # Ganondorf. This way, the path to the race mode dungeon takes hint priority for that item.
      if self.max_path_hints > 0:
        for dungeon_name in dungeon_paths:
          for item_tuple in required_locations_for_paths[dungeon_name]:
            if item_tuple in required_locations_for_paths["Hyrule"]:
              required_locations_for_paths["Hyrule"].remove(item_tuple)
            if item_tuple in required_locations_for_paths["Ganon's Tower"]:
              required_locations_for_paths["Ganon's Tower"].remove(item_tuple)
      
      # Likewise, remove items that are hinted on the path to Hyrule from the path to Ganondorf. This way, the path to
      # Hyrule takes hint priority over the path to Ganondorf for that item.
      if self.max_path_hints > 0:
        for item_tuple in required_locations_for_paths["Hyrule"]:
          if item_tuple in required_locations_for_paths["Ganon's Tower"]:
            required_locations_for_paths["Ganon's Tower"].remove(item_tuple)
      
      hinted_path_zones = []
      previously_hinted_locations = []
      
      # Generate a path hint for each race-mode dungeon.
      for dungeon_name in dungeon_paths:
        # If there are no hintable locations for path hints, skip to barren hints.
        if len(required_locations_for_paths) == 0:
          break
        
        if len(hinted_path_zones) < self.max_path_hints:
          path_hint, location_name = self.get_path_hint(required_locations_for_paths[dungeon_name], previously_hinted_locations, dungeon_name)
          
          # Unable to generate a path hint for the dungeon, so remove path goal and move on to the next.
          if path_hint is None:
            del required_locations_for_paths[dungeon_name]
            continue
          
          # Remove locations that are hinted in always hints from being hinted path.
          if not self.use_always_hints or (location_name not in self.location_hints or self.location_hints[location_name]["Type"] != "Always"):
            hinted_path_zones.append(path_hint)
            previously_hinted_locations.append(location_name)
      
      while len(required_locations_for_paths) > 0 and len(hinted_path_zones) < self.max_path_hints:
        path_name = self.rando.rng.choice(list(required_locations_for_paths.keys()))
        path_hint, location_name = self.get_path_hint(required_locations_for_paths[path_name], previously_hinted_locations, path_name)
        
        # Unable to generate a path hint for the dungeon, so remove path goal.
        if path_hint is None:
          del required_locations_for_paths[path_name]
        else:
          # Remove locations that are hinted in always hints from being hinted path.
          if not self.use_always_hints or (location_name not in self.location_hints or self.location_hints[location_name]["Type"] != "Always"):
            hinted_path_zones.append(path_hint)
            previously_hinted_locations.append(location_name)
      
      # Generate barren hints.
      # We select at most `self.max_barren_hints` zones at random to hint as barren. Barren zones are weighted by the
      # square root of the number of locations at that zone.
      unhinted_barren_zones = self.get_barren_zones(progress_locations)
      hinted_barren_zones = []
      while len(unhinted_barren_zones) > 0 and len(hinted_barren_zones) < self.max_barren_hints:
        # Weight each barren zone by the square root of the number of locations there.
        zone_weights = [sqrt(location_counter[zone]) for zone in unhinted_barren_zones]
        
        barren_hint = self.get_barren_hint(unhinted_barren_zones, zone_weights)
        if barren_hint is not None:
          hinted_barren_zones.append(barren_hint)
      
      # Generate item hints.
      # We select at most `self.max_item_hints` items at random to hint at. We do not want to hint at items already
      # covered by the path hints, nor do we want to hint at items in barren-hinted locations.
      hintable_locations = self.get_legal_item_hints(progress_locations, hinted_barren_zones, previously_hinted_locations)
      
      hinted_item_locations = []
      while len(hintable_locations) > 0 and len(hinted_item_locations) < self.max_item_hints:
        item_hint, location_name = self.get_item_hint(hintable_locations)
        
        # Apply cryptic text, unless the clearer hints option is selected.
        if self.clearer_hints:
          item_hint.reward = tweaks.add_article_before_item_name(item_hint.reward)
        else:
          item_hint.reward = self.progress_item_hints[Hints.get_hint_item_name(item_hint.reward)]
          item_hint.place = self.island_name_hints[item_hint.place]
        
        hinted_item_locations.append(item_hint)
        previously_hinted_locations.append(location_name)
      
      # Generate location hints.
      # We try to generate location hints until we get to `self.total_num_hints` total hints, but if there are not enough
      # valid hintable locations, then we have no choice but to return less than the desired amount of hints.
      always_hintable_locations, sometimes_hintable_locations = self.get_legal_location_hints(progress_locations, hinted_barren_zones, previously_hinted_locations)
      hinted_locations = []
      remaining_hints_desired = self.total_num_hints - len(hinted_path_zones) - len(hinted_barren_zones) - len(hinted_item_locations)
      
      # Start by exhausting the list of always hints.
      while len(always_hintable_locations) > 0 and remaining_hints_desired > 0:
        remaining_hints_desired -= 1
        location_hint = self.get_location_hint(always_hintable_locations)
        hinted_locations.append(location_hint)
      
      # Fill out the remaining hint slots with sometimes hints.
      while len(sometimes_hintable_locations) > 0 and remaining_hints_desired > 0:
        remaining_hints_desired -= 1
        location_hint = self.get_location_hint(sometimes_hintable_locations)
        hinted_locations.append(location_hint)
      
      return hinted_path_zones + hinted_barren_zones + hinted_item_locations + hinted_locations
  
files: hints.py
files: 
  import yaml
  import re
  from collections import OrderedDict
  import copy
  
  import os
  
  from logic.item_types import PROGRESS_ITEMS, NONPROGRESS_ITEMS, CONSUMABLE_ITEMS, DUPLICATABLE_CONSUMABLE_ITEMS, DUNGEON_PROGRESS_ITEMS, DUNGEON_NONPROGRESS_ITEMS
  from wwrando_paths import LOGIC_PATH
  from randomizers import entrances
  
  class Logic:
    DUNGEON_NAMES = OrderedDict([
      ("DRC",  "Dragon Roost Cavern"),
      ("FW",   "Forbidden Woods"),
      ("TotG", "Tower of the Gods"),
      ("FF",   "Forsaken Fortress"),
      ("ET",   "Earth Temple"),
      ("WT",   "Wind Temple"),
    ])
    DUNGEON_NAME_TO_SHORT_DUNGEON_NAME = OrderedDict([v, k] for k, v in DUNGEON_NAMES.items())
    
    PROGRESS_ITEM_GROUPS = OrderedDict([
      ("Triforce Shards",  [
        "Triforce Shard 1",
        "Triforce Shard 2",
        "Triforce Shard 3",
        "Triforce Shard 4",
        "Triforce Shard 5",
        "Triforce Shard 6",
        "Triforce Shard 7",
        "Triforce Shard 8",
      ]),
      ("Goddess Pearls",  [
        "Nayru's Pearl",
        "Din's Pearl",
        "Farore's Pearl",
      ]),
      ("Tingle Statues",  [
        "Dragon Tingle Statue",
        "Forbidden Tingle Statue",
        "Goddess Tingle Statue",
        "Earth Tingle Statue",
        "Wind Tingle Statue",
      ]),
    ])
    
    initial_item_locations = None
    initial_macros = None
    
    def __init__(self, rando):
      self.rando = rando
      self.requirement_met_cache = {}
      
      
      # Initialize location related attributes.
      self.item_locations = Logic.load_and_parse_item_locations()
      self.load_and_parse_macros()
      
      self.locations_by_zone_name = OrderedDict()
      for location_name in self.item_locations:
        zone_name, specific_location_name = self.split_location_name_by_zone(location_name)
        if zone_name not in self.locations_by_zone_name:
          self.locations_by_zone_name[zone_name] = []
        self.locations_by_zone_name[zone_name].append(location_name)
      
      self.remaining_item_locations = list(self.item_locations.keys())
      self.prerandomization_item_locations = OrderedDict()
      
      self.done_item_locations = OrderedDict()
      for location_name in self.item_locations:
        self.done_item_locations[location_name] = None
      
      self.rock_spire_shop_ship_locations = []
      for location_name, location in self.item_locations.items():
        if location_name.startswith("Rock Spire Isle - Beedle's Special Shop Ship - "):
          self.rock_spire_shop_ship_locations.append(location_name)
      
      # Sync the logic macros with the randomizer.
      self.update_entrance_connection_macros()
      self.update_chart_macros()
      
      
      # Initialize item related attributes.
      self.all_progress_items = PROGRESS_ITEMS.copy()
      self.all_nonprogress_items = NONPROGRESS_ITEMS.copy()
      self.all_fixed_consumable_items = CONSUMABLE_ITEMS.copy()
      self.duplicatable_consumable_items = DUPLICATABLE_CONSUMABLE_ITEMS.copy()
      
      self.triforce_chart_names = []
      self.treasure_chart_names = []
      for i in range(1, 8+1):
        self.triforce_chart_names.append("Triforce Chart %d" % i)
      for i in range(1, 41+1):
        self.treasure_chart_names.append("Treasure Chart %d" % i)
      
      if self.rando.options.get("sword_mode") == "Swordless":
        self.all_progress_items = [
          item_name for item_name in self.all_progress_items
          if item_name != "Progressive Sword"
        ]
        self.all_nonprogress_items = [
          item_name for item_name in self.all_nonprogress_items
          if item_name != "Hurricane Spin"
        ]
      
      if self.rando.options.get("progression_triforce_charts"):
        self.all_progress_items += self.triforce_chart_names
      else:
        self.all_nonprogress_items += self.triforce_chart_names
      if self.rando.options.get("progression_treasure_charts"):
        self.all_progress_items += self.treasure_chart_names
      else:
        self.all_nonprogress_items += self.treasure_chart_names
      
      # Add dungeon items to the progress/nonprogress items lists.
      if self.rando.options.get("progression_dungeons"):
        self.all_progress_items += DUNGEON_PROGRESS_ITEMS
      else:
        self.all_nonprogress_items += DUNGEON_PROGRESS_ITEMS
      self.all_nonprogress_items += DUNGEON_NONPROGRESS_ITEMS
      
      # Tell the randomizer to register dungeon-specific item names as the normal items.
      for dungeon_item_name in (DUNGEON_PROGRESS_ITEMS + DUNGEON_NONPROGRESS_ITEMS):
        regular_item_name = dungeon_item_name.split(" ", 1)[1]
        self.rando.item_name_to_id[dungeon_item_name] = self.rando.item_name_to_id[regular_item_name]
      
      self.all_cleaned_item_names = []
      all_item_names = []
      all_item_names += self.all_progress_items
      all_item_names += self.all_nonprogress_items
      all_item_names += self.all_fixed_consumable_items
      all_item_names += self.duplicatable_consumable_items
      for item_name in all_item_names:
        cleaned_item_name = self.clean_item_name(item_name)
        if cleaned_item_name not in self.all_cleaned_item_names:
          self.all_cleaned_item_names.append(cleaned_item_name)
      
      self.unplaced_progress_items = self.all_progress_items.copy()
      self.unplaced_nonprogress_items = self.all_nonprogress_items.copy()
      self.unplaced_fixed_consumable_items = self.all_fixed_consumable_items.copy()
      
      self.progress_item_groups = copy.deepcopy(self.PROGRESS_ITEM_GROUPS)
      
      self.currently_owned_items = []
      
      for item_name in self.rando.starting_items:
        self.add_owned_item(item_name)
      
      # Decide what will count as a progress item on these settings.
      self.requirement_met_cache.clear()
      self.make_useless_progress_items_nonprogress()
      
      # Replace progress items that are part of a group with the group name instead.
      for group_name, item_names in self.progress_item_groups.items():
        if all(item_name in self.unplaced_progress_items for item_name in item_names):
          self.unplaced_progress_items.append(group_name)
          for item_name in item_names:
            self.unplaced_progress_items.remove(item_name)
      
      # Remove starting items from item groups.
      for group_name, group_item_names in self.progress_item_groups.items():
        items_to_remove_from_group = [
          item_name for item_name in group_item_names
          if item_name in self.rando.starting_items
        ]
        for item_name in items_to_remove_from_group:
          self.progress_item_groups[group_name].remove(item_name)
        if len(self.progress_item_groups[group_name]) == 0:
          if group_name in self.unplaced_progress_items:
            self.unplaced_progress_items.remove(group_name)
      
      self.requirement_met_cache.clear()
      self.cached_enemies_tested_for_reqs_tuple = OrderedDict()
    
    def save_simulated_playthrough_state(self):
      vars_backup = {}
      for attr_name in [
        "currently_owned_items",
        "unplaced_progress_items",
        "unplaced_nonprogress_items",
        "unplaced_fixed_consumable_items",
        "requirement_met_cache",
      ]:
        vars_backup[attr_name] = getattr(self, attr_name).copy()
      return vars_backup
    
    def load_simulated_playthrough_state(self, vars_backup):
      for attr_name, value in vars_backup.items():
        setattr(self, attr_name, value.copy())
    
    def is_dungeon_or_cave(self, location_name):
      # Look up the setting that the location name is under
      is_dungeon = "Dungeon" in self.item_locations[location_name]["Types"]
      is_puzzle_cave = "Puzzle Secret Cave" in self.item_locations[location_name]["Types"]
      is_combat_cave = "Combat Secret Cave" in self.item_locations[location_name]["Types"]
      is_savage = "Savage Labyrinth" in self.item_locations[location_name]["Types"]
      
      return (is_dungeon or is_puzzle_cave or is_combat_cave or is_savage)
    
    def set_location_to_item(self, location_name, item_name):
      #print("Setting %s to %s" % (location_name, item_name))
      
      if self.done_item_locations[location_name]:
        raise Exception("Location was used twice: " + location_name)
      
      self.done_item_locations[location_name] = item_name
      self.remaining_item_locations.remove(location_name)
      
      self.add_owned_item(item_name)
    
    def set_multiple_locations_to_group(self, available_locations, group_name):
      items_in_group = self.progress_item_groups[group_name]
      
      #print("Placing group: %s (size: %d)" % (group_name, len(items_in_group)))
      
      if len(available_locations) < len(items_in_group):
        raise Exception("Not enough locations to place all items in group %s" % group_name)
      
      for item_name in items_in_group:
        available_locations = self.filter_locations_valid_for_item(available_locations, item_name)
        location_name = available_locations.pop()
        self.set_location_to_item(location_name, item_name)
      
      self.unplaced_progress_items.remove(group_name)
    
    def set_prerandomization_item_location(self, location_name, item_name):
      # Temporarily keep track of where certain items are placed before the main progression item randomization loop starts.
      
      #print("Setting prerand %s to %s" % (location_name, item_name))
      
      assert location_name in self.item_locations
      self.prerandomization_item_locations[location_name] = item_name
    
    def get_num_progression_items(self):
      num_progress_items = 0
      for item_name in self.unplaced_progress_items:
        if item_name in self.progress_item_groups:
          group_name = item_name
          for item_name in self.progress_item_groups[group_name]:
            num_progress_items += 1
        else:
          num_progress_items += 1
      
      return num_progress_items
    
    def get_num_progression_locations(self):
      return Logic.get_num_progression_locations_static(self.item_locations, self.rando.options)
    
    @staticmethod
    def get_num_progression_locations_static(item_locations, options):
      progress_locations = Logic.filter_locations_for_progression_static(
        item_locations.keys(),
        item_locations,
        options,
        filter_sunken_treasure=True
      )
      num_progress_locations = len(progress_locations)
      if options.get("progression_triforce_charts"):
        num_progress_locations += 8
      if options.get("progression_treasure_charts"):
        num_progress_locations += 41
      
      return num_progress_locations
  
    def get_max_race_mode_banned_locations(self):
      if not self.rando.options.get("race_mode"):
        return 0
      
      all_locations = self.item_locations.keys()
      progress_locations = self.filter_locations_for_progression(all_locations)
      location_counts_by_dungeon = OrderedDict()
      
      for location_name in progress_locations:
        zone_name, _ = self.split_location_name_by_zone(location_name)
        
        dungeon_name = None
        if self.is_dungeon_location(location_name):
          dungeon_name = zone_name
        elif location_name == "Mailbox - Letter from Orca":
          dungeon_name = "Forbidden Woods"
        elif location_name == "Mailbox - Letter from Baito":
          dungeon_name = "Earth Temple"
        elif location_name == "Mailbox - Letter from Aryll":
          dungeon_name = "Forsaken Fortress"
        elif location_name == "Mailbox - Letter from Tingle":
          dungeon_name = "Forsaken Fortress"
        
        if dungeon_name is None:
          continue
        
        if dungeon_name in location_counts_by_dungeon:
          location_counts_by_dungeon[dungeon_name] += 1
        else:
          location_counts_by_dungeon[dungeon_name] = 1
      
      dungeon_location_counts = list(location_counts_by_dungeon.values())
      dungeon_location_counts.sort(reverse=True)
      num_banned_dungeons = 6 - int(self.rando.options.get("num_race_mode_dungeons"))
      max_banned_locations = sum(dungeon_location_counts[:num_banned_dungeons])
      
      return max_banned_locations
    
    def get_progress_and_non_progress_locations(self):
      all_locations = self.item_locations.keys()
      progress_locations = self.filter_locations_for_progression(all_locations, filter_sunken_treasure=True)
      nonprogress_locations = []
      for location_name in all_locations:
        if location_name in progress_locations:
          continue
        
        types = self.item_locations[location_name]["Types"]
        if "Sunken Treasure" in types:
          chart_name = self.chart_name_for_location(location_name)
          if "Triforce Chart" in chart_name:
            if self.rando.options.get("progression_triforce_charts"):
              progress_locations.append(location_name)
            else:
              nonprogress_locations.append(location_name)
          else:
            if self.rando.options.get("progression_treasure_charts"):
              progress_locations.append(location_name)
            else:
              nonprogress_locations.append(location_name)
        else:
          nonprogress_locations.append(location_name)
      
      return (progress_locations, nonprogress_locations)
    
    def add_owned_item(self, item_name):
      cleaned_item_name = self.clean_item_name(item_name)
      if cleaned_item_name not in self.all_cleaned_item_names:
        raise Exception("Unknown item name: " + item_name)
      
      self.currently_owned_items.append(cleaned_item_name)
      
      if item_name in self.unplaced_progress_items:
        self.unplaced_progress_items.remove(item_name)
      elif item_name in self.unplaced_nonprogress_items:
        self.unplaced_nonprogress_items.remove(item_name)
      elif item_name in self.unplaced_fixed_consumable_items:
        self.unplaced_fixed_consumable_items.remove(item_name)
      
      self.requirement_met_cache.clear()
    
    def remove_owned_item(self, item_name):
      cleaned_item_name = self.clean_item_name(item_name)
      if cleaned_item_name not in self.all_cleaned_item_names:
        raise Exception("Unknown item name: " + item_name)
      
      self.currently_owned_items.remove(cleaned_item_name)
      
      if self.all_progress_items.count(item_name) > self.unplaced_progress_items.count(item_name):
        self.unplaced_progress_items.append(item_name)
      elif item_name in self.all_nonprogress_items:
        self.unplaced_nonprogress_items.append(item_name)
      else:
        # Removing consumable items doesn't work because we don't know if the item is from the fixed list or the duplicatable list
        raise Exception("Cannot remove item from simulated inventory: %s" % item_name)
      
      self.requirement_met_cache.clear()
    
    def add_owned_item_or_item_group(self, item_name):
      if item_name in self.progress_item_groups:
        group_name = item_name
        for item_name in self.progress_item_groups[group_name]:
          self.currently_owned_items.append(item_name)
        self.requirement_met_cache.clear()
      else:
        self.add_owned_item(item_name)
    
    def remove_owned_item_or_item_group(self, item_name):
      if item_name in self.progress_item_groups:
        group_name = item_name
        for item_name in self.progress_item_groups[group_name]:
          self.currently_owned_items.remove(item_name)
        self.requirement_met_cache.clear()
      else:
        self.remove_owned_item(item_name)
    
    def get_accessible_remaining_locations(self, for_progression=False):
      accessible_location_names = []
      
      locations_to_check = self.remaining_item_locations
      if for_progression:
        locations_to_check = self.filter_locations_for_progression(locations_to_check)
      
      for location_name in locations_to_check:
        requirement_expression = self.item_locations[location_name]["Need"]
        if self.check_logical_expression_req(requirement_expression):
          accessible_location_names.append(location_name)
      
      return accessible_location_names
    
    def get_first_useful_item(self, items_to_check):
      # Searches through a given list of items and returns the first one that opens up at least 1 new location.
      # The randomizer shuffles the list before passing it to this function, so in effect it picks a random useful item.
      
      accessible_undone_locations = self.get_accessible_remaining_locations(for_progression=True)
      inaccessible_undone_item_locations = []
      locations_to_check = self.remaining_item_locations
      locations_to_check = self.filter_locations_for_progression(locations_to_check)
      for location_name in locations_to_check:
        if location_name not in accessible_undone_locations:
          inaccessible_undone_item_locations.append(location_name)
      
      # Cache whether each item is useful in order to avoid an absurd number of duplicate recursive calls when checking if a predetermined dungeon item location has a useful item or not.
      self.cached_items_are_useful = {}
      
      for item_name in items_to_check:
        if self.check_item_is_useful(item_name, inaccessible_undone_item_locations):
          self.cached_items_are_useful = None
          return item_name
      
      self.cached_items_are_useful = None
      
      return None
    
    def get_items_by_usefulness_fraction(self, item_names_to_check):
      # Takes a list of items and locations, and determines for each item what the lowest number of items including it the player needs before a new location is opened up, and returns that in a dict.
      # For example, say there are 3 items A B and C, and 2 locations X and Y.
      # Location X requires items A and B while location Y requires items A B and C.
      # This function would return {A: 2, B: 2, C: 3} because A requires 1 other item (B) to help access anything, B also requires one other item (A) to help access anything, but C requires 2 other items (both A and B) before it becomes useful.
      # In other words, items A and B have 1/2 usefulness, while item C has 1/3 usefulness.
      
      accessible_undone_locations = self.get_accessible_remaining_locations(for_progression=True)
      inaccessible_undone_item_locations = []
      locations_to_check = self.remaining_item_locations
      locations_to_check = self.filter_locations_for_progression(locations_to_check)
      for location_name in locations_to_check:
        if location_name not in accessible_undone_locations:
          if location_name in self.rando.race_mode_banned_locations:
            # Don't consider locations inside unchosen dungeons in race mode when calculating usefulness.
            continue
          if location_name in self.prerandomization_item_locations:
            # We just ignore items with predetermined items when calculating usefulness fractions.
            # TODO: In the future, we might want to consider recursively checking if the item here is useful, and if so include this location.
            continue
          inaccessible_undone_item_locations.append(location_name)
      
      # Generate a list of what items are needed for each inaccessible location (+beating the game).
      # Note: Performance could be improved somewhat by only calculating which items are needed for each location at the start of item randomization, instead of once per call to this function. But this seems unnecessary.
      item_names_for_all_locations = []
      for location_name in inaccessible_undone_item_locations:
        requirement_expression = self.item_locations[location_name]["Need"]
        item_names_for_loc = self.get_item_names_from_logical_expression_req(requirement_expression)
        item_names_for_all_locations.append(item_names_for_loc)
      item_names_to_beat_game = self.get_item_names_by_req_name("Can Reach and Defeat Ganondorf")
      item_names_for_all_locations.append(item_names_to_beat_game)
      
      # Now calculate the best case scenario usefulness fraction for all items given.
      item_by_usefulness_fraction = OrderedDict()
      for item_name in item_names_to_check:
        item_by_usefulness_fraction[item_name] = 9999
      
      for item_names_for_loc in item_names_for_all_locations:
        item_names_for_loc_without_owned = item_names_for_loc.copy()
        for item_name in self.currently_owned_items:
          if item_name in item_names_for_loc_without_owned:
            item_names_for_loc_without_owned.remove(item_name)
        
        for item_name in item_names_for_loc_without_owned:
          if item_name not in item_by_usefulness_fraction:
            continue
          usefulness_fraction_for_item = len(item_names_for_loc_without_owned)
          if usefulness_fraction_for_item < item_by_usefulness_fraction[item_name]:
            item_by_usefulness_fraction[item_name] = usefulness_fraction_for_item
      
      return item_by_usefulness_fraction
    
    def get_all_useless_items(self, items_to_check):
      # Searches through a given list of items and returns which of them do not open up even 1 new location.
      
      if len(items_to_check) == 0:
        return []
      
      accessible_undone_locations = self.get_accessible_remaining_locations(for_progression=True)
      inaccessible_undone_item_locations = []
      locations_to_check = self.remaining_item_locations
      locations_to_check = self.filter_locations_for_progression(locations_to_check)
      for location_name in locations_to_check:
        if location_name not in accessible_undone_locations:
          inaccessible_undone_item_locations.append(location_name)
      
      self.cached_items_are_useful = {}
      
      useless_items = []
      for item_name in items_to_check:
        if not self.check_item_is_useful(item_name, inaccessible_undone_item_locations):
          useless_items.append(item_name)
      
      self.cached_items_are_useful = None
      
      return useless_items
    
    def check_item_is_useful(self, item_name, inaccessible_undone_item_locations):
      # Checks whether a specific item unlocks any new locations or not.
      # This function should only be called by get_first_useful_item, get_all_useless_items, or by itself for recursion purposes.
      
      if item_name in self.cached_items_are_useful:
        return self.cached_items_are_useful[item_name]
      
      self.add_owned_item_or_item_group(item_name)
      
      for location_name in inaccessible_undone_item_locations:
        if location_name in self.rando.race_mode_banned_locations:
          # Don't consider locations inside unchosen dungeons in race mode when calculating usefulness.
          continue
        
        if location_name in self.prerandomization_item_locations:
          # If this location has a predetermined item in it, we need to recursively check if that item is useful.
          unlocked_prerand_item = self.prerandomization_item_locations[location_name]
          # Need to exclude the current location from recursive checks to prevent infinite recursion.
          temp_inaccessible_undone_item_locations = [
            loc for loc in inaccessible_undone_item_locations
            if not loc == location_name
          ]
          if not self.check_item_is_useful(unlocked_prerand_item, temp_inaccessible_undone_item_locations):
            # If that item is not useful, don't consider the current item useful for unlocking it.
            continue
          
          requirement_expression = self.item_locations[location_name]["Need"]
          if self.check_logical_expression_req(requirement_expression):
            self.remove_owned_item_or_item_group(item_name)
            self.cached_items_are_useful[item_name] = True
            return True
        
        requirement_expression = self.item_locations[location_name]["Need"]
        if self.check_logical_expression_req(requirement_expression):
          self.remove_owned_item_or_item_group(item_name)
          self.cached_items_are_useful[item_name] = True
          return True
      
      self.remove_owned_item_or_item_group(item_name)
      self.cached_items_are_useful[item_name] = False
      return False
    
    def filter_locations_for_progression(self, locations_to_filter, filter_sunken_treasure=False):
      return Logic.filter_locations_for_progression_static(
        locations_to_filter,
        self.item_locations,
        self.rando.options,
        filter_sunken_treasure=filter_sunken_treasure
      )
    
    @staticmethod
    def filter_locations_for_progression_static(locations_to_filter, item_locations, options, filter_sunken_treasure=False):
      filtered_locations = []
      for location_name in locations_to_filter:
        types = item_locations[location_name]["Types"]
        if "No progression" in types:
          continue
        if "Consumables only" in types:
          continue
        if "Dungeon" in types and not options.get("progression_dungeons"):
          continue
        if "Tingle Chest" in types and not options.get("progression_tingle_chests"):
          continue
        if "Great Fairy" in types and not options.get("progression_great_fairies"):
          continue
        if "Puzzle Secret Cave" in types and not options.get("progression_puzzle_secret_caves"):
          continue
        if "Combat Secret Cave" in types and not options.get("progression_combat_secret_caves"):
          continue
        if "Savage Labyrinth" in types and not options.get("progression_savage_labyrinth"):
          continue
        if "Short Sidequest" in types and not options.get("progression_short_sidequests"):
          continue
        if "Long Sidequest" in types and not options.get("progression_long_sidequests"):
          continue
        if "Spoils Trading" in types and not options.get("progression_spoils_trading"):
          continue
        if "Minigame" in types and not options.get("progression_minigames"):
          continue
        if "Battlesquid" in types and not options.get("progression_battlesquid"):
          continue
        if "Free Gift" in types and not options.get("progression_free_gifts"):
          continue
        if "Mail" in types and not options.get("progression_mail"):
          continue
        if ("Platform" in types or "Raft" in types) and not options.get("progression_platforms_rafts"):
          continue
        if "Submarine" in types and not options.get("progression_submarines"):
          continue
        if "Eye Reef Chest" in types and not options.get("progression_eye_reef_chests"):
          continue
        if ("Big Octo" in types or "Gunboat" in types) and not options.get("progression_big_octos_gunboats"):
          continue
        if "Expensive Purchase" in types and not options.get("progression_expensive_purchases"):
          continue
        if "Island Puzzle" in types and not options.get("progression_island_puzzles"):
          continue
        if ("Other Chest" in types or "Misc" in types) and not options.get("progression_misc"):
          continue
        if "Sunken Treasure" in types and filter_sunken_treasure:
          continue
        # Note: The Triforce/Treasure Chart sunken treasures are handled differently from other types.
        # During randomization they are handled by not considering the charts themselves to be progress items.
        # That results in the item randomizer considering these locations inaccessible until after all progress items are placed.
        # But when calculating the total number of progression locations, sunken treasures are filtered out entirely here so they can be specially counted elsewhere.
        
        filtered_locations.append(location_name)
      
      return filtered_locations
    
    def check_item_valid_in_location(self, item_name, location_name):
      # Don't allow dungeon items to appear outside their proper dungeon when Key-Lunacy is off.
      if self.is_dungeon_item(item_name) and not self.rando.options.get("keylunacy"):
        short_dungeon_name = item_name.split(" ")[0]
        dungeon_name = self.DUNGEON_NAMES[short_dungeon_name]
        if not self.is_dungeon_location(location_name, dungeon_name_to_match=dungeon_name):
          return False
      
      # Beedle's shop does not work properly if the same item is in multiple slots of the same shop.
      # Ban the Bait Bag slot from having bait.
      if location_name == "The Great Sea - Beedle's Shop Ship - 20 Rupee Item" and item_name in ["All-Purpose Bait", "Hyoi Pear"]:
        return False
      
      # Also ban the same item from appearing more than once in the rock spire shop ship.
      if location_name in self.rock_spire_shop_ship_locations:
        for other_location_name in self.rock_spire_shop_ship_locations:
          if other_location_name == location_name:
            continue
          if other_location_name in self.done_item_locations:
            other_item_name = self.done_item_locations[other_location_name]
            if item_name == other_item_name:
              return False
      
      # Our code to fix Zunari's Magic Armor item gift relies on the items Zunari gives all having different IDs.
      # Therefore we don't allow the other two items Zunari gives to be placed in the Magic Armor slot.
      if location_name == "Windfall Island - Zunari - Stock Exotic Flower in Zunari's Shop" and item_name in ["Town Flower", "Boat's Sail"]:
        return False
      
      types = self.item_locations[location_name]["Types"]
      if "Consumables only" in types:
        if item_name not in self.all_fixed_consumable_items and item_name not in self.duplicatable_consumable_items:
          return False
      
      return True
    
    def filter_items_by_any_valid_location(self, items, locations):
      # Filters out items that cannot be in any of the given possible locations.
      valid_items = []
      for item_name in items:
        if item_name in self.progress_item_groups:
          group_name = item_name
          items_in_group = self.progress_item_groups[group_name]
          if len(items_in_group) > len(locations):
            # Not enough locations to place all items in this group.
            continue
          # If the number of locations is sufficient, we consider this group able to be placed.
          # NOTE: We do not check if each individual item in the group can also be placed.
          # This is fine for shards and pearls, but would be incorrect for items that actually have location restrictions.
          valid_items.append(group_name)
        else:
          for location_name in locations:
            if self.check_item_valid_in_location(item_name, location_name):
              valid_items.append(item_name)
              break
      return valid_items
    
    def filter_locations_valid_for_item(self, locations, item_name):
      valid_locations = []
      for location_name in locations:
        if self.check_item_valid_in_location(item_name, location_name):
          valid_locations.append(location_name)
      return valid_locations
    
    def filter_items_valid_for_location(self, items, location_name):
      valid_items = []
      for item_name in items:
        if self.check_item_valid_in_location(item_name, location_name):
          valid_items.append(item_name)
      return valid_items
    
    @staticmethod
    def load_and_parse_item_locations():
      if Logic.initial_item_locations is not None:
        return Logic.initial_item_locations.copy()
      
      with open(os.path.join(LOGIC_PATH, "item_locations.txt")) as f:
        item_locations = yaml.load(f, YamlOrderedDictLoader)
      
      for location_name in item_locations:
        req_string = item_locations[location_name]["Need"]
        if req_string is None:
          raise Exception("Requirements are blank for location \"%s\"" % location_name)
        item_locations[location_name]["Need"] = Logic.parse_logic_expression(req_string)
        
        types_string = item_locations[location_name]["Types"]
        types = types_string.split(",")
        types = [type.strip() for type in types]
        item_locations[location_name]["Types"] = types
      
      Logic.initial_item_locations = item_locations.copy()
      return item_locations
      
    def load_and_parse_macros(self):
      if Logic.initial_macros is not None:
        self.macros = Logic.initial_macros.copy()
        return self.macros
      
      with open(os.path.join(LOGIC_PATH, "macros.txt")) as f:
        macro_strings = yaml.safe_load(f)
      
      self.macros = {}
      for macro_name, req_string in macro_strings.items():
        self.set_macro(macro_name, req_string)
      
      Logic.initial_macros = self.macros.copy()
      return self.macros
    
    def set_macro(self, macro_name, req_string):
      self.macros[macro_name] = Logic.parse_logic_expression(req_string)
      self.requirement_met_cache.clear()
    
    def update_entrance_connection_macros(self):
      # Update all the macros to take randomized entrances into account.
      for entrance_name, zone_name in self.rando.entrance_connections.items():
        zone_access_macro_name = "Can Access " + zone_name
        entrance_access_macro_name = "Can Access " + entrance_name
        self.set_macro(zone_access_macro_name, entrance_access_macro_name)
    
    def temporarily_make_dungeon_entrance_macros_impossible(self):
      # Update all the dungeon access macros to be considered "Impossible".
      # Useful when the item randomizer is deciding how to place keys in DRC.
      for zone_exit in entrances.DUNGEON_EXITS:
        dungeon_access_macro_name = "Can Access " + zone_exit.unique_name
        self.set_macro(dungeon_access_macro_name, "Impossible")
    
    def temporarily_make_entrance_macros_impossible(self):
      # Update all the dungeon/secret cave access macros to be considered "Impossible".
      # Useful when the entrance randomizer is selecting which dungeons/secret caves should be allowed where.
      for entrance_name, zone_name in self.rando.entrance_connections.items():
        zone_access_macro_name = "Can Access " + zone_name
        self.set_macro(zone_access_macro_name, "Impossible")
    
    def temporarily_make_entrance_macros_worst_case_scenario(self):
      # Update all the dungeon/secret cave access macros to be a combination of all the macros for accessing dungeons/secret caves that can have their entrance randomized.
      
      if self.rando.options.get("randomize_entrances") == "Dungeons":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=True, include_caves=False)
      elif self.rando.options.get("randomize_entrances") == "Secret Caves":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=False, include_caves=True)
      elif self.rando.options.get("randomize_entrances") == "Dungeons & Secret Caves (Separately)":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=True, include_caves=False)
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=False, include_caves=True)
      elif self.rando.options.get("randomize_entrances") == "Dungeons & Secret Caves (Together)":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=True, include_caves=True)
      else:
        raise Exception("Invalid entrance randomizer option: %s" % self.rando.options.get("randomize_entrances"))
    
    def temporarily_make_one_set_of_entrance_macros_worst_case_scenario(self, include_dungeons=False, include_caves=False):
      relevant_entrances = []
      zones = []
      if include_dungeons:
        relevant_entrances += entrances.DUNGEON_ENTRANCES
        zones += entrances.DUNGEON_EXITS
      if include_caves:
        relevant_entrances += entrances.SECRET_CAVE_ENTRANCES
        zones += entrances.SECRET_CAVE_EXITS
      
      all_entrance_access_macro_names = []
      for entrance in relevant_entrances:
        entrance_access_macro_name = "Can Access " + entrance.entrance_name
        all_entrance_access_macro_names.append(entrance_access_macro_name)
      can_access_all_entrances = " & ".join(all_entrance_access_macro_names)
      for zone in zones:
        zone_access_macro_name = "Can Access " + zone.unique_name
        self.set_macro(zone_access_macro_name, can_access_all_entrances)
    
    def update_chart_macros(self):
      # Update all the "Chart for Island" macros to take randomized charts into account.
      for island_number in range(1, 49+1):
        chart_macro_name = "Chart for Island %d" % island_number
        chart_item_name = self.rando.island_number_to_chart_name[island_number]
        
        if "Triforce Chart" in chart_item_name:
          req_string = "%s & Any Wallet Upgrade" % chart_item_name
        else:
          req_string = chart_item_name
        
        self.set_macro(chart_macro_name, req_string)
    
    def clean_item_name(self, item_name):
      # Remove parentheses from any item names that may have them. (Formerly Master Swords, though that's not an issue anymore.)
      return item_name.replace("(", "").replace(")", "")
    
    def make_useless_progress_items_nonprogress(self):
      # Detect which progress items don't actually help access any locations with the user's current settings, and move those over to the nonprogress item list instead.
      # This is so things like dungeons-only runs don't have a lot of useless items hogging the progress locations.
      
      if self.rando.options.get("randomize_entrances") not in ["Disabled", None]:
        # Since the randomizer hasn't decided which dungeon/secret cave will be where yet, we have to assume the worst case scenario by considering that you need to be able to access all dungeon/secret cave entrances in order to access each individual one.
        self.temporarily_make_entrance_macros_worst_case_scenario()
      
      filter_sunken_treasure = True
      if self.rando.options.get("progression_triforce_charts") or self.rando.options.get("progression_treasure_charts"):
        filter_sunken_treasure = False
      progress_locations = Logic.filter_locations_for_progression_static(
        self.item_locations.keys(),
        self.item_locations,
        self.rando.options,
        filter_sunken_treasure=filter_sunken_treasure
      )
      
      items_needed = OrderedDict()
      for location_name in progress_locations:
        requirement_expression = self.item_locations[location_name]["Need"]
        sub_items_needed = self.get_items_needed_from_logical_expression_req(requirement_expression)
        for item_name, num_required in sub_items_needed.items():
          items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      sub_items_needed = self.get_items_needed_by_req_name("Can Reach and Defeat Ganondorf")
      for item_name, num_required in sub_items_needed.items():
        items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      
      useful_items = self.flatten_items_needed_to_item_names(items_needed)
      
      all_progress_items_filtered = []
      for item_name in useful_items:
        if item_name == "Progressive Sword" and self.rando.options.get("sword_mode") == "Swordless":
          continue
        if self.is_dungeon_item(item_name) and not self.rando.options.get("progression_dungeons"):
          continue
        if item_name not in self.all_progress_items:
          if not (item_name.startswith("Triforce Chart ") or item_name.startswith("Treasure Chart")):
            raise Exception("Item %s opens up progress locations but is not in the list of all progress items." % item_name)
        all_progress_items_filtered.append(item_name)
      
      all_items_to_make_nonprogress = self.all_progress_items.copy()
      starting_items_to_remove = self.rando.starting_items.copy()
      for item_name in all_progress_items_filtered:
        if item_name not in all_items_to_make_nonprogress:
          if (item_name.startswith("Triforce Chart ") or item_name.startswith("Treasure Chart")):
            continue
        all_items_to_make_nonprogress.remove(item_name)
        if item_name in starting_items_to_remove:
          starting_items_to_remove.remove(item_name)
      unplaced_items_to_make_nonprogress = all_items_to_make_nonprogress.copy()
      for item_name in starting_items_to_remove:
        if item_name not in self.all_progress_items:
          continue
        unplaced_items_to_make_nonprogress.remove(item_name)
      
      for item_name in all_items_to_make_nonprogress:
        #print(item_name)
        self.all_progress_items.remove(item_name)
        self.all_nonprogress_items.append(item_name)
      for item_name in unplaced_items_to_make_nonprogress:
        self.unplaced_progress_items.remove(item_name)
        self.unplaced_nonprogress_items.append(item_name)
      
      if self.rando.options.get("randomize_entrances") not in ["Disabled", None]:
        # Reset the dungeon/secret cave access macros if we changed them earlier.
        self.update_entrance_connection_macros()
    
    def split_location_name_by_zone(self, location_name):
      if " - " in location_name:
        zone_name, specific_location_name = location_name.split(" - ", 1)
      else:
        zone_name = specific_location_name = location_name
      
      return zone_name, specific_location_name
    
    def is_dungeon_item(self, item_name):
      return (item_name in DUNGEON_PROGRESS_ITEMS or item_name in DUNGEON_NONPROGRESS_ITEMS)
    
    def is_dungeon_location(self, location_name, dungeon_name_to_match=None):
      zone_name, specific_location_name = self.split_location_name_by_zone(location_name)
      if zone_name not in self.DUNGEON_NAME_TO_SHORT_DUNGEON_NAME:
        # Not a dungeon.
        return False
      if dungeon_name_to_match and dungeon_name_to_match != zone_name:
        # Wrong dungeon.
        return False
      if "Sunken Treasure" in self.item_locations[location_name]["Types"]:
        # Outside the dungeon.
        return False
      return True
    
    @staticmethod
    def parse_logic_expression(string):
      tokens = [substring.strip() for substring in re.split("([&|()])", string)]
      tokens = [token for token in tokens if token != ""]
      
      stack = []
      for token in tokens:
        if token == "(":
          stack.append("(")
        elif token == ")":
          nested_tokens = []
          
          nested_parentheses_level = 0
          while len(stack) != 0:
            exp = stack.pop()
            if exp == "(":
              if nested_parentheses_level == 0:
                break
              else:
                nested_parentheses_level -= 1
            if exp == ")":
              nested_parentheses_level += 1
            nested_tokens.append(exp)
          
          nested_tokens.reverse()
          stack.append("(")
          stack.append(nested_tokens)
          stack.append(")")
        else:
          stack.append(token)
      
      return stack
    
    def check_requirement_met(self, req_name):
      if req_name in self.requirement_met_cache:
        return self.requirement_met_cache[req_name]
      
      if req_name.startswith("Progressive "):
        result = self.check_progressive_item_req(req_name)
      elif " Small Key x" in req_name:
        result = self.check_small_key_req(req_name)
      elif req_name.startswith("Can Access Other Location \""):
        result = self.check_other_location_requirement(req_name)
      elif req_name.startswith("Option \""):
        result = self.check_option_enabled_requirement(req_name)
      elif req_name in self.all_cleaned_item_names:
        result = req_name in self.currently_owned_items
      elif req_name in self.macros:
        logical_expression = self.macros[req_name]
        result = self.check_logical_expression_req(logical_expression)
      elif req_name == "Nothing":
        result = True
      elif req_name == "Impossible":
        result = False
      else:
        raise Exception("Unknown requirement name: " + req_name)
      
      self.requirement_met_cache[req_name] = result
      return result
    
    def check_logical_expression_req(self, logical_expression):
      expression_type = None
      subexpression_results = []
      tokens = logical_expression.copy()
      tokens.reverse()
      while tokens:
        token = tokens.pop()
        if token == "|":
          if expression_type == "AND":
            raise Exception("Error parsing progression requirements: & and | must not be within the same nesting level.")
          expression_type = "OR"
        elif token == "&":
          if expression_type == "OR":
            raise Exception("Error parsing progression requirements: & and | must not be within the same nesting level.")
          expression_type = "AND"
        elif token == "(":
          nested_expression = tokens.pop()
          if nested_expression == "(":
            # Nested parentheses
            nested_expression = ["("] + tokens.pop()
          result = self.check_logical_expression_req(nested_expression)
          subexpression_results.append(result)
          assert tokens.pop() == ")"
        else:
          # Subexpression.
          result = self.check_requirement_met(token)
          subexpression_results.append(result)
      
      if expression_type == "OR":
        return any(subexpression_results)
      else:
        return all(subexpression_results)
    
    def get_item_names_by_req_name(self, req_name):
      items_needed = self.get_items_needed_by_req_name(req_name)
      return self.flatten_items_needed_to_item_names(items_needed)
    
    def get_item_names_from_logical_expression_req(self, logical_expression):
      items_needed = self.get_items_needed_from_logical_expression_req(logical_expression)
      return self.flatten_items_needed_to_item_names(items_needed)
    
    def flatten_items_needed_to_item_names(self, items_needed):
      item_names = []
      for item_name, num_required in items_needed.items():
        item_names += [item_name]*num_required
      return item_names
    
    def get_items_needed_by_req_name(self, req_name):
      items_needed = OrderedDict()
      if req_name.startswith("Progressive "):
        match = re.search(r"^(Progressive .+) x(\d+)$", req_name)
        item_name = match.group(1)
        num_required = int(match.group(2))
        items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      elif " Small Key x" in req_name:
        match = re.search(r"^(.+ Small Key) x(\d+)$", req_name)
        small_key_name = match.group(1)
        num_keys_required = int(match.group(2))
        items_needed[small_key_name] = max(num_keys_required, items_needed.setdefault(small_key_name, 0))
      elif req_name.startswith("Can Access Other Location \""):
        match = re.search(r"^Can Access Other Location \"([^\"]+)\"$", req_name)
        other_location_name = match.group(1)
        requirement_expression = self.item_locations[other_location_name]["Need"]
        sub_items_needed = self.get_items_needed_from_logical_expression_req(requirement_expression)
        for item_name, num_required in sub_items_needed.items():
          items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      elif req_name.startswith("Option \""):
        pass
      elif req_name in self.all_cleaned_item_names:
        items_needed[req_name] = max(1, items_needed.setdefault(req_name, 0))
      elif req_name in self.macros:
        logical_expression = self.macros[req_name]
        sub_items_needed = self.get_items_needed_from_logical_expression_req(logical_expression)
        for item_name, num_required in sub_items_needed.items():
          items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      elif req_name == "Nothing":
        pass
      elif req_name == "Impossible":
        pass
      else:
        raise Exception("Unknown requirement name: " + req_name)
      
      return items_needed
    
    def get_items_needed_from_logical_expression_req(self, logical_expression):
      if self.check_logical_expression_req(logical_expression):
        # If this expression is already satisfied, we don't want to include any other items in the OR statement.
        return OrderedDict()
      
      items_needed = OrderedDict()
      tokens = logical_expression.copy()
      tokens.reverse()
      while tokens:
        token = tokens.pop()
        if token == "|":
          pass
        elif token == "&":
          pass
        elif token == "(":
          nested_expression = tokens.pop()
          if nested_expression == "(":
            # Nested parentheses
            nested_expression = ["("] + tokens.pop()
          sub_items_needed = self.get_items_needed_from_logical_expression_req(nested_expression)
          for item_name, num_required in sub_items_needed.items():
            items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
          assert tokens.pop() == ")"
        else:
          # Subexpression.
          sub_items_needed = self.get_items_needed_by_req_name(token)
          for item_name, num_required in sub_items_needed.items():
            items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      
      return items_needed
    
    def check_progressive_item_req(self, req_name):
      match = re.search(r"^(Progressive .+) x(\d+)$", req_name)
      item_name = match.group(1)
      num_required = int(match.group(2))
      
      num_owned = self.currently_owned_items.count(item_name)
      return num_owned >= num_required
    
    def check_small_key_req(self, req_name):
      match = re.search(r"^(.+ Small Key) x(\d+)$", req_name)
      small_key_name = match.group(1)
      num_keys_required = int(match.group(2))
      
      num_small_keys_owned = self.currently_owned_items.count(small_key_name)
      return num_small_keys_owned >= num_keys_required
    
    def check_other_location_requirement(self, req_name):
      match = re.search(r"^Can Access Other Location \"([^\"]+)\"$", req_name)
      other_location_name = match.group(1)
      
      requirement_expression = self.item_locations[other_location_name]["Need"]
      return self.check_logical_expression_req(requirement_expression)
    
    def check_option_enabled_requirement(self, req_name):
      positive_boolean_match = re.search(r"^Option \"([^\"]+)\" Enabled$", req_name)
      negative_boolean_match = re.search(r"^Option \"([^\"]+)\" Disabled$", req_name)
      positive_dropdown_match = re.search(r"^Option \"([^\"]+)\" Is \"([^\"]+)\"$", req_name)
      negative_dropdown_match = re.search(r"^Option \"([^\"]+)\" Is Not \"([^\"]+)\"$", req_name)
      positive_list_match = re.search(r"^Option \"([^\"]+)\" Contains \"([^\"]+)\"$", req_name)
      negative_list_match = re.search(r"^Option \"([^\"]+)\" Does Not Contain \"([^\"]+)\"$", req_name)
      if positive_boolean_match:
        option_name = positive_boolean_match.group(1)
        return not not self.rando.options.get(option_name)
      elif negative_boolean_match:
        option_name = negative_boolean_match.group(1)
        return not self.rando.options.get(option_name)
      elif positive_dropdown_match:
        option_name = positive_dropdown_match.group(1)
        value = positive_dropdown_match.group(2)
        return self.rando.options.get(option_name) == value
      elif negative_dropdown_match:
        option_name = negative_dropdown_match.group(1)
        value = negative_dropdown_match.group(2)
        return self.rando.options.get(option_name) != value
      elif positive_list_match:
        option_name = positive_list_match.group(1)
        value = positive_list_match.group(2)
        return value in self.rando.options.get(option_name, [])
      elif negative_list_match:
        option_name = negative_list_match.group(1)
        value = negative_list_match.group(2)
        return value not in self.rando.options.get(option_name, [])
      else:
        raise Exception("Invalid option check requirement: %s" % req_name)
    
    def chart_name_for_location(self, location_name):
      reqs = self.item_locations[location_name]["Need"]
      chart_req = next(req for req in reqs if req.startswith("Chart for Island "))
      
      reqs = self.macros[chart_req]
      chart_name = reqs[0]
      assert chart_name in self.all_cleaned_item_names
      
      return chart_name
    
    
    @staticmethod
    def load_and_parse_enemy_locations():
      with open(os.path.join(LOGIC_PATH, "enemy_locations.txt")) as f:
        enemy_locations = yaml.load(f, YamlOrderedDictLoader)
      
      return enemy_locations
    
    def filter_out_enemies_that_add_new_requirements(self, original_req_string, has_throwable_objects, has_bomb_flowers, possible_new_enemy_datas):
      # This function takes a list of enemy types and removes the ones that would add new required items for a room.
      # This is because the enemy randomizer cannot increase the logic requirements compared to when enemies are not randomized, it can only keep them the same or decrease them.
      
      # Accomplishing this by directly comparing the requirement lists for the original enemies in the room to the new possible enemies would be very complicated, if not impossible, to do accurately.
      # So instead, a brute-force approach is used.
      # The brute-force approach works like this:
      # * Build a list of progress items that were relevant for defeating the original enemies in the room.
      # * Build a very large list of all item combinations possible with the above items. This list is at least 2^n where n is the number of relevant items, but will be larger if having more than 1 of any given progressive item is relevant in this room. e.g. Hookshot being relevant multiplies the number of combos by 2 for having or not having it, but Fire & Ice Arrows multiplies the number of combos by 3 for having no bow, Hero's Bow, or Fire & Ice Arrows.
      # * Go through every single combination in this list and check if this combination allowed you to defeat all the original enemies in the room.
      # * For combinations that were valid for the original room, check to be sure that they are also valid for each enemy type we're considering placing in this room.
      # * Enemy types that cannot be beaten with even one item combination that could beat the original room are considered invalid and thrown away.
      
      # Default to assuming they're all allowed, remove ones as we find out they don't work.
      enemy_datas_allowed_here = possible_new_enemy_datas.copy()
      
      # Default to checking all enemy datas passed to this function.
      possible_new_enemy_datas_to_check = possible_new_enemy_datas.copy()
      
      # This tuple is the key we'll use into the cache to identify this set of requirement arguments.
      reqs_tuple_key = (original_req_string, has_throwable_objects, has_bomb_flowers)
      
      # However, we don't recheck ones that are already in the cache.
      if reqs_tuple_key not in self.cached_enemies_tested_for_reqs_tuple:
        self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key] = OrderedDict()
      else:
        for possible_new_enemy_data in possible_new_enemy_datas:
          enemy_name = possible_new_enemy_data["Pretty name"]
          if enemy_name in self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key]:
            # Cached.
            possible_new_enemy_datas_to_check.remove(possible_new_enemy_data)
            if not self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key][enemy_name]:
              enemy_datas_allowed_here.remove(possible_new_enemy_data)
      
      if not possible_new_enemy_datas_to_check:
        # All the enemies we need to check have already been checked and cached. Return early to improve performance.
        return enemy_datas_allowed_here
      
      orig_req_expression = Logic.parse_logic_expression(original_req_string)
      
      max_num_of_each_item_to_check = self.get_items_needed_from_logical_expression_req(orig_req_expression)
      
      # Remove starting items from being checked.
      for item_name in self.currently_owned_items:
        if item_name in max_num_of_each_item_to_check:
          max_num_of_each_item_to_check[item_name] -= 1
          if max_num_of_each_item_to_check[item_name] == 0:
            del max_num_of_each_item_to_check[item_name]
      
      relevant_item_names = list(max_num_of_each_item_to_check.keys())
      if self.rando.options.get("sword_mode") == "Swordless":
        if "Progressive Sword" in relevant_item_names:
          relevant_item_names.remove("Progressive Sword")
        if "Hurricane Spin" in relevant_item_names:
          relevant_item_names.remove("Hurricane Spin")
      
      item_combos_to_check = [[]]
      for item_name in relevant_item_names:
        old_item_combos = item_combos_to_check.copy()
        for num in range(1, max_num_of_each_item_to_check[item_name]+1):
          new_items_to_add = [item_name]*num
          for old_item_combo in old_item_combos:
            new_item_combo = old_item_combo + new_items_to_add
            if new_item_combo in item_combos_to_check:
              raise Exception("Duplicate item combo!")
            item_combos_to_check.append(new_item_combo)
      
      for item_combo in item_combos_to_check:
        for item_name in item_combo:
          self.add_owned_item_or_item_group(item_name)
        
        orig_req_met = self.check_logical_expression_req(orig_req_expression)
        if orig_req_met:
          for possible_new_enemy_data in possible_new_enemy_datas_to_check:
            if possible_new_enemy_data not in enemy_datas_allowed_here:
              # Already removed this one
              continue
            
            enemy_name = possible_new_enemy_data["Pretty name"]
            
            # TODO: Need to find a way to 100% guarantee the player has enough throwable objects to actually kill all the enemies.
            if has_throwable_objects and possible_new_enemy_data["Can be killed with thrown objects"]:
              # Allow enemies that can be killed by throwing stuff at them even if the player doesn't have the weapons to kill them.
              continue
            
            if has_bomb_flowers and possible_new_enemy_data["Can be killed with bomb flowers"]:
              # Allow enemies that can be killed by bombs in rooms with bomb flowers even if the player doesn't own the bombs upgrade.
              continue
            
            possible_new_enemy_req_expression = Logic.parse_logic_expression(possible_new_enemy_data["Requirements to defeat"])
            new_req_met = self.check_logical_expression_req(possible_new_enemy_req_expression)
            if not new_req_met:
              enemy_datas_allowed_here.remove(possible_new_enemy_data)
              self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key][enemy_name] = False
        
        for item_name in item_combo:
          self.remove_owned_item_or_item_group(item_name)
      
      for enemy_data in enemy_datas_allowed_here:
        enemy_name = enemy_data["Pretty name"]
        self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key][enemy_name] = True
      
      return enemy_datas_allowed_here
  
  class YamlOrderedDictLoader(yaml.SafeLoader):
    pass
  
  YamlOrderedDictLoader.add_constructor(
    yaml.resolver.BaseResolver.DEFAULT_MAPPING_TAG,
    lambda loader, node: OrderedDict(loader.construct_pairs(node))
  )
  
files: logic/logic.py
files: 
  import yaml
  import re
  from collections import OrderedDict
  import copy
  
  import os
  
  from logic.item_types import PROGRESS_ITEMS, NONPROGRESS_ITEMS, CONSUMABLE_ITEMS, DUPLICATABLE_CONSUMABLE_ITEMS, DUNGEON_PROGRESS_ITEMS, DUNGEON_NONPROGRESS_ITEMS
  from wwrando_paths import LOGIC_PATH
  from randomizers import entrances
  
  class Logic:
    DUNGEON_NAMES = OrderedDict([
      ("DRC",  "Dragon Roost Cavern"),
      ("FW",   "Forbidden Woods"),
      ("TotG", "Tower of the Gods"),
      ("FF",   "Forsaken Fortress"),
      ("ET",   "Earth Temple"),
      ("WT",   "Wind Temple"),
    ])
    DUNGEON_NAME_TO_SHORT_DUNGEON_NAME = OrderedDict([v, k] for k, v in DUNGEON_NAMES.items())
    
    PROGRESS_ITEM_GROUPS = OrderedDict([
      ("Triforce Shards",  [
        "Triforce Shard 1",
        "Triforce Shard 2",
        "Triforce Shard 3",
        "Triforce Shard 4",
        "Triforce Shard 5",
        "Triforce Shard 6",
        "Triforce Shard 7",
        "Triforce Shard 8",
      ]),
      ("Goddess Pearls",  [
        "Nayru's Pearl",
        "Din's Pearl",
        "Farore's Pearl",
      ]),
      ("Tingle Statues",  [
        "Dragon Tingle Statue",
        "Forbidden Tingle Statue",
        "Goddess Tingle Statue",
        "Earth Tingle Statue",
        "Wind Tingle Statue",
      ]),
    ])
    
    initial_item_locations = None
    initial_macros = None
    
    def __init__(self, rando):
      self.rando = rando
      self.requirement_met_cache = {}
      
      
      # Initialize location related attributes.
      self.item_locations = Logic.load_and_parse_item_locations()
      self.load_and_parse_macros()
      
      self.locations_by_zone_name = OrderedDict()
      for location_name in self.item_locations:
        zone_name, specific_location_name = self.split_location_name_by_zone(location_name)
        if zone_name not in self.locations_by_zone_name:
          self.locations_by_zone_name[zone_name] = []
        self.locations_by_zone_name[zone_name].append(location_name)
      
      self.remaining_item_locations = list(self.item_locations.keys())
      self.prerandomization_item_locations = OrderedDict()
      
      self.done_item_locations = OrderedDict()
      for location_name in self.item_locations:
        self.done_item_locations[location_name] = None
      
      self.rock_spire_shop_ship_locations = []
      for location_name, location in self.item_locations.items():
        if location_name.startswith("Rock Spire Isle - Beedle's Special Shop Ship - "):
          self.rock_spire_shop_ship_locations.append(location_name)
      
      # Sync the logic macros with the randomizer.
      self.update_entrance_connection_macros()
      self.update_chart_macros()
      
      
      # Initialize item related attributes.
      self.all_progress_items = PROGRESS_ITEMS.copy()
      self.all_nonprogress_items = NONPROGRESS_ITEMS.copy()
      self.all_fixed_consumable_items = CONSUMABLE_ITEMS.copy()
      self.duplicatable_consumable_items = DUPLICATABLE_CONSUMABLE_ITEMS.copy()
      
      self.triforce_chart_names = []
      self.treasure_chart_names = []
      for i in range(1, 8+1):
        self.triforce_chart_names.append("Triforce Chart %d" % i)
      for i in range(1, 41+1):
        self.treasure_chart_names.append("Treasure Chart %d" % i)
      
      if self.rando.options.get("sword_mode") == "Swordless":
        self.all_progress_items = [
          item_name for item_name in self.all_progress_items
          if item_name != "Progressive Sword"
        ]
        self.all_nonprogress_items = [
          item_name for item_name in self.all_nonprogress_items
          if item_name != "Hurricane Spin"
        ]
      
      if self.rando.options.get("progression_triforce_charts"):
        self.all_progress_items += self.triforce_chart_names
      else:
        self.all_nonprogress_items += self.triforce_chart_names
      if self.rando.options.get("progression_treasure_charts"):
        self.all_progress_items += self.treasure_chart_names
      else:
        self.all_nonprogress_items += self.treasure_chart_names
      
      # Add dungeon items to the progress/nonprogress items lists.
      if self.rando.options.get("progression_dungeons"):
        self.all_progress_items += DUNGEON_PROGRESS_ITEMS
      else:
        self.all_nonprogress_items += DUNGEON_PROGRESS_ITEMS
      self.all_nonprogress_items += DUNGEON_NONPROGRESS_ITEMS
      
      # Tell the randomizer to register dungeon-specific item names as the normal items.
      for dungeon_item_name in (DUNGEON_PROGRESS_ITEMS + DUNGEON_NONPROGRESS_ITEMS):
        regular_item_name = dungeon_item_name.split(" ", 1)[1]
        self.rando.item_name_to_id[dungeon_item_name] = self.rando.item_name_to_id[regular_item_name]
      
      self.all_cleaned_item_names = []
      all_item_names = []
      all_item_names += self.all_progress_items
      all_item_names += self.all_nonprogress_items
      all_item_names += self.all_fixed_consumable_items
      all_item_names += self.duplicatable_consumable_items
      for item_name in all_item_names:
        cleaned_item_name = self.clean_item_name(item_name)
        if cleaned_item_name not in self.all_cleaned_item_names:
          self.all_cleaned_item_names.append(cleaned_item_name)
      
      self.unplaced_progress_items = self.all_progress_items.copy()
      self.unplaced_nonprogress_items = self.all_nonprogress_items.copy()
      self.unplaced_fixed_consumable_items = self.all_fixed_consumable_items.copy()
      
      self.progress_item_groups = copy.deepcopy(self.PROGRESS_ITEM_GROUPS)
      
      self.currently_owned_items = []
      
      for item_name in self.rando.starting_items:
        self.add_owned_item(item_name)
      
      # Decide what will count as a progress item on these settings.
      self.requirement_met_cache.clear()
      self.make_useless_progress_items_nonprogress()
      
      # Replace progress items that are part of a group with the group name instead.
      for group_name, item_names in self.progress_item_groups.items():
        if all(item_name in self.unplaced_progress_items for item_name in item_names):
          self.unplaced_progress_items.append(group_name)
          for item_name in item_names:
            self.unplaced_progress_items.remove(item_name)
      
      # Remove starting items from item groups.
      for group_name, group_item_names in self.progress_item_groups.items():
        items_to_remove_from_group = [
          item_name for item_name in group_item_names
          if item_name in self.rando.starting_items
        ]
        for item_name in items_to_remove_from_group:
          self.progress_item_groups[group_name].remove(item_name)
        if len(self.progress_item_groups[group_name]) == 0:
          if group_name in self.unplaced_progress_items:
            self.unplaced_progress_items.remove(group_name)
      
      self.requirement_met_cache.clear()
      self.cached_enemies_tested_for_reqs_tuple = OrderedDict()
    
    def is_dungeon_or_cave(self, location_name):
      # Look up the setting that the location name is under
      is_dungeon = "Dungeon" in self.item_locations[location_name]["Types"]
      is_puzzle_cave = "Puzzle Secret Cave" in self.item_locations[location_name]["Types"]
      is_combat_cave = "Combat Secret Cave" in self.item_locations[location_name]["Types"]
      is_savage = "Savage Labyrinth" in self.item_locations[location_name]["Types"]
      
      return (is_dungeon or is_puzzle_cave or is_combat_cave or is_savage)
    
    def set_location_to_item(self, location_name, item_name):
      #print("Setting %s to %s" % (location_name, item_name))
      
      if self.done_item_locations[location_name]:
        raise Exception("Location was used twice: " + location_name)
      
      self.done_item_locations[location_name] = item_name
      self.remaining_item_locations.remove(location_name)
      
      self.add_owned_item(item_name)
    
    def set_multiple_locations_to_group(self, available_locations, group_name):
      items_in_group = self.progress_item_groups[group_name]
      
      #print("Placing group: %s (size: %d)" % (group_name, len(items_in_group)))
      
      if len(available_locations) < len(items_in_group):
        raise Exception("Not enough locations to place all items in group %s" % group_name)
      
      for item_name in items_in_group:
        available_locations = self.filter_locations_valid_for_item(available_locations, item_name)
        location_name = available_locations.pop()
        self.set_location_to_item(location_name, item_name)
      
      self.unplaced_progress_items.remove(group_name)
    
    def set_prerandomization_item_location(self, location_name, item_name):
      # Temporarily keep track of where certain items are placed before the main progression item randomization loop starts.
      
      #print("Setting prerand %s to %s" % (location_name, item_name))
      
      assert location_name in self.item_locations
      self.prerandomization_item_locations[location_name] = item_name
    
    def get_num_progression_items(self):
      num_progress_items = 0
      for item_name in self.unplaced_progress_items:
        if item_name in self.progress_item_groups:
          group_name = item_name
          for item_name in self.progress_item_groups[group_name]:
            num_progress_items += 1
        else:
          num_progress_items += 1
      
      return num_progress_items
    
    def get_num_progression_locations(self):
      return Logic.get_num_progression_locations_static(self.item_locations, self.rando.options)
    
    @staticmethod
    def get_num_progression_locations_static(item_locations, options):
      progress_locations = Logic.filter_locations_for_progression_static(
        item_locations.keys(),
        item_locations,
        options,
        filter_sunken_treasure=True
      )
      num_progress_locations = len(progress_locations)
      if options.get("progression_triforce_charts"):
        num_progress_locations += 8
      if options.get("progression_treasure_charts"):
        num_progress_locations += 41
      
      return num_progress_locations
  
    def get_max_race_mode_banned_locations(self):
      if not self.rando.options.get("race_mode"):
        return 0
      
      all_locations = self.item_locations.keys()
      progress_locations = self.filter_locations_for_progression(all_locations)
      location_counts_by_dungeon = OrderedDict()
      
      for location_name in progress_locations:
        zone_name, _ = self.split_location_name_by_zone(location_name)
        
        dungeon_name = None
        if self.is_dungeon_location(location_name):
          dungeon_name = zone_name
        elif location_name == "Mailbox - Letter from Orca":
          dungeon_name = "Forbidden Woods"
        elif location_name == "Mailbox - Letter from Baito":
          dungeon_name = "Earth Temple"
        elif location_name == "Mailbox - Letter from Aryll":
          dungeon_name = "Forsaken Fortress"
        elif location_name == "Mailbox - Letter from Tingle":
          dungeon_name = "Forsaken Fortress"
        
        if dungeon_name is None:
          continue
        
        if dungeon_name in location_counts_by_dungeon:
          location_counts_by_dungeon[dungeon_name] += 1
        else:
          location_counts_by_dungeon[dungeon_name] = 1
      
      dungeon_location_counts = list(location_counts_by_dungeon.values())
      dungeon_location_counts.sort(reverse=True)
      num_banned_dungeons = 6 - int(self.rando.options.get("num_race_mode_dungeons"))
      max_banned_locations = sum(dungeon_location_counts[:num_banned_dungeons])
      
      return max_banned_locations
    
    def get_progress_and_non_progress_locations(self):
      all_locations = self.item_locations.keys()
      progress_locations = self.filter_locations_for_progression(all_locations, filter_sunken_treasure=True)
      nonprogress_locations = []
      for location_name in all_locations:
        if location_name in progress_locations:
          continue
        
        types = self.item_locations[location_name]["Types"]
        if "Sunken Treasure" in types:
          chart_name = self.chart_name_for_location(location_name)
          if "Triforce Chart" in chart_name:
            if self.rando.options.get("progression_triforce_charts"):
              progress_locations.append(location_name)
            else:
              nonprogress_locations.append(location_name)
          else:
            if self.rando.options.get("progression_treasure_charts"):
              progress_locations.append(location_name)
            else:
              nonprogress_locations.append(location_name)
        else:
          nonprogress_locations.append(location_name)
      
      return (progress_locations, nonprogress_locations)
    
    def add_owned_item(self, item_name):
      cleaned_item_name = self.clean_item_name(item_name)
      if cleaned_item_name not in self.all_cleaned_item_names:
        raise Exception("Unknown item name: " + item_name)
      
      self.currently_owned_items.append(cleaned_item_name)
      
      if item_name in self.unplaced_progress_items:
        self.unplaced_progress_items.remove(item_name)
      elif item_name in self.unplaced_nonprogress_items:
        self.unplaced_nonprogress_items.remove(item_name)
      elif item_name in self.unplaced_fixed_consumable_items:
        self.unplaced_fixed_consumable_items.remove(item_name)
      
      self.requirement_met_cache.clear()
    
    def remove_owned_item(self, item_name):
      cleaned_item_name = self.clean_item_name(item_name)
      if cleaned_item_name not in self.all_cleaned_item_names:
        raise Exception("Unknown item name: " + item_name)
      
      self.currently_owned_items.remove(cleaned_item_name)
      
      if self.all_progress_items.count(item_name) > self.unplaced_progress_items.count(item_name):
        self.unplaced_progress_items.append(item_name)
      elif item_name in self.all_nonprogress_items:
        self.unplaced_nonprogress_items.append(item_name)
      else:
        # Removing consumable items doesn't work because we don't know if the item is from the fixed list or the duplicatable list
        raise Exception("Cannot remove item from simulated inventory: %s" % item_name)
      
      self.requirement_met_cache.clear()
    
    def add_owned_item_or_item_group(self, item_name):
      if item_name in self.progress_item_groups:
        group_name = item_name
        for item_name in self.progress_item_groups[group_name]:
          self.currently_owned_items.append(item_name)
        self.requirement_met_cache.clear()
      else:
        self.add_owned_item(item_name)
    
    def remove_owned_item_or_item_group(self, item_name):
      if item_name in self.progress_item_groups:
        group_name = item_name
        for item_name in self.progress_item_groups[group_name]:
          self.currently_owned_items.remove(item_name)
        self.requirement_met_cache.clear()
      else:
        self.remove_owned_item(item_name)
    
    def get_accessible_remaining_locations(self, for_progression=False):
      accessible_location_names = []
      
      locations_to_check = self.remaining_item_locations
      if for_progression:
        locations_to_check = self.filter_locations_for_progression(locations_to_check)
      
      for location_name in locations_to_check:
        requirement_expression = self.item_locations[location_name]["Need"]
        if self.check_logical_expression_req(requirement_expression):
          accessible_location_names.append(location_name)
      
      return accessible_location_names
    
    def get_first_useful_item(self, items_to_check):
      # Searches through a given list of items and returns the first one that opens up at least 1 new location.
      # The randomizer shuffles the list before passing it to this function, so in effect it picks a random useful item.
      
      accessible_undone_locations = self.get_accessible_remaining_locations(for_progression=True)
      inaccessible_undone_item_locations = []
      locations_to_check = self.remaining_item_locations
      locations_to_check = self.filter_locations_for_progression(locations_to_check)
      for location_name in locations_to_check:
        if location_name not in accessible_undone_locations:
          inaccessible_undone_item_locations.append(location_name)
      
      # Cache whether each item is useful in order to avoid an absurd number of duplicate recursive calls when checking if a predetermined dungeon item location has a useful item or not.
      self.cached_items_are_useful = {}
      
      for item_name in items_to_check:
        if self.check_item_is_useful(item_name, inaccessible_undone_item_locations):
          self.cached_items_are_useful = None
          return item_name
      
      self.cached_items_are_useful = None
      
      return None
    
    def get_items_by_usefulness_fraction(self, item_names_to_check):
      # Takes a list of items and locations, and determines for each item what the lowest number of items including it the player needs before a new location is opened up, and returns that in a dict.
      # For example, say there are 3 items A B and C, and 2 locations X and Y.
      # Location X requires items A and B while location Y requires items A B and C.
      # This function would return {A: 2, B: 2, C: 3} because A requires 1 other item (B) to help access anything, B also requires one other item (A) to help access anything, but C requires 2 other items (both A and B) before it becomes useful.
      # In other words, items A and B have 1/2 usefulness, while item C has 1/3 usefulness.
      
      accessible_undone_locations = self.get_accessible_remaining_locations(for_progression=True)
      inaccessible_undone_item_locations = []
      locations_to_check = self.remaining_item_locations
      locations_to_check = self.filter_locations_for_progression(locations_to_check)
      for location_name in locations_to_check:
        if location_name not in accessible_undone_locations:
          if location_name in self.rando.race_mode_banned_locations:
            # Don't consider locations inside unchosen dungeons in race mode when calculating usefulness.
            continue
          if location_name in self.prerandomization_item_locations:
            # We just ignore items with predetermined items when calculating usefulness fractions.
            # TODO: In the future, we might want to consider recursively checking if the item here is useful, and if so include this location.
            continue
          inaccessible_undone_item_locations.append(location_name)
      
      # Generate a list of what items are needed for each inaccessible location (+beating the game).
      # Note: Performance could be improved somewhat by only calculating which items are needed for each location at the start of item randomization, instead of once per call to this function. But this seems unnecessary.
      item_names_for_all_locations = []
      for location_name in inaccessible_undone_item_locations:
        requirement_expression = self.item_locations[location_name]["Need"]
        item_names_for_loc = self.get_item_names_from_logical_expression_req(requirement_expression)
        item_names_for_all_locations.append(item_names_for_loc)
      item_names_to_beat_game = self.get_item_names_by_req_name("Can Reach and Defeat Ganondorf")
      item_names_for_all_locations.append(item_names_to_beat_game)
      
      # Now calculate the best case scenario usefulness fraction for all items given.
      item_by_usefulness_fraction = OrderedDict()
      for item_name in item_names_to_check:
        item_by_usefulness_fraction[item_name] = 9999
      
      for item_names_for_loc in item_names_for_all_locations:
        item_names_for_loc_without_owned = item_names_for_loc.copy()
        for item_name in self.currently_owned_items:
          if item_name in item_names_for_loc_without_owned:
            item_names_for_loc_without_owned.remove(item_name)
        
        for item_name in item_names_for_loc_without_owned:
          if item_name not in item_by_usefulness_fraction:
            continue
          usefulness_fraction_for_item = len(item_names_for_loc_without_owned)
          if usefulness_fraction_for_item < item_by_usefulness_fraction[item_name]:
            item_by_usefulness_fraction[item_name] = usefulness_fraction_for_item
      
      return item_by_usefulness_fraction
    
    def get_all_useless_items(self, items_to_check):
      # Searches through a given list of items and returns which of them do not open up even 1 new location.
      
      if len(items_to_check) == 0:
        return []
      
      accessible_undone_locations = self.get_accessible_remaining_locations(for_progression=True)
      inaccessible_undone_item_locations = []
      locations_to_check = self.remaining_item_locations
      locations_to_check = self.filter_locations_for_progression(locations_to_check)
      for location_name in locations_to_check:
        if location_name not in accessible_undone_locations:
          inaccessible_undone_item_locations.append(location_name)
      
      self.cached_items_are_useful = {}
      
      useless_items = []
      for item_name in items_to_check:
        if not self.check_item_is_useful(item_name, inaccessible_undone_item_locations):
          useless_items.append(item_name)
      
      self.cached_items_are_useful = None
      
      return useless_items
    
    def check_item_is_useful(self, item_name, inaccessible_undone_item_locations):
      # Checks whether a specific item unlocks any new locations or not.
      # This function should only be called by get_first_useful_item, get_all_useless_items, or by itself for recursion purposes.
      
      if item_name in self.cached_items_are_useful:
        return self.cached_items_are_useful[item_name]
      
      self.add_owned_item_or_item_group(item_name)
      
      for location_name in inaccessible_undone_item_locations:
        if location_name in self.rando.race_mode_banned_locations:
          # Don't consider locations inside unchosen dungeons in race mode when calculating usefulness.
          continue
        
        if location_name in self.prerandomization_item_locations:
          # If this location has a predetermined item in it, we need to recursively check if that item is useful.
          unlocked_prerand_item = self.prerandomization_item_locations[location_name]
          # Need to exclude the current location from recursive checks to prevent infinite recursion.
          temp_inaccessible_undone_item_locations = [
            loc for loc in inaccessible_undone_item_locations
            if not loc == location_name
          ]
          if not self.check_item_is_useful(unlocked_prerand_item, temp_inaccessible_undone_item_locations):
            # If that item is not useful, don't consider the current item useful for unlocking it.
            continue
          
          requirement_expression = self.item_locations[location_name]["Need"]
          if self.check_logical_expression_req(requirement_expression):
            self.remove_owned_item_or_item_group(item_name)
            self.cached_items_are_useful[item_name] = True
            return True
        
        requirement_expression = self.item_locations[location_name]["Need"]
        if self.check_logical_expression_req(requirement_expression):
          self.remove_owned_item_or_item_group(item_name)
          self.cached_items_are_useful[item_name] = True
          return True
      
      self.remove_owned_item_or_item_group(item_name)
      self.cached_items_are_useful[item_name] = False
      return False
    
    def filter_locations_for_progression(self, locations_to_filter, filter_sunken_treasure=False):
      return Logic.filter_locations_for_progression_static(
        locations_to_filter,
        self.item_locations,
        self.rando.options,
        filter_sunken_treasure=filter_sunken_treasure
      )
    
    @staticmethod
    def filter_locations_for_progression_static(locations_to_filter, item_locations, options, filter_sunken_treasure=False):
      filtered_locations = []
      for location_name in locations_to_filter:
        types = item_locations[location_name]["Types"]
        if "No progression" in types:
          continue
        if "Consumables only" in types:
          continue
        if "Dungeon" in types and not options.get("progression_dungeons"):
          continue
        if "Tingle Chest" in types and not options.get("progression_tingle_chests"):
          continue
        if "Great Fairy" in types and not options.get("progression_great_fairies"):
          continue
        if "Puzzle Secret Cave" in types and not options.get("progression_puzzle_secret_caves"):
          continue
        if "Combat Secret Cave" in types and not options.get("progression_combat_secret_caves"):
          continue
        if "Savage Labyrinth" in types and not options.get("progression_savage_labyrinth"):
          continue
        if "Short Sidequest" in types and not options.get("progression_short_sidequests"):
          continue
        if "Long Sidequest" in types and not options.get("progression_long_sidequests"):
          continue
        if "Spoils Trading" in types and not options.get("progression_spoils_trading"):
          continue
        if "Minigame" in types and not options.get("progression_minigames"):
          continue
        if "Battlesquid" in types and not options.get("progression_battlesquid"):
          continue
        if "Free Gift" in types and not options.get("progression_free_gifts"):
          continue
        if "Mail" in types and not options.get("progression_mail"):
          continue
        if ("Platform" in types or "Raft" in types) and not options.get("progression_platforms_rafts"):
          continue
        if "Submarine" in types and not options.get("progression_submarines"):
          continue
        if "Eye Reef Chest" in types and not options.get("progression_eye_reef_chests"):
          continue
        if ("Big Octo" in types or "Gunboat" in types) and not options.get("progression_big_octos_gunboats"):
          continue
        if "Expensive Purchase" in types and not options.get("progression_expensive_purchases"):
          continue
        if "Island Puzzle" in types and not options.get("progression_island_puzzles"):
          continue
        if ("Other Chest" in types or "Misc" in types) and not options.get("progression_misc"):
          continue
        if "Sunken Treasure" in types and filter_sunken_treasure:
          continue
        # Note: The Triforce/Treasure Chart sunken treasures are handled differently from other types.
        # During randomization they are handled by not considering the charts themselves to be progress items.
        # That results in the item randomizer considering these locations inaccessible until after all progress items are placed.
        # But when calculating the total number of progression locations, sunken treasures are filtered out entirely here so they can be specially counted elsewhere.
        
        filtered_locations.append(location_name)
      
      return filtered_locations
    
    def check_item_valid_in_location(self, item_name, location_name):
      # Don't allow dungeon items to appear outside their proper dungeon when Key-Lunacy is off.
      if self.is_dungeon_item(item_name) and not self.rando.options.get("keylunacy"):
        short_dungeon_name = item_name.split(" ")[0]
        dungeon_name = self.DUNGEON_NAMES[short_dungeon_name]
        if not self.is_dungeon_location(location_name, dungeon_name_to_match=dungeon_name):
          return False
      
      # Beedle's shop does not work properly if the same item is in multiple slots of the same shop.
      # Ban the Bait Bag slot from having bait.
      if location_name == "The Great Sea - Beedle's Shop Ship - 20 Rupee Item" and item_name in ["All-Purpose Bait", "Hyoi Pear"]:
        return False
      
      # Also ban the same item from appearing more than once in the rock spire shop ship.
      if location_name in self.rock_spire_shop_ship_locations:
        for other_location_name in self.rock_spire_shop_ship_locations:
          if other_location_name == location_name:
            continue
          if other_location_name in self.done_item_locations:
            other_item_name = self.done_item_locations[other_location_name]
            if item_name == other_item_name:
              return False
      
      # Our code to fix Zunari's Magic Armor item gift relies on the items Zunari gives all having different IDs.
      # Therefore we don't allow the other two items Zunari gives to be placed in the Magic Armor slot.
      if location_name == "Windfall Island - Zunari - Stock Exotic Flower in Zunari's Shop" and item_name in ["Town Flower", "Boat's Sail"]:
        return False
      
      types = self.item_locations[location_name]["Types"]
      if "Consumables only" in types:
        if item_name not in self.all_fixed_consumable_items and item_name not in self.duplicatable_consumable_items:
          return False
      
      return True
    
    def filter_items_by_any_valid_location(self, items, locations):
      # Filters out items that cannot be in any of the given possible locations.
      valid_items = []
      for item_name in items:
        if item_name in self.progress_item_groups:
          group_name = item_name
          items_in_group = self.progress_item_groups[group_name]
          if len(items_in_group) > len(locations):
            # Not enough locations to place all items in this group.
            continue
          # If the number of locations is sufficient, we consider this group able to be placed.
          # NOTE: We do not check if each individual item in the group can also be placed.
          # This is fine for shards and pearls, but would be incorrect for items that actually have location restrictions.
          valid_items.append(group_name)
        else:
          for location_name in locations:
            if self.check_item_valid_in_location(item_name, location_name):
              valid_items.append(item_name)
              break
      return valid_items
    
    def filter_locations_valid_for_item(self, locations, item_name):
      valid_locations = []
      for location_name in locations:
        if self.check_item_valid_in_location(item_name, location_name):
          valid_locations.append(location_name)
      return valid_locations
    
    def filter_items_valid_for_location(self, items, location_name):
      valid_items = []
      for item_name in items:
        if self.check_item_valid_in_location(item_name, location_name):
          valid_items.append(item_name)
      return valid_items
    
    @staticmethod
    def load_and_parse_item_locations():
      if Logic.initial_item_locations is not None:
        return Logic.initial_item_locations.copy()
      
      with open(os.path.join(LOGIC_PATH, "item_locations.txt")) as f:
        item_locations = yaml.load(f, YamlOrderedDictLoader)
      
      for location_name in item_locations:
        req_string = item_locations[location_name]["Need"]
        if req_string is None:
          raise Exception("Requirements are blank for location \"%s\"" % location_name)
        item_locations[location_name]["Need"] = Logic.parse_logic_expression(req_string)
        
        types_string = item_locations[location_name]["Types"]
        types = types_string.split(",")
        types = [type.strip() for type in types]
        item_locations[location_name]["Types"] = types
      
      Logic.initial_item_locations = item_locations.copy()
      return item_locations
      
    def load_and_parse_macros(self):
      if Logic.initial_macros is not None:
        self.macros = Logic.initial_macros.copy()
        return self.macros
      
      with open(os.path.join(LOGIC_PATH, "macros.txt")) as f:
        macro_strings = yaml.safe_load(f)
      
      self.macros = {}
      for macro_name, req_string in macro_strings.items():
        self.set_macro(macro_name, req_string)
      
      Logic.initial_macros = self.macros.copy()
      return self.macros
    
    def set_macro(self, macro_name, req_string):
      self.macros[macro_name] = Logic.parse_logic_expression(req_string)
      self.requirement_met_cache.clear()
    
    def update_entrance_connection_macros(self):
      # Update all the macros to take randomized entrances into account.
      for entrance_name, zone_name in self.rando.entrance_connections.items():
        zone_access_macro_name = "Can Access " + zone_name
        entrance_access_macro_name = "Can Access " + entrance_name
        self.set_macro(zone_access_macro_name, entrance_access_macro_name)
    
    def temporarily_make_dungeon_entrance_macros_impossible(self):
      # Update all the dungeon access macros to be considered "Impossible".
      # Useful when the item randomizer is deciding how to place keys in DRC.
      for zone_exit in entrances.DUNGEON_EXITS:
        dungeon_access_macro_name = "Can Access " + zone_exit.unique_name
        self.set_macro(dungeon_access_macro_name, "Impossible")
    
    def temporarily_make_entrance_macros_impossible(self):
      # Update all the dungeon/secret cave access macros to be considered "Impossible".
      # Useful when the entrance randomizer is selecting which dungeons/secret caves should be allowed where.
      for entrance_name, zone_name in self.rando.entrance_connections.items():
        zone_access_macro_name = "Can Access " + zone_name
        self.set_macro(zone_access_macro_name, "Impossible")
    
    def temporarily_make_entrance_macros_worst_case_scenario(self):
      # Update all the dungeon/secret cave access macros to be a combination of all the macros for accessing dungeons/secret caves that can have their entrance randomized.
      
      if self.rando.options.get("randomize_entrances") == "Dungeons":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=True, include_caves=False)
      elif self.rando.options.get("randomize_entrances") == "Secret Caves":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=False, include_caves=True)
      elif self.rando.options.get("randomize_entrances") == "Dungeons & Secret Caves (Separately)":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=True, include_caves=False)
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=False, include_caves=True)
      elif self.rando.options.get("randomize_entrances") == "Dungeons & Secret Caves (Together)":
        self.temporarily_make_one_set_of_entrance_macros_worst_case_scenario(include_dungeons=True, include_caves=True)
      else:
        raise Exception("Invalid entrance randomizer option: %s" % self.rando.options.get("randomize_entrances"))
    
    def temporarily_make_one_set_of_entrance_macros_worst_case_scenario(self, include_dungeons=False, include_caves=False):
      relevant_entrances = []
      zones = []
      if include_dungeons:
        relevant_entrances += entrances.DUNGEON_ENTRANCES
        zones += entrances.DUNGEON_EXITS
      if include_caves:
        relevant_entrances += entrances.SECRET_CAVE_ENTRANCES
        zones += entrances.SECRET_CAVE_EXITS
      
      all_entrance_access_macro_names = []
      for entrance in relevant_entrances:
        entrance_access_macro_name = "Can Access " + entrance.entrance_name
        all_entrance_access_macro_names.append(entrance_access_macro_name)
      can_access_all_entrances = " & ".join(all_entrance_access_macro_names)
      for zone in zones:
        zone_access_macro_name = "Can Access " + zone.unique_name
        self.set_macro(zone_access_macro_name, can_access_all_entrances)
    
    def update_chart_macros(self):
      # Update all the "Chart for Island" macros to take randomized charts into account.
      for island_number in range(1, 49+1):
        chart_macro_name = "Chart for Island %d" % island_number
        chart_item_name = self.rando.island_number_to_chart_name[island_number]
        
        if "Triforce Chart" in chart_item_name:
          req_string = "%s & Any Wallet Upgrade" % chart_item_name
        else:
          req_string = chart_item_name
        
        self.set_macro(chart_macro_name, req_string)
    
    def clean_item_name(self, item_name):
      # Remove parentheses from any item names that may have them. (Formerly Master Swords, though that's not an issue anymore.)
      return item_name.replace("(", "").replace(")", "")
    
    def make_useless_progress_items_nonprogress(self):
      # Detect which progress items don't actually help access any locations with the user's current settings, and move those over to the nonprogress item list instead.
      # This is so things like dungeons-only runs don't have a lot of useless items hogging the progress locations.
      
      if self.rando.options.get("randomize_entrances") not in ["Disabled", None]:
        # Since the randomizer hasn't decided which dungeon/secret cave will be where yet, we have to assume the worst case scenario by considering that you need to be able to access all dungeon/secret cave entrances in order to access each individual one.
        self.temporarily_make_entrance_macros_worst_case_scenario()
      
      filter_sunken_treasure = True
      if self.rando.options.get("progression_triforce_charts") or self.rando.options.get("progression_treasure_charts"):
        filter_sunken_treasure = False
      progress_locations = Logic.filter_locations_for_progression_static(
        self.item_locations.keys(),
        self.item_locations,
        self.rando.options,
        filter_sunken_treasure=filter_sunken_treasure
      )
      
      items_needed = OrderedDict()
      for location_name in progress_locations:
        requirement_expression = self.item_locations[location_name]["Need"]
        sub_items_needed = self.get_items_needed_from_logical_expression_req(requirement_expression)
        for item_name, num_required in sub_items_needed.items():
          items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      sub_items_needed = self.get_items_needed_by_req_name("Can Reach and Defeat Ganondorf")
      for item_name, num_required in sub_items_needed.items():
        items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      
      useful_items = self.flatten_items_needed_to_item_names(items_needed)
      
      all_progress_items_filtered = []
      for item_name in useful_items:
        if item_name == "Progressive Sword" and self.rando.options.get("sword_mode") == "Swordless":
          continue
        if self.is_dungeon_item(item_name) and not self.rando.options.get("progression_dungeons"):
          continue
        if item_name not in self.all_progress_items:
          if not (item_name.startswith("Triforce Chart ") or item_name.startswith("Treasure Chart")):
            raise Exception("Item %s opens up progress locations but is not in the list of all progress items." % item_name)
        all_progress_items_filtered.append(item_name)
      
      all_items_to_make_nonprogress = self.all_progress_items.copy()
      starting_items_to_remove = self.rando.starting_items.copy()
      for item_name in all_progress_items_filtered:
        if item_name not in all_items_to_make_nonprogress:
          if (item_name.startswith("Triforce Chart ") or item_name.startswith("Treasure Chart")):
            continue
        all_items_to_make_nonprogress.remove(item_name)
        if item_name in starting_items_to_remove:
          starting_items_to_remove.remove(item_name)
      unplaced_items_to_make_nonprogress = all_items_to_make_nonprogress.copy()
      for item_name in starting_items_to_remove:
        if item_name not in self.all_progress_items:
          continue
        unplaced_items_to_make_nonprogress.remove(item_name)
      
      for item_name in all_items_to_make_nonprogress:
        #print(item_name)
        self.all_progress_items.remove(item_name)
        self.all_nonprogress_items.append(item_name)
      for item_name in unplaced_items_to_make_nonprogress:
        self.unplaced_progress_items.remove(item_name)
        self.unplaced_nonprogress_items.append(item_name)
      
      if self.rando.options.get("randomize_entrances") not in ["Disabled", None]:
        # Reset the dungeon/secret cave access macros if we changed them earlier.
        self.update_entrance_connection_macros()
    
    def split_location_name_by_zone(self, location_name):
      if " - " in location_name:
        zone_name, specific_location_name = location_name.split(" - ", 1)
      else:
        zone_name = specific_location_name = location_name
      
      return zone_name, specific_location_name
    
    def is_dungeon_item(self, item_name):
      return (item_name in DUNGEON_PROGRESS_ITEMS or item_name in DUNGEON_NONPROGRESS_ITEMS)
    
    def is_dungeon_location(self, location_name, dungeon_name_to_match=None):
      zone_name, specific_location_name = self.split_location_name_by_zone(location_name)
      if zone_name not in self.DUNGEON_NAME_TO_SHORT_DUNGEON_NAME:
        # Not a dungeon.
        return False
      if dungeon_name_to_match and dungeon_name_to_match != zone_name:
        # Wrong dungeon.
        return False
      if "Sunken Treasure" in self.item_locations[location_name]["Types"]:
        # Outside the dungeon.
        return False
      return True
    
    @staticmethod
    def parse_logic_expression(string):
      tokens = [substring.strip() for substring in re.split("([&|()])", string)]
      tokens = [token for token in tokens if token != ""]
      
      stack = []
      for token in tokens:
        if token == "(":
          stack.append("(")
        elif token == ")":
          nested_tokens = []
          
          nested_parentheses_level = 0
          while len(stack) != 0:
            exp = stack.pop()
            if exp == "(":
              if nested_parentheses_level == 0:
                break
              else:
                nested_parentheses_level -= 1
            if exp == ")":
              nested_parentheses_level += 1
            nested_tokens.append(exp)
          
          nested_tokens.reverse()
          stack.append("(")
          stack.append(nested_tokens)
          stack.append(")")
        else:
          stack.append(token)
      
      return stack
    
    def check_requirement_met(self, req_name):
      if req_name in self.requirement_met_cache:
        return self.requirement_met_cache[req_name]
      
      if req_name.startswith("Progressive "):
        result = self.check_progressive_item_req(req_name)
      elif " Small Key x" in req_name:
        result = self.check_small_key_req(req_name)
      elif req_name.startswith("Can Access Other Location \""):
        result = self.check_other_location_requirement(req_name)
      elif req_name.startswith("Option \""):
        result = self.check_option_enabled_requirement(req_name)
      elif req_name in self.all_cleaned_item_names:
        result = req_name in self.currently_owned_items
      elif req_name in self.macros:
        logical_expression = self.macros[req_name]
        result = self.check_logical_expression_req(logical_expression)
      elif req_name == "Nothing":
        result = True
      elif req_name == "Impossible":
        result = False
      else:
        raise Exception("Unknown requirement name: " + req_name)
      
      self.requirement_met_cache[req_name] = result
      return result
    
    def check_logical_expression_req(self, logical_expression):
      expression_type = None
      subexpression_results = []
      tokens = logical_expression.copy()
      tokens.reverse()
      while tokens:
        token = tokens.pop()
        if token == "|":
          if expression_type == "AND":
            raise Exception("Error parsing progression requirements: & and | must not be within the same nesting level.")
          expression_type = "OR"
        elif token == "&":
          if expression_type == "OR":
            raise Exception("Error parsing progression requirements: & and | must not be within the same nesting level.")
          expression_type = "AND"
        elif token == "(":
          nested_expression = tokens.pop()
          if nested_expression == "(":
            # Nested parentheses
            nested_expression = ["("] + tokens.pop()
          result = self.check_logical_expression_req(nested_expression)
          subexpression_results.append(result)
          assert tokens.pop() == ")"
        else:
          # Subexpression.
          result = self.check_requirement_met(token)
          subexpression_results.append(result)
      
      if expression_type == "OR":
        return any(subexpression_results)
      else:
        return all(subexpression_results)
    
    def get_item_names_by_req_name(self, req_name):
      items_needed = self.get_items_needed_by_req_name(req_name)
      return self.flatten_items_needed_to_item_names(items_needed)
    
    def get_item_names_from_logical_expression_req(self, logical_expression):
      items_needed = self.get_items_needed_from_logical_expression_req(logical_expression)
      return self.flatten_items_needed_to_item_names(items_needed)
    
    def flatten_items_needed_to_item_names(self, items_needed):
      item_names = []
      for item_name, num_required in items_needed.items():
        item_names += [item_name]*num_required
      return item_names
    
    def get_items_needed_by_req_name(self, req_name):
      items_needed = OrderedDict()
      if req_name.startswith("Progressive "):
        match = re.search(r"^(Progressive .+) x(\d+)$", req_name)
        item_name = match.group(1)
        num_required = int(match.group(2))
        items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      elif " Small Key x" in req_name:
        match = re.search(r"^(.+ Small Key) x(\d+)$", req_name)
        small_key_name = match.group(1)
        num_keys_required = int(match.group(2))
        items_needed[small_key_name] = max(num_keys_required, items_needed.setdefault(small_key_name, 0))
      elif req_name.startswith("Can Access Other Location \""):
        match = re.search(r"^Can Access Other Location \"([^\"]+)\"$", req_name)
        other_location_name = match.group(1)
        requirement_expression = self.item_locations[other_location_name]["Need"]
        sub_items_needed = self.get_items_needed_from_logical_expression_req(requirement_expression)
        for item_name, num_required in sub_items_needed.items():
          items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      elif req_name.startswith("Option \""):
        pass
      elif req_name in self.all_cleaned_item_names:
        items_needed[req_name] = max(1, items_needed.setdefault(req_name, 0))
      elif req_name in self.macros:
        logical_expression = self.macros[req_name]
        sub_items_needed = self.get_items_needed_from_logical_expression_req(logical_expression)
        for item_name, num_required in sub_items_needed.items():
          items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      elif req_name == "Nothing":
        pass
      elif req_name == "Impossible":
        pass
      else:
        raise Exception("Unknown requirement name: " + req_name)
      
      return items_needed
    
    def get_items_needed_from_logical_expression_req(self, logical_expression):
      if self.check_logical_expression_req(logical_expression):
        # If this expression is already satisfied, we don't want to include any other items in the OR statement.
        return OrderedDict()
      
      items_needed = OrderedDict()
      tokens = logical_expression.copy()
      tokens.reverse()
      while tokens:
        token = tokens.pop()
        if token == "|":
          pass
        elif token == "&":
          pass
        elif token == "(":
          nested_expression = tokens.pop()
          if nested_expression == "(":
            # Nested parentheses
            nested_expression = ["("] + tokens.pop()
          sub_items_needed = self.get_items_needed_from_logical_expression_req(nested_expression)
          for item_name, num_required in sub_items_needed.items():
            items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
          assert tokens.pop() == ")"
        else:
          # Subexpression.
          sub_items_needed = self.get_items_needed_by_req_name(token)
          for item_name, num_required in sub_items_needed.items():
            items_needed[item_name] = max(num_required, items_needed.setdefault(item_name, 0))
      
      return items_needed
    
    def check_progressive_item_req(self, req_name):
      match = re.search(r"^(Progressive .+) x(\d+)$", req_name)
      item_name = match.group(1)
      num_required = int(match.group(2))
      
      num_owned = self.currently_owned_items.count(item_name)
      return num_owned >= num_required
    
    def check_small_key_req(self, req_name):
      match = re.search(r"^(.+ Small Key) x(\d+)$", req_name)
      small_key_name = match.group(1)
      num_keys_required = int(match.group(2))
      
      num_small_keys_owned = self.currently_owned_items.count(small_key_name)
      return num_small_keys_owned >= num_keys_required
    
    def check_other_location_requirement(self, req_name):
      match = re.search(r"^Can Access Other Location \"([^\"]+)\"$", req_name)
      other_location_name = match.group(1)
      
      requirement_expression = self.item_locations[other_location_name]["Need"]
      return self.check_logical_expression_req(requirement_expression)
    
    def check_option_enabled_requirement(self, req_name):
      positive_boolean_match = re.search(r"^Option \"([^\"]+)\" Enabled$", req_name)
      negative_boolean_match = re.search(r"^Option \"([^\"]+)\" Disabled$", req_name)
      positive_dropdown_match = re.search(r"^Option \"([^\"]+)\" Is \"([^\"]+)\"$", req_name)
      negative_dropdown_match = re.search(r"^Option \"([^\"]+)\" Is Not \"([^\"]+)\"$", req_name)
      positive_list_match = re.search(r"^Option \"([^\"]+)\" Contains \"([^\"]+)\"$", req_name)
      negative_list_match = re.search(r"^Option \"([^\"]+)\" Does Not Contain \"([^\"]+)\"$", req_name)
      if positive_boolean_match:
        option_name = positive_boolean_match.group(1)
        return not not self.rando.options.get(option_name)
      elif negative_boolean_match:
        option_name = negative_boolean_match.group(1)
        return not self.rando.options.get(option_name)
      elif positive_dropdown_match:
        option_name = positive_dropdown_match.group(1)
        value = positive_dropdown_match.group(2)
        return self.rando.options.get(option_name) == value
      elif negative_dropdown_match:
        option_name = negative_dropdown_match.group(1)
        value = negative_dropdown_match.group(2)
        return self.rando.options.get(option_name) != value
      elif positive_list_match:
        option_name = positive_list_match.group(1)
        value = positive_list_match.group(2)
        return value in self.rando.options.get(option_name, [])
      elif negative_list_match:
        option_name = negative_list_match.group(1)
        value = negative_list_match.group(2)
        return value not in self.rando.options.get(option_name, [])
      else:
        raise Exception("Invalid option check requirement: %s" % req_name)
    
    def chart_name_for_location(self, location_name):
      reqs = self.item_locations[location_name]["Need"]
      chart_req = next(req for req in reqs if req.startswith("Chart for Island "))
      
      reqs = self.macros[chart_req]
      chart_name = reqs[0]
      assert chart_name in self.all_cleaned_item_names
      
      return chart_name
    
    
    @staticmethod
    def load_and_parse_enemy_locations():
      with open(os.path.join(LOGIC_PATH, "enemy_locations.txt")) as f:
        enemy_locations = yaml.load(f, YamlOrderedDictLoader)
      
      return enemy_locations
    
    def filter_out_enemies_that_add_new_requirements(self, original_req_string, has_throwable_objects, has_bomb_flowers, possible_new_enemy_datas):
      # This function takes a list of enemy types and removes the ones that would add new required items for a room.
      # This is because the enemy randomizer cannot increase the logic requirements compared to when enemies are not randomized, it can only keep them the same or decrease them.
      
      # Accomplishing this by directly comparing the requirement lists for the original enemies in the room to the new possible enemies would be very complicated, if not impossible, to do accurately.
      # So instead, a brute-force approach is used.
      # The brute-force approach works like this:
      # * Build a list of progress items that were relevant for defeating the original enemies in the room.
      # * Build a very large list of all item combinations possible with the above items. This list is at least 2^n where n is the number of relevant items, but will be larger if having more than 1 of any given progressive item is relevant in this room. e.g. Hookshot being relevant multiplies the number of combos by 2 for having or not having it, but Fire & Ice Arrows multiplies the number of combos by 3 for having no bow, Hero's Bow, or Fire & Ice Arrows.
      # * Go through every single combination in this list and check if this combination allowed you to defeat all the original enemies in the room.
      # * For combinations that were valid for the original room, check to be sure that they are also valid for each enemy type we're considering placing in this room.
      # * Enemy types that cannot be beaten with even one item combination that could beat the original room are considered invalid and thrown away.
      
      # Default to assuming they're all allowed, remove ones as we find out they don't work.
      enemy_datas_allowed_here = possible_new_enemy_datas.copy()
      
      # Default to checking all enemy datas passed to this function.
      possible_new_enemy_datas_to_check = possible_new_enemy_datas.copy()
      
      # This tuple is the key we'll use into the cache to identify this set of requirement arguments.
      reqs_tuple_key = (original_req_string, has_throwable_objects, has_bomb_flowers)
      
      # However, we don't recheck ones that are already in the cache.
      if reqs_tuple_key not in self.cached_enemies_tested_for_reqs_tuple:
        self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key] = OrderedDict()
      else:
        for possible_new_enemy_data in possible_new_enemy_datas:
          enemy_name = possible_new_enemy_data["Pretty name"]
          if enemy_name in self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key]:
            # Cached.
            possible_new_enemy_datas_to_check.remove(possible_new_enemy_data)
            if not self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key][enemy_name]:
              enemy_datas_allowed_here.remove(possible_new_enemy_data)
      
      if not possible_new_enemy_datas_to_check:
        # All the enemies we need to check have already been checked and cached. Return early to improve performance.
        return enemy_datas_allowed_here
      
      orig_req_expression = Logic.parse_logic_expression(original_req_string)
      
      max_num_of_each_item_to_check = self.get_items_needed_from_logical_expression_req(orig_req_expression)
      
      # Remove starting items from being checked.
      for item_name in self.currently_owned_items:
        if item_name in max_num_of_each_item_to_check:
          max_num_of_each_item_to_check[item_name] -= 1
          if max_num_of_each_item_to_check[item_name] == 0:
            del max_num_of_each_item_to_check[item_name]
      
      relevant_item_names = list(max_num_of_each_item_to_check.keys())
      if self.rando.options.get("sword_mode") == "Swordless":
        if "Progressive Sword" in relevant_item_names:
          relevant_item_names.remove("Progressive Sword")
        if "Hurricane Spin" in relevant_item_names:
          relevant_item_names.remove("Hurricane Spin")
      
      item_combos_to_check = [[]]
      for item_name in relevant_item_names:
        old_item_combos = item_combos_to_check.copy()
        for num in range(1, max_num_of_each_item_to_check[item_name]+1):
          new_items_to_add = [item_name]*num
          for old_item_combo in old_item_combos:
            new_item_combo = old_item_combo + new_items_to_add
            if new_item_combo in item_combos_to_check:
              raise Exception("Duplicate item combo!")
            item_combos_to_check.append(new_item_combo)
      
      for item_combo in item_combos_to_check:
        for item_name in item_combo:
          self.add_owned_item_or_item_group(item_name)
        
        orig_req_met = self.check_logical_expression_req(orig_req_expression)
        if orig_req_met:
          for possible_new_enemy_data in possible_new_enemy_datas_to_check:
            if possible_new_enemy_data not in enemy_datas_allowed_here:
              # Already removed this one
              continue
            
            enemy_name = possible_new_enemy_data["Pretty name"]
            
            # TODO: Need to find a way to 100% guarantee the player has enough throwable objects to actually kill all the enemies.
            if has_throwable_objects and possible_new_enemy_data["Can be killed with thrown objects"]:
              # Allow enemies that can be killed by throwing stuff at them even if the player doesn't have the weapons to kill them.
              continue
            
            if has_bomb_flowers and possible_new_enemy_data["Can be killed with bomb flowers"]:
              # Allow enemies that can be killed by bombs in rooms with bomb flowers even if the player doesn't own the bombs upgrade.
              continue
            
            possible_new_enemy_req_expression = Logic.parse_logic_expression(possible_new_enemy_data["Requirements to defeat"])
            new_req_met = self.check_logical_expression_req(possible_new_enemy_req_expression)
            if not new_req_met:
              enemy_datas_allowed_here.remove(possible_new_enemy_data)
              self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key][enemy_name] = False
        
        for item_name in item_combo:
          self.remove_owned_item_or_item_group(item_name)
      
      for enemy_data in enemy_datas_allowed_here:
        enemy_name = enemy_data["Pretty name"]
        self.cached_enemies_tested_for_reqs_tuple[reqs_tuple_key][enemy_name] = True
      
      return enemy_datas_allowed_here
  
  class YamlOrderedDictLoader(yaml.SafeLoader):
    pass
  
  YamlOrderedDictLoader.add_constructor(
    yaml.resolver.BaseResolver.DEFAULT_MAPPING_TAG,
    lambda loader, node: OrderedDict(loader.construct_pairs(node))
  )
  
files: logic/logic.py