fork download 
  1. %You will be given a board that consists of N x M cells.
  2. % Each cell contains a color (Red, Yellow or Blue).
  3. % Your task is to find color cycles for any of the three colors
  4. % For example, as shown in the picture, cells 2,1-> 2,2-> 3,2-> 3,1 form a blue cycle
  5. % Another cycle could be cells 2,0-> 2,1-> 3,1-> 3,0
  6. % Note that yellow and red colors do not form cycles in this example.
  7.  %Your code should print at least one of these cycles including its color (if any) or no cycles
  8. % exist
  9. % Cycle defined by the following cells c1, c2, ..., ck must have the following:
  10. %These cells are different (no duplicates)--
  11. %At least 4 cells (or more)
  12.  %All cells have the same color
  13.  %The cells are adjacent to each other
  14.  %You are allowed to use the search engine for uninformed search that we given in the lab
  15.  %Your main tasks are:----
  16.  %Design input
  17.  %Design state representation
  18.  %Design moves
  19.  %Design output
  20.  
  21. %Helper
  22.  
  23. replace(0,[_|T],X,[X|T]).
  24. replace(Index,[H|T],X,[H|R]):-
  25.     Index>0,NewIndex is Index - 1,
  26.     replace(NewIndex,T,X,R).
  27.  
  28.  
  29. getLast([H],H):-!.
  30. getLast([_|T],Last):-
  31.     getLast(T,Last).
  32.  
  33.  
  34. fill([],_,[]):-!.
  35. fill([_|T],X,[X|Done]):-
  36.     fill(T,X,Done).     
  37.  
  38.  
  39. :-dynamic n/1.
  40. :-dynamic m/1.
  41.  
  42. :-dynamic path/1.
  43.  
  44.  
  45. setPath(Path):-
  46.     retractall(path(_)),
  47.     assertz(path(Path)).
  48.  
  49.  
  50.  
  51.  
  52.  
  53. isValid(I,J):-
  54.     n(N),m(M),
  55.     I<N,I>=0,J<M,J>=0.
  56.  
  57. getCell(I,J,Grid,Output):-
  58.     nth0(I,Grid,ROW),
  59.     nth0(J,ROW,Output).    
  60.  
  61. detectCycle(N,M,Grid):-
  62.     retractall(n(_)),retractall(m(_)),
  63.     assertz(n(N)),assertz(m(M)),
  64.     detectCycle(Grid).
  65.  
  66.  
  67.  
  68.  
  69. visit(I,J,Visited,NewVisited):-
  70.     nth0(I,Visited,Row),
  71.     replace(J,Row,true,NewRow),
  72.     replace(I,Visited,NewRow,NewVisited).
  73.  
  74.  
  75.  
  76. detectCycle(Grid):-
  77.     n(N),m(M),
  78.     length(ROW,M),
  79.     fill(ROW,false,NewRow),
  80.     length(V,N),
  81.     fill(V,NewRow,Visited),
  82.  
  83.     ((tryAll(Grid,Visited,-1,-1,[]), path(Path),length(Path,L),L>=4)->
  84.         write('Cycle Found:'), 
  85.         writeln(Path);
  86.         write('No Cycle Found')
  87.     ).
  88.  
  89.  %down
  90. move(I,J,X,J):-
  91.     X is I + 1.
  92.  %up
  93. move(I,J,X,J):-
  94.     X is I - 1.
  95.  
  96. %right
  97.  move(I,J,I,Y):-
  98.      Y is J+1.
  99. % left
  100.  move(I,J,I,Y):-
  101.     Y is J -1.
  102.  
  103.  
  104.  
  105. tryAll(Grid,Visited,ParentX,ParentY,Path):-
  106.     n(N),m(M),
  107.     setPath([]),
  108.     between(0,N,I),
  109.     between(0,M,J),
  110.     searchCycle(I,J,Grid,Visited,ParentX,ParentY,Path).
  111.  
  112.  
  113.  
  114.  
  115. searchCycle(I,J,Grid,Visited,ParentX,ParentY,Path):-
  116.     writeln([I,J]),
  117.     isValid(I,J),
  118.     getCell(I,J,Grid,Color),
  119.     getCell(I,J,Visited,IsVisited),
  120.     \+IsVisited, % not visited before
  121.     visit(I,J,Visited,NewVisited),
  122.     findall(_,
  123.         (
  124.         move(I,J,X,Y), %next state
  125.         isValid(X,Y), % check next 
  126.         path(GlobalPath),
  127.         GlobalPath == [], % no cycles found
  128.         getCell(X,Y,Grid,CurrColor),
  129.         getCell(X,Y,NewVisited,CurrIsVisited),
  130.         (
  131.             Color == CurrColor,
  132.             NextPath = [[I,J]|Path],
  133.             CurrIsVisited == true,
  134.             \+(ParentX = X , ParentY = Y)-> 
  135.             (getLast(NextPath,Last),Last == [X,Y] -> setPath(NextPath))
  136.             ;
  137.             (Color == CurrColor -> NextPath = [[I, J] | Path] ),
  138.             searchCycle(X,Y,Grid,Visited,I,J,NextPath)
  139.  
  140.         )
  141.     )
  142.  
  143.     ,Temp),
  144.     length(Temp,L),
  145.     L>0.
  146.  
  147.  
  148.  
  149.  
  150.  
  151.  
  152.  
  153.  
Success #stdin #stdout #stderr 0.31s 40536KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
Error: unexpected input in "%You will be given a board that consists of N x M cells."
Execution halted
https://ideone.com/Tv3vgr
language:
R (R 3.5.2)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!