Juego para aprender estructuras de datos y algoritmos

JUEGO PARA APRENDER ESTRUCTURAS DE DATOS Y ALGORITMOS GAME FOR LEARNING DATA STRUCTURES AND ALGORITHMS Alejand o Jim´enez S´anchez DOBLE GRADO EN INGENIER´ IA INFORM´ ATICA Y MATEM´ ATICAS FACULTAD DE INFORM´ ATICA UNIVERSIDAD COMPLUTENSE DE MADRID T abajo Fin de G ado en Ingenie ´ıa In o m´a ica Cu so 2020/2021 Feb e o de 2021 Di ec o : I ´an Ga c´ıa-Maga i˜no Ga c´ıa ´ Indice gene al 1. In oducci´on 4 1.1. In oduc ion..................................... 4 1.2. In oducci´on a los juegos se ios. Concep os p incipales . . . . . . . . . . . . . . 5 1.3. In oducci´on a la aplicaci´on desa ollada . . . . . . . . . . . . . . . . . . . . . 7 1.4. T abajo exis en e y aplicaciones simila es . . . . . . . . . . . . . . . . . . . . . 11 1.5. Plande abajo................................... 13 2. Algo i mos e In e acci´on 15 2.1. In oducci´on..................................... 15 2.2. O denaci´on po inse ci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.2.1. Tu o ialdeljuego.............................. 16 2.2.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 18 2.2.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 21 2.3. O denaci´on po selecci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 2.3.1. Tu o ialdeljuego.............................. 24 2.3.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 25 2.3.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 26 2.4. O denaci´on po el m´e odo de la bu buja . . . . . . . . . . . . . . . . . . . . . 27 2.4.1. Tu o ialdeljuego.............................. 28 2.4.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 29 2.4.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 30 2.5. O denaci´on po mezclas (1) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.5.1. Tu o ialdeljuego.............................. 33 2.5.2. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 35 2.5.3. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 36 2.6. T´ecnica de en ana deslizan e . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6.1. In oducci´on a la ´ecnica . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.6.2. Tu o ialdeljuego.............................. 40 2.6.3. In e acci´on de allada con un ejemplo . . . . . . . . . . . . . . . . . . . 42 2.6.4. Algo i mos de con ol y comp obaci´on . . . . . . . . . . . . . . . . . . 44 3. Dise˜no y aspec os de la aplicaci´on 45 3.1. Clases y p ocesos p incipales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.1. Clases .................................... 45 3.1.2. Diag amas de secuencia de dos p ocesos p incipales . . . . . . . . . . . 48 3.2. Feedback p opo cionado y o as uncionalidades . . . . . . . . . . . . . . . . . 50 3.2.1. Feedback................................... 50 3.2.2. Log con la in e acci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 1 4. E aluaci´on con Usua ios 54 4.1. P ime as p uebas con usua ios . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 4.1.1. In oducci´on................................. 54 4.1.2. P uebas ealizadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.1.3. Resul ados y posibles mejo as . . . . . . . . . . . . . . . . . . . . . . . 55 4.2. Teo ´ıa sob e p uebas de usabilidad . . . . . . . . . . . . . . . . . . . . . . . . 57 4.3. P uebas inales con usua ios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.4. Resul ados de las p uebas y conclusiones . . . . . . . . . . . . . . . . . . . . . 59 4.4.1. Cues iona io p e io . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.4.2. Cues iona io inal.............................. 61 4.4.3. An´alisis de los logs ............................. 62 5. Conclusiones y abajo u u o 65 5.1. Conclusiones..................................... 65 5.2. T abajo u u o ................................... 65 5.3. Conclusions ..................................... 66 5.4. Fu u ewo k..................................... 66 Bibliog a ´ıa 67 2 Resumen Las asigna u as de algo i mos y es uc u as de da os son una pa e undamen al en los es udios de in o m´a ica. En una p ime a ap oximaci´on a ellas, el alumno puede ene di- icul ades en su comp ensi´on. Es po ello que puede se buena idea disminui el ni el de abs acci´on, elegi un caso conc e o y mos a la aplicaci´on del algo i mo a dicho ejemplo. Adem´as, nume osos es udios es ´an a a o de que sea ambi´en el es udian e el que ap ende po s´ı mismo median e la in e acci´on con un juego elacionado con el concep o a es udia . Es po ello que se implemen a una aplicaci´on en Uni y que mues a las ideas p incipales de algunos de los algo i mos b´asicos y es uc u as de da os ´ıpicas, y que no se limi a a mos a su uncionamien o, sino que pe mi e la in e acci´on del usua io, gua dando ambi´en es ad´ıs icas sob e su endimien o. En es a memo ia se explican inicialmen e los obje i os y las aplicaciones simila es exis en es. En los cap´ı ulos siguien es, se desc ibe el desa ollo de la aplicaci´on. P ime o, se cen a en cada juego implemen ado y la in e acci´on pedida al usua io en cada caso; despu´es, en los aspec os del dise˜no y desa ollo de la aplicaci´on. La memo ia inaliza con los esul ados de las p uebas con usua ios. Palab as cla e Algo i mos, ap endizaje basado en juegos, es uc u as de da os, p uebas de usabilidad, Uni y. Abs ac Algo i hms and da a s uc u es a e co e subjec s in compu e science cou ses. In a i s app oach, he s uden may ind hem di icul . In consequence, i could be a good idea o use a lowe le el o abs ac ion, choose a conc e e example and show he low o he algo i hm applied o ha case. In addi ion, he e a e a lo o a icles ha uphold he bene i s o he s uden s i hey in e ac wi h a game abou hese concep s. The e o e, a Uni y game has been de eloped in o de o show he main concep s o hese mos common algo i hms and da a s uc u es. I allows use s o in e ac wi h i o make lea ning mo e a ac i e, and sa es da a abou hei pe o mance. In his wo k, ini ially, he aims o he applica ion a e explained, and simila games a e analyzed. Then, he e a e wo chap e s abou he de elopmen o he applica ion. The i s one is ocused on he games ha a e implemen ed and he use in e ac ion. The second one explains he design and he de elopmen o he game. Finally, he ou comes o he usabili y es s a e shown. Keywo ds Algo i hms, game-based lea ning, da a s uc u es, usabili y es ing, Uni y. 3 Cap´ı ulo 1 In oducci´on Las asigna u as de algo i mos y es uc u as de da os son b´asicas en los cu sos de ciencias de la compu aci´on. Adem´as, son muchos los au o es que de ienden que inco po a ideojuegos en el p oceso educa i o es una buena idea. Es o ha se ido de mo i aci´on pa a desa olla una aplicaci´on educa i a en Uni y sob e ciencias de la compu aci´on. En es e abajo se explica dicho juego educa i o sob e algo i mos y es uc u as de da- os. El obje i o es que el usua io pueda simula el lujo de un algo i mo haciendo acciones simila es a las que ha ´ıa el o denado sob e su memo ia, ap endiendo as´ı c´omo unciona el algo i mo. Adem´as, la aplicaci´on gua da es ad´ıs icas sob e el endimien o de los jugado es y iene ca ac e ´ıs icas ´ıpicas de los juegos como pun uaciones. En es e cap´ı ulo in oduc o io se exponen concep os b´asicos sob e juegos se ios, se analizan las aplicaciones simila es y se expone el plan de abajo as una e apa de in es igaci´on. El segundo cap´ı ulo se cen a en los algo i mos implemen ados en el juego y la in e acci´on eque ida al usua io. El e ce o explica el dise˜no global as´ı como uncionalidades adicionales. Se adjun an ambi´en algunos diag amas UML. Po ´ul imo, el cua o cap´ı ulo explica los esul ados de las p uebas de usabilidad ealizadas al inaliza el desa ollo. 1.1. In oduc ion Algo i hms and da a s uc u es a e co e subjec s in compu e science cou ses. In addi ion, a lo o esea che s uphold ha inco po a ing ideogames in educa ion is a good idea. This has been a mo i a ion o de elop a Uni y educa ional applica ion abou compu e science. In his wo k, his educa ional game abou algo i hms and da a s uc u es is explained. The aim is ha he use can simula e he low o an algo i hm by execu ing ac ions ha a e simila o hose execu ed by he compu e on i s memo y. Thus, he s uden would lea n how he algo i hm wo ks. In addi ion, he applica ion sa es s a is ics abou he pe o mance o he playe s and includes some game ea u es like sco es. In his in oduc o y chap e , basic concep s abou se ious games a e explained a e some esea ch. The second chap e ocuses on hese algo i hms implemen ed in he game and he in e ac ion ha is equi ed o playe s. The hi d one is abou he o e all design o he applica ion and addi ional unc ionali ies. Some UML diag ams a e shown in his chap e oo. Finally, he ou comes o he usabili y es s ha we e pe o med a e he de elopmen was inished a e explained in he ou h chap e . 4 1.2. In oducci´on a los juegos se ios. Concep os p inci- pales Dado que el obje i o de es e abajo es desa olla un juego se io educa i o sob e ciencias de la compu aci´on, en p ime luga se exponen concep os sob e es e campo. Es a in es iga- ci´on ha ayudado al dise˜no y desa ollo de la aplicaci´on, p opo cionando ideas ya p obadas po o os au o es. Es a secci´on in oduc o ia se basa p incipalmen e en la e e encia [1]. Se sabe que los juegos han es ado p esen es en las di e en es sociedades desde hace mucho iempo. Con la apa ici´on de o denado es, consolas y o os ma e iales in o m´a icos se ab ie on nue as posibilidades y se comenza on a desa olla los llamados juegos digi ales. Es e campo de los ideojuegos se ha desa ollado eno memen e en los ´ul imos a˜nos, y una de las cla es de es e c ecimien o es el hecho de p o oca en sus usua ios una eno me a acci´on. Como se de ini´o en [2], el jugado puede llega al llamado es ado men al de lujo, donde queda o al- men e concen ado e inme so en el juego. O o concep o elacionado es el de lujo del juego [3], ca ac e izado po concen aci´on exclusi a, sen imien o de con ol sob e el juego, ene eedback inmedia o de las acciones ealizadas y a on a me as cla as. Po an o, consegui ese es ado se ´a uno de los obje i os del equipo de desa ollo de un juego digi al. Es as ca ac e ´ıs icas de los juegos se pueden ap o echa pa a p op´osi os que aba can no solo el en e enimien o, sino ambi´en o os campos. En [1] se comen a el ejemplo de la ele isi´on. Pasado un iempo as su apa ici´on, se empeza on a desa olla p og amas con p op´osi os educa i os, po ci a un campo dis in o al en e enimien o. De hecho, algunos jue- gos de mesa ya en´ıan p op´osi os adicionales a di e i se. Po ´ul imo, es cla o que los juegos depo i os ienen la en aja adicional de mejo a la salud. Se de ine juego se io como aquel juego digi al que pe sigue en e ene y consegui al menos un obje i o m´as. No obs an e, no hay un consenso o al en es a de inici´on, ya que algunos au o es se cen an en la in enci´on del desa ollado del juego, mien as que o os se cen an en la in enci´on del usua io. En cambio, s´ı es com´un la idea de ene al menos un obje i o adem´as del en e enimien o. Es as me as adicionales se denominan obje i os ca ac e ´ıs icos. Los juegos se ios pueden se de cualquie g´ene o, ya que se puede busca la consecuci´on de los obje i os ca ac e ´ıs icos po medio de di e sas em´a icas. Si un juego se io iene ´exi o, el jugado se ´a dis in o despu´es de habe jugado espec o a an es: end ´a m´as conocimien o, mejo salud o sus opiniones hab ´an cambiado. El ´e mino “juego se io” gan´o popula idad en 2002 con el a ´ıculo de Sawye y Reje ski [4] y con el juego Ame ica’s A my [5]. Relacionado con los concep os de lujo explicados m´as a iba, Sinclai [6] in oduce el lujo dual pa a juegos se ios: hay que busca an o el a ac i o del juego (buena expe ien- cia de usua io) como su e ec i idad (consecuci´on del obje i o ca ac e ´ıs ico). El a ac i o se consigue con un equilib io en e la di icul ad y el ni el de habilidad del usua io. Como es e ´ul imo es din´amico (es espe able que la habilidad mejo e con la p ´ac ica del juego), hab ´ıa que adap a la di icul ad din´amicamen e ambi´en pa a que el jugado no caiga en el edio. El o o ex emo (la di icul ad supe a ampliamen e a las habilidades) se ca ac e iza po us aci´on po pa e del usua io. En cuan o a la e ec i idad, en es e a ´ıculo [6] se p esen a un juego se io elacionado con el depo e (uno de los llamados exe games). Po an o, la e ec i idad consis i ´ıa en encon a un equilib io en e la capacidad ´ısica del usua io y la in ensidad del eje cicio, man eni´endose siemp e la exigencia del juego en un in e alo que no esul e i ial pa a el usua io (no gene a ´ıa bene icio en la salud del mismo) pe o que ampoco 5 exija demasiado (pod ´ıan ocu i lesiones). Es o se ex iende a muchos o os g´ene os de juegos. Habi ualmen e se elacionan los concep os de juegos educa i os, “edu ainmen ” ([7], don- de se jun an educa ion yen e ainmen ) y ap endizaje basado en juegos (game-based lea ning, [7]) con el concep o de juegos se ios, ya que se es ablece la iden i icaci´on del obje i o ca ac- e ´ıs ico con el ap endizaje. Es o no es cie o, ya que el obje i o ca ac e ´ıs ico puede se muy di e so (pone se en o ma, desa olla habilidades sociales o de esoluci´on de p oblemas, p omo e cie os alo es). Po an o, los juegos educa i os y es o de concep os elacionados se iden i ican m´as bien como un subconjun o es ic o de los juegos se ios. Pese a que la indus ia de los juegos se ios ha c ecido ecien emen e, es ´a muy lejos de lle- ga al campo de los ideojuegos de en e enimien o (nomencla u a usada pa a aquellos cuyo obje i o es solo en e ene ). Una az´on de es o es que el p´ublico obje i o suele se mucho m´as educido y espec´ı ico que en el caso de ideojuegos de en e enimien o. O o incon enien e es que los p esupues os pa a el desa ollo de la aplicaci´on suelen se meno es. Adem´as, es m´as complejo su desa ollo, ya que habi ualmen e hay que inclui en el p oceso a expe os del dominio del obje i o ca ac e ´ıs ico. Es a mul idisciplina idad puede complica el desa ollo de la aplicaci´on, al con i i pe sonas con di e en es o mas de esol e p oblemas y de pensa , o incluso las disciplinas pueden ene e minolog´ıa dis in a. Po ´ul imo, como es un campo menos amplio, los desa ollado es de juegos se ios ienen menos e e encias en las que basa se. Como ya se ha comen ado, es buena idea (y no solo en juegos se ios, sino en cualquie ipo de juego) adap a se a la habilidad del usua io. Adem´as, el hecho de que cada juego se io enga unos usua ios obje i o muy espec´ı icos, hace a´un m´as necesa io si cabe la adap aci´on de la di icul ad a las habilidades. Dado que una de las p incipales amas de los juegos se ios son los juegos educa i os y en es a memo ia se explica el dise˜no y desa ollo de una aplicaci´on cuyo obje i o ca ac e ´ıs i- co es el ap endizaje, es in e esan e cen a se ambi´en en algunos aspec os educa i os. En el a ´ıculo mencionado an e io men e [7], M. P ensky asegu a que la mo i aci´on que despie an los juegos en los ni˜nos se debe al ap endizaje que p opo cionan (y es a mo i aci´on es deseable al en en a se a un ap endizaje). Los ideojuegos ense˜nan, en un ni el subyacen e, a ecopila in o maci´on y oma decisiones ´apidamen e, desa olla es a egias pa a supe a p oblemas o a coope a con o os jugado es. En cuan o a las di e en es o mas de ap ende , el modelo de e e encia e´o ico 8LEM (Eigh Lea ning E en s Model) [8] desc ibe el ap endizaje a pa i de ocho e en os de ap endizaje b´asicos, siendo un e en o de ap endizaje la desc ipci´on de la ac i idad de un alumno y un maes o en un con ex o educa i o. Los ocho e en os b´asicos son los siguien es: Imi aci´on: Obse a y, pos e io men e, imi a . El p o eso si e como modelo, pe o es e modelo no iene po qu´e se suyo. Recepci´on: Recibi in o maci´on emi ida po el p o eso in encionadamen e pa a ense˜na . Eje cicio: En campos en los que hay que au oma iza habilidades, se ap ende p ac i- cando. El u o debe guia y p opo ciona eedback adecuado. Explo aci´on: Ap ende median e p opia in es igaci´on con cie a libe ad, buscando en- e da os. El p o eso p opo ciona ´ıa uen es de in o maci´on adecuadas. 6 Expe imen aci´on: P ueba y e o , es deci , manipula el en o no y obse a consecuen- cias. El alumno p oba ´ıa as´ı odas las combinaciones posibles o aquellas que conside e in e esan es. C eaci´on: C ea nue o con enido, donde el ´e mino “nue o” se e ie e al alumno, no necesa iamen e con enido que no es ´e ya c eado po ninguna o a pe sona. Au o e lexi´on: Re lexiona sob e los p opios p ocesos cogni i os. Deba e: Ap ende median e in e acciones sociales, como deba es en los que se de iende una posici´on an e un con lic o, y es ´an p omo idos y mode ados po un u o . La in e acci´on puede se as´ınc ona (como en un o o) o s´ınc ona. Como ya se ha dicho, el desa ollo de juegos se ios es mul idisciplina . Po an o, si se quie- e desa olla un so wa e educa i o (po ejemplo), con iene conoce alguna de es as eo ´ıas pa a pode aplica los p incipios al desa ollo. Tambi´en ela i o a es e campo, el a ´ıculo [9] y o os esul ados an´alogos p oponen m´as cla es pa a un juego educa i o de ´exi o: p o- po ciona eedback inmedia o, ene g an ni el de in e acci´on, desa ´ıo y compe i i idad; y consegui que el usua io enga mo i aci´on in ´ınseca pa a juga . Como se indica en [1], un juego se io ambi´en puede se u ilizado a pa i de mo i aci´on ex ´ınseca (usa la aplicaci´on como he amien a pa a consegui cie a me a). Po ejemplo, un es udian e que quie e supe a una p ueba: u iliza la aplicaci´on pa a es udia y ap oba el examen, y despu´es ya no iene la necesidad de usa la. En el dise˜no de ideojuegos y juegos se ios in e ienen muchos o os ac o es. Adem´as de los ob ios (como pod ´ıa se de ini el p´ublico obje i o) hay o os como pensa en el pe il de los posibles jugado es (Ba le [10] public´o un modelo pa a juegos MUDs basado en kille s, achie e s,socialize s yexplo e s) y la adap aci´on del juego a cada ipo. Tambi´en hay que conside a aspec os como la necesidad de supe isi´on po pa e de un ins uc o , el en o no donde se debe juga , la posibilidad de ol e a juga (algunos juegos es ´an dise˜nados pa a juga una sola ez; o os, pa a juga a ias eces) o el iempo necesa io pa a juga (el iempo necesa io pa a cada pa ida es un aspec o impo an e). Las ideas y a ´ıculos sob e juegos se ios son en la ac ualidad muy nume osos. La aplicaci´on que se explica en es a memo ia ha seguido algunos de los concep os expues os en es a secci´on in oduc o ia, con mecanismos muy simples pe o que (se p e ende) mejo an la expe iencia de usua io espec o a las p ime as e siones que se implemen a on, donde no se u ie on en cuen a es os concep os. 1.3. In oducci´on a la aplicaci´on desa ollada Hay di e en es a ´ıculos sob e el p oceso de es udio de cu sos elacionados con las ciencias de la compu aci´on. Po ejemplo, en [11] se p esen an los esul ados de una encues a en la que pa icipa on m´as de 500 es udian es y p o eso es, con el obje i o de encon a aquellos pun os que m´as cues an a los es udian es de los p ime os cu sos de in o m´a ica. Es e a ´ıculo llega a la conclusi´on de que muchos alumnos desa ollan concep os supe iciales sob e la p o- g amaci´on (dominan la sin axis de cie o lenguaje de p og amaci´on y dominan ins ucciones aisladas) pe o allan al in eg a es o en p og amas comple os que esuel an un p oblema. Adem´as, los esul ados de la encues a asegu aban que los concep os que m´as di ´ıciles esul- aban e an di idi un p og ama en subp og amas, pun e os, ecu si´on y ipos abs ac os de 7 da os (TADs). En cuan o a m´e odos de ap endizaje, el p e e ido es basa se en p og amas de ejemplo, y des acan los m´e odos p ´ac icos sob e los e´o icos, aunque la eo ´ıa sea ambi´en impo an e. En odo caso, en ende las es uc u as de da os y los algo i mos m´as b´asicos es imp es- cindible pa a cualquie es udian e de in o m´a ica. En p ime luga , conoce los pe mi e oma la mejo decisi´on de dise˜no en e a un p oblema en cuan o a e iciencia y simplicidad. Pe o, m´as all´a de es o, en ende su uncionamien o en p o undidad pe mi e pode implemen a modi icaciones de los mismos. Es o si e pa a adap a los a p oblemas conc e os en los que las es uc u as o algo i mos necesa ios di ie en en alg´un pun o de los que se es udian como base, pe o la idea subyacen e es simila y puede se usada pa a esol e dicho p oblema. I o mando es a capacidad pa a pensa en qu´e usa pa a esol e el p oblema, as´ı como hace que el ap endizaje sea g adual y comenza po c´odigos sencillos, es lo que puede expli- ca que se es udien algo i mos que no se usan al ene ya implemen aciones mejo es (aunque hay una discusi´on sob e si la sencillez de c´odigo jus i ica su ense˜nanza en e a ine iciencia e inu ilizaci´on del mismo en el a ´ıculo [12]). En muchos cen os se man iene la ense˜nanza de los algo i mos de o denaci´on de complejidad cuad ´a ica O(n2). An e una p ime a ap oxima- ci´on, es in e esan e comp ende es os algo i mos pa a despu´es pode pasa al es udio de los algo i mos ´op imos en cuan o a complejidad O(nlog n), pe o menos in ui i os. En cualquie caso, no hay duda de la impo ancia de las asigna u as elacionadas con es- os concep os. Pa a muchos es udian es, la mejo o ma de en ende el uncionamien o de un algo i mo es e la aplicaci´on del mismo a un caso conc e o, lo que hace mucho m´as in ui i o el c´odigo asociado y pe mi e, incluso, que no sea necesa io memo iza lo en absolu o. Es o se elaciona con el a ´ıculo [11], donde no des aca especialmen e el m´e odo de ap endizaje de isualizaciones in e ac i as, pe o iene una buena acep aci´on (3.3 sob e 5, en l´ınea con o os m´e odos a excepci´on del ya mencionado uso de p og amas de ejemplo). Su gen as´ı in e e- san es aplicaciones que mues an el lujo de cie os algo i mos o la isualizaci´on de algunas es uc u as de da os: en [13] se p esen a un isualizado de es uc u as de da os a ni el con- cep ual (po ejemplo, los ´a boles se p esen an de la o ma esquem´a ica habi ual en luga de mos a el con enido de la memo ia del o denado ). El usua io puede ealiza acciones sob e es as es uc u as de da os y ap ecia c´omo an cambiando de o ma concep ual. En de ini i a, su gen aplicaciones que apo an un eedback mucho m´as isual que he amien as ´ıpicas de depu aci´on de c´odigo (debugging). Todo es o ha se ido de mo i aci´on pa a implemen a un juego (con m´as ca ga educa i a que l´udica) que explique algunos de los algo i mos b´asicos y es uc u as de da os p incipales de las ciencias de la compu aci´on. La in enci´on es simula la aplicaci´on del algo i mo sob e un caso conc e o y alea o io de en ada, siendo el usua io el que hace acciones simila es a las que ha ´ıa un o denado en ese caso conc e o. Po ejemplo, pa a o denaci´on po inse ci´on pod ´ıamos pensa que la ase en la que se hace hueco al elemen o a inse a consis e en que el alo de una posici´on se desplaza a la posici´on siguien e, cuando ealmen e se ob iene el alo de la posici´on iy se copia en la posici´on i+ 1. Es o, de o ma in e ac i a, se puede modela haciendo click en dicha posici´on iy a as ando a la posici´on i+ 1, lo que copia ´ıa el alo . Es as me ´a o as cla amen e no in e ienen en la comp ensi´on del algo i mo (se ´ıa simplemen e una peque˜na abs acci´on), y podemos deci que el usua io es ´a haciendo acciones simila es a las que ha ´ıa el o denado sob e su memo ia. Con la desc ipci´on dada, el juego se engloba ´ıa en el g´ene o de juegos de l´ogica o puzzles. 8 Cap´ı ulo 2 Algo i mos e In e acci´on 2.1. In oducci´on En es e cap´ı ulo se explica ´a la in e acci´on pedida en cada uno de los juegos implemen- ados en la aplicaci´on, eco demos: o denaci´on po inse ci´on, o denaci´on po el m´e odo de la bu buja, o denaci´on po selecci´on, o denaci´on po mezclas (pa e de la mezcla de dos lis as o denadas) y ´ecnica de la en ana deslizan e. Pa a cada uno de ellos, se mues an las ideas que ansmi e el u o ial asociado en el juego y se explica la in e acci´on eque ida, ponien- do ambi´en un ejemplo. El dise˜no y es uc u a global de la aplicaci´on, jun o con diag amas UML, se explica en el siguien e cap´ı ulo; se deja es e pa a lo espec´ı ico de los algo i mos implemen ados. Adem´as de lo mencionado, se explica pa a cada juego c´omo se ha ealizado el con ol del lujo; es deci , el con ol del a ance de la simulaci´on del algo i mo po pa e del usua io, as´ı como el con ol de la consis encia del modelo in e no en odo momen o espec o a la is a, es o es, espec o al es ado de la es uc u a de da os mos ada en la pan alla. Se ha in en ado que odas es as im´agenes que se adjun an cub an lo mejo posible odas las opciones y di e en es in e acciones de la aplicaci´on. En pa icula , se in en a mos a en es a memo ia an o los di e en es ex os sin pis as ac i as como aquellos en los que se han ac i ado las pis as (es a ´ecnica de adap aci´on de la di icul ad se explica con de alle en el cap´ı ulo 3). Pa a e ambi´en la de ecci´on an o de in e acciones e ´oneas como de in e acciones co- ec as o las di e en es pun uaciones esul an es en unci´on de los acie os y allos du an e el juego y del iempo empleado, se adjun a aqu´ı un ´ıdeo conjun o de oda la expe iencia en la aplicaci´on sob e la pa e de los u o iales y de los algo i mos. A lo la go del ´ıdeo se incluyen acciones inco ec as pa a mos a la ac i aci´on de las pis as. El ´ıdeo es ´a disponible en h ps://you u.be/K PyXDBppLQ An es de pasa a analiza cada algo i mo, una obse aci´on que ald ´a pa a odos los juegos es que las posiciones de los a ays se inicializan con alo es alea o ios en e -99 y 99. En el caso de o denaciones, el usua io end ´a que o dena es os alo es de meno a mayo simulando el algo i mo que es ´e p ac icando; en el caso de la ´ecnica de la en ana deslizan e, se ope a con sumas y es as de los alo es, ya que se ilus a la ´ecnica median e el p oblema de ob ene la suma m´axima de kelemen os consecu i os del a ay. 15 2.2. O denaci´on po inse ci´on En o denaci´on po inse ci´on, uno de los p ime os algo i mos es udiados, se dis inguen es ases en el juego, as´ı como las es e apas asociadas en el algo i mo que comp ueba que el usua io in e acciona co ec amen e. Es e algo i mo pe enece a o denaci´on na u al: se ealizan menos ope aciones cuan o m´as o denado es ´e inicialmen e el a ay. La complejidad es O(n2). Figu a 2.1: Diag ama de lujo co espondien e a o denaci´on po inse ci´on, con ano aciones sob e la in e acci´on eque ida. 2.2.1. Tu o ial del juego Se in en an ense˜na las bases del algo i mo y de la in e acci´on pedida con las siguien es e apas del u o ial: An es de en a en las ases del algo i mo, se in oduce o denaci´on po inse ci´on. Se dis inguen dos pa es en el a ay, una p ime a que siemp e es ´a o denada (inicialmen e con el p ime elemen o, y es ´a indicada en el juego usando colo e de) y una segunda pa e sin es a necesa iamen e o denada (indicada en el juego en colo blanco). Se indica que la in enci´on es, en odo momen o, inse a den o de la pa e o denada el p ime elemen o de la segunda pa e, has a que el a ay quede comple amen e o denado. 16 Figu a 2.2: Ideas b´asicas iniciales en el u o ial de o denaci´on po inse ci´on. En la siguien e e apa del u o ial, comienzan las animaciones que explican las es ases que se epi en en el algo i mo y los es ipos de in e acci´on usados en el juego. 1. Elegi la siguien e posici´on a inse a y gua da la en una a iable auxilia . En la e apa 1 se pide al usua io busca la siguien e posici´on cuyo alo se inse a ´a en la pa e o denada del a ay, y a as a dicha posici´on a la a iable auxilia ( ep esen ada po una posici´on sin da os y colocada en el juego ue a del a ay). Se explica que es e paso es pa a e i a pe de el alo a inse a , ya que a a se sob esc i o. Figu a 2.3: Paso 1: gua da el alo de la posici´on a inse a den o de la a iable auxilia . La animaci´on mues a el p oceso de a as a la posici´on con el alo -9. 2. “Hace hueco” en la pa e o denada del a ay al elemen o a inse a . En es e segundo paso se pide a as a , mien as sea necesa io, la posici´on j−1 a la posici´on jpa a copia el alo del a ay en una cie a posici´on a la siguien e. Es e p oceso, aco de con el algo i mo, se ealiza comenzando po la posici´on i(siendo ila posici´on del elemen o a inse a ) y yendo hacia el comienzo del a ay ( isualmen e, hacia la izquie da). Se a indicando la posici´on ac ual en colo ama illo pa a hace m´as isual el p oceso. 17 Figu a 2.4: Animaci´on que a as a la posici´on 0 a la 1 pa a eplica el alo 75. Es necesa io es e desplazamien o po que −9<75. Se pie de el alo -9 del a ay, pe o se man iene isible en odo momen o en la a iable auxilia . 3. Inse a el elemen o en la pa e o denada. Cuando en el segundo paso se llegue a un elemen o que ya es meno que el elemen o a inse a o se alcance el inicio del a ay, la segunda ase e mina (n´o ese que puede ocu i que la e apa 2 sea ac´ıa). En ese momen o, pod emos inse a o denadamen e el alo co espondien e a la e apa 1 de o ma que la p ime a pa e del a ay (ya o denada) c ece una unidad. Pos e io men e, el p oceso uel e a la e apa 1. La in e acci´on pedida es a as a la a iable auxilia a la posici´on donde se debe inse a el alo (es deci , donde se ha ealizado hueco). Figu a 2.5: Animaci´on a as ando el alo de la a iable auxilia hacia la posici´on 0 de la pa e o denada (la co ec a en es e caso), copiando el alo o igen en la posici´on des ino y log ando po an o que la pa e o denada del a ay c ezca en una unidad. 2.2.2. In e acci´on de allada con un ejemplo El u o ial mues a las ideas b´asicas del algo i mo y de la in e acci´on pedida, pe o eamos la in e acci´on de o ma m´as de allada, ya con un ejemplo en el que se e a al usua io a simula el algo i mo a pa i de un inpu alea o io. Se in en an aba ca odos los posibles eedbacks de odas las e apas, po lo que en las im´agenes siguien es se ha p o ocado la ac i aci´on y desac i aci´on de las pis as pa a mos a los di e en es ex os. 18 Figu a 2.6: Paso 1: Lle a la siguien e posici´on a inse a a la a iable auxilia . Figu a 2.7: Paso 2: Desplaza copiando pa a hace hueco al 61 en la pa e o denada ( ex o sin pis as). 19 Figu a 2.8: Paso 2: Desplaza copiando pa a hace hueco al 61 en la pa e o denada ( ex o con pis as). Figu a 2.9: Paso 3: A as a la a iable auxilia a la posici´on co ec a pa a copia el alo , y log a un suba ay o denado de 2 posiciones. El p oceso ol e ´ıa a empeza , eniendo que inse a el alo -50 en la pa e o denada. 20 Un ´ul imo comen a io es que si la ase 2 es ac´ıa (no hacen al a desplazamien os), en onces no se pide ninguna in e acci´on en es a ase. Las pa es 1 y 3 pe manece ´ıan iguales, aunque en es e caso sean acciones innecesa ias al es a gua dando un alo en una a iable auxilia e inmedia amen e ecupe ando el alo . Se ha implemen ado as´ı po homogeneidad y pa a omen a la idea de ac ua de o ma me ´odica. 2.2.3. Algo i mos de con ol y comp obaci´on El modelo se co esponde con la clase Inse ionSo Manage , que se comunica p inci- palmen e con A ayPosInsSo y que iene los siguien es a ibu os y m´e odos. A ibu os. • alues:A ay con los alo es a o dena , que se a modi icando aco de a las ac- ciones del usua io. •s epNumbe : N´ume o de e apa en que se encuen a el p oceso. •nex Posi ionS ep1: En e o que indica la siguien e posici´on a inse a en la pa e o denada. •numbe ToInse : Valo a inse a en la pa e o denada. •mo esS ep2: N´ume o de acciones eque idas en el paso 2. Se conside a acci´on de la segunda e apa a cada uno de los desplazamien os de una posici´on a la siguien e pa a copia el alo . •comple edS ep2: Acciones ya comple adas en el paso 2. •posS ep3: Posici´on del a ay donde inse a el alo en la e apa 3. M´e odos. •M´e odos de inicializaci´on, ge yse . • es a (): Reinicia los alo es pa a empeza un nue o juego. La e apa pasa a se la 1, la siguien e posici´on a inse a pasa a se la segunda (posici´on 1) e indica ambi´en que no se ha comple ado ning´un paso en la e apa 2. •s ep1Comple ed(): Debe se llamado cuando el usua io comple a con ´exi o la e apa 1. Recalcula y ac ualiza sus a ibu os, cambiando s epNumbe al alo 2, gua dando el alo que hay que inse a en el a ibu o numbe ToInse , calcu- lando la posici´on donde hay que inse a ese alo (median e el m´e odo p i ado indPosToInse () que se explica m´as adelan e) y calculando po ´ul imo el n´ume- o de desplazamien os necesa ios, usando la di e encia en e la posici´on po la que se encuen a el p oceso de o denaci´on y la posici´on en la que hay que inse a el alo , es deci , nex Posi ionS ep1 - indPosToInse (nex Posi ionS ep1). Se usa una a iable auxilia pa a e i a los c´alculos edundan es que p o oca ´ıa llama a la unci´on indPosToInse () dos eces. •s ep2Posi ion(): Indica la siguien e posici´on con la que se debe ´ıa in e acciona en la e apa 2. •subS ep2Comple ed(): Debe se llamado as cada mo imien o co ec o del usua- io en la e apa 2. Ac ualiza sus a ibu os, como el a ay alues. Inc emen a el a ibu o del n´ume o de desplazamien os ya comple ados en la e apa 2 y, de o ma an´aloga, dec emen a el n´ume o de desplazamien os es an es. 21 •s ep2Comple ed(): Debe se llamado as comple a oda la e apa 2. Ac ualiza sus a ibu os indicando que la e apa es aho a la e ce a, e inicializando el n´ume o de desplazamien os comple ados en la e apa 2 a ce o, de ca a a la siguien e i e aci´on. •s ep3Comple ed(): Llamado as comple a la e apa 3. Recalcula los a ibu os, ac ualizando el a ay median e alues[posS ep3] = numbe ToInse ; y de ol- iendo el es ado a la e apa 1. • inished(): De uel e un alo bool que indica si el p oceso de o denaci´on ha e minado. Bas a compa a si se es ´a en la e apa 1 pe o la siguien e posici´on a inse a coincide ya con la longi ud del a ay (es e ama˜no iene dado como cons an e en la clase U ili ies). • indPosToInse (): M´e odo p i ado que ayuda a ecalcula los a ibu os as inaliza la e apa 1. Se ealiza una b´usqueda desde una cie a posici´on o igen del a ay hacia el comienzo del mismo, has a que se alcanza el inicio de la es uc u a o has a que se encuen a una posici´on al que su alo es meno o igual que el alo de la posici´on o igen. Es deci , es e m´e odo calcula la posici´on obje i o a la que iene que llega el siguien e elemen o a inse a . Figu a 2.10: C´odigo del m´e odo p i ado indPosToInse () . 2.3. O denaci´on po selecci´on O o de los algo i mos de complejidad cuad ´a ica es la o denaci´on po selecci´on. Tambi´en se dis ingue en e una pa e inicial o denada (inicialmen e ac´ıa e indicada en el juego en e de) y el es o del a ay (indicado en el juego en blanco); el algo i mo consis e en busca el m´ınimo de es a segunda pa e e inse a lo en la p ime a pa e, in e cambiando los alo es de las dos posiciones que in e ienen. Una p opiedad de es e algo i mo es que siemp e ealiza el mismo n´ume o de ope aciones (con la sal edad de posibles in e cambios “ i iales” (una posici´on con s´ı misma) que se pod ´ıan e i a ). La in e acci´on que se pide al usua io en es e juego es, p obablemen e, la m´as sencilla de odas, como se e ´a a con inuaci´on. Como ya se ha dicho, es a implemen aci´on de o denaci´on po selecci´on ealiza siemp e el mismo n´ume o de ope aciones. Es o se ep esen a cla amen e en el eedback que se da al comple a el juego, ya que siemp e se necesi an el mismo n´ume o de acciones. Sin emba go, es o no debe con undi al usua io: la in e acci´on en es e juego pe mi e que el usua io acceda al elemen o m´ınimo de la segunda pa e de un is azo, sin consumi acciones. Es as ope aciones en una compu ado a s´ı hay que ealiza las. 22 Figu a 2.11: Diag ama de lujo de o denaci´on po selecci´on, con ano aciones sob e la in e - acci´on del juego. Figu a 2.12: Diag ama de lujo de m´as bajo ni el de o denaci´on po selecci´on, de allando la ins ucci´on del diag ama an e io swap(a[i], a[posMin(a[i:])]). 23 2.3.1. Tu o ial del juego En p ime luga , se p esen a una in oducci´on a es a o denaci´on: Figu a 2.13: In oducci´on del u o ial de o denaci´on po selecci´on. Una ez comenzado el juego, se p esen an dos opciones de in e acci´on: 1. Si el m´ınimo de la segunda pa e no queda ya en la p ime a posici´on de es a pa e no necesa iamen e o denada, se busca dicho alo y se a as a a la siguien e posici´on a o dena : Figu a 2.14: El m´ınimo de la segunda pa e (al inicio, la segunda pa e coincide con odo el a ay) es a as ado a la siguien e posici´on a o dena . 2. Si el m´ınimo de la segunda pa e en alguna e apa coincide con su posici´on des ino (es deci , queda ya o denado), la in e acci´on que se equie e es simplemen e hace click en esa posici´on: 24 •posSo ed: Posici´on has a la cual se iene segu idad que el comienzo del a ay es ´a o denado. Es deci , el ango [0,posSo ed) es ´a o denado. •posBubble: Posici´on del elemen o que hay que in e cambia con su posici´on an e- io , es deci , con el que hay que in e ac ua en cada momen o. M´e odos. •M´e odos de inicializaci´on, ge yse . •ini ialize(): Inicializa el a ibu o posBubble con ayuda del m´e odo p i ado que se explica ´a pos e io men e calcula ePosBubble(), pasando como pa ´ame o el alo U ili ies.LENGTH-1pa a que la b´usqueda se ealice en oda la es uc u a. •subS epComple ed(): Ac ualiza los a ibu os as cada in e acci´on co ec a, in- e cambiando alues[posBubble] y alues[posBubble-1]y ecalculando la si- guien e posici´on con la que in e acciona median e calcula ePosBubble() con el pa ´ame o adecuado. •s epComple ed(): Ac ualiza los a ibu os cada ez que el usua io comple a un eco ido desde el inal del a ay has a el comienzo in e cambiando posiciones. Tend emos una posici´on adicional o denada, y pa a la siguien e posici´on con la que hay que in e acciona se lanza una b´usqueda en odo el a ay de nue o median e calcula ePosBubble(). • inished(): Indica si el p oceso de o denaci´on ha e minado. Se implemen a com- p obando que la b´usqueda del siguien e elemen o con el que in e acciona llega al inicio de la es uc u a, es deci , el a ay ya es ´a o denado. • es a (): Reinicia el modelo, inicializando los a ibu os. Se ac ualiza a 0 la posici´on has a la cual enemos un suba ay o denado con segu idad. •calcula ePosBubble(): M´e odo p i ado auxilia que busca desde la posici´on in- dicada en el pa ´ame o hacia el inicio del a ay el p ime pa de elemen os conse- cu i os (a, b) al que a > b. N´o ese que es e m´e odo auxilia se usa en muchos de los an e io men e explicados. Figu a 2.23: C´odigo del m´e odo p i ado auxilia que pe mi e implemen a muchos de los m´e odos es an es de es a clase. 2.5. O denaci´on po mezclas (1) La o denaci´on po mezclas (en ingl´es, me ge so ) es ya un algo i mo ´op imo en cuan o a complejidad en iempo (O(nlog n)). Es e algo i mo, pe enecien e al g upo de los algo i mos “Di ide y ence ´as”, ue in en ado po John on Neumann en 1945. Se basa en dos ideas: 31 ecu si´on y mezcla de dos lis as o denadas. En la escena Me geSo 1 del juego se p e ende que el usua io abaje sob e la mezcla de dos a ays o denados. En es a escena, al p incipio, se p esen an dos a ays de cua o elemen os ya o denados, sepa ados en e s´ı. Debajo, se coloca la lis a (inicialmen e en blanco) sob e la que se cons- ui ´a el a ay o denado esul ado de la mezcla de las dos lis as supe io es. La in e acci´on consis e en pensa el ´ındice que se lle a en cada lis a en un momen o de e - minado (aunque es o se indica cla amen e usando colo es). Aho a, se compa a an los elemen- os de cada lis a en sus espec i os ´ındices (es deci , lis a0[indice0] ylis a1[indice1]). T as elegi el meno de los dos, dicha posici´on se a as a a la siguien e posici´on a comple a del a ay in e io . 32 Figu a 2.24: Diag ama de lujo de la mezcla de dos lis as o denadas. 2.5.1. Tu o ial del juego El u o ial de es e juego explica median e animaciones lo que se ha indicado en la in o- ducci´on an e io . Inicialmen e se explica el p op´osi o. Despu´es, comienzan las animaciones que mues an el p oceso. 33 Figu a 2.25: En p ime luga , se in oduce la mezcla de dos lis as o denadas. 1. Ambos ´ındices comienzan en ce o, y se compa an po an o las posiciones iniciales de ambos a ays. El alo in e io es el que se inse a en el a ay esul ado, median e una in e acci´on d ag-and-d op como habi ualmen e. Figu a 2.26: lis a0[indice0] = lis a0[0]= 9 <17 = lis a1[0] = lis a1[indice1], po lo que se a as a la p ime a posici´on del a ay 0 a la es uc u a esul ado. Se inc emen a el ´ındice de la p ime a lis a (indice0), indic´andolo en el juego con posiciones en g is ( e siguien e pun o). 2. Se compa an de nue o los alo es apun ados po los ´ındices co espondien es (uno de los dos ´ındices iene que habe cambiado). En el u o ial, la animaci´on mues a el desplazamien o del segundo elemen o, de nue o omando como o igen la p ime a lis a. 34 Figu a 2.27: El u o ial pasa a mos a que indice0 == 1u ilizando una posici´on en g is en la p ime a lis a. Como 13 <17, la animaci´on mues a que se debe a as a el alo 13 al a ay esul ado. 3. Pa a ilus a un ejemplo en el que se oma como o igen la segunda lis a, el u o ial con in´ua un paso m´as. 4. Finalmen e, aunque es muy in ui i o cu´ando a a acaba el juego, el u o ial e mina con la animaci´on del mo imien o inal, m´as bien pa a pode explica en el ex o asociado que el p oceso acaba cuando los ´ındices de ambas lis as o igen son iguales a su longi ud: 2.5.2. In e acci´on de allada con un ejemplo En la subsecci´on an e io ya se han explicado con su icien e de alle las in e acciones pedidas, usando el ejemplo del u o ial (que es un ejemplo ijo (es deci , no alea o io) y seleccionado con cuidado pa a se ilus a i o). Sin emba go, pa a e el ex o que se mues a al usua io du an e el juego, an o en su e si´on sin pis as como en su e si´on con pis as si el usua io se bloquea en un paso, eamos las dos p ime as in e acciones de o o ejemplo, con inpu alea o io: 35 Figu a 2.28: P ime a in e acci´on, con el ex o sin pis as: se indica que hay que a as a cie a posici´on de cie o a ay a las posiciones in e io es. Figu a 2.29: Segunda in e acci´on, p o ocando que se ac i en las pis as al alla a ias eces: se indica la posici´on y la lis a con la que se debe in e acciona . 2.5.3. Algo i mos de con ol y comp obaci´on La inicializaci´on de los alo es en es e caso es lige amen e dis in a al es o: como los dos a ays a mezcla ienen que es a ya o denados, cada posici´on no se puede inicializa de o ma indi idual, ya que depende de o as. La clase co espondien e al modelo de es a pan alla es Me geSo 1Manage , que in e - acciona p incipalmen e con A ayPosMe geSo 1. Se ha c eado en el modelo la es uc u a in e ac ionMe geSo 1 pa a encapsula la in o maci´on de la siguien e in e acci´on que se le pedi ´a al usua io: n´ume o de lis a donde es ´a la siguien e posici´on a inse a , as´ı como el ´ındice de la posici´on. Los a ibu os y m´e odos de Me geSo 1Manage son los siguien es. A ibu os. • alues0, alues1: Lis as con los alo es a mezcla . •index0,index1:´ Indices de las espec i as lis as. M´e odos. •M´e odos de inicializaci´on y ge . •s epComple ed(): Llamado as una in e acci´on co ec a, inc emen a el ´ındice adecuado. 36 •ge Nex In e ac ion(): De uel e un obje o in e ac ionMe geSo 1 que encap- sula la siguien e in e acci´on que debe hace el usua io. Se comp ueba si alguna de las dos lis as ha sido ago ada. Si ninguna de las dos es ´a ago ada, se busca aquella al que su ´ındice apun a al alo meno . Se adjun a imagen de es e m´e odo. •ge Nex Index(): De uel e la siguien e posici´on a ellena del a ay esul ado (index0 + index1). • inished(): Indica si el p oceso ha e minado, comp obando si el ´ındice de ambas lis as es igual a su longi ud. • es a (): Reinicia el juego, inicializando de nue o los a ibu os. Los ´ındices uel en a 0, y las lis as se c ean con nue os alo es alea o ios. 2.6. T´ecnica de en ana deslizan e 2.6.1. In oducci´on a la ´ecnica In o malmen e, la en ana deslizan e se pod ´ıa explica como una ´ecnica en la que una subes uc u a se desplaza po una es uc u a mayo . Po ejemplo, un suba ay que se des- plaza po un a ay (es deci , en cada caso se ienen en cuen a solamen e cie as posiciones consecu i as del a ay mayo ); ambi´en pod ´ıa se una peque˜na ma iz que se desplaza po una ma iz mayo . En de ini i a, la cla e de es a ´ecnica es que en cada mo imien o la sub- es uc u a solamen e cambia algunas de sus ca ac e ´ıs icas, y no odas, po lo que no hace al a ecalcula la ope aci´on asociada a la subes uc u a en cada paso, sino hace un c´alculo inicial y pos e io men e ajus a el c´alculo solamen e eniendo en cuen a los cambios que se han ealizado. Expliquemos es o con m´as de alle, usando el ejemplo que se ha implemen ado en el juego: dado un a ay de longi ud ncuyos alo es son n´ume os en e os, que emos encon a la suma m´axima de kelemen os consecu i os (pa a k≤n). Una posible implemen aci´on que de uel e el esul ado co ec o consis e en coge los kp ime os elemen os (posiciones 0 a k−1, ambas incluidas), suma los e inicializa el m´aximo a es e alo . Pos e io men e, se oman los ele- men os co espondien es a las posiciones 1 has a la k, se suman y se compa a el esul ado con el m´aximo inicializado an e io men e, omando como m´aximo p o isional el mayo alo de en e es os dos. El p oceso con in´ua, calculando en cada caso la suma de kelemen os consecu i os del a ay subyacen e y compa ando el esul ado con el m´aximo p o isional. Al inal, ob enemos el esul ado co ec o median e es e algo i mo de complejidad O(n·k). Pe o es a complejidad se puede educi , ya que se es ´an ealizando muchos c´alculos edundan es: al pasa de suma las posiciones ihas a k+i−1 (supongamos un ejemplo y un alo de 37 i al que k+isiga en ango) a suma las posiciones i+ 1 has a k+i(ambas incluidas), solamen e es ´an cambiando en la suma los ´e minos co espondien es a las posiciones i(cuyo alo desapa ece en la suma) y k+i(cuyo alo no es aba en la suma, y aho a apa ece). Po an o, la o ma adecuada de implemen a el p oceso se ´ıa hace el c´alculo inicial, pe o despu´es bas a con es a a la suma ya calculada el alo de la posici´on que deja de se conside ada, y suma a la suma ya calculada el alo de la posici´on que en a a se conside ada. Podemos e es o como una en ana (subes uc u a, suba ay) de longi ud k, que aba ca inicialmen e las posiciones iak+i−1, y que se desplaza una unidad “hacia adelan e”: aho a aba ca las posiciones i+1 a k+i. Bas a ´ıa en onces es a el ex emo izquie do de la en ana o iginal, y suma el alo de la posici´on del ex emo de echo de la misma, que ha pasado a conside a se. La complejidad en es e caso pasa a O(n). El caso de una ma iz (a ay bidimensional) es simila : al mo e una subma iz una uni- dad (una ila m´as, una ila menos, una columna m´as o una columna menos), en gene al (sal o casos ex emos, como conside a una subma iz ila y mo e la po ilas) hay elemen os que siguen es ando den o de dicha subma iz, mien as que o os s´ı que cambian. Bas a ´ıa hace el ajus e conside ando los elemen os que deja de aba ca la subes uc u a y aquellos que pasan a es a aba cados po ella. Es a ´ecnica ambi´en se puede adap a a p oblemas que no p esen an una elaci´on an ob ia con la misma: encon a anag amas de cie a palab a den o de un ex o. Si buscamos anag amas de una palab a de longi ud ken un ex o de longi ud n, se desplaza po el ex o (que es un a ay de ca ac e es) un suba ay de longi ud k. En es e caso, la ope aci´on asociada a la en ana es la ecuencia con que apa ecen las le as: inicialmen e se calcula la ecuencia de apa ici´on de los kp ime os ca ac e es, pe o al desplaza la en ana bas a con es a una apa ici´on al ca ac e que sale de la subes uc u a, y suma una apa ici´on al ca ac e que en a. Si las ecuencias de apa ici´on de la en ana coinciden con las ecuencias de apa ici´on de la palab a de la que buscamos anag amas, hemos encon ado un anag ama, es deci , una pe mu aci´on de los mismos ca ac e es. Figu a 2.30: C´odigo Py hon pa a el p oblema de la suma m´axima de kelemen os consecu i os de un a ay. Se adjun an comen a ios con las e apas que se dis inguen en la in e acci´on. 38 Figu a 2.31: Diag ama de lujo del p oblema de la suma m´axima de kelemen os consecu i os. Las ano aciones indican las di e en es e apas conside adas y la in e acci´on eque ida. 39 2.6.2. Tu o ial del juego En p ime luga , se expone el p oblema que ya se ha comen ado, as´ı como los elemen os con los que se a a in e acciona : Figu a 2.32: In oducci´on del u o ial del juego. Al pulsa el bo ´on pa a pasa al siguien e paso del u o ial, se pasa al paso 1 del algo i mo (se dis inguen dos pasos, donde el segundo iene es sube apas posibles): 1. Hace la suma inicial: el u o ial mues a la animaci´on de suma los p ime os kelemen- os, a as ando las posiciones al bo ´on e de de “+”. Figu a 2.33: Hace la suma inicial: se mues a la animaci´on de la suma de las es p ime as posiciones. En la imagen, ya se han sumado las dos p ime as posiciones (colo e de) y se es ´a sumando la e ce a posici´on. 2. Desplaza la en ana y compa a las sumas con el m´aximo p o isional. Es a e apa iene es sube apas, con es in e acciones asociadas: a) Desplaza la en ana (1): Se mues a la animaci´on que a as a el ex emo izquie - do de la en ana al bo ´on de la es a, pa a deja de ene en cuen a ese elemen o en la suma o al. 40 acie o o el e o del usua io; po ´ul imo, el e ce o ac ualiza las ins ucciones seg´un la e apa del juego y seg´un si se han ac i ado las pis as. Figu a 3.3: Todas las clases A ayPos implemen an las in e aces que pe mi en hace d ag- and-d op. Adem´as, he edan de MonoBeha iou , es deci , son sc ip s. Game. Tipo enume ado con un posible alo pa a cada juego y men´u, con un alo adicional pa a de ec a e o es. A ayCon olle yMe geSo 1Con olle . Ges ionan odos los bo ones que compo- nen el a ay de o ma global. Tambi´en ealizan median e c´odigo las animaciones del comienzo de cada juego. Me geSo 1Con olle es necesa io po que la dis ibuci´on que se p esen a en es a pan alla es dis in a al es o. Su m´e odo m´as impo an e es loca e(), que ecoloca las posiciones a su luga adecuado en la escena as cada acci´on del usua io. GameOp ions. Se enca ga de los bo ones de einicio y ol e hacia a ´as de odos los juegos. Conoce la acci´on que debe ealiza seg´un el pa ´ame o game que ecibe en los m´e odos es a Selec ed() ybackSelec ed(). SceneCon olle . Ges iona el cambio de escena y el cie e de la aplicaci´on al hace click en el bo ´on de sali . O he Op ionsCon olle . Con ola la animaci´on del pop-up del panel de o as opcio- nes, despleg´andolo u ocul ´andolo seg´un el bo ´on pulsado. SlidWindowNewMax. Es simila a los sc ip s que ienen los bo ones que con o man el a ay, es deci , A ayPos(Juego), aunque es e caso es algo excepcional. La az´on es que en la ac i idad de desplazamien o de en ana hay un elemen o adicional que s´ı admi e in e acci´on. As´ı, el bo ´on de nue o m´aximo necesi a ene un sc ip con c´odigo que se ejecu e al se pulsado pa a comp oba si esa in e acci´on es co ec a o no. El c´odigo se co esponde con su m´e odo newMaxBu onClicked(). ShowS a is ics. Realiza el olcado del ex o de los da os de endimien o al ´a ea de ex o p esen e en la pan alla de es ad´ıs icas, pa a pode mos a las. Se ayuda del m´e o- do ge S a is icsTex () de Da aManage , que a su ez iene una ins ancia de Playe con esa in o maci´on eque ida. Da aManage . Clase que ges iona los da os de la aplicaci´on. Se implemen a usando el pa ´on de dise˜no Single on pa a ene una ´unica ins ancia en odo el juego (adem´as, 47 es segu o en e a concu encia). Sus a ibu os son la p opia ins ancia (como en cual- quie Single on), el lock de p o ecci´on, una a iable bool loaded que indica si ya se han ca gado los da os (pa a ca ga los una sola ez aunque se eciban m´as pe iciones), a ias u as pa a la ges i´on de a chi os, a ibu os pa a ges i´on de pun uaciones y de es ad´ıs icas, a ibu os pa a con ola el sis ema de log y un en e o con el es ado de las pis as (solamen e se mues an las pis as en el es ado 2). Adem´as iene una ins ancia de Playe , encapsulando la in o maci´on de un usua io. En la ca ga de da os (m´e odo loadDa a()) se usa la clase Bina yFo ma e , y es po es o po lo que se ha explicado unos p´a a os an es que cie as clases son se ializables. Da aManage ambi´en se en- ca ga de ges iona las es ad´ıs icas de un juego, como la pun uaci´on. Cuando un juego acaba, el m´e odo gameFinished() indica a la ins ancia de Playe que ac ualice sus es ad´ıs icas a˜nadiendo las de la pa ida que acaba de e mina . Tambi´en iene m´e odos des inados al sis ema de log, aunque es os se explica ´an m´as adelan e. Po ´ul imo, es el enca gado de gua da los da os pa a que la p ´oxima ez que se en e a la aplicaci´on las es ad´ıs icas sigan disponibles. Pa a es o, de nue o se usa Bina yFo ma e y se gua da la ins ancia de Playe median e el m´e odo Se ialize(). LoadDa a. Al ab i la aplicaci´on, ejecu a la ca ga de da os, indicando ambi´en al Da aManage la u a Applica ion.pe sis en Da aPa h. U ili ies. Clase con cons an es y con algunos m´e odos auxilia es, como comp oba si dos ec o es ep esen an posiciones ce canas (con cie o ma gen EPS_NEAR) o ans o - ma una a iable de ipo TimeSpan a segundos. 3.1.2. Diag amas de secuencia de dos p ocesos p incipales En p ime luga se mues a un diag ama de secuencia ilus a i o pa a el caso de uso de consul a es ad´ıs icas. Es o pe mi e en ende mejo y complemen a lo expues o en la secci´on an e io ela i o a las es ad´ıs icas. Po ´ul imo, se ep esen a median e o o diag ama de secuencia la anidaci´on de las llamadas en el p oceso de comp oba si una in e acci´on del usua io es co ec a. Se oma como ejemplo el juego de o denaci´on po selecci´on y se mues a uno de los posibles eco idos (no se conside an en el diag ama las dis in as opciones de e apas en el juego o in e acci´on co ec a o e ´onea debido a cues iones de espacio). Consul a es ad´ıs icas. Uno de los casos de uso de la aplicaci´on es consul a las es- ad´ıs icas del usua io. La cadena de llamadas que se gene a da luga al siguien e diag ama de secuencia. 48 Figu a 3.4: Diag ama de secuencia pa a el caso de uso de consul a es ad´ıs icas. Se conside an solo implemen ados dos juegos po cues iones de espacio, pe o las llamadas desde la ins ancia de Playe segui ´ıan al es o de ins ancias GameIn o(Juego). Comp oba in e acci´on. O a de las unciones esenciales que debe ealiza la aplicaci´on es e i ica que las acciones que ealiza el usua io son co ec as. Se adjun a un diag ama de secuencia co espondien e a una de es as comp obaciones. 49 Figu a 3.5: Diag ama de secuencia de la comp obaci´on de una in e acci´on del usua io en el juego de o denaci´on po selecci´on. Se conside a solo un eco ido de las dis in as opciones que se p esen an y se mues a la anidaci´on de las llamadas en el caso en que la siguien e posici´on no es ´a ya o denada, el usua io in e acciona co ec amen e, el juego no inaliza as esa in e acci´on y el a ay con el log no se llena al esc ibi una posici´on adicional. 3.2. Feedback p opo cionado y o as uncionalidades 3.2.1. Feedback Como se ha discu ido analizando a ´ıculos en el cap´ı ulo 1 de es a memo ia, muchos au o es coinciden en la necesidad de p opo ciona eedback adecuado, as´ı como adap a la di icul ad del juego a la habilidad del usua io. Po ejemplo, es os emas se discu en en [1], [6] o [3]. El juego que se p esen a en es a memo ia iene es ipos de eedback de di e en e na u aleza: Acie os/E o es: T as cada acci´on, el sis ema in o ma de si la in e acci´on es co ec a 50 o e ´onea median e ex o en la pan alla del juego. In e namen e, se ac ualiza la pun ua- ci´on que se mues a al inaliza dicho juego y se ac ualiza el modelo de adap aci´on de la di icul ad din´amicamen e. Es os dos concep os que se acaban de menciona cons i uyen el es o de o mas de eedback de la aplicaci´on, y se a a ´an a con inuaci´on. Pun uaciones y es ad´ıs icas: Pa a in oduci m´as componen e l´udico y ´ıpico de juegos, se inco po an pun uaciones y es ad´ıs icas. Al acaba cada pa ida se mues a el iempo que se ha a dado en comple a la y una pun uaci´on asociada que depende de dicho iempo y del n´ume o de acie os y de e o es. Finalmen e, ambi´en se mues a el n´ume o de acciones necesa ias pa a comple a el juego (es e ´ul imo da o es m´as bien solo in o ma i o). En cuan o a la pun uaci´on, se busca un equilib io en e con igu a- ciones iniciales. Si es sencilla, se eque i ´an menos acciones y po an o hab ´a menos opo unidades de suma pun os, pe o es as con igu aciones sencillas ambi´en debe ´ıan comple a se en menos iempo, penalizando menos la pun uaci´on. Con igu aciones a- les que son necesa ias muchas acciones pa a acaba lle a ´ıan a una mayo can idad de acie os ( ambi´en de allos, segu amen e) pe o ambi´en penaliza ´ıa m´as la pun uaci´on po el iempo a dado. Figu a 3.6: Imagen del eedback p opo cionado al e mina un juego, en es e caso o denaci´on po selecci´on. Adem´as del sis ema de pun uaciones, se gua dan es ad´ıs icas in e esan es pa a el usua- io desde el pun o de is a e´o ico. Po ejemplo, pa a cada pan alla se cuen an el n´ume o de pa idas inalizadas, el n´ume o de acciones eque idas o ales en dichas pa idas o el iempo o al empleado. Combinando es os da os, podemos mos a al usua io es ad´ıs i- cas como el n´ume o medio de acciones eque idas en una pa ida. Tambi´en podemos consegui da os sob e su endimien o, como el iempo medio empleado pa a cada acci´on. Se ha decidido mos a en la pan alla de “Es ad´ıs icas”, pa a cada juego implemen a- do, la mayo pun uaci´on conseguida, el n´ume o de pa idas e minadas, la media de acciones po juego, el iempo o al empleado en dicha pan alla y la media de iempo empleado en cada acci´on. Si un juego no iene pa idas e minadas, se indica que no hay da os. 51 Figu a 3.7: Cap u a de pan alla de las es ad´ıs icas mos adas. Adap aci´on din´amica de la di icul ad: Segu amen e el m´e odo m´as e icaz pa a es e ipo de aplicaciones. En es e caso, se basa en p opo ciona mayo o meno in o maci´on en el ex o que se mues a en cada e apa de cada juego. Se puede modela como un dia- g ama de es es ados, pe o donde solamen e se han implemen ado dos salidas (mos a pis as o no). El diag ama de es ados es el siguien e. Figu a 3.8: Diag ama de es ados co espondien e al sis ema de adap aci´on din´amica de la di icul ad. En dicho diag ama ap eciamos: •Es ado “Sin pis as ( ue e)”: Es el es ado inicial. P ime o se e a al usua io a esol e el p oblema sin pis as. Mien as se acie e, el sis ema pe manece en es e es ado; an e un e o , el sis ema cambia al siguien e es ado que se a a explica a con inuaci´on, donde segui ´a sin mos a las pis as a´un. •Es ado “Sin pis as (d´ebil)”: Se sigue sin mos a ayuda ex a, pe o el usua io ya ha come ido un allo. An e un acie o, se uel e al es ado an e io men e explicado; sin emba go, si alla, ya sabemos que ha enido dos allos seguidos. Pa a e i a la us aci´on del usua io y que se quede bloqueado en alg´un paso, el es ado cambia 52 a “Con pis as” y el ex o se ac ualiza dando m´as in o maci´on, como la posici´on con la que hay que in e acciona o el mo imien o que hay que ealiza . •Es ado “Con pis as”: Las ´ul imas dos in e acciones (al menos) han sido allidas. Las pis as se ac i an y se mues a m´as in o maci´on in en ando que el usua io encuen e la in e acci´on co ec a. Es o, a su ez, le puede da m´as pis as pa a en ende la in e acci´on pedida en gene al y con ello el algo i mo en es udio. Si se acie a, se desac i an las ayudas comple amen e (es o es, se uel e al es ado “Sin pis as ( ue e)”); mien as se alle, el sis ema se man iene en dicho es ado con pis as. Pa a implemen a es o, la clase Da aManage gua da un a ibu o en e o hin sS a e, donde 0 se co esponde con “Sin pis as ( ue e)”, 1 se co esponde con “Sin pis as (d´ebil)” y 2 se co esponde con el es ado “Con pis as”. En el cons uc o y an e nue os comienzos de juegos, como ya se ha comen ado, se inicializa a 0; po o o lado, an e cada in e acci´on, se ac ualiza el alo de la siguien e o ma. Si se ha ace ado, se pasa al es ado 0; si no, el es ado se inc emen a en una unidad, con la excepci´on de es a ya en el es ado 2 (pis as ac i as) en cuyo caso el a ibu o no cambia. Po ´ul imo, el m´e odo de Da aManage showHin s() indica si se deben mos a las pis as o no: bas a compa a el a ibu o hin sS a e con el alo 2. En los m´e odos upda eIns uc ions() que se comen a on an e io men e, el s ing asociado a las ins ucciones adquie e un alo u o o seg´un lo que de uel e es e m´e odo showHin s(). 3.2.2. Log con la in e acci´on Po ´ul imo, se almacena un a chi o de ex o con oda la in e acci´on del usua io. Es o en e siones pos e io es del juego pod ´ıa ene u ilidad pa a consegui es ad´ıs icas m´as elabo a- das. Sin emba go, el obje i o del log en es e abajo es se i de ayuda en las p uebas inales con usua ios. Se ecoge la secuencia de acciones ealizadas en cie a pan alla (momen o en que sucede medido en segundos desde que el usua io en a en la aplicaci´on, se indica si la in e acci´on es co ec a y ambi´en se egis an o as acciones como el inal o el einicio del juego). Pos e io - men e, los a chi os se analiza ´an pa a saca conclusiones de los usua ios que pa icipan en las p uebas. En cuan o a la implemen aci´on de dicho log, se gua da como a ibu o de Da aManage un a ay de ipo s ing de LOG_BUFFER_SIZE posiciones. Pa a no es a ac ualizando el a chi o de ex o as cada acci´on, la in o maci´on de la in e acci´on se a inse ando en dicho a ay; cuando es e se llena, se aslada al a chi o de ex o, y el ´ındice de esc i u a del a ay pasa de nue o al alo 0 (no hace al a bo a lo, se a sob esc ibiendo). Una peque˜na conside aci´on que hay que ene en cuen a al u iliza es e mecanismo es que al ce a la aplicaci´on, se encuen e donde se encuen e el ´ındice de esc i u a, hay que olca la in o maci´on del a ay al a chi o de ex o. Pa a pe mi i es o es ´a el m´e odo o ceLogFileUpda e() de la clase Da aManage . Pa a ca ga y gua da la in o maci´on se usa la clase File de Sys em.IO. 53 Cap´ı ulo 4 E aluaci´on con Usua ios En es e cap´ı ulo se explican las p uebas de usabilidad lle adas a cabo pa a la aplicaci´on. Una p ime a secci´on desa olla los p ime os ensayos que se eliza on, con una e si´on de la aplicaci´on a´un no de ini i a. An e la necesidad de m´e odos m´as iables y an e los malos esul ados de las p uebas, se dedic´o una ase in e media (mien as se segu´ıa desa ollando la aplicaci´on y mien as se co eg´ıan algunos e o es que salie on a la luz en dichas p uebas) pa a in es iga a ´ıculos sob e m´e odos pa a ealiza las p uebas de usabilidad, as´ı como el an´alisis de las mismas. La eo ´ıa que se encon ´o m´as aplicable al caso de es a aplicaci´on se expone esumida en la segunda secci´on. La e ce a explica las p uebas inales con usua ios. Finalmen e, el cap´ı ulo e mina con los esul ados y las conclusiones sob e odo es e p oceso ealizado ela i o a p uebas de usabilidad. 4.1. P ime as p uebas con usua ios 4.1.1. In oducci´on Una ez se consigui´o una e si´on es able con cie os algo i mos implemen ados, se pudo p oba dicha aplicaci´on con dos usua ios pa a de ec a posibles e o es en ases emp anas del desa ollo ( al aban po a˜nadi uncionalidades y algunos juegos m´as en e a la e si´on inal). Como se mencion´o al inal del cap´ı ulo 1, el cos e de a egla un e o se inc emen a conside ablemen e seg´un aumen a el desa ollo de la aplicaci´on y, e ec i amen e, es as p ue- bas si ie on pa a co egi lo que se es aba haciendo inco ec amen e y segui desa ollando de o ma adecuada. Las p uebas se u ie on que ealiza en emo o, lo que iene algunos incon enien es (aun- que ambi´en en ajas, como que el usua io es ´a en su en o no). Po an o, ue una e aluaci´on no mode ada pe o s´ı guiada (sc ip ed es ), ya que se le indic´o al usua io lo que en´ıa que ha- ce . En conc e o, p ime o se les p opo cion´o un guion con los pasos a ealiza y he amien as a usa . T as es o, los usua ios deb´ıan ellena un cues iona io p e io a la p ueba. Pos e io men- e, se pod´ıan ija en la lis a de a eas a ealiza en la aplicaci´on (g abando simul ´aneamen e la pan alla as habe comp obado que el a chi o de log se gua daba co ec amen e en su disposi i o). Finalmen e, en´ıan que ellena o o cues iona io con las imp esiones que les ge- ne ´o la aplicaci´on. Como se ealiza on dos p uebas, las espues as cuan i a i as al cues iona io apenas ienen ele ancia (la mues a es muy peque˜na). Sin emba go, la ase de in e acci´on con la aplicaci´on as´ı como las espues as cuali a i as y suge encias de mejo a s´ı esul a on muy ´u iles. 54 El a ´ıculo [27] explica que an o los es s de usabilidad como el game-based lea ning es ´an ganando impo ancia. Po an o, ambi´en se debe desa olla el dise˜no de dichos juegos y sus p uebas. Mien as que en el so wa e habi ual el hecho de no come e e o es es bueno, un ideojuego debe desa ia cons an emen e al usua io, y se uel e abu ido si no se come e ning´un e o . En de ini i a, aunque es ´a cla o que las p uebas de usabilidad habi uales hay que modi ica las pa a ideojuegos y, en conc e o, pa a juegos se ios educa i os, en es a p ime a ase de las p uebas no se in odujo ninguna dis inci´on. Es a ue o a az´on po la que se decidi´o hace un segundo conjun o de p uebas de usabilidad. 4.1.2. P uebas ealizadas Los dos usua ios que pa icipa on en las p uebas en´ıan ya conocimien os de p og ama- ci´on. En la e si´on que p oba on, e a el usua io el que eleg´ıa si que ´ıa ene pis as o no (es o se cambi´o m´as adelan e al sis ema de es es ados ya mencionado, as conoce la de ensa que ealizaban di e sos a ´ıculos cien ´ı icos del eedback pe sonalizado y de la adap aci´on din´amica y au om´a ica de la di icul ad). En es a e si´on an igua que se us´o en las p ime as p uebas, uno de los usua ios ealiz´o la p ueba sin ayuda de las pis as, mien as que el o o pod´ıa consul a las pis as en odo momen o. Las p uebas es aban pensadas pa a ealiza se en un iempo de en e 15 y 20 minu os. Las a eas del guion se p esen a on en o ma de a- eas di ec as (solamen e se in o ma de lo que iene que hace , en con aposici´on a las a eas escena io que a˜naden un con ex o). Los usua ios ealiza on la e aluaci´on con sus disposi i os m´o iles as p opo ciona les el a chi o .apk de la aplicaci´on. T as hace el cues iona io inicial, pone en ma cha las he amien as de g abaci´on y com- p oba que el log se gua da co ec amen e, el usua io pod´ıa comenza con las a eas, que consis ´ıan en juga 4 pa idas de cada uno de los siguien es juegos: o denaci´on po inse ci´on, m´e odo de la bu buja, o denaci´on po selecci´on y o denaci´on po mezclas (1). Adem´as, el usua io deb´ıa comp oba sus es ad´ıs icas en el juego. T as inaliza , en´ıa que comple a la encues a inal dando sus imp esiones y en ia los esul ados. 4.1.3. Resul ados y posibles mejo as Aunque no e a un n´ume o de usua ios signi ica i o pa a esul a i os cuan i a i os, s´ı se ob u ie on suge encias de mejo a, as´ı como posibles cambios en la aplicaci´on as analiza las g abaciones: Un e o obse ado en es as p uebas ue la p ecisi´on en el pa ´on d ag-and-d op. El usua io hac´ıa muchos mo imien os que e an co ec os pe o el sis ema los de ec aba como inco ec os. Es e p oblema se conside a como c ´ı ico. Hab´ıa apa ecido en ases iniciales del desa ollo, pe o as ajus a el alo de la a iable asociada a la p ecisi´on, qued´o sol en ado. M´as adelan e, se descub i´o un e o asociado en el c´odigo. T as soluciona lo, el p oblema despa eci´o en las segundas p uebas. En o denaci´on po inse ci´on, en la p ime a implemen aci´on ealizada, hab´ıa una ase en que desapa ec´ıa de la pan alla el elemen o a inse a , ya que en la ase de hace hueco a dicho elemen o e a solapado al hace la copia. Es o despis ´o a los usua ios. En la e si´on inal se incluye la a iable auxilia ya mencionada pa a ene disponible en odo momen o cualquie elemen o. Adem´as, es o es iel a c´omo ac ´ua ealmen e el algo i mo. 55 Los usua ios coinciden en que e a necesa ia una p ime a pa e de eo ´ıa (quiz´as incluso con pseudoc´odigo) pa a e i a el p oceso inicial de p ueba y e o . Po es o, pa a que la aplicaci´on sea au ocon enida, se implemen a un u o ial guiado que se despliega cuando el usua io en a a la pan alla de un juego. Un usua io epo a que en algunos casos el sis ema de in e acci´on pod ´ıa se di e en- e a d ag-and-d op. Po ejemplo, al in e cambia elemen os se ealiza a as ando un elemen o conc e o al o o. Es o hac´ıa pensa al usua io que un elemen o iene mayo je a qu´ıa que el o o, cuando es o no es as´ı. Tambi´en se encon ´o alg´un aspec o que esul ´o especialmen e ag adable a los usua ios: el uso de colo es en los bo ones pa a da cie os eedbacks ue bien enido, po lo que se gene aliz´o el uso de es a ca ac e ´ıs ica en el desa ollo pos e io . Aunque es o no lo epo ´o ning´un usua io, en el an´alisis de las g abaciones se ap ecia- ba que en ocasiones el usua io comienza una acci´on, pe o obse a que es una acci´on inco ec a an es de inaliza la, po lo que de uel e el bo ´on a su posici´on inicial. Sin emba go, el juego lo de ec a como in e acci´on e ´onea y penaliza la pun uaci´on. Quiz´as es o se pod ´ıa dis ingui de alguna o ma, de mane a que si el usua io uel e al es ado inicial, no se conside e un e o . Se dis ingui ´ıan as´ı es as acciones de las co ec as que se comple an o almen e y de las inco ec as que se comple an o almen e. El iempo que emplea on los usua ios en comple a las a eas ue de 20 y de 26 minu os (poco m´as de lo espe ado). El p oblema de la p ecisi´on con amin´o o almen e el a chi o de log, ya que en la g abaci´on se ap eciaba que el usua io iba en endiendo los concep os, pe o segu´ıa allando mucho debido a la p ecisi´on: mo imien os co ec os e an clasi icados como inco ec os. Es a es o a az´on pa a ol e a ealiza p uebas con una e si´on mejo ada. La siguien e imagen, co espondien e a los e o es acumulados en el iempo de los usua ios, mues a que las pendien es de las cu as no bajan, como e a p e isible. Adem´as, el p ocesa- mien o del log se debe hace ag upado seg´un el juego. Si no, al cambia a uno nue o, ol e ´an a apa ece e o es, di icul ando mucho la ob enci´on de conclusiones. Figu a 4.1: G ´a icas de e o es acumulados a lo la go del iempo as analiza los logs de los usua ios de las p uebas iniciales. Se ap ecia que la pendien e apenas desciende a lo la go del iempo. La g ´a ica es simila a la de [27], con la di e encia de ano a e o es en ez de e en os, como se hace en el modelo de es e a ´ıculo. Pos e io men e se encuen a el a ´ıculo [16], que expone la eo ´ıa de las cu as de ap endizaje. Cu iosamen e, si la m´e ica usada es el n´ume o de e o es y se oma de o ma acumulada, se pod ´ıa deci que es as g ´a icas co esponden a e siones de cu as de ap endizaje. 56 El uncionamien o de es e sc ip de an´alisis consis e en gua da en una a iable de ipo dicciona io el momen o de comienzo de un nue o juego. Se egis an los e o es y acie os en ese juego en in e alos empo ales a pa i de ese ins an e inicial. Es muy ilus a i a la e oluci´on de la asa de e o es a lo la go del iempo en el caso de o denaci´on po inse ci´on, que adem´as es el juego que m´as acciones egis a y el que los usua- ios han clasi icado como menos in ui i o. La g ´a ica se adjun a a con inuaci´on, donde se ha inco po ado la ec a que ap oxima los pun os, usando el m´odulo scipy.op imize. Se ap ecia una cla a pendien e nega i a, se˜nal de que el usua io es ´a ap endiendo el concep o a lo la go del iempo. Debajo de es a imagen se adjun a o a g ´a ica con los e o es acumulados. Se ap ecia una disminuci´on de la pendien e al a anza en el iempo. Figu a 4.6: Tasa de e o es a lo la go del iempo pa a o denaci´on po inse ci´on, en in e alos de 10 segundos (es amos po an o an e una cu a de ap endizaje). El eje x ep esen a el n´ume o de in e alo conside ado, y el eje yindica el an o po uno de e o es. La ec a de ajus e mues a pendien e nega i a. Figu a 4.7: E o es acumulados a lo la go de in e alos de iempo, pa a el juego de o denaci´on po inse ci´on. El eje x ep esen a el n´ume o de in e alo de iempo (igual que en la igu a an e io ). El eje y ep esen a el o al de e o es. Po ´ul imo, se adjun a una abla con es ad´ıs icas globales de odos los logs sob e los di- e en es juegos. 63 Acciones Acie os E o es Tasa de acie os Inse ci´on 3713 3017 696 81.26 % Selecci´on 740 617 123 83.38 % Bu buja 1643 1299 344 79.06 % Mezclas 729 624 105 85.60 % Ven ana 1465 1238 227 84.51 % Cuad o 4.1: Es ad´ıs icas sob e las acciones ealizadas. La asa de acie os inal es buena en odos los casos, en o no al 80 %. Como e a espe able, los juegos que han pa ecido m´as complicados son los que ienen meno asa de acie os. La di e encia no es g ande, pe o an e la g an can idad de acciones egis adas s´ı es ep esen a i a. 64 Cap´ı ulo 5 Conclusiones y abajo u u o 5.1. Conclusiones El obje i o de es e abajo es c ea una aplicaci´on educa i a que simula el uncionamien o de algo i mos o es uc u as de da os y que pe mi a la in e acci´on del usua io. Las p uebas ealizadas al inal del desa ollo demues an que es o ha sido conseguido, ya que an o el cues iona io inal sob e las imp esiones con la aplicaci´on como el an´alisis de los logs a ojan esul ados posi i os. La in e acci´on puede esul a di ´ıcil al p incipio, pe o el usua io aca- ba en endiendo las acciones que ealiza el algo i mo y, as alguna pa ida, puede eplica lo sin p oblema. Las p uebas ambi´en han demos ado que las uncionalidades adicionales im- plemen adas ag egan alo a la aplicaci´on, como el sis ema de adap aci´on din´amica de la di icul ad o el sis ema de pun uaciones. Po o o lado, en es e abajo se han u ilizado concep os es udiados a lo la go del g a- do en ingenie ´ıa in o m´a ica. Como es ob io, las asigna u as de algo i mia ienen un g an peso, aunque se hayan implemen ado algo i mos b´asicos. Po o o lado, el pa adigma de p o- g amaci´on o ien ada a obje os se ha u ilizado pa a desa olla un c´odigo eu ilizable, po lo que asigna u as como Tecnolog´ıa de la p og amaci´on o Ingenie ´ıa del so wa e ambi´en han ayudado al desa ollo de es a aplicaci´on. Pa a las p uebas con usua ios ha sido ´u il la asigna u a Desa ollo de sis emas in e ac i os, p opo cionando un m´e odo pa a es e ipo de e aluaciones. Po ´ul imo, es e abajo ambi´en ha se ido pa a ap ende nue os concep os que no hab´ıan sido a ados a lo la go del g ado. Po ejemplo, el mo o de ideojuegos Uni y, usando el lenguaje de p og amaci´on C#, que ha esul ado no edoso igualmen e. 5.2. T abajo u u o La aplicaci´on implemen ada se pod ´ıa mejo a de di e sas o mas. En p ime luga , la mane a m´as inmedia a es inclui nue os juegos asociados a o os algo i mos. Po o o lado, se pod ´ıa u iliza el sis ema de pun uaciones pa a c ea una base de da os que omen e la compe i i idad en el juego, con el ap endizaje asociado. El sis ema de adap aci´on din´amica de di icul ad ha esul ado e ec i o, pe o no deja de se muy sencillo, po lo que la aplicaci´on pod ´ıa pe sonaliza se m´as a´un. O a posible mejo a es amplia la in e acci´on d ag-and-d op, con o as o mas de ealiza las acciones en el juego. Po ejemplo, si se implemen an ´a boles, una in e acci´on in e esan e pod ´ıa se inclina el el´e ono hacia el lado co ec o pa a ep esen a que el ´a bol o a pa a queda equilib ado. 65 Conclusions and u u e wo k 5.3. Conclusions The aim o his wo k is o de elop an educa ional applica ion ha simula es he low o algo i hms and eaches he basics o da a s uc u es, allowing use s o in e ac wi h i . The usabili y es s pe o med a he end o he de elopmen show ha hese goals ha e been achie ed. Bo h he su ey abou he imp essions o he use s and he log ile analysis show posi i e ou comes. Ini ially, use s may ind in e ac ion di icul , bu hey unde s and how algo i hms wo k a e playing a ew games. Fu he mo e, usabili y es s ha e shown ha addi ional unc ionali ies in he game like he sco e sys em o dynamic adap abili y imp o e he applica ion. In addi ion, concep s s udied h oughou he deg ee in compu e science ha e been used. Ob iously, subjec s abou algo i hms and da a s uc u es a e e y impo an in his wo k, al hough algo i hms implemen ed in he game a e basic. Objec -o ien ed p og amming pa a- digm has been used in o de o de elop eusable code, so subjec s like Compu e P og amming Technology o So wa e Enginee ing ha e played an impo an ole in his wo k oo. In e ac- i e sys ems de elopmen subjec has been use ul o usabili y es ing, because i p o ides a me hod o make hese es s. Finally, I ha e lea ned new concep s oo, like Uni y game engine o C# p og amming language. 5.4. Fu u e wo k The applica ion ha has been de eloped could be imp o ed in se e al ways. Fi s , new games abou algo i hms and da a s uc u es could be included in he applica ion. Secondly, he sco e sys em may be used o c ea e a da abase ha os e s compe i i eness. The dynamic di icul y adjus men sys em has been e ec i e, al hough i is e y simple and he applica ion i sel could be e adjus o he needs o each use . Ano he possible imp o emen o he game is o ex end d ag-and-d op in e ac ion pa e n wi h o he ways o execu ing ac ions. Fo example, i ees we e implemen ed, i would be in e es ing o allow he use o il he de ice in o de o o a e and balance hem. 66 Bibliog a ´ıa [1] R. D¨o ne , S. G¨obel, W. E elsbe g, and J. Wiemeye , Se ious Games. Sp inge , 2016. [2] M. Csikszen mihalyi, Flow: The psychology o op imal expe ience. Ha pe & Row New Yo k, 1990. [3] P. Swee se and P. Wye h, “Game low: A model o e alua ing playe enjoymen in games,” ACM Compu e s in En e ainmen , ol. 3, 07 2005. [4] B. Sawye and D. Rejeski, “Se ious games: Imp o ing public policy h ough game-based lea ning and simula ion,” 01 2002. Wood ow Wilson In e na ional Cen e o Schola s, Washing on, DC. [5] P. Games and M. Knigh , “Ame ica’s a my,” 2002. C own Publishing G oup, New Yo k. [6] J. Sinclai , “Feedback con ol o exe games,” 2011. h ps:// o.ecu.edu.au/ heses/380/ (Accessed 13 Decembe 2020). [7] M. P ensky, “Digi al game-based lea ning,” ACM Compu e s in En e ainmen , ol. 1, 10 2003. [8] D. Lecle cq, “The 8 Lea ning E en s Model and i s p inciples,” 2005. h p://www.labse .ne /media/p od/8LEM.pd (Accessed 13 Decembe 2020). [9] M. D. Kickmeie -Rus and D. Albe , “Mic o-adap i i y: P o ec ing imme sion in di- dac ically adap i e digi al educa ional games,” Jou nal o Compu e Assis ed Lea ning, ol. 26, no. 2, pp. 95–105, 2010. [10] R. Ba le, “Hea s, clubs, diamonds, spades: Playe s who sui muds,” Jou nal o MUD esea ch, ol. 1, no. 1, 1996. [11] E. Lah inen, K. Ala-Mu ka, and H.-M. J¨a inen, “A s udy o he di icul ies o no ice p og amme s,” Acm sigcse bulle in, ol. 37, no. 3, pp. 14–18, 2005. [12] O. As achan, “Bubble so : an a chaeological algo i hmic analysis,” ACM Sigcse Bu- lle in, ol. 35, no. 1, pp. 1–5, 2003. [13] R. S. Bake , M. Boilen, M. T. Good ich, R. Tamassia, and B. A. S ibel, “Tes e s and isualize s o eaching da a s uc u es,” ACM SIGCSE Bulle in, ol. 31, no. 1, pp. 261– 265, 1999. [14] D. Diche a and A. Hodge, “Ac i e lea ning h ough game play in a da a s uc u es cou se,” in P oceedings o he 49 h ACM Technical Symposium on Compu e Science Educa ion, pp. 834–839, 2018. 67 [15] E. Ha ps ead, B. A. Mye s, and V. Ale en, “In sea ch o lea ning: Facili a ing da a analysis in educa ional games,” in P oceedings o he SIGCHI Con e ence on Human Fac o s in Compu ing Sys ems, CHI ’13, (New Yo k, NY, USA), p. 79–88, Associa ion o Compu ing Machine y, 2013. [16] B. Ma in, K. R. Koedinge , A. Mi o ic, and S. Ma han, “On using lea ning cu es o e alua e i s,” in P oceedings o he 2005 Con e ence on A i icial In elligence in Educa- ion: Suppo ing Lea ning h ough In elligen and Socially In o med Technology, (NLD), p. 419–426, IOS P ess, 2005. [17] J. K. Haas, “A his o y o he uni y game engine,” 2014. Wo ces e Poly echnic Ins i u e, h ps://digi alcommons.wpi.edu/iqp-all/3207/ (Accessed 13 Decembe 2020). [18] E. Balagu usamy, P og amming in C#: A P ime . McG aw-Hill Educa ion, o h ed., 2010. [19] C. Kazimoglu, M. Kie nan, L. Bacon, and L. Mackinnon, “A se ious game o de eloping compu a ional hinking and lea ning in oduc o y compu e p og amming,” P ocedia - Social and Beha io al Sciences, ol. 47, pp. 1991 – 1999, 2012. Cyp us In e na ional Con e ence on Educa ional Resea ch (CY-ICER-2012)No h Cyp us, US08-10 Feb ua y, 2012 h p://www.sciencedi ec .com/science/a icle/pii/S1877042812026742 (Accessed 13 Decembe 2020). [20] J. M. Wing, “Compu a ional hinking,” Communica ions o he ACM, ol. 49, no. 2, pp. 33–35, 2006. [21] J. A. Qualls and L. B. She ell, “Why compu a ional hinking should be in eg a ed in o he cu iculum,” Jou nal o Compu ing Sciences in Colleges, ol. 25, no. 5, pp. 66–71, 2010. [22] T. Ba nes, H. Rich e Lip o d, E. Powell, A. Cha in, and A. Godwin, “Game2lea n: building cs1 lea ning games o e en ion,” ol. 39, pp. 121–125, 01 2007. [23] A. Cha in, K. Do an, D. Hicks, and T. Ba nes, “Expe imen al e alua ion o eaching ecu sion in a ideo game,” in P oceedings o he 2009 ACM SIGGRAPH Symposium on Video Games, pp. 79–86, 2009. [24] E. B. Cos a, A. M. Toda, M. A. A. Mesqui a, and J. D. B anche , “Dslep (da a s uc- u e lea ning pla o m o aid in highe educa ion i cou ses),” In e na ional Jou nal o Compu e and Sys ems Enginee ing, ol. 8, no. 4, pp. 1143 – 1148, 2014. [25] N. Kau and G. Gee ha, “Play and lea n ds: In e ac i e and game ul lea ning o da a s uc u e,” In e na ional Jou nal o Technology Enhanced Lea ning, ol. 7, pp. 44–56, 09 2015. [26] M. Eagle and T. Ba nes, “Expe imen al e alua ion o an educa ional game o imp o- ed lea ning in in oduc o y compu ing,” SIGCSE’09 - P oceedings o he 40 h ACM Technical Symposium on Compu e Science Educa ion, ol. 41, pp. 321–325, 03 2009. [27] P. Mo eno-Ge , J. To en e, Y. G. Hsieh, and W. T. Les e , “Usabili y es ing o se ious games: Making in o med design decisions wi h use da- a,” Ad ances in Human-Compu e In e ac ion, ol. 2012, 2012. Hindawi, h ps://www.hindawi.com/jou nals/ahci/2012/369637/ (Accessed 13 Decembe 2020). 68