Hamiltonian Cycle

July 27, 2020

Bilgisayar temizliği ve organizasyonu işlerine bulaştım. Arşivimden çıkan bir problemi paylaşmak istiyorum.

Kim olduğunu hatırlamamakla beraber IBM olabilir, kodlama mülakatında aşağıdaki problemi sormuştu.

Size N elemanlı bir string dizisi veriliyor. Sizin amacınız ise her kelimenin son harfinin bir sonraki kelimenin ilk harfi olacak şekilde N elemanlı bir döngü bulmanız ve bu döngüyü cevap olarak ekrana bastırmanız.

1
2

arr  = [ "ab", "az", "ba", "za"];
// Dogru konfigurasyonu ab -> ba -> az -> za -> ab;

Bu problem literatürde hamiltonian cycle olarak geçiyor. Bir vertexten başlayıp tüm vertexleri sadece bir defa gezerek başladığınız noktaya geliyorsanız buna hamilton cycle deniyor.

Mülakat sırasında doğru implementasyonu yapamamıştım. Backtracking kısmını unuttuğum için segfault alarak elenmeyi garantiledim.

Mülakattan sonra salim kafayla oturup tekrar çözdüm. Basitçe dfs + backtracking ile çözülüyormuş. Açıklamaları comment olarak ekledim.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

#include <bits/stdc++.h>
using namespace std;

int isValidNextVertex(vector<vector<int>>& G, vector<int>& P, int v, int pos) {    
    // Bir once eklenen vertex in komsusu degilse bizim isimize yaramaz.
    if (G[P[pos - 1]][v] == 0)
        return 0;

    // Vertex hali hazirda path e eklendiyse bizim isimize yaramaz.
    for (int i = 0; i < pos; i++)
        if (P[i] == v)
            return 0;

    return 1;
}

int hamiltonian(vector<vector<int>>& G, vector<int>& P, int n) {
    // Turumuz bittiyse, buldugumuz son elemandan ilk elemana bir yol olup olmadigina bakalim.
    if (n == G.size())
        return G[P[n - 1]][P[0]] == 1;

    for (int i = 1; i < G.size(); i++) {
        if (isValidNextVertex(G, P, i, n)) {
            P[n] = i; // vertexi yola ekleyelim.
            if (hamiltonian(G, P, n + 1))
                return 1;
            P[n] = -1; // backtrack, ayni arama uzayina tekrar girmemek icin.
        }
    }

    return false;
}

vector<int> findPath(vector<string>& words) {
    int n = words.size();

    vector<vector<int>> G(n, vector<int> (n, 0)); // komsuluk matrisi
    vector<int> P(n, -1); // Takip edeceğimiz vertexlerin idleri
    P[0] = 0; // ilk dugum olarak 0 dan baslasin.

    // Graphımızı oluşturalım.
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            G[i][j] = words[i][words[i].size() - 1] == words[j][0];

    if (hamiltonian(G, P, 1)) 
        return P;
    return vector<int>(0);
}

int main() {
    vector<string> words = { "esra", "tahir", "mahmut", "faruk", "raziye", "kerim", "akif" };
    vector<int> path = findPath(words);

    int size = path.size();
    if (size == 0) {
        cout << "NO" << endl;
        return 0;
    }

    cout << "YES" << endl;
    for (int i = 0; i < size; i++){
        if (i < size - 1) cout << words[path[i]] << " ";
        else cout << words[path[i]];
    }

    return 0;
}
« Lockdown ve Beklenen Değer
Basit Bir Olasılık Sorusu »

hidden

AI: Where in the Loop Should Humans Go?

This is a re-publishing of a blog post I originally wrote for work, but wanted on my own blog as well.AI is everywhere, and its impressive claims are leading to rapid adoption. At this stage, I’d qualify it as charismatic technology—someth…

via Ferd.ca

More Good Programming Quotes, Part 6

Here are more good programming quotes I have found since my last post. Programming “Configuration is coding in a poorly designed programming language without tests, version control, or documentation.”Gregor Hohpe “It’s the developers misunderstanding, not…

via Henrik Warne's blog

HOWTO: Change your behavior

In theory, behavior change should be easy. At first glance, it seems like you control your behavior. So, if you desire different behavior, why doesn’t your behavior change as instantly as your desire to change it? In short, lasting change of habitual behavio…

via Matt Might's blog