Daily Programming Challenge:

[pidsley]

Code: Select all

palindrome :: String -> Bool
palindrome str = str == reverse str 

main = do
    (arg1:args) <- getArgs
    if (palindrome arg1) then
        putStrLn (arg1 ++ " is a palindrome")
    else
        putStrLn (arg1 ++ " is not a palindrome")

I had to look up the command-line arg stuff, and I'm still not entirely clear on how it works. I also admit to finding the reverse function in a web search. And this code does not work for strings that are palindromes except for spaces (like "no x in nixon").

[GekkoP]

The quick and dirty solution for now:

Code: Select all

(defn palindrome? [s]
  (= s
     (apply str (reverse s))))

[machinebacon]

Rules:
1). Don't cheat. Kill/Yanking someone else's code is for pussies. I won't double-check you, but you're a bitch if you cheat.

I did double-check. And found this -> http://linuxbhaveshp3.blogspot.jp/2013/ ... drome.html

And if you want to compare how much off your solution is -> http://rosettacode.org/wiki/Palindrome_detection

[GekkoP]

Well, I feel bad now. I swear I quickly wrote it in a buffer while chatting with Joe on ERC.
Here's with single blank space check.

Code: Select all

(defn remove-blanks [s]
  (apply str
         (remove #(= " " %)
                 (map str (vec s)))))

(defn palindrome? [s]
  (let [s (remove-blanks s)]
    (= s
       (apply str (reverse s)))))

[DebianJoe]

...can I claim that mine is BETTER than the posted ones?

Code: Select all

;; NOT MY CODE, I STEALS THIS FROM MB'S LINK;;
(define (palindrome? s)
  (let ((chars (string->list s)))
    (equal? chars (reverse chars))))

....mine's better than this. It has colors, and is way better at warming up the CPU on cold winter days. :D

Edit: also, how about MY bash code. (totally original)
================
ln -s /path/to/mb/bash /path/to/original/DJ/work
================

....2nd Edit: Ok, so I actually EXPECT some research to go into these. I do it, and take good ideas from wherever I can find them. Pidsley is learning Haskell as we go, so obviously his answers are going to have to reflect some examples. Learning from those who have come before us is what keeps us from reinventing the wheel every generation. That being said, you're not learning if you just copy-paste someone else's code.

Also, I totally stole my python 2 fizzbuzz example...from the piece-of-shit's old work on the subject of shortening Python2 Fizzbuzz.

[machinebacon]

I was quite surprised to see how neat Pidsley's version is, with String conversion etc.!

And GekkoP, of course I know you didn't steal it :) You're much too man :D

[GekkoP]

^ well, too late mate! You scared the hell out of me with that link and I feel like someone's spying on me! ;)

[machinebacon]

^ Your inbuilt webcam works well. :)

[machinebacon]

Webcam was pointed at Gekko.

But zazen, maybe this helps as some reference material:
http://rextester.com/GLRY11890
http://jlordiales.wordpress.com/2014/02 ... roduction/
http://lateblt.tripod.com/basic.htm
http://www.cplusplus.com/forum/lounge/69069/#msg369243
http://www.cplusplus.com/forum/lounge/69069/#msg368917

I'd like to quote a good friend of mine:

WHY THE FUCK WOULD YOU LIE ABOUT SOMETHING THAT DOESN'T EVEN MATTER?

[DebianJoe]

... .... ..... shameful display.



Anyhow, back to the fun!

Pidsley and I talked today (probably far too much) about size v sloc v efficiency v time invested v all sorts of choices for doing things in one way or the other. We now already have multiple offerings regarding different ways to do things in different languages.


The Challenge

Normal Mode: No need to come up with some new program, but rather...determine a few points of interest about an existing piece of code you have done at least 2 ways. The "Focus Group" one is fine. Now, instead of figuring it low, have it do a few thousand cycles to derive an answer. Using some key metrics, compare the two and share your findings about the differences.

Professor Mode: Why are they different? Explain in as much detail as you can.

[DebianJoe]

Ha ha ha. Okay, hang with me for a bit guys...this one gets a tad bit funny.
I'll start by showing you EXACTLY what I'm doing:

So, Fib1 is our 'recursive' model, which is a picture perfect "Tree Recursion model" in Scheme. (Those who've read through SICP are probably already laughing about a 100,000 step recursion tree...but let's see how it works.)

So, the size of the compiled binaries in Chicken are pretty similar. The total amount of code in each is pretty similar too...but:

Code: Select all

╰─$ time ./fib1
^C
[2]    2143 interrupt  ./fib1
./fib1  63.66s user 0.22s system 99% cpu 1:03.97 total

╰─$ time ./fib2
./fib2  0.02s user 0.00s system 93% cpu 0.027 total

╰─$ time ./fib3
./fib3  0.03s user 0.00s system 95% cpu 0.037 total

After starting to wonder if fib1 (the tree recursive method) would EVER complete, I interrupted it. HOLY SHIT that one is a freaking resource hog. The other two are close, because they both function in linear time, and are similar. It's worth noting at this point that Chicken's CSC compiler is tail-call optimized, but that doesn't really make that much difference when the expansion of the function isn't tail-recursive.

"What the ever-loving hell?" Someone might ask. Well...it has to do with how the expansion takes place. I think that substitution makes good sense here. Essentially Fib3 has a short "dangling" tail that deals with the mutables, but is a linear method. Fib2 is a very tight linear method, and Fib1 is practically designed to eat memory. As a short example, let's look at how Fib1 would expand (fib 5)

Code: Select all

fib5 - fib 3 - fib 1 - 1
      |    | - fib 2 - fib 1 - 1
      |         | ---- fib 0 - 0
      |
      fib 4 - fib 2 -fib 1 - 1
            |   |----fib 0 - 0
            |
           fib 3 - fib 1 - 1
                 |-fib 2 -fib 1 - 1
                          |- fib 0 - 0

Heh, so for every step higher that 'n' is valued, our amount of processes is growing almost exponentially. Compare that to our mutable Fib3 program:

Code: Select all

fib n<--index 1---------index 2---------------index 3--->
       |- a is b is 1      | - a is b is 1        | - a is b is 2
       |- b is c is 1      | - b is c is 2        | - b is c is 3
       |- c (+ a b) is 2   | - c (+ a b) is 3     | - c (+ a b) is 5    ...etc

(This reasoning is covered in WAY better detail in SICP, btw. Which is where I learned about most of the theory anyhow. The tree recursion example is the one used as a "Don't do this" example there. lol)

So, Fib2 & Fib3 run in a constant linear progression, while Fib1 is designed to grow until it hits a point where it can actually compress its expansion back into pure mathematical reasoning.

[pidsley]

Fibonacci, Haskell recursive method, to term 35:

Code: Select all

gadget:/media/shared/code/haskell $ time ./fib                                             
102334155
                                                                                          
real    1m56.792s                                                                          
user    1m55.340s                                                                          
sys     0m0.608s 

and check out the executable size:

Code: Select all

gadget:/media/shared/code/haskell $ ls -l fib                                        
-rwxr-xr-x 1 pidsley pidsley 838592 Dec  7 12:46 fib*

Fortran, iteration to term 35:

Code: Select all

gadget:/media/shared/code/fortran $ time ./fib
   102334155

real    0m0.006s
user    0m0.000s
sys     0m0.000s

And the executable:

Code: Select all

gadget:/media/shared/code/fortran $ ls -l fib
-rwxr-xr-x 1 pidsley pidsley 6217 Dec  7 12:46 fib*

;) I expect that the reason for the time difference is as Joe described above. I have no good explanation for the executable size, but there appear to be many posts on the web about this, so there may be some compiler switches I don't know about.

Conclusion: don't use recursion to calculate the fibonacci sequence!

[DebianJoe]

The executable for Haskell is rather huge. I'm sure that if there's a simple way to improve on it, you'll run across the answer. ;)

Conclusion: don't use recursion to calculate the fibonacci sequence!

This is pretty well solid theory! The 'thing' ('central concept', whatever you want to call it) I really am bringing away from this is it's far easier to spot the difference between iteration and recursion than between different types of recursion when writing functions or processes. I would assume that we could probably make some generalizations about when it's appropriate to use recursion and when it's best to play it safe and iterate instead. Recursion offers some really useful answers to complex problem, but even with tail-call recursion optimization, an iterating loop still looks to be a faster running solution.

Maybe the rule should be:
1. When in doubt, iterate.

[DebianJoe]

This week's 'Zen Reflection'



I may start doing this as well on a regular basis. I'm not asking by any stretch of the word for you to sit down and share some deep philosophy, but rather that to point out something/anything that you've learned about YOUR language of choice. Every language has some quirks and tricks that we only run into after some time spent dealing with them. So, share something, anything, that you have discovered about your language, and show a short example of how it works.

To start I'll share mine: In Scheme, even basic symbols are within my ability to control.

Code: Select all

(define (Ilikeminus a b)
  (let ((- +))
    (- (- a a) (- b b))))

> (Ilikeminus 2 3)
10

I break up the addition into subsections, even though I could have written it (- a a b b) to show that my mutation (while localized) will hold true until the end of the process.

[franksinistra]

Palindrome in Clojure

Code: Select all

(defn pre-palindrome [w]
  ;; remove whitespaces and special characters, then lower-case the word
  (clojure.string/lower-case (apply str (re-seq #"\w+" w))))

(defn palindrome [w]
  ;; match w against its reverse seq
  (let [a (#(pre-palindrome %) w)
        b (#(apply str (reduce conj () (pre-palindrome %))) w)]
    (cond
      (= a b) (println "Palindrome detected")
      :else (println "Not a palindrome"))))

scrot or didn't happen

[GekkoP]

^ cool. I didn't use clojure.string cause Joe said not to use too many libraries, so I preferred going very basic.

One thing I learnt studying Clojure is that JVM is not optimized for TCO (tail-call optimization). JVM is not intended for functional programming, I suppose. It became clear with Fibonacci series. Tail-call recursion for high numbers blows the stack. Clojure solves this with lazy sequences, but I until I approached recursion through SICP I didn't know this particular detail about the JVM.

[franksinistra]

^right i should've noticed what Joe said before. Thanks for the reminder Gekko!

[pidsley]

Well, I haven't spent much time learning Haskell, so I can't speak as eloquently as you guys about arcane quirks, but one thing I already really like in Haskell is this construct:

Code: Select all

winner p1name p2name
   | p1 == 0 = (p1name ++ " is not valid")
   | p2 == 0 = (p2name ++ " is not valid")
   | a == 0 = "tie"
   | a < 3 = (p1name ++ " wins")
   | a < 5 = (p2name ++ " wins")
   where
      a = (p1 - p2) `mod` 5
      p1 = (getnum p1name)
      p2 = (getnum p2name)

Those | statements at the top are called "guards" and they are basically a set of "if then - else if" clauses, and the "where" expressions set local variables that can then be used in the guard statements. I like how clean and simple it is. There are much more complex versions of this using patterns, but I don't understand how that works yet.

[DebianJoe]

^ Cool! Now it makes more sense to read. I was looking at it like you might look at PLC ladder logic (reads down from the first section, if the whole 'rung' is true, then set condition at the end...not too far off.)


Today (and probably tomorrow's challenge, as I have some other stuff I want to work on and it may take me a bit to finish this one.)

Normal Mode: Conan the Barbarian is a data-structure of your choice. First, represent him as a set of stats (ala: rogue/nethack) that tell you something about his current abilities. Be able to recall those stats.

Buff Mode: Conan has found the 'Flask of Badassity' which adds a permanent +1 of some stat. Be able to call a function that represents the flask, and make a permanent change to one of his stats.

[DebianJoe]

Code: Select all

;; Define Conan as an associated list
(define conan '((str 10) (dex 5) (HP 20)))

;; Make quick recalls
(define (str?) (assq 'str conan))
(define (dex?) (assq 'dex conan))
(define (HP?)  (assq 'HP conan))

;; Define the Flask as a procedure, assume known values.
(define (flask_of_badassity)
 (set! (cdr (str?)) '(11)))

I probably should have unpacked the list and read its value, but I'm playing with something else and am being lazy. :D