planet.sagemath.orgPlanet Sage

Blog December 03, 2020 Sébastien Labbé Tiling a polyomino with polyominoes in SageMath Suppose that you 3D print many copies of the following 3D hexo-mino at home: sage : from sage.combinat.tiling import Polyomino , TilingSolver sage : p = Polyomino ([( 0 , 0 , 0 ), ( 0 , 1 , 0 ), ( 1 , 0 , 0 ), ( 2 , 0 , 0 ), ( 2 , 1 , 0 ), ( 2 , 1 , 1 )], color = ’blue’ ) sage : p . show3d () Launched html viewer for Graphics3d Object You would like to know if you can tile a larger polyomino or in particular a rectangular box with many copies of it. The TilingSolver module in SageMath is made for that. See also this recent question on ask.sagemath.org . sage : T = TilingSolver ([ p ], ( 7 , 5 , 3 ), rotation = True , reflection = False , reusable = True ) sage : T Tiling solver of 1 pieces into a box of size 24 Rotation allowed : True Reflection allowed : False Reusing pieces allowed : True There is no solution when tiling a box of shape 7x5x3 with this polyomino: sage : T . number_of_solutions () 0 But there are 4 solutions when tiling a box of shape 4x3x2 with this polyomino: sage : T = TilingSolver ([ p ], ( 4 , 3 , 2 ), rotation = True , reflection = False , reusable = True ) sage : T . number_of_solutions () 4 We construct the list of solutions: sage : solutions = [ sol for sol in T . solve ()] Each solution contains the isometric copies of the polyominoes tiling the box: sage : solutions [ 0 ] [ Polyomino : [( 0 , 0 , 0 ), ( 0 , 0 , 1 ), ( 0 , 1 , 0 ), ( 1 , 1 , 0 ), ( 2 , 0 , 0 ), ( 2 , 1 , 0 )], Color : #ff0000, Polyomino : [( 0 , 1 , 1 ), ( 0 , 2 , 0 ), ( 0 , 2 , 1 ), ( 1 , 1 , 1 ), ( 2 , 1 , 1 ), ( 2 , 2 , 1 )], Color : #ff0000, Polyomino : [( 1 , 0 , 0 ), ( 1 , 0 , 1 ), ( 2 , 0 , 1 ), ( 3 , 0 , 0 ), ( 3 , 0 , 1 ), ( 3 , 1 , 0 )], Color : #ff0000, Polyomino : [( 1 , 2 , 0 ), ( 1 , 2 , 1 ), ( 2 , 2 , 0 ), ( 3 , 1 , 1 ), ( 3 , 2 , 0 ), ( 3 , 2 , 1 )], Color : #ff0000] It may be easier to visualize the solutions, so we define the following function allowing to draw the solutions with different colors for each piece: sage : def draw_solution ( solution , size = 0.9 ): .... : colors = rainbow ( len ( solution )) .... : for piece , col in zip ( solution , colors ): .... : piece . color ( col ) .... : return sum (( piece . show3d ( size = size ) for piece in solution ), Graphics ()) sage : G = [ draw_solution ( sol ) for sol in solutions ] sage : G [ Graphics3d Object , Graphics3d Object , Graphics3d Object , Graphics3d Object ] sage : G [ 0 ] # in Sage, this will open a 3d viewer automatically sage : G [ 1 ] sage : G [ 2 ] sage : G [ 3 ] We may save the solutions to a file: sage : G [ 0 ] . save ( ’solution0.png’ , aspect_ratio = 1 , zoom = 1.2 ) sage : G [ 1 ] . save ( ’solution1.png’ , aspect_ratio = 1 , zoom = 1.2 ) sage : G [ 2 ] . save ( ’solution2.png’ , aspect_ratio = 1 , zoom = 1.2 ) sage : G [ 3 ] . save ( ’solution3.png’ , aspect_ratio = 1 , zoom = 1.2 ) Question: are all of the 4 solutions isometric to each other? The tiling problem is solved due to a reduction to the exact cover problem for which dancing links Knuth’s algorithm provides all the solutions. One can see the rows of the dancing links matrix as follows: sage : d = T . dlx_solver () sage : d Dancing links solver for 24 columns and 56 rows sage : d . rows () [[ 0 , 1 , 2 , 4 , 5 , 11 ], [ 6 , 7 , 8 , 10 , 11 , 17 ], [ 12 , 13 , 14 , 16 , 17 , 23 ], ... [ 4 , 6 , 7 , 9 , 10 , 11 ], [ 10 , 12 , 13 , 15 , 16 , 17 ], [ 16 , 18 , 19 , 21 , 22 , 23 ]] The solutions to the dlx solver can be obtained as follows: sage : it = d . solutions_iterator () sage : next ( it ) [ 3 , 36 , 19 , 52 ] These are the indices of the rows each corresponding to an isometric copy of the polyomino within the box. Since SageMath-9.2 , the possibility to reduce the problem to a MILP problem or a SAT instance was added to SageMath (see #29338 and #29955): sage : d . to_milp () ( Boolean Program ( no objective , 56 variables , 24 constraints ), MIPVariable of dimension 1 ) sage : d . to_sat_solver () CryptoMiniSat solver : 56 variables , 2348 clauses . by Sébastien Labbé at December 03, 2020 01:48 PM April 13, 2020 William Stein DataDog: Don’t make the same mistake I dida followup and thoughts about very unhappy customers This is a followup to my previous blog post about DataDog billing . TL;DR: - I don’t recommend DataDog, - dealing with unhappy customers is hard, - monitoring for data science nerds? Hacker News Comments DataDog at Google Cloud Summit I was recently at the Seattle Google Cloud Summit and DataDog was well represented, with the biggest booth and top vendor billing during the keynote. Clearly they are doing something right. I had a past unpleasant experience with them, and I had just been auditing my records and discovered that last year DataDog had actually charged me a lot more than I thought, so was kind of annoyed. Nonetheless, they kept coming up and talking to me, server monitoring is life-and-death important to me, and their actual software is very impressive in some ways. Nick Parisi started talking with me about DataDog. He sincerely wanted to know about my past experience with monitoring and the DataDog product, which he was clearly very enthuisiastic about. So I told him a bit, and he encouraged me to tell him more, explaining that he did not work at DataDog last year, and that he would like to know what happened. So he gave me his email, and he was very genuinely concerned and helpful , so I sent him an email with a link to my post, etc. I didn’t receive a response, so a week later I asked why, and received a followup email from Jay Robichau, who is DataDog’s Director of Sales. Conference Call with DataDog Jay setup a conference call with me today at 10am (September 22, 2017). Before the call, I sent him a summary of my blog post, and also requested a refund, especially for the suprise bill they sent me nearly 6 weeks after my post. During the call, Jay explained that he was "protecting" Nick from me, and that I would mostly talk with Michelle Danis who is in charge of customer success. My expectation for the call is that we would find some common ground, and that they would at least appreciate the chance to make things right and talk with an unhappy customer. I was also curious about how a successful startup company addresses the concerns of an unhappy customer (me). I expected the conversation to be difficult but go well, with me writing a post singing the praises of the charming DataDog sales and customer success people. A few weeks ago CoCalc.com (my employer) had a very unhappy customer who got (rightfully) angry over a miscommunication, told us he would no longer use our product, and would definitely not recommend it to anybody else. I wrote to him wanting to at least continue the discussion and help, but he was completely gone. I would do absolutely anything I could to ensure he is a satisfied, if only he would give me the chance. Also, there was a recent blog post from somebody unhappy with using CoCalc/Sage for graphics, and I reached out to them as best I could to at least clarify things... In any case, here’s what DataDog charged us as a result of us running their daemon on a few dozen containers in our Kubernetes cluster (a contractor who is not a native English speaker actually setup these monitors for us): 07/22/2016 449215JWJH87S8N4 DATADOG 866-329-4466 NY $639.19 08/29/2016 2449215L2JH87V8WZ DATADOG 866-329-4466 NY $927.22 I was shocked by the 07/22 bill which spured my post, and discovered the 8/29 one only later. We canceled our subscription on July 22 (cancelling was difficult in itself). Michelle started the conference call by explaining that the 08/29 bill was for charges incurred before 07/22, and that their billing system has over a month lag (and it does even today, unlike Google Cloud Platform, say). Then Michelle explained at length many of the changes that DataDog has made to their software to address the issues I (and others?) have pointed out with their pricing...