An ***ameoba graph**** is a type of tree whose nodes all have values from 0 to some non-negative integer N, and any particular node with value x < N connects to x+1 distinct nodes with values x+1.
Ameoba graph for N = 3: (Denoted A3)
Note that the 2's are not allowed to share any of the 3's; exactly three 3's must "belong" to each 2.
Your task is to inductively "grow" these ameoba graphs in a 2-dimensional grid by greedily minimizing the Manhattan distance between nodes:
- Base case: A0 is simply the graph
- Inductive step: AN+1 is generated by iteratively placing the new N+1 valued nodes as close as possible to the N values nodes in the existing AN structure. (It can only be as close as possible since the closest spots may already be filled.)
For the inductive step the general procedure you must follow is:
for each existing node P with value N: for each new N+1 valued node Q you need to connect to P: //this loops N+1 times find the set of vacant spots that are minimally distant from P //by Manhattan distance place Q in any of these vacant spots
(A different procedure with indistinguishable output is fine.)
Growth example for A4:
A0 is always the same: 0 For A1 I happen to put the 1 to the right of the 0 (it has to go on one of the 4 open sides): 01 For A2 I happen to put the two 2's above and to the right of the 1: 2 012 For A3 I find that one of the six 3's I must place cannot be directly next to a 2, so I put in one of the next closest places: 3 323 0123 33 <-- this 3 is distance two away from its 2 The process continues in A4. Note that I'm iterating over each 3 and placing four 4's next to it or as close as possible, then moving to the next 3 (the order of 3's does not matter): 444 443444 4323444 4012344 44334 4444 44 Always keep in mind that nodes cannot be "shared".
The program you write must take in a number from 0 to 8 (inclusive) and output a valid ameoba graph of it, using the inductive growth pattern explained above.
What happens beyond 8 does not matter.
(A8 contains 46234 nodes which is pushing it. Anything beyond A8 would be too far. Thanks to Martin Büttner for noticing this.)
The input should come from stdin or the command line and output should go to stdout or a file.
Examples (taken directly from above)
Input: 0 Output: 0 Input: 1 Output: 01 Input: 2 Output: 2 012 Input: 3 Output: 3 323 0123 33 Input: 4 Output: 444 443444 4323444 4012344 44334 4444 44
* These type of graphs might already have a name. I admit I just made them up. ;)