Bones
BAN USERThis question is definitely designed to test your ability to ask questions about a given task so that you can clearly tackle the problem. Starting questions I would ask back:
- Real time or turn based?
- Does internet scale mean played in a browser, or able to handle an 'internet sized' amount of users?
- What are the limits of my resources? Server memory, processing, disk space....
- Do we have a target amount of concurrent users?
- Who is our target audience?
- How authoritative is this? Can the client just send updates about their state to the server and have the server relay it? Movement gets broken by things like speed hacks at this point...but the MMORPG requirements are so low that cheating to run through the world doesn't seem like a big deal.
- Can a player do 2 actions at once?
Things of that nature.
#include <iostream>
using namespace std;
// REVERSING THE WORDS IN A SENTENCE
void ReverseString( char* string, unsigned start, unsigned end ) {
for( unsigned i = start, j = end; i < j; ++i, --j ) {
char temp = *(string + i);
*(string + i) = *(string + j);
*(string + j) = temp;
}
}
void ReverseSentence( char* sentence ) {
if( !sentence )
return;
// Subtract 1 to account for null terminator
int sentenceLen = strlen(sentence);
ReverseString(sentence, 0, sentenceLen - 1);
// Find the indices of each word
unsigned start = 0, end = 0;
for( unsigned i = 0; i <= sentenceLen; ++i ) {
if( sentence[ i ] == ' ' || sentence[ i ] == '\0' ) {
end = i - 1;
ReverseString(sentence, start, end);
start = i + 1;
}
}
}
int main(int argc, char *argv[]) {
char sentence[] = "Reverse the words in this sentence";
ReverseSentence(sentence);
printf(sentence);
}
This is the approach I came up with. I'm unsure if it's the optimal solution though. Would love suggestions!
Anyways, the idea is that you evaluate each kid in the circle, if he can pass an apple to someone who needs it behind him, then he does. Otherwise, if they have excess apples, then they just continue to pass it forward.
From the way the question seemed to be phrased, I took it that a pass is a single iteration through all children in the circle, so once everyone has given an apple away (if they can), then the next pass (step) starts.
#include <iostream>
using namespace std;
struct Child {
int AppleCount;
Child( ) { AppleCount = 0; }
Child( int appleCount ) { AppleCount = appleCount; }
};
// Returns false if there are no apples to pass, true otherwise
bool PassApples( Child* children, unsigned childCount, unsigned appleCount ) {
// Check our kids and see if there are more apples to be passed on
bool needsPass = false;
unsigned endIdx = childCount - 1;
for( unsigned i = 0; i < childCount; ++i ) {
int prevChildIdx;
if( i == 0 )
prevChildIdx = childCount - 1;
else
prevChildIdx = i - 1;
// If the child before us has less apples than desired, pass it to him
if( children[ prevChildIdx ].AppleCount < appleCount && children[ i ].AppleCount ) {
children[ prevChildIdx ].AppleCount += 1;
children[ i ].AppleCount -= 1;
needsPass = true;
}
else {
// If this child has excess apples, pass it along.
if( children[ i ].AppleCount > appleCount ) {
children[ i ].AppleCount -= 1;
children[ (i + 1) % childCount ].AppleCount += 1;
needsPass = true;
}
}
}
return needsPass;
}
int main(int argc, char *argv[]) {
// @TODO: Read the values in from input, or a file or something...
const int CHILDCOUNT = 5;
Child children[ CHILDCOUNT ] = { 3, 4, 6, 10, 2 };
// Find total apples
unsigned totalApples = 0;
for( int i = 0; i < CHILDCOUNT; ++i )
totalApples += children[ i ].AppleCount;
bool needsPass = true;
unsigned numPasses = 0;
while( needsPass ) {
if( PassApples( children, CHILDCOUNT, totalApples / CHILDCOUNT ) )
++numPasses;
else
needsPass = false;
}
cout << "Total Passes: " << numPasses;
// This is just here so that the app doesn't close before output can be seen
char c;
cin >> c;
}
Correct me if I'm wrong, but isn't the max distance the position of the last occurrence subtracted from the position of the first occurrence?
In C#
- Bones April 19, 2013