8
\$\begingroup\$

The Monkey has swung home to find his tree all in pieces.

He likes order and scoops up all his 'tree-parts' and sets them out in 3 groups.

The Monkey's 3 nested lists:

STEP = [['S', '1', 'B', '3'], ['S', '3', 'B', '11'], ['S', '5', 'B', '12'], ['S', '4', 'B', '13'], ['S', '2', 'B', '14']]

TRANSITION = [['T', '2', 'B', '4'], ['T', '7', 'B', '4'], ['T', '3', 'S', '4'], ['T', '5', 'S', '5'], ['T', '1', 'S', '2'], ['T', '8', 'S', '2'], ['T', '6', 'S', '1'], ['T', '9', 'S', '2'], ['T', '4', 'S', '1'], ['T', '10', 'S', '1']]

BRANCH = [['B', '3', 'T', '1'], ['B', '3', 'T', '7'], ['B', '4', 'S', '3'], ['B', '11', 'T', '3'], ['B', '11', 'T', '5'], ['B', '12', 'T', '6'], ['B', '12', 'T', '8'], ['B', '13', 'T', '4'], ['B', '13', 'T', '9'], ['B', '14', 'T', '2'], ['B', '14', 'T', '10']]

Each element holds information as such:

# Example

STEP[0]  =  ['S', '1', 'B', '3']

Where:

  • 'S' is the STEP type
  • '1' is the STEP number id
  • 'B' is the linked BRANCH type
  • '3' is the linked BRANCH number id

Starting from a STEP the data is all linked, so using the linked reference you can find the next element and the next until another STEP is reached.

This is some parameters of the data:

  • STEPS are connected to single BRANCHES
  • BRANCHES are connected to one or more TRANSITIONS
  • TRANSITIONS can be connected to a single BRANCH or STEP

The BRANCH data can have a fork where a single BRANCH id has one or more options for TRANSITIONS.

Re-create this monkey's tree (nested list format is fine) in the shortest way possible (he is not a fan of long instructions):

           [S1]
            |          
          B3|_________ 
            |         |
           [T1]     [T7]
            |         |
            |       B4|
            |         |
           [S2]     [S3]

And list all the routes on this tree:

Routes = [[S1, B3, T1, S2], [S1, B3, T7, B4, S3]]

UPDATE: This is Code-golf and from the data given you need to output the display of the tree ( This can be different from my example but requires the same elements to be displayed in any format) and as you cycle through the problem to output all the possible routes as a BONUS.

Notes:

  • This is a single-rooted tree
  • You may use a different format for input but please explicitly state the input format in your solution
\$\endgroup\$
  • \$\begingroup\$ Pretty new here, still getting the etiquette down. Yes Code-golf and from the data given you need to output the display of the tree ( This can be different from my example but requires the same elements to be displayed in any format) and as you cycle through the problem to output all the possible routes as a BONUS. \$\endgroup\$ – leopardxpreload Feb 28 at 4:48
  • 1
    \$\begingroup\$ Welcome to Code Golf! What are acceptable outputs for the tree? Can it just be nested lists? Or does it need to be some ascii-art? (in which case this tag should be added and the format should be specified some more) \$\endgroup\$ – Arnauld Feb 28 at 14:43
  • \$\begingroup\$ @arnauld - thank you! It can just be nested lists - okay, fantastic Ill update that \$\endgroup\$ – leopardxpreload Feb 28 at 22:34
  • \$\begingroup\$ Welcome to CCPG! I enjoy graph theory related challenges. Some questions: 1. The input seems a bit laborious; can we simply take a single list of tuples (x,y) where x and y are strings? E.g.: [('S1', 'B3'), ('B3', 'T1'), ('B3, 'T7'), ...]? 2. Can we assume that the graph described by the input is a single rooted tree? \$\endgroup\$ – Chas Brown Feb 29 at 6:32
  • 1
    \$\begingroup\$ Hi @ChasBrown -- Yes that will be fine, I thought that keeping them separated makes it easier to crunch when numbers are larger than 9 - but feel free to modify the input format -- as long as it can reproduce the tree and the input is explicitly stated in your solution - yes this is a single-rooted tree. Thank you for the feedback - I'll take it on board for future posts! \$\endgroup\$ – leopardxpreload Mar 1 at 7:55
1
\$\begingroup\$

Java (JDK), 570 bytes

t->{return "Routes = "+Arrays.deepToString(Arrays.stream(r(t.get(0).get(0),t,t.get(0).get(0)).split("\\[")).filter(d->d.endsWith("]")).map(d->d.replaceAll("]", "")).map(d->d.split("(?=[A-Z])")).collect(Collectors.toList()).toArray());};String r(String s, List<List<String>>t, String b){List<String>o = t.stream().filter(e->e.get(0).equals(s)).map(e->e.get(1)).collect(Collectors.toList());if(s.matches("^S(?!(?:1)$)\\d+"))return s;if(o.size()>1){String x="";for(String n:o){x+="["+b+r(n,t,b+n)+"]";}return x;}if(o.size()==1)return s+r(o.get(0),t,b+o.get(0));return "]";}

As you may notice by my code I´m still learning a lot every day. My answer is neighter pretty nor short and I honestly even hope this works for different testcases even though I tested a couple. But I hope that this question gets the attention it deserves and there will be more answers I can learn from.

INPUT

String[][] STEP = { { "S1", "B3" },  ... ,{ "B14", "T2" }, { "B14", "T10" } };
List<List<String>> tupels = Arrays.stream(STEP).map(Arrays::asList).collect(Collectors.toList());
z(tupels);

I converted your given Input into an 2D-Java-Array String[][] and converted that into a List<List<String>>.

CODE

The first method calls a recursive method to get all routes and formats the output.

t->{
return "Routes ="+Arrays.deepToString(
  Arrays.stream(r(t.get(0).get(0),t,t.get(0).get(0)).split("\\["))
 .filter(d->d.endsWith("]")).map(d->d.replaceAll("]", ""))
 .map(d->d.split("(?=[A-Z])")).collect(Collectors.toList()).toArray());
};

The second method is the recursive method which gathers all the possible routes

String r(String s, List<List<String>>t, String b){
  List<String>o =t.stream().filter(e->e.get(0).equals(s)).map(e->e.get(1))
  .collect(Collectors.toList());
  if(s.matches("^S(?!(?:1)$)\\d+"))
    return s;
  if(o.size()>1){
    String x="";
    for(String n:o){
      x+="["+b+r(n,t,b+n)+"]";
    }
    return x;
  }
  if(o.size()==1)
    return s+r(o.get(0),t,b+o.get(0));
  return "]";
}  

Try it online!

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.