program编程设计代做、代写Python留学生程序

日期：2021-03-24 10:40

Intro to Dear AI - Spring 2021

Homework 1

Burnt pancake problem

Due: Wednesday, March 24th

, 11:59 pm

In Short

Write a program that receives an order of 4 bottom-burnt pancakes and prints the

solution that BFS and A* search will find for going from the Start state to the Goal

(ordered pancakes and all burnt-side down).

Description

In this programming homework, you will work on a modified version of the classic

pancake problem that was discussed in the class. In this version, one side of each

pancake is burnt, and the pancakes must be sorted with all the burnt-side down. You

need to write a program that receives an arbitrary order of such 4 pancakes from the

user, plus the type of the search algorithm, and prints the steps that the specified

algorithm will take to reach the Goal state.

Format

Similar to the format described in class, each of the pancakes has an ID number that is

consistent with their size followed by a letter “w” or “b”. This way, the largest pancake

has an ID of 4, the next largest 3, the next 2, and the smallest has an ID of 1. The letter

“w” refers to the unburnt (white) side is up, and “b” shows that the burnt side is up. The

goal is to reach “1w2w3w4w”. Figure 1 shows an example of the IDs associated with

each pancake in a certain configuration.

Input

The input should consist of pairs of four digits and one character, a hyphen, and one

last character (#C#C#C#C-X), where the first digit indicates the ID of the top pancake

and the first character indicates whether if the burnt side is down (“w”) or not (“b”), the

second number indicates the second-highest pancake followed by a character, etc. The

last character (X) would be “b” or “a” characters, which refer to the Breadth-First (BFS)

or A* search algorithms respectively. The program should receive this variable as an

input from the user upon running the code.

Implementation

The cost associated with each flip is equal to the number of pancakes that are being

flipped. For instance, the cost of one flip between pancake 3b and 2b from the state

“4w1b2w3b” to “2b1w4b3b” is equal to 3 (spatula between 2 and 3). For each state, use

the same heuristic function (h(x)) that was discussed in the class: “the ID of the largest

pancake that is still out of place”. For BFS, you don’t need to consider a cost and a

heuristic function. Use the graph version of the algorithms, meaning that use some type

of list (closed set) to avoid visiting the nodes multiple times.

Add as many comments as you can to your code, so that it’s easy to understand your

implementation, including the role of functions, variables, etc. Specifically, make it clear

how your fringe is implemented and employed. Use an informative name for your fringe

and add comments where you define that.

Tie-Breaking

When needed for any of the search algorithms, use the following tie-breaking

mechanism:

"when there is a tie between two nodes, replace “w” with 1 and “b” with 0 to obtain an

eight-digit number. After that pick the node with a larger numerical ID chosen."

For instance, if there is a tie between 4b3w2b1b and 3w4w2b1b, then 4b3w2b1b will be

chosen as 40312010>31412010.

Output

Your program must print the steps that the specified algorithm (e.g., BFS) finds to solve

the problem, line by line. In other words, simply prints the solution that the algorithm

finds. For each state (except the final state), use the character “|” to show where the flip

to go to the next step happens. For A*, also print the value for the actual cost (function

g), and the value of the heuristic function (function h) in each step. The following is an

example of an input and output of the program.

Input:

1b2b3w4b-a # “a” indicates A*

Output: 1b2b|3w4b g:0, h:0

2w|1w3w4b g:2, h:2

2b1w3w4b| g:3, h:2

4w|3b1b2w g:7, h:4

4b3b1b2w| g:8, h:4

2b1w|3w4w g:12, h:2

1b|2w3w4w g:14, h:0

1w2w3w4w g:15, h:0

Note that the values for g and h correspond to the “current” state, and the character “|”

denotes the location of the flip for going to the “next” state.

Programming Language

At this point, our Moodle implementation only accepts Python.

Submitting Instructions

Follow this procedure for enrolling on the Moodle server:

● Go to https://quiz.cis.udel.edu/

● Select “CISC 681/481-21S-Beheshti” from the course list

● Enroll yourself as a student using the enrollment key: “dearai”

● Select the related assignment (Burnt Pancake)

● Click on the Edit tab and enter your program in the editor (tabbed

"hw1.py"). You can run and evaluate your code there. To evaluate your

code, you should first save the code and then click on evaluate.

● Your highest score before the deadline will be recorded as the proposed

grade. There’s no limitation on the number of submissions you can make.

The format of the input is as described above and you should enter input with the

same format while running the code. The program should only print the

requested output with the format described earlier.

Similarity Check

Please note that Moodle automatically checks for similarities between any submission

at any time that is related to this homework. The Collaboration and Cheating policy is

presented in our syllabus.

Grading

The total points will be 100. For each of the two requested search algorithms, you will

receive 50 points. The system will drop points per each failed test-case. For instance, if

there are 10 test-cases, you will lose 10 points per any wrong output.

Note that what you see on Moodle will be the “proposed grade.” Your submission can be

manually evaluated to ensure your code is actually solving the problems as requested.

To make understanding your code easier, you may want to use a different function for

each of the search algorithms, even if it needs copying the same piece of code and use

easily distinguishable names for your functions.

Questions?

Post them on Pizza. You can mention our TA @Mina Samizadeh for questions about

formatting and Moodle.

Final Note

Don’t start late! It might take you longer than you expect to finish the homework.

Some Other Examples

Example 1

Input: 1w2b3w4b-a

Output: 1w2b|3w4b g:0, h:0

2w|1b3w4b g:2, h:2

2b1b3w4b| g:3, h:2

4w|3b1w2w g:7, h:4

4b3b1w2w| g:8, h:4

2b1b|3w4w g:12, h:2

1w2w3w4w g:14, h:0

Example 2

Input: 1w2b3w4b-b

Output: 1w2b|3w4b

2w|1b3w4b

2b1b|3w4b

1w2w3w4b|

4w|3b2b1b

4b3b2b1b|

1w2w3w4w

Example 3

Input: 1b2b3w4b-a

Output: 1b2b|3w4b g:0, h:0

2w|1w3w4b g:2, h:2

2b1w3w4b| g:3, h:2

4w|3b1b2w g:7, h:4

4b3b1b2w| g:8, h:4

2b1w|3w4w g:12, h:2

1b|2w3w4w g:14, h:0

1w2w3w4w g:15, h:0

Example 4

Input: 1w2b3b4w-b

Output: 1w2b|3b4w

2w|1b3b4w

2b1b|3b4w

1w2w3b|4w

3w|2b1b4w

3b2b1b|4w

1w2w3w4w

Example 5

Input: 1b2w3b4b-a

Output: 1b2w3b4b| g:0, h:0

4w|3w2b1w g:4, h:4

4b3w|2b1w g:5, h:4

3b|4w2b1w g:7, h:4

3w4w|2b1w g:8, h:4

4b3b2b1w| g:10, h:4

1b|2w3w4w g:14, h:0

1w2w3w4w g:15, h:0