-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path#maze_fun.ml#
269 lines (208 loc) · 11.6 KB
/
#maze_fun.ml#
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
#load "str.cma";;
(*
read_line (* reads from standard input *)
print_string (* writes to standard output *)
print_newline (* writes to standard output *)
*)
(* naive implementation -- always grabs first letter available (may grab same letter multiple times *)
let rec maze_robot = ()
let current_pos = ref (0,0)
let update_current_pos p = (fun c -> match c , !p with
| 'U' , (a,b) -> p := (a,b+1); p
| 'D' , (a,b) -> p := (a,b-1); p
| 'R' , (a,b) -> p := (a+1,b); p
| 'L' , (a,b) -> p := (a-1,b); p
)
let pos_visited = ref [(0,0)];;
let update_pos_visited p = (fun cp -> (p := (cp :: !p)); p);;
let rec visited_already pos_list pos = match pos_list with
| [] -> false
| h::t -> if (h = pos) then true else (we_visited_already t pos)
let havent_visited_yet pos_list pos = not (we_visited_already pos_list pos)
let letters_caught = ref []
let remove_first_letter = (fun s -> String.sub s 1 ((String.length s) - 1))
let rec string_to_list_of_chars = (fun s ->
match s with
| "" -> []
| _ -> (String.get s 0) :: (string_to_list_of_chars (remove_first_letter s)))
let rec there_is_a_letter_we_can_move_to = (fun s -> match (string_to_list_of_chars (remove_first_letter s)) with
| [] -> false
| h :: t -> if (h = '#' || h = ' ') then (there_is_a_letter_we_can_move_to (remove_first_letter s))
else
true)
let rec join l1 l2 = match l1, l2 with
| [], [] -> []
| h1::t1, h2::t2 -> (h1,h2) :: join t1 t2;;
let view_to_tuples current_view =
let l1 = string_to_list_of_chars (remove_first_letter current_view) in
let l2 = ['U';'D';'L';'R'] in
join l2 l1;;
(* method below moves to first new square available --> looks Up, then down, then left then right *)
let rec make_new_move view_tuples current_pos pos_list = match view_tuples, !current_pos with
| [], _ -> 'K' (* no new move available *)
| (_,'#') :: t , _ -> make_new_move t current_pos pos_list
| ('U',char) :: t , (x,y) -> if (havent_visited_yet !pos_list (x,y+1)) then 'U'
else make_new_move t current_pos pos_list
| ('D',char) :: t , (x,y) -> if (havent_visited_yet !pos_list (x,y-1)) then 'D'
else make_new_move t current_pos pos_list
| ('L',char) :: t , (x,y) -> if (havent_visited_yet !pos_list (x-1,y)) then 'L'
else make_new_move t current_pos pos_list
| ('R',char) :: t , (x,y) -> if (havent_visited_yet !pos_list (x+1,y)) then 'R'
else make_new_move t current_pos pos_list
let check_if_sitting_on_letter = (fun s -> match (String.get s 0) with
| '#' -> (letters_caught := !letters_caught)
| ' ' -> (letters_caught := !letters_caught)
| _ -> (letters_caught := ((String.get s 0) :: !letters_caught)))
let move_to_first_available_letter = (fun s ->
let rec aux s moves_left = match (string_to_list_of_chars s), moves_left with
| h1 :: t1 , h2 :: t2 -> if (h1 = '#' || h1 = ' ') then (aux (remove_first_letter s) t2)
else
h2
in aux (remove_first_letter s) ['U';'D';'L';'R'] )
let move_to_first_available_space = (fun s ->
let rec aux s moves_left = match (string_to_list_of_chars s), moves_left with
| h1 :: t1 , h2 :: t2 -> if (h1 = '#') then (aux (remove_first_letter s) t2)
else
h2
in aux (remove_first_letter s) ['U';'D';'L';'R'] )
let make_naive_move = (fun s -> (check_if_sitting_on_letter s); if (there_is_a_letter_we_can_move_to s) then (move_to_first_available_letter s)
else
(move_to_first_available_space s))
(*
let make_even_better_move current_pos current_view pos_list =
check_if_sitting_on_letter current_view;
move_to_all_new_locations
*)
let sort_char_list_alphabetically = ()
let concatenate_list = ()
(* testing *)
let maze_3_4 = ['#';'#';'#';'#';
'#';'A';'B';'#';
'#';'#';'#';'#']
let rec get_kth_element_from_list list = (fun k -> match k, list with
| 1, h :: t -> h
| _, h :: t-> get_kth_element_from_list t (k-1))
let k_3_4 = get_kth_element_from_list maze_3_4
let current_3_by_4_view_letters = ref ['A';'#';'#';'#';'B'] (* positions [6; 2; 10; 5; 7] in 3_by_4 maze *)
let current_3_by_4_view_positions = ref [6;2;10;5;7]
let update_3_by_4_view_positions c move = match move with
| 'U' -> c := [((get_kth_element_from_list !current_3_by_4_view_positions 1)-4);
((get_kth_element_from_list !current_3_by_4_view_positions 2)-4);
((get_kth_element_from_list !current_3_by_4_view_positions 3)-4);
((get_kth_element_from_list !current_3_by_4_view_positions 4)-4);
((get_kth_element_from_list !current_3_by_4_view_positions 5)-4)]
| 'D' -> c := [((get_kth_element_from_list !current_3_by_4_view_positions 1)+4);
((get_kth_element_from_list !current_3_by_4_view_positions 2)+4);
((get_kth_element_from_list !current_3_by_4_view_positions 3)+4);
((get_kth_element_from_list !current_3_by_4_view_positions 4)+4);
((get_kth_element_from_list !current_3_by_4_view_positions 5)+4)]
| 'L' -> c := [((get_kth_element_from_list !current_3_by_4_view_positions 1)-1);
((get_kth_element_from_list !current_3_by_4_view_positions 2)-1);
((get_kth_element_from_list !current_3_by_4_view_positions 3)-1);
((get_kth_element_from_list !current_3_by_4_view_positions 4)-1);
((get_kth_element_from_list !current_3_by_4_view_positions 5)-1)]
| 'R' -> c := [((get_kth_element_from_list !current_3_by_4_view_positions 1)+1);
((get_kth_element_from_list !current_3_by_4_view_positions 2)+1);
((get_kth_element_from_list !current_3_by_4_view_positions 3)+1);
((get_kth_element_from_list !current_3_by_4_view_positions 4)+1);
((get_kth_element_from_list !current_3_by_4_view_positions 5)+1)]
let update_3_by_4_view_letters = (fun c ->
c := [k_3_4 (get_kth_element_from_list !current_3_by_4_view_positions 1);
k_3_4 (get_kth_element_from_list !current_3_by_4_view_positions 2);
k_3_4 (get_kth_element_from_list !current_3_by_4_view_positions 3);
k_3_4 (get_kth_element_from_list !current_3_by_4_view_positions 4);
k_3_4 (get_kth_element_from_list !current_3_by_4_view_positions 5);
])
let rec list_of_chars_to_string clist =
match clist with
| [] -> ""
| h :: t -> (String.make 1 (get_kth_element_from_list clist 1)) ^ (list_of_chars_to_string t);;
let update_view = (fun m -> (update_3_by_4_view_positions current_3_by_4_view_positions m);
update_3_by_4_view_letters current_3_by_4_view_letters; list_of_chars_to_string !current_3_by_4_view_letters)
let starting_view = "A###B"
let current_view = list_of_chars_to_string !current_3_by_4_view_letters;;
let rec sort lst =
match lst with
[] -> []
| head :: tail -> insert head (sort tail)
and insert elt lst =
match lst with
[] -> [elt]
| head :: tail -> if elt <= head then elt :: lst else head :: insert elt tail
let end_game () = "K" ^ (list_of_chars_to_string (sort(!letters_caught)))
(* to reset *)
(current_pos := (0,0); pos_visited := [(0,0)];
current_3_by_4_view_positions := [6;2;10;5;7];
current_3_by_4_view_letters := ['A';'#';'#';'#';'B'];
letters_caught := []);;
let rec lets_play current_view current_pos pos_visited =
check_if_sitting_on_letter current_view;
let move = (make_new_move (view_to_tuples current_view) current_pos pos_visited) in
if move = 'K' then Printf.printf "%s\n%!" (end_game ()) else
(Printf.printf "%s\n%!" current_view;
Printf.printf "%c\n%!" move;
let cp = (update_current_pos current_pos move) in
let pv = (update_pos_visited pos_visited !cp) in
lets_play (update_view move) cp pv)
let start_game () = lets_play starting_view current_pos pos_visited
(* to do
1. implement general solution algorithm
2. create function to sort and return character trophies
*)
(* testing slightly harder maze *)
let maze_6_13 = ['#';'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';
'#';' ';' ';' ';'A';' ';' ';' ';'#';' ';' ';' ';'#';
'#';' ';'#';'#';' ';'#';'#';' ';'#';' ';'#';' ';'#';
'#';' ';'Q';'#';' ';'#';' ';' ';' ';'B';' ';' ';'#';
'#';' ';' ';'#';'A';'#';' ';'#';' ';'#';'#';'#';'#';
'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';'#';]
let k_6_13 = get_kth_element_from_list maze_6_13
let current_6_by_13_view_letters = ref ['A';'#';' ';' ';' '] (* positions [18; 5; 31; 17; 19;] in 6_by_13 maze *)
let current_6_by_13_view_positions = ref [18;5;31;17;19]
let update_6_by_13_view_positions c move = match move with
| 'U' -> c := [((get_kth_element_from_list !current_6_by_13_view_positions 1)-13);
((get_kth_element_from_list !current_6_by_13_view_positions 2)-13);
((get_kth_element_from_list !current_6_by_13_view_positions 3)-13);
((get_kth_element_from_list !current_6_by_13_view_positions 4)-13);
((get_kth_element_from_list !current_6_by_13_view_positions 5)-13)]
| 'D' -> c := [((get_kth_element_from_list !current_6_by_13_view_positions 1)+13);
((get_kth_element_from_list !current_6_by_13_view_positions 2)+13);
((get_kth_element_from_list !current_6_by_13_view_positions 3)+13);
((get_kth_element_from_list !current_6_by_13_view_positions 4)+13);
((get_kth_element_from_list !current_6_by_13_view_positions 5)+13)]
| 'L' -> c := [((get_kth_element_from_list !current_6_by_13_view_positions 1)-1);
((get_kth_element_from_list !current_6_by_13_view_positions 2)-1);
((get_kth_element_from_list !current_6_by_13_view_positions 3)-1);
((get_kth_element_from_list !current_6_by_13_view_positions 4)-1);
((get_kth_element_from_list !current_6_by_13_view_positions 5)-1)]
| 'R' -> c := [((get_kth_element_from_list !current_6_by_13_view_positions 1)+1);
((get_kth_element_from_list !current_6_by_13_view_positions 2)+1);
((get_kth_element_from_list !current_6_by_13_view_positions 3)+1);
((get_kth_element_from_list !current_6_by_13_view_positions 4)+1);
((get_kth_element_from_list !current_6_by_13_view_positions 5)+1)]
let update_6_by_13_view_letters = (fun c ->
c := [k_6_13 (get_kth_element_from_list !current_6_by_13_view_positions 1);
k_6_13 (get_kth_element_from_list !current_6_by_13_view_positions 2);
k_6_13 (get_kth_element_from_list !current_6_by_13_view_positions 3);
k_6_13 (get_kth_element_from_list !current_6_by_13_view_positions 4);
k_6_13 (get_kth_element_from_list !current_6_by_13_view_positions 5);
])
let starting_view_h = "A# "
let current_view_h = list_of_chars_to_string !current_6_by_13_view_letters;;
(* to reset *)
(current_pos := (0,0); pos_visited := [(0,0)];
current_6_by_13_view_positions := [18;5;31;17;19];
current_6_by_13_view_letters := ['A';'#';' ';' ';' '];
letters_caught := []);;
let update_view1 = (fun m -> (update_6_by_13_view_positions current_6_by_13_view_positions m);
update_6_by_13_view_letters current_6_by_13_view_letters; list_of_chars_to_string !current_6_by_13_view_letters)
let rec lets_play_harder current_view current_pos pos_visited =
check_if_sitting_on_letter current_view;
let move = (make_new_move (view_to_tuples current_view) current_pos pos_visited) in
if move = 'K' then Printf.printf "%s\n%!" (end_game ()) else
(Printf.printf "%s\n%!" current_view;
Printf.printf "%c\n%!" move;
let cp = (update_current_pos current_pos move) in
let pv = (update_pos_visited pos_visited !cp) in
lets_play_harder (update_view1 move) cp pv)
let start_game1 () = lets_play_harder starting_view_h current_pos pos_visited