[Pawlis]

Ktoś stąd ogarnia programowanie dynamiczne i jest w stanie pomóc mi z pewnym zadaniem? Prowadzący ma na Nas w------e i nawet na maile nie odpisuje, a terminy gonią.

"Posiadając na wejściu pewną tablicę znaków T możesz wykonać następującą
operację:
• Weź dwa sąsiadujące ze sobą elementy, które mają różne znaki i zamień je na
inny, trzeci znak (ze zbioru początkowego tablicy T).
Znajdź długość najmniejszej tablicy, jaka może być osiągnięta w sposób
powtarzania tej operacji na kolejno uzyskiwanych transformacjach."

Zaczynam od tablicy {a,a,b,c,d}
b,c => d i dostaję {a,a,d,d}
I tutaj się pojawia pierwsze moje pytanie(możliwe, że wyjątkowo głupie):
Czy mogę tym momencie wykonać transformację a,d=>c?

Z jednej strony korzystam ze zbioru początkowego T, a co za tym idzie "c" jest jak najbardziej dostępne, ale z drugiej strony, jeśli taka operacja jest dozwolona, to mając 4 różne znaki w tablicy wejściowej zawsze można ją sprowadzić do tablicy długości 1(chyba, że o to chodzi w tym zadaniu XD).

Ale jeśli taka operacja nie jest możliwa, to sam nie wiem co z tym zadaniem zrobić bo rozpisuje sobie różne przykłady i żadnego schematu zauważyć nie mogę. Jakiś pro-tip jak do tego podejść żeby zobaczyć jakąkolwiek zależność?

#programowanie

[Defined]

@Pawlis: No do jednego można zredukować ostatecznie, jak to zauważyłeś. A jeżeli masz elementy z tym samym znakiem, to nie możesz ich zredukować

[Verbatino]

@Pawlis:
1. Pierwsze różne elementy to a, b.
2. Transformacja ma być wykonana na znak ze zbioru początkowego, więc możesz wykorzystać każdy znak, również c.
3. Troszkę niejasna jest treść zadania ponieważ nie podano, że masz stworzyć nową tablicę, a zamiana znaków nie oznacza, że zmienia się długość tablicy. Niemniej zapewne chodziło o to, że w efekcie końcowym transformacji mamy jednakowe elementy tablicy. W zadaniu nie wskazano również ile może

[Pawlis]

@Verbatino: akurat może być więcej niż jedna podmiana. Zastanawiałem się nad sprawdzaniem kolejnych podtablic np. {a}, {a,a}, {a,a,b} i przy pomocy hashsetu kontrolowaniem ile różnych znaków już mam i w zależności od tego kontrolować minimalną długość tablicy. Ale nie jestem pewien czy spełnia to założenia programowania dynamicznego. Niby rozbijam to nad podproblemy, ale mam wrażenie, że to dość naciągane podejście.

[kkthxbb]

@Pawlis: IMO wydaje mi się, że jeżeli masz co najmniej 3 różne znaki w tablicy, to każdy ostateczny zredukowany ciąg będzie miał długość 1. W przeciwnym razie wynikiem zawsze będzie długość tablicy. Łap rekurencyjnego brute-force'a: https://pastebin.com/fiXkH1vr

[Pawlis]

@kkthxbb: 3 to za mało, masz {a,b,c}, ab możesz zamienić tylko na c, a z c,c już nic nie zrobisz

[kkthxbb]

@Pawlis: Ach, to prawda! :D

[Verbatino]

@Pawlis: Nie wiem jak wyobrażałbyś sobie implementację z HashSet-em ale istnieje duże prawdopodobieństwo, że pominąłbyś kombinacje.
Zastosuj klasyczną metodę top-down (rekurencyjnie) z zapisywaniem wyniku.

[Pawlis]

@Verbatino: hashset jedynie w celu sprawdzania czy znak, który właśnie został dodany, już wcześniej się pojawił. Dzięki za pomoc

[Verbatino]

@Pawlis: Właśnie to jest dobry przykład, że możesz popełnić błąd ( ͡° ͜ʖ ͡°)
Przykładowo tablica: {a,b,a,b,a,c,d}

[kkthxbb]

@Pawlis: Mały update, teraz powinno generować dobre rozwiązanie: https://pastebin.com/MAQndpXx

[Pawlis]

@kkthxbb: Dziękuję pięknie