Python Programming Challenges for beginners?

[astral orange]

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

 

[alex23]

I would like to test out what I know so far by solving programming
challenges.

Project Euler can be a lot of fun: http://projecteuler.net/

 

[n00m]

[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

 

[Wolodja Wentland]

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.

Project Euler has already been pointed out to you, but I enjoyed solving
the riddles at:

http://www.pythonchallenge.com/

Enjoy!
--
.''`. Wolodja Wentland <[email protected]>
: :' :
`. `'` 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-----

 

[John McMonagle]

[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

Way to fail dude.

You're missing some sub-strings.

 

[n00m]

You're missing some sub-strings.

Yes!

 

[Jon Clements]

Yes!

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

Jon.

 

[n00m]

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

Jon.

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

PS It's a hard problem; so let's leave it alone

 

[J Kenneth King]

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

http://www.pythonchallenge.com/

I find this one neat because it uses riddles rather than straight
math.

 

[MRAB]

[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 abba
bbaz
abbaz
==================
Answer: 11

Answer: 13

 

[Paul Rudin]

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

PS It's a hard problem; so let's leave it alone

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)))

 

[n00m]

abba

bbaz> abbaz

Answer: 13- Hide quoted text -

14 ! with '' (empty substring )

 

[n00m]

efficiency ...

This is it!

 

[Lie Ryan]

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

PS It's a hard problem; so let's leave it alone

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...

 

[jim-on-linux]

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

 

[n00m]

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...

.... and you can check it here: http://www.spoj.pl/problems/DISUBSTR/
I see there only one (accepted) solution in Python:
http://www.spoj.pl/ranks/DISUBSTR/lang=PYTH 2.5

 

[n00m]

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;
}

 

[Edward A. Falk]

Project Euler can be a lot of fun: http://projecteuler.net/

Oooh, that *does* look like fun.

 

[Jon Clements]

Oooh, that *does* look like fun.

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.