Opened 4 years ago

Closed 4 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: sage-6.10
Component: combinatorics Keywords:
Cc: vdelecroix Merged in:
Authors: Sébastien Labbé Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: d72c8d9 (Commits) 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 4 years ago by slabbe

  • Branch set to u/slabbe/19107
  • Commit set to 25ed836ab3fd20461bdfa509fdbb8e764c3458f7

Initials commits from the split that occured in #18987 (they do not depend on #18987).


New commits:

5833a1eTrac #19107: count solutions up to rotations
25ed836Trac #19107: Add a transparent gray box to QuantuminoState.show3d

comment:2 Changed 4 years ago by slabbe

  • 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 follow-up: Changed 4 years ago by vdelecroix

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 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:5 in reply to: ↑ 3 Changed 4 years ago by slabbe

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 4 years ago by git

  • Commit changed from 25ed836ab3fd20461bdfa509fdbb8e764c3458f7 to 23d109a75bd0c024af9fb6eb8865b85e0f66ada1

Branch pushed to git repo; I updated commit sha1. New commits:

e5c36d5Trac #19107: Fixing reviewers comments (#3)
23d109aTrac #19107: Using normal matrices instead of MatrixGroup elements

comment:7 Changed 4 years ago by slabbe

  • 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 4 years ago by vdelecroix

  • Authors set to Sébastien Labbé
  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

Merge conflict in src/sage/combinat/tiling.py

comment:9 follow-up: Changed 4 years ago by slabbe

Because of #19260 I guess...

comment:10 in reply to: ↑ 9 ; follow-up: Changed 4 years ago by vdelecroix

Replying to slabbe:

Because of #19260 I guess...

If it is then the merge will be very easy.

comment:11 Changed 4 years ago by git

  • Commit changed from 23d109a75bd0c024af9fb6eb8865b85e0f66ada1 to a1d44650afb5b9e0d9bb96f75b6641a3a1a5ce4d

Branch pushed to git repo; I updated commit sha1. New commits:

a1d4465Fix conflicts of #19107 with sage-6.10.beta1

comment:12 in reply to: ↑ 10 Changed 4 years ago by slabbe

  • 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 4 years ago by vdelecroix

  • Milestone changed from sage-6.9 to sage-6.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 4 years ago by git

  • Commit changed from a1d44650afb5b9e0d9bb96f75b6641a3a1a5ce4d to 3ef5d3a2e1e7edda2032fbfc66e2644e0c2ce231

Branch pushed to git repo; I updated commit sha1. New commits:

df92a40Merge #19107 into sage-6.10.beta6
3ef5d3aTrac #19107: rename methods XYZ_iterator -> XYZ

comment:15 follow-up: Changed 4 years ago by vdelecroix

needs review?

comment:16 Changed 4 years ago by slabbe

  • 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 4 years ago by slabbe

Replying to vdelecroix:

needs review?

you're too fast:)

comment:18 Changed 4 years ago by slabbe

I am still wondering if modpi is the good name for what I mean. Maybe upto_box_isometries would be better?

comment:19 follow-up: Changed 4 years ago by vdelecroix

  • 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 than upto_box_isometries
  • the prefix mod makes it clear that you are considering a quotient

comment:20 Changed 4 years ago by git

  • Commit changed from 3ef5d3a2e1e7edda2032fbfc66e2644e0c2ce231 to d72c8d936da1c57fd7fd4971b65ee73c66eae7ea

Branch pushed to git repo; I updated commit sha1. New commits:

d72c8d9Trac #19107: renamed modpi -> mod_box_isometries

comment:21 in reply to: ↑ 19 Changed 4 years ago by slabbe

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 n-cube. 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:22 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Good for me.

comment:23 Changed 4 years ago by slabbe

Thanks for your review.

comment:24 Changed 4 years ago by vbraun

  • Branch changed from u/slabbe/19107 to d72c8d936da1c57fd7fd4971b65ee73c66eae7ea
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.