Advertisement
IcaroPeretti

searchA

Apr 1st, 2022
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. function getNumeroPadres(possibilidade) {
  2. const padres = String(possibilidade).substring(0,3);
  3. const numPadres = padres.split('').reduce((p, n) => p + (n === '1' ? 1 : 0), 0)
  4.  
  5. return numPadres
  6. }
  7. function getNumeroCanibais(possibilidade) {
  8. const canibais = String(possibilidade).substring(3,6);
  9. const numCanibais = canibais.split('').reduce((p, n) => p + (n === '1' ? 1 : 0), 0);
  10. return numCanibais;
  11. }
  12. function temPossibilidadeEquivalente (possibilidade, possibilidades) {
  13. return possibilidades.some((combinacao) => {
  14. const numPadresCombinacao = getNumeroPadres(combinacao);
  15. const numCanibaisCombinacao = getNumeroCanibais(combinacao);
  16.  
  17. const numPadresNovaPossibilidade = getNumeroPadres(possibilidade);
  18. const numCanibaisNovaPossibilidade = getNumeroCanibais(possibilidade);
  19.  
  20. return (numPadresCombinacao === numPadresNovaPossibilidade && numCanibaisCombinacao === numCanibaisNovaPossibilidade)
  21. })
  22. }
  23. function gerarPossibilidadesAdicao2 (config) {
  24. const splitted = config.split('');
  25. const possibilidades = [];
  26.  
  27. for (let index = 0; index < splitted.length; index++) {
  28. if (splitted[index] === '0') {
  29. const aux = [...splitted];
  30. aux[index] = '1';
  31.  
  32. for (let index2 = 0; index2 < aux.length; index2++) {
  33. if (index !== index2 && aux[index2] === '0') {
  34. const aux2 = [...aux];
  35. aux2[index2] = '1';
  36. const newPossibilidade = aux2.join('');
  37. if (!possibilidades.includes(newPossibilidade) && !temPossibilidadeEquivalente(newPossibilidade, possibilidades)) {
  38. possibilidades.push(newPossibilidade);
  39. }
  40. }
  41.  
  42. }
  43. }
  44. }
  45. return possibilidades;
  46. }
  47. function gerarPossibilidadesAdicao1 (config) {
  48. const splitted = config.split('');
  49. const possibilidades = [];
  50.  
  51. const numTotal = splitted.reduce((p,n) => p+ (n === '1' ? 1 : 0), 0);
  52.  
  53. if (numTotal <= 5) {
  54. for (let index = 0; index < splitted.length; index++) {
  55. if (splitted[index] === '0') {
  56. const aux = [...splitted];
  57. aux[index] = '1'
  58. const newConfig = String(aux.join(''));
  59. if (!temPossibilidadeEquivalente(newConfig, possibilidades)) {
  60. possibilidades.push(newConfig);
  61. }
  62. }
  63. }
  64. }
  65.  
  66. return possibilidades;
  67. }
  68. function gerarPossibilidadesRemocao2 (config) {
  69. // itera tudo e para aqueles que forem 1 adiciona 0 nele mesmo e itera todos os outros
  70.  
  71.  
  72. const splitted = config.split('');
  73. const possibilidades = [];
  74.  
  75. for (let index = 0; index < splitted.length; index++) {
  76. if (splitted[index] === '1') {
  77. const aux = [...splitted];
  78. aux[index] = '0';
  79.  
  80. for (let index2 = 0; index2 < aux.length; index2++) {
  81. if (index !== index2 && aux[index2] === '1') {
  82. const aux2 = [...aux];
  83. aux2[index2] = '0';
  84. const newPossibilidade = aux2.join('');
  85. if (!possibilidades.includes(newPossibilidade) && !temPossibilidadeEquivalente(newPossibilidade, possibilidades)) {
  86. possibilidades.push(newPossibilidade);
  87. }
  88. }
  89.  
  90. }
  91. }
  92. }
  93. return possibilidades;
  94.  
  95. }
  96. function gerarPossibilidadesRemocao1 (config) {
  97. const splitted = config.split('');
  98. const possibilidades = [];
  99.  
  100. const numTotal = splitted.reduce((p,n) => p+ (n === '1' ? 1 : 0), 0);
  101.  
  102. if (numTotal <= 5) {
  103. for (let index = 0; index < splitted.length; index++) {
  104. if (splitted[index] === '1') {
  105. const aux = [...splitted];
  106. aux[index] = '0'
  107. const newConfig = String(aux.join(''));
  108. if (!temPossibilidadeEquivalente(newConfig, possibilidades)) {
  109. possibilidades.push(newConfig);
  110. }
  111. }
  112. }
  113. }
  114.  
  115. return possibilidades;
  116. }
  117. function gerarPossibilidades (config, vaiParaEsquerda) {
  118. const adicao2 = gerarPossibilidadesAdicao2(config);
  119. const adicao1 = gerarPossibilidadesAdicao1(config);
  120. const remocao2 = gerarPossibilidadesRemocao2(config);
  121. const remocao1 = gerarPossibilidadesRemocao1(config);
  122. const possibilidades =[]
  123.  
  124. if (vaiParaEsquerda) {
  125. possibilidades.push(...[...adicao2, ...adicao1])
  126. } else {
  127. possibilidades.push(...[...remocao2, ...remocao1])
  128. }
  129.  
  130. return possibilidades;
  131. }
  132. function peneira (possibilidades) {
  133. const possibilidadesValidas = [];
  134. for (const possibilidade of possibilidades) {
  135. const numPadres = getNumeroPadres(possibilidade);
  136. const numCanibais = getNumeroCanibais(possibilidade);
  137.  
  138. if (numCanibais === numPadres || (numPadres > numCanibais && numPadres === 3) || (numCanibais > numPadres && numPadres === 0)) {
  139. possibilidadesValidas.push(possibilidade)
  140. }
  141. }
  142. return possibilidadesValidas;
  143. }
  144. const estadosGerados = ['111111'];
  145. function gerarNodo (nodo, pos) {
  146. if (pos === 30) return;
  147. const possibilidadesValidas = peneira(gerarPossibilidades(nodo.estado, pos % 2), pos % 2)
  148.  
  149. for (const possibilidade of possibilidadesValidas) {
  150. const novoNodo = {
  151. estado: possibilidade,
  152. caminhos: []
  153. }
  154.  
  155. if (!estadosGerados.includes(novoNodo.estado)) {
  156. if (possibilidade === '000000') {
  157. nodo.caminhos.push(novoNodo)
  158. } else {
  159. estadosGerados.push(novoNodo.estado)
  160. nodo.caminhos.push(novoNodo)
  161.  
  162. gerarNodo(novoNodo, pos+1)
  163. }
  164. }
  165.  
  166. }
  167. }
  168. function pegarMelhorCaminho(nodo) {
  169. let melhor = {
  170. qtd: 99,
  171. index: null
  172. };
  173. for (let index = 0; index < nodo.caminhos.length; index++) {
  174. const caminho = nodo.caminhos[index];
  175. const qtd = caminho.estado.split('').reduce((p, n) => p+ (n==='1' ? 1 : 0), 0)
  176.  
  177. if (qtd < melhor.qtd) {
  178. melhor.qtd = qtd;
  179. melhor.index = index;
  180. }
  181. if (qtd === 0) {
  182. return nodo.caminhos[melhor.index].estado
  183. }
  184. }
  185. return pegarMelhorCaminho(nodo.caminhos[melhor.index])
  186. }
  187. const inicio = {
  188. estado: '111111',
  189. caminhos: [],
  190. }
  191. gerarNodo(inicio, 0)
  192. console.log('\n', pegarMelhorCaminho(inicio));
  193. require('fs').writeFile('nodes', JSON.stringify(inicio, null, 2), () => {})
  194. // printar(inicio)
Advertisement
RAW Paste Data Copied
Advertisement