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));
}
}
