CODEWITHSUNDEEP
f#functional-programming
Ron Quega
Ron Quega

Reputation: 33

Dead clown with functional data structure

here we go with the problem:

I have a clown agency with many clowns going to different parties. Some go to the same party. And I keep a log with who has gone to which party. Then, I have a dead clown but I need to parse the logs to get which people to investigate, clowns and other people in the party, but also need all the parties and clowns related to the dead clown (all the clowns that have been in the previous parties the clown has participated).

Basically, I have thought on doing it with graphs, but maybe it is not the best idea, graphs are pretty complex for being used in this problem.

My logs are like this:

type Action = 
  | Move of Clown * Party
let logs = Action list

What do you think is it gonna be a good data structure to transform the list and parse it?

Upvotes: 3

Views: 741

Answers (2)

John Palmer
John Palmer

Reputation: 25516

Here is a functional solution, using the Seq.groupBy function

logs |> Seq.groupBy (function |Move(clown,party) -> party) |> Map.ofSeq

this will give you a Map<Party,Clown list> which you can easily query to find which clowns are at which party.

Upvotes: 3

Ken Wayne VanderLinde
Ken Wayne VanderLinde

Reputation: 19339

You're right that graphs are pretty complex - but that's mostly when you develop a general-purpose graph. In your case, I would say that a graph is still the best way to go, since that would directly model the situation.

I'm not sure how to do this in the functional paradigm, but here's the idea in good old imperative style:

  1. Give each of your n clowns and number from 0 (inclusive) to n (exclusive). These will serve as array indices
  2. Build an n * n array, initialized to all zeros.
  3. When a party is planned, the for each pair of clowns in the party (with numbers i and j), set the i,j-th and the j-i-th cell to 1

When you're given a dead clown, all you would have to do now is read the row corresponding to the dead clown's number. The cells with a 1 in them will tell you which clowns attended parties with the dead clown.

I think the above description shows that graphs don't have to be complex, if they're set up for a particular situation. Then again, I'm not sure how nicely graphs manifest themselves in functional programming, so if your goal is to do everything in a functional style, a graph might be much more complex.

Upvotes: 1

Related Questions