Minomol
Apr '09

I need a little help , here it is:

On the planet Gliese 581 there are two nations, which fight all the
time...as soon as one of the sides is dominant in numbers, it starts
attacking the second one. On peace discussions they decided, that the
solution is splitting the population in such way, that no adjacent
cities will have the same nation in them.(In ine city there are only
inhabitants from one nation.)

In the function input there is the adjacency of cities assigned by a
list [[m11,m21],[m12,m22],...,[m1N,m2N]], where the pairs [m1i,m2i]
says, that the cities m1i and m2i are adjacent.

The function result gives TRUE, if it is possible to inhabit all
cities, else it gives FALSE.

example:
peaceAble [[1,2],[2,3],[3,5],[4,5],[10,2],[11,3],[5,6],[8,9],[7,8],
[4,7],[5,8],[8,12]] ==> True
peaceAble [[1,2],[2,3],[3,1]] ==> False

Anyone can help me?

  • created

    Apr '09

  • last reply

    Nov '09
  • 1

    reply

  • 218

    views

  • 2

    users

8 months later
ileq
Nov '09

This isn't too hard because there are only 2 nations. The basic idea is that it doesn't matter which nation is in which city so long as all the neighboring cities have the other nation. The easiest way I can think to do that would be like this:

Say you get the input [[1,2],[1,3],[2,4],[3,4],[3,5],[5,2]]. Let's call the two nations A and B.
Arbitrarily assign nation A to city 1: 1A
In order for there to be peace you must also then have 2B and 3B because cities 2 and 3 are adjacent to city 1.
Next you have 4A and 5A. City 4 have been fully accounted for, but there is still one more assignment for city 5, namely [5,2]. This requires nation B to be in city 2, which we already know is true.
Therefore this arrangement can have peace.

The general idea is that you assign a nation to any of the cities and check to see if that forces any other cities into conflict.

-ileq