1. Hello there!

    I am posting this here because my stack overflow account was recently banned (don't ask why) and I need help with a Java question. I came across this problem while doing the CCC junior contest, and was unable to finish it within the time. As far as I know, everything is correct. However, when ran with a test case, my code outputs nothing. Bear with me that I am quite stupid and may have made a simple error.

    Code:
    package javaapplication62;
    
    import java.util.*;
    
    public class RuleOfThree_NoEdge {
    
        static String[][] mRules = new String[3][2];
        static int iStep;
        static String sStart, sEnd;
    
        static LinkedList<String> oAllStrings = new LinkedList<String>();
        static LinkedList<int[]>[] aSteps;
    
        public static void main(String args[]) {
            Scanner oIn = new Scanner(System.in);
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 2; j++) {
                    mRules[i][j] = oIn.next();
                }
            }
            iStep = oIn.nextInt();
            sStart = oIn.next();
            sEnd = oIn.next();
    
            aSteps = new LinkedList[iStep + 1];
            for (int i = 0; i < iStep + 1; i++) {
                aSteps[i] = new LinkedList<int[]>();
            }
    
            buildSteps();
    
            // debug info
            // printSteps();
            LinkedList<int[]> oResults = new LinkedList<int[]>();
            int iCurr = oAllStrings.indexOf(sEnd);
            for (int i = iStep; i > -1; i--) {
                for (int j = 0; j < aSteps[i].size(); j++) {
                    if (iCurr == aSteps[i].get(j)[2]) {
                        oResults.add(aSteps[i].get(j));
                        iCurr = aSteps[i].get(j)[3];
                    }
                }
            }
            for (int i = oResults.size() - 2; i > -1; i--) {
                System.out.println((oResults.get(i)[0] + 1) + " " + (oResults.get(i)[1] + 1) + " " + oAllStrings.get(oResults.get(i)[2]));
            }
        }
    
        private static void buildSteps() {
            oAllStrings.add(sStart);
    
            int[] aNode = new int[4];
            aNode[2] = oAllStrings.indexOf(sStart);
            aSteps[0].add(aNode);
    
            for (int i = 0; i < iStep; i++) {
                for (int j = 0; j < aSteps[i].size(); j++) {
                    addSteps(aSteps[i].get(j)[2], i + 1);
                }
            }
        }
    
        private static void addSteps(int iInd, int iStp) {
            String sTmp = oAllStrings.get(iInd);
            String sNew, sSub;
            int iNew;
            int[] aNode;
    
            for (int i = 0; i < sTmp.length(); i++) {
                sSub = sTmp.substring(i);
                for (int j = 0; j < 3; j++) {
                    if (sSub.startsWith(mRules[j][0])) {
                        sNew = replace(sTmp, i, mRules[j][0], mRules[j][1]);
    
                        if (!oAllStrings.contains(sNew)) {
                            oAllStrings.add(sNew);
                        }
                        iNew = oAllStrings.indexOf(sNew);
    
                        if (notInStep(iStp, iNew)) {
                            aNode = new int[4];
                            aNode[0] = j;
                            aNode[1] = i;
                            aNode[2] = iNew;
                            aNode[3] = iInd;
                            aSteps[iStp].add(aNode);
                        }
                    }
                }
            }
        }
    
        private static String replace(String sVal, int iInd, String sStr1, String sStr2) {
            String sRet = " ";
            sRet = sRet + sVal.substring(0, iInd) + sStr2 + sVal.substring(iInd + sStr1.length());
            return sRet;
        }
    
        private static boolean notInStep(int iStp, int iNew) {
            LinkedList<int[]> oNodes = aSteps[iStp];
            int[] aEdge;
            boolean bFound = false;
            for (int i = 0; i < oNodes.size(); i++) {
                aEdge = oNodes.get(i);
                if (aEdge[2] == iNew) {
                    bFound = true;
                    break;
                }
            }
            return !bFound;
        }
    
        private static void printSteps() {
            for (int i = 0; i < aSteps.length; i++) {
                System.out.println("Step " + i);
                for (int j = 0; j < aSteps[i].size(); j++) {
                    System.out.print(Arrays.toString(aSteps[i].get(j)) + " ");
                    System.out.print(oAllStrings.get(aSteps[i].get(j)[2]) + " ");
                }
                System.out.println("");
            }
        }
    }
    

    As far as I know, this forum applies to general code, and not just Minecraft modding.

    I was wondering if anyone could help me with this. I have no idea if this part of the forums is still alive, but if it is, please send help! (If you need any description of the code, I can do that.)

    Battle
     
    #1
  2. Nivyox

    Nivyox <p>roast-, meme- and daberator \o> dab</p>

    NIVYOX
    Mod
    Messages:
    4,166
    Hey, I'll check it out myself in a second;
     
    #2
    • Like Like x 1
    • Hype Train Hype Train x 1
  3. I like this challenge, I'll see if I can solve it too in some spare time today
     
    #3
  4. The issue why its not printing anything for you lies here

    Code:
        private static String replace(String sVal, int iInd, String sStr1, String sStr2) {
            String sRet = " ";
            sRet = sRet + sVal.substring(0, iInd) + sStr2 + sVal.substring(iInd + sStr1.length());
            return sRet;
        }
    You add a space to the string each time you use this function. As such, the final answer is " AAAB" , which cannot be found if trying to match to "AAAB"

    Removing the space makes your code work for the first test cases - but the time limit is reached on the further test cases.
     
    #4
  5. Thanks. So easy to mess up code these days.
     
    #5
  6. For research purposes, here's my code.
    It fails on some problems due to exceeding the time limit, but it solved 9 correctly within the time


    Code:
    import java.io.*;
    import java.util.ArrayList;
    import java.util.HashMap;
    
    public class Temp{
    
        private String[][] substitutions = new String[3][2];
        private int maxSteps;
        private String beginSeq, endSeq;
        private HashMap<String, Integer> checked = new HashMap<>();
    
        public static void main(String[] args){
            Temp m = new Temp();
            try {
                m.run(); //some stuff to not deal with static everywhere
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    
        public void run() throws IOException {
            //note bufferedreader is MUCH faster than scanner. i recommend using this
            //read all input we get
            BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
            for(int i = 0; i< 3; i++){
                String sub = in.readLine();
                String[] subSplit = sub.split(" ");
                substitutions[i][0]= subSplit[0];
                substitutions[i][1] = subSplit[1];
            }
            String[] infs = in.readLine().split(" ");
            maxSteps = Integer.parseInt(infs[0]);
            beginSeq = infs[1];
            endSeq = infs[2];
    
            //find the solution
            ArrayList<Change> sol = findSolution(new ArrayList<>(), beginSeq, maxSteps);
            //print the solution step by step
            for(Change c: sol){
                System.out.println(c.toString());
            }
        }
    
        private ArrayList<Change> findSolution(ArrayList<Change> currentSteps, String currentSeq, int steps){
            if(steps<=0){ //out of moves
                if(currentSeq.equals(endSeq)){ //if its the same, return the steps we took
                    return currentSteps;
                }
                return null; //we didnt find it
            }
    
            //if we have already checked this particular string with this many moves (or less) left, we dont have to do it again!
            if(checked.get(currentSeq)!=null && checked.get(currentSeq)>steps){
                return null;
            }
            checked.put(currentSeq, steps);
           
            //start recursion
    
            //go over each sub we have once
            for(int q=0;q<substitutions.length;q++){
                String[] set = substitutions[q];
                String key = set[0]; //get the substitution key
                //loop over the sequence we have
                int position = currentSeq.indexOf(key); //get the first position of this key in our current sequence
                while(position!=-1){ //if its position is -1, it means it doesnt exist anymore.
                    String newCurInd = currentSeq.substring(0, position) + set[1] + currentSeq.substring(position+key.length()); //create the new string
                    ArrayList<Change> curCopy = new ArrayList<>(currentSteps); //add a step to our steps array, after cloning.
                    curCopy.add(new Change(q, position, newCurInd));
                    ArrayList<Change> ret; //get a return array from recursion
                    if ((ret = findSolution(curCopy, newCurInd, steps-1)) != null) { //recursive call into this function with the new sequence, and a step less than our current call
                        return ret; // if we find a solution, return it
                    }
    
                    position = currentSeq.indexOf(key, position+1); // find the next position of this key in our sequence
                }
            }
    
            //here we found absolutely nothing!
            return null;
        }
    
        /**
         * class to hold changes we make to the string
         */
        public class Change{
            int rule;
            int position;
            String newString;
    
            public Change(int rule, int position, String newString){
                this.rule = rule;
                this.position = position;
                this.newString = newString;
            }
    
            @Override
            public String toString(){
                return (rule+1) + " " + (position+1) + " " + newString;
            }
        }
    }
     
    #6
    • Useful Useful x 1

Share This Page