Are you ready for a quiz? [SOLVED]

[ilan]

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

good luck!

 

[Beja]

Something like this

sorry Ilan, just joking.. your quiz is big challenge.

 

[ilan]

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

 

[Erel]

There is no "fast" solution for this problem (unless NP = P). This is a known problem: https://en.wikipedia.org/wiki/Travelling_salesman_problem

I played with the jar file and it is very nice

 

[ilan]

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

 

[Erel]

You are correct.

 

[ilan]

You are correct.

that doesn't happen much

 

[Erel]

Here is my implementation: https://b4x.com:51041/mst/index.html

 

[ilan]

Bravo, you are very smart @Erel.
you earned a free pizza

 

[ilan]

this is the code i use

 

[Erel]

I posted my solution here: https://www.b4x.com/android/forum/threads/webapp-minimum-spanning-tree.64870/

 

[ilan]

@Erel you were the first to answer this quiz so i sent you a donation for the free Pizza, "Bon Appetit"

(Pypal Transaction ID 05F10123PY745681H)

 

[ilan]

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]

There is no "fast" solution for this problem (unless NP = P). .....

"unless NP = P"

From Algebraic point of view, this is impossible.

 

[Beja]

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]

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

 

[Beja]

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

I am in..
My wisdom is: make the game smart, not fast