Ask General Programming Questions Not Worth Their Own Thread

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›671 »

digital-entropy: Apr 21, 2002

This is more applicable for an algorithms thread, but I couldn't find one.

Some background: I have a canvas in an Adobe Flex application that has n number of equal sized square children. User can drag these around, or add a new one. If they choose to add a new one, a new one is created and added to the canvas.

Problem: They are always added in the same place, which means if the user adds two or more without first moving them, they are added to the same position.

What I need to do is find a a square space within the canvas that is not occupied by any other components. I can brute force this by looking at every point (x,y) in the canvas and checking to see if the rectangle defined by (x, y, width, height) intersects with any other component, but that isn't a very finessed way of doing it. Has anyone come across this problem before, and if so, did you have a better way of solving the problem?

# ? Mar 17, 2009 19:48

Adbot: ADBOT LOVES YOU

# ? Jun 4, 2024 04:16

POKEMAN SAM: Jul 8, 2004

digital-entropy posted:

This is more applicable for an algorithms thread, but I couldn't find one.

Some background: I have a canvas in an Adobe Flex application that has n number of equal sized square children. User can drag these around, or add a new one. If they choose to add a new one, a new one is created and added to the canvas.

Problem: They are always added in the same place, which means if the user adds two or more without first moving them, they are added to the same position.

What I need to do is find a a square space within the canvas that is not occupied by any other components. I can brute force this by looking at every point (x,y) in the canvas and checking to see if the rectangle defined by (x, y, width, height) intersects with any other component, but that isn't a very finessed way of doing it. Has anyone come across this problem before, and if so, did you have a better way of solving the problem?

If you keep a sorted list in the X and Y directions you can binary search into the lists for where the intersecting rectangle would be, etc. It'd be O(lgn), which is faster than your O(n) solution.

# ? Mar 17, 2009 19:56

digital-entropy: Apr 21, 2002

Ugg boots posted:

If you keep a sorted list in the X and Y directions you can binary search into the lists for where the intersecting rectangle would be, etc. It'd be O(lgn), which is faster than your O(n) solution.

Good point. For now I have only 5 or 6 things max that I have to check against so it works fairly well. It started getting slow around 12 or so, so I optimized it slightly by skipping over n pixels in the direction I'm searching where n is the width or height of the component that intersects. That made it work reasonably fast so while there's no inherent need to optimize further I'll probably end up working on it later.

# ? Mar 17, 2009 22:13

Chuu: Sep 11, 2004; Grimey Drawer

A long time ago I saw a video (I think linked from slashdot?) about a very mature visual programming language whose goal was to simplify extremely complicated conditional paths.

Anyone remember the name of this language? I have a current project that I actually want to mess a bit around with it.

# ? Mar 18, 2009 17:03

Scaevolus: Apr 16, 2007

Chuu posted:

A long time ago I saw a video (I think linked from slashdot?) about a very mature visual programming language whose goal was to simplify extremely complicated conditional paths.

Anyone remember the name of this language? I have a current project that I actually want to mess a bit around with it.

Subtext

# ? Mar 18, 2009 17:39

Dicky B: Mar 23, 2004

Given the coordinates of points A and B and the distance D, what would be the best way of calculating the coordinates of point C?

I figured out a retardedly convulated way of doing it but I'm sure there must be a nice elegant solution. I'm no mathematician so I don't really know what I should be putting into Google.

# ? Mar 18, 2009 19:32

spiritual bypass: Feb 19, 2008; Grimey Drawer

Dicky B posted:

what I should be putting into Google.

Scalar multiplication of vectors? Maybe something about a unit vector?

# ? Mar 18, 2009 19:42

That Turkey Story: Mar 30, 2003

Dicky B posted:

Given the coordinates of points A and B and the distance D, what would be the best way of calculating the coordinates of point C?

B + D * ( normalized AB )

# ? Mar 18, 2009 19:48

Dicky B: Mar 23, 2004

That Turkey Story posted:

B + D * ( normalized AB )

Thank you this is great! Thank you also royallthefourth, this is fun to learn about. I wish they had taught us this kind of stuff in my graphics and animation classes.

# ? Mar 18, 2009 20:34

No Safe Word: Feb 26, 2005

Dicky B posted:

Thank you this is great! Thank you also royallthefourth, this is fun to learn about. I wish they had taught us this kind of stuff in my graphics and animation classes.

They (or the prerequisite classes) didn't? :what:

# ? Mar 18, 2009 20:49

fletcher: Jun 27, 2003; ken park is my favorite movie; Cybernetic Crumb

I want to parse a human readable string of time spans, not really sure how to approach this to make it clean. I'm sure I could come up with something that works, but I have a feeling it will be a sloppy mess of poo poo if I don't go in with a plan of attack. I'll be using Java for this.

The basic format is:
1:00pm to 2:00pm and 3:00pm to 4:00pm

It can come in other variations:
1:15-2
1-2 3-4
1-2 and 3-4
1 to 2 and 3-4
1300-1400

I also want to handle overlap:
1-2 and 2-3 turns into 1-3

Can anybody give me a nudge in the right direction?

fletcher fucked around with this message at 21:07 on Mar 18, 2009

# ? Mar 18, 2009 21:03

digital-entropy: Apr 21, 2002

fletcher posted:

Can anybody give me a nudge in the right direction?

Regular expressions?

# ? Mar 18, 2009 21:18

chocojosh: Jun 9, 2007; D00D.

fletcher posted:

I want to parse a human readable string of time spans, not really sure how to approach this to make it clean. I'm sure I could come up with something that works, but I have a feeling it will be a sloppy mess of poo poo if I don't go in with a plan of attack. I'll be using Java for this.

The basic format is:
1:00pm to 2:00pm and 3:00pm to 4:00pm

It can come in other variations:
1:15-2
1-2 3-4
1-2 and 3-4
1 to 2 and 3-4
1300-1400

I also want to handle overlap:
1-2 and 2-3 turns into 1-3

Can anybody give me a nudge in the right direction?

Is it possible to write a mini-parser to take care of this? This may be overkill for what you want though..

code:

<time-set> ::= <time-range> and <time-range> | 
               <time-range> <time-range> |
               <time-range>
<time-range> ::= <time> <connector> <time>
<time> ::= specific time formats
<connector> ::= to | -

# ? Mar 19, 2009 00:09

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

fletcher posted:

Can anybody give me a nudge in the right direction?

You asked for a nudge instead of a solution, so I'll give you a solution in a different language using principles that may be difficult to translate over. It's a fun little trivial problem, though.

chocojosh posted:

Is it possible to write a mini-parser to take care of this?

Yes, it is!

chocojosh posted:

This may be overkill for what you want though..

Blasphemy!

code:

> import Control.Monad
> import Control.Monad.State
> import Data.List

> data Time = Time Int Int
>   deriving (Eq, Show)
> data Timespan = Timespan Time Time
>   deriving (Eq, Show)

Parsing a string is the process of beginning with some state (the string to parse) and whittling away at the beginning of it until we have the empty state, and our result. We admit that there may be ambiguity in our parsing, so we elect to produce a list of possible results - this also allows us to do backtracking, as we'll see.

code:

> type TimespanP = StateT String []

We expect to want to ignore whitespace from time to time, so let's write a function that ignores any whitespace at the beginning of the state.

code:

> whitespace :: TimespanP ()
> whitespace = modify $ dropWhile (== ' ')

We also will need to compare the beginning of the state with some literal, so let's generalize that next.

code:

> expect :: String -> TimespanP ()
> expect str = do
>   whitespace
>   match <- gets $ take $ length str
>   guard $ match == str
>   modify $ drop $ length str

And we'll be reading integers from the input string. We do this with some pre-existing support from Haskell, because parsing integers ourselves is boring.

code:

> number :: TimespanP Int
> number = do
>   whitespace
>   str <- get
>   (num, str') <- msum $ map return $ reads str
>   put str'
>   return num

Now that the preliminaries are out of the way, we can start parsing times.

code:

> time :: TimespanP Time
> time = do
>   first <- number
>   if first > 100
>     then return $ Time (first `div` 100) (first `mod` 100)
>     else
>       (do
>         expect ":"
>         second <- number
>         return $ Time first second
>       ) `mplus` (return $ Time first 0)

That doesn't handle AM/PM, so we wrap it in something that does.

code:

> timeampm :: TimespanP Time
> timeampm = do
>   (Time hour min) <- time
>   (do expect "pm"; return $ Time (hour + 12) min) `mplus` (do expect "am"; return $ Time hour min)

> anytime :: TimespanP Time
> anytime = timeampm `mplus` time

Timespans are just two times with a divider.

code:

> timespan :: TimespanP Timespan
> timespan = do
>   t1 <- anytime
>   expect "to" `mplus` expect "-"
>   t2 <- anytime
>   return $ Timespan t1 t2

Finally, a time string is just a sequence of timespans, ending with the end of the string.

code:

> timestr :: TimespanP [Timespan]
> timestr = (
>   do
>     span <- timespan
>     expect "and" `mplus` return ()
>     spans <- timestr
>     return $ span : spans
>   ) `mplus` (
>   do
>     whitespace
>     str <- get
>     guard $ str == ""
>     return []
>   )

A little wrapper to parse time strings.

code:

> parseTimes :: String -> [Timespan]
> parseTimes str = head $ evalStateT timestr str

And we're done! The parseTimes function will take a string in the format you specified, and return the first successful parse of it into a sequence of timespans (it is unlikely that there will be multiple successful parses; I haven't bothered to check if this grammar is actually ambiguous or not).

Edit: For overlapping, we just define a sort order on timespans, then walk down a sorted list and collapse overlaps.

code:

> instance Ord Time where
>   compare (Time hour1 min1) (Time hour2 min2) =
>     case compare hour1 hour2 of
>       EQ -> compare min1 min2
>       c  -> c

> instance Ord Timespan where
>   compare (Timespan s1 e1) (Timespan s2 e2) =
>     case compare s1 s2 of
>       EQ -> compare e1 e2
>       c  -> c

> overlaps :: Timespan -> Timespan -> Bool
> overlaps (Timespan s1 e1) (Timespan s2 e2) = e1 >= s2

> merge :: Timespan -> Timespan -> Timespan
> merge (Timespan s1 e1) (Timespan s2 e2) | e1 > e2   = Timespan s1 e1
>                                         | otherwise = Timespan s1 e2

> nonOverlapping :: [Timespan] -> [Timespan]
> nonOverlapping [] = []
> nonOverlapping (t1:t2:ts) | t1 `overlaps` t2 = nonOverlapping $ (t1 `merge` t2) : ts
> nonOverlapping (t:ts)                        = t : nonOverlapping ts

> parseNonOverlapping :: String -> [Timespan]
> parseNonOverlapping str = nonOverlapping $ sort $ parseTimes str

ShoulderDaemon fucked around with this message at 00:38 on Mar 19, 2009

# ? Mar 19, 2009 00:14

narbsy: Jun 2, 2007

fletcher posted:

I want to parse a human readable string of time spans, not really sure how to approach this to make it clean. I'm sure I could come up with something that works, but I have a feeling it will be a sloppy mess of poo poo if I don't go in with a plan of attack. I'll be using Java for this.

The basic format is:
1:00pm to 2:00pm and 3:00pm to 4:00pm

It can come in other variations:
1:15-2
1-2 3-4
1-2 and 3-4
1 to 2 and 3-4
1300-1400

I also want to handle overlap:
1-2 and 2-3 turns into 1-3

Can anybody give me a nudge in the right direction?

Check out the Ruby gem Chronic, which does natural date/time parsing. Might make life easier if it works with the format you've got.

# ? Mar 19, 2009 00:24

digital-entropy: Apr 21, 2002

ShoulderDaemon posted:

stuff

Christ, he asked for a nudge and you pushed him off the cliff... good show!

# ? Mar 19, 2009 00:48

Ensign Expendable: Nov 11, 2008; Lager beer is proof that god loves us; Pillbug

Can anyone recommend an 8085 Assembler IDE? I need a memory editor and labels, that's about it. I already tried the Olshonsoft one.

# ? Mar 19, 2009 23:20

Brackhar: Aug 26, 2006; I'll give you a definite maybe.

Can any of you tell me what CSS/HTML is required to center two images side by side? My end goal is to create a 2x2 grid of images, with each being their own html link.

# ? Mar 20, 2009 03:37

POKEMAN SAM: Jul 8, 2004

Brackhar posted:

Can any of you tell me what CSS/HTML is required to center two images side by side? My end goal is to create a 2x2 grid of images, with each being their own html link.

Sounds like you want display 4 images in a table!

code:

<table>
<tr>
<td><img src="one.jpg" /></td>
<td><img src="two.jpg" /></td>
</tr>
<tr>
<td><img src="three.jpg" /></td>
<td><img src="four.jpg" /></td>
</tr>
</table>

HTML linking of the images left as an exercise to the reader.

:smugspike:

# ? Mar 20, 2009 04:41

baquerd: Jul 2, 2007; by FactsAreUseless

Only little girls use tables. The real solution is to set up a tapestry installation and through that deliver a custom applet layout of the images.

# ? Mar 20, 2009 05:33

ayb: Sep 12, 2003; Kills Drifters for erections

I am in Programming I and we're using Java to learn with. I have an assignment with the following question

Write a Java application to find all Pythagorean Triples for side1, side2 and the hypotenuse, each no larger than 200. Use a triple-nested for loop that tries all possibilities.

SUGGESTION: Use a set of 3 nested loops, with an if construct inside the inner-most loop.

I have no idea how to find a Pythagorean Triple with code. Any sort of guidance on that would be nice but I would prefer to obviously write the code myself

# ? Mar 21, 2009 05:01

Scaevolus: Apr 16, 2007

ayb posted:

I am in Programming I and we're using Java to learn with. I have an assignment with the following question

Write a Java application to find all Pythagorean Triples for side1, side2 and the hypotenuse, each no larger than 200. Use a triple-nested for loop that tries all possibilities.

SUGGESTION: Use a set of 3 nested loops, with an if construct inside the inner-most loop.

I have no idea how to find a Pythagorean Triple with code. Any sort of guidance on that would be nice but I would prefer to obviously write the code myself

here's a hint

a * a + b * b == c * c

# ? Mar 21, 2009 05:13

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

ayb posted:

I am in Programming I and we're using Java to learn with. I have an assignment with the following question

Write a Java application to find all Pythagorean Triples for side1, side2 and the hypotenuse, each no larger than 200. Use a triple-nested for loop that tries all possibilities.

SUGGESTION: Use a set of 3 nested loops, with an if construct inside the inner-most loop.

I have no idea how to find a Pythagorean Triple with code. Any sort of guidance on that would be nice but I would prefer to obviously write the code myself

ooh ooh ooh

code:

> import Control.Monad

A Pythagorean triple is a set of numbers a, b, and c such that a² + b² = c². We define a helper function to test this; it takes three numbers and returns a boolean indicating if they are a Pythagorean triple or not.

code:

> pythagoreanTriple :: Int -> Int -> Int -> Bool
> pythagoreanTriple a b c = a^2 + b^2 == c^2

Now, we simply test every possible a, b, and c combination by looping through all possible as, inside that loop going through all possible bs, and inside that loop going through all possible cs. At the innermost, we check if the current combination is a Pythagorean triple.

code:

> allPythagoreanTriplesUpto :: Int -> [(Int, Int, Int)]
> allPythagoreanTriplesUpto n = do
>   a <- [1..n]
>   b <- [1..n]
>   c <- [1..n]
>   guard $ pythagoreanTriple a b c 
>   return (a,b,c)

Note that this does a lot of extra work, and spits out duplicate answers (3,4,5 and 4,3,5 for example).

# ? Mar 21, 2009 05:20

Scaevolus: Apr 16, 2007

ShoulderDaemon posted:

ooh ooh ooh
Note that this does a lot of extra work, and spits out duplicate answers (3,4,5 and 4,3,5 for example).

Sure, do the guy's homework for him. :rolleyes:

e: might as well...

code:

[(a, b, c) for c in xrange(201) for b in xrange(c) for a in xrange(b) if a**2 + b**2 == c**2]

Scaevolus fucked around with this message at 09:32 on Mar 21, 2009

# ? Mar 21, 2009 05:30

baquerd: Jul 2, 2007; by FactsAreUseless

Scaevolus posted:

Sure, do the guy's homework for him.

He still has to translate from moon to Java.

# ? Mar 21, 2009 05:51

Avenging Dentist: Oct 1, 2005; oh my god is that a circular saw that does not go in my mouth aaaaagh

Scaevolus posted:

Sure, do the guy's homework for him.

People love doing this because they get to show off their amazing ability to solve freshmen-level assignments thanks to completing a degree in CS. Bravo, folks. Bravo.

# ? Mar 21, 2009 06:48

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

quadreb posted:

He still has to translate from moon to Java.

You're right, I made that way too simple.

code:

0>1+:01p0>1+:02p0>1+:03p03g:*02g:*+01g:*-v
 ^$<     |-g10:$<|-g20:<              _v#<
         #      ^<    v,*52.g10.g20.g30<
         ^       <     #
   ^     <            >^

This version is better optimized.

# ? Mar 21, 2009 07:02

Mithaldu: Sep 25, 2007; Let's cuddle.

What the christ is that?

# ? Mar 21, 2009 08:06

ShoulderDaemon: Oct 9, 2003; support goon fund; Taco Defender

Mithaldu posted:

What the christ is that?

Befunge, although I'm fairly certain I could've folded it better and my use of storage instead of pure stack manipulation is lame. If it's not obvious, I'm kind of bored.

Edit: And that version also has an extra control structure that I left in because I must've missed it as I revised my code. Oops.

# ? Mar 21, 2009 08:16

tef: May 30, 2004; -> some l-system crap ->

Hopping on the pythagorean train:

code:

every (z is 1 .. 200 && y is 1 .. z && x is 1 .. y && 0 is x * x + y * y - z * z && [x y z])

tef fucked around with this message at 09:50 on Mar 21, 2009

# ? Mar 21, 2009 09:45

hey mom its 420: May 12, 2007

Okay guys but can you write fizz buzz? :smug:

# ? Mar 21, 2009 11:06

Ensign Expendable: Nov 11, 2008; Lager beer is proof that god loves us; Pillbug

drat, I'm not cool enough to solve Pythagorean triples in some esoteric language.

# ? Mar 21, 2009 16:23

Mustach: Mar 2, 2003; In this long line, there's been some real strange genes. You've got 'em all, with some extras thrown in.

Haskell is the best language for solving trivial problems.

# ? Mar 21, 2009 16:30

tk: Dec 10, 2003; Nap Ghost

Ensign Expendable posted:

drat, I'm not cool enough to solve Pythagorean triples in some esoteric language.

code:

var homework =
	from x in Enumerable.Range(1, 200)
	from y in Enumerable.Range(1, 200)
	from h in Enumerable.Range(1, 200)
	where x * x + y * y == h * h
	select new {x, y, h};

# ? Mar 21, 2009 16:33

chocojosh: Jun 9, 2007; D00D.

While working on my Java school project I had to debug some NullPointerExceptions. This made me wonder:

How can Java have Null Pointer Exceptions if Java only has references?

# ? Mar 21, 2009 17:28

shrughes: Oct 11, 2008; (call/cc call/cc)

chocojosh posted:

How can Java have Null Pointer Exceptions if Java only has references?

Well gee, don't read the documentation.

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/NullPointerException.html

# ? Mar 21, 2009 17:55

chocojosh: Jun 9, 2007; D00D.

shrughes posted:

Well gee, don't read the documentation.

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/NullPointerException.html

I meant it as a tongue-in-cheek joke because of people who say that "Java doesn't have pointers". If Java doesn't have pointers, it should be a NullReferenceException

# ? Mar 21, 2009 19:13

shrughes: Oct 11, 2008; (call/cc call/cc)

chocojosh posted:

If Java doesn't have pointers, it should be a NullReferenceException

No it shouldn't -- Java was targeting C++ programmers.

# ? Mar 21, 2009 19:43

That Turkey Story: Mar 30, 2003

shrughes posted:

No it shouldn't -- Java was targeting C++ programmers.

They are called references in Java, so why would they call their exceptions null pointer exceptions? If you follow your logic of Java being targeted at C++ programmers, then Java reference types shouldn't be called reference types, they should be called pointer types. The point is, Java is needlessly inconsistent, not to mention the fact that the language is gay as hell to begin with.

# ? Mar 21, 2009 20:26

Adbot: ADBOT LOVES YOU

# ? Jun 4, 2024 04:16

Lee Bow: May 11, 2008; by Fistgrrl

I'm new to vbulletin, but cannot figure out why this 20 pixel boarder shows up around my forums. Any help is greatly appreciated.

Click here for the full 1280x600 image.

wait, I think I can handle it after all.

Lee Bow fucked around with this message at 00:01 on Mar 22, 2009

# ? Mar 21, 2009 23:37

The Something Awful Forums > Discussion > Serious Hardware/Software Crap > The Cavern of COBOL > Ask General Programming Questions Not Worth Their Own Thread

«‹›671 »