Opened 7 years ago
Closed 6 years ago
#19107 closed enhancement (fixed)
Do not count 4 times the same solution (up to rotations) in QuantuminoSolver
Reported by:  slabbe  Owned by:  

Priority:  major  Milestone:  sage6.10 
Component:  combinatorics  Keywords:  
Cc:  vdelecroix  Merged in:  
Authors:  Sébastien Labbé  Reviewers:  Vincent Delecroix 
Report Upstream:  N/A  Work issues:  
Branch:  d72c8d9 (Commits, GitHub, GitLab)  Commit:  d72c8d936da1c57fd7fd4971b65ee73c66eae7ea 
Dependencies:  Stopgaps: 
Description
The following computation takes a lot of time:
sage: from sage.games.quantumino import QuantuminoSolver sage: QuantuminoSolver(0).number_of_solutions() # long time (several days)
A solution is a tiling of a 5x8x2 box. Since a 5x8x2 box has four orientation preserving isometries that preserves it, each solution up to rotation is counted four times in the computation above.
It is possible to avoid to compute 4 times the same solution. This ticket does this by choosing a piece and considering 4 times less positions for that piece.
This ticket was created from a split into two parts of #18987.
Change History (24)
comment:1 Changed 7 years ago by
 Branch set to u/slabbe/19107
 Commit set to 25ed836ab3fd20461bdfa509fdbb8e764c3458f7
comment:2 Changed 7 years ago by
 Cc vdelecroix added
 Status changed from new to needs_review
Salut Vincent, I am adding you in cc here since you started the review of that code at #18987.
comment:3 followup: ↓ 5 Changed 7 years ago by
Salut,
This is bad
H = [h for h in G if all(i==j for (i,j) in h.matrix().nonzero_positions())]
You are iterating through the whole group to get the subgroup of diagonal matrices... but you know already what they are!
You can remove this line
assert MatrixGroup(H).cardinality() == len(H)
To build the cosets, you would better use something smarter
G_set = set(G) cosets = [] while G_set: g = G_set.pop() left_coset = sorted(h*g for h in H) right_coset = sorted(g*h for h in H) assert left_coset == right_coset # must be a normal subgroup G_set.difference_update(left_coset) cosets.append(left_coset)
There are some trailing whitespaces in _rows_modpi
... more to come
comment:4 Changed 7 years ago by
 Status changed from needs_review to needs_work
comment:5 in reply to: ↑ 3 Changed 7 years ago by
Replying to vdelecroix:
This is bad
H = [h for h in G if all(i==j for (i,j) in h.matrix().nonzero_positions())]
The code below would be nice but leads to this bug: #19270.
from sage.misc.misc_c import prod it = itertools.product((1,1), repeat=n) if orientation_preserving: H = [diagonal_matrix(L) for L in it if prod(L) == 1] else: H = [diagonal_matrix(L) for L in it] H = G.subgroup(H)
If you can find a way of creating G
and H
so that g * h
works and returns an hashable object for all g in G and h in H, tell me.
comment:6 Changed 7 years ago by
 Commit changed from 25ed836ab3fd20461bdfa509fdbb8e764c3458f7 to 23d109a75bd0c024af9fb6eb8865b85e0f66ada1
comment:7 Changed 7 years ago by
 Status changed from needs_work to needs_review
Okay, so I decided to use matrices + .set_immutable()
instead of MatrixGroup
elements.
Needs review!
comment:8 Changed 7 years ago by
 Reviewers set to Vincent Delecroix
 Status changed from needs_review to needs_work
Merge conflict in src/sage/combinat/tiling.py
comment:9 followup: ↓ 10 Changed 7 years ago by
Because of #19260 I guess...
comment:10 in reply to: ↑ 9 ; followup: ↓ 12 Changed 7 years ago by
comment:11 Changed 7 years ago by
 Commit changed from 23d109a75bd0c024af9fb6eb8865b85e0f66ada1 to a1d44650afb5b9e0d9bb96f75b6641a3a1a5ce4d
Branch pushed to git repo; I updated commit sha1. New commits:
a1d4465  Fix conflicts of #19107 with sage6.10.beta1

comment:12 in reply to: ↑ 10 Changed 7 years ago by
 Status changed from needs_work to needs_review
If it is then the merge will be very easy.
Indeed (I was expecting something worse), now needs review.
comment:13 Changed 6 years ago by
 Milestone changed from sage6.9 to sage6.10
 Status changed from needs_review to needs_info
minor comment: The names XYZ_iterator
is a bit heavy. With Python 3 more stuff is actually returning iterator (like range
, zip
) without explicit names. What about isometric_copies
and translated_copies
. In that case canonical_isometric_copies
would better returns an iterator as well.
otherwise it looks good to me.
comment:14 Changed 6 years ago by
 Commit changed from a1d44650afb5b9e0d9bb96f75b6641a3a1a5ce4d to 3ef5d3a2e1e7edda2032fbfc66e2644e0c2ce231
comment:15 followup: ↓ 17 Changed 6 years ago by
needs review?
comment:16 Changed 6 years ago by
 Status changed from needs_info to needs_review
I renamed the methods. I kept canonical_isometric_copies
returning a set since it needs to avoid duplicates. And also returning iter(set(it))
is bad if the user then creates a set out of it...
comment:17 in reply to: ↑ 15 Changed 6 years ago by
comment:18 Changed 6 years ago by
I am still wondering if modpi
is the good name for what I mean. Maybe upto_box_isometries
would be better?
comment:19 followup: ↓ 21 Changed 6 years ago by
 in any case you should be clearer in the documentation that its meaning somehow depends on the other argument
orientation_preserving
up_to_box_isometries
is better thanupto_box_isometries
 the prefix
mod
makes it clear that you are considering a quotient
comment:20 Changed 6 years ago by
 Commit changed from 3ef5d3a2e1e7edda2032fbfc66e2644e0c2ce231 to d72c8d936da1c57fd7fd4971b65ee73c66eae7ea
Branch pushed to git repo; I updated commit sha1. New commits:
d72c8d9  Trac #19107: renamed modpi > mod_box_isometries

comment:21 in reply to: ↑ 19 Changed 6 years ago by
Replying to vdelecroix:
 in any case you should be clearer in the documentation that its meaning somehow depends on the other argument
orientation_preserving
The documentation of both orientation_preserving
and mod_box_isometries
are now written in terms of the group of isometries of the ncube. The first restrict to a subgroup whereas the second is quotient by a subgroup. And they are compatible. Tell me if it is better now.
Needs review.
comment:23 Changed 6 years ago by
Thanks for your review.
comment:24 Changed 6 years ago by
 Branch changed from u/slabbe/19107 to d72c8d936da1c57fd7fd4971b65ee73c66eae7ea
 Resolution set to fixed
 Status changed from positive_review to closed
Initials commits from the split that occured in #18987 (they do not depend on #18987).
New commits:
Trac #19107: count solutions up to rotations
Trac #19107: Add a transparent gray box to QuantuminoState.show3d