http___projecteulercozum.blogspot.com.tr_2014_02_problem-96-su-doku.html_1.xml
1.1 4.1 5.1 6.1 6.2 6.3 7.1 8.1 8.2 8.3 9.1 10.1 10.2 10.3 11.1 12.1 12.2 12.3 12.4 12.5 12.6 14.1 15.1 15.2 15.3 15.4 16.1 17.1 18.1 19.1 21.1 22.1 23.1 24.1 25.1 26.1 27.1 28.1 29.1 30.1 31.1 32.1 32.2 33.1 33.2 34.1 34.2 35.1 36.1 37.1 38.1 39.1 41.1 42.1 43.1 44.1 45.1 46.1 48.1 49.1 50.1 51.1 52.1 53.1 54.1 55.1 56.1 60.1 61.1 64.1 65.1 66.1 67.1 68.1 69.1 70.1 71.1 72.1 73.1 74.1
Problem Links: Problem: Most crossword puzzle fans are used to anagrams --groups of words with the same letters in different orders--for example OPTS, SPOT, STOP, POTS and POST. Some words however do not have this attribute, no matter how you rearrange their letters, you cannot form another word. Such words are called ananagrams , an example is QUIZ. Obviously such definitions depend on the domain within which we are working; you might think that ATHENE is an ananagram, whereas any chemist would quickly produce ETHANE. One possible domain would be the entire English language, but this could lead to some problems. One could restrict the domain to, say, Music, in which case SCALE becomes a relative ananagram (LACES is not in the same domain) but NOTE is not since it can produce TONE. Write a program that will read in the dictionary of a restricted domain and determine the relative ananagrams. Note that single letter words are, ipso facto, relative ananagrams since they cannot be ``rearranged'' at all. The dictionary will contain no more than 1000 words. Input Input will consist of a series of lines. No line will be more than 80 characters long, but may contain any number of words. Words consist of up to 20 upper and/or lower case letters, and will not be broken across lines. Spaces may appear freely around words, and at least one space separates multiple words on the same line. Note that words that contain the same letters but of differing case are considered to be anagrams of each other, thus tIeD and EdiT are anagrams. The file will be terminated by a line consisting of a single # Output Output will consist of a series of lines. Each line will consist of a single word that is a relative ananagram in the input dictionary. Words must be output in lexicographic (case-sensitive) order. There will always be at least one relative ananagram. Sample input ladder came tape soon leader acme RIDE lone Dreis peat ScAlE orb eye Rides dealer NotE derail LaCeS drIed noel dire Disk mace Rob dries Sample output Disk NotE derail drIed eye ladder soon Solution: Sort. Source Code: import java.io. BufferedReader; import java.io. InputStreamReader; import java.util. Arrays; public class Main { public static void main(String[] args) throws Exception { Main main = new Main(); main.run(); System.exit(0); public void run() throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String str = ""; String line = null; while ((line = br.readLine()) != null && line.compareTo("#") != 0) { str += line + " "; //make sure words are separated. String[] list = str.split("[\\s]+"); Arrays.sort(list); for (int i = 0; i < list.length; i++) { boolean found = false; for (int j = 0; j < list.length; j++) { if (i != j) { if (checkAIsRelativeAnanagram2B(list[i], list[j])) { found = true; break; if (!found) System.out.println(list[i]); public boolean checkAIsRelativeAnanagram2B(String a, String b) { if (a.length() != b.length()) return false; char[] charA = a.toLowerCase().toCharArray(); char[] charB = b.toLowerCase().toCharArray(); Arrays.sort(charA); Arrays.sort(charB); for (int i = 0; i < charA.length; i++) if (charA[i] != charB[i]) return false; return true;
1.1 2.1 3.1 4.1 5.1 6.1 7.1 8.1 9.1 10.1 11.1 12.1 13.1 14.1 15.1 16.1 17.1 18.1 19.1 20.1 21.1 23.1 24.1 26.1 27.1 28.1 29.1 30.1 31.1 33.1 34.1 35.1 37.1 38.1 39.1 40.1 41.1 43.1 44.1 45.1 47.1 48.1 49.1 50.1 51.1 52.1 53.1 55.1 56.1 57.1 58.1 59.1 60.1 61.1 62.1 63.1
30 Ocak 2014 Perşembe Problem 96 - Su Doku Soru Japonca anlamı sayı yerleştirme olan Sudoku problemiyle karşı karşıyayız. Her bir satırı ve sütunu 1-9 arası sayıların tamamını birer kere içeren, 9x9'luk karelerden oluşuyor. Aynı zamanda 9 parçaya ayrılmış 3x3'lük kareleri de 1-9'a kadar olan sayıların hepsini barındırmalı. Soruda istenilen, .txt dosyası ile verilen 50 adet Sudoku'nun çözülmesi ve her Sudoku'nun ilk üç karesinin toplamlarının bulunması. Bu sayı örnekte 483. http://projecteuler.net/problem=96 http://projecteuler.net/project/sudoku.txt Çözüm Elbette her Sudoku'yu tek tek çözmeyeceğiz. Bunun için Sudoku çözen bir program yapmamız lazım. Bunun için öncelikle kuralları iyi belirlemeliyiz. 1) Her satırda 1-9 arası tüm sayılar bulunmalı 2) Her sütunda 1-9 arası tüm sayılar bulunmalı 3) Her üçlüde 1-9 arası tüm sayılar bulunmalı Çeşitli yollarla çözmek mümkün. Ben iki boyutlu tek bir bool dizi kullanarak çözme yolunu tercih ettim. Her bir sayı için matriste dolaşıp o sayıyı bulunduğunda, mevcut olduğu satır ve sütunları eleyen bir dizi. Çünkü her sayı bir satır, sütun ve üçlüde yalnızca bir kere bulunabilir. Öyleyse sayının bulunduğu satır, sütun ve üçlüleri elersek geriye kalan kareler bize sayının olası konumlarını verir. Bunu muhakkak bir kağıda çizerek denemelisiniz, zaten bu elemeleri yaptığınızda sistemin nasıl işlediği kolayca belli oluyor. Bundan sonra o satır, sütun ve üçlülerin özel olup olmadığını test edeceğiz. Buradan özelden kastım, o sayı mecburen orada mı olmalıdır, yani başka koyulacak bir yer yok mudur sorusunun cevabıdır. Fakat tüm bunlar yine yetersiz kalabilir ve başka bir yola başvurmak zorunda kalabiliriz. O durumda da mevcut olasılıkları deneyerek sonucun doğru çıktığı yolu bulmaya çalışacağız. Bu işin zor kısmı, ne de olsa zor sudokular için. Kodlama İlk başta basit kısmı ele alalım. Programın tüm işini yürüten parça bu kod. İşaretleme kısmı static void CheckingProcess(char Number) for (int a = 0; a < 9; a++) // Checking all true(possible) for (int b = 0; b < 9; b++) PossibleSquares[a, b] = true; for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (Board[i, j] == Number) EliminateSquares(i, j); ListingProcess(Number); Üstteki kodun ilk iki for döngüsü tüm kareleri true değerle işaretliyor. Sonrasındaki iki for döngüsü ise, EliminateSquares(KareleriEle) metotunu kullanarak belirlenen bir sayının matristeki i ve j konumunu göndererek o konumdaki üçlüyü, satır ve sütunu false olarak işaretliyor. Son olarak da ListingProcess(Listelemeİşlemi) yeni listeyi oluşturuyor. Eleme İşlemi static void EliminateSquares(int i, int j) for (int a = 0; a < 9; a++) // Eliminate row PossibleSquares[i, a] = false; for (int a = 0; a < 9; a++) // Eliminate column PossibleSquares[a, j] = false; EliminateTriad(i, j); Burada EliminateTriad(ÜçlüyüEle) fonksiyonunu ayrıca yazıp çağırdım. İlk for döngüsü satırı ikincisi ise sütunu karalıyor(false yapıyor). Satır Özel mi? static bool isRowUnique(int i, int j) byte count = 0; for (int a = 0; a < 9; a++) if (PossibleSquares[i, a] == true) count++; if (count > 1) return false; return true; Yukarıdaki kod ise, o satırda eğer sadece bir kareye bu sayı yerleştirilebiliyorsa true, eğer başka kareye de gelme olasılığı varsa false değerini döndürüyor. Eğer true dönerse, o sayı mecbur o kareye gelecektir ve biz de onu tahmine gerek kalmaksızın oraya koyabiliriz. Sayıyı kareye yerleştirme if (PossibleSquares[i, j] == true && (isRowUnique(i,j) || isColumnUnique(i,j) || isTriadUnique(i,j) )) Board[i, j] = Number; Üstteki kodda dikkat edilmesi gereken paranteze alınmış "veya" - "||" işlemleri. Sayının muhtemelen o kareye gelme ihtimalinin doğru olması ve o üç kuraldan sadece birinin geçerli olması oraya yerleştirmemiz için yeterli koşulu sağlıyor. Bu haliyle işleme aldığınızda 50 Sudoku'dan alınan sonuç aşağıdaki gibi oluyor. Dolayısıyla zor Sudoku'ları çözmek için tahmin yoluna da gideceğiz. Bunu da sonra ekleyeceğim. Gönderen Ögetay Kayalı zaman: 06:41 Etiketler: C#, Çözüm, Project Euler 96 Çözüm, Sudoku, Sudoku Çözücü Kaydol: Kayıt Yorumları (Atom)