Αλγόριθμος ζάρι

alou · 16 Νοεμβρίου 2016

Εαν ομως εχεις 1,3,3,3

Τοτε εχεις 50% να κεδρισεις και 25% να χασεις.

Πως το βγάζεις αυτό?

iceblade · 16 Νοεμβρίου 2016

Το πρόβλημα είναι ενδιαφέρον, γιατί έχει και την ιδιότητα του non-transativity, δηλαδή αν πχ έχουμε 3 σετ A,B,C μπορεί το A να νικάει το B, το Β να νικάει το C αλλά το C να νικάει το A. Είσαι σίγουρος ότι το πρόβλημα λύνεται για n (arbitrary) αριθμό από έδρες και ότι έχει και global optimum?

tsofras · 16 Νοεμβρίου 2016

Μήπως καλύτερη λύση θα ήταν να κάνεις ένα simulation με το ζάρι του 1ου παίχτη στις 100 φορές , να βρείς τις πιθανότητες για κάθε έδρα και μετα να υπολογίσεις τις δικές σου?

alou · 16 Νοεμβρίου 2016

@tsofras: οι πιθανότητες είναι για τον κάθε ένα συγκεκριμένες, νίκες / αριθμό γεγονότων. Οι νίκες είναι βέβαια πάντα σε συνδυασμό με τον αντίπαλο και ισχύει αυτό που λέει ο iceblade (non-transative)

@iceblade: δεν μιλάει νομίζω πουθενά για global optimum, έχεις input και με βάση αυτό φτιάχνεις ένα σετ που θα πάρει το καλύτερο δυνατό αποτέλεσμα (μερικές φορές είναι αδύνατη η νίκη έτσι και αλλιώς).

Γμτ έχω δουλειά...

Zaytsev · 16 Νοεμβρίου 2016

Δε θα σου δώσω τον αλγόριθμο, αλλά θα σου εξηγήσω το σκεπτικό.

Ο αντίπαλος έχει ένα ζάρι [1,2,3,4,5,6] όπου το άθροισμα είναι 21.

Άρα εσύ, πρέπει να μοιράσεις το 21 με τέτοιιο τρόπο, ώστε να έχεις 50% +1 πιθανότητες να τον κερδίσεις.

Άρα, με τις έξι έδρες, το 50% + 1 είναι 4 έδρες. Που σημαίνει ότι χρειάζεσαι 4 καλύτερες από του αντιπάλου.

Θα πάρεις λοιπόν τις υπόλοιπες, 2 εδώ (5, 6), θα τις φέρεις στη μονάδα και θα μοιράσεις τις υπόλοιπες μονάδες (4, 5 αντίστοιχα) στις έδρες σου, κατά τέτοιο τρόπο ώστε όλες να είναι +1 από τη επόμενη μεγαλύτερή του, εδώ δηλαδή το 4.

πχ το 4 σου, θα το κάνεις 5 (υπόλοιπο 8 μονάδες)

το 3 σου θα το κάνεις 5 (υπόλοιπο 6 μονάδες)

Το 2 σου θα το κάνεις 5 (υπόλοιπο 3 μονάδες)

Το 1 σου θα το κάνεις 4 (υπόλοιπο 0 μονάδες)

Άρα έχεις [4,5,5,5,1,1] εναντίον [1,2,3,4,5,6]

alou · 16 Νοεμβρίου 2016

Αυτά που λες ( [4,5,5,5,1,1] εναντίον [1,2,3,4,5,6] ) έχουν ίδιες πιθανότητες έτσι όπως το βλέπω / υπολογίζω τουλάχιστον και δεν ισχύει αυτή η λογική σε όλο το φάσμα των πιθανών συνδυασμών.

Το σκορ σου προέρχεται από συνδυασμό νικών και αποφυγής ήττας, δεν γίνεται να το προσδιορίσεις μόνο με 50%+1 νίκες γιατί είναι αδύνατο σε πολλές περιπτώσεις οπότε πρέπει να πας για το μεγαλύτερο αριθμό που θα προκύπτει από το νίκες - ήττες με τον συγκεκριμένο αντίπαλο.

Zaytsev · 16 Νοεμβρίου 2016

Aν μας πεις πως το υπολογίζεις, θα καταλάβουμε το σκεπτικό σου

Εδώ έχουμε:

1: 5 ήττες, 1 ισοπαλία

4: 3 νίκες, 1 ισοπαλία, 2 ήττες

5: 4 νίκες, 1 ισοπαλία, 1 ήττα

Άρα, στο σύνολο έχεις 6 ισοπαλίες, 15 ήττες, 15 νίκες, που σημαίνει 50%-50%. Το αναφέρει ο TS ότι αν οι τιμές είναι συνεχόμενες, δεν μπορείς να κερδίσεις. Επίσης, αναφέρει ότι οι τιμές δεν είναι συγκεκριμένες ανά έδρα. Άρα, θα μπορούσε το ζάρι να είναι [6,6,6,6,6,6], όπου δε θα κερδίσεις ποτέ.

Το σκεπτικό της άσκησης, επειδή αρκετοί από εμάς την έχουμε κάνει στο Πανεπιστήμιο, είναι να βρει τον αλγόριθμο που του δίνει το αποτέλεσμα κι όχι να κερδίζει πάντα. Για αυτό δεν του έγραψα τον αλγόριθμο καθαυτόν, αλλά το έδωσα μια κατεύθυνση.

alou · 16 Νοεμβρίου 2016

Sorry δεν το είδες ίσως αλλά είπα πως το υπολογίζω λίγο πριν. Νόμιζα ότι ενοούσες πως δεν ήταν 50-50 το συγκεκριμένο παράδειγμα, γιαυτό το ανέφερα, συμφωνούμε σε αυτό.

Εγω καταλαβαίνω ότι ο στόχος δεν είναι να βρεις τον τρόπο υπολογισμού των πιθανοτήτων αλλά να βρεις αντίπαλο με τις καλύτερες δυνατές πιθανότητες με βάση το input που σου δίνει.

k33theod · 16 Νοεμβρίου 2016

Γιατι να εχεις μεγαλυτερες τιμες στις μισες εδρες; Ο σκοπος ειναι να εχεις μεγαλυτερη πιθανοτητα απο τον αντιπαλο.

Αυτο που θες ειναι περισσοτερες εδρες νικης απο τον αντιπαλο. Για να το πετυχεις αυτο, θες μια εδρα που να χανει απο ολες τις εδρες του αντιπαλου.

Πχ αν ο αντιπαλος εχει 1,2,3,4 και εσυ 1,2,3,4

Τοτε οι πιθανότητες ειναι 50-50

Εαν ομως εχεις 1,3,3,3

Τοτε εχεις 50% να κεδρισεις και 25% να χασεις.

Δεν είναι έτσι decideWinner ([1,3,3,3],[1,2,3,4])

(6, 6) To ζάρι [1,2,3,4] απ' ότι φένεται δεν χτυπιέται

Η decideWinner όπως την έδωσε ο alou

Δε θα σου δώσω τον αλγόριθμο, αλλά θα σου εξηγήσω το σκεπτικό.

Ο αντίπαλος έχει ένα ζάρι [1,2,3,4,5,6] όπου το άθροισμα είναι 21.

Άρα εσύ, πρέπει να μοιράσεις το 21 με τέτοιιο τρόπο, ώστε να έχεις 50% +1 πιθανότητες να τον κερδίσεις.

Άρα, με τις έξι έδρες, το 50% + 1 είναι 4 έδρες. Που σημαίνει ότι χρειάζεσαι 4 καλύτερες από του αντιπάλου.

Θα πάρεις λοιπόν τις υπόλοιπες, 2 εδώ (5, 6), θα τις φέρεις στη μονάδα και θα μοιράσεις τις υπόλοιπες μονάδες (4, 5 αντίστοιχα) στις έδρες σου, κατά τέτοιο τρόπο ώστε όλες να είναι +1 από τη επόμενη μεγαλύτερή του, εδώ δηλαδή το 4.

πχ το 4 σου, θα το κάνεις 5 (υπόλοιπο 8 μονάδες)

το 3 σου θα το κάνεις 5 (υπόλοιπο 6 μονάδες)

Το 2 σου θα το κάνεις 5 (υπόλοιπο 3 μονάδες)

Το 1 σου θα το κάνεις 4 (υπόλοιπο 0 μονάδες)

Άρα έχεις [4,5,5,5,1,1] εναντίον [1,2,3,4,5,6]

είναι επίσης λάθος το [1,2,3,4,5,6] δεν νικιέται

Zaytsev · 16 Νοεμβρίου 2016

είναι επίσης λάθος το [1,2,3,4,5,6] δεν νικιέται

Την εκφώνιση της άσκησης τη διάβασες;

Βάζει ότι θέλεις στις έδρες.

Θα μπορούσε να βάλει [6,6,6,6,6,6].

Νικιέται;

k33theod · 16 Νοεμβρίου 2016

Μέχρι στιγμής έχω γράψει αυτό σε python το οποίο είναι λάθος τελικά

χτυπάει σε τεστ.

def winning_die(a):
  lena=len(a)
  a.sort()
  b=[i for i in a]
  count1=a.count(1)
  k=count1+(len(-count1)//2
  l=0+count1
  awins,bwins=decideWinner (a,
  for i in range(30):
    if awins>=bwins:
      change_die(
      awins,bwins=decideWinner(a,
    else:
      return b  
  return []

def decideWinner (a,:
  awins = 0
  bwins = 0
  for i in range(len(a)):
    for j in range(len():
      if(a[i] > b[j]):
        awins +=1
      elif a[i] < b[j]:
        bwins +=1
    
  return awins, bwins

def change_die(a):
  max_count=1
  max_count_index=0
  count1=a.count(1)
  k=count1+(len(a)-count1)//2
  for i in range(len(a)):
    if a.count(a[i])>=max_count:
      max_count=a.count(a[i])
      max_count_index=i
  index_to_reduce=0
  for i in a:
    if i>1:
      index_to_reduce=a.index(i)
      break
  if max_count>1:
    a[max_count_index]+=1
    a[index_to_reduce]-=1
  else:
    a[k]+=1
    a[index_to_reduce]-=1
  return a

Ετσι αποφάσισα να χρησιμοποιήσω τον εξής αλγόριθμο

αλλάζω το αρχικό ζάρι ένα στοιχείο κάθε φορά κατά 1 και βρίσκω ποια αλλαγή μου δίνει μέγιστο ώφελος αδιαφορόντας για το άθροισμα

στη συνέχεια στο νέο ζάρι αφαιρώ ένα από κάθε στοιχείο κάθε φορά ώστε να είμαι στο ίδιο άθροισμα και ελέγχω πάλι

άν βγάλω νικητή είναι οκ αλλιώς συνεχίζω

η συνάρτηση μου για το μέγιστο benefit είναι αυτή

def increase_die(a,:#ίδιο α και β 
  awins,bwins=decideWinner (a,
  max_benefit=bwins-awins
  index_to_increase=0
  for i in range((len()):
    b[i]+=1
    awins,bwins=decideWinner (a,
    b[i]-=1
    if bwins-awins>max_benefit:
      index_to_increase=i
      max_benefit=bwins-awins
  b[index_to_increase]+=1 
  return b

Την εκφώνιση της άσκησης τη διάβασες;

Βάζει ότι θέλεις στις έδρες.

Θα μπορούσε να βάλει [6,6,6,6,6,6].

Νικιέται;

Βασίλη το [6,6,6,6,6,6] νικιέται ας σου φένεται παράδοξο

decideWinner ([6,6,6,6,6,6],[4, 6, 6, 6, 7, 7])

(6, 12)

tsofras · 16 Νοεμβρίου 2016

Το ξέρει ο νικιέται ,το έβαλε ώς παράδειγμα επειδή είπες ότι δεν νικιέται το [1,2,3,4,5,6]

παπι · 16 Νοεμβρίου 2016

Πως το βγάζεις αυτό?

ενδιαφερων

1,2,3,4 == 1,3,3,3 > 0,3,3,4

ψιλοπαραδοξο χεχε

alou · 16 Νοεμβρίου 2016

Δοκιμάζω και μια άλλη προσέγγιση, προσπαθώντας να υπάρχει μια λογική (πάνω κάτω αυτό που λέει και ο Zaytsev αλλά με συγκεκριμένο στόχο) αλλά θέλει αρκετή δουλειά και την προσέγγιση που θα έχεις στις υπόλοιπες περιπτώσεις, μέχρι να το ξαναπιάσω ίσως κάποιος ενδιαφέρεται.

Η λογική είναι ότι στοχεύεις το μεσαίο (ή το μεσαίο + 1 σε ζυγό αριθμό στοιχείων) νούμερο και βλέπεις αν μπορείς να έχεις πάνω από τα μισά στοιχεία μεγαλύτερα. Αυτό, μάλλον, με κάποιες προϋποθέσεις σου εξασφαλίζει ότι κερδίζεις...

let createWinner = (loser) => {
	let length = loser.length,
		isEven = length % 2 === 0,
		total = 0, midNumber = 0, remainingNumbers = 0, targetNumber = 0;

	loser.map((num) => total += num);
	loser.sort( (a, => a - ;
	
	!isEven ? midNumber = (length - 1) / 2
			: midNumber = length / 2;

	remainingNumbers = length - midNumber;
	targetNumber = loser[midNumber] + 1;

	let easyWin = (midNumber * targetNumber + remainingNumbers) <= total;
	let winner = [];

	if (easyWin) {
		let remainder = total;
		for (let i=0;i<midNumber;i++) {
			winner.push(targetNumber);
			remainder -= targetNumber;
		}
		for (let ii = 1; ii <= remainingNumbers; ii++) {
			if (ii === remainingNumbers) {
				winner.push(remainder);
			} else if (remainder > (targetNumber + remainingNumbers - 1)) {
				winner.push(targetNumber);
				remainder -= targetNumber;
			} else {
				winner.push((remainder - remainingNumbers) + 1);
				remainder -= ((remainder - remainingNumbers) + 1);
			}
		}

		return winner;
		
	} else {
		//...
	}



}

k33theod · 16 Νοεμβρίου 2016

Δεν άντεξα το έλυσα με πουστιά βάζοντας μια εξαίρεση στο κώδικα για το σφάλμα που έπαιρνα μιας και ήταν στο τελευταίο test.

Τώρα μπορώ να δώ τις λύσεις των άλλων

Μόλις βρώ πως γίνονται τα spoiler θα ποστάρω μερικές

και για να μην ανυσηχούμε

Users attempted: 170 Users succeeded: 92

Δοκιμάζω και μια άλλη προσέγγιση, προσπαθώντας να υπάρχει μια λογική (πάνω κάτω αυτό που λέει και ο Zaytsev αλλά με συγκεκριμένο στόχο) αλλά θέλει αρκετή δουλειά και την προσέγγιση που θα έχεις στις υπόλοιπες περιπτώσεις, μέχρι να το ξαναπιάσω ίσως κάποιος ενδιαφέρεται.

Η λογική είναι ότι στοχεύεις το μεσαίο (ή το μεσαίο + 1 σε ζυγό αριθμό στοιχείων) νούμερο και βλέπεις αν μπορείς να έχεις πάνω από τα μισά στοιχεία μεγαλύτερα. Αυτό, μάλλον, με κάποιες προϋποθέσεις σου εξασφαλίζει ότι κερδίζεις...
let createWinner = (loser) => {
	let length = loser.length,
		isEven = length % 2 === 0,
		total = 0, midNumber = 0, remainingNumbers = 0, targetNumber = 0;

	loser.map((num) => total += num);
	loser.sort( (a, => a - ;
	
	!isEven ? midNumber = (length - 1) / 2
			: midNumber = length / 2;

	remainingNumbers = length - midNumber;
	targetNumber = loser[midNumber] + 1;

	let easyWin = (midNumber * targetNumber + remainingNumbers) <= total;
	let winner = [];

	if (easyWin) {
		let remainder = total;
		for (let i=0;i<midNumber;i++) {
			winner.push(targetNumber);
			remainder -= targetNumber;
		}
		for (let ii = 1; ii <= remainingNumbers; ii++) {
			if (ii === remainingNumbers) {
				winner.push(remainder);
			} else if (remainder > (targetNumber + remainingNumbers - 1)) {
				winner.push(targetNumber);
				remainder -= targetNumber;
			} else {
				winner.push((remainder - remainingNumbers) + 1);
				remainder -= ((remainder - remainingNumbers) + 1);
			}
		}

		return winner;
		
	} else {
		//...
	}



}

Αυτό που λέει ο Zaytsev αν και φαίνεται λογικό δεν ισχύει και νομίζω άδικα θα κουραστείς

winning_die([2, 2, 5, 5, 5, 5]) == [3, 3, 3, 3, 6, 6] Το δεύτερο νικάει το 1ο αν και χάνει σε 4 έδρες και κερδίζει σε 2

decideWinner([2, 2, 5, 5, 5, 5],[3, 3, 3, 3, 6, 6])

(16, 20)

Αν καταλαβαίνω καλά την πρότασή του.

Νομίζω ότι ο μόνος τρόπος για να προσεγγιστεί το πρόβλημα είναι μέσω της decideWinner

Σύνδεση

Αλγόριθμος ζάρι

Προτεινόμενες αναρτήσεις

alou

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Συχνή συμμετοχή στο θέμα

Δημοφιλείς Ημέρες

Δημοφιλή Μηνύματα

alou

alou

Zaytsev

iceblade

tsofras

alou

Zaytsev

alou

Zaytsev

alou

k33theod

Zaytsev

k33theod

tsofras

παπι

alou

k33theod

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Δημιουργία λογαριασμού

Σύνδεση

alou

alou

Zaytsev

Σύνδεση