14
\$\begingroup\$

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

Improve this question
\$\endgroup\$
1
  • 10
    \$\begingroup\$ Not sure why this has JSON in the title, but "The paths must be in the same order of the input." conflicts with "JSON" as the members of a JSON object are inherently unordered, as are dictionaries and associative arrays — at least in principle. \$\endgroup\$ Commented May 3, 2022 at 14:42

12 Answers 12

Reset to default
4
\$\begingroup\$

Perl 5, 67 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ select(.[1]=={})[0] saves 2 bytes. And it seems like select(.[1])[0] works, as only leafs have 2 elements. \$\endgroup\$ Commented May 5, 2022 at 9:22
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ The ~ isn't needed \$\endgroup\$ Commented May 3, 2022 at 14:36
  • \$\begingroup\$ 57 bytes: Try it online! \$\endgroup\$ Commented May 3, 2022 at 14:41
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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).

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Why the lapply? :) Try it online! \$\endgroup\$ Commented May 6, 2022 at 10:23
  • \$\begingroup\$ @pajonk I was so incredibly proud I remembered to use Map instead of mapply, too... \$\endgroup\$ Commented May 6, 2022 at 13:44
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ nice! The cmdlet ConvertFrom-Json' with the paramater -asHashtable' will allow you to use $o.Keys instead Get-Members and member names. \$\endgroup\$ Commented May 11, 2022 at 4:47
  • 1
    \$\begingroup\$ Try it online!? \$\endgroup\$ Commented May 11, 2022 at 18:04
  • 1
    \$\begingroup\$ I thought the get-member was the crux to make it shorter :) Nice one! \$\endgroup\$ Commented May 11, 2022 at 21:17
1
\$\begingroup\$

Pip -xp, 23 21 bytes

FL:_.{b?'/.(\fb)x}MUa

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

Try It Online!

Explanation

A recursive full program:

FL:_.{b?'/.(\fb)x}MUa a Program argument (a list of pairs) MU Unpack and map this function to each pair: _ The first element of the pair .{ } Concatenated (itemwise if necessary) to: b? Is the second element of the pair (a list) nonempty? '/. If so, concatenate "/" (itemwise) to (\f ) a recursive call of the main function b with the second element of the pair as the argument x If it is empty, empty string FL: Flatten the resulting list
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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) }
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

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

ran with parsrj.sh and sed

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
Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.