Tym razem kodowałem w samolocie... i 6 tasków z grafów i drzew poszło bez problemu.
Wychodzi na to, że dla mnie miejsce 4C w A220 Swiss jest świetnym miejscem do kodowania ;-) [ciekawa sprawa A220 ma układ foteli 2+3, pierwszy raz w życiu taki widziałem]
Ale jak wysiadłem i siedzę teraz na lotnisku w Zurichu to już mi tak dobrze nie idzie.... Nie do końca mam pomysł na to rozwiązać... a wiem, że umiałem - czyli mam blokadę przez stres ;-)
A i próbowałem jeszcze 1 metody ataku, o której nie pisałem poprzednio. Atak przez przepisanie danych z jednego formatu na drugi ;-)
Teraz próbuję zrobić build order - czyli mam dzień dobry listę projektów i tego co zależy od danego projektu.
Trochę mi brakuje iPada do narysowania tych zależności ;-)
A jakoś chwilowo mam wyłączony w głowie moduł dopasowujący znane algorytmy do tego.... Więc na razie mam tylko pomysł jak to zrobić "na piechotę", mam listę projektów z tego na ilu zależą... wybieram taki, który ma 0... wszystkim jego dzieciom odejmuję ten projekt... a go dodaję do listy.... biorę kolejny z 0 i robię to samo.... jak nie znajdę takiego z 0 to wiem, że tego się nie da zrobić.
Ale na razie mi się to nie podoba bo brzmi bardzo...
[Dopisane ~36h później]
Wróciłem do tego zadania już w Wenecji.. i miałem w głowie te przemyślenia, więc zacząłem pisać, ale nie od góry, a od dołu. Tzn. wcześniej pisałem od góry, czyli definiowałem zmienne i tak dalej... ale uznałem, że zamiast od ogółu do szczegółu - pójdę od szczegółu do ogółu. Już miałem w głowie, że będę miał zeros jako list projektów które w chwili obecnej od niczego nie zależą i że będę miał order... więc najpierw zrobiłem while (order.size()==projects.length) i próbowałem pisać środek, ale szybko do mnie dotarło, że nie tędy droga i że lepiej mieć while (!zeros.isEmpty())... i jak to napisałem, następne miałem var current = zeros.poll() (bo wiedziałem, że to musi być ArrayDeque żeby mi Java nie krzyczała, że ona nie będzie iterowała po kolekcji jak ją modyfikuję.... i jak to już miałem to do mnie dotarło "Ty, gościu przecież to jest prawie BFS" i już się samo pisało... i to się napisało:
Wróciłem do tego zadania już w Wenecji.. i miałem w głowie te przemyślenia, więc zacząłem pisać, ale nie od góry, a od dołu. Tzn. wcześniej pisałem od góry, czyli definiowałem zmienne i tak dalej... ale uznałem, że zamiast od ogółu do szczegółu - pójdę od szczegółu do ogółu. Już miałem w głowie, że będę miał zeros jako list projektów które w chwili obecnej od niczego nie zależą i że będę miał order... więc najpierw zrobiłem while (order.size()==projects.length) i próbowałem pisać środek, ale szybko do mnie dotarło, że nie tędy droga i że lepiej mieć while (!zeros.isEmpty())... i jak to napisałem, następne miałem var current = zeros.poll() (bo wiedziałem, że to musi być ArrayDeque żeby mi Java nie krzyczała, że ona nie będzie iterowała po kolekcji jak ją modyfikuję.... i jak to już miałem to do mnie dotarło "Ty, gościu przecież to jest prawie BFS" i już się samo pisało... i to się napisało:
public static List<String> order(String[] projects, String[][] dependencies) {
var deps = new HashMap<String, Set<String>>(); // project2dependants
var deps2 = new HashMap<String,Set<String>>(); // dependant2dependency
for (var dep:dependencies) {
var first = dep[0];
var second = dep[1];
deps.computeIfAbsent(first, k -> new HashSet<String>()).add(second);
deps2.computeIfAbsent(second, k -> new HashSet<String>()).add(first);
}
var zeros = new ArrayDeque<String>();
for (var project:projects) {
if (deps2.getOrDefault(project, Set.of()).isEmpty()) zeros.addLast(project);
}
List<String> order = new ArrayList<String>();
while (!zeros.isEmpty()) {
var current = zeros.poll();
order.add(current);
for (var other:deps.getOrDefault(current,Set.of())) {
var set = deps2.get(other);
set.remove(current);
if (set.isEmpty()) {
deps2.remove(other);
zeros.addLast(other);
}
}
}
if (order.size()!=projects.length) return List.of(); // error
return order;
}
I teraz obserwacje.
Po pierwsze nadal moja głowa ma takie "e, ale to trudne, nie róbmy tego"... chyba trochę to blogowanie mnie odblokowuje, bo mam takie "e, może jakiś wpis na bloga się tak urodzi?".. więc to jest trochę odblokowywacz. Ale też pamiętam, że "Przemek - możesz napisać źle, ale napisz".
I wyszło mi jeszcze, że jest kolejny sposób na atak - pisz od szczegółu do ogółu ;-)
I wyszło mi jeszcze, że jest kolejny sposób na atak - pisz od szczegółu do ogółu ;-)
Czyli lista na przełamanie blokady jest na razie taka (po dodaniu nowego - ostatiego):
- zrób prosto i nieoptymalnie i próbuj stąd atakować - to ma wady, bo można się "źle nauczyć" - dla mnie to jest często jedyny sposób na atak na rzeczy z dynamic programming,
- zrób głupio - podobne do poprzedniej, ale z takim "tu dzieje się cud" (tu nie można przesadzać, bo nie może być całe tak zrobione, ale może uda się zidentyfikować gdzie dokładnie jest problem),
- oszukaj - może da się to zrobić inaczej? (np. obrót tablicy 2D.... można to ubrać w metody które nic nie obracają, a robią strukturę danych która ma w środku prawdziwą tablicę),
- ogranicz się - jak nie wiesz jak atakować to spróbuj inaczej, a może przez rekursję się da?
- zrób od tyłu - jeśli nie idzie Ci pisanie od ogółu do szczegółu, to pisz od szczegółu do ogółu - sprowadź problem do najmniejszego końcowego problemu - jak zbudować wynik? Ale już na samym końcu... (tutaj to było to, że do listy wolno dodawać tylko projekty które mają 0 dependencji) [tak, w pewien sposób to jest trochę takie podejście jakie używam przy rekurencji... jakie są warunki powrotu?]
Podobne postybeta
Napisz źle, ale napisz ;-)
Popsuł mi się Calc w OpenOffice.org :-(
Niecne wykorzystanie refleksji... czyli jak poszukać tekstu w drzewie obiektów? ;-)
Który kod (nie kot! ;-)) lepszy?
Podobne posty i zachwyty nad nimi... ;-) i trochę o Java 7
