Algorith Problem Decode Hex To Set Output

I got an algorithm that I need to solve. Unfortunately, I can't even find a clue about a solution. Please help me to understand how to solve this problem. The problem An imaginary

Solution 1:

First of all, some important information is missing from your question: how the numbers like 4000 (in the result) are encoded in the hex format.

I think I could derive it from the example though

The peculiar numeric encoding

Numbers seem to be encoded with 2 bytes (4 hex characters) each, where the most significant bits of these 2 bytes (bits 7 and 15) do not contribute to the value (they are always zero).

Furthermore, the remaining 14 bits are encoded in offset binary, where the most significant of those 14 bits is the inverted sign bit.

This means that "4000" is zero, "0000" is -8192 (the minimum), and "7F7F" is 8191 (the maximum). Note that the one but last character cannot be more than 7, since that would set a bit that is not used in this (custom) encoding.

This was the hardest part to derive from the little info you provided.

On the Example

The input example you provided can be broken down into pieces like this:

opcode | argument(s)
-------+----------------------------"F0"  |
 "A0"  | "4000""417F""4000""417F""C0"  | "4000""4000""80"  | "4001""C0"  | "5F20""5F20""80"  | "4000"

Using the numeric conversion discussed above, this would translate to:

opcode | argument(s)
-------+------------
  240  |
  160  | 0 255 0 255
  192  | 0 0
  128  | 1
  192  | 4000 4000
  128  | 0

And then it is a matter of following the instructions to turn that into the required output.

So the algorithm could first decode the input string into commands, where each command consists of an opcode and zero or more numeric arguments.

And then those commands could be turned into the required output by keeping track of whether the pen is down and what the current coordinates are:

functiondecode(hex) {
    let commands = [];
    let command;
    for (let i = 0, len; i < hex.length; i+=len) {
        // Opcodes take 1 byte (i.e. 2 hex characters), and // numbers take 2 bytes (4 characters)
        len = hex[i] >= "8" ? 2 : 4;
        let num = parseInt(hex.slice(i, i+len), 16);
        if (len === 2) { // opcode
            command = []; // start a new command
            commands.push(command);
        } else { // number// The encoded format is a custom one. This seems to be it:
            num = ((num & 0x7F00) >> 1) + (num & 0x7F) - 0x2000; 
        }
        command.push(num); // push opcode or argument in current command
    }
    return commands;
}

functiondisassemble(hex) {
    let isPenDown = false;
    let x = 0, y = 0;
    let output = "";
    let commands = decode(hex);
    for (let [opcode, ...args] of commands) {
        if (opcode === 0xF0) {
            x = y = 0;
            isPenDown = false;
            output += "CLR;\n";
        } elseif (opcode === 0x80) {
            isPenDown = args[0] > 0;
            output += "PEN " + (isPenDown ? "DOWN" : "UP") + ";\n";
        } elseif (opcode === 0xA0) {
            output += "CO " + args.join(" ") + ";\n";
        } elseif (opcode === 0xC0) {
            let allPos = "", lastPos;
            for (let i = 0; i < args.length; i+=2) {
                x += args[i];
                y += args[i+1];
                lastPos = ` (${x}, ${y})`;
                if (isPenDown) allPos += lastPos;
            }
            output += "MV" + (allPos || lastPos) + ";\n";
        } // else: ignore unknown commands
    }
    return output;
}

// Sample:console.log(disassemble("F0A04000417F4000417FC040004000804001C05F205F20804000"));

More to do

In the screenshot of the problem, near the end, there is also mention of clipping movements to a bounding box. This goes beyond your question about decoding the hex input, so I will leave it at this. For the interested, you could check out Q&A about calculating line segment intersections, such as this one.