pwc144 solution in go

7 files changed, 245 insertions, 0 deletions

diff --git a/challenge-144/pokgopun/README b/challenge-144/pokgopun/README
new file mode 100644
index 0000000000..33dfd303a4
--- /dev/null
+++ b/challenge-144/pokgopun/README
@@ -0,0 +1 @@
+Solution by PokGoPun
diff --git a/challenge-144/pokgopun/go/ch-1.go b/challenge-144/pokgopun/go/ch-1.go
new file mode 100644
index 0000000000..e9df6a77f5
--- /dev/null
+++ b/challenge-144/pokgopun/go/ch-1.go
@@ -0,0 +1,33 @@
+/*
+Write a script to generate all Semiprime number <= 100.
+
+For more information about Semiprime, please checkout the wikipedia page.
+
+
+In mathematics, a semiprime is a natural number that is the product of exactly two prime numbers. The two primes in the product may equal each other, so the semiprimes include the squares of prime numbers.
+
+Usage:
+To get Semiprime number <= 10
+go run ch-1.go 10
+4, 6, 9, 10
+*/
+package main
+
+import (
+	"fmt"
+	"log"
+	"os"
+
+	"github.com/pokgopun/go/semiprime"
+)
+
+func main() {
+	var n uint = 100
+	if len(os.Args) > 1 {
+		_, err := fmt.Sscanf(os.Args[1], "%d", &n)
+		if err != nil {
+			log.Fatal(err)
+		}
+	}
+	fmt.Println(semiprime.NewSemiprime(n))
+}
diff --git a/challenge-144/pokgopun/go/ch-2.go b/challenge-144/pokgopun/go/ch-2.go
new file mode 100644
index 0000000000..20359474ae
--- /dev/null
+++ b/challenge-144/pokgopun/go/ch-2.go
@@ -0,0 +1,35 @@
+/*
+You are given two positive numbers, $u and $v.
+
+Write a script to generate Ulam Sequence having at least 10 Ulam numbers where $u and $v are the first 2 Ulam numbers.
+
+For more information about Ulam Sequence, please checkout the website.
+
+The standard Ulam sequence (the (1, 2)-Ulam sequence) starts with U1 = 1 and U2 = 2. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.
+
+Usage:
+To get a 10 Ulam numbers where u=2 and v=5
+go run ch-2.go 2 5 10
+2, 5, 7, 9, 11, 12, 13, 15, 19, 23
+*/
+package main
+
+import (
+	"fmt"
+	"log"
+	"os"
+	"strings"
+
+	"github.com/pokgopun/go/ulam"
+)
+
+func main() {
+	var u, v, n uint = 1, 2, 10
+	if len(os.Args) > 3 {
+		_, err := fmt.Sscanf(strings.Join(os.Args[1:], " "), "%d %d %d", &u, &v, &n)
+		if err != nil {
+			log.Fatal(err)
+		}
+	}
+	fmt.Println(ulam.NewUlam(u, v, n))
+}
diff --git a/challenge-144/pokgopun/go/semiprime/semiprime.go b/challenge-144/pokgopun/go/semiprime/semiprime.go
new file mode 100644
index 0000000000..6db9a765b7
--- /dev/null
+++ b/challenge-144/pokgopun/go/semiprime/semiprime.go
@@ -0,0 +1,73 @@
+package semiprime
+
+import (
+	"math"
+	"strconv"
+)
+
+func NewSemiprime(n uint) (smprm semiprime) {
+	smprm.n = n
+	smprm.buildPrime(n)
+	for i := uint(2); i <= n; i++ {
+		if smprm.isSemiprime(i) {
+			smprm.vals = append(smprm.vals, i)
+		}
+	}
+	return smprm
+}
+
+type semiprime struct {
+	pmap  []bool
+	plist []uint
+	n     uint
+	vals  []uint
+}
+
+func (smprm semiprime) String() (s string) {
+	if len(smprm.vals) == 0 {
+		return s
+	}
+	for _, v := range smprm.vals {
+		s += ", " + strconv.FormatUint(uint64(v), 10)
+	}
+	return s[2:]
+}
+
+func (smprm semiprime) isSemiprime(n uint) bool {
+	if smprm.pmap[n] {
+		return false
+	}
+	for i := 0; i < len(smprm.plist); i++ {
+		if n%smprm.plist[i] == 0 {
+			n /= smprm.plist[i]
+			break
+		}
+	}
+	if smprm.pmap[n] {
+		return true
+	}
+	return false
+}
+
+func (smprm *semiprime) buildPrime(n uint) {
+	smprm.pmap = make([]bool, int(n)+1)
+	for i := 2; i <= int(n); i++ {
+		smprm.pmap[i] = true
+	}
+	l := int(math.Floor(math.Sqrt(float64(n))))
+	for i := 2; i <= l; i++ {
+		if !smprm.pmap[i] {
+			continue
+		}
+		j := i * i
+		for j <= int(n) {
+			smprm.pmap[j] = false
+			j += i
+		}
+	}
+	for i := 2; i < len(smprm.pmap); i++ {
+		if smprm.pmap[i] {
+			smprm.plist = append(smprm.plist, uint(i))
+		}
+	}
+}
diff --git a/challenge-144/pokgopun/go/semiprime/semiprime_test.go b/challenge-144/pokgopun/go/semiprime/semiprime_test.go
new file mode 100644
index 0000000000..a7b6900bd8
--- /dev/null
+++ b/challenge-144/pokgopun/go/semiprime/semiprime_test.go
@@ -0,0 +1,25 @@
+package semiprime
+
+import (
+	"testing"
+)
+
+func TestNewSemiprime(t *testing.T) {
+	data := []struct {
+		n   uint
+		seq string
+	}{
+		{0, ""},
+		{1, ""},
+		{2, ""},
+		{3, ""},
+		{4, "4"},
+		{100, "4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95"},
+	}
+	for _, d := range data {
+		res, ans := NewSemiprime(d.n).String(), d.seq
+		if ans != res {
+			t.Error("incorrect result: expected " + ans + ", got " + res)
+		}
+	}
+}
diff --git a/challenge-144/pokgopun/go/ulam/ulam.go b/challenge-144/pokgopun/go/ulam/ulam.go
new file mode 100644
index 0000000000..d43aab86f7
--- /dev/null
+++ b/challenge-144/pokgopun/go/ulam/ulam.go
@@ -0,0 +1,54 @@
+package ulam
+
+import (
+	"sort"
+	"strconv"
+)
+
+type ulam struct {
+	u, v, n uint
+	vals    []uint
+}
+
+func (ul ulam) String() (s string) {
+	if ul.n == 0 {
+		return s
+	}
+	for _, v := range ul.vals {
+		s += ", " + strconv.FormatUint(uint64(v), 10)
+	}
+	return s[2:]
+}
+
+func NewUlam(u, v, n uint) ulam {
+	ul := ulam{u, v, n, []uint{u, v, u + v}}
+	if n < 3 {
+		ul.vals = ul.vals[:int(n)]
+		return ul
+	}
+	for len(ul.vals) < int(n) {
+		m := make(map[uint]uint)
+		l := len(ul.vals)
+		var sum uint
+		for i := 0; i < l; i++ {
+			for j := i + 1; j < l; j++ {
+				sum = ul.vals[i] + ul.vals[j]
+				if sum > ul.vals[l-1] {
+					m[sum]++
+				}
+			}
+		}
+		var s []uint
+		for k, v := range m {
+			if v > 1 {
+				continue
+			}
+			s = append(s, k)
+		}
+		sort.SliceStable(s, func(i, j int) bool {
+			return s[i] < s[j]
+		})
+		ul.vals = append(ul.vals, s[0])
+	}
+	return ul
+}
diff --git a/challenge-144/pokgopun/go/ulam/ulam_test.go b/challenge-144/pokgopun/go/ulam/ulam_test.go
new file mode 100644
index 0000000000..026e7c2ad1
--- /dev/null
+++ b/challenge-144/pokgopun/go/ulam/ulam_test.go
@@ -0,0 +1,24 @@
+package ulam
+
+import "testing"
+
+func TestNewUlam(t *testing.T) {
+	data := []struct {
+		u, v, n uint
+		seq     string
+	}{
+		{1, 2, 0, ""},
+		{2, 3, 1, "2"},
+		{2, 5, 2, "2, 5"},
+		{1, 2, 10, "1, 2, 3, 4, 6, 8, 11, 13, 16, 18"},
+		{2, 3, 10, "2, 3, 5, 7, 8, 9, 13, 14, 18, 19"},
+		{2, 5, 10, "2, 5, 7, 9, 11, 12, 13, 15, 19, 23"},
+	}
+	for _, d := range data {
+		res := NewUlam(d.u, d.v, d.n).String()
+		ans := d.seq
+		if ans != res {
+			t.Error("incorrect result: expected " + ans + ", got " + res)
+		}
+	}
+}