I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Thursday Code Puzzler: Two Generals

05.30.2012
| 3921 views |
  • submit to reddit

By now you should be familiar with our Thursday Code Puzzler slot. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you think is suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

The Two Generals Problem

This week's problem is another classic computer science puzzle that is designed to deal with communication protocols. The problem statement is as follows

Two armies, each led by a general, are preparing to attack a city. The armies are encamped outside the city on two mountains separated by a large valley. In order to capture the city, the generals must attack at exactly the same time. The only way for the generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders, so there's a chance any given messenger will be captured. Each general has no way of knowing if their messenger arrived. How do the generals coordinate their attack?
Try to make the solution as efficient as possible. Good luck

Comments

Jonathan Fisher replied on Sun, 2012/06/03 - 1:18pm

Duh, call in Air Support! 

Stephane Vaucher replied on Sun, 2012/06/03 - 9:44pm

I wouldn't try to solve this deterministically; I would deal with this with a Monte Carlo algorithm because we note that the message delivered (algorithm) is always correct if delivered. We'd use amplification to lower the acceptability of failure (more messages = less risk).

If the there is a probability P that the message gets intercepted, general A needs to send a large number of messengers (e.g., N = 100) with N being part of the message to determine the probability of interception. With this information, general B can determine what level of risk is acceptable and send the appropriate number of messengers given the risk constraint. If you send M messengers, the probability of interception is P^M. If you are willing to accept a probability of failure of Q, then you would need to solve find < in the equation: Q >= P^M (equal to log(Q) >= log(P) * M, or log(Q) /log(P) >= M). For example, if P = 1/2 and you want to make sure you succeed in Q=1/1024, you'd send at least 10 messengers (or log(1/1024) / log (1/2)).

From an efficiency standpoint, you'd have to send N messages + log(Q) / log(P) (or O(N + log(Q)/log(P)). Of course, the assumption is that the probability of interception of a message is constant. If the problem where applied to a larger number of communications, the importance of N would be negligeable. I'm just hoping my math is not off: it's been a while since my last algorithm course.

Vijay Nathani replied on Wed, 2012/06/06 - 1:46pm

I was waiting for someone else to solve this one. Since no one did it, my solution in Groovy (using open source GPars library) is given below:

#!/usr/bin/env groovy
import static groovyx.gpars.actor.Actors.*;
import groovyx.gpars.actor.*;
import groovy.transform.Canonical;
import java.util.concurrent.*

class Message {
	Date d = getRandomFutureDate();
	int sentNumber, recvNumber
	private def getRandomFutureDate() {
		int MINIMUM_DAYS_IN_FUTURE = 30;
		int MAXIMUM_DAYS_IN_FUTURE = 100;
		new Date().plus(ThreadLocalRandom.current().nextInt(
			MINIMUM_DAYS_IN_FUTURE,MAXIMUM_DAYS_IN_FUTURE));
	}
	def nextMessage(threadPool) {
		sentNumber++;
		int MESSAGE_WILL_REACH_SUCCESS_PERCENTAGE = 60
		(ThreadLocalRandom.current().nextInt(100) <
				MESSAGE_WILL_REACH_SUCCESS_PERCENTAGE)?
					copyMessage(this):
					"Interrupted"
	}
	def copyMessage(Message m) {
		new Message(d:m.d, sentNumber:m.sentNumber, recvNumber:m.recvNumber)
	}
	def updateMessage(Message m) {
		recvNumber = m.sentNumber;
		if (m.d < d) d = m.d;
	}
	public String toString() {
		"Message Date:${d.getDateString()} SendSeq:${sentNumber} ReceiveSeq:${recvNumber}"
	}
}
@Canonical
class General extends DefaultActor {
	int number;
	General other;
	Message m = new Message()
	def pool = Executors.newScheduledThreadPool(1)
	@Override protected void act() {
		onStop { pool.shutdownNow() }
        loop {
			sendMessage(m.nextMessage());
			long MAX_WAIT_TIME_FOR_MESSAGE = 15
            react (MAX_WAIT_TIME_FOR_MESSAGE, TimeUnit.SECONDS) { mesg ->
				receiveMessage(mesg) 
			}
        }
    }
	def sendMessage (message) {
		println "General${number} sending ${message}"
		long MINIMUM_TIME = 10
		long MAXIMUM_TIME = 20
		long timeTakenByMessage = ThreadLocalRandom.current().nextLong(
				MINIMUM_TIME, MAXIMUM_TIME)
		pool.schedule ( { other.send(message) }, timeTakenByMessage,
				TimeUnit.SECONDS )
	}
	def receiveMessage (message) {
		if (message == Actor.TIMEOUT) return
		println "General${number} received ${message}"
        if (message == "Interrupted") return
		m.updateMessage(message);
	}
}
def general1 = new General(number:1);
def general2 = new General(number:2, other:general1);
general1.other = general2;
def g = [general1, general2]
g*.start()
sleep(60000) //Run for these many milliseconds
g*.stop()

 

Stephane Vaucher replied on Thu, 2012/06/07 - 7:50pm

@Vijay I don't see why this code solves the problem. You didn't take into account the probability of capture of the messengers. That means that your algorithm is unsafe.

Vijay Nathani replied on Sat, 2012/06/30 - 3:21pm in response to: Stephane Vaucher

There is a timeout. If a general does not receive a message within that timeout, he will send the message. So it does take care of capture of messengers.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.