Post Reply 
Programming puzzles: processing lists!
08-14-2017, 12:12 PM (This post was last modified: 08-15-2017 07:31 AM by pier4r.)
Post: #179
RE: Programming puzzles: processing lists!
So, after having done the #37 in userRPL (as reported above, I am not 100% sure that all the possible match days are found, nor duplicates are excluded), I realized that my algorithm is not that fast (and no I am not fan of "full stack no variables").

So I started to search another platform that is as quick, for development, as userRPL. really RPL is amazing.

I tried newRPL since it has the new integration for text files. Unfortunately it does not run in my winXP machine (machine for the 50g). It has to wait until I setup the win10 system.

I tried RPL/2, since it is a great project that deserved to be used too, but the last version of the 4.0.x release does not compile easily in cygwin 2.5.2 , I spent some hours on it but nothing. I'll try another time.

I completely forgot about the HP prime on android (those are the moment I need to use that beast), damn me, and so the closest small and quick language that I know that could do the task is awk (although it lacks of many array manipulation functions or central repositories for libraries, well I do them myself, even if poorly. Python with no curly braces or blocks defined not only by empty lines is not really liked by me)

awk 4.1.4 on cygwin 2.5.2, pentium M 1.73 Ghz.

the following is wrong, see the edits.
4 team: 3 matchdays, 2 seconds.
8 teams: 67 matchdays, 2 seconds.
10 teams: 5002 matchdays, 1min 40 seconds.

Would be helpful if someone else can match the 8 teams matchdays. If there are more or less.

PS: of course this will lead to the next challenge. Given the list of all matchdays, find all the possible valid schedules. That is, with N teams, find N-1 matchdays where every team is paired with any other team. But I will have to clarify it better in the first post.

edit: I found failures in the hash function that I devised. With 6 teams
1-6 2-4 3-5 : value 336
1-5 2-6 3-4 : value 336
1-6 2-3 4-5 : value 315
1-4 2-5 3-6 : value 315

So likely my program does not found all valid match days, but still I did not find duplicates. I need to redesign my hash function.

Edit2: second quick approach. Still not foolproof, just working on intuition and missing counterexamples.
A pair is composed by two different numbers that won't appear in other pairs (given a match day).
So while the sum may match for two different pairings, it is unlikely (I would say impossible, but I did not formalized this), that the sum and the absolute difference between two numbers will match.

Nevertheless having x+y=s and |x-y|=d should describe the two numbers better than the only sum. Then to "combine" this information I use the multiplication, since a number can be determined by its factors uniquely.

So now I do not have only the products of the sum of the teams in each pair, but the product of the sum and the absolute difference between the teams in each pair.

1-6 2-4 3-5 : 7*5 * 6*2 * 8*2 : 6720
1-5 2-6 3-4 : 6*4 * 8*4 * 7*1 : 5376
1-6 2-3 4-5 : 7*5 * 5*1 * 9*1 : 1575
1-4 2-5 3-6 : 5*3 * 7*3 * 9*3 : 8505

Plus found also a mistake in swapping teams.

edit3:
Ok the new hash function seems to be more robust (although not proven).
4 teams, 3 match days
6 teams, 15 match days
8 teams, 100 match days
10 teams, 870 match days

all those pretty quick (I had also to fix some helper functions, gawk is surprisingly empty, ready for new libraries)

Now running 16 teams, is taking a while.

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 08-14-2017 12:12 PM



User(s) browsing this thread: 5 Guest(s)