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
|
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")
var sum = 0
var seg = []int{}
func build(a *sql.Rows, l, r, n int) {
if l == r {
a.Next()
a.Scan(&seg[n])
sum += seg[n]
return
}
m := (l + r) >> 1
build(a, l, m, n<<1)
build(a, m+1, r, n<<1|1)
seg[n] = seg[n<<1] + seg[n<<1|1]
}
func update(x, v, l, r, n int) {
if l == r {
seg[n] = v
return
}
m := (l + r) >> 1
if x <= m {
update(x, v, l, m, n<<1)
} else {
update(x, v, m+1, r, n<<1|1)
}
seg[n] = seg[n<<1] + seg[n<<1|1]
}
func query(v, l, r, n int) (int, int) {
if l == r {
return seg[n], l
}
m := (l + r) >> 1
if seg[n<<1] >= v {
return query(v, l, m, n<<1)
} else {
return query(v-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)
seg = make([]int, 4*N)
// Build segment tree
rows, err := db.Query("SELECT weight FROM cards")
if err != nil {
panic(err)
}
build(rows, 0, N-1, 1)
rows.Close()
if *verbose {
fmt.Println(N)
fmt.Println(seg)
}
// 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 := 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
update(i, w, 0, N-1, 1)
_, err = db.Exec("UPDATE cards SET weight=? WHERE idx=?", w, i)
if err != nil {
panic(err)
}
}
}
|
