Alien Numbers

Bu yazı ilk olarak 2008-07-15 tarihinde yazılmış kaynak kodları kaybetmem üzerine 2015-10-02 tarihinte tekrar düzenlenmiştir.

Google code.jam'i keşfetmem üzerine hemen kolları sıvadım. Code Jam, Google tarafından düzenlenen bir programlama yarışması. Verilen problemleri istediğiniz bir programlama dili kullanarak çözmeye çalışıyorsunuz. Yarışmanın ilk ayağı 16 Temmuz Çarşamba günü başlayacak. Üyelik ücretsiz. Profesyonelinden öğrencisine herkes yarışmaya katılabilir. Birinciye $10.000 ödül verilen yarışmada derece yapmanın Google'da bir iş bulabilmeye yarayacağını düşünüyorum.

Şu an için code.jam'da örnek problemler mevcut. Bu problemler yarışanların code.jam hakkında fikir sahibi olmalarını sağlıyor. Örnek problemler arasında yer alan ilk problem Alien Numbers. Diğer problemlere göre kolay olan bu probleme bende bir çözüm üretmeyi başarabildim.

Uzaylı Sayıları

Bu problem yeni bir sayı sistemi yaratmak ile ilgili. Problem sizden verilen karakterlere göre 2 değişik sayı sistemi yaratmanızı ve bu sistemde geçen bir sayıyı, ikinci sayı sisteminde yer alan karşılığını vermenizi istiyor. Diğer problemlere göre kolay olan bu problemi Perl Rust ile yapmayı başardım. Size kısaca algoritmasından bahsedeyim.

Kullandığımı sayı sistemi 0123456789 rakamlarından oluşmakta. Problem bize verilen karakterlerden yeni bir sayı sistemi oluşturmamızı ve yine bu sayı sistemiyle yazılmış alien sayısını, hedef dil ile oluşturulmuş sayı sisteminde ki karşılığını bulmamızı istiyor. Verilenler şu şekilde:

alien_sayisi kaynak_dil hedef_dil

Problem sayfasında yer alan örneklere bakacak olursak; alien sayısı olarak 9, kaynak dil olarak 0123456789 ve hedef sayı sistemi olarak "oF8" karakterleri verilmiş. Öncelikle kaynak dili ele alalım. Kaynak dil şuan kullandığımız sayı sistemi ve oluşturulabilecek sayılar şu şekildedir: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12... Görüdüğünüz gibi 0'ı kullanmadık. Sayma sayıları 1 den başlamakta. Hedef dilimizde de böyle olmalı. Verilen alien sayısı 9 bu sayı sisteminin 9. sayısını oluşturmaktadır. İkinci sayı sistemine bakacak olursak bize "oF8" karakterleri verilmiş. Bu karakterler ile oluşturulacak sayılar şu şekilde olur: F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF... 9 sayısı kaynak dilimizde 9. sırada yer almaktaydı. Demekki 9 sayısının hedef dilimizde ki karşılığı, hedef dilimizde 9. sırada yer alan Foo.

Peki bunu programlama ile nasıl yapacağız?

Bu problemi programa dökmek için gerçek hayattaki gibi düşündüm (farklı çözümler üretenler de olmuş). Kullandığımız sayı sisteminde yer alan sayılar ile sonsuz miktarda sayı üretebiliyoruz. 0 1 2 3 4 5 6 7 8 9 ile saydıktan sonra 10 geliyor. Yani son sayıya geldiğimizde, eğer solunda bir sayı yoksa soluna bir ilk sayma sayımız ekleniyor ve ilk sayımız başa dönüyor. 17 18 19 20 şeklinde saydığımızda ise solda yer alan sayı, sayma sayılarımızın son sayısı olmadığından bir arttırılıyor. Yaptığım programın aynen bunu yapmasını sağladım. Öncelikle tüm sayıları bir array'a bölüp, daha sonra 1. sayıdan başlayarak artmasını sağladım. Arttır fonksiyonunu inceleyecek olursak...

Programı yıllar sonra tekrar Rust ile yazdım. Bu sefer ilkinden farklı bir algoritma kullanarak alien sayısını, verilen karakter dizesindeki karşılıklarıyla ondalık tabana çevirdim ve ardından hedef dil tabanına çevirerek, hedef dildeki rakam karşılıklarını buldum.

Problemdeki ilk örneği ele alalım:

Foo oF8 0123456789

oF8 rakamlarıyla yazılmış Foo alien sayısını, 0123456789 rakamlarını kullanarak yazmamızı istiyor. Bunun için öncelikle Foo sayısını 10 tabanında yazmayı deneyelim.

Foo sayısını oF8 rakamlarını kullanarak onluk sayı sistemine şöyle dönüştürebiliriz:

\(Foo_3 = (F \times 3^2) + (o \times 3^1) + (o \times 3^0)\)

oF8 sadece 3 karakter olduğundan alien sayı dilimiz aynı zamanda 3 tabanında olmalıdır. Foo karakterleri yerine de index değerlerini kullanırsak, sayımızı tam anlamıyla onluk tabana çevirebiliriz.

\(Foo_3 = (1 \times 3^2) + (0 \times 3^1) + (0 \times 3^0) = 9\)

Alien diliyle yazılmış Foo sayısı, onluk tabanda 9'a karşılık geliyor. Ardından hedef dile baktığımızda: 0123456789 zaten kullandığımız onluk sayı sisteminin rakamları. Alien diliyle yazılmış Foo, sayı sistemimizde 9'a eşit.

Diğer bir örneğe bakalım:

CODE O!CDE? A?JM!.

O!CDE? rakamlarıyla yazılmış CODE alien sayısını, A?JM!. rakamlarını kullanan başka bir alien sayı sistemiyle yazmamızı istiyor. Hemen O!CDE?'u onluk tabana çevirelim. İlk alien sayı sistemi 6 karakter içerdiğinden, altılık tabanda olmalı:

\(CODE_6 = (C \times 6 ^ 3) + (O \times 6^2) + (D \times 6^1) + (E \times 6^0)\) \(CODE_6 = (2 \times 6 ^ 3) + (0 \times 6^2) + (3 \times 6^1) + (4 \times 6^0) = 454\)

Alien diliyle yazılmış CODE sayısının onluk tabandaki eşitini bulduk. Şimdi bu sayıyı A?JM! rakamlarını kullanan diğer bir alien diline çevirmemiz gerekli. Hedef dilimiz 6 rakamdan oluştuğundan, onluk tabanda yazılan sayımızı altılık tabana çevirirsek bulabiliriz. Onluk tabandan altılık tabana çevirme bildiğimiz gibi sayıyı 6'dan küçük olana kadar 6'ya bölüp, bölüm ve kalanları sağdan sola yazarak yapılıyor.

Bu da bize: \(454_{10} = 2034_6\) sonucunu veriyor. Ama bizim kaynak dilimiz altılık sayı sisteminde olmasına rağmen 012345 rakamlarını yerine A?JM!. rakamlarından oluşuyor. Hedef dilimizdeki rakamları indexleyecek olursak:

012345
A?JM!.

2034'ü şöyle yazabiliriz: \(2034 = JAM!\)

Bu işlemi bilgisayara nasıl yaptırabiliriz ona bakalım:

use std::io;
use std::io::prelude::*;

// alien sayısı, kaynak dil sayı sisteminde (source) ile
// yazıldığında onluk tabanda karşılığını bulan fonksiyon
fn to_base_10(alien_number: &str, source: &str) -> usize {

    // n: onluk tabandaki karşılığı, bulmaya çalıştığımız değer
    // d: taban çarpanı, sayının basamak değerini bulmamız için
    //    gerekli çarpan her sayının sıfırıncı kuvveti 1
    //    olduğundan ilk değeri 1
    let (mut n, mut d) = (0, 1);

    // alien_number karakterlerine sondan başa doğru bakıyoruz
    // normalde bir sayıyı başka bir tabana çevirirken de
    // sondan başlayarak basamak değerlerini topluyoruz
    for c in alien_number.chars().rev() {

        // baktığımız alien karakterinin source
        // dizesi içerisindeki indexini buluyoruz.
        // bu index bizim onluk sayı sistemimizdeki rakama eşit
        // ve aynı zamanda sayı değeri
        let p = source.find(c).unwrap();

        // basamak değerini topluyoruz
        n += p * d;

        // basamak değeri çarpanımızın bir üssünü alıyoruz
        // source'da ne kadar karakter varsa, tabanımızda
        // bu olmalı
        d *= source.len();
    }

    n
}


// onluk tabandaki sayıyı, hedef dil tabanındaki sayıya
// dönüştürüp hedef dil ile yazılımını dönen fonksiyon
fn from_base_10(mut n: usize, target: &str) -> String {
    let mut string = String::new();

    // taban, hedef dildeki karakter sayısına eşit
    let b = target.len();

    // aynı yukarıdaki örnek gibi sayı tabandan büyük
    // olduğu sürece, sayıyı tabana bölmeye devam edeceğiz
    // tek şart son kalan'ı da almak için sıfırdan büyük
    // olduğu sürece bölmeye devam ediyoruz
    while n > 0 {

        // n % b ile bulduğumuz kalan'ın hedef alien dilindeki
        // karşılığını döneceğimiz string'e ekliyoruz
        string.push(target.chars().nth(n % b).unwrap());

        n /= b;
    }

    // sayıyı onluk tabandan başka bir tabana
    // çevirdiğimizde, kalanlan sağdan itibaren yazıldığından
    // son olarak strigimizi ters çevirip dönüyoruz
    string.chars().rev().collect()
}


fn main() {

    let stdin = io::stdin();

    for (i, line) in stdin.lock().lines().enumerate() {

        // ilk satır soru miktarını
        // içerdiğinden atlıyoruz
        if i == 0 { continue }

        let line = line.unwrap();

        // standart girdiden okuduğumuz string'i parçalıyoruz
        // vectorümüzün ilk değeri alien sayısını
        // ikinci değeri kaynak alien dilini
        // üçüncü değeri de hedef alien dilini tutuyor
        let v: Vec<&str> = line.split_whitespace().collect();

        let n = to_base_10(v[0], v[1]);
        let r = from_base_10(n, v[2]);

        println!("Case #{}: {}", i, r);
    }

}