# Are you ready for a quiz? [SOLVED]

#### ilan

##### Expert
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!

#### Attachments

• 308.4 KB Views: 140

#### Beja

##### Expert
Something like this

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

#### ilan

##### Expert
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

Staff member

Staff member

#### ilan

##### Expert
@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)

Last edited:

#### ilan

##### Expert
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
There is no "fast" solution for this problem (unless NP = P). .....
"unless NP = P"

From Algebraic point of view, this is impossible.

#### Beja

##### Expert
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
so you can develop games with the core library..

(+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