Assignment 1 Solution

Microproject
Write a small C program which holds the locations of items on a shelving unit. Specifically, your program should:
    • Contain a struct representing an item on the shelf. It needs only contain the item’s name and price.
    • Ask the user for the number of shelves in the unit, and the number of “slots” available on each shelf which can hold items.
    • From the above, build a two dimensional array of item structs. The array represents locations on the shelving unit (rows = shelves, columns = locations on the shelves).
    • Allow the user to add items to the shelves by giving the name, price, and location.
    • Allow the user to indicate they are done adding items. At this point the user should be able to enter the coordinate of an item in the shelving unit and the program should print out the information about the selected item (or some message if that slot is empty).
Main Project
In this assignment you will implement a Turing Machine (TM) in C. A TM consists of:
    • An infinite tape, divided into cells
    • A read/write head which traverses along the tape, capable of reading the current cell, writing a new value in the current cell, and moving left or right
    • A state register
    • A finite table of instructions which, given the current state of the machine, and the value in the tape cell currently being read, tells the machine to: 
        1. Write some (possibly the same) item into the cell
        2. Move the head left or right one cell
        3. Change to some (possibly the same) state
To represent the tape, you will implement a doubly linked list. As you move the tape head, you will update a pointer to the current cell seen by the tape head. Initial tape contents will be provided by an input file. If you need more cells during processing you should create them on the fly. You may use the ASCII character ‘B’ to indicate a blank cell.
The set of instructions will also be provided in the input file. In order to represent these in your program, create a two-dimensional array, where the rows indices are states and the columns indices are all ASCII characters (i.e., there should always be 255 columns). Given the current state and the current character being read by the read/write head, the machine looks up an instruction in this array. For example, if the machine is in state 1, reading a ‘B’ from the tape it should access [1][‘B’] in the array. The instruction at that position will tell the machine what value to write, what direction to move, and what the new state should be. (In the below example, this would be to write a ‘B’, move left, and change to state 2).
Below is a sample input file which adds two unary numbers together. Given an initial tape input of 111B1111, representing the numbers 3 and 4 separated by a blank, the machine walks to the end of the tape, changing the middle B to a 1, and changing the last 1 to a B. The result is 1111111, unary 7. 
1
2
3
4
5
6
7
8
9
10
11
111B1111
5
0
4
0 1 1 R 0
0 B 1 R 1
1 1 1 R 1
1 B B L 2
2 1 B L 3
3 1 1 L 3
3 B B R 4

The input file has the following specification:
Line 1: Initial tape content
Line 2: Number of states
Line 3: Start state
Line 4: End state
Remaining lines represent the state machine. Each line is has 5 parts:
State, ReadVal, WriteVal, MoveDirection, NewState
Remember that your program should work for any input file which represents a Turing Machine in this format, with any number of states.
Your program should take a single command line argument, the name of the file to be read.
Given the above input file, the program should output unary 7, with some blanks on each end of the tape. My version produces the following:
1
2
3
4
Input file: input_test_1
Writing tape…
Initial tape contents: 111B1111
Final tape contents: B1111111BB

You may use any built-in C library functions in your program, but you must implement the doubly linked list yourself. You may not use code found on the internet.
Simulation, in Detail
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
State 0
111B1111
^         
Write 1, Move R, New State 0
------------
State 0
111B1111
^
Write 1, Move R, New State 0
------------
State 0
111B1111
  ^
Write 1, Move R, New State 0
------------
State 0
111B1111
   ^
Write 1, Move R, New State 1
------------
State 1
11111111
    ^
Write 1, Move R, New State 1
------------
State 1
11111111
     ^
Write 1, Move R, New State 1
------------
State 1
11111111
      ^
Write 1, Move R, New State 1
------------
State 1
11111111
       ^
Write 1, Move R, New State 1
------------
State 1
11111111B
        ^
Write B, Move L, New State 2
------------
State 2
11111111B
       ^
Write B, Move L, New State 3
------------
State 3
1111111BB
      ^
Write 1, Move L, New State 3
------------
State 3
1111111BB
     ^
Write 1, Move L, New State 3
------------
State 3
1111111BB
    ^
Write 1, Move L, New State 3
------------
State 3
1111111BB
   ^
Write 1, Move L, New State 3
------------
State 3
1111111BB
  ^
Write 1, Move L, New State 3
------------
State 3
1111111BB
^
Write 1, Move L, New State 3
------------
State 3
1111111BB
^
Write 1, Move L, New State 3
------------
State 3
B1111111BB
^
Write B, Move R, New State 4
------------
State 4
B1111111BB
^
Halt.

Notes and Tips
    • Be sure to put your name at the top of your source file.
    • If you’re careful, you can use fscanf for reading from the input file. Better would be fgets then sscanf.
    • Remember to differentiate between characters representing numbers (e.g., ‘1’) and numbers themselves (e.g., 1).