====== 01 Intro and Search I ======
We log on, discuss the rules, answer first questions, create first simple Python program.

Read about [[https://cyber.felk.cvut.cz/study/computer-labs/|computer labs]] how to set-up initial password, access home directory, links to other university services, ...

Reading about Python and programming essentials from the Programming Essentials course. [[https://cw.fel.cvut.cz/wiki/courses/be5b33kui/tutorials/start|Tutorials]] help with setting Python, discuss how to upload homework correctly, and add some class examples and some most frequent Python modules.

After solving the logging issues we will go into Objective Python. We will look into the environment you'll use to implement and deliver the algorithms you'll meet in the course. Python is well on-line documented/discussed, in case of problems, the internet is your friend.
However, be careful to read about the [[https://cw.fel.cvut.cz/wiki/help/common/plagiarism_cheating|plagiarism rules]] concerning your assignments uploads.

===== Exercise for bonus points: Optimal plane travel plan=====
  * Calculate the optimal travel plan of a plane
  * submit your solution to [[https://cw.felk.cvut.cz/brute/|BRUTE]] **lab01quiz** by February 20, midnight
  * format: text file, photo of your solution on paper, pdf - what is convenient for you
  * solution will be discussed on the next lab
  * 0.5 points
  * Students with their family name starting from A to K (included) have to solve and upload {{ :courses:be5b33kui:labs:weekly:plane_a_2023.pdf |subject A}} , while students with family name from L to Z have to solve and upload {{ :courses:be5b33kui:labs:weekly:plane_b_2023.pdf |subject B}}.

> {{page>courses:be5b33kui:internal:quizzes#Plane flight plan}}

===== Assignment: finding a way in a maze =====

In the State Space Search environment, find the cheapest path. Keep in mind that the cost of changing positions is not necessarily the same everywhere.

===== Getting to know the KUIMaze environment =====
   * Download and extract the {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze environment}}. Install the necessary python packages, see the ''How To'' section here: [[https://cw.fel.cvut.cz/b222/courses/be5b33kui/labs/search/start|Search (1st assignment)]]
   * Create a maze environment, i.e. an instance of the class ''kuimaze.InfEasyMaze'' with the map given by the image ''maps/easy_intro/easy_intro_1.bmp'':
<code python>
>>> import kuimaze
>>> MAP = 'maps/easy_intro/easy_intro_1.bmp'
>>> env = kuimaze.InfEasyMaze(map_image=MAP)</code>
  * Render the maze map with the ''render()'' method:
<code>
>>> env.render()
</code>
You should see the following image:
{{ :courses:b3b33kui:cviceni:program_po_tydnech:easy_intro_1.png?200 |}}
**Keep the image window open for now, don't close it!**
  * Try to guess what the ''reset()'' method does. Compare the result of the following call with the image of the maze:
<code>
>>> env.reset()
((1, 0, 0.0), (4, 2, 0.0))
</code>
  * Try to guess what the ''expand()'' method does:
<code>
>>> env.expand((1,0))
[[(2, 0), 1.0], [(0, 0), 1.0]]
</code>
  * Try calling ''env.render()'' again. Has the image changed in any way?
  * Examine ''easy_example.py'' and try to understand what is going on in it.
  * Try to construct the path from the start to the destination manually and modify the method ''Agent.find_path()'' so that it returns your hard-coded path.
  * Try submitting your agent to [[https://cw.felk.cvut.cz/brute/|BRUTE]] in task ''01-easy-search'', see below.

===== Search warm-up - optional task 01-easy_search =====
Although some of you might be impatient to jump to the implementation of the A* algorithm, try finding your way through a simple maze first. It is a smaller problem, easier for you to follow step-by-step and debug, and you will verify the correct handling of the environment on a simpler problem. The basic communication interface is the same, that is
<code python>
import kuimaze
MAP = 'maps/normal/normal9.bmp'
env = kuimaze.InfEasyMaze(map_image=MAP)
observation = env.reset() # returns start_pos, goal_pos
positions_with_costs = env.expand(position) # list of tuples (pos,cost), i.e. [(pos1, cost1),(pos2,cost2),...]
</code>
You will also submit the ''agent.py'' module, exactly according to the [[https://cw.fel.cvut.cz/b222/courses/be5b33kui/labs/search/start#agent_class_and_its_methods|specifications]] (name of the functions, input parameters, output format, etc).
Try different search strategies. If you write in a general enough way, the same code will work for the A* algorithm (the first mandatory assignment). You have to submit your work to the [[https://cw.felk.cvut.cz/brute/|upload system, BRUTE]], under ''01-easy_search''. The deadline is February 26 at midnight.


  * The following Python libraries may help you for searches in a tree: [[https://docs.python.org/3/library/queue.html|queue]] and [[https://docs.python.org/3.6/library/heapq.html|heapq]].


===== Mandatory Assignment: searching in a maze =====

This assignment is meant to implement an algorithm you'll see in the second lecture, A*, but if you can do the bonus "Easy Search" assignment fast enough and if you are used to Python, you can start working on the first mandatory assignment.

The full description of the assignment is here [[https://cw.fel.cvut.cz/b222/courses/be5b33kui/labs/search/start|Search (1st assignment)]]. In a maze environment, you will program the A* algorithm to find the shortest path. Do not forget that the cost of transition between different positions does not have to be the same.

===== Other =====
  * [[http://tristanpenman.com/demos/n-puzzle/|visualisation]] of different search algorithms demonstrated on the n-1 puzzle problem