How to measure students’ Computational Problem-Solving (CPS) competencies is an ongoing research topic. Prevalent approaches vary by measurement tools (e.g., interactive programming, multiple-choice tests, or programming-independent tests) and task types (e.g., debugging problems or Parson problems). However, few studies have examined the measurement tools of CPS competencies themselves: affordances and limitations of the measurement tools and how they compare, or whether different task types might elicit CPS competencies differently. Research needs to address these questions in order to better understand how to design robust, generalizable, and effective measurement tools for CPS competencies. This paper presents an exploratory study that contributes to this research direction. It is part of a larger international project to develop an open-access formative assessment platform for CPS, which includes a novel authoring tool for a wide range of task types for interactive block-based programming. We used the tool to create an interactive programming experience with multiple task types, and gave it to more than 300 secondary school students from different countries. We also gave a validated multiple-choice measurement of Computational Thinking with block-based programs. We focused on task complexity as a characteristics of task type, using a classification scheme based on task design features. Comparing students’ performances on tasks of different complexity and between measurement tools, we found that the multiple-choice measurement only partially predicts performance on the interactive programming task, and that its predictive capacity varies significantly between task types of different complexity. We conclude with a discussion of the implications of this empirical exploration.