Convert JSON object of directories to list of paths

Question

Task

The input consists of a JSON object, where every value is an object (eventually empty), representing a directory structure. The output must be a list of the corresponding root-to-leaf paths.

Inspired by this comment on StackOverflow.

Input specifications

• You can assume that that the input always contains a JSON object.
• The input can be a empty JSON object ({}); in this case the output must be a empty list.
• You can assume that the names/keys contain only printable ASCII characters, and they do not contain \0, \, /, ", ', nor `.
• You can assume each JSON object does not contain duplicate names/keys.

Input format

The input can be:

• a string;
• a dictionary or an associative array in a language of your choice;
• a list or array of tuples, where each tuples contains the name/key and the value (which is itself a list of tuples).

Output specifications

• There is no need to escape any character.
• You can use as directory separator either / or \, but you cannot have a mixed use of both (e.g. a/b/c and a\b\c are both valid, but a/b\c and a\b/c are not).
• Each path can have a leading and/or trailing directory separator (e.g. a/b, /a/b, a/b/, and /a/b/ are equally valid).
• If you output a newline-separated list, the output can have a trailing newline.
• The paths must be in the same order of the input.

Test cases

Input 1:

{
    "animal": {
        "cat": {"Persian": {}, "British_Shorthair": {}},
        "dog": {"Pug": {}, "Pitbull": {}}
    },
    "vehicle": {
        "car": {"Mercedes": {}, "BMW": {}}
    }
}

Output 1:

animal/cat/Persian
animal/cat/British_Shorthair
animal/dog/Pug
animal/dog/Pitbull
vehicle/car/Mercedes
vehicle/car/BMW

Input 2

{
    "bin": {
        "ls": {}
    },
    "home": {},
    "usr": {
        "bin": {
            "ls": {}
        },
        "include": {
            "sys": {}
        },
        "share": {}
    }
}

Output 2:

/bin/ls
/home
/usr/bin/ls
/usr/include/sys
/usr/share

Sandbox: https://codegolf.meta.stackexchange.com/a/24594/73593

Answer 1

jq, 42 40 bytes (+11 penalty for "-r --stream" options)

select(.[1]=={})[0]|join("/")

Try it online!

The --stream option converts JSON to an alternate format where each leaf node is an element in a list. Those entries are also lists, with two fields, the first of which is a list of the keys representing the path. The second entry (for out test cases) is an empty dictionary.

So the code selects every list entry where the second entry is a an empty dictionary, them assembles the list of keys in the first entry into the output we want.

select(.[1]=={})[0]            - pick "leaf" node entries only (1st field only)
                   |join("/")  - join the list of string w/ a "/" separator

Answer 2

JavaScript (V8), 55 bytes

Thanks to @pxeger for suggesting to use for(k in o)

Expects an object. Prints the results with a leading /.

f=(o,p,q)=>{for(k in o)f(o[q=k],[p]+'/'+k);q||print(p)}

Try it online!

---

JavaScript (V8), 63 bytes

Expects an object. Prints the results with a leading /.

f=(o,p)=>Object.keys(o).map(k=>f(o[k],[p]+'/'+k))+''||~print(p)

Try it online!

Answer 3

Perl 5, 67 bytes

map/}/?/{/&&say($s)..$s=~s|[^/]+/$||:($s.=s/"//gr."/"),/{?}|".+?"/g

Try it online!

Answer 4

Python, 52 bytes

def f(d,s=""):[f(d[x],s+"/"+x)for x in d]or print(s)

Attempt This Online!

Takes input as a dictionary, and outputs to STDOUT.

Answer 5

Jelly, 14 bytes

;”/;ⱮßW⁹?}ʋ/€Ẏ

A monadic Link that accepts a list of lists where each is a key-value pair where the key is a list of characters and the value is a, possibly empty, list of the same type* and yields a list of lists of characters - the paths.

* i.e. uses the option a list or array of tuples, where each tuples contains the name/key and the value (which is itself a list of tuples).

Try it online!

How?

;”/;ⱮßW⁹?}ʋ/€Ẏ - (recursive) Link: list, J
            €  - for each key-value pair in J:
           /   -   reduce by:
          ʋ    -     last four links as a dyad - f(Key, Value)
 ”/            -       '/' character
;              -       (Key) concatenate ('/')
         }     -     use right argument, Value with:
        ?      -       if...
       ⁹       -       ...condition: chain's right argument, Value
     ß         -       ...then: call this recursive Link with that (non-empty) Value
      W        -       ...else: wrap that (empty) Value in a list -> [[]]
    Ɱ          -     map across the recursive call result (or the [[]]) with:
   ;           -       concatenate
             Ẏ - tighten

Answer 6

Perl 5 + -M5.10.0 -n0175, 36 bytes

pop@;;push@;,/\w+/g;$,="/";/{/&&say@

Try it online!

Explanation

A different approach to the other Perl answer. This uses the -0175 command line flag to split the input on }. For each closing curly brace, @; is popped removing any previous path keys that aren't needed. Next all the keys (/\w+/g - this might be too lenient?) are pushed onto @;. Finally $, (which is printed between records when a list - @... - is printed) is set to "/" and if { exists in the input, say is used to output @; (with $, printed between each index).

Answer 7

Retina 0.8.2, 96 bytes

+1`"([^"]+)":{("[^"]+":{(({)|(?<-4>})|[^{}])*(?(4)^)},)*"(?!\1/)
$&$1/
M!`"[^"]+":{}
%`^.|....$

Try it online! Link includes test cases. Explanation:

+1`"([^"]+)":{("[^"]+":{(({)|(?<-4>})|[^{}])*(?(4)^)},)*"(?!\1/)
$&$1/

Replace each key in turn with its path.

M!`"[^"]+":{}

List the entries whose values are empty objects.

%`^.|....$

Keep just the keys.

Answer 8

R, 79 73 bytes

f=function(L)"if"(length(L),unlist(Map(paste0,names(L),"/",Map(f,L))),"")

Try it online!

Takes input as a named R list, i.e., list(name=value), and returns a character (string) vector of directories.

-3 bytes thanks to pajonk.

Answer 9

PowerShell Core, 103 88 bytes

function f($o,$p){($x=$o.keys|%{f $o.$_ $p/$_})
if(!$x){$p}}f($args|ConvertFrom-Json -a)

Try it online!

Takes a string as a parameter
Returns a list of string with a leading /

Thanks mazzy for shaving 15 bytes off!

Answer 10

Kotlin 1.6.21, 118 bytes

{fun f(m:Map<*,*>,s:(Any?)->Any){for((k,v)in m)if((v as Map<*,*>).size==0)s(k)else f(v){s("$k/$it")}};f(it,::println)}

Try it online!

An anonymous function of type (Map<*, *>) -> Unit that takes in a recursive map of String to Map<String, ...> and prints the answer without leading or trailing slashes.

Ungolfed code:

{
    // Define function f that iterates a map recursively and
    // outputs its keys' paths to a sink function
    fun f(m: Map<*, *>, s: (Any?) -> Any) {
        for ((k, v) in m)
            // Note: .size==0 is 2 bytes shorter than .isEmpty()
            if ((v as Map<*,*>).size == 0)
                // For an empty map, call the sink with the key
                s(k)
            else
                // Call f again on the inner map with a wrapped sink that
                // that appends the current key + "/" to the input
                f(v) { s("$k/$it") }
    }

    // Run f for the input map, using ::println as the sink
    f(it, ::println)
}

Answer 11

Pip 1.1.0-alpha -xp, 23 bytes

@_.{a@1?'/.(\fa@1)x}MFa

Takes a list of tuples (i.e. two-element lists) as a command-line argument. Outputs a list of strings.

Pip 1.1 (required for both \f and MF) is not on Attempt This Online at the time of writing, but you can try it on Replit. The easiest way is to exit out of the Pip REPL with ;quit and then:

> ./pip.py -xpe "@_.{a@1?'/.(\fa@1)x}MFa" '[["bin"; [["ls"; []]]]; ["home"; []]; ["usr"; [["bin"; [["ls"; []]]]; ["include"; [["sys"; []]]]; ["share"; []]]]]'
["bin/ls";"home";"usr/bin/ls";"usr/include/sys";"usr/share"]

Explanation

A recursive full program:

@_.{a@1?'/.(\fa@1)x}MFa
                      a  Program argument (a list of pairs)
                    MF   Map this function to each and flatten the results:
@_                         The first element of the pair
  .{               }       Concatenated (itemwise if necessary) to:
    a@1?                   Is the second element of the pair (a list) nonempty?
        '/.                If so, concatenate / (itemwise) to
           (\f   )         a recursive call of the main function
              a@1          with the second element of the pair as the argument
                  x        If it is empty, empty string

Answer 12

Bash (sed + ShellShoccar-jpn/Parsrs parsrj.sh), 31 29 bytes

Assumes parsrj.sh is on a directory specified by PATH environment variable. Tested with parsrj.sh Version : 2020-05-06 22:42:19 JST.

parsrj.sh -rt -kd/|sed s,/$,,

Example runs on my Termux

Explained

parsrj.sh -rt -kd/|
# default output for {"foo":{"bar":{}},"baz":{}}:
#   $.foo.bar.
#   $.baz.
# -rt to replace $ with ""
# -kd/ to replace . with /
# thus output is:
#   /foo/bar/
#   /baz/
sed s,/$,,
# trailing slash is removed