motris ([info]motris) wrote,
@ 2008-06-14 15:22:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Dot Triangles - "By Logic"
Here is my quick triangle count - only a half hour to get all the errors out of it - which may still have an error:

A (6) - ABG, ACG, ACI, AGI, AHJ, ANQ
B (3) - ABG, BDK, BGO
C (8) - ACG, ACI, CEH, CGI, CGM, CHL, CON, CNT
D (6) - BDK, DEJ, DGH, DMK, DOS, DQS
E (7) - CEH, DEJ, EGL, EGN, EIL, EJK, ELN
F (2) - FHI, FST
G (13) - ABG, ACG, AGI, BGO, CGI, CGM, DGH, EGL, EGN, GHK, GIO, GLN, GNR
H (10) - AHJ, CEH, CHL, DGH, FHI, GHK, HJO, HIK, HLR, HMN
I (10) - ACI, AGI, CGI, EIL, FHI, GIO, HIK, IJN, ILU, IOP
J (12) - AHJ, DEJ, EJK, HJO, IJN, JKR, JKS, JLM, JQR, JQU, JRS, JRU
K (12) - BDK, DKM, EJK, GHK, HIK, JKR, JKS, KLS, KMT, KNO, KPT, KRS
L (11) - CHL, EGL, EIL, ELN, GLN, HLR, ILU, JLM, KLS, LNU, LOR
M (5) - CGM, DKM, HNM, JML, KMT
N (15) - ANQ, CON, CNT, ELN, EGN, GLN, GNR, HMN, IJN, KNO, LNU, NOT, NQS, NSO, NST
O (11) - BGO, CON, DOS, GIO, HJO, IOP, KNO, LOR, NOS, NOT, OTS
P (2) - IOP, KPT
Q (5) - AQN, DQS, JQR, JQU, NQS
R (8) - GNR, HLR, JKR, JQR, JRS, JRU, KRS, LOR
S (11) - DOS, DQS, FST, JRS, JKS, KLS, KRS, NQS, NST, NOS, OST
T (7) - CNT, FST, KMT, KPT, NOT, NST, OST
U (4) - ILU, JQU, JRU, LNU

(Edit: My horrible inaccurate list has been updated to reflect the comments below. If I had seen the BGO triangle, I may never have finished the puzzle as it is the kind of triangle I believe a "mean" constructor will certainly choose since it is the largest one without using any grid-lines possible. Of course, CGM and DOS also work in this way so its good I missed those too. The first part of my old logical path to eliminate KPT/FHI has the extra wrinkle of needing to test BGO but this will also fail)

So, my count above is 141 for 3x47 triangles. Considering my first draft of this list had 106 triangles (seemingly short of 36 which was my triangle count last year), a counting puzzle here is also difficult. Ok, so the logical path needs to focus on B, F, and P (assuming you notice those are the critical points and I only noticed B and P during the test). Either IOP and FST, or KPT and FHI (which also forces ABG). If you draw in the second, it forces CON. This forces U-J (but either QR), but then E cannot go anywhere. Great.

So IOP and FST. Now, it is either BDK or ABG. Let's say BDK. M must be in JLM or HMN, so either of these takes a vertex from NLU, so U connects to J (and one of QR) and M is HMN. Now, that forces EGL, but now C can't be ACG so it fails. So ABG! Great.

IOP, FST, ABG. Now CH (but either E or L). QJ (R or U), which finally forces DKM. R must now be to JQ, leaving LNU, and CEH.

Um, you testsolvers totally did not catch how unfair this puzzle is unless you guess and guess well. Does anyone have a good "logical" way through this? I really hit the bad side of the variance curve here, and I hope it doesn't cost me the title. Over 22% of my total time for 20 points.



(Post a new comment)


(Anonymous)
2008-06-14 11:56 pm UTC (link)
You might consider partitioning. It is easy to see that P and U are in different triangles, and also B and C are in still different
triangles. I admit it takes some work, but you can also see that F
is in a fifth triangle. As you work through the constraints, some of
your reasoning reappears if you organize it by finding allowable
partitions of the remaining points to each of the four triangles
and BAG. Let us know if this approach seems more logical and effective to you.

Gerhard Paseman

(Reply to this) (Thread)


[info]motris
2008-06-15 12:05 am UTC (link)
Thanks. This sounds like an interesting alternative frame to try to use. I can easily see how I'd label 6 of the vertices with different numbers, so maybe that could get me to visualize why some triangles aren't allowed easier. I don't know how much easier, but I'll try it again after a couple days and the answer slipping from memory.

(Reply to this) (Parent)


[info]jdyer
2008-06-15 12:20 am UTC (link)
If you want more puzzles like this, check Erich Friedman's site:

http://www.stetson.edu/~efriedma/tridots/

(Reply to this)

Don't get too bogged down...
[info]cyrebjr
2008-06-15 01:01 am UTC (link)
There's one more triangle: BGO. I am confident, though, that 48 is the correct total.

See, I came up with a parity trick for this. The endpoints of the big leg have to be an even number of units away in each of the horizontal and vertical directions. This divides the grid into four groups of nine intersections each, some of which are occupied by points: ACGHINO, BMP, DFKQST, and EJLRU. The third point might be in up to four places. Long story short, my counts for each group were 28, 0, 12, and 8, for 48 total.

Admittedly, I did not solve Dot Triangles at all (I even had trouble re-solving the example puzzle), but my method clearly shows that BMP belong to separate triangles, and by observation (if one knows to look there, of course), so are CFU. (Bitmap, see a few....)

(Reply to this) (Thread)

Re: Don't get too bogged down...
[info]motris
2008-06-15 01:28 am UTC (link)
Damn. I would totally have missed BGO even with all the quintuple checking. Thank goodness it wasn't a counting puzzle.

Your parity of leg distance rule is super interesting. I'll examine it to see where it goes too. Having just gotten a link to a bunch more of these puzzles by Erich Friedman, I may have a go at them sometime with some of this new thinking. On this puzzle today, I should have just been more careful and found B, F, and P as being the most constrained and bifurcated more effectively than I did when I wasn't including F in my set.

(Reply to this) (Parent)

Re: Don't get too bogged down...
[info]cyrebjr
2008-06-15 03:03 am UTC (link)
And just incidentally, N has 15 listed, and I and T are missing FHI and KPT.

(Reply to this) (Parent)(Thread)

Re: Don't get too bogged down...
[info]motris
2008-06-15 03:05 am UTC (link)
wow. I'm really bad at this data collection (counting) thing. Thanks for piecing through it so carefully.

(Reply to this) (Parent)(Thread)

Re: Don't get too bogged down...
[info]cyrebjr
2008-06-15 03:21 am UTC (link)
Actually, I just noticed that AIJ (in A only) isn't right. This means I haven't found all the mistakes, but I don't think I'll be looking for them.

(Reply to this) (Parent)


[info]nickbaxter
2008-06-15 05:52 am UTC (link)
There are 56 distinct triangles in my enumeration, corresponding to a triple-count of 168. This was manual, but I'm pretty confident it's complete. You are missing:
BGO, CGI, CFM, DOS, EGL, EIL, GIO,and KLS.

Some other errors in the list were already noted. The full list is:
- FHI missing from H and I lists
- EJK missing from J and K lists
- Count for N list should be 15
- KPT missing from T list
- AIJ should not be in A list

(Reply to this) (Thread)


[info]motris
2008-06-15 01:11 pm UTC (link)
Provided you mean CGM, not CFM, I can give you full credit.

(Reply to this) (Parent)(Thread)


[info]cyrebjr
2008-06-15 01:49 pm UTC (link)
Well, re-counting, I now get 15 from my EJLRU group and 13 from DFKQT, for a running/grand total of 56. The trick I provided may not be foolproof, but it should keep most triangles from being counted twice.

(Reply to this) (Parent)


[info]cramerica
2008-06-16 02:09 am UTC (link)
This was the one puzzle that I didn't even find an in for even after the contest. The sort of thing I'd let my computer knock itself out on.

(Reply to this) (Thread)


[info]motris
2008-06-16 02:11 am UTC (link)
Yeah - I'm wondering if anyone who didn't "have to do it" actually did it. Its my prediction for least attempted/completed puzzle with the line at about 5%

(Reply to this) (Parent)

Logical spoiler
(Anonymous)
2008-06-17 05:02 am UTC (link)
I had a nice writeup which solved this problem and which also exceeded the 4300 character limit that LiveJournal has for responses. It even had chemistry puns inside it. Of course I did not save it anywhere and a system reset sent it to where old bits go.

I take issue with your remark about the unfairness of the puzzle. By using the partitioning idea (which for me turned out to be AEFMOU) and combining it with the restrictions on PF, I came up with an analysis similar to yours which eliminated FHI and PKT as possibilities, and which left 3 choices for triangles for M. The partitioning helped me organize the relevant triangles into columns, and I ended up having to use a little more than half the triangles in the diagram to solve the puzzle.

Briefly, 3 is not an allowed distance for a triangle edge, and so the central square EFMO is a set of four points, no two of which can be on a triangle. (3 root 2 can also be shown not to be a distance.) A little more work allows one to add A and U to get six independent points.

One can now make a list of triangles for each of the six points, but to shorten the work, one uses the two triangles for P to eliminate some of the triangles needed. In each case, less than half the triangles need be considered.

In the case that FHI and PKT are considered, one sees that B can have at most two choices, which forces G not to be in the same triangle with M, which forces MJL and no possibilities for U.

In the case that POI and FST are chosen, there are at most three triangles that can contain M. Two of the possibilities quickly lead to a contradiction. The third leads to analyzing 3 possibilities
for U, two of which lead to a failed partition. The third of course gives the solution.

I've summarized the last bit of the analysis, but I think it uses a reasonable approach that could
allow someone who has practiced to do the puzle within 15 minutes. I think you should occasionally be given a puzzle that takes more than 15 minutes, even in competition. Or do you get too much of
that in your postdoc?

Gerhard Paseman

(Reply to this) (Thread)

Re: Logical spoiler
[info]thedan
2008-06-17 02:38 pm UTC (link)
> I think you should occasionally be given a puzzle that takes more than 15 minutes, even in competition.

Sure, but I think part of the issue is the point value. The test is 150 minutes long and has a maximum of 365 points; if this 20-point puzzle takes 15 minutes, that's 1/10 of the time allotted for less than 1/18 of the possible score. That's undervalued, particularly when you consider some of the other 20-point puzzles that are far easier.

The 3-square is a very nice find, and I'd like to think that's an intended break in. At the same time, I notice you're working into a 7-triangle puzzle with a 6-partition; obviously that eventually leads to a solution, but I'd feel better about it as an elegant puzzle if there was a clever way to partition a point for every triangle.

(Reply to this) (Parent)

Re: Logical spoiler
[info]motris
2008-06-17 03:32 pm UTC (link)
Well, thanks for trying to type a long analysis. What survives has some interesting bits. I still wonder if any analysis which requires so many characters, even allowing for playful metaphors and puns, is really what is needed for a 20-point (~ 8 minute) puzzle.

Your insight of the 3 length is very good and getting to the AEFMOU set is a great start, but even it - which is by no means a simple start if you've never done this kind of puzzle before - leaves a lot of work and there is no reason a priori to think that following up on partitioning is going to lead to the solution better than some other area you might not have discovered.

I do not agree that seeing all the triangles is easy (like BGO or DOS, which I'd tend to miss every time I was working on it), and it is quite likely in the midst of a rushed-solved at a USPC, you would make an error in an exhaustive search that would keep you from seeing a solution. Having read the horror stories of peoples' experiences with the Ampers&, where there are 2-4 work-ins based on either letters, or words that are very forcing (Beandip), or searching for all possible 4 word rings as I did, but it is easy to make a mistake or think you've made a mistake, I think you need a "hot spot" here for the puzzle to feel fair - I'd want to be able to draw in a single triangle (or just a single edge) with confidence in a reasonable time.

If P had had two choices but they were PTK and PI*K, where I is the point from moving that vertex one space to the left, well, then that is a puzzle with a work-in. Putting in PK now limits triangles around K. Imagining a fantasy world where this new I* doesn't add triangles to B. You could now write in BG as an edge, since K being removed from BDK leaves two choices that both share BG. Pulling out G from triangles that don't go to B might lead to a further edge/triangle. This would be satisfying. I've always felt what separates puzzles humans should solve from "puzzles" computers should solve is that an efficient set of rules leads to an answer where exhaustive search without such rules will be inefficient. I also think puzzles should be fun, and in a non-USPC situation, they should be something I want to do. Dot Triangles, at least this example, seems to fail on both points.

There is something about a puzzle that you can solve and know, this is THE solution, which is satisfying. It takes more work than a 20-pointer requires, at least with the methods I've read so far, to get to the "unique solution" part of this puzzle, than I'd prefer.

(Reply to this) (Parent)(Thread)

Re: Logical spoiler
[info]zotmeister
2008-06-18 06:00 pm UTC (link)
"I've always felt what separates puzzles humans should solve from "puzzles" computers should solve is that an efficient set of rules leads to an answer where exhaustive search without such rules will be inefficient. I also think puzzles should be fun, and in a non-USPC situation, they should be something I want to do. Dot Triangles, at least this example, seems to fail on both points."

Thank you so much - I'm glad I'm not the only one who sees it that way. I would add that I see puzzles as an art, and that there's no elegance to a brute-force-only guessfest. I could see a carefully-crafted Dot Triangles expressing cleverness, but the one on the test, well... sorry, I can't resist: it fails on all three points. - ZM, who swears he didn't make this comment just to make that pun

(Reply to this) (Parent)


[info]ztbb
2008-06-18 09:55 am UTC (link)
I was certainly very lucky when testsolving this puzzle (which I imagine Nick was able to infer, since my solving comments included at least one totally incorrect statement that makes it clear my solution was rather fluky). Like you, I left this puzzle for last, thinking that it looked brutal. I solved it in around 27 minutes (including 6 minutes of "prep work" thinking about the possible sizes and orientations of triangles, some or all of which I would normally have done before taking the competition).

After some amount of trial and error (maybe half of the 21 minutes? I'm not sure) my intuition was that relatively few triangles involved P, so I checked carefully and saw that there were indeed only two. Other vertices that had seemed to be members of few triangles were C and F, so I enumerated those as well, somehow completely missing some of the C triangles, but very luckily not CEH. Now there were only two ways of using P and F, so I set out to try them both, and it happened that I used IOP/FST first; with my possibilities for C more restricted than reality, but including the correct CEH, I finished the puzzle rapidly after that. So I got lucky twice, first because of the missing C triangles, second because I tried the right P/F combination first.

(Reply to this)


Create an Account
Forgot your login?
Login w/ OpenID
English • Español • Deutsch • Русский…