Hexual Harassment – Prosa 2013 writeup

Af Tits|GTFO

I teksten til udfordringen stod der: ”Den gale forsker fra 2013 er tilbage, og han er ikke blevet raskere.” Med et link til opgaven i 2011.

I EuroNOP’s writeup fra 2011, kunne man læse om hvordan de løste en labyrint med kode. Den sti de fandt, havde forskellige farvede pixels, som indikerede 1 og 0, satte man disse sammen endte man ud med en binær fil. Mon ikke vi skulle i samme retning?

Billedet blev smækket ind i GIMP, 11996 x 12004 pixels, og når man zoomede ind, så det således ud:

Vejene består tydeligvis ikke at firkantede gange som i forrige opgave, men var der igen en gråtone af hvid, som ligger så tæt på hvid at vi ikke kan se den? Bingo, en hurtig analyse gennem GIMP fortæller os at der er 3 unikke farver i billedet. Her er et billede hvor vi skiftede den normale hvide farve ud med blå:

Så kom der blod på tanden, nu begyndte det at ligne noget. Ved at kigge nærmere på billede begyndte vi at se et mønster. Der er 6 forskellige veje du kan tage fra hver plet til den næste; op, op-højre, ned-højre, ned, ned-venstre og op-venstre. Disse er vist på næste billede:

Ved at kigge på om der var sorte pixels på vejen til næste plet, og skrev det i metoder til hver retning, manglede vi faktisk kun noget logik til at finde vej gennem labyrinten. Denne logik blev først skrevet i ikke optimeret i C#, men blev efter en time hvor den endnu ikke havde løst opgaven, skrevet over i java med hashtabels i stedet for collections. Hvilket bevirkede at opgaven blev løst på ca. 30 sek. I stedet :)

Efterfølgende blev stien oversat til 1 og 0 ved at kigge på om der var en specielt farvet pixel i hver plet. Efter at have leget lidt med big og small endians, fik vi noget data som gav mening. Her et lille udpluk af data’en i en tekst editor:

Det ligner umiddelbart koden til selv labyrinten. Credit til den som har lavet udfordringen for at indlejre koden til labyrinten i selve labyrinten :)

Her er vores endelige java kode til løsning af udfordringen:

import javax.imageio.ImageIO;

import java.awt.*;

import java.awt.image.BufferedImage;

import java.io.*;

import java.util.*;

import java.util.Queue;

public class Solution

{

        private static final int WHITE_COLOR = 0xFFFFFFFF;

        private static final int BLACK_COLOR = 0xFF000000;

        private static final int BLUE_COLOR = 0xFF0000FF;

        private final BufferedImage image;

        public Solution(BufferedImage image)

        {

                this.image = image;

        }

        private ArrayList<Point> breadthFirstSearch(Point from, Point to)

        {

                return new BreadFirstSearch(from, to).execute();

        }

        private void writeOutBytesInPath(ArrayList<Point> path, File file) throws IOException

        {

                int NUMBER_OF_BITS_IN_4_BYTES = 32;

                DataOutputStream out = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(file)));

                int b = 0;

                int i = 0;

                for(Point p : path)

                {

                        i++;

                        b = (b >>> 1) | (isWhite(p) ? 0 : 0x80000000);

                        if(i == NUMBER_OF_BITS_IN_4_BYTES)

                        {

                                out.writeInt(littleToBigEndian(b));

                                i = 0;

                                b = 0;

                        }

                }

                if(i != 0)

                        out.write(littleToBigEndian(b));

                out.close();

        }

        private static int littleToBigEndian(int i)

        {

                return ((i & 0xff) << 24) + ((i & 0xff00) << 8) + ((i & 0xff0000) >> 8) + ((i >> 24) & 0xff);

        }

        private boolean isBlack(Point p)

        {

                return image.getRGB(p.x, p.y) == BLACK_COLOR;

        }

        private boolean isWhite(Point p)

        {

                return image.getRGB(p.x, p.y) == WHITE_COLOR;

        }

        public boolean isInsideImageBounds(Point p)

        {

                return p.x >= 0 && p.y >= 0 && p.x < image.getWidth() && p.y < image.getHeight();

        }

        private static void writeOutImageWithBlueDotsOnPath(BufferedImage image, ArrayList<Point> path, File out) throws IOException

        {

                for(Point p : path)

                        image.setRGB(p.x - 1, p.y - 1, BLUE_COLOR);

                ImageIO.write(image, "png", out);

        }

        private class BreadFirstSearch

        {

                private static final int PIXELS_BETWEEN = 6;

                private final Map<Point, Point> fastestWayBackMap = new HashMap<>();

                private final Queue<Point> workList = new ArrayDeque<>();

                private final Point from;

                private final Point to;

                private BreadFirstSearch(Point from, Point to)

                {

                        this.from = from;

                        this.to = to;

                }

                public ArrayList<Point> execute()

                {

                        fastestWayBackMap.put(from, from);

                        workList.add(from);

                        while(!workList.isEmpty())

                        {

                                Point p = workList.remove();

                                if(p.equals(to))

                                        return constructRouteBackFrom(p);

                                visit(p);

                        }

                        throw new RuntimeException("Could not a way to go: " + from + " -> " + to);

                }

                private void visit(Point p)

                {

                        Point[] neighbours = new Point[]

                                        {

                                                        new Point(p.x, p.y - PIXELS_BETWEEN),

                                                        new Point(p.x, p.y + PIXELS_BETWEEN),

                                                        new Point(p.x - PIXELS_BETWEEN, p.y + PIXELS_BETWEEN / 2),

                                                        new Point(p.x - PIXELS_BETWEEN, p.y - PIXELS_BETWEEN / 2),

                                                        new Point(p.x + PIXELS_BETWEEN, p.y + PIXELS_BETWEEN / 2),

                                                        new Point(p.x + PIXELS_BETWEEN, p.y - PIXELS_BETWEEN / 2),

                                        };

                        for(Point neighbour : neighbours)

                        {

                                if(pathPossible(p, neighbour) && !alreadyVisited(neighbour))

                                {

                                        workList.add(neighbour);

                                        fastestWayBackMap.put(neighbour, p);

                                }

                        }

                }

                private boolean pathPossible(Point from, Point to)

                {

                        Point between = new Point((from.x + to.x) / 2, (from.y + to.y) / 2);

                        return isInsideImageBounds(to) && !isBlack(between) && to.y != 0 && to.y != image.getHeight() - 1;

                }

                private boolean alreadyVisited(Point p)

                {

                        return fastestWayBackMap.containsKey(p);

                }

                private ArrayList<Point> constructRouteBackFrom(Point p)

                {

                        ArrayList<Point> route = new ArrayList<>();

                        while(p != from)

                        {

                                route.add(p);

                                p = fastestWayBackMap.get(p);

                        }

                        route.add(p);

                        Collections.reverse(route);

                        return route;

                }

        }

        public static void main(String[] args) throws IOException

        {

                System.out.println("Reading image");

                BufferedImage image = ImageIO.read(new File("original_recolored.png"));

                System.out.println("Image loaded");

                Solution h = new Solution(image);

                Point from = new Point(4, 3);

                Point to = new Point(11992, 11997);

                System.out.println("Finding fastest path");

                ArrayList<Point> fastestPath = h.breadthFirstSearch(from, to);

                System.out.println("Path found, it has " + fastestPath.size() + " steps");

                System.out.println("Writing out binary file from bits on the path");

                h.writeOutBytesInPath(fastestPath, new File("fastestPath.bin"));

                System.out.println("Writing out original image with blue dots on the fastest path");

                writeOutImageWithBlueDotsOnPath(image, fastestPath, new File("original_recolored_with_path.png"));

                System.out.println("All done");

        }

}