diff options
Diffstat (limited to 'šola/p1/wordle/Tekm_63230317.java')
| -rw-r--r-- | šola/p1/wordle/Tekm_63230317.java | 217 |
1 files changed, 217 insertions, 0 deletions
diff --git a/šola/p1/wordle/Tekm_63230317.java b/šola/p1/wordle/Tekm_63230317.java new file mode 100644 index 0000000..7059642 --- /dev/null +++ b/šola/p1/wordle/Tekm_63230317.java @@ -0,0 +1,217 @@ +import java.util.*; +public class Tekm_63230317 implements Stroj { + static class OpisBesede { + TreeSet<Character> črkeVBesedi; + boolean črkeNiVBesedi[]; + boolean črkeNiNaPoziciji[][]; // ko dobimo o si zabeležimo, da ta črka ni na tej poziciji + char gotoveČrke[]; + public OpisBesede (int d) { + črkeVBesedi = new TreeSet<>(); + črkeNiVBesedi = new boolean[256]; + gotoveČrke = new char[d]; + črkeNiNaPoziciji = new boolean[d][256]; + } + public OpisBesede (OpisBesede o) { + črkeVBesedi = new TreeSet<>(o.črkeVBesedi); + črkeNiVBesedi = Arrays.copyOf(o.črkeNiVBesedi, o.črkeNiVBesedi.length); + črkeNiNaPoziciji = Arrays.copyOf(o.črkeNiNaPoziciji, o.črkeNiNaPoziciji.length); + gotoveČrke = Arrays.copyOf(o.gotoveČrke, o.gotoveČrke.length); + } + public void gotovaČrka (int pozicija, char črka) { + gotoveČrke[pozicija] = črka; + črkeVBesedi.add(črka); + } + public void možnaČrka (int pozicija, char črka) { + črkeNiNaPoziciji[pozicija][črka] = true; + črkeVBesedi.add(črka); + } + public boolean aČrkeNiNaPoziciji (int pozicija, char črka) { + if (črkeNiVBesedi[črka]) + return true; + if (črkeNiNaPoziciji[pozicija][črka]) + return true; + return false; + } + public void informacije (String ugib, List<Character> odziv) { + for (int i = 0; i < gotoveČrke.length; i++) { + if (odziv.get(i) == '+') + gotovaČrka(i, ugib.charAt(i)); + if (odziv.get(i) == '-') + črkeNiVBesedi[ugib.charAt(i)] = true; + if (odziv.get(i) == 'o') + možnaČrka(i, ugib.charAt(i)); + } + } + public boolean opisuje (String beseda) { + for (int i = 0; i < gotoveČrke.length; i++) { + if (gotoveČrke[i] != '\000') + if (gotoveČrke[i] != beseda.charAt(i)) { + if (beseda.equals("tombak")) + System.err.println("DEBUG1"); + return false; + } + if (aČrkeNiNaPoziciji(i, beseda.charAt(i))) { + if (beseda.equals("tombak")) { + System.err.println("DEBUG2, i=" + i + ", opis: " + toString()); + } + return false; + } + } + for (Character znak : črkeVBesedi) + if (beseda.indexOf(znak) < 0) { + if (beseda.equals("tombak")) + System.err.println("DEBUG3"); + return false; + } + return true; + } + @Override + public String toString () { + String r = "gotoveČrke: " + Arrays.toString(gotoveČrke) + ", črkeVBesedi: " + črkeVBesedi + ", črkeNiVBesedi: "; + for (int i = 0; i < 256; i++) + if (črkeNiVBesedi[i]) + r += Character.valueOf((char) i); + r += ", črkeNiNaPoziciji: "; + for (int i = 0; i < gotoveČrke.length; i++) { + for (int j = 0; j < 256; j++) + if (črkeNiNaPoziciji[i][j]) + r += Character.valueOf((char) j); + if (i != gotoveČrke.length-1) + r += ','; + } + return r; + } + } + Set<String> slovar; + Set<String> možneBesede; + Set<String> besede; + String zadnjaIzbira; + String odpirač; + OpisBesede opisbesede; + int dolžina; + public Tekm_63230317 () { + zadnjaIzbira = ""; + odpirač = "odpira"; + } + @Override + public void inicializiraj(Set<String> besede) { + slovar = new TreeSet<>(besede); + možneBesede = new TreeSet<>(slovar); + dolžina = besede.iterator().next().length(); + } + class Odzivi implements Iterable<List<Character>> { + class IteratorOdzivov implements Iterator<List<Character>> { + int št; + public IteratorOdzivov () { + št = 0; + } + @Override + public List<Character> next () { + List<Character> odziv = new ArrayList<>(); + int š = št; + char možnosti[] = new char[]{'-', 'o', '+'}; + for (int i = 0; i < dolžina; i++) { + odziv.add(možnosti[š % 3]); + š /= 3; + } + št++; + return odziv; + } + @Override + public boolean hasNext () { + return št < Math.pow(dolžina, 3); + } + } + @Override + public Iterator<List<Character>> iterator () { + return new IteratorOdzivov(); + } + } + class BitiBesede implements Comparable<BitiBesede> { + String beseda; + double biti; + public BitiBesede (String beseda) { + this.beseda = beseda; + biti = 0; + int možnihodzivov = 0; + for (List<Character> odziv : new Odzivi()) { + if (!jeZdružljiv(beseda, odziv, opisbesede)) + continue; + možnihodzivov++; + } + for (List<Character> odziv : new Odzivi()) { + if (!jeZdružljiv(beseda, odziv, opisbesede)) + continue; + int možnihpougibu = 0; + for (String b: besede) { + new OpisBesede(opisbesede); + opisbesede.informacije(beseda, odziv); + if (opisbesede.opisuje(b)) + možnihpougibu++; + } + biti += (double) možnihpougibu*1/možnihodzivov; + } + } + public int compareTo (BitiBesede d) { + if (biti < d.biti) + return -1; + if (biti > d.biti) + return 1; + return 0; + } + } + @Override + public String poteza(List<Character> odziv) { + System.err.println("poteza klicana z odzivom " + odziv + ". zadnja beseda je " + zadnjaIzbira); + if (odziv == null) { + možneBesede.remove(zadnjaIzbira); + besede = new TreeSet<>(možneBesede); + opisbesede = new OpisBesede(dolžina); + return this.zadnjaIzbira = odpirač; + } + opisbesede.informacije(zadnjaIzbira, odziv); + if (vseEnako(odziv, '+')) + return null; + Set<String> odstrani = new TreeSet<>(); + for (String beseda : besede) + if (!opisbesede.opisuje(beseda)) + odstrani.add(beseda); + besede.removeAll(odstrani); + if (besede.isEmpty()) + throw new RuntimeException("množica 'besede' je prazna!"); + ArrayList<BitiBesede> rangiranje = new ArrayList<BitiBesede>(); + for (String beseda : besede) + rangiranje.add(new BitiBesede(beseda)); + Collections.sort(rangiranje); + zadnjaIzbira = rangiranje.get(rangiranje.size()-1).beseda; + System.err.println(" ... in rekel bom " + zadnjaIzbira); + return zadnjaIzbira; + } + boolean jeZdružljiv (String beseda, List<Character> odziv, OpisBesede ob) { // a lahko dobimo tak odziv na besedo (glede na trenutno stanje ugibanja) + for (int i = 0; i < dolžina; i++) { + char znak = beseda.charAt(i); + if (odziv.get(i) == '+') { + if (ob.črkeNiVBesedi[znak]) + return false; + if (ob.črkeNiNaPoziciji[i][znak]) + return false; + continue; + } + if (odziv.get(i) == '-') { + if (ob.črkeVBesedi.contains(znak)) + return false; + continue; + } + if (odziv.get(i) == 'o') { + if (ob.črkeNiVBesedi[znak]) + return false; + if (ob.gotoveČrke[i] == znak) + return false; + } + } + return true; + } + private static <T> boolean vseEnako(List<T> seznam, T element) { + return seznam.stream().allMatch(e -> e.equals(element)); + } +} |