Djikstra's Out: The Yospos Algorithm Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > Djikstra's Out: The Yospos Algorithm Thread

«‹›3 »

Symbolic Butt: Mar 22, 2009; (_!_); Buglord

dfs and bfs are straightforward algos that I use quite often

they're like the natural evolution of for loops

# ? Sep 13, 2016 02:10

Adbot: ADBOT LOVES YOU

# ? May 16, 2024 02:09

Symbolic Butt: Mar 22, 2009; (_!_); Buglord

you have zero excuse if you can't whip them in a programming interview imo

# ? Sep 13, 2016 02:10

hobbesmaster: Jan 28, 2008

Symbolic Butt posted:

you have zero excuse if you can't whip them in a programming interview imo

people reading this thread are more likely to be fretting over their cost function for A* or which ordering is optimal for dfs than to have no idea how to create a "trivial" implementation of a bfs or dfs

# ? Sep 13, 2016 02:26

Shaman Linavi: Apr 3, 2012

i tried to implement some kind of bi-directional A* but instead i just got two A*s that went right past each other
at least the initial/goal states were correct for each direction so i was half right

# ? Sep 13, 2016 02:35

Bloody: Mar 3, 2013

i have certainly sweat through a bfs/dfs whiteboard before, in part because the interviewer was an rear end in a top hat

# ? Sep 13, 2016 04:21

Bloody: Mar 3, 2013

but like this is poo poo i use literally never, get off my nuts interview-man

# ? Sep 13, 2016 04:22

Captain Foo: May 11, 2004; we vibin'
we slidin'
we breathin'
we dyin'

boob-first / dick-first search

# ? Sep 13, 2016 15:24

carry on then: Jul 10, 2010; by VideoGames
(and can't post for 10 years!)

hobbesmaster posted:

people reading this thread are more likely to be fretting over their cost function for A* or which ordering is optimal for dfs than to have no idea how to create a "trivial" implementation of a bfs or dfs

i need to feel like an ultra-competent hardass by accusing everyone around me of fundamental incompetence, so please don't interrupt

# ? Sep 13, 2016 15:56

The MUMPSorceress: Jan 6, 2012; ^SHTPSTS; Gary’s Answer

i used to know dfs and bfs, but mumps has hosed my brain because they can be fully replaced with $o and $q

# ? Sep 13, 2016 18:50

BONGHITZ: Jan 1, 1970

Captain Foo posted:

boob-first / dick-first search

# ? Sep 13, 2016 19:56

pepperoni and keys: Sep 7, 2011; _{I think about food literally all day every day. It's a thing.}

have this been posted yet

https://www.youtube.com/watch?v=ywWBy6J5gz8

# ? Sep 14, 2016 17:21

Captain Foo: May 11, 2004; we vibin'
we slidin'
we breathin'
we dyin'

Zaito posted:

have this been posted yet

https://www.youtube.com/watch?v=ywWBy6J5gz8

oh my goodness

this is fantastic

# ? Sep 14, 2016 17:52

FamDav: Mar 29, 2008

Symbolic Butt posted:

you have zero excuse if you can't whip them in a programming interview imo

whenever I do phone screens for entry/mid-level hires I usually ask them to write a "head-to-tail" solver and its always

when they come up with very bad optimizations (hash the words in the dictionary and then sort?) and then when I do convince them to just write the bfs and track incoming edges they do p miserably

. please just learn a search; it will make you comfortable with using several different data structures (set, queue, stack, and a map if you're storing back references) while not being more than like 10 lines of code.

code:


fn do_a_search(visit_container_ctr, graph, start, end) -> Maybe(Node)
  let seen = set()
  let to_visit = visit_container_ctr(start)

  while !to_visit.empty?
     let n = to_visit.pop
     seen.add(n)
     return n if n == start

     to_visit.push_all(n.neighbors.difference(seen))
  end

  return Nothing
end

let bfs = do_a_search(queue)
let dfs = do_a_search(stack)

FamDav fucked around with this message at 15:23 on Sep 15, 2016

# ? Sep 14, 2016 17:53

AWWNAW: Dec 30, 2008

what's a "head-to-tail" solver?

# ? Sep 14, 2016 18:21

ahmeni: May 1, 2005; It's one continuous form where hardware and software function in perfect unison, creating a new generation of iPhone that's better by any measure.; Grimey Drawer

AWWNAW posted:

what's a "head-to-tail" solver?

an extra $50

# ? Sep 14, 2016 23:23

FamDav: Mar 29, 2008

AWWNAW posted:

what's a "head-to-tail" solver?

if you're given two words (like head and tail) find a chain of words that's one letter different that link the two words. so

head
heal
teal
tell
tall
tail

# ? Sep 15, 2016 15:25

Captain Foo: May 11, 2004; we vibin'
we slidin'
we breathin'
we dyin'

FamDav posted:

if you're given two words (like head and tail) find a chain of words that's one letter different that link the two words. so

head
heal
teal
tell
tall
tail

this poo poo was a great way to kill time in high school

poo poo
shot
soot
toot
tort
port
post

# ? Sep 15, 2016 15:33

The MUMPSorceress: Jan 6, 2012; ^SHTPSTS; Gary’s Answer

FamDav posted:

if you're given two words (like head and tail) find a chain of words that's one letter different that link the two words. so

head
heal
teal
tell
tall
tail

so i assume one of the preconditions of the interview question is that you can assume youre provided with a dictionary from which you can load words? and the expected answer is basically just "load these into a graph with edges between all words that are one letter apart performance be damned, then do a dfs or bfs to find a path between the two input words"?

i really enjoy how in 90% of problems like this where someone wants you to use a graph to solve the problem, the lovely difficult part of actually building the graph is sort of a handwave.

# ? Sep 15, 2016 15:40

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

why do you need to load them into a graph?

there are only (25 * length-of-word) possible connections, just enumerate them all at every step and check if they're in the dictionary. a constant factor of 100 is irrelevant in the "just get it working" stage.

# ? Sep 15, 2016 16:25

hobbesmaster: Jan 28, 2008

Jabor posted:

why do you need to load them into a graph?

there are only (25 * length-of-word) possible connections, just enumerate them all at every step and check if they're in the dictionary. a constant factor of 100 is irrelevant in the "just get it working" stage.

but then you'd probably be told to trie again

# ? Sep 15, 2016 16:33

DONT THREAD ON ME: Oct 1, 2002; by Nyc_Tattoo; Floss Finder

hobbesmaster posted:

but then you'd probably be told to trie again

lol

# ? Sep 15, 2016 16:36

FamDav: Mar 29, 2008

LeftistMuslimObama posted:

so i assume one of the preconditions of the interview question is that you can assume youre provided with a dictionary from which you can load words? and the expected answer is basically just "load these into a graph with edges between all words that are one letter apart performance be damned, then do a dfs or bfs to find a path between the two input words"?

i really enjoy how in 90% of problems like this where someone wants you to use a graph to solve the problem, the lovely difficult part of actually building the graph is sort of a handwave.

yeah no need to build a graph. just search and keep track of parents so you can reconstruct the path. the goal is to give you a no magic question; there shouldn't be a critical insight that makes things easy. it's also a question that requires you to use a few different data structures (even if it's an algorithm you should just know), as opposed to many others which are just array operations.

this is for a phone screen, so in the event that they get this all very fast we start talking about similar problems that actually exist and how we can scale them beyond one off scripts.

# ? Sep 15, 2016 16:47

Shaman Linavi: Apr 3, 2012

i did a genetic algorithm to find rare trade routes in elite: dangerous
of course i dont actually play the game anymore so hell if i know if they are actually good or not

http://i.imgur.com/n3l5xtc.gifv

also i like genetic algorithms

# ? Sep 22, 2016 23:44

toiletbrush: May 17, 2010

That's really cool. A couple years ago I wrote am iOS Worms clone that started off using genetic algorithms to find the best shot to take to hit an enemy player until I realised that actually just choosing the best angle/power out of 10,000 random shots worked even better. It was disappointing it was such a lame algorithm but the results were brilliant because it would always take the 'obvious' shots when they existed, and choose the shortest 'blow a tunnel through the mountain/roof' route when that was the only option. It was weird how intelligent it seemed when it did sneaky stuff like taking advantage of bugs in collision detection etc.

My final year project at uni used them so a basic voice synthesiser would 'learn' how to pronounce words by example. It was sort of intelligible if you knew what it was trying to say.

# ? Sep 23, 2016 13:19

OzyMandrill: Aug 12, 2013; Look upon my words
and despair

Captain Foo posted:

this poo poo was a great way to kill time in high school

poo poo
shot
soot
~~toot~~sort
~~tort~~
port
post

# ? Sep 23, 2016 15:56

big scary monsters: Sep 2, 2011; -~Ｓｋｕｌｌｗａｖｅ~-

i was trying to find a good memory efficient algorithm to compute the median of large datasets, didn't find one really but there are a number of cool approximations you can use. in the end i treated my data like a stream divided into frames and used reservoir gap sampling to approximate the median. it's not the most difficult or smartest algorithm out there but i thought it was nice

i've also been having fun with algorithms for principal curvature estimation in point clouds, been implementing this thing and learned that "osculating" is a word https://otik.uk.zcu.cz/bitstream/handle/11025/10828/Getto.pdf

i've come to the conclusion that point clouds suck for modelling 3d surfaces, use something with a continuous representation instead

# ? Sep 24, 2016 02:41

duTrieux.: Oct 9, 2003

toiletbrush posted:

That's really cool. A couple years ago I wrote am iOS Worms clone that started off using genetic algorithms to find the best shot to take to hit an enemy player until I realised that actually just choosing the best angle/power out of 10,000 random shots worked even better. It was disappointing it was such a lame algorithm but the results were brilliant because it would always take the 'obvious' shots when they existed, and choose the shortest 'blow a tunnel through the mountain/roof' route when that was the only option. It was weird how intelligent it seemed when it did sneaky stuff like taking advantage of bugs in collision detection etc.

My final year project at uni used them so a basic voice synthesiser would 'learn' how to pronounce words by example. It was sort of intelligible if you knew what it was trying to say.

this is neat

the bit about the algorithm doing sneaky stuff to seem more robust than it actually was is probably i think very close to how intelligence actually works

i'm pretty sure that at least half of what i do is rationalized as a conscious act after the fact

# ? Sep 24, 2016 02:49

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

big scary monsters posted:

i was trying to find a good memory efficient algorithm to compute the median of large datasets, didn't find one really but there are a number of cool approximations you can use. in the end i treated my data like a stream divided into frames and used reservoir gap sampling to approximate the median. it's not the most difficult or smartest algorithm out there but i thought it was nice

i've also been having fun with algorithms for principal curvature estimation in point clouds, been implementing this thing and learned that "osculating" is a word https://otik.uk.zcu.cz/bitstream/handle/11025/10828/Getto.pdf

i've come to the conclusion that point clouds suck for modelling 3d surfaces, use something with a continuous representation instead

you can implement quickselect with just streamed inputs and (intermediate) outputs - the actual resident-in-memory data is absolutely miniscule

# ? Sep 24, 2016 11:51

Cybernetic Vermin: Apr 18, 2005

how do you stream quickselect with less than linear memory? seems non-obvious since you can't really do anything with the output of a partitioning round without knowing which partition will become larger (and solving that is tantamount to solving the original problem)

# ? Sep 24, 2016 15:23

Jabor: Jul 16, 2010; #1 Loser at SpaceChem

you write two intermediate outputs, one for items larger than the pivot and one for items smaller - the only state you need to track is how many items went each way.

the intermediate streams make it linear in total additional storage required, but streamable storage is a whole lot cheaper than random-access memory.

# ? Sep 24, 2016 15:38

Adbot: ADBOT LOVES YOU

# ? May 16, 2024 02:09

Cybernetic Vermin: Apr 18, 2005

right, strictly speaking linear, but with a logarithmic bound on the number of reversals of head movement required on the work tape or something a bit wonky lik ethat. i expect "properly" sub-linear memory use is impossible without some solid additional assumptions though

# ? Sep 24, 2016 17:47

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > YOSPOS > Djikstra's Out: The Yospos Algorithm Thread

«‹›3 »