From: Emre Sevinc
Subject: Help me come up with a few and simple programming challenges
Date:
Message-ID: <87psrz9yw0.fsf@ileriseviye.org>
Can programming languages really shape the ways we think
about solving problems?
http://en.wikipedia.org/wiki/Sapir-Whorf_and_programming_languages
I know this is an endless discussion. The same questions
is asked again and again related to natural language.
What I want to do is gather some data for a comparative study. I have
a bunch of CS students who saw some Scheme programming but
no other programming language. And then it is easy to find
some programmers (close to the avg. age of the first group, which
is 19 years) who used C-like languages (C, C++, Java, Perl, PHP, etc.) but
not Lisp, Scheme or other Lisp variants.
Now I need to find some small programming challenges. The problems
need to be precise, well defined and short. The solution must not
take long (in Lisp, Scheme) because I don't have time until
the end of the world, a couple of students in a class setting
and about 1-2 hours. Maybe 4-5 programming questions. What
I want to have is not the exact solution but capture the thought
processes of those students, thus I will tell them (or their professor
will tell) to note down every trial they make, not only the exact
solution (if they can find it).
My first candidate question is the famous permutation task, which
can be expressed roughly as "given a set of elements, write a program
that produces all the permutations of that set". My intuition and hypothesis
is that the thought process of Scheme (or Lisp) programmer is going
to be different than a non-Lisp programmer (maybe similar things can
be said for a Prolog programmer but I don't have such participants
for this study unfortunately).
I'd be very glad if comp.lang.lisp participants can come up
with small programming challenges having the characteristics
described above that can help me distinguish between those
Scheme-but-no-other-language knowing kids and another group
of non-Lisp programmers. If the challenges seem a little bit complex
but have easy and short solutions in Lisp/Scheme (contrasting the
solutions in C, Java, Perl, etc.) I believe they can help me
with this research.
Thanks in advance.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Emre Sevinc wrote:
>
> Can programming languages really shape the ways we think
> about solving problems?
>
> http://en.wikipedia.org/wiki/Sapir-Whorf_and_programming_languages
>
> I know this is an endless discussion. The same questions
> is asked again and again related to natural language.
>
> What I want to do is gather some data for a comparative study. I have
> a bunch of CS students who saw some Scheme programming but
> no other programming language. And then it is easy to find
> some programmers (close to the avg. age of the first group, which
> is 19 years) who used C-like languages (C, C++, Java, Perl, PHP, etc.) but
> not Lisp, Scheme or other Lisp variants.
>
> Now I need to find some small programming challenges. The problems
> need to be precise, well defined and short. The solution must not
> take long (in Lisp, Scheme) because I don't have time until
> the end of the world, a couple of students in a class setting
> and about 1-2 hours. Maybe 4-5 programming questions. What
> I want to have is not the exact solution but capture the thought
> processes of those students, thus I will tell them (or their professor
> will tell) to note down every trial they make, not only the exact
> solution (if they can find it).
>
> My first candidate question is the famous permutation task, which
> can be expressed roughly as "given a set of elements, write a program
> that produces all the permutations of that set". My intuition and
> hypothesis is that the thought process of Scheme (or Lisp) programmer is
> going to be different than a non-Lisp programmer (maybe similar things can
> be said for a Prolog programmer but I don't have such participants
> for this study unfortunately).
>
> I'd be very glad if comp.lang.lisp participants can come up
> with small programming challenges having the characteristics
> described above that can help me distinguish between those
> Scheme-but-no-other-language knowing kids and another group
> of non-Lisp programmers. If the challenges seem a little bit complex
> but have easy and short solutions in Lisp/Scheme (contrasting the
> solutions in C, Java, Perl, etc.) I believe they can help me
> with this research.
>
> Thanks in advance.
>
>
>
One simple nice one is the subset sum problem, which is described at
http://en.wikipedia.org/wiki/Subset_sum_problem
In short, given a set A of integers and another integer I, find (if there is
any) a subset of A whose elements sum up to I. This one is NP-complete!
--
(+::+) oni (+::+)
(I already try to be as amusing as possible, my master!)
From: Emre Sevinc
Subject: Re: Help me come up with a few and simple programming challenges
Date:
Message-ID: <87irxnoip6.fsf@ileriseviye.org>
Onay Urfalioglu <·····@gmx.net> writes:
> Emre Sevinc wrote:
>
>>
>> Can programming languages really shape the ways we think
>> about solving problems?
>>
>> http://en.wikipedia.org/wiki/Sapir-Whorf_and_programming_languages
>>
>> What I want to do is gather some data for a comparative study. I have
>> a bunch of CS students who saw some Scheme programming but
>> no other programming language. And then it is easy to find
>> some programmers (close to the avg. age of the first group, which
>> is 19 years) who used C-like languages (C, C++, Java, Perl, PHP, etc.) but
>> not Lisp, Scheme or other Lisp variants.
>>
>> Now I need to find some small programming challenges. The problems
>> need to be precise, well defined and short. The solution must not
>> take long (in Lisp, Scheme) because I don't have time until
>> the end of the world, a couple of students in a class setting
>> and about 1-2 hours. Maybe 4-5 programming questions. What
>> I want to have is not the exact solution but capture the thought
>> processes of those students, thus I will tell them (or their professor
>> will tell) to note down every trial they make, not only the exact
>> solution (if they can find it).
>>
>> My first candidate question is the famous permutation task, which
>> can be expressed roughly as "given a set of elements, write a program
>> that produces all the permutations of that set". My intuition and
>> hypothesis is that the thought process of Scheme (or Lisp) programmer is
>> going to be different than a non-Lisp programmer (maybe similar things can
>> be said for a Prolog programmer but I don't have such participants
>> for this study unfortunately).
>>
> One simple nice one is the subset sum problem, which is described at
> http://en.wikipedia.org/wiki/Subset_sum_problem
> In short, given a set A of integers and another integer I, find (if there is
> any) a subset of A whose elements sum up to I. This one is NP-complete!
Thank you very much. The description is clear.
I'll examine this problem and check for possible implementations
in Lisp to compare with other languages and try to see if it
can lead to differences in student's thinking styles.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
> Now I need to find some small programming challenges. The
> problems need to be precise, well defined and short.
GO
The game of GO is played by placing black and white stones
on the intersections of a square grid of horizontal and
vertical lines. Two stones of the same colour are connected
if they are adjacent, horizontally or vertically. (not
diagonally, as is suggested by the absence of diagonal lines
from the markings on the playing surface).
There is a formal concept of a "group" of stones (all of the
same colour) that is used in the rules of the game. The
groups are the equivalence classes under the transitive
closure of the relation of connectedness. That is to say, if
A is next to B then A and B are in the same group, and also
if C and D are in the same group and D and E are in the same
group then C and E are in the same group.
The suggested puzzle: given a boolean array, indicating the
positions of one players pieces, print out a list of the
stones, in "groups" as defined by the rules of GO.
This is little more than the computation of the transitive
closure, so it is perhaps a test of book learning. On the
other hand it motivates the puzzle and makes it a little
more interesting for the students.
Egyptian fractions
express rational numbers as the sum of the reciprocals of
distinct integers. E.G.
2/3 = 1/2 + 1/6
3/4 = 1/2 + 1/4
2/5 = 1/3 + 1/15
Alan Crowe
Edinburgh
Scotland
From: Emre Sevinc
Subject: Re: Help me come up with a few and simple programming challenges
Date:
Message-ID: <871x4bnsi6.fsf@ileriseviye.org>
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
>> Now I need to find some small programming challenges. The
>> problems need to be precise, well defined and short.
>
> GO
>
> The game of GO is played by placing black and white stones
> on the intersections of a square grid of horizontal and
> vertical lines. Two stones of the same colour are connected
> if they are adjacent, horizontally or vertically. (not
> diagonally, as is suggested by the absence of diagonal lines
> from the markings on the playing surface).
Aaarrgghh, don't talk to me about it when I was beaten harshly
today on IGS! ;-)
> There is a formal concept of a "group" of stones (all of the
> same colour) that is used in the rules of the game. The
> groups are the equivalence classes under the transitive
> closure of the relation of connectedness. That is to say, if
> A is next to B then A and B are in the same group, and also
> if C and D are in the same group and D and E are in the same
> group then C and E are in the same group.
And when you don't take enough precautions, play too close
and tight you lose your so-called groups one by one... I always
have a nausea when they die...
> The suggested puzzle: given a boolean array, indicating the
> positions of one players pieces, print out a list of the
> stones, in "groups" as defined by the rules of GO.
Hmm, do you mean "find the coordinates which belong to a group?"
as if given array = [a2, b2, b3, g3, h7] tell that [a2, b2, b3]
forms a group?
> This is little more than the computation of the transitive
> closure, so it is perhaps a test of book learning. On the
> other hand it motivates the puzzle and makes it a little
> more interesting for the students.
Certainly putting it in the context of a popular
game (even though GO is not that popular in Turkey) may
be a motivating factor.
However I'm not sure if this problem is going to
create a difference between Lisp-only students and
the ones no-Lisp-but-C-C++-Java-Perl-etc. experience.
(I must think harder about this one).
> Egyptian fractions
>
> express rational numbers as the sum of the reciprocals of
> distinct integers. E.G.
>
> 2/3 = 1/2 + 1/6
> 3/4 = 1/2 + 1/4
> 2/5 = 1/3 + 1/15
Another nice problem! Thank you very much.
I'll take that into account, too.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
From: Peter Seibel
Subject: Re: Help me come up with a few and simple programming challenges
Date:
Message-ID: <m2mzmzqhw0.fsf@gigamonkeys.com>
Emre Sevinc <·····@bilgi.edu.tr> writes:
> Alan Crowe <····@cawtech.freeserve.co.uk> writes:
>
>>> Now I need to find some small programming challenges. The
>>> problems need to be precise, well defined and short.
>>
>> GO
>>
>> The game of GO is played by placing black and white stones
>> on the intersections of a square grid of horizontal and
>> vertical lines. Two stones of the same colour are connected
>> if they are adjacent, horizontally or vertically. (not
>> diagonally, as is suggested by the absence of diagonal lines
>> from the markings on the playing surface).
>
> Aaarrgghh, don't talk to me about it when I was beaten harshly
> today on IGS! ;-)
>
>
>> There is a formal concept of a "group" of stones (all of the
>> same colour) that is used in the rules of the game. The
>> groups are the equivalence classes under the transitive
>> closure of the relation of connectedness. That is to say, if
>> A is next to B then A and B are in the same group, and also
>> if C and D are in the same group and D and E are in the same
>> group then C and E are in the same group.
>
> And when you don't take enough precautions, play too close
> and tight you lose your so-called groups one by one... I always
> have a nausea when they die...
>
>
>> The suggested puzzle: given a boolean array, indicating the
>> positions of one players pieces, print out a list of the
>> stones, in "groups" as defined by the rules of GO.
>
> Hmm, do you mean "find the coordinates which belong to a group?"
> as if given array = [a2, b2, b3, g3, h7] tell that [a2, b2, b3]
> forms a group?
>
>
>> This is little more than the computation of the transitive
>> closure, so it is perhaps a test of book learning. On the
>> other hand it motivates the puzzle and makes it a little
>> more interesting for the students.
>
> Certainly putting it in the context of a popular
> game (even though GO is not that popular in Turkey) may
> be a motivating factor.
>
> However I'm not sure if this problem is going to
> create a difference between Lisp-only students and
> the ones no-Lisp-but-C-C++-Java-Perl-etc. experience.
> (I must think harder about this one).
All the more reason to do it--either you'll be surprised by the result
(best case) or, worst case, you'll have an interesting data point:
this particular problem is solved in pretty much the same way
regardless of language. However I suspect you'll actually get quite
different solutions.
If you wanted to push things a bit, ask them to implement a basic Go
engine--not something that plays go but something that manages a game,
accepting moves, determining if they are legal, and then modifying the
state of the board as appropriate, i.e. taking off killed groups. (You
can leave out Ko-detection if you want to make their lives a bit
easier.) It's not too hard but it's complex enough to allow for lots
of different approaches that will take folks into wildly different
points in the solution space.
A couple other interesting problems:
The Impossible Book:
See: <http://bridge.thomasoandrews.com/impossible/algorithm.html>
This one requires bignums which is fine for Common Lisp, Java, and
Python. You'll need to provide a arbitrary precision intereg lib for
C++.
Fischer Random Chess:
In a variant of chess called Fischer Random Chess, you start the
board in a (partially) random position according to the following
rules. You place the pawns in their normal starting positions. Then
you place the white pieces in the first rank in a random arrangement
excepting that:
o The bishops are each on different colored squares.
o The king is somewhere between the two rooks.
Then the black pieces are placed in there corresponding places on
the other side of the board.
Write a function (method, procedure, whatever) that returns a
randomly generated legal arrangement of the eight white pieces.
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Emre,
How about a Solitaire game? Not a game for a player, but a program that
plays Solitaire, as found on every Windows system.
There are several data structures there, and some heuristics for playing
strategy. Most people are probably familiar with the game, or can become
so very quickly.
Several questions can be asked:
Given a shuffled deck, can your program find a winning series of moves?
Given a series of decks, how many games can your program win?
The output could be graphical or ascii, or none, for max speed.
Sure, Solitaire is sort of a tedious time killer, but there are
interesting programming challenges there.
Michael
Emre Sevinc wrote:
> Can programming languages really shape the ways we think
> about solving problems?
Absolutely. I am stuck in the .NET world right now and I find myself
thinking "This would be so much easier in Lisp." or "Damn it! Lisp can
do this! Why not C#?!"
> Now I need to find some small programming challenges. The problems
> need to be precise, well defined and short. The solution must not
How about "Calculate the area of the Mandelbrot set?"
I was doing some research for a little Mandelbrot-picture generator and
I discovered that mathematicians do things like that. After a couple of
nights of after-dinner-hacking I got a pretty good approximation. More
importantly, it was fun.
--dennis
From: David Steuber
Subject: Re: Help me come up with a few and simple programming challenges
Date:
Message-ID: <8764tmqkgf.fsf@david-steuber.com>
Dennis Dunn <·····@insight.rr.com> writes:
> How about "Calculate the area of the Mandelbrot set?"
>
> I was doing some research for a little Mandelbrot-picture generator
> and I discovered that mathematicians do things like that. After a
> couple of nights of after-dinner-hacking I got a pretty good
> approximation. More importantly, it was fun.
What sort of precision did you work out to? I strongly suspect that
the area is an incalculable number, so you can only ever aproximate
it. I would guess that it is also transcendental but I can't prove
that (I lack the math fu at present. Perhaps I can learn it.).
What would be really cool is a function that is faster than the
standard escape function that a: tells you if you are in the set and
b: tells you the escape value when you are not. My fractal movie
xenos-xoom.mov took a very long time to compute because the region I
chose had such long escape times outside of the set.
--
My .sig file sucks. Can anyone recommend a better one?
Hi David,
>
> What sort of precision did you work out to? I strongly suspect that
I played with it until my results agreed with my reference to about 4 or
5 decimal places. Basically until I decided that I understood the
problem well enough and moved on to other things. To tell you the
truth, I didn't think about "precision" at all. That's one reason I
like to do my recreational/exploratory programming in Lisp, I don't need
to worry about "double" or "long" or how many bits a foo has.
>
> What would be really cool is a function that is faster than the
> standard escape function that a: tells you if you are in the set and
> b: tells you the escape value when you are not.
This site might be of interest to you, the "Mandelbrot Encyclopedia."
http://www.mrob.com/pub/muency.html
--dennis
Dennis Dunn wrote:
> This site might be of interest to you, the "Mandelbrot Encyclopedia."
>
> http://www.mrob.com/pub/muency.html
nice site. BTW: text-only is possible with some Lisp, too, but would need
some more code for choosing the character, which matches the form of the
mandelbrot image more closely, like the text-only picture from the website.
(loop for y from -1 to 1.1 by 0.1 do
(loop for x from -2 to 1 by 0.04 do
(loop with a = (complex x y)
for z = a then (+ (* z z) a)
while (< (abs z) 2)
for c from 126 above 32
finally (princ (code-char c))))
(terpri))
~~~~~~~~~~~~~}}}}}}}}}}}}}}}}}}}}||||||||{{{zyvrwuW{|||||}}}}}}~~~~~~~~~~~~
~~~~~~~~~~}}}}}}}}}}}}}}}}}}}}|||||||||{{{zyxwoaqwxz{{{|||||}}}}}}~~~~~~~~~
~~~~~~~~}}}}}}}}}}}}}}}}}}}|||||||||{{zzzyxvn Knwyz{{{{||||}}}}}}~~~~~~~
~~~~~~}}}}}}}}}}}}}}}}}}||||||||{{zyxuxxxwvuq svwwyzzzyr{||}}}}}}}~~~~~
~~~~}}}}}}}}}}}}}}}}}|||||{{{{{zzzxt> qf pttfqeqz{|}}}}}}}}~~~
~~~}}}}}}}}}}}}}}|||{{{{{{{{{zzzywotn atyz{||}}}}}}}}~~
~~}}}}}}}}}||||{{zwvyyyyyyyyyyyxvsP swvz{||}}}}}}}}~
~}}}}|||||||{{{{zyxvpN[ur]spvwwvi qxz{|||}}}}}}}}
~}||||||||{{{{{zyytun qq avz{|||}}}}}}}}
~||||||{zzzzyyxtroqb a xz{{|||}}}}}}}}
·@G::# 6# ( pvxyz{{||||}}}}}}}
~||||||{zzzzyyxtroqb a xz{{|||}}}}}}}}
~}||||||||{{{{{zyytun qq avz{|||}}}}}}}}
~}}}}|||||||{{{{zyxvpN[ur]spvwwvi qxz{|||}}}}}}}}
~~}}}}}}}}}||||{{zwvyyyyyyyyyyyxvsP swvz{||}}}}}}}}~
~~~}}}}}}}}}}}}}}|||{{{{{{{{{zzzywotn atyz{||}}}}}}}}~~
~~~~}}}}}}}}}}}}}}}}}|||||{{{{{zzzxt> qf pttfqeqz{|}}}}}}}}~~~
~~~~~~}}}}}}}}}}}}}}}}}}||||||||{{zyxuxxxwvuq svwwyzzzyr{||}}}}}}}~~~~~
~~~~~~~~}}}}}}}}}}}}}}}}}}}|||||||||{{zzzyxvn Knwyz{{{{||||}}}}}}~~~~~~~
~~~~~~~~~~}}}}}}}}}}}}}}}}}}}}|||||||||{{{zyxwoaqwxz{{{|||||}}}}}}~~~~~~~~~
~~~~~~~~~~~~~}}}}}}}}}}}}}}}}}}}}||||||||{{{zyvrwuW{|||||}}}}}}~~~~~~~~~~~~
~~~~~~~~~~~~~~~~~}}}}}}}}}}}}}}}}}}}}}|||||{zmt{{{||||}}}}}~~~~~~~~~~~~~~~~
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Hi!!!
Maybe a nice problem would be this:
If you take a fairly big number of digits of pi, you can see that:
a) There are as many "0"s as "1"s as "2"s...."9"s
b) There are as many "00"s as "01"s as "02"s..."99"s
c) As many "000"s as...."999"s
and so on.
(http://www.lbl.gov/Science-Articles/Archive/pi-random.html)
The problem would be, of course, to "prove" it with a program :-)
From: Emre Sevinc
Subject: Re: Help me come up with a few and simple programming challenges
Date:
Message-ID: <87wtlxm2pc.fsf@ileriseviye.org>
"LuisGLopez" <············@gmail.com> writes:
> Hi!!!
>
> Maybe a nice problem would be this:
> If you take a fairly big number of digits of pi, you can see that:
> a) There are as many "0"s as "1"s as "2"s...."9"s
> b) There are as many "00"s as "01"s as "02"s..."99"s
> c) As many "000"s as...."999"s
> and so on.
> (http://www.lbl.gov/Science-Articles/Archive/pi-random.html)
Thanks for the URL, nice article but...
> The problem would be, of course, to "prove" it with a program :-)
Wouldn't be this misleading for the young students? I mean
the word "prove". On the other hand, telling them something
like
1- Write a function to produce as many digits of PI as
you want.
2- Count the number of 0's compared to 1s, 2s, ... and
then count the number of 000s compared to 999s, etc.
But then again I have to think about it and see if
this creates a noticable difference between a Lisp
solution and a C/C++/Java/Perl/PHP imperative style
solution.
Thanks again.
Happy hacking,
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr
Here a sugestion for a problem I'm starting on (paster from another
thread)
Something to get the class going:
In words the kind of functions I'm looking for are:
(substitute-all-atoms-in-tree tree oldatom &restatoms atoms)
===>
(substitute-nth-atom-in-tree tree n oldatom &restatoms atoms)
,
counting n in order atoms appear in tree
(count-numberof-atoms-in-tree tree)
(dedupe-a-list-of-trees list) where each list element is a
tree, is
any tree appears >1 then keep only one
(dedupe-a-list-of-trees-considering-only-structure list) where
structure is irrespective of contents of leafs so (1 (2 3) == (a (b d)
but (1 (2 3)) /= (a (b (c)))
; (this would probably use dedupe-a-list-of-trees with something list
a 'treestructure' function applied, which would turn all the atoms to
the same constant).
And this tricky one :-)
(create-a-list-of-all-trees-resulting-from-cmbinatorial-replacements-of-each-'oldatom'-with-either-'new1''new2'-OR-'new3'-in-the-tree
tree oldatom new1 new2 new3)
as en example it would behave list this:
(caloatrfcroeowennonitt '(1 2 (1)) 1 a b c) ===>
;;;let me thing about this one.... :-)
(
(a b 2 (a b))
(a b 2 (c ))
(c2 (a b))
(c2 (c ))
)
Why all this haste you might ask, I'm hoping to create a combinatorial
search through the space of all possible function definitions , testing
each one against a 'input output pair' , (lots will be syntactically
incorrect, but that's ok, we'll just escape with :error... I hope, and
ignore them) later adding some evolutionary ideas to cut the
combinatorial search... as inspired by
http://www-ia.hiof.no/~rolando /adate_intro.html
Kind regards.
G
> Now I need to find some small programming challenges. The problems
> need to be precise, well defined and short. The solution must not
> take long (in Lisp, Scheme) because I don't have time until
> the end of the world, a couple of students in a class setting
> and about 1-2 hours. Maybe 4-5 programming questions. What
> I want to have is not the exact solution but capture the thought
> processes of those students, thus I will tell them (or their professor
> will tell) to note down every trial they make, not only the exact
> solution (if they can find it).
May take a bit longer than an hour or two, but solving Sudokus seem to
be very popular at the moment. I recently took part in a language
battle at work where we used different programming languages (C, Python
and Java) to solve sudokus. And yes, we did implement different
algorithms and we thought about the problem in completely different
ways.
BR
Johan Lindberg
·····@pulp.se
On Sat, 27 Aug 2005 18:34:55 +0300, Emre Sevinc <·····@bilgi.edu.tr> tried to
confuse everyone with this message:
>Now I need to find some small programming challenges. The problems
>need to be precise, well defined and short.
Given a 6-digit number, arrange arithmetic operations and parens between it's
digits so the result is 100 (or any arbitrary N). Optionally: print all of
solutions.
>(nums 266121 100)
"-(2-(6*((6+12)-1)))" ;;That's one of the two different solutions btw. This
number is also notorious that neither me, nor my roommate could find a solution
before the program did it - so this is the hardest number known to me that has
the solution.
This was the first program I coded in Lisp. It is kind of slow because it conses
a tree that describes what to do, and then calculates its result. I think the C
algorithm would be completely different (the operations would be applied to
digits right away).
--
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru http://grue3.tripod.com |
| k || PWNZ J00 || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
On Fri, 09 Sep 2005 16:37:40 GMT, <····@mail.ru> wrote:
>
>
> On Sat, 27 Aug 2005 18:34:55 +0300, Emre Sevinc <·····@bilgi.edu.tr> tried to
> confuse everyone with this message:
>
>>Now I need to find some small programming challenges. The problems
>>need to be precise, well defined and short.
>
> Given a 6-digit number, arrange arithmetic operations and parens between it's
> digits so the result is 100 (or any arbitrary N). Optionally: print all of
> solutions.
>
>(nums 266121 100)
> "-(2-(6*((6+12)-1)))" ;;That's one of the two different solutions btw. This
your answer is not a lisp expression?
> number is also notorious that neither me, nor my roommate could find a solution
> before the program did it - so this is the hardest number known to me that has
> the solution.
>
> This was the first program I coded in Lisp. It is kind of slow because it conses
> a tree that describes what to do, and then calculates its result. I think the C
> algorithm would be completely different (the operations would be applied to
> digits right away).
This should be a classic first problem for beginning Genetic Algorithm
students. Much more interesting than ONES or HELLO-WORLD. You might
want to look at Kozas 'lilgp' or whatever he called the GPP code.
--
You can always tell a really good idea by the enemies it makes.
On Fri, 9 Sep 2005 14:47:11 -0700, GP lisper <········@CloudDancer.com> tried to
confuse everyone with this message:
>On Fri, 09 Sep 2005 16:37:40 GMT, <····@mail.ru> wrote:
>>
>>(nums 266121 100)
>> "-(2-(6*((6+12)-1)))" ;;That's one of the two different solutions btw. This
>
>your answer is not a lisp expression?
It's printed in a human-readable way :)
--
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru http://grue3.tripod.com |
| k || PWNZ J00 || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
Hi!
Maybe this would be useful:
http://en.wikipedia.org/wiki/McCarthy_91_function
It's a simple recursive function, and the webpage shows solutions in
lisp and java, to compare :-)
From: Emre Sevinc
Subject: Re: Help me come up with a few and simple programming challenges
Date:
Message-ID: <87br2ym0yj.fsf@ileriseviye.org>
"LuisGLopez" <············@gmail.com> writes:
> Hi!
>
> Maybe this would be useful:
> http://en.wikipedia.org/wiki/McCarthy_91_function
>
> It's a simple recursive function, and the webpage shows solutions in
> lisp and java, to compare :-)
Thanks for the URL. It has a very simple and clear
definition and I think it is a good candidate to differentiate
between Scheme-only students and Java-only students.
--
Emre Sevinc
eMBA Software Developer Actively engaged in:
http:www.bilgi.edu.tr http://ileriseviye.org
http://www.bilgi.edu.tr http://fazlamesai.net
Cognitive Science Student http://cazci.com
http://www.cogsci.boun.edu.tr