Problem E: deltree
You have just run out of disk space and decided to delete some of your directories. Rationally, you will first have an
exploration of what you have in your file system. And more rationally, you will do this exploration through a command
line interface. The interface used in this problem is called “MSDOS–”, since it is something like MSDOS with fewer
features. The commands of MSDOS– are as follows:
cd <directory>
Assuming to be the name of a relative descendant of current directory, this command changes the
current directory to . For example, when the current directory is “\A\B\” and one of its
descendants is “C\D”, the execution of “cd C\D” will change the current directory to “\A\B\C\D\”.
cd \
This command changes the current directory to “\” (the root of the file system). For example, when the current
directory is “\A\B\”, the execution of “cd \” will change the current directory to “\”.
cd ..
Assuming the current directory to be anything except “\”, this command changes the current directory to its
parent directory. For example, when the current directory is “\A\B\”, the execution of “cd ..” will change
the current directory to “\A\”.
cd \<directory>
This command is equivalent to the execution of the following two commands:
cd \
cd <directory>
dir
This command lists the name of files and directories directly in the current directory, each on a separate line.
These file/directory names are made up of (lowercase and uppercase) letters, digits, and dots (“.”). Directory
names precede the file names in the list, and each one, comes alone in a single line. On the contrary, each file
name is accompanied by its size separated by a space. A sample output of “dir” is as follows:
HW1
HW1.old
Syllab.pdf 10000
notes.txt 3241
deltree <directory>
Assuming <directory> to be the name of a relative descendant of current directory, this command tries to
delete and all its descendant files and subdirectories (and thus, freeing that much of space). For
example, when the current directory is “\A\B\” and one of its descendants is “C\D”, the execution of
“deltree C\D” will try to delete directory “\A\B\C\D\” and all of its descendant files and directories.
deltree \<directory>
This command is equivalent to the execution of the following two commands:
cd \
deltree <directory>
exit
This command terminates the command line interface.
A “scenario” is an exploration (a consistent series of “cd” and “dir” commands and their results, starting from root)
followed by exactly one “deltree” command. Given a scenario, you are to find the maximum space guaranteed to be
freed by executing its “deltree” command.
Input (Standard Input)
Input contains multiple independent scenarios. There is an empty line after each scenario. The input ends with an
“exit” command. There is a “>” sign before each command in the input (with no spaces in between). The length of
each file name does not exceed 50. You may assume that the input is correct.
Output (Standard Output)
Write the result of the ith scenario as a single integer on the ith line of output.
Sample Input and Output
راه حل:
package acm2008.e;
import java.util.ArrayList;
import java.util.List;
import util.AcmUtil;
public class acm2008e {
public static void main(String[] args) {
String input = "E:\\acm\\2008\\TD87\\E.in";
String output = "E:\\acm\\2008\\TD87\\E.out";
String myOutput = "E:\\acm\\2008\\TD87\\E-my.out";
List<String> outputList = new ArrayList<String>();
List<String> fileContent = AcmUtil.readFromFile(input);
CMD cmd = new CMD();
while (!isEndExit(fileContent.get(cmd.lineNum))) {
cmd.currentId = 1l;
cmd.maxId = 1l;
cmd.folderDataList = new ArrayList<FolderData>();
FolderData root = new FolderData(cmd.maxId++, 0, "root", 0);
cmd.folderDataList.add(root);
while (!isEndExit(fileContent.get(cmd.lineNum))) {
String currentLine = fileContent.get(cmd.lineNum);
if (currentLine.startsWith(">cd ")) {
cmd.process_cd(currentLine);
} else if (currentLine.startsWith(">dir")) {
cmd.process_dir(fileContent, currentLine);
} else if (currentLine.startsWith(">deltree ")) {
FolderData folderData = cmd.process_deltree(currentLine);
outputList.add("" + cmd.getTotalSize(folderData));
//System.out.println(cmd.getTotalSize(folderData));
} else if (isEnd(currentLine)) {
cmd.lineNum++;
break;
}
}
}
AcmUtil.writeToFile(outputList, myOutput);
System.out.println(AcmUtil.diffFile(output, myOutput));
}
public static boolean isEndExit(String currentLine) {
if (currentLine.equals(">exit"))
return true;
return false;
}
public static boolean isEnd(String currentLine) {
if (currentLine.equals("") || currentLine.equals(">exit"))
return true;
return false;
}
}
package acm2008.e;
import java.util.ArrayList;
import java.util.List;
public class CMD {
public int lineNum = 0;
public long currentId = 1l;
public long maxId = 1l;
public List<FolderData> folderDataList = new ArrayList<FolderData>();
public CMD() {
lineNum = 0;
currentId = 1l;
maxId = 1l;
}
public void process_cd(String currentLine) {
String currentLineTemp = currentLine;
String folderName = currentLineTemp = currentLineTemp.replace(">cd ", "");
FolderData folder = null;
if (folderName.equals("..")) {
folder = findById(folderDataList, currentId);
folder = findById(folderDataList, folder.parentId);
} else if (folderName.equals("\\")) {
folder = findById(folderDataList, 1);
} else if (folderName.contains("\\")) {
if (folderName.startsWith("\\"))
currentId = 1;
String[] folders = folderName.split("\\\\");
for (String myFolder : folders) {
if (!myFolder.equals(""))
folder = createFolder(myFolder, folder == null ? currentId : folder.id);
}
} else {
folder = createFolder(folderName, currentId);
}
currentId = folder.id;
lineNum += 1;
}
private FolderData createFolder(String folderName, long parentId) {
FolderData folder = findNodeDataId(folderName, parentId);
if (folder == null) {
folder = new FolderData(maxId, parentId, folderName, 0);
folderDataList.add(folder);
maxId++;
}
return folder;
}
public void process_dir(List<String> fileContent, String currentLine) {
lineNum++;
int size = 0;
while (!fileContent.get(lineNum).startsWith(">")) {
currentLine = fileContent.get(lineNum);
if (!currentLine.startsWith(">")) {
if (!currentLine.contains(" ")) {
String name = currentLine;
if (findNodeDataId(name, currentId) == null) {
FolderData nodeData = new FolderData(maxId, currentId, name, 0);
folderDataList.add(nodeData);
}
} else {
String nodeSize = currentLine.split(" ")[1];
size += Double.parseDouble(nodeSize);
}
lineNum++;
maxId++;
for (FolderData folderData : folderDataList) {
if (folderData.id == currentId)
folderData.size = size;
}
} else {
break;
}
}
}
public FolderData process_deltree(String currentLine) {
lineNum++;
String folderName = getFolderName_delTree(currentLine);
FolderData folder = findNodeDataId(folderName, currentId);
return folder;
}
public FolderData findNodeDataId(String name, long parentId) {
for (FolderData nodeData : folderDataList) {
if (nodeData.name.equals(name) && nodeData.parentId == parentId)
return nodeData;
}
return null;
}
public List<FolderData> findByParentId(long parentId) {
List<FolderData> result = new ArrayList<FolderData>();
for (FolderData folderData : folderDataList) {
if (folderData.parentId == parentId)
result.add(folderData);
}
return result;
}
public FolderData findById(List<FolderData> folderDataList, long id) {
for (FolderData folderData : folderDataList) {
if (folderData.id == id)
return folderData;
}
return null;
}
public int getTotalSize(FolderData folderData) {
int size = folderData.size;
List<FolderData> childeren = findByParentId(folderData.id);
if (childeren != null && childeren.size() > 0) {
for (FolderData child : childeren) {
size += getTotalSize(child);
}
}
return size;
}
public String getFolderName_delTree(String currentLine) {
String folderName = currentLine.replace(">deltree ", "");
if (folderName.startsWith("\\"))
currentId = 1;
if (folderName.substring(1).contains("\\")) {
String[] folders = folderName.split("\\\\");
FolderData folder = null;
for (String myFolder : folders) {
if (!myFolder.equals(""))
folder = createFolder(myFolder, folder == null ? currentId : folder.id);
}
folderName = folder.name;
currentId = folder.parentId;
} else {
folderName = folderName.replace("\\", "");
}
return folderName;
}
}
package acm2008.e;
public class FolderData {
public long id;
public long parentId;
public String name;
public int size;
public FolderData() {}
public FolderData(long id, long parentId, String name, int size) {
this.id = id;
this.parentId = parentId;
this.name = name;
this.size = size;
}
}
