Problema printer

marcoBeretta · 20 Agosto 2014, 8:22pm

Sto risolvendo il problema printer… ho sottoposto questo codice, ma totalizza solo la metà dei punti, per gli altri dà output errato…

Il codice è questo:

#include <string>
#include <deque>
#include <stdio.h>
#include <stdlib.h>

#define N (int)'z'-(int)'a'+1;
#define A (int)'a';

using namespace std;

class Nodo{
	public:
		char c;
		int col;
		deque<class Nodo*> succ;
};

// lunghezza della stringa più lunga
int max_lenght = 0;

// lista dei caratteri da stampare su file
deque<char> out;


// funzione che cerca una stringa con lunghezza max_lenght e setta i colori a 2 (la stringa formata da quei caratteri sarà l'ultima da stampare)
int search(class Nodo* n, int prof){
	
	if(prof == max_lenght){
		n->col = 2;
		return 2;
	}
	else{
		for(int i=0; i<n->succ.size(); i++)
			if(search(n->succ[i], prof+1) == 2){
				n->col = 2;
				return 2;
			}
		
		return 0;
	}
}

// visita di un nodo
void visit(class Nodo* n){
	// stampo il carattere del nodo
	out.push_back(n->c);
	// se è un nodo foglio stampo P
	if(n->succ.size() == 0)
		out.push_back('P');
	// visito tutti i sottonodi
	for(int i=0; i<n->succ.size(); i++)
		visit(n->succ[i]);
	// stampo - per togliere il carattere
	out.push_back('-');
}

// visita per il ramo dell'albero in cui c'è la stringa da lasciare per ultima
void visit2(class Nodo* n){
	
	out.push_back(n->c);
	if(n->succ.size() == 0)
		out.push_back('P');

	int i,index = -1;
	for(int i=0; i<n->succ.size(); i++)
		if(n->succ[i]->col == 2)
			index = i;
		else
			visit(n->succ[i]);
	
	if(n->col != 2)
		out.push_back('-');
	
	if(index != -1)
		visit2(n->succ[index]);
}

// costruzione dell'albero
void insert(class Nodo* n, string s, int last_i){
	
	if(s.size() == last_i+1)
		return;
	
	if(n->succ.size() == 0){
		Nodo* e;
		e = new Nodo();
		last_i++;
		e->c = s[last_i];
		e->col = 0;
		n->succ.push_back(e);
		insert(n->succ[0], s, last_i);
	}
	else{
		last_i++;
		int flag = 0;
		int j;
		for(j=0; j<n->succ.size(); j++)
			if(n->succ[j]->c == s[last_i]){
				flag = 1;
				break;
			}
		if(flag)
			insert(n->succ[j], s, last_i);
		else{
			Nodo* e;
			e = new Nodo();
			e->c = s[last_i];
			e->col = 0;
			n->succ.push_back(e);
			insert(n->succ[n->succ.size()-1], s, last_i);
		}
	}
	
}

main(){
	FILE *pF = fopen("input.txt", "r");
	int n;
	fscanf(pF, "%d", &n);
	int i;
	char s2[21];
	string s;
	deque<class Nodo*> first;
	
	for(i=0; i<n; i++){
		fscanf(pF, "\n%s", s2);
		s = s2;
		if(s.size() > max_lenght)
			max_lenght = s.size();
			
		if(first.size() == 0){
			Nodo* n;
			n = new Nodo();
			n->c = s[0];
			n->col = 0;
			first.push_back(n);
			insert(first[0], s, 0);
		}
		else{
			int flag = 0;
			int j;
			for(j=0; j<first.size(); j++)
				if(first[j]->c == s[0]){
					flag = 1;
					break;
				}
			if(flag)
				insert(first[j], s, 0);
			else{
				Nodo* n;
				n = new Nodo();
				n->c = s[0];
				n->col = 0;
				first.push_back(n);
				insert(first[first.size()-1], s, 0);
			}
		}
	}
	fclose(pF);

	for(i=0; i<first.size(); i++)
		if(search(first[i], 1) == 2)
			break;
	
	int index = i;
	
	for(i=0; i<index; i++)
		visit(first[i]);

	for(i=index+1; i<first.size(); i++)
		visit(first[i]);
		
	visit2(first[index]);
	
	pF = fopen("output.txt", "w");
	fprintf(pF, "%d", out.size());
	for(i=0; i<out.size(); i++)
		fprintf(pF, "\n%c", out[i]);
	fclose(pF);
}

( http://pastebin.com/s9jn2PpZ )

In pratica costruisco un albero con tutte le parole, identifico il ramo dove c’è la parola più lunga, visito tutti i rami tranne quello e poi visito quel ramo lasciando la parola più lunga per ultima. Qualcuno può dirmi dove sbaglio?

VashTheStampede · 20 Agosto 2014, 8:44pm

Premetto che il tuo codice non l’ho letto (mi fido sul fatto che hai implementato correttamente l’albero).

Premetto anche che i TRIE li ho letti l’altro giorno per puro caso e non so implementarli.

Ma facendomi un disegnino su carta forse ho capito dove sbagli.

Come hai capito, devi “stampare” per ultima la parola più lunga.

Ma questo ragionamento lo applichi anche per le precedenti N-1 parole?

Non ne sono sicuro eh, (nemmeno io l’ho risolto/provato quel problema) ma ad intuito, tra due o più sotto-alberi, devi scegliere prima quello che possiede meno nodi.

Degiac · 20 Agosto 2014, 9:00pm

Non consideri il caso in cui l’ultima lettera di una parola da stampare non si trova in una foglia dell’albero.
ES:
ama

amare

amaretto

marcoBeretta · 20 Agosto 2014, 9:02pm

Per le parole prima l’ordine di stampa corrisponde all’ordine di inserimento nell’albero, quindi non è detto che vengano stampate prima le parole più corte… ma ciò è necessario? Prima o poi tutte le parole devono essere cancellate (interamente o in parte), quindi l’ordine non è indifferente?

marcoBeretta · 20 Agosto 2014, 9:06pm

Non consideri il caso in cui l'ultima lettera di una parola da stampare non si trova in una foglia dell'albero.
ES:
ama
amare
amaretto
Degiac

Quindi dovrei mettere un flag per ogni lettera che mi dice se quella lettera è la fine di una parola, giusto?

Degiac · 20 Agosto 2014, 9:08pm

Non consideri il caso in cui l'ultima lettera di una parola da stampare non si trova in una foglia dell'albero.
ES:
ama
amare
amaretto
Degiac
Quindi dovrei mettere un flag per ogni lettera che mi dice se quella lettera è la fine di una parola, giusto?
marcoBeretta

Esatto

mark03 · 20 Agosto 2014, 9:23pm

Per le parole prima l'ordine di stampa corrisponde all'ordine di inserimento nell'albero, quindi non è detto che vengano stampate prima le parole più corte... ma ciò è necessario? Prima o poi tutte le parole devono essere cancellate (interamente o in parte), quindi l'ordine non è indifferente?
marcoBeretta

L'importante è lasciare per ultima quella più lunga

VashTheStampede · 20 Agosto 2014, 9:26pm

Per le parole prima l'ordine di stampa corrisponde all'ordine di inserimento nell'albero, quindi non è detto che vengano stampate prima le parole più corte... ma ciò è necessario? Prima o poi tutte le parole devono essere cancellate (interamente o in parte), quindi l'ordine non è indifferente?
marcoBeretta
L'importante è lasciare per ultima quella più lunga
mark03

Si ho fatto confusione scusate! =P

mark03 · 20 Agosto 2014, 9:36pm

Quindi dovrei mettere un flag per ogni lettera che mi dice se quella lettera è la fine di una parola, giusto?
marcoBeretta

Così facendo io ho fatto 100/100. Comunque la tua implementazione è un po' complicata, si potrebbe fare un po' più semplicemente ;)

marcoBeretta · 21 Agosto 2014, 8:32am

Non consideri il caso in cui l'ultima lettera di una parola da stampare non si trova in una foglia dell'albero.
ES:
ama
amare
amaretto
Degiac
Quindi dovrei mettere un flag per ogni lettera che mi dice se quella lettera è la fine di una parola, giusto?
marcoBeretta
Esatto
Degiac

Risolto grazie :)

marcoBeretta · 21 Agosto 2014, 8:33am

Quindi dovrei mettere un flag per ogni lettera che mi dice se quella lettera è la fine di una parola, giusto?
marcoBeretta
Così facendo io ho fatto 100/100. Comunque la tua implementazione è un po' complicata, si potrebbe fare un po' più semplicemente ;)
mark03

Sì hai ragione... si potrebbe fare di meglio!

EmanueleRossi · 21 Agosto 2014, 8:40am

Qui c’è il mio codice. Io applico tutte le idee che avete detto, quindi trie che stampa l’ultima parola alla fine e stampa anche parole che non finiscono nelle foglie ma faccio 40/100. Idee?

#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <utility>
#include <stdio.h>
#include <queue>
#include <fstream>
#include <functional>
#include <cstdlib>
#include <map>
#include <set>
#include <math.h>
#include <string.h>
#include <stdlib.h> 

using namespace std;

typedef pair<int, int> ii ;
typedef vector< ii >   vii ;
typedef vector<int> vi ;
typedef vector<vi> vvi; 
typedef pair< int, string > is;

#define pb push_back 
#define MAX_N 2000005
 
int n, printable[MAX_N];
int last[MAX_N];
vector< ii > g[MAX_N];
string sol,maxim;
vector< string > sorted;

bool cmp(const string &a, const string &b ){
    return a.length()>b.length();
}

void dfs(int n){
    
    for(int i=0;i<g[n].size();i++){
        if(!last[g[n][i].first]){
            sol.pb(char(g[n][i].second+'a'));
            dfs(g[n][i].first);
        }
    }
    for(int i=0;i<g[n].size();i++){
        if(last[g[n][i].first]){
            sol.pb(char(g[n][i].second+'a'));
            dfs(g[n][i].first);
        }
    }    
    
    for(int i=0;i<printable[n];i++)
        sol.pb('P');
        
    sol.pb('-');
}

void dfsLast(int n, int pos){
    last[n] = 1;
    if(pos == maxim.size())
        return;
    for(int i=0;i<g[n].size();i++){
        if(char(g[n][i].second+'a') == maxim[pos] ){
            dfsLast(g[n][i].first,pos+1);
            break;
        }
    }
}

int main() {
    
    #ifdef EVAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    scanf("%d",&n);
    int maxNode = 0;
    
    for(int i=0;i<n;i++){
        char t[30]; scanf("%s",t);//cin>>t;
        string temp = t;
        if(temp.length() > maxim.length())
            maxim = temp;
        sorted.pb(temp);
    }
    
    //sort(sorted.begin(), sorted.end(), cmp);
    
    for(int i=0;i<n;i++){
        int nodeCurr = 0;
        for(int j=0;j<sorted[i].length();j++){
            int ind = -1 ;
            for(int k=0;k<g[nodeCurr].size();k++)
                if(g[nodeCurr][k].second == sorted[i][j]-'a'){
                    ind = k;
                    break;
                }
            if(ind == -1){
                g[nodeCurr].push_back(make_pair(++maxNode, sorted[i][j]-'a'));
                ind = g[nodeCurr].size()-1;
            }
            if(j == sorted[i].length() - 1)
                printable[maxNode]++;
            
            nodeCurr = g[nodeCurr][ind].first;
            
        }
    }
    /*for(int i=0;i<maxNode;i++){
        cout<<i<<": ";
        for(int j=0;j<g[i].size();j++)
            cout<<g[i][j].first<<" "<<char(g[i][j].second+'a')<<endl;
    }*/
    dfsLast(0,0);
    dfs(0);
    
    int k = sol.length()-1;
    while(sol[k] == '-')
        k--;
    printf("%d\n",k+1);
    for(int i=0;i<=k;i++)
        printf("%c\n",sol[i]);
     
    return 0;
}

//7 -1 2 -1 5 -2 3 -3 1 1 -1 -2 -1 -3 -4

( http://pastebin.com/vmHXpm4g )

Lawliet · 21 Agosto 2014, 8:55am

Qui c'è il mio codice. Io applico tutte le idee che avete detto, quindi trie che stampa l'ultima parola alla fine e stampa anche parole che non finiscono nelle foglie ma faccio 40/100. Idee?
http://pastebin.com/vmHXpm4g
EmanueleRossi

Come implementazione è un po' contorta. In realtà è sufficiente salvarsi l'indice della parola più lunga ed inserirla nel trie alla fine in un modo un po' diverso. Io l'ho fatto mettendo ogni sottoalbero che comprendeva quella parola sempre più a destra, quindi come ultima scelta per ogni nodo. Poi il resto è un normale trie.

mark03 · 21 Agosto 2014, 9:47am

Qui c'è il mio codice. Io applico tutte le idee che avete detto, quindi trie che stampa l'ultima parola alla fine e stampa anche parole che non finiscono nelle foglie ma faccio 40/100. Idee?
http://pastebin.com/vmHXpm4g
EmanueleRossi

Come implementazione è un po' contorta. In realtà è sufficiente salvarsi l'indice della parola più lunga ed inserirla nel trie alla fine in un modo un po' diverso. Io l'ho fatto mettendo ogni sottoalbero che comprendeva quella parola sempre più a destra, quindi come ultima scelta per ogni nodo. Poi il resto è un normale trie.
Lawliet

Oppure "colorare" la parola dopo, con una dfs

Lawliet · 21 Agosto 2014, 10:03am

Oppure "colorare" la parola dopo, con una dfs (vedi qui)
mark03

Anche è vero, non ci avevo pensato. Dovrebbe essere più veloce la tua soluzione.

Degiac · 21 Agosto 2014, 11:25am

Io mi salvo in ogni nodo la lunghezza della parola più lunga che inizia da lì, poi faccio nth_element sui figli in modo da tenere il sottoalbero con la parola più lunga per ultimo

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int contaOp = 0;

struct trie
{
    bool print;
    char c;
    vector<trie> sons;
    int mWord;
};

bool operator<(const trie &a, const trie&b)
{
    return a.mWord < b.mWord;
}

void addWord(string w, trie &node)
{
    if(w.empty())
    {
        node.print = true;
        return;
    }

    bool found = false;
    int i = 0;
    for(i = 0; i < (int)node.sons.size() && !found; i++)
	if(node.sons[i].c == w[0]) found = true;

    if(!found)
    {
        trie newNode;
        newNode.c = w[0];
        newNode.mWord = 0;
        newNode.print = false;
        node.sons.push_back(newNode);
    }
    else i--;

    node.sons[i].mWord = max(node.sons[i].mWord, (int)w.length());

    addWord(w.substr(1, string::npos), node.sons[i]);
}

void printSol(int &N, trie &nodo, ofstream &out)
{
    if(nodo.print)
    {
	N--;
	out << "P\n";
	contaOp++;
    }

    if(nodo.sons.empty())
	return;

    nth_element(nodo.sons.begin(), nodo.sons.end()-1, nodo.sons.end());

    int i = 0;

    while(i < nodo.sons.size())
    {
        out << nodo.sons[i].c << "\n";
        contaOp++;
        printSol(N, nodo.sons[i], out);
        if(N > 0) { out << "-\n"; contaOp++; }
        i++;
    }
}


int main()
{
    ifstream in("input.txt");
    ofstream out("output.txt");

    int N;
    string w;
    trie triet;
    triet.c = '0';
    triet.print = false;
    in >> N;

    for(int i = 0; i < N; i++)
    {
        in >> w;
        addWord(w, triet);
    }

    out << "                                             \n";

    printSol(N, triet, out);

    out.seekp(ios_base::beg);

    out << contaOp;



    return 0;
}

( http://pastebin.com/b959SXAx )

Lawliet · 21 Agosto 2014, 11:56am

Bè dato che lo stiamo postando tutti, il mio codice è questo.

mark03 · 21 Agosto 2014, 12:06pm

C’è comunque una soluzione alternativa più lenta ma che porta comunque ai 100/100. Basta farsi un vector di string e ordinarlo con una funzione compare “modificata” in modo che resti per ultima la parola più lunga

EmanueleRossi · 21 Agosto 2014, 12:24pm

Lo so che il mio codice è molto contorto, però io faccio proprio cosi, costruisco il trie, poi coloro nel trie la parola piu lunga, e dopo la stampo per ultima…però bho…proverò a reimplementare…