04. კარელის სავარჯიშოები

მიმატება

მოცემულია სამყარო, სადაც 2x1 პოზიციაზე დევს n ცალი ბურთი, ხოლო 3x1 პოზიციაზე - m ცალი. კარელს უნდა, რომ ეს ბურთები შეაგროვოს და დადოს ერთ რომელიმე პოზიციაზე. საბოლოო ჯამში სამყაროს ექნება ისეთი სახე, სადაც ერთ-ერთ პოზიციაზე იდება n + m ცალი ბურთი.

გახსოვდეს, რომ პროგრამა უნდა მუშაობდეს ნებისმიერი რაოდენობის ბურთებისთვის.

საწყის მაგალითში, 2x1 პოზიციაზე დევს 3 ცალი ბურთი და 3x1 პოზიციაზე დევს 2 ცალი ბურთი. საბოლოო ჯამში, სამყაროში ერთ-ერთ პოზიციაზე უნდა იდოს 5 ცალი ბურთი.

კარელი საწყის პოზიციაში დგას სამყაროს ქვედა მარცხენა კუთხეში და მიმართულია აღმოსავლეთით.

ამოხსნის კონცეპტი

ამ ეტაპზე არ გვისწავლია ცვლადები და რიცხვების ოპერაციები. მათ გარეშე მიმატება შეიძლება შეუძლებელი ჩანდეს, თუმცა შეგვიძლია ამოცანას სხვანაირად შევხედოთ - თუ ერთ უჯრაზე დევს 2 ბურთი, ხოლო მეორეზე 3, შეგვიძლია ყველა ბურთი, რომელიც ამ უჯრებზე დევს, მესამე უჯრაზე გადავიტანოთ. ამ გზით, მესამე უჯრაზე იმდენი ბურთი იდება, რაც პირველზე და მეორეზე ერთად.

ამოხსნა კონკრეტულ რაოდენობაზე

ჯერ-ჯერობით ამოხსნის ერთ-ერთ კომპონენტზე ვკონცენტრირდეთ: დავუშვათ, ერთ უჯრაზე გვაქვს 10 ბურთი, და გვინდა მეორეზე გადავიტანოთ. ამას შემდეგნაირად დავწერდით:

function start(){
    move();
    for(var i = 0; i < 10; i++) {
        takeBall();
    }
    move();
    for(var i = 0; i < 10; i++) {
        putBall();
    }
    move();
}

ამოხსნა ციკლის მეშვეობით

რა თქმა უნდა, პირველი მარტივი ამოხსნა არ გვაწყობს, რადგან არ ვიცით ზუსტად რამდენი ბურთი იქნება უჯრაზე. ამიტომ, ყველა ბურთის გადატანის პრობლემა სხვანაირად ჩამოვაყალიბოთ:

• გადავიტანოთ ერთი უჯრიდან ბურთი მეორე უჯრაზე მანამ, სანამ პირველ უჯრაზე ბურთი დევს

ასეთი ფორმულირებით, მხოლოდ შესაბამისი კოდის დაწერაღა გვრჩება

function start(){
    move();
    for(var i = 0; i < 100; i++) {
        moveBall();
        returnBack();
    }
    move();
}

// გადაიტანს ბურთს კარელის პოზიციიდან ორი უჯრით წინ
function moveBall() {
    takeBall();
    move();
    move();
    putBall();
}

// დაბრუნდება კარელის უკან ორი უჯრით
function returnBack() {
    turnAround();
    move();
    move();
    turnAround();
}

მეორე უჯრიდან ბურთების გადატანა

რა განსხვავებაა პირველსა და მეორე უჯრას შორის? - მეორე უჯრის შემთხვევაში, მესამემდე ერთი move() გვჭირდება

უფრო მარტივი ამოხსნა

• ყველა ბურთის გადატანა პირველიდან მეორე უჯრაზე
• ყველა ბურთის გადატანა მეორედან მესამე უჯრაზე

სამყაროს შევსება ბურთებით

მოცემულია ნებისმიერი ზომის სამყარო, რომლის შიგნითაც კედლები არ გვხვდება. კარელს უნდა, რომ სამყარო შეავსოს ჩოგბურთის ბურთებით და არ დატოვოს ცარიელი ადგილი. დაეხმარეთ კარელს სამყაროს შევსებაში. კარელი საწყის პოზიციაში დგას სამყაროს ქვედა მარცხენა კუთხეში და მიმართულია აღმოსავლეთით.

1. მარტივად დასაწერი ამოხსნა

დამოუკიდებლად სცადეთ ასეთი ალგორითმის იმპლემენტაციის დაწერა. დააკვირდით, რომ ჯერ ფუნქციების და კომენტარების გამზადება კოდის წერის პროცესს უფრო კომფორტულს ხდის

/*
შევავსოთ ყველა სვეტი (ვერტიკალური) ქუჩის გაყოლებაზე
(ანუ სანამ წინ თავისუფალია)
*/
function fillWorldV1() {

}

/**
 * შეავსებს ერთ სვეტს ვერტიკალურად და დაბრუნდება ისევ
 * ყველაზე ქვედა უჯრაზე 
 * 
 * დასაწყისი: აღმოსავლეთით
 * დასასრული: იმავე უჯრაზე, აღმოსავლეთით
 * */
function fillOneRow() {

}

/**
 * ბურთებით შეავსებს ხაზს კედლამდე
 * დასაწყისი: ნებისმიერ ადგილას, ნებისმიერი მიმართულებით
 * დასასრული: საწყისი მიმართულებით ქუჩის ბოლოს
 * */
function fillLine() {

}

—

2. უფრო "efficient" ვერსია

შეიძლება მოგვინდეს ისეთი ამოხსნის დაწერა, სადაც არასაჭირო მოძრაობები ამოკლებულია. სამყაროს ყველა უჯრის შემოვლა ისე,

• ხაზებად (პირველი ხაზი, დატრიალება, მეორე ხაზი, ა.შ)
• სპირალურად

მეორე ამოხსნაზე ფიქრს გირჩევდით, ჯერ უფრო მარტივით დავიწყოთ. ინსტინქტურად, ერთი ხაზის შევსება უნდა გავიმეოროთ მანამ, სანამ ჩვენს მიერ მოფიქრებული პირობა არ დაკმაყოფილდება. პირობაზე ჯერ არ ვკონცენტრირდეთ და პატერნს დავაკვირდეთ. რატომ არ გამოვა მარტო ერთი ხაზის შევსების და დატრიალების გამეორება?

ქუჩის ბოლოს აღმოსავლეთ მიმართულებით მისვლის შემთხვევაში ზედა ქუჩაზე ასასვლელად ხელმარცხნივ უნდა დავტრიალდეთ, ხოლო დასავლეთით სიარულისას - ხელმარჯვნივ. თუმცა, ამას თუ ავამუშავებთ, შეგვიძლია საჭირო რაოდენობაჯერ გავაკეთოთ.

ახლა პირობაზე დავფიქრდეთ, რა არის განსხვავებული ბოლო ქუჩასა და ყველა დანარჩენ ქუჩას შორის?

function fillWorldV2() {
    while(leftIsClear()) {
        fillTwoLines();
    }
}
/**
 * შეავსებს ახლანდელ და ზედა ხაზს ბურთებით
 * დასაწყისი: ახლანდელი ქუჩის პირველი უჯრა აღმოსავლეთ მიმართულებით
 * დასასრული: ორი ქუჩის ზემოთ აღმოსავლეთ მიმართულებით
 * */
function fillTwoLines() {
    fillLine();
    makeUTurnLeft();
    fillLine();
    makeUTurnRight();
}

/**
 * შეავსებს ერთ ქუჩას ბურთებით
 * ეს ფუნქცია უკვე დაწერილი გვაქვს
 * */
function fillLine() { }

function makeUTurnLeft() {
    turnLeft();
    move();
    turnLeft();
}

function makeUTurnRight() {
    turnRight();
    move()
    turnRight();
}

რა პრობლემაა ამ კოდში? არც ისე რთული მისახვედრია, რომ კარელი კედელს makeUTurnLeft() ფუნქციაში ეჯახება. დაჯახება კი მხოლოდ move() ფუნქციის გამოძახებისას არის შესაძლებელი.

function makeUTurnRight() {
    turnRight();
    if (frontIsClear()) {
        move();
    }
    turnRight();
}

გადართე მეორე სამყაროზე. რა პრობლემაა?

function fillWorldV2() {
    while(leftIsClear()) {
        fillTwoLines();
    }
    // თუ კენტ სამყაროშია, მაშინ ერთი ხაზი
    // ცარიელი რჩება
    if (noBallsPresent()) {
        fillLine();
    }   
}

ჩასწორების მერე გადართე ისევ პირველ სამყაროზე.

generic მოტრიალება

თუ უფრო ჭკვიანურად დავწერთ მოტრიალების ფუნქციას, შეგვეძლება 2-2 ხაზის მაგივრად თავდაპირველი იდეა დავაიმპლემენტიროთ და ამ აუტანელ ამოხსნას აღარ ვეწვალოთ.

function makeUTurn() {
    if (facingEast()) {
        makeUTurnLeft();
    } else {
        makeUTurnRight();
    }
}

ამ შემთხვევაში, მთავარია, OBOB არ დაგვემართოს და ყველა ხაზის შევსების შემდეგ ბოლო ხაზიც შევავსოთ.

function fillWholeWorld() {
    while(leftIsClear()) {
        fillLine();
        makeUTurn();
    }   
    fillLine();
}

თუ ვინმეს წინა ვერსიის დასრულება ძალიან გინდათ, სცადეთ ბოლო fillLine-ის წინ რამე სხვა პირობის შემოწმება.

მაგალითად, უკვე დევს თუ არა ბურთი უჯრაზე.