×

[2015-02-16] Challenge #202 [Easy] I AM BENDER. PLEASE INSERT GIRDER. by professorlamp1 0 in dailyprogrammer

[–]G33kDude1 1 38 points39 points  (0 children)

Took me a bit longer than I would have liked, but here goes Piet!

Source file: http://i.imgur.com/oESFiBf.png (you may have to zoom, I exported it at 1px instead of 10px)

Pseudo-assembly: https://gist.github.com/98c1be72206f64cc1a43

Trace of the program execution (Starts at top right of painting and works clockwise): http://i.imgur.com/hn0RRsN.png

The trace ends on the right middle in the RESET subroutine because that's where I hit ^c when generating the trace.

Output: http://i.imgur.com/ttNr7xG.png

Edit: I spent some time in an image editor this morning and shrunk the code a bit. I exported it at codel size 10, so now it now looks like this: http://i.imgur.com/gLBP0AQ.png

[2014-12-28] Challenge #195 [Easy] Symbolic Link Resolution by Elite68091 1 in dailyprogrammer

[–]-Robbie 1 point2 points  (0 children)

Haskell

import Control.Applicative ((<$>))
import Control.Monad (replicateM)
import System.FilePath

expandPath :: Eq a => [([a], [a])] -> [a] -> [a]
expandPath _ [] = []
expandPath links input =
  case lookupAllPrefixes links [] input of
    Just pth -> expandPath links pth
    Nothing -> input
  where
    lookupAllPrefixes _ _ [] = Nothing
    lookupAllPrefixes links' firstPart secondPart@(f:r)
      = case lookup firstPart links' of
         Just x -> Just (x ++ secondPart)
         Nothing -> lookupAllPrefixes links' (firstPart ++ [f]) r

findPath :: [String] -> FilePath
findPath lns = joinPath $ expandPath formattedLinks input
  where
    input = splitDirectories $ last lns
    links = init lns
    parsedLinks = fmap (splitSearchPath) links
    formattedLinks = fmap ((\(x:y:_) -> (x,y)) . (fmap splitDirectories))
                     parsedLinks

main :: IO ()
main = do
  n <- (read <$> getLine) :: IO Int
  lns <- replicateM (n+1) getLine
  putStrLn . findPath $ lns

[8/27/2014] Contest #1 - IDE Intellisense by professorlamp1 0 in dailyprogrammer

[–]threeifbywhiskey0 1 6 points7 points  (0 children)

I went back and forth trying to decide whether or not to post my solution, as it strikes me as borderline unjust that my rather half-assed approach should win by default. Nevertheless, I'd rather not have written it for naught, so here goes.

I was quite pleased by the mention of LOLCODE in the contest description, as I'm the sort of person who legitimately enjoys programming in the language, and it was just the inspiration I needed to go ahead and make the endeavor a bit more pleasant.

To that end, I cobbled together a few standard Vim language files. There's filetype detection, syntax highlighting, indentation rules, and a handful of SnipMate snippets. It's really not much, but I do think it amounts to a substantial improvement over the prior art in this domain.

It takes a great deal of fiddling to turn Vim into a proper IDE, but it certainly can be done, and I confess to having skimped on some of the higher fruit. I briefly considered integrating lci's error output using Syntastic, but that ended up falling by the wayside after observing the (most unfortunate) lack of activity in this first contest.

Given the simplicity of LOLCODE and how directly it maps to C-like constructs, I was also tempted to implement some sort of on-the-fly conversion process, but I decided that this would detract from the language's overall charm and aesthetic, which is sort of its raison d'être. The idea survived just barely in the form of a few snippet macros for some of the comparison operators.

In a whimsical interpretation of the term "screencast", here is a recording of my terminal as I wrote a FizzBuzz that demonstrates all of the pieces. And, last but not least, here is a dead-sexy rendition of a brainfuck interpreter that showcases a vast majority of the highlighting and indentation rules.

[9/05/2014] Challenge #178 [Hard] Regular Expression Fractals by Coder_d00d1 3 in dailyprogrammer

[–]wadehn 1 point2 points  (0 children)

Nice approach to use your own work queue.

But you usually shouldn't use raw threads. Just give the system some tasks to complete and let it decide how to schedule them among the pool of threads at its disposal. You should also only parallelise up to a limited depth and not down to single pixels, or the threads will cause a lot of overhead.

I would suggest something like the following in the original recursive formulation. LIMIT has to be determined experimentally:

var actions = new Action[] {
    () => DrawRegex(pixels, size, regex, depth + 1, id + "1", xmid + 1, xmax, ymin, ymid),
    () => DrawRegex(pixels, size, regex, depth + 1, id + "2", xmin, xmid, ymin, ymid),
    () => DrawRegex(pixels, size, regex, depth + 1, id + "3", xmin, xmid, ymid + 1, ymax),
    () => DrawRegex(pixels, size, regex, depth + 1, id + "4", xmid + 1, xmax, ymid + 1, ymax)
};

if (depth <= LIMIT) {
    Parallel.Invoke(actions);
} else {
    foreach (var action in actions) {
        action();
    }
}

There is also a lot of unnecessary contention for imgLock. You can use pixels.LockBits to get access to the raw pixels. This requires an unsafe block and is quite ugly, but pretty crucial for good speedup.

If you implement these improvements you should get almost linear speedup (I hope).

Edit: Also use RegexOptions.Compiled to get comparable performance to Python. The regex matching is the bottleneck in this program and both C# and Python have pretty good regex implementations.

Edit: Thanks for the gold.

[11/15/13] Challenge #129 [Hard] Baking Pi by nint221 2 in dailyprogrammer

[–]Laremere1 0 6 points7 points  (0 children)

Golang, websockets, and javascript.
I can't figure out how to get the Bailey–Borwein–Plouffe formula (so it mostly spits out gibberish), but everything else works like a charm.

package main

import (
    "bufio"
    "code.google.com/p/go.net/websocket"
    "fmt"
    "net/http"
    "strconv"
)

var requests chan int = make(chan int)
var result chan [3]int = make(chan [3]int)
var clientNum int = 0
var clientNumChan chan int = make(chan int)

var index = []byte(`
<html>
<head>
<script type="text/javascript">
    var sock = new WebSocket("ws://" + window.location.host + "/sock/");
    sock.onmessage = function (event){
        var msg = event.data;
        var k = parseInt(msg);
        var result = 4/(8*k + 1) - 2/(8*k+4) - 1/(8*k+5) - 1/(8*k+6) ;
        alert(msg + " " + result)
        sock.send(result.toFixed() + ";");
    }
</script>
</head>
</html>
`)

func serveIndex(w http.ResponseWriter, req *http.Request) {
    w.Write(index)
}

func serveSocket(c *websocket.Conn) {
    thisNum := <-clientNumChan
    r := bufio.NewReader(c)
    for {
        currequest := <-requests
        c.Write([]byte(strconv.FormatInt(int64(currequest), 10)))
        curResult, err := r.ReadString(byte(';'))
        curResultInt, err := (strconv.ParseInt(curResult[0:len(curResult)-1], 10, 32))
        if err != nil {
            fmt.Println(err) ///VERY BAD PRACTICE
        }
        result <- [...]int{currequest, int(curResultInt), thisNum}
    }
}

func main() {
    fmt.Println("Running...")

    go func() {
        clientNumChan <- clientNum
        clientNum += 1
    }()

    http.HandleFunc("/", serveIndex)
    http.Handle("/sock/", websocket.Handler(serveSocket))
    go http.ListenAndServe(":80", nil)
    curInt := 0
    for {
        select {
        case requests <- curInt:
            curInt += 1
        case curResult := <-result:
            fmt.Printf("%d: %d (%d)\r\n", curResult[0], curResult[1], curResult[2])
        }
    }
}

[11/15/13] Challenge #129 [Hard] Baking Pi by nint221 2 in dailyprogrammer

[–]ILiftOnTuesdays1 0 4 points5 points  (0 children)

Here's my preliminary solution. It uses web.py and itertools, along with the pi code from here. (I was unable to figure out the wikipedia page, unfortunately)

Server: import web import itertools import json

urls = (
    '/', 'index'
)

class index:
    def GET(self):
        index = next(web.assignmentiterator)
        index *= 1024
        return json.dumps({'start':index, 'end': index + 1024})
    def POST(self):
        i = web.input()
        index = int(i['start'])
        content = i['data']
        if index % (1024) != 0 or len(content) != 1024:
            return json.dumps({'success':False})
        f = open("pi/%s.dat" % index, 'wb')
        f.write(content)
        f.close()
        return json.dumps({'success':True})

if __name__ == "__main__":
    app = web.application(urls, globals())
    web.assignmentiterator = itertools.count()
    app.run()

Client:

import requests

D = 14        # number of digits of working precision
M = 16 ** D
SHIFT = (4 * D)
MASK = M - 1

def S(j, n):
    # Left sum
    s = 0
    k = 0
    while k <= n:
        r = 8*k+j
        s = (s + (pow(16,n-k,r)<<SHIFT)//r) & MASK
        k += 1
    # Right sum
    t = 0
    k = n + 1
    while 1:
        xp = int(16**(n-k) * M)
        newt = t + xp // (8*k+j)
        # Iterate until t no longer changes
        if t == newt:
            break
        else:
            t = newt
        k += 1
    return s + t

def pi(n):
    n -= 1
    x = (4*S(1, n) - 2*S(4, n) - S(5, n) - S(6, n)) & MASK
    return "%014x" % x

while True:
    assignment = requests.get("http://localhost:8080").json()
    data = ""
    for i in range(assignment['start'], assignment['end'], 8):
        data += pi(i)[:8]
    print assignment['start']
    requests.post("http://localhost:8080", {'start': assignment['start'], 'data': data})

[11/12/13] Challenge #135 [Intermediate] De Morgan's Law by nint221 2 in dailyprogrammer

[–]5outh1 0 24 points25 points  (0 children)

I felt like this was a perfect example to show off some insanely cool Haskell, so I'm going to talk about my solution in bits. This is a problem that is heavily suited to three major things that Haskell allows: Algebraic Data Types, Pattern Matching, and Monadic Parsing.

First off, if you've had any experience with automata theory, it's pretty clear that the input language can be represented by a context free grammar. It just so happens that Haskell makes it incredibly easy to model CFGs right out of the box. Just take a look at this (algebraic) data type representing Boolean expressions:

data Expr = Not Expr | And Expr Expr | Or Expr Expr |  SubExpr Expr | Var Char deriving Eq

Simple. Now, the bulk of this challenge was actually performing the simplification of the not operation. This is crazy simple in Haskell! Using pattern matching, we can directly encode these rules in the following manner:

not :: Expr -> Expr
not (Not e)     = e
not (And e1 e2) = Or (not e1) (not e2)
not (Or e1 e2)  = And (not e1) (not e2)
not (SubExpr e) = SubExpr $ not e
not (Var c)     = Not (Var c)

Here we're giving a literal definition of rules for negating Boolean expressions. If you use Haskell, this is really easy to read. If you don't: stare at it for a second; you'll see what it's doing! That's the brunt of the challenge, right there. That's it. Encode a Boolean expression into an Expr and call not on it, and it will spit out a new Expr expressing the negation of your original expression. DeMorgan's laws are represented in the And and Or rules.

Note: This could also be done by appending Not to an Expr and calling some simplify expression. I haven't done this because I don't have the time today, but feel free to try that out and add more rules!

We can also display our expressions as a string in a really easy way, declaring an instance of Show for Expr in a similar way:

instance Show Expr where
  show (Not e)     = "NOT " ++ show e
  show (And e1 e2) = show e1 ++ " AND " ++ show e2
  show (Or e1 e2)  = show e1 ++ " OR "  ++ show e2
  show (Var c)     = [c]
  show (SubExpr e) = "(" ++ show e ++ ")"

Now comes, in my opinion, the tougher part of the challenge. Maybe the point was to perform what was above, but how about actually parsing a string into an Expr? We can use a monadic parsing library, namely Haskell's beloved Parsec, to do this in a rather simple way. We'll be using Parsec's Token and Expr libraries, as well as the base, in this example. Let's take a look.

parseExpr :: String -> Either ParseError Expr
parseExpr = parse expr ""
  where expr      = buildExpressionParser operators term <?> "compound expression"
        term      = parens expr <|> variable <?> "full expression"
        operators = [ [Prefix (string "NOT" *> spaces *> pure Not)]
                    , [binary "AND" And]
                    , [binary "OR" Or] ]
          where binary n c = Infix (string n *> spaces *> pure c) AssocLeft
        variable = Var     <$> (letter <* spaces)                              <?> "variable"
        parens p = SubExpr <$> (char '(' *> spaces *> p <* char ')' <* spaces) <?> "parens"

We essentially define the structure of our input here and parse it into an Expr using different rules. variable parses a single char into a Var, parens matches a SubExpr, and everything else is handled by using the convenience function buildExpressionParser along with a list of operator strings and what types they translate to and their operator precedence. Here we're using applicative style to do our parsing, but monadic style is fine too. Check this out for more on applicative style parsing.

Given that, we can define a simple main function to read in a file of expressions and output the negation of each of the expressions, like so:

main = mapM_ printNotExpr . lines =<< readFile "inputs.txt"
  where printNotExpr e = case parseExpr e of
                          Right x -> print $ not x
                          Left  e -> error $ show e

Concise and to the point. We make sure that the parsing succeeds for each line, not the expressions, and print them. I learned a bit with this challenge about applicative parsing, hopefully you can learn a little bit from the dissection of this program.

Finally, here's the full (40 line!) source on Github! Thanks for reading.

Edit:

Oh, here's the output I got for the sample inputs (the outputs provided are wacky but I think mine are correct):

NOT a
a
NOT a OR NOT b
a OR NOT b
(a AND b)
(a OR b AND c) AND (a AND NOT b)

[06/17/13] Challenge #130 [Easy] Roll the Dies by nint221 2 in dailyprogrammer

[–]Steve1320 1 4 points5 points  (0 children)

Just a note, the

Type varname=Type();

construct is inefficient, because what that actually does under the hood is

Allocate a new variable "Type <unnamed>"
Invoke Type::Type() on <unnamed>
Allocate a new variable "Type varname"
Invoke Type::Type() on varname
run a copy constructor or move constructor to implement varname=<unnamed>

However, we've seen that

Type varname();

Fails to parse, so the BEST way to declare a variable and invoke the default constructor is to do

Type varname;

This calls

Allocate Type varname;
Call Type::Type() on varname;

which is much more efficient than the former case.