Lucky tickets (#171)

SirBogman · web-flow · commit d386360cb924 · 2020-04-14T02:20:14.000+01:00
* Add the lucky-tickets hole.

Note that the algorithm used in lucky-tickets.go is not the most efficient algorithm, but it is only used to generate the results for the random test cases and typically runs in less than 20 milliseconds. For the longest test case, it took about 2.5 seconds to generate the result on my machine, so I am including the precomputed result for performance. For many languages, a better algorithm will be required to solve the hole within the time constraint.

* hole/hole.go: Reduce complexity of the Play function.
diff --git a/db/0.schema.sql b/db/0.schema.sql
@@ -4,7 +4,7 @@ CREATE TYPE hole AS ENUM (
     '12-days-of-christmas', '99-bottles-of-beer', 'abundant-numbers',
     'arabic-to-roman', 'brainfuck', 'christmas-trees', 'cubes', 'diamonds',
     'divisors', 'emirp-numbers', 'evil-numbers', 'fibonacci', 'fizz-buzz',
-    'happy-numbers', 'leap-years', 'morse-decoder', 'morse-encoder',
+    'happy-numbers', 'leap-years', 'lucky-tickets', 'morse-decoder', 'morse-encoder',
     'niven-numbers', 'odious-numbers', 'ordinal-numbers', 'pangram-grep',
     'pascals-triangle', 'pernicious-numbers', 'poker', 'prime-numbers',
     'quine', 'rock-paper-scissors-spock-lizard', 'roman-to-arabic',
diff --git a/hole/hole.go b/hole/hole.go
@@ -21,37 +21,46 @@ type Scorecard struct {
 	Took           time.Duration
 }
 
-func Play(ctx context.Context, holeID, langID, code string) (score Scorecard) {
+func getAnswer(holeID, code string) ([]string, string) {
+	var answer string
+	var args []string
 	switch holeID {
 	case "arabic-to-roman", "roman-to-arabic":
-		score.Args, score.Answer = arabicToRoman(holeID == "roman-to-arabic")
+		args, answer = arabicToRoman(holeID == "roman-to-arabic")
 	case "brainfuck":
-		score.Args, score.Answer = brainfuck()
+		args, answer = brainfuck()
+	case "lucky-tickets":
+		args, answer = luckyTickets()
 	case "morse-decoder", "morse-encoder":
-		score.Args, score.Answer = morse(holeID == "morse-decoder")
+		args, answer = morse(holeID == "morse-decoder")
 	case "ordinal-numbers":
-		score.Args, score.Answer = ordinalNumbers()
+		args, answer = ordinalNumbers()
 	case "pangram-grep":
-		score.Args, score.Answer = pangramGrep()
+		args, answer = pangramGrep()
 	case "poker":
-		score.Args, score.Answer = poker()
+		args, answer = poker()
 	case "quine":
-		score.Answer = code
+		answer = code
 	case "rock-paper-scissors-spock-lizard":
-		score.Args, score.Answer = rockPaperScissorsSpockLizard()
+		args, answer = rockPaperScissorsSpockLizard()
 	case "seven-segment":
-		score.Args, score.Answer = sevenSegment()
+		args, answer = sevenSegment()
 	case "spelling-numbers":
-		score.Args, score.Answer = spellingNumbers()
+		args, answer = spellingNumbers()
 	case "sudoku":
-		score.Args, score.Answer = sudoku()
+		args, answer = sudoku()
 	case "ten-pin-bowling":
-		score.Args, score.Answer = tenPinBowling()
+		args, answer = tenPinBowling()
 	case "united-states":
-		score.Args, score.Answer = unitedStates()
+		args, answer = unitedStates()
 	default:
-		score.Answer = answers[holeID]
+		answer = answers[holeID]
 	}
+	return args, answer
+}
+
+func Play(ctx context.Context, holeID, langID, code string) (score Scorecard) {
+	score.Args, score.Answer = getAnswer(holeID, code)
 
 	var stderr, stdout bytes.Buffer
 
diff --git a/hole/lucky-tickets.go b/hole/lucky-tickets.go
@@ -0,0 +1,86 @@
+package hole
+
+import (
+	"math/rand"
+	"strconv"
+	"strings"
+)
+
+type Ticket struct {
+	digits int
+	base   int
+	result int64
+}
+
+var data = []Ticket{
+	{8, 2, 70},
+	{4, 8, 344},
+	{2, 10, 10},
+	{4, 10, 670},
+	{6, 10, 55252},
+	{14, 12, 39222848622984},
+}
+
+func iPow(a, b int64) int64 {
+	var result int64 = 1
+	for b != 0 {
+		if b&1 != 0 {
+			result *= a
+		}
+		b >>= 1
+		a *= a
+	}
+	return result
+}
+
+func sumDigits(number int64, base int64) int64 {
+	var result int64
+	for number > 0 {
+		result += number % base
+		number /= base
+	}
+	return result
+}
+
+func luckyTickets() ([]string, string) {
+	tickets := make([]Ticket, len(data))
+	copy(tickets, data)
+
+	// Randomly generate additional test cases.
+	for i := 0; i < 5; i++ {
+		digits := 2 + 2*rand.Intn(5)
+		base := 2 + rand.Intn(15)
+
+		halfValue := iPow(int64(base), int64(digits/2))
+		maxSum := (base - 1) * digits / 2
+		counts := make([]int64, maxSum+1)
+		var j int64
+		for ; j < halfValue; j++ {
+			counts[sumDigits(j, int64(base))] += 1
+		}
+
+		var result int64
+		for _, count := range counts {
+			result += count * count
+		}
+
+		tickets = append(tickets, Ticket{digits, base, result})
+	}
+
+	args := make([]string, len(tickets))
+	outs := make([]string, len(tickets))
+
+	for i, item := range tickets {
+		args[i] = strconv.Itoa(item.digits) + " " + strconv.Itoa(item.base)
+		outs[i] = strconv.FormatInt(item.result, 10)
+	}
+
+	// Shuffle
+	for i := range args {
+		j := rand.Intn(i + 1)
+		args[i], args[j] = args[j], args[i]
+		outs[i], outs[j] = outs[j], outs[i]
+	}
+
+	return args, strings.Join(outs, "\n")
+}
diff --git a/holes.toml b/holes.toml
@@ -358,6 +358,15 @@ preamble = '''
     to and including <b>2400</b>.
 '''
 
+['Lucky Tickets']
+category = 'Mathematics'
+preamble = '''
+<p>
+    In Russia, bus tickets numbers consist of 6 decimal digits. It is considered lucky when the sum of the first three digits equals the sum of the last three digits. The concept of lucky tickets can be extended to ticket numbering systems with even numbers of digits and arbitrary bases.
+<p>
+    Each argument describes a ticket numbering system and consists of two numbers separated by a space. The first is the even number of digits. The second is the base of the numbering system (2-16). For each argument, output the total number of lucky tickets for the numbering system on a separate line.
+'''
+
 ['Morse Decoder']
 category = 'Transform'
 preamble = '''
