Create a Trie that stores slice orderings

[grim tundra]

I want to create a trie that can store data like so:

data = [[10,10,25],[10,10,25],[10,25,10]] gets turned into

10: {
  10: {
    25: {}
  25: {
    10: {}
  }
}```

I am struggling to avoid overwriting my trie data

Current form of my trie

type TrieNode struct {
    value    int
    children []*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}```

[little dagger]

Is it related to your prev question?

[grim tundra]

aye, thought i'd spin the issue with the trie into a new question

[little dagger]

about your prev question, you can create nested map like it

and

if there are not elements you want to add you can save subarray

if there are

you delete array

isn't it solution for your case?

[grim tundra]

probably, can I see a code example? Brain isn't putting 2 and 2 together atm

[little dagger]

give me a minute

type M map[int]M

func main() {
    arrays := [][]int{{1, 2, 3}, {3, 2, 1}, {1, 2, 3}, {2, 3, 1}, {3, 2, 1}}
    var result [][]int
    headM := make(M)
    currM := headM
    invalid := false
    for _, s := range arrays {
        for _, v := range s {
            _, ok := currM[v]
            if ok {
                invalid = true
                break
            }
            currM[v] = make(M)
            currM = currM[v]
        }
        currM = headM
        if invalid {
            invalid = false
            continue
        }
        result = append(result, s)
    }
    fmt.Printf("%v\n", result)
}

something like this

@grim tundra

[grim tundra]

lemme check it out

[little dagger]

but i forgot about one question

all your subarrays is a same length?

[grim tundra]

yes

[little dagger]

ok

then it should work

[grim tundra]

numbers = []int{1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100} full list of numbers I am using, at most the subslices will be length 6

[little dagger]

btw if memory is a problem you can set non unique slices to nil

instead of results array

[grim tundra]

hmmm, unless I am missing something. It seems too effective

[little dagger]

what are you missing?

[grim tundra]

the length of my permutation slice of slices is 120, after putting it through your code it comes to 4

[100, 10, 10] gets through

[10, 10, 100] doesn't

[little dagger]

hmm

let me fix it

[little dagger]

can you send me full array?

[grim tundra]

[[10 10 25] [10 25 10] [10 10 25] [10 25 10] [25 10 10] [25 10 10] [10 10 50] [1
0 50 10] [10 10 50] [10 50 10] [50 10 10] [50 10 10] [10 10 75] [10 75 10] [10 1
0 75] [10 75 10] [75 10 10] [75 10 10] [10 10 100] [10 100 10] [10 10 100] [10 1
00 10] [100 10 10] [100 10 10] [10 25 50] [10 50 25] [25 10 50] [25 50 10] [50 1
0 25] [50 25 10] [10 25 75] [10 75 25] [25 10 75] [25 75 10] [75 10 25] [75 25 1
0] [10 25 100] [10 100 25] [25 10 100] [25 100 10] [100 10 25] [100 25 10] [10 5
0 75] [10 75 50] [50 10 75] [50 75 10] [75 10 50] [75 50 10] [10 50 100] [10 100
 50] [50 10 100] [50 100 10] [100 10 50] [100 50 10] [10 75 100] [10 100 75] [75
 10 100] [75 100 10] [100 10 75] [100 75 10] [10 25 50] [10 50 25] [25 10 50] [2
5 50 10] [50 10 25] [50 25 10] [10 25 75] [10 75 25] [25 10 75] [25 75 10] [75 1
0 25] [75 25 10] [10 25 100] [10 100 25] [25 10 100] [25 100 10] [100 10 25] [10
0 25 10] [10 50 75] [10 75 50] [50 10 75] [50 75 10] [75 10 50] [75 50 10] [10 5
0 100] [10 100 50] [50 10 100] [50 100 10] [100 10 50] [100 50 10] [10 75 100] [
10 100 75] [75 10 100] [75 100 10] [100 10 75] [100 75 10] [25 50 75] [25 75 50]
 [50 25 75] [50 75 25] [75 25 50] [75 50 25] [25 50 100] [25 100 50] [50 25 100]
 [50 100 25] [100 25 50] [100 50 25] [25 75 100] [25 100 75] [75 25 100] [75 100
 25] [100 25 75] [100 75 25] [50 75 100] [50 100 75] [75 50 100] [75 100 50] [10
0 50 75] [100 75 50]]

[little dagger]

for me it seems to work

[grim tundra]

what about [10, 100, 10]?

[little dagger]

hmm

not

interesting

ou

yea

i found problem

type M map[int]M

func main() {
    arrays := [][]int{{10, 10, 100}, {100, 10, 10}, {10, 100, 10}}
    var result [][]int
    headM := make(M)
    currM := headM
    invalid := false
    k := len(arrays[0]) // NEW value
    c := 0 // NEW value
    for _, s := range arrays {
        for _, v := range s {
                        c += 1 // NEW
            m, ok := currM[v] // Change _, ok -> m, ok
            if ok && c == k { // Add && c == k
                invalid = true
                break
            } else if !ok { // NEW
                m = make(M)
            }
            currM[v] = m // Change make(M) -> m
            currM = currM[v]
        }
        currM = headM
        c = 0 // NEW
        if invalid {
            invalid = false
            continue
        }
        result = append(result, s)
    }
    fmt.Printf("%v\n", result)
}

@grim tundra

try it

prev decision was make on any subarray step

now on last step

[grim tundra]

that works, thanks

this is to remove dupliactes, not to build a trie yeah?

[little dagger]

Yes and no. If you noticed it is tree like map

If we have two arrays

1,2,4 and 1,2,3

1 -> 2

2 -> 3

2 -> 4

Do you understand it?

[grim tundra]

yes? Might take sometime going through with teh debugger to properly get my head around it

can I walk it like a trie?

[little dagger]

Depends on your use case

[grim tundra]

I wanna build a trie of all the possible permutations for the numbers I am using (max length 6). I would then iterate over the trie to get each possible permutation and generate a trie of all possible equations

[little dagger]

i don't quite understand you

an example

you have 2 permutation places

and numbers 1,2,3

are all numbers present in each place?

but anyway

if you want to

you can iterate over map

for key, value := range m {}

[civic dawn]

Hmph interesting lemme digest

Does it work with your billion slices ? @grim tundra

[little dagger]

btw 220 billions with slice header 24 bytes and 11 ints with length 88 byte
220 * 10**9 * 112 / 1024**4 =~ 22tb

if i am correct

only input

[civic dawn]

22tb

[grim tundra]

i did the calcs on this awhile ago, a) I don't think it reached terabytes, and b) precisely for the problem of the size multiple 100gb's I cleaned it up as I went

if you are curious as to how I previously achieved this in java https://github.com/Ghrafkly/countdownJava

btw, I was finally able to get the trie to work

just a couple of properly placed if statements

type TrieNode struct {
    children map[int][]*TrieNode
    isEnd    bool
}

type Trie struct {
    root *TrieNode
}

func NewTrie() *Trie {
    t := new(Trie)
    t.root = new(TrieNode)
    return t
}

func (t *Trie) insert(nums []int) {
    current := t.root
    for _, index := range nums {
        if _, ok := current.children[index]; !ok {
            if current.children == nil {
                current.children = make(map[int][]*TrieNode)
            }
            current.children[index] = []*TrieNode{new(TrieNode)}
        }
        current = current.children[index][0]
    }
    current.isEnd = true
}```

[little dagger]

hmm trie and part from the code above?

[grim tundra]

no? at least not intentionally

known that I needed a slice of trie nodes as the value for the map since almost the beginning. Just a matter of figuring out the correct combo needed to make it work

same with the if _, ok.. part.

I had the pieces, just had to figure out how to make them work

Thing of beauty

This is exactly what I was trying for

[little dagger]

btw, why are you using map[int][]*TrieNode instead map[int]*TrieNode

[grim tundra]

good point, artifact of me throwing stuff at the well until it worked

[little dagger]

and what do you think about map[int]TrieNode instead of map[int]*TrieNode
and do you need isEnd?
if Node doesn't have children doesn't it mean end?

[grim tundra]

is end makes it cleaner imo

[little dagger]

func (t *TrieNode) isEnd() bool {
  return t.children == nil
}

?

[grim tundra]

I don't know what the change would effect?

[little dagger]

maximum change is less memory consume

1 byte per node

[grim tundra]

fair

though

how much change is it from storing if the node isEnd, vs making a function call?

memory vs speed I suppose?

i.e. node.isEnd vs node.isEnd()

[little dagger]

depends on trie size

@grim tundraand btw

isEnd trie should be implement on each node

but in your case

only for one last

not for each last

[grim tundra]

wdym only for one vs each last?

[little dagger]

p, r, r, o, f, s, t are last

ou sorry

forget

incorrect code read

[little dagger]

but i should notice

i would prefer each TreeNode to implement insert

and do it using recursion

[grim tundra]

how do you mean?

also, this is the final number of permutations I have after filtering 5322360

think it results in a 2gb trie

but having it in memory is nice

that said, from prior expereince the slow down is when I try to start calcaulating everything

[little dagger]

type TrieNode struct {
  children map[int]*TrieNode
  value int
}

func newNode(value int) *TrieNode {
    return &TrieNode{
        value: value,
        children: make(map[int]*TrieNode), // TO prevent panic
    }
}

func (t *TrieNode) insert(nums []int) {
    if len(nums) == 0 {
        return
    }
    v, ok := t.children[nums[0]]
    if !ok {
        v = newNode(nums[0])
        t.children[nums[0]] = v
    }
    v.insert(nums[1:])
}

something like this

@grim tundra

[grim tundra]

how does this work differently?

and whats the pros/cons vs what I am doing

[little dagger]

you can insert when you have any trie node

and code cleaner

[grim tundra]

damn, can't just drop it in

huh

[little dagger]

btw

there are with your method

and with my methods

depends on use case

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

[grim tundra]

yeah, I had seen both methods. Until I got it working, it didn't make 100% sense to me

also, struggling to implmement your code

doesn't create the nested children

at least not with trying it the same way I was doing before

[grim tundra]

here is my current code https://github.com/Ghrafkly/version_Go

struggling to implemement your code to see how it works

[grim tundra]

try again, made it public

[little dagger]

func (t *TrieNode) insert(nums []int) {
    if len(nums) == 0 {
        return
    }
    v, ok := t.children[nums[0]]
    if !ok {
        v = newNode(nums[0])
        t.children[nums[0]] = v
    }
    v.insert(nums[1:])
}

just add it

and try

anyTrieNode.insert([]int{1,2,3})

func newNode(value int) *TrieNode {
    return &TrieNode{
        value: value,
        children: make(map[int]*TrieNode), // TO prevent panic
    }
}

and it

[grim tundra]

I think the problem is where I start my Trie

(in the permutations function)

[little dagger]

replace trie.insert(temp) -> trie.root.insert(temp)

should work

[grim tundra]

hmm, still not there

getting panic: assignment to entry in nil map

[little dagger]

show me your insert func

[grim tundra]

I just dropped your code into my trie.go file

[grim tundra]

yep, havent pushed up the changes but thats the file

[little dagger]

this code too?

[grim tundra]

both yes

[little dagger]

change it

t.root = new(TrieNode) -> t.root = newNode(-1)

[grim tundra]

well, its not erroring, but it is also just immediately ending

[little dagger]

could you show current version of this?

[grim tundra]

func permutations(nums []int) {
    perms := combin.Permutations(len(nums), len(nums))

    var temp []int
    for _, p := range perms {
        for _, i := range p {
            temp = append(temp, nums[i])
        }
        permTrie.root.insert(temp)
        temp = nil
    }
}```

[little dagger]

from where are you getting number of permutations value?

[grim tundra]

trie.go -> display

just call len(permTrie.display)

is that whta you mean?

[little dagger]

func (t *TrieNode) isEnd() bool {
return t.children == nil
}

replace to return len(t.children) == 0

and it should work

[grim tundra]

easy, thanks

[little dagger]

now every node has init map

[grim tundra]

my code took 42 seconds to produce the permutations I needed, wonder how much of a difference there will be

[little dagger]

btw i think no difference

just another method

any tree is a graph

and recursion classic graph method

[grim tundra]

gonna try and multithread the permutation generation, get the practice in early so I know what I am doing when implementing it for the solving portion (which is 90% of the reason why my code is so slow)

[little dagger]

hmm

if you want to

you can use sync.Map

for children

instead classic map

[grim tundra]

sync.Map?

I have only done basic research, so I know about channels, mutexes, and atomics

[little dagger]

https://pkg.go.dev/sync#Map.LoadOrStore

look

[grim tundra]

oh cool

that will come in handy

it seems like it is a bit like Java's ConcurrentHashMap?

btw, my trie code runs 43-45s. Yours is 46-49s

[little dagger]

type TrieNode struct {
    children sync.Map
    value    int
    isEnd    atomic.Bool
}

func newNode(value int) *TrieNode {
    t := &TrieNode{
        value: value,
    }
    t.isEnd.Store(true)
    return t
}

func (t *TrieNode) insert(nums []int) {
    if len(nums) == 0 {
        return
    }
    v, _ := t.children.LoadOrStore(nums[0], newNode(nums[0]))
    if len(nums) > 1 {
        v.(*TrieNode).insert(nums[1:])
        t.isEnd.Store(false)
    }
}

func (t *TrieNode) String() string {
    var c []*TrieNode
    t.children.Range(func(key, value any) bool {
        c = append(c, value.(*TrieNode))
        return true
    })
    return fmt.Sprintf("%v: %v", t.value, c)
}

func (t *TrieNode) IsEnd() bool {
    return t.isEnd.Load()
}

concurrency safe code

@grim tundra

(probably)

[grim tundra]

cheers, I am about to head to bed so I will take a look in the morning

interestingly though, I tried using waitgroups and mutexes and it ran twice as slow

[little dagger]

based on lock

[grim tundra]

possible I did it wrong, or the structs lend to needing to use sync.Map

[little dagger]

i guess your prev code locks whole Trie

here

lock per node

[grim tundra]

bingo

ah gotcha

yeah, this is how I currently do it

mutex.Lock()
{
    permTrie.insert(temp)
    //permTrie.root.insert(temp)
}```

[little dagger]

but there can be problem with delete

hmm i know how to solve it lightly

[grim tundra]

well the good news is the only time I ever have to delete it to just remove the entire trie

no pruning, just uprooting

otherwise I run out of memory, though this is a problem for future code

[little dagger]

@grim tundrahow's it going?

[grim tundra]

really good, got the trie working

and was able to copy-paste old code I use for the next step to generate all equations

So that's all good

big problem now is figuring out how to get this multithreading working as needed

1 combination; 360 permutations; 15482880 equations // Test data
177100 combinations; 5322360 permutations; 228904058880 equations // Full program

at this stage, generating all 220 billion equations will take 50 hours. Not including it will take up 100's gb. I do have a way to iteratively generate, evaluate and delete the equations. Just need to figure out the best way to do it in go

[little dagger]

what is your numbers range?

1-100?

and 11 places for numbers?

[grim tundra]

number range is 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 25, 50, 75, 100

6 numbers + 5 operators comes to 11

I am using -1, -2, -3, -4 to represent +, -, /, *

[little dagger]

you can run one gorutine per first number

to parallel it

i mean

an example

we have 1,2,3,4,5

and 3 places

111
112
113
114
115

and

we can run gorutine per each first num

first gorutine: 111, 112, 113, 114, 115, 121, 122, 123, 124 .....
second gorutine: 211, 212, 213, 214, 215, 221, 222, 223, 224 ......
third gorutine: 311, 312, 313, 314, 315, 321, 322, 323, 324 .....