1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
package main
import (
"database/sql"
"flag"
"fmt"
"math/rand"
"os"
"os/exec"
_ "modernc.org/sqlite"
)
var verbose = flag.Bool("v", false, "debug output")
var file = flag.String("f", "cards", "cards file")
type segmentTree struct {
N int
seg []int
}
// Build segment tree
func (s segmentTree) build(a *sql.Rows, l, r, n int) {
if l == r {
a.Next()
a.Scan(&s.seg[n])
return
}
m := (l + r) >> 1
s.build(a, l, m, n<<1)
s.build(a, m+1, r, n<<1|1)
s.seg[n] = s.seg[n<<1] + s.seg[n<<1|1]
}
// Update value at index x
func (s segmentTree) update(x, v, l, r, n int) {
if l == r {
s.seg[n] = v
return
}
m := (l + r) >> 1
if x <= m {
s.update(x, v, l, m, n<<1)
} else {
s.update(x, v, m+1, r, n<<1|1)
}
s.seg[n] = s.seg[n<<1] + s.seg[n<<1|1]
}
// Find element with prefix sum v
func (s segmentTree) query(v, l, r, n int) (int, int) {
if l == r {
return s.seg[n], l
}
m := (l + r) >> 1
if s.seg[n<<1] >= v {
return s.query(v, l, m, n<<1)
} else {
return s.query(v-s.seg[n<<1], m+1, r, n<<1|1)
}
}
func main() {
flag.Parse()
db, err := sql.Open("sqlite", *file)
if err != nil {
panic(err)
}
// Get number of cards
var N int
_ = db.QueryRow("SELECT COUNT(*) FROM cards").Scan(&N)
s := segmentTree{N, make([]int, 4*N)}
// Build segment tree
rows, err := db.Query("SELECT weight FROM cards")
if err != nil {
panic(err)
}
s.build(rows, 0, N-1, 1)
sum := s.seg[1]
rows.Close()
if *verbose {
fmt.Println(s)
}
// https://stackoverflow.com/questions/14094190/function-similar-to-getchar
// disable input buffering
exec.Command("stty", "-F", "/dev/tty", "cbreak", "min", "1").Run()
// do not display entered characters on the screen
exec.Command("stty", "-F", "/dev/tty", "-echo").Run()
// restore the echoing state when exiting
defer exec.Command("stty", "-F", "/dev/tty", "echo").Run()
for {
// Choose a random card
x := rand.Intn(sum)
if *verbose {
fmt.Println(sum)
fmt.Println(x)
}
w, i := s.query(x, 0, N-1, 1)
fmt.Println(w)
fmt.Println(i)
// Get card contents from database
var key, val string
db.QueryRow("SELECT key, val FROM cards WHERE idx=?", i).Scan(&key, &val)
fmt.Println(key)
// Wait for confirmation
var b []byte = make([]byte, 1)
os.Stdin.Read(b)
fmt.Println(val)
// Read user input
os.Stdin.Read(b)
if b[0] == byte('y') {
w >>= 1
sum -= w
} else if b[0] == byte('n') {
sum += w
w <<= 1
} else {
os.Exit(0)
}
// Update segment tree and database
s.update(i, w, 0, N-1, 1)
_, err = db.Exec("UPDATE cards SET weight=? WHERE idx=?", w, i)
if err != nil {
panic(err)
}
}
}
|
