The challenge of this problem is to read in a series of directory changes and list operations and process these into a tree of directories and files.

There are some technical issues to do with keeping track of our position in the directory tree, adding items to the directory, etc, but these are not specifically Icon issues.

Of interest from a Icon point of view are:

1. Scanning a string where there may be multiple possible patterns
2. Writing our own generator.

In this problem, the input can be one of several kinds: the "cd" or "ls" operations, or a definition of a directory or file. We can check each case using the tab(match(STR)) or =STR test:

  line ? {
    if ="$ cd /" then {
      # process cd root
    } else if ="$ cd .." then {
      # process cd ..
    } else if ="$ cd " then {     # <1>
      dirname := tab(0)           # <2>
      # process directory change
    } else if ="$ ls" then {
      # process ls
    } else if ="dir " then {
      dirname := tab(0)
      # process directory definition
    } else { # assume is a file
      size := tab(many(&digits))
      =" "
      filename := tab(0)
      # process file definition
    }
  }

1. The match operation leaves the cursor at the end of its matched string
2. ... so tab(0) can pick up the rest of the line as the directory name.

The directories and files are stored in a nested data structure, defined as components of a record:

record fileobject(name, size, children)

When a file is read, its size is set and there are no children (empty list). When a directory is defined, it will have children added.

To complete the two tasks, we need to find information about the directories, and this means iterating through the directories themselves. We would like to use the usual every ... do construct to iterate through directories, so we write a generator procedure:

procedure directories(item)                     # <1>
  if *item.children = 0 then {                  # <2>
    fail                                        # <3>
  } else {
    suspend item                                # <4>
    every suspend directories(!item.children)   # <5>
  }
end

1. We start from a given "fileobject" instance.
2. If this item has no children, then fail, because it must be a file.
3. ... fail stops the generator
4. This item is a directory, so suspend (return) this item.
5. Recursively suspend any sub-directories.

Given this procedure, we can now iterate through all directories using:

  every directory := directories(root) do {
    # work on directory
  }

The only interesting part of the program is how the location within the file system is maintained when loading in the definition: the path is kept as a list, and the current directory is the first item in the list. Hence, "cd .." is as simple as popping an item off the path. But seeing the definition of a directory or file means the new definition can be added as a child to the first item.

procedure main(inputs)
  local filename

  if *inputs = 1 then {
    filename := inputs[1]

    # Part 1 solution
    write("Part 1 solution is: ", part_1(filename))
    # Part 2 solution
    write("Part 2 directory size is: ", part_2(filename))
  } else {
    write("Provide a filename of data")
  }
end

record fileobject(name, size, children)

procedure part_1(filename)
  local directory, item_total, root

  root := load_filesystem(filename)

  item_total := 0
  every directory := directories(root) do
    if directory.size <= 100000 then
      item_total +:= directory.size

  return item_total
end

procedure part_2(filename)
  local directory, root, smallest_directory
  local remaining_space, required_space

  root := load_filesystem(filename)
  remaining_space := 70000000 - root.size
  required_space := 30000000 - remaining_space
  if required_space <= 0 then {
    write ("Enough space exists")
  } else {
    smallest_directory := root
    every directory := directories(root) do {
      if required_space < directory.size < smallest_directory.size then
        smallest_directory := directory
    }
  }
  return smallest_directory.size
end

procedure load_filesystem(filename)
  local file, line
  local dir, dirname, filename, size
  local path, root

  root := fileobject("/", 0, [])                              # <1>
  path := [root]                                              # <2>

  file := open(filename, "r") | stop("Could not open file")
  every line := !file do {
    line ? {
      if ="$ cd /" then {
        path := [root]                                        # <3>
      } else if ="$ cd .." then {
        pop(path)                                             # <4>
      } else if ="$ cd " then {
        dirname := tab(0)
        every dir := !path[1].children do {                   # <5>
          if dir.name == dirname then {
            push(path, dir)
          }
        }
      } else if ="$ ls" then {
        # ignore line                                           <6>
      } else if ="dir " then {
        dirname := tab(0)
        put(path[1].children, fileobject(dirname, 0, []))     # <7>
      } else { # assume is a file
        size := tab(many(&digits))
        =" "
        filename := tab(0)
        put(path[1].children, fileobject(filename, size, [])) # <8>
      }
    }
  }
  close(file)

  compute_sizes(root)

  return root
end

procedure compute_sizes(item)
  if *item.children > 0 then {
    item.size := 0
    every item.size +:= compute_sizes(!item.children)
  }

  return item.size
end

# generate the directories of file system
procedure directories(item)
  if *item.children = 0 then {
    fail
  } else {
    suspend item
    every suspend directories(!item.children)
  }
end

1. Create the root directory for the filesystem.
2. The path is a list, with the current directory as the first item.
3. "cd /" returns the path to the root directory.
4. "cd .." pops the current directory from the path.
5. "cd dirname" looks for the directory name in the current directory's children: if found that directory's definition is pushed onto the front of the path.
6. "ls" commands do nothing.
7. "dir dirname" defines a new directory, whose definition is added to the current directory's children.
8. "NNNN filename" defines a new file, whose definition is added to the current directory's children.