Programming puzzles: processing lists!

[pier4r]

(08-15-2017 02:50 PM)DavidM Wrote:  My current test found 105 possible pairings:

This is what I hoped. Either someone does an implementation plus a proof of a solid hash function, or, well, we need attempts. I'll scan your 105 results, then I compare them to mine to see if I have to improve things.

I have to say that, aside from backtracking (that quickly get unpractical due to the complexity) the problem is really interesting, especially to find useful list/array routines.

my gawk implementation on the 1.73 ghz Dothan took over 80 minutes for 16 teams, so I killed it (I do not have the results). But if I miss something, it makes no sense, so I thank you for your results, I have something to compare to now.

PS: I think that better environments to attack the problem are, in the RPL/HP related world: sysrpl / newRPL / hppl (maybe rpl/2 if I got to know how to fix some compilation problems) plus a bit of optimizations.

[DavidM]

(08-15-2017 07:39 PM)pier4r Wrote:  my gawk implementation on the 1.73 ghz Dothan took over 80 minutes for 16 teams, so I killed it (I do not have the results). But if I miss something, it makes no sense, so I thank you for your results, I have something to compare to now.

I also tried a completely different method and got the exact same results for 8 teams. Now of course it could simply be because the same developer created the same problems in a slightly different way, but it does at least give one more data point to consider.

(08-15-2017 07:39 PM)pier4r Wrote:  PS: I think that better environments to attack the problem are, in the RPL/HP related world: sysrpl / newRPL / hppl (maybe rpl/2 if I got to know how to fix some compilation problems) plus a bit of optimizations.

After approaching this a couple of different ways now, I'm thinking that my next attempt will be to treat this as a specialized lexicographic sequence. In doing so, the hard part then becomes determining how to step through the sequence properly. My previous attempts were actually just modified forms of full permutations that would simply discard all inappropriate results, which is why they slowed down immensely with increasing team counts.

This sequencing technique is actually the same way DOCOMB and DOPERM work internally. There's a "control mask" that designates the order/selection of list elements, and some Saturn routines manipulate the mask by stepping up (or down) in lexicographic order. So if we can determine how to "step" the sequence properly, we can then simply return each team list in the sequence. That's easier said than done, though.

The nice part about this particular challenge is that there is no need for a mask; the mask is the actual input (and output, after modification). In other words, once you "step" the team list, you just format it appropriately and move on the next one. There's no need to "apply the mask" to some other list in this case.

[pier4r]

(08-15-2017 08:29 PM)DavidM Wrote:  The nice part about this particular challenge is that there is no need for a mask; the mask is the actual input (and output, after modification). In other words, once you "step" the team list, you just format it appropriately and move on the next one. There's no need to "apply the mask" to some other list in this case.

yeah but while generating a valid match day from another is relatively easy (swap two teams) the point is: was that match day already generated? Thanks for the other data point though. I strongly believe my hash function is not so foolproof although it should now include two parameters to identify a pairing quite uniquely. Well, I will check.

Ok then I need to improve my method of construction, because my hash values continue to fail, it seems that I have to rely on a smart construction method to get the proper answer. Nice challenge (and it is still 10% of a larger problem). (note: nice - tricky but not overwhelming. Because otherwise I can find plenty of overwhelming challenges for my relatively low skill)
1-3 2-5 4-6 7-8
1-4 2-3 5-7 6-8
50400

[DavidM]

(08-15-2017 09:03 PM)pier4r Wrote:  yeah but while generating a valid match day from another is relatively easy (swap two teams) the point is: was that match day already generated?

But the point to consider is that a single step through the sequence isn't the same thing as simply swapping the position of two list elements. A single lexicographic step will almost certainly involve an entire sequence of operations/comparisons/swaps to move from one valid position to the next one.

One nice thing about doing it this way is that you don't have to consider whether that grouping has come up before -- if the sequence truly has a lexicographic representation (and you can create the algorithm to step through it ), then you simply step through each member in order.

As I mentioned before, the trick is in creating a working algorithm that takes you from one valid sequence point to the next. Having 3 (hopefully) good sequences to use as a reference (4/6/8 teams) should provide some clues as to what that "stepping" algorithm needs to do. I believe the chances are good that this problem has a valid stepping algorithm, so the fun of this puzzle (from my perspective) will be to see if I can deduce a working algorithm to facilitate it.

[pier4r]

uh yes if there is a pattern (and maybe there is, just I did not attempt to find it) to generate each valid sequence from the previous, then yes that would be likely the fastest approach.

Though also side approach are not that bad in terms of required solutions. Aside from backtracking, I cannot like it.

[pdo]

Hello,

I don't know if this has been mentioned already for #37, and excuse me if I'm barging in and stating the obvious here, but I think there is a simple proof that the total number of match-day pairings for any even N is equal to (N-1)(N-3)(N-5)...1 and an efficient/elegant way of enumerating them would probably be recursive in nature.

Paul

[pier4r]

(08-16-2017 12:51 PM)pdo Wrote:  Hello,

I don't know if this has been mentioned already for #37, and excuse me if I'm barging in and stating the obvious here, but I think there is a simple proof that the total number of match-day pairings for any even N is equal to (N-1)(N-3)(N-5)...1 and an efficient/elegant way of enumerating them would probably be recursive in nature.

Paul

Well I cannot have an opinion on this if you don't say more. How do you get the (N-1)(N-3)(N-5)...(N-N-1) formula? Would be nice to have a reference.

Plus I am pretty sure the problem is already long solved because people had to make calendars for sport leagues long ago. Personally I try first to attack the problem on my own (it is even better when other people are interested and try on their own) before checking existing results that would spoil the fun. Also I learned that when I try by myself and I make some sort of progress and then I get stuck, I appreciate and understand existing results better.

[DavidM]

(08-16-2017 12:51 PM)pdo Wrote:  Hello,

I don't know if this has been mentioned already for #37, and excuse me if I'm barging in and stating the obvious here, but I think there is a simple proof that the total number of match-day pairings for any even N is equal to (N-1)(N-3)(N-5)...1 and an efficient/elegant way of enumerating them would probably be recursive in nature.

Paul

Well I think it's safe to say that you are neither "barging in" nor "stating the obvious", since neither of the two previously-active participants for this problem seemed to have deduced the equation for the number of "match-days".

I hope you have the time (and inclination) to put something together for this. It would be nice to see how you approach it!

[pdo]

(08-16-2017 03:03 PM)DavidM Wrote:  

(08-16-2017 12:51 PM)pdo Wrote:  Hello,

I don't know if this has been mentioned already for #37, and excuse me if I'm barging in and stating the obvious here, but I think there is a simple proof that the total number of match-day pairings for any even N is equal to (N-1)(N-3)(N-5)...1 and an efficient/elegant way of enumerating them would probably be recursive in nature.

Paul

Well I think it's safe to say that you are neither "barging in" nor "stating the obvious", since neither of the two previously-active participants for this problem seemed to have deduced the equation for the number of "match-days".

I hope you have the time (and inclination) to put something together for this. It would be nice to see how you approach it!

Hi David,

Sorry for being cryptic, it was just a quick post after my lunchtime reading (this forum).

My reasoning is as follows: given a list of N items (N even) take the first item, then you have a choice of N-1 items with which to pair it. Choose one, then remove both items from the list. This will leave a list of N-2 items to which you can apply the same procedure, this time giving a choice of N-3 items, and so on. This gives a total number of possible "routes" through this process of (N-1)(N-3)(N-5)...1. For a proper proof we'd need to show each route gives a unique result -- seems plausible to me, but I think it requires a bit more thought to put into words.

As far as a program to compute the pairings goes, I was imagining a function recursing on the list in a similar way to my description above, but collecting all the possible choices and collating the results. I can imagine how to do this in a language like Lisp, for example, but on the way home from work I got to thinking how I would implement this in RPL, and to be honest I'm not sure how I would go about it. Stuff to ponder...

Paul

[pier4r]

(08-16-2017 06:58 PM)pdo Wrote:  My reasoning is as follows: given a list of N items (N even) take the first item, then you have a choice of N-1 items with which to pair it. Choose one, then remove both items from the list. This will leave a list of N-2 items to which you can apply the same procedure, this time giving a choice of N-3 items, and so on. This gives a total number of possible "routes" through this process of (N-1)(N-3)(N-5)...1. For a proper proof we'd need to show each route gives a unique result -- seems plausible to me, but I think it requires a bit more thought to put into words.

Then I saw through your hints properly. The idea is nice (and sort of what I do but without thinking about a formula) but as you said I am not entirely convinced that it gives only unique results.

Actually the #37 is a particular case of https://en.wikipedia.org/wiki/Matching_(graph_theory) so I believe what we are trying to solve is long solved. Just, as I wrote, before looking around I try to not spoil the fun (and learning experience) by myself.

For the recursive way: I thought too to make a tree (like a tree for keys) building it as soon as I pick elements, but the problem is that I may build elements that are just swapped. Like 1-2 3-4 and 3-4 1-2 . So in one case the tree will follow the branch 1-2 and the other 3-4 considering the two complete results different.

Instead if one find an order with built in "safety of no duplicates", like DavidM wants to do it, I guess it will be the most effective way.

[DavidM]

(08-16-2017 06:58 PM)pdo Wrote:  I can imagine how to do this in a language like Lisp, for example, but on the way home from work I got to thinking how I would implement this in RPL, and to be honest I'm not sure how I would go about it. Stuff to ponder...

Even if you start by implementing it in Lisp and confirming the result counts (and possibly lists as well), that would be useful for helping to nail down the targets. Your formula and description certainly seem plausible.

(08-16-2017 07:33 PM)pier4r Wrote:  Instead if one find an order with built in "safety of no duplicates", like DavidM wants to do it, I guess it will be the most effective way.

I'm still struggling to find the elusive algorithm to do that, if it even exists. Looking at the result lists I have sure makes it appear that there is a pattern, but so far I'm not coming up with the right steps to match it. The goal, of course, is ultimately to limit the inner loops to the minimum needed iterations to produce the full result set. Assuming Paul's formula is correct and a recursive solution is created that matches the described groupings, then it would probably be even more efficient. My initial recursive attempts became unwieldy because they had to cull out unneeded branches of combinations.

[pier4r]

In terms of going through the matches building them without duplicates I thought at the start, and then left because I still wish to make a proper hash function, the following:

we know that for 4 teams one can have
1-2 3-4
1-3 2-4
1-4 2-3

so if one has this "blocks", adding other 2 teams should bring the following :
1-2 (all the blocks between 3,4,5,6 see with 4 teams) : 3 blocks
1-3 (all the blocks between 2,4,5,6) : 3 blocks
1-4 (all the blocks between 2,3,5,6) : 3 blocks
1-5 (like above)
1-6 (...)
2-3 (...)
2-4 (...)
2-5 (...)
2-6 (...)
3-4 (...)
3-5 (...)
3-6 (...)
4-5 (...)
4-6 (...)
5-6 (...)

One can see here that likely a lot of duplicates are made (ex: 5-6 3-4 1-2), even with 3 basic blocks (that then gets expanded).

And I agree with DavidM. Whatever the implementation (even in Malebolge, no ok not in Malebolge), please share!

[pdo]

(08-16-2017 08:10 PM)pier4r Wrote:  And I agree with DavidM. Whatever the implementation (even in Malebolge, no ok not in Malebolge), please share!

Okay, you asked for it :-)

This is my quick-and-dirty implementation in Common Lisp:-

Code:


(defun generate-match-pairings (players)
  "Generate a list of all player pairings.
Where PLAYERS is a list of objects unique under EQL comparisons."
  (if (eql 2 (length players))
      (list players)
      (loop
         :with a := (first players)
         :for b :in (rest players)
         :append (let ((remaining (remove b (rest players))))
                   (mapcar (lambda (match-pairing)
                             (list* a b match-pairing))
                           (generate-match-pairings remaining))))))

and here is a function that takes the lists produced by the above routine and prints them out in a more readable form:-

Code:


(defun print-match-pairings (match-pairings)
  (dolist (match-pairing match-pairings)
    (loop
       :for even := t :then (not even)
       :for players :on match-pairing
       :when even
       :do (format t " ~A-~A" (first players) (second players)))
    (format t "~%")))

so if I invoke those functions as:-

Code:


(print-match-pairings (generate-match-pairings '(1 2 3 4 5 6)))

I get the following 15 lines:-
1-2 3-4 5-6
1-2 3-5 4-6
1-2 3-6 4-5
1-3 2-4 5-6
1-3 2-5 4-6
1-3 2-6 4-5
1-4 2-3 5-6
1-4 2-5 3-6
1-4 2-6 3-5
1-5 2-3 4-6
1-5 2-4 3-6
1-5 2-6 3-4
1-6 2-3 4-5
1-6 2-4 3-5
1-6 2-5 3-4

Now I am aware that I am probably the only person here who is familiar with Common Lisp, which makes the above of somewhat limited use :-), but maybe it will pique your (or someone else's) interest enough to consider learning the language. It is very productive for this kind of explorative programming! Don't be scared by the parenthesis!

Anyway, the basic principle of operation is that the function recurses down on the input list, shortening it by two elements each time. It returns a list of match-pairings, where a match-pairing is simply a flat list of objects, implicitly pairing together items at index 1 & 2, 3 & 4, etc.

Hope this is enough to give the general idea.

Paul

[DavidM]

(08-16-2017 10:21 PM)pdo Wrote:  Okay, you asked for it :-)

This is my quick-and-dirty implementation in Common Lisp:
...

Thanks, Paul! There's a couple of folks here that I've seen make references to using Lisp, so there may be more interest in it than you think. It's been a loooooong time since I did a translation of some Lisp code once, but hopefully I remember enough to make sense of what you've provided.

I'm not able to run the code directly -- would you mind doing a sample run of 8 and 10 teams? It would be useful for validating other methods. If you'd rather not post the long lists, feel free to PM the results.

[SlideRule]

(08-15-2017 09:36 PM)DavidM Wrote:  ... the trick is in creating a working algorithm that takes you from one valid sequence point to the next ... what that "stepping" algorithm needs to do ... the chances are good that this problem has a valid stepping algorithm ... a working algorithm to facilitate it...

An interesting url for Tournament Scheduling! presents a geometric model which could be transformed into a mathematical model {i.e. programmed}. Irrespective, it is a good read.

BEST!
SlideRule

[pier4r]

(08-16-2017 10:21 PM)pdo Wrote:  Now I am aware that I am probably the only person here who is familiar with Common Lisp, which makes the above of somewhat limited use :-), but maybe it will pique your (or someone else's) interest enough to consider learning the language. It is very productive for this kind of explorative programming! Don't be scared by the parenthesis!

First, thanks. Then a couple of observations about this.
Unless you use esoteric languages (see malebolge or brainfuck) I guess every language, even with a functional or declarative (prolog) paradigm could be read somehow. Well if we want to be honest it is possible to write some oneliners that looks unreadable in perl or awk as well.

Second, as you said, it can be an input to make other people interested, so I think it is always good to share rather than saying "Nah, (I think) no one uses this language so I keep it for myself". Especially in forums like this where people are normally interested rather than scared.

Third. Lisp (or Ocaml or haskell) are since long time in my todo list, the problem is that I am spread on too many languages already (at the moment RPL and variants, javascript, php, perl, bash, powershell, awk, applescript, basic variants) that I cannot add more without losing track of what I do. Or better I should add the hppl of the prime application.

Your code just confirmed that I should hurry up to reach a satisfying level (for me) in those languages and start with a functional one.

(08-17-2017 12:04 AM)SlideRule Wrote:  An interesting url for Tournament Scheduling!

The geometric model is literal! I was thinking something about geometric series. Nice link.

[pdo]

(08-17-2017 07:27 AM)pier4r Wrote:  Your code just confirmed that I should hurry up to reach a satisfying level (for me) in those languages and start with a functional one.

There's never enough time to do all the things you want to do!

A small suggestion: if you're looking to learn a simple functional language then take a look at Scheme. It's in the Lisp family of languages, but is very small and elegant. There are many different implementations, and a full-featured, batteries-included one is Racket. I haven't used it for a while, but when I did it was very easy to get going.

Paul

[pdo]

I couldn't resist. It hooked me in again, so here's my RPL translation of the Lisp program I posted. It's not particularly pretty, but I thought I'd post it anyway.

Firstly, I created a utility function called LFLTP (Lisp FiLTer on Positions). Its stack diagram is
(List Positions -> RemainderList ExtractedList)
where List is an arbitrary list of things and Positions is a list of positive indexes.
The function then extracts all those objects referenced by the indexes and places them in the ExtractedList, leaving the other objects in RemainderList.

The definition of LFLTP is

Code:


\<< { } { } \-> wnt got rem
  \<< 1.
    \<<
      IF wnt NSUB POS
      THEN 'got'
      ELSE 'rem'
      END STO+
    \>> DOSUBS
    rem REVLIST
    got REVLIST
  \>>
\>>

Then I wrote my equivalent of generate-match-pairings, which I called LAMP (List All Match Pairings). Its code is

Code:


\<< { } \-> mps
  \<<
    IF DUP SIZE 2. == THEN
      1. \->LIST 'mps' STO+
    ELSE
      2. OVER SIZE FOR n
        DUP 1. n 2. \->LIST
        LFLTP SWAP
        LAMP
        DUP SIZE ROT SWAP NDUPN \->LIST SWAP
        2. \<< + \>> DOLIST
        'mps' STO+
      NEXT
      DROP
    END mps REVLIST
  \>>
\>>

which as I said above is not too pretty, and could do with refactoring into smaller routines to make it digestible. The main thing to note is the recursive call of LAMP in the middle.

Some runs:-

{1 2 3 4 5 6} 'LAMP' TEVAL
returns a list of 15 entries and takes about 3.5 seconds.

{1 2 3 4 5 6 7 8} 'LAMP' TEVAL
returns a list of 105 entries and takes about 27 seconds.

{1 2 3 4 5 6 7 8 9 10} 'LAMP' TEVAL
returns a list of 945 entries and takes about 256 seconds.

Seems to be growing with a factor of approx N-1, which seems reasonable. I didn't try anything longer for fear of running out of memory and/or battery power! (I am using a 49g+ so can't run it off USB power.)

Hope this is interesting for someone (other than me, and perhaps David and Pier :-)

Paul

[pier4r]

(08-19-2017 09:59 PM)pdo Wrote:  (I am using a 49g+ so can't run it off USB power.)

Hope this is interesting for someone (other than me, and perhaps David and Pier :-)

Paul

Why cannot the 49g+ run from USB power? I thought it was like the 50g just with a different keyboard.

Anyway thanks for the contribution (it was already nice with lisp, now we have two languages!). Did you confirm/sort of prove that your approach is the correct one?

My attempt is on hold (and after it I have the #34) but surely I'll use your result and code as "correct" (unless proved otherwise) to verify the result. I want to make an hash comparing function. Of course building the list of possible match days safely is better and more efficient. Your code in RPL is already faster than mine in gawk.

About the readers, you never know who is interested. For example I am reading _now_ topics about the HHC 2016 RPL challenge, just the original statement is unavailable so I am not sure where to find it. (Would be nice when those files would be hosted on a stable http/ftp location instead of dropbox that may change URLs). The point is, readers can read even with years of delay, so the more the useful info in a thread, the better.

[pdo]

(08-20-2017 06:18 AM)pier4r Wrote:  Did you confirm/sort of prove that your approach is the correct one?

We need to show two things: all possibilities are generated and no possibility is generated twice. My reasoning for believing that this is indeed the case is summarized as follows:-

At each stage of the recursion we gather together all possibilities for a partner to the first element of the list, so I think we can be sure that all possibilities are generated.

Also, at each stage of recursion, we remove the partnered pair from the list supplied to the next stage. So as long as each partnered pair is associated with only one recursive invocation then we can be sure that no duplicate match-pairings will be generated.

Hope this makes sense!

Paul