3n+1 challenge at UVa

6.3k views Asked by At

I'm having trouble running the "3n+1 Problem" from the "Programming Challenges" book.

I've tried every solution in Java I could find on google (even the ones on Stack Overflow), and not a single one works, they all report a "Wrong answer". I also found a working C++ solution, translated it to Java, and same thing: "Wrong answer".

I'm using the template from Programming Challenges for Java submissions, and I could swear my algorithm is right, the only possible problem I can think of is in the code for reading the input or writing the output, but I can't figure it out. Here's my code, any help would be greatly appreciated:

class myStuff implements Runnable {

    @Override
    public void run() {
        String line = Main.ReadLn(128);
        while (line != null) {
            process(line);
            line = Main.ReadLn(128);
        }
    }

    private void process(String line) {

        String[] data = line.split("\\s+");

        if (data.length == 2) {
            int low = Integer.parseInt(data[0]);
            int high = Integer.parseInt(data[1]);
            int max = low < high ? findMax(low, high) : findMax(high, low);
            System.out.println(low + " " + high + " " + max);
        }

    }

    private int findMax(int low, int high) {
        int max = Integer.MIN_VALUE;
        for (int i = low; i <= high; i++) {
            int length = cycleLength(i);
            if (length > max)
                max = length;
        }
        return max;
    }

    private int cycleLength(int i) {

        long n = i;
        int length = 1;

        while (n > 1) {
            n = ((n & 1) == 0) ? n >> 1 : 3*n + 1;
            length++;
        }

        return length;

    }

}

// java program model from www.programming-challenges.com
class Main implements Runnable {
    static String ReadLn(int maxLength) { // utility function to read from
        // stdin, Provided by Programming-challenges, edit for style only
        byte line[] = new byte[maxLength];
        int length = 0;
        int input = -1;
        try {
            while (length < maxLength) { // Read untill maxlength
                input = System.in.read();
                if ((input < 0) || (input == '\n'))
                    break; // or untill end of line ninput
                line[length++] += input;
            }

            if ((input < 0) && (length == 0))
                return null; // eof
            return new String(line, 0, length);
        } catch (java.io.IOException e) {
            return null;
        }
    }

    public static void main(String args[]) { // entry point from OS
        Main myWork = new Main(); // Construct the bootloader
        myWork.run(); // execute
    }

    @Override
    public void run() {
        new myStuff().run();
    }

}
2

There are 2 answers

2
Óscar López On BEST ANSWER

Solved. OK, for starters the site http://programming-challenges.com definitely is not working right now for Java submissions (they're doing some kind of server migration now). I tried the alternate site http://uva.onlinejudge.org ; that one is processing Java submissions correctly.

But anyway, I had a bug in my code above - this line fixes it:

String[] data = line.trim().split("\\s+");

The input data will always be messy - extra spaces, empty lines, etc. and anyone trying to parse the input should assume this.

0
aked On

Home>Online Judge > submission Specifications

this link might help

Sample code to read input is from : http://online-judge.uva.es/problemset/data/p100.java.html

here is one more link for stackoverflow : https://stackoverflow.com/a/14632770/1060656

I think the most important thing in UVA judge is 1) Get the output Exactly same , No Extra Lines at the end . 2) I am assuming , Never throw exception just return or break with No output for Outside boundary parameters. 3)Output is case sensitive 4)Output Parameters should Maintain Space as shown in problem