Post Reply 
Programming puzzles: processing lists!
05-26-2019, 05:51 PM (This post was last modified: 05-26-2019 06:52 PM by pier4r.)
Post: #280
RE: Programming puzzles: processing lists!
For #45 (actually on strings rather than reals but it is the same) I am using this program

Code:

    gpFindDupInListWords
    @ find duplicates in the list of collected words
    @returning the positions, as they are on paper.
    @ at first effective, can be optimized later.
    @ uses listExt
    @ 2019-03-22. It works
    \<<
      0 "lvLsize"    DROP
      0 "lvPos"      DROP
      0 "lvValidRes" DROP
      
      \->
      @input
      @var
      lvLsize
      lvPos
      lvValidRes
      \<<
        gvLBaseWordsColPaper SIZE 'lvLsize' STO
        
        1 lvLsize
        FOR lvPos
          gvLBaseWordsColPaper
          gvLBaseWordsColPaper lvPos GET
          MPOS
          
          IF
            @if the result is an empty list or list of size 1
            DUP SIZE 1 \<=
          THEN
            @not needed
            DROP
          ELSE
            @count it as valid
            'lvValidRes' 1 STO+
          END
        NEXT
        
        @we have the valid results on the stack. we merge them in a list.
        lvValidRes
        \->LIST LDDUP
         @ if there are 3 entries that are duplicated, the program returns
         @ 3 list with those three entries. It is enough to have one.
      \>>
    \>>

Where gvLBaseWordsColPaper is a list of words with possible duplicates in the form exposed at the end.

Obviously since the comparison are being done for each element in the list (therefore O(n^2) ), when the list is long enough, it is going to take long even on emu48 (that it is still simulated).

So now I am going to use ksort to speed up the algorithm.

Code:

    gvLBaseWordsColPaper
    @words collected on paper
    {
      "freude"
      "humor"
      "mut"
      "grosszuegig"
      "frech"
      "kritisch"
      "lebendig"
      "gar"
      "hilfe"
      "nachhilfe"
      "respekt"
      "beeinflussen"
      "ebenso"
      "moewe"
      "gehalt"
      "klima"
      "auszubildende"
      "erzieher"
      "leistung"
      "leiter"
      "praxis"
      "theorie"
      "held"
      "entschliessen"
      "einschlafen"
      "verabschieden"
      "zeit"
      "vollzeit"
      "besprechung"
      "atmosphaere"
      "fuehren"
      "ueberlegen"
      "uebrig bleiben"
      "vorstellen"
      "zurechtkommen"
      "gering"
      "merkwuerdig"
      "komisch"
      "steuer"
      "tagesablauf"
      "ablauf"
      "gehorsam"
      "gehweg"
      "anschrift"
      "adresse"
      "verkehr"
      "fuehlen"
      "schaden"
      "rutschen"
      "unfall"
      "zukommen"
      "hinzukommen"
      "wagen"
      "beschwerden"
      "verhaeltnis"
      "beruehmt"
      "versaeumen"
      "wert"
      "gaststaette"
      "geschaeft"
      "gesicht"
      "geschichte"
      "buerste"
      "eigentum"
      "heim"
      "hof"
      "lage"
      "lift"
      "aufzug"
      "zug"
      "steigen"
      "einsteigen"
      "aussteigen"
      "land"
      "ermaessigung"
      "mitteilen"
      "anpreisen"
      "miete"
      "vermieter"
      "ofen"
      "quartier"
      "vorort"
      "ort"
      "fett"
      "pfand"
      "preis"
      "eimer"
      "block"
      "wohnblock"
      "flaeche"
      "mangel"
      "gang"
      "zugang"
      "eingang"
      "ausgang"
      "auftritt"
      "vorher"
      "vorhin"
      "buchstabe"
      "verpflegung"
      "erschoepft"
      "erschoepfen"
      "packen"
      "einpacken"
      "einziehen"
      "umziehen"
      "anziehen"
      "buerger"
      "einwohner"
      "staat"
      "note"
      "noten"
      "misserfolg"
      "fieber"
      "lampenfieber"
      "auslaendisch"
      "drittel"
      "apartament"
      "etwa"
      "illustrierte"
      "interview"
      "tod"
      "mensch"
      "name"
      "titel"
      "geschlecht"
      "einladen"
      "laden"
      "voriger"
      "ergaenzen"
      "ankreuzen"
      "zuordnen"
      "ordnen"
      "dicht"
      "backen"
      "befehlen"
      "befleissen"
      "beginnen"
      "ungefaehr"
      "zaehlen"
      "fortschritt"
      "geschicklichkeit"
      "gelingen"
      "vorrat"
      "stadion"
      "platz"
      "bad"
      "hallenbad"
      "publikum"
      "technik"
      "bus"
      "plakat"
      "sprecher"
      "siedlung"
      "amuesieren"
      "heerschen"
      "werfen"
      "allerdings"
      "lebendig"
      "wirt"
      "vieh"
      "spannen"
      "erlebnis"
      "schweigen"
      "laechen"
      "wange"
      "zufall"
      "vorschrift"
      "anweisung"
      "dorf"
      "ufer"
      "see"
      "innerhalb"
      "durch"
      "an entlang"
      "um herum"
      "raum"
      "zimmer"
      "mussen"
      "duerfen"
      "moegen"
      "licht"
      "balken"
      "auszug"
      "stift"
      "theater"
      "beobachten"
      "tempus"
      "ueben"
      "gedaechtnis"
      "fall"
      "tastatur"
      "foerdern"
      "bezahlen"
      "bevorzugen"
      "indem"
      "erfuellen"
      "lustig machen"
      "sammeln"
      "umso desto"
      "satz"
      "oft"
      "bewerber"
      "bewerbung"
      "giftig"
      "wille"
      "kuessen"
      "kissen"
      "kiste"
      "hauen"
      "sand"
      "burg"
      "turm"
      "eimer"
      "ei"
      "bein"
      "arm"
      "klettern"
      "holz"
      "stein"
      "pflanze"
      "sofa"
      "teppich"
      "trockenstaender"
      "stube"
      "werkstatt"
      "anpreisen"
      "erhalten"
      "vergnuegen"
      "park"
      "fluss"
      "zentrum"
      "gegner"
      "macht"
      "maechtig"
      "kraeftig"
      "ursache"
      "verlangen"
      "vorstellung"
      "genehmigung"
      "anzahl"
      "flucht"
      "bedarf"
      "fordern"
      "werden"
      "fuehren"
      "einfuhren"
      "fahren"
      "werden"
      "ausdruecken"
      "zweck"
      "verwandt"
      "verwandte"
      "bezug"
      "beziehung"
      "zusammenhaengen"
      "hangen"
      "vergleich"
      "versehen"
      "eroeffnen"
      "feiern"
      "gruenden"
      "abhauen"
      "mitteilen"
      "absehbar"
      "schimpfen"
      "schulter"
      "untersagen"
      "anschliessen"
      "schaden"
      "beschaedigen"
      "schaedlich"
      "hahn"
      "ausschneiden"
      "geisel"
}
Yes, it is for flashcards without using flashcards rather list of words on a4. I find them much more effective than anki and variants.


---------

And a bit faster code.
Code:

\<<
      0  "lvLsize"        DROP
      {} "lvLsortedWords" DROP
      {} "lvLpositions"   DROP
      
      0 "lvPos"        DROP
      0 "lvDuplicates" DROP
      
      "first_word_should_not_match" "lvLastWord" DROP
      "" "lvCurWord"  DROP
      0  "lvWordRepet"  DROP
      \->
      @input
      @var
      lvLsize
      lvLsortedWords
      lvLpositions
      
      lvPos
      lvDuplicates
      
      lvLastWord
      lvCurWord
      lvWordRepet @repetitions of current word
      \<<
        gvLBaseWordsColPaper SIZE 'lvLsize' STO
        lvLsize LSEQ 'lvLpositions' STO @store the positions 1 to n, since we are going to use ksort
        
        @sort the words and accordingly the positions
        lvLpositions
        gvLBaseWordsColPaper
        KSORT
        'lvLsortedWords' STO
        'lvLpositions' STO
        
        
        
        1 lvLsize
        FOR lvPos
          lvLsortedWords lvPos GET 'lvCurWord' STO
          
          IF
            lvCurWord lvLastWord ==
          THEN
            @to collect the positions
            lvPos @on the stack to collect it later.
            'lvWordRepet' 1 STO+ @one more repetition
          ELSE
            @no repetition
            IF
              @if there were repetitions save the result and reset the counter
              lvWordRepet 0 >
            THEN
              @we need to add the position of the first time the entry repeated,
              @as in that case we never put the position on the stack
              
              lvWordRepet PICK @we pick the first position we left on the stack
              1 - @it is a position before that
              'lvWordRepet' 1 STO+ @now there is an additional position
              lvWordRepet ROLLD @move the position down in the stack
              
              lvWordRepet \->LIST @saving the result of the positions on the stack
              lvLpositions SWAP LPICK @pick the corrisponding original positions given the positions of sorted words
                                      @and leaves it on the stack
              
              0 'lvWordRepet' STO @reset counter
              'lvDuplicates' 1 STO+
            END @if repetition
            lvCurWord 'lvLastWord' STO @updating the last word now that it changed
          END @if not same words
        NEXT
        
        @we have the valid results on the stack. we merge them in a list.
        lvDuplicates
        \->LIST SORT @to make it easier
      \>>
    \>>

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 05-26-2019 05:51 PM



User(s) browsing this thread: 1 Guest(s)