amusement park scheduling rides using dynamic programming
You arrive at Waldo's World Amusement Park with T minutes remaining until the park closes. The park has n rides and your objective is to complete as many rides as possible before the park closes. (For this problem, taking the same ride twice counts as 2 rides.) You are given a table W such that W(i, t) gives you the waiting time for ride i at time t. For convenience, assume that t is expressed as minutes before the park closes. Ride i itself takes ri minutes and all times are measured in integer minutes.
I tried solving it using a method similar to 0 1 knapsack problem. But the Table W which contains the waiting time for ride i varies wrt to time t. Is it exactly a knapsack plus activity selection combined problem?
1 answer

Would this make any sense? Let
f(t)
represent the most achievable rides at timet
. Then:// Higher t is back in time // since t is how many minutes // before the park closes f(t) = max( // Not taking any ride f(t  1), // Take ride i 1 + f(t  W(i, t)  r_i) ) for all i
See also questions close to this topic

compress list of numbers into unique non overlapping time ranges using python
I'm from biology and very new to python and ML, the lab has a blackbox ML model which outputs a sequence like this :
Predictions = [1,1,1,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,0,1,1,1,1,1,1,0]
each value represents a predicted time frame of duration 0.25seconds.
1 means High.
0 means Not High.How do I convert these predictions into a [start,stop,label] ?
so that longer sequences are grouped example the first 10 ones represent 0 to 10*.25s thus the first range and label would be[[0.0,2.5, High]
next there are 13 zeroes ===> start = (2.5), stop = 13*.25 +2.5, label = Not high
thus
[2.5, 5.75, NotHigh]so final list would be something like a list of lists/ranges with unique non overlapping intervals along with a label like :
[[0.0,2.5, High], [2.5, 5.75, NotHigh], [5.75,6.50, High] ..
What I tried:
1. Count number of values in Predictions
2. Generate two ranges , one starting at zero and another starting at 0.25
3. merge these two lists into tuplesimport numpy as np len_pred = len(Predictions) range_1 = np.arange(0,len_pred,0.25) range_2 = np.arange(0.25,len_pred,0.25) new_range = zip(range_1,range_2)
Here I'm able to get the ranges, but missing out on the labels.
Seems like simple problem but I'm running in circles.Please advise. Thanks.

Java program to generate all possible sequence of prioritized test suite
I'm creating a java program that can reorder a test suite by prioritizing them based on the modified transition the test cases traversed.
 Input = A 2 dimensional integer array where the rows represent the test cases while the columns represent the number of modified transition. For example, if test case 2 traversed modified transition 3, then
testSuite[1][2] = 1
. If not,testSuite[1][2] = 0
.  Output = A string arraylist showing the test case number from highest priority to lowest ones.
 Prioritization criteria = Tries to equalize the execution of each modified transition. For example, (1) test case 2 that traversed modified transition 3 is selected into the prioritized ordering, then (2) the execution count for modified transition 3 will be increased by 1. Next, the approach (3) identifies modified transitions with least execution count, select (4) one of them randomly, then (5) select randomly a test case that traverses the selected modified transition. Then, repeat steps 2  5 until all test cases that traverse at least one modified transition are selected into prioritized ordering.
The actual proposed approach is from the even spread countbased test prioritization approach from this paper https://link.springer.com/article/10.1007/s112190169330x . I have successfully created a working program but it only generates a single ordering where this approach has the possibility of generating more than 1 ordering. So I want to be able to generate all the possible ordering but have no clue of how it can be done using the current program I had created. Below is the coding for the approach. any improvement or addition to the actual coding is also appreciated.
import java.util.ArrayList; public class EvenSpread { public static void main(String[] args) { //Input //# of test cases vs # of modified transitions traversed for each test case int [][]testSuite = { {0,0,0,0,0,0,0}, {0,0,1,1,0,0,0}, {1,0,0,0,0,0,1}, {0,0,1,0,1,0,0}, {0,0,1,0,1,1,0}, {0,1,0,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,1,0,0}, {0,0,1,0,1,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,1,0,1,0,0} }; //get # of test cases and # of modified transitions from testSuite array final int NUM_OF_MODIFIEDTRANSITION = testSuite[0].length; final int NUM_OF_TC = testSuite.length; //for storing prioritized ordering ArrayList<String> ordering = new ArrayList<String>(); //for storing test cases with at least one modified transition ArrayList<Integer> TCWithModifiedTransition = new ArrayList<Integer>(); //for storing modified transition with the least execution count for a particular iteration ArrayList<Integer> ModifiedTransitionWithLeastExecution = new ArrayList<Integer>(); //for storing the value of the least execution count int min; //Initialize modified transition execution count and set to zero int[] modifiedTransitionExecution = new int[NUM_OF_MODIFIEDTRANSITION]; for (int i = 0; i < modifiedTransitionExecution.length; i++) modifiedTransitionExecution[i] = 0; //Identify and store info of test cases with at least one modified transition for (int i = 0; i < NUM_OF_TC; i++) for (int j = 0; j < NUM_OF_MODIFIEDTRANSITION; j++) if (testSuite[i][j] == 1) { TCWithModifiedTransition.add(i); break; } //Print all test cases with modified transition System.out.println(""); System.out.println("Remaining test case = "); for(int word : TCWithModifiedTransition) System.out.print(word + " "); System.out.println(""); //prioritize test cases containing modified transitions until all are selected while (!TCWithModifiedTransition.isEmpty()) { //needs to be reset because in next iteration the lowest value might increase min = 100; //Update the modified transition with least execution number for (int i = 0; i < NUM_OF_MODIFIEDTRANSITION; i++) if (modifiedTransitionExecution[i] < min) min = modifiedTransitionExecution[i]; //needs to be cleared because each iteration it may changes ModifiedTransitionWithLeastExecution.clear(); //Put modified transitions with least execution into an arraylist for (int i = 0; i < NUM_OF_MODIFIEDTRANSITION; i++) if (modifiedTransitionExecution[i] == min) ModifiedTransitionWithLeastExecution.add(i); int k = 0, m = 0; while ( k < TCWithModifiedTransition.size() ) { if (testSuite[TCWithModifiedTransition.get(k)][ModifiedTransitionWithLeastExecution.get(m)] == 1) { //put selected test case into prioritized ordering ordering.add(TCWithModifiedTransition.get(k).toString()); //increase execution count of modified transition traversed in selected test case for (int l = 0; l < NUM_OF_MODIFIEDTRANSITION; l++) if (testSuite[TCWithModifiedTransition.get(k)][l] == 1) modifiedTransitionExecution[l] += 1; System.out.println(""); System.out.println("remove test case " + TCWithModifiedTransition.get(k)); //remove selected test case from arraylist TCWithModifiedTransition.remove(k); for (int i = 0; i < modifiedTransitionExecution.length; i++) System.out.print("MT" + i + "=" + modifiedTransitionExecution[i] + ", "); System.out.println(""); System.out.print("Remaining test case = "); for(int word : TCWithModifiedTransition) System.out.print(word + " "); System.out.println(""); break; } k++; //if no test case traverse current modified transition with least execution, //move to next modified transition with least execution if (k == TCWithModifiedTransition.size()) { m++; k = 0; } //if no more test case traverse the least executed modified transition, //move to next least executed modified transition if (m == ModifiedTransitionWithLeastExecution.size()) { m = 0; k = 0; min += 1; //Put modified transitions with new least execution into an arraylist for (int j = 0; j < NUM_OF_MODIFIEDTRANSITION; j++) if (modifiedTransitionExecution[j] == min) ModifiedTransitionWithLeastExecution.add(j); } } } //Put remaining test cases into ordering for (int i = 0; i < NUM_OF_TC; i++) for (int j = 0; j < NUM_OF_MODIFIEDTRANSITION; j++) { if (testSuite[i][j] == 1) break; if (j == (NUM_OF_MODIFIEDTRANSITION1) && testSuite[i][j] == 0) ordering.add(Integer.toString(i)); } //Output System.out.print("Prioritized ordering = "); for(String word : ordering) System.out.print(word + " "); } }
 Input = A 2 dimensional integer array where the rows represent the test cases while the columns represent the number of modified transition. For example, if test case 2 traversed modified transition 3, then

Clamping to next lowest value in a series
I'm trying to clamp a number to the lower value of a series of numbers. For instance, if I have a series (sorry for the bad notation)
[pq]
wherep
is any integer andq
is any positive number.Say if
q is 50
my series will be...150, 100, 50, 0, 50, 100, 150...
Now what I'd like is to have a function
f(y)
which'll clamp any number to the next lowest number in the series.For example, if I had the number
37
I'd be expecting thef(37) = 0
and I'd be expectingf(37) = 50
.I've tried many algorithms involving modulus and integer division but I can't seem to figure it out. The latest I've tried is for example
(37 / q) * q
which works great for positive numbers but doesn't work for any number between 50 and 0.I've also tried
((37  q) / q) * q
but this won't work for negative cases which land exactly in the series.EDIT
Assume that I do not have the entire series but only the multiplier
p
of the series. 
Algorithm: Computing tower locations to minimize expected distance
I came across this question while studying for my graduate algorithms class:
Say you have
p
towers that you want to place along a line ofn
cities, where each city is an integer from 1 to n. The cost of placing the tower is the expected distance from the tower to the rest of the cities. The problem is to provide an efficient algorithm to place all thep
towers while minimizing cost.There is a greedy approach given here : https://www.mssanz.org.au/modsim2015/J11/dzator.pdf, but it doesn't seem too efficient.
So far, I've tried attacking the problem using dynamic programming. For example, if there is 1 tower and 5 cities, I go through each of the cities as a potential candidate for the tower and calculate the cost of placing the tower there. Then, I choose the city that minimizes the cost.
However, I am having trouble following up when there are 2 or more towers. I tried to divide the cities into distinct, continuous subsets, but I can't seem to progress from that  i.e. I can't seem to identify the subproblems.
Any pointers?
EDIT:
The cost of a tower is exactly as described in the question: it is the distance to the cities from the position of the tower. However, placing a tower will affect how other towers are placed, since people of a particular city will go to their closest tower.

How to find the longest subsequence with a maximum slope
So I have a sequence
[a1, a2, ..., an]
and a slopem
and I need to find the longest subsequence such that if[ai1, ai2, ..., aik]
is my subsequence output then for alli
,j (i<j)
,(aj  ai)/(ji) <= m
. 
Debug coin change Dynamic Programming
My coin change dynamic programming implementation is failing for some of the test cases, and I am having a hard time figuring out why:
Problem Statement: Given an amount and a list of coins, find the minimum number of coins required to make that amount.
Ex:
Target Amount: 63
Coin List: [1, 5, 10, 21, 25]
Output: [21, 21, 21]def coin_change(change_list, amount, tried): if amount <= 0: return [] if amount in change_list: return [amount] if amount in tried: return tried[amount] coin_count = [] for change in change_list: if change < amount: changes = coin_change(change_list, amountchange, tried) changes.append(change) coin_count.append(changes) min_changes = coin_count[0][:] for x in coin_count[1:]: if len(min_changes) >= len(x): min_changes = x[:] tried[amount] = min_changes[:] return min_changes def main(): for amount in range(64): changes = coin_change([1, 5, 10, 21, 25], amount, {}) if sum(changes) != amount: print "WRONG: Change for %d is: %r" % (amount, changes) else: # print "Change for %d is: %r" % (amount, changes) pass if __name__ == "__main__": main()
Trinket: https://trinket.io/python/43fcff035e

Can't install Matplotlib in python 3.7
For install matplotlib in windows 10 64 bit machine get error showing
python setup.py egg_info" failed with error code 1 in C:\Users\Animus\AppData\Local\Temp\pipbuildurqbuxb_\unroll\
please help

Multivariate linear mixed effects model in Python
I am playing around with this code which is for Univariate linear mixed effects modelling. The data set denotes:
 students as s
 instructors as d
 departments as dept
 service as service
In the syntax of R's lme4 package (Bates et al., 2015), the model implemented can be summarized as:
y ~ 1 + (1students) + (1instructor) + (1dept) + service
where 1 denotes an intercept term,(1x) denotes a random effect for x, and x denotes a fixed effect.
from __future__ import absolute_import from __future__ import division from __future__ import print_function import edward as ed import pandas as pd import tensorflow as tf import matplotlib.pyplot as plt from edward.models import Normal from observations import insteval data = pd.DataFrame(data, columns=metadata['columns']) train = data.sample(frac=0.8) test = data.drop(train.index) train.head()
s_train = train['s'].values d_train = train['dcodes'].values dept_train = train['deptcodes'].values y_train = train['y'].values service_train = train['service'].values n_obs_train = train.shape[0] s_test = test['s'].values d_test = test['dcodes'].values dept_test = test['deptcodes'].values y_test = test['y'].values service_test = test['service'].values n_obs_test = test.shape[0] n_s = max(s_train) + 1 # number of students n_d = max(d_train) + 1 # number of instructors n_dept = max(dept_train) + 1 # number of departments n_obs = train.shape[0] # number of observations # Set up placeholders for the data inputs. s_ph = tf.placeholder(tf.int32, [None]) d_ph = tf.placeholder(tf.int32, [None]) dept_ph = tf.placeholder(tf.int32, [None]) service_ph = tf.placeholder(tf.float32, [None]) # Set up fixed effects. mu = tf.get_variable("mu", []) service = tf.get_variable("service", []) sigma_s = tf.sqrt(tf.exp(tf.get_variable("sigma_s", []))) sigma_d = tf.sqrt(tf.exp(tf.get_variable("sigma_d", []))) sigma_dept = tf.sqrt(tf.exp(tf.get_variable("sigma_dept", []))) # Set up random effects. eta_s = Normal(loc=tf.zeros(n_s), scale=sigma_s * tf.ones(n_s)) eta_d = Normal(loc=tf.zeros(n_d), scale=sigma_d * tf.ones(n_d)) eta_dept = Normal(loc=tf.zeros(n_dept), scale=sigma_dept * tf.ones(n_dept)) yhat = (tf.gather(eta_s, s_ph) + tf.gather(eta_d, d_ph) + tf.gather(eta_dept, dept_ph) + mu + service * service_ph) y = Normal(loc=yhat, scale=tf.ones(n_obs)) #Inference q_eta_s = Normal( loc=tf.get_variable("q_eta_s/loc", [n_s]), scale=tf.nn.softplus(tf.get_variable("q_eta_s/scale", [n_s]))) q_eta_d = Normal( loc=tf.get_variable("q_eta_d/loc", [n_d]), scale=tf.nn.softplus(tf.get_variable("q_eta_d/scale", [n_d]))) q_eta_dept = Normal( loc=tf.get_variable("q_eta_dept/loc", [n_dept]), scale=tf.nn.softplus(tf.get_variable("q_eta_dept/scale", [n_dept]))) latent_vars = { eta_s: q_eta_s, eta_d: q_eta_d, eta_dept: q_eta_dept} data = { y: y_train, s_ph: s_train, d_ph: d_train, dept_ph: dept_train, service_ph: service_train} inference = ed.KLqp(latent_vars, data)
This works fine in the univariate case for Linear mixed effects modelling. I am trying to extend this approach to the multivariate case. Any ideas are more than welcome.

Fastest sentiment analysis method for python
I need some help with sentiment analysis in Python. I have thousands of thousands of thousands (let's say 200000) tweets stored in data frame. I am doing tweet cleaning, removing weird signs, and translating to English. But it's slow. I tried text blob, but still.. its so slow. Anybody got an idea how to do it in a blink of an eye ?