ამ კვირის მასალა: https://codehs.com/lms/assignment/44667211

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

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

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

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

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

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

/**
 * ბურთებით შეავსებს ხაზს კედლამდე
 * დასაწყისი: ნებისმიერ ადგილას, ნებისმიერი მიმართულებით
 * დასასრული: საწყისი მიმართულებით ქუჩის ბოლოს
 * */
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-ის წინ რამე სხვა პირობის შემოწმება

მიმატება

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

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

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

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