Building a training set of tags for go

Question

Building a training set of tags for go

iHiD opened this issue a year ago · 22 comments

Hello lovely maintainers 👋

We've recently added "tags" to student's solutions. These express the constructs, paradigms and techniques that a solution uses. We are going to be using these tags for lots of things including filtering, pointing a student to alternative approaches, and much more.

In order to do this, we've built out a full AST-based tagger in C#, which has allowed us to do things like detect recursion or bit shifting. We've set things up so other tracks can do the same for their languages, but its a lot of work, and we've determined that actually it may be unnecessary. Instead we think that we can use machine learning to achieve tagging with good enough results. We've fine-tuned a model that can determine the correct tags for C# from the examples with a high success rate. It's also doing reasonably well in an untrained state for other languages. We think that with only a few examples per language, we can potentially get some quite good results, and that we can then refine things further as we go.

I released a new video on the Insiders page that talks through this in more detail.

We're going to be adding a fully-fledged UI in the coming weeks that allow maintainers and mentors to tag solutions and create training sets for the neural networks, but to start with, we're hoping you would be willing to manually tag 20 solutions for this track. In this post we'll add 20 comments, each with a student's solution, and the tags our model has generated. Your mission (should you choose to accept it) is to edit the tags on each issue, removing any incorrect ones, and add any that are missing. In order to build one model that performs well across languages, it's best if you stick as closely as possible to the C# tags as you can. Those are listed here. If you want to add extra tags, that's totally fine, but please don't arbitrarily reword existing tags, even if you don't like what Erik's chosen, as it'll just make it less likely that your language gets the correct tags assigned by the neural network.

To summarise - there are two paths forward for this issue:

You're up for helping: Add a comment saying you're up for helping. Update the tags some time in the next few days. Add a comment when you're done. We'll then add them to our training set and move forward.
You not up for helping: No problem! Just please add a comment letting us know :)

If you tell us you're not able/wanting to help or there's no comment added, we'll automatically crowd-source this in a week or so.

Finally, if you have questions or want to discuss things, it would be best done on the forum, so the knowledge can be shared across all maintainers in all tracks.

Thanks for your help! 💙

Note: Meta discussion on the forum

Answer 1 · 2023-11-01T07:08:50.000Z

Exercise: raindrops

Code

package raindrops

import "strconv"

func Convert(input int) (raindrop string) {
	if input%3 == 0 {
		raindrop += "Pling"
	}

	if input%5 == 0 {
		raindrop += "Plang"
	}

	if input%7 == 0 {
		raindrop += "Plong"
	}

	if raindrop == "" {
		raindrop = strconv.Itoa(input)
	}

	return

}

Tags:

construct:assignment
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:method
construct:number
construct:package
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:procedural

Answer 2 · 2023-11-01T07:08:56.000Z

Exercise: scrabble-score

Code

package scrabble

import "unicode"

func Score(word string) int {
	scores := map[string]int{
		"A": 1,
		"E": 1,
		"I": 1,
		"O": 1,
		"U": 1,
		"L": 1,
		"N": 1,
		"R": 1,
		"S": 1,
		"T": 1,
		"D": 2,
		"G": 2,
		"B": 3,
		"C": 3,
		"M": 3,
		"P": 3,
		"F": 4,
		"H": 4,
		"V": 4,
		"W": 4,
		"Y": 4,
		"K": 5,
		"J": 8,
		"X": 8,
		"Q": 10,
		"Z": 10,
	}
	score := 0
	for _, letter := range word {
		score += scores[string(unicode.ToUpper(letter))]
	}
	return score
}

Tags:

construct:assignment
construct:char
construct:for-loop
construct:function
construct:implicit-conversion
construct:int
construct:integral-number
construct:invocation
construct:map
construct:number
construct:package
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:functional
paradigm:object-oriented
technique:looping
uses:map

Answer 3 · 2023-11-01T07:09:02.000Z

Exercise: difference-of-squares

Code

package diffsquares

func SquareOfSums(n int) int {
	sum := n * (n + 1) / 2 // http://www.trans4mind.com/personal_development/mathematics/series/sumNaturalNumbers.htm#mozTocId914933
	return sum * sum
}

func SumOfSquares(n int) int {
	return n * (n + 1) * (2*n + 1) / 6 // http://www.trans4mind.com/personal_development/mathematics/series/sumNaturalSquares.htm#summation
}

func Difference(n int) int {
	return SquareOfSums(n) - SumOfSquares(n)
}

Tags:

construct:add
construct:comment
construct:divide
construct:function
construct:int
construct:integral-number
construct:invocation
construct:multiply
construct:number
construct:package
construct:parameter
construct:return
construct:subtract
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:multiparadigm
technique:math

Answer 4 · 2023-11-01T07:09:08.000Z

Exercise: sublist

Code

package sublist

import (
    "fmt"
    "strings"
)

type Relation string

func Sublist(first, second []int) Relation {
    firstString := sliceToString(first)
    secondString := sliceToString(second)
    firstContainsSecond := strings.Contains(firstString, secondString)
    secondContainsFirst := strings.Contains(secondString, firstString)
    if firstContainsSecond {
        if secondContainsFirst {
            return "equal"
        } else {
            return "superlist"
        }
    }
    if secondContainsFirst {
        return "sublist"
    } else {
        return "unequal"
    }
}

func sliceToString(str []int) string {
    return strings.Trim(fmt.Sprint(str), "[]")
}

Tags:

construct:boolean
construct:if
construct:import
construct:invocation
construct:package
construct:return
construct:string
construct:type-conversion
construct:variable-assignment
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean
technique:higher-order-functions

Answer 5 · 2023-11-01T07:09:14.000Z

Exercise: leap

Code

package leap

func IsLeapYear(year int) bool {
	return year%4 == 0 && year%100 != 0 || year%400 == 0
}

Tags:

construct:boolean
construct:&&
construct:==
construct:function
construct:int
construct:integral-number
construct:logical-or
construct:number
construct:package
construct:parameter
construct:return
construct:ternary
construct:year
paradigm:logical
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic

Answer 6 · 2023-11-01T07:09:20.000Z

Exercise: accumulate

Code

package accumulate

const testVersion = 1

func Accumulate(input []string, acc func(string) string) []string {
	for i, v := range input {
		input[i] = acc(v)
	}
	return input
}

Tags:

construct:assignment
construct:const
construct:for-loop
construct:function
construct:function-type
construct:indexing
construct:int
construct:integral-number
construct:loop
construct:number
construct:package
construct:parameter
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:functional
technique:higher-order-functions
technique:looping

Answer 7 · 2023-11-01T07:09:26.000Z

Exercise: sum-of-multiples

Code

package summultiples

import "sort"

var MultipleSummer = MultipleSummerSorted

func MultipleSummerNaive(divs ...int) func(int) int {
	return func(n int) (s int) {
		for i := 1; i < n; i++ {
			for _, d := range divs {
				if i%d == 0 {
					s += i
					break
				}
			}
		}
		return s
	}
}

// The naive algorithm can be sped up dramatically by recognising that
// a closed-form solution exists for single divisors
//
//   Σ_{1 ≤ x < n, 0 = x (mod d)} x = d*Σ_{1 ≤ x < k} x
//     = d*(1/2)*k*(k + 1), (where k = n/d).
//
// For multiple divisors the total sum can be computed by adding the
// sum for each divisor, and subtracting the sum for all products of
// combinations of divisors to cancel multiples that are counted more
// than once. It is also necessary to ensure that the divisors are
// unique and pairwise coprime (see definition of coprime base from
// http://cr.yp.to/lineartime/dcba-20040404.pdf).
//
// MultipleSummerClosure is the simplest implementation of this.
//
// MultipleSummerStruct uses a struct to save the overhead of creating
// the closure, but is slower in computing the sum.
//
// MultipleSummerSort, in addition to using a struct, sorts the
// products list so that the function can exit early (sum(n,d)=0 when
// d > n).
//
// Benchmarks at the bottom.

// comprime returns the comprime base of s.
func coprime(s []int) []int {
	sort.Ints(s)
	for n := 0; n < len(s)-1; n++ {
		j := n + 1
		for i := j; i < len(s); i++ {
			s[j] = s[i]
			if s[i]%s[n] != 0 {
				j++
			}
		}
		s = s[:j]
	}
	return s
}

// products returns a copy of s and the set of products of all
// combinations of elements of s. (A copy of s is made to simplify the
// procedure, both returned slices are contiguous in memory.)
func products(s []int) ([]int, []int) {
	r := make([]int, 1<<uint(len(s))-1)
	copy(r, s)
	l := len(s)
	for i, j := l-2, l; i >= 0; i-- {
		for _, k := range r[i+1 : j] {
			r[j] = r[i] * k
			j++
		}
	}
	return r[:len(s)], r[len(s):]
}

// sum returns the sum of all multiples of d from 1 up to but not
// including n.
func sum(n, d int) int {
	k := (n - 1) / d
	return d * k * (k + 1) / 2
}

func MultipleSummerClosure(d ...int) func(int) int {
	d, p := products(coprime(d))
	return func(n int) (s int) {
		for _, d := range d {
			s += sum(n, d)
		}
		for _, d := range p {
			s -= sum(n, d)
		}
		return
	}
}

type multisum struct{ d, p []int }

func (m multisum) sum(n int) (s int) {
	for _, d := range m.d {
		s += sum(n, d)
	}
	for _, d := range m.p {
		s -= sum(n, d)
	}
	return
}

func MultipleSummerStruct(d ...int) func(int) int {
	d, p := products(coprime(d))
	return multisum{d, p}.sum
}

type sortsum struct{ d, p []int }

func (m sortsum) sum(n int) (s int) {
	for _, d := range m.d {
		if d > n {
			return
		}
		s += sum(n, d)
	}
	for _, d := range m.p {
		if d > n {
			return
		}
		s -= sum(n, d)
	}
	return
}

func MultipleSummerSorted(d ...int) func(int) int {
	d, p := products(coprime(d))
	sort.Ints(p)
	return sortsum{d, p}.sum
}

// $ go test -bench . -benchtime=10s
// PASS
// BenchmarkNaive35     1000000         17738 ns/op
// BenchmarkNaiveVar      50000        593264 ns/op
// BenchmarkClosure35  100000000          188 ns/op
// BenchmarkClosureVar  5000000          3342 ns/op
// BenchmarkStruct35   100000000          197 ns/op
// BenchmarkStructVar  10000000          2402 ns/op
// BenchmarkSorted35   100000000          119 ns/op
// BenchmarkSortedVar   5000000          3186 ns/op

// func bench35(sum func(...int) func(int) int, b *testing.B) {
//     sum35 := sum(3, 5)
//     b.ResetTimer() // bench just the sum function
//     for i := 0; i < b.N; i++ {
//         for _, test := range test35 {
//             sum35(test.limit)
//         }
//     }
// }

// func benchVar(sum func(...int) func(int) int, b *testing.B) {
//     // bench combined time to bind sum function and call it.
//     for i := 0; i < b.N; i++ {
//         for _, test := range varTests {
//             sum(test.divisors...)(test.limit)
//         }
//     }
// }

// func BenchmarkNaive35(b *testing.B)    { bench35(MultipleSummerNaive, b) }
// func BenchmarkNaiveVar(b *testing.B)   { benchVar(MultipleSummerNaive, b) }
// func BenchmarkClosure35(b *testing.B)  { bench35(MultipleSummerClosure, b) }
// func BenchmarkClosureVar(b *testing.B) { benchVar(MultipleSummerClosure, b) }
// func BenchmarkStruct35(b *testing.B)   { bench35(MultipleSummerStruct, b) }
// func BenchmarkStructVar(b *testing.B)  { benchVar(MultipleSummerStruct, b) }
// func BenchmarkSorted35(b *testing.B)   { bench35(MultipleSummerSorted, b) }
// func BenchmarkSortedVar(b *testing.B)  { benchVar(MultipleSummerSorted, b) }

Tags:

construct:add
construct:assignment
construct:break
construct:comment
construct:continue
construct:divide
construct:for-loop
construct:function
construct:if
construct:import
construct:index
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:left-shift
construct:len
construct:method
construct:multiply
construct:number
construct:parameter
construct:return
construct:right-shift
construct:sort
construct:struct
construct:subtract
construct:type-conversion
construct:variable
construct:variadic-function
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:bit-manipulation
technique:bit-shifting
technique:higher-order-functions
uses:sort.Ints

Answer 8 · 2023-11-01T07:09:32.000Z

Exercise: sieve

Code

package sieve

const testVersion = 1

func Sieve(n int) []int {
	primes := []int{}
	sieve := make([]bool, n)

	for p := 2; p < n; p++ {
		if !sieve[p] {
			// element p is prime if value at index p in sieve is false
			primes = append(primes, p)
			for multiple := p * 2; multiple < n; multiple += p {
				// filter out multiples of primes
				sieve[multiple] = true
			}
		}
	}

	return primes
}

Tags:

construct:assignment
construct:boolean
construct:comment
construct:const
construct:for-loop
construct:func
construct:if
construct:indexing
construct:int
construct:integral-number
construct:invocation
construct:make
construct:package
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:reflective
technique:looping

Answer 9 · 2023-11-01T07:09:38.000Z

Exercise: protein-translation

Code

package protein

const testVersion = 1

var mappings = map[string]string{
	"AUG": "Methionine",
	"UUU": "Phenylalanine",
	"UUC": "Phenylalanine",
	"UUA": "Leucine",
	"UUG": "Leucine",
	"UCU": "Serine",
	"UCC": "Serine",
	"UCA": "Serine",
	"UCG": "Serine",
	"UAU": "Tyrosine",
	"UAC": "Tyrosine",
	"UGU": "Cysteine",
	"UGC": "Cysteine",
	"UGG": "Tryptophan",
	"UAA": "STOP",
	"UAG": "STOP",
	"UGA": "STOP",
}

func FromCodon(input string) string {
	return mappings[input]
}

func FromRNA(input string) []string {
	size := len(input) / 3

	proteins := []string{}
	for i := 0; i < size; i++ {
		protein := FromCodon(input[i*3 : (i+1)*3])
		if protein != "STOP" {
			proteins = append(proteins, protein)
		} else {
			break
		}
	}
	return proteins
}

Tags:

construct:add
construct:assignment
construct:break
construct:const
construct:divide
construct:for-loop
construct:func
construct:if
construct:index
construct:initializer
construct:int
construct:integral-number
construct:invocation
construct:map
construct:multiply
construct:number
construct:package
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:functional
paradigm:object-oriented
technique:looping
uses:map

Answer 10 · 2023-11-01T07:09:44.000Z

Exercise: roman-numerals

Code

package romannumerals

import "strings"

var patterns = [...]string{
	"",             // zero
	"{L}",          // one
	"{L}{L}",       // two
	"{L}{L}{L}",    // three
	"{L}{M}",       // four
	"{M}",          // five
	"{M}{L}",       // six
	"{M}{L}{L}",    // seven
	"{M}{L}{L}{L}", // eight
	"{L}{H}",       // nine
}

var charSets = [...]struct {
	low  string
	mid  string
	high string
}{
	{"M", "V̅", "X̅"}, // thousands
	{"C", "D", "M"},   // hundreds
	{"X", "L", "C"},   // tens
	{"I", "V", "X"},   // ones
}

// ToRomanNumeral converts an integer value to a string of roman numerals
func ToRomanNumeral(arabic int) (roman string) {
	digits := []int{
		(arabic % 10000) / 1000, // thousands
		(arabic % 1000) / 100,   // hundreds
		(arabic % 100) / 10,     // tens
		(arabic % 10) / 1,       // ones
	}

	for i := 0; i < 4; i++ {
		r := strings.NewReplacer(
			"{L}", charSets[i].low,
			"{M}", charSets[i].mid,
			"{H}", charSets[i].high,
		)
		roman += r.Replace(patterns[digits[i]])
	}

	return
}

Tags:

construct:assignment
construct:char
construct:comment
construct:divide
construct:for-loop
construct:function
construct:implicit-conversion
construct:index
construct:initializer
construct:int
construct:integral-number
construct:invocation
construct:method
construct:number
construct:package
construct:parameter
construct:return
construct:string
construct:struct
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:functional
paradigm:object-oriented
technique:looping
uses:strings.Builder

Answer 11 · 2023-11-01T07:09:50.000Z

Exercise: nth-prime

Code

package prime

// isPrime determine if p is divible by li
func isPrime(p int, li []int, lenN int) bool {
	for i := 0; i < lenN; i++ {
		if p%li[i] == 0 {
			return false

		}
	}
	return true
}

// Nth returns the nth Prime
//
// 1 -> 2, 2 -> 3, 3 -> 5. 4 -> 7
func Nth(n int) (int, bool) {
	var primes = make([]int, n+2)
	primes[0] = 2
	primes[1] = 3
	// check lower bound
	if n < 1 {
		return 0, false
	}
	// initial values
	if n < 3 {
		return primes[n-1], true
	}

	lenN := 2
	posprime := 5
	for {
		if isPrime(posprime, primes, lenN) {
			if lenN+1 == n {
				return posprime, true

			}
			primes[lenN] = posprime
			lenN++
		}
		posprime += 2
		if isPrime(posprime, primes, lenN) {
			if lenN+1 == n {
				return posprime, true
			}
			primes[lenN] = posprime
			lenN++
		}
		posprime += 4
	}
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:comment
construct:for-loop
construct:func
construct:function-invocation
construct:if
construct:implicit-conversion
construct:indexing
construct:int
construct:integral-number
construct:invocation
construct:make
construct:number
construct:parameter
construct:return
construct:subtract
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:looping

Answer 12 · 2023-11-01T07:09:56.000Z

Exercise: ocr-numbers

Code

package ocr

import "strings"

// signatures maps a string signature of a digit to its character form
var signatures = map[string]byte{
	" _ | ||_|   ": '0',
	"     |  |   ": '1',
	" _  _||_    ": '2',
	" _  _| _|   ": '3',
	"   |_|  |   ": '4',
	" _ |_  _|   ": '5',
	" _ |_ |_|   ": '6',
	" _   |  |   ": '7',
	" _ |_||_|   ": '8',
	" _ |_| _|   ": '9',
}

// recognizeDigit attempts to OCR a single digit, returning '?' if not possible
func recognizeDigit(s string) byte {
	n, ok := signatures[s]
	if !ok {
		return '?'
	}
	return n
}

// Recognize converts from digits to recognized string form
func Recognize(given string) []string {
	lines := strings.Split(given[1:], "\n")
	results := []string{}
	// consider 4 lines at a time
	for i := 0; i < len(lines); i += 4 {
		// construct and recognize each digit by its signature
		row := []byte{}
		for j := 0; j < len(lines[0]); j += 3 {
			sig := lines[i][j:j+3] + lines[i+1][j:j+3] + lines[i+2][j:j+3] + lines[i+3][j:j+3]
			row = append(row, recognizeDigit(sig))
		}
		results = append(results, string(row))
	}
	return results
}

Tags:

construct:add
construct:assignment
construct:byte
construct:char
construct:comment
construct:for-loop
construct:func
construct:if
construct:implicit-conversion
construct:indexing
construct:initializer
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:map
construct:number
construct:package
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
technique:looping
uses:map
uses:strings

Answer 13 · 2023-11-01T07:10:03.000Z

Exercise: wordy

Code

package wordy

import (
	"strconv"
	"strings"
)

// Answer takes a worded math question and solves it
func Answer(question string) (int, bool) {

	if strings.HasPrefix(question, "What is ") &&
		!strings.HasSuffix(question, "?") {
		return 0, false
	}

	question = question[8 : len(question)-1]
	question = strings.Replace(question, " by", "", -1)
	chunks := strings.Split(question, " ")

	if len(chunks)%2 == 0 { // malformed question
		return 0, false
	}

	var answer int
	var currentOp string

	for i, chunk := range chunks {

		if i%2 != 0 {
			currentOp = chunk
			continue
		}

		num, err := strconv.Atoi(chunk)
		if err != nil {
			return 0, false
		}

		if i == 0 {
			answer = num
			continue
		}

		switch currentOp {
		case "plus":
			answer += num
		case "minus":
			answer -= num
		case "multiplied":
			answer *= num
		case "divided":
			answer /= num
		}

	}

	return answer, true
}

Tags:

construct:assignment
construct:boolean
construct:comment
construct:continue
construct:for-loop
construct:function
construct:if
construct:import
construct:indexing
construct:int
construct:integral-number
construct:logical-and
construct:method
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:switch
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping
uses:strings.HasPrefix
uses:strings.Replace

Answer 14 · 2023-11-01T07:10:09.000Z

Exercise: saddle-points

Code

package matrix

type Pair [2]int

func (m Matrix) isSaddle(r, c int) bool {
	// Check if m_rc is greater than or equal to every element in its row
	// i.e., m_rc >= m_ri for i in [0, m.nc)
	for i := 0; i < m.nc; i++ {
		if m.v[r*m.nc+c] < m.v[r*m.nc+i] {
			return false
		}
	}
	// Check if m_rc is less than or equal to every element in its column
	// i.e., m_rc <= m_ic for i in [0, m.nr)
	for i := 0; i < m.nr; i++ {
		if m.v[r*m.nc+c] > m.v[i*m.nc+c] {
			return false
		}
	}
	return true
}

func (m Matrix) Saddle() []Pair {
	var saddles []Pair
	for r := 0; r < m.nr; r++ {
		for c := 0; c < m.nc; c++ {
			if m.isSaddle(r, c) {
				saddles = append(saddles, Pair{r, c})
			}
		}
	}
	return saddles
}

Tags:

construct:assignment
construct:boolean
construct:comment
construct:for-loop
construct:function
construct:if
construct:int
construct:integral-number
construct:invocation
construct:method
construct:multiply
construct:number
construct:parameter
construct:return
construct:struct
construct:type-conversion
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:looping

Answer 15 · 2023-11-01T07:10:15.000Z

Exercise: all-your-base

Code

package allyourbase

const testVersion = 1

type Error string

func (e Error) Error() string { return string(e) }

const ErrInvalidDigit = Error("Invalid Digit")
const ErrInvalidBase = Error("Invalid Base")

func convertToUInt(inputBase uint64, inputDigits []uint64) (num uint64, err error) {
	var power uint64 = 1
	for i := len(inputDigits) - 1; i >= 0; i-- {
		if inputDigits[i] >= inputBase {
			err = ErrInvalidDigit
			return
		}
		num += inputDigits[i] * power
		power *= inputBase
	}
	return
}

func convertToBase(input uint64, outputBase uint64) (outputDigits []uint64) {
	var power uint64 = 1
	for true {
		digit := (input % (power * outputBase)) / power
		outputDigits = append([]uint64{digit}, outputDigits...)
		input -= digit * power
		if input <= 0 {
			break
		}
		power *= outputBase
	}
	return
}

func ConvertToBase(inputBase uint64, inputDigits []uint64, outputBase uint64) (outputDigits []uint64, err error) {
	var base2 uint64
	if inputBase < 2 || outputBase < 2 {
		err = ErrInvalidBase
		return
	}
	base2, err = convertToUInt(inputBase, inputDigits)
	if err != nil {
		return
	}
	outputDigits = convertToBase(base2, outputBase)
	return
}

Tags:

construct:assignment
construct:boolean
construct:break
construct:const
construct:constructor
construct:divide
construct:for-loop
construct:function
construct:if
construct:implicit-conversion
construct:index
construct:initializer
construct:int
construct:integral-number
construct:invocation
construct:logical-or
construct:method
construct:multiply
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:type-conversion
construct:typed-boolean
construct:typed-constant
construct:typed-number
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping

Answer 16 · 2023-11-01T07:10:21.000Z

Exercise: variable-length-quantity

Code

package variablelengthquantity

// DecodeVarint take a VLQ slice of bytes and converts it to an integer
func DecodeVarint(data []byte) (uint32, int) {
	var i uint32
	size := 0
	for _, b := range data {

		i += uint32(b & 0x7F)
		if b&0x80 != 0 {
			i <<= 7
			size++
		}
	}

	if size == 0 {
		size++
	}
	return i, size
}

// EncodeVarint takes an integer and converts it to a VLQ byte slice
func EncodeVarint(i uint32) (data []byte) {
	first := true
	for ; i != 0; i >>= 7 {

		b := byte(i & 0x7F)
		if !first {
			b |= 0x80
		}

		// append byte to first of slice
		data = append([]byte{b}, data...)
		first = false
	}
	return data
}

Tags:

construct:assignment
construct:bitwise-and
construct:boolean
construct:byte
construct:comment
construct:for-loop
construct:function
construct:hexadecimal-number
construct:if
construct:initializer
construct:int
construct:integral-number
construct:invocation
construct:logical-not
construct:number
construct:package
construct:return
construct:shift-left
construct:slice
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:reflective
technique:bit-manipulation
technique:boolean-logic
technique:looping

Answer 17 · 2023-11-01T07:10:27.000Z

Exercise: zebra-puzzle

Code

package zebra

import "bytes"

//Solution structure to return solution in consistent way
type Solution struct {
	DrinksWater string
	OwnsZebra   string
}

//generate all permuations from byte slice, code from stack exchange
func permutations(arr []byte) [][]byte {
	var helper func([]byte, int)
	res := [][]byte{}

	helper = func(arr []byte, n int) {
		if n == 1 {
			tmp := make([]byte, len(arr))
			copy(tmp, arr)
			res = append(res, tmp)
		} else {
			for i := 0; i < n; i++ {
				helper(arr, n-1)
				if n%2 == 1 {
					tmp := arr[i]
					arr[i] = arr[n-1]
					arr[n-1] = tmp
				} else {
					tmp := arr[0]
					arr[0] = arr[n-1]
					arr[n-1] = tmp
				}
			}
		}
	}
	helper(arr, len(arr))
	return res
}

//Absolute value function
func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

//Map bytes to full nation names for the solution
var nationMap = map[byte]string{'E': "Englishman", 'S': "Spaniard", 'U': "Ukranian", 'J': "Japanese", 'N': "Norwegian"}

//SolvePuzzle solves the zebra puzzle
func SolvePuzzle() Solution {
	nations := []byte{'E', 'S', 'U', 'J', 'N'}
	drinks := []byte{'w', 'c', 't', 'o', 'm'}
	houses := []byte{'r', 'g', 'b', 'y', 'i'}
	smokes := []byte{'o', 'k', 'c', 'l', 'p'}
	pets := []byte{'z', 's', 'f', 'h', 'd'}
	for _, n := range permutations(nations) {
		if bytes.IndexByte(n, 'N') != 0 {
			//Norwegian lives in first house
			continue
		}
		for _, d := range permutations(drinks) {
			if bytes.IndexByte(d, 'm') != 2 {
				//Milk in middle house
				continue
			}
			if bytes.IndexByte(n, 'U') != bytes.IndexByte(d, 't') {
				//Ukrainian drinks tea
				continue
			}
			for _, h := range permutations(houses) {
				if bytes.IndexByte(h, 'g') != bytes.IndexByte(h, 'i')+1 {
					//green is right of ivory
					continue
				}
				if bytes.IndexByte(n, 'E') != bytes.IndexByte(h, 'r') {
					//English in red
					continue
				}
				if bytes.IndexByte(d, 'c') != bytes.IndexByte(h, 'g') {
					//coffee drinker in green
					continue
				}
				if abs(bytes.IndexByte(n, 'N')-bytes.IndexByte(h, 'b')) != 1 {
					//norweigain next to blue
					continue
				}
				for _, s := range permutations(smokes) {
					if bytes.IndexByte(h, 'y') != bytes.IndexByte(s, 'k') {
						//kools smoker in yellow
						continue
					}
					if bytes.IndexByte(s, 'l') != bytes.IndexByte(d, 'o') {
						//lucky strike drinks orange
						continue
					}
					if bytes.IndexByte(s, 'p') != bytes.IndexByte(n, 'J') {
						//Japanese smokes parliaments
						continue
					}
					for _, p := range permutations(pets) {
						if bytes.IndexByte(s, 'o') != bytes.IndexByte(p, 's') {
							//old gold has snails
							continue
						}
						if bytes.IndexByte(n, 'S') != bytes.IndexByte(p, 'd') {
							//spaniard has dog
							continue
						}
						if abs(bytes.IndexByte(s, 'c')-bytes.IndexByte(p, 'f')) != 1 {
							//chesterfieled next to fox
							continue
						}
						if abs(bytes.IndexByte(s, 'k')-bytes.IndexByte(p, 'h')) != 1 {
							//kools next to horse
							continue
						}
						return Solution{
							DrinksWater: nationMap[n[bytes.IndexByte(d, 'w')]],
							OwnsZebra:   nationMap[n[bytes.IndexByte(p, 'z')]],
						}
					}
				}
			}
		}
	}
	panic("No solution found, this can't happen!")
}

Tags:

construct:add
construct:append
construct:assignment
construct:byte
construct:comment
construct:constructor
construct:continue
construct:for-loop
construct:func
construct:function-type
construct:if
construct:implicit-conversion
construct:index
construct:initializer
construct:int
construct:integral-number
construct:invocation
construct:lambda
construct:map
construct:method
construct:number
construct:package
construct:parameter
construct:return
construct:string
construct:struct
construct:subtract
construct:type-conversion
construct:type-embedding
construct:type
construct:variable
construct:visibility-modifiers
paradigm:functional
paradigm:imperative
paradigm:object-oriented
technique:higher-order-functions
technique:looping
technique:recursion
uses:map

Answer 18 · 2023-11-01T07:10:33.000Z

Exercise: rectangles

Code

package rectangles

const corner = '+'
const vertical = '|'

// Count returns the number of reactangles founds
func Count(input []string) int {
	count := 0
	for y1 := 0; y1 < len(input); y1++ {
		row := input[y1]
		for x1 := 0; x1 < len(row); x1++ {
			if row[x1] == corner {
				for x2 := x1 + 1; x2 < len(row); x2++ {
					if row[x2] == corner {
						for y2 := y1 + 1; y2 < len(input); y2++ {
							if (input[y2][x1] != vertical && input[y2][x1] != corner) || (input[y2][x2] != vertical && input[y2][x2] != corner) {
								break
							}
							if input[y2][x1] == corner && input[y2][x2] == corner {
								count++
							}
						}
					}
				}
			}
		}
	}
	return count
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:break
construct:char
construct:comment
construct:const
construct:for-loop
construct:if
construct:indexing
construct:int
construct:integral-number
construct:logical-and
construct:logical-or
construct:nested-loop
construct:number
construct:package
construct:return
construct:string
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:object-oriented
technique:boolean-logic
technique:looping

Answer 19 · 2023-11-01T07:10:39.000Z

Exercise: counter

Code

package counter

import (
	"testing"
)

// Define your tests here

var (
	cases = []struct {
		s string
		//Cumulative lines, letters, characters including previous cases
		expectedLines, expectedLetters, expectedCharacters int
	}{
		{"hello ", 1, 5, 6},
		{"\n go away", 2, 11, 15},
		{" pay me ", 2, 16, 23},
		{" have $4", 2, 20, 31},
		{"\n\t bye.", 3, 23, 38},
		{"香Ή", 3, 25, 40},
	}
)

func TestAddString(t *testing.T) {
	ctr := makeCounter()
	ctr.AddString("boom")
	ctr.AddString("")
	ctr.AddString(" smile")
}

func TestLines(t *testing.T) {
	ctr := makeCounter()
	for _, c := range cases {
		ctr.AddString(c.s)
		actualLines := ctr.Lines()
		if actualLines != c.expectedLines {
			t.Errorf("Counter.Lines() returns %d, want %d", actualLines, c.expectedLines)
		}
	}
}

func TestLetters(t *testing.T) {
	ctr := makeCounter()
	for _, c := range cases {
		ctr.AddString(c.s)
		actualLetters := ctr.Letters()
		if actualLetters != c.expectedLetters {
			t.Errorf("Counter.Letters() returns %d, want %d", actualLetters, c.expectedLetters)
		}
	}
}

func TestCharacters(t *testing.T) {
	ctr := makeCounter()
	for _, c := range cases {
		ctr.AddString(c.s)
		actualCharacters := ctr.Characters()
		if actualCharacters != c.expectedCharacters {
			t.Errorf("Counter.Characters() returns %d, want %d", actualCharacters, c.expectedCharacters)
		}
	}
}

Tags:

construct:string
construct:assignment
construct:comment
construct:for-loop
construct:func
construct:if
construct:import
construct:int
construct:integral-number
construct:invocation
construct:method
construct:package
construct:range
construct:struct
construct:testing
construct:variable
construct:visibility-modifiers
paradigm:imperative
paradigm:reflective
technique:looping

Answer 20 · 2023-11-01T07:10:45.000Z

Exercise: hexadecimal

Code

package hexadecimal

// ToDecimal converts a string representing a hexadecimal number into
// an int64. If the string contains invalid digits, the result is 0.
func ToDecimal(digits string) int64 {
	var result, value int64
	exponent := uint(4 * len(digits))
	for _, d := range digits {
		exponent -= 4
		switch {
		case d >= '0' && d <= '9':
			value = int64(d - '0')
		case d >= 'a' && d <= 'f':
			value = int64(d - 'a' + 10)
		case d >= 'A' && d <= 'F':
			value = int64(d - 'A' + 10)
		default:
			return 0
		}
		result += value * (1 << exponent)
	}
	return result
}

Tags:

construct:add
construct:assignment
construct:boolean
construct:case
construct:comment
construct:for-loop
construct:if
construct:int
construct:int64
construct:integral-number
construct:invocation
construct:left-shift
construct:len
construct:logical-and
construct:method
construct:multiply
construct:number
construct:parameter
construct:return
construct:string
construct:subtract
construct:switch
construct:variable
construct:visibility
paradigm:imperative
paradigm:procedural
technique:bit-manipulation
technique:bit-shifting
technique:boolean-logic
technique:looping

Answer 21 · 2023-11-14T12:42:47.000Z

This is an automated comment

Hello 👋 Next week we're going to start using the tagging work people are doing on these. If you've already completed the work, thank you! If you've not, but intend to this week, that's great! If you're not going to get round to doing it, and you've not yet posted a comment letting us know, could you please do so, so that we can find other people to do it. Thanks!

Answer 22 · 2023-11-23T22:01:51.000Z

Sorry, I don't have time to work on this.