/* EARLY BIRD NUMBERS SEQUENCE [Frogged challenge] REF: https://www.sololearn.com/post/1096638/?ref=app ℹ🤓 TAKING CONTEXT: ============================= The Natural Number String is the infinite string 012345678910111213141516171819202122232425... made by joining together all the natural numbers. Every number will eventually appear in the string of course, but some appear earlier than expected, such as "12" which is between "0" and "3" as well as its natural place between "11" and "13"; next one is 21, which is built by 12 and 13; and next is 23 which is built by 2 and 3... There are several interesting questions we can ask about this string of digits: ❓ What digit is at position i if the positions start at 0 for number 0 and what number is the digit in? For example, the digit at position 20 is the "1" in number 15 position: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... number : 0 1 2 3 4 5 6 7 8 9 10 11 12 ... position: 16 17 18 19 20 21 ... 188 189 ... number : 13 14 15 ... 99 ... Each position (index number) in the string will have in it a particular digit of one of the natural numbers that were joined together. So number 12 in the sequence is in positions 14-15 and at position 15 is a digit of the number 12. Of course, as a string, "12" appears in many upper places in the sequence. ❓ Where is the first appearance of number N? For example 12 appears at positions 1-2 between numbers "1'2" which is before its "natural" place in the sequence, at position 14-15 in number "12". And then... 12 is called an "Early Bird number". ❓ Find all the positions at which a string occurs. For example, up to position 99 (in number 54) '0' occurs 6 times at positions : 0, 11, 31, 51, 71, 91 in numbers: 0, 10, 20, 30, 40, 50. ❓ Count the frequencies of the digits in any range of numbers For example, the digit counts in all two digit numbers are. Frequencies of digits in numbers 10–99 [90 numbers]: digit: 0 1 2 3 4 5 6 7 8 9 Total count: 9 19 19 19 19 19 19 19 19 19 180 📋 TASK: ============================= Show the first 100 numbers that occur in the string ahead of their natural place, sorted into increasing order. 📮↩ INPUT: ============================= Any positive number. If you enter other thing, default value of 100 is taken. 📮↪ OUTPUT: ============================= 12, 21, 23, 31, 32, 34, 41, 42, 43, 45, 51, 52, 53, 54, 56, 61, 62, 63, 64, 65, 67, 71, 72, 73, 74, 75, 76, 78, 81, 82, 83, 84, 85, 86, 87, 89, 91, 92, 93, 94, 95, 96, 97, 98, 99, 101, 110, 111, 112, 121, 122, 123, 131, 132, 141, 142, 151, 152, 161, 162, 171, 172, 181, 182, 191, 192, 201, 202, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 231, 232, 233, 234, 241, 242, 243, 251, 252, 253, 261, 262, 263, 271, 272, 273, 281, 282 🌐 RESOURCES: ============================= - Online Enciclopedia of Integer Sequences entry: https://oeis.org/A116700 - http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/EarlyBirds/natseq.html @author davorpatech @since 2021-05-23 */ package main import ( "fmt" "log" _"math" "os" "sort" "strconv" "strings" "sync" "time" ) //====================================== // PROGRAM // var ( logerr *log.Logger wtty int = 40 ) func init() { // init package const flags = log.Ltime | log.Lmicroseconds | log.LUTC | log.Lmsgprefix // Configure default logger log.SetFlags(flags) log.SetOutput(os.Stdout) log.SetPrefix(":app: ") // configure error logger logerr = log.New(os.Stdout, ":err: ", flags) } func main() { defer TraceStartEnd(time.Now())() printSplash() var count int var start, end int fmt.Print("How many numbers do you want? (100): ") if _, err := fmt.Scanln(&count); err != nil || count < 0 { logerr.Println("Invalid number.", err) count = 100 // infer defaults on input errors } fmt.Println(); fmt.Println() // Natural Number String var nns = new(NatNumStr) // allocate nearest size nns.AllocRangeC(start, count) // cap := nns.Cap() // Generate nums := make(IntSlice, count) var first, last int = 0, 0 for i, n := 0, start; i < count; n += 1 { if nns.SeqContains(n) { nums[i] = n if i == 0 { first = n } i += 1 } end = n nns.Add(n) /* if ccap := nns.Cap(); ccap > cap { cap = ccap; fmt.Println("nns.Cap()", cap) } */ } var perc float64 = 0.0 var maxlen int = start if len := len(nums); len > 0 { last = nums[len-1] if (last > maxlen) { maxlen = last } perc = float64(len) / float64(last+1) * 100 } maxlen = len(fmt.Sprint(maxlen)) // Print fmt.Printf(`ℹ There are %d (%0.03f %%) Early Birds in natural numbers range [%d..%d]: First: %*d Last: %*d %v `, len(nums), perc, start, end, maxlen, first, // "%*d" uses maxlen as width maxlen, last, nums.SliceStringJoin(", "), ) fmt.Println() // fmt.Println(nns.Cap()) if freqs, total := nns.DigitFrecuencies(); true { fmt.Printf(`ℹ Digit frecuencies in the Natural Number string (total %d): `, total) ForEachOrderedMapUint8Uint(freqs, func(digit uint8, count uint, index int) { // 2 columns printing var nl rune = '\n' if index & 1 == 0 { nl = 0x00 } fmt.Printf(" %d : %-10d%c", digit, count, nl) }) } fmt.Println() fmt.Printf(`ℹ The Natural Number string sequence of %[2]d digits is: %[1]v `, nns, nns.Len()) } func printSplash() { w := wtty - 1 fmt.Printf(` %[1]v %[2]v |%[3]v| <|%[4]v|> |%[3]v| %[2]v `, Center("_.o•°~@/¤\\@~°•o._", w), strings.Repeat("=", w), Spaces(w-2), Center("🐹 EARLY BIRD NUMBERS GENERATOR 🐹", w-2*2), //2=>emojis ) } //====================================== // MODEL // type NatNumStr struct { lk sync.RWMutex buf StringBuilder } func (nns *NatNumStr) String() string { nns.lk.RLock(); defer nns.lk.RUnlock() return nns.buf.String() } func (nns *NatNumStr) AllocRangeC(start, count int) (c int) { // @TODO adjust a bit more c = 2 for i,l := Diglen(start),Diglen(start+count); i<=l; i++ { c *= 100 c /= 21 } c += (count+start) * (Diglen(count) * 5) / 3 nns.lk.Lock(); nns.lk.Unlock() nns.buf.Grow(c) // fmt.Println(c, nns.Cap()) return } func (nns *NatNumStr) Cap() int { nns.lk.RLock(); defer nns.lk.RUnlock() return nns.buf.Cap() } func (nns *NatNumStr) Len() int { nns.lk.RLock(); defer nns.lk.RUnlock() return nns.buf.Len() } func (nns *NatNumStr) Add(n int) { nns.lk.Lock(); defer nns.lk.Unlock() nns.buf.WriteInt(n) } func (nns *NatNumStr) SeqContains(n int) bool { ns := strconv.Itoa(n) nns.lk.RLock() s := nns.buf.String() nns.lk.RUnlock() return strings.Contains(s, ns) } func (nns *NatNumStr) DigitFrecuencies() (counts map[uint8]uint, total uint) { nns.lk.RLock() s := nns.buf.String() nns.lk.RUnlock() lo, hi := uint8(0), uint8(9) counts = make(map[uint8]uint, 10) // alloc 10 items // log.Println(len(counts)) total = uint(0) // parallel count var wg sync.WaitGroup // A semaphore to avoid concurrent map writes. // Buffered channels block when are full, so it's important use one with size=1 to get the locking behaviour. semaphore := make(chan struct{}, 1) wg.Add(10) // register workers for digit := lo; digit <= hi; digit++ { // execute worker go func(digit uint8, done func()) { defer done() // notify worker end freq := strings.Count(s, strconv.Itoa(int(digit))) semaphore <- struct{}{} // adquire token counts[digit] = uint(freq) total += uint(freq) <- semaphore // release token }(digit, wg.Done) } wg.Wait() // wait all done return } //====================================== // UTILS. math/ints // //#package ints //#import "strconv" // Diglen counts the number of digits of which an "int" number is composed. Sign is take into account. func Diglen(n int) int { s := strconv.Itoa(n) return len(s) } //====================================== // UTILS. log/trace // //#package trace //#import "log" //#import ."strings/pool" //#import "time" // TraceStartEnd emits a log trace at begin and end with the elapsed time on invoke returned function. // Commonly used as... defer TraceStartEnd(time.Now())() func TraceStartEnd(start time.Time) (ender func()) { log.Println(SemjInfoini, "Start...") return func() { log.Println(SemjInfoend, "End.", time.Since(start)) } } //====================================== // UTILS. strings/pool // //#package pool // Predefined string constants pool. const ( // Empty string. Sempty = "" // Single Space string. Sspace = " " // Carriage return string. Scr = "\r" // Line feed string. Slf = "\n" // CRLF string. Scrlf = "\r\n" // Ellipsis string. Sellipsis = "..." // Open bracket string. Sbracketopen = "[" // Close bracket string. Sbracketclos = "]" ) // Predefined emoji icons constants pool. const ( // SemjGopher = "🐹" // Warn icon string. SemjWarn = "⚠" // Info start icon string. SemjInfoini = "ℹ🚩" // Info finish icon string. SemjInfoend = "ℹ🏁" ) //====================================== // UTILS. strings // //#package strings //#import "bytes" //#import "fmt" //#import "runtime" //#import "strconv" //#import "strings" //#import ."strings/pool" type ( IntWriter interface { WriteInt(x int) (len int, err error) } UintWriter interface { WriteUint(x uint) (len int, err error) } Uint8Writer interface { WriteUint8(x uint8) (len int, err error) } Uint32Writer interface { WriteUint32(x uint32) (len int, err error) } Uint64Writer interface { WriteUint64(x uint64) (len int, err error) } ) type StringBuilder struct { strings.Builder // embed to extend } func (sb *StringBuilder) WriteInt(x int) (len int, err error) { s := strconv.Itoa(x) len, err = sb.WriteString(s) return } func (sb *StringBuilder) WriteUint(x uint) (len int, err error) { return sb.WriteUint64(uint64(x)) } func (sb *StringBuilder) WriteUint8(x uint8) (len int, err error) { return sb.WriteUint64(uint64(x)) } func (sb *StringBuilder) WriteUint32(x uint32) (len int, err error) { return sb.WriteUint64(uint64(x)) } func (sb *StringBuilder) WriteUint64(x uint64) (len int, err error) { s := strconv.FormatUint(x, 10) // to base-10 len, err = sb.WriteString(s) return } // Spaces generate a string with the given number of whitespaces. func Spaces(n int) string { return strings.Repeat(Sspace, n) } // Center tries to center a string to a given width using whitespace as filling characters. // It preserves codepoints joined when distributable width is computed. func Center(s string, w int) (cs string) { if len(s) == 0 { cs = Spaces(w) return } scp := []rune(s) // sc = fmt.Sprintf("%*s", -w, fmt.Sprintf("%*s", (w + len(s))/2, s)) cs = fmt.Sprintf("%*s", -w, fmt.Sprintf("%*s", (w + len(scp))/2, s)) return } //====================================== // UTILS. collection/slices // //#package slices //#import "strings" //#import ."strings/pool" //#import "strconv" // SliceStringer iface defines the contract of slices to be formatted with some characteristics. type SliceStringer interface { SliceStringJoin(sep string) string SliceStringDelim(start, end, sep string) string String() string // fmt.Stringer iface } // IntStreamer iface allows send int values to stream channel. type IntStreamer interface { StreamInt() <- chan int } // Type alias for a slice of ints matching SliceStringer, Lenger ifaces. type IntSlice []int // Len implements Lenger iface computing slice length. func (this IntSlice) Len() int { return len(this) } // -- SliceStringer iface implementation -- // // SliceStringJoin formats the slice using the provided separator between items to compose formatted string. func (this IntSlice) SliceStringJoin(sep string) (s string) { return this.SliceStringDelim(Sempty, Sempty, sep) } // SliceStringDelim formats the slice using the "start"-"end" delimiters and the provided separator between items to compose formatted string. func (this IntSlice) SliceStringDelim(start, end, sep string) (s string) { if len, ls, le, lsep := len(this), len(start), len(end), len(sep); ls + le + (lsep*len) > 0 { var b StringBuilder // @TODO: Compute real items len? // alloc initial capacity for n-digit ints b.Grow(ls + le + (lsep*len) + (len*16)) // append start delimiter if ls > 0 { b.WriteString(start) } if len > 0 { // process elements // append first b.WriteInt(this[0]) for i := 1; i < len; i++ { // append previous item separator b.WriteString(sep) // append current item b.WriteInt(this[i]) } } // append end delimiter if le > 0 { b.WriteString(end) } // return inner value s = b.String() } return } // String implements fmt.Stringer iface using the slice default format to compose the string representation. func (this IntSlice) String() string { start,end,sep := Sbracketopen,Sbracketclos,Sspace return this.SliceStringDelim(start, end, sep) } // SliceToString format a slice using their default format to get the composed string representation. func SliceToString(ss SliceStringer) (s string) { if ss != nil { s = ss.String() } return } // SliceToJoinString format a slice using the provided separator between items to compose formatted string. func SliceToJoinString(ss SliceStringer, sep string) (s string) { if ss != nil { s = ss.SliceStringJoin(sep) } return } // Iterate a map using a consumer function where values are receive (index, key, value) ensuring that is done according with keys natural order. func ForEachOrderedMapUint8Uint( smap map[uint8]uint, consumer func(key uint8, val uint, i int)) { // to key slice keys := make([]uint8, len(smap)) i := 0 for k := range smap { keys[i] = k i++ } // apply natural order sort.Slice(keys, func(i,j int) bool { return keys[i] < keys[j] }) // iterate ordered for i,k := range keys { consumer(k, smap[k], i) } }

🐹 Early Bird Numbers .go