Advent of Code 2022, Dec 7<\/a> puzzle.<\/p>\nFor this puzzle, the input is a list of commands for walking through a file system. Each line either has a command like change directory (cd) or list directory (ls), or a directory name or file.<\/p>\n
The object of the puzzle is to identify folders on the drive that can be deleted to make room for a \u201csystem update\u201d file to fix the device. To do this, we need to identify the hierarchy of the filesystem by following the commands from beginning to end, identifying all the directories a file is a child of. Finally, the total size of files in each directory (inclusive of all children folders and files) needs to be calculated to find directories that can be deleted to create enough space for the update file to be loaded onto the device.<\/p>\n
While that probably sounds a bit complicated, we can break up the steps using a recursive CTE and slowly build our solution.<\/p>\n
Puzzle Input<\/h3>\n
The sample data, shown below, has 22 lines. Files are shown with the numerical size first followed by the name\u2014directories identified after a \u2018dir\u2019 keyword.<\/p>\n
$ cd \/\n$ ls\ndir a\n14848514 b.txt\n8504156 c.dat\ndir d\n$ cd a\n$ ls\ndir e\n29116 f\n2557 g\n62596 h.lst\n$ cd e\n$ ls\n584 i\n$ cd ..\n$ cd ..\n$ cd d\n$ ls\n4060174 j\n8033020 d.log\n5626152 d.ext\n7214296 k<\/pre>\nStep 1: <\/strong>Identify directories and files. Everything else is noise.<\/p>\nwith recursive commands as (\n select id,\n regexp_match(file_system, '\\$ cd (.*)') as dir,\n regexp_match(file_system,'([\\d]+) (.*)') as file \n from dec07\n)\nSELECT * FROM commands;<\/pre>\nThis returns:<\/p>\n
id|dir |file |\n--+----+----------------+\n 1|{\/} |NULL |\n 2|NULL|NULL |\n 3|NULL|NULL |\n 4|NULL|{14848514,b.txt}|\n 5|NULL|{8504156,c.dat} |\n 6|NULL|NULL |\n 7|{a} |NULL |\n 8|NULL|NULL |\n 9|NULL|NULL |\n10|NULL|{29116,f} |\n11|NULL|{2557,g} |\n12|NULL|{62596,h.lst} |\n13|{e} |NULL |\n14|NULL|NULL |\n15|NULL|{584,i} |\n16|{..}|NULL |\n17|{..}|NULL |\n18|{d} |NULL |\n19|NULL|NULL |\n20|NULL|{4060174,j} |\n21|NULL|{8033020,d.log} |\n22|NULL|{5626152,d.ext} |\n23|NULL|{7214296,k} |<\/pre>\nStep 2:<\/strong> Recursively step through the output of the first CTE, modifying the directory array as we go down or move up through the directories. Also, break out the file and size into separate columns. Note that we simply commented out the initial SELECT<\/code> statement and added a second (recursive) CTE.<\/p>\nwith recursive commands as (\n select id,\n regexp_match(file_system, '\\$ cd (.*)') as dir,\n regexp_match(file_system,'([\\d]+) (.*)') as file from dec07\n)\n--SELECT * FROM commands;\n,\nwalk_tree as (\n --Initial query, just static data to get started\n select 1::int id,\n '{}'::text[] as dir, \n null::text file,\n null::int fsize \n union all\n -- Check the first element of the directory array.\n-- \n-- If it is not \u2018..\u2019 and not NULL, append the directory \n-- to the array of directories.\n-- \n-- If it is \u2018..\u2019, remove the last element from the \n-- array because we moved up a directory.\n select c.id+1, \n case when c.dir[1] != '..' and c.dir is not null \n then wt.dir || c.dir[1]\n when c.dir[1] = '..' THEN \n-- remove the last element in the array\n trim_array(wt.dir,1)\n else wt.dir end dir,\n c.file[2], c.file[1]::int\n from commands c\n join walk_tree wt on c.id = wt.id\n)\nSELECT * FROM walk_tree;<\/pre>\nAnd this returns:<\/p>\n
id|dir |file |fsize |\n--+-------+-----+--------+\n 1|{} | | |\n 2|{\/} | | |\n 3|{\/} | | |\n 4|{\/} | | |\n 5|{\/} |b.txt|14848514|\n 6|{\/} |c.dat| 8504156|\n 7|{\/} | | |\n 8|{\/,a} | | |\n 9|{\/,a} | | |\n10|{\/,a} | | |\n11|{\/,a} |f | 29116|\n12|{\/,a} |g | 2557|\n13|{\/,a} |h.lst| 62596|\n14|{\/,a,e}| | |\n15|{\/,a,e}| | |\n16|{\/,a,e}|i | 584|\n17|{\/,a} | | |\n18|{\/} | | |\n19|{\/,d} | | |\n20|{\/,d} | | |\n21|{\/,d} |j | 4060174|\n22|{\/,d} |d.log| 8033020|\n23|{\/,d} |d.ext| 5626152|\n24|{\/,d} |k | 7214296|<\/pre>\nStep 3:<\/strong> Get a distinct set of values from the \u2018dir<\/code>\u2019 column and then sum the total size of each directory, all child files included.<\/p>\nwith recursive commands as (\n select id,\n regexp_match(file_system, '\\$ cd (.*)') as dir,\n regexp_match(file_system,'([\\d]+) (.*)') as file from dec07\n)\n--SELECT * FROM commands;\n,\nwalk_tree as (\n select 1::int id,\n '{}'::text[] as dir, \n null::text file,\n null::int fsize \n union all\n select c.id+1, \n case when c.dir[1] != '..' and c.dir is not null \n then wt.dir || c.dir[1]\n when c.dir[1] = '..' THEN \n trim_array(wt.dir,1)\n else wt.dir end dir,\n c.file[2], c.file[1]::int\n from commands c\n join walk_tree wt on c.id = wt.id\n)\n--SELECT * FROM walk_tree;\n,\npaths (dir) as (\n select distinct dir\n from walk_tree \n where CARDINALITY(dir) > 0\n)\n--SELECT dir, cardinality(dir) FROM paths;\n,\nsizes(dir, size) as (\n select p.dir, sum(fsize)\n from paths as p\n join walk_tree wt on wt.dir[:CARDINALITY(p.dir)] = p.dir\n group by p.dir\n)\nSELECT * FROM sizes;<\/pre>\nReturns:<\/p>\n
dir |size |\n-------+--------+\n{\/,a} | 94853|\n{\/} |48381165|\n{\/,d} |24933642|\n{\/,a,e}| 584|<\/pre>\nStep 4:<\/strong> Find all directories that are less than 100,000 in total size and add them up. These are the directories that will be deleted, and we want to know how much total space will be freed.<\/p>\nwith recursive commands as (\n select id,\n regexp_match(file_system, '\\$ cd (.*)') as dir,\n regexp_match(file_system,'([\\d]+) (.*)') as file from dec07\n)\n--SELECT * FROM commands;\n,\nwalk_tree as (\n select 1::int id,\n '{}'::text[] as dir, \n null::text file,\n null::int fsize \n union all\n select c.id+1, \n case when c.dir[1] != '..' and c.dir is not null \n then wt.dir || c.dir[1]\n when c.dir[1] = '..' THEN \n trim_array(wt.dir,1)\n else wt.dir end dir,\n c.file[2], c.file[1]::int\n from commands c\n join walk_tree wt on c.id = wt.id\n)\n--SELECT * FROM walk_tree;\n,\npaths (dir) as (\n select distinct dir\n from walk_tree \n where CARDINALITY(dir) > 0\n)\n--SELECT dir, cardinality(dir) FROM paths;\n,\nsizes(dir, size) as (\n select p.dir, sum(fsize)\n from paths as p\n join walk_tree wt on wt.dir[:CARDINALITY(p.dir)] = p.dir\n group by p.dir\n)\n--SELECT * FROM sizes;\nselect sum(size) as first_star\nfrom sizes\nwhere size < 100000;<\/pre>\nFinally returning<\/p>\n
space_freed|\n-----------+\n 95437|<\/pre>\nData transformation, building a query with CTE\u2019s, and a recursive CTE to build the filesystem structure.<\/p>\n
Conclusion<\/h2>\n
These three articles are just the tip of the iceberg for what is possible using SQL features and PostgreSQL functions. Transforming and analyzing data close to the database reduces dependencies on external tools and allows for easy modifications and updates as your process improves.<\/p>\n
I\u2019d recommend trying to solve puzzles from sites like the Advent of Code, and search for solutions that other SQL developers have posted to learn new tips and techniques. Each little step will improve your knowledge and hone your skills for working with data using SQL and PostgreSQL.<\/p>\n","protected":false},"excerpt":{"rendered":"
The first two articles in this series demonstrated how PostgreSQL is a capable tool for ELT – taking raw input and transforming it into usable data for querying and analyzing. We used sample data from the Advent of Code 2023 to demonstrate some of the ELT techniques in PostgreSQL. In the first article, we discussed……<\/p>\n","protected":false},"author":341037,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[53,143534],"tags":[158982,158978],"coauthors":[158981],"class_list":["post-101922","post","type-post","status-publish","format-standard","hentry","category-featured","category-postgresql","tag-planetpostgresqlryanbooz","tag-postgresql"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/101922","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/users\/341037"}],"replies":[{"embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/comments?post=101922"}],"version-history":[{"count":21,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/101922\/revisions"}],"predecessor-version":[{"id":109208,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/posts\/101922\/revisions\/109208"}],"wp:attachment":[{"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/media?parent=101922"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/categories?post=101922"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/tags?post=101922"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/www.red-gate.com\/simple-talk\/wp-json\/wp\/v2\/coauthors?post=101922"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"A](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2024\/04\/a-close-up-of-a-working-table-description-automat.png\")
<\/p>\n![\"A](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2024\/04\/a-table-with-black-text-description-automatically.png\")
<\/p>\n![\"A](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2024\/04\/a-white-sheet-of-paper-with-black-text-descriptio.png\")
<\/p>\n![\"\"](\"https:\/\/www.red-gate.com\/simple-talk\/wp-content\/uploads\/2024\/04\/Screenshot-2024-03-27-145109.png\")
<\/p>\n