Python Programming Challenges for beginners?

Discussion in 'Python' started by astral orange, Nov 27, 2009.

  1. Hi-

    I am reading the online tutorial along with a book I bought on Python.
    I would like to test out what I know so far by solving programming
    challenges. Similar to what O'Reilly Learning Perl has. I really
    enjoyed the challenges at the end of the chapter and it really help me
    test out if I was truly taking in the material like I should. Could I
    get some suggestions on resources? Is there anywhere where I can go
    online (for free or purchase) for programming problems? I am familiar
    with sites like Code Chef...etc...but at this stage that is not the
    right 'venue' for me. I mainly need challenges like the ones they have
    in Learning Perl.

    Thanks again for all the help,
    457r0
     
    astral orange, Nov 27, 2009
    #1
    1. Advertisements

  2. astral orange

    alex23 Guest

    Project Euler can be a lot of fun: http://projecteuler.net/
     
    alex23, Nov 27, 2009
    #2
    1. Advertisements

  3. astral orange

    n00m Guest

    [skip]

    How about the next problem:
    you are given string "s" (len(s) <= ~10000), in the string only
    letters 'a'..'z'
    Task: to count the number of all *different* substrings of "s"

    Example:
    s = 'abbaz'
    Its different substrings are:
    a
    b
    z
    ab
    bb
    ba
    az
    abb
    bba
    baz
    abbaz
    ==================
    Answer: 11
     
    n00m, Nov 27, 2009
    #3
  4. Project Euler has already been pointed out to you, but I enjoyed solving
    the riddles at:

    http://www.pythonchallenge.com/

    Enjoy! :)
    --
    .''`. Wolodja Wentland <-heidelberg.de>
    : :' :
    `. `'` 4096R/CAF14EFC
    `- 081C B7CD FF04 2BA9 94EA 36B2 8B7F 7D30 CAF1 4EFC

    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.10 (GNU/Linux)

    iQIcBAEBCAAGBQJLD4xcAAoJEIt/fTDK8U78sfwP/2ISaaFsYR9utTO2ygaWH1Gn
    MdPVZUh4izLKlzsoFg62fnqjllV4MIwBPL9BVpiG/aYUDI0xjFYaGYFNbqNavoaW
    EBlIJ/k3xaazqwzVEdeS/GcQkDCoxpPbVpDKC6PTR1jMpx6j90ikUd1hEqccSKSd
    u8DlV3FcYnmfnI2lTwIPOo88iZ7TB/x00emhji+qJVRH1xJCcU52amF7QuHZpmhn
    S66tWVa12cD7B5teeZzS2VycVDNplmdG18P8y5CxK9whZv8XnqXp/3U7fFkprhtB
    Lgw1Zk/14AWFtyzL4fEUSHg08V4oZx8cTX8DFqd/MHQCTezokr62B3XzYVBPz3gF
    +tgHIfWpGRt46G+krFP+bKmAo2Ye3hSsQ23Q7w001M3kKn+fi4jNPXt9YxJ0yP7U
    /8XESaFfnKROolqgsUhe5OOUP5RRKTFfYSyWspuNG1tGs5AImwTgsToaL7abNaX5
    lW0NQb+0ZDGWYVOfwNfFom3ecdxTBwt+8aDskiDEahn6Ps8TaQ5NpXhmwo+FQ1Yx
    nP77T8tpSXIKYmSzSHwUvQcX4fL44jZ7Ky4+2Iaif7atayPTpR26TJ7iZbYqlhVv
    ssOE6HFWDURjeV41j1YoQm/QR5zzx7RucZnQnhHTbzIQbfMI9Clv0Z6M8YPrhRPz
    qr1HPPcMOK3M3ccajzZW
    =CNRl
    -----END PGP SIGNATURE-----
     
    Wolodja Wentland, Nov 27, 2009
    #4
  5. Way to fail dude.

    You're missing some sub-strings.
     
    John McMonagle, Nov 27, 2009
    #5
  6. astral orange

    n00m Guest

    You're missing some sub-strings.

    Yes! :)
     
    n00m, Nov 27, 2009
    #6
  7. astral orange

    Jon Clements Guest

    Of course, if you take '~' literally (len(s) <= -10001) I reckon
    you've got way too many :)

    Jon.
     
    Jon Clements, Nov 27, 2009
    #7
  8. astral orange

    n00m Guest

    Then better: len(s) < abs(~10000)

    PS It's a hard problem; so let's leave it alone
     
    n00m, Nov 27, 2009
    #8
  9. http://www.pythonchallenge.com/

    I find this one neat because it uses riddles rather than straight
    math.
     
    J Kenneth King, Nov 27, 2009
    #9
  10. astral orange

    MRAB Guest

    Answer: 13
     
    MRAB, Nov 27, 2009
    #10
  11. astral orange

    Paul Rudin Guest

    what's hard? substrings of a string? If you don't care too much about
    efficiency it's easy enough:

    import itertools
    def subs(s):
    return set(itertools.chain(
    s[i:j]
    for i in xrange(len(s))
    for j in xrange(i, len(s)+1)))
     
    Paul Rudin, Nov 27, 2009
    #11
  12. astral orange

    n00m Guest

    abba

    14 ! with '' (empty substring :))
     
    n00m, Nov 27, 2009
    #12
  13. astral orange

    n00m Guest

    This is it!
     
    n00m, Nov 27, 2009
    #13
  14. astral orange

    Lie Ryan Guest

    I'm not going to write it, but I guess a fairly efficient solution can
    be written with using a Trie: http://en.wikipedia.org/wiki/Trie

    and iterating over its items, including partial prefixes.

    Worse case scenario for creating the tree would be O(n**2) where n =
    length of string, and iterating the structure would take O(N) where N =
    number of different substring.

    for "abbaz", the data structure would be:
    {'a': {'b': {'b': {'a': {'z': None}}},
    'z': None,
    },
    'b': {'b': {'a': {'z': None}},
    'a': {'z': None}},
    },
    'z': None,
    }

    iterating the structure:
    a
    ab
    abb
    abba
    abbaz
    az
    b
    bb
    bba
    bbaz
    ba
    baz
    z
    ---
    13 (not including '')

    Now, this makes me interested. How efficient it would be when len(s) ==
    10000... might as well write it and see. Take back what I said, give me
    a minute...
     
    Lie Ryan, Nov 28, 2009
    #14
  15. astral orange

    jim-on-linux Guest

    I have used py2exe many times with success.

    My current program is completing as expected but the
    exe file fails to open.

    The output file states that _imaging_gif is missing. I
    can run the program ok with IDLE but after converting
    with py2exe, the exe file just sits there.
    I'm using 2.6 on win XP.

    Any Ideas?

    jim-on-linux
     
    jim-on-linux, Nov 28, 2009
    #15
  16. astral orange

    n00m Guest

    n00m, Nov 28, 2009
    #16
  17. astral orange

    n00m Guest

    PS
    My straightforward C++ solution got TLE...

    #include <stdlib.h>
    #include <stdio.h>
    #include <string.h>
    #include <ctype.h>
    #include <math.h>
    #include <time.h>
    #include <iostream>
    #include <vector>
    #include <string>
    using namespace std;

    int main() {
    //freopen("88.txt", "rt", stdin);
    //freopen("99.txt", "wt", stdout);
    int tcs;
    string s;
    cin >> tcs;
    while (tcs-- > 0) {
    cin >> s;
    int n = s.size();
    s = s + ' ';
    vector< vector<int> > a(256);
    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
    int lev = 0;
    vector<int> p = a[s];
    vector<int> q;
    while (!p.empty()) {
    q.clear();
    ++lev;
    for (int j = 0; j < p.size(); ++j) {
    if (s[p[j] + 1] == s[i + lev]) {
    q.push_back(p[j] + 1);
    }
    }
    p.swap(q);
    }
    a[s].push_back(i);
    ans += n - i - lev;
    }
    cout << ans << endl;
    }

    return 0;
    }
     
    n00m, Nov 28, 2009
    #17
  18. Edward A. Falk, Nov 30, 2009
    #18
  19. astral orange

    Jon Clements Guest

    Only problem is (quoting Douglas Adams): "I love deadlines. I like the
    whooshing sound they make as they fly by."

    scipy is extremely useful to have installed, and if you get *really*
    into it, then the sage library|system at http://sagemath.org is
    *extremely* useful...

    Jon.
     
    Jon Clements, Dec 1, 2009
    #19
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.