503 Service Unavailable

2007-09-24

Counting Triangles (2)

Filed under: Programming — rg3 @ 17:36

In connection with the previous post, reader Álvaro has pointed out two easy simplifications I missed completely, and they make the program much easier from the user’s point of view.

First, the need to input segments is superfluous. Passing the straights alone is enough. You can get the segments, if you want, by combining the vertex of each straight in couples.

Second, on top of that, generating the segments isn’t really needed from the programming perspective, as you can easily test that any given segment (a, b) exists if those two vertex appear in the same straight, for any of the available straights.

Applying the changes to the source code is easy and the final result is a shorter program that only needs to be passed the list of straights in the same format as the previous program. This means the user only has to identify the vertex and enumerate the straights, writing them to a text file.

Source code (public domain)

#!/usr/bin/env python
import operator
import sys

# Recursive combinations function
def combs_aux(elems, comb_len, depth, start_at, cur_comb, output):
  if depth >= comb_len:
    output.append(tuple(cur_comb))
    return

  for x in xrange(start_at, len(elems) - (comb_len - depth) + 1):
    cur_comb[depth] = elems[x]
    combs_aux(elems, comb_len, depth + 1, x + 1, cur_comb, output)

# Wrapper to ease calls
def combinations(elems, comb_len):
  elems = list(elems)
  output = []
  combs_aux(elems, comb_len, 0, 0, [None] * comb_len, output)
  return output

# Auxiliar: does every edge exist?
def edges_exist((a, b, c), straights):
  one = [s for s in straights if a in s and b in s]
  two = [s for s in straights if a in s and c in s]
  three = [s for s in straights if b in s and c in s]
  return (len(one) > 0 and len(two) > 0 and len(three) > 0)

# Auxiliar: all vertex in the same straight?
def same_straight((a, b, c), straights):
  return (len([s for s in straights if a in s and b in s and c in s]) > 0)

# Read files
try:
  straights_str = file(sys.argv[1], 'r').read()
except (IOError, OSError, IndexError):
  sys.exit('Usage: %s straights_file' % sys.argv[0])

# Straights
straights_lines = [x for x in straights_str.split('\n') if len(x) != 0]
straights_strlists = [x.split() for x in straights_lines]
straights_lists = [[long(x) for x in lst] for lst in straights_strlists]
straights = set(tuple(x) for x in straights_lists if len(x) != 0)

# Extract vertex
vertex = set(reduce(operator.concat, straights_lists, []))

# Generate combinations and filter by existing edges and straights
candidates = combinations(vertex, 3)
candidates = [x for x in candidates if edges_exist(x, straights)]
triangles = [x for x in candidates if not same_straight(x, straights)]

# Print triangles and total count
if len(triangles) > 0:
  print '\n'.join('(%s, %s, %s)' % (a, b, c) for (a, b, c) in triangles)
print 'Number of triangles: %s' % len(triangles)

2007-09-20

Counting Triangles

Filed under: Programming — rg3 @ 17:05

Update: do not forget to read Counting Triangles (2) after this post.

Some days ago I was watching a movie on TV and I fell asleep just after it finished. When I woke up a couple of hours later it was already the time of participative quizs. These are TV shows in which a game is proposed (usually a very simple game, like a word search) and people call the program to give answers and get a monetary prize. I won’t give much more details about how these shows work and get your money. Yesterday there was, however, a mildly interesting game when I woke up. They presented a geometric figure like the following one:

The goal was to find out the amount triangles present in that image. To ease things from our point of view, we are going to number the vertex.

Counting the number of triangles by hand is not an easy task at all, and it’s extremely easy to get lost in the process. There is obviously an outside triangle (0, 2, 9), and there are twelve inside triangles formed by one piece each ((0, 1, 3), (1, 2, 4), etc). But there are many more triangles. For example, (1, 6, 8) is also a triangle, and (0, 8, 9) is a valid triangle too. Hopefully, you start to realize how counting the triangles is a very complex process. Just so you get an idea, there are 47 triangles in the sample figure. It looks easy, but it’s not.

This prompted me to try to create a small Python program to count them. It wasn’t difficult at all. I had it running flawlessly in less than 30 minutes. The figure can be understood as a graph from the mathematical point of view, but I’m going to take a simpler approach anybody can understand. The program works with 3 different kinds of elements: vertex, segments and straights.

Vertex

Vertex are just ending points for a segment in the figure. It’s quite simple to understand, because in the second image we numbered the vertex so you can clearly see them. When you are given a figure, the first step is to number each vertex, taking care not to leave any behind.

Segments

A segment is specified as a couple of vertex. Enumerating each segment is the most complex action you need to perform by hand, but compared to counting triangles it’s quite easy. Take the top edge in the figure. In it, we have three vertex called 0, 1 and 2. There are 3 segments in that edge. The obvious segments (0, 1) and (1, 2), but there’s also (0, 2). I’ve come to the conclusion that the easiest method to enumerate segments is to take the vertex in order and see if there’s a straight line that joins it with every vertex of higher index. You start by 0 and see if there’s a line that joins it with 1, 2, …, 9. You follow by 1 and try to see if there are lines that join it with 2, 3, …, 9. Etc. In the sample figure above, there are 36 segments, listed below.

0 1 
0 2
0 3
0 5
0 6
0 8
0 9
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 4
2 5
2 6
2 8
2 9
3 5
3 6
3 8
4 5
4 6
4 8
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9

Straights

Straights are groups of vertex forming one single line. You can call them lines if you prefer. They are very easy to count. In the sample figure there are 9 straights or lines, listed below.

0 1 2
0 3 5 8
0 6 9
1 3 6
1 4 8
1 5 7 9
2 4 5 6
2 8 9
6 7 8

As you see, the top edge (0, 1, 2) is one of them, but you also have the straight (1, 5, 7, 9) in the middle of the sample figure, etc. Straights play an important part in our program, as you’ll see.

What the program does

The program needs two files as input. The first file is the segments file. Its format is the one I used above, with pairs of vertex, one pair per line. It then needs a second file containing the straights, also in the format I used above. A set of vertex each line, describing one straight each.

The program first proceeds to parse the contents of both files, extracting pairs of numbers and saving them to a set named arches, and the tuples of vertex forming the straights, saving the tuples to a set named straights. The procedure it follows then is very simple.

First, from the segments and straights it forms a list of vertex, and finds the combinations of those elements in groups of 3. Each one of those combinations is a candidate, a possible triangle, that needs to be confirmed. The confirmation comes in two steps. For every combination (a, b, c) it checks if the pairs (a, b), (a, c) and (b, c) are present in the set of segments. Finally, it checks that there are no straights that contain the 3 elements (a, b, c), which would mean that there is no real triangle, but just a straight line. For example, combination (0, 1, 2) is a candidate for which (0, 1), (0, 2) and (1, 2) are segments, as we explained above. However, there is a straight line that contains the elements (0, 1, 2). It is precisely the straight (0, 1, 2). That makes (0, 1, 2) an invalid triangle, because it’s in fact a straight line.

The program finally prints a list of triangles and the total count.

Program code (public domain)

#!/usr/bin/env python
import sys

# Recursive combinations function
def combs_aux(elems, comb_len, depth, start_at, cur_comb, output):
  if depth >= comb_len:
    output.append(tuple(cur_comb))
    return

  for x in xrange(start_at, len(elems) - (comb_len - depth) + 1):
    cur_comb[depth] = elems[x]
    combs_aux(elems, comb_len, depth + 1, x + 1, cur_comb, output)

# Wrapper to ease calls
def combinations(elems, comb_len):
  elems = list(elems)
  output = []
  combs_aux(elems, comb_len, 0, 0, [None] * comb_len, output)
  return output

# Read files
try:
  segments_str = file(sys.argv[1], 'r').read()
  straights_str = file(sys.argv[2], 'r').read()
except (IOError, OSError, IndexError):
  sys.exit('Usage: %s segments_file straights_file' % sys.argv[0])

try:
  segments_lines = [x for x in segments_str.split('\n') if len(x) != 0]
  segments_num_str = [x.split() for x in segments_lines]
  segments = [(long(a), long(b)) for [a, b] in segments_num_str]
except (ValueError, IndexError):
  sys.exit('Error parsing segments file')

# Arches
arches = set()
for seg in segments:
  arches.add(tuple(sorted(seg)))

# Straights
straights_lines = [x for x in straights_str.split('\n') if len(x) != 0]
straights_strlists = [x.split() for x in straights_lines]
straights_lists = [[long(x) for x in lst] for lst in straights_strlists]
straights = set(tuple(sorted(x)) for x in straights_lists if len(x) != 0)

# Extract vertex
vertex = set()
for arch in arches:
  vertex.update(set(arch))
for st in straights:
  vertex.update(set(st))

# Generate combinations and filter them by existing arches and straights
candidates = combinations(vertex, 3)
candidates = [tuple(sorted(x)) for x in candidates]
candidates = [(a, b, c) for (a, b, c) in candidates
    if (a, b) in arches and (b, c) in arches and (a, c) in arches]
triangles = [(a, b, c) for (a, b, c) in candidates
    if len([s for s in straights if a in s and b in s and c in s]) == 0]

# Print triangles and total count
print '\n'.join('(%s, %s, %s)' % (a, b, c) for (a, b, c) in triangles)
print 'Number of triangles: %s' % len(triangles)

2007-09-05

Multiples of 3

Filed under: Maths — rg3 @ 22:32

You may have heard that a number is a multiple of 3 if the sum of its digits is also a multiple of 3. For example, take number 4379. Let’s see: 4 + 3 + 7 + 9 = 23. If you still don’t know, repeat again: 2 + 3 = 5. No, it’s not. Easy method, indeed, and recursive. When a number is a multiple of 3, the sum of its digits is also a multiple. If the sum of its digits is a multiple, the sum of the sum of its digits is also a multiple, etc. Somebody asked me today why that method worked. I thought about it for some minutes and came to a practical explanation. After that I headed to Dr. Math to find a mathematical answer but the explanation I found didn’t satisfy me completely.

It turns out the rule is not valid for 3 only. It’s also valid for 9. Numbers 3 and 9 have something in common: the remainder of the division 10/9 and 10/3 is 1. The practical explanation I thought gave me the clue the method works with any base and any digit for which the remainder of the division (base / digit) is 1. From now on we’ll call that operation by its name, which is “modulo” and we’ll use the symbol % to represent it. The method works when base % digit = 1. For example, in hexadecimal (base 16) you can apply this method to know if the number is a multiple of 3, 5 or F (15 in decimal).

Practical explanation

Let’s use base 10 and number 3 as an example. In the way we represent numbers, we have 10 digits (0 to 9). A number is represented by a sequence of digits whose value is bigger the more to the left it is. In number 234, the digit 2 represents the value 200, the digit 3 represents the value 30 and the digit 4 represents the value 4. When counting from zero, we start by increasing the rightmost digit until it reaches the value 10. When that happens, the digit rolls over back to 0 and we increase the digit to its left. So if we try to write the multiples of 3, we have a coincidence that makes the method work. We start by 03, then 06, then 09 and… whoops, the next will be twelve, but the rightmost digit rolls over to 0 when increased once, and to 2 when we increase it twice more as needed. The digit to its left is increased. So we jump from 09 to 12. This increase of the digit to the left compensates the value we lost in the rightmost digit as when multiplying the highest possible multiple of 3 before 10 is precisely 9, one less. So in the first round we passed by 3, 6 and 9. In the second round, thanks to 10 % 3 = 1, we are going to pass by those minus 1: 2, 5, 8. Yet the sum of the digits is still 3 because the digit 1 appears to their left forming the numbers 12, 15 and 18. In the next round we pass through digits 1, 4 and 7. The sum is still 3 because the leftmost digit will be increased to 2 to give numbers 21, 24 and 27. In the next number we go back to the original digits (plus 0) but the leftmost digit is increased again for the third time, resulting in a multiple of 3: 30, 33, 36, 39. Well, this is pretty easy to understand.

Now, what happens with the rest of the digits? The rightmost digit is always increased this way, but the rest of the digits are increased normally one by one until they roll over again. For example, what happens at 99? Sure, the rightmost 9 changes to 2 and, to compensate, we would have to increase the leftmost 9 to “ten”, but we can’t do that. The 9 on the left will become 0 and a new 1 will appear on the left, to form number 102. How is the condition still true? Let’s see. If the rightmost 9 rolls to 2, the leftmost 9 should become “ten” for the condition to be met. Instead, its value becomes 0. That’s 10 less than what we expected. Yet the rightmost digit is increased by 1, so we’ve got 10 less than expected on the middle digit, but one more on the leftmost digit. Summing up, we have a sum that falls short by 9 (in general, base - 1), which is a multiple of 3! From (9,9), total sum 18, we wanted to go to (10, 2), which is impossible, so we went to (1, 0, 2). (10, 2) would sum 12. (1, 0, 2) sums 3, that is, 9 less as we just explained. Sometimes this event triggers more than once. Let’s take 9999. The last 9 rolls over to 2. It would be fine if the 9 to its left becomes 0 and we increase the digit to the left of that 9. Which we can do… oops! No, we can’t make that, but we can make it 0 and make the leftmost digit a… oops! No, it will have to become 0 and we’ll add a 1 to the left. Result: 10002. The property is kept.

The only question remaining in your head could be (maybe not): when the value of the sum is decreased as we just see, isn’t it possible to be left with a number that is not a multiple of 3? But the answer is no. If the sum is a multiple of 3 and we substract 9, the resulting sum is either 0 (which is impossible because every number greater than 0 has at least a nonzero digit) or another multiple of 3, by definition. So it always works.

Mathematical explanation: enter modular arithmetic

Dr. Math explains this very easily. He says: let’s have a number formed by two digits: ab. The value of that number is, in decimal, 10*a + b. Now, 10*a + b = (9*a + a) + b = 9*a + (a + b). 9*a is a multiple of 3 because it’s a multiple of 9. So 10*a + b (our number) is a multiple of 3 if (a + b) (the sum of its digits) is also a multiple of 3. The same can be exposed for a number composed of 3, 4… N digits. For example, for 3 digits abc, the number can be expressed as 99*a + 9*b + (a + b + c).

Let’s generalize that for any base and any digit for which (base % digit) = 1. Let’s call the base B and the digit D. This number has digits numbered from 0 (rightmost) to N (leftmost). These digits are called X0… XN. This number can be expressed as SUM { B^i * Xi for i in [0, N] }. As Dr. Math showed, we can also decompose this sum as SUM { (B^i - 1) * Xi for i in [1, N] } + SUM { Xi for i in [0, N] }. The second part is the sum of its digits. If we can prove that the first part is a multiple of D, we can conclude that the sum of the digits must be then a multiple of D too. To prove that the first part is a multiple of D, we’ll try to prove that (B^i - 1) is a multiple of D. If that’s true, as it seems to be (9, 99, 999 were multiples of 3), then (B^i - 1) * Xi is a multiple too, and the sum of them is a multiple too. So the key here is to prove that (B^i - 1) is a multiple of D for any i. If (B^i - 1) is a multiple of D ((B^i - 1) % D = 0), then, by definition of how the division operation works, B^i % D = 1. We need to prove that B^i % D = 1 knowing that B % D = 1.

Let’s stop here for a moment and remember the rules of modular arithmetic for sums. (a + b) % c = ((a % c) + (b % c)) % c. This is more or less trivial. Let’s suppose you have to divide the contents of two bags, one with a items and the other one with b items. This rule tells us that to know the remainder of that division we can put all the items together and divide, or we could also divide the contents of each bag individually, put together the remainders and divide again. This works for any number of “bags”. Let’s translate this to multiplication. (a * b) % c = (a + ... (b times) ... + a) % c = ((a % c) + ... (b times) ... + (a % c)) % c = ((a % c) * b) % c. And finally translate this rule to powers, what we need: B^i % D = (B * B^(i - 1)) % D = ((B % D) * B^(i - 1)) % D. But we know that (B % D) == 1, so this is equal to B^(i - 1) % D. So we have that B^i % D = B^(i - 1) % D = ... = B % D = 1. QED.

With our notation system, under any base, if the remainder of the division of the base by a digit is 1, the sum of the digits in any multiple of that original digit is also a multiple of the original digit.

Note that in the last step of the demonstration we could have concluded that B^0 % D = 1 % D = 1. This is not a problem, because the only digit that wouldn’t allow this is 1, but in that case B % D couldn’t be 1 either (one of our conditions). It would be 0.

Blog at WordPress.com.