Meaningless Drivel is fun!
The moose likes Programming Diversions and the fly likes Cool but hard riddle: Design this algorithm Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "Cool but hard riddle: Design this algorithm" Watch "Cool but hard riddle: Design this algorithm" New topic

Cool but hard riddle: Design this algorithm

Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 115
you get a graph of 100 nodes (not a single vertex at first) , on each iteration (named T- it simulates time) each node gets this amount of coins for free (from Santa). For node n the amount of coins he receives is constant (in iteration 1 he receives just as much as in iteration 5674 - or any other).

In each iteration the nodes want to add friends to each other. For A to add B as friend A sends and invite this iteration(unit of time) T and B accepts/decline the next tieration (unit of time T+1). They are friends when B accepts. When a node A is friend to node B then A receives from B the amount (coins of B / friends of B) $. B receives fom A (coins of A / friends of A) $.

Coins are useless to the nodes (well ,they determine the amount of $ that this node gives to its friends). Everyone want to make as much $ as possible.

Your job is to simulate these iterations in order to see what the equilibrium state is (if there is one actually).

My question is: sure one can make 100 objects of class Node in java , then for each iteration , iterate on them 100 nodes and compute their decision. Here comes the hard part :

strategy 1: Some nodes want to add as many friends as they can (each friend gives you at least one coin meaning 1$).

strategy 2: Some nodes want at some point to remove 50% of their friends , so they have less friends so greater value in the next iteration (A has less friends means A gives more $ means a very productive B is more likely to invite/accept his invitation).

strategy 3: Some nodes evaluate what friends they have that give them less $ than they receive from them. In any iteration they remove 50% of those nodes

strategy 4: Some nodes just choose a list of Constant other nodes they they are not friends with yet and send invites to the most profitable half of this Constant.

Your job is to write an algorithm / think about it , that for a node combines these strategies and it creates a unique strategy for that specific node (that is a combination of these 4).

How would this algorithm look like ?
Is there any strategy that I have not mentioned ? (could there be a 5th strategy too) ?

Thank you in advance for any replies , Good luck solving this riddle !

Myke Enriq
Ranch Hand

Joined: Feb 13, 2012
Posts: 115
Come on people , reply to me please.
Tim Moores

Joined: Sep 21, 2011
Posts: 2414
Is this homework you should be doing?
fred rosenberger
lowercase baba

Joined: Oct 02, 2003
Posts: 11955

Myke Enriq wrote:Come on people , reply to me please.

Nobody is obligated to help you. Perhaps you should read some of our FAQs on HowToAskQuestionsOnJavaRanch <--click that

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
I agree. Here's the link:
subject: Cool but hard riddle: Design this algorithm
It's not a secret anymore!