Google har sat gang i en vaskeægte skattejagt. Hvad kisten indeholder er fornuværende stadig en velbevaret hemmelighed, og det famøse X på skattekortet jagtes af mange. Du kan selv deltage her og du kan læse mere om konkurrencen på denne side.
Første etape af udfordringen er at svare på hvor mange unikke stier der er for en robot der kun kan bevæge sig henholdsvist ned og mod højre, når denne starter i øverste venstre hjørne af et skakbræt af størrelsen W x H. Tallene W og H oplyses naturligvis forskelligt pr. forsøg man foretager.
Set fra et IT-synspunkt, er det fælles for løsningerne at det endelige tal overstiger almindelige heltals typer, så man skal benytte bit manipulation eller f.eks. BigInteger klassen fra Java for at kunne rumme det endelige tal.
Hinnerup Net ApS har hastigt strukket denne lille Java sag på 42 linier sammen, som kan løse opgaven uanset W og H (dog givet W og H er positive heltal):
Klik her for at se Java koden – spoiler advarsel!
package GoogleTreasureHunt2008;
import java.math.BigInteger;
public class GoogleBotSolver
{
private BigInteger[][] results;
public GoogleBotSolver(int w, int h)
{
results = new BigInteger[w][h];
for (int x = 0; x < w; x++)
{
for (int y = 0; y < h; y++)
{
results[x][y] = null;
}
}
System.out.println(C(w - 1, h - 1).toString());
}
private BigInteger C(int x, int y)
{
if (results[x][y] != null) return results[x][y];
BigInteger res;
if (x == 0 && y == 0)
{
res = BigInteger.ZERO;
}
else if (x == 0 || y == 0)
{
res = BigInteger.ONE;
}
else
{
res = C(x - 1, y).add(C(x, y - 1));
}
results[x][y] = res;
return res;
}
public static void main(String[] args)
{
GoogleBotSolver gbs = new GoogleBotSolver(38, 58);
}
}
Svaret for W=38 og H=58 som herover er 194937478788574958222679204. Så robotten har rigtigt nok et par muligheder at vælge imellem.
Opgaven er iøvrigt en velkendt afart af Pascal’s trekant.