算法题 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"));

还有更多工作要做

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

算法题 Decode Hex to set output

Algorith problem Decode Hex to set output

javascript

algorithm

bit-manipulation

bitwise-operators

奇特的数字编码

关于示例

还有更多工作要做