/**********************************************************************************************************
 * Programmeerimisharjutused. LTAT.03.007
 * 2019/2020 kevadsemester
 *
 * Kodutöö. Ülesanne nr /7a/
 * Teema:
 *            Rekursiooni kasutamine ülesannetes.
 *
 * Autor: Markkus Koodi
 *
 ***********************************************************************************************************/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/***********************************************************************************
 * Programmi peaklass, mis sisaldab ka testimismeetodit.
 * Autor: Markkus Koodi.
 ***********************************************************************************/

public class Ulesanne7a {
    //7a-1
    static List<Integer> misMündid = new ArrayList<>();//Et teada saada mis münte kasutada on vaja, et summat ära maksta.

    /**
     *
     * @param raha
     * @param summa Antud täisarv.
     * @param i Antud täisarv.
     * @param j Antud täisarv.
     * @return Tagastab tõ
     */

    static boolean kasOnTäpneRaha(int[] raha, int summa, int i, int j){
        if(i == summa){return true;}
        if(j == raha.length){return false;}
        return kasOnTäpneRaha(raha, summa, raha[j] + i, j + 1) && misMündid.add(raha[j]) || kasOnTäpneRaha(raha, summa, i, j+1);
    }

    static void täpneRaha(int[] mündid, int makstavRaha) {
        misMündid.clear();
        StringBuilder taskusOn = new StringBuilder();
        StringBuilder ostuSumma = new StringBuilder();

        taskusOn.append("Taskus on mündid ");
        for (int element : mündid) taskusOn.append(element + " ");
        System.out.println(taskusOn.toString().strip());

        ostuSumma.append("Ostusumma s = " + makstavRaha + " ");
        if (kasOnTäpneRaha(mündid, makstavRaha, 0, 0)) {
            Collections.sort(misMündid);
            for (int i = 0; i < misMündid.size(); i++) {
                if (i == misMündid.size() - 1) ostuSumma.append(misMündid.get(i));
                else ostuSumma.append(misMündid.get(i) + "+");
            }
        } else ostuSumma.append("Pole võimalik tasuda!");
        System.out.println(ostuSumma.toString().strip() + "\n");
    }

    static int väljastaSõnad(String[] esimene, String[] teine){
        System.out.println("Antud sõnajärjendid: " + Arrays.asList(esimene) + " ja " + Arrays.asList(teine));
        System.out.println("Nendest koostatud laused: ");
        return sõnadeJärjestamine(esimene, teine, "", 0, 0);
    }

    static int sõnadeJärjestamine(String[] esimene, String[] teine, String s, int i, int n){
        int lauseid = 0;
        if(i > esimene.length || n > teine.length){
            return 0;
        }

        if(i == esimene.length && n == teine.length){
            s = s.strip();
            System.out.printf("|%s|\n", s);
            return 1;
        }
        if(i < esimene.length){
            lauseid += sõnadeJärjestamine(esimene,teine,s + esimene[i] + " ", i+1, n);
        }
        if(n < teine.length){
            lauseid += sõnadeJärjestamine(esimene,teine,s + teine[n] + " ", i, n + 1);
        }
        return lauseid;
    }


    public static void main(String[] args) {
        System.out.println("+".repeat(70) + "\n");

        System.out.println("Kodutöö nr 7a-1." + " ".repeat(37) + "Programmi väljund");
        System.out.println("=".repeat(69) + ":\n");
        int[] test1 = new int[]{1, 5, 10, 30, 50, 200};
        täpneRaha(test1, 137);
        int[] test2 = new int[]{2, 20, 30, 50, 100, 200};
        täpneRaha(test2, 120);
        int[] test3 = new int[]{1, 30, 50, 200};
        täpneRaha(test3, 163);
        int[] test4 = new int[]{2, 30, 50, 100};
        täpneRaha(test4,75);
        int[] test5 = new int[]{1, 5, 10, 20, 30, 50, 100};
        täpneRaha(test5, 163);
        int[] test6 = new int[]{1, 2, 20, 30, 50, 200};
        täpneRaha(test6, 101);
        int[] test7 = new int[]{1, 2, 100};
        täpneRaha(test7, 191);
        System.out.println("=".repeat(69) + ".\n");

        System.out.println("Kodutöö nr 7a-2." + " ".repeat(37) + "Programmi väljund");
        System.out.println("=".repeat(69) + ":\n");
        System.out.println("=".repeat(69) + ".\n");

        String[] essa = new String[]{"Essa", "Teine", "Kolmas"};
        String[] tessa = new String[]{"Neljas", "Viies", "Kuues"};
        System.out.println("Kokku: " + väljastaSõnad(essa, tessa) + "\n");

        String[] esimene = new String[]{"Peeter", "Paan", "Malle"};
        String[] teine = new String[]{"Karu", "Kati", "Aadu"};
        System.out.println("Kokku: " + väljastaSõnad(esimene,teine) + "\n");

        System.out.println("+".repeat(70));
        System.out.println("Markkus Koodi" + " ".repeat(35) + new java.sql.Timestamp(System.currentTimeMillis()));
    }
}