Gynvael’s mission PL-008

/ derfenriswolf

This is a solution of a “mission” created by Gynvael Coldwind and presented on the YouTube video. The actual mission text (in polish)
Solution code (in GO this time): https://github.com/jzakrzewski/gyn-pl-008
Translation would be something along this:

SCAN DRONE v0.17.3
CLASSIFIED DATA. FOR YOUR EYES ONLY.

— Operator’s Manual
1. Drone is equipped with a spinning LIDAR.
2. Drone automatically scans each new position with the LIDAR.
3. The scan is made in 10-degree interval; the results are in meters.
4. 0-degree angle means north.
5. There may be some imprecision, especially in tight passages.
6. The LIDAR has 50m range. Everything above that returns “inf”.
7. The scan is made at constant height of 1m above the ground.
8. Drone always moves exactly 1m.
9. Drone reports its position in meters on the W-E and N-S axis. The position
is relative to a (fixed) sender.
10. Drone can only move in the E/W/N/S direction.

— Data Format
SCAN DRONE v0.17.3
DRONES_POSITION_X DRONES_POSITION_Y
DISTANCE_ON_ANGLE_0
DISTANCE_ON_ANGLE_10
DISTANCE_ON_ANGLE_20
…
DISTANCE_ON_ANGLE_350
MOVE_EAST: ADDRESS_MOVING_EAST_OR_”not possible”
MOVE_WEST: ADDRESS_MOVING_WEST_OR_”not possible”
MOVE_SOUTH: ADDRESS_MOVING_SOUTH_OR_”not possible”
MOVE_NORTH: ADDRESS_MOVING_NORTH_OR_”not possible”

–Data
START

The “START” is actually the link to the first portion of data.

The task (or what do we really have to do)

As in every mission the objective is to find a secret passphrase. So probably the best idea is to visualise the data. This would be our second task.
The first thing to do is to actually get the data.

The tools (and why)

Even though I’d be perfectly capable of writing some C(++) and using curl to get the files (I do such things on a daily basis), I decided to give the go language a try. I’m trying to learn it (I still suck, what is clearly visible in the code) and thought it’d be fun. Additionally I took a sneak peek at KrzaQ’s solution (PL) just to have an idea if I’d have had enough time and I’ve learned that I shouldn’t try to solve it without parallelism 😉 So GO it is.

Downloading

I wanted to achieve parallel download. The problem was that every example I have found had its data set known in advance. Our must be discovered on the fly. My solution involves two channels, a WaitGroup, a Mutex and a map. (Warning! Ugly code ahead):

scans = make(map[string]Scan)
dwQueue = make(chan string, maxParallel*4)

for i := 0; i < maxParallel; i++ {
    go func() {
        downloadWorker(wd)
    }()
}

queueScanDownload("68eb1a7625837e38d55c54dc99257a17.txt")
wg.Wait()

for i := 0; i < maxParallel; i++ {
    dwEnd <- 0
}

So here I basically create all the workers, kick off the download, wait until everything is downloaded and send the signal to the workers to finish. BTW: I had a stupid mistake here where I had only sent 1 item to the dwEnd channel. I have debugged it for an hour trying to figure out why doesn’t it finish…
Anyway, the trickiest part has been to synchronise it correctly.

func downloadWorker(dest string) {
    for {
        select {
        case id := <-dwQueue:
            if err := downloadScan(id, dest); err != nil {
                panic(err)
            }
        case <-dwEnd:
            return
        }
    }
}

func queueScanDownload(id string) {
    mux.Lock()
    _, exists := scans[id]
    if !exists {
        scans[id] = Scan{} // block the spot
    }
    mux.Unlock()
    if !exists {
        wg.Add(1)
        go func() {
            dwQueue <- id
        }() // avoiding deadlock by delegating to yet another coroutine
    }
}

The particularly difficult to place was the incrementing and decrementing the WaitGroup (wg), and adding the id to dwQueue. (FYI: the decrementing of wg must be placed after all the move links from current download are queued.

It has downloaded 187812 scan files. Over 95 megabytes of data…

Anyway, this part has been more like my fight with the new language.

Primary task solution

Parsing the data from the disk has been done in similar manner (also parallel). Nothing really interesting. The last part is mostly some basic geometry math:

pts := make([]point, len(scans)*36) // max points
rad := float64(math.Pi / 180.0)
type sincos struct {
    sin float64
    cos float64
}
sc := make([]sincos, 36)
for i := 0; i < 36; i++ {
    sin, cos := math.Sincos(rad * float64(i*10))
    sc[i] = sincos{sin, cos}
}

var mx float64 = 0.0
var my float64 = 0.0

factor := 1.0
pos := 0
for _, s := range scans {
    for i, d := range s.dist {
        if !math.IsInf(d, 0) {
            p := point{
                x: factor * (s.pos.x + sc[i].sin*d),
                y: factor * (s.pos.y - sc[i].cos*d),
            }
            pts[pos] = p
            pos++
            if p.x > mx {
                mx = p.x
            }
            if p.y > my {
                my = p.y
            }
        }
    }
}

w := int(mx + 10)
h := int(my + 10)
fmt.Println("w: ", w, " h: ", h)
out := make([]byte, w*h)
for _, p := range pts {
    out[int(int(p.y)*w+int(p.x))] = byte(255)
}

err := ioutil.WriteFile("/tmp/map.data", out, 0644)
if err != nil {
    panic(err)
}

fmt.Println("Done")

So I precompute a table of sine and cosine then compute absolute point coordinates. The factor lets me scale the result. At 1.0 (100%) it’s however readable enough.
The hack when computing w and h is there to counteract the problems with float rounding. Without it you’ll get index out of bounds.
The last part just saves a raw bitmap on the disk. Ad because I’m lazy, it’s white-on-black. GIMP rendered this:
map Can you find the password?

Bonus

The bonus task was to create some kind of visualisation. For this. I have an amazing idea ( ;P ) but no time at the moment. I may however do this later, in which case I’ll share it here.

Leave a comment