Go4Expert

Go4Expert (http://www.go4expert.com/)
-   $1 Daily Competition (http://www.go4expert.com/contests/daily-competition/)
-   -   Closed Loop | 22 Oct 2009 (http://www.go4expert.com/contests/closed-loop-22-oct-2009-t19855/)

shabbir 22Oct2009 17:42

Closed Loop | 22 Oct 2009
 
Now on 20th Oct I had an interesting question and this is also a variant of the same.

Find the number of closed loop in the figure.

http://www.go4expert.com/attachment....1&d=1256047616

Numbers and G4EF.com are for reference and not the part of actual puzzle. You know why ?

SaswatPadhi 22Oct2009 19:02

Re: Closed Loop | 22 Oct 2009
 
OMG !! Number of closed loops ... that would be a huge number. :crazy:

neo_vi 22Oct2009 19:10

Re: Closed Loop | 22 Oct 2009
 
yes saswat. U re rit. i just tried to compute. Then realized the same. I guess it wud be more than 50

xpi0t0s 22Oct2009 19:54

Re: Closed Loop | 22 Oct 2009
 
Does it include crossovers, such as the large figure-8 through the triangles numbered 1 9 10 4?

nimesh 22Oct2009 20:00

Re: Closed Loop | 22 Oct 2009
 
whatever the answer may be, the question is very good :)

@shabbir: by closed loop you mean that triangle of 1,5,3 would be one closed loop (even if take it as 1,3,5 or 5,3,1 or 5,1,3...)

and what about the joint in between 1,6 and 3,4. there are some loose endings. :D

anyone's trying?

xpi0t0s 22Oct2009 21:54

Re: Closed Loop | 22 Oct 2009
 
yeah i've had a look but am getting nowhere quickly

xpi0t0s 23Oct2009 13:29

Re: Closed Loop | 22 Oct 2009
 
Got it: 3165.

xpi0t0s 23Oct2009 14:01

Re: Closed Loop | 22 Oct 2009
 
Or 108 if crossovers are disallowed.

xpi0t0s 23Oct2009 14:02

Re: Closed Loop | 22 Oct 2009
 
Any polygonal area can be subdivided into triangles: that's what shabbir has done here.
A closed loop comprises a single small triangle, or two or more triangles that are connected together. For this I have assumed that crossovers are OK, so 2-3 is a closed loop, as is 6-9-2.
So I created a data structure that lists what triangles are connected to what:
triangle 1 is connected to triangles 6, 7, 11, 9, 12, 8, 2;
triangle 2 is connected to triangles 1, 9, 12, 8, 3;
and so on.
This was done as a bitmask so we can determine if any two triangles are connected just by doing a bitwise AND.
For example is 1 connected to 4? The bitmask for triangle 1 is
1 1011 1100 0100
(remember the rightmost bit is bit 0, not bit 1, and the triangles are numbered from 1). bit 4 is
0 0000 0001 0000
and you can see that ANDing these two together will be zero.

On the other hand is 1 connected to 9? bit 9 is
0 0010 0000 0000 and you can see an AND will be non-zero.

So how do we determine if a set of triangles is connected?
It occurred to me we could look at each triangle in turn, and if it is connected to any other, we can eliminate it from the set. So for example 6-9-2: 6 is connected to 9 so we can eliminate it, leaving 9-2. 9 is connected so eliminate it. This leaves 2, which is a single bit so this is a connected set.
Conversely 6-5-3-2 reduces to 5-3-2 then to 5-2, which is 2 bits, so this is a disconnected set.

Code:

void loops()
{
        int connections[13];
        connections[1]=bit6+bit7+bit9+bit12+bit8+bit2;
        connections[2]=bit1+bit9+bit12+bit8+bit3;
        connections[3]=bit2+bit8+bit12+bit10+bit4;
        connections[4]=bit5+bit7+bit11+bit10+bit12+bit8+bit3;
        connections[5]=bit6+bit7+bit11+bit10+bit4;
        connections[6]=bit1+bit9+bit11+bit7+bit5;
        connections[7]=bit6+bit1+bit9+bit11+bit10+bit4+bit5;
        connections[8]=bit1+bit9+bit12+bit10+bit4+bit3+bit2;
        connections[9]=bit1+bit2+bit8+bit12+bit10+bit11+bit7+bit6;
        connections[10]=bit4+bit5+bit7+bit11+bit9+bit12+bit8+bit3;
        connections[11]=bit1+bit9+bit12+bit10+bit4+bit5+bit7+bit6;
        connections[12]=bit1+bit9+bit11+bit10+bit4+bit3+bit8+bit2;

        int connected=0;
        int rowcount=0;
        for (int i=1; i<4096; i++)
        {
                int test=i<<1;
                int bitval=2;
                for (int bit=1; bit<=12; bit++, bitval<<=1)
                {
                        if (test & bitval)
                        {
                                // is triangle[bit] connected to any other?
                                if (test & connections[bit])
                                {
                                        // yes: remove it from the set
                                        test ^= bitval;
                                }
                        }
                }
                int cb=countbits(test);
                if (cb==1)
                {
                        //printf("1 bit left so we must have a connected set: 0x%04x\n",i);
                        printf("%04x ", i<<1);
                        rowcount++;
                        if (rowcount>12)
                        {
                                rowcount=0;
                                printf("\n");
                        }
                        connected++;
                }
                else if (cb==0)
                {
                        //printf("0 bits left - this shouldn't be possible: 0x%04x\n",i);
                }
                else
                {
                        //printf("2 bits left - this means we have a disjoint set: 0x%04x\n",i);
                }
        }
        printf("\nNumber of connected sets: %d\n",connected);
}

Output (partial):
Code:

0002 0004 0006 0008 000c 000e 0010 0018 001c 001e 0020 0030 0038
003c 003e 0040 0042 0060 0062 0070 0072 0078 007a 007c 007e 0080
0082 0090 0092 0098 009a 009c 009e 00a0 00a2 00b0 00b2 00b8 00ba
00bc 00be 00c0 00c2 00d0 00d2 00d8 00da 00dc 00de 00e0 00e2 00f0
00f2 00f8 00fa 00fc 00fe 0100 0102 0104 0106 0108 010a 010c 010e
(snip)
1f8c 1f8e 1f90 1f92 1f94 1f96 1f98 1f9a 1f9c 1f9e 1fa0 1fa2 1fa4
1fa6 1fa8 1faa 1fac 1fae 1fb0 1fb2 1fb4 1fb6 1fb8 1fba 1fbc 1fbe
1fc0 1fc2 1fc4 1fc6 1fc8 1fca 1fcc 1fce 1fd0 1fd2 1fd4 1fd6 1fd8
1fda 1fdc 1fde 1fe0 1fe2 1fe4 1fe6 1fe8 1fea 1fec 1fee 1ff0 1ff2
1ff4 1ff6 1ff8 1ffa 1ffc 1ffe
Number of connected sets: 3165

If the triangles must share a side to be considered connected, then we can use exactly the same code and just change the data:
Code:

        connections[1]=bit9;
        connections[2]=bit8;
        connections[3]=bit8;
        connections[4]=bit10;
        connections[5]=bit7;
        connections[6]=bit7;
        connections[7]=bit6+bit11+bit5;
        connections[8]=bit12+bit3+bit2;
        connections[9]=bit1+bit12+bit11;
        connections[10]=bit4+bit11+bit12;
        connections[11]=bit9+bit10+bit7;
        connections[12]=bit9+bit10+bit8;

Output (much less this time, of course, so this is complete)
Code:

0002 0004 0008 0010 0020 0040 0080 00a0 00c0 00e0 0100 0104 0108
010c 0200 0202 0400 0410 0800 0880 08a0 08c0 08e0 0a00 0a02 0a80
0a82 0aa0 0aa2 0ac0 0ac2 0ae0 0ae2 0c00 0c10 0c80 0c90 0ca0 0cb0
0cc0 0cd0 0ce0 0cf0 0e00 0e02 0e10 0e12 0e80 0e82 0e90 0e92 0ea0
0ea2 0eb0 0eb2 0ec0 0ec2 0ed0 0ed2 0ee0 0ee2 0ef0 0ef2 1000 1100
1104 1108 110c 1200 1202 1300 1302 1304 1306 1308 130a 130c 130e
1400 1410 1500 1504 1508 150c 1510 1514 1518 151c 1600 1602 1610
1612 1700 1702 1704 1706 1708 170a 170c 170e 1710 1712 1714 1716
1718 171a 171c 171e
Number of connected sets: 108


xpi0t0s 23Oct2009 14:16

Re: Closed Loop | 22 Oct 2009
 
Oops, found a bug. 10-11-12 is connected but excluded from the last set (bitmask 1c00).
Don't think this bug applies to the larger set though, but checking.


All times are GMT +5.5. The time now is 23:03.