Walking the Trie

[tabithabragg]

From a discord discussion with Dale (now a contributor):

1:12 PM] Rosencrantz23: Saw your post on FB [1:12 PM] Rosencrantz23: try something like this for the core of what you're doing: [1:14 PM] Rosencrantz23: In [18]: ObjGroupings = { ...: "Computer_A": [[1,2,3,4],['Case','Keyboard','Mouse','Monitor']], ...: "Computer_B": [[5],['Laptop_Complete']], ...: "Backpack": [[6],['Backpack']]}

In [21]: outDict = {}

In [24]: for k, v in ObjGroupings.items(): ...: outDict[k] = [[e+1, pair[1]] for e, pair in enumerate(zip(v))] [1:15 PM] Rosencrantz23: that gives you the output In [25]: outDict
Out[25]: {'Computer_A': [[1, 'Case'], [2, 'Keyboard'], [3, 'Mouse'], [4, 'Monitor']], 'Computer_B': [[1, 'Laptop_Complete']], 'Backpack': [[1, 'Backpack']]} [2:18 PM] Rosencrantz23: (the operator unpacks lists and tuples, and then if you need it, the ** operator does the same thing for dictionaries. Which is why in a lot of function signatures, you [2:21 PM] Rosencrantz23: you'll see something like:

def my_fun(var1, var2, var3, *args, **kwargs):

unpacking an arbitrary list of parameters from args, and/or an arbitrary dictionary of name-value pairs [2:21 PM] Rosencrantz23: from kwargs [2:21 PM] Rosencrantz23: (I personally like the * operator's name in Ruby: "Splat") [3:14 PM] Scott (dlvphoto): do you have a github account? [3:17 PM] Scott (dlvphoto): The first part of the post is what I start with. I have to get from that to the breakdown in ObjGroupings. I don't get to start there. [3:18 PM] Scott (dlvphoto): How do I get from here: 1,ABCD_Test_Computer_A_Case 2,ABCD_Test_Computer_A_Keyboard 3,ABCD_Test_Computer_A_Mouse 4,ABCD_Test_Computer_A_Monitor 5,ABCD_Test_Computer_B_Laptop_Complete 6,ABCD_Test_Backpack 7,ABCD_Test_Computer_Desk_A_Oak 8,ABCD_Test_Computer_Desk_B_Teak 9,ABCD_Test_Computer_Desk_B_Chair_Teak 10,ABCD_Test_DeskLamp_Body 11,ABCD_Test_DeskLamp_Bulb 12,ABCD_Test_DeskLamp_Power_Cord [3:18 PM] Scott (dlvphoto): to [3:19 PM] Scott (dlvphoto): ObjGroupings = { "Computer_A": ((1,2,3,4),(Case,Keyboard,Mouse,Monitor)), "Computer_B": ((5),(Laptop_Complete)), "Backpack": ((6),(Backpack)), "Computer_Desk_A_Oak": ((7),(Computer_Desk_A_Oak)), "Computer_Desk_B": ((8,9),(Teak,Chair_Teak)), "DeskLamp": ((10,11,12),(Body,Bulb,Power_Cord)) } [3:19 PM] Scott (dlvphoto): then to: [3:19 PM] Scott (dlvphoto): Layer #, Layer name 1,Case 2,Keyboard 3,Mouse 4,Monitor

3d object name: Computer_B_Laptop_Complete Layer #, Layer name 1,Computer_B_Laptop_Complete

3d object name: Backpack Layer #, Layer name 1,Backpack

3d object name: Computer_Desk_A_Oak Layer #, Layer name 1,Computer_Desk_A_Oak

3d object name: Computer_Desk_B (edge case with badly named parts.. rare but happens) Layer #, Layer name 1,Teak 2,Chair_Teak

3d object name: DeskLamp Layer #, Layer name 1,Body 2,Bulb 3,Power_Cord [3:27 PM] Scott (dlvphoto): I started a github project for this (and shortly, the other half of this project; the surface handler) [3:28 PM] Scott (dlvphoto): https://github.com/scottbragg/LWTools/blob/master/kbconvert_notes GitHub scottbragg/LWTools Contribute to scottbragg/LWTools development by creating an account on GitHub.

[3:39 PM] Rosencrantz23: I'm dsj529 on github (rosencrantz23@gmail.com) [3:42 PM] Rosencrantz23: ok, to me it looks the hardest part is going from the source list into the dictionary of lists. Manipulating from there should be pretty easy. [3:42 PM] Scott (dlvphoto): hang on.. want to invite you to be a contributor to that project. [3:43 PM] Scott (dlvphoto): Yep. The variant naming scheme is what's a pain in the arse. [3:43 PM] Scott (dlvphoto): Not going to be able to do it without logic to check for that, I think. [3:43 PM] Rosencrantz23: Yeah. [3:44 PM] Rosencrantz23: hmmmm. [3:44 PM] Rosencrantz23: I'm getting the glimmerings of an idea, but I don't know enough low-level code to implement the data structure. [3:45 PM] Scott (dlvphoto): Let me get you set up on the git repo. toss ideas on there in the discussion for it (I'll start an 'issue' and tag it 'discussion'). This is good job-resume-stuff fodder. :slight_smile: [3:45 PM] Rosencrantz23: I think, if you could split the initial names: [1,ABCD_Test_Computer_A_Case 2,ABCD_Test_Computer_A_Keyboard 3,ABCD_Test_Computer_A_Mouse 4,ABCD_Test_Computer_A_Monitor 5,ABCD_Test_Computer_B_Laptop_Complete 6,ABCD_Test_Backpack 7,ABCD_Test_Computer_Desk_A_Oak 8,ABCD_Test_Computer_Desk_B_Teak 9,ABCD_Test_Computer_Desk_B_Chair_Teak 10,ABCD_Test_DeskLamp_Body 11,ABCD_Test_DeskLamp_Bulb 12,ABCD_Test_DeskLamp_Power_Cord] [3:46 PM] Rosencrantz23: into a list of lists: [[abcd, test, computer, a, case], [abcd, test, computer, a, keyboard], ... ] [3:46 PM] Scott (dlvphoto): Split out the ABCD_Test and just save it somewhere if I need it later. It's guaranteed to be the same everywhere for that object set. [3:46 PM] Rosencrantz23: And load that into a Trie [3:46 PM] Rosencrantz23: https://en.wikipedia.org/wiki/Trie Trie In computer science, a trie, also called digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings. Unlike a binary search tree, no node in the tree stores the key as...

[3:47 PM] Rosencrantz23: You should be able to get the groupings you need pretty easily. I've just never written/implemented a trie before. [3:47 PM] Scott (dlvphoto): Yep. that's exactly what it is. Just didn't know where was a formalized structure for it. [3:48 PM] Scott (dlvphoto): Basically it's trie->finalbranch(-1) is my layername. [3:48 PM] Rosencrantz23: Right. [3:49 PM] Scott (dlvphoto): trie->branch(1)_branch(2){if branch(2) NE finalbranch(-1) or NE finalbranch() [3:50 PM] Rosencrantz23: I ran across tries maybe 2 years ago when researching how to do parallelized string matching of multiple patterns. There's a few algorithms built straight on tries, and then you get into parallelized regex engines which do things I have no idea how. [3:55 PM] Scott (dlvphoto): if (numBranches = 1) ObjName = lyrName = trie->branch(1) else if (numBranches = 2) ObjName = trie->branch(1); lyrName = trie->branch(2) else if (numBranches > 2 ObjName = trie>branch(numBranches-2); lyrName - trie->branch(x) [3:55 PM] Scott (dlvphoto): or some such. [3:56 PM] Rosencrantz23: I think that works. [3:56 PM] Scott (dlvphoto): It's backwards in how it's walking the branches. Requires multiple iteratiosn of each branch in it's logic. Letting a couple of background processes in my head work on that one. :slight_smile: [3:58 PM] Rosencrantz23: Yeah, I know that feeling. Waiting for my backbrain to tell me its solved the thing I'm stuck on. [3:58 PM] Scott (dlvphoto): You've been invited as a collaborator.

[tabithabragg]

From the discussion:

Trie: https://en.wikipedia.org/wiki/Trie

Trie library: https://github.com/pytries/marisa-trie

[tabithabragg]

Need to Ping Dale again with the logic flow info to see if that helps him understand what I want to do in a more coherent fashion.

[tabithabragg]

Closing this as it's too specific to the KB3D object naming scheme instead of the surface naming schema. This project is currently focusing on a more general PBR mass surfacing toolset that would include KB3D (and megascans) as a subset use case.