Draw a folder tree from n file paths.
A path is a list of names separated by /. The last name is a file, and the names before it are folders, going from outside to inside.
For example, src/app/main.py is the file main.py inside the folder app inside the folder src. Paths starting with the same folder names refer to the same folders.
The first line is just ., meaning the top folder.
Below it, write the things inside a folder with folders first and files after. Folders among themselves, and files among themselves, are in character-code (ASCII) order of their names. If one name is the beginning of another, the shorter name comes first. After writing a folder's line, write everything inside that folder right below it by the same rules before moving on to the next thing.
A line is the string made of a prefix, a connector and a name, in that order.
The connector is \-- (a backslash, two minus signs and a space) if it is the last thing written inside its folder, and |-- otherwise.
Things directly inside the top folder have the empty string as prefix.
If a folder's line has prefix P, the things inside that folder have prefix P followed by four spaces if that folder was last, and P followed by | and three spaces otherwise.
A folder name is followed by /.
If a folder other than the top folder contains no files and exactly one folder, write the two on one line as outer/inner/. If the inner folder is like that too, keep joining. Then write the things inside the last joined folder below this line.
A folder that contains only a single file is not joined. The top folder . is never joined either.
The order of a joined line, and whether it is last, are decided by the name of its outermost folder.
The first line gives n, and the next n lines give one path each.
Input
1 ≤ n ≤ 500. Each path is 1 to 40 characters long and has 1 to 10 names. Names consist only of lowercase English letters, digits, ., - and _, are not empty, and are not . or ... Paths are distinct, and a file in one path is never used as a folder in another path.
Output
The lines of the tree drawing (the first line is .)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
This problem builds each line as prefix + connector + name and joins the lines. The prefix is passed to a recursive function as a string and grows by four characters per level: Python, JS and TS build a new string with prefix + "| " and pass it on; Java and C# collect the lines in a StringBuilder and print once (thousands of string += copy the string each time). C keeps one char prefix[64], appends four characters with memcpy, and cuts back with prefix[plen] = '\0' when it returns. Craykon passes a new string prefix + more, collects the lines in a list and writes them once with lines.Join("\n"). Inside a string literal the backslash must be written twice, as in "\\-- ". Sorting by character code: Python sorted, JS/TS the default sort() (UTF-16 code order), Java TreeMap and Collections.sort, C# StringComparer.Ordinal (the default comparison may follow culture rules), C strcmp, C++ std::map and std::sort, Craykon Sort(). JS localeCompare uses human dictionary order, so -, . and _ land in different places. Five traps: (1) Drawing | below the last folder too makes a finished line keep running down; whether the folder was last must be carried in the prefix. (2) Not joining a folder that holds only one folder, or (3) also joining a folder that holds only one file, is wrong. (4) The top . is never joined. (5) Sorting folders and files together by name only puts the z/ folder after the a file.
Pythonmain.py · 43 lines
import sysclass Folder: def __init__(self): self.folders: dict[str, "Folder"] = {} self.files: list[str] = []def draw(folder, prefix, out): entries = [(name, True) for name in sorted(folder.folders)] + [(name, False) for name in sorted(folder.files)] for i, (name, is_folder) in enumerate(entries): last = i == len(entries) - 1 mark = "\\-- " if last else "|-- " if not is_folder: out.append(prefix + mark + name) continue label, inner = name, folder.folders[name] # 든 것이 폴더 하나뿐이면 한 줄에 이어 쓴다 while len(inner.folders) == 1 and not inner.files: (child, sub), = inner.folders.items() label += "/" + child inner = sub out.append(prefix + mark + label + "/") draw(inner, prefix + (" " if last else "| "), out)def main(): lines = sys.stdin.read().split("\n") n = int(lines[0]) root = Folder() for path in lines[1:1 + n]: parts = path.strip().split("/") cur = root for name in parts[:-1]: cur = cur.folders.setdefault(name, Folder()) cur.files.append(parts[-1]) out = ["."] draw(root, "", out) print("\n".join(out))main()
JavaScriptmain.js · 37 lines
const lines = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const newFolder = () => ({ folders: new Map(), files: [] });const root = newFolder();for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split("/"); let cur = root; for (const name of parts.slice(0, -1)) { if (!cur.folders.has(name)) cur.folders.set(name, newFolder()); cur = cur.folders.get(name); } cur.files.push(parts[parts.length - 1]);}const out = ["."];// 기본 sort()는 문자열을 UTF-16 코드 순으로 늘어놓는다(ASCII 이름이면 글자 코드 순)function draw(folder, prefix) { const entries = [...[...folder.folders.keys()].sort().map((name) => [name, true]), ...[...folder.files].sort().map((name) => [name, false])]; entries.forEach(([name, isFolder], i) => { const last = i === entries.length - 1; const mark = last ? "\\-- " : "|-- "; if (!isFolder) { out.push(prefix + mark + name); return; } let label = name; let inner = folder.folders.get(name); while (inner.folders.size === 1 && inner.files.length === 0) { const [child, sub] = [...inner.folders][0]; label += "/" + child; inner = sub; } out.push(prefix + mark + label + "/"); draw(inner, prefix + (last ? " " : "| ")); });}draw(root, "");console.log(out.join("\n"));
TypeScriptmain.ts · 48 lines
interface Folder { folders: Map<string, Folder>; files: string[];}const lines: string[] = require("fs").readFileSync(0, "utf8").split("\n");const n = Number(lines[0]);const newFolder = (): Folder => ({ folders: new Map(), files: [] });const root = newFolder();for (let i = 1; i <= n; i++) { const parts = lines[i].trim().split("/"); let cur = root; for (const name of parts.slice(0, -1)) { let next = cur.folders.get(name); if (next === undefined) { next = newFolder(); cur.folders.set(name, next); } cur = next; } cur.files.push(parts[parts.length - 1]);}const out: string[] = ["."];function draw(folder: Folder, prefix: string): void { const entries: [string, boolean][] = [ ...[...folder.folders.keys()].sort().map((name): [string, boolean] => [name, true]), ...[...folder.files].sort().map((name): [string, boolean] => [name, false]), ]; entries.forEach(([name, isFolder], i) => { const last = i === entries.length - 1; const mark = last ? "\\-- " : "|-- "; if (!isFolder) { out.push(prefix + mark + name); return; } let label = name; let inner = folder.folders.get(name)!; while (inner.folders.size === 1 && inner.files.length === 0) { const [child, sub] = [...inner.folders][0]; label += "/" + child; inner = sub; } out.push(prefix + mark + label + "/"); draw(inner, prefix + (last ? " " : "| ")); });}draw(root, "");console.log(out.join("\n"));
JavaMain.java · 50 lines
import java.io.*;import java.util.*;public class Main { static class Folder { // TreeMap은 열쇠를 compareTo 순(ASCII 이름이면 글자 코드 순)으로 들고 있다 final TreeMap<String, Folder> folders = new TreeMap<>(); final List<String> files = new ArrayList<>(); } static final StringBuilder out = new StringBuilder(); static void draw(Folder folder, String prefix) { List<String> files = new ArrayList<>(folder.files); Collections.sort(files); int total = folder.folders.size() + files.size(); int i = 0; for (Map.Entry<String, Folder> e : folder.folders.entrySet()) { boolean last = ++i == total; StringBuilder label = new StringBuilder(e.getKey()); Folder inner = e.getValue(); while (inner.folders.size() == 1 && inner.files.isEmpty()) { Map.Entry<String, Folder> only = inner.folders.firstEntry(); label.append('/').append(only.getKey()); inner = only.getValue(); } out.append(prefix).append(last ? "\\-- " : "|-- ").append(label).append("/\n"); draw(inner, prefix + (last ? " " : "| ")); } for (String name : files) { boolean last = ++i == total; out.append(prefix).append(last ? "\\-- " : "|-- ").append(name).append('\n'); } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); Folder root = new Folder(); for (int k = 0; k < n; k++) { String[] parts = br.readLine().trim().split("/"); Folder cur = root; for (int j = 0; j < parts.length - 1; j++) cur = cur.folders.computeIfAbsent(parts[j], x -> new Folder()); cur.files.add(parts[parts.length - 1]); } out.append(".\n"); draw(root, ""); System.out.print(out); }}
C#Main.cs · 68 lines
using System;using System.Collections.Generic;using System.Text;class Folder{ // 문자열 비교는 문화권 규칙이 아니라 글자 코드 순(Ordinal)으로 public SortedDictionary<string, Folder> Folders = new SortedDictionary<string, Folder>(StringComparer.Ordinal); public List<string> Files = new List<string>();}class Program{ static readonly StringBuilder Out = new StringBuilder(); static void Draw(Folder folder, string prefix) { var files = new List<string>(folder.Files); files.Sort(StringComparer.Ordinal); int total = folder.Folders.Count + files.Count; int i = 0; foreach (var e in folder.Folders) { bool last = ++i == total; var label = new StringBuilder(e.Key); Folder inner = e.Value; while (inner.Folders.Count == 1 && inner.Files.Count == 0) { foreach (var only in inner.Folders) { label.Append('/').Append(only.Key); inner = only.Value; } } Out.Append(prefix).Append(last ? "\\-- " : "|-- ").Append(label).Append("/\n"); Draw(inner, prefix + (last ? " " : "| ")); } foreach (var name in files) { bool last = ++i == total; Out.Append(prefix).Append(last ? "\\-- " : "|-- ").Append(name).Append('\n'); } } static void Main() { int n = int.Parse(Console.ReadLine().Trim()); var root = new Folder(); for (int k = 0; k < n; k++) { string[] parts = Console.ReadLine().Trim().Split('/'); Folder cur = root; for (int j = 0; j < parts.Length - 1; j++) { if (!cur.Folders.TryGetValue(parts[j], out Folder next)) { next = new Folder(); cur.Folders[parts[j]] = next; } cur = next; } cur.Files.Add(parts[parts.Length - 1]); } Out.Append(".\n"); Draw(root, ""); Console.Write(Out); }}
C++main.cpp · 64 lines
#include <algorithm>#include <iostream>#include <map>#include <sstream>#include <string>#include <vector>struct Folder { std::map<std::string, int> folders; // 이름 → folders 목록의 자리. map은 이름을 글자 코드 순으로 들고 있다 std::vector<std::string> files;};std::vector<Folder> all(1); // 0번이 맨 위 폴더std::string out;void draw(int v, const std::string &prefix) { std::vector<std::string> files = all[v].files; std::sort(files.begin(), files.end()); size_t total = all[v].folders.size() + files.size(), i = 0; for (const auto &[name, at] : all[v].folders) { bool last = ++i == total; std::string label = name; int inner = at; while (all[inner].folders.size() == 1 && all[inner].files.empty()) { const auto &only = *all[inner].folders.begin(); label += "/" + only.first; inner = only.second; } out += prefix + (last ? "\\-- " : "|-- ") + label + "/\n"; draw(inner, prefix + (last ? " " : "| ")); } for (const auto &name : files) { bool last = ++i == total; out += prefix + (last ? "\\-- " : "|-- ") + name + "\n"; }}int main() { int n; std::cin >> n; for (int i = 0; i < n; i++) { std::string path, part; std::cin >> path; std::vector<std::string> parts; std::stringstream ss(path); while (std::getline(ss, part, '/')) parts.push_back(part); int cur = 0; for (size_t j = 0; j + 1 < parts.size(); j++) { auto it = all[cur].folders.find(parts[j]); if (it == all[cur].folders.end()) { all.emplace_back(); // 여기서 all이 옮겨질 수 있으니 참조를 쥐지 않고 자리 번호로 다룬다 all[cur].folders[parts[j]] = (int)all.size() - 1; cur = (int)all.size() - 1; } else { cur = it->second; } } all[cur].files.push_back(parts.back()); } out = ".\n"; draw(0, ""); std::cout << out; return 0;}
Cmain.c · 83 lines
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXNODE 5001typedef struct { char name[41]; int is_folder; int first, next; /* 첫 아이와 다음 형제(없으면 -1) */ int kids; /* 든 것의 수 */} Node;static Node nodes[MAXNODE];static int count = 1; /* 0번은 맨 위 폴더 */static char prefix[64]; /* 앞머리: 깊이마다 네 글자씩 붙였다가 떼어 낸다 */static int child(int parent, const char *name, int is_folder) { for (int c = nodes[parent].first; c >= 0; c = nodes[c].next) if (strcmp(nodes[c].name, name) == 0) return c; Node *nd = &nodes[count]; strcpy(nd->name, name); nd->is_folder = is_folder; nd->first = -1; nd->kids = 0; nd->next = nodes[parent].first; nodes[parent].first = count; nodes[parent].kids++; return count++;}/* 폴더가 먼저, 같은 종류끼리는 글자 코드 순(strcmp) */static int by_kind_then_name(const void *pa, const void *pb) { const Node *a = &nodes[*(const int *)pa], *b = &nodes[*(const int *)pb]; if (a->is_folder != b->is_folder) return b->is_folder - a->is_folder; return strcmp(a->name, b->name);}static void draw(int v, size_t plen) { int k = nodes[v].kids, i = 0; int *list = malloc(sizeof(int) * (size_t)k); for (int c = nodes[v].first; c >= 0; c = nodes[c].next) list[i++] = c; qsort(list, (size_t)k, sizeof(int), by_kind_then_name); for (i = 0; i < k; i++) { int c = list[i], last = i == k - 1; prefix[plen] = '\0'; printf("%s%s%s", prefix, last ? "\\-- " : "|-- ", nodes[c].name); if (!nodes[c].is_folder) { printf("\n"); continue; } while (nodes[c].kids == 1 && nodes[nodes[c].first].is_folder) { c = nodes[c].first; printf("/%s", nodes[c].name); } printf("/\n"); memcpy(prefix + plen, last ? " " : "| ", 5); /* 끝의 '\0'까지 */ draw(c, plen + 4); } free(list);}int main(void) { int n; char line[64]; nodes[0].first = -1; nodes[0].kids = 0; nodes[0].is_folder = 1; scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%63s", line); int cur = 0; char *part = line; for (char *slash; (slash = strchr(part, '/')) != NULL; part = slash + 1) { *slash = '\0'; cur = child(cur, part, 1); } child(cur, part, 0); } printf(".\n"); draw(0, 0); return 0;}
Craykonmain.cray · 71 lines
// 폴더 하나를 사전 하나로: "folders"(이름 → 폴더 사전)와 "files"(파일 이름 목록)새폴더(){ f = Dict(); f["folders"] = Dict(); f["files"] = []; return f;}lines = [];// 그리기: 폴더 안의 것을 앞머리 prefix를 붙여 한 줄씩 lines에 넣는다그리기(folder, prefix){ dirs = folder["folders"].Keys; dirs.Sort(); // 문자열은 글자 코드 순 files = folder["files"].GetRange(0, folder["files"].Count); files.Sort(); total = dirs.Count + files.Count; for (i = 0; i < dirs.Count; i++) { last = i == total - 1; mark = "|-- "; more = "| "; if (last) { mark = "\\-- "; more = " "; } label = dirs[i]; inner = folder["folders"][dirs[i]]; // 든 것이 폴더 하나뿐이면 한 줄에 이어 쓴다 while (inner["folders"].Count == 1 && inner["files"].Count == 0) { only = inner["folders"].Keys[0]; label = label + "/" + only; inner = inner["folders"][only]; } lines.Add(prefix + mark + label + "/"); 그리기(inner, prefix + more); } for (j = 0; j < files.Count; j++) { mark = "|-- "; if (dirs.Count + j == total - 1) { mark = "\\-- "; } lines.Add(prefix + mark + files[j]); }}n = Console.ReadLine().Trim().ToNumber();root = 새폴더();for (k = 0; k < n; k++){ parts = Console.ReadLine().Trim().Split("/"); cur = root; for (j = 0; j < parts.Count - 1; j++) { if (!cur["folders"].Contains(parts[j])) { cur["folders"][parts[j]] = 새폴더(); } cur = cur["folders"][parts[j]]; } cur["files"].Add(parts[parts.Count - 1]);}lines.Add(".");그리기(root, "");Console.WriteLine(lines.Join("\n"));