Μήνας: Ιουνίου 2018

Αυτή η παλιά άσκηση με τα δυαδικά δέντρα…

Το κλασσικό σορτάρισμα με δυαδικό δέντρο σε Golang.

Ναι, η test case είναι αυτή και ναι, την εμπνεύστηκα απο αυτό το σκέτς που καταλάβατε.

package main

import (
 "fmt"
 "strings"
 )

type TreeNode struct {
 myText string
 lnode *TreeNode
 rnode *TreeNode
 }

func AddLeaf(x *TreeNode, myStr string) {
 var newNode TreeNode
 if x.myText > myStr {
 if x.lnode == nil {
 newNode = TreeNode{myText: myStr}
 x.lnode = &newNode
 } else {
 AddLeaf(x.lnode, myStr)
 }
 } else {
 if x.rnode == nil {
 newNode = TreeNode{myText: myStr}
 x.rnode = &newNode
 } else {
 AddLeaf(x.rnode, myStr)
 }

}

}

func PrintSort(x *TreeNode) {
 if x.lnode != nil {
 PrintSort(x.lnode)
 }
 fmt.Println(x.myText)
 if x.rnode != nil {
 PrintSort(x.rnode)
 }
 }

func main() {
 var mytree TreeNode
 wordlist := strings.Split("ΑΕΤΟΣ ΑΔΡΑΧΤΙ ΛΙΜΕΝΟΦΥΛΑΚΑΣ ΝΥΧΟΚΟΠΤΗΣ ΜΠΡΕΛΟΚ ΑΝΕΜΟΓΚΑΣΤΡΙ ΑΒΕΣΣΑΛΩΜ ΙΣΤΙΟΠΛΟΟΣ ΧΩΡΙΣΤΡΑ", " ")

mytreecur := &mytree
 mytreecur.myText = wordlist[0]
 for i := 1; i < len(wordlist); i++ {
 AddLeaf(mytreecur, wordlist[i])
 }

PrintSort(mytreecur)

}
Advertisements

Σκονάκια

Η προγραμματιστική άσκηση ήταν κάτι που με τσίγκλισε. Τον τελευταίο καιρό προσπαθώ να κάνω κάτι ταρζανιές λίγο περίεργες (περιλαμβάνουν κάμποσο CSS, ολίγη Javascript, μια μυρωδιά HTML και πολύ-πολύ μακαρονικό κώδικα), οπότε, όταν απομακρύνομαι απο το χάος, προσπαθώ να παίξω με άλλα πραγματάκια. Ας πούμε Python…  ή Go.

Λοιπόν με αυτή την Go έπαθα ότι με το Mass Effect. Της έριξα μια ματιά στην αρχή, δε μου έκανε κούκου, την παραμέρισα, παπαρίστηκα με διάφορα άλλα άσχετα, και λίγο καιρό μετά, την ξαναείδα με φρέσκο μάτι και πολύ με άρεζε. Αλλά, παρασύρομαι, είμαι και σε ηλικία που αρχίζει ο γερμανός και σου παίρνει τα μυαλά, οπότε, ας μπούμε στο θεμα.

Η άσκηση ήταν κατά τα φαινόμενα απλή. Θυμάστε το Πυθαγόρειο Θεώρημα από το Λύκειο; «Το τετράγωνον της υποτεινούσης ισούται με το άθροισμα των τετραγώνων των δύο κάθετων πλευρών«; Ελπίζω να μην κάνω summon τον LAMAG αυτή τη στιγμή...  Γενικά ο αριθμός που αντιστοιχεί στο τετράγωνο της υποτείνουσας δεν έχει σα ρίζα ακέραιο αριθμό, πράγμα που πολύ εσκότισεν τον Πυθαγόρα μόλις το πήρε χαμπάρι. Όμως, σε κάποιες, άρκετες περιπτώσεις, τυχαίνει.  Να, π.χ.  To Τρίγωνο με πλευρές 3 και 4 μονάδων έχει υποτείνουσα 5 μονάδες:

path4165

Αυτή λοιπόν η τριάδα (3,4,5) λέγεται Πυθαγόρεια τριάδα. Η άσκηση μας ζητάει να βρούμε τη μία και μοναδική τριάδα (α,β,γ) όπου α+β+γ=1000.

Ούπς!

Η πρώτη μου ιδέα ήταν να δω αν υπάρχει κάτι αλγεβρικό. Αλλά απέχω μια ζωή από το Λύκειο και το Πανεπιστήμιο και με έπιασε απελπισία. Οπότε, η πρώτη μου απόπειρα σε Python ήταν το ακόλουθο αίσχος:

squares={i:i*i for i in range(1,500)}
invsquares={squares[i]:i for i in squares}
for i in range (1,500):
    for j in range(i,500):
        if (i*i+j*j) in invsquares:
            k=invsquares[(i*i+j*j)]
            if i+j+k==1000: print (i,j,k)

Είναι νομίζω ψιλοσαφές τι κάνω, και ζητώ συγγνώμη για τυχόν ανατριχίλες που νιώσατε. Ίσως θα μπορούσα να κάνω και τα for..next comprehensions, αλλά βιαζόμουνα. Δεν έχει σημασία, μερικές φορές σημασία έχει να βγάλεις κώδικα και αποτέλεσμα γρήγορα, και μετά να ανησυχείς για το πόσο έξυπν@ θα φανείς και πόσα comprehension θα δέσεις σε αλυσίδα.

Απλό, λιτό, κατανοητό, αλλά… είμαι μόλις μισή βδομάδα με την Go, και δεν το έχω και τόσο στα arrays. Τι να κάνουμε λοιπόν… τι να κάνουμε;

Ιδέα. Μια συνάρτηση που να βρίσκει την ακέραια ρίζα ενός ακεραίου (αν αυτή υπάρχει). Οπότε, κρατάμε το for loop και απλά, αντί να ψάχνουμε το λεξικό, βλέπουμε επι τόπου αν έχουμε πυθαγόρεια τριάδα.

Οπότε, έχοντας φτιάξει προηγουμένως ένα πρωτοτυπάκι σε Python, έφτιαξα το ακόλουθο προγραμματάκι σε  Go:

package main

import "fmt"

func intSqrt(x int) int {
 var result=-1
 if (x==0 || x==1) {
 result=x
 } else {
 llim,ulim:=0,x
 not_found:=true
 var csr int
 csr=x/2
 for not_found {
 if csr*csr==x {
 not_found=false
 result=csr
 } else if csr*csr>x {
 ulim=csr
 csr=(ulim+llim)/2
 } else {
 llim=csr
 csr=ulim+llim/2
 }
 if ulim-1<=llim {not_found=false} 
 }
 
 }
 return result
}

func main() {
 var a,b,c int
 for i:=1;i<=500;i++ {
 for j:=i;j<=500;j++{
 k:=intSqrt(i*i+j*j)
 if k!=-1 {
 a=i
 b=j
 c=k
 if (a+b+c==1000) {fmt.Println("Η πυθαγόρεια τριάδα με άθροισμα 1000 είναι η: ",a,b,c)}}
 }
 }
 }

Είναι θλιβερό, είναι γάμησέ τα, αλλά την Πυθαγόρειο τριάδα τη βρήκε μια χαρούλα.

Ποια γλώσσα είναι καλύτερη;

Εξαρτάται, αλλά βρήκα ότι μου αρέσει πιο πολύ η σαφήνεια και η περιεκτικότητα της Python. Βέβαια, αν θέλω ασφάλεια, ταχύτητα και compiled κώδικα, εννοείται ότι θα πάω σε Go.