Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Boggling Return to C

thraxil.org

Post reply on HN
Print view View original

71–80 of 88 posts

Re: A Boggling Return to C

#71

Post by Jare »

tosseraccount wrote: post #62
VMG wrote: post #58

Earlier quoted context omitted.

Not being a experienced C programmer by any measure, but this doesn't look right to me: https://github.com/thraxil/boggle/blob/master/boggle.c#L92 struct foo f() { struct foo f; return f; } isn't returning a stack-allocated struct a bad idea?

It returns a copy of it. Example: #include struct foo { char space[1024]; }; struct foo f() { struct foo f; printf("address of f is %p\n",&f); return f; } int main() { struct foo g; g = f(); printf("address of g is %p\n",&g); return 0; } produces this output: address of f is 0x7fbfffec30 address of g is 0x7fbffff050

If I remember correctly (been a long time), most compilers would implement many cases of struct return by letting the caller pass the address of a block of (stack) memory to contain the return value. The function can then optimize things to get rid of its local copy, operate directly on the intended target, and the caller doesn't need to perform any copies.

Re: A Boggling Return to C

#72

Post by thraxil »

galactus wrote: post #12

The author implements an inneficient algorithm using python and then a better one using C. He seems to feel python is for dirty brute force and C is for "real" programming...

Yes and no.

I wrote the Python version in probably under an hour. My girlfriend had gotten into playing some stupid Facebook version of Boggle and I just wanted to see her face when I came out of nowhere with implausibly high scores. I didn't think hard about the problem, just reached for the tool I know best and implemented the first obvious approach that came to mind. It worked as needed and I moved on. You make it sound like I think that's a bad thing.

Later, when I had a bit of time to think about it, it occurred to me that a trie would be a better approach, so when I was feeling like getting back into C and wanted a toy problem, re-implementing the boggle solver in C with a trie seemed like a good choice.

The experience of programming in the different languages does feel different though and I think it can affect how one approaches solving problems. Python is so good at just letting me solve the immediate problem that sometimes I rush and don't think things through or settle for a less than optimal solution. This will come back and bite me if that suboptimal code ends up getting built on and re-used elsewhere.

When I write C (or Go, Erlang, Haskell, etc. basically any language that requires me to think a little more up-front about how I'll implement it), I know going in that I'm going to be putting some serious time and effort into the code, so I tend to be more careful about things at every stage. The game changes from "get a result as quickly and painlessly as possible" to "write something that is elegant in itself". That's not always a win. Sometimes you are much better off building the prototype quickly, seeing flaws that you never would've thought of and then being able to approach the problem in a whole new way. Sometimes you just need a result quickly and time spent making things elegant or efficient actually is wasted (I'm not going to build a framework out of the boggle solving code anytime soon, eg).

I code in Python pretty much every day. I have for years. I probably will for years to come. It works for me. I'm just saying that sometimes other languages push you in different directions and I can see why, despite taking more lines of code to write, taking longer to write, having more potential for segfaults, and so on, languages like C still find a niche for writing systems and platforms. And that reason isn't just that it runs a little faster.

Re: A Boggling Return to C

#73

Post by abecedarius »

My Python answer http://stackoverflow.com/questions/746082/how-to-find-list-o... runs in 200ms on my laptop. It probably isn't actually within a factor of 2 of this C code, since I don't know what input board it was tested with to get 100ms, and it matters how much of the dictionary gets pruned while loading. I just stuck in a random 5x5 board and got 412ms real time, still pretty tolerable.

Edit: The next Python answer there uses a trie and takes 16.7 seconds on the 4x4 board. I like tries because they're elegant, but I hardly ever use them because the built-in collections are well-engineered even for problems you'd think are made for a trie.

Re: A Boggling Return to C

#75

Post by eli_gottlieb »

luriel wrote: post #24
babarock wrote: post #6

I absolutely love writing C. Up until late 2011, it was by far the language I used the most. I am now learning Lisp (not exactly, I'm using Lisp in SICP), and use Python more than before. One thing I realized, is that reading C is more tedious than code in other languages. Sure that's a gross generalization and is not true for every piece of code out there. However, I find I have less troubles picking up a Python pro…

> The code relies heavily on preprocessor macros and some weird gcc-only syntax that made my head hurt. The preprocessor is generally recognized as one of C's biggest flaws, is not for nothing that Ken Thompson, the first C programmer and the greatest influence on the language other than DMR himself, cut down most of the preprocessor when he wrote his own set of C compilers for Plan 9: http://doc.cat-v.org/plan_9/4th…

It keeps all the simplicity of C, without actually being able to write a kernel or device driver!

Re: A Boggling Return to C

#76

Post by philwelch »

daniel-cussen wrote: post #67
xarien wrote: post #26

Earlier quoted context omitted.

My intro course in college was run this way as well and to this day, I'm very glad to have started my career bottom up instead of top down...

I did top down starting at Lisp. I'm not unhappy with this choice, know assembly by now, and by the way, totally love C.

Bottom-up and top-down are both better than the worst learning method, which is to start somewhere in the middle and just stay there.

Re: A Boggling Return to C

#77

Post by davidjohnstone »

robryan wrote: post #18
fferen wrote: post #17

It's funny, because I recently tackled this exact same problem in Python as well. And guess what my first step was? Writing a prefix tree implementation, in order to use the exact same approach the author took in C. It never seriously occurred to me to do it any other way. It may be because I recently got into C as well after spending years with only Python, but honestly I think I would have done the same thing befor…

Providing you are aware of prefix trees. I guess you could come up with the idea independently but I would assume a lot of people when presented with the problem wouldn't.

At the end of my first year of my software engineering degree I wrote a Boggle solving program in C# using a trie. About a year later I discovered that tries are a recognised data structure and that I wasn't the first person to use one.

Re: A Boggling Return to C

#78

Post by revscat »

X-Istence wrote: post #34
babarock wrote: post #6

I absolutely love writing C. Up until late 2011, it was by far the language I used the most. I am now learning Lisp (not exactly, I'm using Lisp in SICP), and use Python more than before. One thing I realized, is that reading C is more tedious than code in other languages. Sure that's a gross generalization and is not true for every piece of code out there. However, I find I have less troubles picking up a Python pro…

The one thing that I have trouble with in Python projects is that it can be very difficult to figure out where the actual object is from that is being imported. from somedir.somefile import objectX Then when you go to somedir.somefile you find out objectX is nowhere to be found only to figure out later that it is dynamically created and added to that namespace and it can be imported in the file you've been reading be…

I have come to the exact same conclusion about Ruby. Finding the source of given behavior is where I tend to get the most annoyed. This is doubly so for any library which uses method_missing? or other bits of Ruby-dynamism. Yes, it can (and does) lead to terser, elegant code. But it also makes it challenging to analyze root causes, and I have become less enamored of this style as I have had to deal with it over the past few years.

In this respect method_missing? is analogous to (over)using C's preprocessors. It seemed like a good idea at the time, but...

Re: A Boggling Return to C

#79

Post by heretohelp »

davidjohnstone wrote: post #77
robryan wrote: post #18

Earlier quoted context omitted.

Providing you are aware of prefix trees. I guess you could come up with the idea independently but I would assume a lot of people when presented with the problem wouldn't.

At the end of my first year of my software engineering degree I wrote a Boggle solving program in C# using a trie. About a year later I discovered that tries are a recognised data structure and that I wasn't the first person to use one.

Tries are notorious for this by the way.

I know a programmer who's been working in the industry since the 70s, she did the same damn thing when she was young with the same exact data structure.

Re: A Boggling Return to C

#80

Post by CUR10US »

X-Istence wrote: post #33
yason wrote: post #4

I started with assembly language and I thought C was heaven. Of course, there are easier languages, there are more powerful languages, there are fancier languages and whatnot. I like Python and I adore Lisp. But I still love C most. C is the sweet spot where I can extend my programs to do high-level stuff while still keep my hands down on the actual hardware I'm programming. I like that a lot, probably because I grew…

Reading DJB's code can be both awesome in that his code is written clearly and neatly, yet at the same time it can be an excercise in frustration because he has foregone most of the standard library and written his own (especially string management, which is superior, in my humble opinion), so it can look foreign or weird to people looking at it. The source to qmail/daemontools is a pleasure to read though and having…

djb once wrote a FORTH implementation for the IOCC. It would be cool to get it running under current BSD/Linux/Solaris.

Arthur Whitney is another I would put on par with djb. He's a bit older than djb.

For expertise you can't beat W. Richard Stevens. He also studies and wrote about FORTH before focusing on solely on C.

Both Whitney and djb have a true appreciation for speed, efficiency and succinctness; both have solid foundations in maths; both can build very level abstractions. But they have different areas of focus.

djb - secure systems administration and networking. (Stevens - documentation.) Whitney - Lisp background; big data.

Whitney has proven that it's possible, using a matrix-based approach, to meet or beat the speed of C with an interpreted language.

But it's difficult to write UNIX systems or networking code without knowing C. For guidance on navigating the many pitfalls of C, djb and Stevens are as good as it gets.

Post reply on HN