Obliczanie czasu w którym gracz wygrywał

0

Mam dane z zewnątrz, mianowicie pary tablic. W pierwszej siedzą czasy (w sekundach) w których pierwszy gracz zdobywał punkty, a w drugiej czasy w których punktował drugi. Ilość zdobytych punktów jest nieograniczona, rozgrywkę ogranicza czas gry (600 sekund). Dane są oczywiście posegregowane rosnąco.
Na przykład:

gracz2 = [150, 345, 401, 481, 521]```

Muszę obliczyć czas przez jaki dany gracz wygrywał (dla obu graczy, bez wliczania czasu w którym gracz remisował). Rozgrywka zaczyna się od remisu 0:0.
Wymiękam zupełnie przy tym zadaniu. Wie ktoś jak to napisać, albo chociaż co wyszukiwać?
1

Rozpisz to sobie po kroku, tj. gracz1 wygrywał od 27 do 150 sekundy, następnie przez 39 sekund był remis itd. potem będzie Ci łatwiej to przerobić na właściwy algorytm.

2

Dokładnie - tak, jak pisał @Markuz - zastanów się, jak to ugryźć w sposób bezkomputerowy ;)

Najpierw ważne, żebyś zrozumiał sam sposób, w jaki bys to liczył na kartce / ręcznie. Jakie kroki byś podjął, jak byś to ugryzł pisząc sobie ołówkiem w zeszyciku.
Potem, jak to w pełni zrozumiesz, przerobienie na prawdziwy program powinno być dość proste (oczywiście zakładając, że masz jakieś pojęcie o programowaniu).

0

Usiadłem jeszcze na chwilę i wydaje mi się teraz, że konieczne będzie wykorzystanie rekurencji. Dobrze kombinuję?

2

Napisz krok po kroku (ale "ludzkim" językiem, nie żadnym pseudokodem lub schematem blokowym) jak widzisz rozwiązanie zadania, w jaki sposób chcesz to zrobić.
A potem skomentujemy i doradzimy albo damy inną opcję :)

Co do rekurencji - pewnie też jest to jakaś opcja (aczkolwiek rekurencja to bardzo ogólne stwierdzenie, nie napisałeś konkretnie co i jak chcesz zrobić). Ale równie dobrze można to (w mało elegancki, ale skuteczny sposób) zrobić poprzez pętle od 1 do 600 i sprawdzać w każdej sekundzie, jak wygląda sytuacja. Albo przesuwać sie po kolei po tablicach i porównywać czasy.

Jeszcze taka uwaga - piszesz o zdobywaniu punktów. O ile proste jest to w sytuacji, gdy mamy 1:0, potem 1:1, a potem 2:1, to przecież mogą być także sytuacje, w których masz 2:7, potem pierwszy zawodnik zdobywa punkt i się robi 3:7 - ale mimo zdobycia punktu, nadal wygrywa drugi. Może to być oczywiste, ale czasami takie "oczywistości" potrafią gdzieś umknąć i popsuć zabawę ;)

1

Spróbuj spojrzeć na to zadanie z mniej oczywistej strony, zauważ że czas jest skończoną dość małą liczbą, więc spokojnie możesz iterować od 0 do 600 i dla każdej sekundy sprawdzać kto w niej zdobył punkty, co pozwoli na odtworzenie stanu gry z danej sekundy.

0

Iterowanie przez 600 przedziałów 1-sekundowych w pythonie:

gracz1 = []
gracz2 = []
wynikg1 = 0
wynikg2 = 0
czaswygrywaniag1 = 0
czaswygrywaniag2 = 0

for i in range(0, 600):
	if wynikg1 > wynikg2:
		czaswygrywaniag1 += 1
	elif wynikg1 < wynikg2:
		czaswygrywaniag2 += 1
	if gracz1.count(i):
		wynikg1 += 1
	elif gracz2.count(i):
		wynikg2 += 1

Chyba o niczym nie zapomniałem? Nieeleganckie, ale chyba najkrótsze i najmniej wymagające intelektualnie. Pomyślę jeszcze nad innymi sposobami.

1

Rozwiązanie z iterowanie po czasie jest jak najbardziej eleganckie i sprytne, natomiast w Twojej implementacji nie wykorzystujesz faktu że masz już posortowane tablice na wejściu, które możesz potraktować jako stosy, i patrzeć tylko na element na szczycie stosu w danej sekundzie, a nie cale tablice przeglądać za każdym razem.

0
gracz1 = [] 
gracz2 = []
wynikg1 = 0
wynikg2 = 0
czaswygrywaniag1 = 0
czaswygrywaniag2 = 0

for i in range(0, 601):
	if wynikg1 > wynikg2:
		czaswygrywaniag1 += 1
	elif wynikg2 > wynikg1:
		czaswygrywaniag2 += 1
	try:
		gracz1.remove(i)
		wynikg1 += 1
	except:
		pass
	try:
		gracz2.remove(i)
		wynikg2 += 1
	except:
		pass
		
for i in range(0, 601):
	if wynikg1 > wynikg2:
		czaswygrywaniag1 += 1
	elif wynikg2 > wynikg1:
		czaswygrywaniag2 += 1
	if len(gracz1) > 0:
		if gracz1[0] == i:
			wynikg1 += 1
			gracz1.pop(0)
	if len(gracz2) > 0:
		if gracz2[0] == i:
			wynikg2 += 1
			gracz2.pop(0)

Który sposób jest lepszy i dlaczego?

1
bkruczyński napisał(a):

Który sposób jest lepszy i dlaczego?

Oba są złe, bo po co pętla ma się obracać 601 razy??? Weź poszukaj takiego hasła jak merging i spróbuj przeglądać jednocześnie obie tablice, ale nie w taki sposób...

1
neves napisał(a):

Rozwiązanie z iterowanie po czasie jest jak najbardziej eleganckie i sprytne, natomiast w Twojej implementacji nie wykorzystujesz faktu że masz już posortowane tablice na wejściu, które możesz potraktować jako stosy, i patrzeć tylko na element na szczycie stosu w danej sekundzie, a nie cale tablice przeglądać za każdym razem.

Nie, to nie jest eleganckie. To jest dokładnie problem symulacji, gdzie mamy wydarzenia w podanych punktach czasowych (to się jakoś nazywa, nie pamiętam jak) i nie ma sensu iterować po minimalnych krokach czasowych, tylko skacze się do najbliższego wydarzenia... Jak byście to zrobili, gdyby dane były podane nie co do jednej sekundy tylko z większą dokładnością? Na przykład do 0.01 sekundy? Wtedy mamy 60001 kroków do ziterowania, całkiem bez sensu... A gdyby dane były we floacie, nie w incie? Co wtedy?

1
koszalek-opalek napisał(a):

Nie, to nie jest eleganckie. To jest dokładnie problem symulacji, gdzie mamy wydarzenia w podanych punktach czasowych (to się jakoś nazywa, nie pamiętam jak) i nie ma sensu iterować po minimalnych krokach czasowych, tylko skacze się do najbliższego wydarzenia... Jak byście to zrobili, gdyby dane były podane nie co do jednej sekundy tylko z większą dokładnością? Na przykład do 0.01 sekundy? Wtedy mamy 60001 kroków do ziterowania, całkiem bez sensu... A gdyby dane były we floacie, nie w incie? Co wtedy?

Rozwiązanie się dobiera do kontekstu zdefiniowanego w problemie, a nie próbuje się rozwiązać bardziej ogólny problem którego nie mamy, no bo po co? KISS

0
neves napisał(a):
koszalek-opalek napisał(a):

Nie, to nie jest eleganckie. To jest dokładnie problem symulacji, gdzie mamy wydarzenia w podanych punktach czasowych (to się jakoś nazywa, nie pamiętam jak) i nie ma sensu iterować po minimalnych krokach czasowych, tylko skacze się do najbliższego wydarzenia... Jak byście to zrobili, gdyby dane były podane nie co do jednej sekundy tylko z większą dokładnością? Na przykład do 0.01 sekundy? Wtedy mamy 60001 kroków do ziterowania, całkiem bez sensu... A gdyby dane były we floacie, nie w incie? Co wtedy?

Rozwiązanie się dobiera do kontekstu zdefiniowanego w problemie, a nie próbuje się rozwiązać bardziej ogólny problem którego nie mamy, no bo po co? KISS

No właśnie -- 601 iteracji dla problemu który można zrobić w kilku(nastu)??? :) KISS :)

0

No właśnie -- 601 iteracji dla problemu który można zrobić w kilku(nastu)??? :) KISS :)

Tylko zrobienie tego w pętli jest znacznie prostsze dla osoby początkującej, niż bardziej skomplikowane algorytmy, które są bardziej ekonomiczne dla procesora, ale trudniejsze do ogarnięcia. A przemielenie 600 razy dwóch prostych sprawdzeń raczej będzie się wykonywać w ułamkach sekund.

1
koszalek-opalek napisał(a):

No właśnie -- 601 iteracji dla problemu który można zrobić w kilku(nastu)??? :) KISS :)

600 jest na tyle małą stałą że nie robi to różnicy w tym wypadku, więc skoro będzie łatwiej komuś to zaimplementować w ten sposób nie widzę żadnej przeszkody by wybrał prostsza wersję.
Natomiast zauważ że "Ilość zdobytych punktów jest nieograniczona" więc wcale nie masz zagwarantowane tych kilkunastu iteracji ;), to będzie właśnie nasza dominująca operacja w tym liniowym algorytmie.

Zresztą z wersji iterującej po czasie i traktującej tablice jako stosy, już jest bardzo niedaleko do wersji która nie potrzebuje iterować po czasie ;)

0

Pewnie mega nieoptymalne, ale co powiecie na to?

os_czasu.png

Mamy sobie oś czasu na, którą nakładamy gracza 1 i gracza 2. Na tej osi buduje się na bilans punktów, który przechyla się w jedną bądź drugą stronę w zależności od tego, który gracz zdobywa punkty.

def polaczTabeleGraczy(t1, t2):
    #dodajemy do laczonych list pary z 1, -1 aby odroznic graczy
    t = list(map(lambda i: [i, 1], t1)) + list(map(lambda i: [i, -1], t2))
    t.sort(key = lambda i: i[0])

    print (t)

    return t

def liczCzasy(g1, g2):
    czas1 = 0
    czas2 = 0

    bilansPunktow = 0

    gracze = polaczTabeleGraczy(g1, g2)

    # jedziemy po "osi czasu" i liczymy punkty każdego gracza
    for e,i in enumerate(gracze):
        if bilansPunktow > 0:
            czas1 += i[0] - gracze[e - 1][0]
        elif bilansPunktow < 0:
            czas2 += i[0] - gracze[e - 1][0]

        bilansPunktow += i[1]

    #potem wygrywający gracz wygrywa do końca gry (do 600 sekundy)
    if bilansPunktow > 0:
        czas1 += 600 - gracze[-1][0]
    elif bilansPunktow < 0:
        czas2 += 600 - gracze[-1][0]

    return czas1, czas2

gracz1 = [27, 189, 201, 541]
#punkty    1,   2,   3,   4

gracz2 = [150, 345, 401, 481, 521]
#punkty     1,   2,   3,   4,   5

cz1, cz2 = liczCzasy(gracz1, gracz2)
print(cz1)
print(cz2)
1

No to jak już wklejamy gotowce to ja bym to napisał to tak, wykorzystując idee ze sortowania przez zliczanie, prościej i bardziej elegancko się chyba nie da :)

            List<int> gracz1 = new List<int>{ 27, 189, 201, 541};
            List<int> gracz2 = new List<int>{150, 345, 401, 481, 521};

            int[] zmianaStanuGry = new int[601];

            gracz1.ForEach(x => ++zmianaStanuGry[x]);
            gracz2.ForEach(x => --zmianaStanuGry[x]);

            int gracz1czas = 0;
            int gracz2czas = 0;
            int stanGry = 0;

            foreach(int zmiana in zmianaStanuGry)
            {
                stanGry += zmiana;

                if (stanGry > 0) gracz1czas++;
                if (stanGry < 0) gracz2czas++;
            }  

1 użytkowników online, w tym zalogowanych: 0, gości: 1