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: OK U GUIS WANTED A HARD QUESTION

Previous Thread :: Next Thread 
Wayne_Gretzky is not online. Wayne_Gretzky
Joined: 03 Apr 2008
Total Posts: 78011
11 Mar 2016 04:18 PM
Alrite this is straight from the Googles!!!

You're in a car on a road trip. You get bored, so you decide to play a game. For every passing car, you'll look through a dictionary and find the smallest word that has all the letters from the license plate.

The license plates are 2 letters followed by 5 characters, containing at most two more letters. You have to find the smallest word for 100 different license plates.

You are limited in both memory and time, so your goal is to make this as efficiently as possible without overloading the memory of the computer.

For example, a license plate may be;
TO 40S0P, where the answer would be "STOP".
RC 11601, where the answer would be "CAR".

Do this for all 100 license plates.

https://youtu.be/L78yVFeyvRo?t=31
Report Abuse
segmentation_fault is not online. segmentation_fault
Joined: 07 Mar 2016
Total Posts: 30
11 Mar 2016 04:29 PM
can we assume that

local dictionary;

contains all english words and that it is sorted from shortest to longest words?
Report Abuse
eLunate is not online. eLunate
Joined: 29 Jul 2014
Total Posts: 13268
11 Mar 2016 04:29 PM
You confused me at car.
Report Abuse
segmentation_fault is not online. segmentation_fault
Joined: 07 Mar 2016
Total Posts: 30
11 Mar 2016 04:29 PM
oh u ACTUALLY WANT IT TO WORK lol
Report Abuse
Wayne_Gretzky is not online. Wayne_Gretzky
Joined: 03 Apr 2008
Total Posts: 78011
11 Mar 2016 04:31 PM
Dictionary contains all English words, but its not sorted.
You can however explain the method you'd use to sort it without giving the code for sorting.


And you get car because you have to find the shortest word that contains both 'R' and 'C'.
'R' is not a word
'C' is not a word
'RC' is not a word
'CR' is not a word

So you have to find add another letter to turn that into a word
By adding 'A', you get "CAR"
So the shortest word you can find with both 'R' and 'C' would be car (although there are other options, but its just the length 3 that matters, not car specifically)

https://youtu.be/L78yVFeyvRo?t=31
Report Abuse
Garfanzo is not online. Garfanzo
Joined: 24 Apr 2015
Total Posts: 742
11 Mar 2016 04:31 PM
for i = 1, 100, 1 do

math.random(stuff)

end

Boom done!
Report Abuse
Wayne_Gretzky is not online. Wayne_Gretzky
Joined: 03 Apr 2008
Total Posts: 78011
11 Mar 2016 04:32 PM
@Seg
Doesn't matter if it works
Its basically the thought process, what your idea is to solve it, how efficient that is etc

'Cause that's what they're gonna ask u in interviews :o
They don't care if it works as long as u get the right process to it

https://youtu.be/L78yVFeyvRo?t=31
Report Abuse
Tynezz is not online. Tynezz
Joined: 28 Apr 2014
Total Posts: 4945
11 Mar 2016 04:34 PM
local Dictionary={}
local smallest;
game.Workspace.ChildAdded:connect(function(car)
local plate=car.Value
for _,v in pairs(Dictionary) do
local count=0
for i=1,string.len(plate) do
if tostring(v):match(tostring(plate:sub(i,i))) then
count=count+1
end
end
if count>=plate:len() then
if not smallest then smallest=plate elseif plate:len()>smallest:len() then smallest=plate end end end end)

ik ugly made in the post
Report Abuse
Wayne_Gretzky is not online. Wayne_Gretzky
Joined: 03 Apr 2008
Total Posts: 78011
11 Mar 2016 04:40 PM
gg ^
that's the first one he said u shud come up with

but then is there any way to optimize :o

https://youtu.be/L78yVFeyvRo?t=31
Report Abuse
segmentation_fault is not online. segmentation_fault
Joined: 07 Mar 2016
Total Posts: 30
11 Mar 2016 04:43 PM
local dictionary; -- assume this contains all english words
local plates; -- assume this contains all 100 license plates

table.sort(dictionary, function(a, b) return a:len() < b:len() end)

-- just a heads up i copied this permute function cuz im lazy
function permute(text)
local function inner(a, n, tbl)
if n > 0 then
for i = 1, n do
a[i], a[n] = a[n], a[i]
inner(a, n - 1, tbl)
a[i], a[n] = a[n], a[i]
end
else
local text = table.concat(a, '')
for _,v in pairs(tbl) do -- ugly combination checker
if v == text then return end
end
table.insert(tbl, text)
end
end

local tbl = {}
local collection = {}

for c in text:gmatch('.') do table.insert(tbl, c) end

inner(tbl, #tbl, collection)

return collection
end

function findWord(word)
local letters = {}
word = word:gmatch("%s+", "") -- is there whitespace in a license plate? if so remove it
for n in word:gmatch(".") do
if tonumber(n, 10) then
table.insert(letters, n)
end
end
local k = 4
local permutations = permute(word)
for i, v in ipairs(permutations) do
local found = false
for j, k in ipairs(dictionary) do
if v == k then
print("FOUND WORD", v)
break
end
end
if found then break end
end
end

for i, v in ipairs(plates) do find(v) end
Report Abuse
Wayne_Gretzky is not online. Wayne_Gretzky
Joined: 03 Apr 2008
Total Posts: 78011
11 Mar 2016 04:45 PM
gg that's one of the better methods he gave ^

https://youtu.be/L78yVFeyvRo?t=31
Report Abuse
segmentation_fault is not online. segmentation_fault
Joined: 07 Mar 2016
Total Posts: 30
11 Mar 2016 04:45 PM
oh i didnt think about just checking that every character is in the word xdddd
Report Abuse
Wayne_Gretzky is not online. Wayne_Gretzky
Joined: 03 Apr 2008
Total Posts: 78011
11 Mar 2016 04:48 PM
he probably wouldn't care xd
its that u had good idea of how to do it1

https://youtu.be/L78yVFeyvRo?t=31
Report Abuse
eLunate is not online. eLunate
Joined: 29 Jul 2014
Total Posts: 13268
11 Mar 2016 04:55 PM
I wanted to try it. I didn't want to try it the way everyone else will do it, I wanted to try it a way that I thought was different to what you might expect.
Even if it is a lot slower.

dictionary = table.sort(dictionary) or dictionary; -- I don't really know if it returns the table it sorted.
dictk = table.concat(dictionary,'|');
dictionary = nil; -- Turns out I didn't need that.
for i=1,#plates do
local letters = "["..plates[i]:gsub('%A','').."]";
local _t = dictk:match(letters.."+");
if _t then
plates[i] = _t;
else
-- Ugh silly plate why do you do this.
local _t = dictk;
for n=2,#letters-1 do
local _s = {};
local _f = function(s) _s[#_s+1] = s end;
_t:gsub('[^|]*'..letters:sub(n,n)..'[^|]*', _f);
_t = table.concat(_s,'|');
end;
if #_t == 0 then
plates[i] = '';
else
plates[i] = _t:match('^[^|]+');
end;
end;
end;
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