Project Euler - Masalah 042

Quote

The n^th term of the sequence of triangle numbers is given by, t_n = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (http://projecteuler.net/project/words.txt), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

Sumber: http://projecteuler.net/index.php?section=problems&id=42

Analisis:
Selepas aku memuat turun 'words.txt' yang mengandungi senarai-senarai perkatan, aku terus menukarkan susunan perkataan-perkataan tersebut. Aku lebih gemar menguruskan data yang di susun secara satu data pada setiap baris. Memandangkan aku mengguna IDE DrJava, terdapat satu feature dalam perisian tersebut di mana aku boleh membuat carian bagi sesuatu perkataan dan mengubah perkataan tersebut pada keseluruhan kod sumber dengan hanya satu klik. Jadi, dengan mudah aku menukarkan simbol "," kepada bari baru.

Tidak kisah bagaimana sekalipun aku menysusun data-data tersebut. Perkara yang paling penting, bagaimana korang boleh menyelesaikan masalah tersebut dengan pengaturcaraan Java. Pertama sekali, ambil setiap data yang ada dalam fail teks tersebut. Dalam setiap pengambilan, aku memeriksa sama ada data tersebut merupakan nombor triangular ataupun tidak. Dengan cara ini, aku dapat mengelakkan daripada menggunakan array.

Sesudah aku mengambil sesuatu data tersebut dan masukkan ke dalam variable String, aku menggunakan loop untuk memeriksa setiap karekter yang terdapat dalam String tersebut. Terdapat pelbagai cara untuk mendapatkan posisi sesebuah karekter. Korang boleh menggunakan switch case jika korang mahu (memang selalu di gunakan).

Aku tidak memilih untuk menggunakan switch case kerana aku malas untuk menulis 26 case. Jadi, aku menggunakan cara yang lebih mudah. Dalam fail teks tersebut, kesemua perkataan di tulis dengan huruf besar. Berpandukan Ascii table (http://www.cs.utk.edu/~pham/ascii_table.jpg), nombor decimal 65-90 merupakan nombor decimal bagi karekter 'A' sehingga 'Z'. Jadi, tukarkan sahaja karekter tersebut kepada datatype integer bagi mendapatkan nombor decimalnya dan tolak 64 bagi mendapatkan posisi sebenar karekter tersebut.

*Rujuk artikel "Cheat Sheet: Penukaran Datatype" bagi mengetahui teknik menukar sesebuah datatype ke datatype yang lain (http://secure.javamalaysia.com/tutorial-asas-java/cheat-sheet-penukaran-datatype/).

Sekarang, bagaimana pula caranya untuk memeriksa sama ada perkataan tersebut merupakan nombor triangular ataupun tidak? Seperti yang di nyatakan dalam soalan, nombor triangular boleh di periksa dengan menggunakan formula berikut:

Quote

t_n = ½n(n+1)

Hasil tambah kesemua posisi karekter dalam sesebuah perkataan akan memberikan nilai t_n. Jadi, kita perlu mendapatkan nilai n yang di gunakan untuk mendapatkan nilai t_n.

Bagi menyelesaikan masalah tersebut, korang perlu bermain sedikit dengan asas algebra. Katakan t_n = X. Cuba terbitkan sebuah lagi formula yang berbentuk seperti n =... . Untuk melakukan proses tersebut, korang perlu menggunakan formula Quadratic (http://en.wikipedia.org/wiki/Quadratic_equation#Quadratic_formula). Lihat kod sumber yang sudah aku tulis untuk melihat formula yang telah aku gunakan. Susah sikit nak tulis dalam ni.

Nombor triangular hanya di aplikasikan pada nombor neutral. Jadi, pada setiap nombor yang korang dapat daripada formula tersebut, bulatkan nombor tersebut dan masukkan ke dalam sebuah lagi variable. Kemudian, periksa sama ada variable-variable tersebut sama atupun tidak. Jika formula tersebut memberi jawapan nombor 10 sebagai contoh, korang akan mendapat nombor yang sama setelah korang bulatkan. Namun begitu, berbeza jika formula tersebut menghasilkan nombor 10.3 kerana bagi 10.3, korang akan mendapat nilai 10 setelah di bulatkan.

Kod Sumber:

Code:

import java.io.*;
import java.math.*;

class Problem42{
  public static void main(String[] args)
   throws Exception{
   int counter = 0;
   int charPosition;

   FileInputStream fstream = new FileInputStream("words.txt");
   DataInputStream in = new DataInputStream(fstream);
   BufferedReader br = new BufferedReader(new InputStreamReader(in));
   String strLine;

   while ((strLine = br.readLine()) != null){
   int Tn = 0;
   for(int i = 0; i < strLine.length(); i++){
   charPosition = strLine.charAt(i);
   charPosition -= 64;
   Tn += charPosition;
   }

   double z1 = ((-1) + Math.sqrt(1 – (4 * (-2 * Tn)))) / 2;
   double z2 = Math.round(z1);

   if(z2 – z1 == 0)
   counter++;
   }

   System.out.println("No of triangle words: " + counter);
   in.close();
  }
}