算法问题解码十六进制以设置输出 [英] 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.
问题
假想的笔输入设备将十六进制数据发送到该设备以显示带有颜色的行.
An imaginary pen input device sends hex data to the device to display a line with color.
示例绘制简单的绿线
将颜色设置为绿色，在(0,0)到(4000，4000)之间画一条线.该图中的实心圆表示笔向下
位置，空圆圈表示笔的向上位置.
Examples Draw simple Green Line
Set color to green, draw a line from (0,0) to (4000, 4000). Filled circle in this diagram indicates a pen down
position, empty circle indicates pen up position.
输入数据:F0A04000417F4000417FC040004000804001C05F205F20804000
Input Data: F0A04000417F4000417FC040004000804001C05F205F20804000
输出:
CLR； CO 0 255 0 255；
MV(0，0);
放下笔；
MV(4000，4000);
上笔;
Output:
CLR; CO 0 255 0 255;
MV (0, 0);
PEN DOWN;
MV (4000, 4000);
PEN UP;
我获得了有关每个输出的信息.
I got the information about each output.
此代码用于将十六进制编码为二进制.我猜想该解决方案会将十六进制编码为二进制，并对其进行操作以设置正确的输出.
This code is for encoding hex to binary. I guess that the solution would encode the hex to binary, and manipulate it to set correct output.
function hex2bin(hex){
return (parseInt(hex, 16).toString(2))}
具有输入数据的预期结果与示例例的输出相同.
The expected result has the same output as Examaple's with the input data.
推荐答案
首先，您的问题中缺少一些重要的信息:像4000这样的数字(结果)是如何以十六进制格式编码的.
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
数字似乎每个都用2个字节(4个十六进制字符)编码，其中这2个字节的最高有效位(第7和15位)对值无贡献(它们始终为零).
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).
此外，其余14位用偏移二进制进行编码，其中这14位是反相符号位.
Furthermore, the remaining 14 bits are encoded in offset binary, where the most significant of those 14 bits is the inverted sign bit.
这意味着"4000"为零，"0000"为-8192(最小)，而"7F7F"为8191(最大).请注意，最后一个字符不能超过7，因为这会设置此(自定义)编码中未使用的位.
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.
您提供的输入示例可以分为以下几部分:
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:
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"));
在问题的屏幕快照中，快要结束了，还提到了将剪切动作剪切到边界框上的情况.这超出了您有关解码十六进制输入的问题，因此我将保留此内容.有兴趣的人可以查看有关计算线段交点的问答，例如此.
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.
这篇关于算法问题解码十六进制以设置输出的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
