-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathgreater_than_ideas.txt
More file actions
140 lines (112 loc) · 4.66 KB
/
Copy pathgreater_than_ideas.txt
File metadata and controls
140 lines (112 loc) · 4.66 KB
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
138
139
140
3 4 1 7 10 6 5 8 9 2
^
HEAD
- - x x x - - - - - => 3
- - x x - - - x x - => 4
3 4 1 7 10 6 5 8 9 2
^
HEAD
x x - x x - - - - x => 5
x x - x - - - x x x => 6
12 6 2 10 8 4 16 7 18 13 1 9 5 3 14 19 15 11 17 20
^
HEAD
- - - - - - - - - - x x - - x x - - x x => 6
- - - - - - - - - - x x - - x x - - x x => 6
- - - - - - - - - - x x - - x - x - x x => 6
- - - - - - - - - - x - x - x - x - x x => 6
- - - - - - - - - - x - - x x - x - x x => 6
12 6 2 10 8 4 16 7 18 13 1 9 5 3 14 19 15 11 17 20
^
HEAD
- - x x - - x - x - - - - - - x - - - x => 6
- - x - - x - x - - - x - - x - x - x x => 8 -->so there are different ways to calculate...
TAIL
v
15 8 20 12 13 17 1 7 4 3 14 18 10 11 2 6 16 19 9 5
^
HEAD
- - x - - - x x - - x x - - - - - x - - => 6
1 7 4 3 14 18 10 11 2 6 16 19 9 5 15 8 20 12 13 17
x x -----yes------> x --no->x --no---> x x x (range = 3)
x x----yes------> x --no->x --no---> x x x
1 7 4 3 14 18 10 11 2 6 16 19 9 5 15 8 20 12 13 17 (range = 4)
x --x-----------------x-------x------------x-x--x
12 19 17 7 3 18 1 8 5 6 14 10 16 13 11 15 4 9 20 2
1 8 5 6 14 10 16 13 11 15 4 9 20 2 12 19 17 7 3 18
y y n y y n y n n y n y n n y y n n n y =>10
1 8 5 6 14 10 16 13 11 15 4 9 20 2 12 19 17 7 3 18
x--------------------------------x------------x--- (range = 1) 3, best = 3
x--------------------------------x------------x--- (range = 2) 3, best = 3
x-------------------------x-----------------x----- (range = 3) 3, best = 3
x---x-x----x-----x-----x--------------x----------- (range = 4) 7
o->x pop the last one
x---x-x----x-----x-----x--------------o--x-----x- 8
x<--o<o<---o<----o<----o<-------------o<-o<-----o no more intermediary incremental values in a range of 4
best = 8
1 8 5 6 14 10 16 13 11 15 4 9 20 2 12 19 17 7 3 18
x---x-x----x-----x-----x-------x------------------ (range = 5) 7
x---x-x----x-----x-----x-------o pop the last one
x---x-x----x-----x-----x-------o------x----------- 7
x---x-x----x-----x-----x-------o----->x pop the last one
x---x-x----x-----x-----x-------o------x----------- 7
x---x-x----x-----x-----x-------o----->o--x pop the last one
x---x-x----x-----x-----x-------o------o--x------x- 8
x<--o<o<---o<----o<----o<-------------o<-o<-----o no more intermediary incremental values in a range of 4
13 27 11 14 12 18 2 23 3 25 28 16 29 19 17 15 20 7 22 9 5 26 30 6 1 8 10 21 4 24
1 8 10 21 4 24 13 27 11 14 12 18 2 23 3 25 28 16 29 19 17 15 20 7 22 9 5 26 30 6
x-x-x--x----x-----x------------------------x-----x--------------------------x--- 9
x-x-x--x----o<----c<-----------------------c<----c<-------------------------c 'c'= continue; can't be popped, b/c no intermediary value
x-x-x--x----o-----o----------------x----x--x-----x--------------------------x--- 9
x-x-x--o<--------------------------c<---c<-c<----c<-------------------------c 'c'= continue; can't be popped, b/c no intermediary value
Calculate max nb of staying values:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 141516 17 1819
15 8 20 12 13 17 1 7 4 3 14 18 10 11 2 6 16 19 9 5
^
HEAD
y n y n y y y y n n y y n y n y y y n n => 12.
I believe this gives a good ballpark of theoretical max, but it almost always gonna be less than this
1. Map values to their positions ! This way you have a lookup table and don't have to iterate through values
e.g.
val_pos[1] : 6
val_pos[2] : 14
val_pos[3] : 9
(...)
val_pos[19] : 17
val_pos[20] : 2
They could all be iterators, so that they're easy to commonly increment/decrement. Should not be done more than a max of nb_vals times anyways
could store a max_value_left variable to check if max_value_left - curr_value + nb_increasing >
new stack:
15 20 13 17 1 7 14 18 11 6 16 19 ---->DOESN'T WORK, b/c you might want to exclude some of them, therefore including some that are not there rn
temp result for 100 with up to 3
with delta_values:
1.
Nb tests done: 1000
Average nb of moves: 575
Worst nb of moves: 639
Nb of moves above 575 : 507
2.
Nb tests done: 1000
Average nb of moves: 576
Worst nb of moves: 651
Nb of moves above 575 : 524
without delta_values
1.
Nb tests done: 1000
Average nb of moves: 580
Worst nb of moves: 649
Nb of moves above 575 : 567
2.
Nb tests done: 1000
Average nb of moves: 581
Worst nb of moves: 657
Nb of moves above 575 : 573
5500:
Average nb of moves: 5155
(Test #414) Worst nb of moves: 5534
Nb of moves above 5304 : 125
Nb tests done: 5001
Average nb of moves: 5169
(Test #2538) Worst nb of moves: 5634
Nb of moves above 5500 : 22
for now seems to reduce the nb of the max_moves, but could be an outlier