Are you ready for a quiz? [SOLVED]

ilan

Expert
Licensed User
have you already had a coffee today? if not you better get one before get to this quiz :)

the goal is:

on every mouse click a dot will be drawn on the screen and now we will need to connect all dots
with a line. but the goal is to find the shortest line to each dot and draw a line between those 2 dots but all lines must be connect with each other, so you need to write an algorithm that does it.

i will include the jar file and i hope you will make it faster then i did :)

screen.png


good luck!
 

Attachments

ilan

Expert
Licensed User
this is not "the travelling salesman problem" this is the "minimum spanning tree" problem
you can see that the travelling salesman problem does not draw the shortest line between the dots
it just draw a closed shape that is connected to all dots.

in the "minimum spanning tree" problem we need to find to any dot the shortest neighbor dot and connect both.

HINT: create 2 groups of dots, reached and unreached, now every time an unreached dot is reached you delete it from the list array and put it in reached dots

you always need go through all reached dots and find the shortest distance to the unreached dots UNTIL unreached list array is empty :)

https://en.wikipedia.org/wiki/Minimum_spanning_tree
 

ilan

Expert
Licensed User
maybe this technique could be used in a pizza delivery app.
for example you have 5 orders and you need to find the shortest path for the pizza deliverer so this algorithm will calculate the shortest distance between
the dots and give you the fastest route for the delivery. of course it need to be modified a little bit.

but i believe google maps got already his "calculate shortest route" function. :) (have not used google maps until now so don't know if it got such a function)
 

Beja

Expert
Licensed User
Great idea for a new game beja. :)
This code can be used for it very easily.
You can draw those characters also with the jar file i included
That's good hope, ilan,
so you can develop games with the core library..
 

ilan

Expert
Licensed User
so you can develop games with the core library..
https://www.b4x.com/android/forum/threads/free-source-codes.53152/#post-333010
https://www.b4x.com/android/forum/threads/free-source-codes.53152/#post-333079
https://www.b4x.com/android/forum/threads/free-source-codes.53152/#post-363976
https://www.b4x.com/android/forum/threads/free-source-codes.53152/#post-364004

(+all my b4i games are using only the core lib)

you can do a lot with the core lib. of course if you want to make a more complex game that uses physics and lots of sprites you better use a game engine.
but it could also be done without any libs it will only require lots of calculations.

i would like to see a CORE ONLY GAME CONTEST, would be in for sure :)
 
Top