kirarpit
commented
6 years ago Well here is the way I did it but I'm sure it could be better.
First I computed the list of 5 digit numbers upto '44444' because after that, by symmetry we can produce the result for higher numbers ourselves. For example, score of 44445 would be same as the score of 44443.
def myFunc(s):
if (not len(s) or int(s) <= int('4'*len(s))) and len(s) == 5:
print(s)
if len(s) and len(s) == 5:
return
for i in range(1, 8):
myFunc(s + str(i))
myFunc("")Next, I fed these number strings to the program to get a score for each of them. It took about 12 hours on my 2013 MacBook Pro. Note, if we have scores for all these numbers then we can compute the score of any other number smaller than 777777. Although, this way the program caching is not being used at its fullest since every number that we compute would have a different subTree. That's why I think it could be better.
import os, pickle, time
start = time.time()
WIDTH = 7
fname = '5set'
sols = {}
def saveDict(sols):
with open('dict', 'wb') as handle:
pickle.dump(sols, handle, protocol=pickle.HIGHEST_PROTOCOL)
def mirror(e):
j = ""
for i in e:
j += str(8 - int(i))
return j
if os.path.exists(fname):
with open(fname) as f:
content = f.readlines()
for x in content:
line = x.split()
sols[line[0]] = int(line[1])
sols[mirror(line[0])] = int(line[1])
def myFunc(sttr):
if sttr in sols: return int(sols[sttr])
score = float("+inf")
for i in range(1, WIDTH + 1):
score = min(score, myFunc(sttr + str(i)))
sols[sttr] = -1 * score
return sols[sttr]
sttr = ""
myFunc(sttr)
saveDict(sols)
print("Time taken: " + str(time.time() - start))And, finally this is what my main function in main.cpp file looks like
int main() {
Solver solver;
std::string line;
for(int l = 1; std::getline(std::cin, line); l++) {
Position P;
if(P.play(line) == line.size()) {
int score = solver.solve(P, false);
std::cout << line << " " << score ;
}
std::cout << std::endl;
}
}
PascalPons
Hey, is there an efficient way to return the scores of next possible moves just the way it's done on the website under "Show Solution"?
One way is to call the entire program 7 times with the updated strings but that's making it slower. What I believe is that we can return that in a single call but I'm not able to figure it out how since I'm not very familiar with the bitmap.
Any help would be highly appreciated! Thanks!
UPDATE: I am able to figure out how the bit masking is working, thanks to your blog post. I can now modify the code to return all possible moves with their scores but it's still going to be quite slow for initial moves specifically.
I read that you precomputed the opening data for the standard 6X7 board on the server which is why you're able to return results that fast. Can you please provide some information regarding how I could do the same on my system?
Thanks!