Well, no. This is not a particularly "nice vehicle for programmers to
familiarise themselves with recursion".
To start with, a quick web search turns up
https://en.wikipedia.org/wiki/Wheat_and_chessboard_problem.
Problems where the result depend on previous results often fall into
the "dynamic programming" category,
with
Object subclass: #ChessBoard
instanceVariableNames: 'board sum'
class methods for: 'instance creation'
new: n
^self new initialize: n
methods for: 'initializing;
initialize: n
board := Array new: n squared.
board at: 1 put: 1.
2 to: board size do: [:i |
board at: i put: (board at: i - 1) * 2].
sum := 0.
board do: [:each |
sum := sum + each].
^self
methods for: 'accessing'
squareAt: i
^board at: i
total
^sum
being the most obvious elementary implementation. The very
description of the problem
suggests an iterative approach.
To find a nice problem for recursion, you have to find one where
tabulation is *not* a
good strategy.
On Mon, 6 Jan 2020 at 08:06, Ben Coman <b...@openinworld.com> wrote:
>
> Hi Richard,
>
> Just fyi, the aim of Exercism is not to teach programming. Its aim is for
> experienced programmers to fast-start in new languages.
> It just happens to that new programmers also use Exercism and there is some
> catering in the exercise text for this.
>
> The grains exercise provides a nice vehicle for programmers to familiarize
> themselves with recursion in Pharo,
> and the hint for the exercise says "These kinds of problems (where an answer
> is dependent on a previous) one are often called recursion"
> which is why Roelof is approaching the problem this way.
>
> That said, any solution will do. Your advice on alternative considerations
> is insightful and always good to read.
>
> cheers -ben
>
> On Mon, 6 Jan 2020 at 00:25, Richard O'Keefe <rao...@gmail.com> wrote:
>>
>> I did not ask why you were validating input.
>> I asked about why you *repeatedly* validated input.
>>
>> Think of it this way:
>> publicMethod: arg1 also: arg2
>> ... check arg1 ...
>> ... check arg2 ...
>> ^self privateMethod: arg1 also: arg2
>>
>> privateMethod: arg1 also: arg2
>> ... trust that arg1 and arg2 are valide ...
>> ... recursive calls use #privateMethod:andAlso: ...
>> ... not #publicMethod:andAlso: and must ensure ...
>> ... that arguments are valid by construction ...
>>
>> In my solution to the "Grains" exercism, I have
>> atSquare: n -- checks its argument
>> total ^(1 bitShift: 64) - 1
>> You are required to implement these two methods, true.
>> You are NOT required to implement #total by calling #atSquare:.
>> Not even once. Nor is #atSquare: required to be recursive.
>>
>> On Mon, 6 Jan 2020 at 02:05, Roelof Wobben <r.wob...@home.nl> wrote:
>> >
>> > Hello Ricard.
>> >
>> > You mean when I calcualate the total of a board.
>> > That is because on when I had to calculate the number of a particular
>> > field there were tests where the number was lower then zero or higher
>> > then 64 which makes no sense.
>> >
>> > But im open for a solution where on a particular field I could check for
>> > that and for the total I do not need that part.
>> >
>> > Roelof
>> >
>> >
>> >
>> > Op 5-1-2020 om 13:58 schreef Richard O'Keefe:
>> > > Time microsecondsToRun: [
>> > > |n|
>> > > n := (2 raisedToInteger: 8 * 8) - 1.
>> > > Transcript
>> > > nextPutAll: 'The number of grains on an 8x8 chessboard is ';
>> > > print: n; cr; endEntry].
>> > > <PRINT-IT>
>> > > On my laptop, this reports 194 microseconds.
>> > >
>> > > Why would you use recursion, anyway?
>> > >
>> > > Time microsecondsToRun: [
>> > > |n|
>> > > n := (1 to: 8 * 8) inject: 0 into: [:acc :each | acc+acc+1].
>> > > Transcript
>> > > nextPutAll: 'The number of grains on an 8x8 chessboard is ';
>> > > print: n; cr; endEntry].
>> > > <PRINT-IT>
>> > > On the same laptop, this reports 118 microseconds.
>> > >
>> > > One of the lessons of 'functional' languages, promptly adopted by
>> > > Smalltalk, is
>> > > to encapsulate control structures into reusable methods, such as
>> > > #inject:into:,
>> > > more commonly known as `foldl` in functional languages. It's then none
>> > > of
>> > > my business whether such a method works by recursion, iteration, or gangs
>> > > of otherwise seasonally unemployed Christmas elves.
>> > >
>> > > In my own Smalltalk library,
>> > > (GeometricSeries new: 64 from: 1 byFactor: 2) sum
>> > > only takes 15 microseconds.
>> > >
>> > > I do note that you are calling validateInput repeatedly. Why?
>> > >
>> > >
>> > > On Sun, 5 Jan 2020 at 07:41, Roelof Wobben via Pharo-users
>> > > <pharo-users@lists.pharo.org> wrote:
>> > >> Oke,
>> > >>
>> > >> So I can better not use recursion for this problem if I understand you
>> > >> well, Richard.
>> > >>
>> > >> Roelof
>> > >>
>> > >>
>> > >>
>> > >> Op 4-1-2020 om 19:02 schreef Richard Sargent:
>> > >>
>> > >> On Sat, Jan 4, 2020 at 9:47 AM Roelof Wobben via Pharo-users
>> > >> <pharo-users@lists.pharo.org> wrote:
>> > >>> Hello,
>> > >>>
>> > >>> For a exercism challenge I need to calculate the total grains on a
>> > >>> chessboard.
>> > >>> So I did :
>> > >>>
>> > >>> atSquare: anInteger
>> > >>> self validateInput: anInteger.
>> > >>> ^ anInteger = 1
>> > >>> ifTrue: [ 1 ]
>> > >>> ifFalse: [ 2 * (self atSquare: anInteger - 1) ]
>> > >>>
>> > >>>
>> > >>> but when I run the tests , the vm seems to be not responsive for some 4
>> > >>> - 5 seconds.
>> > >>>
>> > >>> Is there a way I can use this code and take care that the vm stays
>> > >>> responsive.
>> > >>
>> > >> What do you want the VM to do in addition to calculating that sum while
>> > >> it is calculating that sum?
>> > >>
>> > >>
>> > >> The best way to keep the VM responsive is to take a page from Gauss'
>> > >> notebook and pay attention to the numbers[1]. Let's consider the first
>> > >> four squares and extrapolate from there.
>> > >>
>> > >> In binary, the squares hold the following grains: 2r1, 2r10, r2100, and
>> > >> 2r1000. When we add them up, we get 2r1111. If we use Gauss' tricks, we
>> > >> can notice that 2r1111 is equal to 2r10000 - 1. So, the sum of the
>> > >> grains on the first 4 squares is 2^5 - 1. You can easily generalize
>> > >> that pattern, of course. Then your program can calculate the answer
>> > >> quickly.
>> > >>
>> > >>
>> > >> [1] The story goes that Gauss' teacher was frustrated with his
>> > >> student's abilities and set him a challenge to occupy him for some
>> > >> time: sum the numbers from 1 through 100. Gauss immediately answered
>> > >> 5,050, much to his teacher's chagrin.
>> > >>
>> > >>> Regards,
>> > >>>
>> > >>> Roelof
>> > >>>
>> > >>>
>> >
>>
