HOG2
PermutationPuzzleEnvironment.h
Go to the documentation of this file.
1 #include <assert.h>
2 #include <iostream>
3 #include <fstream>
4 #include <map>
5 #include <stdint.h>
6 #include <cstdlib>
7 #include <cstdio>
8 #include <thread>
9 #include <deque>
10 #include "SearchEnvironment.h"
11 #include "Timer.h"
12 #include "SharedQueue.h"
13 #include "RangeCompression.h"
14 #include "MR1Permutation.h"
15 
16 #ifndef PERMPUZZ_H
17 #define PERMPUZZ_H
18 
19 #pragma mark -
20 #pragma mark Declarations
21 #pragma mark -
22 
23 namespace PermutationPuzzle {
24 
25  template <class state, class action>
26  class PermutationPuzzleEnvironment;
27 
28  enum PDBTreeNodeType {
29  kMaxNode,
30  kAddNode,
31  kLeafNode,
32  kLeafMinCompress,
33  kLeafFractionalCompress,
34  kLeafFractionalModCompress,
35  kLeafModCompress,
36  kLeafValueCompress,
37  kLeafDivPlusDeltaCompress, // two lookups with the same index, one is div, one is delta
38  kLeafDefaultHeuristic
39  };
40 
41  struct PDBTreeNode
42  {
43  PDBTreeNodeType t;
44  uint8_t numChildren;
45  uint8_t firstChildID;
46  uint8_t PDBID;
47  };
48 
49  const uint64_t kDone = -1;
50 
55  template <class state, class action>
56  class PermutationPuzzleEnvironment : public SearchEnvironment<state, action>
57  {
58  public:
59  PermutationPuzzleEnvironment()
60  :maxItem(0), minPattern(100), additive(false) {}
61 
62  double HCost(const state &s) const;
63  virtual double AdditiveGCost(const state &s, const action &d)
64  { assert(!"Additive Gost used but not defined for this class\n"); }
65 
66  void GetStateFromHash(state &s, uint64_t hash) const;
67  uint64_t GetStateHash(const state &s) const;
68  static uint64_t Hash(const state &s)
69  {
70  MR1KPermutation mr1;
71  state tmp = s;
72  state dual;
73  for (size_t x = 0; x < tmp.size(); x++)
74  dual.puzzle[tmp.puzzle[x]] = x;
75  return mr1.Rank(tmp.puzzle, dual.puzzle, s.size(), s.size());
76  }
77 
78  state TranformToStandardGoal(const state &a, const state &b) const;
79  virtual void FinishUnranking(state &s) const {}
80 // void PrintPDBHistogram(int which) const;
81 // void GetPDBHistogram(int which, std::vector<uint64_t> &values) const;
82 
83  static bool Check_Permutation(const std::vector<int> &to_check);
84  static bool Output_Puzzles(std::vector<state> &puzzle_vector, bool write_puzz_num);
85  static bool Read_In_Permutations(const char *filename, unsigned size, unsigned max_puzzles,
86  std::vector<std::vector<int> > &permutations, bool puzz_num_start);
87  static std::vector<int> Get_Random_Permutation(unsigned size);
88 
89 
90  private:
91 // void DeltaWorker(std::vector<uint8_t> *array,
92 // std::vector<int> *distinct,
93 // int puzzleSize,
94 // uint64_t start, uint64_t end);
95 // void ThreadWorker(int depth, int totalTiles,
96 // std::vector<uint8_t> *DB,
97 // //std::vector<uint8_t> *coarseOpen,
98 // const std::vector<int> *distinct,
99 // SharedQueue<std::pair<uint64_t, uint64_t> > *work,
100 // SharedQueue<uint64_t> *results,
101 // std::mutex *lock,
102 // bool additive);
103 // double HCost(const state &s, int treeNode,
104 // std::vector<int> &c1, std::vector<int> &c2) const;
105  virtual double DefaultH(const state &s) const { return 0; }
106  void buildCaches() const;
107 
108  protected:
109  uint64_t Factorial(int val) const;
110  uint64_t nUpperk(int n, int k) const;
111 
112 
119  virtual bool State_Check(const state &to_check) = 0;
120 
121  public:
122  bool Validate_Problems(std::vector<state> &puzzles);
123 
124  bool additive;
125  int maxItem, minPattern;
126  // holds a set of Pattern Databases which can be maxed over later
127  std::vector<std::vector<uint8_t> > PDB;
128  // holds the set of distinct items used to build the associated PDB (and therefore needed for hashing)
129  std::vector<std::vector<int> > PDB_distincts;
130  std::vector<PDBTreeNode> lookups;
131  mutable std::vector<std::vector<uint64_t> > factorialCache;
132 
133  MR1KPermutation mr1;
134  };
135 
136  template <typename state, typename environment>
137  class ArbitraryGoalPermutation : public Heuristic<state> {
138  public:
139  ArbitraryGoalPermutation(Heuristic<state> *h, environment *env) { this->h = h; e = env; }
140  virtual double HCost(const state &a, const state &b) const
141  { state g; return h->HCost(e->TranformToStandardGoal(a, b), g); }
142  private:
143  Heuristic<state> *h;
144  environment *e;
145  };
146 
147 //#pragma mark -
148 //#pragma mark Implementation - In-Memory Operations
149 //#pragma mark -
150 //
151 // template <class state, class action>
152 // void PermutationPuzzleEnvironment<state, action>::Min_Compress_PDB(int whichPDB, int factor, bool print_histogram)
153 // {
154 // printf("Performing min compression, reducing from %lu entries to %lu entries\n",
155 // PDB[whichPDB].size(), (PDB[whichPDB].size()+factor-1)/factor);
156 // std::vector<uint8_t> newPDB((PDB[whichPDB].size()+factor-1)/factor);
157 // for (uint64_t x = 0; x < PDB[whichPDB].size(); x+=factor)
158 // {
159 // int minVal = PDB[whichPDB][x];
160 // for (uint64_t y = 1; y < factor; y++)
161 // {
162 // if (x+y < PDB[whichPDB].size())
163 // minVal = min(minVal, PDB[whichPDB][x+y]);
164 // }
165 // newPDB[x/factor] = minVal;
166 // }
167 // PDB[whichPDB].swap(newPDB);
168 // if (print_histogram)
169 // PrintPDBHistogram(whichPDB);
170 // }
171 //
172 // template <class state, class action>
173 // void PermutationPuzzleEnvironment<state, action>::Fractional_Compress_PDB(int whichPDB, uint64_t count, bool print_histogram)
174 // {
175 // PDB[whichPDB].resize(count);
176 // }
177 //
178 // template <class state, class action>
179 // void PermutationPuzzleEnvironment<state, action>::Fractional_Mod_Compress_PDB(int whichPDB, uint64_t factor,
180 // bool print_histogram)
181 // {
182 // std::vector<uint8_t> newPDB(PDB[whichPDB].size()/factor);
183 // for (int x = 0; x < PDB[whichPDB].size(); x+= factor)
184 // {
185 // newPDB[x/factor] = PDB[whichPDB][x];
186 // }
187 // PDB[whichPDB].swap(newPDB);
188 // if (print_histogram)
189 // PrintPDBHistogram(whichPDB);
190 // }
191 //
192 //
193 // template <class state, class action>
194 // void PermutationPuzzleEnvironment<state, action>::Mod_Compress_PDB(int whichPDB, uint64_t newEntries, bool print_histogram)
195 // {
196 // if (newEntries == 0)
197 // {
198 // printf("Error -- cannot reduce to 0 entries\n");
199 // return;
200 // }
201 // printf("Performing mod compression, reducing from %lu entries to %" PRId64 " entries\n", PDB[whichPDB].size(), newEntries);
202 // std::vector<uint8_t> newPDB(newEntries);
203 // for (uint64_t x = 0; x < newEntries; x++)
204 // newPDB[x] = PDB[whichPDB][x];
205 // for (uint64_t x = newEntries; x < PDB[whichPDB].size(); x++)
206 // newPDB[x%newEntries] = min(newPDB[x%newEntries], PDB[whichPDB][x]);
207 // PDB[whichPDB].swap(newPDB);
208 // if (print_histogram)
209 // PrintPDBHistogram(whichPDB);
210 // }
211 //
212 //
213 // template <class state, class action>
214 // void PermutationPuzzleEnvironment<state, action>::Value_Compress_PDB(int whichPDB, int maxValue, bool print_histogram)
215 // {
216 // for (uint64_t x = 0; x < PDB[whichPDB].size(); x++)
217 // if (PDB[whichPDB][x] > maxValue)
218 // PDB[whichPDB][x] = maxValue;
219 //
220 // if (print_histogram)
221 // PrintPDBHistogram(whichPDB);
222 // }
223 //
224 // template <class state, class action>
225 // void PermutationPuzzleEnvironment<state, action>::Value_Range_Compress_PDB(int whichPDB, int numBits, bool print_histogram)
226 // {
227 // std::vector<uint64_t> dist;
228 // std::vector<int> cutoffs;
229 // GetPDBHistogram(whichPDB, dist);
230 // GetOptimizedBoundaries(dist, 1<<numBits, cutoffs);
231 // printf("Setting boundaries [%d values]: ", (1<<numBits));
232 // for (int x = 0; x < cutoffs.size(); x++)
233 // printf("%d ", cutoffs[x]);
234 // printf("\n");
235 // cutoffs.push_back(256);
236 //
237 // for (uint64_t x = 0; x < PDB[whichPDB].size(); x++)
238 // {
239 // for (int y = 0; y < cutoffs.size(); y++)
240 // {
241 // if (PDB[whichPDB][x] >= cutoffs[y] && PDB[whichPDB][x] < cutoffs[y+1])
242 // {
243 // //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
244 // PDB[whichPDB][x] = cutoffs[y];
245 // break;
246 // }
247 // }
248 // }
249 // if (print_histogram)
250 // PrintPDBHistogram(whichPDB);
251 // }
252 //
253 //
254 // template <class state, class action>
255 // void PermutationPuzzleEnvironment<state, action>::Value_Compress_PDB(int whichPDB, std::vector<int> cutoffs, bool print_histogram)
256 // {
257 //
258 // for (uint64_t x = 0; x < PDB[whichPDB].size(); x++)
259 // {
260 // for (int y = 0; y < cutoffs.size(); y++)
261 // {
262 // if (PDB[whichPDB][x] >= cutoffs[y] && PDB[whichPDB][x] < cutoffs[y+1])
263 // {
264 // //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
265 // PDB[whichPDB][x] = cutoffs[y];
266 // break;
267 // }
268 // }
269 // }
270 //
271 // if (print_histogram)
272 // PrintPDBHistogram(whichPDB);
273 // }
274 //
275 // template <class state, class action>
276 // void PermutationPuzzleEnvironment<state, action>::Delta_Compress_PDB(state goal, int whichPDB, bool print_histogram)
277 // {
278 // Timer t;
279 // t.StartTimer();
280 // uint64_t COUNT = PDB[whichPDB].size();
281 // if (1) // use threads
282 // {
283 // printf("Starting threaded delta computation (%" PRId64 " entries)\n", COUNT);
284 // int numThreads = std::thread::hardware_concurrency();
285 // std::vector<std::thread*> threads(numThreads);
286 // uint64_t workSize = COUNT/numThreads+1;
287 // uint64_t start = 0;
288 // for (int x = 0; x < numThreads; x++)
289 // {
290 // threads[x] = new std::thread(&PermutationPuzzleEnvironment<state, action>::DeltaWorker, this,
291 // &PDB[whichPDB], &PDB_distincts[whichPDB], goal.puzzle.size(), start, min(start+workSize, COUNT));
292 // start += workSize;
293 // }
294 // for (int x = 0; x < numThreads; x++)
295 // {
296 // threads[x]->join();
297 // delete threads[x];
298 // threads[x] = 0;
299 // }
300 // }
301 // else {
302 // printf("Starting sequential delta computation\n");
303 // state tmp;
304 // for (uint64_t x = 0; x < COUNT; x++)
305 // {
306 // GetStateFromPDBHash(x, tmp, goal.puzzle.size(), PDB_distincts[whichPDB]);
307 // int h1 = HCost(tmp);
308 // int h2 = PDB.back()[x];
309 // // if ((h1%2)||(h2%2))
310 // // printf("%d - %d = %d\n", h2, h1, h2-h1);
311 // PDB.back()[x] = h2 - h1;
312 // }
313 // }
314 // printf("%1.2fs doing delta conversion\n", t.EndTimer());
315 //
316 // if (print_histogram)
317 // PrintPDBHistogram(whichPDB);
318 // }
319 //
320 // template <class state, class action>
321 // void PermutationPuzzleEnvironment<state, action>::DeltaWorker(std::vector<uint8_t> *array,
322 // std::vector<int> *distinct,
323 // int puzzleSize,
324 // uint64_t start, uint64_t end)
325 // {
326 // std::vector<int> dual;
327 // std::vector<int> c1;
328 // std::vector<int> c2;
329 // state tmp;
330 // for (uint64_t x = start; x < end; x++)
331 // {
332 // GetStateFromPDBHash(x, tmp, puzzleSize, *distinct, dual);
333 // int h1 = HCost(tmp, 0, c1, c2);
334 // int h2 = (*array)[x];
335 // (*array)[x] = h2 - h1;
336 // assert(h2 >= h1);
337 // }
338 // }
339 //
340 //
341 //#pragma mark -
342 //#pragma mark Implementation - Buildling PDBs
343 //#pragma mark -
344 //
345 // const int coarseSize = 1024;
346 //
347 // template <class state, class action>
348 // void PermutationPuzzleEnvironment<state, action>::ThreadWorker(int depth, int totalTiles,
349 // std::vector<uint8_t> *DB,
350 // //std::vector<uint8_t> *coarseOpen,
351 // const std::vector<int> *distinct,
352 // SharedQueue<std::pair<uint64_t, uint64_t> > *work,
353 // SharedQueue<uint64_t> *results,
354 // std::mutex *lock,
355 // bool additive)
356 // {
357 // std::pair<uint64_t, uint64_t> p;
358 // std::vector<uint64_t> additiveQueue;
359 // std::vector<int> cache1;
360 // std::vector<int> cache2;
361 // uint64_t start, end;
362 // std::vector<action> acts;
363 // state s, t;
364 // uint64_t count = 0;
365 //
366 // struct writeInfo {
367 // uint64_t rank;
368 // int newGCost;
369 // };
370 // std::vector<writeInfo> cache;
371 // while (true)
372 // {
373 // if (work->Remove(p) == false)
374 // {
375 // std::this_thread::sleep_for(std::chrono::microseconds(10));
376 // continue;
377 // }
378 // if (p.first == p.second)
379 // {
380 // break;
381 // }
382 // start = p.first;
383 // end = p.second;
384 // //int nextDepth = 255;
385 // for (uint64_t x = start; x < end; x++)
386 // {
387 // int stateDepth = (*DB)[x];
388 // if (stateDepth == depth)
389 // {
390 // count++;
391 // GetStateFromPDBHash(x, s, totalTiles, *distinct, cache1);
392 // //std::cout << "Expanding[r][" << stateDepth << "]: " << s << std::endl;
393 // this->GetActions(s, acts);
394 // for (int y = 0; y < acts.size(); y++)
395 // {
396 // this->GetNextState(s, acts[y], t);
397 // assert(this->InvertAction(acts[y]) == true);
398 // //virtual bool InvertAction(action &a) const = 0;
399 //
400 // uint64_t nextRank = GetPDBHash(t, *distinct, cache1, cache2);
401 // int newCost = stateDepth+(additive?this->AdditiveGCost(t, acts[y]):this->GCost(t, acts[y]));
402 // cache.push_back({nextRank, newCost});
403 // }
404 // }
405 // }
406 // do {
407 // // write out everything
408 // lock->lock();
409 // for (auto d : cache)
410 // {
411 // if (d.newGCost < (*DB)[d.rank]) // shorter path
412 // {
413 // (*DB)[d.rank] = d.newGCost;
414 // if (d.newGCost == depth) // 0-cost action; will expand immediately
415 // {
416 // additiveQueue.push_back(d.rank);
417 // }
418 // }
419 // }
420 // lock->unlock();
421 // cache.resize(0);
422 //
423 // while (additiveQueue.size() > 0)
424 // {
425 // uint64_t x = additiveQueue.back();
426 // additiveQueue.pop_back();
427 // int stateDepth = (*DB)[x];
428 // assert(stateDepth == depth);
429 //
430 // count++;
431 // GetStateFromPDBHash(x, s, totalTiles, *distinct, cache1);
432 // //std::cout << "Expanding[a][" << stateDepth << "]: " << s << std::endl;
433 // this->GetActions(s, acts);
434 // for (int y = 0; y < acts.size(); y++)
435 // {
436 // this->GetNextState(s, acts[y], t);
437 // assert(this->InvertAction(acts[y]) == true);
438 // //virtual bool InvertAction(action &a) const = 0;
439 //
440 // uint64_t nextRank = GetPDBHash(t, *distinct, cache1, cache2);
441 // int newCost = stateDepth+(additive?this->AdditiveGCost(t, acts[y]):this->GCost(t, acts[y]));
442 // cache.push_back({nextRank, newCost});
443 // }
444 // }
445 //
446 // } while (cache.size() != 0);
447 // }
448 // results->Add(count);
449 // }
450 //
451 //
452 // template <class state, class action>
453 // void PermutationPuzzleEnvironment<state, action>::Build_PDB(state &start, const std::vector<int> &distinct,
454 // const char *pdb_filename, int numThreads, bool additive)
455 // {
456 // SharedQueue<std::pair<uint64_t, uint64_t> > workQueue;
457 // SharedQueue<uint64_t> resultQueue;
458 // std::mutex lock;
459 //
460 // maxItem = max(maxItem,start.puzzle.size());
461 // minPattern = min(minPattern, distinct.size());
462 // buildCaches();
463 //
464 // uint64_t COUNT = nUpperk(start.puzzle.size(), start.puzzle.size() - distinct.size());
465 // std::vector<uint8_t> DB(COUNT);
466 //
467 // std::fill(DB.begin(), DB.end(), 255);
468 //
469 // // with weights we have to store the lowest weight stored to make sure
470 // // we don't skip regions
471 // std::vector<uint8_t> coarseOpen((COUNT+coarseSize-1)/coarseSize);
472 // std::fill(coarseOpen.begin(), coarseOpen.end(), 255);
473 //
474 // uint64_t entries = 0;
475 // std::cout << "Num Entries: " << COUNT << std::endl;
476 // std::cout << "Goal State: " << start << std::endl;
477 // std::cout << "State Hash of Goal: " << GetStateHash(start) << std::endl;
478 // std::cout << "PDB Hash of Goal: " << GetPDBHash(start, distinct) << std::endl;
479 //
480 // std::deque<state> q_curr, q_next;
481 // std::vector<state> children;
482 //
483 // for (unsigned i = 0; i < start.puzzle.size(); i++)
484 // {
485 // bool is_distinct = false;
486 // for (unsigned j = 0; j < distinct.size(); j++)
487 // {
488 // if (start.puzzle[i] == distinct[j])
489 // {
490 // is_distinct = true;
491 // break;
492 // }
493 // }
494 //
495 // if (!is_distinct)
496 // {
497 // start.puzzle[i] = -1;
498 // }
499 // }
500 //
501 // std::cout << "Abstract Goal State: " << start << std::endl;
502 // std::cout << "Abstract PDB Hash of Goal: " << GetPDBHash(start, distinct) << std::endl;
503 // Timer t;
504 // t.StartTimer();
505 // // q_curr.push_back(start);
506 // DB[GetPDBHash(start, distinct)] = 0;
507 // coarseOpen[GetPDBHash(start, distinct)/coarseSize] = 0;
508 // int depth = 0;
509 // uint64_t newEntries;
510 // std::vector<std::thread*> threads(numThreads);
511 // printf("Creating %d threads\n", numThreads);
512 // do {
513 // newEntries = 0;
514 // Timer s;
515 // s.StartTimer();
516 // for (int x = 0; x < numThreads; x++)
517 // {
518 // threads[x] = new std::thread(&PermutationPuzzleEnvironment<state, action>::ThreadWorker, this,
519 // depth, start.puzzle.size(), &DB,// &coarseOpen,
520 // &distinct,
521 // &workQueue, &resultQueue, &lock, additive);
522 // }
523 //
524 // for (uint64_t x = 0; x < COUNT; x+=coarseSize)
525 // {
526 // bool submit = false;
527 // for (uint64_t t = x; t < min(COUNT, x+coarseSize); t++)
528 // {
529 // if (DB[t] == depth)
530 // {
531 // submit = true;
532 // //newEntries++;
533 // }
534 // }
535 // if (submit)
536 // {
537 // while (workQueue.size() > 10*numThreads)
538 // { std::this_thread::sleep_for(std::chrono::microseconds(10)); }
539 // workQueue.Add({x, min(COUNT, x+coarseSize)});
540 // }
541 // }
542 // for (int x = 0; x < numThreads; x++)
543 // {
544 // workQueue.Add({0,0});
545 // }
546 // for (int x = 0; x < numThreads; x++)
547 // {
548 // threads[x]->join();
549 // delete threads[x];
550 // threads[x] = 0;
551 // }
552 // // read out node counts
553 // while (true)
554 // {
555 // uint64_t val;
556 // if (resultQueue.Remove(val))
557 // {
558 // //newEntries+=val;
559 // }
560 // else {
561 // break;
562 // }
563 // }
564 //
565 // newEntries = 0;
566 // for (uint64_t x = 0; x < COUNT; x++)
567 // {
568 // if (DB[x] == depth)
569 // {
570 // newEntries++;
571 // }
572 // }
573 // entries += newEntries;
574 // printf("Depth %d complete; %1.2fs elapsed. %" PRId64 " new states seen; %" PRId64 " of %" PRId64 " total\n",
575 // depth, s.EndTimer(), newEntries, entries, COUNT);
576 // depth++;
577 // // depth = coarseOpen[0];
578 // // for (int x = 1; x < coarseOpen.size(); x++)
579 // // depth = min(depth, coarseOpen[x]);
580 // // if (depth == 255) // no new entries!
581 // // break;
582 // } while (entries != COUNT);
583 //
584 // printf("%1.2fs elapsed\n", t.EndTimer());
585 // if (entries != COUNT)
586 // {
587 // printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
588 // assert(entries == COUNT);
589 // }
590 //
591 // //TODO fix the output of PDBs
592 // FILE *f = fopen(pdb_filename, "w");
593 // int num = distinct.size();
594 // assert(fwrite(&num, sizeof(num), 1, f) == 1);
595 // assert(fwrite(&distinct[0], sizeof(distinct[0]), distinct.size(), f) == distinct.size());
596 // assert(fwrite(&DB[0], sizeof(uint8_t), COUNT, f) == COUNT);
597 // fclose(f);
598 //
599 // PDB.push_back(DB); // increase the number of regular PDBs being stored
600 // PDB_distincts.push_back(distinct); // stores distinct
601 // PrintPDBHistogram(PDB.size()-1);
602 // }
603 //
604 //
605 //
606 // template <class state, class action>
607 // void PermutationPuzzleEnvironment<state, action>::Build_Regular_PDB(state &start, const std::vector<int> &distinct, const char *pdb_filename)
608 // {
609 // maxItem = max(maxItem,start.puzzle.size());
610 // minPattern = min(minPattern, distinct.size());
611 // buildCaches();
612 //
613 // uint64_t COUNT = nUpperk(start.puzzle.size(), start.puzzle.size() - distinct.size());
614 // std::vector<uint8_t> DB(COUNT);
615 //
616 // for (unsigned int x = 0; x < DB.size(); x++)
617 // DB[x] = 255;
618 //
619 // uint64_t entries = 0;
620 // std::cout << "Num Entries: " << COUNT << std::endl;
621 // std::cout << "Goal State: " << start << std::endl;
622 // std::cout << "State Hash of Goal: " << GetStateHash(start) << std::endl;
623 // std::cout << "PDB Hash of Goal: " << GetPDBHash(start, distinct) << std::endl;
624 //
625 // std::deque<state> q_curr, q_next;
626 // std::vector<state> children;
627 //
628 // for (unsigned i = 0; i < start.puzzle.size(); i++)
629 // {
630 // bool is_distinct = false;
631 // for (unsigned j = 0; j < distinct.size(); j++)
632 // {
633 // if (start.puzzle[i] == distinct[j])
634 // {
635 // is_distinct = true;
636 // break;
637 // }
638 // }
639 //
640 // if (!is_distinct)
641 // {
642 // start.puzzle[i] = -1;
643 // }
644 // }
645 //
646 // std::cout << "Abstract Goal State: " << start << std::endl;
647 // std::cout << "Abstract PDB Hash of Goal: " << GetPDBHash(start, distinct) << std::endl;
648 // Timer t;
649 // t.StartTimer();
650 // q_curr.push_back(start);
651 // DB[GetPDBHash(start, distinct)] = 0;
652 // entries++;
653 // int depth = 1;
654 // std::vector<uint64_t> depths(2);
655 // do {
656 // while (!q_curr.empty())
657 // {
658 // state next = q_curr.front();
659 // q_curr.pop_front();
660 // children.clear();
661 // this->GetSuccessors(next, children);
662 // for (unsigned int x = 0; x < children.size(); x++)
663 // {
664 // if (DB[GetPDBHash(children[x], distinct)] == 255)
665 // {
666 // int hval = depth;//-this->HCost(children[x]);
667 // assert(hval >= 0);
668 // DB[GetPDBHash(children[x], distinct)] = hval;
669 // depths[hval]++;
670 //
671 // q_next.push_back(children[x]);
672 // entries++;
673 // if ((entries % 100000) == 0)
674 // {
675 // std::cout << entries << std::endl;
676 // }
677 // // std::cout << children[x] << std::endl;
678 // /* For Debugging
679 // if (entries < 20)
680 // {
681 // std::cout << children[x] << ": " << (unsigned) DB[GetPDBHash(children[x], distinct)] << "\n";
682 // }*/
683 // }
684 // }
685 // }
686 // depth++;
687 // depths.resize(depth+1);
688 // q_curr.swap(q_next);
689 // } while (!q_curr.empty());
690 //
691 // printf("%1.2fs elapsed\n", t.EndTimer());
692 // if (entries != COUNT)
693 // {
694 // printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
695 // assert(entries == COUNT);
696 // }
697 //
698 // //TODO fix the output of PDBs
699 // FILE *f = fopen(pdb_filename, "w");
700 // int num = distinct.size();
701 // assert(fwrite(&num, sizeof(num), 1, f) == 1);
702 // assert(fwrite(&distinct[0], sizeof(distinct[0]), distinct.size(), f) == distinct.size());
703 // assert(fwrite(&DB[0], sizeof(uint8_t), COUNT, f) == COUNT);
704 // //fprintf(f, "%ld\n", distinct.size()); // first element is the number of distinct pieces
705 // // for (unsigned i = 0; i < distinct.size(); i++)
706 // // {
707 // // fprintf(f, "%d\n", distinct[i]); //first few lines are these distinct elements
708 // // }
709 // // for (unsigned i = 0; i < COUNT; i++)
710 // // {
711 // // fprintf(f, "%d\n", DB[i]);
712 // // }
713 //
714 // fclose(f);
715 //
716 // printf("Wrote %lld entries to '%s'\n", entries, pdb_filename);
717 // for (int x = 0; x < depths.size(); x++)
718 // printf("%d %lld\n", x, depths[x]);
719 //
720 // PDB.push_back(DB); // increase the number of regular PDBs being stored
721 // PDB_distincts.push_back(distinct); // stores distinct
722 // }
723 //
724 // // The distinct states should not include blanks
725 // template <class state, class action>
726 // void PermutationPuzzleEnvironment<state, action>::Build_Additive_PDB(state &start, const std::vector<int> &distinct, const char *pdb_filename, bool blank)
727 // {
728 // maxItem = max(maxItem,start.puzzle.size());
729 // minPattern = min(minPattern, distinct.size());
730 // buildCaches();
731 //
732 // uint64_t COUNT = nUpperk(start.puzzle.size(), start.puzzle.size() - distinct.size());
733 // uint64_t closedSize = nUpperk(start.puzzle.size(), start.puzzle.size() - distinct.size() - 1);
734 // std::vector<int> closedPattern(distinct);
735 // std::vector<uint8_t> DB(COUNT);
736 // std::vector<bool> closed(closedSize);
737 //
738 // if (blank)
739 // closedPattern.push_back(0);
740 //
741 // for (unsigned int x = 0; x < DB.size(); x++)
742 // DB[x] = 255;
743 //
744 // uint64_t entries = 0;
745 // std::cout << "Num Entries: " << COUNT << std::endl;
746 // std::cout << "Closed list entries: " << closedSize << std::endl;
747 // std::cout << "Goal State: " << start << std::endl;
748 // std::cout << "State Hash of Goal: " << GetStateHash(start) << std::endl;
749 // std::cout << "PDB Hash of Goal: " << GetPDBHash(start, distinct) << std::endl;
750 //
751 // std::deque<state> q_curr, q_next;
752 // std::vector<state> children;
753 //
754 // for (unsigned i = 0; i < start.puzzle.size(); i++)
755 // {
756 // bool is_distinct = false;
757 // for (unsigned j = 0; j < distinct.size(); j++)
758 // {
759 // if (start.puzzle[i] == distinct[j])
760 // {
761 // is_distinct = true;
762 // break;
763 // }
764 // }
765 //
766 // if (!is_distinct)
767 // {
768 // if (start.puzzle[i] != 0 || !blank)
769 // start.puzzle[i] = -1;
770 // }
771 // }
772 //
773 // std::cout << "Abstract Goal State: " << start << std::endl;
774 // std::cout << "Abstract PDB Hash of Goal: " << GetPDBHash(start, distinct) << std::endl;
775 //
776 // q_curr.push_back(start);
777 // DB[GetPDBHash(start, distinct)] = 0;
778 // entries++;
779 // int depth = 1;
780 // std::vector<uint64_t> depths(2);
781 // depths[0]++;
782 // do {
783 // while (!q_curr.empty())
784 // {
785 // state next = q_curr.front();
786 // q_curr.pop_front();
787 //
788 // //printf("%" PRId64 "\n", GetPDBHash(next, distinct));
789 // assert(DB[GetPDBHash(next, distinct)] != 255);
790 //
791 // uint64_t closedHash = GetPDBHash(next, closedPattern);
792 // if (closed[closedHash]) // closed
793 // {
794 // continue;
795 // }
796 // else {
797 // closed[closedHash] = true;
798 // }
799 //
800 // children.resize(0);
801 // this->GetSuccessors(next, children);
802 //
803 // for (unsigned int x = 0; x < children.size(); x++)
804 // {
805 // if (children[x] == next)
806 // {
807 // if (closed[GetPDBHash(children[x], closedPattern)] == false)
808 // {
809 // q_curr.push_back(children[x]);
810 // }
811 // }
812 // else {
813 // uint64_t pdbHash = GetPDBHash(children[x], distinct);
814 // if (DB[pdbHash] == 255)
815 // {
816 // int hval = this->HCost(children[x]);//*2-40;
817 // // if (0 == hval%2) // even
818 // // {
819 // // hval=hval*2-40;
820 // // }
821 // // else {
822 // // hval=hval*2-41;
823 // // }
824 // //if (hval > 12) hval = 12;
825 // hval = depth-hval;
826 // assert(hval >= 0);
827 // DB[pdbHash] = hval;
828 // if (hval >= depths.size())
829 // depths.resize(hval+1);
830 // depths[hval]++;
831 // entries++;
832 //
833 // // updates on how much built
834 // if ((entries % 100000) == 0)
835 // {
836 // std::cout << entries << std::endl;
837 // }
838 // }
839 // if (closed[GetPDBHash(children[x], closedPattern)] == false)
840 // {
841 // q_next.push_back(children[x]);
842 // }
843 // }
844 // }
845 // }
846 // depth++;
847 // //depths.resize(depth+1);
848 // q_curr.swap(q_next);
849 // } while (!q_curr.empty());
850 //
851 // assert(entries == COUNT);
852 //
853 // //TODO fix the output of PDBs
854 // FILE *f = fopen(pdb_filename, "w");
855 // fprintf(f, "%ld\n", distinct.size()); // first element is the number of distinct pieces
856 // for (unsigned i = 0; i < distinct.size(); i++)
857 // {
858 // fprintf(f, "%d\n", distinct[i]); //first few lines are these distinct elements
859 // }
860 // assert(fwrite(&DB[0], sizeof(uint8_t), COUNT, f) == COUNT);
861 // // for (unsigned i = 0; i < COUNT; i++)
862 // // {
863 // // fprintf(f, "%d\n", DB[i]);
864 // // }
865 //
866 // fclose(f);
867 // printf("%lld entries\n", entries);
868 // for (int x = 0; x < depths.size(); x++)
869 // printf("%d %lld\n", x, depths[x]);
870 // }
871 //
872 //
873 //#pragma mark -
874 //#pragma mark Implementation - Loading PDBs
875 //#pragma mark -
876 //
877 // template <class state, class action>
878 // void PermutationPuzzleEnvironment<state, action>::Load_Regular_PDB(const char *fname, state &goal, bool print_histogram)
879 // {
880 // //additive = false;
881 // PDB.resize(PDB.size()+1); // increase the number of regular PDBs being stored
882 // printf("Loading PDB '%s'\n", fname);
883 // std::vector<int> distinct;
884 //
885 // FILE *f;
886 // f = fopen(fname, "r");
887 // if (f == 0)
888 // {
889 // printf("Failed to open pdb '%s'\n", fname);
890 // exit(0);
891 // }
892 //
893 // int num_distinct;
894 // assert(fread(&num_distinct, sizeof(num_distinct), 1, f) == 1);
895 // distinct.resize(num_distinct);
896 // assert(fread(&distinct[0], sizeof(distinct[0]), distinct.size(), f) == distinct.size());
897 //
898 // maxItem = max(maxItem,goal.puzzle.size());
899 // minPattern = min(minPattern, distinct.size());
900 // buildCaches();
901 //
902 // uint64_t COUNT = nUpperk(goal.puzzle.size(), goal.puzzle.size() - distinct.size());
903 // PDB.back().resize(COUNT);
904 //
905 // size_t index;
906 // if ((index = fread(&PDB.back()[0], sizeof(uint8_t), COUNT, f)) != COUNT)
907 // {
908 // printf("Error; did not correctly read %" PRId64 " entries from PDB (%lu instead)\n", COUNT, index);
909 // exit(0);
910 // }
911 // fclose(f);
912 //
913 // PDB_distincts.push_back(distinct); // stores distinct
914 //
915 // if (print_histogram)
916 // PrintPDBHistogram(PDB.size()-1);
917 // }
918 //
919 //
920 // template <class state, class action>
921 // void PermutationPuzzleEnvironment<state, action>::Load_Additive_PDB(const state &goal, const char *pdb_filename)
922 // {
923 // //additive = true;
924 //
925 // PDB.resize(PDB.size()+1); // increase the number of regular PDBs being stored
926 //
927 // std::vector<int> distinct;
928 //
929 // FILE *f;
930 // f = fopen(pdb_filename, "r");
931 // if (f == 0)
932 // {
933 // printf("Failed to open pdb '%s'\n", pdb_filename);
934 // exit(0);
935 // }
936 //
937 // unsigned num_distinct;
938 // if (fscanf(f, "%d\n", &num_distinct) != 1)
939 // {
940 // printf("Failure reading tile count from PDB\n");
941 // exit(0);
942 // }
943 //
944 // for (unsigned i = 0; i < num_distinct; i++)
945 // {
946 // int tmp;
947 // if (fscanf(f, "%d\n", &tmp) != 1)
948 // {
949 // printf("Failure reading tile from PDB\n");
950 // exit(0);
951 // }
952 //
953 // distinct.push_back(tmp);
954 // }
955 //
956 // maxItem = max(maxItem,goal.puzzle.size());
957 // minPattern = min(minPattern, distinct.size());
958 // buildCaches();
959 //
960 // uint64_t COUNT = nUpperk(goal.puzzle.size(), goal.puzzle.size() - distinct.size());
961 // PDB.back().resize(COUNT);
962 //
963 // size_t index;
964 // if ((index = fread(&PDB.back()[0], sizeof(uint8_t), COUNT, f)) != COUNT)
965 // {
966 // printf("Error; did not correctly read %lu entries from PDB (%lu instead)\n", COUNT, index);
967 // exit(0);
968 // }
969 // fclose(f);
970 //
971 // PDB_distincts.push_back(distinct); // stores distinct
972 //
973 // PrintPDBHistogram(PDB.size()-1);
974 // }
975 //
976 //#pragma mark -
977 //#pragma mark Implementation - Runtime Usage
978 //#pragma mark -
979 //
980 // /**
981 // * Deprecated: this code should no longer be used.
982 // */
983 // template <class state, class action>
984 // double PermutationPuzzleEnvironment<state, action>::PDB_Lookup(const state &s) const
985 // {
986 // if (true)//!additive)
987 // {
988 // double val = 0;
989 // for (unsigned int x = 0; x < PDB.size(); x++)
990 // {
991 // uint64_t index = GetPDBHash(s, PDB_distincts[x]);
992 // //histogram[PDB[x][index]]++;
993 // val = std::max(val, (double)PDB[x][index]);
994 // }
995 // return val;
996 // }
997 // else {
998 // double val = 0;
999 // uint8_t tmp;
1000 // for (unsigned int x = 0; x < PDB.size(); x++)
1001 // {
1002 // uint64_t index = GetPDBHash(s, PDB_distincts[x]);
1003 // //histogram[PDB[x][index]]++;
1004 // tmp = PDB[x][index];
1005 // if (tmp > 4) tmp = 4;
1006 // val += (double)tmp;
1007 // }
1008 // return val;
1009 // }
1010 // }
1011 //
1012  template <class state, class action>
1013  double PermutationPuzzleEnvironment<state, action>::HCost(const state &s) const
1014  {
1015 // if (lookups.size() == 0)
1016 // return 0;
1017 // static std::vector<int> c1, c2;
1018 // return HCost(s, 0, c1, c2);
1019  return 0;
1020  }
1021 //
1022 // template <class state, class action>
1023 // double PermutationPuzzleEnvironment<state, action>::HCost(const state &s, int treeNode,
1024 // std::vector<int> &c1, std::vector<int> &c2) const
1025 // {
1026 // double hval = 0;
1027 // switch (lookups[treeNode].t)
1028 // {
1029 // case kMaxNode:
1030 // {
1031 // for (int x = 0; x < lookups[treeNode].numChildren; x++)
1032 // {
1033 // hval = max(hval, HCost(s, lookups[treeNode].firstChildID+x, c1, c2));
1034 // }
1035 // } break;
1036 // case kAddNode:
1037 // {
1038 // for (int x = 0; x < lookups[treeNode].numChildren; x++)
1039 // {
1040 // hval += HCost(s, lookups[treeNode].firstChildID+x, c1, c2);
1041 // }
1042 // } break;
1043 // case kLeafNode:
1044 // {
1045 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2);
1046 // hval = PDB[lookups[treeNode].PDBID][index];
1047 // } break;
1048 // case kLeafFractionalCompress:
1049 // {
1050 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2);
1051 // if (index < PDB[lookups[treeNode].PDBID].size())
1052 // hval = PDB[lookups[treeNode].PDBID][index];
1053 // else
1054 // hval = 0;
1055 // } break;
1056 // case kLeafFractionalModCompress: // num children is the compression factor
1057 // {
1058 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2);
1059 // if (0 == index%lookups[treeNode].numChildren)
1060 // hval = PDB[lookups[treeNode].PDBID][index/lookups[treeNode].numChildren];
1061 // else
1062 // hval = 0;
1063 // } break;
1064 // case kLeafModCompress:
1065 // {
1066 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2);
1067 // hval = PDB[lookups[treeNode].PDBID][index%PDB[lookups[treeNode].PDBID].size()];
1068 // } break;
1069 // case kLeafMinCompress:
1070 // {
1071 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2)/lookups[treeNode].numChildren;
1072 // hval = PDB[lookups[treeNode].PDBID][index];
1073 // } break;
1074 // case kLeafValueCompress:
1075 // {
1076 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2);
1077 // hval = PDB[lookups[treeNode].PDBID][index];
1078 // if (hval > lookups[treeNode].numChildren)
1079 // hval = lookups[treeNode].numChildren;
1080 // } break;
1081 // case kLeafDivPlusDeltaCompress:
1082 // {
1083 // uint64_t index = GetPDBHash(s, PDB_distincts[lookups[treeNode].PDBID], c1, c2);
1084 // hval = PDB[lookups[treeNode].PDBID][index/lookups[treeNode].numChildren];
1085 // hval += PDB[lookups[treeNode].firstChildID][index];
1086 // }
1087 // case kLeafDefaultHeuristic:
1088 // {
1089 // hval = DefaultH(s);
1090 // } break;
1091 // }
1092 // return hval;
1093 // }
1094 //
1095 //#pragma mark -
1096 //#pragma mark Implementation - Utilities
1097 //#pragma mark -
1098 //
1099  template <class state, class action>
1100  uint64_t PermutationPuzzleEnvironment<state, action>::Factorial(int val) const
1101  {
1102  static uint64_t table[21] =
1103  { 1ll, 1ll, 2ll, 6ll, 24ll, 120ll, 720ll, 5040ll, 40320ll, 362880ll, 3628800ll, 39916800ll, 479001600ll,
1104  6227020800ll, 87178291200ll, 1307674368000ll, 20922789888000ll, 355687428096000ll,
1105  6402373705728000ll, 121645100408832000ll, 2432902008176640000ll };
1106  if (val > 20)
1107  return (uint64_t)-1;
1108  return table[val];
1109  }
1110 
1114  template <class state, class action>
1115  void PermutationPuzzleEnvironment<state, action>::buildCaches() const
1116  {
1117  factorialCache.resize(maxItem+1);
1118  for (int n = 0; n < factorialCache.size(); n++)
1119  {
1120  factorialCache[n].resize(maxItem-minPattern+1);
1121  for (int k = 0; k < factorialCache[n].size(); k++)
1122  {
1123  uint64_t value = 1;
1124  for (int i = n; i > k; i--)
1125  {
1126  value *= i;
1127  }
1128  factorialCache[n][k] = value;
1129 
1130  }
1131  }
1132  }
1133 
1137  template <class state, class action>
1138  uint64_t PermutationPuzzleEnvironment<state, action>::nUpperk(int n, int k) const
1139  {
1140  assert(factorialCache.size() > n);
1141  assert(factorialCache[n].size() > k);
1142  return factorialCache[n][k];
1143 
1144  // static std::vector<std::vector<uint64_t> > cache;
1145  // if (n >= cache.size())
1146  // cache.resize(n+1);
1147  // if (k >= cache[n].size())
1148  // cache[n].resize(k+1);
1149  // if (cache[n][k] == 0)
1150  // {
1151  // uint64_t value = 1;
1152  // assert(n >= 0 && k >= 0);
1153  //
1154  // for (int i = n; i > k; i--)
1155  // {
1156  // value *= i;
1157  // }
1158  //
1159  // cache[n][k] = value;
1160  // return value;
1161  // }
1162  // return cache[n][k];
1163  }
1164 //
1165 // /**
1166 // Returns the Hash Value of the given state using the given set of distinct items
1167 // **/
1168 // template <class state, class action>
1169 // uint64_t PermutationPuzzleEnvironment<state, action>::GetPDBHash(const state &s,
1170 // const std::vector<int> &distinct) const
1171 // {
1172 // static std::vector<int> locs;
1173 // static std::vector<int> dual;
1174 // return GetPDBHash(s, distinct, locs, dual);
1175 // }
1176 //
1177 // /**
1178 // Compute the size of a PDB using a given state & set of tiles
1179 // **/
1180 // template <class state, class action>
1181 // uint64_t PermutationPuzzleEnvironment<state, action>::Get_PDB_Size(state &start, int pdbEntries)
1182 // {
1183 // maxItem = max(maxItem,start.puzzle.size());
1184 // minPattern = min(minPattern, pdbEntries);
1185 // buildCaches();
1186 // return nUpperk(start.puzzle.size(), start.puzzle.size()-pdbEntries);
1187 // }
1188 //
1189 // // TODO Change to Myrvold and Ruskey ranking function
1190 // /**
1191 // Returns the Hash Value of the given state using the given set of distinct items
1192 // This version is thread safe -- caches are passed in
1193 // **/
1194 // template <class state, class action>
1195 // uint64_t PermutationPuzzleEnvironment<state, action>::GetPDBHash(const state &s,
1196 // const std::vector<int> &distinct,
1197 // std::vector<int> &locs,
1198 // std::vector<int> &dual) const
1199 // {
1200 // locs.resize(distinct.size()); // vector for distinct item locations
1201 // dual.resize(s.puzzle.size()); // vector for distinct item locations
1202 //
1203 // // find item locations
1204 // for (unsigned int x = 0; x < s.puzzle.size(); x++)
1205 // {
1206 // if (s.puzzle[x] != -1)
1207 // dual[s.puzzle[x]] = x;
1208 // }
1209 // for (int x = 0; x < distinct.size(); x++)
1210 // {
1211 // locs[x] = dual[distinct[x]];
1212 // }
1213 //
1214 // uint64_t hashVal = 0;
1215 // int numEntriesLeft = s.puzzle.size();
1216 //
1217 // for (unsigned int x = 0; x < locs.size(); x++)
1218 // {
1219 // hashVal += locs[x]*nUpperk(numEntriesLeft-1, s.puzzle.size()-distinct.size());
1220 // numEntriesLeft--;
1221 //
1222 // // decrement locations of remaining items
1223 // for (unsigned y = x; y < locs.size(); y++)
1224 // {
1225 // if (locs[y] > locs[x])
1226 // locs[y]--;
1227 // }
1228 // }
1229 // return hashVal;
1230 // }
1231 //
1232 // /**
1233 // Returns the state from the hash value given the pattern and number of items in the puzzle
1234 // This function is not thread safe.
1235 // **/
1236 // template <class state, class action>
1237 // void PermutationPuzzleEnvironment<state, action>::GetStateFromPDBHash(uint64_t hash, state &s, int count,
1238 // const std::vector<int> &pattern)
1239 // {
1240 // static std::vector<int> dual;
1241 // GetStateFromPDBHash(hash, s, count, pattern, dual);
1242 // }
1243 //
1244 // /**
1245 // Returns the state from the hash value given the pattern and number of items in the puzzle
1246 // This function needs a vector which it shouldn't re-create at every time step. As such, we
1247 // require the user to pass one in. (This enables concurrency; although better solutions exist.)
1248 // **/
1249 // template <class state, class action>
1250 // void PermutationPuzzleEnvironment<state, action>::GetStateFromPDBHash(uint64_t hash, state &s, int count,
1251 // const std::vector<int> &pattern,
1252 // std::vector<int> &dual)
1253 // {
1254 // uint64_t hashVal = hash;
1255 // dual.resize(pattern.size());
1256 //
1257 // int numEntriesLeft = count-pattern.size()+1;
1258 // for (int x = pattern.size()-1; x >= 0; x--)
1259 // {
1260 // dual[x] = hashVal%numEntriesLeft;
1261 // hashVal /= numEntriesLeft;
1262 // numEntriesLeft++;
1263 // for (int y = x+1; y < pattern.size(); y++)
1264 // {
1265 // if (dual[y] >= dual[x])
1266 // dual[y]++;
1267 // }
1268 // }
1269 // s.puzzle.resize(count);
1270 // std::fill(s.puzzle.begin(), s.puzzle.end(), -1);
1271 // for (int x = 0; x < dual.size(); x++)
1272 // s.puzzle[dual[x]] = pattern[x];
1273 // }
1274 
1275  template <class state, class action>
1276  void PermutationPuzzleEnvironment<state, action>::GetStateFromHash(state &s, uint64_t hash) const
1277  {
1278  state tmp;
1279  mr1.Unrank(hash, s.puzzle, tmp.puzzle, s.size(), s.size());
1280  s.FinishUnranking();
1281  }
1282 
1283  template <class state, class action>
1284  uint64_t PermutationPuzzleEnvironment<state, action>::GetStateHash(const state &s) const
1285  {
1286  state tmp = s;
1287  state dual;
1288  for (size_t x = 0; x < tmp.size(); x++)
1289  dual.puzzle[tmp.puzzle[x]] = x;
1290 
1291  uint64_t hash = mr1.Rank(&tmp.puzzle[0], &dual.puzzle[0], s.size(), s.size());
1292  return hash;
1293  }
1294 
1295  template <class state, class action>
1296  state PermutationPuzzleEnvironment<state, action>::TranformToStandardGoal(const state &a, const state &b) const
1297  {
1298  state dual;
1299  state result;
1300  for (size_t x = 0; x < b.size(); x++)
1301  {
1302  dual.puzzle[b.puzzle[x]] = x;
1303  }
1304  for (size_t x = 0; x < b.size(); x++)
1305  {
1306  result.puzzle[x] = dual.puzzle[a.puzzle[x]];
1307  }
1308  result.FinishUnranking();
1309  return result;
1310  }
1311 
1312 // /**
1313 // * Show the distribution and average value of a PDB.
1314 // */
1315 // template <class state, class action>
1316 // void PermutationPuzzleEnvironment<state, action>::PrintPDBHistogram(int which) const
1317 // {
1318 // double average = 0;
1319 // uint8_t maxval = 0;
1320 // std::vector<uint64_t> values(256);
1321 // // performs histogram count
1322 // for (uint64_t x = 0; x < PDB[which].size(); x++)
1323 // {
1324 // values[(PDB[which][x])]++;
1325 // maxval = max(maxval, PDB[which][x]);
1326 // }
1327 // // outputs histogram of heuristic value counts
1328 // for (uint64_t x = 0; x <= maxval; x++)
1329 // {
1330 // printf("%lld:\t%" PRId64 "\n", x, values[x]);
1331 // average += x*values[x];
1332 // }
1333 // printf("Average value: %1.4f\n", average/PDB[which].size());
1334 // }
1335 //
1336 // /**
1337 // * Return the distribution of values in a PDB.
1338 // */
1339 // template <class state, class action>
1340 // void PermutationPuzzleEnvironment<state, action>::GetPDBHistogram(int which, std::vector<uint64_t> &values) const
1341 // {
1342 // uint8_t maxval = 0;
1343 // values.resize(0);
1344 // values.resize(256);
1345 // // performs histogram count
1346 // for (uint64_t x = 0; x < PDB[which].size(); x++)
1347 // {
1348 // values[(PDB[which][x])]++;
1349 // maxval = max(maxval, PDB[which][x]);
1350 // }
1351 // values.resize(maxval+1);
1352 // }
1353 //
1354 //
1359  template <class state, class action>
1360  bool PermutationPuzzleEnvironment<state, action>::Check_Permutation(const std::vector<int> &to_check)
1361  {
1362  const auto size = to_check.size();
1363 
1364  bool in_puzzle[size];
1365 
1366  for (size_t i = 0; i < size; i++)
1367  {
1368  in_puzzle[i] = false;
1369  }
1370 
1371  for (size_t i = 0; i < size; i++)
1372  {
1373  in_puzzle[to_check[i]] = true;
1374  }
1375 
1376  for (size_t i = 0; i < size; i++)
1377  {
1378  if (!in_puzzle[i])
1379  return false;
1380  }
1381 
1382  return true;
1383  }
1384 
1393  template <class state, class action>
1394  bool PermutationPuzzleEnvironment<state, action>::Output_Puzzles(std::vector<state> &puzzle_vector, bool write_puzz_num)
1395  {
1396  // check validity of puzzles
1397  for (unsigned i = 0; i < puzzle_vector.size(); i++)
1398  {
1402  if (!Check_Permutation(puzzle_vector[i].puzzle))
1403  {
1404  std::cerr << "Invalid Puzzle: " << puzzle_vector[i] << '\n';
1405  return false;
1406  }
1407  }
1408 
1409  for (unsigned i = 0; i < puzzle_vector.size(); i++)
1410  {
1411  if (write_puzz_num)
1412  {
1413  printf("%u ", i + 1);
1414  }
1415  printf("%d", puzzle_vector[i].puzzle[0]);
1416 
1417  for (unsigned j = 1; j < puzzle_vector[i].puzzle.size(); j++)
1418  {
1419  printf(" %d", puzzle_vector[i].puzzle[j]);
1420  }
1421  printf("\n");
1422  }
1423  return true;
1424  }
1425 
1426  // TODO clean up using split
1427  template <class state, class action>
1428  bool PermutationPuzzleEnvironment<state, action>::Read_In_Permutations(const char *filename, unsigned size, unsigned max_puzzles,
1429  std::vector<std::vector<int> > &permutations, bool puzz_num_start)
1430  {
1431  std::ifstream ifs(filename, std::ios::in);
1432 
1433  if (ifs.fail())
1434  {
1435  fprintf(stderr, "File Reading Failed\n");
1436  return false;
1437  }
1438 
1439  std::string s, temp;
1440 
1441  std::vector<int> puzz_ints;
1442 
1443  bool first = true;
1444  unsigned puzz_count = 0;
1445 
1446  while(!ifs.eof() && (puzz_count < max_puzzles || max_puzzles==0) )
1447  {
1448  puzz_ints.clear();
1449 
1450  getline(ifs, s);
1451  // indicates are starting new permutation
1452  first = true;
1453  for (unsigned int i = 0; i < s.length(); i++)
1454  {
1455  if (s.at(i) == ' ' || s.at(i) == '\t')
1456  {
1457  if (temp.length() > 0)
1458  {
1459  if (puzz_num_start && first)
1460  {
1461  temp.clear();
1462  first = false;
1463  }
1464  else
1465  {
1466  puzz_ints.push_back(atoi(temp.c_str()));
1467  temp.clear();
1468  }
1469  }
1470  }
1471  else
1472  {
1473  temp.push_back(s.at(i));
1474  }
1475  }
1476 
1477 
1478  if (temp.length() > 0)
1479  {
1480  puzz_ints.push_back(atoi(temp.c_str()));
1481  temp = "";
1482  }
1483 
1484  // ensure is proper permutation, otherwise don't add it to the list
1485  if (puzz_ints.size() == size && Check_Permutation(puzz_ints))
1486  {
1487  puzz_count++;
1488  permutations.push_back(puzz_ints);
1489  }
1490 
1491  }
1492 
1493  ifs.close();
1494 
1495  return true;
1496  }
1497 
1498  template <class state, class action>
1499  std::vector<int> PermutationPuzzleEnvironment<state, action>::Get_Random_Permutation(unsigned size)
1500  {
1501  std::vector<int> permutation;
1502 
1503  for (unsigned i = 0; i < size; i++)
1504  {
1505  permutation.push_back(i);
1506  }
1507  int index = 0;
1508  int temp;
1509 
1510  // randomizes elements in the permutation
1511  while(size > 1)
1512  { index = rand() % size;
1513  temp = permutation[size - 1];
1514  permutation[size - 1] = permutation[index];
1515  permutation[index] = temp;
1516 
1517  size--;
1518  }
1519 
1520  return permutation;
1521  }
1522 
1523  template <class state, class action>
1524  bool PermutationPuzzleEnvironment<state, action>::Validate_Problems(std::vector<state> &puzzles)
1525  {
1526  for (unsigned i = 0; i < puzzles.size(); i++)
1527  {
1528  if (!State_Check(puzzles[i]) || !Check_Permutation(puzzles[i].puzzle))
1529  {
1530  std::cerr << puzzles[i] << '\n';
1531  std::cerr << "Invalid Puzzle\n";
1532  }
1533  }
1534  return true;
1535  }
1536 
1537 }
1538 
1539 #endif // PERMPUZZ_H
PermutationPuzzle::PermutationPuzzleEnvironment::GetStateHash
uint64_t GetStateHash(const state &s) const
Definition: PermutationPuzzleEnvironment.h:1284
PermutationPuzzle::PermutationPuzzleEnvironment::nUpperk
uint64_t nUpperk(int n, int k) const
Returns the value of n! / k!
Definition: PermutationPuzzleEnvironment.h:1138
PermutationPuzzle::PermutationPuzzleEnvironment::Check_Permutation
static bool Check_Permutation(const std::vector< int > &to_check)
Ensures that the state contains a valid permutation.
Definition: PermutationPuzzleEnvironment.h:1360
PermutationPuzzle::PDBTreeNode::t
PDBTreeNodeType t
Definition: PermutationPuzzleEnvironment.h:43
PermutationPuzzle::PermutationPuzzleEnvironment::Get_Random_Permutation
static std::vector< int > Get_Random_Permutation(unsigned size)
Definition: PermutationPuzzleEnvironment.h:1499
Heuristic
Definition: Heuristic.h:30
PermutationPuzzle::kDone
const uint64_t kDone
Definition: PermutationPuzzleEnvironment.h:49
RangeCompression.h
PermutationPuzzle::kLeafDivPlusDeltaCompress
@ kLeafDivPlusDeltaCompress
Definition: PermutationPuzzleEnvironment.h:37
PermutationPuzzle::kMaxNode
@ kMaxNode
Definition: PermutationPuzzleEnvironment.h:29
PermutationPuzzle::ArbitraryGoalPermutation::e
environment * e
Definition: PermutationPuzzleEnvironment.h:144
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
PermutationPuzzle::PermutationPuzzleEnvironment::Output_Puzzles
static bool Output_Puzzles(std::vector< state > &puzzle_vector, bool write_puzz_num)
Outputs the set of puzzles in puzzle_vector to standard output.
Definition: PermutationPuzzleEnvironment.h:1394
PermutationPuzzle::PDBTreeNode::numChildren
uint8_t numChildren
Definition: PermutationPuzzleEnvironment.h:44
PermutationPuzzle::kLeafFractionalModCompress
@ kLeafFractionalModCompress
Definition: PermutationPuzzleEnvironment.h:34
PermutationPuzzle::PermutationPuzzleEnvironment::buildCaches
void buildCaches() const
Builds caches for nUpperk.
Definition: PermutationPuzzleEnvironment.h:1115
PermutationPuzzle::PermutationPuzzleEnvironment::State_Check
virtual bool State_Check(const state &to_check)=0
Checks that the given state is a valid state for this domain.
PermutationPuzzle::PermutationPuzzleEnvironment::Read_In_Permutations
static bool Read_In_Permutations(const char *filename, unsigned size, unsigned max_puzzles, std::vector< std::vector< int > > &permutations, bool puzz_num_start)
Definition: PermutationPuzzleEnvironment.h:1428
PermutationPuzzle::PermutationPuzzleEnvironment::TranformToStandardGoal
state TranformToStandardGoal(const state &a, const state &b) const
Definition: PermutationPuzzleEnvironment.h:1296
PermutationPuzzle::PermutationPuzzleEnvironment::PDB_distincts
std::vector< std::vector< int > > PDB_distincts
Definition: PermutationPuzzleEnvironment.h:129
PermutationPuzzle::PermutationPuzzleEnvironment::PermutationPuzzleEnvironment
PermutationPuzzleEnvironment()
Definition: PermutationPuzzleEnvironment.h:59
PermutationPuzzle::PermutationPuzzleEnvironment::AdditiveGCost
virtual double AdditiveGCost(const state &s, const action &d)
Definition: PermutationPuzzleEnvironment.h:63
PermutationPuzzle::PDBTreeNode::PDBID
uint8_t PDBID
Definition: PermutationPuzzleEnvironment.h:46
PermutationPuzzle::PDBTreeNode
Definition: PermutationPuzzleEnvironment.h:41
PermutationPuzzle::kLeafModCompress
@ kLeafModCompress
Definition: PermutationPuzzleEnvironment.h:35
PermutationPuzzle::PermutationPuzzleEnvironment::FinishUnranking
virtual void FinishUnranking(state &s) const
Definition: PermutationPuzzleEnvironment.h:79
PermutationPuzzle::kLeafNode
@ kLeafNode
Definition: PermutationPuzzleEnvironment.h:31
Timer.h
PermutationPuzzle::PermutationPuzzleEnvironment::additive
bool additive
Definition: PermutationPuzzleEnvironment.h:124
PermutationPuzzle::PermutationPuzzleEnvironment::GetStateFromHash
void GetStateFromHash(state &s, uint64_t hash) const
Definition: PermutationPuzzleEnvironment.h:1276
PermutationPuzzle::ArbitraryGoalPermutation::HCost
virtual double HCost(const state &a, const state &b) const
Definition: PermutationPuzzleEnvironment.h:140
MR1KPermutation
Definition: MR1Permutation.h:16
PermutationPuzzle::PermutationPuzzleEnvironment::maxItem
int maxItem
Definition: PermutationPuzzleEnvironment.h:125
PermutationPuzzle::PDBTreeNodeType
PDBTreeNodeType
Definition: PermutationPuzzleEnvironment.h:28
PermutationPuzzle::PermutationPuzzleEnvironment
Note, assumes that state has a public vector<int> called puzzle in which the permutation is held.
Definition: PermutationPuzzleEnvironment.h:26
PermutationPuzzle::PermutationPuzzleEnvironment::Factorial
uint64_t Factorial(int val) const
Definition: PermutationPuzzleEnvironment.h:1100
PermutationPuzzle::PermutationPuzzleEnvironment::Validate_Problems
bool Validate_Problems(std::vector< state > &puzzles)
Definition: PermutationPuzzleEnvironment.h:1524
PermutationPuzzle::ArbitraryGoalPermutation::ArbitraryGoalPermutation
ArbitraryGoalPermutation(Heuristic< state > *h, environment *env)
Definition: PermutationPuzzleEnvironment.h:139
PermutationPuzzle::PermutationPuzzleEnvironment::minPattern
int minPattern
Definition: PermutationPuzzleEnvironment.h:125
PermutationPuzzle::PermutationPuzzleEnvironment::HCost
double HCost(const state &s) const
Definition: PermutationPuzzleEnvironment.h:1013
PermutationPuzzle::kAddNode
@ kAddNode
Definition: PermutationPuzzleEnvironment.h:30
PermutationPuzzle::ArbitraryGoalPermutation
Definition: PermutationPuzzleEnvironment.h:137
PermutationPuzzle::PDBTreeNode::firstChildID
uint8_t firstChildID
Definition: PermutationPuzzleEnvironment.h:45
SharedQueue.h
PermutationPuzzle::kLeafDefaultHeuristic
@ kLeafDefaultHeuristic
Definition: PermutationPuzzleEnvironment.h:38
MR1Permutation.h
PermutationPuzzle::PermutationPuzzleEnvironment::Hash
static uint64_t Hash(const state &s)
Definition: PermutationPuzzleEnvironment.h:68
PermutationPuzzle
Definition: PermutationPuzzleEnvironment.h:23
PermutationPuzzle::kLeafMinCompress
@ kLeafMinCompress
Definition: PermutationPuzzleEnvironment.h:32
PermutationPuzzle::kLeafValueCompress
@ kLeafValueCompress
Definition: PermutationPuzzleEnvironment.h:36
MR1KPermutation::Rank
uint64_t Rank(int *items, int *dual, int k, int N) const
Definition: MR1Permutation.cpp:21
PermutationPuzzle::PermutationPuzzleEnvironment::factorialCache
std::vector< std::vector< uint64_t > > factorialCache
Definition: PermutationPuzzleEnvironment.h:131
PermutationPuzzle::ArbitraryGoalPermutation::h
Heuristic< state > * h
Definition: PermutationPuzzleEnvironment.h:143
PermutationPuzzle::kLeafFractionalCompress
@ kLeafFractionalCompress
Definition: PermutationPuzzleEnvironment.h:33
PermutationPuzzle::PermutationPuzzleEnvironment::mr1
MR1KPermutation mr1
Definition: PermutationPuzzleEnvironment.h:133
PermutationPuzzle::PermutationPuzzleEnvironment::DefaultH
virtual double DefaultH(const state &s) const
Definition: PermutationPuzzleEnvironment.h:105
PermutationPuzzle::PermutationPuzzleEnvironment::lookups
std::vector< PDBTreeNode > lookups
Definition: PermutationPuzzleEnvironment.h:130
SearchEnvironment
Definition: SearchEnvironment.h:30
SearchEnvironment.h
PermutationPuzzle::PermutationPuzzleEnvironment::PDB
std::vector< std::vector< uint8_t > > PDB
Definition: PermutationPuzzleEnvironment.h:127
Generated by   doxygen 1.8.17