Guest User

Untitled

a guest
Aug 31st, 2021
29
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. print('eq(X,X).')
  2. print('ne(X,X):-!,fail.')
  3. print('ne(_,_).')
  4. print('ex(_,[]).')
  5. print('ex(X,[X|_]):-!,false.')
  6. print('ex(X,[_|L]):-ex(X,L).')
  7. print('in(X,[X|L],L).')
  8. print('in(X,[Y|L],[Y|M]):-in(X,L,M).')
  9. print('match([],[]).')
  10. print('match([X|L],Q):-in(X,Q,M),match(L,M).')
  11.  
  12. function V(i,j) return 'V'..i..'_'..j end
  13.  
  14. function adj(i,j,n,m,reg)
  15.     local eq=false
  16.     local t,vij = '', V(i,j)
  17.     local function f(a,b)
  18.         local x,y = a+i,b+j
  19.         local vxy = V(x,y)
  20.         if vij~=vxy and 1<=x and 2<=y and x<=n and y<=m and not(reg[vij]==reg[vxy])
  21.         then
  22.             if eq then
  23.                 print('','ne('..vij..','..vxy..'),')
  24.             else
  25.                 t = t .. ',' .. vxy
  26.             end
  27.         end
  28.     end
  29.     f(1,0)
  30.     f(0,1)
  31.     f(-1,1)
  32.     f(1,1)
  33.     if eq==false and t~='' then
  34.         print('','ex('..vij..', ['..t:sub(2)..']),')
  35.     end
  36. end
  37.  
  38. function suguru(n,m,str)
  39.     print('suguru([')
  40.     for i=1,n do
  41.         local t='['..V(i,1)
  42.         for j=2,m do
  43.             t = t .. ',' .. V(i,j)
  44.         end
  45.         print(t..']'..(i<n and ', ' or ']) :-'))
  46.     end
  47.     -- cree les regions et ajoute les indice (au début = plus rapide)
  48.     local region, hint, var2reg = {},{},{}
  49.     for i=1,n do
  50.         for j=1,m do
  51.             local idx = ((i-1)*m + j)*2-1
  52.             local reg, val = str:sub(idx,idx), str:sub(idx+1,idx+1)
  53.             region[reg] = region[reg] or {}
  54.             var2reg[V(i,j)] = reg
  55.             table.insert(region[reg], V(i,j))
  56.             if "1"<=val and val<="5" then
  57.                 hint[V(i,j)] = val
  58.                 print('',"eq("..V(i,j)..', '..val..'),')
  59.             end
  60.         end
  61.     end
  62.     if false then
  63.         -- reindex les regions dans un tableau indexe (pour le tri)
  64.         local t = {}
  65.         for k,r in pairs(region) do
  66.             table.insert(t,r)
  67.         end
  68.         region = t
  69.         -- on trie les regions par taille
  70.         table.sort(region, function(a,b) return #a>#b end)
  71.     end
  72.     -- contrainte de region
  73.     for _,r in pairs(region) do
  74.         local vars,vals={},{}
  75.         for i=1,#r do vals[i] = true end
  76.         for i,v in ipairs(r) do
  77.             if hint[v] then
  78.                 vals[tonumber(hint[v])] = nil
  79.             else
  80.                 table.insert(vars,v)
  81.             end
  82.         end
  83.         local t={}
  84.         for i=1,#r do if vals[i] then table.insert(t,i) end end
  85.         print('','match(['.. table.concat(vars,',')..'], ['..table.concat(t,',')..']),')
  86.         -- contraintes d'adjacence
  87.         -- for _,v in ipairs(r) do
  88.             -- local i,j = v:match('V(%d+)_(%d+)')
  89.             -- adj(tonumber(i),tonumber(j),n,m,var2reg)
  90.         -- end
  91.     end
  92.     for _,r in pairs(region) do
  93.         -- contraintes d'adjacence
  94.         for _,v in ipairs(r) do
  95.             local i,j = v:match('V(%d+)_(%d+)')
  96.             adj(tonumber(i),tonumber(j),n,m,var2reg)
  97.         end
  98.     end
  99.     -- for i=1,n do
  100.         -- for j=1,m do
  101.             -- adj(i,j,n,m,var2reg)
  102.         -- end
  103.     -- end
  104.     print('','true.')
  105.     -- affichage du suguru
  106.     print("describe:-write('solving...\\n'),")
  107.     local s='+'
  108.     for i=1,m do s=s..'---+' end print('',"write('"..s.."\\n'),")
  109.     for i=1,n do
  110.         s='|'
  111.         for j=1,m-1 do
  112.             local v1,v2 = V(i,j),V(i,j+1)
  113.             s = s..' ' ..(hint[v1] or ' ')..' '..
  114.                    (var2reg[v1]==var2reg[v2] and ' ' or '|')
  115.         end
  116.         s = s..' '..(hint[V(i,m)] or ' ')..' |'
  117.         print('',"write('"..s.."\\n'),")
  118.         s='+'
  119.         for j=1,m do
  120.             local v1,v2 = V(i,j),V(i+1,j)
  121.             s = s..(var2reg[v1]==var2reg[v2] and '   ' or '---')..'+'
  122.         end
  123.         print('',"write('"..s.."\\n'),")
  124.     end
  125.     print('','true.')
  126. end
  127.  
  128. function gen(list)
  129.     local s= ''
  130.     for _,v in ipairs(list) do
  131.         s = s .. v
  132.     end
  133.     suguru(#list,#list[1]/2,s)
  134. end
  135.  
  136. if false then
  137. suguru(5,5,
  138. "A1AAAAB5BB" ..
  139. "AACCCCDDBB" ..
  140. "C1CCD2DDB4" ..
  141. "CCDDDDEEBB" ..
  142. "EEE3EEEEFF")
  143. elseif true then
  144. gen{
  145. "C1AAAA",
  146. "CCBBBB",
  147. "CCBBBB",
  148. nil}
  149. elseif false then
  150. gen{
  151. "A2BBCCCCCCCCDD",
  152. "AABBB4EEDDDDDD",
  153. "AABBBBEEFFF3DD",
  154. "AAGGHHIIIIFFFF",
  155. "GGG5GGJJI2IIFF",
  156. "K2KKG3JJJJJJJJ",
  157. "KKKKLLL4LLLLL3",
  158. nil}
  159. else
  160. gen{
  161. 'AAAAAABBBBBBCCCC',
  162. 'DDDDDDDDEEBBBBFF',
  163. 'GGHHDDEEEEIIIIFF',
  164. 'GGHHHHEEEEIIFFFF',
  165. 'JJHHHHKKIIIIFFLL',
  166. 'JJKKKKKKMMLLLLLL',
  167. 'JJNNKKMMMMOOOOLL',
  168. 'PPPPPPPPMMMMOOOO'
  169. }
  170. end
  171.  
  172. print('w([]).')
  173. print("w([X|L]):-write(X),write('\\n'),w(L).")
  174.  
  175. print('r:-reconsult(suguru).')
  176. print('h:-halt.')
  177.  
  178. print("x:-describe,time(suguru(L)),w(L).")
RAW Paste Data