J2ME – Bomberman Math

Help Bomberman and his friends solve their math puzzles before they get beaten by the monsters. The game guarantees a playing experience that is intensive, addictive yet very simple.

WHAT’S BOMBERMAN MATH?
A lightweight version of the classic Bomberman game with powerups, multiple levels, unlockable characters and simple arithmetic problems. Get Bomberman Math for your mobile phone NOW. It’s FREE!!!

OVERVIEW

• Character select screen


The game initially has one playable character (Bomberman) and provides 4 unlockable characters as you progress through the game. Each character has its own set of levels and by finishing these levels, you unlock the next character.










• Quiz screen


The goal of the game is to solve a simple math quiz. You’re given an arithmetic operation with a missing digit in the result. If you find this digit during the game-play, you advance to the next level.






• Levels


Each character plays three different levels with increasing difficulty. The levels vary in the number of enemies and their speed. The last level has faster enemies. The game automatically saves your progress on your sd-card so that you can continue from where you started.








• Gameplay


You can move your character on the gird using the DIRECTIONAL buttons. Place bombs using the game FIRE button. Select the quiz answer using your game A button.
When bombs explode, fires spread in four directions killing and destroying anything they meet. When fire reaches a bomb it creates a “chain reaction” resulting in more destruction. When you destroy breakable blocks you either reveal a power-up, a digit for the puzzle solution or nothingness.
Enemy numbers increase per level and they move in totally random motion. So, good luck!
















• Powerups


Powerups are your allies against the barbarian monsters. To pick a powerup, simply walk on it. Power-ups disappear after some period of time, so pick them quickly. Whether you pick up a good or a bad powerup, you’ll get score points. The game has ten powerups generated randomly throughout the grid:

• fire-up – increases the bomb’s fire range by one point.
• fire-down – decreases the bomb’s fire range by one point.
• bomb-up – increases the number of bombs you can place simultaneously.
• bomb-down – decreases the number of bombs you can place simultaneously.
• speed-up – increases your speed by one point.
• speed-down – decreases your speed by one point.
• power-bomb – moves your bombs’ range points to the maximum.
• roll-bomb – allows you to throw bombs forward.
• no-roll-bomb – disables the previous powerup.
• pierce-bomb – allows your bombs’ fires to penetrate multiple walls.

PERMISSION DESCRIPTION

• Storage – SD-Card access. This is needed to store your progress.

DOWNLOAD EXECUTABLES

• GetJar – Bomberman-Math
• Mobile9 – Bomberman Math
• Google Code repository – Bomberman Math

SOURCE CODE

• Google Code repository – Bomberman Math

LCM Cardinality

Each pair of integers has a unique LCM:
lcm(a, b) = a * b / gcd(a, b)
Note that gcd(a, b) is unque too.
The LCM cardinality for an integer (n) is the number of distinct pairs of integers (a & b) that satisfy:
n = lcm(a, b)
A few Examples:

6	8	9	12
=====	=====	=====	=====
1, 6	1, 8	1, 9	1, 12
2, 6	2, 8	3, 9	2, 12
3, 6	4, 8	9, 9	3, 12
6, 6	8, 8	-----	4, 12
-----	-----	3, 3	6, 12
2, 3	2, 4		12,12
			-----
			2, 6
			3, 4
=====	=====	=====	=====
5	5	4	8

After observing the pattern, what we’re actually doing is: we are counting the number of factors of the integer n, HOWEVER, factors less than or equal to the root of n are counted twice (except the factor 1).
For example the cardinality of 16:

factor			1	2	4	8	16
factor <= 4		true	true	true	false	false
lcm cardinality	=	1 +	2 +	2 +	1 +	1	= 7

We can implement this either with pre-calculation or factorization.

Pre-calculation

#include <iostream>
#include <climits>
#include <cstdlib>
using namespace std;

const int N = 5000;
int lcmCardinality[N];

void calculate() {
	// 1
	lcmCardinality[1] = 1;
	for (int i = 2; i < N; ++i)
		lcmCardinality[i] = 0;
	// other
	for (int i = 2; i < N; ++i) {
		// less than root
		for (int j = i; j <= i * i && j <= N; j += i)
			lcmCardinality[j] += 2;
		// more
		if (i + 1 < INT_MAX / i)
			for (int j = i * (i + 1); j <= N; j += i)
				lcmCardinality[j]++;
	}
}

int main() {
	calculate();
	int n;
	while (cin >> n)
		cout << lcmCardinality[n] << endl;
	return 0;
}

530 – Binomial Showdown

This problem is identical to 369 – Combinations.

369 – Combinations

A combinations problem. Given N and R, find NCR.
There’s a variety of ways; The first two solutions are straight-forward computation of . The last two have some tricks:

A naive Java solution that uses big arithmetic:

import java.math.*;
import java.util.*;

public class Main {

	private static BigInteger C(BigInteger n, BigInteger r) {
		r = (r.compareTo(n.subtract(r)) > 0) ? n.subtract(r) : r;
		BigInteger num = BigInteger.ONE, den = BigInteger.ONE;
		while (!r.equals(BigInteger.ZERO)) {
			num = num.multiply(n); den = den.multiply(r);
			r = r.subtract(BigInteger.ONE); n = n.subtract(BigInteger.ONE);
		}
		return num.divide(den);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			BigInteger n = s.nextBigInteger(), r = s.nextBigInteger();
			if (n.equals(BigInteger.ZERO) && r.equals(BigInteger.ZERO))
				break;
			System.out.printf("%s things taken %s at a time is %s exactly.\n", n, r, C(n, r));
		}
	}
}

A similar C++ solution:

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

unsigned long long C(int n, int r) {
	r = min(n - r, r);
	long long out = 1;
	for (int i = 1; i <= r; ++i) {
		out *= n - r + i;
		out /= i;
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

A slower, but totally accepted, solution reduces the computations as you were doing it by hand; We have two arrays, one for the numerator and another for the denominator. We do a 2D loop to reduce the numerator with respect to the denominator and hence the answer. C++ implementation:

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

#define REDUCE(a, b) { int g = gcd(a, b); a /= g; b /= g; }

int num[100], den[100];
int numI, denI;

long long gcd(long long a, long long b) {
	long long t;
	while (a) { t = a; a = b % a; b = t; }
	return b;
}

long long C(int n, int r) {
	// fill arrays
	r = min(n - r, r);
	numI = denI = 0;
	while (r) { num[numI++] = n--; den[denI++] = r--; }
	// reduce & compute
	long long out = 1;
	for (int i = 0; i < numI; ++i) {
		for (int j = 0; j < denI; ++j)
			REDUCE(num[i], den[j]);
		out *= num[i];
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

The last solution has the same complexity as the first two. It uses Pascal’s Triangle for computing combinations. C++ implementation:

#include <cstdio>
using namespace std;

#define N 128

long long pascalTri[N * (N + 1) / 2];

void fillPascal() {
	for (int l = 0, lStart = 0; l < N; ++l, lStart += l) {
		pascalTri[lStart] = pascalTri[lStart + l] = 1;
		for (int i = 1; i < l; ++i)
			pascalTri[lStart + i] = pascalTri[lStart + i - l] + pascalTri[lStart + i - l - 1];
	}
}

int main() {
	fillPascal();
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, pascalTri[n * (n + 1) / 2 + r]);
	return 0;
}

11621 – Small Factors

A –supposed– math problem. But it turns out to be an ad-hoc problem.
Given an integer n, find the next integer m that’s in the set :
. In other words, the factors of m are only 2’s and 3’s.
A brute-force solution loops from n and onwards until it finds m. m is the first integer that after factorization with respect to 2 and 3, becomes 1 (no other factors remain). This gets a time limit exceeded.
Another brute-force solution does the same, however, for every input, it generates valid m‘s (by successive multiplications by 2 and 3) until one of them exceeds or equals n. After all possible optimizations that I could think of, this solution, also, gets a time limit exceeded.
After some thought, since m is only composed of 2’s and 3’s, for a number to match m‘s criterion, it must have
gcd(m, 2 * 2 * 2 ... * 2) * gcd(m, 3 * 3 * 3 ... * 3) = m
So, i did the same loop but with the former stopping condition. Still, a time limit exceeded. Anyways, here’s the C++ implementation:

#include <cstdio>
using namespace std;

#define P2 1073741824
#define P3 1162261467

int gcd(int a, int b) {
	int t;
	while (b) { t = a; a = b; b = t % b; }
	return a;
}

int n, m;

int main() {
	while (scanf("%d", &n) == 1 && (m = n)) {
		while(gcd(m, P2) * gcd(m, P3) != m)
			++m;
		printf("%d\n", m);
	}
	return 0;
}

Ironically, the only accepted solution I could get was to pre-calculate the set ! Then you have to find m that’s larger than or equal to input (n). Pre-calculation it is! C++ rank 58:

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long int64;

int64 p2[32] = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096,
		8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608,
		16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648ll };
int64 p3[21] = { 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323,
		4782969, 14348907, 43046721, 129140163, 387420489, 1162261467, 3486784401ll };
int64 n;
vector<int64> q;

int main() {
	// pre-calculate
	for (int i = 0; i < 32; ++i)
		for (int j = 0; j < 21; ++j)
			q.push_back(p2[i] * p3[j]);
	sort(q.begin(), q.end());
	// solve
	while (scanf("%lld", &n) == 1 && n)
		printf("%lld\n", q[lower_bound(q.begin(), q.end(), n) - q.begin()]);
	return 0;
}