 |
|
| 이전 주제 보기 :: 다음 주제 보기 |
| 글쓴이 |
메시지 |
tjdals4565
가입: 2014년 9월 7일
올린 글: 14
|
 올려짐: 2014년11월26일 14:27 주제: 튜링 테스트케이스 만들어보았습니다 |
 |
|
| 코드: |
#use "hw7_1.ml"
open TuringMachine
let rec run_your_tm_by_step tm size =
match step_tm tm with
| None -> print_endline (print_tm tm size)
| Some n -> print_endline (print_tm tm size);run_your_tm_by_step n size
let run_your_tm tm size =
print_endline (print_tm (run_tm tm) size)
let range top bottom =
let rec iter i ans =
if i = top + 1 then ans else iter (i+1) (i::ans)
in iter bottom []
let rangeup bottom top =
let rec iter i ans =
if i = bottom-1 then ans else iter (i-1) (i::ans)
in iter top []
let make id sym write move lst =
List.map (fun i -> (id^(string_of_int i),sym,Write write,move,id^(string_of_int (i-1)))) lst
let makeup id sym write move lst =
List.map (fun i -> (id^(string_of_int i),sym,Write write,move,id^(string_of_int (i+1)))) lst
let explode s = List.map (fun i -> String.sub s i 1) (rangeup 0 (String.length s - 1))
let printfrom st sym s whatever =
(st,sym,Write sym,Right,s^"0")::
(List.flatten (List.map (fun (st,_,todo,move,newst) -> (List.map (fun wh -> (st,wh,todo,move,newst)) whatever))
(List.map (fun i -> (s ^ (string_of_int i),"whatever",Write (String.sub s i 1),Right,s ^ (string_of_int (i+1)))) (rangeup 0 (String.length s - 1))))
)
let _ = print_endline ("Insert a number for primality test")
let n = int_of_string (read_line ())
let rules1 =
[("start","-",Write "#",Right,"sr"^(string_of_int (n-1)))]@
(make "sr" "-" "-" Right (range (n-1) 1))@
[("sr0","-",Write "X",Right,"ssr"^(string_of_int n))]@
(make "ssr" "-" "O" Right (range n 1))@
[("ssr0","-",Write "-",Left,"leftuntil")]@
[("leftuntil","-",Write "-",Left,"leftuntil")]@
[("leftuntil","X",Write "X",Left,"leftuntil")]@
[("leftuntil","O",Write "O",Left,"leftuntil")]@
[("leftuntil","#",Write "2",Right,"2div1")]@
(List.map (fun i -> ("leftuntil", string_of_int i, Write (string_of_int (i+1)), Right, (string_of_int (i+1))^"div"^(string_of_int i))) (rangeup 2 (n-2)))@
[("leftuntil",string_of_int (n-1),Write "done",Stay,"IsPrime")]
let rules2 =
(List.flatten
(List.map (fun (st,_,_,_,newst) -> [(st,"-",Write "-",Right,newst);(st,"X",Write "X",Right,newst);(st,"O",Write "O",Right,newst)])
(List.flatten
(
List.map
(fun k ->
List.map
(fun j -> (string_of_int k ^ "div" ^ (string_of_int j),"-","-",Right,string_of_int k ^ "div" ^ (string_of_int (j-1))))
(range (k-1) 1)
)
(rangeup 2 (n-1))
))))
let rules3 =
(List.flatten
(List.map
(fun k -> [(string_of_int k ^ "div0","-",Write "-",Right,string_of_int k ^ "div" ^ (string_of_int (k-1)));
(string_of_int k ^ "div0","O",Write "O",Left,"leftuntil");
(string_of_int k ^ "div0","X",Write "X",Stay,"IsNotPrime")])
(rangeup 2 (n-1))
))@
(printfrom "IsPrime" "done" (string_of_int n ^ " is prime") ["-";"X";"O"])@
(printfrom "IsNotPrime" "X" (string_of_int n ^ " is not prime") ["-";"X";"O"])
let rules = rules1@rules2@rules3
let tm = make_tm [] "start" rules ;;
run_your_tm_by_step tm 20
|
ocaml test.ml 라고 쳐서 실행한 후에
숫자를 입력하면 (2보다는 크게해주세요 ㅠ)
여러분의 튜링머신이 소수판별을 해줍니다 |
|
| 위로 |
|
 |
홍선기
가입: 2014년 9월 29일
올린 글: 11
|
| 올려짐: 2014년11월26일 15:42 주제: ㅠㅠ |
|
|
과제의 그레이더는 통과하는데 구현방식에 따라서 이 테스트 케이스는 통과하지 못할 수 있나요?
-.-.-.-.-.-.-.-.-.-.-.-.-만 출력되고 무한루프에 빠지네요 |
|
| 위로 |
|
|
tjdals4565
가입: 2014년 9월 7일
올린 글: 14
|
| 올려짐: 2014년11월26일 15:51 주제: |
|
|
음.. 코드에서 가져다 쓰는건 step_tm 이랑 run_tm 이랑 print_tm 밖에 없는데요..
너무 큰 수를 입력하면 -.-.-.-.- ... 가 한동안 계속될 수 있습니다 |
|
| 위로 |
|
|
tjdals4565
가입: 2014년 9월 7일
올린 글: 14
|
| 올려짐: 2014년11월26일 16:31 주제: |
|
|
ㅋㅋㅋ 참고로 중간에 O X 뜨는건 신경쓰실 필요 없습니다
그건 튜링의 계산과정일뿐이고
모든 것이 끝나고 맨 마지막줄에 소수라고 출력되는지 아니라고 출력되는지만 보시면 됩니다.. |
|
| 위로 |
|
|
오평석
가입: 2014년 10월 17일
올린 글: 8
|
| 올려짐: 2014년11월26일 17:01 주제: |
|
|
이전 과제 때 게시판에 올라온 테스트케이스들을 ml 형식에 맞게 수정하여 덧붙여봅니다.
https://ropas.snu.ac.kr/phpbb/viewtopic.php?t=4583
이번에도 눈으로 보고 옮긴 거라 틀렸을 수 있으니, 같이 확인해보아요 
| 코드: | ocaml *.cmo [이 파일 이름]
|
사용법은 기존 self-grader처럼 사용하면 됩니다.
| 코드: | open CommonGrade
open Hw7_1
(* Tape *)
let _ = print_endline "Tape"
let tape1 = TuringMachine.init_tape ["a";"b"]
let tape2 = TuringMachine.move_tape_left tape1
let tape3 = TuringMachine.move_tape_left tape2
let tape4 = TuringMachine.move_tape_right tape3
let tape5 = TuringMachine.move_tape_right tape4
let tape6 = TuringMachine.move_tape_right tape5
let tape7 = TuringMachine.write_tape tape6 "c"
let tape8 = TuringMachine.move_tape_right tape7
let tape9 = TuringMachine.move_tape_right tape8
let tape10 = TuringMachine.move_tape_right tape9
let tape11 = TuringMachine.write_tape tape10 "_"
let tape12 = TuringMachine.move_tape_left tape11
let tape13 = TuringMachine.move_tape_left tape12
let tape14 = TuringMachine.write_tape tape13 "d"
let tape15 = TuringMachine.move_tape_left tape14
let _ = output (fun () -> "-.-.a.b.-" = (TuringMachine.print_tape tape1 2))
let _ = output (fun () -> "-.a.b.-.-" = (TuringMachine.print_tape tape2 2))
let _ = output (fun () -> "a.b.-.-.-" = (TuringMachine.print_tape tape3 2))
let _ = output (fun () -> "-.a.b.-.-" = (TuringMachine.print_tape tape4 2))
let _ = output (fun () -> "-.-.a.b.-" = (TuringMachine.print_tape tape5 2))
let _ = output (fun () -> "-.-.-.a.b" = (TuringMachine.print_tape tape6 2))
let _ = output (fun () -> "-.-.c.a.b" = (TuringMachine.print_tape tape7 2))
let _ = output (fun () -> "-.-.-.-.-.-.-.-.c.a.b.-.-.-.-" = (TuringMachine.print_tape tape8 7))
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.c.a.b.-.-.-" = (TuringMachine.print_tape tape9 7))
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.-.c.a.b.-.-" = (TuringMachine.print_tape tape10 7))
let _ = output (fun () -> "-.-.-.-.-.-.-._.-.-.c.a.b.-.-" = (TuringMachine.print_tape tape11 7))
let _ = output (fun () -> "-.-.-.-.-.-._.-.-.c.a.b.-.-.-" = (TuringMachine.print_tape tape12 7))
let _ = output (fun () -> "-.-.-.-.-._.-.-.c.a.b.-.-.-.-" = (TuringMachine.print_tape tape13 7))
let _ = output (fun () -> "-.-.-.-.-._.-.d.c.a.b.-.-.-.-" = (TuringMachine.print_tape tape14 7))
let _ = output (fun () -> "-.-.-.-._.-.d.c.a.b.-.-.-.-.-" = (TuringMachine.print_tape tape15 7))
let _ = output (fun () -> "-.-.-.-.-.-.-.a.b.c.d.e.-.-.-" = (TuringMachine.print_tape (TuringMachine.init_tape ["a";"b";"c";"d";"e"]) 7))
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.-.-.-.-.-.-" = (TuringMachine.print_tape (TuringMachine.init_tape []) 7))
let _ = output (fun () -> "a" = (TuringMachine.read_tape tape1))
let _ = output (fun () -> "b" = (TuringMachine.read_tape tape2))
let _ = output (fun () -> "c" = (TuringMachine.read_tape tape7))
let _ = output (fun () -> "_" = (TuringMachine.read_tape tape11))
let _ = output (fun () -> "-" = (TuringMachine.read_tape tape12))
let _ = output (fun () -> "c" = (TuringMachine.read_tape tape15))
let _ = output (fun () -> "-" = (TuringMachine.read_tape (TuringMachine.init_tape [])))
let _ = output (fun () -> "a" = (TuringMachine.read_tape (TuringMachine.init_tape ["a";"b";"c";"d";"e"])))
(* Rule table *)
let _ = print_endline "Rule table"
let table =
[("1","a",TuringMachine.Write "d",TuringMachine.Right,"2");
("2","b",TuringMachine.Write "e",TuringMachine.Right,"3");
("3","-",TuringMachine.Write "b",TuringMachine.Left,"4");
("4","e",TuringMachine.Write "a",TuringMachine.Left,"5");
("5","d",TuringMachine.Write "c",TuringMachine.Left,"6");
("6","-",TuringMachine.Write "c",TuringMachine.Stay,"7");
("1","c",TuringMachine.Write "d",TuringMachine.Left,"4");
("3","a",TuringMachine.Write "c",TuringMachine.Stay,"1");
("6","a",TuringMachine.Erase, TuringMachine.Right,"3");
("2","c",TuringMachine.Write "a",TuringMachine.Stay,"2");
("2","d",TuringMachine.Write "b",TuringMachine.Right,"3");
("2","a",TuringMachine.Write "c",TuringMachine.Left,"1");
("3","b",TuringMachine.Write "a",TuringMachine.Right,"4");
("3","c",TuringMachine.Write "b",TuringMachine.Left,"2");
("3","d",TuringMachine.Write "a",TuringMachine.Stay,"7");
("7","a",TuringMachine.Write "b",TuringMachine.Left,"4");
("7","b",TuringMachine.Erase, TuringMachine.Right,"2");
("7","c",TuringMachine.Write "a",TuringMachine.Stay,"3");
("4","a",TuringMachine.Write "d",TuringMachine.Left,"2");
("4","c",TuringMachine.Write "e",TuringMachine.Left,"1");
("4","b",TuringMachine.Erase, TuringMachine.Stay,"3");
("5","a",TuringMachine.Write "b",TuringMachine.Right,"2");
("5","b",TuringMachine.Write "a",TuringMachine.Left,"3");
("5","-",TuringMachine.Write "c",TuringMachine.Stay,"4");
("2","-",TuringMachine.Write "a",TuringMachine.Right,"3");
("4","d",TuringMachine.Write "c",TuringMachine.Right,"2");
("4","-",TuringMachine.Write "b",TuringMachine.Left,"2")]
let _ = output (fun () ->
Some (TuringMachine.Write "d",TuringMachine.Right,"2") =
TuringMachine.match_rule "1" "a" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "e",TuringMachine.Right,"3") =
TuringMachine.match_rule "2" "b" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "b",TuringMachine.Left,"4") =
TuringMachine.match_rule "3" "-" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "a",TuringMachine.Left,"5") =
TuringMachine.match_rule "4" "e" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "c",TuringMachine.Left,"6") =
TuringMachine.match_rule "5" "d" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "c",TuringMachine.Stay,"7") =
TuringMachine.match_rule "6" "-" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "c",TuringMachine.Stay,"1") =
TuringMachine.match_rule "3" "a" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "a",TuringMachine.Stay,"2") =
TuringMachine.match_rule "2" "c" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "c",TuringMachine.Left,"1") =
TuringMachine.match_rule "2" "a" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "c",TuringMachine.Stay,"4") =
TuringMachine.match_rule "5" "-" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "e",TuringMachine.Left,"1") =
TuringMachine.match_rule "4" "c" table
)
let _ = output (fun () ->
Some (TuringMachine.Write "b",TuringMachine.Left,"4") =
TuringMachine.match_rule "7" "a" table
)
(* Turaing machine *)
let _ = print_endline "Turing machine"
let rec step_n : int -> TuringMachine.tm -> TuringMachine.tm option =
fun n tm ->
if n > 0
then
(match TuringMachine.step_tm tm with
| Some tm' -> step_n (n-1) tm'
| None -> None)
else Some tm
let tm1 = TuringMachine.make_tm ["a";"b"] "1" table
let tm2_opt = step_n 1 tm1
let tm3_opt = step_n 2 tm1
let tm4_opt = step_n 3 tm1
let tm5_opt = step_n 4 tm1
let tm6_opt = step_n 5 tm1
let tm7_opt = step_n 6 tm1
let tm8_opt = step_n 7 tm1
let tm9_opt = step_n 8 tm1
let tm10_opt = step_n 9 tm1
let tm11_opt = step_n 10 tm1
let tm12_opt = step_n 11 tm1
let tm13_opt = step_n 12 tm1
let tm14_opt = step_n 13 tm1
let tm15_opt = step_n 14 tm1
let tm_run = TuringMachine.run_tm tm1
let tm_run2 = TuringMachine.run_tm tm1
let tm_run3 = TuringMachine.run_tm tm1
let tm_run4 = TuringMachine.run_tm tm1
let _ = output (fun () -> "-.-.a.b.-" = TuringMachine.print_tm tm1 2)
let _ = output (fun () ->
(match tm2_opt with
| Some tm2 -> "-.d.b.-.-" = TuringMachine.print_tm tm2 2
| None -> false
))
let _ = output (fun () ->
(match tm3_opt with
| Some tm3 -> "d.e.-.-.-" = TuringMachine.print_tm tm3 2
| None -> false
))
let _ = output (fun () ->
(match tm4_opt with
| Some tm4 -> "-.d.e.b.-" = TuringMachine.print_tm tm4 2
| None -> false
))
let _ = output (fun () ->
(match tm5_opt with
| Some tm5 -> "-.-.d.a.b" = TuringMachine.print_tm tm5 2
| None -> false
))
let _ = output (fun () ->
(match tm6_opt with
| Some tm6 -> "-.-.-.c.a" = TuringMachine.print_tm tm6 2
| None -> false
))
let _ = output (fun () ->
(match tm7_opt with
| Some tm7 -> "-.-.c.c.a" = TuringMachine.print_tm tm7 2
| None -> false
))
let _ = output (fun () ->
(match tm8_opt with
| Some tm8 -> "-.-.-.-.-.-.-.a.c.a.b.-.-.-.-" = TuringMachine.print_tm tm8 7
| None -> false
))
let _ = output (fun () ->
(match tm9_opt with
| Some tm9 -> "-.-.-.-.-.-.-.c.c.a.b.-.-.-.-" = TuringMachine.print_tm tm9 7
| None -> false
))
let _ = output (fun () ->
(match tm10_opt with
| Some tm10 -> "-.-.-.-.-.-.-.-.d.c.a.b.-.-.-" = TuringMachine.print_tm tm10 7
| None -> false
))
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.-.-.c.d.d.c.a.b.-.-.-.-" = TuringMachine.print_tm tm_run 10)
(* If no rule is applicable, just do nothing. *)
let tm16_opt = step_n 1 tm_run
let _ = output (fun () ->
(match tm16_opt with
| Some _ -> false
| None -> true
))
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.-.-.c.d.d.c.a.b.-.-.-.-" = TuringMachine.print_tm tm_run2 10)
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.-.-.c.d.d.c.a.b.-.-.-.-" = TuringMachine.print_tm tm_run3 10)
let _ = output (fun () -> "-.-.-.-.-.-.-.-.-.-.-.c.d.d.c.a.b.-.-.-.-" = TuringMachine.print_tm tm_run4 10)
|
|
|
| 위로 |
|
|
홍선기
가입: 2014년 9월 29일
올린 글: 11
|
| 올려짐: 2014년11월26일 18:55 주제: d |
|
|
| 두번째 테스트 케이스는 다 잘 나오지만 소수 튜링기계는 여전히 무한루프를 도네요 ㅠㅠ |
|
| 위로 |
|
|
tjdals4565
가입: 2014년 9월 7일
올린 글: 14
|
| 올려짐: 2014년11월26일 19:07 주제: |
|
|
ㅠ
make_tm 에 빈 심볼리스트가 들어갔을 떄 잘 작동하는지 확인해보세용 |
|
| 위로 |
|
|
jaewooklee
가입: 2014년 10월 3일
올린 글: 23
|
| 올려짐: 2014년11월26일 20:27 주제: |
|
|
두분의 테스트 모두 잘 통과하는 것 같습니다.
소수 여부 판별은 100 이상 숫자를 넣으면 좀 시간이 걸리기는 하지만요 |
|
| 위로 |
|
|
정현진
가입: 2014년 9월 22일
올린 글: 7
|
| 올려짐: 2014년11월26일 21:29 주제: |
|
|
| 잘되네용 |
|
| 위로 |
|
|
홍선기
가입: 2014년 9월 29일
올린 글: 11
|
| 올려짐: 2014년11월27일 12:51 주제: 고치니깐 잘 되네요! |
|
|
| 빈 리스트가 들어올때가 문제였어요! 감사합다 ㅎㅎ |
|
| 위로 |
|
|
이수현
가입: 2014년 9월 22일
올린 글: 4
|
| 올려짐: 2014년11월28일 17:03 주제: 감사합니다 :) |
|
|
두 분이 올려주신 테스트 케이스 모두 잘 실행되네요!
특히 소수 판별기는 튜링머신을 구현해놓고도 어떻게 동작시키는건지 몰랐는데 실제로 이렇게 작동하는거 보니까 정말 신기하네요 ㅋㅋㅋㅋ 두 분 모두 감사합니다~ |
|
| 위로 |
|
|
|
|
새로운 주제를 올릴 수 없습니다
답글을 올릴 수 없습니다
주제를 수정할 수 없습니다
올린 글을 삭제할 수 없습니다
투표를 할 수 없습니다
|
Powered by phpBB 2.0.21-7 (Debian) © 2001, 2005 phpBB Group
Translated by kss & drssay |
FAQ
검색
멤버리스트
사용자 그룹
사용자 등록하기
개인 정보
비공개 메시지를 확인하려면 로그인하십시오
로그인
