Zadanie zo skúšky PAZ1b (unister)
Created: 2008-06-19 - 17:12
Unister.paz
Zadanie
Testovaci vstup (teda obsah suboru vstupUnister.txt):
{zaciatok}
Anna Jozef
Anna Martin
Martin Karol
Martin Jozef
Martin Artur
Martin Vincent
Vincent Artur
Artur Maria
Jozef Jimmy
Jimmy Milan
Jimmy Noname
Noname Artur
Noname Johny
Noname Stewie
Adolf
{koniec}
Vyzera to asi takto:
(kedze som najprv kreslil graf a az potom som si uvedomil ze som zabudol jednemu priradit meno. Nuz to je Noname :D)
import java.io.File; import java.util.*; public class Unister { public int[][] g; public Map<String,Integer> mena; public Unister(){ mena = new HashMap<String,Integer>(); g = new int[100][100]; } public void nacitajData(String vstup){ File subor; Scanner s = new Scanner(System.in); try{ subor = new File("vstupUnister.txt"); s = new Scanner(subor); } catch(Exception f){ System.out.println("Subor neexistuje"); } String riadok = ""; while(s.hasNextLine()){ riadok = s.nextLine(); StringTokenizer tok = new StringTokenizer(riadok," ",false); int i=0; if(!mena.isEmpty()){ i = Collections.max(mena.values()); } String meno = tok.nextToken(); if(mena.isEmpty()){ mena.put(meno,i); } if(!mena.containsKey(meno)){ mena.put(meno,i+1); } if(tok.hasMoreTokens()){ String meno2 = tok.nextToken(); if(!mena.containsKey(meno2)){ mena.put(meno2,i+1); } g[mena.get(meno)][mena.get(meno2)]=1; g[mena.get(meno2)][mena.get(meno)]=1; } } } public String toString(){ String out = ""; for(int i=0;i<100;i++){ for(int j=0;j<100;j++){ out += " "+g[i][j]; } out += "\n"; } out += mena.toString(); return out; } public ArrayList<String> spolocniPriatelia(String meno1, String meno2){ int prvy = mena.get(meno1); int druhy = mena.get(meno2); HashSet<Integer> spolocniPriatelia = new HashSet<Integer>(); for(int i=0;i<100;i++){ for(int j=0;j<100;j++){ for(int k=0;k<100;k++){ if(g[i][prvy]==1 && g[i][druhy]==1 && g[i][j]==1 && g[i][k]==1) spolocniPriatelia.add(i); } } } ArrayList<String> spol = new ArrayList<String>(); for (Integer p : spolocniPriatelia) { for(Map.Entry<String, Integer> v : mena.entrySet()){ if(v.getValue()==p) spol.add(v.getKey()); } } return spol; } public ArrayList<String> zoznamPriatelov(String meno){ ArrayList<String> spol = new ArrayList<String>(); int i=-1; for(Map.Entry<String, Integer> v : mena.entrySet()){ if(v.getKey().equals(meno)) i=v.getValue(); } if(i!=-1){ for(Map.Entry<String, Integer> v : mena.entrySet()){ if(g[v.getValue()][i]==1) spol.add(v.getKey()); } } return spol; } public ArrayList<String> priateliaPriatelov(String meno){ ArrayList<String> spol = new ArrayList<String>(); ArrayList<String> priateliaTypka = new ArrayList<String>(); priateliaTypka = zoznamPriatelov(meno); for (String priateliaT : priateliaTypka) { ArrayList<String> tJehoPriatelia = new ArrayList<String>(); tJehoPriatelia = zoznamPriatelov(priateliaT); for (String priateliaPriatelov : tJehoPriatelia) { if(!spol.contains(priateliaPriatelov)){ spol.add(priateliaPriatelov); } } } //odstranit priatelov mena for(String odstran : priateliaTypka){ if(spol.contains(odstran)) spol.remove(odstran); } //moze sa stat ze je tam samotne meno tak ho odstranime if(spol.contains(meno)) spol.remove(meno); return spol; } public String najpriatelskejsi(){ LinkedList<String> najviacPriatelski = new LinkedList<String>(); for(Map.Entry<String, Integer> v : mena.entrySet()){ najviacPriatelski.add(zoznamPriatelov(v.getKey()).size()+"="+v.getKey()); } String out = ""; for(int i=0;i<5;i++){ if(!najviacPriatelski.isEmpty()){ String men = Collections.max(najviacPriatelski); StringTokenizer dajHetCisloARovnaSa = new StringTokenizer(men,"=123456789",false); out+= dajHetCisloARovnaSa.nextToken()+","; najviacPriatelski.remove(men); } } return out; } public int priatelskaVzdialenost(String meno1, String meno2){ //najprv overime ci ma meno2 susedov if(zoznamPriatelov(meno2).isEmpty()) return -1; //prehladavanie do sirky Queue<String> fifo = new PriorityQueue<String>(); fifo.add(meno1); String s; Map<String,Boolean> preskumane = new TreeMap<String,Boolean>(); Map<String,Integer> vzdialenosti = new TreeMap<String,Integer>(); Map<String,String> predchodcovia = new TreeMap<String,String>(); for(Map.Entry<String, Integer> v : mena.entrySet()){ preskumane.put(v.getKey(), false); } for(Map.Entry<String, Integer> v : mena.entrySet()){ vzdialenosti.put(v.getKey(), 0); } for(Map.Entry<String, Integer> v : mena.entrySet()){ predchodcovia.put(v.getKey(), meno1); } int vzd=1; while(!fifo.isEmpty()){ s = fifo.poll(); preskumane.put(s, true); ArrayList<String> susedia = new ArrayList<String>(zoznamPriatelov(s)); if(susedia.isEmpty()) return -1; for (String k : susedia) { if(!preskumane.get(k)){ preskumane.put(k,true); predchodcovia.put(k, s); vzdialenosti.put(k, vzd+vzdialenosti.get(predchodcovia.get(k))); fifo.add(k); } if(k.equals(meno2)) return vzdialenosti.get(k); } } return -2; } private ArrayList<String> zoznamNiePriatelov(String meno){ ArrayList<String> zoznamLudi = new ArrayList<String>(); for(Map.Entry<String, Integer> v : mena.entrySet()){ zoznamLudi.add(v.getKey()); } for (String z : zoznamPriatelov(meno)) { if(zoznamLudi.contains(z)) zoznamLudi.remove(z); } if(zoznamLudi.contains(meno)) zoznamLudi.remove(meno); return zoznamLudi; } public ArrayList<String> uzIchPoznas(String meno){ //predpokladame, ze mame metodu ktora ukaze iba tych co su z jeho univerzity a teda: //zoznam bude mat najviac 5 hodnot //aspon 1 tam musia byt s pVzd: 2 3 4 //nesmu to byt jeho priatelia... takze mozu to byt aj ti ktorych nepozna ArrayList<String> uzIchPoznas = new ArrayList<String>(); ArrayList<String> zoznamLudiKtorychNepozna = zoznamNiePriatelov(meno); boolean dvojkaJe=false; boolean trojkaJe=false; boolean stvorkaJe=false; for (Iterator iter = zoznamLudiKtorychNepozna.iterator(); iter.hasNext();) { String element = (String) iter.next(); if(priatelskaVzdialenost(meno, element)==2 && !dvojkaJe){ uzIchPoznas.add(element); iter.remove(); dvojkaJe = true; } if(priatelskaVzdialenost(meno, element)==3 && !trojkaJe){ uzIchPoznas.add(element); iter.remove(); trojkaJe = true; } if(priatelskaVzdialenost(meno, element)==4 && !stvorkaJe){ uzIchPoznas.add(element); iter.remove(); stvorkaJe = true; } } for (String clovek : zoznamLudiKtorychNepozna) { if(uzIchPoznas.size()<5){ //ak sa tam este zmestia nejaki ludia pridame kvazi nahodnych ludi uzIchPoznas.add(clovek); } } return uzIchPoznas; } public static void main(String[] args) { Unister unister = new Unister(); unister.nacitajData("vstup.txt"); System.out.println("Spolocni priatelia Vincenta a Marie: "+ unister.spolocniPriatelia("Vincent", "Maria")); System.out.println("Zoznam priatelov Jozefa: "+unister.zoznamPriatelov("Jozef")); System.out.println("Priatela Anninych priatelov: " +unister.priateliaPriatelov("Anna")); System.out.println("Najpriatelskejsi uzivatelia: "+unister.najpriatelskejsi()); System.out.println("Priatelska vzdialenost medzi Jozefom a Johnym:"+unister.priatelskaVzdialenost("Jozef", "Johny")); System.out.println("Uz ich poznas? Pre uzivatela Jozef:" +unister.uzIchPoznas("Jozef")); } } ================================ Testovaci vystup: Spolocni priatelia Vincenta a Marie: [Artur] Zoznam priatelov Jozefa: [Anna, Martin, Jimmy] Priatela Anninych priatelov: [Artur, Karol, Vincent, Jimmy] Najpriatelskejsi uzivatelia: Martin,Noname,Artur,Jozef,Jimmy, Priatelska vzdialenost medzi Jozefom a Johnym:3 Uz ich poznas? Pre uzivatela Jozef:[Milan, Stewie, Artur, Johny, Karol]
Nacitanie zo vstupu funguje jednoducho cez Scanner, nacitava cele riadky, ak riadok obsahuje dve mena, tak vytvori v grafe (zaklad je reprezentovany maticou susednosti g[100][100]) vztah pre dane mena. Samotne mena su mapovane na cisla, ktore znamenaju poradie v matici susednosti. Poradie je urcene tak, ze sa urci maximum z hodnot, ktore uz boli priradene a zvysi sa o 1 (popripade 2). Graf je mozne vypisat pomocou metody toString().
Spolocni priatelia su zistovani pre konkretne mena a teda prechadzam maticu susednosti a zistujem, ci obaja maju priradeneho nejakeho priatela s rovnakym indexom. Ak ano zistim jeho meno a ulozim do zoznamu.
Priatelia priatelov pouziva metodu zoznamPriatelov pre konkretne mena. Teda najprv si zistim pre dane meno jeho priatelov, potom pre kazdych z tychto priatelov zistujem ich priatelov a ukladam do zoznamu. Zo zoznamu potom odstranim priatelov toho mena, ktore bolo na vstupe + to meno (lebo sa tam moze vyskytnut).Najpriatelskejsi su ti, ktori maju najviac priatelov. Opat pouzijem metodu zoznamPriatelov, ktora vracia zoznam priatelov pre dane meno. Zistujem, ktory zoznam je najvacsi a to meno potom hodim do zoznamu (aj s hodnotou velkosti daneho zoznamu pred menom). Potom vyberam maximum z danej mnoziny a odstranujem tie indexy, aby vratilo len konkretne mena bez cisel.
Priatelska vzdialenost sa da riesit vselijakymi sposobmi, ja som si vybral prehladavanie do sirky a zistovanie najkratsej vzdialenosti od daneho vrchola k ostatnym. Teda je tam samostatna mapa na vzdialenosti, predchodcov a preskumane vrcholy. Pri prehladavani do sirky urcujem pre kazdy vrchol minimalnu vzdialenost od vstupneho vrchola (mena) a tiez jeho predchodcu. Ked dorazi po vrchol, ktory sme hladali, tak.. bingo vrati hodnotu najkratsej cesty.
Uz ich poznas? je tiez len o aplikovani predchodzich algoritmov. Vytvoril som si zvlast metodu, ktora vrati zoznam ludi, ktorych dane meno nepozna. Pre kazdeho z nich potom urcujem ci sa tam nachadza aspon jeden s priatelskou vzdialenostou 2,3,4 -- toto sa urcuje prioritne a ked je to uz urcene, tak sa potom zvysny zoznam doplni nejakymi ostatnymi menami, ktore este nepozna.