## June 21, 2008

at
Saturday, June 21, 2008
Labels:
Computer Science,
Java,
Lisp,
Python,
Thinking in Java
Posted by
Billy

Chapter: Controlling Execution

Exercise 10: (5) A vampire number has an even number of digits and is formed by multiplying a pair of numbers containing half the number of digits of the result. The digits are taken from the original number in any order. Pairs of trailing zeroes are not allowed. Examples include:

1260 = 21 * 60

1827 = 21 * 87

2187 = 27 * 81

Write a program that finds all the 4-digit vampire numbers.

The straight foward way to solve this problem is through brute force: check every four digit number and test if it qualifies as a vampire number. If we write out all the ways to multiple two 2-digit numbers we can see a pattern that fits nicely into loops. Let a, b, c and d be the digits of a four-digit number. The possible vampire factors (called "fangs") are:

ab * cd

ab * dc

ba * cd

ba * dc

ac * bd

...

ad * bc

...

and so forth, for a total of 12 combinations. The solutions below use multiple for-loops to test all the combinations by swapping the digits. The inner for-loop swaps the third and fourth digits, the middle for-loop swaps the first and second digits, and the outer for-loop swaps the second digit with either the third or fourth digit. This tests all the combinations in the same sequence as the pattern above. (Note, I have not verified the results. See the bottom of this post for the numbers I got).

In Java:

package chapter.controllingExecution;

public class Exercise10 {

public static void main(String[] args) {

for (int i = 1000; i < 10000; i++)

if (isVampire(i))

System.out.println(i);

}

static boolean isVampire(int num) {

int temp;

int a = Integer.parseInt((String.valueOf(num)).substring(0, 1));

int b = Integer.parseInt((String.valueOf(num)).substring(1, 2));

int c = Integer.parseInt((String.valueOf(num)).substring(2, 3));

int d = Integer.parseInt((String.valueOf(num)).substring(3));

for (int i = 3; i <= 5; i++) {

for (int y = 1; y <= 2; y++) {

for (int z = 1; z <= 2; z++) {

if (num == combineNumbers(a, b) * combineNumbers(c, d))

return true;

temp = c;

c = d;

d = temp;

}

temp = a;

a = b;

b = temp;

}

if (i == 3) {

temp = b;

b = c;

c = temp;

} else {

temp = b;

b = d;

d = temp;

}

}

return false;

}

static int combineNumbers(int x, int y) {

return Integer.parseInt(Integer.toString(x) + Integer.toString(y));

}

}

In Python:

for i in range(1000, 10000):

if isVampire(i):

print i

def combineNumbers(a, b):

return int(str(a) + str(b))

def isVampire(num):

a = str(num)[0]

b = str(num)[1]

c = str(num)[2]

d = str(num)[3]

for i in 3,4,5:

for y in 1,2:

for z in 1,2:

if num == combineNumbers(a,b) * combineNumbers(c,d):

return True

c, d = d, c

a, b = b, a

if i == 3:

b, c = c, b

else:

b, d = d, b

return False

In Lisp:

(loop for i from 1000 to 10000 do

(if (vampire? i)

(print i)))

(defun combine-numbers (a b)

(+ (* a 10) b))

(defun vampire? (number)

(let* ((num (write-to-string number))

(a (parse-integer (subseq num 0 1)))

(b (parse-integer (subseq num 1 2)))

(c (parse-integer (subseq num 2 3)))

(d (parse-integer (subseq num 3 4)))

(temp 0)

(result nil))

(loop for i in '(3 4 5) while (eq result nil) do

(progn (loop for y in '(1 2) while (eq result nil) do

(progn (loop for z in '(1 2) while (eq result nil) do

(if (eq number

(* (combine-numbers a b)

(combine-numbers c d)))

(setq result t)

(setq temp c

c d

d temp)))

(setq temp a

a b

b temp)))

(if (eq i 3)

(setq temp b

b c

c temp)

(setq temp b

b d

d temp))))

result))

The python solution is my favorite because of the simple swapping feature. My results:

1260

1395

1435

1530

1827

2187

6880

Subscribe to:
Post Comments (Atom)

## 0 comments:

Post a Comment