Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Introduction

Computers conventionally represent colour using the RGB format. Using the 6-bit RGB scheme for example, a single colour can be represented as a string of 6 binary digits. The colour orange could be represented as the string 111000, where 11 is the red value, 10 is the green value and 00 is the blue value.

Unfortunately, the university printers are having trouble printing out a large range of colours. On top of this, the IT department have all called in sick leaving nobody but you to solve our problem. Luckily, there are many colours that appear close enough to the ones that we cannot print. We denote the set of colours that can be printed as LEGAL.

Our goal is to find a sequence of steps that converts a starting colour that is not in LEGAL to a colour that is in LEGAL. Within each step, we may flip one binary digit of the current colour. For example, in one step we may change from colour 111000 to 111010 by flipping the 5th digit. However, there is a catch. If any step ends in a certain set of colours, our printer crashes! We denote this set of colours as UNSAFE. We want to avoid any step that produces a colour in UNSAFE.

Broken Printer

Write a program to find solutions to the problem of converting a starting colour in the k-bit colour format to a LEGAL colour using the following 6 search strategies: BFS, DFS, IDS, Greedy, A*, and Hill-climbing. Here, k can be any integer from 3 to 12 inclusive. Use the smallest Hamming distance from any LEGAL colour for the heuristic in Greedy and A* search, and as an evaluation function in hill-climbing algorithms.

You will need to adhere to the following constraints:

2. When expanding a node, generate its children in ascending order of the index being flipped. i.e. The first child generated has the 1st bit from the left flipped, and the last child generated has the k-th bit from the left flipped.

3. For the heuristic search strategies and the hill-climbing algorithm, if two or more nodes have the same priority for expansion, expand the oldest of those nodes.

As your program will be automatically tested, it is important that you adhere to these strict rules for program input and output.

Input

The input file format is described below.

For example, the input file “simple.txt” might contain:

Here, the X denotes that both 111 and 110 are in UNSAFE. The X character can only appear in legal-state and unsafe-state inputs. Additionally, more than one X may be present in an input. Your program should also be able to automatically determine k, the bit-depth of the colour from the inputs. You may assume that all input files are valid input files.

Output

Your program will produce a two-line input:

Line 1

This line should express the path found to the solution, beginning with the start state and finishing at a goal state. The path is a sequence of binary strings separated by commas. If the maximum expanded nodes are reached or if there are no more nodes to expand but a goal-state has not been reached, write the line “SEARCH FAILED”.