javascript - 算法题 Decode Hex to set output

Question

我有一个算法需要解决。不幸的是，我什至找不到解决方案的线索。请帮助我了解如何解决此问题。

问题

想象中的笔输入设备将十六进制数据发送到设备以显示带颜色的线条。

示例绘制简单的绿线
将颜色设置为绿色，从 (0,0) 到 (4000, 4000) 画一条线。此图中的实心圆表示落笔 位置，空心圆圈表示抬笔位置。

Input Data: F0A04000417F4000417FC040004000804001C05F205F20804000

Output:
CLR; CO 0 255 0 255;
MV (0, 0);
PEN DOWN;
MV (4000, 4000);
PEN UP;

我得到了每个输出的信息。

此代码用于将十六进制编码为二进制。我猜该解决方案会将十六进制编码为二进制，并对其进行操作以设置正确的输出。

function hex2bin(hex){
    return (parseInt(hex, 16).toString(2))}

预期结果与 Examaple 的输入数据具有相同的输出。

Answer 1

首先，您的问题中缺少一些重要信息:像 4000 这样的数字(在结果中)是如何以十六进制格式编码的。

我想我可以从这个例子中推导出来

奇特的数字编码

数字似乎每个都用 2 个字节(4 个十六进制字符)编码，其中这 2 个字节的最高有效位(第 7 位和第 15 位)对值没有贡献(它们始终为零)。

此外，剩余的 14 位编码在 offset binary 中，其中这 14 位中最重要的是反转的符号位。

这意味着“4000”是零，“0000”是-8192(最小值)，“7F7F”是8191(最大值)。请注意，最后一个字符不能超过 7 个，因为这会设置一个未在此(自定义)编码中使用的位。

这是从您提供的少量信息中得出的最难的部分。

关于例子

您提供的输入示例可以分解成这样的部分:

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

使用上面讨论的数字转换，这将转化为:

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

然后只需按照说明将其转换为所需的输出即可。

因此该算法可以首先将输入字符串解码为命令，其中每个命令由一个操作码和零个或多个数字参数组成。

然后通过跟踪笔是否按下以及当前坐标是什么，可以将这些命令转换为所需的输出:

function decode(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;
}

function disassemble(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";
        } else if (opcode === 0x80) {
            isPenDown = args[0] > 0;
            output += "PEN " + (isPenDown ? "DOWN" : "UP") + ";\n";
        } else if (opcode === 0xA0) {
            output += "CO " + args.join(" ") + ";\n";
        } else if (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"));

更多工作要做

在问题的屏幕截图中，接近尾声时，还提到了边界框的裁剪运动。这超出了你关于解码十六进制输入的问题，所以我会把它留在这里。有兴趣的可以看看关于计算线段交点的Q&A，比如this one .