generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Coding Challenge: Difficulty - Medium

Previous Thread :: Next Thread 
AshleyFromUnderneath is not online. AshleyFromUnderneath
Joined: 14 Sep 2015
Total Posts: 667
17 Sep 2015 08:57 PM
Your challenge, if you choose to accept it, is to create some code that can solve the Travelling Salesman problem.

The problem goes as such: A salesman must travel to a number of cities. He wants to know the shortest route he can take to hit all the cities at least once and end up back where he started, so he can go on the route again in the future.

Essentially, you generate many random points, and try to figure out what is the order to go through them that will take the least distance.

It must be able to solve it for at least 30 cities and the algorithm must be fast enough to solve it under 30 seconds.

Your algorithm doesn't need to find the perfect solution every time. It needs to be able to at least find the perfect solution sometimes and a very good solution every other time. It shouldn't return a bad solution.

You can do it in any programming language you wish.
I have done it in Java using simulated annealing.

It should look something like this:
https://www.youtube.com/watch?v=eLZvNv1bMoE
Report Abuse
cntkillme is not online. cntkillme
Joined: 07 Apr 2008
Total Posts: 44956
17 Sep 2015 08:58 PM
This challenge sounds very familiar... like too familiar.
Report Abuse
MKofOrbiter is not online. MKofOrbiter
Joined: 28 Aug 2010
Total Posts: 910
17 Sep 2015 09:13 PM
^

It is quite popular.
Report Abuse
DeathsLASTwords is not online. DeathsLASTwords
Joined: 28 Jan 2012
Total Posts: 2701
17 Sep 2015 09:14 PM
i remember doing this with i think the A* algorithm for pathfinding, i hated it


(This is my signature): Im extremely sarcastic, but most of the time I will provide useful info for you! :)
Report Abuse
MKofOrbiter is not online. MKofOrbiter
Joined: 28 Aug 2010
Total Posts: 910
17 Sep 2015 09:23 PM
I am now starting, should be fun!
Report Abuse
flshguy100 is not online. flshguy100
Joined: 21 Jul 2015
Total Posts: 45
22 Sep 2015 05:35 AM
local function PTheorem(a,b)
return (a ^ 2) + (b ^ 2)
end

Perhaps... You can use this to find C assuming it is triangular.
Report Abuse
morash is not online. morash
Joined: 22 May 2010
Total Posts: 5834
22 Sep 2015 06:21 AM
Pick the points with the shortest distance between them?
Report Abuse
InsaneDays is not online. InsaneDays
Joined: 28 Jan 2012
Total Posts: 762
22 Sep 2015 07:27 AM

local points = {}
local cityNearby

local cityMap = Instance.new("Model", game.Workspace)
cityMap.Name = "City"

local tracks = Instance.new("Model", game.Workspace)
tracks.Name = "Tracks"

local start = Instance.new("Part", cityMap)
start.Name = "StartCity"
start.Anchored = true
start.BrickColor = BrickColor.Random()
start.Size = Vector3.new(2,4,2)
start.CFrame = CFrame.new(Vector3.new(math.random(-200,200),-10,math.random(-200,200)))

local lastCity = start
local lastMag = math.huge

for i = 1,math.random(30,40) do
local city = Instance.new("Part", cityMap)
city.Name = "City"..i
city.Anchored = true
city.BrickColor = BrickColor.Random()
city.Size = Vector3.new(2,4,2)
city.CFrame = CFrame.new(Vector3.new(math.random(-200,200),-10,math.random(-200,200)))
table.insert(points,#points+1, {city, false})
end

for i,v in pairs(points) do
local currentCity
for t,q in pairs(points) do
local mag = (lastCity.Position-q[1].Position).magnitude
if mag < lastMag and q[2] == false then
lastMag = mag
currentCity = q
print("Found")
end
end
local track = Instance.new("Part", tracks)
track.Name = "Track"
track.BrickColor = BrickColor.new("Black")
track.Size = Vector3.new(2,4,lastMag)
track.CFrame = CFrame.new(lastCity.Position, currentCity[1].Position)*CFrame.new(0,0,-lastMag/2)
track.Anchored = true
currentCity[2] = true
lastCity = currentCity[1]
lastMag = math.huge
wait()
end

lastMag = (lastCity.Position-start.Position).magnitude
local track = Instance.new("Part", tracks)
track.Name = "Track"
track.BrickColor = BrickColor.new("Black")
track.Size = Vector3.new(2,4,lastMag)
track.CFrame = CFrame.new(lastCity.Position, start.Position)*CFrame.new(0,0,-lastMag/2)
track.Anchored = true

Took me roughly 30 mins, good challange so far.
Report Abuse
InsaneDays is not online. InsaneDays
Joined: 28 Jan 2012
Total Posts: 762
22 Sep 2015 07:40 AM
Edited it, made a proper animation for it.

Take it here:
http://www.roblox.com/SalesMan-Challange-item?id=299447278
Report Abuse
InsaneDays is not online. InsaneDays
Joined: 28 Jan 2012
Total Posts: 762
22 Sep 2015 03:52 PM
I guess i won ;3
Report Abuse
chimmmihc is not online. chimmmihc
Joined: 24 Jul 2014
Total Posts: 2420
22 Sep 2015 04:53 PM
You didn't account for gas into the pathfinding, this is part of the real problem

Fun fact, airports have people do this cause so far computers haven't been able too.
Report Abuse
notfruit is not online. notfruit
Joined: 21 Sep 2012
Total Posts: 1386
22 Sep 2015 06:15 PM
bruh get ur NP-complete problems out of here

unless someone has an algorithm for solving this in polynomial time

if u do pls share

that means we can factor large integers in polynomial time

which means we can essentially break at least some kinds of encryption (symmetric-key)
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image