Informatika gyűjtemény

Egy szinttel feljebb szamjegy.java

2004050607080910

<<  3. óra  >>

<<  Számjegyek kitalálása  >>

NézetNyomtat

szamjegy.java (Vissza)
Az alábbi letöltési lehetőségek közül választhatsz: (segítség)
Karakterkódolás:
Sortörés:
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: utf-8
Méret: 9 KB
/*
 * Az http://prog.berzsenyi.hu:8080/prog/View/szakkor/bdg/0809/03ora/szamjegy oldalon található feladatot oldja meg a program.
 * A szamjegy.be fájlból beolvasunk hasonló sorokat: USA+USSR=PEACE
 * A szamjegy.ki fájlba írunk hasonló sorokat: 932+9338=10270
 * 
 * Algoritmus röviden:
 *  1.  beolvassuk a sorokat a bemeneti fájlból, melyekből Problem objektumokat csinálunk
 *  2.  values = [0,9] -> ezt permutáljuk, majd megpróbáljuk a problémákra ezeket ráilleszteni:
 *      Ha az adott problémában n különböző számjegy van, akkor a values első n értékét illesztjük rá a számjegyekre.
 *      Csak akkor történik illesztés az adott problémára, ha a permutáció az előzőhöz képest az első n értéken változtatott (különben nincs értelme, hiszen ugyanazokat a számokat kapnánk.
 *  3.  Egy adott illesztés után ellenőrizzük, hogy az összeg valóban helyes (matematikailag), hiszen ha nem, akkor a kövi permutációt keressük
 *      Ennek egyszerű és gyors megvalósítása, hogy úgy adjuk össze a számokat, ahogy mi is tennénk (először az egyes helyiértéken álló -> tizes helyiérték stb.)
 *      Ha valamelyik helyiérték nem stimmel (nem egyenlő a bal és jobb oldalon), akkor tovább lépünk
 *  4.  A jó megoldásokat Solution objektumként egy tömbben tároljuk, majd a végén ezt iterálva, kiíjuk a jó megoldásokat.
 * 
 * Készítette: Kriván Bálint
 */

package hu.krivan.szakkor.szamjegy;

import java.util.*;
import java.io.*;

class Common {
    public static int[] values;
}

/**
 * Egy megoldandó problémát képviselő objektum.
 * 
 * @author balint
 */
class Problem {
    /*
     * itt találhatóak, az egyes számok, és azok számjegyeinek indexei (amik a values[]-ra mutatnak)
     * tehát, egy szám adott helyiértékén szereplő számjegy = values[ numbers[szam][helyiertek] ]
     */
    public ArrayList<ArrayList<Integer>> numbers = new ArrayList<ArrayList<Integer>>();
    private int maxIdx = 0;

    // ez tárolja az egyenlőségjel "pozícióját" -> innen tudjuk, hogy ha nézzük a számokat, akkor melyiktől kezdve vannak a számok az egyenlőség jobb oldalán
    public int eqIndex = 0;
    public int id = -1;

    private int getIdxFromChar(char a) {
        return (int) a - 65;
    }

    public Problem(String s, int idx) {
        id = idx;
        
        String[] eqSides = s.split("=");
        if (eqSides.length != 2) {
            return;
        }
        String[] numbers1 = eqSides[0].split("\\+");
        eqIndex = numbers1.length; // ahol az egyenlőségjel van.
        String[] numbers2 = eqSides[1].split("\\+");
        String[] numbers_ = new String[numbers1.length + numbers2.length];

        for (int i = 0; i < numbers1.length; i++) {
            numbers_[i] = numbers1[i];
        }
        for (int i = 0; i < numbers2.length; i++) {
            numbers_[i + numbers1.length] = numbers2[i];
        }

        // itt tároljuk ideiglenesen azt, hogy az adott karaktert hol találtuk meg először (ez ahhoz kell, hogy minden karaktert egy 0-9-ig eső számmal jellemezhessünk)
        int[] indicies = new int[26];
        for (int i = 0; i < 26; i++) {
            indicies[i] = -1;
        }

        // végrehajtunk egy karakter-analízist, hogy a karakterekből számokat tudjunk csinálni.
        int c = 0;

        for (int i = 0; i < numbers_.length; i++) {
            ArrayList<Integer> number = new ArrayList<Integer>(); //ez egy szám
            for (int a = 0; a < numbers_[i].length(); a++) {
                // ha még nem volt ilyen karakter, akkor kapjon egy számot (0-9) 
                if (indicies[getIdxFromChar(numbers_[i].charAt(a))] == -1) {
                    indicies[getIdxFromChar(numbers_[i].charAt(a))] = c++;
                }
                number.add(indicies[getIdxFromChar(numbers_[i].charAt(a))]);
            }
            numbers.add(number); // a számot hozzáadjuk a számokhoz.
        }
        
        /*
         * Ebben a pillanatban a numbers[][] tárolja a számokat és azok "számjegyeit", de az adott számjegy, csak egy index
         * ami helyére behelyettesítjük a permutációnak megfelelő jelenlegi értéket.
         */

        maxIdx = c - 1; // eltároljuk, hogy hány számot használunk 0-9-ből, hiszen a permutáció során, ezekkel nem foglalkozunk.
    }

    /**
     * Megvizsgáljuk, hogy a problémára az adott permutáció ad-e megoldást.
     * 
     * @return jó-e az adott permutáció
     */
    public boolean isGoodPermutation() {
        // számjegyeken végig megyünk. (hátulról)
        int X = 0; // bal oldal
        int Y = 0; // jobb oldal
        boolean endOfNumbers = true;
        for (int i = 0; i < 12; i++) { // 12 = max. számjegyek, végig pörgetjük a számjegyeket.
            for (int j = 0; j < numbers.size(); j++) { // vegyük sorra az összeadandókat.
                if (Common.values[numbers.get(j).get(0)] == 0) { // ha valamelyik szám 0-val kezdődik, az felejtős
                    return false;
                }
                if (numbers.get(j).size() > i) {
                    // csak akkor adjuk hozzá az adott szám számjegyét, ha létezik ;)
                    endOfNumbers = false; // ezzel vizsgáljuk, hogy történt-e összeadás, ha ez true lenne, akkor a végén kilépünk, mert az összeadás végére értünk.
                    if (j < eqIndex) { // ha az egyenlőség bal oldalán van
                        X += Common.values[numbers.get(j).get(numbers.get(j).size() - i - 1)];
                    } else { // ha a jobbon.
                        Y += Common.values[numbers.get(j).get(numbers.get(j).size() - i - 1)];
                    }
                }
            }
            if (X % 10 != Y % 10) { // ha az adott helyiérték nem stimmel, akkor nem küzdünk tovább -> kilépünk
                return false;
            }
            
            // maradékok kiszámolása
            X /= 10;
            Y /= 10;
            
            if (endOfNumbers) { // ha nem volt mit összeadni, akkor végére értünk és minden rendben.
                break;
            }
        }
        return true;
    }

    /**
     * Ellenőrizzük, hogy kell-e a permutációt ellenőrizni, hogy megoldás-e. Nyílván, ha a permutáció a számunkra
     * érdekes helyen nem változott, akkor fölöslegesen ne szenvedjünk.
     * 
     * @param j melyik az a legkisebb index, amin a permutáció változtatott
     * @return kell-e az adott permutációt ellenőriztetni
     */
    public boolean shouldCheck(int j) {
        return j <= maxIdx;
    }
}

/**
 * Egy megoldást képviselő objektum
 * 
 * @author balint
 */
class Solution {

    ArrayList<ArrayList<Integer>> numbers;
    int[] values;
    int eqIndex;

    /**
     * Az adott probléma megoldását hozzuk létre.
     * 
     * @param p melyik problémára van megoldásunk.
     */
    public Solution(Problem p) {
        numbers = p.numbers;
        eqIndex = p.eqIndex;
        this.values = Common.values.clone(); // klónozzuk, mert ez folyamatosan változik.
    }

    /**
     * Kíírjuk a megfelelő megoldást.
     */
    public void print( PrintWriter out ) throws IOException {
        for (int i = 0; i < numbers.size(); i++) {
            if (i == eqIndex) {
                out.print("=");
            } else if (i != 0) {
                out.print("+");
            }
            for (int j = 0; j < numbers.get(i).size(); j++) {
                // itt történik a "lefordítás"
                out.print(values[numbers.get(i).get(j)]);
            }
        }
        out.println();
    }
}

public class Program {

    private ArrayList<Problem> problems;
    private int lastSwappedIdx = -1;
    
    public Program() {
        //StreamReader r = new StreamReader("szamjegy.be");
        BufferedReader in = null;
        try {
            in = new BufferedReader(new FileReader("szamjegy.be"));
            problems = new ArrayList<Problem>();
            String str;
            int id = 0;
            // beolvassuk a sorokat
            while ((str = in.readLine()) != null) {
                // létrehozunk egy problémát, az adott sorhoz (és egy ID-t kap)
                problems.add(new Problem(str, id++));
            }
        } catch (IOException ex) {
            ex.printStackTrace();
        } finally {
            try {
                in.close();
            } catch (IOException ex) {
                ex.printStackTrace();
            }
        }
    }

    public static void main(String[] args) {
        Program p = new Program();
        p.solveProblems();
    }

    public void solveProblems() {
        // inicializáljuk a permutáció 1. elemét. [0,9]
        Common.values = new int[10];
        for (int i = 0; i < 10; i++) {
            Common.values[i] = i;
        }

        Solution[] solutions = new Solution[problems.size()];

        Problem p;
        do {
            // az adott permutációt mindegyik problémára lefuttatjuk.
            for (int i = 0; i < problems.size(); i++) {
                p = problems.get(i);
                if (p.shouldCheck(lastSwappedIdx)) { // ha van értelme ellenőrizni.
                    if (p.isGoodPermutation()) { // ha megoldás
                        solutions[p.id] = new Solution(p); // eltároljuk a megoldást.
                        problems.remove( p ); // megoldva, kivesszük a listából.
                        if (problems.size() == 0) {
                            break; // ha elfogytak a megoldandó problémák, akkor köszönjünk el.
                        }
                    }
                }
            }

        } while (hasNextPermutation()); // követekező permutációt nézzük.

        // kiírjuk a megoldásokat
        PrintWriter out = null;
        try {
            out = new PrintWriter(new FileWriter("szamjegy.ki"));
            for (int i = 0; i < solutions.length; i++) {
                solutions[i].print( out );
            }
        } catch (IOException ex) {
            ex.printStackTrace();
        } finally {
            out.close();
        }
    }

    /**
     * Permutáció generáló algoritmus
     * 
     * @return van-e újabb permutáció
     */
    private boolean hasNextPermutation() {
        int j, m, k;
        int n = 10; // 10 elemű permutáció: [0,9]

        j = n - 2; // hátulról kolbászolunk előre (azért -2, mert -1 lenne az utolsó elem, de nekünk az utolsó előtti kell.)
        while (Common.values[j] >= Common.values[j + 1]) {
            j--;
            if (j == -1) {
                break; // különben exception.
            }
        }
        if (j == -1) {
            return false; // nem találtunk cserélni valót.
        }
        m = n - 1; // megint hátulról kolbászolunk előre és megkeressük az első olyan elemet, amely nagyobb j.-nél
        while (Common.values[j] >= Common.values[m]) {
            m--;
            if (m == -1) {
                break; // lehet ilyen?
            }
        }

        lastSwappedIdx = j; // elmentjük, hogy melyik a legkisebb indexű elem, amin változtattunk.
        swap(j, m); // kicseréljük a két fekete bárányt.

        k = j + 1;
        m = n - 1;

        // (j+1; n) intervallumban minden elemet felcserélünk
        while (k < m) {
            swap(k++, m--);
        }
        
        return true;
    }

    private void swap(int j, int m) {
        int tmp = Common.values[j];
        Common.values[j] = Common.values[m];
        Common.values[m] = tmp;
    }
}
(Vissza)