1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Closed Loop | 22 Oct 2009

Discussion in '$1 Daily Competition' started by shabbir, Oct 22, 2009.

  1. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    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.

    [​IMG]

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

    SaswatPadhi ~ Б0ЯИ Τ0 С0δЭ ~

    Joined:
    May 5, 2009
    Messages:
    1,343
    Likes Received:
    55
    Trophy Points:
    0
    Occupation:
    STUDENT !
    Location:
    Orissa, INDIA
    Home Page:
    OMG !! Number of closed loops ... that would be a huge number. :crazy:
     
  3. neo_vi

    neo_vi Member

    Joined:
    Feb 1, 2008
    Messages:
    722
    Likes Received:
    15
    Trophy Points:
    18
    Occupation:
    Software engineer
    Location:
    Earth
    Home Page:
    yes saswat. U re rit. i just tried to compute. Then realized the same. I guess it wud be more than 50
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Does it include crossovers, such as the large figure-8 through the triangles numbered 1 9 10 4?
     
  5. nimesh

    nimesh New Member

    Joined:
    Apr 13, 2009
    Messages:
    770
    Likes Received:
    20
    Trophy Points:
    0
    Occupation:
    Oracle Apps Admin
    Location:
    Mumbai
    Home Page:
    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?
     
  6. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    yeah i've had a look but am getting nowhere quickly
     
  7. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Got it: 3165.
     
  8. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Or 108 if crossovers are disallowed.
     
  9. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    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
    
     
    nimesh likes this.
  10. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    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.
     
  11. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Yes, it does apply to the larger set. Oh well.
     
  12. nimesh

    nimesh New Member

    Joined:
    Apr 13, 2009
    Messages:
    770
    Likes Received:
    20
    Trophy Points:
    0
    Occupation:
    Oracle Apps Admin
    Location:
    Mumbai
    Home Page:
    I won't fight over all those posts, whatever is the right answer :D
     
  13. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,292
    Likes Received:
    365
    Trophy Points:
    83
    Nor would I :?
     

Share This Page