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

«‹›6 »

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

Red Alert posted:

Basically what I need is a function that constantly improves a value until it gets to its desired result. It takes a function that improves a value, a function that decides when a value is close enough to the actual one, and it returns a function that takes a value and returns an improved value.

code:

import Data.List

iterativeImprove :: (Float -> Bool) -> (Float -> Float) -> (Float -> Float)
iterativeImprove goodEnough improve initialValue = head $ dropWhile (not . goodEnough) $ unfoldr (\v -> Just (v, improve v)) initialValue

Reading from right to left: We start with the initial value. We create an infinite list of values by accumulating calls to the improve function. We discard values from the head of this list until we find something good enough. We return that value.

Note that I would probably split this into two functions: One that just does the unfoldr stuff, and one that does the dropWhile and head. It's occasionally useful to deal with an infinite lazy list of values for stuff like this rather than just the least-good-enough value.

Edit: Also, all your deriv, goodEnough, and improve functions would be more normally written without those lambdas but just doing all the pattern matching left of the equals. Haskell lets you curry functions, so the type a -> (b -> c) is the same as a -> b -> c.

ShoulderDaemon fucked around with this message at 08:11 on Jan 28, 2009

# ¿ Jan 28, 2009 08:02

Adbot: ADBOT LOVES YOU

# ¿ May 15, 2024 13:07

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

Red Alert posted:

Thanks for the quick response, but that seems a little too complicated at this time. I'm just starting the 4th week of this class and haven't learned anything about Just or $.

"a b c $ d e f" is shorthand for, essentially, "a b c (d e f)". The Just is sort of an uninteresting part of the type required by unfoldr.

Red Alert posted:

Also, I'm not really sure how to do the pattern matching after the equals. Would I just do something like this?

improve f = guess -> guess - f(guess)/(deriv f(guess))

You've got your parenthesis a bit mixed up, what you want is:
improve f = \guess -> guess - (f guess) / (deriv (f guess))
which is the same as
improve f guess = guess - (f guess) / (deriv (f guess))
which is the same as
improve f guess = guess - (f guess) / (deriv $ f guess)
if that helps you understand $ and currying at all.

Anyway, we can rewrite iterativeImprove as a few simpler functions.

Have you been taught about lazy lists yet? We can write:

code:

improvedValues :: (Float -> Float) -> Float -> [Float]
improvedValues improve initialValue = initialValue : map improve (improvedValues improve initialValue)

This creates an infinite list of values, starting with an initial value, and improving it by one step each time, using recursion. The unfoldr function is just sort of shorthand for this kind of thing.
Edit: Durr, I'm sort of dumb right now.

Now that we have this improvedValues function, we can use it:

code:

firstGoodEnough :: (Float -> Bool) -> [Float] -> Float
firstGoodEnough goodEnough (x:xs) = if goodEnough x
                                      then x
                                      else firstGoodEnough goodEnough xs

Again, we're using recursion and a list. This time we consume the list one element at a time, check if the value is good enough, if it is we return it, otherwise we check the rest of the list. The head and dropWhile function do the same thing, or you can use find, or a few other similar functions.

Finally, we can put it all together:

code:

iterativeImprove :: (Float -> Bool) -> (Float -> Float) -> Float -> Float
iterativeImprove goodEnough improve initialValue = firstGoodEnough goodEnough (improvedValues improve initialValue)

This is just sticking our helper functions together so they do what we want.

ShoulderDaemon fucked around with this message at 08:42 on Jan 28, 2009

# ¿ Jan 28, 2009 08:25

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

Here's how I would solve the problem. I'm going to spoiler the actual definitions for the sake of your homework assignment; you should be able to write these functions on your own given the types and explanations.

We will calculate the square root of n based on Newton's method to find a root of x^2 - n.

> rootFunc :: Float -> Float -> Float
> rootFunc n x = x^2 - n

Newton's method requires the derivative of our target function. The derivative of x^2 - n is simply 2x by first-year calculus.
I include the n parameter simply for consistency with rootFunc, and to generalize to other applications than square roots.

> rootFunc' :: Float -> Float -> Float
> rootFunc' n x = 2 * x

This is our initial crappy guess for the square root of a number.

> guess :: Float -> Float
> guess n = n / 2

Newton's method operates by iterative improvement on a guess.

> improve :: (Float -> Float) -> (Float -> Float) -> Float -> Float
> improve f f' x = x - (f x) / (f' x)

Now, we can construct an infinite list of successive improvements.

> successiveImprovements :: (Float -> Float) -> Float -> [Float]
> successiveImprovements improve initialValue = initialValue : map improve (successiveImprovements improve initialValue)

The generalized Newton's method: Given a function to find the root of, that function's derivative, and a guess, produce an infinite list of estimates.

> newtonMethod :: (Float -> Float) -> (Float -> Float) -> Float -> [Float]
> newtonMethod f f' guess = successiveImprovements (improve f f') guess

Given an infinite list of successive improvements, we want to remove the high-error values at the start.
We do this by dropping elements until the difference between elements is no more than some epsilon.

> reduceError :: Float -> [Float] -> [Float]
> reduceError epsilon (x1:x2:xs) = if abs (x1 - x2) >= epsilon then reduceError epsilon (x2:xs) else (x1:x2:xs)

I'll define a global epsilon, here.

> epsilon :: Float
> epsilon = 0.000001

Now, we produce the infinite list of estimates of the square root of a number, using Newton's method.

> newtonRootEstimates :: Float -> [Float]
> newtonRootEstimates n = newtonMethod (rootFunc n) (rootFunc' n) (guess n)

We restrict those estimates to the "good enough" estimates.

> newtonRootGoodEstimates :: Float -> [Float]
> newtonRootGoodEstimates n = reduceError epsilon (newtonRootEstimates n)

Finally, we simply take the first such "good enough" estimate, and use that as the Newton root.

> newtonRoot :: Float -> Float
> newtonRoot n = head (newtonRootGoodEstimates n)

# ¿ Jan 28, 2009 09:17

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

dealmaster posted:

I'm still working on this and am trying to get Math.Round to cooperate using the MidpointRounding arguments. Anyways, I'm trying to figure out why this is happening:

double x = 9076.095;
x = Math.Round(x, 2, MidpointRounding.AwayFromZero);

This should store 9076.1 into x, but it doesn't, it ends up putting 9076.09 into it. What is going on here, do you guys have any advice? I'm really at a loss here.

Rounding to positions other than the normal decimal point is normally done by multiplying by a multiple of 10, rounding to the decimal point, then dividing.

9076.095 * 100 is 907609.49999999 with doubles, which rounds to 907609.

If you can get away with fixed-point, it's a much better way to handle situations like this.

ShoulderDaemon fucked around with this message at 23:25 on Jan 28, 2009

# ¿ Jan 28, 2009 23:23

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

dealmaster posted:

Yeah, that's true. I tried this and got the right result, so even though is hideous, I'll probably end up using it because it works:

double x = 9076.095;
x *= 10;
x = Math.Round(x, 1, MidpointRounding.AwayFromZero);
x /= 10;

I guess I'll have to do this, but I've got about 30 or 40 rounding calls in my code (thanks to our actuaries), so this could end up getting messy.

Keep in mind that your technique may or may not work, depending on what numbers are passing through it. If you always need to be accurate to two digits, you should really just be storing everything always multiplied by 100 and always do your rounding at the decimal point. Floating point math is designed for floating point situations; integer math is more appropriate for fixed point situations.

# ¿ Jan 28, 2009 23:34

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

wrok posted:

The obvious way to do this is to permute all possible sets of valid pairings and calculate which set has the best result. This is very slow of course. Is there a better way?

Well, there's only six combinations, so it can't be that slow. But assuming you're talking about the general case, you can do some prunings by keeping track of the best result you've gotten so far, and each time you take a possible assignment from the list of remaining assignments, do a trivial check of "does the current value, plus the maximum possible value from each row remaining to be assigned, exceed the best value I've seen?" and similarly for each remaining column. You can also heuristically always choose the assignment which adds the most immediate value.

So, in literate Haskell...

code:

Get a bundle of imports out of the way.

> import Control.Monad.Identity
> import Control.Monad.List
> import Control.Monad.Reader
> import Control.Monad.State
> import Control.Monad.Writer
> import Data.List
> import qualified Data.Map as M

Assignments are tuples of integers and characters, values are integers.

> type Assignment = (Int, Char)
> type Value      = Int

We'll maintain maps of available assignments (that is, assignments which do not conflict with any existing assignment) to values.

> type AvailableAssignments = M.Map Assignment Value

The starting set of available assignments.

> topAvailable :: AvailableAssignments
> topAvailable = M.fromList
>   [ ((1, 'a'), 10), ((1, 'b'),  9), ((1, 'c'),  5)
>   , ((2, 'a'),  8), ((2, 'b'),  1), ((2, 'c'),  2)
>   , ((3, 'a'),  5), ((3, 'b'),  3), ((3, 'c'),  7)
>   ]

Backtracking search in ListT with global state, per-result list of assignments, and local available assignments.

> type Search a = WriterT [Assignment] (ReaderT AvailableAssignments (ListT (StateT Value (Identity)))) a

> runSearch :: Search a -> [(a, [Assignment])]
> runSearch s = runIdentity $ evalStateT (runListT $ runReaderT (runWriterT s) topAvailable) (-1)

Backtracking choice of available assignment.
We take the associations from the available assignments map, sort to maximize the value, then lift that list into our search monad.

> getAssignment :: Search (Assignment, Value)
> getAssignment = do
>   availableMap <- ask
>   let availableList = sortBy (\(a1, v1) (a2, v2) -> compare v2 v1) $ M.assocs availableMap
>   msum $ map return availableList

Given an assignment and a subsearch, we add the assignment to the per-result list of assignments taken,
and locally filter the available assignments to remove those that conflict for the subsearch.

> withAssignment :: Assignment -> Search a -> Search a
> withAssignment a@(r,c) s = do
>   tell [a]
>   local (M.filterWithKey (\(r',c') v -> r /= r' && c /= c')) s

Given a current value, we find the best value for every column remaining to be assigned, sum those values,
and prune the search if that doesn't exceed the best result we've seen.

> pruneByColumns :: Value -> Search ()
> pruneByColumns value = do
>   available <- ask
>   let bestPossibleColumns = M.foldWithKey (\(r, c) v m -> M.insert c (max v $ M.findWithDefault 0 c m) m) M.empty available
>   let bestPossibleTotal   = sum $ M.elems bestPossibleColumns
>   best <- get
>   guard $ value + bestPossibleTotal > best

Same for rows.

> pruneByRows :: Value -> Search ()
> pruneByRows value = do
>   available <- ask
>   let bestPossibleRows  = M.foldWithKey (\(r, c) v m -> M.insert r (max v $ M.findWithDefault 0 r m) m) M.empty available
>   let bestPossibleTotal = sum $ M.elems bestPossibleRows
>   best <- get
>   guard $ value + bestPossibleTotal > best

We're done if there are no remaining assignments.

> areDone :: Search Bool
> areDone = do
>   availableMap <- ask
>   return $ M.size availableMap == 0

The search itself. We prune first, then check if we're done.
If we are, save the current value as the new best value (pruning ensures it can't be worse), then return it.
Otherwise, we take an assignment, and subsearch with that assignment.

> theSearch :: Value -> Search Value
> theSearch value = do
>   pruneByColumns value
>   pruneByRows value
>   done <- areDone
>   if done
>     then do
>       put value
>       return value
>     else do
>       (assignment, assignmentValue) <- getAssignment
>       withAssignment assignment $ theSearch $ value + assignmentValue

The best result is the last result.

> main :: IO ()
> main = do
>   let result = runSearch $ theSearch 0
>   print $ last result

Edit: Slight generality changes and a little cleanup.

ShoulderDaemon fucked around with this message at 23:43 on Jan 30, 2009

# ¿ Jan 30, 2009 23:24

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

jschmidt posted:

Anyone have any idea of a program that will do that? If not, how easy would it be to hire someone to create something that did? Even if it's an add-on to some other program.

Building an XSL transform for your XML schema isn't a hard task for someone experienced, although if you go that approach you may need a new transform for every set of "custom information", depending on exactly what database features you're thinking of using.

Edit:

Mithaldu posted:

How to put this... The question you asked is similar to asking whether there's a program that can import a report written in plain english.

XML may be terrible, but it's nowhere nearly that bad, and there are frameworks like XSL for doing transforms to different forms; this was, after all, one of the primary design purposes of XML.

ShoulderDaemon fucked around with this message at 18:55 on Feb 8, 2009

# ¿ Feb 8, 2009 18:52

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

Rocko Bonaparte posted:

I wanted to ask some more stuff about neural networks, but I wondered first if somebody could recommend a good overall theory book on them that's focused on using neural networks, and less on making something from scratch. You'll probably get what I mean from the questions I have. Assuming I am using backwards propagation to train a neural network:

I'll start with a question for you: Why are you using a neural network? They really aren't suitable for more than a few specific subfields in machine learning, and they tend to perform poorly outside those areas. What specific problem are you solving, and if you're following someone's existing working on machine learning in that area, what papers are you basing your work on?

Rocko Bonaparte posted:

1. What does it mean that the single greatest factor in training the network is the random variables with which I start? I seem to only get a few percentage reduced error from my starting number after 500 runs, and the success seems to depend more on the random values.

Most likely, either your training data is poor quality, the problem you are solving has too many local minima, or you implemented your algorithm incorrectly.

Rocko Bonaparte posted:

2. What are some good rule of thumb formulas for calculation the amount of neurons for my hidden layer? The first one I heard was to have 1.5x as many as the input layer, but I've heard of other formulas based on the number of different combinations I want represented in my output.

There is a certain amount of experimentation involved here. 1.5*input is a decent enough place to start for most problems.

Rocko Bonaparte posted:

3. Have there been any advances in training neural networks that I should be looking for instead? I don't mean things like pruning but more like things that make backwards propagation obsolete.

In my experience, most highly successful supervised-training neural networks are essentially trained by backpropagation, but have been modified and carefully tuned to match the model relevant for their operation and frequently use slight variants of the neural network algorithm to that end. In many cases, they are combined with other machine learning techniques in order to make a gestalt learner with the neural network portion specialized to the specific aspects of the model it is best suited for, and supplemented with Bayesian or decision-tree learners for other model aspects.

Edit: I tend to strongly discourage neural networks because even in cases where they are well-suited and the training data available is of acceptable quantity and quality, they still require tweaking and experimentation to get robust results out. Worse, if your problem isn't suitable for neural network learners, and that isn't obvious to you from your model, then the failure case neural networks deliver is terrible: they will mostly look like they just aren't well trained, complete with occasionally and unpredictably giving you high-confidence-seeming answers that appear correct. It's incredibly unhelpful, and smart people have wasted years fighting to get neural networks to solve problems that other machine learning techniques can adapt to in mere weeks of programmer time.

ShoulderDaemon fucked around with this message at 07:21 on Feb 9, 2009

# ¿ Feb 9, 2009 07:15

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

In Haskell you can define your own type in the Num class, and give it some nonsense fromIntegral definition, which would have approximately the same effect.

# ¿ Feb 9, 2009 23:47

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

You want "mail merge", which should be documented in the help for office.

# ¿ Feb 12, 2009 04:50

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

First, you should contact the original author, show him your code, and ask if he wants to integrate into a new version of his class. If so, arrange with him for how you should be credited. If you have significantly rewritten the code, he may want you to become the primary maintainer.

If he would prefer not to integrate your code in his module, then you can release your code on your own. You should choose a new name, credit him with the original work, and provide a link to the original class. Make sure that the license you are releasing under is compatible with the license he chose.

# ¿ Feb 12, 2009 09:56

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

BDA7DD posted:

I'm trying to make a bash script to automate the backup process and ran into a minor issue.

You shouldn't be using the -b argument to ls.

Instead of this:

code:

for DIR in $(ls -b /foo); echo $DIR; done

You want code that's something like this:

code:

for DIR in "$(ls /foo)"; echo "$DIR"; done

The first set of quotes makes bash separate results from ls by line rather than by word, which is far more reliable than hoping ls gets its escaping right and trying to make bash respect it. The second set of quotes means that even if the directory you are currently operating on has wacky characters in it, bash will pass it as a single argument.

As a rule of thumb: never try to generate escape sequences if you can avoid it. Just use the quoting patterns, and avoid escapes altogether.

# ¿ Feb 13, 2009 21:50

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

riggsninja posted:

Flash seems to think 0 is out the right (3 o'clock), and it goes counter-clockwise. But I don't fully trust flash, cause it also thinks there's only 180 degrees and everything past that is negative.

This is how it's typically done in mathematics. If you choose anything else, then the cos and sin functions won't have their traditional meanings.

Edit: I guess if your origin is in the upper-left instead of the lower-left corner, then having zero degrees point to the right with positive degrees moving clockwise is reasonable.

ShoulderDaemon fucked around with this message at 06:41 on Feb 19, 2009

# ¿ Feb 19, 2009 06:28

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

Felony posted:

I am not claiming to be good in any of these by the way.

Many of us will argue that this is because you started with PHP.

# ¿ Feb 21, 2009 03:57

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

Buffer errors normally mean you didn't provide a large enough output buffer.

# ¿ Feb 22, 2009 03:03

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

Maybe you could provide code, spec, and sample file, then?

# ¿ Feb 22, 2009 03:14

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

bitprophet posted:

Could your file be sufficiently large that it's eating up all your free memory (or conversely, if you're running this without much free memory to start with, the file doesn't need to be all that big)?

Based on what he'd posted before his edit, it only decompressed to an 8KiB stream. I was able to recreate the error message he was getting after mangling his code to work on a 64-bit machine, and changing to separate decompress objects also fixed it. I assume there's some stupid issue with Python's zlib binding at work.

# ¿ Feb 22, 2009 03:52

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

kaschei posted:

I'm taking an AI course in lisp. We're making game-playing programs that play each other in a very structured way; when it's your turn, a function you write is called with the board information, etc., which is expected to return a move. You can store information for between moves, but I don't see an obvious way to do "thinking" on your opponent's turn in this situation. Is there a way to split a process off, like a thread in java? My instinct says no, it's interpreted and functional and native lisp has no support for doing two things at once, but if there's a way to use my opponent's time I'd really like to know.

It depends on your Lisp implementation, but most Lisps support some kind of threads. This is likely to be fairly close to whatever your implementation does.

# ¿ Feb 22, 2009 06:18

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

Dijkstracula posted:

This may not be the best thread to ask this, but does anyone know how public nethack servers that you connect to over telnet handle ncurses running over different sockets? I'm working on something similar, and I was hoping to use some screen-handling API, but it doesn't appear that ncurses really is intended to write to use anything other than stdin/stdout. Thoughts?

For the most part, they arrange a pty for each socket, then spawn a separate process for each pty that the ncurses code runs in (talking on stdin/stdout), and do anything fancy with IPC.

ncurses and terminfo are seriously the worst code.

# ¿ Feb 25, 2009 18:09

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

Dijkstracula posted:

Blech, this doesn't sound like it will play nicely with my poll()/select() server. Sounds like I'll have to come up with something myself - all I really need is something to handle terminal control codes and some very basic window layout.

Even if you try to use the terminfo directly, you will find that it doesn't play nicely with anything but stdin/stdout and has essentially no way to reliably handle multiple terminals at a time.

If you find yourself reimplementing the terminfo library, I may be able to give you some pointers; I've done partial reimplementations myself.

I can tell you that if you just hardcode in the proper handling rules and escape sequences for a basic xterm, no-one will ever complain and it will work somewhat more reliably. Seriously, everyone nowadays is xterm-compatible to at least a first approximation and there are some broken telnet clients which will try to report as vt2* but expect no padding instead (like an xterm) and will choke when ncurses itself tries to talk to them.

# ¿ Feb 25, 2009 18:30

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

Dijkstracula posted:

Thanks for this; I may take you up on this once I've thought the new problem through better (ie. it only just occurred to me that I won't have a SIGWINCH if I'm just dumping poo poo through a socket, so a lot of what I'm doing has to be thrown out the window)

Telnet clients should send a window size option when they resize, so that's not a major problem. Feel free to email me if you'd rather not clutter the thread, jblake@omgwallhack.org.

# ¿ Feb 26, 2009 04:41

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

functional posted:

It helps new questions stand out from ongoing discussions. It's common practice in other threads, where it doesn't draw any attention. Typically it's followed by a more in depth problem description, but here the question was so straightforward it didn't seem to need elaboration.

Well I hate it, and by extension, you.

Has anyone in here done programming with a ZigBee stack? I'm looking at a few and can't really bring myself to care about any of the various special features (I have an extremely simple application) but if anyone has any opinions about which are particularly easy or painful to work with, that would be useful.

# ¿ Mar 3, 2009 05:07

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

I used ^((?:[^,]+,)*?)((?:[^,]+,)+?)\2+$ to match strings of the form a,b,c,d,e, and find the shortest prefix before repetition, and the shortest repetition pattern with that prefix.

First, anchor to the beginning of the string. Then, capture a minimal prefix, comprised of zero or more elements (where an element is one or more noncommas followed by a comma). Next capture a minimal repetition, which is again comprised of zero or more elements. Finally, repeat exactly the second capture until we complete the string.

Edit:

GrumpyDoctor posted:

unless I'm wildly mistaken you can't actually do that with a finite-state machine

Backreferences mean that the "regular expression" is no longer a finite-state machine.

ShoulderDaemon fucked around with this message at 20:37 on Mar 11, 2009

# ¿ Mar 11, 2009 20:34

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

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

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

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

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

cr0y posted:

Does anyone know if there is an easy way to encrypt large files in php with a public key?

Please don't write your own encryption software, you'll do it wrong. Find some library that complies with RFC 3852.

# ¿ Mar 25, 2009 20:37

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

Fruit Smoothies posted:

I have 12 categories that need to be placed doubled up in 6 boxes. However, some of the categories can't pair up. Kinda like "cold" and "hot" can't go together. How would I go writing a program that can solve this type of combination problem, but apply rules to it? Is there a program that exists, or easy way of doing this without a computer program?

Cheers.

Here's a horrible ineffecient solution which should work.

If we need to assign 0 elements to n boxes, there is trivially only a single valid assignment: n empty boxes.

If we need to assign j > 0 elements to n boxes, then:

First, find all valid assignments of j-1 elements to n boxes (ignoring the last element, e).
For each such assignment a, consider each of the numbers i = 1 to n.
If e can be placed in the ith box of a without conflict, then yield that as an assignment of j elements to n boxes.

This method will generate all the valid assignments; it is essentially backtracking by using lists.

Here's an implementation:

code:

import Control.Monad
import Data.List

data Element
  = Cold
  | Hot
  | Black
  | White
  | Small
  | Large
  | Cat
  | Dog
  deriving (Eq, Show)

elementRules :: Element -> [Element] -> [()]
elementRules e box = do
  guard $ not $ e == Cold && Hot `elem` box
  guard $ not $ e == Hot && Cold `elem` box
  guard $ not $ e == Black && White `elem` box
  guard $ not $ e == White && Black `elem` box
  guard $ not $ e == Small && Large `elem` box
  guard $ not $ e == Large && Small `elem` box
  guard $ not $ e == Cat && Dog `elem` box
  guard $ not $ e == Dog && Cat `elem` box

assign :: [Element] -> [[Element]] -> [[[Element]]]
assign [] boxes = return boxes
assign (e:elems) boxes = do
  boxes <- assign elems boxes
  i <- msum $ map return $ [0 .. length boxes - 1]
  let box = boxes !! i
  elementRules e box
  return $ take i boxes ++ [e:box] ++ drop (i + 1) boxes

# ¿ Mar 29, 2009 23:22

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

Fruit Smoothies posted:

Forgive my ignorance, but how do I access the result of this? I've done a few tutorials just now, but they involve printing to the screen, or saving to a file.

To be perfectly honest, I hadn't bothered to test that before posting it, but it looks right. You'll call it as assign elements boxes where elements is a list of elements to assign, such as [Hot, Cold, White], and boxes is a list of empty boxes to store in to, such as [ [], [] ]. The result is a list of lists of boxes, such as [ [ [Hot, White], [Cold] ], [ [Hot], [Cold, White] ] ]. You can play with this in ghci.

But this is really terrible code to try to learn Haskell from.

# ¿ Mar 30, 2009 00:56

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

Fruit Smoothies posted:

Isn't elements from your expression assign elements boxes simply the variable Element? Or is Element the type here?

Element is a type.

And that use of boxes is correct.

# ¿ Mar 30, 2009 01:05

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

Fruit Smoothies posted:

Edit: It seems like the program wants to put more than two things in a box.

Yeah, I was only solving for a general case; you'd express size limitations in that guard function. If your problem is really just this trivial then I don't see why a program is needed.

I mean, let's say you have 12 elements in 6 pairs:

pre:

 A A'
 B B'
 C C'
 D D'
 E E'
 F F'

And you want to assign them to 6 boxes, such that no box contains both elements of a pair and every box contains two elements, then you can trivially construct a solution by hand. Just take that right column and rotate it:

pre:

 A B'
 B C'
 C D'
 D E'
 E F'
 F A'

If there's more to this problem that makes it harder, then I certainly didn't code for it. What, precisely, are you trying to do?

# ¿ Mar 30, 2009 02:23

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

Fruit Smoothies posted:

I guess what I don't get about any of these bits of code, is when the program stops, and where it starts.

We're using programming paradigms that don't have as strictly-defined concepts of execution as you're used to.

Fruit Smoothies posted:

I have realised a good example of this problem is that of the numbers 1-12. If you add a constraint that prime numbers can't be paired with each other, you very quickly end up with an interesting set of allowed pairings:
code:
1,4   4,12
1,6   5,6
1,8   5,8
1,10  5,10
1,12  5,12
2,4   6,7
2,6   6,8
2,8   6,9
2,10  6,10
2,12  6,11
3,4   6,12
3,6   7,8
3,8   7,10
3,10  7,12
3,12  8,9
4,5   8,10
4,6   8,11
4,7   8,12
4,8   9,10
4,9   9,12
4,10  10,11
4,11  10,12
      11,12
Say I start with the first allowed pair (1,4) and then move to the next allowed pair (2,6) etc; (3,8)(5,10)(7,12)... Where would the program go from here? It's reached the end of the list, and there are no more allowed pairs?

You decide that an earlier decision must have been wrong, so you back up and try something else. This is hidden in the List monad in Haskell, and in the unification algorithm in Prolog.

Fruit Smoothies posted:

Of course, this example strikes me as impossible, because the pairs are pretty much restricted to odd-even. This would work if 2 wasn't a prime number. (Correct me if I'm wrong, here)

There are six primes and six nonprimes in the range 1..12 (assuming you count 1 as prime) so the solution is quite straightforward.

(1,4),(2,6),(3,8),(5,9),(7,10),(11,12)

And, obviously, any substitution of the above where primality is preserved.

# ¿ Mar 30, 2009 17:08

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

Fruit Smoothies posted:

I counted 9 as prime

Would it be true to say that starting at every point in the list, and considering all of the other items' compatibility would solve this problem? Although it would be inefficient?

I'm not exactly sure what you mean...

An inefficient but easy-to-verify solution to the general problem is:

code:

FindPairs:
  given l, a list of unpaired elements
  choose an element a from l, and consider l' the other elements in l
  choose an element b from l', and consider l'' the other elements in l'
  if (a, b) is a valid pairing
    ps <- FindPairs l''
    return ps + (a, b)
  otherwise
    find the most recent choice for which there are alternatives we have not considered
    backtrack to that choice, and choose something else

It doesn't matter which choice you make first, because this will always find a solution if one exists. But in most cases (such as the prime number case) there are far better solutions which minimize or eliminate backtracking by picking in the "best" order according to some heuristic. For example, in the prime number case, if we always try to pick a prime number for a and a nonprime for b then we are guaranteed to find a solution without backtracking, if one exists.

# ¿ Mar 30, 2009 17:31

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

Fruit Smoothies posted:

If you want the code, here it is with some of the constraints not yet added, because it's harder to debug with them all in initially.

Now I'm really curious what your problem domain is, because that's a wacky set of constraints.

That said, visual inspection can give us a solution without too much trouble. We reformulate the constraints as allowed pairs rather than unallowed pairs:

pre:

 1:           6 7 8 9 10 11 12
 2:               8 9 10
 3:         5   7 8 9 10    12  
 4:         5     8         12  
 5:     3 4   6 7 8 9       12  
 6: 1       5     8 9 10    12  
 7: 1   3   5     8 9       12  
 8: 1 2 3 4 5 6 7 8 9 10 11 12
 9: 1 2 3 4 5 6 7 8 9 10 11 12
10: 1 2 3 4 5 6 7 8 9 10 11 12
11: 1 2 3 4 5 6 7 8 9 10 11 12
12: 1 2 3 4 5 6 7 8 9 10 11 12

Assign (1,6).

pre:

 2:               8 9 10
 3:         5   7 8 9 10    12  
 4:         5     8         12  
 5:     3 4     7 8 9       12  
 7:     3   5     8 9       12  
 8:   2 3 4 5   7 8 9 10 11 12
 9:   2 3 4 5   7 8 9 10 11 12
10:   2 3 4 5   7 8 9 10 11 12
11:   2 3 4 5   7 8 9 10 11 12
12:   2 3 4 5   7 8 9 10 11 12

Assign (2,8).

pre:

 3:         5   7   9 10    12
 4:         5               12
 5:     3 4     7   9       12
 7:     3   5       9       12
 9:     3 4 5   7   9 10 11 12
10:     3 4 5   7   9 10 11 12
11:     3 4 5   7   9 10 11 12
12:     3 4 5   7   9 10 11 12

Assign (3,5).

pre:

 4:                         12
 7:                 9       12
 9:       4     7   9 10 11 12
10:       4     7   9 10 11 12
11:       4     7   9 10 11 12
12:       4     7   9 10 11 12

Assign (4,12).

pre:

 7:                 9
 9:             7   9 10 11
10:             7   9 10 11
11:             7   9 10 11

Assign (7,9).

pre:

10:                   10 11
11:                   10 11

Assign (10,11), and we're done; no backtracking.

The only pair I'm not sure of is (10,11), because you didn't provide enough constraints.

Edit: [(1,11),(4,8),(6,12),(7,5),(3,9),(2,10)] is a solution that exists entirely within the constraints you specified.

ShoulderDaemon fucked around with this message at 18:18 on Apr 5, 2009

# ¿ Apr 5, 2009 18:10

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

Fruit Smoothies posted:

I'm really not going to go into the problem, because it really is complicated. Those are some of the constraints.

My concern is that making all these lists, and lists of lists isn't the best way to implement the backtracking.

Yeah, you're doing something crazy in there with parentOf and recursing up the search tree instead of down and I don't really understand what you want that code to do.

Backtracking would normally be done sort of like this:

code:

procedure findPairs( items ): // items has type list-of-integer
                              // return type is list-of-list-of-pair-of-integer
  if items is empty then:
    return [[]] // list with one element: an empty list
  else:

    let a = first element in items
    let l = list of elements in items after the first

    let ret = [] // empty list; we are building our return value here

    for each element b in l:

      let l' = list of elements in l, except for b

      if (a, b) is an allowed pair then:
        for each c in findPairs( l' ): // c is a list of pairs
          add (a, b) to c
          add c to ret

     return ret

Note that in a strict language, this procedure is also strict, so you won't get any results until every result is calculated. But that's fine, because this is a really trivial problem that you can fully enumerate in less than a second.

Fruit Smoothies posted:

Also, with the complexity of the full-scale problem, human attempts would be rendered useless, because you'd have to permanently look these things up.

I'm not sure I believe you, because so far everything you've posted has been really trivially easy to solve by hand, and I'm having trouble accepting that it's any easier to express your wacky constraints in code, debug the code, etc.

# ¿ Apr 6, 2009 21:33

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

Fruit Smoothies posted:

I don't know why you'd think I'd lie about this. It's not difficult to do by hand, but it's lengthy.

With the constraints you've been posting, it's been taking me less than a minute to find solutions each time. There's only twelve elements. Seriously, computers are overkill sometimes, if you can't solve these problems yourself faster than you can write a program, something is very wrong.

Fruit Smoothies posted:

Additionally, the constraints change on a (fairly) regular bases, sometimes resulting in pairs within pairs and all sorts of complications that can be considered (if at all) after the backtracking is sorted.

So, what you're saying is, you'd have to spend even more time writing an even more complicated program, and you'd have to change the program frequently to account for new rules, which may be difficult to express in your algorithm. These do not sound like good reasons for using a program.

Fruit Smoothies posted:

I know what your code does there, and I have considered doing it myself, but a lot of this is about a learning curve, so I'd like to have a backtracker, rather than a list of permutations.

First of all, I didn't do anything involving permutations in that pseudocode.

Secondly, backtracking is, exactly and precisely, the act of building a list of results at one level, then transforming that into a list of results from the next-highest level. To transform "idealized" backtracking code into a single-result form, you simply change the algorithm to only return the first element (if there is one) of the result list, and optimize away any calculations that would thus be redundant. In this case, such a transformation is trivial, because we have the nice property that if the recursive call returns any results, then they are all equally valid - in particular, the first one is valid, so we can eliminate list management altogether.

This trivially changes the pseudocode into the reduced form:

code:

data type MaybeList is one of:
  Failure
  Success list // list has type list-of-pair-of-integer

procedure findPairs( items ): // items has type list-of-integer
                              // return type is MaybeList
  if items is empty then:
    return Success []
  else:

    let a = first element in items
    let l = list of elements in items after the first

    for each element b in l:

      let l' = list of elements in l, except for b

      if (a, b) is an allowed pair then:

        let child = findPairs( l' )

        if child is Success childList then:
          add (a, b) to childList
          return Success childList

     return Failure

The only interesting property of lists that we are obligated to preserve in this case is that they may be empty, representing a failed search, because there is no concept in this problem of some results being "better" than others.

This is, honestly, the kind of problem I'd expect to see in an intro data structures class. It's about 100 lines of C with no need for dynamic allocation, is easy to verify by hand, and is operating on an incredibly tiny problem with questionable utility.

# ¿ Apr 7, 2009 01:50

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

ShoulderDaemon posted:

This is, honestly, the kind of problem I'd expect to see in an intro data structures class. It's about 100 lines of C with no need for dynamic allocation, is easy to verify by hand, and is operating on an incredibly tiny problem with questionable utility.

So, I said this, and then I started thinking to myself that I should be prepared to be called-out on a statement like this. My first try was 99 lines, but I like round numbers, so here's a 50 line version:

code:

#include <stdio.h>
#include <string.h>

#define MAX 12
#define BITS 4

static short allowed_bits[MAX] = { 0xfe0, 0x380, 0xbd0, 0x890, 0x9ec, 0xb91, 0x995 };

#define ALLOWED(f,i) (allowed_bits[(-1)[f]-1]&(1<<((i)[f]-1)))
#define PAIR(f,i) (((i)[f]<<BITS)|(-1)[f])

struct maybe_list {
  int elems;
  int pairs[MAX/2];
};

void find_pairs( struct maybe_list *ret, const int *from, int sz ) {

  if (! (sz-- || (*(int *)ret = 0))) return;

  int lprime[sz - 1];
  memcpy( lprime, ++from + 1, sizeof( lprime ) );

  for ( int i = 0; i < sz; lprime[i] = from[i], ++i )
    if ( ALLOWED(from,i) ) {
      int p = PAIR(from,i);

      find_pairs( ret, lprime, sz - 1 );
      if ( ret->elems >= 0 && (ret->pairs[ret->elems++] = p) )
        break;
    };

}

int main( int argc, char *argv[] ) {

  int starting_from[MAX+1];

  for ( int i = -1; i < MAX; ++i )
    starting_from[i + 1] = i + 1;
  --starting_from[0];

  struct maybe_list *result = (void *)&starting_from;

  find_pairs( result, starting_from + 1, MAX );
  while ( result->elems-- > 0 )
    fprintf( stdout, "(%d,%d) ", *result->pairs & ((1<<BITS)-1), *result->pairs >> BITS ), *result->pairs = result->elems[result->pairs];
  fprintf( stdout, "\n" );

}

I was worried about memory use, so it doesn't touch the heap and reuses a few memory locations. And yeah, I realize only 34 lines are code, the vertical space is to make it readable! It compiles without warnings in gcc's c99 mode; I didn't bother to test with anything else.

# ¿ Apr 7, 2009 05:35

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

floWenoL posted:

Man, look at those strict aliasing violations.

I wanted to make it even less defined, but any other changes I was making to it confused gcc enough to make it stop working on my laptop. If you drop the number of elements to 10 from 12, I have a version that works and uses code space to store the result list instead of reusing the initial elements list; I guess I could use an asm call to pad out this one and put that trick back in... actually, now that I think about it, there should be enough room in find_pairs instead of main where I was sticking them, so I could claim it was "broken memoization" or something...

# ¿ Apr 7, 2009 06:15

Adbot: ADBOT LOVES YOU

# ¿ May 15, 2024 13:07

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

frumpus posted:

In VBScript, I have a url-encoded string which I have parsed together.

In order to pass it to a 3rd party website I need to create a secure hash using the HMAC-SHA256 algorithm, and a secret code word that they gave me.

I have no idea how to do this and my googling hasn't been very helpful. All I can find are downloads that I don't trust. Surely there is a way to do this with some vbscript code, it sounds like a fairly common task.

Help?

Please do not implement cryptographic primitives on your own, you will do it wrong. If you find a third-party which you do not trust, post a link in here and I can do some tests on the implementation for you and tell you if it's at least outwardly correct.

# ¿ Apr 8, 2009 20:08

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

«‹›6 »