Problem 58528. ICFP 2023:Orchestra - Greedy algorithm for Musician Placement
The ICFP 2023 Competition in July was to place musicians on a stage to maximize the attendees net happiness. The musicians played various instruments with attendees having preference values for each instrument type. Musicians could block attendees from seeing musicians behind them. Blocking occurs if a_i to m_j vector touched within 5 of m_k. No musicians allowed within 10 of one another. Vector check is being done with a prior Cody 1446 solution variant. Volume per musician was allowed but not in this Challenge. Happiness drops off as the square of distance between musician and attendee.
The ICFP 2023 site will hopefully have contestant writeups. The ICFP 2023 Orchestra Spec shows details of the contest. I modified the problem contents to the sufficient elements regarding the stage. The joys of JSON can be viewed. The musician types were upgraded by 1 to be non-zero based.
This Challenge is to place the 16 musicians onto the stage,mxy, of Problem 22 using a Greedy algorithm using provided Happiness tables. Score an Attendee happiness of higher than 46 million; Best known 47221761. The standard inputs are detailed in the function template and include axy-attendee positions, am-attendee happiness factors to each instrument, mu-instruments of each musician, stage limits-[xmin xmax ymin ymax]. This stage is a line of ymin=ymax=10, xmin=10, and xmax=990, seen in the image below. The special performance tables provide Joy values for Musician types vs X. Table mscrit, matrix_score_XvsType, assumes no neighbors and mscrit10 assumes neighbors at +/-10 blocking thus gives less Joy.
Individual attendee happiness= 1000000*am(i,mu(j))/d2(i,j) for attendee-i and musician-j where d2 is distance squared.
Simplest solution would be mxy(:,1)=10:10:160 where mxy(:,2)=10 but this scores only 13M suffering from 1/d2 and blocks.
Please submit the template to view the tables and graphs. The graphs show the mscrit and mscrit10 information.
This is the Orchestra room problem 22 showing the attendees and the stage.
The stage is the line on the bottom at Y=10 extending in X 10:990 .
Solution CommentsShow comments
Problem Recent Solvers1