Dear mọi người,
Mình có 1 bài code challenge sử dụng .Net, hiện mình đang bí chưa hiểu ra vấn đề hiện tại. Mong mọi người giành chút time xem qua và thông não hộ mình với, thank all !
Coding Challenge Homework
Mình mù tịt mấy cái này, nhưng mà mình có nghĩ ra một cách không biết nó có đúng không. Mình sẽ xét case 4
Giả sử ta tách ra làm 2 list (sắp theo thứ tự)
List 1: a, b, c, d, e, f và List 2: 0 c f a b 0. Đầu tiên mình sẽ tìm những kí tự không nằm trong list 2 rồi sắp chúng nó vào (thứ tự nào cũng được, vì nằm trong list 2 chứng tỏ nó không bị phụ thuộc)
=> output = de
Vậy ta còn
List 1: a, b, c, f và List 2: 0, c, f, 0. Làm tương tự như bước trên, ta được
=> output = ab
Ta còn lại
List 1: c, f và List 2: f, 0. Lại làm như bước trên
=> output = c
vậy cuối cùng ta được
deabcf
Nếu ai thấy sai sót thì góp ý nhẹ nhàng giúp mình với nhé 
Đây là code của mình
with open('input.txt') as f:
f = f.readlines()
if len(f) <= 0:
print('empty')
exit(0)
if len(f) == 1:
print(f[0][0])
exit(0)
for i in range(len(f)):
f[i] = f[i].split('=>')
f[i] = [c.strip() for c in f[i]]
fi, la = [v[0] for v in f], [v[1] for v in f]
for i in range(len(fi)):
if fi[i] == la[i]:
print('error')
exit(0)
def isequal(a, b):
return set(a) == set(b)
s = ''
while not isequal(fi, la):
i = 0
while i < len(fi):
if fi[i] not in la:
s += fi.pop(i)
del la[i]
continue
i += 1
if len(fi) != 0:
print('error')
exit(0)
print(s)
2 Likes
Mình đưa ra một ý tưởng thế này, còn áp dụng lập trình thế nào thì các bác tự làm nhé (đây đúng là sắp xếp tô-pô):
Về bài này:
a => null
b => c
c => f
d => a
e => b
f => null
Ta có thể duyệt từng dòng, và mỗi dòng chúng ta resolve cái đuôi cuối của chuỗi phụ thuộc, ví dụ b => c thì c sẽ được resolve thành b => c => f, sau đó ta xóa dòng c => f đi, rồi lại tiếp tục resolve đuôi cuối là f, tạo ra b => c => f => null, lại xóa f => null đi, làm đến khi nào không làm được nữa (gặp null) thì thôi, chuyển sang dòng tiếp theo.
Vậy với case này, kết quả sau khi đã resolve tất cả các dòng là:
d => a => null
e => b => c => f => null
Và ta in ra từ trên xuống dưới, từ phải sang trái: a, d, f, c, b ,e
Với case có phụ thuộc vòng vo:
a => null
b => null
c => c
Thì phát hiện ra nó rất đơn giản, nếu trong quá trình resolve mà tự dưng lại resolve ra chính cái dòng đang xét thì tức là circular dependency.
Có một case mà đề bài không nói:
a => b
c => d
d => b
Sau khi resolve:
a => b
c => d => b
Ở đây ta có b được cả 2 dòng phụ thuộc vào, ở đây mình nghĩ cứ in ra như trên, nhưng trong quá trình in thì kiểm tra để không in ra 1 node quá 1 lần.
Bổ sung: thực ra cách của mình bản chất là đi ngồi duyệt cây theo chiều sâu.
Bổ sung 2: cách của mình không thể áp dụng với trường hợp 1 jobs có nhiều phụ thuộc (ngoài phạm vi của bài này)
4 Likes
Còn:
a => b
b => c
a => d
Cũng giống với các trường hợp lỗi như đề bài.
3 Likes
Trường hợp này đâu có hợp lệ đúng không, 1 job chỉ có 1 sự phụ thuộc thôi
3 Likes
Thanh các bác, mình đang bí 2 câu cuối cùng các bác ạ, bác nào giải thích hộ em câu trước câu cuối với, em không hiểu input vào như nào cho nó báo ra lỗi cả. Em chưa làm được 2 câu cuối 
Còn đây là cách em làm câu số 4 bác ạ :
var input = string.Empty;
var output = string.Empty;
while (input.Length != 3)
{
Console.WriteLine("Please input a string which consists of 3 characters ");
input = Console.ReadLine();
var firstJob = input[0];
var lastJob = input[input.Length - 1];
var secondJob = input[input.Length - 2];
output = $"{firstJob}{lastJob}{secondJob}";
}
Console.WriteLine("Jobs output order is: " + output);Còn đây là câu số 5 của em , các bác thấy em làm kiểu này có sai nguyên tắc gì không sửa lỗi giúp em với, thank mọi người
var input = string.Empty;
var firstResult = string.Empty;
var secondtResult = string.Empty;
while (input.Length != 6)
{
Console.WriteLine("Please input a string which consists of 3 characters ");
input = Console.ReadLine();
var JobsBC = input.Substring(1, input.Length - 4);
var jobsEF = input.Substring(input.Length - 2);
var jobsFCBE = $"{jobsEF[jobsEF.Length - 1]}" + $"{JobsBC[JobsBC.Length - 1]}" + $"{JobsBC[0]}" + $"{jobsEF[0]}";
var jobsAD = $"{input[0]}" + $"{input[input.Length - 3]}";
firstResult = jobsFCBE + jobsAD;
secondtResult = jobsAD + jobsFCBE;
}
Console.WriteLine("Jobs output order is: " + firstResult + " or " + secondtResult);Dear bác, em cứ nghĩ là chỉ cần giải quyết đề bài theo yêu cầu mà họ muốn mình sắp xếp @@, vậy là không phải hả bác ?
Mình tưởng đây là 1 bài duy nhất?
2 Likes
Vậy theo bác đây là 1 bài duy nhất hả bác, chứ không nó phải tách thành từng phần ?? Tại đây là lần đầu mình giải toán như này?
Chắc hiếm người nghĩ đây là nhiều bài lắm bạn ạ.
2 Likes
Nhiều bài chắc mình in ra kết quả luôn ko cần nghĩ logic làm gì 
3 Likes
Cảm ơn mọi người, thế chắc tèo thật rồi :(, mình đang làm lại switch case nhưng mình chưa hiểu cách trình bày ra sao để nó hiểu được thằng b phụ thuộc vào thằng c :(((
Em đọc mọi người viết C++ em không hiểu lắm, em vô làm giải toán là làm C#
Em làm xong rồi mọi người ạ, nhưng cách của em chắc là cách học sinh cấp 1 các bác ạ @@. Nhờ mọi người chỉ em hướng giải quyết khác với. Thanks !
private static void Exercise(string[] content)
{
var output = string.Empty;
string[] jobs; // list job and it's dependency in each line
switch (content.Length)
{
case 0: // empty string
output = "An empty sequence";
break;
case 1: // Input has one line and no dependency (a=>)
jobs = content[0].Split(new[] { "=>" }, StringSplitOptions.RemoveEmptyEntries);
output = jobs[0];
break;
case 3:// Input has 3 lines
for (int i = 0; i < content.Length; i++) // loop each line
{
var line = content[i].Replace(" ", ""); // Trim all white space in line
jobs = line.Split(new[] { "=>" }, StringSplitOptions.RemoveEmptyEntries); // split job in line and it's dependency
if (jobs.Length == 2) // if job has it's dependency (ex: b=>c)
{
if (jobs[0] == jobs[jobs.Length - 1]) // if job depends on itself (ex: c=>c)
{
output = " jobs can’t depend on themselves.";
break;
}
if (!output.Contains(line[0])) // add new job to output but it must not existed in output
{
output += jobs[jobs.Length - 1] + jobs[0];
}
}
else // if job doesn't have dependency (ex: a=>)
{
if (!output.Contains(line[0]))// add new job to output but it must not existed in output
{
output += line[0];
}
}
}
break;
case 6:// Input has 6 lines
List<string> temp = new List<string>(); // list contain job without it's dependency
for (int i = 0; i < content.Length; i++) // loop each line
{
var line = content[i].Replace(" ", ""); // Trim all white space in line
jobs = line.Split(new[] { "=>" }, StringSplitOptions.RemoveEmptyEntries); // split job in line and it's dependency
if (jobs.Length == 1) // job without it's dependency (ex: a=>)
{
temp.Add(jobs[0]); // add it to 'temp'
}
else
{
//if (temp.Contains(jobs[0]) || temp.Contains(jobs[jobs.Length - 1])) // remove item from temp list if it depends on others
//{
// temp.Remove(jobs[0]);
// temp.Remove(jobs[jobs.Length - 1]);
//}
if (output.Contains(jobs[jobs.Length - 1]) && output.Contains(jobs[0])) // if output contains both job and it's dependency
{
output = " jobs can’t have circular dependencies";
}
else if (output.Contains(jobs[0])) // add new job to output but it must not existed in output (ex : b=>c)
{
output = output.Insert(output.IndexOf(jobs[0]), jobs[jobs.Length - 1]);
}
else if (output.Contains(jobs[jobs.Length - 1])) // add new job to output but it must not existed in output(ex : b=>c)
{
output = output.Insert(output.IndexOf(jobs[1]) + 1, jobs[0]);
}
else // add new job to output but it must not existed in output(ex : b=>c)
{
output += jobs[jobs.Length - 1] + jobs[0];
}
}
}
break;
default:
break;
}
Console.WriteLine("Output: " + output);
}@Jason_Statham: Bạn có thể dùng giải thuật Kahn từ Wikipedia về Topological sorting:
Giải thuật này rất tốt và đúng trong mọi trường hợp nếu graph là DAG (đúng cho cả trong trường hợp của @SITUVN.gcd đã đưa ra). Tuy nhiên, để nó làm việc được với yêu cầu của đề bài bạn đang giải thì bạn phải làm một số thay đổi nhỏ trong đó (ví dụ như làm sao phát hiện được circular reference, dùng cấu trúc dữ liệu nào cho S thay vì dùng tập hợp, chèn phần tử vào danh sách S như thế nào, v.v.)
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?