programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Cool but hard riddle: Design this algorithm

Myke Enriq
Ranch Hand
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
Posts: 115

Tim Moores
Saloon Keeper
Posts: 3834
80
Is this homework you should be doing?

fred rosenberger
lowercase baba
Bartender
Posts: 12529
48