Do I have what it takes?

adekoba · 2008-02-28 22:29:15

the desire to create keeps me going. I love making programs that work, and sometimes after you are done, you look back on an algorithm and think, "beautiful." Some functions really are just very neat.

It is also a way for me to express pure logic. Regular language is not very apt for this, as words are often left up to personal interpretation and can be ambiguous.

lloeki · 2008-02-28 22:48:33

OT: That was what I was about to comment to: there is that sort of magic point where mathematics gives you a chill upon looking at some well tied piece of reasoning, and it makes you shiver at how both the simplicity and cleverness of it just makes sense, yet reaches a seemingly overwhelming conclusion.

Ultimately mathematics gave me a sort of insight of myself and the world around me and I began to make sense out of things (or they began to make sense to me), and I start to encompass the world with a sort of structure emerging in mind.

This is overwhelming.

Einstein said:

To me it suffices to wonder at these secrets and to attempt humbly to grasp with my mind a mere image of the lofty structure of all that is there

PS: Yes, some people do think I'm mad.

AbacusMonkey · 2008-02-29 07:20:29

wuischke wrote:

Allow me to give you a homework:
Create a program, which takes a number from 1 to 365 as input and tells you which month and which day of month this number represents.
E.g. 87 -> 28.03. or 256 -> 13.08. [I hope I got these numbers right, I calculated it manually]
The age shouldn't matter.

I am an I.T. student at Queensland University of Technology in Australia. I am majoring in Software Architecture and have just begun second year. I have done programming languages such as VB.NET, C# and Scheme and have finally started learning C this year.

Seeing this post (directed from the awesome newsletter), I decided to give this problem a shot.

Here is my solution to it.

Please don't mind the excessive commenting, Uni request we do it like that so I'm kind of in the habit.

Not sure how good it is, but it seems to do what we requested.

/* Small program to convert a day of the year
  * into a day/month representation
  * 29/02/2007 by Abacus Monkey
  */

#include <stdio.h>

int main()
{
   // Integer to receive user input
   int userInput;
   // Array of the days in each month, from January to December
   int months[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
   // Integer to store outputs
   int day, month;
   // Array counter, and day counter respectively
   int i, count = 0;
   
   // Request user input
   printf("Please enter a number between 1 and 365: ");
   scanf("%d", &userInput);
   
   // Calculates the day and month according to the users input
   for (i = 0; i < 12; i++)
   {
      count += months[i];
      // Checks to see if the users day falls within the current month
      if (userInput <= count)
      {
         // An exception occurs in the first month 
         // that requires special treatment
         if (i == 0)
         {
            day = userInput;
            month = 1;
            break;
         }
         // Every other month uses this calculation
         else 
         {
            // The final calculated day is equal to the total of
            // all days passed before the start of the current month.
            day = userInput - (count - months[i]);
            month = i + 1;
            break;
         }
      }
   }
   
   // Print final output
   printf("Day %d is equal to %d/%d\n", userInput, day, month);
   
   return 0; 
}

Last edited by AbacusMonkey (2008-02-29 07:21:07)

iphitus · 2008-02-29 07:33:09

kensai: Seems like you've got "the right stuff". Just find an itch to scratch, and go for that. I'm sure there's some sort of utility, tool or application that would make your computer easier or more comfortable. Or just reimplement something you dont like.

I found exercises boring for anything beyond learning basic constructs. I've always found sitting there tackling a real problem, sometimes out of my depth, going "wtf"... .and then working it out, is way more rewarding. Don't perceive things as "too hard" -- just try and you'll be surprised at what you can do.

Depending on what language you learn.. there's always little tricks. My rule of thumb for python is "if it seems to complicated/messy/wrong, then it probably is"

James

Last edited by iphitus (2008-02-29 07:34:24)

SiC · 2008-02-29 08:10:01

AbacusMonkey wrote:

wuischke wrote:
Allow me to give you a homework:
Create a program, which takes a number from 1 to 365 as input and tells you which month and which day of month this number represents.
E.g. 87 -> 28.03. or 256 -> 13.08. [I hope I got these numbers right, I calculated it manually]
The age shouldn't matter.
I am an I.T. student at Queensland University of Technology in Australia. I am majoring in Software Architecture and have just begun second year. I have done programming languages such as VB.NET, C# and Scheme and have finally started learning C this year.
Seeing this post (directed from the awesome newsletter), I decided to give this problem a shot.
Here is my solution to it.
Please don't mind the excessive commenting, Uni request we do it like that so I'm kind of in the habit.
Not sure how good it is, but it seems to do what we requested.

Not a bad idea. A quicker way of doing it would be to have a pre-initialised array containing every possible combination of day and month. Requires more memory, but since when has that been a problem.

wuischke · 2008-02-29 09:04:17

AbacusMonkey: Your code works well and it looks like I miscalculated the day for 256... on a side note: I'm jealous that you learn scheme in university.

Anyway: Your code is very verbose. This is alright for a small project, but I personally value readability and short code very high. It's easier to maintain and often it is faster, too. My solution for the algorithm was the following: (month has been initialized with 0 and month+1 gives you the correct month to output)

        while (months[month] <  day) {
                day = day - months[month];
                month++;
        }

Now, we have a problem: There are sometimes leap years, e.g. 2008 is one. Extend your code to deal with this when the user inputs a day and the year. I recommend writing a function which checks a year for being a leap year or not.

lloeki · 2008-02-29 15:05:02

A quicker way of doing it would be to have a pre-initialised array containing every possible combination of day and month. Requires more memory, but since when has that been a problem.

SiC, this is optimization worthy of assembly language... in higher levels that's where bloat comes from. besides, while correct, it does not really tackle the issue, because there would be no algorithm apart from a pointer lookup.

wuischke, your approach in indeed very compact, yet it has a bottleneck.
for every loop, you have a count of two operations. therefore, the worst case is that you have to do 2*n operations to obtain the data you wish. of course we only have twelve months here, but in a n case for equiprobable data you have a mean cost of 2*n/2, otherwise said as a complexity of O(n).

it would be wiser to have months array set to [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] and compare day on that. then you compute the day in the month and month. this way the computation complexity is O(1).

this means that in our case, imagining a situation of a program that would recklessly call the function above, even with only twelve months, your approach would be slower by six times to the one I described.

AbacusMonkey, while the solution you give is correct, to me it has two flaws:
- variable naming: I feel months is not the right name. after all the array does not hold months but days in a given month (days_in_month would be more appropriate). this may sound picky, but someone evaluating you may or may not let that go. also, it induces some thinking overhead on the reader's mind as to what the variable really means, each time it is used. this can be confusing, and may lead to errors.
- unvalidated user input: that may sound picky too, and not on the spot of the issue, but I had an instructor who literally threw /dev/urandom into our programs input. if the program didn't react accordingly, then we were having malus on the mark.

Last edited by lloeki (2008-02-29 15:21:18)

shining · 2008-02-29 16:20:02

lloeki wrote:

OT: That was what I was about to comment to: there is that sort of magic point where mathematics gives you a chill upon looking at some well tied piece of reasoning, and it makes you shiver at how both the simplicity and cleverness of it just makes sense, yet reaches a seemingly overwhelming conclusion.
Ultimately mathematics gave me a sort of insight of myself and the world around me and I began to make sense out of things (or they began to make sense to me), and I start to encompass the world with a sort of structure emerging in mind.
This is overwhelming.
Einstein said:
To me it suffices to wonder at these secrets and to attempt humbly to grasp with my mind a mere image of the lofty structure of all that is there
PS: Yes, some people do think I'm mad.

lloeki wrote:

it would be wiser to have months array set to [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] and compare day on that. then you compute the day in the month and month. this way the computation complexity is O(1).

You are confusing mathematics and d r u g s

Last edited by shining (2008-02-29 16:20:55)

SiC · 2008-02-29 17:17:59

lloeki wrote:

A quicker way of doing it would be to have a pre-initialised array containing every possible combination of day and month. Requires more memory, but since when has that been a problem.
SiC, this is optimization worthy of assembly language... in higher levels that's where bloat comes from. besides, while correct, it does not really tackle the issue, because there would be no algorithm apart from a pointer lookup.

Totally agreed, in fact if writing this in C, I would probably just have used asm() to do it. I just wanted to give an alternative way of doing it. I've spent all week optimising some frequently called code that had been written in such a fashion by a previous dev-team. May there souls burn in hell In fact using your argument below regarding operation complexity, this is several orders of magnitude quicker even than your solution, yours would be approximately O(2n) where n is the number of iterations required, whereas mine is just O(1).

lloeki wrote:

wuischke, your approach in indeed very compact, yet it has a bottleneck.
for every loop, you have a count of two operations. therefore, the worst case is that you have to do 2*n operations to obtain the data you wish. of course we only have twelve months here, but in a n case for equiprobable data you have a mean cost of 2*n/2, otherwise said as a complexity of O(n).
it would be wiser to have months array set to [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] and compare day on that. then you compute the day in the month and month. this way the computation complexity is O(1).
this means that in our case, imagining a situation of a program that would recklessly call the function above, even with only twelve months, your approach would be slower by six times to the one I described.

Just to illustrate that for wuischke, or anyone else, you would iterate through the loop as follows. Only then would you perform the subtraction.

 removed

lloeki wrote:

AbacusMonkey, while the solution you give is correct, to me it has two flaws:
- variable naming: I feel months is not the right name. after all the array does not hold months but days in a given month (days_in_month would be more appropriate). this may sound picky, but someone evaluating you may or may not let that go. also, it induces some thinking overhead on the reader's mind as to what the variable really means, each time it is used. this can be confusing, and may lead to errors.
- unvalidated user input: that may sound picky too, and not on the spot of the issue, but I had an instructor who literally threw /dev/urandom into our programs input. if the program didn't react accordingly, then we were having malus on the mark.

Definitely, variable naming is extremely important when doing coding, not merely because someone else may read it but more because you will read it yourself later. It is an exceptionally good idea to get into a good habit when naming variables and functions, bad habits die hard. I am a big fan of hungarian notation. Not the mangled version that most windows developers use, but if you read the original thesis behind it, it has some excellent ideas regarding variable and function naming, and they could all be considered "best practice". Ofc ymmv.

Last edited by SiC (2008-02-29 18:26:29)

SiC · 2008-02-29 17:21:00

shining wrote:

You are confusing mathematics and d r u g s

Mathematics is better than d r u g s. You get more done in the long run. It's cheaper too

Last edited by SiC (2008-02-29 17:21:21)

peets · 2008-02-29 18:00:00

...but, but, writing [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] takes more developer time! I try to go by the maxim "early optimization is the root of all evil". It turns out programmers and mathematicians are pretty bad at predicting where the bottlenecks in their code will be.

I think I try to write my code in the most elegant way (which usually means the most human-readable way, where the code is pretty close to the concepts as humans normally picture them). I also get shivers when looking at well-done math/physics derivations, and the terse equations that result from them. (or truths that can't be proven: "this expression is unprovable", if made out of legal syntax for such and such a formal system, is true because it can't be proven!)

Weird, I also like Perl.

lloeki · 2008-02-29 18:11:15

Just to illustrate that for wuischke, or anyone else

I didn't show the code for people to ponder on it oh well.

...but, but, writing [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] takes more developer time! I try to go by the maxim "early optimization is the root of all evil".

that's why I first went as far as generating days_of_month, from the very rules we all use to actually generate it 'by hand'.

#!/usr/bin/python

import sys

# read arguments
d = int(sys.argv[1])
y = int(sys.argv[2])
print d, y

# what we want to generate
#s J   F   M   A   M   J   J   A   S   O   N   D
#m 1   2   3   4   5   6   7   8   9   10  11  12
#n 31  28  31  30  31  30  31  31  30  31  30  31
#t 31  59  90  120 151 181 212 243 273 304 334 365

# index list
m_list = range(1, 13)
print m_list

# leap year extra day
def leap(y):
    if y % 400 == 0 or (y % 100 != 0 and y % 4 == 0):
        return 1
    else:
        return 0

# month index to day count in that month
def m_to_n(m, y):
    if m > 7:
        return 31 - (m % 2)
    elif m != 2:
        return 30 + (m % 2)
    else:
        return 28 + leap(y)

# list of number of days in a given month
n_list = [ m_to_n(m,y) for m in m_list ]
print n_list

# list of number of days necessary to complete a month
t_list = []
for n in n_list:
    if len(t_list) == 0:
        t_list.append(n)
    else:
        t_list.append(n + t_list[-1])
print t_list

# match the slice we're in
for i in range(0,len(t_list)):
    if d < t_list[0]:
        print 1, d
        break
    elif d <= t_list[i]:
        print i+1, d - t_list[i-1]
        break

I'm a beginner in python so there may be some more pythonic way to do things.

Last edited by lloeki (2008-02-29 18:19:36)

SiC · 2008-02-29 18:23:11

peets wrote:

...but, but, writing [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] takes more developer time! I try to go by the maxim "early optimization is the root of all evil". It turns out programmers and mathematicians are pretty bad at predicting where the bottlenecks in their code will be.

yeah definitely, i remember implementing a software system for smoothing whilst doing my dissertation, I had only the slightest idea of how the algorithm was going to work and it turned out that my initial "optimizations" did squat, and at one point made things worse

peets wrote:

I think I try to write my code in the most elegant way (which usually means the most human-readable way, where the code is pretty close to the concepts as humans normally picture them). I also get shivers when looking at well-done math/physics derivations, and the terse equations that result from them. (or truths that can't be proven: "this expression is unprovable", if made out of legal syntax for such and such a formal system, is true because it can't be proven!)
Weird, I also like Perl.

Human readable code only helps so far, sometimes you just can't write things that way. As for elegance, to my mind elegance comes from the simplest possible solution to a particular task. That doesn't necessarily mean the quickest, but certainly it usually tends that way.

As an aside, do you have any formal training in mathematics or physics, or is it just a hobby?

SiC · 2008-02-29 18:25:59

lloeki wrote:

Just to illustrate that for wuischke, or anyone else
I didn't show the code for people to ponder on it oh well.

Oooh, sorry matey Didn't realise that was why you left it out.... i'll edit the post and hope nobody else read it lol

lloeki wrote:

...but, but, writing [31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334, 365] takes more developer time! I try to go by the maxim "early optimization is the root of all evil".
that's why I first went as far as generating days_of_month, from the very rules we all use to actually generate it 'by hand'.
I'm a beginner in python so there may be some more pythonic way to do things.

Thats pretty much how i was thinking of getting the initial array, however I wasn't thinking in python, which is a language I have never used (But certainly one I keep meaning to learn). I would probably have written it in basic to be honest. Either that or C.

wuischke · 2008-02-29 19:21:01

Wow, there's more to my little homework as I thought... ;-)

I think I'll open a little "programming challenges" thread later. I'll think about an interesting problem you can solve within less than an hour, but which still is not too trivial. The demand seems to exist and it's fun.

lloeki: I'm more or less familiar with complexity and I can see your point, although 6 times is wrong, if I'm not mistaken. (For the worst case I have 12 * 2 instructions + 12 * 1 comparision = 36; you have 12 * 1 instruction + 12 * 1 comparision + 1 instruction (you have to do one substraction, too) = 25 -> my code is up to 1.44 times slower and if you substract the calculations necessary to generate your array, mine needs even less instructions. For higher numbers, your code will be ~1.5 times better, though)

But I would happily trade in such a relatively small speed difference for smaller and easier to understand code. That's why I'm currently learning Haskell. I've written (and sometimes I still write) some very bad code in this regard...speed is not everything.

shining · 2008-02-29 19:36:43

wuischke wrote:

lloeki: I'm more or less familiar with complexity and I can see your point, although 6 times is wrong, if I'm not mistaken. (For the worst case I have 12 * 2 instructions + 12 * 1 comparision = 36; you have 12 * 1 instruction + 12 * 1 comparision + 1 instruction (you have to do one substraction, too) = 25 -> my code is up to 1.44 times slower and if you substract the calculations necessary to generate your array, mine needs even less instructions. For higher numbers, your code will be ~1.5 times better, though)

For higher numbers of what? Executions?
If yes, we might finally be on the same line

wuischke · 2008-02-29 19:59:24

shining: I have 3 instructions per month, while he has two per month. When we use a high number of months (by either increasing the number of months of the year or executing the code many times), all one-time differences can be ignored, resulting in a ratio of 3/2 -> 1.5.

Edit: P.S. See http://bbs.archlinux.org/viewtopic.php?id=44730

Last edited by wuischke (2008-02-29 20:34:44)

shining · 2008-02-29 20:38:07

wuischke wrote:

shining: I have 3 instructions per month, while he has two per month. When we use a high number of months (by either increasing the number of months of the year or executing the code many times), all one-time differences can be ignored, resulting in a ratio of 3/2 -> 1.5.

If you increase the number of months, then his array generation loop will increase too...
The only difference between your version and lloeki one is that he splitted the loop in two.
And the only advantage of doing that is that you can do the initialization once, and then use that array several times.
For example, the code could be simply edited to be run into a loop, asking the user to enter a value as many times as he wants.

Otherwise, if you really care about the complexity of algorithm with higher values (which is not possible in this problem), then doing a linear search sounds really funny.
Even more when you notice that the "cumulative array" is already sorted.

SiC · 2008-02-29 21:52:45

shining wrote:

If you increase the number of months, then his array generation loop will increase too...

In something such as you have here, there is no array generation loop, it is a fixed cost when writing the code. If you assume a normal year, and don't account for leap years (which is what I would have done as this program is an exercise in algorithm design rather than a practical exercise) then his will always be faster than yours, although you are correct in saying that yours is 3/2 times slower.

Taking it to the extreme that I took it, you would have the array permanently stored within the program code, so the function could in theory be 36 times faster than yours, however in practice would average out at 18 times quicker.

Here's a simple programming exercise for you it should take no longer than 10 minutes to solve. Write an algorithm to continuously generate prime numbers, until aborted by a keypress.

Last edited by SiC (2008-02-29 21:53:41)

peets · 2008-02-29 22:55:08

SiC wrote:

As an aside, do you have any formal training in mathematics or physics, or is it just a hobby?

Whatever it means, I was in an engineering physics degree for two years and some weeks. I agree with your definition of elegance. That's how I consider math stuff elegant. I don't know enough computer science to consider it math yet!

SiC · 2008-02-29 23:05:03

peets wrote:

Whatever it means, I was in an engineering physics degree for two years and some weeks. I agree with your definition of elegance. That's how I consider math stuff elegant. I don't know enough computer science to consider it math yet!

Engineering Physics Bit dry for my tastes, too much calculus lol, but certainly mathematics! As for computer science, well its not so much that it's pure maths, but the use and design of algorithms has it's roots in mathematics. If you can think logically and clearly, which most mathematicians are trained to do, then you will be better at the computer side of things.

lloeki · 2008-02-29 23:09:07

I beg to differ, or rather explain how I found the 6:1 ratio. This is slightly more complicated than simply counting number of "instructions".

here I am not considering a variable number of months at all.
I am also considering the static case, not the one where I compute the whole array.
also, I consider the time cost source as being addition/substraction operations.

now, the input to the program is any number in range 1-365.

for any value of the input, the number of calculations done in my algorithm is exactly zero (d) or one (d - t_list[i-1])

for any value of the input, the number of calculations done in wuischke algorithm is at most 12 (day - months[month]). I ignore the simple month++ increment.

now the important part is that we consider the function being called a high number of times in a row, with purely random choice among 1-365 as input. given that the repartition of days in months is almost even (~30), the mean number of calculations done in wuischke algorithm will be 6, while for me it is constant and equal to 1, thus my 1:6 ratio.

the reason why I take only additions into account is that I generalized the algorithms in something like:

for i in range(0,len(list)):
    if d < list[i]:
        f(d,i)
        break

vs

while d < list[i]:
    d = f(d, i)
    i++

f being the costy calculation. this is why one can't count instructions, and how one would evaluate the generic performance of a given algorithm.
of course this is offseted here because f is trivial and consists of a mere substraction. also a compiler may be able to optimise this greatly.

as a simple empirical confirmation, I wrote those two snippets (with cost() aggravating the algorithmical cost unit):

date1.py

from random import *

t_list = [ 31,  59,  90, 120, 151, 181, 212, 243, 273, 304, 334, 365 ]

def cost():
    z=0
    for i in range(1, 1000):
        z=z+1

for i in range(1, 10000):

    d = randint(1, 365)

    for i in range(0,len(t_list)):
        if d < t_list[0]:
            d
            cost()
            break
        elif d <= t_list[i]:
            d - t_list[i-1]
            cost()
            break

date2.py

from random import *

n_list = [ 31,  28,  31,  30,  31,  30,  31,  31,  30,  31,  30,  31 ]

def cost():
    z=0
    for i in range(1, 1000):
        z=z+1

for i in range(1, 10000):

    d = randint(1, 365)

    i=0
    k=d
    while n_list[i] < k:
        k = k - n_list[i]
        cost()
        i = i+1

and I ran a number of times:

time python date1.py ; time python date2.py

which gives me 0m1.450s vs 0m7.483s, that's a ratio of ~5.

the funniest part being that if you comment out the calls to cost(), the faster one is wuischke's (1.923/1.682 = 1.14). I can only suppose some compilation optimisation takes place, or I'm using some costy python feature...

Last edited by lloeki (2008-02-29 23:20:59)

wuischke · 2008-02-29 23:43:35

lloeki and shining: Thank you both for extending my mindset when regarding such problems. I would never have thought about binary search or different weighting for these instructions myself when thinking about this problem.

Complexity is (just as functional programming) something which is more or less ignored at my university. Unfortunately.

lloeki · 2008-03-01 10:49:57

you're welcome. but you know, this is nonetheless interesting to me, as I come to get around some performance issues on python, and have a better insight on it. this kind of discussion is profitable to everyone

as one says: "if we exchange two objects, we have one object each, if we exchange two ideas, we have two ideas each".

back on topic, anyone on the prime number task?

Last edited by lloeki (2008-03-01 10:51:29)

kevin89 · 2008-03-01 14:42:57

@lloeki: You should really take a look at http://projecteuler.net.
This site has all kinds of mathematical problems to be solved in some kind of programming language.

It's quite fun if you like programming

Arch Linux

#26 2008-02-28 22:29:15

Re: Do I have what it takes?

#27 2008-02-28 22:48:33

Re: Do I have what it takes?

#28 2008-02-29 07:20:29

Re: Do I have what it takes?

#29 2008-02-29 07:33:09

Re: Do I have what it takes?

#30 2008-02-29 08:10:01

Re: Do I have what it takes?

#31 2008-02-29 09:04:17

Re: Do I have what it takes?

#32 2008-02-29 15:05:02

Re: Do I have what it takes?

#33 2008-02-29 16:20:02

Re: Do I have what it takes?

#34 2008-02-29 17:17:59

Re: Do I have what it takes?

#35 2008-02-29 17:21:00

Re: Do I have what it takes?

#36 2008-02-29 18:00:00

Re: Do I have what it takes?

#37 2008-02-29 18:11:15

Re: Do I have what it takes?

#38 2008-02-29 18:23:11

Re: Do I have what it takes?

#39 2008-02-29 18:25:59

Re: Do I have what it takes?

#40 2008-02-29 19:21:01

Re: Do I have what it takes?

#41 2008-02-29 19:36:43

Re: Do I have what it takes?

#42 2008-02-29 19:59:24

Re: Do I have what it takes?

#43 2008-02-29 20:38:07

Re: Do I have what it takes?

#44 2008-02-29 21:52:45

Re: Do I have what it takes?

#45 2008-02-29 22:55:08

Re: Do I have what it takes?

#46 2008-02-29 23:05:03

Re: Do I have what it takes?

#47 2008-02-29 23:09:07

Re: Do I have what it takes?

#48 2008-02-29 23:43:35

Re: Do I have what it takes?

#49 2008-03-01 10:49:57

Re: Do I have what it takes?

#50 2008-03-01 14:42:57

Re: Do I have what it takes?

Board footer