Proposal（第三次作业 SHRDLU）

Clancy-Zhu commented 2 years ago

SHRDLU是由MIT的Terry Winograd在1970年开发的一个以“积木世界”模拟为背景的自然语言理解程序。程序构建了一个“积木世界”，用户可以通过英语来控制“机器人”与积木进行命名、移动、查询等互动。本作业不会考察你的程序对英语文本的理解，而是让你实现一个对“积木世界”的模拟（我们对原本的“积木世界”有所改编，以适应作业需求）。

积木的种类包括：长方体（box）、圆柱体（column）、四棱锥体（pyramid）。

输入包含N+1行：第一行为指令数N，随后每行为一个指令。输入的指令包括以下几种：

构建积木（1）：输入包括积木种类（B/C/P）、长宽高（均为不大于100的正整数，保证圆柱长宽相同）、名称。构造一个对应积木。输出“YES. THE (BOX/COLUMN/PYRAMID) NAMED XXX.\n”

放置积木（2）：输入包括积木名称、目的（x,y）坐标。将（未放置的）对应积木放置到底面中心为（x,y）的位置，且其底面z坐标为此矩形范围内最高的积木（若为平面）顶部（你可以理解为这个世界有重力）；若放置成功，输出“OK.\n”。若不可放置该积木，则输出“I CAN'T.\n”。放置积木时，只要底面范围内有棱锥，就不可放置（即所有棱锥必须在顶部）；否则底面范围内最高的积木顶部为底面Z坐标。（提示，棱锥的get_h()可以返回一个足够高的高度）“底面相交”指底面的公共面积大于0。

移除积木（3）：输入包括积木名称。将（已放置的）对应积木移除（需要先移除高于该积木且底面有交集的所有积木，这些移除不需要提示信息）；若移除成功，输出”OK.\n”。若该积木未被放置则输出“I CAN'T.\n”。

查询坐标（4）：输入包括(x,y)坐标。输出对应位置俯视看到的积木”THE (BOX/COLUMN/PYRAMID) NAMED XXX.\n”；若没有积木则输出“NO.\n”。若该坐标恰为某积木的边界，不算看到该积木。

查询积木位置（5）：输入包括积木名称。输出对应积木重心的(x,y,z)坐标；若其未被放置，则输出“NO.\n”。

销毁积木（0）：输入包括积木名称。将对应积木销毁。由指令销毁积木时，必须保证积木未被放置，否则输出"I CAN'T\n"。若成功销毁，输出”GOODBYE.\n”

对输入积木名称的（除构建积木外的）指令：成功选择时输出”THE (BOX/COLUMN/PYRAMID) NAMED XXX. ”不存在对应名称积木，则输出”I DON'T UNDERSTAND WHICH BLOCK YOU MEAN. \n“并不进行任何操作。在你的程序结束时，应当销毁所有尚未销毁的积木，顺序与构建的相反。此时仍需要输出提示信息（仅有”GOODBYE.\n”）。

我们将给定Makefile、main.cpp、block.h/cpp、world.h，你不应该改动这些文件。你的任务是在实现block类的基础上继承box、column、pyramid类；并完成world类的函数定义。

一个简单的样例： INPUT 10 1 B 10 10 5 BEN 2 BEN 0 0 5 TIM 1 P 6 6 4 PETER 2 PETER 1 3 1 C 5 5 5 CLANCY 4 -2 -2 3 CLANCY 0 CLANCY 5 BEN

OUTPUT YES. THE BOX NAMED BEN. THE BOX NAMED BEN. OK. I DON'T UNDERSTAND WHICH BLOCK YOU MEAN. YES. THE PYRAMID NAMED PETER. THE PYRAMID NAMED PETER. OK. YES. THE COLUMN NAMED CLANCY. THE BOX NAMED BEN. THE COLUMN NAMED CLANCY. I CAN’T. THE COLUMN NAMED CLANCY. GOODBYE. THE BOX NAMED BEN. (0,0,2.5). GOODBYE. GOODBYE.

数据范围：指令数不大于1000 积木数不大于100 且每个积木长宽高不大于100 涉及的所有xyz坐标为绝对值不大于1000的整数保证每个积木名称为各不相同的2-20位字符串

hzhwcmhf commented 2 years ago

有几个问题：

题目主要考点是什么。我能理解几个形状都可以作为某一基础物体的子类，但感觉看起来判断逻辑基本相同，和形状关系不大，把形状和颜色都作为物体的成员记录即可，不太需要重载的多态性质。这个地方可能是我没理解，但总之需要更加明确一些
算法实现难度。OOP的作业主要考察对对象的抽象能力，编写面向对象的逻辑。目前不少操作比较复杂，比如下落和删除时都需要判断三维物体的位置，这部分是想让同学们怎么实现？
有些说明不太清楚，落到多个物体上怎么解决，只有一部分重合怎么解决？

Clancy-Zhu commented 2 years ago

1.主要考点为类的继承；world类中存储的是block的指针。 2.可将操作“移动”（实现较难）改为“绕底面中心旋转90度”（已放置的积木需要先判断是否有足够空间（不需要移除上方积木）；cube类无对应操作，这两种情况输出"I CAN'T.\n"）；其余操作每次遍历所有积木即可（最多100块，不会超时） 3.同时落到多个同等高度物体上，只要有一个为方形，即为可以放置；只要重合部分面积大于0即可放置。

hzhwcmhf commented 2 years ago

我还是感觉这里的继承意义不大，整个程序可能基本还是由面向过程的方法处理，建议可以再考虑一下如何充分利用多态性质。如果你觉得现在设计合理的话，麻烦给一下具体细节，比如Block.h如何有什么函数

Clancy-Zhu commented 2 years ago

更改描述： “底面相交”指底面的公共面积大于0 放置积木时，只要底面范围内有pyramid，就不可放置（即所有pyramid必须在顶部）；否则底面范围内最高的积木顶部为底面Z坐标。（提示，pyramid类的get_c可以返回一个足够高的高度）移除积木时，需要先移除高于该积木且底面有交集的所有积木。旋转90度时先给出一个维度（保证为XYZ之一），然后交换另两个维度的长度。只能旋转未放置的积木，cube类不可旋转，pyramid类不能在非Z平面旋转。这两种情况输出"I CAN'T.\n"。由指令销毁积木时，必须保证积木未被放置，否则输出"I CAN'T\n"。 ` class Block{ private: int a,b,c,x,y,z; char color; string name; bool is_placed; public: Block(); ~Block(); const bool placed(); const int get_x(); const int get_y(); const int get_z(); const int get_a(); const int get_b(); const int get_c(); void is_found(bool type);//find的提示信息 void place(int X,int Y,int Z); void remove(); void rotate(char dim); void rename(string new_name); const bool overlap(const Block& oth);//判断oth积木是否与该积木底面相交 const bool overlap(int A,int B,int X,int Y); }

class World{ private: Block* All_blocks[100]; int now; public: const int find_block(char col); const int find_block(string name); void create_block(char typ,char col,int A,int B,int C,string nam=""); void place_block(int index,int X,int Y);//放置积木 void remove_block(int index,bool active);//移除某个积木，bool表示是否需要提示信息 void rotate_block(int index,char dim);//旋转某个积木 void find_color(int X,int Y);//获取给定位置的颜色 void find_XYZ(int index);//获取给定下标积木的坐标 void rename_block(int index,string newname); void delete_block(int index);//摧毁积木 } `

Clancy-Zhu commented 2 years ago

更改描述：一切积木都给定名称

hzhwcmhf commented 2 years ago

我看了代码，现在题目的主要问题在于对多态的使用非常冗余。例如输出BLEU CUBE还是别的什么可以在构造的时候直接使用string储存，没有必要每个类里都单独在输出时判断。这种设计不仅让代码变得更复杂，也是违背继承的初衷的。同时，多态的使用和核心问题没有关系。问题核心应该在放置、判断是否重合等功能上，但目前使用了普通的基类实现即可解决问题。建议再思考一下如何将核心问题和多态的特性结合在一起

Clancy-Zhu commented 2 years ago

我现在有一个想法，是去掉cube类，增加sphere类（放置要求为“底面中心在一个平面上，同时球内不能有其他物体”；球上不能放东西）或column类（圆柱，其余要求都不变），您看是否可行呢？可以将题目改为纯粹搭（box、pyramid、sphere、column）积木，实现对应的放置判断

Clancy-Zhu commented 2 years ago

但是感觉这样会比较繁杂（要写球和球、球和方块、方块和球的判断）

hzhwcmhf commented 2 years ago

这个要看怎么设计接口。如果说每个类里面都需要判断另一个物体是什么形状，那这个接口设计就比较失败。比如球和方块的判断与方块和球的判断，两者逻辑应该是一致的，则最终应该只有一份逻辑实现代码

Clancy-Zhu commented 2 years ago

嗯，那您认为这样改题目（纯粹搭四种积木，去掉rotate，也可以去掉颜色）可行吗？

hzhwcmhf commented 2 years ago

你先提出一个接口的设计方案？

Clancy-Zhu commented 2 years ago

方块和棱锥为一类；球和圆柱一类，增加一个public的bool接口只需要增加圆&圆、圆&方块（可以直接令方块&圆返回圆&方块）

Clancy-Zhu commented 2 years ago

球的放置条件改为“底面中心在一个平面上，同时球赤道所在的圆柱内不能有其他物体”

Clancy-Zhu commented 2 years ago

或者也可以采用二级继承，棱锥是特殊的方块；球是特殊的圆柱？这样可以简化放置的逻辑

hzhwcmhf commented 2 years ago

重点是怎么样通过虚函数的形式将不同判断重叠的逻辑分配到不同的对象中，这一部分麻烦给一点具体的函数定义或者实现（可以先不实现数学的部分）

Clancy-Zhu commented 2 years ago

由于球类型的overlap不满足交换律，方块&圆返回圆&方块似乎不可取但是如果只有圆柱就可以直接应用交换律

hzhwcmhf commented 2 years ago

现在最大的问题就是基类里面涉及到太多子类的信息，比如说is_round和几个不同的overlap。面向对象的设计原则就是父类要尽量少干涉子类的情况，使得增加新的子类的时候父类不用做修改。

你现在遇到的这个问题在C++里叫 double dispatch，确实比较不容易实现。我给你一个例子，利用了c++的模板特性，你可以考虑按这个重新组织一下接口。题目可以设计为提供部分形状的实现，让同学们拓展更多的其他形状。

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

class Block
{
public:
    bool overlap(Block* other);
    virtual string type() = 0;
};

class Box: public Block
{
public:
    virtual string type() {return "box";}
};

class Pyramid: public Block
{
public:
    virtual string type() {return "pyramid";}
};

class Column: public Block
{
public:
    virtual string type() {return "column";}
};

template<class T1, class T2>
bool call_overlap(T1 *a, T2 *b) {
    assert(false);
}

template<class T2>
bool call_overlap(Block *a, T2 *b){
    if(a->type() == "box") return call_overlap(b, dynamic_cast<Box*>(a));
    else if (a->type() == "pyramid") return call_overlap(b, dynamic_cast<Pyramid*>(a));
    else if (a->type() == "column") return call_overlap(b, dynamic_cast<Column*>(a));
    else assert(false);
}
// template<> bool call_overlap(Block *a, Block *b);

template<>
bool call_overlap(Box *a, Box *b) {cout << "box, box" << endl; return true;}
template<>
bool call_overlap(Box *a, Pyramid *b) {cout << "box, Pyramid" << endl; return true;}
template<>
bool call_overlap(Pyramid *a, Column *b) {cout << "pyramid, column" << endl; return true;}

bool Block::overlap(Block *other){
    return call_overlap(this, other);
}

int main()
{
    Block* a[] = {new Box(), new Pyramid(), new Column()};
    a[0]->overlap(a[0]);
    a[0]->overlap(a[1]);
    a[1]->overlap(a[2]);
    return 0;
}

Clancy-Zhu commented 2 years ago

如果使用模板主要考点会不会变化太多了？我想也许可以在基类只设定一个virtual bool overlap(const Block &oth) const，在box和column类使用重载各自设定一个版本的实现？但是那样column和box会不独立……感觉不太好

hzhwcmhf commented 2 years ago

如果要用template的话，可以考虑先给两个形状，剩下的让同学补全，可以作为C++两种多态综合运用的练习

你现在那种每个子类都要写个if，对新加形状不太友好。每加一个，所有个类都得改

Clancy-Zhu commented 2 years ago

好的，也许可以先给一个box类，其余进行补充。

hzhwcmhf commented 2 years ago

你把题目再细化一下吧，包括题目要求、提供给同学们的部分代码

Clancy-Zhu commented 2 years ago

现在我想的一个问题是如果给定box类，pyramid类会不会太简单了？在思考如何更改pyramid类的要求很难想到一个难度适中的方案（计算棱锥各高度的截面比较繁琐，尤其需要增加不止一个接口）……决定维持现状或者可以直接把棱锥删除，专注于实现column类

Clancy-Zhu commented 2 years ago

题目简介

SHRDLU是由MIT的Terry Winograd在1970年开发的一个以“积木世界”模拟为背景的自然语言理解程序。程序构建了一个“积木世界”，用户可以通过英语来控制“机器人”与积木进行命名、移动、查询等互动。本作业不会考察你的程序对英语文本的理解，而是让你实现一个对“积木世界”的模拟。我们对原本的“积木世界”有所简化，以适应作业需求。本题中积木的种类包括长方体（box）和圆柱体（column）。我们已经写好了main函数，实现了box类（及基类block），现在希望你能够完成column类，并实现积木世界类world的各操作。

输入/输出格式

输入包含N+1行。第一行为指令数N。随后每行为一个整数op（代表指令种类）和对应的指令参数。你应恰有一行输出对应每行输入指令。指令包括以下几种：构建积木（op=1）：参数包括积木种类（字符B/C）、长、宽、高（均为不大于100的正整数，保证圆柱长宽相同）、名称。构造一个对应积木。输出"YES. THE (BOX/COLUMN) NAMED XXX.\n" 放置积木（op=2）：参数包括一个字符串（积木名称）、目的(x, y)坐标。将（未放置的）对应积木放置到底面中心为(x, y)的位置，且其底面z坐标为底面内（指与底面的公共面积大于0）最高的积木顶部；若放置成功，输出"OK.\n"。若该积木已放置则输出"I CAN'T.\n"。移除积木（op=3）：参数包括一个字符串（积木名称）。将（已放置的）对应积木移除（需要先移除高于该积木且底面有交集的所有积木，这些移除不需要提示信息）；若移除成功，输出"OK.\n"。若该积木未被放置则输出"I CAN'T.\n”。查询坐标（op=4）：参数包括两个整数，代表(x, y)坐标。输出对应位置俯视看到的积木"THE (BOX/COLUMN) NAMED XXX.\n"；若该位置没有积木则输出"NO.\n"。 若该坐标恰在某积木的底面边界上，该积木不算被看到。 查询积木位置（op=5）：参数包括一个字符串（积木名称）。输出对应积木重心的(x, y, z)坐标；若其未被放置，则输出"NO.\n"。销毁积木（op=0）：参数包括一个字符串（积木名称）。将对应积木销毁。由指令销毁积木时，必须保证积木未被放置，否则输出"I CAN'T\n"。若成功销毁，输出"XXX, GOODBYE.\n" 保证所有输入指令格式合法。

对指定积木名称的（除构建积木外的）指令：成功选择积木时输出"THE (BOX/COLUMN) NAMED XXX. "不存在对应名称积木，则输出"I DON'T UNDERSTAND WHICH BLOCK YOU MEAN. \n"并不进行任何操作。在你的程序结束时，应当销毁所有尚未销毁的积木，顺序与构建的相反。此时仍需要输出提示信息（仅有"XXX, GOODBYE.\n"）。

我们将给定Makefile、main.cpp、block.h/cpp、box.h/cpp、world.h，你不应该改动这些文件。下载地址

你的任务是参考基类和box类，实现column类；并完成world类的函数定义。这些类的声明和部分简单函数的定义如下。

class Block
{
private:
    int a, b, c, x, y, z;
    string name;
    bool placed;

public:
    Block(int A, int B, int C, string Name) : a(A), b(B), c(C), name(Name), placed(0){};
    ~Block() { cout << name << "GOODBYE.\n"; };
    virtual string type() const = 0;
    string get_name() const { return name; };
    bool is_placed() const { return placed; };
    int get_x() const { return x; };
    int get_y() const { return y; };
    int get_z() const { return z; };
    int get_a() const { return a; };
    int get_b() const { return b; };
    int get_height() const { return c + z; };
    void place_Z(int Z);
    void place_XY(int X, int Y);
    void remove();
    bool overlap(const Block &other) const;
    void screen() const { cout << "THE " << type() << " NAMED " << get_name() << ". "; };
    void center_of_mass() const { cout << '(' << x << ',' << y << ',' << z + c * 0.5 << ").\n"; };
    virtual bool contain(int X, int Y) const = 0;
};

class Box : public Block
{
public:
    Box(int A, int B, int C, string Name);
    string type() const { return "BOX"; };
    bool contain(int X, int Y) const;
};

bool call_overlap(const Box &A, const Box &B);

class World
{
private:
    Block *All_blocks[100];
    int now;

public:
    World();
    ~World();
    int find_block(string name) const;
    void create_block(char typ, int A, int B, int C, string nam);
    void place_block(int index, int X, int Y);
    void remove_block(int index, bool echo);
    void find_name(int X, int Y) const;
    void find_XYZ(int index) const;
    void delete_block(int index);
};

输入样例

10
1 B 10 10 5 BEN
2 BEN 0 0 
5 TIM
1 C 6 6 4 CINDY
2 CINDY 1 3
1 C 5 5 5 CLANCY
4 -2 -2
3 CLANCY
0 CLANCY
5 CINDY

输出样例

YES. THE BOX NAMED BEN.
THE BOX NAMED BEN. OK.
I DON'T UNDERSTAND WHICH BLOCK YOU MEAN.
YES. THE COLUMN NAMED CINDY.
THE COLUMN NAMED CINDY. OK.
YES. THE COLUMN NAMED CLANCY. 
THE COLUMN NAMED CINDY.
THE COLUMN NAMED CLANCY. I CAN'T.
THE COLUMN NAMED CLANCY. CLANCY, GOODBYE.
THE COLUMN NAMED CINDY. (1,3,7).
CINDY, GOODBYE.
BEN, GOODBYE.

提交要求

你需要提交一个zip压缩包，至少包含column.h/cpp、world.cpp。其余文件会在oj中自动贴入。

数据范围：

指令数不大于1000 积木数不大于100 涉及的所有xyz坐标为绝对值不大于1000的整数保证每个积木名称为各不相同的2-20位全大写英文字母字符串

时间限制：1s 空间限制：256MB

Clancy-Zhu commented 2 years ago

把模板包含在给定代码中就没有办法考到这个考点了，但是不包括模板的话应该有办法绕过……比较两难不含模板的版本 no_template.zip

hzhwcmhf commented 2 years ago

我觉得call_overlap的模板可以只给Box那个if。Column可以让大家填。我觉得题面甚至也可以提一下这个实现，普及一下关于dispatch的知识，让大家去拓展这个形式。（如果大家想自己另外实现，也不用卡）

其他的有几个问题

建议再加一种形状，比如底面是直角三角形的柱子，三个的话比较能说明拓展的复杂性
建议移除操作仅检查上方有没有积木，如果有的话，就不移除。这样更简洁，否则需要递归的移除上方积木，比较麻烦
bool函数return true和false，不要用0和1
Block里有个contain函数，目前我没明白是用在哪的。如果不需要可以去掉

Clancy-Zhu commented 2 years ago

感觉加入直角三角形过于复杂了……直角三角形和圆的重叠、直角三角形之间的重叠的判断都不好写 contain用来判断一个点是否在图形内其余的改动都已做好。

Clancy-Zhu commented 2 years ago

感觉增加形状工作量是几何级数增长……实在难以平衡我就考虑换题吧

hzhwcmhf commented 2 years ago

contain具体是在哪个函数里有使用？

加个圆锥也可以，只有两个形状用这个设计模式意义不大

Clancy-Zhu commented 2 years ago

contain可以直接在流程里调用（判断某坐标的积木）可以考虑增加圆锥/四棱锥？

hzhwcmhf commented 2 years ago

圆锥和四棱锥，两个选一个就行，可以设定为上面不能放东西。

数据麻烦分成几个部分

3个点只包含box，其中1个点比较短，和样例类似的
7个点包含所有形状，其中1个是样例

请将完整题面、数据（包括数据生成文件）、judger和答案程序，自行测试通过。完成之后发到邮箱 huangfei382@163.com。对于编写judger有问题可在小教员群（或找助教）讨论

JianGuanTHU / UOJ_Offline