Seating couples round a table - alternative view of handbell

No need to worry about going "off topic" here
Forum rules
This forum is for general chit-chat, not necessarily APL-related. However, it's not for spam or for offensive or illegal comments.

Re: Seating couples round a table - alternative view of hand

Postby nicholas.small on Thu Jul 29, 2021 10:53 am

> That approach does not fully work...
Yes, I realized before I tried it that with an odd number of pairs the symmetric extra case allowed duplications, so clean was still required.
More interestingly, a 50% improvement in performance resulted from reversing the order in which the items are processed in the loop, using

rgs←len ⍙ring¨⍳p-1
((p-1)⊃rgs)←{(⌈(⍴⍵)÷2)↑⍵}(p-1)⊃rgs
set←rgs←⌽rgs

I have not had a close look at your latest approach. However, I did try it for 9 pairs but noticed no improvement in performance. (I am running unicode version 18.0.39659.0)
nicholas.small
 
Posts: 23
Joined: Tue Mar 30, 2021 8:45 pm

Re: Seating couples round a table - alternative view of hand

Postby Veli-Matti on Mon Aug 02, 2021 9:01 am

I made some changes in the code - e.g. using matrices instead of nested vectors, and thus I could get the following results:

pairs - results - used time
1 - 1
2 - 0
3 - 0
4 - 1
5 - 2
6 - 0
7 - 0
8 - 192
9 - 1 200 - 0.5 s
10 - 0 - 3 s
11 - 0 - 26 s
12 - 456 960 - 1 min 58 s
13 - 4 009 024 - 35 min 18 s
14 - 0 - 3 h 44 min 44 s
15 - 0 - 1 day 22 h 27 min

There _seems_ to be a pattern here (no results for 18 and 9 pairs?), but I don't have time to proceed further.

The code (sorry for short variable names and no commenting):

z←seats p;b;c;e;f;i;l;n;r;s;⍙rg

⍙rg←{v←⊃(1-⍳⍺-⍵+1)⌽¨⊂⍺↑(≢,⊢,≢)⍵⍴0 ⋄ 2>⍵:v
∪v⍪⊃(1-⍳⍵-1)⌽¨⊂⍺↑⍵(,,⊣)0⍴⍨⍺-⍵}

i←1 ⋄ z←0⍴⍨0,l←2×p-1 ⋄ s←r←l ⍙rg¨⌽⍳p-1

:Repeat
:If 0∊⍴l←i⊃s ⋄ i←i-1
:ElseIf i=≢s ⋄ i←i-1 ⋄ z⍪←l
:Else ⋄ s[i]←⊂1↓l ⋄ n←1+i
s[n]←⊂p←((2×n)=+/0≠p)⌿p←(1⌷l)+[2]n⊃r
i←i+~0∊⍴p
:EndIf
:Until 0=i

s←b←0∧f←⊣/z ⋄ e←f=l←⊢/z

:For i :In ∪f
s←s∨i=f ⋄ c←e<s<i=l
b←b∨c\(↓c⌿z)∊↓⌽(e<i=f)⌿z
:EndFor

:For i :In ⍸e
:If i⊃e ⋄ e←e\1≠z[,i;]⍳⌽e⌿z ⋄ :End
:EndFor

z←0,0,(e⍱b)⌿z


-Veli-Matti
Veli-Matti
 
Posts: 93
Joined: Sat Nov 28, 2009 3:12 pm

Re: Seating couples round a table - alternative view of hand

Postby nicholas.small on Mon Aug 02, 2021 9:24 pm

That certainly is a leap in performance.

A pair separated by an even number of places will be sitting in one odd numbered seat and one even numbered one. A pair separated by an odd number of places will be sitting in two odd numbered seat or two even numbered ones. There are equal numbers of odd and even seats, so, for a solution to be possible, there cannot be an odd number of pairs separated by an odd number of places. If we to do our counting in ⎕IO←0, the parity of the pair will match the parity of the number, and we see that 2, 3, 6, 7, 10, 11, 14, 15, 18, 19, etc. pairs will have no solution. (I.e. no solution if {1=2|⌊⍵÷2}p.)

Nicholas
nicholas.small
 
Posts: 23
Joined: Tue Mar 30, 2021 8:45 pm

Previous

Return to Chat

Who is online

Users browsing this forum: No registered users and 1 guest