|
| 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 |
|
|
|
| 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
|
  |
| Joined: 29 Jul 2014 |
| Total Posts: 13268 |
|
| |
|
|
| 11 Mar 2016 04:29 PM |
| oh u ACTUALLY WANT IT TO WORK lol |
|
|
| Report Abuse |
|
|
|
| 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
|
  |
| 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 |
|
|
|
| 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
|
  |
| 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 |
|
|
|
| 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 |
|
|
|
| 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 |
|
|
|
| 11 Mar 2016 04:45 PM |
gg that's one of the better methods he gave ^
https://youtu.be/L78yVFeyvRo?t=31 |
|
|
| Report Abuse |
|
|
|
| 11 Mar 2016 04:45 PM |
| oh i didnt think about just checking that every character is in the word xdddd |
|
|
| Report Abuse |
|
|
|
| 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
|
  |
| 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 |
|
|