Map - Values nicht korrekt ersetzt (Abzählspiel)

[tom.j85]

Hallo liebe Java-Peers,

Die Aufgabe lautet: 10000 Leute stehen durchnummeriert im Kreis. Nacheinander muss jeder Dritte gehen. Welche 2 Personen bleiben übrig?
Ich weiß...eigentlich kann man das alles mit einem einfachen Array lösen, aber ich habe mir vorgenommen es mit einer Map zu versuchen und bin massiv an meine Grenzen gestoßen.

import java.util.HashMap;

import java.util.Iterator;
import java.util.Map;
import java.util.Set;

public class Durchzaehlen {

    public static void main(String[] args) {
   
// Initiierung der Map

        Map<Integer, Integer> personenMap = new HashMap<Integer, Integer>();

        for (Integer i = 1; i <= 10; i++) {

            personenMap.put(i, i);
        }

        Integer ersterEintragValues = 1;

        while (personenMap.size() >= 3) {

            //drei Methoden s.u.
            loescheAlleDreiSchritte(personenMap);
            setzeKeysNeu(personenMap, ersterEintragValues);
            ersterEintragValues = listeErsterFestlegen(personenMap);

            /**
             * Um zu sehen, wie groß die Map noch ist:
             */
            System.out.println(personenMap.size());
        }
        System.out.println(personenMap);
    }

    // Methoden

    /**
     *
     * @param personenMap Die Liste, in der Personen gespeichert sind, die
     *                    hochzählen
     *
     *                    Die Methode löscht jeden dritten Eintrag mittels eines
     *                    Iterators aus der Liste.
     *
     * @return Die Personenliste wird wieder ausgegeben
     *
     */
    public static Map<Integer, Integer> loescheAlleDreiSchritte(Map<Integer, Integer> personenMap) {

        Iterator<Integer> iterator = personenMap.values().iterator();

        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (next % 3 == 0) {
                iterator.remove();
            }
        }

        return personenMap;
    }

    /**
     *
     * @param personenMap
     *
     * @param counter     setzt den value für personenMap am index 0 fest
     *
     *                    Die Methode setzt das valueSet neu. Erster Eintrag ist der
     *                    counter, dann wird hochgezählt
     *
     * @return Die Liste mit den neuen Values
     *
     */

    public static Map<Integer, Integer> setzeKeysNeu(Map<Integer, Integer> personenMap, Integer counter) {

        for (Integer key : personenMap.values()) {

            if (key != null) {
                personenMap.replace(key, counter);
            }
            counter++;
        }
        return personenMap;
    }

    /**
     *
     * @param map
     *
     *            Legt den ersten Eintrag der Liste per Modulo fest. Bei 10 Personen
     *            im Kreis ist 10 % 3 = 1 in der nächsten Runde muss ab 2 gezählt
     *            werden, daher plus 1
     *
     * @return
     */
    public static Integer listeErsterFestlegen(Map<Integer, Integer> map) {

        Integer listeErster = (map.size() % 3) + 1;
        return listeErster;
    }
}

Die Idee:

Der Key der Map ist eine feste Zahl, beginnend mit eins und hochgezählt - die ID der Person quasi. Der Value zählt ebenfalls hoch, wird aber nach jeder runde (wenn "durchgezählt" wurde) wieder neu gesetzt (bei z.b. 10 Leuten fängt No. 1 nach einer Runde nicht bei eins an zu zählen sonder sagt "zwei"). Aus der Map wird jeder Eintrag, der durch drei teibar ist, gelöscht.

Das Problem:

Die ersten beiden Runden funktionieren die Methoden, ab der dritten wird der Initialwert (ersterEintragValues) falsch gesetzt (nicht auf 3 sondern wieder auf eins, laut eclipse debugger).

Die Map:
Runde 1:
Runde 2: {1=1, 2=2, 4=3, 5=4, 7=5, 8=6, 10=7}
Runde 3: {1=1, 2=2, 5=4, 7=5, 10=7} --> da sollte mit {1=3, 2=4.....} stehen

Außerdem werden die Values nicht korrekt hochgezählt:
Runde 4: {1=2, 2=3, 5=5, 7=6, 10=7} --> da sollte, wenn schon, {1=2, 2=3, 5=3...} stehen.

Vielleicht hat jedamd den erleuchtenden Tipp

Es entsteht eine Endlosschleife bei map.size = 3 ...vermutlich weil er keine Values mehr findet, die durch drei teilbar sind. Ich geh den Code dur

 

[krgewb]

1. Wenn du den value ersetzen willst, musst du einfach put verwenden.
2. Bei einer HashMap kann die Reihenfolge jedesmal anders sein. Es gibt keinen Index. Mathematisch gesehen ist ein HashSet eine Menge. Eine Menge enthält keine Duplikate. Außerdem gibt es keine Reihenfolge. Zum Beispiel die Menge Hobbies: {Reiten, Schach spielen, Spazieren}. Die Reihenfolge ist egal. Wenn du zeigen, willst, welche Hobbies du mehr magst, musst du es anders machen. Das Beispiel zeigt auch, dass es keine Duplikate gibt. Solch eine Menge würde ja keinen Mehrwert geben: {Reiten, Schach spielen, Reiten, Spazieren}

 

[mihe7]

Das Ganze ist aber schon von hinten durch die Brust ins Auge...

Problem 1: eine Map garantiert keine Reihenfolge der Einträge. Du willst aber eine Ordnung, also eine SortedMap. Als Implementierung verwende einfach eine TreeMap.

Problem 2: Du musst die Position der Elemente setzen, bevor Du jedes dritte entfernst. Das erreichst Du, indem Du einfach die Zeilen in Deiner Schleife vertauschst:

Problem 3: Du musst in setzeKeysNeu schon über die Schlüssel und nicht über die Werte iterieren.

Den Code mal an die drei Punkte angepasst:

public class Durchzaehlen {

    public static void main(String[] args) {
   
// Initiierung der Map

        SortedMap<Integer, Integer> personenMap = new TreeMap<>();

        for (Integer i = 1; i <= 10; i++) {
            personenMap.put(i, i);
        }

        Integer ersterEintragValues = 1;

        System.out.println(personenMap);
        while (personenMap.size() >= 3) {

            //drei Methoden s.u.
            loescheAlleDreiSchritte(personenMap);
            ersterEintragValues = listeErsterFestlegen(personenMap);
            setzeKeysNeu(personenMap, ersterEintragValues);

            System.out.println(personenMap);
        }
    }

    // Methoden

    /**
     *
     * @param personenMap Die Liste, in der Personen gespeichert sind, die
     *                    hochzählen
     *
     *                    Die Methode löscht jeden dritten Eintrag mittels eines
     *                    Iterators aus der Liste.
     *
     * @return Die Personenliste wird wieder ausgegeben
     *
     */
    public static Map<Integer, Integer> loescheAlleDreiSchritte(SortedMap<Integer, Integer> personenMap) {

        Iterator<Integer> iterator = personenMap.values().iterator();

        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (next % 3 == 0) {
                iterator.remove();
            }
        }

        return personenMap;
    }

    /**
     *
     * @param personenMap
     *
     * @param counter     setzt den value für personenMap am index 0 fest
     *
     *                    Die Methode setzt das valueSet neu. Erster Eintrag ist der
     *                    counter, dann wird hochgezählt
     *
     * @return Die Liste mit den neuen Values
     *
     */

    public static Map<Integer, Integer> setzeKeysNeu(SortedMap<Integer, Integer> personenMap, Integer counter) {
        
        for (Integer key : personenMap.keySet()) {

            if (key != null) {
                personenMap.replace(key, counter);
            }
            counter++;
        }
        return personenMap;
    }

    /**
     *
     * @param map
     *
     *            Legt den ersten Eintrag der Liste per Modulo fest. Bei 10 Personen
     *            im Kreis ist 10 % 3 = 1 in der nächsten Runde muss ab 2 gezählt
     *            werden, daher plus 1
     *
     * @return
     */
    public static Integer listeErsterFestlegen(Map<Integer, Integer> map) {

        Integer listeErster = (map.size() % 3) + 1;
        return listeErster;
    }
}

 

[MoxxiManagarm]

10000 Leute stehen durchnummeriert im Kreis

Genau genommen wäre es das Beste, das auch genau so zu implementieren. Nämlich einen Kreis. Zumindest bin ich dieser Meinung. Um einen Kreis abzubilden eignet sich eine LinkedList, deren Tail wieder auf den Head zeigt anstatt auf null.

class CircularPersonLinkedList {
  private PersonNode current = null; // TODO: Implement PersonNode
  private int size = 0;
 
  public addPerson(int p) { // p ist the number of the person and the value of the node
    // TODO
  }

  public step(int n) {
    for (int i = 1; i <= n; i++) {
      current = current.next;
    }
  }

  public removeCurrent() {
    // TODO
  }

  public int getSize() {
    return size;
  }

  public void print() {
    // TODO
  }

  public static void main() {
    CircularPersonLinkedList circle = new CircularPersonLinkedList();

    for (int i = 1; i <= 10000; i++) {
      circle.addPerson(i);
    }

    while (circle.size > 2) {
      circle.step(3);
      circle.removeCurrent();
    }

    circle.print();
  }
}

Anregung kannst du dir dafür auch im Web holen, z.B. hier https://www.baeldung.com/java-circular-linked-list

 

[tom.j85]

Besten Dank für den Input, krgewb und nicht zuletzt mihe7 haben die entscheidenden Fehler gefunden (die LinkedList von MoxxiManagarm schaue ich mir auch nochmal an, vielen Dank!)

Zunächst natürlich: Ich denke auch niemand, wirklich niemand sollte so coden, aber es packt mich einfach wenn ich mir Dinge vorstelle und sie nicht funktionieren...

Ich habe alle Vorschläge eingebaut. Zusätzlich war auch der erste Eintrag für die nächste Runde falsch gesetzt. Das scheint nicht richtig mit Modulo zu funktionieren. Ich habe mir mit Iterator den letzten Value ausgeben lassen und plus eins gerechnet. Wahlweise könnte man auch die Values in einen Array überführen und den Wert der letzten Stelle verwenden.

Der Code, wie er funktioniert, sieht jetzt so aus:

import java.util.*;

public class Durchzaehlen {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        SortedMap<Integer, Integer> personenMap = new TreeMap<Integer, Integer>();

        for (Integer i = 1; i <= 10000; i++) {
            personenMap.put(i, i);
        }

        Integer ersterEintragValues = 1;

        while (personenMap.size() >= 3) {

            
            setzeKeysNeu(personenMap, ersterEintragValues);
            ersterEintragValues = listeErsterFestlegen(personenMap);
            loescheAlleDreiSchritte(personenMap);
            
            
            /**
             * Um zu sehen, in welcher Runde sich das Programm befindet:
             */

            System.out.println(personenMap.size());

        }

        System.out.println(personenMap);

    }

    // Methoden

    /**
     *
     * @param personenMap Die Liste, in der Personen gespeichert sind, die
     *                    hochzählen
     *
     *                    Die Methode löscht jeden dritten Eintrag mittels eines
     *                    Iterators aus der Liste.
     *
     * @return Die Personenliste wird wieder ausgegeben
     *
     */

    public static SortedMap<Integer, Integer> loescheAlleDreiSchritte(SortedMap<Integer, Integer> personenMap) {

        Iterator<Integer> iterator = personenMap.values().iterator();
        while (iterator.hasNext()) {
            Integer next = iterator.next();
            if (next % 3 == 0) {
                iterator.remove();
            }
        }
        return personenMap;
    }

    /**
     *
     * @param personenMap
     *
     * @param counter     setzt den value für personenMap am index 0 fest
     *
     *                    Die Methode setzt das valueSet neu. Erster Eintrag ist der
     *                    counter, dann wird hochgezählt
     *
     * @return Die Liste mit den neuen Values
     *
     */

    public static SortedMap<Integer, Integer> setzeKeysNeu(SortedMap<Integer, Integer> personenMap, Integer counter) {

        for (Integer key : personenMap.keySet()) {
            if (key != null) {
                personenMap.replace(key, counter);
            }
            counter++;
        }
        return personenMap;
    }

    /**
     *
     * @param map
     *
     *              Legt den ersten Eintrag der Liste mittels Iterator fest. Der letzte Eintrag + 1
     *              ist der erste Eintrag der neuen Runde
     *             
     *             
     *              Alternativ: Values in einen Array überführen und den letzten Eintrag aus geben,
     *              der plus eins gerechnet wird (Zählung geht in nächste Runde)
     *             
//     *             
     * @return
     */

    public static Integer listeErsterFestlegen(Map<Integer, Integer> map) {
        
            
        Iterator<Integer> iterator = map.values().iterator();
        Integer lastEntry = null;
        
        while (iterator.hasNext()) {
            lastEntry = iterator.next();
        }
        
        Integer firstNextEntry = lastEntry + 1;
        return firstNextEntry;
        
        
        
        // wahlweise mit Array:
        
//        Object[] lastEntry = map.values().toArray();
//       
//        Integer firstNextEntry = (Integer)lastEntry[lastEntry.length -1] + 1;
//       
//        return nextFirst;
        
        
    

    }

}

Vielen Dank an alle!

 

[Meniskusschaden]

Genau genommen wäre es das Beste, das auch genau so zu implementieren. Nämlich einen Kreis.

So sehe ich das auch. Alternativ - falls man die vordefinierten Datenstrukturen nutzen möchte - könnte man auch einfach eine Queue verwenden, aus der man fortwährend Elemente entnimmt und (bis auf jedes dritte) sofort wieder einfügt, bis nur noch zwei Elemente übrig sind.

 

[MoxxiManagarm]

Der Code, wie er funktioniert, sieht jetzt so aus:

Und was kommt bei dir raus? (Eigentlich eine Funfrage, ich habe es schon überprüft, du bekommst das Gleiche Ergebnis) Ich habe gerade mal fix meinen Vorschlag ausprogrammiert. Quick & dirty sieht es so aus:

Spoiler

package de.javaforum.circle;

class CircularPersonLinkedList {
    class PersonNode {
        protected PersonNode next;
        protected PersonNode prev;
        private int index;

        protected PersonNode(int index) {
            this.index = index;
        }

        @Override
        public String toString() {
            return "" + index;
        }
    }

    private PersonNode current = null;
    private int size = 0;

    public void addPerson(int p) {
        PersonNode node = new PersonNode(p);

        if (current == null) {
            node.next = node;
            node.prev = node;
        } else {
            current.next.prev = node;
            node.next = current.next;
            current.next = node;
            node.prev = current;
        }

        current = node;
        size++;
    }

    public void step(int n) {
        for (int i = 1; i <= n; i++) {
            current = current.next;
        }
    }

    public void delinkCurrent() {
        current.prev.next = current.next;
        current.next.prev = current.prev;

        current = current.prev;

        size--;
    }

    public void print() {
        PersonNode marker = current;

        do {
            System.out.print(current + " ");
            step(1);
        } while(marker != current);

        System.out.println();
    }

    public static void main(String... args) {
        CircularPersonLinkedList circle = new CircularPersonLinkedList();

        for (int i = 1; i <= 10000; i++) {
            circle.addPerson(i);
            //circle.print();
        }

        System.out.println("---");

        while (circle.size > 2) {
            circle.step(3);
            circle.delinkCurrent();
            //circle.print();
        }

        circle.print();
    }
}

Ergebnis:

Spoiler

2692 8923

Nur, dass die LinkedList Variante ca. 50% der Zeit benötigt

 

[MoxxiManagarm]

Ich habe gerade noch Menikus' Variante ausprobiert, sie ist an Geschwindigkeit und Kürze so vermutlich fast nicht zu übertreffen ;-)

Spoiler

LinkedList<Integer> queue = new LinkedList<>();

for (int i = 1; i <= 10000; i++) {
    queue.add(i);
}

while (queue.size() > 2) {
    queue.add(queue.poll());
    queue.add(queue.poll());
    queue.poll();
}

System.out.println(queue);

 

[tom.j85]

Nicht schlecht, das übertrifft alles. Die Zahlen habe ich auch raus. Handelte es sich um echte Menschen, hätte der Vorletzte (die Nummer 2692) übrigens bis 29993 gezählt und der Letzte (Nummer 8923) bis zur Zahl 29995... just FYI

 

[httpdigest]

Man kann für dieses Josephus-Problem auch die rekursive Lösung für den general case nehmen und diese entweder rekursiv implementieren oder relativ einfach in eine iterative Lösung umwandeln.
Das habe ich mal gemacht. Hier eine Lösung mit frei wählbarem `n` (Anzahl der Personen im Kreis, hier n=10000), `k` (der wievielte soll jeweils "ausgelöscht" werden, hier k=3) und `m` (die wievielten zuletzt übrigen Personen sollen ausgegeben werden):

public class Josephus {
  public static int[] j(int n, int k, int m) {
    int[] res = new int[m];
    for (int i = m; i <= n; i++)
      for (int j = 0; j < m; j++)
        if (i > j + 1)
          res[j] = (res[j] + k) % i;
    return res;
  }
  public static void main(String[] args) {
    System.out.println(Arrays.toString(j(10000, 3, 2))); // <- [2691, 8922]
  }
}

Man muss hier nur immer 1 zum Ergebnis dazurechnen, wenn man mit 1 statt 0 anfängt zu zählen.

 

[abc66]

So sehe ich das auch. Alternativ - falls man die vordefinierten Datenstrukturen nutzen möchte - könnte man auch einfach eine Queue verwenden, aus der man fortwährend Elemente entnimmt und (bis auf jedes dritte) sofort wieder einfügt, bis nur noch zwei Elemente übrig sind.

Meinst Du das so:

public static void spiel(ArrayDeque<String> d, int targetSize, int nth) {
	while (d.size() > targetSize) {
		for (int i = 1; i < nth; i++) {
			d.add(d.poll());
		}
		System.out.println(d.poll() + " muss gehen.");
		System.out.println("Es verbleiben: " + d);
	}
}

public static void main(String[] args) {
	spiel(new ArrayDeque<String>(Arrays.stream(
			"Herzogin von Alba Maria del Rosario Cayetana Alfonsa Victoria Eugenia Francisca Fitz-James Stuart y de Silva"
			.split(" "))
			.collect(Collectors.toList())), 2, 3);
}

Alba muss gehen.
Es verbleiben: [Maria, del, Rosario, Cayetana, Alfonsa, Victoria, Eugenia, Francisca, Fitz-James, Stuart, y, de, Silva, Herzogin, von]
Rosario muss gehen.
Es verbleiben: [Cayetana, Alfonsa, Victoria, Eugenia, Francisca, Fitz-James, Stuart, y, de, Silva, Herzogin, von, Maria, del]
Victoria muss gehen.
Es verbleiben: [Eugenia, Francisca, Fitz-James, Stuart, y, de, Silva, Herzogin, von, Maria, del, Cayetana, Alfonsa]
Fitz-James muss gehen.
Es verbleiben: [Stuart, y, de, Silva, Herzogin, von, Maria, del, Cayetana, Alfonsa, Eugenia, Francisca]
de muss gehen.
Es verbleiben: [Silva, Herzogin, von, Maria, del, Cayetana, Alfonsa, Eugenia, Francisca, Stuart, y]
von muss gehen.
Es verbleiben: [Maria, del, Cayetana, Alfonsa, Eugenia, Francisca, Stuart, y, Silva, Herzogin]
Cayetana muss gehen.
Es verbleiben: [Alfonsa, Eugenia, Francisca, Stuart, y, Silva, Herzogin, Maria, del]
Francisca muss gehen.
Es verbleiben: [Stuart, y, Silva, Herzogin, Maria, del, Alfonsa, Eugenia]
Silva muss gehen.
Es verbleiben: [Herzogin, Maria, del, Alfonsa, Eugenia, Stuart, y]
del muss gehen.
Es verbleiben: [Alfonsa, Eugenia, Stuart, y, Herzogin, Maria]
Stuart muss gehen.
Es verbleiben: [y, Herzogin, Maria, Alfonsa, Eugenia]
Maria muss gehen.
Es verbleiben: [Alfonsa, Eugenia, y, Herzogin]
y muss gehen.
Es verbleiben: [Herzogin, Alfonsa, Eugenia]
Eugenia muss gehen.
Es verbleiben: [Herzogin, Alfonsa]

 

[httpdigest]

Korrektur:

public static int[] j(int n, int k, int m) {
  int[] res = new int[m];
  for (int i = 1; i <= n; i++)
    for (int j = 0; j < m; j++)
      res[j] = i <= j ? j : (res[j] + k) % i;
  return res;
}

 

[MoxxiManagarm]

Meinst Du das so:

Nein, er meinte das wie in Post #8

 

[abc66]

Nein, er meinte das wie in Post #8

Du brauchst nicht bockig sein, meins ist besser.