Coding: Fleeting Thoughts

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Coding: Fleeting Thoughts

Postby btilly » Fri Aug 01, 2008 5:19 am UTC

You, sir, name? wrote:Sort of like static in C-like languages. Oh, what shenanigans that keyword can be up to.

Code: Select all

void foo() {
        for(static int i = 0; i < 5; i++) printf("%d", i);
}

int main() {
        for(;;) foo();
        return 0;
}


When run, produces

01234[nothing]

:-D

Your "when run" comment is somewhat misleading. When run interactively it probably produces that output. When not run interactively it probably produces nothing. :-)
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Fleeting Thoughts

Postby You, sir, name? » Sat Aug 02, 2008 12:43 am UTC

It always produces that output, irregardless if you choose to view it or not. Point remains, static for loop variables are nasty in so many ways.
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Coding: Fleeting Thoughts

Postby btilly » Sat Aug 02, 2008 2:40 am UTC

You, sir, name? wrote:It always produces that output, irregardless if you choose to view it or not. Point remains, static for loop variables are nasty in so many ways.

I beg to differ on the existence of output. Before you disagree again I would suggest that you carefully consider the complexities of buffering, and the fact that standard C libraries usually buffer differently depending on whether stdout happens to be a terminal.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
You, sir, name?
Posts: 6983
Joined: Sun Apr 22, 2007 10:07 am UTC
Location: Chako Paul City
Contact:

Re: Coding: Fleeting Thoughts

Postby You, sir, name? » Sat Aug 02, 2008 5:30 am UTC

Still, that is a case of a strange environment. The program is obviously intended to run at the terminal (since it uses printf.)
I edit my posts a lot and sometimes the words wrong order words appear in sentences get messed up.

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Sat Aug 02, 2008 5:34 am UTC

You, sir, name? wrote:Still, that is a case of a strange environment. The program is obviously intended to run at the terminal (since it uses printf.)
Console redirection is a common occurrence, and would trigger the behaviors btilly talks about. (That said, and while I don't think btilly is picking nits, I think that it still may not be necessary to mention in full for the purposes of this discussion.)

User avatar
xulaus
Posts: 136
Joined: Thu Jul 03, 2008 11:09 am UTC

Re: Coding: Fleeting Thoughts

Postby xulaus » Sat Aug 02, 2008 10:51 pm UTC

PHP is notorious for spaghetti code, yes? So why this?
goto is now a reserved keyword

NOOOOOOOOOOOOOOOooooooooooooooooooooooo.
Meaux_Pas wrote:I don't even know who the fuck this guy is

EvanED
Posts: 4331
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI
Contact:

Re: Coding: Fleeting Thoughts

Postby EvanED » Sun Aug 03, 2008 1:53 am UTC

Don't panic quite yet... Java also reserves goto, just so you can't use it. ;-)

User avatar
4835016
Posts: 5
Joined: Sat Aug 02, 2008 4:50 pm UTC

Re: Coding: Fleeting Thoughts

Postby 4835016 » Sun Aug 03, 2008 2:41 am UTC

I made a number guessing game that had values from 1 to (2^63)-1in java. I usually get it in under 70 guesses.
I just realized. When you end a class in C++, it makes a sad face.

Code: Select all

class Aclass {
     public:
          int variable
     };

Look at it... };

Programming is depressing...

User avatar
misskwiz
Posts: 96
Joined: Wed Mar 21, 2007 6:19 am UTC

Re: Coding: Fleeting Thoughts

Postby misskwiz » Sun Aug 03, 2008 2:52 am UTC

Behold! The power of default arguments that are only evaluated once.

Code: Select all

>>> def foo(i=[0]):
...     while i[0]<5:
...          print i[0]
...          i[0] += 1
...
>>> foo()
0
1
2
3
4
>>> foo()
>>>
I am currently enjoying the pathetic anger bread of a dissatisfied life.

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

Re: Coding: Fleeting Thoughts

Postby sparkyb » Sun Aug 03, 2008 3:24 am UTC

4835016 wrote:I made a number guessing game that had values from 1 to (2^63)-1in java. I usually get it in under 70 guesses.


stupid java and its lack of unsigned data types.

If you're doing it right you should always be able to guess it in 63 or fewer guess. (I assume it gives you higher or lower if you are wrong.)

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Fleeting Thoughts

Postby Berengal » Sun Aug 03, 2008 6:09 am UTC

MisterKwiz wrote:Behold! The power of default arguments that are only evaluated once.

It's somewhat of a pitfall if you don't know about it, but it's quite useful for memoization. Want something to persist through several calls to a function? Put it in the argument list (and make a wrapper, as you don't want anyone to actually use that argument for something).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
'; DROP DATABASE;--
Posts: 3284
Joined: Thu Nov 22, 2007 9:38 am UTC
Location: Midwest Alberta, where it's STILL snowy
Contact:

Re: Coding: Fleeting Thoughts

Postby '; DROP DATABASE;-- » Tue Aug 05, 2008 4:32 am UTC

I caught myself recently duplicating some code, that operates on local variables, into multiple functions. I figured it would be better if I gave this stuff its own function, but I couldn't because in each case it's operating on a different local variable that another function wouldn't have access to.
I felt like an idiot a bit later when I realized I could just pass pointers to said variables. >_<
poxic wrote:You suck. And simultaneously rock. I think you've invented a new state of being.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Coding: Fleeting Thoughts

Postby btilly » Tue Aug 05, 2008 10:31 am UTC

'; DROP DATABASE;-- wrote:I caught myself recently duplicating some code, that operates on local variables, into multiple functions. I figured it would be better if I gave this stuff its own function, but I couldn't because in each case it's operating on a different local variable that another function wouldn't have access to.
I felt like an idiot a bit later when I realized I could just pass pointers to said variables. >_<

Go back and rework the code into the form it should be in.

I suggest this not primarily for the quality of code in that section, but so to cement your insight. That will make you more likely to remember that you can do this the next time you run into this situation.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Coding: Fleeting Thoughts

Postby Qoppa » Fri Aug 08, 2008 3:28 am UTC

I'm making progress in Scheme! I solved problem 7 on Project Euler: calculate the 10,001st prime. I did it. It just took over an hour to calculate. Thank god my code worked. This calls for... a better algorithm!

Lesson learned: brute force is not the best way to calculate primes.

EDIT: A square root, and it can now do the same calculation in ~5 sec. Not the greatest, but much better than an hour.
EDIT 2: and only ~3 sec if I skip even numbers!

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

Dongorath
Posts: 93
Joined: Tue Oct 16, 2007 1:17 pm UTC

Re: Coding: Fleeting Thoughts

Postby Dongorath » Fri Aug 08, 2008 11:53 am UTC

And here I was thinking that brute force couldn't be that bad for this one. I checked what I wrote for this one, and though I didn't used the best solution, it only took 65ms to compute. Then I tried the worst algorithm I could think of. It is that bad... Well, at least, it takes more than 2 minutes before I killed it... (After adding two little simplistic optimizations, it only took 21s)

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Coding: Fleeting Thoughts

Postby Qoppa » Fri Aug 08, 2008 5:31 pm UTC

Got it down to 20 milliseconds. I thought keeping a list of previous primes found and then only checking divisibility by items in that list would be quicker, but I guess working with a list of 10000 items is cumbersome and it's faster to just check every number.

This fix (and some others) also let me bring my execution time for summing the primes below 2000000 (Project Euler no. 10) down from 10 and a half minutes to 4.66 seconds.

Look ma! I r lerningz!

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

0xBADFEED
Posts: 687
Joined: Mon May 05, 2008 2:14 am UTC

Re: Coding: Fleeting Thoughts

Postby 0xBADFEED » Fri Aug 08, 2008 6:24 pm UTC

Qoppa wrote:but I guess working with a list of 10000 items is cumbersome and it's faster to just check every number.


How were you using the list? You weren't just checking all the items in the list were you?

I would think decent speed could be acheived by using a sorted array of the currently known primes.

Then for a given number N

Code: Select all


a : Array of primes
lo = 0
hi = N/2

while(a[lo] <= hi)
    if(N % a[lo] == 0 )
       return N is not prime
    else
        lo++
        hi = N/a[lo] + 1
end
return N is prime



There may be some off-by-one errors above but I think the prinicple is sound. I haven't written any prime-sieving style programs in a long time. Does this not provide any speedup?
Last edited by 0xBADFEED on Fri Aug 08, 2008 11:42 pm UTC, edited 1 time in total.

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Coding: Fleeting Thoughts

Postby btilly » Fri Aug 08, 2008 7:09 pm UTC

Qoppa wrote:Got it down to 20 milliseconds. I thought keeping a list of previous primes found and then only checking divisibility by items in that list would be quicker, but I guess working with a list of 10000 items is cumbersome and it's faster to just check every number.

It depends on how you are accessing the list. My bet is that you were using O(n) operations by accident rather than a O(1) one. Also you only need to divide primes up to the square root.
Qoppa wrote:This fix (and some others) also let me bring my execution time for summing the primes below 2000000 (Project Euler no. 10) down from 10 and a half minutes to 4.66 seconds.

Some of the Project Euler questions are better solved with smart mathematics than smart programming. In this case you want to use the inclusion-exclusion principle. http://www.cut-the-knot.org/arithmetic/ ... sion.shtml looks like it has a reasonable explanation of that.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
Iori_Yagami
Posts: 606
Joined: Wed Oct 03, 2007 8:37 pm UTC

Re: Coding: Fleeting Thoughts

Postby Iori_Yagami » Mon Aug 11, 2008 11:44 am UTC

Do you hate programming the same way I do when it's not working the way I want it to? :cry: :cry: :cry: :evil: :evil: :evil:
They cannot defend themselves; they cannot run away. INSANITY is their only way of escape.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Fleeting Thoughts

Postby Berengal » Sat Aug 16, 2008 10:40 pm UTC

Haskell's type system is confusing/awesome, and it's functions are weird. Take for example the following functions:

Code: Select all

f :: (Num a) => a -> a
f x = x * x

g :: (Num a) => a -> a -> a
g x y = x * x * (y + 2)

f takes one argument of type class Num and produces a result of the same type as the input (the a -> a part).
g also takes one argument, despite looking like it takes two arguments, and it produces a function that has type a -> a as the result! (a -> a -> a = a -> (a -> a). Remember how f was of type a -> a ?)

Now, I've encountered currying before, but never on this scale, and it's sort of confusing to think about the intermediate functions (in python at least it is more obvious due to the explicit scoping).
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
niteice
Posts: 186
Joined: Wed May 02, 2007 4:17 am UTC
Contact:

Re: Coding: Fleeting Thoughts

Postby niteice » Sun Aug 17, 2008 9:32 pm UTC

I opened Python this morning. I wanted to write a program that would help me visualize which courses I would need to take for a double major in CS and EE. I started listing everything, all the prerequisites, spent a couple of hours writing some search algorithms...

and I hit the term "dependency graph". Neurons fired, synapses closed, and suddenly...

I did it in 5 minutes with graphviz.

:oops:
GENERATION 4294967292: The first time you see this, copy it into your sig on any forum, negate the generation, and convert it to a 32-bit unsigned integer. Social experiment.

User avatar
Iori_Yagami
Posts: 606
Joined: Wed Oct 03, 2007 8:37 pm UTC

Re: Coding: Fleeting Thoughts

Postby Iori_Yagami » Mon Aug 18, 2008 9:42 am UTC

The real WTF strange thing is that you can't do it manually. Well, makes sense - prerequisites for CS courses have to be done programmatically with a PC, otherwise, why would you think you could bear those courses if you can't even program their dependency with an algorithm? :?
And our cryptography courses' materials are stored on a secure server encrypted with 16777216 bit key, so it's your job to crack and get them, student!
They cannot defend themselves; they cannot run away. INSANITY is their only way of escape.

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Fleeting Thoughts

Postby Berengal » Mon Aug 18, 2008 2:45 pm UTC

Iori_Yagami wrote:And our cryptography courses' materials are stored on a secure server encrypted with 16777216 bit key, so it's your job to crack and get them, student!

I could do that if the algorithm was ciphertext = plaintext^key^key.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
niteice
Posts: 186
Joined: Wed May 02, 2007 4:17 am UTC
Contact:

Re: Coding: Fleeting Thoughts

Postby niteice » Tue Aug 19, 2008 2:09 am UTC

Iori_Yagami wrote:The real WTF strange thing is that you can't do it manually. Well, makes sense - prerequisites for CS courses have to be done programmatically with a PC, otherwise, why would you think you could bear those courses if you can't even program their dependency with an algorithm? :?
And our cryptography courses' materials are stored on a secure server encrypted with 16777216 bit key, so it's your job to crack and get them, student!


Well, I could have. I just realized that a far more efficient use of my time was graphviz. Maybe I'll finish it some day for the hell of it.
GENERATION 4294967292: The first time you see this, copy it into your sig on any forum, negate the generation, and convert it to a 32-bit unsigned integer. Social experiment.

miles01110
Posts: 611
Joined: Tue Oct 31, 2006 3:39 pm UTC

Re: Coding: Fleeting Thoughts

Postby miles01110 » Sun Aug 24, 2008 8:46 pm UTC

I was working on a small tcl/tk widget today.

After a couple hours, I noticed that my file was named "test.tcl"

"test.tcl" .... I changed the name.

User avatar
'; DROP DATABASE;--
Posts: 3284
Joined: Thu Nov 22, 2007 9:38 am UTC
Location: Midwest Alberta, where it's STILL snowy
Contact:

Re: Coding: Fleeting Thoughts

Postby '; DROP DATABASE;-- » Tue Aug 26, 2008 1:35 am UTC

I had that once. The menu was supposed to show up:

Code: Select all

PHONE DIALER
TEST

but the line break code didn't work properly, so the second line printed over the first...

Also, 1337th post.
poxic wrote:You suck. And simultaneously rock. I think you've invented a new state of being.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Coding: Fleeting Thoughts

Postby jaap » Tue Aug 26, 2008 8:23 am UTC

'; DROP DATABASE;-- wrote:I had that once. The menu was supposed to show up:

Code: Select all

PHONE DIALER
TEST

but the line break code didn't work properly, so the second line printed over the first...


That would have been better with:

Code: Select all

PHONE CALLER
TEST

|Erasmus|
Branson
Posts: 2643
Joined: Tue Oct 30, 2007 7:53 am UTC
Location: Sydney, Australia
Contact:

Re: Coding: Fleeting Thoughts

Postby |Erasmus| » Fri Aug 29, 2008 10:53 pm UTC

I found the shortest way me (my friends and I) know how to get GCC to throw a "confused by earlier errors: bailing out" error.

Code: Select all

if(0 continue;


that, in main, by itself, will do it.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Coding: Fleeting Thoughts

Postby Guff » Sun Aug 31, 2008 7:36 am UTC

Speaking of Project Euler, I just created an account there today. And completed the first three problems.
Now, this was my first time ever using Python, and so I did run into quite a few syntax errors before I figured out what I was doing wrong. My initial idea for the first problem ended up working:
Spoiler:

Code: Select all

a = int(raw_input('Enter an integer, a:'))
b = int(raw_input('Enter an integer, b:'))
c = int(raw_input('Enter an integer, c:'))

# sum of a, b, and ab
def multsum(n,lim):
   newlim = (lim - lim%n)/n
   sum = n*newlim*(newlim + 1)/2
   return sum
   
finalsum = multsum(a,c) + multsum (b,c) - multsum (a*b,c)
if (c%a == 0) or (c%b == 0):
   finalsum = finalsum - c
print "\nThe sum of the multiples of a and b less than c is:"
print finalsum

I tried to generalize it as much as I could, but I soon abandoned this approach for the second and third problems :)

And, as I said, this was my first time ever using Python, and short of looking up syntax for one or two things (and seeing a section on input, though I have no idea if I should be using raw_input() or not), I wrote this mostly by guessing based on my very limited previous programming experience. So, what syntax/algorithmic improvements are there to be made?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Fleeting Thoughts

Postby Berengal » Sun Aug 31, 2008 1:40 pm UTC

Python's input function could've been defined as

Code: Select all

def input(prompt = ""):
  return eval(raw_input(prompt))

In python 3, raw_input is going to be renamed input, and the original input function gone.
What you're doing with your input seems right enough.

Also, just for kicks, my solution to the first problem:

Code: Select all

print sum([n for n in range(1,1000) if n % 3 == 0 or n % 5 == 0])
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
Guff
Posts: 165
Joined: Thu Jan 03, 2008 11:56 pm UTC

Re: Coding: Fleeting Thoughts

Postby Guff » Sun Aug 31, 2008 4:54 pm UTC

Thanks.
Berengal wrote:Also, just for kicks, my solution to the first problem:

Code: Select all

print sum([n for n in range(1,1000) if n % 3 == 0 or n % 5 == 0])

Ah, that's much simpler. And I just modified that to work with problem 6, taking advantage of the fact that the square of the sum from 1 to n is the same as the sum of the cubes from 1 to n.

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

Re: Coding: Fleeting Thoughts

Postby qbg » Tue Sep 02, 2008 3:27 am UTC

Common Lisp macros indeed can hide so much code from the end user.

For example this: (sorry, I used PRINT to save it to a file)

Code: Select all

(DEFINE-APPLICATION-FRAME BUTTONS NIL NIL
                          (:PANES
                           (BUTTON
                            (HORIZONTALLY NIL
                                          (MAKE-PANE 'PUSH-BUTTON :LABEL
                                                     "Squeeze"
                                                     :ACTIVATE-CALLBACK
                                                     #'SQUEEZE)
                                          (MAKE-PANE 'PUSH-BUTTON :LABEL
                                                     "Press"
                                                     :ACTIVATE-CALLBACK
                                                     #'PRESS)))
                           (APPLICATION :APPLICATION))
                          (:LAYOUTS
                           (DEFAULT
                            (VERTICALLY NIL (1/8 BUTTON)
                                        (7/8 APPLICATION))))))

Becomes this eventually in SBCL:
...
Sorry, I was going to post it, but I got this error message: "Your message contains 60860 characters. The maximum number of allowed characters is 60000." That should give you an idea...

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: Coding: Fleeting Thoughts

Postby Berengal » Fri Sep 05, 2008 1:37 am UTC

I'm at a very weird point right now. Usually when I'm faced with a challenge, I'll always find a way to code my way out of it, either by utilizing a clever algorithm, or by cleverly pruning my brute force search to make it finish in respectable time. I've never been stumped by a problem for very long without finding at least a partially acceptable solution.

However, for some reason, I cannot for the life of me find all the proper divisors of a number given it's prime factorization.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

User avatar
phlip
Restorer of Worlds
Posts: 7569
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Coding: Fleeting Thoughts

Postby phlip » Fri Sep 05, 2008 1:44 am UTC

Code: Select all

For i in 0 to number_of_2s_in_prime_factorisation_of_n:
  For j in 0 to number_of_3s_in_prime_factorisation_of_n:
    For k in 0 to number_of_5s_in_prime_factorisation_of_n:
      ...
        factor = 2^i * 3^j * 5^k * ...

Obviously, you'd use some kind of recursion to avoid the heavily-nested-to-arbitrary-depths loops, but that's the general algorithm there.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
headprogrammingczar
Posts: 3072
Joined: Mon Oct 22, 2007 5:28 pm UTC
Location: Beaming you up

Re: Coding: Fleeting Thoughts

Postby headprogrammingczar » Fri Sep 05, 2008 1:03 pm UTC

Berengal wrote:I'm at a very weird point right now. Usually when I'm faced with a challenge, I'll always find a way to code my way out of it, either by utilizing a clever algorithm, or by cleverly pruning my brute force search to make it finish in respectable time. I've never been stumped by a problem for very long without finding at least a partially acceptable solution.

However, for some reason, I cannot for the life of me find all the proper divisors of a number given it's prime factorization.

Do some Google-fu and search for a "find permutations" algorithm. I just checked and there are loads of them out there.
Edit: here is one, written by skeptical scientist:

Code: Select all

    function listPermutations(set)
    // lists all permutations of set
    newlist list
    if size set > 1
        for x in set
            temp=listPermutations(set minus x)
            for y in temp
                prepend x to y
                add y to list
            end for
        end for
    else
        list=set
    end if
    return list
<quintopia> You're not crazy. you're the goddamn headprogrammingspock!
<Weeks> You're the goddamn headprogrammingspock!
<Cheese> I love you

btilly
Posts: 1877
Joined: Tue Nov 06, 2007 7:08 pm UTC

Re: Coding: Fleeting Thoughts

Postby btilly » Fri Sep 05, 2008 4:12 pm UTC

Berengal wrote:I'm at a very weird point right now. Usually when I'm faced with a challenge, I'll always find a way to code my way out of it, either by utilizing a clever algorithm, or by cleverly pruning my brute force search to make it finish in respectable time. I've never been stumped by a problem for very long without finding at least a partially acceptable solution.

However, for some reason, I cannot for the life of me find all the proper divisors of a number given it's prime factorization.

Suppose you have an array of the prime factors. Let me show you one way to do it in Perl:

Code: Select all

sub all_factors_from_prime {
  my %count_of_prime_factor;
  for my $prime (@_) {
    $count_of_prime_factor{$prime}++;
  }

  my @factors = 1;

  for my $prime (keys %count_of_prime_factor) {
    @factors
      = map {
          my $factor = $_;
          map {$factor * $prime**$_} 0..$count_of_prime_factor{$prime}
        } @factors;
  }
  return @factors;
}

print join " ", all_factors_from_prime(2, 2, 3), "\n";
__END__
1 2 4 3 6 12

headprogrammingczar wrote:
Berengal wrote:I'm at a very weird point right now. Usually when I'm faced with a challenge, I'll always find a way to code my way out of it, either by utilizing a clever algorithm, or by cleverly pruning my brute force search to make it finish in respectable time. I've never been stumped by a problem for very long without finding at least a partially acceptable solution.

However, for some reason, I cannot for the life of me find all the proper divisors of a number given it's prime factorization.

Do some Google-fu and search for a "find permutations" algorithm. I just checked and there are loads of them out there.

You're solving the wrong problem. Permutations are just reorderings of the factors. What Berengal wants is closer to all subsets. But not exactly because of repeated factors.
Some of us exist to find out what can and can't be done.

Others exist to hold the beer.

User avatar
sparkyb
Posts: 1091
Joined: Thu Sep 06, 2007 7:30 pm UTC
Location: Camberville proper!
Contact:

Re: Coding: Fleeting Thoughts

Postby sparkyb » Fri Sep 05, 2008 4:23 pm UTC

headprogrammingczar wrote:Do some Google-fu and search for a "find permutations" algorithm.


Edit: ah ninja'd and I didn't even see it.

Except for this problem I don't think permutations is what he wants. Maybe I'm misunderstanding what you're permuting. I was about to say that what this problem calls for is combinations of the prime factors since order doesn't matter since you actually want the product of these sets in the end. But you need all the combination of size n for every n between 1 and the size of the prime factorization. So really what you're saying is that you need every unique subset of the prime factorization but you need to be careful because there are duplicates. Basically, what philip said.

Here's my recursive python implementation of philip's algorithm:
Spoiler:
where primeFactorization is a dictionary of the count of each prime

Code: Select all

def getDivisors(primeFactorization):
    primeFactorization = dict(primeFactorization)
    primes = primeFactorization.keys()
    primes.sort()
    divisors = [1]
    for prime in primes:
        if (prime==1):
            del primeFactorization[prime]
            continue
        count = primeFactorization[prime]
        del primeFactorization[prime]
        for divisor in getDivisors(primeFactorization):
            for i in xrange(1,count+1):
                divisors.append(divisor*pow(prime,i))
    divisors.sort()
    return divisors


and my function get that prime factorization:
Spoiler:

Code: Select all

def getPrimeFactorization(n):
    primeFactorization = {}
    i = 2
    while (n!=1):
        while (n%i==0):
            primeFactorization[i]=primeFactorization.get(i,0)+1
            n/=i
        i+=1
    return primeFactorization
Last edited by sparkyb on Sat Sep 06, 2008 12:31 am UTC, edited 1 time in total.

User avatar
Briareos
Posts: 1940
Joined: Thu Jul 12, 2007 12:40 pm UTC
Location: Town of the Big House

Re: Coding: Fleeting Thoughts

Postby Briareos » Fri Sep 05, 2008 9:35 pm UTC

btilly wrote:You're solving the wrong problem. Permutations are just reorderings of the factors. What Berengal wants is closer to all subsets. But not exactly because of repeated factors.


Actually, I think he wants exactly all subsets of the set of factors. Pseudocode:

Code: Select all

properDivisors(n):
   divisors = {}
   for s in subsets(primeFactorization(n)):
      divisors.append(product(s))


where:
primeFactorization returns the set of prime factors of n (including repeated factors)
subsets returns the power set of a set (i.e. the set of all subsets)
product returns the product of all members of a set.

note: since every set is a subset of itself (though not a proper subset), this pseudocode will return n as the largest divisor of n. This could be manually removed.

EDIT: oh, right, repeated factors. You're right, btilly. Don't use this algorithm, or insert a step that checks for duplicates.
Sandry wrote:Bless you, Briareos.

Blriaraisghaasghoasufdpt.
Oregonaut wrote:Briareos is my new bestest friend.

User avatar
Enki v.2
Posts: 7
Joined: Wed Sep 10, 2008 9:51 pm UTC
Location: /dev/urandom
Contact:

Re: Declarative Programming

Postby Enki v.2 » Thu Sep 11, 2008 1:56 am UTC

Code: Select all

Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.58)
Copyright (c) 1990-2008 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- TheAnswerToLifeTheUniverseAndEverything.
% ... 1,000,000 ............ 10,000,000 years later
%
%       >> 42 << (last release gives the question)
?-         

Code: Select all

mortal(X) :- man(X).
man(socrates).
?- mortal(socrates). % yes. %
?- mortal(kitten). % no. kittens are immortal. FAIL. %


Conclusion: Damn, I love prolog. It's the only language I know that can give multiple contradictory weighted responses to a single query through pure first order predicate logic and a little basic arithmetic.+
a = a iff a = a ; else a != a

"That would be like making the justified mouth-noise while urinating!" - unnamed Atlantean Senator, Illuminatus! Trilogy

guyy
Posts: 610
Joined: Tue May 06, 2008 3:02 am UTC

Re: Coding: Fleeting Thoughts

Postby guyy » Sat Sep 13, 2008 5:37 am UTC

Out of extreme boredom, I just put a bad Internet meme in a comment after a line that should normally never be executed:

Code: Select all

GetMassOfEditedThingy = 0   'if this happens, you've achieved epic fail


...I should really go to bed.


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 4 guests