Smalltalk › Pharo › Pharo Smalltalk Users

Little challenges for a friday evening

_‹ Previous Topic Next Topic _›

Classic

List

Threaded

17 messages Options

stepharo

Little challenges for a friday evening

Hi

I'm checking how I would implement an isogram checker

'Pharo' isogram

>>> true

because it contains only single letter.

I got a stupid bag drivent implementation but I will do another better
and faster.

Stef

PS: after I will do anagram and pangram to have the family of gram
checks (this is for a book).

Sven Van Caekenberghe-2

Re: Little challenges for a friday evening

[ :string | string size = string asSet size ] value: 'Pharo'.

>>> true

[ :string | string size = string asSet size ] value: 'Pharoo'.

>>> false

String>>#isIsogram
^ self size = self asSet size

?

> On 10 Nov 2016, at 22:19, stepharo <[hidden email]> wrote:
>
> Hi
>
> I'm checking how I would implement an isogram checker
>
> 'Pharo' isogram
>
> >>> true
>
> because it contains only single letter.
>
> I got a stupid bag drivent implementation but I will do another better and faster.
>
> Stef
>
> PS: after I will do anagram and pangram to have the family of gram checks (this is for a book).
>
>

CyrilFerlicot

Re: Little challenges for a friday evening

Le 10/11/2016 à 23:09, Sven Van Caekenberghe a écrit :

> [ :string | string size = string asSet size ] value: 'Pharo'.
>
>>>> true
>
> [ :string | string size = string asSet size ] value: 'Pharoo'.
>
>>>> false
>
> String>>#isIsogram
> ^ self size = self asSet size
>
> ?
>

'Pharop' size = 'Pharop' asSet size

>>> true

Does it count? If upper-case counts you will need to do `^ self size =
self asLowercase asSet size` :)

--
Cyril Ferlicot

http://www.synectique.eu

2 rue Jacques Prévert 01,
59650 Villeneuve d'ascq France

signature.asc (836 bytes) Download Attachment

Sven Van Caekenberghe-2

Re: Little challenges for a friday evening

you're right, should probably be case insensitive.

> On 10 Nov 2016, at 23:14, Cyril Ferlicot D. <[hidden email]> wrote:
>
> Le 10/11/2016 à 23:09, Sven Van Caekenberghe a écrit :
>> [ :string | string size = string asSet size ] value: 'Pharo'.
>>
>>>>> true
>>
>> [ :string | string size = string asSet size ] value: 'Pharoo'.
>>
>>>>> false
>>
>> String>>#isIsogram
>> ^ self size = self asSet size
>>
>> ?
>>
>
> 'Pharop' size = 'Pharop' asSet size
>
>>>> true
>
> Does it count? If upper-case counts you will need to do `^ self size =
> self asLowercase asSet size` :)
>
> --
> Cyril Ferlicot
>
> http://www.synectique.eu
>
> 2 rue Jacques Prévert 01,
> 59650 Villeneuve d'ascq France

Henrik Nergaard-2

Re: Little challenges for a friday evening

In reply to this post by Sven Van Caekenberghe-2

String>>isIsogram

1 to: self size -1 do: [ :ix |
(self
findString: (self at: ix) asString
startingAt: ix +1
caseSensitive: false
) ~~ 0 ifTrue: [ ^ false ]
].

^ true

-----Original Message-----
From: Pharo-users [mailto:[hidden email]] On Behalf Of Sven Van Caekenberghe
Sent: Thursday, November 10, 2016 11:10 PM
To: Any question about pharo is welcome <[hidden email]>
Subject: Re: [Pharo-users] Little challenges for a friday evening

[ :string | string size = string asSet size ] value: 'Pharo'.

>>> true

[ :string | string size = string asSet size ] value: 'Pharoo'.

>>> false

String>>#isIsogram
^ self size = self asSet size

?

Ben Coman

Re: Little challenges for a friday evening

In reply to this post by Sven Van Caekenberghe-2

First I've heard of an isogram. Wikipedia [1] is ambiguous. Are you
considering only single occurrence of letters, or also equal
occurrence of letters.

I like Sven's answer best, but just as an exercise I thought of an alternative.

String>>#isIsogram
| letters |
letters := Dictionary new.
self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].

On Fri, Nov 11, 2016 at 6:19 AM, Sven Van Caekenberghe <[hidden email]> wrote:
> you're right, should probably be case insensitive.

Or maybe that is overly restrictive. A case sensitive #isogram would
have the flexibility to used both ways...

'Pharop' isogram
'Pharop' asLowercase isogram

Now a philosophical question (not that its practical to change anything),
but intuitively I tried using #lowercase before searching and finding
#asLowercase,
so I am wondering...
I feel #asXXX methods are there to change the 'type' of an object,
while #asLowercase isn't changing the type, but returning a
transformation much like...

'Pharop' sorted

We don't say 'Pharop' asSorted

cheers -ben

>
>> On 10 Nov 2016, at 23:14, Cyril Ferlicot D. <[hidden email]> wrote:
>>
>> Le 10/11/2016 à 23:09, Sven Van Caekenberghe a écrit :
>>> [ :string | string size = string asSet size ] value: 'Pharo'.
>>>
>>>>>> true
>>>
>>> [ :string | string size = string asSet size ] value: 'Pharoo'.
>>>
>>>>>> false
>>>
>>> String>>#isIsogram
>>> ^ self size = self asSet size
>>>
>>> ?
>>>
>>
>> 'Pharop' size = 'Pharop' asSet size
>>
>>>>> true
>>
>> Does it count? If upper-case counts you will need to do `^ self size =
>> self asLowercase asSet size` :)

stepharo

Re: Little challenges for a friday evening

Le 11/11/16 à 01:09, Ben Coman a écrit :

> First I've heard of an isogram. Wikipedia [1] is ambiguous. Are you
> considering only single occurrence of letters, or also equal
> occurrence of letters.
>
> I like Sven's answer best, but just as an exercise I thought of an alternative.
>
> String>>#isIsogram
> | letters |
> letters := Dictionary new.
> self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].

Yes I did that one too and I was surprised because it was as slow as the
bag implementation.

>
>
> On Fri, Nov 11, 2016 at 6:19 AM, Sven Van Caekenberghe <[hidden email]> wrote:
>> you're right, should probably be case insensitive.
> Or maybe that is overly restrictive. A case sensitive #isogram would
> have the flexibility to used both ways...
>
> 'Pharop' isogram
> 'Pharop' asLowercase isogram
>
>
> Now a philosophical question (not that its practical to change anything),
> but intuitively I tried using #lowercase before searching and finding
> #asLowercase,
> so I am wondering...
> I feel #asXXX methods are there to change the 'type' of an object,
> while #asLowercase isn't changing the type, but returning a
> transformation much like...
>
> 'Pharop' sorted
>
> We don't say 'Pharop' asSorted
>
> cheers -ben
>
>>> On 10 Nov 2016, at 23:14, Cyril Ferlicot D. <[hidden email]> wrote:
>>>
>>> Le 10/11/2016 à 23:09, Sven Van Caekenberghe a écrit :
>>>> [ :string | string size = string asSet size ] value: 'Pharo'.
>>>>
>>>>>>> true
>>>> [ :string | string size = string asSet size ] value: 'Pharoo'.
>>>>
>>>>>>> false
>>>> String>>#isIsogram
>>>> ^ self size = self asSet size
>>>>
>>>> ?
>>>>
>>> 'Pharop' size = 'Pharop' asSet size
>>>
>>>>>> true
>>> Does it count? If upper-case counts you will need to do `^ self size =
>>> self asLowercase asSet size` :)
>

stepharo

Re: Little challenges for a friday evening

In reply to this post by Henrik Nergaard-2

Cool

I will add it to my collection of solutions and I guess that this one is
the fastest but I should check first :)

Le 11/11/16 à 00:23, Henrik Nergaard a écrit :

> String>>isIsogram
>
> 1 to: self size -1 do: [ :ix |
> (self
> findString: (self at: ix) asString
> startingAt: ix +1
> caseSensitive: false
> ) ~~ 0 ifTrue: [ ^ false ]
> ].
>
> ^ true
>
> -----Original Message-----
> From: Pharo-users [mailto:[hidden email]] On Behalf Of Sven Van Caekenberghe
> Sent: Thursday, November 10, 2016 11:10 PM
> To: Any question about pharo is welcome <[hidden email]>
> Subject: Re: [Pharo-users] Little challenges for a friday evening
>
> [ :string | string size = string asSet size ] value: 'Pharo'.
>
>>>> true
> [ :string | string size = string asSet size ] value: 'Pharoo'.
>
>>>> false
> String>>#isIsogram
> ^ self size = self asSet size
>
> ?
>
>> On 10 Nov 2016, at 22:19, stepharo <[hidden email]> wrote:
>>
>> Hi
>>
>> I'm checking how I would implement an isogram checker
>>
>> 'Pharo' isogram
>>
>>>>> true
>> because it contains only single letter.
>>
>> I got a stupid bag drivent implementation but I will do another better and faster.
>>
>> Stef
>>
>> PS: after I will do anagram and pangram to have the family of gram checks (this is for a book).
>>
>>
>
>
>

stepharo

Re: Little challenges for a friday evening

In reply to this post by Henrik Nergaard-2

[ [ [
[ GramChecker new
isIsogramBag: 'ALTRUISME'] bench '99,720 per second'
] ] ]

[ [ [
[ GramChecker new
isIsogram2Dict: 'ALTRUISME'] bench '137,937 per second'
]]]

[ [ [
[ GramChecker new
isIsogramSet: 'ALTRUISME'] bench '390,887 per second'
]]]

[ [ [
[ GramChecker new
isIsogramHenrik: 'ALTRUISME'] bench '570,193 per second'
]]]

I will transform that as method extension and send the code around.

Then I will try pangram :)

Le 11/11/16 à 00:23, Henrik Nergaard a écrit :

Damien Pollet-2

Re: Little challenges for a friday evening

In reply to this post by stepharo

On 11 November 2016 at 12:02, stepharo <[hidden email]> wrote:

String>>#isIsogram
| letters |
letters := Dictionary new.
self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].

Yes I did that one too and I was surprised because it was as slow as the bag implementation.

Anyone tried replacing the dictionary with an array of 26 booleans and indexing based on ascii, or even a SmallInteger and bit shifting?

Henrik Nergaard-2

Re: Little challenges for a friday evening

isIsogram

| i |

i := 0.

self asLowercase do: [ :char |

| val |

val := (char asInteger - 96).

(val between: 1 and: 26) ifFalse: [ ^ false ].

(i bitAt: val ) == 1 ifTrue: [ ^ false ].

i bitAt: val put: 1

^ true

An interesting observation here is that if #asLowercase is moved to each character instead “val := (char asLowercase asInteger - 96).” Then it leads to a 4-5x performance loss .

From: Pharo-users [mailto:[hidden email]] On Behalf Of Damien Pollet
Sent: Friday, November 11, 2016 4:14 PM
To: Any question about pharo is welcome <[hidden email]>
Subject: Re: [Pharo-users] Little challenges for a friday evening

On 11 November 2016 at 12:02, stepharo <[hidden email]> wrote:

String>>#isIsogram
| letters |
letters := Dictionary new.
self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].

Yes I did that one too and I was surprised because it was as slow as the bag implementation.

Anyone tried replacing the dictionary with an array of 26 booleans and indexing based on ascii, or even a SmallInteger and bit shifting?

Richard Sargent

Re: Little challenges for a friday evening

Administrator

Henrik Nergaard-2 wrote

isIsogram

| i |

i := 0.

self asLowercase do: [ :char |
| val |
val := (char asInteger - 96).

"Don't bother with #asLowercase and its attendant overhead."
val := (char asInteger bitAnd: 2r11011111) - 16r40.

(val between: 1 and: 26) ifFalse: [ ^ false ].
(i bitAt: val ) == 1 ifTrue: [ ^ false ].
i bitAt: val put: 1
].

^ true

An interesting observation here is that if #asLowercase is moved to each character instead “val := (char asLowercase asInteger - 96).” Then it leads to a 4-5x performance loss .

From: Pharo-users [mailto:[hidden email]] On Behalf Of Damien Pollet
Sent: Friday, November 11, 2016 4:14 PM
To: Any question about pharo is welcome <[hidden email]>
Subject: Re: [Pharo-users] Little challenges for a friday evening

On 11 November 2016 at 12:02, stepharo <[hidden email]<mailto:[hidden email]>> wrote:
String>>#isIsogram
| letters |
letters := Dictionary new.
self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].
Yes I did that one too and I was surprised because it was as slow as the bag implementation.

Anyone tried replacing the dictionary with an array of 26 booleans and indexing based on ascii, or even a SmallInteger and bit shifting?

stepharo

Re: Little challenges for a friday evening

In reply to this post by Damien Pollet-2

I pair programmed with my middle son and we got the following chapter.

Now going to bed :)

Le 11/11/16 à 16:13, Damien Pollet a écrit :

On 11 November 2016 at 12:02, stepharo <[hidden email]> wrote:

String>>#isIsogram
| letters |
letters := Dictionary new.
self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].

Yes I did that one too and I was surprised because it was as slow as the bag implementation.

Anyone tried replacing the dictionary with an array of 26 booleans and indexing based on ascii, or even a SmallInteger and bit shifting?

GramKatas.pdf (200K) Download Attachment

stepharo

Re: Little challenges for a friday evening

In reply to this post by Henrik Nergaard-2

I love all these solutions!!!
Thank for you for such cool but compact discussions!

I did a check to see how I could get isograms for french so over a
dictionary of 300000 entities around 50000 are
and I got really surprised because stupily I was counting é, ê, e and è
as the same letter and well they are not (I remember
the points that I got removed during my french lecture because I
confused é and è).
So the french alphabet is around 42 if we count
à, â, é, è, ê, î, ï, ô, ù, û, ç, æ et œ (I never saw ü, ÿ, ë)
but this excellent to show some important points too....

a solution can be excellent if it matches well the requirements and some
solutions are more flexible than others.

Stef

Ben Coman

Re: Little challenges for a friday evening

In reply to this post by stepharo

A nice read. What audience is it aimed at?
Some grammar suggestions...

> Sets are collections that only contains one element.

Being pedantic ;) the following Set does more than "contain one element"...
(Set new) add: 1; add: 2.

so maybe...
"Sets are unordered collections where elements do not repeat. " (??)

> isIsogramSetImplementation
> isIsogramFatestImplementation

might be shortened to "isIsogramBySet" and "isIsogramByFindString"

> To define a method as class extension

To define a method as "a" class extension

> and move the methods we define as class extension

and move the methods we define as class extension"s"

> verifie

"verify"

> Because the user of the method will not have the

This seems an incomplete sentence.

> either return always a collection as for that we convert the character ...

"either always return a collection (thus we convert the character ... )"

cheers -ben

On Sat, Nov 12, 2016 at 7:19 AM, stepharo <[hidden email]> wrote:

> I pair programmed with my middle son and we got the following chapter.
>
> Now going to bed :)
>
>
> Le 11/11/16 à 16:13, Damien Pollet a écrit :
>
> On 11 November 2016 at 12:02, stepharo <[hidden email]> wrote:
>>>
>>> String>>#isIsogram
>>> | letters |
>>> letters := Dictionary new.
>>> self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].
>>
>> Yes I did that one too and I was surprised because it was as slow as the
>> bag implementation.
>
>
> Anyone tried replacing the dictionary with an array of 26 booleans and
> indexing based on ascii, or even a SmallInteger and bit shifting?
>
>

stepharo

Re: Little challenges for a friday evening

> A nice read. What audience is it aimed at?
Difficult question :)
First or second year students and more.
So with and without a Java lecture before.
But the guy should know how to program a bit
I told you that it was fuzzy

> Some grammar suggestions...
Oh I'm sure that they are many.
I will fix them

>
>> Sets are collections that only contains one element.
> Being pedantic ;) the following Set does more than "contain one element"...
> (Set new) add: 1; add: 2.
>
> so maybe...
> "Sets are unordered collections where elements do not repeat. " (??)
>
>
>> isIsogramSetImplementation
>> isIsogramFatestImplementation
> might be shortened to "isIsogramBySet" and "isIsogramByFindString"
>
>
>> To define a method as class extension
> To define a method as "a" class extension
>
>
>> and move the methods we define as class extension
> and move the methods we define as class extension"s"
>
>
>> verifie
> "verify"
>
>
>> Because the user of the method will not have the
> This seems an incomplete sentence.
>
>
>> either return always a collection as for that we convert the character ...
> "either always return a collection (thus we convert the character ... )"
>
>
> cheers -ben

Thanks ben.
If you want to do PR all the chapter is on github LearningOOP with Pharo.

>
>
> On Sat, Nov 12, 2016 at 7:19 AM, stepharo <[hidden email]> wrote:
>> I pair programmed with my middle son and we got the following chapter.
>>
>> Now going to bed :)
>>
>>
>> Le 11/11/16 à 16:13, Damien Pollet a écrit :
>>
>> On 11 November 2016 at 12:02, stepharo <[hidden email]> wrote:
>>>> String>>#isIsogram
>>>> | letters |
>>>> letters := Dictionary new.
>>>> self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].
>>> Yes I did that one too and I was surprised because it was as slow as the
>>> bag implementation.
>>
>> Anyone tried replacing the dictionary with an array of 26 booleans and
>> indexing based on ascii, or even a SmallInteger and bit shifting?
>>
>>
>

stepharo

Re: Little challenges for a friday evening

In reply to this post by Henrik Nergaard-2

Hi henrik

I have the impression that the code is missing something

'aa' isIsogram
>>> true

I wonder how we can set a bit without returning a new integer.

isIsogram

                | i |



                i := 0.



                self asLowercase do: [ :char |

                                | val |

                                val := (char asInteger - 96).

                                (val between: 1 and: 26) ifFalse: [ ^ false ].

                                (i bitAt: val ) == 1 ifTrue: [ ^ false ].

                                i bitAt: val put: 1

i := i bitAt: val put: 1

].

^ true

An interesting observation here is that if #asLowercase is moved to each character instead “val := (char asLowercase asInteger - 96).” Then it leads to a 4-5x performance loss .

From: Pharo-users [[hidden email]] On Behalf Of Damien Pollet
Sent: Friday, November 11, 2016 4:14 PM
To: Any question about pharo is welcome [hidden email]
Subject: Re: [Pharo-users] Little challenges for a friday evening

On 11 November 2016 at 12:02, stepharo <[hidden email]> wrote:

String>>#isIsogram
| letters |
letters := Dictionary new.
self do: [ :x | letters at: x ifAbsent: [] ifPresent: [ ^false ].

Yes I did that one too and I was surprised because it was as slow as the bag implementation.

Anyone tried replacing the dictionary with an array of 26 booleans and indexing based on ascii, or even a SmallInteger and bit shifting?