001package ball.riddler538.ant.taskdefs;
002/*-
003 * ##########################################################################
004 * Solutions for the 538 Riddler
005 * %%
006 * Copyright (C) 2015 - 2022 Allen D. Ball
007 * %%
008 * Licensed under the Apache License, Version 2.0 (the "License");
009 * you may not use this file except in compliance with the License.
010 * You may obtain a copy of the License at
011 *
012 *      http://www.apache.org/licenses/LICENSE-2.0
013 *
014 * Unless required by applicable law or agreed to in writing, software
015 * distributed under the License is distributed on an "AS IS" BASIS,
016 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017 * See the License for the specific language governing permissions and
018 * limitations under the License.
019 * ##########################################################################
020 */
021import ball.swing.table.MapsTableModel;
022import ball.swing.table.SimpleTableModel;
023import ball.util.ant.taskdefs.AntTask;
024import java.util.ArrayList;
025import java.util.Arrays;
026import java.util.Collections;
027import java.util.List;
028import java.util.Map;
029import java.util.TreeMap;
030import lombok.Getter;
031import lombok.NoArgsConstructor;
032import lombok.Setter;
033import lombok.ToString;
034import org.apache.tools.ant.BuildException;
035
036import static org.apache.commons.lang3.StringUtils.EMPTY;
037
038/**
039 * {@link.uri http://ant.apache.org/ Ant} {@link org.apache.tools.ant.Task}
040 * to solve
041 * {@link.uri
042 * http://fivethirtyeight.com/features/will-someone-be-sitting-in-your-seat-on-the-plane/
043 * Will Someone Be Sitting In Your Seat On The Plane?}
044 * <p>
045 * There's an airplane with 100 seats, and there are 100 ticketed passengers
046 * each with an assigned seat.  They line up to board in some random order.
047 * However, the first person to board is the worst person alive, and just
048 * sits in a random seat, without even looking at his boarding pass.  Each
049 * subsequent passenger sits in his or her own assigned seat if it's empty,
050 * but sits in a random open seat if the assigned seat is occupied.  What is
051 * the probability that you, the hundredth passenger to board, finds your
052 * seat unoccupied?
053 * </p>
054 * Solution uses the Monte Carlo method.
055 *
056 * {@ant.task}
057 *
058 * @author {@link.uri mailto:ball@hcf.dev Allen D. Ball}
059 */
060@AntTask("solve-riddle-2016-02-19")
061@NoArgsConstructor @ToString
062public class SolveRiddle20160219Task extends AbstractSimulationTask {
063    @Getter @Setter
064    private int passengers = -1;
065    @Getter @Setter
066    private int seats = 100;
067
068    @Override
069    public void execute() throws BuildException {
070        super.execute();
071
072        if (getPassengers() < 0) {
073            setPassengers(getSeats());
074        }
075
076        try {
077            List<Integer> passengers = asList(0, getPassengers());
078            List<Integer> seats = asList(0, getSeats());
079            ArrayList<Simulation> simulations = new ArrayList<>(getCount());
080
081            for (int i = 0, n = getCount(); i < n; i += 1) {
082                simulations.add(new Simulation(passengers, seats));
083            }
084
085            int passengerN = passengers.get(passengers.size() - 1);
086            int seatN = passengerN;
087            int successes = 0;
088
089            for (Simulation simulation : simulations) {
090                if (simulation.get(seatN) == passengerN) {
091                    successes += 1;
092                }
093            }
094
095            log(new SimpleTableModel(new Object[][] { }, 3)
096                .row("seats:", getSeats(), EMPTY)
097                .row("passengers:", getPassengers(), EMPTY)
098                .row("count:", simulations.size(), EMPTY)
099                .row("successes:", successes, asPercent(successes, simulations.size()) + "%"));
100
101            String[] headers = new String[] { "passenger", "seat#" + seatN + "count", "%", "cum%" };
102            ArrayList<Map<Integer,Number>> maps = new ArrayList<>();
103
104            maps.add(new TreeMap<Integer,Number>());
105            maps.add(new TreeMap<Integer,Number>());
106            maps.add(new TreeMap<Integer,Number>());
107
108            for (int passenger : passengers) {
109                maps.get(0).put(passenger, 0);
110            }
111
112            for (Simulation simulation : simulations) {
113                int passenger = simulation.get(seatN);
114
115                maps.get(0).put(passenger, maps.get(0).get(passenger).intValue() + 1);
116            }
117
118            float cumulative = (float) 0;
119
120            for (int passenger : passengers) {
121                float probability = asPercent(maps.get(0).get(passenger), simulations.size());
122
123                maps.get(1).put(passenger, probability);
124
125                cumulative += probability;
126
127                maps.get(2).put(passenger, cumulative);
128            }
129
130            log();
131            log(new MapsTableModel(maps, "passenger", "seat#" + seatN + " count", "%", "cum%"));
132        } catch (BuildException exception) {
133            throw exception;
134        } catch (Throwable throwable) {
135            throwable.printStackTrace();
136            throw new BuildException(throwable);
137        }
138    }
139
140    private List<Integer> asList(int start, int end) {
141        Integer[] array = new Integer[end - start];
142
143        for (int i = 0; i < array.length; i += 1) {
144            array[i] = start + i;
145        }
146
147        return Collections.unmodifiableList(Arrays.asList(array));
148    }
149
150    private class Simulation extends TreeMap<Integer,Integer> {
151        private static final long serialVersionUID = -4047361911757741221L;
152
153        public Simulation(List<Integer> passengers, List<Integer> seats) {
154            passengers = new ArrayList<>(passengers);
155            seats = new ArrayList<>(seats);
156            /*
157             * First passenger chooses any seat.
158             */
159            Collections.sort(passengers);
160            Collections.shuffle(seats);
161            put(seats.remove(0), passengers.remove(0));
162            /*
163             * Remaining passenger takes their assigned seat unless someone
164             * has already taken their's.
165             */
166            for (int p : passengers) {
167                int s = p;
168
169                if (! seats.remove((Object) s)) {
170                    s = seats.remove(0);
171                }
172
173                put(s, p);
174            }
175        }
176    }
177}