0votos

función resuelveSumas en JavaScript

por josejuan hace 5 años

El problema del desafío no es sólo encontrar sumandos, el sistema completo de ecuaciones debe cumplir los criterios impuestos (ej. usar una y sólo una vez cada sumando). Aquí se resuelve la versión de partición en dos y sólo dos sumandos.

programar, utilizando Hugs una función resuelveSumas que dada una tupla formada por una lista de resultados y una lista de sumandos, devuelva una cadena de caracteres indicando si el problema tiene solución y si ésta es única o no.

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
/* 
 
  Aquí se resuelve el deafío en la forma 
   
       Ri = Ai + Bi 
 
  Si el número de ecuaciones a obtener son R, 
  entonces el número sumandos son siempre 2R. 
   
  Una búsqueda directa combinacional de las 
  elecciones (binarias) 
   
       Ri = xi1 Ai + xi2 Bi + xi3 Ci + ... 
 
  eligiendo las binarias xij tales que sólo dos 
  estén seleccionadas en cada ecuación y sólo una 
  vez en todo el sistema. 
   
  Hacen un número de combinaciones de 
   
     C2R,2 * C2(R-1),2 * ... C2,2 
 
  que está acotado superiormente por 
   
    2^R R^2R 
     
  una barbaridad, vamos. 
   
  Una búsqueda directa en backtraking de todas 
  las posibilidades, nos lleva a buscar en cada 
  nivel 2 elementos de los restantes, por lo que 
  las iteraciones vendrán a ser en el peor caso 
   
    2R * 2(R-1) * ... 
 
  Es decir 
   
    2^R R! 
     
  algo se ha mejorado... 
   
  Si agrupamos sumandos iguales y buscamos sólo 
  el primero de los dos sumando, acotamos la búsqueda 
  anterior en dos aspectos: 
   
  1. sólo iteramos sobre las particiones de cada R y no 
     sobre todos los sumandos posibles. 
      
  2. todas las particiones equivalentes son revisadas en 
     una única pasada (ej. si tenemos sumandos [2,2,2,2,4,4,4], 
     hay 24 formas de sumar 6, pero todas son equivalentes en 
     la forma 2+4=6). 
 
  Por supuesto, si sólo queremos un sistema de ecuaciones o dos, 
  o los que sean pero no todos, se puede terminar antes, claro. 
 
*/ 
function computeAllSums(rs, xs) { 
  var ks = xs.toFrequencyHash(); 
  var us = ks.sortedNumKeys(); 
  var hs = {}; 
 
  var backtrack = (ri, ss) => { 
    var r = rs[ri], rm = r >> 1, y; 
    if(!r) 
      hs[ss.map(s => s.join(',')).sort().join(';')] = ss.map(i=>i); 
    else { 
      us.forEach( x => { if(x <= rm && !!ks[y = r - x]) { 
          ks[x] -= 1; ks[y] -= 1; 
          if(ks[x] >= 0 && ks[y] >= 0) { 
            ss.push([x, y]); 
            backtrack(ri + 1, ss); 
            ss.pop(); 
          ks[x] += 1; ks[y] += 1; 
      }}); 
  }; 
 
  backtrack(0, []); 
 
  return hs; 
 
 
 
 
 
 
 
 
// así, por ejemplo 
computeShowAndPrintSums([7, 8, 10, 6], [2, 3, 6, 5, 5, 4, 5, 1]); 
/* genera la salida: 
 
        7 = 1 + 6 
        8 = 3 + 5 
        10 = 5 + 5 
        6 = 2 + 4 
 
        7 = 2 + 5 
        8 = 3 + 5 
        10 = 4 + 6 
        6 = 1 + 5 
 
        7 = 3 + 4 
        8 = 2 + 6 
        10 = 5 + 5 
        6 = 1 + 5 
         
*/ 
 
 
 
// Para generar instancias más difíciles de resolver, se puede hacer 
var Size = 15, MinR = 4, MaxR = 10; 
var rs = Array(Size).join(' ').split('').map(_ => MinR + ~~((MaxR - MinR) * Math.random())); 
var xs = rs.map(r => { var z = 1 + ~~((r - 1) * Math.random()); return [z, r - z] }).reduce((a,b)=>a.concat(b)); 
computeShowAndPrintSums(rs, xs); 
 
/* Que para los parámetros anteriores, una salida aleatoria podría ser: 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 2 + 2 
        5 = 2 + 3 
        9 = 1 + 8 
        7 = 1 + 6 
        6 = 3 + 3 
        6 = 3 + 3 
        4 = 2 + 2 
        6 = 2 + 4 
        8 = 4 + 4 
        5 = 1 + 4 
        4 = 1 + 3 
        5 = 1 + 4 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 2 + 2 
        5 = 2 + 3 
        9 = 1 + 8 
        7 = 3 + 4 
        6 = 3 + 3 
        6 = 2 + 4 
        4 = 1 + 3 
        6 = 2 + 4 
        8 = 2 + 6 
        5 = 1 + 4 
        4 = 1 + 3 
        5 = 1 + 4 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 2 + 2 
        5 = 1 + 4 
        9 = 1 + 8 
        7 = 3 + 4 
        6 = 3 + 3 
        6 = 3 + 3 
        4 = 2 + 2 
        6 = 2 + 4 
        8 = 2 + 6 
        5 = 1 + 4 
        4 = 1 + 3 
        5 = 1 + 4 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 2 + 2 
        5 = 2 + 3 
        9 = 1 + 8 
        7 = 1 + 6 
        6 = 3 + 3 
        6 = 2 + 4 
        4 = 1 + 3 
        6 = 2 + 4 
        8 = 4 + 4 
        5 = 2 + 3 
        4 = 1 + 3 
        5 = 1 + 4 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 1 + 3 
        5 = 2 + 3 
        9 = 1 + 8 
        7 = 3 + 4 
        6 = 2 + 4 
        6 = 2 + 4 
        4 = 1 + 3 
        6 = 2 + 4 
        8 = 2 + 6 
        5 = 2 + 3 
        4 = 1 + 3 
        5 = 1 + 4 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 2 + 2 
        5 = 1 + 4 
        9 = 1 + 8 
        7 = 1 + 6 
        6 = 3 + 3 
        6 = 3 + 3 
        4 = 2 + 2 
        6 = 3 + 3 
        8 = 4 + 4 
        5 = 1 + 4 
        4 = 2 + 2 
        5 = 1 + 4 
 
        5 = 1 + 4 
        9 = 1 + 8 
        4 = 2 + 2 
        5 = 1 + 4 
        9 = 1 + 8 
        7 = 3 + 4 
        6 = 3 + 3 
        6 = 3 + 3 
        4 = 2 + 2 
        6 = 3 + 3 
        8 = 2 + 6 
        5 = 1 + 4 
        4 = 2 + 2 
        5 = 1 + 4 
 
        5 = 2 + 3 
        9 = 1 + 8 
        4 = 1 + 3 
        5 = 2 + 3 
        9 = 1 + 8 
        7 = 1 + 6 
        6 = 2 + 4 
        6 = 2 + 4 
        4 = 1 + 3 
        6 = 2 + 4 
        8 = 4 + 4 
        5 = 2 + 3 
        4 = 1 + 3 
        5 = 2 + 3 
         
*/ 
 
 
 
 
 
 
// funciones auxiliares 
Array.prototype.toFrequencyHash = function () { 
  return this.reduce((a, x) => (a[x] = (a[x] || 0) + 1, a), {}); 
}; 
Array.prototype.sum = function () { 
  return this.reduce((a, b) => ~~a + ~~b, 0); 
}; 
Object.prototype.sortedNumKeys = function () { 
  return Object.keys(this).sort((a, b) => a - b).map(n => ~~n); 
}; 
function showSums(hs) { 
  return Object. 
           keys(hs). 
           map(k => hs[k].map(ss => ss.sum() + " = " + ss.join(" + ")).join("\n")). 
           join("\n\n"); 
function computeShowAndPrintSums(rs, xs) { 
  console.log( showSums( computeAllSums(rs, xs) ) ); 
14 comentarios
0votos

Escrito por ilopez hace 5 años

Independientemente de la lógica que hayas usado, ya que no se haskell, te diré que los resultados que da tu método no están completos.

En tu primer ejemplo al tener 3 cincos como sumando cada resultado en los que intervengan el numero 5 debería de tener 3 salidas y en tu salida sólo se muestran 2.

A continuación te pongo la salida que debería de darte ordenada por resultado:
--------------------------------------------------
6 = 2 + 4
6 = 5 + 1 //Primer 5
6 = 5 + 1 //Segundo 5
6 = 5 + 1 //Tercer 5
7 = 6 + 1
7 = 3 + 4
7 = 2 + 5 // Primer 5
7 = 2 + 5 //Segundo 5
7 = 2 + 5 //Tercer 5
8 = 2 + 6
8 = 3 + 5 //Primer 5
8 = 3 + 5 //Segundo 5
8 = 3 + 5 //Tercer 5
10 = 6 + 4
10 = 5 5 //Primer cinco Segundo Cinco
10 = 5 5 //Primer cinco Tercer Cinco
10 = 5 5 //Segundo cinco tercer Cinco
-------------------------------------------
Como ves en total son unas 17 soluciones posibles y tu salida da unas 14 soluciones.
0votos

Escrito por josejuan hace 5 años

Hola @ilopez, en el enunciado se pide explícitamente eliminar los sistemas equivalentes, puedes cambiar no obstante:
hs[ss.map(s => s.join(',')).sort().join(';')] = ss.map(i=>i);

por
hs[Math.random()] = ss.map(i=>i);

si las quieres todas.

Por cierto, no es Haskell, es javascript... ;)
0votos

Escrito por josejuan hace 5 años

Por cierto, creo que no has entendido cual es el resultado esperado.

No hay "unas 14 soluciones", hay exactamente tres.

// primera solución
    7 = 1 + 6 
    8 = 3 + 5 
    10 = 5 + 5 
    6 = 2 + 4 

// segunda solución
    7 = 2 + 5 
    8 = 3 + 5 
    10 = 4 + 6 
    6 = 1 + 5 

// tercera solución
    7 = 3 + 4 
    8 = 2 + 6 
    10 = 5 + 5 
    6 = 1 + 5 
0votos

Escrito por ilopez hace 5 años

Creo que has entendido mal el enunciado, no es un sistema de ecuaciones, el objetivo es hallar todas las posibles combinaciones de sumandos que da cada resultado.
0votos

Escrito por ilopez hace 5 años

Y sino es así el creador del desafío que lo especifique mejor.
0votos

Escrito por Mordecai hace 5 años

Hola

el objetivo es hallar todas las posibles combinaciones de sumandos, pero filtrando las que sean iguales o equivalentes
0votos

Escrito por ilopez hace 5 años

¿Aunque tengan números repetidos como sumandos?
0votos

Escrito por ilopez hace 5 años

Entonces esta solución no vale lo siento josejuan
0votos

Escrito por adr hace 5 años

Yo no la ví válida porque claramente hace que los sumandos sean únicos en este caso:

// primera solución
    7 = 1 + 6 
    8 = 3 + 5 
    10 = 5 + 5 
    6 = 2 + 4 

// segunda solución
    7 = 2 + 5 
    8 = 3 + 5 
    10 = 4 + 6 
    6 = 1 + 5 

// tercera solución
    7 = 3 + 4 
    8 = 2 + 6 
    10 = 5 + 5 
    6 = 1 + 5 


Y siendo así no debería aparecer de nuevo el 10= 5+5

Si dijese que los 5 se repiten hasta tres veces debería dar para 10:

10 = 6 + 4
10 = 5 + 5
10 = 5 + 5
10 = 5 + 5
0votos

Escrito por Mordecai hace 5 años

No sabes cómo me gustaría hacer un comentario inteligente a la altura de tu resolución, pero desgraciadamente mi dominio del javascript no da para tanto. Mi petición de que se utilizara haskell no obedecía a ningún capricho, simplemente es uno de los pocos lenguajes que controlo un poco. Podrías publicar la solución en haskell ?
0votos

Escrito por Mordecai hace 5 años

Crees que utilizando Java la ejecución del programa sería más eficiente que en haskell?
0votos

Escrito por josejuan hace 5 años

No creo que usar uno u otro sea determinante.
0votos

Escrito por Mordecai hace 5 años

Es que otro usuario ha utilizado php, que creo que utiliza objetos y clases como java, y supuse que al escoger los dos ese tipo de programación quizás significaba que era más adecuada para este caso. Por qué has escogido java?
0votos

Escrito por adr hace 5 años

Javascript, no Java. No mezclemos lenguajes que tampoco es lo mismo C++ que C#.
Texto del enlace

Aquí cada cual usa el lenguaje que quiere. Como yo veo que no hay casi nadie de php y es de los que más uso por trabajo pues...

Es cierto que especificaste uno en concreto, pero si lo pasas a pseudocódigos, ves lo que hacen y lo haces en el que quieras.

Un programador sólo necesita la lógica y después aprender una sintaxis nueva.

Es cierto que las funciones nativas y las propiedades cambian, pero este ejercicio es muy muy facilito y yo creo que es fácil pasarlo de uno a otro.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.