Help with search trees (Euler Project problem 18)

General
1

Hi

I have just started out on my F# adventure, and what a ride :slight_smile: (I have 10-12 years of professional C# programming experience)

I have challenged myself to solve as many problems as I can in project euler using F# and trying to stay true to the functional paradigme. But now I am stuck at problem 18 link

So here is my problem, this is my first search tree in F#, but nodes share leafs. Which isn’t the case for all the examples I can find.
I think it is ok easy describe the union. My take:

type Tree =
    | Node of int * Tree * Tree
    | Empty

I have two questions:

  1. How do I populate a tree, when using immutable data and shared leafs like in the link? Should I create an id for each node, and put them in a set / look-up, and try to get them from there before creating the node?

  2. Furthermore, I need to do a lot of calculations from bottom-up (The current solution I am working with). If I just made a recursive algoritme, that went from the top, and just tried every route, I would have had no (or little) problem implementing it.
    But adding the largest leaf to the node, requires a mutable data structure? Or how do I solve this the most “pure” functional way?

Perhaps I just need the correct terms to search for. Or should I just throw the data into a good old-fashioned 2D array?
I would prefer as little help as possible, but just enough so I am no longer stuck…

2

There is a great artcile about using Trees:

Trees in the real world

You probably find answers to the Qs there.

Well, I think that way will be much easier, yes.

1 Like
3

So, I ended up using a list<list<int>> :slight_smile:
I will not post the solution here, as it is encouraged not share the solutions in public.
But if someone, just can not live without my half-baked n00b solution, then PM me.

And thanks @FoggyFinder, but I didn’t find any such structures in the above link…