UVA - 918 - ASCII Mandelbrot 

This article will explain my thought process to solve a problem called ASCII Mandelbrot (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Mandelbrot Set

Objective 

Given:

  1. Set of letters.

  2. Lower bound of the imaginary number.

  3. Upper bound of the imaginary number.

  4. Precision of the imaginary number.

  5. Lower bound of the real number.

  6. Upper bound of the real number.

  7. Precision of the real number.

We want to:

  1. Plot the mandelbrot set of the region.

Glossary 

  1. Mandelbrot Set — The set of all points in the complex plane that are bounded under a certain mathematical iteration.

Observation 

A complex number consists of 2 numbers, a real number and imaginary number. Complex number is expressed as z = a + ib, with z being the complex number, a being the real part, b being the imaginary part, and i being the imaginary unit or √-1.

We want to plot the given range of complex number into 2 dimensional array, with the first dimension for the real part and the second dimension for the imaginary part, to visualize the mandelbrot set. The mandelbrot set is based on the magnitude of Z, which can be calculated using the test equation of Z(0) = 0; Z(n) = Z(n-1)^2 + C and the magnitude equation of d = sqrt(a^2 + b^2).

For each complex number, we want to calculate the values of Z from Z(0) until Z(12). The C on the test equation is the complex number that we are currently plotting. Since C is a complex number, then Z will be a complex number as well due to addition.

After we know the Z value, we want to calculate the magnitude. Since Z is a complex number, the a on the magnitude equation is the real number and the b on the magnitude equation is the imaginary number. d will be a real number because the imaginary number is squared.

After the magnitude is known, we want to encode it as a letter. Find the first iteration with magnitude exceeding 2 and use the letter that correspond to the iteration number.

Algorithm 

To explore the complex number set, use a nested loop to explore the imaginary part and the real part of the given range. For each complex number, use another loop to calculate the test equation and the magnitude equation 12 times, then stop when the magnitude is greater than 2.

Due to precision issue, double won’t be enough to solve this problem, so we need to rely BigDecimal. Java 9 introduce the square root function for BigDecimal, however this feature is not available as the UVA platform is still using the Java 8. We can avoid the square root by comparing the squared magnitude against 2^2.

The time complexity of this solution is O({imaginary range} * {real range} * 12).

Implementation 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.math.BigDecimal;
import java.math.RoundingMode;

/**
 * 918 - ASCII Mandelbrot
 * Time limit: 3.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=859
 */
public class Main {
    public static void main(final String... args) throws IOException {
        final BufferedIO io = new BufferedIO(System.in, System.out);
        final Process process = new Process();

        final int totalCases = Integer.parseInt(io.readLine());
        for (int i = 0; i < totalCases; i++) {
            final String[] line = io.readLine(" ");

            final Input input = new Input();
            input.letters = line[0].substring(1, 13).toCharArray();
            input.imaginaryMin = new BigDecimal(line[1]);
            input.imaginaryMax = new BigDecimal(line[2]);
            input.imaginaryPrecision = new BigDecimal(line[3]);
            input.realMin = new BigDecimal(line[4]);
            input.realMax = new BigDecimal(line[5]);
            input.realPrecision = new BigDecimal(line[6]);

            final Output output = process.process(input);
            if (i > 0) io.write("\n");
            for (final char[] ploti : output.plot) {
                io.write("%s\n", new String(ploti));
            }
        }

        io.close();
    }
}

class Input {
    public char[] letters;
    public BigDecimal imaginaryMin;
    public BigDecimal imaginaryMax;
    public BigDecimal realMin;
    public BigDecimal realMax;
    public BigDecimal imaginaryPrecision;
    public BigDecimal realPrecision;
}

class Output {
    public char[][] plot;
}

class Process {
    public Output process(final Input input) {
        final Output output = new Output();

        final int vertical = getLength(input.imaginaryMin, input.imaginaryMax, input.imaginaryPrecision);
        final int horizontal = getLength(input.realMin, input.realMax, input.realPrecision);
        output.plot = new char[vertical + 1][horizontal + 1];
        fill(output.plot, ' ');

        BigDecimal imaginary = input.imaginaryMin;
        for (
                int row = 0;
                row < output.plot.length;
                row++, imaginary = imaginary.add(input.imaginaryPrecision)
        ) {
            BigDecimal real = input.realMin;
            for (
                    int col = 0;
                    col < output.plot[row].length;
                    col++, real = real.add(input.realPrecision)
            ) {
                ComplexNumber c = new ComplexNumber(real, imaginary);
                ComplexNumber z = new ComplexNumber(BigDecimal.ZERO, BigDecimal.ZERO);
                for (int iteration = 0; iteration < 12; iteration++) {
                    z = z.power2().add(c);
                    BigDecimal d2 = z.magnitude2();
                    if (d2.compareTo(BigDecimal.valueOf(4)) > 0) {
                        output.plot[row][col] = input.letters[iteration];
                        break;
                    }
                }
            }
        }

        return output;
    }

    private int getLength(final BigDecimal lower, final BigDecimal upper, final BigDecimal precision) {
        return upper.subtract(lower).divide(precision, RoundingMode.CEILING).intValue();
    }

    private void fill(final char[][] array, final char fill) {
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                array[i][j] = fill;
            }
        }
    }
}

class ComplexNumber {
    public final BigDecimal real;
    public final BigDecimal imaginary;

    public ComplexNumber(
            BigDecimal real,
            BigDecimal imaginary
    ) {
        this.real = real;
        this.imaginary = imaginary;
    }

    public ComplexNumber power2() {
        final BigDecimal r2 = real.multiply(real);
        final BigDecimal i2 = imaginary.multiply(imaginary);
        final BigDecimal ri = real.multiply(imaginary);
        return new ComplexNumber(
                r2.subtract(i2),
                ri.multiply(BigDecimal.valueOf(2))
        );
    }

    public ComplexNumber add(ComplexNumber o) {
        return new ComplexNumber(
                real.add(o.real),
                imaginary.add(o.imaginary)
        );
    }

    public BigDecimal magnitude2() {
        final BigDecimal r2 = real.multiply(real);
        final BigDecimal i2 = imaginary.multiply(imaginary);
        return r2.add(i2);
    }
}

final class BufferedIO {
    private final BufferedReader in;
    private final BufferedWriter out;

    public BufferedIO(final InputStream in, final OutputStream out) {
        this.in = new BufferedReader(new InputStreamReader(in));
        this.out = new BufferedWriter(new OutputStreamWriter(out));
    }

    public String[] readLine(final String separator) throws IOException {
        final String line = readLine();
        return line == null ? null : line.split(separator);
    }

    public String readLine() throws IOException {
        String line = in.readLine();
        while (line != null && line.isEmpty()) line = in.readLine();
        return line;
    }

    public void write(final String format, Object... args) throws IOException {
        final String string = String.format(format, args);
        write(string);
    }

    public void write(final String string) throws IOException {
        out.write(string);
    }

    public void close() throws IOException {
        in.close();
        out.flush();
        out.close();
    }
}


Powered by Docmost