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
  
  [... the rest is omitted ...]
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_
  
  [... the rest is omitted ...]
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("
  
  [... the rest is omitted ...]
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
  
  [... the rest is omitted ...]
files: logic/logic.py