Author Topic: Loop all possible words algorithm  (Read 27191 times)

0 Members and 1 Guest are viewing this topic.

Offline harold

  • LV5 Advanced (Next: 300)
  • *****
  • Posts: 226
  • Rating: +41/-3
    • View Profile
Re: Loop all possible words algorithm
« Reply #15 on: August 02, 2011, 01:20:41 pm »
This probably won't help because it's an inefficient algorithm, but here's some Haskell that does what you want:
Code: [Select]
allLetters = ['a'..'z']
allWords = concat [wordsOfLen x | x<-[1..]]
           where
                wordsOfLen 1 = [[x] | x<-allLetters]
                wordsOfLen len = [x : y | x<-allLetters, y<-wordsOfLen (len - 1)]
Blog about bitmath: bitmath.blogspot.nl
Check the haroldbot thread for the supported commands and syntax.
You can use haroldbot from this website.

Ashbad

  • Guest
Re: Loop all possible words algorithm
« Reply #16 on: August 02, 2011, 02:20:36 pm »
Well, in a C/C++ way of thinking, a way would possibly be something like this:

Code: [Select]
void*GetPossibleWords(unsigned int amount) {
  unsigned int length=0;
  unsigned int char_length=1;
  unsigned int placeholder=amount;
  int placeholder2=1;
  while (placeholder) {
    length+=placeholder^26*placeholder2++;
    placeholder=(placeholder>=0)?(placeholder/26):(0);
  }
  void*memalloc=malloc(length);
  void*returnalloc=memalloc;
  *(memalloc)=length;
  memalloc+=sizeof(unsigned int);
  char*chars=malloc(placeholder2);
  *(chars)='a';
  int k;
  for(int j=1;j<=char_length;j++) {
    memcop(chars,memalloc,char_length);
    k=char_length;
    while(k) {
      *(chars+k-1)++
      if (*(chars+k-1)=='z') {
        *(chars+(k--)-1)='a';
      } elseif (*(chars)=='z') {
        char_length++;
        for(int l=0;l<=char_length-1;l++) {
          *(chars+l)='a'; }
      } else { k=0; }
    } }
  return returnalloc;
}

This is really rough, since I kinda just drafted it out in <5 minutes with no testing whatsoever :P.  In fact, i think its only like 80% complete, since I really was rushed making it.  What the purpose of this is to take an amount of words to process and output a pointer (with the sizeof(int) first bytes holding the size of the returned allocated memory) pointing to a chunk in memory with the words in lexical order.

Edit: haha, just realized this is really broken.  Ignore that it wont loop through more than once, just keep in mind the purpose I was aiming towards, since this was kinda a step in the right direction..
* Ashbad goes back to making a much smaller and working version of this in Haskell..

Edit2: was I seriously ninja'd by Haskell code? <.<
« Last Edit: August 02, 2011, 02:23:50 pm by Ashbad »

Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55943
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Loop all possible words algorithm
« Reply #17 on: August 02, 2011, 02:28:54 pm »
Lol actually I found that quite funny because you mentionned you like Haskell a lot in another topic, yet you get ninja'd by Haskell code while posting using a different programming language. ;D

Offline nemo

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1203
  • Rating: +95/-11
    • View Profile
Re: Loop all possible words algorithm
« Reply #18 on: August 02, 2011, 03:06:45 pm »
here's my attempt, though my use of pointers is probably pretty ugly since i just used an online tutorial as a reference for that part.

Code: [Select]
#include <stdio.h>

unsigned long pow(unsigned long base, unsigned long exp)
{
    if(exp == 1)
        return base;
    return base * pow(base, exp - 1);
}

char *GetString(int stringLength, unsigned long combination)
{
    char* character = malloc(sizeof(char) * 2);
    *character = combination % 26 + 'a';
    *(character + 1) = '\0';
    if(stringLength == 1)
        return character;
    return strcat(GetString(stringLength - 1, combination / 26), character);
}

int main(int argc, int *argv[])
{
    const int MAX_LEN = 3;
    int len;
    unsigned long i;
    for(len = 1; len <= MAX_LEN; len++)
    {
        for(i = 0; i < pow(26, len); i++)
        {
            printf("%s\n", GetString(len, i));
        }
    }
    return 0;
}


Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: Loop all possible words algorithm
« Reply #19 on: August 05, 2011, 03:20:25 am »
Attempt to create a short solution that fails epically (in TI-BASIC)

Darn my TI-BASIC coding skills are rather rusty. Didn't test oncalc, sorry.

Code: [Select]
:ClrHome
:For(A,1,8
:Disp "
:End
:For(A,1,1E99
:" ->Str1
:A->B
:While B
:round(26fPart(B/26->C
:If C
:Then
:sub("ABCDEFGHIJKLMNOPQRSTUVWXY",C,1)+Str1->Str1
:Else
:"Z"+Str1->Str1
:B-26->B
:End
:iPart(B/26->B
:End
:Output(8,1,Str1
:Disp "
:End

Slightly shorter than ztrumpet's? :P

idk, but I think it's quite a bit faster
« Last Edit: August 05, 2011, 03:21:38 am by phenomist »
Level Designer for Graviter

[Disclaimer: I can't program for my life.]

Offline Horrowind

  • LV2 Member (Next: 40)
  • **
  • Posts: 25
  • Rating: +6/-0
    • View Profile
Re: Loop all possible words algorithm
« Reply #20 on: August 05, 2011, 07:04:11 am »
well.... my two cents using recursion:
Code: [Select]
#include "iostream"
#include "string"
void allwords(string s, int i) {
for(char j = 97; j <123; j++) {
if(i > 1)
allwords(s + j, i-1);
else
std::cout<<s+j<<'\n';
}
}
int main(void) {
int i = 0;
while(1) {
allwords("", i);
i++;
}
}

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Re: Loop all possible words algorithm
« Reply #21 on: August 05, 2011, 10:38:50 am »
Here is a verson in Lua ;D
Code: (Lua) [Select]
a="a"

function increment(str)
        len = #str
        if len==0 then
                return "a"
        end
        bt = str:byte(len)
        if bt<122 then
                str = str:sub(1, len - 1) .. string.char(bt+1)
        else
                str = increment(str:sub(1, len - 1)) .. "a"
        end
        return str
end

print(a)
for i=1,100 do
 a=increment(a)
 print(a)
end

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
Re: Loop all possible words algorithm
« Reply #22 on: August 05, 2011, 10:52:30 am »
Code: [Select]
def increment(x):
    """Increments the string x"""
    length_of_string = len(x)
    if length_of_string == 0:
        return "a"
    bt = ord(x)
    if bt < 122:
        x = x[1:-1] + chr(bt+1)
    else:
        x = increment(x[1:-1] + "a")
    return x
   
def main():
    """Displays all possible words using alphabet a-z"""
    a = "a"
   
    for i in range(1000):
        a = increment(a)
        print a
 
if __name__ == "__main__":
    main()

Heh Jim, I tried to copy cat your version to Python, but failed :P

Offline Levak

  • LV9 Veteran (Next: 1337)
  • *********
  • Posts: 1002
  • Rating: +208/-39
    • View Profile
    • My website
Re: Loop all possible words algorithm
« Reply #23 on: August 05, 2011, 11:05:35 am »
Algorithm
Code: [Select]
import Levak

def main():
    for words in Levak.dictionnary:
        print words

Output
Code: [Select]
42


Hum, I'm missing something ...
I do not get mad at people, I just want them to learn the way I learnt.
My website - TI-Planet - iNspired-Lua

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Re: Loop all possible words algorithm
« Reply #24 on: August 05, 2011, 11:18:51 am »
ephan, I'll give you a tip: Lua starts with 1, python with 0 :)
(/me waits for the beating)

@Levak, lol

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
Re: Loop all possible words algorithm
« Reply #25 on: August 05, 2011, 11:25:20 am »
ephan, I'll give you a tip: Lua starts with 1, python with 0 :)
(/me waits for the beating)

@Levak, lol

Jim, I did not understand your algorithm, I just copied so I don't know where it is wrong.

Code: [Select]
def increment(x):
    """Increments the string x"""
    length_of_string = len(x)
    if length_of_string == 0:
        return "a"
    bt = ord(x) #The problem is that ord doesn't work for strings, only characters
    if bt < 122:
        x = x[-1] + chr(bt+1)
    else:
        x = increment(x[-1] + "a")
    return x
   
def main():
    """Displays all possible words using alphabet a-z"""
    a = "a"
   
    for i in range(1000):
        a = increment(a)
        print a
 
if __name__ == "__main__":
    main()

So I tried:

Code: [Select]
def increment(x):
    """Increments the string x"""
    length_of_string = len(x)
    if length_of_string == 0:
        return "a"
    bt = x.encode("hex")
    if bt < 122:
        x = x + chr(bt+1)
    else:
        x = increment(x + "a")
    return x
   
def main():
    """Displays all possible words using alphabet a-z"""
    a = "a"
   
    for i in range(1000):
        a = increment(a)
        print a
 
if __name__ == "__main__":
    main()

But I get recursion errors.

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Loop all possible words algorithm
« Reply #26 on: August 05, 2011, 12:25:32 pm »
Slightly shorter than ztrumpet's? :P

idk, but I think it's quite a bit faster
I'll take that challenge.
I'm going to try to beat you on both speed and size.  Here's to coding! ^-^

Edit: Yours doesn't have any errors; well done.  I really like the algorithm you used.  Also, you probably want to flip the final Disp and Output lines so you can see a little bit more on the screen at once.  Excellent job, though. :D\

Edit 2: I just settled for optimizing yours. ;)  Here's what I came up with:
Code: [Select]
:ClrHome
:For(A,-8,-1
:Disp "
:End
:Repeat getKey
:" ->Str1
:A+1->A
:Ans->B
:While Ans
:round(26fPart(Ans/26
:If Ans
:Then
:sub("ABCDEFGHIJKLMNOPQRSTUVWXY",Ans,1)+Str1->Str1
:B
:Else
:"Z"+Str1->Str1
:B-26
:End
:int(Ans/26->B
:End
:Disp "
:Output(8,1,Str1
:End
« Last Edit: August 05, 2011, 02:07:18 pm by ztrumpet »

Offline Munchor

  • LV13 Extreme Addict (Next: 9001)
  • *************
  • Posts: 6199
  • Rating: +295/-121
  • Code Recycler
    • View Profile
Re: Loop all possible words algorithm
« Reply #27 on: August 05, 2011, 02:08:54 pm »
Size comparisons ztrumpet? Nice either way

Offline ztrumpet

  • The Rarely Active One
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 5712
  • Rating: +364/-4
  • If you see this, send me a PM. Just for fun.
    • View Profile
Re: Loop all possible words algorithm
« Reply #28 on: August 05, 2011, 02:24:18 pm »
Size comparisons ztrumpet? Nice either way
Technically they're the same size, but my version's faster. ;)

Offline fb39ca4

  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1749
  • Rating: +60/-3
    • View Profile
Re: Loop all possible words algorithm
« Reply #29 on: August 05, 2011, 02:33:12 pm »
so this is basically counting upwards in base 26, using the letters as digits, right?